author Richard Levitte Sun, 1 Dec 2002 00:49:36 +0000 (00:49 +0000) committer Richard Levitte Sun, 1 Dec 2002 00:49:36 +0000 (00:49 +0000)
PR: 366

index 465f2774b6267e0b6dd4e983bfc35926860e7d31..6bd0e87a9a22d5999e12b812c2e0cfc0bfdd7603 100644 (file)
@@ -172,145 +172,106 @@ n=12 ;(AP)      n       by value (input)
; }
;
; Using EDIV would be very easy, if it didn't do signed calculations.
; }
;
; Using EDIV would be very easy, if it didn't do signed calculations.
-; Therefore, som extra things have to happen around it.  The way to
-; handle that is to shift all operands right one step (basically dividing
-; them by 2) and handle the different cases depending on what the lowest
-; bit of each operand was.
+; It doesn't accept a signed dividend, but accepts a signed divisor.
+; So, shifting down the dividend right one bit makes it positive, and
+; just makes us lose the lowest bit, which can be used afterwards as
+; an addition to the remainder.  All that needs to be done at the end
+; is a little bit of fiddling; shifting both quotient and remainder
+; one step to the left, and deal with the situation when the remainder
+; ends up being larger than the divisor.
;
;
-; To start with, let's define the following:
+; We end up doing something like this:
;
;
-; a' = l & 1
-; a2 = <h,l> >> 1      # UNSIGNED shift!
-; b' = d & 1
-; b2 = d >> 1          # UNSIGNED shift!
+; l'    = l & 1
+; [h,l] = [h,l] >> 1
+; [q,r] = floor([h,l] / d)
+; if (q < 0) q = -q    # Because EDIV thought d was negative
;
;
-; Now, use EDIV to calculate a quotient and a remainder:
+; Now, we need to adjust back by multiplying quotient and remainder with 2,
+; and add the bit that dropped out when dividing by 2:
;
;
-; q'' = a2/b2
-; r'' = a2 - q''*b2
+; r'    = r & 0x80000000
+; q     = q << 1
+; r     = (r << 1) + a'
;
;
-; If b' is 0, the quotient is already correct, we just need to adjust the
-; remainder:
+; And now, the final adjustment if the remainder happens to get larger than
+; the divisor:
;
;
-; if (b' == 0)
+; if (r')
;   {
;   {
-;     r = 2*r'' + a'
-;     q = q''
+;     r = r - d
+;     q = q + 1
;   }
;   }
-;
-; If b' is 1, we need to do other adjustements.  The first thought is the
-; following (note that r' will not always have the right value, but an
-;
-; if (b' == 1)
-;   {
-;     q' = q''
-;     r' = a - q'*b
-;
-; However, one can note the folowing relationship:
-;
-;                         r'' = a2 - q''*b2
-;                  =>   2*r'' = 2*a2 - 2*q''*b2
-;                             = { a = 2*a2 + a', b = 2*b2 + b' = 2*b2 + 1,
-;                                 q' = q'' }
-;                             = a - a' - q'*(b - 1)
-;                             = a - q'*b - a' + q'
-;                             = r' - a' + q'
-;                  =>     r'  = 2*r'' - q' + a'
-;
-; This enables us to use r'' instead of discarding and calculating another
-; modulo:
-;
-; if (b' == 1)
+; while (r > d)
;   {
;   {
-;     q' = q''
-;     r' = (r'' << 1) - q' + a'
-;
-; Now, all we have to do is adjust r', because it might be < 0:
-;
-;     while (r' < 0)
-;       {
-;         r' = r' + b
-;         q' = q' - 1
-;       }
+;     r = r - d
+;     q = q + 1
;   }
;
;   }
;
-; return q'
+; return q

h=4 ;(AP)      h       by value (input)
l=8 ;(AP)      l       by value (input)
d=12 ;(AP)     d       by value (input)

h=4 ;(AP)      h       by value (input)
l=8 ;(AP)      l       by value (input)
d=12 ;(AP)     d       by value (input)

-;aprim=r5
-;a2=r6
-;a20=r6
-;a21=r7
-;bprim=r8
-;b2=r9
-;qprim=r10     ; initially used as q''
-;rprim=r11     ; initially used as r''
+;lprim=r5
+;rprim=r6

.psect  code,nowrt

.psect  code,nowrt

-.entry bn_div_words,^m<r2,r3,r4,r5,r6,r7,r8,r9,r10,r11>
+.entry bn_div_words,^m<r2,r3,r4,r5,r6>
movl    l(ap),r2
movl    h(ap),r3
movl    d(ap),r4

movl    #0,r5
movl    l(ap),r2
movl    h(ap),r3
movl    d(ap),r4

movl    #0,r5
-       movl    #0,r8
-       movl    #0,r0
-;      movl    #0,r1
+       movl    #0,r6

-       rotl    #-1,r2,r6       ; a20 = l >> 1 (almost)
-       rotl    #-1,r3,r7       ; a21 = h >> 1 (almost)
-       rotl    #-1,r4,r9       ; b2 = d >> 1 (almost)
+       rotl    #-1,r2,r2       ; l = l >> 1 (almost)
+       rotl    #-1,r3,r3       ; h = h >> 1 (almost)

-       tstl    r6
+       tstl    r2
bgeq    1\$
bgeq    1\$
-       xorl2   #^X80000000,r6  ; fixup a20 so highest bit is 0
-       incl    r5              ; a' = 1
+       xorl2   #^X80000000,r2  ; fixup l so highest bit is 0
+       incl    r5              ; l' = 1
1\$:
1\$:
-       tstl    r7
+       tstl    r3
bgeq    2\$
bgeq    2\$
-       xorl2   #^X80000000,r6  ; fixup a20 so highest bit is 1,
-                               ; since that's what was lowest in a21
-       xorl2   #^X80000000,r7  ; fixup a21 so highest bit is 1
+       xorl2   #^X80000000,r2  ; fixup l so highest bit is 1,
+                               ; since that's what was lowest in h
+       xorl2   #^X80000000,r3  ; fixup h so highest bit is 0
2\$:
2\$:
-       tstl    r9
+       tstl    r4
beql    666\$            ; Uh-oh, the divisor is 0...
beql    666\$            ; Uh-oh, the divisor is 0...
-       bgtr    3\$
-       xorl2   #^X80000000,r9  ; fixup b2 so highest bit is 0
-       incl    r8              ; b' = 1
+
+       ediv    r4,r2,r2,r3     ; Do the actual division
+
+       tstl    r2
+       bgeq    3\$
+       mnegl   r2,r2           ; if q < 0, negate it
3\$:
3\$:
-       tstl    r9
-       bneq    4\$              ; if b2 is 0, we know that b' is 1
tstl    r3
tstl    r3
-       bneq    666\$            ; if higher half isn't 0, we overflow
-       movl    r2,r10          ; otherwise, we have our result
-       brb     42\$             ; This is a success, really.
+       bgeq    4\$
+       incl    r6              ; since the high bit in r is set, set rprim
4\$:
4\$:
-       ediv    r9,r6,r10,r11
+       ashl    #1,r2,r2
+       ashl    #1,r3,r3

-       tstl    r8
-       bneq    5\$              ; If b' != 0, go to the other part
-       brb     42\$
+       tstl    r6
+       beql    5\$
+       subl    r4,r3
+       incl    r2
5\$:
5\$:
-       ashl    #1,r11,r11
-       subl2   r10,r11
-       bgeq    7\$
-6\$:
-       decl    r10
-       blss    6\$
-7\$:
-;      movl    r11,r1
+       cmpl    r3,r4
+       blequ   42\$
+       subl    r4,r3
+       incl    r2
+       brb     5\$
42\$:
42\$:
-       movl    r10,r0
+;      movl    r3,r1
+       movl    r2,r0
666\$:
ret
\f
666\$:
ret
\f