Skip to content

Instantly share code, notes, and snippets.

@highskore

highskore/Quicksort.huff

Last active March 11, 2024 04:07
Show Gist options
  • Save highskore/63578bc2bdaaab3458681924ec5ad67a to your computer and use it in GitHub Desktop.
Save highskore/63578bc2bdaaab3458681924ec5ad67a to your computer and use it in GitHub Desktop.
Download ZIP
Recursive QuickSort in Huff
Raw
Quicksort.huff
/// @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