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

annotate Python/pyhash.c @ 87353:c8a84eed9155

Remove a commented-out line

author	Brett Cannon <brett@python.org>
date	Fri, 22 Nov 2013 12:07:43 -0500
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 @ 87353:c8a84eed9155