Bitshifting-Bytes in 32/64-Bit-Mengen effizient?

Question

Der Einfachheit halber nehmen, ich bin ein 32-Bit-Little-Endian-Prozessor und haben die folgenden 4-Byte-Puffer erklärt:

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

Sagen wir, mein Ziel jedes Byte in dem Puffer zu bitweise Verschiebung nach links ist um 4 Bits. Das heißt, ich möchte die Pufferwerte wie folgt transformieren: { 0xbc, 0xde, 0xf4, 0x60 }. Zur Durchführung einer solchen Transformation könnte schreiben einen Code wie:

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

Während dies funktioniert, würde ich viel lieber alle 4 Bytes verschieben gleichzeitig mein Prozessor native 32-Bit-Register mit:

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

Die oben Snippet führt erfolgreich eine Verschiebung durch, aber nicht auf die Art, nach der ich suche. Es scheint, dass, da ich Puffer zu einem unsigned Int Casting bin, das Register geladen wird (Little-Endian) mit dem Wert 0x46efcdab (anstelle von 0xabcdef46). Folglich führt das Ausführen der 4-Bit-Linksverschiebung zu 0xb0dafc6e anstelle von 0xbcdef460.

Neben dem Austauschen von Bytes vor der Verschiebung (z. B. htonl et al.) Gibt es irgendwelche Tricks für die effiziente Verschiebung von Bytes in der Art, die ich suche?

Vielen Dank im Voraus für Ihre Erkenntnisse.

Answer 1

Verwenden htonl/ntohl zwischen Netzwerk (big-endian) Bytereihenfolge und nativen Bytereihenfolge zu kippen:

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

Effektiv dies den Pufferinhalt als Integer in Big-Endian-lädt Ordnung, führt die Verschiebung durch und schreibt sie dann in Big-Endian-Reihenfolge zurück.

Dies kompiliert in ein paar bswap Anweisungen auf x86, so sollte es einigermaßen effizient sein (gcc -O3).

---

Hier einige Testcode (buffer global konstant Faltung zu vermeiden, und die return verhindert dead-Code Elimination):

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

Die folgenden recht einfachen Maschinencode kompiliert in (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 $0x4, %eax  ; shift 
000000000000000f bswapl %eax   ; endian flip 
0000000000000011 movl %eax, (%rip) ; save buffer 
0000000000000017 popq %rbp   ; finish 
0000000000000018 retq 

Answer 2

Nur zum Vergleich, können Sie dies tun, ohne die Verwendung von htonl/ntohl. Dies setzt voraus, ein Little-Endian-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); 
} 

und die erzeugte Baugruppe mit gcc -O3:

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

Je nachdem, wie viele Zyklen bswapl ist, ist es wahrscheinlich die schnellere Alternative.