add sok_ctx_hash, cache, solver fixes

4 files changed, 139 insertions, 48 deletions

diff --git a/src/libsok/sok-cache.c b/src/libsok/sok-cache.c
index 748614e..261d6b9 100644
--- a/src/libsok/sok-cache.c
+++ b/src/libsok/sok-cache.c
@@ -1,23 +1,16 @@
 #include <stdbool.h> // bool
 #include <stdint.h> // uint64_t
 #include <stdlib.h> // bsearch(), qsort()
+#include <string.h> // memcpy
+#include <stdio.h> // debug
 #include "sok.h"
 
 #define UNUSED(a) ((void) (a))
 #define GROW_SIZE (4096 / sizeof(uint64_t))
 
-static uint64_t
-hash_ctx(
-  const sok_ctx_t * const ctx
-) {
-  UNUSED(ctx);
-  // TODO
-  return 0;
-}
-
 static int
 u64_cmp(
-  const void * const ap, 
+  const void * const ap,
   const void * const bp
 ) {
   const uint64_t a = *((uint64_t*) ap),
@@ -37,7 +30,7 @@ sok_cache_grow(
   }
 
   // reallocate memory
-  uint64_t * const vals = realloc(cache->vals, new_capacity);
+  uint64_t * const vals = realloc(cache->vals, new_capacity * sizeof(uint64_t));
   if (!vals) {
     return false;
   }
@@ -55,6 +48,16 @@ sok_cache_has_hash(
   const sok_cache_t * const cache,
   const uint64_t hash
 ) {
+#if 0
+  for (size_t i = 0; i < cache->num_vals; i++) {
+    if (cache->vals[i] == hash) {
+      return true;
+    }
+  }
+
+  // return failure
+  return false;
+#else
   return !!bsearch(
     &hash,
     cache->vals,
@@ -62,6 +65,7 @@ sok_cache_has_hash(
     sizeof(uint64_t),
     u64_cmp
   );
+#endif /* 0 */
 }
 
 bool
@@ -69,7 +73,7 @@ sok_cache_has(
   const sok_cache_t * const cache,
   const sok_ctx_t * const ctx
 ) {
-  return sok_cache_has_hash(cache, hash_ctx(ctx));
+  return sok_cache_has_hash(cache, sok_ctx_hash(ctx));
 }
 
 bool
@@ -77,13 +81,15 @@ sok_cache_add(
   sok_cache_t * const cache,
   const sok_ctx_t * const ctx
 ) {
-  // hash context
-  const uint64_t hash = hash_ctx(ctx);
-
-  // check for duplicates
-  if (sok_cache_has_hash(cache, hash)) {
-    return true;
-  }
+/* 
+ *   // hash context
+ *   const uint64_t hash = sok_ctx_hash(ctx);
+ * 
+ *   // check for duplicates
+ *   if (sok_cache_has_hash(cache, hash)) {
+ *     return false;
+ *   }
+ */ 
 
   // check capacity
   if (cache->num_vals >= cache->capacity) {
@@ -94,8 +100,11 @@ sok_cache_add(
     }
   }
 
-  // append hash, sort values
-  cache->vals[cache->num_vals++] = hash_ctx(ctx);
+  // append hash
+  cache->vals[cache->num_vals] = sok_ctx_hash(ctx);
+  cache->num_vals++;
+
+  // sort values
   qsort(cache->vals, cache->num_vals, sizeof(uint64_t), u64_cmp);
 
   // return success
@@ -108,7 +117,7 @@ sok_cache_init(
   const size_t capacity
 ) {
   // alloc memory, check for error
-  uint64_t * const vals = malloc(sizeof(uint64_t) * capacity);
+  uint64_t * const vals = malloc(capacity * sizeof(uint64_t));
   if (!vals) {
     // return failure
     return false;
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);
+}
diff --git a/src/libsok/sok-solve.c b/src/libsok/sok-solve.c
index 6637feb..225ce9b 100644
--- a/src/libsok/sok-solve.c
+++ b/src/libsok/sok-solve.c
@@ -9,36 +9,40 @@ sok_solve_step(
   sok_cache_t * const cache,
   void (*on_error)(const char * const)
 ) {
+  // check for success
+  if (sok_ctx_is_done(ctx)) {
+    // return success
+    return true;
+  }
+
+  if (sok_cache_has(cache, ctx)) {
+    // return failure
+    return false;
+  }
+
+  // add to cache
+  if (!sok_cache_add(cache, ctx)) {
+    if (on_error) {
+      // log error
+      on_error("sok_cache_add() failed");
+    }
+
+    // return failure
+    return false;
+  }
+
   for (size_t dir = 0; dir < SOK_DIR_LAST; dir++) {
     if (!sok_ctx_move(ctx, dir)) {
       continue;
     }
 
-    if (!sok_cache_has(cache, ctx)) {
-      // check for success
-      if (sok_ctx_is_done(ctx)) {
-        // return success
-        return true;
-      }
-
-      // add to cache
-      if (!sok_cache_add(cache, ctx)) {
-        if (on_error) {
-          // log error
-          on_error("sok_cache_add() failed");
-        }
-
-        // return failure
-        return false;
-      }
-
-      // recurse, check for success
-      if (sok_solve_step(ctx, cache, on_error)) {
-        // return success
-        return true;
-      }
+    // recurse, check for success
+    if (sok_solve_step(ctx, cache, on_error)) {
+      // return success
+      return true;
     }
 
+    // undo move
     if (!sok_ctx_undo(ctx)) {
       if (on_error) {
         // log error
diff --git a/src/libsok/sok.h b/src/libsok/sok.h
index 074fbf6..54e6c93 100644
--- a/src/libsok/sok.h
+++ b/src/libsok/sok.h
@@ -36,12 +36,12 @@ typedef struct {
 
 typedef struct sok_level_parser_t_ sok_level_parser_t;
 
-typedef bool (*sok_level_parser_pos_cb_t)(
+typedef _Bool (*sok_level_parser_pos_cb_t)(
   const sok_level_parser_t * const,
   const sok_pos_t
 );
 
-typedef bool (*sok_level_parser_junk_cb_t)(
+typedef _Bool (*sok_level_parser_junk_cb_t)(
   const sok_level_parser_t * const,
   const size_t,
   const char
@@ -67,7 +67,7 @@ void sok_level_parser_init(
   void * const user_data
 );
 
-bool sok_level_parser_parse(
+_Bool sok_level_parser_parse(
   sok_level_parser_t * const parser,
   const char * const buf,
   const size_t buf_len
@@ -175,6 +175,12 @@ _Bool sok_ctx_walk(
   void * const
 );
 
+/****************/
+/* context hash */
+/****************/
+
+uint64_t sok_ctx_hash(const sok_ctx_t * const);
+
 /*********/
 /* cache */
 /*********/