diff options
| -rw-r--r-- | ChangeLog | 8 | ||||
| -rw-r--r-- | INSTALL | 12 | ||||
| -rw-r--r-- | Makefile.in | 8 | ||||
| -rw-r--r-- | NEWS | 8 | ||||
| -rw-r--r-- | README | 81 | ||||
| -rw-r--r-- | arg_parser.cc | 7 | ||||
| -rw-r--r-- | arg_parser.h | 2 | ||||
| -rwxr-xr-x | configure | 2 | ||||
| -rw-r--r-- | decoder.cc | 7 | ||||
| -rw-r--r-- | doc/lzip.1 | 10 | ||||
| -rw-r--r-- | doc/lzip.info | 124 | ||||
| -rw-r--r-- | doc/lzip.texi | 111 | ||||
| -rw-r--r-- | encoder.cc | 100 | ||||
| -rw-r--r-- | encoder.h | 123 | ||||
| -rw-r--r-- | fast_encoder.cc | 2 | ||||
| -rw-r--r-- | fast_encoder.h | 2 | ||||
| -rw-r--r-- | main.cc | 47 | ||||
| -rwxr-xr-x | testsuite/check.sh | 82 |
18 files changed, 403 insertions, 333 deletions
@@ -1,3 +1,9 @@ +2014-05-16 Antonio Diaz Diaz <antonio@gnu.org> + + * Version 1.16-pre2 released. + * Compression ratio of option '-9' has been slightly increased. + * Compression time of option '-0' has been reduced by 2%. + 2014-01-11 Antonio Diaz Diaz <antonio@gnu.org> * Version 1.16-pre1 released. @@ -74,7 +80,7 @@ reduced to extend range of use towards gzip. Lower numbers now compress less but faster. (-1 now takes 43% less time for only 20% larger compressed size). - * encoder.cc: Compression of option -9 has been slightly increased. + * Compression ratio of option '-9' has been slightly increased. * lziprecover.cc: Added new option '-m, --merge' which tries to produce a correct file merging the good parts of two or more damaged copies. @@ -39,12 +39,12 @@ the main archive. Another way ----------- -You can also compile lzip into a separate directory. To do this, you -must use a version of 'make' that supports the 'VPATH' variable, such -as GNU 'make'. 'cd' to the directory where you want the object files -and executables to go and run the 'configure' script. 'configure' -automatically checks for the source code in '.', in '..' and in the -directory that 'configure' is in. +You can also compile lzip into a separate directory. +To do this, you must use a version of 'make' that supports the 'VPATH' +variable, such as GNU 'make'. 'cd' to the directory where you want the +object files and executables to go and run the 'configure' script. +'configure' automatically checks for the source code in '.', in '..' and +in the directory that 'configure' is in. 'configure' recognizes the option '--srcdir=DIR' to control where to look for the sources. Usually 'configure' can determine that directory diff --git a/Makefile.in b/Makefile.in index 66aad84..df11a7d 100644 --- a/Makefile.in +++ b/Makefile.in @@ -16,16 +16,16 @@ objs = arg_parser.o encoder.o fast_encoder.o decoder.o main.o all : $(progname) $(progname) : $(objs) - $(CXX) $(LDFLAGS) -o $@ $(objs) + $(CXX) $(CXXFLAGS) $(LDFLAGS) -o $@ $(objs) $(progname)_profiled : $(objs) - $(CXX) $(LDFLAGS) -pg -o $@ $(objs) + $(CXX) $(CXXFLAGS) $(LDFLAGS) -pg -o $@ $(objs) main.o : main.cc - $(CXX) $(CPPFLAGS) $(CXXFLAGS) -DPROGVERSION=\"$(pkgversion)\" -c -o $@ $< + $(CXX) $(CXXFLAGS) $(CPPFLAGS) -DPROGVERSION=\"$(pkgversion)\" -c -o $@ $< %.o : %.cc - $(CXX) $(CPPFLAGS) $(CXXFLAGS) -c -o $@ $< + $(CXX) $(CXXFLAGS) $(CPPFLAGS) -c -o $@ $< $(objs) : Makefile arg_parser.o : arg_parser.h @@ -1,11 +1,15 @@ Changes in version 1.16: +Compression ratio of option -9 has been slightly increased. + +Compression time has been reduced by 4%. + +"lzip -0" is now comparable in compression speed and ratio to "gzip -6". + Copying of file dates, permissions, and ownership now behaves like "cp -p". (If the user ID or the group ID can't be duplicated, the file permission bits S_ISUID and S_ISGID are cleared). -Compression time has been reduced by 4%. - Some minor improvements have been made. "lzip.texinfo" has been renamed to "lzip.texi". @@ -5,43 +5,42 @@ one of gzip or bzip2. Lzip is about as fast as gzip, compresses most files more than bzip2, and is better than both from a data recovery perspective. Lzip is a clean implementation of the LZMA algorithm. -The lzip file format is designed for long-term data archiving and -provides very safe integrity checking. It is as simple as possible (but -not simpler), so that with the only help of the lzip manual it would be -possible for a digital archaeologist to extract the data from a lzip -file long after quantum computers eventually render LZMA obsolete. -Additionally lzip is copylefted, which guarantees that it will remain -free forever. - -The member trailer stores the 32-bit CRC of the original data, the size -of the original data and the size of the member. These values, together -with the value remaining in the range decoder and the end-of-stream -marker, provide a 4 factor integrity checking which guarantees that the -decompressed version of the data is identical to the original. This -guards against corruption of the compressed data, and against undetected -bugs in lzip (hopefully very unlikely). The chances of data corruption -going undetected are 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. - -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 copies -of a file. +The lzip file format is designed for long-term data archiving, taking +into account both data integrity and decoder availability: + + * The lzip format provides very safe integrity checking and some data + recovery means. The lziprecover program can repair bit-flip errors + (one of the most common forms of data corruption) in lzip files, + and provides data recovery capabilities, including error-checked + merging of damaged copies of a file. + + * The lzip format is as simple as possible (but not simpler). The + lzip manual provides the code of a simple decompressor along with a + detailed explanation of how it works, so that with the only help of + the lzip manual it would be possible for a digital archaeologist to + extract the data from a lzip file long after quantum computers + eventually render LZMA obsolete. + + * Additionally lzip is copylefted, which guarantees that it will + remain free forever. Lzip uses the same well-defined exit status values used by bzip2, which makes it safer than compressors returning ambiguous warning values (like gzip) when it is used as a back end for tar or zutils. +Lzip 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. + When compressing, lzip replaces every file given in the command line with a compressed version of itself, with the name "original_name.lz". When decompressing, lzip attempts to guess the name for the decompressed file from that of the compressed file as follows: -filename.lz becomes filename -filename.tlz becomes filename.tar -anyothername becomes anyothername.out +filename.lz becomes filename +filename.tlz becomes filename.tar +anyothername becomes anyothername.out (De)compressing a file is much like copying or moving it; therefore lzip preserves the access and modification dates, permissions, and, when @@ -72,18 +71,22 @@ Lzip is able to compress and decompress streams of unlimited size by automatically creating multi-member output. The members so created are large, about 64 PiB each. -Lzip will automatically use the smallest possible dictionary size -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. - -Lzip implements a simplified version of the LZMA (Lempel-Ziv-Markov -chain-Algorithm) algorithm. The high compression of LZMA comes from -combining two basic, well-proven compression ideas: sliding dictionaries -(LZ77/78) and markov models (the thing used by every compression -algorithm that uses a range encoder or similar order-0 entropy coder as -its last stage) with segregation of contexts according to what the bits -are used for. +There is no such thing as a "LZMA algorithm"; it is more like a "LZMA +coding scheme". For example, the option '-0' of lzip uses the scheme in +almost the simplest way possible; issuing the longest match it can find, +or a literal byte if it can't find a match. Inversely, a much more +elaborated way of finding coding sequences of minimum price than the one +currently used by lzip could be developed, and the resulting sequence +could also be coded using the LZMA coding scheme. + +Lzip currently implements two variants of the LZMA algorithm; fast (used +by option -0) and normal (used by all other compression levels). + +The high compression of LZMA comes from combining two basic, well-proven +compression ideas: sliding dictionaries (LZ77/78) and markov models (the +thing used by every compression algorithm that uses a range encoder or +similar order-0 entropy coder as its last stage) with segregation of +contexts according to what the bits are used for. 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 diff --git a/arg_parser.cc b/arg_parser.cc index 5cb98a9..44e158e 100644 --- a/arg_parser.cc +++ b/arg_parser.cc @@ -1,5 +1,5 @@ /* Arg_parser - POSIX/GNU command line argument parser. (C++ version) - Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 + Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014 Antonio Diaz Diaz. This library is free software: you can redistribute it and/or modify @@ -120,7 +120,7 @@ bool Arg_parser::parse_short_option( const char * const opt, const char * const if( index < 0 ) { - error_ = "invalid option -- "; error_ += c; + error_ = "invalid option -- '"; error_ += c; error_ += '\''; return false; } @@ -135,7 +135,8 @@ bool Arg_parser::parse_short_option( const char * const opt, const char * const { if( !arg || !arg[0] ) { - error_ = "option requires an argument -- "; error_ += c; + error_ = "option requires an argument -- '"; error_ += c; + error_ += '\''; return false; } data.back().argument = arg; ++argind; cind = 0; diff --git a/arg_parser.h b/arg_parser.h index 5248cb1..8d0d5b3 100644 --- a/arg_parser.h +++ b/arg_parser.h @@ -1,5 +1,5 @@ /* Arg_parser - POSIX/GNU command line argument parser. (C++ version) - Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 + Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014 Antonio Diaz Diaz. This library is free software: you can redistribute it and/or modify @@ -7,7 +7,7 @@ # to copy, distribute and modify it. pkgname=lzip -pkgversion=1.16-pre1 +pkgversion=1.16-pre2 progname=lzip srctrigger=doc/${pkgname}.texi @@ -47,7 +47,7 @@ void Pretty_print::operator()( const char * const msg ) const std::fprintf( stderr, " " ); if( !msg ) std::fflush( stderr ); } - if( msg ) std::fprintf( stderr, "%s.\n", msg ); + if( msg ) std::fprintf( stderr, "%s\n", msg ); } } @@ -121,8 +121,7 @@ bool LZ_decoder::verify_trailer( const Pretty_print & pp ) const { File_trailer trailer; const int trailer_size = File_trailer::size( member_version ); - const unsigned long long member_size = - rdec.member_position() + trailer_size; + const unsigned long long member_size = rdec.member_position() + trailer_size; bool error = false; int size = rdec.read_data( trailer.data, trailer_size ); @@ -143,7 +142,7 @@ bool LZ_decoder::verify_trailer( const Pretty_print & pp ) const if( !rdec.code_is_zero() ) { error = true; - pp( "Range decoder final code is not zero" ); + pp( "Range decoder final code is not zero." ); } if( trailer.data_crc() != crc() ) { @@ -1,7 +1,7 @@ .\" DO NOT MODIFY THIS FILE! It was generated by help2man 1.37.1. -.TH LZIP "1" "January 2014" "Lzip 1.16-pre1" "User Commands" +.TH LZIP "1" "May 2014" "lzip 1.16-pre2" "User Commands" .SH NAME -Lzip \- reduces the size of files +lzip \- reduces the size of files .SH SYNOPSIS .B lzip [\fIoptions\fR] [\fIfiles\fR] @@ -89,13 +89,13 @@ This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. .SH "SEE ALSO" The full documentation for -.B Lzip +.B lzip is maintained as a Texinfo manual. If the .B info and -.B Lzip +.B lzip programs are properly installed at your site, the command .IP -.B info Lzip +.B info lzip .PP should give you access to the complete manual. diff --git a/doc/lzip.info b/doc/lzip.info index 609da4f..244d120 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.16-pre1, 11 January 2014). +This manual is for Lzip (version 1.16-pre2, 16 May 2014). * Menu: @@ -41,15 +41,27 @@ File: lzip.info, Node: Introduction, Next: Algorithm, Prev: Top, Up: Top Lzip is a lossless data compressor with a user interface similar to the one of gzip or bzip2. Lzip is about as fast as gzip, compresses most files more than bzip2, and is better than both from a data recovery -perspective. Lzip is a clean implementation of the LZMA algorithm. +perspective. Lzip is a clean implementation of the LZMA +(Lempel-Ziv-Markov chain-Algorithm) algorithm. - The lzip file format is designed for long-term data archiving and -provides very safe integrity checking. It is as simple as possible (but -not simpler), so that with the only help of the lzip manual it would be -possible for a digital archaeologist to extract the data from a lzip -file long after quantum computers eventually render LZMA obsolete. -Additionally lzip is copylefted, which guarantees that it will remain -free forever. + The lzip file format is designed for long-term data archiving, taking +into account both data integrity and decoder availability: + + * The lzip format provides very safe integrity checking and some data + recovery means. The lziprecover program can repair bit-flip errors + (one of the most common forms of data corruption) in lzip files, + and provides data recovery capabilities, including error-checked + merging of damaged copies of a file. + + * The lzip format is as simple as possible (but not simpler). The + lzip manual provides the code of a simple decompressor along with + a detailed explanation of how it works, so that with the only help + of the lzip manual it would be possible for a digital + archaeologist to extract the data from a lzip file long after + quantum computers eventually render LZMA obsolete. + + * Additionally lzip is copylefted, which guarantees that it will + remain free forever. The member trailer stores the 32-bit CRC of the original data, the size of the original data and the size of the member. These values, @@ -63,16 +75,22 @@ 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. - 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 copies -of a file. - Lzip uses the same well-defined exit status values used by bzip2, which makes it safer than compressors returning ambiguous warning values (like gzip) when it is used as a back end for tar or zutils. + 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 limit, else 2) plus 9 times the dictionary size really used. The +option '-0' is special and only requires about 1.5 MiB at most. The +amount of memory required for decompression is about 46 kB larger than +the dictionary size really used. + + Lzip 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. + When compressing, lzip replaces every file given in the command line with a compressed version of itself, with the name "original_name.lz". When decompressing, lzip attempts to guess the name for the decompressed @@ -111,31 +129,28 @@ multivolume compressed tar archives. automatically creating multi-member output. The members so created are 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 limit, else 2) plus 9 times the dictionary size really used. The -option '-0' is special and only requires about 1.5 MiB at most. The -amount of memory required for decompression is about 46 kB larger than -the dictionary size really used. - - Lzip will automatically use the smallest possible dictionary size -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. - File: lzip.info, Node: Algorithm, Next: Invoking lzip, Prev: Introduction, Up: Top 2 Algorithm *********** -Lzip implements a simplified version of the LZMA (Lempel-Ziv-Markov -chain-Algorithm) algorithm. The high compression of LZMA comes from -combining two basic, well-proven compression ideas: sliding dictionaries -(LZ77/78) and markov models (the thing used by every compression -algorithm that uses a range encoder or similar order-0 entropy coder as -its last stage) with segregation of contexts according to what the bits -are used for. +There is no such thing as a "LZMA algorithm"; it is more like a "LZMA +coding scheme". For example, the option '-0' of lzip uses the scheme in +almost the simplest way possible; issuing the longest match it can find, +or a literal byte if it can't find a match. Inversely, a much more +elaborated way of finding coding sequences of minimum price than the one +currently used by lzip could be developed, and the resulting sequence +could also be coded using the LZMA coding scheme. + + Lzip currently implements two variants of the LZMA algorithm; fast +(used by option -0) and normal (used by all other compression levels). + + The high compression of LZMA comes from combining two basic, +well-proven compression ideas: sliding dictionaries (LZ77/78) and +markov models (the thing used by every compression algorithm that uses +a range encoder or similar order-0 entropy coder as its last stage) +with segregation of contexts according to what the bits are used for. Lzip is a two stage compressor. The first stage is a Lempel-Ziv coder, which reduces redundancy by translating chunks of data to their @@ -143,11 +158,6 @@ corresponding distance-length pairs. The second stage is a range encoder that uses a different probability model for each type of data; distances, lengths, literal bytes, etc. - The match finder, part of the LZ coder, is the most important piece -of the LZMA algorithm, as it is in many Lempel-Ziv based algorithms. -Most of lzip's execution time is spent in the match finder, and it has -the greatest influence on the compression ratio. - Here is how it works, step by step: 1) The member header is written to the output stream. @@ -259,7 +269,7 @@ The format for running lzip is: '--dictionary-size=BYTES' 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 + size for each file 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 (BYTES / 16) to it. @@ -450,7 +460,7 @@ that could be individually described. It seems that the only way of describing the LZMA-302eos stream is describing the algorithm that decodes it. And given the many details about the range decoder that need to be described accurately, the source -code of a real decoder seems the only appropiate reference to use. +code of a real decoder seems the only appropriate reference to use. What follows is a description of the decoding algorithm for LZMA-302eos streams using as reference the source code of "lzd", an @@ -609,7 +619,7 @@ The LZMA stream is consumed one byte at a time by the range decoder. variable number of decoded bits, depending on how well these bits agree with their context. (See 'decode_bit' in the source). - The range decoder state consists of two unsigned 32-bit variables, + The range decoder state consists of two unsigned 32-bit variables; 'range' (representing the most significant part of the range size not yet decoded), and 'code' (representing the current point within 'range'). 'range' is initialized to (2^32 - 1), and 'code' is @@ -627,7 +637,7 @@ source). After decoding the member header and obtaining the dictionary size, the range decoder is initialized and then the LZMA decoder enters a loop (See 'decode_member' in the source) where it invokes the range decoder -with the appropiate contexts to decode the different coding sequences +with the appropriate contexts to decode the different coding sequences (matches, repeated matches, and literal bytes), until the "End Of Stream" marker is decoded. @@ -1005,7 +1015,7 @@ void LZ_decoder::flush_data() 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 ) ); + { std::fprintf( stderr, "Write error: %s.\n", std::strerror( errno ) ); std::exit( 1 ); } if( pos >= dictionary_size ) { partial_data_pos += pos; pos = 0; } stream_pos = pos; @@ -1104,12 +1114,12 @@ bool LZ_decoder::decode_member() // Returns false if error } state.set_match(); if( rep0 >= dictionary_size || rep0 >= data_position() ) - return false; + { flush_data(); return false; } } - for( int i = 0; i < len; ++i ) - put_byte( get_byte( rep0 ) ); + for( int i = 0; i < len; ++i ) put_byte( get_byte( rep0 ) ); } } + flush_data(); return false; } @@ -1171,7 +1181,7 @@ int main( const int argc, const char * const argv[] ) } if( std::fclose( stdout ) != 0 ) - { std::fprintf( stderr, "Can't close stdout: %s\n", std::strerror( errno ) ); + { std::fprintf( stderr, "Can't close stdout: %s.\n", std::strerror( errno ) ); return 1; } return 0; } @@ -1202,15 +1212,15 @@ Concept index Tag Table: Node: Top208 -Node: Introduction1059 -Node: Algorithm5466 -Node: Invoking lzip7960 -Node: File format13638 -Node: Stream format16186 -Node: Examples25616 -Node: Problems27573 -Node: Reference source code28103 -Node: Concept index41592 +Node: Introduction1055 +Node: Algorithm5733 +Node: Invoking lzip8491 +Node: File format14167 +Node: Stream format16715 +Node: Examples26147 +Node: Problems28104 +Node: Reference source code28634 +Node: Concept index42151 End Tag Table diff --git a/doc/lzip.texi b/doc/lzip.texi index 957af34..698526a 100644 --- a/doc/lzip.texi +++ b/doc/lzip.texi @@ -6,8 +6,8 @@ @finalout @c %**end of header -@set UPDATED 11 January 2014 -@set VERSION 1.16-pre1 +@set UPDATED 16 May 2014 +@set VERSION 1.16-pre2 @dircategory Data Compression @direntry @@ -61,15 +61,32 @@ to copy, distribute and modify it. Lzip is a lossless data compressor with a user interface similar to the one of gzip or bzip2. Lzip is about as fast as gzip, compresses most files more than bzip2, and is better than both from a data recovery -perspective. Lzip is a clean implementation of the LZMA algorithm. - -The lzip file format is designed for long-term data archiving and -provides very safe integrity checking. It is as simple as possible (but -not simpler), so that with the only help of the lzip manual it would be -possible for a digital archaeologist to extract the data from a lzip -file long after quantum computers eventually render LZMA obsolete. +perspective. Lzip is a clean implementation of the LZMA +(Lempel-Ziv-Markov chain-Algorithm) algorithm. + +The lzip file format is designed for long-term data archiving, taking +into account both data integrity and decoder availability: + +@itemize @bullet +@item +The lzip format provides very safe integrity checking and some data +recovery means. The lziprecover program can repair bit-flip errors (one +of the most common forms of data corruption) in lzip files, and provides +data recovery capabilities, including error-checked merging of damaged +copies of a file. + +@item +The lzip format is as simple as possible (but not simpler). The lzip +manual provides the code of a simple decompressor along with a detailed +explanation of how it works, so that with the only help of the lzip +manual it would be possible for a digital archaeologist to extract the +data from a lzip file long after quantum computers eventually render +LZMA obsolete. + +@item Additionally lzip is copylefted, which guarantees that it will remain free forever. +@end itemize The member trailer stores the 32-bit CRC of the original data, the size of the original data and the size of the member. These values, together @@ -82,16 +99,22 @@ going undetected are 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. -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 copies -of a file. - Lzip uses the same well-defined exit status values used by bzip2, which makes it safer than compressors returning ambiguous warning values (like gzip) when it is used as a back end for tar or zutils. +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 +limit, else 2) plus 9 times the dictionary size really used. The option +@samp{-0} is special and only requires about 1.5 MiB at most. The amount +of memory required for decompression is about 46 kB larger than the +dictionary size really used. + +Lzip 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. + When compressing, lzip replaces every file given in the command line with a compressed version of itself, with the name "original_name.lz". When decompressing, lzip attempts to guess the name for the decompressed @@ -132,30 +155,27 @@ Lzip is able to compress and decompress streams of unlimited size by automatically creating multi-member output. The members so created are 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 -limit, else 2) plus 9 times the dictionary size really used. The option -@samp{-0} is special and only requires about 1.5 MiB at most. The amount -of memory required for decompression is about 46 kB larger than the -dictionary size really used. - -Lzip will automatically use the smallest possible dictionary size -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. - @node Algorithm @chapter Algorithm @cindex algorithm -Lzip implements a simplified version of the LZMA (Lempel-Ziv-Markov -chain-Algorithm) algorithm. The high compression of LZMA comes from -combining two basic, well-proven compression ideas: sliding dictionaries -(LZ77/78) and markov models (the thing used by every compression -algorithm that uses a range encoder or similar order-0 entropy coder as -its last stage) with segregation of contexts according to what the bits -are used for. +There is no such thing as a "LZMA algorithm"; it is more like a "LZMA +coding scheme". For example, the option '-0' of lzip uses the scheme in +almost the simplest way possible; issuing the longest match it can find, +or a literal byte if it can't find a match. Inversely, a much more +elaborated way of finding coding sequences of minimum price than the one +currently used by lzip could be developed, and the resulting sequence +could also be coded using the LZMA coding scheme. + +Lzip currently implements two variants of the LZMA algorithm; fast (used +by option -0) and normal (used by all other compression levels). + +The high compression of LZMA comes from combining two basic, well-proven +compression ideas: sliding dictionaries (LZ77/78) and markov models (the +thing used by every compression algorithm that uses a range encoder or +similar order-0 entropy coder as its last stage) with segregation of +contexts according to what the bits are used for. Lzip is a two stage compressor. The first stage is a Lempel-Ziv coder, which reduces redundancy by translating chunks of data to their @@ -163,11 +183,6 @@ corresponding distance-length pairs. The second stage is a range encoder that uses a different probability model for each type of data; distances, lengths, literal bytes, etc. -The match finder, part of the LZ coder, is the most important piece of -the LZMA algorithm, as it is in many Lempel-Ziv based algorithms. Most -of lzip's execution time is spent in the match finder, and it has the -greatest influence on the compression ratio. - Here is how it works, step by step: 1) The member header is written to the output stream. @@ -282,7 +297,7 @@ Quiet operation. Suppress all messages. @itemx --dictionary-size=@var{bytes} 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 +file 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. @@ -478,7 +493,7 @@ that could be individually described. It seems that the only way of describing the LZMA-302eos stream is describing the algorithm that decodes it. And given the many details about the range decoder that need to be described accurately, the source -code of a real decoder seems the only appropiate reference to use. +code of a real decoder seems the only appropriate reference to use. What follows is a description of the decoding algorithm for LZMA-302eos streams using as reference the source code of "lzd", an educational @@ -648,7 +663,7 @@ The LZMA stream is consumed one byte at a time by the range decoder. variable number of decoded bits, depending on how well these bits agree with their context. (See @samp{decode_bit} in the source). -The range decoder state consists of two unsigned 32-bit variables, +The range decoder state consists of two unsigned 32-bit variables; @code{range} (representing the most significant part of the range size not yet decoded), and @code{code} (representing the current point within @code{range}). @code{range} is initialized to (2^32 - 1), and @@ -665,7 +680,7 @@ the source). After decoding the member header and obtaining the dictionary size, the range decoder is initialized and then the LZMA decoder enters a loop (See @samp{decode_member} in the source) where it invokes the range -decoder with the appropiate contexts to decode the different coding +decoder with the appropriate contexts to decode the different coding sequences (matches, repeated matches, and literal bytes), until the "End Of Stream" marker is decoded. @@ -1073,7 +1088,7 @@ void LZ_decoder::flush_data() 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 ) ); + { std::fprintf( stderr, "Write error: %s.\n", std::strerror( errno ) ); std::exit( 1 ); } if( pos >= dictionary_size ) { partial_data_pos += pos; pos = 0; } stream_pos = pos; @@ -1172,12 +1187,12 @@ bool LZ_decoder::decode_member() // Returns false if error } state.set_match(); if( rep0 >= dictionary_size || rep0 >= data_position() ) - return false; + { flush_data(); return false; } } - for( int i = 0; i < len; ++i ) - put_byte( get_byte( rep0 ) ); + for( int i = 0; i < len; ++i ) put_byte( get_byte( rep0 ) ); } } + flush_data(); return false; } @@ -1239,7 +1254,7 @@ int main( const int argc, const char * const argv[] ) } if( std::fclose( stdout ) != 0 ) - { std::fprintf( stderr, "Can't close stdout: %s\n", std::strerror( errno ) ); + { std::fprintf( stderr, "Can't close stdout: %s.\n", std::strerror( errno ) ); return 1; } return 0; } @@ -51,7 +51,7 @@ bool Matchfinder_base::read_block() void Matchfinder_base::normalize_pos() { if( pos > stream_pos ) - internal_error( "pos > stream_pos in Matchfinder_base::normalize_pos" ); + internal_error( "pos > stream_pos in Matchfinder_base::normalize_pos." ); if( !at_stream_end ) { const int offset = pos - dictionary_size_ - before_size; @@ -130,7 +130,7 @@ void Matchfinder_base::reset() } -int Matchfinder::get_match_pairs( struct Pair * pairs ) +int Matchfinder::get_match_pairs( Pair * pairs ) { int len_limit = match_len_limit_; if( len_limit > available_bytes() ) @@ -149,7 +149,7 @@ int Matchfinder::get_match_pairs( struct Pair * pairs ) const int key2 = tmp & ( num_prev_positions2 - 1 ); tmp ^= (unsigned)data[2] << 8; const int key3 = num_prev_positions2 + ( tmp & ( num_prev_positions3 - 1 ) ); - const int key4 = num_prev_positions2 + num_prev_positions3 + + const int key4 = num_prev_positions23 + ( ( tmp ^ ( crc32[data[3]] << 5 ) ) & key4_mask ); if( pairs ) @@ -245,33 +245,6 @@ void Range_encoder::flush_data() } -void Len_encoder::encode( Range_encoder & renc, int symbol, - const int pos_state ) - { - symbol -= min_match_len; - if( symbol < len_low_symbols ) - { - renc.encode_bit( choice1, 0 ); - renc.encode_tree3( bm_low[pos_state], symbol ); - } - else - { - renc.encode_bit( choice1, 1 ); - if( symbol < len_low_symbols + len_mid_symbols ) - { - renc.encode_bit( choice2, 0 ); - renc.encode_tree3( bm_mid[pos_state], symbol - len_low_symbols ); - } - else - { - renc.encode_bit( choice2, 1 ); - renc.encode_tree8( bm_high, symbol - len_low_symbols - len_mid_symbols ); - } - } - if( --counters[pos_state] <= 0 ) update_prices( pos_state ); - } - - // End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len) void LZ_encoder_base::full_flush( const unsigned long long data_position, const State state ) @@ -291,15 +264,7 @@ void LZ_encoder_base::full_flush( const unsigned long long data_position, } -void LZ_encoder::fill_align_prices() - { - for( int i = 0; i < dis_align_size; ++i ) - align_prices[i] = price_symbol_reversed( bm_align, i, dis_align_bits ); - align_price_count = dis_align_size; - } - - -void LZ_encoder::fill_distance_prices() +void LZ_encoder::update_distance_prices() { for( int dis = start_dis_model; dis < modeled_distances; ++dis ) { @@ -336,6 +301,7 @@ void LZ_encoder::fill_distance_prices() /* Return value == number of bytes advanced (ahead). trials[0]..trials[ahead-1] contain the steps to encode. ( trials[0].dis == -1 ) means literal. + A match/rep longer or equal than match_len_limit finishes the sequence. */ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], const State state ) @@ -416,7 +382,7 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], if( replens[rep] < min_match_len ) continue; const int price = rep_match_price + price_rep( rep, state, pos_state ); for( int len = min_match_len; len <= replens[rep]; ++len ) - trials[len].update( price + rep_len_encoder.price( len, pos_state ), + trials[len].update( price + rep_len_prices.price( len, pos_state ), rep, 0 ); } @@ -435,10 +401,9 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], } int cur = 0; - matchfinder.move_pos(); - while( true ) // price optimization loop { + matchfinder.move_pos(); if( ++cur >= num_trials ) // no more initialized trials { backward( cur ); @@ -499,7 +464,6 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], const uint8_t prev_byte = matchfinder[1]; const uint8_t cur_byte = matchfinder[0]; const uint8_t match_byte = matchfinder[cur_trial.reps[0]+1]; - matchfinder.move_pos(); int next_price = cur_trial.price + price0( bm_match[cur_state()][pos_state] ); @@ -529,7 +493,7 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], } } - const int available_bytes = std::min( matchfinder.available_bytes() + 1, + const int available_bytes = std::min( matchfinder.available_bytes(), max_num_trials - 1 - cur ); if( available_bytes < min_match_len ) continue; @@ -539,7 +503,7 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], // try literal + rep0 if( match_byte != cur_byte && next_trial.prev_index != cur ) { - const uint8_t * const data = matchfinder.ptr_to_current_pos() - 1; + const uint8_t * const data = matchfinder.ptr_to_current_pos(); const int dis = cur_trial.reps[0] + 1; const int limit = std::min( matchfinder.match_len_limit() + 1, available_bytes ); @@ -564,7 +528,7 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], // try rep distances for( int rep = 0; rep < num_rep_distances; ++rep ) { - const uint8_t * const data = matchfinder.ptr_to_current_pos() - 1; + const uint8_t * const data = matchfinder.ptr_to_current_pos(); int len; const int dis = cur_trial.reps[rep] + 1; @@ -575,7 +539,7 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], trials[++num_trials].price = infinite_price; int price = rep_match_price + price_rep( rep, cur_state, pos_state ); for( int i = min_match_len; i <= len; ++i ) - trials[cur+i].update( price + rep_len_encoder.price( i, pos_state ), + trials[cur+i].update( price + rep_len_prices.price( i, pos_state ), rep, cur ); if( rep == 0 ) start_len = len + 1; // discard shorter matches @@ -590,7 +554,7 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], int pos_state2 = ( pos_state + len ) & pos_state_mask; State state2 = cur_state; state2.set_rep(); - price += rep_len_encoder.price( len, pos_state ) + + price += rep_len_prices.price( len, pos_state ) + price0( bm_match[state2()][pos_state2] ) + price_matched( data[len-1], data[len], data[len-dis] ); pos_state2 = ( pos_state2 + 1 ) & pos_state_mask; @@ -624,7 +588,7 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], // try match + literal + rep0 if( len == pairs[i].len ) { - const uint8_t * const data = matchfinder.ptr_to_current_pos() - 1; + const uint8_t * const data = matchfinder.ptr_to_current_pos(); const int dis2 = dis + 1; int len2 = len + 1; const int limit = std::min( matchfinder.match_len_limit() + len2, @@ -661,17 +625,22 @@ bool LZ_encoder::encode_member( const unsigned long long member_size ) { const unsigned long long member_size_limit = member_size - File_trailer::size() - max_marker_size; - const int fill_count = ( matchfinder.match_len_limit() > 12 ) ? 128 : 512; - int fill_counter = 0; + const bool best = ( matchfinder.match_len_limit() > 12 ); + const int dis_price_count = best ? 1 : 512; + const int align_price_count = best ? 1 : dis_align_size; + const int price_count = ( matchfinder.match_len_limit() > 36 ) ? 1013 : 4093; + int price_counter = 0; + int dis_price_counter = 0; + int align_price_counter = 0; int reps[num_rep_distances]; State state; for( int i = 0; i < num_rep_distances; ++i ) reps[i] = 0; if( matchfinder.data_position() != 0 || renc.member_position() != File_header::size ) - return false; // can be called only once + return false; // can be called only once - if( !matchfinder.finished() ) // encode first byte + if( !matchfinder.finished() ) // encode first byte { const uint8_t prev_byte = 0; const uint8_t cur_byte = matchfinder[0]; @@ -684,15 +653,24 @@ bool LZ_encoder::encode_member( const unsigned long long member_size ) while( !matchfinder.finished() ) { - if( pending_num_pairs == 0 ) + if( price_counter <= 0 && pending_num_pairs == 0 ) { - if( fill_counter <= 0 ) - { fill_distance_prices(); fill_counter = fill_count; } - if( align_price_count <= 0 ) fill_align_prices(); + price_counter = price_count; // recalculate prices every these bytes + if( dis_price_counter <= 0 ) + { dis_price_counter = dis_price_count; update_distance_prices(); } + if( align_price_counter <= 0 ) + { + align_price_counter = align_price_count; + for( int i = 0; i < dis_align_size; ++i ) + align_prices[i] = price_symbol_reversed( bm_align, i, dis_align_bits ); + } + match_len_prices.update_prices(); + rep_len_prices.update_prices(); } int ahead = sequence_optimizer( reps, state ); if( ahead <= 0 ) return false; // can't happen + price_counter -= ahead; for( int i = 0; ahead > 0; ) { @@ -738,7 +716,8 @@ bool LZ_encoder::encode_member( const unsigned long long member_size ) if( len == 1 ) state.set_short_rep(); else { - rep_len_encoder.encode( renc, len, pos_state ); + renc.encode_len( rep_len_model, len, pos_state ); + rep_len_prices.decrement_counter( pos_state ); state.set_rep(); } } @@ -746,8 +725,9 @@ bool LZ_encoder::encode_member( const unsigned long long member_size ) { encode_pair( dis - num_rep_distances, len, pos_state ); if( get_slot( dis - num_rep_distances ) >= end_dis_model ) - --align_price_count; - --fill_counter; + --align_price_counter; + --dis_price_counter; + match_len_prices.decrement_counter( pos_state ); state.set_match(); } } @@ -16,7 +16,7 @@ along with this program. If not, see <http://www.gnu.org/licenses/>. */ -enum { max_num_trials = 1 << 12, +enum { max_num_trials = 1 << 13, price_shift_bits = 6, price_step_bits = 2, price_step = 1 << price_step_bits }; @@ -59,19 +59,18 @@ class Prob_prices public: void init() { - for( int i = price_step / 2; i < bit_model_total; i += price_step ) + for( int i = 0; i < bit_model_total >> price_step_bits; ++i ) { - unsigned val = i; - int bits = 0; // base 2 logarithm of val + unsigned val = ( i * price_step ) + ( price_step / 2 ); + int bits = 0; // base 2 logarithm of val for( int j = 0; j < price_shift_bits; ++j ) { val = val * val; bits <<= 1; while( val >= 1 << 16 ) { val >>= 1; ++bits; } } - bits += 15; // remaining bits in val - data[i >> price_step_bits] = - ( bit_model_total_bits << price_shift_bits ) - bits; + bits += 15; // remaining bits in val + data[i] = ( bit_model_total_bits << price_shift_bits ) - bits; } } @@ -268,7 +267,7 @@ public: } int match_len_limit() const { return match_len_limit_; } - int get_match_pairs( struct Pair * pairs = 0 ); + int get_match_pairs( Pair * pairs = 0 ); }; @@ -419,42 +418,80 @@ public: } while( symbol < 0x10000 ); } + + void encode_len( Len_model & lm, int symbol, const int pos_state ) + { + symbol -= min_match_len; + bool bit = ( symbol >= len_low_symbols ); + encode_bit( lm.choice1, bit ); + if( !bit ) + encode_tree3( lm.bm_low[pos_state], symbol ); + else + { + bit = ( symbol >= len_low_symbols + len_mid_symbols ); + encode_bit( lm.choice2, bit ); + if( !bit ) + encode_tree3( lm.bm_mid[pos_state], symbol - len_low_symbols ); + else + encode_tree8( lm.bm_high, symbol - len_low_symbols - len_mid_symbols ); + } + } }; -class Len_encoder : public Len_model +class Len_prices { - int prices[pos_states][max_len_symbols]; + const Len_model & lm; const int len_symbols; + const int count; + int prices[pos_states][max_len_symbols]; int counters[pos_states]; - void update_prices( const int pos_state ) + void update_low_mid_prices( const int pos_state ) { + counters[pos_state] = count; int * const pps = prices[pos_state]; - int tmp = price0( choice1 ); + int tmp = price0( lm.choice1 ); int len = 0; for( ; len < len_low_symbols && len < len_symbols; ++len ) - pps[len] = tmp + price_symbol3( bm_low[pos_state], len ); - tmp = price1( choice1 ); + pps[len] = tmp + price_symbol3( lm.bm_low[pos_state], len ); + if( len >= len_symbols ) return; + tmp = price1( lm.choice1 ) + price0( lm.choice2 ); for( ; len < len_low_symbols + len_mid_symbols && len < len_symbols; ++len ) - pps[len] = tmp + price0( choice2 ) + - price_symbol3( bm_mid[pos_state], len - len_low_symbols ); - for( ; len < len_symbols; ++len ) + pps[len] = tmp + + price_symbol3( lm.bm_mid[pos_state], len - len_low_symbols ); + } + + void update_high_prices() + { + const int tmp = price1( lm.choice1 ) + price1( lm.choice2 ); + for( int len = len_low_symbols + len_mid_symbols; len < len_symbols; ++len ) // using 4 slots per value makes "price" faster - prices[3][len] = prices[2][len] = prices[1][len] = prices[0][len] = - tmp + price1( choice2 ) + - price_symbol8( bm_high, len - len_low_symbols - len_mid_symbols ); - counters[pos_state] = len_symbols; + prices[3][len] = prices[2][len] = prices[1][len] = prices[0][len] = tmp + + price_symbol8( lm.bm_high, len - len_low_symbols - len_mid_symbols ); } public: - explicit Len_encoder( const int match_len_limit ) - : len_symbols( match_len_limit + 1 - min_match_len ) + Len_prices( const Len_model & m, const int match_len_limit ) + : + lm( m ), + len_symbols( match_len_limit + 1 - min_match_len ), + count( ( match_len_limit > 12 ) ? 1 : len_symbols ) { - for( int i = 0; i < pos_states; ++i ) update_prices( i ); + for( int i = 0; i < pos_states; ++i ) counters[i] = 0; } - void encode( Range_encoder & renc, int symbol, const int pos_state ); + void decrement_counter( const int pos_state ) { --counters[pos_state]; } + + void update_prices() + { + bool high_pending = false; + for( int pos_state = 0; pos_state < pos_states; ++pos_state ) + if( counters[pos_state] <= 0 ) + { update_low_mid_prices( pos_state ); high_pending = true; } + if( high_pending && len_symbols > len_low_symbols + len_mid_symbols ) + update_high_prices(); + } int price( const int symbol, const int pos_state ) const { return prices[pos_state][symbol - min_match_len]; } @@ -481,18 +518,15 @@ protected: Bit_model bm_align[dis_align_size]; Range_encoder renc; - Len_encoder match_len_encoder; - Len_encoder rep_len_encoder; + Len_model match_len_model; + Len_model rep_len_model; unsigned crc() const { return crc_ ^ 0xFFFFFFFFU; } - LZ_encoder_base( const File_header & header, const int match_len_limit, - const int outfd ) + LZ_encoder_base( const File_header & header, const int outfd ) : crc_( 0xFFFFFFFFU ), - renc( outfd ), - match_len_encoder( match_len_limit ), - rep_len_encoder( match_len_limit ) + renc( outfd ) { for( int i = 0; i < File_header::size; ++i ) renc.put_byte( header.data[i] ); @@ -503,8 +537,8 @@ protected: int price_matched( const uint8_t prev_byte, const uint8_t symbol, const uint8_t match_byte ) const - { return ::price_matched( bm_literal[get_lit_state(prev_byte)], - symbol, match_byte ); } + { return ::price_matched( bm_literal[get_lit_state(prev_byte)], symbol, + match_byte ); } void encode_literal( const uint8_t prev_byte, const uint8_t symbol ) { renc.encode_tree8( bm_literal[get_lit_state(prev_byte)], symbol ); } @@ -516,7 +550,7 @@ protected: void encode_pair( const unsigned dis, const int len, const int pos_state ) { - match_len_encoder.encode( renc, len, pos_state ); + renc.encode_len( match_len_model, len, pos_state ); const int dis_slot = get_slot( dis ); renc.encode_tree6( bm_dis_slot[get_len_state(len)], dis_slot ); @@ -584,18 +618,18 @@ class LZ_encoder : public LZ_encoder_base }; Matchfinder & matchfinder; + Len_prices match_len_prices; + Len_prices rep_len_prices; int pending_num_pairs; - struct Pair pairs[max_match_len+1]; + Pair pairs[max_match_len+1]; Trial trials[max_num_trials]; - int dis_prices[len_states][modeled_distances]; int dis_slot_prices[len_states][2*max_dictionary_bits]; + int dis_prices[len_states][modeled_distances]; int align_prices[dis_align_size]; - int align_price_count; const int num_dis_slots; - void fill_align_prices(); - void fill_distance_prices(); + void update_distance_prices(); // move-to-front dis in/into reps if( dis > 0 ) static void mtf_reps( const int dis, int reps[num_rep_distances] ) @@ -636,12 +670,12 @@ class LZ_encoder : public LZ_encoder_base int price_rep0_len( const int len, const State state, const int pos_state ) const { return price_rep( 0, state, pos_state ) + - rep_len_encoder.price( len, pos_state ); + rep_len_prices.price( len, pos_state ); } int price_pair( const int dis, const int len, const int pos_state ) const { - const int price = match_len_encoder.price( len, pos_state ); + const int price = match_len_prices.price( len, pos_state ); const int len_state = get_len_state( len ); if( dis < modeled_distances ) return price + dis_prices[len_state][dis]; @@ -709,10 +743,11 @@ class LZ_encoder : public LZ_encoder_base public: LZ_encoder( Matchfinder & mf, const File_header & header, const int outfd ) : - LZ_encoder_base( header, mf.match_len_limit(), outfd ), + LZ_encoder_base( header, outfd ), matchfinder( mf ), + match_len_prices( match_len_model, mf.match_len_limit() ), + rep_len_prices( rep_len_model, mf.match_len_limit() ), pending_num_pairs( 0 ), - align_price_count( 0 ), num_dis_slots( 2 * real_bits( mf.dictionary_size() - 1 ) ) {} diff --git a/fast_encoder.cc b/fast_encoder.cc index f87fdec..5b30a46 100644 --- a/fast_encoder.cc +++ b/fast_encoder.cc @@ -133,7 +133,7 @@ bool FLZ_encoder::encode_member( const unsigned long long member_size ) reps[0] = distance; } state.set_rep(); - rep_len_encoder.encode( renc, len, pos_state ); + renc.encode_len( rep_len_model, len, pos_state ); fmatchfinder.move_pos(); fmatchfinder.update_and_move( len - 1 ); continue; diff --git a/fast_encoder.h b/fast_encoder.h index 486f03f..711dde6 100644 --- a/fast_encoder.h +++ b/fast_encoder.h @@ -67,7 +67,7 @@ class FLZ_encoder : public LZ_encoder_base public: FLZ_encoder( Fmatchfinder & mf, const File_header & header, const int outfd ) : - LZ_encoder_base( header, mf.len_limit, outfd ), + LZ_encoder_base( header, outfd ), fmatchfinder( mf ) {} @@ -140,7 +140,7 @@ void show_help() void show_version() { - std::printf( "%s %s\n", Program_name, PROGVERSION ); + std::printf( "%s %s\n", program_name, PROGVERSION ); std::printf( "Copyright (C) %s Antonio Diaz Diaz.\n", program_year ); std::printf( "License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>\n" "This is free software: you are free to change and redistribute it.\n" @@ -259,8 +259,7 @@ int open_instream( const char * const name, struct stat * const in_statsp, } else { - do infd = open( name, O_RDONLY | O_BINARY ); - while( infd < 0 && errno == EINTR ); + infd = open( name, O_RDONLY | O_BINARY ); if( infd < 0 ) { if( verbosity >= 0 ) @@ -323,8 +322,7 @@ bool open_outstream( const bool force ) int flags = O_CREAT | O_WRONLY | O_BINARY; if( force ) flags |= O_TRUNC; else flags |= O_EXCL; - do outfd = open( output_filename.c_str(), flags, outfd_mode ); - while( outfd < 0 && errno == EINTR ); + outfd = open( output_filename.c_str(), flags, outfd_mode ); if( outfd < 0 && verbosity >= 0 ) { if( errno == EEXIST ) @@ -429,7 +427,7 @@ int compress( const unsigned long long member_size, if( !header.dictionary_size( encoder_options.dictionary_size ) || encoder_options.match_len_limit < min_match_len_limit || encoder_options.match_len_limit > max_match_len ) - internal_error( "invalid argument to encoder" ); + internal_error( "invalid argument to encoder." ); try { Matchfinder matchfinder( header.dictionary_size(), @@ -445,7 +443,7 @@ int compress( const unsigned long long member_size, if( verbosity >= 2 ) show_progress( in_size, &matchfinder, &pp, cfile_size ); // init if( !encoder.encode_member( size ) ) - { pp( "Encoder error" ); retval = 1; break; } + { pp( "Encoder error." ); retval = 1; break; } in_size += matchfinder.data_position(); out_size += encoder.member_position(); if( matchfinder.finished() ) break; @@ -459,7 +457,7 @@ int compress( const unsigned long long member_size, { close_and_set_permissions( in_statsp ); if( !next_filename() ) - { pp( "Too many volume files" ); retval = 1; break; } + { pp( "Too many volume files." ); retval = 1; break; } if( !open_outstream( true ) ) { retval = 1; break; } delete_output_on_interrupt = true; } @@ -483,7 +481,7 @@ int compress( const unsigned long long member_size, } catch( std::bad_alloc ) { - pp( "Not enough memory. Try a smaller dictionary size" ); + pp( "Not enough memory. Try a smaller dictionary size." ); retval = 1; } catch( Error e ) { pp(); show_error( e.msg, errno ); retval = 1; } @@ -505,7 +503,7 @@ int fcompress( const unsigned long long member_size, try { Fmatchfinder fmatchfinder( infd ); if( !header.dictionary_size( fmatchfinder.dictionary_size() ) ) - internal_error( "invalid argument to encoder" ); + internal_error( "invalid argument to encoder." ); unsigned long long in_size = 0, out_size = 0, partial_volume_size = 0; while( true ) // encode one member per iteration @@ -516,7 +514,7 @@ int fcompress( const unsigned long long member_size, if( verbosity >= 2 ) show_progress( in_size, &fmatchfinder, &pp, cfile_size ); // init if( !encoder.encode_member( size ) ) - { pp( "Encoder error" ); retval = 1; break; } + { pp( "Encoder error." ); retval = 1; break; } in_size += fmatchfinder.data_position(); out_size += encoder.member_position(); if( fmatchfinder.finished() ) break; @@ -530,7 +528,7 @@ int fcompress( const unsigned long long member_size, { close_and_set_permissions( in_statsp ); if( !next_filename() ) - { pp( "Too many volume files" ); retval = 1; break; } + { pp( "Too many volume files." ); retval = 1; break; } if( !open_outstream( true ) ) { retval = 1; break; } delete_output_on_interrupt = true; } @@ -554,7 +552,7 @@ int fcompress( const unsigned long long member_size, } catch( std::bad_alloc ) { - pp( "Not enough memory. Try a smaller dictionary size" ); + pp( "Not enough memory. Try a smaller dictionary size." ); retval = 1; } catch( Error e ) { pp(); show_error( e.msg, errno ); retval = 1; } @@ -594,6 +592,7 @@ void show_trailing_garbage( const uint8_t * const data, const int size, garbage_msg += xdigit( data[i] & 0x0F ); } } + garbage_msg += '.'; pp( garbage_msg.c_str() ); } @@ -613,7 +612,7 @@ int decompress( const int infd, const Pretty_print & pp, const bool testing ) if( rdec.finished() ) // End Of File { if( first_member ) - { pp( "File ends unexpectedly at member header" ); retval = 2; } + { pp( "File ends unexpectedly at member header." ); retval = 2; } else if( verbosity >= 4 && size > 0 ) show_trailing_garbage( header.data, size, pp, true ); break; @@ -621,7 +620,7 @@ int decompress( const int infd, const Pretty_print & pp, const bool testing ) if( !header.verify_magic() ) { if( first_member ) - { pp( "Bad magic number (file not in lzip format)" ); retval = 2; } + { pp( "Bad magic number (file not in lzip format)." ); retval = 2; } else if( verbosity >= 4 ) show_trailing_garbage( header.data, size, pp, false ); break; @@ -636,7 +635,7 @@ int decompress( const int infd, const Pretty_print & pp, const bool testing ) } if( header.dictionary_size() < min_dictionary_size || header.dictionary_size() > max_dictionary_size ) - { pp( "Invalid dictionary size in member header" ); retval = 2; break; } + { pp( "Invalid dictionary size in member header." ); retval = 2; break; } if( verbosity >= 2 || ( verbosity == 1 && first_member ) ) { pp(); if( verbosity >= 3 ) show_header( header ); } @@ -650,10 +649,10 @@ int decompress( const int infd, const Pretty_print & pp, const bool testing ) { pp(); if( result == 2 ) - std::fprintf( stderr, "File ends unexpectedly at pos %llu\n", + std::fprintf( stderr, "File ends unexpectedly at pos %llu.\n", partial_file_pos ); else - std::fprintf( stderr, "Decoder error at pos %llu\n", + std::fprintf( stderr, "Decoder error at pos %llu.\n", partial_file_pos ); } retval = 2; break; @@ -662,7 +661,7 @@ int decompress( const int infd, const Pretty_print & pp, const bool testing ) { std::fprintf( stderr, testing ? "ok\n" : "done\n" ); pp.reset(); } } } - catch( std::bad_alloc ) { pp( "Not enough memory" ); retval = 1; } + catch( std::bad_alloc ) { pp( "Not enough memory." ); retval = 1; } catch( Error e ) { pp(); show_error( e.msg, errno ); retval = 1; } if( verbosity == 1 && retval == 0 ) std::fprintf( stderr, testing ? "ok\n" : "done\n" ); @@ -698,7 +697,7 @@ void show_error( const char * const msg, const int errcode, const bool help ) { std::fprintf( stderr, "%s: %s", program_name, msg ); if( errcode > 0 ) - std::fprintf( stderr, ": %s", std::strerror( errcode ) ); + std::fprintf( stderr, ": %s.", std::strerror( errcode ) ); std::fprintf( stderr, "\n" ); } if( help ) @@ -711,7 +710,7 @@ void show_error( const char * const msg, const int errcode, const bool help ) void internal_error( const char * const msg ) { if( verbosity >= 0 ) - std::fprintf( stderr, "%s: internal error: %s.\n", program_name, msg ); + std::fprintf( stderr, "%s: internal error: %s\n", program_name, msg ); std::exit( 3 ); } @@ -837,7 +836,7 @@ int main( const int argc, const char * const argv[] ) case 't': program_mode = m_test; break; case 'v': if( verbosity < 4 ) ++verbosity; break; case 'V': show_version(); return 0; - default : internal_error( "uncaught option" ); + default : internal_error( "uncaught option." ); } } // end process options @@ -874,13 +873,13 @@ int main( const int argc, const char * const argv[] ) struct stat in_stats; output_filename.clear(); - if( !filenames[i].size() || filenames[i] == "-" ) + if( filenames[i].empty() || filenames[i] == "-" ) { input_filename.clear(); infd = STDIN_FILENO; if( program_mode != m_test ) { - if( to_stdout || !default_output_filename.size() ) + if( to_stdout || default_output_filename.empty() ) outfd = STDOUT_FILENO; else { diff --git a/testsuite/check.sh b/testsuite/check.sh index a8d0bf1..7ce7a10 100755 --- a/testsuite/check.sh +++ b/testsuite/check.sh @@ -13,7 +13,7 @@ testdir=`cd "$1" ; pwd` LZIP="${objdir}"/lzip framework_failure() { echo "failure in testing framework" ; exit 1 ; } -if [ ! -x "${LZIP}" ] ; then +if [ ! -f "${LZIP}" ] || [ ! -x "${LZIP}" ] ; then echo "${LZIP}: cannot execute" exit 1 fi @@ -28,22 +28,29 @@ fail=0 printf "testing lzip-%s..." "$2" +"${LZIP}" -cqm4 in > /dev/null +if [ $? = 1 ] ; then printf . ; else printf - ; fail=1 ; fi +"${LZIP}" -cqm274 in > /dev/null +if [ $? = 1 ] ; then printf . ; else printf - ; fail=1 ; fi "${LZIP}" -cqs-1 in > /dev/null -if [ $? = 1 ] ; then printf . ; else fail=1 ; printf - ; fi +if [ $? = 1 ] ; then printf . ; else printf - ; fail=1 ; fi "${LZIP}" -cqs0 in > /dev/null -if [ $? = 1 ] ; then printf . ; else fail=1 ; printf - ; fi +if [ $? = 1 ] ; then printf . ; else printf - ; fail=1 ; fi "${LZIP}" -cqs4095 in > /dev/null -if [ $? = 1 ] ; then printf . ; else fail=1 ; printf - ; fi -"${LZIP}" -cqm274 in > /dev/null -if [ $? = 1 ] ; then printf . ; else fail=1 ; printf - ; fi -"${LZIP}" -tq in -if [ $? = 2 ] ; then printf . ; else fail=1 ; printf - ; fi -"${LZIP}" -tq < in -if [ $? = 2 ] ; then printf . ; else fail=1 ; printf - ; fi +if [ $? = 1 ] ; then printf . ; else printf - ; fail=1 ; fi +"${LZIP}" -cqs513MiB in > /dev/null +if [ $? = 1 ] ; then printf . ; else printf - ; fail=1 ; fi +printf " in: Bad magic number (file not in lzip format).\n" > msg +"${LZIP}" -t in 2> out +if [ $? = 2 ] && cmp out msg ; then printf . ; else printf - ; fail=1 ; fi +printf " (stdin): Bad magic number (file not in lzip format).\n" > msg +"${LZIP}" -t < in 2> out +if [ $? = 2 ] && cmp out msg ; then printf . ; else printf - ; fail=1 ; fi +rm -f out msg "${LZIP}" -cdq in -if [ $? = 2 ] ; then printf . ; else fail=1 ; printf - ; fi +if [ $? = 2 ] ; then printf . ; else printf - ; fail=1 ; fi "${LZIP}" -cdq < in -if [ $? = 2 ] ; then printf . ; else fail=1 ; printf - ; fi +if [ $? = 2 ] ; then printf . ; else printf - ; fail=1 ; fi dd if="${in_lz}" bs=1 count=6 2> /dev/null | "${LZIP}" -tq if [ $? = 2 ] ; then printf . ; else printf - ; fail=1 ; fi dd if="${in_lz}" bs=1 count=20 2> /dev/null | "${LZIP}" -tq @@ -54,8 +61,38 @@ if [ $? = 2 ] ; then printf . ; else printf - ; fail=1 ; fi cmp in copy || fail=1 printf . +cat "${in_lz}" > copy.lz || framework_failure +printf "to be overwritten" > copy || framework_failure +"${LZIP}" -df copy.lz || fail=1 +cmp in copy || fail=1 +printf . + +printf "to be overwritten" > copy || framework_failure +"${LZIP}" -df -o copy < "${in_lz}" || fail=1 +cmp in copy || fail=1 +printf . + +"${LZIP}" < in > anyothername || fail=1 +"${LZIP}" -d anyothername || fail=1 +cmp in anyothername.out || fail=1 +printf . + +cat in in > in2 || framework_failure +"${LZIP}" -o copy2 < in2 || fail=1 +"${LZIP}" -t copy2.lz || fail=1 +printf . +"${LZIP}" -cd copy2.lz > copy2 || fail=1 +cmp in2 copy2 || fail=1 +printf . + +printf "garbage" >> copy2.lz || framework_failure +printf "to be overwritten" > copy2 || framework_failure +"${LZIP}" -df copy2.lz || fail=1 +cmp in2 copy2 || fail=1 +printf . + "${LZIP}" -cfq "${in_lz}" > out -if [ $? = 1 ] ; then printf . ; else fail=1 ; printf - ; fi +if [ $? = 1 ] ; then printf . ; else printf - ; fail=1 ; fi "${LZIP}" -cF "${in_lz}" > out || fail=1 "${LZIP}" -cd out | "${LZIP}" -d > copy || fail=1 cmp in copy || fail=1 @@ -92,25 +129,6 @@ for i in s4Ki 0 1 2 3 4 5 6 7 8 9 ; do done printf . -"${LZIP}" < in > anyothername || fail=1 -"${LZIP}" -d anyothername || fail=1 -cmp in anyothername.out || fail=1 -printf . - -cat in in > in2 || framework_failure -"${LZIP}" -o copy2 < in2 || fail=1 -"${LZIP}" -t copy2.lz || fail=1 -printf . -"${LZIP}" -cd copy2.lz > copy2 || fail=1 -cmp in2 copy2 || fail=1 -printf . - -printf "garbage" >> copy2.lz || framework_failure -printf "to be overwritten" > copy2 || framework_failure -"${LZIP}" -df copy2.lz || fail=1 -cmp in2 copy2 || fail=1 -printf . - echo if [ ${fail} = 0 ] ; then echo "tests completed successfully." |