Comment décaler un tableau d'octets de 12 bits

Question

Je souhaite décaler le contenu d'un tableau d'octets de 12 bits vers la gauche.

Par exemple, en commençant par ce tableau de type uint8_t shift[10]:

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

Je voudrais le décaler vers la gauche de 12 bits, ce qui donne :

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

Answer 1

Vive les pointeurs !

Ce code fonctionne en anticipant 12 bits pour chaque octet et en copiant les bits appropriés vers l'avant.12 bits correspondent à la moitié inférieure (nybble) de l'octet suivant et à la moitié supérieure de 2 octets.

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 a écrit :
@Mike, votre solution fonctionne, mais ne fonctionne pas.

Eh bien, je dirais qu'une opération de décalage normale fait exactement cela (appelé débordement) et laisse simplement les bits supplémentaires tomber à droite ou à gauche.C'est assez simple à transporter si vous le souhaitez - sauvegardez simplement les 12 bits avant de commencer à décaler.Peut-être souhaitez-vous un décalage circulaire, pour remettre les morceaux débordés vers le bas ?Peut-être souhaitez-vous réaffecter le tableau et l'agrandir ?Rendre le débordement à l'appelant ?Renvoie un booléen si des données non nulles ont été débordées ?Vous devrez définir ce que le portage signifie pour vous.

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

Voici ma solution, mais plus important encore, mon approche pour résoudre le problème.

J'ai abordé le problème en

• dessiner les cellules mémoire et dessiner des flèches de la destination à la source.
• fait un tableau montrant le dessin ci-dessus.
• étiqueter chaque ligne du tableau avec l'adresse d'octet relative.

Cela m'a montré le modèle :

• laisser iL être le petit nybble (demi-octet) de a[i]
• laisser iH être le grand luxe de a[i]
• iH = (i+1)L
• iL = (i+2)H

Ce modèle est valable pour tous les octets.

Traduit en C, cela signifie :

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

Nous faisons maintenant trois autres observations :

• puisque nous effectuons les affectations de gauche à droite, nous n'avons pas besoin de stocker de valeurs dans des variables temporaires.
• nous aurons un cas particulier pour la queue :tous 12 bits à la fin sera zéro.
• nous devons éviter de lire la mémoire non définie au-delà du tableau.puisque nous n'avons jamais lu plus que a[i+2], cela n'affecte que les deux derniers octets

Alors on

• gérer le cas général en faisant une boucle pour N-2 bytes et effectuer le calcul général ci-dessus
• gérer l'avant-dernier octet en définissant iH = (i+1)L
• gérer le dernier octet en le définissant sur 0

donné a avec longueur N, on a:

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;

Et voila...le tableau est décalé vers la gauche de 12 bits.Cela pourrait facilement être généralisé au déplacement N bits, notant qu'il y aura M instructions d'affectation où M = number of bits modulo 8, Je crois.

La boucle pourrait être rendue plus efficace sur certaines machines en la traduisant en pointeurs

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

et en utilisant le plus grand type de données entier pris en charge par le processeur.

(Je viens de taper ceci, ce serait donc le bon moment pour que quelqu'un révise le code, d'autant plus qu'il est notoirement facile de se tromper.)

Answer 3

Faisons-en la meilleure façon de changer N bits dans le tableau d’entiers de 8 bits.

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

Je suppose qu'à partir de là, vous devrez trouver le moyen le plus optimal d'utiliser ces données pour déplacer les entiers dans un tableau.Les algorithmes génériques consisteraient à appliquer les décalages entiers complets en commençant par la droite du tableau et en déplaçant chaque entier F index.Zéro remplit les espaces nouvellement vides.Puis enfin effectuer un R décalage de bits sur tous les index, toujours en commençant par la droite.

En cas de déplacement 0xBC par R bits, vous pouvez calculer le débordement en faisant un ET au niveau du bit, et le décalage en utilisant l'opérateur bitshift :

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

Gardez à l’esprit que les 4 bits ne sont qu’un simple masque :0x0F ou simplement 0b00001111.Ceci est facile à calculer, à construire dynamiquement ou vous pouvez même utiliser une simple table de recherche statique.

J'espère que c'est assez générique.Je ne suis pas du tout doué avec C/C++, alors peut-être que quelqu'un pourra nettoyer ma syntaxe ou être plus précis.

Prime:Si vous êtes astucieux avec votre C, vous pourrez peut-être truquer plusieurs index de tableau en un seul entier de 16, 32 ou même 64 bits et effectuer les décalages.Mais ce n’est probablement pas très portable et je le déconseille.Juste une optimisation possible.

Answer 4

Voici une solution de travail, utilisant des variables temporaires :

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

Appelez cette fonction 3 fois pour un décalage de 12 bits.

La solution de Mike est peut-être plus rapide, grâce à l'utilisation de variables temporaires.

Answer 5

La version 32 bits...:-) Gère 1 <= nombre <= 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, notez que les variables ont une largeur de 8 bits, tandis que le décalage est de 12 bits.Votre solution ne fonctionne que pour N <= taille variable.

Si vous pouvez supposer que votre tableau est un multiple de 4, vous pouvez convertir le tableau en un tableau de uint64_t, puis travailler dessus.S'il ne s'agit pas d'un multiple de 4, vous pouvez travailler autant que possible en morceaux de 64 bits et travailler sur le reste un par un.C'est peut-être un peu plus de codage, mais je pense que c'est plus élégant au final.

Answer 7

Il existe quelques cas extrêmes qui en font un problème intéressant :

• le tableau d'entrée est peut-être vide
• le dernier et l'avant-dernier bits doivent être traités spécialement, car ils contiennent zéro bit décalé

Voici une solution simple qui boucle sur le tableau en copiant le quartet de poids faible de l'octet suivant dans son quartet de poids fort, et le quartet de poids fort de l'octet suivant (+2) dans son quartet de poids faible.Pour éviter de déréférencer le pointeur d'anticipation deux fois, il conserve un tampon à deux éléments avec les octets « dernier » et « suivant » :

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

Considérons les cas limites, qui activent successivement plusieurs parties de la fonction :

• Quand length est nul, on renfloue sans toucher à la mémoire.
• Quand length est un, nous mettons le seul et unique élément à zéro.
• Quand length est deux, nous définissons le quartet de poids fort du premier octet sur le quartet de poids faible du deuxième octet (c'est-à-dire les bits 12 à 16) et le deuxième octet sur zéro.Nous n'activons pas la boucle.
• Quand length est supérieur à deux, nous exécutons la boucle, mélangeant les octets dans le tampon à deux éléments.

Si l'efficacité est votre objectif, la réponse dépend probablement en grande partie de l'architecture de votre machine.En règle générale, vous devez conserver le tampon à deux éléments, mais gérer un mot machine (entier non signé de 32/64 bits) à la fois.Si vous déplacez beaucoup de données, il sera intéressant de traiter les premiers octets comme un cas particulier afin que vous puissiez aligner les pointeurs de mots de votre machine.La plupart des processeurs accèdent à la mémoire plus efficacement si les accès se situent dans les limites des mots machine.Bien sûr, les octets de fin doivent également être traités spécialement afin de ne pas toucher à la mémoire au-delà de la fin du tableau.