Proposal for v2 API

[akhilles]

Addresses a couple of different issues (#37, #46, #45, #40):

• code duplication under the crc16, crc32, and crc64 modules
• dependency on build scripts/macros (multiple Digests can share a crc table)

// Crc

pub trait Width: From<u8> + Into<u64> + Copy + 'static {}
impl Width for u16 {}
impl Width for u32 {}
impl Width for u64 {}

pub struct Algorithm<W: Width> {
    pub poly: W,
    pub init: W,
    pub xorout: W,
    pub check: W,
    pub residue: W,
    pub refin: bool,
    pub refout: bool,
}

pub const CRC_16_IBM_3740: Algorithm<u16> = Algorithm {
    poly: 0x1021, init: 0xffff,
    xorout: 0x0000, check: 0x29b1, residue: 0x0000,
    refin: false, refout: false,
};
pub const CRC_16_AUTOSAR: Algorithm<u16> = CRC_16_IBM_3740;

pub struct Crc<W: Width> {
    algorithm: &'static Algorithm<W>,
    table: [W; 256],
}

impl<W: Width> Crc<W> {
    fn new(algorithm: &'static Algorithm<W>) -> Self {
        let table = make_table(algorithm.poly, algorithm.init);
        Crc { algorithm, table }
    }
}

// Digest

pub struct Digest<'a, W: Width> {
    crc: &'a Crc<W>,
    value: W,
}

impl<'a, W: Width> Digest<'a, W> {
    fn new(crc: &'a Crc<W>) -> Self {
        let value = crc.algorithm.init;
        Digest { crc, value }
    }
}

impl<'a, W: Width> core::hash::Hasher for Digest<'a, W> {
    fn write(&mut self, bytes: &[u8]) {}
    fn finish(&self) -> u64 {
        unimplemented!()
    }
}

fn make_table<W: Width>(poly: W, init: W) -> [W; 256] {
    unimplemented!()
}

This represents a significant change in the API and internal structure of this library, but I believer the advantages are clear. Fully implementing these changes will take quite a bit of work. So, I wanted to get feedback before drafting a PR.

[akhilles]

cc @mrhooray @zachmse

[mrhooray]

Consider implementing std::hash::Hasher? Related: #8

[akhilles]

Updated to implement core::hash::Hasher to preserve no_std

[chrysn]

Can make_table and thus new be const, so that a Crc<_> can be either created static const (with its table and constants in ROM on microprocessors) in addition to being constructable (preferably once, but as I read the API it's up to the user to make this happen only once) in RAM at runtime?

I'd be happy with this API, especially if the above can be arranged.

I figure that tables for the common algorithms would just all be declared in the module, and rely on dead code elimination to not be linked in if not needed?

It might make sense to seal the Write trait; that'd allow later addition of requirements. (I'm not sure even the current requirements are sufficient.)

If code and RAM size matter a lot and hashing is rare, generalizing Crc into a trait that's implemented by CrcWithTable and CrcWithoutTable may make sense (where the WithoutTable generates the entries at runtime, saving 2k of table space minus the size of the entry generation).

[akhilles]

Having make_table be const is the ideal solution but it's quite difficult due to the current limitations of constant evaluation. There can't be loops, heap allocation, or mutable state in const fn. However, there is active development in opening up constant evaluation to support these things.

I figure that tables for the common algorithms would just all be declared in the module, and rely on dead code elimination to not be linked in if not needed?

I think that makes the most sense.

If code and RAM size matter a lot and hashing is rare, generalizing Crc into a trait that's implemented by CrcWithTable and CrcWithoutTable may make sense (where the WithoutTable generates the entries at runtime, saving 2k of table space minus the size of the entry generation).

Wouldn't having Crc::new be const address this use case? If Crc::new is used to declare a module-level const, then the table is generated at compile time. If Crc::new is used in function scope, then the table is generated at runtime.

[chrysn]

Wouldn't having Crc::new be const address this use case?

I was rather thinking about not calculating the table at all (when RAM is a premium as well) and calculating the table's entries for each access. My point was not about implementing this now, but leaving such possibilities open by something like this:

pub trait Crc<W: Width> {
    fn get_init() -> W;
    fn get_entry(u8) -> W;
}

pub struct TableCrc<W: Width> {
    algorithm: &'static Algorithm<W>,
    table: [W; 256],
}

impl<W: Width> Crc<W> for TableCrc<W> {
    fn get_init() -> W {
        self.algorithm.init
    }

    fn get_entry(i: u8) -> W {
        self.table[i]
    }
}

pub struct Digest<'a, W: Width, C: Crc<W>> {
    crc: &'a C,
    value: W,
}

impl<'a, W: Width, C: Crc<W>> Digest<'a, W, C> {
    fn new(crc: &'a impl Crc<W>) -> Self {
        Digest { crc, crc.get_init() }
    }
}

That's a bit hypothetical, though, so if the above would make things overly complicated, and at the same time doesn't allow using a CRC accelerator like the one in STM32s with the same interface (which would require going through a trait not at the Crc but at the Digest level). It's probably be better to go for a v2 as it is now rather than to fall into the second version pitfall here.

[rlabrecque]

Just throwing my two cents in but I would love if the API functioned roughly the same as https://github.com/RustCrypto/hashes

[johnnybravo-xyz]

I was going through documentation which shows to use 2.0 as the version but the last release is still on 1.8.1, is there a plan to release these v2 changes?

[mrhooray]

With #55 merged, do we want to close out this one / track additional improvements in a separate issue?

[mrhooray]

Published 2.0.0 after rc period