以 32/64 位数量有效地移位字节？

Question

为简单起见，假设我使用的是 32 位小端处理器并声明了以下 4 字节缓冲区：

unsigned char buffer[] = { 0xab, 0xcd, 0xef, 0x46 };

假设我的目标是将缓冲区中的每个字节按位左移 4 位。也就是说，我想将缓冲区值转换为： { 0xbc, 0xde, 0xf4, 0x60 }。要执行这样的转换，可以编写如下代码：

for (int i = 0; i < 3; ++i)
{
  buffer[i] <<= 4; 
  buffer[i] |= (buffer[i + 1] >> 4);
}
buffer[3] <<= 4;

虽然这可行，但我更愿意使用处理器的本机 32 位寄存器同时移动所有 4 个字节：

unsigned char buffer[] = { 0xab, 0xcd, 0xef, 0x46 };
unsigned int *p = (unsigned int*)buffer; // unsigned int is 32 bit on my platform
*p <<= 4;

上面的代码片段成功地执行了一次转换，但不是我正在寻找的方式。似乎因为我将缓冲区转换为无符号整数，所以寄存器被加载（小端）值 0x46efcdab（而不是 0xabcdef46）。因此，执行 4 位左移会导致 0xb0dafc6e 而不是 0xbcdef460。

除了在移位之前交换字节（例如 htonl 等）之外，还有什么技巧可以按照我想要的方式有效地移位字节吗？

提前感谢您的见解。

Answer 1

使用 htonl/ntohl 在 network（big-endian）字节顺序和 native 之间切换字节顺序：

uint32_t *p = (uint32_t*)buffer;
*p = htonl(ntohl(*p) << 4);

实际上，这会将缓冲区内容作为整数以大端顺序加载，执行移位，然后以大端顺序将其写回。

这会在 x86 上编译成几个 bswap 指令，因此它应该相当高效 (gcc -O3)。

这是一些测试代码（buffer 是全局代码以避免常量折叠，return 防止死代码消除）：

#include <stdint.h>    // uint32_t
#include <arpa/inet.h> // ntohl, htonl

unsigned char buffer[] = { 0xab, 0xcd, 0xef, 0x46 };

int main() {
    uint32_t *p = (uint32_t*)buffer; // unsigned int is 32 bit on my platform
    *p = htonl(ntohl(*p) << 4);
    return *p;
}

这会编译成以下相当简单的机器代码（x86-64；LLVM 7.0.2；cc -O2）：

0000000000000000    pushq   %rbp           ; frame setup
0000000000000001    movq    %rsp, %rbp     ; frame setup
0000000000000004    movl    (%rip), %eax   ; load buffer
000000000000000a    bswapl  %eax           ; endian flip
000000000000000c    shll    [=12=]x4, %eax     ; shift
000000000000000f    bswapl  %eax           ; endian flip
0000000000000011    movl    %eax, (%rip)   ; save buffer
0000000000000017    popq    %rbp           ; finish
0000000000000018    retq

Answer 2

只是为了比较，您可以在不使用 htonl/ntohl 的情况下执行此操作。这假设一个小端 CPU:

#include <stdint.h>

void lshift(unsigned char* buf) {
  uint32_t* p = (uint32_t*)buf;
  uint32_t lo = *p & 0x0F0F0F0F;
  uint32_t hi = *p & 0xF0F0F000;
  *p = (lo << 4) | (hi >> 12);
}

以及生成的程序集 gcc -O3:

pushq   %rbp
movq    %rsp, %rbp
movl    (%rdi), %eax
movl    %eax, %ecx
shll    , %ecx
andl    $-252645136, %ecx       ## imm = 0xFFFFFFFFF0F0F0F0
shrl    , %eax
andl    6895, %eax           ## imm = 0xF0F0F
orl     %ecx, %eax
movl    %eax, (%rdi)
popq    %rbp
retq

根据 bswapl 的周期数，它可能是更快的替代方案。

以 32/64 位数量有效地移位字节？

Efficiently bitshifting bytes in 32/64 bit quantities?

c

bit-manipulation

bit-shift