DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Implementation

Mercurial (2ccc66480643)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312
/*
 *  mpi.h
 *
 *  Arbitrary precision integer arithmetic library
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef _H_MPI_
#define _H_MPI_

#include "mpi-config.h"

#include "seccomon.h"
SEC_BEGIN_PROTOS

#if MP_DEBUG
#undef MP_IOFUNC
#define MP_IOFUNC 1
#endif

#if MP_IOFUNC
#include <stdio.h>
#include <ctype.h>
#endif

#include <limits.h>

#if defined(BSDI)
#undef ULLONG_MAX
#endif

#include <sys/types.h>

#define MP_NEG 1
#define MP_ZPOS 0

#define MP_OKAY 0    /* no error, all is well */
#define MP_YES 0     /* yes (boolean result)  */
#define MP_NO -1     /* no (boolean result)   */
#define MP_MEM -2    /* out of memory         */
#define MP_RANGE -3  /* argument out of range */
#define MP_BADARG -4 /* invalid parameter     */
#define MP_UNDEF -5  /* answer is undefined   */
#define MP_LAST_CODE MP_UNDEF

typedef unsigned int mp_sign;
typedef unsigned int mp_size;
typedef int mp_err;

#define MP_32BIT_MAX 4294967295U

#if !defined(ULONG_MAX)
#error "ULONG_MAX not defined"
#elif !defined(UINT_MAX)
#error "UINT_MAX not defined"
#elif !defined(USHRT_MAX)
#error "USHRT_MAX not defined"
#endif

#if defined(ULLONG_MAX) /* C99, Solaris */
#define MP_ULONG_LONG_MAX ULLONG_MAX
/* MP_ULONG_LONG_MAX was defined to be ULLONG_MAX */
#elif defined(ULONG_LONG_MAX) /* HPUX */
#define MP_ULONG_LONG_MAX ULONG_LONG_MAX
#elif defined(ULONGLONG_MAX) /* IRIX, AIX */
#define MP_ULONG_LONG_MAX ULONGLONG_MAX
#endif

/* We only use unsigned long for mp_digit iff long is more than 32 bits. */
#if !defined(MP_USE_UINT_DIGIT) && ULONG_MAX > MP_32BIT_MAX
typedef unsigned long mp_digit;
#define MP_DIGIT_MAX ULONG_MAX
#define MP_DIGIT_FMT "%016lX" /* printf() format for 1 digit */
#define MP_HALF_DIGIT_MAX UINT_MAX
#undef MP_NO_MP_WORD
#define MP_NO_MP_WORD 1
#undef MP_USE_LONG_DIGIT
#define MP_USE_LONG_DIGIT 1
#undef MP_USE_LONG_LONG_DIGIT

#elif !defined(MP_USE_UINT_DIGIT) && defined(MP_ULONG_LONG_MAX)
typedef unsigned long long mp_digit;
#define MP_DIGIT_MAX MP_ULONG_LONG_MAX
#define MP_DIGIT_FMT "%016llX" /* printf() format for 1 digit */
#define MP_HALF_DIGIT_MAX UINT_MAX
#undef MP_NO_MP_WORD
#define MP_NO_MP_WORD 1
#undef MP_USE_LONG_LONG_DIGIT
#define MP_USE_LONG_LONG_DIGIT 1
#undef MP_USE_LONG_DIGIT

#else
typedef unsigned int mp_digit;
#define MP_DIGIT_MAX UINT_MAX
#define MP_DIGIT_FMT "%08X" /* printf() format for 1 digit */
#define MP_HALF_DIGIT_MAX USHRT_MAX
#undef MP_USE_UINT_DIGIT
#define MP_USE_UINT_DIGIT 1
#undef MP_USE_LONG_LONG_DIGIT
#undef MP_USE_LONG_DIGIT
#endif

#if !defined(MP_NO_MP_WORD)
#if defined(MP_USE_UINT_DIGIT) && \
    (defined(MP_ULONG_LONG_MAX) || (ULONG_MAX > UINT_MAX))

#if (ULONG_MAX > UINT_MAX)
typedef unsigned long mp_word;
typedef long mp_sword;
#define MP_WORD_MAX ULONG_MAX

#else
typedef unsigned long long mp_word;
typedef long long mp_sword;
#define MP_WORD_MAX MP_ULONG_LONG_MAX
#endif

#else
#define MP_NO_MP_WORD 1
#endif
#endif /* !defined(MP_NO_MP_WORD) */

#if !defined(MP_WORD_MAX) && defined(MP_DEFINE_SMALL_WORD)
typedef unsigned int mp_word;
typedef int mp_sword;
#define MP_WORD_MAX UINT_MAX
#endif

#define MP_DIGIT_SIZE sizeof(mp_digit)
#define MP_DIGIT_BIT (CHAR_BIT * MP_DIGIT_SIZE)
#define MP_WORD_BIT (CHAR_BIT * sizeof(mp_word))
#define MP_RADIX (1 + (mp_word)MP_DIGIT_MAX)

#define MP_HALF_DIGIT_BIT (MP_DIGIT_BIT / 2)
#define MP_HALF_RADIX (1 + (mp_digit)MP_HALF_DIGIT_MAX)
/* MP_HALF_RADIX really ought to be called MP_SQRT_RADIX, but it's named
** MP_HALF_RADIX because it's the radix for MP_HALF_DIGITs, and it's
** consistent with the other _HALF_ names.
*/

/* Macros for accessing the mp_int internals           */
#define MP_SIGN(MP) ((MP)->sign)
#define MP_USED(MP) ((MP)->used)
#define MP_ALLOC(MP) ((MP)->alloc)
#define MP_DIGITS(MP) ((MP)->dp)
#define MP_DIGIT(MP, N) (MP)->dp[(N)]

/* This defines the maximum I/O base (minimum is 2)   */
#define MP_MAX_RADIX 64

typedef struct {
    mp_sign sign;  /* sign of this quantity      */
    mp_size alloc; /* how many digits allocated  */
    mp_size used;  /* how many digits used       */
    mp_digit *dp;  /* the digits themselves      */
} mp_int;

/* Default precision       */
mp_size mp_get_prec(void);
void mp_set_prec(mp_size prec);

/* Memory management       */
mp_err mp_init(mp_int *mp);
mp_err mp_init_size(mp_int *mp, mp_size prec);
mp_err mp_init_copy(mp_int *mp, const mp_int *from);
mp_err mp_copy(const mp_int *from, mp_int *to);
void mp_exch(mp_int *mp1, mp_int *mp2);
void mp_clear(mp_int *mp);
void mp_zero(mp_int *mp);
void mp_set(mp_int *mp, mp_digit d);
mp_err mp_set_int(mp_int *mp, long z);
#define mp_set_long(mp, z) mp_set_int(mp, z)
mp_err mp_set_ulong(mp_int *mp, unsigned long z);

/* Single digit arithmetic */
mp_err mp_add_d(const mp_int *a, mp_digit d, mp_int *b);
mp_err mp_sub_d(const mp_int *a, mp_digit d, mp_int *b);
mp_err mp_mul_d(const mp_int *a, mp_digit d, mp_int *b);
mp_err mp_mul_2(const mp_int *a, mp_int *c);
mp_err mp_div_d(const mp_int *a, mp_digit d, mp_int *q, mp_digit *r);
mp_err mp_div_2(const mp_int *a, mp_int *c);
mp_err mp_expt_d(const mp_int *a, mp_digit d, mp_int *c);

/* Sign manipulations      */
mp_err mp_abs(const mp_int *a, mp_int *b);
mp_err mp_neg(const mp_int *a, mp_int *b);

/* Full arithmetic         */
mp_err mp_add(const mp_int *a, const mp_int *b, mp_int *c);
mp_err mp_sub(const mp_int *a, const mp_int *b, mp_int *c);
mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c);
#if MP_SQUARE
mp_err mp_sqr(const mp_int *a, mp_int *b);
#else
#define mp_sqr(a, b) mp_mul(a, a, b)
#endif
mp_err mp_div(const mp_int *a, const mp_int *b, mp_int *q, mp_int *r);
mp_err mp_div_2d(const mp_int *a, mp_digit d, mp_int *q, mp_int *r);
mp_err mp_expt(mp_int *a, mp_int *b, mp_int *c);
mp_err mp_2expt(mp_int *a, mp_digit k);

/* Modular arithmetic      */
#if MP_MODARITH
mp_err mp_mod(const mp_int *a, const mp_int *m, mp_int *c);
mp_err mp_mod_d(const mp_int *a, mp_digit d, mp_digit *c);
mp_err mp_addmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
mp_err mp_submod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
mp_err mp_mulmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
#if MP_SQUARE
mp_err mp_sqrmod(const mp_int *a, const mp_int *m, mp_int *c);
#else
#define mp_sqrmod(a, m, c) mp_mulmod(a, a, m, c)
#endif
mp_err mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
mp_err mp_exptmod_d(const mp_int *a, mp_digit d, const mp_int *m, mp_int *c);
#endif /* MP_MODARITH */

/* Comparisons             */
int mp_cmp_z(const mp_int *a);
int mp_cmp_d(const mp_int *a, mp_digit d);
int mp_cmp(const mp_int *a, const mp_int *b);
int mp_cmp_mag(const mp_int *a, const mp_int *b);
int mp_isodd(const mp_int *a);
int mp_iseven(const mp_int *a);

/* Number theoretic        */
mp_err mp_gcd(mp_int *a, mp_int *b, mp_int *c);
mp_err mp_lcm(mp_int *a, mp_int *b, mp_int *c);
mp_err mp_xgcd(const mp_int *a, const mp_int *b, mp_int *g, mp_int *x, mp_int *y);
mp_err mp_invmod(const mp_int *a, const mp_int *m, mp_int *c);
mp_err mp_invmod_xgcd(const mp_int *a, const mp_int *m, mp_int *c);

/* Input and output        */
#if MP_IOFUNC
void mp_print(mp_int *mp, FILE *ofp);
#endif /* end MP_IOFUNC */

/* Base conversion         */
mp_err mp_read_raw(mp_int *mp, char *str, int len);
int mp_raw_size(mp_int *mp);
mp_err mp_toraw(mp_int *mp, char *str);
mp_err mp_read_radix(mp_int *mp, const char *str, int radix);
mp_err mp_read_variable_radix(mp_int *a, const char *str, int default_radix);
int mp_radix_size(mp_int *mp, int radix);
mp_err mp_toradix(mp_int *mp, char *str, int radix);
int mp_tovalue(char ch, int r);

#define mp_tobinary(M, S) mp_toradix((M), (S), 2)
#define mp_tooctal(M, S) mp_toradix((M), (S), 8)
#define mp_todecimal(M, S) mp_toradix((M), (S), 10)
#define mp_tohex(M, S) mp_toradix((M), (S), 16)

/* Error strings           */
const char *mp_strerror(mp_err ec);

/* Octet string conversion functions */
mp_err mp_read_unsigned_octets(mp_int *mp, const unsigned char *str, mp_size len);
unsigned int mp_unsigned_octet_size(const mp_int *mp);
mp_err mp_to_unsigned_octets(const mp_int *mp, unsigned char *str, mp_size maxlen);
mp_err mp_to_signed_octets(const mp_int *mp, unsigned char *str, mp_size maxlen);
mp_err mp_to_fixlen_octets(const mp_int *mp, unsigned char *str, mp_size len);

/* Miscellaneous */
mp_size mp_trailing_zeros(const mp_int *mp);
void freebl_cpuid(unsigned long op, unsigned long *eax,
                  unsigned long *ebx, unsigned long *ecx,
                  unsigned long *edx);

#define MP_CHECKOK(x)          \
    if (MP_OKAY > (res = (x))) \
    goto CLEANUP
#define MP_CHECKERR(x)         \
    if (MP_OKAY > (res = (x))) \
    goto CLEANUP

#define NEG MP_NEG
#define ZPOS MP_ZPOS
#define DIGIT_MAX MP_DIGIT_MAX
#define DIGIT_BIT MP_DIGIT_BIT
#define DIGIT_FMT MP_DIGIT_FMT
#define RADIX MP_RADIX
#define MAX_RADIX MP_MAX_RADIX
#define SIGN(MP) MP_SIGN(MP)
#define USED(MP) MP_USED(MP)
#define ALLOC(MP) MP_ALLOC(MP)
#define DIGITS(MP) MP_DIGITS(MP)
#define DIGIT(MP, N) MP_DIGIT(MP, N)

#if MP_ARGCHK == 1
#define ARGCHK(X, Y)    \
    {                   \
        if (!(X)) {     \
            return (Y); \
        }               \
    }
#elif MP_ARGCHK == 2
#include <assert.h>
#define ARGCHK(X, Y) assert(X)
#else
#define ARGCHK(X, Y) /*  */
#endif

#ifdef CT_VERIF
void mp_taint(mp_int *mp);
void mp_untaint(mp_int *mp);
#endif

SEC_END_PROTOS

#endif /* end _H_MPI_ */