Submission cf02fb51...

ChallengeString search
Submitterzac.creditmint.eth
Submitted at2018-14-24
Gas used40228
/**
 * 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.23;

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.
     *
     * @return The index of `needle` in `haystack`, or -1 if not found.
     */
    function indexOf(string, string) external view returns(int) {
        assembly {
            let _needleSize := calldataload(add(calldataload(0x24), 0x04))
            if gt(_needleSize, calldataload(0x44)) {
                mstore(0x00, sub(0, 1))
                return(0x00, 0x20)
            }
            if iszero(_needleSize) {
                mstore(0x00, 0x00)
                return(0x00, 0x20)
            }
            if eq(_needleSize, 1) {
                indexOfSingleByte()
            }
            indexOfManyBytes()
            function indexOfManyBytes() {
                let offset := add(calldataload(0x24), 0x04)
                let needleSize := calldataload(offset)
                let needleIterator := 0x00
                let needleByteRepeated := 0x00
                get_needle_comparators:
                    needleByteRepeated := mul(
                        and(calldataload(add(add(offset, 0x01), needleIterator)), 0xff),
                        0x0101010101010101010101010101010101010101010101010101010101010101
                    )
                    mstore(mul(needleIterator, 0x20), needleByteRepeated)
                    needleIterator := add(needleIterator, 0x01)
                    jumpi(get_needle_comparators, lt(needleIterator, needleSize))
                let lookupTableOffset := mul(0x20, needleSize)
                mstore(add(lookupTableOffset, 0x20), 0x000a1e170b0800011c1800150000090e000614020000000019001a001016001b)
                mstore(add(lookupTableOffset, 0x40), 0x000000131100000f00001f000700000c0d03000000040000121d000000000005)

                // We want to iterate over our haystack in word-chunks.
                // We're going to start by comparing the *last* byte in our sequence to we should start at a position that is
                // equal to start of haystack + size of our needle
                let calldataIterator := add(0x64, sub(needleSize, 0x01))
                let needleEndpoint := mul(0x20, sub(needleSize, 0x01))
                let needleCrawler, w, v
                iterate_over_words:
                    needleIterator := add(needleEndpoint, 0x20) // todo: we should store as a constant
                    needleCrawler := sub(0, 1)
                    w := 0x8080808080808080808080808080808080808080808080808080808080808080
                    iterate_over_needle:
                        // let's get the next byte and see if it's a match
                        needleIterator := sub(needleIterator, 0x20)
                        needleCrawler := add(needleCrawler, 0x01)
                        w := and(
                                and(
                                    not(add(
                                        // TODO: most of the time we don't need to load a new word of calldata, can use what we have
                                        // and address via BYTE
                                        xor(calldataload(sub(calldataIterator, needleCrawler)), mload(needleIterator)),
                                        0x7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
                                    )),
                                    0x8080808080808080808080808080808080808080808080808080808080808080
                                ),
                                w
                        )
                        // we want to keep going if w is not zero and needleIterator is not zero.
                        // if w is zero we skip out, if needleIterator is zero we skip out
                        jumpi(iterate_over_needle, iszero(or(iszero(needleIterator), iszero(w))))
                        
                    // ok, so we're out of iterate_over_needle
                    // if w is true then we've found our match!
                    // otherwise, we need to load up the next word.
                    // first test if we've found a match as this is the most likely outcome for short haystacks
                    jumpi(found_match, w)
                    // repeat loop for failed tests
                    calldataIterator := add(calldataIterator, 0x20)
                    jumpi(iterate_over_words, lt(calldataIterator, offset))
                    jump(found_no_match)

                    found_match:
                        // Alright! we've found a match!
                        // 'w' is going to have high bits set at the 8th bit of every byte where there was a match
                        // for every (offset) needle byte.
                        // there may be more than one, so we want the index of the *most* significant bit.
                        // As this can range up to 2^255 we can't use a simple lookup table. We can,
                        // however, use degenerate bit hacks.
                        // Todo, optimize out not(0). Also, using IULIA for this bit is super inefficient.
                        w := mulmod(w, 0xfe00000000000000000000000000000000000000000000000000000000000001, not(0))
                        w := or(w, div(w, 0x100))
                        w := or(w, div(w, 0x10000))
                        w := or(w, div(w, 0x100000000))
                        w := or(w, div(w, 0x10000000000000000))
                        w := mod(add(or(w, div(w, 0x100000000000000000000000000000000)), 0x01), 71)
                        mstore(0x00, add(and(mload(add(lookupTableOffset, w)), 0xff), sub(sub(calldataIterator, needleSize), 0x63)))
                        return(0x00, 0x20)

                    found_no_match:
                        mstore(0x00, sub(0, 1))
                        return(0x00, 0x20)
            }
            function indexOfSingleByte() {
                mstore(0x20, 0x000a1e170b0800011c1800150000090e000614020000000019001a001016001b)
                mstore(0x40, 0x000000131100000f00001f000700000c0d03000000040000121d000000000005)

                let testByte := and(calldataload(add(calldataload(0x24), 0x05)), 0xff)
                let testVector := mul(
                    testByte,
                    0x0101010101010101010101010101010101010101010101010101010101010101
                )
                let calldataIndex := 0x64
                let end := add(calldataload(0x24), 0x04)
                let w := 0x00
                for {} lt(calldataIndex, end) {calldataIndex := add(calldataIndex, 0x20)} {
                    w := and(not(add(xor(calldataload(calldataIndex), testVector), 0x7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f)), 0x8080808080808080808080808080808080808080808080808080808080808080)
                    if w {
                        w := mulmod(w, 0xfe00000000000000000000000000000000000000000000000000000000000001, not(0))
                        w := or(w, div(w, 0x100))
                        w := or(w, div(w, 0x10000))
                        w := or(w, div(w, 0x100000000))
                        w := or(w, div(w, 0x10000000000000000))
                        w := mod(add(or(w, div(w, 0x100000000000000000000000000000000)), 0x01), 71)
                        let r := add(and(mload(w), 0xff), sub(calldataIndex, 0x64))
                        mstore(0x00, r)
                        return(0x00, 0x20)
                    }
                }
                mstore(0x00, sub(0, 1))
                return(0x00, 0x20)
            }
        }
    }
}