User:TakuikaNinja/Binary-coded decimal
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 d1 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
- ↑ 6502 decimal mode tutorial
- ↑ Applying Artificial Intelligence to Nintendo Tetris: Breakdown of the flawed BCD addition routine in Tetris (Nintendo).