¿Qué es un algoritmo eficiente en el tiempo para copiar matrices de bits no alineadas?

Question

He tenido que hacer esto muchas veces en el pasado, y nunca he estado satisfecho con los resultados.

¿Alguien puede sugerir una forma rápida de copiar una matriz de bits contigua desde el origen hasta el destino donde tanto la fuente como el destino pueden no estar alineados (desplazados a la derecha) en los límites convenientes del procesador?

Si la fuente y el destino no están alineados, el problema puede cambiarse rápidamente a uno en el que solo ninguno de ellos esté alineado (después de la primera copia).

Como punto de partida, mi código es inevitable que se busca algo así como las siguientes (ignorar los efectos no probados, lado esto es sólo una fuera el ejemplo manguito):

const char mask[8] = { 1, 3, 7, 15, 31, 63, 127, 255 }; 
/* Assume: 
* - destination is already zeroed, 
* - offsets are right shifts 
* - bits to copy is big (> 32 say) 
*/ 
int bitarray_copy(char * src, int src_bit_offset, int src_bit_len, 
        char * dst, int dst_bit_offset) { 
    if (src_bit_offset == dst_bit_offset) { /* Not very interesting */ 
    } else { 
     int bit_diff_offset = src_bit_offset - dst_bit_offset; /* assume positive */ 
     int loop_count; 
     char c; 
     char mask_val = mask[bit_diff_offset]; 

     /* Get started, line up the destination. */ 
     c = (*src++ << bit_diff_offset) | ((*src >> (8 - bit_diff_offset)) & mask_val); 
     c &= mask[8-dst_bit_offset]; 

     *dst++ |= c; 

     src_bit_len -= 8 - dst_bit_offset; 
     loop_count = src_bit_len >> 3; 

     while (--loop_count >= 0) 
      * dst ++ = (*src++ << bit_diff_offset) | ((*src >> (8 - bit_diff_offset)) & mask_val); 

     /* Trailing tail copy etc ... */ 
     if (src_bit_len % 8) /* ... */ 
    } 
} 

(en realidad esto es mejor que yo' he hecho antes. No se ve muy mal)

Answer 1

Su bucle interno toma pedazos de dos bytes y los mueve a un byte de destino. Eso es casi óptimo. Aquí hay algunos consejos más sin un orden en particular:

• No hay necesidad de limitarse a un byte a la vez. Usa el tamaño entero más grande que tu plataforma te permita salirte con la tuya. Esto, por supuesto, complicará su lógica inicial y final.
• Si usa caracteres o caracteres enteros sin signo, es posible que no necesite enmascarar la segunda parte de la fuente una vez que se haya desplazado hacia la derecha. Esto dependerá de tu compilador.
• Si necesita la máscara, asegúrese de que su compilador está moviendo la búsqueda de la tabla fuera del ciclo. Si no es así, cópielo en una variable temporal y úselo.

Answer 2

Su solución es similar a la mayoría de las que he visto: básicamente, realiza un trabajo no alineado al principio y al final, con el bucle principal en el medio utilizando accesos alineados. Si realmente necesita eficiencia y lo hace en flujos de bits muy largos, le sugiero que utilice algo específico de arquitectura como SSE2 en el ciclo principal.

Answer 3

Lo óptimo dependerá de la plataforma de destino. En algunas plataformas sin desplazador de barril, desplazar todo el vector hacia la derecha o hacia la izquierda un bit, n veces, para n < 3, será el enfoque más rápido (en la plataforma PIC18, un ciclo de bytes desenrollado 8x para desplazar un bit izquierdo costará 11 ciclos de instrucciones por ocho bytes). De lo contrario, me gusta el patrón (nota Src2 tendrá que ser inicializado dependiendo de lo que quiere hacer con el final de su memoria intermedia)

 
    src1 = *src++; 
    src2 = (src1 shl shiftamount1) | (src2 shr shiftamount2); 
    *dest++ = src2; 
    src2 = *src++; 
    src1 = (src2 shl shiftamount1) | (src1 shr shiftamount2); 
    *dest++ = src1; 

que debe prestarse a la implementación muy eficiente en un ARM (ocho instrucciones de cada dos palabras, si los registros están disponibles para src, dest, src1, src2, shiftamount1 y shiftamount2. El uso de más registros permitiría un funcionamiento más rápido a través de instrucciones de carga/almacenamiento de palabras múltiples. Manejar cuatro palabras sería algo así como (una instrucción de máquina por línea, excepto que las primeras cuatro líneas juntas serían una instrucción, al igual que las últimas cuatro líneas):

 
    src0 = *src++; 
    src1 = *src++; 
    src2 = *src++; 
    src3 = *src++; 
    tmp = src0; 
    src0 = src0 shr shiftamount1 
    src0 = src0 | src1 shl shiftamount2 
    src1 = src1 shr shiftamount1 
    src1 = src1 | src2 shl shiftamount2 
    src2 = src2 shr shiftamount1 
    src2 = src2 | src3 shl shiftamount2 
    src3 = src3 shr shiftamount1 
    src3 = src3 | tmp shl shiftamount2 
    *dest++ = src0; 
    *dest++ = src1; 
    *dest++ = src2; 
    *dest++ = src3; 

Se rotaron once instrucciones por cada 16 bytes.

Answer 4

Esto es lo que terminé haciendo. (EDIT Se cambió el 8/21/2014 por un error de copia de un solo bit.)

#include <limits.h> 
#include <string.h> 
#include <stddef.h> 

#define PREPARE_FIRST_COPY()          \ 
    do {               \ 
    if (src_len >= (CHAR_BIT - dst_offset_modulo)) {    \ 
     *dst  &= reverse_mask[dst_offset_modulo];    \ 
     src_len -= CHAR_BIT - dst_offset_modulo;     \ 
    } else {              \ 
     *dst  &= reverse_mask[dst_offset_modulo]    \ 
       | reverse_mask_xor[dst_offset_modulo + src_len]; \ 
     c  &= reverse_mask[dst_offset_modulo + src_len]; \ 
     src_len = 0;            \ 
    } } while (0) 


static void 
bitarray_copy(const unsigned char *src_org, int src_offset, int src_len, 
        unsigned char *dst_org, int dst_offset) 
{ 
    static const unsigned char mask[] = 
     { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff }; 
    static const unsigned char reverse_mask[] = 
     { 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff }; 
    static const unsigned char reverse_mask_xor[] = 
     { 0xff, 0x7f, 0x3f, 0x1f, 0x0f, 0x07, 0x03, 0x01, 0x00 }; 

    if (src_len) { 
     const unsigned char *src; 
       unsigned char *dst; 
     int     src_offset_modulo, 
          dst_offset_modulo; 

     src = src_org + (src_offset/CHAR_BIT); 
     dst = dst_org + (dst_offset/CHAR_BIT); 

     src_offset_modulo = src_offset % CHAR_BIT; 
     dst_offset_modulo = dst_offset % CHAR_BIT; 

     if (src_offset_modulo == dst_offset_modulo) { 
      int    byte_len; 
      int    src_len_modulo; 
      if (src_offset_modulo) { 
       unsigned char c; 

       c = reverse_mask_xor[dst_offset_modulo]  & *src++; 

       PREPARE_FIRST_COPY(); 
       *dst++ |= c; 
      } 

      byte_len = src_len/CHAR_BIT; 
      src_len_modulo = src_len % CHAR_BIT; 

      if (byte_len) { 
       memcpy(dst, src, byte_len); 
       src += byte_len; 
       dst += byte_len; 
      } 
      if (src_len_modulo) { 
       *dst  &= reverse_mask_xor[src_len_modulo]; 
       *dst |= reverse_mask[src_len_modulo]  & *src; 
      } 
     } else { 
      int    bit_diff_ls, 
          bit_diff_rs; 
      int    byte_len; 
      int    src_len_modulo; 
      unsigned char c; 
      /* 
      * Begin: Line things up on destination. 
      */ 
      if (src_offset_modulo > dst_offset_modulo) { 
       bit_diff_ls = src_offset_modulo - dst_offset_modulo; 
       bit_diff_rs = CHAR_BIT - bit_diff_ls; 

       c = *src++ << bit_diff_ls; 
       c |= *src >> bit_diff_rs; 
       c  &= reverse_mask_xor[dst_offset_modulo]; 
      } else { 
       bit_diff_rs = dst_offset_modulo - src_offset_modulo; 
       bit_diff_ls = CHAR_BIT - bit_diff_rs; 

       c = *src >> bit_diff_rs  & 
        reverse_mask_xor[dst_offset_modulo]; 
      } 
      PREPARE_FIRST_COPY(); 
      *dst++ |= c; 

      /* 
      * Middle: copy with only shifting the source. 
      */ 
      byte_len = src_len/CHAR_BIT; 

      while (--byte_len >= 0) { 
       c = *src++ << bit_diff_ls; 
       c |= *src >> bit_diff_rs; 
       *dst++ = c; 
      } 

      /* 
      * End: copy the remaing bits; 
      */ 
      src_len_modulo = src_len % CHAR_BIT; 
      if (src_len_modulo) { 
       c = *src++ << bit_diff_ls; 
       c |= *src >> bit_diff_rs; 
       c  &= reverse_mask[src_len_modulo]; 

       *dst  &= reverse_mask_xor[src_len_modulo]; 
       *dst |= c; 
      } 
     } 
    } 
}