Databases
StackOverflow2013
Postsdbo
POWhat's a time efficient algorithm to copy unaligned bit arrays?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhat's a time efficient algorithm to copy unaligned bit arrays?
    text
    copied!<p>I've had to do this many times in the past, and I've never been satisfied with the results.</p> <p><strong>Can anyone suggest a fast way of copying a contiguous bit array from source to destination where both the source and destination's may not be aligned (right shifted) on convenient processor boundaries?</strong></p> <p>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).</p> <p>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):</p> <pre><code>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 (&gt; 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++ &lt;&lt; bit_diff_offset) | ((*src &gt;&gt; (8 - bit_diff_offset)) &amp; mask_val); c &amp;= mask[8-dst_bit_offset]; *dst++ |= c; src_bit_len -= 8 - dst_bit_offset; loop_count = src_bit_len &gt;&gt; 3; while (--loop_count &gt;= 0) * dst ++ = (*src++ &lt;&lt; bit_diff_offset) | ((*src &gt;&gt; (8 - bit_diff_offset)) &amp; mask_val); /* Trailing tail copy etc ... */ if (src_bit_len % 8) /* ... */ } } </code></pre> <p>(actually this is better than I've done before. It doesn't look too bad)</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload