summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ChangeLog13
-rw-r--r--INSTALL8
-rw-r--r--Makefile.in19
-rw-r--r--NEWS19
-rw-r--r--README6
-rw-r--r--arg_parser.cc4
-rwxr-xr-xconfigure37
-rw-r--r--decoder.cc75
-rw-r--r--decoder.h104
-rw-r--r--doc/lzip.14
-rw-r--r--doc/lzip.info64
-rw-r--r--doc/lzip.texinfo52
-rw-r--r--encoder.cc498
-rw-r--r--encoder.h345
-rw-r--r--fast_encoder.cc238
-rw-r--r--fast_encoder.h24
-rw-r--r--lzip.h104
-rw-r--r--main.cc179
-rwxr-xr-xtestsuite/check.sh41
-rw-r--r--testsuite/test.txt.lzbin0 -> 11518 bytes
-rw-r--r--testsuite/test_sync.lzbin11658 -> 0 bytes
-rw-r--r--testsuite/test_v0.lzbin11540 -> 0 bytes
-rw-r--r--testsuite/test_v1.lzbin11548 -> 0 bytes
23 files changed, 1021 insertions, 813 deletions
diff --git a/ChangeLog b/ChangeLog
index 8e3aa1e..296049a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+2013-02-17 Antonio Diaz Diaz <ant_diaz@teleline.es>
+
+ * Version 1.14 released.
+ * Multi-step trials have been implemented.
+ * Compression ratio has been slightly increased.
+ * Compression time has been reduced by 5%.
+ * Decompression time has been reduced by 12%.
+ * Makefile.in: Added new target 'install-bin'.
+ * main.cc: Use 'setmode' instead of '_setmode' on Windows and OS/2.
+ * main.cc: Define 'strtoull' to 'std::strtoul' on Windows.
+
2012-02-24 Antonio Diaz Diaz <ant_diaz@teleline.es>
* Version 1.13 released.
@@ -209,7 +220,7 @@
* Version 0.1 released.
-Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This file is a collection of facts, and thus it is not copyrightable,
but just in case, you have unlimited permission to copy, distribute and
diff --git a/INSTALL b/INSTALL
index 4885d81..54406be 100644
--- a/INSTALL
+++ b/INSTALL
@@ -1,7 +1,7 @@
Requirements
------------
You will need a C++ compiler.
-I use gcc 4.3.5 and 3.3.6, but the code should compile with any
+I use gcc 4.7.2 and 3.3.6, but the code should compile with any
standards compliant compiler.
Gcc is available at http://gcc.gnu.org.
@@ -32,6 +32,10 @@ the main archive.
5. Type 'make install' to install the program and any data files and
documentation.
+ You can install only the program, the info manual or the man page
+ typing 'make install-bin', 'make install-info' or 'make install-man'
+ respectively.
+
Another way
-----------
@@ -50,7 +54,7 @@ After running 'configure', you can run 'make' and 'make install' as
explained above.
-Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This file is free documentation: you have unlimited permission to copy,
distribute and modify it.
diff --git a/Makefile.in b/Makefile.in
index d64b06c..f6daaa1 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -6,11 +6,11 @@ INSTALL_DATA = $(INSTALL) -p -m 644
INSTALL_DIR = $(INSTALL) -d -m 755
SHELL = /bin/sh
-objs = arg_parser.o decoder.o encoder.o fast_encoder.o main.o
+objs = arg_parser.o encoder.o fast_encoder.o decoder.o main.o
-.PHONY : all install install-info install-man install-strip \
- uninstall uninstall-info uninstall-man \
+.PHONY : all install install-bin install-info install-man install-strip \
+ uninstall uninstall-bin uninstall-info uninstall-man \
doc info man check dist clean distclean
all : $(progname)
@@ -54,14 +54,16 @@ Makefile : $(VPATH)/configure $(VPATH)/Makefile.in
check : all
@$(VPATH)/testsuite/check.sh $(VPATH)/testsuite $(pkgversion)
-install : all install-info install-man
+install : install-bin install-info install-man
+
+install-bin : all
if [ ! -d "$(DESTDIR)$(bindir)" ] ; then $(INSTALL_DIR) "$(DESTDIR)$(bindir)" ; fi
$(INSTALL_PROGRAM) ./$(progname) "$(DESTDIR)$(bindir)/$(progname)"
install-info :
if [ ! -d "$(DESTDIR)$(infodir)" ] ; then $(INSTALL_DIR) "$(DESTDIR)$(infodir)" ; fi
$(INSTALL_DATA) $(VPATH)/doc/$(pkgname).info "$(DESTDIR)$(infodir)/$(pkgname).info"
- -install-info --info-dir="$(DESTDIR)$(infodir)" $(DESTDIR)$(infodir)/$(pkgname).info
+ -install-info --info-dir="$(DESTDIR)$(infodir)" "$(DESTDIR)$(infodir)/$(pkgname).info"
install-man :
if [ ! -d "$(DESTDIR)$(mandir)/man1" ] ; then $(INSTALL_DIR) "$(DESTDIR)$(mandir)/man1" ; fi
@@ -70,7 +72,9 @@ install-man :
install-strip : all
$(MAKE) INSTALL_PROGRAM='$(INSTALL_PROGRAM) -s' install
-uninstall : uninstall-info uninstall-man
+uninstall : uninstall-bin uninstall-info uninstall-man
+
+uninstall-bin :
-rm -f "$(DESTDIR)$(bindir)/$(progname)"
uninstall-info :
@@ -96,8 +100,7 @@ dist : doc
$(DISTNAME)/doc/$(pkgname).texinfo \
$(DISTNAME)/testsuite/check.sh \
$(DISTNAME)/testsuite/test.txt \
- $(DISTNAME)/testsuite/test_sync.lz \
- $(DISTNAME)/testsuite/test_v[01].lz \
+ $(DISTNAME)/testsuite/test.txt.lz \
$(DISTNAME)/*.h \
$(DISTNAME)/*.cc
rm -f $(DISTNAME)
diff --git a/NEWS b/NEWS
index 41cf2d4..0bf236a 100644
--- a/NEWS
+++ b/NEWS
@@ -1,18 +1,11 @@
-Changes in version 1.13:
+Changes in version 1.14:
-Lziprecover has been moved to its own package.
+Multi-step trials have been implemented.
-Inability to change output file attributes has been downgraded from
-error to warning.
+Compression ratio has been slightly increased.
-Compression time of option "-0" has been reduced by 2%.
+Compression time has been reduced by 5%.
-A reorganization of the compression code has been made.
+Decompression time has been reduced by 12%.
-A small change has been made in the "--help" output and man page.
-
-Quote characters in messages have been changed as advised by GNU Coding
-Standards.
-
-Configure option "--datadir" has been renamed to "--datarootdir" to
-follow GNU Standards.
+The target "install-bin" has been added to the Makefile.
diff --git a/README b/README
index 6ff4771..98f4efb 100644
--- a/README
+++ b/README
@@ -32,6 +32,10 @@ split the compressed output in volumes of a given size, even when
reading from standard input. This allows the direct creation of
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).
+
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
@@ -63,7 +67,7 @@ range encoding), Igor Pavlov (for putting all the above together in
LZMA), and Julian Seward (for bzip2's CLI and the idea of unzcrash).
-Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This file is free documentation: you have unlimited permission to copy,
distribute and modify it.
diff --git a/arg_parser.cc b/arg_parser.cc
index b3fd48d..13bcbcb 100644
--- a/arg_parser.cc
+++ b/arg_parser.cc
@@ -36,7 +36,7 @@
bool Arg_parser::parse_long_option( const char * const opt, const char * const arg,
const Option options[], int & argind )
{
- unsigned int len;
+ unsigned len;
int index = -1;
bool exact = false, ambig = false;
@@ -178,7 +178,7 @@ Arg_parser::Arg_parser( const int argc, const char * const argv[],
if( error_.size() ) data.clear();
else
{
- for( unsigned int i = 0; i < non_options.size(); ++i )
+ for( unsigned i = 0; i < non_options.size(); ++i )
{ data.push_back( Record() ); data.back().argument.swap( non_options[i] ); }
while( argind < argc )
{ data.push_back( Record() ); data.back().argument = argv[argind++]; }
diff --git a/configure b/configure
index f96530e..b30d534 100755
--- a/configure
+++ b/configure
@@ -1,6 +1,6 @@
#! /bin/sh
# configure script for Lzip - Data compressor based on the LZMA algorithm
-# Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+# Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
#
# This configure script is free software: you have unlimited permission
# to copy, distribute and modify it.
@@ -8,7 +8,7 @@
args=
no_create=
pkgname=lzip
-pkgversion=1.13
+pkgversion=1.14
progname=lzip
srctrigger=lzip.h
@@ -22,11 +22,19 @@ bindir='$(exec_prefix)/bin'
datarootdir='$(prefix)/share'
infodir='$(datarootdir)/info'
mandir='$(datarootdir)/man'
-CXX=
+CXX=g++
CPPFLAGS=
CXXFLAGS='-Wall -W -O2'
LDFLAGS=
+# checking whether we are using GNU C++.
+if [ ! -x /bin/g++ ] &&
+ [ ! -x /usr/bin/g++ ] &&
+ [ ! -x /usr/local/bin/g++ ] ; then
+ CXX=c++
+ CXXFLAGS='-W -O2'
+fi
+
# Loop over all args
while [ -n "$1" ] ; do
@@ -91,14 +99,14 @@ done
srcdirtext=
if [ -z "${srcdir}" ] ; then
srcdirtext="or . or .." ; srcdir=.
- if [ ! -r ${srcdir}/${srctrigger} ] ; then srcdir=.. ; fi
- if [ ! -r ${srcdir}/${srctrigger} ] ; then
+ if [ ! -r "${srcdir}/${srctrigger}" ] ; then srcdir=.. ; fi
+ if [ ! -r "${srcdir}/${srctrigger}" ] ; then
## the sed command below emulates the dirname command
srcdir=`echo $0 | sed -e 's,[^/]*$,,;s,/$,,;s,^$,.,'`
fi
fi
-if [ ! -r ${srcdir}/${srctrigger} ] ; then
+if [ ! -r "${srcdir}/${srctrigger}" ] ; then
exec 1>&2
echo
echo "configure: Can't find sources in ${srcdir} ${srcdirtext}"
@@ -107,18 +115,7 @@ if [ ! -r ${srcdir}/${srctrigger} ] ; then
fi
# Set srcdir to . if that's what it is.
-if [ "`pwd`" = "`cd ${srcdir} ; pwd`" ] ; then srcdir=. ; fi
-
-# checking whether we are using GNU C++.
-if [ -z "${CXX}" ] ; then # Let the user override the test.
- if [ -x /bin/g++ ] ||
- [ -x /usr/bin/g++ ] ||
- [ -x /usr/local/bin/g++ ] ; then
- CXX="g++"
- else
- CXX="c++"
- fi
-fi
+if [ "`pwd`" = "`cd "${srcdir}" ; pwd`" ] ; then srcdir=. ; fi
echo
if [ -z "${no_create}" ] ; then
@@ -152,7 +149,7 @@ echo "LDFLAGS = ${LDFLAGS}"
rm -f Makefile
cat > Makefile << EOF
# Makefile for Lzip - Data compressor based on the LZMA algorithm
-# Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+# Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
# This file was generated automatically by configure. Do not edit.
#
# This Makefile is free software: you have unlimited permission
@@ -173,6 +170,6 @@ CPPFLAGS = ${CPPFLAGS}
CXXFLAGS = ${CXXFLAGS}
LDFLAGS = ${LDFLAGS}
EOF
-cat ${srcdir}/Makefile.in >> Makefile
+cat "${srcdir}/Makefile.in" >> Makefile
echo "OK. Now you can run make."
diff --git a/decoder.cc b/decoder.cc
index ae37563..537143f 100644
--- a/decoder.cc
+++ b/decoder.cc
@@ -1,5 +1,5 @@
/* Lzip - Data compressor based on the LZMA algorithm
- Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+ Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -42,7 +42,7 @@ void Pretty_print::operator()( const char * const msg ) const
{
first_post = false;
std::fprintf( stderr, " %s: ", name_.c_str() );
- for( unsigned int i = 0; i < longest_name - name_.size(); ++i )
+ for( unsigned i = 0; i < longest_name - name_.size(); ++i )
std::fprintf( stderr, " " );
if( !msg ) std::fflush( stderr );
}
@@ -60,13 +60,13 @@ int readblock( const int fd, uint8_t * const buf, const int size )
errno = 0;
while( rest > 0 )
{
- errno = 0;
const int n = read( fd, buf + size - rest, rest );
if( n > 0 ) rest -= n;
- else if( n == 0 ) break;
+ else if( n == 0 ) break; // EOF
else if( errno != EINTR && errno != EAGAIN ) break;
+ errno = 0;
}
- return ( rest > 0 ) ? size - rest : size;
+ return size - rest;
}
@@ -79,12 +79,12 @@ int writeblock( const int fd, const uint8_t * const buf, const int size )
errno = 0;
while( rest > 0 )
{
- errno = 0;
const int n = write( fd, buf + size - rest, rest );
if( n > 0 ) rest -= n;
else if( n < 0 && errno != EINTR && errno != EAGAIN ) break;
+ errno = 0;
}
- return ( rest > 0 ) ? size - rest : size;
+ return size - rest;
}
@@ -121,10 +121,11 @@ bool LZ_decoder::verify_trailer( const Pretty_print & pp ) const
{
File_trailer trailer;
const int trailer_size = File_trailer::size( member_version );
- const long long member_size = range_decoder.member_position() + trailer_size;
+ const unsigned long long member_size =
+ range_decoder.member_position() + trailer_size;
bool error = false;
- const int size = range_decoder.read_data( trailer.data, trailer_size );
+ int size = range_decoder.read_data( trailer.data, trailer_size );
if( size < trailer_size )
{
error = true;
@@ -134,9 +135,11 @@ bool LZ_decoder::verify_trailer( const Pretty_print & pp ) const
std::fprintf( stderr, "Trailer truncated at trailer position %d;"
" some checks may fail.\n", size );
}
- for( int i = size; i < trailer_size; ++i ) trailer.data[i] = 0;
+ while( size < trailer_size ) trailer.data[size++] = 0;
}
+
if( member_version == 0 ) trailer.member_size( member_size );
+
if( !range_decoder.code_is_zero() )
{
error = true;
@@ -149,7 +152,7 @@ bool LZ_decoder::verify_trailer( const Pretty_print & pp ) const
{
pp();
std::fprintf( stderr, "CRC mismatch; trailer says %08X, data CRC is %08X.\n",
- (unsigned int)trailer.data_crc(), (unsigned int)crc() );
+ trailer.data_crc(), crc() );
}
}
if( trailer.data_size() != data_position() )
@@ -158,7 +161,7 @@ bool LZ_decoder::verify_trailer( const Pretty_print & pp ) const
if( pp.verbosity() >= 0 )
{
pp();
- std::fprintf( stderr, "Data size mismatch; trailer says %lld, data size is %lld (0x%llX).\n",
+ std::fprintf( stderr, "Data size mismatch; trailer says %llu, data size is %llu (0x%llX).\n",
trailer.data_size(), data_position(), data_position() );
}
}
@@ -168,7 +171,7 @@ bool LZ_decoder::verify_trailer( const Pretty_print & pp ) const
if( pp.verbosity() >= 0 )
{
pp();
- std::fprintf( stderr, "Member size mismatch; trailer says %lld, member size is %lld (0x%llX).\n",
+ std::fprintf( stderr, "Member size mismatch; trailer says %llu, member size is %llu (0x%llX).\n",
trailer.member_size(), member_size, member_size );
}
}
@@ -178,9 +181,8 @@ bool LZ_decoder::verify_trailer( const Pretty_print & pp ) const
( 8.0 * member_size ) / data_position(),
100.0 * ( 1.0 - ( (double)member_size / data_position() ) ) );
if( !error && pp.verbosity() >= 4 )
- std::fprintf( stderr, "data CRC %08X, data size %9lld, member size %8lld. ",
- (unsigned int)trailer.data_crc(), trailer.data_size(),
- trailer.member_size() );
+ std::fprintf( stderr, "data CRC %08X, data size %9llu, member size %8llu. ",
+ trailer.data_crc(), trailer.data_size(), trailer.member_size() );
return !error;
}
@@ -189,6 +191,7 @@ bool LZ_decoder::verify_trailer( const Pretty_print & pp ) const
// 3 = trailer error, 4 = unknown marker found.
int LZ_decoder::decode_member( const Pretty_print & pp )
{
+ Bit_model bm_literal[1<<literal_context_bits][0x300];
Bit_model bm_match[State::states][pos_states];
Bit_model bm_rep[State::states];
Bit_model bm_rep0[State::states];
@@ -196,32 +199,30 @@ int LZ_decoder::decode_member( const Pretty_print & pp )
Bit_model bm_rep2[State::states];
Bit_model bm_len[State::states][pos_states];
Bit_model bm_dis_slot[max_dis_states][1<<dis_slot_bits];
- Bit_model bm_dis[modeled_distances-end_dis_model+1];
+ Bit_model bm_dis[modeled_distances-end_dis_model];
Bit_model bm_align[dis_align_size];
-
- unsigned int rep0 = 0; // rep[0-3] latest four distances
- unsigned int rep1 = 0; // used for efficient coding of
- unsigned int rep2 = 0; // repeated distances
- unsigned int rep3 = 0;
-
Len_decoder len_decoder;
Len_decoder rep_match_len_decoder;
- Literal_decoder literal_decoder;
+
+ unsigned rep0 = 0; // rep[0-3] latest four distances
+ unsigned rep1 = 0; // used for efficient coding of
+ unsigned rep2 = 0; // repeated distances
+ unsigned rep3 = 0;
+
State state;
range_decoder.load();
- while( true )
+ while( !range_decoder.finished() )
{
- if( range_decoder.finished() ) { flush_data(); return 2; }
const int pos_state = data_position() & pos_state_mask;
if( range_decoder.decode_bit( bm_match[state()][pos_state] ) == 0 )
{
const uint8_t prev_byte = get_prev_byte();
if( state.is_char() )
- put_byte( literal_decoder.decode( range_decoder, prev_byte ) );
+ put_byte( range_decoder.decode_tree( bm_literal[get_lit_state(prev_byte)], 8 ) );
else
- put_byte( literal_decoder.decode_matched( range_decoder, prev_byte,
- get_byte( rep0 ) ) );
+ put_byte( range_decoder.decode_matched( bm_literal[get_lit_state(prev_byte)],
+ get_byte( rep0 ) ) );
state.set_char();
}
else
@@ -232,7 +233,7 @@ int LZ_decoder::decode_member( const Pretty_print & pp )
len = 0;
if( range_decoder.decode_bit( bm_rep0[state()] ) == 1 )
{
- unsigned int distance;
+ unsigned distance;
if( range_decoder.decode_bit( bm_rep1[state()] ) == 0 )
distance = rep1;
else
@@ -258,20 +259,20 @@ int LZ_decoder::decode_member( const Pretty_print & pp )
}
else
{
- const unsigned int rep0_saved = rep0;
+ const unsigned rep0_saved = rep0;
len = min_match_len + len_decoder.decode( range_decoder, pos_state );
- const int dis_slot = range_decoder.decode_tree( bm_dis_slot[get_dis_state(len)], dis_slot_bits );
+ const int dis_slot = range_decoder.decode_tree6( bm_dis_slot[get_dis_state(len)] );
if( dis_slot < start_dis_model ) rep0 = dis_slot;
else
{
const int direct_bits = ( dis_slot >> 1 ) - 1;
rep0 = ( 2 | ( dis_slot & 1 ) ) << direct_bits;
if( dis_slot < end_dis_model )
- rep0 += range_decoder.decode_tree_reversed( bm_dis + rep0 - dis_slot, direct_bits );
+ rep0 += range_decoder.decode_tree_reversed( bm_dis + rep0 - dis_slot - 1, direct_bits );
else
{
rep0 += range_decoder.decode( direct_bits - dis_align_bits ) << dis_align_bits;
- rep0 += range_decoder.decode_tree_reversed( bm_align, dis_align_bits );
+ rep0 += range_decoder.decode_tree_reversed4( bm_align );
if( rep0 == 0xFFFFFFFFU ) // Marker found
{
rep0 = rep0_saved;
@@ -296,11 +297,13 @@ int LZ_decoder::decode_member( const Pretty_print & pp )
}
rep3 = rep2; rep2 = rep1; rep1 = rep0_saved;
state.set_match();
- if( rep0 >= (unsigned int)dictionary_size ||
- ( rep0 >= (unsigned int)pos && !partial_data_pos ) )
+ if( rep0 >= (unsigned)dictionary_size ||
+ ( rep0 >= (unsigned)pos && !partial_data_pos ) )
{ flush_data(); return 1; }
}
copy_block( rep0, len );
}
}
+ flush_data();
+ return 2;
}
diff --git a/decoder.h b/decoder.h
index d583c65..a3559ad 100644
--- a/decoder.h
+++ b/decoder.h
@@ -1,5 +1,5 @@
/* Lzip - Data compressor based on the LZMA algorithm
- Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+ Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -18,7 +18,7 @@
class Range_decoder
{
enum { buffer_size = 16384 };
- long long partial_member_pos;
+ unsigned long long partial_member_pos;
uint8_t * const buffer; // input buffer
int pos; // current pos in buffer
int stream_pos; // when reached, a new block must be read
@@ -49,12 +49,12 @@ public:
bool code_is_zero() const { return ( code == 0 ); }
bool finished() { return pos >= stream_pos && !read_block(); }
- long long member_position() const { return partial_member_pos + pos; }
+ unsigned long long member_position() const { return partial_member_pos + pos; }
void reset_member_position() { partial_member_pos = -pos; }
uint8_t get_byte()
{
- if( finished() ) return 0x55; // make code != 0
+ if( finished() ) return 0xAA; // make code != 0
return buffer[pos++];
}
@@ -68,14 +68,14 @@ public:
pos += rd;
rest -= rd;
}
- return ( rest > 0 ) ? size - rest : size;
+ return size - rest;
}
void load()
{
code = 0;
- range = 0xFFFFFFFFU;
for( int i = 0; i < 5; ++i ) code = (code << 8) | get_byte();
+ range = 0xFFFFFFFFU;
}
void normalize()
@@ -89,17 +89,14 @@ public:
int symbol = 0;
for( int i = num_bits; i > 0; --i )
{
- symbol <<= 1;
- if( range <= 0x00FFFFFFU )
- {
- range <<= 7; code = (code << 8) | get_byte();
- if( code >= range ) { code -= range; symbol |= 1; }
- }
- else
- {
- range >>= 1;
- if( code >= range ) { code -= range; symbol |= 1; }
- }
+ normalize();
+ range >>= 1;
+// symbol <<= 1;
+// if( code >= range ) { code -= range; symbol |= 1; }
+ const uint32_t mask = 0U - (code < range);
+ code -= range;
+ code += range & mask;
+ symbol = (symbol << 1) + (mask + 1);
}
return symbol;
}
@@ -131,36 +128,63 @@ public:
return model - (1 << num_bits);
}
+ int decode_tree6( Bit_model bm[] )
+ {
+ int model = 1;
+ model = ( model << 1 ) | decode_bit( bm[model] );
+ model = ( model << 1 ) | decode_bit( bm[model] );
+ model = ( model << 1 ) | decode_bit( bm[model] );
+ model = ( model << 1 ) | decode_bit( bm[model] );
+ model = ( model << 1 ) | decode_bit( bm[model] );
+ model = ( model << 1 ) | decode_bit( bm[model] );
+ return model - (1 << 6);
+ }
+
int decode_tree_reversed( Bit_model bm[], const int num_bits )
{
int model = 1;
int symbol = 0;
for( int i = 0; i < num_bits; ++i )
{
- const int bit = decode_bit( bm[model] );
+ const bool bit = decode_bit( bm[model] );
model <<= 1;
- if( bit ) { model |= 1; symbol |= (1 << i); }
+ if( bit ) { ++model; symbol |= (1 << i); }
}
return symbol;
}
- int decode_matched( Bit_model bm[], const int match_byte )
+ int decode_tree_reversed4( Bit_model bm[] )
+ {
+ int model = 1;
+ int symbol = 0;
+ int bit = decode_bit( bm[model] );
+ model = (model << 1) + bit; symbol |= bit;
+ bit = decode_bit( bm[model] );
+ model = (model << 1) + bit; symbol |= (bit << 1);
+ bit = decode_bit( bm[model] );
+ model = (model << 1) + bit; symbol |= (bit << 2);
+ if( decode_bit( bm[model] ) ) symbol |= 8;
+ return symbol;
+ }
+
+ int decode_matched( Bit_model bm[], int match_byte )
{
Bit_model * const bm1 = bm + 0x100;
int symbol = 1;
for( int i = 7; i >= 0; --i )
{
- const int match_bit = ( match_byte >> i ) & 1;
- const int bit = decode_bit( bm1[(match_bit<<8)+symbol] );
- symbol = ( symbol << 1 ) | bit;
- if( match_bit != bit )
+ match_byte <<= 1;
+ const int match_bit = match_byte & 0x100;
+ const int bit = decode_bit( bm1[match_bit+symbol] );
+ symbol = ( symbol << 1 ) + bit;
+ if( match_bit != bit << 8 )
{
- while( --i >= 0 )
- symbol = ( symbol << 1 ) | decode_bit( bm[symbol] );
+ while( symbol < 0x100 )
+ symbol = ( symbol << 1 ) + decode_bit( bm[symbol] );
break;
}
}
- return symbol & 0xFF;
+ return symbol - 0x100;
}
};
@@ -187,27 +211,9 @@ public:
};
-class Literal_decoder
- {
- Bit_model bm_literal[1<<literal_context_bits][0x300];
-
- int lstate( const uint8_t prev_byte ) const
- { return ( prev_byte >> ( 8 - literal_context_bits ) ); }
-
-public:
- uint8_t decode( Range_decoder & range_decoder, const uint8_t prev_byte )
- { return range_decoder.decode_tree( bm_literal[lstate(prev_byte)], 8 ); }
-
- uint8_t decode_matched( Range_decoder & range_decoder,
- const uint8_t prev_byte, const uint8_t match_byte )
- { return range_decoder.decode_matched( bm_literal[lstate(prev_byte)],
- match_byte ); }
- };
-
-
class LZ_decoder
{
- long long partial_data_pos;
+ unsigned long long partial_data_pos;
Range_decoder & range_decoder;
const int dictionary_size;
const int buffer_size;
@@ -246,7 +252,7 @@ class LZ_decoder
if( i < 0 ) i += buffer_size;
if( len < buffer_size - std::max( pos, i ) && len <= std::abs( pos - i ) )
{
- std::memcpy( buffer + pos, buffer + i, len );
+ std::memcpy( buffer + pos, buffer + i, len ); // no wrap, no overlap
pos += len;
}
else for( ; len > 0; --len )
@@ -277,9 +283,9 @@ public:
~LZ_decoder() { delete[] buffer; }
- uint32_t crc() const { return crc_ ^ 0xFFFFFFFFU; }
+ unsigned crc() const { return crc_ ^ 0xFFFFFFFFU; }
- long long data_position() const { return partial_data_pos + pos; }
+ unsigned long long data_position() const { return partial_data_pos + pos; }
int decode_member( const Pretty_print & pp );
};
diff --git a/doc/lzip.1 b/doc/lzip.1
index f83c444..e0b9ad0 100644
--- a/doc/lzip.1
+++ b/doc/lzip.1
@@ -1,5 +1,5 @@
.\" DO NOT MODIFY THIS FILE! It was generated by help2man 1.37.1.
-.TH LZIP "1" "February 2012" "Lzip 1.13" "User Commands"
+.TH LZIP "1" "February 2013" "Lzip 1.14" "User Commands"
.SH NAME
Lzip \- reduces the size of files
.SH SYNOPSIS
@@ -76,7 +76,7 @@ Report bugs to lzip\-bug@nongnu.org
.br
Lzip home page: http://www.nongnu.org/lzip/lzip.html
.SH COPYRIGHT
-Copyright \(co 2012 Antonio Diaz Diaz.
+Copyright \(co 2013 Antonio Diaz Diaz.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
.br
This is free software: you are free to change and redistribute it.
diff --git a/doc/lzip.info b/doc/lzip.info
index 9379eb3..e61550e 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.13, 24 February 2012).
+This manual is for Lzip (version 1.14, 17 February 2013).
* Menu:
@@ -24,7 +24,7 @@ This manual is for Lzip (version 1.13, 24 February 2012).
* Concept Index:: Index of concepts
- Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+ Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This manual is free documentation: you have unlimited permission to
copy, distribute and modify it.
@@ -67,12 +67,16 @@ split the compressed output in volumes of a given size, even when
reading from standard input. This allows the direct creation of
multivolume compressed tar archives.
- The amount of memory required for compression is about 5 MiB plus 1
-or 2 times the dictionary size limit (1 if input file size is less than
-dictionary size limit, else 2) plus 8 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 only a few tens
-of KiB larger than the dictionary size really used.
+ 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).
+
+ 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 only a few tens of KiB
+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
@@ -325,7 +329,12 @@ File: lzip.info, Node: File Format, Next: Examples, Prev: Invoking Lzip, Up:
4 File Format
*************
-In the diagram below, a box like this:
+Perfection is reached, not when there is no longer anything to add, but
+when there is no longer anything to take away.
+-- Antoine de Saint-Exupery
+
+
+ In the diagram below, a box like this:
+---+
| | <-- the vertical bars might be missing
+---+
@@ -354,15 +363,18 @@ additional information before, between, or after them.
"LZIP".
`VN (version number, 1 byte)'
- Just in case something needs to be modified in the future. Valid
- values are 0 and 1. Version 0 files are deprecated. They can
- contain only one member and lack the `Member size' field.
+ Just in case something needs to be modified in the future. 1 for
+ now.
`DS (coded dictionary size, 1 byte)'
- Bits 4-0 contain the base 2 logarithm of the base dictionary size.
- Bits 7-5 contain the number of "wedges" to substract from the base
- dictionary size to obtain the dictionary size. The size of a wedge
- is (base dictionary size / 16).
+ Lzip divides the distance between any two powers of 2 into 8
+ equally spaced intervals, named "wedges". The dictionary size is
+ calculated by taking a power of 2 (the base size) and substracting
+ from it a number of 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.
Valid values for dictionary size range from 4KiB to 512MiB.
`Lzma stream'
@@ -376,9 +388,9 @@ additional information before, between, or after them.
Size of the uncompressed original data.
`Member size (8 bytes)'
- Total size of the member, including header and trailer. This
- facilitates safe recovery of undamaged members from multi-member
- files.
+ Total size of the member, including header and trailer. This field
+ acts as a distributed index, and facilitates safe recovery of
+ undamaged members from multi-member files.

@@ -493,13 +505,13 @@ Concept Index

Tag Table:
Node: Top224
-Node: Introduction919
-Node: Algorithm4420
-Node: Invoking Lzip6938
-Node: File Format12290
-Node: Examples14283
-Node: Problems16230
-Node: Concept Index16752
+Node: Introduction925
+Node: Algorithm4590
+Node: Invoking Lzip7108
+Node: File Format12460
+Node: Examples14767
+Node: Problems16714
+Node: Concept Index17236

End Tag Table
diff --git a/doc/lzip.texinfo b/doc/lzip.texinfo
index 0ebc9ca..76ccfc9 100644
--- a/doc/lzip.texinfo
+++ b/doc/lzip.texinfo
@@ -6,8 +6,8 @@
@finalout
@c %**end of header
-@set UPDATED 24 February 2012
-@set VERSION 1.13
+@set UPDATED 17 February 2013
+@set VERSION 1.14
@dircategory Data Compression
@direntry
@@ -45,7 +45,8 @@ This manual is for Lzip (version @value{VERSION}, @value{UPDATED}).
@end menu
@sp 1
-Copyright @copyright{} 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+Copyright @copyright{} 2008, 2009, 2010, 2011, 2012, 2013
+Antonio Diaz Diaz.
This manual is free documentation: you have unlimited permission
to copy, distribute and modify it.
@@ -87,12 +88,16 @@ split the compressed output in volumes of a given size, even when
reading from standard input. This allows the direct creation of
multivolume compressed tar archives.
-The amount of memory required for compression is about 5 MiB plus 1 or 2
-times the dictionary size limit (1 if input file size is less than
-dictionary size limit, else 2) plus 8 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 only a few tens
-of KiB larger than the dictionary size really used.
+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).
+
+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 only a few tens of KiB 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
@@ -348,6 +353,11 @@ Table of SI and binary prefixes (unit multipliers):
@chapter File Format
@cindex file format
+Perfection is reached, not when there is no longer anything to add, but
+when there is no longer anything to take away.@*
+--- Antoine de Saint-Exupery
+
+@sp 1
In the diagram below, a box like this:
@verbatim
+---+
@@ -383,15 +393,16 @@ All multibyte values are stored in little endian order.
A four byte string, identifying the lzip format, with the value "LZIP".
@item VN (version number, 1 byte)
-Just in case something needs to be modified in the future. Valid values
-are 0 and 1. Version 0 files are deprecated. They can contain only one
-member and lack the @samp{Member size} field.
+Just in case something needs to be modified in the future. 1 for now.
@item DS (coded dictionary size, 1 byte)
-Bits 4-0 contain the base 2 logarithm of the base dictionary size.@*
-Bits 7-5 contain the number of "wedges" to substract from the base
-dictionary size to obtain the dictionary size. The size of a wedge is
-(base dictionary size / 16).@*
+Lzip divides the distance between any two powers of 2 into 8 equally
+spaced intervals, named "wedges". The dictionary size is calculated by
+taking a power of 2 (the base size) and substracting from it a number of
+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.@*
Valid values for dictionary size range from 4KiB to 512MiB.
@item Lzma stream
@@ -405,8 +416,9 @@ CRC of the uncompressed original data.
Size of the uncompressed original data.
@item Member size (8 bytes)
-Total size of the member, including header and trailer. This facilitates
-safe recovery of undamaged members from multi-member files.
+Total size of the member, including header and trailer. This field acts
+as a distributed index, and facilitates safe recovery of undamaged
+members from multi-member files.
@end table
@@ -419,8 +431,8 @@ WARNING! Even if lzip is bug-free, other causes may result in a corrupt
compressed file (bugs in the system libraries, memory errors, etc).
Therefore, if the data you are going to compress is important, give the
@samp{--keep} option to lzip and do not remove the original file until
-you verify the compressed file with a command like @w{@samp{lzip -cd
-file.lz | cmp file -}}.
+you verify the compressed file with a command like
+@w{@samp{lzip -cd file.lz | cmp file -}}.
@sp 1
@noindent
diff --git a/encoder.cc b/encoder.cc
index 56820b5..2e00c3d 100644
--- a/encoder.cc
+++ b/encoder.cc
@@ -1,5 +1,5 @@
/* Lzip - Data compressor based on the LZMA algorithm
- Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+ Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -69,45 +69,51 @@ void Matchfinder_base::normalize_pos()
Matchfinder_base::Matchfinder_base( const int before, const int dict_size,
- const int dict_factor, const int len_limit,
- const int num_prev_pos, const int ifd,
- const int pos_array_factor )
+ const int after_size, const int dict_factor,
+ const int match_len_limit, const int num_prev_positions23,
+ const int pos_array_factor, const int ifd )
:
partial_data_pos( 0 ),
- prev_positions( new int32_t[num_prev_pos] ),
- num_prev_positions( num_prev_pos ),
before_size( before ),
- match_len_limit_( len_limit ),
- infd( ifd ),
+ match_len_limit_( match_len_limit ),
pos( 0 ),
cyclic_pos( 0 ),
stream_pos( 0 ),
+ infd( ifd ),
at_stream_end( false )
{
- for( int i = 0; i < num_prev_positions; ++i ) prev_positions[i] = -1;
const int buffer_size_limit =
- ( dict_size * dict_factor ) + before_size + after_size;
+ ( dict_factor * dict_size ) + before_size + after_size;
buffer_size = std::max( 65536, dict_size );
buffer = (uint8_t *)std::malloc( buffer_size );
- if( !buffer ) { delete[] prev_positions; throw std::bad_alloc(); }
+ if( !buffer ) throw std::bad_alloc();
if( read_block() && !at_stream_end && buffer_size < buffer_size_limit )
{
buffer_size = buffer_size_limit;
uint8_t * const tmp = (uint8_t *)std::realloc( buffer, buffer_size );
- if( !tmp )
- { std::free( buffer ); delete[] prev_positions; throw std::bad_alloc(); }
+ if( !tmp ) { std::free( buffer ); throw std::bad_alloc(); }
buffer = tmp;
read_block();
}
if( at_stream_end && stream_pos < dict_size )
dictionary_size_ = std::max( (int)min_dictionary_size, stream_pos );
- else dictionary_size_ = dict_size;
+ else
+ dictionary_size_ = dict_size;
pos_limit = buffer_size;
if( !at_stream_end ) pos_limit -= after_size;
- pos_array_size = pos_array_factor * dictionary_size_;
- pos_array = new( std::nothrow ) int32_t[pos_array_size];
- if( !pos_array )
- { std::free( buffer ); delete[] prev_positions; throw std::bad_alloc(); }
+ int size = 1 << std::max( 16, real_bits( dictionary_size_ - 1 ) - 2 );
+ if( dictionary_size_ > 1 << 26 )
+ size >>= 1;
+ key4_mask = size - 1;
+ size += num_prev_positions23;
+
+ num_prev_positions = size;
+ pos_array_size = pos_array_factor * ( dictionary_size_ + 1 );
+ size += pos_array_size;
+ prev_positions = new( std::nothrow ) int32_t[size];
+ if( !prev_positions ) { std::free( buffer ); throw std::bad_alloc(); }
+ pos_array = prev_positions + num_prev_positions;
+ for( int i = 0; i < num_prev_positions; ++i ) prev_positions[i] = -1;
}
@@ -124,7 +130,7 @@ void Matchfinder_base::reset()
}
-int Matchfinder::longest_match_len( int * const distances )
+int Matchfinder::get_match_pairs( struct Pair * pairs )
{
int len_limit = match_len_limit_;
if( len_limit > available_bytes() )
@@ -134,28 +140,44 @@ int Matchfinder::longest_match_len( int * const distances )
}
int maxlen = min_match_len - 1;
- const int min_pos = (pos >= dictionary_size_) ?
- (pos - dictionary_size_ + 1) : 0;
+ int num_pairs = 0;
+ const int min_pos = (pos > dictionary_size_) ?
+ pos - dictionary_size_ : 0;
const uint8_t * const data = buffer + pos;
- const int key2 = num_prev_positions4 + num_prev_positions3 +
- ( ( (int)data[0] << 8 ) | data[1] );
- const uint32_t tmp = crc32[data[0]] ^ data[1] ^ ( (uint32_t)data[2] << 8 );
- const int key3 = num_prev_positions4 +
- (int)( tmp & ( num_prev_positions3 - 1 ) );
- const int key4 = (int)( ( tmp ^ ( crc32[data[3]] << 5 ) ) &
- ( num_prev_positions4 - 1 ) );
-
- if( distances )
+
+ unsigned tmp = crc32[data[0]] ^ data[1];
+ const int key2 = tmp & ( num_prev_positions2 - 1 );
+ tmp ^= (uint32_t)data[2] << 8;
+ const int key3 = num_prev_positions2 + ( tmp & ( num_prev_positions3 - 1 ) );
+ const int key4 = num_prev_positions2 + num_prev_positions3 +
+ ( ( tmp ^ ( crc32[data[3]] << 5 ) ) & key4_mask );
+
+ if( pairs )
{
- int np = prev_positions[key2];
- if( np >= min_pos )
- { distances[2] = pos - np - 1; maxlen = 2; }
- else distances[2] = 0x7FFFFFFF;
- np = prev_positions[key3];
- if( np >= min_pos && buffer[np] == data[0] )
- { distances[3] = pos - np - 1; maxlen = 3; }
- else distances[3] = 0x7FFFFFFF;
- distances[4] = 0x7FFFFFFF;
+ int np2 = prev_positions[key2];
+ int np3 = prev_positions[key3];
+ if( np2 >= min_pos && buffer[np2] == data[0] )
+ {
+ pairs[0].dis = pos - np2 - 1;
+ pairs[0].len = maxlen = 2;
+ num_pairs = 1;
+ }
+ if( np2 != np3 && np3 >= min_pos && buffer[np3] == data[0] )
+ {
+ maxlen = 3;
+ pairs[num_pairs].dis = pos - np3 - 1;
+ ++num_pairs;
+ np2 = np3;
+ }
+ if( num_pairs > 0 )
+ {
+ const int delta = pos - np2;
+ while( maxlen < len_limit && data[maxlen-delta] == data[maxlen] )
+ ++maxlen;
+ pairs[num_pairs-1].len = maxlen;
+ if( maxlen >= len_limit ) pairs = 0;
+ }
+ if( maxlen < 3 ) maxlen = 3;
}
prev_positions[key2] = pos;
@@ -170,46 +192,43 @@ int Matchfinder::longest_match_len( int * const distances )
for( int count = cycles; ; )
{
if( newpos < min_pos || --count < 0 ) { *ptr0 = *ptr1 = -1; break; }
- const uint8_t * const newdata = buffer + newpos;
- while( len < len_limit && newdata[len] == data[len] ) ++len;
const int delta = pos - newpos;
- if( distances ) while( maxlen < len ) distances[++maxlen] = delta - 1;
-
int32_t * const newptr = pos_array +
( ( cyclic_pos - delta +
- ( ( cyclic_pos >= delta ) ? 0 : dictionary_size_ ) ) << 1 );
-
- if( len < len_limit )
+ ( ( cyclic_pos >= delta ) ? 0 : dictionary_size_ + 1 ) ) << 1 );
+ if( data[len-delta] == data[len] )
{
- if( newdata[len] < data[len] )
+ while( ++len < len_limit && data[len-delta] == data[len] ) {}
+ if( pairs && maxlen < len )
{
- *ptr0 = newpos;
- ptr0 = newptr + 1;
- newpos = *ptr0;
- len0 = len; if( len1 < len ) len = len1;
+ pairs[num_pairs].dis = delta - 1;
+ pairs[num_pairs].len = maxlen = len;
+ ++num_pairs;
}
- else
+ if( len >= len_limit )
{
- *ptr1 = newpos;
- ptr1 = newptr;
- newpos = *ptr1;
- len1 = len; if( len0 < len ) len = len0;
+ *ptr0 = newptr[0];
+ *ptr1 = newptr[1];
+ break;
}
}
+ if( data[len-delta] < data[len] )
+ {
+ *ptr0 = newpos;
+ ptr0 = newptr + 1;
+ newpos = *ptr0;
+ len0 = len; if( len1 < len ) len = len1;
+ }
else
{
- *ptr0 = newptr[0];
- *ptr1 = newptr[1];
- break;
+ *ptr1 = newpos;
+ ptr1 = newptr;
+ newpos = *ptr1;
+ len1 = len; if( len0 < len ) len = len0;
}
}
- if( distances )
- {
- if( distances[3] > distances[4] ) distances[3] = distances[4];
- if( distances[2] > distances[3] ) distances[2] = distances[3];
- }
- return maxlen;
+ return num_pairs;
}
@@ -240,12 +259,14 @@ void Len_encoder::encode( Range_encoder & range_encoder, int symbol,
if( symbol < len_low_symbols + len_mid_symbols )
{
range_encoder.encode_bit( choice2, 0 );
- range_encoder.encode_tree( bm_mid[pos_state], symbol - len_low_symbols, len_mid_bits );
+ range_encoder.encode_tree( bm_mid[pos_state], symbol - len_low_symbols,
+ len_mid_bits );
}
else
{
range_encoder.encode_bit( choice2, 1 );
- range_encoder.encode_tree( bm_high, symbol - len_low_symbols - len_mid_symbols, len_high_bits );
+ range_encoder.encode_tree( bm_high, symbol - len_low_symbols - len_mid_symbols,
+ len_high_bits );
}
}
if( --counters[pos_state] <= 0 ) update_prices( pos_state );
@@ -253,7 +274,7 @@ void Len_encoder::encode( Range_encoder & range_encoder, int symbol,
// End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len)
-void LZ_encoder_base::full_flush( const long long data_position,
+void LZ_encoder_base::full_flush( const unsigned long long data_position,
const State state )
{
const int pos_state = data_position & pos_state_mask;
@@ -283,11 +304,11 @@ void LZ_encoder::fill_distance_prices()
{
for( int dis = start_dis_model; dis < modeled_distances; ++dis )
{
- const int dis_slot = dis_slots.table( dis );
+ const int dis_slot = dis_slots[dis];
const int direct_bits = ( dis_slot >> 1 ) - 1;
const int base = ( 2 | ( dis_slot & 1 ) ) << direct_bits;
- const int price =
- price_symbol_reversed( bm_dis + base - dis_slot, dis - base, direct_bits );
+ const int price = price_symbol_reversed( bm_dis + base - dis_slot - 1,
+ dis - base, direct_bits );
for( int dis_state = 0; dis_state < max_dis_states; ++dis_state )
dis_prices[dis_state][dis] = price;
}
@@ -301,14 +322,14 @@ void LZ_encoder::fill_distance_prices()
dsp[slot] = price_symbol( bmds, slot, dis_slot_bits );
for( ; slot < num_dis_slots; ++slot )
dsp[slot] = price_symbol( bmds, slot, dis_slot_bits ) +
- (((( slot >> 1 ) - 1 ) - dis_align_bits ) << price_shift );
+ (((( slot >> 1 ) - 1 ) - dis_align_bits ) << price_shift_bits );
int * const dp = dis_prices[dis_state];
int dis = 0;
for( ; dis < start_dis_model; ++dis )
dp[dis] = dsp[dis];
for( ; dis < modeled_distances; ++dis )
- dp[dis] += dsp[dis_slots.table( dis )];
+ dp[dis] += dsp[dis_slots[dis]];
}
}
@@ -316,16 +337,20 @@ void LZ_encoder::fill_distance_prices()
// Return value == number of bytes advanced (ahead).
// trials[0]..trials[retval-1] contain the steps to encode.
// ( trials[0].dis == -1 && trials[0].price == 1 ) means literal.
+//
int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances],
const State state )
{
- int main_len;
- if( longest_match_found > 0 ) // from previous call
+ int num_pairs, num_trials;
+
+ if( pending_num_pairs > 0 ) // from previous call
{
- main_len = longest_match_found;
- longest_match_found = 0;
+ num_pairs = pending_num_pairs;
+ pending_num_pairs = 0;
}
- else main_len = read_match_distances();
+ else
+ num_pairs = read_match_distances();
+ const int main_len = ( num_pairs > 0 ) ? pairs[num_pairs-1].len : 0;
int replens[num_rep_distances];
int rep_index = 0;
@@ -344,36 +369,34 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances],
if( main_len >= matchfinder.match_len_limit() )
{
- trials[0].dis = match_distances[matchfinder.match_len_limit()] +
- num_rep_distances;
+ trials[0].dis = pairs[num_pairs-1].dis + num_rep_distances;
trials[0].price = main_len;
move_pos( main_len );
return main_len;
}
- {
const int pos_state = matchfinder.data_position() & pos_state_mask;
const uint8_t prev_byte = matchfinder[-1];
const uint8_t cur_byte = matchfinder[0];
const uint8_t match_byte = matchfinder[-reps[0]-1];
trials[0].state = state;
- for( int i = 0; i < num_rep_distances; ++i ) trials[0].reps[i] = reps[i];
trials[1].dis = -1;
- trials[1].prev_index = 0;
trials[1].price = price0( bm_match[state()][pos_state] );
if( state.is_char() )
- trials[1].price += literal_encoder.price_symbol( prev_byte, cur_byte );
+ trials[1].price += price_literal( prev_byte, cur_byte );
else
- trials[1].price += literal_encoder.price_matched( prev_byte, cur_byte, match_byte );
+ trials[1].price += price_matched( prev_byte, cur_byte, match_byte );
const int match_price = price1( bm_match[state()][pos_state] );
const int rep_match_price = match_price + price1( bm_rep[state()] );
if( match_byte == cur_byte )
- trials[1].update( 0, 0, rep_match_price + price_rep_len1( pos_state, state ) );
+ trials[1].update( rep_match_price + price_rep_len1( state, pos_state ), 0, 0 );
- if( main_len < min_match_len )
+ num_trials = std::max( main_len, replens[rep_index] );
+
+ if( num_trials < min_match_len )
{
trials[0].dis = trials[1].dis;
trials[0].price = 1;
@@ -381,71 +404,107 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances],
return 1;
}
- if( main_len <= replens[rep_index] )
+ for( int i = 0; i < num_rep_distances; ++i ) trials[0].reps[i] = reps[i];
+ trials[1].prev_index = 0;
+ trials[1].prev_index2 = single_step_trial;
+
+ for( int len = min_match_len; len <= num_trials; ++len )
+ trials[len].price = infinite_price;
+
+ for( int rep = 0; rep < num_rep_distances; ++rep )
{
- main_len = replens[rep_index];
- for( int len = min_match_len; len <= main_len; ++len )
- trials[len].price = infinite_price;
+ 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_match_len_encoder.price( len, pos_state ),
+ rep, 0 );
}
- else
+
+ if( main_len > replens[0] )
{
const int normal_match_price = match_price + price0( bm_rep[state()] );
- for( int len = min_match_len; len <= main_len; ++len )
+ int i = 0, len = std::max( replens[0] + 1, (int)min_match_len );
+ while( len > pairs[i].len ) ++i;
+ while( true )
{
- trials[len].dis = match_distances[len] + num_rep_distances;
- trials[len].prev_index = 0;
- trials[len].price = normal_match_price +
- price_pair( match_distances[len], len, pos_state );
+ const int dis = pairs[i].dis;
+ trials[len].update( normal_match_price + price_pair( dis, len, pos_state ),
+ dis + num_rep_distances, 0 );
+ if( ++len > pairs[i].len && ++i >= num_pairs ) break;
}
}
- for( int rep = 0; rep < num_rep_distances; ++rep )
- {
- const int price = rep_match_price + price_rep( rep, pos_state, state );
- for( int len = min_match_len; len <= replens[rep]; ++len )
- trials[len].update( rep, 0, price +
- rep_match_len_encoder.price( len, pos_state ) );
- }
- }
-
int cur = 0;
- int num_trials = main_len;
matchfinder.move_pos();
- while( true )
+ while( true ) // price optimization loop
{
if( ++cur >= num_trials ) // no more initialized trials
{
backward( cur );
return cur;
}
- const int newlen = read_match_distances();
+
+ const int num_pairs = read_match_distances();
+ const int newlen = ( num_pairs > 0 ) ? pairs[num_pairs-1].len : 0;
if( newlen >= matchfinder.match_len_limit() )
{
- longest_match_found = newlen;
+ pending_num_pairs = num_pairs;
backward( cur );
return cur;
}
+ // give final values to current trial
Trial & cur_trial = trials[cur];
- const int prev_index = cur_trial.prev_index;
-
- cur_trial.state = trials[prev_index].state;
+ int prev_index = cur_trial.prev_index;
+ const int prev_index2 = cur_trial.prev_index2;
+ State cur_state;
- for( int i = 0; i < num_rep_distances; ++i )
- cur_trial.reps[i] = trials[prev_index].reps[i];
+ if( prev_index2 != single_step_trial )
+ {
+ --prev_index;
+ if( prev_index2 >= 0 )
+ {
+ cur_state = trials[prev_index2].state;
+ if( cur_trial.dis2 < num_rep_distances )
+ cur_state.set_rep();
+ else
+ cur_state.set_match();
+ }
+ else
+ cur_state = trials[prev_index].state;
+ cur_state.set_char();
+ }
+ else
+ cur_state = trials[prev_index].state;
if( prev_index == cur - 1 )
{
- if( cur_trial.dis == 0 ) cur_trial.state.set_short_rep();
- else cur_trial.state.set_char();
+ if( cur_trial.dis == 0 ) cur_state.set_short_rep();
+ else cur_state.set_char();
+ for( int i = 0; i < num_rep_distances; ++i )
+ cur_trial.reps[i] = trials[prev_index].reps[i];
}
else
{
- if( cur_trial.dis < num_rep_distances ) cur_trial.state.set_rep();
- else cur_trial.state.set_match();
- mtf_reps( cur_trial.dis, cur_trial.reps );
+ int dis;
+ if( prev_index2 >= 0 )
+ {
+ dis = cur_trial.dis2;
+ prev_index = prev_index2;
+ cur_state.set_rep();
+ }
+ else
+ {
+ dis = cur_trial.dis;
+ if( dis < num_rep_distances ) cur_state.set_rep();
+ else cur_state.set_match();
+ }
+ for( int i = 0; i < num_rep_distances; ++i )
+ cur_trial.reps[i] = trials[prev_index].reps[i];
+ mtf_reps( dis, cur_trial.reps );
}
+ cur_trial.state = cur_state;
const int pos_state = matchfinder.data_position() & pos_state_mask;
const uint8_t prev_byte = matchfinder[-1];
@@ -453,85 +512,168 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances],
const uint8_t match_byte = matchfinder[-cur_trial.reps[0]-1];
int next_price = cur_trial.price +
- price0( bm_match[cur_trial.state()][pos_state] );
- if( cur_trial.state.is_char() )
- next_price += literal_encoder.price_symbol( prev_byte, cur_byte );
+ price0( bm_match[cur_state()][pos_state] );
+ if( cur_state.is_char() )
+ next_price += price_literal( prev_byte, cur_byte );
else
- next_price += literal_encoder.price_matched( prev_byte, cur_byte, match_byte );
+ next_price += price_matched( prev_byte, cur_byte, match_byte );
matchfinder.move_pos();
+ // try last updates to next trial
Trial & next_trial = trials[cur+1];
- next_trial.update( -1, cur, next_price );
+ next_trial.update( next_price, -1, cur );
- const int match_price = cur_trial.price + price1( bm_match[cur_trial.state()][pos_state] );
- const int rep_match_price = match_price + price1( bm_rep[cur_trial.state()] );
+ const int match_price = cur_trial.price + price1( bm_match[cur_state()][pos_state] );
+ const int rep_match_price = match_price + price1( bm_rep[cur_state()] );
if( match_byte == cur_byte && next_trial.dis != 0 )
- next_trial.update( 0, cur, rep_match_price +
- price_rep_len1( pos_state, cur_trial.state ) );
+ {
+ const int price = rep_match_price +
+ price_rep_len1( cur_state, pos_state );
+ if( price <= next_trial.price )
+ {
+ next_trial.price = price;
+ next_trial.dis = 0;
+ next_trial.prev_index = cur;
+ next_trial.prev_index2 = single_step_trial;
+ }
+ }
- const int len_limit = std::min( std::min( max_num_trials - 1 - cur,
- matchfinder.available_bytes() ), matchfinder.match_len_limit() );
- if( len_limit < min_match_len ) continue;
+ const int available_bytes = std::min( matchfinder.available_bytes() + 1,
+ max_num_trials - 1 - cur );
+ if( available_bytes < min_match_len ) continue;
- for( int rep = 0; rep < num_rep_distances; ++rep )
+ const int len_limit = std::min( matchfinder.match_len_limit(),
+ available_bytes );
+
+ // try literal + rep0
+ if( match_byte != cur_byte && next_trial.prev_index != cur )
{
- const int dis = cur_trial.reps[rep] + 1;
- int len = 0;
const uint8_t * const data = matchfinder.ptr_to_current_pos() - 1;
- while( len < len_limit && data[len] == data[len-dis] ) ++len;
- if( len >= min_match_len )
+ const int dis = cur_trial.reps[0] + 1;
+ const int limit = std::min( matchfinder.match_len_limit() + 1,
+ available_bytes );
+ int len = 1;
+ while( len < limit && data[len-dis] == data[len] ) ++len;
+ if( --len >= min_match_len )
{
- const int price = rep_match_price +
- price_rep( rep, pos_state, cur_trial.state );
- while( num_trials < cur + len )
+ const int pos_state2 = ( pos_state + 1 ) & pos_state_mask;
+ State state2 = cur_state; state2.set_char();
+ const int price = next_price +
+ price1( bm_match[state2()][pos_state2] ) +
+ price1( bm_rep[state2()] ) +
+ price_rep0_len( len, state2, pos_state2 );
+ while( num_trials < cur + 1 + len )
trials[++num_trials].price = infinite_price;
- for( ; len >= min_match_len; --len )
- trials[cur+len].update( rep, cur, price +
- rep_match_len_encoder.price( len, pos_state ) );
+ trials[cur+1+len].update2( price, 0, cur + 1 );
}
}
- if( newlen <= len_limit &&
- ( newlen > min_match_len ||
- ( newlen == min_match_len &&
- match_distances[min_match_len] < modeled_distances ) ) )
+ int start_len = min_match_len;
+
+ // try rep distances
+ for( int rep = 0; rep < num_rep_distances; ++rep )
+ {
+ const uint8_t * const data = matchfinder.ptr_to_current_pos() - 1;
+ int len;
+ const int dis = cur_trial.reps[rep] + 1;
+
+ if( data[-dis] != data[0] || data[1-dis] != data[1] ) continue;
+ for( len = min_match_len; len < len_limit; ++len )
+ if( data[len-dis] != data[len] ) break;
+ while( num_trials < cur + len )
+ 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_match_len_encoder.price( i, pos_state ),
+ rep, cur );
+
+ if( rep == 0 ) start_len = len + 1; // discard shorter matches
+
+ // try rep + literal + rep0
+ int len2 = len + 1;
+ const int limit = std::min( matchfinder.match_len_limit() + len2,
+ available_bytes );
+ while( len2 < limit && data[len2-dis] == data[len2] ) ++len2;
+ len2 -= len + 1;
+ if( len2 < min_match_len ) continue;
+
+ int pos_state2 = ( pos_state + len ) & pos_state_mask;
+ State state2 = cur_state; state2.set_rep();
+ price += rep_match_len_encoder.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;
+ state2.set_char();
+ price += price1( bm_match[state2()][pos_state2] ) +
+ price1( bm_rep[state2()] ) +
+ price_rep0_len( len2, state2, pos_state2 );
+ while( num_trials < cur + len + 1 + len2 )
+ trials[++num_trials].price = infinite_price;
+ trials[cur+len+1+len2].update3( price, 0, cur + len + 1, rep, cur );
+ }
+
+ // try matches
+ if( newlen >= start_len && newlen <= len_limit )
{
const int normal_match_price = match_price +
- price0( bm_rep[cur_trial.state()] );
+ price0( bm_rep[cur_state()] );
+
while( num_trials < cur + newlen )
trials[++num_trials].price = infinite_price;
- int dis = match_distances[min_match_len];
- int dis_state = get_dis_state( min_match_len );
- int dis_price = infinite_price;
- if( dis < modeled_distances )
- trials[cur+min_match_len].update( dis + num_rep_distances, cur,
- normal_match_price + dis_prices[dis_state][dis] +
- len_encoder.price( min_match_len, pos_state ) );
- for( int len = min_match_len + 1; len <= newlen; ++len )
+ int i = 0;
+ while( start_len > pairs[i].len ) ++i;
+ int dis = pairs[i].dis;
+ for( int len = start_len; ; ++len )
{
- if( dis != match_distances[len] || dis_state < max_dis_states - 1 )
+ int price = normal_match_price + price_pair( dis, len, pos_state );
+
+ trials[cur+len].update( price, dis + num_rep_distances, cur );
+
+ // try match + literal + rep0
+ if( len == pairs[i].len )
{
- dis = match_distances[len];
- dis_state = get_dis_state( len );
- dis_price = price_dis( dis, dis_state );
+ const uint8_t * const data = matchfinder.ptr_to_current_pos() - 1;
+ const int dis2 = dis + 1;
+ int len2 = len + 1;
+ const int limit = std::min( matchfinder.match_len_limit() + len2,
+ available_bytes );
+ while( len2 < limit && data[len2-dis2] == data[len2] ) ++len2;
+ len2 -= len + 1;
+ if( len2 >= min_match_len )
+ {
+ int pos_state2 = ( pos_state + len ) & pos_state_mask;
+ State state2 = cur_state; state2.set_match();
+ price += price0( bm_match[state2()][pos_state2] ) +
+ price_matched( data[len-1], data[len], data[len-dis2] );
+ pos_state2 = ( pos_state2 + 1 ) & pos_state_mask;
+ state2.set_char();
+ price += price1( bm_match[state2()][pos_state2] ) +
+ price1( bm_rep[state2()] ) +
+ price_rep0_len( len2, state2, pos_state2 );
+
+ while( num_trials < cur + len + 1 + len2 )
+ trials[++num_trials].price = infinite_price;
+ trials[cur+len+1+len2].update3( price, 0, cur + len + 1,
+ dis + num_rep_distances, cur );
+ }
+ if( ++i >= num_pairs ) break;
+ dis = pairs[i].dis;
}
- trials[cur+len].update( dis + num_rep_distances, cur,
- normal_match_price + dis_price +
- len_encoder.price( len, pos_state ) );
}
}
}
}
-bool LZ_encoder::encode_member( const long long member_size )
+bool LZ_encoder::encode_member( const unsigned long long member_size )
{
- const long long member_size_limit =
+ const unsigned long long member_size_limit =
member_size - File_trailer::size() - max_marker_size;
- const int fill_count = ( matchfinder.match_len_limit() > 12 ) ? 512 : 2048;
+ const int fill_count = ( matchfinder.match_len_limit() > 12 ) ? 128 : 512;
int fill_counter = 0;
int rep_distances[num_rep_distances];
State state;
@@ -546,20 +688,23 @@ bool LZ_encoder::encode_member( const long long member_size )
const uint8_t prev_byte = 0;
const uint8_t cur_byte = matchfinder[0];
range_encoder.encode_bit( bm_match[state()][0], 0 );
- literal_encoder.encode( range_encoder, prev_byte, cur_byte );
+ encode_literal( prev_byte, cur_byte );
crc32.update( crc_, cur_byte );
- matchfinder.longest_match_len();
+ matchfinder.get_match_pairs();
matchfinder.move_pos();
}
while( !matchfinder.finished() )
{
- if( fill_counter <= 0 )
- { fill_distance_prices(); fill_counter = fill_count; }
+ if( pending_num_pairs == 0 )
+ {
+ if( fill_counter <= 0 )
+ { fill_distance_prices(); fill_counter = fill_count; }
+ if( align_price_count <= 0 ) fill_align_prices();
+ }
int ahead = sequence_optimizer( rep_distances, state );
if( ahead <= 0 ) return false; // can't happen
- fill_counter -= ahead;
for( int i = 0; ; )
{
@@ -576,12 +721,11 @@ bool LZ_encoder::encode_member( const long long member_size )
const uint8_t cur_byte = matchfinder[-ahead];
crc32.update( crc_, cur_byte );
if( state.is_char() )
- literal_encoder.encode( range_encoder, prev_byte, cur_byte );
+ encode_literal( prev_byte, cur_byte );
else
{
const uint8_t match_byte = matchfinder[-ahead-rep_distances[0]-1];
- literal_encoder.encode_matched( range_encoder,
- prev_byte, cur_byte, match_byte );
+ encode_matched( prev_byte, cur_byte, match_byte );
}
state.set_char();
}
@@ -613,9 +757,9 @@ bool LZ_encoder::encode_member( const long long member_size )
else
{
encode_pair( dis - num_rep_distances, len, pos_state );
- if( dis_slots[dis - num_rep_distances] >= end_dis_model &&
- --align_price_count <= 0 )
- fill_align_prices();
+ if( get_slot( dis - num_rep_distances ) >= end_dis_model )
+ --align_price_count;
+ --fill_counter;
state.set_match();
}
}
diff --git a/encoder.h b/encoder.h
index 75250ca..da83a3c 100644
--- a/encoder.h
+++ b/encoder.h
@@ -1,5 +1,5 @@
/* Lzip - Data compressor based on the LZMA algorithm
- Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+ Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -16,17 +16,19 @@
*/
enum { max_num_trials = 1 << 12,
- price_shift = 6 };
+ price_shift_bits = 6,
+ price_step_bits = 2,
+ price_step = 1 << price_step_bits };
class Dis_slots
{
- unsigned char data[1<<12];
+ uint8_t data[1<<10];
public:
void init()
{
for( int slot = 0; slot < 4; ++slot ) data[slot] = slot;
- for( int i = 4, size = 2, slot = 4; slot < 24; slot += 2 )
+ for( int i = 4, size = 2, slot = 4; slot < 20; slot += 2 )
{
std::memset( &data[i], slot, size );
std::memset( &data[i+size], slot + 1, size );
@@ -35,51 +37,57 @@ public:
}
}
- unsigned char table( const int dis ) const { return data[dis]; }
-
- int operator[]( const uint32_t dis ) const
- {
- if( dis < (1 << 12) ) return data[dis];
- if( dis < (1 << 23) ) return data[dis>>11] + 22;
- return data[dis>>22] + 44;
- }
+ uint8_t operator[]( const int dis ) const { return data[dis]; }
};
extern Dis_slots dis_slots;
+static inline uint8_t get_slot( const uint32_t dis )
+ {
+ if( dis < (1 << 10) ) return dis_slots[dis];
+ if( dis < (1 << 19) ) return dis_slots[dis>> 9] + 18;
+ if( dis < (1 << 28) ) return dis_slots[dis>>18] + 36;
+ return dis_slots[dis>>27] + 54;
+ }
+
class Prob_prices
{
- int data[bit_model_total >> 2];
+ short data[bit_model_total >> price_step_bits];
public:
void init()
{
- const int num_bits = ( bit_model_total_bits - 2 );
- int j = 1, end = 2;
- data[0] = bit_model_total_bits << price_shift;
- for( int i = num_bits - 1; i >= 0; --i, end <<= 1 )
+ for( int i = price_step / 2; i < bit_model_total; i += price_step )
{
- for( ; j < end; ++j )
- data[j] = ( i << price_shift ) +
- ( ( (end - j) << price_shift ) >> ( num_bits - i - 1 ) );
+ unsigned val = i;
+ 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;
}
}
int operator[]( const int probability ) const
- { return data[probability >> 2]; }
+ { return data[probability >> price_step_bits]; }
};
extern Prob_prices prob_prices;
-inline int price0( const Bit_model & bm )
+inline int price0( const Bit_model bm )
{ return prob_prices[bm.probability]; }
-inline int price1( const Bit_model & bm )
- { return prob_prices[bit_model_total-bm.probability]; }
+inline int price1( const Bit_model bm )
+ { return prob_prices[bit_model_total - bm.probability]; }
-inline int price_bit( const Bit_model & bm, const int bit )
+inline int price_bit( const Bit_model bm, const int bit )
{ if( bit ) return price1( bm ); else return price0( bm ); }
@@ -113,29 +121,22 @@ inline int price_symbol_reversed( const Bit_model bm[], int symbol,
}
-inline int price_matched( const Bit_model bm[], const int symbol,
- const int match_byte )
+inline int price_matched( const Bit_model bm[], unsigned symbol,
+ unsigned match_byte )
{
int price = 0;
- int model = 1;
-
- for( int i = 7; i >= 0; --i )
- {
- const int match_bit = ( match_byte >> i ) & 1;
- int bit = ( symbol >> i ) & 1;
- price += price_bit( bm[(match_bit<<8)+model+0x100], bit );
- model = ( model << 1 ) | bit;
- if( match_bit != bit )
- {
- while( --i >= 0 )
- {
- bit = ( symbol >> i ) & 1;
- price += price_bit( bm[model], bit );
- model = ( model << 1 ) | bit;
- }
- break;
- }
+ unsigned mask = 0x100;
+ symbol |= 0x100;
+
+ do {
+ match_byte <<= 1;
+ const unsigned match_bit = match_byte & mask;
+ symbol <<= 1;
+ const unsigned bit = symbol & 0x100;
+ price += price_bit( bm[match_bit+(symbol>>9)+mask], bit );
+ mask &= ~(match_byte ^ symbol); // if( match_bit != bit ) mask = 0;
}
+ while( symbol < 0x10000 );
return price;
}
@@ -149,37 +150,36 @@ class Matchfinder_base
void operator=( const Matchfinder_base & ); // declared as private
protected:
- enum { after_size = max_match_len }; // bytes to keep in buffer after pos
-
- long long partial_data_pos;
- int32_t * const prev_positions; // last seen position of key
- uint8_t * buffer; // input buffer
- int32_t * pos_array; // may be tree or chain
- const int num_prev_positions;
+ unsigned long long partial_data_pos;
+ uint8_t * buffer; // input buffer
+ int32_t * prev_positions; // last seen position of key
+ int32_t * pos_array; // may be tree or chain
const int before_size; // bytes to keep in buffer before dictionary
const int match_len_limit_;
- const int infd; // input file descriptor
int buffer_size;
int dictionary_size_; // bytes to keep in buffer before pos
int pos; // current pos in buffer
- int cyclic_pos; // current pos in dictionary
+ int cyclic_pos; // cycles through [0, dictionary_size]
int pos_limit; // when reached, a new block must be read
int stream_pos; // first byte not yet read from file
+ unsigned key4_mask;
+ int num_prev_positions; // size of prev_positions
int pos_array_size;
+ const int infd; // input file descriptor
bool at_stream_end; // stream_pos shows real end of file
Matchfinder_base( const int before, const int dict_size,
- const int dict_factor, const int len_limit,
- const int num_prev_pos, const int ifd,
- const int pos_array_factor );
+ const int after_size, const int dict_factor,
+ const int match_len_limit, const int num_prev_positions23,
+ const int pos_array_factor, const int ifd );
~Matchfinder_base()
- { delete[] pos_array; std::free( buffer ); delete[] prev_positions; }
+ { delete[] prev_positions; std::free( buffer ); }
public:
uint8_t operator[]( const int i ) const { return buffer[pos+i]; }
int available_bytes() const { return stream_pos - pos; }
- long long data_position() const { return partial_data_pos + pos; }
+ unsigned long long data_position() const { return partial_data_pos + pos; }
int dictionary_size() const { return dictionary_size_; }
bool finished() const { return at_stream_end && pos >= stream_pos; }
int match_len_limit() const { return match_len_limit_; }
@@ -195,34 +195,43 @@ public:
return i;
}
- void reset();
void move_pos()
{
- if( ++cyclic_pos >= dictionary_size_ ) cyclic_pos = 0;
+ if( ++cyclic_pos > dictionary_size_ ) cyclic_pos = 0;
if( ++pos >= pos_limit ) normalize_pos();
}
+
+ void reset();
+ };
+
+
+struct Pair /* distance-length pair */
+ {
+ int dis;
+ int len;
};
class Matchfinder : public Matchfinder_base
{
- enum { before = max_num_trials + 1,
+ enum { before_size = max_num_trials + 1,
+ // bytes to keep in buffer after pos
+ after_size = ( 2 * max_match_len ) + 1,
dict_factor = 2,
- num_prev_positions4 = 1 << 20,
- num_prev_positions3 = 1 << 18,
- num_prev_positions2 = 1 << 16,
- num_prev_pos = num_prev_positions4 + num_prev_positions3 +
- num_prev_positions2,
+ num_prev_positions3 = 1 << 16,
+ num_prev_positions2 = 1 << 10,
+ num_prev_positions23 = num_prev_positions2 + num_prev_positions3,
pos_array_factor = 2 };
const int cycles;
public:
- Matchfinder( const int dict_size, const int len_limit, const int ifd )
+ Matchfinder( const int dict_size, const int match_len_limit, const int ifd )
:
- Matchfinder_base( before, dict_size, dict_factor, len_limit,
- num_prev_pos, ifd, pos_array_factor ),
- cycles( ( len_limit < max_match_len ) ? 16 + ( len_limit / 2 ) : 256 )
+ Matchfinder_base( before_size, dict_size, after_size, dict_factor,
+ match_len_limit, num_prev_positions23, pos_array_factor, ifd ),
+ cycles( ( match_len_limit < max_match_len ) ?
+ 16 + ( match_len_limit / 2 ) : 256 )
{}
bool dec_pos( const int ahead )
@@ -230,11 +239,11 @@ public:
if( ahead < 0 || pos < ahead ) return false;
pos -= ahead;
cyclic_pos -= ahead;
- if( cyclic_pos < 0 ) cyclic_pos += dictionary_size_;
+ if( cyclic_pos < 0 ) cyclic_pos += dictionary_size_ + 1;
return true;
}
- int longest_match_len( int * const distances = 0 );
+ int get_match_pairs( struct Pair * pairs = 0 );
};
@@ -242,7 +251,7 @@ class Range_encoder
{
enum { buffer_size = 65536 };
uint64_t low;
- long long partial_member_pos;
+ unsigned long long partial_member_pos;
uint8_t * const buffer; // output buffer
int pos; // current pos in buffer
uint32_t range;
@@ -281,7 +290,7 @@ public:
~Range_encoder() { delete[] buffer; }
- long long member_position() const
+ unsigned long long member_position() const
{ return partial_member_pos + pos + ff_count; }
void flush() { for( int i = 0; i < 5; ++i ) shift_low(); }
@@ -345,26 +354,20 @@ public:
}
}
- void encode_matched( Bit_model bm[], int symbol, int match_byte )
+ void encode_matched( Bit_model bm[], unsigned symbol, unsigned match_byte )
{
- int model = 1;
- for( int i = 7; i >= 0; --i )
- {
- const int match_bit = ( match_byte >> i ) & 1;
- int bit = ( symbol >> i ) & 1;
- encode_bit( bm[(match_bit<<8)+model+0x100], bit );
- model = ( model << 1 ) | bit;
- if( match_bit != bit )
- {
- while( --i >= 0 )
- {
- bit = ( symbol >> i ) & 1;
- encode_bit( bm[model], bit );
- model = ( model << 1 ) | bit;
- }
- break;
- }
+ unsigned mask = 0x100;
+ symbol |= 0x100;
+
+ do {
+ match_byte <<= 1;
+ const unsigned match_bit = match_byte & mask;
+ symbol <<= 1;
+ const unsigned bit = symbol & 0x100;
+ encode_bit( bm[match_bit+(symbol>>9)+mask], bit );
+ mask &= ~(match_byte ^ symbol); // if( match_bit != bit ) mask = 0;
}
+ while( symbol < 0x10000 );
}
};
@@ -401,8 +404,8 @@ class Len_encoder
}
public:
- explicit Len_encoder( const int len_limit )
- : len_symbols( len_limit + 1 - min_match_len )
+ explicit Len_encoder( const int match_len_limit )
+ : len_symbols( match_len_limit + 1 - min_match_len )
{
for( int i = 0; i < pos_states; ++i ) update_prices( i );
}
@@ -415,33 +418,6 @@ public:
};
-class Literal_encoder
- {
- Bit_model bm_literal[1<<literal_context_bits][0x300];
-
- int lstate( const uint8_t prev_byte ) const
- { return ( prev_byte >> ( 8 - literal_context_bits ) ); }
-
-public:
- void encode( Range_encoder & range_encoder,
- uint8_t prev_byte, uint8_t symbol )
- { range_encoder.encode_tree( bm_literal[lstate(prev_byte)], symbol, 8 ); }
-
- void encode_matched( Range_encoder & range_encoder,
- uint8_t prev_byte, uint8_t symbol, uint8_t match_byte )
- { range_encoder.encode_matched( bm_literal[lstate(prev_byte)],
- symbol, match_byte ); }
-
- int price_symbol( uint8_t prev_byte, uint8_t symbol ) const
- { return ::price_symbol( bm_literal[lstate(prev_byte)], symbol, 8 ); }
-
- int price_matched( uint8_t prev_byte, uint8_t symbol,
- uint8_t match_byte ) const
- { return ::price_matched( bm_literal[lstate(prev_byte)],
- symbol, match_byte ); }
- };
-
-
class LZ_encoder_base
{
protected:
@@ -450,6 +426,7 @@ protected:
uint32_t crc_;
+ Bit_model bm_literal[1<<literal_context_bits][0x300];
Bit_model bm_match[State::states][pos_states];
Bit_model bm_rep[State::states];
Bit_model bm_rep0[State::states];
@@ -457,17 +434,16 @@ protected:
Bit_model bm_rep2[State::states];
Bit_model bm_len[State::states][pos_states];
Bit_model bm_dis_slot[max_dis_states][1<<dis_slot_bits];
- Bit_model bm_dis[modeled_distances-end_dis_model+1];
+ Bit_model bm_dis[modeled_distances-end_dis_model];
Bit_model bm_align[dis_align_size];
Range_encoder range_encoder;
Len_encoder len_encoder;
Len_encoder rep_match_len_encoder;
- Literal_encoder literal_encoder;
const int num_dis_slots;
- uint32_t crc() const { return crc_ ^ 0xFFFFFFFFU; }
+ unsigned crc() const { return crc_ ^ 0xFFFFFFFFU; }
LZ_encoder_base( const File_header & header, const int dictionary_size,
const int match_len_limit, const int outfd )
@@ -498,10 +474,26 @@ protected:
}
}
+ int price_literal( const uint8_t prev_byte, const uint8_t symbol ) const
+ { return price_symbol( bm_literal[get_lit_state(prev_byte)], symbol, 8 ); }
+
+ 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 ); }
+
+ void encode_literal( const uint8_t prev_byte, const uint8_t symbol )
+ { range_encoder.encode_tree( bm_literal[get_lit_state(prev_byte)], symbol, 8 ); }
+
+ void encode_matched( const uint8_t prev_byte, const uint8_t symbol,
+ const uint8_t match_byte )
+ { range_encoder.encode_matched( bm_literal[get_lit_state(prev_byte)],
+ symbol, match_byte ); }
+
void encode_pair( const uint32_t dis, const int len, const int pos_state )
{
len_encoder.encode( range_encoder, len, pos_state );
- const int dis_slot = dis_slots[dis];
+ const int dis_slot = get_slot( dis );
range_encoder.encode_tree( bm_dis_slot[get_dis_state(len)], dis_slot, dis_slot_bits );
if( dis_slot >= start_dis_model )
@@ -511,7 +503,7 @@ protected:
const uint32_t direct_dis = dis - base;
if( dis_slot < end_dis_model )
- range_encoder.encode_tree_reversed( bm_dis + base - dis_slot,
+ range_encoder.encode_tree_reversed( bm_dis + base - dis_slot - 1,
direct_dis, direct_bits );
else
{
@@ -521,31 +513,58 @@ protected:
}
}
- void full_flush( const long long data_position, const State state );
+ void full_flush( const unsigned long long data_position, const State state );
public:
- long long member_position() const { return range_encoder.member_position(); }
+ unsigned long long member_position() const
+ { return range_encoder.member_position(); }
};
class LZ_encoder : public LZ_encoder_base
{
- enum { infinite_price = 0x0FFFFFFF };
+ enum { infinite_price = 0x0FFFFFFF,
+ single_step_trial = -2,
+ dual_step_trial = -1 };
struct Trial
{
State state;
- int dis;
- int prev_index; // index of prev trial in trials[]
int price; // dual use var; cumulative price, match length
+ int dis; // rep index or match distance
+ int prev_index; // index of prev trial in trials[]
+ int dis2;
+ int prev_index2; // -2 trial is single step
+ // -1 literal + rep0
+ // >= 0 rep or match + literal + rep0
int reps[num_rep_distances];
- void update( const int d, const int p_i, const int pr )
- { if( pr < price ) { dis = d; prev_index = p_i; price = pr; } }
+
+ void update( const int pr, const int d, const int p_i )
+ {
+ if( pr < price )
+ { price = pr; dis = d; prev_index = p_i;
+ prev_index2 = single_step_trial; }
+ }
+
+ void update2( const int pr, const int d, const int p_i )
+ {
+ if( pr < price )
+ { price = pr; dis = d; prev_index = p_i;
+ prev_index2 = dual_step_trial; }
+ }
+
+ void update3( const int pr, const int d, const int p_i,
+ const int d2, const int p_i2 )
+ {
+ if( pr < price )
+ { price = pr; dis = d; prev_index = p_i;
+ dis2 = d2; prev_index2 = p_i2; }
+ }
};
Matchfinder & matchfinder;
- int longest_match_found;
- int match_distances[max_match_len+1];
+ int pending_num_pairs;
+ struct Pair pairs[max_match_len+1];
Trial trials[max_num_trials];
int dis_slot_prices[max_dis_states][2*max_dictionary_bits];
@@ -556,12 +575,12 @@ class LZ_encoder : public LZ_encoder_base
void fill_align_prices();
void fill_distance_prices();
- int price_rep_len1( const int pos_state, const State state ) const
+ int price_rep_len1( const State state, const int pos_state ) const
{
return price0( bm_rep0[state()] ) + price0( bm_len[state()][pos_state] );
}
- int price_rep( const int rep, const int pos_state, const State state ) const
+ int price_rep( const int rep, const State state, const int pos_state ) const
{
if( rep == 0 ) return price0( bm_rep0[state()] ) +
price1( bm_len[state()][pos_state] );
@@ -576,30 +595,41 @@ class LZ_encoder : public LZ_encoder_base
return price;
}
+ int price_rep0_len( const int len, const State state, const int pos_state ) const
+ {
+ return price_rep( 0, state, pos_state ) +
+ rep_match_len_encoder.price( len, pos_state );
+ }
+
int price_dis( const int dis, const int dis_state ) const
{
if( dis < modeled_distances )
return dis_prices[dis_state][dis];
else
- return dis_slot_prices[dis_state][dis_slots[dis]] +
+ return dis_slot_prices[dis_state][get_slot( dis )] +
align_prices[dis & (dis_align_size - 1)];
}
int price_pair( const int dis, const int len, const int pos_state ) const
{
- if( len <= min_match_len && dis >= modeled_distances )
- return infinite_price;
return len_encoder.price( len, pos_state ) +
price_dis( dis, get_dis_state( len ) );
}
int read_match_distances()
{
- int len = matchfinder.longest_match_len( match_distances );
- if( len == matchfinder.match_len_limit() && len < max_match_len )
- len += matchfinder.true_match_len( len, match_distances[len] + 1,
- max_match_len - len );
- return len;
+ const int num_pairs = matchfinder.get_match_pairs( pairs );
+ if( num_pairs > 0 )
+ {
+ int len = pairs[num_pairs-1].len;
+ if( len == matchfinder.match_len_limit() && len < max_match_len )
+ {
+ len += matchfinder.true_match_len( len, pairs[num_pairs-1].dis + 1,
+ max_match_len - len );
+ pairs[num_pairs-1].len = len;
+ }
+ }
+ return num_pairs;
}
void move_pos( int n )
@@ -607,7 +637,7 @@ class LZ_encoder : public LZ_encoder_base
if( --n >= 0 ) matchfinder.move_pos();
while( --n >= 0 )
{
- matchfinder.longest_match_len();
+ matchfinder.get_match_pairs();
matchfinder.move_pos();
}
}
@@ -619,6 +649,20 @@ class LZ_encoder : public LZ_encoder_base
{
const int prev_index = trials[cur].prev_index;
Trial & prev_trial = trials[prev_index];
+
+ if( trials[cur].prev_index2 != single_step_trial )
+ {
+ prev_trial.dis = -1;
+ prev_trial.prev_index = prev_index - 1;
+ prev_trial.prev_index2 = single_step_trial;
+ if( trials[cur].prev_index2 >= 0 )
+ {
+ Trial & prev_trial2 = trials[prev_index-1];
+ prev_trial2.dis = trials[cur].dis2;
+ prev_trial2.prev_index = trials[cur].prev_index2;
+ prev_trial2.prev_index2 = single_step_trial;
+ }
+ }
prev_trial.price = cur - prev_index; // len
cur = dis; dis = prev_trial.dis; prev_trial.dis = cur;
cur = prev_index;
@@ -633,8 +677,9 @@ public:
:
LZ_encoder_base( header, mf.dictionary_size(), mf.match_len_limit(), outfd ),
matchfinder( mf ),
- longest_match_found( 0 )
- { fill_align_prices(); }
+ pending_num_pairs( 0 ),
+ align_price_count( 0 )
+ {}
- bool encode_member( const long long member_size );
+ bool encode_member( const unsigned long long member_size );
};
diff --git a/fast_encoder.cc b/fast_encoder.cc
index 2d99b04..954e671 100644
--- a/fast_encoder.cc
+++ b/fast_encoder.cc
@@ -1,5 +1,5 @@
/* Lzip - Data compressor based on the LZMA algorithm
- Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+ Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -39,7 +39,7 @@ int Fmatchfinder::longest_match_len( int * const distance )
if( len_limit < 4 ) return 0;
}
- key4 = ( ( key4 << 4 ) ^ buffer[pos+3] ) & ( num_prev_pos - 1 );
+ key4 = ( ( key4 << 4 ) ^ buffer[pos+3] ) & key4_mask;
int newpos = prev_positions[key4];
prev_positions[key4] = pos;
@@ -49,18 +49,18 @@ int Fmatchfinder::longest_match_len( int * const distance )
for( int count = 4; ; )
{
- if( newpos < (pos - dictionary_size_ + 1) || newpos < 0 || --count < 0 )
+ const int delta = pos - newpos;
+ if( delta > dictionary_size_ || newpos < 0 || --count < 0 )
{ *ptr0 = -1; break; }
int len = 0;
if( buffer[maxlen+newpos] == buffer[maxlen+pos] )
while( len < len_limit && buffer[len+newpos] == buffer[len+pos] ) ++len;
- const int delta = pos - newpos;
if( maxlen < len ) { maxlen = len; *distance = delta - 1; }
int32_t * const newptr = pos_array +
( cyclic_pos - delta +
- ( ( cyclic_pos >= delta ) ? 0 : dictionary_size_ ) );
+ ( ( cyclic_pos >= delta ) ? 0 : dictionary_size_ + 1 ) );
if( len < len_limit )
{
@@ -80,133 +80,48 @@ int Fmatchfinder::longest_match_len( int * const distance )
}
-void Fmatchfinder::longest_match_len()
- {
- int len_limit = match_len_limit_;
- if( len_limit > available_bytes() )
- {
- len_limit = available_bytes();
- if( len_limit < 4 ) return;
- }
-
- key4 = ( ( key4 << 4 ) ^ buffer[pos+3] ) & ( num_prev_pos - 1 );
-
- const int newpos = prev_positions[key4];
- prev_positions[key4] = pos;
-
- int32_t * const ptr0 = pos_array + cyclic_pos;
-
- if( newpos < (pos - dictionary_size_ + 1) || newpos < 0 )
- *ptr0 = -1;
- else if( buffer[len_limit-1+newpos] != buffer[len_limit-1+pos] ||
- std::memcmp( buffer + newpos, buffer + pos, len_limit - 1 ) )
- *ptr0 = newpos;
- else
- {
- int idx = cyclic_pos - pos + newpos;
- if( idx < 0 ) idx += dictionary_size_;
- *ptr0 = pos_array[idx];
- }
- }
-
-
-void FLZ_encoder::sequence_optimizer( int reps[num_rep_distances],
- State & state )
+void Fmatchfinder::longest_match_len( int n )
{
- int match_distance;
- const int main_len = fmatchfinder.longest_match_len( &match_distance );
- const int pos_state = fmatchfinder.data_position() & pos_state_mask;
- int dis = 0;
- int len = 0;
-
- for( int i = 0; i < num_rep_distances; ++i )
- {
- const int tlen =
- fmatchfinder.true_match_len( 0, reps[i] + 1, max_match_len );
- if( tlen > len ) { len = tlen; dis = i; }
- }
- if( len > min_match_len && len + 4 > main_len )
+ while( --n >= 0 )
{
- crc32.update( crc_, fmatchfinder.ptr_to_current_pos(), len );
- mtf_reps( dis, reps );
- range_encoder.encode_bit( bm_match[state()][pos_state], 1 );
- range_encoder.encode_bit( bm_rep[state()], 1 );
- const bool bit = ( dis == 0 );
- range_encoder.encode_bit( bm_rep0[state()], !bit );
- if( bit )
- range_encoder.encode_bit( bm_len[state()][pos_state], 1 );
- else
+ int len_limit = match_len_limit_ - 1; // len_limit - 1
+ if( len_limit >= available_bytes() )
{
- range_encoder.encode_bit( bm_rep1[state()], dis > 1 );
- if( dis > 1 )
- range_encoder.encode_bit( bm_rep2[state()], dis > 2 );
+ len_limit = available_bytes() - 1;
+ if( len_limit < 3 ) { move_pos(); continue; }
}
- rep_match_len_encoder.encode( range_encoder, len, pos_state );
- state.set_rep();
- move_pos( len );
- return;
- }
- if( main_len > min_match_len ||
- ( main_len == min_match_len && match_distance < modeled_distances ) )
- {
- crc32.update( crc_, fmatchfinder.ptr_to_current_pos(), main_len );
- dis = match_distance;
- mtf_reps( dis + num_rep_distances, reps );
- range_encoder.encode_bit( bm_match[state()][pos_state], 1 );
- range_encoder.encode_bit( bm_rep[state()], 0 );
- encode_pair( dis, main_len, pos_state );
- state.set_match();
- move_pos( main_len );
- return;
- }
+ key4 = ( ( key4 << 4 ) ^ buffer[pos+3] ) & key4_mask;
- const uint8_t prev_byte = fmatchfinder[-1];
- const uint8_t cur_byte = fmatchfinder[0];
- const uint8_t match_byte = fmatchfinder[-reps[0]-1];
- crc32.update( crc_, cur_byte );
- fmatchfinder.move_pos();
+ const int newpos = prev_positions[key4];
+ prev_positions[key4] = pos;
- if( match_byte == cur_byte )
- {
- int price = price0( bm_match[state()][pos_state] );
- if( state.is_char() )
- price += literal_encoder.price_symbol( prev_byte, cur_byte );
+ int32_t * const ptr0 = pos_array + cyclic_pos;
+
+ if( pos - newpos > dictionary_size_ || newpos < 0 )
+ *ptr0 = -1;
+ else if( buffer[len_limit+newpos] != buffer[len_limit+pos] ||
+ std::memcmp( buffer + newpos, buffer + pos, len_limit ) != 0 )
+ *ptr0 = newpos;
else
- price += literal_encoder.price_matched( prev_byte, cur_byte, match_byte );
- const int short_rep_price = price1( bm_match[state()][pos_state] ) +
- price1( bm_rep[state()] ) +
- price0( bm_rep0[state()] ) +
- price0( bm_len[state()][pos_state] );
- if( short_rep_price < price )
{
- range_encoder.encode_bit( bm_match[state()][pos_state], 1 );
- range_encoder.encode_bit( bm_rep[state()], 1 );
- range_encoder.encode_bit( bm_rep0[state()], 0 );
- range_encoder.encode_bit( bm_len[state()][pos_state], 0 );
- state.set_short_rep();
- return;
+ int idx = cyclic_pos - pos + newpos;
+ if( idx < 0 ) idx += dictionary_size_ + 1;
+ *ptr0 = pos_array[idx];
}
+ move_pos();
}
-
- // literal byte
- range_encoder.encode_bit( bm_match[state()][pos_state], 0 );
- if( state.is_char() )
- literal_encoder.encode( range_encoder, prev_byte, cur_byte );
- else
- literal_encoder.encode_matched( range_encoder,
- prev_byte, cur_byte, match_byte );
- state.set_char();
}
-bool FLZ_encoder::encode_member( const long long member_size )
+bool FLZ_encoder::encode_member( const unsigned long long member_size )
{
- const long long member_size_limit =
+ const unsigned long long member_size_limit =
member_size - File_trailer::size() - max_marker_size;
- int rep_distances[num_rep_distances];
+ int dis = 0;
+ int reps[num_rep_distances];
State state;
- for( int i = 0; i < num_rep_distances; ++i ) rep_distances[i] = 0;
+ for( int i = 0; i < num_rep_distances; ++i ) reps[i] = 0;
if( fmatchfinder.data_position() != 0 ||
range_encoder.member_position() != File_header::size )
@@ -217,15 +132,100 @@ bool FLZ_encoder::encode_member( const long long member_size )
const uint8_t prev_byte = 0;
const uint8_t cur_byte = fmatchfinder[0];
range_encoder.encode_bit( bm_match[state()][0], 0 );
- literal_encoder.encode( range_encoder, prev_byte, cur_byte );
+ encode_literal( prev_byte, cur_byte );
crc32.update( crc_, cur_byte );
- fmatchfinder.longest_match_len();
- fmatchfinder.move_pos();
+ fmatchfinder.longest_match_len( 1 );
}
while( !fmatchfinder.finished() &&
range_encoder.member_position() < member_size_limit )
- sequence_optimizer( rep_distances, state );
+ {
+ int match_distance;
+ const int main_len = fmatchfinder.longest_match_len( &match_distance );
+ const int pos_state = fmatchfinder.data_position() & pos_state_mask;
+ int len = 0;
+
+ for( int i = 0; i < num_rep_distances; ++i )
+ {
+ const int tlen =
+ fmatchfinder.true_match_len( 0, reps[i] + 1, max_match_len );
+ if( tlen > len ) { len = tlen; dis = i; }
+ }
+ if( len > min_match_len && len + 4 > main_len )
+ {
+ crc32.update( crc_, fmatchfinder.ptr_to_current_pos(), len );
+ range_encoder.encode_bit( bm_match[state()][pos_state], 1 );
+ range_encoder.encode_bit( bm_rep[state()], 1 );
+ const bool bit = ( dis == 0 );
+ range_encoder.encode_bit( bm_rep0[state()], !bit );
+ if( bit )
+ range_encoder.encode_bit( bm_len[state()][pos_state], 1 );
+ else
+ {
+ const int distance = reps[dis];
+ for( int i = dis; i > 0; --i ) reps[i] = reps[i-1];
+ reps[0] = distance;
+ range_encoder.encode_bit( bm_rep1[state()], dis > 1 );
+ if( dis > 1 )
+ range_encoder.encode_bit( bm_rep2[state()], dis > 2 );
+ }
+ rep_match_len_encoder.encode( range_encoder, len, pos_state );
+ state.set_rep();
+ move_pos( len );
+ continue;
+ }
+
+ if( main_len > min_match_len ||
+ ( main_len == min_match_len && match_distance < modeled_distances ) )
+ {
+ crc32.update( crc_, fmatchfinder.ptr_to_current_pos(), main_len );
+ dis = match_distance;
+ range_encoder.encode_bit( bm_match[state()][pos_state], 1 );
+ range_encoder.encode_bit( bm_rep[state()], 0 );
+ encode_pair( dis, main_len, pos_state );
+ state.set_match();
+ move_pos( main_len );
+ for( int i = num_rep_distances - 1; i > 0; --i ) reps[i] = reps[i-1];
+ reps[0] = dis;
+ continue;
+ }
+
+ const uint8_t prev_byte = fmatchfinder[-1];
+ const uint8_t cur_byte = fmatchfinder[0];
+ const uint8_t match_byte = fmatchfinder[-reps[0]-1];
+ crc32.update( crc_, cur_byte );
+ fmatchfinder.move_pos();
+
+ if( match_byte == cur_byte )
+ {
+ int price = price0( bm_match[state()][pos_state] );
+ if( state.is_char() )
+ price += price_literal( prev_byte, cur_byte );
+ else
+ price += price_matched( prev_byte, cur_byte, match_byte );
+ const int short_rep_price = price1( bm_match[state()][pos_state] ) +
+ price1( bm_rep[state()] ) +
+ price0( bm_rep0[state()] ) +
+ price0( bm_len[state()][pos_state] );
+ if( short_rep_price < price )
+ {
+ range_encoder.encode_bit( bm_match[state()][pos_state], 1 );
+ range_encoder.encode_bit( bm_rep[state()], 1 );
+ range_encoder.encode_bit( bm_rep0[state()], 0 );
+ range_encoder.encode_bit( bm_len[state()][pos_state], 0 );
+ state.set_short_rep();
+ continue;
+ }
+ }
+
+ // literal byte
+ range_encoder.encode_bit( bm_match[state()][pos_state], 0 );
+ if( state.is_char() )
+ encode_literal( prev_byte, cur_byte );
+ else
+ encode_matched( prev_byte, cur_byte, match_byte );
+ state.set_char();
+ }
full_flush( fmatchfinder.data_position(), state );
return true;
diff --git a/fast_encoder.h b/fast_encoder.h
index 05c3ca8..5b5169f 100644
--- a/fast_encoder.h
+++ b/fast_encoder.h
@@ -1,5 +1,5 @@
/* Lzip - Data compressor based on the LZMA algorithm
- Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+ Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -17,11 +17,13 @@
class Fmatchfinder : public Matchfinder_base
{
- enum { before = max_match_len + 1,
+ enum { before_size = max_match_len + 1,
dict_size = 65536,
+ // bytes to keep in buffer after pos
+ after_size = max_match_len,
dict_factor = 16,
len_limit = 16,
- num_prev_pos = 1 << 16,
+ num_prev_positions23 = 0,
pos_array_factor = 1 };
int key4; // key made from latest 4 bytes
@@ -29,14 +31,14 @@ class Fmatchfinder : public Matchfinder_base
public:
explicit Fmatchfinder( const int ifd )
:
- Matchfinder_base( before, dict_size, dict_factor, len_limit,
- num_prev_pos, ifd, pos_array_factor ),
+ Matchfinder_base( before_size, dict_size, after_size, dict_factor,
+ len_limit, num_prev_positions23, pos_array_factor, ifd ),
key4( 0 )
{}
void reset() { Matchfinder_base::reset(); key4 = 0; }
int longest_match_len( int * const distance );
- void longest_match_len();
+ void longest_match_len( int n );
};
@@ -47,15 +49,9 @@ class FLZ_encoder : public LZ_encoder_base
void move_pos( int n )
{
if( --n >= 0 ) fmatchfinder.move_pos();
- while( --n >= 0 )
- {
- fmatchfinder.longest_match_len();
- fmatchfinder.move_pos();
- }
+ fmatchfinder.longest_match_len( n );
}
- void sequence_optimizer( int reps[num_rep_distances], State & state );
-
public:
FLZ_encoder( Fmatchfinder & mf, const File_header & header, const int outfd )
:
@@ -63,5 +59,5 @@ public:
fmatchfinder( mf )
{}
- bool encode_member( const long long member_size );
+ bool encode_member( const unsigned long long member_size );
};
diff --git a/lzip.h b/lzip.h
index 1e61400..77aa73e 100644
--- a/lzip.h
+++ b/lzip.h
@@ -1,5 +1,5 @@
/* Lzip - Data compressor based on the LZMA algorithm
- Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+ Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -17,41 +17,23 @@
class State
{
- unsigned char st;
+ int st;
public:
enum { states = 12 };
State() : st( 0 ) {}
- unsigned char operator()() const { return st; }
+ int operator()() const { return st; }
bool is_char() const { return st < 7; }
void set_char()
{
- static const unsigned char next[states] =
- { 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5 };
+ static const int next[states] = { 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5 };
st = next[st];
}
- void set_match()
- {
- static const unsigned char next[states] =
- { 7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10 };
- st = next[st];
- }
-
- void set_rep()
- {
- static const unsigned char next[states] =
- { 8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11 };
- st = next[st];
- }
-
- void set_short_rep()
- {
- static const unsigned char next[states] =
- { 9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11 };
- 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 ); }
};
@@ -68,7 +50,7 @@ enum {
dis_slot_bits = 6,
start_dis_model = 4,
end_dis_model = 14,
- modeled_distances = 1 << (end_dis_model / 2),
+ modeled_distances = 1 << (end_dis_model / 2), // 128
dis_align_bits = 4,
dis_align_size = 1 << dis_align_bits,
@@ -86,12 +68,11 @@ enum {
max_dis_states = 4 };
-inline int get_dis_state( int len )
- {
- len -= min_match_len;
- if( len >= max_dis_states ) len = max_dis_states - 1;
- return len;
- }
+inline int get_dis_state( const int len )
+ { return std::min( len - min_match_len, max_dis_states - 1 ); }
+
+inline int get_lit_state( const uint8_t prev_byte )
+ { return ( prev_byte >> ( 8 - literal_context_bits ) ); }
enum { bit_model_move_bits = 5,
@@ -100,17 +81,17 @@ enum { bit_model_move_bits = 5,
struct Bit_model
{
- unsigned int probability;
+ int probability;
Bit_model() : probability( bit_model_total / 2 ) {}
};
class Pretty_print
{
+ std::string name_;
const char * const stdin_name;
- unsigned int longest_name;
+ unsigned longest_name;
const int verbosity_;
- std::string name_;
mutable bool first_post;
public:
@@ -118,11 +99,11 @@ public:
: stdin_name( "(stdin)" ), longest_name( 0 ), verbosity_( v ),
first_post( false )
{
- const unsigned int stdin_name_len = std::strlen( stdin_name );
- for( unsigned int i = 0; i < filenames.size(); ++i )
+ const unsigned stdin_name_len = std::strlen( stdin_name );
+ for( unsigned i = 0; i < filenames.size(); ++i )
{
const std::string & s = filenames[i];
- const unsigned int len = ( ( s == "-" ) ? stdin_name_len : s.size() );
+ const unsigned len = ( ( s == "-" ) ? stdin_name_len : s.size() );
if( len > longest_name ) longest_name = len;
}
if( longest_name == 0 ) longest_name = stdin_name_len;
@@ -149,9 +130,9 @@ class CRC32
public:
CRC32()
{
- for( unsigned int n = 0; n < 256; ++n )
+ for( unsigned n = 0; n < 256; ++n )
{
- unsigned int c = n;
+ unsigned c = n;
for( int k = 0; k < 8; ++k )
{ if( c & 1 ) c = 0xEDB88320U ^ ( c >> 1 ); else c >>= 1; }
data[n] = c;
@@ -159,8 +140,10 @@ public:
}
uint32_t operator[]( const uint8_t byte ) const { return data[byte]; }
+
void update( uint32_t & crc, const uint8_t byte ) const
{ crc = data[(crc^byte)&0xFF] ^ ( crc >> 8 ); }
+
void update( uint32_t & crc, const uint8_t * const buffer, const int size ) const
{
for( int i = 0; i < size; ++i )
@@ -171,16 +154,15 @@ public:
extern const CRC32 crc32;
-inline int real_bits( const unsigned int value )
+inline int real_bits( unsigned value )
{
- int bits = 0, i = 1;
- unsigned int mask = 1;
- for( ; mask > 0; ++i, mask <<= 1 ) if( value & mask ) bits = i;
+ int bits = 0;
+ while( value > 0 ) { value >>= 1; ++bits; }
return bits;
}
-const uint8_t magic_string[4] = { 'L', 'Z', 'I', 'P' };
+const uint8_t magic_string[4] = { 0x4C, 0x5A, 0x49, 0x50 }; // "LZIP"
struct File_header
{
@@ -196,10 +178,10 @@ struct File_header
uint8_t version() const { return data[4]; }
bool verify_version() const { return ( data[4] <= 1 ); }
- int dictionary_size() const
+ unsigned dictionary_size() const
{
- int sz = ( 1 << ( data[5] & 0x1F ) );
- if( sz > min_dictionary_size && sz <= max_dictionary_size )
+ unsigned sz = ( 1 << ( data[5] & 0x1F ) );
+ if( sz > min_dictionary_size )
sz -= ( sz / 16 ) * ( ( data[5] >> 5 ) & 7 );
return sz;
}
@@ -233,36 +215,36 @@ struct File_trailer
static int size( const int version = 1 )
{ return ( ( version >= 1 ) ? 20 : 12 ); }
- uint32_t data_crc() const
+ unsigned data_crc() const
{
- uint32_t tmp = 0;
+ unsigned tmp = 0;
for( int i = 3; i >= 0; --i ) { tmp <<= 8; tmp += data[i]; }
return tmp;
}
- void data_crc( uint32_t crc )
+ void data_crc( unsigned crc )
{ for( int i = 0; i <= 3; ++i ) { data[i] = (uint8_t)crc; crc >>= 8; } }
- long long data_size() const
+ unsigned long long data_size() const
{
- long long tmp = 0;
+ unsigned long long tmp = 0;
for( int i = 11; i >= 4; --i ) { tmp <<= 8; tmp += data[i]; }
return tmp;
}
- void data_size( long long sz )
+ void data_size( unsigned long long sz )
{
for( int i = 4; i <= 11; ++i ) { data[i] = (uint8_t)sz; sz >>= 8; }
}
- long long member_size() const
+ unsigned long long member_size() const
{
- long long tmp = 0;
+ unsigned long long tmp = 0;
for( int i = 19; i >= 12; --i ) { tmp <<= 8; tmp += data[i]; }
return tmp;
}
- void member_size( long long sz )
+ void member_size( unsigned long long sz )
{
for( int i = 12; i <= 19; ++i ) { data[i] = (uint8_t)sz; sz >>= 8; }
}
@@ -276,11 +258,11 @@ struct Error
};
+// defined in decoder.cc
+int readblock( const int fd, uint8_t * const buf, const int size );
+int writeblock( const int fd, const uint8_t * const buf, const int size );
+
// defined in main.cc
void show_error( const char * const msg, const int errcode = 0,
const bool help = false );
void internal_error( const char * const msg );
-
-// defined in decoder.cc
-int readblock( const int fd, uint8_t * const buf, const int size );
-int writeblock( const int fd, const uint8_t * const buf, const int size );
diff --git a/main.cc b/main.cc
index 276fe30..068ca62 100644
--- a/main.cc
+++ b/main.cc
@@ -1,5 +1,5 @@
/* Lzip - Data compressor based on the LZMA algorithm
- Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+ Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -41,6 +41,7 @@
#include <io.h>
#define fchmod(x,y) 0
#define fchown(x,y,z) 0
+#define strtoull std::strtoul
#define SIGHUP SIGTERM
#define S_ISSOCK(x) 0
#define S_IRGRP 0
@@ -62,22 +63,12 @@
#error "Environments where CHAR_BIT != 8 are not supported."
#endif
-#ifndef LLONG_MAX
-#define LLONG_MAX 0x7FFFFFFFFFFFFFFFLL
-#endif
-#ifndef LLONG_MIN
-#define LLONG_MIN (-LLONG_MAX - 1LL)
-#endif
-#ifndef ULLONG_MAX
-#define ULLONG_MAX 0xFFFFFFFFFFFFFFFFULL
-#endif
-
namespace {
const char * const Program_name = "Lzip";
const char * const program_name = "lzip";
-const char * const program_year = "2012";
+const char * const program_year = "2013";
const char * invocation_name = 0;
#ifdef O_BINARY
@@ -98,6 +89,8 @@ struct Lzma_options
};
enum Mode { m_compress, m_decompress, m_test };
+const unsigned long long max_member_size = 0x1000000000000000ULL;
+const unsigned long long max_volume_size = 0x7FFFFFFFFFFFFFFFULL;
std::string output_filename;
int outfd = -1;
@@ -154,30 +147,31 @@ void show_version()
}
-const char * format_num( long long num )
+void show_header( const File_header & header )
{
const char * const prefix[8] =
{ "Ki", "Mi", "Gi", "Ti", "Pi", "Ei", "Zi", "Yi" };
- enum { buf_size = 16, factor = 1024 };
- static char buf[buf_size];
- const char *p = "";
+ enum { factor = 1024 };
+ const char * p = "";
+ const char * np = " ";
+ unsigned num = header.dictionary_size();
bool exact = ( num % factor == 0 );
- for( int i = 0; i < 8 && ( llabs( num ) > 9999 ||
- ( exact && llabs( num ) >= factor ) ); ++i )
- { num /= factor; if( num % factor != 0 ) exact = false; p = prefix[i]; }
- snprintf( buf, buf_size, "%lld %s", num, p );
- return buf;
+ for( int i = 0; i < 8 && ( num > 9999 || ( exact && num >= factor ) ); ++i )
+ { num /= factor; if( num % factor != 0 ) exact = false;
+ p = prefix[i]; np = ""; }
+ std::fprintf( stderr, "version %d, dictionary size %s%4u %sB. ",
+ header.version(), np, num, p );
}
-long long getnum( const char * const ptr,
- const long long llimit = LLONG_MIN + 1,
- const long long ulimit = LLONG_MAX )
+unsigned long long getnum( const char * const ptr,
+ const unsigned long long llimit,
+ const unsigned long long ulimit )
{
errno = 0;
- char *tail;
- long long result = strtoll( ptr, &tail, 0 );
+ char * tail;
+ unsigned long long result = strtoull( ptr, &tail, 0 );
if( tail == ptr )
{
show_error( "Bad or missing numerical argument.", 0, true );
@@ -212,7 +206,7 @@ long long getnum( const char * const ptr,
}
for( int i = 0; i < exponent; ++i )
{
- if( LLONG_MAX / factor >= llabs( result ) ) result *= factor;
+ if( ulimit / factor >= result ) result *= factor;
else { errno = ERANGE; break; }
}
}
@@ -228,7 +222,7 @@ long long getnum( const char * const ptr,
int get_dict_size( const char * const arg )
{
- char *tail;
+ char * tail;
int bits = std::strtol( arg, &tail, 0 );
if( bits >= min_dictionary_bits &&
bits <= max_dictionary_bits && *tail == 0 )
@@ -274,7 +268,7 @@ int open_instream( const std::string & name, struct stat * const in_statsp,
else
{
const int i = fstat( infd, in_statsp );
- const mode_t & mode = in_statsp->st_mode;
+ const mode_t mode = in_statsp->st_mode;
const bool can_read = ( i == 0 &&
( S_ISBLK( mode ) || S_ISCHR( mode ) ||
S_ISFIFO( mode ) || S_ISSOCK( mode ) ) );
@@ -401,7 +395,7 @@ void close_and_set_permissions( const struct stat * const in_statsp )
bool next_filename()
{
- const unsigned int len = std::strlen( known_extensions[0].from );
+ const unsigned len = std::strlen( known_extensions[0].from );
if( output_filename.size() >= len + 5 ) // "*00001.lz"
for( int i = output_filename.size() - len - 1, j = 0; j < 5; --i, ++j )
{
@@ -412,13 +406,15 @@ bool next_filename()
}
-int compress( const long long member_size, const long long volume_size,
+int compress( const unsigned long long member_size,
+ const unsigned long long volume_size,
const Lzma_options & encoder_options, const int infd,
const Pretty_print & pp, const struct stat * const in_statsp )
{
int retval = 0;
File_header header;
header.set_magic();
+
if( verbosity >= 1 ) pp();
if( !header.dictionary_size( encoder_options.dictionary_size ) ||
encoder_options.match_len_limit < min_match_len_limit ||
@@ -430,28 +426,31 @@ int compress( const long long member_size, const long long volume_size,
encoder_options.match_len_limit, infd );
header.dictionary_size( matchfinder.dictionary_size() );
- long long in_size = 0, out_size = 0, partial_volume_size = 0;
+ unsigned long long in_size = 0, out_size = 0, partial_volume_size = 0;
while( true ) // encode one member per iteration
{
LZ_encoder encoder( matchfinder, header, outfd );
- const long long size =
- std::min( member_size, volume_size - partial_volume_size );
+ const unsigned long long size = ( ( volume_size > 0 ) ?
+ std::min( member_size, volume_size - partial_volume_size ) : member_size );
if( !encoder.encode_member( size ) )
{ pp( "Encoder error" ); retval = 1; break; }
in_size += matchfinder.data_position();
out_size += encoder.member_position();
if( matchfinder.finished() ) break;
- partial_volume_size += encoder.member_position();
- if( partial_volume_size >= volume_size - min_dictionary_size )
+ if( volume_size > 0 )
{
- partial_volume_size = 0;
- if( delete_output_on_interrupt )
+ partial_volume_size += encoder.member_position();
+ if( partial_volume_size >= volume_size - min_dictionary_size )
{
- close_and_set_permissions( in_statsp );
- if( !next_filename() )
- { pp( "Too many volume files" ); retval = 1; break; }
- if( !open_outstream( true ) ) { retval = 1; break; }
- delete_output_on_interrupt = true;
+ partial_volume_size = 0;
+ if( delete_output_on_interrupt )
+ {
+ close_and_set_permissions( in_statsp );
+ if( !next_filename() )
+ { pp( "Too many volume files" ); retval = 1; break; }
+ if( !open_outstream( true ) ) { retval = 1; break; }
+ delete_output_on_interrupt = true;
+ }
}
}
matchfinder.reset();
@@ -459,11 +458,11 @@ int compress( const long long member_size, const long long volume_size,
if( retval == 0 && verbosity >= 1 )
{
- if( in_size <= 0 || out_size <= 0 )
+ if( in_size == 0 || out_size == 0 )
std::fprintf( stderr, " no data compressed.\n" );
else
std::fprintf( stderr, "%6.3f:1, %6.3f bits/byte, "
- "%5.2f%% saved, %lld in, %lld out.\n",
+ "%5.2f%% saved, %llu in, %llu out.\n",
(double)in_size / out_size,
( 8.0 * out_size ) / in_size,
100.0 * ( 1.0 - ( (double)out_size / in_size ) ),
@@ -480,8 +479,8 @@ int compress( const long long member_size, const long long volume_size,
}
-int fcompress( const long long member_size, const long long volume_size,
- const int infd,
+int fcompress( const unsigned long long member_size,
+ const unsigned long long volume_size, const int infd,
const Pretty_print & pp, const struct stat * const in_statsp )
{
int retval = 0;
@@ -491,30 +490,34 @@ int fcompress( const long long member_size, const long long volume_size,
try {
Fmatchfinder fmatchfinder( infd );
- header.dictionary_size( fmatchfinder.dictionary_size() );
+ if( !header.dictionary_size( fmatchfinder.dictionary_size() ) )
+ internal_error( "invalid argument to encoder" );
- long long in_size = 0, out_size = 0, partial_volume_size = 0;
+ unsigned long long in_size = 0, out_size = 0, partial_volume_size = 0;
while( true ) // encode one member per iteration
{
FLZ_encoder encoder( fmatchfinder, header, outfd );
- const long long size =
- std::min( member_size, volume_size - partial_volume_size );
+ const unsigned long long size = ( ( volume_size > 0 ) ?
+ std::min( member_size, volume_size - partial_volume_size ) : member_size );
if( !encoder.encode_member( size ) )
{ pp( "Encoder error" ); retval = 1; break; }
in_size += fmatchfinder.data_position();
out_size += encoder.member_position();
if( fmatchfinder.finished() ) break;
- partial_volume_size += encoder.member_position();
- if( partial_volume_size >= volume_size - min_dictionary_size )
+ if( volume_size > 0 )
{
- partial_volume_size = 0;
- if( delete_output_on_interrupt )
+ partial_volume_size += encoder.member_position();
+ if( partial_volume_size >= volume_size - min_dictionary_size )
{
- close_and_set_permissions( in_statsp );
- if( !next_filename() )
- { pp( "Too many volume files" ); retval = 1; break; }
- if( !open_outstream( true ) ) { retval = 1; break; }
- delete_output_on_interrupt = true;
+ partial_volume_size = 0;
+ if( delete_output_on_interrupt )
+ {
+ close_and_set_permissions( in_statsp );
+ if( !next_filename() )
+ { pp( "Too many volume files" ); retval = 1; break; }
+ if( !open_outstream( true ) ) { retval = 1; break; }
+ delete_output_on_interrupt = true;
+ }
}
}
fmatchfinder.reset();
@@ -522,11 +525,11 @@ int fcompress( const long long member_size, const long long volume_size,
if( retval == 0 && verbosity >= 1 )
{
- if( in_size <= 0 || out_size <= 0 )
+ if( in_size == 0 || out_size == 0 )
std::fprintf( stderr, " no data compressed.\n" );
else
std::fprintf( stderr, "%6.3f:1, %6.3f bits/byte, "
- "%5.2f%% saved, %lld in, %lld out.\n",
+ "%5.2f%% saved, %llu in, %llu out.\n",
(double)in_size / out_size,
( 8.0 * out_size ) / in_size,
100.0 * ( 1.0 - ( (double)out_size / in_size ) ),
@@ -584,9 +587,9 @@ int decompress( const int infd, const Pretty_print & pp, const bool testing )
int retval = 0;
try {
+ unsigned long long partial_file_pos = 0;
Range_decoder rdec( infd );
- long long partial_file_pos = 0;
- for( bool first_member = true; ; first_member = false, pp.reset() )
+ for( bool first_member = true; ; first_member = false )
{
File_header header;
rdec.reset_member_position();
@@ -620,13 +623,7 @@ int decompress( const int infd, const Pretty_print & pp, const bool testing )
{ pp( "Invalid dictionary size in member header" ); retval = 2; break; }
if( verbosity >= 2 || ( verbosity == 1 && first_member ) )
- {
- pp();
- if( verbosity >= 2 )
- std::fprintf( stderr, "version %d, dictionary size %7sB. ",
- header.version(),
- format_num( header.dictionary_size() ) );
- }
+ { pp(); if( verbosity >= 2 ) show_header( header ); }
LZ_decoder decoder( header, rdec, outfd );
const int result = decoder.decode_member( pp );
@@ -637,17 +634,17 @@ int decompress( const int infd, const Pretty_print & pp, const bool testing )
{
pp();
if( result == 2 )
- std::fprintf( stderr, "File ends unexpectedly at pos %lld\n",
+ std::fprintf( stderr, "File ends unexpectedly at pos %llu\n",
partial_file_pos );
else
- std::fprintf( stderr, "Decoder error at pos %lld\n",
+ std::fprintf( stderr, "Decoder error at pos %llu\n",
partial_file_pos );
}
retval = 2; break;
}
if( verbosity >= 2 )
{ if( testing ) std::fprintf( stderr, "ok\n" );
- else std::fprintf( stderr, "done\n" ); }
+ else std::fprintf( stderr, "done\n" ); pp.reset(); }
}
}
catch( std::bad_alloc )
@@ -691,7 +688,7 @@ void show_error( const char * const msg, const int errcode, const bool help )
std::fprintf( stderr, ": %s", std::strerror( errcode ) );
std::fprintf( stderr, "\n" );
}
- if( help && invocation_name && invocation_name[0] )
+ if( help )
std::fprintf( stderr, "Try '%s --help' for more information.\n",
invocation_name );
}
@@ -723,8 +720,11 @@ int main( const int argc, const char * const argv[] )
{ 3 << 23, 132 }, // -8
{ 1 << 25, 273 } }; // -9
Lzma_options encoder_options = option_mapping[6]; // default = "-6"
- long long member_size = LLONG_MAX;
- long long volume_size = LLONG_MAX;
+ unsigned long long member_size = max_member_size;
+ unsigned long long volume_size = 0;
+ std::string input_filename;
+ std::string default_output_filename;
+ std::vector< std::string > filenames;
int infd = -1;
Mode program_mode = m_compress;
bool force = false;
@@ -732,9 +732,6 @@ int main( const int argc, const char * const argv[] )
bool recompress = false;
bool to_stdout = false;
bool zero = false;
- std::string input_filename;
- std::string default_output_filename;
- std::vector< std::string > filenames;
invocation_name = argv[0];
const Arg_parser::Option options[] =
@@ -783,7 +780,7 @@ int main( const int argc, const char * const argv[] )
case '5': case '6': case '7': case '8': case '9':
zero = false;
encoder_options = option_mapping[code-'0']; break;
- case 'b': member_size = getnum( arg, 100000, LLONG_MAX / 2 ); break;
+ case 'b': member_size = getnum( arg, 100000, max_member_size ); break;
case 'c': to_stdout = true; break;
case 'd': program_mode = m_decompress; break;
case 'f': force = true; break;
@@ -797,7 +794,7 @@ int main( const int argc, const char * const argv[] )
case 'q': verbosity = -1; break;
case 's': encoder_options.dictionary_size = get_dict_size( arg );
zero = false; break;
- case 'S': volume_size = getnum( arg, 100000, LLONG_MAX / 2 ); break;
+ case 'S': volume_size = getnum( arg, 100000, max_volume_size ); break;
case 't': program_mode = m_test; break;
case 'v': if( verbosity < 4 ) ++verbosity; break;
case 'V': show_version(); return 0;
@@ -806,8 +803,8 @@ int main( const int argc, const char * const argv[] )
} // end process options
#if defined(__MSVCRT__) || defined(__OS2__)
- _fsetmode( stdin, "b" );
- _fsetmode( stdout, "b" );
+ setmode( STDIN_FILENO, O_BINARY );
+ setmode( STDOUT_FILENO, O_BINARY );
#endif
if( program_mode == m_test )
@@ -821,8 +818,8 @@ int main( const int argc, const char * const argv[] )
bool filenames_given = false;
for( ; argind < parser.arguments(); ++argind )
{
- if( parser.argument( argind ) != "-" ) filenames_given = true;
filenames.push_back( parser.argument( argind ) );
+ if( filenames.back() != "-" ) filenames_given = true;
}
if( filenames.empty() ) filenames.push_back("-");
@@ -833,7 +830,7 @@ int main( const int argc, const char * const argv[] )
Pretty_print pp( filenames, verbosity );
int retval = 0;
- for( unsigned int i = 0; i < filenames.size(); ++i )
+ for( unsigned i = 0; i < filenames.size(); ++i )
{
struct stat in_stats;
output_filename.clear();
@@ -849,12 +846,12 @@ int main( const int argc, const char * const argv[] )
else
{
if( program_mode == m_compress )
- set_c_outname( default_output_filename, volume_size != LLONG_MAX );
+ set_c_outname( default_output_filename, volume_size > 0 );
else output_filename = default_output_filename;
outfd_mode = all_rw;
if( !open_outstream( force ) )
{
- if( outfd == -1 && retval < 1 ) retval = 1;
+ if( retval < 1 ) retval = 1;
close( infd ); infd = -1;
continue;
}
@@ -874,12 +871,12 @@ int main( const int argc, const char * const argv[] )
else
{
if( program_mode == m_compress )
- set_c_outname( input_filename, volume_size != LLONG_MAX );
+ set_c_outname( input_filename, volume_size > 0 );
else set_d_outname( input_filename, eindex );
outfd_mode = usr_rw;
if( !open_outstream( force ) )
{
- if( outfd == -1 && retval < 1 ) retval = 1;
+ if( retval < 1 ) retval = 1;
close( infd ); infd = -1;
continue;
}
@@ -893,7 +890,7 @@ int main( const int argc, const char * const argv[] )
delete_output_on_interrupt = true;
const struct stat * const in_statsp = input_filename.size() ? &in_stats : 0;
pp.set_name( input_filename );
- int tmp = 0;
+ int tmp;
if( program_mode == m_compress )
{
if( zero )
diff --git a/testsuite/check.sh b/testsuite/check.sh
index 116345c..ff3f574 100755
--- a/testsuite/check.sh
+++ b/testsuite/check.sh
@@ -1,6 +1,6 @@
#! /bin/sh
# check script for Lzip - Data compressor based on the LZMA algorithm
-# Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+# Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
#
# This script is free software: you have unlimited permission
# to copy, distribute and modify it.
@@ -22,33 +22,31 @@ mkdir tmp
cd "${objdir}"/tmp
cat "${testdir}"/test.txt > in || framework_failure
-cat in in > in2 || framework_failure
fail=0
printf "testing lzip-%s..." "$2"
-"${LZIP}" -t "${testdir}"/test_v0.lz || fail=1
-"${LZIP}" -cd "${testdir}"/test_v0.lz > copy || fail=1
-cmp in copy || fail=1
-printf .
-
-"${LZIP}" -t "${testdir}"/test_v1.lz || fail=1
-"${LZIP}" -cd "${testdir}"/test_v1.lz > copy || fail=1
-cmp in copy || fail=1
-printf .
-
-"${LZIP}" -t "${testdir}"/test_sync.lz || fail=1
-"${LZIP}" -cd "${testdir}"/test_sync.lz > copy || fail=1
+"${LZIP}" -t "${testdir}"/test.txt.lz || fail=1
+"${LZIP}" -cd "${testdir}"/test.txt.lz > copy || fail=1
cmp in copy || fail=1
printf .
-"${LZIP}" -cfq "${testdir}"/test_v1.lz > out
+"${LZIP}" -cfq "${testdir}"/test.txt.lz > out
if [ $? != 1 ] ; then fail=1 ; printf - ; else printf . ; fi
-"${LZIP}" -cF "${testdir}"/test_v1.lz > out || fail=1
+"${LZIP}" -cF "${testdir}"/test.txt.lz > out || fail=1
"${LZIP}" -cd out | "${LZIP}" -d > copy || fail=1
cmp in copy || fail=1
printf .
+"${LZIP}" -cqs-1 in > out
+if [ $? != 1 ] ; then fail=1 ; printf - ; else printf . ; fi
+"${LZIP}" -cqs0 in > out
+if [ $? != 1 ] ; then fail=1 ; printf - ; else printf . ; fi
+"${LZIP}" -cqs4095 in > out
+if [ $? != 1 ] ; then fail=1 ; printf - ; else printf . ; fi
+"${LZIP}" -cqm274 in > out
+if [ $? != 1 ] ; then fail=1 ; printf - ; else printf . ; fi
+
for i in s4Ki 0 1 2 3 4 5 6 7 8 9 ; do
"${LZIP}" -k -$i in || fail=1
mv -f in.lz copy.lz || fail=1
@@ -80,16 +78,17 @@ for i in s4Ki 0 1 2 3 4 5 6 7 8 9 ; do
printf .
done
-"${LZIP}" < in2 > out2 || fail=1
-"${LZIP}" -d < out2 > copy2 || fail=1
-cmp in2 copy2 || 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}" < in2 > out2 || fail=1
+"${LZIP}" -d < out2 > copy2 || fail=1
+cmp in2 copy2 || fail=1
+printf .
+
echo
if [ ${fail} = 0 ] ; then
echo "tests completed successfully."
diff --git a/testsuite/test.txt.lz b/testsuite/test.txt.lz
new file mode 100644
index 0000000..4db881a
--- /dev/null
+++ b/testsuite/test.txt.lz
Binary files differ
diff --git a/testsuite/test_sync.lz b/testsuite/test_sync.lz
deleted file mode 100644
index 419fa97..0000000
--- a/testsuite/test_sync.lz
+++ /dev/null
Binary files differ
diff --git a/testsuite/test_v0.lz b/testsuite/test_v0.lz
deleted file mode 100644
index a09b1e8..0000000
--- a/testsuite/test_v0.lz
+++ /dev/null
Binary files differ
diff --git a/testsuite/test_v1.lz b/testsuite/test_v1.lz
deleted file mode 100644
index f1c79eb..0000000
--- a/testsuite/test_v1.lz
+++ /dev/null
Binary files differ
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-02 04:07:43 +0000