Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 1 | /* ===-- udivmodti4.c - Implement __udivmodti4 -----------------------------=== |
| 2 | * |
| 3 | * The LLVM Compiler Infrastructure |
| 4 | * |
Howard Hinnant | 9ad441f | 2010-11-16 22:13:33 +0000 | [diff] [blame] | 5 | * This file is dual licensed under the MIT and the University of Illinois Open |
| 6 | * Source Licenses. See LICENSE.TXT for details. |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 7 | * |
| 8 | * ===----------------------------------------------------------------------=== |
| 9 | * |
| 10 | * This file implements __udivmodti4 for the compiler_rt library. |
| 11 | * |
| 12 | * ===----------------------------------------------------------------------=== |
| 13 | */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 14 | |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 15 | #include "int_lib.h" |
| 16 | |
Chandler Carruth | 7f2d7c7 | 2012-06-22 21:09:22 +0000 | [diff] [blame^] | 17 | #if __x86_64 |
| 18 | |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 19 | /* Effects: if rem != 0, *rem = a % b |
| 20 | * Returns: a / b |
| 21 | */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 22 | |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 23 | /* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 24 | |
| 25 | tu_int |
| 26 | __udivmodti4(tu_int a, tu_int b, tu_int* rem) |
| 27 | { |
| 28 | const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT; |
| 29 | const unsigned n_utword_bits = sizeof(tu_int) * CHAR_BIT; |
| 30 | utwords n; |
| 31 | n.all = a; |
| 32 | utwords d; |
| 33 | d.all = b; |
| 34 | utwords q; |
| 35 | utwords r; |
| 36 | unsigned sr; |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 37 | /* special cases, X is unknown, K != 0 */ |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 38 | if (n.s.high == 0) |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 39 | { |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 40 | if (d.s.high == 0) |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 41 | { |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 42 | /* 0 X |
| 43 | * --- |
| 44 | * 0 X |
| 45 | */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 46 | if (rem) |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 47 | *rem = n.s.low % d.s.low; |
| 48 | return n.s.low / d.s.low; |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 49 | } |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 50 | /* 0 X |
| 51 | * --- |
| 52 | * K X |
| 53 | */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 54 | if (rem) |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 55 | *rem = n.s.low; |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 56 | return 0; |
| 57 | } |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 58 | /* n.s.high != 0 */ |
| 59 | if (d.s.low == 0) |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 60 | { |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 61 | if (d.s.high == 0) |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 62 | { |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 63 | /* K X |
| 64 | * --- |
| 65 | * 0 0 |
| 66 | */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 67 | if (rem) |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 68 | *rem = n.s.high % d.s.low; |
| 69 | return n.s.high / d.s.low; |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 70 | } |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 71 | /* d.s.high != 0 */ |
| 72 | if (n.s.low == 0) |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 73 | { |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 74 | /* K 0 |
| 75 | * --- |
| 76 | * K 0 |
| 77 | */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 78 | if (rem) |
| 79 | { |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 80 | r.s.high = n.s.high % d.s.high; |
| 81 | r.s.low = 0; |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 82 | *rem = r.all; |
| 83 | } |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 84 | return n.s.high / d.s.high; |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 85 | } |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 86 | /* K K |
| 87 | * --- |
| 88 | * K 0 |
| 89 | */ |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 90 | if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 91 | { |
| 92 | if (rem) |
| 93 | { |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 94 | r.s.low = n.s.low; |
| 95 | r.s.high = n.s.high & (d.s.high - 1); |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 96 | *rem = r.all; |
| 97 | } |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 98 | return n.s.high >> __builtin_ctzll(d.s.high); |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 99 | } |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 100 | /* K K |
| 101 | * --- |
| 102 | * K 0 |
| 103 | */ |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 104 | sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high); |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 105 | /* 0 <= sr <= n_udword_bits - 2 or sr large */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 106 | if (sr > n_udword_bits - 2) |
| 107 | { |
| 108 | if (rem) |
| 109 | *rem = n.all; |
| 110 | return 0; |
| 111 | } |
| 112 | ++sr; |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 113 | /* 1 <= sr <= n_udword_bits - 1 */ |
| 114 | /* q.all = n.all << (n_utword_bits - sr); */ |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 115 | q.s.low = 0; |
| 116 | q.s.high = n.s.low << (n_udword_bits - sr); |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 117 | /* r.all = n.all >> sr; */ |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 118 | r.s.high = n.s.high >> sr; |
| 119 | r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr); |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 120 | } |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 121 | else /* d.s.low != 0 */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 122 | { |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 123 | if (d.s.high == 0) |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 124 | { |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 125 | /* K X |
| 126 | * --- |
| 127 | * 0 K |
| 128 | */ |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 129 | if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 130 | { |
| 131 | if (rem) |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 132 | *rem = n.s.low & (d.s.low - 1); |
| 133 | if (d.s.low == 1) |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 134 | return n.all; |
Joerg Sonnenberger | 4fcc9aa | 2011-07-28 23:15:41 +0000 | [diff] [blame] | 135 | sr = __builtin_ctzll(d.s.low); |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 136 | q.s.high = n.s.high >> sr; |
| 137 | q.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr); |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 138 | return q.all; |
| 139 | } |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 140 | /* K X |
| 141 | * --- |
| 142 | * 0 K |
| 143 | */ |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 144 | sr = 1 + n_udword_bits + __builtin_clzll(d.s.low) |
| 145 | - __builtin_clzll(n.s.high); |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 146 | /* 2 <= sr <= n_utword_bits - 1 |
| 147 | * q.all = n.all << (n_utword_bits - sr); |
| 148 | * r.all = n.all >> sr; |
| 149 | * if (sr == n_udword_bits) |
| 150 | * { |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 151 | * q.s.low = 0; |
| 152 | * q.s.high = n.s.low; |
| 153 | * r.s.high = 0; |
| 154 | * r.s.low = n.s.high; |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 155 | * } |
| 156 | * else if (sr < n_udword_bits) // 2 <= sr <= n_udword_bits - 1 |
| 157 | * { |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 158 | * q.s.low = 0; |
| 159 | * q.s.high = n.s.low << (n_udword_bits - sr); |
| 160 | * r.s.high = n.s.high >> sr; |
| 161 | * r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr); |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 162 | * } |
| 163 | * else // n_udword_bits + 1 <= sr <= n_utword_bits - 1 |
| 164 | * { |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 165 | * q.s.low = n.s.low << (n_utword_bits - sr); |
| 166 | * q.s.high = (n.s.high << (n_utword_bits - sr)) | |
| 167 | * (n.s.low >> (sr - n_udword_bits)); |
| 168 | * r.s.high = 0; |
| 169 | * r.s.low = n.s.high >> (sr - n_udword_bits); |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 170 | * } |
| 171 | */ |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 172 | q.s.low = (n.s.low << (n_utword_bits - sr)) & |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 173 | ((di_int)(int)(n_udword_bits - sr) >> (n_udword_bits-1)); |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 174 | q.s.high = ((n.s.low << ( n_udword_bits - sr)) & |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 175 | ((di_int)(int)(sr - n_udword_bits - 1) >> (n_udword_bits-1))) | |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 176 | (((n.s.high << (n_utword_bits - sr)) | |
| 177 | (n.s.low >> (sr - n_udword_bits))) & |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 178 | ((di_int)(int)(n_udword_bits - sr) >> (n_udword_bits-1))); |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 179 | r.s.high = (n.s.high >> sr) & |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 180 | ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1)); |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 181 | r.s.low = ((n.s.high >> (sr - n_udword_bits)) & |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 182 | ((di_int)(int)(n_udword_bits - sr - 1) >> (n_udword_bits-1))) | |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 183 | (((n.s.high << (n_udword_bits - sr)) | |
| 184 | (n.s.low >> sr)) & |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 185 | ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1))); |
| 186 | } |
| 187 | else |
| 188 | { |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 189 | /* K X |
| 190 | * --- |
| 191 | * K K |
| 192 | */ |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 193 | sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high); |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 194 | /*0 <= sr <= n_udword_bits - 1 or sr large */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 195 | if (sr > n_udword_bits - 1) |
| 196 | { |
| 197 | if (rem) |
| 198 | *rem = n.all; |
| 199 | return 0; |
| 200 | } |
| 201 | ++sr; |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 202 | /* 1 <= sr <= n_udword_bits */ |
| 203 | /* q.all = n.all << (n_utword_bits - sr); */ |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 204 | q.s.low = 0; |
| 205 | q.s.high = n.s.low << (n_udword_bits - sr); |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 206 | /* r.all = n.all >> sr; |
| 207 | * if (sr < n_udword_bits) |
| 208 | * { |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 209 | * r.s.high = n.s.high >> sr; |
| 210 | * r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr); |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 211 | * } |
| 212 | * else |
| 213 | * { |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 214 | * r.s.high = 0; |
| 215 | * r.s.low = n.s.high; |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 216 | * } |
| 217 | */ |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 218 | r.s.high = (n.s.high >> sr) & |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 219 | ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1)); |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 220 | r.s.low = (n.s.high << (n_udword_bits - sr)) | |
| 221 | ((n.s.low >> sr) & |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 222 | ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1))); |
| 223 | } |
| 224 | } |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 225 | /* Not a special case |
| 226 | * q and r are initialized with: |
| 227 | * q.all = n.all << (n_utword_bits - sr); |
| 228 | * r.all = n.all >> sr; |
| 229 | * 1 <= sr <= n_utword_bits - 1 |
| 230 | */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 231 | su_int carry = 0; |
| 232 | for (; sr > 0; --sr) |
| 233 | { |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 234 | /* r:q = ((r:q) << 1) | carry */ |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 235 | r.s.high = (r.s.high << 1) | (r.s.low >> (n_udword_bits - 1)); |
| 236 | r.s.low = (r.s.low << 1) | (q.s.high >> (n_udword_bits - 1)); |
| 237 | q.s.high = (q.s.high << 1) | (q.s.low >> (n_udword_bits - 1)); |
| 238 | q.s.low = (q.s.low << 1) | carry; |
Edward O'Callaghan | 37a6a45 | 2009-08-07 20:30:09 +0000 | [diff] [blame] | 239 | /* carry = 0; |
| 240 | * if (r.all >= d.all) |
| 241 | * { |
| 242 | * r.all -= d.all; |
| 243 | * carry = 1; |
| 244 | * } |
| 245 | */ |
Daniel Dunbar | b3a6901 | 2009-06-26 16:47:03 +0000 | [diff] [blame] | 246 | const ti_int s = (ti_int)(d.all - r.all - 1) >> (n_utword_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 | } |
| 255 | |
Edward O'Callaghan | 8bf1e09 | 2009-08-09 18:41:02 +0000 | [diff] [blame] | 256 | #endif /* __x86_64 */ |