什么是一次有效的算法来复制未对齐位阵列？ [英] What's a time efficient algorithm to copy unaligned bit arrays?

问题描述

我已经在过去这样做很多次，我从来没有得到满意的结果。

I've had to do this many times in the past, and I've never been satisfied with the results.

任何人都可以提出从源头到目的地，源和目的地的可能不对齐（右移位）上的便利处理器边界复制一个连续的位阵列的快速方式？

如果源和目标的两个未对齐​​，问题可以迅速被改变成一个其中只有它们中的不对齐（第一个复制之后说）。

If both the source and destination's aren't aligned , the problem can quickly be changed into one where only either of them aren't aligned (after the first copy say).

作为一个起点，我的code不可避免地最终看起来类似下面的（未经测试，忽略副作用这只是一个即兴的例子）：

As a starting point, my code inevitably ends up looking something like the following (untested, ignore side effects this is just an off the cuff example):

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

（其实这是比我做过的事情。它看起来并不太坏）

(actually this is better than I've done before. It doesn't look too bad)

推荐答案

您内环需要两个字节块，并将其移动到目的地的字节。这几乎是最优的。这里有一些更多的提示没有特定的顺序：

Your inner loop takes pieces of two bytes and moves them to a destination byte. That's almost optimal. Here are a few more hints in no particular order:

• 有没有必要限制自己一个字节一次。使用最大整数大小平台将让你得逞的。这当然将你的起始和结尾的逻辑复杂化。


• 如果您使用的无符号的字符或整数，你可能不需要它的右移后，以掩盖第二片源。这将取决于你的编译器。


• 如果您需要做面膜，确保你的编译器是移动查表的循环之外。如果不是，将其复制到一个临时变量并使用它。

这篇关于什么是一次有效的算法来复制未对齐位阵列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！