[linux.git] / lib / int_sqrt.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (C) 2013 Davidlohr Bueso <[email protected]>
 *
 *  Based on the shift-and-subtract algorithm for computing integer
 *  square root from Guy L. Steele.
 */

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