Block generation & buffering API design

[dhardy]

Status quo (derived from last release): we have

pub trait BlockRngCore {
    type Item;

    type Results: AsRef<[Self::Item]> + AsMut<[Self::Item]> + Default;

    fn generate(&mut self, results: &mut Self::Results);
}

pub trait CryptoBlockRng: BlockRngCore {}

#[derive(Clone)]
pub struct BlockRng<R: BlockRngCore> {
    results: R::Results,
    index: usize,
    pub core: R,
}

impl<R: BlockRngCore<Item = u32>> RngCore for BlockRng<R> {}

#[derive(Clone)]
pub struct BlockRng64<R: BlockRngCore + ?Sized> {
    results: R::Results,
    index: usize,
    half_used: bool, // true if only half of the previous result is used
    pub core: R,
}

impl<R: BlockRngCore<Item = u64>> RngCore for BlockRng64<R> {}

Issue: the results buffer is internal, which makes it hard to do things like implement serde support externally. #30 allows this; the result is somewhat ugly but acceptable in my opinion.

Issue: BlockRng64 shouldn't need to be separate from BlockRng (if we ignore the half_used optimisation), however Rust does not (yet) support deconflicting implementations over associated types (i.e. the two impls above are considered to conflict if both apply to BlockRng).

Issue: BlockRngCore::Results supports variable-sized buffer types like Vec<u32> which it really shouldn't.

Issue: BlockRngCore::Results requires a Default bound (for construction), but [u32; 64] doesn't (yet) support this. Both chacha20 and rand_chacha crates use a custom Array type to work around this. Rust should fix this in the future: rust-lang/rust#61415.

Issue: this is quite a lot of code for what is supposed to just be an RNG-interface crate.

[dhardy]

Attempted design:

pub trait BlockRngCore {
    type Item: Word;

    const LEN: usize;

    fn generate(&mut self, results: &mut [Self::Item; Self::LEN]);
}

Problem: Rust doesn't support generic_const_exprs on stable yet. (I don't think the design even works on unstable Rust: it complains that the results: [R::Item; R::LEN] field is an unconstrained generic constant.)

Every design which attempts to precisely specify the buffer type hits this problem: it requires that support for generic const exprs.

We also can't constrain the buffer type to Array<u32> or Array<W, _> since there is no Array trait, hence why the status-quo uses the much looser bound AsMut<[W]>.

[dhardy]

Possible design from #26:

pub trait Generator {
    type Result;

    fn generate(&mut self, result: &mut Self::Result);
}

This is a variation on the status quo which drops bounds on the Result type, moving bounds to implementations.

This succeeds in doing something the above attempted design does not: precisely specifying the buffer type. This fixes both issues pertaining to BlockRngCore::Results above.

[dhardy]

Possible minor simplification: remove BlockRng64. Of our RNGs, only Isaac64Rng uses it, and this RNG is rather unimportant.

It isn't quite so simple to move the BlockRng64 code to the rand_isaac crate since it uses fill_via_chunks which is internal (though that and its Observable trait could be copied too).

[dhardy]

Attempted design from #24: replace block module with helper fns:

pub fn new_buffer<W: Word, const N: usize>() -> [W; N] { /* .. */ }

pub fn next_word_via_gen_block<W: Word, const N: usize>(
    buf: &mut [W; N],
    mut generate_block: impl FnMut(&mut [W; N]),
) -> W { /* .. */ }

pub fn next_u64_via_gen_block<const N: usize>(
    buf: &mut [u32; N],
    mut generate_block: impl FnMut(&mut [u32; N]),
) -> u64 { /* .. */ }

pub fn fill_bytes_via_gen_block<W: Word, const N: usize>(
    mut dst: &mut [u8],
    buf: &mut [W; N],
    mut generate_block: impl FnMut(&mut [W; N]),
) { /* .. */ }

Issue: lack of type-safety for the buffer.

Issue: performance issues for u32 / u64 generation with rand::rng() due to ReseedingRng lacking direct access to a block-generation fn.

[newpavlov]

I think the main question is whether we want a trait for block generation or not. Its primary use is ReseedingRng and I am not sure it's a sufficient motivation. I have a rough idea of how we can implement it efficiently (albeit slightly ugly), but unfortunately I did not have time to work on it during previous week.

[dhardy]

The motivation is to avoid a significant penalty to rand::rng() performance (reportedly 20-50% in rust-random/rand#1686). I believe we need some type of block generation trait to avoid that.

#24 was interesting, but personally I did not like the lack of type safety around the buffer. I briefly considered adding a Buffer struct, but the result is mostly the same as BlockRng.

I'm reasonably positive about #26 as a starting point. It can be worked further (e.g. integrating the index into the buffer, supporting serialization) but I'd prefer not to push that into the same PR.

[dhardy]

I also think it's acceptable to just drop BlockRng64 (and u64 support). It would be nice if we could simply move it into rand_isaac (the only user), but the current code uses fill_via_chunks which is internal to rand_core.