Submission b8f5f036...

ChallengeString search
Submitter0xabcdef0db461f2f...
Submitted at2018-38-03
Gas used57966
/**
 * 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) {
        assembly {

            let hsLen := calldataload(0x44)
            let nLen := calldataload(add(calldataload(0x24), 0x04))

            if iszero(nLen) {
                mstore(0x40, 0x0000000000000000000000000000000000000000000000000000000000000000)
                return(0x40, 0x20)
            }

            if lt(hsLen, nLen) {
                mstore(0x40, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
                return(0x40, 0x20)
            }

            function findOne(hsIdxL, hsIdxR, nByte) {
                for { let idx := hsIdxL }
                    lt(idx, hsIdxR)
                    { idx := add(idx, 0x1) } {
                    if eq(nByte,
                          and(
                              calldataload(idx),
                              0xff00000000000000000000000000000000000000000000000000000000000000)) {
                        mstore(0x20, sub(idx, hsIdxL))
                        idx := hsIdxR
                    }
                }
            }

            function findFew(hsIdxL, hsIdxR, nUint, nMask) {
                for { let idx := hsIdxL }
                    lt(idx, hsIdxR)
                    { idx := add(idx, 0x1) } {
                    if eq(nUint, and(calldataload(idx), nMask)) {
                        mstore(0x20, sub(idx, hsIdxL))
                        idx := hsIdxR
                    }
                }
            }

            function findUint(hsIdxL, hsIdxR, nUint) {
                for { let idx := hsIdxL }
                    lt(idx, hsIdxR)
                    { idx := add(idx, 0x1) } {
                    if eq(nUint, calldataload(idx)) {
                        mstore(0x20, sub(idx, hsIdxL))
                        idx := hsIdxR
                    }
                }
            }

            function findMuch() {
                let nLen1 := calldataload(add(calldataload(0x24), 0x04))
                calldatacopy(
                    0x40,
                    add(calldataload(0x24), 0x24),
                    nLen1)
                let nHash := keccak256(0x40, nLen1)
                calldatacopy(
                    0x40,
                    0x64,
                    calldataload(0x44))
                let idxR := sub(calldataload(0x44), sub(nLen1, 1))
                let hsPtr := 0x40
                for { let idx := 0 }
                    lt(idx, idxR)
                    { idx := add(idx, 0x01) } {
                    if eq(nHash, keccak256(add(hsPtr, idx), nLen1)) {
                        mstore(0x20, idx)
                        idx := idxR
                    }
                }
            }

            function findMuchV2(hsIdxL, hsIdxR, nIdxL, _nLen) {
                let nLeft := mod(_nLen, 0x20)
                let nIdxR := sub(add(nIdxL, _nLen), nLeft)
                let nUint := calldataload(nIdxL)
                for { let idx := hsIdxL }
                    lt(idx, hsIdxR)
                    { idx := add(idx, 0x1) } {
                    if eq(nUint, calldataload(idx)) {
                        let idx2 := add(nIdxL, 0x20)
                        let idx3 := idx
                        for { } lt(idx2, nIdxR) { } {
                            idx3 := add(idx3, 0x20)
                            switch eq(calldataload(idx2), calldataload(idx3))
                            case 1 { idx2 := add(idx2, 0x20) }
                            default { idx2 := add(nIdxR, 0x01) }
                        }
                        if eq(idx2, nIdxR) {
                            switch iszero(nLeft)
                            case 1 {
                                mstore(0x20, sub(idx, hsIdxL))
                                idx := hsIdxR
                            }
                            default {
                                if eq(
                                    calldataload(idx2),
                                    and(
                                        calldataload(
                                            add(idx3, 0x20)),
                                            not(
                                                sub(
                                                    exp(
                                                        0x02,
                                                        mul(0x08, nLeft)),
                                                    0x01)))) {
                                    mstore(0x20, sub(idx, hsIdxL))
                                    idx := hsIdxR
                                }
                            }
                        }
                    }
                }
            }

            mstore(0x20, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
            switch nLen
            case 1 {
                findOne(
                    0x64,
                    add(0x64, hsLen),
                    calldataload(add(calldataload(0x24), 0x24)))
            }
            case 32 {
                findUint(
                    0x64,
                    sub(add(0x64, hsLen), 0x1f),
                    calldataload(add(calldataload(0x24), 0x24)))
            }
            default {
                if lt(nLen, 32) {
                    findFew(
                        0x64,
                        sub(add(0x64, hsLen), sub(nLen, 0x01)),
                        calldataload(add(calldataload(0x24), 0x24)),
                        not(
                            sub(
                                exp(
                                    0x02,
                                    mul(0x08, nLen)),
                                0x01)))
                }
                findMuchV2(
                    0x64,
                    sub(add(0x64, hsLen), sub(nLen, 0x01)),
                    add(calldataload(0x24), 0x24),
                    nLen)
            }
            return(0x20, 0x20)
        }
    }
}