kit

int64.c (12936B)

---

 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 // Consolidated per-op runtime helpers for kit's libkit_rt.a.
 // The build compiles only this one file per directory; the per-op .c files
 // are #included as snippets and not directly compiled.
 // License: Apache-2.0 WITH LLVM-exception (see lib/LICENSE-compiler-rt.txt).
 
 // udivmodti4.c first: __udivmodti4 is called by divmodti4, divti3, modti3,
 // udivti3, and umodti3 — must be defined before those callers.
 // ---- udivmodti4.c ----
 #include "int_lib.h"
 
 // Returns the 128 bit division result by 64 bit. Result must fit in 64 bits.
 // Remainder stored in r.
 // Taken and adjusted from libdivide libdivide_128_div_64_to_64 division
 // fallback. For a correctness proof see the reference for this algorithm
 // in Knuth, Volume 2, section 4.3.1, Algorithm D.
 UNUSED
 static inline du_int udiv128by64to64default(du_int u1, du_int u0, du_int v,
                                             du_int* r) {
   const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;
   const du_int b = (1ULL << (n_udword_bits / 2));  // Number base (32 bits)
   du_int un1, un0;                                 // Norm. dividend LSD's
   du_int vn1, vn0;                                 // Norm. divisor digits
   du_int q1, q0;                                   // Quotient digits
   du_int un64, un21, un10;                         // Dividend digit pairs
   du_int rhat;                                     // A remainder
   si_int s;  // Shift amount for normalization
 
   s = __builtin_clzll(v);
   if (s > 0) {
     // Normalize the divisor.
     v = v << s;
     un64 = (u1 << s) | (u0 >> (n_udword_bits - s));
     un10 = u0 << s;  // Shift dividend left
   } else {
     // Avoid undefined behavior of (u0 >> 64).
     un64 = u1;
     un10 = u0;
   }
 
   // Break divisor up into two 32-bit digits.
   vn1 = v >> (n_udword_bits / 2);
   vn0 = v & 0xFFFFFFFF;
 
   // Break right half of dividend into two digits.
   un1 = un10 >> (n_udword_bits / 2);
   un0 = un10 & 0xFFFFFFFF;
 
   // Compute the first quotient digit, q1.
   q1 = un64 / vn1;
   rhat = un64 - q1 * vn1;
 
   // q1 has at most error 2. No more than 2 iterations.
   while (q1 >= b || q1 * vn0 > b * rhat + un1) {
     q1 = q1 - 1;
     rhat = rhat + vn1;
     if (rhat >= b) break;
   }
 
   un21 = un64 * b + un1 - q1 * v;
 
   // Compute the second quotient digit.
   q0 = un21 / vn1;
   rhat = un21 - q0 * vn1;
 
   // q0 has at most error 2. No more than 2 iterations.
   while (q0 >= b || q0 * vn0 > b * rhat + un0) {
     q0 = q0 - 1;
     rhat = rhat + vn1;
     if (rhat >= b) break;
   }
 
   *r = (un21 * b + un0 - q0 * v) >> s;
   return q1 * b + q0;
 }
 
 static inline du_int udiv128by64to64(du_int u1, du_int u0, du_int v,
                                      du_int* r) {
   return udiv128by64to64default(u1, u0, v, r);
 }
 
 static inline int ut_is_zero(utwords a) {
   return a.s.low == 0 && a.s.high == 0;
 }
 
 static inline int ut_cmp(utwords a, utwords b) {
   if (a.s.high != b.s.high) return a.s.high < b.s.high ? -1 : 1;
   if (a.s.low != b.s.low) return a.s.low < b.s.low ? -1 : 1;
   return 0;
 }
 
 static inline utwords ut_add(utwords a, utwords b) {
   utwords r;
   r.s.low = a.s.low + b.s.low;
   r.s.high = a.s.high + b.s.high + (r.s.low < a.s.low);
   return r;
 }
 
 static inline utwords ut_sub(utwords a, utwords b) {
   utwords r;
   r.s.low = a.s.low - b.s.low;
   r.s.high = a.s.high - b.s.high - (a.s.low < b.s.low);
   return r;
 }
 
 static inline utwords ut_neg(utwords a) {
   utwords z;
   z.s.low = 0;
   z.s.high = 0;
   return ut_sub(z, a);
 }
 
 static inline utwords ut_shl1(utwords a) {
   utwords r;
   r.s.low = a.s.low << 1;
   r.s.high = (a.s.high << 1) | (a.s.low >> 63);
   return r;
 }
 
 static inline utwords ut_shr1(utwords a) {
   utwords r;
   r.s.low = (a.s.low >> 1) | (a.s.high << 63);
   r.s.high = a.s.high >> 1;
   return r;
 }
 
 static inline utwords ut_shl(utwords a, unsigned sh) {
   utwords r;
   if (sh >= 128u) {
     r.s.low = 0;
     r.s.high = 0;
   } else if (sh == 0) {
     r = a;
   } else if (sh >= 64u) {
     r.s.low = 0;
     r.s.high = a.s.low << (sh - 64u);
   } else {
     r.s.low = a.s.low << sh;
     r.s.high = (a.s.high << sh) | (a.s.low >> (64u - sh));
   }
   return r;
 }
 
 static inline utwords ut_lshr(utwords a, unsigned sh) {
   utwords r;
   if (sh >= 128u) {
     r.s.low = 0;
     r.s.high = 0;
   } else if (sh == 0) {
     r = a;
   } else if (sh >= 64u) {
     r.s.low = a.s.high >> (sh - 64u);
     r.s.high = 0;
   } else {
     r.s.low = (a.s.low >> sh) | (a.s.high << (64u - sh));
     r.s.high = a.s.high >> sh;
   }
   return r;
 }
 
 static inline twords t_ashr(twords a, unsigned sh) {
   twords r;
   if (sh >= 128u) {
     r.s.low = a.s.high < 0 ? ~(du_int)0 : 0;
     r.s.high = a.s.high < 0 ? (di_int)-1 : 0;
   } else if (sh == 0) {
     r = a;
   } else if (sh >= 64u) {
     r.s.low = (du_int)(a.s.high >> (sh - 64u));
     r.s.high = a.s.high < 0 ? (di_int)-1 : 0;
   } else {
     r.s.low = ((du_int)a.s.high << (64u - sh)) | (a.s.low >> sh);
     r.s.high = a.s.high >> sh;
   }
   return r;
 }
 
 static inline utwords ut_mul(utwords a, utwords b) {
   utwords r;
   const int half_bits = (int)(sizeof(du_int) * CHAR_BIT) / 2;
   const du_int mask = (du_int)~0 >> half_bits;
   du_int t;
   r.s.low = (a.s.low & mask) * (b.s.low & mask);
   t = r.s.low >> half_bits;
   r.s.low &= mask;
   t += (a.s.low >> half_bits) * (b.s.low & mask);
   r.s.low += (t & mask) << half_bits;
   r.s.high = t >> half_bits;
   t = r.s.low >> half_bits;
   r.s.low &= mask;
   t += (b.s.low >> half_bits) * (a.s.low & mask);
   r.s.low += (t & mask) << half_bits;
   r.s.high += t >> half_bits;
   r.s.high += (a.s.low >> half_bits) * (b.s.low >> half_bits);
   r.s.high += a.s.high * b.s.low + a.s.low * b.s.high;
   return r;
 }
 
 static inline void ut_udivmod(utwords n, utwords d, utwords* q, utwords* rem) {
   utwords quotient;
   utwords remainder;
   quotient.s.low = 0;
   quotient.s.high = 0;
   remainder.s.low = 0;
   remainder.s.high = 0;
   if (ut_is_zero(d)) {
     if (q) *q = quotient;
     if (rem) *rem = n;
     return;
   }
   for (int i = 127; i >= 0; --i) {
     du_int bit = i < 64 ? ((n.s.low >> (unsigned)i) & 1u)
                         : ((n.s.high >> (unsigned)(i - 64)) & 1u);
     remainder = ut_shl1(remainder);
     remainder.s.low |= bit;
     if (ut_cmp(remainder, d) >= 0) {
       remainder = ut_sub(remainder, d);
       if (i < 64)
         quotient.s.low |= (du_int)1 << (unsigned)i;
       else
         quotient.s.high |= (du_int)1 << (unsigned)(i - 64);
     }
   }
   if (q) *q = quotient;
   if (rem) *rem = remainder;
 }
 
 // Effects: if rem != 0, *rem = a % b
 // Returns: a / b
 
 COMPILER_RT_ABI tu_int __udivmodti4(tu_int a, tu_int b, tu_int* rem) {
   utwords dividend;
   dividend.all = a;
   utwords divisor;
   divisor.all = b;
   utwords quotient;
   utwords remainder;
   ut_udivmod(dividend, divisor, &quotient, &remainder);
   if (rem) *rem = remainder.all;
   return quotient.all;
 }
 
 // Leaf ops (no intra-directory dependencies):
 // ---- ashlti3.c ----
 #include "int_lib.h"
 
 // Returns: a << b
 
 // Precondition:  0 <= b < bits_in_tword
 
 COMPILER_RT_ABI ti_int __ashlti3(ti_int a, int b) {
   utwords input;
   utwords result;
   input.all = a;
   result = ut_shl(input, (unsigned)b);
   return (ti_int)result.all;
 }
 
 // ---- ashrti3.c ----
 #include "int_lib.h"
 
 // Returns: arithmetic a >> b
 
 // Precondition:  0 <= b < bits_in_tword
 
 COMPILER_RT_ABI ti_int __ashrti3(ti_int a, int b) {
   twords input;
   twords result;
   input.all = a;
   result = t_ashr(input, (unsigned)b);
   return result.all;
 }
 
 // ---- clzti2.c ----
 #include "int_lib.h"
 
 // Returns: the number of leading 0-bits
 
 // Precondition: a != 0
 
 COMPILER_RT_ABI int __clzti2(ti_int a) {
   twords x;
   x.all = a;
   const di_int f = -(x.s.high == 0);
   return __builtin_clzll((x.s.high & ~f) | (x.s.low & f)) +
          ((si_int)f & ((si_int)(sizeof(di_int) * CHAR_BIT)));
 }
 
 // ---- ctzti2.c ----
 #include "int_lib.h"
 
 // Returns: the number of trailing 0-bits
 
 // Precondition: a != 0
 
 COMPILER_RT_ABI int __ctzti2(ti_int a) {
   twords x;
   x.all = a;
   const di_int f = -(x.s.low == 0);
   return __builtin_ctzll((x.s.high & f) | (x.s.low & ~f)) +
          ((si_int)f & ((si_int)(sizeof(di_int) * CHAR_BIT)));
 }
 
 // ---- lshrti3.c ----
 #include "int_lib.h"
 
 // Returns: logical a >> b
 
 // Precondition:  0 <= b < bits_in_tword
 
 COMPILER_RT_ABI ti_int __lshrti3(ti_int a, int b) {
   utwords input;
   utwords result;
   input.all = a;
   result = ut_lshr(input, (unsigned)b);
   return (ti_int)result.all;
 }
 
 // ---- multi3.c ----
 #include "int_lib.h"
 
 // Returns: a * b
 
 static ti_int __mulddi3(du_int a, du_int b) {
   twords r;
   const int bits_in_dword_2 = (int)(sizeof(di_int) * CHAR_BIT) / 2;
   const du_int lower_mask = (du_int)~0 >> bits_in_dword_2;
   r.s.low = (a & lower_mask) * (b & lower_mask);
   du_int t = r.s.low >> bits_in_dword_2;
   r.s.low &= lower_mask;
   t += (a >> bits_in_dword_2) * (b & lower_mask);
   r.s.low += (t & lower_mask) << bits_in_dword_2;
   r.s.high = t >> bits_in_dword_2;
   t = r.s.low >> bits_in_dword_2;
   r.s.low &= lower_mask;
   t += (b >> bits_in_dword_2) * (a & lower_mask);
   r.s.low += (t & lower_mask) << bits_in_dword_2;
   r.s.high += t >> bits_in_dword_2;
   r.s.high += (a >> bits_in_dword_2) * (b >> bits_in_dword_2);
   return r.all;
 }
 
 // Returns: a * b
 
 COMPILER_RT_ABI ti_int __multi3(ti_int a, ti_int b) {
   utwords x;
   utwords y;
   utwords r;
   x.all = (tu_int)a;
   y.all = (tu_int)b;
   r = ut_mul(x, y);
   return (ti_int)r.all;
 }
 
 // ---- negti2.c ----
 #include "int_lib.h"
 
 // Returns: -a
 
 COMPILER_RT_ABI ti_int __negti2(ti_int a) {
   utwords x;
   utwords r;
   x.all = (tu_int)a;
   r = ut_neg(x);
   return (ti_int)r.all;
 }
 
 COMPILER_RT_ABI ti_int __kit_addti3(ti_int a, ti_int b) {
   utwords x;
   utwords y;
   utwords r;
   x.all = (tu_int)a;
   y.all = (tu_int)b;
   r = ut_add(x, y);
   return (ti_int)r.all;
 }
 
 COMPILER_RT_ABI ti_int __kit_subti3(ti_int a, ti_int b) {
   utwords x;
   utwords y;
   utwords r;
   x.all = (tu_int)a;
   y.all = (tu_int)b;
   r = ut_sub(x, y);
   return (ti_int)r.all;
 }
 
 COMPILER_RT_ABI ti_int __kit_andti3(ti_int a, ti_int b) {
   utwords x;
   utwords y;
   utwords r;
   x.all = (tu_int)a;
   y.all = (tu_int)b;
   r.s.low = x.s.low & y.s.low;
   r.s.high = x.s.high & y.s.high;
   return (ti_int)r.all;
 }
 
 COMPILER_RT_ABI ti_int __kit_orti3(ti_int a, ti_int b) {
   utwords x;
   utwords y;
   utwords r;
   x.all = (tu_int)a;
   y.all = (tu_int)b;
   r.s.low = x.s.low | y.s.low;
   r.s.high = x.s.high | y.s.high;
   return (ti_int)r.all;
 }
 
 COMPILER_RT_ABI ti_int __kit_xorti3(ti_int a, ti_int b) {
   utwords x;
   utwords y;
   utwords r;
   x.all = (tu_int)a;
   y.all = (tu_int)b;
   r.s.low = x.s.low ^ y.s.low;
   r.s.high = x.s.high ^ y.s.high;
   return (ti_int)r.all;
 }
 
 COMPILER_RT_ABI ti_int __kit_notti3(ti_int a) {
   utwords x;
   utwords r;
   x.all = (tu_int)a;
   r.s.low = ~x.s.low;
   r.s.high = ~x.s.high;
   return (ti_int)r.all;
 }
 
 COMPILER_RT_ABI ti_int __kit_sext64ti(di_int a) {
   twords r;
   r.s.low = (du_int)a;
   r.s.high = a < 0 ? -1 : 0;
   return r.all;
 }
 
 COMPILER_RT_ABI ti_int __kit_zext64ti(du_int a) {
   utwords r;
   r.s.low = a;
   r.s.high = 0;
   return (ti_int)r.all;
 }
 
 COMPILER_RT_ABI si_int __kit_cmpti2(ti_int a, ti_int b) {
   twords x;
   twords y;
   x.all = a;
   y.all = b;
   if (x.s.high < y.s.high) return -1;
   if (x.s.high > y.s.high) return 1;
   if (x.s.low < y.s.low) return -1;
   if (x.s.low > y.s.low) return 1;
   return 0;
 }
 
 COMPILER_RT_ABI si_int __kit_ucmpti2(tu_int a, tu_int b) {
   utwords x;
   utwords y;
   x.all = a;
   y.all = b;
   if (x.s.high < y.s.high) return -1;
   if (x.s.high > y.s.high) return 1;
   if (x.s.low < y.s.low) return -1;
   if (x.s.low > y.s.low) return 1;
   return 0;
 }
 
 // Callers of __udivmodti4:
 // ---- udivti3.c ----
 #include "int_lib.h"
 
 // Returns: a / b
 
 COMPILER_RT_ABI tu_int __udivti3(tu_int a, tu_int b) {
   return __udivmodti4(a, b, 0);
 }
 
 // ---- umodti3.c ----
 #include "int_lib.h"
 
 // Returns: a % b
 
 COMPILER_RT_ABI tu_int __umodti3(tu_int a, tu_int b) {
   tu_int r;
   __udivmodti4(a, b, &r);
   return r;
 }
 
 // ---- divmodti4.c ----
 #include "int_lib.h"
 
 // Returns: a / b, *rem = a % b
 
 COMPILER_RT_ABI ti_int __divmodti4(ti_int a, ti_int b, ti_int* rem) {
   twords sa;
   twords sb;
   utwords ua;
   utwords ub;
   utwords uq;
   utwords ur;
   int neg_a;
   int neg_b;
   sa.all = a;
   sb.all = b;
   neg_a = sa.s.high < 0;
   neg_b = sb.s.high < 0;
   ua.all = (tu_int)a;
   ub.all = (tu_int)b;
   if (neg_a) ua = ut_neg(ua);
   if (neg_b) ub = ut_neg(ub);
   ut_udivmod(ua, ub, &uq, &ur);
   if (neg_a != neg_b) uq = ut_neg(uq);
   if (neg_a) ur = ut_neg(ur);
   if (rem) *rem = (ti_int)ur.all;
   return (ti_int)uq.all;
 }
 
 // ---- divti3.c ----
 #include "int_lib.h"
 
 // Returns: a / b
 
 COMPILER_RT_ABI ti_int __divti3(ti_int a, ti_int b) {
   ti_int r;
   return __divmodti4(a, b, &r);
 }
 
 // ---- modti3.c ----
 #include "int_lib.h"
 
 // Returns: a % b
 
 COMPILER_RT_ABI ti_int __modti3(ti_int a, ti_int b) {
   ti_int r;
   (void)__divmodti4(a, b, &r);
   return r;
 }