LCOV - differential code coverage report
Current view: top level - src/include/common - int128.h (source / functions) Coverage Total Hit CBC
Current: Differential Code Coverage 16@8cea358b128 vs 17@8cea358b128 Lines: 100.0 % 13 13 13
Current Date: 2024-04-14 14:21:10 Functions: 100.0 % 4 4 4
Baseline: 16@8cea358b128 Branches: 100.0 % 4 4 4
Baseline Date: 2024-04-14 14:21:09 Line coverage date bins:
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed (240..) days: 100.0 % 13 13 13
Function coverage date bins:
(240..) days: 100.0 % 4 4 4
Branch coverage date bins:
(240..) days: 100.0 % 4 4 4

 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/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
 2566 tgl@sss.pgh.pa.us          62                 :CBC      288907 : int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
                                 63                 :                : {
 2489                            64                 :         288907 :     *i128 += (int128) x * (int128) y;
 2566                            65                 :         288907 : }
                                 66                 :                : 
                                 67                 :                : /*
                                 68                 :                :  * Compare two INT128 values, return -1, 0, or +1.
                                 69                 :                :  */
                                 70                 :                : static inline int
                                 71                 :         145078 : int128_compare(INT128 x, INT128 y)
                                 72                 :                : {
                                 73         [ +  + ]:         145078 :     if (x < y)
                                 74                 :          77579 :         return -1;
                                 75         [ +  + ]:          67499 :     if (x > y)
                                 76                 :          55771 :         return 1;
                                 77                 :          11728 :     return 0;
                                 78                 :                : }
                                 79                 :                : 
                                 80                 :                : /*
                                 81                 :                :  * Widen int64 to INT128.
                                 82                 :                :  */
                                 83                 :                : static inline INT128
                                 84                 :         291329 : int64_to_int128(int64 v)
                                 85                 :                : {
                                 86                 :         291329 :     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                 :           1173 : int128_to_int64(INT128 val)
                                 95                 :                : {
                                 96                 :           1173 :     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 */
        

Generated by: LCOV version 2.1-beta2-3-g6141622