[PATCH v3 2/4] hash: add dynamic polynomial calculation

[Vladimir Medvedkin <vladimir.medvedkin@intel.com>]

Current polynomial table has the following limitations:

1. It has polynomials up to degree 16
2. For each degree there are only 4 polynomials

The above results in less entropy when generating Toeplitz hash key
subsequences.

This patch replaces the current static table approach with dynamic
polynomial calculation for polynomials of degree 7 or higher, resulting
in better entropy of generated RSS hash key.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 lib/hash/meson.build               |   1 +
 lib/hash/rte_thash.c               |  46 +-----
 lib/hash/rte_thash.h               |  13 ++
 lib/hash/rte_thash_gf2_poly_math.c | 253 +++++++++++++++++++++++++++++
 lib/hash/version.map               |   1 +
 5 files changed, 274 insertions(+), 40 deletions(-)
 create mode 100644 lib/hash/rte_thash_gf2_poly_math.c

diff --git a/lib/hash/meson.build b/lib/hash/meson.build
index 277eb9fa93..7ce504ee8b 100644
--- a/lib/hash/meson.build
+++ b/lib/hash/meson.build
@@ -23,6 +23,7 @@ sources = files(
         'rte_fbk_hash.c',
         'rte_thash.c',
         'rte_thash_gfni.c',
+        'rte_thash_gf2_poly_math.c',
 )
 
 deps += ['net']
diff --git a/lib/hash/rte_thash.c b/lib/hash/rte_thash.c
index 894b4d9197..5c3d246657 100644
--- a/lib/hash/rte_thash.c
+++ b/lib/hash/rte_thash.c
@@ -31,33 +31,6 @@ static struct rte_tailq_elem rte_thash_tailq = {
 };
 EAL_REGISTER_TAILQ(rte_thash_tailq)
 
-/**
- * Table of some irreducible polinomials over GF(2).
- * For lfsr they are represented in BE bit order, and
- * x^0 is masked out.
- * For example, poly x^5 + x^2 + 1 will be represented
- * as (101001b & 11111b) = 01001b = 0x9
- */
-static const uint32_t irreducible_poly_table[][4] = {
-	{0, 0, 0, 0},	/** < degree 0 */
-	{1, 1, 1, 1},	/** < degree 1 */
-	{0x3, 0x3, 0x3, 0x3},	/** < degree 2 and so on... */
-	{0x5, 0x3, 0x5, 0x3},
-	{0x9, 0x3, 0x9, 0x3},
-	{0x9, 0x1b, 0xf, 0x5},
-	{0x21, 0x33, 0x1b, 0x2d},
-	{0x41, 0x11, 0x71, 0x9},
-	{0x71, 0xa9, 0xf5, 0x8d},
-	{0x21, 0xd1, 0x69, 0x1d9},
-	{0x81, 0x2c1, 0x3b1, 0x185},
-	{0x201, 0x541, 0x341, 0x461},
-	{0x941, 0x609, 0xe19, 0x45d},
-	{0x1601, 0x1f51, 0x1171, 0x359},
-	{0x2141, 0x2111, 0x2db1, 0x2109},
-	{0x4001, 0x801, 0x101, 0x7301},
-	{0x7781, 0xa011, 0x4211, 0x86d9},
-};
-
 struct thash_lfsr {
 	uint32_t	ref_cnt;
 	uint32_t	poly;
@@ -159,28 +132,21 @@ get_rev_bit_lfsr(struct thash_lfsr *lfsr)
 	return ret;
 }
 
-static inline uint32_t
-thash_get_rand_poly(uint32_t poly_degree)
-{
-	return irreducible_poly_table[poly_degree][rte_rand() %
-		RTE_DIM(irreducible_poly_table[poly_degree])];
-}
-
 static struct thash_lfsr *
-alloc_lfsr(struct rte_thash_ctx *ctx)
+alloc_lfsr(uint32_t poly_degree)
 {
 	struct thash_lfsr *lfsr;
 	uint32_t i;
 
-	if (ctx == NULL)
+	if ((poly_degree > 32) || (poly_degree == 0))
 		return NULL;
 
 	lfsr = rte_zmalloc(NULL, sizeof(struct thash_lfsr), 0);
 	if (lfsr == NULL)
 		return NULL;
 
-	lfsr->deg = ctx->reta_sz_log;
-	lfsr->poly = thash_get_rand_poly(lfsr->deg);
+	lfsr->deg = poly_degree;
+	lfsr->poly = rte_thash_get_rand_poly(lfsr->deg);
 	do {
 		lfsr->state = rte_rand() & ((1 << lfsr->deg) - 1);
 	} while (lfsr->state == 0);
@@ -460,7 +426,7 @@ insert_before(struct rte_thash_ctx *ctx,
 	int ret;
 
 	if (end < cur_ent->offset) {
-		ent->lfsr = alloc_lfsr(ctx);
+		ent->lfsr = alloc_lfsr(ctx->reta_sz_log);
 		if (ent->lfsr == NULL) {
 			rte_free(ent);
 			return -ENOMEM;
@@ -613,7 +579,7 @@ rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name, uint32_t len,
 		continue;
 	}
 
-	ent->lfsr = alloc_lfsr(ctx);
+	ent->lfsr = alloc_lfsr(ctx->reta_sz_log);
 	if (ent->lfsr == NULL) {
 		rte_free(ent);
 		return -ENOMEM;
diff --git a/lib/hash/rte_thash.h b/lib/hash/rte_thash.h
index ab534aea2f..943cdff390 100644
--- a/lib/hash/rte_thash.h
+++ b/lib/hash/rte_thash.h
@@ -108,6 +108,19 @@ union rte_thash_tuple {
 	struct rte_ipv6_tuple	v6;
 };
 
+/** @internal
+ *  @brief Generates a random polynomial
+ *
+ * @param poly_degree
+ *   degree of the polynomial
+ *
+ * @return
+ *   random polynomial
+ */
+__rte_internal
+uint32_t
+rte_thash_get_rand_poly(uint32_t poly_degree);
+
 /**
  * Prepare special converted key to use with rte_softrss_be()
  * @param orig
diff --git a/lib/hash/rte_thash_gf2_poly_math.c b/lib/hash/rte_thash_gf2_poly_math.c
new file mode 100644
index 0000000000..e6eb1ef3c5
--- /dev/null
+++ b/lib/hash/rte_thash_gf2_poly_math.c
@@ -0,0 +1,253 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2024 Intel Corporation
+ */
+#include <rte_random.h>
+#include <rte_common.h>
+#include <rte_bitops.h>
+#include <rte_debug.h>
+#include <rte_thash.h>
+
+#define MAX_TOEPLITZ_KEY_LENGTH 64
+
+/*
+ * Finite field math for field extensions with irreducing polynomial
+ * of degree <= 32.
+ * Polynomials are represented with 2 arguments - uint32_t poly and int degree.
+ * poly argument does not hold the highest degree coefficient,
+ * so full polynomial can be expressed as poly|(1ULL << degree).
+ * The algorithm to produce random irreducible polynomial was inspired by:
+ * "Computation in finite fields" by John Kerl, Chapter 10.4.
+ */
+
+static const uint32_t irreducible_poly_table[][3] = {
+	{0, 0, 0},		/* degree 0 */
+	{0x1, 0x1, 0x1},	/* degree 1 */
+	{0x3, 0x3, 0x3},	/* degree 2 and so on.. */
+	{0x3, 0x5, 0x3},	/* x^3+x^2+1(0x5) is reverted x^3+x+1(0x3) */
+	{0x3, 0x9, 0x3},	/* x^4+x^3+1(0x9) is reverted x^4+x+1(0x3) */
+	{0x5, 0xf, 0x17},	/* 0x5 <-> 0x9; 0xf <-> 0x1d; 0x17 <-> 0x1b */
+	{0x3, 0x27, 0x1b},	/* 0x3 <-> 0x21; 0x27 <-> 0x33; 0x1b <-> 0x2d*/
+};
+
+/*
+ * Table of the monic lowest weight irreducible polynomials over GF(2)
+ * starting from degree 7 up to degree 32.
+ * Taken from Handbook of Finite Fields by Gary L. Mullen and
+ * Daniel Penario p.33 Table 2.2.1.
+ * https://people.math.carleton.ca/~daniel/hff/irred/F2-2to10000.txt
+ */
+static const uint32_t default_irreducible_poly[] = {
+	0x3,    /* x^7 + x + 1*/
+	0x1b,   /* x^8 + x^4 + x^3 + x + 1 */
+	0x3,    /* x^9 + x + 1*/
+	0x9,    /* x^10 + x^3 + 1 */
+	0x5,    /* x^11 + x^2 + 1 */
+	0x9,    /* x^12 + x^3 + 1 */
+	0x1b,   /* x^13 + x^4 + x^3 + x + 1 */
+	0x33,   /* x^14 + x^5 + 1 */
+	0x3,    /* x^15 + x + 1 */
+	0x2b,   /* x^16 + x^5 + x^3 + x + 1 */
+	0x9,    /* x^17 + x^3 + 1 */
+	0x9,    /* x^18 + x^3 + 1 */
+	0x27,   /* x^19 + x^5 + x^2 + x + 1 */
+	0x9,    /* x^20 + x^3 + 1 */
+	0x5,    /* x^21 + x^2 + 1 */
+	0x3,    /* x^22 + x + 1 */
+	0x21,   /* x^23 + x^5 + 1 */
+	0x1b,   /* x^24 + x^4 + x^3 + x + 1 */
+	0x9,    /* x^25 + x^3 + 1 */
+	0x1b,   /* x^26 + x^4 + x^3 + x + 1 */
+	0x27,   /* x^27 + x^5 + x^2 + x + 1 */
+	0x3,    /* x^28 + x + 1 */
+	0x5,    /* x^29 + x^2 + 1 */
+	0x3,    /* x^30 + x + 1 */
+	0x9,    /* x^31 + x^3 + 1 */
+	0x8d,   /* x^32 + x^7 + x^3 + x^2 + 1 */
+};
+
+#define MAX_DIVISORS 28 /* 2^24 - 1 */
+
+struct divisors {
+	uint32_t n; /* number of divisors */
+	uint32_t div_arr[MAX_DIVISORS];
+};
+
+/* divisors of (2^n - 1) less than MIN(512, 2^n - 1) for all n in [7, 32] */
+static const struct divisors divisors[] = {
+	{ .n = 0, .div_arr = {} }, /* 2^7-1 is Mersenne prime */
+	{ .n = 6, .div_arr = {3, 5, 15, 17, 51, 85} },
+	{ .n = 2, .div_arr = {7, 73} },
+	{ .n = 6, .div_arr = {3, 11, 31, 33, 93, 341} },
+	{ .n = 2, .div_arr = {23, 89} },
+	{ .n = 19, .div_arr = {3, 5, 7, 9, 13, 15, 21, 35, 39, 45, 63, 65, 91,
+		105, 117, 195, 273, 315, 455} },
+	{ .n = 0, .div_arr = {} }, /* 2^13-1 is Mersenne prime */
+	{ .n = 5, .div_arr = {3, 43, 127, 129, 381} },
+	{ .n = 4, .div_arr = {7, 31, 151, 217} },
+	{ .n = 8, .div_arr = {3, 5, 15, 17, 51, 85, 255, 257} },
+	{ .n = 0, .div_arr = {} }, /* 2^17-1 is Mersenne prime */
+	{ .n = 14, .div_arr = {3, 7, 9, 19, 21, 27, 57, 63, 73, 133, 171, 189,
+		219, 399} },
+	{ .n = 0, .div_arr = {0} }, /* 2^19-1 is Mersenne prime */
+	{ .n = 19, .div_arr = {3, 5, 11, 15, 25, 31, 33, 41, 55, 75, 93, 123,
+		155, 165, 205, 275, 341, 451, 465} },
+	{ .n = 4, .div_arr = {7, 49, 127, 337} },
+	{ .n = 5, .div_arr = {3, 23, 69, 89, 267} },
+	{ .n = 1, .div_arr = {47} },
+	{ .n = 28, .div_arr = {3, 5, 7, 9, 13, 15, 17, 21, 35, 39, 45, 51, 63,
+		65, 85, 91, 105, 117, 119, 153, 195, 221, 241, 255, 273, 315,
+		357, 455} },
+	{ .n = 1, .div_arr = {31} },
+	{ .n = 1, .div_arr = {3} },
+	{ .n = 2, .div_arr = {7, 73} },
+	{ .n = 14, .div_arr = {3, 5, 15, 29, 43, 87, 113, 127, 129, 145, 215,
+		339, 381, 435} },
+	{ .n = 1, .div_arr = {233} },
+	{ .n = 18, .div_arr = {3, 7, 9, 11, 21, 31, 33, 63, 77, 93, 99, 151,
+		217, 231, 279, 331, 341, 453} },
+	{ .n = 0, .div_arr = {} },/* 2^31-1 is Mersenne prime */
+	{ .n = 8, .div_arr = {3, 5, 15, 17, 51, 85, 255, 257} },
+};
+
+static uint32_t
+gf2_mul(uint32_t a, uint32_t b, uint32_t r, int degree)
+{
+	uint64_t product = 0;
+	uint64_t r_poly = r|(1ULL << degree);
+
+	for (; b; b &= (b - 1))
+		product ^= (uint64_t)a << (rte_bsf32(b));
+
+	for (int i = degree * 2 - 1; i >= degree; i--)
+		if (product & (1 << i))
+			product ^= r_poly << (i - degree);
+
+	return product;
+}
+
+static uint32_t
+gf2_pow(uint32_t a, uint32_t pow, uint32_t r, int degree)
+{
+	uint32_t result = 1;
+	unsigned int i;
+
+	for (i = 0; i < (sizeof(pow)*CHAR_BIT - rte_clz32(pow)); i++) {
+		if (pow & (1 << i))
+			result = gf2_mul(result, a, r, degree);
+
+		a = gf2_mul(a, a, r, degree);
+	}
+
+	return result;
+}
+
+static uint32_t
+__thash_get_rand_poly(int poly_degree)
+{
+	uint32_t roots[poly_degree];
+	uint32_t rnd;
+	uint32_t ret_poly = 0;
+	int i, j;
+	bool short_orbit = false;
+
+	/* special case for low degree */
+	if (poly_degree < 7)
+		return irreducible_poly_table[poly_degree][rte_rand() %
+			RTE_DIM(irreducible_poly_table[poly_degree])];
+
+	uint32_t r = default_irreducible_poly[poly_degree - 7];
+
+	do {
+		short_orbit = false;
+		do {
+			rnd = rte_rand() & ((1 << poly_degree) - 1);
+		} while ((rnd == 0) || (rnd == 1));
+
+		/*
+		 * Quick check if random returned one of the roots of
+		 * the initial polynomial.
+		 * In other words if we randomy got x, x^2, x^4, x^8 or x^16
+		 */
+#define ROOT_POLY_MSK ((1 << 1)|(1 << 2)|(1 << 4)|(1 << 8)|(1 << 16))
+		if ((rte_popcount32(rnd) == 1) && (rnd & ROOT_POLY_MSK))
+			return default_irreducible_poly[poly_degree - 7];
+
+		/*
+		 * init array with some random polynomial roots
+		 * applying Frobenius automorphism (i.e. squaring them)
+		 * also checking for short orbits (i.e. if there are repeated roots)
+		 */
+		roots[0] = rnd;
+		for (i = 1; i < poly_degree; i++) {
+			roots[i] = gf2_pow(roots[i - 1], 2, r, poly_degree);
+			if (roots[i] == roots[0])
+				short_orbit = true;
+		}
+	} while (short_orbit);
+
+	/*
+	 * Get coefficients of the polynomial for
+	 * (x - roots[0])(x - roots[1])...(x - roots[n])
+	 */
+	uint32_t poly_coefficients[poly_degree + 1];
+	for (i = 0; i <= poly_degree; i++)
+		poly_coefficients[i] = 0;
+
+	poly_coefficients[0] = 1; /* highest degree term coefficient in the end */
+	for (i = 0; i < (int)poly_degree; i++) {
+		/* multiply by x */
+		for (j = i; j >= 0; j--)
+			poly_coefficients[j + 1] = poly_coefficients[j];
+
+		poly_coefficients[0] = 0;
+
+		/* multiply by root */
+		for (j = 0; j <= i; j++)
+			poly_coefficients[j] ^=
+				gf2_mul(poly_coefficients[j + 1],
+				roots[i], r, poly_degree);
+	}
+
+	for (i = 0; i < poly_degree; i++) {
+		if (poly_coefficients[i]) {
+			RTE_ASSERT(poly_coefficients[i] == 1);
+			ret_poly |= 1 << i;
+		}
+	}
+
+	return ret_poly;
+}
+
+/* test an order of the multiplicative subgroup generated by x */
+static int
+thash_test_poly_order(uint32_t poly, int degree)
+{
+	unsigned int i;
+	int div_idx = degree - 7;
+
+	if (degree < 7)
+		return 0;
+
+	for (i = 0; i < divisors[div_idx].n; i++) {
+		if (gf2_pow(0x2, divisors[div_idx].div_arr[i],
+				poly, degree) == 1)
+			return 1;
+	}
+
+	return 0;
+}
+
+uint32_t
+rte_thash_get_rand_poly(uint32_t poly_degree)
+{
+	uint32_t ret_poly;
+
+	if (poly_degree > 32)
+		return 0;
+
+	do
+		ret_poly = __thash_get_rand_poly(poly_degree);
+	while (thash_test_poly_order(ret_poly, poly_degree));
+
+	return ret_poly;
+}
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 4f13f1d5aa..7ce6ab1121 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -61,4 +61,5 @@ INTERNAL {
 
 	rte_thash_gfni_stub;
 	rte_thash_gfni_bulk_stub;
+	rte_thash_get_rand_poly;
 };
-- 
2.43.0