==ARX: More compact than an LFSR==
A lot of modern cryptographic research looks at a type of operation called “add-rotate-xor” (where “xor” means “exclusive or”), or ARX for short. For example, the SHA-3 finalists Skein and Blake are both “ARX” ciphers.
Since the 6502 supports both modulo addition and xor (with the mnemonic “EOR”), as well as one-bit rotates, we can compactly implement an 8-bit ARX in 6502.
The one I tried out is like this for the forward function:
uint8_t xar(uint8_t r, uint8_t a, uint8_t b) {
int y;
for(y = 0; y < 3; y++) {
// 12 bytes in 6502
r ^= b; // lda r ; eor #b
r += a; // clc; adc #a; sta r
r = (r << 1) | (r >> 7); // asl ; rol r
}
return r;
}
And like this for the inverse function:
uint8_t rsx(uint8_t r, uint8_t a, uint8_t b) {
int y;
for(y = 0; y < 3; y++) {
// 14 bytes in 6502
r = (r >> 1) | (r << 7); // lda r; lsr ; ror r ; lda r
r -= a; // sec; sbc #a
r ^= b; // eor #b ; sta r
}
return r;
}
There are some 40 different possible values for a and b that give us a full permutation: All 256 possible 8-bit values are seen. The constants I used for my alternate 256-location Pitfall map are, in decimal (a=3;b=11). I carefully tweaked the map to be solvable in about the same amount of time as the original Pitfall map.
Not only are there 40 possible 256-location jungles, there are a total of 2,176 different possible (a,b) values where:
- One can grab all 32 treasures
- The default player’s start is can reach these 32 treasures
Note that the above code runs the ARX loop three times; this is because my experiements show that a single ARX iteration doesn’t make a sufficiently random-looking map (the “diffusion” is poor). Some of the map lengths, such as 255, will need to use a different number of iterations besides three (since 255 is 3 * 5 * 17). The most number of times this loop would have to be run is can be as high as seven for the 16 240-length maps; fortunately, there appear to be enough cycles leftover during the vertical blank to do this (and even enough cycles to run it 21 times for the underground passages in the 16 240-length maps).
The smallest jungles using this ARX generation technique with all treasures are 125 locations in size—under half the size of Pitfall’s original jungle. One of these values, again in decimal, is (a=16, b=10). I have made a special easier training version of Pitfall where the jungle is replaced with this smaller, easier 125-location jungle.
I have increased the player’s time limit from 20 to 60 minutes in this jungle, have given the player 60 instead of three lives (the player just loses a minute of time every time they die; if they die with under a minute left, the game ends), and have removed all of the underground walls.
Since the main map is only 125 locations in size, I looked more closely at the random number generator when given (a=16, b=10) and discovered there are 19 other jungles available, albeit without treasure, with these constants; one can enter one of those jungles by simply changing the location Harry is in.
I have taken one of those 19 jungles and have converted it in to a one-minute challenge course for Harry to run through. This other map can be entered by hitting “game Select”. It places Harry in a small training course suitable for practicing movement and jumping. The goal is to get to the right end of the course within a minute. This training course discourages bad habits by being more deadly: Touching a log or falling down ends the run. Harry is not allowed to run left from the starting line; no underground shortcuts may be used or the player has to start over.
These changes do not affect the gameplay of the main jungle. Along with the other easier jungle, this allows people to train for Pitfall with either a medium sized easy-to-play jungle, or a small very difficult to play jungle.
The way I was able to pull off these changes is because removing the code to process underground walls gave me just enough room to implement this obstacle course.
These files can be downloaded here:
http://samiam.org/pitfall==Galois LFSR==
Thomas Jentzsch pointed out to me that we can even more compactly represent a LFSR in 6502 by using a “Galois” LFSR instead of the “Fibonacci” LFSR that David Crane used for Pitfall. This is extremely compact in 6502:
lda random
lsr
bcc .skipEor
eor #$d4
.skipEor:
sta random
Its inverse is equally compact:
lda random
asl
bcc .skipEor
eor #$a9
.skipEor:
sta random
Code that can run both the forward and inverse Galois 8-bit LFSR in C:
uint8_t lfsr(uint8_t random, int taps, int direction) {
uint8_t c;
if(direction == 0) {
c = random & 1; random >>= 1;
} else {
c = random & 0x80; random <<= 1;
taps <<= 1;
taps |= 1;
}
if(c != 0) {
random ^= taps;
}
return random;
}
Valid “taps” values are: 0x8e, 0x95, 0x96, 0xa6, 0xaf, 0xb1, 0xb2, 0xb4, 0xb8, 0xc3, 0xc6, 0xd4, 0xe1, 0xe7, 0xf3, and 0xfa. I chose 0xd4 because it appears to generate a jungle that can be finished in 20 minutes, just like the original Pitfall jungle.
==A comparison of RNG techniques==
David Crane’s code used up 31 bytes total, for both the forward and inverse LFSR. The ARX code uses 26 bytes, five bytes smaller, and has many more solvable jungles than the LFSR code. A Galois LSFR is the most compact, using only 18 bytes.
ARX number generators as well as Galois LFSRs are random number generation techniques unknown to David Crane when he developed Pitfall (to be fair to Crane, ARX did not become popular until the mid-’00s, and Galois LFSRs probably were not widely used back then); they allow Pitfall to have some interesting alternate jungle maps.
I will mention one more time a couple of downloads for alternate Pitfall maps:
http://samiam.org/pitfall/
To post a comment about an entry, send me an email and I may or may not post your comment (with or without editing)