11e57a46299244793beb27e74be171d1540606999oliviermartin/** @file 21e57a46299244793beb27e74be171d1540606999oliviermartin Compiler intrinsic for 32-bit unsigned div, ported from LLVM code. 31e57a46299244793beb27e74be171d1540606999oliviermartin 41e57a46299244793beb27e74be171d1540606999oliviermartin Copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR> 53402aac7d985bf8a9f9d3c639f3fe93609380513Ronald Cron 61e57a46299244793beb27e74be171d1540606999oliviermartin This program and the accompanying materials 71e57a46299244793beb27e74be171d1540606999oliviermartin are licensed and made available under the terms and conditions of the BSD License 81e57a46299244793beb27e74be171d1540606999oliviermartin which accompanies this distribution. The full text of the license may be found at 91e57a46299244793beb27e74be171d1540606999oliviermartin http://opensource.org/licenses/bsd-license.php 101e57a46299244793beb27e74be171d1540606999oliviermartin 111e57a46299244793beb27e74be171d1540606999oliviermartin THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, 121e57a46299244793beb27e74be171d1540606999oliviermartin WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. 131e57a46299244793beb27e74be171d1540606999oliviermartin 141e57a46299244793beb27e74be171d1540606999oliviermartin**/ 151e57a46299244793beb27e74be171d1540606999oliviermartin/** 161e57a46299244793beb27e74be171d1540606999oliviermartin University of Illinois/NCSA 171e57a46299244793beb27e74be171d1540606999oliviermartin Open Source License 183402aac7d985bf8a9f9d3c639f3fe93609380513Ronald Cron 191e57a46299244793beb27e74be171d1540606999oliviermartin Copyright (c) 2003-2008 University of Illinois at Urbana-Champaign. 201e57a46299244793beb27e74be171d1540606999oliviermartin All rights reserved. 213402aac7d985bf8a9f9d3c639f3fe93609380513Ronald Cron 221e57a46299244793beb27e74be171d1540606999oliviermartin Developed by: 233402aac7d985bf8a9f9d3c639f3fe93609380513Ronald Cron 241e57a46299244793beb27e74be171d1540606999oliviermartin LLVM Team 253402aac7d985bf8a9f9d3c639f3fe93609380513Ronald Cron 261e57a46299244793beb27e74be171d1540606999oliviermartin University of Illinois at Urbana-Champaign 273402aac7d985bf8a9f9d3c639f3fe93609380513Ronald Cron 281e57a46299244793beb27e74be171d1540606999oliviermartin http://llvm.org 293402aac7d985bf8a9f9d3c639f3fe93609380513Ronald Cron 301e57a46299244793beb27e74be171d1540606999oliviermartin Permission is hereby granted, free of charge, to any person obtaining a copy of 311e57a46299244793beb27e74be171d1540606999oliviermartin this software and associated documentation files (the "Software"), to deal with 321e57a46299244793beb27e74be171d1540606999oliviermartin the Software without restriction, including without limitation the rights to 331e57a46299244793beb27e74be171d1540606999oliviermartin use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies 341e57a46299244793beb27e74be171d1540606999oliviermartin of the Software, and to permit persons to whom the Software is furnished to do 351e57a46299244793beb27e74be171d1540606999oliviermartin so, subject to the following conditions: 363402aac7d985bf8a9f9d3c639f3fe93609380513Ronald Cron 371e57a46299244793beb27e74be171d1540606999oliviermartin * Redistributions of source code must retain the above copyright notice, 381e57a46299244793beb27e74be171d1540606999oliviermartin this list of conditions and the following disclaimers. 393402aac7d985bf8a9f9d3c639f3fe93609380513Ronald Cron 401e57a46299244793beb27e74be171d1540606999oliviermartin * Redistributions in binary form must reproduce the above copyright notice, 411e57a46299244793beb27e74be171d1540606999oliviermartin this list of conditions and the following disclaimers in the 421e57a46299244793beb27e74be171d1540606999oliviermartin documentation and/or other materials provided with the distribution. 433402aac7d985bf8a9f9d3c639f3fe93609380513Ronald Cron 441e57a46299244793beb27e74be171d1540606999oliviermartin * Neither the names of the LLVM Team, University of Illinois at 451e57a46299244793beb27e74be171d1540606999oliviermartin Urbana-Champaign, nor the names of its contributors may be used to 461e57a46299244793beb27e74be171d1540606999oliviermartin endorse or promote products derived from this Software without specific 471e57a46299244793beb27e74be171d1540606999oliviermartin prior written permission. 483402aac7d985bf8a9f9d3c639f3fe93609380513Ronald Cron 491e57a46299244793beb27e74be171d1540606999oliviermartin THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 501e57a46299244793beb27e74be171d1540606999oliviermartin IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS 511e57a46299244793beb27e74be171d1540606999oliviermartin FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 521e57a46299244793beb27e74be171d1540606999oliviermartin CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 531e57a46299244793beb27e74be171d1540606999oliviermartin LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 541e57a46299244793beb27e74be171d1540606999oliviermartin OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE 551e57a46299244793beb27e74be171d1540606999oliviermartin SOFTWARE. 561e57a46299244793beb27e74be171d1540606999oliviermartin**/ 571e57a46299244793beb27e74be171d1540606999oliviermartin 581e57a46299244793beb27e74be171d1540606999oliviermartin 591e57a46299244793beb27e74be171d1540606999oliviermartin#include "Llvm_int_lib.h" 601e57a46299244793beb27e74be171d1540606999oliviermartin 611e57a46299244793beb27e74be171d1540606999oliviermartin 621e57a46299244793beb27e74be171d1540606999oliviermartin// Returns: n / d 631e57a46299244793beb27e74be171d1540606999oliviermartin 641e57a46299244793beb27e74be171d1540606999oliviermartin// Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide 651e57a46299244793beb27e74be171d1540606999oliviermartin 661e57a46299244793beb27e74be171d1540606999oliviermartinUINT32 671e57a46299244793beb27e74be171d1540606999oliviermartin__udivsi3(UINT32 n, UINT32 d) 681e57a46299244793beb27e74be171d1540606999oliviermartin{ 691e57a46299244793beb27e74be171d1540606999oliviermartin const unsigned n_uword_bits = sizeof(UINT32) * CHAR_BIT; 701e57a46299244793beb27e74be171d1540606999oliviermartin UINT32 q; 711e57a46299244793beb27e74be171d1540606999oliviermartin UINT32 r; 721e57a46299244793beb27e74be171d1540606999oliviermartin unsigned sr; 731e57a46299244793beb27e74be171d1540606999oliviermartin 741e57a46299244793beb27e74be171d1540606999oliviermartin // special cases 751e57a46299244793beb27e74be171d1540606999oliviermartin if (d == 0) { 761e57a46299244793beb27e74be171d1540606999oliviermartin// ASSERT (FALSE); 771e57a46299244793beb27e74be171d1540606999oliviermartin return 0; // ?! 781e57a46299244793beb27e74be171d1540606999oliviermartin } 791e57a46299244793beb27e74be171d1540606999oliviermartin if (n == 0) 801e57a46299244793beb27e74be171d1540606999oliviermartin return 0; 811e57a46299244793beb27e74be171d1540606999oliviermartin 821e57a46299244793beb27e74be171d1540606999oliviermartin sr = COUNT_LEADING_ZEROS(d) - COUNT_LEADING_ZEROS(n); 831e57a46299244793beb27e74be171d1540606999oliviermartin // 0 <= sr <= n_uword_bits - 1 or sr large 841e57a46299244793beb27e74be171d1540606999oliviermartin if (sr > n_uword_bits - 1) // d > r 851e57a46299244793beb27e74be171d1540606999oliviermartin return 0; 861e57a46299244793beb27e74be171d1540606999oliviermartin if (sr == n_uword_bits - 1) // d == 1 871e57a46299244793beb27e74be171d1540606999oliviermartin return n; 881e57a46299244793beb27e74be171d1540606999oliviermartin ++sr; 891e57a46299244793beb27e74be171d1540606999oliviermartin // 1 <= sr <= n_uword_bits - 1 901e57a46299244793beb27e74be171d1540606999oliviermartin // Not a special case 911e57a46299244793beb27e74be171d1540606999oliviermartin q = n << (n_uword_bits - sr); 921e57a46299244793beb27e74be171d1540606999oliviermartin r = n >> sr; 931e57a46299244793beb27e74be171d1540606999oliviermartin UINT32 carry = 0; 941e57a46299244793beb27e74be171d1540606999oliviermartin for (; sr > 0; --sr) 951e57a46299244793beb27e74be171d1540606999oliviermartin { 961e57a46299244793beb27e74be171d1540606999oliviermartin // r:q = ((r:q) << 1) | carry 971e57a46299244793beb27e74be171d1540606999oliviermartin r = (r << 1) | (q >> (n_uword_bits - 1)); 981e57a46299244793beb27e74be171d1540606999oliviermartin q = (q << 1) | carry; 991e57a46299244793beb27e74be171d1540606999oliviermartin // carry = 0; 1001e57a46299244793beb27e74be171d1540606999oliviermartin // if (r.all >= d.all) 1011e57a46299244793beb27e74be171d1540606999oliviermartin // { 1021e57a46299244793beb27e74be171d1540606999oliviermartin // r.all -= d.all; 1031e57a46299244793beb27e74be171d1540606999oliviermartin // carry = 1; 1041e57a46299244793beb27e74be171d1540606999oliviermartin // } 1051e57a46299244793beb27e74be171d1540606999oliviermartin const INT32 s = (INT32)(d - r - 1) >> (n_uword_bits - 1); 1061e57a46299244793beb27e74be171d1540606999oliviermartin carry = s & 1; 1071e57a46299244793beb27e74be171d1540606999oliviermartin r -= d & s; 1081e57a46299244793beb27e74be171d1540606999oliviermartin } 1091e57a46299244793beb27e74be171d1540606999oliviermartin q = (q << 1) | carry; 1101e57a46299244793beb27e74be171d1540606999oliviermartin return q; 1111e57a46299244793beb27e74be171d1540606999oliviermartin} 112