Bit Striping in C

Question

Ich habe 3 Puffer mit R, G, B Bitdaten, die auf einem 32-Bit-Prozessor laufen.

Ich brauche die drei Bytes in der folgenden Art und Weise zu kombinieren:

R[0] = 0b r1r2r3r4r5r6r7r8 
G[0] = 0b g1g2g3g4g5g6g7g8 
B[0] = 0b b1b2b3b4b5b6b7b8 

int32_t Out = 0b r1g1b1r2g2b2r3g3 b3r4g4b4r5g5b5r6 g6b6r7g7b7r8g8b8 xxxxxxxx 

wo xxxxxxxx weiterhin in den Puffern zu jedem des nächsten Bytes auf.

Ich bin auf der Suche nach einer optimalen Möglichkeit, sie zu kombinieren. Mein Ansatz ist definitiv nicht effizient.

Hier ist mein Ansatz

static void rgbcombineline(uint8_t line) 
{ 
    uint32_t i, bit; 
    uint8_t bitMask, rByte, gByte, bByte; 
    uint32_t ByteExp, rgbByte; 
    uint8_t *strPtr = (uint8_t*)&ByteExp; 

    for (i = 0; i < (LCDpixelsCol/8); i++) 
    { 
     rByte = rDispbuff[line][i]; 
     gByte = gDispbuff[line][i]; 
     bByte = bDispbuff[line][i]; 

     bitMask = 0b00000001; 
     ByteExp = 0; 
     for(bit = 0; bit < 8; bit++) 
     { 
      rgbByte = 0; 
      rgbByte |= ((rByte & bitMask) >> bit) << 2; 
      rgbByte |= ((gByte & bitMask) >> bit) << 1; 
      rgbByte |= ((bByte & bitMask) >> bit); 
      ByteExp |= (rgbByte << 3*bit); 
      bitMask <<= 1; 
     } 
     TempLinebuff[((i*3)+0) +2] = *(strPtr + 2); 
     TempLinebuff[((i*3)+1) +2] = *(strPtr + 1); 
     TempLinebuff[((i*3)+2) +2] = *(strPtr + 0); 
    } 
} 

Answer 1

Sie eine Tabelle der Größe verwenden können 64, die bitstripped Werte für 6-Bit enthält, und dann 2 Bits holen jeweils von r, g und b und Tabelle für eine schnellere Lookup verwenden. Die Verwendung von Lookup der Größe 512 oder 4096 kann effizienter sein.

/* Converts bits abcdefghijkl to adgjbehkcfil */ 
static const uint32_t bitStripLookUp[4096] = { 
    /* Hard coded values, can be generate with some script */ 
    ... 
}; 

... 

rByte = rDispbuff[line][i]; // rByte, gByte, bByte should be unit32 
gByte = gDispbuff[line][i]; 
bByte = bDispbuff[line][i]; 

uMSB = ((rByte << 4) & 0x0F00) | (gByte & 0x00F0) | ((bByte >> 4) & 0x000F); // r7r6r5r4g7g6g5g4b7b6b5b4 
uLSB = ((rByte << 8) & 0x0F00) | ((gByte << 4) & 0x00F0) | (bByte & 0x000F); // r3r2r1r0g3g2g1g0b3b2b1b0 
stuffed_value = (bitStripLookUp[uMSB] << 12) | bitStripLookUp[uLSB]; 

Answer 2

Wenn Sie 1024 Bytes erübrigen können, können Sie das gewünschte Ergebnis mit einer einzigen 256-Element-Lookup-Tabelle erreichen:

uint32_t lookup[256] = { 
    0, 1, 8, 9, 64, 65, ... 
    /* map abcdefgh to a00b00c00d00e00f00g00h */ 
}; 

uint32_t result = (lookup[rByte] << 2) | (lookup[gByte] << 1) | lookup[bByte]; 

Dies nutzt nur 3-Lookups, 2 Schichten und 2 or Operationen, die sollte eine akzeptable Beschleunigung bieten.

Wenn Sie mehr Platz haben, können Sie drei Lookup-Tabellen verwenden, um die Schichten zu beseitigen (obwohl dies in schlechter Cache-Leistung führen kann, also immer überprüfen Profil!)

Answer 3

Sie können durch eine Multiplikation verwenden ein " magische "Konstante, um die Bits zu replizieren. Verwenden Sie dann Bit-Shifts, um die benötigten Bits zu extrahieren, und bitweise Maskierung, um sie zu kombinieren. Die "magische" Konstante ist eine 17-Bit-Binärzahl 10000000100000001. Wenn sie damit multipliziert wird, wird jede 8-Bit-Zahl 3-mal mit sich selbst verkettet.

 
r1r2r3r4r5r6r7r8 * M  = r1r2r3r4r5r6r7r8r1r2r3r4r5r6r7r8r1r2r3r4r5r6r7r8 
r1r2r3r4r5r6r7r8 * M shr 2 = 0 0 r1r2r3r4r5r6r7r8r1r2r3r4r5r6r7r8r1r2r3r4r5r6 
r1r2r3r4r5r6r7r8 * M shr 4 = 0 0 0 0 r1r2r3r4r5r6r7r8r1r2r3r4r5r6r7r8r1r2r3r4 
r1r2r3r4r5r6r7r8 * M shr 6 = 0 0 0 0 0 0 r1r2r3r4r5r6r7r8r1r2r3r4r5r6r7r8r1r2 

Die fett markierten Bits sind diejenigen, die an den richtigen Stellen sind.

Wenn Sie diese Maskierung Code

R * M  & 0b100000000000100000000000 | 
(R * M >> 2) & 0b000100000000000100000000 | 
(R * M >> 4) & 0b000000100000000000100000 | 
(R * M >> 6) & 0b000000000100000000000100 

Sie werden die "roten" Bits in der richtigen Weise kombiniert erhalten:

r1 0 0 r2 0 0 r3 0 0 r4 0 0 r5 0 0 r6 0 0 r7 0 0 r8 0 0 

Dann verbinden die "blauen" und "grünen" Bits in ein ähnlicher Weg.

---

Eine grobe Schätzung der Anzahl der Operationen:

• Multiplikationen: 3
• Bitverschiebungen: 9
• bitweises UND: 12
• bitweises ODER: 11

Answer 4

Interleaving with bitwise operators

inline int interleave(int n) 
{ 
    n = ((n << 18) | (n << 9) | n) & 0007007007; // 000000111 000000111 000000111 
    n = ((n << 6) | (n << 3) | n) & 0444444444; // 100100100 100100100 100100100 
    return n; 
} 

r = interleave(r); 
g = interleave(g); 
b = interleave(b); 

rgb = r | (g >> 1) | (b >> 2); 

TempLinebuff[((i*3)+0) +2] = (rgb >> 16) & 0xFF; 
TempLinebuff[((i*3)+1) +2] = (rgb >> 8) & 0xFF; 
TempLinebuff[((i*3)+2) +2] = rgb  & 0xFF; 

---

Ein anderer Weg ist

Verwendung magic number multiplication Verschachteln mit diesem packing technique

Nehmen wir an rByte hat 8 Bits 12345678 numeriert. Nach dem Striping in das Endergebnis werden diese R-Bits wie folgt aussehen, Bindestriche sind Nicht-Care-Bits.

1--2--3--4--5--6--7--8------------------------------------------ 

Wir werden die Bits in 8 Bytes gleichmäßig durch

unsigned long long r = (rByte * 0x0101010101010101ULL) * 0x8040201008040201ULL; 

Jetzt verteilen r enthält, die Bits in rbyte als

1--------2--------3--------4--------5--------6--------7--------8 

mit Bindestrichen sind alle Nullen

---

Erläuterung

........................................................12345678 (rByte) 
x ..............1......1......1......1......1......1......1......1 (Magic number, dots are 0s) 
__________________________________________________________________ 
    ........................................................12345678 
    ................................................12345678.......↓ 
    ........................................12345678......↓........↓ 
    ................................12345678.....↓........↓........↓ 
+ ........................12345678....↓........↓........↓........↓ 
    ................12345678...↓........↓........↓........↓........↓ 
    ........12345678..↓........↓........↓........↓........↓........↓ 
    12345678.↓........↓........↓........↓........↓........↓........↓ 
__________________________________________________________________  
= 1........2........3........4........5........6........7........8 

---

Um die Bits in r an ihren endgültigen Positionen bewegen wir r in 2 Teile geteilt und die Bits in jedem Teil in die richtige Position zu bekommen. Der erste Teil wird die Bits 1, 4, 5 und 8 mit der magischen Nummer 0x40001040001 verschieben und der zweite Teil wird die verbleibenden Bits mit der magischen Nummer 0x01040001040 verschieben. Diese magischen Zahlen können auf die gleiche Weise wie oben berechnet werden. Vielleicht ist die 32-Bit-Multiplikation dafür ausreichend, aber ich habe das nicht überprüft.

#define RBIT(n)  (1ULL << (8-n)*9) 
#define RMASK_1458 (RBIT(1) | RBIT(4) | RBIT(5) | RBIT(8)) 
#define RMASK_2367 (RBIT(2) | RBIT(3) | RBIT(6) | RBIT(7)) 

#define BIT(n)  ((1ULL << 63) >> ((n-1)*3)) 
#define MASK_BIT1458 (BIT(1) | BIT(4) | BIT(5) | BIT(8)) 
#define MASK_BIT2367 (BIT(2) | BIT(3) | BIT(6) | BIT(7)) 

#define MAGIC_1458 0x40001040001ULL 
#define MAGIC_2367 0x01040001040ULL 

uint64_t resultR = (((r & RMASK_1458) * MAGIC_1458) & MASK_BIT1458) 
       | (((r & RMASK_2367) * MAGIC_2367) & MASK_BIT2367); 

Die Bits für G und B können ähnlich berechnet werden. Danach werden die Ergebnisse nur zusammen

kombiniert werden können

result = (resultR >> 32) | (resultG >> 33) | (resultB >> 34);