The LZSS Compression Algorithm
Introduction to LZSS
LZSS is an improved version of LZ77, published by James A. Storer and Thomas Szymanski in the Journal of the ACM in 1982. LZSS makes full use of bit flags, which significantly improves compression efficiency compared with LZ77.
See Wikipedia: lzss
How the algorithm works
Before reading this post, you should know the general flow of LZ77; if not, read this post first.
LZSS and LZ77 share the same encoding/decoding logic; the difference lies in how encoded data is marked. Below I describe LZSS's marking scheme in detail, which shows how it improves compression efficiency so much.
A key concept in LZSS encoding is: grouping data.
A byte consists of 8 bits, so one byte can flag whether each of the following (at least) 8 items is a compressed code, instead of using a \0x00\0x00 prefix to distinguish compressed from uncompressed data. This saves the large overhead of all those \0x00\0x00 prefixes.
How the grouping flags work:

As you can see, with this grouping scheme the worst case adds only one extra byte for every 8 bytes, a big improvement over the 2 extra bytes per literal byte in LZ77.
Source code
Helper function:
unsigned int search_maxlen_p( unsigned char** pt, \
unsigned char* head, \
unsigned char* tail, \
unsigned char* end)
{
unsigned char* tmp = *pt;
unsigned int leng = 0, i;
for(tmp;tmp >= head;tmp--){
if(tmp[0] == tail[0]){
for(i = 0;(i < ((1 << LENGTHBITS) + 1)) && (&tmp[i] > head) && (&tmp[i] < tail) && (&tail[i] < end) && (tmp[i] == tail[i]);i++);
if(i > leng){
leng = i;
*pt = tmp;
}
}
}
return leng;
}
Encoder:
int lzss_encode(FILE* in,FILE* out)
{
unsigned char* buf = 0,* head = 0,* tail = 0;
long size = 0;
if(! in || ! out)return 1;
get_filesize(in,size);
if(size <= 0)return 1;
buf = (unsigned char*)malloc(size* sizeof(unsigned char));
if(! buf)return 1;
if(fread(buf,sizeof(unsigned char),size,in) == size){
unsigned int np = 1 ,control_count = 0;
unsigned char suf[17] = {0}; // 2*8 + 1
fputc((size >> 24) & 0xff,out);
fputc((size >> 16) & 0xff,out);
fputc((size >> 8) & 0xff,out);
fputc((size >> 0) & 0xff,out);
head = tail = buf;
for(;;){
head = tail - WINDOWSIZE;
if(head < buf)head = buf;
if(control_count >= 8){
put_bytes(suf,np,out);
memset(suf,0,sizeof(suf));
np = 1;
control_count = 1;
} else {
control_count++;
}
if(tail > buf + size - 1)break;
if(head < tail){
unsigned int bytes = 0;
unsigned char* pt = tail - 1;
bytes = search_maxlen_p(&pt,head,tail,buf + size);
if(bytes > 2){ // if find a pattern more than 2 bytes, save its offset-length.
suf[0] <<= 1;
suf[0] |= OFFLENFLAG;
suf[np++] = (unsigned char)(( (tail - pt) >> LENGTHBITS) & 0xff);
suf[np++] = (unsigned char)((((tail - pt) << LENGTHBITS) + bytes - 2) & 0xff);
tail += bytes;
} else {
suf[0] <<= 1;
suf[np++] = tail[0];
tail++;
}
} else {
suf[0] <<= 1;
suf[np++] = tail[0];
tail++;
}
}
for(control_count;control_count <= 8;control_count++)suf[0] <<= 1; // must keep highest bit is aligned to first byte.
put_bytes(suf,np,out);
}
free(buf);
return 0;
}
Decoder:
int lzss_decode(FILE* in,FILE* out)
{
unsigned char* in_buffer = 0,* out_buffer = 0,* head = 0,* tail = 0;
long in_size = 0,out_size = 0;
if(! in || ! out)return 1;
get_filesize(in,in_size);
if(in_size <= 0)return 1;
out_size = (fgetc(in) & 0xff) << 24;
out_size += (fgetc(in) & 0xff) << 16;
out_size += (fgetc(in) & 0xff) << 8;
out_size += (fgetc(in) & 0xff) << 0;
if(out_size <= 0)return 1;
in_buffer = (unsigned char*)malloc(sizeof(unsigned char)* in_size);
if(! in_buffer)return 1;
out_buffer = (unsigned char*)malloc(sizeof(unsigned char)* out_size);
if(out_buffer){
if(fread(in_buffer,sizeof(unsigned char),in_size,in) == in_size - 4){
unsigned int control_count = 0;
unsigned char control_flags = 0;
unsigned char* pt = (unsigned char*)in_buffer;
head = tail = out_buffer;
control_flags = pt[0];
pt++;
for(;;){
if(pt >= (in_buffer + in_size - 4))break;
if(control_count >= 8){
control_flags = pt[0];
pt++;
control_count = 1;
} else {
control_count++;
}
if(control_flags >> 7){ // offset-length.
unsigned int offset = 0,length = 0,i;
offset = pt[0] << LENGTHBITS;
offset += (pt[1] >> LENGTHBITS) & 0x0f;
length = (pt[1] & 0x0f) + 2;
for(i = 0;i < length;i++){
tail[i] = ((unsigned char*)(tail - offset))[i];
}
tail += length;
pt += 2;
control_flags <<= 1;
} else { // literal.
tail[0] = pt[0];
tail++;
pt++;
control_flags <<= 1;
}
}
fwrite(out_buffer,sizeof(unsigned char),out_size,out);
}
free(out_buffer);
}
free(in_buffer);
return 0;
}
Analysis
Data compressed with LZSS is already quite good, as the hex dump below shows:

However, there is still room for further optimization: encoding the output again with the Huffman coding mentioned in the LZ77 post yields an even better compression result.
Link: Code on GitHub