Submission 1a83422c...

ChallengeString search
Submitterwicketh.eth
Submitted at2018-03-27
Gas used63089
/**
 * This file is part of the 1st Solidity Gas Golfing Contest.
 *
 * This work is licensed under Creative Commons Attribution ShareAlike 3.0.
 * https://creativecommons.org/licenses/by-sa/3.0/
 */

pragma solidity 0.4.24;

contract IndexOf {

    uint256 constant firstBits = 0x0101010101010101010101010101010101010101010101010101010101010101;
    
    uint256 constant firstByte = 0x0100000000000000000000000000000000000000000000000000000000000000;

    function indexOf(string haystack, string needle)
        public pure
        returns(int)
    {
        bytes memory n = bytes(needle);
        uint256 nl = n.length;
        if (nl == 0) {
            return 0;
        }
        bytes memory h = bytes(haystack);
        uint256 hl = h.length;
        if (nl > hl) {
            return -1;
        }
        
        if (nl < 32) {
            
            assembly {
                let mask
                let pat
                let value
                let i
                let end
                
                mask := 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
                mask := mul(mask, exp(256, sub(32, nl)))
                
                i := add(h, 32)
                end := add(sub(add(i, hl), nl), 1) // Why the 1?
                pat := and(mload(add(n, 32)), mask)
                
                for {} lt(i, end) {} {
                    value := mload(i)
                    value := and(not(xor(value, pat)), mask)
                    if eq(value, mask) {
                        mstore(0, sub(i, add(h, 32)))
                        return(0, 32)
                    }
                    i := add(i, 1)
                }
                
                mstore(0, not(0))
                return(0, 32)
            }
            
        } else {
            
            assembly {
                let nh
                let pat
                let value
                let i
                let end

                nh := keccak256(add(n, 32), nl)
                
                i := add(h, 32)
                end := add(sub(add(i, hl), nl), 1)
                pat := mload(add(n, 32))
                
                for {} lt(i, end) {} {
                    value := mload(i)
                    if eq(value, pat) {
                        let hh := keccak256(i, nl)
                        if eq(nh, hh) {
                            mstore(0, sub(i, add(h, 32)))
                            return(0, 32)
                        }
                    }
                    i := add(i, 1)
                }
                mstore(0, not(0))
                return(0, 32)
            }
            
        }
        return -1;
    }
}