비트 순서 효율적으로 뒤집기

흔히 발생하는 endian 문제와 달리 아주 드물게 필요한 기능이 비트 오더링 뒤집기입니다. 통신칩이 msb:lsb 순서를 반대로 요구하는 경우가 있습니다. 이런 경우에 소프트웨어적으로 비트순서를 뒤집어 줘야 합니다.

팩스 보드에서 들어오고 나가는 스트림의 비트순서를 뒤집어야 할 일이 있었는데, 이게 막상 해보면 효율적으로 처리하기가 쉽지 않았습니다. 당시에 제가 작성한 코드는 이런 것이었습니다.

unsigned char reverse(unsigned char b) {
   unsigned char bb = 0;
   
   if (b & 0x80) bb |= 0x01;
   if (b & 0x40) bb |= 0x02;
   if (b & 0x20) bb |= 0x04;
   if (b & 0x10) bb |= 0x08;
   if (b & 0x08) bb |= 0x10;
   if (b & 0x04) bb |= 0x20;
   if (b & 0x02) bb |= 0x40;
   if (b & 0x01) bb |= 0x80;
   
   return bb;
}

논리연산이 16번이라서 성능이 안 좋을 것 같았습니다. 그래도 문제는 없어서 그냥 사용했는데 두고두고 찜찜했습니다.

이런 경우 성능을 높이는 방법을 찾아 봤습니다.

1. 스와핑 반복

4비트를 4만큼 이동해서 swap → 2비트를 2만큼 이동 → 1비트를 1만큼 이동

unsigned char reverse(unsigned char b) {
   b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
   b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
   b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
   return b;
}

그림으로 표시하면 이렇습니다.

연산량은 논리연산 6번으로 줄어듭니다. (시프트는 instruction 레벨에선 비용이 없는 경우가 많습니다)

2. 테이블화

위의 방법이 멋지긴 하지만, 이런 문제에는 참조 테이블보다 강력한 방법이 없습니다.

바이트니까 입력값의 종류가 256개라서 출력값을 256개의 배열로 만드는 게 제일 빠릅니다.

unsigned char reverse(unsigned char b) {
    static const unsigned char table[] = {
        0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
        0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
        0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
        0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
        0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
        0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
        0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
        0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
        0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
        0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
        0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
        0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
        0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
        0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
        0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
        0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
        0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
        0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
        0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
        0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
        0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
        0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
        0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
        0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
        0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
        0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
        0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
        0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
        0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
        0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
        0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
        0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
    };
    return table[x];
}

메모리는 잡아먹긴 하지만 성능은 최강입니다.

갑자기 그때 코딩하면서 찜찜했던 게 생각나서 찾아봤네요. (2002년… ^^;)