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