Debian Codegraph @

xpp/oct612x/apilib/largmath/octapi_largmath.c

raw
1 /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
2
3 File: octapi_largmath.h
4
5 Copyright (c) 2001-2007 Octasic Inc.
6
7 Description:
8
9 Library used to perform arithmetic on integer values of an integer multiple
10 of 32-bits.
11
12 This file is part of the Octasic OCT6100 GPL API . The OCT6100 GPL API is
13 free software; you can redistribute it and/or modify it under the terms of
14 the GNU General Public License as published by the Free Software Foundation;
15 either version 2 of the License, or (at your option) any later version.
16
17 The OCT6100 GPL API is distributed in the hope that it will be useful, but
18 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
19 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with the OCT6100 GPL API; if not, write to the Free Software
24 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
25
26 $Octasic_Release: OCT612xAPI-01.00-PR49 $
27
28 $Octasic_Revision: 10 $
29
30 \*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
31 #include "apilib/octapi_largmath.h"
32
33
34 /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
35 | API UTILITIES
36 |
37 | Function: OctApiLmAdd.
38 |
39 | Description: This function adds 2 numbers, a and b. Number a is
40 | (alen + 1) * 32 bits long; b is (blen + 1) * 32 bits long. The
41 | result is (zlen + 1) * 32 bits long. It the function succeeds it returns
42 | GENERIC_OK, else GENERIC_ERROR.
43 |
44 | -----------------------------------------------------------------------
45 | | Variable | Type | Description
46 | -----------------------------------------------------------------------
47 | *a UINT32 The array containing the first number.
48 | alen USHORT The length of array a, minus 1 (0 - 99).
49 | *b UINT32 The array containing the second number.
50 | blen USHORT The length of array b, minus 1 (0 - 99).
51 | *z UINT32 The array containing the resulting number.
52 | zlen USHORT The length of array z, minus 1 (0 - 99).
53 |
54 \*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
55 #if !SKIP_OctApiLmAdd
56 UINT32 OctApiLmAdd(UINT32 * a,USHORT alen,UINT32 * b,USHORT blen,UINT32 * z, USHORT zlen)
57 {
58 USHORT i;
59 UINT32 temp;
60 UINT32 carry=0;
61 UINT32 aprim;
62 UINT32 bprim;
63
64 /* Check for array lengths.*/
65 if (alen > zlen || blen > zlen) return(OCTAPI_LM_ARRAY_SIZE_MISMATCH);
66
67 for(i=0;i<=zlen;i++)
68 {
69 if (i <= alen) aprim = *(a+i); else aprim = 0;
70 if (i <= blen) bprim = *(b+i); else bprim = 0;
71 temp = aprim + bprim + carry;
72
73 /* Calculate carry for next time.*/
74 if (carry == 0)
75 if (temp < aprim) carry = 1; else carry = 0;
76 else
77 if (temp <= aprim) carry = 1; else carry = 0;
78
79 /* Write new value.*/
80 *(z+i) = temp;
81 }
82
83 /* Check for overflow.*/
84 if (carry == 1) return(OCTAPI_LM_OVERFLOW);
85
86 /* All is well.*/
87 return(GENERIC_OK);
88 }
89 #endif
90
91 /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
92 | API UTILITIES
93 |
94 | Function: OctApiLmSubtract.
95 |
96 | Description: This function subtracts 2 numbers, a and b. Number a is
97 | (alen + 1) * 32 bits long; b is (blen + 1) * 32 bits long. The result
98 | is (zlen + 1) * 32 bits long. It the function succeeds it returns
99 | GENERIC_OK, else GENERIC_ERROR.
100 |
101 | -----------------------------------------------------------------------
102 | | Variable | Type | Description
103 | -----------------------------------------------------------------------
104 | *a UINT32 The array containing the first number.
105 | alen USHORT The length of array a, minus 1 (0 - 99).
106 | *bneg UINT32 The array containing the second number.
107 | blen USHORT The length of array b, minus 1 (0 - 99).
108 | *z UINT32 The array containing the resulting number.
109 | zlen USHORT The length of array z, minus 1 (0 - 99).
110 | *neg USHORT Indicates if the result is negative
111 | (TRUE/FALSE).
112 |
113 \*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
114 #if !SKIP_OctApiLmSubtract
115 UINT32 OctApiLmSubtract(UINT32 * a,USHORT alen,UINT32 * bneg,USHORT blen,UINT32 * z,USHORT zlen,USHORT * neg)
116 {
117 USHORT i;
118 UINT32 temp;
119 UINT32 carry=1;
120 UINT32 aprim;
121 UINT32 bprim;
122
123 /* Check for array lengths.*/
124 if (alen > zlen || blen > zlen) return(OCTAPI_LM_ARRAY_SIZE_MISMATCH);
125
126 for(i=0;i<=zlen;i++)
127 {
128 if (i <= alen) aprim = *(a+i); else aprim = 0;
129 if (i <= blen) bprim = ~(*(bneg+i)); else bprim = 0xFFFFFFFF;
130 temp = aprim + bprim + carry;
131
132 /* Calculate carry for next time.*/
133 if (carry == 0)
134 if (temp < aprim) carry = 1; else carry = 0;
135 else
136 if (temp <= aprim) carry = 1; else carry = 0;
137
138 /* Write new value.*/
139 *(z+i) = temp;
140 }
141
142 /* Check for overflow, which means negative number!*/
143 if (carry == 0)
144 {
145 /* Number is not of right neg. Invert and add one to correct neg.*/
146 for(i=0;i<=zlen;i++)
147 *(z+i) = ~(*(z+i));
148
149 temp = 1;
150 OctApiLmAdd(&temp,0,z,zlen,z,zlen);
151
152 *neg = TRUE;
153 return(GENERIC_OK);
154 }
155
156 /* Result is positive.*/
157 *neg = FALSE;
158 return(GENERIC_OK);
159 }
160 #endif
161
162 /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
163 | API UTILITIES
164 |
165 | Function: OctApiLmCompare.
166 |
167 | Description: This function compares two numbers (arrays) of equal lengths.
168 | Number a is (alen + 1) * 32 bits long; b is (blen + 1) * 32 bits long. The result
169 |
170 | -----------------------------------------------------------------------
171 | | Variable | Type | Description
172 | -----------------------------------------------------------------------
173 | *a UINT32 The array containing the first number.
174 | alen USHORT The length of array a, minus 1 (0 - 99).
175 | *b UINT32 The array containing the second number.
176 | blen USHORT The length of array b, minus 1 (0 - 99).
177 | *neg USHORT Result of compare.
178 |
179 \*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
180 #if !SKIP_OctApiLmCompare
181 UINT32 OctApiLmCompare(UINT32 * a,USHORT alen,UINT32 * bneg,USHORT blen,USHORT * neg)
182 {
183 USHORT i;
184 UINT32 temp;
185 UINT32 carry=1;
186 UINT32 aprim;
187 UINT32 bprim;
188 UINT32 zlen;
189
190 /* Set zlen to alen or blen (which ever is longer)*/
191 if (alen < blen)
192 zlen = blen;
193 else
194 zlen = alen;
195
196 for(i=0;i<=zlen;i++)
197 {
198 if (i <= alen) aprim = *(a+i); else aprim = 0;
199 if (i <= blen) bprim = ~(*(bneg+i)); else bprim = 0xFFFFFFFF;
200 temp = aprim + bprim + carry;
201
202 /* Calculate carry for next time.*/
203 if (carry == 0)
204 if (temp < aprim) carry = 1; else carry = 0;
205 else
206 if (temp <= aprim) carry = 1; else carry = 0;
207 }
208
209 /* Check for overflow, which means negative number!*/
210 if (carry == 0)
211 {
212 *neg = TRUE;
213 return(GENERIC_OK);
214 }
215
216 /* Result is positive.*/
217 *neg = FALSE;
218 return(GENERIC_OK);
219 }
220 #endif
221
222 /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
223 | API UTILITIES
224 |
225 | Function: OctApiLmSubtract.
226 |
227 | Description: This function multiplies 2 numbers, a and b. Number a and
228 | b are both (ablen + 1) * 32 bits long. The result is twice as
229 | long. If the functions succeeds if returns GENERIC_OK,
230 | else GENERIC_ERROR.
231 |
232 | -----------------------------------------------------------------------
233 | | Variable | Type | Description
234 | -----------------------------------------------------------------------
235 | *a UINT32 The array containing the first number.
236 | *b UINT32 The array containing the second number.
237 | ablen USHORT The length of arrays a and b, minus 1 (0 - 99).
238 | *z UINT32 The array containing the resulting number.
239 |
240 \*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
241 #if !SKIP_OctApiLmMultiply
242 UINT32 OctApiLmMultiply(UINT32 * a,UINT32 * b,USHORT ablen,UINT32 * z)
243 {
244 USHORT i,j,k;
245 USHORT nos;
246 UINT32 lownum;
247 UINT32 highnum;
248 USHORT longnumi;
249 USHORT longnumj;
250 USHORT indentw,indentl;
251
252
253 /* Caculate number of shorts in a and b.*/
254 nos = (USHORT)((ablen+1) * 2);
255
256 /* Clear answer word.*/
257 for(i=0;i<nos;i++)
258 *(z+i) = 0;
259
260 {
261 USHORT optimizea, optimizeb;
262 USHORT l;
263 optimizea = TRUE;
264 optimizeb = TRUE;
265 for(l = 1; l < ablen+1; l++)
266 {
267 if(*(a+l) != 0)
268 optimizea = FALSE;
269 if(*(b+l) != 0)
270 optimizeb = FALSE;
271 }
272 if(*a > OCTAPI_LM_MAX_OPTIMIZE_MUL)
273 optimizea = FALSE;
274 if(*b > OCTAPI_LM_MAX_OPTIMIZE_MUL)
275 optimizeb = FALSE;
276
277 if(optimizea == TRUE)
278 {
279 for(l = 0; l < *a; l++)
280 OctApiLmAdd(z, (USHORT)(nos-1), b, ablen, z, (USHORT)(nos-1));
281 return(GENERIC_OK);
282 }
283
284 if(optimizeb == TRUE)
285 {
286 for(l = 0; l < *b; l++)
287 OctApiLmAdd(z, (USHORT)(nos-1), a, ablen, z, (USHORT)(nos-1));
288 return(GENERIC_OK);
289 }
290 }
291
292 for(i=0;i<nos;i++)
293 {
294 longnumi = (USHORT)( i/2 );
295 /* One iteration per short in a.*/
296 if ((i%2) == 0)
297 lownum = *(a+longnumi) & 0xFFFF; /* Even word. Lower part of long.*/
298 else
299 lownum = *(a+longnumi)>>16; /* Odd word. Upper part of long.*/
300
301 for(j=0;j<nos;j++)
302 {
303 UINT32 product;
304
305 longnumj = (USHORT)( j/2 );
306 /* One iteration per short in a.*/
307 if ((j%2) == 0)
308 highnum = *(b+longnumj) & 0xFFFF; /* Even word. Lower part of long.*/
309 else
310 highnum = *(b+longnumj)>>16; /* Odd word. Upper part of long.*/
311
312 /* Find the word indent of the answer. 0 = no indent. 1 = one word indent.*/
313 indentw = (USHORT)( j+i );
314 indentl = (USHORT)( indentw / 2 );
315
316 /* Multiply both numbers.*/
317 product = highnum * lownum;
318
319 /* After multiplying both numbers, add result to end result.*/
320 if ((indentw % 2) == 0) /* Even word boundary, addition in one shot!*/
321 {
322 UINT32 carry=0;
323 UINT32 temp;
324 UINT32 addme;
325
326 for(k=indentl;k<nos;k++)
327 {
328 if (k==indentl) addme = product; else addme = 0;
329
330 temp = *(z+k) + addme + carry;
331
332 /* Calculate carry for next time.*/
333 if (carry == 0)
334 if (temp < addme) carry = 1; else carry = 0;
335 else
336 if (temp <= addme) carry = 1; else carry = 0;
337
338 /* Set value.*/
339 *(z+k) = temp;
340 }
341
342 /* Carry should always be 0.*/
343 if (carry == 1) return(GENERIC_ERROR);
344 }
345 else /* Odd word boundary, addition in two shots.*/
346 {
347 UINT32 carry=0;
348 UINT32 temp;
349 UINT32 addme;
350
351 for(k=indentl;k<nos;k++)
352 {
353 if (k==indentl) addme = product<<16;
354 else if (k==(indentl+1)) addme = product>>16;
355 else addme = 0;
356
357 temp = *(z+k) + addme + carry;
358
359 /* Calculate carry for next time.*/
360 if (carry == 0)
361 if (temp < addme) carry = 1; else carry = 0;
362 else
363 if (temp <= addme) carry = 1; else carry = 0;
364
365 /* Set value.*/
366 *(z+k) = temp;
367 }
368
369 /* Carry should always be 0.*/
370 if (carry == 1) return(GENERIC_ERROR);
371 }
372 }
373 }
374
375 return(GENERIC_OK);
376 }
377 #endif
378
379
380 /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
381 | API UTILITIES
382 |
383 | Function: OctApiLmDivide.
384 |
385 | Description: This function divides the number n by the number d. The
386 | quotient is placed in q and the remainder in r. The arrays
387 | n, d, q and r are all of the same length, namely (ndqrlen + 1).
388 | If the functions succeeds if returns GENERIC_OK, else
389 | GENERIC_ERROR.
390 |
391 | -----------------------------------------------------------------------
392 | | Variable | Type | Description
393 | -----------------------------------------------------------------------
394 | *a UINT32 The array containing the first number.
395 | *b UINT32 The array containing the second number.
396 | ablen USHORT The length of arrays a and b, minus 1 (0 - 99).
397 | *z UINT32 The array containing the resulting number.
398 |
399 \*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
400 #if !SKIP_OctApiLmDivide
401 UINT32 OctApiLmDivide(UINT32 * n,UINT32 * d,UINT32 * q,UINT32 * r,USHORT ndqrlen)
402 {
403 /* Proceedure for division:*/
404 /* r = n*/
405 /* q = 0*/
406 /* shift = initial_denominator_shift (for upper '1's to be in same bit position).*/
407 /* d <<= shift;*/
408 /* Start loop:*/
409 /* compare r and d*/
410 /* if r > d then*/
411 /* r -= d;*/
412 /* write a '1' to bit "shift" of array q.*/
413 /* end if;*/
414 /* if shift == 0 then*/
415 /* return;*/
416 /* else*/
417 /* shift--;*/
418 /* d>>=1;*/
419 /* goto "Start loop:"*/
420 /* end if;*/
421
422 UINT32 i;
423 UINT32 result;
424 USHORT shift,n_msb,d_msb;
425 USHORT neg;
426 USHORT ConditionFlag = TRUE;
427
428 /* r = n*/
429 for(i=0;i<=ndqrlen;i++)
430 *(r+i) = *(n+i);
431
432 /* q = 0*/
433 for(i=0;i<=ndqrlen;i++)
434 *(q+i) = 0;
435
436 /* shift = initial_denominator_shift (for upper '1's to be in same bit position).*/
437 result = OctApiLmGetMsb(d,ndqrlen,&d_msb);
438 if (result != GENERIC_OK) return(result);
439
440 result = OctApiLmGetMsb(n,ndqrlen,&n_msb);
441 if (result != GENERIC_OK) return(result);
442
443 if (d_msb == 0xFFFF) /* Division by 0.*/
444 return(OCTAPI_LM_DIVISION_BY_ZERO);
445
446 if (n_msb == 0xFFFF) /* 0/n, returns 0 R 0.*/
447 return(GENERIC_OK);
448
449 if (n_msb < d_msb) /* x/y, where x is smaller than y, returns 0 R x.*/
450 return(GENERIC_OK);
451
452 shift = (USHORT)( n_msb - d_msb );
453
454 /* Shift d to match n highest bit position.*/
455 result = OctApiLmShiftn(d,ndqrlen,TRUE,shift);
456 if (result != GENERIC_OK) return(result);
457
458 /* Start loop:*/
459 while( ConditionFlag == TRUE )
460 {
461 /* compare r and d*/
462 result = OctApiLmCompare(r,ndqrlen,d,ndqrlen,&neg);
463 if (result != GENERIC_OK) return(result);
464
465 if (neg == FALSE) /* Subtraction can be done(do it).*/
466 {
467 /* r -= d;*/
468 result = OctApiLmSubtract(r,ndqrlen,d,ndqrlen,r,ndqrlen,&neg);
469 if (result != GENERIC_OK) return(result);
470
471 /* write a '1' to bit "shift" of array q.*/
472 *(q+(shift/32)) |= (UINT32)0x1 << (shift%32);
473 }
474
475 /* if shift == 0 then*/
476 /* return;*/
477 if (shift == 0) return(GENERIC_OK);
478
479 /* shift--;*/
480 /* d>>=1;*/
481 /* goto "Start loop:"*/
482 shift--;
483 OctApiLmShiftRight1(d,ndqrlen);
484 }
485
486 return(GENERIC_OK);
487 }
488 #endif
489
490
491 /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
492 | API UTILITIES
493 |
494 | Function: octapi_lm_shifright1.
495 |
496 | Description: The function is for internal use only.
497 |
498 | -----------------------------------------------------------------------
499 | | Variable | Type | Description
500 | -----------------------------------------------------------------------
501 | N/A.
502 |
503 \*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
504 #if !SKIP_OctApiLmShiftRight1
505 UINT32 OctApiLmShiftRight1(UINT32 * a,USHORT alen)
506 {
507 UINT32 i;
508
509 /* Start with lower long and move up by one long each time,*/
510 /* shifting each long to the right by one bit. The upper bit*/
511 /* of the next long will have to be concatenated each time a*/
512 /* loop is executed. For the last long, leave the highest bit*/
513 /* intact.*/
514 for(i=0;i<alen;i++)
515 {
516 *(a+i)>>=1; /* Shift long by one to the right.*/
517 *(a+i)|=*(a+i+1)<<31;
518 }
519 *(a+alen)>>=1; /* Shift last long, leaving it's highest bit at 0.*/
520
521 return(GENERIC_OK);
522 }
523 #endif
524
525 /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
526 | API UTILITIES
527 |
528 | Function: OctApiLmShiftn.
529 |
530 | Description: The function is for internal use only.
531 |
532 | -----------------------------------------------------------------------
533 | | Variable | Type | Description
534 | -----------------------------------------------------------------------
535 | N/A.
536 |
537 \*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
538 #if !SKIP_OctApiLmShiftn
539 UINT32 OctApiLmShiftn(UINT32 * a,USHORT alen,USHORT shiftleft,USHORT shiftn)
540 {
541 UINT32 i;
542 USHORT long_offset;
543 USHORT bit_offset;
544
545 long_offset = (USHORT)( shiftn / 32 );
546 bit_offset = (USHORT)( shiftn % 32 );
547
548 if (shiftleft == TRUE) /* Shift left.*/
549 {
550 for(i=alen;i<=alen;i--)
551 {
552 /* Fill upper bits of long.*/
553 if (i >= long_offset)
554 *(a+i) = *(a+i-long_offset) << bit_offset;
555 else
556 *(a+i) = 0;
557
558 /* Fill lower bits of long.*/
559 if (i > long_offset && bit_offset != 0)
560 *(a+i) |= *(a+i-long_offset-1) >> (32-bit_offset);
561 }
562 }
563 else /* Shift right.*/
564 {
565 for(i=0;i<=alen;i++)
566 {
567 /* Fill lower bits of long.*/
568 if ((alen-i) >= long_offset)
569 *(a+i) = *(a+i+long_offset) >> bit_offset;
570 else
571 *(a+i) = 0;
572
573 /* Fill upper bits of long.*/
574 if ((alen-i) > long_offset && bit_offset != 0)
575 *(a+i) |= *(a+i+long_offset+1) << (32-bit_offset);
576
577 }
578 }
579
580 return(GENERIC_OK);
581 }
582 #endif
583
584
585 /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
586 | API UTILITIES
587 |
588 | Function: OctApiLmGetMsb.
589 |
590 | Description: The function is for internal use only.
591 |
592 | -----------------------------------------------------------------------
593 | | Variable | Type | Description
594 | -----------------------------------------------------------------------
595 | N/A.
596 |
597 \*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
598 #if !SKIP_OctApiLmGetMsb
599 UINT32 OctApiLmGetMsb(UINT32 * a,USHORT alen,USHORT * msb_pos)
600 {
601 UINT32 i,j;
602 UINT32 x;
603
604 for(i=alen;i<=alen;i--)
605 {
606 if (*(a+i) == 0) continue;
607
608 x = *(a+i);
609 for(j=31;j<=31;j--)
610 {
611 /* Test for bit being '1'.*/
612 if ((x & 0x80000000) != 0)
613 {
614 *msb_pos=(USHORT)(j+(32*i));
615 return(GENERIC_OK);
616 }
617
618 /* Shift bit one bit position, and try again.*/
619 x<<=1;
620 }
621 }
622
623 /* MSB not found.*/
624 *msb_pos = 0xFFFF;
625
626 return(GENERIC_OK);
627 }
628 #endif