Submission d2e9b64a...

ChallengeRemove duplicate elements
Submitterwicketh.eth
Submitted at2018-13-17
Gas used208533
/**
 * 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.24;

contract Unique {
    
    function () external payable { assembly {
        
        // @author Remco Bloemen <[email protected]>
        // Competition gas: 202359
        
        // Clear all memory
        mstore(0x40, 0)
        
        let l := calldataload(36)
        jumpi(main, l)
        
        // Empty list
        mstore(0, 32)
        mstore(32, 0)
        return(0, 64)
        
    main:
        let ptr := 64
        let i := 68
        let htl := div(mul(l, 25), 10)
        let skip := mul(htl, 32)
        let scale := add(div(sub(0, mul(htl, 32)), mul(htl, 32)), 1)
        
    oloop:
        {
            let value
            let vhash
            let index1
            let index2
            let iv
            
            // Read value
            value := calldataload(i)
            
            // Offset value so we don't get zeros
            vhash := add(value,
0x1bd0595188413fa59c3f008d96befaf74adc3f8956246ce2df08e2f0f8c50024
            )
            
            // Compute index 1
            index1 := add(and(div(mul(vhash,
0xde142f4c3f629ab89752dbb20b144e968ee343196fb7658806224a32e607937a
            ), scale), 0xFFFFFFFFFFFFFE0), calldatasize)
            
            // Read index 1
            iv := mload(index1)
            jumpi(unique1, iszero(iv))
            jumpi(seen, eq(iv, vhash))
            
            // Compute index 2
            index2 := add(and(div(mul(vhash,
0x9d6bc012ecf658fc07ef5ab754e3a2ec771519170c280624616bf3352aaab27
            ), scale), 0xFFFFFFFFFFFFFE0), calldatasize)
            
            // Read index 2
            iv := mload(index2)
            jumpi(unique2, iszero(iv))
            jumpi(seen, eq(iv, vhash))
            
        iloop:
            // Increment and test index 1
            index1 := add(index1, skip)
            iv := mload(index1)
            jumpi(unique1, iszero(iv))
            jumpi(seen, eq(iv, vhash))
            
            // Incerment and test index 2
            index2 := add(index2, skip)
            iv := mload(index2)
            jumpi(unique2, iszero(iv))
            jumpi(seen, eq(iv, vhash))
            
            // Loop
            jump(iloop)
        
        unique2:
            // Add to the hash table
            mstore(index2, vhash)
            
            // Add to start of list
            mstore(ptr, value)
            ptr := add(ptr, 32)
            jump(seen)
            
        unique1:
            // Add to the hash table
            mstore(index1, vhash)
            
            // Add to start of list
            mstore(ptr, value)
            ptr := add(ptr, 32)
        
        seen:
        }
            
    // oloop_continue:
        i := add(i, 32)
        jumpi(oloop, lt(i, calldatasize))
        
    // oloop_end:
        mstore(0, 32)
        mstore(32, div(sub(ptr, 64), 32))
        return(0, ptr)
    }}
    
}