Submission 70738ac3...

ChallengeString search
Submitter0xabcdef0db461f2f...
Submitted at2018-18-02
Gas used76172
/**
 * 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 {
    /**
     * @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) {
        bytes memory hsBytes = bytes(haystack);
        bytes memory nBytes = bytes(needle);
        if (nBytes.length == 0) {
            return;
        }
        if (hsBytes.length < nBytes.length) {
            assembly {
                mstore(0x40, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
                return(0x40, 0x20)
            }
        }
        if (nBytes.length == 1) {
            return findOne(hsBytes, nBytes[0]);
        }
        if (nBytes.length < 32) {
            return findFew(hsBytes, nBytes);
        }
        if (nBytes.length == 32) {
            return findUint(hsBytes, nBytes);
        }
        return findMuch(hsBytes, nBytes);
    }

    function findOne(bytes memory hsBytes, byte nByte) internal pure returns (int) {
        assembly {
            let hsPtrL := add(hsBytes, 0x20)
            let hsPtrR := add(hsPtrL, mload(hsBytes))
            for { let ptr := hsPtrL }
                lt(ptr, hsPtrR)
                { ptr := add(ptr, 0x1) } {
                if eq(nByte, and(0xff00000000000000000000000000000000000000000000000000000000000000, mload(ptr))) {
                    mstore(0x40, sub(ptr, hsPtrL))
                    return(0x40, 0x20)
                }
            }
            mstore(0x40, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
            return(0x40, 0x20)
        }
    }

    function findFew(bytes memory hsBytes, bytes memory nBytes) internal pure returns (int) {
        assembly {
            let nMask := not(
                sub(
                    exp(
                        0x02,
                        mul(0x08, mload(nBytes))),
                    0x01)
            )
            let nUint := and(mload(add(nBytes, 0x20)), nMask)
            let hsPtrL := add(hsBytes, 0x20)
            let hsPtrR := sub(
                add(hsPtrL, mload(hsBytes)),
                sub(mload(nBytes), 0x01))
            for { let ptr := hsPtrL }
                lt(ptr, hsPtrR)
                { ptr := add(ptr, 0x1) } {
                if eq(nUint, and(nMask, mload(ptr))) {
                    mstore(0x40, sub(ptr, hsPtrL))
                    return(0x40, 0x20)
                }
            }
            mstore(0x40, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
            return(0x40, 0x20)
        }
    }

    function findUint(bytes memory hsBytes, bytes memory nBytes) internal pure returns (int) {
        assembly {
            let nUint := mload(add(nBytes, 0x20))
            let hsPtrL := add(hsBytes, 0x20)
            let hsPtrR := sub(
                add(hsPtrL, mload(hsBytes)),
                0x1f)
            for { let ptr := hsPtrL }
                lt(ptr, hsPtrR)
                { ptr := add(ptr, 0x1) } {
                if eq(nUint, mload(ptr)) {
                    mstore(0x40, sub(ptr, hsPtrL))
                    return(0x40, 0x20)
                }
            }
            mstore(0x40, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
            return(0x40, 0x20)
        }
    }

    function findMuch(bytes memory hsBytes, bytes memory nBytes) internal pure returns (int) {
        assembly {
            let nLen := mload(nBytes)
            let nHash := keccak256(add(nBytes, 0x20), nLen)
            let idxR := sub(mload(hsBytes), sub(nLen, 1))
            let hsPtr := add(hsBytes, 0x20)
            for { let idx := 0 }
                lt(idx, idxR)
                { idx := add(idx, 0x01) } {
                if eq(nHash, keccak256(add(hsPtr, idx), nLen)) {
                    mstore(0x40, idx)
                    return(0x40, 0x20)
                }
            }
            mstore(0x40, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
            return(0x40, 0x20)
        }
    }
}