How do I get the chunk index from a screen row?

For all the scrolling functions I need to retrieve the playfield bytes of a specific row.  The screens are compressed on the ROM and are stored as indexes to chunks.  So to retrieve a row's playfield data I need to know which chunk it's in.  The problem I needed to solve is given a row number for a screen what chunk is the row in?

This may sound like a trivial problem, but I need to do it very fast since I need this during gameplay - not during screen load.

One option is to loop through the chunks of a screen and count up the chunk sizes until I pass the desired row number.... this is a terrible idea - too slow!

The solution I came up with is having a bit per row indicating if the current row is in a new chunk with a 1, or 0 if the current row is the same chunk as the previous row above it.  These bits are stored in 3 bytes called NewChunkIndicies0, NewChunkIndicies1, and NewChunkIndicies2.  Then I have to count all the bits down to and including the desired row.

Let's look at some examples.

The red line!  How do we count the bits down to and including the red line?  The red line is on the 7th bit of the first NewChunkIndicies byte.  Lets just mask out the bits of the first byte we're not interested in.  So let's do this:

Temp = NewChunkIndicies0 AND #%01111111.  Now we need to count the number of bits in Temp.

That brings us to another problem.  How do we count the number of bits in a byte?  The solution I came up with is having a 256 byte table with a bit count of any possible configuration of 8 bits.  That's a BIG table for the 2600!  I came up with an optimization.  I just store all possible bit counts of a nibble.  This is only a 16 byte table.  I use this table to add up the bits in both nibbles of a byte.  It's a tad slower but worth the speed tradeoff.  Let's put this in a "CountBits" function.

Going back to the red line problem I just put Temp into CountBits and get chunk #3.

Now what chunk is the orange line in?  The orange line is on the 10th row.  So to find the corresponding chunk I need to add up the first 10 bits of NewChunkIndicies.

I do CountBits on the entire first byte of NewChunkIndicies, and CountBits on the first 2 bits of NewChunkIndicies1.  So with some masking , counting and adding I get chunk #4.

For the lime green colored line I do the following:  CountBits(NewChunkIndicies0) + CountBits(NewChunkIndicies1) + CountBits(NewChunkIndicies2 AND %00111111).  This comes out to chunk #11.

Sorry if this was kinda boring, but game programming isn't all fun and games.