我正在尝试找到一种快速简便的方法，以查找字节数组中每个位的众数（“平均值”）。
以下是我正在寻找的示例：
Byte 1 1010 1010
Byte 2 0101 0101
Byte n 1010 1000
Result 1010 1000
如果位位置大多数是1，则答案中的位位置为1。如果位位置大多数是0，则答案为0。如果1和0的出现次数相等，则我不关心在答案中放入该位置的值。
输入数量的数量级对我的用例来说很小（大约10到20个输入），但欢迎讨论您的方法随着输入数量的增加而扩展的性能。
我可以手动计算每个1和每个0的数量，然后解决问题，但我希望有一种更优雅且可能更快的方法来解决它。
bytes是一个vector<uint8_t>或array<uint8_t>。counts的表，其中包含8个整数，全部初始化为0。伪代码：For each byte B in the input set of bytes
for each bit b at index i in B
if b is set:
counts[i]++
然后使用counts来构建最终结果：
vector<int> counts(8);
uint8_t result = 0;
for (uint8_t b : bytes)
{
uint8_t mask = 0x80;
size_t needed = (bytes.size() +1) / 2;
for (size_t i = 0; i < 8; i++)
{
counts[i] += (mask & b) ? 1 : 0;
if (counts[i] >= needed)
{
result = mask | result;
}
mask = mask >> 1;
}
}
std::cout << "Result: " << result << "\n";
n == bytes.size()。 - selbie#include <stdio.h>
#include <stdint.h>
uint8_t bitvote(uint8_t *bytes, unsigned n)
{
uint8_t bit = 1;
uint8_t result = 0;
// Iterate over each bit position
for(unsigned i = 0; i < 8*sizeof(uint8_t); i++)
{
// For the current position, gather a "vote" count from each input
// byte. A 0-bit counts as -1 and a 1-bit as +1.
int vote = 0;
for(unsigned c = 0; c < n; c++)
{
vote += (bytes[c] & bit) ? 1 : -1;
}
// If the "vote" is larger than 0, there is a majority of 1-bits, so
// set the corresponding bit in the result.
// On equal count of 0's and 1's, the resulting bit is 0. To change
// that to 1, use "vote >= 0".
if(vote > 0) result |= bit;
bit = bit << 1;
}
return result;
}
int main()
{
uint8_t bytes[] = {0xaa, 0x55, 0xa8}; // Test vector of the OP
uint8_t result = bitvote(bytes, sizeof(bytes)/sizeof(bytes[0]));
printf("0x%02x", result); // Prints 0xa8 matching the OP expected result
return 0;
}
这种方法相当直接，但我认为不可能进行一些智能的位操作。部分论据如下：
考虑两个位，因此可能的组合是00、01、10、11。这给出了3种可能性：大多数为0、计数相等和大多数为1。因此，不可能将此信息压缩成单个位。因此，如果我们逐个处理输入字节，则不能具有仅为一个字节的中间状态。
for (unsigned char mask = 0x80; mask; mask >>= 1 ) {
if (data & mask) {
// 1-case
} else {
// 0-case
}
}
(data & mask) ? /* 1-case */ : /* 0-case */
在计算位数时，我们只需要计算足够的位数，直到确定下一个特定位数的大多数之前。如果数据倾向于某一方向，我们可以考虑提前退出实现。如果数据平均值非常接近，则我们别无选择，只能迭代所有记录。
当达到以下条件时，就可以确定大多数：
majority == n/2 , n even
majority == (n+1)/2 , n odd
在进行整数运算时，我们可以使用以下语句来涵盖两种情况：
int majority = (n+1) >> 1;
当我们识别到一个1-case时，我们可以通过以下方式在结果中设置一个位：
result |= mask;
#include <stdio.h>
#include <bitset>
#include <iostream>
void print_data(unsigned char data) {
std::cout << std::bitset<8>(data) << '\n';
}
void print_arr(unsigned char*data, int n) {
for (int i = 0; i < n; i++, data++) {
std::cout << "Byte " << i << " ";
print_data(*data);
}
}
unsigned char mean_arr(unsigned char*data, int n) {
int majority = (n + 1) >> 1;
unsigned char result = 0;
for (unsigned char mask = 0x80; mask; mask >>= 1 ) {
int count[2] = {0,0};
unsigned char* ptr = data;
for (int i = 0; i < n; i++, ptr++) {
if (++count[*ptr & mask ? 1 : 0] < majority) continue;
if (*ptr & mask) result |= mask;
break;
}
}
return result;
}
int main() {
unsigned char data[3] = { 0xaa, 0x55, 0xa8 };
print_arr(data, 3);
unsigned char result = mean_arr(data, 3);
std::cout << "Result ";
print_data(result);
return 0;
}
输出结果为：
Byte 0 10101010
Byte 1 01010101
Byte 2 10101000
Result 10101000
https://dev59.com/G2oy5IYBdhLWcg3wkO-g#51750902
使用他们的公式，我们可以写出以下内容：
// The following is valid only if the size of the span is less than 256,
// otherwise a temporary array must be used to accumulate the results
// every 255 elements.
auto bits_mode(std::span<std::uint8_t> src) -> std::uint8_t
{
// Multiplying a byte by this 64-bit constant will "copy" it in 8
// different positions with a gap of 1 bit between them.
//
// E.g. given x = 10100100
// 10100100
// * 1000000001000000001000000001000000001000000001000000001000000001
// = 0010100100010100100010100100010100100010100100010100100010100100
// ^ ^^^^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^^^^^
constexpr std::uint64_t mult {
0b10000000'01000000'00100000'00010000'00001000'00000100'00000010'00000001
};
// The gaps between the copies is crucial, it let us retrieve the
// spread bits (with reversed endianness) with a simple mask:
//
// & 1000000010000000100000001000000010000000100000001000000010000000
// = 0000000000000000100000000000000000000000100000000000000010000000
// ^ ^ ^ ^ ^ ^ ^ ^
constexpr std::uint64_t mask {
0b10000000'10000000'10000000'10000000'10000000'10000000'10000000'10000000
};
// Shifting the intermediate gives us something we can safely sum up
// to 255 times.
//
// >> 7
// = 0000000000000000000000010000000000000000000000010000000000000001
// ^ ^ ^ ^ ^ ^ ^ ^
constexpr auto expand = [] (std::uint8_t x) -> std::uint64_t {
return ((x * mult) & mask) >> 7;
};
auto result{ std::transform_reduce( src.begin(), src.end()
, std::uint64_t{}
, std::plus<>{}, expand ) };
// the resulting byte can be formed a bit at a time "traversing"
// the bytes of the previous sum.
std::uint64_t target{ src.size() / 2 };
std::uint8_t mode{};
for ( int i{8}; i--; )
{
mode |= ((result & 0xff) > target) << i;
result >>= 8;
}
return mode;
}
对于标准的C++，已经有很多答案了。
评论中有人说：“但我认为没有一种位操作技巧可以让你在不检查单个位的情况下完成此操作。”，这促使我编写了这篇文章，它基于Intel内置函数而不是标准的C++。
您可以使用PDEP将位提取到U64字节中（如果输入中有超过256个元素，请相应地调整PDEP以使用多个U64，并为每个位累加器“通道”增加位宽度）。
英特尔BMI的维基百科链接, 英特尔内置函数参考, 相关的Stack Overflow问题。
您可以使用std::transform_reduce 和 std::execution::par_unseq，其中 transform 是 PDEP 展开，reduce 是 sum 操作（假设您根据溢出不可能的输入数量将每个 lane 的位宽设置得足够宽），最后，如果一个 lane 的值超过输入字节数的一半，则将输出的相应位设置为 1。这部分可能有一种花哨的 SIMD 方法来完成，但该步骤的性能影响是一个常数因子（而且我现在懒得找到那种方法）。有一种有点繁琐的方法，可以使用std::uint8_t和std::uint64_t来实现相同的效果。它（几乎）是无分支且原地排序的。但是，下面我会讨论一个注意事项。
如果您有一系列位，并对其进行排序，则可以查看中间值并获得平均值。实际上，您可以获得任何所需的分位数。这是因为位是二进制的。
例如：01001010001 -> 00000001111 -> 中间位是0 -> 平均值是0。
如果您有两个数字a和b，则可以通过意识到将所有1“向下”移动并将所有0“向上”移动的结果来按列对位进行排序：
// pseudo-swap:
a2 = a&b;
b2 = a|b;
这可以保证总的0和1的数量不变，并且它是位并行的。 而且无需分支。
将此应用于n个值而不使用分支不像人们想象中的那么简单。平凡的解决方案是伪交换每个值与另一个值，这在纸面上具有二次复杂度，但也是无需分支（除了可以轻松地进行分支预测或展开的循环之外），并且除现有数组外不需要额外的内存。 我相信肯定有更好的方法来解决这个问题，但我想不出来。或许有人能够进一步发展这个想法。
该算法将此变为：
11010000
00100010
11100111
11010101
00100000
11111000
11101001
转换成这个：
00000000
00000000
11100000
11100000 <--- your average
11110001
11111111
11111111
void pseudoswap(std::uint8_t& a, std::uint8_t& b) {
auto const fst = a & b;
auto const snd = a | b;
a = fst;
b = snd;
}
template <std::size_t N>
void sieve(std::uint8_t (&xs)[N]) {
for (auto i = 0; i < N; ++i) {
for (auto j = i+1; j < N; ++j) {
pseudoswap(xs[i],xs[j]);
}
}
}
看看 编译器资源管理器上的演示，它展示了一些主要实现的不错优化：
.L88:
mov rsi, r8
add r8, 1
mov rax, rsi
.L90:
movzx edx, BYTE PTR [rsi-1]
movzx ecx, BYTE PTR [rax]
add rax, 1
mov edi, edx
or edx, ecx
and edi, ecx
mov BYTE PTR [rsi-1], dil
mov BYTE PTR [rax-1], dl
cmp rbx, rax
jne .L90
cmp rbx, r8
jne .L88
对于小的数组大小，sieve 循环似乎在热路径中没有任何跳转。
这个算法的复杂度是二次的听起来很糟糕。但你说你的输入数组非常小，只有10到20个元素。这意味着b*n和n*n（其中b是一个字中的位数）的复杂度在实际上无法区分，因为b和n的数量级相当。这种方法的优势在于：
如果你的数据量达到了百万或十亿字节的级别，那么应该切换到一种计算1的个数的解决方案，因为二次复杂度会成为一个问题。
如果有疑问，请进行性能测试！
std::uint8_t xs[]{1,2,3,128,128};检查了你的代码，但无法解释你的输出。但也许我错了…… - A M以下是部分答案，因为我的方法无法处理任意数量的输入字节。它可以处理已知有效排序网络的任何数量的输入。下面的代码中，我展示了长度为2到16个字节的数组的示例。
Knuth，TAOCP，vol. 4A，第7.1.1节详细解释了三进制主要操作⟨xyz⟩ = (x ∧ y) ∨ (y ∧ z) ∨ (x ∧ z) 的实用性。当按位应用这个函数到三个输入时，将实现问者所请求的结果。Knuth更喜欢将该函数称为“中位数”，而不是“多数派”，因为如果让∧对应于min，∨对应于max，那么⟨xyz⟩= y恰当地表示x≤y≤z。
有趣的观察是，构建排序网络的一种方法是使用min和max原语。三个数的中位数median3(x,y,z) = min(max(min(y,z),x),max(y,z))，而min3(x,y,z) = min(x,min(y,z))和max3(x,y,z) = max(x,max(y,z))。
Knuth指出，任何单调布尔函数都可以仅使用中位数操作和常量0和1来表示。因此，五个数的中位数也可以用这种方式表示，而根据Knuth（第64页）的说法，最有效的排列方式是⟨vwxyz⟩=⟨v⟨xyz⟩⟨wx⟨wyz⟩⟩⟩。
为了测试位运算中值计算是否可由排序网络推导出，我使用了一篇文献中的九输入网络，并将其转换成位中值计算。这个计算方法能够提供询问者所需的结果。我还将之前研究中获得的一些搜索网络图形转化成相应的最大/最小操作序列，并翻译了TAOCP第3卷中的其他网络图形。对于额外的排序网络，我参考了代码注释中提到的Bert Dobbelaere's列表。维基百科有关排序网络的文章指出，已知具有(近)最优性的排序网络可达20个输入，因此涵盖了询问者感兴趣的数组长度范围。
关于效率，下面代码中的byte_mode_16()使用Clang 16编译，编译成大约170个x86指令，并具有很多指令级并行性，因此我会估计它可以在现代x86-64 CPU上执行约50个周期。在支持任意三输入逻辑操作的NVIDIA GPU上，使用LOP3指令编译的相同函数只需大约80条指令。#include <cstdio>
#include <cstdlib>
#include <climits>
#include <cstdint>
#define REPS (1000000)
#define N (16)
#define USE_KNUTH (0)
uint8_t byte_mode_ref (const uint8_t *bytes, int n)
{
int count1 [CHAR_BIT] = {0, 0, 0, 0, 0, 0, 0, 0};
uint8_t res = 0;
for (int i = 0; i < n; i++) {
uint8_t a = bytes [i];
for (int j = 0; j < CHAR_BIT; j++) {
uint8_t bit = (a >> j) & 1;
count1 [j] += bit;
}
}
for (int j = 0; j < CHAR_BIT; j++) {
res |= (count1[j] > (n / 2)) << j;
}
return res;
}
#define MIN3(x,y,z) (x & y & z)
#define MEDIAN3(x,y,z) (((y & z) | x) & (y | z))
#define MAX3(x,y,z) (x | y | z)
#define MIN2(x,y) (x & y)
#define MAX2(x,y) (x | y)
#define SWAP(i,j) do { int s = MIN2(a##i,a##j); int t = MAX2(a##i,a##j); a##i = s; a##j = t; } while (0)
uint8_t byte_mode_2 (const uint8_t *bytes)
{
int x = bytes [0];
int y = bytes [1];
return MIN2 (x, y);
}
uint8_t byte_mode_3 (const uint8_t *bytes)
{
int x = bytes [0];
int y = bytes [1];
int z = bytes [2];
return MEDIAN3 (x, y, z);
}
uint8_t byte_mode_4 (const uint8_t *bytes)
{
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
SWAP (0, 2); SWAP (1, 3);
SWAP (0, 1); SWAP (2, 3);
SWAP (1, 2);
return a1;
}
uint8_t byte_mode_5 (const uint8_t *bytes)
{
#if USE_KNUTH
int v = bytes [0];
int w = bytes [1];
int x = bytes [2];
int y = bytes [3];
int z = bytes [4];
/* Knuth, TAOCP, Vol. 4a, p. 64 */
return MEDIAN3 (v, MEDIAN3 (x, y, z), MEDIAN3 (w, x, (MEDIAN3 (w, y, z))));
#else // USE_KNUTH
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
int a4 = bytes [4];
SWAP (0, 3); SWAP (1, 4);
SWAP (0, 2); SWAP (1, 3);
SWAP (0, 1); SWAP (2, 4);
SWAP (1, 2); SWAP (3, 4);
SWAP (2, 3);
return a2;
#endif // USE_KNUTH
}
uint8_t byte_mode_6 (const uint8_t *bytes)
{
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
int a4 = bytes [4];
int a5 = bytes [5];
SWAP (0, 5); SWAP (1, 3); SWAP (2,4);
SWAP (1, 2); SWAP (3, 4);
SWAP (0, 3); SWAP (2, 5);
SWAP (0, 1); SWAP (2, 3); SWAP (4, 5);
SWAP (1, 2); SWAP (3, 4);
return a2;
}
uint8_t byte_mode_7 (const uint8_t *bytes)
{
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
int a4 = bytes [4];
int a5 = bytes [5];
int a6 = bytes [6];
SWAP (0, 6); SWAP (2, 3); SWAP (4, 5);
SWAP (0, 2); SWAP (1, 4); SWAP (3, 6);
SWAP (0, 1); SWAP (2, 5); SWAP (3, 4);
SWAP (1, 2); SWAP (4, 6);
SWAP (2, 3); SWAP (4, 5);
SWAP (1, 2); SWAP (3, 4); SWAP (5, 6);
return a3;
}
uint8_t byte_mode_8 (const uint8_t *bytes)
{
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
int a4 = bytes [4];
int a5 = bytes [5];
int a6 = bytes [6];
int a7 = bytes [7];
SWAP (0, 2); SWAP (1, 3); SWAP (4, 6); SWAP (5, 7);
SWAP (0, 4); SWAP (1, 5); SWAP (2, 6); SWAP (3, 7);
SWAP (0, 1); SWAP (2, 3); SWAP (4, 5); SWAP (6, 7);
SWAP (2, 4); SWAP (3, 5);
SWAP (1, 4); SWAP (3, 6);
SWAP (1, 2); SWAP (3, 4); SWAP (5, 6);
return a3;
}
uint8_t byte_mode_9 (const uint8_t *bytes)
{
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
int a4 = bytes [4];
int a5 = bytes [5];
int a6 = bytes [6];
int a7 = bytes [7];
int a8 = bytes [8];
int b0, b1, b2, b3, b4, b5, b6, b7, b8;
int c2, c4, c6;
/*
Chaitali Chakrabarti and Li-Yu Wang, "Novel sorting network-based
architectures for rank order filters." IEEE Transactions on Very
Large Scale Integration Systems, Vol. 2, No. 4, 1994, pp. 502-507
*/
// SORT3 (0, 1, 2)
b0 = MIN3 (a0, a1, a2);
b1 = MEDIAN3 (a0, a1, a2);
b2 = MAX3 (a0, a1, a2);
// SORT3 (3, 4, 5)
b3 = MIN3 (a3, a4, a5);
b4 = MEDIAN3 (a3, a4, a5);
b5 = MAX3 (a3, a4, a5);
// SORT3 (6, 7, 8)
b6 = MIN3 (a6, a7, a8);
b7 = MEDIAN3 (a6, a7, a8);
b8 = MAX3 (a6, a7, a8);
// SORT3 (0, 3, 6)
// c0 = MIN3 (b0, b3, b6);
// c3 = MEDIAN3 (b0, b3, b6);
c6 = MAX3 (b0, b3, b6);
// SORT3 (1, 4, 7)
// c1 = MIN3 (b1, b4, b7);
c4 = MEDIAN3 (b1, b4, b7);
// c7 = MAX3 (b1, b4, b7);
// SORT3 (2, 5, 8)
c2 = MIN3 (b2, b5, b8);
// c5 = MEDIAN3 (b2, b5, b8);
// c8 = MAX3 (b2, b5, b8);
// final median computation
// SORT3 (2, 4, 6)
return MEDIAN3 (c2, c4, c6);
}
uint8_t byte_mode_10 (const uint8_t *bytes)
{
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
int a4 = bytes [4];
int a5 = bytes [5];
int a6 = bytes [6];
int a7 = bytes [7];
int a8 = bytes [8];
int a9 = bytes [9];
#if USE_KNUTH
/* Knuth, TAOCP, vol. 3, p. 227 */
SWAP (4, 9); SWAP (3, 8); SWAP (2, 7); SWAP (1, 6); SWAP (0, 5);
SWAP (1, 4); SWAP (6, 9); SWAP (0, 3); SWAP (5, 8);
SWAP (0, 2); SWAP (3, 6); SWAP (7, 9);
SWAP (0, 1); SWAP (2, 4); SWAP (5, 7); SWAP (8, 9);
SWAP (4, 6); SWAP (1, 2); SWAP (7, 8); SWAP (3, 5);
SWAP (2, 5); SWAP (6, 8); SWAP (1, 3); SWAP (4, 7);
SWAP (2, 3); SWAP (6, 7);
SWAP (3, 4); SWAP (5, 6);
SWAP (4, 5);
#else // USE_KNUTH
/* https://bertdobbelaere.github.io/sorting_networks.html */
SWAP (0, 8); SWAP (1, 9); SWAP (2, 7); SWAP (3, 5); SWAP (4, 6);
SWAP (0, 2); SWAP (1, 4); SWAP (5, 8); SWAP (7, 9);
SWAP (0, 3); SWAP (2, 4); SWAP (5, 7); SWAP (6, 9);
SWAP (0, 1); SWAP (3, 6); SWAP (8, 9);
SWAP (1, 5); SWAP (2, 3); SWAP (4, 8); SWAP (6, 7);
SWAP (1, 2); SWAP (3, 5); SWAP (4, 6); SWAP (7, 8);
SWAP (2, 3); SWAP (4, 5); SWAP (6, 7);
SWAP (3, 4); SWAP (5, 6);
#endif // USE_KNUTH
return a4;
}
uint8_t byte_mode_11 (const uint8_t *bytes)
{
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
int a4 = bytes [4];
int a5 = bytes [5];
int a6 = bytes [6];
int a7 = bytes [7];
int a8 = bytes [8];
int a9 = bytes [9];
int a10 = bytes [10];
/* https://bertdobbelaere.github.io/sorting_networks.html */
SWAP (0, 9); SWAP (1, 6); SWAP (2, 4); SWAP (3, 7); SWAP (5, 8);
SWAP (0, 1); SWAP (3, 5); SWAP (4, 10); SWAP (6, 9); SWAP (7, 8);
SWAP (1, 3); SWAP (2, 5); SWAP (4, 7); SWAP (8, 10);
SWAP (0, 4); SWAP (1, 2); SWAP (3, 7); SWAP (5, 9); SWAP (6, 8);
SWAP (0, 1); SWAP (2, 6); SWAP (4, 5); SWAP (7, 8); SWAP (9, 10);
SWAP (2, 4); SWAP (3, 6); SWAP (5, 7); SWAP (8, 9);
SWAP (1, 2); SWAP (3, 4); SWAP (5, 6); SWAP (7, 8);
SWAP (2, 3); SWAP (4, 5); SWAP (6, 7);
return a5;
}
uint8_t byte_mode_12 (const uint8_t *bytes)
{
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
int a4 = bytes [4];
int a5 = bytes [5];
int a6 = bytes [6];
int a7 = bytes [7];
int a8 = bytes [8];
int a9 = bytes [9];
int a10 = bytes [10];
int a11 = bytes [11];
#if USE_KNUTH
/* Knuth, TAOCP, vol. 3, p. 227 */
SWAP (0, 1); SWAP (2, 3); SWAP (4, 5); SWAP (6, 7); SWAP (8, 9); SWAP (10, 11);
SWAP (1, 3); SWAP (5, 7); SWAP (9, 11); SWAP (0, 2); SWAP (4, 6); SWAP ( 8, 10);
SWAP (1, 2); SWAP (5, 6); SWAP (9, 10);
SWAP (1, 5); SWAP (6, 10);
SWAP (2, 6); SWAP (5, 9);
SWAP (1, 5); SWAP (6, 10);
SWAP (0, 4); SWAP (7, 11);
SWAP (3, 7); SWAP (4, 8);
SWAP (0, 4); SWAP (7, 11);
SWAP (1, 4); SWAP (7, 10); SWAP (3, 8);
SWAP (2, 3); SWAP (8, 9);
SWAP (2, 4); SWAP (7, 9); SWAP (3, 5); SWAP (6, 8);
SWAP (3, 4); SWAP (5, 6); SWAP (7, 8);
#else // USE_KNUTH
/* https://bertdobbelaere.github.io/sorting_networks.html */
SWAP (0, 8); SWAP (1, 7); SWAP (2, 6); SWAP (3, 11); SWAP (4, 10); SWAP (5, 9);
SWAP (0, 1); SWAP (2, 5); SWAP (3, 4); SWAP (6, 9); SWAP (7, 8); SWAP (10, 11);
SWAP (0, 2); SWAP (1, 6); SWAP (5, 10); SWAP (9, 11);
SWAP (0, 3); SWAP (1, 2); SWAP (4, 6); SWAP (5, 7); SWAP (8, 11); SWAP (9, 10);
SWAP (1, 4); SWAP (3, 5); SWAP (6, 8); SWAP (7, 10);
SWAP (1, 3); SWAP (2, 5); SWAP (6, 9); SWAP (8, 10);
SWAP (2, 3); SWAP (4, 5); SWAP (6, 7); SWAP (8, 9);
SWAP (4, 6); SWAP (5, 7);
SWAP (3, 4); SWAP (5, 6); SWAP (7, 8);
#endif // USE_KNUTH
return a5;
}
uint8_t byte_mode_13 (const uint8_t *bytes)
{
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
int a4 = bytes [4];
int a5 = bytes [5];
int a6 = bytes [6];
int a7 = bytes [7];
int a8 = bytes [8];
int a9 = bytes [9];
int a10 = bytes [10];
int a11 = bytes [11];
int a12 = bytes [12];
/* Knuth, TAOCP, vol. 3, p. 227 */
SWAP (0, 5); SWAP ( 8, 12); SWAP (1, 7); SWAP ( 3, 9); SWAP ( 2, 4); SWAP (6, 11);
SWAP (0, 6); SWAP ( 7, 9); SWAP (1, 3); SWAP ( 5, 11); SWAP ( 2, 8); SWAP (4, 12);
SWAP (0, 2); SWAP ( 4, 5); SWAP (6, 8); SWAP ( 9, 10); SWAP (11, 12);
SWAP (7, 8); SWAP (10, 12); SWAP (5, 9); SWAP ( 3, 11);
SWAP (1, 5); SWAP ( 9, 11); SWAP (2, 3); SWAP ( 4, 7); SWAP ( 8, 10);
SWAP (0, 1); SWAP ( 5, 6); SWAP (8, 9); SWAP (10, 11);
SWAP (3, 6); SWAP ( 2, 5); SWAP (1, 4); SWAP ( 7, 8); SWAP ( 9, 10);
SWAP (3, 7); SWAP ( 1, 2); SWAP (4, 5); SWAP ( 6, 8);
SWAP (2, 4); SWAP ( 6, 7); SWAP (3, 5); SWAP ( 8, 9);
SWAP (3, 4); SWAP ( 5, 6);
return a6;
}
uint8_t byte_mode_14 (const uint8_t *bytes)
{
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
int a4 = bytes [4];
int a5 = bytes [5];
int a6 = bytes [6];
int a7 = bytes [7];
int a8 = bytes [8];
int a9 = bytes [9];
int a10 = bytes [10];
int a11 = bytes [11];
int a12 = bytes [12];
int a13 = bytes [13];
/* https://bertdobbelaere.github.io/sorting_networks.html */
SWAP (0, 1); SWAP (2, 3); SWAP (4, 5); SWAP (6, 7); SWAP ( 8, 9); SWAP (10, 11); SWAP (12, 13);
SWAP (0, 2); SWAP (1, 3); SWAP (4, 8); SWAP (5, 9); SWAP (10, 12); SWAP (11, 13);
SWAP (0, 10); SWAP (1, 6); SWAP (2, 11); SWAP (3, 13); SWAP ( 5, 8); SWAP ( 7, 12);
SWAP (1, 4); SWAP (2, 8); SWAP (3, 6); SWAP (5, 11); SWAP ( 7, 10); SWAP ( 9, 12);
SWAP (0, 1); SWAP (3, 9); SWAP (4, 10); SWAP (5, 7); SWAP ( 6, 8); SWAP (12, 13);
SWAP (1, 5); SWAP (2, 4); SWAP (3, 7); SWAP (6, 10); SWAP ( 8, 12); SWAP ( 9, 11);
SWAP (1, 2); SWAP (3, 5); SWAP (4, 6); SWAP (7, 9); SWAP ( 8, 10); SWAP (11, 12);
SWAP (2, 3); SWAP (4, 5); SWAP (6, 7); SWAP (8, 9); SWAP (10, 11);
SWAP (3, 4); SWAP (5, 6); SWAP (7, 8); SWAP (9, 10);
return a6;
}
uint8_t byte_mode_15 (const uint8_t *bytes)
{
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
int a4 = bytes [4];
int a5 = bytes [5];
int a6 = bytes [6];
int a7 = bytes [7];
int a8 = bytes [8];
int a9 = bytes [9];
int a10 = bytes [10];
int a11 = bytes [11];
int a12 = bytes [12];
int a13 = bytes [13];
int a14 = bytes [14];
/* https://bertdobbelaere.github.io/sorting_networks.html */
SWAP (0, 6); SWAP (1, 10); SWAP (2,14); SWAP (3, 9); SWAP ( 4, 12); SWAP ( 5, 13); SWAP ( 7, 11);
SWAP (0, 7); SWAP (2, 5); SWAP (3, 4); SWAP (6, 11); SWAP ( 8, 10); SWAP ( 9, 12); SWAP (13, 14);
SWAP (1, 13); SWAP (2, 3); SWAP (4, 6); SWAP (5, 9); SWAP ( 7, 8); SWAP (10, 14); SWAP (11, 12);
SWAP (0, 3); SWAP (1, 4); SWAP (5, 7); SWAP (6, 13); SWAP ( 8, 9); SWAP (10, 11); SWAP (12, 14);
SWAP (0, 2); SWAP (1, 5); SWAP (3, 8); SWAP (4, 6); SWAP ( 7, 10); SWAP ( 9, 11); SWAP (12, 13);
SWAP (0, 1); SWAP (2, 5); SWAP (3,10); SWAP (4, 8); SWAP ( 6, 7); SWAP ( 9, 12); SWAP (11, 13);
SWAP (1, 2); SWAP (3, 4); SWAP (5, 6); SWAP (7, 9); SWAP ( 8, 10); SWAP (11, 12);
SWAP (3, 5); SWAP (4, 6); SWAP (7, 8); SWAP (9, 10);
SWAP (2, 3); SWAP (4, 5); SWAP (6, 7); SWAP (8, 9); SWAP (10, 11);
return a7;
}
uint8_t byte_mode_16 (const uint8_t *bytes)
{
int a0 = bytes [0];
int a1 = bytes [1];
int a2 = bytes [2];
int a3 = bytes [3];
int a4 = bytes [4];
int a5 = bytes [5];
int a6 = bytes [6];
int a7 = bytes [7];
int a8 = bytes [8];
int a9 = bytes [9];
int a10 = bytes [10];
int a11 = bytes [11];
int a12 = bytes [12];
int a13 = bytes [13];
int a14 = bytes [14];
int a15 = bytes [15];
/* Knuth TAOCP, vol. 3, p. 229 */
SWAP (0, 1); SWAP ( 2, 3); SWAP ( 4, 5); SWAP ( 6, 7); SWAP ( 8, 9); SWAP (10, 11); SWAP (12, 13); SWAP (14, 15);
SWAP (1, 3); SWAP ( 5, 7); SWAP ( 9, 11); SWAP (13, 15); SWAP ( 0, 2); SWAP ( 4, 6); SWAP ( 8, 10); SWAP (12, 14);
SWAP (3, 7); SWAP (11, 15); SWAP ( 2, 6); SWAP (10, 14); SWAP ( 1, 5); SWAP ( 9, 13); SWAP ( 0, 4); SWAP ( 8, 12);
SWAP (7, 15); SWAP ( 6, 14); SWAP ( 5, 13); SWAP ( 4, 12); SWAP ( 3, 11); SWAP ( 2, 10); SWAP ( 1, 9); SWAP ( 0, 8);
SWAP (1, 2); SWAP ( 3, 12); SWAP (13, 14); SWAP ( 7, 11); SWAP ( 4, 8); SWAP ( 5, 10); SWAP ( 6, 9);
SWAP (1, 4); SWAP (11, 14); SWAP ( 7, 13); SWAP ( 2, 8); SWAP ( 6, 12); SWAP ( 3, 10); SWAP ( 5, 9);
SWAP (3, 5); SWAP ( 7, 9); SWAP (11, 13); SWAP ( 2, 4); SWAP ( 6, 8); SWAP (10, 12);
SWAP (5, 8); SWAP ( 9, 12); SWAP ( 3, 6); SWAP ( 7, 10);
SWAP (3, 4); SWAP ( 5, 6); SWAP ( 7, 8); SWAP ( 9, 10); SWAP (11, 12);
return a7;
}
// George Marsaglia's KISS PRNG, period 2**123. Newsgroup sci.math, 21 Jan 1999
// Bug fix: Greg Rose, "KISS: A Bit Too Simple" http://eprint.iacr.org/2011/007
static uint32_t kiss_z=362436069, kiss_w=521288629;
static uint32_t kiss_jsr=123456789, kiss_jcong=380116160;
#define znew (kiss_z=36969*(kiss_z&65535)+(kiss_z>>16))
#define wnew (kiss_w=18000*(kiss_w&65535)+(kiss_w>>16))
#define MWC ((znew<<16)+wnew )
#define SHR3 (kiss_jsr^=(kiss_jsr<<13),kiss_jsr^=(kiss_jsr>>17), \
kiss_jsr^=(kiss_jsr<<5))
#define CONG (kiss_jcong=69069*kiss_jcong+1234567)
#define KISS ((MWC^CONG)+SHR3)
int main (void)
{
uint8_t res, ref, arr [N];
printf ("Testing byte arrays of length %d\n", N);
for (int i = 0; i < REPS; i++) {
for (int j = 0; j < N; j++) {
arr [j] = KISS;
}
ref = byte_mode_ref (arr, N);
#if N==2
res = byte_mode_2 (arr);
#elif N==3
res = byte_mode_3 (arr);
#elif N==4
res = byte_mode_4 (arr);
#elif N==5
res = byte_mode_5 (arr);
#elif N==6
res = byte_mode_6 (arr);
#elif N==7
res = byte_mode_7 (arr);
#elif N==8
res = byte_mode_8 (arr);
#elif N==9
res = byte_mode_9 (arr);
#elif N==10
res = byte_mode_10 (arr);
#elif N==11
res = byte_mode_11 (arr);
#elif N==12
res = byte_mode_12 (arr);
#elif N==13
res = byte_mode_13 (arr);
#elif N==14
res = byte_mode_14 (arr);
#elif N==15
res = byte_mode_15 (arr);
#elif N==16
res = byte_mode_16 (arr);
#else
#error unsupported value of N
#endif
if (res != ref) {
printf ("Error: res=%02x ref=%02x bytes: ", res, ref);
for (int j = 0; j < N; j++) {
printf ("%02x ", arr[j]);
}
printf ("\nTest FAILED\n");
return EXIT_FAILURE;
}
}
printf ("Test PASSED\n");
return EXIT_SUCCESS;
}
popcount包装起来，否则由于+的工作方式，高位会支配低位。 - bitmask