Jump to content
  • Advertisement
Sign in to follow this  
Guacamole

Using LZMA to do in-memory compression-decompression

This topic is 3712 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I wanted to compress some buffers in-memory, so I grabbed a copy of the 7z LZMA SDK. I used gzip before, and it was a simple matter of a few function calls. However, the LZMA SDK doesn't come with any reference docs (if they are there, and I wasn't able to spot them, I apologize, just point me at them with a gentle RTFM. lzma.txt is NOT a reference :D). Does anyone know where I can get my hands on a simple tutorial or API reference? If there's something out there that's better suited to my needs (in-memory compression-decompression, could sacrifice a bit of compression ratio for speed), I'd be glad to hear about it. TIA.

Share this post


Link to post
Share on other sites
Advertisement
"The documentation in the SDK is very limited, providing no design information." Lempel-Ziv-Markov chain algorithm

It looks like you'll have to wing it using header files and maybe digging through the source code to applications that use it (listed in the wikipedia entry).

Share this post


Link to post
Share on other sites
Hmm, with that large dictionary size it might not be what I'm looking for. I want to independently compress hundrends of buffers, each about 1 or 2 KBs. Any other (documented!) recommendations?

Share this post


Link to post
Share on other sites
If you need some example sources, check out the function ExtractLzmaCompressedFile in this file: ResourceSupport.cpp

It contains the minimal code required to extract a file compressed with the LZMA.exe command line tool from the LZMA SDK.

Share this post


Link to post
Share on other sites
Why don't you use good old zlib? And there are tons of wrappers out there, if you are doing C++ you can use the Boost one, or mine (shameless plug, text is in French but code is in English and pretty much self-explanatory). Any other language generally has wrappers ready for use.

Share this post


Link to post
Share on other sites
Je parle francais! ;)

Anyone know whether some speed/compression ratio of different formats are discussed somewhere?

Share this post


Link to post
Share on other sites
Here's what I use in LoseThos.

http://www.losethos.com


#define ARC_MAX_BITS 12
#define ARC_MAX_TABLE_ENTRY ((1<<ARC_MAX_BITS)-1)

#define CT_NONE 0
#define CT_7_BIT 1
#define CT_8_BIT 2

class ArcTableEntry
{
ArcTableEntry *next;
U2 basecode;
U1 ch,pad;
U4 pad2;
};

public class ArcCs //control structure
{
U8 src_pos;
U8 src_size;
U8 dst_pos;
U8 dst_size;
U1 *src_buf;
U1 *dst_buf;
U8 min_bits;
U8 min_table_entry;
ArcTableEntry *cur_entry;
ArcTableEntry *next_entry;
U8 cur_bits_in_use;
U8 next_bits_in_use;
U1 *stack_ptr;
U1 *stack_base;
U8 free_index;
U8 free_limit;
U8 saved_basecode;
U8 entry_used;
U8 last_ch;
ArcTableEntry compress[ARC_MAX_TABLE_ENTRY+1];
ArcTableEntry *hash[ARC_MAX_TABLE_ENTRY+1];
};

public class ArcCompressStruct
{
U8 compressed_size,
expanded_size;
U2 compression_type,flags;
U1 body[1];
};


////**************************PROCEDURE*************************
OR_U4_BIT_FIELD::
PUSH EBP
MOV RBP,RSP
MOV RBX,U8 SF_ARG2[RBP]
SHR RBX,3
ADD RBX,U8 SF_ARG1[RBP]
MOV RAX,U8 SF_ARG3[RBP]
MOV RCX,U8 SF_ARG2[RBP]
AND RCX,7
SHL RAX,CL
OR U8 [RBX],RAX
POP EBP
RET
////**************************PROCEDURE*************************
SYS_EBF_MASKTABLE:
DU8 0,1,3,7,15,31,63,127,255;
DU8 0x1FF,0x3FF,0x7FF,0x0FFF;
DU8 0x1FFF,0x3FFF,0x7FFF,0x0FFFF;
DU8 0x1FFFF,0x3FFFF,0x7FFFF,0xFFFFF;
DU8 0x1FFFFF,0x3FFFFF,0x7FFFFF,0xFFFFFF;
DU8 0x1FFFFFF,0x3FFFFFF,0x7FFFFFF,0xFFFFFFF;
DU8 0x1FFFFFFF,0x3FFFFFFF,0x7FFFFFFF,0xFFFFFFFF;

EXTRACT_U4_BIT_FIELD::
PUSH EBP
MOV RBP,RSP
MOV RBX,U8 SF_ARG2[RBP]
MOV CL,3
SHR RBX,3
ADD RBX,U8 SF_ARG1[RBP]
MOV RAX,U8 [RBX]
MOV RCX,U8 SF_ARG2[RBP]
AND RCX,7
SHR RAX,CL
MOV RBX,U8 SF_ARG3[RBP]
AND RAX,U8 SYS_EBF_MASKTABLE[RBX*8]
POP EBP
RET
////**************************PROCEDURE*************************
/*
I8 ArcDetermineCompressionType(U1 *src,U8 size)
{
U8 i,j=0;
for (i=0;i<size;i++)
j|=src;
if (j & 0x80)
return CT_8_BIT;
else
return CT_7_BIT;
}
*/

CP_ARC_DETERMINE_COMPRESSION_TYPE::
PUSH EBP
MOV RBP,RSP
PUSH ESI
MOV RSI,U8 SF_ARG1[RBP]
MOV RCX,U8 SF_ARG2[RBP]
OR RCX,RCX
JZ @@100
XOR EBX,EBX
@@1: LODSB
OR BL,AL
LOOP @@1
OR BL,BL
JNS @@100
MOV RAX,CT_8_BIT
JMP @@110
@@100: MOV RAX,CT_7_BIT
@@110: POP ESI
POP EBP
RET
////**************************PROCEDURE*************************
/*
U8 ArcCheckSum(U1 *buf,U8 size)
{
U4 *ptr=buf;
U8 result=0,i,l=size>>2;
for (i=0;i<l;i++)
result^=ptr;
return result;
}
*/

CP_ARC_CHECK_SUM::
PUSH EBP
MOV RBP,RSP
PUSH ESI
MOV RSI,U8 SF_ARG1[RBP]
MOV RCX,U8 SF_ARG2[RBP]
XOR EBX,EBX
SHR RCX,2
JZ @@100
@@1: LODSD
XOR RBX,RAX
LOOP @@1
@@100: MOV RAX,RBX
POP ESI
POP EBP
RET
////**************************PROCEDURE*************************

/*
void ArcGetTableEntry(ArcCs *c)
{
U8 i;
ArcTableEntry *temp,*temp1;

if (c->entry_used) {
i=c->free_index;

c->entry_used=FALSE;
c->cur_entry=c->next_entry;
c->cur_bits_in_use=c->next_bits_in_use;
if (c->next_bits_in_use<ARC_MAX_BITS) {
c->next_entry = &c->compress[i++];
if (i==c->free_limit) {
c->next_bits_in_use++;
c->free_limit=1<<c->next_bits_in_use;
}
} else {
do if (++i==c->free_limit)
i=c->min_table_entry;
while (c->hash);
temp=&c->compress;
c->next_entry=temp;
temp1=&c->hash[temp->basecode];
while (temp1) {
if (temp1->next==temp) {
temp1->next=temp->next;
break;
} else
temp1=temp1->next;
}
}
c->free_index=i;
}
}
*/

CP_ARC_GET_TABLE_ENTRY::
PUSH EBP
MOV RBP,RSP
PUSH ESI
PUSH EDI
MOV RSI,U8 SF_ARG1[RBP]
BTR U8 ACS_ENTRY_USED[RSI],0
JNC I4 @@100
MOV RDX,U8 ACS_FREE_INDEX[RSI]
XOR EAX,EAX
MOV RAX,U8 ACS_NEXT_ENTRY[RSI]
MOV U8 ACS_CUR_ENTRY[RSI],RAX
MOV RCX,U8 ACS_NEXT_BITS_IN_USE[RSI]
MOV U8 ACS_CUR_BITS_IN_USE[RSI],RCX
CMP RCX,ARC_MAX_BITS
JAE @@20
MOV RAX,RDX
SHL RAX,4
LEA RAX,U8 ACS_COMPRESS[RSI+RAX]
MOV U8 ACS_NEXT_ENTRY[RSI],RAX
INC RDX
CMP U8 ACS_FREE_LIMIT[RSI],RDX
JNE @@90
INC RCX
MOV U8 ACS_NEXT_BITS_IN_USE[RSI],RCX
MOV RAX,1
SHL RAX,CL
MOV U8 ACS_FREE_LIMIT[RSI],RAX
JMP @@90
@@20: INC RDX
CMP U8 ACS_FREE_LIMIT[RSI],RDX
JNE @@25
MOV RDX,U8 ACS_MIN_TABLE_ENTRY[RSI]
@@25: MOV RAX,U8 ACS_HASH[RSI+RDX*8]
OR RAX,RAX
JNZ @@20
MOV RDI,RDX
SHL RDI,4
LEA RDI,U8 ACS_COMPRESS[RSI+RDI]
MOV U4 ACS_NEXT_ENTRY[RSI],EDI
MOVZX RBX,U2 ATE_BASECODE[RDI]
LEA RCX,U8 ACS_HASH[RSI+RBX*8]
@@50: OR RCX,RCX
JZ @@90
MOV RAX,U8 ATE_NEXT[RCX]
CMP RDI,RAX
JNE @@55
MOV RAX,U8 ATE_NEXT[RDI]
MOV U8 ATE_NEXT[RCX],RAX
JMP @@90
@@55: MOV RCX,RAX
JMP @@50
@@90: MOV U8 ACS_FREE_INDEX[RSI],RDX
@@100: POP EDI
POP ESI
POP EBP
RET


$PJ,"Project: OSMain","/LT/OSMain/OS.SPZ"$
// The following algorithm came from a magazine
// and I implimented it when I worked for Ticketmaster.

void ArcCompressBuf(ArcCs *c)
//Use $LK,"CompressBuf","MN:CompressBuf"$() unless you are doing
//more than one buffer.
{
ArcTableEntry *temp,*temp1;
U8 basecode;
U1 *src_ptr,*src_limit,ch;

src_ptr=c->src_buf+c->src_pos;
src_limit=c->src_buf+c->src_size;

if (c->saved_basecode==MAX_U4)
basecode=*src_ptr++;
else
basecode=c->saved_basecode;

while (src_ptr<src_limit &&
c->dst_pos+c->cur_bits_in_use<=c->dst_size) {
ArcGetTableEntry(c);

arc_start_loop1:
if (src_ptr>=src_limit) goto arc_done_compression;
ch=*src_ptr++;
if (temp=c->hash[basecode])
do {
if (temp->ch==ch) {
basecode=temp-&c->compress[0];
goto arc_start_loop1;
}
} while (temp=temp->next);

OrU4BitField(c->dst_buf,c->dst_pos,basecode);
c->dst_pos+=c->cur_bits_in_use;

c->entry_used=TRUE;
temp=c->cur_entry;
temp->basecode=basecode;
temp->ch=ch;
temp1=&c->hash[basecode];
temp->next=temp1->next;
temp1->next=temp;

basecode=ch;
}
arc_done_compression:
c->saved_basecode=basecode;
c->src_pos=src_ptr-c->src_buf;
}

void ArcFinishCompression(ArcCs *c)
{
if (c->dst_pos+c->cur_bits_in_use<=c->dst_size) {
OrU4BitField(c->dst_buf,c->dst_pos,c->saved_basecode);
c->dst_pos+=c->cur_bits_in_use;
}
}

void ArcExpandBuf(ArcCs *c)
//Use $LK,"ExpandBuf","MN:ExpandBuf"$() unless you know what
//you're doing. I forgot why I made this
//"public".
{
U1 *dst_ptr,*dst_limit;
U8 basecode,lastcode,code;
ArcTableEntry *temp,*temp1;

dst_ptr=c->dst_buf+c->dst_pos;
dst_limit=c->dst_buf+c->dst_size;

while (dst_ptr<dst_limit &&
c->stack_ptr!=c->stack_base)
*dst_ptr++ = * -- c->stack_ptr;

if (c->stack_ptr==c->stack_base && dst_ptr<dst_limit) {
if (c->saved_basecode==MAX_U4) {
lastcode=ExtractU4BitField(c->src_buf,c->src_pos,
c->next_bits_in_use);
c->src_pos+=c->next_bits_in_use;
*dst_ptr++=lastcode;
ArcGetTableEntry(c);
c->last_ch=lastcode;
} else
lastcode=c->saved_basecode;
while (dst_ptr<dst_limit &&
c->src_pos+c->next_bits_in_use<=c->src_size) {
basecode=ExtractU4BitField(c->src_buf,c->src_pos,
c->next_bits_in_use);
c->src_pos+=c->next_bits_in_use;
if (c->cur_entry==&c->compress[basecode]) {
*c->stack_ptr++=c->last_ch;
code=lastcode;
} else
code=basecode;
while (code>=c->min_table_entry) {
*c->stack_ptr++=c->compress.ch;
code=c->compress.basecode;
}
*c->stack_ptr++=code;
c->last_ch=code;

c->entry_used=TRUE;
temp=c->cur_entry;
temp->basecode=lastcode;
temp->ch=c->last_ch;
temp1=&c->hash[lastcode];
temp->next=temp1->next;
temp1->next=temp;

ArcGetTableEntry(c);
while (dst_ptr<dst_limit && c->stack_ptr!=c->stack_base)
*dst_ptr++ = * -- c->stack_ptr;
lastcode=basecode;
}
c->saved_basecode=lastcode;
}
c->dst_pos=dst_ptr-c->dst_buf;
}

ArcCs *ArcCsNew(BoolI1 expand,BoolI1 text_only)
{
ArcCs *c;
c=MAllocZ(sizeof(ArcCs));
if (expand) {
c->stack_base=MAlloc(ARC_MAX_TABLE_ENTRY+1);
c->stack_ptr=c->stack_base;
}
if (text_only)
c->min_bits=7;
else
c->min_bits=8;
c->min_table_entry=1<<c->min_bits;
c->free_index=c->min_table_entry;
c->next_bits_in_use=c->min_bits+1;
c->free_limit=1<<c->next_bits_in_use;
c->saved_basecode=MAX_U4;
c->entry_used=TRUE;
ArcGetTableEntry(c);
c->entry_used=TRUE;
return c;
}

void ArcCsDel(ArcCs *c)
{
Free(c->stack_base);
Free(c);
}


ArcCompressStruct *CompressBuf(U1 *src,U8 size,
U8 flags=0,TssStruct *tss=NULL)
{
U8 size_out;
ArcCompressStruct *result;
BoolI1 text_only=ArcDetermineCompressionType(src,size)==CT_7_BIT;
ArcCs *c=ArcCsNew(FALSE,text_only);
c->src_size=size;
c->src_buf=src;
c->dst_size=(size+sizeof(ArcCompressStruct)-1)<<3;
c->dst_buf=MAllocZ(c->dst_size>>3);
c->dst_pos=(sizeof(ArcCompressStruct)-1)<<3;
ArcCompressBuf(c);
ArcFinishCompression(c);
if (c->src_pos==c->src_size) {
size_out=(c->dst_pos+7)>>3;
result=MAlloc(size_out,tss);
MemCpy(result,c->dst_buf,size_out);
result->compression_type=text_only ? CT_7_BIT:CT_8_BIT;
result->compressed_size=size_out;
} else {
result=MAlloc(size+sizeof(ArcCompressStruct)-1,tss);
MemCpy(result->body,src,size);
result->compression_type=CT_NONE;
result->compressed_size=size+sizeof(ArcCompressStruct)-1;
}
result->expanded_size=size;
result->flags=flags;
Free(c->dst_buf);
ArcCsDel(c);
return result;
}

U1 *ExpandBuf(ArcCompressStruct *r,TssStruct *tss=NULL)
{
ArcCs *c;
U1 *result;
BoolI1 text_only;
result=MAlloc(r->expanded_size+1,tss);
result[r->expanded_size]=0; //terminate

text_only= r->compression_type==CT_7_BIT;
if (r->compression_type==CT_NONE) {
MemCpy(result,r->body,r->expanded_size);
goto expand_end;
}
c=ArcCsNew(TRUE,text_only);
c->src_size=r->compressed_size<<3;
c->src_pos=(sizeof(ArcCompressStruct)-1)<<3;
c->src_buf=r;
c->dst_size=r->expanded_size;
c->dst_buf=result;
c->dst_pos=0;
ArcExpandBuf(c);
ArcCsDel(c);

expand_end:
return result;
}




// LessBread edit: please use the source tags when posting large chunks of code. Check out the faq for details about them.

[Edited by - LessBread on July 17, 2008 5:01:29 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Guacamole
Anyone know whether some speed/compression ratio of different formats are discussed somewhere?
Most of them will perform very badly on tiny 1-2k chunks anyway. Would it be unreasonably expensive to decompress larger (64k or so) blocks and keep only the part you're interested in, and perhaps cache the rest for a while?
Otherwise you'll want to go with a library specifically developed with random access in mind, or write some custom code yourself (compression isn't nearly as scary as it's sometimes made out to be). In other words algorithms like LZMA and BWT are out, but LZ variants and statistical coders with dictionaries shared by many blocks ought to work nicely.
In the end things depend largely on what type of data you're dealing with, as well as in which order it will need to be (de)compressed.

Share this post


Link to post
Share on other sites
Yes, that I realized. Not many algorithms are efficient for small chunks, but I don't see a feasible way to group them, as the order of compression/decompression is completely arbitrary. Any ideas?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!