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) |
Powered by WebSVN v2.8.3