15ffd83dbSDimitry Andric//===-- int_div_impl.inc - Integer division ---------------------*- C++ -*-===// 25ffd83dbSDimitry Andric// 35ffd83dbSDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 45ffd83dbSDimitry Andric// See https://llvm.org/LICENSE.txt for license information. 55ffd83dbSDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 65ffd83dbSDimitry Andric// 75ffd83dbSDimitry Andric//===----------------------------------------------------------------------===// 85ffd83dbSDimitry Andric// 95ffd83dbSDimitry Andric// Helpers used by __udivsi3, __umodsi3, __udivdi3, and __umodsi3. 105ffd83dbSDimitry Andric// 115ffd83dbSDimitry Andric//===----------------------------------------------------------------------===// 125ffd83dbSDimitry Andric 135ffd83dbSDimitry Andric#define clz(a) (sizeof(a) == sizeof(unsigned long long) ? __builtin_clzll(a) : clzsi(a)) 145ffd83dbSDimitry Andric 155ffd83dbSDimitry Andric// Adapted from Figure 3-40 of The PowerPC Compiler Writer's Guide 165ffd83dbSDimitry Andricstatic __inline fixuint_t __udivXi3(fixuint_t n, fixuint_t d) { 175ffd83dbSDimitry Andric const unsigned N = sizeof(fixuint_t) * CHAR_BIT; 185ffd83dbSDimitry Andric // d == 0 cases are unspecified. 195ffd83dbSDimitry Andric unsigned sr = (d ? clz(d) : N) - (n ? clz(n) : N); 205ffd83dbSDimitry Andric // 0 <= sr <= N - 1 or sr is very large. 215ffd83dbSDimitry Andric if (sr > N - 1) // n < d 225ffd83dbSDimitry Andric return 0; 235ffd83dbSDimitry Andric if (sr == N - 1) // d == 1 245ffd83dbSDimitry Andric return n; 255ffd83dbSDimitry Andric ++sr; 265ffd83dbSDimitry Andric // 1 <= sr <= N - 1. Shifts do not trigger UB. 275ffd83dbSDimitry Andric fixuint_t r = n >> sr; 285ffd83dbSDimitry Andric n <<= N - sr; 295ffd83dbSDimitry Andric fixuint_t carry = 0; 305ffd83dbSDimitry Andric for (; sr > 0; --sr) { 315ffd83dbSDimitry Andric r = (r << 1) | (n >> (N - 1)); 325ffd83dbSDimitry Andric n = (n << 1) | carry; 335ffd83dbSDimitry Andric // Branch-less version of: 345ffd83dbSDimitry Andric // carry = 0; 355ffd83dbSDimitry Andric // if (r >= d) r -= d, carry = 1; 365ffd83dbSDimitry Andric const fixint_t s = (fixint_t)(d - r - 1) >> (N - 1); 375ffd83dbSDimitry Andric carry = s & 1; 385ffd83dbSDimitry Andric r -= d & s; 395ffd83dbSDimitry Andric } 405ffd83dbSDimitry Andric n = (n << 1) | carry; 415ffd83dbSDimitry Andric return n; 425ffd83dbSDimitry Andric} 435ffd83dbSDimitry Andric 445ffd83dbSDimitry Andric// Mostly identical to __udivXi3 but the return values are different. 455ffd83dbSDimitry Andricstatic __inline fixuint_t __umodXi3(fixuint_t n, fixuint_t d) { 465ffd83dbSDimitry Andric const unsigned N = sizeof(fixuint_t) * CHAR_BIT; 475ffd83dbSDimitry Andric // d == 0 cases are unspecified. 485ffd83dbSDimitry Andric unsigned sr = (d ? clz(d) : N) - (n ? clz(n) : N); 495ffd83dbSDimitry Andric // 0 <= sr <= N - 1 or sr is very large. 505ffd83dbSDimitry Andric if (sr > N - 1) // n < d 515ffd83dbSDimitry Andric return n; 525ffd83dbSDimitry Andric if (sr == N - 1) // d == 1 535ffd83dbSDimitry Andric return 0; 545ffd83dbSDimitry Andric ++sr; 555ffd83dbSDimitry Andric // 1 <= sr <= N - 1. Shifts do not trigger UB. 565ffd83dbSDimitry Andric fixuint_t r = n >> sr; 575ffd83dbSDimitry Andric n <<= N - sr; 585ffd83dbSDimitry Andric fixuint_t carry = 0; 595ffd83dbSDimitry Andric for (; sr > 0; --sr) { 605ffd83dbSDimitry Andric r = (r << 1) | (n >> (N - 1)); 615ffd83dbSDimitry Andric n = (n << 1) | carry; 625ffd83dbSDimitry Andric // Branch-less version of: 635ffd83dbSDimitry Andric // carry = 0; 645ffd83dbSDimitry Andric // if (r >= d) r -= d, carry = 1; 655ffd83dbSDimitry Andric const fixint_t s = (fixint_t)(d - r - 1) >> (N - 1); 665ffd83dbSDimitry Andric carry = s & 1; 675ffd83dbSDimitry Andric r -= d & s; 685ffd83dbSDimitry Andric } 695ffd83dbSDimitry Andric return r; 705ffd83dbSDimitry Andric} 71*e8d8bef9SDimitry Andric 72*e8d8bef9SDimitry Andric#ifdef COMPUTE_UDIV 73*e8d8bef9SDimitry Andricstatic __inline fixint_t __divXi3(fixint_t a, fixint_t b) { 74*e8d8bef9SDimitry Andric const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1; 75*e8d8bef9SDimitry Andric fixint_t s_a = a >> N; // s_a = a < 0 ? -1 : 0 76*e8d8bef9SDimitry Andric fixint_t s_b = b >> N; // s_b = b < 0 ? -1 : 0 77*e8d8bef9SDimitry Andric fixuint_t a_u = (fixuint_t)(a ^ s_a) + (-s_a); // negate if s_a == -1 78*e8d8bef9SDimitry Andric fixuint_t b_u = (fixuint_t)(b ^ s_b) + (-s_b); // negate if s_b == -1 79*e8d8bef9SDimitry Andric s_a ^= s_b; // sign of quotient 80*e8d8bef9SDimitry Andric return (COMPUTE_UDIV(a_u, b_u) ^ s_a) + (-s_a); // negate if s_a == -1 81*e8d8bef9SDimitry Andric} 82*e8d8bef9SDimitry Andric#endif // COMPUTE_UDIV 83*e8d8bef9SDimitry Andric 84*e8d8bef9SDimitry Andric#ifdef ASSIGN_UMOD 85*e8d8bef9SDimitry Andricstatic __inline fixint_t __modXi3(fixint_t a, fixint_t b) { 86*e8d8bef9SDimitry Andric const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1; 87*e8d8bef9SDimitry Andric fixint_t s = b >> N; // s = b < 0 ? -1 : 0 88*e8d8bef9SDimitry Andric fixuint_t b_u = (fixuint_t)(b ^ s) + (-s); // negate if s == -1 89*e8d8bef9SDimitry Andric s = a >> N; // s = a < 0 ? -1 : 0 90*e8d8bef9SDimitry Andric fixuint_t a_u = (fixuint_t)(a ^ s) + (-s); // negate if s == -1 91*e8d8bef9SDimitry Andric fixuint_t res; 92*e8d8bef9SDimitry Andric ASSIGN_UMOD(res, a_u, b_u); 93*e8d8bef9SDimitry Andric return (res ^ s) + (-s); // negate if s == -1 94*e8d8bef9SDimitry Andric} 95*e8d8bef9SDimitry Andric#endif // ASSIGN_UMOD 96