A bit of assembly

August 29, 2009 by · 1 Comment
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 ;
}

Cricketing World Awaits a New World Order

August 25, 2009 by · 1 Comment
Filed under: misc 

After a series spanning  five tests and approximately two months, England  reclaimed ashes.

Let’s talk about the  winning  team first  – their middle order is ‘average’ if you don’t want to critical . Greame Swann’s contribution with the bat will count no less than contribution with the ball. Stuart Broad – best all rounder was non starter for the 5th test. Andrew Strauss was the only consistent batsman and Jimmy Anderson was the only consistent bowler.

Point here is not to berate the achievements of the winning team but to put in perspective the fact that despite all these, Australia lost. you’ll have to think for few seconds , if asked to name their best bowler.  Right, it was BW Hilfenhaus. Hauritz outperformed everbody’s expectation but was still not good enough to be selected for two of the five tests.  South Africa never became a world beater without a world class spinner , Australia can’t hope to remain one without one good enough one at least. Magician left the stage and it doesn’t look like art anymore, forget magic. Ponting stands tall among lesser mortals and Michael Clarke stands up very often, but that makes them a team with some very good players and not a very good team.
Ashes 2009 will be remembered for Andrew Flintoff’s last Ashes, Stuart Broad’s arrival as an all rounder(if he adds some more Ashes folklore to his promising  start), and one of the most telling debut century of all time by Trott but it will also be remembered as the point where ifs and buts about Australia’s supremacy were finally put to rest, it is over. Don’t get me wrong they can still unearth Mike Hussey or Stuart Clark but you feel the contribution of  all time greats when they go missing. Sometimes they come to remind you of themselves in IPL but still they can not be replaced. Let’s feel blessed for having seen Warne, McGrath and Gilchrist playing together and being supported by Waughs, Ponting, Hyden , Martin and Langer.

Going forward, South Africa will always remain a very good team but they need to win semifinals and be more consistent around the globe, Pakistan will remain enigmatically brilliant, Indian young guns will probably find it tough to fill the shoes of extraordinary predecessors. Sri Lanka should continue to show glimpses of art in craft. But, we may have to wait for sometime before having an all out dominant team or before a captain complains of lack of competition, as Steve Waugh did once.

On a related note – let’s welcome the coming back of Asif , he has a hell lot of potential, let’s hope to see some of that and also welcome Andy Flower in the new awatar, right you can’t keep good men down for long.

ruby one liners to create hash

August 20, 2009 by · 1 Comment
Filed under: technology 

Yesterday while going through one of my old programs, I found this written by me sometime back :

#begin magic
hash=Hash[*CGI.unescape(raw_text).split('&').map{|x| b=x.split("=");b.push(nil) if b.size==1;b}.flatten]
#end magic

To kill some of suspense let me disclose that raw_text looks like

"SUCCESS&mc_gross=10.00&protection_eligibility=Ineligible&payer_id=U7PPJJ4TSJ47E&tax=0.00&payment_date=09%3A45%3A30+Jul+10%2C+2009+PDT&payment_status=Pending"

, right it has been cut from paypal payment acknowledgment.

Above line if broken in parts reads better :

  unescaped_array= CGI.unescape(raw_text).split('&')
  unescaped_array= unescaped_array.collect{|x| b=x.split("=");b.push(nil) if b.size==1;b}
  flattened_array= unescaped_array.flatten
  hash= Hash[*flattened_array]

Let’s do individual steps in irb:

irb(main):009:0>unescaped_array= CGI.unescape(raw_text).split('&')    

=> ["SUCCESS", "mc_gross=10.00", "protection_eligibility=Ineligible", "payer_id=U7PPJJ4TSJ47E", "tax=0.00", "payment_date=09:45:30 Jul 10, 2009 PDT", "payment_status=Pending"]                                                                         

irb(main):013:0> unescaped_array= unescaped_array.map{|x| b=x.split("=");b.push(nil) if b.size==1;b}  

=> [["SUCCESS", nil], ["mc_gross", "10.00"],["protection_eligibility", "Ineligible"], ["payer_id", "U7PPJJ4TSJ47E"], ["tax", "0.00"], ["payment_date", "09:45:30 Jul 10, 2009 PDT"], ["payment_status", "Pending"]]                               

irb(main):014:0> flattened_array= unescaped_array.flatten     

=> ["SUCCESS", nil, "mc_gross", "10.00", "protection_eligibility", "Ineligible", "payer_id", "U7PPJJ4TSJ47E", "tax", "0.00", "payment_date", "09:45:30 Jul 10, 2009 PDT", "payment_status", "Pending"]
irb(main):015:0>
hash= Hash[*flattened_array]
=> {"tax"=>"0.00", "payment_status"=>"Pending", "payer_id"=>"U7PPJJ4TSJ47E", "mc_gross"=>"10.00", "SUCCESS"=>nil, "payment_date"=>"09:45:30 Jul 10, 2009 PDT", "protection_eligibility"=>"Ineligible"}

BTW, * is called splat operator in ruby

Another way to create hash from ‘array of pairs ‘ is to use inject :

hash= [[1,2],[3,4]].inject({}){|result,element| result[element.first]= result[element.last]; result}

There is one more way :) Write a loop, that I’ll leave as an exercise to the readers !!

Here is a bit unrelated use case of creating hash from arrays:

irb(main):005:0> [1,2,3,4,7,9].group_by{|x| x<5 ? :lesser : :greater}

=> {:lesser=>[1, 2, 3, 4], :greater=>[7, 9]}

You can do more things, basically result of the block is used as the key for that element in the resulting hash.

gmail, mutt and msmtp fix

August 17, 2009 by · 3 Comments
Filed under: technology 

If you use mutt and smtp to access gmail . Here is a (bad) news. Cool guys at Google again changed certificate. Oh, did you ask – how do it know it ? Simple mutt started complaining about bad certificate when trying to use msmpt, infamous ‘msmtp: TLS certificate verification failed: the certificate hasn’t got a known issuer.’ greeted me on the screen.

To cross confirm –
Just run following

$ msmtp --serverinfo --host=smtp.gmail.com --tls=on --port=587 --tls-certcheck=off

In place of old Thwate Server now you get following in issuer segment
Issuer:
Common Name: Google Internet Authority
Organization: Google Inc
Country: US

Fortunately fix is simple, here is what you need to do on debian

# apt-get install ca-certificates
# dpkg -s ca-certificates|grep Version
Version: 20090814

After this just change following line in you ~/.msmtprc

tls_trust_file /certs/Thawte SSLWeb Server Roots/thawte Premium Server CA/Thawte Premium Server CA.pem

to

tls_trust_file /usr/share/ca-certificates/mozilla/Equifax_Secure_CA.crt

Git and Awesome Survey

August 15, 2009 by · 1 Comment
Filed under: misc 

Here are two links for survey by git (version control system) and awesome(window manager) community. If you use either of these, please take out some time to fill in the questionnaire. Think of it as the simplest way to contribute back to the software you use.
Here are the links :

Git – http://www.survs.com/survey?id=2PIMZGU0&channel=Q0EKJ3NF54

Awesome – http://www.survs.com/survey?id=8BVEV3FO&channel=BH07CQ040D

Note -(As found on those pages but at the bottom :) ) –
“If you have cookies enabled, you can always submit partially filled survey, and return to your answers at later time, completing it later.”

  • Recent Posts