gistfile1.diff

From 695d27766eeff690dd530e9bc1933365367ed85d Mon Sep 17 00:00:00 2001
From: Matthew Draper <matthew@trebex.net>
Date: Sat, 10 Apr 2010 02:51:26 +0930
Subject: [PATCH] Improved Kernel.{rand,srand} implementation.

Doesn't yet produce extra randomness to properly fill a bignum range.
---
 benchmark/rubinius/bm_random.rb |   50 ++++++++++++++++++
 kernel/common/kernel.rb         |   64 +++++++----------------
 kernel/common/load_order.txt    |    1 +
 kernel/common/random.rb         |  109 +++++++++++++++++++++++++++++++++++++++
 rakelib/platform.rake           |    9 +++
 5 files changed, 188 insertions(+), 45 deletions(-)
 create mode 100644 benchmark/rubinius/bm_random.rb
 create mode 100644 kernel/common/random.rb

diff --git a/benchmark/rubinius/bm_random.rb b/benchmark/rubinius/bm_random.rb
new file mode 100644
index 0000000..18646ea
--- /dev/null
+++ b/benchmark/rubinius/bm_random.rb
@@ -0,0 +1,50 @@
+require 'benchmark'
+
+total = (ENV['TOTAL'] || 10_000).to_i
+
+Benchmark.bmbm do |x|
+  x.report("Kernel#rand()") do
+    total.times do
+      rand
+    end
+  end
+
+  x.report("Kernel#rand(10)") do
+    total.times do
+      rand(10)
+    end
+  end
+
+  x.report("Kernel#rand(0x12345678901234567890)") do
+    total.times do
+      rand(0x12345678901234567890)
+    end
+  end
+
+  x.report("Kernel#srand()") do
+    total.times do
+      srand
+    end
+  end
+
+  x.report("Kernel#srand(0)") do
+    total.times do
+      srand(0)
+    end
+  end
+
+  x.report("Kernel#srand(0x12345678901234567890)") do
+    total.times do
+      srand(0x12345678901234567890)
+    end
+  end
+
+  x.report("Kernel#srand(10); Kernel#rand") do
+    (total / 20).times do
+      srand(10)
+      50.times do
+        rand
+      end
+    end
+  end
+end
diff --git a/kernel/common/kernel.rb b/kernel/common/kernel.rb
index 5d08471..be7e1a5 100644
--- a/kernel/common/kernel.rb
+++ b/kernel/common/kernel.rb
@@ -222,57 +222,31 @@ module Kernel
   end
   module_function :open
 
-  #--
-  # NOTE: This isn't quite MRI compatible.
-  # We don't seed the RNG by default with a combination of time, pid and
-  # sequence number
-  #++
-  #
-
-  @current_seed = 0
-
-  def self.srand(seed=undefined)
-    cur = @current_srand
-
+  def srand(seed=undefined)
     if seed.equal? undefined
-      begin
-        File.open("/dev/urandom", "r") do |f|
-          seed = f.read(10).unpack("I*")[0]
-        end
-      rescue Errno::ENOENT, Errno::EPERM, Errno::EACCES
-        seed = Time.now.to_i
-      end
-    else
-      seed = Type.coerce_to(seed, Integer, :to_int)
+      seed = Rubinius::Randomizer.instance.generate_seed
     end
 
-    FFI::Platform::POSIX.srand(seed)
-    @current_srand = seed
-
-    cur
-  end
+    unless seed.respond_to?(:to_int)
+      raise TypeError, "can't convert #{seed.class} into Integer"
+    end
 
-  # Redispatch to Kernel so we can store @current_srand as an ivar
-  # on Kernel without an accessor.
-  def srand(seed=undefined)
-    Kernel.srand(seed)
+    Rubinius::Randomizer.instance.swap_seed seed.to_int
   end
+  module_function :srand
 
-  private :srand
-
-  def rand(max=0)
-    max = max.to_i.abs
-    x = FFI::Platform::POSIX.rand
+  def rand(limit=0)
+    limit = Integer(limit).abs
 
-    # scale result of rand to a domain between 0 and max
-    if max == 0
-      x.to_f / 2147483647.0
-    elsif max == 1
-      0
-    elsif x < max
-      x
+    case limit
+    when 0
+      Rubinius::Randomizer.instance.random_float
+    when Fixnum
+      Rubinius::Randomizer.instance.random_fixnum limit
+    when Bignum
+      Rubinius::Randomizer.instance.random_bignum limit
     else
-      x % max
+      raise TypeError, "Integer() returned a non-integer"
     end
   end
   module_function :rand
diff --git a/kernel/common/load_order.txt b/kernel/common/load_order.txt
index 13e55b2..00fa0e8 100644
--- a/kernel/common/load_order.txt
+++ b/kernel/common/load_order.txt
@@ -64,6 +64,7 @@ rubinius.rbc
 pack.rbc
 struct.rbc
 process.rbc
+random.rbc
 regexp.rbc
 selector.rbc
 signal.rbc
diff --git a/kernel/common/random.rb b/kernel/common/random.rb
new file mode 100644
index 0000000..f336c35
--- /dev/null
+++ b/kernel/common/random.rb
@@ -0,0 +1,109 @@
+class Rubinius::Randomizer
+  POSIX_RAND_MAX = Rubinius::Config['rbx.platform.rand.RAND_MAX']
+  MAX = POSIX_RAND_MAX > Fixnum::MAX ? Fixnum::MAX : POSIX_RAND_MAX
+
+  def self.instance
+    @instance || (@instance = new)
+  end
+
+  def initialize
+    @counter = 0
+    begin
+      @handle = File.open("/dev/urandom", "r")
+    rescue Errno::ENOENT, Errno::EPERM, Errno::EACCES
+      @handle = nil
+    end
+
+    self.seed = generate_seed
+  end
+
+  def urandom(bytes)
+    @handle && @handle.read(bytes)
+  end
+
+  attr_reader :seed
+  def seed=(new_seed)
+    set_seed new_seed
+    @seed = new_seed
+  end
+
+  def set_seed(new_seed)
+    FFI::Platform::POSIX.srand new_seed
+  end
+
+  def swap_seed(new_seed)
+    old_seed, self.seed = self.seed, new_seed
+    old_seed
+  end
+
+  # Generate a random Float, in the range 0...1.0
+  def random_float
+    while true
+      result = random_bits.to_f / (MAX + 1).to_f
+      return result if result < 1.0
+    end
+  end
+
+  # Generate a random Fixnum, in the range 0...limit
+  def random_fixnum(limit)
+    # If the platform doesn't naturally supply enough randomness to
+    # achieve the limit, fall through to random_bignum, which knows how
+    # to amass randomness.
+    if MAX < Fixnum::MAX && limit > MAX + 1
+      random_bignum limit
+    else
+      while true
+        result = random_bits / ((MAX + 1) / limit)
+        return result if result < limit
+      end
+    end
+  end
+
+  # Generate a random Integer, in the range 0...limit
+  def random_bignum(limit)
+    while true
+      result = random_bits * (limit / (MAX + 1))
+      return result if result < limit
+    end
+  end
+
+  # We must clamp the result of rand(3) to a fixnum somehow, because
+  # otherwise the timing difference created by the construction of a
+  # bignum could reveal that one of the high bits is set.
+  #
+  # This is particularly relevant on many modern 32-bit systems, where
+  # RAND_MAX is 0x7fffffff (and Fixnum::MAX is 0x3fffffff); the timing
+  # difference would reveal exactly one bit.
+  if Fixnum::MAX >= POSIX_RAND_MAX
+    # If rand(3) will never return a Bignum, we needn't do any clamping.
+    def random_bits
+      FFI::Platform::POSIX.rand
+    end
+  else
+    # Otherwise, we (dangerously?) assume the result bits are all
+    # equally random, and mask out the bits we can't use.
+    def random_bits
+      FFI::Platform::POSIX.rand & Fixnum::MAX
+    end
+  end
+
+  def generate_seed
+    if urand = urandom(Rubinius::WORDSIZE / 2)
+      result = urand.unpack("I4")
+    else
+      result = [0, 0, 0, 0]
+    end
+
+    now = Time.now
+
+    result[0] ^= now.tv_usec
+    result[1] ^= now.tv_sec
+    result[2] ^= $$ ^ ((@counter += 1) << 16)
+    result[3] ^= result.object_id
+
+
+    (result[3] << (3 * Rubinius::WORDSIZE)) +
+      ((result[2] << (2 * Rubinius::WORDSIZE)) +
+      ((result[1] << (1 * Rubinius::WORDSIZE)) + result[0]))
+  end
+end
diff --git a/rakelib/platform.rake b/rakelib/platform.rake
index e6cdaf1..0ba8333 100644
--- a/rakelib/platform.rake
+++ b/rakelib/platform.rake
@@ -460,6 +460,14 @@ file 'runtime/platform.conf' => deps do |task|
     }
   end
 
+  rand_cg = FFI::ConstGenerator.new 'rbx.platform.rand' do |cg|
+    cg.include 'stdlib.h'
+
+    rand_constants = %w[RAND_MAX]
+
+    rand_constants.each { |c| cg.const c }
+  end
+
   # The constants come from MRI's signal.c. This means that some of them might
   # be missing.
 
@@ -543,6 +551,7 @@ file 'runtime/platform.conf' => deps do |task|
     socket_cg.dump_constants f
     process_cg.dump_constants f
     signal_cg.dump_constants f
+    rand_cg.dump_constants f
     zlib_cg.dump_constants f
 
     f.puts FFI::TypesGenerator.generate
-- 
1.7.0