contrib/compiler-rt/lib/builtins/udivsi3.c

   1 //===-- udivsi3.c - Implement __udivsi3 -----------------------------------===//
   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 // This file implements __udivsi3 for the compiler_rt library.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "int_lib.h"
  14
  15 // Returns: a / b
  16
  17 // Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide
  18
  19 // This function should not call __divsi3!
  20 COMPILER_RT_ABI su_int __udivsi3(su_int n, su_int d) {
  21   const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT;
  22   su_int q;
  23   su_int r;
  24   unsigned sr;
  25   // special cases
  26   if (d == 0)
  27     return 0; // ?!
  28   if (n == 0)
  29     return 0;
  30   sr = __builtin_clz(d) - __builtin_clz(n);
  31   // 0 <= sr <= n_uword_bits - 1 or sr large
  32   if (sr > n_uword_bits - 1) // d > r
  33     return 0;
  34   if (sr == n_uword_bits - 1) // d == 1
  35     return n;
  36   ++sr;
  37   // 1 <= sr <= n_uword_bits - 1
  38   // Not a special case
  39   q = n << (n_uword_bits - sr);
  40   r = n >> sr;
  41   su_int carry = 0;
  42   for (; sr > 0; --sr) {
  43     // r:q = ((r:q)  << 1) | carry
  44     r = (r << 1) | (q >> (n_uword_bits - 1));
  45     q = (q << 1) | carry;
  46     // carry = 0;
  47     // if (r.all >= d.all)
  48     // {
  49     //      r.all -= d.all;
  50     //      carry = 1;
  51     // }
  52     const si_int s = (si_int)(d - r - 1) >> (n_uword_bits - 1);
  53     carry = s & 1;
  54     r -= d & s;
  55   }
  56   q = (q << 1) | carry;
  57   return q;
  58 }
  59
  60 #if defined(__ARM_EABI__)
  61 COMPILER_RT_ALIAS(__udivsi3, __aeabi_uidiv)
  62 #endif