From 986ad2f782cf944990e4eda8bf88ea1821233302 Mon Sep 17 00:00:00 2001 From: Robin Krahl Date: Tue, 11 Dec 2018 23:50:45 +0100 Subject: Add nitrokey as a dependency to nitrocli The nitrokey crate provides a simple interface to the Nitrokey Storage and the Nitrokey Pro based on the libnitrokey library developed by Nitrokey UG. The low-level bindings to this library are available in the nitrokey-sys crate. This patch adds version v0.2.1 of the nitrokey crate as a dependency for nitrocli. It includes the indirect dependencies nitrokey-sys (version 3.4.1) and rand (version 0.4.3). Import subrepo nitrokey/:nitrokey at 2eccc96ceec2282b868891befe9cda7f941fbe7b Import subrepo nitrokey-sys/:nitrokey-sys at f1a11ebf72610fb9cf80ac7f9f147b4ba1a5336f Import subrepo rand/:rand at d7d5da49daf7ceb3e5940072940d495cced3a1b3 --- rand/src/distributions/range.rs | 241 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 241 insertions(+) create mode 100644 rand/src/distributions/range.rs (limited to 'rand/src/distributions/range.rs') diff --git a/rand/src/distributions/range.rs b/rand/src/distributions/range.rs new file mode 100644 index 0000000..935a00a --- /dev/null +++ b/rand/src/distributions/range.rs @@ -0,0 +1,241 @@ +// Copyright 2013 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Generating numbers between two others. + +// this is surprisingly complicated to be both generic & correct + +use core::num::Wrapping as w; + +use Rng; +use distributions::{Sample, IndependentSample}; + +/// Sample values uniformly between two bounds. +/// +/// This gives a uniform distribution (assuming the RNG used to sample +/// it is itself uniform & the `SampleRange` implementation for the +/// given type is correct), even for edge cases like `low = 0u8`, +/// `high = 170u8`, for which a naive modulo operation would return +/// numbers less than 85 with double the probability to those greater +/// than 85. +/// +/// Types should attempt to sample in `[low, high)`, i.e., not +/// including `high`, but this may be very difficult. All the +/// primitive integer types satisfy this property, and the float types +/// normally satisfy it, but rounding may mean `high` can occur. +/// +/// # Example +/// +/// ```rust +/// use rand::distributions::{IndependentSample, Range}; +/// +/// fn main() { +/// let between = Range::new(10, 10000); +/// let mut rng = rand::thread_rng(); +/// let mut sum = 0; +/// for _ in 0..1000 { +/// sum += between.ind_sample(&mut rng); +/// } +/// println!("{}", sum); +/// } +/// ``` +#[derive(Clone, Copy, Debug)] +pub struct Range { + low: X, + range: X, + accept_zone: X +} + +impl Range { + /// Create a new `Range` instance that samples uniformly from + /// `[low, high)`. Panics if `low >= high`. + pub fn new(low: X, high: X) -> Range { + assert!(low < high, "Range::new called with `low >= high`"); + SampleRange::construct_range(low, high) + } +} + +impl Sample for Range { + #[inline] + fn sample(&mut self, rng: &mut R) -> Sup { self.ind_sample(rng) } +} +impl IndependentSample for Range { + fn ind_sample(&self, rng: &mut R) -> Sup { + SampleRange::sample_range(self, rng) + } +} + +/// The helper trait for types that have a sensible way to sample +/// uniformly between two values. This should not be used directly, +/// and is only to facilitate `Range`. +pub trait SampleRange : Sized { + /// Construct the `Range` object that `sample_range` + /// requires. This should not ever be called directly, only via + /// `Range::new`, which will check that `low < high`, so this + /// function doesn't have to repeat the check. + fn construct_range(low: Self, high: Self) -> Range; + + /// Sample a value from the given `Range` with the given `Rng` as + /// a source of randomness. + fn sample_range(r: &Range, rng: &mut R) -> Self; +} + +macro_rules! integer_impl { + ($ty:ty, $unsigned:ident) => { + impl SampleRange for $ty { + // we play free and fast with unsigned vs signed here + // (when $ty is signed), but that's fine, since the + // contract of this macro is for $ty and $unsigned to be + // "bit-equal", so casting between them is a no-op & a + // bijection. + + #[inline] + fn construct_range(low: $ty, high: $ty) -> Range<$ty> { + let range = (w(high as $unsigned) - w(low as $unsigned)).0; + let unsigned_max: $unsigned = ::core::$unsigned::MAX; + + // this is the largest number that fits into $unsigned + // that `range` divides evenly, so, if we've sampled + // `n` uniformly from this region, then `n % range` is + // uniform in [0, range) + let zone = unsigned_max - unsigned_max % range; + + Range { + low: low, + range: range as $ty, + accept_zone: zone as $ty + } + } + + #[inline] + fn sample_range(r: &Range<$ty>, rng: &mut R) -> $ty { + loop { + // rejection sample + let v = rng.gen::<$unsigned>(); + // until we find something that fits into the + // region which r.range evenly divides (this will + // be uniformly distributed) + if v < r.accept_zone as $unsigned { + // and return it, with some adjustments + return (w(r.low) + w((v % r.range as $unsigned) as $ty)).0; + } + } + } + } + } +} + +integer_impl! { i8, u8 } +integer_impl! { i16, u16 } +integer_impl! { i32, u32 } +integer_impl! { i64, u64 } +#[cfg(feature = "i128_support")] +integer_impl! { i128, u128 } +integer_impl! { isize, usize } +integer_impl! { u8, u8 } +integer_impl! { u16, u16 } +integer_impl! { u32, u32 } +integer_impl! { u64, u64 } +#[cfg(feature = "i128_support")] +integer_impl! { u128, u128 } +integer_impl! { usize, usize } + +macro_rules! float_impl { + ($ty:ty) => { + impl SampleRange for $ty { + fn construct_range(low: $ty, high: $ty) -> Range<$ty> { + Range { + low: low, + range: high - low, + accept_zone: 0.0 // unused + } + } + fn sample_range(r: &Range<$ty>, rng: &mut R) -> $ty { + r.low + r.range * rng.gen::<$ty>() + } + } + } +} + +float_impl! { f32 } +float_impl! { f64 } + +#[cfg(test)] +mod tests { + use distributions::{Sample, IndependentSample}; + use super::Range as Range; + + #[should_panic] + #[test] + fn test_range_bad_limits_equal() { + Range::new(10, 10); + } + #[should_panic] + #[test] + fn test_range_bad_limits_flipped() { + Range::new(10, 5); + } + + #[test] + fn test_integers() { + let mut rng = ::test::rng(); + macro_rules! t { + ($($ty:ident),*) => {{ + $( + let v: &[($ty, $ty)] = &[(0, 10), + (10, 127), + (::core::$ty::MIN, ::core::$ty::MAX)]; + for &(low, high) in v.iter() { + let mut sampler: Range<$ty> = Range::new(low, high); + for _ in 0..1000 { + let v = sampler.sample(&mut rng); + assert!(low <= v && v < high); + let v = sampler.ind_sample(&mut rng); + assert!(low <= v && v < high); + } + } + )* + }} + } + #[cfg(not(feature = "i128_support"))] + t!(i8, i16, i32, i64, isize, + u8, u16, u32, u64, usize); + #[cfg(feature = "i128_support")] + t!(i8, i16, i32, i64, i128, isize, + u8, u16, u32, u64, u128, usize); + } + + #[test] + fn test_floats() { + let mut rng = ::test::rng(); + macro_rules! t { + ($($ty:ty),*) => {{ + $( + let v: &[($ty, $ty)] = &[(0.0, 100.0), + (-1e35, -1e25), + (1e-35, 1e-25), + (-1e35, 1e35)]; + for &(low, high) in v.iter() { + let mut sampler: Range<$ty> = Range::new(low, high); + for _ in 0..1000 { + let v = sampler.sample(&mut rng); + assert!(low <= v && v < high); + let v = sampler.ind_sample(&mut rng); + assert!(low <= v && v < high); + } + } + )* + }} + } + + t!(f32, f64) + } + +} -- cgit v1.2.1