Какой эффективный алгоритм времени для копирования неровных бит-массивов?

Мне приходилось делать это много раз в прошлом, и я никогда не был доволен результатами.

Может ли кто-нибудь предложить быстрый способ копирования непрерывного массива бит из источника в пункт назначения, где как источник, так и пункт назначения могут не быть выровнены (сдвинуты вправо) на удобных границах процессора?

Если оба источника и адресата не выровнены, проблему можно быстро изменить на одну, где только одна из них не выровнена (после первой копии).

В качестве отправной точки мой код неизбежно заканчивается тем, что выглядит следующим образом (непроверенные, игнорируют побочные эффекты, это просто от примера манжеты):

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++ <> (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++ <> (8 - bit_diff_offset)) & mask_val); /* Trailing tail copy etc ... */ if (src_bit_len % 8) /* ... */ } } 

(на самом деле это лучше, чем я делал раньше. Это выглядит не так уж плохо)

    Ваш внутренний цикл принимает куски двух байтов и перемещает их в байт назначения. Это почти оптимально. Вот еще несколько советов в каком-то конкретном порядке:

    • Нет необходимости ограничивать себя байтом за раз. Используйте самый большой целочисленный размер, который ваша платформа позволит вам уйти. Это, конечно, усложнит вашу начальную и конечную логику.
    • Если вы используете неподписанные символы или целые числа, вам может не понадобиться замаскировать второй fragment источника после его смещения вправо. Это будет зависеть от вашего компилятора.
    • Если вам нужна маска, убедитесь, что ваш компилятор перемещает поиск таблицы вне цикла. Если это не так, скопируйте его во временную переменную и используйте это.

    Это то, что я закончил делать. ( EDIT изменен на 21.08.2014 для однобитовой копии.)

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

    То, что оптимально, будет зависеть от целевой платформы. На некоторых платформах без баррелей-сдвигов сдвиг всего вектора вправо или влево один бит, n раз, при n <3, будет самым быстрым (на платформе PIC18, 8x-развернутый цикл байта для сдвига влево один бит будет стоить 11 циклов инструкций на восемь байтов). В противном случае мне нравится шаблон (примечание src2 нужно будет инициализировать в зависимости от того, что вы хотите сделать с концом вашего буфера)

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

    Это должно обеспечить очень эффективную реализацию на ARM (восемь инструкций каждые два слова, если регистры доступны для src, dest, src1, src2, shiftamount1 и shiftamount2. Использование большего количества регистров позволит ускорить работу через многословную загрузку / сохранение Инструкции. Обработка четырех слов будет чем-то вроде (одна машинная инструкция на строку, за исключением того, что первые четыре строки будут вместе одной инструкцией, как и последние четыре строки):

       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;
    

    Одиннадцать команд на 16 байт повернуты.

    Ваше решение похоже на большинство, что я видел: в основном выполняйте некоторую работу без выравнивания в начале и в конце, с основным циклом в середине, используя выровненные обращения. Если вам действительно нужна эффективность и сделать это на очень длинных битовых streamах, я бы предложил использовать что-то вроде архитектуры, например SSE2 в основном цикле.