Thuật toán hiệu quả thời gian để sao chép mảng bit không được ký hiệu là gì?

Question

Tôi đã phải làm điều này nhiều lần trong quá khứ và tôi chưa bao giờ hài lòng với kết quả.

Bất cứ ai có thể đề xuất cách sao chép nhanh mảng bit liền kề từ nguồn đến đích nơi cả nguồn và đích có thể không căn chỉnh (phải dịch chuyển) trên ranh giới bộ xử lý thuận tiện?

Nếu cả nguồn và đích không được căn chỉnh, vấn đề có thể nhanh chóng được thay đổi thành một nơi mà chỉ có một trong số chúng không được căn chỉnh (sau bản sao đầu tiên nói).

Như một điểm khởi đầu, mã của tôi chắc chắn sẽ trông giống như sau (, bỏ qua tác dụng phụ chưa được kiểm tra này chỉ là một off the dụ cuff là):

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

(thực ra đây là tốt hơn so với tôi đã thực hiện trước đó. Nó không quá xấu)

Answer 1

Vòng lặp bên trong của bạn lấy các phần của hai byte và di chuyển chúng đến một byte đích. Đó là gần như tối ưu. Dưới đây là một vài gợi ý khác không theo thứ tự cụ thể:

• Không cần giới hạn bản thân vào một byte cùng một lúc. Sử dụng kích thước nguyên lớn nhất nền tảng của bạn sẽ cho phép bạn thoát khỏi. Điều này tất nhiên sẽ làm phức tạp logic bắt đầu và theo dõi của bạn.
• Nếu bạn sử dụng ký tự không dấu hoặc số nguyên, bạn có thể không cần che phần thứ hai của nguồn sau khi được dịch chuyển sang phải. Điều này sẽ phụ thuộc vào trình biên dịch của bạn.
• Nếu bạn cần mặt nạ, hãy đảm bảo trình biên dịch của bạn đang di chuyển tìm kiếm bảng bên ngoài vòng lặp. Nếu không, hãy sao chép nó vào một biến tạm thời và sử dụng nó.

Answer 2

Giải pháp của bạn trông giống như hầu hết những gì tôi đã thấy: về cơ bản thực hiện một số công việc chưa được ký ở đầu và cuối, với vòng lặp chính ở giữa sử dụng truy cập được căn chỉnh. Nếu bạn thực sự cần hiệu quả và làm điều này trên bitstream rất dài, tôi sẽ đề nghị sử dụng một cái gì đó kiến ​​trúc cụ thể như SSE2 trong vòng lặp chính.

Answer 3

Điều tối ưu sẽ phụ thuộc vào nền tảng đích. Trên một số nền tảng mà không cần chuyển số thùng, dịch chuyển toàn bộ vectơ sang phải hoặc trái một bit, n lần, cho n < 3, sẽ là phương pháp nhanh nhất (trên nền tảng PIC18, một vòng byte 8x chưa được cuộn để dịch chuyển sang trái một chút sẽ có giá 11 chu kỳ lệnh trên mỗi tám byte). Nếu không, tôi thích mô hình (lưu ý src2 sẽ phải được khởi tạo tùy thuộc vào những gì bạn muốn làm với thời điểm cuối của bộ đệm của bạn)

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

Điều đó sẽ tự để thực hiện rất hiệu quả cho vay trên ARM (tám hướng dẫn mỗi hai các từ, nếu các thanh ghi có sẵn cho src, dest, src1, src2, shiftamount1 và shiftamount2. Sử dụng nhiều thanh ghi hơn sẽ cho phép hoạt động nhanh hơn thông qua các lệnh tải/lưu trữ nhiều từ. ngoại trừ bốn dòng đầu tiên sẽ cùng nhau là một hướng dẫn, cũng như bốn dòng cuối cùng):

 
    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; 

Mười một lệnh mỗi 16 byte được xoay.

Answer 4

Đây là những gì tôi đã kết thúc. (EDIT Đã thay đổi vào ngày 21/8/2014 cho một lỗi bản sao 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; 
      } 
     } 
    } 
}