1/*
  2 * PW hash based on https://github.com/Nicoshev/rapidhash
  3 *
  4 * Rapidhash has the following advantages to be adopted:
  5 *   - Clean maintainable code.
  6 *   - Simple algorithm.
  7 *
  8 * Implementation differences:
  9 *   - Tail is padded with zeroes and the code is simplified.
 10 *   - Although data length is known for all PW values, it is excluded
 11 *     from hash calculations to make PW code simpler and less error prone.
 12 *     But it can be uncommented for testing against the original implementation.
 13 */
 14
 15#include "include/pw_hash.h"
 16
 17#include "src/rapidhash.h"
 18
 19//#define TRACE(...)  printf(__VA_ARGS__)
 20#define TRACE(...)
 21
 22struct _PwHashContext {
 23    uint64_t seed;
 24    uint64_t see1;
 25    uint64_t see2;
 26    uint64_t buffer[6];
 27    int buf_size;
 28};
 29
 30void _pw_hash_init(PwHashContext* ctx)
 31{
 32    ctx->seed = RAPID_SEED ^ rapid_mix(RAPID_SEED ^ RAPID_SECRET_0, RAPID_SECRET_1) /* ^ len */;
 33    ctx->see1 = ctx->seed;
 34    ctx->see2 = ctx->seed;
 35    //ctx->len = len;
 36    ctx->buf_size = 0;
 37}
 38
 39void _pw_hash_uint64(PwHashContext* ctx, uint64_t data)
 40{
 41    if (ctx->buf_size == 6) {
 42        ctx->buf_size = 0;
 43
 44        ctx->seed = rapid_mix(ctx->buffer[0] ^ RAPID_SECRET_0, ctx->buffer[1] ^ ctx->seed);
 45        ctx->see1 = rapid_mix(ctx->buffer[2] ^ RAPID_SECRET_1, ctx->buffer[3] ^ ctx->see1);
 46        ctx->see2 = rapid_mix(ctx->buffer[4] ^ RAPID_SECRET_2, ctx->buffer[5] ^ ctx->see2);
 47        TRACE("PW round seed=%llx\n", (unsigned long long) ctx->seed);
 48    }
 49    ctx->buffer[ctx->buf_size++] = data;
 50}
 51
 52void _pw_hash_buffer(PwHashContext* ctx, void* buffer, size_t length)
 53{
 54    if ( ! (((ptrdiff_t) buffer) & 7)) {
 55        // aligned
 56        uint64_t* data_ptr = (uint64_t*) buffer;
 57        while (length >= 8) {
 58            _pw_hash_uint64(ctx, *data_ptr++);
 59            length -= 8;
 60        }
 61        buffer = (void*) data_ptr;
 62    }
 63    // remainder or not aligned buffer
 64    uint8_t* data_ptr = (uint8_t*) buffer;
 65    while (length) {
 66        uint64_t v = 0;
 67        for (size_t i = 0; i < 8; i++) {
 68            v <<= 8;
 69            v += *data_ptr++;
 70            if (0 == --length) {
 71                break;
 72            }
 73        }
 74        _pw_hash_uint64(ctx, v);
 75    }
 76}
 77
 78void _pw_hash_string(PwHashContext* ctx, char* str)
 79{
 80    for (;;) {
 81        uint64_t v = 0;
 82        for (size_t i = 0; i < 8; i++) {
 83            uint8_t c = *str++;
 84            if (c == 0) {
 85                _pw_hash_uint64(ctx, v);
 86                return;
 87            }
 88            v <<= 8;
 89            v += c;
 90        }
 91        _pw_hash_uint64(ctx, v);
 92    }
 93}
 94
 95void _pw_hash_string32(PwHashContext* ctx, char32_t* str)
 96{
 97    for (;;) {
 98        uint64_t v = 0;
 99        for (size_t i = 0; i < 2; i++) {
100            uint32_t c = *str++;
101            if (c == 0) {
102                _pw_hash_uint64(ctx, v);
103                return;
104            }
105            v <<= 32;
106            v += c;
107        }
108        _pw_hash_uint64(ctx, v);
109    }
110}
111
112PwType_Hash _pw_hash_finish(PwHashContext* ctx)
113{
114    ctx->seed ^= ctx->see1 ^ ctx->see2;
115
116    while (ctx->buf_size < 2) {
117        TRACE("PAD %d\n", ctx->buf_size);
118        ctx->buffer[ctx->buf_size++] = 0;
119    }
120
121    if (ctx->buf_size > 2) {
122        ctx->seed = rapid_mix(ctx->buffer[0] ^ RAPID_SECRET_2, ctx->buffer[1] ^ ctx->seed ^ RAPID_SECRET_1);
123        TRACE("PW %d seed=%llx\n", ctx->buf_size, (unsigned long long) ctx->seed);
124        if (ctx->buf_size > 4) {
125            ctx->seed = rapid_mix(ctx->buffer[2] ^ RAPID_SECRET_2, ctx->buffer[3] ^ ctx->seed);
126            TRACE("PW %d seed=%llx\n", ctx->buf_size, (unsigned long long) ctx->seed);
127        }
128    }
129
130    uint64_t a = ctx->buffer[ctx->buf_size - 2] ^ RAPID_SECRET_1;
131    uint64_t b = ctx->buffer[ctx->buf_size - 1] ^ ctx->seed;
132    TRACE("PW a=%llx b=%llx\n", (unsigned long long) a, (unsigned long long) b);
133    rapid_mum(&a, &b);
134
135    return rapid_mix(a ^ RAPID_SECRET_0 /* ^ ctx->len */, b ^ RAPID_SECRET_1);
136}
137
138PwType_Hash pw_hash(PwValuePtr value)
139{
140    PwHashContext ctx;
141    _pw_hash_init(&ctx);
142    _pw_call_hash(value, &ctx, nullptr);
143    return _pw_hash_finish(&ctx);
144}