Submission 6574507a...

ChallengeString search
Submitterricmoo.firefly.eth
Submitted at2018-04-28
Gas used427407
/**
 * 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/
 *
 *  Author: Richard Moore <[email protected]>
 *  Date: May 27, 2018
 */

pragma solidity 0.4.24;

contract IndexOf {
    /**
     * @dev Returns the index of the first occurrence of `needle` in `haystack`,
     *      or -1 if `needle` is not found in `haystack`.
     *
     * Input strings may be of any length <2^255.
     *
     * @param haystack The string to search.
     * @param needle The string to search for.
     * @return The index of `needle` in `haystack`, or -1 if not found.
     */
    function indexOf(string haystack, string needle) public pure returns(int) {
        assembly {
            let needleLength := mload(needle)
            if iszero(needleLength) {
                mstore(0x0, 0)
                return (0, 32)
            }

            let haystackLength := mload(haystack)
            if gt(needleLength, haystackLength) {
                mstore(0, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
                return(0, 32)
            }

            let haystackIndex := add(haystack, 32)
            let haystackEnd := add(add(haystackIndex, sub(haystackLength, needleLength)), 1)
            for { } lt(haystackIndex, haystackEnd) { } {
                let needleIndex := add(needle, 32)
                let needleEnd := add(needleIndex, needleLength)

                let found := 1
                let haystackSubIndex := haystackIndex
                for { } lt(needleIndex, needleEnd) { } {
                    if eq(eq(byte(0, mload(haystackSubIndex)), byte(0, mload(needleIndex))), 0) {
                        needleIndex := 0xffffffff
                        found := 0
                    }
                    needleIndex := add(needleIndex, 1)
                    haystackSubIndex := add(haystackSubIndex, 1)
                }

                if eq(found, 1) {
                    mstore(0x0, sub(haystackIndex, add(haystack, 32)))
                    return(0x0, 32)
                }

                haystackIndex := add(haystackIndex, 1)
            }

            mstore(0, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
            return(0, 32)
        }
    }
}