September 18, 2013 at 16:08[NES] We are writing a level editor for Prince of Persia. Epilogue. Dungeon
Chapter One , Chapter Two , Chapter Three , Chapter Four , Chapter Five , Epilogue
“Over and over, passing the games I liked so far and wide, finding all the possible secrets, I wanted to play them again and again, but with new levels, new secrets and new opportunities.”, I wrote . Naturally, passing the same game in the “regular” mode, the search began for something that was hidden behind the scenes. If the game has hidden levels, rooms, receptions or a system of passwords, then all day and midnight it was necessary to go behind the blue screen in attempts to find it, and crack passwords. PoP was no exception. And although I didn’t pick up an algorithm for compiling passwords, I was still able to find a couple of methods that allow me to compose the correct password from the existing one. It is true to say where the new password leads, until the moment of its use, I could not.
The PoP password system for NES is now described in more than detail: there are both methods for changing the existing password and a description of the algorithm itself.
It’s short, so I’ll bring it in the first language that came to hand:
And now, sorting passwords (back then on dendy, when there were no emulators in their current form and in the project), I ended up in strange places that were not explicitly provided for by the developers:
or the
Office in these "levels" only works partially, the appearance strange, and you can’t get there from the main game.
Now, looking at how the engine stores level data, I even made sure that more than 14 levels in the game are simply not provided. Where do these passwords lead?
As it turned out, in the game there are no checks for overflowing anything. For example, having placed more active active blocks in the room in the editor, you can get a frozen game, or other interesting artifacts in the form of a double that appeared or something else interesting.
The lack of verification also applies to the procedure for compiling passwords, the algorithm of which provides level numbers from 0 to 15. In order to save development time, the developers decided that since the game does not make up passwords, in which there will be levels with numbers 14 and 15 (in indexing from 0), then no one will enter them. Yeah.
We know that in our three tables of pointers, from which the final level is built, only 14 elements and 15 with 16 are not provided there. Therefore, the level is built from garbage that falls into the pointers when interpreting the data following the existing tables. But why there you can not fully control the character?
The level is built on the basis of three types of data, each of which has its own table of pointers:
There is also auxiliary data:
Tables with pointers are exactly 28 bytes apart. In other words, they follow each other. And if so, then the pointers are taken not from the desired table, but from the next one. Since the data referenced by these pointers is also mixed together, moving to 15 or 16 “levels”, we get somewhere in the middle of that data array. Moreover, data of one sense will be interpreted as data of another sense.
Let us mentally imagine a view of, say, 15 “level”. Take the offset 0x1EB66 (heading), add 28, and look at the pointer:
$ 8279 is even earlier than the heading of the first level [$ 82D9]. It is clear that we get to the data that describes the geometry of the first level. But they will now be interpreted differently:
* 05 - start in room 5;
* 00 00 - start at position 00 and look to the right;
* The rest of the data tells us that the guard will be in each room somewhere in the upper left corner, with a few exceptions.
0x1EB4A + 28 = 0x1EB66: $ 82D9. The level will be built on the basis of data that was once the heading of the first level. But we will start from the fifth room, therefore, starting from $ 82D9, we need to skip 4 rooms according to the rule: +30 bytes if the first byte is not equal to #FF, otherwise +1 byte:
$ 82D9 = # 01. We add +30.
$ 82F7 = # 05. We add +30.
$ 8315 = # 08. We add +30.
$ 8333 = # 20. We add +30.
$ 8,351:
Judging by the nature of the data, we ended up somewhere in the middle of some second-level room. The second level starts at $ 8331, therefore, it is somewhere inside the second room, which looks like this:
.
The guard should be located in the upper left corner, based on the header provided.
Now let's look at the level geometry.
0x1EB82 + 28 = 0x1EBA0:
Compare:
Since the border of this “room” does not coincide with the border of the second room of the second level, you can see some shift of the “architecture” to the left. Also on the left you can see the cliff, which corresponds to the next room, but it, according to the wrong level geometry, is not there.
Now I propose to see how the information about the guards in the level is used.
The procedure $ C0DA, as we recall, extracts a pointer to the level heading and places it at the addresses $ 6D: $ 6E, in register Y we have offset # 03, since the information about the guards is stored after the first three bytes, which are responsible for the prince’s position in the beginning of the level. It is further seen that if the first 5 bits are added to the number # 1E, then the iteration is skipped, otherwise the following structure is written to addresses starting from $ 0710: <room number>: <guard coordinate> - two bytes per structure. If all the rooms are full of guards, then the last address where we can put the data will be $ 0740, after which the #FF marker will be placed at $ 0742. But the addresses, starting from $ 0735, are used for a different purpose - this is evident during the regular operation of the game, which means that in this situation a classic buffer overflow occurs.
At $ 0735, we have a flag that is responsible for controlling the gamepad. If there is 0, then the control is standard, if not 0, then it is considered that we are in the start room, where control is limited. Now, at this "level", due to the fact that the coordinates of the guards have overwritten the important data, the cell $ 0 735 is not zero, and if we put 0 in it, we can fully control the prince. True, we will not be able to escape beyond this room, since the level geometry is broken.
The same applies to the 16th "level". 17 and above, “levels”, if at the time of entering a password of $ 70 put down the desired number, they fall into overt garbage and simply do not appear.
In this article I tried to tell that the widespread myth of "secret" levels is not true. In principle, analyzing the game code, and this was seen in previous articles, there are no secrets in the game at all: hidden rooms, levels, or anything like that. "Secret levels" - this is a banal lack of the necessary verification conditions in the procedure for reading passwords.
As a result of the whole study, I can say the following: the game is extremely simple within the framework of the second mapper, and moreover, it is most likely developed in a hurry. You can see a pretty good basis for the engine, but in the end it was obviously finished on crutches: the implementation of a double or non-standard transitions between levels is just a hardcode that is inserted in the middle of even code. This is where the differences between the NES version and other ports appear: in the end, the little things were simply not combed, although a couple of simple procedures were enough to bring to mind. If you add this in the form of a trivial patch to the engine, you can achieve almost full compliance with the original version, and then, it seems to me, the version on the NES will even win compared to the DOS version. Already at least the presence of musical accompaniment, a password system and a darker atmosphere.
This is the end of a series of articles about NES reverse. Now the plans include a descent to a lower level - the level of iron, since I want to play a new game on a real Dendy. There will be a couple more articles about this.
Disclaimer
“Over and over, passing the games I liked so far and wide, finding all the possible secrets, I wanted to play them again and again, but with new levels, new secrets and new opportunities.”, I wrote . Naturally, passing the same game in the “regular” mode, the search began for something that was hidden behind the scenes. If the game has hidden levels, rooms, receptions or a system of passwords, then all day and midnight it was necessary to go behind the blue screen in attempts to find it, and crack passwords. PoP was no exception. And although I didn’t pick up an algorithm for compiling passwords, I was still able to find a couple of methods that allow me to compose the correct password from the existing one. It is true to say where the new password leads, until the moment of its use, I could not.
Dungeon
The PoP password system for NES is now described in more than detail: there are both methods for changing the existing password and a description of the algorithm itself.
It’s short, so I’ll bring it in the first language that came to hand:
Bash password generator
#!/bin/bash
PLEVEL=$1
PTIME=$2
if ! [[ ${PLEVEL} =~ ^[0-9]{1,2}$ ]] ; then echo "Invalid level" >&2 ; exit 1 ; fi
if ! [[ ${PTIME} =~ ^[0-9]{1,2}$ ]] ; then echo "Invalid time" >&2 ; exit 1 ; fi
if [ "0" == ${PLEVEL} ] ; then echo "Level must be great than 0" >&2 ; exit 1 ; fi
PLEVEL=$[PLEVEL-1]
R1=$[RANDOM % 10]
R2=$[RANDOM % 10]
PASS0=$[((PTIME / 10)+R1) % 10]
PASS3=$[((PTIME % 10)+R2) % 10]
PASS1=$[((PLEVEL & 3)+R1) % 10]
PASS7=$[((PLEVEL / 4)+R2) % 10]
PASS2=$R1
PASS5=$R2
SUM=$[PASS0+PASS1+PASS2+PASS3]
SUM=$[SUM+(SUM % 10)+PASS5]
SUM=$[SUM+(SUM / 10)+PASS7]
PASS4=$[SUM % 10]
PASS6=$[SUM / 10]
echo "${PASS0}${PASS1}${PASS2}${PASS3}${PASS4}${PASS5}${PASS6}${PASS7}${PASS8}${PASS9}"
And now, sorting passwords (back then on dendy, when there were no emulators in their current form and in the project), I ended up in strange places that were not explicitly provided for by the developers:
or the
Office in these "levels" only works partially, the appearance strange, and you can’t get there from the main game.
Now, looking at how the engine stores level data, I even made sure that more than 14 levels in the game are simply not provided. Where do these passwords lead?
Overflow
As it turned out, in the game there are no checks for overflowing anything. For example, having placed more active active blocks in the room in the editor, you can get a frozen game, or other interesting artifacts in the form of a double that appeared or something else interesting.
The lack of verification also applies to the procedure for compiling passwords, the algorithm of which provides level numbers from 0 to 15. In order to save development time, the developers decided that since the game does not make up passwords, in which there will be levels with numbers 14 and 15 (in indexing from 0), then no one will enter them. Yeah.
We know that in our three tables of pointers, from which the final level is built, only 14 elements and 15 with 16 are not provided there. Therefore, the level is built from garbage that falls into the pointers when interpreting the data following the existing tables. But why there you can not fully control the character?
Recall the theory
The level is built on the basis of three types of data, each of which has its own table of pointers:
- Blocks from which rooms are built - 0x1EB4A;
- Level header - 0x1EB66;
- Level geometry - 0x1EB82.
There is also auxiliary data:
- Type of level;
- Palette;
- Type of guard;
- Amount of health;
- Other data that does not significantly affect the appearance.
Tables with pointers are exactly 28 bytes apart. In other words, they follow each other. And if so, then the pointers are taken not from the desired table, but from the next one. Since the data referenced by these pointers is also mixed together, moving to 15 or 16 “levels”, we get somewhere in the middle of that data array. Moreover, data of one sense will be interpreted as data of another sense.
Let us mentally imagine a view of, say, 15 “level”. Take the offset 0x1EB66 (heading), add 28, and look at the pointer:
D9 82 61 86 91 89 F1 8C 06 90 85 92 0D 96 61 99 F3 9C CD 9F 2C A3 9B A6 5B A8 AC A9 >> 79 82 << ...$ 8279 is even earlier than the heading of the first level [$ 82D9]. It is clear that we get to the data that describes the geometry of the first level. But they will now be interpreted differently:
05 00 00 02 06 03 01 00 02 09 00 00 13 0E 14 00 15 01 00 06 08 02 05 00 ...* 05 - start in room 5;
* 00 00 - start at position 00 and look to the right;
* The rest of the data tells us that the guard will be in each room somewhere in the upper left corner, with a few exceptions.
0x1EB4A + 28 = 0x1EB66: $ 82D9. The level will be built on the basis of data that was once the heading of the first level. But we will start from the fifth room, therefore, starting from $ 82D9, we need to skip 4 rooms according to the rule: +30 bytes if the first byte is not equal to #FF, otherwise +1 byte:
$ 82D9 = # 01. We add +30.
$ 82F7 = # 05. We add +30.
$ 8315 = # 08. We add +30.
$ 8333 = # 20. We add +30.
$ 8,351:
20 00 00 14 01 03 21 03 14 14 20 00 00 14 14 14 14...Judging by the nature of the data, we ended up somewhere in the middle of some second-level room. The second level starts at $ 8331, therefore, it is somewhere inside the second room, which looks like this:
. The guard should be located in the upper left corner, based on the header provided.
Now let's look at the level geometry.
0x1EB82 + 28 = 0x1EBA0:
0C 03 C0 30 0C 03...That is, it will be somewhere around the address $ 030C in RAM (not in ROM!). The data at these addresses is known to be more than 24, which suggests that it will not be possible to go to the next room with all the desire. Compare:
Since the border of this “room” does not coincide with the border of the second room of the second level, you can see some shift of the “architecture” to the left. Also on the left you can see the cliff, which corresponds to the next room, but it, according to the wrong level geometry, is not there.
Set in motion
Now I propose to see how the information about the guards in the level is used.
$F284:20 DA C0 JSR $C0DA
$F287:B1 6D LDA ($6D),Y @ $9FC7 = #$1E
$F289:29 1F AND #$1F
$F28B:C9 1E CMP #$1E
$F28D:B0 0E BCS $F29D
$F28F:A6 17 LDX $0017 = #$00
$F291:9D 11 07 STA $0711,X @ $0723 = #$00
$F294:A5 18 LDA $0018 = #$00
$F296:9D 10 07 STA $0710,X @ $0722 = #$00
$F299:E6 17 INC $0017 = #$00
$F29B:E6 17 INC $0017 = #$00
$F29D:E6 18 INC $0018 = #$00
$F29F:A5 18 LDA $0018 = #$00
$F2A1:C9 19 CMP #$19
$F2A3:D0 D9 BNE $F27E
$F2A5:A6 17 LDX $0017 = #$00
$F2A7:A9 FF LDA #$FF
$F2A9:9D 10 07 STA $0710,X @ $0722 = #$00
$F2AC:60 RTS
The procedure $ C0DA, as we recall, extracts a pointer to the level heading and places it at the addresses $ 6D: $ 6E, in register Y we have offset # 03, since the information about the guards is stored after the first three bytes, which are responsible for the prince’s position in the beginning of the level. It is further seen that if the first 5 bits are added to the number # 1E, then the iteration is skipped, otherwise the following structure is written to addresses starting from $ 0710: <room number>: <guard coordinate> - two bytes per structure. If all the rooms are full of guards, then the last address where we can put the data will be $ 0740, after which the #FF marker will be placed at $ 0742. But the addresses, starting from $ 0735, are used for a different purpose - this is evident during the regular operation of the game, which means that in this situation a classic buffer overflow occurs.
At $ 0735, we have a flag that is responsible for controlling the gamepad. If there is 0, then the control is standard, if not 0, then it is considered that we are in the start room, where control is limited. Now, at this "level", due to the fact that the coordinates of the guards have overwritten the important data, the cell $ 0 735 is not zero, and if we put 0 in it, we can fully control the prince. True, we will not be able to escape beyond this room, since the level geometry is broken.
The same applies to the 16th "level". 17 and above, “levels”, if at the time of entering a password of $ 70 put down the desired number, they fall into overt garbage and simply do not appear.
Epilogue in the epilogue
In this article I tried to tell that the widespread myth of "secret" levels is not true. In principle, analyzing the game code, and this was seen in previous articles, there are no secrets in the game at all: hidden rooms, levels, or anything like that. "Secret levels" - this is a banal lack of the necessary verification conditions in the procedure for reading passwords.
As a result of the whole study, I can say the following: the game is extremely simple within the framework of the second mapper, and moreover, it is most likely developed in a hurry. You can see a pretty good basis for the engine, but in the end it was obviously finished on crutches: the implementation of a double or non-standard transitions between levels is just a hardcode that is inserted in the middle of even code. This is where the differences between the NES version and other ports appear: in the end, the little things were simply not combed, although a couple of simple procedures were enough to bring to mind. If you add this in the form of a trivial patch to the engine, you can achieve almost full compliance with the original version, and then, it seems to me, the version on the NES will even win compared to the DOS version. Already at least the presence of musical accompaniment, a password system and a darker atmosphere.
This is the end of a series of articles about NES reverse. Now the plans include a descent to a lower level - the level of iron, since I want to play a new game on a real Dendy. There will be a couple more articles about this.