1/*****************************************************************************
2
3Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved.
4Copyright (c) 2017, MariaDB Corporation.
5
6This program is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free Software
8Foundation; version 2 of the License.
9
10This program is distributed in the hope that it will be useful, but WITHOUT
11ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
14You should have received a copy of the GNU General Public License along with
15this program; if not, write to the Free Software Foundation, Inc.,
1651 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
17
18*****************************************************************************/
19
20/**************************************************************//**
21@file include/ut0rnd.ic
22Random numbers and hashing
23
24Created 5/30/1994 Heikki Tuuri
25*******************************************************************/
26
27#define UT_HASH_RANDOM_MASK 1463735687
28#define UT_HASH_RANDOM_MASK2 1653893711
29
30#ifndef UNIV_INNOCHECKSUM
31
32#define UT_RND1 151117737
33#define UT_RND2 119785373
34#define UT_RND3 85689495
35#define UT_RND4 76595339
36#define UT_SUM_RND2 98781234
37#define UT_SUM_RND3 126792457
38#define UT_SUM_RND4 63498502
39#define UT_XOR_RND1 187678878
40#define UT_XOR_RND2 143537923
41
42/** Seed value of ut_rnd_gen_ulint() */
43extern ulint ut_rnd_ulint_counter;
44
45/********************************************************//**
46This is used to set the random number seed. */
47UNIV_INLINE
48void
49ut_rnd_set_seed(
50/*============*/
51 ulint seed) /*!< in: seed */
52{
53 ut_rnd_ulint_counter = seed;
54}
55
56/********************************************************//**
57The following function generates a series of 'random' ulint integers.
58@return the next 'random' number */
59UNIV_INLINE
60ulint
61ut_rnd_gen_next_ulint(
62/*==================*/
63 ulint rnd) /*!< in: the previous random number value */
64{
65 ulint n_bits;
66
67 n_bits = 8 * sizeof(ulint);
68
69 rnd = UT_RND2 * rnd + UT_SUM_RND3;
70 rnd = UT_XOR_RND1 ^ rnd;
71 rnd = (rnd << 20) + (rnd >> (n_bits - 20));
72 rnd = UT_RND3 * rnd + UT_SUM_RND4;
73 rnd = UT_XOR_RND2 ^ rnd;
74 rnd = (rnd << 20) + (rnd >> (n_bits - 20));
75 rnd = UT_RND1 * rnd + UT_SUM_RND2;
76
77 return(rnd);
78}
79
80/********************************************************//**
81The following function generates 'random' ulint integers which
82enumerate the value space of ulint integers in a pseudo random
83fashion. Note that the same integer is repeated always after
842 to power 32 calls to the generator (if ulint is 32-bit).
85@return the 'random' number */
86UNIV_INLINE
87ulint
88ut_rnd_gen_ulint(void)
89/*==================*/
90{
91 ulint rnd;
92
93 ut_rnd_ulint_counter = UT_RND1 * ut_rnd_ulint_counter + UT_RND2;
94
95 rnd = ut_rnd_gen_next_ulint(ut_rnd_ulint_counter);
96
97 return(rnd);
98}
99
100/*******************************************************//**
101The following function generates a hash value for a ulint integer
102to a hash table of size table_size, which should be a prime
103or some random number for the hash table to work reliably.
104@return hash value */
105UNIV_INLINE
106ulint
107ut_hash_ulint(
108/*==========*/
109 ulint key, /*!< in: value to be hashed */
110 ulint table_size) /*!< in: hash table size */
111{
112 ut_ad(table_size);
113 key = key ^ UT_HASH_RANDOM_MASK2;
114
115 return(key % table_size);
116}
117
118/*************************************************************//**
119Folds a 64-bit integer.
120@return folded value */
121UNIV_INLINE
122ulint
123ut_fold_ull(
124/*========*/
125 ib_uint64_t d) /*!< in: 64-bit integer */
126{
127 return(ut_fold_ulint_pair((ulint) d & ULINT32_MASK,
128 (ulint) (d >> 32)));
129}
130
131/*************************************************************//**
132Folds a character string ending in the null character.
133@return folded value */
134UNIV_INLINE
135ulint
136ut_fold_string(
137/*===========*/
138 const char* str) /*!< in: null-terminated string */
139{
140 ulint fold = 0;
141
142 ut_ad(str);
143
144 while (*str != '\0') {
145 fold = ut_fold_ulint_pair(fold, (ulint)(*str));
146 str++;
147 }
148
149 return(fold);
150}
151
152#endif /* !UNIV_INNOCHECKSUM */
153
154/*************************************************************//**
155Folds a pair of ulints.
156@return folded value */
157UNIV_INLINE
158ulint
159ut_fold_ulint_pair(
160/*===============*/
161 ulint n1, /*!< in: ulint */
162 ulint n2) /*!< in: ulint */
163{
164 return(((((n1 ^ n2 ^ UT_HASH_RANDOM_MASK2) << 8) + n1)
165 ^ UT_HASH_RANDOM_MASK) + n2);
166}
167
168/*************************************************************//**
169Folds a binary string.
170@return folded value */
171UNIV_INLINE
172ulint
173ut_fold_binary(
174/*===========*/
175 const byte* str, /*!< in: string of bytes */
176 ulint len) /*!< in: length */
177{
178 ulint fold = 0;
179 const byte* str_end = str + (len & 0xFFFFFFF8);
180
181 ut_ad(str || !len);
182
183 while (str < str_end) {
184 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
185 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
186 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
187 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
188 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
189 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
190 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
191 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
192 }
193
194 switch (len & 0x7) {
195 case 7:
196 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
197 /* fall through */
198 case 6:
199 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
200 /* fall through */
201 case 5:
202 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
203 /* fall through */
204 case 4:
205 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
206 /* fall through */
207 case 3:
208 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
209 /* fall through */
210 case 2:
211 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
212 /* fall through */
213 case 1:
214 fold = ut_fold_ulint_pair(fold, (ulint)(*str++));
215 }
216
217 return(fold);
218}
219