1 /* Copyright (c) 1998,2011-2014 Apple Inc. All Rights Reserved.
3 * NOTICE: USE OF THE MATERIALS ACCOMPANYING THIS NOTICE IS SUBJECT
4 * TO THE TERMS OF THE SIGNED "FAST ELLIPTIC ENCRYPTION (FEE) REFERENCE
5 * SOURCE CODE EVALUATION AGREEMENT" BETWEEN APPLE, INC. AND THE
6 * ORIGINAL LICENSEE THAT OBTAINED THESE MATERIALS FROM APPLE,
7 * INC. ANY USE OF THESE MATERIALS NOT PERMITTED BY SUCH AGREEMENT WILL
8 * EXPOSE YOU TO LIABILITY.
9 ***************************************************************************
11 giantIntegers.c - library for large-integer arithmetic.
15 Fixed a==b bug in addg().
17 Changed to compile with C++.
18 13 Apr 98 Fixed shiftright(1) bug in modg_via_recip.
20 Major rewrite of core arithmetic routines to make this module
21 independent of size of giantDigit.
22 Removed idivg() and radixdiv().
24 Deleted FFT arithmetic; simplified mulg().
26 gshiftright() optimization.
28 newGiant() returns NULL on malloc failure
30 New grammarSquare(); optimized modg_via_recip()
32 Added modg_via_recip(), divg_via_recip(), make_recip()
33 Added new multiple giant stack mechanism
34 Fixed potential packing/alignment bug in copyGiant()
35 Added profiling for borrowGiant(), returnGiant()
36 Deleted obsolete ifdef'd code
38 All calls to borrowGiant() now specify required size (no more
41 Changed size of giantstruct.n to 1 for Mac build
43 newGiant() no longer modifies CurrentMaxShorts or giant stack
46 Added iszero() check in gcompg
48 Fixed negation bug in gmersennemod()
49 Fixed n[words-1] == 0 bug in extractbits()
50 Cleaned up lots of static declarations
52 Fixed --size underflow bug in normal_subg().
54 Fixed (b<n), (sign<0) case in gmersennemod() to allow for arbitrary n.
56 Fixed sign-extend bug in data_to_giant().
58 Changed precision in newtondivide().
59 Removed #ifdef UNUSED code.
70 #include "giantIntegers.h"
73 #include "ellipticMeasure.h"
75 #include "giantPortCommon.h"
78 #if (GIANT_LOG2_BITS_PER_DIGIT == 4)
79 #warning Compiling with two-byte giantDigits
88 void printGiantBuf(giant x
)
92 sprintf(printbuf2
, "sign=%d cap=%d n[]=", x
->sign
, x
->capacity
);
93 for(i
=0; i
<abs(x
->sign
); i
++) {
94 sprintf(printbuf3
+ 10*i
, "%u:", x
->n
[i
]);
100 void printGiantBuf2(giant x
)
104 sprintf(printbuf4
, "sign=%d cap=%d n[]=", x
->sign
, x
->capacity
);
105 for(i
=0; i
<abs(x
->sign
); i
++) {
106 sprintf(printbuf5
+ 10*i
, "%u:", x
->n
[i
]);
109 #endif /* FEE_DEBUG */
112 /******** debugging flags *********/
115 * Flag use of unoptimized divg, modg, binvg
117 //#define WARN_UNOPTIMIZE FEE_DEBUG
118 #define WARN_UNOPTIMIZE 0
121 * Log interesting giant stack events
123 #define LOG_GIANT_STACK 0
126 * Log allocation of giant larger than stack size
128 #define LOG_GIANT_STACK_OVERFLOW 1
131 * Flag newGiant(0) and borrowGiant(0) calls
133 #define WARN_ZERO_GIANT_SIZE FEE_DEBUG
135 /* temp mac-only giant initialization debug */
136 #define GIANT_MAC_DEBUG 0
140 #include <TextUtils.h>
142 /* this one needs a writable string */
143 static void logCom(unsigned char *str
) {
148 /* constant strings */
149 void dblog0(const char *str
) {
151 strcpy((char *)outStr
, str
);
158 #endif /* GIANT_MAC_DEBUG */
161 #define min(a,b) ((a)<(b)? (a) : (b))
164 #define max(a,b) ((a)>(b)? (a) : (b))
174 static void absg(giant g
); /* g := |g|. */
176 /************** globals *******************/
179 /* ------ giant stack package ------ */
182 * The giant stack package is a local cache which allows us to avoid calls
183 * to malloc() for borrowGiant(). On a 90 Mhz Pentium, enabling the
184 * giant stack package shows about a 1.35 speedup factor over an identical
185 * CryptKit without the giant stacks enabled.
190 giant
borrowGiant(unsigned numDigits
)
193 result
= newGiant(numDigits
);
195 PROF_INCR(numBorrows
);
199 void returnGiant(giant g
)
204 void freeGiant(giant x
) {
208 giant
newGiant(unsigned numDigits
) {
209 // giant sufficient for 2^numbits+16 sized ops
213 #if WARN_ZERO_GIANT_SIZE
215 printf("newGiant(0)\n");
219 #endif // WARN_ZERO_GIANT_SIZE
221 size
= (numDigits
-1) * GIANT_BYTES_PER_DIGIT
+ sizeof(giantstruct
);
222 result
= (giant
)fmalloc(size
);
227 result
->capacity
= numDigits
;
231 giant
copyGiant(giant x
)
235 giant result
= newGiant(x
->capacity
);
239 * NO! this assumes packed alignment
241 bytes
= sizeof(giantstruct
) +
242 ((x
->capacity
- 1) * GIANT_BYTES_PER_DIGIT
);
243 bcopy(x
, result
, bytes
);
247 /* ------ initialization and utility routines ------ */
250 unsigned bitlen(giant n
) {
251 unsigned b
= GIANT_BITS_PER_DIGIT
;
252 giantDigit c
= ((giantDigit
)1) << (GIANT_BITS_PER_DIGIT
- 1);
258 w
= n
->n
[abs(n
->sign
) - 1];
260 CKRaise("bitlen - no bit set!");
266 return(GIANT_BITS_PER_DIGIT
* (abs(n
->sign
)-1) + b
);
269 int bitval(giant n
, int pos
) {
270 int i
= abs(pos
) >> GIANT_LOG2_BITS_PER_DIGIT
;
271 giantDigit c
= ((giantDigit
)1) << (pos
& (GIANT_BITS_PER_DIGIT
- 1));
273 return ((0!=((n
->n
[i
]) & c
))?1:0);
277 /* returns the sign of g */
279 if (isZero(g
)) return(0);
280 if (g
->sign
> 0) return(1);
285 * Adjust sign for possible leading (m.s.) zero digits
287 void gtrimSign(giant g
)
289 int numDigits
= abs(g
->sign
);
292 for(i
=numDigits
-1; i
>=0; i
--) {
301 g
->sign
= -numDigits
;
310 return((g
->sign
==1)&&(g
->n
[0]==1));
313 int isZero(giant thegiant
) {
314 /* Returns TRUE if thegiant == 0. */
316 int length
= abs(thegiant
->sign
);
317 giantDigit
*numpointer
;
320 numpointer
= thegiant
->n
;
322 for(count
= 0; count
<length
; ++count
,++numpointer
)
323 if (*numpointer
!= 0 ) return(FALSE
);
328 int gcompg(giant a
, giant b
)
329 /* returns -1,0,1 if a<b, a=b, a>b, respectively */
338 if(isZero(a
) && isZero(b
)) return 0;
339 if(sa
> sb
) return(1);
340 if(sa
< sb
) return(-1);
342 sa
= -sa
; /* Take absolute value of sa */
345 for(j
= sa
-1; j
>= 0; j
--) {
346 va
= a
->n
[j
]; vb
= b
->n
[j
];
347 if (va
> vb
) return(sgn
);
348 if (va
< vb
) return(-sgn
);
353 /* destgiant becomes equal to srcgiant */
354 void gtog(giant srcgiant
, giant destgiant
) {
358 CKASSERT(srcgiant
!= NULL
);
359 numbytes
= abs(srcgiant
->sign
) * GIANT_BYTES_PER_DIGIT
;
360 if (destgiant
->capacity
< abs(srcgiant
->sign
))
361 CKRaise("gtog overflow!!");
362 memcpy((char *)destgiant
->n
, (char *)srcgiant
->n
, numbytes
);
363 destgiant
->sign
= srcgiant
->sign
;
366 void int_to_giant(int i
, giant g
) {
367 /* The giant g becomes set to the integer value i. */
369 unsigned int j
= abs(i
);
378 if(GIANT_BYTES_PER_DIGIT
== sizeof(int)) {
383 /* one loop per digit */
384 unsigned scnt
= GIANT_BITS_PER_DIGIT
; // fool compiler
386 for(dex
=0; dex
<sizeof(int); dex
++) {
387 g
->n
[dex
] = j
& GIANT_DIGIT_MASK
;
396 g
->sign
= -(g
->sign
);
400 /*------------- Arithmetic --------------*/
407 void iaddg(int i
, giant g
) { /* positive g becomes g + (int)i */
410 int size
= abs(g
->sign
);
417 for(j
=0; ((j
<size
) && (carry
!= 0)); j
++) {
418 g
->n
[j
] = giantAddDigits(g
->n
[j
], carry
, &carry
);
423 if (g
->sign
> (int)g
->capacity
) CKRaise("iaddg overflow!");
432 * FIXME - we can improve this...
434 void imulg(unsigned n
, giant g
)
436 giant tmp
= borrowGiant(abs(g
->sign
) + sizeof(int));
438 int_to_giant(n
, tmp
);
443 static void normal_addg(giant a
, giant b
)
444 /* b := a + b, both a,b assumed non-negative. */
446 giantDigit carry1
= 0;
447 giantDigit carry2
= 0;
448 int asize
= a
->sign
, bsize
= b
->sign
;
449 giantDigit
*an
= a
->n
;
450 giantDigit
*bn
= b
->n
;
465 /* first handle the common digits */
466 for(j
=0; j
<comSize
; j
++) {
468 * first add the carry, then an[j] - either add could result
471 if(carry1
|| carry2
) {
472 tmp
= giantAddDigits(bn
[j
], (giantDigit
)1, &carry1
);
478 bn
[j
] = giantAddDigits(tmp
, an
[j
], &carry2
);
483 /* now propagate remaining carry beyond asize */
488 for(; j
<bsize
; j
++) {
489 bn
[j
] = giantAddDigits(bn
[j
], (giantDigit
)1, &carry1
);
496 /* now propagate remaining an[] and carry beyond bsize */
500 for(; j
<asize
; j
++) {
502 bn
[j
] = giantAddDigits(an
[j
], (giantDigit
)1, &carry1
);
515 if (b
->sign
> (int)b
->capacity
) CKRaise("iaddg overflow!");
520 static void normal_subg(giant a
, giant b
)
521 /* b := b - a; requires b, a non-negative and b >= a. */
526 giantDigit borrow1
= 0;
527 giantDigit borrow2
= 0;
528 giantDigit
*an
= a
->n
;
529 giantDigit
*bn
= b
->n
;
535 for (j
=0; j
<a
->sign
; ++j
) {
536 if(borrow1
|| borrow2
) {
537 tmp
= giantSubDigits(bn
[j
], (giantDigit
)1, &borrow1
);
543 bn
[j
] = giantSubDigits(tmp
, an
[j
], &borrow2
);
545 if(borrow1
|| borrow2
) {
546 /* propagate borrow thru remainder of bn[] */
548 for (j
=a
->sign
; j
<size
; ++j
) {
550 bn
[j
] = giantSubDigits(bn
[j
], (giantDigit
)1, &borrow1
);
558 /* adjust sign for leading zero digits */
559 while((size
-- > 0) && (b
->n
[size
] == 0))
561 b
->sign
= (b
->n
[size
] == 0)? 0 : size
+1;
564 static void reverse_subg(giant a
, giant b
)
565 /* b := a - b; requires b, a non-negative and a >= b. */
570 giantDigit borrow1
= 0;
571 giantDigit borrow2
= 0;
572 giantDigit
*an
= a
->n
;
573 giantDigit
*bn
= b
->n
;
579 for (j
=0; j
<b
->sign
; ++j
) {
580 if(borrow1
|| borrow2
) {
581 tmp
= giantSubDigits(an
[j
], (giantDigit
)1, &borrow1
);
587 bn
[j
] = giantSubDigits(tmp
, bn
[j
], &borrow2
);
589 if(borrow1
|| borrow2
) {
590 /* propagate borrow thru remainder of bn[] */
593 for (j
=b
->sign
; j
<size
; ++j
) {
595 bn
[j
] = giantSubDigits(an
[j
], (giantDigit
)1, &borrow1
);
603 b
->sign
= size
; /* REC, 21 Apr 1996. */
604 while(!b
->n
[--size
]);
609 void addg(giant a
, giant b
)
610 /* b := b + a, any signs any result. */
611 { int asgn
= a
->sign
, bsgn
= b
->sign
;
612 if(asgn
== 0) return;
617 if((asgn
< 0) == (bsgn
< 0)) {
622 negg(a
); if(a
!= b
) negg(b
); normal_addg(a
,b
); /* Fix REC 1 Dec 98. */
623 negg(a
); if(a
!= b
) negg(b
); return; /* Fix REC 1 Dec 98. */
627 if(gcompg(b
,a
) >= 0) {
638 if(gcompg(b
,a
) < 0) {
647 void subg(giant a
, giant b
)
648 /* b := b - a, any signs, any result. */
650 int asgn
= a
->sign
, bsgn
= b
->sign
;
651 if(asgn
== 0) return;
657 if((asgn
< 0) != (bsgn
< 0)) {
670 if(gcompg(b
,a
) >= 0) {
679 if(gcompg(b
,a
) >= 0) {
690 static void bdivg(giant v
, giant u
)
691 /* u becomes greatest power of two not exceeding u/v. */
693 int diff
= bitlen(u
) - bitlen(v
);
700 scratch7
= borrowGiant(u
->capacity
);
702 gshiftleft(diff
,scratch7
);
703 if(gcompg(u
,scratch7
) < 0) diff
--;
706 returnGiant(scratch7
);
711 returnGiant(scratch7
);
714 int binvaux(giant p
, giant x
)
715 /* Binary inverse method.
716 Returns zero if no inverse exists, in which case x becomes
728 if(isone(x
)) return(result
);
729 giantSize
= 4 * abs(p
->sign
);
730 scratch7
= borrowGiant(giantSize
);
731 u0
= borrowGiant(giantSize
);
732 u1
= borrowGiant(giantSize
);
733 v0
= borrowGiant(giantSize
);
734 v1
= borrowGiant(giantSize
);
735 int_to_giant(1, v0
); gtog(x
, v1
);
736 int_to_giant(0,x
); gtog(p
, u1
);
738 gtog(u1
, u0
); bdivg(v1
, u0
);
753 if(x
->sign
<0) addg(p
, x
);
757 if (x
->sign
<0) addg(p
, x
);
759 returnGiant(scratch7
);
764 PROF_END(binvauxTime
);
769 * Superceded by binvg_cp()
772 int binvg(giant p
, giant x
)
775 return(binvaux(p
,x
));
779 static void absg(giant g
) {
780 /* g becomes the absolute value of g */
781 if (g
->sign
< 0) g
->sign
= -g
->sign
;
784 void gshiftleft(int bits
, giant g
) {
785 /* shift g left bits bits. Equivalent to g = g*2^bits */
786 int rem
= bits
& (GIANT_BITS_PER_DIGIT
- 1);
787 int crem
= GIANT_BITS_PER_DIGIT
- rem
;
788 int digits
= 1 + (bits
>> GIANT_LOG2_BITS_PER_DIGIT
);
789 int size
= abs(g
->sign
);
798 CKRaise("gshiftleft(-bits)\n");
800 #endif /* FEE_DEBUG */
804 if((size
+digits
) > (int)g
->capacity
) {
805 CKRaise("gshiftleft overflow");
807 k
= size
- 1 + digits
; // (MSD of result + 1)
810 /* bug fix for 32-bit giantDigits; this is also an optimization for
811 * other sizes. rem=0 means we're shifting strictly by digits, no
814 g
->n
[k
] = 0; // XXX hack - for sign fixup
815 for(j
=size
-1; j
>=0; j
--) {
824 * normal unaligned case
825 * FIXME - this writes past g->n[size-1] the first time thru!
827 for(j
=size
-1; j
>=0; j
--) {
829 g
->n
[k
--] = (dat
>> crem
) | carry
;
830 carry
= (dat
<< rem
);
837 k
= size
- 1 + digits
;
838 if(g
->n
[k
] == 0) --k
;
839 g
->sign
= sign
* (k
+1);
840 if (abs(g
->sign
) > g
->capacity
) {
841 CKRaise("gshiftleft overflow");
845 void gshiftright(int bits
, giant g
) {
846 /* shift g right bits bits. Equivalent to g = g/2^bits */
848 int size
=abs(g
->sign
);
850 int digits
= bits
>> GIANT_LOG2_BITS_PER_DIGIT
;
851 int remain
= bits
& (GIANT_BITS_PER_DIGIT
- 1);
852 int cremain
= GIANT_BITS_PER_DIGIT
- remain
;
856 CKRaise("gshiftright(-bits)\n");
858 #endif /* FEE_DEBUG */
860 if(isZero(g
)) return;
861 if (digits
>= size
) {
868 /* Begin OPT: 9 Jan 98 REC. */
876 for(j
=0; j
< size
; j
++) {
877 g
->n
[j
] = g
->n
[j
+digits
];
881 /* End OPT: 9 Jan 98 REC. */
883 for(j
=0;j
<size
;++j
) {
888 carry
= (g
->n
[j
+digits
+1]) << cremain
;
890 g
->n
[j
] = ((g
->n
[j
+digits
]) >> remain
) | carry
;
892 if (g
->n
[size
-1] == 0) {
901 if (abs(g
->sign
) > g
->capacity
) {
902 CKRaise("gshiftright overflow");
907 void extractbits(unsigned n
, giant src
, giant dest
) {
908 /* dest becomes lowermost n bits of src. Equivalent to dest = src % 2^n */
909 int digits
= n
>> GIANT_LOG2_BITS_PER_DIGIT
;
910 int numbytes
= digits
* GIANT_BYTES_PER_DIGIT
;
911 int bits
= n
& (GIANT_BITS_PER_DIGIT
- 1);
916 if (dest
->capacity
* 8 * GIANT_BYTES_PER_DIGIT
< n
) {
917 CKRaise("extractbits - not enough room");
919 if (digits
>= abs(src
->sign
)) {
923 memcpy((char *)(dest
->n
), (char *)(src
->n
), numbytes
);
925 dest
->n
[digits
] = src
->n
[digits
] & ((1<<bits
)-1);
928 /* Next, fix by REC, 12 Jan 97. */
929 // while((dest->n[words-1] == 0) && (words > 0)) --words;
930 while((digits
> 0) && (dest
->n
[digits
-1] == 0)) {
934 dest
->sign
= -digits
;
940 if (abs(dest
->sign
) > dest
->capacity
) {
941 CKRaise("extractbits overflow");
945 #define NEW_MERSENNE 0
948 * New gmersennemod, 24 Dec 1997. This runs significantly slower than the
958 /* g := g (mod 2^n - 1) */
961 giant scratch3
= borrowGiant(g
->capacity
);
962 giant scratch4
= borrowGiant(1);
964 if ((the_sign
= gsign(g
)) < 0) absg(g
);
965 while (bitlen(g
) > n
) {
967 gshiftright(n
,scratch3
);
969 gshiftleft(n
,scratch3
);
972 if(isZero(g
)) goto out
;
973 int_to_giant(1,scratch3
);
974 gshiftleft(n
,scratch3
);
975 int_to_giant(1,scratch4
);
976 subg(scratch4
,scratch3
);
977 if(gcompg(g
,scratch3
) >= 0) subg(scratch3
,g
);
983 returnGiant(scratch3
);
984 returnGiant(scratch4
);
987 #else /* NEW_MERSENNE */
989 void gmersennemod(int n
, giant g
) {
990 /* g becomes g mod ((2^n)-1)
991 31 Jul 96 modified REC.
992 17 Jan 97 modified REC.
994 unsigned bits
= n
& (GIANT_BITS_PER_DIGIT
- 1);
995 unsigned digits
= 1 + ((n
-1) >> GIANT_LOG2_BITS_PER_DIGIT
);
996 int isPositive
= (g
->sign
> 0);
1001 giantDigit mask
= (bits
== 0) ? GIANT_DIGIT_MASK
: (giantDigit
)((1<<bits
)-1);
1006 unsigned numDigits
= (n
+ GIANT_BITS_PER_DIGIT
- 1) >>
1007 GIANT_LOG2_BITS_PER_DIGIT
;
1008 giantDigit lastWord
= 0;
1009 giantDigit bits
= 1;
1011 if(g
->sign
>= 0) return;
1014 * Cons up ((2**n)-1), add to g.
1016 scratch1
= borrowGiant(numDigits
+ 1);
1017 scratch1
->sign
= numDigits
;
1018 for(j
=0; j
<(int)(numDigits
-1); j
++) {
1019 scratch1
->n
[j
] = GIANT_DIGIT_MASK
;
1023 * Last word has lower (n & (GIANT_BITS_PER_DIGIT-1)) bits set.
1025 for(j
=0; j
< (int)(n
& (GIANT_BITS_PER_DIGIT
-1)); j
++) {
1029 scratch1
->n
[numDigits
-1] = lastWord
;
1030 addg(g
, scratch1
); /* One version. */
1032 returnGiant(scratch1
);
1036 for(foundzero
=0, j
=0; j
<b
; j
++) {
1037 if(bitval(g
, j
)==0) {
1049 scratch1
= borrowGiant(g
->capacity
);
1050 while ( ((unsigned)(g
->sign
) > digits
) ||
1051 ( ((unsigned)(g
->sign
)==digits
) && (g
->n
[digits
-1] > mask
))) {
1052 extractbits(n
, g
, scratch1
);
1058 /* Commence new negation routine - REC 17 Jan 1997. */
1059 if (!isPositive
) { /* Mersenne negation is just bitwise complement. */
1060 for(j
= digits
-1; j
>= size
; j
--) {
1061 g
->n
[j
] = GIANT_DIGIT_MASK
;
1063 for(j
= size
-1; j
>= 0; j
--) {
1066 g
->n
[digits
-1] &= mask
;
1068 while((g
->n
[j
] == 0) && (j
> 0)) {
1073 /* End new negation routine. */
1076 if (abs(g
->sign
) > g
->capacity
) {
1077 CKRaise("gmersennemod overflow");
1079 if (size
< (int)digits
) {
1082 if (g
->n
[size
-1] != mask
) {
1085 mask
= GIANT_DIGIT_MASK
;
1086 for(j
=0; j
<(size
-1); j
++) {
1087 if (g
->n
[j
] != mask
) {
1093 returnGiant(scratch1
);
1096 #endif /* NEW_MERSENNE */
1098 void mulg(giant a
, giant b
) { /* b becomes a*b. */
1102 giantDigit
*bptr
= b
->n
;
1121 bsize
= abs(b
->sign
);
1122 asize
= abs(a
->sign
);
1123 scratch1
= borrowGiant((asize
+bsize
));
1124 scrPtr
= scratch1
->n
;
1126 for(i
=0; i
<asize
+bsize
; ++i
) {
1130 for(i
=0; i
<bsize
; ++i
, scrPtr
++) {
1133 carry
= VectorMultiply(mult
,
1137 /* handle MSD carry */
1138 scrPtr
[asize
] += carry
;
1142 if(scratch1
->n
[bsize
- 1] == 0) {
1145 scratch1
->sign
= gsign(a
) * gsign(b
) * bsize
;
1146 if (abs(scratch1
->sign
) > scratch1
->capacity
) {
1147 CKRaise("GiantGrammarMul overflow");
1150 returnGiant(scratch1
);
1153 (void)bitlen(b
); // Assertion....
1154 #endif /* FEE_DEBUG */
1155 PROF_INCR(numMulg
); // for normal profiling
1156 INCR_MULGS
; // for ellipticMeasure
1159 void grammarSquare(giant a
) {
1161 * For now, we're going to match the old implementation line for
1162 * line by maintaining prod, carry, and temp as double precision
1163 * giantDigits. There is probably a much better implementation....
1167 giantDigit carryLo
= 0;
1168 giantDigit carryHi
= 0;
1171 unsigned int cur_term
;
1174 giantDigit
*ptr
= a
->n
;
1179 /* dmitch 11 Jan 1998 - special case for a == 0 */
1183 /* end a == 0 case */
1184 asize
= abs(a
->sign
);
1185 max
= asize
* 2 - 1;
1186 scratch
= borrowGiant(2 * asize
);
1192 * scratch->n[0] = temp;
1193 * carry = temp >> 16;
1195 giantMulDigits(*ptr
, *ptr
, &tempLo
, &tempHi
);
1196 scratch
->n
[0] = tempLo
;
1200 for (cur_term
= 1; cur_term
< max
; cur_term
++) {
1202 if (cur_term
<= asize
) {
1205 ptr1
+= cur_term
- asize
;
1210 * prod = carry & 0xFFFF;
1217 while(ptr1
< ptr2
) {
1219 * temp = *ptr1++ * *ptr2--;
1221 giantMulDigits(*ptr1
++, *ptr2
--, &tempLo
, &tempHi
);
1224 * prod += (temp << 1) & 0xFFFF;
1226 giantAddDouble(&prodLo
, &prodHi
, (tempLo
<< 1));
1229 * carry += (temp >> 15);
1230 * use bits from both product digits..
1232 giantAddDouble(&carryLo
, &carryHi
,
1233 (tempLo
>> (GIANT_BITS_PER_DIGIT
- 1)));
1234 giantAddDouble(&carryLo
, &carryHi
, (tempHi
<< 1));
1236 /* snag the msb from that last shift */
1237 carryHi
+= (tempHi
>> (GIANT_BITS_PER_DIGIT
- 1));
1244 giantMulDigits(*ptr1
, *ptr1
, &tempLo
, &tempHi
);
1247 * prod += temp & 0xFFFF;
1249 giantAddDouble(&prodLo
, &prodHi
, tempLo
);
1252 * carry += (temp >> 16);
1254 giantAddDouble(&carryLo
, &carryHi
, tempHi
);
1258 * carry += prod >> 16;
1260 giantAddDouble(&carryLo
, &carryHi
, prodHi
);
1262 scratch
->n
[cur_term
] = prodLo
;
1265 scratch
->n
[cur_term
] = carryLo
;
1266 scratch
->sign
= cur_term
+1;
1267 } else scratch
->sign
= cur_term
;
1270 returnGiant(scratch
);
1272 PROF_INCR(numGsquare
);
1276 * Clear all of a giant's data fields, for secure erasure of sensitive data.,
1278 void clearGiant(giant g
)
1282 for(i
=0; i
<g
->capacity
; i
++) {
1292 * Calculate the reciprocal of a demonimator used in divg_via_recip() and
1296 make_recip(giant d
, giant r
)
1297 /* r becomes the steady-state reciprocal
1298 2^(2b)/d, where b = bit-length of d-1. */
1301 int giantSize
= 4 * abs(d
->sign
);
1302 giant tmp
= borrowGiant(giantSize
);
1303 giant tmp2
= borrowGiant(giantSize
);
1305 if (isZero(d
) || (d
->sign
< 0))
1307 CKRaise("illegal argument to make_recip");
1309 int_to_giant(1, r
); subg(r
, d
); b
= bitlen(d
); addg(r
, d
);
1310 gshiftleft(b
, r
); gtog(r
, tmp2
);
1314 gshiftright(b
, tmp
);
1316 gshiftright(b
, tmp
);
1317 addg(r
, r
); subg(tmp
, r
);
1318 if(gcompg(r
, tmp2
) <= 0) break;
1321 int_to_giant(1, tmp
);
1322 gshiftleft(2*b
, tmp
);
1323 gtog(r
, tmp2
); mulg(d
, tmp2
);
1325 int_to_giant(1, tmp2
);
1326 while(tmp
->sign
< 0) {
1337 * Optimized divg, when reciprocal of denominator is known.
1340 divg_via_recip(giant d
, giant r
, giant n
)
1341 /* n := n/d, where r is the precalculated
1342 steady-state reciprocal of d. */
1344 int s
= 2*(bitlen(r
)-1), sign
= gsign(n
);
1345 int giantSize
= (4 * abs(d
->sign
)) + abs(n
->sign
);
1346 giant tmp
= borrowGiant(giantSize
);
1347 giant tmp2
= borrowGiant(giantSize
);
1349 if (isZero(d
) || (d
->sign
< 0))
1351 CKRaise("illegal argument to divg_via_recip");
1353 n
->sign
= abs(n
->sign
);
1354 int_to_giant(0, tmp2
);
1358 gshiftright(s
, tmp
);
1362 if(gcompg(n
,d
) >= 0) {
1366 if(gcompg(n
,d
) < 0) break;
1376 * Optimized modg, when reciprocal of denominator is known.
1379 /* New version, 24 Dec 1997. */
1387 /* This is the fastest mod of the present collection.
1388 n := n % d, where r is the precalculated
1389 steady-state reciprocal of d. */
1392 int s
= (bitlen(r
)-1), sign
= n
->sign
;
1393 int giantSize
= (4 * abs(d
->sign
)) + abs(n
->sign
);
1396 tmp
= borrowGiant(giantSize
);
1397 tmp2
= borrowGiant(giantSize
);
1398 if (isZero(d
) || (d
->sign
< 0))
1400 CKRaise("illegal argument to modg_via_recip");
1402 n
->sign
= abs(n
->sign
);
1406 /* bug fix 13 Apr 1998 */
1411 gshiftright(s
-1, tmp
);
1415 gshiftright(s
+1, tmp
);
1418 if (gcompg(n
,d
) >= 0)
1420 if (gcompg(n
,d
) < 0)
1436 * Unoptimized, inefficient general modg, when reciprocal of denominator
1445 /* n becomes n%d. n is arbitrary, but the denominator d must be
1449 * 4/9/2001: seeing overflow on this recip. Alloc per
1450 * d->capacity, not d->sign.
1452 //giant recip = borrowGiant(2 * abs(d->sign));
1453 giant recip
= borrowGiant(2 * d
->capacity
);
1456 dbgLog(("Warning: unoptimized modg!\n"));
1457 #endif // WARN_UNOPTIMIZE
1459 make_recip(d
, recip
);
1460 modg_via_recip(d
, recip
, n
);
1465 * Unoptimized, inefficient general divg, when reciprocal of denominator
1474 /* n becomes n/d. n is arbitrary, but the denominator d must be
1478 giant recip
= borrowGiant(2 * abs(d
->sign
));
1481 dbgLog(("Warning: unoptimized divg!\n"));
1482 #endif // WARN_UNOPTIMIZE
1484 make_recip(d
, recip
);
1485 divg_via_recip(d
, recip
, n
);