Munching Squares.pushem

From Esolang
Jump to navigation Jump to search


This program implements the munching squares display hack in BytePusher. This program is written in PUSHEM.

Munching_Squares.pushem =
  Helps ; (except LoopBackHelp)
  Main Loop
  Video Table

Lookup tables

Lookup tables are a simple thing to implement.

This next macro creates a small table.

The command \a skips to an aligned boundary (#FF is the bit mask for the boundary address).

The command \c creates a constant and assigns a name and value. In this case, the name is taken from the first parameter (^1) and the value is the current address (?). Now this table can be refer to by name.

The command \R #1 means "repeat once", it is a way to do a kind of trick in PUSHEM to parse a command with spaces, where ^, represents a space in a parameter, in a macro definition, and ^2 is the second parameter, which might contain spaces. These spaces are converted into splitting parameters, due to the \R.

Macros =

{ Table (name) (parameters)
  \a #FF
  \c ^1 ?
  \R #1 \t^,^2

This macro does a lookup, changing a register value according to a table (such as an increment table, to increment a register). (In case you didn't know: The \x command compiles the instruction to copy a byte, and to jump to the next instruction.)

Macros =

{ Lookup (register) (table)
  \x ^1 +#8
  \x ^2 ^1

The common tables used in this program are as follows:

Tables =

Table Increment |__MINOR #1 #1

Table CurrentValues |__MINOR #1 #0

The vertical bar allows everything else on the line to be one parameter (the Table macro then splits it into separate parameters).

When creating a table, parameters are:

  1. The base value.
  2. The value to multiply base value by
  3. The value to add to this result.
  4. The mask value, ANDed by that result (optional).
  5. (Only the least significant byte of the result is used)

The special word __MINOR tells what position in the table we are at.

Miscellaneous macros

The SetAddress macro puts a address in another position of the program. It is used for setting starting instruction address in the header. \W stores a 3-byte value, and \A changes the current address to compile into, so it works by moving there and then going back after writing.

Macros =

{ SetAddress (number)
  \c x ?
  \A ^1
  \W x
  \A x

This macro just defines a label name for the current position in the program (like many assemblers have built-in).

Macros =

{ Label (name)
  \c ^1 ?

Main program

This is the main part of the program, which is a loop that goes 256 times to update every display row.

Main Loop =

 Initialize loop start
 Fix current pixel
 Next loop iteration

The main loop will fit into the first page of memory (256 bytes).

These two registers are used to keep track of the current XOR value (basically, the frame number), and the loop counter.

Registers =

Label XOR_Value
  \B #FF

Label Counter
  \B #00

The video table is not stored in the file, but it must be created anyways:

Video Table =

\c y ?
\a #FFFF
SetAddress #5
Label Video
\A y

Initialize loop start

First step: Increment the XOR value and set the end of loop to go back to beginning of loop.

Initialize loop start =

SetAddress #2
  Lookup XOR_Value Increment ; 2 inst
  \x LoopStartHelp LoopBackAddr ; 1 inst

Fix current pixel

Second step: Fix the current pixel. It starts by clearing the current position, setting the new position, and setting the pixel at that new position.

Fix current pixel =

Label LoopStart
  SetPixel #00 ; 4 inst
  FixCurrentValues ; 6 inst
  SetPixel #D0 ; 4 inst

This macro is used twice and is used to change a pixel. Since it is twice with a different parameter each time, we can use label names with ^1 in it so that each label will be unique.

The ampersand tells it to write into a certain position in an instruction: xyz are source operand bytes (where x is least significant), and XYZ are destination operand bytes.

Macros =

{ SetPixel (color)
  \c y Increment ^1
  \x Counter x&SS^1
  Label SS^1
  \x CurrentValues X&S^1
  \x Counter Y&S^1
  Label S^1
  \x y Video

This macro fixes current values. It should be possible to understand; see the section about XOR tables to understand how it works.

Macros =

{ FixCurrentValues
  \x Counter x&F1
  \x Counter X&F3
  \x XOR_Value x&F2
  Label F1
  \x CurrentValues x&F3
  Label F2
  \x XOR_Lookup y&F3
  Label F3
  \x #0 CurrentValues

Next loop iteration

Third step: Go back to the start of the loop. The loop counter must be incremented, and then it must figure out the position to jump to, because after 256 times it has to halt until the next frame.

Next loop iteration =

  Lookup Counter Increment ; 2 inst
  FixJumpPosition ; 3 inst
\c LoopBackAddr -#1
  \j LoopStart

Some "helps" must be defined to allow copying of values into memory (that is, into the jump instruction), since BytePusher has no instructions for copying constant values, so they must be stored in RAM instead.

Helps =

Label LoopStartHelp
  \B LoopStart

Label HaltHelp
  \B Halt

This last "help" is actually a small table (with only one entry), which decides where to put the jump address. If the loop counter is not zero, it will write a part of the header which we do not use (this program doesn't use the keyboard, it is output only). If it is zero, that is the end of the loop and it must halt, which means to change the jump at the end of the loop.

LoopBackHelp =

Label LoopBackHelp
  \B LoopBackAddr

At the end, just halt.

Main Loop =

Label Halt
  \x #0 #0
  \j Halt

XOR tables

These XOR tables don't XOR all values. We can save memory by using only some values. Instead of XORing the position by each current XOR value, it it XOR the last value by a number that causes the same effect in the end.

You can see here how it works (in binary):

00000001 00000001
00000011 00000010
00000001 00000011
00000111 00000100

As you can see, XORing only these numbers (on the left) will result in the proper sequence of numbers (on the right).

The commands like \R01 are just mean which phase it should use it at. PUSHEM programs are compiled in multiple phases. (We use the \R #1 trick here again, but this time for a different reason than before.) The second time, just skip over the table, since the macro would overwrite part of the header, and the second phase will cause it to recompile the header correctly.

Tables =

\R01 #1 Create_XOR_Lookup
\R11 #1 |\A +#100

Macros =

{ Create_XOR_Lookup
  Temporary XOR lookup table
  Calculate XOR lookup table

These temporary values indicate which table corresponds to each frame number of the animation.

Temporary XOR lookup table =

WriteAt #00 #8
WriteAt #01 #1
WriteAt #02 #2
WriteAt #04 #3
WriteAt #08 #4
WriteAt #10 #5
WriteAt #20 #6
WriteAt #40 #7
WriteAt #80 #8

It must calculate which is the highest bit which is set in a value, which can be calcuated using (x&-x) (think about it!). The results are the number with only the high bit set.

Next, it must go back over the table and convert the values according to the temporary table. **+__MINOR is a sort of double-indirection to look up in this table itself, and then back to the start, at the temporary table... Whereas, >? is a way to shift right the current address, so that the table number of the tables created by Create_XOR_Tables will be stored here, instead, by adding it (since those other tables come next, just add the number to figure out where).

Calculate XOR lookup table =

Table XOR_Lookup __MINOR^,#1^,#0^,-__MINOR
\A -#100
Table XOR_Lookup **+__MINOR^,#1^,>?

Now to create the tables which actually XOR the values. There are eight of them, so it must be repeated eight times. The value y is used during compile time to count what is the next value which we are XORing by.

Tables =

\c y #01
\R #8 Create_XOR_Tables

A note about tables: If you set the address ahead, it will still create the table aligned properly, but will XOR the positions in the table!

Macros =

{ Create_XOR_Tables
  \A +y
  \t __MINOR #1 #0
  ; Set the next number y=2*(y+1)-1;
  \c y y #01
  \c y y y
  \c y y minus_one ; Any undefined value is -1


Here is a screenshot of the running program:

BytePusher Example Program Munching Squares.png