1//! ISAAC64 - http://www.burtleburtle.net/bob/rand/isaacafa.html
2//!
3//! Follows the general idea of the implementation from here with a few shortcuts.
4//! https://doc.rust-lang.org/rand/src/rand/prng/isaac64.rs.html
5
6const std = @import("std");
7const mem = std.mem;
8const Isaac64 = @This();
9
10r: [256]u64,
11m: [256]u64,
12a: u64,
13b: u64,
14c: u64,
15i: usize,
16
17pub fn init(init_s: u64) Isaac64 {
18 var isaac = Isaac64{
19 .r = undefined,
20 .m = undefined,
21 .a = undefined,
22 .b = undefined,
23 .c = undefined,
24 .i = undefined,
25 };
26
27 // seed == 0 => same result as the unseeded reference implementation
28 isaac.seed(init_s, 1);
29 return isaac;
30}
31
32pub fn random(self: *Isaac64) std.Random {
33 return std.Random.init(self, fill);
34}
35
36fn step(self: *Isaac64, mix: u64, base: usize, comptime m1: usize, comptime m2: usize) void {
37 const x = self.m[base + m1];
38 self.a = mix +% self.m[base + m2];
39
40 const y = self.a +% self.b +% self.m[@as(usize, @intCast((x >> 3) % self.m.len))];
41 self.m[base + m1] = y;
42
43 self.b = x +% self.m[@as(usize, @intCast((y >> 11) % self.m.len))];
44 self.r[self.r.len - 1 - base - m1] = self.b;
45}
46
47fn refill(self: *Isaac64) void {
48 const midpoint = self.r.len / 2;
49
50 self.c +%= 1;
51 self.b +%= self.c;
52
53 {
54 var i: usize = 0;
55 while (i < midpoint) : (i += 4) {
56 self.step(~(self.a ^ (self.a << 21)), i + 0, 0, midpoint);
57 self.step(self.a ^ (self.a >> 5), i + 1, 0, midpoint);
58 self.step(self.a ^ (self.a << 12), i + 2, 0, midpoint);
59 self.step(self.a ^ (self.a >> 33), i + 3, 0, midpoint);
60 }
61 }
62
63 {
64 var i: usize = 0;
65 while (i < midpoint) : (i += 4) {
66 self.step(~(self.a ^ (self.a << 21)), i + 0, midpoint, 0);
67 self.step(self.a ^ (self.a >> 5), i + 1, midpoint, 0);
68 self.step(self.a ^ (self.a << 12), i + 2, midpoint, 0);
69 self.step(self.a ^ (self.a >> 33), i + 3, midpoint, 0);
70 }
71 }
72
73 self.i = 0;
74}
75
76fn next(self: *Isaac64) u64 {
77 if (self.i >= self.r.len) {
78 self.refill();
79 }
80
81 const value = self.r[self.i];
82 self.i += 1;
83 return value;
84}
85
86fn seed(self: *Isaac64, init_s: u64, comptime rounds: usize) void {
87 // We ignore the multi-pass requirement since we don't currently expose full access to
88 // seeding the self.m array completely.
89 @memset(self.m[0..], 0);
90 self.m[0] = init_s;
91
92 // prescrambled golden ratio constants
93 var a = [_]u64{
94 0x647c4677a2884b7c,
95 0xb9f8b322c73ac862,
96 0x8c0ea5053d4712a0,
97 0xb29b2e824a595524,
98 0x82f053db8355e0ce,
99 0x48fe4a0fa5a09315,
100 0xae985bf2cbfc89ed,
101 0x98f5704f6c44c0ab,
102 };
103
104 comptime var i: usize = 0;
105 inline while (i < rounds) : (i += 1) {
106 var j: usize = 0;
107 while (j < self.m.len) : (j += 8) {
108 comptime var x1: usize = 0;
109 inline while (x1 < 8) : (x1 += 1) {
110 a[x1] +%= self.m[j + x1];
111 }
112
113 a[0] -%= a[4];
114 a[5] ^= a[7] >> 9;
115 a[7] +%= a[0];
116 a[1] -%= a[5];
117 a[6] ^= a[0] << 9;
118 a[0] +%= a[1];
119 a[2] -%= a[6];
120 a[7] ^= a[1] >> 23;
121 a[1] +%= a[2];
122 a[3] -%= a[7];
123 a[0] ^= a[2] << 15;
124 a[2] +%= a[3];
125 a[4] -%= a[0];
126 a[1] ^= a[3] >> 14;
127 a[3] +%= a[4];
128 a[5] -%= a[1];
129 a[2] ^= a[4] << 20;
130 a[4] +%= a[5];
131 a[6] -%= a[2];
132 a[3] ^= a[5] >> 17;
133 a[5] +%= a[6];
134 a[7] -%= a[3];
135 a[4] ^= a[6] << 14;
136 a[6] +%= a[7];
137
138 comptime var x2: usize = 0;
139 inline while (x2 < 8) : (x2 += 1) {
140 self.m[j + x2] = a[x2];
141 }
142 }
143 }
144
145 @memset(self.r[0..], 0);
146 self.a = 0;
147 self.b = 0;
148 self.c = 0;
149 self.i = self.r.len; // trigger refill on first value
150}
151
152pub fn fill(self: *Isaac64, buf: []u8) void {
153 var i: usize = 0;
154 const aligned_len = buf.len - (buf.len & 7);
155
156 // Fill complete 64-byte segments
157 while (i < aligned_len) : (i += 8) {
158 var n = self.next();
159 comptime var j: usize = 0;
160 inline while (j < 8) : (j += 1) {
161 buf[i + j] = @as(u8, @truncate(n));
162 n >>= 8;
163 }
164 }
165
166 // Fill trailing, ignoring excess (cut the stream).
167 if (i != buf.len) {
168 var n = self.next();
169 while (i < buf.len) : (i += 1) {
170 buf[i] = @as(u8, @truncate(n));
171 n >>= 8;
172 }
173 }
174}
175
176test "sequence" {
177 var r = Isaac64.init(0);
178
179 // from reference implementation
180 const seq = [_]u64{
181 0xf67dfba498e4937c,
182 0x84a5066a9204f380,
183 0xfee34bd5f5514dbb,
184 0x4d1664739b8f80d6,
185 0x8607459ab52a14aa,
186 0x0e78bc5a98529e49,
187 0xfe5332822ad13777,
188 0x556c27525e33d01a,
189 0x08643ca615f3149f,
190 0xd0771faf3cb04714,
191 0x30e86f68a37b008d,
192 0x3074ebc0488a3adf,
193 0x270645ea7a2790bc,
194 0x5601a0a8d3763c6a,
195 0x2f83071f53f325dd,
196 0xb9090f3d42d2d2ea,
197 };
198
199 for (seq) |s| {
200 try std.testing.expect(s == r.next());
201 }
202}
203
204test fill {
205 var r = Isaac64.init(0);
206
207 // from reference implementation
208 const seq = [_]u64{
209 0xf67dfba498e4937c,
210 0x84a5066a9204f380,
211 0xfee34bd5f5514dbb,
212 0x4d1664739b8f80d6,
213 0x8607459ab52a14aa,
214 0x0e78bc5a98529e49,
215 0xfe5332822ad13777,
216 0x556c27525e33d01a,
217 0x08643ca615f3149f,
218 0xd0771faf3cb04714,
219 0x30e86f68a37b008d,
220 0x3074ebc0488a3adf,
221 0x270645ea7a2790bc,
222 0x5601a0a8d3763c6a,
223 0x2f83071f53f325dd,
224 0xb9090f3d42d2d2ea,
225 };
226
227 for (seq) |s| {
228 var buf0: [8]u8 = undefined;
229 var buf1: [7]u8 = undefined;
230 std.mem.writeInt(u64, &buf0, s, .little);
231 r.fill(&buf1);
232 try std.testing.expect(std.mem.eql(u8, buf0[0..7], buf1[0..]));
233 }
234}