Submission 64e64b8d...

ChallengeRemove duplicate elements
Submitterzac.creditmint.eth
Submitted at2018-50-11
Gas used240273
/**
 * 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 Unique {
    /**
     * @dev Removes all but the first occurrence of each element from a list of
     *      integers, preserving the order of original elements, and returns the list.
     *
     * The input list may be of any length.
     *
     * @return The input list, with any duplicate elements removed.
     */


    function uniquify(uint[]) public view returns(uint[]) {

        assembly {
            // hash map
            if eq(calldatasize, 0x44) {
                mstore(0x00, 0x20)
                return(0x00, 0x40)
            }
            mstore(0x0, 1)
            mstore(0x20, 2)
            mstore(0x40, 4)
            mstore(0x60, 8)
            mstore(0x80, 16)
            mstore(0xa0, 32)
            mstore(0xc0, 64)
            mstore(0xe0, 128)
    
            let bloomFilterWords := 0x300
            let memOffset := add(0x120, mul(bloomFilterWords, 0x20))
            let nextIndex := memOffset
            let arrayPointer := nextIndex
            let end := add(calldatasize, sub(nextIndex, 0x44))

            calldatacopy(nextIndex, 0x44, sub(calldatasize, 0x44))

            for {} lt(nextIndex, end) {} {
                let h1 := keccak256(nextIndex, 0x20)
                let indexA := add(0x100, and(h1, sub(mul(bloomFilterWords, 0x20), 0x20)))
                // let indexB := add(0x100, and(div(h1, 0x400), 0x3FF))
                let bitsA := mload(byte(3, h1))
                // let bitsB := mload(byte(3, h1))
                if iszero(and(mload(indexA), bitsA)) {
                    mstore(arrayPointer, mload(nextIndex))
                    mstore(indexA, or(mload(indexA), bitsA))
                    // mstore(indexB, or(mload(indexB), bitsB))
                    arrayPointer := add(arrayPointer, 0x20)
                }
                nextIndex := add(nextIndex, 0x20)
            }
            
            let size := sub(arrayPointer, memOffset)
            mstore(sub(memOffset, 0x40), 0x20)
            mstore(sub(memOffset, 0x20), div(size, 0x20))
            return(sub(memOffset, 0x40), add(size, 0x40))
        }
    }
}