+++ /dev/null
-/** @file\r
- Compiler intrinsic for 64-bit compare, ported from LLVM code.\r
-\r
- Copyright (c) 2008-2009, Apple Inc. All rights reserved.<BR>\r
-\r
- SPDX-License-Identifier: BSD-2-Clause-Patent\r
-\r
-**/\r
-/**\r
- University of Illinois/NCSA\r
- Open Source License\r
-\r
- Copyright (c) 2003-2008 University of Illinois at Urbana-Champaign.\r
- All rights reserved.\r
-\r
- Developed by:\r
-\r
- LLVM Team\r
-\r
- University of Illinois at Urbana-Champaign\r
-\r
- http://llvm.org\r
-\r
- Permission is hereby granted, free of charge, to any person obtaining a copy of\r
- this software and associated documentation files (the "Software"), to deal with\r
- the Software without restriction, including without limitation the rights to\r
- use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies\r
- of the Software, and to permit persons to whom the Software is furnished to do\r
- so, subject to the following conditions:\r
-\r
- * Redistributions of source code must retain the above copyright notice,\r
- this list of conditions and the following disclaimers.\r
-\r
- * Redistributions in binary form must reproduce the above copyright notice,\r
- this list of conditions and the following disclaimers in the\r
- documentation and/or other materials provided with the distribution.\r
-\r
- * Neither the names of the LLVM Team, University of Illinois at\r
- Urbana-Champaign, nor the names of its contributors may be used to\r
- endorse or promote products derived from this Software without specific\r
- prior written permission.\r
-\r
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
- IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS\r
- FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
- CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
- LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
- OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE\r
- SOFTWARE.\r
-**/\r
-\r
-\r
-#include "Llvm_int_lib.h"\r
-\r
-// Effects: if rem != 0, *rem = a % b\r
-// Returns: a / b\r
-\r
-// Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide\r
-\r
-UINT64\r
-__udivmoddi4 (UINT64 a, UINT64 b, UINT64* rem)\r
-{\r
- const unsigned n_uword_bits = sizeof(UINT32) * CHAR_BIT;\r
- const unsigned n_udword_bits = sizeof(UINT64) * CHAR_BIT;\r
- udwords n;\r
- n.all = a;\r
- udwords d;\r
- d.all = b;\r
- udwords q;\r
- udwords r;\r
- unsigned sr;\r
-\r
- if (b == 0) {\r
-// ASSERT (FALSE);\r
- return 0;\r
- }\r
-\r
- // special cases, X is unknown, K != 0\r
- if (n.high == 0)\r
- {\r
- if (d.high == 0)\r
- {\r
- // 0 X\r
- // ---\r
- // 0 X\r
- if (rem)\r
- *rem = n.low % d.low;\r
- return n.low / d.low;\r
- }\r
- // 0 X\r
- // ---\r
- // K X\r
- if (rem)\r
- *rem = n.low;\r
- return 0;\r
- }\r
- // n.high != 0\r
- if (d.low == 0)\r
- {\r
- if (d.high == 0)\r
- {\r
- // K X\r
- // ---\r
- // 0 0\r
- if (rem)\r
- *rem = n.high % d.low;\r
- return n.high / d.low;\r
- }\r
- // d.high != 0\r
- if (n.low == 0)\r
- {\r
- // K 0\r
- // ---\r
- // K 0\r
- if (rem)\r
- {\r
- r.high = n.high % d.high;\r
- r.low = 0;\r
- *rem = r.all;\r
- }\r
- return n.high / d.high;\r
- }\r
- // K K\r
- // ---\r
- // K 0\r
- if ((d.high & (d.high - 1)) == 0) // if d is a power of 2\r
- {\r
- if (rem)\r
- {\r
- r.low = n.low;\r
- r.high = n.high & (d.high - 1);\r
- *rem = r.all;\r
- }\r
- return n.high >> COUNT_TRAILING_ZEROS(d.high);\r
- }\r
- // K K\r
- // ---\r
- // K 0\r
- sr = COUNT_LEADING_ZEROS(d.high) - COUNT_LEADING_ZEROS(n.high);\r
- // 0 <= sr <= n_uword_bits - 2 or sr large\r
- if (sr > n_uword_bits - 2)\r
- {\r
- if (rem)\r
- *rem = n.all;\r
- return 0;\r
- }\r
- ++sr;\r
- // 1 <= sr <= n_uword_bits - 1\r
- // q.all = n.all << (n_udword_bits - sr);\r
- q.low = 0;\r
- q.high = n.low << (n_uword_bits - sr);\r
- // r.all = n.all >> sr;\r
- r.high = n.high >> sr;\r
- r.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr);\r
- }\r
- else // d.low != 0\r
- {\r
- if (d.high == 0)\r
- {\r
- // K X\r
- // ---\r
- // 0 K\r
- if ((d.low & (d.low - 1)) == 0) // if d is a power of 2\r
- {\r
- if (rem)\r
- *rem = n.low & (d.low - 1);\r
- if (d.low == 1)\r
- return n.all;\r
- unsigned sr = COUNT_TRAILING_ZEROS(d.low);\r
- q.high = n.high >> sr;\r
- q.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr);\r
- return q.all;\r
- }\r
- // K X\r
- // ---\r
- // 0 K\r
- sr = 1 + n_uword_bits + COUNT_LEADING_ZEROS(d.low) - COUNT_LEADING_ZEROS(n.high);\r
- // 2 <= sr <= n_udword_bits - 1\r
- // q.all = n.all << (n_udword_bits - sr);\r
- // r.all = n.all >> sr;\r
- // if (sr == n_uword_bits)\r
- // {\r
- // q.low = 0;\r
- // q.high = n.low;\r
- // r.high = 0;\r
- // r.low = n.high;\r
- // }\r
- // else if (sr < n_uword_bits) // 2 <= sr <= n_uword_bits - 1\r
- // {\r
- // q.low = 0;\r
- // q.high = n.low << (n_uword_bits - sr);\r
- // r.high = n.high >> sr;\r
- // r.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr);\r
- // }\r
- // else // n_uword_bits + 1 <= sr <= n_udword_bits - 1\r
- // {\r
- // q.low = n.low << (n_udword_bits - sr);\r
- // q.high = (n.high << (n_udword_bits - sr)) |\r
- // (n.low >> (sr - n_uword_bits));\r
- // r.high = 0;\r
- // r.low = n.high >> (sr - n_uword_bits);\r
- // }\r
- q.low = (n.low << (n_udword_bits - sr)) &\r
- ((INT32)(n_uword_bits - sr) >> (n_uword_bits-1));\r
- q.high = ((n.low << ( n_uword_bits - sr)) &\r
- ((INT32)(sr - n_uword_bits - 1) >> (n_uword_bits-1))) |\r
- (((n.high << (n_udword_bits - sr)) |\r
- (n.low >> (sr - n_uword_bits))) &\r
- ((INT32)(n_uword_bits - sr) >> (n_uword_bits-1)));\r
- r.high = (n.high >> sr) &\r
- ((INT32)(sr - n_uword_bits) >> (n_uword_bits-1));\r
- r.low = ((n.high >> (sr - n_uword_bits)) &\r
- ((INT32)(n_uword_bits - sr - 1) >> (n_uword_bits-1))) |\r
- (((n.high << (n_uword_bits - sr)) |\r
- (n.low >> sr)) &\r
- ((INT32)(sr - n_uword_bits) >> (n_uword_bits-1)));\r
- }\r
- else\r
- {\r
- // K X\r
- // ---\r
- // K K\r
- sr = COUNT_LEADING_ZEROS(d.high) - COUNT_LEADING_ZEROS(n.high);\r
- // 0 <= sr <= n_uword_bits - 1 or sr large\r
- if (sr > n_uword_bits - 1)\r
- {\r
- if (rem)\r
- *rem = n.all;\r
- return 0;\r
- }\r
- ++sr;\r
- // 1 <= sr <= n_uword_bits\r
- // q.all = n.all << (n_udword_bits - sr);\r
- q.low = 0;\r
- q.high = n.low << (n_uword_bits - sr);\r
- // r.all = n.all >> sr;\r
- // if (sr < n_uword_bits)\r
- // {\r
- // r.high = n.high >> sr;\r
- // r.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr);\r
- // }\r
- // else\r
- // {\r
- // r.high = 0;\r
- // r.low = n.high;\r
- // }\r
- r.high = (n.high >> sr) &\r
- ((INT32)(sr - n_uword_bits) >> (n_uword_bits-1));\r
- r.low = (n.high << (n_uword_bits - sr)) |\r
- ((n.low >> sr) &\r
- ((INT32)(sr - n_uword_bits) >> (n_uword_bits-1)));\r
- }\r
- }\r
- // Not a special case\r
- // q and r are initialized with:\r
- // q.all = n.all << (n_udword_bits - sr);\r
- // r.all = n.all >> sr;\r
- // 1 <= sr <= n_udword_bits - 1\r
- UINT32 carry = 0;\r
- for (; sr > 0; --sr)\r
- {\r
- // r:q = ((r:q) << 1) | carry\r
- r.high = (r.high << 1) | (r.low >> (n_uword_bits - 1));\r
- r.low = (r.low << 1) | (q.high >> (n_uword_bits - 1));\r
- q.high = (q.high << 1) | (q.low >> (n_uword_bits - 1));\r
- q.low = (q.low << 1) | carry;\r
- // carry = 0;\r
- // if (r.all >= d.all)\r
- // {\r
- // r.all -= d.all;\r
- // carry = 1;\r
- // }\r
- const INT64 s = (INT64)(d.all - r.all - 1) >> (n_udword_bits - 1);\r
- carry = s & 1;\r
- r.all -= d.all & s;\r
- }\r
- q.all = (q.all << 1) | carry;\r
- if (rem)\r
- *rem = r.all;\r
- return q.all;\r
-}\r