adler32 optimization

This is a discussion on adler32 optimization within the C Programming forums, part of the General Programming Boards category; Hello again: Yesterday I wrote a function that would perform the old adler32 hash on given data. My function works ...

  1. #1
    Registered User carrotcake1029's Avatar
    Join Date
    Apr 2008
    Posts
    398

    adler32 optimization

    Hello again:

    Yesterday I wrote a function that would perform the old adler32 hash on given data. My function works perfectly well and so far always has found the correct hash. The problem is big files. I made a file exactly 1 MB and hashed it with various commercial software. They took no more than 5-10 secs. Mine takes 1hr and 5mins....

    Since this is a fairly simple hash algo, I was hoping that someone here would recognize and optimizations that could be made to my code. I wrote it from scratch and hopefully right off the bat I am not too inefficient!

    Code:
    unsigned int adler32(unsigned char *data, unsigned int len)
    {
    	unsigned int A = 1, B = 0;
    	unsigned int i, j;
    
    	for (i = 0; i < len; i++)
    	{
    
    		A += data[i];
    		for (j = i + 1; j > 0; j--)
    			B += data[j-1];
    		B++;
    
    		A %= 65521;
    		B %= 65521;
    	}
    
    	return (B * 65536) + A;
    }

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,588
    http://en.wikipedia.org/wiki/Adler-32
    Your inner loop is a killer.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User carrotcake1029's Avatar
    Join Date
    Apr 2008
    Posts
    398
    Ya, I got the specifics of the function from wikipedia. I don't want to copy that function verbatim though. I will try to work on my inner loop.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,588
    > data[j-1]
    If you think about it, you've already summed these (except for the [j-1] entry itself) the last time you were round the loop.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    Yeah, dealing with pointers is a bit quicker than running threw indexing the array. Also bit shifting is faster than multiplication as used for your return value. The wikipedia posting would be the way to go.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Turn Off Optimization?
    By danlee58 in forum C Programming
    Replies: 6
    Last Post: 12-10-2008, 02:52 AM
  2. need reading material for c++ database optimization
    By elninio in forum C++ Programming
    Replies: 0
    Last Post: 07-24-2008, 11:32 PM
  3. optimization flags
    By markucd in forum C++ Programming
    Replies: 4
    Last Post: 06-30-2006, 09:08 AM
  4. Optimization settings
    By Roaring_Tiger in forum C Programming
    Replies: 4
    Last Post: 02-23-2005, 01:53 AM
  5. Optimization stuff
    By jverkoey in forum C++ Programming
    Replies: 2
    Last Post: 05-26-2004, 06:02 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21