// This is free and unencumbered software released into the public domain.
//
// Anyone is free to copy, modify, publish, use, compile, sell, or
// distribute this software, either in source code form or as a compiled
// binary, for any purpose, commercial or non-commercial, and by any
// means.

// A simple Sieve of Eratosthenes

#include "firmware.h"

#define BITMAP_SIZE 64

static uint32_t bitmap[BITMAP_SIZE / 32];
static uint32_t hash;

static uint32_t mkhash(uint32_t a, uint32_t b)
{
    // The XOR version of DJB2
    return ((a << 5) + a) ^ b;
}

static void bitmap_set(int idx)
{
    bitmap[idx / 32] |= 1 << (idx % 32);
}

static bool bitmap_get(int idx)
{
    return (bitmap[idx / 32] & (1 << (idx % 32))) != 0;
}

static void print_prime(int idx, int val)
{
    if (idx < 10)
        print_str(" ");
    print_dec(idx);
    if (idx / 10 == 1)
        goto force_th;
    switch (idx % 10) {
    case 1:
        print_str("st");
        break;
    case 2:
        print_str("nd");
        break;
    case 3:
        print_str("rd");
        break;
    force_th:
    default:
        print_str("th");
        break;
    }
    print_str(" prime is ");
    print_dec(val);
    print_str(".\n");

    hash = mkhash(hash, idx);
    hash = mkhash(hash, val);
}

void sieve(void)
{
    int idx = 1;
    hash = 5381;
    print_prime(idx++, 2);
    for (int i = 0; i < BITMAP_SIZE; i++) {
        if (bitmap_get(i))
            continue;
        print_prime(idx++, 3 + 2 * i);
        for (int j = 2 * (3 + 2 * i);; j += 3 + 2 * i) {
            if (j % 2 == 0)
                continue;
            int k = (j - 3) / 2;
            if (k >= BITMAP_SIZE)
                break;
            bitmap_set(k);
        }
    }

    print_str("checksum: ");
    print_hex(hash, 8);

    if (hash == 0x1772A48F) {
        print_str(" OK\n");
    } else {
        print_str(" ERROR\n");
        __asm__ volatile("ebreak");
    }
}
