C/C++ 또는 Cuda에서 문자 배열을 대각선으로 효과적으로 비트 플립하려면 어떻게해야합니까?

Question

나는 char 배열 char input[8] = "abcdabcd" 있고, 내 말은하는, 대각선하여 플립 비트 단위하려는
input :

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 

output :

    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); 
}