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

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