So verschieben Sie ein Byte-Array um 12 Bit

Question

Ich möchte den Inhalt eines Byte-Arrays um 12 Bit nach links verschieben.

Beginnen Sie beispielsweise mit diesem Array-Typ uint8_t shift[10]:

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

Ich würde es gerne um 12 Bit nach links verschieben, was zu Folgendem führt:

{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xAB, 0xC0, 0x00}

Answer 1

Hurra für Hinweise!

Dieser Code funktioniert, indem er für jedes Byte 12 Bits vorausschaut und die richtigen Bits nach vorne kopiert.12 Bits sind die untere Hälfte (Nybble) des nächsten Bytes und die obere Hälfte von 2 Bytes entfernt.

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;

Justin schrieb:
@Mike, deine Lösung funktioniert, funktioniert aber nicht.

Nun, ich würde sagen, eine normale Schiebeoperation macht genau das (Überlauf genannt) und lässt die zusätzlichen Bits einfach rechts oder links wegfallen.Es ist ganz einfach, es bei Bedarf mitzunehmen – speichern Sie einfach die 12 Bits, bevor Sie mit dem Verschieben beginnen.Vielleicht möchten Sie eine kreisförmige Verschiebung, um die übergelaufenen Bits wieder unten zu platzieren?Vielleicht möchten Sie das Array neu zuordnen und vergrößern?Den Überlauf an den Anrufer zurückgeben?Einen booleschen Wert zurückgeben, wenn Daten ungleich Null übergelaufen sind?Sie müssten definieren, was Tragen für Sie bedeutet.

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;

Answer 2

Hier ist meine Lösung, aber noch wichtiger ist mein Ansatz zur Lösung des Problems.

Ich bin an das Problem herangegangen

• Zeichnen der Speicherzellen und Zeichnen von Pfeilen vom Ziel zur Quelle.
• habe eine Tabelle erstellt, die die obige Zeichnung zeigt.
• Beschriften jeder Zeile in der Tabelle mit der relativen Byteadresse.

Das zeigte mir das Muster:

• lassen iL sei das niedrige Nybble (halbes Byte) von a[i]
• lassen iH Sei das hohe Knabberzeug von a[i]
• iH = (i+1)L
• iL = (i+2)H

Dieses Muster gilt für alle Bytes.

In C übersetzt bedeutet das:

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

Wir machen nun noch drei weitere Beobachtungen:

• Da wir die Zuweisungen von links nach rechts durchführen, müssen wir keine Werte in temporären Variablen speichern.
• Wir werden einen Sonderfall für den Schwanz haben:alle 12 bits am Ende wird Null sein.
• Wir müssen vermeiden, undefinierten Speicher über das Array hinaus zu lesen.da wir nie mehr gelesen haben als a[i+2], dies betrifft nur die letzten beiden Bytes

Also, wir

• Behandeln Sie den allgemeinen Fall durch eine Schleife für N-2 bytes und Durchführen der allgemeinen Berechnung oben
• Behandeln Sie das vorletzte Byte damit, indem Sie es festlegen iH = (i+1)L
• Behandeln Sie das letzte Byte, indem Sie es auf setzen 0

gegeben a mit Länge N, wir bekommen:

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;

Und da haben Sie es...Das Array wird um nach links verschoben 12 bits.Es könnte leicht auf das Verschieben verallgemeinert werden N bits, unter Hinweis darauf, dass dies der Fall sein wird M Zuweisungsanweisungen wo M = number of bits modulo 8, Ich glaube.

Die Schleife könnte auf einigen Maschinen durch die Übersetzung in Zeiger effizienter gestaltet werden

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

und durch Verwendung des größten von der CPU unterstützten ganzzahligen Datentyps.

(Ich habe das gerade erst eingegeben, also wäre jetzt ein guter Zeitpunkt für jemanden, den Code zu überprüfen, vor allem, weil es bekanntermaßen leicht ist, etwas falsch zu machen.)

Answer 3

Machen wir es zum besten Weg, um zu wechseln N Bits im Array von 8-Bit-Ganzzahlen.

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

Ich denke, von hier aus müssten Sie den optimalsten Weg finden, diese Daten zu nutzen, um Ints in einem Array zu verschieben.Generische Algorithmen würden die Verschiebungen der gesamten Ganzzahl anwenden, indem sie rechts im Array beginnen und jede Ganzzahl verschieben F Indizes.Null füllt die neu leeren Räume.Dann führen Sie endlich eine durch R Bitverschiebung auf allen Indizes, wiederum beginnend von rechts.

Im Falle einer Verschiebung 0xBC von R Bits können Sie den Überlauf berechnen, indem Sie ein bitweises UND und die Verschiebung mit dem Bitshift-Operator durchführen:

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

Bedenken Sie, dass es sich bei den 4 Bits nur um eine einfache Maske handelt:0x0F oder einfach 0b00001111.Dies lässt sich leicht berechnen, dynamisch erstellen oder Sie können sogar eine einfache statische Nachschlagetabelle verwenden.

Ich hoffe, das ist allgemein genug.Ich bin überhaupt nicht gut mit C/C++, also kann vielleicht jemand meine Syntax bereinigen oder genauer sein.

Bonus:Wenn Sie sich mit C auskennen, können Sie möglicherweise mehrere Array-Indizes in eine einzige 16-, 32- oder sogar 64-Bit-Ganzzahl umwandeln und die Verschiebungen durchführen.Aber das ist wahrscheinlich nicht sehr portabel und ich würde davon abraten.Nur eine mögliche Optimierung.

Answer 4

Hier eine funktionierende Lösung mit temporären Variablen:

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

Rufen Sie diese Funktion dreimal auf, um eine 12-Bit-Verschiebung durchzuführen.

Mikes Lösung ist aufgrund der Verwendung temporärer Variablen möglicherweise schneller.

Answer 5

Die 32-Bit-Version...:-) Behandelt 1 <= count <= num_words

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

Answer 6

@Joseph, beachten Sie, dass die Variablen 8 Bit breit sind, während die Verschiebung 12 Bit breit ist.Ihre Lösung funktioniert nur für N <= Variablengröße.

Wenn Sie davon ausgehen können, dass Ihr Array ein Vielfaches von 4 ist, können Sie das Array in ein Array von uint64_t umwandeln und dann daran arbeiten.Wenn es kein Vielfaches von 4 ist, können Sie so viel wie möglich in 64-Bit-Blöcken bearbeiten und den Rest nacheinander bearbeiten.Das ist vielleicht etwas mehr Codierung, aber ich denke, dass es am Ende eleganter ist.

Answer 7

Es gibt ein paar Randfälle, die dies zu einem netten Problem machen:

• Das Eingabearray ist möglicherweise leer
• Die letzten und vorletzten Bits müssen besonders behandelt werden, da in sie Nullbits verschoben werden

Hier ist eine einfache Lösung, die das Array durchläuft und dabei das niederwertige Halbbyte des nächsten Bytes in sein höherwertiges Halbbyte und das höherwertige Halbbyte des übernächsten (+2) Bytes in sein niederwertiges Halbbyte kopiert.Um die doppelte Dereferenzierung des Look-Ahead-Zeigers zu vermeiden, verwaltet es einen Puffer mit zwei Elementen mit dem „letzten“ und dem „nächsten“ Byte:

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

Betrachten Sie die Grenzfälle, die sukzessive mehr Teile der Funktion aktivieren:

• Wann length Null ist, steigen wir aus, ohne die Erinnerung zu berühren.
• Wann length eins ist, setzen wir das einzige Element auf Null.
• Wann length Ist zwei, setzen wir das höherwertige Halbbyte des ersten Bytes auf das niederwertige Halbbyte des zweiten Bytes (d. h. die Bits 12–16) und das zweite Byte auf Null.Wir aktivieren die Schleife nicht.
• Wann length größer als zwei ist, gelangen wir in die Schleife und mischen die Bytes über den Zwei-Elemente-Puffer.

Wenn Effizienz Ihr Ziel ist, hängt die Antwort wahrscheinlich weitgehend von der Architektur Ihrer Maschine ab.Normalerweise sollten Sie den Puffer mit zwei Elementen beibehalten, aber jeweils ein Maschinenwort (32/64-Bit-Ganzzahl ohne Vorzeichen) verarbeiten.Wenn Sie viele Daten verschieben, lohnt es sich, die ersten paar Bytes als Sonderfall zu behandeln, damit Sie die Wortzeiger Ihrer Maschine wortausrichten können.Die meisten CPUs greifen effizienter auf den Speicher zu, wenn die Zugriffe an Maschinenwortgrenzen liegen.Natürlich müssen auch die nachfolgenden Bytes speziell behandelt werden, damit Sie den Speicher nicht über das Ende des Arrays hinaus berühren.