/* 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. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #include #include #include #include #include #include "includes.h" #include "talloc.h" #include "lzxpress.h" #include "lib/util/base64.h" /* set LZX_DEBUG_FILES to true to save round-trip files in /tmp. */ #define LZX_DEBUG_FILES false /* set LZX_DEBUG_VERBOSE to true to print more. */ #define LZX_DEBUG_VERBOSE false #if LZX_DEBUG_VERBOSE #define debug_message(...) print_message(__VA_ARGS__) #include struct timespec start = {0}; struct timespec end = {0}; static void debug_start_timer(void) { clock_gettime(CLOCK_MONOTONIC, &start); } static void debug_end_timer(const char *name, size_t len) { uint64_t ns; double secs; double rate; clock_gettime(CLOCK_MONOTONIC, &end); ns = end.tv_nsec; ns += end.tv_sec * 1000 * 1000 * 1000; ns -= start.tv_nsec; ns -= start.tv_sec * 1000 * 1000 * 1000; secs = ns / 1e9; rate = len / (secs * 1024 * 1024); debug_message("%s %zu bytes in %.2g: \033[1;35m%.2f\033[0m MB per second\n", name, len, secs, rate); } #else #define debug_message(...) /* debug_message */ #define debug_start_timer(...) /* debug_start_timer */ #define debug_end_timer(...) /* debug_end_timer */ #endif struct lzx_pair { const char *name; DATA_BLOB compressed; DATA_BLOB decompressed; }; struct lzx_file_pair { const char *name; const char *compressed_file; const char *decompressed_file; }; #define DECOMP_DIR "testdata/compression/decompressed" #define COMP_DIR "testdata/compression/compressed-plain" #define MORE_COMP_DIR "testdata/compression/compressed-more-plain" #define BLOB_FROM_ARRAY(...) \ { \ .data = (uint8_t[]){__VA_ARGS__}, \ .length = sizeof((uint8_t[]){__VA_ARGS__}) \ } #define BLOB_FROM_STRING(s) \ { \ .data = discard_const_p(uint8_t, s), \ .length = (sizeof(s) - 1) \ } const char * file_names[] = { "generate-windows-test-vectors.c", "fib_shuffle-128k+", "fuzzing-0fc2d461b56cd8103c91", "fuzzing-3ec3bca27bb9eb40c128", "fuzzing-a3115a81d1ac500318f9", "fuzzing-3591f9dc02bb00a54b60", "27826-8.txt", "5d049b4cb1bd933f5e8ex19", "638e61e96d54279981c3x5", "64k-minus-one-zeros", "64k-plus-one-zeros", "64k-zeros", "96f696a4e5ce56c61a3dx10", "9e0b6a12febf38e98f13", "abc-times-101", "abc-times-105", "abc-times-200", "b63289ccc7f218c0d56b", "beta-variate1-128k+", "beta-variate3-128k+", "decayed_alphabet_128k+", "decayed_alphabet_64k", "f00842317dc6d5695b02", "fib_shuffle", "midsummer-nights-dream.txt", "notes-on-the-underground.txt", "pg22009.txt", "repeating", "repeating-exactly-64k", "setup.log", "slow-015ddc36a71412ccc50d", "slow-100e9f966a7feb9ca40a", "slow-2a671c3cff4f1574cbab", "slow-33d90a24e70515b14cd0", "slow-49d8c05261e3f412fc72", "slow-50a249d2fe56873e56a0", "slow-63e9f0b52235fb0129fa", "slow-73b7f971d65908ac0095", "slow-8b61e3dd267908544531", "slow-9d1c5a079b0462986f1f", "slow-aa7262a821dabdcf04a6", "slow-b8a91d142b0d2af7f5ca", "slow-c79142457734bbc8d575", "slow-d736544545b90d83fe75", "slow-e3b9bdfaed7d1a606fdb", "slow-f3f1c02a9d006e5e1703", "trigram_128k+", "trigram_64k", "trigram_sum_128k+", "trigram_sum_64k", NULL }; static DATA_BLOB datablob_from_file(TALLOC_CTX *mem_ctx, const char *filename) { DATA_BLOB b = {0}; FILE *fh = fopen(filename, "rb"); int ret; struct stat s; size_t len; if (fh == NULL) { debug_message("could not open '%s'\n", filename); return b; } ret = fstat(fileno(fh), &s); if (ret != 0) { fclose(fh); return b; } b.data = talloc_array(mem_ctx, uint8_t, s.st_size); if (b.data == NULL) { fclose(fh); return b; } len = fread(b.data, 1, s.st_size, fh); if (ferror(fh) || len != s.st_size) { TALLOC_FREE(b.data); } else { b.length = len; } fclose(fh); return b; } static void test_lzxpress_plain_decompress_files(void **state) { size_t i; int score = 0; TALLOC_CTX *mem_ctx = talloc_new(NULL); for (i = 0; file_names[i] != NULL; i++) { char filename[200]; uint8_t *dest = NULL; ssize_t written; TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx); struct lzx_pair p = { .name = file_names[i] }; debug_message("%s\n", p.name); snprintf(filename, sizeof(filename), "%s/%s.decomp", DECOMP_DIR, p.name); p.decompressed = datablob_from_file(tmp_ctx, filename); assert_non_null(p.decompressed.data); snprintf(filename, sizeof(filename), "%s/%s.lzplain", COMP_DIR, p.name); p.compressed = datablob_from_file(tmp_ctx, filename); assert_non_null(p.compressed.data); dest = talloc_array(tmp_ctx, uint8_t, p.decompressed.length); debug_start_timer(); written = lzxpress_decompress(p.compressed.data, p.compressed.length, dest, p.decompressed.length); debug_end_timer("decompress", p.decompressed.length); if (written == p.decompressed.length && memcmp(dest, p.decompressed.data, p.decompressed.length) == 0) { debug_message("\033[1;32mdecompressed %s!\033[0m\n", p.name); score++; } else { debug_message("\033[1;31mfailed to decompress %s!\033[0m\n", p.name); debug_message("size %zd vs reference %zu\n", written, p.decompressed.length); } talloc_free(tmp_ctx); } debug_message("%d/%zu correct\n", score, i); assert_int_equal(score, i); } static void test_lzxpress_plain_decompress_more_compressed_files(void **state) { /* * This tests the decompression of files that have been compressed on * Windows with the level turned up (to 1, default for MS-XCA is 0). * * The format is identical, but it will have tried harder to find * matches. */ size_t i; int score = 0; int found = 0; TALLOC_CTX *mem_ctx = talloc_new(NULL); for (i = 0; file_names[i] != NULL; i++) { char filename[200]; uint8_t *dest = NULL; ssize_t written; TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx); struct lzx_pair p = { .name = file_names[i] }; debug_message("%s\n", p.name); snprintf(filename, sizeof(filename), "%s/%s.decomp", DECOMP_DIR, p.name); p.decompressed = datablob_from_file(tmp_ctx, filename); assert_non_null(p.decompressed.data); snprintf(filename, sizeof(filename), "%s/%s.lzplain", MORE_COMP_DIR, p.name); p.compressed = datablob_from_file(tmp_ctx, filename); if (p.compressed.data == NULL) { /* * We don't have all the vectors in the * more-compressed directory, which is OK, we skip * them. */ continue; } found++; dest = talloc_array(tmp_ctx, uint8_t, p.decompressed.length); debug_start_timer(); written = lzxpress_decompress(p.compressed.data, p.compressed.length, dest, p.decompressed.length); debug_end_timer("decompress", p.decompressed.length); if (written != -1 && written == p.decompressed.length && memcmp(dest, p.decompressed.data, p.decompressed.length) == 0) { debug_message("\033[1;32mdecompressed %s!\033[0m\n", p.name); score++; } else { debug_message("\033[1;31mfailed to decompress %s!\033[0m\n", p.name); debug_message("size %zd vs reference %zu\n", written, p.decompressed.length); } talloc_free(tmp_ctx); } debug_message("%d/%d correct\n", score, found); assert_int_equal(score, found); } /* * attempt_round_trip() tests whether a data blob can survive a compression * and decompression cycle. If save_name is not NULL and LZX_DEBUG_FILES * evals to true, the various stages are saved in files with that name and the * '-original', '-compressed', and '-decompressed' suffixes. If ref_compressed * has data, it'll print a message saying whether the compressed data matches * that. */ static ssize_t attempt_round_trip(TALLOC_CTX *mem_ctx, DATA_BLOB original, const char *save_name, DATA_BLOB ref_compressed) { TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx); DATA_BLOB compressed = data_blob_talloc(tmp_ctx, NULL, original.length * 8 / 7 + 8); DATA_BLOB decompressed = data_blob_talloc(tmp_ctx, NULL, original.length); ssize_t comp_written, decomp_written; debug_start_timer(); comp_written = lzxpress_compress(original.data, original.length, compressed.data, compressed.length); debug_end_timer("compress", original.length); if (comp_written <= 0) { talloc_free(tmp_ctx); return -1; } if (ref_compressed.data != NULL) { /* * This is informational, not an assertion; there are * ~infinite legitimate ways to compress the data, many as * good as each other (think of compression as a language, not * a format). */ debug_message("compressed size %zd vs reference %zu\n", comp_written, ref_compressed.length); if (comp_written == compressed.length && memcmp(compressed.data, ref_compressed.data, comp_written) == 0) { debug_message("\033[1;32mbyte identical!\033[0m\n"); } } debug_start_timer(); decomp_written = lzxpress_decompress(compressed.data, comp_written, decompressed.data, decompressed.length); debug_end_timer("decompress", original.length); if (save_name != NULL && LZX_DEBUG_FILES) { char s[300]; FILE *fh = NULL; snprintf(s, sizeof(s), "%s-original", save_name); fprintf(stderr, "Saving %zu bytes to %s\n", original.length, s); fh = fopen(s, "w"); fwrite(original.data, 1, original.length, fh); fclose(fh); snprintf(s, sizeof(s), "%s-compressed", save_name); fprintf(stderr, "Saving %zu bytes to %s\n", comp_written, s); fh = fopen(s, "w"); fwrite(compressed.data, 1, comp_written, fh); fclose(fh); /* * We save the decompressed file using original.length, not * the returned size. If these differ, the returned size will * be -1. By saving the whole buffer we can see at what point * it went haywire. */ snprintf(s, sizeof(s), "%s-decompressed", save_name); fprintf(stderr, "Saving %zu bytes to %s\n", original.length, s); fh = fopen(s, "w"); fwrite(decompressed.data, 1, original.length, fh); fclose(fh); } if (original.length != decomp_written || memcmp(decompressed.data, original.data, original.length) != 0) { debug_message("\033[1;31mgot %zd, expected %zu\033[0m\n", decomp_written, original.length); talloc_free(tmp_ctx); return -1; } talloc_free(tmp_ctx); return comp_written; } static void test_lzxpress_plain_round_trip_files(void **state) { size_t i; int score = 0; ssize_t compressed_total = 0; ssize_t reference_total = 0; TALLOC_CTX *mem_ctx = talloc_new(NULL); for (i = 0; file_names[i] != NULL; i++) { char filename[200]; char *debug_files = NULL; TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx); ssize_t comp_size; struct lzx_pair p = { .name = file_names[i] }; debug_message("-------------------\n"); debug_message("%s\n", p.name); snprintf(filename, sizeof(filename), "%s/%s.decomp", DECOMP_DIR, p.name); p.decompressed = datablob_from_file(tmp_ctx, filename); assert_non_null(p.decompressed.data); snprintf(filename, sizeof(filename), "%s/%s.lzplain", COMP_DIR, p.name); p.compressed = datablob_from_file(tmp_ctx, filename); if (p.compressed.data == NULL) { debug_message( "Could not load %s reference file %s\n", p.name, filename); debug_message("%s decompressed %zu\n", p.name, p.decompressed.length); } else { debug_message("%s: reference compressed %zu decomp %zu\n", p.name, p.compressed.length, p.decompressed.length); } if (1) { /* * We're going to save copies in /tmp. */ snprintf(filename, sizeof(filename), "/tmp/lzxplain-%s", p.name); debug_files = filename; } comp_size = attempt_round_trip(mem_ctx, p.decompressed, debug_files, p.compressed); if (comp_size > 0) { debug_message("\033[1;32mround trip!\033[0m\n"); score++; if (p.compressed.length) { compressed_total += comp_size; reference_total += p.compressed.length; } } talloc_free(tmp_ctx); } debug_message("%d/%zu correct\n", score, i); print_message("\033[1;34mtotal compressed size: %zu\033[0m\n", compressed_total); print_message("total reference size: %zd \n", reference_total); print_message("diff: %7zd \n", reference_total - compressed_total); assert_true(reference_total != 0); print_message("ratio: \033[1;3%dm%.2f\033[0m \n", 2 + (compressed_total >= reference_total), ((double)compressed_total) / reference_total); /* * Assert that the compression is better than Windows. Unlike the * Huffman variant, where things are very even, here we do much better * than Windows without especially trying. */ assert_true(compressed_total <= reference_total); assert_int_equal(score, i); talloc_free(mem_ctx); } /* * Bob Jenkins' Small Fast RNG. * * We don't need it to be this good, but we do need it to be reproduceable * across platforms, which rand() etc aren't. * * http://burtleburtle.net/bob/rand/smallprng.html */ struct jsf_rng { uint32_t a; uint32_t b; uint32_t c; uint32_t d; }; #define ROTATE32(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) static uint32_t jsf32(struct jsf_rng *x) { uint32_t e = x->a - ROTATE32(x->b, 27); x->a = x->b ^ ROTATE32(x->c, 17); x->b = x->c + x->d; x->c = x->d + e; x->d = e + x->a; return x->d; } static void jsf32_init(struct jsf_rng *x, uint32_t seed) { size_t i; x->a = 0xf1ea5eed; x->b = x->c = x->d = seed; for (i = 0; i < 20; ++i) { jsf32(x); } } static void test_lzxpress_plain_long_gpl_round_trip(void **state) { /* * We use a kind of model-free Markov model to generate a massively * extended pastiche of the GPLv3 (chosen because it is right there in * "COPYING" and won't change often). * * The point is to check a round trip of a very long message with * multiple repetitions on many scales, without having to add a very * large file. */ size_t i, j, k; uint8_t c; TALLOC_CTX *mem_ctx = talloc_new(NULL); DATA_BLOB gpl = datablob_from_file(mem_ctx, "COPYING"); DATA_BLOB original = data_blob_talloc(mem_ctx, NULL, 5 * 1024 * 1024); DATA_BLOB ref = {0}; ssize_t comp_size; struct jsf_rng rng; jsf32_init(&rng, 1); j = 1; original.data[0] = gpl.data[0]; for (i = 1; i < original.length; i++) { size_t m; char p = original.data[i - 1]; c = gpl.data[j]; original.data[i] = c; j++; m = (j + jsf32(&rng)) % (gpl.length - 50); for (k = m; k < m + 30; k++) { if (p == gpl.data[k] && c == gpl.data[k + 1]) { j = k + 2; break; } } if (j == gpl.length) { j = 1; } } comp_size = attempt_round_trip(mem_ctx, original, "/tmp/gpl", ref); assert_true(comp_size > 0); assert_true(comp_size < original.length); talloc_free(mem_ctx); } static void test_lzxpress_plain_long_random_graph_round_trip(void **state) { size_t i; TALLOC_CTX *mem_ctx = talloc_new(NULL); DATA_BLOB original = data_blob_talloc(mem_ctx, NULL, 5 * 1024 * 1024); DATA_BLOB ref = {0}; /* * There's a random trigram graph, with each pair of sequential bytes * pointing to a successor. This would probably fall into a fairly * simple loop, but we introduce damage into the system, randomly * flipping about 1 bit in 64. * * The result is semi-structured and compressible. */ uint8_t *d = original.data; uint8_t *table = talloc_array(mem_ctx, uint8_t, 65536); uint32_t *table32 = (void*)table; ssize_t comp_size; struct jsf_rng rng; jsf32_init(&rng, 1); for (i = 0; i < (65536 / 4); i++) { table32[i] = jsf32(&rng); } d[0] = 'a'; d[1] = 'b'; for (i = 2; i < original.length; i++) { uint16_t k = (d[i - 2] << 8) | d[i - 1]; uint32_t damage = jsf32(&rng) & jsf32(&rng) & jsf32(&rng); damage &= (damage >> 16); k ^= damage & 0xffff; d[i] = table[k]; } comp_size = attempt_round_trip(mem_ctx, original, "/tmp/random-graph", ref); assert_true(comp_size > 0); assert_true(comp_size < original.length); talloc_free(mem_ctx); } static void test_lzxpress_plain_chaos_graph_round_trip(void **state) { size_t i; TALLOC_CTX *mem_ctx = talloc_new(NULL); DATA_BLOB original = data_blob_talloc(mem_ctx, NULL, 5 * 1024 * 1024); DATA_BLOB ref = {0}; /* * There's a random trigram graph, with each pair of sequential bytes * pointing to a successor. This would probably fall into a fairly * simple loop, but we keep changing the graph. The result is long * periods of stability separatd by bursts of noise. */ uint8_t *d = original.data; uint8_t *table = talloc_array(mem_ctx, uint8_t, 65536); uint32_t *table32 = (void*)table; ssize_t comp_size; struct jsf_rng rng; jsf32_init(&rng, 1); for (i = 0; i < (65536 / 4); i++) { table32[i] = jsf32(&rng); } d[0] = 'a'; d[1] = 'b'; for (i = 2; i < original.length; i++) { uint16_t k = (d[i - 2] << 8) | d[i - 1]; uint32_t damage = jsf32(&rng); d[i] = table[k]; if ((damage >> 29) == 0) { uint16_t index = damage & 0xffff; uint8_t value = (damage >> 16) & 0xff; table[index] = value; } } comp_size = attempt_round_trip(mem_ctx, original, "/tmp/chaos-graph", ref); assert_true(comp_size > 0); assert_true(comp_size < original.length); talloc_free(mem_ctx); } static void test_lzxpress_plain_sparse_random_graph_round_trip(void **state) { size_t i; TALLOC_CTX *mem_ctx = talloc_new(NULL); DATA_BLOB original = data_blob_talloc(mem_ctx, NULL, 5 * 1024 * 1024); DATA_BLOB ref = {0}; /* * There's a random trigram graph, with each pair of sequential bytes * pointing to a successor. This will fall into a fairly simple loops, * but we introduce damage into the system, randomly mangling about 1 * byte in 65536. * * The result has very long repetitive runs, which should lead to * oversized blocks. */ uint8_t *d = original.data; uint8_t *table = talloc_array(mem_ctx, uint8_t, 65536); uint32_t *table32 = (void*)table; ssize_t comp_size; struct jsf_rng rng; jsf32_init(&rng, 3); for (i = 0; i < (65536 / 4); i++) { table32[i] = jsf32(&rng); } d[0] = 'a'; d[1] = 'b'; for (i = 2; i < original.length; i++) { uint16_t k = (d[i - 2] << 8) | d[i - 1]; uint32_t damage = jsf32(&rng); if ((damage & 0xffff0000) == 0) { k ^= damage & 0xffff; } d[i] = table[k]; } comp_size = attempt_round_trip(mem_ctx, original, "/tmp/sparse-random-graph", ref); assert_true(comp_size > 0); assert_true(comp_size < original.length); talloc_free(mem_ctx); } static void test_lzxpress_plain_random_noise_round_trip(void **state) { size_t i; size_t len = 10 * 1024 * 1024; TALLOC_CTX *mem_ctx = talloc_new(NULL); DATA_BLOB original = data_blob_talloc(mem_ctx, NULL, len); DATA_BLOB ref = {0}; ssize_t comp_size; /* * We are filling this up with incompressible noise, but we can assert * quite tight bounds on how badly it will fail to compress. * * There is one additional bit for each code, which says whether the * code is a literal byte or a match. If *all* codes are literal * bytes, the length should be 9/8 the original (with rounding * issues regarding the indicator bit blocks). * * If some matches are found the length will be a bit less. We would * expect one 3 byte match per 1 << 24 tries, but we try 8192 times * per position. That means there'll a match 1/2048 of the time at * best. 255 times out of 256 this will be exactly a 3 byte match, * encoded as two bytes, so we could get a 1 / 2048 saving on top of * the 1/8 cost. There'll be a smattering of longer matches too, and * the potential for complicated maths to account for those, but we'll * skimp on that by allowing for a 1/1500 saving. * * With the hash table, we take a shortcut in the "8192 tries", and * the size of the table makes a difference in how we perform, with 13 * bits (8192 slots) naturally being luckier than 12. Ultimately, * either way, the compressed file is still 12.5% bigger than the * original. */ size_t limit = len * 9 / 8 + 4; uint32_t *d32 = (uint32_t*)((void*)original.data); struct jsf_rng rng; jsf32_init(&rng, 2); for (i = 0; i < (len / 4); i++) { d32[i] = jsf32(&rng); } comp_size = attempt_round_trip(mem_ctx, original, "/tmp/random-noise", ref); debug_message("original size %zu; compressed size %zd; ratio %.5f\n", len, comp_size, ((double)comp_size) / len); debug_message("expected range %zu - %zu\n", limit - limit / 1500, limit); assert_true(comp_size > 0); assert_true(comp_size < limit); assert_true(comp_size >= limit - limit / 1500); talloc_free(mem_ctx); } /* Tests based on [MS-XCA] 3.1 Examples */ static void test_msft_data1(void **state) { TALLOC_CTX *tmp_ctx = talloc_new(NULL); 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)); c_size = lzxpress_compress((const uint8_t *)fixed_data, strlen(fixed_data), out, talloc_get_size(out)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, sizeof(fixed_out)); assert_memory_equal(out, fixed_out, c_size); out2 = talloc_size(tmp_ctx, strlen(fixed_data)); c_size = lzxpress_decompress(out, sizeof(fixed_out), out2, talloc_get_size(out2)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, strlen(fixed_data)); assert_memory_equal(out2, fixed_data, c_size); talloc_free(tmp_ctx); } static void test_msft_data2(void **state) { TALLOC_CTX *tmp_ctx = talloc_new(NULL); 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)); c_size = lzxpress_compress((const uint8_t *)fixed_data, strlen(fixed_data), out, talloc_get_size(out)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, sizeof(fixed_out)); assert_memory_equal(out, fixed_out, c_size); out2 = talloc_size(tmp_ctx, strlen(fixed_data)); c_size = lzxpress_decompress(out, sizeof(fixed_out), out2, talloc_get_size(out2)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, strlen(fixed_data)); assert_memory_equal(out2, fixed_data, c_size); talloc_free(tmp_ctx); } /* test lzxpress */ static void test_lzxpress(void **state) { TALLOC_CTX *tmp_ctx = talloc_new(NULL); const char *fixed_data = "this is a test. and this is a test too"; 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 }; 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, *out3; out = talloc_size(tmp_ctx, 2048); memset(out, 0x42, talloc_get_size(out)); c_size = lzxpress_compress((const uint8_t *)fixed_data, strlen(fixed_data), out, talloc_get_size(out)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, sizeof(fixed_out)); assert_memory_equal(out, fixed_out, c_size); out2 = talloc_size(tmp_ctx, strlen(fixed_data)); c_size = lzxpress_decompress(out, sizeof(fixed_out), out2, talloc_get_size(out2)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, strlen(fixed_data)); assert_memory_equal(out2, fixed_data, c_size); 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)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, strlen(fixed_data)); assert_memory_equal(out3, fixed_data, c_size); talloc_free(tmp_ctx); } static void test_lzxpress2(void **state) { /* * Use two matches, separated by a literal, and each with a length * greater than 10, to test the use of nibble_index. Both length values * (less ten) should be stored as adjacent nibbles to form the 0x21 * byte. */ TALLOC_CTX *tmp_ctx = talloc_new(NULL); const char *fixed_data = "aaaaaaaaaaaabaaaaaaaaaaaa"; const uint8_t fixed_out[] = { 0xff, 0xff, 0xff, 0x5f, 0x61, 0x07, 0x00, 0x21, 0x62, 0x67, 0x00}; ssize_t c_size; uint8_t *out, *out2; out = talloc_size(tmp_ctx, 2048); memset(out, 0x42, talloc_get_size(out)); c_size = lzxpress_compress((const uint8_t *)fixed_data, strlen(fixed_data), out, talloc_get_size(out)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, sizeof(fixed_out)); assert_memory_equal(out, fixed_out, c_size); out2 = talloc_size(tmp_ctx, strlen(fixed_data)); c_size = lzxpress_decompress(out, sizeof(fixed_out), out2, talloc_get_size(out2)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, strlen(fixed_data)); assert_memory_equal(out2, fixed_data, c_size); talloc_free(tmp_ctx); } static void test_lzxpress3(void **state) { /* * Use a series of 31 literals, followed by a single minimum-length * match (and a terminating literal), to test setting indic_pos when the * 32-bit flags value overflows after a match. */ TALLOC_CTX *tmp_ctx = talloc_new(NULL); const char *fixed_data = "abcdefghijklmnopqrstuvwxyz01234abca"; const uint8_t fixed_out[] = { 0x01, 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, 0x30, 0x31, 0x32, 0x33, 0x34, 0xf0, 0x00, 0xff, 0xff, 0xff, 0x7f, 0x61}; ssize_t c_size; uint8_t *out, *out2; out = talloc_size(tmp_ctx, 2048); memset(out, 0x42, talloc_get_size(out)); c_size = lzxpress_compress((const uint8_t *)fixed_data, strlen(fixed_data), out, talloc_get_size(out)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, sizeof(fixed_out)); assert_memory_equal(out, fixed_out, c_size); out2 = talloc_size(tmp_ctx, strlen(fixed_data)); c_size = lzxpress_decompress(out, sizeof(fixed_out), out2, talloc_get_size(out2)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, strlen(fixed_data)); assert_memory_equal(out2, fixed_data, c_size); talloc_free(tmp_ctx); } static void test_lzxpress4(void **state) { /* * Use a series of 31 literals, followed by a single minimum-length * match, to test that the final set of 32-bit flags is written * correctly when it is empty. */ TALLOC_CTX *tmp_ctx = talloc_new(NULL); const char *fixed_data = "abcdefghijklmnopqrstuvwxyz01234abc"; const uint8_t fixed_out[] = { 0x01, 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, 0x30, 0x31, 0x32, 0x33, 0x34, 0xf0, 0x00, 0xff, 0xff, 0xff, 0xff}; ssize_t c_size; uint8_t *out, *out2; out = talloc_size(tmp_ctx, 2048); memset(out, 0x42, talloc_get_size(out)); c_size = lzxpress_compress((const uint8_t *)fixed_data, strlen(fixed_data), out, talloc_get_size(out)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, sizeof(fixed_out)); assert_memory_equal(out, fixed_out, c_size); out2 = talloc_size(tmp_ctx, strlen(fixed_data)); c_size = lzxpress_decompress(out, sizeof(fixed_out), out2, talloc_get_size(out2)); assert_int_not_equal(c_size, -1); assert_int_equal(c_size, strlen(fixed_data)); assert_memory_equal(out2, fixed_data, c_size); talloc_free(tmp_ctx); } static void test_lzxpress_many_zeros(void **state) { /* * Repeated values (zero is convenient but not special) will lead to * very long substring searches in compression, which can be very slow * if we're not careful. * * This test makes a very loose assertion about how long it should * take to compress a million zeros. * * Wall clock time *should* be < 0.1 seconds with the fix and around a * minute without it. We try for CLOCK_THREAD_CPUTIME_ID which should * filter out some noise on the machine, and set the threshold at 5 * seconds. */ TALLOC_CTX *tmp_ctx = talloc_new(NULL); const size_t N_ZEROS = 1000000; const uint8_t *zeros = talloc_zero_size(tmp_ctx, N_ZEROS); const ssize_t expected_c_size_max = 120; const ssize_t expected_c_size_min = 93; ssize_t c_size; uint8_t *comp, *decomp; static struct timespec t_start, t_end; uint64_t elapsed_ns; if (clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t_start) != 0) { if (clock_gettime(CUSTOM_CLOCK_MONOTONIC, &t_start) != 0) { clock_gettime(CLOCK_REALTIME, &t_start); } } comp = talloc_zero_size(tmp_ctx, 2048); c_size = lzxpress_compress(zeros, N_ZEROS, comp, talloc_get_size(comp)); /* * Because our compression depends on heuristics, we don't insist on * an exact size in this case. */ assert_true(c_size <= expected_c_size_max); assert_true(c_size >= expected_c_size_min); decomp = talloc_size(tmp_ctx, N_ZEROS * 2); c_size = lzxpress_decompress(comp, c_size, decomp, N_ZEROS * 2); if (clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t_end) != 0) { if (clock_gettime(CUSTOM_CLOCK_MONOTONIC, &t_end) != 0) { clock_gettime(CLOCK_REALTIME, &t_end); } } elapsed_ns = ( (t_end.tv_sec - t_start.tv_sec) * 1000U * 1000U * 1000U) + (t_end.tv_nsec - t_start.tv_nsec); print_message("round-trip time: %"PRIu64" ns\n", elapsed_ns); assert_true(elapsed_ns < 3 * 1000U * 1000U * 1000U); assert_memory_equal(decomp, zeros, N_ZEROS); talloc_free(tmp_ctx); } static void test_lzxpress_round_trip(void **state) { /* * Examples found using via fuzzing. */ TALLOC_CTX *tmp_ctx = talloc_new(NULL); size_t i; struct b64_pair { const char *uncompressed; const char *compressed; } pairs[] = { { /* this results in a trailing flags block */ "AAICAmq/EKdP785YU2Ddh7d4vUtdlQyLeHV09LHpUBw=", "AAAAAAACAgJqvxCnT+/OWFNg3Ye3eL1LXZUMi3h1dPSx6VAc/////w==", }, { /* empty string compresses to empty string */ "", "" }, }; const size_t alloc_size = 1000; uint8_t *data = talloc_array(tmp_ctx, uint8_t, alloc_size); for (i = 0; i < ARRAY_SIZE(pairs); i++) { ssize_t len; DATA_BLOB uncomp = base64_decode_data_blob_talloc( tmp_ctx, pairs[i].uncompressed); DATA_BLOB comp = base64_decode_data_blob_talloc( tmp_ctx, pairs[i].compressed); len = lzxpress_compress(uncomp.data, uncomp.length, data, alloc_size); assert_int_not_equal(len, -1); assert_int_equal(len, comp.length); assert_memory_equal(comp.data, data, len); len = lzxpress_decompress(comp.data, comp.length, data, alloc_size); assert_int_not_equal(len, -1); assert_int_equal(len, uncomp.length); assert_memory_equal(uncomp.data, data, len); } talloc_free(tmp_ctx); } int main(void) { const struct CMUnitTest tests[] = { cmocka_unit_test(test_lzxpress_plain_decompress_files), cmocka_unit_test(test_lzxpress_plain_decompress_more_compressed_files), cmocka_unit_test(test_lzxpress_plain_round_trip_files), cmocka_unit_test(test_lzxpress_plain_long_gpl_round_trip), cmocka_unit_test(test_lzxpress_plain_long_random_graph_round_trip), cmocka_unit_test(test_lzxpress_plain_chaos_graph_round_trip), cmocka_unit_test(test_lzxpress_plain_sparse_random_graph_round_trip), cmocka_unit_test(test_lzxpress_plain_long_random_graph_round_trip), cmocka_unit_test(test_lzxpress_plain_random_noise_round_trip), cmocka_unit_test(test_lzxpress), cmocka_unit_test(test_msft_data1), cmocka_unit_test(test_msft_data2), cmocka_unit_test(test_lzxpress2), cmocka_unit_test(test_lzxpress3), cmocka_unit_test(test_lzxpress4), cmocka_unit_test(test_lzxpress_many_zeros), cmocka_unit_test(test_lzxpress_round_trip), }; if (!isatty(1)) { cmocka_set_message_output(CM_OUTPUT_SUBUNIT); } return cmocka_run_group_tests(tests, NULL, NULL); }