puede - Cómo cambiar una matriz de bytes por 12 bits

manual de programacion android pdf

Question

Quiero cambiar el contenido de una matriz de bytes por 12 bits a la izquierda.

Por ejemplo, comenzando con esta matriz de tipo uint8_t shift[10] :

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

Me gustaría desplazarlo a la izquierda en 12 bits lo que da como resultado:

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

Answer 1

¡Hurra por los indicadores!

Este código funciona mirando hacia adelante 12 bits para cada byte y copiando los bits apropiados 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, tu solución funciona, pero no funciona.

Bueno, yo diría que una operación de cambio normal hace precisamente eso (llamado desbordamiento), y simplemente permite 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

@Joseph, observe que las variables tienen 8 bits de ancho, mientras que el cambio tiene 12 bits de ancho. Su solución solo funciona 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 3

Aquí una solución de trabajo, utilizando 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;
    }
}

Llame a esta función 3 veces para un cambio de 12 bits.

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

Answer 4

Hay un par de casos extremos que hacen que este sea un problema claro:

• la matriz de entrada puede estar vacía
• los últimos y penúltimos bits deben tratarse especialmente, porque tienen cero bits desplazados en ellos

Aquí hay una solución simple que recorre la matriz copiando el nibble de bajo orden del siguiente byte en su nibble de alto orden, y el nibble de alto orden del byte siguiente (+2) en su nibble de bajo orden. Para guardar la eliminación de referencias al puntero de búsqueda anticipada dos veces, mantiene un búfer de dos elementos con los bytes "último" y "siguiente":

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

Considere los casos límite, que activan sucesivamente más partes de la función:

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

Si su objetivo es la eficiencia, 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.

Answer 5

Vamos a hacer que sea la mejor manera de desplazar N bits 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í tendrías que encontrar la forma más óptima de utilizar estos datos para moverte 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 desplazamiento de bit R en todos los índices, comenzando de nuevo desde la derecha.

En el caso de cambiar 0xBC por R bits, puede calcular el desbordamiento haciendo un AND a nivel de bit, y el cambio usando el operador de cambio de bits:

// 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 son solo una máscara simple: 0x0F o simplemente 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 astuto con tu C, puedes mezclar 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 6

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

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

Abordé el problema

• dibujando las celdas de memoria y dibujando flechas desde el destino hasta la fuente.
• hizo una tabla que muestra el dibujo de arriba.
• etiquetar cada fila en la tabla con la dirección de bytes relativa.

Esto me mostró el patrón:

• deja que iL sea ​​el nybble bajo (medio byte) de a[i]
• deja que sea el alto nybble de a[i]
• iH = (i+1)L
• iL = (i+2)H

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

Traducir a C, esto significa:

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

Ahora hacemos tres observaciones más:

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

Así que nosotros

• manejar el caso general haciendo un bucle para N-2 bytes y realizando el cálculo general anterior
• manejar el penúltimo byte estableciendo iH = (i+1)L
• manejar el último byte al configurarlo en 0

dado a con a 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 en 12 bits . Podría generalizarse fácilmente para desplazar N bits , teniendo en cuenta que habrá M instrucciones de asignación donde M = number of bits modulo 8 , creo.

El ciclo se puede hacer más eficiente en algunas máquinas traduciendo a punteros

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

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

(Acabo de tipear esto, por lo que ahora sería un buen momento para que alguien revise el código, especialmente dado que es muy fácil equivocarse al jugar un poco).