test_worst_shifts()

Documentation for tests/zkevm/test_worst_compute.py::test_worst_shifts@64f949d0.

Generate fixtures for these test cases for Prague with:

fill -v tests/zkevm/test_worst_compute.py::test_worst_shifts --fork Prague

Test running a block with as many shift instructions with non-trivial arguments. This test generates left-right pairs of shifts to avoid zeroing the argument. The shift amounts are randomly pre-selected from the constant pool of 15 values on the stack.

Source code in tests/zkevm/test_worst_compute.py

@pytest.mark.valid_from("Cancun")
@pytest.mark.parametrize("shift_right", [Op.SHR, Op.SAR])
def test_worst_shifts(
    state_test: StateTestFiller,
    pre: Alloc,
    fork: Fork,
    shift_right: Op,
):
    """
    Test running a block with as many shift instructions with non-trivial arguments.
    This test generates left-right pairs of shifts to avoid zeroing the argument.
    The shift amounts are randomly pre-selected from the constant pool of 15 values on the stack.
    """
    max_code_size = fork.max_code_size()

    def to_signed(x):
        return x if x < 2**255 else x - 2**256

    def to_unsigned(x):
        return x if x >= 0 else x + 2**256

    def shr(x, s):
        return x >> s

    def shl(x, s):
        return x << s

    def sar(x, s):
        return to_unsigned(to_signed(x) >> s)

    match shift_right:
        case Op.SHR:
            shift_right_fn = shr
        case Op.SAR:
            shift_right_fn = sar
        case _:
            raise ValueError(f"Unexpected shift op: {shift_right}")

    rng = random.Random(1)  # Use random with a fixed seed.
    initial_value = 2**256 - 1  # The initial value to be shifted; should be negative for SAR.

    # Create the list of shift amounts with 15 elements (max reachable by DUPs instructions).
    # For the worst case keep the values small and omit values divisible by 8.
    shift_amounts = [x + (x >= 8) + (x >= 15) for x in range(1, 16)]

    code_prefix = sum(Op.PUSH1[sh] for sh in shift_amounts) + Op.JUMPDEST + Op.CALLDATALOAD(0)
    code_suffix = Op.POP + Op.JUMP(len(shift_amounts) * 2)
    code_body_len = max_code_size - len(code_prefix) - len(code_suffix)

    def select_shift_amount(shift_fn, v):
        """Select a shift amount that will produce a non-zero result."""
        while True:
            index = rng.randint(0, len(shift_amounts) - 1)
            sh = shift_amounts[index]
            new_v = shift_fn(v, sh) % 2**256
            if new_v != 0:
                return new_v, index

    code_body = Bytecode()
    v = initial_value
    while len(code_body) <= code_body_len - 4:
        v, i = select_shift_amount(shl, v)
        code_body += make_dup(len(shift_amounts) - i) + Op.SHL
        v, i = select_shift_amount(shift_right_fn, v)
        code_body += make_dup(len(shift_amounts) - i) + shift_right

    code = code_prefix + code_body + code_suffix
    assert len(code) == max_code_size - 2

    env = Environment()

    tx = Transaction(
        to=pre.deploy_contract(code=code),
        data=initial_value.to_bytes(32, byteorder="big"),
        gas_limit=env.gas_limit,
        sender=pre.fund_eoa(),
    )

    state_test(
        env=env,
        pre=pre,
        post={},
        tx=tx,
    )

Parametrized Test Cases

The interactive table below is also available as a standalone page.

Fork All Forks Cancun Prague Osaka

Fixture Type All Fixture Types state_test blockchain_test

Test ID (Abbreviated)	shift_right
...fork_Cancun-state_test-shift_right_SHR	SHR
...fork_Cancun-state_test-shift_right_SAR	SAR
...fork_Cancun-blockchain_test_from_state_test-shift_right_SHR	SHR
...fork_Cancun-blockchain_test_from_state_test-shift_right_SAR	SAR
...fork_Prague-state_test-shift_right_SHR	SHR
...fork_Prague-state_test-shift_right_SAR	SAR
...fork_Prague-blockchain_test_from_state_test-shift_right_SHR	SHR
...fork_Prague-blockchain_test_from_state_test-shift_right_SAR	SAR
...fork_Osaka-state_test-shift_right_SHR	SHR
...fork_Osaka-state_test-shift_right_SAR	SAR
...fork_Osaka-blockchain_test_from_state_test-shift_right_SHR	SHR
...fork_Osaka-blockchain_test_from_state_test-shift_right_SAR	SAR