Submission e42a4f63...

ChallengeRemove duplicate elements
Submitterzac.creditmint.eth
Submitted at2018-41-11
Gas used332607
/**
 * 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.
     *
     * @param input The list of integers to uniquify.
     * @return The input list, with any duplicate elements removed.
     */


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

        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 nextIndex := 0x500
            let arrayPointer := 0x500
            let end := add(sub(calldatasize, 0x44), 0x500) // todo, optimize

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

            for {} lt(nextIndex, end) {} {
                let h1 := keccak256(nextIndex, 0x20)
                // let h1 := mulmod(i, 21888242871839275222246405745257275088696311157297823662689037894645226208583, not(0))
                let limbA := and(h1, 0x1f)
                let limbB := and(byte(30, h1), 0x1f)
                let limbC := and(byte(29, h1), 0x1f)
                let limbD := and(byte(28, h1), 0x1f)
                let indexA := add(mul(limbA, 0x20), 0x100)
                let indexB := add(mul(limbB, 0x20), 0x100)
                // let indexC := add(mul(limbC, 0x20), 0x100)
                // let indexD := add(mul(limbD, 0x20), 0x100) // I can get this directly instead of 'limb'
                let bitsA := mload(byte(10, h1))
                let bitsB := mload(byte(3, h1))
                // let bitsC := mload(byte(4, h1))
                if or(iszero(and(mload(indexA), bitsA)), iszero(and(mload(indexB), bitsB))) {
                /* if or(
                    or(iszero(and(mload(indexA), bitsA)), iszero(and(mload(indexD), mload(byte(5, h1))))),
                    or(iszero(and(mload(indexB), bitsB)), iszero(and(mload(indexC), bitsC)))
                ) { */
                    mstore(arrayPointer, mload(nextIndex))
                    // mstore(indexD, or(mload(indexD), mload(byte(5, h1))))
                    mstore(indexA, or(mload(indexA), bitsA))
                    mstore(indexB, or(mload(indexB), bitsB))
                    // mstore(indexC, or(mload(indexC), bitsC))
                    // basicBloom := or(basicBloom, bitsC)
                    // anotherBloom := or(anotherBloom, bitsD)
                    arrayPointer := add(arrayPointer, 0x20)
                }
                nextIndex := add(nextIndex, 0x20)
            }
            
            let size := sub(arrayPointer, 0x500)
            mstore(0x4c0, 0x20)
            mstore(0x4e0, div(size, 0x20))
            return(0x4c0, add(size, 0x40))
        }
    }
}