-
-
Notifications
You must be signed in to change notification settings - Fork 185
/
base32.c
250 lines (228 loc) · 49.1 KB
/
base32.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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
#include "base32.h"
#include <smmintrin.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <x86intrin.h> // update if we need to support Windows.
static int8_t zero_masks[32] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
//////////////////////////
/// Source: Faster Base64 Encoding and Decoding Using AVX2 Instructions,
/// https://arxiv.org/abs/1704.00605
//////////////////////////
// credit @aqrit
//////////////////////////
size_t base32hex_simd(uint8_t *dst, const uint8_t *src) {
bool valid = true;
const __m128i delta_check =
_mm_setr_epi8(-16, -32, -48, 70, -65, 41, -97, 9, 0, 0, 0, 0, 0, 0, 0, 0);
const __m128i delta_rebase =
_mm_setr_epi8(0, 0, 0, -48, -55, -55, -87, -87, 0, 0, 0, 0, 0, 0, 0, 0);
const uint8_t *srcinit = src;
do {
__m128i v = _mm_loadu_si128((__m128i *)src);
__m128i hash_key = _mm_and_si128(_mm_srli_epi32(v, 4), _mm_set1_epi8(0x0F));
__m128i check = _mm_add_epi8(_mm_shuffle_epi8(delta_check, hash_key), v);
v = _mm_add_epi8(v, _mm_shuffle_epi8(delta_rebase, hash_key));
unsigned int m = (unsigned)_mm_movemask_epi8(check);
if (m) {
int length = __builtin_ctz(m);
if (length == 0) {
break;
}
src += length;
__m128i zero_mask =
_mm_loadu_si128((__m128i *)(zero_masks + 16 - length));
v = _mm_andnot_si128(zero_mask, v);
valid = false;
} else { // common case
src += 16;
}
v = _mm_maddubs_epi16(v, _mm_set1_epi32(0x01200120));
v = _mm_madd_epi16(
v, _mm_set_epi32(0x00010400, 0x00104000, 0x00010400, 0x00104000));
// ...00000000`0000eeee`efffffgg`ggghhhhh`00000000`aaaaabbb`bbcccccd`dddd0000
v = _mm_or_si128(v, _mm_srli_epi64(v, 48));
v = _mm_shuffle_epi8(
v, _mm_set_epi8(0, 0, 0, 0, 0, 0, 12, 13, 8, 9, 10, 4, 5, 0, 1, 2));
/* decoded 10 bytes... but write 16 cause why not? */
_mm_storeu_si128((__m128i *)dst, v);
dst += 10;
} while (valid);
return (size_t)(src - srcinit);
}
size_t base32hex_avx(uint8_t *dst, const uint8_t *src) {
static int8_t zero_masks256[64] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
bool valid = true;
const __m256i delta_check = _mm256_setr_epi8(
-16, -32, -48, 70, -65, 41, -97, 9, 0, 0, 0, 0, 0, 0, 0, 0, -16, -32, -48,
70, -65, 41, -97, 9, 0, 0, 0, 0, 0, 0, 0, 0);
const __m256i delta_rebase = _mm256_setr_epi8(
0, 0, 0, -48, -55, -55, -87, -87, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -48,
-55, -55, -87, -87, 0, 0, 0, 0, 0, 0, 0, 0);
const uint8_t *srcinit = src;
do {
__m256i v = _mm256_loadu_si256((__m256i *)src);
__m256i hash_key =
_mm256_and_si256(_mm256_srli_epi32(v, 4), _mm256_set1_epi8(0x0F));
__m256i check =
_mm256_add_epi8(_mm256_shuffle_epi8(delta_check, hash_key), v);
v = _mm256_add_epi8(v, _mm256_shuffle_epi8(delta_rebase, hash_key));
unsigned int m = (unsigned)_mm256_movemask_epi8(check);
if (m) {
int length = __builtin_ctz(m);
if (length == 0) {
break;
}
src += length;
__m256i zero_mask =
_mm256_loadu_si256((__m256i *)(zero_masks256 + 32 - length));
v = _mm256_andnot_si256(zero_mask, v);
valid = false;
} else { // common case
src += 32;
}
v = _mm256_maddubs_epi16(v, _mm256_set1_epi32(0x01200120));
v = _mm256_madd_epi16(
v, _mm256_set_epi32(0x00010400, 0x00104000, 0x00010400, 0x00104000,
0x00010400, 0x00104000, 0x00010400, 0x00104000));
// ...00000000`0000eeee`efffffgg`ggghhhhh`00000000`aaaaabbb`bbcccccd`dddd0000
v = _mm256_or_si256(v, _mm256_srli_epi64(v, 48));
v = _mm256_shuffle_epi8(
v, _mm256_set_epi8(0, 0, 0, 0, 0, 0, 12, 13, 8, 9, 10, 4, 5, 0, 1, 2, 0,
0, 0, 0, 0, 0, 12, 13, 8, 9, 10, 4, 5, 0, 1, 2));
// 5. store bytes
_mm_storeu_si128((__m128i *)dst, _mm256_castsi256_si128(v));
dst += 10;
_mm_storeu_si128((__m128i *)dst, _mm256_extractf128_si256(v, 1));
dst += 10;
} while (valid);
return (size_t)(src - srcinit);
}
/* if we didn't have to worry about an unknown number of base32 digits...
then we could just unroll and sign-extend to detect bad chars
*/
size_t base32hex_simple(uint8_t *dst, const uint8_t *src) {
static const uint8_t table[256] = {
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 32, 32, 32, 32, 32, 32,
32, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32,
32, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
};
bool valid = true;
const uint8_t *srcinit = src;
do {
uint64_t r = 0;
for (size_t i = 0; i < 8; i++) {
uint8_t x = table[*src];
src++;
if (x > 31) {
r <<= (5 * (8 - i));
valid = false;
break;
}
r <<= 5;
r |= x;
}
r = (unsigned long int)_bswap64((long long int)r);
uint64_t rs = ((uint64_t)r >> (3 * 8));
memcpy(dst, (const char *)&rs, 8);
dst += 5;
} while (valid);
return (size_t)(src - srcinit);
}
size_t base32hex_fast(uint8_t *dst, const uint8_t *src) {
// clang-format off
static const uint64_t table0[] = {72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,0ULL,8ULL,16ULL,24ULL,32ULL,40ULL,48ULL,56ULL,64ULL,72ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,80ULL,88ULL,96ULL,104ULL,112ULL,120ULL,128ULL,136ULL,144ULL,152ULL,160ULL,168ULL,176ULL,184ULL,192ULL,200ULL,208ULL,216ULL,224ULL,232ULL,240ULL,248ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,80ULL,88ULL,96ULL,104ULL,112ULL,120ULL,128ULL,136ULL,144ULL,152ULL,160ULL,168ULL,176ULL,184ULL,192ULL,200ULL,208ULL,216ULL,224ULL,232ULL,240ULL,248ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL,72057594037927936ULL};
static const uint64_t table1[] = {144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,0ULL,16384ULL,32768ULL,49152ULL,1ULL,16385ULL,32769ULL,49153ULL,2ULL,16386ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,32770ULL,49154ULL,3ULL,16387ULL,32771ULL,49155ULL,4ULL,16388ULL,32772ULL,49156ULL,5ULL,16389ULL,32773ULL,49157ULL,6ULL,16390ULL,32774ULL,49158ULL,7ULL,16391ULL,32775ULL,49159ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,32770ULL,49154ULL,3ULL,16387ULL,32771ULL,49155ULL,4ULL,16388ULL,32772ULL,49156ULL,5ULL,16389ULL,32773ULL,49157ULL,6ULL,16390ULL,32774ULL,49158ULL,7ULL,16391ULL,32775ULL,49159ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL,144115188075855872ULL};
static const uint64_t table2[] = {288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,0ULL,512ULL,1024ULL,1536ULL,2048ULL,2560ULL,3072ULL,3584ULL,4096ULL,4608ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,5120ULL,5632ULL,6144ULL,6656ULL,7168ULL,7680ULL,8192ULL,8704ULL,9216ULL,9728ULL,10240ULL,10752ULL,11264ULL,11776ULL,12288ULL,12800ULL,13312ULL,13824ULL,14336ULL,14848ULL,15360ULL,15872ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,5120ULL,5632ULL,6144ULL,6656ULL,7168ULL,7680ULL,8192ULL,8704ULL,9216ULL,9728ULL,10240ULL,10752ULL,11264ULL,11776ULL,12288ULL,12800ULL,13312ULL,13824ULL,14336ULL,14848ULL,15360ULL,15872ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL,288230376151711744ULL};
static const uint64_t table3[] = {576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,0ULL,1048576ULL,2097152ULL,3145728ULL,4194304ULL,5242880ULL,6291456ULL,7340032ULL,8388608ULL,9437184ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,10485760ULL,11534336ULL,12582912ULL,13631488ULL,14680064ULL,15728640ULL,256ULL,1048832ULL,2097408ULL,3145984ULL,4194560ULL,5243136ULL,6291712ULL,7340288ULL,8388864ULL,9437440ULL,10486016ULL,11534592ULL,12583168ULL,13631744ULL,14680320ULL,15728896ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,10485760ULL,11534336ULL,12582912ULL,13631488ULL,14680064ULL,15728640ULL,256ULL,1048832ULL,2097408ULL,3145984ULL,4194560ULL,5243136ULL,6291712ULL,7340288ULL,8388864ULL,9437440ULL,10486016ULL,11534592ULL,12583168ULL,13631744ULL,14680320ULL,15728896ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL,576460752303423488ULL};
static const uint64_t table4[] = {1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,0ULL,2147483648ULL,65536ULL,2147549184ULL,131072ULL,2147614720ULL,196608ULL,2147680256ULL,262144ULL,2147745792ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,327680ULL,2147811328ULL,393216ULL,2147876864ULL,458752ULL,2147942400ULL,524288ULL,2148007936ULL,589824ULL,2148073472ULL,655360ULL,2148139008ULL,720896ULL,2148204544ULL,786432ULL,2148270080ULL,851968ULL,2148335616ULL,917504ULL,2148401152ULL,983040ULL,2148466688ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,327680ULL,2147811328ULL,393216ULL,2147876864ULL,458752ULL,2147942400ULL,524288ULL,2148007936ULL,589824ULL,2148073472ULL,655360ULL,2148139008ULL,720896ULL,2148204544ULL,786432ULL,2148270080ULL,851968ULL,2148335616ULL,917504ULL,2148401152ULL,983040ULL,2148466688ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL,1152921504606846976ULL};
static const uint64_t table5[] = {2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,0ULL,67108864ULL,134217728ULL,201326592ULL,268435456ULL,335544320ULL,402653184ULL,469762048ULL,536870912ULL,603979776ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,671088640ULL,738197504ULL,805306368ULL,872415232ULL,939524096ULL,1006632960ULL,1073741824ULL,1140850688ULL,1207959552ULL,1275068416ULL,1342177280ULL,1409286144ULL,1476395008ULL,1543503872ULL,1610612736ULL,1677721600ULL,1744830464ULL,1811939328ULL,1879048192ULL,1946157056ULL,2013265920ULL,2080374784ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,671088640ULL,738197504ULL,805306368ULL,872415232ULL,939524096ULL,1006632960ULL,1073741824ULL,1140850688ULL,1207959552ULL,1275068416ULL,1342177280ULL,1409286144ULL,1476395008ULL,1543503872ULL,1610612736ULL,1677721600ULL,1744830464ULL,1811939328ULL,1879048192ULL,1946157056ULL,2013265920ULL,2080374784ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL,2305843009213693952ULL};
static const uint64_t table6[] = {4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,0ULL,137438953472ULL,274877906944ULL,412316860416ULL,549755813888ULL,687194767360ULL,824633720832ULL,962072674304ULL,16777216ULL,137455730688ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,274894684160ULL,412333637632ULL,549772591104ULL,687211544576ULL,824650498048ULL,962089451520ULL,33554432ULL,137472507904ULL,274911461376ULL,412350414848ULL,549789368320ULL,687228321792ULL,824667275264ULL,962106228736ULL,50331648ULL,137489285120ULL,274928238592ULL,412367192064ULL,549806145536ULL,687245099008ULL,824684052480ULL,962123005952ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,274894684160ULL,412333637632ULL,549772591104ULL,687211544576ULL,824650498048ULL,962089451520ULL,33554432ULL,137472507904ULL,274911461376ULL,412350414848ULL,549789368320ULL,687228321792ULL,824667275264ULL,962106228736ULL,50331648ULL,137489285120ULL,274928238592ULL,412367192064ULL,549806145536ULL,687245099008ULL,824684052480ULL,962123005952ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL,4611686018427387904ULL};
static const uint64_t table7[] = {9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,0ULL,4294967296ULL,8589934592ULL,12884901888ULL,17179869184ULL,21474836480ULL,25769803776ULL,30064771072ULL,34359738368ULL,38654705664ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,42949672960ULL,47244640256ULL,51539607552ULL,55834574848ULL,60129542144ULL,64424509440ULL,68719476736ULL,73014444032ULL,77309411328ULL,81604378624ULL,85899345920ULL,90194313216ULL,94489280512ULL,98784247808ULL,103079215104ULL,107374182400ULL,111669149696ULL,115964116992ULL,120259084288ULL,124554051584ULL,128849018880ULL,133143986176ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,42949672960ULL,47244640256ULL,51539607552ULL,55834574848ULL,60129542144ULL,64424509440ULL,68719476736ULL,73014444032ULL,77309411328ULL,81604378624ULL,85899345920ULL,90194313216ULL,94489280512ULL,98784247808ULL,103079215104ULL,107374182400ULL,111669149696ULL,115964116992ULL,120259084288ULL,124554051584ULL,128849018880ULL,133143986176ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL,9223372036854775808ULL};
static const uint64_t masks[] = {248, 49407, 65279, 15794175, 2164260863, 4244635647, 966367641599};
// clang-format on
bool valid = true;
const uint8_t *srcinit = src;
do {
uint64_t r = table0[src[0]];
if(r & 0xff00000000000000) {
break; // we are done
}
r |= table1[src[1]] | table2[src[2]] | table3[src[3]] | table4[src[4]] | table5[src[5]] | table6[src[6]] | table7[src[7]];
uint64_t m = (r & 0xff00000000000000);
if(m) {
int length = __builtin_ctzll(m) - 8*7;
// will be at least 1 and no more than 7
src += length;
r &= masks[length - 1];
valid = false;
} else {
src += 8; // common path
}
memcpy(dst, (const char *)&r, 8);
dst += 5;
} while (valid);
return (size_t)(src - srcinit);
}
size_t base32hex_swar(uint8_t *dst, const uint8_t *src) {
const uint64_t nibble_mask = 0x0F0F0F0F0F0F0F0FULL;
const uint64_t bit6_mask = 0x4040404040404040ULL;
const uint64_t check_min = 0x3636363636363636ULL;
const uint64_t check_max = 0x6060606060606060ULL;
const uint64_t bit7_mask = 0x8080808080808080ULL;
const uint8_t *srcinit = src;
bool valid = true;
do {
uint64_t v;
memcpy(&v, src, 8); // todo: big endian support
uint64_t check = v; // if MSB of lane is set then bad char
check |= ((v ^ nibble_mask) - check_min); // catch bad chars below 0x40
uint64_t is_bit6 =
(v & bit6_mask) >> 6; // split range between letters and digits
v &= (is_bit6 + nibble_mask) | nibble_mask; // v &= (is_bit6) ? 0x1F : 0x0F
check |= v - is_bit6; // catch 0x40 and 0x60
v += is_bit6 * 9; // rebase letters
check |= v + check_max; // catch 0x57..0x5F and 0x77..0x7F
check &= bit7_mask;
if (check != 0) { // has bad char, delimiter, or padding
valid = false;
unsigned trailing = (unsigned)__builtin_ctzll(check) / 8;
if (trailing == 0) {
break;
}
src += trailing;
v &= (check ^ (check - 1)) / 8; // zero from bad char and beyond
} else {
src += 8;
}
const uint64_t m1 = 0x00FF00FF00FF00FFULL;
const uint64_t m2 = 0x0000FFFF0000FFFFULL;
v = ((v & m1) << 5) | ((v & ~m1) >> 8);
v = ((v & m2) << 10) | ((v & ~m2) >> 16);
v = (v << 44) | (v >> 8);
v = __builtin_bswap64(v);
// deliberately overwrites (8 bytes)
memcpy(dst, &v, 8); // todo: big endian support
dst += 5;
} while (valid);
return (size_t)(src - srcinit);
}