phf.cc

/* ==========================================================================
 * phf.cc - Tiny perfect hash function library.
 * --------------------------------------------------------------------------
 * Copyright (c) 2014-2015, 2019  William Ahern
 *
 * 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.
 * ==========================================================================
 */
#include <limits.h>   /* CHAR_BIT SIZE_MAX */
#include <inttypes.h> /* PRIu32 PRIu64 PRIx64 */
#include <stdint.h>   /* UINT32_C UINT64_C uint32_t uint64_t */
#include <stdlib.h>   /* abort(3) calloc(3) free(3) qsort(3) */
#include <string.h>   /* memset(3) */
#include <errno.h>    /* errno */
#include <assert.h>   /* assert(3) */

#if !PHF_NO_LIBCXX
#include <algorithm>   /* std::sort */
#include <iterator>    /* std::begin std::end */
#include <new>         /* std::nothrow */
#include <string>      /* std::string */
#endif
#include <type_traits> /* std::is_standard_layout std::is_trivial */
#include <utility>     /* std::move */

#include "phf.h"


#ifndef PHF_HAVE_ATTRIBUTE_FALLTHROUGH
#define PHF_HAVE_ATTRIBUTE_FALLTHROUGH phf_has_attribute(fallthrough)
#endif

#if PHF_HAVE_ATTRIBUTE_FALLTHROUGH
#define PHF_FALLTHROUGH __attribute__((fallthrough))
#else
#define PHF_FALLTHROUGH (void)0 /* fall through */
#endif

#ifdef __clang__
#pragma clang diagnostic ignored "-Wunused-function"
#pragma clang diagnostic ignored "-Wunused-label"
#if __cplusplus < 201103L
#pragma clang diagnostic ignored "-Wc++11-long-long"
#endif
#elif PHF_GNUC_PREREQ(4, 6)
#pragma GCC diagnostic ignored "-Wunused-function"
#pragma GCC diagnostic ignored "-Wunused-label"
#if __cplusplus < 201103L
#pragma GCC diagnostic ignored "-Wlong-long"
#pragma GCC diagnostic ignored "-Wformat" // %zu
#endif
#endif


/*
 * M A C R O  R O U T I N E S
 *
 * Mostly copies of <sys/param.h>
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#define PHF_BITS(T) (sizeof (T) * CHAR_BIT)
#define PHF_HOWMANY(x, y) (((x) + ((y) - 1)) / (y))
#define PHF_MIN(a, b) (((a) < (b))? (a) : (b))
#define PHF_MAX(a, b) (((a) > (b))? (a) : (b))
#define PHF_ROTL(x, y) (((x) << (y)) | ((x) >> (PHF_BITS(x) - (y))))
#define PHF_COUNTOF(a) (sizeof (a) / sizeof *(a))

#if PHF_NO_LIBCXX
#define PHF_IFELSE_LIBCXX(a, b) b
#else
#define PHF_IFELSE_LIBCXX(a, b) a
#endif


/*
 * A L L O C A T I O N  R O U T I N E S
 *
 * C allocation semantics in a nominally safe manner for C++.
 *
 * NOTE: phf.cc wasn't written as a proper C++ library, but refactored from
 * C to C++ primarily to make use of templates for the convenience of the
 * command-line utility, and secondarily as a C++ learning exercise.
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

template<typename T>
static phf_error_t phf_calloc(T **p, size_t count)
{
#if !PHF_NO_LIBCXX
	if (!std::is_trivially_copyable<T>::value) {
		if (SIZE_MAX / sizeof **p < count)
			return ENOMEM;

		if (!(*p = static_cast<T*>(malloc(count * sizeof **p))))
			return errno;

		for (size_t i = 0; i < count; i++)
			new (&(*p)[i]) T;

		return 0;
	}
#else
	static_assert(std::is_standard_layout<T>::value && std::is_trivial<T>::value, "compiled without C++ runtime support");
#endif
	if (!(*p = static_cast<T*>(calloc(count, sizeof **p))))
		return errno;

	return 0;
} /* phf_calloc() */

template<typename T>
static void phf_freearray(T *p, size_t count)
{
#if !PHF_NO_LIBCXX
	if (!std::is_trivially_destructible<T>::value) {
		for (size_t i = 0; i < count; i++)
			p[i].~T();
	}
#else
	static_assert(std::is_standard_layout<T>::value && std::is_trivial<T>::value, "compiled without C++ runtime support");
#endif
	(void)count;
	free(p);
} /* phf_freearray() */


/*
 * M O D U L A R  A R I T H M E T I C  R O U T I N E S
 *
 * Two modular reduction schemes are supported: bitwise AND and naive
 * modular division. For bitwise AND we must round up the values r and m to
 * a power of 2.
 *
 * TODO: Implement and test Barrett reduction as alternative to naive
 * modular division.
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/* round up to nearest power of 2 */
static inline size_t phf_powerup(size_t i) {
#if defined SIZE_MAX
	i--;
	i |= i >> 1;
	i |= i >> 2;
	i |= i >> 4;
	i |= i >> 8;
	i |= i >> 16;
#if SIZE_MAX != 0xffffffffu
	i |= i >> 32;
#endif
	return ++i;
#else
#error No SIZE_MAX defined
#endif
} /* phf_powerup() */

static inline uint64_t phf_a_s_mod_n(uint64_t a, uint64_t s, uint64_t n) {
	uint64_t v;

	assert(n <= UINT32_MAX);

	v = 1;
	a %= n;

	while (s > 0) {
		if (s % 2 == 1)
			v = (v * a) % n;
		a = (a * a) % n;
		s /= 2;
	}

	return v;
} /* phf_a_s_mod_n() */

/*
 * Rabin-Miller primality test adapted from Niels Ferguson and Bruce
 * Schneier, "Practical Cryptography" (Wiley, 2003), 201-204.
 */
static inline bool phf_witness(uint64_t n, uint64_t a, uint64_t s, uint64_t t) {
	uint64_t v, i;

	assert(a > 0 && a < n);
	assert(n <= UINT32_MAX);

	if (1 == (v = phf_a_s_mod_n(a, s, n)))
		return 1;

	for (i = 0; v != n - 1; i++) {
		if (i == t - 1)
			return 0;
		v = (v * v) % n;
	}

	return 1;
} /* phf_witness() */

static inline bool phf_rabinmiller(uint64_t n) {
	/*
	 * Witness 2 is deterministic for all n < 2047. Witnesses 2, 7, 61
	 * are deterministic for all n < 4,759,123,141.
	 */
	static const int witness[] = { 2, 7, 61 };
	uint64_t s, t, i;

	assert(n <= UINT32_MAX);

	if (n < 3 || n % 2 == 0)
		return 0;

	/* derive 2^t * s = n - 1 where s is odd */
	s = n - 1;
	t = 0;
	while (s % 2 == 0) {
		s /= 2;
		t++;
	}

	/* NB: witness a must be 1 <= a < n */
	if (n < 2047)
		return phf_witness(n, 2, s, t);

	for (i = 0; i < PHF_COUNTOF(witness); i++) {
		if (!phf_witness(n, witness[i], s, t))
			return 0;
	}

	return 1;
} /* phf_rabinmiller() */

static inline bool phf_isprime(size_t n) {
	static const char map[] = { 0, 0, 2, 3, 0, 5, 0, 7 };
	size_t i;

	if (n < PHF_COUNTOF(map))
		return map[n];

	for (i = 2; i < PHF_COUNTOF(map); i++) {
		if (map[i] && (n % map[i] == 0))
			return 0;
	}

	return phf_rabinmiller(n);
} /* phf_isprime() */

static inline size_t phf_primeup(size_t n) {
	/* NB: 4294967291 is largest 32-bit prime */
	if (n > 4294967291)
		return 0;

	while (n < SIZE_MAX && !phf_isprime(n))
		n++;

	return n;
} /* phf_primeup() */


/*
 * B I T M A P  R O U T I N E S
 *
 * We use a bitmap to track output hash occupancy when searching for
 * displacement values.
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

typedef unsigned long phf_bits_t;

static inline bool phf_isset(phf_bits_t *set, size_t i) {
	return set[i / PHF_BITS(*set)] & ((size_t)1 << (i % PHF_BITS(*set)));
} /* phf_isset() */

static inline void phf_setbit(phf_bits_t *set, size_t i) {
	set[i / PHF_BITS(*set)] |= ((size_t)1 << (i % PHF_BITS(*set)));
} /* phf_setbit() */

static inline void phf_clrbit(phf_bits_t *set, size_t i) {
	set[i / PHF_BITS(*set)] &= ~((size_t)1 << (i % PHF_BITS(*set)));
} /* phf_clrbit() */

static inline void phf_clrall(phf_bits_t *set, size_t n) {
	memset(set, '\0', PHF_HOWMANY(n, PHF_BITS(*set)) * sizeof *set);
} /* phf_clrall() */


/*
 * K E Y  D E D U P L I C A T I O N
 *
 * Auxiliary routine to ensure uniqueness of each key in array.
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

namespace PHF {
	namespace Uniq {
		static bool operator!=(const phf_string_t &a, const phf_string_t &b) {
			return a.n != b.n || 0 != memcmp(a.p, b.p, a.n);
		}

		template<typename T>
		static int cmp(const T *a, const T *b) {
			if (*a > *b)
				return -1;
			if (*a < *b)
				return 1;
			return 0;
		} /* cmp() */

		template<>
		int cmp(const phf_string_t *a, const phf_string_t *b) {
			int cmp;
			if ((cmp = memcmp(a->p, b->p, PHF_MIN(a->n, b->n))))
				return cmp;
			if (a->n > b->n)
				return -1;
			if (a->n < b->n)
				return 1;
			return 0;
		} /* cmp<phf_string_t>() */

		template<typename T>
		static void sort(T k[], const size_t n) {

#if !PHF_NO_LIBCXX
			if (!std::is_trivially_copyable<T>::value) {
				std::sort(k, &k[n]);
				return;
			}
#else
			static_assert(std::is_standard_layout<T>::value && std::is_trivial<T>::value, "compiled without C++ runtime support");
#endif
			qsort(k, n, sizeof *k, reinterpret_cast<int(*)(const void *, const void *)>(&cmp<T>));
		} /* sort() */
	} /* Uniq:: */
} /* PHF:: */

template<typename key_t>
PHF_PUBLIC size_t PHF::uniq(key_t k[], const size_t n) {
	using namespace PHF::Uniq;
	size_t i, j;

	sort<key_t>(k, n);

	for (i = 1, j = 0; i < n; i++) {
		if (k[i] != k[j])
			k[++j] = k[i];
	}

	return (n > 0)? j + 1 : 0;
} /* PHF::uniq() */

template size_t PHF::uniq<uint32_t>(uint32_t[], const size_t);
template size_t PHF::uniq<uint64_t>(uint64_t[], const size_t);
template size_t PHF::uniq<phf_string_t>(phf_string_t[], const size_t);
#if !PHF_NO_LIBCXX
template size_t PHF::uniq<std::string>(std::string[], const size_t);
#endif

PHF_PUBLIC size_t phf_uniq_uint32(uint32_t k[], const size_t n) {
	return PHF::uniq(k, n);
} /* phf_uniq_uint32() */

PHF_PUBLIC size_t phf_uniq_uint64(uint64_t k[], const size_t n) {
	return PHF::uniq(k, n);
} /* phf_uniq_uint64() */

PHF_PUBLIC size_t phf_uniq_string(phf_string_t k[], const size_t n) {
	return PHF::uniq(k, n);
} /* phf_uniq_string() */


/*
 * H A S H  P R I M I T I V E S
 *
 * Universal hash based on MurmurHash3_x86_32. Variants for 32- and 64-bit
 * integer keys, and string keys.
 *
 * We use a random seed to address the non-cryptographic-strength collision
 * resistance of MurmurHash3. A stronger hash like SipHash is just too slow
 * and unnecessary for my particular needs. For some environments a
 * cryptographically stronger hash may be prudent.
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

static inline uint32_t phf_round32(uint32_t k1, uint32_t h1) {
	k1 *= UINT32_C(0xcc9e2d51);
	k1 = PHF_ROTL(k1, 15);
	k1 *= UINT32_C(0x1b873593);

	h1 ^= k1;
	h1 = PHF_ROTL(h1, 13);
	h1 = h1 * 5 + UINT32_C(0xe6546b64);

	return h1;
} /* phf_round32() */

static inline uint32_t phf_round32(const unsigned char *p, size_t n, uint32_t h1) {
	uint32_t k1;

	while (n >= 4) {
		k1 = (p[0] << 24)
		   | (p[1] << 16)
		   | (p[2] << 8)
		   | (p[3] << 0);

		h1 = phf_round32(k1, h1);

		p += 4;
		n -= 4;
	}

	k1 = 0;

	switch (n & 3) {
	case 3:
		k1 |= p[2] << 8;
		PHF_FALLTHROUGH;
	case 2:
		k1 |= p[1] << 16;
		PHF_FALLTHROUGH;
	case 1:
		k1 |= p[0] << 24;
		h1 = phf_round32(k1, h1);
	}

	return h1;
} /* phf_round32() */

static inline uint32_t phf_round32(phf_string_t k, uint32_t h1) {
	return phf_round32(reinterpret_cast<const unsigned char *>(k.p), k.n, h1);
} /* phf_round32() */

#if !PHF_NO_LIBCXX
static inline uint32_t phf_round32(std::string k, uint32_t h1) {
	return phf_round32(reinterpret_cast<const unsigned char *>(k.c_str()), k.length(), h1);
} /* phf_round32() */
#endif

static inline uint32_t phf_mix32(uint32_t h1) {
	h1 ^= h1 >> 16;
	h1 *= UINT32_C(0x85ebca6b);
	h1 ^= h1 >> 13;
	h1 *= UINT32_C(0xc2b2ae35);
	h1 ^= h1 >> 16;

	return h1;
} /* phf_mix32() */


/*
 * g(k) & f(d, k)  S P E C I A L I Z A T I O N S
 *
 * For every key we first calculate g(k). Then for every group of collisions
 * from g(k) we search for a displacement value d such that f(d, k) places
 * each key into a unique hash slot.
 *
 * g() and f() are specialized for 32-bit, 64-bit, and string keys.
 *
 * g_mod_r() and f_mod_n() are specialized for the method of modular
 * reduction--modular division or bitwise AND. bitwise AND is substantially
 * faster than modular division, and more than makes up for any space
 * inefficiency, particularly for small hash tables.
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/* 32-bit, phf_string_t, and std::string keys */
template<typename T>
static inline uint32_t phf_g(T k, uint32_t seed) {
	uint32_t h1 = seed;

	h1 = phf_round32(k, h1);

	return phf_mix32(h1);
} /* phf_g() */

template<typename T>
static inline uint32_t phf_f(uint32_t d, T k, uint32_t seed) {
	uint32_t h1 = seed;

	h1 = phf_round32(d, h1);
	h1 = phf_round32(k, h1);

	return phf_mix32(h1);
} /* phf_f() */


/* 64-bit keys */
static inline uint32_t phf_g(uint64_t k, uint32_t seed) {
	uint32_t h1 = seed;

	h1 = phf_round32(k, h1);
	h1 = phf_round32(k >> 32, h1);

	return phf_mix32(h1);
} /* phf_g() */

static inline uint32_t phf_f(uint32_t d, uint64_t k, uint32_t seed) {
	uint32_t h1 = seed;

	h1 = phf_round32(d, h1);
	h1 = phf_round32(static_cast<uint32_t>(k), h1);
	h1 = phf_round32(static_cast<uint32_t>(k >> 32), h1);

	return phf_mix32(h1);
} /* phf_f() */


/* g() and f() which parameterize modular reduction */
template<bool nodiv, typename T>
static inline uint32_t phf_g_mod_r(T k, uint32_t seed, size_t r) {
	return (nodiv)? (phf_g(k, seed) & (r - 1)) : (phf_g(k, seed) % r);
} /* phf_g_mod_r() */

template<bool nodiv, typename T>
static inline uint32_t phf_f_mod_m(uint32_t d, T k, uint32_t seed, size_t m) {
	return (nodiv)? (phf_f(d, k, seed) & (m - 1)) : (phf_f(d, k, seed) % m);
} /* phf_f_mod_m() */


/*
 * B U C K E T  S O R T I N G  I N T E R F A C E S
 *
 * For every key [0..n) we calculate g(k) % r, where 0 < r <= n, and
 * associate it with a bucket [0..r). We then sort the buckets in decreasing
 * order according to the number of keys. The sorting is required for both
 * optimal time complexity when calculating f(d, k) (less contention) and
 * optimal space complexity (smaller d).
 *
 * The actual sorting is done in the core routine. The buckets are organized
 * and sorted as a 1-dimensional array to minimize run-time memory (less
 * data structure overhead) and improve data locality (less pointer
 * indirection). The following section merely implements a templated
 * bucket-key structure and the comparison routine passed to qsort(3).
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

static bool operator==(const phf_string_t &a, const phf_string_t &b) {
	return a.n == b.n && 0 == memcmp(a.p, b.p, a.n);
}

static bool operator<(const phf_string_t &a, const phf_string_t &b) {
	int cmp = memcmp(a.p, b.p, PHF_MIN(a.n, b.n));
	if (cmp)
		return cmp < 0;
	return a.n < b.n;
}

static bool operator>(const phf_string_t &a, const phf_string_t &b) {
	int cmp = memcmp(a.p, b.p, PHF_MIN(a.n, b.n));
	if (cmp)
		return cmp > 0;
	return a.n > b.n;
}

template<typename T>
struct phf_key {
	T k;
	phf_hash_t g; /* result of g(k) % r */
	size_t *n;  /* number of keys in bucket g */
}; /* struct phf_key */

template<typename T>
static int phf_keycmp(const phf_key<T> *a, const phf_key<T> *b) {
	if (*(a->n) > *(b->n))
		return -1;
	if (*(a->n) < *(b->n))
		return 1;
	if (a->g > b->g)
		return -1;
	if (a->g < b->g)
		return 1;

	/* duplicate key? */
	if (a->k == b->k && a != b) {
		assert(!(a->k == b->k));
		abort(); /* if NDEBUG defined */
	}

	return 0;
} /* phf_keycmp() */

template<typename T>
static bool operator>(const phf_key<T> &a, const phf_key<T> &b) {
	return phf_keycmp(&a, &b) > 0;
}

template<typename T>
static bool operator<(const phf_key<T> &a, const phf_key<T> &b) {
	return phf_keycmp(&a, &b) < 0;
}

template<typename T>
static void phf_keysort(phf_key<T> k[], const size_t n) {
#if !PHF_NO_LIBCXX
	if (!std::is_trivially_copyable<T>::value) {
		std::sort(k, &k[n]);
		return;
	}
#else
	static_assert(std::is_standard_layout<T>::value && std::is_trivial<T>::value, "compiled without C++ runtime support");
#endif
	qsort(k, n, sizeof *k, reinterpret_cast<int(*)(const void *, const void *)>(&phf_keycmp<T>));
} /* phf_keysort() */


/*
 * C O R E  F U N C T I O N  G E N E R A T O R
 *
 * The entire algorithm is contained in PHF:init. Everything else in this
 * source file is either a simple utility routine used by PHF:init, or an
 * interface to PHF:init or the generated function state.
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

template<typename key_t, bool nodiv>
PHF_PUBLIC int PHF::init(struct phf *phf, const key_t k[], const size_t n, const size_t l, const size_t a, const phf_seed_t seed) {
	size_t n1 = PHF_MAX(n, 1); /* for computations that require n > 0 */
	size_t l1 = PHF_MAX(l, 1);
	size_t a1 = PHF_MAX(PHF_MIN(a, 100), 1);
	size_t r; /* number of buckets */
	size_t m; /* size of output array */
	phf_key<key_t> *B_k = NULL; /* linear bucket-slot array */
	size_t *B_z = NULL;         /* number of slots per bucket */
	phf_key<key_t> *B_p, *B_pe;
	phf_bits_t *T = NULL; /* bitmap to track index occupancy */
	phf_bits_t *T_b;      /* per-bucket working bitmap */
	size_t T_n;
	uint32_t *g = NULL; /* displacement map */
	uint32_t d_max = 0; /* maximum displacement value */
	int error;

	if ((phf->nodiv = nodiv)) {
		/* round to power-of-2 so we can use bit masks instead of modulo division */
		r = phf_powerup(n1 / PHF_MIN(l1, n1));
		m = phf_powerup((n1 * 100) / a1);
	} else {
		r = phf_primeup(PHF_HOWMANY(n1, l1));
		/* XXX: should we bother rounding m to prime number for small n? */
		m = phf_primeup((n1 * 100) / a1);
	}

	if (r == 0 || m == 0)
		return ERANGE;

	if ((error = phf_calloc(&B_k, n1)))
		goto error;
	if (!(B_z = static_cast<size_t *>(calloc(r, sizeof *B_z))))
		goto syerr;

	for (size_t i = 0; i < n; i++) {
		phf_hash_t g = phf_g_mod_r<nodiv>(k[i], seed, r);

		B_k[i].k = k[i];
		B_k[i].g = g;
		B_k[i].n = &B_z[g];
		++*B_k[i].n;
	}

	phf_keysort(B_k, n1);

	T_n = PHF_HOWMANY(m, PHF_BITS(*T));
	if (!(T = static_cast<phf_bits_t *>(calloc(T_n * 2, sizeof *T))))
		goto syerr;
	T_b = &T[T_n]; /* share single allocation */

	/*
	 * FIXME: T_b[] is unnecessary. We could clear T[] the same way we
	 * clear T_b[]. In fact, at the end of generation T_b[] is identical
	 * to T[] because we don't clear T_b[] on success.
	 *
	 * We just need to tweak the current reset logic to stop before the
	 * key that failed, and then we can elide the commit to T[] at the
	 * end of the outer loop.
	 */

	if (!(g = static_cast<uint32_t *>(calloc(r, sizeof *g))))
		goto syerr;

	B_p = B_k;
	B_pe = &B_k[n];

	for (; B_p < B_pe && *B_p->n > 0; B_p += *B_p->n) {
		phf_key<key_t> *Bi_p, *Bi_pe;
		size_t d = 0;
		uint32_t f;
retry:
		d++;
		Bi_p = B_p;
		Bi_pe = B_p + *B_p->n;

		for (; Bi_p < Bi_pe; Bi_p++) {
			f = phf_f_mod_m<nodiv>(d, Bi_p->k, seed, m);

			if (phf_isset(T, f) || phf_isset(T_b, f)) {
				/* reset T_b[] */
				for (Bi_p = B_p; Bi_p < Bi_pe; Bi_p++) {
					f = phf_f_mod_m<nodiv>(d, Bi_p->k, seed, m);
					phf_clrbit(T_b, f);
				}

				goto retry;
			} else {
				phf_setbit(T_b, f);
			}
		}

		/* commit to T[] */
		for (Bi_p = B_p; Bi_p < Bi_pe; Bi_p++) {
			f = phf_f_mod_m<nodiv>(d, Bi_p->k, seed, m);
			phf_setbit(T, f);
		}

		/* commit to g[] */
		g[B_p->g] = d;
		d_max = PHF_MAX(d, d_max);
	}

	phf->seed = seed;
	phf->r = r;
	phf->m = m;

	phf->g = g;
	g = NULL;

	phf->d_max = d_max;
	phf->g_op = (nodiv)? phf::PHF_G_UINT32_BAND_R : phf::PHF_G_UINT32_MOD_R;
	phf->g_jmp = NULL;

	error = 0;

	goto clean;
syerr:
	error = errno;
error:
	(void)0;
clean:
	free(g);
	free(T);
	free(B_z);
	phf_freearray(B_k, n1);

	return error;
} /* PHF::init() */


/*
 * D I S P L A C E M E N T  M A P  C O M P A C T I O N
 *
 * By default the displacement map is an array of uint32_t. This routine
 * compacts the map by using the smallest primitive type that will fit the
 * largest displacement value.
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

template<typename dst_t, typename src_t>
static inline void phf_memmove(dst_t *dst, src_t *src, size_t n) {
	for (size_t i = 0; i < n; i++) {
		dst_t tmp = src[i];
		dst[i] = tmp;
	}
} /* phf_memmove() */

PHF_PUBLIC void PHF::compact(struct phf *phf) {
	size_t size = 0;
	void *tmp;

	switch (phf->g_op) {
	case phf::PHF_G_UINT32_MOD_R:
	case phf::PHF_G_UINT32_BAND_R:
		break;
	default:
		return; /* already compacted */
	}

	if (phf->d_max <= 255) {
		phf_memmove(reinterpret_cast<uint8_t *>(phf->g), reinterpret_cast<uint32_t *>(phf->g), phf->r);
		phf->g_op = (phf->nodiv)? phf::PHF_G_UINT8_BAND_R : phf::PHF_G_UINT8_MOD_R;
		size = sizeof (uint8_t);
	} else if (phf->d_max <= 65535) {
		phf_memmove(reinterpret_cast<uint16_t *>(phf->g), reinterpret_cast<uint32_t *>(phf->g), phf->r);
		phf->g_op = (phf->nodiv)? phf::PHF_G_UINT16_BAND_R : phf::PHF_G_UINT16_MOD_R;
		size = sizeof (uint16_t);
	} else {
		return; /* nothing to compact */
	}

	/* simply keep old array if realloc fails */
	if ((tmp = realloc(phf->g, phf->r * size)))
		phf->g = static_cast<uint32_t *>(tmp);
} /* PHF::compact() */


/*
 * F U N C T I O N  G E N E R A T O R  &  S T A T E  I N T E R F A C E S
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

template int PHF::init<uint32_t, true>(struct phf *, const uint32_t[], const size_t, const size_t, const size_t, const phf_seed_t);
template int PHF::init<uint64_t, true>(struct phf *, const uint64_t[], const size_t, const size_t, const size_t, const phf_seed_t);
template int PHF::init<phf_string_t, true>(struct phf *, const phf_string_t[], const size_t, const size_t, const size_t, const phf_seed_t);
#if !PHF_NO_LIBCXX
template int PHF::init<std::string, true>(struct phf *, const std::string[], const size_t, const size_t, const size_t, const phf_seed_t);
#endif

template int PHF::init<uint32_t, false>(struct phf *, const uint32_t[], const size_t, const size_t, const size_t, const phf_seed_t);
template int PHF::init<uint64_t, false>(struct phf *, const uint64_t[], const size_t, const size_t, const size_t, const phf_seed_t);
template int PHF::init<phf_string_t, false>(struct phf *, const phf_string_t[], const size_t, const size_t, const size_t, const phf_seed_t);
#if !PHF_NO_LIBCXX
template int PHF::init<std::string, false>(struct phf *, const std::string[], const size_t, const size_t, const size_t, const phf_seed_t);
#endif

template<bool nodiv, typename map_t, typename key_t>
static inline phf_hash_t phf_hash_(map_t *g, key_t k, uint32_t seed, size_t r, size_t m) {
	if (nodiv) {
		uint32_t d = g[phf_g(k, seed) & (r - 1)];

		return phf_f(d, k, seed) & (m - 1);
	} else {
		uint32_t d = g[phf_g(k, seed) % r];

		return phf_f(d, k, seed) % m;
	}
} /* phf_hash_() */

template<typename T>
PHF_PUBLIC phf_hash_t PHF::hash(struct phf *phf, T k) {
#if PHF_HAVE_COMPUTED_GOTOS && !PHF_NO_COMPUTED_GOTOS
	static const void *const jmp[] = {
		NULL,
		&&uint8_mod_r, &&uint8_band_r,
		&&uint16_mod_r, &&uint16_band_r,
		&&uint32_mod_r, &&uint32_band_r,
	};

	goto *((phf->g_jmp)? phf->g_jmp : (phf->g_jmp = jmp[phf->g_op]));

	uint8_mod_r:
		return phf_hash_<false>(reinterpret_cast<uint8_t *>(phf->g), k, phf->seed, phf->r, phf->m);
	uint8_band_r:
		return phf_hash_<true>(reinterpret_cast<uint8_t *>(phf->g), k, phf->seed, phf->r, phf->m);
	uint16_mod_r:
		return phf_hash_<false>(reinterpret_cast<uint16_t *>(phf->g), k, phf->seed, phf->r, phf->m);
	uint16_band_r:
		return phf_hash_<true>(reinterpret_cast<uint16_t *>(phf->g), k, phf->seed, phf->r, phf->m);
	uint32_mod_r:
		return phf_hash_<false>(reinterpret_cast<uint32_t *>(phf->g), k, phf->seed, phf->r, phf->m);
	uint32_band_r:
		return phf_hash_<true>(reinterpret_cast<uint32_t *>(phf->g), k, phf->seed, phf->r, phf->m);
#else
	switch (phf->g_op) {
	case phf::PHF_G_UINT8_MOD_R:
		return phf_hash_<false>(reinterpret_cast<uint8_t *>(phf->g), k, phf->seed, phf->r, phf->m);
	case phf::PHF_G_UINT8_BAND_R:
		return phf_hash_<true>(reinterpret_cast<uint8_t *>(phf->g), k, phf->seed, phf->r, phf->m);
	case phf::PHF_G_UINT16_MOD_R:
		return phf_hash_<false>(reinterpret_cast<uint16_t *>(phf->g), k, phf->seed, phf->r, phf->m);
	case phf::PHF_G_UINT16_BAND_R:
		return phf_hash_<true>(reinterpret_cast<uint16_t *>(phf->g), k, phf->seed, phf->r, phf->m);
	case phf::PHF_G_UINT32_MOD_R:
		return phf_hash_<false>(reinterpret_cast<uint32_t *>(phf->g), k, phf->seed, phf->r, phf->m);
	case phf::PHF_G_UINT32_BAND_R:
		return phf_hash_<true>(reinterpret_cast<uint32_t *>(phf->g), k, phf->seed, phf->r, phf->m);
	default:
		abort();
		return 0;
	}
#endif
} /* PHF::hash() */

template phf_hash_t PHF::hash<uint32_t>(struct phf *, uint32_t);
template phf_hash_t PHF::hash<uint64_t>(struct phf *, uint64_t);
template phf_hash_t PHF::hash<phf_string_t>(struct phf *, phf_string_t);
#if !PHF_NO_LIBCXX
template phf_hash_t PHF::hash<std::string>(struct phf *, std::string);
#endif

PHF_PUBLIC void PHF::destroy(struct phf *phf) {
	free(phf->g);
	phf->g = NULL;
} /* PHF::destroy() */

PHF_PUBLIC int phf_init_uint32(struct phf *phf, const uint32_t *k, const size_t n, const size_t lambda, const size_t alpha, const phf_seed_t seed, const bool nodiv) {
	if (nodiv)
		return PHF::init<uint32_t, true>(phf, k, n, lambda, alpha, seed);
	else
		return PHF::init<uint32_t, false>(phf, k, n, lambda, alpha, seed);
} /* phf_init_uint32() */

PHF_PUBLIC int phf_init_uint64(struct phf *phf, const uint64_t *k, const size_t n, const size_t lambda, const size_t alpha, const phf_seed_t seed, const bool nodiv) {
	if (nodiv)
		return PHF::init<uint64_t, true>(phf, k, n, lambda, alpha, seed);
	else
		return PHF::init<uint64_t, false>(phf, k, n, lambda, alpha, seed);
} /* phf_init_uint64() */

PHF_PUBLIC int phf_init_string(struct phf *phf, const phf_string_t *k, const size_t n, const size_t lambda, const size_t alpha, const phf_seed_t seed, const bool nodiv) {
	if (nodiv)
		return PHF::init<phf_string_t, true>(phf, k, n, lambda, alpha, seed);
	else
		return PHF::init<phf_string_t, false>(phf, k, n, lambda, alpha, seed);
} /* phf_init_string() */

PHF_PUBLIC void phf_compact(struct phf *phf) {
	PHF::compact(phf);
} /* phf_compact() */

PHF_PUBLIC phf_hash_t phf_hash_uint32(struct phf *phf, const uint32_t k) {
	return PHF::hash(phf, k);
} /* phf_hash_uint32() */

PHF_PUBLIC phf_hash_t phf_hash_uint64(struct phf *phf, const uint64_t k) {
	return PHF::hash(phf, k);
} /* phf_hash_uint64() */

PHF_PUBLIC phf_hash_t phf_hash_string(struct phf *phf, const phf_string_t k) {
	return PHF::hash(phf, k);
} /* phf_hash_string() */

PHF_PUBLIC void phf_destroy(struct phf *phf) {
	PHF::destroy(phf);
} /* phf_destroy() */


#if PHF_LUALIB
#include <time.h> /* time(2) */

#include <lua.hpp>


#if LUA_VERSION_NUM < 502
static int lua_absindex(lua_State *L, int idx) {
	return (idx > 0 || idx <= LUA_REGISTRYINDEX)? idx : lua_gettop(L) + idx + 1;
} /* lua_absindex() */

#define lua_rawlen(t, index) lua_objlen(t, index)
#endif


struct phfctx {
	int (*hash)(struct phf *, lua_State *, int index);
	struct phf ctx;
}; /* struct phfctx */


static int phf_hash_uint32(struct phf *phf, lua_State *L, int index) {
	uint32_t k = static_cast<uint32_t>(luaL_checkinteger(L, index));

	lua_pushinteger(L, static_cast<lua_Integer>(PHF::hash(phf, k) + 1));

	return 1;
} /* phf_hash_uint32() */

static int phf_hash_uint64(struct phf *phf, lua_State *L, int index) {
	uint64_t k = static_cast<uint64_t>(luaL_checkinteger(L, index));

	lua_pushinteger(L, static_cast<lua_Integer>(PHF::hash(phf, k) + 1));

	return 1;
} /* phf_hash_uint64() */

static int phf_hash_string(struct phf *phf, lua_State *L, int index) {
	phf_string_t k;

	k.p = const_cast<char *>(luaL_checklstring(L, index, &k.n));

	lua_pushinteger(L, static_cast<lua_Integer>(PHF::hash(phf, k) + 1));

	return 1;
} /* phf_hash_string() */

static phf_seed_t phf_seed(lua_State *L) {
	return phf_g(static_cast<uint32_t>(reinterpret_cast<intptr_t>(L)), static_cast<uint32_t>(time(NULL)));
} /* phf_seed() */

static phf_error_t phf_tokey(lua_State *L, int index, uint32_t *k) {
	if (LUA_TNUMBER != lua_type(L, index))
		return EINVAL;

#if LUA_VERSION_NUM > 502
	lua_Integer v;

	v = static_cast<lua_Integer>(lua_tointeger(L, index));

	if (v > UINT32_MAX)
		return ERANGE;
#else
	lua_Number v;

	v = static_cast<lua_Number>(lua_tonumber(L, index));

	if (v > UINT32_MAX)
		return ERANGE;
#endif
	*k = static_cast<uint32_t>(v);

	return 0;
} /* phf_tokey() */

static phf_error_t phf_tokey(lua_State *L, int index, uint64_t *k) {
	if (LUA_TNUMBER != lua_type(L, index))
		return EINVAL;

#if LUA_VERSION_NUM > 502
	lua_Integer v;

	v = static_cast<lua_Integer>(lua_tointeger(L, index));
#else
	lua_Number v;

	v = static_cast<lua_Number>(lua_tonumber(L, index));
#endif
	*k = static_cast<uint64_t>(v);

	return 0;
} /* phf_tokey() */

static phf_error_t phf_tokey(lua_State *L, int index, phf_string_t *k) {
	if (LUA_TSTRING != lua_type(L, index))
		return EINVAL;

	k->p = const_cast<char *>(lua_tolstring(L, index, &k->n));

	return 0;
} /* phf_tokey() */

template<typename T>
static phf_error_t phf_addkeys(lua_State *L, int index, T **_keys, size_t *_count) {
	T *keys = *_keys, *kp;
	size_t count, i;
	int error;

	/*
	 * XXX: because of the way phf_addkeys is used in phf_new we cannot
	 * support non-trivial types
	 */
	static_assert(std::is_standard_layout<T>::value && std::is_trivial<T>::value, "compiled without C++ runtime support");

	count = lua_rawlen(L, index);
	if (SIZE_MAX / sizeof *keys < count)
		return ENOMEM;
	if (!(keys = static_cast<T*>(realloc(keys, count * sizeof *keys))))
		return errno;

	*_keys = kp = keys;
	*_count = count;

	for (i = 1; i <= count; i++) {
		lua_rawgeti(L, index, i);

		error = phf_tokey(L, -1, kp++);

		lua_pop(L, 1);

		if (error)
			return error;
	}

	*_count = PHF::uniq(keys, count);

	return 0;
} /* phf_addkeys() */

static int phf_new(lua_State *L) {
	size_t l = static_cast<size_t>(luaL_optinteger(L, 2, 4));
	size_t a = static_cast<size_t>(luaL_optinteger(L, 3, 80));
	phf_seed_t seed = (lua_isnoneornil(L, 4))? phf_seed(L) : static_cast<phf_seed_t>(luaL_checkinteger(L, 4));
	bool nodiv = static_cast<bool>(lua_toboolean(L, 5));
	void *keys = NULL;
	struct phfctx *phf;
	size_t n = 0;
	int error;

	lua_settop(L, 5);
	luaL_checktype(L, 1, LUA_TTABLE);

	phf = static_cast<struct phfctx *>(lua_newuserdata(L, sizeof *phf));
	memset(phf, 0, sizeof *phf);

	luaL_getmetatable(L, "PHF*");
	lua_setmetatable(L, -2);

	switch ((error = phf_addkeys(L, 1, reinterpret_cast<uint32_t **>(&keys), &n))) {
	case 0:
		break;
	case ERANGE:
		goto uint64;
	case EINVAL:
		goto string;
	default:
		goto error;
	}

	if (n == 0)
		goto empty;

	if ((error = phf_init_uint32(&phf->ctx, reinterpret_cast<uint32_t *>(keys), n, l, a, seed, nodiv)))
		goto error;

	phf->hash = &phf_hash_uint32;

	goto done;
uint64:
	switch ((error = phf_addkeys(L, 1, reinterpret_cast<uint64_t **>(&keys), &n))) {
	case 0:
		break;
	case EINVAL:
		goto string;
	default:
		goto error;
	}

	if (n == 0)
		goto empty;

	if ((error = phf_init_uint64(&phf->ctx, reinterpret_cast<uint64_t *>(keys), n, l, a, seed, nodiv)))
		goto error;

	phf->hash = &phf_hash_uint64;

	goto done;
string:
	if ((error = phf_addkeys(L, 1, reinterpret_cast<phf_string_t **>(&keys), &n)))
		goto error;

	if (n == 0)
		goto empty;

	if ((error = phf_init_string(&phf->ctx, reinterpret_cast<phf_string_t *>(keys), n, l, a, seed, nodiv)))
		goto error;

	phf->hash = &phf_hash_string;

	goto done;
done:
	free(keys);

	PHF::compact(&phf->ctx);

	return 1;
empty:
	free(keys);

	lua_pushstring(L, "empty key set");

	return lua_error(L);
error:
	free(keys);

	lua_pushstring(L, strerror(error));

	return lua_error(L);
} /* phf_new() */

static int phf_r(lua_State *L) {
	struct phfctx *phf = static_cast<struct phfctx *>(luaL_checkudata(L, 1, "PHF*"));

	lua_pushinteger(L, static_cast<lua_Integer>(phf->ctx.r));

	return 1;
} /* phf_r() */

static int phf_m(lua_State *L) {
	struct phfctx *phf = static_cast<struct phfctx *>(luaL_checkudata(L, 1, "PHF*"));

	lua_pushinteger(L, static_cast<lua_Integer>(phf->ctx.m));

	return 1;
} /* phf_m() */

static int (phf_hash)(lua_State *L) {
	struct phfctx *phf = static_cast<struct phfctx *>(luaL_checkudata(L, 1, "PHF*"));

	return phf->hash(&phf->ctx, L, 2);
} /* phf_hash() */

static int phf__gc(lua_State *L) {
	struct phfctx *phf = (struct phfctx *)luaL_checkudata(L, 1, "PHF*");

	phf_destroy(&phf->ctx);

	return 0;
} /* phf__gc() */

static const luaL_Reg phf_methods[] = {
	{ "hash", &(phf_hash) },
	{ "r",    &phf_r },
	{ "m",    &phf_m },
	{ NULL,   NULL },
}; /* phf_methods[] */

static const luaL_Reg phf_metatable[] = {
	{ "__call", &phf_hash },
	{ "__gc",   &phf__gc },
	{ NULL,     NULL },
}; /* phf_metatable[] */

static const luaL_Reg phf_globals[] = {
	{ "new", &phf_new },
	{ NULL,  NULL },
}; /* phf_globals[] */

static void phf_register(lua_State *L, const luaL_Reg *l) {
#if LUA_VERSION_NUM >= 502
	luaL_setfuncs(L, l, 0);
#else
	luaL_register(L, NULL, l);
#endif
} /* phf_register() */

extern "C" int luaopen_phf(lua_State *L) {
	if (luaL_newmetatable(L, "PHF*")) {
		phf_register(L, phf_metatable);
		lua_newtable(L);
		phf_register(L, phf_methods);
		lua_setfield(L, -2, "__index");
	}

	lua_pop(L, 1);

	lua_newtable(L);
	phf_register(L, phf_globals);

	return 1;
} /* luaopen_phf() */

#endif /* PHF_LUALIB */


#if PHF_MAIN

#include <stdlib.h>    /* arc4random(3) free(3) realloc(3) */
#include <stdio.h>     /* fclose(3) fopen(3) fprintf(3) fread(3) freopen(3) printf(3) */
#include <time.h>      /* CLOCKS_PER_SEC clock(3) */
#include <string.h>    /* strcmp(3) */
#include <sys/param.h> /* BSD */
#include <unistd.h>    /* getopt(3) */
#include <strings.h>   /* ffsl(3) */
#include <err.h>       /* err(3) errx(3) warnx(3) */

#ifndef HAVE_VALGRIND_MEMCHECK_H
#define HAVE_VALGRIND_MEMCHECK_H __has_include(<valgrind/memcheck.h>)
#endif

#if HAVE_VALGRIND_MEMCHECK_H
#include <valgrind/memcheck.h>
#endif

static uint32_t randomseed(void) {
#if __APPLE__
	/*
	 * As of macOS 10.13.6 ccaes_vng_ctr_crypt and drbg_update in
	 * libcorecrypto.dylib trigger a "Conditional jump or move on
	 * uninitialized value(s)". As of Valgrind 3.15.0.GIT (20190214)
	 * even when suppressed it still taints code indirectly conditioned
	 * on the seed value.
	 */
	uint32_t seed = arc4random();
	#ifdef VALGRIND_MAKE_MEM_DEFINED
	VALGRIND_MAKE_MEM_DEFINED(&seed, sizeof seed);
	#else
	#warning unable to suppress CoreCrypto CSPRNG uninitialized value tainting
	#endif
	return seed;
#elif defined BSD /* catchall for modern BSDs, which all have arc4random */
	return arc4random();
#else
	FILE *fp;
	uint32_t seed;

	if (!(fp = fopen("/dev/urandom", "r")))
		err(1, "/dev/urandom");

	if (1 != fread(&seed, sizeof seed, 1, fp))
		err(1, "/dev/urandom");

	fclose(fp);

	return seed;
#endif
} /* randomseed() */


template<typename T>
static void pushkey(T **k, size_t *n, size_t *z, T kn) {
	if (!(*n < *z)) {
		size_t z1 = PHF_MAX(*z, 1) * 2;
		T *p;

#if !PHF_NO_LIBCXX
		if (!std::is_trivially_copyable<T>::value) {
			int error;

			if ((error = phf_calloc(&p, z1)))
				errx(1, "calloc: %s", strerror(error));
			for (size_t i = 0; i < *n; i++)
				p[i] = std::move((*k)[i]);
			phf_freearray(*k, *z);

			goto commit;
		}
#else
		static_assert(std::is_standard_layout<T>::value && std::is_trivial<T>::value, "compiled without C++ runtime support");
#endif
		if (z1 < *z || (SIZE_MAX / sizeof **k) < z1)
			errx(1, "addkey: %s", strerror(ERANGE));

		if (!(p = (T *)realloc(*k, z1 * sizeof **k)))
			err(1, "realloc");

commit:
		*k = p;
		*z = z1;
	}

	(*k)[(*n)++] = std::move(kn);
} /* pushkey() */


template<typename T>
static void addkey(T **k, size_t *n, size_t *z, const char *src) {
	pushkey(k, n, z, static_cast<T>(strtoull(src, NULL, 0)));
} /* addkey() */

static void addkey(phf_string_t **k, size_t *n, size_t *z, char *src, size_t len) {
	phf_string_t kn = { (void *)src, len };
	pushkey(k, n, z, kn);
} /* addkey() */

static void addkey(phf_string_t **k, size_t *n, size_t *z, char *src) {
	addkey(k, n, z, src, strlen(src));
} /* addkey() */

#if !PHF_NO_LIBCXX
static void addkey(std::string **k, size_t *n, size_t *z, char *src, size_t len) {
	pushkey(k, n, z, std::string(src, len));
} /* addkey() */

static void addkey(std::string **k, size_t *n, size_t *z, char *src) {
	addkey(k, n, z, src, strlen(src));
} /* addkey() */
#endif

template<typename T>
static void addkeys(T **k, size_t *n, size_t *z, char **src, int count) {
	for (int i = 0; i < count; i++)
		addkey(k, n, z, src[i]);
} /* addkey() */

template<typename T>
static void addkeys(T **k, size_t *n, size_t *z, FILE *fp, char **data) {
	char *ln = NULL;
	size_t lz = 0;
	ssize_t len;

	(void)data;

	while ((len = getline(&ln, &lz, fp)) > 0) {
		if (--len > 0) {
			if (ln[len] == '\n')
				ln[len] = '\0';
			addkey(k, n, z, ln);
		}
	}
	
	free(ln);
} /* addkeys() */

/* slurp file into a single string and take pointers */
static void addkeys(phf_string_t **k, size_t *n, size_t *z, FILE *fp, char **data) {
	size_t p = 0, pe = 0, tp;
	char buf[BUFSIZ], *tmp;
	size_t buflen;

	while ((buflen = fread(buf, 1, sizeof buf, fp))) {
		if (buflen > (pe - p)) {
			if (~buflen < pe || 0 == (pe = phf_powerup(buflen + pe)))
				errx(1, "realloc: %s", strerror(ERANGE));
			if (!(tmp = (char *)realloc(*data, pe)))
				err(1, "realloc");
			*data = tmp;
		}

		memcpy(*data + p, buf, buflen);
		p += buflen;
	}

	for (pe = p, p = 0; p < pe; ) {
		while (p < pe && (*data)[p] == '\n')
			p++;

		tp = p;

		while (p < pe && (*data)[p] != '\n')
			p++;
				
		if (p > tp)
			addkey(k, n, z, &(*data)[tp], (size_t)(p - tp));
	}
} /* addkeys() */


static inline void printkey(phf_string_t &k, phf_hash_t hash) {
	printf("%-32.*s : %" PHF_PRIuHASH "\n", (int)k.n, (char *)k.p, hash);
} /* printkey() */

#if !PHF_NO_LIBCXX
static inline void printkey(std::string &k, phf_hash_t hash) {
	printf("%-32s : %" PHF_PRIuHASH "\n", k.c_str(), hash);
} /* printkey() */
#endif

template<typename T>
static inline void printkey(T k, phf_hash_t hash) {
	printf("%llu : %" PHF_PRIuHASH "\n", (unsigned long long)k, hash);
} /* printkey() */

template<typename T, bool nodiv>
static inline void exec(int argc, char **argv, size_t lambda, size_t alpha, size_t seed, bool verbose, bool noprint) {
	T *k = NULL;
	size_t n = 0, z = 0;
	char *data = NULL;
	struct phf phf;
	clock_t begin, end;

	addkeys(&k, &n, &z, argv, argc);
	addkeys(&k, &n, &z, stdin, &data);

	size_t m = PHF::uniq(k, n);
	if (verbose)
		warnx("loaded %zu keys (%zu duplicates)", m, (n - m));
	n = m;

	begin = clock();
	PHF::init<T, nodiv>(&phf, k, n, lambda, alpha, seed);
	end = clock();


	if (verbose) {
		warnx("found perfect hash for %zu keys in %fs", n, (double)(end - begin) / CLOCKS_PER_SEC);

		begin = clock();
		PHF::compact(&phf);
		end = clock();
		warnx("compacted displacement map in %fs", (double)(end - begin) / CLOCKS_PER_SEC);

		int d_bits = ffsl((long)phf_powerup(phf.d_max));
		double k_bits = ((double)phf.r * d_bits) / n;
		double g_load = (double)n / phf.r;
		warnx("r:%zu m:%zu d_max:%zu d_bits:%d k_bits:%.2f g_load:%.2f", phf.r, phf.m, phf.d_max, d_bits, k_bits, g_load);

		size_t x = 0;
		begin = clock();
		for (size_t i = 0; i < n; i++) {
			x += PHF::hash(&phf, k[i]);
		}
		end = clock();
		warnx("hashed %zu keys in %fs (x:%zu)", n, (double)(end - begin) / CLOCKS_PER_SEC, x);
	}

	if (!noprint) {
		for (size_t i = 0; i < n; i++) {
			printkey(k[i], PHF::hash(&phf, k[i]));
		}
	}

	phf_destroy(&phf);
	free(data);
	phf_freearray(k, n);
} /* exec() */

static void printprimes(int argc, char **argv) {
	intmax_t n = 0, m = UINT32_MAX;
	char *end;

	if (argc > 0) {
		n = strtoimax(argv[0], &end, 0);
		if (end == argv[0] || *end != '\0' || n < 0 || n > UINT32_MAX)
			errx(1, "%s: invalid number", argv[0]);
		n = PHF_MAX(n, 2);
	}

	if (argc > 1) {
		m = strtoimax(argv[1], &end, 0);
		if (end == argv[1] || *end != '\0' || m < n || m > UINT32_MAX)
			errx(1, "%s: invalid number", argv[1]);
	}

	for (; n <= m; n++) {
		if (phf_isprime(n))
			printf("%" PRIdMAX "\n", n);
	}
} /* printprimes() */

int main(int argc, char **argv) {
	const char *path = "/dev/null";
	size_t lambda = 4;
	size_t alpha = 80;
	uint32_t seed = randomseed();
	bool verbose = 0;
	bool noprint = 0;
	bool nodiv = 0;
	enum {
		PHF_UINT32,
		PHF_UINT64,
		PHF_STRING,
#if !PHF_NO_LIBCXX
		PHF_STD_STRING
#endif
	} type = PHF_UINT32;
	bool primes = 0;
	extern char *optarg;
	extern int optind;
	int optc;

	while (-1 != (optc = getopt(argc, argv, "f:l:a:s:2t:nvph"))) {
		switch (optc) {
		case 'f':
			path = optarg;
			break;
		case 'l':
			lambda = strtoul(optarg, NULL, 0);
			break;
		case 'a':
			alpha = strtoul(optarg, NULL, 0);
			break;
		case 's':
			seed = strtoul(optarg, NULL, 0);
			break;
		case '2':
			nodiv = 1;
			break;
		case 't':
			if (!strcmp(optarg, "uint32")) {
				type = PHF_UINT32;
			} else if (!strcmp(optarg, "uint64")) {
				type = PHF_UINT64;
			} else if (!strcmp(optarg, "string")) {
				type = PHF_STRING;
#if !PHF_NO_LIBCXX
			} else if (!strcmp(optarg, "std::string")) {
				type = PHF_STD_STRING;
#endif
			} else {
				errx(1, "%s: invalid key type", optarg);
			}

			break;
		case 'n':
			noprint = 1;
			break;
		case 'v':
			verbose = 1;
			break;
		case 'p':
			primes = 1;
			break;
		case 'h':
			/* FALL THROUGH */
		default:
			fprintf(optc == 'h'? stdout : stderr,
				"%s [-f:l:a:s:t:2nvph] [key [...]]\n"
				"  -f PATH  read keys from PATH (- for stdin)\n"
				"  -l NUM   number of keys per displacement map bucket (reported as g_load)\n"
				"  -a PCT   hash table load factor (1%% - 100%%)\n"
				"  -s SEED  random seed\n"
				"  -t TYPE  parse and hash keys as uint32, uint64, " PHF_IFELSE_LIBCXX("string, or std::string\n", "or string\n")
				"  -2       avoid modular division by rounding r and m to power of 2\n"
				"  -n       do not print key-hash pairs\n"
				"  -v       report hashing status\n"
				"  -p       operate like primes(3) utility\n"
				"  -h       print usage message\n"
				"\n"
				"Report bugs to <william@25thandClement.com>\n",
				argv[0]
			);

			return optc == 'h'? 0 : 1;
		}
	}

	argc -= optind;
	argv += optind;

	if (primes)
		return printprimes(argc, argv), 0;

	if (strcmp(path, "-") && !freopen(path, "r", stdin))
		err(1, "%s", path);

	switch (type) {
	case PHF_UINT32:
		if (nodiv)
			exec<uint32_t, true>(argc, argv, lambda, alpha, seed, verbose, noprint);
		else
			exec<uint32_t, false>(argc, argv, lambda, alpha, seed, verbose, noprint);
		break;
	case PHF_UINT64:
		if (nodiv)
			exec<uint64_t, true>(argc, argv, lambda, alpha, seed, verbose, noprint);
		else
			exec<uint64_t, false>(argc, argv, lambda, alpha, seed, verbose, noprint);
		break;
	case PHF_STRING:
		if (nodiv)
			exec<phf_string_t, true>(argc, argv, lambda, alpha, seed, verbose, noprint);
		else
			exec<phf_string_t, false>(argc, argv, lambda, alpha, seed, verbose, noprint);
		break;
#if !PHF_NO_LIBCXX
	case PHF_STD_STRING:
		if (nodiv)
			exec<std::string, true>(argc, argv, lambda, alpha, seed, verbose, noprint);
		else
			exec<std::string, false>(argc, argv, lambda, alpha, seed, verbose, noprint);
		break;
#endif
	}

	return 0;
} /* main() */

#endif /* PHF_MAIN */