diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/lzip.1 | 5 | ||||
| -rw-r--r-- | doc/lzip.info | 255 | ||||
| -rw-r--r-- | doc/lzip.texinfo | 246 |
3 files changed, 282 insertions, 224 deletions
@@ -1,5 +1,5 @@ .\" DO NOT MODIFY THIS FILE! It was generated by help2man 1.37.1. -.TH LZIP "1" "July 2013" "Lzip 1.15-pre3" "User Commands" +.TH LZIP "1" "August 2013" "Lzip 1.15-rc1" "User Commands" .SH NAME Lzip \- reduces the size of files .SH SYNOPSIS @@ -70,7 +70,8 @@ Ki = KiB = 2^10 = 1024, M = 10^6, Mi = 2^20, G = 10^9, Gi = 2^30, etc... The bidimensional parameter space of LZMA can't be mapped to a linear scale optimal for all files. If your files are large, very repetitive, etc, you may need to use the \fB\-\-match\-length\fR and \fB\-\-dictionary\-size\fR -options directly to achieve optimal performance. +options directly to achieve optimal performance. For example, \fB\-9m64\fR +usually compresses executables more (and faster) than \fB\-9\fR. .PP Exit status: 0 for a normal exit, 1 for environmental problems (file not found, invalid flags, I/O errors, etc), 2 to indicate a corrupt or diff --git a/doc/lzip.info b/doc/lzip.info index 97d2bbb..4445d40 100644 --- a/doc/lzip.info +++ b/doc/lzip.info @@ -11,7 +11,7 @@ File: lzip.info, Node: Top, Next: Introduction, Up: (dir) Lzip Manual *********** -This manual is for Lzip (version 1.15-pre3, 15 July 2013). +This manual is for Lzip (version 1.15-rc1, 1 August 2013). * Menu: @@ -43,10 +43,6 @@ compresses more than bzip2, which makes it well suited for software distribution and data archiving. Lzip is a clean implementation of the LZMA algorithm. - Lzip uses the same well-defined exit status values used by bzip2, -which makes it safer when used in pipes or scripts than compressors -returning ambiguous warning values, like gzip. - The lzip file format is designed for long-term data archiving and provides very safe integrity checking. The member trailer stores the 32-bit CRC of the original data, the size of the original data and the @@ -63,7 +59,12 @@ recover the original uncompressed data. If you ever need to recover data from a damaged lzip file, try the lziprecover program. Lziprecover makes lzip files resistant to bit-flip (one of the most common forms of data corruption), and provides data -recovery capabilities, including error-checked merging of damaged files. +recovery capabilities, including error-checked merging of damaged copies +of a file. + + Lzip uses the same well-defined exit status values used by bzip2, +which makes it safer when used in pipes or scripts than compressors +returning ambiguous warning values, like gzip. Lzip replaces every file given in the command line with a compressed version of itself, with the name "original_name.lz". Each compressed @@ -90,7 +91,7 @@ multivolume compressed tar archives. Lzip is able to compress and decompress streams of unlimited size by automatically creating multi-member output. The members so created are -large (about 2^60 bytes each). +large, about 64 PiB each. The amount of memory required for compression is about 1 or 2 times the dictionary size limit (1 if input file size is less than dictionary @@ -170,7 +171,7 @@ The ideas embodied in lzip are due to (at least) the following people: Abraham Lempel and Jacob Ziv (for the LZ algorithm), Andrey Markov (for the definition of Markov chains), G.N.N. Martin (for the definition of range encoding), Igor Pavlov (for putting all the above together in -LZMA), and Julian Seward (for bzip2's CLI and the idea of unzcrash). +LZMA), and Julian Seward (for bzip2's CLI). File: lzip.info, Node: Invoking lzip, Next: File format, Prev: Algorithm, Up: Top @@ -194,10 +195,9 @@ The format for running lzip is: `-b BYTES' `--member-size=BYTES' - Produce a multi-member file and set the member size limit to BYTES. - Minimum member size limit is 100kB. Small member size may degrade - compression ratio, so use it only when needed. The default is to - produce single-member files. + Set the member size limit to BYTES. A small member size may + degrade compression ratio, so use it only when needed. Valid values + range from 100 kB to 64 PiB. Defaults to 64 PiB. `-c' `--stdout' @@ -246,8 +246,8 @@ The format for running lzip is: `-s BYTES' `--dictionary-size=BYTES' - Set the dictionary size limit in bytes. Valid values range from - 4KiB to 512MiB. Lzip will use the smallest possible dictionary + Set the dictionary size limit in bytes. Valid values range from 4 + KiB to 512 MiB. Lzip will use the smallest possible dictionary size for each member without exceeding this limit. Note that dictionary sizes are quantized. If the specified size does not match one of the valid sizes, it will be rounded upwards by adding @@ -263,9 +263,9 @@ The format for running lzip is: Split the compressed output into several volume files with names `original_name00001.lz', `original_name00002.lz', etc, and set the volume size limit to BYTES. Each volume is a complete, maybe - multi-member, lzip file. Minimum volume size limit is 100kB. Small - volume size may degrade compression ratio, so use it only when - needed. + multi-member, lzip file. A small volume size may degrade + compression ratio, so use it only when needed. Valid values range + from 100 kB to 4 EiB. `-t' `--test' @@ -293,7 +293,8 @@ The format for running lzip is: linear scale optimal for all files. If your files are large, very repetitive, etc, you may need to use the `--match-length' and `--dictionary-size' options directly to achieve optimal - performance. + performance. For example, `-9m64' usually compresses executables + more (and faster) than `-9'. Level Dictionary size Match length limit -0 64 KiB 16 bytes @@ -312,7 +313,6 @@ The format for running lzip is: Aliases for GNU gzip compatibility. - Numbers given as arguments to options may be followed by a multiplier and an optional `B' for "byte". @@ -371,7 +371,7 @@ additional information before, between, or after them. `ID string' A four byte string, identifying the lzip format, with the value - "LZIP". + "LZIP" (0x4C, 0x5A, 0x49, 0x50). `VN (version number, 1 byte)' Just in case something needs to be modified in the future. 1 for @@ -386,12 +386,13 @@ additional information before, between, or after them. Bits 4-0 contain the base 2 logarithm of the base size (12 to 29). Bits 7-5 contain the number of wedges (0 to 7) to substract from the base size to obtain the dictionary size. - Example: 0xD3 = (2^19 - 6 * 2^15) = (512KiB - 6 * 32KiB) = 320KiB - Valid values for dictionary size range from 4KiB to 512MiB. + Example: 0xD3 = 2^19 - 6 * 2^15 = 512 KiB - 6 * 32 KiB = 320 KiB + Valid values for dictionary size range from 4 KiB to 512 MiB. `Lzma stream' The lzma stream, finished by an end of stream marker. Uses default - values for encoder properties. + values for encoder properties. See the chapter `Stream format' + (*note Stream format::) for a complete description. `CRC32 (4 bytes)' CRC of the uncompressed original data. @@ -508,8 +509,9 @@ integers representing the probability of the corresponding bit being 0. The indices used in these arrays are: `state' - A state machine (`State' in the source) coding the latest 2 to 4 - types of sequences processed. The initial state is 0. + A state machine (`State' in the source) with 12 states (0 to 11), + coding the latest 2 to 4 types of sequences processed. The initial + state is 0. `pos_state' Value of the 2 least significant bits of the current position in @@ -523,6 +525,26 @@ integers representing the probability of the corresponding bit being 0. resulting value is in the range 0 to 3. + In the following table, `!literal' is any sequence except a literal +byte. `rep' is any one of `rep0', `rep1', `rep2' or `rep3'. The types +of previous sequences corresponding to each state are: + +State Types of previous sequences +---------------------------------------------- +0 literal, literal, literal +1 match, literal, literal +2 (rep or shortrep), literal, literal +3 literal, shortrep, literal, literal +4 match, literal +5 (rep or shortrep), literal +6 literal, shortrep, literal +7 literal, match +8 literal, rep +9 literal, shortrep +10 !literal, match +11 !literal, (rep or shortrep) + + The contexts for decoding the type of coding sequence are: Name Indices Used when @@ -619,7 +641,7 @@ and show the compression ratio. Example 2: Like example 1 but the created `file.lz' is multi-member -with a member size of 1MiB. The compression ratio is not shown. +with a member size of 1 MiB. The compression ratio is not shown. lzip -b 1MiB file @@ -642,7 +664,7 @@ Example 5: Compress a whole floppy in /dev/fd0 and send the output to lzip -c /dev/fd0 > file.lz -Example 6: Decompress `file.lz' partially until 10KiB of decompressed +Example 6: Decompress `file.lz' partially until 10 KiB of decompressed data are produced. lzip -cd file.lz | dd bs=1024 count=10 @@ -655,7 +677,7 @@ to decompressed byte 15000 (5000 bytes are produced). Example 8: Create a multivolume compressed tar archive with a volume -size of 1440KiB. +size of 1440 KiB. tar -c some_directory | lzip -S 1440KiB -o volume_name @@ -665,9 +687,9 @@ Example 9: Extract a multivolume compressed tar archive. lzip -cd volume_name*.lz | tar -xf - -Example 10: Create a multivolume compressed backup of a big database -file with a volume size of 650MB, where each volume is a multi-member -file with a member size of 32MiB. +Example 10: Create a multivolume compressed backup of a large database +file with a volume size of 650 MB, where each volume is a multi-member +file with a member size of 32 MiB. lzip -b 32MiB -S 650MB big_db @@ -692,6 +714,22 @@ File: lzip.info, Node: Reference source code, Next: Concept index, Prev: Prob Appendix A Reference source code ******************************** +/* Lzd - Educational decompressor for lzip files + Copyright (C) 2013 Antonio Diaz Diaz. + + This program is free software: you have unlimited permission + to copy, distribute and modify it. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. +*/ +/* + Exit status: 0 for a normal exit, 1 for environmental problems + (file not found, invalid flags, I/O errors, etc), 2 to indicate a + corrupt or invalid input file. +*/ + #include <algorithm> #include <cerrno> #include <cstdio> @@ -716,20 +754,20 @@ public: static const int next[states] = { 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5 }; st = next[st]; } - - void set_match() { st = ( ( st < 7 ) ? 7 : 10 ); } - void set_rep() { st = ( ( st < 7 ) ? 8 : 11 ); } - void set_short_rep() { st = ( ( st < 7 ) ? 9 : 11 ); } + void set_match() { st = ( st < 7 ) ? 7 : 10; } + void set_rep() { st = ( st < 7 ) ? 8 : 11; } + void set_short_rep() { st = ( st < 7 ) ? 9 : 11; } }; enum { + min_dictionary_size = 1 << 12, + max_dictionary_size = 1 << 29, literal_context_bits = 3, pos_state_bits = 2, pos_states = 1 << pos_state_bits, pos_state_mask = pos_states - 1, - max_dis_states = 4, dis_slot_bits = 6, start_dis_model = 4, end_dis_model = 14, @@ -744,13 +782,14 @@ enum { len_mid_symbols = 1 << len_mid_bits, len_high_symbols = 1 << len_high_bits, max_len_symbols = len_low_symbols + len_mid_symbols + len_high_symbols, + min_match_len = 2, // must be 2 + max_dis_states = 4, bit_model_move_bits = 5, bit_model_total_bits = 11, bit_model_total = 1 << bit_model_total_bits }; - struct Bit_model { int probability; @@ -767,6 +806,40 @@ struct Len_model }; +class CRC32 + { + uint32_t data[256]; // Table of CRCs of all 8-bit messages. + +public: + CRC32() + { + for( unsigned n = 0; n < 256; ++n ) + { + unsigned c = n; + for( int k = 0; k < 8; ++k ) + { if( c & 1 ) c = 0xEDB88320U ^ ( c >> 1 ); else c >>= 1; } + data[n] = c; + } + } + + void update_buf( uint32_t & crc, const uint8_t * const buffer, + const int size ) const + { + for( int i = 0; i < size; ++i ) + crc = data[(crc^buffer[i])&0xFF] ^ ( crc >> 8 ); + } + }; + +const CRC32 crc32; + + +typedef uint8_t File_header[6]; // 0-3 magic, 4 version, 5 coded_dict_size + +typedef uint8_t File_trailer[20]; + // 0-3 CRC32 of the uncompressed data + // 4-11 size of the uncompressed data + // 12-19 member size including header and trailer + class Range_decoder { uint32_t code; @@ -775,9 +848,11 @@ class Range_decoder public: Range_decoder() : code( 0 ), range( 0xFFFFFFFFU ) { - for( int i = 0; i < 5; ++i ) code = (code << 8) | std::getc( stdin ); + for( int i = 0; i < 5; ++i ) code = (code << 8) | get_byte(); } + uint8_t get_byte() { return std::getc( stdin ); } + int decode( const int num_bits ) { int symbol = 0; @@ -787,7 +862,7 @@ public: symbol <<= 1; if( code >= range ) { code -= range; symbol |= 1; } if( range <= 0x00FFFFFFU ) // normalize - { range <<= 8; code = (code << 8) | std::getc( stdin ); } + { range <<= 8; code = (code << 8) | get_byte(); } } return symbol; } @@ -810,7 +885,7 @@ public: symbol = 1; } if( range <= 0x00FFFFFFU ) // normalize - { range <<= 8; code = (code << 8) | std::getc( stdin ); } + { range <<= 8; code = (code << 8) | get_byte(); } return symbol; } @@ -856,12 +931,11 @@ public: int decode_len( Len_model & lm, const int pos_state ) { if( decode_bit( lm.choice1 ) == 0 ) - return min_match_len + - decode_tree( lm.bm_low[pos_state], len_low_bits ); + return decode_tree( lm.bm_low[pos_state], len_low_bits ); if( decode_bit( lm.choice2 ) == 0 ) - return min_match_len + len_low_symbols + + return len_low_symbols + decode_tree( lm.bm_mid[pos_state], len_mid_bits ); - return min_match_len + len_low_symbols + len_mid_symbols + + return len_low_symbols + len_mid_symbols + decode_tree( lm.bm_high, len_high_bits ); } }; @@ -881,8 +955,8 @@ class LZ_decoder uint8_t get_byte( const unsigned distance ) const { - int i = pos - distance - 1; - if( i < 0 ) i += dictionary_size; + unsigned i = pos - distance - 1; + if( pos <= distance ) i += dictionary_size; return buffer[i]; } @@ -912,38 +986,12 @@ public: }; -class CRC32 - { - uint32_t data[256]; // Table of CRCs of all 8-bit messages. - -public: - CRC32() - { - for( unsigned n = 0; n < 256; ++n ) - { - unsigned c = n; - for( int k = 0; k < 8; ++k ) - { if( c & 1 ) c = 0xEDB88320U ^ ( c >> 1 ); else c >>= 1; } - data[n] = c; - } - } - - void update( uint32_t & crc, const uint8_t * buffer, const int size ) const - { - for( int i = 0; i < size; ++i ) - crc = data[(crc^buffer[i])&0xFF] ^ ( crc >> 8 ); - } - }; - -const CRC32 crc32; - - void LZ_decoder::flush_data() { if( pos > stream_pos ) { const unsigned size = pos - stream_pos; - crc32.update( crc_, buffer + stream_pos, size ); + crc32.update_buf( crc_, buffer + stream_pos, size ); errno = 0; if( std::fwrite( buffer + stream_pos, 1, size, stdout ) != size ) { std::fprintf( stderr, "Write error: %s\n", std::strerror( errno ) ); @@ -993,12 +1041,7 @@ bool LZ_decoder::decode_member() // Returns false if error int len; if( rdec.decode_bit( bm_rep[state()] ) == 1 ) // 2nd bit { - if( rdec.decode_bit( bm_rep0[state()] ) == 0 ) // 3rd bit - { - if( rdec.decode_bit( bm_len[state()][pos_state] ) == 0 ) // 4th bit - { state.set_short_rep(); put_byte( get_byte( rep0 ) ); continue; } - } - else + if( rdec.decode_bit( bm_rep0[state()] ) == 1 ) // 3rd bit { unsigned distance; if( rdec.decode_bit( bm_rep1[state()] ) == 0 ) // 4th bit @@ -1014,13 +1057,18 @@ bool LZ_decoder::decode_member() // Returns false if error rep1 = rep0; rep0 = distance; } - len = rdec.decode_len( rep_len_model, pos_state ); + else + { + if( rdec.decode_bit( bm_len[state()][pos_state] ) == 0 ) // 4th bit + { state.set_short_rep(); put_byte( get_byte( rep0 ) ); continue; } + } + len = min_match_len + rdec.decode_len( rep_len_model, pos_state ); state.set_rep(); } else { rep3 = rep2; rep2 = rep1; rep1 = rep0; - len = rdec.decode_len( match_len_model, pos_state ); + len = min_match_len + rdec.decode_len( match_len_model, pos_state ); const int dis_state = std::min( len - min_match_len, max_dis_states - 1 ); const int dis_slot = rdec.decode_tree( bm_dis_slot[dis_state], dis_slot_bits ); @@ -1055,46 +1103,25 @@ bool LZ_decoder::decode_member() // Returns false if error } -enum { min_dictionary_size = 1 << 12, - max_dictionary_size = 1 << 29 }; - -typedef uint8_t File_header[6]; // 0-3 magic, 4 version, 5 coded_dict_size - -typedef uint8_t File_trailer[20]; - // 0-3 CRC32 of the uncompressed data - // 4-11 size of the uncompressed data - // 12-19 member size including header and trailer - - -/* Exit status: 0 for a normal exit, 1 for environmental problems - (file not found, invalid flags, I/O errors, etc), 2 to indicate a - corrupt or invalid input file. */ - int main( const int argc, const char * const argv[] ) { if( argc > 1 ) { std::printf( "Lzd %s - Educational decompressor for lzip files.\n", PROGVERSION ); - std::printf( "Study the source to learn how a simple lzip decompressor works.\n" - "It is not safe to use it for any real work.\n" + std::printf( "Study the source to learn how a lzip decompressor works.\n" + "See the lzip manual for an explanation of the code.\n" + "It is not safe to use lzd for any real work.\n" "\nUsage: %s < file.lz > file\n", argv[0] ); std::printf( "Lzd decompresses from standard input to standard output.\n" "\nCopyright (C) 2013 Antonio Diaz Diaz.\n" "This is free software: you are free to change and redistribute it.\n" "There is NO WARRANTY, to the extent permitted by law.\n" "Report bugs to lzip-bug@nongnu.org\n" - "Lzip home page: http://www.nongnu.org/lzip/lzip.html\n" ); + "Lzd home page: http://www.nongnu.org/lzip/lzd.html\n" ); return 0; } - if( isatty( STDIN_FILENO ) ) - { - std::fprintf( stderr, "I won't read compressed data from a terminal.\n" - "Try '%s --help' for more information.\n", argv[0] ); - return 1; - } - for( bool first_member = true; ; first_member = false ) { File_header header; @@ -1166,14 +1193,14 @@ Concept index Tag Table: Node: Top210 Node: Introduction1052 -Node: Algorithm5006 -Node: Invoking lzip7524 -Node: File format13162 -Node: Stream format15595 -Node: Examples24309 -Node: Problems26258 -Node: Reference source code26788 -Node: Concept index40035 +Node: Algorithm5012 +Node: Invoking lzip7505 +Node: File format13181 +Node: Stream format15729 +Node: Examples25134 +Node: Problems27090 +Node: Reference source code27620 +Node: Concept index41135 End Tag Table diff --git a/doc/lzip.texinfo b/doc/lzip.texinfo index 1c04f2c..0e8ac92 100644 --- a/doc/lzip.texinfo +++ b/doc/lzip.texinfo @@ -6,8 +6,8 @@ @finalout @c %**end of header -@set UPDATED 15 July 2013 -@set VERSION 1.15-pre3 +@set UPDATED 1 August 2013 +@set VERSION 1.15-rc1 @dircategory Data Compression @direntry @@ -64,10 +64,6 @@ compresses more than bzip2, which makes it well suited for software distribution and data archiving. Lzip is a clean implementation of the LZMA algorithm. -Lzip uses the same well-defined exit status values used by bzip2, which -makes it safer when used in pipes or scripts than compressors returning -ambiguous warning values, like gzip. - The lzip file format is designed for long-term data archiving and provides very safe integrity checking. The member trailer stores the 32-bit CRC of the original data, the size of the original data and the @@ -84,7 +80,12 @@ recover the original uncompressed data. If you ever need to recover data from a damaged lzip file, try the lziprecover program. Lziprecover makes lzip files resistant to bit-flip (one of the most common forms of data corruption), and provides data -recovery capabilities, including error-checked merging of damaged files. +recovery capabilities, including error-checked merging of damaged copies +of a file. + +Lzip uses the same well-defined exit status values used by bzip2, which +makes it safer when used in pipes or scripts than compressors returning +ambiguous warning values, like gzip. Lzip replaces every file given in the command line with a compressed version of itself, with the name "original_name.lz". Each compressed @@ -111,7 +112,7 @@ multivolume compressed tar archives. Lzip is able to compress and decompress streams of unlimited size by automatically creating multi-member output. The members so created are -large (about 2^60 bytes each). +large, about 64 PiB each. The amount of memory required for compression is about 1 or 2 times the dictionary size limit (1 if input file size is less than dictionary size @@ -193,7 +194,7 @@ The ideas embodied in lzip are due to (at least) the following people: Abraham Lempel and Jacob Ziv (for the LZ algorithm), Andrey Markov (for the definition of Markov chains), G.N.N. Martin (for the definition of range encoding), Igor Pavlov (for putting all the above together in -LZMA), and Julian Seward (for bzip2's CLI and the idea of unzcrash). +LZMA), and Julian Seward (for bzip2's CLI). @node Invoking lzip @@ -222,10 +223,9 @@ Print the version number of lzip on the standard output and exit. @item -b @var{bytes} @itemx --member-size=@var{bytes} -Produce a multi-member file and set the member size limit to @var{bytes}. -Minimum member size limit is 100kB. Small member size may degrade -compression ratio, so use it only when needed. The default is to produce -single-member files. +Set the member size limit to @var{bytes}. A small member size may +degrade compression ratio, so use it only when needed. Valid values +range from 100 kB to 64 PiB. Defaults to 64 PiB. @item -c @itemx --stdout @@ -271,8 +271,8 @@ Quiet operation. Suppress all messages. @item -s @var{bytes} @itemx --dictionary-size=@var{bytes} -Set the dictionary size limit in bytes. Valid values range from 4KiB to -512MiB. Lzip will use the smallest possible dictionary size for each +Set the dictionary size limit in bytes. Valid values range from 4 KiB to +512 MiB. Lzip will use the smallest possible dictionary size for each member without exceeding this limit. Note that dictionary sizes are quantized. If the specified size does not match one of the valid sizes, it will be rounded upwards by adding up to (@var{bytes} / 16) to it. @@ -286,8 +286,9 @@ is affected at compression time by the choice of dictionary size limit. Split the compressed output into several volume files with names @samp{original_name00001.lz}, @samp{original_name00002.lz}, etc, and set the volume size limit to @var{bytes}. Each volume is a complete, maybe -multi-member, lzip file. Minimum volume size limit is 100kB. Small volume -size may degrade compression ratio, so use it only when needed. +multi-member, lzip file. A small volume size may degrade compression +ratio, so use it only when needed. Valid values range from 100 kB to 4 +EiB. @item -t @itemx --test @@ -314,7 +315,8 @@ The bidimensional parameter space of LZMA can't be mapped to a linear scale optimal for all files. If your files are large, very repetitive, etc, you may need to use the @samp{--match-length} and @samp{--dictionary-size} options directly to achieve optimal -performance. +performance. For example, @samp{-9m64} usually compresses executables +more (and faster) than @samp{-9}. @multitable {Level} {Dictionary size} {Match length limit} @item Level @tab Dictionary size @tab Match length limit @@ -336,7 +338,6 @@ Aliases for GNU gzip compatibility. @end table -@sp 1 Numbers given as arguments to options may be followed by a multiplier and an optional @samp{B} for "byte". @@ -402,7 +403,8 @@ All multibyte values are stored in little endian order. @table @samp @item ID string -A four byte string, identifying the lzip format, with the value "LZIP". +A four byte string, identifying the lzip format, with the value "LZIP" +(0x4C, 0x5A, 0x49, 0x50). @item VN (version number, 1 byte) Just in case something needs to be modified in the future. 1 for now. @@ -415,12 +417,13 @@ wedges between 0 and 7. The size of a wedge is (base_size / 16).@* Bits 4-0 contain the base 2 logarithm of the base size (12 to 29).@* Bits 7-5 contain the number of wedges (0 to 7) to substract from the base size to obtain the dictionary size.@* -Example: 0xD3 = (2^19 - 6 * 2^15) = (512KiB - 6 * 32KiB) = 320KiB@* -Valid values for dictionary size range from 4KiB to 512MiB. +Example: 0xD3 = 2^19 - 6 * 2^15 = 512 KiB - 6 * 32 KiB = 320 KiB@* +Valid values for dictionary size range from 4 KiB to 512 MiB. @item Lzma stream -The lzma stream, finished by an end of stream marker. Uses default values -for encoder properties. +The lzma stream, finished by an end of stream marker. Uses default +values for encoder properties. See the chapter @samp{Stream format} +(@pxref{Stream format}) for a complete description. @item CRC32 (4 bytes) CRC of the uncompressed original data. @@ -540,9 +543,9 @@ The indices used in these arrays are: @table @samp @item state - -A state machine (@samp{State} in the source) coding the latest 2 to 4 -types of sequences processed. The initial state is 0. +A state machine (@samp{State} in the source) with 12 states (0 to 11), +coding the latest 2 to 4 types of sequences processed. The initial state +is 0. @item pos_state Value of the 2 least significant bits of the current position in the @@ -558,6 +561,28 @@ resulting value is in the range 0 to 3. @end table +In the following table, @samp{!literal} is any sequence except a literal +byte. @samp{rep} is any one of @samp{rep0}, @samp{rep1}, @samp{rep2} or +@samp{rep3}. The types of previous sequences corresponding to each state +are: + +@multitable {State} {literal, shortrep, literal, literal} +@headitem State @tab Types of previous sequences +@item 0 @tab literal, literal, literal +@item 1 @tab match, literal, literal +@item 2 @tab (rep or shortrep), literal, literal +@item 3 @tab literal, shortrep, literal, literal +@item 4 @tab match, literal +@item 5 @tab (rep or shortrep), literal +@item 6 @tab literal, shortrep, literal +@item 7 @tab literal, match +@item 8 @tab literal, rep +@item 9 @tab literal, shortrep +@item 10 @tab !literal, match +@item 11 @tab !literal, (rep or shortrep) +@end multitable + +@sp 1 The contexts for decoding the type of coding sequence are: @multitable @columnfractions .2 .4 .4 @@ -659,7 +684,7 @@ lzip -v file @sp 1 @noindent Example 2: Like example 1 but the created @samp{file.lz} is multi-member -with a member size of 1MiB. The compression ratio is not shown. +with a member size of 1 MiB. The compression ratio is not shown. @example lzip -b 1MiB file @@ -695,7 +720,7 @@ lzip -c /dev/fd0 > file.lz @sp 1 @noindent -Example 6: Decompress @samp{file.lz} partially until 10KiB of +Example 6: Decompress @samp{file.lz} partially until 10 KiB of decompressed data are produced. @example @@ -714,7 +739,7 @@ lzip -cd file.lz | dd bs=1000 skip=10 count=5 @sp 1 @noindent Example 8: Create a multivolume compressed tar archive with a volume -size of 1440KiB. +size of 1440 KiB. @example tar -c some_directory | lzip -S 1440KiB -o volume_name @@ -730,9 +755,9 @@ lzip -cd volume_name*.lz | tar -xf - @sp 1 @noindent -Example 10: Create a multivolume compressed backup of a big database -file with a volume size of 650MB, where each volume is a multi-member -file with a member size of 32MiB. +Example 10: Create a multivolume compressed backup of a large database +file with a volume size of 650 MB, where each volume is a multi-member +file with a member size of 32 MiB. @example lzip -b 32MiB -S 650MB big_db @@ -759,6 +784,22 @@ find by running @w{@samp{lzip --version}}. @cindex reference source code @verbatim +/* Lzd - Educational decompressor for lzip files + Copyright (C) 2013 Antonio Diaz Diaz. + + This program is free software: you have unlimited permission + to copy, distribute and modify it. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. +*/ +/* + Exit status: 0 for a normal exit, 1 for environmental problems + (file not found, invalid flags, I/O errors, etc), 2 to indicate a + corrupt or invalid input file. +*/ + #include <algorithm> #include <cerrno> #include <cstdio> @@ -783,20 +824,20 @@ public: static const int next[states] = { 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5 }; st = next[st]; } - - void set_match() { st = ( ( st < 7 ) ? 7 : 10 ); } - void set_rep() { st = ( ( st < 7 ) ? 8 : 11 ); } - void set_short_rep() { st = ( ( st < 7 ) ? 9 : 11 ); } + void set_match() { st = ( st < 7 ) ? 7 : 10; } + void set_rep() { st = ( st < 7 ) ? 8 : 11; } + void set_short_rep() { st = ( st < 7 ) ? 9 : 11; } }; enum { + min_dictionary_size = 1 << 12, + max_dictionary_size = 1 << 29, literal_context_bits = 3, pos_state_bits = 2, pos_states = 1 << pos_state_bits, pos_state_mask = pos_states - 1, - max_dis_states = 4, dis_slot_bits = 6, start_dis_model = 4, end_dis_model = 14, @@ -811,13 +852,14 @@ enum { len_mid_symbols = 1 << len_mid_bits, len_high_symbols = 1 << len_high_bits, max_len_symbols = len_low_symbols + len_mid_symbols + len_high_symbols, + min_match_len = 2, // must be 2 + max_dis_states = 4, bit_model_move_bits = 5, bit_model_total_bits = 11, bit_model_total = 1 << bit_model_total_bits }; - struct Bit_model { int probability; @@ -834,6 +876,40 @@ struct Len_model }; +class CRC32 + { + uint32_t data[256]; // Table of CRCs of all 8-bit messages. + +public: + CRC32() + { + for( unsigned n = 0; n < 256; ++n ) + { + unsigned c = n; + for( int k = 0; k < 8; ++k ) + { if( c & 1 ) c = 0xEDB88320U ^ ( c >> 1 ); else c >>= 1; } + data[n] = c; + } + } + + void update_buf( uint32_t & crc, const uint8_t * const buffer, + const int size ) const + { + for( int i = 0; i < size; ++i ) + crc = data[(crc^buffer[i])&0xFF] ^ ( crc >> 8 ); + } + }; + +const CRC32 crc32; + + +typedef uint8_t File_header[6]; // 0-3 magic, 4 version, 5 coded_dict_size + +typedef uint8_t File_trailer[20]; + // 0-3 CRC32 of the uncompressed data + // 4-11 size of the uncompressed data + // 12-19 member size including header and trailer + class Range_decoder { uint32_t code; @@ -842,9 +918,11 @@ class Range_decoder public: Range_decoder() : code( 0 ), range( 0xFFFFFFFFU ) { - for( int i = 0; i < 5; ++i ) code = (code << 8) | std::getc( stdin ); + for( int i = 0; i < 5; ++i ) code = (code << 8) | get_byte(); } + uint8_t get_byte() { return std::getc( stdin ); } + int decode( const int num_bits ) { int symbol = 0; @@ -854,7 +932,7 @@ public: symbol <<= 1; if( code >= range ) { code -= range; symbol |= 1; } if( range <= 0x00FFFFFFU ) // normalize - { range <<= 8; code = (code << 8) | std::getc( stdin ); } + { range <<= 8; code = (code << 8) | get_byte(); } } return symbol; } @@ -877,7 +955,7 @@ public: symbol = 1; } if( range <= 0x00FFFFFFU ) // normalize - { range <<= 8; code = (code << 8) | std::getc( stdin ); } + { range <<= 8; code = (code << 8) | get_byte(); } return symbol; } @@ -923,12 +1001,11 @@ public: int decode_len( Len_model & lm, const int pos_state ) { if( decode_bit( lm.choice1 ) == 0 ) - return min_match_len + - decode_tree( lm.bm_low[pos_state], len_low_bits ); + return decode_tree( lm.bm_low[pos_state], len_low_bits ); if( decode_bit( lm.choice2 ) == 0 ) - return min_match_len + len_low_symbols + + return len_low_symbols + decode_tree( lm.bm_mid[pos_state], len_mid_bits ); - return min_match_len + len_low_symbols + len_mid_symbols + + return len_low_symbols + len_mid_symbols + decode_tree( lm.bm_high, len_high_bits ); } }; @@ -948,8 +1025,8 @@ class LZ_decoder uint8_t get_byte( const unsigned distance ) const { - int i = pos - distance - 1; - if( i < 0 ) i += dictionary_size; + unsigned i = pos - distance - 1; + if( pos <= distance ) i += dictionary_size; return buffer[i]; } @@ -979,38 +1056,12 @@ public: }; -class CRC32 - { - uint32_t data[256]; // Table of CRCs of all 8-bit messages. - -public: - CRC32() - { - for( unsigned n = 0; n < 256; ++n ) - { - unsigned c = n; - for( int k = 0; k < 8; ++k ) - { if( c & 1 ) c = 0xEDB88320U ^ ( c >> 1 ); else c >>= 1; } - data[n] = c; - } - } - - void update( uint32_t & crc, const uint8_t * buffer, const int size ) const - { - for( int i = 0; i < size; ++i ) - crc = data[(crc^buffer[i])&0xFF] ^ ( crc >> 8 ); - } - }; - -const CRC32 crc32; - - void LZ_decoder::flush_data() { if( pos > stream_pos ) { const unsigned size = pos - stream_pos; - crc32.update( crc_, buffer + stream_pos, size ); + crc32.update_buf( crc_, buffer + stream_pos, size ); errno = 0; if( std::fwrite( buffer + stream_pos, 1, size, stdout ) != size ) { std::fprintf( stderr, "Write error: %s\n", std::strerror( errno ) ); @@ -1060,12 +1111,7 @@ bool LZ_decoder::decode_member() // Returns false if error int len; if( rdec.decode_bit( bm_rep[state()] ) == 1 ) // 2nd bit { - if( rdec.decode_bit( bm_rep0[state()] ) == 0 ) // 3rd bit - { - if( rdec.decode_bit( bm_len[state()][pos_state] ) == 0 ) // 4th bit - { state.set_short_rep(); put_byte( get_byte( rep0 ) ); continue; } - } - else + if( rdec.decode_bit( bm_rep0[state()] ) == 1 ) // 3rd bit { unsigned distance; if( rdec.decode_bit( bm_rep1[state()] ) == 0 ) // 4th bit @@ -1081,13 +1127,18 @@ bool LZ_decoder::decode_member() // Returns false if error rep1 = rep0; rep0 = distance; } - len = rdec.decode_len( rep_len_model, pos_state ); + else + { + if( rdec.decode_bit( bm_len[state()][pos_state] ) == 0 ) // 4th bit + { state.set_short_rep(); put_byte( get_byte( rep0 ) ); continue; } + } + len = min_match_len + rdec.decode_len( rep_len_model, pos_state ); state.set_rep(); } else { rep3 = rep2; rep2 = rep1; rep1 = rep0; - len = rdec.decode_len( match_len_model, pos_state ); + len = min_match_len + rdec.decode_len( match_len_model, pos_state ); const int dis_state = std::min( len - min_match_len, max_dis_states - 1 ); const int dis_slot = rdec.decode_tree( bm_dis_slot[dis_state], dis_slot_bits ); @@ -1122,46 +1173,25 @@ bool LZ_decoder::decode_member() // Returns false if error } -enum { min_dictionary_size = 1 << 12, - max_dictionary_size = 1 << 29 }; - -typedef uint8_t File_header[6]; // 0-3 magic, 4 version, 5 coded_dict_size - -typedef uint8_t File_trailer[20]; - // 0-3 CRC32 of the uncompressed data - // 4-11 size of the uncompressed data - // 12-19 member size including header and trailer - - -/* Exit status: 0 for a normal exit, 1 for environmental problems - (file not found, invalid flags, I/O errors, etc), 2 to indicate a - corrupt or invalid input file. */ - int main( const int argc, const char * const argv[] ) { if( argc > 1 ) { std::printf( "Lzd %s - Educational decompressor for lzip files.\n", PROGVERSION ); - std::printf( "Study the source to learn how a simple lzip decompressor works.\n" - "It is not safe to use it for any real work.\n" + std::printf( "Study the source to learn how a lzip decompressor works.\n" + "See the lzip manual for an explanation of the code.\n" + "It is not safe to use lzd for any real work.\n" "\nUsage: %s < file.lz > file\n", argv[0] ); std::printf( "Lzd decompresses from standard input to standard output.\n" "\nCopyright (C) 2013 Antonio Diaz Diaz.\n" "This is free software: you are free to change and redistribute it.\n" "There is NO WARRANTY, to the extent permitted by law.\n" "Report bugs to lzip-bug@nongnu.org\n" - "Lzip home page: http://www.nongnu.org/lzip/lzip.html\n" ); + "Lzd home page: http://www.nongnu.org/lzip/lzd.html\n" ); return 0; } - if( isatty( STDIN_FILENO ) ) - { - std::fprintf( stderr, "I won't read compressed data from a terminal.\n" - "Try '%s --help' for more information.\n", argv[0] ); - return 1; - } - for( bool first_member = true; ; first_member = false ) { File_header header; |