1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

use primal_bit::BitVec;
use std::{cmp, ptr};

use wheel;
use super::{StreamingSieve};

const MINIMUM_PRESIEVE: usize = 2 * 3 * 5;
const PRESIEVE_PRIMES: &'static [usize] = &[7, 11, 13, 17, 19, 23, 29];

#[derive(Debug)]
pub struct Presieve {
    sieve: BitVec,
    presieve_prod: usize,
    presieve_idx: usize,
}
impl Presieve {
    #[inline(never)]
    pub 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: sieve,
                presieve_prod: prod,
                presieve_idx: idx,
            }
        }
    }
    pub fn smallest_unincluded_prime(&self) -> usize {
        PRESIEVE_PRIMES[self.presieve_idx]
    }
    pub 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)
            }
        }
    }
    pub 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());
            unsafe {
                ptr::copy(src.as_ptr(), dst.as_mut_ptr(), l);
            }
            l
        }
    }
}

#[cfg(all(test, feature = "unstable"))]
mod benches {
    use test::Bencher;
    use super::Presieve;
    fn run_presieve(b: &mut Bencher, n: usize) {
        b.iter(|| Presieve::new(::wheel::bits_for(n)))
    }
    #[bench]
    fn presieve_small(b: &mut Bencher) {
        run_presieve(b, 100)
    }
    #[bench]
    fn presieve_medium(b: &mut Bencher) {
        run_presieve(b, 10_000)
    }
    #[bench]
    fn presieve_large(b: &mut Bencher) {
        run_presieve(b, 100_000)
    }
    #[bench]
    fn presieve_larger(b: &mut Bencher) {
        run_presieve(b, 1_000_000)
    }
    #[bench]
    fn presieve_huge(b: &mut Bencher) {
        run_presieve(b, 10_000_000)
    }
}