Displaying large numbers on the ZX Spectrum

Printing a number on screen requires transforming it to a series of digits in base-10 notation. It's not a big deal if the number is small enough to fit in a CPU register, and the CPU has a built-in division instruction: you have only to divide the number by 10, taking the remainder as a digit, and let the quotient to be the new number. Do this until the quotient is less than the divisor.

But, what if your CPU has no division instruction, and the number you try to convert is not an 8,16 or 32-bit value, but a 255-bit value? This routine shows you how it can be possible on a humble Z80 processor.



The challenge
Sábado, 19 de Agosto de 2006 00:00

This was posted at comp.sys.sinclair:

Could someone show me some Z80 assembly code that will display a N-byte
unsigned binary integer as a base 10 number in ASCII, for N<256?

I can't think how to do this using Decimal Adjust Accumulator rather
than long division.
 
The response
Martes, 22 de Agosto de 2006 00:00

It's not optimized for speed. I've been able to run it with numbers ranging from 8 byte-wide to 255 byte-wide. For a number consisting on 255 bytes, all of them with the value 255 (that is, 2^(255*8)-1 ), the computation took 3213,82 seconds (using Spectaculator). It can be checked using the online version of the GNU MP library

Here you have a screenshot after converting such number:

The routine is meant to be used from BASIC, as it returns the address of the first ASCII digit after conversion. Beware! because the algorithm I've written extracts digits from least significant to most significant, the number is stored in memory that way. That means that the address returned is the last address used to store de ASCII version of the number, and you have to walk downwards memory to retrieve the rest of the digits, until a NULL byte is found.

I think that the attached BASIC program will clarify what I've said. Machine code begins at 32768.

The algorithm:

The key for this method to work is to be able to divide an arbitrary number by 10, and give back both quotient and remainder. Remainder is a little number that can be held in a 8-bit register, and it's the least significant digit in decimal. The quotient becomes the new number to be divided, and the subsequent division leads to the following remainder, which becomes the next decimal digit. This continues until the number is 0.

For the division, I have based my code on the one listed at the Milos "baze" Bazelides page "Z80 bits" : http://map.tni.nl/sources/external/z80bits.html . More precisely, the algorithm for 16 bits / 8 bits unsigned division.

What in the original algorithm is a simple add hl,hl (hl contains the dividend-quotient), in my version it's a separate routine which uses shift/rotations to perform the same operation (in fact, multiply by 2 the whole number in memory). What in the algorithm is a "inc l", my version is a "inc (hl)" provided that HL points to the least significant byte of the number.

The loop at the Main procedure simply calls the routine to get a new remainder: converts it to an ASCII digit and store in the buffer pointed by DE. If the number is not zero, the loop continues. At the end, the final value of DE is transferred to BC to be available to the BASIC program, which prints the number peeking downwards memory until it reaches the NULL byte.

Source code

BASIC loader

10 CLEAR 32767
20 LOAD ""CODE
30 LET t1=PEEK 23672+256*PEEK 23673+65536*PEEK 23674
40 LET adr=USR 32768
50 LET t2=PEEK 23672+256*PEEK 23673+65536*PEEK 23674
60 LET digit=PEEK adr: IF digit THEN PRINT CHR$ digit;: LET adr=adr-1: GO TO 60
70 PRINT: PRINT "Conversion took ";(t2-t1)/50;" seconds."

For everyday use, you should get the address of NUMERO, and poke from it to put your number, little endian way. Poke NBYTES with the number of bytes your number , and finally, call the routine with something like "LET adr=USR 32768" to get on "adr" the address of the first (most significant) digit on your number.

Aseembler source code (compiled with PASMO 0.5.2)

This source code is regulated under the GNU license. Original division routine
(c)Milos "baze" Bazelides, ( 
 CLOAKING
  ) . Rest of code (c)Miguel Angel
Rodriguez Jodar ( 
 CLOAKING
  )

                 org 32768

Main             proc
                 ld de,CADENA

otro_digito      push de
                 call Obtener_Resto     ; Get next remainder
                 pop de
                 add a,'0'              ; Convert to an ASCII digit
                 ld (de),a              ; and store it
                 inc de
                 call Check_Cero                ; Is it the new dividend null?
                 jr nz,otro_digito      ; Go to get another digit if not null

                 dec de                 ; Fix end address
                 ld b,d                 ; And copy it to BC register
                 ld c,e
                 ret                    ; Return to BASIC
                 endp

Obtener_Resto     proc
                 ld a,(NBYTES)          ; A = number of bytes of the original
                                        ; number. We need number of bits, so we
                                        ; multiply it by 8.
                 ld l,a
                 ld h,0
                 add hl,hl
                 add hl,hl
                 add hl,hl
                 ex de,hl               ; DE = number of bits of the original  
                                        ; number
                 ld c,10                        ; C holds the divisor.
                 ld hl,NUMERO           ; HL points to the dividend/quotient
                 xor a                  ; Reset remainder

buc_div          push hl                 ; This is, esencially, the same
                                        ; algorithm from Milos Bazelides, with
                                        ; the changers detailed above.
                 call Mult_2            ; The "old" ADD HL,HL
                 pop hl
                 rla
                 cp c
                 jr c,no_incr
                 sub c
                 call Increm             ; The "old" INC L
no_incr          dec de
                 push af
                 ld a,d
                 or e
                 jr z,fin_div
                 pop af
                 jr buc_div

fin_div          pop af
                 ret
                 endp

Increm           proc
                 ld hl,NUMERO
                 inc (hl)
                 ret
                 endp

Mult_2           proc
                 ld hl,NBYTES
                 ld b,(hl)
                 ld hl,NUMERO

                 sla (hl)
                 inc hl
                 dec b
                 ret z

buc_desplaza     rl (hl)
                 inc hl
                 djnz buc_desplaza

                 ret
                 endp

Check_Cero       proc
                 ld hl,NUMERO
                 ld a,(NBYTES)
                 ld b,a

check_byte       ld a,(hl)
                 or a
                 jr nz,no_cero
                 inc hl
                 djnz check_byte
                 xor a
no_cero          ret
                 endp

;Variables
NUMERO           ds 255,255    ; 255 bytes filled with the value 255. Little
                              ; endian notation. This is the largest number this routine can manage
(although it's possible that it can deal with 256 byte-wide numbers
NBYTES           db 255        ; how many bytes comprises our number
                 db 0          ; NULL byte to mark end of the converted number
CADENA           equ $         ; here will be the ASCII code of the least
                              ; significant digit of the converted number. 
 


ZX Projects, Powered by Joomla! and designed by SiteGround web hosting