Random.fz

# This file is part of the Fuzion language implementation.
#
# The Fuzion language implementation is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License as published
# by the Free Software Foundation, version 3 of the License.
#
# The Fuzion language implementation is distributed in the hope that it will be
# useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
# License for more details.
#
# You should have received a copy of the GNU General Public License along with The
# Fuzion language implementation.  If not, see <https://www.gnu.org/licenses/>.


# -----------------------------------------------------------------------
#
#  Tokiwa Software GmbH, Germany
#
#  Source code of Fuzion standard library feature random
#
#  Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------

# random -- effect that provides random numbers
#
public Random ref : effect
is

  # for a random instance installed in the current environment, update the
  # environment to the next random value.  The the contents of the current
  # instance are left unchanged, 'Random.env' will provide the new instance.
  #
  public next Random => abstract


  # get current random number
  #
  public get u64 => abstract


  # return next random number of type i32 in the range 0..exclusive_bound-1
  #
  public next_i32(exclusive_bound i32) i32
    pre debug: exclusive_bound ? 0
  =>
    next exclusive_bound.as_u64 .as_i32


  # return next random number of type i32 in the full range of i32 (i32.min..i32.max)
  #
  public next_i32 i32 =>
    next_u32.cast_to_i32


  # return next random number of type i64 in the range 0..exclusive_bound-1
  #
  # Note: uniform distribution is not perfect, it gets worse the closer exclusive_bound gets to 2^64, because internal calculation uses modulo
  #
  public next_i64(exclusive_bound i64) i64
    pre debug: exclusive_bound ? 0
  =>
    next exclusive_bound.as_u64 .as_i64


  # return next random number of type i64 in the full range of i64 (i64.min..i64.max)
  #
  public next_i64 i64 =>
    next_u64.cast_to_i64


  # return next random number of type u32 in the range 0..exclusive_bound-1
  #
  public next_u32(exclusive_bound u32) u32 =>
    next exclusive_bound.as_u64 .as_u32


  # return next random number of type u32 in the full range of u32 (0..u32.max)
  #
  public next_u32 u32 =>
    (next_u64 & 0x0000_0000_ffff_ffff).as_u32


  # return next random number of type u64 in the range 0..exclusive_bound-1
  #
  # Note: uniform distribution is not perfect, it gets worse the closer exclusive_bound gets to 2^64, because internal calculation uses modulo
  #
  public next_u64(exclusive_bound u64) u64 =>
    next exclusive_bound


  # return next random number of type u64 in the full range of u64 (0..u64.max)
  #
  public next_u64 u64 =>
    x := next
    Random.replace x
    x.get


  next(exclusive_bound u64) =>
    next_u64 % exclusive_bound


  # return next random number of type f32 in the range [0..1),
  # result will never be equal to f32 1
  #
  public next_f32 f32 =>
    max := u64 1 << f32.significand_bits.as_u64
    (next_u64 max).as_f64.as_f32 / max.as_f64.as_f32


  # return next random number of type f64 in the range [0..1),
  # result will never be equal to f64 1
  #
  public next_f64 f64 =>
    max := u64 1 << f64.significand_bits.as_u64
    (next_u64 max).as_f64 / max.as_f64


  # return next random number as a bool
  #
  public next_bool bool =>
    next_u64 %% 2


  # get the current random number in the range 0..exclusive_bound-1
  #
  # Note: uniform distribution is not perfect, it gets worse the closer exclusive_bound gets to 2^64, because internal calculation uses modulo
  #
  public get (exclusive_bound u64) u64
  =>
    get % exclusive_bound  # NYI: This implementation is bad if exclusive_bound is big


  # default implementation of random
  #
  # this will get instated automatically at startup
  #
  public redef fixed type.default_value option Random =>
    simple_random.default


  # instate a random that is seed seeded and run rr in its context
  #
  public type.simple(T type, seed u64, rr ()->T) T =>
    Random.instate (simple_random seed seed) rr


  # instate a random that is time seeded and run rr in its context
  #
  public type.time_seeded(T type, rr ()->T) T ! time.Nano =>
    Random.instate simple_random.time_seeded rr


# simple random number for pseudo random numbers that are not safe
# for security and that do not meet typical requirements for a good
# random number generator.
#
simple_random(seed1 u64, seed2 u64) : Random is

  # get next instance by shuffling bits in seeds around
  #
  public redef next Random =>
    # NYI: This does not meet any requirements on a decent random number generator
    s1 := (seed1 *? 1717171717 +? 13113131313) ^ seed2
    s2 := (seed2 *? 9191919191 +? 37637373737) ^ seed1
    rot1 := s2 & 0x3f
    rot2 := s1 & 0x3f
    simple_random (s2<<rot2 | s2>>(u64 64 - rot2))
                  (s1<<rot1 | s1>>(u64 64 - rot1))

  # get current random number
  #
  public redef get u64 => seed1


  # name of env var to provide default random seed.
  #
  # If set, this u64-value will be used too seed the default random number generator.
  # If not set, the default random number generator will be time seeded.
  #
  # If set to unparsable number, panic on installation of the default random
  # number generator.
  #
  type.random_seed_env_var => "FUZION_RANDOM_SEED"


  # create the default random handler depending on the environment settings
  #
  type.default =>
    # NYI: BUG: should be : match envir.Vars.env[random_seed_env_var]
    # but we need to be able to define order of default effects for this to work
    #
    match envir.Vars.default_value.or_panic.get random_seed_env_var
     s String =>
       match s.parse_u64
         seed u64 => simple_random seed 98765432109876543
         e error  => panic "Failed to parse value in env var '$random_seed_env_var': $e"
     nil      => time_seeded


  # create a time-seeded simple handler for pseudo random numbers that are not safe
  # for security and that do not meet typical requirements for a good
  # random number generator.
  #
  type.time_seeded Random ! time.Nano =>
    # initialize with large numbers XORed with nano time
    #
    # NYI: BUG: we need ordering of default effects
    # simple_random (u64 77777777777777 ^ time.Nano.env.read.val) 98765432109876543
    simple_random (u64 77777777777777 ^ (fzE_posix_time (id posix.clockid_t posix.clock_monotonic).val)) 98765432109876543