alpha-mont.pl: gcc portability fix and make-rule.

[openssl.git] / crypto / bn / asm / vms.mar

diff --git a/crypto/bn/asm/vms.mar b/crypto/bn/asm/vms.mar
index 6bd0e87a9a22d5999e12b812c2e0cfc0bfdd7603..aefab15cdb298dec3da28827510c8bb1957767a2 100644 (file)
--- a/crypto/bn/asm/vms.mar
+++ b/crypto/bn/asm/vms.mar
@@ -1,4 +1,4 @@
-       .title  vax_bn_mul_add_word  unsigned multiply & add, 32*32+32+32=>64
+       .title  vax_bn_mul_add_words  unsigned multiply & add, 32*32+32+32=>64

 ;
 ; w.j.m. 15-jan-1999
 ;
 ;
 ; w.j.m. 15-jan-1999
 ;


@@ -59,7 +59,7 @@ w=16 ;(AP)    w       by value (input)
        movl    r6,r0                   ; return c
        ret
 \f
        movl    r6,r0                   ; return c
        ret
 \f

-       .title  vax_bn_mul_word  unsigned multiply & add, 32*32+32=>64
+       .title  vax_bn_mul_words  unsigned multiply & add, 32*32+32=>64

 ;
 ; w.j.m. 15-jan-1999
 ;
 ;
 ; w.j.m. 15-jan-1999
 ;


@@ -172,40 +172,71 @@ 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.

-; 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.
+; Any time any of the input numbers are signed, there are problems,
+; usually with integer overflow, at which point it returns useless
+; data (the quotient gets the value of l, and the remainder becomes 0).

 ;
 ;

-; We end up doing something like this:
+; If it was just for the dividend, it would be very easy, just divide
+; it by 2 (unsigned), do the division, multiply the resulting quotient
+; and remainder by 2, add the bit that was dropped when dividing by 2
+; to the remainder, and do some adjustment so the remainder doesn't
+; end up larger than the divisor.  For some cases when the divisor is
+; negative (from EDIV's point of view, i.e. when the highest bit is set),
+; dividing the dividend by 2 isn't enough, and since some operations
+; might generate integer overflows even when the dividend is divided by
+; 4 (when the high part of the shifted down dividend ends up being exactly
+; half of the divisor, the result is the quotient 0x80000000, which is
+; negative...) it needs to be divided by 8.  Furthermore, the divisor needs
+; to be divided by 2 (unsigned) as well, to avoid more problems with the sign.
+; In this case, a little extra fiddling with the remainder is required.

 ;
 ;

-; 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
+; So, the simplest way to handle this is always to divide the dividend
+; by 8, and to divide the divisor by 2 if it's highest bit is set.
+; After EDIV has been used, the quotient gets multiplied by 8 if the
+; original divisor was positive, otherwise 4.  The remainder, oddly
+; enough, is *always* multiplied by 8.
+; NOTE: in the case mentioned above, where the high part of the shifted
+; down dividend ends up being exactly half the shifted down divisor, we
+; end up with a 33 bit quotient.  That's no problem however, it usually
+; means we have ended up with a too large remainder as well, and the
+; problem is fixed by the last part of the algorithm (next paragraph).

 ;
 ;

-; Now, we need to adjust back by multiplying quotient and remainder with 2,
-; and add the bit that dropped out when dividing by 2:
+; The routine ends with comparing the resulting remainder with the
+; original divisor and if the remainder is larger, subtract the
+; original divisor from it, and increase the quotient by 1.  This is
+; done until the remainder is smaller than the divisor.

 ;
 ;

-; r'    = r & 0x80000000
-; q     = q << 1
-; r     = (r << 1) + a'
+; The complete algorithm looks like this:

 ;
 ;

-; And now, the final adjustment if the remainder happens to get larger than
-; the divisor:
+; d'    = d
+; l'    = l & 7
+; [h,l] = [h,l] >> 3
+; [q,r] = floor([h,l] / d)     # This is the EDIV operation
+; if (q < 0) q = -q            # I doubt this is necessary any more

 ;
 ;

-; if (r')
+; r'    = r >> 29
+; if (d' >= 0)
+;   q'  = q >> 29
+;   q   = q << 3
+; else
+;   q'  = q >> 30
+;   q   = q << 2
+; r     = (r << 3) + l'
+;
+; if (d' < 0)

 ;   {
 ;   {

-;     r = r - d
-;     q = q + 1
+;     [r',r] = [r',r] - q
+;     while ([r',r] < 0)
+;       {
+;         [r',r] = [r',r] + d
+;         [q',q] = [q',q] - 1
+;       }

 ;   }
 ;   }

-; while (r > d)
+;
+; while ([r',r] >= d')

 ;   {
 ;   {

-;     r = r - d
-;     q = q + 1
+;     [r',r] = [r',r] - d'
+;     [q',q] = [q',q] + 1

 ;   }
 ;
 ; return q
 ;   }
 ;
 ; return q


@@ -214,66 +245,102 @@ h=4 ;(AP)        h       by value (input)
 l=8 ;(AP)      l       by value (input)
 d=12 ;(AP)     d       by value (input)
 
 l=8 ;(AP)      l       by value (input)
 d=12 ;(AP)     d       by value (input)
 

-;lprim=r5
-;rprim=r6
-
+;r2 = l, q
+;r3 = h, r
+;r4 = d
+;r5 = l'
+;r6 = r'
+;r7 = d'
+;r8 = q'

 
        .psect  code,nowrt
 
 
        .psect  code,nowrt
 

-.entry bn_div_words,^m<r2,r3,r4,r5,r6>
+.entry bn_div_words,^m<r2,r3,r4,r5,r6,r7,r8>

        movl    l(ap),r2
        movl    h(ap),r3
        movl    d(ap),r4
 
        movl    l(ap),r2
        movl    h(ap),r3
        movl    d(ap),r4
 

-       movl    #0,r5
-       movl    #0,r6
+       bicl3   #^XFFFFFFF8,r2,r5 ; l' = l & 7
+       bicl3   #^X00000007,r2,r2

 
 

-       rotl    #-1,r2,r2       ; l = l >> 1 (almost)
-       rotl    #-1,r3,r3       ; h = h >> 1 (almost)
+       bicl3   #^XFFFFFFF8,r3,r6
+       bicl3   #^X00000007,r3,r3
+        
+       addl    r6,r2
+
+       rotl    #-3,r2,r2       ; l = l >> 3
+       rotl    #-3,r3,r3       ; h = h >> 3
+                
+       movl    r4,r7           ; d' = d
+
+       movl    #0,r6           ; r' = 0
+       movl    #0,r8           ; q' = 0

 
 

-       tstl    r2
-       bgeq    1$
-       xorl2   #^X80000000,r2  ; fixup l so highest bit is 0
-       incl    r5              ; l' = 1
-1$:
-       tstl    r3
-       bgeq    2$
-       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$:

        tstl    r4
        beql    666$            ; Uh-oh, the divisor is 0...
        tstl    r4
        beql    666$            ; Uh-oh, the divisor is 0...

-
+       bgtr    1$
+       rotl    #-1,r4,r4       ; If d is negative, shift it right.
+       bicl2   #^X80000000,r4  ; Since d is then a large number, the
+                               ; lowest bit is insignificant
+                               ; (contradict that, and I'll fix the problem!)
+1$:     

        ediv    r4,r2,r2,r3     ; Do the actual division
 
        tstl    r2
        bgeq    3$
        mnegl   r2,r2           ; if q < 0, negate it
        ediv    r4,r2,r2,r3     ; Do the actual division
 
        tstl    r2
        bgeq    3$
        mnegl   r2,r2           ; if q < 0, negate it

-3$:
-       tstl    r3
-       bgeq    4$
-       incl    r6              ; since the high bit in r is set, set rprim
-4$:
-       ashl    #1,r2,r2
-       ashl    #1,r3,r3
-       addl    r5,r3
-
-       tstl    r6
-       beql    5$
-       subl    r4,r3
-       incl    r2
-5$:
-       cmpl    r3,r4
-       blequ   42$
-       subl    r4,r3
-       incl    r2
-       brb     5$      
+3$:     
+       tstl    r7
+       blss    4$
+       rotl    #3,r2,r2        ;   q = q << 3
+       bicl3   #^XFFFFFFF8,r2,r8 ;    q' gets the high bits from q
+       bicl3   #^X00000007,r2,r2
+       bsb     41$
+4$:                            ; else
+       rotl    #2,r2,r2        ;   q = q << 2
+       bicl3   #^XFFFFFFFC,r2,r8 ;   q' gets the high bits from q
+       bicl3   #^X00000003,r2,r2
+41$:
+       rotl    #3,r3,r3        ; r = r << 3
+       bicl3   #^XFFFFFFF8,r3,r6 ; r' gets the high bits from r
+       bicl3   #^X00000007,r3,r3
+       addl    r5,r3           ; r = r + l'
+
+       tstl    r7
+       bgeq    5$
+       bitl    #1,r7
+       beql    5$              ; if d' < 0 && d' & 1
+       subl    r2,r3           ;   [r',r] = [r',r] - [q',q]
+       sbwc    r8,r6
+45$:
+       bgeq    5$              ;   while r < 0
+       decl    r2              ;     [q',q] = [q',q] - 1
+       sbwc    #0,r8
+       addl    r7,r3           ;     [r',r] = [r',r] + d'
+       adwc    #0,r6
+       brb     45$
+
+; The return points are placed in the middle to keep a short distance from
+; all the branch points

 42$:
 ;      movl    r3,r1
        movl    r2,r0
 42$:
 ;      movl    r3,r1
        movl    r2,r0

+       ret

 666$:
 666$:

+       movl    #^XFFFFFFFF,r0

        ret
        ret

+
+5$:
+       tstl    r6
+       bneq    6$
+       cmpl    r3,r7
+       blssu   42$             ; while [r',r] >= d'
+6$:
+       subl    r7,r3           ;   [r',r] = [r',r] - d'
+       sbwc    #0,r6
+       incl    r2              ;   [q',q] = [q',q] + 1
+       adwc    #0,r8
+       brb     5$      

 \f
        .title  vax_bn_add_words  unsigned add of two arrays
 ;
 \f
        .title  vax_bn_add_words  unsigned add of two arrays
 ;