- Division in z80 assembly
- 10 Oct 2012 07:36:39 am
- Last edited by Xeda112358 on 13 Nov 2012 04:12:21 pm; edited 2 times in total
(sorry for the horrible formatting, I couldn't figure out how to make a monospaced font)
In z80 assembly, the division algorithms you might have seem probably seem unintuitive. But guess what? They are usually a variation on long division that you learned in school, but modified for binary. In my experience, math in binary is so much easier and faster than in base 10, so here is an example. Let's try to divide 85 by 3:
(Note: 3=11b and 85=1010101b. The math in this example is all done in binary)
Code:
We have a remainder of 1, and the quotient is 11100 which is 28. 28*3=84, add 1 and you have 85. Now how do we implement this in pseudocode?
P is the numerator
Q is the denominator
(we are essentially doing P/Q, then)
Let B be the number of bits
Let C be the remainder between each step
Let A be the accumulator
Code:
But what would this look like in assembly? Here is an example:
Code:
This works, but can we optimise it for the z80? Of course! Note that the registers E and C are 8 bits. Since we are shifting a bit out of E each time, we can use that doubly as an accumulator. here is what I mean:
Code:
This routine is pretty good for D/E/ How good? 14 bytes and 344+3b cycles (where b is at most 8) This can basically execute over 17000 times a second at 6MHz, over 43000 at 15MHz.
I hope this helps people!
In z80 assembly, the division algorithms you might have seem probably seem unintuitive. But guess what? They are usually a variation on long division that you learned in school, but modified for binary. In my experience, math in binary is so much easier and faster than in base 10, so here is an example. Let's try to divide 85 by 3:
(Note: 3=11b and 85=1010101b. The math in this example is all done in binary)
Code:
________
11|1010101
Now you check if 11≤1. It isn't, so you have a zero:
0_______
11|1010101
Now you check if 11≤10. It isn't, so you have another zero:
00______
11|1010101
Now you check if 11≤101. It is, so you subtract 101-11 to get 10.
001_____
11|1010101
10
Now you check if 11≤100. It is, so you subtract 100-11 to get 1.
0011____
11|1010101
10
1
Now you check if 11≤11. It is, so you subtract 11-11 to get 0.
00111___
11|1010101
10
1
0
Now you check if 11≤00. It isn't, so you put a zero up top.
001110__
11|1010101
10
1
0
Now shift in the last bit, a 1.Since 11≤01 is not true, we have a zero.
0011100_
11|1010101
10
1
0
We have a remainder of 1, and the quotient is 11100 which is 28. 28*3=84, add 1 and you have 85. Now how do we implement this in pseudocode?
P is the numerator
Q is the denominator
(we are essentially doing P/Q, then)
Let B be the number of bits
Let C be the remainder between each step
Let A be the accumulator
Code:
0→C
0→A
Loop:
A<< (I mean to say, shift A left, also the same as multiply by 2)
Q<<C (I mean to say, shift Q left, shifting the carry into C
If C≤P
C-P→C
A++ (increment A. Since A was multiplied by 2, the last bit would be zero. This sets it to 1)
B--
If B
Goto Loop
But what would this look like in assembly? Here is an example:
Code:
;we will do D/E
xor a ;0→C we let A be the remainder
ld bc,0800h ;8→B, 0→A We let C be the accumulator
Loop:
sla c ;A<<
rl e \ rla ;Q<<C
cp d ;If C≤P
jr nc,$+4
sub d ;C-P→C
inc c ;A++
djnz Loop ;B-- \ If B \ Goto Loop
ret
This works, but can we optimise it for the z80? Of course! Note that the registers E and C are 8 bits. Since we are shifting a bit out of E each time, we can use that doubly as an accumulator. here is what I mean:
Code:
;we will do D/E
xor a ;0→C we let A be the remainder
ld b,8 ;8→B we will let Q be the accumulator
Loop:
rl e \ rla ;Q<<C, also A<<
cp d ;If C≤P
jr nc,$+4
sub d ;C-P→C
inc e ;A++
djnz Loop ;B-- \ If B \ Goto Loop
ret
This routine is pretty good for D/E/ How good? 14 bytes and 344+3b cycles (where b is at most 8) This can basically execute over 17000 times a second at 6MHz, over 43000 at 15MHz.
I hope this helps people!
In my spare time, I am developing a document that goes in depth on every aspect of z80 assembly coding that I can think about. Only pieces of it will be released, I am sure, but division has yet to make it in there. I couldn't think of a clear way to explain it before, but I will probably use this. 
I am worried about doing something like dividing by .5 (which is multiplying by 2) or anything else like that, so feel free to report back! 
