Submission e0053793...

ChallengeString search
Submitterricmoo.firefly.eth
Submitted at2018-56-30
Gas used55413
pragma solidity 0.4.24;

contract IndexOf {
    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)

            // Trivial case
            if gt(needleLength, haystackLength) {
                mstore(0x0, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
                return(0, 32)
            }

            if lt(needleLength, 9) {
                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
                        if lt(needleBlockLength, 32) {
                            mstore(0, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
                            mstore8(sub(needleBlockLength, 1), 0xfe)
                            mask := add(mload(0), 1)
                        }

                        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)
            }

            let needleBase := add(needle, 32)
            let haystackBase := add(haystack, 32)

            // byte(0, mload(add(srcBase, i)))

            let i := 0
            let badCharacter := mload(0x40)
            for { } lt(i, needleLength) {} {
                let ci := byte(0, mload(add(needleBase, i)))
                mstore(add(badCharacter, mul(32, ci)), add(i, 1))
                i := add(i, 1)
            }

            let j := 0

            let shift := 0

            let end := add(sub(haystackLength, needleLength), 1)
            for {} lt(shift, end) {} {
                j := sub(needleLength, 1)
                let done := 1
                for {} done {} {
                    done := iszero(slt(j, 0x0))
                    if done {
                        let n := byte(0, mload(add(needleBase, j)))
                        let h := byte(0, mload(add(haystackBase, add(shift, j))))
                        done := eq(n, h)
                        j := sub(j, done)
                    }
                }

                if slt(j, 0) {
                    mstore(0x0, shift)
                    return(0x0, 32)
                }

                let ci := byte(0, mload(add(haystackBase, add(shift, j))))
                let value := sub(mload(add(badCharacter, mul(32, ci))), 1)
                if slt(value, j) {
                    shift := add(shift, sub(sub(j, value), 1))
                }

                shift := add(shift, 1)
            }
            mstore(0, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
            return(0x0, 32)

            //return -1;
        }
    }
}