lib/hcrypto/imath/imath.h

   1 /*
   2   Name:     imath.h
   3   Purpose:  Arbitrary precision integer arithmetic routines.
   4   Author:   M. J. Fromberger <http://spinning-yarns.org/michael/>
   5   Info:     $Id: imath.h 635 2008-01-08 18:19:40Z sting $
   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 typedef long               mp_small;  /* must be a signed type */
  43 typedef unsigned long      mp_usmall; /* must be an unsigned type */
  44 #ifdef USE_LONG_LONG
  45 typedef unsigned int       mp_digit;
  46 typedef unsigned long long mp_word;
  47 #else
  48 typedef unsigned short     mp_digit;
  49 typedef unsigned int       mp_word;
  50 #endif
  51
  52 typedef struct mpz {
  53   mp_digit    single;
  54   mp_digit   *digits;
  55   mp_size     alloc;
  56   mp_size     used;
  57   mp_sign     sign;
  58 } mpz_t, *mp_int;
  59
  60 #define MP_DIGITS(Z) ((Z)->digits)
  61 #define MP_ALLOC(Z)  ((Z)->alloc)
  62 #define MP_USED(Z)   ((Z)->used)
  63 #define MP_SIGN(Z)   ((Z)->sign)
  64
  65 extern const mp_result MP_OK;
  66 extern const mp_result MP_FALSE;
  67 extern const mp_result MP_TRUE;
  68 extern const mp_result MP_MEMORY;
  69 extern const mp_result MP_RANGE;
  70 extern const mp_result MP_UNDEF;
  71 extern const mp_result MP_TRUNC;
  72 extern const mp_result MP_BADARG;
  73 extern const mp_result MP_MINERR;
  74
  75 #define MP_DIGIT_BIT    (sizeof(mp_digit) * CHAR_BIT)
  76 #define MP_WORD_BIT     (sizeof(mp_word) * CHAR_BIT)
  77 #define MP_SMALL_MIN    LONG_MIN
  78 #define MP_SMALL_MAX    LONG_MAX
  79 #define MP_USMALL_MIN   ULONG_MIN
  80 #define MP_USMALL_MAX   ULONG_MAX
  81
  82 #ifdef USE_LONG_LONG
  83 #  ifndef ULONG_LONG_MAX
  84 #    ifdef ULLONG_MAX
  85 #      define ULONG_LONG_MAX   ULLONG_MAX
  86 #    else
  87 #      error "Maximum value of unsigned long long not defined!"
  88 #    endif
  89 #  endif
  90 #  define MP_DIGIT_MAX   (ULONG_MAX * 1ULL)
  91 #  define MP_WORD_MAX    ULONG_LONG_MAX
  92 #else
  93 #  define MP_DIGIT_MAX    (USHRT_MAX * 1UL)
  94 #  define MP_WORD_MAX     (UINT_MAX * 1UL)
  95 #endif
  96
  97 #define MP_MIN_RADIX    2
  98 #define MP_MAX_RADIX    36
  99
 100 /* Values with fewer than this many significant digits use the
 101    standard multiplication algorithm; otherwise, a recursive algorithm
 102    is used.  Choose a value to suit your platform.
 103  */
 104 #define MP_MULT_THRESH  22
 105
 106 #define MP_DEFAULT_PREC 8   /* default memory allocation, in digits */
 107
 108 extern const mp_sign   MP_NEG;
 109 extern const mp_sign   MP_ZPOS;
 110
 111 #define mp_int_is_odd(Z)  ((Z)->digits[0] & 1)
 112 #define mp_int_is_even(Z) !((Z)->digits[0] & 1)
 113
 114 mp_result mp_int_init(mp_int z);
 115 mp_int    mp_int_alloc(void);
 116 mp_result mp_int_init_size(mp_int z, mp_size prec);
 117 mp_result mp_int_init_copy(mp_int z, mp_int old);
 118 mp_result mp_int_init_value(mp_int z, mp_small value);
 119 mp_result mp_int_set_value(mp_int z, mp_small value);
 120 void      mp_int_clear(mp_int z);
 121 void      mp_int_free(mp_int z);
 122
 123 mp_result mp_int_copy(mp_int a, mp_int c);           /* c = a     */
 124 void      mp_int_swap(mp_int a, mp_int c);           /* swap a, c */
 125 void      mp_int_zero(mp_int z);                     /* z = 0     */
 126 mp_result mp_int_abs(mp_int a, mp_int c);            /* c = |a|   */
 127 mp_result mp_int_neg(mp_int a, mp_int c);            /* c = -a    */
 128 mp_result mp_int_add(mp_int a, mp_int b, mp_int c);  /* c = a + b */
 129 mp_result mp_int_add_value(mp_int a, mp_small value, mp_int c);
 130 mp_result mp_int_sub(mp_int a, mp_int b, mp_int c);  /* c = a - b */
 131 mp_result mp_int_sub_value(mp_int a, mp_small value, mp_int c);
 132 mp_result mp_int_mul(mp_int a, mp_int b, mp_int c);  /* c = a * b */
 133 mp_result mp_int_mul_value(mp_int a, mp_small value, mp_int c);
 134 mp_result mp_int_mul_pow2(mp_int a, mp_small p2, mp_int c);
 135 mp_result mp_int_sqr(mp_int a, mp_int c);            /* c = a * a */
 136 mp_result mp_int_div(mp_int a, mp_int b,             /* q = a / b */
 137                      mp_int q, mp_int r);            /* r = a % b */
 138 mp_result mp_int_div_value(mp_int a, mp_small value, /* q = a / value */
 139                            mp_int q, mp_small *r);   /* r = a % value */
 140 mp_result mp_int_div_pow2(mp_int a, mp_small p2,     /* q = a / 2^p2  */
 141                           mp_int q, mp_int r);       /* r = q % 2^p2  */
 142 mp_result mp_int_mod(mp_int a, mp_int m, mp_int c);  /* c = a % m */
 143 #define   mp_int_mod_value(A, V, R) mp_int_div_value((A), (V), 0, (R))
 144 mp_result mp_int_expt(mp_int a, mp_small b, mp_int c);         /* c = a^b */
 145 mp_result mp_int_expt_value(mp_small a, mp_small b, mp_int c); /* c = a^b */
 146
 147 int       mp_int_compare(mp_int a, mp_int b);          /* a <=> b     */
 148 int       mp_int_compare_unsigned(mp_int a, mp_int b); /* |a| <=> |b| */
 149 int       mp_int_compare_zero(mp_int z);                  /* a <=> 0  */
 150 int       mp_int_compare_value(mp_int z, mp_small value); /* a <=> v  */
 151
 152 /* Returns true if v|a, false otherwise (including errors) */
 153 int       mp_int_divisible_value(mp_int a, mp_small v);
 154
 155 /* Returns k >= 0 such that z = 2^k, if one exists; otherwise < 0 */
 156 int       mp_int_is_pow2(mp_int z);
 157
 158 mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m,
 159                          mp_int c);                    /* c = a^b (mod m) */
 160 mp_result mp_int_exptmod_evalue(mp_int a, mp_small value,
 161                                 mp_int m, mp_int c);   /* c = a^v (mod m) */
 162 mp_result mp_int_exptmod_bvalue(mp_small value, mp_int b,
 163                                 mp_int m, mp_int c);   /* c = v^b (mod m) */
 164 mp_result mp_int_exptmod_known(mp_int a, mp_int b,
 165                                mp_int m, mp_int mu,
 166                                mp_int c);              /* c = a^b (mod m) */
 167 mp_result mp_int_redux_const(mp_int m, mp_int c);
 168
 169 mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c); /* c = 1/a (mod m) */
 170
 171 mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c);    /* c = gcd(a, b)   */
 172
 173 mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c,    /* c = gcd(a, b)   */
 174                       mp_int x, mp_int y);             /* c = ax + by     */
 175
 176 mp_result mp_int_lcm(mp_int a, mp_int b, mp_int c);    /* c = lcm(a, b)   */
 177
 178 mp_result mp_int_root(mp_int a, mp_small b, mp_int c); /* c = floor(a^{1/b}) */
 179 #define   mp_int_sqrt(a, c) mp_int_root(a, 2, c)       /* c = floor(sqrt(a)) */
 180
 181 /* Convert to a small int, if representable; else MP_RANGE */
 182 mp_result mp_int_to_int(mp_int z, mp_small *out);
 183 mp_result mp_int_to_uint(mp_int z, mp_usmall *out);
 184
 185 /* Convert to nul-terminated string with the specified radix, writing at
 186    most limit characters including the nul terminator  */
 187 mp_result mp_int_to_string(mp_int z, mp_size radix,
 188                            char *str, int limit);
 189
 190 /* Return the number of characters required to represent
 191    z in the given radix.  May over-estimate. */
 192 mp_result mp_int_string_len(mp_int z, mp_size radix);
 193
 194 /* Read zero-terminated string into z */
 195 mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str);
 196 mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str,
 197                               char **end);
 198
 199 /* Return the number of significant bits in z */
 200 mp_result mp_int_count_bits(mp_int z);
 201
 202 /* Convert z to two's complement binary, writing at most limit bytes */
 203 mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit);
 204
 205 /* Read a two's complement binary value into z from the given buffer */
 206 mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len);
 207
 208 /* Return the number of bytes required to represent z in binary. */
 209 mp_result mp_int_binary_len(mp_int z);
 210
 211 /* Convert z to unsigned binary, writing at most limit bytes */
 212 mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit);
 213
 214 /* Read an unsigned binary value into z from the given buffer */
 215 mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len);
 216
 217 /* Return the number of bytes required to represent z as unsigned output */
 218 mp_result mp_int_unsigned_len(mp_int z);
 219
 220 /* Return a statically allocated string describing error code res */
 221 const char *mp_error_string(mp_result res);
 222
 223 #if DEBUG
 224 void      s_print(char *tag, mp_int z);
 225 void      s_print_buf(char *tag, mp_digit *buf, mp_size num);
 226 #endif
 227
 228 #ifdef __cplusplus
 229 }
 230 #endif
 231 #endif /* end IMATH_H_ */