[mirror_ubuntu-bionic-kernel.git] / lib / 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/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);
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 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);