Robbepop commented 5 years ago

There is only one thing currently not working which is f64::log2 not being found by the compiler in no_std mode which is a rather strange bug.

The error looks like:

error[E0599]: no method named `log2` found for type `f64` in the current scope
   --> src/apint/serialization.rs:269:45
    |
269 |         let bits = f64::from(radix.to_u8()).log2() * v.len() as f64;
    |                                             ^^^^ method not found in `f64`

Needs further investigation.

edit:

Turns out the above error is a result of https://github.com/rust-lang/rfcs/issues/2505. So we have several options to continue:

Disapprove and discontinue any use of those std-only functions, remove all old code that depends on it which is fortunately just this one instance as far as it seems.
Depend on libm to be able to continue depending on these functions. Note that libm does not provide the best possible performance.

coveralls commented 5 years ago

Coverage decreased (-0.2%) to 75.948% when pulling 987843ca56551ceb42bcdedd5d1643089ed1a0be on make-no_std-compatible into 6e3a052c8e95915111068ee45e54b41d10d0f6c1 on master.

codecov-io commented 5 years ago

Codecov Report

Merging #50 into master will decrease coverage by 0.15%. The diff coverage is 96.66%.

@@            Coverage Diff             @@
##           master      #50      +/-   ##
==========================================
- Coverage   76.03%   75.88%   -0.16%     
==========================================
  Files          22       22              
  Lines        5345     5340       -5     
==========================================
- Hits         4064     4052      -12     
- Misses       1281     1288       +7

Impacted Files	Coverage Δ
src/lib.rs	`0% <ø> (ø)`	:arrow_up:
src/digit_seq.rs	`77.77% <ø> (ø)`	:arrow_up:
src/errors.rs	`34.41% <ø> (ø)`	:arrow_up:
src/apint/arithmetic.rs	`91.35% <ø> (-0.1%)`	:arrow_down:
src/digit.rs	`93.05% <ø> (ø)`	:arrow_up:
src/int.rs	`0% <ø> (ø)`	:arrow_up:
src/uint.rs	`0% <ø> (ø)`	:arrow_up:
src/apint/utils.rs	`79.36% <ø> (-0.53%)`	:arrow_down:
src/apint/relational.rs	`26.36% <ø> (ø)`	:arrow_up:
src/apint/casting.rs	`76.39% <ø> (ø)`	:arrow_up:
... and 10 more

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 6e3a052...987843c. Read the comment docs.

AaronKutch commented 5 years ago

I am pretty sure it is faster and safer to do something like let bits= (1usize << (8 - radix.leading_zeros())).checked_mul(v.len()).unwrap(). Instead of using floating point. I just looked at my stashed serialization code, and I think I can modify it to work with master.

Robbepop commented 5 years ago

Please file a PR to improve upon this PR. But whenever you make performance-PRs please file an associated benchmark to prove that we are not pulling in premature optimizations or even general pessimizations.

AaronKutch commented 5 years ago

Also, you might want to compare with how I originally updated the rand file. The test also uses an outside crate for pseudorandom tests.

...
use rand::{
    self,
    distributions::{Distribution, Standard},
    rngs::SmallRng,
    Rng,
    SeedableRng,
};

impl Distribution<Digit> for Standard {
    /// Creates a random `Digit` using the given random number generator.
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Digit {
        Digit(rng.next_u64())
    }
}

/// # Random Utilities using `rand` crate.
impl ApInt {
    /// Creates a new `ApInt` with the given `BitWidth` and random `Digit`s.
    pub fn random_with_width(width: BitWidth) -> ApInt {
        ApInt::random_with_width_using(width, &mut SmallRng::from_entropy())
    }

    /// Creates a new `ApInt` with the given `BitWidth` and random `Digit`s
    /// using the given random number generator. This is useful for
    /// cryptographic or testing purposes.
    pub fn random_with_width_using<R: Rng>(width: BitWidth, rng: &mut R) -> ApInt {
        let required_digits = width.required_digits();
        assert!(required_digits >= 1);
        let random_digits = rng
            .sample_iter::<Digit, Standard>(Standard)
            .take(required_digits);
        ApInt::from_iter(random_digits)
            .expect("We asserted that `required_digits` is at least `1` or greater
                     so it is safe to assume that `ApInt::from_iter` won't fail.")
            // This truncation will be cheap always!
            .into_truncate(width)
            .expect("`BitWidth::required_digits` returns an upper bound for the
                     number of required digits, so it is safe to truncate.")
    }

    /// Randomizes the digits of this `ApInt` inplace.
    pub fn randomize(&mut self) {
        self.randomize_using(&mut SmallRng::from_entropy())
    }

    /// Randomizes the digits of this `ApInt` inplace using the given random
    /// number generator.
    pub fn randomize_using<R: Rng>(&mut self, rng: &mut R) {
        self.digits_mut()
            .zip(rng.sample_iter::<Digit, Standard>(Standard))
            .for_each(|(d, r)| *d = r);
        self.clear_unused_bits();
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand_xoshiro::Xoshiro256StarStar;

    #[test]
    fn random_with_width_using() {
        let r = &mut Xoshiro256StarStar::seed_from_u64(0);
        assert_eq!(
            ApInt::random_with_width_using(BitWidth::w1(), r),
            ApInt::from_bool(false)
        );
        assert_eq!(
            ApInt::random_with_width_using(BitWidth::w8(), r),
            ApInt::from_u8(42)
        );
        assert_eq!(
            ApInt::random_with_width_using(BitWidth::w16(), r),
            ApInt::from_u16(59104)
        );
        assert_eq!(
            ApInt::random_with_width_using(BitWidth::w32(), r),
            ApInt::from_u32(640494892)
        );
        assert_eq!(
            ApInt::random_with_width_using(BitWidth::w64(), r),
            ApInt::from_u64(13521403990117723737)
        );
        assert_eq!(
            ApInt::random_with_width_using(BitWidth::w128(), r),
            ApInt::from([7788427924976520344u64, 18442103541295991498])
        );
    }

    #[test]
    fn randomize_using() {
        let r1 = &mut Xoshiro256StarStar::seed_from_u64(0);
        let r2 = &mut Xoshiro256StarStar::seed_from_u64(0);
...

Robbepop commented 5 years ago

Also, you might want to compare with how I originally updated the rand file. The test also uses an outside crate for pseudorandom tests.

...
use rand::{
    self,
    distributions::{Distribution, Standard},
    rngs::SmallRng,
    Rng,
    SeedableRng,
};

impl Distribution<Digit> for Standard {
    /// Creates a random `Digit` using the given random number generator.
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Digit {
        Digit(rng.next_u64())
    }
}

/// # Random Utilities using `rand` crate.
impl ApInt {
    /// Creates a new `ApInt` with the given `BitWidth` and random `Digit`s.
    pub fn random_with_width(width: BitWidth) -> ApInt {
        ApInt::random_with_width_using(width, &mut SmallRng::from_entropy())
    }

    /// Creates a new `ApInt` with the given `BitWidth` and random `Digit`s
    /// using the given random number generator. This is useful for
    /// cryptographic or testing purposes.
    pub fn random_with_width_using<R: Rng>(width: BitWidth, rng: &mut R) -> ApInt {
        let required_digits = width.required_digits();
        assert!(required_digits >= 1);
        let random_digits = rng
            .sample_iter::<Digit, Standard>(Standard)
            .take(required_digits);
        ApInt::from_iter(random_digits)
            .expect("We asserted that `required_digits` is at least `1` or greater
                     so it is safe to assume that `ApInt::from_iter` won't fail.")
            // This truncation will be cheap always!
            .into_truncate(width)
            .expect("`BitWidth::required_digits` returns an upper bound for the
                     number of required digits, so it is safe to truncate.")
    }

    /// Randomizes the digits of this `ApInt` inplace.
    pub fn randomize(&mut self) {
        self.randomize_using(&mut SmallRng::from_entropy())
    }

    /// Randomizes the digits of this `ApInt` inplace using the given random
    /// number generator.
    pub fn randomize_using<R: Rng>(&mut self, rng: &mut R) {
        self.digits_mut()
            .zip(rng.sample_iter::<Digit, Standard>(Standard))
            .for_each(|(d, r)| *d = r);
        self.clear_unused_bits();
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand_xoshiro::Xoshiro256StarStar;

    #[test]
    fn random_with_width_using() {
        let r = &mut Xoshiro256StarStar::seed_from_u64(0);
        assert_eq!(
            ApInt::random_with_width_using(BitWidth::w1(), r),
            ApInt::from_bool(false)
        );
        assert_eq!(
            ApInt::random_with_width_using(BitWidth::w8(), r),
            ApInt::from_u8(42)
        );
        assert_eq!(
            ApInt::random_with_width_using(BitWidth::w16(), r),
            ApInt::from_u16(59104)
        );
        assert_eq!(
            ApInt::random_with_width_using(BitWidth::w32(), r),
            ApInt::from_u32(640494892)
        );
        assert_eq!(
            ApInt::random_with_width_using(BitWidth::w64(), r),
            ApInt::from_u64(13521403990117723737)
        );
        assert_eq!(
            ApInt::random_with_width_using(BitWidth::w128(), r),
            ApInt::from([7788427924976520344u64, 18442103541295991498])
        );
    }

    #[test]
    fn randomize_using() {
        let r1 = &mut Xoshiro256StarStar::seed_from_u64(0);
        let r2 = &mut Xoshiro256StarStar::seed_from_u64(0);
...

Could you please file a single-purpose PR to improve upon this? Thanks! I explicitely do not want to copy from your work/branch since that is your IP and you should be credited for it.

Robbepop / apint

Make whole crate no_std compatible #50

Codecov Report