Return to nn.c CVS log

Up to [PGP] / pgp / rsaref / source

Annotation of pgp/rsaref/source/nn.c, revision 1.1

1.1     ! root        1: /* NN.C - natural numbers routines
        !             2:  */
        !             3: 
        !             4: /* Copyright (C) RSA Laboratories, a division of RSA Data Security,
        !             5:      Inc., created 1991. All rights reserved.
        !             6:  */
        !             7: 
        !             8: /* CHANGES MADE TO THIS FILE UNDER RSAREF 2.0 license clause 1(c):
        !             9: 
        !            10:    For the MIT PGP 2.5 distribution, this file was modified to permit
        !            11:    replacement of the NN_ModExp routine by an equivalent routine contained 
        !            12:    in the PGP 2.5 sources.  To enable this change, an #ifdef was added to this 
        !            13:    file (search for #ifndef USEMPILIB below).  RSAREF *must* be compiled with 
        !            14:    USEMPILIB defined for this change to occur.
        !            15: 
        !            16:    Change made May 8, 1994.  */
        !            17: 
        !            18: #include "global.h"
        !            19: #include "rsaref.h"
        !            20: #include "nn.h"
        !            21: #include "digit.h"
        !            22: 
        !            23: static NN_DIGIT NN_AddDigitMult PROTO_LIST 
        !            24:   ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int));
        !            25: static NN_DIGIT NN_SubDigitMult PROTO_LIST 
        !            26:   ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int));
        !            27: 
        !            28: static unsigned int NN_DigitBits PROTO_LIST ((NN_DIGIT));
        !            29: 
        !            30: /* Decodes character string b into a, where character string is ordered
        !            31:    from most to least significant.
        !            32: 
        !            33:    Lengths: a[digits], b[len].
        !            34:    Assumes b[i] = 0 for i < len - digits * NN_DIGIT_LEN. (Otherwise most
        !            35:    significant bytes are truncated.)
        !            36:  */
        !            37: void NN_Decode (a, digits, b, len)
        !            38: NN_DIGIT *a;
        !            39: unsigned char *b;
        !            40: unsigned int digits, len;
        !            41: {
        !            42:   NN_DIGIT t;
        !            43:   int j;
        !            44:   unsigned int i, u;
        !            45:   
        !            46:   for (i = 0, j = len - 1; i < digits && j >= 0; i++) {
        !            47:     t = 0;
        !            48:     for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
        !            49:       t |= ((NN_DIGIT)b[j]) << u;
        !            50:     a[i] = t;
        !            51:   }
        !            52:   
        !            53:   for (; i < digits; i++)
        !            54:     a[i] = 0;
        !            55: }
        !            56: 
        !            57: /* Encodes b into character string a, where character string is ordered
        !            58:    from most to least significant.
        !            59: 
        !            60:    Lengths: a[len], b[digits].
        !            61:    Assumes NN_Bits (b, digits) <= 8 * len. (Otherwise most significant
        !            62:    digits are truncated.)
        !            63:  */
        !            64: void NN_Encode (a, len, b, digits)
        !            65: NN_DIGIT *b;
        !            66: unsigned char *a;
        !            67: unsigned int digits, len;
        !            68: {
        !            69:   NN_DIGIT t;
        !            70:   int j;
        !            71:   unsigned int i, u;
        !            72: 
        !            73:   for (i = 0, j = len - 1; i < digits && j >= 0; i++) {
        !            74:     t = b[i];
        !            75:     for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
        !            76:       a[j] = (unsigned char)(t >> u);
        !            77:   }
        !            78: 
        !            79:   for (; j >= 0; j--)
        !            80:     a[j] = 0;
        !            81: }
        !            82: 
        !            83: /* Assigns a = b.
        !            84: 
        !            85:    Lengths: a[digits], b[digits].
        !            86:  */
        !            87: void NN_Assign (a, b, digits)
        !            88: NN_DIGIT *a, *b;
        !            89: unsigned int digits;
        !            90: {
        !            91:   unsigned int i;
        !            92: 
        !            93:   for (i = 0; i < digits; i++)
        !            94:     a[i] = b[i];
        !            95: }
        !            96: 
        !            97: /* Assigns a = 0.
        !            98: 
        !            99:    Lengths: a[digits].
        !           100:  */
        !           101: void NN_AssignZero (a, digits)
        !           102: NN_DIGIT *a;
        !           103: unsigned int digits;
        !           104: {
        !           105:   unsigned int i;
        !           106: 
        !           107:   for (i = 0; i < digits; i++)
        !           108:     a[i] = 0;
        !           109: }
        !           110: 
        !           111: /* Assigns a = 2^b.
        !           112: 
        !           113:    Lengths: a[digits].
        !           114:    Requires b < digits * NN_DIGIT_BITS.
        !           115:  */
        !           116: void NN_Assign2Exp (a, b, digits)
        !           117: NN_DIGIT *a;
        !           118: unsigned int b, digits;
        !           119: {
        !           120:   NN_AssignZero (a, digits);
        !           121: 
        !           122:   if (b >= digits * NN_DIGIT_BITS)
        !           123:     return;
        !           124: 
        !           125:   a[b / NN_DIGIT_BITS] = (NN_DIGIT)1 << (b % NN_DIGIT_BITS);
        !           126: }
        !           127: 
        !           128: /* Computes a = b + c. Returns carry.
        !           129: 
        !           130:    Lengths: a[digits], b[digits], c[digits].
        !           131:  */
        !           132: NN_DIGIT NN_Add (a, b, c, digits)
        !           133: NN_DIGIT *a, *b, *c;
        !           134: unsigned int digits;
        !           135: {
        !           136:   NN_DIGIT ai, carry;
        !           137:   unsigned int i;
        !           138: 
        !           139:   carry = 0;
        !           140: 
        !           141:   for (i = 0; i < digits; i++) {
        !           142:     if ((ai = b[i] + carry) < carry)
        !           143:       ai = c[i];
        !           144:     else if ((ai += c[i]) < c[i])
        !           145:       carry = 1;
        !           146:     else
        !           147:       carry = 0;
        !           148:     a[i] = ai;
        !           149:   }
        !           150: 
        !           151:   return (carry);
        !           152: }
        !           153: 
        !           154: /* Computes a = b - c. Returns borrow.
        !           155: 
        !           156:    Lengths: a[digits], b[digits], c[digits].
        !           157:  */
        !           158: NN_DIGIT NN_Sub (a, b, c, digits)
        !           159: NN_DIGIT *a, *b, *c;
        !           160: unsigned int digits;
        !           161: {
        !           162:   NN_DIGIT ai, borrow;
        !           163:   unsigned int i;
        !           164: 
        !           165:   borrow = 0;
        !           166: 
        !           167:   for (i = 0; i < digits; i++) {
        !           168:     if ((ai = b[i] - borrow) > (MAX_NN_DIGIT - borrow))
        !           169:       ai = MAX_NN_DIGIT - c[i];
        !           170:     else if ((ai -= c[i]) > (MAX_NN_DIGIT - c[i]))
        !           171:       borrow = 1;
        !           172:     else
        !           173:       borrow = 0;
        !           174:     a[i] = ai;
        !           175:   }
        !           176: 
        !           177:   return (borrow);
        !           178: }
        !           179: 
        !           180: /* Computes a = b * c.
        !           181: 
        !           182:    Lengths: a[2*digits], b[digits], c[digits].
        !           183:    Assumes digits < MAX_NN_DIGITS.
        !           184:  */
        !           185: void NN_Mult (a, b, c, digits)
        !           186: NN_DIGIT *a, *b, *c;
        !           187: unsigned int digits;
        !           188: {
        !           189:   NN_DIGIT t[2*MAX_NN_DIGITS];
        !           190:   unsigned int bDigits, cDigits, i;
        !           191: 
        !           192:   NN_AssignZero (t, 2 * digits);
        !           193:   
        !           194:   bDigits = NN_Digits (b, digits);
        !           195:   cDigits = NN_Digits (c, digits);
        !           196: 
        !           197:   for (i = 0; i < bDigits; i++)
        !           198:     t[i+cDigits] += NN_AddDigitMult (&t[i], &t[i], b[i], c, cDigits);
        !           199:   
        !           200:   NN_Assign (a, t, 2 * digits);
        !           201:   
        !           202:   /* Zeroize potentially sensitive information.
        !           203:    */
        !           204:   R_memset ((POINTER)t, 0, sizeof (t));
        !           205: }
        !           206: 
        !           207: /* Computes a = b * 2^c (i.e., shifts left c bits), returning carry.
        !           208: 
        !           209:    Lengths: a[digits], b[digits].
        !           210:    Requires c < NN_DIGIT_BITS.
        !           211:  */
        !           212: NN_DIGIT NN_LShift (a, b, c, digits)
        !           213: NN_DIGIT *a, *b;
        !           214: unsigned int c, digits;
        !           215: {
        !           216:   NN_DIGIT bi, carry;
        !           217:   unsigned int i, t;
        !           218:   
        !           219:   if (c >= NN_DIGIT_BITS)
        !           220:     return (0);
        !           221:   
        !           222:   t = NN_DIGIT_BITS - c;
        !           223: 
        !           224:   carry = 0;
        !           225: 
        !           226:   for (i = 0; i < digits; i++) {
        !           227:     bi = b[i];
        !           228:     a[i] = (bi << c) | carry;
        !           229:     carry = c ? (bi >> t) : 0;
        !           230:   }
        !           231:   
        !           232:   return (carry);
        !           233: }
        !           234: 
        !           235: /* Computes a = c div 2^c (i.e., shifts right c bits), returning carry.
        !           236: 
        !           237:    Lengths: a[digits], b[digits].
        !           238:    Requires: c < NN_DIGIT_BITS.
        !           239:  */
        !           240: NN_DIGIT NN_RShift (a, b, c, digits)
        !           241: NN_DIGIT *a, *b;
        !           242: unsigned int c, digits;
        !           243: {
        !           244:   NN_DIGIT bi, carry;
        !           245:   int i;
        !           246:   unsigned int t;
        !           247:   
        !           248:   if (c >= NN_DIGIT_BITS)
        !           249:     return (0);
        !           250:   
        !           251:   t = NN_DIGIT_BITS - c;
        !           252: 
        !           253:   carry = 0;
        !           254: 
        !           255:   for (i = digits - 1; i >= 0; i--) {
        !           256:     bi = b[i];
        !           257:     a[i] = (bi >> c) | carry;
        !           258:     carry = c ? (bi << t) : 0;
        !           259:   }
        !           260:   
        !           261:   return (carry);
        !           262: }
        !           263: 
        !           264: /* Computes a = c div d and b = c mod d.
        !           265: 
        !           266:    Lengths: a[cDigits], b[dDigits], c[cDigits], d[dDigits].
        !           267:    Assumes d > 0, cDigits < 2 * MAX_NN_DIGITS,
        !           268:            dDigits < MAX_NN_DIGITS.
        !           269:  */
        !           270: void NN_Div (a, b, c, cDigits, d, dDigits)
        !           271: NN_DIGIT *a, *b, *c, *d;
        !           272: unsigned int cDigits, dDigits;
        !           273: {
        !           274:   NN_DIGIT ai, cc[2*MAX_NN_DIGITS+1], dd[MAX_NN_DIGITS], t;
        !           275:   int i;
        !           276:   unsigned int ddDigits, shift;
        !           277:   
        !           278:   ddDigits = NN_Digits (d, dDigits);
        !           279:   if (ddDigits == 0)
        !           280:     return;
        !           281:   
        !           282:   /* Normalize operands.
        !           283:    */
        !           284:   shift = NN_DIGIT_BITS - NN_DigitBits (d[ddDigits-1]);
        !           285:   NN_AssignZero (cc, ddDigits);
        !           286:   cc[cDigits] = NN_LShift (cc, c, shift, cDigits);
        !           287:   NN_LShift (dd, d, shift, ddDigits);
        !           288:   t = dd[ddDigits-1];
        !           289:   
        !           290:   NN_AssignZero (a, cDigits);
        !           291: 
        !           292:   for (i = cDigits-ddDigits; i >= 0; i--) {
        !           293:     /* Underestimate quotient digit and subtract.
        !           294:      */
        !           295:     if (t == MAX_NN_DIGIT)
        !           296:       ai = cc[i+ddDigits];
        !           297:     else
        !           298:       NN_DigitDiv (&ai, &cc[i+ddDigits-1], t + 1);
        !           299:     cc[i+ddDigits] -= NN_SubDigitMult (&cc[i], &cc[i], ai, dd, ddDigits);
        !           300: 
        !           301:     /* Correct estimate.
        !           302:      */
        !           303:     while (cc[i+ddDigits] || (NN_Cmp (&cc[i], dd, ddDigits) >= 0)) {
        !           304:       ai++;
        !           305:       cc[i+ddDigits] -= NN_Sub (&cc[i], &cc[i], dd, ddDigits);
        !           306:     }
        !           307:     
        !           308:     a[i] = ai;
        !           309:   }
        !           310:   
        !           311:   /* Restore result.
        !           312:    */
        !           313:   NN_AssignZero (b, dDigits);
        !           314:   NN_RShift (b, cc, shift, ddDigits);
        !           315: 
        !           316:   /* Zeroize potentially sensitive information.
        !           317:    */
        !           318:   R_memset ((POINTER)cc, 0, sizeof (cc));
        !           319:   R_memset ((POINTER)dd, 0, sizeof (dd));
        !           320: }
        !           321: 
        !           322: /* Computes a = b mod c.
        !           323: 
        !           324:    Lengths: a[cDigits], b[bDigits], c[cDigits].
        !           325:    Assumes c > 0, bDigits < 2 * MAX_NN_DIGITS, cDigits < MAX_NN_DIGITS.
        !           326:  */
        !           327: void NN_Mod (a, b, bDigits, c, cDigits)
        !           328: NN_DIGIT *a, *b, *c;
        !           329: unsigned int bDigits, cDigits;
        !           330: {
        !           331:   NN_DIGIT t[2 * MAX_NN_DIGITS];
        !           332:   
        !           333:   NN_Div (t, a, b, bDigits, c, cDigits);
        !           334:   
        !           335:   /* Zeroize potentially sensitive information.
        !           336:    */
        !           337:   R_memset ((POINTER)t, 0, sizeof (t));
        !           338: }
        !           339: 
        !           340: /* Computes a = b * c mod d.
        !           341: 
        !           342:    Lengths: a[digits], b[digits], c[digits], d[digits].
        !           343:    Assumes d > 0, digits < MAX_NN_DIGITS.
        !           344:  */
        !           345: void NN_ModMult (a, b, c, d, digits)
        !           346: NN_DIGIT *a, *b, *c, *d;
        !           347: unsigned int digits;
        !           348: {
        !           349:   NN_DIGIT t[2*MAX_NN_DIGITS];
        !           350: 
        !           351:   NN_Mult (t, b, c, digits);
        !           352:   NN_Mod (a, t, 2 * digits, d, digits);
        !           353:   
        !           354:   /* Zeroize potentially sensitive information.
        !           355:    */
        !           356:   R_memset ((POINTER)t, 0, sizeof (t));
        !           357: }
        !           358: 
        !           359: /* Computes a = b^c mod d.
        !           360: 
        !           361:    Lengths: a[dDigits], b[dDigits], c[cDigits], d[dDigits].
        !           362:    Assumes d > 0, cDigits > 0, dDigits < MAX_NN_DIGITS.
        !           363:  */
        !           364: 
        !           365: /* PGP 2.5's mpilib contains a faster modular exponentiation routine, mp_modexp.
        !           366:    If USEMPILIB is defined, NN_ModExp is replaced in the PGP 2.5 sources with a 
        !           367:    stub call to mp_modexp.  If USEMPILIB is not defined, we'll get a pure (albeit
        !           368:    slower) RSAREF implementation.
        !           369: 
        !           370:    The RSAREF 2.0 license, clause 1(c), permits "...modify[ing] the Program in any
        !           371:    manner for porting or performance improvement purposes..." */
        !           372: 
        !           373: #ifndef USEMPILIB
        !           374: void NN_ModExp (a, b, c, cDigits, d, dDigits)
        !           375: NN_DIGIT *a, *b, *c, *d;
        !           376: unsigned int cDigits, dDigits;
        !           377: {
        !           378:   NN_DIGIT bPower[3][MAX_NN_DIGITS], ci, t[MAX_NN_DIGITS];
        !           379:   int i;
        !           380:   unsigned int ciBits, j, s;
        !           381: 
        !           382:   /* Store b, b^2 mod d, and b^3 mod d.
        !           383:    */
        !           384:   NN_Assign (bPower[0], b, dDigits);
        !           385:   NN_ModMult (bPower[1], bPower[0], b, d, dDigits);
        !           386:   NN_ModMult (bPower[2], bPower[1], b, d, dDigits);
        !           387:   
        !           388:   NN_ASSIGN_DIGIT (t, 1, dDigits);
        !           389: 
        !           390:   cDigits = NN_Digits (c, cDigits);
        !           391:   for (i = cDigits - 1; i >= 0; i--) {
        !           392:     ci = c[i];
        !           393:     ciBits = NN_DIGIT_BITS;
        !           394:     
        !           395:     /* Scan past leading zero bits of most significant digit.
        !           396:      */
        !           397:     if (i == (int)(cDigits - 1)) {
        !           398:       while (! DIGIT_2MSB (ci)) {
        !           399:         ci <<= 2;
        !           400:         ciBits -= 2;
        !           401:       }
        !           402:     }
        !           403: 
        !           404:     for (j = 0; j < ciBits; j += 2, ci <<= 2) {
        !           405:       /* Compute t = t^4 * b^s mod d, where s = two MSB's of ci.
        !           406:        */
        !           407:       NN_ModMult (t, t, t, d, dDigits);
        !           408:       NN_ModMult (t, t, t, d, dDigits);
        !           409:       if ((s = DIGIT_2MSB (ci)) != 0)
        !           410:         NN_ModMult (t, t, bPower[s-1], d, dDigits);
        !           411:     }
        !           412:   }
        !           413:   
        !           414:   NN_Assign (a, t, dDigits);
        !           415:   
        !           416:   /* Zeroize potentially sensitive information.
        !           417:    */
        !           418:   R_memset ((POINTER)bPower, 0, sizeof (bPower));
        !           419:   R_memset ((POINTER)t, 0, sizeof (t));
        !           420: }
        !           421: #endif
        !           422: 
        !           423: /* Compute a = 1/b mod c, assuming inverse exists.
        !           424:    
        !           425:    Lengths: a[digits], b[digits], c[digits].
        !           426:    Assumes gcd (b, c) = 1, digits < MAX_NN_DIGITS.
        !           427:  */
        !           428: void NN_ModInv (a, b, c, digits)
        !           429: NN_DIGIT *a, *b, *c;
        !           430: unsigned int digits;
        !           431: {
        !           432:   NN_DIGIT q[MAX_NN_DIGITS], t1[MAX_NN_DIGITS], t3[MAX_NN_DIGITS],
        !           433:     u1[MAX_NN_DIGITS], u3[MAX_NN_DIGITS], v1[MAX_NN_DIGITS],
        !           434:     v3[MAX_NN_DIGITS], w[2*MAX_NN_DIGITS];
        !           435:   int u1Sign;
        !           436: 
        !           437:   /* Apply extended Euclidean algorithm, modified to avoid negative
        !           438:      numbers.
        !           439:    */
        !           440:   NN_ASSIGN_DIGIT (u1, 1, digits);
        !           441:   NN_AssignZero (v1, digits);
        !           442:   NN_Assign (u3, b, digits);
        !           443:   NN_Assign (v3, c, digits);
        !           444:   u1Sign = 1;
        !           445: 
        !           446:   while (! NN_Zero (v3, digits)) {
        !           447:     NN_Div (q, t3, u3, digits, v3, digits);
        !           448:     NN_Mult (w, q, v1, digits);
        !           449:     NN_Add (t1, u1, w, digits);
        !           450:     NN_Assign (u1, v1, digits);
        !           451:     NN_Assign (v1, t1, digits);
        !           452:     NN_Assign (u3, v3, digits);
        !           453:     NN_Assign (v3, t3, digits);
        !           454:     u1Sign = -u1Sign;
        !           455:   }
        !           456:   
        !           457:   /* Negate result if sign is negative.
        !           458:     */
        !           459:   if (u1Sign < 0)
        !           460:     NN_Sub (a, c, u1, digits);
        !           461:   else
        !           462:     NN_Assign (a, u1, digits);
        !           463: 
        !           464:   /* Zeroize potentially sensitive information.
        !           465:    */
        !           466:   R_memset ((POINTER)q, 0, sizeof (q));
        !           467:   R_memset ((POINTER)t1, 0, sizeof (t1));
        !           468:   R_memset ((POINTER)t3, 0, sizeof (t3));
        !           469:   R_memset ((POINTER)u1, 0, sizeof (u1));
        !           470:   R_memset ((POINTER)u3, 0, sizeof (u3));
        !           471:   R_memset ((POINTER)v1, 0, sizeof (v1));
        !           472:   R_memset ((POINTER)v3, 0, sizeof (v3));
        !           473:   R_memset ((POINTER)w, 0, sizeof (w));
        !           474: }
        !           475: 
        !           476: /* Computes a = gcd(b, c).
        !           477: 
        !           478:    Lengths: a[digits], b[digits], c[digits].
        !           479:    Assumes b > c, digits < MAX_NN_DIGITS.
        !           480:  */
        !           481: void NN_Gcd (a, b, c, digits)
        !           482: NN_DIGIT *a, *b, *c;
        !           483: unsigned int digits;
        !           484: {
        !           485:   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS], v[MAX_NN_DIGITS];
        !           486: 
        !           487:   NN_Assign (u, b, digits);
        !           488:   NN_Assign (v, c, digits);
        !           489: 
        !           490:   while (! NN_Zero (v, digits)) {
        !           491:     NN_Mod (t, u, digits, v, digits);
        !           492:     NN_Assign (u, v, digits);
        !           493:     NN_Assign (v, t, digits);
        !           494:   }
        !           495: 
        !           496:   NN_Assign (a, u, digits);
        !           497: 
        !           498:   /* Zeroize potentially sensitive information.
        !           499:    */
        !           500:   R_memset ((POINTER)t, 0, sizeof (t));
        !           501:   R_memset ((POINTER)u, 0, sizeof (u));
        !           502:   R_memset ((POINTER)v, 0, sizeof (v));
        !           503: }
        !           504: 
        !           505: /* Returns sign of a - b.
        !           506: 
        !           507:    Lengths: a[digits], b[digits].
        !           508:  */
        !           509: int NN_Cmp (a, b, digits)
        !           510: NN_DIGIT *a, *b;
        !           511: unsigned int digits;
        !           512: {
        !           513:   int i;
        !           514:   
        !           515:   for (i = digits - 1; i >= 0; i--) {
        !           516:     if (a[i] > b[i])
        !           517:       return (1);
        !           518:     if (a[i] < b[i])
        !           519:       return (-1);
        !           520:   }
        !           521: 
        !           522:   return (0);
        !           523: }
        !           524: 
        !           525: /* Returns nonzero iff a is zero.
        !           526: 
        !           527:    Lengths: a[digits].
        !           528:  */
        !           529: int NN_Zero (a, digits)
        !           530: NN_DIGIT *a;
        !           531: unsigned int digits;
        !           532: {
        !           533:   unsigned int i;
        !           534:   
        !           535:   for (i = 0; i < digits; i++)
        !           536:     if (a[i])
        !           537:       return (0);
        !           538:     
        !           539:   return (1);
        !           540: }
        !           541: 
        !           542: /* Returns the significant length of a in bits.
        !           543: 
        !           544:    Lengths: a[digits].
        !           545:  */
        !           546: unsigned int NN_Bits (a, digits)
        !           547: NN_DIGIT *a;
        !           548: unsigned int digits;
        !           549: {
        !           550:   if ((digits = NN_Digits (a, digits)) == 0)
        !           551:     return (0);
        !           552: 
        !           553:   return ((digits - 1) * NN_DIGIT_BITS + NN_DigitBits (a[digits-1]));
        !           554: }
        !           555: 
        !           556: /* Returns the significant length of a in digits.
        !           557: 
        !           558:    Lengths: a[digits].
        !           559:  */
        !           560: unsigned int NN_Digits (a, digits)
        !           561: NN_DIGIT *a;
        !           562: unsigned int digits;
        !           563: {
        !           564:   int i;
        !           565:   
        !           566:   for (i = digits - 1; i >= 0; i--)
        !           567:     if (a[i])
        !           568:       break;
        !           569: 
        !           570:   return (i + 1);
        !           571: }
        !           572: 
        !           573: /* Computes a = b + c*d, where c is a digit. Returns carry.
        !           574: 
        !           575:    Lengths: a[digits], b[digits], d[digits].
        !           576:  */
        !           577: static NN_DIGIT NN_AddDigitMult (a, b, c, d, digits)
        !           578: NN_DIGIT *a, *b, c, *d;
        !           579: unsigned int digits;
        !           580: {
        !           581:   NN_DIGIT carry, t[2];
        !           582:   unsigned int i;
        !           583: 
        !           584:   if (c == 0)
        !           585:     return (0);
        !           586: 
        !           587:   carry = 0;
        !           588:   for (i = 0; i < digits; i++) {
        !           589:     NN_DigitMult (t, c, d[i]);
        !           590:     if ((a[i] = b[i] + carry) < carry)
        !           591:       carry = 1;
        !           592:     else
        !           593:       carry = 0;
        !           594:     if ((a[i] += t[0]) < t[0])
        !           595:       carry++;
        !           596:     carry += t[1];
        !           597:   }
        !           598:   
        !           599:   return (carry);
        !           600: }
        !           601: 
        !           602: /* Computes a = b - c*d, where c is a digit. Returns borrow.
        !           603: 
        !           604:    Lengths: a[digits], b[digits], d[digits].
        !           605:  */
        !           606: static NN_DIGIT NN_SubDigitMult (a, b, c, d, digits)
        !           607: NN_DIGIT *a, *b, c, *d;
        !           608: unsigned int digits;
        !           609: {
        !           610:   NN_DIGIT borrow, t[2];
        !           611:   unsigned int i;
        !           612: 
        !           613:   if (c == 0)
        !           614:     return (0);
        !           615: 
        !           616:   borrow = 0;
        !           617:   for (i = 0; i < digits; i++) {
        !           618:     NN_DigitMult (t, c, d[i]);
        !           619:     if ((a[i] = b[i] - borrow) > (MAX_NN_DIGIT - borrow))
        !           620:       borrow = 1;
        !           621:     else
        !           622:       borrow = 0;
        !           623:     if ((a[i] -= t[0]) > (MAX_NN_DIGIT - t[0]))
        !           624:       borrow++;
        !           625:     borrow += t[1];
        !           626:   }
        !           627:   
        !           628:   return (borrow);
        !           629: }
        !           630: 
        !           631: /* Returns the significant length of a in bits, where a is a digit.
        !           632:  */
        !           633: static unsigned int NN_DigitBits (a)
        !           634: NN_DIGIT a;
        !           635: {
        !           636:   unsigned int i;
        !           637:   
        !           638:   for (i = 0; i < NN_DIGIT_BITS; i++, a >>= 1)
        !           639:     if (a == 0)
        !           640:       break;
        !           641:     
        !           642:   return (i);
        !           643: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.