The branch, master has been updated via c4e576052fa s4-samr: Fix missing check for GnuTLS errors from E_old_pw_hash() via 8a91ffa6bd6 fuzz: add lzxpress compress/decompress round-trip via 6c9fd8fbdbe fuzz: add fuzz_lzxpress_compress via 505d2879fa8 compression:tests: align test names with functions via 05c760165bf compression: add a few comments, including MS-XCA pointers. via 383a7cfed98 compression: remove always false constant comparison via e36cb10b162 compression: lzxpress decompress empty string as empty string via 1ca44492941 compression: fix lzxpress decompress with trailing flags via d8a90d2a8fc compression:tests: test lzxpress in some edge cases via 075df819cce compression: Move maximum length calculation out of inner loop via 877f007f32d compression: Use correct values for max len and offset via fe5fa7e1974 compression: Replace divisions with shifts via 131eb752699 compression: Remove unneeded loop variable via 5b1f8ea8d3e compression: Reduce scope of variables via 1a964210d24 compression: Use PUSH_LE_U32 for first output buffer write via 41b88d35ce6 compression: Add bounds check for first output buffer write via 0c813ee5637 compression: Remove helper variables str1 and str2 via 430bcd7a083 compression: Fix writing output flags via bb9115e023b compression: Remove byte_left variable via 417e0c914fd compression: Remove redundant bounds check via 6f3f1ba5b4d compression: Add range check for indic_pos via b62fbc4a535 compression: Remove redundant nibble_index check via 52982c01a59 compression: Make use of PUSH_LE_Uxx macros via f2ea8d4c056 compression: Simplify code by making indic_pos an index via b1534457982 compression: Make use of CHECK_{IN,OUT}PUT_BYTES macros via ea42717ccae compression: Simplify code by removing metadata_size variable via 69244b52ed4 compression: Use correct value for indic_pos via 7fab9f90e8a compression: Use correct value for nibble_index via f8feac11cbb compression: Simplify redundant branches via d368fa61cfc compression: Consistently use PUSH_LE_Uxx macros via 9516b268458 compression: Use explicit data sizes via eb7f139dec0 compression tests: Add additional compression tests via 3c2f1f03c19 compression: fix lzxpress-compress via 8f7fbc5c8fd compression: lzxpress_compress: fix no-op shift of 0 via a8fb45247ba compression: fix lzxpress_decompress via f67ff611e96 compression tests: add test for legacy compressed data via 4bcdc3bf30a compression tests: add LZXpress tests based on [MS-XCA] via eddefe3c62a util/base64: decode_data_blob_talloc catches talloc error from be2e2044b8e s3: libsmbclient: Cope with SMB2 servers that return STATUS_USER_SESSION_DELETED on a SMB2_ECHO (SMB2_OP_KEEPALIVE) call with a NULL session.
https://git.samba.org/?p=samba.git;a=shortlog;h=master - Log ----------------------------------------------------------------- commit c4e576052fa9bc57d288bed69abb599e1f9bb27b Author: Andrew Bartlett <abart...@samba.org> Date: Thu May 12 10:54:22 2022 +1200 s4-samr: Fix missing check for GnuTLS errors from E_old_pw_hash() Not likely to be an issue in the real world as the earlier calls will have failed if weak crypto was disabled, but this was missed in dce944e8a1119034f184336f6b71a28080152a0a. Signed-off-by: Andrew Bartlett <abart...@samba.org> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Autobuild-User(master): Andrew Bartlett <abart...@samba.org> Autobuild-Date(master): Thu May 12 03:18:42 UTC 2022 on sn-devel-184 commit 8a91ffa6bd64746358faf8661649c33f683759ef Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Wed May 11 12:08:54 2022 +1200 fuzz: add lzxpress compress/decompress round-trip We say it is an error to end up at a different result. Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 6c9fd8fbdbecc47e0595d3606bccf7d143b01b61 Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Wed May 11 12:08:06 2022 +1200 fuzz: add fuzz_lzxpress_compress Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 505d2879fa813796bf16af27615f0984bc71ad36 Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Wed May 11 17:21:46 2022 +1200 compression:tests: align test names with functions You'll thank me if you're ever debugging these and wondering why 'lzxpress4' calls 'lzxpress2' (or is it the other way round?). Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 05c760165bffa246b724d1471e307c488171b749 Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Wed May 11 16:20:46 2022 +1200 compression: add a few comments, including MS-XCA pointers. Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 383a7cfed9856b9057f2e56a1a26b8d4247ebbb6 Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Wed May 11 10:25:13 2022 +1200 compression: remove always false constant comparison We set `uncompressed_pos = 0;` unconditionally, just ~10 lines up. Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit e36cb10b1629c1bf8d8c365c02bbe1e81cd75548 Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Wed May 11 16:06:38 2022 +1200 compression: lzxpress decompress empty string as empty string This mirrors the behaviour of lzxpress_compress, which "encodes" an empty string as an empty string. Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 1ca444929417a8c86108776bba0ad6be3e5efff1 Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Wed May 11 12:46:21 2022 +1200 compression: fix lzxpress decompress with trailing flags Every so often, lzxpress adds a 32-bit block of indicator flags to help decode the next clump of 32 code words. A naive compressor (such as we have) might do this at the very end for flags that aren't actually used because there are no more bytes to decompress. If that happens we need to stop processing, or we'll come to worse outcome at the next CHECK_INPUT_BYTES. Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit d8a90d2a8fc5f42859297c771bc83ec12f45a658 Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Wed May 11 15:24:38 2022 +1200 compression:tests: test lzxpress in some edge cases Empty strings and trailing flag blocks. (found with Honggfuzz and a round-trip fuzzer that aborts if the strings differ). Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 075df819cce783d69069943f39bead833f3628ef Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Tue Mar 8 12:27:10 2022 +1300 compression: Move maximum length calculation out of inner loop This makes the code clearer. Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit 877f007f32d2cee8944b747be988cc062d13d5c0 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Tue Mar 8 12:25:59 2022 +1300 compression: Use correct values for max len and offset Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit fe5fa7e19740896c21ab374cbf1f0f44a0412c94 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Tue Mar 8 12:21:02 2022 +1300 compression: Replace divisions with shifts This is more consistent with the compression code. Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit 131eb7526996fc90eef2a5c2aae9ac15c2f258ff Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Tue Mar 8 12:19:45 2022 +1300 compression: Remove unneeded loop variable Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 5b1f8ea8d3ec4ee8b56cbf81e568ce7aea57b050 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Tue Mar 8 12:17:15 2022 +1300 compression: Reduce scope of variables This makes the code clearer. Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 1a964210d243737d0f31ee93c546fc33566745b1 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Tue Mar 8 12:13:12 2022 +1300 compression: Use PUSH_LE_U32 for first output buffer write Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 41b88d35ce6b120a1252093ea55ef80b7685e71e Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Tue Mar 8 12:11:51 2022 +1300 compression: Add bounds check for first output buffer write Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit 0c813ee56377c51bf4be786633b863f85a5f540e Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Tue Mar 8 12:10:01 2022 +1300 compression: Remove helper variables str1 and str2 This simplifies the code and makes it clearer. Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit 430bcd7a083a2dfbd12361f1ad352bc33e7963cb Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Tue Mar 8 12:02:13 2022 +1300 compression: Fix writing output flags If indic_bit == 0, the shift amount of 32 - indic_bit == 32 will equal the width of a 32-bit integer type, and these shifts will invoke undefined behaviour, which is likely to cause incorrect output. Fix this by not shifting a 32-bit integer type by 32 bits or more. Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit bb9115e023bb304e19aac074294694170c31dc51 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 20:33:45 2022 +1300 compression: Remove byte_left variable We can simplify this code using the identity: byte_left + uncompressed_pos = uncompressed_size Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit 417e0c914fdb64c58631e3dd862f704ce53dfeed Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 20:31:33 2022 +1300 compression: Remove redundant bounds check Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit 6f3f1ba5b4d45085a8aacc72f77b5a7d239a9cb2 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 20:30:42 2022 +1300 compression: Add range check for indic_pos This now matches the other use of indic_pos. Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit b62fbc4a535a84167ee4ddff244e66536742a618 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 20:28:05 2022 +1300 compression: Remove redundant nibble_index check If nibble_index is non-zero, we have already written to it, and so don't need to check again that it is in bounds. Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit 52982c01a596284b00cd9d0a4addcb6b73eed9cd Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 20:24:48 2022 +1300 compression: Make use of PUSH_LE_Uxx macros Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit f2ea8d4c056a20a42c4168c816b858fd6b433ed0 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 20:21:32 2022 +1300 compression: Simplify code by making indic_pos an index Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit b153445798273b10751438c3a01e6d676ec6820d Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 19:38:08 2022 +1300 compression: Make use of CHECK_{IN,OUT}PUT_BYTES macros Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit ea42717ccae9be6872e698270d8bedcb61a1b420 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 20:12:46 2022 +1300 compression: Simplify code by removing metadata_size variable Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit 69244b52ed4faa047b4b4117da4d1f9c58ba11e7 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 20:09:40 2022 +1300 compression: Use correct value for indic_pos Previously, we were setting this to the wrong value and overwriting existing output data. Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit 7fab9f90e8a90318b279b1d69656fd997a597665 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 20:09:40 2022 +1300 compression: Use correct value for nibble_index Previously, we were setting this to the wrong value and overwriting existing output data. Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit f8feac11cbba9a955485b0c4b12f386e9ce6c385 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 19:58:51 2022 +1300 compression: Simplify redundant branches Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit d368fa61cfcd3bc4504db01d55b4e54b289e511e Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 19:34:00 2022 +1300 compression: Consistently use PUSH_LE_Uxx macros Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 9516b268458dc2afd8e802c7c646aa565f84ffc3 Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Mon Mar 7 19:30:43 2022 +1300 compression: Use explicit data sizes Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit eb7f139dec08dec578c2ce20c418287c2834198d Author: Joseph Sutton <josephsut...@catalyst.net.nz> Date: Tue Mar 8 10:38:09 2022 +1300 compression tests: Add additional compression tests Signed-off-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 3c2f1f03c1937b180d539ad9bb96540ce1dd957b Author: Matt Suiche <msui...@comae.com> Date: Tue Mar 23 20:33:34 2021 +0400 compression: fix lzxpress-compress Signed-off-by: Matt Suiche <msui...@comae.com> Reviewed-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit 8f7fbc5c8fd0fba8542f6080908eeaa1c2d479b8 Author: Matt Suiche <msui...@comae.com> Date: Tue Jun 15 11:14:51 2021 +1200 compression: lzxpress_compress: fix no-op shift of 0 Signed-off-by: Matt Suiche <msui...@comae.com> Reviewed-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit a8fb45247baf9af8e3f2223e5a384fac4351dbc3 Author: Matt Suiche <msui...@comae.com> Date: Tue Jun 15 11:52:37 2021 +1200 compression: fix lzxpress_decompress Signed-off-by: Matt Suiche <msui...@comae.com> Reviewed-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> commit f67ff611e96b2d229a8e8d0e8b13b89916c5f27d Author: Matt Suiche <msui...@comae.com> Date: Thu Mar 25 16:50:42 2021 +0400 compression tests: add test for legacy compressed data Signed-off-by: Matt Suiche <msui...@comae.com> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit 4bcdc3bf30a0a2548a8bbf216ad960cc7d55eaae Author: Matt Suiche <msui...@comae.com> Date: Tue Jun 15 10:45:19 2021 +1200 compression tests: add LZXpress tests based on [MS-XCA] MS-XCA contains examples, and we should at least get those right. Signed-off-by: Matt Suiche <msui...@comae.com> Reviewed-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> commit eddefe3c62a537ed0b94d3d5f4ab58ae10d00828 Author: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Date: Wed Apr 7 06:53:16 2021 +1200 util/base64: decode_data_blob_talloc catches talloc error Signed-off-by: Douglas Bagnall <douglas.bagn...@catalyst.net.nz> Reviewed-by: Joseph Sutton <josephsut...@catalyst.net.nz> Reviewed-by: Andrew Bartlett <abart...@samba.org> ----------------------------------------------------------------------- Summary of changes: lib/compression/lzxpress.c | 352 ++++++++++---------- lib/compression/testsuite.c | 367 ++++++++++++++++++++- .../{fuzz_lzxpress.c => fuzz_lzxpress_compress.c} | 2 +- ...{fuzz_lzxpress.c => fuzz_lzxpress_round_trip.c} | 24 +- lib/fuzzing/wscript_build | 10 + lib/util/base64.c | 11 +- source4/rpc_server/samr/samr_password.c | 2 +- 7 files changed, 572 insertions(+), 196 deletions(-) copy lib/fuzzing/{fuzz_lzxpress.c => fuzz_lzxpress_compress.c} (94%) copy lib/fuzzing/{fuzz_lzxpress.c => fuzz_lzxpress_round_trip.c} (64%) Changeset truncated at 500 lines: diff --git a/lib/compression/lzxpress.c b/lib/compression/lzxpress.c index 3453dd36f2a..71b39c1efb3 100644 --- a/lib/compression/lzxpress.c +++ b/lib/compression/lzxpress.c @@ -37,81 +37,78 @@ #include "../lib/util/byteorder.h" -#define __BUF_POS_CONST(buf,ofs)(((const uint8_t *)buf)+(ofs)) -#define __PULL_BYTE(buf,ofs) \ - ((uint8_t)((*__BUF_POS_CONST(buf,ofs)) & 0xFF)) - -#ifndef PULL_LE_UINT16 -#define PULL_LE_UINT16(buf,ofs) ((uint16_t)( \ - ((uint16_t)(((uint16_t)(__PULL_BYTE(buf,(ofs)+0))) << 0)) | \ - ((uint16_t)(((uint16_t)(__PULL_BYTE(buf,(ofs)+1))) << 8)) \ -)) -#endif - -#ifndef PULL_LE_UINT32 -#define PULL_LE_UINT32(buf,ofs) ((uint32_t)( \ - ((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+0))) << 0)) | \ - ((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+1))) << 8)) | \ - ((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+2))) << 16)) | \ - ((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+3))) << 24)) \ -)) -#endif +#define __CHECK_BYTES(__size, __index, __needed) do { \ + if (unlikely(__index >= __size)) { \ + return -1; \ + } else { \ + uint32_t __avail = __size - __index; \ + if (unlikely(__needed > __avail)) { \ + return -1; \ + } \ + } \ +} while(0) + +#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) ssize_t lzxpress_compress(const uint8_t *uncompressed, uint32_t uncompressed_size, uint8_t *compressed, uint32_t max_compressed_size) { - uint32_t uncompressed_pos, compressed_pos, byte_left; - uint32_t max_offset, best_offset; - int32_t offset; - uint32_t max_len, len, best_len; - const uint8_t *str1, *str2; + /* + * This is the algorithm in [MS-XCA] 2.3 "Plain LZ77 Compression". + * + * It avoids Huffman encoding by including literal bytes inline when a + * match is not found. Every so often it includes a uint32 bit map + * flagging which positions contain matches and which contain + * literals. The encoding of matches is of variable size, depending on + * 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; - uint8_t *indic_pos; + uint32_t indic_pos; uint32_t indic_bit, nibble_index; - uint32_t metadata_size; - uint16_t metadata; - uint16_t *dest; - if (!uncompressed_size) { return 0; } uncompressed_pos = 0; + compressed_pos = 0; indic = 0; - *(uint32_t *)compressed = 0; - compressed_pos = sizeof(uint32_t); - indic_pos = &compressed[0]; + CHECK_OUTPUT_BYTES(sizeof(uint32_t)); + PUSH_LE_U32(compressed, compressed_pos, 0); + compressed_pos += sizeof(uint32_t); + indic_pos = 0; - byte_left = uncompressed_size; indic_bit = 0; nibble_index = 0; - if (uncompressed_pos > XPRESS_BLOCK_SIZE) - return 0; - - do { + while ((uncompressed_pos < uncompressed_size) && + (compressed_pos < max_compressed_size)) { bool found = false; - max_offset = uncompressed_pos; + uint32_t best_len = 2; + uint32_t best_offset = 0; - str1 = &uncompressed[uncompressed_pos]; + int32_t offset; - best_len = 2; - best_offset = 0; - - max_offset = MIN(0x1FFF, max_offset); + 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++) { - str2 = &str1[-offset]; - - /* maximum len we can encode into metadata */ - max_len = MIN((255 + 15 + 7 + 3), byte_left); + uint32_t len; - for (len = 0; (len < max_len) && (str1[len] == str2[len]); 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 @@ -124,111 +121,102 @@ ssize_t lzxpress_compress(const uint8_t *uncompressed, } } - if (found) { - metadata_size = 0; - dest = (uint16_t *)&compressed[compressed_pos]; - - if (best_len < 10) { - /* Classical meta-data */ - metadata = (uint16_t)(((best_offset - 1) << 3) | (best_len - 3)); - SSVAL(dest, metadata_size / sizeof(uint16_t), metadata); - metadata_size += sizeof(uint16_t); - } else { - metadata = (uint16_t)(((best_offset - 1) << 3) | 7); - SSVAL(dest, metadata_size / sizeof(uint16_t), metadata); - metadata_size = sizeof(uint16_t); - - if (best_len < (15 + 7 + 3)) { - /* Shared byte */ - if (!nibble_index) { - compressed[compressed_pos + metadata_size] = (best_len - (3 + 7)) & 0xF; - metadata_size += sizeof(uint8_t); - } else { - compressed[nibble_index] &= 0xF; - compressed[nibble_index] |= (best_len - (3 + 7)) * 16; - } - } else if (best_len < (3 + 7 + 15 + 255)) { - /* Shared byte */ - if (!nibble_index) { - compressed[compressed_pos + metadata_size] = 15; - metadata_size += sizeof(uint8_t); - } else { - compressed[nibble_index] &= 0xF; - compressed[nibble_index] |= (15 * 16); - } + if (!found) { + /* + * This is going to 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++]; - /* Additional best_len */ - compressed[compressed_pos + metadata_size] = (best_len - (3 + 7 + 15)) & 0xFF; - metadata_size += sizeof(uint8_t); - } else { - /* Shared byte */ - if (!nibble_index) { - compressed[compressed_pos + metadata_size] |= 15; - metadata_size += sizeof(uint8_t); - } else { - compressed[nibble_index] |= 15 << 4; - } + indic <<= 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); + } + } else { + uint32_t match_len = best_len; - /* Additional best_len */ - compressed[compressed_pos + metadata_size] = 255; + uint16_t metadata; - metadata_size += sizeof(uint8_t); + match_len -= 3; + best_offset -= 1; - compressed[compressed_pos + metadata_size] = (best_len - 3) & 0xFF; - compressed[compressed_pos + metadata_size + 1] = ((best_len - 3) >> 8) & 0xFF; - metadata_size += sizeof(uint16_t); - } - } + /* 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); - indic |= 1U << (32 - ((indic_bit % 32) + 1)); + if (match_len >= 7) { + match_len -= 7; - if (best_len > 9) { - if (nibble_index == 0) { - nibble_index = compressed_pos + sizeof(uint16_t); + 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); + } + } + } } - compressed_pos += metadata_size; - uncompressed_pos += best_len; - byte_left -= best_len; - } else { - compressed[compressed_pos++] = uncompressed[uncompressed_pos++]; - byte_left--; - } - indic_bit++; + indic = (indic << 1) | 1; + indic_bit += 1; - if ((indic_bit - 1) % 32 > (indic_bit % 32)) { - SIVAL(indic_pos, 0, indic); - indic = 0; - indic_pos = &compressed[compressed_pos]; - compressed_pos += sizeof(uint32_t); - } - } while (byte_left > 3); + 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); + } - do { - compressed[compressed_pos] = uncompressed[uncompressed_pos]; - indic_bit++; - - uncompressed_pos++; - compressed_pos++; - if (((indic_bit - 1) % 32) > (indic_bit % 32)){ - SIVAL(indic_pos, 0, indic); - indic = 0; - indic_pos = &compressed[compressed_pos]; - compressed_pos += sizeof(uint32_t); + uncompressed_pos += best_len; } - } while (uncompressed_pos < uncompressed_size); - - if ((indic_bit % 32) > 0) { - for (; (indic_bit % 32) != 0; indic_bit++) - indic |= 0 << (32 - ((indic_bit % 32) + 1)); + } - SIVAL(compressed, compressed_pos, 0); - SIVAL(indic_pos, 0, indic); - compressed_pos += sizeof(uint32_t); + if (indic_bit != 0) { + indic <<= 32 - indic_bit; } + indic |= UINT32_MAX >> indic_bit; + PUSH_LE_U32(compressed, indic_pos, indic); return compressed_pos; } @@ -238,40 +226,43 @@ ssize_t lzxpress_decompress(const uint8_t *input, uint8_t *output, uint32_t max_output_size) { + /* + * This is the algorithm in [MS-XCA] 2.4 "Plain LZ77 Decompression + * Algorithm Details". + */ uint32_t output_index, input_index; uint32_t indicator, indicator_bit; - uint32_t length; - uint32_t offset; uint32_t nibble_index; + if (input_size == 0) { + return 0; + } + output_index = 0; input_index = 0; indicator = 0; indicator_bit = 0; - length = 0; - offset = 0; nibble_index = 0; -#define __CHECK_BYTES(__size, __index, __needed) do { \ - if (unlikely(__index >= __size)) { \ - return -1; \ - } else { \ - uint32_t __avail = __size - __index; \ - if (unlikely(__needed > __avail)) { \ - return -1; \ - } \ - } \ -} while(0) +#undef CHECK_INPUT_BYTES #define CHECK_INPUT_BYTES(__needed) \ __CHECK_BYTES(input_size, input_index, __needed) +#undef CHECK_OUTPUT_BYTES #define CHECK_OUTPUT_BYTES(__needed) \ __CHECK_BYTES(max_output_size, output_index, __needed) do { if (indicator_bit == 0) { - CHECK_INPUT_BYTES(4); - indicator = PULL_LE_UINT32(input, input_index); + CHECK_INPUT_BYTES(sizeof(uint32_t)); + indicator = PULL_LE_U32(input, input_index); input_index += sizeof(uint32_t); + if (input_index == input_size) { + /* + * The compressor left room for indicator + * flags for data that doesn't exist. + */ + break; + } indicator_bit = 32; } indicator_bit--; @@ -282,60 +273,69 @@ ssize_t lzxpress_decompress(const uint8_t *input, * check whether the 4th bit of the value in indicator is set */ if (((indicator >> indicator_bit) & 1) == 0) { - CHECK_INPUT_BYTES(1); - CHECK_OUTPUT_BYTES(1); + CHECK_INPUT_BYTES(sizeof(uint8_t)); + CHECK_OUTPUT_BYTES(sizeof(uint8_t)); output[output_index] = input[input_index]; input_index += sizeof(uint8_t); output_index += sizeof(uint8_t); } else { - CHECK_INPUT_BYTES(2); - length = PULL_LE_UINT16(input, input_index); + uint32_t length; + uint32_t offset; + + CHECK_INPUT_BYTES(sizeof(uint16_t)); + length = PULL_LE_U16(input, input_index); input_index += sizeof(uint16_t); - offset = length / 8; - length = length % 8; + offset = (length >> 3) + 1; + length &= 7; if (length == 7) { if (nibble_index == 0) { - CHECK_INPUT_BYTES(1); + CHECK_INPUT_BYTES(sizeof(uint8_t)); nibble_index = input_index; - length = input[input_index] % 16; + length = input[input_index] & 0xf; input_index += sizeof(uint8_t); } else { - length = input[nibble_index] / 16; + length = input[nibble_index] >> 4; nibble_index = 0; } if (length == 15) { - CHECK_INPUT_BYTES(1); + CHECK_INPUT_BYTES(sizeof(uint8_t)); length = input[input_index]; input_index += sizeof(uint8_t); if (length == 255) { - CHECK_INPUT_BYTES(2); - length = PULL_LE_UINT16(input, input_index); + CHECK_INPUT_BYTES(sizeof(uint16_t)); + length = PULL_LE_U16(input, input_index); input_index += sizeof(uint16_t); + if (length == 0) { + CHECK_INPUT_BYTES(sizeof(uint32_t)); + length = PULL_LE_U32(input, input_index); + input_index += sizeof(uint32_t); + } + + if (length < (15 + 7)) { + return -1; + } length -= (15 + 7); } length += 15; } length += 7; } - length += 3; - if (length == 0) { - return -1; - } - if (offset >= output_index) { + if (length == 0) { return -1; } - CHECK_OUTPUT_BYTES(length); - - do { - output[output_index] = output[output_index - offset - 1]; + for (; length > 0; --length) { + if (offset > output_index) { + return -1; + } + CHECK_OUTPUT_BYTES(sizeof(uint8_t)); + output[output_index] = output[output_index - offset]; output_index += sizeof(uint8_t); - length -= sizeof(uint8_t); - } while (length != 0); + } } } while ((output_index < max_output_size) && (input_index < (input_size))); diff --git a/lib/compression/testsuite.c b/lib/compression/testsuite.c index e39ba0482a8..4de3700c727 100644 --- a/lib/compression/testsuite.c +++ b/lib/compression/testsuite.c @@ -1,19 +1,19 @@ -/* +/* Unix SMB/CIFS implementation. test suite for the compression functions Copyright (C) Jelmer Vernooij 2007 - + This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. - + This program 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 General Public License for more details. - -- Samba Shared Repository