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 (

  # the handler this effect uses to create random numbers
  p Random_Handler
  ) : 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.
  #
  next =>
    res := random p.next
    res.replace
    res


  # 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.get 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.get 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.get 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.get exclusive_bound


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


  # 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 =>
    p.get %% 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
  =>
    p.get % exclusive_bound  # NYI: This implementation is bad if exclusive_bound is big


  # install default instance of random
  #
  type.install_default =>
    if !random.is_instated
      (random simple_random_handler.default).default


# random with no argument returns random.env, i.e., the currently installed
# source of randomness.
#
public random random =>
  random.install_default
  random.env

public simple_random(seed u64, rr ()->unit) unit =>
  random <- (random (simple_random_handler seed seed)) ! rr

public time_seeded_random(rr ()->unit) unit =>
  random <- (random simple_random_handler.time_seeded) ! rr


# Random_Handler -- abstract source of random numbers
#
# This provides the random number input to be used by the 'random' effect.
# Implementation may be dumb sequences of pseudo-random numbers or high-quality
# cryptographic random number generators
#
# A Random_Handler contains an immutable state, repeated calls to 'get' result
# in the same value.  To produce a sequence of different random numbers, 'next'
# must be used to create a new instance of 'Random_Handler' before 'get' can be
# used to obtain the new random number.
#
public Random_Handler ref is

  # create a new instance of Random_Handler containing a new state. Depending
  # on the quality of this random number generator, this might be a simple
  # function of the original Random_Handler or it might use an external source
  # of entropy to create a new instance.
  #
  public next Random_Handler => abstract

  # Return the random number stored in this instance of Random_Handler, in the
  # range 0..u64.max
  #
  # NOTE: this feature is pure, i.e., repeated calls on the same target result
  # in equal results.  Use 'next' to get different results.
  #
  public get u64 => abstract



# simple random number handler 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_handler(seed1 u64, seed2 u64) : Random_Handler is

  # get next instance by shuffling bits in seeds around
  #
  public redef next Random_Handler =>
    # 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_handler (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 =>
    match envir.vars.get random_seed_env_var
     s String =>
       match s.parse_u64
         seed u64 => simple_random_handler 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_Handler =>
    # initialize with large numbers XORed with nano time
    #
    simple_random_handler (u64 77777777777777 ^ fzE_nanotime) 98765432109876543


  # create a time-seeded 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(rr ()->unit) =>
    random <- (random time_seeded) ! rr