Quiz: Quicksort
In this quiz you are supposed to write an assembly program with some more complex functions. The program should first print a string, then sort the characters of the string and finally print the sorted result:
1 2 3 | theon$ quicksort
hello, world!
!,dehllloorw
|
For sorting you should write a function that implements the Quicksort algorithm. However, this assignment is not about the theoretical background of sorting algorithms. The purpose is to practise the calling conventions that where introduced in this session. Furthermore, you should get some idea how a compiler can translate C code into assembly code (with all optimization flags turned of, i.e. -O0). For that sake you will find a complete C implementation for the assigned problem and also a variant rewritten in spaghetti code. Translate the spaghetti code statement by statement into assembly code.
On theon submit your program with the command
submit hpc quiz12 quicksort.s
Reading assignment
This interview with a Microsoft developer is more or less on-topic Russell Hadley: The Route to C++ Code Optimization. He works on the C++ compiler team and gives a not to technical talk some overview how compilers work, apply optimizations and finally generate assembly code. I think a lot will make sense to you after this session, or even sound familiar to you by know. For example, at minute 1:30 we mentions how nice C++ code gets translated into spaghetti code). It's also interesting to see that the guy is not using the Visual Studio IDE but Emacs (besides Vim the only legit alternative).
I also stumbled over this article The Mistakes I Made As a Beginner Programmer. This is not directly related to the topic of Session 10 but about programming in general (it does not matter that he uses examples from JavaScript). It's great and you should read it. I love and totally agree to quotes like “For example, if you are not consistent with your indentation and capitalization, you should simply lose your license to code.” or “Expert programmers love errors. Newbies hate them.”.
About the subscript notation used in the C code examples
In the functions you will see the notation A[i] which is equivalent to *(A+i). The variable A is declared with type char *, hence it is a pointer to a character
With *(A+i) the character with address A+i is dereferenced:
And A[i] is just a more readable notation for that:
In the assembly code the you can use movzbq (%X, %Y), %Z for fetching and movb %X, (%Y, %Z) for storing the i-the character:
-
If %X contains the value of A, i.e. the address of the first character, and %Y contains the index i then movzbq (%X, %Y), %Z fetches A[i] into register %Z.
-
If %Y contains the value of A, i.e. the address of the first character, and %Z contains the index i then movb %X, (%Y, %Z) stores the least significant byte from %X in the memory location A[i].
When we discuss pointer arithmetic in C you will see why it makes sense that the fetch and store operations in the instruction set have further variants with a scaling parameter. Here the secret in short: When you have a pointer A then in general A+i is not the address of A plus i. Instead it is the address of A plus i times the size of the elements. For example, if A points to quad word integers, let's say it has type int64_t * or type uint64_t *, then “A + i” means “address stored in A plus 8*i”. In that case, if the value of variable A is in %X and the value of i in %Y then movq (%X, %Y, 8), %Z can be used for fetching a quad word into %Z. And vice versa, with movq %X, (%Y, %Z, 8) an instruction is provided that can be used for storing an array element.
Example for sorting a string with bubble sort
This program is basically solving the problem with the bubble sort algorithm instead of the Quicksort. For translating this manually into assembly code the same approach is followed. Some C code first get rewritten in a primitive variant that then can be translated statement by statement (and you will find here all ingredients needed for the quicksort assignment).
This is the initial C code:
// -- Some adjustments for didactic reasons ----------
typedef unsigned long uint64_t; // ok on theseus
int putchar ( int character );
// ---------------------------------------------------
void
bubblesort(char *A, uint64_t n)
{
uint64_t swapped;
do {
swapped = 0;
for (uint64_t i=1; i<n; ++i) {
if (A[i-1] > A[i]) {
char tmp = A[i];
A[i] = A[i-1];
A[i-1] = tmp;
swapped = 1;
}
}
--n;
} while (swapped);
}
void
puts(char *str)
{
while (*str) {
putchar(*str++);
}
putchar('\n');
}
uint64_t
strlen(char *str)
{
char *ch = str;
while (*ch) {
++ch;
}
return ch - str;
}
char msg[] = "hello, world!";
int
main()
{
puts(msg);
bubblesort(msg, strlen(msg));
puts(msg);
}
As we are reimplementing puts and strlen from the C library (with a slightly different function signature) you get some annoying warnings when you compile that. For ignoring this you can use the option -Wno-builtin-declaration-mismatch:
theon$ gcc -Wno-builtin-declaration-mismatch -o bubblesort bubblesort.c theon$ bubblesort hello, world! !,dehllloorw theon$
The bubble sort example with C spaghetti code
Procedure bublesort has 3 local variables. It is conveninet that you can declare local variables within compound statements. Hovever, technically it is eqivalent to declare all local variables at the beginning of the function body:
|
|
Next the nice to read loop-statements and the if-statements can be rewritten with more primitive statements that are easy to translate into chunks of assembly code:
|
|
This transformation of readable code into spaghetti code gets done by starting with the most outer control flow statement, describing its meaning with a flowchart and then expressing it with spaghetti code. You then can continue by repeating the procedure for nested controlstructures etc.
So we begin with the do-statement in the bubble sort code which can be described and rewritten as follows:
|
|
The next inner control flow statement is the for-loop:
|
And the most inner control stament can be rewritten as follows
|
Finally we reached the most inner control statement:
|
|
Why is it called spaghetti code?
I think you already got the idea. But nonetheless, have a look at the corresponding flowchart:
|
Complete spaghetti code
Here the complete beast:
// -- Some adjustments for didactic reasons ----------
typedef unsigned long uint64_t; // ok on theseus
int putchar ( int character );
// ---------------------------------------------------
void
bubblesort(char *A, uint64_t n)
{
uint64_t swapped;
uint64_t i;
char tmp;
bubblesort_do:
swapped = 0;
i = 1;
bubblesort_for:
if (i >= n)
goto bubblesort_endfor;
if (A[i-1] <= A[i])
goto bubblesort_endif;
tmp = A[i];
A[i] = A[i-1];
A[i-1] = tmp;
swapped = 1;
bubblesort_endif:
i = i + 1;
goto bubblesort_for;
n = n - 1;
bubblesort_endfor:
if (swapped)
goto bubblesort_do;
}
void
puts(char *str)
{
while (*str) {
putchar(*str++);
}
putchar('\n');
}
uint64_t
strlen(char *str)
{
char *ch = str;
while (*ch) {
++ch;
}
return ch - str;
}
char msg[] = "hello, world!";
int
main()
{
puts(msg);
bubblesort(msg, strlen(msg));
puts(msg);
}
theon$ gcc -Wno-builtin-declaration-mismatch -o bubblesort bubblesort_spaghetti.c theon$ bubblesort hello, world! !,dehllloorw theon$
Implementing the bubble sort example in assembly for the ULM
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 | .equ FP, 1
.equ SP, 2
.equ RET, 3
//------------------------------------------------------------------------------
// Function _start()
//------------------------------------------------------------------------------
.equ ret, 0
.equ fp, 8
.equ rval, 16
.text
_start:
// begin of the function body
ldzwq 0, %SP
// call function main()
subq 24, %SP, %SP
ldzwq main, %4
jmp %4, %RET
movq rval(%SP), %4
addq 24, %SP, %SP
halt %4
//------------------------------------------------------------------------------
// Global variables
//------------------------------------------------------------------------------
.data
msg .string "hello, world!"
//------------------------------------------------------------------------------
// Function main()
//------------------------------------------------------------------------------
.equ ret, 0
.equ fp, 8
.equ rval, 16
.text
main:
// function prologue
movq %RET, ret(%SP)
movq %FP, fp(%SP)
addq 0, %SP, %FP
// begin of the function body
/*
puts(msg);
*/
// call procedure puts(msg)
subq 24, %SP, %SP
# store argument msg in 16(%SP)
ldzwq msg, %4
movq %4, 16(%SP)
ldzwq puts, %4
jmp %4, %RET
movq rval(%SP), %4
addq 24, %SP, %SP
/*
bubblesort(msg, strlen(msg));
*/
// call procedure bubblesort(msg, strlen(msg))
subq 32, %SP, %SP
# store argument msg in 16(%SP)
ldzwq msg, %4
movq %4, 16(%SP)
# store argument strlen(msg) in 24(%SP)
// call function strlen(msg)
subq 32, %SP, %SP
# store argument msg in 24(%SP)
ldzwq msg, %4
movq %4, 24(%SP)
ldzwq strlen, %4
jmp %4, %RET
movq rval(%SP), %4
addq 32, %SP, %SP
movq %4, 24(%SP)
ldzwq bubblesort, %4
jmp %4, %RET
addq 32, %SP, %SP
/*
puts(msg);
*/
// call procedure puts(msg)
subq 24, %SP, %SP
# store argument msg in 16(%SP)
ldzwq msg, %4
movq %4, 16(%SP)
ldzwq puts, %4
jmp %4, %RET
movq rval(%SP), %4
addq 24, %SP, %SP
/*
return 0;
*/
ldzwq 0, %4
movq %4, rval(%FP)
jmp main.leave
// end of the function body
// function epilogue
main.leave:
addq 0, %FP, %SP
movq fp(%SP), %FP
movq ret(%SP), %RET
jmp %RET, %0
//------------------------------------------------------------------------------
// Procedure puts(str)
//------------------------------------------------------------------------------
.equ ret, 0
.equ fp, 8
// procedure arguments
.equ str, 16
.text
puts:
// function prologue
movq %RET, ret(%SP)
movq %FP, fp(%SP)
addq 0, %SP, %FP
// reserve space for 0 local variables.
subq 0, %SP, %SP
// begin of the function body
/*
if (*str == 0)
goto puts.leave;
*/
puts.while
movq str(%FP), %4
movzbq (%4), %4
subq 0, %4, %0
jz puts.while.done
/*
putchar(*str);
*/
movq str(%FP), %4
movzbq (%4), %4
putc %4
/*
str = str + 1;
*/
movq str(%FP), %4
addq 1, %4, %4
movq %4, str(%FP)
/*
goto puts.while;
*/
jmp puts.while
puts.while.done:
/*
putchar('\n');
*/
putc '\n'
// end of the function body
// function epilogue
puts.leave:
addq 0, %FP, %SP
movq fp(%SP), %FP
movq ret(%SP), %RET
jmp %RET, %0
//------------------------------------------------------------------------------
// Function strlen(str)
//------------------------------------------------------------------------------
.equ ret, 0
.equ fp, 8
.equ rval, 16
// function arguments
.equ str, 24
// local variables
.equ ch, -8
.text
strlen:
// function prologue
movq %RET, ret(%SP)
movq %FP, fp(%SP)
addq 0, %SP, %FP
// reserve space for 1 local variables.
subq 8, %SP, %SP
// begin of the function body
/*
ch = str;
*/
movq str(%FP), %4
movq %4, ch(%FP)
/*
if (*ch == 0)
goto strlen.while.done;
*/
strlen.while:
movq ch(%FP), %4
movzbq (%4), %4
subq 0, %4, %0
jz strlen.while.done
/*
ch = ch + 1;
*/
movq ch(%FP), %4
addq 1, %4, %4
movq %4, ch(%FP)
/*
goto strlen.while;
*/
jmp strlen.while
strlen.while.done:
/*
return ch - str;
*/
movq ch(%FP), %4
movq str(%FP), %5
subq %5, %4, %4
movq %4, rval(%FP)
jmp strlen.leave
// end of the function body
// function epilogue
strlen.leave:
addq 0, %FP, %SP
movq fp(%SP), %FP
movq ret(%SP), %RET
jmp %RET, %0
//------------------------------------------------------------------------------
// Procedure bubblesort(A, n)
//------------------------------------------------------------------------------
.equ ret, 0
.equ fp, 8
// procedure arguments
.equ A, 16
.equ n, A+8
// local variables
.equ swapped, -8
.equ i, swapped-8
.equ tmp, i-8
.text
bubblesort:
// function prologue
movq %RET, ret(%SP)
movq %FP, fp(%SP)
addq 0, %SP, %FP
// reserve space for 3 local variables.
subq 24, %SP, %SP
// begin of the function body
bubblesort_do:
/*
swapped = 0;
*/
ldzwq 0, %4
movq %4, swapped(%FP)
/*
i = 1;
*/
ldzwq 1, %4
movq %4, i(%FP)
bubblesort_for:
/*
if (i >= n)
goto bubblesort_endfor;
*/
movq i(%FP), %4
movq n(%FP), %5
subq %5, %4, %0
jae bubblesort_endfor
/*
if (A[i-1] <= A[i])
goto bubblesort_endif;
*/
movq i(%FP), %4
subq 1, %4, %4 # i-1
movq i(%FP), %5 # i
movq A(%FP), %6
movzbq (%6, %4), %4 # A[i-1]
movzbq (%6, %5), %5 # A[i]
subq %5, %4, %0
jbe bubblesort_endif
/*
tmp = A[i];
*/
movq i(%FP), %4 # i
movq A(%FP), %5
movzbq (%5, %4), %4 # A[i]
movb %4, tmp(%FP)
/*
A[i] = A[i-1];
*/
movq i(%FP), %4
subq 1, %4, %4 # i-1
movq i(%FP), %5 # i
movq A(%FP), %6
movzbq (%6, %4), %4 # fetch A[i-1]
movb %4, (%6, %5) # store A[i]
/*
A[i-1] = tmp;
*/
movzbq tmp(%FP), %4
movq i(%FP), %5
subq 1, %5, %5 # i-1
movq A(%FP), %6
movb %4, (%6, %5) # store A[i]
/*
swapped = 1;
*/
ldzwq 1, %4
movq %4, swapped(%FP)
bubblesort_endif
/*
i = i + 1;
*/
movq i(%FP), %4
addq 1, %4, %4
movq %4, i(%FP)
/*
goto bubblesort_for;
*/
jmp bubblesort_for
bubblesort_endfor:
/*
n = n - 1;
*/
movq n(%FP), %4
subq 1, %4, %4
movq %4, n(%FP)
/*
if (swapped)
goto bubblesort_do;
*/
movq swapped(%FP), %4
subq 0, %4, %0
jnz bubblesort_do
// end of the function body
// function epilogue
bubblesort.leave:
addq 0, %FP, %SP
movq fp(%SP), %FP
movq ret(%SP), %RET
jmp %RET, %0
|
theon$ ulmas -o bubblesort bubblesort.s theon$ ulm bubblesort hello, world! !,dehllloorw theon$
Example in C for sorting a string with Quicksort
// -- Some adjustments for didactic reasons ----------
typedef unsigned long uint64_t; // ok on theseus
typedef unsigned char uint8_t;
int putchar ( int character );
// ---------------------------------------------------
void
puts(char *str)
{
while (*str) {
putchar(*str++);
}
putchar('\n');
}
uint64_t
strlen(char *str)
{
char *ch = str;
while (*ch) {
++ch;
}
return ch - str;
}
void
quicksort(char *A, uint64_t n)
{
if (n < 2) {
return;
}
uint64_t p = n/2;
uint64_t left = 0;
uint64_t right = n - 1;
do {
while (A[left] < A[p]) {
++left;
}
while (A[p] < A[right]) {
--right;
}
if (left <= right) {
char tmp = A[left];
A[left] = A[right];
A[right] = tmp;
if (left == p) {
p = right;
} else if (right == p) {
p = left;
}
++left;
--right;
}
} while (left <= right);
quicksort(A, right + 1);
quicksort(A+left, n - left);
}
char msg[] = "hello, world!";
int
main()
{
puts(msg);
quicksort(msg, strlen(msg));
puts(msg);
}
Compile and run:
theon$ gcc -Wno-builtin-declaration-mismatch -o quicksort quicksort.c theon$ quicksort hello, world! !,dehllloorw theon$
Some C spaghetti code for the Quicksort example
// -- Some adjustments for didactic reasons ----------
typedef unsigned long uint64_t; // ok on theseus
typedef unsigned char uint8_t;
int putchar ( int character );
// ---------------------------------------------------
void
puts(char *str)
{
while (*str) {
putchar(*str++);
}
putchar('\n');
}
uint64_t
strlen(char *str)
{
char *ch = str;
while (*ch) {
++ch;
}
return ch - str;
}
void
quicksort(char *A, uint64_t n)
{
uint64_t p;
uint64_t left = 0;
uint64_t right = n - 1;
char tmp;
if (n < 2)
goto quicksort_done;
p = n/2;
left = 0;
right = n - 1;
quicksort_do:
quicksort_while_left:
if (A[left] >= A[p])
goto quicksort_endwhile_left;
left = left + 1;
goto quicksort_while_left;
quicksort_endwhile_left:
quicksort_while_right:
if (A[p] >= A[right])
goto quicksort_endwhile_right;
right = right - 1;
goto quicksort_while_right;
quicksort_endwhile_right:
if (left>right)
goto quicksort_endif_left_right;
tmp = A[left];
A[left] = A[right];
A[right] = tmp;
if (left != p)
goto quicksort_if_p_eq_right;
p = right;
goto quicksort_endif_p;
quicksort_if_p_eq_right:
if (right != p)
goto quicksort_endif_p;
p = left;
quicksort_endif_p:
left = left + 1;
right = right - 1;
quicksort_endif_left_right:
if (left <= right)
goto quicksort_do;
quicksort(A, right + 1);
quicksort(A+left, n - left);
quicksort_done:
;
}
char msg[] = "hello, world!";
int
main()
{
puts(msg);
quicksort(msg, strlen(msg));
puts(msg);
}
Compile and run:
theon$ gcc -Wno-builtin-declaration-mismatch -o quicksort quicksort_spaghetti.c theon$ quicksort hello, world! !,dehllloorw theon$
Skeleton for the Quicksort assembly program
For the quiz you can use the following skeleton. Function quicksort contains the labels from the corresponding C spaghetti code and the C statements in comments:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 | .equ FP, 1
.equ SP, 2
.equ RET, 3
//------------------------------------------------------------------------------
// Function _start()
//------------------------------------------------------------------------------
.equ ret, 0
.equ fp, 8
.equ rval, 16
.text
_start:
// begin of the function body
ldzwq 0, %SP
// call function main()
subq 24, %SP, %SP
ldzwq main, %4
jmp %4, %RET
movq rval(%SP), %4
addq 24, %SP, %SP
halt %4
//------------------------------------------------------------------------------
// Global variables
//------------------------------------------------------------------------------
.data
msg .string "hello, world!"
//------------------------------------------------------------------------------
// Function main()
//------------------------------------------------------------------------------
.equ ret, 0
.equ fp, 8
.equ rval, 16
.text
main:
// function prologue
movq %RET, ret(%SP)
movq %FP, fp(%SP)
addq 0, %SP, %FP
// begin of the function body
/*
puts(msg);
*/
// call procedure puts(msg)
subq 24, %SP, %SP
# store argument msg in 16(%SP)
ldzwq msg, %4
movq %4, 16(%SP)
ldzwq puts, %4
jmp %4, %RET
movq rval(%SP), %4
addq 24, %SP, %SP
/*
quicksort(msg, strlen(msg));
*/
// call procedure quicksort(msg, strlen(msg))
subq 32, %SP, %SP
# store argument msg in 16(%SP)
ldzwq msg, %4
movq %4, 16(%SP)
# store argument strlen(msg) in 24(%SP)
// call function strlen(msg)
subq 32, %SP, %SP
# store argument msg in 24(%SP)
ldzwq msg, %4
movq %4, 24(%SP)
ldzwq strlen, %4
jmp %4, %RET
movq rval(%SP), %4
addq 32, %SP, %SP
movq %4, 24(%SP)
ldzwq quicksort, %4
jmp %4, %RET
addq 32, %SP, %SP
/*
puts(msg);
*/
// call procedure puts(msg)
subq 24, %SP, %SP
# store argument msg in 16(%SP)
ldzwq msg, %4
movq %4, 16(%SP)
ldzwq puts, %4
jmp %4, %RET
movq rval(%SP), %4
addq 24, %SP, %SP
/*
return 0;
*/
ldzwq 0, %4
movq %4, rval(%FP)
jmp main.leave
// end of the function body
// function epilogue
main.leave:
addq 0, %FP, %SP
movq fp(%SP), %FP
movq ret(%SP), %RET
jmp %RET, %0
//------------------------------------------------------------------------------
// Procedure puts(str)
//------------------------------------------------------------------------------
.equ ret, 0
.equ fp, 8
// procedure arguments
.equ str, 16
.text
puts:
// function prologue
movq %RET, ret(%SP)
movq %FP, fp(%SP)
addq 0, %SP, %FP
// reserve space for 0 local variables.
subq 0, %SP, %SP
// begin of the function body
/*
if (*str == 0)
goto puts.leave;
*/
puts.while
movq str(%FP), %4
movzbq (%4), %4
subq 0, %4, %0
jz puts.while.done
/*
putchar(*str);
*/
movq str(%FP), %4
movzbq (%4), %4
putc %4
/*
str = str + 1;
*/
movq str(%FP), %4
addq 1, %4, %4
movq %4, str(%FP)
/*
goto puts.while;
*/
jmp puts.while
puts.while.done:
/*
putchar('\n');
*/
putc '\n'
// end of the function body
// function epilogue
puts.leave:
addq 0, %FP, %SP
movq fp(%SP), %FP
movq ret(%SP), %RET
jmp %RET, %0
//------------------------------------------------------------------------------
// Function strlen(str)
//------------------------------------------------------------------------------
.equ ret, 0
.equ fp, 8
.equ rval, 16
// function arguments
.equ str, 24
// local variables
.equ ch, -8
.text
strlen:
// function prologue
movq %RET, ret(%SP)
movq %FP, fp(%SP)
addq 0, %SP, %FP
// reserve space for 1 local variables.
subq 8, %SP, %SP
// begin of the function body
/*
ch = str;
*/
movq str(%FP), %4
movq %4, ch(%FP)
/*
if (*ch == 0)
goto strlen.while.done;
*/
strlen.while:
movq ch(%FP), %4
movzbq (%4), %4
subq 0, %4, %0
jz strlen.while.done
/*
ch = ch + 1;
*/
movq ch(%FP), %4
addq 1, %4, %4
movq %4, ch(%FP)
/*
goto strlen.while;
*/
jmp strlen.while
strlen.while.done:
/*
return ch - str;
*/
movq ch(%FP), %4
movq str(%FP), %5
subq %5, %4, %4
movq %4, rval(%FP)
jmp strlen.leave
// end of the function body
// function epilogue
strlen.leave:
addq 0, %FP, %SP
movq fp(%SP), %FP
movq ret(%SP), %RET
jmp %RET, %0
//------------------------------------------------------------------------------
// Procedure quicksort(A, n)
//------------------------------------------------------------------------------
.equ ret, 0
.equ fp, 8
// procedure arguments
.equ A, 16
.equ n, A+8
// local variables
.equ p, -8
.equ left, p-8
.equ right, left-8
.equ tmp, right-8
.text
quicksort:
// function prologue
movq %RET, ret(%SP)
movq %FP, fp(%SP)
addq 0, %SP, %FP
// reserve space for 4 local variables.
subq 32, %SP, %SP
// begin of the function body
/*
if (n < 2)
goto quicksort_done;
*/
/*
p = n/2;
*/
/*
left = 0;
*/
/*
right = n - 1;
*/
quicksort_do:
quicksort_while_left:
/*
if (A[left] >= A[p])
goto quicksort_endwhile_left;
*/
/*
left = left + 1;
*/
/*
goto quicksort_while_left;
*/
quicksort_endwhile_left:
quicksort_while_right:
/*
if (A[p] >= A[right])
goto quicksort_endwhile_right;
*/
/*
right = right - 1;
*/
/*
goto quicksort_while_right;
*/
quicksort_endwhile_right:
/*
if (left>right)
goto quicksort_endif_left_right;
*/
/*
tmp = A[left];
*/
/*
A[left] = A[right];
*/
/*
A[right] = tmp;
*/
/*
if (left != p)
goto quicksort_if_p_eq_right;
*/
/*
p = right;
*/
/*
goto quicksort_endif_p;
*/
quicksort_if_p_eq_right:
/*
if (right != p)
goto quicksort_endif_p;
*/
/*
p = left;
*/
quicksort_endif_p:
/*
left = left + 1;
*/
/*
right = right - 1;
*/
quicksort_endif_left_right:
/*
if (left <= right)
goto quicksort_do;
*/
/*
quicksort(A, right + 1);
*/
/*
quicksort(A+left, n - left);
*/
quicksort_done:
/*
;
*/
// end of the function body
// function epilogue
quicksort.leave:
addq 0, %FP, %SP
movq fp(%SP), %FP
movq ret(%SP), %RET
jmp %RET, %0
|
In its current form it translates but function quicksort just returns. Therefore you see string printed twice:
theon$ ulmas -o quicksort quicksort.s theon$ ulm quicksort hello, world! hello, world! theon$