Submission 5908c46e...

ChallengeRemove duplicate elements
Submitterricmoo.firefly.eth
Submitted at2018-35-31
Gas used254607
contract Unique {
    function uniquify(uint[] /* input */) public pure returns(uint[]) {
        assembly {

            // Memory
            //   - 256 x 256 bit values for filter
            //   - output data dynlink0 (32)
            //   - output data size (32 bytes)
            //   - input data (re-used as output data)
            let smallFilter := mload(0x40)
            let bloomFilter := add(smallFilter, 256)
            let data := add(bloomFilter, 8192)

            calldatacopy(data, 4, sub(calldatasize, 4))
            mstore(data, 32)

            // WARNING: Should actually load the pointer first
            let length := mload(add(data, 32))

            // Trivially unique
            if lt(length, 2) {
                mstore(add(data, 32), length)
                return(data, add(length, add(64, mul(length, 32))))
            }

            let offset := add(data, 64)
            let outputOffset := offset
            let end := add(offset, mul(length, 32))
            length := 0
            for { } lt(offset, end) { } {

                let v := mload(offset)
                let unique := 0

                // Small number; we have a custom filter for those
                if lt(v, 256) {
                    let index := add(smallFilter, v)
                    let check := byte(0, mload(index))
                    if iszero(check) {
                        unique := 1
                        mstore8(index, 0x01)
                    }
                }

                // Fallback onto the bloom filter
                if gt(v, 255) {
                    let index := add(bloomFilter, and(v, 0xfff))
                    let check := mload(index)

                    let test := eq(and(check, v), v)

                    // Bloom filter miss (unique!)
                    if iszero(test) {
                        unique := 1
                        mstore(index, or(check, v))
                    }

                    if test {
                        // Scan existing entries for v
                        unique := 1
                        let scanOffset := add(data, 64)
                        for { } lt(scanOffset, outputOffset) { } {
                            if eq(mload(scanOffset), v) {
                                unique := 0
                                scanOffset := outputOffset
                            }
                            scanOffset := add(scanOffset, 32)
                        }
                    }
                }

                if unique {
                    mstore(outputOffset, v)
                    outputOffset := add(outputOffset, 32)
                    length := add(length, 1)
                }

                offset := add(offset, 32)
            }

            mstore(add(data, 32), length)
            return(data, sub(offset, data))
        }
    }
}