2N/A * The contents of this file are subject to the terms of the 2N/A * Common Development and Distribution License (the "License"). 2N/A * You may not use this file except in compliance with the License. 2N/A * See the License for the specific language governing permissions 2N/A * and limitations under the License. 2N/A * When distributing Covered Code, include this CDDL HEADER in each 2N/A * If applicable, add the following below this CDDL HEADER, with the 2N/A * fields enclosed by brackets "[]" replaced with your own identifying 2N/A * information: Portions Copyright [yyyy] [name of copyright owner] 2N/A * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 2N/A * Use is subject to license terms. 2N/A * C support for 64-bit modulo and division. 2N/A * Hand-customized compiler output - see comments for details. 2N/A * Hand-customized compiler output: the non-GCC entry points depart from 2N/A * the SYS V ABI by requiring their arguments to be popped, and in the 2N/A * [u]divrem64 cases returning the remainder in %ecx:%esi. Note the 2N/A * compiler-generated use of %edx:%eax for the first argument of 2N/A * internal entry points. 2N/A * Inlines for speed: 2N/A * - counting the number of leading zeros in a word 2N/A * - multiplying two 32-bit numbers giving a 64-bit result 2N/A * - dividing a 64-bit number by a 32-bit number, giving both quotient 2N/A * - subtracting two 64-bit results 2N/A/
/* give index of highest bit */ 2N/A/
/* multiply two uint32_ts resulting in a uint64_t */ 2N/A/
/* divide a uint64_t by a uint32_t */ 2N/A/
/* subtract two uint64_ts (with borrow) */ 2N/A/
asm(
"subl %4,%0\n\tsbbl %5,%1" \
2N/A/ * Unsigned division with remainder. 2N/A/ * Divide two uint64_ts, and calculate remainder. 2N/A/
/* simple cases: y is a single uint32_t */ 2N/A/
/* result is a single uint32_t, use one division */ 2N/A/
/* result is a double uint32_t, use two divisions */ 2N/A/
/* calculate q0 and remainder */ 2N/A/
/* return remainder */ 2N/A/
/* return result */ 2N/A/
/* HI(x) < HI(y) => x < y => result is 0 */ 2N/A/
/* return remainder */ 2N/A/
/* return result */ 2N/A/ * uint64_t by uint64_t division, resulting in a one-uint32_t 2N/A/
/* normalize by shifting x and y so MSB(y) == 1 */ 2N/A/
/* no shifting needed, and x < 2*y so q <= 1 */ 2N/A/
/* if x >= y then q = 1 (note x1 >= y1) */ 2N/A/
/* subtract y from x to get remainder */ 2N/A/
/* return remainder */ 2N/A/
/* return result */ 2N/A/ * the last case: result is one uint32_t, but we need to 2N/A/
/* normalize x (we need 3 uint32_ts!!!) */ 2N/A/
/* estimate q0, and reduce x to a two uint32_t value */ 2N/A/
/* adjust q0 down if too high */ 2N/A/ * because of the limited range of x2 we can only be 2N/A/
/* return remainder */ 2N/A/
/* subtract product from x to get remainder */ 2N/A/
/* return result */ 2N/A * Unsigned division without remainder. 2N/A/
/* simple cases: y is a single uint32_t */ 2N/A/
/* result is a single uint32_t, use one division */ 2N/A/
/* result is a double uint32_t, use two divisions */ 2N/A/
/* calculate q0 and remainder */ 2N/A/
/* return result */ 2N/A/
/* HI(x) < HI(y) => x < y => result is 0 */ 2N/A/
/* return result */ 2N/A/ * uint64_t by uint64_t division, resulting in a one-uint32_t 2N/A/
/* normalize by shifting x and y so MSB(y) == 1 */ 2N/A/
/* no shifting needed, and x < 2*y so q <= 1 */ 2N/A/
/* if x >= y then q = 1 (note x1 >= y1) */ 2N/A/
/* subtract y from x to get remainder */ 2N/A/
/* A_SUB2(y0, y1, x0, x1); */ 2N/A/
/* return result */ 2N/A/ * the last case: result is one uint32_t, but we need to 2N/A/
/* normalize x (we need 3 uint32_ts!!!) */ 2N/A/
/* estimate q0, and reduce x to a two uint32_t value */ 2N/A/
/* adjust q0 down if too high */ 2N/A/ * because of the limited range of x2 we can only be 2N/A/
/* return result */ 2N/A * Perform division of two unsigned 64-bit quantities, returning the 2N/A * quotient in %edx:%eax. __udiv64 pops the arguments on return, 2N/A * Perform division of two unsigned 64-bit quantities, returning the 2N/A * remainder in %edx:%eax. __urem64 pops the arguments on return 2N/A * Perform division of two signed 64-bit quantities, returning the 2N/A * quotient in %edx:%eax. __div64 pops the arguments on return. 2N/A * Perform division of two signed 64-bit quantities, returning the 2N/A * remainder in %edx:%eax. __rem64 pops the arguments on return. 2N/A * Perform division of two unsigned 64-bit quantities, returning the 2N/A * quotient in %edx:%eax, and the remainder in %ecx:%esi. __udivrem64 2N/A * pops the arguments on return. 2N/A * Signed division with remainder. 2N/A * Perform division of two signed 64-bit quantities, returning the 2N/A * quotient in %edx:%eax, and the remainder in %ecx:%esi. __divrem64 2N/A * pops the arguments on return.