Submission 41da0025...

ChallengeInteger sorting
Submitterzac.creditmint.eth
Submitted at2018-05-27
Gas used480677
/**
 * 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 Sort {
    /**
     * @dev Sorts a list of integers in ascending order.
     *
     * The input list may be of any length.
     *
     * @param input The list of integers to sort.
     * @return The sorted list.
     */
    function insertionNonsense(uint[] input) external view returns(uint[]) {
        assembly {
            let size := sub(calldatasize, 0x44)
            mstore(0x40, sort_two)
            mstore(0x60, sort_three)
            mstore(0x80, sort_four)
            mstore(0xa0, sort_five)
            mstore(0xc0, sort_six)
            mstore(0xe0, sort_seven)
            mstore(0x100, sort_eight)
            calldatacopy(0x120, 0x04, calldatasize)
            0x160
            jump(mload(size))
            pop
            finished_insertion_sort:
                return(0x120, add(size, 0x40))
            sort_two:
                dup1 0x20 add mload // a
                dup2 mload          // b a
                dup2 dup2 lt        // 0 1 p
                two_0_1_skip jumpi
                swap1
            two_0_1_skip:               // (max) (min) p
                dup3 mstore
                dup2 0x20 add mstore
            jump(finished_insertion_sort)

            sort_three:
                dup1 0x40 add       // p2
                dup2 0x20 add       // p1 p2 p
                dup2 mload          // 2 p1 p2 p
                dup2 mload          // 1 2 p1 p2 p
                dup5 mload          // 0 1 2 p1 p2 p

                dup3 dup3 lt three_1_2_skip jumpi
                swap2               // 2 1 0
                swap1               // 1 2 0
                swap2               // 0 2 1
            three_1_2_skip:         // 0 1 2
                dup3 dup2 lt three_0_2_skip jumpi
                swap2
            three_0_2_skip:         // 0 1 2
                dup2 dup2 lt three_0_1_skip jumpi
                swap1
            three_0_1_skip:         // 0 1 2 p1 p2 p
            dup6 mstore             // 1 2 p1 p2 p
            swap3 mstore            // p1 1 p
            mstore                  // p

            jump(finished_insertion_sort)

            sort_four:
                dup1 0x60 add
                dup2 0x40 add
                dup3 0x20 add
                dup3 mload          // 3 p1 p2 p3 p
                dup3 mload
                dup3 mload          // 1 2 3 p1 p2 p3 p
                dup7 mload          // 0 1 2 3 p1 p2 p3

            dup2 dup2 lt four_0_1_skip jumpi
            swap1
            four_0_1_skip:          // 0 1 2 3 p
            dup4 dup4 lt four_2_3_skip jumpi
            swap3                   // 3 1 2 0
            swap2                   // 2 1 3 0
            swap3                   // 0 1 3 2
            four_2_3_skip:          // 0 1 2 3 p
            dup3 dup2 lt four_0_2_skip jumpi
            swap2
            four_0_2_skip:          // 0 1 2 3 p
            dup4 dup3 lt four_1_3_skip jumpi
            swap3 swap1 swap3
            four_1_3_skip:          // 0 1 2 3 p
            dup3 dup3 lt four_1_2_skip jumpi
            swap1 swap2 swap1
            four_1_2_skip:          // 0 1 2 3 p1 p2 p3 p
            dup8 mstore             // 1 2 3 p1 p2 p3 p
            swap4 mstore            // 3 p1 1 p3 p
            swap2 mstore
            swap1 mstore
            
            jump(finished_insertion_sort)
        
            sort_five:
                dup1 0x80 add
                dup2 0x60 add
                dup3 0x40 add
                dup4 0x20 add       // p1 p2 p3 p4 p
                dup4 mload          // 4 p1 p2 p3 p4 p
                dup4 mload
                dup4 mload
                dup4 mload
                dup9 mload          // 0 1 2 3 4 p1 p2 p3 p4 p
            dup2 dup2 lt five_0_1_skip jumpi
            swap1
            five_0_1_skip:          // 0 1 2 3 4
            dup5 dup5 lt five_3_4_skip jumpi
            swap3 swap4 swap3
            five_3_4_skip:          // 0 1 2 3 4
            dup5 dup4 lt five_2_4_skip jumpi
            swap2 swap4 swap2
            five_2_4_skip:          // 0 1 2 3 4
            dup4 dup4 lt five_2_3_skip jumpi
            swap2 swap3 swap2
            five_2_3_skip:          // 0 1 2 3 4
            dup5 dup3 lt five_1_4_skip jumpi
            swap1 swap4 swap1
            five_1_4_skip:          // 0 1 2 3 4
            dup4 dup2 lt five_0_3_skip jumpi
            swap3
            five_0_3_skip:          // 0 1 2 3 4
            dup3 dup2 lt five_0_2_skip jumpi
            swap2
            five_0_2_skip:
            dup4 dup3 lt five_1_3_skip jumpi
            swap1 swap3 swap1
            five_1_3_skip:          // 0 1 2 3 4
            dup3 dup3 lt five_1_2_skip jumpi
            swap1 swap2 swap1
            five_1_2_skip:          // 0 1 2 3 4 p1 p2 p3 p4 p
            dup10 mstore            // 1 2 3 4 p1 p2 p3 p4 p
            swap5 mstore            // 3 4 p1 1 p3 p4 p
            swap5 mstore            // p1 1 p3 3 p
            mstore                  // p3 3 p
            mstore                  // p
            jump(finished_insertion_sort)
                
            sort_six:
                dup1 0xa0 add
                dup2 0x80 add
                dup3 0x60 add
                dup4 0x40 add
                dup5 0x20 add       // p1 p2 p3 p4 p
                dup5 mload          // 4 p1 p2 p3 p4 p
                dup5 mload
                dup5 mload
                dup5 mload
                dup5 mload
                dup11 mload          // 0 1 2 3 4 5 p1 p2 p3 p4 p5 p
                
                dup3 dup3 lt six_1_2_skip jumpi
                swap1 swap2 swap1
                six_1_2_skip:
                dup6 dup6 lt six_4_5_skip jumpi
                swap4 swap5 swap4
                six_4_5_skip:
                dup3 dup2 lt six_0_2_skip jumpi
                swap2
                six_0_2_skip:
                dup6 dup5 lt six_3_5_skip jumpi
                swap3 swap5 swap3
                six_3_5_skip:
                dup2 dup2 lt six_0_1_skip jumpi
                swap1
                six_0_1_skip:
                dup5 dup5 lt six_3_4_skip jumpi
                swap3 swap4 swap3
                six_3_4_skip:
                dup6 dup4 lt six_2_5_skip jumpi
                swap2 swap5 swap2
                six_2_5_skip:
                dup4 dup2 lt six_0_3_skip jumpi
                swap3
                six_0_3_skip:
                dup5 dup3 lt six_1_4_skip jumpi
                swap1 swap4 swap1
                six_1_4_skip:
                dup5 dup4 lt six_2_4_skip jumpi
                swap2 swap4 swap2
                six_2_4_skip:
                dup4 dup3 lt six_1_3_skip jumpi
                swap1 swap3 swap1
                six_1_3_skip:
                dup4 dup4 lt six_2_3_skip jumpi
                swap2 swap3 swap2
                six_2_3_skip:           // 0 1 2 3 4 5 p1 p2 p3 p4 p5 p
                dup12 mstore            // 1 2 3 4 5 p1 p2 p3 p4 p5 p
                swap6 mstore            // 3 4 5 p1 1 p3 p4 p5 p
                swap6 mstore            // 5 p1 1 p3 3 p5 p
                swap2 swap1 mstore      // 5 p3 3 p5 p
                swap2 swap1 mstore      // 5 p5 p
                swap1 mstore
                jump(finished_insertion_sort)
                
            sort_seven:
                dup1 0xc0 add
                dup2 0xa0 add
                dup3 0x80 add
                dup4 0x60 add
                dup5 0x40 add
                dup6 0x20 add       // p1 p2 p3 p4 p5 p6 p
                dup6 mload          // 4 p1 p2 p3 p4 p
                dup6 mload
                dup6 mload
                dup6 mload
                dup6 mload
                dup6 mload
                dup13 mload          // 0 1 2 3 4 5 6 p1 p2 p3 p4 p5 p6 p
                
                dup3 dup3 lt seven_1_2_skip jumpi
                swap1 swap2 swap1
                seven_1_2_skip:
                dup5 dup5 lt seven_3_4_skip jumpi
                swap3 swap4 swap3
                seven_3_4_skip:
                dup7 dup7 lt seven_5_6_skip jumpi
                swap5 swap6 swap5
                seven_5_6_skip:
                dup3 dup2 lt seven_0_2_skip jumpi
                swap2
                seven_0_2_skip:
                dup6 dup5 lt seven_3_5_skip jumpi
                swap3 swap5 swap3
                seven_3_5_skip:
                dup7 dup6 lt seven_4_6_skip jumpi
                swap4 swap6 swap4
                seven_4_6_skip:
                dup2 dup2 lt seven_0_1_skip jumpi
                swap1
                seven_0_1_skip:
                dup6 dup6 lt seven_4_5_skip jumpi
                swap4 swap5 swap4
                seven_4_5_skip:
                dup7 dup4 lt seven_2_6_skip jumpi
                swap2 swap6 swap2
                seven_2_6_skip:
                dup5 dup2 lt seven_0_4_skip jumpi
                swap4
                seven_0_4_skip:
                dup6 dup3 lt seven_1_5_skip jumpi
                swap1 swap5 swap1
                seven_1_5_skip:
                dup4 dup2 lt seven_0_3_skip jumpi
                swap3
                seven_0_3_skip:
                dup6 dup4 lt seven_2_5_skip jumpi
                swap2 swap5 swap2
                seven_2_5_skip:
                dup4 dup3 lt seven_1_3_skip jumpi
                swap1 swap3 swap1
                seven_1_3_skip:
                dup5 dup4 lt seven_2_4_skip jumpi
                swap2 swap4 swap2
                seven_2_4_skip:
                dup4 dup4 lt seven_2_3_skip jumpi
                swap2 swap3 swap2
                seven_2_3_skip:         // 0 1 2 3 4 5 6 p1 p2 p3 p4 p5 p6 p
                dup14 mstore            // 1 2 3 4 5 6 p1 p2 p3 p4 p5 p6 p
                swap7 mstore            // 3 4 5 6 p1 1 p3 p4 p5 p6 p
                swap7 mstore            // 5 6 p1 1 p3 3 p5 p6 p
                swap7 mstore            // p1 1 p3 3 p5 5 p
                mstore
                mstore
                mstore
                jump(finished_insertion_sort)
                
                
            sort_eight:
                dup1 0xe0 add
                dup2 0xc0 add
                dup3 0xa0 add
                dup4 0x80 add
                dup5 0x60 add
                dup6 0x40 add
                dup7 0x20 add       // p1 p2 p3 p4 p5 p6 p
                dup7 mload          // 4 p1 p2 p3 p4 p
                dup7 mload
                dup7 mload
                dup7 mload
                dup7 mload
                dup7 mload
                dup7 mload
                dup15 mload          // 0 1 2 3 4 5 6 7 p1 p2 p3 p4 p5 p6 p7 p
                
                dup2 dup2 lt eight_0_1_skip jumpi
                swap1
                eight_0_1_skip:
                dup4 dup4 lt eight_2_3_skip jumpi
                swap2 swap3 swap2
                eight_2_3_skip:
                dup6 dup6 lt eight_4_5_skip jumpi
                swap4 swap5 swap4
                eight_4_5_skip:
                dup8 dup8 lt eight_6_7_skip jumpi
                swap6 swap7 swap6
                eight_6_7_skip:
                dup3 dup2 lt eight_0_2_skip jumpi
                swap2
                eight_0_2_skip:
                dup4 dup3 lt eight_1_3_skip jumpi
                swap1 swap3 swap1
                eight_1_3_skip:
                dup7 dup6 lt eight_4_6_skip jumpi
                swap4 swap6 swap4
                eight_4_6_skip:
                dup8 dup7 lt eight_5_7_skip jumpi
                swap5 swap7 swap5
                eight_5_7_skip:
                dup3 dup3 lt eight_1_2_skip jumpi
                swap1 swap2 swap1
                eight_1_2_skip:
                dup7 dup7 lt eight_5_6_skip jumpi
                swap5 swap6 swap4
                eight_5_6_skip:
                dup5 dup2 lt eight_0_4_skip jumpi
                swap4
                eight_0_4_skip:
                dup8 dup5 lt eight_3_7_skip jumpi
                swap7 swap3 swap7
                eight_3_7_skip:
                dup6 dup3 lt eight_1_5_skip jumpi
                swap1 swap5 swap1
                eight_1_5_skip:
                dup7 dup4 lt eight_2_6_skip jumpi
                swap2 swap6 swap2
                eight_2_6_skip:
                dup5 dup3 lt eight_1_4_skip jumpi
                swap1 swap4 swap1
                eight_1_4_skip:
                dup7 dup5 lt eight_3_6_skip jumpi
                swap3 swap6 swap3
                eight_3_6_skip:
                dup5 dup4 lt eight_2_4_skip jumpi
                swap2 swap4 swap2
                eight_2_4_skip:
                dup6 dup5 lt eight_3_5_skip jumpi
                swap3 swap5 swap3
                eight_3_5_skip:
                dup5 dup5 lt eight_3_4_skip jumpi
                swap3 swap4 swap3
                eight_3_4_skip:         // 0 1 2 3 4 5 6 7 p1 p2 p3 p4 p5 p6 p7 p
                dup16 mstore            // 1 2 3 4 5 6 7 p1 p2 p3 p4 p5 p6 p7 p
                swap8 mstore            // 3 4 5 6 7 p1 1 p3 p4 p5 p6 p7 p
                swap8 mstore            // 5 6 7 p1 1 p3 3 p5 p6 p7 p
                swap8 mstore            // 7 p1 1 p3 3 p5 5 p7 p
                swap2 swap1 mstore      // 7 p3 3 p5 5 p7 p
                swap2 swap1 mstore      // 7 p5 5 p7 p
                swap2 swap1 mstore      // 7 p7 p
                swap1 mstore
                jump(finished_insertion_sort)
        }
    }
    function sort(uint[] input) external view returns(uint[]) {
        assembly {
            calldatacopy(0, 0x04, calldatasize)
            let it := 0x60
            let size := sub(calldatasize, 0x24)
            let end := add(size, 0x20)
            let prev := mload(0x40)
            let current
            check_if_perfect_start:
                jumpi(check_if_perfect_skip, gt(prev, mload(it)))
                prev := mload(it)
                it := add(it, 0x20)
                jumpi(check_if_perfect_start, lt(it, end))
            // hey, it's perfect!
            return(0x00, add(end, 0x40))
            check_if_perfect_skip:


            let stack_ptr := add(msize, 0x20)
            let stack_ptr_test := sub(msize, 0x20)

            mstore(msize, 0x40)
            mstore(msize, size)
            let p_start, p_end, p

            stack_loop_start:
                p_end := mload(stack_ptr)
                p_start := mload(sub(stack_ptr, 0x20))
                stack_ptr := sub(stack_ptr, 0x40)
                jumpi(proceed, lt(p_start, p_end))
                jump(end_test)
                proceed:
                p := partition(p_start, p_end)
                mstore(add(stack_ptr, 0x20), p_start)
                mstore(add(stack_ptr, 0x40), sub(p, 0x20))
                mstore(add(stack_ptr, 0x60), add(p, 0x20))
                mstore(add(stack_ptr, 0x80), p_end)
                stack_ptr := add(stack_ptr, 0x80)
            end_test:
                jumpi(stack_loop_start, gt(stack_ptr, stack_ptr_test))

            // quickSort(0x40, size)
            return(0x00, add(end, 0x40))
            function quickSort(p_low, p_high) {
                if lt(p_low, p_high) {
                    let pi := partition(p_low, p_high)
                    quickSort(p_low, sub(pi, 0x20))
                    quickSort(add(pi, 0x20), p_high)
                }
            }
            function partition(p_low, p_high) -> v {
                let i := p_low
                let t := 0x00
                let moduli := div(sub(p_high, p_low), 0x20)
                let factor := add(p_low, mul(mulmod(gas, 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfe47, moduli), 0x20))
                let pivot := mload(factor)
                mstore(factor, mload(p_high))
                mstore(p_high, pivot)
                for {let j := p_low} lt(j, p_high) {j := add(j, 0x20)} {
                    if lt(mload(j), pivot) {
                        t := mload(j)
                        mstore(j, mload(i))
                        mstore(i, t)
                        i := add(i, 0x20)
                    }
                }
                v := i
                t := mload(p_high)
                mstore(p_high, mload(v))
                mstore(v, t)
            }
        }
    }
}