1
/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
3
File: octapi_largmath.h
5
Copyright (c) 2001-2006 Octasic Inc.
9
Library used to perform arithmetic on integer values of an integer multiple
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.
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
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.
26
$Octasic_Release: OCT612xAPI-01.00-PR43 $
28
$Octasic_Revision: 10 $
30
\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
31
#include "apilib/octapi_largmath.h"
34
/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
37
| Function: OctApiLmAdd.
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.
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).
54
\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
56
UINT32 OctApiLmAdd(UINT32 * a,USHORT alen,UINT32 * b,USHORT blen,UINT32 * z, USHORT zlen)
64
/* Check for array lengths.*/
65
if (alen > zlen || blen > zlen) return(OCTAPI_LM_ARRAY_SIZE_MISMATCH);
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;
73
/* Calculate carry for next time.*/
75
if (temp < aprim) carry = 1; else carry = 0;
77
if (temp <= aprim) carry = 1; else carry = 0;
83
/* Check for overflow.*/
84
if (carry == 1) return(OCTAPI_LM_OVERFLOW);
91
/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
94
| Function: OctApiLmSubtract.
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.
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
113
\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
114
#if !SKIP_OctApiLmSubtract
115
UINT32 OctApiLmSubtract(UINT32 * a,USHORT alen,UINT32 * bneg,USHORT blen,UINT32 * z,USHORT zlen,USHORT * neg)
123
/* Check for array lengths.*/
124
if (alen > zlen || blen > zlen) return(OCTAPI_LM_ARRAY_SIZE_MISMATCH);
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;
132
/* Calculate carry for next time.*/
134
if (temp < aprim) carry = 1; else carry = 0;
136
if (temp <= aprim) carry = 1; else carry = 0;
138
/* Write new value.*/
142
/* Check for overflow, which means negative number!*/
145
/* Number is not of right neg. Invert and add one to correct neg.*/
150
OctApiLmAdd(&temp,0,z,zlen,z,zlen);
156
/* Result is positive.*/
162
/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
165
| Function: OctApiLmCompare.
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
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.
179
\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
180
#if !SKIP_OctApiLmCompare
181
UINT32 OctApiLmCompare(UINT32 * a,USHORT alen,UINT32 * bneg,USHORT blen,USHORT * neg)
190
/* Set zlen to alen or blen (which ever is longer)*/
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;
202
/* Calculate carry for next time.*/
204
if (temp < aprim) carry = 1; else carry = 0;
206
if (temp <= aprim) carry = 1; else carry = 0;
209
/* Check for overflow, which means negative number!*/
216
/* Result is positive.*/
222
/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
225
| Function: OctApiLmSubtract.
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.
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.
240
\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
241
#if !SKIP_OctApiLmMultiply
242
UINT32 OctApiLmMultiply(UINT32 * a,UINT32 * b,USHORT ablen,UINT32 * z)
250
USHORT indentw,indentl;
253
/* Caculate number of shorts in a and b.*/
254
nos = (USHORT)((ablen+1) * 2);
256
/* Clear answer word.*/
261
USHORT optimizea, optimizeb;
265
for(l = 1; l < ablen+1; l++)
272
if(*a > OCTAPI_LM_MAX_OPTIMIZE_MUL)
274
if(*b > OCTAPI_LM_MAX_OPTIMIZE_MUL)
277
if(optimizea == TRUE)
279
for(l = 0; l < *a; l++)
280
OctApiLmAdd(z, (USHORT)(nos-1), b, ablen, z, (USHORT)(nos-1));
284
if(optimizeb == TRUE)
286
for(l = 0; l < *b; l++)
287
OctApiLmAdd(z, (USHORT)(nos-1), a, ablen, z, (USHORT)(nos-1));
294
longnumi = (USHORT)( i/2 );
295
/* One iteration per short in a.*/
297
lownum = *(a+longnumi) & 0xFFFF; /* Even word. Lower part of long.*/
299
lownum = *(a+longnumi)>>16; /* Odd word. Upper part of long.*/
305
longnumj = (USHORT)( j/2 );
306
/* One iteration per short in a.*/
308
highnum = *(b+longnumj) & 0xFFFF; /* Even word. Lower part of long.*/
310
highnum = *(b+longnumj)>>16; /* Odd word. Upper part of long.*/
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 );
316
/* Multiply both numbers.*/
317
product = highnum * lownum;
319
/* After multiplying both numbers, add result to end result.*/
320
if ((indentw % 2) == 0) /* Even word boundary, addition in one shot!*/
326
for(k=indentl;k<nos;k++)
328
if (k==indentl) addme = product; else addme = 0;
330
temp = *(z+k) + addme + carry;
332
/* Calculate carry for next time.*/
334
if (temp < addme) carry = 1; else carry = 0;
336
if (temp <= addme) carry = 1; else carry = 0;
342
/* Carry should always be 0.*/
343
if (carry == 1) return(GENERIC_ERROR);
345
else /* Odd word boundary, addition in two shots.*/
351
for(k=indentl;k<nos;k++)
353
if (k==indentl) addme = product<<16;
354
else if (k==(indentl+1)) addme = product>>16;
357
temp = *(z+k) + addme + carry;
359
/* Calculate carry for next time.*/
361
if (temp < addme) carry = 1; else carry = 0;
363
if (temp <= addme) carry = 1; else carry = 0;
369
/* Carry should always be 0.*/
370
if (carry == 1) return(GENERIC_ERROR);
380
/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
383
| Function: OctApiLmDivide.
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
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.
399
\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
400
#if !SKIP_OctApiLmDivide
401
UINT32 OctApiLmDivide(UINT32 * n,UINT32 * d,UINT32 * q,UINT32 * r,USHORT ndqrlen)
403
/* Proceedure for division:*/
406
/* shift = initial_denominator_shift (for upper '1's to be in same bit position).*/
412
/* write a '1' to bit "shift" of array q.*/
414
/* if shift == 0 then*/
419
/* goto "Start loop:"*/
424
USHORT shift,n_msb,d_msb;
426
USHORT ConditionFlag = TRUE;
429
for(i=0;i<=ndqrlen;i++)
433
for(i=0;i<=ndqrlen;i++)
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);
440
result = OctApiLmGetMsb(n,ndqrlen,&n_msb);
441
if (result != GENERIC_OK) return(result);
443
if (d_msb == 0xFFFF) /* Division by 0.*/
444
return(OCTAPI_LM_DIVISION_BY_ZERO);
446
if (n_msb == 0xFFFF) /* 0/n, returns 0 R 0.*/
449
if (n_msb < d_msb) /* x/y, where x is smaller than y, returns 0 R x.*/
452
shift = (USHORT)( n_msb - d_msb );
454
/* Shift d to match n highest bit position.*/
455
result = OctApiLmShiftn(d,ndqrlen,TRUE,shift);
456
if (result != GENERIC_OK) return(result);
459
while( ConditionFlag == TRUE )
462
result = OctApiLmCompare(r,ndqrlen,d,ndqrlen,&neg);
463
if (result != GENERIC_OK) return(result);
465
if (neg == FALSE) /* Subtraction can be done(do it).*/
468
result = OctApiLmSubtract(r,ndqrlen,d,ndqrlen,r,ndqrlen,&neg);
469
if (result != GENERIC_OK) return(result);
471
/* write a '1' to bit "shift" of array q.*/
472
*(q+(shift/32)) |= (UINT32)0x1 << (shift%32);
475
/* if shift == 0 then*/
477
if (shift == 0) return(GENERIC_OK);
481
/* goto "Start loop:"*/
483
OctApiLmShiftRight1(d,ndqrlen);
491
/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
494
| Function: octapi_lm_shifright1.
496
| Description: The function is for internal use only.
498
| -----------------------------------------------------------------------
499
| | Variable | Type | Description
500
| -----------------------------------------------------------------------
503
\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
504
#if !SKIP_OctApiLmShiftRight1
505
UINT32 OctApiLmShiftRight1(UINT32 * a,USHORT alen)
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*/
516
*(a+i)>>=1; /* Shift long by one to the right.*/
517
*(a+i)|=*(a+i+1)<<31;
519
*(a+alen)>>=1; /* Shift last long, leaving it's highest bit at 0.*/
525
/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
528
| Function: OctApiLmShiftn.
530
| Description: The function is for internal use only.
532
| -----------------------------------------------------------------------
533
| | Variable | Type | Description
534
| -----------------------------------------------------------------------
537
\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
538
#if !SKIP_OctApiLmShiftn
539
UINT32 OctApiLmShiftn(UINT32 * a,USHORT alen,USHORT shiftleft,USHORT shiftn)
545
long_offset = (USHORT)( shiftn / 32 );
546
bit_offset = (USHORT)( shiftn % 32 );
548
if (shiftleft == TRUE) /* Shift left.*/
550
for(i=alen;i<=alen;i--)
552
/* Fill upper bits of long.*/
553
if (i >= long_offset)
554
*(a+i) = *(a+i-long_offset) << bit_offset;
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);
563
else /* Shift right.*/
567
/* Fill lower bits of long.*/
568
if ((alen-i) >= long_offset)
569
*(a+i) = *(a+i+long_offset) >> bit_offset;
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);
585
/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
588
| Function: OctApiLmGetMsb.
590
| Description: The function is for internal use only.
592
| -----------------------------------------------------------------------
593
| | Variable | Type | Description
594
| -----------------------------------------------------------------------
597
\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
598
#if !SKIP_OctApiLmGetMsb
599
UINT32 OctApiLmGetMsb(UINT32 * a,USHORT alen,USHORT * msb_pos)
604
for(i=alen;i<=alen;i--)
606
if (*(a+i) == 0) continue;
611
/* Test for bit being '1'.*/
612
if ((x & 0x80000000) != 0)
614
*msb_pos=(USHORT)(j+(32*i));
618
/* Shift bit one bit position, and try again.*/