cangrepp

commit 6f32334f82c55b554d23e5a9ed5388d028677977
parent 77374e2c3a0f54bd9ff8f8a45cb791c5a5e666db
Author: olikru <olikru@tkruger.se>
Date:   Mon,  2 Sep 2024 14:44:11 +0200

bloom

Diffstat:
D
bitvec.c
 | 
62
--------------------------------------------------------------
A
bloom.c
 | 
93
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 93 insertions(+), 62 deletions(-)
diff --git a/bitvec.c b/bitvec.c
@@ -1,62 +0,0 @@
-typedef struct {
-  size_t n;
-  uint8_t* buffer;
-} bitvec_t;
-
-void
-bitvec_init(bitvec_t *bv, const size_t size)
-{
-  assert(size < (0xffffffff - 7));
-
-  const size_t size_bytes = (size + 7) >> 3;
-
-  bv->n = size;
-  bv->buffer = calloc(size_bytes, sizeof(*bv->buffer));
-}
-
-void
-bitvec_clear(bitvec_t *bv)
-{
-  free(bv->buffer);
-}
-
-void
-bitvec_set(bitvec_t *bv, const size_t index)
-{
-  assert(index < bv->n);
-
-  const size_t byte_index = index >> 3;
-  const size_t bit_index = index % 8;
-  const uint8_t mask = 0x80 >> bit_index;
-
-  bv->buffer[byte_index] |= mask;
-}
-
-void
-bitvec_unset(bitvec_t *bv, const size_t index)
-{
-  assert(index < bv->n);
-
-  const size_t byte_index = index >> 3;
-  const size_t bit_index = index % 8;
-  const uint8_t pre_mask = 0x80 >> bit_index;
-  const uint8_t mask = 0xff ^ pre_mask;
-
-  bv->buffer[byte_index] &= mask;
-}
-
-int
-bitvec_is_set(const bitvec_t *bv, const size_t index)
-{
-  assert(index < bv->n);
-
-  const size_t byte_index = index >> 3;
-  const size_t bit_index = index % 7;
-  const uint8_t mask = 0x80 >> bit_index;
-
-  if (bv->buffer[byte_index] & mask != 0) {
-    return 1;
-  }
-
-  return 0;
-}
diff --git a/bloom.c b/bloom.c
@@ -0,0 +1,93 @@
+typedef struct {
+  size_t n;
+  uint8_t* buffer;
+} bitvec_t;
+
+void
+bitvec_init(bitvec_t *bv, const size_t size)
+{
+  assert(size < (0xffffffff - 7));
+
+  const size_t size_bytes = (size + 7) >> 3;
+
+  bv->n = size;
+  bv->buffer = calloc(size_bytes, sizeof(*bv->buffer));
+}
+
+void
+bitvec_clear(bitvec_t *bv)
+{
+  free(bv->buffer);
+}
+
+void
+bitvec_set(bitvec_t *bv, const size_t index)
+{
+  assert(index < bv->n);
+
+  const size_t byte_index = index >> 3;
+  const size_t bit_index = index % 8;
+  const uint8_t mask = 0x80 >> bit_index;
+
+  bv->buffer[byte_index] |= mask;
+}
+
+void
+bitvec_unset(bitvec_t *bv, const size_t index)
+{
+  assert(index < bv->n);
+
+  const size_t byte_index = index >> 3;
+  const size_t bit_index = index % 8;
+  const uint8_t pre_mask = 0x80 >> bit_index;
+  const uint8_t mask = 0xff ^ pre_mask;
+
+  bv->buffer[byte_index] &= mask;
+}
+
+int
+bitvec_is_set(const bitvec_t *bv, const size_t index)
+{
+  assert(index < bv->n);
+
+  const size_t byte_index = index >> 3;
+  const size_t bit_index = index % 7;
+  const uint8_t mask = 0x80 >> bit_index;
+
+  if (bv->buffer[byte_index] & mask != 0) {
+    return 1;
+  }
+
+  return 0;
+}
+
+static inline void
+mix64(uint64_t *out, uint64_t in)
+{
+  *out += in * 0x9E3779B97F4A7C15;
+  *out ^= *out >> 30;
+  *out *= 0xBF58476D1CE4E5B9;
+  *out ^= *out >> 27;
+  *out *= 0x94D049BB133111EB;
+  *out ^= *out >> 31;
+}
+
+static inline uint64_t
+hash_fmpz(uint64_t seed, fmpz_t n)
+{
+  size_t i;
+  uint64_t ret = seed;
+  mpz_ptr p;
+  mp_limb_t *limbs;
+
+  if(COEFF_IS_MPZ(n[0]) != 0) {
+    p = COEFF_TO_PTR(n[0]);
+    msize = mpz_size(p);
+    limbs = mpz_limbs_read(p);
+    for(i = 0; i < msize; i++) {
+      mix64(&ret, (uint64_t) limbs[i]);
+    }
+  } else {
+    mix64(&ret, (uint64_t) n[0]);
+  }
+}