1//===-- udivmodti4.c - Implement __udivmodti4 -----------------------------===//
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 __udivmodti4 for the compiler_rt library.
10//
11//===----------------------------------------------------------------------===//
12
13#include "int_lib.h"
14
15#ifdef CRT_HAS_128BIT
16
17// Effects: if rem != 0, *rem = a % b
18// Returns: a / b
19
20// Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide
21
22COMPILER_RT_ABI tu_int __udivmodti4(tu_int a, tu_int b, tu_int *rem) {
23  const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;
24  const unsigned n_utword_bits = sizeof(tu_int) * CHAR_BIT;
25  utwords n;
26  n.all = a;
27  utwords d;
28  d.all = b;
29  utwords q;
30  utwords r;
31  unsigned sr;
32  // special cases, X is unknown, K != 0
33  if (n.s.high == 0) {
34    if (d.s.high == 0) {
35      // 0 X
36      // ---
37      // 0 X
38      if (rem)
39        *rem = n.s.low % d.s.low;
40      return n.s.low / d.s.low;
41    }
42    // 0 X
43    // ---
44    // K X
45    if (rem)
46      *rem = n.s.low;
47    return 0;
48  }
49  // n.s.high != 0
50  if (d.s.low == 0) {
51    if (d.s.high == 0) {
52      // K X
53      // ---
54      // 0 0
55      if (rem)
56        *rem = n.s.high % d.s.low;
57      return n.s.high / d.s.low;
58    }
59    // d.s.high != 0
60    if (n.s.low == 0) {
61      // K 0
62      // ---
63      // K 0
64      if (rem) {
65        r.s.high = n.s.high % d.s.high;
66        r.s.low = 0;
67        *rem = r.all;
68      }
69      return n.s.high / d.s.high;
70    }
71    // K K
72    // ---
73    // K 0
74    if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ {
75      if (rem) {
76        r.s.low = n.s.low;
77        r.s.high = n.s.high & (d.s.high - 1);
78        *rem = r.all;
79      }
80      return n.s.high >> __builtin_ctzll(d.s.high);
81    }
82    // K K
83    // ---
84    // K 0
85    sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high);
86    // 0 <= sr <= n_udword_bits - 2 or sr large
87    if (sr > n_udword_bits - 2) {
88      if (rem)
89        *rem = n.all;
90      return 0;
91    }
92    ++sr;
93    // 1 <= sr <= n_udword_bits - 1
94    // q.all = n.all << (n_utword_bits - sr);
95    q.s.low = 0;
96    q.s.high = n.s.low << (n_udword_bits - sr);
97    // r.all = n.all >> sr;
98    r.s.high = n.s.high >> sr;
99    r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
100  } else /* d.s.low != 0 */ {
101    if (d.s.high == 0) {
102      // K X
103      // ---
104      // 0 K
105      if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ {
106        if (rem)
107          *rem = n.s.low & (d.s.low - 1);
108        if (d.s.low == 1)
109          return n.all;
110        sr = __builtin_ctzll(d.s.low);
111        q.s.high = n.s.high >> sr;
112        q.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
113        return q.all;
114      }
115      // K X
116      // ---
117      // 0 K
118      sr = 1 + n_udword_bits + __builtin_clzll(d.s.low) -
119           __builtin_clzll(n.s.high);
120      // 2 <= sr <= n_utword_bits - 1
121      // q.all = n.all << (n_utword_bits - sr);
122      // r.all = n.all >> sr;
123      if (sr == n_udword_bits) {
124        q.s.low = 0;
125        q.s.high = n.s.low;
126        r.s.high = 0;
127        r.s.low = n.s.high;
128      } else if (sr < n_udword_bits) /* 2 <= sr <= n_udword_bits - 1 */ {
129        q.s.low = 0;
130        q.s.high = n.s.low << (n_udword_bits - sr);
131        r.s.high = n.s.high >> sr;
132        r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
133      } else /* n_udword_bits + 1 <= sr <= n_utword_bits - 1 */ {
134        q.s.low = n.s.low << (n_utword_bits - sr);
135        q.s.high = (n.s.high << (n_utword_bits - sr)) |
136                   (n.s.low >> (sr - n_udword_bits));
137        r.s.high = 0;
138        r.s.low = n.s.high >> (sr - n_udword_bits);
139      }
140    } else {
141      // K X
142      // ---
143      // K K
144      sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high);
145      // 0 <= sr <= n_udword_bits - 1 or sr large
146      if (sr > n_udword_bits - 1) {
147        if (rem)
148          *rem = n.all;
149        return 0;
150      }
151      ++sr;
152      // 1 <= sr <= n_udword_bits
153      // q.all = n.all << (n_utword_bits - sr);
154      // r.all = n.all >> sr;
155      q.s.low = 0;
156      if (sr == n_udword_bits) {
157        q.s.high = n.s.low;
158        r.s.high = 0;
159        r.s.low = n.s.high;
160      } else {
161        r.s.high = n.s.high >> sr;
162        r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
163        q.s.high = n.s.low << (n_udword_bits - sr);
164      }
165    }
166  }
167  // Not a special case
168  // q and r are initialized with:
169  // q.all = n.all << (n_utword_bits - sr);
170  // r.all = n.all >> sr;
171  // 1 <= sr <= n_utword_bits - 1
172  su_int carry = 0;
173  for (; sr > 0; --sr) {
174    // r:q = ((r:q)  << 1) | carry
175    r.s.high = (r.s.high << 1) | (r.s.low >> (n_udword_bits - 1));
176    r.s.low = (r.s.low << 1) | (q.s.high >> (n_udword_bits - 1));
177    q.s.high = (q.s.high << 1) | (q.s.low >> (n_udword_bits - 1));
178    q.s.low = (q.s.low << 1) | carry;
179    // carry = 0;
180    // if (r.all >= d.all)
181    // {
182    //     r.all -= d.all;
183    //      carry = 1;
184    // }
185    const ti_int s = (ti_int)(d.all - r.all - 1) >> (n_utword_bits - 1);
186    carry = s & 1;
187    r.all -= d.all & s;
188  }
189  q.all = (q.all << 1) | carry;
190  if (rem)
191    *rem = r.all;
192  return q.all;
193}
194
195#endif // CRT_HAS_128BIT
196