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

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

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

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

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

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

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

6
задан Jamie 21 August 2010 в 02:32
поделиться