1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2 * gmpy2_hash.c *
3 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
4 * Python interface to the GMP or MPIR, MPFR, and MPC multiple precision *
5 * libraries. *
6 * *
7 * Copyright 2000 - 2009 Alex Martelli *
8 * *
9 * Copyright 2008 - 2021 Case Van Horsen *
10 * *
11 * This file is part of GMPY2. *
12 * *
13 * GMPY2 is free software: you can redistribute it and/or modify it under *
14 * the terms of the GNU Lesser General Public License as published by the *
15 * Free Software Foundation, either version 3 of the License, or (at your *
16 * option) any later version. *
17 * *
18 * GMPY2 is distributed in the hope that it will be useful, but WITHOUT *
19 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or *
20 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public *
21 * License for more details. *
22 * *
23 * You should have received a copy of the GNU Lesser General Public *
24 * License along with GMPY2; if not, see <http://www.gnu.org/licenses/> *
25 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
26
27 static Py_hash_t
GMPy_MPZ_Hash_Slot(MPZ_Object * self)28 GMPy_MPZ_Hash_Slot(MPZ_Object *self)
29 {
30 #ifdef _PyHASH_MODULUS
31 Py_hash_t hash;
32
33 if (self->hash_cache != -1) {
34 return self->hash_cache;
35 }
36
37 hash = (Py_hash_t)mpn_mod_1(self->z->_mp_d, mpz_size(self->z), _PyHASH_MODULUS);
38 if (mpz_sgn(self->z) < 0) {
39 hash = -hash;
40 }
41 if (hash == -1) {
42 hash = -2;
43 }
44 return (self->hash_cache = hash);
45 #else
46 unsigned long x;
47
48 if (self->hash_cache != -1) {
49 return self->hash_cache;
50 }
51
52 x = (unsigned long)mpn_mod_1(self->z->_mp_d, mpz_size(self->z), ULONG_MAX);
53 if (mpz_sgn(self->z) < 0) {
54 x = x * -1;
55 }
56 if (x == (unsigned long)-1) {
57 x = (unsigned long)-2;
58 }
59 return (self->hash_cache = (long)x);
60 #endif
61 }
62
63 static Py_hash_t
GMPy_MPQ_Hash_Slot(MPQ_Object * self)64 GMPy_MPQ_Hash_Slot(MPQ_Object *self)
65 {
66 #ifdef _PyHASH_MODULUS
67 Py_hash_t hash = 0;
68 mpz_t temp, temp1, mask;
69
70 if (self->hash_cache != -1) {
71 return self->hash_cache;
72 }
73
74 mpz_init(temp);
75 mpz_init(temp1);
76 mpz_init(mask);
77 mpz_set_si(mask, 1);
78 mpz_mul_2exp(mask, mask, _PyHASH_BITS);
79 mpz_sub_ui(mask, mask, 1);
80
81 if (!mpz_invert(temp, mpq_denref(self->q), mask)) {
82 mpz_clear(temp);
83 mpz_clear(temp1);
84 mpz_clear(mask);
85 hash = _PyHASH_INF;
86 if (mpz_sgn(mpq_numref(self->q)) < 0) {
87 hash = -hash;
88 }
89 self->hash_cache = hash;
90 return hash;
91 }
92 mpz_set(temp1, mask);
93 mpz_sub_ui(temp1, temp1, 2);
94 mpz_powm(temp, mpq_denref(self->q), temp1, mask);
95
96 mpz_tdiv_r(temp1, mpq_numref(self->q), mask);
97 mpz_mul(temp, temp, temp1);
98 hash = (Py_hash_t)mpn_mod_1(temp->_mp_d, mpz_size(temp), _PyHASH_MODULUS);
99
100 if (mpz_sgn(mpq_numref(self->q)) < 0) {
101 hash = -hash;
102 }
103 if (hash == -1) {
104 hash = -2;
105 }
106 mpz_clear(temp);
107 mpz_clear(temp1);
108 mpz_clear(mask);
109 self->hash_cache = hash;
110 return hash;
111 #else
112 PyObject *temp;
113
114 if (self->hash_cache != -1) {
115 return self->hash_cache;
116 }
117
118 if (!(temp = GMPy_PyFloat_From_MPQ(self, NULL))) {
119 SYSTEM_ERROR("Could not convert 'mpq' to float.");
120 return -1;
121 }
122 self->hash_cache = PyObject_Hash(temp);
123 Py_DECREF(temp);
124 return self->hash_cache;
125 #endif
126 }
127
128 static Py_hash_t
_mpfr_hash(mpfr_t f)129 _mpfr_hash(mpfr_t f)
130 {
131 #ifdef _PyHASH_MODULUS
132 Py_uhash_t hash = 0;
133 Py_ssize_t exp;
134 size_t msize;
135 int sign;
136
137 /* Handle special cases first */
138 if (!mpfr_number_p(f)) {
139 if (mpfr_inf_p(f)) {
140 if (mpfr_sgn(f) > 0) {
141 return _PyHASH_INF;
142 }
143 else {
144 return -_PyHASH_INF;
145 }
146 }
147 else {
148 #if PY_VERSION_HEX >= 0x030A00A0
149 // Python 3.10
150 return _Py_HashPointer(f);
151 #else
152 return _PyHASH_NAN;
153 #endif
154 }
155 }
156
157 /* Calculate the number of limbs in the mantissa. */
158 msize = (f->_mpfr_prec + mp_bits_per_limb - 1) / mp_bits_per_limb;
159
160 /* Calculate the hash of the mantissa. */
161 if (mpfr_sgn(f) > 0) {
162 hash = mpn_mod_1(f->_mpfr_d, msize, _PyHASH_MODULUS);
163 sign = 1;
164 }
165 else if (mpfr_sgn(f) < 0) {
166 hash = mpn_mod_1(f->_mpfr_d, msize, _PyHASH_MODULUS);
167 sign = -1;
168 }
169 else {
170 return 0;
171 }
172
173 /* Calculate the final hash. */
174 exp = f->_mpfr_exp - (msize * mp_bits_per_limb);
175 exp = exp >= 0 ? exp % _PyHASH_BITS : _PyHASH_BITS-1-((-1-exp) % _PyHASH_BITS);
176 hash = ((hash << exp) & _PyHASH_MODULUS) | hash >> (_PyHASH_BITS - exp);
177
178 hash *= sign;
179 if (hash == (Py_uhash_t)(-1)) {
180 hash = (Py_uhash_t)(-2);
181 }
182 return (Py_hash_t)hash;
183 #else
184 double temp;
185 CTXT_Object *context = NULL;
186
187 CHECK_CONTEXT(context);
188 temp = mpfr_get_d(f, GET_MPFR_ROUND(context));
189 return _Py_HashDouble(temp);
190 #endif
191 }
192
193 static Py_hash_t
GMPy_MPFR_Hash_Slot(MPFR_Object * self)194 GMPy_MPFR_Hash_Slot(MPFR_Object *self)
195 {
196 if (self->hash_cache == -1) {
197 self->hash_cache = _mpfr_hash(self->f);
198 }
199 return self->hash_cache;
200 }
201
202 static Py_hash_t
GMPy_MPC_Hash_Slot(MPC_Object * self)203 GMPy_MPC_Hash_Slot(MPC_Object *self)
204 {
205 Py_uhash_t hashreal, hashimag, combined;
206
207 if (self->hash_cache != -1) {
208 return self->hash_cache;
209 }
210
211 hashreal = (Py_uhash_t)_mpfr_hash(mpc_realref(self->c));
212 if (hashreal == (Py_uhash_t)(-1)) {
213 return -1;
214 }
215 hashimag = (Py_uhash_t)_mpfr_hash(mpc_imagref(self->c));
216 if (hashimag == (Py_uhash_t)(-1)) {
217 return -1;
218 }
219 combined = hashreal + _PyHASH_IMAG * hashimag;
220 if (combined == (Py_uhash_t)(-1)) {
221 combined = (Py_uhash_t)(-2);
222 }
223 self->hash_cache = combined;
224 return (Py_hash_t)combined;
225 }
226
227