/*---------------------------------------------------------------------------
  Copyright 2020-2021, Microsoft Research, Daan Leijen.

  This is free software; you can redistribute it and/or modify it under the
  terms of the Apache License, Version 2.0. A copy of the License can be
  found in the LICENSE file at the root of this distribution.
---------------------------------------------------------------------------*/

/* Random numbers.
*/
module std/num/randomstd/num/random

import std/num/int32std/num/int32
import std/num/int64std/num/int64
import std/num/float64std/num/float64

extern import
  js file "random-inline.js"

pubstd/num/random/random: (E, V) -> V effect randomstd/num/random/random: (E, V) -> V
  fun random-int32() : int32std/core/types/int32: V

pub fun @default-random(actionaction: () -> <random,ndet|$466> $465 : () -> <randomstd/num/random/random: (E, V) -> V,ndetstd/core/types/ndet: X|std/core/types/effect-extend: (X, E) -> Eee: E> aa: V)result: -> <ndet|485> 484 : <ndetstd/core/types/ndet: X|std/core/types/effect-extend: (X, E) -> Eee: E> aa: V
  strong-randomstd/num/random/strong-random: (action : () -> <random,ndet|$466> $465) -> <ndet|$466> $465(actionaction: () -> <random,ndet|$466> $465)

// Pick random numbers from a the best strong random source in the OS.
// (e.g. like `/dev/urandom`, `arc4random` etc.). Use `srandom-is-strong` to test if the
// numbers are indeed based on a strong random source.
pub fun strong-randomstd/num/random/strong-random: forall<a,e> (action : () -> <random,ndet|e> a) -> <ndet|e> a(actionaction: () -> <random,ndet|$390> $389 : () -> <randomstd/num/random/random: (E, V) -> V,ndetstd/core/types/ndet: X|std/core/types/effect-extend: (X, E) -> Eee: E> aa: V)result: -> <ndet|458> 457 : <ndetstd/core/types/ndet: X|std/core/types/effect-extend: (X, E) -> Eee: E> aa: V
  withhandler: (() -> <random,ndet|$390> $389) -> <ndet|$390> $389 fun random-int32random-int32: () -> <ndet|$390> int32() srandom-int32std/num/random/srandom-int32: () -> <ndet|$390> int32()
  actionaction: () -> <random,ndet|$390> $389()

// Pseudo random number using sfc32 by Chris Doty-Humphrey.
// It is a "chaotic" pseudo random generator that uses 32-bit operations only
// (so we can be deterministic across architectures in results and performance).
// It has good statistical properties and passes PractRand and Big-crush.
// It uses a 32-bit counter to guarantee a worst-case cycle
// of 2^32. It has a 96-bit state, so the average period is 2^127.
// The chance of a cycle of less than 2^(32+max(96-k,0)) is 2^-(32+k),
// (e.g. the chance of a cycle of less than 2^48 is 2^-80).
// <https://pracrand.sourceforge.net/RNG_engines.txt>
abstract value struct sfcstd/num/random/sfc: V(xresult: -> total int32:int32std/core/types/int32: V, yresult: -> total int32:int32std/core/types/int32: V, zresult: -> total int32:int32std/core/types/int32: V, cntstd/num/random/sfc/cnt: (sfc : sfc) -> int32:int32std/core/types/int32: V)

pub value struct sfc-resultstd/num/random/sfc-result: V( rndstd/num/random/sfc-result/rnd: (sfc-result) -> int32 : int32std/core/types/int32: V, rstatestd/num/random/sfc-result/rstate: (sfc-result) -> sfc : sfcstd/num/random/sfc: V )

pub fun sfc-stepstd/num/random/sfc-step: (sfc : sfc) -> sfc-result( sfcsfc: sfc : sfcstd/num/random/sfc: V )result: -> total sfc-result : sfc-resultstd/num/random/sfc-result: V
  match sfcsfc: sfc
    Sfcstd/num/random/Sfc: (x : int32, y : int32, z : int32, cnt : int32) -> sfc(xx: int32,yy: int32,zz: int32,cntcnt: int32) ->
      val resres: int32 = xx: int32 +std/num/int32/(+): (x : int32, y : int32) -> int32 yy: int32 +std/num/int32/(+): (x : int32, y : int32) -> int32 cntcnt: int32
      Sfc-resultstd/num/random/Sfc-result: (rnd : int32, rstate : sfc) -> sfc-result( resres: int32, Sfcstd/num/random/Sfc: (x : int32, y : int32, z : int32, cnt : int32) -> sfc( yy: int32 ^std/num/int32/(^): (x : int32, y : int32) -> int32 shrstd/num/int32/shr: (i : int32, shift : int) -> int32(yy: int32,9literal: int
dec  = 9
hex8 = 0x09
bit8 = 0b00001001),
                            zz: int32 +std/num/int32/(+): (x : int32, y : int32) -> int32 shlstd/num/int32/shl: (i : int32, shift : int) -> int32(zz: int32,3literal: int
dec  = 3
hex8 = 0x03
bit8 = 0b00000011),
                            rotlstd/num/int32/rotl: (i : int32, shift : int) -> int32(zz: int32,21literal: int
dec  = 21
hex8 = 0x15
bit8 = 0b00010101) +std/num/int32/(+): (x : int32, y : int32) -> int32 resres: int32,
                            cntcnt: int32 +std/num/int32/(+): (x : int32, y : int32) -> int32 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001.int32std/num/int32/int32: (i : int) -> int32 ))

pub fun sfc-init32std/num/random/sfc-init32: (seed1 : int32, seed2 : int32) -> sfc( seed1seed1: int32 : int32std/core/types/int32: V, seed2seed2: int32 : int32std/core/types/int32: V )result: -> total sfc : sfcstd/num/random/sfc: V
  val sfc0sfc0: sfc = Sfcstd/num/random/Sfc: (x : int32, y : int32, z : int32, cnt : int32) -> sfc(0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000.int32std/num/int32/int32: (i : int) -> int32, seed1seed1: int32, seed2seed2: int32, 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001.int32std/num/int32/int32: (i : int) -> int32)
  fold-int32std/num/int32/fold-int32: (n : int32, init : sfc, f : (int32, sfc) -> sfc) -> sfc( 12literal: int
dec  = 12
hex8 = 0x0C
bit8 = 0b00001100.int32std/num/int32/int32: (i : int) -> int32, sfc0sfc0: sfc, fnfn: (int32, s : sfc) -> sfc(_,ss: sfc){ sfc-stepstd/num/random/sfc-step: (sfc : sfc) -> sfc-result(ss: sfc).rstatestd/num/random/sfc-result/rstate: (sfc-result) -> sfc } )  // step 12 times


pub fun sfc-initstd/num/random/sfc-init: (seed : int) -> sfc( seedseed: int : intstd/core/types/int: V )result: -> total sfc : sfcstd/num/random/sfc: V
  sfc-init32std/num/random/sfc-init32: (seed1 : int32, seed2 : int32) -> sfc(seedseed: int.int32std/num/int32/int32: (i : int) -> int32, (seedseed: int /std/core/int/(/): (x : int, y : int) -> int 0x100000000literal: int
dec  = 4294967296
hex64= 0x0000000100000000
bit64= 0b0000000000000000000000000000000100000000000000000000000000000000).int32std/num/int32/int32: (i : int) -> int32)


// Use pseudo random numbers given some initial `seed`. At most
// 64-bits of the initial seed are used. Do not use this for
// cryptographic applications (use `strong-random` instead).
// Uses _sfc32_ by Chris Doty-Humphrey which is a fast random
// number generator with a 128-bit internal state which
// passes PractRand and BigCrush. The worst case minimum cycle
// is 2^^32^^, where a potential cycle of 2^^48^^ has a chance
// of 2^^-80^^.
pub fun pseudo-randomstd/num/random/pseudo-random: forall<a,e> (seed : int, action : () -> <random|e> a) -> e a( seedseed: int : intstd/core/types/int: V, actionaction: () -> <random|$610> $609 : () -> <randomstd/num/random/random: (E, V) -> V|std/core/types/effect-extend: (X, E) -> Eee: E> aa: V)result: -> 829 828 : ee: E aa: V
  var ss: local-var<$619,sfc> := sfc-initstd/num/random/sfc-init: (seed : int) -> <local<$619>|$610> sfc(seedseed: int)
  withhandler: (() -> <random,local<$619>|$610> $609) -> <local<$619>|$610> $609 fun random-int32random-int32: () -> <local<$619>|$610> int32()
    val sfcsfc: sfc-result = sfc-stepstd/num/random/sfc-step: (sfc : sfc) -> <local<$619>|$610> sfc-result(ss: sfc)
    ss: local-var<$619,sfc> :=std/core/types/local-set: (v : local-var<$619,sfc>, assigned : sfc) -> <local<$619>|$610> () sfcsfc: sfc-result.rstatestd/num/random/sfc-result/rstate: (sfc-result) -> <local<$619>|$610> sfc
    sfcsfc: sfc-result.rndstd/num/random/sfc-result/rnd: (sfc-result) -> <local<$619>|$610> int32
  actionaction: () -> <random|$610> $609()


// Return a random boolean
pub fun random-boolstd/num/random/random-bool: () -> random bool()result: -> random bool : randomstd/num/random/random: (E, V) -> V boolstd/core/types/bool: V
  (random-int32std/num/random/random-int32: () -> random int32() >=std/num/int32/(>=): (x : int32, y : int32) -> random bool 0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000.int32std/num/int32/int32: (i : int) -> random int32)

// Return a random integer in the range [-2^^31^^, 2^^31^^).
pub fun random-intstd/num/random/random-int: () -> random int()result: -> random int : randomstd/num/random/random: (E, V) -> V intstd/core/types/int: V
  random-int32std/num/random/random-int32: () -> random int32().intstd/num/int32/int: (i : int32) -> random int

pub fun random-int64std/num/random/random-int64: () -> random int64()result: -> random int64 : randomstd/num/random/random: (E, V) -> V int64std/core/types/int64: V
  int64std/num/int64/hilo32/int64: (hi : int32, lo : int32) -> random int64( random-int32std/num/random/random-int32: () -> random int32(), random-int32std/num/random/random-int32: () -> random int32()) // todo: add native random-int64?

// Return a random float64 in the range [0,1) using 52-bits of randomness
pub fun random-float64std/num/random/random-float64: () -> random float64()result: -> random float64 : randomstd/num/random/random: (E, V) -> V float64std/core/types/float64: V
  val magmag: int64 = random-int64std/num/random/random-int64: () -> random int64().shrstd/num/int64/shr: (i : int64, shift : int) -> random int64(12literal: int
dec  = 12
hex8 = 0x0C
bit8 = 0b00001100).orstd/num/int64/or: (int64, int64) -> random int64(0x3FF0_0000_0000_0000literal: int
dec  = 4607182418800017408
hex64= 0x3FF0000000000000
bit64= 0b0011111111110000000000000000000000000000000000000000000000000000.int64std/num/int64/int64: (i : int) -> random int64)
  (float64-from-bitsstd/num/float64/float64-from-bits: (i : int64) -> random float64(magmag: int64) -std/num/float64/(-): (x : float64, y : float64) -> random float64 1.0literal: float64
hex64= 0x1p0)


// Returns one of its arguments `x`  or `y`  based on a non-deterministic choice.
pub fun choosestd/num/random/choose: forall<a> (x : a, y : a) -> ndet a( xx: $933: aa: V, yy: $933: aa: V)result: -> ndet 948 : ndetstd/core/types/ndet: X aa: V
  if srandom-boolstd/num/random/srandom-bool: () -> ndet bool() then xx: $933 else yy: $933

// Return a strong random boolean
pub fun srandom-boolstd/num/random/srandom-bool: () -> ndet bool()result: -> ndet bool : ndetstd/core/types/ndet: X boolstd/core/types/bool: V
  (srandom-int32std/num/random/srandom-int32: () -> ndet int32() >=std/num/int32/(>=): (x : int32, y : int32) -> ndet bool 0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000.int32std/num/int32/int32: (i : int) -> ndet int32)

// Return a strong random integer in the range [-2^^31^^, 2^^31^^).
pub fun srandom-intstd/num/random/srandom-int: () -> ndet int()result: -> ndet int : ndetstd/core/types/ndet: X intstd/core/types/int: V
  srandom-int32std/num/random/srandom-int32: () -> ndet int32().intstd/num/int32/int: (i : int32) -> ndet int

// Return a strong random `:int32`
pub extern srandom-int32std/num/random/srandom-int32: () -> ndet int32: () -> ndetstd/core/types/ndet: X int32std/core/types/int32: V
  c  inline "(int32_t)kk_srandom_uint32(kk_context())"
  js "_srandom_int32"

// Return a strong random `:float64` in the range [0,1) using 52-bits of randomness
pub extern srandom-float64std/num/random/srandom-float64: () -> ndet float64 : () -> ndetstd/core/types/ndet: X float64std/core/types/float64: V
  c  "kk_srandom_double"
  js "_srandom_double"

// Are the strong random numbers generated from a strong random source? (like /dev/urandom)
pub extern srandom-is-strongstd/num/random/srandom-is-strong: () -> ndet bool: () -> ndetstd/core/types/ndet: X boolstd/core/types/bool: V
  c  "kk_srandom_is_strong"
  js "_srandom_is_strong"

// Return a strong random `:int32` uniformly distributed in the range [lo,hi)
pub extern srandom-int32-rangestd/num/random/srandom-int32-range: (lo : int32, hi : int32) -> ndet int32(lolo: int32 : int32std/core/types/int32: V, hihi: int32 : int32std/core/types/int32: V) : ndetstd/core/types/ndet: X int32std/core/types/int32: V
  c  "kk_srandom_range_int32"
  js "_srandom_range_int32"

// Generate a strong random float64 uniformly distributed in the range [lo, hi)
pub fun srandom-float64-rangestd/num/random/srandom-float64-range: (lo : float64, hi : float64) -> ndet float64(lolo: float64 : float64std/core/types/float64: V, hihi: float64 : float64std/core/types/float64: V)result: -> ndet float64 : ndetstd/core/types/ndet: X float64std/core/types/float64: V
  val lowlow: float64  = if lolo: float64 <=std/num/float64/(<=): (x : float64, y : float64) -> ndet bool hihi: float64 then lolo: float64 else hihi: float64
  val highhigh: float64 = if lolo: float64 <=std/num/float64/(<=): (x : float64, y : float64) -> ndet bool hihi: float64 then hihi: float64 else lolo: float64
  val xx: float64 = ((highhigh: float64 -std/num/float64/(-): (x : float64, y : float64) -> ndet float64 lowlow: float64) *std/num/float64/(*): (x : float64, y : float64) -> ndet float64 srandom-float64std/num/random/srandom-float64: () -> ndet float64()) +std/num/float64/(+): (x : float64, y : float64) -> ndet float64 lowlow: float64
  if xx: float64 >=std/num/float64/(>=): (x : float64, y : float64) -> ndet bool highhigh: float64 then lowlow: float64 else xx: float64  // can happen due to rounding