Submission 726fc5d0...

ChallengeString search
Submitterwicketh.eth
Submitted at2018-32-27
Gas used25500
pragma solidity 0.4.24;

contract IndexOf {

    function () external payable { assembly {
        // indexOf(string haystack, string needle)
        
        // @author Remco Bloemen <[email protected]>
        
        let h := add(calldataload(0x04), 4)
        let n := add(calldataload(0x24), 4)
        let hl := calldataload(h)
        let nl := calldataload(n)
        
        // Empty needle 
        if iszero(nl) {
            mstore(0, 0)
            return(0, 32)
        }
        // Needle longer than haystack
        if gt(nl, hl) {
            mstore(0, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)
            return(0, 32)
        }
        
        // Special case for single character needle
        // We assume hl is less than 32
        if eq(nl, 1) {
            
            n := and(calldataload(add(n, 1)), 0xFF)
            let mask := not(mul(n, 0x0101010101010101010101010101010101010101010101010101010101010101))
            
            h := calldataload(add(h, 32))
            
            let matc := xor(mask, h)
            matc := and(matc, div(matc, 16))
            matc := and(matc, div(matc, 4))
            matc := and(matc, div(matc, 2))
            matc := and(matc, 0x0101010101010101010101010101010101010101010101010101010101010101)
            
            jumpi(found, matc)
            
        //notfound:
            mstore(0, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)
            return(0, 32)
            
        found:
            mstore(0, and(div(
            0x000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f, matc), 0xff))
            return(0, 32)
        }
        
        // General case using hashes
        calldatacopy(0, add(n, 32), nl)
        let nh := keccak256(0, nl)
        calldatacopy(0, add(h, 32), hl)
        
        let mask := not(mul(and(calldataload(add(n, 1)), 0xFF), 0x0101010101010101010101010101010101010101010101010101010101010101))
        n := calldataload(add(n, 32))
        
        let i := 0
        let e := sub(hl, nl)
        let hh
        let matc
        
        loop:
            h := mload(i)
            
            matc := xor(mask, h)
            matc := and(matc, div(matc, 16))
            matc := and(matc, div(matc, 4))
            matc := and(matc, div(matc, 2))
            matc := and(matc, 0x0101010101010101010101010101010101010101010101010101010101010101)
            
            jumpi(maybe, matc)
            
            i := add(i, 32)
            jumpi(notfound, gt(i, e))
            jump(loop)
            
        maybe:
            i := add(i, and(div(
            0x000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f, matc), 0xff))
            
            // Assume nl >= 32
            hh := mload(i)
            jumpi(check_hash, eq(hh, n))
            i := add(i, 1)
            //jumpi(notfound, gt(i, e))
            jump(loop)
            
        check_hash:
            hh := keccak256(i, nl)
            jumpi(found, eq(nh, hh))
            i := add(i, 1)
            jumpi(notfound, gt(i, e))
            jump(loop)
            
        found:
            mstore(0, i)
            return(0, 32)
            
        notfound:
            mstore(0, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)
            return(0, 32)
    }}
}