2 * LiZaRd -- Fast compression method based on Lempel-Ziv 77
4 * (c) 2004, Robert Spalek <robert@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
20 * The compression routine needs input buffer 8 characters longer, because it
21 * does not check the input bounds all the time.
23 #define LIZARD_NEEDS_CHARS 8
25 #define LIZARD_MAX_MULTIPLY 23./22
26 #define LIZARD_MAX_ADD 4
27 /* In the worst case, the compressed file will not be longer than its
28 * original length * 23/22 + 4.
30 * The additive constant is for EOF and the header of the file.
32 * The multiplicative constant comes from 19-byte incompressible string
33 * followed by a 3-sequence that can be compressed into 2-byte link. This
34 * breaks the copy-mode and it needs to be restarted with a new header. The
35 * total length is 2(header) + 19(string) + 2(link) = 23.
39 * The compressed data will not be longer than `LIZARD_MAX_LEN(input_length)`.
40 * Note that `LIZARD_MAX_LEN(length) > length` (this is not a problem of the algorithm,
41 * every lossless compression algorithm must have an input for which it produces a larger
44 * Use this to compute the size of @out paramater of @lizard_compress().
46 #define LIZARD_MAX_LEN(LENGTH) ((LENGTH) * LIZARD_MAX_MULTIPLY + LIZARD_MAX_ADD)
51 * Compress data provided in @in.
52 * The input buffer must be at last `@in_len + <<def_LIZARD_NEEDS_CHARS,LIZARD_NEEDS_CHARS>>`
53 * long (the compression algorithm does not check the bounds all the time).
55 * The output will be stored in @out. The @out buffer must be at last <<def_LIZARD_LEN,`LIZARD_LEN(@in_len)`>>
56 * bytes long for the output to fit in for sure.
58 * The function returns number of bytes actually needed (the size of output).
60 * Use @lizard_decompress() to get the original data.
62 int lizard_compress(const byte *in, uns in_len, byte *out);
65 * Decompress data previously compressed by @lizard_compress().
66 * Input is taken from @in and the result stored in @out.
67 * The size of output is returned.
69 * Note that you need to know the maximal possible size of the output to
70 * allocate enough memory.
72 * See also <<safe,safe decompression>>.
74 int lizard_decompress(const byte *in, byte *out);
83 * You can use safe decompression, when you want to make sure you got the
84 * length right and when you want to reuse the buffer for output.
87 struct lizard_buffer; /** Type of the output buffer for @lizard_decompress_safe(). **/
89 struct lizard_buffer *lizard_alloc(void); /** Get me a new <<struct_lizard_buffer,`lizard_buffer`>>. **/
90 void lizard_free(struct lizard_buffer *buf); /** Return memory used by a <<struct_lizard_buffer,`lizard_buffer`>>. **/
93 * Decompress data previously compressed by @lizard_compress().
94 * Input is taken from @in. @buf is used to store the output.
95 * You need to provide the length of the uncompressed data in @expected_length.
97 * The pointer to data is returned.
99 * If an error occurs, NULL is returned and `errno` is set.
100 * `EINVAL` means the actual length does not match @expected_length.
101 * `EFAULT` means a segfault was encountered while decompressing (probably @expected_length was way too low).
103 byte *lizard_decompress_safe(const byte *in, struct lizard_buffer *buf, uns expected_length);
112 * This is here because it is commonly used to check data compressed by LiZaRd.
113 * However, it could also belong to <<hash,hashing routines>>.
117 * Update the Adler-32 checksum with more data.
118 * @adler is the old value, @byte points to @len bytes of data to update with.
119 * Result is returned.
121 uns adler32_update(uns adler, const byte *ptr, uns len);
124 * Compute the Adler-32 checksum of a block of data.
126 static inline uns adler32(const byte *buf, uns len)
128 return adler32_update(1, buf, len);