Given some black-box permutation that operates on an array of integers, it's easy to find out what the permutation does: feed it an array containing the number 0 .. n-1, apply the permutation to it, then the result tells you exactly what the permutation does. And now that you have that resulting array that describes the permutation, you no long need the black-box permutation - you can apply the permutation by using that array. But what about bit-permutations? You can't exactly feed them an array containing 0 .. n-1 .. or can you?
What you can do is feed in an integer constructed out of all the least significant bits of that array, permute it, and deconstruct it into an array. Repeat for every relevant bit, performing log2(n) applications of the black-box bit-permutation. Both taking bit-slices of an array like that and deconstructing the results back into a "normal" array correspond to some form of bit-matrix transpose, so we won't be messing around with individual bits one at a time. For example, for a 64-bit bit-permutation, for which I derived the relevant transposes in Permuting bits with GF2P8AFFINEQB (or you could have them automatically generated using this little tool):
__m512i Transpose8x64(__m512i x) {
__m512i s1 = _mm512_set_epi8(
7, 15, 23, 31, 39, 47, 55, 63,
6, 14, 22, 30, 38, 46, 54, 62,
5, 13, 21, 29, 37, 45, 53, 61,
4, 12, 20, 28, 36, 44, 52, 60,
3, 11, 19, 27, 35, 43, 51, 59,
2, 10, 18, 26, 34, 42, 50, 58,
1, 9, 17, 25, 33, 41, 49, 57,
0, 8, 16, 24, 32, 40, 48, 56);
__m512i m2 = _mm512_set1_epi64(0x8040201008040201);
x = _mm512_permutexvar_epi8(s1, x);
x = _mm512_gf2p8affine_epi64_epi8(m2, x, 0);
return x;
}
std::array<uint8_t, 64> analyze_permutation(std::function<__m512i(__m512i)> perm)
{
__m512i input = _mm512_setr_epi64(
0xAAAAAAAA'AAAAAAAA,
0xCCCCCCCC'CCCCCCCC,
0xF0F0F0F0'F0F0F0F0,
0xFF00FF00'FF00FF00,
0xFFFF0000'FFFF0000,
0xFFFFFFFF'00000000,
0x00000000'00000000,
0x00000000'00000000);
__m512i permuted = perm(input);
__m512i indices = Transpose8x64(permuted);
std::array<uint8_t, 64> res;
_mm512_storeu_epi64(&res[0], indices);
return res;
}
If your bit-permutation function doesn't deal in __m512i but in plain old integers, you can of course call it 6 times. The inputs to the permutation can alternatively be calculated fairly easily by their index, but I'm going to show it in C#:
ulong mask_i = ulong.MaxValue / ((1UL << (1 << i)) + 1);
Using the indices
A nice way to bit-permute one u64 at the time given an array of indices, is the vpshufbitqmb approach mentioned in Dynamic bit shuffle using AVX-512:
// source: https://lemire.me/blog/2023/06/29/dynamic-bit-shuffle-using-avx-512/
uint64_t faster_bit_shuffle(uint64_t w, uint8_t indexes[64]) {
__m512i as_vec_register = _mm512_set1_epi64(w);
__mmask64 as_mask = _mm512_bitshuffle_epi64_mask(as_vec_register,
_mm512_loadu_si512(indexes));
return _cvtmask64_u64(as_mask);
}
Or, using even more bit-matrix transposes, we can leverage vpermb to do the bit-permutation for us across 8 u64 at the same time. vpermb does not permute at the bit-level, obviously, but it can permute 64 u8 and if we transpose our 8 u64 into 64 u8 (one u8 at index i holding the 8 i'th bits of the u64s) then we can vpermb those bytes and after transposing back into 8 u64 we will have bit-permuted them according to the specified indices. But we can do a little better than that. The second transpose, going back from 64 u8 to 8 u64, starts with a vpshufb with a fixed shufflemask. We're probably going to permute bits with the same indices multiple times (otherwise why bother doing any of this), that shuffle can be shaved off of the actual bit-permutation function by permuting our indices beforehand:
// do this once, before using the indices
__m512i byterev_qwords = _mm512_set_epi8(
8, 9, 10, 11, 12, 13, 14, 15,
0, 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14, 15,
0, 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14, 15,
0, 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14, 15,
0, 1, 2, 3, 4, 5, 6, 7);
__m512i modified_indices = _mm512_shuffle_epi8(indices, byterev_qwords);
__m512i permute_bits_qword(__m512i modified_indices, __m512i x)
{
__m512i s1 = _mm512_set_epi8(
7, 15, 23, 31, 39, 47, 55, 63,
6, 14, 22, 30, 38, 46, 54, 62,
5, 13, 21, 29, 37, 45, 53, 61,
4, 12, 20, 28, 36, 44, 52, 60,
3, 11, 19, 27, 35, 43, 51, 59,
2, 10, 18, 26, 34, 42, 50, 58,
1, 9, 17, 25, 33, 41, 49, 57,
0, 8, 16, 24, 32, 40, 48, 56);
__m512i m2 = _mm512_set1_epi64(0x8040201008040201);
__m512i s3 = _mm512_set_epi8(
63, 55, 47, 39, 31, 23, 15, 7,
62, 54, 46, 38, 30, 22, 14, 6,
61, 53, 45, 37, 29, 21, 13, 5,
60, 52, 44, 36, 28, 20, 12, 4,
59, 51, 43, 35, 27, 19, 11, 3,
58, 50, 42, 34, 26, 18, 10, 2,
57, 49, 41, 33, 25, 17, 9, 1,
56, 48, 40, 32, 24, 16, 8, 0);
x = _mm512_permutexvar_epi8(s1, x);
x = _mm512_gf2p8affine_epi64_epi8(m2, x, 0);
x = _mm512_permutexvar_epi8(modified_indices, x);
x = _mm512_gf2p8affine_epi64_epi8(m2, x, 0);
x = _mm512_permutexvar_epi8(s3, x);
return x;
}
Back to those permuted masks
Let's back up to when we had the variable permuted, before transposing it into a nice neat array of indices. If we're dealing with a BPC permutation, a permutation that can be described by how the bits of the indices (not the original bits that are being permuted) are permuted and optionally also complemented, then that is both easy to detect from the entries of permuted, and easy to analyse. Each entry of permuted will correspond to either one of the original query-masks that we put into the bit-permutation, or its complement. If (and only if) the permutation is of that form, then it is a BPC permutation, and the corresponding signed permutation is a convenient way to describe it.
My little AVX512 BPC code generator also takes that representation (generalized to 9 index bits, not 6) as its input, as an alternative to a giant array of raw indices, and does everything it does in terms of such a 9-element signed permutations (that does not prove that that's the best thing to do, maybe I should be working with signed permutation matrices that seems less error-prone). This representation has also been useful in experiments to optimize larger (multi-vector) transposes (any reasonable transpose is a BPC permutation, BP actually, sans C - but vgf2p8affineqb forces me to care about index-bit-complements), which is still a work in progress.
As usual, LLMs were not intentionally consulted while writing this post, or the accompanying code. Some of the code was generated by old-fashioned non-LLM tools. LLM-generated "AI overviews" have occasionally popped up on Google, for example while looking into the hyperoctahedral group.
