1 #ifndef Py_HASH_H 2 3 #define Py_HASH_H 4 #ifdef __cplusplus 5 extern "C" { 6 #endif 7 8 /* Helpers for hash functions */ 9 #ifndef Py_LIMITED_API 10 PyAPI_FUNC(Py_hash_t) _Py_HashDouble(PyObject *, double); 11 PyAPI_FUNC(Py_hash_t) _Py_HashPointer(const void*); 12 // Similar to _Py_HashPointer(), but don't replace -1 with -2 13 PyAPI_FUNC(Py_hash_t) _Py_HashPointerRaw(const void*); 14 PyAPI_FUNC(Py_hash_t) _Py_HashBytes(const void*, Py_ssize_t); 15 #endif 16 17 /* Prime multiplier used in string and various other hashes. */ 18 #define _PyHASH_MULTIPLIER 1000003UL /* 0xf4243 */ 19 20 /* Parameters used for the numeric hash implementation. See notes for 21 _Py_HashDouble in Python/pyhash.c. Numeric hashes are based on 22 reduction modulo the prime 2**_PyHASH_BITS - 1. */ 23 24 #if SIZEOF_VOID_P >= 8 25 # define _PyHASH_BITS 61 26 #else 27 # define _PyHASH_BITS 31 28 #endif 29 30 #define _PyHASH_MODULUS (((size_t)1 << _PyHASH_BITS) - 1) 31 #define _PyHASH_INF 314159 32 #define _PyHASH_IMAG _PyHASH_MULTIPLIER 33 34 35 /* hash secret 36 * 37 * memory layout on 64 bit systems 38 * cccccccc cccccccc cccccccc uc -- unsigned char[24] 39 * pppppppp ssssssss ........ fnv -- two Py_hash_t 40 * k0k0k0k0 k1k1k1k1 ........ siphash -- two uint64_t 41 * ........ ........ ssssssss djbx33a -- 16 bytes padding + one Py_hash_t 42 * ........ ........ eeeeeeee pyexpat XML hash salt 43 * 44 * memory layout on 32 bit systems 45 * cccccccc cccccccc cccccccc uc 46 * ppppssss ........ ........ fnv -- two Py_hash_t 47 * k0k0k0k0 k1k1k1k1 ........ siphash -- two uint64_t (*) 48 * ........ ........ ssss.... djbx33a -- 16 bytes padding + one Py_hash_t 49 * ........ ........ eeee.... pyexpat XML hash salt 50 * 51 * (*) The siphash member may not be available on 32 bit platforms without 52 * an unsigned int64 data type. 53 */ 54 #ifndef Py_LIMITED_API 55 typedef union { 56 /* ensure 24 bytes */ 57 unsigned char uc[24]; 58 /* two Py_hash_t for FNV */ 59 struct { 60 Py_hash_t prefix; 61 Py_hash_t suffix; 62 } fnv; 63 /* two uint64 for SipHash24 */ 64 struct { 65 uint64_t k0; 66 uint64_t k1; 67 } siphash; 68 /* a different (!) Py_hash_t for small string optimization */ 69 struct { 70 unsigned char padding[16]; 71 Py_hash_t suffix; 72 } djbx33a; 73 struct { 74 unsigned char padding[16]; 75 Py_hash_t hashsalt; 76 } expat; 77 } _Py_HashSecret_t; 78 PyAPI_DATA(_Py_HashSecret_t) _Py_HashSecret; 79 80 #ifdef Py_DEBUG 81 PyAPI_DATA(int) _Py_HashSecret_Initialized; 82 #endif 83 84 85 /* hash function definition */ 86 typedef struct { 87 Py_hash_t (*const hash)(const void *, Py_ssize_t); 88 const char *name; 89 const int hash_bits; 90 const int seed_bits; 91 } PyHash_FuncDef; 92 93 PyAPI_FUNC(PyHash_FuncDef*) PyHash_GetFuncDef(void); 94 #endif 95 96 97 /* cutoff for small string DJBX33A optimization in range [1, cutoff). 98 * 99 * About 50% of the strings in a typical Python application are smaller than 100 * 6 to 7 chars. However DJBX33A is vulnerable to hash collision attacks. 101 * NEVER use DJBX33A for long strings! 102 * 103 * A Py_HASH_CUTOFF of 0 disables small string optimization. 32 bit platforms 104 * should use a smaller cutoff because it is easier to create colliding 105 * strings. A cutoff of 7 on 64bit platforms and 5 on 32bit platforms should 106 * provide a decent safety margin. 107 */ 108 #ifndef Py_HASH_CUTOFF 109 # define Py_HASH_CUTOFF 0 110 #elif (Py_HASH_CUTOFF > 7 || Py_HASH_CUTOFF < 0) 111 # error Py_HASH_CUTOFF must in range 0...7. 112 #endif /* Py_HASH_CUTOFF */ 113 114 115 /* hash algorithm selection 116 * 117 * The values for Py_HASH_SIPHASH24 and Py_HASH_FNV are hard-coded in the 118 * configure script. 119 * 120 * - FNV is available on all platforms and architectures. 121 * - SIPHASH24 only works on platforms that don't require aligned memory for integers. 122 * - With EXTERNAL embedders can provide an alternative implementation with:: 123 * 124 * PyHash_FuncDef PyHash_Func = {...}; 125 * 126 * XXX: Figure out __declspec() for extern PyHash_FuncDef. 127 */ 128 #define Py_HASH_EXTERNAL 0 129 #define Py_HASH_SIPHASH24 1 130 #define Py_HASH_FNV 2 131 132 #ifndef Py_HASH_ALGORITHM 133 # ifndef HAVE_ALIGNED_REQUIRED 134 # define Py_HASH_ALGORITHM Py_HASH_SIPHASH24 135 # else 136 # define Py_HASH_ALGORITHM Py_HASH_FNV 137 # endif /* uint64_t && uint32_t && aligned */ 138 #endif /* Py_HASH_ALGORITHM */ 139 140 #ifdef __cplusplus 141 } 142 #endif 143 144 #endif /* !Py_HASH_H */ 145