!pr1
Building Hi-Res Pre-Shift Tables.............Gianluca Pomponi
                                                  Pisa, Italy

Given my interest in everything related to graphics, I read eagerly Bob's article "Generating Tables..." in the Dec 94 issue of AAL.  I haven't yet had the chance to read the Apple Supplement of Byte (my local newsstand receives it discontinuously); however, I had already heard about the use of preshift tables in animation.  I experimented with this technique some time ago, getting excellent results in moving colored shapes against some very complex backgrounds with relatively simple code.

Maybe one of the most challenging steps is typing in the preshift tables.  Writing a program to generate the tables is not difficult, and is probably better.  The code that follows only takes $68 bytes as a subroutine, using two page zero variables.  And it only takes 24 milliseconds to generate the tables, which is many times faster than reading them from a disk.

The Byte article used 14 tables of 256 bytes each.  They correspond to left and right portions of each possible 8-bit value shifted any amount from 1 to 7 bits.  No columns are kept in memory for shifting 0 bits, as the result is entirely too predictable.

Since, in hi-res graphics, the high bit does not get shifted, you can deal with it separately.  Before looking up the preshifted values you can split off the high bit and rejoin it later.  The extra code for this is very minor, and it results in a vast memory saving.  By doing it this way we get by with 12 tables of 128 bytes each (six pages instead of 14!).  Six tables for the left side results and six for the right, for every possible shift of from 1 to 6 bits, for every possible value from $00 to $7F.

I sometimes find it worthwhile to limit the quotient-remainder tables such as Bob generated in the December article to only 256 bytes each (instead of 280), using code like the following to read them when the X-coordinate is larger than 255:

       LDX XCOORD      low byte of xcoord
       LDA QUO+4,X
       CLC
       ADC #$24
       STA XBYTE
       LDA REM+4,X
       STA XBIT

Here now is my program to generate the preshift tables, as modified by Bob.  LInes 1080-1210 allocate space for the 12 tables, each 128 bytes long.  I put them at $0900 for this example, but of course you can put them wherever you wish.

Lines 1230-1310 are a macro definition.  The macro is called out six times in the main loop, once for each shift of a value.  For the benefit of those without a macro assembler, I have shown the expansion in the listing of lines 1430-1480.  Some of the code in the macro could have been handled by a subroutine, but it would save a negligible amount of space at a cost of an non-negligible amount of time.

The shifting algorithm is familiar to those of you who have been fiddling with hi-res for a while.  Remember that the picture bits are stored backwards in each byte, so that shifting the picture on the screen right one bit requires shifting the bits in memory left within each byte, stepping over bit 7, and from byte to byte in a left-to-right direction.

The little program called TIME, lines 1530-1660, calls the BUILD program 1000 times.  I ran it and clocked it at a little less than 24 seconds, which means building once took less than 24 milliseconds.  The tables would take up six disk sectors if they were stored part of the program on disk.  The disk spins at 300 rpm, or 200 milliseconds per revolution.  The absolute minimum time to read six sectors would be 67.5 milliseconds, but in actual practice it takes closer to a half second.  It depends on whether it is part of a larger file or stored as a separate file, the latter taking longer.  Since the program only needs to be executed once, even the memory it occupies it available to the program for other purposes.
