Branch data Line data Source code
1 : : /*
2 : : * This file is part of the MicroPython project, http://micropython.org/
3 : : *
4 : : * The MIT License (MIT)
5 : : *
6 : : * Copyright (c) 2013, 2014 Damien P. George
7 : : *
8 : : * Permission is hereby granted, free of charge, to any person obtaining a copy
9 : : * of this software and associated documentation files (the "Software"), to deal
10 : : * in the Software without restriction, including without limitation the rights
11 : : * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 : : * copies of the Software, and to permit persons to whom the Software is
13 : : * furnished to do so, subject to the following conditions:
14 : : *
15 : : * The above copyright notice and this permission notice shall be included in
16 : : * all copies or substantial portions of the Software.
17 : : *
18 : : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 : : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 : : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 : : * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 : : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 : : * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
24 : : * THE SOFTWARE.
25 : : */
26 : : #ifndef MICROPY_INCLUDED_PY_MPZ_H
27 : : #define MICROPY_INCLUDED_PY_MPZ_H
28 : :
29 : : #include <stdint.h>
30 : :
31 : : #include "py/mpconfig.h"
32 : : #include "py/misc.h"
33 : :
34 : : // This mpz module implements arbitrary precision integers.
35 : : //
36 : : // The storage for each digit is defined by mpz_dig_t. The actual number of
37 : : // bits in mpz_dig_t that are used is defined by MPZ_DIG_SIZE. The machine must
38 : : // also provide a type that is twice as wide as mpz_dig_t, in both signed and
39 : : // unsigned versions.
40 : : //
41 : : // MPZ_DIG_SIZE can be between 4 and 8*sizeof(mpz_dig_t), but it makes most
42 : : // sense to have it as large as possible. If MPZ_DIG_SIZE is not already
43 : : // defined then it is auto-detected below, depending on the machine. The types
44 : : // are then set based on the value of MPZ_DIG_SIZE (although they can be freely
45 : : // changed so long as the constraints mentioned above are met).
46 : :
47 : : #ifndef MPZ_DIG_SIZE
48 : : #if defined(__x86_64__) || defined(_WIN64)
49 : : // 64-bit machine, using 32-bit storage for digits
50 : : #define MPZ_DIG_SIZE (32)
51 : : #else
52 : : // default: 32-bit machine, using 16-bit storage for digits
53 : : #define MPZ_DIG_SIZE (16)
54 : : #endif
55 : : #endif
56 : :
57 : : #if MPZ_DIG_SIZE > 16
58 : : #define MPZ_DBL_DIG_SIZE (64)
59 : : typedef uint32_t mpz_dig_t;
60 : : typedef uint64_t mpz_dbl_dig_t;
61 : : typedef int64_t mpz_dbl_dig_signed_t;
62 : : #elif MPZ_DIG_SIZE > 8
63 : : #define MPZ_DBL_DIG_SIZE (32)
64 : : typedef uint16_t mpz_dig_t;
65 : : typedef uint32_t mpz_dbl_dig_t;
66 : : typedef int32_t mpz_dbl_dig_signed_t;
67 : : #elif MPZ_DIG_SIZE > 4
68 : : #define MPZ_DBL_DIG_SIZE (16)
69 : : typedef uint8_t mpz_dig_t;
70 : : typedef uint16_t mpz_dbl_dig_t;
71 : : typedef int16_t mpz_dbl_dig_signed_t;
72 : : #else
73 : : #define MPZ_DBL_DIG_SIZE (8)
74 : : typedef uint8_t mpz_dig_t;
75 : : typedef uint8_t mpz_dbl_dig_t;
76 : : typedef int8_t mpz_dbl_dig_signed_t;
77 : : #endif
78 : :
79 : : #ifdef _WIN64
80 : : #ifdef __MINGW32__
81 : : #define MPZ_LONG_1 1LL
82 : : #else
83 : : #define MPZ_LONG_1 1i64
84 : : #endif
85 : : #else
86 : : #define MPZ_LONG_1 1L
87 : : #endif
88 : :
89 : : // these define the maximum storage needed to hold an int or long long
90 : : #define MPZ_NUM_DIG_FOR_INT ((sizeof(mp_int_t) * 8 + MPZ_DIG_SIZE - 1) / MPZ_DIG_SIZE)
91 : : #define MPZ_NUM_DIG_FOR_LL ((sizeof(long long) * 8 + MPZ_DIG_SIZE - 1) / MPZ_DIG_SIZE)
92 : :
93 : : typedef struct _mpz_t {
94 : : // Zero has neg=0, len=0. Negative zero is not allowed.
95 : : size_t neg : 1;
96 : : size_t fixed_dig : 1; // flag, 'dig' buffer cannot be reallocated
97 : : size_t alloc : (8 * sizeof(size_t) - 2); // number of entries allocated in 'dig'
98 : : size_t len; // number of entries used in 'dig'
99 : : mpz_dig_t *dig;
100 : : } mpz_t;
101 : :
102 : : // convenience macro to declare an mpz with a digit array from the stack, initialised by an integer
103 : : #define MPZ_CONST_INT(z, val) mpz_t z; mpz_dig_t z##_digits[MPZ_NUM_DIG_FOR_INT]; mpz_init_fixed_from_int(&z, z_digits, MPZ_NUM_DIG_FOR_INT, val);
104 : :
105 : : void mpz_init_zero(mpz_t *z);
106 : : void mpz_init_from_int(mpz_t *z, mp_int_t val);
107 : : void mpz_init_fixed_from_int(mpz_t *z, mpz_dig_t *dig, size_t dig_alloc, mp_int_t val);
108 : : void mpz_deinit(mpz_t *z);
109 : :
110 : : void mpz_set(mpz_t *dest, const mpz_t *src);
111 : : void mpz_set_from_int(mpz_t *z, mp_int_t src);
112 : : void mpz_set_from_ll(mpz_t *z, long long i, bool is_signed);
113 : : #if MICROPY_PY_BUILTINS_FLOAT
114 : : void mpz_set_from_float(mpz_t *z, mp_float_t src);
115 : : #endif
116 : : size_t mpz_set_from_str(mpz_t *z, const char *str, size_t len, bool neg, unsigned int base);
117 : : void mpz_set_from_bytes(mpz_t *z, bool big_endian, size_t len, const byte *buf);
118 : :
119 : 40092 : static inline bool mpz_is_zero(const mpz_t *z) {
120 [ + + + + : 40092 : return z->len == 0;
+ + + + -
+ ]
121 : : }
122 : 386 : static inline bool mpz_is_neg(const mpz_t *z) {
123 [ + + ]: 386 : return z->neg != 0;
124 : : }
125 : : int mpz_cmp(const mpz_t *lhs, const mpz_t *rhs);
126 : :
127 : : void mpz_abs_inpl(mpz_t *dest, const mpz_t *z);
128 : : void mpz_neg_inpl(mpz_t *dest, const mpz_t *z);
129 : : void mpz_not_inpl(mpz_t *dest, const mpz_t *z);
130 : : void mpz_shl_inpl(mpz_t *dest, const mpz_t *lhs, mp_uint_t rhs);
131 : : void mpz_shr_inpl(mpz_t *dest, const mpz_t *lhs, mp_uint_t rhs);
132 : : void mpz_add_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
133 : : void mpz_sub_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
134 : : void mpz_mul_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
135 : : void mpz_pow_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
136 : : void mpz_pow3_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs, const mpz_t *mod);
137 : : void mpz_and_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
138 : : void mpz_or_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
139 : : void mpz_xor_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
140 : : void mpz_divmod_inpl(mpz_t *dest_quo, mpz_t *dest_rem, const mpz_t *lhs, const mpz_t *rhs);
141 : :
142 : 22670 : static inline size_t mpz_max_num_bits(const mpz_t *z) {
143 : 22670 : return z->len * MPZ_DIG_SIZE;
144 : : }
145 : : mp_int_t mpz_hash(const mpz_t *z);
146 : : bool mpz_as_int_checked(const mpz_t *z, mp_int_t *value);
147 : : bool mpz_as_uint_checked(const mpz_t *z, mp_uint_t *value);
148 : : // Returns true if 'z' fit into 'len' bytes of 'buf' without overflowing, 'buf' is truncated otherwise.
149 : : bool mpz_as_bytes(const mpz_t *z, bool big_endian, bool as_signed, size_t len, byte *buf);
150 : : #if MICROPY_PY_BUILTINS_FLOAT
151 : : mp_float_t mpz_as_float(const mpz_t *z);
152 : : #endif
153 : : size_t mpz_as_str_inpl(const mpz_t *z, unsigned int base, const char *prefix, char base_char, char comma, char *str);
154 : :
155 : : #endif // MICROPY_INCLUDED_PY_MPZ_H
|
