Bit reversing

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

Post Reply
claudineskiles
Posts: 1
Joined: Mon Mar 30, 2020 9:16 pm

Bit reversing

Post by claudineskiles » Mon Mar 30, 2020 9:18 pm

[spam deleted]
Last edited by claudineskiles on Mon Apr 27, 2020 7:23 am, edited 2 times in total.

User avatar
tokumaru
Posts: 11691
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Bit reversing

Post by tokumaru » Mon Mar 30, 2020 9:29 pm

Well, the obvious way would be this:

Code: Select all

lsr Variable
rol a
lsr Variable
rol a
lsr Variable
rol a
lsr Variable
rol a
lsr Variable
rol a
lsr Variable
rol a
lsr Variable
rol a
lsr Variable
rol a
sta Variable
It's possible that there are clever tricks to speed this up, but if this is a serious requirement of your program, you might consider investing in a 256-byte look-up table.

User avatar
Bregalad
Posts: 7879
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland

Re: Bit reversing

Post by Bregalad » Tue Mar 31, 2020 1:51 am

The chances you'll ever need bit reversing in real-life applications are very small. If you need it somewhere, the odds that you designed something badly are very big.

This is similar to those programming exercices that requires you to swap 2 variables (via several exculsing-or opperation). It's a fun exercice, but if I ever see this in a real program I'll wonder about the sanity of the whole thing.

Or programing exercices that does a complex calculations and display the result. If what you wanted to do is just display the result, then just code something that does - there's no reason your program should do any calculation prior to that if you could do it yourself.
Last edited by Bregalad on Wed Apr 01, 2020 1:55 am, edited 1 time in total.

User avatar
rainwarrior
Posts: 7812
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Bit reversing

Post by rainwarrior » Tue Mar 31, 2020 3:05 am

Bregalad wrote:
Tue Mar 31, 2020 1:51 am
The chances you'll ever need bit reversing in real-life applications are very small. If you need it somewhere, the odds that you designed something badly are very big.
There are a few applications that bit-reversal applies to. Indexing for a fast fourier transform algorithm is one that I remember from the top of my head. I think there's some cache-coherent reordered texture formats for GPUs that it may apply to as well.

On modern CPUs there are some bit-swizzling instructions that are really good at this sort of thing, but of course that doesn't help with 6502.

User avatar
Alp
Posts: 220
Joined: Mon Oct 06, 2014 12:37 am

Re: Bit reversing

Post by Alp » Tue Mar 31, 2020 6:18 am

Bregalad wrote:
Tue Mar 31, 2020 1:51 am
The chances you'll ever need bit reversing in real-life applications are very small. If you need it somewhere, the odds that you designed something badly are very big.
Depends on what you're doing with it.

When I wrote an Atari 2600 game a few years ago, I had used both bit-reversal and masking, to save as much ROM space as possible.
(I only used a 4KB ROM for it.)

tepples
Posts: 21971
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Bit reversing

Post by tepples » Tue Mar 31, 2020 6:51 am

On Nintendo PPUs, the need for bit reversal is small but not quite nonexistent. The application I ran into during the development of 240p Test Suite involved copying the tiles in the left half of a symmetric scene to the right half and flipping them. The NES and Game Boy PPU both lack background tile flipping, and I want to fit both within a ROM size limit. (More so on Game Boy because of the steep cost of exceeding 32K in currently available homebrew carts.)

Bit reversal is more common on SMS because its VDP has no sprite flipping. But then it's so common there that a 256-entry lookup table is worthwhile, as shown in this tech demo.

User avatar
Jarhmander
Formerly ~J-@D!~
Posts: 497
Joined: Sun Mar 12, 2006 12:36 am
Location: Rive nord de Montréal

Re: Bit reversing

Post by Jarhmander » Tue Mar 31, 2020 8:27 pm

Let's not forget that bit reversing the frame counter can be useful to allow subpixel velocities without having to store the subpixel position, as explained here.
((λ (x) (x x)) (λ (x) (x x)))

User avatar
Bregalad
Posts: 7879
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland

Re: Bit reversing

Post by Bregalad » Wed Apr 01, 2020 1:54 am

OK please disregard what I said. BG tile flipping would be a senseful application of bit reversing on the NES for example - I'm just used to use CHR-ROM and I forgot about CHR-RAM.

What I originally tought - if you'd for example store the bits reversed in ROM as opposed to what your program uses, but if there would be no rational reason for them to be that way, other than "the data is more user-friendly to store that way" - then it'd be bad programming. Just like how we learn to made 16-bit pointer tables with lower and upper bytes interleved, when it's actually simpler to have separate low and high table - despite it being less user-friendly to handle.

Post Reply