Does anyone have a good reference for something to convert a long as if
it were an unsigned long to a string. Even better, one that allows me
to convert it to a number of bases (hex, octal, binary)
It is easy to write signed routines if you have unsigned operators but
not the reverse.
The easy way is to convert it to a BigInteger and let it worry out it.
The core of converting long to string is a division /modulus by 10,
peeling of one digit from the left each time. See any into forth book
on how it works.
You can divide a long number by a small one in stages, mimicing what
you do with long division. I wrote an assembler routine that does it,
pretty tough slugging though the notes may help.
Here is a multiprecision divide.
Not something you want to do just to avoid big int.
This code is for a 16 bit 8086. your code can be simpler since it
only has to work for a divisor of 10, a small number.
Also, since 10 = 8+2, you might think about how you could do division
with shifts and substracts.
CHEAD plainFL,UMSLMOD,"UM/MOD",FORTH
; ( DON'T CONFUSE THIS WITH MU/MOD !!!)
; unsigned divide
; ( numerator-64 divisor-32 -- rem-32 quot-32 : unsigned floored
)
; Divide by 0 is officially an error but it is handled
; by returning two 0s as a result.
; On overflow you just get the low order part of the quotient.
; Wasn't I kind?
; c.f. MU/MOD which gives 64-bit quotient
COMMENT |
Division is complicated, but in many ways it is just a
mechanization of long division you learned in grade 4. The only
difference is that we are using base s=2^16 instead of base 10
numbers. In long division you make a guess at the quotient then
multiply out then subtract to see how good your guess was. If
the guess was too big, we try a smaller number. Knuth in The
Art Of Computer Programming Vol 2 - Seminumerical Algorithms
pages 229-248 discusses the problem of multiprecision
arithmetic.
The worst case is analogous to dividing a 4 digit number by a 2
digit number, where the answer is guaranteed to be no more than
2 digits. The Forth-83 standard says it is an error if the
quotient would overflow. Forth-83 says we are not supposed to
carry on and compute the low order portion of the overflowed
quotient and the remainder. But since UM/MOD is used in MOD,
this seems unreasonable, so what I do is calculate the low order
2 digits of the quotient in case of overflow and push 0s in case
of divide by 0. This is a little friendlier than letting the
divide-by-0 or overflow interrupt take care of it.
The overflow can be detected early in the game and is handled by
UM/MOD-OVL high level code so we don't have to ever handle the
case of more than "2-digits" in the quotient. We can tell right
at the start if we will have overflow by comparing the high
order 2 digits with the two digits of the divisor. If they are
greater or equal to the divisor, we will have trouble.
Note that MU/MOD does let you get a "4-digit" quotient, but it
works by using UM/MOD twice.
In real life, most of the time the dividend and divisor will
have lots of leading zeroes. Then we may collapse the problem
to dividing by a 1 digit number. If the problem collapses to
dividing a 1 or 2 digit by a 1 digit, in most cases this can be
done with the DIV machine instruction that can divide 32 bits by
16 bits so long as the quotient is under 16 bits. Again we can
tell ahead of time if we are safe by comparing high order digit
of the dividend with the 1-digit divisor. If it is greater or
equal to the divisor, we would have overflow, and must then
resort to a longer method.
Knuth tells us some amazingly good news about guessing. It is
possible to directly compute a guess that is always within 2 of
the correct answer, and most of the time bang on. Even if you
guess wrong, you don't have to remultiply and resubtract! All
you have do do is add the divisor to your your previous
difference.
Ok, what's the catch. First we must have the divisor
normalized. s is the base=2^16. In other words the divisor
must be > s/2 for this to work. Not to worry, this is easy to
arrange. If k is a normalizing number (a power of 2) calculated
to shift the divisor so that it is > s/2 (ie. leading bit is a
one) then:
U / V = kU / kV -- normalizing has no effect
U mod V= (kU mod kV) / k -- you have to unnormalize at the end
Multiplying and dividing by k is easy -- we just use shifts.
The only nasty thing about shifting is that we may have added an
extra digit to u1 by the shift. Also, even the NEC V20 (which
has fast single-register multibit shifts) has to do multiple
register shifts one bit at a time.
At each stage of the division we are dividing a 3 digit dividend
by a 2 digit divisor and we are guaranteed the quotient will be one
digit and the remainder will be one or 2 digits. Now to make a
guess g for that quotient
q1
-------------
v1v2 / u0 u1 u2
g * v1v2
----------
r1h r1l
let U = sý * u0 + s * u1 + u2
V = s * v1 + v2
q1 = U / V q1 < s
r1 = U mod V r1 < V
Presume U and V are normalized
so that v1 > s/2 and u0 ó v1
guess for q = g = ( s * u0 + u1) / v1 if v1 > u0,
but if v1 = u0 we use s-1 instead. This guess can be computed
with a single DIV instruction.
q ó g ó q+2 The true answer q is g, g-1 or g-2.
g < s
Knuth gives a technique for refining the guess, but it is really
only is useful when you are using divisors of >2 digits. All it
amounts to is testing the two high order digits of the divisor
before you do a full test.
We have to compute r1 to see if our guess was too big. We could
compute r1 in the traditional way by multiplying out our guess
and subtracting it from the dividend.
Let us look at this expression algebraically:
r1 = sý*u0 + s*u1 + u2
- s*v1*g - v2*g
This is what Knuth would have us do. However in our case there
is a shortcut. In the process of computing the guess g we
incidentally computed the remainder of u0u1 / v1
r0 = s*u0 + u1 - g*v1
So we can rewrite the expression as:
r1 = s*r0 + u2 - v2*g
This saves us a multiply and a mess of adds over the brute force
approach.
If our guess were computed without a division as s-1 we don't
have r0 sitting around. So what can we do in that case to
quickly compute r1?
r1 = sý*v1 + s*u1 + u2
- s*v1*(s-1) - v2*(s-1)
because g=s-1 and u0=v1
r1 = s*(u1-v2+v1) + u2+v2
In either case, our guess may have been too big.
If r1 is negative this indicates g is too large. The equivalent
r1 for g-1 is r1 + sv1 + v2, so we don't have to remultiply out
if we guessed too large. Why didn't they tell me this in grade
4?
If r1 is still negative, we repeat this one more time
decrementing our guess and guaranteed we are ok now without even
checking!
This handles one cycle. We can now "bring down" the next digit
and append it after our remainder.
We then have this problem to solve:
q2
--------------
v1v2 / r1h r1l u3
q2 * v1v2
----------
r2h r2l
Note that v1 > s/2 and v1 ò r1h so we are right back where we
started with all the magic necessary normalization conditions
satisfied except that we already have one digit of the quotient
calculated.
We solve this in the same way. Then we are done. Because we
check for overflow before we start, we are guaranteed the
quotient has only 2 digits.
Then we have to normalize the two digit remainder by dividing
it by k implemented as a quick shift right.
If we are lucky, (99% of the time) the high order digit of the
divisor will be 0. Nearly always we are just dividing by 10 in
order to convert from binary to ASCII decimal. In that case
life is much simpler. We don't even have to normalize.
At each stage we have a problem like this to solve:
q1
-------------
v2 / u0 u1 u2
g * v2
----------
r1
Because we precheck for overflow, guaranteed u0 = 0 and v1 > u1
let U = su1 + u2
V = v2
q1 = u1 / v2 q1 < s
r1 = u1 mod v2 r1 < v2
We guess for q1 = g = (su1 + u2) / v2 This guess is always < s.
This guess is exact. We don't even have to multiply and
subtract to get the remainder. It is hanging around as a result
of computing the guess. The guess can be computed with a single
DIV instruction.
We then bring down the digit to the right and repeat once more.
We can further optimize divisions by checking the special case
of q being 0. If u1=0 and v2 > u2, we know q=0 and r1 = u2.
There are two other special cases -- when q=1 and when q=s-1.
However these cases are rare, so it does not pay to check for
them. The overhead of checking slows things down in the usual
case.
Now putting all this together:
We first decide whether we will have overflow. If we do, we
indirectly let MU/MOD handle it. If not, we can now presume
that the quotient will have only 1 or 2 digits. Then we check
to see if we have a 1 or 2 digit divisor. We branch to the two
different algorithms -- the 1-digit being the more common.
Because the NEC V20 chip is so fast at division (my guess is it
uses some of the ideas from this algorithm internally), it never
pays to check for the case where the quotient would be 0.
However it does pay to check for 1 or 2 digit divisors.
You may wonder why I documented UM/MOD so fully. It is not
likely you will ever modify this code, but you may someday port
this compiler to a different chip, or want to steal this code
for your C compiler. Then you will bless me for doing this. If
you are lucky the chip will have a decent 64 bit by 32 bit
divide and all this can be thrown away to be resurrected when
you want 128 bit by 64 bit divides. And of course there is
always the possibility of a bug in this code.
| ; end of comment
; divide u0u1u2u3 by v1v2 to get
; quotient q1q2 and remainder r1r2
; CX:BX = v1v2 the divisor
POPDA ; DX:AX = u0u1 high order dividend
; low order u2u3 still on stack
CMP CX,DX ; compare v1 : u0
JB UMSLMODOVL? ; < have overflow or ö0
JA UMSLMODSAFE ; > definitely no overflow
CMP BX,AX ; = compare v2 : u1
JBE UMSLMODOVL? ; <= have overflow or ö0
; we used CMP instruction rather
; than SUB SBB and a single JB
; because we did not want to destroy
; the values of u0u1 v1v2.
UMSLMODSAFE:
; definitely don't have overflow
; quotient Q=q1q2 will fit in
; two digits for sure
OR CX,CX ; compare v1 : 0
JNZ UMSLMODLONG ; <>0 -- use long form
; can use 1-digit divisor v2
; Note that we are sure u0=0 and
; v2 > u1
; now we divide u1u2u3 by v2 to
; get q1q2
; q1 will usually be 0, so we check
; for this special case by
; checking if
; u1=0 and u2<v2 and save
; ourselves a divide.
; At this point CX=0 BX=v1 DX=0 AX=u1
POP DX ; DX=u2
;>>>>>>>>>>
IFE (CHIP EQ NECV20) OR (CHIP EQ NECV30) OR (CHIP GE INTEL80386)
;; IFE because we BYPASS this code
;>>>>>>>>>>
; For Nec chip there is no point
; in checking for 0 quotients
; since divide is faster than the
checks
; so we bypass all this code and
; go straight to the
; UMSLMODQUICK case with two divisions
CMP DX,BX ; compare u2 : v2
JAE UMSLMODQUICK ; >=
OR AX,AX ; compare u1 : 0
JNZ UMSLMODQUICK ; not 0
; we know now that q1 = 0 and r=u2
; all we need do is u2u3 / v2
; At this point DX=u2 BX=v2
POP AX ; AX=u3
; check if q2 would be 0. In
; that case we don't need to do
; any divide at all.
; This case is common as # uses UM/MOD
; indirectly via MU/MOD. Leading
; 0 #'s use two 0-type divides.
; #'s normally use 1 zero-type
; divide to get the high order
quotient.
; It is also common when MOD
; uses UM/MOD on numbers that
; are already MODed.
; q2 will be 0 if u2:u3 < v2
; i.e. u2=0 and u3 < v2
CMP AX,BX ; compare u3 : v1 - do finer
; gauntlet filter first
JAE UMSLMODVQUICK ; >=
OR DX,DX ; compare u2 : 0
JNZ UMSLMODVQUICK ; <>
UMSLMODUQUICK:
; ULTRA QUICK DIVIDE -- No DIV instructions needed. quotient is 0
; This is most common case
; Note that on the NEC chip it does not pay to check for
; the q=0 case
; We know q1q2 = 0
; remainder is u3 in AX
PUSH AX ; push r2
PUSH DI ; push r1 = 0
CLEAR BX ; BX=q2=DI=0
CLEAR CX ; CX=q1=DI=0
QNEXT
UMSLMODVQUICK :
; VERY QUICK DIVIDE -- only one DIV instruction
; This is the second most common case.
; we know that q2 <> 0.
; and q1 = 0 and r=u2
; all we need do is u2u3 / v2
; At this point DX=u2 BX=v2 AX=u3
; note this can often be used even
; when u2>0
; we have already checked that
; q2 is not 0. It does not pay to
; check for q2=1 or s-1.
DIV BX ; DX:AX / BX = u2u3 / v2
; DX = rem AX=q2
PUSH DX ; push r2
PUSH DI ; push r1 = 0
MOV BX,AX ; BX=q2=AX
MOV CX,DI ; CX=q1=DI=0
QNEXT
;>>>>>>>>>>
ENDIF ; end of code BYPASSED for NECV20
;>>>>>>>>>>
UMSLMODQUICK:
; QUICK DIVIDE -- two DIV instructions -- no MUL instructions
; we know q1 <> 0, but v1=0
XCHG DX,AX ; DX=u1 AX=u2
; we have already checked
; that q1 <> 0, It does not
; pay to check for q1=1 or s-1
DIV BX ; u1u2 / v2
; AX=q1 DX=r
MOV CX,AX ; CX=q1
POP AX ; AX=u3
; It does not pay to check for
; q2 = 0,1,s-1 as these
; cases happen very rarely
DIV BX ; DX:AX BX = u2u3 / v2
; DX=r2 AX=q2
MOV BX,AX ; BX=q2
; at this point CX:BX = q1q2
PUSH DX ; push r2
PUSH DI ; push r1=0
QNEXT
UMSLMODOVL?:
; May have overflow or ö0
; decide which.
; CX:BX = v1v2 the divisor
; DX:AX = u0u1 high order dividend
OR BX,BX
JNZ UMSLMODOVL ; v2 <> 0 - problem was overflow
OR CX,CX ;
JNZ UMSLMODOVL ; v1 <> 0 - problem was overflow
; v1v2 = 0 - divided by 0
; DIVIDED BY 0
XCHG SP,BP ; u2u3 still on stack, convert
; them to r1r2
CLEAR CX ; q1=0
CLEAR BX ; q2=0
CLEAR [BP] ; r1=0
CLEAR [BP+2] ; r2=0
XCHG BP,SP
QNEXT
UMSLMODOVL:
; OVERFLOWED recover by using UM/MOD-OVL
; it calls MU/MOD which calls UM/MOD.
; We won't get into a loop because of the way
; MU/MOD calls UM/MOD guarantees overflow is not possible.
; CX:BX = v1v2 the divisor
; DX:AX = u0u1 high order dividend
PUSHDA ; put q0q1 back where they were
JMP UMSLMODOVL_cfa
UMSLMODLONG:
; LONG DIVIDE -- two DIV instructions and 2 MUL instructions
; v1 > 0, so we need a 2-digit divisor
; We must divide u0u1u2u3 by v1,v2
; We are sure we can get a two digit quotient q1q2
; and a two digit remainder r1r2.
; First of all we must normalize so that v1>s/2 ie
; has a leading 1. We will be shifting v1,v2 left as we
; look for the 1. We will also be shifting u0u1u2u3 left.
; There is no danger that bits will fall off the end
; because we have already checked that v1v2 > u0u1. So
; We don't have to worry about having to deal with the
; extra digit that Knuth warns about.
; This long form is quite complex to follow, but
; relatively quick to execute. The traditional methods
; would take 3 DIV instructions and 6 MULs to accomplish
; the same thing. I have optimized it so that the usual
; case does not take branches. There is great parallelism
; computing q1 and q2 which could have be implemented as a
; loop. I have unravelled that loop for speed.
XCHG SP,BP ; Save registers. We are about to
; use every register as a temporary.
; NOTE THAT THE USE OF DS: AND ES:
; as scratch registers
; is not compatible with
; Protected mode.
PUSH SI ; we can't use Dstack as it has u2u3
PUSH DS ; which we will want soon
XCHG BP,SP
;
; Register usage here
; AX=u1 BX=v2 CX=v1 DX=u0 SI=free DI=0 ES=free DS=free stack=u2u3
;
; CX:BX = v1v2 the divisor
; DX:AX = u0u1 high order dividend
; Dstack has u2u3 low order dividend
;
; <<< start of normalization>>>
;
MOV SI,CX ; v1 = SI := CX
CLEAR CX ; CX counts how much we had to shift
; DI still 0
MOV DI,BX ; v2 = DI := BX
; at this point SI
I has v1v2
UMSLMODNORMLOOP1:
SHL DI,1 ; shift v1v2 left one bit
RCL SI,1
; leading 1 bit shifts into carry
JC UMSLMODLOOP1DONE
; jump when found the leading 1-bit
INC CX ; count another 0-bit
JMP SHORT UMSLMODNORMLOOP1
; loop till find leading 1 bit
; guaranteed there is one
UMSLMODLOOP1DONE:
; at this point we have counted
; CX properly, but v1,v2 is shifted
; one too far left
RCR SI,1 ; undo the last shift putting
RCR DI,1 ; carry back into SI.
; You might ask why I didn't test
; the sign bit instead of the
; carry bit. Then I would not have
; overshot. RCL does not set
; the sign flag. I would have
; needed an extra OR in the
; tight loop.
;
; Register usage here
; AX=u1 BX=free CX=k DX=u0 SI=v1 DI=v2 ES=free DS=free stack=u2u3
;
MOV DS,CX ; k = DS := CX save the shift count
MOV ES,SI ; v1 = ES := SI normalized
; we need CX and SI for other purposes
; temporarily
POP BX ; u2 = BX was on stack
POP SI ; u3 = SI was on stack
PUSH DS ; save k = DS shift count on the stack
; this frees up DS
;
; Register usage here
; AX=u1 BX=u2 CX=k DX=u0 SI=u3 DI=v2 ES=v1 DS=free stack=k
;
JCXZ UMSLMODLOOP2BYPASS ; loop shifting u0u1u2u3 left
UMSLMODNORMLOOP2:
SHL SI,1 ; treat DX:AX:BX:SI as giant
RCL BX,1 ; register to hold u0u1u2u3
RCL AX,1 ; shift left k bits 1 bit at a time
RCL DX,1 ; We never lose a bit out of DX
LOOP UMSLMODNORMLOOP2
UMSLMODLOOP2BYPASS:
MOV DS,SI ; u3 = DS
MOV SI,ES ; v1 = SI := ES
;
; Register usage here
; AX=u1 BX=u2 CX=0 DX=u0 SI=v1 DI=v2 ES=free DS=u3 stack=k
;
;<<< Start of calculation of q1 >>>
;
CMP SI,DX ; compare v1 : u0 SI : DX
JE UMSLMODGUESS1 ; v1=u0 guess s-1
; v1 > u0
; Make a guess g as u0u1 / v1. Save the remainder r0
; u0 = DX no longer needed
; u1 = AX no longer needed
DIV SI ; u0u1 / v1 = DX:AX / SI
; g = AX r0 = DX
MOV CX,AX ; g = CX := AX
MOV ES,DX ; r0 = ES := DX
;
; Register usage here
; AX=g BX=u2 CX=g DX=free SI=v1 DI=v2 ES=r0 DS=u3 stack=k
;
; Compute the remainder r1 as
; r1 = s*r0 + u2 - v2*g
MUL DI ; g = AX; v2 = DI
; DX:AX = v2*g
SUB BX,AX ; r1l = BX := u2 - v2gl
; u2 no longer needed
MOV AX,ES ; r0 = AX := ES
SBB AX,DX ; r1h = AX := r0 - v2gh
; r0 no longer needed
MOV DX,AX ; r1 = DX:AX
MOV AX,BX ;
MOV BX,0 ; keep carry of r1
SBB BL,BH ; in BL, 0 in BH
;
; Register usage here
; AX=r1l BX=r1carry CX=g DX=r1h SI=v1 DI=v2 ES=free DS=u3 stack=k
;
; Test the remainder from q1 for being negative
JL UMSLMODBADQ1 ; BX is signed so no need for JB
UMSLMODGOODQ1:
; We have a perfect guess g for q1, and and a non-negative remainder
r1
; DX:AX = r1
; r1 carry is 0
; g = q1 = CX
;
;<<< Start of calculation of q2 >>>
;
;
; Register usage here
; AX=r1l BX=free CX=q1 DX=r1h SI=v1 DI=v2 ES=free DS=u3 stack=k
;
MOV BX,DS ; u3 = BX := DS
MOV DS,CX ; q1 = DS := CX -- save q1
CMP SI,DX ; compare v1 : r1h SI : DX
JE UMSLMODGUESS2 ; v1=r1h guess q2 as s-1
; v1 > r1h
; Make a guess g as r1h r1l / v1. Keep the remainder r0
;
; Register usage here
; AX=r1l BX=u3 CX=free DX=r1h SI=v1 DI=v2 ES=free DS=q1 stack=k
;
DIV SI ; DX:AX / SI = r1h r1l / v2
; r1h = DX no longer needed
; r1l = AX no longer needed
; g = AX r0 = DX
MOV CX,AX ; g = CX := AX
MOV ES,DX ; r0 = ES := DX
;
; Compute the remainder r2 as
; r2 = s*r0 + u3 - v2*g
;
; Register usage here
; AX=g BX=u3 CX=g DX=free SI=v1 DI=v2 ES=r0 DS=q1 stack=k
;
MUL DI ; g = AX; v2 = DI
; DX:AX = v2*g
SUB BX,AX ; r2l = BX := u3 - v2gl
; u3 no longer needed
MOV AX,ES ; r0 = AX := ES
SBB AX,DX ; r2h = AX := r0 - v2gh
; r0 no longer needed
MOV DX,AX ; r2 = DX:AX
MOV AX,BX ;
MOV BX,0 ; keep carry of r2
; cant use XOR or would wreck carry
SBB BL,BH ; in BL, 0 in BH
;
; Register usage here
; AX=r2l BX=r2carry CX=g DX=r2h SI=v1 DI=v2 ES=free DS=q1 stack=k
;
; Test the remainder for q2 for being negative
JL UMSLMODBADQ2
;
UMSLMODGOODQ2:
; We have a perfect guess g=q2, and and a non-negative remainder r2
;
; Register usage here
; AX=r2l BX=free CX=q2 DX=r2h SI=free DI=free ES=free DS=q1 stack=k
;
; g = q2 = CX
; q1 = DS
MOV BX,CX ; q2 = BX := CX
; <<< start of denormalization >>>
;
; Register usage here
; AX=r2l BX=q2 CX=free DX=r2h SI=free DI=free ES=free DS=q1 stack=k
;
;
; r2 = DX:AX needs to be denormalized
POP CX ; get k bits we shifted
JCXZ UMSLMODDENORMBYPASS
UMSLMODDENORMLOOP:
SHR DX,1 ; r2 = DX:AX - shift right
RCR AX,1 ; We DONT shift q1q2!!
LOOP UMSLMODDENORMLOOP
UMSLMODDENORMBYPASS:
; q2 = BX already
MOV CX,DS ; q1 = CX := DS
;
; Register usage here
; AX=r2l BX=q2 CX=q1 DX=r2h SI=free DI=free ES=free DS=free
;
XCHG SP,BP
POP DS ; restore DS:SI and DI to usual values
POP SI
XOR DI,DI
XCHG BP,SP
;
PUSHDA ; push normalized remainder
; Register usage here
; AX=free BX=q2 CX=q1 DX=free SI=std DI=0 ES=free DS=std
;
QNEXT
; ----- usual end -----
UMSLMODGUESS1:
; If v1 = u0,
; Make a guess for q1 as s-1
; Statistically we rarely should execute this code
;
; Because we used guess s-1 Compute the remainder r1 as
; r1 = s*(u1+v1-v2) + u2+v2
;
; Register usage here
; AX=u1 BX=u2 CX=free DX=u0 SI=v1 DI=v2 ES=free DS=u3 stack=k
;
; u0 no longer needed
MOV DX,AX ; u1 = DX := AX
; u1 no longer needed
MOV AX,BX ; u2 no longer needed
XOR BX,BX ; clear BX ready for carry
; cannot use DI to clear
ADD AX,DI ; add on v2
ADC DX,SI ; add on v1
ADC BL,BH ; carry in BL, 0 in BH
SUB DX,DI ; subtract off v2
; r1 in DX:AX
SBB BL,BH ; borrow might be ok if
; cancelled by carry
MOV CX,-1 ; g = CX = s-1 all FFFFs
; Test the remainder for being negative
;
; Register usage here
; AX=r1l BX=r1carry CX=g DX=r1h SI=v1 DI=v2 ES=free DS=u3 stack=k
;
JNL UMSLMODGOODQ1 ; remainder was ok
; remainder was -ve
UMSLMODBADQ1:
; If remainder is negative, decrement q1 and increment the
; remainder by v1v2
;
; Register usage here
; AX=r1l BX=r1carry CX=g DX=r1h SI=v1 DI=v2 ES=free DS=u3 stack=k
; ; g = CX, r1 = DX:AX
; v1 = SI; v2 = DI
DEC CX ; g = CX := g - 1
ADD AX,DI ; AX = r1l + v2
ADC DX,SI ; DX = r1h + v1
ADC BL,BH ; BL = r1carry BH=0
; Test the remainder for being negative
JNL UMSLMODGOODQ1
; If remainder is still negative, decrement q1 and increment the
; remainder by v1v2 again
DEC CX ; g = CX := g - 1
ADD AX,DI ; AX = r1l + v2
ADC DX,SI ; DX = r1h + v1
; Don't bother to compute
; BL = r1carry
; with ADC BL,BH
; Remainder guaranteed positive
;
; Register usage here
; AX=r1l BX=free CX=g DX=r1h SI=v1 DI=v2 ES=free DS=u3 stack=k
;
JMP SHORT UMSLMODGOODQ1 ; guaranteed good remainder
UMSLMODGUESS2:
; If v1 = r1h,
; Make a guess for q2 as s-1
; Statistically we rarely should execute this code
;
; Because we used guess s-1 Compute the remainder r1 as
; r2 = s*(r1l+v1-v2) + u3+v2
;
; Register usage here
; AX=r1l BX=u3 CX=free DX=r1h SI=v1 DI=v2 ES=r0 DS=q1 stack=k
;
; r1h = DX no longer needed
MOV DX,AX ; r1l = DX := AX
; r1l no longer needed
MOV AX,BX ; u3 = BX no longer needed
XOR BX,BX ; clear BX ready for carry
; cannot use DI to clear
ADD AX,DI ; add on v2
ADC DX,SI ; add on v1
ADC BL,BH ; keep carry in BL, 0 in BH
SUB DX,DI ; subtract off v2
; r2 in DX:AX
SBB BL,BH ; borrow might be ok if
; cancelled by carry
MOV CX,-1 ; g = CX = s-1 all FFFFs
; Test the remainder for being negative
;
; Register usage here
; AX=r2l BX=r2carry CX=q2 DX=r2h SI=free DI=free ES=free DS=q1 stack=k
;
JNL UMSLMODGOODQ2 ; remainder was ok
; remainder was -ve
UMSLMODBADQ2:
; If remainder is negative, decrement guess g for q2 and increment
the
; remainder by v1v2
;
; Register usage here
; AX=r2l BX=r2carry CX=g DX=r2h SI=v1 DI=v2 ES=free DS=q1 stack=k
;
; ; g = CX, r2 = DX:AX
; v1 = SI; v2 = DI
DEC CX ; g = CX := g - 1
ADD AX,DI ; AX = r2l + v2
ADC DX,SI ; DX = r2h + v1
ADC BL,BH ; BL = r2carry BH=0
; Test the remainder for being negative
JNL UMSLMODGOODQ2
; If remainder is still negative, decrement q2 and increment the
; remainder by v1v2 again
DEC CX ; g = CX := g - 1
ADD AX,DI ; AX = r2l + v2
ADC DX,SI ; DX = r2h + v1
; don't bother computing BL=
; r2carry with ADC BL,BH
; Register usage here
; AX=r2l BX=free CX=g DX=r2h SI=v1 DI=v2 ES=free DS=q1 stack=k
;
; Don't bother to test the remainder for being negative
JMP SHORT UMSLMODGOODQ2 ; guaranteed good
; <<<< end of UM/MOD >>> Whew!
