contrib/compiler-rt/lib/udivmoddi4.c

   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 ARM_EABI_FNALIAS(uldivmod, udivmoddi4);
  24
  25 COMPILER_RT_ABI du_int
  26 __udivmoddi4(du_int a, du_int b, du_int* rem)
  27 {
  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     {
  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_ctz(d.s.high);
  99         }
 100         /* K K
 101          * ---
 102          * K 0
 103          */
 104         sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
 105         /* 0 <= sr <= n_uword_bits - 2 or sr large */
 106         if (sr > n_uword_bits - 2)
 107         {
 108            if (rem)
 109                 *rem = n.all;
 110             return 0;
 111         }
 112         ++sr;
 113         /* 1 <= sr <= n_uword_bits - 1 */
 114         /* q.all = n.all << (n_udword_bits - sr); */
 115         q.s.low = 0;
 116         q.s.high = n.s.low << (n_uword_bits - sr);
 117         /* r.all = n.all >> sr; */
 118         r.s.high = n.s.high >> sr;
 119         r.s.low = (n.s.high << (n_uword_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_ctz(d.s.low);
 136                 q.s.high = n.s.high >> sr;
 137                 q.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
 138                 return q.all;
 139             }
 140             /* K X
 141              * ---
 142              *0 K
 143              */
 144             sr = 1 + n_uword_bits + __builtin_clz(d.s.low) - __builtin_clz(n.s.high);
 145             /* 2 <= sr <= n_udword_bits - 1
 146              * q.all = n.all << (n_udword_bits - sr);
 147              * r.all = n.all >> sr;
 148              * if (sr == n_uword_bits)
 149              * {
 150              *     q.s.low = 0;
 151              *     q.s.high = n.s.low;
 152              *     r.s.high = 0;
 153              *     r.s.low = n.s.high;
 154              * }
 155              * else if (sr < n_uword_bits)  // 2 <= sr <= n_uword_bits - 1
 156              * {
 157              *     q.s.low = 0;
 158              *     q.s.high = n.s.low << (n_uword_bits - sr);
 159              *     r.s.high = n.s.high >> sr;
 160              *     r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
 161              * }
 162              * else              // n_uword_bits + 1 <= sr <= n_udword_bits - 1
 163              * {
 164              *     q.s.low = n.s.low << (n_udword_bits - sr);
 165              *     q.s.high = (n.s.high << (n_udword_bits - sr)) |
 166              *              (n.s.low >> (sr - n_uword_bits));
 167              *     r.s.high = 0;
 168              *     r.s.low = n.s.high >> (sr - n_uword_bits);
 169              * }
 170              */
 171             q.s.low =  (n.s.low << (n_udword_bits - sr)) &
 172                      ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1));
 173             q.s.high = ((n.s.low << ( n_uword_bits - sr))                       &
 174                      ((si_int)(sr - n_uword_bits - 1) >> (n_uword_bits-1))) |
 175                      (((n.s.high << (n_udword_bits - sr))                     |
 176                      (n.s.low >> (sr - n_uword_bits)))                        &
 177                      ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1)));
 178             r.s.high = (n.s.high >> sr) &
 179                      ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1));
 180             r.s.low =  ((n.s.high >> (sr - n_uword_bits))                       &
 181                      ((si_int)(n_uword_bits - sr - 1) >> (n_uword_bits-1))) |
 182                      (((n.s.high << (n_uword_bits - sr))                      |
 183                      (n.s.low >> sr))                                         &
 184                      ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)));
 185         }
 186         else
 187         {
 188             /* K X
 189              * ---
 190              * K K
 191              */
 192             sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
 193             /* 0 <= sr <= n_uword_bits - 1 or sr large */
 194             if (sr > n_uword_bits - 1)
 195             {
 196                if (rem)
 197                     *rem = n.all;
 198                 return 0;
 199             }
 200             ++sr;
 201             /* 1 <= sr <= n_uword_bits */
 202             /*  q.all = n.all << (n_udword_bits - sr); */
 203             q.s.low = 0;
 204             q.s.high = n.s.low << (n_uword_bits - sr);
 205             /* r.all = n.all >> sr;
 206              * if (sr < n_uword_bits)
 207              * {
 208              *     r.s.high = n.s.high >> sr;
 209              *     r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
 210              * }
 211              * else
 212              * {
 213              *     r.s.high = 0;
 214              *     r.s.low = n.s.high;
 215              * }
 216              */
 217             r.s.high = (n.s.high >> sr) &
 218                      ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1));
 219             r.s.low = (n.s.high << (n_uword_bits - sr)) |
 220                     ((n.s.low >> sr)                  &
 221                     ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)));
 222         }
 223     }
 224     /* Not a special case
 225      * q and r are initialized with:
 226      * q.all = n.all << (n_udword_bits - sr);
 227      * r.all = n.all >> sr;
 228      * 1 <= sr <= n_udword_bits - 1
 229      */
 230     su_int carry = 0;
 231     for (; sr > 0; --sr)
 232     {
 233         /* r:q = ((r:q)  << 1) | carry */
 234         r.s.high = (r.s.high << 1) | (r.s.low  >> (n_uword_bits - 1));
 235         r.s.low  = (r.s.low  << 1) | (q.s.high >> (n_uword_bits - 1));
 236         q.s.high = (q.s.high << 1) | (q.s.low  >> (n_uword_bits - 1));
 237         q.s.low  = (q.s.low  << 1) | carry;
 238         /* carry = 0;
 239          * if (r.all >= d.all)
 240          * {
 241          *      r.all -= d.all;
 242          *      carry = 1;
 243          * }
 244          */
 245         const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1);
 246         carry = s & 1;
 247         r.all -= d.all & s;
 248     }
 249     q.all = (q.all << 1) | carry;
 250     if (rem)
 251         *rem = r.all;
 252     return q.all;
 253 }