?lang_form? ?lang_select? ?lang_submit? ?lang_endform?
{HEADER END}
{BLAME START}

library

?curdirlinks? -

Blame information for rev 32

Line No. Rev Author Line
1 32 kaklik /*********************************************************************
2 *
3 * Big Integer Library
4 * Library for Microchip TCP/IP Stack
5 * - Provides support for integers larger than 32 bits
6 *
7 *********************************************************************
8 * FileName: BigInt.c
9 * Dependencies: BigInt_helper.asm (PIC18), BigInt_helper.S
10 * (PIC24/dsPIC) or BigInt_helper_C32.S (PIC32)
11 * Processor: PIC18, PIC24F, PIC24H, dsPIC30F, dsPIC33F, PIC32
12 * Compiler: Microchip C32 v1.05 or higher
13 * Microchip C30 v3.12 or higher
14 * Microchip C18 v3.30 or higher
15 * Company: Microchip Technology, Inc.
16 *
17 * Software License Agreement
18 *
19 * Copyright (C) 2002-2009 Microchip Technology Inc. All rights
20 * reserved.
21 *
22 * Microchip licenses to you the right to use, modify, copy, and
23 * distribute:
24 * (i) the Software when embedded on a Microchip microcontroller or
25 * digital signal controller product ("Device") which is
26 * integrated into Licensee's product; or
27 * (ii) ONLY the Software driver source files ENC28J60.c, ENC28J60.h,
28 * ENCX24J600.c and ENCX24J600.h ported to a non-Microchip device
29 * used in conjunction with a Microchip ethernet controller for
30 * the sole purpose of interfacing with the ethernet controller.
31 *
32 * You should refer to the license agreement accompanying this
33 * Software for additional information regarding your rights and
34 * obligations.
35 *
36 * THE SOFTWARE AND DOCUMENTATION ARE PROVIDED "AS IS" WITHOUT
37 * WARRANTY OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT
38 * LIMITATION, ANY WARRANTY OF MERCHANTABILITY, FITNESS FOR A
39 * PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT SHALL
40 * MICROCHIP BE LIABLE FOR ANY INCIDENTAL, SPECIAL, INDIRECT OR
41 * CONSEQUENTIAL DAMAGES, LOST PROFITS OR LOST DATA, COST OF
42 * PROCUREMENT OF SUBSTITUTE GOODS, TECHNOLOGY OR SERVICES, ANY CLAIMS
43 * BY THIRD PARTIES (INCLUDING BUT NOT LIMITED TO ANY DEFENSE
44 * THEREOF), ANY CLAIMS FOR INDEMNITY OR CONTRIBUTION, OR OTHER
45 * SIMILAR COSTS, WHETHER ASSERTED ON THE BASIS OF CONTRACT, TORT
46 * (INCLUDING NEGLIGENCE), BREACH OF WARRANTY, OR OTHERWISE.
47 *
48 *
49 * Author Date Comment
50 *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
51 * Elliott Wood 6/20/07 Original
52 * Howard Schlunder 11/21/07 Converted to little endian
53 ********************************************************************/
54 #define __BIGINT_C
55  
56 #include "TCPIPConfig.h"
57 #include "HardwareProfile.h"
58  
59 #if (defined(STACK_USE_SSL_SERVER) || defined(STACK_USE_SSL_CLIENT)) && !defined(ENC100_INTERFACE_MODE)
60  
61 #include "TCPIP Stack/TCPIP.h"
62  
63 // External declarations for assembly helpers
64 #if defined(__C30__)
65 extern __attribute__((__near__)) BIGINT_DATA_TYPE *_iA, *_iB, *_xA, *_xB, *_iR, _wC;
66 #else
67 extern BIGINT_DATA_TYPE *_iA, *_iB, *_xA, *_xB, *_iR, _wC;
68 #endif
69 extern void _addBI(void);
70 extern void _subBI(void);
71 extern void _zeroBI(void);
72 extern void _msbBI(void);
73 extern void _mulBI(void);
74 extern void _copyBI(void);
75 extern void _sqrBI(void);
76 extern void _masBI(void);
77 extern void _addBIROM(void);
78 extern void _subBIROM(void);
79 extern void _mulBIROM(void);
80 extern void _masBIROM(void);
81  
82  
83 #if BIGINT_PROFILE
84 DWORD addBICounter = 0;
85 DWORD addBIROMCounter = 0;
86 DWORD subBICounter = 0;
87 DWORD subBIROMCounter = 0;
88 DWORD zeroBICounter = 0;
89 DWORD msbBICounter = 0;
90 DWORD mulBICounter = 0;
91 DWORD mulBIROMCounter = 0;
92 DWORD sqrBICounter = 0;
93 DWORD masBICounter = 0;
94 DWORD masBIROMCounter = 0;
95 DWORD copyBICounter = 0;
96  
97 #define addBI() {addBICounter -= TickGet(); _addBI(); addBICounter += TickGet();}
98 #define addBIROM() {addBIROMCounter -= TickGet(); _addBIROM();addBIROMCounter += TickGet();}
99 #define subBI() {subBICounter -= TickGet(); _subBI(); subBICounter += TickGet();}
100 #define subBIROM() {subBIROMCounter -= TickGet(); _subBIROM(); subBIROMCounter += TickGet();}
101 #define zeroBI() {zeroBICounter -= TickGet(); _zeroBI(); zeroBICounter += TickGet();}
102 #define msbBI() {msbBICounter -= TickGet(); _msbBI(); msbBICounter += TickGet();}
103 #define mulBI() {mulBICounter -= TickGet(); _mulBI(); mulBICounter += TickGet();}
104 #define mulBIROM() {mulBIROMCounter -= TickGet(); _mulBIROM(); mulBIROMCounter += TickGet();}
105 #define sqrBI() {sqrBICounter -= TickGet(); _sqrBI(); sqrBICounter += TickGet();}
106 #define masBI() {masBICounter -= TickGet(); _masBI(); masBICounter += TickGet();}
107 #define masBIROM() {masBIROMCounter -= TickGet(); _masBIROM(); masBIROMCounter += TickGet();}
108 #define copyBI() {copyBICounter -= TickGet(); _copyBI(); copyBICounter += TickGet();}
109 #else
110 #define addBI() _addBI()
111 #define addBIROM() _addBIROM()
112 #define subBI() _subBI()
113 #define subBIROM() _subBIROM()
114 #define zeroBI() _zeroBI()
115 #define msbBI() _msbBI()
116 #define mulBI() _mulBI()
117 #define mulBIROM() _mulBIROM()
118 #define sqrBI() _sqrBI()
119 #define masBI() _masBI()
120 #define masBIROM() _masBIROM()
121 #define copyBI() _copyBI()
122 #endif
123  
124 #if BIGINT_DEBUG
125 #if defined(__18CXX)
126 void BigIntPrint(const BIGINT *a)
127 {
128 BIGINT_DATA_TYPE *ptr;
129  
130 for(ptr = a->ptrMSBMax; ptr >= a->ptrLSB; ptr--)
131 {
132 while(BusyUART());
133 putcUART(btohexa_high(*ptr));
134 while(BusyUART());
135 putcUART(btohexa_low(*ptr));
136 }
137 }
138 void BigIntPrintROM(BIGINT_ROM *a)
139 {
140 ROM BIGINT_DATA_TYPE *ptr;
141  
142 for(ptr = a->ptrMSB; ptr >= a->ptrLSB; ptr--)
143 {
144 while(BusyUART());
145 putcUART(btohexa_high(*ptr));
146 while(BusyUART());
147 putcUART(btohexa_low(*ptr));
148 }
149 }
150 #elif defined(__C30__)
151 void BigIntPrint(const BIGINT *a)
152 {
153 WORD w;
154 BYTE v;
155  
156 BIGINT_DATA_TYPE *ptr;
157  
158 for(ptr = a->ptrMSBMax; ptr >= a->ptrLSB; ptr--)
159 {
160 WORD_VAL wv;
161  
162 wv.Val = *ptr;
163  
164 while(BusyUART());
165 putcUART(btohexa_high(wv.v[1]));
166 while(BusyUART());
167 putcUART(btohexa_low(wv.v[1]));
168 while(BusyUART());
169 putcUART(btohexa_high(wv.v[0]));
170 while(BusyUART());
171 putcUART(btohexa_low(wv.v[0]));
172 }
173 }
174 #endif
175  
176 void putulhexUART(DWORD dw)
177 {
178 while(BusyUART());
179 putcUART('0');
180 while(BusyUART());
181 putcUART('x');
182 while(BusyUART());
183 putcUART(btohexa_high(((BYTE*)&dw)[3]));
184 while(BusyUART());
185 putcUART(btohexa_low(((BYTE*)&dw)[3]));
186 while(BusyUART());
187 putcUART(btohexa_high(((BYTE*)&dw)[2]));
188 while(BusyUART());
189 putcUART(btohexa_low(((BYTE*)&dw)[2]));
190 while(BusyUART());
191 putcUART(btohexa_high(((BYTE*)&dw)[1]));
192 while(BusyUART());
193 putcUART(btohexa_low(((BYTE*)&dw)[1]));
194 while(BusyUART());
195 putcUART(btohexa_high(((BYTE*)&dw)[0]));
196 while(BusyUART());
197 putcUART(btohexa_low(((BYTE*)&dw)[0]));
198 }
199 #endif
200  
201  
202 static BIGINT_DATA_TYPE* BigIntMSB(BIGINT *n);
203  
204 /*********************************************************************
205 * Function: void BigInt(BIGINT *theInt, BIGINT_DATA_TYPE *data, WORD wWordLength)
206 *
207 * PreCondition: None
208 *
209 * Input: *theInt: the integer to create
210 * *data: a pointer to the data
211 * wWordLength: the number of words in the integer (a word is 1 byte on PIC18s, 2 bytes on PIC24/dsPIC)
212 *
213 * Output: The BIGINT is ready to use
214 *
215 * Side Effects: None
216 *
217 * Overview: Call BigInt() to correctly set up the pointers.
218 *
219 * Note: None
220 ********************************************************************/
221 #if defined(BI_USE_CONSTRUCTOR)
222 void BigInt(BIGINT *theInt, BIGINT_DATA_TYPE *data, WORD wWordLength)
223 {
224 theInt->ptrLSB = data;
225 theInt->ptrMSB = data + wWordLength - 1;
226 theInt->ptrMSBMax = theInt->ptrMSB;
227 theInt->bMSBValid = 0;
228 }
229 #endif
230  
231 #if defined(__18CXX) && defined(BI_USE_CONSTRUCTOR_ROM)
232 void BigIntROM(BIGINT_ROM *theInt, ROM BIGINT_DATA_TYPE *data, WORD wWordLength)
233 {
234 theInt->ptrLSB = data;
235 theInt->ptrMSB = data + wWordLength - 1;
236  
237 // Find the MSB, which can never change
238 while(*theInt->ptrMSB == 0u)
239 theInt->ptrMSB--;
240 }
241 #endif
242  
243 /*********************************************************************
244 * Function: void BigIntZero(BIGINT* theInt)
245 *
246 * PreCondition: None
247 *
248 * Input: *theInt: the integer to clear
249 *
250 * Output: theInt = 0
251 *
252 * Side Effects: None
253 *
254 * Overview: Call BigIntZero() zero all data bytes in the BigInt
255 *
256 * Note: None
257 ********************************************************************/
258 #if defined(BI_USE_ZERO)
259 void BigIntZero(BIGINT *theInt)
260 {
261 _iA = theInt->ptrLSB;
262 _xA = theInt->ptrMSBMax;
263 zeroBI();
264  
265 // Set up the new MSB pointer
266 theInt->ptrMSB = theInt->ptrLSB;
267 theInt->bMSBValid = 1;
268 }
269 #endif
270  
271 /*********************************************************************
272 * Function: void BigIntMod(BIGINT *n, const BIGINT* m)
273 *
274 * PreCondition: None
275 *
276 * Input: *n: a pointer to the number
277 * *m: a pointer to the modulus
278 *
279 * Output: *n contains the modded number
280 * i.e: *n = *n % *m
281 *
282 * Side Effects: None
283 *
284 * Overview: Call BigIntMod() to calculate the modulus of two
285 * really big numbers.
286 *
287 * Note: Supports at least 2048 bits
288 ********************************************************************/
289 #if defined(BI_USE_MOD)
290 void BigIntMod(BIGINT *n, BIGINT* m)
291 {
292 BIGINT_DATA_TYPE *ptrMSBn, MSBm;
293 BIGINT_DATA_TYPE_2 qHatInt;
294 union
295 {
296 BIGINT_DATA_TYPE v[2];
297 BIGINT_DATA_TYPE_2 Val;
298 } topTwoWords;
299  
300 // Find the starting MSBs
301 ptrMSBn = BigIntMSB(n);
302 MSBm = *BigIntMSB(m);
303  
304 // Set up assembly pointers for m
305 // _iB and _xB are limiters in the _mas function
306 _iB = m->ptrLSB;
307 _xB = BigIntMSB(m);
308  
309 // Find out how many bytes we need to shift and move the LSB up
310 _iR = n->ptrLSB + (BigIntMagnitudeDifference(n, m) - 1);
311  
312 // This loops while the order of magnitude (in words) of n > m
313 // Each iteration modulos off one word of magnitude from n
314 while(_iR >= n->ptrLSB)
315 {
316 // Find qHat = MSBn:MSBn-1/MSBm
317 topTwoWords.Val = *((BIGINT_DATA_TYPE_2*)(ptrMSBn - 1));
318 qHatInt = topTwoWords.Val / MSBm;
319 if(qHatInt > BIGINT_DATA_MAX)
320 qHatInt = BIGINT_DATA_MAX;
321  
322 #if BIGINT_DEBUG
323 putrsUART("\r\n\r\n n = ");
324 BigIntPrint(n);
325 putrsUART("\r\n m = ");
326 BigIntPrint(m);
327 putrsUART("\r\n qHat (");
328 putulhexUART(qHatInt);
329 putrsUART(") = topTwo(");
330 putulhexUART(topTwoWords.Val);
331 putrsUART(") / (");
332 putulhexUART(MSBm);
333 putrsUART(") ");
334 #endif
335  
336 // Once qHat is determined, we multiply M by qHat, shift it up
337 // as many bytes as possible, and subtract the result.
338 // In essence, qHat is a rough estimation of the quotient, divided
339 // by a power of 2^8 (PIC18) or 2^16 (PIC24/dsPIC) or 2^32 (PIC32)
340  
341 // This implementation multiplies and subtracts in the same step
342 // using a _mas function which saves about 30% of clock cycles.
343  
344 // Save the old MSB and set up the ASM pointers
345 _wC = (BIGINT_DATA_TYPE)qHatInt;
346  
347 // Do the multiply and subtract
348 // Occassionally this results in underflow...this is solved below.
349 masBI();
350  
351 // qHat may have been 1 or 2 greater than possible. If so,
352 // the new MSB will be greater than the old one, so we *add*
353 // M back to N in the shifted position until overflow occurs
354 // and this case corrects itself.
355 while(topTwoWords.v[1] < *BigIntMSB(n))
356 // while(((BIGINT_DATA_TYPE*)&topTwoWords)[1] < *BigIntMSB(n))
357 {
358 _iA = _iR;
359 _xA = BigIntMSB(n);
360 addBI();
361 }
362  
363 // We should have modulated off a word (or two if we were lucky),
364 // so move our MSB and LSB pointers as applicable
365 while(*ptrMSBn == 0x0u)
366 {
367 _iR--;
368 n->ptrMSB--;
369 ptrMSBn--;
370 }
371 }
372  
373 // Iteration of the _mas function can only handle full-byte orders
374 // of magnitude. The result may still be a little larger, so this
375 // cleans up the last few multiples with simple subtraction.
376 while(BigIntCompare(n, m) >= 0)
377 {
378 _iA = n->ptrLSB;
379 _xA = n->ptrMSB;
380 subBI();
381  
382 // Invalidate MSB pointer
383 n->bMSBValid = 0;
384 }
385 }
386 #endif
387  
388 #if defined(__18CXX) && defined(BI_USE_MOD_ROM)
389 void BigIntModROM(BIGINT *n, BIGINT_ROM* m)
390 {
391 BIGINT_DATA_TYPE *ptrMSBn, MSBm;
392 BIGINT_DATA_TYPE_2 qHatInt, topTwoWords;
393  
394 // Find the starting MSBs
395 ptrMSBn = BigIntMSB(n);
396 MSBm = *m->ptrMSB;
397  
398 // Set up assembly pointers for m
399 // _iBr and _xBr are limiters in the _masROM function
400 _iBr = m->ptrLSB;
401 _xBr = m->ptrMSB;
402  
403 // Find out how many bytes we need to shift and move the LSB up
404 _iR = n->ptrLSB + (BigIntMagnitudeDifferenceROM(n, m) - 1);
405  
406 // This loops while the order of magnitude (in words) of n > m
407 // Each iteration modulos off one word of magnitude from n
408 while(_iR >= n->ptrLSB)
409 {
410 // Find qHat = MSBn:MSBn-1/MSBm
411 topTwoWords = *((BIGINT_DATA_TYPE_2*)(ptrMSBn - 1));
412 qHatInt = topTwoWords / MSBm;
413 if(qHatInt > BIGINT_DATA_MAX)
414 qHatInt = BIGINT_DATA_MAX;
415  
416 #if BIGINT_DEBUG
417 putrsUART("\r\n\r\n n = ");
418 BigIntPrint(n);
419 putrsUART("\r\n m = ");
420 BigIntPrintROM(m);
421 putrsUART("\r\n qHat (");
422 putulhexUART(qHatInt);
423 putrsUART(") = topTwo(");
424 putulhexUART(topTwoWords);
425 putrsUART(") / (");
426 putulhexUART(MSBm);
427 putrsUART(") ");
428 #endif
429  
430 // Once qHat is determined, we multiply M by qHat, shift it up
431 // as many bytes as possible, and subtract the result.
432 // In essence, qHat is a rough estimation of the quotient, divided
433 // by a power of 2^8 (PIC18) or 2^16 (PIC24/dsPIC) or 2^32 (PIC32)
434  
435 // This implementation multiplies and subtracts in the same step
436 // using a _mas function which saves about 30% of clock cycles.
437  
438 // Save the old MSB and set up the ASM pointers
439 _wC = (BIGINT_DATA_TYPE)qHatInt;
440  
441 // Do the multiply and subtract
442 // Occassionally this results in underflow...this is solved below.
443 masBIROM();
444  
445 // qHat may have been 1 or 2 greater than possible. If so,
446 // the new MSB will be greater than the old one, so we *add*
447 // M back to N in the shifted position until overflow occurs
448 // and this case corrects itself.
449 while(((BIGINT_DATA_TYPE*)&topTwoWords)[1] < *BigIntMSB(n))
450 {
451 _iA = _iR;
452 _xA = BigIntMSB(n);
453 addBIROM();
454 }
455  
456 // We should have modulated off a word (or two if we were lucky),
457 // so move our MSB and LSB pointers as applicable
458 while(*ptrMSBn == 0x0u)
459 {
460 _iR--;
461 n->ptrMSB--;
462 ptrMSBn--;
463 }
464 }
465  
466 // Iteration of the _mas function can only handle full-byte orders
467 // of magnitude. The result may still be a little larger, so this
468 // cleans up the last few multiples with simple subtraction.
469 while(BigIntCompareROM(n, m) >= 0)
470 {
471 _iA = n->ptrLSB;
472 _xA = n->ptrMSB;
473 subBIROM();
474  
475 // Invalidate MSB pointer
476 n->bMSBValid = 0;
477 }
478 }
479 #endif
480  
481 /*********************************************************************
482 * Function: CHAR BigIntCompare(BIGINT *a, BIGINT *b)
483 *
484 * PreCondition: None
485 *
486 * Input: *a: a pointer to the first number
487 * *b: a pointer to the second number
488 *
489 * Output: 0 if a == b
490 * 1 if a > b
491 * -1 if a < b
492 *
493 * Side Effects: None
494 *
495 * Overview: Determines if a > b, a < b, or a == b
496 *
497 * Note: Supports at least 2048 bits.
498 *
499 ********************************************************************/
500 #if defined(BI_USE_COMPARE)
501 CHAR BigIntCompare(BIGINT *a, BIGINT *b)
502 {
503 PTR_BASE magA, magB;
504 BIGINT_DATA_TYPE valA, valB;
505 BIGINT_DATA_TYPE *ptrA;
506 BIGINT_DATA_TYPE *ptrB;
507  
508 magA = BigIntMSB(a) - a->ptrLSB;
509 magB = BigIntMSB(b) - b->ptrLSB;
510  
511 #if BIGINT_DEBUG_COMPARE
512 putrsUART("\r\n Compared Magnitudes |a|:");
513 putulhexUART(w1);
514 putrsUART(" |b|:");
515 putulhexUART(w2);
516 putrsUART(" diff:");
517 putulhexUART(w1-w2);
518 #endif
519  
520 if(magA > magB)
521 {
522 #if BIGINT_DEBUG_COMPARE
523 putrsUART(" a > b");
524 #endif
525  
526 return 1;
527 }
528 else if(magA < magB)
529 {
530 #if BIGINT_DEBUG_COMPARE
531 putrsUART(" a < b");
532 #endif
533  
534 return -1;
535 }
536  
537 #if BIGINT_DEBUG_COMPARE
538 putrsUART(" Checking further bytes...");
539 #endif
540  
541 // Loop through all words, looking for a non-equal word
542 ptrA = BigIntMSB(a);
543 ptrB = BigIntMSB(b);
544 while(ptrA >= a->ptrLSB) // Magnitude is same, no need to check ptrB bounds
545 {
546 valA = *ptrA--;
547 valB = *ptrB--;
548  
549 if(valA > valB)
550 {
551 #if BIGINT_DEBUG_COMPARE
552 putrsUART(" a > b");
553 #endif
554  
555 return 1;
556 }
557 else if(valA < valB)
558 {
559 #if BIGINT_DEBUG_COMPARE
560 putrsUART(" a < b");
561 #endif
562  
563 return -1;
564 }
565 }
566  
567 // All words were exactly identical, return match
568 return 0;
569 }
570 #endif
571  
572 #if defined(__18CXX) && defined(BI_USE_COMPARE_ROM)
573 CHAR BigIntCompareROM(BIGINT *a, BIGINT_ROM *b)
574 {
575 PTR_BASE magA, magB;
576 BIGINT_DATA_TYPE valA, valB;
577 BIGINT_DATA_TYPE *ptrA;
578 ROM BIGINT_DATA_TYPE *ptrB;
579  
580 magA = BigIntMSB(a) - a->ptrLSB;
581 magB = b->ptrMSB - b->ptrLSB;
582  
583 #if BIGINT_DEBUG_COMPARE
584 putrsUART("\r\n Compared Magnitudes |a|:");
585 putulhexUART(w1);
586 putrsUART(" |b|:");
587 putulhexUART(w2);
588 putrsUART(" diff:");
589 putulhexUART(s);
590 #endif
591  
592 if(magA > magB)
593 {
594 #if BIGINT_DEBUG_COMPARE
595 putrsUART(" a > b");
596 #endif
597  
598 return 1;
599 }
600 else if(magA < magB)
601 {
602 #if BIGINT_DEBUG_COMPARE
603 putrsUART(" a < b");
604 #endif
605  
606 return -1;
607 }
608  
609 #if BIGINT_DEBUG_COMPARE
610 putrsUART(" Checking further bytes...");
611 #endif
612  
613 // Loop through all words, looking for a non-equal word
614 ptrA = BigIntMSB(a);
615 ptrB = b->ptrMSB;
616 while(ptrA >= a->ptrLSB) // Magnitude is same, no need to check ptrB bounds
617 {
618 valA = *ptrA--;
619 valB = *ptrB--;
620  
621 if(valA > valB)
622 {
623 #if BIGINT_DEBUG_COMPARE
624 putrsUART(" a > b");
625 #endif
626  
627 return 1;
628 }
629 else if (valA < valB)
630 {
631 #if BIGINT_DEBUG_COMPARE
632 putrsUART(" a < b");
633 #endif
634  
635 return -1;
636 }
637 }
638  
639 // All words were exactly identical, return match
640 return 0;
641 }
642 #endif
643  
644  
645 /*********************************************************************
646 * Function: int BigIntMagnitudeDifference(const BIGINT *n)
647 *
648 * PreCondition: None
649 *
650 * Input: *a: a pointer to the first number
651 * *b: a pointer to the second number
652 *
653 * Output: Returns the magnitude of difference in zero-bytes
654 *
655 * Side Effects: None
656 *
657 * Overview: Helps to quickly determine a byte shift for operations
658 *
659 * Note: Supports at least 2048 bits
660 ********************************************************************/
661 #if defined(BI_USE_MAG_DIFF)
662 int BigIntMagnitudeDifference(BIGINT *a, BIGINT *b)
663 {
664 return BigIntMagnitude(a) - BigIntMagnitude(b);
665 }
666 #endif
667  
668 #if defined(__18CXX) && defined(BI_USE_MAG_DIFF_ROM)
669 int BigIntMagnitudeDifferenceROM(BIGINT *a, BIGINT_ROM *b)
670 {
671 return BigIntMagnitude(a) - BigIntMagnitudeROM(b);
672 }
673 #endif
674  
675 /*********************************************************************
676 * Function: WORD BigIntMagnitude(BIGINT *n)
677 *
678 * PreCondition: None
679 *
680 * Input: *n: a pointer to the number
681 *
682 * Output: Returns the number of significant words in the data, less one (ex: 0x12, has zero magnitude)
683 *
684 * Side Effects: None
685 *
686 * Overview: Helps to quickly determine the magnitude of the number
687 *
688 * Note: Supports at least 2048 bits
689 ********************************************************************/
690 #if defined(BI_USE_MAG)
691 WORD BigIntMagnitude(BIGINT *n)
692 {
693 return BigIntMSB(n) - n->ptrLSB;
694 }
695 #endif
696  
697 #if defined(__18CXX) && defined(BI_USE_MAG_ROM)
698 WORD BigIntMagnitudeROM(BIGINT_ROM *n)
699 {
700 return n->ptrMSB - n->ptrLSB;
701 }
702 #endif
703  
704 /*********************************************************************
705 * Function: static BIGINT_DATA_TYPE* BigIntMSB(const BIGINT *n)
706 *
707 * PreCondition: None
708 *
709 * Input: *n: a pointer to the number
710 *
711 * Output: n->ptrMSB points to the MSB of n
712 *
713 * Side Effects: None
714 *
715 * Overview: Updates the ptrMSB. Use after an operation in which
716 * the new MSB cannot be estimated.
717 *
718 * Note: Supports at least 2048 bits
719 ********************************************************************/
720 #if defined(BI_USE_MSB)
721 static BIGINT_DATA_TYPE* BigIntMSB(BIGINT *n)
722 {
723 BIGINT_DATA_TYPE *iASave, *xASave;
724  
725 // If cached value is valid, use it
726 if(n->bMSBValid)
727 return n->ptrMSB;
728  
729 // Otherwise find a new MSB and save it
730 iASave = _iA;
731 xASave = _xA;
732 _iA = n->ptrLSB;
733 _xA = n->ptrMSBMax;
734 msbBI();
735 n->ptrMSB = _xA;
736 n->bMSBValid = 1;
737  
738 _iA = iASave;
739 _xA = xASave;
740  
741 return n->ptrMSB;
742 }
743 #endif
744  
745 /*********************************************************************
746 * Function: void BigIntMultiply(const BIGINT *a, const BIGINT *b, BIGINT *res)
747 *
748 * PreCondition: res->ptrMSBMax - res->ptrLSB + 1 >= a->ptrMSBMax - a->ptrLSB + 1 + b->ptrMSBMax - b->ptrLSB + 1, &res != &[a|b]
749 *
750 * Input: *a: a pointer to the first number
751 * *b: a pointer to the second number
752 * *res: a pointer to memory to store the result
753 *
754 * Output: *res contains the result of a * b
755 *
756 * Side Effects: None
757 *
758 * Overview: Call BigIntMultiply() to multiply two really big numbers.
759 *
760 * Note: Supports at least 2048 result bits.
761 * This essentially implements elementary school long
762 * multiplication in base 256 (PIC18) or 65536 (PIC24/dsPIC).
763 * This is the fastest algorithm until you pass about
764 * 1024 bits. This is O(n^2).
765 * res CANNOT be A or B.
766 ********************************************************************/
767 #if defined(BI_USE_MULTIPLY)
768 void BigIntMultiply(BIGINT *a, BIGINT *b, BIGINT *res)
769 {
770 // Clear out the result
771 BigIntZero(res);
772  
773 // Load the start and stop pointers
774 _iA = a->ptrLSB;
775 _xA = BigIntMSB(a);
776 _iB = b->ptrLSB;
777 _xB = BigIntMSB(b);
778 _iR = res->ptrLSB;
779  
780 // Perform the multiplication
781 mulBI();
782  
783 // Invalidate the MSB ptr
784 res->bMSBValid = 0;
785 }
786 #endif
787  
788 #if defined(__18CXX) && defined(BI_USE_MULTIPLY_ROM)
789 void BigIntMultiplyROM(BIGINT *a, BIGINT_ROM *b, BIGINT *res)
790 {
791 //clear out the result
792 BigIntZero(res);
793  
794 // Load the start and stop pointers
795 _iA = a->ptrLSB;
796 _xA = BigIntMSB(a);
797 _iBr = b->ptrLSB;
798 _xBr = b->ptrMSB;
799 _iR = res->ptrLSB;
800  
801 // Perform the multiplication
802 mulBIROM();
803  
804 // Invalidate the MSB ptr
805 res->bMSBValid = 0;
806 }
807 #endif
808  
809 /*********************************************************************
810 * Function: void BigIntSquare(const BIGINT *a, BIGINT *res)
811 *
812 * PreCondition: res->size >= 2 * a->size, &res != &a
813 *
814 * Input: *a: a pointer to the number
815 * *res: a pointer to memory to store the result
816 *
817 * Output: *res contains the result of a * a
818 *
819 * Side Effects: None
820 *
821 * Overview: Call BigIntSquare() to square two really big numbers.
822 *
823 * Note: Supports at least 2048 result bits.
824 * Functionally equivalent to BigIntMultiply, except
825 * an optimization is made for the case of square that
826 * allows us to skip ~1/2 the iterations.
827 * res CANNOT be A.
828 ********************************************************************/
829 #if defined(BI_USE_SQUARE)
830 void BigIntSquare(BIGINT *a, BIGINT *res)
831 {
832 BigIntZero(res);
833 _iA = a->ptrLSB;
834 _xA = BigIntMSB(a);
835 _iR = res->ptrLSB;
836 sqrBI();
837  
838 // Invalidate the MSB ptr
839 res->bMSBValid = 0;
840 }
841 #endif
842  
843 /*********************************************************************
844 * Function: void BigIntAdd(BIGINT *a, const BIGINT *b)
845 *
846 * PreCondition: a->ptrMSBMax - a->ptrLSB must be >= b->ptrMSB - b->ptrLSB
847 *
848 * Input: *a: a pointer to the first number
849 * *b: a pointer to the second number
850 *
851 * Output: a = a + b
852 *
853 * Side Effects: None
854 *
855 * Overview: Call BigIntAdd() to add two really big numbers
856 *
857 * Note: Supports at least 2048 result bits.
858 ********************************************************************/
859 #if defined(BI_USE_ADD)
860 void BigIntAdd(BIGINT *a, BIGINT *b)
861 {
862 _iA = a->ptrLSB;
863 _xA = a->ptrMSBMax;
864 _iB = b->ptrLSB;
865 _xB = BigIntMSB(b);
866 addBI();
867  
868 // Invalidate MSB pointer
869 a->bMSBValid = 0;
870 }
871 #endif
872  
873 #if defined(__18CXX) && defined(BI_USE_ADD_ROM)
874 // Note: This function is not required by either RSA operation
875 void BigIntAddROM(BIGINT *a, BIGINT_ROM *b)
876 {
877 _iA = a->ptrLSB;
878 _xA = a->ptrMSBMax;
879 _iBr = b->ptrLSB;
880 _xBr = b->ptrMSB;
881 addBIROM();
882  
883 //invalidate MSB pointer
884 a->bMSBValid = 0;
885 }
886 #endif
887  
888 /*********************************************************************
889 * Function: void BigIntSubtract(BIGINT *a, const BIGINT *b)
890 *
891 * PreCondition: a->ptrMSBMax - a->ptrLSB must be >= b->ptrMSB - b->ptrLSB
892 *
893 * Input: *a: a pointer to the first number
894 * *b: a pointer to the second number
895 *
896 * Output: a = a - b
897 *
898 * Side Effects: None
899 *
900 * Overview: Call BigIntSubtract() to subtract two really big numbers
901 *
902 * Note: Supports at least 2048 result bits.
903 ********************************************************************/
904 #if defined(BI_USE_SUBTRACT)
905 void BigIntSubtract(BIGINT *a, BIGINT *b)
906 {
907 _iA = a->ptrLSB;
908 _xA = a->ptrMSBMax;
909 _iB = b->ptrLSB;
910 _xB = BigIntMSB(b);
911 subBI();
912  
913 // Invalidate MSB pointer
914 a->bMSBValid = 0;
915 }
916 #endif
917  
918 #if defined(__18CXX) && defined(BI_USE_SUBTRACT_ROM)
919 // Note: This function is not required by either RSA operation
920 void BigIntSubtractROM(BIGINT *a, BIGINT_ROM *b)
921 {
922 _iA = a->ptrLSB;
923 _xA = a->ptrMSBMax;
924 _iBr = b->ptrLSB;
925 _xBr = b->ptrMSB;
926 subBIROM();
927  
928 //invalidate MSB pointer
929 a->bMSBValid = 0;
930 }
931 #endif
932  
933 /*********************************************************************
934 * Function: void BigIntCopy(BIGINT *a, const BIGINT *b)
935 *
936 * PreCondition: None
937 *
938 * Input: *a: a pointer to a BIGINT to copy into
939 * *b: a pointer to the data
940 *
941 * Output: a = b
942 *
943 * Side Effects: None
944 *
945 * Overview: Call BigIntCopy() copy one BIGINT to another
946 *
947 * Note: Supports at least 2048 bits. Only data is copied, so
948 * if sizeof(b) > sizeof(a), only the least significant
949 * sizeof(a) bytes are copied.
950 ********************************************************************/
951 #if defined(BI_USE_COPY)
952 void BigIntCopy(BIGINT *a, BIGINT *b)
953 {
954 _iA = a->ptrLSB;
955 _xA = a->ptrMSBMax;
956 _iB = b->ptrLSB;
957 _xB = b->ptrMSBMax;
958 copyBI();
959  
960 // Invalidate MSB pointer
961 a->bMSBValid = 0;
962 }
963 #endif
964  
965 #if defined(__18CXX) && defined(BI_USE_COPY_ROM)
966 void BigIntCopyROM(BIGINT *a, BIGINT_ROM *b)
967 {
968 BIGINT_DATA_TYPE *pa;
969 ROM BIGINT_DATA_TYPE *pb;
970  
971 for(pa = a->ptrLSB, pb = b->ptrLSB; (pa <= a->ptrMSBMax) && (pb <= b->ptrMSB); pa++, pb++)
972 *pa = *pb;
973  
974 // Zero fill remainder
975 while(pa <= a->ptrMSBMax)
976 {
977 *pa = 0;
978 pa++;
979 }
980  
981 // Invalidate MSB pointer
982 a->bMSBValid = 0;
983 }
984 #endif //#if defined(__18CXX)
985  
986 /*********************************************************************
987 * Function: void BigIntSwapEndianness(BIGINT *a)
988 *
989 * PreCondition: None
990 *
991 * Input: *a: a pointer to the BigInt
992 *
993 * Output: *a: same value, with endianness swapped
994 *
995 * Side Effects: None
996 *
997 * Overview: Converts a big-endian data array to little-endian,
998 * or a little-endian data array to big-endian.
999 *
1000 * Note: None
1001 ********************************************************************/
1002 void BigIntSwapEndianness(BIGINT *a)
1003 {
1004 BYTE temp, *front, *end;
1005  
1006 // Set up the pointers
1007 front = (BYTE*)a->ptrLSB;
1008 end = (BYTE*)a->ptrMSBMax + (sizeof(BIGINT_DATA_TYPE) - 1);
1009  
1010 // Swap all data elements
1011 while(front < end)
1012 {
1013 temp = *front;
1014 *front = *end;
1015 *end = temp;
1016 front++;
1017 end--;
1018 }
1019  
1020 }
1021  
1022 #endif // #if (defined(STACK_USE_SSL_SERVER) || defined(STACK_USE_SSL_CLIENT)) && !defined(ENC100_INTERFACE_MODE)
{BLAME END}
{FOOTER START}

Powered by WebSVN v2.8.3