21 Jan
2008
21 Jan
'08
6:29 p.m.
Date: Sun, 20 Jan 2008 20:57:27 -0800
From: Brent Hilpert <hilpert at cs.ubc.ca>
Subject: Re: div by 10 on Z80 was RE: Reading Polymorphic ---
(I expect you may have noticed already..) the
subroutine (div10s) is
only called once now, you could inline it to save another 4 bytes.
You can do a bit better with that and by using the carryout to form
the quotient bits:
div10:
xor a
ld de,0fd80h ; largest power of 2 times 10 less then 800d
ld b,07 ; only seven loops needed to finish divide 80
divloop:
add hl,de ; trial subtract
jr c,div10s1 ; carry means trial passed
sbc hl,de ; undo previous add, carry is clear
div10s1:
rl a
add hl,hl ; shift number to reuse same constant, 640 decimal
djnz divloop
add hl,hl ; push full remainder in HL
ret
Again, I haven't tried it out, but it should work.
Cheers,
Chuck
21 Jan
21 Jan
6:41 p.m.
New subject: Subject: Re: div by 10 on Z80
Chuck Guzis wrote:
div10:
xor a
ld de,0fd80h ; largest power of 2 times 10 less then 800d
ld b,07 ; only seven loops needed to finish divide 80
divloop:
add hl,de ; trial subtract
jr c,div10s1 ; carry means trial passed
sbc hl,de ; undo previous add, carry is clear
div10s1:
rl a
add hl,hl ; shift number to reuse same constant, 640 decimal
djnz divloop
add hl,hl ; push full remainder in HL
ret
Again, I haven't tried it out, but it should work.
Every time I see code like this for processors without a native DIV, I
wonder if the same code ported to x86 would indeed outperform the native
DIV. Would it? I know that on a 286 or higher, where MUL and DIV were
greatly optimized to about 12 cycles, no; but what about on the original
808x, where MUL/DIV could take as much as 144 cycles?
--
Jim Leonard (trixter at oldskool.org) http://www.oldskool.org/
Help our electronic games project: http://www.mobygames.com/
Or check out some trippy MindCandy at http://www.mindcandydvd.com/
A child borne of the home computer wars: http://trixter.wordpress.com/
22 Jan
22 Jan
3:08 a.m.
New subject: Subject: Re: div by 10 on Z80
Date: Mon, 21 Jan 2008 12:41:31 -0600
From: trixter at oldskool.org
To: General at mail.mobygames.com
CC:
Subject: Re: Subject: Re: div by 10 on Z80
Chuck Guzis wrote:
Most likely not for the 800/10 problem but things like 28/3 might be
small enough to be worth the clock cycles. Most any power of two
problem can be done faster in code than the divide instruction.
The one we have now, on a Z80, looks like 428 to 463 clock cycles
to deal with the zero to 799 divided by 10.
Dwight
_________________________________________________________________
Helping your favorite cause is as easy as instant messaging.?You IM, we give.
http://im.live.com/Messenger/IM/Home/?source=text_hotmail_join
div10:
xor a
ld de,0fd80h ; largest power of 2 times 10 less then 800d
ld b,07 ; only seven loops needed to finish divide 80
divloop:
add hl,de ; trial subtract
jr c,div10s1 ; carry means trial passed
sbc hl,de ; undo previous add, carry is clear
div10s1:
rl a
add hl,hl ; shift number to reuse same constant, 640 decimal
djnz divloop
add hl,hl ; push full remainder in HL
ret
Again, I haven't tried it out, but it should work.
Every time I see code like this for processors without a native DIV, I
wonder if the same code ported to x86 would indeed outperform the native
DIV. Would it? I know that on a 286 or higher, where MUL and DIV were
greatly optimized to about 12 cycles, no; but what about on the original
808x, where MUL/DIV could take as much as 144 cycles? 
23 Jan
23 Jan
11:25 p.m.
New subject: Subject: Re: div by 10 on Z80
On Mon, 21 Jan 2008, Jim Leonard wrote:
Every time I see code like this for processors without
a native DIV, I
wonder if the same code ported to x86 would indeed outperform the native
DIV. Would it? I know that on a 286 or higher, where MUL and DIV were
greatly optimized to about 12 cycles, no; but what about on the original
808x, where MUL/DIV could take as much as 144 cycles?
On the 8088, an enormous amount of time is spent fetching instructions -
so much so that AAM will usually outperform DIV
24 Jan
24 Jan
12:01 a.m.
New subject: Subject: Re: div by 10 on Z80
Fred Cisin wrote:
On Mon, 21 Jan 2008, Jim Leonard wrote:
You lost me, on several levels :-) For one, that was part of my
question: since even a specialized "manual" DIV will be 10-20
instructions, that's 40-80 cycles lost right there just fetching
opcodes... so would it truly be faster than a regular DIV?
Second point I got lost: How would AAM be used instead of DIV? I
thought AAM was ASCII Adjust for Multiplication and was used to unpack
packed decimals or something. Is AAM good for a trick or two I don't
know about? If so, is it faster than DIV? (and if so, why?)
--
Jim Leonard (trixter at oldskool.org) http://www.oldskool.org/
Help our electronic games project: http://www.mobygames.com/
Or check out some trippy MindCandy at http://www.mindcandydvd.com/
A child borne of the home computer wars: http://trixter.wordpress.com/
Every time I see code like this for processors
without a native DIV, I
wonder if the same code ported to x86 would indeed outperform the native
DIV. Would it? I know that on a 286 or higher, where MUL and DIV were
greatly optimized to about 12 cycles, no; but what about on the original
808x, where MUL/DIV could take as much as 144 cycles?
On the 8088, an enormous amount of time is spent fetching instructions -
so much so that AAM will usually outperform DIV
12:15 a.m.
New subject: Subject: Re: div by 10 on Z80
Jim Leonard wrote:
Second point I got lost: How would AAM be used instead
of DIV? I
thought AAM was ASCII Adjust for Multiplication and was used to unpack
packed decimals or something. Is AAM good for a trick or two I don't
know about? If so, is it faster than DIV? (and if so, why?)
Sorry, 15 more minutes of research turned this up:
http://www.x86.org/secrets/opcodes/aam.htm
--
Jim Leonard (trixter at oldskool.org) http://www.oldskool.org/
Help our electronic games project: http://www.mobygames.com/
Or check out some trippy MindCandy at http://www.mindcandydvd.com/
A child borne of the home computer wars: http://trixter.wordpress.com/
12:31 a.m.
New subject: Subject: Re: div by 10 on Z80
> On the 8088, an enormous amount of time is spent
fetching instructions -
> so much so that AAM will usually outperform DIV
On Wed, 23 Jan 2008, Jim Leonard wrote:
You lost me, on several levels :-) For one, that was
part of my
question: since even a specialized "manual" DIV will be 10-20
instructions, that's 40-80 cycles lost right there just fetching
opcodes... so would it truly be faster than a regular DIV?
Second point I got lost: How would AAM be used instead of DIV? I
thought AAM was ASCII Adjust for Multiplication and was used to unpack
packed decimals or something. Is AAM good for a trick or two I don't
know about? If so, is it faster than DIV? (and if so, why?)
AAM is typically the same speed as DIV, but requires fewer bytes, which is
a big issue for 8088, and little else.
Yes, AAM (which is a two byte instruction) takes the value in AL, divides
it by 10, and places the quotient in AH, and the remainder in AL (which is
the opposite of the destination registers of DIV)
BTW, the second byte of AAM ia OAh. (ten decimal).
Guess what happens if you replace that byte with another value!
(watch out for prefetch buffer length!)
25 Jan
25 Jan
1:21 a.m.
New subject: Subject: Re: div by 10 on Z80
Every time I see code like this for processors without
a native DIV, I
wonder if the same code ported to x86 would indeed outperform the native
DIV. Would it? I know that on a 286 or higher, where MUL and DIV were
greatly optimized to about 12 cycles, no; but what about on the original
808x, where MUL/DIV could take as much as 144 cycles?
In 286 and 386 you could usually beat IDIV when dividing by small
constants especially if you knew your dividend was of less than the
full range of the possible register values.
On a 386 you could play tricks with LEA that could shave off cycles.
I seem to barely remember a technique for dividing by 10 in which the
first two instructions were of the form LEA EAX,[EAX+EAX*4] to
multiply the dividend by 25 (2 cycles each)... I can't remember the
tricks that follow that. Overall it was probably "multiply by
approximately 25.6 then right shift by 8 bits". I can't for the life
of me remember in what bit of code I saw it. I could probably write
it from scratch given what I've remembered so far.
Eric
4 a.m.
New subject: Subject: Re: div by 10 on Z80
From: korpela at ssl.berkeley.edu
Based on an email I just had from the cpm news group, I thought
it might be fun to write some Z80 code to do the 0 to 799 as fast
as one could, with no size restriction. Just clocks count.
Dwight
_________________________________________________________________
Shed those extra pounds with MSN and The Biggest Loser!
http://biggestloser.msn.com/
Every time I see code like this for processors
without a native DIV, I
wonder if the same code ported to x86 would indeed outperform the native
DIV. Would it? I know that on a 286 or higher, where MUL and DIV were
greatly optimized to about 12 cycles, no; but what about on the original
808x, where MUL/DIV could take as much as 144 cycles?
In 286 and 386 you could usually beat IDIV when dividing by small
constants especially if you knew your dividend was of less than the
full range of the possible register values.
4:25 a.m.
New subject: Subject: Re: div by 10 on Z80
On Jan 24, 2008 8:00 PM, dwight elvey <dkelvey at hotmail.com> wrote:
Based on an email I just had from the cpm news group,
I thought
it might be fun to write some Z80 code to do the 0 to 799 as fast
as one could, with no size restriction. Just clocks count.
Dwight
No size restriction at all? Can you do any faster than table lookup?
But that's probably not in the true spirit of what you had in mind.
5:12 a.m.
New subject: Subject: Re: div by 10 on Z80
From: glen.slick at gmail.com
On Jan 24, 2008 8:00 PM, dwight elvey wrote:
Hi
That would be valid but for now, lets also do some coding.
Partial table would be OK. I'll have to admit that the table
lookup would beat anything I was thinking of. Still, good
thinking. That is why I asked the question.
dwight
_________________________________________________________________
Climb to the top of the charts!?Play the word scramble challenge with star power.
http://club.live.com/star_shuffle.aspx?icid=starshuffle_wlmailtextlink_jan
Based on an email I just had from the cpm news
group, I thought
it might be fun to write some Z80 code to do the 0 to 799 as fast
as one could, with no size restriction. Just clocks count.
Dwight
No size restriction at all? Can you do any faster than table lookup?
But that's probably not in the true spirit of what you had in mind. 
4:29 a.m.
New subject: Subject: Re: div by 10 on Z80
dwight elvey wrote:
There is a trivial solution: a look up table.
add hl,hl ; double it
ld de,table ; base addr of table
add hl,de ; index
ld a,(hl) ; pick up quotient
...
table db 0,0 ; 0: quotient, remainder
db 0,1 ; 1
db 0,2
db 0,3
etc
From: korpela
at ssl.berkeley.edu
Based on an email I just had from the cpm news group, I thought
it might be fun to write some Z80 code to do the 0 to 799 as fast
as one could, with no size restriction. Just clocks count. Every time I see code like this for processors
without a native DIV, I
wonder if the same code ported to x86 would indeed outperform the native
DIV. Would it? I know that on a 286 or higher, where MUL and DIV were
greatly optimized to about 12 cycles, no; but what about on the original
808x, where MUL/DIV could take as much as 144 cycles?
In 286 and 386 you could
usually beat IDIV when dividing by small
constants especially if you knew your dividend was of less than the
full range of the possible register values.
4:42 a.m.
New subject: Subject: Re: div by 10 on Z80
Jim Battle wrote:
oops, I accidentally deleted the tail end of my program during editing. add
inc hl
ld h,(hl)
after the last instruction above to fetch the remainder
dwight elvey wrote:
...
Based on an
email I just had from the cpm news group, I thought
it might be fun to write some Z80 code to do the 0 to 799 as fast
as one could, with no size restriction. Just clocks count.
There is a trivial solution: a look up table.
add hl,hl ; double it
ld de,table ; base addr of table
add hl,de ; index
ld a,(hl) ; pick up quotient
...
table db 0,0 ; 0: quotient, remainder
db 0,1 ; 1
db 0,2
db 0,3
etc
4:53 a.m.
New subject: Subject: Re: div by 10 on Z80
After doing the "fastest" possible implementation, I realized that
Dwight's "smallest" code is far from the smallest. Behold the trivial
solution on the other end of the spectrum:
div10:
ld de,-10 // divisor
xor a // quotient accumulator; clear carry
loop:
inc a
add hl,de
jr c,loop
sbc hl,de ; undo last subtraction; remainder in L
dec a ; we looped one time too many
That is 11 bytes. It is slow as dirt, but if the game is smallest wins,
then this is doing better than your current 16 byte program.
5:28 a.m.
New subject: Subject: Re: div by 10 on Z80
From: frustum at pacbell.net
After doing the "fastest" possible implementation, I realized that
Dwight's "smallest" code is far from the smallest. Behold the trivial
solution on the other end of the spectrum:
div10:
ld de,-10 // divisor
xor a // quotient accumulator; clear carry
loop:
inc a
add hl,de
jr c,loop
sbc hl,de ; undo last subtraction; remainder in L
dec a ; we looped one time too many
That is 11 bytes. It is slow as dirt, but if the game is smallest wins,
then this is doing better than your current 16 byte program.
Hi Jim
I like this. If I'm that pressed for space, I'll use this.
It isn't all that bad on average. It is about 1110 clocks
for the average.
Here is my Idea of the fastest code without table lookup
just for fun:
; 0-799 divided by 10
; hl = dividend
; Returns:
; h = quotient
; a = remainder
ld d,h
ld e,l
add hl,hl
add hl,hl
add hl,de
add hl,hl
ld b,h
ld c,l
add hl,hl
add hl,hl
add hl,bc
add hl,de
ld a,h
rra
ld l,a
ld h,#0
ld c,a
ld b,h
add hl,hl
add hl,hl
add hl,bc
add hl,h,
ex de,hl
sbc hl,de
ld c,#-10
ld h,a
ld a,l
add a,c
jr c,d10f1
sub a,c
ret
d10f1:
inc h
ret
Worst case clocks is 239 ( by my count )
Now, if someone can comment the code!!
Dwight
_________________________________________________________________
Connect and share in new ways with Windows Live.
http://www.windowslive.com/share.html?ocid=TXT_TAGHM_Wave2_sharelife_012008
22 Jan
22 Jan
2:30 a.m.
From: cclist at sydex.com
Hi chuck
I think the restore operation will cause a carry meaning I need
to clear it here with something like:
ora a ; or other carry clearing instruction
If someone has a debugger running, they might check this
but it does look as though the SBC will cause a carry that needs to be
cleared. The result of the add hl,de that didn't create a carry left
a negative number that will be modified back to a positive
number with a subtract. I'm relatively sure that creates a
carry.
Still, it removes one instruction from the outer loop which is 4
cycles time 7. That is 28 clocks!
This is great. Fine tuning this has been fun.
div10:
xor a
ld de,0fd80h ; largest power of 2 times 10 less then 800d
ld b,07 ; only seven loops needed to finish divide 80
divloop:
add hl,de ; trial subtract
jr c,div10s1 ; carry means trial passed
sbc hl,de ; undo previous add, carry is set??
ora a ; clears carry
div10s1:
rl a
add hl,hl ; shift number to reuse same constant, 640 decimal
djnz divloop
add hl,hl ; push full remainder in HL
ret
Dwight
_________________________________________________________________
Shed those extra pounds with MSN and The Biggest Loser!
http://biggestloser.msn.com/
Date: Sun, 20 Jan 2008 20:57:27 -0800
From: Brent Hilpert
Subject: Re: div by 10 on Z80 was RE: Reading Polymorphic ---
(I expect you may have noticed already..) the
subroutine (div10s) is
only called once now, you could inline it to save another 4 bytes.
You can do a bit better with that and by using the carryout to form
the quotient bits:
div10:
xor a
ld de,0fd80h ; largest power of 2 times 10 less then 800d
ld b,07 ; only seven loops needed to finish divide 80
divloop:
add hl,de ; trial subtract
jr c,div10s1 ; carry means trial passed
sbc hl,de ; undo previous add, carry is clear
6182
days inactive
6186
days old
15 comments
7 participants
participants (7)
-
cclist＠sydex.com -
cisin＠xenosoft.com -
dkelvey＠hotmail.com -
frustum＠pacbell.net -
glen.slick＠gmail.com -
korpela＠ssl.berkeley.edu -
trixter＠oldskool.org