Bit Striping w C

Question

Mam 3 bufory zawierające dane bitowe R, G, B działające na procesorze 32-bitowym.

Muszę połączyć trzy bajty w następujący sposób:

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

int32_t Out = 0b r1g1b1r2g2b2r3g3 b3r4g4b4r5g5b5r6 g6b6r7g7b7r8g8b8 xxxxxxxx 

gdzie xxxxxxxx kontynuuje się do każdego z kolejnych bajtów w buforach.

Szukam optymalnego sposobu na ich połączenie. Moje podejście zdecydowanie nie jest efektywne.

jest mój podejście

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

można stosować tablicę o rozmiarze 64, który zawiera wartości bitstripped przez 6 bitów, a następnie pobrać 2 bity każdy z R, G i B wykorzystać tabelę szybsze odnośnika. Korzystanie z wyszukiwania o rozmiarze 512 lub 4096 może być bardziej wydajne.

/* 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

Jeśli można oszczędzić 1024 bajtów, można osiągnąć pożądany rezultat z jednej tabeli przeglądowej 256-elementu:

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]; 

ta wykorzystuje tylko 3 wyszukiwań, 2 zmiany i 2 or operacji, które powinien zapewnić dopuszczalne przyspieszenie.

Jeśli masz więcej miejsca, można użyć trzy tabele wyszukiwania, aby wyeliminować zmiany zbyt (choć może to spowodować gorszą wydajność pamięci podręcznej, więc zawsze profil do sprawdzenia!)

Answer 3

Można użyć mnożenie przez " magiczna "stała do replikacji bitów. Następnie użyj bit-shifts, aby wyodrębnić potrzebne bity, i bitowe maskowanie, aby je połączyć. Stała "magiczna" jest 17-bitowym binarnym 10000000100000001. Po pomnożeniu przez nią, każda 8-bitowa liczba jest połączona z sobą 3 razy.

 
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 

Bity zaznaczone pogrubieniem są tymi, które znajdują się we właściwych miejscach.

Jeśli użyjesz tego kodu maskowania

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

dostaniesz „czerwony” bity połączone w odpowiedni sposób:

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

następnie połączyć „niebieski” i „zielonych” bity w podobny sposób.

---

Orientacyjna liczba operacji:

• mnożenia: 3
• Bit zmiany biegów: 9
• bitową I: 12
• bitową OR: 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; 

---

Innym sposobem jest

przeplatania z zastosowaniem magic number multiplication ten packing technique

Pozwala przypuszczać rByte zawiera 8 bitów numerach 12345678. Po rozbiciu na końcowy wynik, te fragmenty R będą wyglądały tak, myślniki są nietraktowanymi fragmentami.

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

Będziemy rozpowszechniać bity do 8 bajtów równomiernie przez

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

Teraz R zawiera bity w rByte jak

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

z myślnikami są zerami

---

Wyjaśnienie

........................................................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 

---

Aby przesunąć bity w r do swoich końcowych pozycjach będziemy podzielić r na 2 części i uzyskać bity w każdej części w ich właściwej pozycji. Pierwsza część przesunie bity 1, 4, 5 i 8 z magiczną liczbą 0x40001040001, a druga część przesunie pozostałe bity za pomocą magicznej liczby 0x01040001040. Te magiczne liczby można obliczyć w taki sam sposób jak powyżej. Być może wystarczy 32-bitowe mnożenie, ale tego nie sprawdziłem.

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

Bity dla G i B można obliczyć podobnie. Po, że wyniki mogą być po prostu połączone ze sobą

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