add sok_ctx_hash, cache, solver fixes

1 files changed, 72 insertions, 0 deletions

diff --git a/src/libsok/sok-ctx-hash.c b/src/libsok/sok-ctx-hash.c
new file mode 100644
index 0000000..a3a32c7
--- /dev/null
+++ b/src/libsok/sok-ctx-hash.c
@@ -0,0 +1,72 @@
+#include <stdint.h> // uint16_t
+#include <stdio.h> // debug
+#include "sok.h"
+
+// fnv64
+// src: https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
+#define FNV_OFFSET 1099511628211
+#define FNV_PRIME  0xcbf29ce484222325
+
+static uint64_t
+fnv1a(
+  const uint8_t * const buf,
+  const size_t len
+) {
+  uint64_t hash = FNV_OFFSET;
+
+  for (size_t i = 0; i < len; i++) {
+    hash ^= buf[i];
+    hash *= FNV_PRIME;
+  }
+
+  return hash;
+}
+
+#if 0
+uint64_t
+sok_ctx_hash(
+  const sok_ctx_t * const ctx
+) {
+  uint8_t buf[1024] = {
+    (ctx->home.x) & 0xff, 
+    (ctx->home.x >> 16) & 0xff,
+    (ctx->home.y) & 0xff, 
+    (ctx->home.y >> 16) & 0xff,
+    0,
+  };
+
+  for (size_t i = 0; i < ctx->level.num_boxes; i++) {
+    buf[(4 * (i + 1) + 0)] = ctx->boxes[i].x & 0xff;
+    buf[(4 * (i + 1) + 1)] = (ctx->boxes[i].x >> 16) & 0xff;
+    buf[(4 * (i + 1) + 2)] = ctx->boxes[i].y & 0xff;
+    buf[(4 * (i + 1) + 3)] = (ctx->boxes[i].y >> 16) & 0xff;
+  }
+
+  // calculate buffer length
+  const size_t used = 2 * (ctx->level.num_boxes + 1) * sizeof(uint16_t);
+  const size_t len = (used < sizeof(buf)) ? used : sizeof(buf);
+
+  const uint64_t hash = fnv1a((uint8_t*) buf, len);
+  fprintf(stderr, "hash = %lx, used = %zu, len = %zu\n", hash, used, len);
+  return hash;
+}
+#endif /* 0 */
+
+uint64_t
+sok_ctx_hash(
+  const sok_ctx_t * const ctx
+) {
+  uint16_t buf[512] = {ctx->home.x, ctx->home.y, 0};
+  const size_t BUF_MASK = (sizeof(buf) / sizeof(uint16_t) - 1);
+
+  for (size_t i = 0; i < ctx->level.num_boxes; i++) {
+    buf[(2 * (i + 1) + 0) & BUF_MASK] = ctx->boxes[i].x;
+    buf[(2 * (i + 1) + 1) & BUF_MASK] = ctx->boxes[i].y;
+  }
+
+  // calculate buffer length
+  const size_t used = 2 * (ctx->level.num_boxes + 1) * sizeof(uint16_t);
+  const size_t len = (used < sizeof(buf)) ? used : sizeof(buf);
+
+  return fnv1a((uint8_t*) buf, len);
+}