[catacomb] / base / permute.h

/* -*-c-*-
 *
 * Bit permutations
 *
 * (c) 2024 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software: you can redistribute it and/or modify it
 * under the terms of the GNU Library General Public License as published
 * by the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Catacomb is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb.  If not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
 * USA.
 */

#ifndef CATACOMB_PERMUTE_H
#define CATACOMB_PERMUTE_H

#ifdef __cplusplus
  extern "C" {
#endif

/*----- Header files ------------------------------------------------------*/

#include <mLib/macros.h>

/*----- Macros provided ---------------------------------------------------*/

/* --- Theory lesson --- *
 *
 * It's often useful to rearrange the bits in a word, or a value split across
 * two (or more) words, so it's worth taking a moment to consider how this
 * might be done efficiently.  Throughout this discussion, we use the
 * standard bit numbering, where the least significant bit in a word is bit
 * zero, with numbering increasing with significance.  Equivalently, bit
 * %$k$% has the numerical value %$2^k$%.
 *
 * An essential primitive is the `swizzle', which exchanges two similarly
 * arranged but disjoint groups of bits within a word which are separated by
 * a constant offset.  The groups of bits don't have to be contiguous, but
 * they must be identified by shifts of the same mask.
 *
 * An especially important class of swizzle permutations considers the
 * individual bits of bit indices.  Permutations of the bits in a word can be
 * interpreted as operations on the bits of the indices.  For %$i \ge 0$%,
 * let %$\mu_i$% be the mask such that bit %$k$% of %$\mu_i$% is set if and
 * only if bit %$i$% is clear in %$k$%.  Hence
 *
 *      %$\mu_0 = (\ldots 01010101010101010101010101010101)_2 = -1/3$% ,
 *      %$\mu_1 = (\ldots 00110011001100110011001100110011)_2 = -1/5$% ,
 *      %$\mu_2 = (\ldots 00001111000011110000111100001111)_2 = -1/17$% ,
 *      %$\mu_3 = (\ldots 00000000111111110000000011111111)_2 = -1/257$% ,
 *      etc.
 *
 * In general, the low %$2^i$% bits of %$\mu_i$% are set, the next least
 * significant %$2^i$% bits are clear, the next %$2^i$% bits are set, and so
 * on.  Hence, %$\mu_i \lsl 2^i = \bar{\mu}_i$%, or, in the %$2$%-adic
 * numbers %$\Z_2$%, %$2^{2^i} \mu_k = -1 - \mu_i$%, whence, in general,
 * %$\mu_i = -1/(2^{2^i} + 1)$%.  Let %$x$% be some binary value; now we can
 * describe some important swizzles.
 *
 *   * Let %$y=(x\bitand\mu_i)\lsl 2^i \bitor (x\bitand\bar{\mu}_i)\lsr 2^i%,
 *     or %$y = (x\bitand\mu_i) \lsl 2^k \bitor (x \lsr 2^k)\bitand\mu_i$%.
 *     This exchanges the two sub-blocks of %$2^i$% bits in each %$2^{i+1}$%
 *     block in %$x$%.  In terms of indices, now the bits at indices in which
 *     bit %$i$% is set precede those in which bit %$i$% is clear.
 *     %%\emph{We have inverted index bit %$i$%.}%%
 *
 *   * Suppose that %$i < j$%, and let %$m = \bar{\mu}_i \bitand \mu_j$% and
 *     %$s = 2^j - 2^i$%; let %$y = (x \bitand m) \lsl s \bitor {}$%
 *     %$(x \lsr s)\bitand m \bitor (x\bitand \overline{m \bitor m \lsl s$%.
 *     Now, %$m$% has its bit %$k$% set if and only if bit %$i$% of %$k$% is
 *     set and bit %$j$% of %$k$% is clear.  The related mask %$m \lsl s$%
 *     has bit %$k + s$% set if %$k% has the same property; but, %$k$%
 *     will have bit %$i$% set and bit %$j$% clear if and only if bit %$i$%
 *     is clear and bit %$j$% is set in %$k + s$%.  Combined, the mask
 *     %$m \bitor (m \lsl s)$% selects bits at indices in which bits %$i$%
 *     and %$j$% differ, so %$\overline{m \bitor (m \lsl s)}$% selects the
 *     bits at indices where bits %$i$% and %$j$% are equal.
 *
 *     This swizzle therefore exchanges the bits of %$x$% at indices where
 *     bit %$i$% is set and bit %$j$% is clear with those at indices where
 *     bit %$j$% is set and %$i$% is clear, leaving alone those bits at
 *     indices where bits %$i$% and %$j$% are either both clear or both set.
 *     %%\emph{We have exchanged index bits %$i$% and %$j$%.}%%
 *
 *   * Rounding off this little collection, suppose again that %$i < j$%, and
 *     let %$m = \mu_i \bitand \mu_j$% and %$s = 2^i + 2^j$%; and again, let
 *     %$y = (x \bitand m) \lsl s \bitor (x \lsr s) \bitand m \bitor {}$%
 *     %$(x \bitand \overline{m \bitor m \lsl s$%.  Now, %$m$% has its bit
 *     %$k$% set if and only if bits %$i$% and %$j$% of %$k$% are both clear.
 *     This swizzle therefore exchanges the bits of %$x$% at indices where
 *     bits %$i$% and %$j$% are both clear with those at indices where
 *     bits %$i$% and %$j$% are both set, leaving alone those bits at indices
 *     where bits %$i$% and %$j$% differ.  It takes a little work to (left as
 *     an exercise) to see that the effect combines the previous two.
 *     %%\emph{We have exchanged and inverted index bits %$i$% and %$j$%.}%%
 *
 * Related is the `twizzle', which exchanges similarly arranged groups of
 * bits within two different words.  This can be seen as a multiprecision
 * variant of the swizzle.
 *
 * The machinery here expects some parameters to have been defined:
 *
 *   * @regty@ should be an unsigned integer type, and
 *
 *   * @REGWD@ should be a power of two such that @regty@ can store at least
 *     @REGWD@ bits.
 */

/* We begin with some internal utilities.  @CATACOMB__REPLICATE_n_(x)@
 * produces a hexadecimal constant consisting of %$n$% copies of the digits
 * @x@.
 */
#define CATACOMB__REPLICATE_16_(x) CATACOMB__REPLICATE_8_(GLUE(x, x))
#define CATACOMB__REPLICATE_8_(x) CATACOMB__REPLICATE_4_(GLUE(x, x))
#define CATACOMB__REPLICATE_4_(x) CATACOMB__REPLICATE_2_(GLUE(x, x))
#define CATACOMB__REPLICATE_2_(x) CATACOMB__REPLICATE_1_(GLUE(x, x))
#define CATACOMB__REPLICATE_1_(x) GLUE(0x, x)

/* More internal utilities.  @CATACOMB__REPLi_Un(x)@ returns an %$n$%-bit
 * hexadecimal constant formed by replicating the %$i$%-bit constant (which
 * must have leading zeros) %$n/i$% times.
 */
#define CATACOMB__REPL8_U8 CATACOMB__REPLICATE_1_
#define CATACOMB__REPL8_U16 CATACOMB__REPLICATE_2_
#define CATACOMB__REPL8_U32 CATACOMB__REPLICATE_4_
#define CATACOMB__REPL8_U64 CATACOMB__REPLICATE_8_
#define CATACOMB__REPL8_U128 CATACOMB__REPLICATE_16_

#define CATACOMB__REPL16_U16 CATACOMB__REPLICATE_1_
#define CATACOMB__REPL16_U32 CATACOMB__REPLICATE_2_
#define CATACOMB__REPL16_U64 CATACOMB__REPLICATE_4_
#define CATACOMB__REPL16_U128 CATACOMB__REPLICATE_8_

#define CATACOMB__REPL32_U32 CATACOMB__REPLICATE_1_
#define CATACOMB__REPL32_U64 CATACOMB__REPLICATE_2_
#define CATACOMB__REPL32_U128 CATACOMB__REPLICATE_4_

#define CATACOMB__REPL64_U64 CATACOMB__REPLICATE_1_
#define CATACOMB__REPL64_U128 CATACOMB__REPLICATE_2_

#define CATACOMB__REPL128_U128 CATACOMB__REPLICATE_1_

/* Finally, @CATACOMB__REPLi(x)@ returns a hexadecimal constant formed by
 * replicating the %$i$%-bit constant (including leading zeros) sufficiently
 * many times as to fill a @REGWD@-bit wide register.
 */
#define CATACOMB__REPL8(x) GLUE(CATACOMB__REPL8_U, REGWD)(x)
#define CATACOMB__REPL16(x) GLUE(CATACOMB__REPL16_U, REGWD)(x)
#define CATACOMB__REPL32(x) GLUE(CATACOMB__REPL32_U, REGWD)(x)
#define CATACOMB__REPL64(x) GLUE(CATACOMB__REPL64_U, REGWD)(x)
#define CATACOMB__REPL128(x) GLUE(CATACOMB__REPL128_U, REGWD)(x)

/* The macro @CATACOMB__IXMASK_Bi(_)@ evaluates to the low @REGWD@ bits of
 * the constant %$\mu_i$% defined above.  The argument is ignored; it's
 * necessary to prevent technical problems with macro expansion
 * (specifically, to allow the blue paint on @GLUE@ to be washed off before
 * invoking @CATACOMB__REPLi@).
 */
#define CATACOMB__IXMASK_B0(_) CATACOMB__REPL8(55)
#define CATACOMB__IXMASK_B1(_) CATACOMB__REPL8(33)
#define CATACOMB__IXMASK_B2(_) CATACOMB__REPL8(0f)
#define CATACOMB__IXMASK_B3(_) CATACOMB__REPL16(00ff)
#define CATACOMB__IXMASK_B4(_) CATACOMB__REPL32(0000ffff)
#define CATACOMB__IXMASK_B5(_) CATACOMB__REPL64(00000000ffffffff)
#define CATACOMB__IXMASK_B6(_)                                          \
        CATACOMB__REPL128(0000000000000000ffffffffffffffff)

/* @IXMASK(i)@ returns the low @REGWD@ bits of %$\mu_i$%.  The argument @i@
 * must be a decimal integer constant, without leading zeros.
 */
#define IXMASK(i) GLUE(CATACOMB__IXMASK_B, i)(hunoz)

/* @IXMASK_xy(i, j)@ returns a @REGWD@-bit mask in which bit %$k$% is set if
 * bit %$i$% of %$k$% is equal to %$x$% and bit %$j$% of %$k$% is equal to
 * %$y$%.  The arguments @i@ and @j@ must be decimal integer constants,
 * without leading zeros.
 */
#define IXMASK_00(i, j) (IXMASK(i)&IXMASK(j))
#define IXMASK_01(i, j) (IXMASK(i)&~IXMASK(j))
#define IXMASK_10(i, j) (~IXMASK(i)&IXMASK(j))
#define IXMASK_11(i, j) (~IXMASK(i)&~IXMASK(j))

/* The general swizzle operation.  Exchange the bits in @x@ selected by
 * @mask@ with those selected by @mask << shift@.
 */
#define SWIZZLE(x, shift, mask) do {                                    \
  regty _t = ((x) ^ ((x) >> (shift)))&(mask);                           \
  (x) ^= _t | (_t << (shift));                                          \
} while (0)

/* A swizzle on two words @x@ and @y@, using the same shift, but different
 * masks @mask0@ and @mask1@.  This is just a simple abbreviation.
 */
#define SWIZZLE_2(x, y, shift, mask0, mask1) do {                       \
  SWIZZLE(x, shift, mask0); SWIZZLE(y, shift, mask1);                   \
} while (0)

/* A `twizzle', or a swizzle across two words.
 *
 * The @TWIZZLE_0@ macro exchanges the bits of @x@ and @y selected by
 * @mask@.  The @TWIZZLE_L@ and @TWIZZLE_R@ macros exchange the bits selected
 * by @mask@ in @y@ with the bits in @x@ selected by @mask << shift@ or
 * @mask >> shift@ respectively.  (The names are from the direction in which
 * @x@ is shifted, not the direction the mask is shifted.)
 *
 * These are used to synthesize swizzles within multiprecision words: if the
 * intended shift is %$a w + b$%, where %$w$% is the word width, then %$a$%
 * gives the difference between word indices of the words to be processed,
 * and %$\abs{b$}% gives the @shift@ argument; use @TWIZZLE_R@ if
 * %$b \ge 0$%, @TWIZZLE_L@ if %$b \le 0$% is nonpositive, or @TWIZZLE_0@ if
 * %$b = 0$%.  (We can easily distinguish which of %$a w \pm b$% or
 * %$(a \pm 1) w \mp (w - b)$%, since one kind of shift will keep @mask@
 * within the same word, and the other will shift it out completely.)
 */
#define TWIZZLE_0(x, y, mask) do {                                      \
  regty _t = ((y) ^ ((x)))&(mask);                                      \
  (x) ^= _t; (y) ^= _t;                                                 \
} while (0)
#define TWIZZLE_L(x, y, shift, mask) do {                               \
  regty _t = ((y) ^ ((x) << (shift)))&(mask);                           \
  (x) ^= _t >> (shift); (y) ^= _t;                                      \
} while (0)
#define TWIZZLE_R(x, y, shift, mask) do {                               \
  regty _t = ((y) ^ ((x) >> (shift)))&(mask);                           \
  (x) ^= _t << (shift); (y) ^= _t;                                      \
} while (0)

/* @SWIZZLE_CPL@ applies a swizzle to @x@ which complements index bit @i@;
 * @SWIZZLE_EXCH@ applies a swizzle to exchange index bits @i@ and @j@; and
 * @SWIZZLE_XCPL@ applies a swizzle to exchange and invert index bits @i@ and
 * @j@.  The arguments @i@ and @j@ must be decimal integer constants without
 * leading zeros, with %$i \le j$%.  (The macros do nothing if %$i = j$%.)
 *
 * The variants with @2@ in their names act identically on @x@ and @y@, and
 * are intended as a simple convenience.
 */
#define SWIZZLE_CPL(x, i) SWIZZLE(x, (1 << (i)), IXMASK(i))
#define SWIZZLE_EXCH(x, i, j)                                           \
        SWIZZLE(x, (1 << (j)) - (1 << (i)), IXMASK_10(i, j))
#define SWIZZLE_XCPL(x, i, j)                                           \
        SWIZZLE(x, (1 << (j)) + (1 << (i)), IXMASK_00(i, j))

#define SWIZZLE_CPL2(x, y, i)                                           \
        SWIZZLE_2(x, y, (1 << (i)), IXMASK(i), IXMASK(i))
#define SWIZZLE_EXCH2(x, y, i, j)                                       \
        SWIZZLE_2(x, y, (1 << (j)) - (1 << (i)),                        \
                  IXMASK_10(i, j), IXMASK_10(i, j))
#define SWIZZLE_XCPL2(x, y, i, j)                                       \
        SWIZZLE_2(x, y, (1 << (j)) + (1 << (i)),                        \
                  IXMASK_00(i, j), IXMASK_00(i, j))

/* The @TWIZZLE_EXCH@ and @TWIZZLE_XCPL@ macros act like the similarly named
 * @SWIZZLE_...@ macros above, except that (a) they act on two words from a
 * multiprecision value, and the @j@ index is implicit in the selection of
 * the operands @x@ and @y@.  If the word width is %$w$%, and %$2^j = n w$%,
 * then %$x$% should be chosen to be %$n$% slots more significant than
 * %$y$%.
 *
 * Note that there is no @TWIZZLE_CPL@, since this would simply involve
 * exchanging two entries in an array.
 */
#define TWIZZLE_EXCH(x, y, i) TWIZZLE_L(x, y, (1 << (i)), ~IXMASK(i))
#define TWIZZLE_XCPL(x, y, i) TWIZZLE_R(x, y, (1 << (i)), IXMASK(i))

/*----- That's all, folks -------------------------------------------------*/

#ifdef __cplusplus
  }
#endif

#endif