Cómo cambiar una matriz de bytes por 12 bits

Question

Quiero desplazar el contenido de una matriz de bytes por 12 bits hacia 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 hacia la izquierda por 12-bits resultantes en:

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

Answer 1

¡Hurra para los indicadores!

Este código funciona mirando hacia adelante 12 bits para cada byte y copiando los bits adecuados hacia adelante. 12 bits es la mitad inferior (nybble) del 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 operación de cambio normal hace justamente eso (llamado desbordamiento), y deja que los bits adicionales caigan a la derecha o a la izquierda. Es lo suficientemente simple como para transportarlo si lo desea, solo guarde los 12 bits antes de comenzar a cambiar.¿Tal vez quieres un cambio circular para volver a colocar las partes desbordadas en la parte inferior? ¿Quizás quieras volver a colocar la matriz y agrandarla? Devuelve el desbordamiento a la persona que llama? ¿Devuelve un valor booleano si se desbordaron datos distintos de cero? Tendría que definir lo que significa para 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

deja para hacer que la La mejor manera de cambiar los bits N en la matriz de enteros 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 

supongo que desde aquí se tendría que encontrar la manera más óptima para hacer uso de estos datos para moverse enteros en una matriz. Los algoritmos genéricos serían aplicar los cambios enteros completos comenzando desde la derecha de la matriz y moviendo cada entero F índices. Zero llena los espacios recién vacíos. Luego, finalmente realice un cambio de bit R en todos los índices, comenzando 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 mediante el operador BitShift:

// 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 un simple máscara: 0x0F o solo 0b00001111. Esto es fácil de calcular, construir dinámicamente, o incluso puede usar una tabla de búsqueda estática simple.

Espero que sea lo suficientemente genérico. No soy bueno con C/C++ en absoluto así que tal vez alguien puede limpiar mi sintaxis o ser más específico.

Bonificación: si eres hábil con tu C, puedes cambiar varios índices de matriz en un único entero de 16, 32 o incluso 64 bits y realizar los cambios. Pero eso es, desde luego, poco portátil y recomendaría no hacerlo. Solo una posible optimización.

Answer 3

@Joseph, observe que las variables tienen 8 bits de ancho, mientras que el cambio tiene 12 bits de ancho. Su solución funciona solo para N < = tamaño variable.

Si puede suponer que su matriz es un múltiplo de 4, puede convertir la matriz en una matriz de uint64_t y luego trabajar en eso. Si no es un múltiplo de 4, puede trabajar en fragmentos de 64 bits tanto como pueda y trabajar en el resto uno por uno. Esto puede ser un poco más de codificación, pero creo que es más elegante al final.

Answer 4

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

que abordó el problema por

• dibujar las celdas de memoria y dibujar flechas desde el destino al origen.
• hizo una tabla que muestra el dibujo de arriba.
• etiquetando cada fila en la tabla con la dirección de bytes relativa.

Esto me mostró el patrón:

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

Este patrón es válido para todos los bytes.

Traduciendo en C, esto significa:

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

Ahora hacer tres observaciones más:

• ya que llevamos a cabo las tareas de izquierda a derecha, que no necesitamos para almacenar cualquier valor en variables temporales
• tendremos un caso especial para la cola: todos 12 bits al final será cero.
• debemos evitar leer la memoria indefinida más allá de la matriz. ya que nunca leemos más de a[i+2], esto sólo afecta a los dos últimos bytes

Por lo tanto, nos

• manejamos el caso general de un bucle de N-2 bytes y realizar el cálculo general anterior
• manejar la siguiente al último byte por ella mediante el establecimiento de iH = (i+1)L
• mango del último byte estableciéndolo en 0

dado a con la longitud 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 se desplaza a la izquierda 12 bits. Se podría generalizar fácilmente al cambio N bits, teniendo en cuenta que habrá declaraciones de asignación M donde M = number of bits modulo 8, creo.

El bucle se podría hacer más eficiente 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 uso de la mayor tipo de datos entero apoyado por la CPU.

(I acaba de escribir esto en, por lo que ahora sería un buen momento para que alguien revise el código, sobre todo porque poco haciendo girar es notoriamente fácil equivocarse.)

Answer 5

La versión de 32 bits ... :-) Mangos 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

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 t Imes para un turno de 12 bits.

La solución de Mike es quizás más rápida, debido al uso de variables temporales.

Answer 7

Hay un par de bordes-casos que hacen de este un problema ordenada:

• la matriz de entrada puede estar vacía
• el último y penúltimo trozos deben ser tratados de manera especial, porque tienen cero bits desplazados en ellos

Aquí hay una solución simple que recorre el array de copiar el cuarteto de orden inferior de la siguiente byte a su cuarteto de orden superior, y el cuarteto de orden superior de la siguiente-siguiente (+2) byte en su mordisco de orden bajo. Para guardar dereferencing el puntero de preanálisis dos veces, se mantiene un buffer de dos elementos 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; 
} 

considerar los casos de borde, que activan sucesivamente más partes de la función:

• Cuando length es cero, rescatamos sin tocar la memoria.
• Cuando length es uno, establecemos el elemento único en cero.
• Cuando length es dos, establecemos el nibble de orden superior del primer byte en el nibble de orden inferior del segundo byte (es decir, los bits 12-16) y el segundo byte en cero. No activamos el bucle.
• Cuando length es mayor que dos, pulsamos el bucle, mezclando los bytes en el búfer de dos elementos.

Si la eficiencia es su objetivo, la respuesta probablemente dependa en gran medida de la arquitectura de su máquina. Normalmente, debe mantener el búfer de dos elementos, pero manejar una palabra de máquina (entero sin signo de 32/64 bits) a la vez. Si está transfiriendo una gran cantidad de datos, valdrá la pena tratar los primeros bytes como un caso especial para que pueda obtener los punteros de palabra de la máquina alineados a las palabras. La mayoría de las CPU acceden a la memoria de manera más eficiente si los accesos caen en límites de palabras de la máquina. Por supuesto, los bytes finales deben manejarse especialmente para que no toque la memoria más allá del final de la matriz.