Fonctions de hash

Une Hash function est un algorithme qui transforme un entier en un autre entier qui semble aléatoire mais est entièrement déterministe. C'est la brique fondamentale du bruit procédural, de la génération de terrain, et de tout ce qui nécessite du "pseudo-aléatoire reproductible" sur GPU.

/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   ft_toupper.c                                       :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: rgraling <rgraling@student.s19.be>         +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2024/09/03 19:39:48 by rgraling          #+#    #+#             */
/*   Updated: 2024/09/03 20:02:35 by rgraling         ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

int ft_toupper(int c)
{
    if (c > 96 && c < 123)
        return (c - 32);
    return (c);
}

// Cette structure offre un temps de calcul de 𝑂⁡(𝑛)
unsigned int hash(const char* word)
{
    return ft_toupper(word[0]) - 'A';
}

L'idée est de prendre une valeur et de pouvoir produire une valeur qui devient un raccourci vers elle plus tard, devient plus petit et plus prévisible. Implémentée, une table de hachage est un tableau de pointeurs vers les nœuds.

// Illustration :
                -------------------------
  Yoshi  -->    |         hash()        |    -->  23
                -------------------------
// Yoshi   : une chaine de caractères de taille quelconque (const char *)
// 23      : un entier signé de taille fixe (toujours positif) (unsigned int)

On dit que cette fonction de hachage est non cryptographique et est très faible. Tous les mots commençant par la même lettre donnent la même valeur. Bref, ne l'utilise pas elle est nulle.

En tant que programmeur, vous devez prendre une décision sur les avantages d'utiliser plus de mémoire pour avoir une grande table de hachage et potentiellement réduire le temps de recherche ou d'utiliser moins de mémoire et potentiellement augmenter le temps de recherche.

Propriété essentielle — l'effet avalanche

Une bonne fonction de hash doit changer ~50% de ses bits de sortie quand un seul bit d'entrée change. C'est l'effet avalanche.

// Input:  00000000000000000000000000000001
// Output: 10110101011010010011010110101011  ← ~50% des bits changent
//
// Input:  00000000000000000000000000000010  (1 seul bit décalé)
// Output: 01101010110100100110101101010110  ← complètement différent
//
// Sans effet avalanche : des patterns apparaissent dans le bruit (rayures, grilles)

5 Fonctions pour un fichier Utils.metal

hashPerlin — Wellons / Schechter-Bridson

// Chris Wellons — excellent équilibre vitesse/qualité
inline uint hashPerlin(uint x)
{
    x = ((x >> 16) ^ x) * 0x45d9f3b;  // mélange les bits hauts dans les bas
    x = ((x >> 16) ^ x) * 0x45d9f3b;  // deuxième passe (améliore l'avalanche)
    x = (x >> 16) ^ x;                 // finalisation
    return x;
}
// Qualité : ★★★★☆ — Très bon, utilisable pour le bruit Perlin
// Vitesse  : ★★★★★ — 3 multiplications, 3 XOR

murmur — MurmurHash3 finalizer

// Austin Appleby / Thomas Wang — considéré "excellent" en qualité statistique
inline uint murmur(uint x)
{
    x ^= x >> 16;
    x *= 0x85ebca6b;  // constante choisie pour maximiser l'avalanche
    x ^= x >> 13;
    x *= 0xc2b2ae35;
    x ^= x >> 16;
    return x;
}
// C'est le finalizer de MurmurHash3 — extrait pour un usage seul
// Qualité : ★★★★★ — Excellent, passe les tests SmallCrush
// Vitesse  : ★★★★☆ — 2 multiplications, 3 XOR-shift

pcg — PCG-like

// Inspiré de PCG (Melissa O'Neill) — très bonne qualité
inline uint pcg(uint x)
{
    uint state = x * 747796405u + 2891336453u;  // LCG step
    uint word  = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u; // output mix
    return (word >> 22u) ^ word;
}
// Qualité : ★★★★★ — Excellent, rotation dépendante de l'état = très difficile à prédire
// Vitesse  : ★★★☆☆ — Plus lourd : shift variable selon l'état

wang / wang_hash — Wang hash

// Thomas Wang — classique du GPU, largement utilisé en shaders
inline uint wang(uint x)
{
    x = (x ^ 61u) ^ (x >> 16u);
    x *= 9u;
    x ^= x >> 4u;
    x *= 0x27d4eb2du;
    x ^= x >> 15u;
    return x;
}
// Ton fichier a deux versions identiques (wang et wang_hash) — même algorithme
// Qualité : ★★★★☆ — Très bon, quelques patterns mineurs à haute fréquence
// Vitesse  : ★★★★☆ — 2 multiplications, 3 XOR-shift

lcg — Linear Congruential Generator

// Simple — LCG classique
inline uint lcg(uint x)
{
    return x * 1664525u + 1013904223u;
}
// ⚠ Qualité : ★★☆☆☆ — MÉDIOCRE
// Produit des patterns en diagonale visibles dans le bruit
// Les bits de poids faible sont très peu aléatoires
// Utiliser seulement comme générateur de séquence, JAMAIS pour du bruit spatial

Comparaison — quand utiliser quoi

hash2D et hash3D — combiner des dimensions

// hash2(uint2) — combine x et y :
inline uint hash2(uint2 v)
{
    return hashPerlin(v.x ^ hashPerlin(v.y));
}
// XOR naïf sans hashing préalable serait catastrophique :
// hash(x ^ y) → (1,2) et (2,1) donnent le même résultat → aliasing de biomes

// hash3(uint3) — même principe :
inline uint hash3(uint3 v)
{
    return hashPerlin(v.x ^ hashPerlin(v.y ^ hashPerlin(v.z)));
}

// hashToFloat — convertir en float [0, 1] :
inline float hashToFloat(uint h)
{
    return float(h) / float(0xFFFFFFFF);  // divise par 2^32-1
}
// Utilisation dans voronoi2D pour créer les points de cellule

Seed — rendre le hash reproductible

// Le seed permet de générer des mondes différents avec la même fonction

// Mauvais — le seed affecte peu les bits bas :
uint h = hashPerlin(x + seed);  // si seed = 0 et seed = 1 → très similaire

// Bon — hasher le seed d'abord :
uint h = hashPerlin(x ^ murmur(seed));

// Dans ton fbm2D :
// seed + i * 1337  → chaque octave a un seed différent
// Le 1337 est arbitraire — n'importe quel entier impair marche
// Important : ne pas utiliser seed + i * 2 (trop corrélé)

NoiseParams — la structure de paramètres

// Dans Helpers.metal :
struct NoiseParams
{
    float2   worldOffset; // décalage dans le monde (streaming de chunks)
    float    scale;       // zoom du bruit (plus grand = plus lisse)
    uint     biomeId;     // influence les paramètres de bruit par biome
    uint64_t seed;        // graine globale du monde
};

// À passer en constant buffer :
constant NoiseParams& params [[buffer(2)]]

float h = fbm2D((worldPos.xz + params.worldOffset) * params.scale, 6, 0.5, 2.0, (uint)params.seed ^ params.biomeId);

Tests de qualité — SmallCrush

Pour valider une fonction de hash GPU, la référence est TestU01 (SmallCrush / BigCrush). murmur et pcg passent les deux. lcg échoue à SmallCrush.

// Règle simple : si tu vois des patterns dans ton bruit
// (lignes, grilles, répétitions) → change la fonction de hash
// La plupart du temps : hashPerlin ou murmur règlent le problème