The LZSS Compression Algorithm

April 1, 2018

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:

Data grouping flag bits

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:

c
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:

c
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:

c
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:

Hex dump of compressed data

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