The seeded error's draw: 32 bits for a seed, a step, a key and an index¶
The seeded error's 32-bit draw for (seed, step, key, index) (the host's seeded error's draw_bits): position_hash(position_hash(step, key, seed), index, seed).
The seed is the engine's, the step the step the draw is for (an end, a turn, lusine.clock.step), the index the draw's number within the step, and the key the stream's name hashed: two keys draw independently from one seed. The key is bits, the FNV-1a 32 of the stream's name over its UTF-8, and a game writes it as its name, key = fnv1a("jack"), which the compiler folds to the constant at build: 777243802 for "jack". Checked against a reference in numpy, which has its own tests.
- Source
- tools/lusine/error.py, draw_bits.
- Proof
- reference, limit, invariant.
draw.trait
namespace lusine.error;
bits draw(bits seed, bits step, bits key, bits index)
{
return position_hash(x = position_hash(x = step, y = key, salt = seed), y = index, salt = seed);
}
Uses, without proving it here: error.position_hash, error.uniform.
Position_hash(position_hash(step, key, seed), index, seed), the host's seeded error's draw_bits. The key is the FNV-1a 32 of the stream's name over its UTF-8, and a game writes it as the name: key = fnv1a("jack"), which the compiler folds to the constant at build, 777243802 for "jack". Host code computes the same key as lusine.error.key("jack") in Python or lusine::error::Key("jack") in C++.
In [1]:
Copied!
import os, sys
root = os.getcwd()
while not os.path.isfile(os.path.join(root, 'docsite.json')):
root = os.path.dirname(root)
sys.path.insert(0, os.path.join(root, 'tools'))
import numpy as np
import matplotlib.pyplot as plt
from lusine import error, trait_run
M32 = 0xFFFFFFFF
EDGES = np.array([0, 1, 2, 0x7FFFFFFF, 0x80000000, 0xFFFFFFFE, M32], dtype=np.uint32)
rng = np.random.default_rng(364)
def random_bits(n):
return np.concatenate([EDGES, rng.integers(0, 2 ** 32, n, dtype=np.uint64).astype(np.uint32)])
def lanes(law, **inputs):
"""A kernel's law over many lanes, two thousand items a program (the host's queue holds a step's stores)."""
n = max(np.size(v) for v in inputs.values())
parts = [law(**{k: (v[i:i + 2000] if np.ndim(v) else v) for k, v in inputs.items()}) for i in range(0, n, 2000)]
return np.concatenate(parts)
def planted(text, n, inputs, outputs):
"""A planted program's outputs: `text` compiled by trait and run on n items, each input loaded, not a host field."""
run = trait_run.Program(['error/finalize.trait'], text, {'probe.items': [n]})
for field, values in inputs.items():
run.store('probe.items', field, values)
return [o[0] for o in run.steps('probe.main', 1, [('probe.items', f) for f in outputs])]
import os, sys
root = os.getcwd()
while not os.path.isfile(os.path.join(root, 'docsite.json')):
root = os.path.dirname(root)
sys.path.insert(0, os.path.join(root, 'tools'))
import numpy as np
import matplotlib.pyplot as plt
from lusine import error, trait_run
M32 = 0xFFFFFFFF
EDGES = np.array([0, 1, 2, 0x7FFFFFFF, 0x80000000, 0xFFFFFFFE, M32], dtype=np.uint32)
rng = np.random.default_rng(364)
def random_bits(n):
return np.concatenate([EDGES, rng.integers(0, 2 ** 32, n, dtype=np.uint64).astype(np.uint32)])
def lanes(law, **inputs):
"""A kernel's law over many lanes, two thousand items a program (the host's queue holds a step's stores)."""
n = max(np.size(v) for v in inputs.values())
parts = [law(**{k: (v[i:i + 2000] if np.ndim(v) else v) for k, v in inputs.items()}) for i in range(0, n, 2000)]
return np.concatenate(parts)
def planted(text, n, inputs, outputs):
"""A planted program's outputs: `text` compiled by trait and run on n items, each input loaded, not a host field."""
run = trait_run.Program(['error/finalize.trait'], text, {'probe.items': [n]})
for field, values in inputs.items():
run.store('probe.items', field, values)
return [o[0] for o in run.steps('probe.main', 1, [('probe.items', f) for f in outputs])]
The kernel¶
The law as the library states it.
In [2]:
Copied!
print(trait_run.source('error/draw.trait'))
print(trait_run.source('error/draw.trait'))
// lusine.error.draw: the seeded error's 32-bit draw for (seed, step, key, index) (the host's seeded error's draw_bits):
// position_hash(position_hash(step, key, seed), index, seed). The seed is the engine's, the step the step the draw is
// for (an end, a turn, lusine.clock.step), the index the draw's number within the step, and the key the stream's
// name hashed: two keys draw independently from one seed. The key is bits, the FNV-1a 32 of the stream's name over its
// UTF-8, and a game writes it as its name, `key = fnv1a("jack")`, which the compiler folds to the constant at build:
// 777243802 for "jack".
// Checked against a reference in numpy, which has its own tests.
namespace lusine.error;
bits draw(bits seed, bits step, bits key, bits index)
{
return position_hash(x = position_hash(x = step, y = key, salt = seed), y = index, salt = seed);
}
The program¶
Each section runs the kernel over a lattice of items, one a draw; the key, given here as many keys at once, is the host's error.key(name), the value fnv1a(name) folds to (the next section).
In [3]:
Copied!
print(trait_run.law_program('error/draw.trait', 'draw'))
def draw(seed, step, key, index):
return lanes(lambda **a: trait_run.law('error/draw.trait', 'draw', **a), seed=seed, step=step, key=key, index=index).astype(np.uint64)
print(f'error.key("jack") = {error.key("jack")}')
print(trait_run.law_program('error/draw.trait', 'draw'))
def draw(seed, step, key, index):
return lanes(lambda **a: trait_run.law('error/draw.trait', 'draw', **a), seed=seed, step=step, key=key, index=index).astype(np.uint64)
print(f'error.key("jack") = {error.key("jack")}')
namespace probe;
lusine.version version = { { number = 1 } };
struct item {
host bits seed;
host bits step;
host bits key;
host bits index;
bits result_0;
};
lattice<item, 1> items(spacing = 1 m, boundary = wall);
void main() { items.result_0 = lusine.error.draw(items.seed, items.step, items.key, items.index); }
error.key("jack") = 777243802
Reference: Boules's jack, and the host's draw_bits bit for bit¶
Boules draws each end's jack in its Trait program as draw_bits(seed, end, "jack", 0) and its uniform. The program below is how it writes that with the library's kernels, the key as its name, key = fnv1a("jack"); over ends 0 to 5 and seven seeds, 0 and 2³² − 1 among them, each uniform is the host's uniform(seed, end, "jack", 0) to the bit. Then twenty thousand draws across the 32-bit range, keys among them in other scripts (café, ボール), each against draw_bits; and a planted program with the step and the key swapped in the first hash, which misses on nearly every draw.
In [4]:
Copied!
JACK = '''namespace probe;
lusine.version version = { { number = 1 } };
struct match_end { bits seed; integer number; float jack; };
lattice<match_end, 1> items(spacing = 1 m, boundary = wall);
// the jack's draw for an end: lusine.error's draw_bits(seed, end, "jack", 0)
float jack(bits seed, integer number)
{
return lusine.error.uniform(drawn = lusine.error.draw(seed, step = bits(number), key = fnv1a("jack"), index = bits(0)));
}
void main() { items.jack = jack(items.seed, items.number); }
'''
print(JACK)
seeds = np.array([0, 1, 7, 42, 20261005, 0x80000000, M32], dtype=np.uint32)
s = np.repeat(seeds, 6)
ends = np.tile(np.arange(6), len(seeds))
u, = planted(JACK, len(s), {'seed': s, 'number': ends}, ['jack'])
want = np.array([error.uniform(int(a), int(b), 'jack', 0) for a, b in zip(s, ends)])
assert np.array_equal(np.asarray(u, dtype=np.float64), want)
print('end ' + ' '.join(f'seed {int(x):>10}' for x in (0, M32)))
for e in range(6):
print(f'{e:3} ' + ' '.join(f'{u[i * 6 + e]:15.9f}' for i in (0, len(seeds) - 1)))
names = ['red', 'blue', 'jack', 'jack/normal', 'café', 'ボール', '']
seed, step, index = random_bits(20000), random_bits(20000), random_bits(20000)
name = [names[i % len(names)] for i in range(len(seed))]
key = np.array([error.key(n) for n in name], dtype=np.uint32)
want = np.array([error.draw_bits(int(a), int(b), n, int(c)) for a, b, n, c in zip(seed, step, name, index)], dtype=np.uint64)
assert np.array_equal(draw(seed, step, key, index), want)
WRONG = '''namespace probe;
lusine.version version = { { number = 1 } };
struct item { bits seed; bits step; bits key; bits index; bits drawn; };
lattice<item, 1> items(spacing = 1 m, boundary = wall);
bits swapped(bits seed, bits step, bits key, bits index)
{
return lusine.error.position_hash(x = lusine.error.position_hash(x = key, y = step, salt = seed), y = index, salt = seed);
}
void main() { items.drawn = swapped(items.seed, items.step, items.key, items.index); }
'''
w, = planted(WRONG, len(seed), {'seed': seed, 'step': step, 'key': key, 'index': index}, ['drawn'])
assert np.mean(w.astype(np.uint64) != want) > 0.99
print(f'{len(seed)} draws: the kernel is error.py\'s draw_bits on every one; the step and key swapped miss on '
f'{np.mean(w.astype(np.uint64) != want):.2%}')
JACK = '''namespace probe;
lusine.version version = { { number = 1 } };
struct match_end { bits seed; integer number; float jack; };
lattice<match_end, 1> items(spacing = 1 m, boundary = wall);
// the jack's draw for an end: lusine.error's draw_bits(seed, end, "jack", 0)
float jack(bits seed, integer number)
{
return lusine.error.uniform(drawn = lusine.error.draw(seed, step = bits(number), key = fnv1a("jack"), index = bits(0)));
}
void main() { items.jack = jack(items.seed, items.number); }
'''
print(JACK)
seeds = np.array([0, 1, 7, 42, 20261005, 0x80000000, M32], dtype=np.uint32)
s = np.repeat(seeds, 6)
ends = np.tile(np.arange(6), len(seeds))
u, = planted(JACK, len(s), {'seed': s, 'number': ends}, ['jack'])
want = np.array([error.uniform(int(a), int(b), 'jack', 0) for a, b in zip(s, ends)])
assert np.array_equal(np.asarray(u, dtype=np.float64), want)
print('end ' + ' '.join(f'seed {int(x):>10}' for x in (0, M32)))
for e in range(6):
print(f'{e:3} ' + ' '.join(f'{u[i * 6 + e]:15.9f}' for i in (0, len(seeds) - 1)))
names = ['red', 'blue', 'jack', 'jack/normal', 'café', 'ボール', '']
seed, step, index = random_bits(20000), random_bits(20000), random_bits(20000)
name = [names[i % len(names)] for i in range(len(seed))]
key = np.array([error.key(n) for n in name], dtype=np.uint32)
want = np.array([error.draw_bits(int(a), int(b), n, int(c)) for a, b, n, c in zip(seed, step, name, index)], dtype=np.uint64)
assert np.array_equal(draw(seed, step, key, index), want)
WRONG = '''namespace probe;
lusine.version version = { { number = 1 } };
struct item { bits seed; bits step; bits key; bits index; bits drawn; };
lattice<item, 1> items(spacing = 1 m, boundary = wall);
bits swapped(bits seed, bits step, bits key, bits index)
{
return lusine.error.position_hash(x = lusine.error.position_hash(x = key, y = step, salt = seed), y = index, salt = seed);
}
void main() { items.drawn = swapped(items.seed, items.step, items.key, items.index); }
'''
w, = planted(WRONG, len(seed), {'seed': seed, 'step': step, 'key': key, 'index': index}, ['drawn'])
assert np.mean(w.astype(np.uint64) != want) > 0.99
print(f'{len(seed)} draws: the kernel is error.py\'s draw_bits on every one; the step and key swapped miss on '
f'{np.mean(w.astype(np.uint64) != want):.2%}')
namespace probe;
lusine.version version = { { number = 1 } };
struct match_end { bits seed; integer number; float jack; };
lattice<match_end, 1> items(spacing = 1 m, boundary = wall);
// the jack's draw for an end: lusine.error's draw_bits(seed, end, "jack", 0)
float jack(bits seed, integer number)
{
return lusine.error.uniform(drawn = lusine.error.draw(seed, step = bits(number), key = fnv1a("jack"), index = bits(0)));
}
void main() { items.jack = jack(items.seed, items.number); }
end seed 0 seed 4294967295
0 0.412395775 0.966166973
1 0.371930182 0.864174485
2 0.627430797 0.821041584
3 0.742371082 0.491955161
4 0.757150948 0.506158888
5 0.594655335 0.704775155
20007 draws: the kernel is error.py's draw_bits on every one; the step and key swapped miss on 100.00%
Reference: a key written as its name, fnv1a("jack")¶
fnv1a("...") over a text literal is bits at build, the FNV-1a 32 of the literal's UTF-8. Each name below is written so in one program, compiled and run; each value it stores is the host's fnv1a(name) (error.key) to the bit, ASCII names and names in other scripts alike (café, ボール, naïve/ñ, an emoji). The same names through C++'s lusine::error::Key are held to these values by their own test. A hash over Latin-1 rather than UTF-8 misses every non-ASCII name.
In [5]:
Copied!
names = ['jack', 'jack/normal', 'red', 'blue', '', 'café', 'ボール', 'naïve/ñ', '🎯']
fields = ''.join(f' bits k{i};' for i in range(len(names)))
sets = ''.join(f'\n update keys set k{i} = fnv1a("{k}");' for i, k in enumerate(names))
HASHED = ('namespace hashed;\nlusine.version version = { { number = 1 } };\n'
f'struct named {{{fields} bool held; }};\ntable<named> keys(capacity = 1) = {{ {{ held = true }} }};\n'
f'void main()\n{{{sets}\n}}\n')
run = trait_run.Program([], HASHED, {})
program = [int(column[0][0]) for column in run.steps('hashed.main', 1, [('hashed.keys', f'k{i}') for i in range(len(names))])]
assert program == [error.key(n) for n in names] == [error.fnv1a(n) for n in names]
latin1 = [error._fnv1a_bytes(n.encode('latin-1', 'replace')) for n in names]
assert [p != w for p, w in zip(program, latin1)] == [not n.isascii() for n in names]
for n, h in zip(names, program):
print(f'fnv1a("{n}")'.ljust(22) + f'{h:>10} = error.key("{n}")')
names = ['jack', 'jack/normal', 'red', 'blue', '', 'café', 'ボール', 'naïve/ñ', '🎯']
fields = ''.join(f' bits k{i};' for i in range(len(names)))
sets = ''.join(f'\n update keys set k{i} = fnv1a("{k}");' for i, k in enumerate(names))
HASHED = ('namespace hashed;\nlusine.version version = { { number = 1 } };\n'
f'struct named {{{fields} bool held; }};\ntable<named> keys(capacity = 1) = {{ {{ held = true }} }};\n'
f'void main()\n{{{sets}\n}}\n')
run = trait_run.Program([], HASHED, {})
program = [int(column[0][0]) for column in run.steps('hashed.main', 1, [('hashed.keys', f'k{i}') for i in range(len(names))])]
assert program == [error.key(n) for n in names] == [error.fnv1a(n) for n in names]
latin1 = [error._fnv1a_bytes(n.encode('latin-1', 'replace')) for n in names]
assert [p != w for p, w in zip(program, latin1)] == [not n.isascii() for n in names]
for n, h in zip(names, program):
print(f'fnv1a("{n}")'.ljust(22) + f'{h:>10} = error.key("{n}")')
fnv1a("jack") 777243802 = error.key("jack")
fnv1a("jack/normal") 68526392 = error.key("jack/normal")
fnv1a("red") 1089765596 = error.key("red")
fnv1a("blue") 2197550541 = error.key("blue")
fnv1a("") 2166136261 = error.key("")
fnv1a("café") 2821410889 = error.key("café")
fnv1a("ボール") 4119396136 = error.key("ボール")
fnv1a("naïve/ñ") 1627000772 = error.key("naïve/ñ")
fnv1a("🎯") 1389841871 = error.key("🎯")
Limit: the edge seeds, and all zeros¶
Seeds 0 and 2³² − 1 with every step, key and index at the edges of the 32-bit range, against the host's seeded error; and the one draw that is 0 by construction, every input 0 (position_hash(0, 0, 0) is 0, twice).
In [6]:
Copied!
grid = np.array([(a, b, c, d) for a in (0, M32) for b in EDGES for c in EDGES for d in (0, 1, M32)], dtype=np.uint32)
got = draw(grid[:, 0], grid[:, 1], grid[:, 2], grid[:, 3])
want = np.array([error.position_hash(error.position_hash(int(b), int(c), int(a)), int(d), int(a)) for a, b, c, d in grid],
dtype=np.uint64)
assert np.array_equal(got, want)
assert int(draw(0, 0, 0, 0)[0]) == 0
print(f'{len(grid)} draws at the edges agree; draw(0, 0, 0, 0) = 0')
grid = np.array([(a, b, c, d) for a in (0, M32) for b in EDGES for c in EDGES for d in (0, 1, M32)], dtype=np.uint32)
got = draw(grid[:, 0], grid[:, 1], grid[:, 2], grid[:, 3])
want = np.array([error.position_hash(error.position_hash(int(b), int(c), int(a)), int(d), int(a)) for a, b, c, d in grid],
dtype=np.uint64)
assert np.array_equal(got, want)
assert int(draw(0, 0, 0, 0)[0]) == 0
print(f'{len(grid)} draws at the edges agree; draw(0, 0, 0, 0) = 0')
294 draws at the edges agree; draw(0, 0, 0, 0) = 0
Invariant: the same inputs, the same draw; two keys, two streams¶
A draw is a function of its four inputs alone: a second program run on the same inputs gives the same bits. Two players keyed "red" and "blue" draw from one seed at every step without sharing a draw, and the indices within a step give distinct draws.
In [7]:
Copied!
seed, step = random_bits(5000), random_bits(5000)
n = len(seed)
zero = np.zeros(n, dtype=np.uint32)
red = draw(seed, step, np.full(n, error.key('red'), dtype=np.uint32), zero)
again = draw(seed, step, np.full(n, error.key('red'), dtype=np.uint32), zero)
blue = draw(seed, step, np.full(n, error.key('blue'), dtype=np.uint32), zero)
assert np.array_equal(red, again) and not np.any(red == blue)
idx = draw(np.full(64, 42, dtype=np.uint32), np.full(64, 7, dtype=np.uint32), np.full(64, error.key('red'), dtype=np.uint32),
np.arange(64, dtype=np.uint32))
assert len(set(idx.tolist())) == 64
print(f'{n} seeds and steps: red twice the same, red and blue never equal; 64 indices, 64 distinct draws')
seed, step = random_bits(5000), random_bits(5000)
n = len(seed)
zero = np.zeros(n, dtype=np.uint32)
red = draw(seed, step, np.full(n, error.key('red'), dtype=np.uint32), zero)
again = draw(seed, step, np.full(n, error.key('red'), dtype=np.uint32), zero)
blue = draw(seed, step, np.full(n, error.key('blue'), dtype=np.uint32), zero)
assert np.array_equal(red, again) and not np.any(red == blue)
idx = draw(np.full(64, 42, dtype=np.uint32), np.full(64, 7, dtype=np.uint32), np.full(64, error.key('red'), dtype=np.uint32),
np.arange(64, dtype=np.uint32))
assert len(set(idx.tolist())) == 64
print(f'{n} seeds and steps: red twice the same, red and blue never equal; 64 indices, 64 distinct draws')
5007 seeds and steps: red twice the same, red and blue never equal; 64 indices, 64 distinct draws