/home/mdboom/Work/builds/cpython/Include/pyhash.h
Line | Count | Source |
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_* are hard-coded in the |
118 | * configure script. |
119 | * |
120 | * - FNV and SIPHASH* are available on all platforms and architectures. |
121 | * - With EXTERNAL embedders can provide an alternative implementation with:: |
122 | * |
123 | * PyHash_FuncDef PyHash_Func = {...}; |
124 | * |
125 | * XXX: Figure out __declspec() for extern PyHash_FuncDef. |
126 | */ |
127 | #define Py_HASH_EXTERNAL 0 |
128 | #define Py_HASH_SIPHASH24 1 |
129 | #define Py_HASH_FNV 2 |
130 | #define Py_HASH_SIPHASH13 3 |
131 | |
132 | #ifndef Py_HASH_ALGORITHM |
133 | # ifndef HAVE_ALIGNED_REQUIRED |
134 | # define Py_HASH_ALGORITHM Py_HASH_SIPHASH13 |
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 */ |