Submission 0db26a70...

ChallengeString search
Submitterricmoo.firefly.eth
Submitted at2018-46-28
Gas used242125
/**
 * 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
                let needleBlockLength := needleLength
                for { } lt(needleIndex, needleEnd) { } {
                    let haystackData := mload(haystackSubIndex)
                    let needleData :=  mload(needleIndex)
                    let mask := 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
                    let needleSubLength := needleBlockLength
                    if gt(needleSubLength, 32) {
                        needleSubLength := 32
                    }
                    mask := sub(mask, sub(exp(2, mul(8, sub(32, needleSubLength))), 1))
                    //mstore(0, and(xor(haystackData, needleData), mask))
                    //mstore(0, haystackData)
                    //return (0, 32)
                    if and(xor(haystackData, needleData), mask) {
                        needleIndex := 0xffffffffffffff
                        found := 0
                    }
                    needleIndex := add(needleIndex, 32)
                    haystackSubIndex := add(haystackSubIndex, 32)
                    needleBlockLength := sub(needleBlockLength, 32)
                }

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

                haystackIndex := add(haystackIndex, 1)
            }

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