pext_phf.c

/**
 * Use the PEXT instruction and perfect hash functions to store small integer maps
 * inside a uint64_t (or smaller).
 * 
 * Compile with `-Wno-multichar -mbmi2 -mlzcnt` (or -march=native on any recent x86 CPU).
 * 
 * Modify `tbl` below to change the map.
 * 
 * If it takes a long time and doesn't find a solution, fiddle with the hash function (`h`).
 * 
 * The output is a single expression that encodes the table, and when passed a `key` will
 * evaluate to the corresponding value in `tbl`.
 * 
 * You may do whatever you want with this code, asie from the pcg32_random() function which
 * is under the Apache License 2.0 as noted below.
 */

#include <immintrin.h>
#include <inttypes.h>
#include <stdlib.h>
#include <stdio.h>

struct pcg32_random_state { uint64_t state; };

uint32_t pcg32_random(struct pcg32_random_state *rng)
{
	/**
	 * (c) 2014 M.E. O'Neill / pcg-random.org
	 * Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
	 */
	uint64_t s;
	uint32_t xorshift, rot;

	s = rng->state;
	rng->state = s * 6364136223846793005ull + 0x55ull;
	xorshift = ((s >> 18) ^ s) >> 27;
	rot = s >> 59;
	return (xorshift >> rot) | (xorshift << (-rot & 31));
}

struct record {
	uint32_t key;
	uint8_t value;
} tbl[] = {
	// modify this to change the map
	// keys must be exactly 4 bytes
	{'\0one', 1},
	{'\0two', 2},
	{'tree', 3},
	{'four', 4},
	{'five', 5},
	{'\0six', 6},
	{'sevn', 7},
	{'eigt', 8},
	{'nine', 9},
};
const size_t N = sizeof tbl / sizeof(struct record);

struct pair {
	uint64_t m, c;
};

// modify this to try other hash functions
// (H_STR is only for printing at the end, but for the sake of the output not being too
// confusing it should mirror `h`).
#define H_STR "(uint64_t)key * 0x%" PRIx32 "ull >> 32"
uint64_t h(uint64_t x, uint64_t k)
{
	return x * k >> 32;
}

int main(int argc, const char **argv)
{
	uint32_t x;
	struct pair cs[N];
	uint64_t c;
	struct pcg32_random_state rng;

	rng.state = 0u;
	pcg32_random(&rng);
	rng.state += 42u;
	pcg32_random(&rng);

RETRY:
	x = pcg32_random(&rng);

	for (size_t i = 0; i < N; ++i) {
		const uint64_t k = (uint64_t)tbl[i].key;
		const uint8_t v = tbl[i].value;
		uint64_t mask = h(x, k);
		if (__builtin_popcountll(mask) < 32 - __builtin_ia32_lzcnt_u32(v)) {
			goto RETRY;
		}
		cs[i].m = mask;
		cs[i].c = _pdep_u64(v, mask);
	}

	c = 0;
	for (size_t i = 0; i < N; ++i) {
		for (size_t j = 0; j < N; ++j) {
			const uint64_t m = cs[i].m & cs[j].m;
			if (_pext_u64(cs[i].c, m) != _pext_u64(cs[j].c, m)) {
				goto RETRY;
			}
		}
		c |= cs[i].c;
	}

	printf("_pext_u64(0x%" PRIx64 "ull, " H_STR ")", c, x);
}