Analysis of source code and copy protection Prince of Persia

Transfer

Part 1: Introduction

On April 17, 2012, Jordan Meckner published the source code for Prince of Persia.

Even though this is a version for Apple II written in assembly language of the 6502 processor, it was very nice to dive into the code of this legendary game. As usual, I was waiting for a lot of software interests.

Obviously a weak programming environment for games, the Apple II was in fact the foundation of incomparable innovation and creativity: self-modifying code, an internal bootloader, smart floppy disk format, and offset search tables. In each of its modules, Prince Of Persia stores the treasures of engineering.

Reading the source code allowed me not only to learn more about the game development process in the 80s, but also again aroused a sense of appreciation for those things that are today considered natural.

As usual, I kept detailed notes and based on them created this article. I hope she inspires others to read the source code and improve her development skills.

Acknowledgments: I want to thank Miles.J with 6502.org and Roland Gustafsson (author of RWTS18) for sharing their knowledge with me.

Where to begin?

The source code is available in the repository on GitHub and can be downloaded with one command:

git clone git://github.com/jmechner/Prince-of-Persia-Apple-II.git

The interesting part is in the folder /Prince-of-Persia-Apple-II/01 POP Source/Source/that contains the game engine made up of many files .S.

This is the first thing that programmers did not have at that time: high-level languages with high-quality compilers. To achieve good speed, the developers had to work directly with the hardware in assembly language 6502. It is from this that these files consist .S.

According to Jordan Meckner's book Making of Prince of Persia , Merlin assembler was used in PoP.

One of the good features of Merlin is a directive ORGthat allows you to tell the assembler where instructions will be loaded into RAM: in PoP, it ORGis at the beginning of each file.

Interesting fact: directivesORGwere really just indications. Apple II had neither an operating system, nor a linker or bootloader: the developer himself had to somehow manage to transfer instructions from the floppy disk to the right place.

The second important point that needs to be understood in order to understand PoP in general is the way information is exchanged between modules. Since at that time there was no inter-file linker (and the final executable file, only fragments), the modules should exchange data, making the transition to the void ... in which other modules should be located.

An example of this we can see in the bootloader BOOT.Son line 138 :

jmp$ee00

And this is pretty cryptic.

To follow the flow of instructions, we need to find out what is in $ee00. With a small grep command, you can see org = $ee00in HIRES.Sand port.

Since there were no linkers, the developers of the 80s needed to know the memory scheme of the engine and understand the limitations of RAM. This is now quite rare, because most professionals rely on garbage collectors or the use of vectors with automatic resizing.

Assembler 6502

I will talk about it to introduce the big picture and explain how the transition between subsystems is performed. To understand the contents of each module, you need to get a little acquainted with the central processor. Fortunately, 6502 is a simple 16-bit processor with only three registers, capable of addressing 64 KB of RAM (switching banks expanded this amount to 128 KB), without floating point functions and without segmentation, with only 56 instructions.

The figure shows how simple everything was:

Gray blocks: 64 KB of RAM, including 256 bytes allocated for the stack.
Blue blocks: 3 registers - X, A, Y (8 bits).
Green block: one 16-bit program counter.
Red block: one 8-bit stack pointer.
Yellow block: several STATUS flags.

Most operations are designed to load and store the register, the X and Y registers had simple instructions, and the drive (A) is a bit more complex, but generally quite straightforward and well-documented.

Two great books that are unfortunately out of print today are the Apple II Reference Manual and Inside the Apple IIe .

starting point

In the 80s there were no IDEs and C source files with the method main, so it is impossible to tell where the program started. To understand where to start reading, we need to know how Apple II booted:

Read the first byte X of sector 0 on track 0 from the floppy disk.
Download X sectors from track 0 to RAM at $800.
Start executing code at $800.

To find the starting point, we need to determine which module is instructed to run in $800using the directive search ORG:

    fabiensanglard$ find . -name "*.S" -exec grep -H "org = \$800" {} \;
    ./01 POP Source/Source/BOOT.S:org = $800
    ./02 POP Disk Routines/CP.525/POPBOOT0.S:org = $800
    ./03 Disk Protection/POPBOOT0.S:org = $800
    ./04 Support/MakeDisk/DRAZ/DRAZ.S:org = $800
    ./04 Support/MakeDisk/S/BOOT.S:org = $800

So, the starting point is at BOOT.S: this file, as we will see later, contains the PoP loader.

Part 2: bootloader

To save RAM and computing resources, Apple II game developers did not use the operating system that came with the computer. Therefore, they had to write their own bootloader: a small program that loaded the game engine from a floppy disk into RAM.

The procedures found in the Apple II ROM really helped in this: the RWTS16 was a set of instructions that controlled a floppy disk and allowed us to read / write 16 sectors of 256 bytes per track of 35 tracks. In total, it was 140 KB per disk.

But Brøderbund games did not use RWTS16. They found a better format: RWTS18, which provided more data and proved to be a reliable copy protection mechanism.

Traditional bootloader

Before focusing on the differences, I will list what is usually done in the video game industry:

Three components interact when a computer starts:

Floppy disk.
Boot procedure in Apple ROM.
Floppy Disk Readout Procedures (RWTS16) in Apple ROM.

When launching Apple II:

The computer installed its instruction pointer on boot instructions in Apple ROM
Apple boot procedures used RWTS16 to load sectors from floppy disk into RAM at $800.
These sectors contained the game loader.
Apple II boot procedures then proceeded to $800.

From this moment, the game loader was responsible for loading the game engine from a floppy disk into RAM:

Using the RWTS16 procedures of Apple II ...
He transferred the game engine from a floppy disk to RAM ...
And then he moved on to the engine.

RWTS16

RWTS16 was the floppy disk format shipped with the Apple II. It is described in detail in the brilliant book Beneath Apple DOS . In short, it consisted of a set of procedures in ROM that controlled a disk drive to write and read 16 sectors per track.

Sectors of 256 bytes were recorded on the track as follows:

Since the drives lacked accuracy, huge gaps had to be left between sectors to ensure erasing / restarting without overlapping:

As you can see in the figure below, the drive head could record a little before or after “perfect” provisions. The gaps compensated for these inaccuracies:

RWTS18

RWTS18 was a floppy disk format created by Roland Gustafsson for Brøderbund. It was completely different from RWTS16 in that it not only provided more storage, but also greatly complicated the life of hackers.

The increase in capacity of the RWTS18 was provided by an important observation: when developing games, it was mainly using data reading rather than writing. RWTS18 almost completely abandoned the concept of sectors: he recorded the entire track and read sectors of a much larger size.

Such a scheme made it possible to get rid of most of the gaps that RWTS16 had to have between sectors: only XXX self-synchronization bytes were between sectors.

As a result, RWTS18 provided storage of 768 bytes in each of the 6 sectors and 157 KB per disk instead of the 140 KB available with RWTS16.

But the increased capacity was not the only advantage of the RWTS18. He also created copy protection mechanisms:

All manufactured disks had physical differences: the data was encoded differently thanks to a nibble table loaded by RWTS18 at runtime.
Different Prolog and Epilog sectors confused disk copying programs.

Note: RWTS18 did not completely abandon sectors for two reasons:

The maximum latency of the beginning of track reading was 1/6 of a disk revolution.
Developers still needed a bit of fragmentation (a full track may contain too much data).

Note: Roland Gustafsson added his comment:

According to the specification, when reading a disk, 18 sectors could be transferred to 18 different pages of RAM, and not just be sequential reads of 18 sectors ($ 1200 bytes) in any resulting order. This method is now used for hard drives, it seems to be called "scatter-read" (and then it just seemed like a great idea to me!).

The self-modifying code I used allowed me to perform 4 cyclic readings instead of 6, saving 2 cycles of read / write. In addition, it allowed to “discard” read operations when each sector / page was not necessarily needed. There was an API that controlled all the necessary variations. The read and write cycles of the internal tracks were extremely tight. In fact, the recording procedures had to pre-process the data a little in advance in order to record in one revolution. If not mistaken, the stock was only 20%.

Interesting fact: Roland Gustafsson was so in love with Apple II that he made the number plate "D5 AA 96"for his car(this corresponds to the three-byte prologue marker RWTS16

.

Interesting fact: the source code RWTS18 was written using the LISA assembler, which had a marked-up file format, and not . just text files Roland plans to publish the source code, as you can remove it if you know how to do this, help him..

interesting fact: RWTS18 was so difficult to decipher what a strange legend: it used to be that to create a disco RWTS18 necessary slow disk drives .

Interesting fact:hackers still managed to hack Prince Of Persia ... but for further distribution they had to reverse-engineer the game and burn it to three disks formatted by RWTS16. The original version of PoP was sold on two disks with RWTS18. Even Apple II emulators can only run the hacked version of Prince Of Persia!

Prince Of Persia downloader

Now we have all the information to begin to deal with the PoP bootloader:

PoP started loading in the usual way: the first track was formatted by RWTS16, so Apple II boot procedures loaded the PoP bootloader into RAM.

Then the PoP loader using RWTS16 loaded the RWTS18 procedures from the rest of track 0.

Then the loader used RWTS18 to load the game engine from other tracks formatted by RWTS18.

The bootloader moved on to the game engine, which also used RWTS18 procedures to load game resources.

Interview with Roland Gustafsson

Roland agreed to answer a few questions, here is our interview:

Fabien Sanglar: Hi Roland, can you tell us a little about yourself: when you were born, where did you grow up, did you like school and how you became a programmer?

Roland Gustafsson: I was born in Sweden, but have lived all my life in California. I didn’t really like school, but I graduated from high school and at that time I already programmed and lived well in my 17 years. (That's why I didn’t go to college: at the university, the teaching of computer sciences was in no way connected with interesting new machines called “personal computers.” It was in the late 70s.)

FS:How did it happen that you started working for the Brøderbund in the 80s? How long have you been working there? How did you get the idea of RWTS18, why did you write it? What else have you worked on at Brøderbund besides RWTS18?

RG: I have never been an employee of Brøderbund, I did not have a real job, I was always a freelancer.

The idea of RW18 was born out of necessity. We had Bank Street products (after Bank Street Writer) that did not fit on a standard 16-sector drive. I used to have to do magic tricks, so I was asked if it was possible to come up with something to store more data. For years, I worked on copy protection, thought outside the box and fully understood the capabilities of the Disk II drive. After thinking a bit, I came to the most effective method that came to mind. It happened on a plane on the way to Japan, so I had a lot of time on paper and pencil. My friend Corey Kosak was sure that he had found a way to store 19 sectors (theoretical limit), but it used such expensive mathematical calculations that the weak 6502 could not cope with them. Mathematics for nibble management uses base 64, it was possible to store more data, if it were possible to easily work with base 78 or something similar, I do not remember. Mathematics a little stupor. And working with base 64, of course, binary systems was very simple.

FS: How did you work with Brøderbund (I am interested in schedules, salaries, passionate people like you)? Can you compare that experience with current working conditions?

RG: I did not have a real job, I did not want it, I do not like offices.

FS: Did you even work on Prince of Persia? Did you help the developers of the game or did you finish by passing the source code in assembler and the manual?

WG:I worked directly with Jordan Mekner on the implementation of RW18 and copy protection. We often had interesting moments when we came up with roundabout ways to complicate copying. In some cases, the game seemed to work, but as a result, it became impossible to play. In the case of most other games, I set to work after they were completed and added copy protection. The exception was the RW18 program, which had to be implemented at the development stage! I wrote a simple guide so that it can be easily used.

FS:Hackers: Heroes of the Computer Revolution has a chapter on the fight against Spiradisc and Sierra On-Line against piracy. Looking back, can you name the RWTS18 an effective way to protect the Brøderbund from game piracy? Have you studied copy protection mechanisms of other publishers (Spiradisc)? If so, what do you think of them?

WG:The only copy protection I have carefully studied is the cassette version of Microsoft Flight Simulator. Then I realized that there was copy protection. From that moment on, I developed my security system and rarely studied what others are doing. I myself came to the concept of protection with a spiral disk and used it in many games Brøderbund and Gebelli. I didn’t know if anyone had thought of technology with 18 sectors, but I heard many years later that someone had copied or reached this method himself. But I'm still not so sure. I know for sure that RW18 was invented by me.

FS:Continuing the theme of the fight against software piracy: have you followed the techniques of your opponents to improve RWTS18? Opponents sometimes pay tribute to the skill of those they fight: have you ever been impressed with what the pirates were able to do (for example, a pirated copy of PoP on three RWTS16 disks)?

WP: Yes, at least I studied Locksmith, Nibbles Away and other software for copying, and also read topics about hardware. I added code to protect against hardware copying, which was so well done that Apple couldn’t figure out how to protect against it even in the then unclaimed and secret Apple // e. So they brought this computer to my house and I made the protection work. I hid Apple // e for quite some time until it was announced and released.

Honestly, I believe that the idea of creating a three-disc version for a two-disc game with RW18 was stupid and not very impressive. They were better off creating a copy system that completely recreated this RW18 format and just made exact copies! The game would be much better, faster, etc ...

FS: What hack do you consider the greatest in the history of software development?

RG: Nothing comes to mind. I can say that when someone finds a surprisingly smart solution to a complex problem that requires inventive thinking, it is always worth recognition.

FS: Which game do you like most?
WG:Although I have not played for a very long time, I can name the original version of Tetris for GameBoy as a "network" game, when players fight against each other. I played it very hard at Brøderbund.

FS: Do you have a role model, a personal hero in the computer industry?

WP: The fact that Steve Wozniak insisted on publishing the source code for the original Apple II ROM was extremely important for my training. Once I met him at an Apple users meeting in San Francisco, I managed to talk to him and get detailed information about Disk II, which allowed me to take up copy protection.

FS: What moment are you most proud of as a software engineer?

WG:Whenever I manage to exceed expectations, “get the rabbit out of the hat,” these are amazing moments. I still consider RW18 one of my best tricks.

FS: What are you working on now?

WP: I am the technical director of Oceanhouse Media, we are developing mobile applications. Apple has made a real breakthrough with iOS and application development! We are also developing for other mobile markets, and much remains to be done. Yes, I'm still a big fan of Apple.

Part 3: more about the bootloader

A detailed commented version of the source code can be found on GitHub .

Here is a diagram of this notorious RAM, which will be specified below:

BOOT.S

BOOT.Sstarts with the output $01to the instruction stream ( line: 21 ). This forces the Apple firmware to automatically load one sector from track 0 into RAM at the address $800and go there:

After installing several software switches, it BOOT.Suses RWTS16 to load a series of sectors into RAM using the offset table ( line: 79 ). It BOOT.Sturned out that these sectors contain the rest of the procedures and RWTS18:

After moving the RWTS18 procedures to another bank at the address $D000(for ease of use), it uses RWTS18 to download the whole track 1 to the address $E000( line: 136 ) and goes to the mysterious one $ee00.

HIRES.S

We have no idea what was on track 1 and whether this data should be at the address $ee00.

But you can use grep to figure this out:

    fabiensanglard$ find . -name "*.S" -execgrep -H "org = \$ee00" {} \;
    ./01 POP Source/Source/HIRES.S:org = $ee00
    ./01 POP Source/Source/MOVER.S:org = $ee00

Having studied the code a bit, we found out that we are interested HIRES.S.

HIRES.Sat the beginning contains a conversion table that takes us to another mysterious address: $f880( line: 13 ).

MASTER.S

And again we do not know what should be at the address $f880.

But you can use grep again to find out:

    fabiensanglard$ find . -name "*.S" -execgrep -H "org = \$f880" {} \;
    ./01 POP Source/Source/MASTER.S:org = $f880
    ./04 Support/MakeDisk/S/MASTER.S:org = $f880
    ./04 Support/MakeDisk/S/MASTER525.S:org = $f880

So, the address $f880is the content MASTER.S. We can edit the memory allocation table: it

MASTER.Shas the following contents:

jmp FIRSTBOOT
      jmp LOADLEVEL
      jmp RELOAD
      jmp LoadStage2
      jmp RELOAD
      jmp ATTRACTMODE
      jmp CUTPRINCESS
      jmp SAVEGAME
      jmp LOADGAME
      jmp DOSTARTGAME
      jmp EPILOG
      jmp LOADALTSET

At this point, the game engine is loaded into RAM and ready to load the legendary DOUBLE-HIGH splash screen:

[Note trans.: this article ends somewhat prematurely. The author asked in the comments whether further analysis would be interesting, received a lot of positive answers, but for some reason did not advance further.]

Tags: