Hacker News Reader

Comment by userbinator | Hacker News Reader

Anyone who has played the old arcade games with fixed-width score counters will have seen this trick in action --- many of those ran on 8-bit processors without multiply or divide instructions, so it was much easier to keep the score as an array of digits and increment those than a binary variable and the equivalent of an itoa() every time it needed to be displayed.

More succinctly, in pseudocode:

    while(++digits[i] > '9')
        digits[i--] = '0';

By starting the increment at the non-rightmost digit, it also allows for easy addition of powers of 10: 10, 100, 1000, etc.

View on HN

Related to this is binary coded decimal [1]: let each nibble (4 bits) of your integer represent a decimal digit 0-9. Then do your arithmetic in binary, but after each operation run a special CPU instruction to "correct" the result to what it should be in decimal.

[1] https://en.wikipedia.org/wiki/Binary-coded_decimal

There are two BCD formats. Packed (what you describe) and unpacked (where only a single digit is stored per byte). Unpacked seems to have the advantage that converting to ASCII is just a matter of setting two bits, and converting from ASCII is just a matter of masking those out.

I found this example very illuminating

    sub    AH,AH    ; clear AH
    mov    AL,'6'   ; AL := 36H
    add    AL,'7'   ; AL := 36H+37H = 6DH
    aaa             ; AX := 0103H
    or     AL,30H   ; AL := 33H

because aaa instruction clears the high nibble of AL, it works with either unpacked BCD or with ASCII (but always outputs BCD).

http://service.scs.carleton.ca/sivarama/asm_book_web/Instruc... (page 8)

But iiuc aaa didn't make it in the transation to 64bit processors.

The Game Boy CPU kept track of nibble overflows and had an instruction called DAA to adjust the packed BCD value in the A register after an arithmetic operation. If you disable this instruction in an emulator many games start counting your score in hexadecimal (Tetris even has the sprites A to F interestingly, so you actually get your full score displayed correctly).

The Game Boy "had" this DAA instruction from its CPU, a variant of the Z80. This trick may well have been used also on some Amstrad CPC games also, then.

Indeed, the Z80 itself, which people like us know because it was very common in 8bit home computers, is an enhancement of the Intel 8080, which itself is an ancestor of the current Intel CPUs.

Incidentally, Z80 CPUs are still manufactured 40+ years later ( https://en.wikipedia.org/wiki/Zilog_Z80 ) and benefit from modern C compilers like SDCC and software development environments like z88dk or the one I wrote for the Amstrad CPC: https://github.com/cpcitor/cpc-dev-tool-chain (written for Linux and tools like GNU make, wget, etc).

That said, writing C code that compiles to packed BCD and the use of DAA at assembly level does not seem very practical. If few numbers are manipulated, unpacked BCD is simpler (closer to string, less code to handle) both in assembly and in C.

Some CPUs like the Saturn from Hewlett-Packard [1] are designed for BCD. Though they can perform binary operations, registers are structured for 64-bit floating point operations with a 4-bit wide bus and nibble-granularity addressing of register nibbles: 1 sign, 12 mantissa, 3 exponent.

[1] https://en.wikipedia.org/wiki/HP_Saturn

Reply on news.ycombinator.com