cpython-lru_cache-weakref: Python/pyhash.c annotate

annotate Python/pyhash.c @ 87690:66c1c9f32567 default tip

Add use_weakref option to functools.lru_cache The use_weakref option makes lru_cache create weak references to the function arguments when creating the cache key, which prevents them from staying in the memory forever even after all other references to them are gone. This is a proof of concept for http://bugs.python.org/issue19859

author	Radomir Dopieralski <devel@sheep.art.pl>
date	Tue, 03 Dec 2013 16:02:48 +0100
parents	961d832d8734
children

rev	line source
87288 adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	1 /* Set of hash utility functions to help maintaining the invariant that
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	2 if a==b then hash(a)==hash(b)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	3
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	4 All the utility functions (_Py_Hash*()) return "-1" to signify an error.
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	5 */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	6 #include "Python.h"
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	7
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	8 #ifdef __APPLE__
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	9 # include <libkern/OSByteOrder.h>
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	10 #elif defined(HAVE_LE64TOH) && defined(HAVE_ENDIAN_H)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	11 # include <endian.h>
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	12 #elif defined(HAVE_LE64TOH) && defined(HAVE_SYS_ENDIAN_H)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	13 # include <sys/endian.h>
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	14 #endif
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	15
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	16 #ifdef __cplusplus
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	17 extern "C" {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	18 #endif
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	19
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	20 _Py_HashSecret_t _Py_HashSecret;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	21
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	22 #if Py_HASH_ALGORITHM == Py_HASH_EXTERNAL
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	23 extern PyHash_FuncDef PyHash_Func;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	24 #else
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	25 static PyHash_FuncDef PyHash_Func;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	26 #endif
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	27
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	28 /* Count _Py_HashBytes() calls */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	29 #ifdef Py_HASH_STATS
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	30 #define Py_HASH_STATS_MAX 32
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	31 static Py_ssize_t hashstats[Py_HASH_STATS_MAX + 1] = {0};
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	32 #endif
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	33
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	34 /* For numeric types, the hash of a number x is based on the reduction
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	35 of x modulo the prime P = 2**_PyHASH_BITS - 1. It's designed so that
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	36 hash(x) == hash(y) whenever x and y are numerically equal, even if
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	37 x and y have different types.
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	38
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	39 A quick summary of the hashing strategy:
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	40
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	41 (1) First define the 'reduction of x modulo P' for any rational
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	42 number x; this is a standard extension of the usual notion of
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	43 reduction modulo P for integers. If x == p/q (written in lowest
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	44 terms), the reduction is interpreted as the reduction of p times
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	45 the inverse of the reduction of q, all modulo P; if q is exactly
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	46 divisible by P then define the reduction to be infinity. So we've
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	47 got a well-defined map
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	48
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	49 reduce : { rational numbers } -> { 0, 1, 2, ..., P-1, infinity }.
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	50
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	51 (2) Now for a rational number x, define hash(x) by:
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	52
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	53 reduce(x) if x >= 0
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	54 -reduce(-x) if x < 0
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	55
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	56 If the result of the reduction is infinity (this is impossible for
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	57 integers, floats and Decimals) then use the predefined hash value
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	58 _PyHASH_INF for x >= 0, or -_PyHASH_INF for x < 0, instead.
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	59 _PyHASH_INF, -_PyHASH_INF and _PyHASH_NAN are also used for the
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	60 hashes of float and Decimal infinities and nans.
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	61
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	62 A selling point for the above strategy is that it makes it possible
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	63 to compute hashes of decimal and binary floating-point numbers
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	64 efficiently, even if the exponent of the binary or decimal number
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	65 is large. The key point is that
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	66
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	67 reduce(x * y) == reduce(x) * reduce(y) (modulo _PyHASH_MODULUS)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	68
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	69 provided that {reduce(x), reduce(y)} != {0, infinity}. The reduction of a
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	70 binary or decimal float is never infinity, since the denominator is a power
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	71 of 2 (for binary) or a divisor of a power of 10 (for decimal). So we have,
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	72 for nonnegative x,
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	73
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	74 reduce(x * 2*e) == reduce(x) reduce(2**e) % _PyHASH_MODULUS
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	75
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	76 reduce(x * 10*e) == reduce(x) reduce(10**e) % _PyHASH_MODULUS
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	77
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	78 and reduce(10**e) can be computed efficiently by the usual modular
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	79 exponentiation algorithm. For reduce(2**e) it's even better: since
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	80 P is of the form 2n-1, reduce(2e) is 2**(e mod n), and multiplication
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	81 by 2(e mod n) modulo 2n-1 just amounts to a rotation of bits.
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	82
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	83 */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	84
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	85 Py_hash_t
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	86 _Py_HashDouble(double v)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	87 {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	88 int e, sign;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	89 double m;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	90 Py_uhash_t x, y;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	91
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	92 if (!Py_IS_FINITE(v)) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	93 if (Py_IS_INFINITY(v))
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	94 return v > 0 ? _PyHASH_INF : -_PyHASH_INF;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	95 else
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	96 return _PyHASH_NAN;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	97 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	98
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	99 m = frexp(v, &e);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	100
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	101 sign = 1;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	102 if (m < 0) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	103 sign = -1;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	104 m = -m;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	105 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	106
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	107 /* process 28 bits at a time; this should work well both for binary
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	108 and hexadecimal floating point. */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	109 x = 0;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	110 while (m) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	111 x = ((x << 28) & _PyHASH_MODULUS) \| x >> (_PyHASH_BITS - 28);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	112 m = 268435456.0; / 2*28 /
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	113 e -= 28;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	114 y = (Py_uhash_t)m; /* pull out integer part */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	115 m -= y;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	116 x += y;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	117 if (x >= _PyHASH_MODULUS)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	118 x -= _PyHASH_MODULUS;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	119 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	120
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	121 /* adjust for the exponent; first reduce it modulo _PyHASH_BITS */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	122 e = e >= 0 ? e % _PyHASH_BITS : _PyHASH_BITS-1-((-1-e) % _PyHASH_BITS);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	123 x = ((x << e) & _PyHASH_MODULUS) \| x >> (_PyHASH_BITS - e);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	124
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	125 x = x * sign;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	126 if (x == (Py_uhash_t)-1)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	127 x = (Py_uhash_t)-2;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	128 return (Py_hash_t)x;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	129 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	130
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	131 Py_hash_t
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	132 _Py_HashPointer(void *p)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	133 {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	134 Py_hash_t x;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	135 size_t y = (size_t)p;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	136 /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	137 excessive hash collisions for dicts and sets */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	138 y = (y >> 4) \| (y << (8 * SIZEOF_VOID_P - 4));
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	139 x = (Py_hash_t)y;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	140 if (x == -1)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	141 x = -2;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	142 return x;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	143 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	144
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	145 Py_hash_t
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	146 _Py_HashBytes(const void *src, Py_ssize_t len)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	147 {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	148 Py_hash_t x;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	149 /*
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	150 We make the hash of the empty string be 0, rather than using
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	151 (prefix ^ suffix), since this slightly obfuscates the hash secret
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	152 */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	153 if (len == 0) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	154 return 0;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	155 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	156
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	157 #ifdef Py_HASH_STATS
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	158 hashstats[(len <= Py_HASH_STATS_MAX) ? len : 0]++;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	159 #endif
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	160
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	161 #if Py_HASH_CUTOFF > 0
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	162 if (len < Py_HASH_CUTOFF) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	163 /* Optimize hashing of very small strings with inline DJBX33A. */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	164 Py_uhash_t hash;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	165 const unsigned char *p = src;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	166 hash = 5381; /* DJBX33A starts with 5381 */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	167
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	168 switch(len) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	169 /* ((hash << 5) + hash) + p == hash 33 + p /
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	170 case 7: hash = ((hash << 5) + hash) + p++; / fallthrough */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	171 case 6: hash = ((hash << 5) + hash) + p++; / fallthrough */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	172 case 5: hash = ((hash << 5) + hash) + p++; / fallthrough */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	173 case 4: hash = ((hash << 5) + hash) + p++; / fallthrough */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	174 case 3: hash = ((hash << 5) + hash) + p++; / fallthrough */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	175 case 2: hash = ((hash << 5) + hash) + p++; / fallthrough */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	176 case 1: hash = ((hash << 5) + hash) + *p++; break;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	177 default:
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	178 assert(0);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	179 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	180 hash ^= len;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	181 hash ^= (Py_uhash_t) _Py_HashSecret.djbx33a.suffix;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	182 x = (Py_hash_t)hash;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	183 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	184 else
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	185 #endif /* Py_HASH_CUTOFF */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	186 x = PyHash_Func.hash(src, len);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	187
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	188 if (x == -1)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	189 return -2;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	190 return x;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	191 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	192
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	193 void
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	194 _PyHash_Fini(void)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	195 {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	196 #ifdef Py_HASH_STATS
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	197 int i;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	198 Py_ssize_t total = 0;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	199 char *fmt = "%2i %8" PY_FORMAT_SIZE_T "d %8" PY_FORMAT_SIZE_T "d\n";
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	200
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	201 fprintf(stderr, "len calls total\n");
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	202 for (i = 1; i <= Py_HASH_STATS_MAX; i++) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	203 total += hashstats[i];
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	204 fprintf(stderr, fmt, i, hashstats[i], total);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	205 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	206 total += hashstats[0];
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	207 fprintf(stderr, "> %8" PY_FORMAT_SIZE_T "d %8" PY_FORMAT_SIZE_T "d\n",
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	208 hashstats[0], total);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	209 #endif
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	210 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	211
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	212 PyHash_FuncDef *
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	213 PyHash_GetFuncDef(void)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	214 {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	215 return &PyHash_Func;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	216 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	217
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	218 /* Optimized memcpy() for Windows */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	219 #ifdef _MSC_VER
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	220 # if SIZEOF_PY_UHASH_T == 4
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	221 # define PY_UHASH_CPY(dst, src) do { \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	222 dst[0] = src[0]; dst[1] = src[1]; dst[2] = src[2]; dst[3] = src[3]; \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	223 } while(0)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	224 # elif SIZEOF_PY_UHASH_T == 8
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	225 # define PY_UHASH_CPY(dst, src) do { \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	226 dst[0] = src[0]; dst[1] = src[1]; dst[2] = src[2]; dst[3] = src[3]; \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	227 dst[4] = src[4]; dst[5] = src[5]; dst[6] = src[6]; dst[7] = src[7]; \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	228 } while(0)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	229 # else
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	230 # error SIZEOF_PY_UHASH_T must be 4 or 8
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	231 # endif /* SIZEOF_PY_UHASH_T */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	232 #else /* not Windows */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	233 # define PY_UHASH_CPY(dst, src) memcpy(dst, src, SIZEOF_PY_UHASH_T)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	234 #endif /* _MSC_VER */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	235
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	236
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	237 #if Py_HASH_ALGORITHM == Py_HASH_FNV
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	238 /* **************************************************************************
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	239 * Modified Fowler-Noll-Vo (FNV) hash function
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	240 */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	241 static Py_hash_t
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	242 fnv(const void *src, Py_ssize_t len)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	243 {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	244 const unsigned char *p = src;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	245 Py_uhash_t x;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	246 Py_ssize_t remainder, blocks;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	247 union {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	248 Py_uhash_t value;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	249 unsigned char bytes[SIZEOF_PY_UHASH_T];
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	250 } block;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	251
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	252 #ifdef Py_DEBUG
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	253 assert(_Py_HashSecret_Initialized);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	254 #endif
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	255 remainder = len % SIZEOF_PY_UHASH_T;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	256 if (remainder == 0) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	257 /* Process at least one block byte by byte to reduce hash collisions
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	258 * for strings with common prefixes. */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	259 remainder = SIZEOF_PY_UHASH_T;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	260 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	261 blocks = (len - remainder) / SIZEOF_PY_UHASH_T;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	262
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	263 x = (Py_uhash_t) _Py_HashSecret.fnv.prefix;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	264 x ^= (Py_uhash_t) *p << 7;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	265 while (blocks--) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	266 PY_UHASH_CPY(block.bytes, p);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	267 x = (_PyHASH_MULTIPLIER * x) ^ block.value;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	268 p += SIZEOF_PY_UHASH_T;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	269 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	270 /* add remainder */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	271 for (; remainder > 0; remainder--)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	272 x = (_PyHASH_MULTIPLIER * x) ^ (Py_uhash_t) *p++;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	273 x ^= (Py_uhash_t) len;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	274 x ^= (Py_uhash_t) _Py_HashSecret.fnv.suffix;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	275 if (x == -1) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	276 x = -2;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	277 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	278 return x;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	279 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	280
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	281 static PyHash_FuncDef PyHash_Func = {fnv, "fnv", 8 * SIZEOF_PY_HASH_T,
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	282 16 * SIZEOF_PY_HASH_T};
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	283
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	284 #endif /* Py_HASH_ALGORITHM == Py_HASH_FNV */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	285
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	286
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	287 #if Py_HASH_ALGORITHM == Py_HASH_SIPHASH24
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	288 /* **************************************************************************
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	289 <MIT License>
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	290 Copyright (c) 2013 Marek Majkowski <marek@popcount.org>
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	291
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	292 Permission is hereby granted, free of charge, to any person obtaining a copy
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	293 of this software and associated documentation files (the "Software"), to deal
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	294 in the Software without restriction, including without limitation the rights
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	295 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	296 copies of the Software, and to permit persons to whom the Software is
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	297 furnished to do so, subject to the following conditions:
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	298
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	299 The above copyright notice and this permission notice shall be included in
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	300 all copies or substantial portions of the Software.
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	301
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	302 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	303 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	304 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	305 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	306 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	307 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	308 THE SOFTWARE.
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	309 </MIT License>
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	310
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	311 Original location:
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	312 https://github.com/majek/csiphash/
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	313
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	314 Solution inspired by code from:
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	315 Samuel Neves (supercop/crypto_auth/siphash24/little)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	316 djb (supercop/crypto_auth/siphash24/little2)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	317 Jean-Philippe Aumasson (https://131002.net/siphash/siphash24.c)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	318
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	319 Modified for Python by Christian Heimes:
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	320 - C89 / MSVC compatibility
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	321 - PY_UINT64_T, PY_UINT32_T and PY_UINT8_T
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	322 - _rotl64() on Windows
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	323 - letoh64() fallback
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	324 */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	325
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	326 typedef unsigned char PY_UINT8_T;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	327
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	328 /* byte swap little endian to host endian
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	329 * Endian conversion not only ensures that the hash function returns the same
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	330 * value on all platforms. It is also required to for a good dispersion of
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	331 * the hash values' least significant bits.
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	332 */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	333 #if PY_LITTLE_ENDIAN
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	334 # define _le64toh(x) ((PY_UINT64_T)(x))
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	335 #elif defined(__APPLE__)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	336 # define _le64toh(x) OSSwapLittleToHostInt64(x)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	337 #elif defined(HAVE_LETOH64)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	338 # define _le64toh(x) le64toh(x)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	339 #else
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	340 # define _le64toh(x) (((PY_UINT64_T)(x) << 56) \| \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	341 (((PY_UINT64_T)(x) << 40) & 0xff000000000000ULL) \| \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	342 (((PY_UINT64_T)(x) << 24) & 0xff0000000000ULL) \| \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	343 (((PY_UINT64_T)(x) << 8) & 0xff00000000ULL) \| \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	344 (((PY_UINT64_T)(x) >> 8) & 0xff000000ULL) \| \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	345 (((PY_UINT64_T)(x) >> 24) & 0xff0000ULL) \| \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	346 (((PY_UINT64_T)(x) >> 40) & 0xff00ULL) \| \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	347 ((PY_UINT64_T)(x) >> 56))
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	348 #endif
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	349
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	350
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	351 #ifdef _MSC_VER
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	352 # define ROTATE(x, b) _rotl64(x, b)
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	353 #else
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	354 # define ROTATE(x, b) (PY_UINT64_T)( ((x) << (b)) \| ( (x) >> (64 - (b))) )
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	355 #endif
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	356
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	357 #define HALF_ROUND(a,b,c,d,s,t) \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	358 a += b; c += d; \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	359 b = ROTATE(b, s) ^ a; \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	360 d = ROTATE(d, t) ^ c; \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	361 a = ROTATE(a, 32);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	362
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	363 #define DOUBLE_ROUND(v0,v1,v2,v3) \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	364 HALF_ROUND(v0,v1,v2,v3,13,16); \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	365 HALF_ROUND(v2,v1,v0,v3,17,21); \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	366 HALF_ROUND(v0,v1,v2,v3,13,16); \
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	367 HALF_ROUND(v2,v1,v0,v3,17,21);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	368
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	369
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	370 static Py_hash_t
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	371 siphash24(const void *src, Py_ssize_t src_sz) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	372 PY_UINT64_T k0 = _le64toh(_Py_HashSecret.siphash.k0);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	373 PY_UINT64_T k1 = _le64toh(_Py_HashSecret.siphash.k1);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	374 PY_UINT64_T b = (PY_UINT64_T)src_sz << 56;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	375 const PY_UINT64_T in = (PY_UINT64_T)src;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	376
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	377 PY_UINT64_T v0 = k0 ^ 0x736f6d6570736575ULL;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	378 PY_UINT64_T v1 = k1 ^ 0x646f72616e646f6dULL;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	379 PY_UINT64_T v2 = k0 ^ 0x6c7967656e657261ULL;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	380 PY_UINT64_T v3 = k1 ^ 0x7465646279746573ULL;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	381
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	382 PY_UINT64_T t;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	383 PY_UINT8_T *pt;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	384 PY_UINT8_T *m;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	385
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	386 while (src_sz >= 8) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	387 PY_UINT64_T mi = _le64toh(*in);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	388 in += 1;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	389 src_sz -= 8;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	390 v3 ^= mi;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	391 DOUBLE_ROUND(v0,v1,v2,v3);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	392 v0 ^= mi;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	393 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	394
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	395 t = 0;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	396 pt = (PY_UINT8_T *)&t;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	397 m = (PY_UINT8_T *)in;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	398 switch (src_sz) {
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	399 case 7: pt[6] = m[6];
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	400 case 6: pt[5] = m[5];
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	401 case 5: pt[4] = m[4];
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	402 case 4: ((PY_UINT32_T)&pt[0]) = ((PY_UINT32_T)&m[0]); break;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	403 case 3: pt[2] = m[2];
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	404 case 2: pt[1] = m[1];
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	405 case 1: pt[0] = m[0];
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	406 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	407 b \|= _le64toh(t);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	408
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	409 v3 ^= b;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	410 DOUBLE_ROUND(v0,v1,v2,v3);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	411 v0 ^= b;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	412 v2 ^= 0xff;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	413 DOUBLE_ROUND(v0,v1,v2,v3);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	414 DOUBLE_ROUND(v0,v1,v2,v3);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	415
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	416 /* modified */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	417 t = (v0 ^ v1) ^ (v2 ^ v3);
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	418 return (Py_hash_t)t;
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	419 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	420
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	421 static PyHash_FuncDef PyHash_Func = {siphash24, "siphash24", 64, 128};
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	422
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	423 #endif /* Py_HASH_ALGORITHM == Py_HASH_SIPHASH24 */
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	424
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	425 #ifdef __cplusplus
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	426 }
adb471b9cba1 ssue #19183: Implement PEP 456 'secure and interchangeable hash algorithm'. Christian Heimes <christian@cheimes.de> parents: diff changeset	427 #endif

Mercurial > cpython-lru_cache-weakref

annotate Python/pyhash.c @ 87690:66c1c9f32567 default tip