Hashing Space

Every procedural world needs random numbers that come back the same each time you visit the same place. This is how Islands gets them: a hash turns a seed and a grid position into 32 random-looking bits. Drag the grid, tap a cell, and compare a good hash with two weak ones. How it works.

Todo mundo procedural necesita números aleatorios que vuelvan a ser los mismos cada vez que pasas por el mismo sitio. Así los consigue Islands: un hash convierte una semilla y una posición de la rejilla en 32 bits de aspecto aleatorio. Arrastra la rejilla, toca una celda y compara un buen hash con dos malos. Cómo funciona.

The idea in plain words

A hash is a function that scrambles its input so thoroughly that the output looks random, yet the same input always gives the same output. Give it a seed and the coordinates of a cell, and it hands back a number you can use as that cell's "random" value, today, tomorrow and on someone else's computer.

Think of a blender. The same ingredients always give the same smoothie, and changing one grain of salt changes the whole glass. The analogy has limits. A blender loses information, and a hash does too, but a good hash for noise is also fast and spreads its outputs evenly, which a blender has no reason to do. A second picture: a fingerprint for every place on the map. That one breaks too, because there are only about four billion 32-bit fingerprints, so different places will sometimes share one.

Tap any cell and look at the panel: the seed, then each coordinate "eaten" one after the other, then a final scramble called the avalanche. Under the histogram, two numbers tell a good hash from a bad one; switch between the three hashes and watch them move.

Why it matters

The usual way to get random numbers in a program is a generator: you ask it for the next number, and the next. That works until you need the value of a particular cell without computing all the cells before it, or many cells in parallel, or the same cell again a week later. A hash needs no memory and no order. Any cell can be computed alone, in any order, on any number of cores, and it always comes out the same. That is what makes an infinite, reproducible world possible: drag the grid as far as you like, past zero into negative coordinates, and nothing is stored.

Islands relies on this everywhere. Every noise field is built from hashes of lattice points. The map pipeline gives each field its own seed, the map seed combined with a fixed "salt" per field, so the terrain, the two warp fields and the temperature noise do not echo one another. None of that noise comes from a sequential generator, which is why the same seed always produces the same island, and why Islands can check that with stored reference hashes of its output.

The catch: none of this is random. It only looks random to the tests you run. Switch to Multiply and add. Its histogram is flat, and its picture is a regular plaid. In fact the histogram is too flat: real randomness is lumpy, and a χ² that low is a warning sign of its own. An even spread of values is necessary, and nowhere near enough.

Is there a theorem?

Some, and they mostly say what cannot be done. The pigeonhole principle settles collisions: two 32-bit coordinates make 2⁶⁴ possible inputs and there are only 2³² outputs, so many cells must share a hash. The birthday problem says how soon: among about 77,000 random inputs, the odds that two share a 32-bit hash are already about one in two. For noise that is harmless, since nobody looks up cells by their hash.

The guarantees that do exist apply to families of functions. Carter and Wegman (1979) proved that if you pick a function at random from a universal family, any two distinct keys collide with probability at most 1/m. A fixed, fast hash like SmallXXHash comes with no such proof. Its quality is empirical: it passes or fails batteries of statistical tests such as SMHasher and TestU01. The useful yardstick is the strict avalanche criterion of Webster and Tavares (1985): flipping any single input bit should flip each output bit with probability one half. Jarzynski and Olano (2020) tested over a hundred hashes this way for graphics. Their first figure makes a point this page also makes: a picture can expose a bad hash, but it cannot prove a good one.

The equations

All arithmetic is on 32-bit unsigned integers, so every sum and product wraps around modulo 2³². rotl_k rotates the bits left by k; ⊕ is exclusive or; ≫ is a right shift.

Seed: acc₀ = seed + P_E
Eat: acc′ = rotl₁₇(acc + d · P_C) · P_D
Avalanche: h ← h ⊕ (h ≫ 15); h ← h · P_B; h ← h ⊕ (h ≫ 13); h ← h · P_C; h ← h ⊕ (h ≫ 16)
Cell hash: H(seed, x, y) = avalanche(eat(eat(acc₀, x), y))
Birthday bound: P(some collision among n) ≈ 1 − exp(−n² / 2³³)

The constants P_A…P_E are the five primes of Yann Collet's xxHash32. Read the eat step as: mix the new number in by multiplying it by a large odd constant, then rotate so the well-mixed high bits fall into the low bits, then multiply again. Each eat depends on everything eaten before it, so (x, y) and (y, x) give different hashes.

What the picture does and does not say

Each cell shows one byte, 8 of the 32 bits, as one of 256 shades. Islands reads exactly these bytes (A to D) to pick values and gradient directions.
The histogram only tests evenness. For 16 bins, random data gives a χ² between about 6 and 27 in 95 % of cases. Both weak hashes land below that range: they are too even.
Measured over 4 seeds and 3 windows of 32 × 32 cells, SmallXXHash gave χ² from 5.5 to 24 and a neighbour correlation within ±0.07. The two weak hashes gave χ² from 0.2 to 9 and correlations between −0.5 and 0.35.
The bit count in the legend does not separate them: over 10,000 cells it averages 16.0 for SmallXXHash, 15.5 without the avalanche and 16.7 for multiply-and-add. Moving one cell flips several input bits at once; the avalanche criterion flips one input bit at a time and looks at each output bit separately.
The code is a JavaScript port written for this page. It reproduces the C# in Islands bit for bit: both were run on the same test inputs, negative and extreme coordinates included, and agreed on every one.
The weak hashes are illustrations made for this page. Islands never used them.

How it works

This part walks through the code of the scene, step by step. It covers:

Doing 32-bit unsigned arithmetic in JavaScript.
Building SmallXXHash: seed, eat, avalanche.
Seeing why the avalanche is there.
Hashing a grid of cells into an image.
Measuring a hash: a histogram, a correlation and a bit count.
Moving over a grid that has no edges.

Plain JavaScript and the Canvas 2D API, no libraries. The hash is about 50 lines and the scene about 250. The design follows Jasper Flick's Pseudorandom Noise tutorial at Catlike Coding, which is also where the C# in Islands comes from.

1. Thirty-two bits in a language that has none

The hash is defined on 32-bit unsigned integers that wrap around on overflow. C# has that type, uint. JavaScript has only 64-bit floating-point numbers, which stop being exact above 2⁵³, so a plain product of two 32-bit numbers would silently lose its low bits, the very bits we care about. Three small helpers fix that. Math.imul multiplies as 32-bit integers, and >>> 0 reinterprets the result as unsigned.

// JavaScript numbers are doubles; these keep every step inside 32 unsigned bits.
const mul = (a, b) => Math.imul(a, b) >>> 0;
const add = (a, b) => (a + b) >>> 0;
const rotl = (v, s) => ((v << s) | (v >>> (32 - s))) >>> 0;

Why not use BigInt?

BigInt is exact but arbitrary-precision: every operation allocates, and you would still have to reduce modulo 2³² by hand. The scene hashes up to about 25,000 cells per frame while you drag, and Math.imul does it with plain numbers.

2. Seed and eat

The hash keeps a single 32-bit number, the accumulator. It starts as the seed plus a prime. Each piece of data is then "eaten": multiplied by one prime, added in, rotated left by 17 bits, and multiplied by another prime. These are the xxHash32 primes; the C# in Islands writes them in binary.

export const PRIME_A = 0x9e3779b1;
export const PRIME_B = 0x85ebca77;
export const PRIME_C = 0xc2b2ae3d;
export const PRIME_D = 0x27d4eb2f;
export const PRIME_E = 0x165667b1;

export function seed(s) {
  return add(s >>> 0, PRIME_E);
}

// Feed one integer into the accumulator.
export function eat(acc, data) {
  return mul(rotl(add(acc, mul(data >>> 0, PRIME_C)), 17), PRIME_D);
}

Multiplication only pushes information upwards: the lowest bit of a product depends only on the lowest bits of its factors. The rotation brings the well-mixed high bits back down. Tap a cell and read the panel: each line is the accumulator after one step.

Is this the full xxHash32?

No. xxHash32 is built to digest long messages, so it runs four accumulators in parallel over 16-byte stripes. SmallXXHash only ever eats a few integers, so Catlike Coding's version drops that machinery and keeps the seed, the per-integer round and the final avalanche.

3. The avalanche

After the last eat, the accumulator is scrambled once more: shift right and XOR, multiply, and again. XOR with a right shift lets high bits influence low bits; the multiplications spread low bits upwards. A few rounds make every input bit reach every output bit.

// Final mix: spread every input bit over the whole output.
export function avalanche(acc) {
  let h = acc;
  h = (h ^ (h >>> 15)) >>> 0;
  h = mul(h, PRIME_B);
  h = (h ^ (h >>> 13)) >>> 0;
  h = mul(h, PRIME_C);
  h = (h ^ (h >>> 16)) >>> 0;
  return h;
}

export function hash2(s, x, y) {
  return avalanche(eat(eat(seed(s), x), y));
}

To see what it does, switch the scene to Without avalanche, show byte A and read the panel. Neighbouring cells now correlate, with r around 0.3, and χ² falls to about 4, too even to be chance. The bit count in the legend barely moves, which is the first lesson in testing hashes: one number about one pair of cells tells you very little.

4. Two weak hashes to compare against

The third mode multiplies each coordinate by a large odd constant and adds them up. It is fast and spreads values evenly, and its low byte is a linear function of x and y, so it weaves a regular plaid.

// Multiply and add, no mixing: the low byte is a linear function of x and y.
function naive(s, x, y) {
  return (Math.imul(x, PRIME_A) + Math.imul(y, PRIME_B) + s) >>> 0;
}

function hashCell(x, y) {
  if (state.mode === "naive") return naive(state.seed, x, y);
  const acc = eat(eat(seed(state.seed), x), y);
  return state.mode === "raw" ? acc : avalanche(acc);
}

5. From a hash to a picture

A 32-bit hash holds four bytes. Islands reads them separately, so one hash yields up to four independent-looking values per cell. The scene shows one byte at a time.

// The four bytes Islands reads as BytesA…BytesD (A is the lowest).
export function byteOf(h, which) {
  return (h >>> (8 * which)) & 255;
}

To draw, we write one pixel per cell into a small offscreen image, then stretch it over the canvas with smoothing turned off, so every cell stays a crisp square. The same loop fills the histogram.

// One pixel per cell in an offscreen image, then scaled up without smoothing.
off.width = cols; off.height = rows;
const img = octx.createImageData(cols, rows);
for (let j = 0; j < rows; j++) {
  for (let i = 0; i < cols; i++) {
    const b = byteOf(hashCell(state.ox + i, state.oy + j), state.byte);
    bins[b >> 4]++;
    const v = b / 255, k = 4 * (j * cols + i);
    img.data[k] = DARK[0] + (LIGHT[0] - DARK[0]) * v;
    …
  }
}
octx.putImageData(img, 0, 0);
ctx.imageSmoothingEnabled = false;
ctx.drawImage(off, 0, 0, cols * cs, rows * cs);

6. Measuring a hash

The histogram splits the 256 possible byte values into 16 bins. If the values were truly uniform, each bin would hold about 1/16 of the cells. Pearson's χ² statistic sums the squared deviations from that: for 16 bins it averages 15 for random data, and values above about 25 happen less than 5 % of the time.

// Pearson's chi-squared against a flat histogram. For 16 bins, random data gives
// between about 6 and 27 in 95 % of cases; far lower means suspiciously even.
let chi = 0;
for (const c of bins) chi += (c - expected) ** 2 / expected;

Evenness says nothing about order, so the second number compares each cell with its right neighbour. Pearson's correlation r is 0 when knowing one byte tells you nothing about the next, and approaches ±1 when it tells you everything.

// Pearson correlation between each cell and its right-hand neighbour; near 0 for a good hash.
function neighbourCorrelation(cols, rows) {
  let n = 0, sa = 0, sb = 0, sab = 0, saa = 0, sbb = 0;
  for (let j = 0; j < rows; j++) {
    for (let i = 0; i + 1 < cols; i++) {
      const a = bytes[j * cols + i], b = bytes[j * cols + i + 1];
      n++; sa += a; sb += b; sab += a * b; saa += a * a; sbb += b * b;
    }
  }
  const cov = sab / n - (sa / n) * (sb / n);
  const va = saa / n - (sa / n) ** 2, vb = sbb / n - (sb / n) ** 2;
  return va > 0 && vb > 0 ? cov / Math.sqrt(va * vb) : 0;
}

The legend's bit count XORs the hashes of the selected cell and its neighbour and counts the ones. It is the cheapest test, and as the scene shows, the weakest.

const h = hashCell(x, y);
const hn = hashCell(x + 1, y);
const flips = popcount((h ^ hn) >>> 0);

Why is the naive histogram so flat?

Because the test only counts how often each value appears, not where. Multiplying by an odd number is a bijection modulo 256, so as x walks along a row, the low byte visits the values almost perfectly evenly, far more evenly than chance would. A test that looked at pairs of neighbours would catch it at once, and real test suites do exactly that, with thousands of such tests.

7. A grid with no edges

Nothing is stored, so the grid is just a window: ox and oy say which cell sits in the top-left corner. Dragging changes them; tapping turns a screen position back into a cell with floor, which also handles negative coordinates correctly. The orange lines mark x = 0 and y = 0.

function cellAt(ev) {
  const r = canvas.getBoundingClientRect();
  const cs = cellSize() / dpr;
  return {
    x: state.ox + Math.floor((ev.clientX - r.left) / cs),
    y: state.oy + Math.floor((ev.clientY - r.top) / cs),
  };
}

Going further

Hash four cells at once. Islands' SmallXXHash4 runs the same steps on four lanes with SIMD instructions; in JavaScript you can batch with typed arrays and measure the gain.
Port it to a shader. GLSL ES 3.0 has 32-bit unsigned integers, and Jarzynski and Olano compare xxhash32 with faster GPU options such as pcg3d.
Turn the hash into noise. Put a hashed value on every lattice point and blend between them smoothly: that is value noise, the next page in this series.

La idea en palabras sencillas

Un hash es una función que revuelve su entrada tan a fondo que el resultado parece aleatorio, aunque la misma entrada siempre da la misma salida. Dale una semilla y las coordenadas de una celda, y te devuelve un número que puedes usar como el valor "aleatorio" de esa celda: hoy, mañana y en el ordenador de otra persona.

Piensa en una batidora. Los mismos ingredientes dan siempre el mismo batido, y cambiar un grano de sal cambia el vaso entero. La analogía tiene límites. Una batidora pierde información, y un hash también, pero un buen hash para ruido además es rápido y reparte sus resultados de forma pareja, cosa que a una batidora no se le pide. Otra imagen: una huella dactilar para cada lugar del mapa. Esa también falla, porque solo hay unos cuatro mil millones de huellas de 32 bits, así que a veces dos lugares comparten una.

Toca cualquier celda y mira el panel: la semilla, luego cada coordenada "comida" una tras otra, y al final un último revoltijo llamado avalanche. Bajo el histograma, dos números distinguen un buen hash de uno malo; cambia entre los tres hashes y míralos moverse.

Por qué importa

La forma habitual de obtener números aleatorios en un programa es un generador: le pides el siguiente número, y el siguiente. Funciona hasta que necesitas el valor de una celda concreta sin calcular todas las anteriores, o muchas celdas en paralelo, o la misma celda otra vez una semana después. Un hash no necesita memoria ni orden. Cualquier celda se calcula sola, en cualquier orden y en cualquier número de núcleos, y siempre sale igual. Eso es lo que hace posible un mundo infinito y reproducible: arrastra la rejilla todo lo que quieras, más allá del cero, hacia las coordenadas negativas, y no se guarda nada.

Islands se apoya en esto en todas partes. Cada campo de ruido se construye con hashes de los puntos de una red. El pipeline de mapas da a cada campo su propia semilla, la del mapa combinada con una "sal" fija por campo, para que el terreno, los dos campos de deformación y el ruido de temperatura no se hagan eco entre sí. Nada de ese ruido sale de un generador secuencial, y por eso la misma semilla produce siempre la misma isla, y Islands puede comprobarlo con hashes de referencia guardados de su resultado.

La trampa: nada de esto es aleatorio. Solo lo parece ante las pruebas que le hagas. Cambia a Multiplicar y sumar. Su histograma es plano y su imagen es una trama regular, como un tartán. De hecho, el histograma es demasiado plano: el azar real es irregular, y un χ² tan bajo es una señal de alarma en sí mismo. Un reparto parejo de valores es necesario, y ni de lejos suficiente.

¿Hay un teorema?

Algunos, y sobre todo dicen lo que no se puede hacer. El principio del palomar zanja las colisiones: dos coordenadas de 32 bits dan 2⁶⁴ entradas posibles y solo hay 2³² salidas, así que muchas celdas tienen que compartir hash. El problema del cumpleaños dice cuándo: con unas 77.000 entradas aleatorias, la probabilidad de que dos compartan un hash de 32 bits ya es de una entre dos. Para el ruido no importa, porque nadie busca celdas por su hash.

Las garantías que sí existen valen para familias de funciones. Carter y Wegman (1979) demostraron que, si eliges al azar una función de una familia universal, dos claves distintas colisionan con probabilidad como mucho 1/m. Un hash fijo y rápido como SmallXXHash no tiene ninguna demostración así. Su calidad es empírica: pasa o falla baterías de pruebas estadísticas como SMHasher y TestU01. La vara de medir útil es el criterio estricto de avalancha de Webster y Tavares (1985): al invertir cualquier bit de la entrada, cada bit de la salida debería cambiar con probabilidad un medio. Jarzynski y Olano (2020) probaron así más de cien hashes para gráficos. Su primera figura defiende algo que esta página también muestra: una imagen puede delatar un mal hash, pero no demostrar que uno sea bueno.

Las ecuaciones

Toda la aritmética es con enteros sin signo de 32 bits, así que cada suma y cada producto da la vuelta módulo 2³². rotl_k rota los bits k posiciones a la izquierda; ⊕ es el o exclusivo; ≫ es un desplazamiento a la derecha.

Semilla: acc₀ = semilla + P_E
Comer: acc′ = rotl₁₇(acc + d · P_C) · P_D
Avalancha: h ← h ⊕ (h ≫ 15); h ← h · P_B; h ← h ⊕ (h ≫ 13); h ← h · P_C; h ← h ⊕ (h ≫ 16)
Hash de una celda: H(semilla, x, y) = avalanche(eat(eat(acc₀, x), y))
Cota del cumpleaños: P(alguna colisión entre n) ≈ 1 − exp(−n² / 2³³)

Las constantes P_A…P_E son los cinco primos de xxHash32, de Yann Collet. El paso de comer se lee así: mezcla el número nuevo multiplicándolo por una constante impar grande, rota para que los bits altos, ya bien mezclados, caigan en los bajos, y vuelve a multiplicar. Cada paso depende de todo lo comido antes, así que (x, y) e (y, x) dan hashes distintos.

Lo que la imagen dice y lo que no

Cada celda muestra un byte, 8 de los 32 bits, como uno de 256 tonos. Islands lee justo estos bytes (de la A a la D) para elegir valores y direcciones de gradiente.
El histograma solo mide lo parejo del reparto. Con 16 tramos, datos aleatorios dan un χ² de entre unos 6 y 27 en el 95 % de los casos. Los dos hashes malos quedan por debajo: son demasiado parejos.
Medido en 4 semillas y 3 ventanas de 32 × 32 celdas, SmallXXHash dio un χ² de 5,5 a 24 y una correlación entre vecinas dentro de ±0,07. Los dos hashes malos dieron χ² de 0,2 a 9 y correlaciones entre −0,5 y 0,35.
La cuenta de bits de la leyenda no los distingue: en 10.000 celdas promedia 16,0 con SmallXXHash, 15,5 sin la avalancha y 16,7 con multiplicar y sumar. Moverse una celda invierte varios bits de la entrada a la vez; el criterio de avalancha invierte un solo bit cada vez y mira cada bit de salida por separado.
El código es un port a JavaScript escrito para esta página. Reproduce bit a bit el C# de Islands: ambos se ejecutaron con las mismas entradas de prueba, coordenadas negativas y extremas incluidas, y coincidieron en todas.
Los hashes malos son ilustraciones hechas para esta página. Islands nunca los usó.

Cómo funciona

Esta parte recorre el código de la escena, paso a paso. Cubre:

Hacer aritmética de 32 bits sin signo en JavaScript.
Construir SmallXXHash: semilla, comer, avalancha.
Ver para qué está la avalancha.
Convertir una rejilla de celdas hasheadas en una imagen.
Medir un hash: un histograma, una correlación y una cuenta de bits.
Moverse por una rejilla que no tiene bordes.

JavaScript puro y la API Canvas 2D, sin librerías. El hash ocupa unas 50 líneas y la escena unas 250. El diseño sigue el tutorial Pseudorandom Noise de Jasper Flick en Catlike Coding, que es también de donde viene el C# de Islands. Los comentarios del código están en inglés.

1. Treinta y dos bits en un lenguaje que no los tiene

El hash está definido sobre enteros sin signo de 32 bits que dan la vuelta al desbordarse. C# tiene ese tipo, uint. JavaScript solo tiene números de coma flotante de 64 bits, que dejan de ser exactos por encima de 2⁵³, así que el producto de dos números de 32 bits perdería en silencio sus bits bajos, justo los que nos importan. Tres funciones pequeñas lo arreglan. Math.imul multiplica como enteros de 32 bits, y >>> 0 reinterpreta el resultado como un número sin signo.

// JavaScript numbers are doubles; these keep every step inside 32 unsigned bits.
const mul = (a, b) => Math.imul(a, b) >>> 0;
const add = (a, b) => (a + b) >>> 0;
const rotl = (v, s) => ((v << s) | (v >>> (32 - s))) >>> 0;

¿Por qué no usar BigInt?

BigInt es exacto, pero de precisión arbitraria: cada operación reserva memoria, y aun así habría que reducir a mano módulo 2³². La escena hashea hasta unas 25.000 celdas por fotograma mientras arrastras, y Math.imul lo hace con números normales.

2. Semilla y comer

El hash guarda un único número de 32 bits, el acumulador. Empieza siendo la semilla más un primo. Luego cada dato se "come": se multiplica por un primo, se suma, se rota 17 bits a la izquierda y se multiplica por otro primo. Son los primos de xxHash32; el C# de Islands los escribe en binario.

export const PRIME_A = 0x9e3779b1;
export const PRIME_B = 0x85ebca77;
export const PRIME_C = 0xc2b2ae3d;
export const PRIME_D = 0x27d4eb2f;
export const PRIME_E = 0x165667b1;

export function seed(s) {
  return add(s >>> 0, PRIME_E);
}

// Feed one integer into the accumulator.
export function eat(acc, data) {
  return mul(rotl(add(acc, mul(data >>> 0, PRIME_C)), 17), PRIME_D);
}

La multiplicación solo empuja la información hacia arriba: el bit más bajo de un producto depende solo de los bits más bajos de sus factores. La rotación devuelve hacia abajo los bits altos, ya bien mezclados. Toca una celda y lee el panel: cada línea es el acumulador después de un paso.

¿Es esto xxHash32 completo?

No. xxHash32 está hecho para digerir mensajes largos, así que lleva cuatro acumuladores en paralelo sobre franjas de 16 bytes. SmallXXHash solo come unos pocos enteros, así que la versión de Catlike Coding prescinde de esa maquinaria y se queda con la semilla, la ronda por entero y la avalancha final.

3. La avalancha

Tras el último paso de comer, el acumulador se revuelve una vez más: desplazar a la derecha y hacer XOR, multiplicar, y otra vez. El XOR con desplazamiento a la derecha deja que los bits altos influyan en los bajos; las multiplicaciones llevan los bajos hacia arriba. Unas pocas rondas hacen que cada bit de entrada llegue a cada bit de salida.

// Final mix: spread every input bit over the whole output.
export function avalanche(acc) {
  let h = acc;
  h = (h ^ (h >>> 15)) >>> 0;
  h = mul(h, PRIME_B);
  h = (h ^ (h >>> 13)) >>> 0;
  h = mul(h, PRIME_C);
  h = (h ^ (h >>> 16)) >>> 0;
  return h;
}

export function hash2(s, x, y) {
  return avalanche(eat(eat(seed(s), x), y));
}

Para ver lo que hace, cambia la escena a Sin avalanche, muestra el byte A y lee el panel. Las celdas vecinas ahora están correlacionadas, con r en torno a 0,3, y el χ² baja a unos 4, demasiado parejo para ser casualidad. La cuenta de bits de la leyenda apenas se mueve, y esa es la primera lección para probar hashes: un número sobre un par de celdas dice muy poco.

4. Dos hashes malos para comparar

El tercer modo multiplica cada coordenada por una constante impar grande y las suma. Es rápido y reparte los valores de forma pareja, pero su byte bajo es una función lineal de x e y, así que teje una trama regular.

// Multiply and add, no mixing: the low byte is a linear function of x and y.
function naive(s, x, y) {
  return (Math.imul(x, PRIME_A) + Math.imul(y, PRIME_B) + s) >>> 0;
}

function hashCell(x, y) {
  if (state.mode === "naive") return naive(state.seed, x, y);
  const acc = eat(eat(seed(state.seed), x), y);
  return state.mode === "raw" ? acc : avalanche(acc);
}

5. De un hash a una imagen

Un hash de 32 bits contiene cuatro bytes. Islands los lee por separado, así que un hash da hasta cuatro valores de aspecto independiente por celda. La escena muestra un byte cada vez.

// The four bytes Islands reads as BytesA…BytesD (A is the lowest).
export function byteOf(h, which) {
  return (h >>> (8 * which)) & 255;
}

Para dibujar, escribimos un píxel por celda en una imagen pequeña fuera de pantalla y luego la estiramos sobre el lienzo sin suavizado, para que cada celda siga siendo un cuadrado nítido. El mismo bucle llena el histograma.

// One pixel per cell in an offscreen image, then scaled up without smoothing.
off.width = cols; off.height = rows;
const img = octx.createImageData(cols, rows);
for (let j = 0; j < rows; j++) {
  for (let i = 0; i < cols; i++) {
    const b = byteOf(hashCell(state.ox + i, state.oy + j), state.byte);
    bins[b >> 4]++;
    const v = b / 255, k = 4 * (j * cols + i);
    img.data[k] = DARK[0] + (LIGHT[0] - DARK[0]) * v;
    …
  }
}
octx.putImageData(img, 0, 0);
ctx.imageSmoothingEnabled = false;
ctx.drawImage(off, 0, 0, cols * cs, rows * cs);

6. Medir un hash

El histograma divide los 256 valores posibles de un byte en 16 tramos. Si los valores fueran de verdad uniformes, cada tramo tendría más o menos 1/16 de las celdas. El estadístico χ² de Pearson suma las desviaciones al cuadrado respecto a eso: con 16 tramos promedia 15 para datos aleatorios, y queda entre unos 6 y 27 en el 95 % de los casos.

// Pearson's chi-squared against a flat histogram. For 16 bins, random data gives
// between about 6 and 27 in 95 % of cases; far lower means suspiciously even.
let chi = 0;
for (const c of bins) chi += (c - expected) ** 2 / expected;

Lo parejo no dice nada del orden, así que el segundo número compara cada celda con su vecina de la derecha. La correlación de Pearson r vale 0 cuando conocer un byte no dice nada del siguiente, y se acerca a ±1 cuando lo dice todo.

// Pearson correlation between each cell and its right-hand neighbour; near 0 for a good hash.
function neighbourCorrelation(cols, rows) {
  let n = 0, sa = 0, sb = 0, sab = 0, saa = 0, sbb = 0;
  for (let j = 0; j < rows; j++) {
    for (let i = 0; i + 1 < cols; i++) {
      const a = bytes[j * cols + i], b = bytes[j * cols + i + 1];
      n++; sa += a; sb += b; sab += a * b; saa += a * a; sbb += b * b;
    }
  }
  const cov = sab / n - (sa / n) * (sb / n);
  const va = saa / n - (sa / n) ** 2, vb = sbb / n - (sb / n) ** 2;
  return va > 0 && vb > 0 ? cov / Math.sqrt(va * vb) : 0;
}

La cuenta de bits de la leyenda hace XOR entre los hashes de la celda elegida y su vecina, y cuenta los unos. Es la prueba más barata y, como muestra la escena, la más débil.

const h = hashCell(x, y);
const hn = hashCell(x + 1, y);
const flips = popcount((h ^ hn) >>> 0);

¿Por qué el histograma del hash ingenuo es tan plano?

Porque la prueba solo cuenta cuántas veces sale cada valor, no dónde. Multiplicar por un número impar es una biyección módulo 256, así que, al avanzar x por una fila, el byte bajo recorre los valores de forma casi perfectamente pareja, mucho más de lo que daría el azar. Una prueba que mirara pares de vecinas lo pillaría al momento, y las baterías de pruebas reales hacen justo eso, con miles de pruebas así.

7. Una rejilla sin bordes

No se guarda nada, así que la rejilla es solo una ventana: ox y oy dicen qué celda ocupa la esquina superior izquierda. Arrastrar los cambia; tocar convierte una posición de la pantalla en una celda con floor, que además trata bien las coordenadas negativas. Las líneas naranjas marcan x = 0 e y = 0.

function cellAt(ev) {
  const r = canvas.getBoundingClientRect();
  const cs = cellSize() / dpr;
  return {
    x: state.ox + Math.floor((ev.clientX - r.left) / cs),
    y: state.oy + Math.floor((ev.clientY - r.top) / cs),
  };
}

Para ir más lejos

Hashear cuatro celdas a la vez. SmallXXHash4 de Islands hace los mismos pasos en cuatro carriles con instrucciones SIMD; en JavaScript puedes agrupar con arrays tipados y medir la ganancia.
Portarlo a un shader. GLSL ES 3.0 tiene enteros de 32 bits sin signo, y Jarzynski y Olano comparan xxhash32 con opciones más rápidas para GPU, como pcg3d.
Convertir el hash en ruido. Pon un valor hasheado en cada punto de la red y mezcla entre ellos con suavidad: eso es el ruido de valor, la siguiente página de esta serie.

SourcesFuentes

J. Flick, "Pseudorandom Noise: Hashing", Catlike Coding (2021). The design Islands.Noise follows; code under MIT-0. catlikecoding.com/unity/tutorials/pseudorandom-noise/hashing/
Y. Collet, "xxHash fast digest algorithm", specification (XXH32 primes and avalanche). github.com/Cyan4973/xxHash/blob/dev/doc/xxhash_spec.md
M. Jarzynski, M. Olano, "Hash Functions for GPU Rendering", Journal of Computer Graphics Techniques 9(3) (2020). jcgt.org/published/0009/03/02/
A. F. Webster, S. E. Tavares, "On the Design of S-Boxes", Advances in Cryptology — CRYPTO '85, LNCS 218, 523–534. Defines the strict avalanche criterion. doi.org/10.1007/3-540-39799-X_41
J. L. Carter, M. N. Wegman, "Universal classes of hash functions", J. Comput. Syst. Sci. 18(2) (1979) 143–154. doi.org/10.1016/0022-0000(79)90044-8
A. Appleby, SMHasher: test suite for non-cryptographic hash functions. github.com/aappleby/smhasher
K. Perlin, "An image synthesizer", SIGGRAPH '85, Computer Graphics 19(3) 287–296. doi.org/10.1145/325165.325247
K. Perlin, "Improving noise", ACM Trans. Graph. 21(3) (2002) 681–682. doi.org/10.1145/566654.566636

Part of Islands Lab. Tutorial format and noise design after Catlike Coding.Parte de Islands Lab. Formato de tutorial y diseño del ruido según Catlike Coding.