I'm glad they noted that the lookup table's speed relies on it being in cache, which most "benchmark magic bit-fiddling operations" posts ignore. (Although it's temporal locality, not cache coherence, that's important for this.)
Reversing Bits in C
11–20 of 91 posts
Re: Reversing Bits in C
#12Interestingly, 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.
The VAX (circa 1977) had polynomial evaluation as an instruction[1]. What is your point?
Re: Reversing Bits in C
#13Earlier quoted context omitted.
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.
The VAX (circa 1977) had polynomial evaluation as an instruction[1]. What is your point? [1] http://en.wikipedia.org/wiki/VAX
The point is that bit twiddling can be much more efficient to implement in hardware because all you're doing is placing wires somewhere. The RBIT instruction in the article significantly speeds up an operation at very low hardware cost.
Polynomial evaluation does not fit into this pattern, because you need actual arithmetic operations to do it, and so a hardware polynomial evaluation instruction has no significant benefit over the corresponding sequence of explicit multiplications and additions.
Re: Reversing Bits in C
#14If you've ever dealt with graphics file manipulation code chances are you've suffered the pain of changing the endian-ness of an image file. I never understood why some of these operations are not implemented as machine instructions that can run in one instruction cycle flat. There's nothing to them, I've done exactly that on FPGA's. Yes, they can be a little resource/routing intensive but not that bad.
Re: Reversing Bits in C
#15Interesting. What's the purpose of reversing the bits in a byte?
Re: Reversing Bits in C
#16In 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,…
This does an 18 bit word, right?
Re: Reversing Bits in C
#17"Intel x86/x64 processors don’t have this instruction, so this is definitely not a portable solution."
This stuck out to me. I know that RISC vs CISC is basically a meaningless distinction nowadays, but I still naively expected that x86 would be more-or-less a strict superset of ARM.
Re: Reversing Bits in C
#18"Intel x86/x64 processors don’t have this instruction, so this is definitely not a portable solution." This stuck out to me. I know that RISC vs CISC is basically a meaningless distinction nowadays, but I still naively expected that x86 would be more-or-less a strict superset of ARM.
Strictly speaking, AMD's XOP extensions do have an instruction that is close enough: VPPERM. It allows to not only shuffle bytes, like the already mentioned PSHUFB, but also reverse bits within each byte. Therefore, a single VPPERM instruction can reverse up to 128 bits at a time.
Re: Reversing Bits in C
#19Interesting. What's the purpose of reversing the bits in a byte?
Endian is probably the most common.
Re: Reversing Bits in C
#20Interesting. What's the purpose of reversing the bits in a byte?
Endian is probably the most common.
Endian-ness would be reversing bytes, not bits within bytes, like 0x1234 -> 0x3412. What we're talking about here would be more along the lines of: 0b0010001 -> 0b1000100
The most obvious application I can think of for reversing bits within a byte would be for image processing applications, such as mirroring an image horizontally, or making kaleidoscopes. There are probably signal processing applications, too...