OSX/libsecurity_cryptkit/lib/giantPort_Generic.h

   1 /* Copyright (c) 1998,2011,2014 Apple Inc.  All Rights Reserved.
   2  *
   3  * NOTICE: USE OF THE MATERIALS ACCOMPANYING THIS NOTICE IS SUBJECT
   4  * TO THE TERMS OF THE SIGNED "FAST ELLIPTIC ENCRYPTION (FEE) REFERENCE
   5  * SOURCE CODE EVALUATION AGREEMENT" BETWEEN APPLE, INC. AND THE
   6  * ORIGINAL LICENSEE THAT OBTAINED THESE MATERIALS FROM APPLE,
   7  * INC.  ANY USE OF THESE MATERIALS NOT PERMITTED BY SUCH AGREEMENT WILL
   8  * EXPOSE YOU TO LIABILITY.
   9  ***************************************************************************
  10  *
  11  * giantPort_Generic.h - Generic giant definitions routines, used when
  12  *                       no platform-specific version is available.
  13  *
  14  * Revision History
  15  * ----------------
  16  * 06 Apr 1998 at Apple
  17  *      Created.
  18  */
  19
  20 #ifndef _CK_NSGIANT_PORT_GENERIC_H_
  21 #define _CK_NSGIANT_PORT_GENERIC_H_
  22
  23 #include "feeDebug.h"
  24 #include "platform.h"
  25 #include "giantIntegers.h"
  26
  27 #ifdef __cplusplus
  28 extern "C" {
  29 #endif
  30
  31 /*
  32  * We'll be using the compiler's 64-bit long long for these routines.
  33  *
  34  * Mask for upper word.
  35  */
  36 #define GIANT_UPPER_DIGIT_MASK  (~(unsigned long long(GIANT_DIGIT_MASK)))
  37
  38 /*
  39  * Multiple-precision arithmetic routines/macros.
  40  */
  41
  42 /*
  43  * Add two digits, return sum. Carry bit returned as an out parameter.
  44  * This should work any size giantDigits up to unsigned int.
  45  */
  46 static inline giantDigit giantAddDigits(
  47         giantDigit dig1,
  48         giantDigit dig2,
  49         giantDigit *carry)                      /* RETURNED, 0 or 1 */
  50 {
  51         giantDigit sum = dig1 + dig2;
  52
  53         if((sum < dig1) || (sum < dig2)) {
  54                 *carry = 1;
  55         }
  56         else {
  57                 *carry = 0;
  58         }
  59         return sum & GIANT_DIGIT_MASK;
  60 }
  61
  62 /*
  63  * Add a single digit value to a double digit accumulator in place.
  64  * Carry out of the MSD of the accumulator is not handled.
  65  * This should work any size giantDigits up to unsigned int.
  66  */
  67 static inline void giantAddDouble(
  68         giantDigit *accLow,                     /* IN/OUT */
  69         giantDigit *accHigh,                    /* IN/OUT */
  70         giantDigit val)
  71 {
  72         giantDigit sumLo = *accLow + val;
  73
  74         if((sumLo < *accLow) || (sumLo < val)) {
  75             (*accHigh)++;
  76             #if FEE_DEBUG
  77             if(*accHigh == 0) {
  78                 CKRaise("giantAddDouble overflow");
  79             }
  80             #endif      /* FEE_DEBUG */
  81         }
  82         *accLow = sumLo;
  83 }
  84
  85 /*
  86  * Subtract a - b, return difference. Borrow bit returned as an out parameter.
  87  * This should work any size giantDigits up to unsigned int.
  88  */
  89 static inline giantDigit giantSubDigits(
  90         giantDigit a,
  91         giantDigit b,
  92         giantDigit *borrow)                     /* RETURNED, 0 or 1 */
  93 {
  94         giantDigit diff = a - b;
  95
  96         if(a < b) {
  97                 *borrow = 1;
  98         }
  99         else {
 100                 *borrow = 0;
 101         }
 102         return diff;
 103 }
 104
 105 /*
 106  * Multiply two digits, return two digits.
 107  * This should work for 16 or 32 bit giantDigits, though it's kind of
 108  * inefficient for 16 bits.
 109  */
 110 static inline void giantMulDigits(
 111         giantDigit      dig1,
 112         giantDigit      dig2,
 113         giantDigit      *lowProduct,            /* RETURNED, low digit */
 114         giantDigit      *hiProduct)             /* RETURNED, high digit */
 115 {
 116 #if GIANT_LOG2_BITS_PER_DIGIT>5
 117 #error "dprod is too small to represent the full result of the multiplication"
 118 #else
 119         unsigned long long dprod;
 120 #endif
 121
 122         dprod = (unsigned long long)dig1 * (unsigned long long)dig2;
 123         *hiProduct =  (giantDigit)(dprod >> GIANT_BITS_PER_DIGIT);
 124         *lowProduct = (giantDigit)dprod;
 125 }
 126
 127 /*
 128  * Multiply a vector of giantDigits, candVector, by a single giantDigit,
 129  * plierDigit, adding results into prodVector. Returns m.s. digit from
 130  * final multiply; only candLength digits of *prodVector will be written.
 131  */
 132 static inline giantDigit VectorMultiply(
 133         giantDigit plierDigit,
 134         giantDigit *candVector,
 135         unsigned candLength,
 136         giantDigit *prodVector)
 137 {
 138         unsigned candDex;               // index into multiplicandVector
 139         giantDigit lastCarry = 0;
 140         giantDigit prodLo;
 141         giantDigit prodHi;
 142
 143         for(candDex=0; candDex<candLength; ++candDex) {
 144             /*
 145              * prod = *(candVector++) * plierDigit + *prodVector + lastCarry
 146              */
 147             giantMulDigits(*(candVector++),
 148                 plierDigit,
 149                 &prodLo,
 150                 &prodHi);
 151             giantAddDouble(&prodLo, &prodHi, *prodVector);
 152             giantAddDouble(&prodLo, &prodHi, lastCarry);
 153
 154             /*
 155              * *(destptr++) = prodHi;
 156              * lastCarry = prodLo;
 157              */
 158             *(prodVector++) = prodLo;
 159             lastCarry = prodHi;
 160         }
 161
 162         return lastCarry;
 163 }
 164
 165 #ifdef __cplusplus
 166 extern "C" {
 167 #endif
 168
 169 #endif  /*_CK_NSGIANT_PORT_GENERIC_H_*/