All files / random / _pcg32.ts

100.00% Branches 10/10
100.00% Lines 88/88
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
 
 
x15
x15
 
 
x15
x15
 
x15
 
 
 
 
 
 
 
x15
x10181
x10181
x10181
 
x10181
x10181
x30876
x30876
 
x10181
x10215
x10215
x10269
x10269
x10215
 
x10181
x10187
x10187
x10187
x10187
x10187
x10247
x10247
x10247
x10187
 
x10181
x10181
x15
 
 
 
 
 
 
 
x15
 
 
x15
 
 
x30
 
x30
 
x15
 
x15
x15
x207288
x207288
x15
x52101
x52101
x15
x51948
x51948
x15
 
 
 
x168
x168
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
x15
x226
x284
x284
 
x379
x379
x379
x226
 
 
x15
 
x51795
x51795
x51795
x51795
 
x51795
x51795
x51795
 
 
x15
x51948
x51948
x51948
 
 
x15
x51795
x51795
x51795
x51795
 
x15
x73
x73
 
 
 
 
x15
x73
x73
x73
x73
 
x73
 
 
 
 
x15
 
x292
x73
x15




























































































































































// Copyright 2018-2025 the Deno authors. MIT license.
// Based on Rust `rand` crate (https://github.com/rust-random/rand). Apache-2.0 + MIT license.

import { platform } from "./_platform.ts";
import { seedBytesFromUint64 } from "./_seed_bytes_from_uint64.ts";
import type { IntegerTypedArray } from "./_types.ts";

const b4 = new Uint8Array(4);
const dv4 = new DataView(b4.buffer);

abstract class Prng32 {
  /** Generates a pseudo-random 32-bit unsigned integer. */
  abstract nextUint32(): number;

  /**
   * Mutates the provided typed array with pseudo-random values.
   * @returns The same typed array, now populated with random values.
   */
  getRandomValues<T extends IntegerTypedArray>(arr: T): T {
    const { buffer, byteLength, byteOffset } = arr;
    const rem = byteLength % 4;
    const cutoffLen = byteLength - rem;

    const dv = new DataView(buffer, byteOffset, byteLength);
    for (let i = 0; i < cutoffLen; i += 4) {
      dv.setUint32(i, this.nextUint32(), true);
    }

    if (rem !== 0) {
      dv4.setUint32(0, this.nextUint32(), true);
      for (let i = 0; i < rem; ++i) {
        dv.setUint8(cutoffLen + i, b4[i]!);
      }
    }

    if (arr.BYTES_PER_ELEMENT !== 1 && !platform.littleEndian) {
      const bits = arr.BYTES_PER_ELEMENT * 8;
      const name = bits > 32
        ? `BigUint${bits as 64}` as const
        : `Uint${bits as 16 | 32}` as const;
      for (let i = 0; i < arr.length; ++i) {
        const idx = i * arr.BYTES_PER_ELEMENT;
        dv[`set${name}`](idx, dv[`get${name}`](idx, true) as never, false);
      }
    }

    return arr;
  }
}

/**
 * Internal PCG32 implementation, used by both the public seeded random
 * function and the seed generation algorithm.
 *
 * Modified from https://github.com/rust-random/rand/blob/f7bbcca/rand_pcg/src/pcg64.rs#L140-L153
 */
export class Pcg32 extends Prng32 {
  /** Multiplier for the PCG32 algorithm. */
  // deno-lint-ignore deno-style-guide/naming-convention
  static readonly MULTIPLIER = 6364136223846793005n;
  // Constants are for 64-bit state, 32-bit output
  // deno-lint-ignore deno-style-guide/naming-convention
  static readonly ROTATE = 59n; // 64 - 5
  // deno-lint-ignore deno-style-guide/naming-convention
  static readonly XSHIFT = 18n; // (5 + 32) / 2
  // deno-lint-ignore deno-style-guide/naming-convention
  static readonly SPARE = 27n; // 64 - 32 - 5

  #state = new BigUint64Array(2);
  get state() {
    return this.#state[0]!;
  }
  protected set state(val) {
    this.#state[0] = val;
  }
  get increment() {
    return this.#state[1]!;
  }
  protected set increment(val) {
    // https://www.pcg-random.org/posts/critiquing-pcg-streams.html#changing-the-increment
    // > Increments have just one rule: they must be odd.
    // We OR the increment with 1 upon setting to ensure this.
    this.#state[1] = val | 1n;
  }

  /**
   * Creates a new `Pcg32` instance with entropy generated from the seed.
   * @param seed A 64-bit unsigned integer used to seed the generator.
   */
  constructor(seed: bigint);
  /**
   * Creates a new `Pcg32` instance with the given `state` and `increment` values.
   * @param state The current state of the generator.
   * @param increment The increment value used in the generator.
   *
   * > [!NOTE]
   * > It is typically better to use the constructor that takes a single `seed` value.
   * > However, this constructor can be useful for resuming from a saved state.
   */
  constructor({ state, increment }: { state: bigint; increment: bigint });
  constructor(arg: bigint | { state: bigint; increment: bigint }) {
    if (typeof arg === "bigint") {
      return Pcg32.#seedFromUint64(arg);
    }

    super();
    this.state = arg.state;
    this.increment = arg.increment;
  }

  /** @returns The next pseudo-random 32-bit integer. */
  nextUint32(): number {
    // Output function XSH RR: xorshift high (bits), followed by a random rotate
    const rot = this.state >> Pcg32.ROTATE;
    const xsh = BigInt.asUintN(
      32,
      (this.state >> Pcg32.XSHIFT ^ this.state) >> Pcg32.SPARE,
    );
    this.step();
    return Number(this.#rotateRightUint32(xsh, rot));
  }

  /** Mutates `pcg` by advancing `pcg.state`. */
  step(): this {
    this.state = this.state * Pcg32.MULTIPLIER + this.increment;
    return this;
  }

  // `n`, `rot`, and return val are all u32
  #rotateRightUint32(n: bigint, rot: bigint): bigint {
    const left = BigInt.asUintN(32, n << (-rot & 31n));
    const right = n >> rot;
    return left | right;
  }

  static #seedFromUint64(seed: bigint): Pcg32 {
    return this.#fromSeed(seedBytesFromUint64(seed, new Uint8Array(16)));
  }

  /**
   * Modified from https://github.com/rust-random/rand/blob/f7bbcca/rand_pcg/src/pcg64.rs#L129-L135
   */
  static #fromSeed(seed: Uint8Array) {
    const d = new DataView(seed.buffer);
    return this.#fromStateIncr(
      d.getBigUint64(0, true),
      d.getBigUint64(8, true) | 1n,
    );
  }

  /**
   * Modified from https://github.com/rust-random/rand/blob/f7bbcca/rand_pcg/src/pcg64.rs#L99-L105
   */
  static #fromStateIncr(state: bigint, increment: bigint): Pcg32 {
    // Move state away from initial value
    return new Pcg32({ state: state + increment, increment }).step();
  }
}