0
# Mathematical Utilities
1

2
Comprehensive mathematical operations, safe type conversions, and efficient data structures for smart contract computations including precision arithmetic, data manipulation, and storage optimization.
3

4
## Capabilities
5

6
### Core Mathematical Operations
7

8
Standard mathematical functions with overflow protection, precision control, and gas optimization.
9

10
```solidity { .api }
11
/**
12
 * @dev Standard math utilities with advanced arithmetic operations
13
 */
14
library Math {
15
    /**
16
     * @dev Rounding direction for mathematical operations
17
     */
18
    enum Rounding {
19
        Floor,  // Round toward zero
20
        Ceil,   // Round away from zero  
21
        Trunc,  // Round toward negative infinity
22
        Expand  // Round away from negative infinity
23
    }
24
    
25
    /**
26
     * @dev Returns maximum of two values
27
     */
28
    function max(uint256 a, uint256 b) internal pure returns (uint256);
29
    
30
    /**
31
     * @dev Returns minimum of two values  
32
     */
33
    function min(uint256 a, uint256 b) internal pure returns (uint256);
34
    
35
    /**
36
     * @dev Returns overflow-safe average of two values
37
     */
38
    function average(uint256 a, uint256 b) internal pure returns (uint256);
39
    
40
    /**
41
     * @dev Integer square root using Newton's method
42
     */
43
    function sqrt(uint256 a) internal pure returns (uint256);
44
    function sqrt(uint256 a, Rounding rounding) internal pure returns (uint256);
45
    
46
    /**
47
     * @dev High-precision multiplication and division
48
     */
49
    function mulDiv(uint256 x, uint256 y, uint256 denominator) internal pure returns (uint256);
50
    function mulDiv(uint256 x, uint256 y, uint256 denominator, Rounding rounding) internal pure returns (uint256);
51
    
52
    /**
53
     * @dev Ceiling division avoiding overflow
54
     */
55
    function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256);
56
    
57
    /**
58
     * @dev Logarithm functions with optional rounding
59
     */
60
    function log2(uint256 value) internal pure returns (uint256);
61
    function log2(uint256 value, Rounding rounding) internal pure returns (uint256);
62
    function log10(uint256 value) internal pure returns (uint256);
63
    function log256(uint256 value) internal pure returns (uint256);
64
    
65
    /**
66
     * @dev Modular arithmetic operations
67
     */
68
    function invMod(uint256 a, uint256 n) internal pure returns (uint256);
69
    function modExp(uint256 b, uint256 e, uint256 m) internal pure returns (uint256);
70
    
71
    /**
72
     * @dev Extended precision arithmetic
73
     */
74
    function add512(uint256 a, uint256 b) internal pure returns (uint256 high, uint256 low);
75
    function mul512(uint256 a, uint256 b) internal pure returns (uint256 high, uint256 low);
76
    
77
    /**
78
     * @dev Safe arithmetic with success flags
79
     */
80
    function tryAdd(uint256 a, uint256 b) internal pure returns (bool success, uint256 result);
81
    function trySub(uint256 a, uint256 b) internal pure returns (bool success, uint256 result);
82
    function tryMul(uint256 a, uint256 b) internal pure returns (bool success, uint256 result);
83
    function tryDiv(uint256 a, uint256 b) internal pure returns (bool success, uint256 result);
84
    
85
    /**
86
     * @dev Branchless ternary operation for gas optimization
87
     */
88
    function ternary(bool condition, uint256 a, uint256 b) internal pure returns (uint256);
89
}
90

91
/**
92
 * @dev Signed math utilities for int256 operations
93
 */
94
library SignedMath {
95
    /**
96
     * @dev Returns maximum of two signed values
97
     */
98
    function max(int256 a, int256 b) internal pure returns (int256);
99
    
100
    /**
101
     * @dev Returns minimum of two signed values
102
     */
103
    function min(int256 a, int256 b) internal pure returns (int256);
104
    
105
    /**
106
     * @dev Returns overflow-safe average using bit manipulation
107
     */
108
    function average(int256 a, int256 b) internal pure returns (int256);
109
    
110
    /**
111
     * @dev Returns absolute value using bit twiddling
112
     */
113
    function abs(int256 n) internal pure returns (uint256);
114
    
115
    /**
116
     * @dev Branchless ternary for signed integers
117
     */
118
    function ternary(bool condition, int256 a, int256 b) internal pure returns (int256);
119
}
120
```
121

122
### Safe Type Conversions
123

124
Comprehensive type casting with overflow protection for all integer types.
125

126
```solidity { .api }
127
/**
128
 * @dev Safe type conversion library with overflow detection
129
 */
130
library SafeCast {
131
    /**
132
     * @dev Converts uint256 to smaller unsigned integer types
133
     */
134
    function toUint248(uint256 value) internal pure returns (uint248);
135
    function toUint240(uint256 value) internal pure returns (uint240);
136
    function toUint232(uint256 value) internal pure returns (uint232);
137
    function toUint224(uint256 value) internal pure returns (uint224);
138
    function toUint216(uint256 value) internal pure returns (uint216);
139
    function toUint208(uint256 value) internal pure returns (uint208);
140
    function toUint200(uint256 value) internal pure returns (uint200);
141
    function toUint192(uint256 value) internal pure returns (uint192);
142
    function toUint184(uint256 value) internal pure returns (uint184);
143
    function toUint176(uint256 value) internal pure returns (uint176);
144
    function toUint168(uint256 value) internal pure returns (uint168);
145
    function toUint160(uint256 value) internal pure returns (uint160);
146
    function toUint152(uint256 value) internal pure returns (uint152);
147
    function toUint144(uint256 value) internal pure returns (uint144);
148
    function toUint136(uint256 value) internal pure returns (uint136);
149
    function toUint128(uint256 value) internal pure returns (uint128);
150
    function toUint120(uint256 value) internal pure returns (uint120);
151
    function toUint112(uint256 value) internal pure returns (uint112);
152
    function toUint104(uint256 value) internal pure returns (uint104);
153
    function toUint96(uint256 value) internal pure returns (uint96);
154
    function toUint88(uint256 value) internal pure returns (uint88);
155
    function toUint80(uint256 value) internal pure returns (uint80);
156
    function toUint72(uint256 value) internal pure returns (uint72);
157
    function toUint64(uint256 value) internal pure returns (uint64);
158
    function toUint56(uint256 value) internal pure returns (uint56);
159
    function toUint48(uint256 value) internal pure returns (uint48);
160
    function toUint40(uint256 value) internal pure returns (uint40);
161
    function toUint32(uint256 value) internal pure returns (uint32);
162
    function toUint24(uint256 value) internal pure returns (uint24);
163
    function toUint16(uint256 value) internal pure returns (uint16);
164
    function toUint8(uint256 value) internal pure returns (uint8);
165
    
166
    /**
167
     * @dev Converts uint256 to signed integer types
168
     */
169
    function toInt256(uint256 value) internal pure returns (int256);
170
    function toInt248(int256 value) internal pure returns (int248);
171
    function toInt240(int256 value) internal pure returns (int240);
172
    function toInt232(int256 value) internal pure returns (int232);
173
    function toInt224(int256 value) internal pure returns (int224);
174
    function toInt216(int256 value) internal pure returns (int216);
175
    function toInt208(int256 value) internal pure returns (int208);
176
    function toInt200(int256 value) internal pure returns (int200);
177
    function toInt192(int256 value) internal pure returns (int192);
178
    function toInt184(int256 value) internal pure returns (int184);
179
    function toInt176(int256 value) internal pure returns (int176);
180
    function toInt168(int256 value) internal pure returns (int168);
181
    function toInt160(int256 value) internal pure returns (int160);
182
    function toInt152(int256 value) internal pure returns (int152);
183
    function toInt144(int256 value) internal pure returns (int144);
184
    function toInt136(int256 value) internal pure returns (int136);
185
    function toInt128(int256 value) internal pure returns (int128);
186
    function toInt120(int256 value) internal pure returns (int120);
187
    function toInt112(int256 value) internal pure returns (int112);
188
    function toInt104(int256 value) internal pure returns (int104);
189
    function toInt96(int256 value) internal pure returns (int96);
190
    function toInt88(int256 value) internal pure returns (int88);
191
    function toInt80(int256 value) internal pure returns (int80);
192
    function toInt72(int256 value) internal pure returns (int72);
193
    function toInt64(int256 value) internal pure returns (int64);
194
    function toInt56(int256 value) internal pure returns (int56);
195
    function toInt48(int256 value) internal pure returns (int48);
196
    function toInt40(int256 value) internal pure returns (int40);
197
    function toInt32(int256 value) internal pure returns (int32);
198
    function toInt24(int256 value) internal pure returns (int24);
199
    function toInt16(int256 value) internal pure returns (int16);
200
    function toInt8(int256 value) internal pure returns (int8);
201
    
202
    /**
203
     * @dev Converts signed to unsigned integer
204
     */
205
    function toUint256(int256 value) internal pure returns (uint256);
206
    
207
    /**
208
     * @dev Efficient boolean to uint256 conversion
209
     */
210
    function toUint(bool b) internal pure returns (uint256 u);
211
}
212
```
213

214
### String and Data Manipulation
215

216
String operations with mathematical parsing and data conversion utilities.
217

218
```solidity { .api }
219
/**
220
 * @dev String manipulation library with mathematical parsing
221
 */
222
library Strings {
223
    /**
224
     * @dev Convert integers to string representation
225
     */
226
    function toString(uint256 value) internal pure returns (string memory);
227
    function toStringSigned(int256 value) internal pure returns (string memory);
228
    
229
    /**
230
     * @dev Convert to hexadecimal representation
231
     */
232
    function toHexString(uint256 value) internal pure returns (string memory);
233
    function toHexString(uint256 value, uint256 length) internal pure returns (string memory);
234
    function toHexString(address addr) internal pure returns (string memory);
235
    
236
    /**
237
     * @dev EIP-55 checksummed address representation
238
     */
239
    function toChecksumHexString(address addr) internal pure returns (string memory);
240
    
241
    /**
242
     * @dev Parse string to integer with bounds checking
243
     */
244
    function parseUint(string memory input, uint256 min, uint256 max) internal pure returns (uint256);
245
    function parseInt(string memory input, int256 min, int256 max) internal pure returns (int256);
246
    
247
    /**
248
     * @dev Parse hexadecimal strings
249
     */
250
    function parseHexUint(bytes memory input) internal pure returns (uint256);
251
    function parseAddress(string memory input) internal pure returns (address);
252
    
253
    /**
254
     * @dev String comparison
255
     */
256
    function equal(string memory a, string memory b) internal pure returns (bool);
257
    
258
    /**
259
     * @dev JSON escaping for safe string output
260
     */
261
    function escapeJSON(string memory input) internal pure returns (string memory);
262
}
263

264
/**
265
 * @dev Address utility library for safe operations
266
 */
267
library Address {
268
    /**
269
     * @dev Returns true if account is a contract
270
     */
271
    function isContract(address account) internal view returns (bool);
272
    
273
    /**
274
     * @dev Safe ETH transfer with gas limit protection
275
     */
276
    function sendValue(address payable recipient, uint256 amount) internal;
277
    
278
    /**
279
     * @dev Safe contract calls with error propagation
280
     */
281
    function functionCall(address target, bytes memory data) internal returns (bytes memory);
282
    function functionCallWithValue(address target, bytes memory data, uint256 value) internal returns (bytes memory);
283
    function functionStaticCall(address target, bytes memory data) internal view returns (bytes memory);
284
    function functionDelegateCall(address target, bytes memory data) internal returns (bytes memory);
285
    
286
    /**
287
     * @dev Verify and bubble up call results
288
     */
289
    function verifyCallResult(bool success, bytes memory returndata) internal pure returns (bytes memory);
290
}
291

292
/**
293
 * @dev Enhanced array operations with mathematical algorithms
294
 */
295
library Arrays {
296
    /**
297
     * @dev QuickSort implementation for different array types
298
     */
299
    function sort(uint256[] memory array) internal pure;
300
    function sort(address[] memory array) internal pure;
301
    function sort(bytes32[] memory array) internal pure;
302
    
303
    /**
304
     * @dev Binary search operations (O(log n))
305
     */
306
    function lowerBound(uint256[] storage array, uint256 element) internal view returns (uint256);
307
    function upperBound(uint256[] storage array, uint256 element) internal view returns (uint256);
308
    function lowerBoundMemory(uint256[] memory array, uint256 element) internal pure returns (uint256);
309
    function upperBoundMemory(uint256[] memory array, uint256 element) internal pure returns (uint256);
310
    
311
    /**
312
     * @dev Unsafe array access without bounds checking
313
     */
314
    function unsafeAccess(address[] storage arr, uint256 pos) internal pure returns (StorageSlot.AddressSlot storage);
315
    function unsafeAccess(bytes32[] storage arr, uint256 pos) internal pure returns (StorageSlot.Bytes32Slot storage);
316
    function unsafeAccess(uint256[] storage arr, uint256 pos) internal pure returns (StorageSlot.Uint256Slot storage);
317
    
318
    /**
319
     * @dev Memory array access without bounds checking
320
     */
321
    function unsafeMemoryAccess(uint256[] memory arr, uint256 pos) internal pure returns (uint256 res);
322
    function unsafeMemoryAccess(address[] memory arr, uint256 pos) internal pure returns (address res);
323
    function unsafeMemoryAccess(bytes32[] memory arr, uint256 pos) internal pure returns (bytes32 res);
324
}
325
```
326

327
### Efficient Data Structures
328

329
High-performance data structures optimized for smart contract storage and gas efficiency.
330

331
```solidity { .api }
332
/**
333
 * @dev Efficient boolean storage using bit manipulation
334
 */
335
library BitMaps {
336
    struct BitMap {
337
        mapping(uint256 => uint256) _data;
338
    }
339
    
340
    /**
341
     * @dev Get boolean value at index
342
     */
343
    function get(BitMap storage bitmap, uint256 index) internal view returns (bool);
344
    
345
    /**
346
     * @dev Set boolean value at index
347
     */
348
    function setTo(BitMap storage bitmap, uint256 index, bool value) internal;
349
    function set(BitMap storage bitmap, uint256 index) internal;
350
    function unset(BitMap storage bitmap, uint256 index) internal;
351
}
352

353
/**
354
 * @dev Historical value tracking with binary search optimization
355
 */
356
library Checkpoints {
357
    struct Trace224 {
358
        Checkpoint224[] _checkpoints;
359
    }
360
    
361
    struct Checkpoint224 {
362
        uint32 _key;
363
        uint224 _value;
364
    }
365
    
366
    /**
367
     * @dev Push new checkpoint with ordering validation
368
     */
369
    function push(Trace224 storage self, uint32 key, uint224 value) internal returns (uint224, uint224);
370
    
371
    /**
372
     * @dev Binary search for historical values
373
     */
374
    function lowerLookup(Trace224 storage self, uint32 key) internal view returns (uint224);
375
    function upperLookup(Trace224 storage self, uint32 key) internal view returns (uint224);
376
    function upperLookupRecent(Trace224 storage self, uint32 key) internal view returns (uint224);
377
    
378
    /**
379
     * @dev Get latest value and checkpoint
380
     */
381
    function latest(Trace224 storage self) internal view returns (uint224);
382
    function latestCheckpoint(Trace224 storage self) internal view returns (bool exists, uint32 key, uint224 value);
383
    
384
    /**
385
     * @dev Get checkpoint at specific position
386
     */
387
    function at(Trace224 storage self, uint32 pos) internal view returns (Checkpoint224 memory);
388
    function length(Trace224 storage self) internal view returns (uint256);
389
}
390

391
/**
392
 * @dev Double-ended queue with O(1) operations
393
 */
394
library DoubleEndedQueue {
395
    struct Bytes32Deque {
396
        uint128 _begin;
397
        uint128 _end;
398
        mapping(uint128 => bytes32) _data;
399
    }
400
    
401
    /**
402
     * @dev O(1) queue operations
403
     */
404
    function pushBack(Bytes32Deque storage deque, bytes32 value) internal;
405
    function popBack(Bytes32Deque storage deque) internal returns (bytes32 value);
406
    function pushFront(Bytes32Deque storage deque, bytes32 value) internal;
407
    function popFront(Bytes32Deque storage deque) internal returns (bytes32 value);
408
    
409
    /**
410
     * @dev O(1) access operations
411
     */
412
    function front(Bytes32Deque storage deque) internal view returns (bytes32 value);
413
    function back(Bytes32Deque storage deque) internal view returns (bytes32 value);
414
    function at(Bytes32Deque storage deque, uint256 index) internal view returns (bytes32 value);
415
    
416
    /**
417
     * @dev State management
418
     */
419
    function length(Bytes32Deque storage deque) internal view returns (uint256);
420
    function empty(Bytes32Deque storage deque) internal view returns (bool);
421
    function clear(Bytes32Deque storage deque) internal;
422
}
423

424
/**
425
 * @dev Enumerable set with O(1) operations
426
 */
427
library EnumerableSet {
428
    struct Set {
429
        bytes32[] _values;
430
        mapping(bytes32 => uint256) _positions;
431
    }
432
    
433
    /**
434
     * @dev O(1) set operations
435
     */
436
    function add(Set storage set, bytes32 value) internal returns (bool);
437
    function remove(Set storage set, bytes32 value) internal returns (bool);
438
    function contains(Set storage set, bytes32 value) internal view returns (bool);
439
    
440
    /**
441
     * @dev Enumeration support
442
     */
443
    function length(Set storage set) internal view returns (uint256);
444
    function at(Set storage set, uint256 index) internal view returns (bytes32);
445
    function values(Set storage set) internal view returns (bytes32[] memory);
446
    
447
    // Typed variants for common types
448
    struct Bytes32Set { Set _inner; }
449
    struct AddressSet { Set _inner; }
450
    struct UintSet { Set _inner; }
451
}
452

453
/**
454
 * @dev Binary heap for priority queue operations
455
 */
456
library Heap {
457
    struct Uint256Heap {
458
        uint256[] _data;
459
        function(uint256, uint256) view returns (bool) _comp;
460
    }
461
    
462
    /**
463
     * @dev O(1) access to highest priority element
464
     */
465
    function peek(Uint256Heap storage heap) internal view returns (uint256);
466
    
467
    /**
468
     * @dev O(log n) insertion and removal
469
     */
470
    function push(Uint256Heap storage heap, uint256 value) internal;
471
    function pop(Uint256Heap storage heap) internal returns (uint256);
472
    function replace(Uint256Heap storage heap, uint256 newValue) internal returns (uint256);
473
    
474
    /**
475
     * @dev Heap state management
476
     */
477
    function length(Uint256Heap storage heap) internal view returns (uint256);
478
    function empty(Uint256Heap storage heap) internal view returns (bool);
479
    function clear(Uint256Heap storage heap) internal;
480
}
481
```
482

483
### Specialized Utilities
484

485
Additional utilities for bit manipulation, packing, and advanced data operations.
486

487
```solidity { .api }
488
/**
489
 * @dev Bit packing utilities for storage optimization
490
 */
491
library Packing {
492
    /**
493
     * @dev Pack multiple values into single storage slot
494
     */
495
    function pack_1_31(bytes1 left, bytes31 right) internal pure returns (bytes32 result);
496
    function pack_2_30(bytes2 left, bytes30 right) internal pure returns (bytes32 result);
497
    function pack_4_28(bytes4 left, bytes28 right) internal pure returns (bytes32 result);
498
    function pack_8_24(bytes8 left, bytes24 right) internal pure returns (bytes32 result);
499
    function pack_16_16(bytes16 left, bytes16 right) internal pure returns (bytes32 result);
500
    
501
    /**
502
     * @dev Extract packed values from storage slot
503
     */
504
    function extract_1_31(bytes32 packed) internal pure returns (bytes1 left, bytes31 right);
505
    function extract_2_30(bytes32 packed) internal pure returns (bytes2 left, bytes30 right);
506
    function extract_4_28(bytes32 packed) internal pure returns (bytes4 left, bytes28 right);
507
    function extract_8_24(bytes32 packed) internal pure returns (bytes8 left, bytes24 right);
508
    function extract_16_16(bytes32 packed) internal pure returns (bytes16 left, bytes16 right);
509
}
510

511
/**
512
 * @dev Bytes manipulation with mathematical search
513
 */
514
library Bytes {
515
    /**
516
     * @dev Search operations in bytes
517
     */
518
    function indexOf(bytes memory buffer, bytes1 needle) internal pure returns (uint256);
519
    function indexOf(bytes memory buffer, bytes memory needle) internal pure returns (uint256);
520
    function lastIndexOf(bytes memory buffer, bytes1 needle) internal pure returns (uint256);
521
    
522
    /**
523
     * @dev Extract substring from bytes
524
     */
525
    function slice(bytes memory buffer, uint256 start, uint256 length) internal pure returns (bytes memory);
526
}
527

528
/**
529
 * @dev Comparator functions for sorting algorithms
530
 */
531
library Comparators {
532
    /**
533
     * @dev Standard comparators for different types
534
     */
535
    function lt(uint256 a, uint256 b) internal pure returns (bool);
536
    function gt(uint256 a, uint256 b) internal pure returns (bool);
537
}
538
```
539

540
## Types
541

542
```solidity { .api }
543
/**
544
 * @dev Math operation rounding directions
545
 */
546
enum Rounding {
547
    Floor,  // Round toward zero (default)
548
    Ceil,   // Round away from zero
549
    Trunc,  // Round toward negative infinity
550
    Expand  // Round away from negative infinity
551
}
552

553
/**
554
 * @dev Custom error types for safe operations
555
 */
556
error SafeCastOverflowedUintDowncast(uint8 bits, uint256 value);
557
error SafeCastOverflowedIntToUint(int256 value);
558
error SafeCastOverflowedIntDowncast(uint8 bits, int256 value);
559
error SafeCastOverflowedUintToInt(uint256 value);
560

561
/**
562
 * @dev Checkpoint structure for historical tracking
563
 */
564
struct Checkpoint224 {
565
    uint32 _key;
566
    uint224 _value;
567
}
568

569
struct Checkpoint208 {
570
    uint48 _key;
571
    uint208 _value;
572
}
573

574
struct Checkpoint160 {
575
    uint96 _key;
576
    uint160 _value;
577
}
578
```
579

580
**Usage Example:**
581

582
```solidity
583
import "@openzeppelin/contracts/utils/math/Math.sol";
584
import "@openzeppelin/contracts/utils/math/SafeCast.sol";
585
import "@openzeppelin/contracts/utils/structs/BitMaps.sol";
586

587
contract MathExample {
588
    using Math for uint256;
589
    using SafeCast for uint256;
590
    using BitMaps for BitMaps.BitMap;
591
    
592
    BitMaps.BitMap private permissions;
593
    
594
    function calculateReward(uint256 amount, uint256 rate) external pure returns (uint256) {
595
        // High precision calculation
596
        return Math.mulDiv(amount, rate, 10000);
597
    }
598
    
599
    function safeConvert(uint256 largeValue) external pure returns (uint128) {
600
        // Safe type conversion with overflow protection
601
        return largeValue.toUint128();
602
    }
603
    
604
    function setPermission(uint256 userId, bool hasPermission) external {
605
        // Efficient boolean storage
606
        permissions.setTo(userId, hasPermission);
607
    }
608
}
609
```