Return to nn.c CVS log

Up to [rsaref] / rsaref / source

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

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

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