codekingpro/portable-devtools

1/*-------------------------------------------------------------------------2 *3 * int128.h4 *	  Roll-our-own 128-bit integer arithmetic.5 *6 * We make use of the native int128 type if there is one, otherwise7 * 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-2023, PostgreSQL Global Development Group12 *13 * src/include/common/int128.h14 *15 *-------------------------------------------------------------------------16 */17#ifndef INT128_H18#define INT128_H19 20/*21 * For testing purposes, use of native int128 can be switched on/off by22 * predefining USE_NATIVE_INT128.23 */24#ifndef USE_NATIVE_INT12825#ifdef HAVE_INT12826#define USE_NATIVE_INT128 127#else28#define USE_NATIVE_INT128 029#endif30#endif31 32 33#if USE_NATIVE_INT12834 35typedef int128 INT128;36 37/*38 * Add an unsigned int64 value into an INT128 variable.39 */40static inline void41int128_add_uint64(INT128 *i128, uint64 v)42{43	*i128 += v;44}45 46/*47 * Add a signed int64 value into an INT128 variable.48 */49static inline void50int128_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 than59 * the other implementation; maybe we should do it by hand always?60 */61static inline void62int128_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 */70static inline int71int128_compare(INT128 x, INT128 y)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 */83static inline INT12884int64_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 */93static inline int6494int128_to_int64(INT128 val)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 ordering103 * that a native int128 type would (probably) have.  This makes no difference104 * for ordinary use of INT128, but allows union'ing INT128 with int128 for105 * testing purposes.106 */107typedef struct108{109#ifdef WORDS_BIGENDIAN110	int64		hi;				/* most significant 64 bits, including sign */111	uint64		lo;				/* least significant 64 bits, without sign */112#else113	uint64		lo;				/* least significant 64 bits, without sign */114	int64		hi;				/* most significant 64 bits, including sign */115#endif116} INT128;117 118/*119 * Add an unsigned int64 value into an INT128 variable.120 */121static inline void122int128_add_uint64(INT128 *i128, uint64 v)123{124	/*125	 * First add the value to the .lo part, then check to see if a carry needs126	 * to be propagated into the .hi part.  A carry is needed if both inputs127	 * have high bits set, or if just one input has high bit set while the new128	 * .lo part doesn't.  Remember that .lo part is unsigned; we cast to129	 * 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 */142static inline void143int128_add_int64(INT128 *i128, int64 v)144{145	/*146	 * This is much like the above except that the carry logic differs for147	 * negative v.  Ordinarily we'd need to subtract 1 from the .hi part148	 * (corresponding to adding the sign-extended bits of v to it); but if149	 * 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	else160	{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, while168 * 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 */176static inline void177int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)178{179	/* INT64_AU32 must use arithmetic right shift */180	StaticAssertDecl(((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 compute187	 *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.lo193	 *194	 * Each individual product is of 32-bit terms so it won't overflow when195	 * computed in 64-bit arithmetic.  Then we just have to shift it to the196	 * correct position while adding into the 128-bit result.  We must also197	 * 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		else218			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		else226			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 */237static inline int238int128_compare(INT128 x, INT128 y)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 */254static inline INT128255int64_to_int128(int64 v)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 */268static inline int64269int128_to_int64(INT128 val)270{271	return (int64) val.lo;272}273 274#endif							/* USE_NATIVE_INT128 */275 276#endif							/* INT128_H */277