StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Interesting question. I assume your 37-bit sequence can begin at any point in a byte. Let's say your sequence is represented by this:</p> <pre>ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789@</pre> <p>If we have a byte aligned algorithm, we could see these 32-bit sequences bytes:</p> <pre> BCDEFGHIJKLMNOPQRSTUVWXYZ0123456 [call this pattern w_A] CDEFGHIJKLMNOPQRSTUVWXYZ01234567 [w_B, etc.] DEFGHIJKLMNOPQRSTUVWXYZ012345678 EFGHIJKLMNOPQRSTUVWXYZ0123456789 FGHIJKLMNOPQRSTUVWXYZ0123456789@ GHIJKLMNOPQRSTUVWXYZ0123456789@x HIJKLMNOPQRSTUVWXYZ0123456789@xx IJKLMNOPQRSTUVWXYZ0123456789@xxx </pre> <p>Only these byte values - no others -could form the second third and fourth byte of a byte sequence containing the 37 bits of interest.</p> <p>This leads to a reasonably obvious implementation:</p> <pre> unsigned char *p = ...; // input data size_t n = ...; // bytes available size_t bitpos; --n; p++; bitpos = 0; while (n--) { uint32_t word = *(uint32_t*)p; // nonportable, sorry. bitpos += 8; // compiler should be able to optimise this variable out completely if (word == w_A) { if ((p[4] & 0xF0 == 789@) && (p[-1] & 1 == A)) { // we found the data starting at the 8th bit of p-1 found_at(bitpos-1); } } else if (word == w_B) { if ((p[4] & 0xE0 == 89@) && (p[-1] & 3 == AB)) { // we found the data starting at the 7th bit of p-1 found_at(bitpos-2); } } else if (word == w_C} { ... } ... } </pre> <p>Obviously there are problems with this strategy. First, it might want to evaluate p[-1] first time around the loop, but that's easy to fix. Second, it fetches a word from odd addresses; that wont work on some CPUs - SPARC and 68k for example. But doing so is an easy way to roll 4 comparisons into one.</p> <p>kek444's suggestion would allow you to use a algorithm like KMP to skip forward in the data stream. However, the maximum size of the skip is not huge, so while the Turbo Boyer-Moore algorithm may reduce the number of byte comparisons by 4 or so, that may not be much of a win if the cost of a byte comparison is similar to the cost of a word comparision.</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