A bit of assembly

August 29, 2009 by prashant · Comments
Filed under: technology 

After reading this article about lock free buffers and seeing the use of CAS(compare and swap), I felt like posting the assembly code to do the same. Use case over there was to write a native method and call it from Java(back in 1.5 , when concurrent data structures in Java were more or less non existent). Without further ado , I’ll unleash the code onto you :) . First is for CAS and second is for computing GCD using Euclid’s algorithm(this one can be found in many places and tutorials as well).

Compile and run instructions gcc file_name.c ; ./a.out

Compare and Swap

  #include 
 #include 
//exchange - newvalue, comperand is old/expected value
/*
 * Function actually does the following thing - if the value at *dest is equal to oldvalue then replace it by newvalue else leave it unchanged : do all these atomically
 *
 * There are two options for return value
 *  1.is initial value of *dest and leave the burden of calling fxn to compare it with oldval
 *  2. do it over here and return 0 or 1, this should be more efficient
 * */

/* later change it into macro  */
int cas(int* dest, int oldvalue, int newvalue){
	printf("(%d,%d,%d)",*dest,oldvalue,newvalue);
	/* int cas(int dest, int oldvalue, int newvalue){ */
	/* int cas(int dest, int newvalue, int oldvalue){ */
	int result= 1;/* 1 shows that cas succeeded and 0 shows that it failed  */
	/* btw need to set cc for flag clobbering !  */
	__asm__ __volatile__(
			"movl %2, %%eax\n\t"
			"movl %3, %%ebx\n\t"
			"movl %0, %%ecx\n\t"
			"LOCK\n\t"
			"CMPXCHG %%ebx, (%%ecx)\n\t"  /* should LOCK be on the same line  */
			"jz DONE\n\t"
			"movl $0, %1\n\t "
			"DONE: \n\t"
			:"=m"(dest),"=g"(result)
			:"g" (oldvalue),"g" (newvalue),"m"(dest)
			:"%eax","%ebx","ecx","cc"
			);
	printf("(%d,%d,%d)",*dest,oldvalue,newvalue);
	return result;
}

/* TODO
 * write another asm fxn which puts above fxn in a while loop and keep trying unless it succeeds*/

int main(){
	int a= 5,b= 6;
	int* c = (int*) malloc(sizeof(int));
	*c= 6;
	/* int c= 6; */
	printf("%d\n",cas(c,b,b));
	printf("%d\n",cas(c,b,a));
	printf("%d\n",cas(c,a,a));
	printf("%d\n",cas(c,b,b));
	*c= 6;
	/* c= 5; */
	printf("changing value of *c to %d\n",*c);
	printf("%d\n",cas(c,b,b));
	printf("%d\n",cas(c,b,a));
	printf("%d\n",cas(c,a,a));
	printf("%d\n",cas(c,a,b));
	printf("%d\n",cas(c,b,a));
	return 0;
}

Formatting notes – seems like wp syntax highlighter is adding in the end , ignore that.

GCD

#include 
int gcd( int a, int b ) {
    int result ;
    /* Compute Greatest Common Divisor using Euclid's Algorithm */
    __asm__ __volatile__ ( "movl %1, %%eax;"
                          "movl %2, %%ebx;"
                          "CONTD: cmpl $0, %%ebx;"
                          "je DONE;"
                          "xorl %%edx, %%edx;"
                          "idivl %%ebx;"
                          "movl %%ebx, %%eax;"
                          "movl %%edx, %%ebx;"
                          "jmp CONTD;"
                          "DONE: movl %%eax, %0;" : "=g" (result) : "g" (a), "g" (b)
    );

    return result ;
}

int main() {
    int first, second ;
    printf( "Enter two integers : " ) ;
    scanf( "%d%d", &first, &second );

    printf( "GCD of %d & %d is %d\n", first, second, gcd(first, second) ) ;

    return 0 ;
}

Tags: , , , ,