CompressionTools

KO | EN

gitlite — search

#javascript #hacktoberfest #typescript #golang #android #rust #deep-learning #macos #nodejs #java #cli #vue #pytorch #open-source

CompressionTools

(★ 9)

A set of tools suitable for building compression routines, with a very low resource embedded compresion format as an example.

CompressionTools 최신버젼 다운로드

최종 버전 다운로드 (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Compression Tools - A low resource embedded compression library

This is a tool providing multiple forms of compression (Huffman, Arithmetic, a LZ77 variant, and my own LZ format, LZCL) suitable for low resource environments. A C# compression tool does the compression, provides decompression, and a single file decompressor written in C makes it easy to embed decompression in a C environment.

The usefulness of this is it allows very tunable decompression resource requirements for constrained environments.

The compression tools side provides a lot of primitives for developing compression algorithms with many pluggable and advanced pieces.

Neither side is optimized for speed, as both were meant to be simple and clean to read/extend/implement.

## Usage

### Compression
From the help in CompressionTester.exe

Usage:
     -i inputfile (can be path to do directory with recurse if no output file)
     -o outputfile (if none, no output files)
     -r recurse directories. No outputs
     -f output formats : C# C Binary
     -c codecs         : Arithmetic Huffman Lz77 Lzcl
        The following codec have parameters that can be selected.
        Select as: -c LZ77:param1=value1:param2=value2
                  Lz77:  maxDist - Max distance to look back in buffer
                  Lz77:   minLen - Minimum length of a run to be worthwhile
                  Lz77:   maxLen - Maximum length of a run to be worthwhile
                  Lzcl:  maxDist - Max distance to look back in buffer
                  Lzcl:   minLen - Minimum length of a run to be worthwhile
                  Lzcl:   maxLen - Maximum length of a run to be worthwhile
     -v verbose
     -t test - run current test set
     -d decompress, else compress

You can take a file, compress in one of 4 methods, output to binary or C code, and specify optional parameters if desired.

The compressors generally compress more in order Huffman, Arithmetic, LZ77, LZCL. For general use LZ77 is very good, but if you really need to fit more data in a small space LZCL will beat it handily.

LZ77 and LZCL allow setting the max lookback window and max length of a run. Lower generally lowers compression, but often the optimal value (exhaustively tested) is not large. The buffer size required for these two for incremental decompression is the max of maxDist and maxLen, plus 1. Setting minDist to other than default 2 has is not generally useful.

### Decompression

To decompress in your project, add Decompressor.c and Decompressor.h. In Decompressor.h, select which compression routines you want by commenting out the ones you don't. LZCL needs all the others and will re-`#define` them.

#define DECOMPRESSOR_USE_HUFFMAN
    #define DECOMPRESSOR_USE_ARITHMETIC
    #define DECOMPRESSOR_USE_LZ77
    #define DECOMPRESSOR_USE_LZCL

In your file needing decompression, `#include "Decompressor.h"`, then use code like

uint8_t outputBuffer[DECOMPRESSED_SIZE]; 
    DecompressHuffman(compressedData, sizeof(compressedData), outputBuffer, DECOMPRESSED_SIZE);

to decompress in one large run. The same interface works with `Huffman` replaced by `Arithmetic`, `LZ77`, and `LZCL`.

To decompress incrementally, use each like

// incremental decompression
    uint32_t symbol, index;

// Huffman
    HuffmanState_t huffmanState;
    DecompressHuffmanStart(&huffmanState, huffData, sizeof(huffData));
    index = 0;
    while (1)
    {
        symbol = DecompressHuffmanSymbol(&huffmanState);
        if (symbol == CL_COMPRESSOR_END_TOKEN)
            break;
        ... use symbol here...
    }
    
    // Arithmetic
    ArithmeticState_t arithmeticState;
    uint32_t length = DecompressArithmeticStart(&arithmeticState, arithData, sizeof(arithData));
    index = 0;
    while (index < length) 
    {
        symbol = DecompressArithmeticSymbol(&arithmeticState);
        ... use symbol here ...
    }

// LZ77
    uint8_t localBuffer[<size determined by compression parameters>]; 
    uint32_t destIndex = 0, srcIndex = 0;
    LZ77State_t lz77State;
    DecompressLZ77Start(&lz77State, lz77Data, sizeof(lz77Data),localBuffer,sizeof(localBuffer));
    destIndex = srcIndex = 0;
    while (1)
    {
        uint32_t runLength = DecompressLZ77Block(&lz77State);
        if (runLength == CL_COMPRESSOR_END_TOKEN)
            break;
        // copy out run
        while (runLength-- > 0)
            ... use byte from localBuffer[(srcIndex++)%sizeof(localBuffer)]....
    }

LZCLState_t lzclState;
    DecompressLZCLStart(&lzclState, lzclData, sizeof(lzclData),localBuffer,sizeof(localBuffer));
    destIndex = srcIndex = 0;
    while (1)
    {
        uint32_t runLength = DecompressLZCLBlock(&lzclState);
        if (runLength == CL_COMPRESSOR_END_TOKEN)
            break;
        // copy out run
        while (runLength-- > 0)
            ... use byte from localBuffer[(srcIndex++)%sizeof(localBuffer)]....
    }

And that's it!

## Benchmarks
Compression is generally not very fast, since the algorithms are designed to be easily extended, munged, and used to create more formats if needed. Decompression code is designed to be small, not fast, for the use case I wrote this code for. `Decompressor.c` fits all four decompression routines into a self contained 750ish line C file (~100 for Huffman, ~200 for arithmetic, ~75 for LZ77, ~250 LZCL, rest support.).

The PIC32 sample code, running on a PIC32MX150F128B at 40MHZ, compiled with x32-gcc v1.31, -O3 optimized code, obtains the following decompression rates

| Codec                  | Rate KB/s | Ratio |
| ---------------------- | --------- | ----- |
| Huffman                |   74      |  67%  |
| Arithmetic             |    3      |  66%  |
| LZ77                   |  327      |  53%  |
| LZCL                   |   16      |  42%  |
| Incremental Huffman    |   74      |  67%  |
| Incremental Arithmetic |    3      |  66%  |
| Incremental LZ77       |  285      |  53%  |
| Incremental LZCL       |   16      |  42%  |

This was tested on a compressed version of the 26217 byte file `Decompressor.c`, with both LZ variants set to allow decoding incrementally into a 257 byte buffer.

A common test for smaller files is the Calgary Corpus and Cantebury Corpus

|               Filename | File size | Arithmetic ratio | Arithmetic size | Huffman ratio | Huffman size | Lz77 ratio | Lz77 size | LZCL ratio |   LZCL size |
|------------------------|----------:|------------------|----------------:|---------------|-------------:|------------|----------:|------------|------------:|
|            Calgary\bib |    111261 |            0.651 |           72483 |         0.655 |        72845 |      0.574 |     63813 |  **0.435** |   **48387** |
|          Calgary\book1 |    768771 |            0.566 |          435264 |         0.570 |       438461 |      0.661 |    508162 |  **0.486** |  **373303** |
|          Calgary\book2 |    610856 |            0.599 |          366165 |         0.603 |       368398 |      0.576 |    351818 |  **0.420** |  **256308** |
|            Calgary\geo |    102400 |            0.709 |           72596 |         0.711 |        72826 |      0.898 |     91974 |  **0.645** |   **66024** |
|           Calgary\news |    377109 |            0.649 |          244824 |         0.654 |       246492 |      0.648 |    244267 |  **0.454** |  **171081** |
|           Calgary\obj1 |     21504 |            0.755 |           16242 |         0.759 |        16321 |      0.648 |     13927 |  **0.527** |   **11339** |
|           Calgary\obj2 |    246814 |            0.784 |          193533 |         0.787 |       194366 |      0.484 |    119553 |  **0.361** |   **89035** |
|         Calgary\paper1 |     53161 |            0.626 |           33255 |         0.629 |        33433 |      0.535 |     28421 |  **0.426** |   **22649** |
|         Calgary\paper2 |     82199 |            0.577 |           47422 |         0.580 |        47706 |      0.571 |     46956 |  **0.448** |   **36842** |
|         Calgary\paper3 |     46526 |            0.586 |           27260 |         0.588 |        27360 |      0.568 |     26411 |  **0.474** |   **22036** |
|         Calgary\paper4 |     13286 |            0.596 |            7914 |         0.598 |         7942 |      0.543 |      7214 |  **0.477** |    **6334** |
|         Calgary\paper5 |     11954 |            0.627 |            7494 |         0.629 |         7522 |      0.564 |      6740 |  **0.478** |    **5718** |
|         Calgary\paper6 |     38105 |            0.630 |           23998 |         0.633 |        24117 |      0.561 |     21379 |  **0.431** |   **16412** |
|            Calgary\pic |    513216 |            0.152 |           77890 |         0.208 |       106726 |      0.153 |     78292 |  **0.103** |   **52851** |
|          Calgary\progc |     39611 |            0.653 |           25883 |         0.657 |        26007 |      0.502 |     19902 |  **0.417** |   **16519** |
|          Calgary\progl |     71646 |            0.598 |           42859 |         0.601 |        43071 |      0.362 |     25953 |  **0.277** |   **19819** |
|          Calgary\progp |     49379 |            0.611 |           30195 |         0.614 |        30303 |      0.351 |     17356 |  **0.275** |   **13568** |
|          Calgary\trans |     93695 |            0.693 |           64972 |         0.697 |        65318 |      0.412 |     38625 |  **0.312** |   **29219** |
|  Cantebury\alice29.txt |    152089 |            0.572 |           86979 |         0.577 |        87765 |      0.595 |     90565 |  **0.439** |   **66710** |
| Cantebury\asyoulik.txt |    125179 |            0.602 |           75380 |         0.606 |        75877 |      0.652 |     81660 |  **0.471** |   **58992** |
|      Cantebury\cp.html |     24603 |            0.660 |           16242 |         0.662 |        16295 |      0.501 |     12334 |  **0.423** |   **10414** |
|     Cantebury\fields.c |     11150 |            0.637 |            7097 |         0.638 |         7117 |      0.389 |      4340 |  **0.322** |    **3588** |
|  Cantebury\grammar.lsp |      3721 |            0.603 |            2245 |         0.604 |         2246 |      0.435 |      1617 |  **0.394** |    **1465** |
|   Cantebury\lcet10.txt |    426754 |            0.584 |          249251 |         0.587 |       250651 |      0.576 |    245861 |  **0.419** |  **178911** |
| Cantebury\plrabn12.txt |    481861 |            0.567 |          273117 |         0.572 |       275670 |      0.655 |    315855 |  **0.481** |  **231722** |
|         Cantebury\ptt5 |    513216 |            0.152 |           77890 |         0.208 |       106726 |      0.153 |     78292 |  **0.103** |   **52851** |
|          Cantebury\sum |     38240 |            0.673 |           25733 |         0.678 |        25915 |      0.562 |     21497 |  **0.412** |   **15746** |
|      Cantebury\xargs.1 |      4227 |            0.634 |            2679 |         0.633 |         2676 |      0.517 |      2184 |  **0.474** |    **2004** |
|                Summary |   5032533 |            0.518 |         2606862 |         0.533 |      2680152 |      0.510 |   2564968 |  **0.374** | **1879847** |

Finally, LZ77 and LZCL can vary drastically with different parameters - the above parameters are not tuned to be optimal, which can be done by exhaustively trying them.

## Project

The code includes a Visual Studio 2015 project that contains the C# compressor, a C DLL to test decompression, and also includes a PIC32 sample program to illustrate usage and to measure decompression speed.

## LZCL

My LZCL format is a very bit optimized format, separating the usual LZ77 streams into components
   - Decisions: 0/1 to tell next token type
   - Literals: single bytes encoded
   - Tokens: each is a distance, length pair, encoded in one of two methods

It was designed to solve a use case I had to get the best compression I could, subject to very small code size and very low memory usage for an embedded project. I may finalize the spec carefully (it requires careful specification of multiple other sub-formats... a lot of work) one day.

Some advanced codecs that are small are used here: Golomb coding and Binary Adaptive Sequential Coding (BASC).

Then, decisions is either stored as a bitstream of 0/1, or converted to runs (basic RLE compression). Tokens are tested as both (distance,length) pairs and encoded similarly to length*(maxDistance+1)+distance. All these variants are tested across all supported compression formats (Fixed length, Huffman, Arithmetic, Golomb Coding), and the best combination is chosen.

All formats contribute a decent amount on the corpus tests above.

I plan to write two longer articles on all of this at (or possibly at lomont.org, once I merge sites):

http://clomont.com/programming/compression-notes/
http://clomont.com/software/lzcl-an-embedded-compression-library/

Happy hacking!
Chris Lomont

CompressionTools

CompressionTools 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

CompressionTools

CompressionTools 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README