#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <benchmark/benchmark.h>

unsigned int odd_constant = 0xdeadbeef | 1;

static unsigned int hash_crc32_orig(const void *keyptr)
{
    unsigned int hash = odd_constant;
    const char *key = (const char *)keyptr;
    size_t len = strlen(key);

#if __x86_64__
    while (len >= sizeof(uint64_t)) {
        uint64_t data;
        memcpy(&data, key, sizeof(data));
        hash = (unsigned int)__builtin_ia32_crc32di(hash, data);
        key += sizeof(uint64_t);
        len -= sizeof(uint64_t);
    }
#endif /* __x86_64__ */
    while (len >= sizeof(uint32_t)) {
        uint32_t data;
        memcpy(&data, key, sizeof(data));
        hash = __builtin_ia32_crc32si(hash, data);
        key += sizeof(uint32_t);
        len -= sizeof(uint32_t);
    }
    if (*key && *(key + 1)) {
        uint16_t data;
        memcpy(&data, key, sizeof(data));
        hash = __builtin_ia32_crc32hi(hash, data);
        key += sizeof(uint16_t);
    }
    /* Last byte might be the terminating NUL or the last character.
     * For a hash, this doesn't matter, and shaves off a branch.
     */
    hash = __builtin_ia32_crc32qi(hash, (unsigned char)*key);

    return hash;
}

#ifdef __x86_64__
static inline uint64_t has_zero8(const char *ptr)
{
    uint64_t v;

    memcpy(&v, ptr, sizeof(v));

    return ((v - 0x0101010101010101ull) & ~v & 0x8080808080808080ull);
}
#endif

static inline uint32_t has_zero4(const char *ptr)
{
    uint32_t v;

    memcpy(&v, ptr, sizeof(v));

    return ((v - 0x01010101ul) & ~v & 0x80808080ul);
}

static unsigned int hash_crc32_new(const void *keyptr)
{
    unsigned int hash = odd_constant;
    const char *key = (const char *)keyptr;

#if __x86_64__
    while (!has_zero8(key)) {
        uint64_t data;

        memcpy(&data, key, sizeof(data));

        hash = (unsigned int)__builtin_ia32_crc32di(hash, data);
        key += sizeof(uint64_t);
    }
#endif /* __x86_64__ */

    while (!has_zero4(key)) {
        uint32_t data;

        memcpy(&data, key, sizeof(data));

        hash = __builtin_ia32_crc32si(hash, data);
        key += sizeof(uint32_t);
    }

    if (*key && *(key + 1)) {
        uint16_t data;

        memcpy(&data, key, sizeof(data));

        hash = __builtin_ia32_crc32hi(hash, data);
        key += sizeof(uint16_t);
    }
    /* Last byte might be the terminating NUL or the last character.
     * For a hash, this doesn't matter, and shaves off a branch.
     */
    hash = __builtin_ia32_crc32qi(hash, (unsigned char)*key);

    return hash;
}

template <unsigned int (*hash_func)(const void *ptr)>
static void bm_crc(benchmark::State& state)
{
    while (state.KeepRunning()) {
        benchmark::DoNotOptimize(hash_func("a"));
        benchmark::DoNotOptimize(hash_func("ab"));
        benchmark::DoNotOptimize(hash_func("abc"));
        benchmark::DoNotOptimize(hash_func("abcde"));
        benchmark::DoNotOptimize(hash_func("banana"));
        benchmark::DoNotOptimize(hash_func("uma string maior"));
        benchmark::DoNotOptimize(hash_func("uma string bem grande e que vai testar bem os limites"));
        benchmark::DoNotOptimize(hash_func("uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"
            "uma string bem grande e que vai testar bem os limites"));
    }
}

int main(int argc, char *argv[])
{
    benchmark::RegisterBenchmark("orig", bm_crc<hash_crc32_orig>);
    benchmark::RegisterBenchmark("new", bm_crc<hash_crc32_new>);

    benchmark::Initialize(&argc, argv);
    benchmark::RunSpecifiedBenchmarks();

    return 0;
}