Simplify hashing function to eliminate wraparound carry and use of long long

diff --git a/inode_test_gen.c b/inode_test_gen.c
index cf98d60..7e687a7 100644 (file)
--- a/inode_test_gen.c
+++ b/inode_test_gen.c
@@ -1,3 +1,4 @@
+#include <assert.h>
 #include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -11,7 +12,8 @@
 #define INDIRECT_SHIFT 8
 
 int rand_int(int n) {
-  return (int)((long long)rand() * n / (RAND_MAX + 1LL));
+  assert(sizeof(long) > sizeof(int));
+  return (int)((long)rand() * n / (RAND_MAX + 1L));
 }
 
 int bytes_to_blocks(int size) {

diff --git a/inode_test_run.c b/inode_test_run.c
index ed6a111..c86f8d3 100644 (file)
--- a/inode_test_run.c
+++ b/inode_test_run.c
@@ -15,10 +15,6 @@
 
 #define TRANSFER_SIZE 821 // a prime number somewhat near the block size
 
-int rand_int(int n) {
-  return (int)((long long)rand() * n / (RAND_MAX + 1LL));
-}
-
 bool hash_init(int file, struct cinode *inode, int base, int limit) {
   int count;
   for (int ptr = base; (count = limit - ptr) > 0; ptr += count) {
@@ -26,14 +22,8 @@ bool hash_init(int file, struct cinode *inode, int base, int limit) {
       count = TRANSFER_SIZE;
 
     uint8_t buf[TRANSFER_SIZE];
-    for (int i = 0; i < count; ++i) {
-      long long hash = file * 17 + (i + ptr) * 29;
-      hash = (hash & 0xffffffffLL) + (hash >> 32);
-      hash = (hash & 0xffffLL) + (hash >> 16);
-      hash = (hash & 0xffLL) + (hash >> 8);
-      hash = (hash & 0xffLL) + (hash >> 8);
-      buf[i] = (uint8_t)hash;
-    }
+    for (int i = 0; i < count; ++i)
+      buf[i] = (uint8_t)(file * 17 + (i + ptr) * 29);
 
     udata.u_base = (char *)buf;
     udata.u_count = count;
@@ -59,14 +49,8 @@ void hash_verify(int file, struct cinode *inode, int base, int limit) {
     udata.u_error = 0;
     rassert(readi(inode) == count && udata.u_error == 0);
 
-    for (int i = 0; i < count; ++i) {
-      long long hash = file * 17 + (i + ptr) * 29;
-      hash = (hash & 0xffffffffLL) + (hash >> 32);
-      hash = (hash & 0xffffLL) + (hash >> 16);
-      hash = (hash & 0xffLL) + (hash >> 8);
-      hash = (hash & 0xffLL) + (hash >> 8);
-      rassert(buf[i] == (uint8_t)hash);
-    }
+    for (int i = 0; i < count; ++i)
+      rassert(buf[i] == (uint8_t)(file * 17 + (i + ptr) * 29));
   }
 }
 

diff --git a/p.sh b/p.sh
index ea49b0a..0f30f18 100755 (executable)
--- a/p.sh
+++ b/p.sh
@@ -1,7 +1,7 @@
 #!/bin/sh
 
 echo "generate test script"
-./inode_test_gen 64 16128 16384 4096 >inode_test.txt
+./inode_test_gen 64 16128 1024 4096 >inode_test.txt
 
 echo "run test script"
 rm -f fs.bin

diff --git a/pool_test_gen.c b/pool_test_gen.c
index 1f57e12..c459ced 100644 (file)
--- a/pool_test_gen.c
+++ b/pool_test_gen.c
@@ -1,3 +1,4 @@
+#include <assert.h>
 #include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -5,7 +6,8 @@
 #include "rassert.h"
 
 int rand_int(int n) {
-  return (int)((long long)rand() * n / (RAND_MAX + 1LL));
+  assert(sizeof(long) > sizeof(int));
+  return (int)((long)rand() * n / (RAND_MAX + 1L));
 }
 
 int main(int argc, char **argv) {

diff --git a/pool_test_run.c b/pool_test_run.c
index 2d7a575..1c137f7 100644 (file)
--- a/pool_test_run.c
+++ b/pool_test_run.c
@@ -44,20 +44,14 @@ void move_up(struct pool_item *item, int new_limit) {
 
 void hash_init(int item, int base, int size, int offset) {
   for (int i = 0; i < size; ++i) {
-    long long hash = item * 17 + (i + offset) * 29;
-    hash = (hash & 0xffffffffLL) + (hash >> 32);
-    hash = (hash & 0xffffffffLL) + (hash >> 32);
     rassert(mem[base + i] == 0xaaaaaaaa);
-    mem[base + i] = (int)hash;
+    mem[base + i] = item * 17 + (i + offset) * 29;
   }
 }
 
 void hash_verify(int item, int base, int size, int offset) {
   for (int i = 0; i < size; ++i) {
-    long long hash = item * 17 + (i + offset) * 29;
-    hash = (hash & 0xffffffffLL) + (hash >> 32);
-    hash = (hash & 0xffffffffLL) + (hash >> 32);
-    rassert(mem[base + i] == (int)hash);
+    rassert(mem[base + i] == item * 17 + (i + offset) * 29);
     mem[base + i] = 0xaaaaaaaa;
   }
 }

diff --git a/process_test_gen.c b/process_test_gen.c
index ea3baaa..6f73620 100644 (file)
--- a/process_test_gen.c
+++ b/process_test_gen.c
@@ -1,3 +1,4 @@
+#include <assert.h>
 #include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -17,11 +18,13 @@
 #endif
 
 int rand_int(int n) {
-  return (int)((long long)rand() * n / (RAND_MAX + 1LL));
+  assert(sizeof(long) > sizeof(int));
+  return (int)((long)rand() * n / (RAND_MAX + 1L));
 }
 
 long rand_long(long n) {
-  return (long)((long long)rand() * n / (RAND_MAX + 1LL));
+  assert(sizeof(long) > sizeof(int));
+  return (int)((long)rand() * n / (RAND_MAX + 1L));
 }
 
 int main(int argc, char **argv) {

diff --git a/process_test_run.c b/process_test_run.c
index e688d8f..c271192 100644 (file)
--- a/process_test_run.c
+++ b/process_test_run.c
@@ -20,7 +20,6 @@ uint8_t *swap_block_mem;
 
 void core_hash_init(int process, long base, long size, long offset) {
   long i, addr;
-  long long hash;
 
  //printf("core_hash_init %d %ld(%d) %ld(%d) %ld(%d)\n", process, base, (int)(base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT), offset, (int)(offset >> BLOCK_SHIFT));
   for (i = 0L; i < size; ++i) {
@@ -30,19 +29,13 @@ void core_hash_init(int process, long base, long size, long offset) {
       (core_table_mem[addr >> BLOCK_SHIFT] << BLOCK_SHIFT) |
       (addr & (BLOCK_SIZE - 1));
 #endif /* INDIRECT_CORE */
-    hash = process * 17 + (i + offset) * 29;
-    hash = (hash & 0xffffffffLL) + (hash >> 32);
-    hash = (hash & 0xffffLL) + (hash >> 16);
-    hash = (hash & 0xffLL) + (hash >> 8);
-    hash = (hash & 0xffLL) + (hash >> 8);
     rassert(core_block_mem[addr] == 0xaa);
-    core_block_mem[addr] = (uint8_t)hash;
+    core_block_mem[addr] = (uint8_t)(process * 17 + (i + offset) * 29);
   }
 }
 
 void core_hash_verify(int process, long base, long size, long offset) {
   long i, addr;
-  long long hash;
 
  //printf("core_hash_verify %d %ld(%d) %ld(%d) %ld(%d)\n", process, base, (int)(base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT), offset, (int)(offset >> BLOCK_SHIFT));
   for (i = 0L; i < size; ++i) {
@@ -52,19 +45,15 @@ void core_hash_verify(int process, long base, long size, long offset) {
       (core_table_mem[addr >> BLOCK_SHIFT] << BLOCK_SHIFT) |
       (addr & (BLOCK_SIZE - 1));
 #endif /* INDIRECT_CORE */
-    hash = process * 17 + (i + offset) * 29;
-    hash = (hash & 0xffffffffLL) + (hash >> 32);
-    hash = (hash & 0xffffLL) + (hash >> 16);
-    hash = (hash & 0xffLL) + (hash >> 8);
-    hash = (hash & 0xffLL) + (hash >> 8);
-    rassert(core_block_mem[addr] == (uint8_t)hash);
+    rassert(
+      core_block_mem[addr] == (uint8_t)(process * 17 + (i + offset) * 29)
+    );
     core_block_mem[addr] = 0xaa;
   }
 }
 
 void swap_hash_verify(int process, long base, long size, long offset) {
   long i, addr;
-  long long hash;
 
  //printf("swap_hash_verify %d %ld(%d) %ld(%d) %ld(%d)\n", process, base, (int)(base >> BLOCK_SHIFT), size, (int)((size + (BLOCK_SIZE - 1)) >> BLOCK_SHIFT), offset, (int)(offset >> BLOCK_SHIFT));
   for (i = 0L; i < size; ++i) {
@@ -74,12 +63,9 @@ void swap_hash_verify(int process, long base, long size, long offset) {
       (swap_table_mem[addr >> BLOCK_SHIFT] << BLOCK_SHIFT) |
       (addr & (BLOCK_SIZE - 1));
 #endif /* INDIRECT_SWAP */
-    hash = process * 17 + (i + offset) * 29;
-    hash = (hash & 0xffffffffLL) + (hash >> 32);
-    hash = (hash & 0xffffLL) + (hash >> 16);
-    hash = (hash & 0xffLL) + (hash >> 8);
-    hash = (hash & 0xffLL) + (hash >> 8);
-    rassert(swap_block_mem[addr] == (uint8_t)hash);
+    rassert(
+      swap_block_mem[addr] == (uint8_t)(process * 17 + (i + offset) * 29)
+    );
     swap_block_mem[addr] = 0xaa;
   }
 }