[deliverable/linux.git] / drivers / acpi / utilities / utmath.c

/*******************************************************************************
 *
 * Module Name: utmath - Integer math support routines
 *
 ******************************************************************************/

/*
 * Copyright (C) 2000 - 2008, Intel Corp.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions, and the following disclaimer,
 *    without modification.
 * 2. Redistributions in binary form must reproduce at minimum a disclaimer
 *    substantially similar to the "NO WARRANTY" disclaimer below
 *    ("Disclaimer") and any redistribution must be conditioned upon
 *    including a substantially similar Disclaimer requirement for further
 *    binary redistribution.
 * 3. Neither the names of the above-listed copyright holders nor the names
 *    of any contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
 *
 * Alternatively, this software may be distributed under the terms of the
 * GNU General Public License ("GPL") version 2 as published by the Free
 * Software Foundation.
 *
 * NO WARRANTY
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGES.
 */

#include <acpi/acpi.h>

#define _COMPONENT          ACPI_UTILITIES
ACPI_MODULE_NAME("utmath")

/*
 * Support for double-precision integer divide.  This code is included here
 * in order to support kernel environments where the double-precision math
 * library is not available.
 */
#ifndef ACPI_USE_NATIVE_DIVIDE
/*******************************************************************************
 *
 * FUNCTION:    acpi_ut_short_divide
 *
 * PARAMETERS:  Dividend            - 64-bit dividend
 *              Divisor             - 32-bit divisor
 *              out_quotient        - Pointer to where the quotient is returned
 *              out_remainder       - Pointer to where the remainder is returned
 *
 * RETURN:      Status (Checks for divide-by-zero)
 *
 * DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits)
 *              divide and modulo.  The result is a 64-bit quotient and a
 *              32-bit remainder.
 *
 ******************************************************************************/
acpi_status
acpi_ut_short_divide(acpi_integer dividend,
		     u32 divisor,
		     acpi_integer * out_quotient, u32 * out_remainder)
{
	union uint64_overlay dividend_ovl;
	union uint64_overlay quotient;
	u32 remainder32;

	ACPI_FUNCTION_TRACE(ut_short_divide);

	/* Always check for a zero divisor */

	if (divisor == 0) {
		ACPI_ERROR((AE_INFO, "Divide by zero"));
		return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
	}

	dividend_ovl.full = dividend;

	/*
	 * The quotient is 64 bits, the remainder is always 32 bits,
	 * and is generated by the second divide.
	 */
	ACPI_DIV_64_BY_32(0, dividend_ovl.part.hi, divisor,
			  quotient.part.hi, remainder32);
	ACPI_DIV_64_BY_32(remainder32, dividend_ovl.part.lo, divisor,
			  quotient.part.lo, remainder32);

	/* Return only what was requested */

	if (out_quotient) {
		*out_quotient = quotient.full;
	}
	if (out_remainder) {
		*out_remainder = remainder32;
	}

	return_ACPI_STATUS(AE_OK);
}

/*******************************************************************************
 *
 * FUNCTION:    acpi_ut_divide
 *
 * PARAMETERS:  in_dividend         - Dividend
 *              in_divisor          - Divisor
 *              out_quotient        - Pointer to where the quotient is returned
 *              out_remainder       - Pointer to where the remainder is returned
 *
 * RETURN:      Status (Checks for divide-by-zero)
 *
 * DESCRIPTION: Perform a divide and modulo.
 *
 ******************************************************************************/

acpi_status
acpi_ut_divide(acpi_integer in_dividend,
	       acpi_integer in_divisor,
	       acpi_integer * out_quotient, acpi_integer * out_remainder)
{
	union uint64_overlay dividend;
	union uint64_overlay divisor;
	union uint64_overlay quotient;
	union uint64_overlay remainder;
	union uint64_overlay normalized_dividend;
	union uint64_overlay normalized_divisor;
	u32 partial1;
	union uint64_overlay partial2;
	union uint64_overlay partial3;

	ACPI_FUNCTION_TRACE(ut_divide);

	/* Always check for a zero divisor */

	if (in_divisor == 0) {
		ACPI_ERROR((AE_INFO, "Divide by zero"));
		return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
	}

	divisor.full = in_divisor;
	dividend.full = in_dividend;
	if (divisor.part.hi == 0) {
		/*
		 * 1) Simplest case is where the divisor is 32 bits, we can
		 * just do two divides
		 */
		remainder.part.hi = 0;

		/*
		 * The quotient is 64 bits, the remainder is always 32 bits,
		 * and is generated by the second divide.
		 */
		ACPI_DIV_64_BY_32(0, dividend.part.hi, divisor.part.lo,
				  quotient.part.hi, partial1);
		ACPI_DIV_64_BY_32(partial1, dividend.part.lo, divisor.part.lo,
				  quotient.part.lo, remainder.part.lo);
	}

	else {
		/*
		 * 2) The general case where the divisor is a full 64 bits
		 * is more difficult
		 */
		quotient.part.hi = 0;
		normalized_dividend = dividend;
		normalized_divisor = divisor;

		/* Normalize the operands (shift until the divisor is < 32 bits) */

		do {
			ACPI_SHIFT_RIGHT_64(normalized_divisor.part.hi,
					    normalized_divisor.part.lo);
			ACPI_SHIFT_RIGHT_64(normalized_dividend.part.hi,
					    normalized_dividend.part.lo);

		} while (normalized_divisor.part.hi != 0);

		/* Partial divide */

		ACPI_DIV_64_BY_32(normalized_dividend.part.hi,
				  normalized_dividend.part.lo,
				  normalized_divisor.part.lo,
				  quotient.part.lo, partial1);

		/*
		 * The quotient is always 32 bits, and simply requires adjustment.
		 * The 64-bit remainder must be generated.
		 */
		partial1 = quotient.part.lo * divisor.part.hi;
		partial2.full =
		    (acpi_integer) quotient.part.lo * divisor.part.lo;
		partial3.full = (acpi_integer) partial2.part.hi + partial1;

		remainder.part.hi = partial3.part.lo;
		remainder.part.lo = partial2.part.lo;

		if (partial3.part.hi == 0) {
			if (partial3.part.lo >= dividend.part.hi) {
				if (partial3.part.lo == dividend.part.hi) {
					if (partial2.part.lo > dividend.part.lo) {
						quotient.part.lo--;
						remainder.full -= divisor.full;
					}
				} else {
					quotient.part.lo--;
					remainder.full -= divisor.full;
				}
			}

			remainder.full = remainder.full - dividend.full;
			remainder.part.hi = (u32) - ((s32) remainder.part.hi);
			remainder.part.lo = (u32) - ((s32) remainder.part.lo);

			if (remainder.part.lo) {
				remainder.part.hi--;
			}
		}
	}

	/* Return only what was requested */

	if (out_quotient) {
		*out_quotient = quotient.full;
	}
	if (out_remainder) {
		*out_remainder = remainder.full;
	}

	return_ACPI_STATUS(AE_OK);
}

#else
/*******************************************************************************
 *
 * FUNCTION:    acpi_ut_short_divide, acpi_ut_divide
 *
 * PARAMETERS:  See function headers above
 *
 * DESCRIPTION: Native versions of the ut_divide functions. Use these if either
 *              1) The target is a 64-bit platform and therefore 64-bit
 *                 integer math is supported directly by the machine.
 *              2) The target is a 32-bit or 16-bit platform, and the
 *                 double-precision integer math library is available to
 *                 perform the divide.
 *
 ******************************************************************************/
acpi_status
acpi_ut_short_divide(acpi_integer in_dividend,
		     u32 divisor,
		     acpi_integer * out_quotient, u32 * out_remainder)
{

	ACPI_FUNCTION_TRACE(ut_short_divide);

	/* Always check for a zero divisor */

	if (divisor == 0) {
		ACPI_ERROR((AE_INFO, "Divide by zero"));
		return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
	}

	/* Return only what was requested */

	if (out_quotient) {
		*out_quotient = in_dividend / divisor;
	}
	if (out_remainder) {
		*out_remainder = (u32) (in_dividend % divisor);
	}

	return_ACPI_STATUS(AE_OK);
}

acpi_status
acpi_ut_divide(acpi_integer in_dividend,
	       acpi_integer in_divisor,
	       acpi_integer * out_quotient, acpi_integer * out_remainder)
{
	ACPI_FUNCTION_TRACE(ut_divide);

	/* Always check for a zero divisor */

	if (in_divisor == 0) {
		ACPI_ERROR((AE_INFO, "Divide by zero"));
		return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
	}

	/* Return only what was requested */

	if (out_quotient) {
		*out_quotient = in_dividend / in_divisor;
	}
	if (out_remainder) {
		*out_remainder = in_dividend % in_divisor;
	}

	return_ACPI_STATUS(AE_OK);
}

#endif
Commit	Line	Data
1da177e4 LT	1	/*******************************************************************************
	2	*
	3	* Module Name: utmath - Integer math support routines
	4	*
	5	******************************************************************************/
	6
	7	/*
75a44ce0	8	* Copyright (C) 2000 - 2008, Intel Corp.
1da177e4 LT	9	* All rights reserved.
	10	*
	11	* Redistribution and use in source and binary forms, with or without
	12	* modification, are permitted provided that the following conditions
	13	* are met:
	14	* 1. Redistributions of source code must retain the above copyright
	15	* notice, this list of conditions, and the following disclaimer,
	16	* without modification.
	17	* 2. Redistributions in binary form must reproduce at minimum a disclaimer
	18	* substantially similar to the "NO WARRANTY" disclaimer below
	19	* ("Disclaimer") and any redistribution must be conditioned upon
	20	* including a substantially similar Disclaimer requirement for further
	21	* binary redistribution.
	22	* 3. Neither the names of the above-listed copyright holders nor the names
	23	* of any contributors may be used to endorse or promote products derived
	24	* from this software without specific prior written permission.
	25	*
	26	* Alternatively, this software may be distributed under the terms of the
	27	* GNU General Public License ("GPL") version 2 as published by the Free
	28	* Software Foundation.
	29	*
	30	* NO WARRANTY
	31	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	32	* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	33	* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
	34	* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	35	* HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	36	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	37	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	38	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
	39	* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
	40	* IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
	41	* POSSIBILITY OF SUCH DAMAGES.
	42	*/
	43
1da177e4 LT	44	#include <acpi/acpi.h>
1da177e4 LT	45
1da177e4	46	#define _COMPONENT ACPI_UTILITIES
4be44fcd	47	ACPI_MODULE_NAME("utmath")
1da177e4 LT	48
	49	/*
	50	* Support for double-precision integer divide. This code is included here
	51	* in order to support kernel environments where the double-precision math
	52	* library is not available.
	53	*/
1da177e4 LT	54	#ifndef ACPI_USE_NATIVE_DIVIDE
	55	/*******************************************************************************
	56	*
	57	* FUNCTION: acpi_ut_short_divide
	58	*
	59	* PARAMETERS: Dividend - 64-bit dividend
	60	* Divisor - 32-bit divisor
	61	* out_quotient - Pointer to where the quotient is returned
	62	* out_remainder - Pointer to where the remainder is returned
	63	*
	64	* RETURN: Status (Checks for divide-by-zero)
	65	*
	66	* DESCRIPTION: Perform a short (maximum 64 bits divided by 32 bits)
	67	* divide and modulo. The result is a 64-bit quotient and a
	68	* 32-bit remainder.
	69	*
	70	******************************************************************************/
1da177e4	71	acpi_status
4be44fcd LB	72	acpi_ut_short_divide(acpi_integer dividend,
	73	u32 divisor,
	74	acpi_integer * out_quotient, u32 * out_remainder)
1da177e4	75	{
4be44fcd LB	76	union uint64_overlay dividend_ovl;
	77	union uint64_overlay quotient;
	78	u32 remainder32;
1da177e4	79
b229cf92	80	ACPI_FUNCTION_TRACE(ut_short_divide);
1da177e4 LT	81
	82	/* Always check for a zero divisor */
	83
	84	if (divisor == 0) {
b8e4d893	85	ACPI_ERROR((AE_INFO, "Divide by zero"));
4be44fcd	86	return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
1da177e4 LT	87	}
	88
	89	dividend_ovl.full = dividend;
	90
	91	/*
	92	* The quotient is 64 bits, the remainder is always 32 bits,
	93	* and is generated by the second divide.
	94	*/
4be44fcd	95	ACPI_DIV_64_BY_32(0, dividend_ovl.part.hi, divisor,
1da177e4	96	quotient.part.hi, remainder32);
4be44fcd	97	ACPI_DIV_64_BY_32(remainder32, dividend_ovl.part.lo, divisor,
1da177e4 LT	98	quotient.part.lo, remainder32);
	99
	100	/* Return only what was requested */
	101
	102	if (out_quotient) {
	103	*out_quotient = quotient.full;
	104	}
	105	if (out_remainder) {
	106	*out_remainder = remainder32;
	107	}
	108
4be44fcd	109	return_ACPI_STATUS(AE_OK);
1da177e4 LT	110	}
1da177e4 LT	111
1da177e4 LT	112	/*******************************************************************************
	113	*
	114	* FUNCTION: acpi_ut_divide
	115	*
	116	* PARAMETERS: in_dividend - Dividend
	117	* in_divisor - Divisor
	118	* out_quotient - Pointer to where the quotient is returned
	119	* out_remainder - Pointer to where the remainder is returned
	120	*
	121	* RETURN: Status (Checks for divide-by-zero)
	122	*
	123	* DESCRIPTION: Perform a divide and modulo.
	124	*
	125	******************************************************************************/
	126
	127	acpi_status
4be44fcd LB	128	acpi_ut_divide(acpi_integer in_dividend,
	129	acpi_integer in_divisor,
	130	acpi_integer * out_quotient, acpi_integer * out_remainder)
1da177e4	131	{
4be44fcd LB	132	union uint64_overlay dividend;
	133	union uint64_overlay divisor;
	134	union uint64_overlay quotient;
	135	union uint64_overlay remainder;
	136	union uint64_overlay normalized_dividend;
	137	union uint64_overlay normalized_divisor;
	138	u32 partial1;
	139	union uint64_overlay partial2;
	140	union uint64_overlay partial3;
	141
b229cf92	142	ACPI_FUNCTION_TRACE(ut_divide);
1da177e4 LT	143
	144	/* Always check for a zero divisor */
	145
	146	if (in_divisor == 0) {
b8e4d893	147	ACPI_ERROR((AE_INFO, "Divide by zero"));
4be44fcd	148	return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
1da177e4 LT	149	}
1da177e4 LT	150
4be44fcd	151	divisor.full = in_divisor;
1da177e4 LT	152	dividend.full = in_dividend;
	153	if (divisor.part.hi == 0) {
	154	/*
	155	* 1) Simplest case is where the divisor is 32 bits, we can
	156	* just do two divides
	157	*/
	158	remainder.part.hi = 0;
	159
	160	/*
	161	* The quotient is 64 bits, the remainder is always 32 bits,
	162	* and is generated by the second divide.
	163	*/
4be44fcd	164	ACPI_DIV_64_BY_32(0, dividend.part.hi, divisor.part.lo,
1da177e4	165	quotient.part.hi, partial1);
4be44fcd	166	ACPI_DIV_64_BY_32(partial1, dividend.part.lo, divisor.part.lo,
1da177e4 LT	167	quotient.part.lo, remainder.part.lo);
	168	}
	169
	170	else {
	171	/*
	172	* 2) The general case where the divisor is a full 64 bits
	173	* is more difficult
	174	*/
4be44fcd	175	quotient.part.hi = 0;
1da177e4 LT	176	normalized_dividend = dividend;
	177	normalized_divisor = divisor;
	178
	179	/* Normalize the operands (shift until the divisor is < 32 bits) */
	180
	181	do {
4be44fcd LB	182	ACPI_SHIFT_RIGHT_64(normalized_divisor.part.hi,
	183	normalized_divisor.part.lo);
	184	ACPI_SHIFT_RIGHT_64(normalized_dividend.part.hi,
	185	normalized_dividend.part.lo);
1da177e4 LT	186
	187	} while (normalized_divisor.part.hi != 0);
	188
	189	/* Partial divide */
	190
4be44fcd	191	ACPI_DIV_64_BY_32(normalized_dividend.part.hi,
1da177e4 LT	192	normalized_dividend.part.lo,
	193	normalized_divisor.part.lo,
	194	quotient.part.lo, partial1);
	195
	196	/*
	197	* The quotient is always 32 bits, and simply requires adjustment.
	198	* The 64-bit remainder must be generated.
	199	*/
4be44fcd LB	200	partial1 = quotient.part.lo * divisor.part.hi;
	201	partial2.full =
	202	(acpi_integer) quotient.part.lo * divisor.part.lo;
1da177e4 LT	203	partial3.full = (acpi_integer) partial2.part.hi + partial1;
	204
	205	remainder.part.hi = partial3.part.lo;
	206	remainder.part.lo = partial2.part.lo;
	207
	208	if (partial3.part.hi == 0) {
	209	if (partial3.part.lo >= dividend.part.hi) {
	210	if (partial3.part.lo == dividend.part.hi) {
	211	if (partial2.part.lo > dividend.part.lo) {
	212	quotient.part.lo--;
	213	remainder.full -= divisor.full;
	214	}
4be44fcd	215	} else {
1da177e4 LT	216	quotient.part.lo--;
	217	remainder.full -= divisor.full;
	218	}
	219	}
	220
4be44fcd LB	221	remainder.full = remainder.full - dividend.full;
	222	remainder.part.hi = (u32) - ((s32) remainder.part.hi);
	223	remainder.part.lo = (u32) - ((s32) remainder.part.lo);
1da177e4 LT	224
	225	if (remainder.part.lo) {
	226	remainder.part.hi--;
	227	}
	228	}
	229	}
	230
	231	/* Return only what was requested */
	232
	233	if (out_quotient) {
	234	*out_quotient = quotient.full;
	235	}
	236	if (out_remainder) {
	237	*out_remainder = remainder.full;
	238	}
	239
4be44fcd	240	return_ACPI_STATUS(AE_OK);
1da177e4 LT	241	}
	242
	243	#else
1da177e4 LT	244	/*******************************************************************************
	245	*
	246	* FUNCTION: acpi_ut_short_divide, acpi_ut_divide
	247	*
44f6c012 RM	248	* PARAMETERS: See function headers above
44f6c012 RM	249	*
1da177e4 LT	250	* DESCRIPTION: Native versions of the ut_divide functions. Use these if either
	251	* 1) The target is a 64-bit platform and therefore 64-bit
	252	* integer math is supported directly by the machine.
	253	* 2) The target is a 32-bit or 16-bit platform, and the
	254	* double-precision integer math library is available to
	255	* perform the divide.
	256	*
	257	******************************************************************************/
1da177e4	258	acpi_status
4be44fcd LB	259	acpi_ut_short_divide(acpi_integer in_dividend,
	260	u32 divisor,
	261	acpi_integer * out_quotient, u32 * out_remainder)
1da177e4 LT	262	{
1da177e4 LT	263
b229cf92	264	ACPI_FUNCTION_TRACE(ut_short_divide);
1da177e4 LT	265
	266	/* Always check for a zero divisor */
	267
	268	if (divisor == 0) {
b8e4d893	269	ACPI_ERROR((AE_INFO, "Divide by zero"));
4be44fcd	270	return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
1da177e4 LT	271	}
	272
	273	/* Return only what was requested */
	274
	275	if (out_quotient) {
	276	*out_quotient = in_dividend / divisor;
	277	}
	278	if (out_remainder) {
1f549a24	279	*out_remainder = (u32) (in_dividend % divisor);
1da177e4 LT	280	}
1da177e4 LT	281
4be44fcd	282	return_ACPI_STATUS(AE_OK);
1da177e4 LT	283	}
	284
	285	acpi_status
4be44fcd LB	286	acpi_ut_divide(acpi_integer in_dividend,
	287	acpi_integer in_divisor,
	288	acpi_integer * out_quotient, acpi_integer * out_remainder)
1da177e4	289	{
b229cf92	290	ACPI_FUNCTION_TRACE(ut_divide);
1da177e4 LT	291
	292	/* Always check for a zero divisor */
	293
	294	if (in_divisor == 0) {
b8e4d893	295	ACPI_ERROR((AE_INFO, "Divide by zero"));
4be44fcd	296	return_ACPI_STATUS(AE_AML_DIVIDE_BY_ZERO);
1da177e4 LT	297	}
1da177e4 LT	298
1da177e4 LT	299	/* Return only what was requested */
	300
	301	if (out_quotient) {
	302	*out_quotient = in_dividend / in_divisor;
	303	}
	304	if (out_remainder) {
	305	*out_remainder = in_dividend % in_divisor;
	306	}
	307
4be44fcd	308	return_ACPI_STATUS(AE_OK);
1da177e4 LT	309	}
	310
	311	#endif