0

Practicing my solidity assembly skills and I'm using foundry to test this function. For most inputs it works, but fails when

  1. There is a 0 present in the array
  2. Possibly duplicate values present in the array (?)

I've included failing tests below.

 function maxOf(uint256[] memory a) public pure returns (uint256 max) {
        assembly {
            // grab the length of the array
            // first 32 bytes of the array is its length
            let len := mload(a)

            // first element is actually 32 bytes bytes after, so grab it
            let element := add(a, 0x20)

            // grab the current max
            max := mload(element)
            for { let end := add(element, mul(len, 0x20)) } // end = pointer to first element location + length*32 bytes per word
            lt(element, end) { element := add(element, 0x20) } {
                // move onto the next word in the array
                // x ^ ((x ^ y) & -(x < y));
                let ele := mload(element)
                max := xor(max, and(xor(max, ele), mul(0xFFFFFFFFFFFFFFFFFFF, lt(max, ele))))
            }
        }
    }
[FAIL. Reason: Assertion failed. 
Counterexample: calldata= // omitted for cleanness 
args=[[0, 0, 75557863725914323419136]]] 
testMax(uint256[]) (runs: 2, μ: 62897, ~: 62897)

and

[FAIL. Reason: Assertion failed. 
Counterexample: calldata= // omitted for cleanness
args=[[1, 1, 75557863725914323419136]]]
testMax(uint256[]) (runs: 41, μ: 9460, ~: 9433)

The whole shtick is that I use some bithack x ^ ((x ^ y) & -(x < y)) in order to find the max of two numbers without branching.

I mul(0xFFFFFFFFFFFFFFFFFFF) as to obtain the two's complement of (x < y), so we can get -(x < y). I think that this is the problem but I'm not sure.

1
  • Shouldn't the value 0xFFFFFFFFFFFFFFFFFFF be much bigger?
    – Ismael
    Nov 4, 2022 at 14:25

1 Answer 1

0

You can use something like this to calculate the maximum between two numbers

// SPDX-License-Identifier: ISC
pragma solidity ^0.8.7;

contract X {
    function maxOf(uint256 x, uint256 y) public pure returns (uint256 max) {
        assembly {
            max := xor(x, and(xor(y, x), sub(gt(x, y), 1)))
        }
    }    
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.