CMPS 4350


LZ77-A Compression

Last updated: Tuesday, February 9, 2021

Table of Contents

 1  |  Name

2  |  Description

3  |  Format

        3.1   |  Compressor

        3.2  |  Decompressor

4  |  Source Code

        4.1   |  Compressor

        4.2  |  Decompressor

5  |  Profiling

        5.1   |  Terminal Output

        5.2   |  KCachegrind Output

6  |  References



1 | Name

LZ77-A


2 | Description

LZ77-A is my version of the LZ77 compression algorithm published by Abraham Lempel and Jacob Ziv in 1977.


3 | Format

The LZ77-A format definition is as follows.


3.1  |  Compressor

1. Check if character at input pointer address is equal to character at previous pointer address.

2. If they are the same, then make value of output pointer address equal to '1', pointer address + 1 equal to '1', and pointer address + 2 equal to value in input pointer address + 1.

3. Increase output pointer address by 3 and increase input pointer adress by 2.

4. Else if they are not the same, then make value of output pointer address equal to '0', pointer address + 1 equal to '0', and pointer address + 2 equal to value in input pointer address.

5. Increase output pointer address by 3, and increase input pointer address by 1.


3.2  |  Decompressor

1. Set variable "repeat" to equal value of pointer address + 1.

2. If that value is not equal to 0, then print out value at pointer address - 1 and repeat until it equals value of "repeat".

3. Else if the value is equal to 0, then print out value at pointer address plus 2.


4 | Source Code

The LZ77-A source code is written in the C++ language.


4.1  |  Compressor

The LZ77-A source code is written in the C++ language.

for (int i=0; i < length; i++) {
    if (*p1 == *(p1-1)) {
        *(p2+0) = '1';
        *(p2+1) = '1';
        *(p2+2) = *(p1+1);

        p2 += 3;
        p1 += 2;
        ++i;
    } else {
        *(p2+0) = '0';
        *(p2+1) = '0';
        *(p2+2) = *p1;

        p2 += 3;
        ++p1;
    }
}

4.2  |  Decompressor

The LZ77-A source code is written in the C++ language.

for (int i=1; i < length; i += 3) {
    int repeat = atoi(&buffer[i+1]);
    if (repeat != 0) {
        for (int j=0; j < repeat; j++) {
            fout << buffer[i-1];
        }
    }
    fout << buffer[i+2];
}

5 | Profiling

Here are some examples of profiling using Valgrind profiling tools.


5.1  |  Terminal Output

Here is some terminal output using Valgrind profiling.



5.2  |  KCachegrind Output

Here is some profiling output using the KCachegrind GUI tool included with Valgrind.


6 | References

The following references were used.

https://developer.mantidproject.org/ProfilingWithValgrind.html

http://kcachegrind.sourceforge.net/html/Usage.html