Last active
March 11, 2024 04:07
-
-
Save highskore/63578bc2bdaaab3458681924ec5ad67a to your computer and use it in GitHub Desktop.
Recursive QuickSort in Huff
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// @notice Sort | |
/// @notice Loads the unsorted array from calldata and returns the sorted array | |
#define macro SORT() = takes (0) returns (0) { | |
// copy array from calldata to memory | |
0x24 calldataload // [array_length] | |
0x20 // [0x20, array_length] | |
mul // [32 * array_length] | |
0x44 // [0x44, 32 * array_length] | |
0x00 // [0x00, 0x44, 32 * array_length] | |
calldatacopy | |
// setup stack | |
sorted // [sorted] | |
0x01 // [0x01, sorted] | |
0x24 calldataload // [array_length, 0x01, sorted] | |
sub // [array_length - 1, sorted] | |
0x00 // [0x00, array_length - 1, sorted] | |
QUICK_SORT() | |
// return | |
sorted: | |
0x24 calldataload // [array_length] | |
0x20 // [0x20, array_length] | |
mul // [32 * array_length] | |
0x00 // [0x00, array_length * 32] | |
return | |
} | |
/// @notice Quick Sort | |
/// @notice Sorts the array in memory | |
#define macro QUICK_SORT() = takes (3) returns (0) { | |
recursion: | |
// // [left, right, jumpdest] | |
dup2 // [j, left, right, jumpdest] | |
dup2 // [i, j, left, right, jumpdest] | |
dup2 // [j, i, j, left, right, jumpdest] | |
dup2 // [i, j, i, j, left, right, jumpdest] | |
// if (i == j) return | |
eq // [i == j, i, j, left, right, jumpdest] | |
equals jumpi // [equals, i == j, i, j, left, right, jumpdest] | |
// get pivot index | |
0x02 // [0x02, i, j, left, right, jumpdest] | |
dup2 // [i, 0x02, i, j, left, right, jumpdest] | |
dup4 // [j, i, 0x02, i, j, left, right, jumpdest] | |
sub // [j - i, 0x02, i, j, left, right, jumpdest] | |
sdiv // [(j - i) / 2, i, j, left, right, jumpdest] | |
dup2 // [i, (j - i) / 2, i, j, left, right, jumpdest] | |
add // [i + (j - i) / 2, i, j, left, right, jumpdest] | |
// get pivot value | |
0x20 // [0x20, i + (i - j) / 2, i, j, left, right, jumpdest] | |
mul // [32 * (i + (i - j) / 2), i, j, left, right, jumpdest] | |
mload // [pivot, i, j, left, right, jumpdest] | |
// while (i <= j) | |
while: // [pivot, i, j, left, right, jumpdest] | |
dup3 // [j, pivot, i, j, left, right, jumpdest] | |
dup3 // [i, j, pivot, i, j, left, right, jumpdest] | |
sgt // [i > j, pivot, i, j, left, right, jumpdest] | |
continue_left jumpi // [pivot, i, j, left, right, jumpdest] | |
// while (array[i] < pivot) | |
while_p_gt_i: | |
dup2 // [i, pivot, i, j, left, right, jumpdest] | |
0x20 // [0x20, i, pivot, i, j, left, right, jumpdest] | |
mul // [32 * i, pivot, i, j, left, right, jumpdest] | |
mload // [array[i], pivot, i, j, left, right, jumpdest] | |
dup2 // [pivot, array[i], pivot, i, j, left, right, jumpdest] | |
gt // [pivot > array[i], pivot, i, j, left, right, jumpdest] | |
iszero // [pivot <= array[i], pivot, i, j, left, right, jumpdest] | |
while_p_lt_j // [while_p_lt_j, pivot <= array[i], pivot, i, j, left, right, jumpdest] | |
jumpi // [pivot, i, j, left, right, jumpdest] | |
// i++ | |
0x01 // [0x01, pivot, i, j, left, right, jumpdest] | |
dup3 // [i, 0x01, pivot, i, j, left, right, jumpdest] | |
add // [i + 1, pivot, i, j, left, right, jumpdest] | |
swap2 // [i, pivot, i + 1, j, left, right, jumpdest] | |
pop // [pivot, i + 1, j, left, right, jumpdest] | |
while_p_gt_i // [while_p_gt_i, pivot, i + 1, j, left, right, jumpdest] | |
jump // [pivot, i + 1, j, left, right, jumpdest] | |
// while array[j] > pivotvalue | |
while_p_lt_j: | |
dup3 // [j, pivot, i, j, left, right, jumpdest] | |
0x20 // [0x20, j, pivot, i, j, left, right, jumpdest] | |
mul // [32 * j, pivot, i, j, left, right, jumpdest] | |
mload // [array[j], pivot, i, j, left, right, jumpdest] | |
dup2 // [pivot, array[j], pivot, i, j, left, right, jumpdest] | |
lt // [pivot < array[j], pivot, i, j, left, right, jumpdest] | |
iszero // [pivot >= array[j], pivot, i, j, left, right, jumpdest] | |
continue_p_lt_j // [continue_p_lt_j, pivot >= array[j], pivot, i, j, left, right, jumpdest] | |
jumpi // [pivot, i, j, left, right, jumpdest] | |
// j-- | |
0x01 // [0x01, pivot, i, j, left, right, jumpdest] | |
dup4 // [j, 0x01, pivot, i, j, left, right, jumpdest] | |
sub // [j - 1, pivot, i, j, left, right, jumpdest] | |
swap3 // [j, pivot, i, j-1, left, right, jumpdest] | |
pop // [pivot, i, j-1, left, right, jumpdest] | |
while_p_lt_j // [while_p_lt_j, pivot, i, j-1, left, right, jumpdest] | |
jump // [pivot, i, j-1, left, right, jumpdest] | |
continue_p_lt_j: | |
// if (i <= j) | |
dup2 // [i, pivot, i, j, left, right, jumpdest] | |
dup4 // [j, i, pivot, i, j, left, right, jumpdest] | |
slt // [j < i, pivot, i, j, left, right, jumpdest] | |
continue_if jumpi // [pivot, i, j, left, right, jumpdest] | |
// swap array[i] and array[j] | |
dup3 // [j, pivot, i, j, left, right, jumpdest] | |
dup3 // [i, j, pivot, i, j, left, right, jumpdest] | |
dup2 // [j, i, j, pivot, i, j, left, right, jumpdest] | |
dup2 // [i, j, i, j, pivot, i, j, left, right, jumpdest] | |
0x20 // [0x20, i, j, i, j, pivot, i, j, left, right, jumpdest] | |
mul // [32 * i, j, i, j, pivot, i, j, left, right, jumpdest] | |
mload // [array[i], j, i, j, pivot, i, j, left, right, jumpdest] | |
swap1 // [j, array[i], i, j, pivot, i, j, left, right, jumpdest] | |
0x20 // [0x20, j, array[i], i, j, pivot, i, j, left, right, jumpdest] | |
mul // [32 * j, array[i], i, j, pivot, i, j, left, right, jumpdest] | |
mload // [array[j], array[i], i, j, pivot, i, j, left, right, jumpdest] | |
swap3 // [j, array[i], i, array[j], pivot, i, j, left, right, jumpdest] | |
0x20 // [0x20, j, array[i], i, array[j], pivot, i, j, left, right, jumpdest] | |
mul // [32 * j, array[i], i, array[j], pivot, i, j, left, right, jumpdest] | |
mstore // [i, array[j], pivot, i, j, left, right, jumpdest] | |
0x20 // [0x20, i, array[j], pivot, i, j, left, right, jumpdest] | |
mul // [32 * i, array[j], pivot, i, j, left, right, jumpdest] | |
mstore // [pivot, i, j, left, right, jumpdest] | |
// i++ | |
0x01 // [0x01, pivot, i, j, left, right, jumpdest] | |
dup3 // [i, 0x01, pivot, i, j, left, right, jumpdest] | |
add // [i + 1, pivot, i, j, left, right, jumpdest] | |
swap2 // [i, pivot, i + 1, j, left, right, jumpdest] | |
pop // [pivot, i + 1, j, left, right, jumpdest] | |
// j-- | |
0x01 // [0x01, pivot, i, j, left, right, jumpdest] | |
dup4 // [j, 0x01, pivot, i, j, left, right, jumpdest] | |
sub // [j - 1, pivot, i, j, left, right, jumpdest] | |
swap3 // [j, pivot, i, j-1, left, right, jumpdest] | |
pop // [pivot, i, j-1, left, right, jumpdest] | |
continue_if: | |
while jump | |
continue_left: // [pivot, i, j, left, right, jumpdest] | |
pop // [i, j, left, right, jumpdest] | |
// if (left < j) | |
dup2 // [j, i, j, left, right, jumpdest] | |
dup4 // [left, j, i, j, left, right, jumpdest] | |
slt // [left < j, i, j, left, right, jumpdest] | |
iszero // [left >= j, i, j, left, right, jumpdest] | |
continue_right jumpi // [i, j, left, right, jumpdest] | |
// quicksort(array, left, j) | |
continue_right // [continue_right, i, j, left, right, jumpdest] | |
dup3 // [j, continue_right, i, j, left, right, jumpdest] | |
dup5 // [left, j, continue_right, i, j, left, right, jumpdest] | |
recursion jump // [left, j, continue_right, i, j, left, right, jumpdest] | |
// if (i < right) | |
continue_right: // [i, j, left, right, jumpdest] | |
dup4 // [right, i, j, left, right, jumpdest] | |
dup2 // [i, right, i, j, left, right, jumpdest] | |
slt // [i < right, i, j, left, right, jumpdest] | |
iszero // [i >= right, i, j, left, right, jumpdest] | |
equals jumpi // [i, j, left, right, jumpdest] | |
// quicksort(array, i, right) | |
equals // [equals, i, j, left, right, jumpdest] | |
dup5 // [right, equals, i, j, left, right, jumpdest] | |
dup3 // [i, right, equals, i, j, left, right, jumpdest] | |
recursion jump // [i, right, equals, i, j, left, right, jumpdest] | |
equals: // [i, j, left, right, jumpdest] | |
pop // [j, left, right, jumpdest] | |
pop // [left, right, jumpdest] | |
pop // [right, jumpdest] | |
pop // [jumpdest] | |
jump // | |
} | |
#define macro MAIN() = takes (0) returns (0) { | |
// function sort(uint[]) returns (uint[]) | |
SORT() | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment