Skip to main content

rand/distr/
uniform_other.rs

1// Copyright 2018-2020 Developers of the Rand project.
2// Copyright 2017 The Rust Project Developers.
3//
4// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
5// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
6// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
7// option. This file may not be copied, modified, or distributed
8// except according to those terms.
9
10//! `UniformChar`, `UniformDuration` implementations
11
12use super::{Error, SampleBorrow, SampleUniform, Uniform, UniformInt, UniformSampler};
13use crate::Rng;
14use crate::distr::Distribution;
15use core::time::Duration;
16
17#[cfg(feature = "serde")]
18use serde::{Deserialize, Serialize};
19
20impl SampleUniform for char {
21    type Sampler = UniformChar;
22}
23
24/// The back-end implementing [`UniformSampler`] for `char`.
25///
26/// Unless you are implementing [`UniformSampler`] for your own type, this type
27/// should not be used directly, use [`Uniform`] instead.
28///
29/// This differs from integer range sampling since the range `0xD800..=0xDFFF`
30/// are used for surrogate pairs in UCS and UTF-16, and consequently are not
31/// valid Unicode code points. We must therefore avoid sampling values in this
32/// range.
33#[derive(Clone, Copy, Debug, PartialEq, Eq)]
34#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
35pub struct UniformChar {
36    #[cfg_attr(feature = "serde", serde(deserialize_with = "deser_sampler"))]
37    sampler: UniformInt<u32>,
38}
39
40#[cfg(feature = "serde")]
41fn deser_sampler<'de, D>(d: D) -> Result<UniformInt<u32>, D::Error>
42where
43    D: serde::Deserializer<'de>,
44{
45    let sampler = <UniformInt<u32> as serde::Deserialize>::deserialize(d)?;
46    if sampler.max() > char::MAX as u32 - CHAR_SURROGATE_LEN {
47        return Err(serde::de::Error::custom(
48            "bad sampler range for UniformChar",
49        ));
50    }
51    Ok(sampler)
52}
53
54/// UTF-16 surrogate range start
55const CHAR_SURROGATE_START: u32 = 0xD800;
56/// UTF-16 surrogate range size
57const CHAR_SURROGATE_LEN: u32 = 0xE000 - CHAR_SURROGATE_START;
58
59/// Convert `char` to compressed `u32`
60fn char_to_comp_u32(c: char) -> u32 {
61    match c as u32 {
62        c if c >= CHAR_SURROGATE_START => c - CHAR_SURROGATE_LEN,
63        c => c,
64    }
65}
66
67impl UniformSampler for UniformChar {
68    type X = char;
69
70    #[inline] // if the range is constant, this helps LLVM to do the
71    // calculations at compile-time.
72    fn new<B1, B2>(low_b: B1, high_b: B2) -> Result<Self, Error>
73    where
74        B1: SampleBorrow<Self::X> + Sized,
75        B2: SampleBorrow<Self::X> + Sized,
76    {
77        let low = char_to_comp_u32(*low_b.borrow());
78        let high = char_to_comp_u32(*high_b.borrow());
79        let sampler = UniformInt::<u32>::new(low, high);
80        sampler.map(|sampler| UniformChar { sampler })
81    }
82
83    #[inline] // if the range is constant, this helps LLVM to do the
84    // calculations at compile-time.
85    fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Result<Self, Error>
86    where
87        B1: SampleBorrow<Self::X> + Sized,
88        B2: SampleBorrow<Self::X> + Sized,
89    {
90        let low = char_to_comp_u32(*low_b.borrow());
91        let high = char_to_comp_u32(*high_b.borrow());
92        let sampler = UniformInt::<u32>::new_inclusive(low, high);
93        sampler.map(|sampler| UniformChar { sampler })
94    }
95
96    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
97        let mut x = self.sampler.sample(rng);
98        if x >= CHAR_SURROGATE_START {
99            x += CHAR_SURROGATE_LEN;
100        }
101
102        char::from_u32(x)
103            .expect("rand::distr::uniform::UniformChar: invalid Unicode scalar value (likely memory corruption)")
104    }
105}
106
107#[cfg(feature = "alloc")]
108impl crate::distr::SampleString for Uniform<char> {
109    fn append_string<R: Rng + ?Sized>(
110        &self,
111        rng: &mut R,
112        string: &mut alloc::string::String,
113        len: usize,
114    ) {
115        // Getting the hi value to assume the required length to reserve in string.
116        let mut hi = self.0.sampler.low + self.0.sampler.range - 1;
117        if hi >= CHAR_SURROGATE_START {
118            hi += CHAR_SURROGATE_LEN;
119        }
120        // Get the utf8 length of hi to minimize extra space.
121        let max_char_len = char::from_u32(hi).map(char::len_utf8).unwrap_or(4);
122        string.reserve(max_char_len * len);
123        string.extend(self.sample_iter(rng).take(len))
124    }
125}
126
127/// The back-end implementing [`UniformSampler`] for `Duration`.
128///
129/// Unless you are implementing [`UniformSampler`] for your own types, this type
130/// should not be used directly, use [`Uniform`] instead.
131#[derive(Clone, Copy, Debug, PartialEq, Eq)]
132#[cfg_attr(feature = "serde", derive(Serialize))]
133pub struct UniformDuration {
134    mode: UniformDurationMode,
135    offset: u32,
136}
137
138/// `sample` feeds the sampler state straight to `Duration::new`, which panics
139/// on overflow, so reject any state which cannot have come from `new_inclusive`
140/// in the same way `UniformChar` rejects a bad `UniformInt<u32>`.
141#[cfg(feature = "serde")]
142impl<'de> Deserialize<'de> for UniformDuration {
143    fn deserialize<D>(d: D) -> Result<Self, D::Error>
144    where
145        D: serde::Deserializer<'de>,
146    {
147        /// Nanoseconds in one second
148        const NANOS_PER_SEC: u64 = 1_000_000_000;
149
150        #[derive(Deserialize)]
151        #[serde(rename = "UniformDuration")]
152        struct Fields {
153            mode: UniformDurationMode,
154            offset: u32,
155        }
156
157        let Fields { mode, offset } = Fields::deserialize(d)?;
158
159        let valid = offset < NANOS_PER_SEC as u32
160            && match mode {
161                UniformDurationMode::Small { secs, nanos } => {
162                    let carry = u64::from(nanos.0.max()) / NANOS_PER_SEC;
163                    secs.checked_add(carry).is_some()
164                }
165                UniformDurationMode::Medium { .. } => true,
166                UniformDurationMode::Large {
167                    max_secs,
168                    max_nanos,
169                    secs,
170                } => {
171                    let carry = (u64::from(max_nanos) + u64::from(offset)) / NANOS_PER_SEC;
172                    // `new_inclusive` samples `secs` over at least two values
173                    // (`low_s < high_s`), so `sample` rejects at most about
174                    // half of its draws. A single-value range with a small
175                    // `max_nanos` would make it loop for ~`NANOS_PER_SEC` iterations.
176                    secs.max() == max_secs
177                        && secs.range != 1
178                        && max_secs.checked_add(carry).is_some()
179                }
180            };
181
182        if !valid {
183            return Err(serde::de::Error::custom(
184                "bad sampler state for UniformDuration",
185            ));
186        }
187
188        Ok(UniformDuration { mode, offset })
189    }
190}
191
192#[derive(Debug, Copy, Clone, PartialEq, Eq)]
193#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
194enum UniformDurationMode {
195    Small {
196        secs: u64,
197        nanos: Uniform<u32>,
198    },
199    Medium {
200        nanos: Uniform<u64>,
201    },
202    Large {
203        max_secs: u64,
204        max_nanos: u32,
205        secs: UniformInt<u64>,
206    },
207}
208
209impl SampleUniform for Duration {
210    type Sampler = UniformDuration;
211}
212
213impl UniformSampler for UniformDuration {
214    type X = Duration;
215
216    #[inline]
217    fn new<B1, B2>(low_b: B1, high_b: B2) -> Result<Self, Error>
218    where
219        B1: SampleBorrow<Self::X> + Sized,
220        B2: SampleBorrow<Self::X> + Sized,
221    {
222        let low = *low_b.borrow();
223        let high = *high_b.borrow();
224        if !(low < high) {
225            return Err(Error::EmptyRange);
226        }
227        UniformDuration::new_inclusive(low, high - Duration::new(0, 1))
228    }
229
230    #[inline]
231    fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Result<Self, Error>
232    where
233        B1: SampleBorrow<Self::X> + Sized,
234        B2: SampleBorrow<Self::X> + Sized,
235    {
236        let low = *low_b.borrow();
237        let high = *high_b.borrow();
238        if !(low <= high) {
239            return Err(Error::EmptyRange);
240        }
241
242        let low_s = low.as_secs();
243        let low_n = low.subsec_nanos();
244        let mut high_s = high.as_secs();
245        let mut high_n = high.subsec_nanos();
246
247        if high_n < low_n {
248            high_s -= 1;
249            high_n += 1_000_000_000;
250        }
251
252        let mode = if low_s == high_s {
253            UniformDurationMode::Small {
254                secs: low_s,
255                nanos: Uniform::new_inclusive(low_n, high_n)?,
256            }
257        } else {
258            let max = high_s
259                .checked_mul(1_000_000_000)
260                .and_then(|n| n.checked_add(u64::from(high_n)));
261
262            if let Some(higher_bound) = max {
263                let lower_bound = low_s * 1_000_000_000 + u64::from(low_n);
264                UniformDurationMode::Medium {
265                    nanos: Uniform::new_inclusive(lower_bound, higher_bound)?,
266                }
267            } else {
268                // An offset is applied to simplify generation of nanoseconds
269                let max_nanos = high_n - low_n;
270                UniformDurationMode::Large {
271                    max_secs: high_s,
272                    max_nanos,
273                    secs: UniformInt::new_inclusive(low_s, high_s)?,
274                }
275            }
276        };
277        Ok(UniformDuration {
278            mode,
279            offset: low_n,
280        })
281    }
282
283    #[inline]
284    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Duration {
285        match self.mode {
286            UniformDurationMode::Small { secs, nanos } => {
287                let n = nanos.sample(rng);
288                Duration::new(secs, n)
289            }
290            UniformDurationMode::Medium { nanos } => {
291                let nanos = nanos.sample(rng);
292                Duration::new(nanos / 1_000_000_000, (nanos % 1_000_000_000) as u32)
293            }
294            UniformDurationMode::Large {
295                max_secs,
296                max_nanos,
297                secs,
298            } => {
299                // constant folding means this is at least as fast as `Rng::sample(Range)`
300                let nano_range = Uniform::new(0, 1_000_000_000).unwrap();
301                loop {
302                    let s = secs.sample(rng);
303                    let n = nano_range.sample(rng);
304                    if !(s == max_secs && n > max_nanos) {
305                        let sum = n + self.offset;
306                        break Duration::new(s, sum);
307                    }
308                }
309            }
310        }
311    }
312}
313
314#[cfg(test)]
315mod tests {
316    use super::*;
317    use crate::RngExt;
318
319    #[test]
320    #[cfg(feature = "serde")]
321    fn test_serialization_uniform_duration() {
322        let distr = UniformDuration::new(Duration::from_secs(10), Duration::from_secs(60)).unwrap();
323        let de_distr: UniformDuration =
324            postcard::from_bytes(&postcard::to_allocvec(&distr).unwrap()).unwrap();
325        assert_eq!(distr, de_distr);
326    }
327
328    #[test]
329    #[cfg_attr(miri, ignore)] // Miri is too slow
330    fn test_char() {
331        let mut rng = crate::test::rng(891);
332        let mut max = core::char::from_u32(0).unwrap();
333        for _ in 0..100 {
334            let c = rng.random_range('A'..='Z');
335            assert!(c.is_ascii_uppercase());
336            max = max.max(c);
337        }
338        assert_eq!(max, 'Z');
339        let d = Uniform::new(
340            core::char::from_u32(0xD7F0).unwrap(),
341            core::char::from_u32(0xE010).unwrap(),
342        )
343        .unwrap();
344        for _ in 0..100 {
345            let c = d.sample(&mut rng);
346            assert!((c as u32) < 0xD800 || (c as u32) > 0xDFFF);
347        }
348        #[cfg(feature = "alloc")]
349        {
350            use crate::distr::SampleString;
351            let string1 = d.sample_string(&mut rng, 100);
352            assert_eq!(string1.capacity(), 300);
353            let string2 = Uniform::new(
354                core::char::from_u32(0x0000).unwrap(),
355                core::char::from_u32(0x0080).unwrap(),
356            )
357            .unwrap()
358            .sample_string(&mut rng, 100);
359            assert_eq!(string2.capacity(), 100);
360            let string3 = Uniform::new_inclusive(
361                core::char::from_u32(0x0000).unwrap(),
362                core::char::from_u32(0x0080).unwrap(),
363            )
364            .unwrap()
365            .sample_string(&mut rng, 100);
366            assert_eq!(string3.capacity(), 200);
367        }
368    }
369
370    #[test]
371    #[cfg(feature = "serde")]
372    fn test_char_bad_deser() {
373        fn do_test(json: &str, col: usize) {
374            let result = serde_json::from_str::<Uniform<char>>(json);
375            assert!(result.is_err());
376            let err = result.unwrap_err();
377            assert_eq!(err.classify(), serde_json::error::Category::Data);
378
379            #[cfg(feature = "alloc")]
380            {
381                let msg =
382                    alloc::format!("bad sampler range for UniformChar at line 1 column {col}");
383                assert_eq!(alloc::string::ToString::to_string(&err), msg);
384            }
385        }
386
387        do_test(r#"{"sampler":{"low":5,"range":0,"thresh":0}}"#, 42);
388        do_test(r#"{"sampler":{"low":4294967200,"range":0,"thresh":0}}"#, 51);
389        do_test(
390            r#"{"sampler":{"low":4294967280,"range":32,"thresh":0}}"#,
391            52,
392        );
393    }
394
395    #[test]
396    #[cfg(feature = "serde")]
397    fn test_duration_bad_deser() {
398        fn do_test(json: &str) {
399            let result = serde_json::from_str::<UniformDuration>(json);
400            assert!(result.is_err());
401            let err = result.unwrap_err();
402            assert_eq!(err.classify(), serde_json::error::Category::Data);
403
404            #[cfg(feature = "alloc")]
405            {
406                let msg = "bad sampler state for UniformDuration";
407                assert!(alloc::string::ToString::to_string(&err).starts_with(msg));
408            }
409        }
410
411        // Small: sampled nanos carry a second into `secs`, overflowing it
412        do_test(
413            r#"{"mode":{"Small":{"secs":18446744073709551615,"nanos":{"low":1000000000,"range":1,"thresh":0}}},"offset":0}"#,
414        );
415        // Large: the seconds sampler can exceed `max_secs`, so the rejection
416        // test in `sample` never fires and `secs + 1` overflows
417        do_test(
418            r#"{"mode":{"Large":{"max_secs":0,"max_nanos":999999999,"secs":{"low":18446744073709551615,"range":0,"thresh":0}}},"offset":999999999}"#,
419        );
420        // Large: `offset` is not a valid subsecond nanosecond count
421        do_test(
422            r#"{"mode":{"Large":{"max_secs":10,"max_nanos":999999999,"secs":{"low":0,"range":11,"thresh":0}}},"offset":4294967295}"#,
423        );
424        // Large: the seconds sampler covers all of `u64`, not `..=max_secs`
425        do_test(
426            r#"{"mode":{"Large":{"max_secs":0,"max_nanos":0,"secs":{"low":0,"range":0,"thresh":0}}},"offset":0}"#,
427        );
428        // Large: the seconds sampler's maximum is not `max_secs`
429        do_test(
430            r#"{"mode":{"Large":{"max_secs":20,"max_nanos":0,"secs":{"low":0,"range":11,"thresh":0}}},"offset":0}"#,
431        );
432        // Large: a single-value seconds sampler would reject ~every sample
433        do_test(
434            r#"{"mode":{"Large":{"max_secs":10,"max_nanos":0,"secs":{"low":10,"range":1,"thresh":0}}},"offset":0}"#,
435        );
436    }
437
438    #[test]
439    #[cfg(feature = "serde")]
440    fn test_duration_large_narrow_range_roundtrip() {
441        // Valid `Large` sampler whose seconds range holds only two values
442        let low = Duration::new(u64::MAX - 1, 0);
443        let high = Duration::new(u64::MAX, 0);
444        let distr = UniformDuration::new_inclusive(low, high).unwrap();
445        assert!(matches!(distr.mode, UniformDurationMode::Large { .. }));
446        let json = serde_json::to_string(&distr).unwrap();
447        let de_distr: UniformDuration = serde_json::from_str(&json).unwrap();
448        assert_eq!(distr, de_distr);
449    }
450
451    #[test]
452    #[cfg_attr(miri, ignore)] // Miri is too slow
453    fn test_durations() {
454        let mut rng = crate::test::rng(253);
455
456        let v = &[
457            (Duration::new(10, 50000), Duration::new(100, 1234)),
458            (Duration::new(0, 100), Duration::new(1, 50)),
459            (Duration::new(0, 0), Duration::new(u64::MAX, 999_999_999)),
460        ];
461        for &(low, high) in v.iter() {
462            let my_uniform = Uniform::new(low, high).unwrap();
463            for _ in 0..1000 {
464                let v = rng.sample(my_uniform);
465                assert!(low <= v && v < high);
466            }
467        }
468    }
469}