June 14th, 2013

Prince Of Persia Code Review: Part 2 (Bootloader)

I love you Hoi-en.
In order to save RAM and processing power, Apple II game developers did not use the operating system that came with the machine. As a result, they had to write their own bootloader:

Routines located in the Apple II ROM would help a lot: RWTS16 was a set of instructions that piloted the floppy disk unit and allowed to read/write 16 sectors of 256 bytes per track on 35 tracks for a total of 140kB per disk.

But games from Brøderbund did not use RWTS16. They came up with a better format: RWTS18 which allowed higher data capacity and proved to be a strong copy protection mechanism.

Part I : Introduction
Part II : Bootloader
Part III : Code explained


Traditional bootloader

Before emphasizing on what was different, here is how things were usually done in the video game industry:

Three components interacted together when the computer started :

  • Floppy disk.
  • Booting routine in the Apple ROM.
  • Floppy disk reading routines (RWTS16)in the Apple ROM.




Upon startup the Apple II would :
  1. Set its Instruction Pointer on the booting instructions in the Apple ROM
  2. The Apple booting routines used RWTS16 to load sectors from the floppy to the RAM at $800.
  3. Those sectors contained the game bootloader.
  4. The Apple II booting routines will then branch to $800.




The game's bootloader would be in charge from there to load the game engine from the floppy to the RAM:

  1. Using the Apple II RWTS16 routines...
  2. It would transfer the game engine from floppy to the RAM...
  3. and then branch to the engine.


RWTS 16


RWTS16 was the floppy disk format that came with the Apple II. It is extensively described in the gem of a book "Beneath Apple DOS". In a nutshell it consisted in a set of routines in the ROM that piloted the disk drive in order to write and read 16 sectors per track.

Sectors of 256 bytes were written on a track as in the drawing below :



Because drives lacked accuracy, huge gaps had to be left between sectors in order to allow delete/rewritten without overlaps : As you can see in the following drawing, the drive head could write a little bit before or a little bit after the "ideal" location. Gaps compensated for those inaccuracies :



RWTS 18


RWTS18 was a floppy disk format authored by Roland Gustafsson for Brøderbund. It was a complete departure from RWTS16 that not only provided more storage space: it also made hacker's work much harder.

RWTS18 higher capacity was based on a clever observation: Game distribution involved mainly reading data, not writing. RWTS18 almost dropped the concept of sectors: It wrote entire tracks and read much larger sectors.

This design allowed to remove most of the gaps RWTS16 had to put between sectors: Only the minimum XXX self-synchronizing bytes are between sectors.


As a result, RWTS18 allowed 768 byte on each 6 sectors for a total of 157 kB per disk instead of the 140 kB allowed with RWTS16.

But higher capacity was not the only asset RWTS18 provided. It also featured anti-copy mechanisms :
  • Every disk manufactured was physically difference: Data was encoded differently thanks to a nibble table that was loaded by RWTS18 at runtime.
  • Different sector Prolog and Epilog confused disk copy programs.

Note : RWTS18 did not totally drop sectors for two reasons:
  • The maximum latency to start reading a track was 1/6 revolution.
  • Developers still had a bit of granularity (a full track may have been too much data).
.
Note : Roland Gustafsson also commented the following :


When reading a track, the 18 sectors could go into 18 different pages of RAM as specified, not just sequencial reads of 18 sectors ($1200 bytes) in whatever order they were encountered... this is a method that is now used on hard disks, I believe it is called scatter-read (for me, it just seemed like a good idea at the time! :)

The self-modifying code I used allowed for 4 cycle reads instead of 6, saved 2 cycles for both reading/writing. Plus it allowed for "throw-away" reads where every sector/page was not necessarily desired. There was an API that handled the variations required. The innermost loops for reading and writing were extremely tight, in fact, the write routines needed to pre-process the data a bit before writing in one revolution. I believe it was about a 20% overhead, if I'm not mistaken.



Trivia : Roland Gustafsson was so devoted to Apple II that he made his car license plate "D5 AA 96" which is RWTS16 prologue 3 bytes marker.

.
Trivia : The source of RWTS18 was written with LISA assembler which is a tokenized file format... not just a basic text file. Roland is planning on releasing the source as soon as he find a way to extract it. If you know how to do that, get in touch with him.
Trivia : RWTS18 was so difficult to decipher that it gave birth to bizarre legends: It was originally thought that authoring RWTS18 disks required using slower disk drives.
Trivia : Hackers did end up cracking Prince Of Persia...but they had to reverse-engineer the game and write it on 3 disk formatted with RWTS16 to allow further re-distribution. The original release of POP was contained on two disk using RWTS18. Even Apple II emulators can only run the cracked version of Prince Of Persia !


Prince Of Persia bootloader


Now we have everything we need to understand POP bootloader:

POP started booting in a typical fashion: The first track was formated with RWTS16 so the Apple II boot routines would load POP bootloader in RAM.




POP bootloader would then load RWTS18 routines from the rest of track 0 using RWTS16.



The bootloader then used RWTS18 to load the game engine from the other tracks which where formatted with RWTS18.

The bootloader would branch to the game engine...which would also use RWTS18 routines to load game assets.



Interview with Roland Gustafsson

Rolans accepted to answer a few questions, here is the interview :

Fabien Sanglard : Hello Roland, can you give us some background about you: When were you born, Where did you grow up, how was school for you and how did you get to become a programmer ?
Roland Gustafsson : Born in Sweden but lived in California all my life. I did not really like school, graduated from high school, however, and was already programming and making a good living at it at age 17. (That's why I didn't go on to college, the computer classes offered back then in university weren't relevant with these new things called personal computers... this was in the late 70's)


FS : How did you end up working at Broderbund in the 80s ? How long did you stay with them. How did you get the idea of RWTS18, why did you write it ? Except for RWTS18, what else did you program at Brøderbund ?
RG : Broderbund. I was never an employee, never have had a real job, always freelancer. :)
The idea for RW18 was borne out of necessity. There were some Bank Street products (after Bank Street Writer) that wouldn't fit on a standard 16 sector disk. Having pulled rabbits out of hats before, they asked me if it was possible to come up with a way to store more data. Having worked on copy protection for years, thinking outside the box and fully understanding the capabilities of the Disk II drive, I rubbed my chin for a bit and hashed out the most efficient way I could think of. This was done on a plane to Japan, so had main hours of paper and pencil time to do so. My friend Corey Kosak was convinced he could come up with a way to store 19 sectors (the theoretical limit) but it involved math so intensive that the lowly 6502 back then would not be able to handle it. The underlying math for nibble management is essentially base 64, whereas it would be possible to store more data if you could easily work with base 78 or something like that, can't remember. The math was a bit mind-numbing. :) Base 64, of course, is child's-play for binary systems. :)

FS : How was it working with Brøderbund (working hours, salary, were people as passionate as you ) ? How would you compare that experience to today working conditions ?
RG : I have never had a real job, don't want one, not an office person. :)


FS : Did you work on prince on Persia at all ? Did you usually provide support to game developers or you just gave then the assembly source and manual ?
RG : I worked directly with Jordan Mechner implementing RW18 and the copy protection. We had lots of fun coming up with devious ways to make it difficult to copy... in some cases the game would seem to work but ultimately be unplayable. With most other games, I came in after the game was complete and added the copy protection. The exception was any RW18 program, that needed to be implemented during development phase, of course! I had a basic manual for it that was super easy to use.


FS : The book "Hackers: Heroes of the Computer Revolution" features a chapter about Spiradisc and Sierra On-Line fight against piracy. In retrospect did you consider RWTS18 to be effective fighting Brøderbund game piracy ? Did you ever study other publisher copy protection mechanism (Spiradisc)? If yes, what did you think of them ?
RG : The only other copy protection that I carefully studied was the cassette version of Microsoft's Flight Simulator. That's when I realized that copy protection existed. From that point on, I developed my own copy protection and it was rare for me to look at what others were doing. I came up with the spiral disk copy protection method myself and it was used on many Broderbund and Gebelli games. I was not aware of anyone else coming up with the 18 sector thing but heard many years later that someone either copied or came up with their own method. Still not sure on that. I know for sure I invented RW18, however. :) :)


FS : Still about fighting software piracy: Did you keep up with the opposite side techniques in order to improve RWTS18 ? Opponents can sometimes develop respect for each other skills: Were you ever impressed by what pirates were able to do (like for example pirating POP on three RWTS16 floppy).
RG : Yes, I would at least keep on top of the latest Locksmith, Nibbles Away or other software for copying and also the hardware boards. I added code to prevent hardware copy boards from working that was so thorough that Apple couldn't figure out how to get around it with their then still unannounced and secret Apple //e... so they brought one to my house so I could make it work. I had a disguised Apple //e for quite a while before it was announced and released.

Honestly, I thought the idea of creating a 3 disk version of a 2 disk RW18 game was silly and really not impressive. It would have been better for them to have created a copy-system that created exactly the same format, RW18 and just make exact copies!! The experience was MUCH better, faster, etc... :)


FS : What do you consider the greatest hack in the history of software engineering ?
RG : Nothing jumps to mind. I would say that anytime someone comes up with a surprisingly clever solution to a perplexing problem that involves inventive thinking, that's praiseworthy. :)


FS : What is your all-time favorite video game ?
RG : Even though I haven't played it for many years, the original GameBoy version of Tetris, the "networked" version playing against others. I used to play that at Broderbund competitively. :)


FS : I'm the computer industry do you have any role model, personal hero ?
RG : Steve Wozniak's insistence on publishing the source code for the original Apple II ROMs... that was essential in my learning experience. I also met him once at the Apple users group in San Francisco, I was able to talk to him enough to get details on the Disk II system that got me started on copy protection.


FS : What was your proudest moment as a software engineer ?
RG : Whenever I was able to exceed expectations, pull rabbit out of hat, etc... those were great moments. I still think RW18 is right up there as one of my best tricks.


FS : What are you working on today ?
RG : CTO at Oceanhouse Media developing mobile apps. What Apple has done with iOS and app development is truly ground breaking! We develop for the other mobile markets as well and they still have a lot of catching up to do. Yes, I'm still a huge Apple fan. ;)


Recommend readings

"Beneath Apple DOS" is a great book that describe the internals of Apple II computers. Very useful to understand RWTS16 and 6+2 translation.



Hackers: Heroes of the Computer Revolution features a chapter about Sierra On-Line and the difficult relationships with their anti-hacker wizkid responsible for Spiradisc: Mark Duchaineau.




Next

Now that we have all the knowledge we need, we can actually dive in the code: Prince Of Persia code explained

Comments

 

Fabien Sanglard @2013