GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libcompiler_rt/udivmodti4.c Lines: 0 77 0.0 %
Date: 2017-11-07 Branches: 0 48 0.0 %

Line Branch Exec Source
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
25
COMPILER_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 */