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
|
/*
dev/bit_array_generate.c
project: bit array C library
url: https://github.com/noporpoise/BitArray/
author: Isaac Turner <turner.isaac@gmail.com>
license: Public Domain, no warranty
date: Dec 2013
*/
// 64 bit words
// Array length can be zero
// Unused top bits must be zero
#include <stdlib.h>
#include <stdarg.h>
#include <stdio.h>
#include <errno.h>
#include <string.h> // memset
#include <stdint.h>
uint8_t reverse(uint8_t b)
{
uint8_t r = 0;
int i;
for(i = 0; i < 8; i++)
{
r <<= 1;
r |= b & 0x1;
b >>= 1;
}
return r;
}
// Print table of bytes -> byte reverse
void generate_reverse()
{
int i;
printf("static const word_t reverse_table[256] = \n{\n ");
for(i = 0; i < 256; i++)
{
if(i % 8 == 0 && i > 0)
printf("\n ");
printf(" 0x%02X%c", reverse(i), i == 255 ? '\n' : ',');
}
printf("};\n\n");
}
uint16_t morton(uint8_t b)
{
uint16_t r = 0;
int i;
for(i = 0; i < 8; i++)
{
r |= (b & 0x1) << (2*i);
b >>= 1;
}
return r;
}
// a is either 0 or 1, and is how much to shift by
void generate_morton(char a)
{
int i;
printf("static const word_t morton_table%c[256] = \n{\n ", a ? '1' : '0');
for(i = 0; i < 256; i++)
{
if(i % 8 == 0 && i > 0)
printf("\n ");
uint16_t m = morton(i);
if(a)
m <<= 1;
printf(" 0x%04X%c", m, i == 255 ? '\n' : ',');
}
printf("};\n\n");
}
unsigned int next_permutation(unsigned int v)
{
unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1
// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
//return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
return (t+1) | (((~t & (t+1)) - 1) >> (__builtin_ctz(v) + 1));
}
long factorial(int k)
{
long r = k;
for(k--; k > 1; k--)
{
r *= k;
}
return r;
}
void generate_shuffle()
{
int i;
printf("static const uint8_t shuffle_permutations[9] = {1");
for(i = 1; i < 8; i++)
{
// nCk = n! / ((n-k)!k!)
long combinations = factorial(8) / (factorial(8-i)*factorial(i));
printf(", %li", combinations);
}
printf(", 1};\n");
printf("static const uint8_t shuffle[9][70] = {\n");
for(i = 0; i <= 8; i++)
{
printf(" // %i bits set\n", i);
unsigned char init = i == 0 ? 0 : (0x1 << i) - 1;
printf(" {0x%02X", (int)init);
unsigned int c = next_permutation(init);
int num;
for(num = 1; num < 70; c = next_permutation(c), num++)
{
printf(num % 10 == 0 ? ",\n " : ", ");
printf("0x%02X", c <= 255 ? (int)c : 0);
}
printf(i < 8 ? "},\n" : "}\n};\n\n");
}
}
int main()
{
printf("// byte reverse look up table\n");
generate_reverse();
printf("// Morton table for interleaving bytes\n");
generate_morton(0);
printf("// Morton table for interleaving bytes, shifted left 1 bit\n");
generate_morton(1);
printf("// Tables for shuffling\n");
generate_shuffle();
return 1;
}
|
