path: root/lib/compression/tests/test_lzx_huffman.c

/*
 * Samba compression library - LGPLv3
 *
 * Copyright © Catalyst IT 2022
 *
 * Written by Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
 *
 *  ** NOTE! The following LGPL license applies to this file.
 *  ** It does NOT imply that all of Samba is released under the LGPL
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 3 of the License, or (at your option) any later version.
 *
 *  This library 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
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, see <http://www.gnu.org/licenses/>.
 */

#include <stdarg.h>
#include <stddef.h>
#include <setjmp.h>
#include <cmocka.h>
#include <stdbool.h>
#include <sys/stat.h>
#include "replace.h"
#include <talloc.h>
#include "lzxpress_huffman.h"
#include "lib/util/stable_sort.h"
#include "lib/util/data_blob.h"

/* set LZXHUFF_DEBUG_FILES to true to save round-trip files in /tmp. */
#define LZXHUFF_DEBUG_FILES false

/* set LZXHUFF_DEBUG_VERBOSE to true to print more. */
#define LZXHUFF_DEBUG_VERBOSE false


#if LZXHUFF_DEBUG_VERBOSE
#define debug_message(...) print_message(__VA_ARGS__)

#include <time.h>

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-huffman"
#define MORE_COMP_DIR "testdata/compression/compressed-more-huffman"


#define VARRGH(...) __VA_ARGS__

#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[] = {
	"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",
	"and_rand",
	"and_rand-128k+",
	"b63289ccc7f218c0d56b",
	"beta-variate1-128k+",
	"beta-variate2-128k+",
	"beta-variate3-128k+",
	"decayed_alphabet_128k+",
	"decayed_alphabet_64k",
	"exp_shuffle",
	"exp_shuffle-128k+",
	"f00842317dc6d5695b02",
	"fib_shuffle",
	"fib_shuffle-128k+",
	"fuzzing-0fc2d461b56cd8103c91",
	"fuzzing-17c961778538cc10ab7c",
	"fuzzing-3591f9dc02bb00a54b60",
	"fuzzing-3ec3bca27bb9eb40c128",
	"fuzzing-80b4fa18ff5f8dd04862",
	"fuzzing-a3115a81d1ac500318f9",
	"generate-windows-test-vectors.c",
	"midsummer-nights-dream.txt",
	"notes-on-the-underground.txt",
	"pg22009.txt",
	"repeating",
	"repeating-exactly-64k",
	"setup.log",
	"skewed_choices",
	"skewed_choices-128k+",
	/* These ones were deathly slow in fuzzing at one point */
	"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",
	"square_series",
	"square_series-128k+",
	"trigram_128k+",
	"trigram_64k",
	"trigram_sum_128k+",
	"trigram_sum_64k",
	NULL
};

struct lzx_pair bidirectional_pairs[] = {

	{.name = "abc__100_repeats", /* [MS-XCA] 3.2 example 2. */
	 .decompressed = BLOB_FROM_STRING(
		 "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc"
		 "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc"
		 "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc"
		 "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc"
		 "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc"
		 ),
	 .compressed = BLOB_FROM_ARRAY(
		 /*
		  * The 'a', 'b', and 'c' bytes are 0x61, 0x62, 0x63. No other
		  * symbols occur. That means we need 48 0x00 bytes for the
		  * first 96 symbol-nybbles, then some short codes, then zeros
		  * again for the rest of the literals.
		  */
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,
		 0x30, 0x23, /* a_ cb */
		 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, /* 100 bytes */
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0, /* here end the 0-255 literals (128 bytes) */
		 0x02, /* 'EOF' symbol 256 (byte 128 low) */
		 0,0,0,0,0, 0,0,0,0,0, 0,                    /* 140 bytes */
	         0,0,0,
		 0x20, /* codepoint 287 (byte 143 high) */
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,         /* 160 bytes */
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, /* 240 bytes */
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,
		 /*
		  * So that's the tree.
		  *
		  * length 2 codes for 'c', EOF, 287
		  * length 3 for 'a', 'b'.
		  *
		  * c:   00
		  * EOF: 01
		  * 287: 10
		  * a:   110
		  * b:   111
		  *
		  * thus the literal string "abc" is 110-111-00.
		  *
		  * Now for the lz77 match definitions for EOF and 287.
		  *
		  * Why 287? It encodes the match distance and offset.
		  *
		  * 287 - 256 = 31
		  *
		  * _length = 31 % 16 = 15
		  * _distance = 31 / 16 = 1
		  *
		  * (it's easier to look at the hex, 0x11f:
		  * 1xx means a match; x1x is _distance; xxf is _length)
		  *
		  * _distance 1 means a two bit distance (10 or 11; 2 or 3).
		  * That means the next bit will be the least significant bit
		  * of distance (1 in this case, meaning distance 3).
		  *
		  * if _length is 15, real length is included inline.
		  *
		  * 'EOF' == 256 means _length = 0, _distance = 0.
		  *
		  * _distance 0 means 1, so no further bits needed.
		  * _length 0 means length 3.
		  *
		  * but when used as EOF, this doesn't matter.
		  */
		 0xa8, 0xdc, 0x00, 0x00, 0xff, 0x26, 0x01
		  /* These remaining bytes are:
		  *
		  * 10101000 11011100 00000000 00000000 11111111
		  * 00100110 00000001
		  *
		  * and we read them as 16 chunks (i.e. flipping odd/even order)
		  *
		  * 110-111-00  10-1-01-000
		  *   a  b   c 287 | EOF
		  *                |
		  *                this is the 287 distance low bit.
		  *
		  * The last 3 bits are not used. The 287 length is sort of
		  * out of band, coming up soon (because 287 encodes length
		  * 15; most codes do not do this).
		  *
		  * 00000000 00000000
		  *
		  * This padding is there because the first 32 bits are read
		  * at the beginning of decoding. If there were more things to
		  * be encoded, they would be in here.
		  *
		  * 11111111
		  *
		  * This byte is pulled as the length for the 287 match.
		  * Because it is 0xff, we pull a further 2 bytes for the
		  * actual length, i.e. a 16 bit number greater than 270.
		  *
		  * 00000001 00100110
		  *
		  * that is 0x126 = 294 = the match length - 3 (because we're
		  * encoding ["abc", <copy from 3 back, 297 chars>, EOF]).
		  *
		  */
		 )
	},
	{.name = "abcdefghijklmnopqrstuvwxyz", /* [MS-XCA] 3.2 example 1. */
	 .decompressed = BLOB_FROM_STRING("abcdefghijklmnopqrstuvwxyz"),
	 .compressed = BLOB_FROM_ARRAY(
		 /*
		  * In this case there are no matches encoded as there are no
		  * repeated symbols. Including the EOF, there are 27 symbols
		  * all occurring exactly as frequently as each other (once).
		  * From that we would expect the codes to be mostly 5 bits
		  * long, because 27 < 2^5 (32), but greater than 2^4. And
		  * that's what we see.
		  */
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,
		 /* 14 non-zero bytes for 26 letters/nibbles */
		 0x50, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55,
		 0x55, 0x55, 0x55, 0x45, 0x44, 0x04,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,   /* 80 */
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,
		 0x04,                                 /* 0x100 EOF */
		 /* no matches */
		 0,0,0,0,0, 0,0,0,0,0, 0,                    /* 140 */
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, /* 240 */
		 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,

		 0xd8, 0x52, 0x3e, 0xd7, 0x94, 0x11, 0x5b, 0xe9,
		 0x19, 0x5f, 0xf9, 0xd6, 0x7c, 0xdf, 0x8d, 0x04,
		 0x00, 0x00, 0x00, 0x00)
	},
	{0}
};


static void test_lzxpress_huffman_decompress(void **state)
{
	size_t i;
	ssize_t written;
	uint8_t *dest = NULL;
	TALLOC_CTX *mem_ctx = talloc_new(NULL);
	for (i = 0; bidirectional_pairs[i].name != NULL; i++) {
		struct lzx_pair p = bidirectional_pairs[i];
		dest = talloc_array(mem_ctx, uint8_t, p.decompressed.length);

		debug_message("%s compressed %zu decomp %zu\n", p.name,
			      p.compressed.length,
			      p.decompressed.length);

		written = lzxpress_huffman_decompress(p.compressed.data,
						      p.compressed.length,
						      dest,
						      p.decompressed.length);
		assert_int_not_equal(written, -1);
		assert_int_equal(written, p.decompressed.length);

		assert_memory_equal(dest, p.decompressed.data, p.decompressed.length);
		talloc_free(dest);
	}
}

static void test_lzxpress_huffman_compress(void **state)
{
	size_t i;
	ssize_t written;
	uint8_t *dest = NULL;
	TALLOC_CTX *mem_ctx = talloc_new(NULL);
	for (i = 0; bidirectional_pairs[i].name != NULL; i++) {
		struct lzx_pair p = bidirectional_pairs[i];
		debug_message("%s compressed %zu decomp %zu\n", p.name,
			      p.compressed.length,
			      p.decompressed.length);

		written = lzxpress_huffman_compress_talloc(mem_ctx,
							   p.decompressed.data,
							   p.decompressed.length,
							   &dest);

		assert_int_not_equal(written, -1);
		assert_int_equal(written, p.compressed.length);
		assert_memory_equal(dest, p.compressed.data, p.compressed.length);
		talloc_free(dest);
	}
}


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_huffman_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.lzhuff", 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_huffman_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/%zu correct\n", score, i);
	assert_int_equal(score, i);
}


static void test_lzxpress_huffman_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.lzhuff", 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_huffman_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/%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 LZXHUFF_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 * 4 / 3 + 260);
	DATA_BLOB decompressed = data_blob_talloc(tmp_ctx, NULL,
						original.length);
	ssize_t comp_written, decomp_written;
	debug_start_timer();
	comp_written = lzxpress_huffman_compress_talloc(tmp_ctx,
							original.data,
							original.length,
							&compressed.data);
	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_huffman_decompress(compressed.data,
						     comp_written,
						     decompressed.data,
						     original.length);
	debug_end_timer("decompress", original.length);
	if (save_name != NULL && LZXHUFF_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_huffman_round_trip(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.lzhuff", 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/lzxhuffman-%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 *about* as good as Windows. Of course
	 * it doesn't matter if we do better, but mysteriously getting better
	 * is usually a sign that something is wrong.
	 *
	 * At the time of writing, compressed_total is 2674004, or 10686 more
	 * than the Windows reference total. That's < 0.5% difference, we're
	 * asserting at 2%.
	 */
	assert_true(labs(compressed_total - reference_total) <
		    compressed_total / 50);

	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_huffman_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;

	if (gpl.data == NULL) {
		print_message("could not read COPYING\n");
		fail();
	}

	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_huffman_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_huffman_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_huffman_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_huffman_random_noise_round_trip(void **state)
{
	size_t i;
	size_t len = 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.
	 *
	 * Specifically, with randomly distributed codes, the Huffman table
	 * should come out as roughly even, averaging 8 bit codes. Then there
	 * will be a 256 byte table every 64k, which is a 1/256 overhead (i.e.
	 * the compressed length will be 257/256 the original *on average*).
	 * We assert it is less than 1 in 200 but more than 1 in 300.
	 */
	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);
	assert_true(comp_size > 0);
	assert_true(comp_size > original.length + original.length / 300);
	assert_true(comp_size < original.length + original.length / 200);
	debug_message("original size %zu; compressed size %zd; ratio %.3f\n",
		      len, comp_size, ((double)comp_size) / len);

	talloc_free(mem_ctx);
}


static void test_lzxpress_huffman_overlong_matches(void **state)
{
	size_t i, j = 0;
	TALLOC_CTX *mem_ctx = talloc_new(NULL);
	DATA_BLOB original = data_blob_talloc(mem_ctx, NULL, 1024 * 1024);
	DATA_BLOB ref = {0};
	uint8_t *d = original.data;
	char filename[300];
	/*
	 * We are testing with something like "aaaaaaaaaaaaaaaaaaaaaaabbbbb"
	 * where typically the number of "a"s is > 65536, and the number of
	 * "b"s is < 42.
	 */
	ssize_t na[] = {65535, 65536, 65537, 65559, 65575, 200000, -1};
	ssize_t nb[] = {1, 2, 20, 39, 40, 41, 42, -1};
	int score = 0;
	ssize_t comp_size;

	for (i = 0; na[i] >= 0; i++) {
		ssize_t a = na[i];
		memset(d, 'a', a);
		for (j = 0; nb[j] >= 0; j++) {
			ssize_t b = nb[j];
			memset(d + a, 'b', b);
			original.length = a + b;
			snprintf(filename, sizeof(filename),
				 "/tmp/overlong-%zd-%zd", a, b);
			comp_size = attempt_round_trip(mem_ctx,
						       original,
						       filename, ref);
			if (comp_size > 0) {
				score++;
			}
		}
	}
	debug_message("%d/%zu correct\n", score, i * j);
	assert_int_equal(score, i * j);
	talloc_free(mem_ctx);
}


static void test_lzxpress_huffman_overlong_matches_abc(void **state)
{
	size_t i, j = 0, k = 0;
	TALLOC_CTX *mem_ctx = talloc_new(NULL);
	DATA_BLOB original = data_blob_talloc(mem_ctx, NULL, 1024 * 1024);
	DATA_BLOB ref = {0};
	uint8_t *d = original.data;
	char filename[300];
	/*
	 * We are testing with something like "aaaabbbbcc" where typically
	 * the number of "a"s + "b"s is around 65536, and the number of "c"s
	 * is < 43.
	 */
	ssize_t nab[] = {1, 21, 32767, 32768, 32769, -1};
	ssize_t nc[] = {1, 2, 20, 39, 40, 41, 42, -1};
	int score = 0;
	ssize_t comp_size;

	for (i = 0; nab[i] >= 0; i++) {
		ssize_t a = nab[i];
		memset(d, 'a', a);
		for (j = 0; nab[j] >= 0; j++) {
			ssize_t b = nab[j];
			memset(d + a, 'b', b);
			for (k = 0; nc[k] >= 0; k++) {
				ssize_t c = nc[k];
				memset(d + a + b, 'c', c);
				original.length = a + b + c;
				snprintf(filename, sizeof(filename),
					 "/tmp/overlong-abc-%zd-%zd-%zd",
					 a, b, c);
				comp_size = attempt_round_trip(mem_ctx,
							       original,
							       filename, ref);
				if (comp_size > 0) {
					score++;
				}
			}
		}
	}
	debug_message("%d/%zu correct\n", score, i * j * k);
	assert_int_equal(score, i * j * k);
	talloc_free(mem_ctx);
}


static void test_lzxpress_huffman_extremely_compressible_middle(void **state)
{
	size_t len = 192 * 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;
	/*
	 * When a middle block (i.e. not the first and not the last of >= 3),
	 * can be entirely expressed as a match starting in the previous
	 * block, the Huffman tree would end up with 1 element, which does not
	 * work for the code construction. It really wants to use both bits.
	 * So we need to ensure we have some way of dealing with this.
	 */
	memset(original.data, 'a', 0x10000 - 1);
	memset(original.data + 0x10000 - 1, 'b', 0x10000 + 1);
	memset(original.data + 0x20000, 'a', 0x10000);
	comp_size = attempt_round_trip(mem_ctx, original, "/tmp/compressible-middle", ref);
	assert_true(comp_size > 0);
	assert_true(comp_size < 1024);
	debug_message("original size %zu; compressed size %zd; ratio %.3f\n",
		      len, comp_size, ((double)comp_size) / len);

	talloc_free(mem_ctx);
}


static void test_lzxpress_huffman_max_length_limit(void **state)
{
	size_t len = 65 * 1024 * 1024;
	TALLOC_CTX *mem_ctx = talloc_new(NULL);
	DATA_BLOB original = data_blob_talloc_zero(mem_ctx, len);
	DATA_BLOB ref = {0};
	ssize_t comp_size;
	/*
	 * Reputedly Windows has a 64MB limit in the maximum match length it
	 * will encode. We follow this, and test that here with nearly 65 MB
	 * of zeros between two letters; this should be encoded in three
	 * blocks:
	 *
	 * 1. 'a', 64M × '\0'
	 * 2. (1M - 2) × '\0' -- finishing off what would have been the same match
	 * 3. 'b' EOF
	 *
	 * Which we can assert by saying the length is > 768, < 1024.
	 */
	original.data[0] = 'a';
	original.data[len - 1] = 'b';
	comp_size = attempt_round_trip(mem_ctx, original, "/tmp/max-length-limit", ref);
	assert_true(comp_size > 0x300);
	assert_true(comp_size < 0x400);
	debug_message("original size %zu; compressed size %zd; ratio %.3f\n",
		      len, comp_size, ((double)comp_size) / len);

	talloc_free(mem_ctx);
}


static void test_lzxpress_huffman_short_boring_strings(void **state)
{
	size_t len = 64 * 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;
	ssize_t lengths[] = {
		1, 2, 20, 39, 40, 41, 42, 256, 270, 273, 274, 1000, 64000, -1};
	char filename[300];
	size_t i;
	/*
	 * How do short repetitive strings work? We're poking at the limit
	 * around which LZ77 comprssion is turned on.
	 *
	 * For this test we don't change the blob memory between runs, just
	 * the declared length.
	 */
	memset(original.data, 'a', len);
	for (i = 0; lengths[i] >= 0; i++) {
		original.length = lengths[i];
		snprintf(filename, sizeof(filename),
			 "/tmp/short-boring-%zu",
			 original.length);
		comp_size = attempt_round_trip(mem_ctx, original, filename, ref);
		if (original.length < 41) {
			assert_true(comp_size > 256 + original.length / 8);
		} else if (original.length < 274) {
			assert_true(comp_size == 261);
		} else {
			assert_true(comp_size == 263);
		}
		assert_true(comp_size < 261 + original.length / 8);
	}
	/* let's just show we didn't change the original */
	for (i = 0; i < len; i++) {
		if (original.data[i] != 'a') {
			fail_msg("input data[%zu] was changed! (%2x, expected %2x)\n",
				 i, original.data[i], 'a');
		}
	}

	talloc_free(mem_ctx);
}


static void test_lzxpress_huffman_compress_empty_or_null(void **state)
{
	/*
	 * We expect these to fail with a -1, except the last one, which does
	 * the real thing.
	 */
	ssize_t ret;
	const uint8_t *input = bidirectional_pairs[0].decompressed.data;
	size_t ilen = bidirectional_pairs[0].decompressed.length;
	size_t olen = bidirectional_pairs[0].compressed.length;
	uint8_t output[olen];
	struct lzxhuff_compressor_mem cmp_mem;

	ret = lzxpress_huffman_compress(&cmp_mem, input, 0, output, olen);
	assert_int_equal(ret, -1LL);
	ret = lzxpress_huffman_compress(&cmp_mem, input, ilen, output, 0);
	assert_int_equal(ret, -1LL);

	ret = lzxpress_huffman_compress(&cmp_mem, NULL, ilen, output, olen);
	assert_int_equal(ret, -1LL);
	ret = lzxpress_huffman_compress(&cmp_mem, input, ilen, NULL, olen);
	assert_int_equal(ret, -1LL);
	ret = lzxpress_huffman_compress(NULL, input, ilen, output, olen);
	assert_int_equal(ret, -1LL);

	ret = lzxpress_huffman_compress(&cmp_mem, input, ilen, output, olen);
	assert_int_equal(ret, olen);
}


static void test_lzxpress_huffman_decompress_empty_or_null(void **state)
{
	/*
	 * We expect these to fail with a -1, except the last one.
	 */
	ssize_t ret;
	const uint8_t *input = bidirectional_pairs[0].compressed.data;
	size_t ilen = bidirectional_pairs[0].compressed.length;
	size_t olen = bidirectional_pairs[0].decompressed.length;
	uint8_t output[olen];

	ret = lzxpress_huffman_decompress(input, 0, output, olen);
	assert_int_equal(ret, -1LL);
	ret = lzxpress_huffman_decompress(input, ilen, output, 0);
	assert_int_equal(ret, -1LL);

	ret = lzxpress_huffman_decompress(NULL, ilen, output, olen);
	assert_int_equal(ret, -1LL);
	ret = lzxpress_huffman_decompress(input, ilen, NULL, olen);
	assert_int_equal(ret, -1LL);

	ret = lzxpress_huffman_decompress(input, ilen, output, olen);
	assert_int_equal(ret, olen);
}


int main(void) {
	const struct CMUnitTest tests[] = {
		cmocka_unit_test(test_lzxpress_huffman_short_boring_strings),
		cmocka_unit_test(test_lzxpress_huffman_max_length_limit),
		cmocka_unit_test(test_lzxpress_huffman_extremely_compressible_middle),
		cmocka_unit_test(test_lzxpress_huffman_long_random_graph_round_trip),
		cmocka_unit_test(test_lzxpress_huffman_chaos_graph_round_trip),
		cmocka_unit_test(test_lzxpress_huffman_sparse_random_graph_round_trip),
		cmocka_unit_test(test_lzxpress_huffman_round_trip),
		cmocka_unit_test(test_lzxpress_huffman_decompress_files),
		cmocka_unit_test(test_lzxpress_huffman_decompress_more_compressed_files),
		cmocka_unit_test(test_lzxpress_huffman_compress),
		cmocka_unit_test(test_lzxpress_huffman_decompress),
		cmocka_unit_test(test_lzxpress_huffman_long_gpl_round_trip),
		cmocka_unit_test(test_lzxpress_huffman_long_random_graph_round_trip),
		cmocka_unit_test(test_lzxpress_huffman_random_noise_round_trip),
		cmocka_unit_test(test_lzxpress_huffman_overlong_matches_abc),
		cmocka_unit_test(test_lzxpress_huffman_overlong_matches),
		cmocka_unit_test(test_lzxpress_huffman_decompress_empty_or_null),
		cmocka_unit_test(test_lzxpress_huffman_compress_empty_or_null),
	};
	if (!isatty(1)) {
		cmocka_set_message_output(CM_OUTPUT_SUBUNIT);
	}

	return cmocka_run_group_tests(tests, NULL, NULL);
}