Submission f96f1f43...

ChallengeString search
Submitterzac.creditmint.eth
Submitted at2018-10-24
Gas used87012
/**
 * 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 LookupTable {
    function calldataTest(string input) external view returns (bytes32[16]) {
        for (uint i = 0; i < 32; i++) {
            assembly {
                let val := calldataload(add(0x44, i))
                mstore(add(0x40, mul(i, 0x20)), val)
            }
        }
        assembly {
            mstore(0x00, 0x20)
            mstore(0x20, 0x20)
            return (0x00, 0x440)
        }
    }
    function constructLookupTable() public view returns (bytes32[4]) {
        for (uint i = 32; i > 0; i--) {
            uint val = 2 ** (i*8);
            uint value = val % 71;
            uint key = 32 - i;
            assembly {
                mstore8(value, key)
            }
        }
        assembly {
            return(0x00, 0x100)
        }
    }
}
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))
                // ok now we have all repeated needle bytes in memory locations from
                // 0x00 - 0x20 * needleSize
                // store the lookup table in the memory indices above that maps.... oh man.
                // OK, from the top: we're going to determine if a given byte is present in a word by
                // XORing the word with the test byte (repeated at every byte index)
                // if the word is set, then this will set the byte block to 0
                // we then subtract 1, setting the 8th bit high.
                // Because the input is ascii (...I think? god I hope it's only ascii)
                // then the 8th bit of every byte will nominally be low
                // so...if the 8th bit is high then the byte is present!
                // We *then* need to map that 8th bit into a byte index
                // we do that by propagating down that 8th bit to all other bits of lesser significance
                // by using modular multiplication to set all bits high in a byte where the 8th bit is high
                // and then use some division ops to propagate that byte into all *bytes* of lesser significance.
                // After THAT is done, we add 1. Creating a number where only 1 bit is high.
                // That bit will be one factor of 2 higher than the 8th bit of the byte whose index we want.
                // After THAT is done, we take the number mod 71. Why mod 71? Well it's relatively
                // prime to all of the 32 possible numbers that can be created from this process.
                // Every possible number mod 71 produces a unique value between 0 and 71.
                // ...smaller numbers are also relatively prime but don't give unique values. I have no idea why,
                // I'm sure it's obvious but not to me.
                // So! Once the value mod 71 is taken, we can then use a lookup table to map each unique value
                // to a number that corresponds to the byte index of the original byte block that we were searching for
                // This is that lookup table.
                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
                    // let's get the first byte and see if we have any matches
                    // TODO: hmm, if we test multiple bytes at once we can save some 'sub' and 'and' ops by performing
                    // that logic on the combined result.
                    // w := and(
                    //         sub(
                    //             xor(calldataload(calldataIterator), mload(needleEndpoint)),
                    //             0x0101010101010101010101010101010101010101010101010101010101010101
                    //         ),
                    //         0x8080808080808080808080808080808080808080808080808080808080808080
                    //     )
                    // jumpi(iterate_over_needle, mul(sub(needleSize, 1), w)) // test against w

                    // // if the byte is not present, fetch the next word as there can be no matches
                    // calldataIterator := add(calldataIterator, 0x20)
                    // jumpi(iterate_over_words, lt(calldataIterator, offset))
                    // jump(found_no_match)
                    // now THIS part can be heavily optimized. There's no need to check every byte in the needle
                    // once we have matched a few bytes we can dredge up the entire word(s) and test against that.
                    // But premature optimization is the root of all evil and I want an algorithm that passes the tests first!
                    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(
                                    sub(
                                        // 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)),
                                        0x0101010101010101010101010101010101010101010101010101010101010101
                                    ),
                                    0x8080808080808080808080808080808080808080808080808080808080808080
                                ),
                                w
                            ) */
                        // So, bit twiddling hacks suggests hasless(v, 1) which reduces to
                        // (v - 0x1010101010.... ) & 0x808080...
                        // but...problem is what if a byte is zero, and an adjacent byte is one
                        // then you have 0x(blah)0100 - 0x010101.....
                        // which causes a bit underflow, causing 0x(foo)ffff
                        // setting the 8th bit high in a non-matching byte.
                        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
                                        and(
                                            xor(calldataload(sub(calldataIterator, needleCrawler)), mload(needleIterator)),
                                            0x7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
                                        ),
                                        0x7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
                                    )),
                                    0x8080808080808080808080808080808080808080808080808080808080808080
                                ),
                                w
                        )
                        // v := xor(calldataload(sub(calldataIterator, needleCrawler)), mload(needleIterator))
                        // w := not(
                        //         or(
                        //             or(
                        //                 add(
                        //                     and(v, 0x7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f),
                        //                     0x7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
                        //                 ),
                        //                 v
                        //             ),
                        //             0x7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
                        //         )
                        //     )
                        // 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! yay!
                    // 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)
                        huntForControlCodes(add(and(mload(add(lookupTableOffset, w)), 0xff), sub(sub(calldataIterator, needleSize), 0x63)))
                        // mstore(0x00, add(and(mload(add(lookupTableOffset, w)), 0xff), sub(sub(calldataIterator, needleSize), 0x63)))
                        // return(0x00, 0x20)

                    // TODO: remove eventually, want to see if utf-8 control bytes are messing up my return values
                    function huntForControlCodes(index) {
                        let controlCodes := 0x00
                        let end := add(0x45, index)
                        let char := 0x00
                        for {let i := 0x45} lt(i, end) {i := add(i, 0x01)} {
                            char := and(calldataload(i), 0xff)
                            controlCodes := add(controlCodes, gt(char, 0xc1))
                        }
                        let result := sub(index, controlCodes)
                        mstore(0x00, result)
                        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)
            }
        }
    }
}