summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorjonsykkel <jonrevold@gmail.com>2020-04-08 18:02:57 +0200
committerjonsykkel <jonrevold@gmail.com>2020-04-08 18:02:57 +0200
commite3f5d68ba2f223101a3253be2953376c346e9a88 (patch)
tree41b8c405ff978714e51de173e2745066da7ebdcf
parent13de4d7d44bff1c3db33664a90b201ded7401aec (diff)
downloadct_sequence-e3f5d68ba2f223101a3253be2953376c346e9a88.tar.gz
vork
-rw-r--r--makefile4
-rw-r--r--src/a5.c60
-rw-r--r--src/def.h4
-rw-r--r--src/nt5.c52
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;
+}
+