-
Notifications
You must be signed in to change notification settings - Fork 0
/
hail64.c
135 lines (135 loc) · 3.22 KB
/
hail64.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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdio.h>
#include <stdint.h>
#include <x86intrin.h>
#include "hailstone.h"
/*
* 64-bit wide integer search
*/
#if CHECK_MAXVALUE
void hail64m
#elif CHECK_MAXVALUE_PARENTS
void hail64l
#else
void hail64n
#endif
(uint32_t *n, // input: number to search
int32_t *steps, // input/output: # steps
int32_t *maxsteps, // input/output: maximum
uint32_t *maxvalue,int32_t maxvalue_size) // input/output: maximum
{
int32_t lsteps = *steps;
int32_t lmaxsteps = *maxsteps;
uint64_t num = n[0];
uint64_t num2 = n[1];
uint64_t num3;
uint64_t max = maxvalue[0];
uint64_t max2 = (maxvalue_size > 2)?0xfffffffffffffffflu : maxvalue[1];
int nsize;
uint64_t numx;
int count,clz;
#if DEBUG
if (debug){
printf("%s(%lu %lu)\n",__FUNCTION__,num2,num);
printf("\tmaxvalue_size = %d\n",maxvalue_size);
printf("\tmaxvalue = %u %u %u\n",maxvalue[2],maxvalue[1],maxvalue[0]);
}
#endif
while (num2 > 0){
#if DEBUG
if (debug){ printf("\t%d: %lu %lu\n",lsteps,num2,num); }
#endif
if (num & 0x1){
num = num * 3 + 1;
num2 = num2 * 3 + (num >> 32);
num = num & 0xffffffff;
num3 = num2 >> 32;
lsteps++;
if (num3){
num2 = num2 & 0xffffffff;
n[0] = num;
n[1] = num2;
n[2] = num3;
*steps = lsteps;
nsize = 3;
#if CHECK_MAXVALUE
if ((maxvalue_size == 2)||
((maxvalue_size == 3) &&
((num3 > maxvalue[2]) ||
(num3 == maxvalue[2] &&
((num2 > maxvalue[1])||
((num2 == maxvalue[1]) && (num > maxvalue[0]))))))){
#if DEBUG
if (debug){ printf("maxvalue %lu %lu %lu\n",num3,num2,num); }
#endif
global_maxvalue_found = 1;
global_maxvalue[0] = maxvalue[0] = num;
global_maxvalue[1] = maxvalue[1] = num2;
global_maxvalue[2] = maxvalue[2] = num3;
global_maxvalue_size = maxvalue_size = 3;
}
hailxm(n,nsize,steps,maxsteps,maxvalue,maxvalue_size);
maxvalue[0] = global_maxvalue[0];
maxvalue[1] = global_maxvalue[1];
maxvalue[2] = global_maxvalue[2];
maxvalue_size = global_maxvalue_size;
#else
hailxn(n,nsize,steps,maxsteps,maxvalue,maxvalue_size);
#endif
lsteps = *steps;
lmaxsteps = *maxsteps;
num = n[0];
num2 = n[1];
max2 = 0xfffffffffffffffflu;
nsize = 2;
continue;
}
#if CHECK_MAXVALUE
if ((num2 > max2)||
((num2 == max2) && (num > max))){
global_maxvalue_found = 1;
global_maxvalue[0] = max = num;
global_maxvalue[1] = max2 = num2;
global_maxvalue_size = 2;
}
#endif
#if DEBUG
if (debug){ printf("\t%d: %lu %lu\n",lsteps,num2,num); }
#endif
}
#if 0
num = (num >> 1)|((num2 & 0x1)<<31);
num2 = num2 >> 1;
lsteps++;
#endif
//#if 0
numx = (num2 << 32)| num;
count = __builtin_ffsl(numx)-1;
numx = numx >> count;
num2 = numx >> 32;
num = numx & 0xffffffff;
lsteps += count;
//#endif
#if !CHECK_MAXVALUE
//#if 0
// clz check
clz = __lzcnt64(numx);
if (clz64[clz] + lsteps < lmaxsteps){
n[0] = 1;
n[1] = 0;
*steps = lsteps;
return;
}
//#endif
#endif
}
n[0] = num;
n[1] = num2;
*steps = lsteps;
#if CHECK_MAXSTEPS
if (lsteps > *maxsteps){
global_maxsteps_found = 1;
global_maxsteps = *maxsteps = lsteps;
}
#endif
return;
}