contrib/pgcrypto/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 21 2006-04-02 18:58:36Z sting
   6
   7   Copyright (C) 2002 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 /* $PostgreSQL$ */
  30
  31 #ifndef IMATH_H_
  32 #define IMATH_H_
  33
  34 /* use always 32bit digits - should some arch use 16bit digits? */
  35 #define USE_LONG_LONG
  36
  37 #include <limits.h>
  38
  39 typedef unsigned char mp_sign;
  40 typedef unsigned int mp_size;
  41 typedef int mp_result;
  42
  43 #ifdef USE_LONG_LONG
  44 typedef uint32 mp_digit;
  45 typedef uint64 mp_word;
  46
  47 #define MP_DIGIT_MAX       0xFFFFFFFFULL
  48 #define MP_WORD_MAX                0xFFFFFFFFFFFFFFFFULL
  49 #else
  50 typedef uint16 mp_digit;
  51 typedef uint32 mp_word;
  52
  53 #define MP_DIGIT_MAX       0xFFFFUL
  54 #define MP_WORD_MAX                0xFFFFFFFFUL
  55 #endif
  56
  57 typedef struct mpz
  58 {
  59         mp_digit   *digits;
  60         mp_size         alloc;
  61         mp_size         used;
  62         mp_sign         sign;
  63 }       mpz_t, *mp_int;
  64
  65 #define MP_DIGITS(Z) ((Z)->digits)
  66 #define MP_ALLOC(Z)  ((Z)->alloc)
  67 #define MP_USED(Z)       ((Z)->used)
  68 #define MP_SIGN(Z)       ((Z)->sign)
  69
  70 extern const mp_result MP_OK;
  71 extern const mp_result MP_FALSE;
  72 extern const mp_result MP_TRUE;
  73 extern const mp_result MP_MEMORY;
  74 extern const mp_result MP_RANGE;
  75 extern const mp_result MP_UNDEF;
  76 extern const mp_result MP_TRUNC;
  77 extern const mp_result MP_BADARG;
  78
  79 #define MP_DIGIT_BIT    (sizeof(mp_digit) * CHAR_BIT)
  80 #define MP_WORD_BIT             (sizeof(mp_word) * CHAR_BIT)
  81
  82 #define MP_MIN_RADIX    2
  83 #define MP_MAX_RADIX    36
  84
  85 extern const mp_sign MP_NEG;
  86 extern const mp_sign MP_ZPOS;
  87
  88 #define mp_int_is_odd(Z)  ((Z)->digits[0] & 1)
  89 #define mp_int_is_even(Z) !((Z)->digits[0] & 1)
  90
  91 mp_size         mp_get_default_precision(void);
  92 void            mp_set_default_precision(mp_size s);
  93 mp_size         mp_get_multiply_threshold(void);
  94 void            mp_set_multiply_threshold(mp_size s);
  95
  96 mp_result       mp_int_init(mp_int z);
  97 mp_int          mp_int_alloc(void);
  98 mp_result       mp_int_init_size(mp_int z, mp_size prec);
  99 mp_result       mp_int_init_copy(mp_int z, mp_int old);
 100 mp_result       mp_int_init_value(mp_int z, int value);
 101 mp_result       mp_int_set_value(mp_int z, int value);
 102 void            mp_int_clear(mp_int z);
 103 void            mp_int_free(mp_int z);
 104
 105 mp_result       mp_int_copy(mp_int a, mp_int c);        /* c = a         */
 106 void            mp_int_swap(mp_int a, mp_int c);        /* swap a, c */
 107 void            mp_int_zero(mp_int z);          /* z = 0         */
 108 mp_result       mp_int_abs(mp_int a, mp_int c);         /* c = |a|       */
 109 mp_result       mp_int_neg(mp_int a, mp_int c);         /* c = -a        */
 110 mp_result       mp_int_add(mp_int a, mp_int b, mp_int c);       /* c = a + b */
 111 mp_result       mp_int_add_value(mp_int a, int value, mp_int c);
 112 mp_result       mp_int_sub(mp_int a, mp_int b, mp_int c);       /* c = a - b */
 113 mp_result       mp_int_sub_value(mp_int a, int value, mp_int c);
 114 mp_result       mp_int_mul(mp_int a, mp_int b, mp_int c);       /* c = a * b */
 115 mp_result       mp_int_mul_value(mp_int a, int value, mp_int c);
 116 mp_result       mp_int_mul_pow2(mp_int a, int p2, mp_int c);
 117 mp_result       mp_int_sqr(mp_int a, mp_int c);         /* c = a * a */
 118
 119 mp_result
 120 mp_int_div(mp_int a, mp_int b,                  /* q = a / b */
 121                    mp_int q, mp_int r); /* r = a % b */
 122 mp_result
 123 mp_int_div_value(mp_int a, int value,                   /* q = a / value */
 124                                  mp_int q, int *r);             /* r = a % value */
 125 mp_result
 126 mp_int_div_pow2(mp_int a, int p2,               /* q = a / 2^p2  */
 127                                 mp_int q, mp_int r);    /* r = q % 2^p2  */
 128 mp_result       mp_int_mod(mp_int a, mp_int m, mp_int c);       /* c = a % m */
 129
 130 #define   mp_int_mod_value(A, V, R) mp_int_div_value((A), (V), 0, (R))
 131 mp_result       mp_int_expt(mp_int a, int b, mp_int c);         /* c = a^b       */
 132 mp_result       mp_int_expt_value(int a, int b, mp_int c);      /* c = a^b       */
 133
 134 int                     mp_int_compare(mp_int a, mp_int b); /* a <=> b     */
 135 int                     mp_int_compare_unsigned(mp_int a, mp_int b);            /* |a| <=> |b| */
 136 int                     mp_int_compare_zero(mp_int z);          /* a <=> 0         */
 137 int                     mp_int_compare_value(mp_int z, int value);      /* a <=> v         */
 138
 139 /* Returns true if v|a, false otherwise (including errors) */
 140 int                     mp_int_divisible_value(mp_int a, int v);
 141
 142 /* Returns k >= 0 such that z = 2^k, if one exists; otherwise < 0 */
 143 int                     mp_int_is_pow2(mp_int z);
 144
 145 mp_result
 146 mp_int_exptmod(mp_int a, mp_int b, mp_int m,
 147                            mp_int c);           /* c = a^b (mod m) */
 148 mp_result
 149 mp_int_exptmod_evalue(mp_int a, int value,
 150                                           mp_int m, mp_int c);          /* c = a^v (mod m) */
 151 mp_result
 152 mp_int_exptmod_bvalue(int value, mp_int b,
 153                                           mp_int m, mp_int c);          /* c = v^b (mod m) */
 154 mp_result
 155 mp_int_exptmod_known(mp_int a, mp_int b,
 156                                          mp_int m, mp_int mu,
 157                                          mp_int c); /* c = a^b (mod m) */
 158 mp_result       mp_int_redux_const(mp_int m, mp_int c);
 159
 160 mp_result       mp_int_invmod(mp_int a, mp_int m, mp_int c);            /* c = 1/a (mod m) */
 161
 162 mp_result       mp_int_gcd(mp_int a, mp_int b, mp_int c);       /* c = gcd(a, b)   */
 163
 164 mp_result
 165 mp_int_egcd(mp_int a, mp_int b, mp_int c,               /* c = gcd(a, b)   */
 166                         mp_int x, mp_int y);    /* c = ax + by     */
 167
 168 mp_result       mp_int_sqrt(mp_int a, mp_int c);        /* c = floor(sqrt(q)) */
 169
 170 /* Convert to an int, if representable (returns MP_RANGE if not). */
 171 mp_result       mp_int_to_int(mp_int z, int *out);
 172
 173 /* Convert to nul-terminated string with the specified radix, writing at
 174    most limit characters including the nul terminator  */
 175 mp_result mp_int_to_string(mp_int z, mp_size radix,
 176                                  char *str, int limit);
 177
 178 /* Return the number of characters required to represent
 179    z in the given radix.  May over-estimate. */
 180 mp_result       mp_int_string_len(mp_int z, mp_size radix);
 181
 182 /* Read zero-terminated string into z */
 183 mp_result       mp_int_read_string(mp_int z, mp_size radix, const char *str);
 184 mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str,
 185                                         char **end);
 186
 187 /* Return the number of significant bits in z */
 188 mp_result       mp_int_count_bits(mp_int z);
 189
 190 /* Convert z to two's complement binary, writing at most limit bytes */
 191 mp_result       mp_int_to_binary(mp_int z, unsigned char *buf, int limit);
 192
 193 /* Read a two's complement binary value into z from the given buffer */
 194 mp_result       mp_int_read_binary(mp_int z, unsigned char *buf, int len);
 195
 196 /* Return the number of bytes required to represent z in binary. */
 197 mp_result       mp_int_binary_len(mp_int z);
 198
 199 /* Convert z to unsigned binary, writing at most limit bytes */
 200 mp_result       mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit);
 201
 202 /* Read an unsigned binary value into z from the given buffer */
 203 mp_result       mp_int_read_unsigned(mp_int z, unsigned char *buf, int len);
 204
 205 /* Return the number of bytes required to represent z as unsigned output */
 206 mp_result       mp_int_unsigned_len(mp_int z);
 207
 208 /* Return a statically allocated string describing error code res */
 209 const char *mp_error_string(mp_result res);
 210
 211 #if 0
 212 void            s_print(char *tag, mp_int z);
 213 void            s_print_buf(char *tag, mp_digit * buf, mp_size num);
 214 #endif
 215
 216 #endif   /* end IMATH_H_ */