int_div_impl.inc (4975B)
1 //===-- int_div_impl.inc - Integer division ---------------------*- C++ -*-===// 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 // Helpers used by __udivsi3, __umodsi3, __udivdi3, and __umodsi3. 10 // 11 // Re-includable; safe to use multiple times in one TU. Inputs (caller 12 // must #define before each #include): 13 // fixint_t, fixuint_t -- the signed/unsigned integer width 14 // INT_DIV_SUFFIX -- a unique token; helper names get suffixed 15 // with `_<INT_DIV_SUFFIX>` so concurrent 16 // inclusions don't collide 17 // Optional inputs (gate emission of the signed wrappers): 18 // COMPUTE_UDIV(a, b) -- expression yielding unsigned quotient 19 // ASSIGN_UMOD(res, a, b)-- statement assigning unsigned remainder to res 20 // 21 // Outputs (always emitted as `static inline`): 22 // __udivXi3_<suffix>, __umodXi3_<suffix> 23 // Plus, conditionally: 24 // __divXi3_<suffix> iff COMPUTE_UDIV is defined 25 // __modXi3_<suffix> iff ASSIGN_UMOD is defined 26 // 27 // At exit the inc #undef's all of its inputs (including INT_DIV_SUFFIX, 28 // COMPUTE_UDIV, ASSIGN_UMOD, fixint_t, fixuint_t) so it's clean to 29 // re-include with new settings. 30 // 31 //===----------------------------------------------------------------------===// 32 33 #ifndef INT_DIV_IMPL_INC_GUARD 34 #define INT_DIV_IMPL_INC_GUARD 35 #define INT_DIV_IMPL_CAT_(a, b) a##b 36 #define INT_DIV_IMPL_CAT(a, b) INT_DIV_IMPL_CAT_(a, b) 37 #define INT_DIV_IMPL_CLZ(a) \ 38 (sizeof(a) == sizeof(unsigned long long) ? __builtin_clzll(a) : clzsi(a)) 39 #endif 40 41 #ifndef INT_DIV_SUFFIX 42 #error "int_div_impl.inc: INT_DIV_SUFFIX must be defined before #include" 43 #endif 44 45 // Adapted from Figure 3-40 of The PowerPC Compiler Writer's Guide 46 static inline fixuint_t 47 INT_DIV_IMPL_CAT(__udivXi3_, INT_DIV_SUFFIX)(fixuint_t n, fixuint_t d) { 48 const unsigned N = sizeof(fixuint_t) * CHAR_BIT; 49 // d == 0 cases are unspecified. 50 unsigned sr = (d ? INT_DIV_IMPL_CLZ(d) : N) - (n ? INT_DIV_IMPL_CLZ(n) : N); 51 // 0 <= sr <= N - 1 or sr is very large. 52 if (sr > N - 1) // n < d 53 return 0; 54 if (sr == N - 1) // d == 1 55 return n; 56 ++sr; 57 // 1 <= sr <= N - 1. Shifts do not trigger UB. 58 fixuint_t r = n >> sr; 59 n <<= N - sr; 60 fixuint_t carry = 0; 61 for (; sr > 0; --sr) { 62 r = (r << 1) | (n >> (N - 1)); 63 n = (n << 1) | carry; 64 // Branch-less version of: 65 // carry = 0; 66 // if (r >= d) r -= d, carry = 1; 67 const fixint_t s = (fixint_t)(d - r - 1) >> (N - 1); 68 carry = s & 1; 69 r -= d & s; 70 } 71 n = (n << 1) | carry; 72 return n; 73 } 74 75 // Mostly identical to __udivXi3 but the return values are different. 76 static inline fixuint_t 77 INT_DIV_IMPL_CAT(__umodXi3_, INT_DIV_SUFFIX)(fixuint_t n, fixuint_t d) { 78 const unsigned N = sizeof(fixuint_t) * CHAR_BIT; 79 // d == 0 cases are unspecified. 80 unsigned sr = (d ? INT_DIV_IMPL_CLZ(d) : N) - (n ? INT_DIV_IMPL_CLZ(n) : N); 81 // 0 <= sr <= N - 1 or sr is very large. 82 if (sr > N - 1) // n < d 83 return n; 84 if (sr == N - 1) // d == 1 85 return 0; 86 ++sr; 87 // 1 <= sr <= N - 1. Shifts do not trigger UB. 88 fixuint_t r = n >> sr; 89 n <<= N - sr; 90 fixuint_t carry = 0; 91 for (; sr > 0; --sr) { 92 r = (r << 1) | (n >> (N - 1)); 93 n = (n << 1) | carry; 94 // Branch-less version of: 95 // carry = 0; 96 // if (r >= d) r -= d, carry = 1; 97 const fixint_t s = (fixint_t)(d - r - 1) >> (N - 1); 98 carry = s & 1; 99 r -= d & s; 100 } 101 return r; 102 } 103 104 #ifdef COMPUTE_UDIV 105 static inline fixint_t 106 INT_DIV_IMPL_CAT(__divXi3_, INT_DIV_SUFFIX)(fixint_t a, fixint_t b) { 107 const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1; 108 fixint_t s_a = a >> N; // s_a = a < 0 ? -1 : 0 109 fixint_t s_b = b >> N; // s_b = b < 0 ? -1 : 0 110 fixuint_t a_u = (fixuint_t)(a ^ s_a) + (-s_a); // negate if s_a == -1 111 fixuint_t b_u = (fixuint_t)(b ^ s_b) + (-s_b); // negate if s_b == -1 112 s_a ^= s_b; // sign of quotient 113 return (COMPUTE_UDIV(a_u, b_u) ^ s_a) + (-s_a); // negate if s_a == -1 114 } 115 #endif // COMPUTE_UDIV 116 117 #ifdef ASSIGN_UMOD 118 static inline fixint_t 119 INT_DIV_IMPL_CAT(__modXi3_, INT_DIV_SUFFIX)(fixint_t a, fixint_t b) { 120 const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1; 121 fixint_t s = b >> N; // s = b < 0 ? -1 : 0 122 fixuint_t b_u = (fixuint_t)(b ^ s) + (-s); // negate if s == -1 123 s = a >> N; // s = a < 0 ? -1 : 0 124 fixuint_t a_u = (fixuint_t)(a ^ s) + (-s); // negate if s == -1 125 fixuint_t res; 126 ASSIGN_UMOD(res, a_u, b_u); 127 return (res ^ s) + (-s); // negate if s == -1 128 } 129 #endif // ASSIGN_UMOD 130 131 #undef INT_DIV_SUFFIX 132 #undef COMPUTE_UDIV 133 #undef ASSIGN_UMOD 134 #undef fixint_t 135 #undef fixuint_t