summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorjonsykkel <jonrevold@gmail.com>2020-04-09 14:41:28 +0200
committerjonsykkel <jonrevold@gmail.com>2020-04-09 14:41:28 +0200
commitaab7766f0bc045b6859c2d9a96f6b13bcfe75fd6 (patch)
tree24629ed86c982f1d8925f5e17967364a436c33e3
parent27403efb38b1359e1d431ec637e641a137e81ea2 (diff)
downloadct_sequence-aab7766f0bc045b6859c2d9a96f6b13bcfe75fd6.tar.gz
oke
-rw-r--r--makefile2
-rw-r--r--src/a5.c29
-rw-r--r--src/a6.c84
-rw-r--r--src/def.h4
4 files changed, 96 insertions, 23 deletions
diff --git a/makefile b/makefile
index b8fa6a6..fff6a5a 100644
--- a/makefile
+++ b/makefile
@@ -55,7 +55,7 @@ ifneq ($(run),)
run_cmd := @echo "run $(bin)"
run_cmd += && cd bin
run_cmd += && echo "----------------------------------------------------------------"
- run_cmd += && time ./$(out_file) -a5 100000000
+ run_cmd += && time ./$(out_file) -a6 100000000
run_cmd += ; echo "----------------------------------------------------------------"
run_cmd += && cd ..
endif
diff --git a/src/a5.c b/src/a5.c
index f36bfac..46ddcfd 100644
--- a/src/a5.c
+++ b/src/a5.c
@@ -16,7 +16,7 @@ algo_t a5 = {
static uint32_t *lastp;
static uint64_t *index;
-static uint32_t filled;
+static uint64_t filled;
void a5_init(uint64_t n){
size_t lastp_size;
@@ -28,28 +28,17 @@ void a5_init(uint64_t n){
lastp_size = n*sizeof(uint32_t);
index = calloc(index_size,1);
lastp = calloc(lastp_size,1);
+ /*
+ index = AALLOC(64,index_size);
+ lastp = AALLOC(64,lastp_size);
+ memset(index,0x00,index_size);
+ memset(lastp,0x00,lastp_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;
- }
- */
+ for(uint64_t x = x0;x < x1;x++){
+ uint64_t next;
if(t < filled){
next = x-lastp[t];
diff --git a/src/a6.c b/src/a6.c
new file mode 100644
index 0000000..c865d20
--- /dev/null
+++ b/src/a6.c
@@ -0,0 +1,84 @@
+
+#include "def.h"
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+void a6_init(uint64_t n);
+void a6_loop(uint64_t x0,uint64_t x1);
+
+algo_t a6 = {
+ .name = "a6 (NT5 tek)",
+ .nmax = 1ULL<<32,
+ .init = a6_init,
+ .loop = a6_loop,
+};
+
+static uint32_t *lastp;
+static uint64_t *index;
+static uint64_t *index2;
+static uint64_t filled;
+
+void a6_init(uint64_t n){
+ size_t index_n;
+ size_t index2_n;
+ size_t index_size;
+ size_t index2_size;
+ size_t lastp_size;
+
+ t = 0;
+ filled = 0;
+ index_n = (n-1)/64+1;
+ index2_n = (index_n-1)/64+1;
+ index_size = index_n*sizeof(uint64_t);
+ index2_size = index2_n*sizeof(uint64_t);
+ lastp_size = n*sizeof(uint32_t);
+ index = calloc(index_size,1);
+ index2 = calloc(index2_size,1);
+ lastp = calloc(lastp_size,1);
+}
+
+void a6_loop(uint64_t x0,uint64_t x1){
+ for(uint64_t x = x0;x < x1;x++){
+ uint64_t next;
+
+ if(t < filled){
+ next = x-lastp[t];
+ }else{
+ uint64_t *index2_ptr;
+ uint64_t index2_bit;
+ uint64_t *index_ptr;
+ uint64_t index_bit;
+
+ index2_ptr = index2+(t/64/64);
+ index2_bit = 1ULL<<(t/64%64);
+
+ if(*index2_ptr & index2_bit){
+ next = x-lastp[t];
+ }else{
+ index_ptr = index+(t/64);
+ index_bit = 1ULL<<(t%64);
+
+ if(*index_ptr & index_bit){
+ next = x-lastp[t];
+ }else{
+ next = 0;
+ *index_ptr |= index_bit;
+ if(*index_ptr == 0xFFFFFFFFFFFFFFFF){
+ *index2_ptr |= index2_bit;
+ }
+ }
+ }
+ }
+
+ lastp[t] = x;
+
+ if(t == filled){
+ while(lastp[++filled]);
+ }
+
+ t = next;
+ }
+}
+
diff --git a/src/def.h b/src/def.h
index 4053dcf..0a7acab 100644
--- a/src/def.h
+++ b/src/def.h
@@ -3,14 +3,12 @@
#include <stdint.h>
-/*
#ifdef _WIN32
#include <windows.h>
#define AALLOC(_a,_s) _aligned_malloc(_s,_a)
#else
#define AALLOC(_a,_s) aligned_alloc(_a,_s)
#endif
-*/
typedef struct algo_t{
char const *name;
@@ -28,6 +26,7 @@ extern algo_t a2;
extern algo_t a3;
extern algo_t a4;
extern algo_t a5;
+extern algo_t a6;
extern algo_t nt5;
@@ -38,6 +37,7 @@ static algo_t *algos[] = {
[3] = &a3,
[4] = &a4,
[5] = &a5,
+ [6] = &a6,
};
#define ALGO_CUNT (sizeof(algos)/sizeof(algo_t *))