1
// Sources flattened with hardhat v2.23.0 https://hardhat.org
2
3
// SPDX-License-Identifier: GPL-3.0 AND MIT AND Unlicense
4
5
6
7
// Original license: SPDX_License_Identifier: Unlicense
8
pragma solidity >=0.8.4;
9
10
/// @notice Emitted when the result overflows uint256.
11
error PRBMath__MulDivFixedPointOverflow(uint256 prod1);
12
13
/// @notice Emitted when the result overflows uint256.
14
error PRBMath__MulDivOverflow(uint256 prod1, uint256 denominator);
15
16
/// @notice Emitted when one of the inputs is type(int256).min.
17
error PRBMath__MulDivSignedInputTooSmall();
18
19
/// @notice Emitted when the intermediary absolute result overflows int256.
20
error PRBMath__MulDivSignedOverflow(uint256 rAbs);
21
22
/// @notice Emitted when the input is MIN_SD59x18.
23
error PRBMathSD59x18__AbsInputTooSmall();
24
25
/// @notice Emitted when ceiling a number overflows SD59x18.
26
error PRBMathSD59x18__CeilOverflow(int256 x);
27
28
/// @notice Emitted when one of the inputs is MIN_SD59x18.
29
error PRBMathSD59x18__DivInputTooSmall();
30
31
/// @notice Emitted when one of the intermediary unsigned results overflows SD59x18.
32
error PRBMathSD59x18__DivOverflow(uint256 rAbs);
33
34
/// @notice Emitted when the input is greater than 133.084258667509499441.
35
error PRBMathSD59x18__ExpInputTooBig(int256 x);
36
37
/// @notice Emitted when the input is greater than 192.
38
error PRBMathSD59x18__Exp2InputTooBig(int256 x);
39
40
/// @notice Emitted when flooring a number underflows SD59x18.
41
error PRBMathSD59x18__FloorUnderflow(int256 x);
42
43
/// @notice Emitted when converting a basic integer to the fixed-point format overflows SD59x18.
44
error PRBMathSD59x18__FromIntOverflow(int256 x);
45
46
/// @notice Emitted when converting a basic integer to the fixed-point format underflows SD59x18.
47
error PRBMathSD59x18__FromIntUnderflow(int256 x);
48
49
/// @notice Emitted when the product of the inputs is negative.
50
error PRBMathSD59x18__GmNegativeProduct(int256 x, int256 y);
51
52
/// @notice Emitted when multiplying the inputs overflows SD59x18.
53
error PRBMathSD59x18__GmOverflow(int256 x, int256 y);
54
55
/// @notice Emitted when the input is less than or equal to zero.
56
error PRBMathSD59x18__LogInputTooSmall(int256 x);
57
58
/// @notice Emitted when one of the inputs is MIN_SD59x18.
59
error PRBMathSD59x18__MulInputTooSmall();
60
61
/// @notice Emitted when the intermediary absolute result overflows SD59x18.
62
error PRBMathSD59x18__MulOverflow(uint256 rAbs);
63
64
/// @notice Emitted when the intermediary absolute result overflows SD59x18.
65
error PRBMathSD59x18__PowuOverflow(uint256 rAbs);
66
67
/// @notice Emitted when the input is negative.
68
error PRBMathSD59x18__SqrtNegativeInput(int256 x);
69
70
/// @notice Emitted when the calculating the square root overflows SD59x18.
71
error PRBMathSD59x18__SqrtOverflow(int256 x);
72
73
/// @notice Emitted when addition overflows UD60x18.
74
error PRBMathUD60x18__AddOverflow(uint256 x, uint256 y);
75
76
/// @notice Emitted when ceiling a number overflows UD60x18.
77
error PRBMathUD60x18__CeilOverflow(uint256 x);
78
79
/// @notice Emitted when the input is greater than 133.084258667509499441.
80
error PRBMathUD60x18__ExpInputTooBig(uint256 x);
81
82
/// @notice Emitted when the input is greater than 192.
83
error PRBMathUD60x18__Exp2InputTooBig(uint256 x);
84
85
/// @notice Emitted when converting a basic integer to the fixed-point format format overflows UD60x18.
86
error PRBMathUD60x18__FromUintOverflow(uint256 x);
87
88
/// @notice Emitted when multiplying the inputs overflows UD60x18.
89
error PRBMathUD60x18__GmOverflow(uint256 x, uint256 y);
90
91
/// @notice Emitted when the input is less than 1.
92
error PRBMathUD60x18__LogInputTooSmall(uint256 x);
93
94
/// @notice Emitted when the calculating the square root overflows UD60x18.
95
error PRBMathUD60x18__SqrtOverflow(uint256 x);
96
97
/// @notice Emitted when subtraction underflows UD60x18.
98
error PRBMathUD60x18__SubUnderflow(uint256 x, uint256 y);
99
100
/// @dev Common mathematical functions used in both PRBMathSD59x18 and PRBMathUD60x18. Note that this shared library
101
/// does not always assume the signed 59.18-decimal fixed-point or the unsigned 60.18-decimal fixed-point
102
/// representation. When it does not, it is explicitly mentioned in the NatSpec documentation.
103
library PRBMath {
104
/// STRUCTS ///
105
106
struct SD59x18 {
107
int256 value;
108
}
109
110
struct UD60x18 {
111
uint256 value;
112
}
113
114
/// STORAGE ///
115
116
/// @dev How many trailing decimals can be represented.
117
uint256 internal constant SCALE = 1e18;
118
119
/// @dev Largest power of two divisor of SCALE.
120
uint256 internal constant SCALE_LPOTD = 262144;
121
122
/// @dev SCALE inverted mod 2^256.
123
uint256 internal constant SCALE_INVERSE =
124
78156646155174841979727994598816262306175212592076161876661_508869554232690281;
125
126
/// FUNCTIONS ///
127
128
/// @notice Calculates the binary exponent of x using the binary fraction method.
129
/// @dev Has to use 192.64-bit fixed-point numbers.
130
/// See https://ethereum.stackexchange.com/a/96594/24693.
131
/// @param x The exponent as an unsigned 192.64-bit fixed-point number.
132
/// @return result The result as an unsigned 60.18-decimal fixed-point number.
133
function exp2(uint256 x) internal pure returns (uint256 result) {
134
unchecked {
135
// Start from 0.5 in the 192.64-bit fixed-point format.
136
result = 0x800000000000000000000000000000000000000000000000;
137
138
// Multiply the result by root(2, 2^-i) when the bit at position i is 1. None of the intermediary results overflows
139
// because the initial result is 2^191 and all magic factors are less than 2^65.
140
if (x & 0x8000000000000000 > 0) {
141
result = (result * 0x16A09E667F3BCC909) >> 64;
142
}
143
if (x & 0x4000000000000000 > 0) {
144
result = (result * 0x1306FE0A31B7152DF) >> 64;
145
}
146
if (x & 0x2000000000000000 > 0) {
147
result = (result * 0x1172B83C7D517ADCE) >> 64;
148
}
149
if (x & 0x1000000000000000 > 0) {
150
result = (result * 0x10B5586CF9890F62A) >> 64;
151
}
152
if (x & 0x800000000000000 > 0) {
153
result = (result * 0x1059B0D31585743AE) >> 64;
154
}
155
if (x & 0x400000000000000 > 0) {
156
result = (result * 0x102C9A3E778060EE7) >> 64;
157
}
158
if (x & 0x200000000000000 > 0) {
159
result = (result * 0x10163DA9FB33356D8) >> 64;
160
}
161
if (x & 0x100000000000000 > 0) {
162
result = (result * 0x100B1AFA5ABCBED61) >> 64;
163
}
164
if (x & 0x80000000000000 > 0) {
165
result = (result * 0x10058C86DA1C09EA2) >> 64;
166
}
167
if (x & 0x40000000000000 > 0) {
168
result = (result * 0x1002C605E2E8CEC50) >> 64;
169
}
170
if (x & 0x20000000000000 > 0) {
171
result = (result * 0x100162F3904051FA1) >> 64;
172
}
173
if (x & 0x10000000000000 > 0) {
174
result = (result * 0x1000B175EFFDC76BA) >> 64;
175
}
176
if (x & 0x8000000000000 > 0) {
177
result = (result * 0x100058BA01FB9F96D) >> 64;
178
}
179
if (x & 0x4000000000000 > 0) {
180
result = (result * 0x10002C5CC37DA9492) >> 64;
181
}
182
if (x & 0x2000000000000 > 0) {
183
result = (result * 0x1000162E525EE0547) >> 64;
184
}
185
if (x & 0x1000000000000 > 0) {
186
result = (result * 0x10000B17255775C04) >> 64;
187
}
188
if (x & 0x800000000000 > 0) {
189
result = (result * 0x1000058B91B5BC9AE) >> 64;
190
}
191
if (x & 0x400000000000 > 0) {
192
result = (result * 0x100002C5C89D5EC6D) >> 64;
193
}
194
if (x & 0x200000000000 > 0) {
195
result = (result * 0x10000162E43F4F831) >> 64;
196
}
197
if (x & 0x100000000000 > 0) {
198
result = (result * 0x100000B1721BCFC9A) >> 64;
199
}
200
if (x & 0x80000000000 > 0) {
201
result = (result * 0x10000058B90CF1E6E) >> 64;
202
}
203
if (x & 0x40000000000 > 0) {
204
result = (result * 0x1000002C5C863B73F) >> 64;
205
}
206
if (x & 0x20000000000 > 0) {
207
result = (result * 0x100000162E430E5A2) >> 64;
208
}
209
if (x & 0x10000000000 > 0) {
210
result = (result * 0x1000000B172183551) >> 64;
211
}
212
if (x & 0x8000000000 > 0) {
213
result = (result * 0x100000058B90C0B49) >> 64;
214
}
215
if (x & 0x4000000000 > 0) {
216
result = (result * 0x10000002C5C8601CC) >> 64;
217
}
218
if (x & 0x2000000000 > 0) {
219
result = (result * 0x1000000162E42FFF0) >> 64;
220
}
221
if (x & 0x1000000000 > 0) {
222
result = (result * 0x10000000B17217FBB) >> 64;
223
}
224
if (x & 0x800000000 > 0) {
225
result = (result * 0x1000000058B90BFCE) >> 64;
226
}
227
if (x & 0x400000000 > 0) {
228
result = (result * 0x100000002C5C85FE3) >> 64;
229
}
230
if (x & 0x200000000 > 0) {
231
result = (result * 0x10000000162E42FF1) >> 64;
232
}
233
if (x & 0x100000000 > 0) {
234
result = (result * 0x100000000B17217F8) >> 64;
235
}
236
if (x & 0x80000000 > 0) {
237
result = (result * 0x10000000058B90BFC) >> 64;
238
}
239
if (x & 0x40000000 > 0) {
240
result = (result * 0x1000000002C5C85FE) >> 64;
241
}
242
if (x & 0x20000000 > 0) {
243
result = (result * 0x100000000162E42FF) >> 64;
244
}
245
if (x & 0x10000000 > 0) {
246
result = (result * 0x1000000000B17217F) >> 64;
247
}
248
if (x & 0x8000000 > 0) {
249
result = (result * 0x100000000058B90C0) >> 64;
250
}
251
if (x & 0x4000000 > 0) {
252
result = (result * 0x10000000002C5C860) >> 64;
253
}
254
if (x & 0x2000000 > 0) {
255
result = (result * 0x1000000000162E430) >> 64;
256
}
257
if (x & 0x1000000 > 0) {
258
result = (result * 0x10000000000B17218) >> 64;
259
}
260
if (x & 0x800000 > 0) {
261
result = (result * 0x1000000000058B90C) >> 64;
262
}
263
if (x & 0x400000 > 0) {
264
result = (result * 0x100000000002C5C86) >> 64;
265
}
266
if (x & 0x200000 > 0) {
267
result = (result * 0x10000000000162E43) >> 64;
268
}
269
if (x & 0x100000 > 0) {
270
result = (result * 0x100000000000B1721) >> 64;
271
}
272
if (x & 0x80000 > 0) {
273
result = (result * 0x10000000000058B91) >> 64;
274
}
275
if (x & 0x40000 > 0) {
276
result = (result * 0x1000000000002C5C8) >> 64;
277
}
278
if (x & 0x20000 > 0) {
279
result = (result * 0x100000000000162E4) >> 64;
280
}
281
if (x & 0x10000 > 0) {
282
result = (result * 0x1000000000000B172) >> 64;
283
}
284
if (x & 0x8000 > 0) {
285
result = (result * 0x100000000000058B9) >> 64;
286
}
287
if (x & 0x4000 > 0) {
288
result = (result * 0x10000000000002C5D) >> 64;
289
}
290
if (x & 0x2000 > 0) {
291
result = (result * 0x1000000000000162E) >> 64;
292
}
293
if (x & 0x1000 > 0) {
294
result = (result * 0x10000000000000B17) >> 64;
295
}
296
if (x & 0x800 > 0) {
297
result = (result * 0x1000000000000058C) >> 64;
298
}
299
if (x & 0x400 > 0) {
300
result = (result * 0x100000000000002C6) >> 64;
301
}
302
if (x & 0x200 > 0) {
303
result = (result * 0x10000000000000163) >> 64;
304
}
305
if (x & 0x100 > 0) {
306
result = (result * 0x100000000000000B1) >> 64;
307
}
308
if (x & 0x80 > 0) {
309
result = (result * 0x10000000000000059) >> 64;
310
}
311
if (x & 0x40 > 0) {
312
result = (result * 0x1000000000000002C) >> 64;
313
}
314
if (x & 0x20 > 0) {
315
result = (result * 0x10000000000000016) >> 64;
316
}
317
if (x & 0x10 > 0) {
318
result = (result * 0x1000000000000000B) >> 64;
319
}
320
if (x & 0x8 > 0) {
321
result = (result * 0x10000000000000006) >> 64;
322
}
323
if (x & 0x4 > 0) {
324
result = (result * 0x10000000000000003) >> 64;
325
}
326
if (x & 0x2 > 0) {
327
result = (result * 0x10000000000000001) >> 64;
328
}
329
if (x & 0x1 > 0) {
330
result = (result * 0x10000000000000001) >> 64;
331
}
332
333
// We're doing two things at the same time:
334
//
335
// 1. Multiply the result by 2^n + 1, where "2^n" is the integer part and the one is added to account for
336
// the fact that we initially set the result to 0.5. This is accomplished by subtracting from 191
337
// rather than 192.
338
// 2. Convert the result to the unsigned 60.18-decimal fixed-point format.
339
//
340
// This works because 2^(191-ip) = 2^ip / 2^191, where "ip" is the integer part "2^n".
341
result *= SCALE;
342
result >>= (191 - (x >> 64));
343
}
344
}
345
346
/// @notice Finds the zero-based index of the first one in the binary representation of x.
347
/// @dev See the note on msb in the "Find First Set" Wikipedia article https://en.wikipedia.org/wiki/Find_first_set
348
/// @param x The uint256 number for which to find the index of the most significant bit.
349
/// @return msb The index of the most significant bit as an uint256.
350
function mostSignificantBit(uint256 x) internal pure returns (uint256 msb) {
351
if (x >= 2**128) {
352
x >>= 128;
353
msb += 128;
354
}
355
if (x >= 2**64) {
356
x >>= 64;
357
msb += 64;
358
}
359
if (x >= 2**32) {
360
x >>= 32;
361
msb += 32;
362
}
363
if (x >= 2**16) {
364
x >>= 16;
365
msb += 16;
366
}
367
if (x >= 2**8) {
368
x >>= 8;
369
msb += 8;
370
}
371
if (x >= 2**4) {
372
x >>= 4;
373
msb += 4;
374
}
375
if (x >= 2**2) {
376
x >>= 2;
377
msb += 2;
378
}
379
if (x >= 2**1) {
380
// No need to shift x any more.
381
msb += 1;
382
}
383
}
384
385
/// @notice Calculates floor(x*y÷denominator) with full precision.
386
///
387
/// @dev Credit to Remco Bloemen under MIT license https://xn--2-umb.com/21/muldiv.
388
///
389
/// Requirements:
390
/// - The denominator cannot be zero.
391
/// - The result must fit within uint256.
392
///
393
/// Caveats:
394
/// - This function does not work with fixed-point numbers.
395
///
396
/// @param x The multiplicand as an uint256.
397
/// @param y The multiplier as an uint256.
398
/// @param denominator The divisor as an uint256.
399
/// @return result The result as an uint256.
400
function mulDiv(
401
uint256 x,
402
uint256 y,
403
uint256 denominator
404
) internal pure returns (uint256 result) {
405
// 512-bit multiply [prod1 prod0] = x * y. Compute the product mod 2^256 and mod 2^256 - 1, then use
406
// use the Chinese Remainder Theorem to reconstruct the 512 bit result. The result is stored in two 256
407
// variables such that product = prod1 * 2^256 + prod0.
408
uint256 prod0; // Least significant 256 bits of the product
409
uint256 prod1; // Most significant 256 bits of the product
410
assembly {
411
let mm := mulmod(x, y, not(0))
412
prod0 := mul(x, y)
413
prod1 := sub(sub(mm, prod0), lt(mm, prod0))
414
}
415
416
// Handle non-overflow cases, 256 by 256 division.
417
if (prod1 == 0) {
418
unchecked {
419
result = prod0 / denominator;
420
}
421
return result;
422
}
423
424
// Make sure the result is less than 2^256. Also prevents denominator == 0.
425
if (prod1 >= denominator) {
426
revert PRBMath__MulDivOverflow(prod1, denominator);
427
}
428
429
///////////////////////////////////////////////
430
// 512 by 256 division.
431
///////////////////////////////////////////////
432
433
// Make division exact by subtracting the remainder from [prod1 prod0].
434
uint256 remainder;
435
assembly {
436
// Compute remainder using mulmod.
437
remainder := mulmod(x, y, denominator)
438
439
// Subtract 256 bit number from 512 bit number.
440
prod1 := sub(prod1, gt(remainder, prod0))
441
prod0 := sub(prod0, remainder)
442
}
443
444
// Factor powers of two out of denominator and compute largest power of two divisor of denominator. Always >= 1.
445
// See https://cs.stackexchange.com/q/138556/92363.
446
unchecked {
447
// Does not overflow because the denominator cannot be zero at this stage in the function.
448
uint256 lpotdod = denominator & (~denominator + 1);
449
assembly {
450
// Divide denominator by lpotdod.
451
denominator := div(denominator, lpotdod)
452
453
// Divide [prod1 prod0] by lpotdod.
454
prod0 := div(prod0, lpotdod)
455
456
// Flip lpotdod such that it is 2^256 / lpotdod. If lpotdod is zero, then it becomes one.
457
lpotdod := add(div(sub(0, lpotdod), lpotdod), 1)
458
}
459
460
// Shift in bits from prod1 into prod0.
461
prod0 |= prod1 * lpotdod;
462
463
// Invert denominator mod 2^256. Now that denominator is an odd number, it has an inverse modulo 2^256 such
464
// that denominator * inv = 1 mod 2^256. Compute the inverse by starting with a seed that is correct for
465
// four bits. That is, denominator * inv = 1 mod 2^4.
466
uint256 inverse = (3 * denominator) ^ 2;
467
468
// Use the Newton-Raphson iteration to improve the precision. Thanks to Hensel's lifting lemma, this also works
469
// in modular arithmetic, doubling the correct bits in each step.
470
inverse *= 2 - denominator * inverse; // inverse mod 2^8
471
inverse *= 2 - denominator * inverse; // inverse mod 2^16
472
inverse *= 2 - denominator * inverse; // inverse mod 2^32
473
inverse *= 2 - denominator * inverse; // inverse mod 2^64
474
inverse *= 2 - denominator * inverse; // inverse mod 2^128
475
inverse *= 2 - denominator * inverse; // inverse mod 2^256
476
477
// Because the division is now exact we can divide by multiplying with the modular inverse of denominator.
478
// This will give us the correct result modulo 2^256. Since the preconditions guarantee that the outcome is
479
// less than 2^256, this is the final result. We don't need to compute the high bits of the result and prod1
480
// is no longer required.
481
result = prod0 * inverse;
482
return result;
483
}
484
}
485
486
/// @notice Calculates floor(x*y÷1e18) with full precision.
487
///
488
/// @dev Variant of "mulDiv" with constant folding, i.e. in which the denominator is always 1e18. Before returning the
489
/// final result, we add 1 if (x * y) % SCALE >= HALF_SCALE. Without this, 6.6e-19 would be truncated to 0 instead of
490
/// being rounded to 1e-18. See "Listing 6" and text above it at https://accu.org/index.php/journals/1717.
491
///
492
/// Requirements:
493
/// - The result must fit within uint256.
494
///
495
/// Caveats:
496
/// - The body is purposely left uncommented; see the NatSpec comments in "PRBMath.mulDiv" to understand how this works.
497
/// - It is assumed that the result can never be type(uint256).max when x and y solve the following two equations:
498
/// 1. x * y = type(uint256).max * SCALE
499
/// 2. (x * y) % SCALE >= SCALE / 2
500
///
501
/// @param x The multiplicand as an unsigned 60.18-decimal fixed-point number.
502
/// @param y The multiplier as an unsigned 60.18-decimal fixed-point number.
503
/// @return result The result as an unsigned 60.18-decimal fixed-point number.
504
function mulDivFixedPoint(uint256 x, uint256 y) internal pure returns (uint256 result) {
505
uint256 prod0;
506
uint256 prod1;
507
assembly {
508
let mm := mulmod(x, y, not(0))
509
prod0 := mul(x, y)
510
prod1 := sub(sub(mm, prod0), lt(mm, prod0))
511
}
512
513
if (prod1 >= SCALE) {
514
revert PRBMath__MulDivFixedPointOverflow(prod1);
515
}
516
517
uint256 remainder;
518
uint256 roundUpUnit;
519
assembly {
520
remainder := mulmod(x, y, SCALE)
521
roundUpUnit := gt(remainder, 499999999999999999)
522
}
523
524
if (prod1 == 0) {
525
unchecked {
526
result = (prod0 / SCALE) + roundUpUnit;
527
return result;
528
}
529
}
530
531
assembly {
532
result := add(
533
mul(
534
or(
535
div(sub(prod0, remainder), SCALE_LPOTD),
536
mul(sub(prod1, gt(remainder, prod0)), add(div(sub(0, SCALE_LPOTD), SCALE_LPOTD), 1))
537
),
538
SCALE_INVERSE
539
),
540
roundUpUnit
541
)
542
}
543
}
544
545
/// @notice Calculates floor(x*y÷denominator) with full precision.
546
///
547
/// @dev An extension of "mulDiv" for signed numbers. Works by computing the signs and the absolute values separately.
548
///
549
/// Requirements:
550
/// - None of the inputs can be type(int256).min.
551
/// - The result must fit within int256.
552
///
553
/// @param x The multiplicand as an int256.
554
/// @param y The multiplier as an int256.
555
/// @param denominator The divisor as an int256.
556
/// @return result The result as an int256.
557
function mulDivSigned(
558
int256 x,
559
int256 y,
560
int256 denominator
561
) internal pure returns (int256 result) {
562
if (x == type(int256).min || y == type(int256).min || denominator == type(int256).min) {
563
revert PRBMath__MulDivSignedInputTooSmall();
564
}
565
566
// Get hold of the absolute values of x, y and the denominator.
567
uint256 ax;
568
uint256 ay;
569
uint256 ad;
570
unchecked {
571
ax = x < 0 ? uint256(-x) : uint256(x);
572
ay = y < 0 ? uint256(-y) : uint256(y);
573
ad = denominator < 0 ? uint256(-denominator) : uint256(denominator);
574
}
575
576
// Compute the absolute value of (x*y)÷denominator. The result must fit within int256.
577
uint256 rAbs = mulDiv(ax, ay, ad);
578
if (rAbs > uint256(type(int256).max)) {
579
revert PRBMath__MulDivSignedOverflow(rAbs);
580
}
581
582
// Get the signs of x, y and the denominator.
583
uint256 sx;
584
uint256 sy;
585
uint256 sd;
586
assembly {
587
sx := sgt(x, sub(0, 1))
588
sy := sgt(y, sub(0, 1))
589
sd := sgt(denominator, sub(0, 1))
590
}
591
592
// XOR over sx, sy and sd. This is checking whether there are one or three negative signs in the inputs.
593
// If yes, the result should be negative.
594
result = sx ^ sy ^ sd == 0 ? -int256(rAbs) : int256(rAbs);
595
}
596
597
/// @notice Calculates the square root of x, rounding down.
598
/// @dev Uses the Babylonian method https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method.
599
///
600
/// Caveats:
601
/// - This function does not work with fixed-point numbers.
602
///
603
/// @param x The uint256 number for which to calculate the square root.
604
/// @return result The result as an uint256.
605
function sqrt(uint256 x) internal pure returns (uint256 result) {
606
if (x == 0) {
607
return 0;
608
}
609
610
// Set the initial guess to the least power of two that is greater than or equal to sqrt(x).
611
uint256 xAux = uint256(x);
612
result = 1;
613
if (xAux >= 0x100000000000000000000000000000000) {
614
xAux >>= 128;
615
result <<= 64;
616
}
617
if (xAux >= 0x10000000000000000) {
618
xAux >>= 64;
619
result <<= 32;
620
}
621
if (xAux >= 0x100000000) {
622
xAux >>= 32;
623
result <<= 16;
624
}
625
if (xAux >= 0x10000) {
626
xAux >>= 16;
627
result <<= 8;
628
}
629
if (xAux >= 0x100) {
630
xAux >>= 8;
631
result <<= 4;
632
}
633
if (xAux >= 0x10) {
634
xAux >>= 4;
635
result <<= 2;
636
}
637
if (xAux >= 0x8) {
638
result <<= 1;
639
}
640
641
// The operations can never overflow because the result is max 2^127 when it enters this block.
642
unchecked {
643
result = (result + x / result) >> 1;
644
result = (result + x / result) >> 1;
645
result = (result + x / result) >> 1;
646
result = (result + x / result) >> 1;
647
result = (result + x / result) >> 1;
648
result = (result + x / result) >> 1;
649
result = (result + x / result) >> 1; // Seven iterations should be enough
650
uint256 roundedDownResult = x / result;
651
return result >= roundedDownResult ? roundedDownResult : result;
652
}
653
}
654
}
655
656
657
658
659
// Original license: SPDX_License_Identifier: Unlicense
660
pragma solidity >=0.8.4;
661
662
/// @title PRBMathSD59x18
663
/// @author Paul Razvan Berg
664
/// @notice Smart contract library for advanced fixed-point math that works with int256 numbers considered to have 18
665
/// trailing decimals. We call this number representation signed 59.18-decimal fixed-point, since the numbers can have
666
/// a sign and there can be up to 59 digits in the integer part and up to 18 decimals in the fractional part. The numbers
667
/// are bound by the minimum and the maximum values permitted by the Solidity type int256.
668
library PRBMathSD59x18 {
669
/// @dev log2(e) as a signed 59.18-decimal fixed-point number.
670
int256 internal constant LOG2_E = 1_442695040888963407;
671
672
/// @dev Half the SCALE number.
673
int256 internal constant HALF_SCALE = 5e17;
674
675
/// @dev The maximum value a signed 59.18-decimal fixed-point number can have.
676
int256 internal constant MAX_SD59x18 =
677
57896044618658097711785492504343953926634992332820282019728_792003956564819967;
678
679
/// @dev The maximum whole value a signed 59.18-decimal fixed-point number can have.
680
int256 internal constant MAX_WHOLE_SD59x18 =
681
57896044618658097711785492504343953926634992332820282019728_000000000000000000;
682
683
/// @dev The minimum value a signed 59.18-decimal fixed-point number can have.
684
int256 internal constant MIN_SD59x18 =
685
-57896044618658097711785492504343953926634992332820282019728_792003956564819968;
686
687
/// @dev The minimum whole value a signed 59.18-decimal fixed-point number can have.
688
int256 internal constant MIN_WHOLE_SD59x18 =
689
-57896044618658097711785492504343953926634992332820282019728_000000000000000000;
690
691
/// @dev How many trailing decimals can be represented.
692
int256 internal constant SCALE = 1e18;
693
694
/// INTERNAL FUNCTIONS ///
695
696
/// @notice Calculate the absolute value of x.
697
///
698
/// @dev Requirements:
699
/// - x must be greater than MIN_SD59x18.
700
///
701
/// @param x The number to calculate the absolute value for.
702
/// @param result The absolute value of x.
703
function abs(int256 x) internal pure returns (int256 result) {
704
unchecked {
705
if (x == MIN_SD59x18) {
706
revert PRBMathSD59x18__AbsInputTooSmall();
707
}
708
result = x < 0 ? -x : x;
709
}
710
}
711
712
/// @notice Calculates the arithmetic average of x and y, rounding down.
713
/// @param x The first operand as a signed 59.18-decimal fixed-point number.
714
/// @param y The second operand as a signed 59.18-decimal fixed-point number.
715
/// @return result The arithmetic average as a signed 59.18-decimal fixed-point number.
716
function avg(int256 x, int256 y) internal pure returns (int256 result) {
717
// The operations can never overflow.
718
unchecked {
719
int256 sum = (x >> 1) + (y >> 1);
720
if (sum < 0) {
721
// If at least one of x and y is odd, we add 1 to the result. This is because shifting negative numbers to the
722
// right rounds down to infinity.
723
assembly {
724
result := add(sum, and(or(x, y), 1))
725
}
726
} else {
727
// If both x and y are odd, we add 1 to the result. This is because if both numbers are odd, the 0.5
728
// remainder gets truncated twice.
729
result = sum + (x & y & 1);
730
}
731
}
732
}
733
734
/// @notice Yields the least greatest signed 59.18 decimal fixed-point number greater than or equal to x.
735
///
736
/// @dev Optimized for fractional value inputs, because for every whole value there are (1e18 - 1) fractional counterparts.
737
/// See https://en.wikipedia.org/wiki/Floor_and_ceiling_functions.
738
///
739
/// Requirements:
740
/// - x must be less than or equal to MAX_WHOLE_SD59x18.
741
///
742
/// @param x The signed 59.18-decimal fixed-point number to ceil.
743
/// @param result The least integer greater than or equal to x, as a signed 58.18-decimal fixed-point number.
744
function ceil(int256 x) internal pure returns (int256 result) {
745
if (x > MAX_WHOLE_SD59x18) {
746
revert PRBMathSD59x18__CeilOverflow(x);
747
}
748
unchecked {
749
int256 remainder = x % SCALE;
750
if (remainder == 0) {
751
result = x;
752
} else {
753
// Solidity uses C fmod style, which returns a modulus with the same sign as x.
754
result = x - remainder;
755
if (x > 0) {
756
result += SCALE;
757
}
758
}
759
}
760
}
761
762
/// @notice Divides two signed 59.18-decimal fixed-point numbers, returning a new signed 59.18-decimal fixed-point number.
763
///
764
/// @dev Variant of "mulDiv" that works with signed numbers. Works by computing the signs and the absolute values separately.
765
///
766
/// Requirements:
767
/// - All from "PRBMath.mulDiv".
768
/// - None of the inputs can be MIN_SD59x18.
769
/// - The denominator cannot be zero.
770
/// - The result must fit within int256.
771
///
772
/// Caveats:
773
/// - All from "PRBMath.mulDiv".
774
///
775
/// @param x The numerator as a signed 59.18-decimal fixed-point number.
776
/// @param y The denominator as a signed 59.18-decimal fixed-point number.
777
/// @param result The quotient as a signed 59.18-decimal fixed-point number.
778
function div(int256 x, int256 y) internal pure returns (int256 result) {
779
if (x == MIN_SD59x18 || y == MIN_SD59x18) {
780
revert PRBMathSD59x18__DivInputTooSmall();
781
}
782
783
// Get hold of the absolute values of x and y.
784
uint256 ax;
785
uint256 ay;
786
unchecked {
787
ax = x < 0 ? uint256(-x) : uint256(x);
788
ay = y < 0 ? uint256(-y) : uint256(y);
789
}
790
791
// Compute the absolute value of (x*SCALE)÷y. The result must fit within int256.
792
uint256 rAbs = PRBMath.mulDiv(ax, uint256(SCALE), ay);
793
if (rAbs > uint256(MAX_SD59x18)) {
794
revert PRBMathSD59x18__DivOverflow(rAbs);
795
}
796
797
// Get the signs of x and y.
798
uint256 sx;
799
uint256 sy;
800
assembly {
801
sx := sgt(x, sub(0, 1))
802
sy := sgt(y, sub(0, 1))
803
}
804
805
// XOR over sx and sy. This is basically checking whether the inputs have the same sign. If yes, the result
806
// should be positive. Otherwise, it should be negative.
807
result = sx ^ sy == 1 ? -int256(rAbs) : int256(rAbs);
808
}
809
810
/// @notice Returns Euler's number as a signed 59.18-decimal fixed-point number.
811
/// @dev See https://en.wikipedia.org/wiki/E_(mathematical_constant).
812
function e() internal pure returns (int256 result) {
813
result = 2_718281828459045235;
814
}
815
816
/// @notice Calculates the natural exponent of x.
817
///
818
/// @dev Based on the insight that e^x = 2^(x * log2(e)).
819
///
820
/// Requirements:
821
/// - All from "log2".
822
/// - x must be less than 133.084258667509499441.
823
///
824
/// Caveats:
825
/// - All from "exp2".
826
/// - For any x less than -41.446531673892822322, the result is zero.
827
///
828
/// @param x The exponent as a signed 59.18-decimal fixed-point number.
829
/// @return result The result as a signed 59.18-decimal fixed-point number.
830
function exp(int256 x) internal pure returns (int256 result) {
831
// Without this check, the value passed to "exp2" would be less than -59.794705707972522261.
832
if (x < -41_446531673892822322) {
833
return 0;
834
}
835
836
// Without this check, the value passed to "exp2" would be greater than 192.
837
if (x >= 133_084258667509499441) {
838
revert PRBMathSD59x18__ExpInputTooBig(x);
839
}
840
841
// Do the fixed-point multiplication inline to save gas.
842
unchecked {
843
int256 doubleScaleProduct = x * LOG2_E;
844
result = exp2((doubleScaleProduct + HALF_SCALE) / SCALE);
845
}
846
}
847
848
/// @notice Calculates the binary exponent of x using the binary fraction method.
849
///
850
/// @dev See https://ethereum.stackexchange.com/q/79903/24693.
851
///
852
/// Requirements:
853
/// - x must be 192 or less.
854
/// - The result must fit within MAX_SD59x18.
855
///
856
/// Caveats:
857
/// - For any x less than -59.794705707972522261, the result is zero.
858
///
859
/// @param x The exponent as a signed 59.18-decimal fixed-point number.
860
/// @return result The result as a signed 59.18-decimal fixed-point number.
861
function exp2(int256 x) internal pure returns (int256 result) {
862
// This works because 2^(-x) = 1/2^x.
863
if (x < 0) {
864
// 2^59.794705707972522262 is the maximum number whose inverse does not truncate down to zero.
865
if (x < -59_794705707972522261) {
866
return 0;
867
}
868
869
// Do the fixed-point inversion inline to save gas. The numerator is SCALE * SCALE.
870
unchecked {
871
result = 1e36 / exp2(-x);
872
}
873
} else {
874
// 2^192 doesn't fit within the 192.64-bit format used internally in this function.
875
if (x >= 192e18) {
876
revert PRBMathSD59x18__Exp2InputTooBig(x);
877
}
878
879
unchecked {
880
// Convert x to the 192.64-bit fixed-point format.
881
uint256 x192x64 = (uint256(x) << 64) / uint256(SCALE);
882
883
// Safe to convert the result to int256 directly because the maximum input allowed is 192.
884
result = int256(PRBMath.exp2(x192x64));
885
}
886
}
887
}
888
889
/// @notice Yields the greatest signed 59.18 decimal fixed-point number less than or equal to x.
890
///
891
/// @dev Optimized for fractional value inputs, because for every whole value there are (1e18 - 1) fractional counterparts.
892
/// See https://en.wikipedia.org/wiki/Floor_and_ceiling_functions.
893
///
894
/// Requirements:
895
/// - x must be greater than or equal to MIN_WHOLE_SD59x18.
896
///
897
/// @param x The signed 59.18-decimal fixed-point number to floor.
898
/// @param result The greatest integer less than or equal to x, as a signed 58.18-decimal fixed-point number.
899
function floor(int256 x) internal pure returns (int256 result) {
900
if (x < MIN_WHOLE_SD59x18) {
901
revert PRBMathSD59x18__FloorUnderflow(x);
902
}
903
unchecked {
904
int256 remainder = x % SCALE;
905
if (remainder == 0) {
906
result = x;
907
} else {
908
// Solidity uses C fmod style, which returns a modulus with the same sign as x.
909
result = x - remainder;
910
if (x < 0) {
911
result -= SCALE;
912
}
913
}
914
}
915
}
916
917
/// @notice Yields the excess beyond the floor of x for positive numbers and the part of the number to the right
918
/// of the radix point for negative numbers.
919
/// @dev Based on the odd function definition. https://en.wikipedia.org/wiki/Fractional_part
920
/// @param x The signed 59.18-decimal fixed-point number to get the fractional part of.
921
/// @param result The fractional part of x as a signed 59.18-decimal fixed-point number.
922
function frac(int256 x) internal pure returns (int256 result) {
923
unchecked {
924
result = x % SCALE;
925
}
926
}
927
928
/// @notice Converts a number from basic integer form to signed 59.18-decimal fixed-point representation.
929
///
930
/// @dev Requirements:
931
/// - x must be greater than or equal to MIN_SD59x18 divided by SCALE.
932
/// - x must be less than or equal to MAX_SD59x18 divided by SCALE.
933
///
934
/// @param x The basic integer to convert.
935
/// @param result The same number in signed 59.18-decimal fixed-point representation.
936
function fromInt(int256 x) internal pure returns (int256 result) {
937
unchecked {
938
if (x < MIN_SD59x18 / SCALE) {
939
revert PRBMathSD59x18__FromIntUnderflow(x);
940
}
941
if (x > MAX_SD59x18 / SCALE) {
942
revert PRBMathSD59x18__FromIntOverflow(x);
943
}
944
result = x * SCALE;
945
}
946
}
947
948
/// @notice Calculates geometric mean of x and y, i.e. sqrt(x * y), rounding down.
949
///
950
/// @dev Requirements:
951
/// - x * y must fit within MAX_SD59x18, lest it overflows.
952
/// - x * y cannot be negative.
953
///
954
/// @param x The first operand as a signed 59.18-decimal fixed-point number.
955
/// @param y The second operand as a signed 59.18-decimal fixed-point number.
956
/// @return result The result as a signed 59.18-decimal fixed-point number.
957
function gm(int256 x, int256 y) internal pure returns (int256 result) {
958
if (x == 0) {
959
return 0;
960
}
961
962
unchecked {
963
// Checking for overflow this way is faster than letting Solidity do it.
964
int256 xy = x * y;
965
if (xy / x != y) {
966
revert PRBMathSD59x18__GmOverflow(x, y);
967
}
968
969
// The product cannot be negative.
970
if (xy < 0) {
971
revert PRBMathSD59x18__GmNegativeProduct(x, y);
972
}
973
974
// We don't need to multiply by the SCALE here because the x*y product had already picked up a factor of SCALE
975
// during multiplication. See the comments within the "sqrt" function.
976
result = int256(PRBMath.sqrt(uint256(xy)));
977
}
978
}
979
980
/// @notice Calculates 1 / x, rounding toward zero.
981
///
982
/// @dev Requirements:
983
/// - x cannot be zero.
984
///
985
/// @param x The signed 59.18-decimal fixed-point number for which to calculate the inverse.
986
/// @return result The inverse as a signed 59.18-decimal fixed-point number.
987
function inv(int256 x) internal pure returns (int256 result) {
988
unchecked {
989
// 1e36 is SCALE * SCALE.
990
result = 1e36 / x;
991
}
992
}
993
994
/// @notice Calculates the natural logarithm of x.
995
///
996
/// @dev Based on the insight that ln(x) = log2(x) / log2(e).
997
///
998
/// Requirements:
999
/// - All from "log2".
1000
///
1001
/// Caveats:
1002
/// - All from "log2".
1003
/// - This doesn't return exactly 1 for 2718281828459045235, for that we would need more fine-grained precision.
1004
///
1005
/// @param x The signed 59.18-decimal fixed-point number for which to calculate the natural logarithm.
1006
/// @return result The natural logarithm as a signed 59.18-decimal fixed-point number.
1007
function ln(int256 x) internal pure returns (int256 result) {
1008
// Do the fixed-point multiplication inline to save gas. This is overflow-safe because the maximum value that log2(x)
1009
// can return is 195205294292027477728.
1010
unchecked {
1011
result = (log2(x) * SCALE) / LOG2_E;
1012
}
1013
}
1014
1015
/// @notice Calculates the common logarithm of x.
1016
///
1017
/// @dev First checks if x is an exact power of ten and it stops if yes. If it's not, calculates the common
1018
/// logarithm based on the insight that log10(x) = log2(x) / log2(10).
1019
///
1020
/// Requirements:
1021
/// - All from "log2".
1022
///
1023
/// Caveats:
1024
/// - All from "log2".
1025
///
1026
/// @param x The signed 59.18-decimal fixed-point number for which to calculate the common logarithm.
1027
/// @return result The common logarithm as a signed 59.18-decimal fixed-point number.
1028
function log10(int256 x) internal pure returns (int256 result) {
1029
if (x <= 0) {
1030
revert PRBMathSD59x18__LogInputTooSmall(x);
1031
}
1032
1033
// Note that the "mul" in this block is the assembly mul operation, not the "mul" function defined in this contract.
1034
// prettier-ignore
1035
assembly {
1036
switch x
1037
case 1 { result := mul(SCALE, sub(0, 18)) }
1038
case 10 { result := mul(SCALE, sub(1, 18)) }
1039
case 100 { result := mul(SCALE, sub(2, 18)) }
1040
case 1000 { result := mul(SCALE, sub(3, 18)) }
1041
case 10000 { result := mul(SCALE, sub(4, 18)) }
1042
case 100000 { result := mul(SCALE, sub(5, 18)) }
1043
case 1000000 { result := mul(SCALE, sub(6, 18)) }
1044
case 10000000 { result := mul(SCALE, sub(7, 18)) }
1045
case 100000000 { result := mul(SCALE, sub(8, 18)) }
1046
case 1000000000 { result := mul(SCALE, sub(9, 18)) }
1047
case 10000000000 { result := mul(SCALE, sub(10, 18)) }
1048
case 100000000000 { result := mul(SCALE, sub(11, 18)) }
1049
case 1000000000000 { result := mul(SCALE, sub(12, 18)) }
1050
case 10000000000000 { result := mul(SCALE, sub(13, 18)) }
1051
case 100000000000000 { result := mul(SCALE, sub(14, 18)) }
1052
case 1000000000000000 { result := mul(SCALE, sub(15, 18)) }
1053
case 10000000000000000 { result := mul(SCALE, sub(16, 18)) }
1054
case 100000000000000000 { result := mul(SCALE, sub(17, 18)) }
1055
case 1000000000000000000 { result := 0 }
1056
case 10000000000000000000 { result := SCALE }
1057
case 100000000000000000000 { result := mul(SCALE, 2) }
1058
case 1000000000000000000000 { result := mul(SCALE, 3) }
1059
case 10000000000000000000000 { result := mul(SCALE, 4) }
1060
case 100000000000000000000000 { result := mul(SCALE, 5) }
1061
case 1000000000000000000000000 { result := mul(SCALE, 6) }
1062
case 10000000000000000000000000 { result := mul(SCALE, 7) }
1063
case 100000000000000000000000000 { result := mul(SCALE, 8) }
1064
case 1000000000000000000000000000 { result := mul(SCALE, 9) }
1065
case 10000000000000000000000000000 { result := mul(SCALE, 10) }
1066
case 100000000000000000000000000000 { result := mul(SCALE, 11) }
1067
case 1000000000000000000000000000000 { result := mul(SCALE, 12) }
1068
case 10000000000000000000000000000000 { result := mul(SCALE, 13) }
1069
case 100000000000000000000000000000000 { result := mul(SCALE, 14) }
1070
case 1000000000000000000000000000000000 { result := mul(SCALE, 15) }
1071
case 10000000000000000000000000000000000 { result := mul(SCALE, 16) }
1072
case 100000000000000000000000000000000000 { result := mul(SCALE, 17) }
1073
case 1000000000000000000000000000000000000 { result := mul(SCALE, 18) }
1074
case 10000000000000000000000000000000000000 { result := mul(SCALE, 19) }
1075
case 100000000000000000000000000000000000000 { result := mul(SCALE, 20) }
1076
case 1000000000000000000000000000000000000000 { result := mul(SCALE, 21) }
1077
case 10000000000000000000000000000000000000000 { result := mul(SCALE, 22) }
1078
case 100000000000000000000000000000000000000000 { result := mul(SCALE, 23) }
1079
case 1000000000000000000000000000000000000000000 { result := mul(SCALE, 24) }
1080
case 10000000000000000000000000000000000000000000 { result := mul(SCALE, 25) }
1081
case 100000000000000000000000000000000000000000000 { result := mul(SCALE, 26) }
1082
case 1000000000000000000000000000000000000000000000 { result := mul(SCALE, 27) }
1083
case 10000000000000000000000000000000000000000000000 { result := mul(SCALE, 28) }
1084
case 100000000000000000000000000000000000000000000000 { result := mul(SCALE, 29) }
1085
case 1000000000000000000000000000000000000000000000000 { result := mul(SCALE, 30) }
1086
case 10000000000000000000000000000000000000000000000000 { result := mul(SCALE, 31) }
1087
case 100000000000000000000000000000000000000000000000000 { result := mul(SCALE, 32) }
1088
case 1000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 33) }
1089
case 10000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 34) }
1090
case 100000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 35) }
1091
case 1000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 36) }
1092
case 10000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 37) }
1093
case 100000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 38) }
1094
case 1000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 39) }
1095
case 10000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 40) }
1096
case 100000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 41) }
1097
case 1000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 42) }
1098
case 10000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 43) }
1099
case 100000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 44) }
1100
case 1000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 45) }
1101
case 10000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 46) }
1102
case 100000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 47) }
1103
case 1000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 48) }
1104
case 10000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 49) }
1105
case 100000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 50) }
1106
case 1000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 51) }
1107
case 10000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 52) }
1108
case 100000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 53) }
1109
case 1000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 54) }
1110
case 10000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 55) }
1111
case 100000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 56) }
1112
case 1000000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 57) }
1113
case 10000000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 58) }
1114
default {
1115
result := MAX_SD59x18
1116
}
1117
}
1118
1119
if (result == MAX_SD59x18) {
1120
// Do the fixed-point division inline to save gas. The denominator is log2(10).
1121
unchecked {
1122
result = (log2(x) * SCALE) / 3_321928094887362347;
1123
}
1124
}
1125
}
1126
1127
/// @notice Calculates the binary logarithm of x.
1128
///
1129
/// @dev Based on the iterative approximation algorithm.
1130
/// https://en.wikipedia.org/wiki/Binary_logarithm#Iterative_approximation
1131
///
1132
/// Requirements:
1133
/// - x must be greater than zero.
1134
///
1135
/// Caveats:
1136
/// - The results are not perfectly accurate to the last decimal, due to the lossy precision of the iterative approximation.
1137
///
1138
/// @param x The signed 59.18-decimal fixed-point number for which to calculate the binary logarithm.
1139
/// @return result The binary logarithm as a signed 59.18-decimal fixed-point number.
1140
function log2(int256 x) internal pure returns (int256 result) {
1141
if (x <= 0) {
1142
revert PRBMathSD59x18__LogInputTooSmall(x);
1143
}
1144
unchecked {
1145
// This works because log2(x) = -log2(1/x).
1146
int256 sign;
1147
if (x >= SCALE) {
1148
sign = 1;
1149
} else {
1150
sign = -1;
1151
// Do the fixed-point inversion inline to save gas. The numerator is SCALE * SCALE.
1152
assembly {
1153
x := div(1000000000000000000000000000000000000, x)
1154
}
1155
}
1156
1157
// Calculate the integer part of the logarithm and add it to the result and finally calculate y = x * 2^(-n).
1158
uint256 n = PRBMath.mostSignificantBit(uint256(x / SCALE));
1159
1160
// The integer part of the logarithm as a signed 59.18-decimal fixed-point number. The operation can't overflow
1161
// because n is maximum 255, SCALE is 1e18 and sign is either 1 or -1.
1162
result = int256(n) * SCALE;
1163
1164
// This is y = x * 2^(-n).
1165
int256 y = x >> n;
1166
1167
// If y = 1, the fractional part is zero.
1168
if (y == SCALE) {
1169
return result * sign;
1170
}
1171
1172
// Calculate the fractional part via the iterative approximation.
1173
// The "delta >>= 1" part is equivalent to "delta /= 2", but shifting bits is faster.
1174
for (int256 delta = int256(HALF_SCALE); delta > 0; delta >>= 1) {
1175
y = (y * y) / SCALE;
1176
1177
// Is y^2 > 2 and so in the range [2,4)?
1178
if (y >= 2 * SCALE) {
1179
// Add the 2^(-m) factor to the logarithm.
1180
result += delta;
1181
1182
// Corresponds to z/2 on Wikipedia.
1183
y >>= 1;
1184
}
1185
}
1186
result *= sign;
1187
}
1188
}
1189
1190
/// @notice Multiplies two signed 59.18-decimal fixed-point numbers together, returning a new signed 59.18-decimal
1191
/// fixed-point number.
1192
///
1193
/// @dev Variant of "mulDiv" that works with signed numbers and employs constant folding, i.e. the denominator is
1194
/// always 1e18.
1195
///
1196
/// Requirements:
1197
/// - All from "PRBMath.mulDivFixedPoint".
1198
/// - None of the inputs can be MIN_SD59x18
1199
/// - The result must fit within MAX_SD59x18.
1200
///
1201
/// Caveats:
1202
/// - The body is purposely left uncommented; see the NatSpec comments in "PRBMath.mulDiv" to understand how this works.
1203
///
1204
/// @param x The multiplicand as a signed 59.18-decimal fixed-point number.
1205
/// @param y The multiplier as a signed 59.18-decimal fixed-point number.
1206
/// @return result The product as a signed 59.18-decimal fixed-point number.
1207
function mul(int256 x, int256 y) internal pure returns (int256 result) {
1208
if (x == MIN_SD59x18 || y == MIN_SD59x18) {
1209
revert PRBMathSD59x18__MulInputTooSmall();
1210
}
1211
1212
unchecked {
1213
uint256 ax;
1214
uint256 ay;
1215
ax = x < 0 ? uint256(-x) : uint256(x);
1216
ay = y < 0 ? uint256(-y) : uint256(y);
1217
1218
uint256 rAbs = PRBMath.mulDivFixedPoint(ax, ay);
1219
if (rAbs > uint256(MAX_SD59x18)) {
1220
revert PRBMathSD59x18__MulOverflow(rAbs);
1221
}
1222
1223
uint256 sx;
1224
uint256 sy;
1225
assembly {
1226
sx := sgt(x, sub(0, 1))
1227
sy := sgt(y, sub(0, 1))
1228
}
1229
result = sx ^ sy == 1 ? -int256(rAbs) : int256(rAbs);
1230
}
1231
}
1232
1233
/// @notice Returns PI as a signed 59.18-decimal fixed-point number.
1234
function pi() internal pure returns (int256 result) {
1235
result = 3_141592653589793238;
1236
}
1237
1238
/// @notice Raises x to the power of y.
1239
///
1240
/// @dev Based on the insight that x^y = 2^(log2(x) * y).
1241
///
1242
/// Requirements:
1243
/// - All from "exp2", "log2" and "mul".
1244
/// - z cannot be zero.
1245
///
1246
/// Caveats:
1247
/// - All from "exp2", "log2" and "mul".
1248
/// - Assumes 0^0 is 1.
1249
///
1250
/// @param x Number to raise to given power y, as a signed 59.18-decimal fixed-point number.
1251
/// @param y Exponent to raise x to, as a signed 59.18-decimal fixed-point number.
1252
/// @return result x raised to power y, as a signed 59.18-decimal fixed-point number.
1253
function pow(int256 x, int256 y) internal pure returns (int256 result) {
1254
if (x == 0) {
1255
result = y == 0 ? SCALE : int256(0);
1256
} else {
1257
result = exp2(mul(log2(x), y));
1258
}
1259
}
1260
1261
/// @notice Raises x (signed 59.18-decimal fixed-point number) to the power of y (basic unsigned integer) using the
1262
/// famous algorithm "exponentiation by squaring".
1263
///
1264
/// @dev See https://en.wikipedia.org/wiki/Exponentiation_by_squaring
1265
///
1266
/// Requirements:
1267
/// - All from "abs" and "PRBMath.mulDivFixedPoint".
1268
/// - The result must fit within MAX_SD59x18.
1269
///
1270
/// Caveats:
1271
/// - All from "PRBMath.mulDivFixedPoint".
1272
/// - Assumes 0^0 is 1.
1273
///
1274
/// @param x The base as a signed 59.18-decimal fixed-point number.
1275
/// @param y The exponent as an uint256.
1276
/// @return result The result as a signed 59.18-decimal fixed-point number.
1277
function powu(int256 x, uint256 y) internal pure returns (int256 result) {
1278
uint256 xAbs = uint256(abs(x));
1279
1280
// Calculate the first iteration of the loop in advance.
1281
uint256 rAbs = y & 1 > 0 ? xAbs : uint256(SCALE);
1282
1283
// Equivalent to "for(y /= 2; y > 0; y /= 2)" but faster.
1284
uint256 yAux = y;
1285
for (yAux >>= 1; yAux > 0; yAux >>= 1) {
1286
xAbs = PRBMath.mulDivFixedPoint(xAbs, xAbs);
1287
1288
// Equivalent to "y % 2 == 1" but faster.
1289
if (yAux & 1 > 0) {
1290
rAbs = PRBMath.mulDivFixedPoint(rAbs, xAbs);
1291
}
1292
}
1293
1294
// The result must fit within the 59.18-decimal fixed-point representation.
1295
if (rAbs > uint256(MAX_SD59x18)) {
1296
revert PRBMathSD59x18__PowuOverflow(rAbs);
1297
}
1298
1299
// Is the base negative and the exponent an odd number?
1300
bool isNegative = x < 0 && y & 1 == 1;
1301
result = isNegative ? -int256(rAbs) : int256(rAbs);
1302
}
1303
1304
/// @notice Returns 1 as a signed 59.18-decimal fixed-point number.
1305
function scale() internal pure returns (int256 result) {
1306
result = SCALE;
1307
}
1308
1309
/// @notice Calculates the square root of x, rounding down.
1310
/// @dev Uses the Babylonian method https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method.
1311
///
1312
/// Requirements:
1313
/// - x cannot be negative.
1314
/// - x must be less than MAX_SD59x18 / SCALE.
1315
///
1316
/// @param x The signed 59.18-decimal fixed-point number for which to calculate the square root.
1317
/// @return result The result as a signed 59.18-decimal fixed-point .
1318
function sqrt(int256 x) internal pure returns (int256 result) {
1319
unchecked {
1320
if (x < 0) {
1321
revert PRBMathSD59x18__SqrtNegativeInput(x);
1322
}
1323
if (x > MAX_SD59x18 / SCALE) {
1324
revert PRBMathSD59x18__SqrtOverflow(x);
1325
}
1326
// Multiply x by the SCALE to account for the factor of SCALE that is picked up when multiplying two signed
1327
// 59.18-decimal fixed-point numbers together (in this case, those two numbers are both the square root).
1328
result = int256(PRBMath.sqrt(uint256(x * SCALE)));
1329
}
1330
}
1331
1332
/// @notice Converts a signed 59.18-decimal fixed-point number to basic integer form, rounding down in the process.
1333
/// @param x The signed 59.18-decimal fixed-point number to convert.
1334
/// @return result The same number in basic integer form.
1335
function toInt(int256 x) internal pure returns (int256 result) {
1336
unchecked {
1337
result = x / SCALE;
1338
}
1339
}
1340
}
1341
1342
1343
// File contracts/Context.sol
1344
1345
// Original license: SPDX_License_Identifier: MIT
1346
// OpenZeppelin Contracts (last updated v4.9.4) (utils/Context.sol)
1347
1348
pragma solidity ^0.8.0;
1349
1350
/**
1351
* @dev Provides information about the current execution context, including the
1352
* sender of the transaction and its data. While these are generally available
1353
* via msg.sender and msg.data, they should not be accessed in such a direct
1354
* manner, since when dealing with meta-transactions the account sending and
1355
* paying for execution may not be the actual sender (as far as an application
1356
* is concerned).
1357
*
1358
* This contract is only required for intermediate, library-like contracts.
1359
*/
1360
abstract contract Context {
1361
function _msgSender() internal view virtual returns (address) {
1362
return msg.sender;
1363
}
1364
1365
function _msgData() internal view virtual returns (bytes calldata) {
1366
return msg.data;
1367
}
1368
1369
function _contextSuffixLength() internal view virtual returns (uint256) {
1370
return 0;
1371
}
1372
}
1373
1374
1375
// File contracts/Ownable.sol
1376
1377
// Original license: SPDX_License_Identifier: MIT
1378
// OpenZeppelin Contracts (last updated v4.9.0) (access/Ownable.sol)
1379
1380
pragma solidity ^0.8.0;
1381
1382
/**
1383
* @dev Contract module which provides a basic access control mechanism, where
1384
* there is an account (an owner) that can be granted exclusive access to
1385
* specific functions.
1386
*
1387
* By default, the owner account will be the one that deploys the contract. This
1388
* can later be changed with {transferOwnership}.
1389
*
1390
* This module is used through inheritance. It will make available the modifier
1391
* `onlyOwner`, which can be applied to your functions to restrict their use to
1392
* the owner.
1393
*/
1394
abstract contract Ownable is Context {
1395
address private _owner;
1396
1397
event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);
1398
1399
/**
1400
* @dev Initializes the contract setting the deployer as the initial owner.
1401
*/
1402
constructor() {
1403
_transferOwnership(_msgSender());
1404
}
1405
1406
/**
1407
* @dev Throws if called by any account other than the owner.
1408
*/
1409
modifier onlyOwner() {
1410
_checkOwner();
1411
_;
1412
}
1413
1414
/**
1415
* @dev Returns the address of the current owner.
1416
*/
1417
function owner() public view virtual returns (address) {
1418
return _owner;
1419
}
1420
1421
/**
1422
* @dev Throws if the sender is not the owner.
1423
*/
1424
function _checkOwner() internal view virtual {
1425
require(owner() == _msgSender(), "Ownable: caller is not the owner");
1426
}
1427
1428
/**
1429
* @dev Leaves the contract without owner. It will not be possible to call
1430
* `onlyOwner` functions. Can only be called by the current owner.
1431
*
1432
* NOTE: Renouncing ownership will leave the contract without an owner,
1433
* thereby disabling any functionality that is only available to the owner.
1434
*/
1435
function renounceOwnership() public virtual onlyOwner {
1436
_transferOwnership(address(0));
1437
}
1438
1439
/**
1440
* @dev Transfers ownership of the contract to a new account (`newOwner`).
1441
* Can only be called by the current owner.
1442
*/
1443
function transferOwnership(address newOwner) public virtual onlyOwner {
1444
require(newOwner != address(0), "Ownable: new owner is the zero address");
1445
_transferOwnership(newOwner);
1446
}
1447
1448
/**
1449
* @dev Transfers ownership of the contract to a new account (`newOwner`).
1450
* Internal function without access restriction.
1451
*/
1452
function _transferOwnership(address newOwner) internal virtual {
1453
address oldOwner = _owner;
1454
_owner = newOwner;
1455
emit OwnershipTransferred(oldOwner, newOwner);
1456
}
1457
}
1458
1459
1460
// File contracts/PhoneReputation.sol
1461
1462
// Original license: SPDX_License_Identifier: GPL-3.0
1463
pragma solidity 0.8.17;
1464
1465
1466
contract PhoneReputation is Ownable {
1467
using PRBMathSD59x18 for int;
1468
uint public scaling = 5e18;
1469
uint public k = 14;
1470
uint public c = 1e17; // 0.1 * 1e18
1471
uint public startBalance = 100;
1472
uint public verificationFee;
1473
1474
struct Vote {
1475
uint phone;
1476
int vote;
1477
uint userHistoryWeight;
1478
uint timestamp;
1479
}
1480
1481
struct Voter {
1482
uint posVotes;
1483
uint negVotes;
1484
uint balance;
1485
Vote[] votingHistory;
1486
}
1487
1488
enum RegisterStatus {
1489
None,
1490
PaidFee,
1491
Registered
1492
}
1493
1494
mapping(address => Voter) public voters;
1495
mapping(uint => mapping(address => Vote)) public voteFromUser;
1496
mapping(uint => address[]) public votersPerPhone;
1497
1498
mapping(uint => int[]) private reputationHistory;
1499
mapping(uint => uint[]) private tsReputationHistory;
1500
1501
mapping(address => RegisterStatus) public registerStatus;
1502
mapping(bytes32 => address) private registeredPhone;
1503
1504
event TopUpRequested(address indexed user, uint timestamp, uint value);
1505
event VoteSubmitted(
1506
address indexed voter,
1507
uint indexed phone,
1508
int vote,
1509
uint weight
1510
);
1511
event Registered(address indexed user, bytes32 indexed phoneHash);
1512
1513
constructor(uint _verificationFee) Ownable() {
1514
verificationFee = _verificationFee;
1515
}
1516
1517
function abs(int x) internal pure returns (uint) {
1518
return uint(x < 0 ? -x : x);
1519
}
1520
1521
function ratioToWeight(uint ratio) internal view returns (uint) {
1522
int exponent = int(k) * (int(c) - int(ratio));
1523
int e = exp(exponent);
1524
uint denom = uint(1e18 + e);
1525
return (1e18 * scaling) / denom;
1526
}
1527
1528
function exp(int x) internal pure returns (int) {
1529
return PRBMathSD59x18.exp(x);
1530
}
1531
1532
function requestTopUp() external payable {
1533
require(msg.value >= verificationFee, "Insufficient fee");
1534
require(
1535
registerStatus[msg.sender] == RegisterStatus.None,
1536
"Already requested"
1537
);
1538
1539
registerStatus[msg.sender] = RegisterStatus.PaidFee;
1540
emit TopUpRequested(msg.sender, block.timestamp, msg.value);
1541
}
1542
1543
function completeRegistration(
1544
address user,
1545
bytes32 phoneHash
1546
) external onlyOwner {
1547
require(registerStatus[user] == RegisterStatus.PaidFee, "Not eligible");
1548
require(
1549
registeredPhone[phoneHash] == address(0),
1550
"Phone already registered"
1551
);
1552
1553
registeredPhone[phoneHash] = user;
1554
registerStatus[user] = RegisterStatus.Registered;
1555
1556
voters[user].balance = startBalance;
1557
emit Registered(user, phoneHash);
1558
}
1559
1560
function voteForPhone(uint phone, int vote) external {
1561
require(
1562
registerStatus[msg.sender] == RegisterStatus.Registered,
1563
"Not registered"
1564
);
1565
require(vote != 0, "Zero vote");
1566
uint cost = abs(vote);
1567
1568
Voter storage v = voters[msg.sender];
1569
require(v.balance >= cost, "Not enough balance");
1570
1571
v.balance -= cost;
1572
if (vote > 0) {
1573
v.posVotes += 1;
1574
} else {
1575
v.negVotes += 1;
1576
}
1577
1578
uint historyWeight = getUserHistoryWeight(msg.sender);
1579
Vote memory newVote = Vote(phone, vote, historyWeight, block.timestamp);
1580
1581
if (voteFromUser[phone][msg.sender].timestamp == 0) {
1582
votersPerPhone[phone].push(msg.sender);
1583
} else {
1584
address[] storage votersList = votersPerPhone[phone];
1585
for (uint i = 0; i < votersList.length; i++) {
1586
if (votersList[i] == msg.sender) {
1587
votersList[i] = votersList[votersList.length - 1];
1588
votersList.pop();
1589
break;
1590
}
1591
}
1592
votersList.push(msg.sender);
1593
}
1594
1595
voteFromUser[phone][msg.sender] = newVote;
1596
1597
for (uint i = 0; i < v.votingHistory.length; i++) {
1598
if (v.votingHistory[i].phone == phone) {
1599
v.votingHistory[i] = v.votingHistory[
1600
v.votingHistory.length - 1
1601
];
1602
v.votingHistory.pop();
1603
break;
1604
}
1605
}
1606
v.votingHistory.push(newVote);
1607
1608
reputationHistory[phone].push(getReputation(phone));
1609
tsReputationHistory[phone].push(newVote.timestamp);
1610
1611
emit VoteSubmitted(msg.sender, phone, vote, historyWeight);
1612
}
1613
1614
function getUserHistoryWeight(address user) public view returns (uint) {
1615
Voter storage v = voters[user];
1616
if (v.posVotes == 0 && v.negVotes == 0) return 3e18;
1617
1618
uint minVotes = v.posVotes < v.negVotes ? v.posVotes : v.negVotes;
1619
uint maxVotes = v.posVotes > v.negVotes ? v.posVotes : v.negVotes;
1620
1621
uint ratio = (1e18 * minVotes) / maxVotes;
1622
return ratioToWeight(ratio);
1623
}
1624
1625
function getReputation(uint phone) public view returns (int) {
1626
address[] memory addresses = votersPerPhone[phone];
1627
uint len = addresses.length;
1628
if (len == 0) return 0;
1629
1630
int total = 0;
1631
1632
for (uint i = 0; i < len; i++) {
1633
Vote memory v = voteFromUser[phone][addresses[i]];
1634
uint idxRatio = (1e18 * (i + 1)) / len;
1635
uint timeWeight = ratioToWeight(idxRatio);
1636
uint sumWeight = v.userHistoryWeight + timeWeight;
1637
1638
int weightedVote = (v.vote * int(sumWeight)) / int(1e18);
1639
total += weightedVote;
1640
}
1641
1642
return total / int(len);
1643
}
1644
1645
function getReputationTimeline(
1646
uint phone
1647
)
1648
external
1649
view
1650
returns (int[] memory reputations, uint[] memory timestamps)
1651
{
1652
reputations = reputationHistory[phone];
1653
timestamps = tsReputationHistory[phone];
1654
}
1655
1656
function getVotesForPhone(
1657
uint phone
1658
) external view returns (Vote[] memory) {
1659
address[] memory addresses = votersPerPhone[phone];
1660
Vote[] memory result = new Vote[](addresses.length);
1661
for (uint i = 0; i < addresses.length; i++) {
1662
result[i] = voteFromUser[phone][addresses[i]];
1663
}
1664
return result;
1665
}
1666
1667
function getMyVotingHistory() external view returns (Vote[] memory) {
1668
return voters[msg.sender].votingHistory;
1669
}
1670
1671
function getRegisteredPhone(
1672
bytes32 phoneHash
1673
) external view returns (address) {
1674
return registeredPhone[phoneHash];
1675
}
1676
1677
function getRegisterStatus(
1678
address user
1679
) external view returns (RegisterStatus) {
1680
return registerStatus[user];
1681
}
1682
1683
function setVerificationFee(uint newFee) external onlyOwner {
1684
verificationFee = newFee;
1685
}
1686
1687
function setStartBalance(uint newBalance) external onlyOwner {
1688
startBalance = newBalance;
1689
}
1690
1691
function withdrawFees(address payable to) external onlyOwner {
1692
to.transfer(address(this).balance);
1693
}
1694
}
1695