Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

On the fly compression/decompression

Posted on 2004-08-06
9
Medium Priority
?
526 Views
Last Modified: 2010-04-15
Hi all, been a long time since I need to come here.

I'm looking for a solution to a space problem that I am having. I run a mud, (multi-user-dungeon) and it creates a log for every action of all the players. This takes up alot of space, and I've had to start removing things from teh log to save space, that is a bad solution.

I would do routine compressions of the data if I could, however the mud later on needs the uncompressed data, as we recall the text via a webserver implemented in the mud.

I had the idea of compressing the data using either zlib, or another compression technique, however I am not very well versed in such things.

I would need to compress when writing, and uncompress when reading, without a noticeable speed decrease

My question to you experts: What compression solution should I use (zlib/other?) and is it possible that someone could write me up a quick snippet or code to show me how I would go about compressing/decompressing text on the fly.

Thank you!
0
Comment
Question by:Krule
7 Comments
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 11737811
Here is a simple compression library, just compress and uncompress a block of memory into another buffer.

///////////////////////////////////////////////////////////

WORD UncompressBlock(BYTE *Source, BYTE *Dest, WORD SourceSize)
{
      signed short Hash[4096];
      WORD Key,Size,Pos;
      BYTE Bit = 0;
      WORD Command;
      WORD X = 0;
      WORD Y = 3;
      WORD Z = 1;

      for (Key = 0; Key < 4096; Key++)
            Hash[Key] = -1;
      Dest[0] = FLAG_Compress;

      while (X<SourceSize && Y<=SourceSize) {
            /*printf("X = %i Y = %i Z = %i",X,Y,Z);*/
            if (Bit > 15) {
                  Dest[Z++] = (Command >> 8) & 0x00ff;
                  Dest[Z] = Command & 0x00ff;
                  Z = Y;
                  Bit = 0;
                  Y += 2;
            }
            for (Size = 1; Source[X]==Source[X+Size] && Size<0x0fff && (X+Size) < SourceSize; Size++);
            if (Size >= 16) {
                  Dest[Y++] = 0;
                  Dest[Y++] = ((Size - 16) >> 8) & 0x00ff;
                  Dest[Y++] = (Size - 16) & 0x00ff;
                  Dest[Y++] = Source[X];
                  X += Size;
                  Command = (Command << 1) + 1;
            } else if (GetMatch(Source,X,SourceSize,Hash,Size,Pos)) {
                  Key = ((X-Pos) << 4) + (Size - 3);
                  Dest[Y++] = (Key >> 8) & 0x00ff;
                  Dest[Y++] = Key & 0x00ff;
                  X += Size;
                  Command = (Command << 1) + 1;
            } else {
                  Dest[Y++] = Source[X++];
                  Command = (Command << 1);
            }
            Bit++;
      }
      Command <<= (16-Bit);
      Dest[Z++] = (Command >> 8) & 0x00ff;
      Dest[Z] = Command & 0x00ff;

      if (Y>SourceSize) {
            for (Y=0; Y<SourceSize; Dest[Y+1]=Source[Y++]);
            Dest[0] = FLAG_Copied;
            return SourceSize+1;
      }
      return Y;
}

////////////////////////////////////////////////////////////

WORD CompressBlock(BYTE *Source, BYTE *Dest, WORD SourceSize)
{
      WORD Pos, Size, K;
      WORD Command = (Source[1] << 8) + Source[2];
      WORD X = 3;
      WORD Y = 0;
      BYTE Bit = 16;

      if (Source[0] == FLAG_Copied) {
            for (Y=1; Y<SourceSize; Dest[Y-1]=Source[Y++]);
            return SourceSize-1;
      }
      while (X < SourceSize) {
            if (Bit == 0) {
                  Command = (Source[X++] << 8);
                  Command += Source[X++];
                  Bit = 16;
            }
            if (Command & 0x8000) {
                  Pos = (Source[X++] << 4);
                  Pos += (Source[X] >> 4);
                  if (Pos) {
                        Size = (Source[X++] & 0x0f)+3;
                        for (K=0; K<Size; K++)
                              Dest[Y+K] = Dest[Y-Pos+K];
                        Y += Size;
                  } else {
                        Size = (Source[X++] << 8);
                        Size += Source[X++] + 16;
                        for (K=0; K<Size; Dest[Y+K++] = Source[X]);
                        X++;
                        Y += Size;
                  }
            } else
                  Dest[Y++] = Source[X++];
            Command <<= 1;
            Bit--;
      }
      return Y;
}

BOOL GetMatch(BYTE *Source, WORD X, WORD SourceSize, signed short *Hash, WORD &Size, WORD &Pos)
{       
      WORD HashValue = (40543L*((((Source[X] << 4) ^ Source[X+1]) << 4) ^ Source[X+2]) >> 4) & 0xfff;
      signed short p = Hash[HashValue];

      Hash[HashValue] = X;
      if (p!=-1 && (X-p)<4096) {
            Pos = p;
            for (Size=0; (Size<18) && (Source[X+Size]==Source[p+Size]) && ((X+Size)<SourceSize); Size++);
            return (Size >= 3);
      }
      return false;
}

0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 11737847
Notice about the data type

WORD -> A 16 bits integer
BYTE   -> A 8 bits integer
BOOL  -> An integer, acting as boolean

To compress, call:
CompressBlock(PtrToYourData, PtrToYourCompressedBuffer, OriginalDataSize);
Of course, buffer must be allocated first, with the same size as original data
Also you must store original data size to reserve buffer for uncompress function

To uncompress call:
UncompressBlock(PtrToYourCompressedBuffer, PtrToUncompressedData, CompressedDataSize);
You must allocate uncompressed buffer with original data size



0
 
LVL 3

Author Comment

by:Krule
ID: 11737949
Ok...I might have forgotten to mention a step.

I need to compress..write to disk..read from disk...uncompress. The problem there is keeping track of the uncompressed datas size when I write to disk.. :\
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 11738010
So, what's the problem?

You have some data to store.
Call compress routine to compress it in a buffer.
Open a file
Write uncompressed data size at the very first.
Write compressed block
Close the file

To uncompress:
Open the file
Read uncompressed data size at the very first
Invoke your uncompress routine
Close file

That's all.
0
 
LVL 3

Author Comment

by:Krule
ID: 11738297
Oh, that would work ok.

Is this like the best compression I can get, anyone else have suggestions?
0
 
LVL 7

Accepted Solution

by:
JugglerW earned 800 total points
ID: 11744135
Look here:

http://www.gzip.org/zlib/

exists for many platforms.
0
 
LVL 16

Assisted Solution

by:PaulCaswell
PaulCaswell earned 800 total points
ID: 11750634
One I've used, probably not the best, is LZW. It was designed for on-the-fly serial communications compression and is very fast at both compress and uncompress time. It runs with a type of state table so you can even post it data one byte at a time. If your log is purely ASCII, you will probably get some good ratios.

A google search should find it as lzw or Lempel Ziv Welch. Here's a good article: http://www.dogma.net/markn/articles/lzw/lzw.htm

Paul
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

877 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question