Commit | Line | Data |
---|---|---|
d3f33b9a MW |
1 | /* -*-c-*- |
2 | * | |
3 | * Bit permutations | |
4 | * | |
5 | * (c) 2024 Straylight/Edgeware | |
6 | */ | |
7 | ||
8 | /*----- Licensing notice --------------------------------------------------* | |
9 | * | |
10 | * This file is part of Catacomb. | |
11 | * | |
12 | * Catacomb is free software: you can redistribute it and/or modify it | |
13 | * under the terms of the GNU Library General Public License as published | |
14 | * by the Free Software Foundation; either version 2 of the License, or | |
15 | * (at your option) any later version. | |
16 | * | |
17 | * Catacomb is distributed in the hope that it will be useful, but | |
18 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
20 | * Library General Public License for more details. | |
21 | * | |
22 | * You should have received a copy of the GNU Library General Public | |
23 | * License along with Catacomb. If not, write to the Free Software | |
24 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |
25 | * USA. | |
26 | */ | |
27 | ||
28 | #ifndef CATACOMB_PERMUTE_H | |
29 | #define CATACOMB_PERMUTE_H | |
30 | ||
31 | #ifdef __cplusplus | |
32 | extern "C" { | |
33 | #endif | |
34 | ||
35 | /*----- Header files ------------------------------------------------------*/ | |
36 | ||
37 | #include <mLib/macros.h> | |
38 | ||
39 | /*----- Macros provided ---------------------------------------------------*/ | |
40 | ||
41 | /* --- Theory lesson --- * | |
42 | * | |
43 | * It's often useful to rearrange the bits in a word, or a value split across | |
44 | * two (or more) words, so it's worth taking a moment to consider how this | |
45 | * might be done efficiently. Throughout this discussion, we use the | |
46 | * standard bit numbering, where the least significant bit in a word is bit | |
47 | * zero, with numbering increasing with significance. Equivalently, bit | |
48 | * %$k$% has the numerical value %$2^k$%. | |
49 | * | |
50 | * An essential primitive is the `swizzle', which exchanges two similarly | |
51 | * arranged but disjoint groups of bits within a word which are separated by | |
52 | * a constant offset. The groups of bits don't have to be contiguous, but | |
53 | * they must be identified by shifts of the same mask. | |
54 | * | |
55 | * An especially important class of swizzle permutations considers the | |
56 | * individual bits of bit indices. Permutations of the bits in a word can be | |
57 | * interpreted as operations on the bits of the indices. For %$i \ge 0$%, | |
58 | * let %$\mu_i$% be the mask such that bit %$k$% of %$\mu_i$% is set if and | |
59 | * only if bit %$i$% is clear in %$k$%. Hence | |
60 | * | |
61 | * %$\mu_0 = (\ldots 01010101010101010101010101010101)_2 = -1/3$% , | |
62 | * %$\mu_1 = (\ldots 00110011001100110011001100110011)_2 = -1/5$% , | |
63 | * %$\mu_2 = (\ldots 00001111000011110000111100001111)_2 = -1/17$% , | |
64 | * %$\mu_3 = (\ldots 00000000111111110000000011111111)_2 = -1/257$% , | |
65 | * etc. | |
66 | * | |
67 | * In general, the low %$2^i$% bits of %$\mu_i$% are set, the next least | |
68 | * significant %$2^i$% bits are clear, the next %$2^i$% bits are set, and so | |
69 | * on. Hence, %$\mu_i \lsl 2^i = \bar{\mu}_i$%, or, in the %$2$%-adic | |
70 | * numbers %$\Z_2$%, %$2^{2^i} \mu_k = -1 - \mu_i$%, whence, in general, | |
71 | * %$\mu_i = -1/(2^{2^i} + 1)$%. Let %$x$% be some binary value; now we can | |
72 | * describe some important swizzles. | |
73 | * | |
74 | * * Let %$y=(x\bitand\mu_i)\lsl 2^i \bitor (x\bitand\bar{\mu}_i)\lsr 2^i%, | |
75 | * or %$y = (x\bitand\mu_i) \lsl 2^k \bitor (x \lsr 2^k)\bitand\mu_i$%. | |
76 | * This exchanges the two sub-blocks of %$2^i$% bits in each %$2^{i+1}$% | |
77 | * block in %$x$%. In terms of indices, now the bits at indices in which | |
78 | * bit %$i$% is set precede those in which bit %$i$% is clear. | |
79 | * %%\emph{We have inverted index bit %$i$%.}%% | |
80 | * | |
81 | * * Suppose that %$i < j$%, and let %$m = \bar{\mu}_i \bitand \mu_j$% and | |
82 | * %$s = 2^j - 2^i$%; let %$y = (x \bitand m) \lsl s \bitor {}$% | |
83 | * %$(x \lsr s)\bitand m \bitor (x\bitand \overline{m \bitor m \lsl s$%. | |
84 | * Now, %$m$% has its bit %$k$% set if and only if bit %$i$% of %$k$% is | |
85 | * set and bit %$j$% of %$k$% is clear. The related mask %$m \lsl s$% | |
86 | * has bit %$k + s$% set if %$k% has the same property; but, %$k$% | |
87 | * will have bit %$i$% set and bit %$j$% clear if and only if bit %$i$% | |
88 | * is clear and bit %$j$% is set in %$k + s$%. Combined, the mask | |
89 | * %$m \bitor (m \lsl s)$% selects bits at indices in which bits %$i$% | |
90 | * and %$j$% differ, so %$\overline{m \bitor (m \lsl s)}$% selects the | |
91 | * bits at indices where bits %$i$% and %$j$% are equal. | |
92 | * | |
93 | * This swizzle therefore exchanges the bits of %$x$% at indices where | |
94 | * bit %$i$% is set and bit %$j$% is clear with those at indices where | |
95 | * bit %$j$% is set and %$i$% is clear, leaving alone those bits at | |
96 | * indices where bits %$i$% and %$j$% are either both clear or both set. | |
97 | * %%\emph{We have exchanged index bits %$i$% and %$j$%.}%% | |
98 | * | |
99 | * * Rounding off this little collection, suppose again that %$i < j$%, and | |
100 | * let %$m = \mu_i \bitand \mu_j$% and %$s = 2^i + 2^j$%; and again, let | |
101 | * %$y = (x \bitand m) \lsl s \bitor (x \lsr s) \bitand m \bitor {}$% | |
102 | * %$(x \bitand \overline{m \bitor m \lsl s$%. Now, %$m$% has its bit | |
103 | * %$k$% set if and only if bits %$i$% and %$j$% of %$k$% are both clear. | |
104 | * This swizzle therefore exchanges the bits of %$x$% at indices where | |
105 | * bits %$i$% and %$j$% are both clear with those at indices where | |
106 | * bits %$i$% and %$j$% are both set, leaving alone those bits at indices | |
107 | * where bits %$i$% and %$j$% differ. It takes a little work to (left as | |
108 | * an exercise) to see that the effect combines the previous two. | |
109 | * %%\emph{We have exchanged and inverted index bits %$i$% and %$j$%.}%% | |
110 | * | |
111 | * Related is the `twizzle', which exchanges similarly arranged groups of | |
112 | * bits within two different words. This can be seen as a multiprecision | |
113 | * variant of the swizzle. | |
114 | * | |
115 | * The machinery here expects some parameters to have been defined: | |
116 | * | |
117 | * * @regty@ should be an unsigned integer type, and | |
118 | * | |
119 | * * @REGWD@ should be a power of two such that @regty@ can store at least | |
120 | * @REGWD@ bits. | |
121 | */ | |
122 | ||
123 | /* We begin with some internal utilities. @CATACOMB__REPLICATE_n_(x)@ | |
124 | * produces a hexadecimal constant consisting of %$n$% copies of the digits | |
125 | * @x@. | |
126 | */ | |
127 | #define CATACOMB__REPLICATE_16_(x) CATACOMB__REPLICATE_8_(GLUE(x, x)) | |
128 | #define CATACOMB__REPLICATE_8_(x) CATACOMB__REPLICATE_4_(GLUE(x, x)) | |
129 | #define CATACOMB__REPLICATE_4_(x) CATACOMB__REPLICATE_2_(GLUE(x, x)) | |
130 | #define CATACOMB__REPLICATE_2_(x) CATACOMB__REPLICATE_1_(GLUE(x, x)) | |
131 | #define CATACOMB__REPLICATE_1_(x) GLUE(0x, x) | |
132 | ||
133 | /* More internal utilities. @CATACOMB__REPLi_Un(x)@ returns an %$n$%-bit | |
134 | * hexadecimal constant formed by replicating the %$i$%-bit constant (which | |
135 | * must have leading zeros) %$n/i$% times. | |
136 | */ | |
137 | #define CATACOMB__REPL8_U8 CATACOMB__REPLICATE_1_ | |
138 | #define CATACOMB__REPL8_U16 CATACOMB__REPLICATE_2_ | |
139 | #define CATACOMB__REPL8_U32 CATACOMB__REPLICATE_4_ | |
140 | #define CATACOMB__REPL8_U64 CATACOMB__REPLICATE_8_ | |
141 | #define CATACOMB__REPL8_U128 CATACOMB__REPLICATE_16_ | |
142 | ||
143 | #define CATACOMB__REPL16_U16 CATACOMB__REPLICATE_1_ | |
144 | #define CATACOMB__REPL16_U32 CATACOMB__REPLICATE_2_ | |
145 | #define CATACOMB__REPL16_U64 CATACOMB__REPLICATE_4_ | |
146 | #define CATACOMB__REPL16_U128 CATACOMB__REPLICATE_8_ | |
147 | ||
148 | #define CATACOMB__REPL32_U32 CATACOMB__REPLICATE_1_ | |
149 | #define CATACOMB__REPL32_U64 CATACOMB__REPLICATE_2_ | |
150 | #define CATACOMB__REPL32_U128 CATACOMB__REPLICATE_4_ | |
151 | ||
152 | #define CATACOMB__REPL64_U64 CATACOMB__REPLICATE_1_ | |
153 | #define CATACOMB__REPL64_U128 CATACOMB__REPLICATE_2_ | |
154 | ||
155 | #define CATACOMB__REPL128_U128 CATACOMB__REPLICATE_1_ | |
156 | ||
157 | /* Finally, @CATACOMB__REPLi(x)@ returns a hexadecimal constant formed by | |
158 | * replicating the %$i$%-bit constant (including leading zeros) sufficiently | |
159 | * many times as to fill a @REGWD@-bit wide register. | |
160 | */ | |
161 | #define CATACOMB__REPL8(x) GLUE(CATACOMB__REPL8_U, REGWD)(x) | |
162 | #define CATACOMB__REPL16(x) GLUE(CATACOMB__REPL16_U, REGWD)(x) | |
163 | #define CATACOMB__REPL32(x) GLUE(CATACOMB__REPL32_U, REGWD)(x) | |
164 | #define CATACOMB__REPL64(x) GLUE(CATACOMB__REPL64_U, REGWD)(x) | |
165 | #define CATACOMB__REPL128(x) GLUE(CATACOMB__REPL128_U, REGWD)(x) | |
166 | ||
167 | /* The macro @CATACOMB__IXMASK_Bi(_)@ evaluates to the low @REGWD@ bits of | |
168 | * the constant %$\mu_i$% defined above. The argument is ignored; it's | |
169 | * necessary to prevent technical problems with macro expansion | |
170 | * (specifically, to allow the blue paint on @GLUE@ to be washed off before | |
171 | * invoking @CATACOMB__REPLi@). | |
172 | */ | |
173 | #define CATACOMB__IXMASK_B0(_) CATACOMB__REPL8(55) | |
174 | #define CATACOMB__IXMASK_B1(_) CATACOMB__REPL8(33) | |
175 | #define CATACOMB__IXMASK_B2(_) CATACOMB__REPL8(0f) | |
176 | #define CATACOMB__IXMASK_B3(_) CATACOMB__REPL16(00ff) | |
177 | #define CATACOMB__IXMASK_B4(_) CATACOMB__REPL32(0000ffff) | |
178 | #define CATACOMB__IXMASK_B5(_) CATACOMB__REPL64(00000000ffffffff) | |
179 | #define CATACOMB__IXMASK_B6(_) \ | |
180 | CATACOMB__REPL128(0000000000000000ffffffffffffffff) | |
181 | ||
182 | /* @IXMASK(i)@ returns the low @REGWD@ bits of %$\mu_i$%. The argument @i@ | |
183 | * must be a decimal integer constant, without leading zeros. | |
184 | */ | |
185 | #define IXMASK(i) GLUE(CATACOMB__IXMASK_B, i)(hunoz) | |
186 | ||
187 | /* @IXMASK_xy(i, j)@ returns a @REGWD@-bit mask in which bit %$k$% is set if | |
188 | * bit %$i$% of %$k$% is equal to %$x$% and bit %$j$% of %$k$% is equal to | |
189 | * %$y$%. The arguments @i@ and @j@ must be decimal integer constants, | |
190 | * without leading zeros. | |
191 | */ | |
192 | #define IXMASK_00(i, j) (IXMASK(i)&IXMASK(j)) | |
193 | #define IXMASK_01(i, j) (IXMASK(i)&~IXMASK(j)) | |
194 | #define IXMASK_10(i, j) (~IXMASK(i)&IXMASK(j)) | |
195 | #define IXMASK_11(i, j) (~IXMASK(i)&~IXMASK(j)) | |
196 | ||
197 | /* The general swizzle operation. Exchange the bits in @x@ selected by | |
198 | * @mask@ with those selected by @mask << shift@. | |
199 | */ | |
200 | #define SWIZZLE(x, shift, mask) do { \ | |
201 | regty _t = ((x) ^ ((x) >> (shift)))&(mask); \ | |
202 | (x) ^= _t | (_t << (shift)); \ | |
203 | } while (0) | |
204 | ||
205 | /* A swizzle on two words @x@ and @y@, using the same shift, but different | |
206 | * masks @mask0@ and @mask1@. This is just a simple abbreviation. | |
207 | */ | |
208 | #define SWIZZLE_2(x, y, shift, mask0, mask1) do { \ | |
209 | SWIZZLE(x, shift, mask0); SWIZZLE(y, shift, mask1); \ | |
210 | } while (0) | |
211 | ||
212 | /* A `twizzle', or a swizzle across two words. | |
213 | * | |
214 | * The @TWIZZLE_0@ macro exchanges the bits of @x@ and @y selected by | |
215 | * @mask@. The @TWIZZLE_L@ and @TWIZZLE_R@ macros exchange the bits selected | |
216 | * by @mask@ in @y@ with the bits in @x@ selected by @mask << shift@ or | |
217 | * @mask >> shift@ respectively. (The names are from the direction in which | |
218 | * @x@ is shifted, not the direction the mask is shifted.) | |
219 | * | |
220 | * These are used to synthesize swizzles within multiprecision words: if the | |
221 | * intended shift is %$a w + b$%, where %$w$% is the word width, then %$a$% | |
222 | * gives the difference between word indices of the words to be processed, | |
223 | * and %$\abs{b$}% gives the @shift@ argument; use @TWIZZLE_R@ if | |
224 | * %$b \ge 0$%, @TWIZZLE_L@ if %$b \le 0$% is nonpositive, or @TWIZZLE_0@ if | |
225 | * %$b = 0$%. (We can easily distinguish which of %$a w \pm b$% or | |
226 | * %$(a \pm 1) w \mp (w - b)$%, since one kind of shift will keep @mask@ | |
227 | * within the same word, and the other will shift it out completely.) | |
228 | */ | |
229 | #define TWIZZLE_0(x, y, mask) do { \ | |
230 | regty _t = ((y) ^ ((x)))&(mask); \ | |
231 | (x) ^= _t; (y) ^= _t; \ | |
232 | } while (0) | |
233 | #define TWIZZLE_L(x, y, shift, mask) do { \ | |
234 | regty _t = ((y) ^ ((x) << (shift)))&(mask); \ | |
235 | (x) ^= _t >> (shift); (y) ^= _t; \ | |
236 | } while (0) | |
237 | #define TWIZZLE_R(x, y, shift, mask) do { \ | |
238 | regty _t = ((y) ^ ((x) >> (shift)))&(mask); \ | |
239 | (x) ^= _t << (shift); (y) ^= _t; \ | |
240 | } while (0) | |
241 | ||
242 | /* @SWIZZLE_CPL@ applies a swizzle to @x@ which complements index bit @i@; | |
243 | * @SWIZZLE_EXCH@ applies a swizzle to exchange index bits @i@ and @j@; and | |
244 | * @SWIZZLE_XCPL@ applies a swizzle to exchange and invert index bits @i@ and | |
245 | * @j@. The arguments @i@ and @j@ must be decimal integer constants without | |
246 | * leading zeros, with %$i \le j$%. (The macros do nothing if %$i = j$%.) | |
247 | * | |
248 | * The variants with @2@ in their names act identically on @x@ and @y@, and | |
249 | * are intended as a simple convenience. | |
250 | */ | |
251 | #define SWIZZLE_CPL(x, i) SWIZZLE(x, (1 << (i)), IXMASK(i)) | |
252 | #define SWIZZLE_EXCH(x, i, j) \ | |
253 | SWIZZLE(x, (1 << (j)) - (1 << (i)), IXMASK_10(i, j)) | |
254 | #define SWIZZLE_XCPL(x, i, j) \ | |
255 | SWIZZLE(x, (1 << (j)) + (1 << (i)), IXMASK_00(i, j)) | |
256 | ||
257 | #define SWIZZLE_CPL2(x, y, i) \ | |
258 | SWIZZLE_2(x, y, (1 << (i)), IXMASK(i), IXMASK(i)) | |
259 | #define SWIZZLE_EXCH2(x, y, i, j) \ | |
260 | SWIZZLE_2(x, y, (1 << (j)) - (1 << (i)), \ | |
261 | IXMASK_10(i, j), IXMASK_10(i, j)) | |
262 | #define SWIZZLE_XCPL2(x, y, i, j) \ | |
263 | SWIZZLE_2(x, y, (1 << (j)) + (1 << (i)), \ | |
264 | IXMASK_00(i, j), IXMASK_00(i, j)) | |
265 | ||
266 | /* The @TWIZZLE_EXCH@ and @TWIZZLE_XCPL@ macros act like the similarly named | |
267 | * @SWIZZLE_...@ macros above, except that (a) they act on two words from a | |
268 | * multiprecision value, and the @j@ index is implicit in the selection of | |
269 | * the operands @x@ and @y@. If the word width is %$w$%, and %$2^j = n w$%, | |
270 | * then %$x$% should be chosen to be %$n$% slots more significant than | |
271 | * %$y$%. | |
272 | * | |
273 | * Note that there is no @TWIZZLE_CPL@, since this would simply involve | |
274 | * exchanging two entries in an array. | |
275 | */ | |
276 | #define TWIZZLE_EXCH(x, y, i) TWIZZLE_L(x, y, (1 << (i)), ~IXMASK(i)) | |
277 | #define TWIZZLE_XCPL(x, y, i) TWIZZLE_R(x, y, (1 << (i)), IXMASK(i)) | |
278 | ||
279 | /*----- That's all, folks -------------------------------------------------*/ | |
280 | ||
281 | #ifdef __cplusplus | |
282 | } | |
283 | #endif | |
284 | ||
285 | #endif |