The seeded error's finalizer: 32 bits mixed, the host's bit for bit¶

The seeded error's finalizer (the host's seeded error's hash_finalize, and fallingsand's hashFinalize): an xor-shift, a multiply and an xor-shift on 32 bits, so every input bit reaches every output bit.

The multiplier and the shifts are the hash's own numbers, as the host's seeded error states them. Checked against a reference in numpy, which has its own tests.

Source

tools/lusine/error.py, hash_finalize; fallingsand core/hash.glsl.

Proof

reference, limit, invariant.

finalize.trait

namespace lusine.error;

bits finalize(bits h)
{
  let a = (h ^ (h >> 13)) * bits(1274126177);
  return a ^ (a >> 16);
}

An xor-shift by 13, a multiply by 1274126177 and an xor-shift by 16, each on 32 bits and wrapped, which is the host's seeded error's hash_finalize (and fallingsand's hashFinalize).

In [1]:

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]:

print(trait_run.source('error/finalize.trait'))

print(trait_run.source('error/finalize.trait'))

// lusine.error.finalize: the seeded error's finalizer (the host's seeded error's hash_finalize, and fallingsand's
// hashFinalize): an xor-shift, a multiply and an xor-shift on 32 bits, so every input bit reaches
// every output bit. The multiplier and the shifts are the hash's own numbers, as the host's seeded error states them.
// Checked against a reference in numpy, which has its own tests.

namespace lusine.error;

bits finalize(bits h)
{
  let a = (h ^ (h >> 13)) * bits;
  return a ^ (a >> 16);
}

The program¶

Each section runs the kernel over a lattice of items, one an input: the host stores the 32 bits, and main() binds the kernel over the items, two thousand items a run.

In [3]:

print(trait_run.law_program('error/finalize.trait', 'finalize'))

def finalize(h):
    return lanes(lambda **a: trait_run.law('error/finalize.trait', 'finalize', **a), h=h).astype(np.uint64)

print(trait_run.law_program('error/finalize.trait', 'finalize')) def finalize(h): return lanes(lambda **a: trait_run.law('error/finalize.trait', 'finalize', **a), h=h).astype(np.uint64)

namespace probe;

lusine.version version = { { number = 1 } };

struct item {
  host bits h;
  bits result_0;
};
lattice<item, 1> items(spacing = 1 m, boundary = wall);

void main() { items.result_0 = lusine.error.finalize(items.h); }

Reference: the host's hash_finalize, bit for bit, and two planted faults caught¶

Twenty thousand inputs across the whole 32-bit range, the edges among them: the emitted kernel against the host's hash_finalize, every bit. Two programs plant a fault each, compiled and run the same way: the multiplier one off and the first shift one off (12). Each misses the host's on nearly every input, so the agreement above is no accident of the inputs.

In [4]:

x = random_bits(20000)
want = np.array([error.hash_finalize(int(v)) for v in x], dtype=np.uint64)
assert np.array_equal(finalize(x), want)
WRONG = '''namespace probe;

lusine.version version = { { number = 1 } };

struct item { bits h; bits multiplier; bits shift; };
lattice<item, 1> items(spacing = 1 m, boundary = wall);

bits multiplier_off(bits h) { let a = (h ^ (h >> 13)) * bits; return a ^ (a >> 16); }
bits shift_off(bits h) { let a = (h ^ (h >> 12)) * bits; return a ^ (a >> 16); }

void main() { items.multiplier = multiplier_off(items.h); items.shift = shift_off(items.h); }
'''
m, s = planted(WRONG, len(x), {'h': x}, ['multiplier', 'shift'])
assert np.mean(m.astype(np.uint64) != want) > 0.99 and np.mean(s.astype(np.uint64) != want) > 0.99
print(f'{len(x)} inputs: the kernel is error.py\'s on every one; the wrong multiplier misses on '
      f'{np.mean(m.astype(np.uint64) != want):.2%}, the shift by 12 on {np.mean(s.astype(np.uint64) != want):.2%}')

x = random_bits(20000) want = np.array([error.hash_finalize(int(v)) for v in x], dtype=np.uint64) assert np.array_equal(finalize(x), want) WRONG = '''namespace probe; lusine.version version = { { number = 1 } }; struct item { bits h; bits multiplier; bits shift; }; lattice<item, 1> items(spacing = 1 m, boundary = wall); bits multiplier_off(bits h) { let a = (h ^ (h >> 13)) * bits; return a ^ (a >> 16); } bits shift_off(bits h) { let a = (h ^ (h >> 12)) * bits; return a ^ (a >> 16); } void main { items.multiplier = multiplier_off(items.h); items.shift = shift_off(items.h); } ''' m, s = planted(WRONG, len(x), {'h': x}, ['multiplier', 'shift']) assert np.mean(m.astype(np.uint64) != want) > 0.99 and np.mean(s.astype(np.uint64) != want) > 0.99 print(f'{len(x)} inputs: the kernel is error.py\'s on every one; the wrong multiplier misses on ' f'{np.mean(m.astype(np.uint64) != want).2%}, the shift by 12 on {np.mean(s.astype(np.uint64) != want).2%}')

20007 inputs: the kernel is error.py's on every one; the wrong multiplier misses on 100.00%, the shift by 12 on 99.99%

Limit: the edges of the 32-bit range¶

Zero mixes to zero (every step of the finalizer keeps it), and 2³² − 1 to 0x04F804F8, the value the host's own test names; the other edges as the host gives them.

In [5]:

got = finalize(EDGES)
assert got[0] == 0 and got[-1] == 0x04F804F8
assert all(int(g) == error.hash_finalize(int(e)) for g, e in zip(got, EDGES))
for e, g in zip(EDGES, got):
    print(f'finalize(0x{int(e):08X}) = 0x{int(g):08X}')

got = finalize(EDGES) assert got[0] == 0 and got[-1] == 0x04F804F8 assert all(int(g) == error.hash_finalize(int(e)) for g, e in zip(got, EDGES)) for e, g in zip(EDGES, got): print(f'finalize(0x{int(e):08X}) = 0x{int(g):08X}')

finalize(0x00000000) = 0x00000000
finalize(0x00000001) = 0x4BF1D490
finalize(0x00000002) = 0x97E3A921
finalize(0x7FFFFFFF) = 0x027C027C
finalize(0x80000000) = 0xFD84FD84
finalize(0xFFFFFFFE) = 0x50E9CF88
finalize(0xFFFFFFFF) = 0x04F804F8

Invariant: every input bit reaches the output¶

A finalizer's purpose is that one input bit flipped reaches many output bits, whichever bit it is. Over two thousand inputs, each of the 32 bits flipped in turn: the mean count of changed output bits is between 10 and 19 of 32 for every input bit, never a handful. The low bits reach the most, the multiply carrying them upward; the high bits fewer, reaching the low half only through the xor-shifts. This is the host's finalizer, kept as it is: the kernel's job is its bits, not a better hash.

In [6]:

x = random_bits(2000)
base = finalize(x)
flips = []
for bit in range(32):
    other = finalize(x ^ np.uint32(1 << bit))
    flips.append(np.mean([bin(int(a) ^ int(b)).count('1') for a, b in zip(base, other)]))
flips = np.array(flips)
assert np.all((flips > 10) & (flips < 19)), flips
print(f'output bits changed by one input bit flipped: {flips.min():.1f} to {flips.max():.1f} of 32')
fig, ax = plt.subplots(figsize=(7, 2.8))
ax.bar(range(32), flips)
ax.axhline(16, color='grey', lw=0.5)
ax.set_xlabel('input bit flipped')
ax.set_ylabel('output bits changed (mean)')
plt.show()

x = random_bits(2000) base = finalize(x) flips = [] for bit in range(32): other = finalize(x ^ np.uint32(1 << bit)) flips.append(np.mean([bin(int(a) ^ int(b)).count('1') for a, b in zip(base, other)])) flips = np.array(flips) assert np.all((flips > 10) & (flips < 19)), flips print(f'output bits changed by one input bit flipped: {flips.min():.1f} to {flips.max():.1f} of 32') fig, ax = plt.subplots(figsize=(7, 2.8)) ax.bar(range(32), flips) ax.axhline(16, color='grey', lw=0.5) ax.set_xlabel('input bit flipped') ax.set_ylabel('output bits changed (mean)') plt.show()

output bits changed by one input bit flipped: 10.7 to 18.0 of 32