Lab #6 - Subroutines, strings and arrays

10/12

This lab involves making changes to IA32 assembly language programs, compiling, testing and debugging the resulting code.

There is an IA32 instruction set reference here: IA32 Quick Reference (pdf). All the files listed here are also in ~hollingd/public/lab6 on the CS machines.

We haven't completely subroutines yet! There are some quick notes about subroutines at the end of this document.

Write an assembly language factorial subroutine that is recursive. Here is C code and the corresponding assembly to get you started:

	.file	"p1.c"
	.text
.globl factorial
	.type	factorial,@function
factorial:
	pushl	%ebp
	movl	%esp, %ebp
	movl	$0, %eax
	leave
	ret
.Lfe1:
	.size	factorial,.Lfe1-factorial
	.section	.rodata
.LC0:
	.string	"%d! = %d\n"
	.align 32
.LC1:
	.string	"You have to give me a number!\n"
	.text
.globl main
	.type	main,@function
main:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$8, %esp
	andl	$-16, %esp
	movl	$0, %eax
	subl	%eax, %esp
	cmpl	$1, 8(%ebp)
	jle	.L3
	subl	$12, %esp
	movl	12(%ebp), %eax
	addl	$4, %eax
	pushl	(%eax)
	call	atoi
	addl	$16, %esp
	movl	%eax, -4(%ebp)
	subl	$4, %esp
	subl	$8, %esp
	pushl	-4(%ebp)
	call	factorial
	addl	$12, %esp
	pushl	%eax
	pushl	-4(%ebp)
	pushl	$.LC0
	call	printf
	addl	$16, %esp
	jmp	.L4
.L3:
	subl	$12, %esp
	pushl	$.LC1
	call	printf
	addl	$16, %esp
.L4:
	movl	$1, %eax
	leave
	ret
.Lfe2:
	.size	main,.Lfe2-main

#include <stdio.h>

int factorial(int x) {
  return(0);  /* This needs to be written in assembly! */
}


int main(int argc, char **argv) {
  int num;
  if (argc>1) {
	num = atoi(argv[1]);
	printf("%d! = %d\n",num,factorial(num));
  } else {
	printf("You have to give me a number!\n");
  }
  return(1);
}

Write an assembly language subroutine that returns the length of a string. Some issues:

• The address of the first byte will be passed to the subroutine (this is the only parameter).

• The number of non-null bytes is the length (the null does not count!).

• The suffix 'b' on many IA32 instructions indicates that the instruction operands are each a single byte. There are single byte registers available (%al, %ah are part of %eax, %bl, %bh are part of %ebx, etc). Here are some examples of instructions that deal with bytes:

       movb  (%eax),%bl      # move from address in eax to bl
     
       cmpb  $0,(%eax)       # compare the byte at address in eax to 0
  
       addb  %ah, %al        # add ah and al
  

• Try to minimize the number of assembly instructions that will be executed to determine the length of the string!

Below is some C code that might help you test your code (gcc -S to generate assembly):

#include <stdio.h>

int mystrlen(char *s) {
  return(0); /* you need to write this in assembly */
}

int main(int argc, char **argv) {
  int num;
  if (argc>1) {
	printf("length is %d\n",mystrlen(argv[1]));
  } else {
	printf("You have to give me something!\n");
  }
  return(1);
}

Write an assembly language subroutine that returns the sum of all integers in an array of int. Some issues:

• The address of the array (the address of the first int in the array) will be passed to the subroutine as the first parameter (ebp+8), and the number of ints in the array is the second parameter (ebp+12)

• In general you compute the address of any array element as the base address (the address of the first element in the array) plus the index times the size of each element. For int you can assume the size is 4.

• For this particular subroutine you don't really need to compute the address of each element independently, you can just use a "pointer" (register that holds the address of the next element) and increment it by 4 each time through the loop

Below is some C code that might help you test your code (gcc -S to generate assembly):

#include <stdio.h>

int asum(int *p,int len) {
  return(0); /* you need to write this in assembly */
}

int main(int argc, char **argv) {
  int nums[] = { 1,2,3,4,3,2,1 };
  printf("Sum  is %d\n",asum(nums,sizeof(nums) / sizeof(int)));
  return(1);
}

Write an assembly language subroutine named reverseBits that reverses the bits in a 32 bit integer. The return value has the leftmost bit set if the parameter passed in has it's rightmost bit set, etc. This may be a good place to use the test instruction! Here is some sample code you can use to test your function (and a sample run).

#include <stdio.h>

int reverseBits(int x) {
  /* write this in assembly */
}

int main(int argc, char **argv) {
  int i,r;
 
  if (argc<2) {
    printf("You have to give me a number!\n");
    exit(1);
  }
 
  i = atoi(argv[1]);
  r = reverseBits(i);
  printf("Reverse of %d (%08x) is %d (%08x)\n",i,i,r,r);
  return(0);
}

~/comporg/lab6  ./p4 1
Reverse of 1 (00000001) is -2147483648 (80000000)
~/comporg/lab6  ./p4 100
Reverse of 100 (00000064) is 637534208 (26000000)
~/comporg/lab6  ./p4 85
Reverse of 85 (00000055) is -1442840576 (aa000000)
~/comporg/lab6  ./p4 123456
Reverse of 123456 (0001e240) is 38240256 (02478000)

Once you get your function working, try to optimize the code. Prizes awarded in two categories: speed and code size. Code size is measured as the number of instructions in the reverseBits subroutine (including all standard subroutine overhead). To measure speed, use the code below (it calls the function many times so it can be measured using the time command). Baseline time on monica.cs.rpi.edu is 9.7 seconds.

#include <stdio.h>

void reverseBits(int x) {
  /* write this in assembly */
}

#define LOOPS 10000  
#define INC   100     
#define MAXINT 100000

int main(int argc, char **argv) {
  int i,j;

  for (i=0;i<LOOPS;i++) {
    for (j=0;j<MAXINT;j+=INC) {
      if (j != reverseBits(reverseBits(j))) {
     	printf("ERROR: %d is wrong (%08x => %08x)\n",j,j,reverseBits(j));
      }
    }
  }
  return(0);
}

Stack setup: IA32 subroutines that adhere to the calling convention used by gcc (this includes all the code we've looked at) require that the current stack frame pointer %ebp be saved on the stack so that it can be restored when the subroutine returns to the caller. This requires the instruction push %ebp which should be the first instruction of any subroutine you write. The next instruction should establish the stack frame for this subroutine by setting the stack frame pointer %ebp to point to the current "top of the stack". This second instruction is movl %esp,%ebp (always!).

Returing from the subroutine: Typically a subroutine will compute something and return a value. Return values are simply placed in register %eax before the subroutine jumps back to the caller. Once the right value is in %eax, the subroutine must restore the stack frame pointer %ebp to point to the stack frame for the calling subroutine - this requires first setting the stack pointer to the top of the current stack frame: movl %ebp,%esp and then poping the old stack frame pointer off the stack: pop %ebp. Now the stack frame is restored to the caller's stack frame, and the top of stack contains the return address (the instruction back in the calling subrouting that we should jump to). The ret instruction pops the return address off the stack and jumps there.

NOTE: The IA32 leave instruction does the work of both: movl %ebp,%esp and pop %ebp, and is often used instead of both. This means your subroutines should always end with:

leave
ret

Getting at parameter values: Parameter values are passed on the stack. Since the stack pointer can change inside the body of a subroutine (for example, if the subroutine pushes something on the stack), we record the address of the top of the stack when the subroutine starts (before anything else messes with the stack). This is what the "stack frame pointer", %ebp stuff is all about. Saving the stack frame pointer in %ebp allows us (or a compiler) to access parameters without worrying about whether we have moved the stack pointer. Assuming you always set up the stack frame pointer as described above: the following is how you access parameter values:

Calling a subroutine: To call a subroutine, you must first push the parameter values on the stack (with the pushl instruction) in reverse order. The last pushl will always be the first parameter (by first, I mean leftmost parameter in the C prototype for the function). Then issue the call instruction, this puts the return address on the stack and jumps to the subroutine. When the subrouting returns, it will come back to the instruction immediately following the call. Once the subroutine returns, the stack is just as it was before the call (so any parameter values you pushed are still on the stack).