1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2024 Intel Corporation 3 */ 4 #include <rte_random.h> 5 #include <rte_common.h> 6 #include <rte_bitops.h> 7 #include <rte_debug.h> 8 #include <rte_thash.h> 9 #include <rte_log.h> 10 11 #define MAX_TOEPLITZ_KEY_LENGTH 64 12 RTE_LOG_REGISTER_SUFFIX(thash_poly_logtype, thash_poly, INFO); 13 #define RTE_LOGTYPE_HASH thash_poly_logtype 14 #define HASH_LOG(level, ...) \ 15 RTE_LOG_LINE(level, HASH, "" __VA_ARGS__) 16 17 /* 18 * Finite field math for field extensions with irreducing polynomial 19 * of degree <= 32. 20 * Polynomials are represented with 2 arguments - uint32_t poly and int degree. 21 * poly argument does not hold the highest degree coefficient, 22 * so full polynomial can be expressed as poly|(1ULL << degree). 23 * The algorithm to produce random irreducible polynomial was inspired by: 24 * "Computation in finite fields" by John Kerl, Chapter 10.4. 25 */ 26 27 static const uint32_t irreducible_poly_table[][3] = { 28 {0, 0, 0}, /* degree 0 */ 29 {0x1, 0x1, 0x1}, /* degree 1 */ 30 {0x3, 0x3, 0x3}, /* degree 2 and so on.. */ 31 {0x3, 0x5, 0x3}, /* x^3+x^2+1(0x5) is reverted x^3+x+1(0x3) */ 32 {0x3, 0x9, 0x3}, /* x^4+x^3+1(0x9) is reverted x^4+x+1(0x3) */ 33 {0x5, 0xf, 0x17}, /* 0x5 <-> 0x9; 0xf <-> 0x1d; 0x17 <-> 0x1b */ 34 {0x3, 0x27, 0x1b}, /* 0x3 <-> 0x21; 0x27 <-> 0x33; 0x1b <-> 0x2d*/ 35 }; 36 37 /* 38 * Table of the monic lowest weight irreducible polynomials over GF(2) 39 * starting from degree 7 up to degree 32. 40 * Taken from Handbook of Finite Fields by Gary L. Mullen and 41 * Daniel Penario p.33 Table 2.2.1. 42 * https://people.math.carleton.ca/~daniel/hff/irred/F2-2to10000.txt 43 */ 44 static const uint32_t default_irreducible_poly[] = { 45 0x3, /* x^7 + x + 1*/ 46 0x1b, /* x^8 + x^4 + x^3 + x + 1 */ 47 0x3, /* x^9 + x + 1*/ 48 0x9, /* x^10 + x^3 + 1 */ 49 0x5, /* x^11 + x^2 + 1 */ 50 0x9, /* x^12 + x^3 + 1 */ 51 0x1b, /* x^13 + x^4 + x^3 + x + 1 */ 52 0x33, /* x^14 + x^5 + 1 */ 53 0x3, /* x^15 + x + 1 */ 54 0x2b, /* x^16 + x^5 + x^3 + x + 1 */ 55 0x9, /* x^17 + x^3 + 1 */ 56 0x9, /* x^18 + x^3 + 1 */ 57 0x27, /* x^19 + x^5 + x^2 + x + 1 */ 58 0x9, /* x^20 + x^3 + 1 */ 59 0x5, /* x^21 + x^2 + 1 */ 60 0x3, /* x^22 + x + 1 */ 61 0x21, /* x^23 + x^5 + 1 */ 62 0x1b, /* x^24 + x^4 + x^3 + x + 1 */ 63 0x9, /* x^25 + x^3 + 1 */ 64 0x1b, /* x^26 + x^4 + x^3 + x + 1 */ 65 0x27, /* x^27 + x^5 + x^2 + x + 1 */ 66 0x3, /* x^28 + x + 1 */ 67 0x5, /* x^29 + x^2 + 1 */ 68 0x3, /* x^30 + x + 1 */ 69 0x9, /* x^31 + x^3 + 1 */ 70 0x8d, /* x^32 + x^7 + x^3 + x^2 + 1 */ 71 }; 72 73 #define MAX_DIVISORS 28 /* 2^24 - 1 */ 74 75 struct divisors { 76 uint32_t n; /* number of divisors */ 77 uint32_t div_arr[MAX_DIVISORS]; 78 }; 79 80 /* divisors of (2^n - 1) less than MIN(512, 2^n - 1) for all n in [7, 32] */ 81 static const struct divisors divisors[] = { 82 { .n = 0, .div_arr = {} }, /* 2^7-1 is Mersenne prime */ 83 { .n = 6, .div_arr = {3, 5, 15, 17, 51, 85} }, 84 { .n = 2, .div_arr = {7, 73} }, 85 { .n = 6, .div_arr = {3, 11, 31, 33, 93, 341} }, 86 { .n = 2, .div_arr = {23, 89} }, 87 { .n = 19, .div_arr = {3, 5, 7, 9, 13, 15, 21, 35, 39, 45, 63, 65, 91, 88 105, 117, 195, 273, 315, 455} }, 89 { .n = 0, .div_arr = {} }, /* 2^13-1 is Mersenne prime */ 90 { .n = 5, .div_arr = {3, 43, 127, 129, 381} }, 91 { .n = 4, .div_arr = {7, 31, 151, 217} }, 92 { .n = 8, .div_arr = {3, 5, 15, 17, 51, 85, 255, 257} }, 93 { .n = 0, .div_arr = {} }, /* 2^17-1 is Mersenne prime */ 94 { .n = 14, .div_arr = {3, 7, 9, 19, 21, 27, 57, 63, 73, 133, 171, 189, 95 219, 399} }, 96 { .n = 0, .div_arr = {0} }, /* 2^19-1 is Mersenne prime */ 97 { .n = 19, .div_arr = {3, 5, 11, 15, 25, 31, 33, 41, 55, 75, 93, 123, 98 155, 165, 205, 275, 341, 451, 465} }, 99 { .n = 4, .div_arr = {7, 49, 127, 337} }, 100 { .n = 5, .div_arr = {3, 23, 69, 89, 267} }, 101 { .n = 1, .div_arr = {47} }, 102 { .n = 28, .div_arr = {3, 5, 7, 9, 13, 15, 17, 21, 35, 39, 45, 51, 63, 103 65, 85, 91, 105, 117, 119, 153, 195, 221, 241, 255, 273, 315, 104 357, 455} }, 105 { .n = 1, .div_arr = {31} }, 106 { .n = 1, .div_arr = {3} }, 107 { .n = 2, .div_arr = {7, 73} }, 108 { .n = 14, .div_arr = {3, 5, 15, 29, 43, 87, 113, 127, 129, 145, 215, 109 339, 381, 435} }, 110 { .n = 1, .div_arr = {233} }, 111 { .n = 18, .div_arr = {3, 7, 9, 11, 21, 31, 33, 63, 77, 93, 99, 151, 112 217, 231, 279, 331, 341, 453} }, 113 { .n = 0, .div_arr = {} },/* 2^31-1 is Mersenne prime */ 114 { .n = 8, .div_arr = {3, 5, 15, 17, 51, 85, 255, 257} }, 115 }; 116 117 static uint32_t 118 gf2_mul(uint32_t a, uint32_t b, uint32_t r, int degree) 119 { 120 uint64_t product = 0; 121 uint64_t r_poly = r|(1ULL << degree); 122 123 for (; b; b &= (b - 1)) 124 product ^= (uint64_t)a << (rte_bsf32(b)); 125 126 for (int i = degree * 2 - 1; i >= degree; i--) 127 if (product & (1 << i)) 128 product ^= r_poly << (i - degree); 129 130 return product; 131 } 132 133 static uint32_t 134 gf2_pow(uint32_t a, uint32_t pow, uint32_t r, int degree) 135 { 136 uint32_t result = 1; 137 unsigned int i; 138 139 for (i = 0; i < (sizeof(pow)*CHAR_BIT - rte_clz32(pow)); i++) { 140 if (pow & (1 << i)) 141 result = gf2_mul(result, a, r, degree); 142 143 a = gf2_mul(a, a, r, degree); 144 } 145 146 return result; 147 } 148 149 static uint32_t 150 __thash_get_rand_poly(int poly_degree) 151 { 152 uint32_t roots[poly_degree]; 153 uint32_t rnd; 154 uint32_t ret_poly = 0; 155 int i, j; 156 bool short_orbit = false; 157 158 /* special case for low degree */ 159 if (poly_degree < 7) 160 return irreducible_poly_table[poly_degree][rte_rand() % 161 RTE_DIM(irreducible_poly_table[poly_degree])]; 162 163 uint32_t r = default_irreducible_poly[poly_degree - 7]; 164 165 do { 166 short_orbit = false; 167 do { 168 rnd = rte_rand() & ((1 << poly_degree) - 1); 169 } while ((rnd == 0) || (rnd == 1)); 170 171 /* 172 * Quick check if random returned one of the roots of 173 * the initial polynomial. 174 * In other words if we randomy got x, x^2, x^4, x^8 or x^16 175 */ 176 #define ROOT_POLY_MSK ((1 << 1)|(1 << 2)|(1 << 4)|(1 << 8)|(1 << 16)) 177 if ((rte_popcount32(rnd) == 1) && (rnd & ROOT_POLY_MSK)) 178 return default_irreducible_poly[poly_degree - 7]; 179 180 /* 181 * init array with some random polynomial roots 182 * applying Frobenius automorphism (i.e. squaring them) 183 * also checking for short orbits (i.e. if there are repeated roots) 184 */ 185 roots[0] = rnd; 186 for (i = 1; i < poly_degree; i++) { 187 roots[i] = gf2_pow(roots[i - 1], 2, r, poly_degree); 188 if (roots[i] == roots[0]) 189 short_orbit = true; 190 } 191 } while (short_orbit); 192 193 /* 194 * Get coefficients of the polynomial for 195 * (x - roots[0])(x - roots[1])...(x - roots[n]) 196 */ 197 uint32_t poly_coefficients[poly_degree + 1]; 198 for (i = 0; i <= poly_degree; i++) 199 poly_coefficients[i] = 0; 200 201 poly_coefficients[0] = 1; /* highest degree term coefficient in the end */ 202 for (i = 0; i < (int)poly_degree; i++) { 203 /* multiply by x */ 204 for (j = i; j >= 0; j--) 205 poly_coefficients[j + 1] = poly_coefficients[j]; 206 207 poly_coefficients[0] = 0; 208 209 /* multiply by root */ 210 for (j = 0; j <= i; j++) 211 poly_coefficients[j] ^= 212 gf2_mul(poly_coefficients[j + 1], 213 roots[i], r, poly_degree); 214 } 215 216 for (i = 0; i < poly_degree; i++) { 217 if (poly_coefficients[i]) { 218 RTE_ASSERT(poly_coefficients[i] == 1); 219 ret_poly |= 1 << i; 220 } 221 } 222 223 return ret_poly; 224 } 225 226 /* test an order of the multiplicative subgroup generated by x */ 227 static int 228 thash_test_poly_order(uint32_t poly, int degree) 229 { 230 unsigned int i; 231 int div_idx = degree - 7; 232 233 if (degree < 7) 234 return 0; 235 236 for (i = 0; i < divisors[div_idx].n; i++) { 237 if (gf2_pow(0x2, divisors[div_idx].div_arr[i], 238 poly, degree) == 1) 239 return 1; 240 } 241 242 return 0; 243 } 244 245 uint32_t 246 thash_get_rand_poly(uint32_t poly_degree) 247 { 248 uint32_t ret_poly; 249 250 if (poly_degree > 32) { 251 HASH_LOG(ERR, "Wrong polynomial degree %d, must be in range [1, 32]", poly_degree); 252 return 0; 253 } 254 255 do 256 ret_poly = __thash_get_rand_poly(poly_degree); 257 while (thash_test_poly_order(ret_poly, poly_degree)); 258 259 return ret_poly; 260 } 261