c++ - 如何在 C/C++ 或 Cuda 中按对角线有效地按位翻转 char 数组？

Question

我有一个字符数组char input[8] = "abcdabcd"，我想按对角线对它进行按位翻转，这意味着
输入:

input[0] == 'a': 0 1 1 0 0 0 0 1
input[1] == 'b': 0 1 1 0 0 0 1 0
input[2] == 'c': 0 1 1 0 0 0 1 1
input[3] == 'd': 0 1 1 0 0 1 0 0
input[4] == 'a': 0 1 1 0 0 0 0 1
input[5] == 'b': 0 1 1 0 0 0 1 0
input[6] == 'c': 0 1 1 0 0 0 1 1
input[7] == 'd': 0 1 1 0 0 1 0 0

输出:

                   a b c d a b c d
output[0] ==   0 : 0 0 0 0 0 0 0 0
output[1] == 255 : 1 1 1 1 1 1 1 1
output[2] == 255 : 1 1 1 1 1 1 1 1
output[3] ==   0 : 0 0 0 0 0 0 0 0
output[4] ==   0 : 0 0 0 0 0 0 0 0
output[5] ==  17 : 0 0 0 1 0 0 0 1
output[6] == 102 : 0 1 1 0 0 1 1 0
output[7] == 170 : 1 0 1 0 1 0 1 0

很明显，我们可以使用两个循环结合按位或操作来逐位设置目标位，但是，这意味着我们至少需要 64 * n 操作，我认为这是没有效果。
由于输入和输出只是不同方向(按行或按列)读取内存，有没有更有效的方法？
此外，我认为基于特殊内存布局或更改数组中的数字或字符来进行此操作是完全可以接受的并且有意义。
谢谢!

Answer 1

这是我基于 Hacker's Delight 技巧的代码.虽然它是 CPU 代码，但可以轻松转换为并行 CUDA 代码。

此代码本身用于转置任意大小的位图。您真正需要的是将 uint64_t x 转换为另一个 uint64_t y 的代码。

using BitBlock = uint8_t;
using BitBlocks = std::vector<BitBlock>;

void FPTransMap::transpose_bitmap( BitBlocks& bitmap, size_type blocks_per_row )
{
    assert( bitmap.size() % blocks_per_row == 0 );
    assert( ( bitmap.size() / blocks_per_row ) % 8 == 0 );

    BitBlocks transposed( bitmap.size() );
    size_type nrow = bitmap.size() / blocks_per_row, row_blocks = nrow / 8;
    for ( index_type i = 0; i < row_blocks; ++i ) {
        for ( index_type j = 0; j < blocks_per_row; ++j ) {
            uint64_t x = ( uint64_t( bitmap[   i * 8       * blocks_per_row + j ] ) << 56 ) |
                         ( uint64_t( bitmap[ ( i * 8 + 1 ) * blocks_per_row + j ] ) << 48 ) |
                         ( uint64_t( bitmap[ ( i * 8 + 2 ) * blocks_per_row + j ] ) << 40 ) |
                         ( uint64_t( bitmap[ ( i * 8 + 3 ) * blocks_per_row + j ] ) << 32 ) |
                         ( uint64_t( bitmap[ ( i * 8 + 4 ) * blocks_per_row + j ] ) << 24 ) |
                         ( uint64_t( bitmap[ ( i * 8 + 5 ) * blocks_per_row + j ] ) << 16 ) |
                         ( uint64_t( bitmap[ ( i * 8 + 6 ) * blocks_per_row + j ] ) <<  8 ) |
                         ( uint64_t( bitmap[ ( i * 8 + 7 ) * blocks_per_row + j ] ) );
            uint64_t y = (x & 0x8040201008040201LL) |
                        ((x & 0x0080402010080402LL) <<  7) |
                        ((x & 0x0000804020100804LL) << 14) |
                        ((x & 0x0000008040201008LL) << 21) |
                        ((x & 0x0000000080402010LL) << 28) |
                        ((x & 0x0000000000804020LL) << 35) |
                        ((x & 0x0000000000008040LL) << 42) |
                        ((x & 0x0000000000000080LL) << 49) |
                        ((x >>  7) & 0x0080402010080402LL) |
                        ((x >> 14) & 0x0000804020100804LL) |
                        ((x >> 21) & 0x0000008040201008LL) |
                        ((x >> 28) & 0x0000000080402010LL) |
                        ((x >> 35) & 0x0000000000804020LL) |
                        ((x >> 42) & 0x0000000000008040LL) |
                        ((x >> 49) & 0x0000000000000080LL);
            transposed[ ( j * 8 ) * row_blocks + i ]     = uint8_t( ( y >> 56 ) & 0xFF );
            transposed[ ( j * 8 + 1 ) * row_blocks + i ] = uint8_t( ( y >> 48 ) & 0xFF );
            transposed[ ( j * 8 + 2 ) * row_blocks + i ] = uint8_t( ( y >> 40 ) & 0xFF );
            transposed[ ( j * 8 + 3 ) * row_blocks + i ] = uint8_t( ( y >> 32 ) & 0xFF );
            transposed[ ( j * 8 + 4 ) * row_blocks + i ] = uint8_t( ( y >> 24 ) & 0xFF );
            transposed[ ( j * 8 + 5 ) * row_blocks + i ] = uint8_t( ( y >> 16 ) & 0xFF );
            transposed[ ( j * 8 + 6 ) * row_blocks + i ] = uint8_t( ( y >> 8 ) & 0xFF );
            transposed[ ( j * 8 + 7 ) * row_blocks + i ] = uint8_t( y & 0xFF );
        }
    }
    std::swap( bitmap, transposed );
}