1 | *// SPDX-License-Identifier: GPL-2.0* |

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 | * */* |

8 | |

9 | __#include <linux/kernel.h>__ |

10 | __#include <linux/export.h>__ |

11 | __#include <linux/bitops.h>__ |

12 | |

13 | */*** |

14 | * * int_sqrt - computes the integer square root* |

15 | * * @x: integer of which to calculate the sqrt* |

16 | * ** |

17 | * * Computes: floor(sqrt(x))* |

18 | * */* |

19 | *unsigned* *long* int_sqrt(*unsigned* *long* x) |

20 | { |

21 | *unsigned* *long* b, m, y = `0`; |

22 | |

23 | **if** (x <= `1`) |

24 | **return** x; |

25 | |

26 | m = `1UL` << (__fls(x) & ~`1UL`); |

27 | **while** (m != `0`) { |

28 | b = y + m; |

29 | y >>= `1`; |

30 | |

31 | **if** (x >= b) { |

32 | x -= b; |

33 | y += m; |

34 | } |

35 | m >>= `2`; |

36 | } |

37 | |

38 | **return** y; |

39 | } |

40 | EXPORT_SYMBOL(int_sqrt); |

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

55 | m = `1ULL` << ((fls64(x) - `1`) & ~`1ULL`); |

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

71 | |