ellipsis-hash.h

Go to the documentation of this file.

 
#ifndef ELLIPSIS_HASH_H
#define ELLIPSIS_HASH_H 1
 
#include <stddef.h>
#include <uchar.h>
#include "utils/ellipsis-fibfac.h"
#include "utils/ellipsis-error.h"
 
inline
size_t ellipsis‿hash(size_t len, char32_t const s[restrict static len]) {
  if (!len) return -1;
  /* Make sure that we only spend char32_t arithmetic on the
     multiplication. */
  constexpr char32_t fib21  = ELLIPSIS_FIBFAC(21);
  /* The value for all-zero bytes. This value is not the result of
     fib21*x for any x < 2²¹, because fib21 is odd and thus not a
     power of 2. When forcing this bit onto the result of the
     multiplication, the new value is still unique for all x < 2^²¹,
     because they already have a bit-difference in the lower bits. */
  constexpr char32_t zer21  = (1ULL<<21);
  constexpr size_t rad  = 31;
  size_t ret  = 0;
  for (size_t i = 0; i < len; i++) {
    ret *= rad;
    ret += (fib21 * s[i])|zer21;
  }
  return ret;
}
 
#endif