Improving LZXpress decompression/compression algorithms
Matt Suiche
msuiche at comae.com
Thu Apr 1 08:13:27 UTC 2021
First of all, thanks a lot to Douglas Bagnall for the assistance.
While I was revisiting the LZXpress implementation, I discovered that the 2
official documented cases from MS-XCA were not supported:
https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-xca/72da4f8d-2ba3-437d-b772-2e4173713a0b?redirectedfrom=MSDN
The attached implementation includes bug fixes in the decompression
algorithm, a rewrite of the compression function and additional tests as it
only had a single test.
Thanks,
--
*Matt Suiche *
Founder, Comae
-------------- next part --------------
From 66ae18504bac8c26f26a8834a5e85bb557eabfe0 Mon Sep 17 00:00:00 2001
From: Matt Suiche <msuiche at comae.com>
Date: Tue, 23 Mar 2021 20:33:34 +0400
Subject: [PATCH 1/2] Improve LZXpress compression
---
lib/compression/lzxpress.c | 227 ++++++++++++++++++++----------------
lib/compression/testsuite.c | 103 +++++++++++++++-
2 files changed, 224 insertions(+), 106 deletions(-)
diff --git a/lib/compression/lzxpress.c b/lib/compression/lzxpress.c
index 3453dd36f2a..b827593770b 100644
--- a/lib/compression/lzxpress.c
+++ b/lib/compression/lzxpress.c
@@ -57,6 +57,17 @@
))
#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)
+
ssize_t lzxpress_compress(const uint8_t *uncompressed,
uint32_t uncompressed_size,
uint8_t *compressed,
@@ -65,7 +76,7 @@ ssize_t lzxpress_compress(const uint8_t *uncompressed,
uint32_t uncompressed_pos, compressed_pos, byte_left;
uint32_t max_offset, best_offset;
int32_t offset;
- uint32_t max_len, len, best_len;
+ uint32_t max_len, len, best_len, match_len;
const uint8_t *str1, *str2;
uint32_t indic;
uint8_t *indic_pos;
@@ -92,7 +103,8 @@ ssize_t lzxpress_compress(const uint8_t *uncompressed,
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;
@@ -109,7 +121,7 @@ ssize_t lzxpress_compress(const uint8_t *uncompressed,
str2 = &str1[-offset];
/* maximum len we can encode into metadata */
- max_len = MIN((255 + 15 + 7 + 3), byte_left);
+ max_len = MIN(0x1FFF, byte_left);
for (len = 0; (len < max_len) && (str1[len] == str2[len]); len++);
@@ -124,112 +136,129 @@ ssize_t lzxpress_compress(const uint8_t *uncompressed,
}
}
- if (found) {
+ if (!found) {
+ __CHECK_BYTES(uncompressed_size, uncompressed_pos, sizeof(uint8_t));
+ __CHECK_BYTES(max_compressed_size, compressed_pos, sizeof(uint8_t));
+ compressed[compressed_pos++] = uncompressed[uncompressed_pos++];
+ byte_left--;
+
+ indic <<= 1;
+ indic_bit += 1;
+
+ if (indic_bit == 32) {
+ SIVAL(indic_pos, 0, indic);
+ indic_bit = 0;
+ __CHECK_BYTES(max_compressed_size, compressed_pos, sizeof(uint32_t));
+ indic_pos = &compressed[compressed_pos];
+ compressed_pos += sizeof(uint32_t);
+ }
+ } else {
metadata_size = 0;
+ match_len = best_len;
+ __CHECK_BYTES(max_compressed_size, compressed_pos, sizeof(uint16_t));
dest = (uint16_t *)&compressed[compressed_pos];
- if (best_len < 10) {
+ match_len -= 3;
+ best_offset -= 1;
+
+ if (match_len < 7) {
/* Classical meta-data */
- metadata = (uint16_t)(((best_offset - 1) << 3) | (best_len - 3));
+ __CHECK_BYTES(max_compressed_size, compressed_pos, sizeof(uint16_t));
+ metadata = (uint16_t)((best_offset << 3) + match_len);
SSVAL(dest, metadata_size / sizeof(uint16_t), metadata);
metadata_size += sizeof(uint16_t);
} else {
- metadata = (uint16_t)(((best_offset - 1) << 3) | 7);
+ bool has_extra = false;
+ __CHECK_BYTES(max_compressed_size, compressed_pos, sizeof(uint16_t));
+ metadata = (uint16_t)(best_offset << 3) | 7;
SSVAL(dest, metadata_size / sizeof(uint16_t), metadata);
- metadata_size = sizeof(uint16_t);
+ 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;
+ match_len -= 7;
+
+ if (!nibble_index) {
+ nibble_index = compressed_pos;
+ if (match_len < 15) {
+ __CHECK_BYTES(max_compressed_size, compressed_pos + metadata_size, sizeof(uint8_t));
+ compressed[compressed_pos + metadata_size] = match_len & 0xFF;;
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) {
+ __CHECK_BYTES(max_compressed_size, compressed_pos + metadata_size, sizeof(uint8_t));
compressed[compressed_pos + metadata_size] = 15;
metadata_size += sizeof(uint8_t);
- } else {
- compressed[nibble_index] &= 0xF;
- compressed[nibble_index] |= (15 * 16);
+ has_extra = true;
}
-
- /* 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);
+ if (match_len < 15) {
+ // compressed[nibble_index] &= 0xF;
+ __CHECK_BYTES(max_compressed_size, nibble_index, sizeof(uint8_t));
+ compressed[nibble_index] |= (match_len << 4) & 0xFF;
+ nibble_index = 0;
} else {
- compressed[nibble_index] |= 15 << 4;
+ __CHECK_BYTES(max_compressed_size, nibble_index, sizeof(uint8_t));
+ compressed[nibble_index] |= (15 << 4);
+ nibble_index = 0;
+ has_extra = true;
}
+ }
- /* Additional best_len */
- compressed[compressed_pos + metadata_size] = 255;
+ if (has_extra) {
+ match_len -= 15;
- metadata_size += sizeof(uint8_t);
+ if (match_len < 255) {
+ __CHECK_BYTES(max_compressed_size, compressed_pos + metadata_size, sizeof(uint8_t));
+ compressed[compressed_pos + metadata_size] = match_len & 0xFF;
+ metadata_size += sizeof(uint8_t);
+ } else {
+ /* Additional match_len */
+ __CHECK_BYTES(max_compressed_size, compressed_pos + metadata_size, sizeof(uint8_t));
+ compressed[compressed_pos + metadata_size] = 255;
+ metadata_size += sizeof(uint8_t);
- 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);
+ match_len += 7 + 15;
+
+ if (match_len < (1 << 16)) {
+ __CHECK_BYTES(max_compressed_size, compressed_pos + metadata_size, sizeof(uint16_t));
+ compressed[compressed_pos + metadata_size] = match_len & 0xFF;
+ compressed[compressed_pos + metadata_size + 1] = (match_len >> 8);
+ metadata_size += sizeof(uint16_t);
+ } else {
+ __CHECK_BYTES(max_compressed_size, compressed_pos + metadata_size, sizeof(uint16_t) + sizeof(uint32_t));
+ compressed[compressed_pos + metadata_size] = 0;
+ compressed[compressed_pos + metadata_size + 1] = 0;
+ metadata_size += sizeof(uint16_t);
+
+ compressed[compressed_pos + metadata_size] = match_len & 0xFF;
+ compressed[compressed_pos + metadata_size + 1] = (match_len >> 8) & 0xFF;
+ compressed[compressed_pos + metadata_size + 2] = (match_len >> 16) & 0xFF;
+ compressed[compressed_pos + metadata_size + 3] = (match_len >> 24) & 0xFF;
+ metadata_size += sizeof(uint32_t);
+ }
+ }
}
}
- indic |= 1U << (32 - ((indic_bit % 32) + 1));
+ indic = (indic << 1) | 1;
+ indic_bit += 1;
- if (best_len > 9) {
- if (nibble_index == 0) {
- nibble_index = compressed_pos + sizeof(uint16_t);
- } else {
- nibble_index = 0;
- }
+ if (indic_bit == 32) {
+ SIVAL(indic_pos, 0, indic);
+ indic_bit = 0;
+ indic_pos = &compressed[compressed_pos];
+ 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++;
-
- 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);
-
- 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);
}
- } 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);
}
+ indic <<= 32 - indic_bit;
+ indic |= (1 << (32 - indic_bit)) - 1;
+ SIVAL(indic_pos, 0, indic);
+ // compressed_pos += sizeof(uint32_t);
+
return compressed_pos;
}
@@ -252,16 +281,6 @@ ssize_t lzxpress_decompress(const uint8_t *input,
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)
#define CHECK_INPUT_BYTES(__needed) \
__CHECK_BYTES(input_size, input_index, __needed)
#define CHECK_OUTPUT_BYTES(__needed) \
@@ -281,7 +300,7 @@ ssize_t lzxpress_decompress(const uint8_t *input,
* set in indicator. For example, if indicator_bit has value 4
* check whether the 4th bit of the value in indicator is set
*/
- if (((indicator >> indicator_bit) & 1) == 0) {
+ if ((indicator & (1 << indicator_bit)) == 0) {
CHECK_INPUT_BYTES(1);
CHECK_OUTPUT_BYTES(1);
output[output_index] = input[input_index];
@@ -291,7 +310,7 @@ ssize_t lzxpress_decompress(const uint8_t *input,
CHECK_INPUT_BYTES(2);
length = PULL_LE_UINT16(input, input_index);
input_index += sizeof(uint16_t);
- offset = length / 8;
+ offset = (length / 8) + 1;
length = length % 8;
if (length == 7) {
@@ -313,31 +332,37 @@ ssize_t lzxpress_decompress(const uint8_t *input,
CHECK_INPUT_BYTES(2);
length = PULL_LE_UINT16(input, input_index);
input_index += sizeof(uint16_t);
+ if (length == 0) {
+ CHECK_INPUT_BYTES(4);
+ length = PULL_LE_UINT32(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 (int i = 0; i < length; i++) {
+ if (offset > output_index) {
+ return -1;
+ }
+ CHECK_OUTPUT_BYTES(1);
+ 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)));
+ } while ((output_index < max_output_size) && (input_index < input_size));
return output_index;
}
diff --git a/lib/compression/testsuite.c b/lib/compression/testsuite.c
index e39ba0482a8..dc0fd161db9 100644
--- a/lib/compression/testsuite.c
+++ b/lib/compression/testsuite.c
@@ -24,6 +24,95 @@
#include "talloc.h"
#include "lzxpress.h"
+// Examples: https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-xca/72da4f8d-2ba3-437d-b772-2e4173713a0b?redirectedfrom=MSDN
+static bool test_msft_data1(
+ struct torture_context *test
+)
+{
+ TALLOC_CTX *tmp_ctx = talloc_new(test);
+
+ const char *fixed_data = "abcdefghijklmnopqrstuvwxyz";
+ const uint8_t fixed_out[] = {
+ 0x3f, 0x00, 0x00, 0x00, 0x61, 0x62, 0x63, 0x64,
+ 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c,
+ 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74,
+ 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a };
+
+ ssize_t c_size;
+ uint8_t *out, *out2;
+
+ out = talloc_size(tmp_ctx, 2048);
+ memset(out, 0x42, talloc_get_size(out));
+
+ torture_comment(test, "lzxpress fixed compression\n");
+ c_size = lzxpress_compress((const uint8_t *)fixed_data,
+ strlen(fixed_data),
+ out,
+ talloc_get_size(out));
+
+ torture_assert_int_equal(test, c_size, sizeof(fixed_out), "fixed lzxpress_compress size");
+ torture_assert_mem_equal(test, out, fixed_out, c_size, "fixed lzxpress_compress data");
+
+ torture_comment(test, "lzxpress fixed decompression\n");
+ out2 = talloc_size(tmp_ctx, strlen(fixed_data));
+ c_size = lzxpress_decompress(out,
+ sizeof(fixed_out),
+ out2,
+ talloc_get_size(out2));
+
+ torture_assert_int_equal(test, c_size, strlen(fixed_data), "fixed lzxpress_decompress size");
+ torture_assert_mem_equal(test, out2, fixed_data, c_size, "fixed lzxpress_decompress data");
+
+ return true;
+}
+
+
+static bool test_msft_data2(
+ struct torture_context *test
+)
+{
+ TALLOC_CTX *tmp_ctx = talloc_new(test);
+
+ const char *fixed_data = "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc"
+ "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc"
+ "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc"
+ "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc"
+ "abcabcabcabcabcabcabcabc";
+ const uint8_t fixed_out[] = {
+ 0xff, 0xff, 0xff, 0x1f, 0x61, 0x62, 0x63, 0x17,
+ 0x00, 0x0f, 0xff, 0x26, 0x01};
+
+ ssize_t c_size;
+ uint8_t *out, *out2;
+
+ out = talloc_size(tmp_ctx, 2048);
+ memset(out, 0x42, talloc_get_size(out));
+
+ torture_comment(test, "lzxpress fixed compression\n");
+ c_size = lzxpress_compress((const uint8_t *)fixed_data,
+ strlen(fixed_data),
+ out,
+ talloc_get_size(out));
+
+ torture_assert_int_equal(test, c_size, sizeof(fixed_out), "fixed lzxpress_compress size");
+ torture_assert_mem_equal(test, out, fixed_out, c_size, "fixed lzxpress_compress data");
+
+ torture_comment(test, "lzxpress fixed decompression\n");
+ out2 = talloc_size(tmp_ctx, strlen(fixed_data));
+ c_size = lzxpress_decompress(out,
+ sizeof(fixed_out),
+ out2,
+ talloc_get_size(out2));
+
+ torture_comment(test, "out2: %s\n", (char *)out2);
+
+ torture_assert_int_equal(test, c_size, strlen(fixed_data), "fixed lzxpress_decompress size");
+ torture_assert_mem_equal(test, out2, fixed_data, c_size, "fixed lzxpress_decompress data");
+
+
+ return true;
+}
+
/*
test lzxpress
*/
@@ -31,11 +120,10 @@ static bool test_lzxpress(struct torture_context *test)
{
TALLOC_CTX *tmp_ctx = talloc_new(test);
const char *fixed_data = "this is a test. and this is a test too";
- const uint8_t fixed_out[] = { 0x00, 0x20, 0x00, 0x04, 0x74, 0x68, 0x69, 0x73,
- 0x20, 0x10, 0x00, 0x61, 0x20, 0x74, 0x65, 0x73,
- 0x74, 0x2E, 0x20, 0x61, 0x6E, 0x64, 0x20, 0x9F,
- 0x00, 0x04, 0x20, 0x74, 0x6F, 0x6F, 0x00, 0x00,
- 0x00, 0x00 };
+ const uint8_t fixed_out[] = { 0xff, 0x21, 0x00, 0x04, 0x74, 0x68, 0x69, 0x73,
+ 0x20, 0x10, 0x00, 0x61, 0x20, 0x74, 0x65, 0x73,
+ 0x74, 0x2E, 0x20, 0x61, 0x6E, 0x64, 0x20, 0x9F,
+ 0x00, 0x04, 0x20, 0x74, 0x6F, 0x6F };
ssize_t c_size;
uint8_t *out, *out2;
@@ -49,6 +137,9 @@ static bool test_lzxpress(struct torture_context *test)
talloc_get_size(out));
torture_assert_int_equal(test, c_size, sizeof(fixed_out), "fixed lzxpress_compress size");
+ for (int i = 0; i < c_size; i++) {
+ torture_comment(test, "0x%x ", out[i]);
+ }
torture_assert_mem_equal(test, out, fixed_out, c_size, "fixed lzxpress_compress data");
torture_comment(test, "lzxpress fixed decompression\n");
@@ -70,6 +161,8 @@ struct torture_suite *torture_local_compression(TALLOC_CTX *mem_ctx)
struct torture_suite *suite = torture_suite_create(mem_ctx, "compression");
torture_suite_add_simple_test(suite, "lzxpress", test_lzxpress);
+ torture_suite_add_simple_test(suite, "lzxpress2", test_msft_data1);
+ torture_suite_add_simple_test(suite, "lzxpress3", test_msft_data2);
return suite;
}
--
2.31.0.windows.1
From e6d7d4b13377d31a33e1422b4432be5201de605a Mon Sep 17 00:00:00 2001
From: Matt Suiche <msuiche at comae.com>
Date: Thu, 25 Mar 2021 16:50:42 +0400
Subject: [PATCH 2/2] - Add test for legacy compressed data
Signed-off-by: Matt Suiche <msuiche at comae.com>
---
lib/compression/testsuite.c | 20 +++++++++++++++++++-
1 file changed, 19 insertions(+), 1 deletion(-)
diff --git a/lib/compression/testsuite.c b/lib/compression/testsuite.c
index dc0fd161db9..1f6ca8e3e3c 100644
--- a/lib/compression/testsuite.c
+++ b/lib/compression/testsuite.c
@@ -124,8 +124,15 @@ static bool test_lzxpress(struct torture_context *test)
0x20, 0x10, 0x00, 0x61, 0x20, 0x74, 0x65, 0x73,
0x74, 0x2E, 0x20, 0x61, 0x6E, 0x64, 0x20, 0x9F,
0x00, 0x04, 0x20, 0x74, 0x6F, 0x6F };
+
+ const uint8_t fixed_out_old_version[] = { 0x00, 0x20, 0x00, 0x04, 0x74, 0x68, 0x69, 0x73,
+ 0x20, 0x10, 0x00, 0x61, 0x20, 0x74, 0x65, 0x73,
+ 0x74, 0x2E, 0x20, 0x61, 0x6E, 0x64, 0x20, 0x9F,
+ 0x00, 0x04, 0x20, 0x74, 0x6F, 0x6F, 0x00, 0x00,
+ 0x00, 0x00 };
+
ssize_t c_size;
- uint8_t *out, *out2;
+ uint8_t *out, *out2, *out3;
out = talloc_size(tmp_ctx, 2048);
memset(out, 0x42, talloc_get_size(out));
@@ -152,6 +159,17 @@ static bool test_lzxpress(struct torture_context *test)
torture_assert_int_equal(test, c_size, strlen(fixed_data), "fixed lzxpress_decompress size");
torture_assert_mem_equal(test, out2, fixed_data, c_size, "fixed lzxpress_decompress data");
+
+ torture_comment(test, "lzxpress fixed decompression (old data)\n");
+ out3 = talloc_size(tmp_ctx, strlen(fixed_data));
+ c_size = lzxpress_decompress(fixed_out_old_version,
+ sizeof(fixed_out_old_version),
+ out3,
+ talloc_get_size(out3));
+
+ torture_assert_int_equal(test, c_size, strlen(fixed_data), "fixed lzxpress_decompress size");
+ torture_assert_mem_equal(test, out3, fixed_data, c_size, "fixed lzxpress_decompress data");
+
return true;
}
--
2.31.0.windows.1
More information about the samba-technical
mailing list