Submission 41da0025...
/**
* 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)
}
}
}
}