Created
February 21, 2022 16:09
-
-
Save pnkfelix/0b5d19c7b267dc73a73f99b43cfea4ea to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
mod streaming { | |
use primal_bit::BitVec; | |
use std::cmp; | |
use crate::wheel; | |
mod primes { | |
use crate::wheel; | |
use crate::streaming::{self, StreamingSieve}; | |
pub(crate) struct Primes { | |
base: usize, | |
ones: ::primal_bit::IntoOnes, | |
streaming: StreamingSieve, | |
sieving_primes: Option<Box<Primes>>, | |
left_over: Option<usize>, | |
} | |
impl Primes { | |
#[inline] | |
fn from_bit_index(&self, i: usize) -> Option<usize> { | |
let w = wheel::from_bit_index(i); | |
self.base.checked_add(w) | |
} | |
fn advance_ones(&mut self) -> bool { | |
let low = self.streaming.low; | |
let high = low.saturating_add(streaming::SEG_LEN); | |
for q in self.left_over.into_iter().chain(self.sieving_primes.as_mut().unwrap()) { | |
if q.saturating_mul(q) >= high { | |
self.left_over = Some(q); | |
break | |
} | |
if q > streaming::isqrt(streaming::SEG_LEN) { | |
self.streaming.add_sieving_prime(q, low); | |
} | |
} | |
match self.streaming.next() { | |
Some((_, bits)) => { | |
self.base = low; | |
self.ones = bits.clone().into_ones(); | |
true | |
}, | |
None => false, | |
} | |
} | |
} | |
// See also `Iterator for SievePrimes` with nearly identical code. | |
impl Iterator for Primes { | |
type Item = usize; | |
#[inline] | |
fn next(&mut self) -> Option<usize> { | |
loop { | |
if let Some(i) = self.ones.next() { | |
return self.from_bit_index(i); | |
} | |
if !self.advance_ones() { | |
return None; | |
} | |
} | |
} | |
} | |
} | |
mod presieve { | |
use primal_bit::BitVec; | |
use std::cmp; | |
use crate::wheel; | |
use super::StreamingSieve; | |
const MINIMUM_PRESIEVE: usize = 2 * 3 * 5; | |
const PRESIEVE_PRIMES: &[usize] = &[7, 11, 13, 17, 19, 23, 29]; | |
pub(crate) struct Presieve { | |
sieve: BitVec, | |
presieve_prod: usize, | |
presieve_idx: usize, | |
} | |
impl Presieve { | |
#[inline(never)] | |
pub(crate) fn new(limit_bits: usize) -> Presieve { | |
let mut prod = MINIMUM_PRESIEVE; | |
let mut idx = 0; | |
for (i, &x) in PRESIEVE_PRIMES.iter().enumerate() { | |
let new_prod = prod * x; | |
if wheel::bits_for(new_prod) > limit_bits { | |
break | |
} | |
prod = new_prod; | |
idx = i; | |
} | |
let len = cmp::min(wheel::bits_for(prod), limit_bits); | |
if idx == 0 { | |
Presieve { | |
sieve: BitVec::new(), | |
presieve_prod: prod, | |
presieve_idx: idx, | |
} | |
} else { | |
let mut sievers = vec![]; | |
for &x in &PRESIEVE_PRIMES[..idx] { | |
let (use_, _idx) = wheel::bit_index(x); | |
if use_ { | |
sievers.push(wheel::State::new(wheel::Wheel30, x, prod)); | |
} | |
} | |
let mut sieve = BitVec::from_elem(len, true); | |
StreamingSieve::small_primes_sieve(&mut sieve, &mut sievers); | |
Presieve { | |
sieve, | |
presieve_prod: prod, | |
presieve_idx: idx, | |
} | |
} | |
} | |
// called from StreamingSieve::new | |
pub(crate) fn smallest_unincluded_prime(&self) -> usize { | |
PRESIEVE_PRIMES[self.presieve_idx] | |
} | |
// called from StreamingSieve::next | |
pub(crate) fn mark_small_primes(&self, sieve: &mut BitVec) { | |
for &x in &PRESIEVE_PRIMES[..self.presieve_idx] { | |
let (use_, idx) = wheel::bit_index(x); | |
if use_ { | |
sieve.set(idx, true) | |
} | |
} | |
} | |
// called from StreamingSieve::next | |
pub(crate) fn apply(&self, sieve: &mut BitVec, low: usize) { | |
if self.sieve.len() == 0 { | |
return | |
} | |
let offset = (low % self.presieve_prod) * wheel::BYTE_SIZE / wheel::BYTE_MODULO / 8; | |
copy_all(sieve.as_bytes_mut(), | |
self.sieve.as_bytes(), | |
offset); | |
fn copy_all(dst: &mut [u8], src: &[u8], init_offset: usize) { | |
let mut pos = 0; | |
// pre-fill data at the start, as a rotation of `src`. | |
pos += memcpy(&mut dst[pos..], &src[init_offset..]); | |
if pos >= dst.len() { return } | |
pos += memcpy(&mut dst[pos..], &src[..init_offset]); | |
if pos >= dst.len() { return } | |
// progressively copy the prefix to the rest of the | |
// vector, doubling each time. | |
while pos < dst.len() { | |
let (filled, unfilled) = dst.split_at_mut(pos); | |
pos += memcpy(unfilled, filled); | |
} | |
} | |
fn memcpy<'d>(dst: &'d mut [u8], src: &[u8]) -> usize { | |
let l = cmp::min(dst.len(), src.len()); | |
dst[..l].copy_from_slice(&src[..l]); | |
l | |
} | |
} | |
} | |
} | |
pub(crate) struct StreamingSieve { | |
small: Option<crate::Sieve>, | |
sieve: BitVec, | |
primes: Vec<wheel::State<wheel::Wheel210>>, | |
small_primes: Vec<wheel::State<wheel::Wheel30>>, | |
large_primes: Vec<wheel::State<wheel::Wheel210>>, | |
presieve: presieve::Presieve, | |
low: usize, | |
current: usize, | |
limit: usize, | |
} | |
const CACHE: usize = 32 << 10; | |
const SEG_ELEMS: usize = 8 * CACHE; | |
const SEG_LEN: usize = SEG_ELEMS * wheel::BYTE_MODULO / wheel::BYTE_SIZE; | |
fn isqrt(x: usize) -> usize { | |
(x as f64).sqrt() as usize | |
} | |
impl StreamingSieve { | |
// called from Sieve::new | |
pub(crate) fn new(limit: usize) -> StreamingSieve { | |
let low = 0; | |
let elems = cmp::min(wheel::bits_for(limit), SEG_ELEMS); | |
let presieve = presieve::Presieve::new(elems); | |
let current = presieve.smallest_unincluded_prime(); | |
let small = if limit < current * current { | |
None | |
} else { | |
Some(crate::Sieve::new(isqrt(limit) + 1)) | |
}; | |
StreamingSieve { | |
small, | |
sieve: BitVec::from_elem(elems, true), | |
primes: vec![], | |
small_primes: vec![], | |
large_primes: vec![], | |
presieve, | |
low, | |
current, | |
limit | |
} | |
} | |
fn add_sieving_prime(&mut self, p: usize, low: usize) { | |
if p <= CACHE / 2 { | |
self.small_primes.push(wheel::State::new(wheel::Wheel30, p, low)); | |
} else { | |
let elem = wheel::State::new(wheel::Wheel210, p, low); | |
if p < CACHE * 5 / 2 { | |
self.primes.push(elem) | |
} else { | |
self.large_primes.push(elem) | |
} | |
} | |
} | |
fn find_new_sieving_primes(&mut self, low: usize, high: usize) { | |
if let Some(small) = self.small.take() { | |
for p in small.primes_from(self.current) { | |
if p * p >= high { | |
self.current = p; | |
break | |
} | |
self.add_sieving_prime(p, low); | |
} | |
self.small = Some(small); | |
} | |
} | |
fn small_primes_sieve<W: wheel::Wheel>(sieve: &mut BitVec, | |
small_primes: &mut [wheel::State<W>]) { | |
let bytes = sieve.as_bytes_mut(); | |
for wi in small_primes { | |
wi.sieve_hardcoded(bytes); | |
} | |
} | |
fn direct_sieve(&mut self) { | |
let bytes = self.sieve.as_bytes_mut(); | |
let mut chunks = self.primes.chunks_exact_mut(3); | |
while let Some([wi1, wi2, wi3]) = chunks.next() { | |
wi1.sieve_triple(wi2, wi3, bytes); | |
} | |
for wi in chunks.into_remainder() { | |
wi.sieve(bytes); | |
} | |
} | |
fn large_primes_sieve(&mut self) { | |
let bytes = self.sieve.as_bytes_mut(); | |
let mut chunks = self.large_primes.chunks_exact_mut(2); | |
while let Some([wi1, wi2]) = chunks.next() { | |
wi1.sieve_pair(wi2, bytes); | |
} | |
for wi in chunks.into_remainder() { | |
wi.sieve(bytes); | |
} | |
} | |
// called from Primes::advance_ones, Sieve::new | |
pub(crate) fn next(&mut self) -> Option<(usize, &BitVec)> { | |
if self.low >= self.limit { | |
return None | |
} | |
let low = self.low; | |
self.low = self.low.saturating_add(SEG_LEN); | |
let high = cmp::min(low.saturating_add(SEG_LEN - 1), self.limit); | |
self.find_new_sieving_primes(low, high); | |
self.presieve.apply(&mut self.sieve, low); | |
StreamingSieve::small_primes_sieve(&mut self.sieve, &mut self.small_primes); | |
self.direct_sieve(); | |
self.large_primes_sieve(); | |
if low == 0 { | |
// 1 is not prime. | |
self.sieve.set(0, false); | |
self.presieve.mark_small_primes(&mut self.sieve); | |
} | |
Some((low, &self.sieve)) | |
} | |
} | |
} | |
mod sieve { | |
use primal_bit::BitVec; | |
use crate::wheel; | |
use crate::streaming::StreamingSieve; | |
use std::cmp; | |
use std::slice; | |
pub(crate) struct Sieve { | |
seg_bits: usize, | |
nbits: usize, | |
// seen: SmallVec1<Item>, | |
seen: Vec<Item>, | |
} | |
struct Item { | |
bits: BitVec, | |
} | |
impl Item { | |
fn new(x: BitVec, so_far: &mut usize) -> Item { | |
*so_far += x.count_ones(); | |
Item { | |
bits: x, | |
} | |
} | |
} | |
impl Sieve { | |
pub(crate) fn new(limit: usize) -> Sieve { | |
let mut seen = Vec::new(); | |
let mut nbits = 0; | |
let mut so_far = 0; | |
let mut seg_bits = None; | |
match wheel::small_for(limit) { | |
Some(bits) => { | |
nbits = bits.len(); | |
seen.push(Item::new(bits, &mut 0)); | |
seg_bits = Some(nbits) | |
} | |
None => { | |
let mut stream = StreamingSieve::new(limit); | |
while let Some((n, bits)) = stream.next() { | |
let bits_limit = wheel::bit_index((limit - n).saturating_add(1)).1; | |
seen.push(Item::new(bits.clone(), &mut so_far)); | |
nbits += cmp::min(bits.len(), bits_limit); | |
match seg_bits { | |
None => seg_bits = Some(bits.len()), | |
Some(old) => assert_eq!(old, bits.len()), | |
} | |
} | |
} | |
} | |
let seg_bits_adjust = if seen.len() == 1 { 1 } else { 0 }; | |
Sieve { | |
seg_bits: seg_bits.unwrap() + seg_bits_adjust, | |
nbits, | |
seen, | |
} | |
} | |
fn split_index(&self, idx: usize) -> (usize, usize) { | |
(idx / self.seg_bits, idx % self.seg_bits) | |
} | |
fn index_for(&self, n: usize) -> (bool, usize, usize) { | |
let (b, idx) = wheel::bit_index(n); | |
let (base, tweak) = self.split_index(idx); | |
(b, base, tweak) | |
} | |
pub(crate) fn upper_bound(&self) -> usize { | |
wheel::upper_bound(self.nbits) | |
} | |
pub(crate) fn primes_from(&self, n: usize) -> SievePrimes<'_> { | |
assert!(n <= self.upper_bound()); | |
let early = match n { | |
0..=2 => Early::Two, | |
3 => Early::Three, | |
4..=5 => Early::Five, | |
_ => Early::Done | |
}; | |
let (_, base, tweak) = self.index_for(n); | |
assert!(self.seen.len() == 1 || self.seg_bits % 8 == 0); | |
let base_byte_count = base * self.seg_bits / 8; | |
let bits = &self.seen[base].bits; | |
let current_base = base_byte_count * wheel::BYTE_MODULO; | |
let next_base = current_base + bits.len() * wheel::BYTE_MODULO / 8; | |
SievePrimes { | |
early, | |
base: current_base, | |
next_base, | |
ones: bits.ones_from(tweak), | |
limit: self.upper_bound(), | |
bits: self.seen[base + 1..].iter(), | |
} | |
} | |
} | |
#[derive(Clone)] | |
enum Early { | |
Two, | |
Three, | |
Five, | |
Done, | |
} | |
/// An iterator over the primes stored in a `Sieve` instance. | |
#[derive(Clone)] | |
pub(crate) struct SievePrimes<'a> { | |
early: Early, | |
base: usize, | |
next_base: usize, | |
limit: usize, | |
ones: ::primal_bit::Ones<'a>, | |
bits: slice::Iter<'a, Item>, | |
} | |
impl<'a> SievePrimes<'a> { | |
#[inline] | |
fn from_bit_index(&self, i: usize) -> Option<usize> { | |
let w = wheel::from_bit_index(i); | |
match self.base.checked_add(w) { | |
Some(p) if p <= self.limit => Some(p), | |
_ => None, | |
} | |
} | |
fn advance_ones(&mut self) -> bool { | |
match self.bits.next() { | |
Some(Item { bits, .. }) => { | |
self.base = self.next_base; | |
self.next_base += bits.len() * wheel::BYTE_MODULO / 8; | |
self.ones = bits.ones_from(0); | |
true | |
}, | |
None => false, | |
} | |
} | |
} | |
// See also `Iterator for Primes` with nearly identical code. | |
impl<'a> Iterator for SievePrimes<'a> { | |
type Item = usize; | |
#[inline] | |
fn next(&mut self) -> Option<usize> { | |
match self.early { | |
Early::Done => {} | |
Early::Two => { | |
self.early = Early::Three; | |
return Some(2) | |
} | |
Early::Three => { | |
self.early = Early::Five; | |
return Some(3) | |
} | |
Early::Five => { | |
self.early = Early::Done; | |
return Some(5) | |
} | |
} | |
loop { | |
if let Some(i) = self.ones.next() { | |
return self.from_bit_index(i); | |
} | |
if !self.advance_ones() { | |
return None; | |
} | |
} | |
} | |
} | |
} | |
pub(crate) use crate::sieve::{Sieve}; | |
pub fn main() { | |
let primes = Sieve::new(2_000_000); | |
let mut manual_sum = 0u64; | |
for p in primes.primes_from(0) { manual_sum += p as u64; } | |
dbg!(manual_sum); | |
assert_eq!(manual_sum, 533334666677); | |
} | |
mod wheel { | |
use std::cmp; | |
use primal_bit::BitVec; | |
pub(crate) const BYTE_SIZE: usize = 8; | |
pub(crate) const BYTE_MODULO: usize = 30; | |
const WHEEL_OFFSETS: &[usize; BYTE_MODULO] = &[ | |
0, 0, 0, 0, 0, 0, | |
0, 1, 0, 0, 0, 2, | |
0, 3, 0, 0, 0, 4, | |
0, 5, 0, 0, 0, 6, | |
0, 0, 0, 0, 0, 7, | |
]; | |
pub(crate) fn small_for(x: usize) -> Option<BitVec> { | |
let bits = bits_for(x); | |
if bits < wheel30::SMALL_BITS { | |
let bytes = (bits + 8 - 1) / 8; | |
Some(BitVec::from_bytes(wheel30::SMALL[..bytes].to_owned(), bits)) | |
} else { | |
None | |
} | |
} | |
pub(crate) fn bits_for(x: usize) -> usize { | |
// ceil((x * BYTE_SIZE) / BYTE_MODULO) | |
// computed using the remainder to avoid overflow | |
let d = x / BYTE_MODULO; | |
let r = x % BYTE_MODULO; | |
d * BYTE_SIZE + (r * BYTE_SIZE + BYTE_MODULO - 1) / BYTE_MODULO | |
} | |
pub(crate) fn bit_index(n: usize) -> (bool, usize) { | |
const POS: &[(bool, u8); BYTE_MODULO] = &[ | |
// 0 | |
(false, 0), (true, 0), (false, 1), (false, 1), (false, 1), (false, 1), | |
// 6 | |
(false, 1), (true, 1), (false, 2), (false, 2), (false, 2), (true, 2), | |
// 12 | |
(false, 3), (true, 3), (false, 4), (false, 4), (false, 4), (true, 4), | |
// 18 | |
(false, 5), (true, 5), (false, 6), (false, 6), (false, 6), (true, 6), | |
// 24 | |
(false, 7), (false, 7), (false, 7), (false, 7), (false, 7), (true, 7), | |
]; | |
let init = &POS[n % BYTE_MODULO]; | |
(init.0, (n / BYTE_MODULO) * BYTE_SIZE + init.1 as usize) | |
} | |
pub(crate) fn upper_bound(nbits: usize) -> usize { | |
// basically from_bit_index(nbits)-1, but without overflow | |
(nbits / BYTE_SIZE) | |
.saturating_mul(BYTE_MODULO) | |
.saturating_add(TRUE_AT_BIT[nbits % BYTE_SIZE] - 1) | |
} | |
#[inline] | |
pub(crate) fn from_bit_index(bit: usize) -> usize { | |
(bit / BYTE_SIZE) * BYTE_MODULO + TRUE_AT_BIT[bit % BYTE_SIZE] | |
} | |
const TRUE_AT_BIT: &[usize; 8] = &[1, 7, 11, 13, 17, 19, 23, 29]; | |
pub(crate) use self::wheel30::Wheel30; | |
pub(crate) use self::wheel210::Wheel210; | |
pub(crate) trait Wheel { | |
fn modulo(&self) -> usize; | |
fn size(&self) -> usize; | |
fn wheel(&self) -> &'static [WheelElem]; | |
fn init(&self) -> &'static [WheelInit]; | |
unsafe fn hardcoded_sieve(&self, | |
bytes: &mut [u8], si_: &mut usize, wi_: &mut usize, prime: usize); | |
} | |
type SI = u32; | |
type WI = u16; | |
#[derive(Debug)] | |
pub(crate) struct State<W> { | |
wheel: W, | |
prime: u32, | |
wheel_index: WI, | |
sieve_index: SI, | |
} | |
impl<W: Wheel> State<W> { | |
pub(crate) fn new(w: W, p: usize, low: usize) -> State<W> { | |
let q = cmp::max(low / p + 1, p); | |
// the smallest (interesting) multiple of p larger than low | |
let mut mult = p * q; | |
let init = &w.init()[q % w.modulo()]; | |
// push it up to the smallest multiple that is in the wheel | |
mult += p * init.next_mult_factor as usize; | |
// find the memory location to write to | |
let low_offset = mult - low; | |
let sieve_index = low_offset / BYTE_MODULO; | |
// and now the right info to write | |
let wheel_index = WHEEL_OFFSETS[p % BYTE_MODULO] * w.size() + init.wheel_index as usize; | |
let prime = p / BYTE_MODULO; | |
State { | |
wheel: w, | |
prime: prime as u32, | |
sieve_index: sieve_index as SI, | |
wheel_index: wheel_index as WI, | |
} | |
} | |
#[inline] | |
pub(crate) fn sieve(&mut self, bytes: &mut [u8]) { | |
let bytes = bytes; | |
let top = bytes.len(); | |
let mut si = self.sieve_index as usize; | |
let mut wi = self.wheel_index as usize; | |
let p = self.prime as usize; | |
while si < top { | |
raw_set_bit(self.wheel.wheel(), | |
bytes, &mut si, &mut wi, p) | |
} | |
self.sieve_index = si.wrapping_sub(top) as SI; | |
self.wheel_index = wi as WI; | |
} | |
#[inline] | |
pub(crate) fn sieve_pair(&mut self, self2: &mut State<W>, bytes: &mut [u8]) { | |
let bytes = bytes; | |
let top = bytes.len(); | |
let wheel = self.wheel.wheel(); | |
let mut si1 = self.sieve_index as usize; | |
let mut wi1 = self.wheel_index as usize; | |
let p1 = self.prime as usize; | |
let mut si2 = self2.sieve_index as usize; | |
let mut wi2 = self2.wheel_index as usize; | |
let p2 = self2.prime as usize; | |
while si1 < top && si2 < top { | |
raw_set_bit(wheel, | |
bytes, &mut si1, &mut wi1, p1); | |
raw_set_bit(wheel, | |
bytes, &mut si2, &mut wi2, p2); | |
} | |
while si1 < top { | |
raw_set_bit(wheel, | |
bytes, &mut si1, &mut wi1, p1); | |
} | |
while si2 < top { | |
raw_set_bit(wheel, | |
bytes, &mut si2, &mut wi2, p2); | |
} | |
// if this wraps, we've hit the limit, and so won't be | |
// continuing, so whatever, it can be junk. | |
self.sieve_index = si1.wrapping_sub(top) as SI; | |
self.wheel_index = wi1 as WI; | |
self2.sieve_index = si2.wrapping_sub(top) as SI; | |
self2.wheel_index = wi2 as WI; | |
} | |
pub(crate) fn sieve_triple(&mut self, self2: &mut State<W>, self3: &mut State<W>, | |
bytes: &mut [u8]) { | |
let bytes = bytes; | |
let top = bytes.len(); | |
let wheel = self.wheel.wheel(); | |
let mut si1 = self.sieve_index as usize; | |
let mut wi1 = self.wheel_index as usize; | |
let p1 = self.prime as usize; | |
let mut si2 = self2.sieve_index as usize; | |
let mut wi2 = self2.wheel_index as usize; | |
let p2 = self2.prime as usize; | |
let mut si3 = self3.sieve_index as usize; | |
let mut wi3 = self3.wheel_index as usize; | |
let p3 = self3.prime as usize; | |
while si1 < top && si2 < top && si3 < top { | |
raw_set_bit(wheel, | |
bytes, &mut si1, &mut wi1, p1); | |
raw_set_bit(wheel, | |
bytes, &mut si2, &mut wi2, p2); | |
raw_set_bit(wheel, | |
bytes, &mut si3, &mut wi3, p3); | |
} | |
while si1 < top { | |
raw_set_bit(wheel, | |
bytes, &mut si1, &mut wi1, p1); | |
} | |
while si2 < top { | |
raw_set_bit(wheel, | |
bytes, &mut si2, &mut wi2, p2); | |
} | |
while si3 < top { | |
raw_set_bit(wheel, | |
bytes, &mut si3, &mut wi3, p3); | |
} | |
// if this wraps, we've hit the limit, and so won't be | |
// continuing, so whatever, it can be junk. | |
self.sieve_index = si1.wrapping_sub(top) as SI; | |
self.wheel_index = wi1 as WI; | |
self2.sieve_index = si2.wrapping_sub(top) as SI; | |
self2.wheel_index = wi2 as WI; | |
self3.sieve_index = si3.wrapping_sub(top) as SI; | |
self3.wheel_index = wi3 as WI; | |
} | |
pub(crate) fn sieve_hardcoded(&mut self, bytes: &mut [u8]) { | |
let mut si = self.sieve_index as usize; | |
let mut wi = self.wheel_index as usize; | |
unsafe { | |
self.wheel.hardcoded_sieve(bytes, | |
&mut si, &mut wi, self.prime as usize) | |
} | |
self.sieve_index = si as SI; | |
self.wheel_index = wi as WI; | |
} | |
} | |
#[derive(Debug)] | |
pub(crate) struct WheelInit { | |
next_mult_factor: u8, | |
wheel_index: u8, | |
} | |
#[derive(Debug)] | |
pub(crate) struct WheelElem { | |
unset_bit: u8, | |
next_mult_factor: u8, | |
correction: u8, | |
next: i8, | |
} | |
#[inline(always)] | |
#[cfg(not(feature = "safe"))] | |
fn raw_set_bit(wheel: &'static [WheelElem], | |
x: &mut [u8], si: &mut usize, wi: &mut usize, prime: usize) { | |
unsafe { | |
let WheelElem { unset_bit, next_mult_factor, correction, next } = | |
*wheel.get_unchecked(*wi); | |
*x.get_unchecked_mut(*si) &= unset_bit; | |
*si += prime * next_mult_factor as usize; | |
*si += correction as usize; | |
*wi = wi.wrapping_add(next as usize); | |
} | |
} | |
#[inline(always)] | |
#[cfg(feature = "safe")] | |
fn raw_set_bit(wheel: &'static [WheelElem], | |
x: &mut [u8], si: &mut usize, wi: &mut usize, prime: usize) { | |
let WheelElem { unset_bit, next_mult_factor, correction, next } = wheel[*wi]; | |
x[*si] &= unset_bit; | |
*si += prime * next_mult_factor as usize; | |
*si += correction as usize; | |
*wi = wi.wrapping_add(next as usize); | |
} | |
mod wheel30 { | |
// automatically generated | |
#![allow(clippy::all)] | |
use crate::wheel::{WheelInit, Wheel, WheelElem}; | |
#[derive(Debug, Clone)] | |
pub(crate) struct Wheel30; | |
impl Wheel for Wheel30 { | |
#[inline(always)] | |
fn modulo(&self) -> usize { MODULO } | |
#[inline(always)] | |
fn size(&self) -> usize { SIZE } | |
#[inline(always)] | |
fn wheel(&self) -> &'static [WheelElem] { WHEEL } | |
#[inline(always)] | |
fn init(&self) -> &'static [WheelInit] { INIT } | |
#[inline(always)] | |
unsafe fn hardcoded_sieve(&self, | |
bytes: &mut [u8], si_: &mut usize, wi_: &mut usize, prime: usize) { | |
hardcoded_sieve(bytes, si_, wi_, prime) | |
} | |
} | |
pub(crate) const SIZE: usize = 8; | |
pub(crate) const MODULO: usize = 30; | |
pub(crate) const SMALL_BITS: usize = 2672; | |
pub(crate) const SMALL: &[u8; SMALL_BITS / 8] = &[ | |
0b11111110, 0b11011111, 0b11101111, 0b01111110, 0b10110110, 0b11011011, 0b00111101, 0b11111001, | |
0b11010101, 0b01001111, 0b00011110, 0b11110011, 0b11101010, 0b10100110, 0b11101101, 0b10011110, | |
0b11100110, 0b00001100, 0b11010011, 0b11010011, 0b00111011, 0b11011101, 0b01011001, 0b10100101, | |
0b01101010, 0b01100111, 0b10010010, 0b10111101, 0b01111000, 0b00011110, 0b10100110, 0b01010110, | |
0b01010110, 0b11100011, 0b10101101, 0b00101101, 0b11011110, 0b00101010, 0b01001100, 0b01010101, | |
0b11011001, 0b10100011, 0b11110000, 0b10011111, 0b00000011, 0b01010100, 0b10100001, 0b11111000, | |
0b00101110, 0b11111101, 0b01000100, 0b11101001, 0b01100110, 0b11110110, 0b00010011, 0b00111010, | |
0b10111000, 0b01001100, 0b00101011, 0b00111010, 0b01000101, 0b00010001, 0b10111111, 0b01010100, | |
0b10001100, 0b11000001, 0b01111010, 0b10110011, 0b11001000, 0b10111100, 0b10001100, 0b01001111, | |
0b00100001, 0b01011000, 0b01110001, 0b01110001, 0b10011011, 0b11000001, 0b00010111, 0b11101111, | |
0b01010100, 0b10010110, 0b00011010, 0b00001000, 0b11100101, 0b10000011, 0b10001100, 0b01000110, | |
0b01110010, 0b11111011, 0b10101110, 0b01100101, 0b10010010, 0b10001111, 0b01011000, 0b10000111, | |
0b11010010, 0b10010010, 0b11011000, 0b10000001, 0b01100101, 0b00100110, 0b11100011, 0b10100000, | |
0b00010001, 0b00111000, 0b11000111, 0b00100110, 0b00111100, 0b10000001, 0b11101011, 0b10011001, | |
0b10001101, 0b01010001, 0b10001000, 0b00111110, 0b00100100, 0b11110011, 0b00110011, 0b01001101, | |
0b01011010, 0b10001011, 0b00011100, 0b10100111, 0b00101010, 0b10110100, 0b01011000, 0b01001100, | |
0b01001110, 0b00100110, 0b11110110, 0b00011001, 0b10000010, 0b11011100, 0b10000011, 0b11000011, | |
0b00101100, 0b11110001, 0b00111000, 0b00000010, 0b10110101, 0b11001101, 0b11001101, 0b00000010, | |
0b10110010, 0b01001010, 0b10010100, 0b00001100, 0b01010111, 0b01001100, 0b01111010, 0b00110000, | |
0b01000011, 0b00001011, 0b11110001, 0b11001011, 0b01000100, 0b01101100, 0b00100100, 0b11111000, | |
0b00011001, 0b00000001, 0b10010101, 0b10101000, 0b01011100, 0b01110011, 0b11101010, 0b10001101, | |
0b00100100, 0b10010110, 0b00101011, 0b01010000, 0b10100110, 0b00100010, 0b00011110, 0b11000100, | |
0b11010001, 0b01001000, 0b00000110, 0b11010100, 0b00111010, 0b00101111, 0b01110100, 0b10011100, | |
0b00000111, 0b01101010, 0b00000101, 0b10001000, 0b10111111, 0b01101000, 0b00010101, 0b00101110, | |
0b01100000, 0b01010101, 0b11100011, 0b10110111, 0b01010001, 0b10011000, 0b00001000, 0b00010100, | |
0b10000110, 0b01011010, 0b10101010, 0b01000101, 0b01001101, 0b01001001, 0b01110000, 0b00100111, | |
0b11010010, 0b10010011, 0b11010101, 0b11001010, 0b10101011, 0b00000010, 0b10000011, 0b01100001, | |
0b00000101, 0b00100100, 0b11001110, 0b10000111, 0b00100010, 0b11000010, 0b10101001, 0b10101101, | |
0b00011000, 0b10001100, 0b01001101, 0b01111000, 0b11010001, 0b10001001, 0b00010110, 0b10110000, | |
0b01010111, 0b11000111, 0b01100010, 0b10100010, 0b11000000, 0b00110100, 0b00100100, 0b01010010, | |
0b10101110, 0b01011010, 0b01000000, 0b00110010, 0b10001101, 0b00100001, 0b00001000, 0b01000011, | |
0b00110100, 0b10110110, 0b11010010, 0b10110110, 0b11011001, 0b00011001, 0b11100001, 0b01100000, | |
0b01100111, 0b00011010, 0b00111001, 0b01100000, 0b11010000, 0b01000100, 0b01111010, 0b10010100, | |
0b10011010, 0b00001001, 0b10001000, 0b10000011, 0b10101000, 0b01110100, 0b01010101, 0b00010000, | |
0b00100111, 0b10100001, 0b01011101, 0b01101000, 0b00011110, 0b00100011, 0b11001000, 0b00110010, | |
0b11100000, 0b00011001, 0b00000011, 0b01000100, 0b01110011, 0b01001000, 0b10110001, 0b00111000, | |
0b11000011, 0b11100110, 0b00101010, 0b01010111, 0b01100001, 0b10011000, 0b10110101, 0b00011100, | |
0b00001010, 0b01101000, 0b11000101, 0b10000001, 0b10001111, 0b10101100, 0b00000010, 0b00101001, | |
0b00011010, 0b01000111, 0b11100011, 0b10010100, 0b00010001, 0b01001110, 0b01100100, 0b00101110, | |
0b00010100, 0b11001011, 0b00111101, 0b11011100, 0b00010100, 0b11000101, 0b00000110, 0b00010000, | |
0b11101001, 0b00101001, 0b10110001, 0b10000010, 0b11101001, 0b00110000, 0b01000111, 0b11100011, | |
0b00110100, 0b00011001, 0b11000011, 0b00100101, 0b00001010, 0b00110000, | |
]; | |
const INIT: &[WheelInit; 30] = &[ | |
WheelInit { next_mult_factor: 1, wheel_index: 0 }, // 0 | |
WheelInit { next_mult_factor: 0, wheel_index: 0 }, // 1 | |
WheelInit { next_mult_factor: 5, wheel_index: 1 }, // 2 | |
WheelInit { next_mult_factor: 4, wheel_index: 1 }, // 3 | |
WheelInit { next_mult_factor: 3, wheel_index: 1 }, // 4 | |
WheelInit { next_mult_factor: 2, wheel_index: 1 }, // 5 | |
WheelInit { next_mult_factor: 1, wheel_index: 1 }, // 6 | |
WheelInit { next_mult_factor: 0, wheel_index: 1 }, // 7 | |
WheelInit { next_mult_factor: 3, wheel_index: 2 }, // 8 | |
WheelInit { next_mult_factor: 2, wheel_index: 2 }, // 9 | |
WheelInit { next_mult_factor: 1, wheel_index: 2 }, // 10 | |
WheelInit { next_mult_factor: 0, wheel_index: 2 }, // 11 | |
WheelInit { next_mult_factor: 1, wheel_index: 3 }, // 12 | |
WheelInit { next_mult_factor: 0, wheel_index: 3 }, // 13 | |
WheelInit { next_mult_factor: 3, wheel_index: 4 }, // 14 | |
WheelInit { next_mult_factor: 2, wheel_index: 4 }, // 15 | |
WheelInit { next_mult_factor: 1, wheel_index: 4 }, // 16 | |
WheelInit { next_mult_factor: 0, wheel_index: 4 }, // 17 | |
WheelInit { next_mult_factor: 1, wheel_index: 5 }, // 18 | |
WheelInit { next_mult_factor: 0, wheel_index: 5 }, // 19 | |
WheelInit { next_mult_factor: 3, wheel_index: 6 }, // 20 | |
WheelInit { next_mult_factor: 2, wheel_index: 6 }, // 21 | |
WheelInit { next_mult_factor: 1, wheel_index: 6 }, // 22 | |
WheelInit { next_mult_factor: 0, wheel_index: 6 }, // 23 | |
WheelInit { next_mult_factor: 5, wheel_index: 7 }, // 24 | |
WheelInit { next_mult_factor: 4, wheel_index: 7 }, // 25 | |
WheelInit { next_mult_factor: 3, wheel_index: 7 }, // 26 | |
WheelInit { next_mult_factor: 2, wheel_index: 7 }, // 27 | |
WheelInit { next_mult_factor: 1, wheel_index: 7 }, // 28 | |
WheelInit { next_mult_factor: 0, wheel_index: 7 }, // 29 | |
]; | |
const WHEEL: &[WheelElem; 64] = &[ | |
// remainder 1 | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 1, next: -7 }, | |
// remainder 7 | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 1, next: -7 }, | |
// remainder 11 | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 1, next: -7 }, | |
// remainder 13 | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 1, next: -7 }, | |
// remainder 17 | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 1, next: -7 }, | |
// remainder 19 | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 1, next: -7 }, | |
// remainder 23 | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 1, next: -7 }, | |
// remainder 29 | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 1, next: -7 }, | |
]; | |
pub unsafe fn hardcoded_sieve(bytes: &mut [u8], si_: &mut usize, wi_: &mut usize, _prime: usize) { | |
let bytes = bytes; | |
let start = bytes.as_mut_ptr(); | |
let len = bytes.len() as isize; | |
let end = start.offset(len); | |
let si = *si_ as isize; | |
let p = start.offset(si); | |
let wi = *wi_; | |
*si_ = (p as usize).wrapping_sub(end as usize); | |
*wi_ = wi; | |
} | |
} | |
mod wheel210 { | |
// automatically generated | |
#![allow(clippy::all)] | |
use crate::wheel::{WheelInit, Wheel, WheelElem}; | |
#[derive(Debug, Clone)] | |
pub(crate) struct Wheel210; | |
impl Wheel for Wheel210 { | |
#[inline(always)] | |
fn modulo(&self) -> usize { MODULO } | |
#[inline(always)] | |
fn size(&self) -> usize { SIZE } | |
#[inline(always)] | |
fn wheel(&self) -> &'static [WheelElem] { WHEEL } | |
#[inline(always)] | |
fn init(&self) -> &'static [WheelInit] { INIT } | |
#[inline(always)] | |
unsafe fn hardcoded_sieve(&self, | |
bytes: &mut [u8], si_: &mut usize, wi_: &mut usize, prime: usize) { | |
hardcoded_sieve(bytes, si_, wi_, prime) | |
} | |
} | |
pub(crate) const SIZE: usize = 48; | |
pub(crate) const MODULO: usize = 210; | |
const INIT: &[WheelInit; 210] = &[ | |
WheelInit { next_mult_factor: 1, wheel_index: 0 }, // 0 | |
WheelInit { next_mult_factor: 0, wheel_index: 0 }, // 1 | |
WheelInit { next_mult_factor: 9, wheel_index: 1 }, // 2 | |
WheelInit { next_mult_factor: 8, wheel_index: 1 }, // 3 | |
WheelInit { next_mult_factor: 7, wheel_index: 1 }, // 4 | |
WheelInit { next_mult_factor: 6, wheel_index: 1 }, // 5 | |
WheelInit { next_mult_factor: 5, wheel_index: 1 }, // 6 | |
WheelInit { next_mult_factor: 4, wheel_index: 1 }, // 7 | |
WheelInit { next_mult_factor: 3, wheel_index: 1 }, // 8 | |
WheelInit { next_mult_factor: 2, wheel_index: 1 }, // 9 | |
WheelInit { next_mult_factor: 1, wheel_index: 1 }, // 10 | |
WheelInit { next_mult_factor: 0, wheel_index: 1 }, // 11 | |
WheelInit { next_mult_factor: 1, wheel_index: 2 }, // 12 | |
WheelInit { next_mult_factor: 0, wheel_index: 2 }, // 13 | |
WheelInit { next_mult_factor: 3, wheel_index: 3 }, // 14 | |
WheelInit { next_mult_factor: 2, wheel_index: 3 }, // 15 | |
WheelInit { next_mult_factor: 1, wheel_index: 3 }, // 16 | |
WheelInit { next_mult_factor: 0, wheel_index: 3 }, // 17 | |
WheelInit { next_mult_factor: 1, wheel_index: 4 }, // 18 | |
WheelInit { next_mult_factor: 0, wheel_index: 4 }, // 19 | |
WheelInit { next_mult_factor: 3, wheel_index: 5 }, // 20 | |
WheelInit { next_mult_factor: 2, wheel_index: 5 }, // 21 | |
WheelInit { next_mult_factor: 1, wheel_index: 5 }, // 22 | |
WheelInit { next_mult_factor: 0, wheel_index: 5 }, // 23 | |
WheelInit { next_mult_factor: 5, wheel_index: 6 }, // 24 | |
WheelInit { next_mult_factor: 4, wheel_index: 6 }, // 25 | |
WheelInit { next_mult_factor: 3, wheel_index: 6 }, // 26 | |
WheelInit { next_mult_factor: 2, wheel_index: 6 }, // 27 | |
WheelInit { next_mult_factor: 1, wheel_index: 6 }, // 28 | |
WheelInit { next_mult_factor: 0, wheel_index: 6 }, // 29 | |
WheelInit { next_mult_factor: 1, wheel_index: 7 }, // 30 | |
WheelInit { next_mult_factor: 0, wheel_index: 7 }, // 31 | |
WheelInit { next_mult_factor: 5, wheel_index: 8 }, // 32 | |
WheelInit { next_mult_factor: 4, wheel_index: 8 }, // 33 | |
WheelInit { next_mult_factor: 3, wheel_index: 8 }, // 34 | |
WheelInit { next_mult_factor: 2, wheel_index: 8 }, // 35 | |
WheelInit { next_mult_factor: 1, wheel_index: 8 }, // 36 | |
WheelInit { next_mult_factor: 0, wheel_index: 8 }, // 37 | |
WheelInit { next_mult_factor: 3, wheel_index: 9 }, // 38 | |
WheelInit { next_mult_factor: 2, wheel_index: 9 }, // 39 | |
WheelInit { next_mult_factor: 1, wheel_index: 9 }, // 40 | |
WheelInit { next_mult_factor: 0, wheel_index: 9 }, // 41 | |
WheelInit { next_mult_factor: 1, wheel_index: 10 }, // 42 | |
WheelInit { next_mult_factor: 0, wheel_index: 10 }, // 43 | |
WheelInit { next_mult_factor: 3, wheel_index: 11 }, // 44 | |
WheelInit { next_mult_factor: 2, wheel_index: 11 }, // 45 | |
WheelInit { next_mult_factor: 1, wheel_index: 11 }, // 46 | |
WheelInit { next_mult_factor: 0, wheel_index: 11 }, // 47 | |
WheelInit { next_mult_factor: 5, wheel_index: 12 }, // 48 | |
WheelInit { next_mult_factor: 4, wheel_index: 12 }, // 49 | |
WheelInit { next_mult_factor: 3, wheel_index: 12 }, // 50 | |
WheelInit { next_mult_factor: 2, wheel_index: 12 }, // 51 | |
WheelInit { next_mult_factor: 1, wheel_index: 12 }, // 52 | |
WheelInit { next_mult_factor: 0, wheel_index: 12 }, // 53 | |
WheelInit { next_mult_factor: 5, wheel_index: 13 }, // 54 | |
WheelInit { next_mult_factor: 4, wheel_index: 13 }, // 55 | |
WheelInit { next_mult_factor: 3, wheel_index: 13 }, // 56 | |
WheelInit { next_mult_factor: 2, wheel_index: 13 }, // 57 | |
WheelInit { next_mult_factor: 1, wheel_index: 13 }, // 58 | |
WheelInit { next_mult_factor: 0, wheel_index: 13 }, // 59 | |
WheelInit { next_mult_factor: 1, wheel_index: 14 }, // 60 | |
WheelInit { next_mult_factor: 0, wheel_index: 14 }, // 61 | |
WheelInit { next_mult_factor: 5, wheel_index: 15 }, // 62 | |
WheelInit { next_mult_factor: 4, wheel_index: 15 }, // 63 | |
WheelInit { next_mult_factor: 3, wheel_index: 15 }, // 64 | |
WheelInit { next_mult_factor: 2, wheel_index: 15 }, // 65 | |
WheelInit { next_mult_factor: 1, wheel_index: 15 }, // 66 | |
WheelInit { next_mult_factor: 0, wheel_index: 15 }, // 67 | |
WheelInit { next_mult_factor: 3, wheel_index: 16 }, // 68 | |
WheelInit { next_mult_factor: 2, wheel_index: 16 }, // 69 | |
WheelInit { next_mult_factor: 1, wheel_index: 16 }, // 70 | |
WheelInit { next_mult_factor: 0, wheel_index: 16 }, // 71 | |
WheelInit { next_mult_factor: 1, wheel_index: 17 }, // 72 | |
WheelInit { next_mult_factor: 0, wheel_index: 17 }, // 73 | |
WheelInit { next_mult_factor: 5, wheel_index: 18 }, // 74 | |
WheelInit { next_mult_factor: 4, wheel_index: 18 }, // 75 | |
WheelInit { next_mult_factor: 3, wheel_index: 18 }, // 76 | |
WheelInit { next_mult_factor: 2, wheel_index: 18 }, // 77 | |
WheelInit { next_mult_factor: 1, wheel_index: 18 }, // 78 | |
WheelInit { next_mult_factor: 0, wheel_index: 18 }, // 79 | |
WheelInit { next_mult_factor: 3, wheel_index: 19 }, // 80 | |
WheelInit { next_mult_factor: 2, wheel_index: 19 }, // 81 | |
WheelInit { next_mult_factor: 1, wheel_index: 19 }, // 82 | |
WheelInit { next_mult_factor: 0, wheel_index: 19 }, // 83 | |
WheelInit { next_mult_factor: 5, wheel_index: 20 }, // 84 | |
WheelInit { next_mult_factor: 4, wheel_index: 20 }, // 85 | |
WheelInit { next_mult_factor: 3, wheel_index: 20 }, // 86 | |
WheelInit { next_mult_factor: 2, wheel_index: 20 }, // 87 | |
WheelInit { next_mult_factor: 1, wheel_index: 20 }, // 88 | |
WheelInit { next_mult_factor: 0, wheel_index: 20 }, // 89 | |
WheelInit { next_mult_factor: 7, wheel_index: 21 }, // 90 | |
WheelInit { next_mult_factor: 6, wheel_index: 21 }, // 91 | |
WheelInit { next_mult_factor: 5, wheel_index: 21 }, // 92 | |
WheelInit { next_mult_factor: 4, wheel_index: 21 }, // 93 | |
WheelInit { next_mult_factor: 3, wheel_index: 21 }, // 94 | |
WheelInit { next_mult_factor: 2, wheel_index: 21 }, // 95 | |
WheelInit { next_mult_factor: 1, wheel_index: 21 }, // 96 | |
WheelInit { next_mult_factor: 0, wheel_index: 21 }, // 97 | |
WheelInit { next_mult_factor: 3, wheel_index: 22 }, // 98 | |
WheelInit { next_mult_factor: 2, wheel_index: 22 }, // 99 | |
WheelInit { next_mult_factor: 1, wheel_index: 22 }, // 100 | |
WheelInit { next_mult_factor: 0, wheel_index: 22 }, // 101 | |
WheelInit { next_mult_factor: 1, wheel_index: 23 }, // 102 | |
WheelInit { next_mult_factor: 0, wheel_index: 23 }, // 103 | |
WheelInit { next_mult_factor: 3, wheel_index: 24 }, // 104 | |
WheelInit { next_mult_factor: 2, wheel_index: 24 }, // 105 | |
WheelInit { next_mult_factor: 1, wheel_index: 24 }, // 106 | |
WheelInit { next_mult_factor: 0, wheel_index: 24 }, // 107 | |
WheelInit { next_mult_factor: 1, wheel_index: 25 }, // 108 | |
WheelInit { next_mult_factor: 0, wheel_index: 25 }, // 109 | |
WheelInit { next_mult_factor: 3, wheel_index: 26 }, // 110 | |
WheelInit { next_mult_factor: 2, wheel_index: 26 }, // 111 | |
WheelInit { next_mult_factor: 1, wheel_index: 26 }, // 112 | |
WheelInit { next_mult_factor: 0, wheel_index: 26 }, // 113 | |
WheelInit { next_mult_factor: 7, wheel_index: 27 }, // 114 | |
WheelInit { next_mult_factor: 6, wheel_index: 27 }, // 115 | |
WheelInit { next_mult_factor: 5, wheel_index: 27 }, // 116 | |
WheelInit { next_mult_factor: 4, wheel_index: 27 }, // 117 | |
WheelInit { next_mult_factor: 3, wheel_index: 27 }, // 118 | |
WheelInit { next_mult_factor: 2, wheel_index: 27 }, // 119 | |
WheelInit { next_mult_factor: 1, wheel_index: 27 }, // 120 | |
WheelInit { next_mult_factor: 0, wheel_index: 27 }, // 121 | |
WheelInit { next_mult_factor: 5, wheel_index: 28 }, // 122 | |
WheelInit { next_mult_factor: 4, wheel_index: 28 }, // 123 | |
WheelInit { next_mult_factor: 3, wheel_index: 28 }, // 124 | |
WheelInit { next_mult_factor: 2, wheel_index: 28 }, // 125 | |
WheelInit { next_mult_factor: 1, wheel_index: 28 }, // 126 | |
WheelInit { next_mult_factor: 0, wheel_index: 28 }, // 127 | |
WheelInit { next_mult_factor: 3, wheel_index: 29 }, // 128 | |
WheelInit { next_mult_factor: 2, wheel_index: 29 }, // 129 | |
WheelInit { next_mult_factor: 1, wheel_index: 29 }, // 130 | |
WheelInit { next_mult_factor: 0, wheel_index: 29 }, // 131 | |
WheelInit { next_mult_factor: 5, wheel_index: 30 }, // 132 | |
WheelInit { next_mult_factor: 4, wheel_index: 30 }, // 133 | |
WheelInit { next_mult_factor: 3, wheel_index: 30 }, // 134 | |
WheelInit { next_mult_factor: 2, wheel_index: 30 }, // 135 | |
WheelInit { next_mult_factor: 1, wheel_index: 30 }, // 136 | |
WheelInit { next_mult_factor: 0, wheel_index: 30 }, // 137 | |
WheelInit { next_mult_factor: 1, wheel_index: 31 }, // 138 | |
WheelInit { next_mult_factor: 0, wheel_index: 31 }, // 139 | |
WheelInit { next_mult_factor: 3, wheel_index: 32 }, // 140 | |
WheelInit { next_mult_factor: 2, wheel_index: 32 }, // 141 | |
WheelInit { next_mult_factor: 1, wheel_index: 32 }, // 142 | |
WheelInit { next_mult_factor: 0, wheel_index: 32 }, // 143 | |
WheelInit { next_mult_factor: 5, wheel_index: 33 }, // 144 | |
WheelInit { next_mult_factor: 4, wheel_index: 33 }, // 145 | |
WheelInit { next_mult_factor: 3, wheel_index: 33 }, // 146 | |
WheelInit { next_mult_factor: 2, wheel_index: 33 }, // 147 | |
WheelInit { next_mult_factor: 1, wheel_index: 33 }, // 148 | |
WheelInit { next_mult_factor: 0, wheel_index: 33 }, // 149 | |
WheelInit { next_mult_factor: 1, wheel_index: 34 }, // 150 | |
WheelInit { next_mult_factor: 0, wheel_index: 34 }, // 151 | |
WheelInit { next_mult_factor: 5, wheel_index: 35 }, // 152 | |
WheelInit { next_mult_factor: 4, wheel_index: 35 }, // 153 | |
WheelInit { next_mult_factor: 3, wheel_index: 35 }, // 154 | |
WheelInit { next_mult_factor: 2, wheel_index: 35 }, // 155 | |
WheelInit { next_mult_factor: 1, wheel_index: 35 }, // 156 | |
WheelInit { next_mult_factor: 0, wheel_index: 35 }, // 157 | |
WheelInit { next_mult_factor: 5, wheel_index: 36 }, // 158 | |
WheelInit { next_mult_factor: 4, wheel_index: 36 }, // 159 | |
WheelInit { next_mult_factor: 3, wheel_index: 36 }, // 160 | |
WheelInit { next_mult_factor: 2, wheel_index: 36 }, // 161 | |
WheelInit { next_mult_factor: 1, wheel_index: 36 }, // 162 | |
WheelInit { next_mult_factor: 0, wheel_index: 36 }, // 163 | |
WheelInit { next_mult_factor: 3, wheel_index: 37 }, // 164 | |
WheelInit { next_mult_factor: 2, wheel_index: 37 }, // 165 | |
WheelInit { next_mult_factor: 1, wheel_index: 37 }, // 166 | |
WheelInit { next_mult_factor: 0, wheel_index: 37 }, // 167 | |
WheelInit { next_mult_factor: 1, wheel_index: 38 }, // 168 | |
WheelInit { next_mult_factor: 0, wheel_index: 38 }, // 169 | |
WheelInit { next_mult_factor: 3, wheel_index: 39 }, // 170 | |
WheelInit { next_mult_factor: 2, wheel_index: 39 }, // 171 | |
WheelInit { next_mult_factor: 1, wheel_index: 39 }, // 172 | |
WheelInit { next_mult_factor: 0, wheel_index: 39 }, // 173 | |
WheelInit { next_mult_factor: 5, wheel_index: 40 }, // 174 | |
WheelInit { next_mult_factor: 4, wheel_index: 40 }, // 175 | |
WheelInit { next_mult_factor: 3, wheel_index: 40 }, // 176 | |
WheelInit { next_mult_factor: 2, wheel_index: 40 }, // 177 | |
WheelInit { next_mult_factor: 1, wheel_index: 40 }, // 178 | |
WheelInit { next_mult_factor: 0, wheel_index: 40 }, // 179 | |
WheelInit { next_mult_factor: 1, wheel_index: 41 }, // 180 | |
WheelInit { next_mult_factor: 0, wheel_index: 41 }, // 181 | |
WheelInit { next_mult_factor: 5, wheel_index: 42 }, // 182 | |
WheelInit { next_mult_factor: 4, wheel_index: 42 }, // 183 | |
WheelInit { next_mult_factor: 3, wheel_index: 42 }, // 184 | |
WheelInit { next_mult_factor: 2, wheel_index: 42 }, // 185 | |
WheelInit { next_mult_factor: 1, wheel_index: 42 }, // 186 | |
WheelInit { next_mult_factor: 0, wheel_index: 42 }, // 187 | |
WheelInit { next_mult_factor: 3, wheel_index: 43 }, // 188 | |
WheelInit { next_mult_factor: 2, wheel_index: 43 }, // 189 | |
WheelInit { next_mult_factor: 1, wheel_index: 43 }, // 190 | |
WheelInit { next_mult_factor: 0, wheel_index: 43 }, // 191 | |
WheelInit { next_mult_factor: 1, wheel_index: 44 }, // 192 | |
WheelInit { next_mult_factor: 0, wheel_index: 44 }, // 193 | |
WheelInit { next_mult_factor: 3, wheel_index: 45 }, // 194 | |
WheelInit { next_mult_factor: 2, wheel_index: 45 }, // 195 | |
WheelInit { next_mult_factor: 1, wheel_index: 45 }, // 196 | |
WheelInit { next_mult_factor: 0, wheel_index: 45 }, // 197 | |
WheelInit { next_mult_factor: 1, wheel_index: 46 }, // 198 | |
WheelInit { next_mult_factor: 0, wheel_index: 46 }, // 199 | |
WheelInit { next_mult_factor: 9, wheel_index: 47 }, // 200 | |
WheelInit { next_mult_factor: 8, wheel_index: 47 }, // 201 | |
WheelInit { next_mult_factor: 7, wheel_index: 47 }, // 202 | |
WheelInit { next_mult_factor: 6, wheel_index: 47 }, // 203 | |
WheelInit { next_mult_factor: 5, wheel_index: 47 }, // 204 | |
WheelInit { next_mult_factor: 4, wheel_index: 47 }, // 205 | |
WheelInit { next_mult_factor: 3, wheel_index: 47 }, // 206 | |
WheelInit { next_mult_factor: 2, wheel_index: 47 }, // 207 | |
WheelInit { next_mult_factor: 1, wheel_index: 47 }, // 208 | |
WheelInit { next_mult_factor: 0, wheel_index: 47 }, // 209 | |
]; | |
const WHEEL: &[WheelElem; 384] = &[ | |
// remainder 1 | |
WheelElem { unset_bit: 254, next_mult_factor: 10, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 8, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 8, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 10, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 1, next: -47 }, | |
// remainder 7 | |
WheelElem { unset_bit: 253, next_mult_factor: 10, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 8, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 8, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 10, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 1, next: -47 }, | |
// remainder 11 | |
WheelElem { unset_bit: 251, next_mult_factor: 10, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 8, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 8, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 0, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 10, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 1, next: -47 }, | |
// remainder 13 | |
WheelElem { unset_bit: 247, next_mult_factor: 10, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 8, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 8, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 10, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 2, correction: 1, next: -47 }, | |
// remainder 17 | |
WheelElem { unset_bit: 239, next_mult_factor: 10, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 8, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 8, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 10, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 1, next: -47 }, | |
// remainder 19 | |
WheelElem { unset_bit: 223, next_mult_factor: 10, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 8, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 8, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 4, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 10, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 2, correction: 1, next: -47 }, | |
// remainder 23 | |
WheelElem { unset_bit: 191, next_mult_factor: 10, correction: 8, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 8, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 8, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 6, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 5, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 3, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 10, correction: 8, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 2, correction: 1, next: -47 }, | |
// remainder 29 | |
WheelElem { unset_bit: 127, next_mult_factor: 10, correction: 10, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 8, correction: 7, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 8, correction: 7, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 253, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 1, next: 1 }, | |
WheelElem { unset_bit: 127, next_mult_factor: 6, correction: 6, next: 1 }, | |
WheelElem { unset_bit: 191, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 223, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 239, next_mult_factor: 4, correction: 4, next: 1 }, | |
WheelElem { unset_bit: 247, next_mult_factor: 2, correction: 2, next: 1 }, | |
WheelElem { unset_bit: 251, next_mult_factor: 10, correction: 10, next: 1 }, | |
WheelElem { unset_bit: 254, next_mult_factor: 2, correction: 1, next: -47 }, | |
]; | |
pub(crate) unsafe fn hardcoded_sieve(bytes: &mut [u8], si_: &mut usize, wi_: &mut usize, _prime: usize) { | |
let bytes = bytes; | |
let start = bytes.as_mut_ptr(); | |
let len = bytes.len() as isize; | |
let end = start.offset(len); | |
let si = *si_ as isize; | |
let p = start.offset(si); | |
let wi = *wi_; | |
*si_ = (p as usize).wrapping_sub(end as usize); | |
*wi_ = wi; | |
} | |
} | |
} | |
mod hamming { | |
mod weight_ { | |
fn naive(x: &[u8]) -> u64 { | |
x.iter().fold(0, |a, b| a + b.count_ones() as u64) | |
} | |
pub(crate) fn weight(x: &[u8]) -> u64 { | |
const M1: u64 = 0x5555555555555555; | |
const M2: u64 = 0x3333333333333333; | |
const M4: u64 = 0x0F0F0F0F0F0F0F0F; | |
const M8: u64 = 0x00FF00FF00FF00FF; | |
type T30 = [u64; 30]; | |
let (head, thirty, tail) = unsafe { | |
super::util::align_to::<_, T30>(x) | |
}; | |
let mut count = naive(head) + naive(tail); | |
for array in thirty { | |
let mut acc = 0; | |
for j_ in 0..10 { | |
let j = j_ * 3; | |
let mut count1 = array[j]; | |
let mut count2 = array[j + 1]; | |
let mut half1 = array[j + 2]; | |
let mut half2 = half1; | |
half1 &= M1; | |
half2 = (half2 >> 1) & M1; | |
count1 -= (count1 >> 1) & M1; | |
count2 -= (count2 >> 1) & M1; | |
count1 += half1; | |
count2 += half2; | |
count1 = (count1 & M2) + ((count1 >> 2) & M2); | |
count1 += (count2 & M2) + ((count2 >> 2) & M2); | |
acc += (count1 & M4) + ((count1 >> 4) & M4); | |
} | |
acc = (acc & M8) + ((acc >> 8) & M8); | |
acc = acc + (acc >> 16); | |
acc = acc + (acc >> 32); | |
count += acc & 0xFFFF; | |
} | |
count | |
} | |
} | |
pub(crate) use self::weight_::weight; | |
mod util { | |
use std::{slice, mem}; | |
#[inline(never)] // critical for autovectorization in `weight`. | |
pub(crate) unsafe fn align_to<T, U>(x: &[T]) -> (&[T], &[U], &[T]) { | |
let orig_size = mem::size_of::<T>(); | |
let size = mem::size_of::<U>(); | |
debug_assert!(orig_size < size && size % orig_size == 0); | |
let size_ratio = size / orig_size; | |
let alignment = mem::align_of::<U>(); | |
let ptr = x.as_ptr() as usize; | |
// round up to the nearest multiple | |
let aligned = (ptr + alignment - 1) / alignment * alignment; | |
let byte_distance = aligned - ptr; | |
// can't fit a single U in | |
if mem::size_of_val(x) < size + byte_distance { | |
return (x, &[], &[]) | |
} | |
let (head, middle) = x.split_at(byte_distance / orig_size); | |
assert!(middle.as_ptr() as usize % alignment == 0); | |
let cast_middle = | |
slice::from_raw_parts(middle.as_ptr() as *const U, | |
middle.len() / size_ratio); | |
let tail = &middle[cast_middle.len() * size_ratio..]; | |
(head, cast_middle, tail) | |
} | |
} | |
} | |
// extern crate primal_bit; | |
mod primal_bit { | |
#![deny(unsafe_code)] | |
pub(crate) use primal_bit::inner::BitVec; | |
pub(crate) use primal_bit::iter::{IntoOnes, Ones}; | |
const BITS: usize = 8; | |
impl BitVec { | |
#[inline] | |
pub(crate) fn count_ones(&self) -> usize { | |
super::hamming::weight(self.as_bytes()) as usize | |
} | |
} | |
mod inner { | |
#![allow(unsafe_code)] | |
use primal_bit::BITS; | |
pub(crate) struct BitVec { | |
storage: Vec<u8>, | |
nbits: usize, | |
} | |
impl BitVec { | |
#[inline] | |
pub(crate) fn new() -> BitVec { | |
BitVec { | |
storage: Vec::new(), | |
nbits: 0, | |
} | |
} | |
#[inline] | |
pub(crate) fn from_bytes(data: Vec<u8>, nbits: usize) -> BitVec { | |
let nbytes = nbits / BITS + usize::from(nbits % BITS != 0); | |
assert_eq!(nbytes, data.len()); | |
let mut ret = BitVec { | |
storage: data, | |
nbits, | |
}; | |
ret.fix_last_block(); | |
ret | |
} | |
pub(crate) fn from_elem(nbits: usize, bit: bool) -> BitVec { | |
let nbytes = nbits / BITS + usize::from(nbits % BITS != 0); | |
let out_vec = vec![if bit { !0 } else { 0 }; nbytes]; | |
let mut bit_vec = BitVec { | |
storage: out_vec, | |
nbits, | |
}; | |
if bit { | |
bit_vec.fix_last_block(); | |
} | |
bit_vec | |
} | |
pub(crate) fn fix_last_block(&mut self) { | |
let extra_bits = self.nbits % BITS; | |
if extra_bits > 0 { | |
let mask = (1 << extra_bits) - 1; | |
let last = self.storage.last_mut().unwrap(); | |
*last &= mask; | |
} | |
} | |
#[inline] | |
pub(crate) fn as_bytes_mut(&mut self) -> &mut [u8] { | |
&mut self.storage | |
} | |
#[inline] | |
pub(crate) fn as_bytes(&self) -> &[u8] { | |
&self.storage | |
} | |
#[inline] | |
pub(crate) fn into_bytes(self) -> Vec<u8> { | |
self.storage | |
} | |
#[inline] | |
pub(crate) fn len(&self) -> usize { | |
self.nbits | |
} | |
#[inline] | |
pub(crate) fn get(&self, i: usize) -> Option<bool> { | |
if i >= self.nbits { | |
return None; | |
} | |
let w = i / BITS; | |
let b = i % BITS; | |
let mask = 1 << b; | |
unsafe { | |
let block = *self.storage.get_unchecked(w); | |
Some(block & mask != 0) | |
} | |
} | |
#[inline] | |
pub(crate) fn set(&mut self, i: usize, x: bool) { | |
assert!(i < self.nbits, "index out of bounds"); | |
let w = i / BITS; | |
let b = i % BITS; | |
let mask = 1 << b; | |
let bit = u8::from(x) << b; | |
unsafe { | |
let ptr = self.storage.get_unchecked_mut(w); | |
*ptr = (*ptr & !mask) | bit; | |
} | |
} | |
} | |
impl Clone for BitVec { | |
#[inline] | |
fn clone(&self) -> BitVec { | |
BitVec { | |
storage: self.storage.clone(), | |
nbits: self.nbits, | |
} | |
} | |
#[inline] | |
fn clone_from(&mut self, source: &BitVec) { | |
self.nbits = 0; // safe default while storage is modified | |
self.storage.clone_from(&source.storage); | |
self.nbits = source.nbits; | |
} | |
} | |
} | |
mod iter { | |
use std::iter; | |
use std::mem; | |
use std::ops::Range; | |
use std::slice; | |
use std::vec; | |
use primal_bit::BitVec; | |
use primal_bit::BITS; | |
impl BitVec { | |
#[inline] | |
pub(crate) fn iter(&self) -> Iter<'_> { | |
Iter { | |
bit_vec: self, | |
idx: 0..self.len(), | |
} | |
} | |
} | |
#[derive(Clone)] | |
pub(crate) struct Iter<'a> { | |
bit_vec: &'a BitVec, | |
idx: Range<usize>, | |
} | |
impl<'a> Iterator for Iter<'a> { | |
type Item = bool; | |
#[inline] | |
fn next(&mut self) -> Option<bool> { | |
self.bit_vec.get(self.idx.next()?) | |
} | |
#[inline] | |
fn size_hint(&self) -> (usize, Option<usize>) { | |
self.idx.size_hint() | |
} | |
} | |
impl<'a> DoubleEndedIterator for Iter<'a> { | |
#[inline] | |
fn next_back(&mut self) -> Option<bool> { | |
self.bit_vec.get(self.idx.next_back()?) | |
} | |
} | |
impl<'a> ExactSizeIterator for Iter<'a> {} | |
impl<'a> IntoIterator for &'a BitVec { | |
type Item = bool; | |
type IntoIter = Iter<'a>; | |
#[inline] | |
fn into_iter(self) -> Iter<'a> { | |
self.iter() | |
} | |
} | |
impl BitVec { | |
#[inline] | |
pub(crate) fn ones_from(&self, from: usize) -> Ones<'_> { | |
let (byte, bit) = (from / BITS, from % BITS); | |
let mask = (!0) << bit; | |
let mut iter = self.as_bytes()[byte..].iter().copied(); | |
let (current, _) = usize_from_bytes(&mut iter); | |
NewInnerOnes { | |
base: byte * BITS, | |
current: current & mask, | |
iter, | |
} | |
} | |
#[inline] | |
pub(crate) fn into_ones(self) -> IntoOnes { | |
let mut iter = self.into_bytes().into_iter(); | |
let (current, _) = usize_from_bytes(&mut iter); | |
NewInnerOnes { | |
base: 0, | |
current, | |
iter, | |
} | |
} | |
} | |
pub(crate) type Ones<'a> = NewInnerOnes<iter::Copied<slice::Iter<'a, u8>>>; | |
pub(crate) type IntoOnes = NewInnerOnes<vec::IntoIter<u8>>; | |
#[derive(Clone)] | |
pub(crate) struct NewInnerOnes<I> { | |
base: usize, | |
current: usize, | |
iter: I, | |
} | |
impl<I: Iterator<Item = u8>> Iterator for NewInnerOnes<I> { | |
type Item = usize; | |
#[inline] | |
fn next(&mut self) -> Option<usize> { | |
let mut c = self.current; | |
while c == 0 { | |
let (next, done) = usize_from_bytes(&mut self.iter); | |
if done { | |
return None; | |
} | |
self.base += BITS * mem::size_of::<usize>(); | |
c = next; | |
} | |
let lsb = c.trailing_zeros(); | |
self.current = c & (c - 1); | |
Some(self.base + lsb as usize) | |
} | |
} | |
#[inline] | |
fn usize_from_bytes(iter: &mut impl Iterator<Item = u8>) -> (usize, bool) { | |
let mut n = 0; | |
for i in 0..mem::size_of::<usize>() { | |
match iter.next() { | |
Some(b) => n |= usize::from(b) << (i * BITS), | |
None => return (n, i == 0), | |
} | |
} | |
(n, false) | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment