_primes_bitpacked_inline.nx source

1// _primes_bitpacked_inline.nx -- bit-packed sieve with MANUALLY inlined bit ops. 2// 3// Same algorithm as _primes_bitpacked.nx, but all bit-get / bit-set 4// calls are inlined into the hot loop -- substrate backend doesn't 5// aggressively inline so we do it by hand. 6 7import "syscalls.nx" 8 9const SIEVE_SIZE: i64 = 1000000 10const N_PASSES: i64 = 100 11 12func one_pass(buf: *u8, half: i64, byte_count: i64) -> i64 { 13 var i: i64 = 0 14 while i < byte_count { 15 buf[i] = 0 as u8 16 i = i + 1 17 } 18 var factor: i64 = 3 19 while factor * factor <= SIEVE_SIZE { 20 let factor_idx: i64 = (factor - 3) / 2 21 var fi: i64 = factor_idx 22 var done: i64 = 0 23 while done == 0 { 24 if fi >= half { done = 1 } 25 if done == 0 { 26 // INLINE bit_get 27 let byte_idx_g: i64 = fi >> 3 28 let bit_idx_g: i64 = fi & 7 29 let bit_g: i64 = ((buf[byte_idx_g] as i64) >> bit_idx_g) & 1 30 if bit_g == 0 { done = 1 } 31 if done == 0 { fi = fi + 1 } 32 } 33 } 34 if fi >= half { return -1 } 35 let cur_num: i64 = 2 * fi + 3 36 var mult: i64 = cur_num * cur_num 37 while mult <= SIEVE_SIZE { 38 let idx: i64 = (mult - 3) / 2 39 // INLINE bit_set 40 let byte_idx_s: i64 = idx >> 3 41 let bit_idx_s: i64 = idx & 7 42 let mask: i64 = 1 << bit_idx_s 43 buf[byte_idx_s] = ((buf[byte_idx_s] as i64) | mask) as u8 44 mult = mult + 2 * cur_num 45 } 46 factor = cur_num + 2 47 } 48 var count: i64 = 1 49 var k: i64 = 0 50 while k < half { 51 // INLINE bit_get 52 let bi: i64 = k >> 3 53 let bi_off: i64 = k & 7 54 let b: i64 = ((buf[bi] as i64) >> bi_off) & 1 55 if b == 0 { 56 let n: i64 = 2 * k + 3 57 if n <= SIEVE_SIZE { count = count + 1 } 58 } 59 k = k + 1 60 } 61 return count 62} 63 64func main() -> i64 { 65 let half: i64 = SIEVE_SIZE / 2 66 let byte_count: i64 = (half + 7) / 8 67 let buf: *u8 = sys_mmap(byte_count) 68 var p: i64 = 0 69 var c: i64 = 0 70 while p < N_PASSES { 71 c = one_pass(buf, half, byte_count) 72 p = p + 1 73 } 74 if c != 78498 { return 2 } 75 return 0 76}