1*3cab2bb3Spatrick //===-- udivsi3.c - Implement __udivsi3 -----------------------------------===// 2*3cab2bb3Spatrick // 3*3cab2bb3Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*3cab2bb3Spatrick // See https://llvm.org/LICENSE.txt for license information. 5*3cab2bb3Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*3cab2bb3Spatrick // 7*3cab2bb3Spatrick //===----------------------------------------------------------------------===// 8*3cab2bb3Spatrick // 9*3cab2bb3Spatrick // This file implements __udivsi3 for the compiler_rt library. 10*3cab2bb3Spatrick // 11*3cab2bb3Spatrick //===----------------------------------------------------------------------===// 12*3cab2bb3Spatrick 13*3cab2bb3Spatrick #include "int_lib.h" 14*3cab2bb3Spatrick 15*3cab2bb3Spatrick // Returns: a / b 16*3cab2bb3Spatrick 17*3cab2bb3Spatrick // Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide 18*3cab2bb3Spatrick 19*3cab2bb3Spatrick // This function should not call __divsi3! 20*3cab2bb3Spatrick COMPILER_RT_ABI su_int __udivsi3(su_int n, su_int d) { 21*3cab2bb3Spatrick const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT; 22*3cab2bb3Spatrick su_int q; 23*3cab2bb3Spatrick su_int r; 24*3cab2bb3Spatrick unsigned sr; 25*3cab2bb3Spatrick // special cases 26*3cab2bb3Spatrick if (d == 0) 27*3cab2bb3Spatrick return 0; // ?! 28*3cab2bb3Spatrick if (n == 0) 29*3cab2bb3Spatrick return 0; 30*3cab2bb3Spatrick sr = __builtin_clz(d) - __builtin_clz(n); 31*3cab2bb3Spatrick // 0 <= sr <= n_uword_bits - 1 or sr large 32*3cab2bb3Spatrick if (sr > n_uword_bits - 1) // d > r 33*3cab2bb3Spatrick return 0; 34*3cab2bb3Spatrick if (sr == n_uword_bits - 1) // d == 1 35*3cab2bb3Spatrick return n; 36*3cab2bb3Spatrick ++sr; 37*3cab2bb3Spatrick // 1 <= sr <= n_uword_bits - 1 38*3cab2bb3Spatrick // Not a special case 39*3cab2bb3Spatrick q = n << (n_uword_bits - sr); 40*3cab2bb3Spatrick r = n >> sr; 41*3cab2bb3Spatrick su_int carry = 0; 42*3cab2bb3Spatrick for (; sr > 0; --sr) { 43*3cab2bb3Spatrick // r:q = ((r:q) << 1) | carry 44*3cab2bb3Spatrick r = (r << 1) | (q >> (n_uword_bits - 1)); 45*3cab2bb3Spatrick q = (q << 1) | carry; 46*3cab2bb3Spatrick // carry = 0; 47*3cab2bb3Spatrick // if (r.all >= d.all) 48*3cab2bb3Spatrick // { 49*3cab2bb3Spatrick // r.all -= d.all; 50*3cab2bb3Spatrick // carry = 1; 51*3cab2bb3Spatrick // } 52*3cab2bb3Spatrick const si_int s = (si_int)(d - r - 1) >> (n_uword_bits - 1); 53*3cab2bb3Spatrick carry = s & 1; 54*3cab2bb3Spatrick r -= d & s; 55*3cab2bb3Spatrick } 56*3cab2bb3Spatrick q = (q << 1) | carry; 57*3cab2bb3Spatrick return q; 58*3cab2bb3Spatrick } 59*3cab2bb3Spatrick 60*3cab2bb3Spatrick #if defined(__ARM_EABI__) 61*3cab2bb3Spatrick COMPILER_RT_ALIAS(__udivsi3, __aeabi_uidiv) 62*3cab2bb3Spatrick #endif 63