Three 32-bit values hashed into one: the seeded error's hash¶

Three 32-bit values hashed into one (the host's seeded error's position_hash, and fallingsand's positionHash): each times its own odd multiplier, the sum wrapped at 32 bits, then lusine.error.finalize.

The multipliers 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, position_hash; fallingsand core/hash.glsl.

Proof

reference, limit.

position_hash.trait

namespace lusine.error;

bits position_hash(bits x, bits y, bits salt)
{
  return finalize(h = x * bits(374761393) + y * bits(668265263) + salt * bits(2246822519));
}

Uses, without proving it here: error.finalize.

X × 374761393 + y × 668265263 + salt × 2246822519, wrapped at 32 bits, then lusine.error.finalize; the host's seeded error's position_hash (fallingsand's positionHash).

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/position_hash.trait'))

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

// lusine.error.position_hash: three 32-bit values hashed into one (the host's seeded error's position_hash, and
// fallingsand's positionHash): each times its own odd multiplier, the sum wrapped at 32 bits,
// then lusine.error.finalize. The multipliers 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 position_hash(bits x, bits y, bits salt)
{
  return finalize(h = x * bits + y * bits + salt * bits);
}

The program¶

Each section runs the kernel over a lattice of items, one a triple.

In [3]:

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

def position_hash(x, y, salt):
    return lanes(lambda **a: trait_run.law('error/position_hash.trait', 'position_hash', **a), x=x, y=y, salt=salt).astype(np.uint64)

print(trait_run.law_program('error/position_hash.trait', 'position_hash')) def position_hash(x, y, salt): return lanes(lambda **a: trait_run.law('error/position_hash.trait', 'position_hash', **a), x=x, y=y, salt=salt).astype(np.uint64)

namespace probe;

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

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

void main() { items.result_0 = lusine.error.position_hash(items.x, items.y, items.salt); }

Reference: the host's position_hash, bit for bit, and a planted fault caught¶

Twenty thousand triples across the 32-bit range, the edges among them, against the host's position_hash. The planted program has the salt's multiplier one off: it misses on nearly every triple.

In [4]:

x, y, s = random_bits(20000), random_bits(20000), random_bits(20000)
want = np.array([error.position_hash(int(a), int(b), int(c)) for a, b, c in zip(x, y, s)], dtype=np.uint64)
assert np.array_equal(position_hash(x, y, s), want)
WRONG = '''namespace probe;

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

struct item { bits x; bits y; bits salt; bits hashed; };
lattice<item, 1> items(spacing = 1 m, boundary = wall);

bits salted_off(bits x, bits y, bits salt)
{
  return lusine.error.finalize(h = x * bits + y * bits + salt * bits);
}

void main() { items.hashed = salted_off(items.x, items.y, items.salt); }
'''
w, = planted(WRONG, len(x), {'x': x, 'y': y, 'salt': s}, ['hashed'])
assert np.mean(w.astype(np.uint64) != want) > 0.99
print(f'{len(x)} triples: the kernel is error.py\'s on every one; the salt\'s multiplier one off misses on '
      f'{np.mean(w.astype(np.uint64) != want):.2%}')

x, y, s = random_bits(20000), random_bits(20000), random_bits(20000) want = np.array([error.position_hash(int(a), int(b), int(c)) for a, b, c in zip(x, y, s)], dtype=np.uint64) assert np.array_equal(position_hash(x, y, s), want) WRONG = '''namespace probe; lusine.version version = { { number = 1 } }; struct item { bits x; bits y; bits salt; bits hashed; }; lattice<item, 1> items(spacing = 1 m, boundary = wall); bits salted_off(bits x, bits y, bits salt) { return lusine.error.finalize(h = x * bits + y * bits + salt * bits); } void main { items.hashed = salted_off(items.x, items.y, items.salt); } ''' w, = planted(WRONG, len(x), {'x': x, 'y': y, 'salt': s}, ['hashed']) assert np.mean(w.astype(np.uint64) != want) > 0.99 print(f'{len(x)} triples: the kernel is error.py\'s on every one; the salt\'s multiplier one off misses on ' f'{np.mean(w.astype(np.uint64) != want).2%}')

20007 triples: the kernel is error.py's on every one; the salt's multiplier one off misses on 100.00%

Limit: the corners of the 32-bit range¶

Every corner of {0, 2³² − 1}³ as the host gives it, and (0, 0, 0) hashes to 0: the mix of zeros is zero, which the finalizer keeps. A draw never takes all three zero but at seed, step, key and index all 0 (lusine.error.draw's page).

In [5]:

e = np.array([0, M32], dtype=np.uint32)
corners = np.array([(a, b, c) for a in e for b in e for c in e], dtype=np.uint32)
got = position_hash(corners[:, 0], corners[:, 1], corners[:, 2])
assert got[0] == 0
assert all(int(g) == error.position_hash(int(a), int(b), int(c)) for g, (a, b, c) in zip(got, corners))
for (a, b, c), g in zip(corners, got):
    print(f'position_hash(0x{int(a):08X}, 0x{int(b):08X}, 0x{int(c):08X}) = 0x{int(g):08X}')

e = np.array([0, M32], dtype=np.uint32) corners = np.array([(a, b, c) for a in e for b in e for c in e], dtype=np.uint32) got = position_hash(corners[:, 0], corners[:, 1], corners[:, 2]) assert got[0] == 0 assert all(int(g) == error.position_hash(int(a), int(b), int(c)) for g, (a, b, c) in zip(got, corners)) for (a, b, c), g in zip(corners, got): print(f'position_hash(0x{int(a):08X}, 0x{int(b):08X}, 0x{int(c):08X}) = 0x{int(g):08X}')

position_hash(0x00000000, 0x00000000, 0x00000000) = 0x00000000
position_hash(0x00000000, 0x00000000, 0xFFFFFFFF) = 0x8D092121
position_hash(0x00000000, 0xFFFFFFFF, 0x00000000) = 0x89F6761F
position_hash(0x00000000, 0xFFFFFFFF, 0xFFFFFFFF) = 0x3678A1D8
position_hash(0xFFFFFFFF, 0x00000000, 0x00000000) = 0x8A5E197D
position_hash(0xFFFFFFFF, 0x00000000, 0xFFFFFFFF) = 0x23744D02
position_hash(0xFFFFFFFF, 0xFFFFFFFF, 0x00000000) = 0x2B94BBF1
position_hash(0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF) = 0x97E5DECB