1#ifndef Py_HASH_H
2
3#define Py_HASH_H
4#ifdef __cplusplus
5extern "C" {
6#endif
7
8/* Helpers for hash functions */
9#ifndef Py_LIMITED_API
10PyAPI_FUNC(Py_hash_t) _Py_HashDouble(PyObject *, double);
11PyAPI_FUNC(Py_hash_t) _Py_HashPointer(const void*);
12// Similar to _Py_HashPointer(), but don't replace -1 with -2
13PyAPI_FUNC(Py_hash_t) _Py_HashPointerRaw(const void*);
14PyAPI_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
55typedef 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;
78PyAPI_DATA(_Py_HashSecret_t) _Py_HashSecret;
79
80#ifdef Py_DEBUG
81PyAPI_DATA(int) _Py_HashSecret_Initialized;
82#endif
83
84
85/* hash function definition */
86typedef 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
93PyAPI_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