1214152Sed/* ===-- udivsi3.c - Implement __udivsi3 -----------------------------------=== 2214152Sed * 3214152Sed * The LLVM Compiler Infrastructure 4214152Sed * 5222656Sed * This file is dual licensed under the MIT and the University of Illinois Open 6222656Sed * Source Licenses. See LICENSE.TXT for details. 7214152Sed * 8214152Sed * ===----------------------------------------------------------------------=== 9214152Sed * 10214152Sed * This file implements __udivsi3 for the compiler_rt library. 11214152Sed * 12214152Sed * ===----------------------------------------------------------------------=== 13214152Sed */ 14214152Sed 15214152Sed#include "int_lib.h" 16214152Sed 17214152Sed/* Returns: a / b */ 18214152Sed 19214152Sed/* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */ 20214152Sed 21263560SdimARM_EABI_FNALIAS(uidiv, udivsi3) 22222656Sed 23263560Sdim/* This function should not call __divsi3! */ 24222656SedCOMPILER_RT_ABI su_int 25214152Sed__udivsi3(su_int n, su_int d) 26214152Sed{ 27214152Sed const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT; 28214152Sed su_int q; 29214152Sed su_int r; 30214152Sed unsigned sr; 31214152Sed /* special cases */ 32214152Sed if (d == 0) 33214152Sed return 0; /* ?! */ 34214152Sed if (n == 0) 35214152Sed return 0; 36214152Sed sr = __builtin_clz(d) - __builtin_clz(n); 37214152Sed /* 0 <= sr <= n_uword_bits - 1 or sr large */ 38214152Sed if (sr > n_uword_bits - 1) /* d > r */ 39214152Sed return 0; 40214152Sed if (sr == n_uword_bits - 1) /* d == 1 */ 41214152Sed return n; 42214152Sed ++sr; 43214152Sed /* 1 <= sr <= n_uword_bits - 1 */ 44214152Sed /* Not a special case */ 45214152Sed q = n << (n_uword_bits - sr); 46214152Sed r = n >> sr; 47214152Sed su_int carry = 0; 48214152Sed for (; sr > 0; --sr) 49214152Sed { 50214152Sed /* r:q = ((r:q) << 1) | carry */ 51214152Sed r = (r << 1) | (q >> (n_uword_bits - 1)); 52214152Sed q = (q << 1) | carry; 53214152Sed /* carry = 0; 54214152Sed * if (r.all >= d.all) 55214152Sed * { 56214152Sed * r.all -= d.all; 57214152Sed * carry = 1; 58214152Sed * } 59214152Sed */ 60214152Sed const si_int s = (si_int)(d - r - 1) >> (n_uword_bits - 1); 61214152Sed carry = s & 1; 62214152Sed r -= d & s; 63214152Sed } 64214152Sed q = (q << 1) | carry; 65214152Sed return q; 66214152Sed} 67