udivsi3.c revision 215125 
1/* ===-- udivsi3.c - Implement __udivsi3 -----------------------------------===
2 *
3 *                     The LLVM Compiler Infrastructure
4 *
5 * This file is distributed under the University of Illinois Open Source
6 * License. See LICENSE.TXT for details.
7 *
8 * ===----------------------------------------------------------------------===
9 *
10 * This file implements __udivsi3 for the compiler_rt library.
11 *
12 * ===----------------------------------------------------------------------===
13 */
14
15#include "int_lib.h"
16
17/* Returns: a / b */
18
19/* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */
20
21su_int
22__udivsi3(su_int n, su_int d)
23{
24    const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT;
25    su_int q;
26    su_int r;
27    unsigned sr;
28    /* special cases */
29    if (d == 0)
30        return 0; /* ?! */
31    if (n == 0)
32        return 0;
33    sr = __builtin_clz(d) - __builtin_clz(n);
34    /* 0 <= sr <= n_uword_bits - 1 or sr large */
35    if (sr > n_uword_bits - 1)  /* d > r */
36        return 0;
37    if (sr == n_uword_bits - 1)  /* d == 1 */
38        return n;
39    ++sr;
40    /* 1 <= sr <= n_uword_bits - 1 */
41    /* Not a special case */
42    q = n << (n_uword_bits - sr);
43    r = n >> sr;
44    su_int carry = 0;
45    for (; sr > 0; --sr)
46    {
47        /* r:q = ((r:q)  << 1) | carry */
48        r = (r << 1) | (q >> (n_uword_bits - 1));
49        q = (q << 1) | carry;
50        /* carry = 0;
51         * if (r.all >= d.all)
52         * {
53         *      r.all -= d.all;
54         *      carry = 1;
55         * }
56         */
57        const si_int s = (si_int)(d - r - 1) >> (n_uword_bits - 1);
58        carry = s & 1;
59        r -= d & s;
60    }
61    q = (q << 1) | carry;
62    return q;
63}
64