Sitelet https://github.com/Vectorized/solady/commit/a07082e9b5d33b7b66031cb3d9ef50ccf64124e5
Skip to content

Commit a07082e

Browse files
atarparaatarpara
authored
🐞 Fix LazyShuffler.grow length validation (#1549)
* 🐞 Fix LazyShuffler.grow length validation * T
1 parent 314012e commit a07082e

3 files changed

Lines changed: 85 additions & 15 deletions

File tree

‎src/utils/LibPRNG.sol‎

Lines changed: 10 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,8 @@ library LibPRNG {
1313
/// @dev The initial length must be greater than zero and less than `2**32 - 1`.
1414
error InvalidInitialLazyShufflerLength();
1515

16-
/// @dev The new length must not be less than the current length.
16+
/// @dev The new length must not be less than the current length,
17+
/// and must be less than `2**32 - 1`.
1718
error InvalidNewLazyShufflerLength();
1819

1920
/// @dev The lazy shuffler has not been initialized.
@@ -343,19 +344,22 @@ library LibPRNG {
343344

344345
/// @dev Increases the length of `$`.
345346
/// Reverts if `$` has not been initialized.
347+
/// Reverts if `n` is less than the current length, or if `n >= 2**32 - 1`.
348+
/// Reverts if `n` crosses the entry width boundary at a length of 65535.
346349
function grow(LazyShuffler storage $, uint256 n) internal {
347350
/// @solidity memory-safe-assembly
348351
assembly {
349352
let state := sload($.slot) // The packed value at `$`.
350-
// If the new length is smaller than the old length, revert.
351-
if lt(n, shr(224, state)) {
352-
mstore(0x00, 0xbed37c6e) // `InvalidNewLazyShufflerLength()`.
353-
revert(0x1c, 0x04)
354-
}
355353
if iszero(state) {
356354
mstore(0x00, 0x1ead2566) // `LazyShufflerNotInitialized()`.
357355
revert(0x1c, 0x04)
358356
}
357+
let o := shr(224, state) // The old length.
358+
let limit := or(0xfffe, mul(0xffff0000, gt(o, 0xfffe)))
359+
if or(lt(n, o), gt(n, limit)) {
360+
mstore(0x00, 0xbed37c6e) // `InvalidNewLazyShufflerLength()`.
361+
revert(0x1c, 0x04)
362+
}
359363
sstore($.slot, or(shl(224, n), shr(32, shl(32, state))))
360364
}
361365
}

‎src/utils/g/LibPRNG.sol‎

Lines changed: 10 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -36,7 +36,8 @@ library LibPRNG {
3636
/// @dev The initial length must be greater than zero and less than `2**32 - 1`.
3737
error InvalidInitialLazyShufflerLength();
3838

39-
/// @dev The new length must not be less than the current length.
39+
/// @dev The new length must not be less than the current length,
40+
/// and must be less than `2**32 - 1`.
4041
error InvalidNewLazyShufflerLength();
4142

4243
/// @dev The lazy shuffler has not been initialized.
@@ -348,19 +349,22 @@ library LibPRNG {
348349

349350
/// @dev Increases the length of `$`.
350351
/// Reverts if `$` has not been initialized.
352+
/// Reverts if `n` is less than the current length, or if `n >= 2**32 - 1`.
353+
/// Reverts if `n` crosses the entry width boundary at a length of 65535.
351354
function grow(LazyShuffler storage $, uint256 n) internal {
352355
/// @solidity memory-safe-assembly
353356
assembly {
354357
let state := sload($.slot) // The packed value at `$`.
355-
// If the new length is smaller than the old length, revert.
356-
if lt(n, shr(224, state)) {
357-
mstore(0x00, 0xbed37c6e) // `InvalidNewLazyShufflerLength()`.
358-
revert(0x1c, 0x04)
359-
}
360358
if iszero(state) {
361359
mstore(0x00, 0x1ead2566) // `LazyShufflerNotInitialized()`.
362360
revert(0x1c, 0x04)
363361
}
362+
let o := shr(224, state) // The old length.
363+
let limit := or(0xfffe, mul(0xffff0000, gt(o, 0xfffe)))
364+
if or(lt(n, o), gt(n, limit)) {
365+
mstore(0x00, 0xbed37c6e) // `InvalidNewLazyShufflerLength()`.
366+
revert(0x1c, 0x04)
367+
}
364368
sstore($.slot, or(shl(224, n), shr(32, shl(32, state))))
365369
}
366370
}

‎test/LibPRNG.t.sol‎

Lines changed: 65 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -571,11 +571,14 @@ contract LibPRNGTest is SoladyTest {
571571
function testLazyShufflerRevertsOnGrowWithInvalidLength(uint256 n, uint256 nGrow) public {
572572
n = _bound(n, 1, 2 ** 32 - 2);
573573
this.lazyShufflerInitialize(n);
574-
nGrow = _bound(n, 0, 2 ** 32 - 2);
575-
if (nGrow < n) {
574+
nGrow = _bound(nGrow, 0, 2 ** 32 - 2);
575+
uint256 limit = n > 65534 ? 2 ** 32 - 2 : 65534;
576+
bool reverts = nGrow < n || nGrow > limit;
577+
if (reverts) {
576578
vm.expectRevert(LibPRNG.InvalidNewLazyShufflerLength.selector);
577579
}
578-
this.lazyShufflerGrow(n);
580+
this.lazyShufflerGrow(nGrow);
581+
assertEq(_lazyShuffler0.length(), reverts ? n : nGrow);
579582
}
580583

581584
function testLazyShufflerRevertsOnDoubleInit() public {
@@ -620,4 +623,63 @@ contract LibPRNGTest is SoladyTest {
620623
function lazyShuffler1Get(uint256 i) public view returns (uint256) {
621624
return _lazyShuffler1.get(i);
622625
}
626+
627+
function testLazyShufflerRevertsOnGrowAcrossWidthBoundary() public {
628+
_lazyShuffler0.initialize(2);
629+
_lazyShuffler0.next(0);
630+
vm.expectRevert(LibPRNG.InvalidNewLazyShufflerLength.selector);
631+
this.lazyShufflerGrow(65535);
632+
}
633+
634+
function testLazyShufflerRevertsOnGrowAcrossWidthBoundaryUndrawn() public {
635+
_lazyShuffler0.initialize(2);
636+
vm.expectRevert(LibPRNG.InvalidNewLazyShufflerLength.selector);
637+
this.lazyShufflerGrow(65535);
638+
}
639+
640+
// `grow` had no upper bound check, so the length silently truncated to zero.
641+
function testLazyShufflerRevertsOnGrowOutOfRange(uint256 n) public {
642+
_lazyShuffler0.initialize(10);
643+
n = _bound(n, 2 ** 32 - 1, type(uint256).max);
644+
vm.expectRevert(LibPRNG.InvalidNewLazyShufflerLength.selector);
645+
this.lazyShufflerGrow(n);
646+
assertEq(_lazyShuffler0.length(), 10);
647+
}
648+
649+
function testLazyShufflerGrowWithinSameWidth() public {
650+
_lazyShuffler0.initialize(2);
651+
uint256 first = _lazyShuffler0.next(0);
652+
_lazyShuffler0.grow(1000);
653+
assertEq(_lazyShuffler0.get(0), first);
654+
assertLt(_lazyShuffler0.get(0), 1000);
655+
}
656+
657+
function testLazyShufflerGrowWithinWideWidth() public {
658+
_lazyShuffler0.initialize(70000);
659+
uint256 first = _lazyShuffler0.next(0);
660+
_lazyShuffler0.grow(200000);
661+
assertEq(_lazyShuffler0.get(0), first);
662+
assertLt(_lazyShuffler0.get(0), 200000);
663+
}
664+
665+
// A 32-bit shuffler still draws each value at most once across a grow.
666+
function testLazyShufflerWideProducesNoDuplicatesAcrossGrow() public {
667+
_lazyShuffler0.initialize(65535);
668+
uint256[] memory seen = new uint256[](8);
669+
unchecked {
670+
for (uint256 i; i != 4; ++i) {
671+
seen[i] = _lazyShuffler0.next(_random());
672+
}
673+
_lazyShuffler0.grow(65600);
674+
for (uint256 i = 4; i != 8; ++i) {
675+
seen[i] = _lazyShuffler0.next(_random());
676+
}
677+
LibSort.sort(seen);
678+
LibSort.uniquifySorted(seen);
679+
assertEq(seen.length, 8);
680+
for (uint256 i; i != 8; ++i) {
681+
assertLt(seen[i], 65600);
682+
}
683+
}
684+
}
623685
}

0 commit comments

Comments
 (0)