1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
////////////////////////////////////////////////////////////////////////////
// **** LIBULZW **** //
// Adjusted Binary LZW Compressor/Decompressor //
// Copyright (c) 2016 David Bryant //
// All Rights Reserved //
// Distributed under the BSD Software License (see license.txt) //
////////////////////////////////////////////////////////////////////////////
This project is a fork of https://github.com/dbry/lzw-ab/, ported to C89.
Libulzw is hosted in svn, at svn://repo.hu/libulzw/trunk
Maintainer: Tibor 'Igor2' Palinkas
Contact the maintainer: http://igor2.repo.hu/contact.html
This is an implementation of the Lempel-Ziv-Welch general-purpose data
compression algorithm. It is targeted at embedded applications that require
high speed compression or decompression facilities where lots of RAM for
large dictionaries might not be available. I have used this in several
projects for storing compressed firmware images, and once I even coded the
decompressor in Z-80 assembly language for speed! Depending on the maximum
symbol size selected, the implementation can require from 1024 to 15360
bytes of RAM for decoding (and slightly more for encoding).
The symbols are stored in adjusted binary, which provides considerably
better compression performance (with virtually no speed penalty) compared
to the fixed sizes nominally used. To ensure good performance on data with
varying characteristics (like executable images) the encoder resets as
soon as the dictionary is full. Also, worst-case performance is limited
to about 8% inflation by catching poor performance and forcing an early
reset before longer symbols are sent.
LIBULZW consists of two standard C files (the library and a command-line
demo using pipes). It has been designed with maximum portability in mind
and should work correctly on big-endian as well as little-endian machines.
/* This library implements the LZW general-purpose data compression algorithm.
* The algorithm was originally described as a hardware implementation by
* Terry Welsh here:
*
* Welch, T.A. A Technique for High-Performance Data Compression.
* IEEE Computer 17,6 (June 1984), pp. 8-19
*
* Since then there have been enumerable refinements and variations on the
* basic technique, and this implementation is no different. The target of
* the present implementation is embedded systems, and so emphasis was placed
* on simplicity, fast execution, and minimal RAM usage.
*
* The symbols are stored in adjusted binary, which provides considerably
* better compression performance with virtually no speed penalty compared to
* the fixed sizes normally used. To ensure good performance on data with
* varying characteristics (like executable images) the encoder resets as
* soon as the dictionary is full. Also, worst-case performance is limited
* to about 8% inflation by catching poor performance and forcing an early
* reset before longer symbols are sent.
*
* The maximum symbol size is configurable on the encode side (from 9 bits
* to 12 bits) and determines the RAM footprint required by both sides and,
* to a large extent, the compression performance. This information is
* communicated to the decoder in the first stream byte so that it can
* allocate accordingly. The RAM requirements are as follows:
*
* maximum encoder RAM decoder RAM
* symbol size requirement requirement
* -----------------------------------------
* 9-bit 1792 bytes 1024 bytes
* 10-bit 4352 bytes 3072 bytes
* 11-bit 9472 bytes 7168 bytes
* 12-bit 19712 bytes 15360 bytes
*
* This implementation uses malloc(), but obviously an embedded version could
* use static arrays instead if desired (assuming that the maxbits was
* controlled outside).
*/
|
