std::rand: Add OSRng, ReaderRng wrappers around the OS RNG & generic Readers respectively.

The former reads from e.g. /dev/urandom, the latter just wraps any
std::rt::io::Reader into an interface that implements Rng.

This also adds Rng.fill_bytes for efficient implementations of the above
(reading 8 bytes at a time is inefficient when you can read 1000), and
removes the dependence on src/rt (i.e. rand_gen_seed) although this last
one requires implementing hand-seeding of the XorShiftRng used in the
scheduler on Linux/unixes, since OSRng relies on a scheduler existing to
be able to read from /dev/urandom.

3 files changed, 380 insertions, 29 deletions

diff --git a/src/libstd/rand/mod.rs b/src/libstd/rand/mod.rs
index 237ffb0e9ad..e6bf42a5aed 100644
--- a/src/libstd/rand/mod.rs
+++ b/src/libstd/rand/mod.rs
@@ -44,24 +44,24 @@ fn main () {
 */
 
 use cast;
-use cmp;
 use container::Container;
 use int;
-use iter::{Iterator, range, range_step};
+use iter::{Iterator, range};
 use local_data;
 use prelude::*;
 use str;
-use sys;
 use u32;
 use u64;
 use uint;
 use vec;
-use libc::size_t;
 
 pub use self::isaac::{IsaacRng, Isaac64Rng};
+pub use self::os::OSRng;
 
 pub mod distributions;
 pub mod isaac;
+pub mod os;
+pub mod reader;
 
 /// A type that can be randomly generated using an Rng
 pub trait Rand {
@@ -233,15 +233,6 @@ impl<T: Rand + 'static> Rand for @T {
     fn rand<R: Rng>(rng: &mut R) -> @T { @rng.gen() }
 }
 
-#[abi = "cdecl"]
-pub mod rustrt {
-    use libc::size_t;
-
-    extern {
-        pub fn rand_gen_seed(buf: *mut u8, sz: size_t);
-    }
-}
-
 /// A value with a particular weight compared to other values
 pub struct Weighted<T> {
     /// The numerical weight of this item
@@ -252,7 +243,8 @@ pub struct Weighted<T> {
 
 /// A random number generator
 pub trait Rng {
-    /// Return the next random u32.
+    /// Return the next random u32. This rarely needs to be called
+    /// directly, prefer `r.gen()` to `r.next_u32()`.
     ///
     /// By default this is implemented in terms of `next_u64`. An
     /// implementation of this trait must provide at least one of
@@ -261,7 +253,8 @@ pub trait Rng {
         self.next_u64() as u32
     }
 
-    /// Return the next random u64.
+    /// Return the next random u64. This rarely needs to be called
+    /// directly, prefer `r.gen()` to `r.next_u64()`.
     ///
     /// By default this is implemented in terms of `next_u32`. An
     /// implementation of this trait must provide at least one of
@@ -270,6 +263,76 @@ pub trait Rng {
         (self.next_u32() as u64 << 32) | (self.next_u32() as u64)
     }
 
+    /// Fill `dest` with random data.
+    ///
+    /// This has a default implementation in terms of `next_u64` and
+    /// `next_u32`, but should be overriden by implementations that
+    /// offer a more efficient solution than just calling those
+    /// methods repeatedly.
+    ///
+    /// This method does *not* have a requirement to bear any fixed
+    /// relationship to the other methods, for example, it does *not*
+    /// have to result in the same output as progressively filling
+    /// `dest` with `self.gen::<u8>()`, and any such behaviour should
+    /// not be relied upon.
+    ///
+    /// This method should guarantee that `dest` is entirely filled
+    /// with new data, and may fail if this is impossible
+    /// (e.g. reading past the end of a file that is being used as the
+    /// source of randomness).
+    ///
+    /// # Example
+    ///
+    /// ~~~{.rust}
+    /// use std::rand::{task_rng, Rng};
+    ///
+    /// fn main() {
+    ///    let mut v = [0u8, .. 13579];
+    ///    task_rng().fill_bytes(v);
+    ///    printfln!(v);
+    /// }
+    /// ~~~
+    fn fill_bytes(&mut self, mut dest: &mut [u8]) {
+        // this relies on the lengths being transferred correctly when
+        // transmuting between vectors like this.
+        let as_u64: &mut &mut [u64] = unsafe { cast::transmute(&mut dest) };
+        for dest in as_u64.mut_iter() {
+            *dest = self.next_u64();
+        }
+
+        // the above will have filled up the vector as much as
+        // possible in multiples of 8 bytes.
+        let mut remaining = dest.len() % 8;
+
+        // space for a u32
+        if remaining >= 4 {
+            let as_u32: &mut &mut [u32] = unsafe { cast::transmute(&mut dest) };
+            as_u32[as_u32.len() - 1] = self.next_u32();
+            remaining -= 4;
+        }
+        // exactly filled
+        if remaining == 0 { return }
+
+        // now we know we've either got 1, 2 or 3 spots to go,
+        // i.e. exactly one u32 is enough.
+        let rand = self.next_u32();
+        let remaining_index = dest.len() - remaining;
+        match dest.mut_slice_from(remaining_index) {
+            [ref mut a] => {
+                *a = rand as u8;
+            }
+            [ref mut a, ref mut b] => {
+                *a = rand as u8;
+                *b = (rand >> 8) as u8;
+            }
+            [ref mut a, ref mut b, ref mut c] => {
+                *a = rand as u8;
+                *b = (rand >> 8) as u8;
+                *c = (rand >> 16) as u8;
+            }
+            _ => fail2!("Rng.fill_bytes: the impossible occurred: remaining != 1, 2 or 3")
+        }
+    }
 
     /// Return a random value of a Rand type.
     ///
@@ -630,11 +693,9 @@ impl XorShiftRng {
         // specific size, so we can just use a fixed buffer.
         let mut s = [0u8, ..16];
         loop {
-            do s.as_mut_buf |p, sz| {
-                unsafe {
-                    rustrt::rand_gen_seed(p, sz as size_t);
-                }
-            }
+            let mut r = OSRng::new();
+            r.fill_bytes(s);
+
             if !s.iter().all(|x| *x == 0) {
                 break;
             }
@@ -660,15 +721,10 @@ impl XorShiftRng {
 
 /// Create a new random seed of length `n`.
 pub fn seed(n: uint) -> ~[u8] {
-    #[fixed_stack_segment]; #[inline(never)];
-
-    unsafe {
-        let mut s = vec::from_elem(n as uint, 0_u8);
-        do s.as_mut_buf |p, sz| {
-            rustrt::rand_gen_seed(p, sz as size_t)
-        }
-        s
-    }
+    let mut s = vec::from_elem(n as uint, 0_u8);
+    let mut r = OSRng::new();
+    r.fill_bytes(s);
+    s
 }
 
 // used to make space in TLS for a random number generator
@@ -720,6 +776,14 @@ mod test {
     use super::*;
 
     #[test]
+    fn test_fill_bytes_default() {
+        let mut r = weak_rng();
+
+        let mut v = [0u8, .. 100];
+        r.fill_bytes(v);
+    }
+
+    #[test]
     fn test_gen_integer_range() {
         let mut r = rng();
         for _ in range(0, 1000) {
diff --git a/src/libstd/rand/os.rs b/src/libstd/rand/os.rs
new file mode 100644
index 00000000000..0e6472b4d37
--- /dev/null
+++ b/src/libstd/rand/os.rs
@@ -0,0 +1,193 @@
+// 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 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! Interfaces to the operating system provided random number
+//! generators.
+
+use rand::Rng;
+use ops::Drop;
+
+#[cfg(unix)]
+use rand::reader::ReaderRng;
+#[cfg(unix)]
+use rt::io::{file, Open, Read};
+
+#[cfg(windows)]
+use ptr;
+#[cfg(windows)]
+use cast;
+#[cfg(windows)]
+use libc::{GetLastError, FALSE};
+
+/// A random number generator that retrieves randomness straight from
+/// the operating system. On Unix-like systems this reads from
+/// `/dev/urandom`, on Windows this uses `CryptGenRandom`.
+///
+/// This does not block.
+#[cfg(unix)]
+pub struct OSRng {
+    priv inner: ReaderRng<file::FileStream>
+}
+/// A random number generator that retrieves randomness straight from
+/// the operating system. On Unix-like systems this reads from
+/// `/dev/urandom`, on Windows this uses `CryptGenRandom`.
+///
+/// This does not block.
+///
+/// XXX: it is unlikely that this is threadsafe with the use of
+/// GetLastError.
+#[cfg(windows)]
+pub struct OSRng {
+    priv hcryptprov: raw::HCRYPTPROV
+}
+
+impl OSRng {
+    /// Create a new `OSRng`.
+    #[cfg(unix)]
+    pub fn new() -> OSRng {
+        let reader = file::open(& &"/dev/urandom", Open, Read).expect("Error opening /dev/urandom");
+        let reader_rng = ReaderRng::new(reader);
+
+        OSRng { inner: reader_rng }
+    }
+
+    /// Create a new `OSRng`.
+    #[cfg(windows)]
+    pub fn new() -> OSRng {
+        let hcp = ptr::mut_null();
+        // TODO these two 0 constants are incorrect!
+        if unsafe { raw::CryptAcquireContext(hcp, ptr::null(), ptr::null(), 0, 0); } == FALSE {
+            fail!("CryptAcquireContext failed with error %u", unsafe {GetLastError()})
+        }
+
+        OSRng { hcryptprov: hcp }
+    }
+}
+
+#[cfg(unix)]
+impl Rng for OSRng {
+    fn next_u32(&mut self) -> u32 {
+        self.inner.next_u32()
+    }
+    fn next_u64(&mut self) -> u64 {
+        self.inner.next_u64()
+    }
+    fn fill_bytes(&mut self, v: &mut [u8]) {
+        self.inner.fill_bytes(v)
+    }
+}
+
+#[cfg(windows)]
+impl Rng for OSRng {
+    fn next_u32(&mut self) -> u32 {
+        let mut v = [0u8, .. 4];
+        self.fill_bytes(v);
+        unsafe { cast::transmute(v) }
+    }
+    fn next_u64(&mut self) -> u64 {
+        let mut v = [0u8, .. 8];
+        self.fill_bytes(v);
+        unsafe { cast::transmute(v) }
+    }
+    fn fill_bytes(&mut self, v: &mut [u8]) {
+        if unsafe { raw::CryptGenRandom(self.hcryptprov, v.len(), v.unsafe_mut_ref(0)) } == FALSE {
+            fail!("CryptGenRandom failed with error %u", unsafe {GetLastError()})
+        }
+    }
+}
+
+impl Drop for OSRng {
+    #[cfg(unix)]
+    fn drop(&mut self) {
+        // ensure that OSRng is not implicitly copyable on all
+        // platforms, for consistency.
+    }
+
+    #[cfg(windows)]
+    fn drop(&mut self) {
+        // TODO this 0 means?
+        if unsafe { raw::CryptReleaseContext(self.hcryptprov, 0)} == FALSE {
+            fail!("CryptReleaseContext failed with error %u", unsafe {GetLastError()})
+        }
+    }
+}
+
+#[abi = "cdecl"]
+#[cfg(windows)]
+mod raw {
+    use libc::{LPCTSTR, DWORD, BOOL, BYTE};
+
+    enum HCRYPTPROV_opaque {}
+    pub type HCRYPTPROV = *CRYPTPROV;
+    extern {
+        pub fn CryptAcquireContext(phProv: *mut HCRYPTPROV,
+                                   pszContainer: LPCTSTR, pszProvider: LPCTSTR,
+                                   dwProvType: DWORD, dwFlags: DWORD) -> BOOL;
+        pub fn CryptGenRandom(hProv: HCRYPTPROV, dwLen: DWORD, pbBuffer: *mut BYTE) -> BOOL;
+        pub fn CryptReleaseContext(hProv: HCRYPTPROV, dwFlags: DWORD) -> BOOL;
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    use rand::Rng;
+
+    #[test]
+    fn test_os_rng() {
+        let mut r = OSRng::new();
+
+        r.next_u32();
+        r.next_u64();
+
+        let mut v = [0u8, .. 1000];
+        r.fill_bytes(v);
+    }
+
+    #[test]
+    fn test_os_rng_tasks() {
+        use task;
+        use comm;
+        use comm::{GenericChan, GenericPort};
+        use option::{None, Some};
+        use iter::{Iterator, range};
+        use vec::{ImmutableVector, OwnedVector};
+
+        let mut chans = ~[];
+        for _ in range(0, 20) {
+            let (p, c) = comm::stream();
+            chans.push(c);
+            do task::spawn_with(p) |p| {
+                // wait until all the tasks are ready to go.
+                p.recv();
+
+                // deschedule to attempt to interleave things as much
+                // as possible (XXX: is this a good test?)
+                let mut r = OSRng::new();
+                task::deschedule();
+                let mut v = [0u8, .. 1000];
+
+                for _ in range(0, 100) {
+                    r.next_u32();
+                    task::deschedule();
+                    r.next_u64();
+                    task::deschedule();
+                    r.fill_bytes(v);
+                    task::deschedule();
+                }
+            }
+        }
+
+        // start all the tasks
+        for c in chans.iter() {
+            c.send(())
+        }
+    }
+}
diff --git a/src/libstd/rand/reader.rs b/src/libstd/rand/reader.rs
new file mode 100644
index 00000000000..f1164346fe6
--- /dev/null
+++ b/src/libstd/rand/reader.rs
@@ -0,0 +1,94 @@
+// 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 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use rt::io::Reader;
+use rt::io::ReaderByteConversions;
+
+use rand::Rng;
+
+/// An RNG that reads random bytes straight from a `Reader`. This will
+/// work best with an infinite reader, but this is not required. The
+/// semantics of reading past the end of the reader are the same as
+/// those of the `read` method of the inner `Reader`.
+pub struct ReaderRng<R> {
+    priv reader: R
+}
+
+impl<R: Reader> ReaderRng<R> {
+    /// Create a new `ReaderRng` from a `Reader`.
+    pub fn new(r: R) -> ReaderRng<R> {
+        ReaderRng {
+            reader: r
+        }
+    }
+}
+
+impl<R: Reader> Rng for ReaderRng<R> {
+    fn next_u32(&mut self) -> u32 {
+        // XXX which is better: consistency between big/little-endian
+        // platforms, or speed.
+        if cfg!(target_endian="little") {
+            self.reader.read_le_u32_()
+        } else {
+            self.reader.read_be_u32_()
+        }
+    }
+    fn next_u64(&mut self) -> u64 {
+        if cfg!(target_endian="little") {
+            self.reader.read_le_u64_()
+        } else {
+            self.reader.read_be_u64_()
+        }
+    }
+    fn fill_bytes(&mut self, v: &mut [u8]) {
+        // XXX: check that we filled `v``
+        let _n = self.reader.read(v);
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    use rt::io::mem::MemReader;
+    use cast;
+
+    #[test]
+    fn test_reader_rng_u64() {
+        // transmute from the target to avoid endianness concerns.
+        let v = ~[1u64, 2u64, 3u64];
+        let bytes: ~[u8] = unsafe {cast::transmute(v)};
+        let mut rng = ReaderRng::new(MemReader::new(bytes));
+
+        assert_eq!(rng.next_u64(), 1);
+        assert_eq!(rng.next_u64(), 2);
+        assert_eq!(rng.next_u64(), 3);
+    }
+    #[test]
+    fn test_reader_rng_u32() {
+        // transmute from the target to avoid endianness concerns.
+        let v = ~[1u32, 2u32, 3u32];
+        let bytes: ~[u8] = unsafe {cast::transmute(v)};
+        let mut rng = ReaderRng::new(MemReader::new(bytes));
+
+        assert_eq!(rng.next_u32(), 1);
+        assert_eq!(rng.next_u32(), 2);
+        assert_eq!(rng.next_u32(), 3);
+    }
+    #[test]
+    fn test_reader_rng_fill_bytes() {
+        let v = [1u8, 2, 3, 4, 5, 6, 7, 8];
+        let mut w = [0u8, .. 8];
+
+        let mut rng = ReaderRng::new(MemReader::new(v.to_owned()));
+        rng.fill_bytes(w);
+
+        assert_eq!(v, w);
+    }
+}