llvm-project

1
//===-- udivmoddi4.c - Implement __udivmoddi4 -----------------------------===//
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 __udivmoddi4 for the compiler_rt library.
10
//
11
//===----------------------------------------------------------------------===//
12

13
#include "int_lib.h"
14

15
// Effects: if rem != 0, *rem = a % b
16
// Returns: a / b
17

18
// Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide
19

20
#if defined(_MSC_VER) && !defined(__clang__)
21
// MSVC throws a warning about mod 0 here, disable it for builds that
22
// warn-as-error
23
#pragma warning(push)
24
#pragma warning(disable : 4723 4724)
25
#endif
26

27
COMPILER_RT_ABI du_int __udivmoddi4(du_int a, du_int b, du_int *rem) {
28
  const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT;
29
  const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;
30
  udwords n;
31
  n.all = a;
32
  udwords d;
33
  d.all = b;
34
  udwords q;
35
  udwords r;
36
  unsigned sr;
37
  // special cases, X is unknown, K != 0
38
  if (n.s.high == 0) {
39
    if (d.s.high == 0) {
40
      // 0 X
41
      // ---
42
      // 0 X
43
      if (rem)
44
        *rem = n.s.low % d.s.low;
45
      return n.s.low / d.s.low;
46
    }
47
    // 0 X
48
    // ---
49
    // K X
50
    if (rem)
51
      *rem = n.s.low;
52
    return 0;
53
  }
54
  // n.s.high != 0
55
  if (d.s.low == 0) {
56
    if (d.s.high == 0) {
57
      // K X
58
      // ---
59
      // 0 0
60
      if (rem)
61
        *rem = n.s.high % d.s.low;
62
      return n.s.high / d.s.low;
63
    }
64
    // d.s.high != 0
65
    if (n.s.low == 0) {
66
      // K 0
67
      // ---
68
      // K 0
69
      if (rem) {
70
        r.s.high = n.s.high % d.s.high;
71
        r.s.low = 0;
72
        *rem = r.all;
73
      }
74
      return n.s.high / d.s.high;
75
    }
76
    // K K
77
    // ---
78
    // K 0
79
    if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ {
80
      if (rem) {
81
        r.s.low = n.s.low;
82
        r.s.high = n.s.high & (d.s.high - 1);
83
        *rem = r.all;
84
      }
85
      return n.s.high >> ctzsi(d.s.high);
86
    }
87
    // K K
88
    // ---
89
    // K 0
90
    sr = clzsi(d.s.high) - clzsi(n.s.high);
91
    // 0 <= sr <= n_uword_bits - 2 or sr large
92
    if (sr > n_uword_bits - 2) {
93
      if (rem)
94
        *rem = n.all;
95
      return 0;
96
    }
97
    ++sr;
98
    // 1 <= sr <= n_uword_bits - 1
99
    // q.all = n.all << (n_udword_bits - sr);
100
    q.s.low = 0;
101
    q.s.high = n.s.low << (n_uword_bits - sr);
102
    // r.all = n.all >> sr;
103
    r.s.high = n.s.high >> sr;
104
    r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
105
  } else /* d.s.low != 0 */ {
106
    if (d.s.high == 0) {
107
      // K X
108
      // ---
109
      // 0 K
110
      if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ {
111
        if (rem)
112
          *rem = n.s.low & (d.s.low - 1);
113
        if (d.s.low == 1)
114
          return n.all;
115
        sr = ctzsi(d.s.low);
116
        q.s.high = n.s.high >> sr;
117
        q.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
118
        return q.all;
119
      }
120
      // K X
121
      // ---
122
      // 0 K
123
      sr = 1 + n_uword_bits + clzsi(d.s.low) - clzsi(n.s.high);
124
      // 2 <= sr <= n_udword_bits - 1
125
      // q.all = n.all << (n_udword_bits - sr);
126
      // r.all = n.all >> sr;
127
      if (sr == n_uword_bits) {
128
        q.s.low = 0;
129
        q.s.high = n.s.low;
130
        r.s.high = 0;
131
        r.s.low = n.s.high;
132
      } else if (sr < n_uword_bits) /* 2 <= sr <= n_uword_bits - 1 */ {
133
        q.s.low = 0;
134
        q.s.high = n.s.low << (n_uword_bits - sr);
135
        r.s.high = n.s.high >> sr;
136
        r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
137
      } else /* n_uword_bits + 1 <= sr <= n_udword_bits - 1 */ {
138
        q.s.low = n.s.low << (n_udword_bits - sr);
139
        q.s.high = (n.s.high << (n_udword_bits - sr)) |
140
                   (n.s.low >> (sr - n_uword_bits));
141
        r.s.high = 0;
142
        r.s.low = n.s.high >> (sr - n_uword_bits);
143
      }
144
    } else {
145
      // K X
146
      // ---
147
      // K K
148
      sr = clzsi(d.s.high) - clzsi(n.s.high);
149
      // 0 <= sr <= n_uword_bits - 1 or sr large
150
      if (sr > n_uword_bits - 1) {
151
        if (rem)
152
          *rem = n.all;
153
        return 0;
154
      }
155
      ++sr;
156
      // 1 <= sr <= n_uword_bits
157
      // q.all = n.all << (n_udword_bits - sr);
158
      q.s.low = 0;
159
      if (sr == n_uword_bits) {
160
        q.s.high = n.s.low;
161
        r.s.high = 0;
162
        r.s.low = n.s.high;
163
      } else {
164
        q.s.high = n.s.low << (n_uword_bits - sr);
165
        r.s.high = n.s.high >> sr;
166
        r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
167
      }
168
    }
169
  }
170
  // Not a special case
171
  // q and r are initialized with:
172
  // q.all = n.all << (n_udword_bits - sr);
173
  // r.all = n.all >> sr;
174
  // 1 <= sr <= n_udword_bits - 1
175
  su_int carry = 0;
176
  for (; sr > 0; --sr) {
177
    // r:q = ((r:q)  << 1) | carry
178
    r.s.high = (r.s.high << 1) | (r.s.low >> (n_uword_bits - 1));
179
    r.s.low = (r.s.low << 1) | (q.s.high >> (n_uword_bits - 1));
180
    q.s.high = (q.s.high << 1) | (q.s.low >> (n_uword_bits - 1));
181
    q.s.low = (q.s.low << 1) | carry;
182
    // carry = 0;
183
    // if (r.all >= d.all)
184
    // {
185
    //      r.all -= d.all;
186
    //      carry = 1;
187
    // }
188
    const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1);
189
    carry = s & 1;
190
    r.all -= d.all & s;
191
  }
192
  q.all = (q.all << 1) | carry;
193
  if (rem)
194
    *rem = r.all;
195
  return q.all;
196
}
197

198
#if defined(_MSC_VER) && !defined(__clang__)
199
#pragma warning(pop)
200
#endif
201