User:TakuikaNinja/Binary-coded decimal

From NESdev Wiki
Jump to navigationJump to search

Binary-coded decimal (BCD) is a format used to store decimal numbers in binary systems, usually so it can be easily displayed on a graphical interface. On most processors implementing BCD arithmetic, BCD values are added/subtracted in binary and the result is corrected to BCD using a special instruction (e.g. DAA/DAS on x86). On the 6502 and its successors, however, a special flag called the decimal flag is used to toggle automatic BCD arithmetic on the ADC/SBC instructions (and nothing else).[1] This flag allows one to accomplish BCD arithmetic trivially using code such as the following:

  sed ; set decimal flag
  lda #$23
  clc
  adc #$50 ; = $73
  sec
  sbc #$04 ; = $69
  sta Sum ; ONLY the carry flag is valid after BCD arithmetic on the original 6502, 
  lda Sum ; so reload the value to get the zero/negative flags! (fixed on 65C02/65816)
  cld ; don't forget to clear the decimal flag once we're done!

Unfortunately, the NES CPU does not have that luxury as the BCD logic is disconnected within the die. The remainder of this article will discuss workarounds for BCD arithmetic without a working decimal flag. These come at the cost of increased code size, cycle counts, and memory usage. Software BCD arithmetic is often implemented using a set of generic routines and/or macros to assist with abstraction.

Programmers may prefer to keep numbers in binary format and manually convert them to BCD format for display purposes instead:

  • 16-bit BCD - An efficient 16-bit binary to decimal converter
  • Base 100 - Alternate method of storing numbers, with simpler logic for arithmetic and BCD conversion

Unpacked BCD

Unpacked BCD stores each BCD digit ($00~$09) as individual bytes. This has the advantage of simplifying the logic for doing arithmetic on these numbers and displaying them. However, this wastes some amount of memory as the upper nybble will be unused for each digit. Super Mario Bros., Dr. Mario, and many other games use this format. The logic for unpacked BCD arithmetic is identical to that of base 100, simply requiring a change to base 10.

Packed BCD

Packed BCD stores 2 BCD digits as nybbles within a single byte ($00~$99, no A~F nybbles), and is the format normally used in BCD arithmetic. This reduces memory usage but requires careful logic when it comes to doing arithmetic on these numbers without the decimal flag. Tetris (Nintendo) uses this format but notably suffers from inaccuracies and performance issues due to a flawed implementation of packed BCD arithmetic.[2] There are two methods of implementing BCD arithmetic in this scheme.

Base 100 conversion

One option is to convert the BCD bytes to base 100, do arithmetic on them, and convert them back to BCD format. However, it would be better to use base 100 all of the time instead.

This routine takes in a packed BCD byte and converts it to binary form:

; Parameter: A = BCD value to decode
; Stores the hexadecimal value in Res
; Returns the hexadecimal value in A
; (result is also a valid base 100 value)
BCDToByte:
  pha ; save value for later
  and #$F0 ; letting x = 10's digit, convert 16x to 10x
  lsr a
  sta Res ; 16x/2
  lsr a
  lsr a ; 16x/8
  adc Res ; 16x/8 + 16x/2
  sta Res ; = 10x
  pla ; retrieve and add low nybble to result
  and #$0F
  adc Res ; carry is always clear
  sta Res
  rts

Unpacking

Another option is to unpack the digits of each BCD byte into nybbles, do arithmetic on them, and pack the result back into bytes. This way, similar logic as unpacked BCD can be used.

This snippet demonstrates the unpacking process:

  lda Val
  and #%11110000
  sta HiDigit ; = %xxxx0000
  eor Val
  sta LoDigit ; = %0000xxxx

Repacking the value is a simple bitwise OR operation:

  lda HiDigit ; must be %xxxx0000
  ora LoDigit ; must be %0000xxxx
  sta Res

Multiply/Divide by powers of 10

One advantage of BCD is that multiplication and division by powers of 10 are trivial to implement, and does not require a working decimal flag.

Unpacked

To multiply/divide packed BCD bytes by powers of 10, simply shift them left/right by one byte and place a zero at the opposite end for each power of 10.

Packed

To multiply/divide packed BCD bytes by 10, simply shift them left/right by four bits (one nybble) using a sequence of shift and rotate instructions:

; multiply 16-bit packed BCD value by 10
  asl Val ; shift d7 into carry
  rol Val+1 ; rotate carry into d0
  asl Val ; repeat
  rol Val+1
  asl Val
  rol Val+1
  asl Val
  rol Val+1

; divide 16-bit packed BCD value by 10
  lsr Val+1 ; shift d0 into carry
  ror Val ; rotate carry into d7
  lsr Val+1 ; repeat
  ror Val
  lsr Val+1
  ror Val
  lsr Val+1
  ror Val

To multiply/divide packed BCD bytes by 100, simply shift them left/right by one byte and place a zero at the opposite end for each power of 100, similar to unpacked BCD. Arbitrary powers of 10 can be accounted for by applying byte shifts for each power of 100, then applying a nybble shift if a power of 10 remains.

References

  1. 6502 decimal mode tutorial
  2. Applying Artificial Intelligence to Nintendo Tetris: Breakdown of the flawed BCD addition routine in Tetris (Nintendo).