Cómo pasar un array de bytes por 12-bits

Question

Quiero cambiar el contenido de un array de bytes por 12 bits a la izquierda.

Por ejemplo, a partir de esta matriz de tipo uint8_t shift[10]:

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

Me gustaría cambiar a la izquierda, por 12-bits, resultando en:

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

Answer 1

Bravo por los punteros!

Este código funciona mirando hacia delante 12 bits de cada byte y copiar el correcto bits adelante.12 bits es la mitad inferior (nybble) de la siguiente byte y la mitad superior de 2 bytes de distancia.

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 escribió:
@Mike, su solución funciona, pero no lleva.

Bueno, yo diría que una jornada laboral normal de operación no sólo que (desbordamiento de llamada), y sólo permite que los bits adicionales se caen de la derecha o la izquierda.Es lo suficientemente simple como para llevar si quería - guardar sólo el 12 bits antes de empezar a cambiar.Tal vez usted quiere una circular en cambio, para poner el desbordó bits de espalda en la parte inferior?Tal vez usted quiere realloc la matriz y hacerla más grande?Devolver el desbordamiento de la persona que llama?Devolver un valor booleano si no-cero de los datos se ha desbordado?Tendrías que definir lo que significa llevar a usted.

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

Aquí está mi solución, pero aún más importante, mi enfoque para resolver el problema.

Me acerqué a el problema

• dibujo de la memoria de las células y el dibujo de las flechas desde el destino al origen.
• hizo una tabla que muestra el dibujo.
• el etiquetado de cada fila de la tabla con la relación de bytes de la dirección.

Esto me mostró el patrón:

• vamos iL ser la baja nybble (medio byte) de a[i]
• vamos iH el alto nybble de a[i]
• iH = (i+1)L
• iL = (i+2)H

Este patrón se mantiene para todos los bytes.

La traducción en C, esto significa:

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

Pasamos ahora a hacer tres observaciones:

• desde que llevar a cabo los trabajos de izquierda a derecha, no necesitamos para almacenar valores en variables temporales.
• vamos a tener un caso especial de la cola:todos 12 bits al final va a ser cero.
• debemos evitar la lectura de memoria no definida allá de la matriz.ya que no leer más a[i+2], esto solo afecta a los dos últimos bytes

Así, nos

• manejar el caso general, por el bucle para N-2 bytes y realizar el cálculo en general por encima de
• manejar el siguiente al último byte de configuración iH = (i+1)L
• manejar el último byte se establece en 0

dado a con una longitud de N, obtenemos:

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;

Y ahí lo tienen...la matriz está desplazado a la izquierda por 12 bits.Podría ser fácilmente generalizado a cambio de N bits, señalando que habrá M instrucciones de asignación, donde M = number of bits modulo 8, Creo.

El bucle podría ser más eficaz en algunas máquinas, mediante la traducción a los punteros

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

y mediante el entero más grande tipo de datos soportado por la CPU.

(Solo he escrito esto en, por lo que ahora sería un buen momento para que alguien revise el código, especialmente desde poco cambiando es muy fácil equivocarse.)

Answer 3

Permite hacer la mejor forma de cambio N bits en la matriz de 8 bits enteros.

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

Supongo que desde aquí usted tiene que encontrar la manera más óptima para hacer uso de esta información para mover alrededor de enteros en un array.Genérico algoritmos sería aplicar el pleno entero se mueve a partir de la derecha de la matriz y se mueve cada entero F los índices.Cero llenar la recién espacios vacíos.Entonces, finalmente, realizar una R desplazamiento de bits en todos los índices, empezando de nuevo desde la derecha.

En el caso de cambio de 0xBC por R los bits se puede calcular el desbordamiento haciendo un and bit a bit, y el cambio de uso de la bitshift operador:

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

Tenga en cuenta que los 4 bits es sólo una máscara simple:0x0F o simplemente 0b00001111.Esto es fácil de calcular, construir dinámicamente, o usted puede incluso utilizar una simple estática de la tabla de búsqueda.

Espero que sea lo suficientemente genérica.Yo no soy bueno con C/C++ por lo que, tal vez alguien pueda limpiar mi sintaxis o ser más específico.

Bono:Si eres astuto con su C usted podría ser capaz de fudge de varios índices de matriz en un solo 16, 32, o incluso de 64 bits enteros y realizar los cambios.Pero que es prabably no es muy portátil y me gustaría recomendar en contra de esto.Sólo una posible optimización.

Answer 4

Aquí una solución de trabajo, el uso de variables temporales:

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

Llamar a esta función 3 veces para una niña de 12 de desplazamiento de bits.

Mike solución quizás más rápido, debido a la utilización de variables temporales.

Answer 5

La versión de 32 bits...:-) Se encarga de la 1 <= contar <= 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

@José, observe que las variables son de 8 bits de ancho, mientras que el turno es de 12 bits de ancho.Su solución sólo funciona para N <= tamaño variable.

Si usted puede asumir que su matriz es un múltiplo de 4 se puede convertir la matriz en una matriz de uint64_t y, a continuación, trabajar en eso.Si no es un múltiplo de 4, se puede trabajar en 64 bits en trozos en tanto como usted puede y el trabajo en el resto, uno por uno.Esto puede ser un poco más código, pero creo que es más elegante en la final.

Answer 7

Hay un par de borde-los casos que hacen de este un puro problema:

• la matriz de entrada puede estar vacío
• el último y el penúltimo de los bits deben ser tratados de forma especial, porque tienen cero bits desplazado hacia ellos

He aquí una solución sencilla que se repite a lo largo de la matriz de la copia de la orden bajo nibble de la siguiente byte a su alto poder picar, y el orden alto nibble de la siguiente-siguiente (+2) byte en su orden bajo nibble.Para guardar eliminar el look-ahead puntero dos veces, mantiene una a dos elementos de búfer con el "último" y "siguiente" bytes:

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

Tenga en cuenta el límite de los casos, que activan sucesivamente más partes de la función:

• Cuando length es cero, tenemos la libertad bajo fianza a cabo sin tocar la memoria.
• Cuando length es uno de ellos, hemos establecido el único elemento a cero.
• Cuando length es de dos, se establece el orden alto nibble del primer byte de bajo orden de picar el segundo byte (es decir, los bits 12 a 16), y el segundo byte a cero.No podemos activar el bucle.
• Cuando length es mayor que dos de golpear el bucle, la mezcla de bytes a través de los dos elementos de búfer.

Si la eficiencia es el objetivo, la respuesta probablemente depende en gran medida de la máquina en la arquitectura.Normalmente, usted debe mantener los dos elementos de amortiguamiento, pero manejar una máquina palabra (32/64 bits entero sin signo) en un tiempo.Si usted está cambiando a una gran cantidad de datos que vale la pena el tratamiento de los primeros bytes como un caso especial de modo que usted puede conseguir su máquina de palabra punteros de la palabra-alineados.La mayoría de las CPUs de acceso a la memoria de manera más eficiente si los accesos caer en máquina de los límites de la palabra.Por supuesto, los bytes finales tienen que ser manejados especialmente demasiado para que no toque la memoria más allá del final de la matriz.