blob: 62933c92c4fb0638101e09fcaf78045c8a07e1dd [file] [log] [blame]
Wolfgang Denk7b64fef2006-10-24 14:21:16 +02001/*
2 * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
3 *
4 * Based on former do_div() implementation from asm-parisc/div64.h:
5 * Copyright (C) 1999 Hewlett-Packard Co
6 * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
7 *
8 *
9 * Generic C version of 64bit/32bit division and modulo, with
10 * 64bit result and 32bit remainder.
11 *
12 * The fast case for (n>>32 == 0) is handled inline by do_div().
13 *
14 * Code generated for this function might be very inefficient
15 * for some CPUs. __div64_32() can be overridden by linking arch-specific
Peng Fan0342e332017-04-10 13:39:48 +080016 * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S
17 * or by defining a preprocessor macro in arch/include/asm/div64.h.
Wolfgang Denk7b64fef2006-10-24 14:21:16 +020018 */
19
Peng Fan0342e332017-04-10 13:39:48 +080020#include <linux/compat.h>
21#include <linux/kernel.h>
22#include <linux/math64.h>
Wolfgang Denk7b64fef2006-10-24 14:21:16 +020023
Peng Fan0342e332017-04-10 13:39:48 +080024/* Not needed on 64bit architectures */
25#if BITS_PER_LONG == 32
26
27#ifndef __div64_32
Simon Glassf611a462019-04-08 13:20:49 -060028/*
29 * Don't instrument this function as it may be called from tracing code, since
30 * it needs to read the timer and this often requires calling do_div(), which
31 * calls this function.
32 */
33uint32_t __attribute__((weak, no_instrument_function)) __div64_32(u64 *n,
34 u32 base)
Wolfgang Denk7b64fef2006-10-24 14:21:16 +020035{
Simon Glassca49b2c2019-04-08 13:20:48 -060036 u64 rem = *n;
37 u64 b = base;
38 u64 res, d = 1;
39 u32 high = rem >> 32;
Wolfgang Denk7b64fef2006-10-24 14:21:16 +020040
41 /* Reduce the thing a bit first */
42 res = 0;
43 if (high >= base) {
44 high /= base;
Simon Glassca49b2c2019-04-08 13:20:48 -060045 res = (u64)high << 32;
46 rem -= (u64)(high * base) << 32;
Wolfgang Denk7b64fef2006-10-24 14:21:16 +020047 }
48
49 while ((int64_t)b > 0 && b < rem) {
50 b = b+b;
51 d = d+d;
52 }
53
54 do {
55 if (rem >= b) {
56 rem -= b;
57 res += d;
58 }
59 b >>= 1;
60 d >>= 1;
61 } while (d);
62
63 *n = res;
64 return rem;
65}
Peng Fan0342e332017-04-10 13:39:48 +080066EXPORT_SYMBOL(__div64_32);
67#endif
68
69#ifndef div_s64_rem
70s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
71{
72 u64 quotient;
73
74 if (dividend < 0) {
75 quotient = div_u64_rem(-dividend, abs(divisor), (u32 *)remainder);
76 *remainder = -*remainder;
77 if (divisor > 0)
78 quotient = -quotient;
79 } else {
80 quotient = div_u64_rem(dividend, abs(divisor), (u32 *)remainder);
81 if (divisor < 0)
82 quotient = -quotient;
83 }
84 return quotient;
85}
86EXPORT_SYMBOL(div_s64_rem);
87#endif
88
89/**
90 * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder
91 * @dividend: 64bit dividend
92 * @divisor: 64bit divisor
93 * @remainder: 64bit remainder
94 *
95 * This implementation is a comparable to algorithm used by div64_u64.
96 * But this operation, which includes math for calculating the remainder,
97 * is kept distinct to avoid slowing down the div64_u64 operation on 32bit
98 * systems.
99 */
100#ifndef div64_u64_rem
101u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder)
102{
103 u32 high = divisor >> 32;
104 u64 quot;
105
106 if (high == 0) {
107 u32 rem32;
108 quot = div_u64_rem(dividend, divisor, &rem32);
109 *remainder = rem32;
110 } else {
111 int n = 1 + fls(high);
112 quot = div_u64(dividend >> n, divisor >> n);
113
114 if (quot != 0)
115 quot--;
116
117 *remainder = dividend - quot * divisor;
118 if (*remainder >= divisor) {
119 quot++;
120 *remainder -= divisor;
121 }
122 }
123
124 return quot;
125}
126EXPORT_SYMBOL(div64_u64_rem);
127#endif
128
129/**
130 * div64_u64 - unsigned 64bit divide with 64bit divisor
131 * @dividend: 64bit dividend
132 * @divisor: 64bit divisor
133 *
134 * This implementation is a modified version of the algorithm proposed
135 * by the book 'Hacker's Delight'. The original source and full proof
136 * can be found here and is available for use without restriction.
137 *
138 * 'http://www.hackersdelight.org/hdcodetxt/divDouble.c.txt'
139 */
140#ifndef div64_u64
141u64 div64_u64(u64 dividend, u64 divisor)
142{
143 u32 high = divisor >> 32;
144 u64 quot;
145
146 if (high == 0) {
147 quot = div_u64(dividend, divisor);
148 } else {
149 int n = 1 + fls(high);
150 quot = div_u64(dividend >> n, divisor >> n);
151
152 if (quot != 0)
153 quot--;
154 if ((dividend - quot * divisor) >= divisor)
155 quot++;
156 }
157
158 return quot;
159}
160EXPORT_SYMBOL(div64_u64);
161#endif
162
163/**
164 * div64_s64 - signed 64bit divide with 64bit divisor
165 * @dividend: 64bit dividend
166 * @divisor: 64bit divisor
167 */
168#ifndef div64_s64
169s64 div64_s64(s64 dividend, s64 divisor)
170{
171 s64 quot, t;
172
173 quot = div64_u64(abs(dividend), abs(divisor));
174 t = (dividend ^ divisor) >> 63;
175
176 return (quot ^ t) - t;
177}
178EXPORT_SYMBOL(div64_s64);
179#endif
180
181#endif /* BITS_PER_LONG == 32 */
182
183/*
184 * Iterative div/mod for use when dividend is not expected to be much
185 * bigger than divisor.
186 */
187u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder)
188{
189 return __iter_div_u64_rem(dividend, divisor, remainder);
190}
191EXPORT_SYMBOL(iter_div_u64_rem);