1
// SPDX-License-Identifier: MIT
2
pragma solidity ^0.8.21;
3

4
import { ICourse } from "src/interfaces/ICourse.sol";
5

6
interface FactorialLike {
7
    function perform(uint256 input) external pure returns (uint256 output);
8
}
9

10
contract Factorial is ICourse {
11
    /// @inheritdoc ICourse
12
    function name() external pure returns (string memory) {
13
        return "Factorial";
14
    }
15

16
    /// @inheritdoc ICourse
17
    function run(address target, uint256 seed) external view returns (uint32 usedGas) {
18
        /// @solidity memory-safe-assembly
19
        assembly {
20
            function verifyReturns(target_, input_, output_) {
21
                mstore(0x00, 0xd097bc0d) // `perform(uint256)`.
22
                mstore(0x20, input_)
23
                let success_ := staticcall(gas(), target_, 0x1c, 0x24, 0x00, 0x20)
24
                success_ := and(gt(returndatasize(), 0x1f), success_)
25
                success_ := and(eq(mload(0x00), output_), success_)
26
                if iszero(success_) {
27
                    mstore(0x00, 0x62cebecf) // `IncorrectSolution()`.
28
                    revert(0x1c, 0x04)
29
                }
30
            }
31

32
            function verifyReverts(target_, input_) {
33
                mstore(0x00, 0xd097bc0d) // `perform(uint256)`.
34
                mstore(0x20, input_)
35
                if staticcall(gas(), target_, 0x1c, 0x24, 0x00, 0x00) {
36
                    mstore(0x00, 0x62cebecf) // `IncorrectSolution()`.
37
                    revert(0x1c, 0x04)
38
                }
39
            }
40

41
            // From https://github.com/Vectorized/solady/blob/main/src/utils/LibPRNG.sol.
42
            function shuffle(a_, seed_) -> _nextSeed {
43
                let n_ := mload(a_)
44
                let w_ := not(0)
45
                mstore(0x00, seed_)
46
                let r_ := keccak256(0x00, 0x20)
47
                if n_ {
48
                    for { a_ := add(a_, 0x20) } 1 { } {
49
                        r_ :=
50
                            mulmod(
51
                                r_,
52
                                0x100000000000000000000000000000051,
53
                                0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff43
54
                            )
55
                        {
56
                            let j_ := add(a_, shl(5, mod(and(shr(64, r_), 0xffffffff), n_)))
57
                            n_ := add(n_, w_)
58
                            if iszero(n_) { break }
59

60
                            let i_ := add(a_, shl(5, n_))
61
                            let t := mload(i_)
62
                            mstore(i_, mload(j_))
63
                            mstore(j_, t)
64
                        }
65

66
                        {
67
                            let j_ := add(a_, shl(5, mod(and(shr(32, r_), 0xffffffff), n_)))
68
                            n_ := add(n_, w_)
69
                            if iszero(n_) { break }
70

71
                            let i_ := add(a_, shl(5, n_))
72
                            let t := mload(i_)
73
                            mstore(i_, mload(j_))
74
                            mstore(j_, t)
75
                        }
76
                    }
77
                }
78
                mstore(0x20, seed_)
79
                _nextSeed := keccak256(0x00, 0x40)
80
            }
81

82
            function mallocUint256Array(length_) -> _result {
83
                _result := mload(0x40)
84
                mstore(_result, length_)
85
                mstore(0x40, add(add(_result, 0x20), shl(5, length_)))
86
            }
87

88
            function mallocRange(from_, to_) -> _result {
89
                let length_ := sub(to_, from_)
90
                _result := mallocUint256Array(length_)
91
                let o_ := add(_result, 0x20)
92
                for { let i_ := 0 } iszero(eq(i_, length_)) { i_ := add(i_, 1) } {
93
                    mstore(add(o_, shl(5, i_)), i_)
94
                }
95
            }
96

97
            function testRange(target_, solutions_, from_, to_, seed_) -> _nextSeed {
98
                let length_ := sub(to_, from_)
99
                let indices_ := mallocRange(from_, to_)
100
                _nextSeed := shuffle(indices_, seed_)
101
                let indicesOffset_ := add(indices_, 0x20)
102
                let solutionsOffset_ := add(solutions_, 0x20)
103
                for { let i_ := 0 } iszero(eq(i_, length_)) { i_ := add(i_, 1) } {
104
                    let input_ := mload(add(indicesOffset_, shl(5, i_)))
105
                    let output_ := mload(add(solutionsOffset_, shl(5, input_)))
106
                    verifyReturns(target_, input_, output_)
107
                }
108
            }
109

110
            let preGas := gas()
111
            let m := mload(0x40)
112

113
            let solutions := mallocUint256Array(58)
114
            let solution := 1
115
            let solutionsOffset := add(solutions, 0x20)
116
            for { let j := 0 } 1 { } {
117
                mstore(add(solutionsOffset, shl(5, j)), solution)
118
                j := add(j, 1)
119
                solution := mul(solution, j)
120
                if eq(j, 58) { break }
121
            }
122

123
            seed := testRange(target, solutions, 0, 58, seed)
124
            seed := testRange(target, solutions, 0, 16, seed)
125

126
            for { let j := 58 } iszero(eq(j, 70)) { j := add(j, 1) } {
127
                verifyReverts(target, j)
128
                verifyReverts(target, shl(128, j))
129
                verifyReverts(target, shl(248, j))
130
            }
131

132
            seed := testRange(target, solutions, 0, 8, seed)
133
            seed := testRange(target, solutions, 0, 32, seed)
134

135
            calldatacopy(m, 0x00, shl(8, extcodesize(target)))
136

137
            usedGas := sub(preGas, gas())
138
        }
139
    }
140
}