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/tools/testint128.c for a simple test harness for this file.
      10             :  *
      11             :  * Copyright (c) 2017-2024, 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      253788 : int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
      63             : {
      64      253788 :     *i128 += (int128) x * (int128) y;
      65      253788 : }
      66             : 
      67             : /*
      68             :  * Compare two INT128 values, return -1, 0, or +1.
      69             :  */
      70             : static inline int
      71      128170 : int128_compare(INT128 x, INT128 y)
      72             : {
      73      128170 :     if (x < y)
      74       53844 :         return -1;
      75       74326 :     if (x > y)
      76       52748 :         return 1;
      77       21578 :     return 0;
      78             : }
      79             : 
      80             : /*
      81             :  * Widen int64 to INT128.
      82             :  */
      83             : static inline INT128
      84      258674 : int64_to_int128(int64 v)
      85             : {
      86      258674 :     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
      94        2334 : int128_to_int64(INT128 val)
      95             : {
      96        2334 :     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             :     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 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
     238             : int128_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             :  */
     254             : static inline INT128
     255             : int64_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             :  */
     268             : static inline int64
     269             : int128_to_int64(INT128 val)
     270             : {
     271             :     return (int64) val.lo;
     272             : }
     273             : 
     274             : #endif                          /* USE_NATIVE_INT128 */
     275             : 
     276             : #endif                          /* INT128_H */