Skip to content

Instantly share code, notes, and snippets.

@pnkfelix

pnkfelix/main.rs

Last active February 21, 2022 16:10
Show Gist options
  • Save pnkfelix/f45098bc69482dac920dcf384049b849 to your computer and use it in GitHub Desktop.
Save pnkfelix/f45098bc69482dac920dcf384049b849 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
main.rs
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