compiler-rt/lib/builtins/int_div_impl.inc

   1 //===-- int_div_impl.inc - Integer division ---------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Helpers used by __udivsi3, __umodsi3, __udivdi3, and __umodsi3.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #define clz(a) (sizeof(a) == sizeof(unsigned long long) ? __builtin_clzll(a) : clzsi(a))
  14
  15 // Adapted from Figure 3-40 of The PowerPC Compiler Writer's Guide
  16 static __inline fixuint_t __udivXi3(fixuint_t n, fixuint_t d) {
  17   const unsigned N = sizeof(fixuint_t) * CHAR_BIT;
  18   // d == 0 cases are unspecified.
  19   unsigned sr = (d ? clz(d) : N) - (n ? clz(n) : N);
  20   // 0 <= sr <= N - 1 or sr is very large.
  21   if (sr > N - 1) // n < d
  22     return 0;
  23   if (sr == N - 1) // d == 1
  24     return n;
  25   ++sr;
  26   // 1 <= sr <= N - 1. Shifts do not trigger UB.
  27   fixuint_t r = n >> sr;
  28   n <<= N - sr;
  29   fixuint_t carry = 0;
  30   for (; sr > 0; --sr) {
  31     r = (r << 1) | (n >> (N - 1));
  32     n = (n << 1) | carry;
  33     // Branch-less version of:
  34     // carry = 0;
  35     // if (r >= d) r -= d, carry = 1;
  36     const fixint_t s = (fixint_t)(d - r - 1) >> (N - 1);
  37     carry = s & 1;
  38     r -= d & s;
  39   }
  40   n = (n << 1) | carry;
  41   return n;
  42 }
  43
  44 // Mostly identical to __udivXi3 but the return values are different.
  45 static __inline fixuint_t __umodXi3(fixuint_t n, fixuint_t d) {
  46   const unsigned N = sizeof(fixuint_t) * CHAR_BIT;
  47   // d == 0 cases are unspecified.
  48   unsigned sr = (d ? clz(d) : N) - (n ? clz(n) : N);
  49   // 0 <= sr <= N - 1 or sr is very large.
  50   if (sr > N - 1) // n < d
  51     return n;
  52   if (sr == N - 1) // d == 1
  53     return 0;
  54   ++sr;
  55   // 1 <= sr <= N - 1. Shifts do not trigger UB.
  56   fixuint_t r = n >> sr;
  57   n <<= N - sr;
  58   fixuint_t carry = 0;
  59   for (; sr > 0; --sr) {
  60     r = (r << 1) | (n >> (N - 1));
  61     n = (n << 1) | carry;
  62     // Branch-less version of:
  63     // carry = 0;
  64     // if (r >= d) r -= d, carry = 1;
  65     const fixint_t s = (fixint_t)(d - r - 1) >> (N - 1);
  66     carry = s & 1;
  67     r -= d & s;
  68   }
  69   return r;
  70 }
  71
  72 #ifdef COMPUTE_UDIV
  73 static __inline fixint_t __divXi3(fixint_t a, fixint_t b) {
  74   const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1;
  75   fixint_t s_a = a >> N;                            // s_a = a < 0 ? -1 : 0
  76   fixint_t s_b = b >> N;                            // s_b = b < 0 ? -1 : 0
  77   fixuint_t a_u = (fixuint_t)(a ^ s_a) + (-s_a);    // negate if s_a == -1
  78   fixuint_t b_u = (fixuint_t)(b ^ s_b) + (-s_b);    // negate if s_b == -1
  79   s_a ^= s_b;                                       // sign of quotient
  80   return (COMPUTE_UDIV(a_u, b_u) ^ s_a) + (-s_a);   // negate if s_a == -1
  81 }
  82 #endif // COMPUTE_UDIV
  83
  84 #ifdef ASSIGN_UMOD
  85 static __inline fixint_t __modXi3(fixint_t a, fixint_t b) {
  86   const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1;
  87   fixint_t s = b >> N;                              // s = b < 0 ? -1 : 0
  88   fixuint_t b_u = (fixuint_t)(b ^ s) + (-s);        // negate if s == -1
  89   s = a >> N;                                       // s = a < 0 ? -1 : 0
  90   fixuint_t a_u = (fixuint_t)(a ^ s) + (-s);        // negate if s == -1
  91   fixuint_t res;
  92   ASSIGN_UMOD(res, a_u, b_u);
  93   return (res ^ s) + (-s);                          // negate if s == -1
  94 }
  95 #endif // ASSIGN_UMOD