Hacker News new | ask | show | jobs
by applecore 4707 days ago
Interesting. What's the purpose of reversing the bits in a byte?
5 comments

A common approach for performing a Fast Fourier Transform involves reversing the bits in time-domain samples.
Expanding slightly, there’s a permutation that needs to happen in order to efficiently perform a DFT in-place (and the same approach is often used even when the transform is out-of-place). For power of two sizes (one of the most common cases), that permutation is precisely the same as a bit reversal of the indices.
Reversing the bits in the index to the samples :-)
Besides the FFT addressing, I have encountered SPI devices that wanted to be addressed in LSb-first manner. Some micros let you choose which end goes out first, some don't. In the latter case you find yourself swapping bits in software.
My guess would be FFT. IIRC, a fast implementation of that requires lots of bit reversal. My memory is rusty, though :)
Passwords for the RFB protocol (VNC) are used to DES-encrypt a challenge token sent by the server. However, each byte in the key is reversed before it is used for encryption.

Of course, this happens only once per connection so there's generally not much of a need for it to be particularly fast.

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.

It was at one time standard to store each bitplane separately. If you had a 4-color 320x200 image, for example, you'd have one page of VRAM that stored a 320x200 1-bit image, holding all the bit 0s, and another, exactly the same, holding all the bit 1s. And so on up to as many bit planes as required. (That was one usual arrangement, but there are other options - e.g., interleaved bitplanes and/or no video RAM as such.)

Separate bitplanes were very annoying in many respects, and the demise of the approach was probably regretted by only a few. But storing each bitplane separately does have one major advantage: you can just write all your algorithms to operate on 1-bit images, and they automatically run at any bit depth. Just run the routine once for each bitplane you're interested in processing.

(That may also mean the hardware is simpler to implement - one plausible excuse for its ubiquity. Not my field of expertise though...)

I don't even think that mirroring images would require reversing bytes, unless you want to mess up the color components also or something...