Jaki jest skuteczny algorytm czasu do kopiowania niezarządzanych macierzy bitowych?

Question

Musiałem to robić wiele razy w przeszłości i nigdy nie byłem zadowolony z wyników.

Czy ktoś może zaproponować szybki sposób kopiowania sąsiadującej tablicy bitów ze źródła do miejsca docelowego, w którym zarówno źródło, jak i miejsce docelowe mogą nie być wyrównane (przesunięte w prawo) na dogodnych granicach procesora?

Jeśli zarówno źródło, jak i cel nie są wyrównane, problem można szybko zmienić na taki, w którym tylko jeden z nich nie jest wyrównany (po napisaniu pierwszej kopii).

Jako punkt wyjścia, mój kod nieuchronnie kończy się szuka czegoś podobnego następujące (niesprawdzonych ignorować skutków ubocznych jest to tylko przy mankiecie przykład):

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) /* ... */ 
    } 
} 

(faktycznie jest to lepiej niż ja” To nie wygląda zbyt źle)

Answer 1

Twoja wewnętrzna pętla zajmuje dwa bajty i przenosi je do docelowego bajtu. To prawie optymalne. Oto kilka dodatkowych wskazówek w konkretnej kolejności:

• Nie ma potrzeby ograniczać się do bajtu na raz. Użyj największej liczby całkowitej, z której twoja platforma pozwoli Ci uciec. To oczywiście komplikuje początkową i końcową logikę.
• Jeśli używasz niepodpisanych znaków lub liczb całkowitych, może nie być konieczne maskowanie drugiego fragmentu źródła po jego przesunięciu w prawo. To będzie zależeć od twojego kompilatora.
• Jeśli potrzebujesz maski, upewnij się, że kompilator przesuwa wyszukiwanie tabeli poza pętlę. Jeśli nie jest, skopiuj go do zmiennej tymczasowej i użyj tego.

Answer 2

Twoje rozwiązanie wygląda podobnie do większości, które widziałem: w zasadzie wykonuj pewną niewyrównaną pracę na początku i na końcu, z główną pętlą w środku, korzystając z wyrównanych dostępów. Jeśli naprawdę potrzebujesz wydajności i robisz to w bardzo długich strumieniach, proponuję użyć czegoś specyficznego dla architektury, jak SSE2 w głównej pętli.

Answer 3

To, co jest optymalne, zależy od platformy docelowej. Na niektórych platformach bez przełączników beczkowych, przesunięcie całego wektora w prawo lub w lewo o jeden bit, n razy, dla n < 3, będzie najszybszym podejściem (na platformie PIC18, 8-literowa pętla bajtowa do przesunięcia w lewo jednym bitem będzie kosztować 11 cykle instrukcji na osiem bajtów). W przeciwnym razie, lubię wzór (uwaga src2 będą musiały być inicjowane w zależności od tego, co chcesz zrobić z końcem swojej bufor)

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

To powinno nadaje się do bardzo skutecznego wdrażania na ARM (osiem wskazówek co dwa słowa, jeżeli dostępne są rejestry dla src, dest, src1, src2, shiftamount1 i shiftamount2, użycie większej liczby rejestrów umożliwiłoby szybszą obsługę za pomocą instrukcji ładowania/składowania wielu słów. Obsługa czterech słów byłaby podobna (jedna instrukcja maszynowa na linię, z wyjątkiem pierwszych czterech linii stanowiących łącznie jedną instrukcję, podobnie jak cztery ostatnie linie):

 
    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; 

Jedenaście instrukcji na 16 bajtów obróconych.

Answer 4

Tak właśnie zrobiłem. (EDYCJA Zmieniono na 8/21/2014 w przypadku błędu pojedynczej kopii.)

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