src/nt5.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#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);
  temp = malloc(size);
  memset(temp, 0, size);
  index = (unsigned long long *)temp;
  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;
}