Tuesday, May 2, 2017

Retrochallenge 2017 RC2017/04 Introduction and Wrap Up

Introduction:

When the Enigma Z30 program project started, the final program size was a big unknown. 

The Atmel Atmega 328 used in the Arduino Pro Mini, which the KIM Uno uses has 1kB of EEPROM space. This is visible in the KIM-1 monitor from address 0400 to 07FF  

The KIM Uno had been used in a Hackaday project and already had a couple of programs at 0400, so the Enigma program was started at address 0500, RAM variables at 0050. Version 1, at 703 bytes, occupied the space from 0400 to 06BF. 

Initially, the program only supported lever stepping. This stepping mechanism has a double stepping anomaly. When any of the 3 right wheels show a 9, that wheel and the one to its left is incremented. The following sequence shows how a 9 is propagated through the rotors: 8888->8889->8890->8901->9002->9003. Since a lot of numbers are skipped, the actual machine period, the number of unique combinations between 0000 and 9999 is 8100. 

After reading the Enigma Z30 page at the cryptomuseum and realizing there were two different models of the machine, the decision was made to add gear stepping to the simulator. Gear stepping behaves like a car odometer and no numbers are skipped in between 0000 and 9999. 

Adding gear stepping to the program increased it in size slightly. The problems started with the built in menu system used to change the machine settings.

The enigma program detects when RAM contains the value of 0 and it initializes it with the default machine settings of rotors, 1,2,3 ring settings 1,1,1,1 and initial rotor positions of 4,3,2,1. Those values can be found in RAM starting at 0050 and can be manually edited to change the machine settings. Once the enigma program is started, it can be stopped and the RAM settings edited. The program can be restarted and it will encrypt with the new settings. 

A separate menu program was developed to make the process of changing the settings easier. The enigma program does not use the [A],[B] and [GO] keys. A few instructions in the key reading loop detect whether those keys have been pressed and it jumps to special locations in the enigma program. By default those locations contain a jump to the beginning of the key reading loop. When additional code is written, a jump can be inserted in those locations transfering control to the new code. The [GO] key vector has been initialized with a jump to the RAM variable initialization code and serves to zeroise the machine settings to their default values. A quick keypress can erase the current machine settings and prevent others from getting their hands on a machine with actual encryption keys.

The menu system was designed to re-use the enigma program code that changes the rotors. The first thing is must do is backup the rotor values to a temporary space in RAM. Then the desired settings to be changed can be copied to the rotor memory locations, read a keypress and decide what value to change, overflow conditions must be handled, for example, pushing up on rotor 3, selects rotor 1. 

Pressing the [B] key copies the settings from the rotor memory location to their actual location and copies the next settings to change to the rotor addresses. Any error checking must happen at that time, for example, the rotor settings must use rotors 1,2,3 in any order exactly once, 132 is a valid combination, 133 is not. 

Finally, pushing [B] restores the rotor values from temporary space to their correct memory location and jumps back to the enigma program.

The code sequence was: copy values out, copy values in, read key and handle increment / rollover, jump value checking if [B] is pushed, return to loop if invalid, jump to next setting.

Doing some copy and paste programming, the program quickly filled out the space from 06BF to 07FF. This was a problem, space below 500 had to be found to finish writing the menu system.

This was the initial driving force to optimize the program. Version 2 grouped some of the menu code into routines and with some other optimizations the program, now with dual gear and lever stepping and a menu system with a new step to select the gear mechanism, occupied the space from 0400 to 06CA. This was only 11 bytes more than V1 for a lot more functionality.

V2 was ready in time for arbitrary deadline of March 31 2017, the starting date for the Vintage Computer Festival East

The retrochallenge 2017/04 started that weekend and the idea was born to enter the contest with the goal to further optimize the program so it would be smaller than 703 bytes. 

Techniques:

The program was updated as it was being optimized and debugged.

1) Group temporary variable initializations to avoid having to load registers twice. 
i.e: if TEMP1 and TEMP2 are going to be used right away, but TEMP6 will be used further down in the code, initialize it when A has the desired value of 0. 
LDA 00
STA TEMP1
STA TEMP2
STA TEMP6
2) If an algorithm, ALWAYS sets a register to a certain value and that value is needed later, there is no need to initialize the register.
i.e: 
LDA 00
CLC
ADC *TEMP03 ;will have 0 or 1
ADC *TEMP04 ;will have 0 or 1
ADC *TEMP05 ;will have 0 or 1
CMP #$03
BEQ SETUOK
...
SETUOK ; A is NOW 3
3) Ensure the majority of the instructions are 2 bytes. Use RAM variables in page 0 when appropriate. If base+indexing instructions are used, prioritize the use of the X register for indexing 

This function was rewritten so the instructions that use $F8 index with the X register (3 instructions (F8,x) @ 2 bytes + 2 instructions (ROTORS,Y) @ 3 bytes = 12 bytes) vs (3 instructions (F8,Y) @ 3 bytes + 2 instructions (ROTORS,X) @ 2 bytes = 13 bytes).
One byte saved is one byte earned.

05C0        LDY #$00        A0 00
05C2        LDX #$03        A2 03
05C4 SHOWND
05C4        LDA ROTORS,Y    B9 57 00
05C7        ASL A           0A
05C8        ASL A           0A
05C9        ASL A           0A
05CA        ASL A           0A
05CB        STA *$F8,X      95 F8
05CD        INY             C8
05CE        LDA ROTORS,Y    B9 57 00
05D1        ORA *$F8,X      15 F8
05D3        STA *$F8,X      95 F8
05D5        INY             C8
05D6        DEX             CA
05D7        BNE SHOWND      D0 EB

4) Fallthrough was used a couple of ocassions when two functions (A and B) are called one after the other, the return instruction in the first function is eliminated and control allowed to fall through to function B. Function B returns to the caller. Doing this saves 3 bytes for the call instruction in the calling loop and one byte for the return instruction, for a savings of 4 bytes.

...
call A
call B
...
Entry Point A
...
Return to Caller
 
Entry Point B
...
Return to Caller
 
vs: 
...
call A
...
Entry Point A
...
Entry Point B
...
Return to Caller

5) The SHOWEN routine that mixes the rotor values into the correct memory locations for the monitor display routine was modified to also call the KIM-1 display and readkey routines after realizing that both the main loop and the manu loop called SHOWEN and inmmediately called SCANS and then GETKEY. This saved 6 bytes in the menu code. Control to GETKEY is transferred with a jump instead of a call, the return instruction in GETKEY will return to SHOWEN caller, saves the one byte return instruction in SHOWEN

;REM_SUB_SHOWENIGMA
SHOWEN
;copy rotor values (ROTOR,X) into correct place for SCANS (F8,F9,FA)
JSR SCANS
JMP GETKEY ; this is a jump, so the return
NOP ; this was a Return to Caller that can now be eliminated

6) Loop Unrolling: sometimes its shorter to write a loop, sometimes it is better to unroll the loop into a series of repetitive instructions. Sometimes, the same code has to be written twice to select the shorter version. The code below used to be in a fancy loop. It was shorter and clearer to rewrite it the following way. This detects any combination of 1,2,3 at memory location $58 by creating a hash table at TMP02+X containing 1, if rotor X, with X being 1,2,3 was used, 0 if not. This is also a huge buffer overrun, writing 1 to arbitrary memory locations in page 0 depending on the value at LROTOR, MROTOR or RROTOR. The program ensures those memory locations will only have the values 1..3. The only way to exceed those values is through direct memory manipulation, and at that point, any location can be changed, so the only way to experience it is to already have full memory access.

0727        LDA #$01        A9 01
0729        LDX *LROTOR     A6 58
072B        STA *TMP02,X    95 5F
072D        LDX *MROTOR     A6 59
072F        STA *TMP02,X    95 5F
0731        LDX *RROTOR     A6 5A
0733        STA *TMP02,X    95 5F
0735        LDA #$00        A9 00
0737        CLC             18
0738        ADC *TMP03      65 60
073A        ADC *TMP04      65 61
073C        ADC *TMP05      65 62

7) Instead of writing code in the menu system to rollover the rotor values at 1,2,3 instead of the full 0..9, a generic routine was written that will rollover/under at any point. Once the F3 menu was added and restricted to 0..1 to select gear or lever stepping, this generic routine saved 2 bytes from the total program size. 

Wrapup:

Implementing all of the previous techiques, the total program size was reduced to 679 bytes, 24 bytes less than v1. 

Further optimization could concentrate on reducing the number of 3 byte instructions. This can be accomplished by changing all the jumps (3 bytes) to conditional jumps (2 bytes). To do that, the program needs to be analyzed so a flag that is constant at that point in the program can be used, maybe the overflow flag is a good candidate.

Also, any tables in program space can be moved to page 0 so that a two byte page0+X index instruction can be used instead of a three byte absolute+x index instruction. This modification increases RAM consumption in order to reduce program size. 

Below is the breakdown in enigma algorithm vs. menu system program sizes for each version. Version 3 has an enigma engine that is 1 byte bigger, but it enables a significantly smalled menu, for a smaller total size. This byte can be saved by changing the loops to use 2 byte conditional jumps

v1: enigma 460 menu 243 total 703
v2: enigma 451 menu 263 total 714
v3: enigma 452 menu 227 total 679
 

Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away. Antoine de Saint-Exupery