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)
59typedef uint32_t mpz_dig_t;
60typedef uint64_t mpz_dbl_dig_t;
61typedef int64_t mpz_dbl_dig_signed_t;
62#elif MPZ_DIG_SIZE > 8
63#define MPZ_DBL_DIG_SIZE (32)
64typedef uint16_t mpz_dig_t;
65typedef uint32_t mpz_dbl_dig_t;
66typedef int32_t mpz_dbl_dig_signed_t;
67#elif MPZ_DIG_SIZE > 4
68#define MPZ_DBL_DIG_SIZE (16)
69typedef uint8_t mpz_dig_t;
70typedef uint16_t mpz_dbl_dig_t;
71typedef int16_t mpz_dbl_dig_signed_t;
72#else
73#define MPZ_DBL_DIG_SIZE (8)
74typedef uint8_t mpz_dig_t;
75typedef uint8_t mpz_dbl_dig_t;
76typedef 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
93typedef struct _mpz_t {
94 size_t neg : 1;
95 size_t fixed_dig : 1;
96 size_t alloc : (8 * sizeof(size_t) - 2);
97 size_t len;
98 mpz_dig_t *dig;
99} mpz_t;
100
101// convenience macro to declare an mpz with a digit array from the stack, initialised by an integer
102#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);
103
104void mpz_init_zero(mpz_t *z);
105void mpz_init_from_int(mpz_t *z, mp_int_t val);
106void mpz_init_fixed_from_int(mpz_t *z, mpz_dig_t *dig, size_t dig_alloc, mp_int_t val);
107void mpz_deinit(mpz_t *z);
108
109void mpz_set(mpz_t *dest, const mpz_t *src);
110void mpz_set_from_int(mpz_t *z, mp_int_t src);
111void mpz_set_from_ll(mpz_t *z, long long i, bool is_signed);
112#if MICROPY_PY_BUILTINS_FLOAT
113void mpz_set_from_float(mpz_t *z, mp_float_t src);
114#endif
115size_t mpz_set_from_str(mpz_t *z, const char *str, size_t len, bool neg, unsigned int base);
116void mpz_set_from_bytes(mpz_t *z, bool big_endian, size_t len, const byte *buf);
117
118static inline bool mpz_is_zero(const mpz_t *z) {
119 return z->len == 0;
120}
121static inline bool mpz_is_neg(const mpz_t *z) {
122 return z->len != 0 && z->neg != 0;
123}
124int mpz_cmp(const mpz_t *lhs, const mpz_t *rhs);
125
126void mpz_abs_inpl(mpz_t *dest, const mpz_t *z);
127void mpz_neg_inpl(mpz_t *dest, const mpz_t *z);
128void mpz_not_inpl(mpz_t *dest, const mpz_t *z);
129void mpz_shl_inpl(mpz_t *dest, const mpz_t *lhs, mp_uint_t rhs);
130void mpz_shr_inpl(mpz_t *dest, const mpz_t *lhs, mp_uint_t rhs);
131void mpz_add_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
132void mpz_sub_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
133void mpz_mul_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
134void mpz_pow_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
135void mpz_pow3_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs, const mpz_t *mod);
136void mpz_and_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
137void mpz_or_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
138void mpz_xor_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
139void mpz_divmod_inpl(mpz_t *dest_quo, mpz_t *dest_rem, const mpz_t *lhs, const mpz_t *rhs);
140
141static inline size_t mpz_max_num_bits(const mpz_t *z) {
142 return z->len * MPZ_DIG_SIZE;
143}
144mp_int_t mpz_hash(const mpz_t *z);
145bool mpz_as_int_checked(const mpz_t *z, mp_int_t *value);
146bool mpz_as_uint_checked(const mpz_t *z, mp_uint_t *value);
147void mpz_as_bytes(const mpz_t *z, bool big_endian, size_t len, byte *buf);
148#if MICROPY_PY_BUILTINS_FLOAT
149mp_float_t mpz_as_float(const mpz_t *z);
150#endif
151size_t mpz_as_str_inpl(const mpz_t *z, unsigned int base, const char *prefix, char base_char, char comma, char *str);
152
153#endif // MICROPY_INCLUDED_PY_MPZ_H
154