cangrepp

commit 77374e2c3a0f54bd9ff8f8a45cb791c5a5e666db
parent d48987895a444db5ddc4c1378a103d99afaf5811
Author: olikru <olikru@tkruger.se>
Date:   Mon,  2 Sep 2024 13:16:15 +0200

bitvec for bloom, all still broken

Diffstat:
A
bitvec.c
 | 
62
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
bsgs.c
 | 
135
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
bsgs.h
 | 
10
++++++++++

3 files changed, 207 insertions(+), 0 deletions(-)
diff --git a/bitvec.c b/bitvec.c
@@ -0,0 +1,62 @@
+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/bsgs.c b/bsgs.c
@@ -0,0 +1,135 @@
+#include "bsgs.h"
+
+#define UNDEFINED SIZE_MAX
+
+// For hashing we can use mod because we expect the numbers to behave
+// randomly anyway
+size_t
+hash(const fmpz n)
+{
+  if (COEFF_IS_MPZ(n)) {
+    return (size_t)COEFF_TO_PTR(n)[0]._mp_d[0];
+  } else {
+    return (size_t)n;
+  }
+}
+
+typedef struct _hashmap_integer {
+  size_t n;
+  size_t *table;
+  fmpz_t *keys;
+  size_t ntable;
+} hm_t;
+
+void
+hm_init(hm_t *hm, const size_t s)
+{
+  size_t i;
+  hm->n = 0;
+  hm->ntable = s;
+
+  hm->table = malloc(s * sizeof(*hm->table));
+  hm->keys = malloc(s * sizeof(*hm->keys));
+
+  for (i = 0; i < s; i++) {
+    hm->table[i] = UNDEFINED;
+  }
+}
+
+void
+hm_clear(hm_t *hm)
+{
+  free(hm->table);
+  free(hm->keys);
+}
+
+void
+hm_insert(hm_t *hm, const fmpz_t *key, const size_t val)
+{
+  assert(hm->n < hm->ntable);
+  assert(val != UNDEFINED);
+  size_t kv;
+
+  kv = hash(*key);
+
+  while (hm->table[kv] != UNDEFINED) {
+    if (fmpz_cmp(*(hm->keys[kv]), *key) == 0) {
+      hm->keys[kv] = key;
+      hm->table[kv] = val;
+      return;
+    }
+    kv = (kv + 1) % ht->ntable;
+  }
+
+  hm->keys[kv] = key;
+  hm->table[kv] = val;
+}
+
+size_t
+hm_key_index(const hm_t *hm, const fmpz_t *key)
+{
+  size_t kv;
+
+  kv = hash(*key);
+  while (hm->table[kv] != UNDEFINED) {
+    if (fmpz_cmp(*(hm->keys[kv]), *key) == 0) {
+      return kv;
+    }
+    kv = (kv + 1) % ht->ntable;
+  }
+
+  return UNDEFINED;
+}
+
+size_t
+hm_lookup(size_t *res, const hm_t *hm, const fmpz_t *key)
+{
+  size_t idx = hm_key_index(hm, key);
+  if (idx != UNDEFINED) {
+    *res = hm->table[idx];
+    return 1;
+  } else {
+    return 0;
+  }
+}
+
+// assumptoion:
+//   arguments g and h are already reduced
+uint64_t
+bsgs(ctx_t *ctx, fmpz_mod_ctx_t mod, const fmpz_t g, const fmpz_t h,
+     const uint64_t gorder)
+{
+  assert(ctx->zs_alloc >= 1);
+
+  size_t i;
+  size_t j;
+  uint64_t rr = 0;
+  hm_t hm;
+  const size_t lmt = (size_t)(n_sqrt(gorder) + 1);
+  fmpz *v;
+
+  v = _fmpz_vec_init(nlmt);
+  hm_init(&hm, 2 * lmt);
+
+  // baby step
+  fmpz_set_ui(&v[0], 1);
+  hm_insert(&hm, &v[0], 0);
+  for (i = 1; i < lmt; i++) {
+    fmpz_mod_mul(&v[i], &v[i - 1], g, mod);
+    hm_insert(&hm, &v[i], i);
+  }
+
+  // giantstep
+  fmpz_set(gsc, h);
+  gi = fmpz_mod_inverse(mod, g);
+  for (i = 0; i < lmt; i++) {
+    if(hm_lookup(&j, &hm, gsc) != 0) {
+      rr = (uint64_t) (i*lmt + j);
+    }
+    fmpz_mod_mul(gsc, gsc, gi, mod);
+  }
+
+  hm_clear(&hm);
+
+  return rr;
+}
diff --git a/bsgs.h b/bsgs.h
@@ -0,0 +1,10 @@
+#ifndef BSGS_H
+#define BSGS_H
+
+#include <flint.h>
+#include <fmpz.h>
+#include <ulong_extras.h>
+
+size_t hash(fmpz n);
+
+#endif