1 /*****************************************************************************
2
3 Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved.
4 Copyright (c) 2019, MariaDB Corporation.
5
6 This program is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free Software
8 Foundation; version 2 of the License.
9
10 This program is distributed in the hope that it will be useful, but WITHOUT
11 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along with
15 this program; if not, write to the Free Software Foundation, Inc.,
16 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA
17
18 *****************************************************************************/
19
20 /******************************************************************//**
21 @file include/ut0rnd.h
22 Random numbers and hashing
23
24 Created 1/20/1994 Heikki Tuuri
25 ***********************************************************************/
26
27 #ifndef ut0rnd_h
28 #define ut0rnd_h
29
30 #include "ut0byte.h"
31 #include <my_sys.h>
32
33 #ifndef UNIV_INNOCHECKSUM
34 /** Seed value of ut_rnd_gen() */
35 extern int32 ut_rnd_current;
36
37 /** @return a pseudo-random 32-bit number */
ut_rnd_gen()38 inline uint32_t ut_rnd_gen()
39 {
40 /* This is a Galois linear-feedback shift register.
41 https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Galois_LFSRs
42 The generating primitive Galois Field polynomial is the Castagnoli
43 polynomial that was made popular by CRC-32C:
44 x^32+x^28+x^27+x^26+x^25+x^23+x^22+x^20+
45 x^19+x^18+x^14+x^13+x^11+x^10+x^9+x^8+x^6+1 */
46 const uint32_t crc32c= 0x1edc6f41;
47
48 uint32_t rnd= my_atomic_load32_explicit(&ut_rnd_current,
49 MY_MEMORY_ORDER_RELAXED);
50
51 if (UNIV_UNLIKELY(rnd == 0))
52 {
53 rnd= static_cast<uint32_t>(my_interval_timer());
54 if (!rnd) rnd= 1;
55 }
56 else
57 {
58 bool lsb= rnd & 1;
59 rnd>>= 1;
60 if (lsb)
61 rnd^= crc32c;
62 }
63
64 my_atomic_store32_explicit(&ut_rnd_current, rnd, MY_MEMORY_ORDER_RELAXED);
65 return rnd;
66 }
67
68 /** @return a random number between 0 and n-1, inclusive */
ut_rnd_interval(ulint n)69 inline ulint ut_rnd_interval(ulint n)
70 {
71 return n > 1 ? static_cast<ulint>(ut_rnd_gen() % n) : 0;
72 }
73
74 /*******************************************************//**
75 The following function generates a hash value for a ulint integer
76 to a hash table of size table_size, which should be a prime or some
77 random number to work reliably.
78 @return hash value */
79 UNIV_INLINE
80 ulint
81 ut_hash_ulint(
82 /*==========*/
83 ulint key, /*!< in: value to be hashed */
84 ulint table_size); /*!< in: hash table size */
85 /*************************************************************//**
86 Folds a 64-bit integer.
87 @return folded value */
88 UNIV_INLINE
89 ulint
90 ut_fold_ull(
91 /*========*/
92 ib_uint64_t d) /*!< in: 64-bit integer */
93 MY_ATTRIBUTE((const));
94 /*************************************************************//**
95 Folds a character string ending in the null character.
96 @return folded value */
97 UNIV_INLINE
98 ulint
99 ut_fold_string(
100 /*===========*/
101 const char* str) /*!< in: null-terminated string */
102 MY_ATTRIBUTE((warn_unused_result));
103 /***********************************************************//**
104 Looks for a prime number slightly greater than the given argument.
105 The prime is chosen so that it is not near any power of 2.
106 @return prime */
107 ulint
108 ut_find_prime(
109 /*==========*/
110 ulint n) /*!< in: positive number > 100 */
111 MY_ATTRIBUTE((const));
112
113 #endif /* !UNIV_INNOCHECKSUM */
114
115 /*************************************************************//**
116 Folds a pair of ulints.
117 @return folded value */
118 UNIV_INLINE
119 ulint
120 ut_fold_ulint_pair(
121 /*===============*/
122 ulint n1, /*!< in: ulint */
123 ulint n2) /*!< in: ulint */
124 MY_ATTRIBUTE((const));
125 /*************************************************************//**
126 Folds a binary string.
127 @return folded value */
128 UNIV_INLINE
129 ulint
130 ut_fold_binary(
131 /*===========*/
132 const byte* str, /*!< in: string of bytes */
133 ulint len) /*!< in: length */
134 MY_ATTRIBUTE((pure));
135
136 #include "ut0rnd.inl"
137
138 #endif
139