crypto/dist/heimdal/lib/hcrypto/imath/imath.h

   1 /*
   2   Name:     imath.h
   3   Purpose:  Arbitrary precision integer arithmetic routines.
   4   Author:   M. J. Fromberger <http://www.dartmouth.edu/~sting/>
   5   Info:     $Id: imath.h,v 1.1 2008/03/22 09:42:41 mlelstv Exp $
   6
   7   Copyright (C) 2002-2007 Michael J. Fromberger, All Rights Reserved.
   8
   9   Permission is hereby granted, free of charge, to any person
  10   obtaining a copy of this software and associated documentation files
  11   (the "Software"), to deal in the Software without restriction,
  12   including without limitation the rights to use, copy, modify, merge,
  13   publish, distribute, sublicense, and/or sell copies of the Software,
  14   and to permit persons to whom the Software is furnished to do so,
  15   subject to the following conditions:
  16
  17   The above copyright notice and this permission notice shall be
  18   included in all copies or substantial portions of the Software.
  19
  20   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23   NONINFRINGEMENT.  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  24   BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  25   ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  26   CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  27   SOFTWARE.
  28  */
  29
  30 #ifndef IMATH_H_
  31 #define IMATH_H_
  32
  33 #include <limits.h>
  34
  35 #ifdef __cplusplus
  36 extern "C" {
  37 #endif
  38
  39 typedef unsigned char      mp_sign;
  40 typedef unsigned int       mp_size;
  41 typedef int                mp_result;
  42 #ifdef USE_LONG_LONG
  43 typedef unsigned int       mp_digit;
  44 typedef unsigned long long mp_word;
  45 #else
  46 typedef unsigned short     mp_digit;
  47 typedef unsigned int       mp_word;
  48 #endif
  49
  50 typedef struct mpz {
  51   mp_digit    single;
  52   mp_digit   *digits;
  53   mp_size     alloc;
  54   mp_size     used;
  55   mp_sign     sign;
  56 } mpz_t, *mp_int;
  57
  58 #define MP_DIGITS(Z) ((Z)->digits)
  59 #define MP_ALLOC(Z)  ((Z)->alloc)
  60 #define MP_USED(Z)   ((Z)->used)
  61 #define MP_SIGN(Z)   ((Z)->sign)
  62
  63 extern const mp_result MP_OK;
  64 extern const mp_result MP_FALSE;
  65 extern const mp_result MP_TRUE;
  66 extern const mp_result MP_MEMORY;
  67 extern const mp_result MP_RANGE;
  68 extern const mp_result MP_UNDEF;
  69 extern const mp_result MP_TRUNC;
  70 extern const mp_result MP_BADARG;
  71
  72 #define MP_DIGIT_BIT    (sizeof(mp_digit) * CHAR_BIT)
  73 #define MP_WORD_BIT     (sizeof(mp_word) * CHAR_BIT)
  74
  75 #ifdef USE_LONG_LONG
  76 #  ifndef ULONG_LONG_MAX
  77 #    ifdef ULLONG_MAX
  78 #      define ULONG_LONG_MAX   ULLONG_MAX
  79 #    else
  80 #      error "Maximum value of unsigned long long not defined!"
  81 #    endif
  82 #  endif
  83 #  define MP_DIGIT_MAX   (ULONG_MAX * 1ULL)
  84 #  define MP_WORD_MAX    ULONG_LONG_MAX
  85 #else
  86 #  define MP_DIGIT_MAX    (USHRT_MAX * 1UL)
  87 #  define MP_WORD_MAX     (UINT_MAX * 1UL)
  88 #endif
  89
  90 #define MP_MIN_RADIX    2
  91 #define MP_MAX_RADIX    36
  92
  93 /* Values with fewer than this many significant digits use the
  94    standard multiplication algorithm; otherwise, a recursive algorithm
  95    is used.  Choose a value to suit your platform.
  96  */
  97 #define MP_MULT_THRESH  22
  98
  99 #define MP_DEFAULT_PREC 8   /* default memory allocation, in digits */
 100
 101 extern const mp_sign   MP_NEG;
 102 extern const mp_sign   MP_ZPOS;
 103
 104 #define mp_int_is_odd(Z)  ((Z)->digits[0] & 1)
 105 #define mp_int_is_even(Z) !((Z)->digits[0] & 1)
 106
 107 mp_result mp_int_init(mp_int z);
 108 mp_int    mp_int_alloc(void);
 109 mp_result mp_int_init_size(mp_int z, mp_size prec);
 110 mp_result mp_int_init_copy(mp_int z, mp_int old);
 111 mp_result mp_int_init_value(mp_int z, int value);
 112 mp_result mp_int_set_value(mp_int z, int value);
 113 void      mp_int_clear(mp_int z);
 114 void      mp_int_free(mp_int z);
 115
 116 mp_result mp_int_copy(mp_int a, mp_int c);           /* c = a     */
 117 void      mp_int_swap(mp_int a, mp_int c);           /* swap a, c */
 118 void      mp_int_zero(mp_int z);                     /* z = 0     */
 119 mp_result mp_int_abs(mp_int a, mp_int c);            /* c = |a|   */
 120 mp_result mp_int_neg(mp_int a, mp_int c);            /* c = -a    */
 121 mp_result mp_int_add(mp_int a, mp_int b, mp_int c);  /* c = a + b */
 122 mp_result mp_int_add_value(mp_int a, int value, mp_int c);
 123 mp_result mp_int_sub(mp_int a, mp_int b, mp_int c);  /* c = a - b */
 124 mp_result mp_int_sub_value(mp_int a, int value, mp_int c);
 125 mp_result mp_int_mul(mp_int a, mp_int b, mp_int c);  /* c = a * b */
 126 mp_result mp_int_mul_value(mp_int a, int value, mp_int c);
 127 mp_result mp_int_mul_pow2(mp_int a, int p2, mp_int c);
 128 mp_result mp_int_sqr(mp_int a, mp_int c);            /* c = a * a */
 129 mp_result mp_int_div(mp_int a, mp_int b,             /* q = a / b */
 130                      mp_int q, mp_int r);            /* r = a % b */
 131 mp_result mp_int_div_value(mp_int a, int value,      /* q = a / value */
 132                            mp_int q, int *r);        /* r = a % value */
 133 mp_result mp_int_div_pow2(mp_int a, int p2,          /* q = a / 2^p2  */
 134                           mp_int q, mp_int r);       /* r = q % 2^p2  */
 135 mp_result mp_int_mod(mp_int a, mp_int m, mp_int c);  /* c = a % m */
 136 #define   mp_int_mod_value(A, V, R) mp_int_div_value((A), (V), 0, (R))
 137 mp_result mp_int_expt(mp_int a, int b, mp_int c);    /* c = a^b   */
 138 mp_result mp_int_expt_value(int a, int b, mp_int c); /* c = a^b   */
 139
 140 int       mp_int_compare(mp_int a, mp_int b);          /* a <=> b     */
 141 int       mp_int_compare_unsigned(mp_int a, mp_int b); /* |a| <=> |b| */
 142 int       mp_int_compare_zero(mp_int z);               /* a <=> 0     */
 143 int       mp_int_compare_value(mp_int z, int value);   /* a <=> v     */
 144
 145 /* Returns true if v|a, false otherwise (including errors) */
 146 int       mp_int_divisible_value(mp_int a, int v);
 147
 148 /* Returns k >= 0 such that z = 2^k, if one exists; otherwise < 0 */
 149 int       mp_int_is_pow2(mp_int z);
 150
 151 mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m,
 152                          mp_int c);                    /* c = a^b (mod m) */
 153 mp_result mp_int_exptmod_evalue(mp_int a, int value,
 154                                 mp_int m, mp_int c);   /* c = a^v (mod m) */
 155 mp_result mp_int_exptmod_bvalue(int value, mp_int b,
 156                                 mp_int m, mp_int c);   /* c = v^b (mod m) */
 157 mp_result mp_int_exptmod_known(mp_int a, mp_int b,
 158                                mp_int m, mp_int mu,
 159                                mp_int c);              /* c = a^b (mod m) */
 160 mp_result mp_int_redux_const(mp_int m, mp_int c);
 161
 162 mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c); /* c = 1/a (mod m) */
 163
 164 mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c);    /* c = gcd(a, b)   */
 165
 166 mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c,    /* c = gcd(a, b)   */
 167                       mp_int x, mp_int y);             /* c = ax + by     */
 168
 169 mp_result mp_int_sqrt(mp_int a, mp_int c);          /* c = floor(sqrt(q)) */
 170
 171 /* Convert to an int, if representable (returns MP_RANGE if not). */
 172 mp_result mp_int_to_int(mp_int z, int *out);
 173
 174 /* Convert to nul-terminated string with the specified radix, writing at
 175    most limit characters including the nul terminator  */
 176 mp_result mp_int_to_string(mp_int z, mp_size radix,
 177                            char *str, int limit);
 178
 179 /* Return the number of characters required to represent
 180    z in the given radix.  May over-estimate. */
 181 mp_result mp_int_string_len(mp_int z, mp_size radix);
 182
 183 /* Read zero-terminated string into z */
 184 mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str);
 185 mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str,
 186                               char **end);
 187
 188 /* Return the number of significant bits in z */
 189 mp_result mp_int_count_bits(mp_int z);
 190
 191 /* Convert z to two's complement binary, writing at most limit bytes */
 192 mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit);
 193
 194 /* Read a two's complement binary value into z from the given buffer */
 195 mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len);
 196
 197 /* Return the number of bytes required to represent z in binary. */
 198 mp_result mp_int_binary_len(mp_int z);
 199
 200 /* Convert z to unsigned binary, writing at most limit bytes */
 201 mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit);
 202
 203 /* Read an unsigned binary value into z from the given buffer */
 204 mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len);
 205
 206 /* Return the number of bytes required to represent z as unsigned output */
 207 mp_result mp_int_unsigned_len(mp_int z);
 208
 209 /* Return a statically allocated string describing error code res */
 210 const char *mp_error_string(mp_result res);
 211
 212 #if DEBUG
 213 void      s_print(char *tag, mp_int z);
 214 void      s_print_buf(char *tag, mp_digit *buf, mp_size num);
 215 #endif
 216
 217 #ifdef __cplusplus
 218 }
 219 #endif
 220 #endif /* end IMATH_H_ */