PostgreSQL Source Code  git master
int128.h
Go to the documentation of this file.
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/tools/testint128.c for a simple test harness for this file.
10  *
11  * Copyright (c) 2017-2019, 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 USE_NATIVE_INT128
34 
35 typedef int128 INT128;
36 
37 /*
38  * Add an unsigned int64 value into an INT128 variable.
39  */
40 static inline void
41 int128_add_uint64(INT128 *i128, uint64 v)
42 {
43  *i128 += v;
44 }
45 
46 /*
47  * Add a signed int64 value into an INT128 variable.
48  */
49 static inline void
50 int128_add_int64(INT128 *i128, int64 v)
51 {
52  *i128 += v;
53 }
54 
55 /*
56  * Add the 128-bit product of two int64 values into an INT128 variable.
57  *
58  * XXX with a stupid compiler, this could actually be less efficient than
59  * the other implementation; maybe we should do it by hand always?
60  */
61 static inline void
62 int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
63 {
64  *i128 += (int128) x * (int128) y;
65 }
66 
67 /*
68  * Compare two INT128 values, return -1, 0, or +1.
69  */
70 static inline int
72 {
73  if (x < y)
74  return -1;
75  if (x > y)
76  return 1;
77  return 0;
78 }
79 
80 /*
81  * Widen int64 to INT128.
82  */
83 static inline INT128
84 int64_to_int128(int64 v)
85 {
86  return (INT128) v;
87 }
88 
89 /*
90  * Convert INT128 to int64 (losing any high-order bits).
91  * This also works fine for casting down to uint64.
92  */
93 static inline int64
95 {
96  return (int64) val;
97 }
98 
99 #else /* !USE_NATIVE_INT128 */
100 
101 /*
102  * We lay out the INT128 structure with the same content and byte ordering
103  * that a native int128 type would (probably) have. This makes no difference
104  * for ordinary use of INT128, but allows union'ing INT128 with int128 for
105  * testing purposes.
106  */
107 typedef struct
108 {
109 #ifdef WORDS_BIGENDIAN
110  int64 hi; /* most significant 64 bits, including sign */
111  uint64 lo; /* least significant 64 bits, without sign */
112 #else
113  uint64 lo; /* least significant 64 bits, without sign */
114  int64 hi; /* most significant 64 bits, including sign */
115 #endif
116 } INT128;
117 
118 /*
119  * Add an unsigned int64 value into an INT128 variable.
120  */
121 static inline void
122 int128_add_uint64(INT128 *i128, uint64 v)
123 {
124  /*
125  * First add the value to the .lo part, then check to see if a carry needs
126  * to be propagated into the .hi part. A carry is needed if both inputs
127  * have high bits set, or if just one input has high bit set while the new
128  * .lo part doesn't. Remember that .lo part is unsigned; we cast to
129  * signed here just as a cheap way to check the high bit.
130  */
131  uint64 oldlo = i128->lo;
132 
133  i128->lo += v;
134  if (((int64) v < 0 && (int64) oldlo < 0) ||
135  (((int64) v < 0 || (int64) oldlo < 0) && (int64) i128->lo >= 0))
136  i128->hi++;
137 }
138 
139 /*
140  * Add a signed int64 value into an INT128 variable.
141  */
142 static inline void
143 int128_add_int64(INT128 *i128, int64 v)
144 {
145  /*
146  * This is much like the above except that the carry logic differs for
147  * negative v. Ordinarily we'd need to subtract 1 from the .hi part
148  * (corresponding to adding the sign-extended bits of v to it); but if
149  * there is a carry out of the .lo part, that cancels and we do nothing.
150  */
151  uint64 oldlo = i128->lo;
152 
153  i128->lo += v;
154  if (v >= 0)
155  {
156  if ((int64) oldlo < 0 && (int64) i128->lo >= 0)
157  i128->hi++;
158  }
159  else
160  {
161  if (!((int64) oldlo < 0 || (int64) i128->lo >= 0))
162  i128->hi--;
163  }
164 }
165 
166 /*
167  * INT64_AU32 extracts the most significant 32 bits of int64 as int64, while
168  * INT64_AL32 extracts the least significant 32 bits as uint64.
169  */
170 #define INT64_AU32(i64) ((i64) >> 32)
171 #define INT64_AL32(i64) ((i64) & UINT64CONST(0xFFFFFFFF))
172 
173 /*
174  * Add the 128-bit product of two int64 values into an INT128 variable.
175  */
176 static inline void
177 int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
178 {
179  /* INT64_AU32 must use arithmetic right shift */
180  StaticAssertStmt(((int64) -1 >> 1) == (int64) -1,
181  "arithmetic right shift is needed");
182 
183  /*----------
184  * Form the 128-bit product x * y using 64-bit arithmetic.
185  * Considering each 64-bit input as having 32-bit high and low parts,
186  * we can compute
187  *
188  * x * y = ((x.hi << 32) + x.lo) * (((y.hi << 32) + y.lo)
189  * = (x.hi * y.hi) << 64 +
190  * (x.hi * y.lo) << 32 +
191  * (x.lo * y.hi) << 32 +
192  * x.lo * y.lo
193  *
194  * Each individual product is of 32-bit terms so it won't overflow when
195  * computed in 64-bit arithmetic. Then we just have to shift it to the
196  * correct position while adding into the 128-bit result. We must also
197  * keep in mind that the "lo" parts must be treated as unsigned.
198  *----------
199  */
200 
201  /* No need to work hard if product must be zero */
202  if (x != 0 && y != 0)
203  {
204  int64 x_u32 = INT64_AU32(x);
205  uint64 x_l32 = INT64_AL32(x);
206  int64 y_u32 = INT64_AU32(y);
207  uint64 y_l32 = INT64_AL32(y);
208  int64 tmp;
209 
210  /* the first term */
211  i128->hi += x_u32 * y_u32;
212 
213  /* the second term: sign-extend it only if x is negative */
214  tmp = x_u32 * y_l32;
215  if (x < 0)
216  i128->hi += INT64_AU32(tmp);
217  else
218  i128->hi += ((uint64) tmp) >> 32;
219  int128_add_uint64(i128, ((uint64) INT64_AL32(tmp)) << 32);
220 
221  /* the third term: sign-extend it only if y is negative */
222  tmp = x_l32 * y_u32;
223  if (y < 0)
224  i128->hi += INT64_AU32(tmp);
225  else
226  i128->hi += ((uint64) tmp) >> 32;
227  int128_add_uint64(i128, ((uint64) INT64_AL32(tmp)) << 32);
228 
229  /* the fourth term: always unsigned */
230  int128_add_uint64(i128, x_l32 * y_l32);
231  }
232 }
233 
234 /*
235  * Compare two INT128 values, return -1, 0, or +1.
236  */
237 static inline int
239 {
240  if (x.hi < y.hi)
241  return -1;
242  if (x.hi > y.hi)
243  return 1;
244  if (x.lo < y.lo)
245  return -1;
246  if (x.lo > y.lo)
247  return 1;
248  return 0;
249 }
250 
251 /*
252  * Widen int64 to INT128.
253  */
254 static inline INT128
256 {
257  INT128 val;
258 
259  val.lo = (uint64) v;
260  val.hi = (v < 0) ? -INT64CONST(1) : INT64CONST(0);
261  return val;
262 }
263 
264 /*
265  * Convert INT128 to int64 (losing any high-order bits).
266  * This also works fine for casting down to uint64.
267  */
268 static inline int64
270 {
271  return (int64) val.lo;
272 }
273 
274 #endif /* USE_NATIVE_INT128 */
275 
276 #endif /* INT128_H */
static void int128_add_uint64(INT128 *i128, uint64 v)
Definition: int128.h:122
static int int128_compare(INT128 x, INT128 y)
Definition: int128.h:238
#define StaticAssertStmt(condition, errmessage)
Definition: c.h:842
uint64 lo
Definition: int128.h:113
static INT128 int64_to_int128(int64 v)
Definition: int128.h:255
int64 hi
Definition: int128.h:114
#define INT64_AU32(i64)
Definition: int128.h:170
Definition: int128.h:107
static void int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
Definition: int128.h:177
static int64 int128_to_int64(INT128 val)
Definition: int128.h:269
static void int128_add_int64(INT128 *i128, int64 v)
Definition: int128.h:143
long val
Definition: informix.c:684
#define INT64_AL32(i64)
Definition: int128.h:171