Collisions produced by primitives based on wide multiplication (32*32->64)

wmul-collisions.c

// Copyright (c) 2019 Alexey Tourbin
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

// The hashing primitive based on wide multiplication,
//	lo(x * PRIME) ^ hi(x * PRIME),
// is not invertible.  This program counts the total number of collisions
// produced by the primitive by exhaustively testing all of the 32-bit inputs.
// The program can also be used to demonstrate (with -DOP=+) that ADD rather
// than XOR would be a much better choice to combine the lo and hi halves.
// The program requires 1GB of RAM and takes about 1 minute to complete.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>

#ifndef PRIME
#define PRIME 2654435761
#endif
#ifndef OP
#define OP ^
#endif

// the primitive that we're testing
static inline uint32_t wmul(uint32_t x)
{
    uint64_t w = x * (uint64_t) PRIME;
    return (w >> 32) OP (uint32_t) w;
}

int main()
{
    // 2-bit saturated counter for 2^32 possible hash values
    uint32_t *set = calloc(1, 1 << 30);
    assert(set);

    uint32_t i = 0;
    uint32_t collisions[3] = { 0, 0, 0 };
    do {
	// prefetch ahead of time
	uint32_t x9 = wmul(i + 16);
	// 16 slots per bucket
	uint32_t *b9 = &set[x9 / 16];
	__builtin_prefetch(b9);

	uint32_t x = wmul(i);
	uint32_t *bucket = &set[x / 16];
	uint32_t shift = (x % 16) * 2;
	switch ((*bucket >> shift) & 3) {
	case 0:
	    *bucket |= (1 << shift);
	    break;
	case 1:
	    *bucket += (1 << shift);
	    collisions[0]++;
	    break;
	case 2:
	    *bucket |= (1 << shift);
	    collisions[0]++;
	    collisions[1]++;
	    break;
	case 3:
	    collisions[0]++;
	    collisions[1]++;
	    collisions[2]++;
	    break;
	}
    } while (++i);

    printf("%u pairwise collisions\n", collisions[0]);
    printf("%u triple collisions\n", collisions[1]);
    printf("%u 4+ collisions\n", collisions[2]);
    return 0;
}