Hacking the LYNX

Some people wondered how I did the pictures (and movies) I posted sylvester 2013/14 on atariage, showing some new Chips Challenge levels. Actually, that was pretty easy. For already several years there is a big community of Chips Challenge fans, but on the PC. The reason is that some ehm very big software company rerelease Chips Challenge for DOS. Funny enough they copied over some typos for the level codes... which clearly shows that they did kind of reverse engeneering the Lynx code. I will say a few more words about the differences later.

Anyway. From this big community comes not only some (open source) clone of Chips Challenge, but also some editors and utilities to convert the levels back and forth. And this utility is able to read the Lynx ROM as well as write to it! But how was that possible, I thought that all Lynx ROMs are encryped and checksummed? Well, not all. Chips Challange uses some old loader which is encrypted, but doesnt do checksumming of the ROM. For that reason one can just edit the level files.

Making long story short: There was already a working (perl) script (from Brian Raiter, see links below) which was modifing Lynx ROMs, called c4. Beside that it didnt want to modify my ROM dump because it was very picky on the ROM name. A very good reason to have a closer look at the script.

(Remark: Yes, its a perl script. See my final remaks at teh bottom).

Found quickly a few things the script can not do: Change the level codes. Change the number of levels. Bad. Lets dig deeper into the details. Checking the rom and looking for the codes does not reveal anything. Checking the files reveals that all but the first are packed. Yeah. Fun. Even the level files are packed. Could it be ... ? The script extracts levels from original ROM for editing on PC and can write edited levels back to ROM. But the level files are packed by a simple algorithm. And the same packer is used for all (but the first two files) in the ROM. Thus c4 features the corresponding packer and depacker. But it works not for all files. c4 relys on fixed offsets in the ROM. An the check for the correct rom is overstrict. It claims to handle lnx and lyx, but checks only for lnx header. The number of levels is fixed to 150 (by cc code), while the last level has to be a dummy which plays the extro. If c4 wants to copy in less levels, it fills up to 150 with dummies. Also level codes are hardcoded in CC and can not be changed so easily. Note: This only works because CC is using the "old" epxy loader which is not checksumming the whole ROM.

O.k. so what? We want to get rid of the 149 level limit and use our own level codes! For that we have to disassemble the main code, find the table with the level codes and check where the maximum number is checked. Easy. Lets start with that.

The directory contain 172 files. I indexed them starting at 0.

The what is what comes from some educated guessing about the files sizes and typical ROM layouts as well has the knowledge from the c4 script. O.k. as file 1 is not packed, I could disassemble it and check what it is doing.

Before, lets have a short look at the title picture. On the first look, it it just a simple sprite like in all other games. But if you have a closer look at its structle, I noticed its composed of several sub-sprites. Thus it contains a chained list of four sprites. The chip background is one sprite and each of the text lines another.

Back to work. I mentioned that file 1 is not packed, well it cannot be, because the EPYX loader has to load it. So, lets have a look inside: First, I checked where cartridge access is be done. Then I traced back these functions. It helps a lot that the code is similar to the cart reading code in other games. After some commenting and renaming you find the following.

;;; init code missing
	JSR LoadFileEntryNr2_to_1c6e	
	LDA #$0e	; Load File 16
	JSR LoadFileEntryPlus2_to_b600	
	JMP L1C6E	; Jump to File #2 loaded above

LoadLevel:
	JSR LoadLevelNrTo_0c00	
	LDA $0c00	
	CMP #$ff	
	BNE level_ok	; *+5	
	JMP $819a	; Play Extro?
level_ok:
	JMP $4548	; Play Game
	CLC		
	ADC #$11	
	JSR SelectFileEntry	
	LDX #$00	
	LDY #$90	
	JMP LoadAndDepackToAddrXY	

LoadFileEntryPlus2_to_b600:
	CLC		
	ADC #$02	
	JSR SelectFileEntry	
	LDX #$00	
	LDY #$b6	
	JMP LoadAndDepackToAddrXY	

SelectFileEntry:
	JSR L1BDE	
	JSR L1AAA	
	RTS		

LoadFileEntryNr2_to_1c6e:
	LDA #$02	
	JSR SelectFileEntry	
	LDX #$6e	
	LDY #$1c	
	JMP LoadAndDepackToAddrXY	

LoadLevelNrTo_0c00:
	LDA $0A		; Level Nr in $0A
	CLC		
	ADC #$16	; +22
	JSR SelectFileEntry	
	LDX #$00	
	LDY #$0c	
	JMP LoadAndDepackToAddrXY	

LoadAndDepackToAddrXY:
	; ...

This looks extremly good. We found out that there are special loading routines for file 2, file 3 up and the levels. Different file types are loaded to different adresses in memory. And we found the location of the level number. We also see a check of the first byte of the loaded level. This is the place where a a check for a valid level is made. What we miss is a special code for loading the fractal easter egg (we will find it later). Next after this code come the following section. Uh-uh thats the unpacking code! O.k. we wont need to understand it as its already in c4. Anyway we are not interrested in the loader, but we want the level codes. Thus we next depack file 2 and reassemble it. For that I had to take over the depacking code from c4 to a seperate script. Run it and ... it didnt work! It tried to write out a file with 100kb size. A bit large for the Lynx memory. Thus lets check what the depacker is doing. The first four bytes are threated as 16 bit tablelen and 16 bit datalen. Sound reasonable. Then the table is loaded, and after that the data. So far so goot. After a bit of testing it turned out that several files cannot be depacked. All of them have a tablelen >255 while all files with tablelen<256 are working o.k.. Needless to say, the level codes could not be found in any of the unpackable files. To find out why depacking is going wrong, lets check again the Lynx unpacker code and try to find out whats going on...

LoadAndDepackToAddrXY:
	STX $00		
	STY $01		
	;; select block or set dir/dat code removed
	LDA #$ff	
	SEC		
	SBC LoadingLengthLo	
	EOR #$ff	
	STA SomeLengthLo	
	LDA #$01	
	SBC LoadingLengthHI	
	EOR #$ff	
	STA SomeLengthHi	
Clean0700DepackTable:
	LDX #$3f	; Clear some table???
CLEAN_TAB_LOOP:
	STZ $0700,X	
	STZ $0740,X	
	STZ $0780,X	
	STZ $07c0,X	
	DEX		
	BPL CLEAN_TAB_LOOP	; *-13	
	JSR ReadOneByteToA	
	STA $07		; TableCntLo
	JSR ReadOneByteToA	
	STA $06		; TableCntHi
	JSR ReadOneByteToA	
	STA $08		; DataCntLo
	JSR ReadOneByteToA	
	STA $09		; DataCntHi
	LDA $07		
	BEQ L19FF	; *+38	
	LDX #$01	
ReadDepackTable:
	JSR ReadOneByteToA	
	STA $0600,X	
	TAY		
	LDA $0700,Y	
	STA $0800,X	
	TXA		
	STA $0700,Y	
	JSR ReadOneByteToA	
	STA $0400,X	
	JSR ReadOneByteToA	
	STA $0500,X	
	INX		
	DEC $07		
	BNE ReadDepackTable	; *-32	
L19FF:
	INC $09		
	INC $08		
L1A03:
	DEC $08		
	BNE ReadATo0700	; *+54	
	DEC $09		
	BNE ReadATo0700	; *+50	
	LDA $06		
	BNE Clean0700DepackTable	; *-91
	
	LDA SomeLengthLo	
	CLC		
	ADC #$00	
	STA LoadingLengthLo	
	LDA SomeLengthHi	
	ADC #$02	
	STA LoadingLengthHI	
	;; select block or set dir/dat code removed
	LDX $00		
	LDY $01		
	RTS		
ReadATo0700:
	JSR ReadOneByteToA	
	TAY		
	LDX $0700,Y	
	BNE L1A6C	; *+42	
L1A44:
	STA ($00)	
	INC $00		
	BNE L1A4C	; *+4	
	INC $01		
L1A4C:
	LDA $07		
	BEQ L1A03	; *-75	
	DEC $07		
	PLX		
	LDA $0500,X	
L1A56:
	STX L1A60	; self-modify code!
	TAY		
	LDX $0700,Y	
	BEQ L1A44	; *-25	
L1A5F:
	CPX #$ff	;; missing label L1A60 ! self-modify code!
	BCC L1A6C	; *+11	
	LDA $0800,X	
	TAX		
	BNE L1A5F	; *-8	
	TYA		
	BRA L1A44	; *-38	
L1A6C:
	PHX		
	LDA $0400,X	
	INC $07		
	BRA L1A56	; *-28	

ReadOneByteToA:
	PHX		
	PHY		
	LDA CART0	; $fcb2
	PHA		
	INC SomeLengthLo	
	BNE L1A97	; *+26	
	INC SomeLengthHi	
	BNE L1A97	; *+21	
	INC L1A9F	
	LDX L1A9F	
	JSR L1BA2	
	LDA #$00	
	STA SomeLengthLo	
	LDA #$fe	
	STA SomeLengthHi	
L1A97:
	PLA		
	PLY		
	PLX		
	RTS

Shit, that looks complicated. And it uses self modifing code. And it used the stack for something. Terrible. This is hard to translate back to sme high level understanding (or language). After some staring at it I found that at some point a new table is loaded. But only a part of the tables is cleared in advance. Hard to judge what exactly is done here. I decided to put the code in some test program to watch the decoding. Would be much easier if there would be a reasonable debugger on the Lynx (emulator). Anyway, lets translate the code line by line to a C program. Put some prints in and watch. Hmm the C code does not work, too, something went wrong. But wait: Now I see how a second table is fetched, then the data length is counted down to zero and the next table is fetched. Depending on the second byte in the header. Aha! This is not a 16 bit word of table length (which would not be possible with the indexing on the Lynx anyway!) but is a flag which tells me that another data chunk is following the current one. Now lets change the c4 code to repeat the decoding after it ran out of data. And yes!!!!! It works. The data blocks are completly independent of each other. Readable text (after adding 53 to the bytes to get them to ASCII) until the end of file. Intro text, extro text, menu text. This looks good. Now lets reassemble file 2. Ah that looks better. Readable code.

But, no sign of the level codes. That sux. Lets do it the hard way. Check where the JOYPAD is read. Several times. Hm. O.k. lets take the debugger and trace the the code entering screen. Thats not as easy as its sounds, as all the time the animation is played in the background. But, after some time I found the correct location.

FractalCode:
	dc.b $18,$0c,$19,$0f	; MAND
ReadJoyPad:
	LDA JOYPAD	; $fcb0
	CMP JOYPAD_VALUE	
	STA JOYPAD_VALUE	
	BEQ L38AA	; *+7	
	STZ L3882	
L38A8:
	CLC		
	RTS		
L38AA:
	INC L3882	
	LDX L3882	
	CPX #$01	
	BEQ L38BD	; *+11	
	CPX #$0a	
	BNE L38A8	; *-14	
	LDX #$07	
	STX L3882	
L38BD:
	SEC		
	RTS

Touche, and right above that code, the fractal easter egg code. Things would be easier if I would have directly looked for that. O.k. Now from where is this function called? Ah, right ahead:


	JSR ReadJoyPad	; return in A, Carry says if pressed
	BCC NoKeyProc_L384C	; *+79	
	TAY
	BIT #$20	; Right?
	BEQ NoRight_L3811 ; *+15	
	INC CodeSelectPosition_L3884	
	LDA CodeSelectPosition_L3884	
	CMP #$04	
	BNE NoRight_L3811	; *+5	
	DEC CodeSelectPosition_L3884	
NoRight_L3811:
	TYA		
	BIT #$10	; Left
	BEQ NoLeft_L381E	; *+10	
	DEC CodeSelectPosition_L3884	
	BPL NoLeft_L381E	; *+5	
	INC CodeSelectPosition_L3884	
NoLeft_L381E:
	TYA		
	BIT #$03	; Any Button?
	BNE CodeButtonsPressed_L3852	; *+49	

	BIT #$40	; Up
	BEQ NoUp_L3837	; *+18	
	LDX CodeSelectPosition_L3884	
	LDA CodeString_L268B,X	
	INC		
	CMP #$26	
	BNE L3834	; *+4	
	LDA #$0c	
L3834:
	STA CodeString_L268B,X	
NoUp_L3837:
	TYA		
	BIT #$80	; Down
	BEQ NoKeyProc_L384C	; *+18	
	LDX CodeSelectPosition_L3884	
	LDA CodeString_L268B,X	
	DEC		
	CMP #$0b	
	BNE L3849	; *+4	
	LDA #$25	
L3849:
	STA CodeString_L268B,X	
NoKeyProc_L384C:
	JSR L30D8	
	JMP L37AF

Ah yeah, that looks exactly like some select code code, left/right changes an index, up/down changes values and check under/overflow. Now lets follow what happens if A/B are pressed.

CodeButtonsPressed_L3852:
	JSR CheckForFractalCode_L3885	
	LDX #$00	
CodeCompareLoop_L3857:
	LDA CodeString_L268B	
	CMP $1280,X	
	BNE CodeCompareWrong_L3877	
	LDA L268C	
	CMP $1380,X	
	BNE CodeCompareWrong_L3877		
	LDA L268D	
	CMP $1480,X	
	BNE CodeCompareWrong_L3877		
	LDA L268E	
	CMP $1580,X	
	BEQ CodeCompareFound_L387D		
CodeCompareWrong_L3877:
	INX		
	CPX #$95	; Number Of Levels !!!
	BNE CodeCompareLoop_L3857		
	RTS		
CodeCompareFound_L387D:
	STX $0A		; Level Number found in $0A
	STZ $46		
	RTS		
L3882:
	dc.b $00	
JOYPAD_VALUE: 3883
	dc.b $00	
CodeSelectPosition_L3884:
	dc.b $00	
CheckForFractalCode_L3885:
	LDX #$03	
L3887:
	LDA CodeString_L268B,X	
	CMP FractalCode,X	
	BNE L3895	
	DEX		
	BPL L3887	
	JMP LoadFractal	
L3895:
	RTS		
FractalCode:
	dc.b $18,$0c,$19,$0f	; MAND

O.k. Now we know that the code table is located at $1280 and 4*256 bytes long. Much larger than needed. But when and where is this table filled? Lets look where this address is used, too.

UnpackgenerateCode_L1D08:
 	LDX #$00
 	STZ $44
 	STZ $45
LoopGenerateCode_L1D0E:
 	JSR GenerateCodeFunk1_L1D3C
 	STA $1280,X
 	JSR GenerateCodeFunk1_L1D3C
 	STA $1380,X
 	JSR GenerateCodeFunk1_L1D3C
 	STA $1480,X
 	JSR GenerateCodeFunk1_L1D3C
 	STA $1580,X
 	DEX
 	BNE LoopGenerateCode_L1D0E
 	JSR GenerateCodeFunk1_L1D3C
 	STA $12e1
 	JSR GenerateCodeFunk1_L1D3C
 	STA $12ea
 	JSR GenerateCodeFunk1_L1D3C
 	STA $12f1
 	RTS

GenerateCodeFunk1_L1D3C:
 	JSR GenerateCodeFunk2_L3BDC
 	AND #$1f
 	CMP #$1a
 	BCS GenerateCodeFunk1_L1D3C
 	ADC #$0c
 	RTS

And at some other position in the code:

GenerateCodeFunk2_L3BDC:
	LDA $44		
	LSR		
	LSR		
	SBC $44		
	LSR		
	ROL $45		
	ROR $44		
	LDA $44		
	EOR $45		
	RTS

Gotcha, the codes are created by some pseudo random generator. One function checks the limits (A to Z). And after the table is filles, three values are modified afterwards. Anyway, this proves that the codes are not editable... so easily. So what can we change to make the codes editable? We load them from ROM! We "just" have to replace the generator code above with code which loads from a file to address $1280. And hey, as we can see above how to do that! After loading we have to write the number of valid levels (which is stored as last byte in that table) and modify the code which checks the maximum level in the code selection part. Now fill up the code with nops or zeros to the same length. Et voila!

A reminder about the code table format: 256 bytes first letter of code, 256 bytes second letter and so on. The last byte is overwritten by the number of levels (codes) in use. Altogether 1024 bytes. As CC can only load packed files, we have to pack the code table with the algorithm provided by c4. No problem so far.

And now assemble the source back to an executeable. Run lyxass and .... a lot of missing labels. Shit, what happend here? Maybe the disassembler ran out of labels? Checked the code, 1000 allowed labels, and there should be warning if this is exceeded. Anyway, lets increase it. Compile, run, no change. After searching for an hour I remembered how the disassembler decided about the labeling... by some kind of iterative way it decides if a byte belongs to code or data. And onyl if its code, it can decipher labels from it. Ai, the number of iterations is to low! Increased the number and ah, the number of missing labels went down to a handful. Checked them. O.k. they belong to some self modifing code. This is something the disassembler cannot handle. Fine. Fixed that. Now lets assemble again and ... fail. Lyxass reports missing labels. But the labels exist in the source code? Strange. Maybe the numer of labels in lyxass is exausted? Lets increase the defines there. Again: Better! But still missing labels. Seems lyxass is not including the file where they are defined (but why?). O.k. do the easy way, copy them over. Now it reports error "no RUN adress". But heck, there is one RUN! Somethings is fishy here. Digging a bit deeper. Seems that the table with the atoms for the parser is slightly overwritten. And "RUN" is the first entry in that table. O.k. lets add some dummy data in front of the table. And yeah, it worked. Ok now check that the size of the binary is identical to the original (if not, absolute addresses would have been changed). Yepp, it is. Now I have to pack the file as the lynx loading code is not able to handle unpacked files. Maybe it would have been easier if I fixed that earlier. Too late. Now lets use the packing code from c4. As expected: table full. How do I have to change the code to create a new table before the old runs over? But wait. The data chunks are independent of each other. That means, I can pack parts of the file and put the output just behind each other. Just remember to set the flag in the header for all but the last data chunk. Now lets split the file and pack the parts. Seems that depending on the position within the file 1300 to 2300 bytes of data will fill up the table. But finally, I managed to get some 16 pieces of packed data and put them together.

Now the last part: build a new cartridge ROM image. Thats easy using lynxdir. But lynxdir does not support the 512 bytes EPYX loader. Thus we have to create a second directory for the loader. But thats easy. Parameters 512 bytes/block, Hacked 410 bytes loader. Old title picture, CC loader (file 1), then move to offset 512 for the second directory. As said, I need place for an entry for the new codetable. Lets use entry 0 here. Entry 1 will be a dummy copy of entry 1 in the first directory. And then comes the modified main code to entry 2. After that we just put all the other files from the original ROM. The fractal generator is not needed. Thus we replace it by some dummy entry. (We could have put the codetable here, too but heck, i decided otherwise. For now.) Making the long story short: Run lynxdir, fire up mednafen and ... title picture ... intro ... text ... code selection screen. Juhuu, there is the new code for level 1 as default. Lets check if it can be played. Yes. Check some other codes up to the number of levels set in the new codetable, everything works. Codes above that number are not recognized. Try fractal generator code. No effect, good.

Mission accomplished.

Whats next? Well lets see how many levels one can really squeeze inside. 256-22=234 should be the maximum possible, give or take one. Maybe if one removes some directory entries (fractal, intro, extro) one can gain a few more. Anyway they will not fit into the cartridge with the current packing scheme. But wait! Did I have a packer with 10-20% better performance? Thus if I replace the depacker code (that should be easy!), we can get more space. We could use a smaller loader which doesnt need the title picture.

Buts thats for another story.

O.k. now how can we get that working for everybody? Esp as due to copyright reasons one connot distribute any code or part of the ROM image. Lets assume that c4 is already a very clever piece of code. It only patches an existing ROM. Lets follow that path. Improve c4 to process the Lynx directory, unpack the main code, patch the unpacked code and repack it. Dont forget to extract the level code automatically and add them to the ROM image as well as the number of levels which are contained in the ROM. Maybe a few improvements like level skipping etc. Sound easy. Is easy.

Repacking everything with pucrunch instead of the simple packer would require an external binary in addition to the c4 perl script and to replace (=patch) the loader code. I think I leave that for another holiday.

So what did we archieve? We improved the c4 script to accept more than the original 149 levels. We replaced the passwords. The fractal is gone and leaves more space for levels. We cheated a bit and can now skip levels after a user defined number of tries. Skipping levels in the code selector as well as within the game are now supported. Nice!

Can we now create our user defined ROMs? Yes. But we cannot publish them. But we can use the public available level (hundreds!) to create our own ROM for flash card use. The main problem now are the levels themself. They are made for the PC copy of Chips Challenge. And this differs from the original Lynx version. Not only that they made some typos in the level code list and replaced the ending sequence. No! They made the gameplay buggy (=didnt use the original code?). And as the levels are created for the PC version, they might not work on the Lynx version. These levels might even crash the Lynx, for example if they do not contain a boarder around the playfield. There are limits on the number of enemies, some unsupported tiles and so on. Thus you have to carefully select and test play the levels.

Never heard of perl? Never used a command line? You dont like perl? You have a W***** PC and do not know what to do with the script? O.k. you can try to Strawberry perl. But then you have still the command line ...

Ah, you want me to help you? Maybe write a GUI version? Forget it! Sure, you can contact me for donation details, but I dont think that enough people will donate to change my mind.

And no. I wont create ROMs for you. Dont even ask.

Tile World, c4: http://www.muppetlabs.com/~breadbox/software/tworld/

Newsgroup: http://chips.kaseorg.com/newsgroup/

Forums: http://cczone.invisionzone.com/

The pages contain links to thousands of CC levels.

Chips Challenge - Hidden Chips

Another Story

Final Words

Perl

Links