diff options
Diffstat (limited to 'doc/clzip.info')
| -rw-r--r-- | doc/clzip.info | 304 |
1 files changed, 160 insertions, 144 deletions
diff --git a/doc/clzip.info b/doc/clzip.info index 1fddbd8..81b0a3f 100644 --- a/doc/clzip.info +++ b/doc/clzip.info @@ -11,7 +11,7 @@ File: clzip.info, Node: Top, Next: Introduction, Up: (dir) Clzip Manual ************ -This manual is for Clzip (version 1.10, 6 February 2018). +This manual is for Clzip (version 1.11, 3 January 2019). * Menu: @@ -29,7 +29,7 @@ This manual is for Clzip (version 1.10, 6 February 2018). * Concept index:: Index of concepts - Copyright (C) 2010-2018 Antonio Diaz Diaz. + Copyright (C) 2010-2019 Antonio Diaz Diaz. This manual is free documentation: you have unlimited permission to copy, distribute and modify it. @@ -40,14 +40,14 @@ File: clzip.info, Node: Introduction, Next: Output, Prev: Top, Up: Top 1 Introduction ************** -Clzip is a C language version of lzip, fully compatible with lzip-1.4 or -newer. As clzip is written in C, it may be easier to integrate in -applications like package managers, embedded devices, or systems lacking -a C++ compiler. +Clzip is a C language version of lzip, fully compatible with lzip 1.4 +or newer. As clzip is written in C, it may be easier to integrate in +applications like package managers, embedded devices, or systems +lacking a C++ compiler. Lzip is a lossless data compressor with a user interface similar to the one of gzip or bzip2. Lzip can compress about as fast as gzip -(lzip -0), or compress most files more than bzip2 (lzip -9). +(lzip -0) or compress most files more than bzip2 (lzip -9). Decompression speed is intermediate between gzip and bzip2. Lzip is better than gzip and bzip2 from a data recovery perspective. @@ -88,15 +88,15 @@ microscopic. Be aware, though, that the check occurs upon decompression, so it can only tell you that something is wrong. It can't help you recover the original uncompressed data. - Clzip uses the same well-defined exit status values used by lzip and -bzip2, which makes it safer than compressors returning ambiguous warning -values (like gzip) when it is used as a back end for other programs like -tar or zutils. + Clzip uses the same well-defined exit status values used by lzip, +which makes it safer than compressors returning ambiguous warning +values (like gzip) when it is used as a back end for other programs +like tar or zutils. - Clzip will automatically use the smallest possible dictionary size -for each file without exceeding the given limit. Keep in mind that the -decompression memory requirement is affected at compression time by the -choice of dictionary size limit. + Clzip will automatically use for each file the largest dictionary +size that does not exceed neither the file size nor the limit given. +Keep in mind that the decompression memory requirement is affected at +compression time by the choice of dictionary size limit. 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 @@ -116,7 +116,7 @@ anyothername becomes anyothername.out (De)compressing a file is much like copying or moving it; therefore clzip preserves the access and modification dates, permissions, and, -when possible, ownership of the file just as "cp -p" does. (If the user +when possible, ownership of the file just as 'cp -p' does. (If the user ID or the group ID can't be duplicated, the file permission bits S_ISUID and S_ISGID are cleared). @@ -214,6 +214,7 @@ command line. '-V' '--version' Print the version number of clzip on the standard output and exit. + This version number should be included in all bug reports. '-a' '--trailing-error' @@ -298,12 +299,14 @@ command line. '-s BYTES' '--dictionary-size=BYTES' When compressing, set the dictionary size limit in bytes. Clzip - will use the smallest possible dictionary size for each file - without exceeding this limit. Valid values range from 4 KiB to - 512 MiB. Values 12 to 29 are interpreted as powers of two, meaning - 2^12 to 2^29 bytes. 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 (BYTES / 8) to it. + will use for each file the largest dictionary size that does not + exceed neither the file size nor this limit. Valid values range + from 4 KiB to 512 MiB. Values 12 to 29 are interpreted as powers + of two, meaning 2^12 to 2^29 bytes. Dictionary sizes are quantized + so that they can be coded in just one byte (*note + coded-dict-size::). If the specified size does not match one of + the valid sizes, it will be rounded upwards by adding up to + (BYTES / 8) to it. For maximum compression you should use a dictionary size limit as large as possible, but keep in mind that the decompression memory @@ -342,27 +345,32 @@ command line. Two or more '-v' options show the progress of (de)compression. '-0 .. -9' - Set the compression parameters (dictionary size and match length - limit) as shown in the table below. The default compression level - is '-6'. Note that '-9' can be much slower than '-0'. These - options have no effect when decompressing, testing or listing. + Compression level. Set the compression parameters (dictionary size + and match length limit) as shown in the table below. The default + compression level is '-6', equivalent to '-s8MiB -m36'. Note that + '-9' can be much slower than '-0'. These options have no effect + when decompressing, testing or listing. 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 '--dictionary-size' and '--match-length' options directly to achieve optimal performance. - Level Dictionary size Match length limit - -0 64 KiB 16 bytes - -1 1 MiB 5 bytes - -2 1.5 MiB 6 bytes - -3 2 MiB 8 bytes - -4 3 MiB 12 bytes - -5 4 MiB 20 bytes - -6 8 MiB 36 bytes - -7 16 MiB 68 bytes - -8 24 MiB 132 bytes - -9 32 MiB 273 bytes + If several compression levels or '-s' or '-m' options are given, + the last setting is used. For example '-9 -s64MiB' is equivalent + to '-s64MiB -m273' + + Level Dictionary size (-s) Match length limit (-m) + -0 64 KiB 16 bytes + -1 1 MiB 5 bytes + -2 1.5 MiB 6 bytes + -3 2 MiB 8 bytes + -4 3 MiB 12 bytes + -5 4 MiB 20 bytes + -6 8 MiB 36 bytes + -7 16 MiB 68 bytes + -8 24 MiB 132 bytes + -9 32 MiB 273 bytes '--fast' '--best' @@ -409,10 +417,10 @@ is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult. -- C.A.R. Hoare - Lzip has been designed, written and tested with great care to be the -standard general-purpose compressor for unix-like systems. This chapter -describes the lessons learned from previous compressors (gzip and -bzip2), and their application to the design of lzip. + Lzip has been designed, written and tested with great care to replace +gzip and bzip2 as the standard general-purpose compressed format for +unix-like systems. This chapter describes the lessons learned from +these previous formats, and their application to the design of lzip. 4.1 Format design @@ -455,17 +463,20 @@ error detection. Any distance larger than the dictionary size acts as a forbidden symbol, allowing the decompressor to detect the approximate position of errors, and leaving very little work for the check sequence (CRC and data sizes) in the detection of errors. Lzip is usually able -to detect all posible bit flips in the compressed data without +to detect all possible bit flips in the compressed data without resorting to the check sequence. It would be difficult to write an automatic recovery tool like lziprecover for the gzip format. And, as far as I know, it has never been written. Lzip, like gzip and bzip2, uses a CRC32 to check the integrity of the -decompressed data because it provides more accurate error detection than -CRC64 up to a compressed size of about 16 GiB, a size larger than that -of most files. In the case of lzip, the additional detection capability -of the decompressor reduces the probability of undetected errors more -than a million times beyond what the CRC32 alone provides. +decompressed data because it provides optimal accuracy in the detection +of errors up to a compressed size of about 16 GiB, a size larger than +that of most files. In the case of lzip, the additional detection +capability of the decompressor reduces the probability of undetected +errors about four million times more, resulting in a combined integrity +checking optimally accurate for any member size produced by lzip. +Preliminary results suggest that the lzip format is safe enough to be +used in critical safety avionics systems. The lzip format is designed for long-term archiving. Therefore it excludes any unneeded features that may interfere with the future @@ -520,7 +531,7 @@ extraction of the decompressed data. Bzip2 does not store the uncompressed size of the file. The lzip format provides a 64-bit field for the uncompressed size. - Additionaly, lzip produces multimember output automatically when + Additionally, lzip produces multimember output automatically when the size is too large for a single member, allowing for an unlimited uncompressed size. @@ -568,9 +579,9 @@ extraction of the decompressed data. (lziprecover)Unzcrash. 'Dictionary size' - Lzip automatically uses the smallest possible dictionary size for - each file. In addition to reducing the amount of memory required - for decompression, this feature also minimizes the probability of + Lzip automatically adapts the dictionary size to the size of each + file. In addition to reducing the amount of memory required for + decompression, this feature also minimizes the probability of being affected by RAM errors during compression. 'Exit status' @@ -624,11 +635,11 @@ additional information before, between, or after them. 'DS (coded dictionary size, 1 byte)' The dictionary size is calculated by taking a power of 2 (the base - size) and substracting from it a fraction between 0/16 and 7/16 of + size) and subtracting from it a fraction between 0/16 and 7/16 of the base size. Bits 4-0 contain the base 2 logarithm of the base size (12 to 29). - Bits 7-5 contain the numerator of the fraction (0 to 7) to - substract from the base size to obtain the dictionary size. + Bits 7-5 contain the numerator of the fraction (0 to 7) to subtract + from the base size to obtain the dictionary size. 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. @@ -767,7 +778,7 @@ reusing a recently used distance). There are 7 different coding sequences: Bit sequence Name Description ---------------------------------------------------------------------------- +------------------------------------------------------------------------ 0 + byte literal literal byte 1 + 0 + len + dis match distance-length pair 1 + 1 + 0 + 0 shortrep 1 byte match at latest used distance @@ -787,7 +798,7 @@ order, from MSB to LSB, except where noted otherwise. Lengths (the 'len' in the table above) are coded as follows: Bit sequence Description --------------------------------------------------------------------------- +------------------------------------------------------------------------ 0 + 3 bits lengths from 2 to 9 1 + 0 + 3 bits lengths from 10 to 17 1 + 1 + 8 bits lengths from 18 to 273 @@ -828,7 +839,7 @@ order (from LSB to MSB). For distances >= 128, the 'direct_bits - 4' part is coded with fixed 0.5 probability. Bit sequence Description --------------------------------------------------------------------------- +------------------------------------------------------------------------ slot distances from 0 to 3 slot + direct_bits distances from 4 to 127 slot + (direct_bits - 4) + 4 bits distances from 128 to 2^32 - 1 @@ -864,7 +875,7 @@ 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 (!literal, shortrep), literal, literal @@ -881,24 +892,24 @@ State Types of previous sequences The contexts for decoding the type of coding sequence are: -Name Indices Used when ---------------------------------------------------------------------------- -bm_match state, pos_state sequence start -bm_rep state after sequence 1 -bm_rep0 state after sequence 11 -bm_rep1 state after sequence 111 -bm_rep2 state after sequence 1111 -bm_len state, pos_state after sequence 110 +Name Indices Used when +----------------------------------------------------------------------- +bm_match state, pos_state sequence start +bm_rep state after sequence 1 +bm_rep0 state after sequence 11 +bm_rep1 state after sequence 111 +bm_rep2 state after sequence 1111 +bm_len state, pos_state after sequence 110 The contexts for decoding distances are: -Name Indices Used when ---------------------------------------------------------------------------- -bm_dis_slot len_state, bit tree distance start -bm_dis reverse bit tree after slots 4 to 13 -bm_align reverse bit tree for distances >= 128, after - fixed probability bits +Name Indices Used when +------------------------------------------------------------------------ +bm_dis_slot len_state, bit tree distance start +bm_dis reverse bit tree after slots 4 to 13 +bm_align reverse bit tree for distances >= 128, after fixed + probability bits There are two separate sets of contexts for lengths ('Len_model' in @@ -906,7 +917,7 @@ the source). One for normal matches, the other for repeated matches. The contexts in each Len_model are (see 'decode_len' in the source): Name Indices Used when ---------------------------------------------------------------------------- +------------------------------------------------------------------------ choice1 none length start choice2 none after sequence 1 bm_low pos_state, bit tree after sequence 0 @@ -1013,7 +1024,11 @@ compressed file (bugs in the system libraries, memory errors, etc). Therefore, if the data you are going to compress are important, give the '--keep' option to clzip and don't remove the original file until you verify the compressed file with a command like -'clzip -cd file.lz | cmp file -'. +'clzip -cd file.lz | cmp file -'. Most RAM errors happening during +compression can only be detected by comparing the compressed file with +the original because the corruption happens before clzip compresses the +RAM contents, resulting in a valid compressed file containing wrong +data. Example 1: Replace a regular file with its compressed version 'file.lz' @@ -1106,7 +1121,7 @@ Appendix A Reference source code ******************************** /* Lzd - Educational decompressor for the lzip format - Copyright (C) 2013-2018 Antonio Diaz Diaz. + Copyright (C) 2013-2019 Antonio Diaz Diaz. This program is free software. Redistribution and use in source and binary forms, with or without modification, are permitted provided @@ -1136,7 +1151,7 @@ Appendix A Reference source code #include <cstring> #include <stdint.h> #include <unistd.h> -#if defined(__MSVCRT__) || defined(__OS2__) || defined(_MSC_VER) +#if defined(__MSVCRT__) || defined(__OS2__) || defined(__DJGPP__) #include <fcntl.h> #include <io.h> #endif @@ -1237,9 +1252,9 @@ public: const CRC32 crc32; -typedef uint8_t File_header[6]; // 0-3 magic, 4 version, 5 coded_dict_size +typedef uint8_t Lzip_header[6]; // 0-3 magic, 4 version, 5 coded_dict_size -typedef uint8_t File_trailer[20]; +typedef uint8_t Lzip_trailer[20]; // 0-3 CRC32 of the uncompressed data // 4-11 size of the uncompressed data // 12-19 member size including header and trailer @@ -1433,6 +1448,7 @@ bool LZ_decoder::decode_member() // Returns false if error const int pos_state = data_position() & pos_state_mask; if( rdec.decode_bit( bm_match[state()][pos_state] ) == 0 ) // 1st bit { + // literal byte const uint8_t prev_byte = peek( 0 ); const int literal_state = prev_byte >> ( 8 - literal_context_bits ); Bit_model * const bm = bm_literal[literal_state]; @@ -1441,67 +1457,66 @@ bool LZ_decoder::decode_member() // Returns false if error else put_byte( rdec.decode_matched( bm, peek( rep0 ) ) ); state.set_char(); + continue; } - else // match or repeated match + // match or repeated match + int len; + if( rdec.decode_bit( bm_rep[state()] ) != 0 ) // 2nd bit { - int len; - if( rdec.decode_bit( bm_rep[state()] ) != 0 ) // 2nd bit + if( rdec.decode_bit( bm_rep0[state()] ) == 0 ) // 3rd 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( peek( rep0 ) ); continue; } - } + if( rdec.decode_bit( bm_len[state()][pos_state] ) == 0 ) // 4th bit + { state.set_short_rep(); put_byte( peek( rep0 ) ); continue; } + } + else + { + unsigned distance; + if( rdec.decode_bit( bm_rep1[state()] ) == 0 ) // 4th bit + distance = rep1; else { - unsigned distance; - if( rdec.decode_bit( bm_rep1[state()] ) == 0 ) // 4th bit - distance = rep1; + if( rdec.decode_bit( bm_rep2[state()] ) == 0 ) // 5th bit + distance = rep2; else - { - if( rdec.decode_bit( bm_rep2[state()] ) == 0 ) // 5th bit - distance = rep2; - else - { distance = rep3; rep3 = rep2; } - rep2 = rep1; - } - rep1 = rep0; - rep0 = distance; + { distance = rep3; rep3 = rep2; } + rep2 = rep1; } - state.set_rep(); - len = min_match_len + rdec.decode_len( rep_len_model, pos_state ); + rep1 = rep0; + rep0 = distance; } - else // match + state.set_rep(); + len = min_match_len + rdec.decode_len( rep_len_model, pos_state ); + } + else // match + { + rep3 = rep2; rep2 = rep1; rep1 = rep0; + len = min_match_len + rdec.decode_len( match_len_model, pos_state ); + const int len_state = std::min( len - min_match_len, len_states - 1 ); + rep0 = rdec.decode_tree( bm_dis_slot[len_state], dis_slot_bits ); + if( rep0 >= start_dis_model ) { - rep3 = rep2; rep2 = rep1; rep1 = rep0; - len = min_match_len + rdec.decode_len( match_len_model, pos_state ); - const int len_state = std::min( len - min_match_len, len_states - 1 ); - rep0 = rdec.decode_tree( bm_dis_slot[len_state], dis_slot_bits ); - if( rep0 >= start_dis_model ) + const unsigned dis_slot = rep0; + const int direct_bits = ( dis_slot >> 1 ) - 1; + rep0 = ( 2 | ( dis_slot & 1 ) ) << direct_bits; + if( dis_slot < end_dis_model ) + rep0 += rdec.decode_tree_reversed( bm_dis + ( rep0 - dis_slot ), + direct_bits ); + else { - const unsigned dis_slot = rep0; - const int direct_bits = ( dis_slot >> 1 ) - 1; - rep0 = ( 2 | ( dis_slot & 1 ) ) << direct_bits; - if( dis_slot < end_dis_model ) - rep0 += rdec.decode_tree_reversed( bm_dis + ( rep0 - dis_slot ), - direct_bits ); - else + rep0 += rdec.decode( direct_bits - dis_align_bits ) << dis_align_bits; + rep0 += rdec.decode_tree_reversed( bm_align, dis_align_bits ); + if( rep0 == 0xFFFFFFFFU ) // marker found { - rep0 += rdec.decode( direct_bits - dis_align_bits ) << dis_align_bits; - rep0 += rdec.decode_tree_reversed( bm_align, dis_align_bits ); - if( rep0 == 0xFFFFFFFFU ) // marker found - { - flush_data(); - return ( len == min_match_len ); // End Of Stream marker - } + flush_data(); + return ( len == min_match_len ); // End Of Stream marker } } - state.set_match(); - if( rep0 >= dictionary_size || ( rep0 >= pos && !pos_wrapped ) ) - { flush_data(); return false; } } - for( int i = 0; i < len; ++i ) put_byte( peek( rep0 ) ); + state.set_match(); + if( rep0 >= dictionary_size || ( rep0 >= pos && !pos_wrapped ) ) + { flush_data(); return false; } } + for( int i = 0; i < len; ++i ) put_byte( peek( rep0 ) ); } flush_data(); return false; @@ -1519,7 +1534,7 @@ int main( const int argc, const char * const argv[] ) "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) 2018 Antonio Diaz Diaz.\n" + "\nCopyright (C) 2019 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" @@ -1527,14 +1542,14 @@ int main( const int argc, const char * const argv[] ) return 0; } -#if defined(__MSVCRT__) || defined(__OS2__) || defined(_MSC_VER) - setmode( fileno( stdin ), O_BINARY ); - setmode( fileno( stdout ), O_BINARY ); +#if defined(__MSVCRT__) || defined(__OS2__) || defined(__DJGPP__) + setmode( STDIN_FILENO, O_BINARY ); + setmode( STDOUT_FILENO, O_BINARY ); #endif for( bool first_member = true; ; first_member = false ) { - File_header header; // verify header + Lzip_header header; // verify header for( int i = 0; i < 6; ++i ) header[i] = std::getc( stdin ); if( std::feof( stdin ) || std::memcmp( header, "LZIP\x01", 5 ) != 0 ) { @@ -1553,7 +1568,7 @@ int main( const int argc, const char * const argv[] ) if( !decoder.decode_member() ) { std::fputs( "Data error\n", stderr ); return 2; } - File_trailer trailer; // verify trailer + Lzip_trailer trailer; // verify trailer for( int i = 0; i < 20; ++i ) trailer[i] = std::getc( stdin ); unsigned crc = 0; for( int i = 3; i >= 0; --i ) { crc <<= 8; crc += trailer[i]; } @@ -1598,20 +1613,21 @@ Concept index Tag Table: Node: Top210 -Node: Introduction1210 -Node: Output6491 -Node: Invoking clzip8011 -Ref: --trailing-error8577 -Node: Quality assurance16230 -Node: File format24640 -Node: Algorithm27045 -Node: Stream format29875 -Node: Trailing data40616 -Node: Examples42894 -Ref: concat-example44076 -Node: Problems45121 -Node: Reference source code45657 -Node: Concept index59974 +Node: Introduction1209 +Node: Output6498 +Node: Invoking clzip8018 +Ref: --trailing-error8648 +Node: Quality assurance16666 +Node: File format25271 +Ref: coded-dict-size26564 +Node: Algorithm27674 +Node: Stream format30504 +Node: Trailing data41156 +Node: Examples43434 +Ref: concat-example44866 +Node: Problems45911 +Node: Reference source code46447 +Node: Concept index60660 End Tag Table |