Skip to content

The seeded error's finalizer, live

The finalizer every seeded draw ends in: an xor-shift by 13, a multiply by 1274126177 and an xor-shift by 16, each on 32 bits and wrapped (lusine.error.finalize). A game's draws and the host's seeded error must agree on it to the bit. Below, the library's finalizer runs on your GPU as you read: on twelve inputs whose outputs the host's seeded error gives, the edges of the 32-bit range among them, and on a new input each step, every one of whose 32 bits is flipped in turn to count how many output bits the flip reaches.

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 reach: a finalizer's purpose is that one input bit flipped changes many output bits, whichever bit it is. The chart draws, for each of the 32 input bits, the mean count of output bits its flip has changed over the inputs so far, one bit a step and round again, between the bounds it is held to, 10 and 19. The low bits reach the most, the multiply carrying them upward; the high bits fewer, reaching the low half only through the xor-shifts. Below it, the inputs mixed, this step's input and its output, and the fewest and most of the 32 means.
  • The checks: the host's bits, the twelve inputs giving the host's outputs exactly, 0 giving 0 and 2³² − 1 giving 0x04F804F8 among them; every bit reaches, every input bit changing between 10 and 19 of the 32 output bits on average once 256 inputs are mixed; near misses told apart, the finalizer with its multiplier one off and with its first shift by 12, each giving the finalizer's bits on at most one input in a hundred, so agreement with the host is no accident of the inputs (each has agreed on none so far, shown above it). 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 first input and how many inputs are mixed before the reach 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 32 input bits, the step's input and the checks, the panels the page draws, and the one procedure, main, run each step: the cases finalized, the next input mixed with each of its bits flipped, and the checks.

// The seeded error's finalizer's live page: the library's finalizer held to the host's seeded error's values bit for
// bit, a new input mixed each step and every one of its 32 bits flipped in turn to count the output bits it reaches,
// and two near misses of the finalizer told apart, with the page's checks computed here on the GPU and shown by the
// panels the program declares.

namespace finalize;

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

// The reader's settings: the first input the step's inputs run on from, and how many inputs are mixed before the
// reach is held to its bounds.
host struct { integer start = 12345; integer settle = 256; } settings;

// The host's seeded error's finalizer at twelve inputs, the edges 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 finalizer gives each.
struct case { host integer input; host integer want; bits got; bool held; };
table<case> cases(capacity = 16) = {
  { input = 0, want = 0 },
  { input = 1, want = 1274139792 },
  { input = 2, want = -1746687711 },
  { input = 2147483647, want = 41681532 },
  { input = -2147483648, want = -41615996 },
  { input = -2, want = 1357500296 },
  { input = -1, want = 83363064 },
  { input = 305419896, want = -1336234048 },
  { input = 777243802, want = -14515034 },
  { input = 20261005, want = 865786174 },
  { input = -559038737, want = -298863507 },
  { input = 1000000, want = -695940226 },
};

// The 32 input bits, each with the output bits its flip has changed, summed over the inputs so far, and their mean.
struct flip { integer bit; integer changed; float mean; };
table<flip> flips(capacity = 32) = {
  { bit = 0 }, { bit = 1 }, { bit = 2 }, { bit = 3 }, { bit = 4 }, { bit = 5 }, { bit = 6 }, { bit = 7 },
  { bit = 8 }, { bit = 9 }, { bit = 10 }, { bit = 11 }, { bit = 12 }, { bit = 13 }, { bit = 14 }, { bit = 15 },
  { bit = 16 }, { bit = 17 }, { bit = 18 }, { bit = 19 }, { bit = 20 }, { bit = 21 }, { bit = 22 }, { bit = 23 },
  { bit = 24 }, { bit = 25 }, { bit = 26 }, { bit = 27 }, { bit = 28 }, { bit = 29 }, { bit = 30 }, { bit = 31 },
};

// The step's input, run on from the start by a linear congruential generator (Numerical Recipes'), and what the
// finalizer and its two near misses (the multiplier one off, the first shift by 12) give it; how many inputs so far,
// and on how many each near miss gave the finalizer's bits.
struct {
  bits input; bits output; integer inputs; integer multiplier_agreed; integer shift_agreed;
} mix;

// What the chart and the values show: one input bit a step, round the 32, and the mean count of output bits its flip
// changes, beside the bounds it is held to, 10 and 19; the fewest and the most over the 32 bits.
struct { float bit; float changed; float low = 10.0; float high = 19.0; float fewest; float most; } reach;

// The checks: every case the host's bits; every input bit, once the settle's inputs are mixed, changing between 10 and
// 19 of the 32 output bits on average; and each near miss giving the finalizer's bits on at most one input in a
// hundred.
struct { bool host = true; bool reach = true; bool near_misses = 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);
}

bits stepped(bits input, integer inputs, integer start)
{
  let from = inputs == 0 ? bits(start) : input;
  return from * bits(1664525) + bits;
}

// The ones of a word, counted in parallel (Hacker's Delight, 5-1), not by the finalizer.
integer ones(bits word)
{
  let a = word - ((word >> 1) & bits);
  let b = (a & bits) + ((a >> 2) & bits);
  let c = (b + (b >> 4)) & bits;
  return integer((c * bits(16843009)) >> 24);
}

integer reached(bits input, bits output, integer bit)
{
  return ones(word = output ^ lusine.error.finalize(h = input ^ (bits(1) << bit)));
}

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

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); }
integer agreed(bits near, bits output) { return near == output ? 1 : 0; }

float fewest(table<float> mean) { return min(mean); }
float most(table<float> mean) { return max(mean); }
float mean_of(table<float> mean, table<integer> bit, integer which) { return sum(mean) where bit == which; }

output table<lusine.widget> panels = {
  lusine.series { { panel = "the reach", chart = "output bits changed", quantity = reach.changed, steps = 32,
                    against = reach.bit, label = "mean changed" } },
  lusine.series { { panel = "the reach", chart = "output bits changed", quantity = reach.low, steps = 32,
                    against = reach.bit, label = "at least" } },
  lusine.series { { panel = "the reach", chart = "output bits changed", quantity = reach.high, steps = 32,
                    against = reach.bit, label = "at most" } },
  lusine.value { { panel = "the reach", quantity = mix.inputs, label = "inputs mixed" } },
  lusine.value { { panel = "the reach", quantity = mix.input, label = "this input" } },
  lusine.value { { panel = "the reach", quantity = mix.output, label = "finalized" } },
  lusine.value { { panel = "the reach", quantity = reach.fewest, label = "fewest of 32" } },
  lusine.value { { panel = "the reach", quantity = reach.most, label = "most of 32" } },
  lusine.value { { panel = "the checks", quantity = mix.multiplier_agreed, label = "multiplier one off agreed" } },
  lusine.value { { panel = "the checks", quantity = mix.shift_agreed, label = "shift by 12 agreed" } },
  lusine.value { { panel = "the checks", quantity = checks.host, label = "the host's bits" } },
  lusine.value { { panel = "the checks", quantity = checks.reach, label = "every bit reaches" } },
  lusine.value { { panel = "the checks", quantity = checks.near_misses, label = "near misses told apart" } },
};

void main()
{
  cases.got = lusine.error.finalize(h = bits(cases.input));
  cases.held = matches(cases.got, cases.want);
  mix.input = stepped(mix.input, mix.inputs, settings.start);
  mix.output = lusine.error.finalize(h = mix.input);
  mix.inputs = mix.inputs + 1;
  mix.multiplier_agreed = mix.multiplier_agreed + agreed(near = multiplier_off(h = mix.input), mix.output);
  mix.shift_agreed = mix.shift_agreed + agreed(near = shift_off(h = mix.input), mix.output);
  flips.changed = flips.changed + reached(mix.input, mix.output, flips.bit);
  flips.mean = float(flips.changed) / float(mix.inputs);
  reach.bit = float((mix.inputs - 1) % 32);
  reach.changed = mean_of(flips.mean, flips.bit, which = (mix.inputs - 1) % 32);
  reach.fewest = fewest(flips.mean);
  reach.most = most(flips.mean);
  checks.host = checks.host && missed(cases.held) == 0;
  checks.reach = checks.reach
                 && (mix.inputs < settings.settle || (reach.fewest > reach.low && reach.most < reach.high));
  checks.near_misses = checks.near_misses && 100 * mix.multiplier_agreed <= mix.inputs
                       && 100 * mix.shift_agreed <= mix.inputs;
  lamps.colour = lamp_colour(holds = checks.host && checks.reach && checks.near_misses);
}

The finalizer's other proof (twenty thousand inputs against the host's, the edges, the reach over two thousand inputs) is on its proof page.