什么是复制未对齐位数组的高效算法? [英] 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).
作为一个起点,我的代码最终不可避免地看起来类似于以下内容(未经测试,忽略副作用,这只是一个即兴例子):
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屋!