Last active
February 27, 2025 14:20
-
-
Save ziap/810678f6c11163bddf334183b75feffb to your computer and use it in GitHub Desktop.
Algorithm for initializing large RNGs from strings and other low-entropy sources
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const std = @import("std"); | |
| const seeder = @import("seeder.zig"); | |
| const Xoshiro256 = struct { | |
| s: [4]u64, | |
| pub fn next(self: *Xoshiro256) u64 { | |
| const S = struct { | |
| inline fn rotl(data: u64, rot: u6) u64 { | |
| return (data << rot) | (data >> -% rot); | |
| } | |
| }; | |
| const r = S.rotl(self.s[0] +% self.s[3], 23) +% self.s[0]; | |
| const t = self.s[1] << 17; | |
| self.s[2] ^= self.s[0]; | |
| self.s[3] ^= self.s[1]; | |
| self.s[1] ^= self.s[2]; | |
| self.s[0] ^= self.s[3]; | |
| self.s[2] ^= t; | |
| self.s[3] = S.rotl(self.s[3], 45); | |
| return r; | |
| } | |
| }; | |
| pub fn main() !void { | |
| const stdout_file = std.io.getStdOut().writer(); | |
| var bw = std.io.bufferedWriter(stdout_file); | |
| defer bw.flush() catch {}; | |
| const stdout = bw.writer(); | |
| var rng: Xoshiro256 = .{ | |
| .s = seeder.fromStr(4, "the quick brown fox jumps over the lazy dog") | |
| }; | |
| for (0..20) |_| { | |
| stdout.print("{x}\n", .{ rng.next() }) catch return; | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| fn mixSeeds(comptime N: comptime_int, seeds: *[N]u64) void { | |
| const S = struct { | |
| fn multiplyMix(x: u64, y: u64) u64 { | |
| const m = @as(u128, x) *% @as(u128, y); | |
| const hi: u64 = @intCast(m >> 64); | |
| const lo: u64 = @truncate(m); | |
| return lo ^ hi; | |
| } | |
| const MUL = 0xdb36357734e34abb0050d0761fcdfc15; | |
| const INC = 0x5851f42d4c957f2d14057b7ef767814f; | |
| const Rng = struct { | |
| state: u128, | |
| fn next(self: *Rng) u64 { | |
| const s = self.state; | |
| self.state = s *% MUL +% INC; | |
| const word = (s ^ (s >> ((s >> 122) + 6))) *% MUL; | |
| const xorshifted: u64 = @truncate((word ^ (word >> 35)) >> 58); | |
| const rot: u6 = @intCast(word >> 122); | |
| return (xorshifted >> rot) | (xorshifted << -%rot); | |
| } | |
| }; | |
| }; | |
| comptime var rng: S.Rng = .{ .state = S.INC }; | |
| inline for (seeds) |*seed| { | |
| const h = seed.* ^ comptime rng.next(); | |
| seed.* = S.multiplyMix(h, comptime rng.next()); | |
| } | |
| inline for (seeds, 0..) |seed, idx| { | |
| inline for (idx + 1..idx + N) |next| { | |
| const other = comptime next % N; | |
| const s0 = seed ^ comptime rng.next(); | |
| const s1 = seeds[other] ^ comptime rng.next(); | |
| seeds[other] = S.multiplyMix(s0, s1); | |
| } | |
| } | |
| } | |
| pub fn fromStr(comptime N: comptime_int, data: []const u8) [N]u64 { | |
| const Chunk = @Vector(N, u64); | |
| var seeds: Chunk = @splat(0); | |
| const mul: Chunk = @splat(0xf1357aea2e62a9c5); | |
| const is_le = comptime blk: { | |
| const native_endian = @import("builtin").cpu.arch.endian(); | |
| break :blk native_endian == .little; | |
| }; | |
| const chunk_size = @sizeOf(Chunk); | |
| var view = data; | |
| while (view.len >= chunk_size) : (view = view[chunk_size..]) { | |
| var chunk: Chunk = undefined; | |
| const chunk_ptr: *[chunk_size]u8 = @ptrCast(&chunk); | |
| @memcpy(chunk_ptr, view[0..chunk_size]); | |
| if (!is_le) chunk = @byteSwap(chunk); | |
| seeds = (seeds +% chunk) *% mul; | |
| } | |
| if (view.len > 0) { | |
| var chunk: Chunk = @splat(0); | |
| const chunk_ptr: [*]u8 = @ptrCast(&chunk); | |
| @memcpy(chunk_ptr, view); | |
| if (!is_le) chunk = @byteSwap(chunk); | |
| seeds = (seeds +% chunk) *% mul; | |
| } | |
| mixSeeds(N, &seeds); | |
| return seeds; | |
| } | |
| pub fn fromSeeds(comptime N: comptime_int, data: []const u64) [N]u64 { | |
| var buffer: [N]u64 = .{ 0 } ** N; | |
| @memcpy(buffer[0..data.len], data); | |
| mixSeeds(N, &buffer); | |
| return buffer; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment