[SCM] Samba Shared Repository - branch master updated
Andrew Bartlett
abartlet at samba.org
Thu May 12 03:19:01 UTC 2022
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 <abartlet at 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 <abartlet at samba.org>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Autobuild-User(master): Andrew Bartlett <abartlet at samba.org>
Autobuild-Date(master): Thu May 12 03:18:42 UTC 2022 on sn-devel-184
commit 8a91ffa6bd64746358faf8661649c33f683759ef
Author: Douglas Bagnall <douglas.bagnall at 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.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 6c9fd8fbdbecc47e0595d3606bccf7d143b01b61
Author: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed May 11 12:08:06 2022 +1200
fuzz: add fuzz_lzxpress_compress
Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 505d2879fa813796bf16af27615f0984bc71ad36
Author: Douglas Bagnall <douglas.bagnall at 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.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 05c760165bffa246b724d1471e307c488171b749
Author: Douglas Bagnall <douglas.bagnall at 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.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 383a7cfed9856b9057f2e56a1a26b8d4247ebbb6
Author: Douglas Bagnall <douglas.bagnall at 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.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit e36cb10b1629c1bf8d8c365c02bbe1e81cd75548
Author: Douglas Bagnall <douglas.bagnall at 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.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 1ca444929417a8c86108776bba0ad6be3e5efff1
Author: Douglas Bagnall <douglas.bagnall at 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.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit d8a90d2a8fc5f42859297c771bc83ec12f45a658
Author: Douglas Bagnall <douglas.bagnall at 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.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 075df819cce783d69069943f39bead833f3628ef
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit 877f007f32d2cee8944b747be988cc062d13d5c0
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit fe5fa7e19740896c21ab374cbf1f0f44a0412c94
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit 131eb7526996fc90eef2a5c2aae9ac15c2f258ff
Author: Joseph Sutton <josephsutton at catalyst.net.nz>
Date: Tue Mar 8 12:19:45 2022 +1300
compression: Remove unneeded loop variable
Signed-off-by: Joseph Sutton <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 5b1f8ea8d3ec4ee8b56cbf81e568ce7aea57b050
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 1a964210d243737d0f31ee93c546fc33566745b1
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 41b88d35ce6b120a1252093ea55ef80b7685e71e
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit 0c813ee56377c51bf4be786633b863f85a5f540e
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit 430bcd7a083a2dfbd12361f1ad352bc33e7963cb
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit bb9115e023bb304e19aac074294694170c31dc51
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit 417e0c914fdb64c58631e3dd862f704ce53dfeed
Author: Joseph Sutton <josephsutton at catalyst.net.nz>
Date: Mon Mar 7 20:31:33 2022 +1300
compression: Remove redundant bounds check
Signed-off-by: Joseph Sutton <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit 6f3f1ba5b4d45085a8aacc72f77b5a7d239a9cb2
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit b62fbc4a535a84167ee4ddff244e66536742a618
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit 52982c01a596284b00cd9d0a4addcb6b73eed9cd
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit f2ea8d4c056a20a42c4168c816b858fd6b433ed0
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit b153445798273b10751438c3a01e6d676ec6820d
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit ea42717ccae9be6872e698270d8bedcb61a1b420
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit 69244b52ed4faa047b4b4117da4d1f9c58ba11e7
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit 7fab9f90e8a90318b279b1d69656fd997a597665
Author: Joseph Sutton <josephsutton at 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 <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit f8feac11cbba9a955485b0c4b12f386e9ce6c385
Author: Joseph Sutton <josephsutton at catalyst.net.nz>
Date: Mon Mar 7 19:58:51 2022 +1300
compression: Simplify redundant branches
Signed-off-by: Joseph Sutton <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit d368fa61cfcd3bc4504db01d55b4e54b289e511e
Author: Joseph Sutton <josephsutton at catalyst.net.nz>
Date: Mon Mar 7 19:34:00 2022 +1300
compression: Consistently use PUSH_LE_Uxx macros
Signed-off-by: Joseph Sutton <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 9516b268458dc2afd8e802c7c646aa565f84ffc3
Author: Joseph Sutton <josephsutton at catalyst.net.nz>
Date: Mon Mar 7 19:30:43 2022 +1300
compression: Use explicit data sizes
Signed-off-by: Joseph Sutton <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit eb7f139dec08dec578c2ce20c418287c2834198d
Author: Joseph Sutton <josephsutton at catalyst.net.nz>
Date: Tue Mar 8 10:38:09 2022 +1300
compression tests: Add additional compression tests
Signed-off-by: Joseph Sutton <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 3c2f1f03c1937b180d539ad9bb96540ce1dd957b
Author: Matt Suiche <msuiche at comae.com>
Date: Tue Mar 23 20:33:34 2021 +0400
compression: fix lzxpress-compress
Signed-off-by: Matt Suiche <msuiche at comae.com>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit 8f7fbc5c8fd0fba8542f6080908eeaa1c2d479b8
Author: Matt Suiche <msuiche at 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 <msuiche at comae.com>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit a8fb45247baf9af8e3f2223e5a384fac4351dbc3
Author: Matt Suiche <msuiche at comae.com>
Date: Tue Jun 15 11:52:37 2021 +1200
compression: fix lzxpress_decompress
Signed-off-by: Matt Suiche <msuiche at comae.com>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
commit f67ff611e96b2d229a8e8d0e8b13b89916c5f27d
Author: Matt Suiche <msuiche at comae.com>
Date: Thu Mar 25 16:50:42 2021 +0400
compression tests: add test for legacy compressed data
Signed-off-by: Matt Suiche <msuiche at comae.com>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit 4bcdc3bf30a0a2548a8bbf216ad960cc7d55eaae
Author: Matt Suiche <msuiche at 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 <msuiche at comae.com>
Reviewed-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at samba.org>
commit eddefe3c62a537ed0b94d3d5f4ab58ae10d00828
Author: Douglas Bagnall <douglas.bagnall at 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.bagnall at catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton at catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet at 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
More information about the samba-cvs
mailing list