v11-0004-Tests-for-Delta-Frame-of-Reference-unit.patch

From 523c5a08010e8882e9bf2f601f1e85092a5c61b3 Mon Sep 17 00:00:00 2001
From: Evgeny Voropaev <evorop@gmail.com>
Date: Mon, 13 Apr 2026 23:18:07 +0800
Subject: [PATCH v11 4/5] Tests for Delta Frame of Reference unit.

The unit test is implemented as a C program (ELF executable). The test
can be run with the 'make check-unit'. Tests support the TAP protocol
and are executed using the Prove utility.

Author: Evgeny Voropaev <evgeny.voropaev@tantorlabs.com> <evorop@gmail.com>
Reviewed by: Andrey Borodin <x4mmm@yandex-team.ru>
---
 src/test/dfor/.gitignore      |   1 +
 src/test/dfor/Makefile        |   3 +-
 src/test/dfor/meson.build     |   2 +
 src/test/dfor/test_dfor_u16.c | 371 ++++++++++++++++++++++++++++++++++
 4 files changed, 376 insertions(+), 1 deletion(-)
 create mode 100644 src/test/dfor/test_dfor_u16.c

diff --git a/src/test/dfor/.gitignore b/src/test/dfor/.gitignore
index 0d77a51216b..447e95c0c09 100644
--- a/src/test/dfor/.gitignore
+++ b/src/test/dfor/.gitignore
@@ -1,3 +1,4 @@
 test_bitpack_u16
+test_dfor_u16
 test_uniqsortvect_u16
 test_vect_u16
diff --git a/src/test/dfor/Makefile b/src/test/dfor/Makefile
index 4fc9f4bc1ba..2ca98f76a0f 100644
--- a/src/test/dfor/Makefile
+++ b/src/test/dfor/Makefile
@@ -33,7 +33,8 @@ LIBTAP_OBJS = $(top_builddir)/src/test/libtap/tap.o
 
 TESTS= test_vect_u16 \
        test_uniqsortvect_u16 \
-       test_bitpack_u16
+       test_bitpack_u16 \
+       test_dfor_u16
 
 $(TESTS:%=%.o): CPPFLAGS += -I$(top_builddir)/src/test -DFRONTEND
 
diff --git a/src/test/dfor/meson.build b/src/test/dfor/meson.build
index ce762c52430..4a760ab68fa 100644
--- a/src/test/dfor/meson.build
+++ b/src/test/dfor/meson.build
@@ -8,6 +8,7 @@ dfor_dir = join_paths(meson.project_source_root(), 'src/backend/lib')
 dfor_sources = files(
   join_paths(dfor_dir, 'vect_u16.c'),
   join_paths(dfor_dir, 'bitpack_u16.c'),
+  join_paths(dfor_dir, 'dfor_u16.c'),
 )
 
 dfor_test_lib = static_library(
@@ -36,6 +37,7 @@ test_names = [
   'test_vect_u16',
   'test_uniqsortvect_u16',
   'test_bitpack_u16',
+  'test_dfor_u16',
 ]
 
 foreach t : test_names
diff --git a/src/test/dfor/test_dfor_u16.c b/src/test/dfor/test_dfor_u16.c
new file mode 100644
index 00000000000..322b714ba38
--- /dev/null
+++ b/src/test/dfor/test_dfor_u16.c
@@ -0,0 +1,371 @@
+/*
+ * test_dfor.c
+ */
+
+#include "lib/bitpack_u16.h"
+#include "lib/dfor_u16.h"
+#include "lib/vect_u16.h"
+#include "libtap/tap.h"
+#include "test.h"
+
+void test_delta_calculation(size_t cnt, uint16_t inArr[], size_t cntDelta,
+							uint16_t marDeltasExpected[], size_t cntWidth,
+							uint16_t marWidthsExpected[], size_t cntStat,
+							uint16_t marWidthsStatExpected[]);
+
+void test_calc_exceptions(size_t numDeltas, size_t numWidths,
+						  uint16_t marWidths[], size_t numCounts,
+						  uint16_t marCounts[], size_t szAwaitedWidth,
+						  size_t cntAwaitedExcCount);
+
+void test_dfor(size_t cnt, uint16_t arr[], excalg_t isExcUsage,
+			   size_t widDeltaAwaited, size_t cntExcCntAwaited,
+			   size_t widExcWidAwaited, size_t widExcPosWidAwaited,
+			   size_t cntBitsCountAwaited, size_t cntByteCountAwaited,
+			   float flMinRatioAwaited, uint8_t u8arPackAwaited[]);
+
+void
+test_delta_calculation(size_t cnt, uint16_t inArr[], size_t cntDelta,
+					   uint16_t marDeltasExpected[], size_t cntWidth,
+					   uint16_t marWidthsExpected[], size_t cntStat,
+					   uint16_t marWidthsStatExpected[])
+{
+	vect_u16_t vDeltas;
+	vect_u16_t vWidthCounters;
+	uniqsortvect_u16_t usvDeltaWidths;
+	vect_u16_t awaited;
+	int res;
+
+	printf("------------------------------------------------\n");
+	printf("Test\n");
+	printf("------------------------------------------------\n");
+
+	printf("  inArr:");
+	for (size_t i = 0; i < cnt; i++)
+		printf(" %u", (uint32_t)inArr[i]);
+	printf("\n");
+
+	vect_u16_init(&vDeltas, 0, NULL);
+	vect_u16_init(&usvDeltaWidths, 0, NULL);
+	vect_u16_init(&vWidthCounters, 0, NULL);
+
+	/* Tested function */
+	res = dfor_u16_calc_deltas(cnt, inArr, &vDeltas, &usvDeltaWidths,
+							   &vWidthCounters);
+	cmp_ok(res, "==", 0);
+
+	printf("  Delta expected:");
+	for (size_t i = 0; i < cntDelta; i++)
+		printf(" %u", (uint32_t)marDeltasExpected[i]);
+	printf("\n");
+
+	printf("  Delta fact:    ");
+	vect_u16_print(&vDeltas);
+
+	cmp_ok(vDeltas.cnt, "==", cnt, "The Delta count is OK.");
+	vect_u16_init(&awaited, 0, NULL);
+	vect_u16_fill(&awaited, cnt, marDeltasExpected);
+	cmp_ok(vect_u16_compare(&vDeltas, &awaited), "==", 0,
+		   "All deltas are calculated properly");
+	vect_u16_clear(&awaited);
+
+	printf("  Width expected:");
+	for (size_t i = 0; i < cntWidth; i++)
+		printf(" %u", (uint32_t)marWidthsExpected[i]);
+	printf("\n");
+
+	printf("  Width fact:    ");
+	vect_u16_print(&usvDeltaWidths);
+
+	cmp_ok(usvDeltaWidths.cnt, "==", cntWidth, "The Width count is OK.");
+
+	/* don't really need initialisation after vect_clean having been done
+	 * above*/
+	/* vect_u16_init(&awaited, 0, NULL); */
+
+	vect_u16_fill(&awaited, cntWidth, marWidthsExpected);
+	cmp_ok(vect_u16_compare(&usvDeltaWidths, &awaited), "==", 0,
+		   "All delta widths is OK.");
+	vect_u16_clear(&awaited);
+
+	printf("  Statistics expected:");
+	for (size_t i = 0; i < cntStat; i++)
+		printf(" %u", (uint32_t)marWidthsStatExpected[i]);
+	printf("\n");
+
+	printf("  Statistics fact:    ");
+	vect_u16_print(&vWidthCounters);
+
+	cmp_ok(
+		usvDeltaWidths.cnt, "==", vWidthCounters.cnt,
+		"The count of statistics of widths is equal to the count of widths.");
+
+	/* don't really need initialisation after vect_clean having been done
+	 * above*/
+	vect_u16_fill(&awaited, cntStat, marWidthsStatExpected);
+	cmp_ok(vect_u16_compare(&vWidthCounters, &awaited), "==", 0,
+		   "Width statistics is OK.");
+	vect_u16_clear(&awaited);
+
+	vect_u16_clear(&vDeltas);
+	vect_u16_clear(&usvDeltaWidths);
+	vect_u16_clear(&vWidthCounters);
+}
+
+void
+test_calc_exceptions(size_t numDeltas, size_t numWidths, uint16_t marWidths[],
+					 size_t numCounts, uint16_t marCounts[],
+					 size_t szAwaitedWidth, size_t cntAwaitedExcCount)
+{
+	int res;
+	vect_u16_t vWidthCounters;
+	uniqsortvect_u16_t usvDeltaWidths;
+	size_t width, cntExceptions;
+
+	vect_u16_init(&usvDeltaWidths, 0, NULL);
+	vect_u16_fill(&usvDeltaWidths, numWidths, marWidths);
+
+	vect_u16_init(&vWidthCounters, 0, NULL);
+	vect_u16_fill(&vWidthCounters, numCounts, marCounts);
+
+	res = dfor_u16_calc_width(numDeltas, &usvDeltaWidths, &vWidthCounters,
+							  &width, &cntExceptions);
+	cmp_ok(res, "==", 0);
+	cmp_ok(width, "==", szAwaitedWidth, "Width is OK.");
+	cmp_ok(cntExceptions, "==", cntAwaitedExcCount, "Exceptions num is OK");
+
+	vect_u16_clear(&usvDeltaWidths);
+	vect_u16_clear(&vWidthCounters);
+}
+
+void
+test_dfor(size_t cnt, uint16_t arr[], excalg_t isExcUsage,
+		  size_t widDeltaWidthAwaited, size_t cntExcCntAwaited,
+		  size_t widExcWidAwaited, size_t widExcPosWidAwaited,
+		  size_t cntBitsCountAwaited, size_t cntByteCountAwaited,
+		  float flMinRatioAwaited, uint8_t u8arPackAwaited[])
+{
+	int res;
+	dfor_meta_t dfor;
+	dfor_stats_t stats;
+	uniqsortvect_u16_t extracted;
+
+	res = dfor_u16_pack(cnt, arr, isExcUsage, &dfor, 0, NULL);
+	cmp_ok(res, "==", 0, "dfor_pack func has processed OK.");
+	cmp_ok(dfor.item_cnt, "==", cnt, "Count of deltas is OK.");
+	cmp_ok(dfor.delta_wid, "==", widDeltaWidthAwaited, "Delta width is OK.");
+	cmp_ok(dfor.exc_cnt, "==", cntExcCntAwaited, "Exception count is OK.");
+	cmp_ok(dfor.exc_wid, "==", widExcWidAwaited, "Exception width is OK.");
+	cmp_ok(dfor.exc_pos_wid, "==", widExcPosWidAwaited,
+		   "Exception position width is OK.");
+	ok(dfor.pack != NULL, "Pack is created (not NULL).");
+
+	stats = dfor_u16_calc_stats(dfor);
+	cmp_ok(stats.nbits, "==", cntBitsCountAwaited, "Bits count is OK.");
+	cmp_ok(dfor.nbytes, "==", cntByteCountAwaited, "Bytes count is OK.");
+	ok(stats.ratio > flMinRatioAwaited, "Compression ratio is OK.");
+
+	if (u8arPackAwaited != NULL)
+		ok(0 == memcmp(dfor.pack, u8arPackAwaited, cntByteCountAwaited),
+		   "Pack content is OK.");
+	else
+		ok(0 == 0, "Pack content check is skipped.");
+
+	test_print_u16_array(cnt, (uint16_t *)arr, "\n\nOriginal integer array");
+	test_print_u8_array(dfor.nbytes, dfor.pack, "Compressed integer array");
+	printf("Compression ratio:%f\n\n", stats.ratio);
+
+	vect_u16_init(&extracted, 0, NULL);
+
+	dfor_u16_unpack(&dfor, &extracted, 0, NULL);
+	cmp_ok(extracted.cnt, "==", cnt, "Extracted count is OK");
+	cmp_ok(0, "==", memcmp(arr, extracted.m, cnt),
+		   "Extracted array is equal to original");
+
+	free(dfor.pack);
+	vect_u16_clear(&extracted);
+}
+
+int
+main(void)
+{
+	plan(130);
+	printf("========================================\n");
+	printf("Test DELTA CALCULATION\n");
+	{
+		test_delta_calculation(
+			10, (uint16_t[]) { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, /* inArr */
+			10,
+			(uint16_t[]) { 0, 1, 1, 1, 1, 1, 1, 1, 1,
+						   1 },	   /* marDeltasExpected*/
+			1, (uint16_t[]) { 1 }, /* marWidthsExpected */
+			1, (uint16_t[]) { 10 } /* marWidthsStatExpected */);
+
+		test_delta_calculation(
+			10, (uint16_t[]) { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 }, /* inArr */
+			10,
+			(uint16_t[]) { 1, 2, 2, 2, 2, 2, 2, 2, 2,
+						   2 },		  /* marDeltasExpected*/
+			2, (uint16_t[]) { 1, 2 }, /* marWidthsExpected */
+			2, (uint16_t[]) { 1, 9 } /* marWidthsStatExpected */);
+
+		test_delta_calculation(
+			14,
+			(uint16_t[]) { 100, 200, 300, 400, 401, 402, 403, 404, 406, 408,
+						   410, 412, 414, 416 }, /* inArr */
+			14,
+			(uint16_t[]) { 100, 100, 100, 100, 1, 1, 1, 1, 2, 2, 2, 2, 2,
+						   2 },			 /* marDeltasExpected*/
+			3, (uint16_t[]) { 1, 2, 7 }, /* marWidthsExpected */
+			3, (uint16_t[]) { 4, 6, 4 } /* marWidthsStatExpected */);
+
+		test_delta_calculation(1, (uint16_t[]) { 123 }, /* inArr */
+							   1, (uint16_t[]) { 123 }, /* marDeltasExpected*/
+							   1, (uint16_t[]) { 7 },	/* marWidthsExpected */
+							   1,
+							   (uint16_t[]) { 1 } /* marWidthsStatExpected */);
+
+		test_delta_calculation(0, NULL, /* inArr */
+							   0, NULL, /* marDeltasExpected*/
+							   0, NULL, /* marWidthsExpected */
+							   0, NULL /* marWidthsStatExpected */);
+	}
+	printf("Test DELTA CALCULATION PASSED\n");
+	printf("========================================\n\n");
+
+	printf("========================================\n");
+	printf("Test EXCEPTIONS CALCULATION\n");
+	{
+		int res;
+		vect_u16_t vWidthCounters;
+		uniqsortvect_u16_t usvDeltaWidths;
+		size_t width, cntExceptions;
+
+		vect_u16_init(&usvDeltaWidths, 0, NULL);
+		vect_u16_fill(&usvDeltaWidths, 3, (uint16_t[]) { 1, 2, 7 });
+
+		vect_u16_init(&vWidthCounters, 0, NULL);
+		vect_u16_fill(&vWidthCounters, 3, (uint16_t[]) { 4, 6, 4 }); // 4+6+4=14
+
+		res = dfor_u16_calc_width(14, &usvDeltaWidths, &vWidthCounters, &width,
+								  &cntExceptions);
+		cmp_ok(res, "==", 0);
+		cmp_ok(width, "==", 7, "Widths={1,2,7}, Counters={4,6,4} => width=7");
+		cmp_ok(cntExceptions, "==", 0,
+			   "Widths={1,2,7}, Counters={4,6,4} => excptions_num=0");
+	}
+
+	test_calc_exceptions(14, 3, (uint16_t[]) { 1, 2, 7 }, /* widths of deltas*/
+						 3, (uint16_t[]) { 4, 6, 4 },	  /* statistics */
+						 7,	 /* width of short deltas */
+						 0); /* number of exceptions*/
+
+	test_calc_exceptions(14, 3, (uint16_t[]) { 1, 2, 7 }, /* widths */
+						 3, (uint16_t[]) { 6, 7, 1 },	  /* stat */
+						 2, 1); /* short deltas width, exceptions count*/
+
+	test_calc_exceptions(40, 3, (uint16_t[]) { 5, 6, 12 }, /* widths */
+						 3, (uint16_t[]) { 36, 2, 2 },	   /* stat */
+						 5, 4); /* short deltas width, exceptions count*/
+
+	test_calc_exceptions(40, 4, (uint16_t[]) { 5, 6, 7, 12 }, 4,
+						 (uint16_t[]) { 36, 1, 1, 2 }, 5, 4);
+
+	test_calc_exceptions(40, 4, (uint16_t[]) { 5, 6, 7, 12 }, 4,
+						 (uint16_t[]) { 35, 1, 2, 2 }, 6, 4);
+
+	test_calc_exceptions(40, 4, (uint16_t[]) { 5, 6, 7, 12 }, 4,
+						 (uint16_t[]) { 34, 1, 2, 3 }, 7, 3);
+
+	test_calc_exceptions(40, 4, (uint16_t[]) { 5, 6, 7, 12 }, 4,
+						 (uint16_t[]) { 1, 34, 2, 3 }, 7, 3);
+
+	test_calc_exceptions(40, 4, (uint16_t[]) { 5, 6, 7, 12 }, 4,
+						 (uint16_t[]) { 1, 33, 2, 4 }, 7, 4);
+
+	test_calc_exceptions(40, 4, (uint16_t[]) { 5, 6, 7, 12 }, 4,
+						 (uint16_t[]) { 1, 32, 2, 5 }, 12, 0);
+
+	printf("Test EXCEPTIONS CALCULATION PASSED\n");
+	printf("========================================\n\n");
+
+	printf("========================================\n");
+	printf("Test DELTA FRAME OF REFERENCES PACKING\n");
+
+	test_dfor(16,
+			  (uint16_t[]) { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
+							 15 }, /* cnt, array */
+			  DFOR_EXC_DONT_USE,   /* flag on use of exceptions */
+			  1,				   /* awaited width of short deltas */
+			  0,				   /* awaited count of exceptions */
+			  0,				   /* awaited exception width*/
+			  0,				   /* awaited exception position width*/
+			  16,				   /* awaited bits count */
+			  2,				   /* cntByteCountAwaited */
+			  15.99, /* awaited ratio min value (ratio >= 15.99) */
+			  (uint8_t[]) { 0xFE, 0xFF });
+
+	test_dfor(16,
+			  (uint16_t[]) { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
+							 15 }, /* cnt, array */
+			  DFOR_EXC_USE, /* flag on use of exceptions */
+			  1,			/* awaited width of short deltas */
+			  0,			/* awaited count of exceptions */
+			  0,			/* awaited exception width*/
+			  0,			/* awaited exception position width*/
+			  16,			/* awaited bits count */
+			  2,			/* cntByteCountAwaited */
+			  15.99,		/* awaited ratio min value (ratio >= 15.99) */
+			  (uint8_t[]) { 0xFE, 0xFF });
+
+	test_dfor(16,
+			  (uint16_t[]) { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
+							 1023 }, /* cnt, array */
+			  DFOR_EXC_DONT_USE,	 /* flag on use of exceptions */
+			  10,					 /* awaited width of short deltas */
+			  0,					 /* awaited count of exceptions */
+			  0,					 /* awaited exception width*/
+			  0,					 /* awaited exception position width*/
+			  10 * 16,				 /* awaited bits count */
+			  20,					 /* awaited bytes count */
+			  1.5,					 /* awaited ratio min value */
+			  (uint8_t[]) { 0x00, 0x04, 0x10, 0x40, 0x00, 0x01, 0x04,
+							0x10, 0x40, 0x00, 0x01, 0x04, 0x10, 0x40,
+							0x00, 0x01, 0x04, 0x10, 0x40, 0xFC });
+
+	test_dfor(16,
+			  (uint16_t[]) { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
+							 1023 }, /* cnt, array */
+			  DFOR_EXC_USE,			 /* flag on use of exceptions */
+			  1,					 /* awaited width of short deltas */
+			  1,					 /* awaited count of exceptions */
+			  9,					 /* awaited exception width*/
+			  4,					 /* awaited exception position width*/
+			  16 * 1 + 9 + 4,		 /* awaited bits count */
+			  4,					 /* awaited bytes count */
+			  7.99,					 /* awaited ratio min value */
+			  (uint8_t[]) { 0xFE, 0xFF, 0xF8, 0x1F });
+
+	test_dfor(30, /* cnt */
+					  (uint16_t[]) { 0, 1, 2, 3, 4,
+									 5, 6, 7, 8, 9,
+  /* delta=2, pos=10, deltapos=10 */ 11, 12, 13, 14, 15,
+									 16, 17, 18, 19, 20,
+									 21, 22, 23, 24, 25,
+  /* delta=3, pos=25, deltapos=15 */ 28, 29, 30, 31,
+  /* delta=3, pos=29, deltapos=4 */	 34 },  				/* array */
+			  DFOR_EXC_USE,			  /* flag on use of exceptions */
+			  1,					  /* awaited width of short deltas */
+			  3,					  /* awaited count of exceptions */
+			  1,					  /* awaited exception width*/
+			  4,					  /* awaited exception position width*/
+			  30 * 1 + 3 * 1 + 3 * 4, /* awaited bits count */
+			  6,					  /* awaited bytes count */
+			  9.99,					  /* awaited ratio min value */
+			  (uint8_t[]) { 0xFE, 0xFB, 0xFF, 0xFF, 0xF5, 0x09 });
+
+	printf("Test DELTA FRAME OF REFERENCES PACKING PASSED\n");
+	printf("========================================\n\n");
+
+	done_testing();
+}
-- 
2.53.0