gmpy2_hash.c
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 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 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 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 return _PyHASH_NAN; 149 } 150 } 151 152 /* Calculate the number of limbs in the mantissa. */ 153 msize = (f->_mpfr_prec + mp_bits_per_limb - 1) / mp_bits_per_limb; 154 155 /* Calculate the hash of the mantissa. */ 156 if (mpfr_sgn(f) > 0) { 157 hash = mpn_mod_1(f->_mpfr_d, msize, _PyHASH_MODULUS); 158 sign = 1; 159 } 160 else if (mpfr_sgn(f) < 0) { 161 hash = mpn_mod_1(f->_mpfr_d, msize, _PyHASH_MODULUS); 162 sign = -1; 163 } 164 else { 165 return 0; 166 } 167 168 /* Calculate the final hash. */ 169 exp = f->_mpfr_exp - (msize * mp_bits_per_limb); 170 exp = exp >= 0 ? exp % _PyHASH_BITS : _PyHASH_BITS-1-((-1-exp) % _PyHASH_BITS); 171 hash = ((hash << exp) & _PyHASH_MODULUS) | hash >> (_PyHASH_BITS - exp); 172 173 hash *= sign; 174 if (hash == (Py_uhash_t)(-1)) { 175 hash = (Py_uhash_t)(-2); 176 } 177 return (Py_hash_t)hash; 178 #else 179 double temp; 180 CTXT_Object *context = NULL; 181 182 CHECK_CONTEXT(context); 183 temp = mpfr_get_d(f, GET_MPFR_ROUND(context)); 184 return _Py_HashDouble(temp); 185 #endif 186 } 187 188 static Py_hash_t 189 GMPy_MPFR_Hash_Slot(MPFR_Object *self) 190 { 191 if (self->hash_cache == -1) { 192 self->hash_cache = _mpfr_hash(self->f); 193 } 194 return self->hash_cache; 195 } 196 197 static Py_hash_t 198 GMPy_MPC_Hash_Slot(MPC_Object *self) 199 { 200 Py_uhash_t hashreal, hashimag, combined; 201 202 if (self->hash_cache != -1) { 203 return self->hash_cache; 204 } 205 206 hashreal = (Py_uhash_t)_mpfr_hash(mpc_realref(self->c)); 207 if (hashreal == (Py_uhash_t)(-1)) { 208 return -1; 209 } 210 hashimag = (Py_uhash_t)_mpfr_hash(mpc_imagref(self->c)); 211 if (hashimag == (Py_uhash_t)(-1)) { 212 return -1; 213 } 214 combined = hashreal + _PyHASH_IMAG * hashimag; 215 if (combined == (Py_uhash_t)(-1)) { 216 combined = (Py_uhash_t)(-2); 217 } 218 self->hash_cache = combined; 219 return (Py_hash_t)combined; 220 } 221