Submission c01eb032...

ChallengeString search
Submitter0xabcdef0db461f2f...
Submitted at2018-18-03
Gas used76188
/**
 * 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() -> x, y {
                let nByte := calldataload(add(calldataload(0x24), 0x24))
                let hsIdxL := 0x64
                let hsIdxR := add(0x64, calldataload(0x44))
                for { let idx := hsIdxL }
                    lt(idx, hsIdxR)
                    { idx := add(idx, 0x1) } {
                    if eq(nByte,
                          and(
                              calldataload(idx),
                              0xff00000000000000000000000000000000000000000000000000000000000000)) {
                        mstore(0x40, sub(idx, hsIdxL))
                        return(0x40, 0x20)
                    }
                }
                mstore(0x40, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
                return(0x40, 0x20)
            }

            function findFew() -> x, y {
                let nMask := not(
                    sub(
                        exp(
                            0x02,
                            mul(
                                0x08,
                                calldataload(add(calldataload(0x24), 0x04)))),
                        0x01))
                let nUint := and(calldataload(add(calldataload(0x24), 0x24)), nMask)
                let hsIdxL := 0x64
                let hsIdxR := sub(
                    add(0x64, calldataload(0x44)),
                    sub(
                        calldataload(add(calldataload(0x24), 0x04)),
                        0x01))
                for { let idx := hsIdxL }
                    lt(idx, hsIdxR)
                    { idx := add(idx, 0x1) } {
                    if eq(nUint, and(calldataload(idx), nMask)) {
                        mstore(0x40, sub(idx, hsIdxL))
                        return(0x40, 0x20)
                    }
                }
                mstore(0x40, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
                return(0x40, 0x20)
            }

            function findUint() -> x, y {
                let nUint := calldataload(add(calldataload(0x24), 0x24))
                let hsIdxL := 0x64
                let hsIdxR := sub(
                    add(0x64, calldataload(0x44)),
                    0x1f)
                for { let idx := hsIdxL }
                    lt(idx, hsIdxR)
                    { idx := add(idx, 0x1) } {
                    if eq(nUint, calldataload(idx)) {
                        mstore(0x40, sub(idx, hsIdxL))
                        return(0x40, 0x20)
                    }
                }
                mstore(0x40, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
                return(0x40, 0x20)
            }

            function findMuch() -> x, y {
                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(0x40, idx)
                        return(0x40, 0x20)
                    }
                }
                mstore(0x40, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
                return(0x40, 0x20)
            }

            switch nLen
            case 1 {
                let x, y := findOne()
                return(x, y)
            }
            case 32 {
                let x, y := findUint()
                return(x, y)
            }
            default {
                if lt(nLen, 32) {
                    let x, y := findFew()
                    return(x, y)
                }
                let x, y := findMuch()
                return(x, y)
            }
        }
    }
}