1 /*
2 ** Zabbix
3 ** Copyright (C) 2001-2021 Zabbix SIA
4 **
5 ** This program is free software; you can redistribute it and/or modify
6 ** it under the terms of the GNU General Public License as published by
7 ** the Free Software Foundation; either version 2 of the License, or
8 ** (at your option) any later version.
9 **
10 ** This program is distributed in the hope that it will be useful,
11 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
12 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 ** GNU General Public License for more details.
14 **
15 ** You should have received a copy of the GNU General Public License
16 ** along with this program; if not, write to the Free Software
17 ** Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 **/
19
20 #include "common.h"
21 #include "zbxalgo.h"
22
23 #define UINT64_BIT_COUNT (sizeof(zbx_uint64_t) << 3)
24 #define UINT32_BIT_COUNT (UINT64_BIT_COUNT >> 1)
25 #define UINT32_BIT_MASK (~((~__UINT64_C(0)) << UINT32_BIT_COUNT))
26
27 /******************************************************************************
28 * *
29 * Function: udec128_128 *
30 * *
31 * Purpose: Decrement of 128 bit unsigned integer by the specified value. *
32 * *
33 * Parameters: base - [IN,OUT] the integer to decrement. *
34 * value - [IN] the value to decrement by. *
35 * *
36 * Author: Andris Zeila *
37 * *
38 ******************************************************************************/
udec128_128(zbx_uint128_t * base,const zbx_uint128_t * value)39 static void udec128_128(zbx_uint128_t *base, const zbx_uint128_t *value)
40 {
41 zbx_uint64_t lo = base->lo;
42
43 base->lo -= value->lo;
44 if (lo < base->lo)
45 base->hi--;
46 base->hi -= value->hi;
47 }
48
49 /******************************************************************************
50 * *
51 * Function: ushiftr128 *
52 * *
53 * Purpose: Logical right shift of 128 bit unsigned integer. *
54 * *
55 * Parameters: base - [IN,OUT] the inital value and result *
56 * bits - [IN] the number of bits to shift for. *
57 * *
58 * Author: Andris Zeila *
59 * *
60 ******************************************************************************/
ushiftr128(zbx_uint128_t * base,unsigned int bits)61 static void ushiftr128(zbx_uint128_t *base, unsigned int bits)
62 {
63 if (0 == bits)
64 return;
65
66 if (UINT64_BIT_COUNT <= bits)
67 {
68 bits -= UINT64_BIT_COUNT;
69 base->lo = base->hi >> bits;
70 base->hi = 0;
71 return;
72 }
73
74 base->lo >>= bits;
75 base->lo |= (base->hi << (UINT64_BIT_COUNT - bits));
76 base->hi >>= bits;
77 }
78
79
80 /******************************************************************************
81 * *
82 * Function: ushiftl128 *
83 * *
84 * Purpose: Logical left shift of 128 bit unsigned integer. *
85 * *
86 * Parameters: base - [IN,OUT] the inital value and result *
87 * bits - [IN] the number of bits to shift for. *
88 * *
89 * Author: Andris Zeila *
90 * *
91 ******************************************************************************/
ushiftl128(zbx_uint128_t * base,unsigned int bits)92 static void ushiftl128(zbx_uint128_t *base, unsigned int bits)
93 {
94 if (0 == bits)
95 return;
96
97 if (UINT64_BIT_COUNT <= bits)
98 {
99 bits -= UINT64_BIT_COUNT;
100 base->hi = base->lo << bits;
101 base->lo = 0;
102 return;
103 }
104
105 base->hi <<= bits;
106 base->hi |= (base->lo >> (UINT64_BIT_COUNT - bits));
107 base->lo <<= bits;
108 }
109
110 /******************************************************************************
111 * *
112 * Function: ucmp128_128 *
113 * *
114 * Purpose: Comparison of two 128 bit unsigned integer values. *
115 * *
116 * Parameters: value1 - [IN] the first value to compare. *
117 * value2 - [IN] the second value to compare. *
118 * *
119 * Return value: -1 - value1 < value2 *
120 * 0 - value1 = value2 *
121 * 1 - value1 > value2 *
122 * *
123 * Author: Andris Zeila *
124 * *
125 ******************************************************************************/
ucmp128_128(const zbx_uint128_t * value1,const zbx_uint128_t * value2)126 static int ucmp128_128(const zbx_uint128_t *value1, const zbx_uint128_t *value2)
127 {
128 if (value1->hi != value2->hi)
129 return value1->hi < value2->hi ? -1 : 1;
130 if (value1->lo == value2->lo)
131 return 0;
132 return value1->lo < value2->lo ? -1 : 1;
133 }
134
135 /******************************************************************************
136 * *
137 * Function: umul64_32_shift *
138 * *
139 * Purpose: Multiplication of 64 bit unsigned integer with 32 bit unsigned *
140 * integer value, shifted left by specified number of bits *
141 * *
142 * Parameters: base - [OUT] the value to add result to *
143 * value - [IN] the value to multiply. *
144 * factor - [IN] the factor to multiply by. *
145 * shift - [IN] the number of bits to shift the result by before *
146 * adding it to the base value. *
147 * *
148 * Comments: This is a helper function for umul64_64 implementation. *
149 * *
150 * Author: Andris Zeila *
151 * *
152 ******************************************************************************/
umul64_32_shift(zbx_uint128_t * base,zbx_uint64_t value,zbx_uint64_t factor,int shift)153 static void umul64_32_shift(zbx_uint128_t *base, zbx_uint64_t value, zbx_uint64_t factor, int shift)
154 {
155 zbx_uint128_t buffer;
156
157 uset128(&buffer, 0, (value & UINT32_BIT_MASK) * factor);
158 ushiftl128(&buffer, shift);
159 uinc128_128(base, &buffer);
160
161 uset128(&buffer, 0, (value >> UINT32_BIT_COUNT) * factor);
162 ushiftl128(&buffer, UINT32_BIT_COUNT + shift);
163 uinc128_128(base, &buffer);
164 }
165
166 /******************************************************************************
167 * *
168 * Function: uinc128_64 *
169 * *
170 * Purpose: Increment of 128 bit unsigned integer by the specified 64 bit *
171 * value. *
172 * *
173 * Parameters: base - [IN,OUT] the integer to increment. *
174 * value - [IN] the value to increment by. *
175 * *
176 * Author: Andris Zeila *
177 * *
178 ******************************************************************************/
uinc128_64(zbx_uint128_t * base,zbx_uint64_t value)179 void uinc128_64(zbx_uint128_t *base, zbx_uint64_t value)
180 {
181 zbx_uint64_t low = base->lo;
182
183 base->lo += value;
184 /* handle wraparound */
185 if (low > base->lo)
186 base->hi++;
187 }
188
189 /******************************************************************************
190 * *
191 * Function: uinc128_128 *
192 * *
193 * Purpose: Increment of 128 bit unsigned integer by the specified 128 bit *
194 * value *
195 * *
196 * Parameters: base - [IN,OUT] the integer to increment. *
197 * value - [IN] the value to increment by. *
198 * *
199 * Author: Andris Zeila *
200 * *
201 ******************************************************************************/
uinc128_128(zbx_uint128_t * base,const zbx_uint128_t * value)202 void uinc128_128(zbx_uint128_t *base, const zbx_uint128_t *value)
203 {
204 zbx_uint64_t low = base->lo;
205
206 base->lo += value->lo;
207 /* handle wraparound */
208 if (low > base->lo)
209 base->hi++;
210 base->hi += value->hi;
211 }
212
213 /******************************************************************************
214 * *
215 * Function: umul64_64 *
216 * *
217 * Purpose: Multiplication of two 64 bit unsigned integer values. *
218 * *
219 * Parameters: result - [OUT] the resulting 128 bit unsigned integer value *
220 * value - [IN] the value to multiply. *
221 * factor - [IN] the factor to multiply by. *
222 * *
223 * Author: Andris Zeila *
224 * *
225 ******************************************************************************/
umul64_64(zbx_uint128_t * result,zbx_uint64_t value,zbx_uint64_t factor)226 void umul64_64(zbx_uint128_t *result, zbx_uint64_t value, zbx_uint64_t factor)
227 {
228 uset128(result, 0, 0);
229 /* multiply the value with lower double word of factor and add the result */
230 umul64_32_shift(result, value, factor & UINT32_BIT_MASK, 0);
231 /* multiply the value with higher double word of factor and add the result */
232 umul64_32_shift(result, value, factor >> UINT32_BIT_COUNT, UINT32_BIT_COUNT);
233 }
234
235 /******************************************************************************
236 * *
237 * Function: udiv128_64 *
238 * *
239 * Purpose: Division of 128 bit unsigned integer by a 64 bit unsigned integer *
240 * value. *
241 * *
242 * Parameters: result - [OUT] the resulting quotient value. *
243 * dividend - [IN] the dividend. *
244 * value - [IN] the divisor. *
245 * *
246 * Author: Andris Zeila *
247 * *
248 ******************************************************************************/
udiv128_64(zbx_uint128_t * result,const zbx_uint128_t * dividend,zbx_uint64_t value)249 void udiv128_64(zbx_uint128_t *result, const zbx_uint128_t *dividend, zbx_uint64_t value)
250 {
251 zbx_uint128_t reminder, divisor;
252 zbx_uint64_t result_mask = __UINT64_C(1) << (UINT64_BIT_COUNT - 1);
253
254 /* first handle the simple 64bit/64bit case */
255 if (0 == dividend->hi)
256 {
257 result->hi = 0;
258 result->lo = dividend->lo / value;
259 return;
260 }
261
262 /* divide the high qword and store the result in result, reminder in reminder */
263 reminder = *dividend;
264 if (dividend->hi >= value)
265 {
266 result->hi = dividend->hi / value;
267 reminder.hi -= result->hi * value;
268 }
269 else
270 result->hi = 0;
271 result->lo = 0;
272
273 /* shift divisor left by 64 bits - simply assign it to the high qword */
274 uset128(&divisor, value, 0);
275
276 /* Reminder is always less than divisor shifted right by 64 bits (because of the */
277 /* high qword division above). So pre-shift the divisor to right by one. */
278 ushiftr128(&divisor, 1);
279
280 /* do manual division while reminder is larger than 64 bits */
281 while (reminder.hi)
282 {
283 while (ucmp128_128(&reminder, &divisor) < 0)
284 {
285 ushiftr128(&divisor, 1);
286 result_mask >>= 1;
287 }
288
289 udec128_128(&reminder, &divisor);
290 result->lo |= result_mask;
291
292 }
293 /* reminder is less than 64 bits, proceed with 64bit division */
294 result->lo |= reminder.lo / value;
295 }
296