Reversing Bits in C • Hacker News Board

Re: Reversing Bits in C

#21

Post by ErsatzVerkehr » Tue, Jul 30, 2013, 8:43 PM UTC

unoti wrote: post #20

kbojody wrote: post #19

Earlier quoted context omitted.

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...

> mirroring an image horizontally

...but only a 2-color image.

Re: Reversing Bits in C

#22

Post by RodgerTheGreat » Tue, Jul 30, 2013, 8:45 PM UTC

applecore wrote: post #15

Interesting. What's the purpose of reversing the bits in a byte?

A common approach for performing a Fast Fourier Transform involves reversing the bits in time-domain samples.

Re: Reversing Bits in C

#23

Post by groby_b » Tue, Jul 30, 2013, 8:48 PM UTC

applecore wrote: post #15

Interesting. What's the purpose of reversing the bits in a byte?

My guess would be FFT. IIRC, a fast implementation of that requires lots of bit reversal. My memory is rusty, though :)

Re: Reversing Bits in C

#24

Post by picomancer » Tue, Jul 30, 2013, 8:49 PM UTC

robomartin wrote: post #14

If 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.

> changing the endian-ness

x86 has had the BSWAP instruction since the 486.

gcc has a __builtin_bswap16, __builtin_bswap32, and __builtin_bswap64 which will presumably take advantage of these built-in instructions on x86 and any other gcc-supported architectures where similar instructions exist (and fall back to a reasonably fast and well-tested multi-instruction implementation where they don't).

You should really RTFM every couple years, just to know what your processor [1] and compiler [2] can do.

[1] http://www.intel.com/content/www/us/en/processors/architectu...

[2] http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

Re: Reversing Bits in C

#25

Post by ajb » Tue, Jul 30, 2013, 8:55 PM UTC

RodgerTheGreat wrote: post #22

applecore wrote: post #15

Interesting. What's the purpose of reversing the bits in a byte?

A common approach for performing a Fast Fourier Transform involves reversing the bits in time-domain samples.

Reversing the bits in the index to the samples :-)

Re: Reversing Bits in C

#26

Post by Symmetry » Tue, Jul 30, 2013, 8:57 PM UTC

Very interesting, though you shouldn't be surprised by small differences between O(1) and O(N) algorithms when N is only 8.

Re: Reversing Bits in C

#27

Post by fjarlq » Tue, Jul 30, 2013, 8:59 PM UTC

A great companion to this sort of thing is the book Hacker's Delight by Henry S. Warren, Jr:

http://www.hackersdelight.org/

http://www.amazon.com/Hackers-Delight-2nd-Edition-ebook/dp/B...

Re: Reversing Bits in C

#28

Post by stephencanon » Tue, Jul 30, 2013, 9:00 PM UTC

Symmetry wrote: post #26

Very interesting, though you shouldn't be surprised by small differences between O(1) and O(N) algorithms when N is only 8.

If N is 8, then O(N) is O(1). For that matter, so is O(f(N)), for any function f.

Re: Reversing Bits in C

#29

Post by stephencanon » Tue, Jul 30, 2013, 9:05 PM UTC

kibwen wrote: post #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.

Modern ARM has lots of instructions that don’t have direct x86 equivalents. Most are in the vector domain, but there are plenty of non-vector examples too: BFI, BFC, BIC, ORN, RSB, saturating arithmetic, numerous multiply-add variants, etc.

Re: Reversing Bits in C

#30

Post by stephencanon » Tue, Jul 30, 2013, 9:08 PM UTC

chacham15 wrote: post #12

stephencanon wrote: post #7

Earlier 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

Like my sibling posted, the crazy CISCy instructions aren’t comparable because in general they were no faster than an equivalent sequence of simpler instructions. That’s not the case for permute; there are no “simpler” instructions that let you build an efficient permute. It’s one the fundamental building blocks for efficient vector code -- that’s why it’s shocking that it was added to SSE so late.