Phil Pilgrim (PhiPi)

01-27-2008, 06:02 AM

I needed a division routine that divides a 64-bit unsigned dividend by a 32-bit unsigned divisor to return a 32-bit quotient and 32-bit remainder, leaving the original carry bit unchanged. The only limitation would have to be that the high long of the dividend be less than the divisor (i.e. no overflow). I couldn't find a routine like this in the forum or in the object exchange (although I'm sure that deSilva, who has a memory like a steel trap, can point to one immediately). Here's the code I came up with:

'Divide ra:rb by rx, leaving quotient in rb, remainder in ra, and rx unchanged.

'Precondition: ra < rx.

divabx mov cctr,#32 'Initialize loop counter.

:loop rcl rb,#1 wc 'Rotate quotient bit in from carry,

rcl ra,#1 wc ' and rotate dividend out to carry

if_c sub ra,rx 'rx < carry:ra if carry set, so just subtract, leaving carry set.

if_nc cmpsub ra,rx wc 'Otherwise, use cmpsub to do the dirty work.

djnz cctr,#:loop 'Back for more.

rcl rb,#1 wc 'Rotate last quotient bit into place, restoring original carry.

divabx_ret ret

It's pretty straightforward, except for the inconvenient fact that cmpsub doesn't treat the carry flag as a most-significant bit when doing its comparison; so that condition has to be tested separately. (The consequence of this behavior for division routines that use cmpsub exclusively is that the high bit of the divisor must be zero.) The original carry bit simply propagates through rb and back out again, so is preserved.

Exclusive of the call and return, this routine takes 8.2µs to execute with an 80MHz clock.

-Phil

'Divide ra:rb by rx, leaving quotient in rb, remainder in ra, and rx unchanged.

'Precondition: ra < rx.

divabx mov cctr,#32 'Initialize loop counter.

:loop rcl rb,#1 wc 'Rotate quotient bit in from carry,

rcl ra,#1 wc ' and rotate dividend out to carry

if_c sub ra,rx 'rx < carry:ra if carry set, so just subtract, leaving carry set.

if_nc cmpsub ra,rx wc 'Otherwise, use cmpsub to do the dirty work.

djnz cctr,#:loop 'Back for more.

rcl rb,#1 wc 'Rotate last quotient bit into place, restoring original carry.

divabx_ret ret

It's pretty straightforward, except for the inconvenient fact that cmpsub doesn't treat the carry flag as a most-significant bit when doing its comparison; so that condition has to be tested separately. (The consequence of this behavior for division routines that use cmpsub exclusively is that the high bit of the divisor must be zero.) The original carry bit simply propagates through rb and back out again, so is preserved.

Exclusive of the call and return, this routine takes 8.2µs to execute with an 80MHz clock.

-Phil