Skip to content

The seeded error's hash, live

Three 32-bit values hashed into one: x × 374761393 + y × 668265263 + salt × 2246822519, wrapped at 32 bits, then the seeded error's finalizer (lusine.error.position_hash). Every seeded draw is two of these, and a game's draws and the host's seeded error must agree on it to the bit. Below, the library's hash runs on your GPU as you read: on twelve triples whose hashes the host's seeded error gives, every corner of the 32-bit range among them, and each step on a strip of sixteen positions, x from 0 to 15 at y the step, with one salt, whose hashes' top four bits are binned.

This page runs the program on your GPU through WebGPU, so it needs a browser with WebGPU (a recent Chrome, Edge, Safari or Firefox). Without it the program does not run and nothing is drawn below.

What it shows

  • The strip above the controls is green while every check holds, and turns red for good once one fails.
  • The spread: a hash of neighbouring positions should look like a fair draw, each of the sixteen values of its top four bits as likely as another. The chart draws the chi-square of the sixteen bins against an even spread, a point a step, beside its bound, 44.26, the value a fair draw passes only once in ten thousand times (the 0.9999 quantile of the chi-square law with 15 degrees of freedom). Below it, the hashes binned and the chi-square now.
  • The checks: the host's bits, the twelve triples hashing to the host's values exactly, (0, 0, 0) to 0 among them; a flat spread, the chi-square within its bound at every step once sixteen steps (256 hashes) are binned; near miss told apart, the hash with its salt's multiplier one off giving the hash's bits on at most one hash in a hundred (it has agreed on none so far, shown above it), so agreement with the host is no accident of the inputs. Each is held at every step.

Every number here is computed by the program on the GPU; the page only reads the values back and draws them. The salt and the steps before the spread is held are the program's settings, which the host may write; this page offers no control to change them yet.

The program

The host's cases, the strip, the bins and the checks, the panels the page draws, and the one procedure, main, run each step: the cases hashed, the strip hashed at the step and binned, and the checks.

// The seeded error's hash's live page: the library's position hash held to the host's seeded error's values bit for
// bit, a strip of positions hashed each step with one salt and the top four bits of their hashes binned and held to a
// flat spread by a chi-square bound, and a near miss of the hash told apart, with the page's checks computed here on
// the GPU and shown by the panels the program declares.

namespace position_hash;

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

// The reader's settings: the salt the strip is hashed with, and the steps before the spread is held to its bound.
host struct { integer salt = 20261005; integer settle = 16; } settings;

// The host's seeded error's position hash at twelve triples, every corner of the 32-bit range among them, each as its
// signed 32-bit integer (two's complement: -1 is 2^32 - 1), and what the library's hash gives each.
struct case { host integer x; host integer y; host integer salt; host integer want; bits got; bool held; };
table<case> cases(capacity = 16) = {
  { x = 0, y = 0, salt = 0, want = 0 },
  { x = 0, y = 0, salt = -1, want = -1928781535 },
  { x = 0, y = -1, salt = 0, want = -1980336609 },
  { x = 0, y = -1, salt = -1, want = 913875416 },
  { x = -1, y = 0, salt = 0, want = -1973544579 },
  { x = -1, y = 0, salt = -1, want = 594824450 },
  { x = -1, y = -1, salt = 0, want = 731167729 },
  { x = -1, y = -1, salt = -1, want = -1746542901 },
  { x = 1, y = 2, salt = 3, want = -2143845793 },
  { x = 160, y = 90, salt = 20261005, want = 402360534 },
  { x = -2147483648, y = 7, salt = 42, want = 1503222043 },
  { x = 12345, y = 67890, salt = -889275714, want = -1115167702 },
};

// A strip of sixteen positions, x from 0 to 15 at y the step, each hashed with the salt; its top four bits, a bin
// from 0 to 15; and the near miss's hash, the salt's multiplier one off.
struct position { integer x; bits hashed; integer top; bits near; integer agreed; };
table<position> strip(capacity = 16) = {
  { x = 0 }, { x = 1 }, { x = 2 }, { x = 3 }, { x = 4 }, { x = 5 }, { x = 6 }, { x = 7 },
  { x = 8 }, { x = 9 }, { x = 10 }, { x = 11 }, { x = 12 }, { x = 13 }, { x = 14 }, { x = 15 },
};

// The sixteen bins of the top four bits, each with the hashes it has held so far.
struct bin { integer top; integer held; };
table<bin> bins(capacity = 16) = {
  { top = 0 }, { top = 1 }, { top = 2 }, { top = 3 }, { top = 4 }, { top = 5 }, { top = 6 }, { top = 7 },
  { top = 8 }, { top = 9 }, { top = 10 }, { top = 11 }, { top = 12 }, { top = 13 }, { top = 14 }, { top = 15 },
};

// The step, the hashes binned so far, the chi-square of the bins against a flat spread and its bound, the 0.9999
// quantile of the chi-square law with 15 degrees of freedom; and on how many hashes the near miss gave the hash's bits.
struct { integer step; integer hashes; float chi_square; float bound = 44.26; integer agreed; } spread;

// The checks: every case the host's bits; the bins' chi-square within its bound at every step once the settle's steps
// are binned; and the near miss giving the hash's bits on at most one hash in a hundred.
struct { bool host = true; bool flat = true; bool near_miss = true; } checks;

// A strip of lamps the page draws, lit green while every check holds and red once one fails.
struct lamp { vector<float, 4> colour; };
lattice<lamp, 2> lamps(spacing = 1 m, boundary = wall);

vector<float, 4> lamp_colour(bool holds)
{
  return holds ? vector<float, 4>(0.15, 0.6, 0.3, 1.0) : vector<float, 4>(0.75, 0.15, 0.15, 1.0);
}

bool matches(bits got, integer want) { return got == bits(want); }
integer missed(table<bool> held) { return count(held) where !held; }

integer top_bits(bits hashed) { return integer(hashed >> 28); }

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

integer agreed(bits near, bits hashed) { return near == hashed ? 1 : 0; }
integer total_agreed(table<integer> agreed) { return sum(agreed); }

integer landed(table<integer> top, integer bin)
{
  let which = bin;
  return count(top) where top == which;
}

float chi_square(table<integer> held, integer hashes)
{
  let expected = float(hashes) / 16.0;
  return sum((float(held) - expected) * (float(held) - expected)) / expected;
}

output table<lusine.widget> panels = {
  lusine.series { { panel = "the spread", chart = "chi-square", quantity = spread.chi_square, steps = 400,
                    label = "chi-square" } },
  lusine.series { { panel = "the spread", chart = "chi-square", quantity = spread.bound, steps = 400,
                    label = "its bound" } },
  lusine.value { { panel = "the spread", quantity = spread.hashes, label = "hashes binned" } },
  lusine.value { { panel = "the spread", quantity = spread.chi_square, label = "chi-square, 15 degrees" } },
  lusine.value { { panel = "the checks", quantity = spread.agreed, label = "near miss agreed" } },
  lusine.value { { panel = "the checks", quantity = checks.host, label = "the host's bits" } },
  lusine.value { { panel = "the checks", quantity = checks.flat, label = "a flat spread" } },
  lusine.value { { panel = "the checks", quantity = checks.near_miss, label = "near miss told apart" } },
};

void main()
{
  cases.got = lusine.error.position_hash(x = bits(cases.x), y = bits(cases.y), salt = bits(cases.salt));
  cases.held = matches(cases.got, cases.want);
  spread.step = spread.step + 1;
  strip.hashed = lusine.error.position_hash(x = bits(strip.x), y = bits(spread.step), salt = bits(settings.salt));
  strip.top = top_bits(strip.hashed);
  strip.near = salted_off(strip.x, spread.step, settings.salt);
  strip.agreed = agreed(strip.near, strip.hashed);
  bins.held = bins.held + landed(strip.top, bin = bins.top);
  spread.hashes = spread.hashes + 16;
  spread.agreed = spread.agreed + total_agreed(strip.agreed);
  spread.chi_square = chi_square(bins.held, spread.hashes);
  checks.host = checks.host && missed(cases.held) == 0;
  checks.flat = checks.flat && (spread.step < settings.settle || spread.chi_square <= spread.bound);
  checks.near_miss = checks.near_miss && 100 * spread.agreed <= spread.hashes;
  lamps.colour = lamp_colour(holds = checks.host && checks.flat && checks.near_miss);
}

The hash's other proof (twenty thousand triples against the host's, the corners) is on its proof page.