blob: 7f63175d3e56917d26cc0da4c2ff3eb9d2b0cb41 [file] [log] [blame]
Zack Williamse940c7a2019-08-21 14:25:39 -07001/*
2Copyright 2014 The Kubernetes Authors.
3
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15*/
16
17package resource
18
19import (
20 "math/big"
21
22 inf "gopkg.in/inf.v0"
23)
24
25const (
26 // maxInt64Factors is the highest value that will be checked when removing factors of 10 from an int64.
27 // It is also the maximum decimal digits that can be represented with an int64.
28 maxInt64Factors = 18
29)
30
31var (
32 // Commonly needed big.Int values-- treat as read only!
33 bigTen = big.NewInt(10)
34 bigZero = big.NewInt(0)
35 bigOne = big.NewInt(1)
36 bigThousand = big.NewInt(1000)
37 big1024 = big.NewInt(1024)
38
39 // Commonly needed inf.Dec values-- treat as read only!
40 decZero = inf.NewDec(0, 0)
41 decOne = inf.NewDec(1, 0)
42 decMinusOne = inf.NewDec(-1, 0)
43 decThousand = inf.NewDec(1000, 0)
44 dec1024 = inf.NewDec(1024, 0)
45 decMinus1024 = inf.NewDec(-1024, 0)
46
47 // Largest (in magnitude) number allowed.
48 maxAllowed = infDecAmount{inf.NewDec((1<<63)-1, 0)} // == max int64
49
50 // The maximum value we can represent milli-units for.
51 // Compare with the return value of Quantity.Value() to
52 // see if it's safe to use Quantity.MilliValue().
53 MaxMilliValue = int64(((1 << 63) - 1) / 1000)
54)
55
56const mostNegative = -(mostPositive + 1)
57const mostPositive = 1<<63 - 1
58
59// int64Add returns a+b, or false if that would overflow int64.
60func int64Add(a, b int64) (int64, bool) {
61 c := a + b
62 switch {
63 case a > 0 && b > 0:
64 if c < 0 {
65 return 0, false
66 }
67 case a < 0 && b < 0:
68 if c > 0 {
69 return 0, false
70 }
71 if a == mostNegative && b == mostNegative {
72 return 0, false
73 }
74 }
75 return c, true
76}
77
78// int64Multiply returns a*b, or false if that would overflow or underflow int64.
79func int64Multiply(a, b int64) (int64, bool) {
80 if a == 0 || b == 0 || a == 1 || b == 1 {
81 return a * b, true
82 }
83 if a == mostNegative || b == mostNegative {
84 return 0, false
85 }
86 c := a * b
87 return c, c/b == a
88}
89
90// int64MultiplyScale returns a*b, assuming b is greater than one, or false if that would overflow or underflow int64.
91// Use when b is known to be greater than one.
92func int64MultiplyScale(a int64, b int64) (int64, bool) {
93 if a == 0 || a == 1 {
94 return a * b, true
95 }
96 if a == mostNegative && b != 1 {
97 return 0, false
98 }
99 c := a * b
100 return c, c/b == a
101}
102
103// int64MultiplyScale10 multiplies a by 10, or returns false if that would overflow. This method is faster than
104// int64Multiply(a, 10) because the compiler can optimize constant factor multiplication.
105func int64MultiplyScale10(a int64) (int64, bool) {
106 if a == 0 || a == 1 {
107 return a * 10, true
108 }
109 if a == mostNegative {
110 return 0, false
111 }
112 c := a * 10
113 return c, c/10 == a
114}
115
116// int64MultiplyScale100 multiplies a by 100, or returns false if that would overflow. This method is faster than
117// int64Multiply(a, 100) because the compiler can optimize constant factor multiplication.
118func int64MultiplyScale100(a int64) (int64, bool) {
119 if a == 0 || a == 1 {
120 return a * 100, true
121 }
122 if a == mostNegative {
123 return 0, false
124 }
125 c := a * 100
126 return c, c/100 == a
127}
128
129// int64MultiplyScale1000 multiplies a by 1000, or returns false if that would overflow. This method is faster than
130// int64Multiply(a, 1000) because the compiler can optimize constant factor multiplication.
131func int64MultiplyScale1000(a int64) (int64, bool) {
132 if a == 0 || a == 1 {
133 return a * 1000, true
134 }
135 if a == mostNegative {
136 return 0, false
137 }
138 c := a * 1000
139 return c, c/1000 == a
140}
141
142// positiveScaleInt64 multiplies base by 10^scale, returning false if the
143// value overflows. Passing a negative scale is undefined.
144func positiveScaleInt64(base int64, scale Scale) (int64, bool) {
145 switch scale {
146 case 0:
147 return base, true
148 case 1:
149 return int64MultiplyScale10(base)
150 case 2:
151 return int64MultiplyScale100(base)
152 case 3:
153 return int64MultiplyScale1000(base)
154 case 6:
155 return int64MultiplyScale(base, 1000000)
156 case 9:
157 return int64MultiplyScale(base, 1000000000)
158 default:
159 value := base
160 var ok bool
161 for i := Scale(0); i < scale; i++ {
162 if value, ok = int64MultiplyScale(value, 10); !ok {
163 return 0, false
164 }
165 }
166 return value, true
167 }
168}
169
170// negativeScaleInt64 reduces base by the provided scale, rounding up, until the
171// value is zero or the scale is reached. Passing a negative scale is undefined.
172// The value returned, if not exact, is rounded away from zero.
173func negativeScaleInt64(base int64, scale Scale) (result int64, exact bool) {
174 if scale == 0 {
175 return base, true
176 }
177
178 value := base
179 var fraction bool
180 for i := Scale(0); i < scale; i++ {
181 if !fraction && value%10 != 0 {
182 fraction = true
183 }
184 value = value / 10
185 if value == 0 {
186 if fraction {
187 if base > 0 {
188 return 1, false
189 }
190 return -1, false
191 }
192 return 0, true
193 }
194 }
195 if fraction {
196 if base > 0 {
David Bainbridge86971522019-09-26 22:09:39 +0000197 value++
Zack Williamse940c7a2019-08-21 14:25:39 -0700198 } else {
David Bainbridge86971522019-09-26 22:09:39 +0000199 value--
Zack Williamse940c7a2019-08-21 14:25:39 -0700200 }
201 }
202 return value, !fraction
203}
204
205func pow10Int64(b int64) int64 {
206 switch b {
207 case 0:
208 return 1
209 case 1:
210 return 10
211 case 2:
212 return 100
213 case 3:
214 return 1000
215 case 4:
216 return 10000
217 case 5:
218 return 100000
219 case 6:
220 return 1000000
221 case 7:
222 return 10000000
223 case 8:
224 return 100000000
225 case 9:
226 return 1000000000
227 case 10:
228 return 10000000000
229 case 11:
230 return 100000000000
231 case 12:
232 return 1000000000000
233 case 13:
234 return 10000000000000
235 case 14:
236 return 100000000000000
237 case 15:
238 return 1000000000000000
239 case 16:
240 return 10000000000000000
241 case 17:
242 return 100000000000000000
243 case 18:
244 return 1000000000000000000
245 default:
246 return 0
247 }
248}
249
250// negativeScaleInt64 returns the result of dividing base by scale * 10 and the remainder, or
251// false if no such division is possible. Dividing by negative scales is undefined.
252func divideByScaleInt64(base int64, scale Scale) (result, remainder int64, exact bool) {
253 if scale == 0 {
254 return base, 0, true
255 }
256 // the max scale representable in base 10 in an int64 is 18 decimal places
257 if scale >= 18 {
258 return 0, base, false
259 }
260 divisor := pow10Int64(int64(scale))
261 return base / divisor, base % divisor, true
262}
263
264// removeInt64Factors divides in a loop; the return values have the property that
265// value == result * base ^ scale
266func removeInt64Factors(value int64, base int64) (result int64, times int32) {
267 times = 0
268 result = value
269 negative := result < 0
270 if negative {
271 result = -result
272 }
273 switch base {
274 // allow the compiler to optimize the common cases
275 case 10:
276 for result >= 10 && result%10 == 0 {
277 times++
278 result = result / 10
279 }
280 // allow the compiler to optimize the common cases
281 case 1024:
282 for result >= 1024 && result%1024 == 0 {
283 times++
284 result = result / 1024
285 }
286 default:
287 for result >= base && result%base == 0 {
288 times++
289 result = result / base
290 }
291 }
292 if negative {
293 result = -result
294 }
295 return result, times
296}
297
298// removeBigIntFactors divides in a loop; the return values have the property that
299// d == result * factor ^ times
300// d may be modified in place.
301// If d == 0, then the return values will be (0, 0)
302func removeBigIntFactors(d, factor *big.Int) (result *big.Int, times int32) {
303 q := big.NewInt(0)
304 m := big.NewInt(0)
305 for d.Cmp(bigZero) != 0 {
306 q.DivMod(d, factor, m)
307 if m.Cmp(bigZero) != 0 {
308 break
309 }
310 times++
311 d, q = q, d
312 }
313 return d, times
314}