2012-08-06 Mikolaj Izdebski <zurgunt@gmail.com> Ignore --small src/main.c (main): Reset small to zero. Improve initial tree generation * src/encode.c (generate_initial_trees): During initial set paritioning round set cardinalities to the nearest instead of rounding up. This decreases standard deviation of the size of trees and thus improves compression. Add THANKS Document bugs fixed Explicitly license auxiliary programs under GPLv3+ * tests/minbzcat.c: Relicense under GPLv3+. * tests/timeout.c: Add explicit license terms. Rebase to the newest version of yambi * ALGORITHM: Fix a typo. * Makefile.am: Remove yambi subdirectory. * build-aux/autogen.sh: Implement new directory structure layout. * build-aux/make-crctab.pl: Likewise. * build-aux/style-check.pl: Likewise. * configure.ac: Lower autoconf requirement. Optimize runtime by adding gl_ASSERT_NO_GNULIB_TESTS and gl_ASSERT_NO_GNULIB_POSIXCHECK. Add new compiler warnings. Implement new option "--enable-tracing". Implement new directory structure layout. * src/Makefile.am: Import from newer version of yambi. * src/common.h: Likewise. * src/compress.c: Likewise. * src/decode.c: Likewise. * src/decode.h: Likewise. * src/divbwt.c: Likewise. * src/encode.c: Likewise. * src/encode.h: Likewise. * src/expand.c: Likewise. * src/main.c: Likewise. * src/main.h: Likewise. * src/parse.c: Likewise. * src/process.c: Likewise. * src/process.h: Likewise. * src/signals.c: Likewise. * src/signals.h: Likewise. * tests/Makefile.am: Likewise. * tests/cve2.bz2: Likewise. * src/lbunzip2.c: Remove file. * src/lbunzip2.h: Likewise. * src/lbzip2.c: Likewise. * src/lbzip2.h: Likewise. * src/pqueue.c: Likewise. * src/pqueue.h: Likewise. * yambi/Makefile.am: Likewise. * yambi/collect.c: Likewise. * yambi/decode.c: Likewise. * yambi/decode.h: Likewise. * yambi/divsufsort.c: Likewise. * yambi/emit.c: Likewise. * yambi/encode.c: Likewise. * yambi/encode.h: Likewise. * yambi/prefix.c: Likewise. * yambi/private.h: Likewise. * yambi/retrieve.c: Likewise. * yambi/transmit.c: Likewise. * yambi/yambi.h: Likewise. 2012-06-23 Mikolaj Izdebski <zurgunt@gmail.com> Update ChangeLog Bump version to 2.2 Simplify AUTHORS file Add workaround for Debian bug #673378 * yambi/retrieve.c (YBdec_retrieve): Return YB_UNDERFLOW if in_avail is 0. This Works around dDebian bug #673378. Revert "Implement double-ended queue." * src/deque.c: Delete file. * src/deque.h: Likewise. 2012-02-22 MikoÅaj Izdebski <zurgunt@gmail.com> Implement double-ended queue. * src/deque.c: New file. * src/deque.h: New file. * src/Makefile.am: Add deque.[ch]. Make pqueue_pop() return the popped element * src/pqueue.c (pqueue_pop): Return popped element. * src/pqueue.h (pqueue_pop): Change function prototype. Don't print EPIPE and EFBIG fatal errors * src/main.c (DEF): Skip printing fatal error messages if error number is EPIPE or EFGIG. Cleanup yambi code * yambi/divsufsort.h: Delete header file. * yambi/Makefile.am: Remove reference to divsufsort.h. * yambi/divsufsort.c: Include encode.h instead of divsufsort.h. Change cyclic_divbwt() function name to YBpriv_cyclic_divbwt(). * yambi/encode.h (YBpriv_block_sort, YBpriv_sais): Remove prototypes of previously removed functions. * yambi/encode.c (YBenc_work): Replace reference to cyclic_divbwt() with YBpriv_cyclic_divbwt(). * yambi/private.h (SLong): Remove unused type definition. 2012-02-21 MikoÅaj Izdebski <zurgunt@gmail.com> Implement new error handling Fix a bug in tandem repeat sort code * yambi/divsufsort.c (trsort): Fix a bug introduced in 336008f by altering the main trsort loop invariant. Adding a pre-condition of `-n < *SA' seems to fix the issue. 2012-02-16 MikoÅaj Izdebski <zurgunt@gmail.com> Remove obsolete shallow factor * yambi/collect.c, yambi/encode.h: Get rid of shallow_factor. * yambi/yambi.h: Remove YB_DEFAULT_SHALLOW #definition. * src/lbzip2.c (work_compr): Remove YB_DEFAULT_SHALLOW 2012-02-02 MikoÅaj Izdebski <zurgunt@gmail.com> Update copyright dates Disable load0 test Add version 2.2 entry in NEWS Update references in ALGORITHM Deprecate `--exponential' * build-aux/pretty-usage.pl, man/lbzip2.1: Update `--exponential' info. * src/main.c, src/lbzip2.c, src/lbzip2.h: Drop support for exponential. 2012-01-09 MikoÅaj Izdebski <zurgunt@gmail.com> Fix undefined behavior in divsufsort * yambi/divsufsort.c (trsort): Add bounds checks before moving pointer beyond allocated space. Extend bugfix from ca8e703c * yambi/divsufsort.c: Apply patch provided by Yuta Mori. Fix a bug with sorting periodic strings yambi/divsufsort.c (tr_introsort): Add depth condition. Integrate divsufsort with yambi * yambi/collect.c, yambi/encode.h: Let mtfv[] and SA[] share space and block[] be a separate array. * yambi/encode.c: Use divsufsort instead of old blocksort code. Adjust divsufsort to yambi * yambi/divsufsort.c: Remove include guardians. Define sauchar_t, saint_t and saidx_t in terms of <inttypes.h>. Remove __inline. (MAX): Remove unused macro. (construct_SA): Remove unused function. (construct_BWT): Remove unused parameter `m'. (cyclic_divsufsort): Remove unused function. (cyclic_divbwt): Write resulting BWT transform to SA[] instead of separate output array. Replace malloc() with xmalloc(). Optimize code for case with no B* suffixes. * yambi/divsufsort.h: Remove C++ code. Remove unused prototype. Import code from cyclic-divsufsort-lite yambi/divsufsort.c, yambi/divsufsort.h: New files. Remove existing block-sorting code yambi/blocksort.c, yambi/sais.c: Remove files. 2012-01-07 MikoÅaj Izdebski <zurgunt@gmail.com> Integrate new block-sorting code with yambi yambi/collect.c: Share block[] and mtfv[] space for better cache perfoemance and lower memory usage. yambi/encode.c: Read BWT characters from bwt[] and not block[]. yambi/encode.h: Add YBpriv_sais() prototype. Add bwt field to YBenc_s. yambi/private.h: Implement peekb() and pokeb() macros. build-aux/style-check.pl, yambi/Makefile.am: Mention yambi/sais.c. Refactor block-sorting code yambi/blocksort.c: Refactor quicksort and bucket sort code for better readability. Remove BPR code. Remove code copyrighted by Juliad Seward and the corresponding license block. Import cyclic-sais yambi/sais.c: Import from cyclic-sais 1.0 by Yuta Mori. 2011-12-25 Mikolaj Izdebski <zurgunt@gmail.com> Remove unused constants * src/lbunzip2.c: Remove magic_mask and magic_hdr definitions. Remove unused constant definition * yambi/yambi.h: Remove YB_CANCELED macro definition. 2011-12-23 Mikolaj Izdebski <zurgunt@gmail.com> Import new test case -- load0 * tests/load0.bz2: Initial version. * tests/Makefile.am: Add load0.bz2 as a new test. Limit time and memory usage during tests * tests/timeout.c: Initial version. * tests/Makefile.am: Build timeout from timeout.c. * tests/Tester: Try limiting virtual memory usage with `ulimit -v'. Run decompresion subprocesses with alarm set to 1 minute. Make minbzcat be more compatible with bzip2 * tests/minbzcat.c (main): Count block size digit as part of stream header. Fixes #3. Add check for fatal signals in tester * tests/Tester: Add checks for subprocess exit codes >= 128. All tests in which either lbzip2 or minbzcat exited because of unhandled signals are treated as failed. 2011-12-04 MikoÅaj Izdebski <zurgunt@gmail.com> Add two more test cases. * tests/incomp: Initial version. * tests/incomp-1.bz2, tests/incomp-2.bz2: Generate using tests/incomp. * tests/README: Update to mention incomp-[12].bz2. * tests/Makefile.am: Add the new test cases. Fix bug #5 * src/lbunzip2.c (work_decompr): Assign w2w_blk->bs100k to w2m_blk->bs100k only if YB_OK == ybret. Fixes: #5. This bug caused files with input blocks larger than 1 MiB to be rejected by lbunzip2. * tests/ch255.bz2: Add as a regression test for bug #5. * tests/Makefile.am: Re-enable crc1.bz2, add ch255.bz2. Workaround bug #5 * src/lbunzip2.c (mux): Disable stream CRC check. Fixes #5. * tests/Makefile.am: Exclude crc1.bz2 from test cases. 2011-11-24 MikoÅaj Izdebski <zurgunt@gmail.com> Get rid of AM_MAINTAINER_MODE * configure.ac: Remove AM_MAINTAINER_MODE, which was included by accident. 2011-11-23 MikoÅaj Izdebski <zurgunt@gmail.com> Bump version to 2.1 Fix a use-after-free vulnerability in lbunzip2 * src/lbunzip2.c (work_retrieve.c): Move access to s2w_blk before work_release() call. Fixes #4. 2011-11-11 MikoÅaj Izdebski <zurgunt@gmail.com> Fix build error on OpenBSD 5.0 * src/main.c (opts_setup): Use _SC_THREAD_THREADS_MAX conditionally. 2011-11-05 MikoÅaj Izdebski <zurgunt@gmail.com> Update autogen.sh to remove gitlog-to-changelog * build-aux/autogen.sh: Remove gitlog-to-changelog with -r option. 2011-11-02 MikoÅaj Izdebski <zurgunt@gmail.com> Update and improve documentation * README: Add Laszlo Ersek's copyright notice. * yambi/blocksort.c: Add example Manber-Myers algorithm implementation. 2011-10-31 MikoÅaj Izdebski <zurgunt@gmail.com> Include ChangeLog.old in tarball * Makefile.am: Add ChangeLog.old to EXTRA_DIST. Create changelogs * build-aux/autogen.sh: Add gitlog-to-changelog Gnulib module. * ChangeLog.old: Import from v0.23. * ChangeLog: Generate with build-aux/gitlog-to-changelog. 2011-10-30 MikoÅaj Izdebski <zurgunt@gmail.com> Minor documentation cleanup Add BOOTSTRAP Add filenames and short desc to license blocks Run automated spelling check Make tests/Tester more portable 2011-10-29 MikoÅaj Izdebski <zurgunt@gmail.com> Make install and uninstall targets work Add list of subdirs to README Extend AUTHORS Import ALGORITHM Add a minimal README Cleanup manpage 2011-10-28 MikoÅaj Izdebski <zurgunt@gmail.com> Add scantab.h to noinst_HEADERS 2011-10-27 MikoÅaj Izdebski <zurgunt@gmail.com> Minor code cleanups to avoid gcc warnings * Add extra braces in generated scantab.h * Add __attribute__((printf, ...)) to log_fatal() * Add extra switch case in lbunzip2 parser Make file sizes unsigned integers (uintmax_t) Remove SETX from lbunzip2 2011-10-23 MikoÅaj Izdebski <zurgunt@gmail.com> Fix Tester to support VPATH builds Display progress info during decompression Improve error messages in lbunzip2 muxer Move progress info printing code to main.c Fix a bug that prevented VPATH build from working Reimplement lbunzip2 magic pattern scanner as DFA 2011-10-22 MikoÅaj Izdebski <zurgunt@gmail.com> Cleanup and improve lbunzip2 header parser Improvements implemented: * block overruns are detected (fixes `overrun.bz2') * stream CRCs are computed and checked (fixes `crc1.bz2') * initial stream headers are parsed (fixes `trash.bz2' and `void.bz2') * files with gaps between streams are rejected (fixes `gap.bz2') * minor speed enchancements NEWS were updated to reflect recent improvements. 2011-10-22 MikoÅaj Izdebski <zurgunt@gmail.com> Implement initial header parser for lbunzip2 Partly fixes `gap.bz2' bug. For now the parser isn't detecting parse errors and parsing results (CRC and bs100k) are unused. Reorder scanner code in lbunzip2.c Pad lbunzip2 input blocks to multiple of 32 bits 2011-10-20 MikoÅaj Izdebski <zurgunt@gmail.com> Add more files to EXTRA_DIST Fix a typo in style-check.pl naming. 2011-10-18 MikoÅaj Izdebski <zurgunt@gmail.com> Fix a minor bug in autogen.sh 2011-10-17 MikoÅaj Izdebski <zurgunt@gmail.com> Reimplement BPR algorithm 2011-10-13 MikoÅaj Izdebski <zurgunt@gmail.com> Improve comments in blocksort.c, prefix.c and retrieve.c 2011-10-08 Laszlo Ersek <lacos@caesar.elte.hu> trivial typo fix in man page 2011-10-07 MikoÅaj Izdebski <zurgunt@gmail.com> Fix -Wno-unknown-warning-option Narrow usage text width to 79 characters Add missing _Noreturn attributes Add -Wno-unknown-warning-option for clang Remove Trace() macros Turn off warnings about unreachable code Link lbunzip2 and lbzcat manpages to lbzip2 Use uintmax_t for block identifiers Import a newer version of minbzcat 2011-10-04 MikoÅaj Izdebski <zurgunt@gmail.com> Unset LBZIP2 et al. in tests/Tester Import and extend lbzip2 manpage 2011-09-27 MikoÅaj Izdebski <zurgunt@gmail.com> Print version and usage info on stdout, not stderr Add build-aux/pretty-usage.pl to help maintaining usage message. 2011-09-23 MikoÅaj Izdebski <zurgunt@gmail.com> autogen.sh: set IFS to space-tab-newline Add make-crctab.pl Style fixups based on style-check.pl report Add build-aux/style-check.pl 2011-09-22 MikoÅaj Izdebski <zurgunt@gmail.com> Move autogen.sh to build-aux/ Fix a bug with displaying an error message 2011-09-20 MikoÅaj Izdebski <zurgunt@gmail.com> Fix a typo in tests/cve.c A typo in tests/cve.c caused tests/cve.bz2 to be invalid. Update both. 2011-09-19 MikoÅaj Izdebski <zurgunt@gmail.com> minbzcat: add checks for Kraft's inequality Fix a typo in yambi/Makefile.am Write initial NEWS Import basic test cases Add noinst_HEADERS in src and yambi subdirs 2011-09-14 MikoÅaj Izdebski <zurgunt@gmail.com> Replace AC_SYS_LARGEFILE with largefile Gnulib module Downgrade to autoconf 2.67 to ease development on Debian stable. Import realloc-gnu module. Remove redundant checks from configure.ac. 2011-09-12 MikoÅaj Izdebski <zurgunt@gmail.com> Rename the project back to lbzip2 2011-09-11 MikoÅaj Izdebski <zurgunt@gmail.com> In lbunzip2 initialise `scan' with all ones, not all zeros This decreases probability of finding false-positives when looking for the magic bit pattern. Remove split_chkstart() Upcoming stream parser obsoletes split_chkstart(). Prioritize decompressing earlier blocks Decompress retrieved blocks basing on their position within the stream, not FCFS. Replace lacos_rbtree with pqueue Fix a bug related to htonl() usage Drop fupport for LBZIP2_TRACE_ALLOC Replace home-made xalloc() with xmalloc() provided by Gnulib. Disable compiler warnings about aggregate return 2011-09-10 MikoÅaj Izdebski <zurgunt@gmail.com> Reduce memory usage during decompression 2011-09-09 MikoÅaj Izdebski <zurgunt@gmail.com> Remove emacs file variables Add missing copyright notices Implement smarter scanner in lbunzip2 Redesign yambi's retrieve pass. Remove IBS structure and related functions from yambi API. Perform yambi's retrieve pass directly during lbunzip2's scan pass and not during decompress pass. 2011-09-07 MikoÅaj Izdebski <zurgunt@gmail.com> Read 32 bits at time in lbunzip2 Add #include <sys/types.h> for size_t Include sys/types.h instead of stddef.h for size_t. Guard config.h inclusions Surround #include <config.h> with #ifdef HAVE_CONFIG_H. Make use of SIZE_MAX Replace (size_t)-1 with SIZE_MAX. Improve configure.ac Added -r option to autogen.sh Delete corr-perf.sh, malloc_trace.pl and test.sh Optimize lbunzip2 state machine 2011-08-28 MikoÅaj Izdebski <zurgunt@gmail.com> Restore atime and mtime with nanosec accuracy Convert gettimeofday() calls to gettime() Don't display file name with progress info 2011-08-26 MikoÅaj Izdebski <zurgunt@gmail.com> Add a configure switch to enable warnings 2011-08-25 MikoÅaj Izdebski <zurgunt@gmail.com> Rename to bzimp2 Update externally visible names to bzimp2. Remove man page. Split usage and version printing options. Fix GCC compatibility bugs 2011-08-23 MikoÅaj Izdebski <zurgunt@gmail.com> Remove .cvsignore Add more checks to configure.ac 2011-08-20 MikoÅaj Izdebski <zurgunt@gmail.com> Include <config.h> in all source files Replace utime() with fdutimens() Create autogen.sh Migrate to GNU build system Move lbzip2 source files to "src" subdirectory. Remove Makefiles. Create initial "configure.ac" and "Makefile.am" files. 2011-08-19 MikoÅaj Izdebski <zurgunt@gmail.com> Display progress info during compression Display compression ratio in verbose mode 2011-08-16 MikoÅaj Izdebski <zurgunt@gmail.com> Remove redundant includes 2011-08-15 MikoÅaj Izdebski <zurgunt@gmail.com> Fix a compatibility bug 2011-08-14 MikoÅaj Izdebski <zurgunt@gmail.com> Add support for decompressing randomized blocks 2011-08-13 MikoÅaj Izdebski <zurgunt@gmail.com> Minor comments and code cleanup Add more coments on prefix code decoding. Remove a potential incompatibility with platforms that don't use U2 encoding for signed integers. Remove unused auto variables. Replace loops zeroing bigger arrays with calls to bzero(). 2011-08-12 MikoÅaj Izdebski <zurgunt@gmail.com> Minor formatting cleanup Eliminate SIZES() macro Get rid of SIZES() to simplify the code. Introduce xread() and xwrite() Generalize existing I/O code and create xread() and xwrite() to ease maintaintenance. Pack "fd", "sep" and "fmt" into struct filespec to emphasise their close relationship and simplify the code. 2011-08-11 MikoÅaj Izdebski <zurgunt@gmail.com> Clean up the code Minor code cleanups: * move nested function declaration to global scope, * convert K&R function definitions to ANSI, * move common macros to header file, * remove unused auto variables, * make pointer casts not strip the const qualifier, * change some variable types between signed and unsigned, * add missing copyright notices, * correct intentation in lbzip2.c, * remove white spaces from end of lines, * replace tabs by spaces (except from Makefiles). Improve compression performance The main block sorting algorithm is reworked to behave better in average case while remaining fast enough in the worst case. 2011-08-09 MikoÅaj Izdebski <zurgunt@gmail.com> Make decompression error messages more datailed Implement Yberr_detail() -- a function returning a textual representation of decompression error codes. Make use of Yberr_detail() in lbunzip2.c. 2011-07-30 MikoÅaj Izdebski <zurgunt@gmail.com> Fix a buffer overflow in yambi decompression code Fix a security vulnerability. A specially crafted compressed file could potentially cause a buffer overflow in YBibs_retrieve. Some minor optimizations and cleanups: * utilize htonl() and nothl() for (hopefully) faster memory access * remove outdated code that wasn't used anyways * change default values of some yambi tuning parameters * reorder some struct members; move bigger arrays to the end * remove some automatic variables to reduce register pollution 2011-07-30 MikoÅaj Izdebski <zurgunt@gmail.com> Fix a bug in sorting algorithm implementation Fix a bug in main sorting algorithm implementation. Fix two different bugs Fix a bug in decompression code that was caused by a typo. Fix a compatibility issue in yambi/private.h. 2011-07-29 MikoÅaj Izdebski <zurgunt@gmail.com> Fix a bug in lbzip2 compresion code This commit fixes a bug that was introduced in the previous commit. Minor enchancements: * implement --exponential command line switch with the same semantics as bzip2's equivalent * reduce average-case memory consumption in compression mode by about 3.5 MB per worker Minor cleanups: * remove unused code * remove whitespaces from end of source code lines * replace some tabs with spaces * correct line indentation * remove bogus __builtin_prefetch'es * remove GPLv2 as now the code in under GPLv3+ only * remove README as it doesn't reflect current code * remove ChangeLog as it was obsoleted by migration to git 2011-07-28 MikoÅaj Izdebski <zurgunt@gmail.com> Import a newer version of yambi Import a newer version of yambi, which contains compression code. Remove libbz2 compatibility layer from yambi. Modify lbzip2 and lbunzip2 so that they use yambi's API directly, without the compatibility layer. Update Makefiles. Remove dependency on libbz2. Remove lbunzip2_single Remove lbunzip2_single, as upcoming sequential decompressor is obsoleting it. 2011-07-26 Laszlo Ersek <lacos@caesar.elte.hu> base decompression on newly imported yambi Import yambi. Adapt Makefiles and decompression modules. import lbzip2-0.23