xref: /freebsd/contrib/llvm-project/compiler-rt/lib/builtins/udivsi3.c (revision f976241773df2260e6170317080761d1c5814fe5)
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
63