The Cause of the RBS Discovered?

[xelnia]

I think everyone knows by this point that code-level stuff is far from my level of expertise. But I can work stuff out given time, and I think I've done that with DK3 and its repetitive blue screen (RBS). The logic of my findings has gotten an initial thumbs-up from Sock, but I'm sure there's some nuance I'm missing somewhere. Since I'm not a trained or learned programmer, I'm probably going to do a shit job of formatting this post, so my apologies upfront for that. Anyway, let's get to it:

For background, DK3 has 3 board types: blue, grey, and gold. Levels 1 and 2 are a blue board then a gold board. The grey board joins the mix afterwards and the three boards loop: blue-grey-gold, blue-grey-gold, etc. When we reach Level 159, we expect a blue board, and a blue board it is. So, we would expect Level 160 to be a grey board, Level 161 to be a gold board, and so on. But when we reach Level 160, it's actually a blue board! So is Level 161, so is Level 162...all the way up to Level 255. After Level 255 we get a blue board on Level 0, and then the game loops back to Level 1 and everything is as we would excpect, and if we reach Level 160 again, the RBS comes back. Reaching the RBS earns a player a spiffy DKF badge and as of this post only 3 players have done it: George Riley (who discovered it in 2010), Ben Falls in 2013, and Andrew Barrow in 2017.

So, what causes the RBS?

Prior to Level 29, the game uses some routines to search a table that lists the difficulty and board type that the next level should be. When we reach Level 29+, a special routine is added into the mix to force the game to use the last group of values in that table, effectively making the game loop at its maximum difficulty. This special routine (let's call it the Loop Routine) is where the bug is found. When the current level is equal to 29 the Loop Routine spits out a particular value used in later routines to say "ok, the next board is blue." We expect Level 30 to be blue, so no problem. However, when we get to Level 158 (yes, one-fifty-eight), the Loop Routine spits out the same value as Level 29...and will only spit out that same value until the entire game loops back to Level 1 and the Loop Routine is temporarily retired. Again, we expect Level 159 to be blue, and it is...so no problem. But now that forced value from the Loop Routine makes everything beyond Level 159 blue as well.

In short, the game is forcing itself to always look in the same spot in a data table of difficulties and board types.

Now the nitty-gritty: why does the game get stuck looking in the same place over and over?

It all comes down to a couple of lines in the Loop Routine (which is only implemented once we reach Level 29):

Code: [Select]

396B: DEC     B
396C: JP      M,$3978
These instructions are pretty simple: First subtract 1 from B (DEC B). If the result is a negative number, then jump to $3978 (JP M,$3978). Otherwise, move on to the next instruction. At this point, it's important to actually define what a "negative" number is in this particular case. If the result of a DEC instruction is $80-$FF, then the Sign flag will be set, telling future instructions that we have negative value on our hands. If the Sign flag is set, then the M in JP M,$3978 says "we've got a negative number, jump to $3978." If the result is $00-$7F then the JP M,$3978 instruction doesn't jump anywhere and the next instruction can be followed.

Why is $00-$7F positive, but $80-$FF negative? Aren't those just equivalent to 0-127 and 128-255 in decimal? Yes, but at the bit/binary level they're equivalent to b00000000-b01111111 and b10000000-b11111111. And it's the most significant bit (MSB, the bit on the far left) that gives us a negative number. When the DEC B instruction runs, if the MSB is 0, the result is positive. If it's 1, the result is negative. So for any instruction where sign matters (like JP M,$3978), b10000000-b11111111 ($80-$FF) is considered negative, thus the shift from $80 to $7F constitutes an overflow.

Let's see this context and break it down even further. Here's the entire Loop Routine:

Code: [Select]

; Loop Routine. At this point, A has gone through a couple modifications, but at the start of this routine is equal to the current level.

3966: SUB     $1D         ; subtract $1D (29) from A. result will be $00-$E2.
3968: LD      B,A ; store into B. now B is $00-$E2.
3969: LD      A,$1A  ; set A to $1A (26)
396B: DEC     B ; decrement B. now B is $FF, or $00-$E1.
396C: JP      M,$3978 ; if negative, jump to $3978. otherwise, next step.
396F: INC     A ; increment A (add 1). result will be $1B, $1C, or $1D. \
3970: CP      $1D ; compare with $1D (29)           | will always be skipped if B == $80-$FF.
3972: JR      NZ,$396B ; if equal, next step. if not, jump back to $396B | skipping always makes A == $1A.
3974: LD      A,$1A ; if A == $1D, set it to $1A | will happen on Levels 29, and 158-255.
3976: JR      $396B ; now jump back to $396B /
3978: RET ; once B is negative, go to the next routine
Plainly, this is doing two things. It is subtracting 1 from B until B is negative. While it's doing that it's cycling A through 4 values: $1A, $1B, $1C, and $1D. It doesn't want A to be $1D, so whenever it is, it sets it back to $1A. When B finally reaches a negative value, it ends the routine and sends A's value ahead. As a result, the final value of A will always cycle through $1A, $1B, or $1C and the decrementing of B is used to determine when that cycle stops.

How is this working in-game?

If we're on Level 29 ($1D), then B will immediately be negative: Subtract $1D from $1D, then decrement = $FF. $FF is negative, A has already been set $1A, so the rest of the routine is skipped and that $1A gets fed into future routines and we get a blue board for Level 30 (which we expect anyway).

If we're on Level 30 ($1E), B is not immediately negative: Subtract $1D from $1E, then decrement = $00. $00 is not negative and as usual A already has been set to $1A, but we have to increment A and keep decrementing B until it's negative. So, A becomes $1B and we decrement B to $FF. Now B is negative so we skip the rest of routine without any more modifications to A. A has been set to $1B and $1B gets sent forward for future calculations and we get a grey board.

As the level increases, the more loops it takes for B to become negative...but A will always come out as $1A, $1B, or $1C. Until we hit Level 158 (yes, one-fifty-eight), a gold board. At this point, just like on Level 29, B is negative immediately following the first DEC instruction. Level 158 is Level $9E. $9E - $1D = $81. $81 - 1 = $80. As noted above $80-$FF are negative, so the entire process of incrementing A is skipped and A's value of $1A is sent forward and we get a blue board for Level 159. As also noted above, fine...we expect Level 159 to be blue. But the blues keep coming: on Level 159, B is decremented to $81. On Level 160, it's decremented to $82. Since our first loop through the DEC instruction is negative, we never get to increment A beyond $1A. So on and so forth, until the game levels loop back to Level 1 and this entire Loop Routine is skipped again. B never comes back around to a positive number in this case because there aren't enough boards before the game loops for it to happen.

And...well...that's pretty much it. As the result of an overflow bug, the game gets stuck in a loop where it's always forced to look at the same place in a table. I definitely welcome any clarifications or better explanations that anyone can provide.

Here's a much larger portion of the code. It details the related routines before and after the Loop Routine, showing how the value of A is used to search the table.

Code: [Select]

;this bounces back and forward a bit. this section of code is called when it's time to determine what the next level/difficulty/board type will be
;seems to happen right after all the bonus scores are tallied
;really starts at $3BDE

; arrive here from $3BE7
394E: 3D                          DEC     A              ; decrement A
394F: FE 1D                             CP      $1D            ; are we on level 28 or under?
3951: 38 03                             JR      C,$3956        ; yes, jump to $3956
3953: CD 66 39                          CALL    $3966          ; no, jump to $3966

; reach here from $3951 if we're on level 28 or under. called here from $3978 when we're level 29 or higher.

3956: 6F                          LD      L,A ; load L with A
3957: 26 00                             LD      H,$00 ; load H with $00
3959: 29                                ADD     HL,HL ; add HL to itself   \
395A: 29                                ADD     HL,HL ; add again           | multiply HL by 8
395B: 29                                ADD     HL,HL ; add one more time  /
395C: 01 75 8D                          LD      BC,$8D75 ; load BC with $8D75
395F: 09                                ADD     HL,BC           ; add BC into HL
3960: 01 08 00                          LD      BC,$0008 ; load BC with $08
3963: ED B0                             LDIR ; copy 8 bytes starting from result of $395F into $60D0-$60D7, increment DE and HL by 8
3965: C9                                RET ; return

; called from $3953 and $398E. "Loop Routine": only reach here if we're on board 29 or higher? used to find offset in table to determine difficulty and board for level 30 and higher?

3966: D6 1D                      SUB     $1D ; subtract $1D (29) from A. result will be $00-$E2.
3968: 47                                LD      B,A ; store into B. now B is $00-$E2.
3969: 3E 1A                             LD      A,$1A ; set A to $1A (26)
396B: 05                          DEC     B    ; decrement B. now B is $FF, or $00-$E1.
396C: FA 78 39                          JP      M,$3978 ; if negative, jump to $3978. otherwise, next step.
396F: 3C                                INC     A  ; increment A (add 1). result will be $1B, $1C, or $1D. \
3970: FE 1D                             CP      $1D ; compare with $1D (29)           | will always be skipped if B == $80-$FF.
3972: 20 F7                             JR      NZ,$396B ; if equal, next step. if not, jump back to $396B | skipping always makes A == $1A.
3974: 3E 1A                             LD      A,$1A ; if A == $1D, set it to $1A | will happen on Levels 29, and 158-255.
3976: 18 F3                             JR      $396B ; now jump back to $396B /
3978: C9                          RET ; once B is negative, go to the next routine

; arrive here from $38A7, not related to level number, difficulty, or board type?

3979: 3E 01                      LD      A,$01
397B: 11 A0 60                          LD      DE,$60A0
397E: CD 89 39                          CALL    $3989
3981: 3E 01                             LD      A,$01
3983: 11 A8 60                          LD      DE,$60A8
3986: C3 89 39                          JP      $3989

; arrive here from $3BEE

3989: 3D                          DEC     A         ; decrement A
398A: FE 1D                             CP      $1D ; A < 29?
398C: 38 03                             JR      C,$3991 ; yes, jump to $3991. otherwise next step
398E: CD 66 39                          CALL    $3966 ; jump to $3966
3991: CD 9E 39                    CALL    $399E         ; jump to $399E

; arrive here from $39A6, look for difficulty and board type in table and update accordingly

3994: 4E                                LD      C,(HL) ; load (HL) into C (get our board type from table and store into C)
3995: 23                                INC     HL ; increment HL (location of difficulty in table, which is offset from board type by 1?)
3996: 7E                                LD      A,(HL) ; load (HL) into A
3997: 12                                LD      (DE),A ; update #6018 with A (update difficulty?)
3998: 13                                INC     DE ; increment DE  \
3999: 13                                INC     DE ; increment DE   | change DE to $601B (board type address)
399A: 13                                INC     DE ; increment DE  /
399B: 79                                LD      A,C ; load A with C (board type from table)
399C: 12                                LD      (DE),A ; update $601B with A (update board type)
399D: C9                                RET ; return

; arrive here from $3991, handles where to look in table for difficulty and board type?

399E: 6F                          LD      L,A ; load L with A
399F: 26 00                             LD      H,$00 ; load H with $00
39A1: 29                                ADD     HL,HL ; add HL to itself (multiply by 2)
39A2: 01 3B 8D                          LD      BC,$8D3B ; load BC with $8D3B (start of difficulty/board type table?)
39A5: 09                                ADD     HL,BC ; add BC into HL
39A6: C9                                RET ; return

; arrive here from $3E2C. time to update level number, difficulty(?), and board type?

3BDE: 21 19 60                    LD      HL,$6019        ; load HL with current level number (the level we just finished)
3BE1: 34                                INC     (HL)            ; increment level number by 1
3BE2: 11 D0 60                          LD      DE,$60D0        ; store $60D0 in DE
3BE5: 7E                                LD      A,(HL)          ; store new level number in A
3BE6: F5                                PUSH    AF              ; push to stack
3BE7: CD 4E 39                          CALL    $394E          ; jump to $394E

; arrive here from $3965

3BEA: F1                                POP     AF ; restore AF
3BEB: 11 18 60                          LD      DE,$6018 ; store $6018 into DE
3BEE: C3 89 39                          JP      $3989 ; jump to $3989

; arrive here from $399D

3E2F: D7                                RST     $0010            ; jump to $0010


; difficulty/board type table. 58 bytes long.

8D3B:         00 81 02 01 ; board 1-2
8D3F:   00 82 01 02 02 02 ; board 3-5
8D45:   00 83 01 03 02 03 ; board 6-8
8D4B:   00 84 01 04 02 04 ; board 9-11
8D51:   00 85 01 05 02 05 ; board 12-14
8D57:   00 86 01 06 02 06 ; board 15-17
8D5E: 00 87 01 07 02 07 ; board 18-20
8D63: 00 88 01 08 02 08 ; board 21-23
8D69: 00 89 01 09 02 09 ; board 24-26
8D6F: 00 8A 01 0A 02 0A ; board 27-29+

; table used in #3963, what is this for? each 8 bytes is data for something in a level?

8D75: 00 20 00 00 00 00 00 01
8D7D: 00 88 00 00 00 00 03 00
8D85: 04 1C 00 00 00 00 00 02
8D8D: 04 1C 00 00 00 00 00 02
8D95: 81 87 00 00 00 00 03 00
8D9D: 04 18 00 00 04 00 00 04
8DA5: 04 14 00 00 08 00 00 04
8DAD: 81 85 00 00 82 00 04 00
8DB5: 04 14 00 00 08 00 00 04
8DBD: 08 10 00 00 08 00 00 04
8DC5: 82 84 00 00 82 00 04 00
8DCD: 04 00 14 00 08 00 00 04
8DD5: 08 00 10 00 08 00 00 04
8DDD: 82 00 84 00 82 00 04 01
8DE5: 04 00 14 00 08 00 00 04
8DED: 08 00 10 00 08 00 00 04
8DF5: 82 00 84 00 82 00 04 02
8DFD: 08 00 14 00 00 04 00 04
8E05: 04 00 14 00 00 08 00 04
8E0D: 81 00 85 00 82 00 04 03
8E15: 08 00 10 00 00 08 00 04
8E1D: 04 00 10 00 00 0C 00 04
8E25: 81 00 84 00 00 83 04 03
8E2D: 08 00 08 08 00 08 00 04
8E35: 04 00 08 08 00 0C 00 04
8E3D: 81 00 82 82 00 83 04 03
8E45: 08 00 08 08 00 08 00 04
8E4D: 04 00 08 08 00 0C 00 04
8E55: 81 00 82 82 00 83 05 03


[homerwannabee]

Let me see if I can break it down to layman terms I can understand. After board 30 the program has a system where they split 256 boards.  The first 128 is a positive value, and the next 128 are negative.  Everything is great as long as the boards are positive value, and that leads to the next 128 boards being good to go.  So 30 + 128 = 158.   After that though, the boards have a negative value, and when that happens the program goes back repeatedly to the blue board until that board becomes positive again, but that doesn't happen, and it remains blue for the next 98 boards.  The blue boards then stays that way until board 1 where the original program kicks back into gear (actually board 2 is the first non blue board again).

Thanks for the enlightenment.  I always thought that the repetitive blue board happened along the same lines as Donkey Kong, and Donkey Kong Junior.  Come to find out it's a completely different reason that this happens.

 

[xelnia]

Let me see if I can break it down to layman terms I can understand. After board 30 the program has a system where they split 256 boards.  The first 128 is a positive value, and the next 128 are negative.  Everything is great as long as the boards are positive value, and that leads to the next 128 boards being good to go.  So 30 + 128 = 158.   After that though, the boards have a negative value, and when that happens the program goes back repeatedly to the blue board until that board becomes positive again, but that doesn't happen, and it remains blue for the next 98 boards.  The blue boards then stays that way until board 1 where the original program kicks back into gear (actually board 2 is the first non blue board again).

Thanks for the enlightenment.  I always thought that the repetitive blue board happened along the same lines as Donkey Kong, and Donkey Kong Junior.  Come to find out it's a completely different reason that this happens.

I don't think it's really splitting or separating boards, or anything, into positive or negative values. The Loop Routine just keeps counting down until it sees a negative value, which in this particular case will be $80-$FF. It seems clear the programmers considered the possibility that players would get to board 30 and beyond, because the Loop Routine is what makes the game loop through the maximum values in the table...they just didn't consider, or care, what would happen at the much higher levels. The routine spits out the exact same results if we're going into board 30, 159, or 160...so you might even consider boards 30 and 159 to be "bugged" themselves. But we expect 30 and 159 to blue, so are they really? Are boards 162 or 165 or 168, and so on, "bugged"? We expect those to be blue as well.

[danman123456]

Its really just the simple math routine they used for it George. Its essentially using 128 as the number not really "splitting" anything up as Jry said. Thats why its board 159 because of the way the math worked out that Jry mentions. Its the difficulty check for lvl 29 that wrecks it all

Kinda figured something like this must be the cause because of when the RBS issue happened. Also makes sense why it "flips" after board 256 and goes back to normal. Anyone made it to board 316? I would be willing to bet its RBS all over again. Also based on this and the numbers I would assume the game thinks its level ONE again and the difficultly resets back down to "easiest" as well.

Dan

Let me see if I can break it down to layman terms I can understand. After board 30 the program has a system where they split 256 boards.  The first 128 is a positive value, and the next 128 are negative.  Everything is great as long as the boards are positive value, and that leads to the next 128 boards being good to go.  So 30 + 128 = 158.   After that though, the boards have a negative value, and when that happens the program goes back repeatedly to the blue board until that board becomes positive again, but that doesn't happen, and it remains blue for the next 98 boards.  The blue boards then stays that way until board 1 where the original program kicks back into gear (actually board 2 is the first non blue board again).

Thanks for the enlightenment.  I always thought that the repetitive blue board happened along the same lines as Donkey Kong, and Donkey Kong Junior.  Come to find out it's a completely different reason that this happens.

[homerwannabee]

The game goes back to the start on board 1.  There is no board 312.  But if you are talking about board 256+56=312 then no, it doesn't go RBS.  In order to go RBS again you need to get to board 160 again.  Since I have rolled the levels twice in a row 7 years ago, I am pretty sure this is correct.

[danman123456]

Once the lvl resets to board 1 you would need to go to board 160 again. That is what I meant to say because you need to wait until you get out of "RBS mode". I just did a stupid typo and meant board 416 not 316.

The game goes back to the start on board 1.  There is no board 312.  But if you are talking about board 256+56=312 then no, it doesn't go RBS.  In order to go RBS again you need to get to board 160 again.  Since I have rolled the levels twice in a row 7 years ago, I am pretty sure this is correct.