mirror of
git://git.kernel.org/pub/scm/linux/kernel/git/xiang/erofs.git
synced 2026-10-30 05:42:46 +01:00
Andy Shevchenko
aa6159ab99
kernel.h is being used as a dump for all kinds of stuff for a long time. Here is the attempt to start cleaning it up by splitting out mathematical helpers. At the same time convert users in header and lib folder to use new header. Though for time being include new header back to kernel.h to avoid twisted indirected includes for existing users. [[email protected]: fix powerpc build] Link: https://lkml.kernel.org/r/[email protected] Link: https://lkml.kernel.org/r/[email protected] Signed-off-by: Andy Shevchenko <[email protected]> Cc: "Paul E. McKenney" <[email protected]> Cc: Trond Myklebust <[email protected]> Cc: Jeff Layton <[email protected]> Cc: Rasmus Villemoes <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
72 lines
1.2 KiB
C
72 lines
1.2 KiB
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/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
|