chiark - git - mdw - catacomb/blob - base/permute.h

   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