gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Extremely fast decompression library? (word-aligned)

#80741 - Dwedit - Tue Apr 25, 2006 4:20 am

Does anyone know of an extremely fast decompression library that operates at the word level (32 bit) and no lower?

Something that would be decompressed like this or similar:
Code:

void decompress(int *s, int *d)
{
   int dist,size;
   while (1)
   {
      dist=*s++;
      if (dist>0)
      {
         do //raw words
         {
            *d++=*s++;
         } while (--dist);
      }
      else if (dist<0)
      {
         size=*s++;
         do //previously seen words
         {
            *d=d[dist];
            d++;
         } while (--size);
      }
      else
      {
         return;
      }
   }
}

Never mind that this would obviously be poor compression...

If one doesn't exist, does anyone know of an easy-to-understand LZ compression library that could be modified to be like that?
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."

#80742 - poslundc - Tue Apr 25, 2006 4:34 am

I'm not really aware of any good compression algorithms that aren't "byte-or-smaller".

Part of this I'm sure is just that the age of most of the algorithms out there predate 32-bit processors, but another large part of it also has to do that when you are trying to compress data - and especially smaller samples of data - you trade off in effectiveness by enforcing rules such as word-alignment.

In most compression schemes, the odds of having the same random byte repeated (1 in 256) is far more significant than the odds of having four random bytes repeated (1 in over four billion, and that's alignment notwithstanding).

Still, it's a good question, though, and if I ever were to go back for my Ph. D. it might be to try and devise an optimal 32-bit compression scheme for meeting or beating the bit/byte-level ones.

Dan.

#80810 - Miked0801 - Tue Apr 25, 2006 7:15 pm

RLE style algorithms can be changed to word alignment fairly easily. Same for Huffman style compression, but both almost always lose quite a bit of efficiency in the process. What are you doing that requires word aligned decompression?