Come spostare un array di byte di 12 bit

StackOverflow https://stackoverflow.com/questions/29437

  •  09-06-2019
  •  | 
  •  

Domanda

Voglio spostare il contenuto di un array di byte di 12 bit a sinistra.

Ad esempio, iniziando con questo array di type uint8_t shift[10]:

{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0A, 0xBC}

Vorrei spostarlo a sinistra di 12 bit risultando in:

{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xAB, 0xC0, 0x00}
È stato utile?

Soluzione

Evviva le indicazioni!

Questo codice funziona guardando avanti di 12 bit per ciascun byte e copiando in avanti i bit corretti.12 bit sono la metà inferiore (nybble) del byte successivo e la metà superiore di 2 byte di distanza.

unsigned char length = 10;
unsigned char data[10] = {0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0A,0xBC};
unsigned char *shift = data;
while (shift < data+(length-2)) {
    *shift = (*(shift+1)&0x0F)<<4 | (*(shift+2)&0xF0)>>4;
    shift++;
}
*(data+length-2) = (*(data+length-1)&0x0F)<<4;
*(data+length-1) = 0x00;

Giustino ha scritto:
@Mike, la tua soluzione funziona, ma non funziona.

Bene, direi che una normale operazione di spostamento fa proprio questo (chiamata overflow) e lascia semplicemente cadere i bit extra da destra o da sinistra.È abbastanza semplice da trasportare se lo desideri: salva semplicemente i 12 bit prima di iniziare a cambiare.Forse vuoi uno spostamento circolare, per rimettere in fondo i pezzi in eccesso?Forse vuoi riallocare l'array e ingrandirlo?Restituire l'overflow al chiamante?Restituisce un valore booleano se i dati diversi da zero sono stati traboccati?Dovresti definire cosa significa carry per te.

unsigned char overflow[2];
*overflow = (*data&0xF0)>>4;
*(overflow+1) = (*data&0x0F)<<4 | (*(data+1)&0xF0)>>4;
while (shift < data+(length-2)) {
    /* normal shifting */
}  
/* now would be the time to copy it back if you want to carry it somewhere */
*(data+length-2) = (*(data+length-1)&0x0F)<<4 | (*(overflow)&0x0F);
*(data+length-1) = *(overflow+1);  

/* You could return a 16-bit carry int, 
 * but endian-ness makes that look weird 
 * if you care about the physical layout */
unsigned short carry = *(overflow+1)<<8 | *overflow;

Altri suggerimenti

Ecco la mia soluzione, ma ancora più importante il mio approccio per risolvere il problema.

Ho affrontato il problema tramite

  • disegnando le celle di memoria e disegnando le frecce dalla destinazione alla sorgente.
  • ho realizzato una tabella che mostra il disegno sopra.
  • etichettando ogni riga della tabella con il relativo indirizzo in byte.

Questo mi ha mostrato lo schema:

  • permettere iL essere il nybble basso (mezzo byte) di a[i]
  • permettere iH essere l'alto boccone di a[i]
  • iH = (i+1)L
  • iL = (i+2)H

Questo modello vale per tutti i byte.

Traducendo in C, questo significa:

a[i] = (iH << 4) OR iL
a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4)

Facciamo ora altre tre osservazioni:

  • poiché eseguiamo le assegnazioni da sinistra a destra, non abbiamo bisogno di memorizzare alcun valore in variabili temporanee.
  • avremo un caso speciale per la coda:Tutto 12 bits alla fine sarà zero.
  • dobbiamo evitare di leggere memoria non definita oltre l'array.dal momento che non leggiamo mai più di a[i+2], ciò influisce solo sugli ultimi due byte

Quindi, noi

  • gestire il caso generale eseguendo il loop for N-2 bytes ed eseguendo il calcolo generale sopra
  • gestire il penultimo byte impostandolo iH = (i+1)L
  • gestire l'ultimo byte impostandolo su 0

dato a con lunghezza N, noi abbiamo:

for (i = 0; i < N - 2; ++i) {
    a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4);
}
a[N-2] = (a[N-1) & 0x0f) << 4;
a[N-1] = 0;

E il gioco è fatto...l'array viene spostato a sinistra di 12 bits.Potrebbe essere facilmente generalizzato allo spostamento N bits, rilevando che ci sarà M dichiarazioni di assegnazione dove M = number of bits modulo 8, Credo.

Il ciclo potrebbe essere reso più efficiente su alcune macchine traducendolo in puntatori

for (p = a, p2=a+N-2; p != p2; ++p) {
    *p = ((*(p+1) & 0x0f) << 4) | (((*(p+2) & 0xf0) >> 4);
}

e utilizzando il tipo di dati intero più grande supportato dalla CPU.

(L'ho appena digitato, quindi ora sarebbe il momento giusto per qualcuno di rivedere il codice, soprattutto perché è notoriamente facile sbagliare un po'.)

Rendiamolo il modo migliore per cambiare N bit nell'array di numeri interi da 8 bit.

N            - Total number of bits to shift
F = (N / 8) - Full 8 bit integers shifted
R = (N % 8) - Remaining bits that need to be shifted

Immagino che da qui dovresti trovare il modo più ottimale per utilizzare questi dati per spostarti negli interi in un array.Gli algoritmi generici consisterebbero nell'applicare gli spostamenti interi completi iniziando dalla destra dell'array e spostando ciascun intero F indici.Zero riempie gli spazi appena vuoti.Quindi infine esegui un R bit shift su tutti gli indici, sempre a partire da destra.

In caso di spostamento 0xBC di R bit puoi calcolare l'overflow eseguendo un AND bit per bit e lo spostamento utilizzando l'operatore bitshift:

// 0xAB shifted 4 bits is:
(0xAB & 0x0F) >> 4   // is the overflow      (0x0A)
0xAB << 4            // is the shifted value (0xB0)

Tieni presente che i 4 bit sono solo una semplice maschera:0x0F o semplicemente 0b00001111.È facile da calcolare, creare dinamicamente oppure puoi anche utilizzare una semplice tabella di ricerca statica.

Spero che sia abbastanza generico.Non sono affatto bravo con C/C++, quindi forse qualcuno può ripulire la mia sintassi o essere più specifico.

Bonus:Se sei astuto con il tuo C potresti essere in grado di fondere più indici di array in un singolo intero a 16, 32 o anche 64 bit ed eseguire gli spostamenti.Ma probabilmente non è molto portabile e lo sconsiglio.Solo una possibile ottimizzazione.

Ecco una soluzione funzionante, utilizzando variabili temporanee:

void shift_4bits_left(uint8_t* array, uint16_t size)
{
    int i;
    uint8_t shifted = 0x00;    
    uint8_t overflow = (0xF0 & array[0]) >> 4;

    for (i = (size - 1); i >= 0; i--)
    {
        shifted = (array[i] << 4) | overflow;
        overflow = (0xF0 & array[i]) >> 4;
        array[i] = shifted;
    }
}

Chiama questa funzione 3 volte per uno spostamento di 12 bit.

La soluzione di Mike potrebbe essere più veloce, grazie all'uso di variabili temporanee.

La versione a 32 bit...:-) Gestisce 1 <= conteggio <= num_parole

#include <stdio.h>

unsigned int array[] = {0x12345678,0x9abcdef0,0x12345678,0x9abcdef0,0x66666666};

int main(void) {
  int count;
  unsigned int *from, *to;
  from = &array[0];
  to = &array[0];
  count = 5;

  while (count-- > 1) {
    *to++ = (*from<<12) | ((*++from>>20)&0xfff);
  };
  *to = (*from<<12);

  printf("%x\n", array[0]);
  printf("%x\n", array[1]);
  printf("%x\n", array[2]);
  printf("%x\n", array[3]);
  printf("%x\n", array[4]);

  return 0;
}

@Joseph, nota che le variabili sono larghe 8 bit, mentre lo spostamento è largo 12 bit.La tua soluzione funziona solo per N <= dimensione variabile.

Se puoi supporre che il tuo array sia un multiplo di 4, puoi eseguire il cast dell'array in un array di uint64_t e quindi lavorarci sopra.Se non è un multiplo di 4, puoi lavorare in blocchi a 64 bit quanto più puoi e lavorare sul resto uno per uno.Questo potrebbe richiedere un po' più di codifica, ma penso che alla fine sia più elegante.

Ci sono un paio di casi limite che rendono questo un problema interessante:

  • l'array di input potrebbe essere vuoto
  • l'ultimo e il penultimo bit devono essere trattati in modo speciale, perché al loro interno sono spostati zero bit

Ecco una soluzione semplice che esegue il loop sull'array copiando il nibble di ordine basso del byte successivo nel suo nibble di ordine superiore e il nibble di ordine superiore del byte successivo (+2) nel suo nibble di ordine basso.Per evitare di dereferenziare due volte il puntatore look-ahead, mantiene un buffer a due elementi con i byte "ultimo" e "successivo": 

void shl12(uint8_t *v, size_t length) {
  if (length == 0) {
    return; // nothing to do
  }

  if (length > 1) {
    uint8_t last_byte, next_byte;
    next_byte = *(v + 1);

    for (size_t i = 0; i + 2 < length; i++, v++) {
      last_byte = next_byte;
      next_byte = *(v + 2);
      *v = ((last_byte & 0x0f) << 4) | (((next_byte) & 0xf0) >> 4);
    }

    // the next-to-last byte is half-empty
    *(v++) = (next_byte & 0x0f) << 4;
  }

  // the last byte is always empty
  *v = 0;
}

Consideriamo i casi limite, che attivano successivamente più parti della funzione:

  • Quando length è zero, tiriamo fuori dai guai senza toccare la memoria.
  • Quando length è uno, impostiamo l'unico elemento a zero.
  • Quando length è due, impostiamo il nibble di ordine superiore del primo byte sul nibble di ordine inferiore del secondo byte (ovvero i bit 12-16) e il secondo byte su zero.Non attiviamo il loop.
  • Quando length è maggiore di due entriamo nel ciclo, mescolando i byte attraverso il buffer a due elementi.

Se il tuo obiettivo è l'efficienza, la risposta probabilmente dipende in gran parte dall'architettura della tua macchina.In genere è necessario mantenere il buffer a due elementi, ma gestire una parola macchina (intero senza segno a 32/64 bit) alla volta.Se stai spostando molti dati, varrà la pena trattare i primi byte come un caso speciale in modo da poter allineare le parole ai puntatori delle parole della tua macchina.La maggior parte delle CPU accede alla memoria in modo più efficiente se gli accessi rientrano nei limiti delle parole macchina.Naturalmente, anche i byte finali devono essere gestiti in modo speciale in modo da non toccare la memoria oltre la fine dell'array.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top