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!
20COMPILER_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__)
61COMPILER_RT_ALIAS(__udivsi3, __aeabi_uidiv)
62#endif
63