diff options
Diffstat (limited to 'contrib/pgcrypto/imath.h')
| -rw-r--r-- | contrib/pgcrypto/imath.h | 445 |
1 files changed, 0 insertions, 445 deletions
diff --git a/contrib/pgcrypto/imath.h b/contrib/pgcrypto/imath.h deleted file mode 100644 index 0e1676d04e9..00000000000 --- a/contrib/pgcrypto/imath.h +++ /dev/null @@ -1,445 +0,0 @@ -/* - Name: imath.h - Purpose: Arbitrary precision integer arithmetic routines. - Author: M. J. Fromberger - - Copyright (C) 2002-2007 Michael J. Fromberger, All Rights Reserved. - - Permission is hereby granted, free of charge, to any person obtaining a copy - of this software and associated documentation files (the "Software"), to deal - in the Software without restriction, including without limitation the rights - to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - copies of the Software, and to permit persons to whom the Software is - furnished to do so, subject to the following conditions: - - The above copyright notice and this permission notice shall be included in - all copies or substantial portions of the Software. - - THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - SOFTWARE. - */ - -#ifndef IMATH_H_ -#define IMATH_H_ - -#include <limits.h> - -typedef unsigned char mp_sign; -typedef unsigned int mp_size; -typedef int mp_result; -typedef long mp_small; /* must be a signed type */ -typedef unsigned long mp_usmall; /* must be an unsigned type */ - - -/* Build with words as uint64 by default. */ -#ifdef USE_32BIT_WORDS -typedef uint16 mp_digit; -typedef uint32 mp_word; -#define MP_DIGIT_MAX (PG_UINT16_MAX * 1UL) -#define MP_WORD_MAX (PG_UINT32_MAX * 1UL) -#else -typedef uint32 mp_digit; -typedef uint64 mp_word; -#define MP_DIGIT_MAX (PG_UINT32_MAX * UINT64CONST(1)) -#define MP_WORD_MAX (PG_UINT64_MAX) -#endif - -typedef struct -{ - mp_digit single; - mp_digit *digits; - mp_size alloc; - mp_size used; - mp_sign sign; -} mpz_t , - - *mp_int; - -static inline mp_digit * -MP_DIGITS(mp_int Z) -{ - return Z->digits; -} -static inline mp_size -MP_ALLOC(mp_int Z) -{ - return Z->alloc; -} -static inline mp_size -MP_USED(mp_int Z) -{ - return Z->used; -} -static inline mp_sign -MP_SIGN(mp_int Z) -{ - return Z->sign; -} - -extern const mp_result MP_OK; -extern const mp_result MP_FALSE; -extern const mp_result MP_TRUE; -extern const mp_result MP_MEMORY; -extern const mp_result MP_RANGE; -extern const mp_result MP_UNDEF; -extern const mp_result MP_TRUNC; -extern const mp_result MP_BADARG; -extern const mp_result MP_MINERR; - -#define MP_DIGIT_BIT (sizeof(mp_digit) * CHAR_BIT) -#define MP_WORD_BIT (sizeof(mp_word) * CHAR_BIT) -#define MP_SMALL_MIN LONG_MIN -#define MP_SMALL_MAX LONG_MAX -#define MP_USMALL_MAX ULONG_MAX - -#define MP_MIN_RADIX 2 -#define MP_MAX_RADIX 36 - -/** Sets the default number of digits allocated to an `mp_int` constructed by - `mp_int_init_size()` with `prec == 0`. Allocations are rounded up to - multiples of this value. `MP_DEFAULT_PREC` is the default value. Requires - `ndigits > 0`. */ -void mp_int_default_precision(mp_size ndigits); - -/** Sets the number of digits below which multiplication will use the standard - quadratic "schoolbook" multiplcation algorithm rather than Karatsuba-Ofman. - Requires `ndigits >= sizeof(mp_word)`. */ -void mp_int_multiply_threshold(mp_size ndigits); - -/** A sign indicating a (strictly) negative value. */ -extern const mp_sign MP_NEG; - -/** A sign indicating a zero or positive value. */ -extern const mp_sign MP_ZPOS; - -/** Reports whether `z` is odd, having remainder 1 when divided by 2. */ -static inline bool -mp_int_is_odd(mp_int z) -{ - return (z->digits[0] & 1) != 0; -} - -/** Reports whether `z` is even, having remainder 0 when divided by 2. */ -static inline bool -mp_int_is_even(mp_int z) -{ - return (z->digits[0] & 1) == 0; -} - -/** Initializes `z` with 1-digit precision and sets it to zero. This function - cannot fail unless `z == NULL`. */ -mp_result mp_int_init(mp_int z); - -/** Allocates a fresh zero-valued `mpz_t` on the heap, returning NULL in case - of error. The only possible error is out-of-memory. */ -mp_int mp_int_alloc(void); - -/** Initializes `z` with at least `prec` digits of storage, and sets it to - zero. If `prec` is zero, the default precision is used. In either case the - size is rounded up to the nearest multiple of the word size. */ -mp_result mp_int_init_size(mp_int z, mp_size prec); - -/** Initializes `z` to be a copy of an already-initialized value in `old`. The - new copy does not share storage with the original. */ -mp_result mp_int_init_copy(mp_int z, mp_int old); - -/** Initializes `z` to the specified signed `value` at default precision. */ -mp_result mp_int_init_value(mp_int z, mp_small value); - -/** Initializes `z` to the specified unsigned `value` at default precision. */ -mp_result mp_int_init_uvalue(mp_int z, mp_usmall uvalue); - -/** Sets `z` to the value of the specified signed `value`. */ -mp_result mp_int_set_value(mp_int z, mp_small value); - -/** Sets `z` to the value of the specified unsigned `value`. */ -mp_result mp_int_set_uvalue(mp_int z, mp_usmall uvalue); - -/** Releases the storage used by `z`. */ -void mp_int_clear(mp_int z); - -/** Releases the storage used by `z` and also `z` itself. - This should only be used for `z` allocated by `mp_int_alloc()`. */ -void mp_int_free(mp_int z); - -/** Replaces the value of `c` with a copy of the value of `a`. No new memory is - allocated unless `a` has more significant digits than `c` has allocated. */ -mp_result mp_int_copy(mp_int a, mp_int c); - -/** Swaps the values and storage between `a` and `c`. */ -void mp_int_swap(mp_int a, mp_int c); - -/** Sets `z` to zero. The allocated storage of `z` is not changed. */ -void mp_int_zero(mp_int z); - -/** Sets `c` to the absolute value of `a`. */ -mp_result mp_int_abs(mp_int a, mp_int c); - -/** Sets `c` to the additive inverse (negation) of `a`. */ -mp_result mp_int_neg(mp_int a, mp_int c); - -/** Sets `c` to the sum of `a` and `b`. */ -mp_result mp_int_add(mp_int a, mp_int b, mp_int c); - -/** Sets `c` to the sum of `a` and `value`. */ -mp_result mp_int_add_value(mp_int a, mp_small value, mp_int c); - -/** Sets `c` to the difference of `a` less `b`. */ -mp_result mp_int_sub(mp_int a, mp_int b, mp_int c); - -/** Sets `c` to the difference of `a` less `value`. */ -mp_result mp_int_sub_value(mp_int a, mp_small value, mp_int c); - -/** Sets `c` to the product of `a` and `b`. */ -mp_result mp_int_mul(mp_int a, mp_int b, mp_int c); - -/** Sets `c` to the product of `a` and `value`. */ -mp_result mp_int_mul_value(mp_int a, mp_small value, mp_int c); - -/** Sets `c` to the product of `a` and `2^p2`. Requires `p2 >= 0`. */ -mp_result mp_int_mul_pow2(mp_int a, mp_small p2, mp_int c); - -/** Sets `c` to the square of `a`. */ -mp_result mp_int_sqr(mp_int a, mp_int c); - -/** Sets `q` and `r` to the quotent and remainder of `a / b`. Division by - powers of 2 is detected and handled efficiently. The remainder is pinned - to `0 <= r < b`. - - Either of `q` or `r` may be NULL, but not both, and `q` and `r` may not - point to the same value. */ -mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r); - -/** Sets `q` and `*r` to the quotent and remainder of `a / value`. Division by - powers of 2 is detected and handled efficiently. The remainder is pinned to - `0 <= *r < b`. Either of `q` or `r` may be NULL. */ -mp_result mp_int_div_value(mp_int a, mp_small value, mp_int q, mp_small *r); - -/** Sets `q` and `r` to the quotient and remainder of `a / 2^p2`. This is a - special case for division by powers of two that is more efficient than - using ordinary division. Note that `mp_int_div()` will automatically handle - this case, this function is for cases where you have only the exponent. */ -mp_result mp_int_div_pow2(mp_int a, mp_small p2, mp_int q, mp_int r); - -/** Sets `c` to the remainder of `a / m`. - The remainder is pinned to `0 <= c < m`. */ -mp_result mp_int_mod(mp_int a, mp_int m, mp_int c); - -/** Sets `c` to the value of `a` raised to the `b` power. - It returns `MP_RANGE` if `b < 0`. */ -mp_result mp_int_expt(mp_int a, mp_small b, mp_int c); - -/** Sets `c` to the value of `a` raised to the `b` power. - It returns `MP_RANGE` if `b < 0`. */ -mp_result mp_int_expt_value(mp_small a, mp_small b, mp_int c); - -/** Sets `c` to the value of `a` raised to the `b` power. - It returns `MP_RANGE`) if `b < 0`. */ -mp_result mp_int_expt_full(mp_int a, mp_int b, mp_int c); - -/** Sets `*r` to the remainder of `a / value`. - The remainder is pinned to `0 <= r < value`. */ -static inline -mp_result -mp_int_mod_value(mp_int a, mp_small value, mp_small *r) -{ - return mp_int_div_value(a, value, 0, r); -} - -/** Returns the comparator of `a` and `b`. */ -int mp_int_compare(mp_int a, mp_int b); - -/** Returns the comparator of the magnitudes of `a` and `b`, disregarding their - signs. Neither `a` nor `b` is modified by the comparison. */ -int mp_int_compare_unsigned(mp_int a, mp_int b); - -/** Returns the comparator of `z` and zero. */ -int mp_int_compare_zero(mp_int z); - -/** Returns the comparator of `z` and the signed value `v`. */ -int mp_int_compare_value(mp_int z, mp_small v); - -/** Returns the comparator of `z` and the unsigned value `uv`. */ -int mp_int_compare_uvalue(mp_int z, mp_usmall uv); - -/** Reports whether `a` is divisible by `v`. */ -bool mp_int_divisible_value(mp_int a, mp_small v); - -/** Returns `k >= 0` such that `z` is `2^k`, if such a `k` exists. If no such - `k` exists, the function returns -1. */ -int mp_int_is_pow2(mp_int z); - -/** Sets `c` to the value of `a` raised to the `b` power, reduced modulo `m`. - It returns `MP_RANGE` if `b < 0` or `MP_UNDEF` if `m == 0`. */ -mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, mp_int c); - -/** Sets `c` to the value of `a` raised to the `value` power, modulo `m`. - It returns `MP_RANGE` if `value < 0` or `MP_UNDEF` if `m == 0`. */ -mp_result mp_int_exptmod_evalue(mp_int a, mp_small value, mp_int m, mp_int c); - -/** Sets `c` to the value of `value` raised to the `b` power, modulo `m`. - It returns `MP_RANGE` if `b < 0` or `MP_UNDEF` if `m == 0`. */ -mp_result mp_int_exptmod_bvalue(mp_small value, mp_int b, mp_int m, mp_int c); - -/** Sets `c` to the value of `a` raised to the `b` power, reduced modulo `m`, - given a precomputed reduction constant `mu` defined for Barrett's modular - reduction algorithm. - - It returns `MP_RANGE` if `b < 0` or `MP_UNDEF` if `m == 0`. */ -mp_result mp_int_exptmod_known(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c); - -/** Sets `c` to the reduction constant for Barrett reduction by modulus `m`. - Requires that `c` and `m` point to distinct locations. */ -mp_result mp_int_redux_const(mp_int m, mp_int c); - -/** Sets `c` to the multiplicative inverse of `a` modulo `m`, if it exists. - The least non-negative representative of the congruence class is computed. - - It returns `MP_UNDEF` if the inverse does not exist, or `MP_RANGE` if `a == - 0` or `m <= 0`. */ -mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c); - -/** Sets `c` to the greatest common divisor of `a` and `b`. - - It returns `MP_UNDEF` if the GCD is undefined, such as for example if `a` - and `b` are both zero. */ -mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c); - -/** Sets `c` to the greatest common divisor of `a` and `b`, and sets `x` and - `y` to values satisfying Bezout's identity `gcd(a, b) = ax + by`. - - It returns `MP_UNDEF` if the GCD is undefined, such as for example if `a` - and `b` are both zero. */ -mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, mp_int x, mp_int y); - -/** Sets `c` to the least common multiple of `a` and `b`. - - It returns `MP_UNDEF` if the LCM is undefined, such as for example if `a` - and `b` are both zero. */ -mp_result mp_int_lcm(mp_int a, mp_int b, mp_int c); - -/** Sets `c` to the greatest integer not less than the `b`th root of `a`, - using Newton's root-finding algorithm. - It returns `MP_UNDEF` if `a < 0` and `b` is even. */ -mp_result mp_int_root(mp_int a, mp_small b, mp_int c); - -/** Sets `c` to the greatest integer not less than the square root of `a`. - This is a special case of `mp_int_root()`. */ -static inline -mp_result -mp_int_sqrt(mp_int a, mp_int c) -{ - return mp_int_root(a, 2, c); -} - -/** Returns `MP_OK` if `z` is representable as `mp_small`, else `MP_RANGE`. - If `out` is not NULL, `*out` is set to the value of `z` when `MP_OK`. */ -mp_result mp_int_to_int(mp_int z, mp_small *out); - -/** Returns `MP_OK` if `z` is representable as `mp_usmall`, or `MP_RANGE`. - If `out` is not NULL, `*out` is set to the value of `z` when `MP_OK`. */ -mp_result mp_int_to_uint(mp_int z, mp_usmall *out); - -/** Converts `z` to a zero-terminated string of characters in the specified - `radix`, writing at most `limit` characters to `str` including the - terminating NUL value. A leading `-` is used to indicate a negative value. - - Returns `MP_TRUNC` if `limit` was to small to write all of `z`. - Requires `MP_MIN_RADIX <= radix <= MP_MAX_RADIX`. */ -mp_result mp_int_to_string(mp_int z, mp_size radix, char *str, int limit); - -/** Reports the minimum number of characters required to represent `z` as a - zero-terminated string in the given `radix`. - Requires `MP_MIN_RADIX <= radix <= MP_MAX_RADIX`. */ -mp_result mp_int_string_len(mp_int z, mp_size radix); - -/** Reads a string of ASCII digits in the specified `radix` from the zero - terminated `str` provided into `z`. For values of `radix > 10`, the letters - `A`..`Z` or `a`..`z` are accepted. Letters are interpreted without respect - to case. - - Leading whitespace is ignored, and a leading `+` or `-` is interpreted as a - sign flag. Processing stops when a NUL or any other character out of range - for a digit in the given radix is encountered. - - If the whole string was consumed, `MP_OK` is returned; otherwise - `MP_TRUNC`. is returned. - - Requires `MP_MIN_RADIX <= radix <= MP_MAX_RADIX`. */ -mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str); - -/** Reads a string of ASCII digits in the specified `radix` from the zero - terminated `str` provided into `z`. For values of `radix > 10`, the letters - `A`..`Z` or `a`..`z` are accepted. Letters are interpreted without respect - to case. - - Leading whitespace is ignored, and a leading `+` or `-` is interpreted as a - sign flag. Processing stops when a NUL or any other character out of range - for a digit in the given radix is encountered. - - If the whole string was consumed, `MP_OK` is returned; otherwise - `MP_TRUNC`. is returned. If `end` is not NULL, `*end` is set to point to - the first unconsumed byte of the input string (the NUL byte if the whole - string was consumed). This emulates the behavior of the standard C - `strtol()` function. - - Requires `MP_MIN_RADIX <= radix <= MP_MAX_RADIX`. */ -mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str, char **end); - -/** Returns the number of significant bits in `z`. */ -mp_result mp_int_count_bits(mp_int z); - -/** Converts `z` to 2's complement binary, writing at most `limit` bytes into - the given `buf`. Returns `MP_TRUNC` if the buffer limit was too small to - contain the whole value. If this occurs, the contents of buf will be - effectively garbage, as the function uses the buffer as scratch space. - - The binary representation of `z` is in base-256 with digits ordered from - most significant to least significant (network byte ordering). The - high-order bit of the first byte is set for negative values, clear for - non-negative values. - - As a result, non-negative values will be padded with a leading zero byte if - the high-order byte of the base-256 magnitude is set. This extra byte is - accounted for by the `mp_int_binary_len()` function. */ -mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit); - -/** Reads a 2's complement binary value from `buf` into `z`, where `len` is the - length of the buffer. The contents of `buf` may be overwritten during - processing, although they will be restored when the function returns. */ -mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len); - -/** Returns the number of bytes to represent `z` in 2's complement binary. */ -mp_result mp_int_binary_len(mp_int z); - -/** Converts the magnitude of `z` to unsigned binary, writing at most `limit` - bytes into the given `buf`. The sign of `z` is ignored, but `z` is not - modified. Returns `MP_TRUNC` if the buffer limit was too small to contain - the whole value. If this occurs, the contents of `buf` will be effectively - garbage, as the function uses the buffer as scratch space during - conversion. - - The binary representation of `z` is in base-256 with digits ordered from - most significant to least significant (network byte ordering). */ -mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit); - -/** Reads an unsigned binary value from `buf` into `z`, where `len` is the - length of the buffer. The contents of `buf` are not modified during - processing. */ -mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len); - -/** Returns the number of bytes required to represent `z` as an unsigned binary - value in base 256. */ -mp_result mp_int_unsigned_len(mp_int z); - -/** Returns a pointer to a brief, human-readable, zero-terminated string - describing `res`. The returned string is statically allocated and must not - be freed by the caller. */ -const char *mp_error_string(mp_result res); - -#endif /* end IMATH_H_ */ |