Reversing Bits in C
corner.squareup.com
Reversing Bits in C
1–10 of 91 posts
Re: Reversing Bits in C
#2Great analysis, although I'm curious how the idea that doing a bunch of 64 bit ops in order to accomplish byte arithmetic came about to begin with - was the function in question not written by a firmware guy?
Re: Reversing Bits in C
#3Along the same vein, Andrew Dalke wrote up an interesting series of blog posts benchmarking different implementations of population count (counting the number of set bits in a word):
http://dalkescientific.com/writings/diary/archive/2008/07/03...
http://dalkescientific.com/writings/diary/archive/2008/07/05...
http://dalkescientific.com/writings/diary/archive/2011/11/02...
The Stanford Bit Hacks page linked in the original article is also very interesting reading for folks into this sort of stuff.
Re: Reversing Bits in C
#4Interestingly, while x86-64 does not seem to have a single opcode for reversing bits in a byte, it has a function to arbitrarily shuffle around the 16 bytes in a 128bit SSE register [PSHUFB]. It just blows my mind how much data those SIMD instructions process or move around in relatively few clock-cycles.
http://stackoverflow.com/a/9040426
http://www.intel.com/content/www/us/en/processors/architectu... (it's on page 1256 of 3251).
Re: Reversing Bits in C
#5The multiplication trick reminds me of this StackOverflow answer[1] where an SMT solver (z3) is used to derive mask and multiplier to extract chosen bits from a byte.
[1] : http://stackoverflow.com/questions/14547087/extracting-bits-...
Re: Reversing Bits in C
#6In the GA144, lookup tables are pretty painful, so the way I implement reverse there is:
reverse: a! 16 push . 2 dup . . begin +x 2* 2* unext +x 2* a . + nip ;
In Intel x86/64, the fastest way I know of is to use SIMD instructions, and break the 64-bit word into 16 nibbles (4-bit pieces), and use PSHUFB to perform a parallel lookup against another 128-bit xmm register. Then you aggregate the nibbles in reverse order, using inclusive or and variants of the shuffle instruction.
Re: Reversing Bits in C
#7Interestingly, while x86-64 does not seem to have a single opcode for reversing bits in a byte, it has a function to arbitrarily shuffle around the 16 bytes in a 128bit SSE register [PSHUFB]. It just blows my mind how much data those SIMD instructions process or move around in relatively few clock-cycles. http://stackoverflow.com/a/9040426 http://www.intel.com/content/www/us/en/processors/architectu... (it's on page…
It’s actually shocking how long it took Intel to add PSHUFB to SSE. Altivec (PPC) had the even-more-powerful vperm (arbitrary shuffle mapping 32B to 16B) way back in 1999.
Re: Reversing Bits in C
#8Great analysis, although I'm curious how the idea that doing a bunch of 64 bit ops in order to accomplish byte arithmetic came about to begin with - was the function in question not written by a firmware guy?
Or the programmer was a firmware hacker, and she knew that RBIT is ARMv6T2, which IIRC wasn't available until the iPhone 3GS. (Not 100% certain, and I don't have my manuals handy)
Re: Reversing Bits in C
#9Great analysis, although I'm curious how the idea that doing a bunch of 64 bit ops in order to accomplish byte arithmetic came about to begin with - was the function in question not written by a firmware guy?
I think this one goes back to PDP days and wasn't necessarily written to be the fastest possible implementation. The PDP could do 36*36 multiply into 72 bits. Not sure how the modulo instruction performed but there was a DIV instruction.
Re: Reversing Bits in C
#10Great analysis, although I'm curious how the idea that doing a bunch of 64 bit ops in order to accomplish byte arithmetic came about to begin with - was the function in question not written by a firmware guy?
I think this one goes back to PDP days and wasn't necessarily written to be the fastest possible implementation. The PDP could do 36*36 multiply into 72 bits. Not sure how the modulo instruction performed but there was a DIV instruction.
Down the rabbit hole says this came from HAKMEM No. 239 in 1972!