[SCM] Samba Shared Repository - branch master updated
Joseph Sutton
jsutton at samba.org
Fri Dec 2 00:01:02 UTC 2022
The branch, master has been updated
via d9c192546fa lib/compression/lzxpress: fix our slow compression
via caa643e36e6 lib/compression/lzxpress: shift encoding into helper functions
via fb35cf29a42 lib/compression/lzxpress compression: use a write context struct
via e4066b2be6d lib/compression: more tests for lzxpress plain compression
via c0f28d71858 lib/compression: add test data for lzxpress plain compression
via ce7ea07d073 testdata: move compression examples to re-use with lzxpress plain
via 9589f5282b9 lib/compression/lzx-plain: relax size requirements on long file
via c2db7fda4e3 lib/comression: convert test_lzxpress_plain to cmocka
via 1f0aea77f5c selftest: be less confident in commending st/summary
via e5f9deed0d5 lib/compression: add test scripts README
via 1a3d8da7313 lib/compression: test util to generate fuzzing seeds
via 6a7c0ca23c6 lib/compression: Windows utility to generate test vectors
via 7804570a379 lib/compression: script to test 3 byte hash
via dadecede544 lib/compression: helper script to make unbalanced data
via bce33816ec9 lib/compression: add a debug script to describe headers
via e58e9935047 fuzz: add fuzz_lzxpress_huffman_round_trip
via 307aded670c fuzz: add fuzz_lzxpress_huffman_compress
via cda3c1a2270 fuzz: add fuzz_lzxpress_huffman_decompress
via e795985067e lib/compression/tests: add lzhuffman timer functions
via 77048aaa61e lib/compression: debug routines for lzxpress-huffman
via 955214ef6ec lib/compression/lzhuff: add debug flag to skip LZ77
via d4e3f0c88ef lib/compression: LZ77 + Huffman compression
via f86035c65bf lib/compression: add LZ77 + Huffman decompression
via bd35feaf7ed testdata: add test vectors for LZ77+Huffman [de-]compression
via 7cff3ce2843 test/source_chars: ignore testdata/compression
via f6cda06dfb7 lib/compression: move lzxpress_plain test into tests/
via e24efb88ef5 fuzz: add fuzzers for stable_sort
via 4e18e923999 util: add stable sort functions
from 39df9f4a593 s3: smbd: Fix schedule_smb2_aio_read() to allow the last read in a compound to go async.
https://git.samba.org/?p=samba.git;a=shortlog;h=master
- Log -----------------------------------------------------------------
commit d9c192546faca3b4b692738249f552b78e72d83a
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Fri Nov 25 12:46:08 2022 +1300
lib/compression/lzxpress: fix our slow compression
This uses the same hash table method as lzxpress_huffman, though the
code can't be directly reused as the sizes of the offsets is
different, and there is not a block processing step here.
This will worsen the compression ratio compared to the exhaustive
search we previously used, though we still perform better than
Windows. To put numbers on it, the test files used to compress to 0.91
of Windows' compression size, and now they compress to 0.96.
On the other hand this is many orders of magnitude faster. It is
difficult to say exactly how much faster -- while the testsuite time
has only improved 200-fold (from 7 minutes to 2 seconds), most of the
remaining 2 seconds is used in data generation and management, not
compression. OSSFuzz consistently finds new vectors that time out
after a minute; on these we'll see nearly an order of magnitude of
orders of magnitude inprovement.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
Autobuild-User(master): Joseph Sutton <jsutton at samba.org>
Autobuild-Date(master): Fri Dec 2 00:00:04 UTC 2022 on sn-devel-184
commit caa643e36e671be9cb446afc99dfae3003aa8c6e
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Fri Nov 25 12:38:11 2022 +1300
lib/compression/lzxpress: shift encoding into helper functions
This makes it easier to rework the encoding decision to depend on a
hash table match rather than the current exhaustive search.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit fb35cf29a426ee2cb0ee280e147627fd3e84a71d
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Nov 17 16:15:00 2022 +1300
lib/compression/lzxpress compression: use a write context struct
This will make it possible to move encoding operations into helper
functions, which will make it easier to restructure the code to use a
hash table for faster matching.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit e4066b2be6d87cae130f40e3faf3a0c8815389f8
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Nov 24 11:44:35 2022 +1300
lib/compression: more tests for lzxpress plain compression
These are based on (i.e. copied and pasted from) the LZ77 + Huffman
tests.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit c0f28d71858a0fd3035971ca4f2f5a6af6d450b6
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Nov 24 22:51:01 2022 +1300
lib/compression: add test data for lzxpress plain compression
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit ce7ea07d073ed7169073a1870b61533b7f6f769b
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Nov 24 11:11:15 2022 +1300
testdata: move compression examples to re-use with lzxpress plain
Everything that is in testdata/compression/lzxpress-huffman/ can also
be used for lzxpress plain tests, which is something we really need.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit 9589f5282b9e2adfacd7e1cfdc2651551c4c6702
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Nov 23 13:06:41 2022 +1300
lib/compression/lzx-plain: relax size requirements on long file
We are going to change from a slow exact match algorithm to a fast
heuristic search that will not always get the same results as the
exhaustive search.
To be precise, a million zeros will compress to 112 rather than 93 bytes.
We don't insist on an exact size, because that is not an issue here.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit c2db7fda4e3af571b3b63b753b98517ac948b006
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Nov 23 12:01:15 2022 +1300
lib/comression: convert test_lzxpress_plain to cmocka
Mainly so I can go
make bin/test_lzxpress_plain && bin/test_lzxpress_plain
valgrind bin/test_lzxpress_plain
rr bin/test_lzxpress_plain
rr replay
in a tight loop.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit 1f0aea77f5c065b1af069d09c1044a6e8de6261d
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Fri Nov 18 12:45:12 2022 +1300
selftest: be less confident in commending st/summary
st/summary is useless. If you'll find anything, it'll be in st/subunit.
However, in case *something* useful ever ends up there we still mention it.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit e5f9deed0d5a2b475361486b48095124a973bd71
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Mon Nov 21 11:25:20 2022 +1300
lib/compression: add test scripts README
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit 1a3d8da731320a3422fd6d093cd20beb9ff00167
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Mon Nov 21 10:17:54 2022 +1300
lib/compression: test util to generate fuzzing seeds
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit 6a7c0ca23c6e5a4cc5ba2f860b988269306697fa
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Tue Nov 22 08:49:39 2022 +1300
lib/compression: Windows utility to generate test vectors
If compiled on Windows using Cygwin, MSYS2, or similar, this will output
compressed versions of files exactly as specified by MZ-XCA, if the
following conditions are met:
1. The file > 300 bytes.
2. The compressed file is smaller than the decompressed file.
Otherwise it returns the data unchanged. Without warning; that's just
how the API works.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit 7804570a379f29809a0b7540b6d94abc51d4046c
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Tue Nov 22 08:35:14 2022 +1300
lib/compression: script to test 3 byte hash
Compression uses a 3 byte hash remember LZ77 matches in a 14-bit table.
This script runs the hash over all 16M combinations, then again over
all ASCII combinations, counting collisions to find hot-spots.
If you think you have a better hash, you are probably right, but you
should try it here -- alter h() -- before committing to it. This one is
literally the first one I thought of.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit dadecede544519e4747a8623a1f5e0d0a1450002
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Tue Nov 22 08:23:30 2022 +1300
lib/compression: helper script to make unbalanced data
Huffman tree re-quantisation and perhaps other code paths are only
triggered by pathological data like this.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit bce33816ec9160373110f0ccbf3174c301218c9a
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Nov 17 20:02:21 2022 +1300
lib/compression: add a debug script to describe headers
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit e58e9935047e3d0c3a1965f04326798f7eb7e1f9
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Nov 17 16:09:39 2022 +1300
fuzz: add fuzz_lzxpress_huffman_round_trip
This compresses some data, decompresses it, and asserts that the
result is identical to the original string.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit 307aded670c6a32620e45c16d2d7e447dda1b061
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Nov 17 16:09:26 2022 +1300
fuzz: add fuzz_lzxpress_huffman_compress
This differs from fuzz_lzxpress_huffman_round_trip (next commit) in
that the output buffer might be too small for the compressed data, in
which case we want to see an error and not a crash.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit cda3c1a22706ea1b4ebfb2f2faacf03bb6192fc9
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Nov 17 16:08:52 2022 +1300
fuzz: add fuzz_lzxpress_huffman_decompress
Most strings will not successfully decompress, which is OK. What we
care about of course is memory safety.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit e795985067eb881b857d711f23ac462adb45d052
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Fri Nov 18 09:54:57 2022 +1300
lib/compression/tests: add lzhuffman timer functions
With LZXHUFF_DEBUG_VERBOSE set, we measure the compression and
decompression rate relative to the decompressed size.
On reasonably long strings on my laptop, compiled with -O0, it turns
out to between 20 and 500 MB/s, both ways, depending on the complexity
of the string. Very short strings are of course dominated by overhead.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit 77048aaa61eaf29934cb9446fc552b0c44431f76
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Fri Nov 18 15:54:37 2022 +1300
lib/compression: debug routines for lzxpress-huffman
If you need to see a Huffman tree (and sometimes you do), set
DEBUG_HUFFMAN_TREE to true at the top of lzxpress_huffman.c, and run:
make bin/test_lzx_huffman && bin/test_lzx_huffman
Actually, that will show you hundreds of trees, and you'll be glad of
that if you are ever trying to understand this.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit 955214ef6ec0015d8c1e1f8a43cacdf239b4d253
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Mon Nov 21 10:23:53 2022 +1300
lib/compression/lzhuff: add debug flag to skip LZ77
Encoding without LZ77 matches is valid, and it is useful for isolating
bugs.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit d4e3f0c88ef6f9fdc03ef63c8b45a88ab581f854
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Nov 17 23:14:58 2022 +1300
lib/compression: LZ77 + Huffman compression
This compresses files as described in MS-XCA 2.2, and as decompressed
by the decompressor in the previous commit.
As with the decompressor, there are two public functions -- one that
uses a talloc context, and one that uses pre-allocated memory. The
compressor requires a tightly bound amount of auxillary memory
(>220kB) in a few different buffers, which is all gathered together in
the public struct lzxhuff_compressor_mem. An instantiated but not
initialised copy of this struct is required by the non-talloc
function; it can be used over and over again.
Our compression speed is about the same as the decompression speed
(between 20 and 500 MB/s on this laptop, depending on the data), and
our compression ratio is very similar to that of Windows.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit f86035c65bf4ae41a2c210dbff132dbce499f03c
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Nov 17 14:24:52 2022 +1300
lib/compression: add LZ77 + Huffman decompression
This format is described in [MS-XCA] 2.1 and 2.2, with exegesis in
many posts on the cifs-protocol list[1].
The two public functions are:
ssize_t lzxpress_huffman_decompress(const uint8_t *input,
size_t input_size,
uint8_t *output,
size_t output_size);
uint8_t *lzxpress_huffman_decompress_talloc(TALLOC_CTX *mem_ctx,
const uint8_t *input_bytes,
size_t input_size,
size_t output_size);
In both cases the caller needs to know the *exact* decompressed size,
which is essential for decompression. The _talloc version allocates
the buffer for you, and uses the talloc context to allocate a 128k
working buffer. THe non-talloc function will allocate the working
buffer on the stack.
This compression format gives better compression for messages of
several kilobytes than the "plain" LXZPRESS compression, but is
probably a bit slower to decompress and is certainly worse for very
short messages, having a fixed 256 byte overhead for the first Huffman
table.
Experiments show decompression rates between 20 and 500 MB per second,
depending on the compression ratio and data size, on an i5-1135G7 with
no compiler optimisations.
This compression format is used in AD claims and in SMB, but that
doesn't happen with this commit.
I will not try to describe LZ77 or Huffman encoding here. Don't expect
an answer in MS-XCA either; instead read the code and/or Wikipedia.
[1] Much of that starts here:
https://lists.samba.org/archive/cifs-protocol/2022-October/
but there's more earlier, particularly in June/July 2020, when
Aurélien Aptel was working on an implementation that ended up in
Wireshark.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Pair-programmed-with: Joseph Sutton <josephsutton at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit bd35feaf7ed649968465a2643b42982d3e6f3d56
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Nov 17 16:07:08 2022 +1300
testdata: add test vectors for LZ77+Huffman [de-]compression
Some of the decompressed files were found via fuzzing, some are public
domain texts, and some are designed to test one aspect or another of
the format. For example, some aspects of Huffman tree creation can
only be tested when there is an extreme imbalance in the frequency of
symbols.
See the README for what files are where.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit 7cff3ce28432124f46a5367ee085e460cd5fd9c6
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Nov 23 12:10:20 2022 +1300
test/source_chars: ignore testdata/compression
We are going to have all kinds of rubbish there.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit f6cda06dfb7e6555f817774a1535f4540b57ede4
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Thu Nov 17 16:07:37 2022 +1300
lib/compression: move lzxpress_plain test into tests/
We are going to add more tests for lib/compression, and they can't all
be called "testsuite.c".
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit e24efb88ef5abc794612dae546c5dce37615d2d9
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Nov 30 16:59:51 2022 +1300
fuzz: add fuzzers for stable_sort
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
commit 4e18e9239995b48744cca613e0a83e057d899480
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed Sep 28 14:40:10 2022 +1300
util: add stable sort functions
Sometimes (e.g. in lzxpress Huffman encoding, and in some of our
tests: c.f. https://lists.samba.org/archive/samba-technical/2018-March/126010.html)
we want a stable sort algorithm (meaning one that retains the previous
order of items that compare equal).
The GNU libc qsort() is *usually* stable, in that it first tries to
use a mergesort but reverts to quicksort if the necessary allocations
fail. That has led Samba developers to unthinkingly assume qsort() is
stable which is not the case on many platforms, and might not always
be on GNU/Linuxes either.
This adds four functions. stable_sort() sorts an array, and requires
an auxiliary working array of the same size. stable_sort_talloc()
takes a talloc context so it ca create a working array and call
stable_sort(). stable_sort_r() takes an opaque context blob that gets
passed to the compare function, like qsort_r() and ldb_qsort(). And
stable_sort_talloc_r() rounds out the quadrant.
These are LGPL so that the can be used in ldb, which has problems with
unstable sort.
The tests are borrowed and extended from test_ldb_qsort.c.
When sorting non-trivial structs this is roughly as fast as GNU qsort,
but GNU qsort has optimisations for small items, using direct
assignments of rather than memcpy where the size allows the item to be
cast as some kind of int.
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
-----------------------------------------------------------------------
Summary of changes:
lib/compression/lzxpress.c | 418 +-
lib/compression/lzxpress_huffman.c | 2020 +++++++
lib/compression/lzxpress_huffman.h | 87 +
lib/compression/tests/scripts/README | 19 +
.../tests/scripts/decode-huffman-header | 54 +
.../tests/scripts/generate-windows-test-vectors.c | 206 +
lib/compression/tests/scripts/make-fuzz-examples | 45 +
lib/compression/tests/scripts/make-test-vectors | 185 +
lib/compression/tests/scripts/three-byte-hash | 49 +
lib/compression/tests/test_lzx_huffman.c | 1250 +++++
lib/compression/tests/test_lzxpress_plain.c | 1179 +++++
lib/compression/testsuite.c | 483 --
lib/compression/wscript_build | 20 +-
lib/fuzzing/fuzz_lzxpress_huffman_compress.c | 58 +
lib/fuzzing/fuzz_lzxpress_huffman_decompress.c | 48 +
lib/fuzzing/fuzz_lzxpress_huffman_round_trip.c | 68 +
lib/fuzzing/fuzz_stable_sort.c | 88 +
lib/fuzzing/fuzz_stable_sort_r.c | 69 +
lib/fuzzing/wscript_build | 25 +
lib/util/stable_sort.c | 250 +
lib/util/stable_sort.h | 46 +
lib/util/tests/test_stable_sort.c | 317 ++
lib/util/wscript_build | 13 +
python/samba/tests/source_chars.py | 1 +
python/samba/tests/usage.py | 1 +
selftest/format-subunit | 4 +-
selftest/tests.py | 8 +
source4/torture/local/local.c | 1 -
source4/torture/local/wscript_build | 2 +-
testdata/compression/README | 47 +
.../compressed-huffman/27826-8.txt.lzhuff | Bin 0 -> 8748 bytes
.../5d049b4cb1bd933f5e8ex19.lzhuff | Bin 0 -> 265 bytes
.../638e61e96d54279981c3x5.lzhuff | Bin 0 -> 278 bytes
.../compressed-huffman/64k-minus-one-zeros.lzhuff | Bin 0 -> 263 bytes
.../compressed-huffman/64k-plus-one-zeros.lzhuff | Bin 0 -> 263 bytes
.../compressed-huffman/64k-zeros.lzhuff | Bin 0 -> 263 bytes
.../96f696a4e5ce56c61a3dx10.lzhuff | Bin 0 -> 271 bytes
.../compressed-huffman/9e0b6a12febf38e98f13.lzhuff | Bin 0 -> 614 bytes
.../compressed-huffman/abc-times-101.lzhuff | Bin 0 -> 263 bytes
.../compressed-huffman/abc-times-105.lzhuff | Bin 0 -> 263 bytes
.../compressed-huffman/abc-times-200.lzhuff | Bin 0 -> 263 bytes
.../compressed-huffman/and_rand-128k+.lzhuff | Bin 0 -> 108514 bytes
.../compression/compressed-huffman/and_rand.lzhuff | Bin 0 -> 54150 bytes
.../compressed-huffman/b63289ccc7f218c0d56b.lzhuff | Bin 0 -> 686 bytes
.../compressed-huffman/beta-variate1-128k+.lzhuff | Bin 0 -> 74064 bytes
.../compressed-huffman/beta-variate2-128k+.lzhuff | Bin 0 -> 115548 bytes
.../compressed-huffman/beta-variate3-128k+.lzhuff | Bin 0 -> 73006 bytes
.../decayed_alphabet_128k+.lzhuff | Bin 0 -> 2554 bytes
.../compressed-huffman/decayed_alphabet_64k.lzhuff | Bin 0 -> 2138 bytes
.../compressed-huffman/exp_shuffle-128k+.lzhuff | Bin 0 -> 101510 bytes
.../compressed-huffman/exp_shuffle.lzhuff | Bin 0 -> 50674 bytes
.../compressed-huffman/f00842317dc6d5695b02.lzhuff | Bin 0 -> 2112 bytes
.../compressed-huffman/fib_shuffle-128k+.lzhuff | Bin 0 -> 57818 bytes
.../compressed-huffman/fib_shuffle.lzhuff | Bin 0 -> 28696 bytes
.../fuzzing-0fc2d461b56cd8103c91.lzhuff | Bin 0 -> 570 bytes
.../fuzzing-17c961778538cc10ab7c.lzhuff | Bin 0 -> 91524 bytes
.../fuzzing-3591f9dc02bb00a54b60.lzhuff | Bin 0 -> 9622 bytes
.../fuzzing-3ec3bca27bb9eb40c128.lzhuff | Bin 0 -> 35282 bytes
.../fuzzing-80b4fa18ff5f8dd04862.lzhuff | Bin 0 -> 118567 bytes
.../fuzzing-a3115a81d1ac500318f9.lzhuff | Bin 0 -> 531 bytes
.../generate-windows-test-vectors.c.lzhuff | Bin 0 -> 2008 bytes
.../midsummer-nights-dream.txt.lzhuff | Bin 0 -> 52279 bytes
.../notes-on-the-underground.txt.lzhuff | Bin 0 -> 3931 bytes
.../compressed-huffman/pg22009.txt.lzhuff | Bin 0 -> 21407 bytes
.../repeating-exactly-64k.lzhuff | Bin 0 -> 295 bytes
.../compressed-huffman/repeating.lzhuff | Bin 0 -> 299 bytes
.../compressed-huffman/setup.log.lzhuff | Bin 0 -> 7101 bytes
.../compressed-huffman/skewed_choices-128k+.lzhuff | Bin 0 -> 127646 bytes
.../compressed-huffman/skewed_choices.lzhuff | Bin 0 -> 63676 bytes
.../slow-015ddc36a71412ccc50d.lzhuff | Bin 0 -> 83846 bytes
.../slow-100e9f966a7feb9ca40a.lzhuff | Bin 0 -> 52119 bytes
.../slow-2a671c3cff4f1574cbab.lzhuff | Bin 0 -> 52174 bytes
.../slow-33d90a24e70515b14cd0.lzhuff | Bin 0 -> 51927 bytes
.../slow-49d8c05261e3f412fc72.lzhuff | Bin 0 -> 53392 bytes
.../slow-50a249d2fe56873e56a0.lzhuff | Bin 0 -> 52414 bytes
.../slow-63e9f0b52235fb0129fa.lzhuff | Bin 0 -> 51941 bytes
.../slow-73b7f971d65908ac0095.lzhuff | Bin 0 -> 46251 bytes
.../slow-8b61e3dd267908544531.lzhuff | Bin 0 -> 83836 bytes
.../slow-9d1c5a079b0462986f1f.lzhuff | Bin 0 -> 53281 bytes
.../slow-aa7262a821dabdcf04a6.lzhuff | Bin 0 -> 51957 bytes
.../slow-b8a91d142b0d2af7f5ca.lzhuff | Bin 0 -> 28111 bytes
.../slow-c79142457734bbc8d575.lzhuff | Bin 0 -> 40555 bytes
.../slow-d736544545b90d83fe75.lzhuff | Bin 0 -> 87525 bytes
.../slow-e3b9bdfaed7d1a606fdb.lzhuff | Bin 0 -> 38611 bytes
.../slow-f3f1c02a9d006e5e1703.lzhuff | Bin 0 -> 84063 bytes
.../compressed-huffman/square_series-128k+.lzhuff | Bin 0 -> 122338 bytes
.../compressed-huffman/square_series.lzhuff | Bin 0 -> 61036 bytes
.../compressed-huffman/trigram_128k+.lzhuff | Bin 0 -> 51547 bytes
.../compressed-huffman/trigram_64k.lzhuff | Bin 0 -> 25390 bytes
.../compressed-huffman/trigram_sum_128k+.lzhuff | Bin 0 -> 83462 bytes
.../compressed-huffman/trigram_sum_64k.lzhuff | Bin 0 -> 40577 bytes
.../compressed-more-huffman/27826-8.txt.lzhuff | Bin 0 -> 7630 bytes
.../5d049b4cb1bd933f5e8ex19.lzhuff | Bin 0 -> 265 bytes
.../638e61e96d54279981c3x5.lzhuff | Bin 0 -> 278 bytes
.../64k-minus-one-zeros.lzhuff | Bin 0 -> 263 bytes
.../64k-plus-one-zeros.lzhuff | Bin 0 -> 263 bytes
.../compressed-more-huffman/64k-zeros.lzhuff | Bin 0 -> 263 bytes
.../96f696a4e5ce56c61a3dx10.lzhuff | Bin 0 -> 270 bytes
.../9e0b6a12febf38e98f13.lzhuff | Bin 0 -> 592 bytes
.../compressed-more-huffman/abc-times-101.lzhuff | Bin 0 -> 263 bytes
.../compressed-more-huffman/abc-times-105.lzhuff | Bin 0 -> 263 bytes
.../compressed-more-huffman/abc-times-200.lzhuff | Bin 0 -> 263 bytes
.../compressed-more-huffman/and_rand-128k+.lzhuff | Bin 0 -> 109624 bytes
.../compressed-more-huffman/and_rand.lzhuff | Bin 0 -> 54690 bytes
.../b63289ccc7f218c0d56b.lzhuff | Bin 0 -> 671 bytes
.../beta-variate1-128k+.lzhuff | Bin 0 -> 72416 bytes
.../beta-variate2-128k+.lzhuff | Bin 0 -> 116044 bytes
.../beta-variate3-128k+.lzhuff | Bin 0 -> 68622 bytes
.../decayed_alphabet_128k+.lzhuff | Bin 0 -> 2061 bytes
.../decayed_alphabet_64k.lzhuff | Bin 0 -> 1569 bytes
.../exp_shuffle-128k+.lzhuff | Bin 0 -> 102434 bytes
.../compressed-more-huffman/exp_shuffle.lzhuff | Bin 0 -> 51102 bytes
.../f00842317dc6d5695b02.lzhuff | Bin 0 -> 2093 bytes
.../fib_shuffle-128k+.lzhuff | Bin 0 -> 54528 bytes
.../compressed-more-huffman/fib_shuffle.lzhuff | Bin 0 -> 27080 bytes
.../generate-windows-test-vectors.c.lzhuff | Bin 0 -> 1830 bytes
.../midsummer-nights-dream.txt.lzhuff | Bin 0 -> 43420 bytes
.../notes-on-the-underground.txt.lzhuff | Bin 0 -> 3553 bytes
.../compressed-more-huffman/pg22009.txt.lzhuff | Bin 0 -> 18097 bytes
.../repeating-exactly-64k.lzhuff | Bin 0 -> 297 bytes
.../compressed-more-huffman/repeating.lzhuff | Bin 0 -> 301 bytes
.../compressed-more-huffman/setup.log.lzhuff | Bin 0 -> 5839 bytes
.../skewed_choices-128k+.lzhuff | Bin 0 -> 127654 bytes
.../compressed-more-huffman/skewed_choices.lzhuff | Bin 0 -> 63682 bytes
.../square_series-128k+.lzhuff | Bin 0 -> 122382 bytes
.../compressed-more-huffman/square_series.lzhuff | Bin 0 -> 61060 bytes
.../compressed-more-huffman/trigram_128k+.lzhuff | Bin 0 -> 40556 bytes
.../compressed-more-huffman/trigram_64k.lzhuff | Bin 0 -> 20157 bytes
.../trigram_sum_128k+.lzhuff | Bin 0 -> 69332 bytes
.../compressed-more-huffman/trigram_sum_64k.lzhuff | Bin 0 -> 34701 bytes
.../compressed-more-plain/27826-8.txt.lzplain | Bin 0 -> 8488 bytes
.../5d049b4cb1bd933f5e8ex19.lzplain | Bin 0 -> 15 bytes
.../638e61e96d54279981c3x5.lzplain | Bin 0 -> 37 bytes
.../64k-minus-one-zeros.lzplain | Bin 0 -> 11 bytes
.../64k-plus-one-zeros.lzplain | Bin 0 -> 11 bytes
.../compressed-more-plain/64k-zeros.lzplain | Bin 0 -> 11 bytes
.../96f696a4e5ce56c61a3dx10.lzplain | Bin 0 -> 23 bytes
.../9e0b6a12febf38e98f13.lzplain | Bin 0 -> 436 bytes
.../compressed-more-plain/abc-times-101.lzplain | Bin 0 -> 13 bytes
.../compressed-more-plain/abc-times-105.lzplain | Bin 0 -> 13 bytes
.../compressed-more-plain/abc-times-200.lzplain | Bin 0 -> 13 bytes
.../compressed-more-plain/and_rand-128k+.lzplain | Bin 0 -> 131095 bytes
.../compressed-more-plain/and_rand.lzplain | Bin 0 -> 65536 bytes
.../b63289ccc7f218c0d56b.lzplain | Bin 0 -> 509 bytes
.../beta-variate1-128k+.lzplain | Bin 0 -> 81558 bytes
.../beta-variate2-128k+.lzplain | Bin 0 -> 131095 bytes
.../beta-variate3-128k+.lzplain | Bin 0 -> 78614 bytes
.../decayed_alphabet_128k+.lzplain | Bin 0 -> 2046 bytes
.../decayed_alphabet_64k.lzplain | Bin 0 -> 1782 bytes
.../exp_shuffle-128k+.lzplain | 1 +
.../compressed-more-plain/exp_shuffle.lzplain | 1 +
.../f00842317dc6d5695b02.lzplain | Bin 0 -> 2090 bytes
.../fib_shuffle-128k+.lzplain | Bin 0 -> 64417 bytes
.../compressed-more-plain/fib_shuffle.lzplain | Bin 0 -> 32339 bytes
.../generate-windows-test-vectors.c.lzplain | Bin 0 -> 1982 bytes
.../midsummer-nights-dream.txt.lzplain | Bin 0 -> 49859 bytes
.../notes-on-the-underground.txt.lzplain | Bin 0 -> 4044 bytes
.../compressed-more-plain/pg22009.txt.lzplain | Bin 0 -> 21036 bytes
.../repeating-exactly-64k.lzplain | Bin 0 -> 63 bytes
.../compressed-more-plain/repeating.lzplain | Bin 0 -> 67 bytes
.../compressed-more-plain/setup.log.lzplain | Bin 0 -> 8790 bytes
.../skewed_choices-128k+.lzplain | 41 +
.../compressed-more-plain/skewed_choices.lzplain | 22 +
.../square_series-128k+.lzplain | Bin 0 -> 131095 bytes
.../compressed-more-plain/square_series.lzplain | Bin 0 -> 65536 bytes
.../compressed-more-plain/trigram_128k+.lzplain | Bin 0 -> 44192 bytes
.../compressed-more-plain/trigram_64k.lzplain | Bin 0 -> 22036 bytes
.../trigram_sum_128k+.lzplain | Bin 0 -> 86174 bytes
.../compressed-more-plain/trigram_sum_64k.lzplain | Bin 0 -> 41628 bytes
.../compressed-plain/27826-8.txt.lzplain | Bin 0 -> 11275 bytes
.../5d049b4cb1bd933f5e8ex19.lzplain | Bin 0 -> 17 bytes
.../638e61e96d54279981c3x5.lzplain | Bin 0 -> 37 bytes
.../compressed-plain/64k-minus-one-zeros.lzplain | Bin 0 -> 11 bytes
.../compressed-plain/64k-plus-one-zeros.lzplain | Bin 0 -> 11 bytes
.../compression/compressed-plain/64k-zeros.lzplain | Bin 0 -> 11 bytes
.../96f696a4e5ce56c61a3dx10.lzplain | Bin 0 -> 25 bytes
.../compressed-plain/9e0b6a12febf38e98f13.lzplain | Bin 0 -> 444 bytes
.../compressed-plain/abc-times-101.lzplain | Bin 0 -> 13 bytes
.../compressed-plain/abc-times-105.lzplain | Bin 0 -> 13 bytes
.../compressed-plain/abc-times-200.lzplain | Bin 0 -> 13 bytes
.../compressed-plain/and_rand-128k+.lzplain | Bin 0 -> 131095 bytes
.../compression/compressed-plain/and_rand.lzplain | Bin 0 -> 65536 bytes
.../compressed-plain/b63289ccc7f218c0d56b.lzplain | Bin 0 -> 517 bytes
.../compressed-plain/beta-variate1-128k+.lzplain | Bin 0 -> 95621 bytes
.../compressed-plain/beta-variate2-128k+.lzplain | Bin 0 -> 131095 bytes
.../compressed-plain/beta-variate3-128k+.lzplain | Bin 0 -> 86491 bytes
.../decayed_alphabet_128k+.lzplain | Bin 0 -> 2553 bytes
.../compressed-plain/decayed_alphabet_64k.lzplain | Bin 0 -> 2218 bytes
.../compressed-plain/exp_shuffle-128k+.lzplain | 1 +
.../compressed-plain/exp_shuffle.lzplain | 1 +
.../compressed-plain/f00842317dc6d5695b02.lzplain | Bin 0 -> 2113 bytes
.../compressed-plain/fib_shuffle-128k+.lzplain | Bin 0 -> 101050 bytes
.../compressed-plain/fib_shuffle.lzplain | Bin 0 -> 50469 bytes
.../fuzzing-0fc2d461b56cd8103c91.lzplain | Bin 0 -> 72 bytes
.../fuzzing-17c961778538cc10ab7c.lzplain | Bin 0 -> 131113 bytes
.../fuzzing-3591f9dc02bb00a54b60.lzplain | Bin 0 -> 10269 bytes
.../fuzzing-3ec3bca27bb9eb40c128.lzplain | Bin 0 -> 39095 bytes
.../fuzzing-a3115a81d1ac500318f9.lzplain | Bin 0 -> 30 bytes
.../generate-windows-test-vectors.c.lzplain | Bin 0 -> 2270 bytes
.../midsummer-nights-dream.txt.lzplain | Bin 0 -> 67316 bytes
.../notes-on-the-underground.txt.lzplain | Bin 0 -> 5053 bytes
.../compressed-plain/pg22009.txt.lzplain | Bin 0 -> 27487 bytes
.../compressed-plain/repeating-exactly-64k.lzplain | Bin 0 -> 63 bytes
.../compression/compressed-plain/repeating.lzplain | Bin 0 -> 67 bytes
.../compression/compressed-plain/setup.log.lzplain | Bin 0 -> 10387 bytes
.../compressed-plain/skewed_choices-128k+.lzplain | 41 +
.../compressed-plain/skewed_choices.lzplain | 22 +
.../slow-015ddc36a71412ccc50d.lzplain | Bin 0 -> 114011 bytes
.../slow-100e9f966a7feb9ca40a.lzplain | Bin 0 -> 86951 bytes
.../slow-2a671c3cff4f1574cbab.lzplain | Bin 0 -> 86927 bytes
.../slow-33d90a24e70515b14cd0.lzplain | Bin 0 -> 86926 bytes
.../slow-49d8c05261e3f412fc72.lzplain | Bin 0 -> 88572 bytes
.../slow-50a249d2fe56873e56a0.lzplain | Bin 0 -> 87469 bytes
.../slow-63e9f0b52235fb0129fa.lzplain | Bin 0 -> 86938 bytes
.../slow-73b7f971d65908ac0095.lzplain | Bin 0 -> 80541 bytes
.../slow-8b61e3dd267908544531.lzplain | Bin 0 -> 114004 bytes
.../slow-9d1c5a079b0462986f1f.lzplain | Bin 0 -> 88175 bytes
.../slow-aa7262a821dabdcf04a6.lzplain | Bin 0 -> 86931 bytes
.../slow-b8a91d142b0d2af7f5ca.lzplain | Bin 0 -> 47231 bytes
.../slow-c79142457734bbc8d575.lzplain | Bin 0 -> 71478 bytes
.../slow-d736544545b90d83fe75.lzplain | Bin 0 -> 130017 bytes
.../slow-e3b9bdfaed7d1a606fdb.lzplain | Bin 0 -> 71947 bytes
.../slow-f3f1c02a9d006e5e1703.lzplain | Bin 0 -> 114026 bytes
.../compressed-plain/square_series-128k+.lzplain | Bin 0 -> 131095 bytes
.../compressed-plain/square_series.lzplain | Bin 0 -> 65536 bytes
.../compressed-plain/trigram_128k+.lzplain | Bin 0 -> 58466 bytes
.../compressed-plain/trigram_64k.lzplain | Bin 0 -> 29028 bytes
.../compressed-plain/trigram_sum_128k+.lzplain | Bin 0 -> 105060 bytes
.../compressed-plain/trigram_sum_64k.lzplain | Bin 0 -> 51187 bytes
.../compression/decompressed/27826-8.txt.decomp | 359 ++
.../decompressed/5d049b4cb1bd933f5e8ex19.decomp | Bin 0 -> 304 bytes
.../decompressed/638e61e96d54279981c3x5.decomp | Bin 0 -> 320 bytes
.../decompressed/64k-minus-one-zeros.decomp | Bin 0 -> 65535 bytes
.../decompressed/64k-plus-one-zeros.decomp | Bin 0 -> 65537 bytes
testdata/compression/decompressed/64k-zeros.decomp | Bin 0 -> 65536 bytes
.../decompressed/96f696a4e5ce56c61a3dx10.decomp | Bin 0 -> 320 bytes
.../decompressed/9e0b6a12febf38e98f13.decomp | Bin 0 -> 4096 bytes
.../compression/decompressed/abc-times-101.decomp | 1 +
.../compression/decompressed/abc-times-105.decomp | 1 +
.../compression/decompressed/abc-times-200.decomp | 1 +
.../compression/decompressed/and_rand-128k+.decomp | Bin 0 -> 131095 bytes
testdata/compression/decompressed/and_rand.decomp | Bin 0 -> 65536 bytes
.../decompressed/b63289ccc7f218c0d56b.decomp | Bin 0 -> 1244 bytes
.../decompressed/beta-variate1-128k+.decomp | Bin 0 -> 131095 bytes
.../decompressed/beta-variate2-128k+.decomp | Bin 0 -> 131095 bytes
.../decompressed/beta-variate3-128k+.decomp | Bin 0 -> 131095 bytes
.../decompressed/decayed_alphabet_128k+.decomp | 2 +
.../decompressed/decayed_alphabet_64k.decomp | 2 +
.../decompressed/exp_shuffle-128k+.decomp | 1 +
.../compression/decompressed/exp_shuffle.decomp | 1 +
.../decompressed/f00842317dc6d5695b02.decomp | Bin 0 -> 2391 bytes
.../decompressed/fib_shuffle-128k+.decomp | Bin 0 -> 131095 bytes
.../compression/decompressed/fib_shuffle.decomp | 9 +
.../fuzzing-0fc2d461b56cd8103c91.decomp | Bin 0 -> 65550 bytes
.../fuzzing-17c961778538cc10ab7c.decomp | Bin 0 -> 131113 bytes
.../fuzzing-3591f9dc02bb00a54b60.decomp | Bin 0 -> 131077 bytes
.../fuzzing-3ec3bca27bb9eb40c128.decomp | Bin 0 -> 65573 bytes
.../fuzzing-80b4fa18ff5f8dd04862.decomp | Bin 0 -> 131113 bytes
.../fuzzing-a3115a81d1ac500318f9.decomp | Bin 0 -> 106944 bytes
.../generate-windows-test-vectors.c.decomp | 206 +
.../decompressed/midsummer-nights-dream.txt.decomp | 3980 ++++++++++++++
.../notes-on-the-underground.txt.decomp | 135 +
.../compression/decompressed/pg22009.txt.decomp | 1490 ++++++
.../decompressed/repeating-exactly-64k.decomp | 1338 +++++
testdata/compression/decompressed/repeating.decomp | 1340 +++++
testdata/compression/decompressed/setup.log.decomp | 411 ++
.../decompressed/skewed_choices-128k+.decomp | 41 +
.../compression/decompressed/skewed_choices.decomp | 22 +
.../decompressed/slow-015ddc36a71412ccc50d.decomp | Bin 0 -> 131095 bytes
.../decompressed/slow-100e9f966a7feb9ca40a.decomp | Bin 0 -> 129999 bytes
.../decompressed/slow-2a671c3cff4f1574cbab.decomp | Bin 0 -> 131113 bytes
.../decompressed/slow-33d90a24e70515b14cd0.decomp | Bin 0 -> 130004 bytes
.../decompressed/slow-49d8c05261e3f412fc72.decomp | Bin 0 -> 130781 bytes
.../decompressed/slow-50a249d2fe56873e56a0.decomp | Bin 0 -> 130465 bytes
.../decompressed/slow-63e9f0b52235fb0129fa.decomp | Bin 0 -> 129999 bytes
.../decompressed/slow-73b7f971d65908ac0095.decomp | Bin 0 -> 130001 bytes
.../decompressed/slow-8b61e3dd267908544531.decomp | Bin 0 -> 131113 bytes
.../decompressed/slow-9d1c5a079b0462986f1f.decomp | Bin 0 -> 131113 bytes
.../decompressed/slow-aa7262a821dabdcf04a6.decomp | Bin 0 -> 129978 bytes
.../decompressed/slow-b8a91d142b0d2af7f5ca.decomp | Bin 0 -> 128119 bytes
.../decompressed/slow-c79142457734bbc8d575.decomp | Bin 0 -> 131073 bytes
.../decompressed/slow-d736544545b90d83fe75.decomp | Bin 0 -> 131104 bytes
.../decompressed/slow-e3b9bdfaed7d1a606fdb.decomp | Bin 0 -> 129996 bytes
.../decompressed/slow-f3f1c02a9d006e5e1703.decomp | Bin 0 -> 131099 bytes
.../decompressed/square_series-128k+.decomp | Bin 0 -> 131095 bytes
.../compression/decompressed/square_series.decomp | Bin 0 -> 65536 bytes
.../compression/decompressed/trigram_128k+.decomp | 5517 ++++++++++++++++++++
.../compression/decompressed/trigram_64k.decomp | 2700 ++++++++++
.../decompressed/trigram_sum_128k+.decomp | Bin 0 -> 131095 bytes
.../decompressed/trigram_sum_64k.decomp | Bin 0 -> 65536 bytes
290 files changed, 24129 insertions(+), 619 deletions(-)
create mode 100644 lib/compression/lzxpress_huffman.c
create mode 100644 lib/compression/lzxpress_huffman.h
create mode 100644 lib/compression/tests/scripts/README
create mode 100755 lib/compression/tests/scripts/decode-huffman-header
create mode 100644 lib/compression/tests/scripts/generate-windows-test-vectors.c
create mode 100755 lib/compression/tests/scripts/make-fuzz-examples
create mode 100755 lib/compression/tests/scripts/make-test-vectors
create mode 100755 lib/compression/tests/scripts/three-byte-hash
create mode 100644 lib/compression/tests/test_lzx_huffman.c
create mode 100644 lib/compression/tests/test_lzxpress_plain.c
delete mode 100644 lib/compression/testsuite.c
create mode 100644 lib/fuzzing/fuzz_lzxpress_huffman_compress.c
create mode 100644 lib/fuzzing/fuzz_lzxpress_huffman_decompress.c
create mode 100644 lib/fuzzing/fuzz_lzxpress_huffman_round_trip.c
create mode 100644 lib/fuzzing/fuzz_stable_sort.c
create mode 100644 lib/fuzzing/fuzz_stable_sort_r.c
create mode 100644 lib/util/stable_sort.c
create mode 100644 lib/util/stable_sort.h
create mode 100644 lib/util/tests/test_stable_sort.c
create mode 100644 testdata/compression/README
create mode 100644 testdata/compression/compressed-huffman/27826-8.txt.lzhuff
create mode 100644 testdata/compression/compressed-huffman/5d049b4cb1bd933f5e8ex19.lzhuff
create mode 100644 testdata/compression/compressed-huffman/638e61e96d54279981c3x5.lzhuff
create mode 100644 testdata/compression/compressed-huffman/64k-minus-one-zeros.lzhuff
create mode 100644 testdata/compression/compressed-huffman/64k-plus-one-zeros.lzhuff
create mode 100644 testdata/compression/compressed-huffman/64k-zeros.lzhuff
create mode 100644 testdata/compression/compressed-huffman/96f696a4e5ce56c61a3dx10.lzhuff
create mode 100644 testdata/compression/compressed-huffman/9e0b6a12febf38e98f13.lzhuff
create mode 100644 testdata/compression/compressed-huffman/abc-times-101.lzhuff
create mode 100644 testdata/compression/compressed-huffman/abc-times-105.lzhuff
create mode 100644 testdata/compression/compressed-huffman/abc-times-200.lzhuff
create mode 100644 testdata/compression/compressed-huffman/and_rand-128k+.lzhuff
create mode 100644 testdata/compression/compressed-huffman/and_rand.lzhuff
create mode 100644 testdata/compression/compressed-huffman/b63289ccc7f218c0d56b.lzhuff
create mode 100644 testdata/compression/compressed-huffman/beta-variate1-128k+.lzhuff
create mode 100644 testdata/compression/compressed-huffman/beta-variate2-128k+.lzhuff
create mode 100644 testdata/compression/compressed-huffman/beta-variate3-128k+.lzhuff
create mode 100644 testdata/compression/compressed-huffman/decayed_alphabet_128k+.lzhuff
create mode 100644 testdata/compression/compressed-huffman/decayed_alphabet_64k.lzhuff
create mode 100644 testdata/compression/compressed-huffman/exp_shuffle-128k+.lzhuff
create mode 100644 testdata/compression/compressed-huffman/exp_shuffle.lzhuff
create mode 100644 testdata/compression/compressed-huffman/f00842317dc6d5695b02.lzhuff
create mode 100644 testdata/compression/compressed-huffman/fib_shuffle-128k+.lzhuff
create mode 100644 testdata/compression/compressed-huffman/fib_shuffle.lzhuff
create mode 100644 testdata/compression/compressed-huffman/fuzzing-0fc2d461b56cd8103c91.lzhuff
create mode 100644 testdata/compression/compressed-huffman/fuzzing-17c961778538cc10ab7c.lzhuff
create mode 100644 testdata/compression/compressed-huffman/fuzzing-3591f9dc02bb00a54b60.lzhuff
create mode 100644 testdata/compression/compressed-huffman/fuzzing-3ec3bca27bb9eb40c128.lzhuff
create mode 100644 testdata/compression/compressed-huffman/fuzzing-80b4fa18ff5f8dd04862.lzhuff
create mode 100644 testdata/compression/compressed-huffman/fuzzing-a3115a81d1ac500318f9.lzhuff
create mode 100644 testdata/compression/compressed-huffman/generate-windows-test-vectors.c.lzhuff
create mode 100644 testdata/compression/compressed-huffman/midsummer-nights-dream.txt.lzhuff
create mode 100644 testdata/compression/compressed-huffman/notes-on-the-underground.txt.lzhuff
create mode 100644 testdata/compression/compressed-huffman/pg22009.txt.lzhuff
create mode 100644 testdata/compression/compressed-huffman/repeating-exactly-64k.lzhuff
create mode 100644 testdata/compression/compressed-huffman/repeating.lzhuff
create mode 100644 testdata/compression/compressed-huffman/setup.log.lzhuff
create mode 100644 testdata/compression/compressed-huffman/skewed_choices-128k+.lzhuff
create mode 100644 testdata/compression/compressed-huffman/skewed_choices.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-015ddc36a71412ccc50d.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-100e9f966a7feb9ca40a.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-2a671c3cff4f1574cbab.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-33d90a24e70515b14cd0.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-49d8c05261e3f412fc72.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-50a249d2fe56873e56a0.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-63e9f0b52235fb0129fa.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-73b7f971d65908ac0095.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-8b61e3dd267908544531.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-9d1c5a079b0462986f1f.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-aa7262a821dabdcf04a6.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-b8a91d142b0d2af7f5ca.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-c79142457734bbc8d575.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-d736544545b90d83fe75.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-e3b9bdfaed7d1a606fdb.lzhuff
create mode 100644 testdata/compression/compressed-huffman/slow-f3f1c02a9d006e5e1703.lzhuff
create mode 100644 testdata/compression/compressed-huffman/square_series-128k+.lzhuff
create mode 100644 testdata/compression/compressed-huffman/square_series.lzhuff
create mode 100644 testdata/compression/compressed-huffman/trigram_128k+.lzhuff
create mode 100644 testdata/compression/compressed-huffman/trigram_64k.lzhuff
create mode 100644 testdata/compression/compressed-huffman/trigram_sum_128k+.lzhuff
create mode 100644 testdata/compression/compressed-huffman/trigram_sum_64k.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/27826-8.txt.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/5d049b4cb1bd933f5e8ex19.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/638e61e96d54279981c3x5.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/64k-minus-one-zeros.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/64k-plus-one-zeros.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/64k-zeros.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/96f696a4e5ce56c61a3dx10.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/9e0b6a12febf38e98f13.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/abc-times-101.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/abc-times-105.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/abc-times-200.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/and_rand-128k+.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/and_rand.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/b63289ccc7f218c0d56b.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/beta-variate1-128k+.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/beta-variate2-128k+.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/beta-variate3-128k+.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/decayed_alphabet_128k+.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/decayed_alphabet_64k.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/exp_shuffle-128k+.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/exp_shuffle.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/f00842317dc6d5695b02.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/fib_shuffle-128k+.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/fib_shuffle.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/generate-windows-test-vectors.c.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/midsummer-nights-dream.txt.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/notes-on-the-underground.txt.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/pg22009.txt.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/repeating-exactly-64k.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/repeating.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/setup.log.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/skewed_choices-128k+.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/skewed_choices.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/square_series-128k+.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/square_series.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/trigram_128k+.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/trigram_64k.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/trigram_sum_128k+.lzhuff
create mode 100644 testdata/compression/compressed-more-huffman/trigram_sum_64k.lzhuff
create mode 100644 testdata/compression/compressed-more-plain/27826-8.txt.lzplain
create mode 100644 testdata/compression/compressed-more-plain/5d049b4cb1bd933f5e8ex19.lzplain
create mode 100644 testdata/compression/compressed-more-plain/638e61e96d54279981c3x5.lzplain
create mode 100644 testdata/compression/compressed-more-plain/64k-minus-one-zeros.lzplain
create mode 100644 testdata/compression/compressed-more-plain/64k-plus-one-zeros.lzplain
create mode 100644 testdata/compression/compressed-more-plain/64k-zeros.lzplain
create mode 100644 testdata/compression/compressed-more-plain/96f696a4e5ce56c61a3dx10.lzplain
create mode 100644 testdata/compression/compressed-more-plain/9e0b6a12febf38e98f13.lzplain
create mode 100644 testdata/compression/compressed-more-plain/abc-times-101.lzplain
create mode 100644 testdata/compression/compressed-more-plain/abc-times-105.lzplain
create mode 100644 testdata/compression/compressed-more-plain/abc-times-200.lzplain
create mode 100644 testdata/compression/compressed-more-plain/and_rand-128k+.lzplain
create mode 100644 testdata/compression/compressed-more-plain/and_rand.lzplain
create mode 100644 testdata/compression/compressed-more-plain/b63289ccc7f218c0d56b.lzplain
create mode 100644 testdata/compression/compressed-more-plain/beta-variate1-128k+.lzplain
create mode 100644 testdata/compression/compressed-more-plain/beta-variate2-128k+.lzplain
create mode 100644 testdata/compression/compressed-more-plain/beta-variate3-128k+.lzplain
create mode 100644 testdata/compression/compressed-more-plain/decayed_alphabet_128k+.lzplain
create mode 100644 testdata/compression/compressed-more-plain/decayed_alphabet_64k.lzplain
create mode 100644 testdata/compression/compressed-more-plain/exp_shuffle-128k+.lzplain
create mode 100644 testdata/compression/compressed-more-plain/exp_shuffle.lzplain
create mode 100644 testdata/compression/compressed-more-plain/f00842317dc6d5695b02.lzplain
create mode 100644 testdata/compression/compressed-more-plain/fib_shuffle-128k+.lzplain
create mode 100644 testdata/compression/compressed-more-plain/fib_shuffle.lzplain
create mode 100644 testdata/compression/compressed-more-plain/generate-windows-test-vectors.c.lzplain
create mode 100644 testdata/compression/compressed-more-plain/midsummer-nights-dream.txt.lzplain
create mode 100644 testdata/compression/compressed-more-plain/notes-on-the-underground.txt.lzplain
create mode 100644 testdata/compression/compressed-more-plain/pg22009.txt.lzplain
create mode 100644 testdata/compression/compressed-more-plain/repeating-exactly-64k.lzplain
create mode 100644 testdata/compression/compressed-more-plain/repeating.lzplain
create mode 100644 testdata/compression/compressed-more-plain/setup.log.lzplain
create mode 100644 testdata/compression/compressed-more-plain/skewed_choices-128k+.lzplain
create mode 100644 testdata/compression/compressed-more-plain/skewed_choices.lzplain
create mode 100644 testdata/compression/compressed-more-plain/square_series-128k+.lzplain
create mode 100644 testdata/compression/compressed-more-plain/square_series.lzplain
create mode 100644 testdata/compression/compressed-more-plain/trigram_128k+.lzplain
create mode 100644 testdata/compression/compressed-more-plain/trigram_64k.lzplain
create mode 100644 testdata/compression/compressed-more-plain/trigram_sum_128k+.lzplain
create mode 100644 testdata/compression/compressed-more-plain/trigram_sum_64k.lzplain
create mode 100644 testdata/compression/compressed-plain/27826-8.txt.lzplain
create mode 100644 testdata/compression/compressed-plain/5d049b4cb1bd933f5e8ex19.lzplain
create mode 100644 testdata/compression/compressed-plain/638e61e96d54279981c3x5.lzplain
create mode 100644 testdata/compression/compressed-plain/64k-minus-one-zeros.lzplain
create mode 100644 testdata/compression/compressed-plain/64k-plus-one-zeros.lzplain
create mode 100644 testdata/compression/compressed-plain/64k-zeros.lzplain
create mode 100644 testdata/compression/compressed-plain/96f696a4e5ce56c61a3dx10.lzplain
create mode 100644 testdata/compression/compressed-plain/9e0b6a12febf38e98f13.lzplain
create mode 100644 testdata/compression/compressed-plain/abc-times-101.lzplain
create mode 100644 testdata/compression/compressed-plain/abc-times-105.lzplain
create mode 100644 testdata/compression/compressed-plain/abc-times-200.lzplain
create mode 100644 testdata/compression/compressed-plain/and_rand-128k+.lzplain
create mode 100644 testdata/compression/compressed-plain/and_rand.lzplain
create mode 100644 testdata/compression/compressed-plain/b63289ccc7f218c0d56b.lzplain
create mode 100644 testdata/compression/compressed-plain/beta-variate1-128k+.lzplain
create mode 100644 testdata/compression/compressed-plain/beta-variate2-128k+.lzplain
create mode 100644 testdata/compression/compressed-plain/beta-variate3-128k+.lzplain
create mode 100644 testdata/compression/compressed-plain/decayed_alphabet_128k+.lzplain
create mode 100644 testdata/compression/compressed-plain/decayed_alphabet_64k.lzplain
create mode 100644 testdata/compression/compressed-plain/exp_shuffle-128k+.lzplain
create mode 100644 testdata/compression/compressed-plain/exp_shuffle.lzplain
create mode 100644 testdata/compression/compressed-plain/f00842317dc6d5695b02.lzplain
create mode 100644 testdata/compression/compressed-plain/fib_shuffle-128k+.lzplain
create mode 100644 testdata/compression/compressed-plain/fib_shuffle.lzplain
create mode 100644 testdata/compression/compressed-plain/fuzzing-0fc2d461b56cd8103c91.lzplain
create mode 100644 testdata/compression/compressed-plain/fuzzing-17c961778538cc10ab7c.lzplain
create mode 100644 testdata/compression/compressed-plain/fuzzing-3591f9dc02bb00a54b60.lzplain
create mode 100644 testdata/compression/compressed-plain/fuzzing-3ec3bca27bb9eb40c128.lzplain
create mode 100644 testdata/compression/compressed-plain/fuzzing-a3115a81d1ac500318f9.lzplain
create mode 100644 testdata/compression/compressed-plain/generate-windows-test-vectors.c.lzplain
create mode 100644 testdata/compression/compressed-plain/midsummer-nights-dream.txt.lzplain
create mode 100644 testdata/compression/compressed-plain/notes-on-the-underground.txt.lzplain
create mode 100644 testdata/compression/compressed-plain/pg22009.txt.lzplain
create mode 100644 testdata/compression/compressed-plain/repeating-exactly-64k.lzplain
create mode 100644 testdata/compression/compressed-plain/repeating.lzplain
create mode 100644 testdata/compression/compressed-plain/setup.log.lzplain
create mode 100644 testdata/compression/compressed-plain/skewed_choices-128k+.lzplain
create mode 100644 testdata/compression/compressed-plain/skewed_choices.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-015ddc36a71412ccc50d.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-100e9f966a7feb9ca40a.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-2a671c3cff4f1574cbab.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-33d90a24e70515b14cd0.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-49d8c05261e3f412fc72.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-50a249d2fe56873e56a0.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-63e9f0b52235fb0129fa.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-73b7f971d65908ac0095.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-8b61e3dd267908544531.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-9d1c5a079b0462986f1f.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-aa7262a821dabdcf04a6.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-b8a91d142b0d2af7f5ca.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-c79142457734bbc8d575.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-d736544545b90d83fe75.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-e3b9bdfaed7d1a606fdb.lzplain
create mode 100644 testdata/compression/compressed-plain/slow-f3f1c02a9d006e5e1703.lzplain
create mode 100644 testdata/compression/compressed-plain/square_series-128k+.lzplain
create mode 100644 testdata/compression/compressed-plain/square_series.lzplain
create mode 100644 testdata/compression/compressed-plain/trigram_128k+.lzplain
create mode 100644 testdata/compression/compressed-plain/trigram_64k.lzplain
create mode 100644 testdata/compression/compressed-plain/trigram_sum_128k+.lzplain
create mode 100644 testdata/compression/compressed-plain/trigram_sum_64k.lzplain
create mode 100644 testdata/compression/decompressed/27826-8.txt.decomp
create mode 100644 testdata/compression/decompressed/5d049b4cb1bd933f5e8ex19.decomp
create mode 100644 testdata/compression/decompressed/638e61e96d54279981c3x5.decomp
create mode 100644 testdata/compression/decompressed/64k-minus-one-zeros.decomp
create mode 100644 testdata/compression/decompressed/64k-plus-one-zeros.decomp
create mode 100644 testdata/compression/decompressed/64k-zeros.decomp
create mode 100644 testdata/compression/decompressed/96f696a4e5ce56c61a3dx10.decomp
create mode 100644 testdata/compression/decompressed/9e0b6a12febf38e98f13.decomp
create mode 100644 testdata/compression/decompressed/abc-times-101.decomp
create mode 100644 testdata/compression/decompressed/abc-times-105.decomp
create mode 100644 testdata/compression/decompressed/abc-times-200.decomp
create mode 100644 testdata/compression/decompressed/and_rand-128k+.decomp
create mode 100644 testdata/compression/decompressed/and_rand.decomp
create mode 100644 testdata/compression/decompressed/b63289ccc7f218c0d56b.decomp
create mode 100644 testdata/compression/decompressed/beta-variate1-128k+.decomp
create mode 100644 testdata/compression/decompressed/beta-variate2-128k+.decomp
create mode 100644 testdata/compression/decompressed/beta-variate3-128k+.decomp
create mode 100644 testdata/compression/decompressed/decayed_alphabet_128k+.decomp
create mode 100644 testdata/compression/decompressed/decayed_alphabet_64k.decomp
create mode 100644 testdata/compression/decompressed/exp_shuffle-128k+.decomp
create mode 100644 testdata/compression/decompressed/exp_shuffle.decomp
create mode 100644 testdata/compression/decompressed/f00842317dc6d5695b02.decomp
create mode 100644 testdata/compression/decompressed/fib_shuffle-128k+.decomp
create mode 100644 testdata/compression/decompressed/fib_shuffle.decomp
create mode 100644 testdata/compression/decompressed/fuzzing-0fc2d461b56cd8103c91.decomp
create mode 100644 testdata/compression/decompressed/fuzzing-17c961778538cc10ab7c.decomp
create mode 100644 testdata/compression/decompressed/fuzzing-3591f9dc02bb00a54b60.decomp
create mode 100644 testdata/compression/decompressed/fuzzing-3ec3bca27bb9eb40c128.decomp
create mode 100644 testdata/compression/decompressed/fuzzing-80b4fa18ff5f8dd04862.decomp
create mode 100644 testdata/compression/decompressed/fuzzing-a3115a81d1ac500318f9.decomp
create mode 100644 testdata/compression/decompressed/generate-windows-test-vectors.c.decomp
create mode 100644 testdata/compression/decompressed/midsummer-nights-dream.txt.decomp
create mode 100644 testdata/compression/decompressed/notes-on-the-underground.txt.decomp
create mode 100644 testdata/compression/decompressed/pg22009.txt.decomp
create mode 100644 testdata/compression/decompressed/repeating-exactly-64k.decomp
create mode 100644 testdata/compression/decompressed/repeating.decomp
create mode 100644 testdata/compression/decompressed/setup.log.decomp
create mode 100644 testdata/compression/decompressed/skewed_choices-128k+.decomp
create mode 100644 testdata/compression/decompressed/skewed_choices.decomp
create mode 100644 testdata/compression/decompressed/slow-015ddc36a71412ccc50d.decomp
create mode 100644 testdata/compression/decompressed/slow-100e9f966a7feb9ca40a.decomp
create mode 100644 testdata/compression/decompressed/slow-2a671c3cff4f1574cbab.decomp
create mode 100644 testdata/compression/decompressed/slow-33d90a24e70515b14cd0.decomp
create mode 100644 testdata/compression/decompressed/slow-49d8c05261e3f412fc72.decomp
create mode 100644 testdata/compression/decompressed/slow-50a249d2fe56873e56a0.decomp
create mode 100644 testdata/compression/decompressed/slow-63e9f0b52235fb0129fa.decomp
create mode 100644 testdata/compression/decompressed/slow-73b7f971d65908ac0095.decomp
create mode 100644 testdata/compression/decompressed/slow-8b61e3dd267908544531.decomp
create mode 100644 testdata/compression/decompressed/slow-9d1c5a079b0462986f1f.decomp
create mode 100644 testdata/compression/decompressed/slow-aa7262a821dabdcf04a6.decomp
create mode 100644 testdata/compression/decompressed/slow-b8a91d142b0d2af7f5ca.decomp
create mode 100644 testdata/compression/decompressed/slow-c79142457734bbc8d575.decomp
create mode 100644 testdata/compression/decompressed/slow-d736544545b90d83fe75.decomp
create mode 100644 testdata/compression/decompressed/slow-e3b9bdfaed7d1a606fdb.decomp
create mode 100644 testdata/compression/decompressed/slow-f3f1c02a9d006e5e1703.decomp
create mode 100644 testdata/compression/decompressed/square_series-128k+.decomp
create mode 100644 testdata/compression/decompressed/square_series.decomp
create mode 100644 testdata/compression/decompressed/trigram_128k+.decomp
create mode 100644 testdata/compression/decompressed/trigram_64k.decomp
create mode 100644 testdata/compression/decompressed/trigram_sum_128k+.decomp
create mode 100644 testdata/compression/decompressed/trigram_sum_64k.decomp
Changeset truncated at 500 lines:
diff --git a/lib/compression/lzxpress.c b/lib/compression/lzxpress.c
index 6b2aeef02f6..5e5e5baafc4 100644
--- a/lib/compression/lzxpress.c
+++ b/lib/compression/lzxpress.c
@@ -48,10 +48,247 @@
} \
} while(0)
+
+/*
+ * LZX_PLAIN_COMP_HASH_BITS determines how big the hash table for finding
+ * matches will be.
+ *
+ * The window in which we look for matches is 8192 bytes. That means with
+ * random data a value of 13 is getting close to no collisions, while a 12
+ * will miss about half the possible matches. With compressible data there
+ * will generally be fewer and less diverse entries, so collisions are rarer.
+ *
+ * In the testsuite, bith 12 and 13 give better compression than Windows, but
+ * 12 is faster. 11 does not save time and costs accuracy. Thus we prefer 12.
+ */
+#define LZX_PLAIN_COMP_HASH_BITS 12
+/*
+ * LZX_PLAIN_COMP_HASH_SEARCH_ATTEMPTS is how far ahead to search in the
+ * circular hash table for a match, before we give up. A bigger number will
+ * generally lead to better but slower compression, but a stupidly big number
+ * will just be worse.
+ */
+#define LZX_PLAIN_COMP_HASH_SEARCH_ATTEMPTS 5
+#define HASH_MASK ((1 << LZX_PLAIN_COMP_HASH_BITS) - 1)
+
+static inline uint16_t three_byte_hash(const uint8_t *bytes)
+{
+ uint16_t a = bytes[0];
+ uint16_t b = bytes[1] ^ 0x2e;
+ uint16_t c = bytes[2] ^ 0x55;
+ uint16_t ca = c - a;
+ uint16_t d = ((a + b) << 8) ^ (ca << 5) ^ (c + b) ^ (0xcab + a);
+ return d & HASH_MASK;
+}
+
+
+static inline void store_match(uint32_t *hash_table,
+ uint16_t h,
+ uint32_t offset)
+{
+ int i;
+ uint32_t o = hash_table[h];
+ uint16_t h2;
+ uint16_t worst_h;
+ int worst_score;
+
+ if (o >= offset) {
+ /* there is nothing there yet */
+ hash_table[h] = offset;
+ return;
+ }
+ for (i = 1; i < LZX_PLAIN_COMP_HASH_SEARCH_ATTEMPTS; i++) {
+ h2 = (h + i) & HASH_MASK;
+ if (hash_table[h2] >= offset) {
+ hash_table[h2] = offset;
+ return;
+ }
+ }
+ /*
+ * There are no slots, but we really want to store this, so we'll kick
+ * out the one with the longest distance.
+ */
+ worst_h = h;
+ worst_score = offset - o;
+ for (i = 1; i < LZX_PLAIN_COMP_HASH_SEARCH_ATTEMPTS; i++) {
+ int score;
+ h2 = (h + i) & HASH_MASK;
+ o = hash_table[h2];
+ score = offset - o;
+ if (score > worst_score) {
+ worst_score = score;
+ worst_h = h2;
+ }
+ }
+ hash_table[worst_h] = offset;
+}
+
+
+struct match {
+ const uint8_t *there;
+ uint32_t length;
+};
+
+
+static inline struct match lookup_match(uint32_t *hash_table,
+ uint16_t h,
+ const uint8_t *data,
+ uint32_t offset,
+ size_t max_len)
+{
+ int i;
+ uint32_t o;
+ uint16_t h2;
+ size_t len;
+ const uint8_t *there = NULL;
+ const uint8_t *here = data + offset;
+ struct match best = {0};
+
+ for (i = 0; i < LZX_PLAIN_COMP_HASH_SEARCH_ATTEMPTS; i++) {
+ h2 = (h + i) & HASH_MASK;
+ o = hash_table[h2];
+ if (o >= offset) {
+ /*
+ * Either this is 0xffffffff, or something is really
+ * wrong.
+ *
+ * In setting this, we would never have stepped over
+ * an 0xffffffff, so we won't now.
+ */
+ break;
+ }
+ if (offset - o > 8192) {
+ /* Too far away to use */
+ continue;
+ }
+ there = data + o;
+ /*
+ * When we already have a long match, we can try to avoid
+ * measuring out another long, but shorter match.
+ */
+ if (best.length > 1000 &&
+ there[best.length - 1] != best.there[best.length - 1]) {
+ continue;
+ }
+
+ for (len = 0;
+ len < max_len && here[len] == there[len];
+ len++) {
+ /* counting */
+ }
+ if (len > 2) {
+ if (len > best.length) {
+ best.length = len;
+ best.there = there;
+ }
+ }
+ }
+ return best;
+}
+
+struct write_context {
+ uint8_t *compressed;
+ uint32_t compressed_pos;
+ uint32_t max_compressed_size;
+ uint32_t indic;
+ uint32_t indic_bit;
+ uint32_t indic_pos;
+ uint32_t nibble_index;
+};
+
+
#define CHECK_INPUT_BYTES(__needed) \
__CHECK_BYTES(uncompressed_size, uncompressed_pos, __needed)
#define CHECK_OUTPUT_BYTES(__needed) \
- __CHECK_BYTES(max_compressed_size, compressed_pos, __needed)
+ __CHECK_BYTES(wc->max_compressed_size, wc->compressed_pos, __needed)
+
+
+static inline ssize_t push_indicator_bit(struct write_context *wc, uint32_t bit)
+{
+ wc->indic = (wc->indic << 1) | bit;
+ wc->indic_bit += 1;
+
+ if (wc->indic_bit == 32) {
+ PUSH_LE_U32(wc->compressed, wc->indic_pos, wc->indic);
+ wc->indic_bit = 0;
+ CHECK_OUTPUT_BYTES(sizeof(uint32_t));
+ wc->indic_pos = wc->compressed_pos;
+ wc->compressed_pos += sizeof(uint32_t);
+ }
+ return wc->indic_pos;
+}
+
+
+static ssize_t encode_match(struct write_context *wc,
+ struct match match,
+ const uint8_t *here)
+{
+ uint32_t match_len = match.length - 3;
+ uint32_t best_offset = here - match.there - 1;
+ uint16_t metadata;
+
+ if (best_offset > 8191) {
+ return -1;
+ }
+
+ CHECK_OUTPUT_BYTES(sizeof(uint16_t));
+ metadata = (uint16_t)((best_offset << 3) | MIN(match_len, 7));
+ PUSH_LE_U16(wc->compressed, wc->compressed_pos, metadata);
+ wc->compressed_pos += sizeof(uint16_t);
+
+ if (match_len >= 7) {
+ match_len -= 7;
+
+ if (wc->nibble_index == 0) {
+ wc->nibble_index = wc->compressed_pos;
+
+ CHECK_OUTPUT_BYTES(sizeof(uint8_t));
+ wc->compressed[wc->nibble_index] = MIN(match_len, 15);
+ wc->compressed_pos += sizeof(uint8_t);
+ } else {
+ wc->compressed[wc->nibble_index] |= MIN(match_len, 15) << 4;
+ wc->nibble_index = 0;
+ }
+
+ if (match_len >= 15) {
+ match_len -= 15;
+
+ CHECK_OUTPUT_BYTES(sizeof(uint8_t));
+ wc->compressed[wc->compressed_pos] = MIN(match_len, 255);
+ wc->compressed_pos += sizeof(uint8_t);
+
+ if (match_len >= 255) {
+ /* Additional match_len */
+
+ match_len += 7 + 15;
+
+ if (match_len < (1 << 16)) {
+ CHECK_OUTPUT_BYTES(sizeof(uint16_t));
+ PUSH_LE_U16(wc->compressed, wc->compressed_pos,
+ match_len);
+ wc->compressed_pos += sizeof(uint16_t);
+ } else {
+ CHECK_OUTPUT_BYTES(sizeof(uint16_t) +
+ sizeof(uint32_t));
+ PUSH_LE_U16(wc->compressed,
+ wc->compressed_pos, 0);
+ wc->compressed_pos += sizeof(uint16_t);
+
+ PUSH_LE_U32(wc->compressed,
+ wc->compressed_pos,
+ match_len);
+ wc->compressed_pos += sizeof(uint32_t);
+ }
+ }
+ }
+ }
+ return push_indicator_bit(wc, 1);
+}
+
+#undef CHECK_OUTPUT_BYTES
+#define CHECK_OUTPUT_BYTES(__needed) \
+ __CHECK_BYTES(wc.max_compressed_size, wc.compressed_pos, __needed)
+
ssize_t lzxpress_compress(const uint8_t *uncompressed,
uint32_t uncompressed_size,
@@ -68,161 +305,84 @@ ssize_t lzxpress_compress(const uint8_t *uncompressed,
* the match length; they are always at least 16 bits long, and can
* implicitly use unused half-bytes from earlier in the stream.
*/
- uint32_t uncompressed_pos, compressed_pos;
- uint32_t indic;
- uint32_t indic_pos;
- uint32_t indic_bit, nibble_index;
+ ssize_t ret;
+ uint32_t uncompressed_pos;
+ struct write_context wc = {
+ .indic = 0,
+ .indic_pos = 0,
+ .indic_bit = 0,
+ .nibble_index = 0,
+ .compressed = compressed,
+ .compressed_pos = 0,
+ .max_compressed_size = max_compressed_size
+ };
+ uint32_t hash_table[1 << LZX_PLAIN_COMP_HASH_BITS];
+ memset(hash_table, 0xff, sizeof(hash_table));
if (!uncompressed_size) {
return 0;
}
uncompressed_pos = 0;
- compressed_pos = 0;
- indic = 0;
CHECK_OUTPUT_BYTES(sizeof(uint32_t));
- PUSH_LE_U32(compressed, compressed_pos, 0);
- compressed_pos += sizeof(uint32_t);
- indic_pos = 0;
-
- indic_bit = 0;
- nibble_index = 0;
+ PUSH_LE_U32(wc.compressed, wc.compressed_pos, 0);
+ wc.compressed_pos += sizeof(uint32_t);
while ((uncompressed_pos < uncompressed_size) &&
- (compressed_pos < max_compressed_size)) {
- bool found = false;
-
- uint32_t best_len = 2;
- uint32_t best_offset = 0;
-
- int32_t offset;
+ (wc.compressed_pos < wc.max_compressed_size)) {
- const uint32_t max_offset = MIN(0x2000, uncompressed_pos);
/* maximum len we can encode into metadata */
- const uint32_t max_len = MIN(0xFFFF + 3, uncompressed_size - uncompressed_pos);
-
- /* search for the longest match in the window for the lookahead buffer */
- for (offset = 1; (uint32_t)offset <= max_offset; offset++) {
- uint32_t len;
-
- for (len = 0;
- (len < max_len) && (uncompressed[uncompressed_pos + len] ==
- uncompressed[uncompressed_pos + len - offset]);
- len++);
-
- /*
- * We check if len is better than the value found before, including the
- * sequence of identical bytes
- */
- if (len > best_len) {
- found = true;
- best_len = len;
- best_offset = offset;
- if (best_len == max_len) {
- /* We're not going to do better than this */
- break;
- }
- }
+ const uint32_t max_len = MIN(0xFFFF + 3,
+ uncompressed_size - uncompressed_pos);
+ const uint8_t *here = uncompressed + uncompressed_pos;
+ uint16_t h;
+ struct match match = {0};
+
+ if (max_len >= 3) {
+ h = three_byte_hash(here);
+ match = lookup_match(hash_table,
+ h,
+ uncompressed,
+ uncompressed_pos,
+ max_len);
+
+ store_match(hash_table, h, uncompressed_pos);
+ } else {
+ match.there = NULL;
+ match.length = 0;
}
- if (!found) {
+ if (match.there == NULL) {
/*
- * This is going to literal byte, which we flag by
- * setting a bit in an indicator field somewhere
+ * This is going to be a literal byte, which we flag
+ * by setting a bit in an indicator field somewhere
* earlier in the stream.
*/
CHECK_INPUT_BYTES(sizeof(uint8_t));
CHECK_OUTPUT_BYTES(sizeof(uint8_t));
- compressed[compressed_pos++] = uncompressed[uncompressed_pos++];
-
- indic <<= 1;
- indic_bit += 1;
+ wc.compressed[wc.compressed_pos++] = *here;
+ uncompressed_pos++;
- if (indic_bit == 32) {
- PUSH_LE_U32(compressed, indic_pos, indic);
- indic_bit = 0;
- CHECK_OUTPUT_BYTES(sizeof(uint32_t));
- indic_pos = compressed_pos;
- compressed_pos += sizeof(uint32_t);
+ ret = push_indicator_bit(&wc, 0);
+ if (ret < 0) {
+ return ret;
}
} else {
- uint32_t match_len = best_len;
-
- uint16_t metadata;
-
- match_len -= 3;
- best_offset -= 1;
-
- /* Classical meta-data */
- CHECK_OUTPUT_BYTES(sizeof(uint16_t));
- metadata = (uint16_t)((best_offset << 3) | MIN(match_len, 7));
- PUSH_LE_U16(compressed, compressed_pos, metadata);
- compressed_pos += sizeof(uint16_t);
-
- if (match_len >= 7) {
- match_len -= 7;
-
- if (!nibble_index) {
- nibble_index = compressed_pos;
-
- CHECK_OUTPUT_BYTES(sizeof(uint8_t));
- compressed[nibble_index] = MIN(match_len, 15);
- compressed_pos += sizeof(uint8_t);
- } else {
- compressed[nibble_index] |= MIN(match_len, 15) << 4;
- nibble_index = 0;
- }
-
- if (match_len >= 15) {
- match_len -= 15;
-
- CHECK_OUTPUT_BYTES(sizeof(uint8_t));
- compressed[compressed_pos] = MIN(match_len, 255);
- compressed_pos += sizeof(uint8_t);
-
- if (match_len >= 255) {
- /* Additional match_len */
-
- match_len += 7 + 15;
-
- if (match_len < (1 << 16)) {
- CHECK_OUTPUT_BYTES(sizeof(uint16_t));
- PUSH_LE_U16(compressed, compressed_pos, match_len);
- compressed_pos += sizeof(uint16_t);
- } else {
- CHECK_OUTPUT_BYTES(sizeof(uint16_t) + sizeof(uint32_t));
- PUSH_LE_U16(compressed, compressed_pos, 0);
- compressed_pos += sizeof(uint16_t);
-
- PUSH_LE_U32(compressed, compressed_pos, match_len);
- compressed_pos += sizeof(uint32_t);
- }
- }
- }
+ ret = encode_match(&wc, match, here);
+ if (ret < 0) {
+ return ret;
}
-
- indic = (indic << 1) | 1;
- indic_bit += 1;
-
- if (indic_bit == 32) {
- PUSH_LE_U32(compressed, indic_pos, indic);
- indic_bit = 0;
- CHECK_OUTPUT_BYTES(sizeof(uint32_t));
- indic_pos = compressed_pos;
- compressed_pos += sizeof(uint32_t);
- }
-
- uncompressed_pos += best_len;
+ uncompressed_pos += match.length;
}
}
- if (indic_bit != 0) {
- indic <<= 32 - indic_bit;
+ if (wc.indic_bit != 0) {
+ wc.indic <<= 32 - wc.indic_bit;
}
- indic |= UINT32_MAX >> indic_bit;
- PUSH_LE_U32(compressed, indic_pos, indic);
+ wc.indic |= UINT32_MAX >> wc.indic_bit;
+ PUSH_LE_U32(wc.compressed, wc.indic_pos, wc.indic);
- return compressed_pos;
+ return wc.compressed_pos;
}
ssize_t lzxpress_decompress(const uint8_t *input,
diff --git a/lib/compression/lzxpress_huffman.c b/lib/compression/lzxpress_huffman.c
new file mode 100644
index 00000000000..990552a7d09
--- /dev/null
+++ b/lib/compression/lzxpress_huffman.c
@@ -0,0 +1,2020 @@
+/*
+ * Samba compression library - LGPLv3
+ *
+ * Copyright © Catalyst IT 2022
+ *
+ * Written by Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
+ * and Joseph Sutton <josephsutton at catalyst.net.nz>
+ *
+ * ** NOTE! The following LGPL license applies to this file.
+ * ** It does NOT imply that all of Samba is released under the LGPL
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <talloc.h>
+
+#include "replace.h"
--
Samba Shared Repository
More information about the samba-cvs
mailing list