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