noise() hash-function exhibits geometric self-similarity

noise() hash-function exhibits geometric self-similarity

I did a quick analysis of the hash function used in noise() that is used to map from 3D integer coordinates to 1D indices. In essence this is

let of = (xi + (yi << PERLIN_YWRAPB) + (zi << PERLIN_ZWRAPB)) & PERLIN_SIZE

According to quick analysis it distributes input locations uniformly to PERLIN_SIZE which is a good thing :), but when I colored a 2048x2048 image according to the resulting hashed indices I get

where same colors mean same hash values. Here is a top-left zoom of the same image.

What does this mean? For input locations that obey a geometric pattern, the randomness of the noise might be reduced.
If instead, one changes the hash-function to something along the following lines

let of = p[(p[(p[xi & PERLIN_SIZE] + yi) & PERLIN_SIZE] +zi) & PERLIN_SIZE]

where p is permutation table of size PERLIN_SIZE, one gets

Note, I'm unsure if this problem is only of theoretical nature or has been observed practically as well. In case you revise your algorithm anyway, you might want to reconsider the hash function as well. I'm attaching my Python test script for reference.

# Christoph Heindl, https://github.com/cheind/, 2024
import numpy as np
import matplotlib.pyplot as plt

PERLIN_YWRAPB = 7
PERLIN_ZWRAPB = 8
PERLIN_SIZE = 4095
P = np.random.permutation(PERLIN_SIZE)

# Current hash
# def hash_fn(x: np.ndarray):
#     return (
#         x[..., 0]
#         + np.left_shift(x[..., 1], PERLIN_YWRAPB)
#         + np.left_shift(x[..., 2], PERLIN_ZWRAPB)
#     ) & PERLIN_SIZE


# Proposed hash
def hash_fn(x: np.ndarray):
    u = P[x[..., 0] % PERLIN_SIZE]
    v = P[(u + x[..., 1]) % PERLIN_SIZE]
    w = P[(v + x[..., 2]) % PERLIN_SIZE]
    return w


n = 2048
grid = np.stack(np.meshgrid(np.arange(n), np.arange(n)), -1)
grid = np.concatenate((grid, np.zeros((n, n, 1))), -1).astype(int)
h = hash_fn(grid).reshape(-1)

# Check for uniformity
values, counts = np.unique(h, return_counts=True)
plt.vlines(values, 0, counts, color="C0", lw=4)
plt.show()

# Colorize based on hash value to detect geometric similarities
plt.imshow(h.reshape(n, n) / (PERLIN_SIZE - 1))
plt.show()

Start with the noise() implementation and the hash expression shown in the issue, then run the attached Python script to reproduce the geometric patterns and distribution checks. Done means determining whether the pattern affects practical noise output and, if a change is justified, validating the revised hash against the same checks and visual comparison.