[linux-2.6-block.git] / lib / math / int_sqrt.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (C) 2013 Davidlohr Bueso <davidlohr.bueso@hp.com>
 *
 *  Based on the shift-and-subtract algorithm for computing integer
 *  square root from Guy L. Steele.
 */

#include <linux/export.h>
#include <linux/bitops.h>
#include <linux/limits.h>
#include <linux/math.h>

/**
 * int_sqrt - computes the integer square root
 * @x: integer of which to calculate the sqrt
 *
 * Computes: floor(sqrt(x))
 */
unsigned long int_sqrt(unsigned long x)
{
	unsigned long b, m, y = 0;

	if (x <= 1)
		return x;

	m = 1UL << (__fls(x) & ~1UL);
	while (m != 0) {
		b = y + m;
		y >>= 1;

		if (x >= b) {
			x -= b;
			y += m;
		}
		m >>= 2;
	}

	return y;
}
EXPORT_SYMBOL(int_sqrt);

#if BITS_PER_LONG < 64
/**
 * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input
 * is expected.
 * @x: 64bit integer of which to calculate the sqrt
 */
u32 int_sqrt64(u64 x)
{
	u64 b, m, y = 0;

	if (x <= ULONG_MAX)
		return int_sqrt((unsigned long) x);

	m = 1ULL << ((fls64(x) - 1) & ~1ULL);
	while (m != 0) {
		b = y + m;
		y >>= 1;

		if (x >= b) {
			x -= b;
			y += m;
		}
		m >>= 2;
	}

	return y;
}
EXPORT_SYMBOL(int_sqrt64);
#endif
Commit	Line	Data
b2441318	1	// SPDX-License-Identifier: GPL-2.0
30493cc9 DB	2	/*
	3	* Copyright (C) 2013 Davidlohr Bueso <davidlohr.bueso@hp.com>
	4	*
	5	* Based on the shift-and-subtract algorithm for computing integer
	6	* square root from Guy L. Steele.
	7	*/
1da177e4	8
8bc3bcc9	9	#include <linux/export.h>
f8ae107e	10	#include <linux/bitops.h>
aa6159ab AS	11	#include <linux/limits.h>
aa6159ab AS	12	#include <linux/math.h>
1da177e4 LT	13
1da177e4 LT	14	/**
e813a614	15	* int_sqrt - computes the integer square root
1da177e4 LT	16	* @x: integer of which to calculate the sqrt
1da177e4 LT	17	*
e813a614	18	* Computes: floor(sqrt(x))
1da177e4 LT	19	*/
	20	unsigned long int_sqrt(unsigned long x)
	21	{
30493cc9	22	unsigned long b, m, y = 0;
1da177e4	23
30493cc9 DB	24	if (x <= 1)
30493cc9 DB	25	return x;
1da177e4	26
f8ae107e	27	m = 1UL << (__fls(x) & ~1UL);
30493cc9 DB	28	while (m != 0) {
	29	b = y + m;
	30	y >>= 1;
1da177e4	31
30493cc9 DB	32	if (x >= b) {
	33	x -= b;
	34	y += m;
1da177e4	35	}
30493cc9	36	m >>= 2;
1da177e4	37	}
30493cc9 DB	38
30493cc9 DB	39	return y;
1da177e4 LT	40	}
1da177e4 LT	41	EXPORT_SYMBOL(int_sqrt);
47a36163 CM	42
	43	#if BITS_PER_LONG < 64
	44	/**
	45	* int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input
	46	* is expected.
	47	* @x: 64bit integer of which to calculate the sqrt
	48	*/
	49	u32 int_sqrt64(u64 x)
	50	{
	51	u64 b, m, y = 0;
	52
	53	if (x <= ULONG_MAX)
	54	return int_sqrt((unsigned long) x);
	55
fbfaf851	56	m = 1ULL << ((fls64(x) - 1) & ~1ULL);
47a36163 CM	57	while (m != 0) {
	58	b = y + m;
	59	y >>= 1;
	60
	61	if (x >= b) {
	62	x -= b;
	63	y += m;
	64	}
	65	m >>= 2;
	66	}
	67
	68	return y;
	69	}
	70	EXPORT_SYMBOL(int_sqrt64);
	71	#endif