util/gdss/lib/crypto/bignum/c/bn/bnDivide.c

   1 /* Copyright     Digital Equipment Corporation & INRIA     1988, 1989 */
   2 /* Last modified_on Fri Mar 30  3:29:17 GMT+2:00 1990 by shand */
   3 /*      modified_on Fri Apr 28 18:36:28 GMT+2:00 1989 by herve */
   4
   5
   6 /* bnDivide.c: a piece of the bignum kernel written in C */
   7
   8
   9                 /***************************************/
  10
  11 #define BNNMACROS_OFF
  12 #include "BigNum.h"
  13
  14                         /*** copyright ***/
  15
  16 static char copyright[]="@(#)bnDivide.c: copyright Digital Equipment Corporation & INRIA 1988, 1989, 1990\n";
  17
  18
  19 static divide (nn, nl, dd, dl)
  20
  21          BigNum         nn, dd;
  22 register BigNumLength   nl, dl;
  23
  24 /*
  25  * In-place division.
  26  *
  27  * Input (N has been EXTENDED by 1 PLACE; D is normalized):
  28  *      +-----------------------------------------------+----+
  29  *      |                       N                         EXT|
  30  *      +-----------------------------------------------+----+
  31  *
  32  *      +-------------------------------+
  33  *      |               D              1|
  34  *      +-------------------------------+
  35  *
  36  * Output (in place of N):
  37  *      +-------------------------------+---------------+----+
  38  *      |               R               |          Q         |
  39  *      +-------------------------------+---------------+----+
  40  *
  41  * Assumes:
  42  *    N > D
  43  *    Size(N) > Size(D)
  44  *    last digit of N < last digit of D
  45  *    D is normalized (Base/2 <= last digit of D < Base)
  46  */
  47
  48 {
  49    register     int             ni;
  50                 BigNumDigit     DDigit, BaseMinus1, QApp, RApp;
  51
  52
  53    /* Initialize constants */
  54    BnnSetDigit (&BaseMinus1, 0);
  55    BnnComplement(&BaseMinus1, 1);
  56
  57    /* Save the most significant digit of D */
  58    BnnAssign (&DDigit, dd+dl-1, 1);
  59
  60    /* Replace D by Base - D */
  61    BnnComplement (dd, dl);
  62    BnnAddCarry (dd, dl, 1);
  63
  64    /* For each digit of the divisor, from most significant to least: */
  65    nl += 1;
  66    ni = nl-dl;
  67    while (--ni >= 0)
  68    {
  69       /* Compute the approximate quotient */
  70       nl--;
  71
  72       /* If first digits of numerator and denominator are the same, */
  73       if (BnnCompareDigits (*(nn+nl), DDigit) == BN_EQ)
  74          /* Use "Base - 1" for the approximate quotient */
  75          BnnAssign (&QApp, &BaseMinus1, 1);
  76       else
  77          /* Divide the first 2 digits of N by the first digit of D */
  78          RApp = BnnDivideDigit (&QApp, nn+nl-1, 2, DDigit);
  79
  80       /* Compute the remainder */
  81       BnnMultiplyDigit (nn+ni, dl+1, dd, dl, QApp);
  82
  83       /* Correct the approximate quotient, in case it was too large */
  84       while (BnnCompareDigits (*(nn+nl), QApp) != BN_EQ)
  85       {
  86          BnnSubtract (nn+ni, dl+1, dd, dl, 1);  /* Subtract D from N */
  87          BnnSubtractBorrow (&QApp, 1, 0);       /* Q -= 1 */
  88       }
  89    }
  90
  91    /* Restore original D */
  92    BnnComplement (dd, dl);
  93    BnnAddCarry (dd, dl, 1);
  94 }
  95
  96
  97                 /***************************************/
  98 /*\f*/
  99
 100
 101 void BnnDivide (nn, nl, dd, dl)
 102
 103          BigNum         nn, dd;
 104 register BigNumLength   nl, dl;
 105
 106 /*
 107  * Performs the quotient:
 108  *    N div D => high-order bits of N, starting at N[dl]
 109  *    N mod D => low-order dl bits of N
 110  *
 111  * Assumes
 112  *    Size(N) > Size(D),
 113  *    last digit of N < last digit of D (if N > D).
 114  */
 115
 116 {
 117    BigNumDigit  nshift;
 118
 119
 120    /* Take care of easy cases first */
 121    switch (BnnCompare (nn, nl, dd, dl))
 122    {
 123       case BN_LT:       /* n < d */
 124          ;                                      /* N => R */
 125          BnnSetToZero (nn+dl, nl-dl);           /* 0 => Q */
 126          return;
 127       case BN_EQ:       /* n == d */
 128          BnnSetToZero (nn, nl);                 /* 0 => R */
 129          BnnSetDigit (nn+nl-1, 1);              /* 1 => Q */
 130          return;
 131    }
 132
 133    /* here: n > d */
 134
 135    /* If divisor is just 1 digit, use a special divide */
 136    if (dl == 1)
 137       *nn = BnnDivideDigit (nn+1, nn, nl, *dd);        /* note: nn+1 = nn+dl */
 138    /* Otherwise, divide one digit at a time */
 139    else
 140    {
 141       /* Normalize */
 142       nshift = BnnNumLeadingZeroBitsInDigit (*(dd+dl-1));
 143       BnnShiftLeft (dd, dl, nshift);
 144       BnnShiftLeft (nn, nl, nshift);
 145
 146       /* Divide */
 147       divide (nn, nl-1, dd, dl);
 148
 149       /* Unnormalize */
 150       BnnShiftRight (dd, dl, nshift);
 151       BnnShiftRight (nn, dl, nshift);
 152       /* note: unnormalize N <=> unnormalize R (with R < D) */
 153    }
 154 }