/src/postgres/src/include/common/int128.h

Source
/*-------------------------------------------------------------------------
 *
 * int128.h
 *    Roll-our-own 128-bit integer arithmetic.
 *
 * We make use of the native int128 type if there is one, otherwise
 * implement things the hard way based on two int64 halves.
 *
 * See src/test/modules/test_int128 for a simple test harness for this file.
 *
 * Copyright (c) 2017-2025, PostgreSQL Global Development Group
 *
 * src/include/common/int128.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef INT128_H
#define INT128_H

/*
 * For testing purposes, use of native int128 can be switched on/off by
 * predefining USE_NATIVE_INT128.
 */
#ifndef USE_NATIVE_INT128
#ifdef HAVE_INT128
#define USE_NATIVE_INT128 1
#else
#define USE_NATIVE_INT128 0
#endif
#endif

/*
 * If native int128 support is enabled, INT128 is just int128. Otherwise, it
 * is a structure with separate 64-bit high and low parts.
 *
 * We lay out the INT128 structure with the same content and byte ordering
 * that a native int128 type would (probably) have.  This makes no difference
 * for ordinary use of INT128, but allows union'ing INT128 with int128 for
 * testing purposes.
 *
 * PG_INT128_HI_INT64 and PG_INT128_LO_UINT64 allow the (signed) high and
 * (unsigned) low 64-bit integer parts to be extracted portably on all
 * platforms.
 */
#if USE_NATIVE_INT128

typedef int128 INT128;

#define PG_INT128_HI_INT64(i128)  ((int64) ((i128) >> 64))
#define PG_INT128_LO_UINT64(i128) ((uint64) (i128))

#else

typedef struct
{
#ifdef WORDS_BIGENDIAN
  int64   hi;       /* most significant 64 bits, including sign */
  uint64    lo;       /* least significant 64 bits, without sign */
#else
  uint64    lo;       /* least significant 64 bits, without sign */
  int64   hi;       /* most significant 64 bits, including sign */
#endif
} INT128;

#define PG_INT128_HI_INT64(i128)  ((i128).hi)
#define PG_INT128_LO_UINT64(i128) ((i128).lo)

#endif

/*
 * Construct an INT128 from (signed) high and (unsigned) low 64-bit integer
 * parts.
 */
static inline INT128
make_int128(int64 hi, uint64 lo)
{
#if USE_NATIVE_INT128
  return (((int128) hi) << 64) + lo;
#else
  INT128    val;

  val.hi = hi;
  val.lo = lo;
  return val;
#endif
}

/*
 * Add an unsigned int64 value into an INT128 variable.
 */
static inline void
int128_add_uint64(INT128 *i128, uint64 v)
{
#if USE_NATIVE_INT128
  *i128 += v;
#else
  /*
   * First add the value to the .lo part, then check to see if a carry needs
   * to be propagated into the .hi part.  Since this is unsigned integer
   * arithmetic, which is just modular arithmetic, a carry is needed if the
   * new .lo part is less than the old .lo part (i.e., if modular
   * wrap-around occurred).  Writing this in the form below, rather than
   * using an "if" statement causes modern compilers to produce branchless
   * machine code identical to the native code.
   */
  uint64    oldlo = i128->lo;

  i128->lo += v;
  i128->hi += (i128->lo < oldlo);
#endif
}

/*
 * Add a signed int64 value into an INT128 variable.
 */
static inline void
int128_add_int64(INT128 *i128, int64 v)
{
#if USE_NATIVE_INT128
  *i128 += v;
#else
  /*
   * This is much like the above except that the carry logic differs for
   * negative v -- we need to subtract 1 from the .hi part if the new .lo
   * value is greater than the old .lo value.  That can be achieved without
   * any branching by adding the sign bit from v (v >> 63 = 0 or -1) to the
   * previous result (for negative v, if the new .lo value is less than the
   * old .lo value, the two terms cancel and we leave the .hi part
   * unchanged, otherwise we subtract 1 from the .hi part).  With modern
   * compilers this often produces machine code identical to the native
   * code.
   */
  uint64    oldlo = i128->lo;

  i128->lo += v;
  i128->hi += (i128->lo < oldlo) + (v >> 63);
#endif
}

/*
 * Add an INT128 value into an INT128 variable.
 */
static inline void
int128_add_int128(INT128 *i128, INT128 v)
{
#if USE_NATIVE_INT128
  *i128 += v;
#else
  int128_add_uint64(i128, v.lo);
  i128->hi += v.hi;
#endif
}

/*
 * Subtract an unsigned int64 value from an INT128 variable.
 */
static inline void
int128_sub_uint64(INT128 *i128, uint64 v)
{
#if USE_NATIVE_INT128
  *i128 -= v;
#else
  /*
   * This is like int128_add_uint64(), except we must propagate a borrow to
   * (subtract 1 from) the .hi part if the new .lo part is greater than the
   * old .lo part.
   */
  uint64    oldlo = i128->lo;

  i128->lo -= v;
  i128->hi -= (i128->lo > oldlo);
#endif
}

/*
 * Subtract a signed int64 value from an INT128 variable.
 */
static inline void
int128_sub_int64(INT128 *i128, int64 v)
{
#if USE_NATIVE_INT128
  *i128 -= v;
#else
  /* Like int128_add_int64() with the sign of v inverted */
  uint64    oldlo = i128->lo;

  i128->lo -= v;
  i128->hi -= (i128->lo > oldlo) + (v >> 63);
#endif
}

/*
 * INT64_HI_INT32 extracts the most significant 32 bits of int64 as int32.
 * INT64_LO_UINT32 extracts the least significant 32 bits as uint32.
 */
#define INT64_HI_INT32(i64)   ((int32) ((i64) >> 32))
#define INT64_LO_UINT32(i64)  ((uint32) (i64))

/*
 * Add the 128-bit product of two int64 values into an INT128 variable.
 */
static inline void
int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
{
#if USE_NATIVE_INT128
  /*
   * XXX with a stupid compiler, this could actually be less efficient than
   * the non-native implementation; maybe we should do it by hand always?
   */
  *i128 += (int128) x * (int128) y;
#else
  /* INT64_HI_INT32 must use arithmetic right shift */
  StaticAssertDecl(((int64) -1 >> 1) == (int64) -1,
           "arithmetic right shift is needed");

  /*----------
   * Form the 128-bit product x * y using 64-bit arithmetic.
   * Considering each 64-bit input as having 32-bit high and low parts,
   * we can compute
   *
   *   x * y = ((x.hi << 32) + x.lo) * (((y.hi << 32) + y.lo)
   *       = (x.hi * y.hi) << 64 +
   *       (x.hi * y.lo) << 32 +
   *       (x.lo * y.hi) << 32 +
   *       x.lo * y.lo
   *
   * Each individual product is of 32-bit terms so it won't overflow when
   * computed in 64-bit arithmetic.  Then we just have to shift it to the
   * correct position while adding into the 128-bit result.  We must also
   * keep in mind that the "lo" parts must be treated as unsigned.
   *----------
   */

  /* No need to work hard if product must be zero */
  if (x != 0 && y != 0)
  {
    int32   x_hi = INT64_HI_INT32(x);
    uint32    x_lo = INT64_LO_UINT32(x);
    int32   y_hi = INT64_HI_INT32(y);
    uint32    y_lo = INT64_LO_UINT32(y);
    int64   tmp;

    /* the first term */
    i128->hi += (int64) x_hi * (int64) y_hi;

    /* the second term: sign-extended with the sign of x */
    tmp = (int64) x_hi * (int64) y_lo;
    i128->hi += INT64_HI_INT32(tmp);
    int128_add_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);

    /* the third term: sign-extended with the sign of y */
    tmp = (int64) x_lo * (int64) y_hi;
    i128->hi += INT64_HI_INT32(tmp);
    int128_add_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);

    /* the fourth term: always unsigned */
    int128_add_uint64(i128, (uint64) x_lo * (uint64) y_lo);
  }
#endif
}

/*
 * Subtract the 128-bit product of two int64 values from an INT128 variable.
 */
static inline void
int128_sub_int64_mul_int64(INT128 *i128, int64 x, int64 y)
{
#if USE_NATIVE_INT128
  *i128 -= (int128) x * (int128) y;
#else
  /* As above, except subtract the 128-bit product */
  if (x != 0 && y != 0)
  {
    int32   x_hi = INT64_HI_INT32(x);
    uint32    x_lo = INT64_LO_UINT32(x);
    int32   y_hi = INT64_HI_INT32(y);
    uint32    y_lo = INT64_LO_UINT32(y);
    int64   tmp;

    /* the first term */
    i128->hi -= (int64) x_hi * (int64) y_hi;

    /* the second term: sign-extended with the sign of x */
    tmp = (int64) x_hi * (int64) y_lo;
    i128->hi -= INT64_HI_INT32(tmp);
    int128_sub_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);

    /* the third term: sign-extended with the sign of y */
    tmp = (int64) x_lo * (int64) y_hi;
    i128->hi -= INT64_HI_INT32(tmp);
    int128_sub_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);

    /* the fourth term: always unsigned */
    int128_sub_uint64(i128, (uint64) x_lo * (uint64) y_lo);
  }
#endif
}

/*
 * Divide an INT128 variable by a signed int32 value, returning the quotient
 * and remainder.  The remainder will have the same sign as *i128.
 *
 * Note: This provides no protection against dividing by 0, or dividing
 * INT128_MIN by -1, which overflows.  It is the caller's responsibility to
 * guard against those.
 */
static inline void
int128_div_mod_int32(INT128 *i128, int32 v, int32 *remainder)
{
#if USE_NATIVE_INT128
  int128    old_i128 = *i128;

  *i128 /= v;
  *remainder = (int32) (old_i128 - *i128 * v);
#else
  /*
   * To avoid any intermediate values overflowing (as happens if INT64_MIN
   * is divided by -1), we first compute the quotient abs(*i128) / abs(v)
   * using unsigned 64-bit arithmetic, and then fix the signs up at the end.
   *
   * The quotient is computed using the short division algorithm described
   * in Knuth volume 2, section 4.3.1 exercise 16 (cf. div_var_int() in
   * numeric.c).  Since the absolute value of the divisor is known to be at
   * most 2^31, the remainder carried from one digit to the next is at most
   * 2^31 - 1, and so there is no danger of overflow when this is combined
   * with the next digit (a 32-bit unsigned integer).
   */
  uint64    n_hi;
  uint64    n_lo;
  uint32    d;
  uint64    q;
  uint64    r;
  uint64    tmp;

  /* numerator: absolute value of *i128 */
  if (i128->hi < 0)
  {
    n_hi = 0 - ((uint64) i128->hi);
    n_lo = 0 - i128->lo;
    if (n_lo != 0)
      n_hi--;
  }
  else
  {
    n_hi = i128->hi;
    n_lo = i128->lo;
  }

  /* denomimator: absolute value of v */
  d = abs(v);

  /* quotient and remainder of high 64 bits */
  q = n_hi / d;
  r = n_hi % d;
  n_hi = q;

  /* quotient and remainder of next 32 bits (upper half of n_lo) */
  tmp = (r << 32) + (n_lo >> 32);
  q = tmp / d;
  r = tmp % d;

  /* quotient and remainder of last 32 bits (lower half of n_lo) */
  tmp = (r << 32) + (uint32) n_lo;
  n_lo = q << 32;
  q = tmp / d;
  r = tmp % d;
  n_lo += q;

  /* final remainder should have the same sign as *i128 */
  *remainder = i128->hi < 0 ? (int32) (0 - r) : (int32) r;

  /* store the quotient in *i128, negating it if necessary */
  if ((i128->hi < 0) != (v < 0))
  {
    n_hi = 0 - n_hi;
    n_lo = 0 - n_lo;
    if (n_lo != 0)
      n_hi--;
  }
  i128->hi = (int64) n_hi;
  i128->lo = n_lo;
#endif
}

/*
 * Test if an INT128 value is zero.
 */
static inline bool
int128_is_zero(INT128 x)
{
#if USE_NATIVE_INT128
  return x == 0;
#else
  return x.hi == 0 && x.lo == 0;
#endif
}

/*
 * Return the sign of an INT128 value (returns -1, 0, or +1).
 */
static inline int
int128_sign(INT128 x)
{
#if USE_NATIVE_INT128
  if (x < 0)
    return -1;
  if (x > 0)
    return 1;
  return 0;
#else
  if (x.hi < 0)
    return -1;
  if (x.hi > 0)
    return 1;
  if (x.lo > 0)
    return 1;
  return 0;
#endif
}

/*
 * Compare two INT128 values, return -1, 0, or +1.
 */
static inline int
int128_compare(INT128 x, INT128 y)
{
#if USE_NATIVE_INT128
  if (x < y)
    return -1;
  if (x > y)
    return 1;
  return 0;
#else
  if (x.hi < y.hi)
    return -1;
  if (x.hi > y.hi)
    return 1;
  if (x.lo < y.lo)
    return -1;
  if (x.lo > y.lo)
    return 1;
  return 0;
#endif
}

/*
 * Widen int64 to INT128.
 */
static inline INT128
int64_to_int128(int64 v)
{
#if USE_NATIVE_INT128
  return (INT128) v;
#else
  INT128    val;

  val.lo = (uint64) v;
  val.hi = (v < 0) ? -INT64CONST(1) : INT64CONST(0);
  return val;
#endif
}

/*
 * Convert INT128 to int64 (losing any high-order bits).
 * This also works fine for casting down to uint64.
 */
static inline int64
int128_to_int64(INT128 val)
{
#if USE_NATIVE_INT128
  return (int64) val;
#else
  return (int64) val.lo;
#endif
}

#endif              /* INT128_H */

Coverage Report

Created: 2025-09-27 06:52

Line	Count	Source
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	0	#define PG_INT128_HI_INT64(i128) ((int64) ((i128) >> 64))
50	0	#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
75		make_int128(int64 hi, uint64 lo)
76	0	{
77	0	#if USE_NATIVE_INT128
78	0	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	0	} Unexecuted instantiation: numeric.c:make_int128 Unexecuted instantiation: timestamp.c:make_int128
87
88		/*
89		* Add an unsigned int64 value into an INT128 variable.
90		*/
91		static inline void
92		int128_add_uint64(INT128 *i128, uint64 v)
93	0	{
94	0	#if USE_NATIVE_INT128
95	0	*i128 += v;
96	0	#else
97	0	/*
98	0	* First add the value to the .lo part, then check to see if a carry needs
99	0	* to be propagated into the .hi part. Since this is unsigned integer
100	0	* arithmetic, which is just modular arithmetic, a carry is needed if the
101	0	* new .lo part is less than the old .lo part (i.e., if modular
102	0	* wrap-around occurred). Writing this in the form below, rather than
103	0	* using an "if" statement causes modern compilers to produce branchless
104	0	* machine code identical to the native code.
105	0	*/
106	0	uint64 oldlo = i128->lo;
107	0
108	0	i128->lo += v;
109	0	i128->hi += (i128->lo < oldlo);
110	0	#endif
111	0	} Unexecuted instantiation: numeric.c:int128_add_uint64 Unexecuted instantiation: timestamp.c:int128_add_uint64
112
113		/*
114		* Add a signed int64 value into an INT128 variable.
115		*/
116		static inline void
117		int128_add_int64(INT128 *i128, int64 v)
118	0	{
119	0	#if USE_NATIVE_INT128
120	0	*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		*/
133		uint64 oldlo = i128->lo;
134
135		i128->lo += v;
136		i128->hi += (i128->lo < oldlo) + (v >> 63);
137		#endif
138	0	} Unexecuted instantiation: numeric.c:int128_add_int64 Unexecuted instantiation: timestamp.c:int128_add_int64
139
140		/*
141		* Add an INT128 value into an INT128 variable.
142		*/
143		static inline void
144		int128_add_int128(INT128 *i128, INT128 v)
145	0	{
146	0	#if USE_NATIVE_INT128
147	0	*i128 += v;
148		#else
149		int128_add_uint64(i128, v.lo);
150		i128->hi += v.hi;
151		#endif
152	0	} Unexecuted instantiation: numeric.c:int128_add_int128 Unexecuted instantiation: timestamp.c:int128_add_int128
153
154		/*
155		* Subtract an unsigned int64 value from an INT128 variable.
156		*/
157		static inline void
158		int128_sub_uint64(INT128 *i128, uint64 v)
159	0	{
160	0	#if USE_NATIVE_INT128
161	0	*i128 -= v;
162	0	#else
163	0	/*
164	0	* This is like int128_add_uint64(), except we must propagate a borrow to
165	0	* (subtract 1 from) the .hi part if the new .lo part is greater than the
166	0	* old .lo part.
167	0	*/
168	0	uint64 oldlo = i128->lo;
169	0
170	0	i128->lo -= v;
171	0	i128->hi -= (i128->lo > oldlo);
172	0	#endif
173	0	} Unexecuted instantiation: numeric.c:int128_sub_uint64 Unexecuted instantiation: timestamp.c:int128_sub_uint64
174
175		/*
176		* Subtract a signed int64 value from an INT128 variable.
177		*/
178		static inline void
179		int128_sub_int64(INT128 *i128, int64 v)
180	0	{
181	0	#if USE_NATIVE_INT128
182	0	*i128 -= v;
183		#else
184		/* Like int128_add_int64() with the sign of v inverted */
185		uint64 oldlo = i128->lo;
186
187		i128->lo -= v;
188		i128->hi -= (i128->lo > oldlo) + (v >> 63);
189		#endif
190	0	} Unexecuted instantiation: numeric.c:int128_sub_int64 Unexecuted instantiation: timestamp.c:int128_sub_int64
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
203		int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
204	0	{
205	0	#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		*/
210	0	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 */
235		if (x != 0 && y != 0)
236		{
237		int32 x_hi = INT64_HI_INT32(x);
238		uint32 x_lo = INT64_LO_UINT32(x);
239		int32 y_hi = INT64_HI_INT32(y);
240		uint32 y_lo = INT64_LO_UINT32(y);
241		int64 tmp;
242
243		/* the first term */
244		i128->hi += (int64) x_hi * (int64) y_hi;
245
246		/* the second term: sign-extended with the sign of x */
247		tmp = (int64) x_hi * (int64) y_lo;
248		i128->hi += INT64_HI_INT32(tmp);
249		int128_add_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);
250
251		/* the third term: sign-extended with the sign of y */
252		tmp = (int64) x_lo * (int64) y_hi;
253		i128->hi += INT64_HI_INT32(tmp);
254		int128_add_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);
255
256		/* the fourth term: always unsigned */
257		int128_add_uint64(i128, (uint64) x_lo * (uint64) y_lo);
258		}
259		#endif
260	0	} Unexecuted instantiation: numeric.c:int128_add_int64_mul_int64 Unexecuted instantiation: timestamp.c:int128_add_int64_mul_int64
261
262		/*
263		* Subtract the 128-bit product of two int64 values from an INT128 variable.
264		*/
265		static inline void
266		int128_sub_int64_mul_int64(INT128 *i128, int64 x, int64 y)
267	0	{
268	0	#if USE_NATIVE_INT128
269	0	i128 -= (int128) x (int128) y;
270		#else
271		/* As above, except subtract the 128-bit product */
272		if (x != 0 && y != 0)
273		{
274		int32 x_hi = INT64_HI_INT32(x);
275		uint32 x_lo = INT64_LO_UINT32(x);
276		int32 y_hi = INT64_HI_INT32(y);
277		uint32 y_lo = INT64_LO_UINT32(y);
278		int64 tmp;
279
280		/* the first term */
281		i128->hi -= (int64) x_hi * (int64) y_hi;
282
283		/* the second term: sign-extended with the sign of x */
284		tmp = (int64) x_hi * (int64) y_lo;
285		i128->hi -= INT64_HI_INT32(tmp);
286		int128_sub_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);
287
288		/* the third term: sign-extended with the sign of y */
289		tmp = (int64) x_lo * (int64) y_hi;
290		i128->hi -= INT64_HI_INT32(tmp);
291		int128_sub_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);
292
293		/* the fourth term: always unsigned */
294		int128_sub_uint64(i128, (uint64) x_lo * (uint64) y_lo);
295		}
296		#endif
297	0	} Unexecuted instantiation: numeric.c:int128_sub_int64_mul_int64 Unexecuted instantiation: timestamp.c:int128_sub_int64_mul_int64
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		int128_div_mod_int32(INT128 i128, int32 v, int32 remainder)
309	0	{
310	0	#if USE_NATIVE_INT128
311	0	int128 old_i128 = *i128;
312
313	0	*i128 /= v;
314	0	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		if (i128->hi < 0)
337		{
338		n_hi = 0 - ((uint64) i128->hi);
339		n_lo = 0 - i128->lo;
340		if (n_lo != 0)
341		n_hi--;
342		}
343		else
344		{
345		n_hi = i128->hi;
346		n_lo = i128->lo;
347		}
348
349		/* denomimator: absolute value of v */
350		d = abs(v);
351
352		/* quotient and remainder of high 64 bits */
353		q = n_hi / d;
354		r = n_hi % d;
355		n_hi = q;
356
357		/* quotient and remainder of next 32 bits (upper half of n_lo) */
358		tmp = (r << 32) + (n_lo >> 32);
359		q = tmp / d;
360		r = tmp % d;
361
362		/* quotient and remainder of last 32 bits (lower half of n_lo) */
363		tmp = (r << 32) + (uint32) n_lo;
364		n_lo = q << 32;
365		q = tmp / d;
366		r = tmp % d;
367		n_lo += q;
368
369		/* final remainder should have the same sign as i128 /
370		*remainder = i128->hi < 0 ? (int32) (0 - r) : (int32) r;
371
372		/* store the quotient in i128, negating it if necessary /
373		if ((i128->hi < 0) != (v < 0))
374		{
375		n_hi = 0 - n_hi;
376		n_lo = 0 - n_lo;
377		if (n_lo != 0)
378		n_hi--;
379		}
380		i128->hi = (int64) n_hi;
381		i128->lo = n_lo;
382		#endif
383	0	} Unexecuted instantiation: numeric.c:int128_div_mod_int32 Unexecuted instantiation: timestamp.c:int128_div_mod_int32
384
385		/*
386		* Test if an INT128 value is zero.
387		*/
388		static inline bool
389		int128_is_zero(INT128 x)
390	0	{
391	0	#if USE_NATIVE_INT128
392	0	return x == 0;
393		#else
394		return x.hi == 0 && x.lo == 0;
395		#endif
396	0	} Unexecuted instantiation: numeric.c:int128_is_zero Unexecuted instantiation: timestamp.c:int128_is_zero
397
398		/*
399		* Return the sign of an INT128 value (returns -1, 0, or +1).
400		*/
401		static inline int
402		int128_sign(INT128 x)
403	0	{
404	0	#if USE_NATIVE_INT128
405	0	if (x < 0)
406	0	return -1;
407	0	if (x > 0)
408	0	return 1;
409	0	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	0	} Unexecuted instantiation: numeric.c:int128_sign Unexecuted instantiation: timestamp.c:int128_sign
420
421		/*
422		* Compare two INT128 values, return -1, 0, or +1.
423		*/
424		static inline int
425		int128_compare(INT128 x, INT128 y)
426	0	{
427	0	#if USE_NATIVE_INT128
428	0	if (x < y)
429	0	return -1;
430	0	if (x > y)
431	0	return 1;
432	0	return 0;
433		#else
434		if (x.hi < y.hi)
435		return -1;
436		if (x.hi > y.hi)
437		return 1;
438		if (x.lo < y.lo)
439		return -1;
440		if (x.lo > y.lo)
441		return 1;
442		return 0;
443		#endif
444	0	} Unexecuted instantiation: numeric.c:int128_compare Unexecuted instantiation: timestamp.c:int128_compare
445
446		/*
447		* Widen int64 to INT128.
448		*/
449		static inline INT128
450		int64_to_int128(int64 v)
451	0	{
452	0	#if USE_NATIVE_INT128
453	0	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	0	} Unexecuted instantiation: numeric.c:int64_to_int128 Unexecuted instantiation: timestamp.c:int64_to_int128
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
468		int128_to_int64(INT128 val)
469	0	{
470	0	#if USE_NATIVE_INT128
471	0	return (int64) val;
472		#else
473		return (int64) val.lo;
474		#endif
475	0	} Unexecuted instantiation: numeric.c:int128_to_int64 Unexecuted instantiation: timestamp.c:int128_to_int64
476
477		#endif /* INT128_H */