Conta High Score Display Logic

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
User avatar
vermiceli
Posts: 12
Joined: Tue Nov 24, 2020 5:07 pm

Conta High Score Display Logic

Post by vermiceli »

I did some research into how Contra converts from the score stored in memory as hexadecimal to decimal for display to the player. I thought it was interesting enough to write it up and I figured I could share the information here for discussion. Any feedback would be appreciated. Also, does anyone have insight on how common this technique is across NES games compared to other algorithms?

How Contra Prints the High Score

Overview
There are 3 scores stored in CPU memory for Contra: high score, player 1 score, and player 2 score. Each score is 2 bytes and stored in addresses 0x07e0-0x07e1, 0x07e2-0x07e3, and 0x07e4-0x07e5 respectively. These 2-byte scores are little-endian, i.e. the least significant byte is the lower-addressed byte. All scores have 00 appended when displayed, for example a score of 100 will show as 10000 on the screen. The default initial high score stored in 0x07e2 is 0xc8, or 200 in decimal. This will show as 20000. The exception to this is a score of 0. 0 points will show as 0 and not 000.

The logic to display the score on the screen is non-trivial and worth properly documenting. To display the score on the screen, the code needs to convert an in-memory hexadecimal number to a decimal number.

At a high level, Contra recursively calculates each decimal digit to display one at a time from right to left. If the player's score is 123 in decimal, or 0111 1011 in binary. Contra will call the same routine 3 times, each time producing the next digit in the score from right to left: 3, then 2, then 1.

Code: Select all

Call # | Rest | Right Digit |
-------|------|-------------|
 1     | 12   | 3           |
 2     | 1    | 2           |
 3     | 0    | 1           |
The Rest column can be conceptually though of as 10 times larger than what is stored in memory. So 12 really means 120, and 1 really means 10. This will make conceptualizing the algorithm easier.

Examples
This document's examples are simplified slightly in that these examples are using 1-byte scores and not 2-byte scores like Contra. The source code shown works against 2-byte scores.

Example of Routine
As shown above, the routine is called a number of times, each time retrieving the next digit of the score to display. Below is a step-by-step walk through of calculating a single digit of the score to display.

Code: Select all

  Score (0x01): 0x7b 0111 1011 (123 in decimal)

  Right Digit (0x02): 0x00 0000 0000 (0)

  Shift # | Rest      | Right Digit | Input    | Explanation                  |
  --------|-----------|-------------|----------|------------------------------|
   1      |           |   0         | 111 1011 | left shift                   |
   2      |           |   01        | 111 011  | left shift                   |
   3      |           |   011       | 11 011   | left shift                   |
   4      |           |   0111      | 1 011    | left shift                   |
   5      |           |   1111      | 011      | left shift                   |
          |           |   0101      | 011      | subtract 10 from right digit |
   6      |         1 |   1010      | 11       | shift left, mark 1 into Rest |
          |         1 |   0000      | 11       | subtract 10                  |
   7      |        11 |   0001      | 1        | shift left, mark 1 into Rest |
   8      |       110 |   0011      |          | shift left                   |
   9      |      1100 |   0011      |          | shift left Rest only         |

  Rest (0x01):  0000 1100 (12 decimal)

  Right Digit (0x02): 0000 0011 (3 decimal)
The way Contra determines the right-most digit recursively is very interesting. Every time the algorithm shifts left, the input is passed through the "Right Digit" column which will track when the single-digit is more than 10. Every time the right digit's column is more than 10, 10 is subtracted. On the subsequent left shift, 1 is placed on the right-most bit of the Rest column. That 1 signifies that a subtraction of 10 was performed. Remember that the Rest column's value is conceptually 10 times larger, e.g. 12 really means 120. So when the 1 is carried to the "Rest" column, it is really a 10 being carried, which matches what was subtracted from the "Right Digit" column.

Memory-accurate Example With a 1-byte Score
While the previous example helps understand at a conceptual level, it hides some of the technical ingenuity. Contra doesn't split the score ("Input") into "Right Digit" and "Rest". Contra actually shifts the "Rest" back into the "Input". This is useful because it allows the routine to be called consecutively until there are no more digits to display.

Again, Contra uses 2-byte scores, but if Contra had 1-byte scores, this is how the algorithm would work, while being memory accurate. 0x01 is shifted into 0x02. Right Digit (0x02) is always initialized to zero.

Code: Select all

  Score (0x01): 0x7b 0111 1011 (123)

  Right Digit (0x02): 0x00 0000 0000 (0)

  Shift # |  0x01       |  0x02       | Explanation                  |
  --------|-------------|-------------|------------------------------|
   1      |  1111 0110  |  0000 0000  | left shift 0x01 only         |
   2      |  1110 1100  |  0000 0001  | left shift 0x02, 0x01        |
   3      |  1101 1000  |  0000 0011  | left shift 0x02, 0x01        |
   4      |  1011 0000  |  0000 0111  | left shift 0x02, 0x01        |
   5      |  0110 0000  |  0000 1111  | left shift 0x02, 0x01        |
          |  0110 0000  |  0000 0101  | subtract 10                  |
   6      |  1100 0001  |  0000 1010  | shift left, mark 1 into Rest |
          |  1100 0001  |  0000 0000  | subtract 10                  |
   7      |  1000 0011  |  0000 0001  | shift left, mark 1 into Rest |
   8      |  0000 0110  |  0000 0011  | shift left 0x02, 0x01        |
   9      |  0000 1100  |  0000 0011  | shift left 0x01 only         |

  Rest (0x01):  0000 1100 (12 decimal)

  Right Digit (0x02): 0000 0011 (3 decimal)
You can see that after this routine is called, it can be called again immediately to determine the next right-most digit since the score address (0x01) is overwritten with the new score. 0x02 is never more than 4-bits, and no additional memory locations are needed. I believe this is the reason this algorithm was used over other algorithms that can convert from hexadecimal to decimal with a fixed number of steps.

Contra's Score Display Algorithm in Assembly from Source
The code for converting the scores for display is in the last (8th) PRG ROM bank, bank 7. The logic begins at address $caf8 in CPU memory. Contra will recursively determine the value of the "Right Digit" place, which is then displayed on the screen to the player.

CPU memory addresses used
  • 0x00 - low byte of the current score being calculated
  • 0x01 - high byte of the current score being calculated
  • 0x02 - the next decimal digit to display
  • 0x03 - hard-coded 10 in decimal

Code: Select all

calculate_score_digit:
    lda #$00     ; set the accumulator register A to zero (#$00)
    sta $02      ; zero out any previously calculated digit
    ldy #$10     ; set the left-shift loop counter back to #$10 (16 decimal)
    rol $00      ; shift the score low byte to the left by one bit
                 ; push the most significant bit (msb) to the carry flag
    rol $01      ; shift the score high byte to the left by one byte
                 ; push the msb to the carry flag
                 ; pull in carry flag to least significant bit (lsb)

shift_and_check_digit_carry:
    rol $02      ; shift score high byte to the left by one bit
                 ; if the msb of the score high byte was 1, then carry into lsb
    lda $02      ; load current digit into the accumulator register A
    cmp $03      ; compare #$0a (10 decimal) to the current digit

                 ; branch if current digit is less than #$0a (10 decimal)
                 ;  - this means no subtraction and carry is needed
                 ; if greater than #$0a (10 decimal), don't jump
                 ;  - subtract 10 and carry
    bcc continue_shift_score
    sbc $03      ; the current digit is greater than 10, subtract 10
                 ; this also sets the carry flag, which will be moved to the
                 ; low byte of the score, which is the "Rest" of the number
                 ; this carry represents adding 10 to the "Rest"
    sta $02      ; store the difference (new current digit) back in $02

; $02 (current digit) is less than #$0a, or has just been subtracted
; continue algorithm by shifting score left
continue_shift_score:
    rol $00      ; if just set $02 to digit by subtraction, this will put 1
                 ; in $00's lsb, signifying adding 10 to "Rest"
    rol $01      ; if $00's msb is 1, then it'll carry to the lsb of $01
    dey          ; Y goes from $10 to $00, once Y is $00, the algorithm is done
    bne shift_and_check_digit_carry
    rts
See Also
Converting a hexadecimal number to decimal can be done in multiple ways. A common algorithm for doing this is double dabble algorithm. Contra does not use this method. This is probably because the double dabble algorithm requires more CPU memory space, whereas Contra's algorithm uses the same, fixed 2 bytes of CPU memory (0x01 and 0x02) for all score calculation. Consequently, instead of a fixed number of operations like double dabble, Contra uses recursion, which requires a variable number of CPU cycle at the benefit of fixed memory usage.

Another interesting and related concept is the binary-coded decimal
User avatar
aa-dav
Posts: 220
Joined: Tue Apr 14, 2020 9:45 pm
Location: Russia

Re: Conta High Score Display Logic

Post by aa-dav »

Interesting. I knew method of substracting powers of 10 from number and counting iterations as digits before underflows. It requires array { 10000, 1000, 100, 10, 1 } for 16-bit values and seems to be longer and slower than subj.
Damn, it required a lot time for me to understand that 'double dabble algorithm' just recreates number in BCD format using power-of-two decomposition. That is each iteration is just multiplication by 2 (it could be better understood as sum of BCD number with itself, so idea behind BCD-corrections are more clear and easy to understand) and addition of 1 to form number as powers of twos which is nature of binary numbers.
However I still could not catch idea behind subj, but I need to give it more time.
User avatar
vermiceli
Posts: 12
Joined: Tue Nov 24, 2020 5:07 pm

Re: Conta High Score Display Logic

Post by vermiceli »

The double dabble algorithm was a little tricky for me to understand at first as well. There is a video by Numberphile on Youtube which helped me understand it quickly.

For the Contra score logic, I think it is most easily understood as "splitting the score". So, given a score of 12345, the algorithm really just updates the score memory address to 1234 and stores 5 in a separate memory address (0x02). Then the game knows to display 5 as the next digit on the screen. The algorithm can then be called again immediately and the score of 1234 will be split to 123 and 4.

The ingenuity (to me) is that 1234 and 5 really means (1234 * 10) + 5. So in the algorithm loop, whenever you subtract 10 from 0x02, shifting a 1 to the score is really shifting 10. This means that subtracting 10 from 0x02 and shifting 1 to 0x00 offset each other.
User avatar
aa-dav
Posts: 220
Joined: Tue Apr 14, 2020 9:45 pm
Location: Russia

Re: Conta High Score Display Logic

Post by aa-dav »

Aahhh... I got idea of subj.
It's core algorithm is divider by 10 almost like we do on the math lessons, but in binary system of course.
Then it 'tries to substract 10' it just seeks next columns of 'long division' digits suitable for /10. This columns cannot exceed binary 10000, so it need not to substract twice or more. But it is important to note, that 4 digits in example could not be enough.
Remainder as next digit is accumulated in ''right digit" field due to algorithm.

One thing I am amazed of binary division algorithm is that it can divide by zero and got something not silly bad (!).
In division by zero it produces results with all binary digits set to 1, that is closest to infinity result.
At the same time it produces remainder equal to dividend.
This is tricky thing because if we check result by formula of integer division check we get: (111...1111 * 0 + remainder = dividend) == true. :D
However such a remainder violates exact definition of math remainder, but algorithm do really tries to get as meaningful result as possible! :D
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Conta High Score Display Logic

Post by Oziphantom »

looks like this basically is doing division by Reciprocal Multiplication
score * 1/10 which gives you result + remainder. Where the Remainder is the digit you show and result is the next value.

So
123 * 1/10 = 12 | 3
12 * 1/10 = 1 | 2
1 * 1/10 = 0 | 1

More details on the algorithm in the general case here http://homepage.cs.uiowa.edu/~jones/bcd/divide.html
User avatar
aa-dav
Posts: 220
Joined: Tue Apr 14, 2020 9:45 pm
Location: Russia

Re: Conta High Score Display Logic

Post by aa-dav »

Oziphantom wrote: Thu Nov 26, 2020 9:31 pm looks like this basically is doing division by Reciprocal Multiplication
It's simple binary division algorithm with hardcoded divider.
Generalized algorithm is:

Code: Select all

N := dividend
D := divider
Q := 0 // result
R := 0 // remainder
for i := n − 1 .. 0 do // n - bits number
  R := R << 1           
  R(0) := N(i) ; operator(i) = i-th bit
  if R >= D then
    R := R − D
    Q(i) := 1
  end
end
So, as you can see they just hardcoded 10 in D (and also do some tricks as article metions)
And this is exactly like we divide on math lessons but in binary format (so couple of steps are simplified).
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Conta High Score Display Logic

Post by Oziphantom »

oh the bytes are backwards. So a Left shift is actually "shifting to the right" and hence a div 2 not a mul 2.
User avatar
aa-dav
Posts: 220
Joined: Tue Apr 14, 2020 9:45 pm
Location: Russia

Re: Conta High Score Display Logic

Post by aa-dav »

Oziphantom wrote: Thu Nov 26, 2020 10:30 pm oh the bytes are backwards. So a Left shift is actually "shifting to the right" and hence a div 2 not a mul 2.
No no, it's mul 2.
But it is more meaningful to perceive it as shift.
In fact we determine next possible digits for subdivision in "long division".
It's the same thing like in division of 510 by 20.
At first we decouple first divisible subdigits '51' to make subdivision of 40. By shifts we seek first subdigits bigger than divisor, that is divisible by it with possible remainder (or subremainder).
This is the same thing which happens here then it tries to substract 10, but it's more simple.
Post Reply