path: root/baseline/source/huff_dec/compress.txt

+===========================================================+
|     Introduction to the losslessy compression schemes     |
|           Description of the codec source codes           |
+-----------------------------------------------------------+
| From David Bourgin (E-mail: david.bourgin@ufrima.imag.fr) |
| Date: 22/9/94                                             |
+===========================================================+

                          ------ BE CARE ------
This file (compress.txt) is copyrighted. (c) David Bourgin - 1994
Permission to use this documentation for any purpose other than
its incorporation into a commercial product is hereby granted without fee.
Permission to copy and distribute this documentation only for non-commercial use
is also granted without fee, provided, however, that the above copyright notice
appears in all copies, that both that copyright notice and this permission notice appear in supporting documentation. The author makes no representations about
the suitability of this documentation for any purpose. It is provided "as is"
without express or implied warranty. 

The source codes you obtain with this file are *NOT* covered by the same
copyright, because you can include them for both commercial and non-commercial
use. See below for more infos.

The source code files (codrl1.c, dcodrl1.c, codrle2.c, dcodrle2.c, codrle3.c,
dcodrle3.c, codrle4.c, dcodrle4.c, codhuff.c, dcodhuff.c) are copyrighted.
They have been uploaded on ftp in turing.imag.fr (129.88.31.7):/pub/compression
on 22/5/94 and have been modified on 22/9/94.
(c) David Bourgin - 1994
The source codes I provide have no buggs (!) but being that I make them
available for free I have some notes to make. They can change at any time
without notice. I assume no responsability or liability for any errors or
inaccurracies, make no warranty of any kind (express, implied or statutory)
with respect to this publication and expressly disclaim any and all warranties
of merchantability, fitness for particular purposes. Of course, if you have
some problems to use the information presented here, I will try to help you if
I can.

If you include the source codes in your application, here are the conditions:
- You have to put my name in the header of your source file (not in the
excutable program if you don't want) (this item is a must)
- I would like to see your resulting application, if possible (this item is not
a must, because some applications must remain secret)
- Whenever you gain money with your application, I would like to receive a very
little part in order to be encouraged to update my source codes and to develop
new schemes (this item is not a must)
                          ---------------------

There are several means to compress data. Here, we are only going to deal with
the losslessy schemes. These schemes are also called non-destructive because
you always recover the initial data you had, and this, as soon as you need them.
With losslessy schemes, you won't never lose any informations (except perhaps
when you store or transmit your data but this is another problem...).

In this introduction, we are going to see:
- The RLE scheme (with different possible algorithms)
- The Huffman schemes (dynamical scheme)
- And the LZW scheme

For the novice, a compresser is a program able to read several data (e.g. bytes)
in input and to write several data in output. The data you obtain from the
output (also called compressed data) will - of course - take less space than
the the input data. This is true in most of cases, if the compresser works
and if the type of the data is correct to be compressed with the given scheme.
The codec (coder-decoder) enables you to save space on your hard disk and/or
to save the communication costs because you always store/transmit the compressed
data. You'll use the decompresser as soon as you need to recover your initial
useful data. Note that the compressed data are useless if you have not
the decoder...

You are doubtless asking "How can I reduce the data size without losing some
informations?". It's easy to answer to this question. I'll only take an example.
I'm sure you have heard about the morse. This system established in the 19th
century use a scheme very close to the huffman one. In the morse you encode
the letters to transmit with two kinds of signs. If you encode these two sign
possibilities in one bit, the symbol 'e' is transmitted in a single bit and
the symbols 'y' and 'z' need four bits. Look at the symbols in the text you are
reading, you'll fast understand the compression ratio...

Important: The source codes associated to the algorithms I present are
completely adaptative on what you need to compress. They all use basical
macros on the top of the file. Usually the macros to change are:

- beginning_of_data
- end_of_data
- read_byte
- read_block
- write_byte
- write_block

These allow the programmer to modify only a little part of the header
of the source codes in order to compress as well memory as files.

beginning_of_data(): Macro used to set the program so that the next read_byte()
call will read the first byte to compress.
end_of_data(): Returns a boolean to know whether there is no more bytes to read
from the input stream. Return 0 if there is no more byte to compress, another
non-zero value otherwise.
read_byte(): Returns a byte read from the input stream if available.
write_byte(x): Writes the byte 'x' to the output stream.
read_block(...) and write_block(...): Same use as read_byte and write_byte(x)
but these macros work on blocks of bytes and not only on a single byte.

If you want to compress *from* the memory, before entering in a xxxcoding
procedure ('xxx' is the actual extension to replace with a given codec), you
have to add a pointer set up to the beginning of the zone to compress. Note
that the following pointer 'source_memory_base' is not to add, it is just given
here to specify a name to the address of the memory zone you are going to
encode or decode. That is the same about source_memory_end which can be either
a pointer to create or an existing pointer.

unsigned char *source_memory_base, /* Base of the source memory */
              *source_memory_end,  /* Last address to read.
           source_memory_end=source_memory_base+source_zone_length-1 */
              *source_ptr;         /* Used in the xxxcoding procedure */
void pre_start()
{ source_ptr=source_memory_base;
  xxxcoding();
}

end_of_data() and read_byte() are also to modify to compress *from* memory:

#define end_of_data()  (source_ptr>source_memory_end)
#define read_byte()  (*(source_ptr++))

If you want to compress *to* memory, before entering in a xxxcoding procedure
('xxx' is the actual extension to replace with a given codec), you have to add
a pointer. Note that the pointer 'dest_memory_base' is not to add, it is just
given there to specify the address of the destination memory zone you are
going to encode or decode.

unsigned char *dest_memory_base, /* Base of the destination memory */
              *dest_ptr;         /* Used in the xxxcoding procedure */
void pre_start()
{ dest_ptr=dest_memory_base;
  xxxcoding();
}

Of course, you can combine both from and to memory in the pre_start() procedure.
The files dest_file and source_file handled in the main() function are
to remove...

void pre_start()
{ source_ptr=source_memory_base;
  dest_ptr=dest_memory_base;
  xxxcoding();
}

In fact, to write to memory, the problem is in the write_byte(x) procedure.
This problem exists because your destination zone can either be a static
zone or a dynamically allocated zone. In the two cases, you have to check
if there is no overflow, especially if the coder is not efficient and must
produce more bytes than you reserved in memory.

In the first case, with a *static* zone, write_byte(x) macro should look like
that:

unsigned long int dest_zone_length,
                  current_size;

#define write_byte(x)  { if (current_size==dest_zone_length) \
                            exit(1); \
                         dest_ptr[current_size++]=(unsigned char)(x); \
                       }

In the static version, the pre_start() procedure is to modify as following:

void pre_start()
{ source_ptr=source_memory_base;
  dest_ptr=dest_memory_base;
  dest_zone_length=...; /* Set up to the actual destination zone length */
  current_size=0; /* Number of written bytes */
  xxxcoding();
}
Otherwise, dest_ptr is a zone created by the malloc instruction and you can try
to resize the allocated zone with the realloc instruction. Note that I increment
the zone one kilo-bytes by one kylo-bytes. You have to add two other variables:

unsigned long int dest_zone_length,
                  current_size;

#define write_byte(x)  { if (current_size==dest_zone_length) \
                            { dest_zone_length += 1024; \
                              if ((dest_ptr=(unsigned char *)realloc(dest_ptr,dest_zone_length*sizeof(unsigned char)))==NULL) \
                                 exit(1); /* You can't compress in memory \
                                               => I exit but *you* can make a routine to swap on disk */ \
                            } \
                         dest_ptr[current_size++]=(unsigned char)(x); \
                       }

With the dynamically allocated version, change the pre_start() routine as following:

void pre_start()
{ source_ptr=source_memory_base;
  dest_ptr=dest_memory_base;
  dest_zone_length=1024;
  if ((dest_ptr=(unsigned char *)malloc(dest_zone_length*sizeof(unsigned char)))==NULL)
     exit(1); /* You need at least 1 kb in the dynamical memory ! */
  current_size=0; /* Number of written bytes */
  xxxcoding();
  /* Handle the bytes in dest_ptr but don't forget to free these bytes with:
     free(dest_ptr);
  */
}

The previously given macros work as:

void demo()       /* The file opening, closing and variables
                     must be set up by the calling procedure */
{ unsigned char byte;
                  /* And not 'char byte' (!) */
  while (!end_of_data())
        { byte=read_byte();
          printf("Byte read=%c\n",byte);
        }
}

You must not change the rest of the program unless you're really sure and
really need to do it!

+==========================================================+
|                     The RLE encoding                     |
+==========================================================+

RLE is an acronym that stands for Run Length Encoding. You may encounter it
as an other acronym: RLC, Run Length Coding.

The idea in this scheme is to recode your data with regard to the repetition
frames. A frame is one or more bytes that occurr one or several times.

There are several means to encode occurrences. So, you'll have several codecs.
For example, you may have a sequence such as:
0,0,0,0,0,0,255,255,255,2,3,4,2,3,4,5,8,11

Some codecs will only deal with the repetitions of '0' and '255' but some other
will deal with the repetitions of '0', '255', and '2,3,4'.

You have to keep in your mind something important based on this example. A codec
won't work on all the data you will try to compress. So, in case of non
existence of sequence repetitions, the codecs based on RLE schemes must not
display a message to say: "Bye bye". Actually, they will try to encode these
non repeted data with a value that says "Sorry, I only make a copy of the inital
input". Of course, a copy of the input data with an header in front of this copy
will make a biggest output data but if you consider the whole data to compress,
the encoding of repeated frames will take less space than the encoding
of non-repeated frames.

All of the algorithms with the name of RLE have the following look with three
or four values:
- Value saying if there's a repetition
- Value saying how many repetitions (or non repetition)
- Value of the length of the frame (useless if you just encode frame
with one byte as maximum length)
- Value of the frame to repeat (or not)

I gave four algorithms to explain what I say.

*** First RLE scheme ***

The first scheme is the simpliest I know, and looks like the one used in MAC
system (MacPackBit) and some image file formats such as Targa, PCX, TIFF, ...

Here, all compressed blocks begin with a byte, named header, which description
is:

Bits   7 6 5 4 3 2 1 0
Header X X X X X X X X

Bits 7: Compression status (1=Compression applied)
     0 to 6: Number of bytes to handle

So, if the bit 7 is set up to 0, the 0 to 6 bits give the number of bytes
that follow (minus 1, to gain more over compress) and that were not compressed
(native bytes). If the bit 7 is set up to 1, the same 0 to 6 bits give
the number of repetition (minus 2) of the following byte.

As you see, this method only handle frame with one byte.

Additional note: You have 'minus 1' for non-repeated frames because you must
have at least one byte to compress and 'minus 2' for repeated frames because the
repetition must be 2, at least.

Compression scheme:

              First byte=Next
                    /\
                   /  \
Count the byte         Count the occurrence of NON identical
occurrences            bytes (maximum 128 times)
(maximum 129 times)    and store them in an array
        |                        |
        |                        |
  1 bit '1'                 1 bit '0'
+ 7 bits giving           + 7 bits giving
  the number (-2)           the number (-1)
  of repetitions            of non repetition
+ repeated byte           + n non repeated bytes
        |                        |
 1xxxxxxx,yyyyyyyy        0xxxxxxx,n bytes
[-----------------]      [----------------]

Example:

Sequence of bytes to encode | Coded values | Differences with compression
                            |              |         (unit: byte)
-------------------------------------------------------------------------
       255,15,              |  1,255,15,   |            -1
       255,255,             |    128,255,  |             0
        15,15,              |    128,15,   |             0
     255,255,255,           |   129,255,   |            +1
       15,15,15,            |    129,15,   |            +1
   255,255,255,255,         |   130,255,   |            +2
     15,15,15,15            |    130,15    |            +2

See codecs source codes: codrle1.c and dcodrle1.c

*** Second RLE scheme ***

In the second scheme of RLE compression you look for the less frequent byte
in the source to compress and use it as an header for all compressed block.

In the best cases, the occurrence of this byte is zero in the data to compress.

Two possible schemes, firstly with handling frames with only one byte,
secondly with handling frames with one byte *and* more. The first case is
the subject of this current compression scheme, the second is the subject
of next compression scheme.

For the frame of one byte, header byte is written in front of all repetition
with at least 4 bytes. It is then followed by the repetition number minus 1 and
the repeated byte.
Header byte, Occurrence number-1, repeated byte

If a byte don't repeat more than tree times, the three bytes are written without
changes in the destination stream (no header nor length, nor repetition in front
or after theses bytes).

An exception: If the header byte appears in the source one, two, three and up
times, it'll be respectively encoded as following:
- Header byte, 0
- Header byte, 1
- Header byte, 2
- Header byte, Occurrence number-1, Header byte

Example, let's take the previous example. A non frequent byte is zero-ASCII
because it never appears.

Sequence of bytes to encode | Coded values | Differences with compression
                            |              |         (unit: byte)
-------------------------------------------------------------------------
       255,15,              |    255,15,   |            -1
       255,255,             |   255,255,   |             0
        15,15,              |     15,15,   |             0
     255,255,255,           | 255,255,255, |             0
       15,15,15,            |   15,15,15,  |             0
   255,255,255,255,         |   0,3,255,   |            -1
     15,15,15,15            |    0,3,15    |            -1

If the header would appear, we would see:

Sequence of bytes to encode | Coded values | Differences with compression
                            |              |         (unit: byte)
-------------------------------------------------------------------------
          0,                |      0,0,    |            +1
         255,               |      255,    |             0
         0,0,               |      0,1,    |             0
         15,                |      15,     |             0
        0,0,0,              |      0,2,    |            -1
         255,               |      255,    |             0
       0,0,0,0              |     0,3,0    |            -1

See codecs source codes: codrle2.c and dcodrle2.c

*** Third RLE scheme ***

It's the same idea as the second scheme but we can encode frames with
more than one byte. So we have three cases:

- If it was the header byte, whatever is its occurrence, you encode it with:
Header byte,0,number of occurrence-1
- For frames which (repetition-1)*length>3, encode it as:
Header byte, Number of frame repetition-1, frame length-1,bytes of frame
- If no previous cases were detected, you write them as originally (no header,
nor length, nor repetition in front or after theses bytes).

Example based on the previous examples:

Sequence of bytes to encode |   Coded values   | Differences with compression
                            |                  |         (unit: byte)
-----------------------------------------------------------------------------
           255,15,          |      255,15,     |             0
           255,255,         |     255,255,     |             0
            15,15,          |       15,15,     |             0
         255,255,255,       |   255,255,255,   |             0
           15,15,15,        |     15,15,15,    |             0
       255,255,255,255,     | 255,255,255,255, |             0
         15,15,15,15,       |   15,15,15,15,   |             0
      16,17,18,16,17,18,    |16,17,18,16,17,18,|             0
     255,255,255,255,255,   |    0,4,0,255,    |            -1
       15,15,15,15,15,      |     0,4,0,15,    |            -1
 16,17,18,16,17,18,16,17,18,|  0,2,2,16,17,18, |            -3
  16,17,18,19,16,17,18,19   |0,1,3,16,17,18,19 |            -1

If the header (value 0) would be met, we would see:

Sequence of bytes to encode | Coded values  | Differences with compression
                            |               |         (unit: byte)
--------------------------------------------------------------------------
          0,                |     0,0,0,    |            +2
         255,               |      255,     |             0
         0,0,               |     0,0,1,    |            +1
          15,               |       15,     |             0
        0,0,0,              |     0,0,2,    |             0
         255,               |      255,     |             0
       0,0,0,0              |     0,0,3     |            -1

See codecs source codes: codrle3.c and dcodrle3.c

*** Fourth RLE scheme ***

This last RLE algorithm better handles repetitions of any kind (one byte
and more) and non repetitions, including few non repetitions, and does not
read the source by twice as RLE type 3.

Compression scheme is:

                  First byte=Next byte?
                           /\
                      Yes /  \ No
                         /    \
                 1 bit '0'     1 bit '1'
                       /        \
                      /          \
       Count the                    Motif of several
       occurrences                  repeated  byte?
       of 1 repeated                ( 65 bytes repeated
       byte (maximum                257 times maxi)
       16449 times)                           /\
            /\                               /  \
           /  \                             /    \
          /    \                           /      \
         /      \                         /        \
  1 bit '0'       1 bit '1'        1 bit '0'          1 bit '1'
+ 6 bits        + 14 bits        + 6 bits of              |
giving the      giving the       the length      Number of non repetition
length (-2)     length (-66)     of the motif         (maximum 8224)
of the          of the           + 8 bits of               /\
repeated byte   repeated byte    the number (-2)     < 33 /  \ > 32
+ repeated byte + repeated byte  of repetition           /    \
    |                |           + bytes of the   1 bit '0'       1 bit '1'
    |                |           motif          + 5 bits of     + 13 bits
    |                |               |          the numer (-1)  of the
    |                |               |          of non          number (-33)
    |                |               |          repetition      of repetition
    |                |               |          + non           + non
    |                |               |          repeated        repeated
    |                |               |          bytes           bytes
    |                |               |             |               |
    |                |               |             |  111xxxxx,xxxxxxxx,n bytes
    |                |               |             | [-------------------------]
    |                |               |             |
    |                |               |      110xxxxx,n bytes
    |                |               |     [----------------]
    |                |               |
    |                |  10xxxxxx,yyyyyyyy,n bytes
    |                | [-------------------------]
    |                |
    |   01xxxxxx,xxxxxxxx,1 byte
    |  [------------------------]
    |
 00xxxxxx,1 byte
[---------------]

Example, same as previously:

Sequence of bytes to encode |    Coded values     | Differences with compression
                            |                     |         (unit: byte)
--------------------------------------------------------------------------
       255,15               |   11000001b,255,15, |             +1
       255,255              |   00000000b,255,    |              0
        15,15               |    00000000b,15,    |              0
     255,255,255            |   00000001b,255,    |             -1
       15,15,15             |    00000001b,15,    |             -1
   255,255,255,255          |    00000010b,255,   |             -2
     15,15,15,15            |     00000010b,15,   |             -2
  16,17,18,16,17,18         |10000001b,0,16,17,18,|             -1
 255,255,255,255,255        |   00000011b,255,    |             -3
   15,15,15,15,15           |    00000011b,15,    |             -3
 16,17,18,16,17,18,16,17,18 | 10000001b,16,17,18, |             -4
  16,17,18,19,16,17,18,19   |10000010b,16,17,18,19|             -2

+==========================================================+
|