Repository: google/OpenSK
File: libraries/persistent_store/fuzz/src/lib.rs (Rust)

Code before:
    assert_eq!(num_bits(2), 2);
    assert_eq!(num_bits(3), 2);
    assert_eq!(num_bits(4), 3);
    assert_eq!(num_bits(7), 3);
    assert_eq!(num_bits(8), 4);
    assert_eq!(num_bits(15), 4);
    assert_eq!(num_bits(16), 5);
    assert_eq!(
        num_bits(usize::max_value()),
        8 * std::mem::size_of::<usize>()
    );
}

#[test]
fn read_bit_ok() {
    let mut entropy = Entropy::new(&[0b10110010]);
    assert!(!entropy.read_bit());
    assert!(entropy.read_bit());
    assert!(!entropy.read_bit());
    assert!(!entropy.read_bit());
    assert!(entropy.read_bit());
    assert!(entropy.read_bit());
    assert!(!entropy.read_bit());
    assert!(entropy.read_bit());
}

#[test]
fn read_bits_ok() {
    let mut entropy = Entropy::new(&[0x83, 0x92]);
    assert_eq!(entropy.read_bits(4), 0x3);
    assert_eq!(entropy.read_bits(8), 0x28);
    assert_eq!(entropy.read_bits(2), 0b01);
    assert_eq!(entropy.read_bits(2), 0b10);
}

#[test]
fn read_range_ok() {
    let mut entropy = Entropy::new(&[0b00101011]);
    assert_eq!(entropy.read_range(0, 7), 0b011);
    assert_eq!(entropy.read_range(1, 8), 1 + 0b101);
    assert_eq!(entropy.read_range(4, 6), 4 + 0b00);
    let mut entropy = Entropy::new(&[0b00101011]);
    assert_eq!(entropy.read_range(0, 8), 0b1011 % 9);
    assert_eq!(entropy.read_range(3, 15), 3 + 0b0010);
    let mut entropy = Entropy::new(&[0x12, 0x34, 0x56, 0x78]);
    assert_eq!(entropy.read_range(0, usize::max_value() - 1), 0x78563412);
}


Review comment (suggestion):
This is not a uniform distribution (given the initial bits are uniform i.i.d.). People would usually assume a uniform distribution here. Example:
`min = 0`
`max = 2`
`count = 3`
`read_bits(2)` is uniform in `[0;3]`
`% count` gives the distribution `0: 50%, 1: 25%, 2: 25%`

You either document that you don't care about uniform distributions or improve the algorithm. It shouldn't be too bad for bigger ranges, but there will always be a bias towards smaller numbers.

Code after:
        self.read_bits(8) as u8
    }

    /// Reads a slice.
    fn read_slice(&mut self, length: usize) -> Vec<u8> {
        let mut result = Vec::with_capacity(length);
        for _ in 0..length {
            result.push(self.read_byte());
        }
        result
    }

    /// Reads a number between `min` and `max` (inclusive bounds).
    ///
    /// The distribution is uniform if the range width is a power of two. Otherwise, the minimum
    /// amount of entropy is used (the next power of two) and the distribution is the closest to
    /// uniform for that entropy.
    ///
    /// # Preconditions
    ///
    /// - The bounds should be correctly ordered: `min <= max`.
    /// - The upper-bound should not be too large: `max < usize::max_value()`.
    fn read_range(&mut self, min: usize, max: usize) -> usize {
        assert!(min <= max && max < usize::max_value());
        let count = max - min + 1;
        let delta = self.read_bits(num_bits(count - 1)) % count;
        min + delta
    }
}

/// Returns the number of bits necessary to represent a number.
fn num_bits(x: usize) -> usize {
    8 * std::mem::size_of::<usize>() - x.leading_zeros() as usize
}

#[test]
fn num_bits_ok() {
    assert_eq!(num_bits(0), 0);
    assert_eq!(num_bits(1), 1);
    assert_eq!(num_bits(2), 2);
    assert_eq!(num_bits(3), 2);
    assert_eq!(num_bits(4), 3);
    assert_eq!(num_bits(7), 3);
    assert_eq!(num_bits(8), 4);
    assert_eq!(num_bits(15), 4);
    assert_eq!(num_bits(16), 5);
    assert_eq!(
        num_bits(usize::max_value()),
        8 * std::mem::size_of::<usize>()
    );
}