Date: Tue, 22 Aug 2017 11:11:50 +0000 (UTC) From: Baptiste Daroussin <bapt@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r322784 - in head/contrib/zstd: . doc doc/educational_decoder lib lib/common lib/compress lib/decompress lib/deprecated lib/dictBuilder lib/legacy programs tests tests/files tests/fuzz ... Message-ID: <201708221111.v7MBBoTZ055381@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: bapt Date: Tue Aug 22 11:11:49 2017 New Revision: 322784 URL: https://svnweb.freebsd.org/changeset/base/322784 Log: Import zstandard 1.3.1 Added: head/contrib/zstd/lib/common/compiler.h - copied unchanged from r322782, vendor/zstd/dist/lib/common/compiler.h head/contrib/zstd/tests/files/ - copied from r322780, vendor/zstd/dist/tests/files/ head/contrib/zstd/tests/fuzz/ - copied from r322780, vendor/zstd/dist/tests/fuzz/ head/contrib/zstd/tests/poolTests.c - copied unchanged from r322780, vendor/zstd/dist/tests/poolTests.c Deleted: head/contrib/zstd/PATENTS head/contrib/zstd/tests/pool.c Modified: head/contrib/zstd/CONTRIBUTING.md head/contrib/zstd/Makefile head/contrib/zstd/NEWS head/contrib/zstd/README.md head/contrib/zstd/circle.yml head/contrib/zstd/doc/educational_decoder/harness.c head/contrib/zstd/doc/educational_decoder/zstd_decompress.c head/contrib/zstd/doc/educational_decoder/zstd_decompress.h head/contrib/zstd/doc/zstd_compression_format.md head/contrib/zstd/doc/zstd_manual.html head/contrib/zstd/lib/common/bitstream.h head/contrib/zstd/lib/common/error_private.c head/contrib/zstd/lib/common/error_private.h head/contrib/zstd/lib/common/fse.h head/contrib/zstd/lib/common/fse_decompress.c head/contrib/zstd/lib/common/huf.h head/contrib/zstd/lib/common/mem.h head/contrib/zstd/lib/common/pool.c head/contrib/zstd/lib/common/pool.h head/contrib/zstd/lib/common/threading.h head/contrib/zstd/lib/common/xxhash.c head/contrib/zstd/lib/common/zstd_common.c head/contrib/zstd/lib/common/zstd_errors.h head/contrib/zstd/lib/common/zstd_internal.h head/contrib/zstd/lib/compress/fse_compress.c head/contrib/zstd/lib/compress/huf_compress.c head/contrib/zstd/lib/compress/zstd_compress.c head/contrib/zstd/lib/compress/zstd_opt.h head/contrib/zstd/lib/compress/zstdmt_compress.c head/contrib/zstd/lib/compress/zstdmt_compress.h head/contrib/zstd/lib/decompress/huf_decompress.c head/contrib/zstd/lib/decompress/zstd_decompress.c head/contrib/zstd/lib/deprecated/zbuff.h head/contrib/zstd/lib/deprecated/zbuff_common.c head/contrib/zstd/lib/deprecated/zbuff_compress.c head/contrib/zstd/lib/deprecated/zbuff_decompress.c head/contrib/zstd/lib/dictBuilder/cover.c head/contrib/zstd/lib/dictBuilder/zdict.c head/contrib/zstd/lib/dictBuilder/zdict.h head/contrib/zstd/lib/legacy/zstd_legacy.h head/contrib/zstd/lib/legacy/zstd_v01.c head/contrib/zstd/lib/legacy/zstd_v01.h head/contrib/zstd/lib/legacy/zstd_v02.c head/contrib/zstd/lib/legacy/zstd_v02.h head/contrib/zstd/lib/legacy/zstd_v03.c head/contrib/zstd/lib/legacy/zstd_v03.h head/contrib/zstd/lib/legacy/zstd_v04.c head/contrib/zstd/lib/legacy/zstd_v04.h head/contrib/zstd/lib/legacy/zstd_v05.c head/contrib/zstd/lib/legacy/zstd_v05.h head/contrib/zstd/lib/legacy/zstd_v06.c head/contrib/zstd/lib/legacy/zstd_v06.h head/contrib/zstd/lib/legacy/zstd_v07.c head/contrib/zstd/lib/legacy/zstd_v07.h head/contrib/zstd/lib/zstd.h head/contrib/zstd/programs/.gitignore head/contrib/zstd/programs/Makefile head/contrib/zstd/programs/README.md head/contrib/zstd/programs/bench.c head/contrib/zstd/programs/bench.h head/contrib/zstd/programs/datagen.c head/contrib/zstd/programs/datagen.h head/contrib/zstd/programs/dibio.c head/contrib/zstd/programs/dibio.h head/contrib/zstd/programs/fileio.c head/contrib/zstd/programs/fileio.h head/contrib/zstd/programs/platform.h head/contrib/zstd/programs/util.h head/contrib/zstd/programs/zstd.1 head/contrib/zstd/programs/zstd.1.md head/contrib/zstd/programs/zstdcli.c head/contrib/zstd/tests/Makefile head/contrib/zstd/tests/datagencli.c head/contrib/zstd/tests/decodecorpus.c head/contrib/zstd/tests/fullbench.c head/contrib/zstd/tests/fuzzer.c head/contrib/zstd/tests/invalidDictionaries.c head/contrib/zstd/tests/legacy.c head/contrib/zstd/tests/longmatch.c head/contrib/zstd/tests/namespaceTest.c head/contrib/zstd/tests/paramgrill.c head/contrib/zstd/tests/playTests.sh head/contrib/zstd/tests/roundTripCrash.c head/contrib/zstd/tests/symbols.c head/contrib/zstd/tests/zbufftest.c head/contrib/zstd/tests/zstreamtest.c head/contrib/zstd/zlibWrapper/examples/zwrapbench.c head/contrib/zstd/zlibWrapper/gzcompatibility.h head/contrib/zstd/zlibWrapper/gzlib.c head/contrib/zstd/zlibWrapper/gzread.c head/contrib/zstd/zlibWrapper/gzwrite.c head/contrib/zstd/zlibWrapper/zstd_zlibwrapper.c head/contrib/zstd/zlibWrapper/zstd_zlibwrapper.h Directory Properties: head/contrib/zstd/ (props changed) Modified: head/contrib/zstd/CONTRIBUTING.md ============================================================================== --- head/contrib/zstd/CONTRIBUTING.md Tue Aug 22 11:11:10 2017 (r322783) +++ head/contrib/zstd/CONTRIBUTING.md Tue Aug 22 11:11:49 2017 (r322784) @@ -39,4 +39,4 @@ outlined on that page and do not file a public issue. ## License By contributing to Zstandard, you agree that your contributions will be licensed -under the [LICENSE](LICENSE) file in the root directory of this source tree. +under both the [LICENSE](LICENSE) file and the [COPYING](COPYING) file in the root directory of this source tree. Modified: head/contrib/zstd/Makefile ============================================================================== --- head/contrib/zstd/Makefile Tue Aug 22 11:11:10 2017 (r322783) +++ head/contrib/zstd/Makefile Tue Aug 22 11:11:49 2017 (r322784) @@ -74,14 +74,11 @@ zstdmt: zlibwrapper: $(MAKE) -C $(ZWRAPDIR) test -.PHONY: shortest -shortest: +.PHONY: test shortest +test shortest: + $(MAKE) -C $(PRGDIR) allVariants $(MAKE) -C $(TESTDIR) $@ -.PHONY: test -test: - $(MAKE) -C $(TESTDIR) $@ - .PHONY: examples examples: CPPFLAGS=-I../lib LDFLAGS=-L../lib $(MAKE) -C examples/ all @@ -146,6 +143,11 @@ gcc6build: clean gcc-6 -v CC=gcc-6 $(MAKE) all MOREFLAGS="-Werror" +.PHONY: gcc7build +gcc7build: clean + gcc-7 -v + CC=gcc-7 $(MAKE) all MOREFLAGS="-Werror" + .PHONY: clangbuild clangbuild: clean clang -v @@ -180,7 +182,7 @@ ppc64fuzz: clean CC=powerpc-linux-gnu-gcc QEMU_SYS=qemu-ppc64-static MOREFLAGS="-m64 -static" FUZZER_FLAGS=--no-big-tests $(MAKE) -C $(TESTDIR) fuzztest gpptest: clean - CC=g++ $(MAKE) -C $(PRGDIR) all CFLAGS="-O3 -Wall -Wextra -Wundef -Wshadow -Wcast-align -Werror" + CC=$(CXX) $(MAKE) -C $(PRGDIR) all CFLAGS="-O3 -Wall -Wextra -Wundef -Wshadow -Wcast-align -Werror" gcc5test: clean gcc-5 -v Modified: head/contrib/zstd/NEWS ============================================================================== --- head/contrib/zstd/NEWS Tue Aug 22 11:11:10 2017 (r322783) +++ head/contrib/zstd/NEWS Tue Aug 22 11:11:49 2017 (r322784) @@ -1,3 +1,18 @@ +v1.3.1 +New license : BSD + GPLv2 +perf: substantially decreased memory usage in Multi-threading mode, thanks to reports by Tino Reichardt (@mcmilk) +perf: Multi-threading supports up to 256 threads. Cap at 256 when more are requested (#760) +cli : improved and fixed --list command, by @ib (#772) +cli : command -vV to list supported formats, by @ib (#771) +build : fixed binary variants, reported by @svenha (#788) +build : fix Visual compilation for non x86/x64 targets, reported by Greg Slazinski (@GregSlazinski) (#718) +API exp : breaking change : ZSTD_getframeHeader() provides more information +API exp : breaking change : pinned down values of error codes +doc : fixed huffman example, by Ulrich Kunitz (@ulikunitz) +new : contrib/adaptive-compression, I/O driven compression strength, by Paul Cruz (@paulcruz74) +new : contrib/long_distance_matching, statistics by Stella Lau (@stellamplau) +updated : contrib/linux-kernel, by Nick Terrell (@terrelln) + v1.3.0 cli : new : `--list` command, by Paul Cruz cli : changed : xz/lzma support enabled by default Modified: head/contrib/zstd/README.md ============================================================================== --- head/contrib/zstd/README.md Tue Aug 22 11:11:10 2017 (r322783) +++ head/contrib/zstd/README.md Tue Aug 22 11:11:49 2017 (r322784) @@ -134,12 +134,12 @@ Going into `build` directory, you will find additional ### Status -Zstandard is currently deployed within Facebook. It is used daily to compress and decompress very large amounts of data in multiple formats and use cases. +Zstandard is currently deployed within Facebook. It is used continuously to compress large amounts of data in multiple formats and use cases. Zstandard is considered safe for production environments. ### License -Zstandard is [BSD-licensed](LICENSE). We also provide an [additional patent grant](PATENTS). +Zstandard is dual-licensed under [BSD](LICENSE) and [GPLv2](COPYING). ### Contributing Modified: head/contrib/zstd/circle.yml ============================================================================== --- head/contrib/zstd/circle.yml Tue Aug 22 11:11:10 2017 (r322783) +++ head/contrib/zstd/circle.yml Tue Aug 22 11:11:49 2017 (r322784) @@ -3,7 +3,7 @@ dependencies: - sudo dpkg --add-architecture i386 - sudo add-apt-repository -y ppa:ubuntu-toolchain-r/test; sudo apt-get -y -qq update - sudo apt-get -y install gcc-powerpc-linux-gnu gcc-arm-linux-gnueabi libc6-dev-armel-cross gcc-aarch64-linux-gnu libc6-dev-arm64-cross - - sudo apt-get -y install libstdc++-6-dev clang gcc g++ gcc-5 gcc-6 zlib1g-dev liblzma-dev + - sudo apt-get -y install libstdc++-7-dev clang gcc g++ gcc-5 gcc-6 gcc-7 zlib1g-dev liblzma-dev - sudo apt-get -y install linux-libc-dev:i386 libc6-dev-i386 test: @@ -45,7 +45,7 @@ test: parallel: true - ? | if [[ "$CIRCLE_NODE_INDEX" == "0" ]] ; then make ppc64build && make clean; fi && - if [[ "$CIRCLE_NODE_TOTAL" < "2" ]] || [[ "$CIRCLE_NODE_INDEX" == "1" ]]; then true && make clean; fi #could add another test here + if [[ "$CIRCLE_NODE_TOTAL" < "2" ]] || [[ "$CIRCLE_NODE_INDEX" == "1" ]]; then make gcc7build && make clean; fi #could add another test here : parallel: true - ? | @@ -64,7 +64,7 @@ test: #- gcc -v; make -C tests test32 MOREFLAGS="-I/usr/include/x86_64-linux-gnu" && make clean #- make uasan && make clean #- make asan32 && make clean - #- make -C tests test32 CC=clang MOREFLAGS="-g -fsanitize=address -I/usr/include/x86_64-linux-gnu" + #- make -C tests test32 CC=clang MOREFLAGS="-g -fsanitize=address -I/usr/include/x86_64-linux-gnu" # Valgrind tests #- CFLAGS="-O1 -g" make -C zlibWrapper valgrindTest && make clean #- make -C tests valgrindTest && make clean Modified: head/contrib/zstd/doc/educational_decoder/harness.c ============================================================================== --- head/contrib/zstd/doc/educational_decoder/harness.c Tue Aug 22 11:11:10 2017 (r322783) +++ head/contrib/zstd/doc/educational_decoder/harness.c Tue Aug 22 11:11:49 2017 (r322784) @@ -87,7 +87,7 @@ int main(int argc, char **argv) { } size_t decompressed_size = ZSTD_get_decompressed_size(input, input_size); - if (decompressed_size == -1) { + if (decompressed_size == (size_t)-1) { decompressed_size = MAX_COMPRESSION_RATIO * input_size; fprintf(stderr, "WARNING: Compressed data does not contain " "decompressed size, going to assume the compression " @@ -106,10 +106,16 @@ int main(int argc, char **argv) { return 1; } + dictionary_t* const parsed_dict = create_dictionary(); + if (dict) { + parse_dictionary(parsed_dict, dict, dict_size); + } size_t decompressed = ZSTD_decompress_with_dict(output, decompressed_size, - input, input_size, dict, dict_size); + input, input_size, parsed_dict); + free_dictionary(parsed_dict); + write_file(argv[2], output, decompressed); free(input); @@ -117,4 +123,3 @@ int main(int argc, char **argv) { free(dict); input = output = dict = NULL; } - Modified: head/contrib/zstd/doc/educational_decoder/zstd_decompress.c ============================================================================== --- head/contrib/zstd/doc/educational_decoder/zstd_decompress.c Tue Aug 22 11:11:10 2017 (r322783) +++ head/contrib/zstd/doc/educational_decoder/zstd_decompress.c Tue Aug 22 11:11:49 2017 (r322784) @@ -14,22 +14,8 @@ #include <stdio.h> #include <stdlib.h> #include <string.h> +#include "zstd_decompress.h" -/// Zstandard decompression functions. -/// `dst` must point to a space at least as large as the reconstructed output. -size_t ZSTD_decompress(void *const dst, const size_t dst_len, - const void *const src, const size_t src_len); -/// If `dict != NULL` and `dict_len >= 8`, does the same thing as -/// `ZSTD_decompress` but uses the provided dict -size_t ZSTD_decompress_with_dict(void *const dst, const size_t dst_len, - const void *const src, const size_t src_len, - const void *const dict, const size_t dict_len); - -/// Get the decompressed size of an input stream so memory can be allocated in -/// advance -/// Returns -1 if the size can't be determined -size_t ZSTD_get_decompressed_size(const void *const src, const size_t src_len); - /******* UTILITY MACROS AND TYPES *********************************************/ // Max block size decompressed size is 128 KB and literal blocks can't be // larger than their block @@ -108,10 +94,10 @@ static inline size_t IO_istream_len(const istream_t *c /// Advances the stream by `len` bytes, and returns a pointer to the chunk that /// was skipped. The stream must be byte aligned. -static inline const u8 *IO_read_bytes(istream_t *const in, size_t len); +static inline const u8 *IO_get_read_ptr(istream_t *const in, size_t len); /// Advances the stream by `len` bytes, and returns a pointer to the chunk that /// was skipped so it can be written to. -static inline u8 *IO_write_bytes(ostream_t *const out, size_t len); +static inline u8 *IO_get_write_ptr(ostream_t *const out, size_t len); /// Advance the inner state by `len` bytes. The stream must be byte aligned. static inline void IO_advance_input(istream_t *const in, size_t len); @@ -307,7 +293,7 @@ typedef struct { /// The decoded contents of a dictionary so that it doesn't have to be repeated /// for each frame that uses it -typedef struct { +struct dictionary_s { // Entropy tables HUF_dtable literals_dtable; FSE_dtable ll_dtable; @@ -322,7 +308,7 @@ typedef struct { u64 previous_offsets[3]; u32 dictionary_id; -} dictionary_t; +}; /// A tuple containing the parts necessary to decode and execute a ZSTD sequence /// command @@ -367,27 +353,36 @@ static void execute_sequences(frame_context_t *const c const sequence_command_t *const sequences, const size_t num_sequences); -// Parse a provided dictionary blob for use in decompression -static void parse_dictionary(dictionary_t *const dict, const u8 *src, - size_t src_len); -static void free_dictionary(dictionary_t *const dict); +// Copies literals and returns the total literal length that was copied +static u32 copy_literals(const size_t seq, istream_t *litstream, + ostream_t *const out); + +// Given an offset code from a sequence command (either an actual offset value +// or an index for previous offset), computes the correct offset and udpates +// the offset history +static size_t compute_offset(sequence_command_t seq, u64 *const offset_hist); + +// Given an offset, match length, and total output, as well as the frame +// context for the dictionary, determines if the dictionary is used and +// executes the copy operation +static void execute_match_copy(frame_context_t *const ctx, size_t offset, + size_t match_length, size_t total_output, + ostream_t *const out); + /******* END ZSTD HELPER STRUCTS AND PROTOTYPES *******************************/ size_t ZSTD_decompress(void *const dst, const size_t dst_len, const void *const src, const size_t src_len) { - return ZSTD_decompress_with_dict(dst, dst_len, src, src_len, NULL, 0); + dictionary_t* uninit_dict = create_dictionary(); + size_t const decomp_size = ZSTD_decompress_with_dict(dst, dst_len, src, + src_len, uninit_dict); + free_dictionary(uninit_dict); + return decomp_size; } size_t ZSTD_decompress_with_dict(void *const dst, const size_t dst_len, const void *const src, const size_t src_len, - const void *const dict, - const size_t dict_len) { - dictionary_t parsed_dict; - memset(&parsed_dict, 0, sizeof(dictionary_t)); - // dict_len < 8 is not a valid dictionary - if (dict && dict_len > 8) { - parse_dictionary(&parsed_dict, (const u8 *)dict, dict_len); - } + dictionary_t* parsed_dict) { istream_t in = IO_make_istream(src, src_len); ostream_t out = IO_make_ostream(dst, dst_len); @@ -396,11 +391,9 @@ size_t ZSTD_decompress_with_dict(void *const dst, cons // Multiple frames can be appended into a single file or stream. A frame is // totally independent, has a defined beginning and end, and a set of // parameters which tells the decoder how to decompress it." - while (IO_istream_len(&in) > 0) { - decode_frame(&out, &in, &parsed_dict); - } - free_dictionary(&parsed_dict); + /* this decoder assumes decompression of a single frame */ + decode_frame(&out, &in, parsed_dict); return out.ptr - (u8 *)dst; } @@ -424,30 +417,6 @@ static void decompress_data(frame_context_t *const ctx static void decode_frame(ostream_t *const out, istream_t *const in, const dictionary_t *const dict) { const u32 magic_number = IO_read_bits(in, 32); - - // Skippable frame - // - // "Magic_Number - // - // 4 Bytes, little-endian format. Value : 0x184D2A5?, which means any value - // from 0x184D2A50 to 0x184D2A5F. All 16 values are valid to identify a - // skippable frame." - if ((magic_number & ~0xFU) == 0x184D2A50U) { - // "Skippable frames allow the insertion of user-defined data into a - // flow of concatenated frames. Its design is pretty straightforward, - // with the sole objective to allow the decoder to quickly skip over - // user-defined data and continue decoding. - // - // Skippable frames defined in this specification are compatible with - // LZ4 ones." - const size_t frame_size = IO_read_bits(in, 32); - - // skip over frame - IO_advance_input(in, frame_size); - - return; - } - // Zstandard frame // // "Magic_Number @@ -460,8 +429,8 @@ static void decode_frame(ostream_t *const out, istream return; } - // not a real frame - ERROR("Invalid magic number"); + // not a real frame or a skippable frame + ERROR("Tried to decode non-ZSTD frame"); } /// Decode a frame that contains compressed data. Not all frames do as there @@ -672,8 +641,8 @@ static void decompress_data(frame_context_t *const ctx case 0: { // "Raw_Block - this is an uncompressed block. Block_Size is the // number of bytes to read and copy." - const u8 *const read_ptr = IO_read_bytes(in, block_len); - u8 *const write_ptr = IO_write_bytes(out, block_len); + const u8 *const read_ptr = IO_get_read_ptr(in, block_len); + u8 *const write_ptr = IO_get_write_ptr(out, block_len); // Copy the raw data into the output memcpy(write_ptr, read_ptr, block_len); @@ -685,8 +654,8 @@ static void decompress_data(frame_context_t *const ctx // "RLE_Block - this is a single byte, repeated N times. In which // case, Block_Size is the size to regenerate, while the // "compressed" block is just 1 byte (the byte to repeat)." - const u8 *const read_ptr = IO_read_bytes(in, 1); - u8 *const write_ptr = IO_write_bytes(out, block_len); + const u8 *const read_ptr = IO_get_read_ptr(in, 1); + u8 *const write_ptr = IO_get_write_ptr(out, block_len); // Copy `block_len` copies of `read_ptr[0]` to the output memset(write_ptr, read_ptr[0], block_len); @@ -832,13 +801,13 @@ static size_t decode_literals_simple(istream_t *const switch (block_type) { case 0: { // "Raw_Literals_Block - Literals are stored uncompressed." - const u8 *const read_ptr = IO_read_bytes(in, size); + const u8 *const read_ptr = IO_get_read_ptr(in, size); memcpy(*literals, read_ptr, size); break; } case 1: { // "RLE_Literals_Block - Literals consist of a single byte value repeated N times." - const u8 *const read_ptr = IO_read_bytes(in, 1); + const u8 *const read_ptr = IO_get_read_ptr(in, 1); memset(*literals, read_ptr[0], size); break; } @@ -949,7 +918,7 @@ static void decode_huf_table(HUF_dtable *const dtable, num_symbs = header - 127; const size_t bytes = (num_symbs + 1) / 2; - const u8 *const weight_src = IO_read_bytes(in, bytes); + const u8 *const weight_src = IO_get_read_ptr(in, bytes); for (int i = 0; i < num_symbs; i++) { // "They are encoded forward, 2 @@ -1157,7 +1126,7 @@ static void decompress_sequences(frame_context_t *cons } const size_t len = IO_istream_len(in); - const u8 *const src = IO_read_bytes(in, len); + const u8 *const src = IO_get_read_ptr(in, len); // "After writing the last bit containing information, the compressor writes // a single 1-bit and then fills the byte with 0-7 0 bits of padding." @@ -1262,7 +1231,7 @@ static void decode_seq_table(FSE_dtable *const table, } case seq_rle: { // "RLE_Mode : it's a single code, repeated Number_of_Sequences times." - const u8 symb = IO_read_bytes(in, 1)[0]; + const u8 symb = IO_get_read_ptr(in, 1)[0]; FSE_init_dtable_rle(table, symb); break; } @@ -1303,145 +1272,146 @@ static void execute_sequences(frame_context_t *const c for (size_t i = 0; i < num_sequences; i++) { const sequence_command_t seq = sequences[i]; - { - // If the sequence asks for more literals than are left, the - // sequence must be corrupted - if (seq.literal_length > IO_istream_len(&litstream)) { - CORRUPTION(); - } + const u32 literals_size = copy_literals(seq.literal_length, &litstream, out); + total_output += literals_size; + } - u8 *const write_ptr = IO_write_bytes(out, seq.literal_length); - const u8 *const read_ptr = - IO_read_bytes(&litstream, seq.literal_length); - // Copy literals to output - memcpy(write_ptr, read_ptr, seq.literal_length); + size_t const offset = compute_offset(seq, offset_hist); - total_output += seq.literal_length; - } + size_t const match_length = seq.match_length; - size_t offset; + execute_match_copy(ctx, offset, match_length, total_output, out); - // Offsets are special, we need to handle the repeat offsets - if (seq.offset <= 3) { - // "The first 3 values define a repeated offset and we will call - // them Repeated_Offset1, Repeated_Offset2, and Repeated_Offset3. - // They are sorted in recency order, with Repeated_Offset1 meaning - // 'most recent one'". + total_output += match_length; + } - // Use 0 indexing for the array - u32 idx = seq.offset - 1; - if (seq.literal_length == 0) { - // "There is an exception though, when current sequence's - // literals length is 0. In this case, repeated offsets are - // shifted by one, so Repeated_Offset1 becomes Repeated_Offset2, - // Repeated_Offset2 becomes Repeated_Offset3, and - // Repeated_Offset3 becomes Repeated_Offset1 - 1_byte." - idx++; - } + // Copy any leftover literals + { + size_t len = IO_istream_len(&litstream); + copy_literals(len, &litstream, out); + total_output += len; + } - if (idx == 0) { - offset = offset_hist[0]; - } else { - // If idx == 3 then literal length was 0 and the offset was 3, - // as per the exception listed above - offset = idx < 3 ? offset_hist[idx] : offset_hist[0] - 1; + ctx->current_total_output = total_output; +} - // If idx == 1 we don't need to modify offset_hist[2], since - // we're using the second-most recent code - if (idx > 1) { - offset_hist[2] = offset_hist[1]; - } - offset_hist[1] = offset_hist[0]; - offset_hist[0] = offset; - } +static u32 copy_literals(const size_t literal_length, istream_t *litstream, + ostream_t *const out) { + // If the sequence asks for more literals than are left, the + // sequence must be corrupted + if (literal_length > IO_istream_len(litstream)) { + CORRUPTION(); + } + + u8 *const write_ptr = IO_get_write_ptr(out, literal_length); + const u8 *const read_ptr = + IO_get_read_ptr(litstream, literal_length); + // Copy literals to output + memcpy(write_ptr, read_ptr, literal_length); + + return literal_length; +} + +static size_t compute_offset(sequence_command_t seq, u64 *const offset_hist) { + size_t offset; + // Offsets are special, we need to handle the repeat offsets + if (seq.offset <= 3) { + // "The first 3 values define a repeated offset and we will call + // them Repeated_Offset1, Repeated_Offset2, and Repeated_Offset3. + // They are sorted in recency order, with Repeated_Offset1 meaning + // 'most recent one'". + + // Use 0 indexing for the array + u32 idx = seq.offset - 1; + if (seq.literal_length == 0) { + // "There is an exception though, when current sequence's + // literals length is 0. In this case, repeated offsets are + // shifted by one, so Repeated_Offset1 becomes Repeated_Offset2, + // Repeated_Offset2 becomes Repeated_Offset3, and + // Repeated_Offset3 becomes Repeated_Offset1 - 1_byte." + idx++; + } + + if (idx == 0) { + offset = offset_hist[0]; } else { - // When it's not a repeat offset: - // "if (Offset_Value > 3) offset = Offset_Value - 3;" - offset = seq.offset - 3; + // If idx == 3 then literal length was 0 and the offset was 3, + // as per the exception listed above + offset = idx < 3 ? offset_hist[idx] : offset_hist[0] - 1; - // Shift back history - offset_hist[2] = offset_hist[1]; + // If idx == 1 we don't need to modify offset_hist[2], since + // we're using the second-most recent code + if (idx > 1) { + offset_hist[2] = offset_hist[1]; + } offset_hist[1] = offset_hist[0]; offset_hist[0] = offset; } + } else { + // When it's not a repeat offset: + // "if (Offset_Value > 3) offset = Offset_Value - 3;" + offset = seq.offset - 3; - size_t match_length = seq.match_length; + // Shift back history + offset_hist[2] = offset_hist[1]; + offset_hist[1] = offset_hist[0]; + offset_hist[0] = offset; + } + return offset; +} - u8 *write_ptr = IO_write_bytes(out, match_length); - if (total_output <= ctx->header.window_size) { - // In this case offset might go back into the dictionary - if (offset > total_output + ctx->dict_content_len) { - // The offset goes beyond even the dictionary - CORRUPTION(); - } - - if (offset > total_output) { - // "The rest of the dictionary is its content. The content act - // as a "past" in front of data to compress or decompress, so it - // can be referenced in sequence commands." - const size_t dict_copy = - MIN(offset - total_output, match_length); - const size_t dict_offset = - ctx->dict_content_len - (offset - total_output); - - memcpy(write_ptr, ctx->dict_content + dict_offset, dict_copy); - write_ptr += dict_copy; - match_length -= dict_copy; - } - } else if (offset > ctx->header.window_size) { +static void execute_match_copy(frame_context_t *const ctx, size_t offset, + size_t match_length, size_t total_output, + ostream_t *const out) { + u8 *write_ptr = IO_get_write_ptr(out, match_length); + if (total_output <= ctx->header.window_size) { + // In this case offset might go back into the dictionary + if (offset > total_output + ctx->dict_content_len) { + // The offset goes beyond even the dictionary CORRUPTION(); } - // We must copy byte by byte because the match length might be larger - // than the offset - // ex: if the output so far was "abc", a command with offset=3 and - // match_length=6 would produce "abcabcabc" as the new output - for (size_t i = 0; i < match_length; i++) { - *write_ptr = *(write_ptr - offset); - write_ptr++; - } + if (offset > total_output) { + // "The rest of the dictionary is its content. The content act + // as a "past" in front of data to compress or decompress, so it + // can be referenced in sequence commands." + const size_t dict_copy = + MIN(offset - total_output, match_length); + const size_t dict_offset = + ctx->dict_content_len - (offset - total_output); - total_output += seq.match_length; + memcpy(write_ptr, ctx->dict_content + dict_offset, dict_copy); + write_ptr += dict_copy; + match_length -= dict_copy; + } + } else if (offset > ctx->header.window_size) { + CORRUPTION(); } - // Copy any leftover literals - { - size_t len = IO_istream_len(&litstream); - u8 *const write_ptr = IO_write_bytes(out, len); - const u8 *const read_ptr = IO_read_bytes(&litstream, len); - memcpy(write_ptr, read_ptr, len); - - total_output += len; + // We must copy byte by byte because the match length might be larger + // than the offset + // ex: if the output so far was "abc", a command with offset=3 and + // match_length=6 would produce "abcabcabc" as the new output + for (size_t j = 0; j < match_length; j++) { + *write_ptr = *(write_ptr - offset); + write_ptr++; } - - ctx->current_total_output = total_output; } /******* END SEQUENCE EXECUTION ***********************************************/ /******* OUTPUT SIZE COUNTING *************************************************/ -static void traverse_frame(const frame_header_t *const header, istream_t *const in); - /// Get the decompressed size of an input stream so memory can be allocated in /// advance. -/// This is more complex than the implementation in the reference -/// implementation, as this API allows for the decompression of multiple -/// concatenated frames. +/// This implementation assumes `src` points to a single ZSTD-compressed frame size_t ZSTD_get_decompressed_size(const void *src, const size_t src_len) { istream_t in = IO_make_istream(src, src_len); - size_t dst_size = 0; - // Each frame header only gives us the size of its frame, so iterate over - // all - // frames - while (IO_istream_len(&in) > 0) { + // get decompressed size from ZSTD frame header + { const u32 magic_number = IO_read_bits(&in, 32); - if ((magic_number & ~0xFU) == 0x184D2A50U) { - // skippable frame, this has no impact on output size - const size_t frame_size = IO_read_bits(&in, 32); - IO_advance_input(&in, frame_size); - } else if (magic_number == 0xFD2FB528U) { + if (magic_number == 0xFD2FB528U) { // ZSTD frame frame_header_t header; parse_frame_header(&header, &in); @@ -1451,68 +1421,42 @@ size_t ZSTD_get_decompressed_size(const void *src, con return -1; } - dst_size += header.frame_content_size; - - // Consume the input from the frame to reach the start of the next - traverse_frame(&header, &in); + return header.frame_content_size; } else { - // not a real frame - ERROR("Invalid magic number"); + // not a real frame or skippable frame + ERROR("ZSTD frame magic number did not match"); } } - - return dst_size; } +/******* END OUTPUT SIZE COUNTING *********************************************/ -/// Iterate over each block in a frame to find the end of it, to get to the -/// start of the next frame -static void traverse_frame(const frame_header_t *const header, istream_t *const in) { - int last_block = 0; +/******* DICTIONARY PARSING ***************************************************/ +#define DICT_SIZE_ERROR() ERROR("Dictionary size cannot be less than 8 bytes") +#define NULL_SRC() ERROR("Tried to create dictionary with pointer to null src"); - do { - // Parse the block header - last_block = IO_read_bits(in, 1); - const int block_type = IO_read_bits(in, 2); - const size_t block_len = IO_read_bits(in, 21); - - switch (block_type) { - case 0: // Raw block, block_len bytes - IO_advance_input(in, block_len); - break; - case 1: // RLE block, 1 byte - IO_advance_input(in, 1); - break; - case 2: // Compressed block, compressed size is block_len - IO_advance_input(in, block_len); - break; - case 3: - // Reserved block type - CORRUPTION(); - break; - default: - IMPOSSIBLE(); - } - } while (!last_block); - - if (header->content_checksum_flag) { - IO_advance_input(in, 4); +dictionary_t* create_dictionary() { + dictionary_t* dict = calloc(1, sizeof(dictionary_t)); + if (!dict) { + BAD_ALLOC(); } + return dict; } -/******* END OUTPUT SIZE COUNTING *********************************************/ - -/******* DICTIONARY PARSING ***************************************************/ static void init_dictionary_content(dictionary_t *const dict, istream_t *const in); -static void parse_dictionary(dictionary_t *const dict, const u8 *src, +void parse_dictionary(dictionary_t *const dict, const void *src, size_t src_len) { + const u8 *byte_src = (const u8 *)src; memset(dict, 0, sizeof(dictionary_t)); + if (src == NULL) { /* cannot initialize dictionary with null src */ + NULL_SRC(); + } if (src_len < 8) { - INP_SIZE(); + DICT_SIZE_ERROR(); } - istream_t in = IO_make_istream(src, src_len); + istream_t in = IO_make_istream(byte_src, src_len); const u32 magic_number = IO_read_bits(&in, 32); if (magic_number != 0xEC30A437) { @@ -1564,13 +1508,13 @@ static void init_dictionary_content(dictionary_t *cons BAD_ALLOC(); } - const u8 *const content = IO_read_bytes(in, dict->content_size); + const u8 *const content = IO_get_read_ptr(in, dict->content_size); memcpy(dict->content, content, dict->content_size); } /// Free an allocated dictionary -static void free_dictionary(dictionary_t *const dict) { +void free_dictionary(dictionary_t *const dict) { HUF_free_dtable(&dict->literals_dtable); FSE_free_dtable(&dict->ll_dtable); FSE_free_dtable(&dict->of_dtable); @@ -1579,6 +1523,8 @@ static void free_dictionary(dictionary_t *const dict) free(dict->content); memset(dict, 0, sizeof(dictionary_t)); + + free(dict); } /******* END DICTIONARY PARSING ***********************************************/ @@ -1657,7 +1603,7 @@ static inline size_t IO_istream_len(const istream_t *c /// Returns a pointer where `len` bytes can be read, and advances the internal /// state. The stream must be byte aligned. -static inline const u8 *IO_read_bytes(istream_t *const in, size_t len) { +static inline const u8 *IO_get_read_ptr(istream_t *const in, size_t len) { if (len > in->len) { INP_SIZE(); } @@ -1671,7 +1617,7 @@ static inline const u8 *IO_read_bytes(istream_t *const return ptr; } /// Returns a pointer to write `len` bytes to, and advances the internal state -static inline u8 *IO_write_bytes(ostream_t *const out, size_t len) { +static inline u8 *IO_get_write_ptr(ostream_t *const out, size_t len) { if (len > out->len) { OUT_SIZE(); } @@ -1710,7 +1656,7 @@ static inline istream_t IO_make_istream(const u8 *in, /// `in` must be byte aligned static inline istream_t IO_make_sub_istream(istream_t *const in, size_t len) { // Consume `len` bytes of the parent stream - const u8 *const ptr = IO_read_bytes(in, len); + const u8 *const ptr = IO_get_read_ptr(in, len); // Make a substream using the pointer to those `len` bytes return IO_make_istream(ptr, len); @@ -1814,7 +1760,7 @@ static size_t HUF_decompress_1stream(const HUF_dtable if (len == 0) { INP_SIZE(); } - const u8 *const src = IO_read_bytes(in, len); + const u8 *const src = IO_get_read_ptr(in, len); // "Each bitstream must be read backward, that is starting from the end down // to the beginning. Therefore it's necessary to know the size of each @@ -2065,7 +2011,7 @@ static size_t FSE_decompress_interleaved2(const FSE_dt if (len == 0) { INP_SIZE(); } - const u8 *const src = IO_read_bytes(in, len); + const u8 *const src = IO_get_read_ptr(in, len); // "Each bitstream must be read backward, that is starting from the end down // to the beginning. Therefore it's necessary to know the size of each @@ -2192,7 +2138,7 @@ static void FSE_init_dtable(FSE_dtable *const dtable, } // Now we can fill baseline and num bits - for (int i = 0; i < size; i++) { + for (size_t i = 0; i < size; i++) { u8 symbol = dtable->symbols[i]; u16 next_state_desc = state_desc[symbol]++; // Fills in the table appropriately, next_state_desc increases by symbol @@ -2355,4 +2301,3 @@ static void FSE_copy_dtable(FSE_dtable *const dst, con memcpy(dst->new_state_base, src->new_state_base, size * sizeof(u16)); } /******* END FSE PRIMITIVES ***************************************************/ - Modified: head/contrib/zstd/doc/educational_decoder/zstd_decompress.h ============================================================================== --- head/contrib/zstd/doc/educational_decoder/zstd_decompress.h Tue Aug 22 11:11:10 2017 (r322783) +++ head/contrib/zstd/doc/educational_decoder/zstd_decompress.h Tue Aug 22 11:11:49 2017 (r322784) @@ -7,10 +7,52 @@ * of patent rights can be found in the PATENTS file in the same directory. */ +/******* EXPOSED TYPES ********************************************************/ +/* +* Contains the parsed contents of a dictionary +* This includes Huffman and FSE tables used for decoding and data on offsets +*/ +typedef struct dictionary_s dictionary_t; +/******* END EXPOSED TYPES ****************************************************/ + +/******* DECOMPRESSION FUNCTIONS **********************************************/ +/// Zstandard decompression functions. +/// `dst` must point to a space at least as large as the reconstructed output. size_t ZSTD_decompress(void *const dst, const size_t dst_len, - const void *const src, const size_t src_len); + const void *const src, const size_t src_len); + +/// If `dict != NULL` and `dict_len >= 8`, does the same thing as +/// `ZSTD_decompress` but uses the provided dict size_t ZSTD_decompress_with_dict(void *const dst, const size_t dst_len, - const void *const src, const size_t src_len, - const void *const dict, const size_t dict_len); + const void *const src, const size_t src_len, + dictionary_t* parsed_dict); + +/// Get the decompressed size of an input stream so memory can be allocated in +/// advance +/// Returns -1 if the size can't be determined +/// Assumes decompression of a single frame size_t ZSTD_get_decompressed_size(const void *const src, const size_t src_len); +/******* END DECOMPRESSION FUNCTIONS ******************************************/ +/******* DICTIONARY MANAGEMENT ***********************************************/ +/* + * Return a valid dictionary_t pointer for use with dictionary initialization + * or decompression + */ +dictionary_t* create_dictionary(); + +/* + * Parse a provided dictionary blob for use in decompression + * `src` -- must point to memory space representing the dictionary + * `src_len` -- must provide the dictionary size + * `dict` -- will contain the parsed contents of the dictionary and + * can be used for decompression + */ +void parse_dictionary(dictionary_t *const dict, const void *src, + size_t src_len); + +/* + * Free internal Huffman tables, FSE tables, and dictionary content + */ +void free_dictionary(dictionary_t *const dict); +/******* END DICTIONARY MANAGEMENT *******************************************/ Modified: head/contrib/zstd/doc/zstd_compression_format.md ============================================================================== --- head/contrib/zstd/doc/zstd_compression_format.md Tue Aug 22 11:11:10 2017 (r322783) +++ head/contrib/zstd/doc/zstd_compression_format.md Tue Aug 22 11:11:49 2017 (r322784) @@ -16,7 +16,7 @@ Distribution of this document is unlimited. ### Version -0.2.5 (31/03/17) +0.2.6 (19/08/17) Introduction @@ -106,7 +106,7 @@ The structure of a single Zstandard frame is following | `Magic_Number` | `Frame_Header` |`Data_Block`| [More data blocks] | [`Content_Checksum`] | |:--------------:|:--------------:|:----------:| ------------------ |:--------------------:| -| 4 bytes | 2-14 bytes | n bytes | | 0-4 bytes | +| 4 bytes | 2-14 bytes | n bytes | | 0-4 bytes | __`Magic_Number`__ @@ -1249,23 +1249,30 @@ Consequently, a last byte of `0` is not possible. And the final-bit-flag itself is not part of the useful bitstream. Hence, the last byte contains between 0 and 7 useful bits. -For example, if the literal sequence "0145" was encoded using the prefix codes above, -it would be encoded as: -``` -00000001 01110000 -``` +Starting from the end, +it's possible to read the bitstream in a __little-endian__ fashion, +keeping track of already used bits. Since the bitstream is encoded in reverse +order, starting from the end read symbols in forward order. +For example, if the literal sequence "0145" was encoded using above prefix code, +it would be encoded (in reverse order) as: + |Symbol | 5 | 4 | 1 | 0 | Padding | |--------|------|------|----|---|---------| -|Encoding|`0000`|`0001`|`01`|`1`| `10000` | +|Encoding|`0000`|`0001`|`01`|`1`| `00001` | -Starting from the end, -it's possible to read the bitstream in a __little-endian__ fashion, -keeping track of already used bits. Since the bitstream is encoded in reverse -order, by starting at the end the symbols can be read in forward order. +Resulting in following 2-bytes bitstream : +``` +00010000 00001101 +``` -Reading the last `Max_Number_of_Bits` bits, -it's then possible to compare extracted value to decoding table, +Here is an alternative representation with the symbol codes separated by underscore: +``` +0001_0000 00001_1_01 +``` + +Reading highest `Max_Number_of_Bits` bits, +it's possible to compare extracted value to decoding table, determining the symbol to decode and number of bits to discard. The process continues up to reading the required number of symbols per stream. @@ -1516,12 +1523,13 @@ to crosscheck that an implementation build its decodin Version changes --------------- +- 0.2.6 : fixed an error in huffman example, by Ulrich Kunitz - 0.2.5 : minor typos and clarifications - 0.2.4 : section restructuring, by Sean Purcell - 0.2.3 : clarified several details, by Sean Purcell - 0.2.2 : added predefined codes, by Johannes Rudolph - 0.2.1 : clarify field names, by Przemyslaw Skibinski -- 0.2.0 : numerous format adjustments for zstd v0.8 +- 0.2.0 : numerous format adjustments for zstd v0.8+ - 0.1.2 : limit Huffman tree depth to 11 bits - 0.1.1 : reserved dictID ranges - 0.1.0 : initial release Modified: head/contrib/zstd/doc/zstd_manual.html ============================================================================== --- head/contrib/zstd/doc/zstd_manual.html Tue Aug 22 11:11:10 2017 (r322783) +++ head/contrib/zstd/doc/zstd_manual.html Tue Aug 22 11:11:49 2017 (r322784) @@ -1,10 +1,10 @@ <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"> -<title>zstd 1.3.0 Manual</title> +<title>zstd 1.3.1 Manual</title> </head> <body> -<h1>zstd 1.3.0 Manual</h1> +<h1>zstd 1.3.1 Manual</h1> <hr> <a name="Contents"></a><h2>Contents</h2> <ol> @@ -73,29 +73,43 @@ or an errorCode if it fails (which can be tested using ZSTD_isError()). </p></pre><BR> -<pre><b>unsigned long long ZSTD_getDecompressedSize(const void* src, size_t srcSize); -</b><p> NOTE: This function is planned to be obsolete, in favor of ZSTD_getFrameContentSize(). - ZSTD_getFrameContentSize() works the same way, - returning the decompressed size of a single frame, - but distinguishes empty frames from frames with an unknown size, or errors. - - 'src' is the start of a zstd compressed frame. - @return : content size to be decompressed, as a 64-bits value _if known_, 0 otherwise. - note 1 : decompressed size is an optional field, it may not be present, typically in streaming mode. - When `return==0`, data to decompress could be any size. +<pre><b>#define ZSTD_CONTENTSIZE_UNKNOWN (0ULL - 1) +#define ZSTD_CONTENTSIZE_ERROR (0ULL - 2) +unsigned long long ZSTD_getFrameContentSize(const void *src, size_t srcSize); +</b><p> `src` should point to the start of a ZSTD encoded frame. + `srcSize` must be at least as large as the frame header. + hint : any size >= `ZSTD_frameHeaderSize_max` is large enough. + @return : - decompressed size of the frame in `src`, if known + - ZSTD_CONTENTSIZE_UNKNOWN if the size cannot be determined + - ZSTD_CONTENTSIZE_ERROR if an error occurred (e.g. invalid magic number, srcSize too small) + note 1 : a 0 return value means the frame is valid but "empty". + note 2 : decompressed size is an optional field, it may not be present, typically in streaming mode. + When `return==ZSTD_CONTENTSIZE_UNKNOWN`, data to decompress could be any size. In which case, it's necessary to use streaming mode to decompress data. - Optionally, application can use ZSTD_decompress() while relying on implied limits. - (For example, data may be necessarily cut into blocks <= 16 KB). - note 2 : decompressed size is always present when compression is done with ZSTD_compress() - note 3 : decompressed size can be very large (64-bits value), + Optionally, application can rely on some implicit limit, + as ZSTD_decompress() only needs an upper bound of decompressed size. + (For example, data could be necessarily cut into blocks <= 16 KB). + note 3 : decompressed size is always present when compression is done with ZSTD_compress() + note 4 : decompressed size can be very large (64-bits value), potentially larger than what local system can handle as a single memory segment. In which case, it's necessary to use streaming mode to decompress data. - note 4 : If source is untrusted, decompressed size could be wrong or intentionally modified. - Always ensure result fits within application's authorized limits. + note 5 : If source is untrusted, decompressed size could be wrong or intentionally modified. + Always ensure return value fits within application's authorized limits. Each application can set its own limits. - note 5 : when `return==0`, if precise failure cause is needed, use ZSTD_getFrameHeader() to know more. + note 6 : This function replaces ZSTD_getDecompressedSize() </p></pre><BR> *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201708221111.v7MBBoTZ055381>