contrib/llvm-project/compiler-rt/lib/builtins/udivmoddi4.c

   1 //===-- udivmoddi4.c - Implement __udivmoddi4 -----------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements __udivmoddi4 for the compiler_rt library.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "int_lib.h"
  14
  15 // Effects: if rem != 0, *rem = a % b
  16 // Returns: a / b
  17
  18 // Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide
  19
  20 COMPILER_RT_ABI du_int __udivmoddi4(du_int a, du_int b, du_int *rem) {
  21   const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT;
  22   const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;
  23   udwords n;
  24   n.all = a;
  25   udwords d;
  26   d.all = b;
  27   udwords q;
  28   udwords r;
  29   unsigned sr;
  30   // special cases, X is unknown, K != 0
  31   if (n.s.high == 0) {
  32     if (d.s.high == 0) {
  33       // 0 X
  34       // ---
  35       // 0 X
  36       if (rem)
  37         *rem = n.s.low % d.s.low;
  38       return n.s.low / d.s.low;
  39     }
  40     // 0 X
  41     // ---
  42     // K X
  43     if (rem)
  44       *rem = n.s.low;
  45     return 0;
  46   }
  47   // n.s.high != 0
  48   if (d.s.low == 0) {
  49     if (d.s.high == 0) {
  50       // K X
  51       // ---
  52       // 0 0
  53       if (rem)
  54         *rem = n.s.high % d.s.low;
  55       return n.s.high / d.s.low;
  56     }
  57     // d.s.high != 0
  58     if (n.s.low == 0) {
  59       // K 0
  60       // ---
  61       // K 0
  62       if (rem) {
  63         r.s.high = n.s.high % d.s.high;
  64         r.s.low = 0;
  65         *rem = r.all;
  66       }
  67       return n.s.high / d.s.high;
  68     }
  69     // K K
  70     // ---
  71     // K 0
  72     if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ {
  73       if (rem) {
  74         r.s.low = n.s.low;
  75         r.s.high = n.s.high & (d.s.high - 1);
  76         *rem = r.all;
  77       }
  78       return n.s.high >> __builtin_ctz(d.s.high);
  79     }
  80     // K K
  81     // ---
  82     // K 0
  83     sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
  84     // 0 <= sr <= n_uword_bits - 2 or sr large
  85     if (sr > n_uword_bits - 2) {
  86       if (rem)
  87         *rem = n.all;
  88       return 0;
  89     }
  90     ++sr;
  91     // 1 <= sr <= n_uword_bits - 1
  92     // q.all = n.all << (n_udword_bits - sr);
  93     q.s.low = 0;
  94     q.s.high = n.s.low << (n_uword_bits - sr);
  95     // r.all = n.all >> sr;
  96     r.s.high = n.s.high >> sr;
  97     r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
  98   } else /* d.s.low != 0 */ {
  99     if (d.s.high == 0) {
 100       // K X
 101       // ---
 102       // 0 K
 103       if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ {
 104         if (rem)
 105           *rem = n.s.low & (d.s.low - 1);
 106         if (d.s.low == 1)
 107           return n.all;
 108         sr = __builtin_ctz(d.s.low);
 109         q.s.high = n.s.high >> sr;
 110         q.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
 111         return q.all;
 112       }
 113       // K X
 114       // ---
 115       // 0 K
 116       sr = 1 + n_uword_bits + __builtin_clz(d.s.low) - __builtin_clz(n.s.high);
 117       // 2 <= sr <= n_udword_bits - 1
 118       // q.all = n.all << (n_udword_bits - sr);
 119       // r.all = n.all >> sr;
 120       if (sr == n_uword_bits) {
 121         q.s.low = 0;
 122         q.s.high = n.s.low;
 123         r.s.high = 0;
 124         r.s.low = n.s.high;
 125       } else if (sr < n_uword_bits) /* 2 <= sr <= n_uword_bits - 1 */ {
 126         q.s.low = 0;
 127         q.s.high = n.s.low << (n_uword_bits - sr);
 128         r.s.high = n.s.high >> sr;
 129         r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
 130       } else /* n_uword_bits + 1 <= sr <= n_udword_bits - 1 */ {
 131         q.s.low = n.s.low << (n_udword_bits - sr);
 132         q.s.high = (n.s.high << (n_udword_bits - sr)) |
 133                    (n.s.low >> (sr - n_uword_bits));
 134         r.s.high = 0;
 135         r.s.low = n.s.high >> (sr - n_uword_bits);
 136       }
 137     } else {
 138       // K X
 139       // ---
 140       // K K
 141       sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
 142       // 0 <= sr <= n_uword_bits - 1 or sr large
 143       if (sr > n_uword_bits - 1) {
 144         if (rem)
 145           *rem = n.all;
 146         return 0;
 147       }
 148       ++sr;
 149       // 1 <= sr <= n_uword_bits
 150       // q.all = n.all << (n_udword_bits - sr);
 151       q.s.low = 0;
 152       if (sr == n_uword_bits) {
 153         q.s.high = n.s.low;
 154         r.s.high = 0;
 155         r.s.low = n.s.high;
 156       } else {
 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     }
 162   }
 163   // Not a special case
 164   // q and r are initialized with:
 165   // q.all = n.all << (n_udword_bits - sr);
 166   // r.all = n.all >> sr;
 167   // 1 <= sr <= n_udword_bits - 1
 168   su_int carry = 0;
 169   for (; sr > 0; --sr) {
 170     // r:q = ((r:q)  << 1) | carry
 171     r.s.high = (r.s.high << 1) | (r.s.low >> (n_uword_bits - 1));
 172     r.s.low = (r.s.low << 1) | (q.s.high >> (n_uword_bits - 1));
 173     q.s.high = (q.s.high << 1) | (q.s.low >> (n_uword_bits - 1));
 174     q.s.low = (q.s.low << 1) | carry;
 175     // carry = 0;
 176     // if (r.all >= d.all)
 177     // {
 178     //      r.all -= d.all;
 179     //      carry = 1;
 180     // }
 181     const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1);
 182     carry = s & 1;
 183     r.all -= d.all & s;
 184   }
 185   q.all = (q.all << 1) | carry;
 186   if (rem)
 187     *rem = r.all;
 188   return q.all;
 189 }