X-Git-Url: https://git.openssl.org/gitweb/?p=openssl.git;a=blobdiff_plain;f=crypto%2Fbn%2Fasm%2Fvms.mar;h=aefab15cdb298dec3da28827510c8bb1957767a2;hp=6bd0e87a9a22d5999e12b812c2e0cfc0bfdd7603;hb=98939a05b6884538ba40fae2606291140f9e5839;hpb=a6784306028d85e5c701968a6217f56c9801c452 diff --git a/crypto/bn/asm/vms.mar b/crypto/bn/asm/vms.mar index 6bd0e87a9a..aefab15cdb 100644 --- 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 ; @@ -59,7 +59,7 @@ w=16 ;(AP) w by value (input) movl r6,r0 ; return c ret - .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 ; @@ -172,40 +172,71 @@ n=12 ;(AP) n by value (input) ; } ; ; 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 @@ -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) -;lprim=r5 -;rprim=r6 - +;r2 = l, q +;r3 = h, r +;r4 = d +;r5 = l' +;r6 = r' +;r7 = d' +;r8 = q' .psect code,nowrt -.entry bn_div_words,^m +.entry bn_div_words,^m 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... - + 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 -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 + ret 666$: + movl #^XFFFFFFFF,r0 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$ .title vax_bn_add_words unsigned add of two arrays ;