std: Recreate a `rand` module

This commit shuffles around some of the `rand` code, along with some
reorganization. The new state of the world is as follows:

* The librand crate now only depends on libcore. This interface is experimental.
* The standard library has a new module, `std::rand`. This interface will
  eventually become stable.

Unfortunately, this entailed more of a breaking change than just shuffling some
names around. The following breaking changes were made to the rand library:

* Rng::gen_vec() was removed. This has been replaced with Rng::gen_iter() which
  will return an infinite stream of random values. Previous behavior can be
  regained with `rng.gen_iter().take(n).collect()`

* Rng::gen_ascii_str() was removed. This has been replaced with
  Rng::gen_ascii_chars() which will return an infinite stream of random ascii
  characters. Similarly to gen_iter(), previous behavior can be emulated with
  `rng.gen_ascii_chars().take(n).collect()`

* {IsaacRng, Isaac64Rng, XorShiftRng}::new() have all been removed. These all
  relied on being able to use an OSRng for seeding, but this is no longer
  available in librand (where these types are defined). To retain the same
  functionality, these types now implement the `Rand` trait so they can be
  generated with a random seed from another random number generator. This allows
  the stdlib to use an OSRng to create seeded instances of these RNGs.

* Rand implementations for `Box<T>` and `@T` were removed. These seemed to be
  pretty rare in the codebase, and it allows for librand to not depend on
  liballoc.  Additionally, other pointer types like Rc<T> and Arc<T> were not
  supported.  If this is undesirable, librand can depend on liballoc and regain
  these implementations.

* The WeightedChoice structure is no longer built with a `Vec<Weighted<T>>`,
  but rather a `&mut [Weighted<T>]`. This means that the WeightedChoice
  structure now has a lifetime associated with it.

* The `sample` method on `Rng` has been moved to a top-level function in the
  `rand` module due to its dependence on `Vec`.

cc #13851

[breaking-change]

7 files changed, 925 insertions, 25 deletions

diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index c1bc68b3e12..b63ccbef55f 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -120,12 +120,10 @@
 #[cfg(test)] extern crate debug;
 #[cfg(test)] #[phase(syntax, link)] extern crate log;
 
-// Make and rand accessible for benchmarking/testcases
-#[cfg(test)] extern crate rand;
-
 extern crate alloc;
 extern crate core;
 extern crate libc;
+extern crate core_rand = "rand";
 
 // Make std testable by not duplicating lang items. See #2912
 #[cfg(test)] extern crate realstd = "std";
@@ -208,6 +206,7 @@ pub mod slice;
 pub mod vec;
 pub mod str;
 pub mod string;
+pub mod rand;
 
 pub mod ascii;
 
diff --git a/src/libstd/num/strconv.rs b/src/libstd/num/strconv.rs
index 1efe83217f4..20f5927c9bd 100644
--- a/src/libstd/num/strconv.rs
+++ b/src/libstd/num/strconv.rs
@@ -819,84 +819,84 @@ mod bench {
 
     mod uint {
         use super::test::Bencher;
-        use rand::{XorShiftRng, Rng};
+        use rand::{weak_rng, Rng};
         use num::ToStrRadix;
 
         #[bench]
         fn to_str_bin(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { rng.gen::<uint>().to_str_radix(2); })
         }
 
         #[bench]
         fn to_str_oct(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { rng.gen::<uint>().to_str_radix(8); })
         }
 
         #[bench]
         fn to_str_dec(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { rng.gen::<uint>().to_str_radix(10); })
         }
 
         #[bench]
         fn to_str_hex(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { rng.gen::<uint>().to_str_radix(16); })
         }
 
         #[bench]
         fn to_str_base_36(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { rng.gen::<uint>().to_str_radix(36); })
         }
     }
 
     mod int {
         use super::test::Bencher;
-        use rand::{XorShiftRng, Rng};
+        use rand::{weak_rng, Rng};
         use num::ToStrRadix;
 
         #[bench]
         fn to_str_bin(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { rng.gen::<int>().to_str_radix(2); })
         }
 
         #[bench]
         fn to_str_oct(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { rng.gen::<int>().to_str_radix(8); })
         }
 
         #[bench]
         fn to_str_dec(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { rng.gen::<int>().to_str_radix(10); })
         }
 
         #[bench]
         fn to_str_hex(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { rng.gen::<int>().to_str_radix(16); })
         }
 
         #[bench]
         fn to_str_base_36(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { rng.gen::<int>().to_str_radix(36); })
         }
     }
 
     mod f64 {
         use super::test::Bencher;
-        use rand::{XorShiftRng, Rng};
+        use rand::{weak_rng, Rng};
         use f64;
 
         #[bench]
         fn float_to_str(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { f64::to_str(rng.gen()); })
         }
     }
diff --git a/src/libstd/os.rs b/src/libstd/os.rs
index f960228c63c..f6b9a7b24bc 100644
--- a/src/libstd/os.rs
+++ b/src/libstd/os.rs
@@ -1513,7 +1513,8 @@ mod tests {
 
     fn make_rand_name() -> String {
         let mut rng = rand::task_rng();
-        let n = format!("TEST{}", rng.gen_ascii_str(10u).as_slice());
+        let n = format!("TEST{}", rng.gen_ascii_chars().take(10u)
+                                     .collect::<String>());
         assert!(getenv(n.as_slice()).is_none());
         n
     }
diff --git a/src/libstd/rand/mod.rs b/src/libstd/rand/mod.rs
new file mode 100644
index 00000000000..c7ae6331d11
--- /dev/null
+++ b/src/libstd/rand/mod.rs
@@ -0,0 +1,525 @@
+// 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.
+
+/*!
+
+Utilities for random number generation
+
+The key functions are `random()` and `Rng::gen()`. These are polymorphic
+and so can be used to generate any type that implements `Rand`. Type inference
+means that often a simple call to `rand::random()` or `rng.gen()` will
+suffice, but sometimes an annotation is required, e.g. `rand::random::<f64>()`.
+
+See the `distributions` submodule for sampling random numbers from
+distributions like normal and exponential.
+
+# Task-local RNG
+
+There is built-in support for a RNG associated with each task stored
+in task-local storage. This RNG can be accessed via `task_rng`, or
+used implicitly via `random`. This RNG is normally randomly seeded
+from an operating-system source of randomness, e.g. `/dev/urandom` on
+Unix systems, and will automatically reseed itself from this source
+after generating 32 KiB of random data.
+
+# Cryptographic security
+
+An application that requires an entropy source for cryptographic purposes
+must use `OSRng`, which reads randomness from the source that the operating
+system provides (e.g. `/dev/urandom` on Unixes or `CryptGenRandom()` on Windows).
+The other random number generators provided by this module are not suitable
+for such purposes.
+
+*Note*: many Unix systems provide `/dev/random` as well as `/dev/urandom`.
+This module uses `/dev/urandom` for the following reasons:
+
+-   On Linux, `/dev/random` may block if entropy pool is empty; `/dev/urandom` will not block.
+    This does not mean that `/dev/random` provides better output than
+    `/dev/urandom`; the kernel internally runs a cryptographically secure pseudorandom
+    number generator (CSPRNG) based on entropy pool for random number generation,
+    so the "quality" of `/dev/random` is not better than `/dev/urandom` in most cases.
+    However, this means that `/dev/urandom` can yield somewhat predictable randomness
+    if the entropy pool is very small, such as immediately after first booting.
+    If an application likely to be run soon after first booting, or on a system with very
+    few entropy sources, one should consider using `/dev/random` via `ReaderRng`.
+-   On some systems (e.g. FreeBSD, OpenBSD and Mac OS X) there is no difference
+    between the two sources. (Also note that, on some systems e.g. FreeBSD, both `/dev/random`
+    and `/dev/urandom` may block once if the CSPRNG has not seeded yet.)
+
+# Examples
+
+```rust
+use std::rand;
+use std::rand::Rng;
+
+let mut rng = rand::task_rng();
+if rng.gen() { // bool
+    println!("int: {}, uint: {}", rng.gen::<int>(), rng.gen::<uint>())
+}
+```
+
+```rust
+use std::rand;
+
+let tuple = rand::random::<(f64, char)>();
+println!("{}", tuple)
+```
+*/
+
+use cell::RefCell;
+use clone::Clone;
+use io::IoResult;
+use iter::Iterator;
+use mem;
+use option::{Some, None};
+use rc::Rc;
+use result::{Ok, Err};
+use vec::Vec;
+
+#[cfg(not(target_word_size="64"))]
+use IsaacWordRng = core_rand::IsaacRng;
+#[cfg(target_word_size="64")]
+use IsaacWordRng = core_rand::Isaac64Rng;
+
+pub use core_rand::{Rand, Rng, SeedableRng, Open01, Closed01};
+pub use core_rand::{XorShiftRng, IsaacRng, Isaac64Rng};
+pub use core_rand::{distributions, reseeding};
+pub use rand::os::OSRng;
+
+pub mod os;
+pub mod reader;
+
+/// The standard RNG. This is designed to be efficient on the current
+/// platform.
+pub struct StdRng { rng: IsaacWordRng }
+
+impl StdRng {
+    /// Create a randomly seeded instance of `StdRng`.
+    ///
+    /// This is a very expensive operation as it has to read
+    /// randomness from the operating system and use this in an
+    /// expensive seeding operation. If one is only generating a small
+    /// number of random numbers, or doesn't need the utmost speed for
+    /// generating each number, `task_rng` and/or `random` may be more
+    /// appropriate.
+    ///
+    /// Reading the randomness from the OS may fail, and any error is
+    /// propagated via the `IoResult` return value.
+    pub fn new() -> IoResult<StdRng> {
+        OSRng::new().map(|mut r| StdRng { rng: r.gen() })
+    }
+}
+
+impl Rng for StdRng {
+    #[inline]
+    fn next_u32(&mut self) -> u32 {
+        self.rng.next_u32()
+    }
+
+    #[inline]
+    fn next_u64(&mut self) -> u64 {
+        self.rng.next_u64()
+    }
+}
+
+impl<'a> SeedableRng<&'a [uint]> for StdRng {
+    fn reseed(&mut self, seed: &'a [uint]) {
+        // the internal RNG can just be seeded from the above
+        // randomness.
+        self.rng.reseed(unsafe {mem::transmute(seed)})
+    }
+
+    fn from_seed(seed: &'a [uint]) -> StdRng {
+        StdRng { rng: SeedableRng::from_seed(unsafe {mem::transmute(seed)}) }
+    }
+}
+
+/// Create a weak random number generator with a default algorithm and seed.
+///
+/// It returns the fastest `Rng` algorithm currently available in Rust without
+/// consideration for cryptography or security. If you require a specifically
+/// seeded `Rng` for consistency over time you should pick one algorithm and
+/// create the `Rng` yourself.
+///
+/// This will read randomness from the operating system to seed the
+/// generator.
+pub fn weak_rng() -> XorShiftRng {
+    match OSRng::new() {
+        Ok(mut r) => r.gen(),
+        Err(e) => fail!("weak_rng: failed to create seeded RNG: {}", e)
+    }
+}
+
+/// Controls how the task-local RNG is reseeded.
+struct TaskRngReseeder;
+
+impl reseeding::Reseeder<StdRng> for TaskRngReseeder {
+    fn reseed(&mut self, rng: &mut StdRng) {
+        *rng = match StdRng::new() {
+            Ok(r) => r,
+            Err(e) => fail!("could not reseed task_rng: {}", e)
+        }
+    }
+}
+static TASK_RNG_RESEED_THRESHOLD: uint = 32_768;
+type TaskRngInner = reseeding::ReseedingRng<StdRng, TaskRngReseeder>;
+
+/// The task-local RNG.
+pub struct TaskRng {
+    rng: Rc<RefCell<TaskRngInner>>,
+}
+
+/// Retrieve the lazily-initialized task-local random number
+/// generator, seeded by the system. Intended to be used in method
+/// chaining style, e.g. `task_rng().gen::<int>()`.
+///
+/// The RNG provided will reseed itself from the operating system
+/// after generating a certain amount of randomness.
+///
+/// The internal RNG used is platform and architecture dependent, even
+/// if the operating system random number generator is rigged to give
+/// the same sequence always. If absolute consistency is required,
+/// explicitly select an RNG, e.g. `IsaacRng` or `Isaac64Rng`.
+pub fn task_rng() -> TaskRng {
+    // used to make space in TLS for a random number generator
+    local_data_key!(TASK_RNG_KEY: Rc<RefCell<TaskRngInner>>)
+
+    match TASK_RNG_KEY.get() {
+        None => {
+            let r = match StdRng::new() {
+                Ok(r) => r,
+                Err(e) => fail!("could not initialize task_rng: {}", e)
+            };
+            let rng = reseeding::ReseedingRng::new(r,
+                                                   TASK_RNG_RESEED_THRESHOLD,
+                                                   TaskRngReseeder);
+            let rng = Rc::new(RefCell::new(rng));
+            TASK_RNG_KEY.replace(Some(rng.clone()));
+
+            TaskRng { rng: rng }
+        }
+        Some(rng) => TaskRng { rng: rng.clone() }
+    }
+}
+
+impl Rng for TaskRng {
+    fn next_u32(&mut self) -> u32 {
+        self.rng.borrow_mut().next_u32()
+    }
+
+    fn next_u64(&mut self) -> u64 {
+        self.rng.borrow_mut().next_u64()
+    }
+
+    #[inline]
+    fn fill_bytes(&mut self, bytes: &mut [u8]) {
+        self.rng.borrow_mut().fill_bytes(bytes)
+    }
+}
+
+/// Generate a random value using the task-local random number
+/// generator.
+///
+/// # Example
+///
+/// ```rust
+/// use std::rand::random;
+///
+/// if random() {
+///     let x = random();
+///     println!("{}", 2u * x);
+/// } else {
+///     println!("{}", random::<f64>());
+/// }
+/// ```
+#[inline]
+pub fn random<T: Rand>() -> T {
+    task_rng().gen()
+}
+
+/// Randomly sample up to `n` elements from an iterator.
+///
+/// # Example
+///
+/// ```rust
+/// use std::rand::{task_rng, sample};
+///
+/// let mut rng = task_rng();
+/// let sample = sample(&mut rng, range(1, 100), 5);
+/// println!("{}", sample);
+/// ```
+pub fn sample<T, I: Iterator<T>, R: Rng>(rng: &mut R,
+                                         mut iter: I,
+                                         amt: uint) -> Vec<T> {
+    let mut reservoir: Vec<T> = iter.by_ref().take(amt).collect();
+    for (i, elem) in iter.enumerate() {
+        let k = rng.gen_range(0, i + 1 + amt);
+        if k < amt {
+            *reservoir.get_mut(k) = elem;
+        }
+    }
+    return reservoir;
+}
+
+#[cfg(test)]
+mod test {
+    use prelude::*;
+    use super::{Rng, task_rng, random, SeedableRng, StdRng, sample};
+    use iter::order;
+
+    struct ConstRng { i: u64 }
+    impl Rng for ConstRng {
+        fn next_u32(&mut self) -> u32 { self.i as u32 }
+        fn next_u64(&mut self) -> u64 { self.i }
+
+        // no fill_bytes on purpose
+    }
+
+    #[test]
+    fn test_fill_bytes_default() {
+        let mut r = ConstRng { i: 0x11_22_33_44_55_66_77_88 };
+
+        // check every remainder mod 8, both in small and big vectors.
+        let lengths = [0, 1, 2, 3, 4, 5, 6, 7,
+                       80, 81, 82, 83, 84, 85, 86, 87];
+        for &n in lengths.iter() {
+            let mut v = Vec::from_elem(n, 0u8);
+            r.fill_bytes(v.as_mut_slice());
+
+            // use this to get nicer error messages.
+            for (i, &byte) in v.iter().enumerate() {
+                if byte == 0 {
+                    fail!("byte {} of {} is zero", i, n)
+                }
+            }
+        }
+    }
+
+    #[test]
+    fn test_gen_range() {
+        let mut r = task_rng();
+        for _ in range(0, 1000) {
+            let a = r.gen_range(-3i, 42);
+            assert!(a >= -3 && a < 42);
+            assert_eq!(r.gen_range(0, 1), 0);
+            assert_eq!(r.gen_range(-12, -11), -12);
+        }
+
+        for _ in range(0, 1000) {
+            let a = r.gen_range(10, 42);
+            assert!(a >= 10 && a < 42);
+            assert_eq!(r.gen_range(0, 1), 0);
+            assert_eq!(r.gen_range(3_000_000u, 3_000_001), 3_000_000);
+        }
+
+    }
+
+    #[test]
+    #[should_fail]
+    fn test_gen_range_fail_int() {
+        let mut r = task_rng();
+        r.gen_range(5i, -2);
+    }
+
+    #[test]
+    #[should_fail]
+    fn test_gen_range_fail_uint() {
+        let mut r = task_rng();
+        r.gen_range(5u, 2u);
+    }
+
+    #[test]
+    fn test_gen_f64() {
+        let mut r = task_rng();
+        let a = r.gen::<f64>();
+        let b = r.gen::<f64>();
+        debug!("{}", (a, b));
+    }
+
+    #[test]
+    fn test_gen_weighted_bool() {
+        let mut r = task_rng();
+        assert_eq!(r.gen_weighted_bool(0u), true);
+        assert_eq!(r.gen_weighted_bool(1u), true);
+    }
+
+    #[test]
+    fn test_gen_ascii_str() {
+        let mut r = task_rng();
+        assert_eq!(r.gen_ascii_chars().take(0).len(), 0u);
+        assert_eq!(r.gen_ascii_chars().take(10).len(), 10u);
+        assert_eq!(r.gen_ascii_chars().take(16).len(), 16u);
+    }
+
+    #[test]
+    fn test_gen_vec() {
+        let mut r = task_rng();
+        assert_eq!(r.gen_iter::<u8>().take(0).len(), 0u);
+        assert_eq!(r.gen_iter::<u8>().take(10).len(), 10u);
+        assert_eq!(r.gen_iter::<f64>().take(16).len(), 16u);
+    }
+
+    #[test]
+    fn test_choose() {
+        let mut r = task_rng();
+        assert_eq!(r.choose([1, 1, 1]).map(|&x|x), Some(1));
+
+        let v: &[int] = &[];
+        assert_eq!(r.choose(v), None);
+    }
+
+    #[test]
+    fn test_shuffle() {
+        let mut r = task_rng();
+        let empty: &mut [int] = &mut [];
+        r.shuffle(empty);
+        let mut one = [1];
+        r.shuffle(one);
+        assert_eq!(one.as_slice(), &[1]);
+
+        let mut two = [1, 2];
+        r.shuffle(two);
+        assert!(two == [1, 2] || two == [2, 1]);
+
+        let mut x = [1, 1, 1];
+        r.shuffle(x);
+        assert_eq!(x.as_slice(), &[1, 1, 1]);
+    }
+
+    #[test]
+    fn test_task_rng() {
+        let mut r = task_rng();
+        r.gen::<int>();
+        let mut v = [1, 1, 1];
+        r.shuffle(v);
+        assert_eq!(v.as_slice(), &[1, 1, 1]);
+        assert_eq!(r.gen_range(0u, 1u), 0u);
+    }
+
+    #[test]
+    fn test_random() {
+        // not sure how to test this aside from just getting some values
+        let _n : uint = random();
+        let _f : f32 = random();
+        let _o : Option<Option<i8>> = random();
+        let _many : ((),
+                     (uint,
+                      int,
+                      Option<(u32, (bool,))>),
+                     (u8, i8, u16, i16, u32, i32, u64, i64),
+                     (f32, (f64, (f64,)))) = random();
+    }
+
+    #[test]
+    fn test_sample() {
+        let min_val = 1;
+        let max_val = 100;
+
+        let mut r = task_rng();
+        let vals = range(min_val, max_val).collect::<Vec<int>>();
+        let small_sample = sample(&mut r, vals.iter(), 5);
+        let large_sample = sample(&mut r, vals.iter(), vals.len() + 5);
+
+        assert_eq!(small_sample.len(), 5);
+        assert_eq!(large_sample.len(), vals.len());
+
+        assert!(small_sample.iter().all(|e| {
+            **e >= min_val && **e <= max_val
+        }));
+    }
+
+    #[test]
+    fn test_std_rng_seeded() {
+        let s = task_rng().gen_iter::<uint>().take(256).collect::<Vec<uint>>();
+        let mut ra: StdRng = SeedableRng::from_seed(s.as_slice());
+        let mut rb: StdRng = SeedableRng::from_seed(s.as_slice());
+        assert!(order::equals(ra.gen_ascii_chars().take(100),
+                              rb.gen_ascii_chars().take(100)));
+    }
+
+    #[test]
+    fn test_std_rng_reseed() {
+        let s = task_rng().gen_iter::<uint>().take(256).collect::<Vec<uint>>();
+        let mut r: StdRng = SeedableRng::from_seed(s.as_slice());
+        let string1 = r.gen_ascii_chars().take(100).collect::<String>();
+
+        r.reseed(s.as_slice());
+
+        let string2 = r.gen_ascii_chars().take(100).collect::<String>();
+        assert_eq!(string1, string2);
+    }
+}
+
+#[cfg(test)]
+static RAND_BENCH_N: u64 = 100;
+
+#[cfg(test)]
+mod bench {
+    extern crate test;
+    use prelude::*;
+
+    use self::test::Bencher;
+    use super::{XorShiftRng, StdRng, IsaacRng, Isaac64Rng, Rng, RAND_BENCH_N};
+    use super::{OSRng, weak_rng};
+    use mem::size_of;
+
+    #[bench]
+    fn rand_xorshift(b: &mut Bencher) {
+        let mut rng: XorShiftRng = OSRng::new().unwrap().gen();
+        b.iter(|| {
+            for _ in range(0, RAND_BENCH_N) {
+                rng.gen::<uint>();
+            }
+        });
+        b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
+    }
+
+    #[bench]
+    fn rand_isaac(b: &mut Bencher) {
+        let mut rng: IsaacRng = OSRng::new().unwrap().gen();
+        b.iter(|| {
+            for _ in range(0, RAND_BENCH_N) {
+                rng.gen::<uint>();
+            }
+        });
+        b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
+    }
+
+    #[bench]
+    fn rand_isaac64(b: &mut Bencher) {
+        let mut rng: Isaac64Rng = OSRng::new().unwrap().gen();
+        b.iter(|| {
+            for _ in range(0, RAND_BENCH_N) {
+                rng.gen::<uint>();
+            }
+        });
+        b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
+    }
+
+    #[bench]
+    fn rand_std(b: &mut Bencher) {
+        let mut rng = StdRng::new().unwrap();
+        b.iter(|| {
+            for _ in range(0, RAND_BENCH_N) {
+                rng.gen::<uint>();
+            }
+        });
+        b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
+    }
+
+    #[bench]
+    fn rand_shuffle_100(b: &mut Bencher) {
+        let mut rng = weak_rng();
+        let x : &mut[uint] = [1,..100];
+        b.iter(|| {
+            rng.shuffle(x);
+        })
+    }
+}
diff --git a/src/libstd/rand/os.rs b/src/libstd/rand/os.rs
new file mode 100644
index 00000000000..ea4d7ad25a3
--- /dev/null
+++ b/src/libstd/rand/os.rs
@@ -0,0 +1,248 @@
+// 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.
+
+pub use self::imp::OSRng;
+
+#[cfg(unix)]
+mod imp {
+    use io::{IoResult, File};
+    use path::Path;
+    use rand::Rng;
+    use rand::reader::ReaderRng;
+    use result::{Ok, Err};
+
+    /// A random number generator that retrieves randomness straight from
+    /// the operating system. Platform sources:
+    ///
+    /// - Unix-like systems (Linux, Android, Mac OSX): read directly from
+    ///   `/dev/urandom`.
+    /// - Windows: calls `CryptGenRandom`, using the default cryptographic
+    ///   service provider with the `PROV_RSA_FULL` type.
+    ///
+    /// This does not block.
+    #[cfg(unix)]
+    pub struct OSRng {
+        inner: ReaderRng<File>
+    }
+
+    impl OSRng {
+        /// Create a new `OSRng`.
+        pub fn new() -> IoResult<OSRng> {
+            let reader = try!(File::open(&Path::new("/dev/urandom")));
+            let reader_rng = ReaderRng::new(reader);
+
+            Ok(OSRng { inner: reader_rng })
+        }
+    }
+
+    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)]
+mod imp {
+    extern crate libc;
+
+    use container::Container;
+    use io::{IoResult, IoError};
+    use mem;
+    use ops::Drop;
+    use os;
+    use rand::Rng;
+    use result::{Ok, Err};
+    use rt::stack;
+    use self::libc::{c_ulong, DWORD, BYTE, LPCSTR, BOOL};
+    use slice::MutableVector;
+
+    type HCRYPTPROV = c_ulong;
+
+    /// A random number generator that retrieves randomness straight from
+    /// the operating system. Platform sources:
+    ///
+    /// - Unix-like systems (Linux, Android, Mac OSX): read directly from
+    ///   `/dev/urandom`.
+    /// - Windows: calls `CryptGenRandom`, using the default cryptographic
+    ///   service provider with the `PROV_RSA_FULL` type.
+    ///
+    /// This does not block.
+    pub struct OSRng {
+        hcryptprov: HCRYPTPROV
+    }
+
+    static PROV_RSA_FULL: DWORD = 1;
+    static CRYPT_SILENT: DWORD = 64;
+    static CRYPT_VERIFYCONTEXT: DWORD = 0xF0000000;
+    static NTE_BAD_SIGNATURE: DWORD = 0x80090006;
+
+    extern "system" {
+        fn CryptAcquireContextA(phProv: *mut HCRYPTPROV,
+                                pszContainer: LPCSTR,
+                                pszProvider: LPCSTR,
+                                dwProvType: DWORD,
+                                dwFlags: DWORD) -> BOOL;
+        fn CryptGenRandom(hProv: HCRYPTPROV,
+                          dwLen: DWORD,
+                          pbBuffer: *mut BYTE) -> BOOL;
+        fn CryptReleaseContext(hProv: HCRYPTPROV, dwFlags: DWORD) -> BOOL;
+    }
+
+    impl OSRng {
+        /// Create a new `OSRng`.
+        pub fn new() -> IoResult<OSRng> {
+            let mut hcp = 0;
+            let mut ret = unsafe {
+                CryptAcquireContextA(&mut hcp, 0 as LPCSTR, 0 as LPCSTR,
+                                     PROV_RSA_FULL,
+                                     CRYPT_VERIFYCONTEXT | CRYPT_SILENT)
+            };
+
+            // FIXME #13259:
+            // It turns out that if we can't acquire a context with the
+            // NTE_BAD_SIGNATURE error code, the documentation states:
+            //
+            //     The provider DLL signature could not be verified. Either the
+            //     DLL or the digital signature has been tampered with.
+            //
+            // Sounds fishy, no? As it turns out, our signature can be bad
+            // because our Thread Information Block (TIB) isn't exactly what it
+            // expects. As to why, I have no idea. The only data we store in the
+            // TIB is the stack limit for each thread, but apparently that's
+            // enough to make the signature valid.
+            //
+            // Furthermore, this error only happens the *first* time we call
+            // CryptAcquireContext, so we don't have to worry about future
+            // calls.
+            //
+            // Anyway, the fix employed here is that if we see this error, we
+            // pray that we're not close to the end of the stack, temporarily
+            // set the stack limit to 0 (what the TIB originally was), acquire a
+            // context, and then reset the stack limit.
+            //
+            // Again, I'm not sure why this is the fix, nor why we're getting
+            // this error. All I can say is that this seems to allow libnative
+            // to progress where it otherwise would be hindered. Who knew?
+            if ret == 0 && os::errno() as DWORD == NTE_BAD_SIGNATURE {
+                unsafe {
+                    let limit = stack::get_sp_limit();
+                    stack::record_sp_limit(0);
+                    ret = CryptAcquireContextA(&mut hcp, 0 as LPCSTR, 0 as LPCSTR,
+                                               PROV_RSA_FULL,
+                                               CRYPT_VERIFYCONTEXT | CRYPT_SILENT);
+                    stack::record_sp_limit(limit);
+                }
+            }
+
+            if ret == 0 {
+                Err(IoError::last_error())
+            } else {
+                Ok(OSRng { hcryptprov: hcp })
+            }
+        }
+    }
+
+    impl Rng for OSRng {
+        fn next_u32(&mut self) -> u32 {
+            let mut v = [0u8, .. 4];
+            self.fill_bytes(v);
+            unsafe { mem::transmute(v) }
+        }
+        fn next_u64(&mut self) -> u64 {
+            let mut v = [0u8, .. 8];
+            self.fill_bytes(v);
+            unsafe { mem::transmute(v) }
+        }
+        fn fill_bytes(&mut self, v: &mut [u8]) {
+            let ret = unsafe {
+                CryptGenRandom(self.hcryptprov, v.len() as DWORD,
+                               v.as_mut_ptr())
+            };
+            if ret == 0 {
+                fail!("couldn't generate random bytes: {}", os::last_os_error());
+            }
+        }
+    }
+
+    impl Drop for OSRng {
+        fn drop(&mut self) {
+            let ret = unsafe {
+                CryptReleaseContext(self.hcryptprov, 0)
+            };
+            if ret == 0 {
+                fail!("couldn't release context: {}", os::last_os_error());
+            }
+        }
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use prelude::*;
+
+    use super::OSRng;
+    use rand::Rng;
+    use task;
+
+    #[test]
+    fn test_os_rng() {
+        let mut r = OSRng::new().unwrap();
+
+        r.next_u32();
+        r.next_u64();
+
+        let mut v = [0u8, .. 1000];
+        r.fill_bytes(v);
+    }
+
+    #[test]
+    fn test_os_rng_tasks() {
+
+        let mut txs = vec!();
+        for _ in range(0, 20) {
+            let (tx, rx) = channel();
+            txs.push(tx);
+            task::spawn(proc() {
+                // wait until all the tasks are ready to go.
+                rx.recv();
+
+                // deschedule to attempt to interleave things as much
+                // as possible (XXX: is this a good test?)
+                let mut r = OSRng::new().unwrap();
+                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 tx in txs.iter() {
+            tx.send(())
+        }
+    }
+}
diff --git a/src/libstd/rand/reader.rs b/src/libstd/rand/reader.rs
new file mode 100644
index 00000000000..170884073f3
--- /dev/null
+++ b/src/libstd/rand/reader.rs
@@ -0,0 +1,123 @@
+// 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.
+
+//! A wrapper around any Reader to treat it as an RNG.
+
+use container::Container;
+use io::Reader;
+use rand::Rng;
+use result::{Ok, Err};
+
+/// An RNG that reads random bytes straight from a `Reader`. This will
+/// work best with an infinite reader, but this is not required.
+///
+/// It will fail if it there is insufficient data to fulfill a request.
+///
+/// # Example
+///
+/// ```rust
+/// use std::rand::{reader, Rng};
+/// use std::io::MemReader;
+///
+/// let mut rng = reader::ReaderRng::new(MemReader::new(vec!(1,2,3,4,5,6,7,8)));
+/// println!("{:x}", rng.gen::<uint>());
+/// ```
+pub struct ReaderRng<R> {
+    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 {
+        // This is designed for speed: reading a LE integer on a LE
+        // platform just involves blitting the bytes into the memory
+        // of the u32, similarly for BE on BE; avoiding byteswapping.
+        if cfg!(target_endian="little") {
+            self.reader.read_le_u32().unwrap()
+        } else {
+            self.reader.read_be_u32().unwrap()
+        }
+    }
+    fn next_u64(&mut self) -> u64 {
+        // see above for explanation.
+        if cfg!(target_endian="little") {
+            self.reader.read_le_u64().unwrap()
+        } else {
+            self.reader.read_be_u64().unwrap()
+        }
+    }
+    fn fill_bytes(&mut self, v: &mut [u8]) {
+        if v.len() == 0 { return }
+        match self.reader.read_at_least(v.len(), v) {
+            Ok(_) => {}
+            Err(e) => fail!("ReaderRng.fill_bytes error: {}", e)
+        }
+    }
+}
+
+#[cfg(test)]
+#[allow(deprecated_owned_vector)]
+mod test {
+    use prelude::*;
+
+    use super::ReaderRng;
+    use io::MemReader;
+    use mem;
+    use rand::Rng;
+
+    #[test]
+    fn test_reader_rng_u64() {
+        // transmute from the target to avoid endianness concerns.
+        let v = box [1u64, 2u64, 3u64];
+        let bytes: ~[u8] = unsafe {mem::transmute(v)};
+        let mut rng = ReaderRng::new(MemReader::new(bytes.move_iter().collect()));
+
+        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 = box [1u32, 2u32, 3u32];
+        let bytes: ~[u8] = unsafe {mem::transmute(v)};
+        let mut rng = ReaderRng::new(MemReader::new(bytes.move_iter().collect()));
+
+        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(Vec::from_slice(v)));
+        rng.fill_bytes(w);
+
+        assert!(v == w);
+    }
+
+    #[test]
+    #[should_fail]
+    fn test_reader_rng_insufficient_bytes() {
+        let mut rng = ReaderRng::new(MemReader::new(vec!()));
+        let mut v = [0u8, .. 3];
+        rng.fill_bytes(v);
+    }
+}
diff --git a/src/libstd/slice.rs b/src/libstd/slice.rs
index e5c0cc3babd..55bea068641 100644
--- a/src/libstd/slice.rs
+++ b/src/libstd/slice.rs
@@ -1303,7 +1303,8 @@ mod tests {
         use realstd::clone::Clone;
         for len in range(4u, 25) {
             for _ in range(0, 100) {
-                let mut v = task_rng().gen_vec::<uint>(len);
+                let mut v = task_rng().gen_iter::<uint>().take(len)
+                                      .collect::<Vec<uint>>();
                 let mut v1 = v.clone();
 
                 v.as_mut_slice().sort();
@@ -2321,7 +2322,7 @@ mod bench {
     fn sort_random_small(b: &mut Bencher) {
         let mut rng = weak_rng();
         b.iter(|| {
-            let mut v = rng.gen_vec::<u64>(5);
+            let mut v = rng.gen_iter::<u64>().take(5).collect::<Vec<u64>>();
             v.as_mut_slice().sort();
         });
         b.bytes = 5 * mem::size_of::<u64>() as u64;
@@ -2331,7 +2332,7 @@ mod bench {
     fn sort_random_medium(b: &mut Bencher) {
         let mut rng = weak_rng();
         b.iter(|| {
-            let mut v = rng.gen_vec::<u64>(100);
+            let mut v = rng.gen_iter::<u64>().take(100).collect::<Vec<u64>>();
             v.as_mut_slice().sort();
         });
         b.bytes = 100 * mem::size_of::<u64>() as u64;
@@ -2341,7 +2342,7 @@ mod bench {
     fn sort_random_large(b: &mut Bencher) {
         let mut rng = weak_rng();
         b.iter(|| {
-            let mut v = rng.gen_vec::<u64>(10000);
+            let mut v = rng.gen_iter::<u64>().take(10000).collect::<Vec<u64>>();
             v.as_mut_slice().sort();
         });
         b.bytes = 10000 * mem::size_of::<u64>() as u64;
@@ -2362,7 +2363,8 @@ mod bench {
     fn sort_big_random_small(b: &mut Bencher) {
         let mut rng = weak_rng();
         b.iter(|| {
-            let mut v = rng.gen_vec::<BigSortable>(5);
+            let mut v = rng.gen_iter::<BigSortable>().take(5)
+                           .collect::<Vec<BigSortable>>();
             v.sort();
         });
         b.bytes = 5 * mem::size_of::<BigSortable>() as u64;
@@ -2372,7 +2374,8 @@ mod bench {
     fn sort_big_random_medium(b: &mut Bencher) {
         let mut rng = weak_rng();
         b.iter(|| {
-            let mut v = rng.gen_vec::<BigSortable>(100);
+            let mut v = rng.gen_iter::<BigSortable>().take(100)
+                           .collect::<Vec<BigSortable>>();
             v.sort();
         });
         b.bytes = 100 * mem::size_of::<BigSortable>() as u64;
@@ -2382,7 +2385,8 @@ mod bench {
     fn sort_big_random_large(b: &mut Bencher) {
         let mut rng = weak_rng();
         b.iter(|| {
-            let mut v = rng.gen_vec::<BigSortable>(10000);
+            let mut v = rng.gen_iter::<BigSortable>().take(10000)
+                           .collect::<Vec<BigSortable>>();
             v.sort();
         });
         b.bytes = 10000 * mem::size_of::<BigSortable>() as u64;