Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * int128.h
4 : : * Roll-our-own 128-bit integer arithmetic.
5 : : *
6 : : * We make use of the native int128 type if there is one, otherwise
7 : : * implement things the hard way based on two int64 halves.
8 : : *
9 : : * See src/test/modules/test_int128 for a simple test harness for this file.
10 : : *
11 : : * Copyright (c) 2017-2025, PostgreSQL Global Development Group
12 : : *
13 : : * src/include/common/int128.h
14 : : *
15 : : *-------------------------------------------------------------------------
16 : : */
17 : : #ifndef INT128_H
18 : : #define INT128_H
19 : :
20 : : /*
21 : : * For testing purposes, use of native int128 can be switched on/off by
22 : : * predefining USE_NATIVE_INT128.
23 : : */
24 : : #ifndef USE_NATIVE_INT128
25 : : #ifdef HAVE_INT128
26 : : #define USE_NATIVE_INT128 1
27 : : #else
28 : : #define USE_NATIVE_INT128 0
29 : : #endif
30 : : #endif
31 : :
32 : : /*
33 : : * If native int128 support is enabled, INT128 is just int128. Otherwise, it
34 : : * is a structure with separate 64-bit high and low parts.
35 : : *
36 : : * We lay out the INT128 structure with the same content and byte ordering
37 : : * that a native int128 type would (probably) have. This makes no difference
38 : : * for ordinary use of INT128, but allows union'ing INT128 with int128 for
39 : : * testing purposes.
40 : : *
41 : : * PG_INT128_HI_INT64 and PG_INT128_LO_UINT64 allow the (signed) high and
42 : : * (unsigned) low 64-bit integer parts to be extracted portably on all
43 : : * platforms.
44 : : */
45 : : #if USE_NATIVE_INT128
46 : :
47 : : typedef int128 INT128;
48 : :
49 : : #define PG_INT128_HI_INT64(i128) ((int64) ((i128) >> 64))
50 : : #define PG_INT128_LO_UINT64(i128) ((uint64) (i128))
51 : :
52 : : #else
53 : :
54 : : typedef struct
55 : : {
56 : : #ifdef WORDS_BIGENDIAN
57 : : int64 hi; /* most significant 64 bits, including sign */
58 : : uint64 lo; /* least significant 64 bits, without sign */
59 : : #else
60 : : uint64 lo; /* least significant 64 bits, without sign */
61 : : int64 hi; /* most significant 64 bits, including sign */
62 : : #endif
63 : : } INT128;
64 : :
65 : : #define PG_INT128_HI_INT64(i128) ((i128).hi)
66 : : #define PG_INT128_LO_UINT64(i128) ((i128).lo)
67 : :
68 : : #endif
69 : :
70 : : /*
71 : : * Construct an INT128 from (signed) high and (unsigned) low 64-bit integer
72 : : * parts.
73 : : */
74 : : static inline INT128
30 dean.a.rasheed@gmail 75 :GNC 39 : make_int128(int64 hi, uint64 lo)
76 : : {
77 : : #if USE_NATIVE_INT128
78 : 39 : return (((int128) hi) << 64) + lo;
79 : : #else
80 : : INT128 val;
81 : :
82 : : val.hi = hi;
83 : : val.lo = lo;
84 : : return val;
85 : : #endif
86 : : }
87 : :
88 : : /*
89 : : * Add an unsigned int64 value into an INT128 variable.
90 : : */
91 : : static inline void
3076 tgl@sss.pgh.pa.us 92 : 5000000 : int128_add_uint64(INT128 *i128, uint64 v)
93 : : {
94 : : #if USE_NATIVE_INT128
95 : : *i128 += v;
96 : : #else
97 : : /*
98 : : * First add the value to the .lo part, then check to see if a carry needs
99 : : * to be propagated into the .hi part. Since this is unsigned integer
100 : : * arithmetic, which is just modular arithmetic, a carry is needed if the
101 : : * new .lo part is less than the old .lo part (i.e., if modular
102 : : * wrap-around occurred). Writing this in the form below, rather than
103 : : * using an "if" statement causes modern compilers to produce branchless
104 : : * machine code identical to the native code.
105 : : */
106 : 5000000 : uint64 oldlo = i128->lo;
107 : :
108 : 5000000 : i128->lo += v;
30 dean.a.rasheed@gmail 109 : 5000000 : i128->hi += (i128->lo < oldlo);
110 : : #endif
3076 tgl@sss.pgh.pa.us 111 :GIC 5000000 : }
112 : :
113 : : /*
114 : : * Add a signed int64 value into an INT128 variable.
115 : : */
116 : : static inline void
3076 tgl@sss.pgh.pa.us 117 :GNC 1278739 : int128_add_int64(INT128 *i128, int64 v)
118 : : {
119 : : #if USE_NATIVE_INT128
31 dean.a.rasheed@gmail 120 : 278739 : *i128 += v;
121 : : #else
122 : : /*
123 : : * This is much like the above except that the carry logic differs for
124 : : * negative v -- we need to subtract 1 from the .hi part if the new .lo
125 : : * value is greater than the old .lo value. That can be achieved without
126 : : * any branching by adding the sign bit from v (v >> 63 = 0 or -1) to the
127 : : * previous result (for negative v, if the new .lo value is less than the
128 : : * old .lo value, the two terms cancel and we leave the .hi part
129 : : * unchanged, otherwise we subtract 1 from the .hi part). With modern
130 : : * compilers this often produces machine code identical to the native
131 : : * code.
132 : : */
3076 tgl@sss.pgh.pa.us 133 : 1000000 : uint64 oldlo = i128->lo;
134 : :
135 : 1000000 : i128->lo += v;
30 dean.a.rasheed@gmail 136 : 1000000 : i128->hi += (i128->lo < oldlo) + (v >> 63);
137 : : #endif
3076 tgl@sss.pgh.pa.us 138 :GIC 1278739 : }
139 : :
140 : : /*
141 : : * Add an INT128 value into an INT128 variable.
142 : : */
143 : : static inline void
30 dean.a.rasheed@gmail 144 :GNC 1000027 : int128_add_int128(INT128 *i128, INT128 v)
145 : : {
146 : : #if USE_NATIVE_INT128
147 : 27 : *i128 += v;
148 : : #else
149 : 1000000 : int128_add_uint64(i128, v.lo);
150 : 1000000 : i128->hi += v.hi;
151 : : #endif
152 : 1000027 : }
153 : :
154 : : /*
155 : : * Subtract an unsigned int64 value from an INT128 variable.
156 : : */
157 : : static inline void
158 : 4000000 : int128_sub_uint64(INT128 *i128, uint64 v)
159 : : {
160 : : #if USE_NATIVE_INT128
161 : : *i128 -= v;
162 : : #else
163 : : /*
164 : : * This is like int128_add_uint64(), except we must propagate a borrow to
165 : : * (subtract 1 from) the .hi part if the new .lo part is greater than the
166 : : * old .lo part.
167 : : */
30 dean.a.rasheed@gmail 168 :GIC 4000000 : uint64 oldlo = i128->lo;
169 : :
30 dean.a.rasheed@gmail 170 :GNC 4000000 : i128->lo -= v;
171 : 4000000 : i128->hi -= (i128->lo > oldlo);
172 : : #endif
30 dean.a.rasheed@gmail 173 :GIC 4000000 : }
174 : :
175 : : /*
176 : : * Subtract a signed int64 value from an INT128 variable.
177 : : */
178 : : static inline void
30 dean.a.rasheed@gmail 179 :GNC 1000156 : int128_sub_int64(INT128 *i128, int64 v)
180 : : {
181 : : #if USE_NATIVE_INT128
182 : 156 : *i128 -= v;
183 : : #else
184 : : /* Like int128_add_int64() with the sign of v inverted */
30 dean.a.rasheed@gmail 185 :GIC 1000000 : uint64 oldlo = i128->lo;
186 : :
30 dean.a.rasheed@gmail 187 :GNC 1000000 : i128->lo -= v;
188 : 1000000 : i128->hi -= (i128->lo > oldlo) + (v >> 63);
189 : : #endif
30 dean.a.rasheed@gmail 190 :GIC 1000156 : }
191 : :
192 : : /*
193 : : * INT64_HI_INT32 extracts the most significant 32 bits of int64 as int32.
194 : : * INT64_LO_UINT32 extracts the least significant 32 bits as uint32.
195 : : */
196 : : #define INT64_HI_INT32(i64) ((int32) ((i64) >> 32))
197 : : #define INT64_LO_UINT32(i64) ((uint32) (i64))
198 : :
199 : : /*
200 : : * Add the 128-bit product of two int64 values into an INT128 variable.
201 : : */
202 : : static inline void
3076 tgl@sss.pgh.pa.us 203 : 1418844 : int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
204 : : {
205 : : #if USE_NATIVE_INT128
206 : : /*
207 : : * XXX with a stupid compiler, this could actually be less efficient than
208 : : * the non-native implementation; maybe we should do it by hand always?
209 : : */
31 dean.a.rasheed@gmail 210 :GNC 418844 : *i128 += (int128) x * (int128) y;
211 : : #else
212 : : /* INT64_HI_INT32 must use arithmetic right shift */
213 : : StaticAssertDecl(((int64) -1 >> 1) == (int64) -1,
214 : : "arithmetic right shift is needed");
215 : :
216 : : /*----------
217 : : * Form the 128-bit product x * y using 64-bit arithmetic.
218 : : * Considering each 64-bit input as having 32-bit high and low parts,
219 : : * we can compute
220 : : *
221 : : * x * y = ((x.hi << 32) + x.lo) * (((y.hi << 32) + y.lo)
222 : : * = (x.hi * y.hi) << 64 +
223 : : * (x.hi * y.lo) << 32 +
224 : : * (x.lo * y.hi) << 32 +
225 : : * x.lo * y.lo
226 : : *
227 : : * Each individual product is of 32-bit terms so it won't overflow when
228 : : * computed in 64-bit arithmetic. Then we just have to shift it to the
229 : : * correct position while adding into the 128-bit result. We must also
230 : : * keep in mind that the "lo" parts must be treated as unsigned.
231 : : *----------
232 : : */
233 : :
234 : : /* No need to work hard if product must be zero */
3076 tgl@sss.pgh.pa.us 235 [ + - + - ]:GIC 1000000 : if (x != 0 && y != 0)
236 : : {
30 dean.a.rasheed@gmail 237 :GNC 1000000 : int32 x_hi = INT64_HI_INT32(x);
238 : 1000000 : uint32 x_lo = INT64_LO_UINT32(x);
239 : 1000000 : int32 y_hi = INT64_HI_INT32(y);
240 : 1000000 : uint32 y_lo = INT64_LO_UINT32(y);
241 : : int64 tmp;
242 : :
243 : : /* the first term */
244 : 1000000 : i128->hi += (int64) x_hi * (int64) y_hi;
245 : :
246 : : /* the second term: sign-extended with the sign of x */
247 : 1000000 : tmp = (int64) x_hi * (int64) y_lo;
248 : 1000000 : i128->hi += INT64_HI_INT32(tmp);
249 : 1000000 : int128_add_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);
250 : :
251 : : /* the third term: sign-extended with the sign of y */
252 : 1000000 : tmp = (int64) x_lo * (int64) y_hi;
253 : 1000000 : i128->hi += INT64_HI_INT32(tmp);
254 : 1000000 : int128_add_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);
255 : :
256 : : /* the fourth term: always unsigned */
257 : 1000000 : int128_add_uint64(i128, (uint64) x_lo * (uint64) y_lo);
258 : : }
259 : : #endif
3076 tgl@sss.pgh.pa.us 260 : 1418844 : }
261 : :
262 : : /*
263 : : * Subtract the 128-bit product of two int64 values from an INT128 variable.
264 : : */
265 : : static inline void
30 dean.a.rasheed@gmail 266 : 1000144 : int128_sub_int64_mul_int64(INT128 *i128, int64 x, int64 y)
267 : : {
268 : : #if USE_NATIVE_INT128
269 : 144 : *i128 -= (int128) x * (int128) y;
270 : : #else
271 : : /* As above, except subtract the 128-bit product */
272 [ + - + - ]: 1000000 : if (x != 0 && y != 0)
273 : : {
274 : 1000000 : int32 x_hi = INT64_HI_INT32(x);
275 : 1000000 : uint32 x_lo = INT64_LO_UINT32(x);
276 : 1000000 : int32 y_hi = INT64_HI_INT32(y);
277 : 1000000 : uint32 y_lo = INT64_LO_UINT32(y);
278 : : int64 tmp;
279 : :
280 : : /* the first term */
281 : 1000000 : i128->hi -= (int64) x_hi * (int64) y_hi;
282 : :
283 : : /* the second term: sign-extended with the sign of x */
284 : 1000000 : tmp = (int64) x_hi * (int64) y_lo;
285 : 1000000 : i128->hi -= INT64_HI_INT32(tmp);
286 : 1000000 : int128_sub_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);
287 : :
288 : : /* the third term: sign-extended with the sign of y */
289 : 1000000 : tmp = (int64) x_lo * (int64) y_hi;
290 : 1000000 : i128->hi -= INT64_HI_INT32(tmp);
291 : 1000000 : int128_sub_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);
292 : :
293 : : /* the fourth term: always unsigned */
294 : 1000000 : int128_sub_uint64(i128, (uint64) x_lo * (uint64) y_lo);
295 : : }
296 : : #endif
297 : 1000144 : }
298 : :
299 : : /*
300 : : * Divide an INT128 variable by a signed int32 value, returning the quotient
301 : : * and remainder. The remainder will have the same sign as *i128.
302 : : *
303 : : * Note: This provides no protection against dividing by 0, or dividing
304 : : * INT128_MIN by -1, which overflows. It is the caller's responsibility to
305 : : * guard against those.
306 : : */
307 : : static inline void
308 : 1022620 : int128_div_mod_int32(INT128 *i128, int32 v, int32 *remainder)
309 : : {
310 : : #if USE_NATIVE_INT128
311 : 22620 : int128 old_i128 = *i128;
312 : :
313 : 22620 : *i128 /= v;
314 : 22620 : *remainder = (int32) (old_i128 - *i128 * v);
315 : : #else
316 : : /*
317 : : * To avoid any intermediate values overflowing (as happens if INT64_MIN
318 : : * is divided by -1), we first compute the quotient abs(*i128) / abs(v)
319 : : * using unsigned 64-bit arithmetic, and then fix the signs up at the end.
320 : : *
321 : : * The quotient is computed using the short division algorithm described
322 : : * in Knuth volume 2, section 4.3.1 exercise 16 (cf. div_var_int() in
323 : : * numeric.c). Since the absolute value of the divisor is known to be at
324 : : * most 2^31, the remainder carried from one digit to the next is at most
325 : : * 2^31 - 1, and so there is no danger of overflow when this is combined
326 : : * with the next digit (a 32-bit unsigned integer).
327 : : */
328 : : uint64 n_hi;
329 : : uint64 n_lo;
330 : : uint32 d;
331 : : uint64 q;
332 : : uint64 r;
333 : : uint64 tmp;
334 : :
335 : : /* numerator: absolute value of *i128 */
336 [ + + ]: 1000000 : if (i128->hi < 0)
337 : : {
338 : 500052 : n_hi = 0 - ((uint64) i128->hi);
339 : 500052 : n_lo = 0 - i128->lo;
340 [ + - ]: 500052 : if (n_lo != 0)
341 : 500052 : n_hi--;
342 : : }
343 : : else
344 : : {
345 : 499948 : n_hi = i128->hi;
346 : 499948 : n_lo = i128->lo;
347 : : }
348 : :
349 : : /* denomimator: absolute value of v */
350 : 1000000 : d = abs(v);
351 : :
352 : : /* quotient and remainder of high 64 bits */
353 : 1000000 : q = n_hi / d;
354 : 1000000 : r = n_hi % d;
355 : 1000000 : n_hi = q;
356 : :
357 : : /* quotient and remainder of next 32 bits (upper half of n_lo) */
358 : 1000000 : tmp = (r << 32) + (n_lo >> 32);
359 : 1000000 : q = tmp / d;
360 : 1000000 : r = tmp % d;
361 : :
362 : : /* quotient and remainder of last 32 bits (lower half of n_lo) */
363 : 1000000 : tmp = (r << 32) + (uint32) n_lo;
364 : 1000000 : n_lo = q << 32;
365 : 1000000 : q = tmp / d;
366 : 1000000 : r = tmp % d;
367 : 1000000 : n_lo += q;
368 : :
369 : : /* final remainder should have the same sign as *i128 */
370 [ + + ]: 1000000 : *remainder = i128->hi < 0 ? (int32) (0 - r) : (int32) r;
371 : :
372 : : /* store the quotient in *i128, negating it if necessary */
373 [ + + ]: 1000000 : if ((i128->hi < 0) != (v < 0))
374 : : {
375 : 500771 : n_hi = 0 - n_hi;
376 : 500771 : n_lo = 0 - n_lo;
377 [ + - ]: 500771 : if (n_lo != 0)
378 : 500771 : n_hi--;
379 : : }
380 : 1000000 : i128->hi = (int64) n_hi;
381 : 1000000 : i128->lo = n_lo;
382 : : #endif
383 : 1022620 : }
384 : :
385 : : /*
386 : : * Test if an INT128 value is zero.
387 : : */
388 : : static inline bool
389 : 22620 : int128_is_zero(INT128 x)
390 : : {
391 : : #if USE_NATIVE_INT128
392 : 22620 : return x == 0;
393 : : #else
394 : : return x.hi == 0 && x.lo == 0;
395 : : #endif
396 : : }
397 : :
398 : : /*
399 : : * Return the sign of an INT128 value (returns -1, 0, or +1).
400 : : */
401 : : static inline int
402 : 4397 : int128_sign(INT128 x)
403 : : {
404 : : #if USE_NATIVE_INT128
405 [ + + ]: 4397 : if (x < 0)
406 : 6 : return -1;
407 [ + + ]: 4391 : if (x > 0)
408 : 4286 : return 1;
409 : 105 : return 0;
410 : : #else
411 : : if (x.hi < 0)
412 : : return -1;
413 : : if (x.hi > 0)
414 : : return 1;
415 : : if (x.lo > 0)
416 : : return 1;
417 : : return 0;
418 : : #endif
419 : : }
420 : :
421 : : /*
422 : : * Compare two INT128 values, return -1, 0, or +1.
423 : : */
424 : : static inline int
3076 tgl@sss.pgh.pa.us 425 :GIC 2149464 : int128_compare(INT128 x, INT128 y)
426 : : {
427 : : #if USE_NATIVE_INT128
31 dean.a.rasheed@gmail 428 [ + + ]:GNC 149464 : if (x < y)
429 : 83057 : return -1;
430 [ + + ]: 66407 : if (x > y)
431 : 55622 : return 1;
432 : 10785 : return 0;
433 : : #else
3076 tgl@sss.pgh.pa.us 434 [ + + ]:GIC 2000000 : if (x.hi < y.hi)
435 : 499487 : return -1;
436 [ + + ]: 1500513 : if (x.hi > y.hi)
437 : 500513 : return 1;
438 [ + + ]: 1000000 : if (x.lo < y.lo)
439 : 499812 : return -1;
440 [ + - ]: 500188 : if (x.lo > y.lo)
441 : 500188 : return 1;
3076 tgl@sss.pgh.pa.us 442 :UIC 0 : return 0;
443 : : #endif
444 : : }
445 : :
446 : : /*
447 : : * Widen int64 to INT128.
448 : : */
449 : : static inline INT128
3076 tgl@sss.pgh.pa.us 450 :GIC 300107 : int64_to_int128(int64 v)
451 : : {
452 : : #if USE_NATIVE_INT128
31 dean.a.rasheed@gmail 453 :GNC 300107 : return (INT128) v;
454 : : #else
455 : : INT128 val;
456 : :
457 : : val.lo = (uint64) v;
458 : : val.hi = (v < 0) ? -INT64CONST(1) : INT64CONST(0);
459 : : return val;
460 : : #endif
461 : : }
462 : :
463 : : /*
464 : : * Convert INT128 to int64 (losing any high-order bits).
465 : : * This also works fine for casting down to uint64.
466 : : */
467 : : static inline int64
3076 tgl@sss.pgh.pa.us 468 :GIC 1173 : int128_to_int64(INT128 val)
469 : : {
470 : : #if USE_NATIVE_INT128
31 dean.a.rasheed@gmail 471 :GNC 1173 : return (int64) val;
472 : : #else
473 : : return (int64) val.lo;
474 : : #endif
475 : : }
476 : :
477 : : #endif /* INT128_H */
|
