package Roll;

# You are free to use this program for any purpose.
# Author: Bruno Wolff III
# Last changed: May 27, 2001

# This package provides for generating random dice rolls. A hit counting
# function (for the game Titan) is also provided. Entropy comes from
# /dev/random. The program is designed to conserve on the entropy used to
# generate rolls. This includes preserving left over bits accross rolls
# and allowing for a way to batch rolls together. The random numbers
# generated have no bias (assuming there is none in the data from
# /dev/random).

# Dm   - Generate a random integer from 1 to m. Bad values for m will
#        return a value of 0.

# nDm  - Generate n random integers from 1 to m. The rolls will be batched
#        together in order to use entropy more efficiently. Bad values for
#        n or m will result in an empty list being returned.

# nUm  - Generate n unique random integers from 1 to m. The rolls will be
#        batched together in order to use entropy more efficiently. Bad
#        values for n or m will result in an empty list being returned.

# D6   - Shortcut function for calling Dm with m = 6.

# nD6  - Shortcut function for calling nDm with m = 6.

# hits - The first argument is the minimum value to count. The rest of
#        the arguments are a list of numbers. The number of numbers in that
#        list greater than or equal to the test value is returned.

# D2   - Returns 1 or 2 using buffered bits from /dev/random. Bits are
#        buffered in blocks of 8.

# entropy - Returns how many bits of entropy have been used.

use Exporter();

@ISA = qw(Exporter);
@EXPORT = qw(Dm nDm nUm D6 nD6 hits D2 entropy);

# Do not generate numbers greater than this value. This should 2 to the minimum
# number of bits preserved by either integer or floating point operations,
# power.
$maxint = 2 ** 30;

# Mark random bit buffer as empty
$bits = 8;
open(RANDOM, '/dev/random') || die "Couldn't open /dev/random.\n";

# Keep track on entropy for the curious
$entropy = 0;

# Return a random bit
sub D2() {
  my $i;
  if ($bits >= 8) {
    die "Couldn't read /dev/random.\n" unless sysread(RANDOM, $string, 1) == 1;
    $bits = 0;
  }
  $entropy++;
  vec($string, $bits++, 1) + 1;
}

# Return the number of bits of entropy used
sub entropy() {
  return $entropy;
}

# Return an m-sided die roll
sub Dm($) {
  my $range = 1;
  my $num = 0;
  my $m = $_[0];
  return 0 if $m < 1 || $m >= ($maxint/2) || $m != int($m);
  while (1) {
    while ($range < $m) {
      $range *= 2;
      $num += $num + (D2 - 1);
    }
    return $num + 1 if $num < $m;
    $range -= $m;
    $num -= $m;
  }
}

# Return n m-sided die rolls
sub nDm($$) {
  my @rolls = ();
  my $roll = 0;
  my $n = $_[0];
  my $m = $_[1];
  my $mc = 0;
  my $mm = 1;
  my $i = $maxint / 2;
  return @rolls if $n < 1 || $n >= $maxint || $n != int($n);
  return @rolls if $m < 1 || $m >= ($maxint/2) || $m != int($m);
# Get the maximum number of rolls it is safe to combine
  if ($m == 1) {
    $mc = $n;
  }
  else {
    while ($m < $i) {
      $i /= $m;
      $mc++;
      $mm *= $m;
    }
  }
  while ($n >= $mc) {
    $n -= $mc;
    $roll = Dm($mm) - 1;
    for ($i=0; $i<$mc; $i++) {
      push @rolls, ($roll % $m) + 1;
      $roll = int($roll/$m);
    }
  }
# Don't use exponentiation because there might be rounding problems
  $mm = 1;
  for ($i=0; $i<$n; $i++) {
    $mm *= $m;
  }
  $roll = Dm($mm) - 1;
  for ($i=0; $i<$n; $i++) {
    push @rolls, ($roll % $m) + 1;
    $roll = int($roll/$m);
  }
  return @rolls;
}

# Return n unique m-sided die rolls
sub nUm($$) {
  my @rolls = ();
  my $roll = 0;
  my $n = $_[0];
  my $m = $_[1];
  my $mc = 0;
  my $mm = 1;
  my $mi = 0;
  my %ind = ();
  my $i = $maxint / 2;
  return @rolls if $n < 1 || $n >= $maxint || $n != int($n);
  return @rolls if $m < 1 || $m >= ($maxint/2) || $m != int($m);
  return @rolls if $n > $m;

  while ($n > 0) {
#   Get number of rolls that can be safely combined.
    $mi = $i;
    $mm = 1;
    $mc = 0;
    while (1) {
      last if $mc >= $n || $mi < $m - $mc;
      $mi /= $m - $mc;
      $mm *= $m - $mc;
      $mc++;
    }
#   Make the rolls.
    $n -= $mc;
    $roll = Dm($mm) - 1;
    for (; $mc>0; $mc--,$m--) {
      $mi = ($roll % $m) + 1;
      if (defined($ind{$mi})) {
        push @rolls, $ind{$mi};
      }
      else {
        push @rolls, $mi;
      }
      if ($mi < $m) {
        if (defined($ind{$m})) {
          $ind{$mi} = $ind{$m};
          undef($ind{$m});
        }
        else {
          $ind{$mi} = $m;
        }
      }
      $roll = int($roll/$m);
    }
  }
  return @rolls;
}

# Return a standard 6 sided die roll
sub D6() {
  Dm(6);
}

# Return a list of standard 6 sided die rolls
sub nD6($) {
  nDm($_[0],6);
}

# Return the number of hits in a list of die rolls
sub hits($@) {
  my $i = 0;
  my $j = 1;
  for (; $j<scalar(@_); $j++) {
    $i++ if $_[$j] >= $_[0];
  }
  $i;
}
1;