1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
// 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");
}
}
|
