vork

4 files changed, 118 insertions, 2 deletions

diff --git a/makefile b/makefile
index 196110b..b541a50 100644
--- a/makefile
+++ b/makefile
@@ -27,7 +27,7 @@ bin        := $(bin_dir)/$(out_file)
 ifneq ($(MSYSTEM),)
   bin      := $(bin).exe
   LDFLAGS  += -static
-  RELFLAGS := -s
+  #RELFLAGS := -s
 else
   RELFLAGS := 
 endif
@@ -55,7 +55,7 @@ ifneq ($(run),)
   run_cmd  := @echo "run     $(bin)"
   run_cmd  += && cd bin
   run_cmd  += && echo "----------------------------------------------------------------" 
-  run_cmd  += && time ./$(out_file) -a4 100000000
+  run_cmd  += && time ./$(out_file) -a5 100000000
   run_cmd  += ; echo "----------------------------------------------------------------"
   run_cmd  += && cd ..
 endif
diff --git a/src/a5.c b/src/a5.c
new file mode 100644
index 0000000..f2743bc
--- /dev/null
+++ b/src/a5.c
@@ -0,0 +1,60 @@
+
+#include "def.h"
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+void                a5_init(uint64_t n);
+void                a5_loop(uint64_t x0,uint64_t x1);
+
+algo_t a5 = {
+  .name = "a5 (bassed on NT5 tek)",
+  .nmax = 1ULL<<32,
+  .init = a5_init,
+  .loop = a5_loop,
+};
+
+static uint32_t    *lastp;
+static uint64_t    *index;
+static uint32_t     filled;
+
+void a5_init(uint64_t n){
+  size_t  lastp_size;
+  size_t  index_size;
+
+  t           = 0;
+  filled      = 0;
+  index_size  = (n-1)/8+1;
+  lastp_size  = n*sizeof(unsigned int);
+  index       = malloc(index_size);
+  lastp       = malloc(lastp_size);
+
+  memset(index,0x00,index_size);
+}
+
+void a5_loop(uint64_t x0,uint64_t x1){
+  uint32_t x1_32 = x1;
+
+  for(uint32_t x = x0;x < x1_32;x++){
+    uint32_t  next;
+    uint64_t *index_ptr;
+    int       index_bit;
+
+    index_ptr = index+(t>>6);
+    index_bit = t & 63;
+
+    if(t < filled || ((*index_ptr>>index_bit) & 1)){
+      next = x-lastp[t];
+    }else{
+      next        = 0;
+      *index_ptr |= 1ULL<<index_bit;
+    }
+
+    lastp[t] = x;
+    if(t == filled){
+      while(lastp[++filled]);
+    }
+    t = next;
+  }
+}
+
diff --git a/src/def.h b/src/def.h
index 49de066..4053dcf 100644
--- a/src/def.h
+++ b/src/def.h
@@ -27,6 +27,9 @@ extern algo_t       a1;
 extern algo_t       a2;
 extern algo_t       a3;
 extern algo_t       a4;
+extern algo_t       a5;
+
+extern algo_t       nt5;
 
 static algo_t *algos[] = {
   [0] = &a0,
@@ -34,6 +37,7 @@ static algo_t *algos[] = {
   [2] = &a2,
   [3] = &a3,
   [4] = &a4,
+  [5] = &a5,
 };
 
 #define ALGO_CUNT   (sizeof(algos)/sizeof(algo_t *))
diff --git a/src/nt5.c b/src/nt5.c
new file mode 100644
index 0000000..8cb558e
--- /dev/null
+++ b/src/nt5.c
@@ -0,0 +1,52 @@
+#include "def.h"
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+void                nt5_init(uint64_t n);
+void                nt5_loop(uint64_t x0,uint64_t x1);
+
+algo_t nt5 = {
+  .name = "nt5",
+  .nmax = 1ULL<<32,
+  .init = nt5_init,
+  .loop = nt5_loop,
+};
+
+static unsigned char *temp;
+static unsigned long long *index;
+static unsigned int *lastpos;
+static unsigned int current;
+static unsigned int cont_filled;
+
+void nt5_init(uint64_t n){
+  size_t size = (n-1)/8+1+n*sizeof(unsigned int);
+  //size_t size = n/8+n*sizeof(unsigned int);
+  temp = malloc(size);
+  memset(temp, 0, size);
+  index = (unsigned long long *)temp;
+  //lastpos = (unsigned int *)(&temp[n / 8]);
+  lastpos = (unsigned int *)(&temp[(n-1)/8+1]);
+  current = 0;
+  cont_filled = 0;
+}
+
+void nt5_loop(uint64_t x0,uint64_t x1){
+  uint32_t x1_32 = x1;
+  for(uint32_t i = x0;i < x1_32;i++){
+    unsigned int next;
+    if (current < cont_filled || (index[current / 64] >> (current % 64)) & 1) {
+      next = i - lastpos[current];
+    } else {
+      next = 0;
+      index[current / 64] |= ((unsigned long long)1) << (current % 64);
+    }
+    lastpos[current] = i;
+    if (current == cont_filled) {
+      while (lastpos[++cont_filled]);
+    }
+    current = next;
+  }
+  t = current;
+}
+