Trasforma un grosso frammento di memoria all'indietro, veloce

Question

Ho bisogno di riscrivere circa 4KB di dati in ordine inverso, a livello di bit (l'ultimo bit dell'ultimo byte diventa il primo bit del primo byte), il più velocemente possibile. Ci sono qualche sniplet intelligente per farlo?

Razionale: i dati sono contenuti del display LCD in un dispositivo incorporato che di solito è posizionato in modo che lo schermo si trovi a livello delle spalle. Lo schermo ha l'orientamento "a ore 6", che deve essere visualizzato dal basso, come se fosse disteso o appeso sopra il livello degli occhi. Questo è risolvibile ruotando lo schermo di 180 gradi, ma poi ho bisogno di invertire i dati dello schermo (generati dalla libreria), che è 1 bit = 1 pixel, a partire dalla parte superiore sinistra dello schermo. La CPU non è molto potente, e il dispositivo ha già abbastanza lavoro, più numerosi frame al secondo sarebbero desiderabili, quindi le prestazioni sono un problema; RAM non così tanto.

modifica: Single core, serie ARM 9. 64 MB, (da ridimensionare a 32 MB in seguito), Linux. I dati vengono trasferiti dalla memoria di sistema al driver LCD su una porta IO a 8 bit.

La CPU è a 32 bit e funziona molto meglio con questa dimensione di parola che a livello di byte.

Answer 1

C'è un modo classico di fare questo. Supponiamo che unsigned int sia la tua parola a 32 bit. Sto utilizzando C99 perché la parola chiave restrict consente al compilatore di eseguire ulteriori ottimizzazioni in questo codice critico per la velocità che altrimenti non sarebbe disponibile. Queste parole chiave informano il compilatore che "src" e "dest" non si sovrappongono. Questo presuppone anche che stai copiando un numero intero di parole, se non lo sei, allora questo è solo un inizio.

Inoltre non so quali bit di spostamento/primitive di rotazione siano veloci sull'ARM e che siano lenti. Questo è qualcosa da considerare. Se hai bisogno di più velocità, considera di smontare l'output dal compilatore C e di andare da lì. Se si utilizza GCC, provare O2, O3 e Os per vedere quale è il più veloce. Potresti ridurre le bancarelle nella pipeline facendo due parole contemporaneamente.

Questo utilizza 23 operazioni per parola, senza contare il caricamento e l'archiviazione. Tuttavia, queste 23 operazioni sono tutte molto veloci e nessuna di esse accede alla memoria. Non so se una tabella di ricerca sarebbe più veloce o meno.

void 
copy_rev(unsigned int *restrict dest, 
     unsigned int const *restrict src, 
     unsigned int n) 
{ 
    unsigned int i, x; 
    for (i = 0; i < n; ++i) { 
     x = src[i]; 
     x = (x >> 16) | (x << 16); 
     x = ((x >> 8) & 0x00ff00ffU) | ((x & 0x00ff00ffU) << 8); 
     x = ((x >> 4) & 0x0f0f0f0fU) | ((x & 0x0f0f0f0fU) << 4); 
     x = ((x >> 2) & 0x33333333U) | ((x & 0x33333333U) << 2); 
     x = ((x >> 1) & 0x55555555U) | ((x & 0x555555555) << 1); 
     dest[n-1-i] = x; 
    } 
} 

Questa pagina è un grande riferimento: http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

Nota finale: Guardando il riferimento gruppo del braccio, c'è un codice operativo "REV", che inverte l'ordine dei byte in una parola. Questo dovrebbe radere 7 operazioni per loop dal codice precedente.

Answer 2

Passare attraverso la metà dell'array, convertire e scambiare byte.

for(int i = 0; i < arraySize/2; i++) { 
    char inverted1 = invert(array[i]); 
    char inverted2 = invert(array[arraySize - i - 1]); 
    array[i] = inverted2; 
    array[arraySize - i - 1] = inverted1; 
} 

Per conversione utilizzare una tabella precalcolata - una matrice di 2 ^CHAR_BIT (CHAR_BIT sarà probabilmente 8) elementi dove in posizione "I" del risultato per byte con valore "I" inversione viene memorizzato. Questo sarà molto veloce - un passaggio - e consumerà solo 2 ^CHAR_BIT per il tavolo.

Answer 3

Il sito Bit Twiddling Hacks è un buon punto di partenza per questo tipo di problemi. Dai uno sguardo allo here per l'inversione rapida dei bit. Quindi spetta a te applicarlo a ogni byte/parola del tuo blocco di memoria.

EDIT:

Ispirato da Dietrich Epps risposta e guardando la ARM instruction set, c'è un codice operativo RBIT che inverte i bit contenuti in un registro. Pertanto, se le prestazioni sono critiche, potresti prendere in considerazione l'utilizzo di un codice assembly.

Answer 4

Single Core?

Quanta memoria?

Il display è memorizzato in memoria e inviato al dispositivo o è l'unica copia dei pixel nella memoria dello schermo?

Answer 5

Il modo più veloce sarebbe probabilmente di memorizzare il contrario di tutti i possibili valori di byte in una tabella di ricerca. La tabella richiederebbe solo 256 byte.

Answer 6

Per invertire un singolo byte x è possibile gestire i bit uno alla volta:

unsigned char a = 0; 
for (i = 0; i < 8; ++i) { 
    a += (unsigned char)(((x >> i) & 1) << (7 - i)); 
} 

È possibile creare una cache di questi risultati in una matrice in modo che si può invertire rapidamente un byte solo facendo un ricerca singola invece di loop.

Quindi è sufficiente invertire la matrice di byte e quando si scrivono i dati si applica la mappatura di cui sopra. L'inversione di un array di byte è un problema ben documentato, ad es. here.

Answer 7

Creare una tabella di ricerca di 256 elementi di valori di byte che sono stati invertiti con bit dal loro indice.

{0x00, 0x80, 0x40, 0xc0, etc}

Poi scorrere la vostra copia array utilizzando ogni byte come indice nella tabella di ricerca.

Se si sta scrivendo linguaggio assembly, il set di istruzioni x86 ha un'istruzione XLAT che esegue solo questo tipo di ricerca. Anche se potrebbe non essere più veloce del codice C sui processori moderni.

È possibile eseguire questa operazione se si itera da entrambe le estremità verso il centro. A causa degli effetti della cache, potresti scoprire che è più rapido lo scambio in blocchi da 16 byte (presupponendo una linea cache da 16 byte).

Ecco il codice di base (esclusa l'ottimizzazione linea di cache)

// bit reversing lookup table 
typedef unsigned char BYTE; 
extern const BYTE g_RevBits[256]; 

void ReverseBitsInPlace(BYTE * pb, int cb) 
{ 
    int iter = cb/2; 
    for (int ii = 0, jj = cb-1; ii < iter; ++ii, --jj) 
    { 
     BYTE b1 = g_RevBits[pb[ii]]; 
     pb[ii] = g_RevBits[pb[jj]]; 
     pb[jj] = b1; 
    } 

    if (cb & 1) // if the number of bytes was odd, swap the middle one in place 
    { 
     pb[cb/2] = g_RevBits[pb[cb/2]]; 
    } 
} 

// initialize the bit reversing lookup table using macros to make it less typing. 
#define BITLINE(n) \ 
    0x0##n, 0x8##n, 0x4##n, 0xC##n, 0x2##n, 0xA##n, 0x6##n, 0xE##n,\ 
    0x1##n, 0x9##n, 0x5##n, 0xD##n, 0x3##n, 0xB##n, 0x7##n, 0xF##n, 

const BYTE g_RevBits[256] = { 
    BITLINE(0), BITLINE(8), BITLINE(4), BITLINE(C), 
    BITLINE(2), BITLINE(A), BITLINE(6), BITLINE(E), 
    BITLINE(1), BITLINE(9), BITLINE(5), BITLINE(D), 
    BITLINE(3), BITLINE(B), BITLINE(7), BITLINE(F), 
    }; 

Answer 8

Sembra che questo codice è di circa 50 orologi per bit di swap sul mio i7 XPS 8500 della macchina. 7,6 secondi per un milione di lanci di schiera. Filettato singolo. Stampa alcune opere ASCI basate su pattern di 1 e 0. Ho ruotato la foto a sinistra di 180 gradi dopo aver invertito l'array di bit, utilizzando un editor grafico, e sembrano identici a me. Un'immagine a doppia inversione è la stessa dell'originale.

Per quanto riguarda i vantaggi, è una soluzione completa. Scambia i bit dalla parte posteriore di un array di bit alla parte anteriore, operando su interi/byte e quindi scambiando ints/byte in una matrice.

Inoltre, questa è una libreria di bit generica, quindi potrebbe essere utile in futuro per risolvere altri problemi più banali.

È veloce come la risposta accettata? Penso che sia vicino, ma senza un codice funzionante per il benchmark è impossibile dirlo. Sentiti libero di tagliare e incollare questo programma di lavoro.

// Reverse BitsInBuff.cpp : Defines the entry point for the console application. 
#include "stdafx.h" 
#include "time.h" 
#include "memory.h" 
// 
// Manifest constants 
#define uchar unsigned char 
#define BUFF_BYTES 510 //400 supports a display of 80x40 bits 
#define DW 80 // Display Width 
// ---------------------------------------------------------------------------- 
uchar mask_set[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 }; 
uchar mask_clr[] = { 0xfe, 0xfd, 0xfb, 0xf7, 0xef, 0xdf, 0xbf, 0x7f }; 
// 
// Function Prototypes 
static void PrintIntBits(long x, int bits); 
void BitSet(uchar * BitArray, unsigned long BitNumber); 
void BitClr(uchar * BitArray, unsigned long BitNumber); 
void BitTog(uchar * BitArray, unsigned long BitNumber); 
uchar BitGet(uchar * BitArray, unsigned long BitNumber); 
void BitPut(uchar * BitArray, unsigned long BitNumber, uchar value); 
// 
uchar *ReverseBitsInArray(uchar *Buff, int BitKnt); 
static void PrintIntBits(long x, int bits); 
// ----------------------------------------------------------------------------- 
// Reverse the bit ordering in an array 
uchar *ReverseBitsInArray(uchar *Buff, int BitKnt) { 
    unsigned long front=0, back = BitKnt-1; 
    uchar temp; 
    while(front<back) { 
     temp = BitGet(Buff, front);     // copy front bit to temp before overwriting 
     BitPut(Buff, front, BitGet(Buff, back)); // copy back bit to front bit 
     BitPut(Buff, back, temp);     // copy saved value of front in temp to back of bit arra) 
     front++; 
     back--; 
    } 
    return Buff; 
} 
// --------------------------------------------------------------------------- 
// --------------------------------------------------------------------------- 
int _tmain(int argc, _TCHAR* argv[]) { 
    int i, j, k, LoopKnt = 1000001; 
    time_t start; 
    uchar Buff[BUFF_BYTES]; 
    memset(Buff, 0, sizeof(Buff)); 
    // make an ASCII art picture 
    for(i=0, k=0; i<(sizeof(Buff)*8)/DW; i++) { 
     for(j=0; j<DW/2; j++) { 
      BitSet(Buff, (i*DW)+j+k); 
     } 
     k++; 
    } 
    // print ASCII art picture 
    for(i=0; i<sizeof(Buff); i++) { 
     if(!(i % 10)) printf("\n"); // print bits in blocks of 80 
     PrintIntBits(Buff[i], 8); 
    } 
    i=LoopKnt; 
    start = clock(); 
    while(i--) { 
     ReverseBitsInArray((uchar *)Buff, BUFF_BYTES * 8); 
    } 
    // print ASCII art pic flipped upside-down and rotated left 
    printf("\nMilliseconds elapsed = %d", clock() - start); 
    for(i=0; i<sizeof(Buff); i++) { 
     if(!(i % 10)) printf("\n"); // print bits in blocks of 80 
     PrintIntBits(Buff[i], 8); 
    } 
    printf("\n\nBenchmark time for %d loops\n", LoopKnt); 
    getchar(); 
    return 0; 
} 
// ----------------------------------------------------------------------------- 
// Scaffolding... 
static void PrintIntBits(long x, int bits) { 
    unsigned long long z=1; 
    int i=0; 
    z = z << (bits-1); 
    for (; z > 0; z >>= 1) { 
     printf("%s", ((x & z) == z) ? "#" : "."); 
    } 
} 
// These routines do bit manipulations on a bit array of unsigned chars 
// --------------------------------------------------------------------------- 
void BitSet(uchar *buff, unsigned long BitNumber) { 
    buff[BitNumber >> 3] |= mask_set[BitNumber & 7]; 
} 
// ---------------------------------------------------------------------------- 
void BitClr(uchar *buff, unsigned long BitNumber) { 
    buff[BitNumber >> 3] &= mask_clr[BitNumber & 7]; 
} 
// ---------------------------------------------------------------------------- 
void BitTog(uchar *buff, unsigned long BitNumber) { 
    buff[BitNumber >> 3] ^= mask_set[BitNumber & 7]; 
} 
// ---------------------------------------------------------------------------- 
uchar BitGet(uchar *buff, unsigned long BitNumber) { 
    return (uchar) ((buff[BitNumber >> 3] >> (BitNumber & 7)) & 1); 
} 
// ---------------------------------------------------------------------------- 
void BitPut(uchar *buff, unsigned long BitNumber, uchar value) { 
    if(value) { // if the bit at buff[BitNumber] is true. 
     BitSet(buff, BitNumber); 
    } else { 
     BitClr(buff, BitNumber); 
    } 
} 

Di seguito è riportato l'elenco di codice per un'ottimizzazione utilizzando un nuovo buffer, invece di scambiare byte in posizione. Dato che solo 2030: 4080 BitSet() s sono necessari a causa del test if(), e circa la metà di GetBit() e PutBits() vengono eliminati eliminando TEMP, sospetto che il tempo di accesso alla memoria sia un costo fisso elevato per questo tipo di operazioni, fornendo un limite difficile all'ottimizzazione.

Usando un approccio look-up, e CONDIZIONATAMENTE scambiando byte, anziché bit, riduce di un fattore 8 il numero di accessi alla memoria, e di test per un byte 0 ottiene ammortizzati su 8 bit, anziché 1.

Utilizzando questi due approcci, testare per vedere se l'intero char 8-bit è 0 prima di fare ANYTHING, inclusa la ricerca della tabella, e la scrittura, è probabile che sia l'approccio più veloce possibile, ma richiederebbe un extra di 512 byte per il nuovo array di bit di destinazione e 256 byte per la tabella di ricerca. Il rendimento della performance potrebbe essere piuttosto drammatico.

// ----------------------------------------------------------------------------- 
// Reverse the bit ordering in new array 
uchar *ReverseBitsInNewArray(uchar *Dst, const uchar *Src, const int BitKnt) { 
    int front=0, back = BitKnt-1; 
    memset(Dst, 0, BitKnt/BitsInByte); 

    while(front < back) { 
     if(BitGet(Src, back--)) { // memset() has already set all bits in Dst to 0, 
      BitSet(Dst, front);  // so only reset if Src bit is 1 
     } 
     front++; 
    } 
    return Dst; 

Answer 9

I dati viene spinto dalla memoria di sistema al driver LCD sopra IO porta 8 bit.

Dal momento che sarete scrivendo al display LCD un byte alla volta, penso che l'idea migliore è quella di eseguire l'inversione po 'a destra quando si inviano i dati al driver LCD piuttosto che come un pre separata passaggio. Qualcosa del genere dovrebbe essere più veloce rispetto a qualsiasi delle altre risposte:

void send_to_LCD(uint8_t* data, int len, bool rotate) { 
    if (rotate) 
    for (int i=len-1; i>=0; i--) 
     write(reverse(data[i])); 
    else 
    for (int i=0; i<len; i++) 
     write(data[i]); 
} 

Dove write() è la funzione che invia un byte al driver LCD e reverse() uno dei singolo byte metodi po 'inversione descritti nelle altre risposte .

Questo approccio evita la necessità di memorizzare due copie dei dati video nella ram ed evita anche il roundtrip di lettura-inversione-scrittura. Si noti inoltre che questa è l'implementazione più semplice: potrebbe essere banalmente adattata per caricare, ad esempio, 4 byte alla volta dalla memoria, se ciò dovesse produrre migliori prestazioni. Un compilatore di vettorizzazione intelligente potrebbe persino essere in grado di farlo per te.