view release on metacpan or  search on metacpan

bloom.c  view on Meta::CPAN

  bl = malloc(sizeof(bloom_t));
  if (!bl)
    return NULL;
  bl->hash_function = hash_function;

  bl->k = (unsigned int) S_varint_to_uint64_t((unsigned char **)&blob, (size_t)(end-blob));
  if (blob == NULL) {
    free(bl);
    return NULL;
  }

  bl->significant_bits = (unsigned int) S_varint_to_uint64_t((unsigned char **)&blob, (size_t)(end-blob));
  if (blob == NULL) {
    free(bl);
    return NULL;
  }

  bl->shift = 64 - bl->significant_bits;
  bl->nbytes = end-blob;

  bl->bitmap = malloc(bl->nbytes);
  if (!bl->bitmap) {
    free(bl);
    return NULL;
  }

  memcpy(bl->bitmap, (char *)blob, bl->nbytes);
  blob += bl->nbytes;

  return bl;
}


int
bl_merge(bloom_t *into, const bloom_t * other)
{
  size_t i;
  size_t n;
  char *bf1;
  const char *bf2;

  if (into->k != other->k
      || into->significant_bits != other->significant_bits
      || into->nbytes != other->nbytes /* paranoia */
      || into->hash_function != other->hash_function)
  {
    return 1;
  }

  n = into->nbytes;
  bf1 = into->bitmap;
  bf2 = other->bitmap;
  for (i = 0; i < n; ++i) {
      bf1[i] |= bf2[i];
  }

  return 0;
}


/* Floodyberry's public-domain siphash: https://github.com/floodyberry/siphash */
static inline uint64_t
U8TO64_LE(const unsigned char *p)
{
  return *(const uint64_t *) p;
}

#define ROTL64(a,b) (((a)<<(b))|((a)>>(64-b)))

uint64_t
bl_siphash(uint64_t k0, uint64_t k1, const unsigned char *m, size_t len)
{
  uint64_t v0, v1, v2, v3;
  uint64_t mi;
  uint64_t last7;
  size_t i, blocks;

  v0 = k0 ^ 0x736f6d6570736575ull;
  v1 = k1 ^ 0x646f72616e646f6dull;
  v2 = k0 ^ 0x6c7967656e657261ull;
  v3 = k1 ^ 0x7465646279746573ull;

  last7 = (uint64_t) (len & 0xff) << 56;

#define sipcompress() \
  do { \
    v0 += v1; v2 += v3; \
    v1 = ROTL64(v1,13);  v3 = ROTL64(v3,16); \
    v1 ^= v0; v3 ^= v2; \
    v0 = ROTL64(v0,32); \
    v2 += v1; v0 += v3; \
    v1 = ROTL64(v1,17); v3 = ROTL64(v3,21); \
    v1 ^= v2; v3 ^= v0; \
    v2 = ROTL64(v2,32); \
  } while (0)

  for (i = 0, blocks = (len & ~7); i < blocks; i += 8) {
    mi = U8TO64_LE(m + i);
    v3 ^= mi;
    sipcompress();
    sipcompress();
    v0 ^= mi;
  }

  switch (len - blocks) {
    case 7:
      last7 |= (uint64_t) m[i + 6] << 48;
    case 6:
      last7 |= (uint64_t) m[i + 5] << 40;
    case 5:
      last7 |= (uint64_t) m[i + 4] << 32;
    case 4:
      last7 |= (uint64_t) m[i + 3] << 24;
    case 3:
      last7 |= (uint64_t) m[i + 2] << 16;
    case 2:
      last7 |= (uint64_t) m[i + 1] << 8;
    case 1:
      last7 |= (uint64_t) m[i + 0];
    case 0:
    default:;