[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>

/**
 * int_sqrt - rough approximation to sqrt
 * @x: integer of which to calculate the sqrt
 *
 * A very rough approximation to the sqrt() function.
 */
unsigned long int_sqrt(unsigned long x)
{
	unsigned long b, m, y = 0;

	if (x <= 1)
		return x;

	m = 1UL << (BITS_PER_LONG - 2);
	while (m > x)
		m >>= 2;

	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>
1da177e4 LT	11
	12	/**
	13	* int_sqrt - rough approximation to sqrt
	14	* @x: integer of which to calculate the sqrt
	15	*
	16	* A very rough approximation to the sqrt() function.
	17	*/
	18	unsigned long int_sqrt(unsigned long x)
	19	{
30493cc9	20	unsigned long b, m, y = 0;
1da177e4	21
30493cc9 DB	22	if (x <= 1)
30493cc9 DB	23	return x;
1da177e4	24
30493cc9	25	m = 1UL << (BITS_PER_LONG - 2);
3f329570 PZ	26	while (m > x)
	27	m >>= 2;
	28
30493cc9 DB	29	while (m != 0) {
	30	b = y + m;
	31	y >>= 1;
1da177e4	32
30493cc9 DB	33	if (x >= b) {
	34	x -= b;
	35	y += m;
1da177e4	36	}
30493cc9	37	m >>= 2;
1da177e4	38	}
30493cc9 DB	39
30493cc9 DB	40	return y;
1da177e4 LT	41	}
1da177e4 LT	42	EXPORT_SYMBOL(int_sqrt);