vppinfra: toeplitz hash four in parallel

Type: improvement
Change-Id: Icb3f39f42d01c51d7b03543cb7d6b5dabad11866
Signed-off-by: Damjan Marion <dmarion@me.com>

diff --git a/src/vppinfra/clib.h b/src/vppinfra/clib.h
index 52e7217..50f04e1 100644 (file)
--- a/src/vppinfra/clib.h
+++ b/src/vppinfra/clib.h
@@ -100,6 +100,7 @@
 #define __clib_packed __attribute__ ((packed))
 #define __clib_constructor __attribute__ ((constructor))
 #define __clib_noinline __attribute__ ((noinline))
+#define __clib_noclone           __attribute__ ((noclone))
 #define __clib_aligned(x) __attribute__ ((aligned(x)))
 #define __clib_section(s) __attribute__ ((section(s)))
 #define __clib_warn_unused_result __attribute__ ((warn_unused_result))

diff --git a/src/vppinfra/vector/test/test.h b/src/vppinfra/vector/test/test.h
index 4334dfa..4511bf3 100644 (file)
--- a/src/vppinfra/vector/test/test.h
+++ b/src/vppinfra/vector/test/test.h
@@ -59,8 +59,10 @@ typedef struct
 } test_main_t;
 extern test_main_t test_main;
 
-#define __test_funct_fn static __clib_noinline __clib_section (".test_func")
-#define __test_perf_fn static __clib_noinline __clib_section (".test_perf")
+#define __test_funct_fn                                                       \
+  static __clib_noinline __clib_noclone __clib_section (".test_func")
+#define __test_perf_fn                                                        \
+  static __clib_noinline __clib_noclone __clib_section (".test_perf")
 
 #define REGISTER_TEST(x)                                                      \
   test_registration_t CLIB_MARCH_SFX (__test_##x);                            \

diff --git a/src/vppinfra/vector/test/toeplitz.c b/src/vppinfra/vector/test/toeplitz.c
index 0efc423..d425a44 100644 (file)
--- a/src/vppinfra/vector/test/toeplitz.c
+++ b/src/vppinfra/vector/test/toeplitz.c
@@ -175,6 +175,13 @@ wrapper (clib_toeplitz_hash_key_t *k, u8 *data, u32 n_bytes)
   return clib_toeplitz_hash (k, data, n_bytes);
 }
 
+__test_funct_fn void
+wrapper_x4 (clib_toeplitz_hash_key_t *k, u8 *d0, u8 *d1, u8 *d2, u8 *d3,
+           u32 *h0, u32 *h1, u32 *h2, u32 *h3, u32 n_bytes)
+{
+  clib_toeplitz_hash_x4 (k, d0, d1, d2, d3, h0, h1, h2, h3, n_bytes);
+}
+
 static clib_error_t *
 test_clib_toeplitz_hash (clib_error_t *err)
 {
@@ -222,16 +229,10 @@ test_clib_toeplitz_hash (clib_error_t *err)
   n_key_copies = 6;
   bigkey_len = k->key_length * n_key_copies;
   bigdata_len = bigkey_len - 4;
-  bigkey = clib_mem_alloc (bigkey_len);
-  bigdata = clib_mem_alloc (bigdata_len);
+  bigkey = test_mem_alloc_and_splat (k->key_length, n_key_copies, k->data);
+  bigdata = test_mem_alloc_and_fill_inc_u8 (bigdata_len, 0, 0);
   u32 key_len = k->key_length;
 
-  for (int i = 0; i < n_key_copies; i++)
-    clib_memcpy (bigkey + i * key_len, k->data, key_len);
-
-  for (int i = 0; i < bigdata_len; i++)
-    bigdata[i] = (u8) i;
-
   clib_toeplitz_hash_key_free (k);
   k = clib_toeplitz_hash_key_init (bigkey, n_key_copies * key_len);
 
@@ -252,8 +253,8 @@ test_clib_toeplitz_hash (clib_error_t *err)
 
 done:
   clib_toeplitz_hash_key_free (k);
-  clib_mem_free (bigkey);
-  clib_mem_free (bigdata);
+  test_mem_free (bigkey);
+  test_mem_free (bigdata);
   return err;
 }
 
@@ -334,3 +335,225 @@ REGISTER_TEST (clib_toeplitz_hash) = {
                              .n_ops = 16384,
                              .fn = perftest_variable_size }),
 };
+
+static clib_error_t *
+test_clib_toeplitz_hash_x4 (clib_error_t *err)
+{
+  u32 r[4];
+  int n_key_copies, bigkey_len, bigdata_len;
+  u8 *bigkey, *bigdata0, *bigdata1, *bigdata2, *bigdata3;
+  clib_toeplitz_hash_key_t *k;
+
+  k = clib_toeplitz_hash_key_init (0, 0);
+
+  wrapper_x4 (k, (u8 *) &ip4_tests[0].key, (u8 *) &ip4_tests[1].key,
+             (u8 *) &ip4_tests[2].key, (u8 *) &ip4_tests[3].key, r, r + 1,
+             r + 2, r + 3, 8);
+
+  if (ip4_tests[0].hash_2t != r[0] || ip4_tests[1].hash_2t != r[1] ||
+      ip4_tests[2].hash_2t != r[2] || ip4_tests[3].hash_2t != r[3])
+    return clib_error_return (err,
+                             "wrong IPv4 2 tuple x4 hash "
+                             "calculated { 0x%08x, 0x%08x, 0x%08x, 0x%08x } "
+                             "expected { 0x%08x, 0x%08x, 0x%08x, 0x%08x }",
+                             ip4_tests[0].hash_2t, ip4_tests[1].hash_2t,
+                             ip4_tests[2].hash_2t, ip4_tests[3].hash_2t, r[0],
+                             r[1], r[2], r[3]);
+
+  wrapper_x4 (k, (u8 *) &ip4_tests[0].key, (u8 *) &ip4_tests[1].key,
+             (u8 *) &ip4_tests[2].key, (u8 *) &ip4_tests[3].key, r, r + 1,
+             r + 2, r + 3, 12);
+
+  if (ip4_tests[0].hash_4t != r[0] || ip4_tests[1].hash_4t != r[1] ||
+      ip4_tests[2].hash_4t != r[2] || ip4_tests[3].hash_4t != r[3])
+    return clib_error_return (err,
+                             "wrong IPv4 4 tuple x4 hash "
+                             "calculated { 0x%08x, 0x%08x, 0x%08x, 0x%08x } "
+                             "expected { 0x%08x, 0x%08x, 0x%08x, 0x%08x }",
+                             ip4_tests[0].hash_4t, ip4_tests[1].hash_4t,
+                             ip4_tests[2].hash_4t, ip4_tests[3].hash_4t, r[0],
+                             r[1], r[2], r[3]);
+
+  wrapper_x4 (k, (u8 *) &ip6_tests[0].key, (u8 *) &ip6_tests[1].key,
+             (u8 *) &ip6_tests[2].key, (u8 *) &ip6_tests[0].key, r, r + 1,
+             r + 2, r + 3, 32);
+
+  if (ip6_tests[0].hash_2t != r[0] || ip6_tests[1].hash_2t != r[1] ||
+      ip6_tests[2].hash_2t != r[2] || ip6_tests[0].hash_2t != r[3])
+    return clib_error_return (err,
+                             "wrong IPv6 2 tuple x4 hash "
+                             "calculated { 0x%08x, 0x%08x, 0x%08x, 0x%08x } "
+                             "expected { 0x%08x, 0x%08x, 0x%08x, 0x%08x }",
+                             ip6_tests[0].hash_2t, ip6_tests[1].hash_2t,
+                             ip6_tests[2].hash_2t, ip6_tests[0].hash_2t, r[0],
+                             r[1], r[2], r[3]);
+
+  wrapper_x4 (k, (u8 *) &ip6_tests[0].key, (u8 *) &ip6_tests[1].key,
+             (u8 *) &ip6_tests[2].key, (u8 *) &ip6_tests[0].key, r, r + 1,
+             r + 2, r + 3, 36);
+
+  if (ip6_tests[0].hash_4t != r[0] || ip6_tests[1].hash_4t != r[1] ||
+      ip6_tests[2].hash_4t != r[2] || ip6_tests[0].hash_4t != r[3])
+    return clib_error_return (err,
+                             "wrong IPv6 4 tuple x4 hash "
+                             "calculated { 0x%08x, 0x%08x, 0x%08x, 0x%08x } "
+                             "expected { 0x%08x, 0x%08x, 0x%08x, 0x%08x }",
+                             ip6_tests[0].hash_4t, ip6_tests[1].hash_4t,
+                             ip6_tests[2].hash_4t, ip6_tests[0].hash_4t, r[0],
+                             r[1], r[2], r[3]);
+
+  n_key_copies = 6;
+  bigkey_len = k->key_length * n_key_copies;
+  bigdata_len = bigkey_len - 4;
+  bigkey = test_mem_alloc_and_splat (k->key_length, n_key_copies, k->data);
+  bigdata0 = test_mem_alloc_and_fill_inc_u8 (bigdata_len, 0, 0);
+  bigdata1 = test_mem_alloc_and_fill_inc_u8 (bigdata_len, 0, 0);
+  bigdata2 = test_mem_alloc_and_fill_inc_u8 (bigdata_len, 0, 0);
+  bigdata3 = test_mem_alloc_and_fill_inc_u8 (bigdata_len, 0, 0);
+  u32 key_len = k->key_length;
+
+  clib_toeplitz_hash_key_free (k);
+  k = clib_toeplitz_hash_key_init (bigkey, n_key_copies * key_len);
+
+  for (int i = 0; i < N_LENGTH_TESTS - 4; i++)
+    {
+      wrapper_x4 (k, bigdata0, bigdata1, bigdata2, bigdata3, r, r + 1, r + 2,
+                 r + 3, i);
+      if (length_test_hashes[i] != r[0] || length_test_hashes[i] != r[1] ||
+         length_test_hashes[i] != r[2] || length_test_hashes[i] != r[3])
+       {
+         err = clib_error_return (
+           err,
+           "wrong length test hash x4 for length %u, "
+           "calculated { 0x%08x, 0x%08x, 0x%08x, 0x%08x }, expected 0x%08x",
+           i, r[0], r[1], r[2], r[3], length_test_hashes[i]);
+         goto done;
+       }
+    }
+
+done:
+  clib_toeplitz_hash_key_free (k);
+  test_mem_free (bigkey);
+  test_mem_free (bigdata0);
+  test_mem_free (bigdata1);
+  test_mem_free (bigdata2);
+  test_mem_free (bigdata3);
+  return err;
+}
+
+void __test_perf_fn
+perftest_fixed_12byte_x4 (int fd, test_perf_t *tp)
+{
+  u32 n = tp->n_ops / 4;
+  u8 *d0 = test_mem_alloc_and_splat (12, n, (void *) &ip4_tests[0].key);
+  u8 *d1 = test_mem_alloc_and_splat (12, n, (void *) &ip4_tests[1].key);
+  u8 *d2 = test_mem_alloc_and_splat (12, n, (void *) &ip4_tests[2].key);
+  u8 *d3 = test_mem_alloc_and_splat (12, n, (void *) &ip4_tests[3].key);
+  u32 *h0 = test_mem_alloc (4 * n);
+  u32 *h1 = test_mem_alloc (4 * n);
+  u32 *h2 = test_mem_alloc (4 * n);
+  u32 *h3 = test_mem_alloc (4 * n);
+  clib_toeplitz_hash_key_t *k = clib_toeplitz_hash_key_init (0, 0);
+
+  test_perf_event_enable (fd);
+  for (int i = 0; i < n; i++)
+    clib_toeplitz_hash_x4 (k, d0 + i * 12, d1 + i * 12, d2 + i * 12,
+                          d3 + i * 12, h0 + i, h1 + i, h2 + i, h3 + i, 12);
+  test_perf_event_disable (fd);
+
+  clib_toeplitz_hash_key_free (k);
+  test_mem_free (d0);
+  test_mem_free (d1);
+  test_mem_free (d2);
+  test_mem_free (d3);
+  test_mem_free (h0);
+  test_mem_free (h1);
+  test_mem_free (h2);
+  test_mem_free (h3);
+}
+
+void __test_perf_fn
+perftest_fixed_36byte_x4 (int fd, test_perf_t *tp)
+{
+  u32 n = tp->n_ops / 4;
+  u8 *d0 = test_mem_alloc_and_splat (36, n, (void *) &ip4_tests[0].key);
+  u8 *d1 = test_mem_alloc_and_splat (36, n, (void *) &ip4_tests[1].key);
+  u8 *d2 = test_mem_alloc_and_splat (36, n, (void *) &ip4_tests[2].key);
+  u8 *d3 = test_mem_alloc_and_splat (36, n, (void *) &ip4_tests[3].key);
+  u32 *h0 = test_mem_alloc (4 * n);
+  u32 *h1 = test_mem_alloc (4 * n);
+  u32 *h2 = test_mem_alloc (4 * n);
+  u32 *h3 = test_mem_alloc (4 * n);
+  clib_toeplitz_hash_key_t *k = clib_toeplitz_hash_key_init (0, 0);
+
+  test_perf_event_enable (fd);
+  for (int i = 0; i < n; i++)
+    clib_toeplitz_hash_x4 (k, d0 + i * 36, d1 + i * 36, d2 + i * 36,
+                          d3 + i * 36, h0 + i, h1 + i, h2 + i, h3 + i, 36);
+  test_perf_event_disable (fd);
+
+  clib_toeplitz_hash_key_free (k);
+  test_mem_free (d0);
+  test_mem_free (d1);
+  test_mem_free (d2);
+  test_mem_free (d3);
+  test_mem_free (h0);
+  test_mem_free (h1);
+  test_mem_free (h2);
+  test_mem_free (h3);
+}
+
+void __test_perf_fn
+perftest_variable_size_x4 (int fd, test_perf_t *tp)
+{
+  u32 key_len, n_keys, n = tp->n_ops / 4;
+  u8 *key;
+  u8 *d0 = test_mem_alloc (n);
+  u8 *d1 = test_mem_alloc (n);
+  u8 *d2 = test_mem_alloc (n);
+  u8 *d3 = test_mem_alloc (n);
+  u32 *h0 = test_mem_alloc (sizeof (u32));
+  u32 *h1 = test_mem_alloc (sizeof (u32));
+  u32 *h2 = test_mem_alloc (sizeof (u32));
+  u32 *h3 = test_mem_alloc (sizeof (u32));
+  clib_toeplitz_hash_key_t *k = clib_toeplitz_hash_key_init (0, 0);
+
+  k = clib_toeplitz_hash_key_init (0, 0);
+  key_len = k->key_length;
+  n_keys = ((n + 4) / k->key_length) + 1;
+  key = test_mem_alloc_and_splat (n_keys, key_len, k->data);
+  clib_toeplitz_hash_key_free (k);
+  k = clib_toeplitz_hash_key_init (key, key_len * n_keys);
+
+  test_perf_event_enable (fd);
+  clib_toeplitz_hash_x4 (k, d0, d1, d2, d3, h0, h1, h2, h3, n);
+  test_perf_event_disable (fd);
+
+  clib_toeplitz_hash_key_free (k);
+  test_mem_free (key);
+  test_mem_free (d0);
+  test_mem_free (d1);
+  test_mem_free (d2);
+  test_mem_free (d3);
+  test_mem_free (h0);
+  test_mem_free (h1);
+  test_mem_free (h2);
+  test_mem_free (h3);
+}
+
+REGISTER_TEST (clib_toeplitz_hash_x4) = {
+  .name = "clib_toeplitz_hash_x4",
+  .fn = test_clib_toeplitz_hash_x4,
+  .perf_tests = PERF_TESTS ({ .name = "fixed_12",
+                             .op_name = "12B Tuple",
+                             .n_ops = 1024,
+                             .fn = perftest_fixed_12byte_x4 },
+                           { .name = "fixed_36",
+                             .op_name = "36B Tuple",
+                             .n_ops = 1024,
+                             .fn = perftest_fixed_36byte_x4 },
+                           { .name = "variable_size",
+                             .op_name = "Byte",
+                             .n_ops = 16384,
+                             .fn = perftest_variable_size_x4 }),
+};

diff --git a/src/vppinfra/vector/toeplitz.h b/src/vppinfra/vector/toeplitz.h
index a199a4d..76297f0 100644 (file)
--- a/src/vppinfra/vector/toeplitz.h
+++ b/src/vppinfra/vector/toeplitz.h
@@ -16,13 +16,6 @@ typedef struct
 clib_toeplitz_hash_key_t *clib_toeplitz_hash_key_init (u8 *key, u32 keylen);
 void clib_toeplitz_hash_key_free (clib_toeplitz_hash_key_t *k);
 
-#if defined(__GFNI__) && defined(__AVX512F__)
-
-#define u64x8_gf2p8_affine(d, m, imm)                                         \
-  (u64x8) _mm512_gf2p8affine_epi64_epi8 ((__m512i) (d), (__m512i) (m), imm)
-
-#endif
-
 #ifdef CLIB_HAVE_VEC256
 static_always_inline u32x8
 toeplitz_hash_one_x8 (u32x8 hash, u64x4 v4, u8 data, u8 off)
@@ -40,6 +33,58 @@ toeplitz_hash_one_x8 (u32x8 hash, u64x4 v4, u8 data, u8 off)
 }
 #endif
 
+#if defined(__GFNI__) && defined(__AVX512F__)
+static const u8x64 __clib_toeplitz_hash_gfni_permute = {
+  /* clang-format off */
+  0x00, 0x01, 0x02, 0x03, 0x40, 0x41, 0x42, 0x43,
+  0x01, 0x02, 0x03, 0x04, 0x41, 0x42, 0x43, 0x44,
+  0x02, 0x03, 0x04, 0x05, 0x42, 0x43, 0x44, 0x45,
+  0x03, 0x04, 0x05, 0x06, 0x43, 0x44, 0x45, 0x46,
+  0x04, 0x05, 0x06, 0x07, 0x44, 0x45, 0x46, 0x47,
+  0x05, 0x06, 0x07, 0x08, 0x45, 0x46, 0x47, 0x48,
+  0x06, 0x07, 0x08, 0x09, 0x46, 0x47, 0x48, 0x49,
+  0x07, 0x08, 0x09, 0x0a, 0x47, 0x48, 0x49, 0x4a
+  /* clang-format on */
+};
+static_always_inline u64x8
+clib_toeplitz_hash_gfni_one (u8x64 d0, u64x8 m, int i)
+{
+
+  d0 = i == 1 ? (u8x64) u64x8_align_right (d0, d0, 1) : d0;
+  d0 = i == 2 ? (u8x64) u64x8_align_right (d0, d0, 2) : d0;
+  d0 = i == 3 ? (u8x64) u64x8_align_right (d0, d0, 3) : d0;
+  d0 = i == 4 ? (u8x64) u64x8_align_right (d0, d0, 4) : d0;
+  d0 = i == 5 ? (u8x64) u64x8_align_right (d0, d0, 5) : d0;
+  d0 = i == 6 ? (u8x64) u64x8_align_right (d0, d0, 6) : d0;
+
+  d0 = u8x64_permute (__clib_toeplitz_hash_gfni_permute, d0);
+
+  return (u64x8) _mm512_gf2p8affine_epi64_epi8 ((__m512i) d0, (__m512i) m, 0);
+}
+
+static_always_inline u64x8
+clib_toeplitz_hash_gfni_two (u8x64 d0, u8x64 d1, u64x8 m, int i)
+{
+
+  d0 = i == 1 ? (u8x64) u64x8_align_right (d0, d0, 1) : d0;
+  d1 = i == 1 ? (u8x64) u64x8_align_right (d1, d1, 1) : d1;
+  d0 = i == 2 ? (u8x64) u64x8_align_right (d0, d0, 2) : d0;
+  d1 = i == 2 ? (u8x64) u64x8_align_right (d1, d1, 2) : d1;
+  d0 = i == 3 ? (u8x64) u64x8_align_right (d0, d0, 3) : d0;
+  d1 = i == 3 ? (u8x64) u64x8_align_right (d1, d1, 3) : d1;
+  d0 = i == 4 ? (u8x64) u64x8_align_right (d0, d0, 4) : d0;
+  d1 = i == 4 ? (u8x64) u64x8_align_right (d1, d1, 4) : d1;
+  d0 = i == 5 ? (u8x64) u64x8_align_right (d0, d0, 5) : d0;
+  d1 = i == 5 ? (u8x64) u64x8_align_right (d1, d1, 5) : d1;
+  d0 = i == 6 ? (u8x64) u64x8_align_right (d0, d0, 6) : d0;
+  d1 = i == 6 ? (u8x64) u64x8_align_right (d1, d1, 6) : d1;
+
+  d0 = u8x64_permute2 (__clib_toeplitz_hash_gfni_permute, d0, d1);
+
+  return (u64x8) _mm512_gf2p8affine_epi64_epi8 ((__m512i) d0, (__m512i) m, 0);
+}
+#endif
+
 static_always_inline u32
 clib_toeplitz_hash (clib_toeplitz_hash_key_t *k, u8 *data, int n_bytes)
 {
@@ -48,91 +93,68 @@ clib_toeplitz_hash (clib_toeplitz_hash_key_t *k, u8 *data, int n_bytes)
   ASSERT (k->key_length - n_bytes >= 4);
 
 #if defined(__GFNI__) && defined(__AVX512F__)
-  u8x64 a, b, dv;
-  u64x8 xor_sum_x8 = {};
+  u8x64 d0;
+  u64x8 h0 = {};
   u64x8u *m = (u64x8u *) ((u8 *) k + k->gfni_offset);
 
-  u8x64 idx = { 0x00, 0x01, 0x02, 0x03, 0x00, 0x01, 0x02, 0x03, 0x01, 0x02,
-               0x03, 0x04, 0x01, 0x02, 0x03, 0x04, 0x02, 0x03, 0x04, 0x05,
-               0x02, 0x03, 0x04, 0x05, 0x03, 0x04, 0x05, 0x06, 0x03, 0x04,
-               0x05, 0x06, 0x04, 0x05, 0x06, 0x07, 0x04, 0x05, 0x06, 0x07,
-               0x05, 0x06, 0x07, 0x08, 0x05, 0x06, 0x07, 0x08, 0x06, 0x07,
-               0x08, 0x09, 0x06, 0x07, 0x08, 0x09, 0x07, 0x08, 0x09, 0x0a,
-               0x07, 0x08, 0x09, 0x0a };
-
   /* move data ptr backwards for 3 byte so mask load "prepends" three zeros */
   data -= 3;
   n_bytes += 3;
 
   if (n_bytes < 64)
     {
-      dv = u8x64_mask_load_zero ((u8 *) data, pow2_mask (n_bytes - 3) << 3);
+      d0 = u8x64_mask_load_zero ((u8 *) data, pow2_mask (n_bytes - 3) << 3);
       goto last8;
     }
 
-  dv = u8x64_mask_load_zero ((u8 *) data, -1ULL << 3);
+  d0 = u8x64_mask_load_zero ((u8 *) data, -1ULL << 3);
 next56:
-  a = u8x64_permute (idx, dv);
-  b = u8x64_permute (idx, (u8x64) u64x8_align_right (dv, dv, 1));
-  xor_sum_x8 = u64x8_xor3 (xor_sum_x8, u64x8_gf2p8_affine (a, m[0], 0),
-                          u64x8_gf2p8_affine (b, m[1], 0));
-
-  a = u8x64_permute (idx, (u8x64) u64x8_align_right (dv, dv, 2));
-  b = u8x64_permute (idx, (u8x64) u64x8_align_right (dv, dv, 3));
-  xor_sum_x8 = u64x8_xor3 (xor_sum_x8, u64x8_gf2p8_affine (a, m[2], 0),
-                          u64x8_gf2p8_affine (b, m[3], 0));
-
-  a = u8x64_permute (idx, (u8x64) u64x8_align_right (dv, dv, 4));
-  b = u8x64_permute (idx, (u8x64) u64x8_align_right (dv, dv, 5));
-  xor_sum_x8 = u64x8_xor3 (xor_sum_x8, u64x8_gf2p8_affine (a, m[4], 0),
-                          u64x8_gf2p8_affine (b, m[5], 0));
-
-  a = u8x64_permute (idx, (u8x64) u64x8_align_right (dv, dv, 6));
-  xor_sum_x8 ^= u64x8_gf2p8_affine (a, m[6], 0);
+  h0 = u64x8_xor3 (h0, clib_toeplitz_hash_gfni_one (d0, m[0], 0),
+                  clib_toeplitz_hash_gfni_one (d0, m[1], 1));
+  h0 = u64x8_xor3 (h0, clib_toeplitz_hash_gfni_one (d0, m[2], 2),
+                  clib_toeplitz_hash_gfni_one (d0, m[3], 3));
+  h0 = u64x8_xor3 (h0, clib_toeplitz_hash_gfni_one (d0, m[4], 4),
+                  clib_toeplitz_hash_gfni_one (d0, m[5], 5));
+  h0 ^= clib_toeplitz_hash_gfni_one (d0, m[6], 6);
   n_bytes -= 56;
   data += 56;
   m += 7;
 
   if (n_bytes >= 64)
     {
-      dv = *(u8x64u *) data;
+      d0 = *(u8x64u *) data;
       goto next56;
     }
 
   if (n_bytes == 0)
     goto done;
 
-  dv = u8x64_mask_load_zero ((u8 *) data, pow2_mask (n_bytes));
+  d0 = u8x64_mask_load_zero ((u8 *) data, pow2_mask (n_bytes));
 last8:
-  a = u8x64_permute (idx, dv);
-  xor_sum_x8 ^= u64x8_gf2p8_affine (a, m[0], 0);
+  h0 ^= clib_toeplitz_hash_gfni_one (d0, m[0], 0);
   n_bytes -= 8;
 
   if (n_bytes > 0)
     {
       m += 1;
-      dv = (u8x64) u64x8_align_right (u64x8_zero (), dv, 1);
+      d0 = (u8x64) u64x8_align_right (u64x8_zero (), d0, 1);
       goto last8;
     }
 
 done:
-  /* horizontal xor */
-  xor_sum_x8 ^= u64x8_align_right (xor_sum_x8, xor_sum_x8, 4);
-  xor_sum_x8 ^= u64x8_align_right (xor_sum_x8, xor_sum_x8, 2);
-  return xor_sum_x8[0] ^ xor_sum_x8[1];
+  return u64x8_hxor (h0);
 #elif defined(CLIB_HAVE_VEC256)
   u64x4 v4, shift = { 0, 1, 2, 3 };
-  u32x8 hash8 = {};
-  u32x4 hash4;
+  u32x8 h0 = {};
 
   while (n_bytes >= 4)
     {
       v4 = u64x4_splat (clib_net_to_host_u64 (*(u64u *) key)) << shift;
 
-      hash8 = toeplitz_hash_one_x8 (hash8, v4, data[0], 0);
-      hash8 = toeplitz_hash_one_x8 (hash8, v4, data[1], 1);
-      hash8 = toeplitz_hash_one_x8 (hash8, v4, data[2], 2);
-      hash8 = toeplitz_hash_one_x8 (hash8, v4, data[3], 3);
+      h0 = toeplitz_hash_one_x8 (h0, v4, data[0], 0);
+      h0 = toeplitz_hash_one_x8 (h0, v4, data[1], 1);
+      h0 = toeplitz_hash_one_x8 (h0, v4, data[2], 2);
+      h0 = toeplitz_hash_one_x8 (h0, v4, data[3], 3);
 
       data += 4;
       key += 4;
@@ -149,29 +171,25 @@ done:
          v |= (u64) key[5] << 16;
          v |= (u64) key[6] << 8;
          v4 = u64x4_splat (v) << shift;
-         hash8 = toeplitz_hash_one_x8 (hash8, v4, data[0], 0);
-         hash8 = toeplitz_hash_one_x8 (hash8, v4, data[1], 1);
-         hash8 = toeplitz_hash_one_x8 (hash8, v4, data[2], 2);
+         h0 = toeplitz_hash_one_x8 (h0, v4, data[0], 0);
+         h0 = toeplitz_hash_one_x8 (h0, v4, data[1], 1);
+         h0 = toeplitz_hash_one_x8 (h0, v4, data[2], 2);
        }
       else if (n_bytes == 2)
        {
          v |= (u64) key[5] << 16;
          v4 = u64x4_splat (v) << shift;
-         hash8 = toeplitz_hash_one_x8 (hash8, v4, data[0], 0);
-         hash8 = toeplitz_hash_one_x8 (hash8, v4, data[1], 1);
+         h0 = toeplitz_hash_one_x8 (h0, v4, data[0], 0);
+         h0 = toeplitz_hash_one_x8 (h0, v4, data[1], 1);
        }
       else
        {
          v4 = u64x4_splat (v) << shift;
-         hash8 = toeplitz_hash_one_x8 (hash8, v4, data[0], 0);
+         h0 = toeplitz_hash_one_x8 (h0, v4, data[0], 0);
        }
     }
 
-  hash4 = u32x8_extract_lo (hash8) ^ u32x8_extract_hi (hash8);
-  hash4 ^= (u32x4) u8x16_align_right (hash4, hash4, 8);
-  hash4 ^= (u32x4) u8x16_align_right (hash4, hash4, 4);
-  return hash4[0];
-
+  return u32x8_hxor (h0);
 #endif
   u64 v, hash = 0;
 
@@ -215,4 +233,281 @@ done:
   return hash >> 32;
 }
 
+static_always_inline void
+clib_toeplitz_hash_x4 (clib_toeplitz_hash_key_t *k, u8 *data0, u8 *data1,
+                      u8 *data2, u8 *data3, u32 *hash0, u32 *hash1,
+                      u32 *hash2, u32 *hash3, int n_bytes)
+{
+  /* key must be 4 bytes longer than data */
+  ASSERT (k->key_length - n_bytes >= 4);
+#if defined(__GFNI__) && defined(__AVX512F__)
+  u64x8u *m = (u64x8u *) ((u8 *) k + k->gfni_offset);
+  u8x64 d0, d1, d2, d3;
+  u64x8 h0 = {}, h2 = {};
+  u64 h, mask;
+
+  /* move data ptr backwards for 3 byte so mask load "prepends" three zeros */
+  data0 -= 3;
+  data1 -= 3;
+  data2 -= 3;
+  data3 -= 3;
+  n_bytes += 3;
+
+  if (n_bytes < 64)
+    {
+      mask = pow2_mask (n_bytes - 3) << 3;
+      d0 = u8x64_mask_load_zero ((u8 *) data0, mask);
+      d1 = u8x64_mask_load_zero ((u8 *) data1, mask);
+      d2 = u8x64_mask_load_zero ((u8 *) data2, mask);
+      d3 = u8x64_mask_load_zero ((u8 *) data3, mask);
+      goto last8;
+    }
+
+  mask = -1ULL << 3;
+  d0 = u8x64_mask_load_zero ((u8 *) data0, mask);
+  d1 = u8x64_mask_load_zero ((u8 *) data1, mask);
+  d2 = u8x64_mask_load_zero ((u8 *) data2, mask);
+  d3 = u8x64_mask_load_zero ((u8 *) data3, mask);
+next56:
+  h0 = u64x8_xor3 (h0, clib_toeplitz_hash_gfni_two (d0, d1, m[0], 0),
+                  clib_toeplitz_hash_gfni_two (d0, d1, m[1], 1));
+  h2 = u64x8_xor3 (h2, clib_toeplitz_hash_gfni_two (d2, d3, m[0], 0),
+                  clib_toeplitz_hash_gfni_two (d2, d3, m[1], 1));
+
+  h0 = u64x8_xor3 (h0, clib_toeplitz_hash_gfni_two (d0, d1, m[2], 2),
+                  clib_toeplitz_hash_gfni_two (d0, d1, m[3], 3));
+  h2 = u64x8_xor3 (h2, clib_toeplitz_hash_gfni_two (d2, d3, m[2], 2),
+                  clib_toeplitz_hash_gfni_two (d2, d3, m[3], 3));
+
+  h0 = u64x8_xor3 (h0, clib_toeplitz_hash_gfni_two (d0, d1, m[4], 4),
+                  clib_toeplitz_hash_gfni_two (d0, d1, m[5], 5));
+  h2 = u64x8_xor3 (h2, clib_toeplitz_hash_gfni_two (d2, d3, m[4], 4),
+                  clib_toeplitz_hash_gfni_two (d2, d3, m[5], 5));
+
+  h0 ^= clib_toeplitz_hash_gfni_two (d0, d1, m[6], 6);
+  h2 ^= clib_toeplitz_hash_gfni_two (d2, d3, m[6], 6);
+
+  n_bytes -= 56;
+  data0 += 56;
+  data1 += 56;
+  data2 += 56;
+  data3 += 56;
+  m += 7;
+
+  if (n_bytes >= 64)
+    {
+      d0 = *(u8x64u *) data0;
+      d1 = *(u8x64u *) data1;
+      d2 = *(u8x64u *) data2;
+      d3 = *(u8x64u *) data3;
+      goto next56;
+    }
+
+  if (n_bytes == 0)
+    goto done;
+
+  mask = pow2_mask (n_bytes);
+  d0 = u8x64_mask_load_zero ((u8 *) data0, mask);
+  d1 = u8x64_mask_load_zero ((u8 *) data1, mask);
+  d2 = u8x64_mask_load_zero ((u8 *) data2, mask);
+  d3 = u8x64_mask_load_zero ((u8 *) data3, mask);
+last8:
+  h0 ^= clib_toeplitz_hash_gfni_two (d0, d1, m[0], 0);
+  h2 ^= clib_toeplitz_hash_gfni_two (d2, d3, m[0], 0);
+  n_bytes -= 8;
+
+  if (n_bytes > 0)
+    {
+      u64x8 zero = {};
+      m += 1;
+      d0 = (u8x64) u64x8_align_right (zero, d0, 1);
+      d1 = (u8x64) u64x8_align_right (zero, d1, 1);
+      d2 = (u8x64) u64x8_align_right (zero, d2, 1);
+      d3 = (u8x64) u64x8_align_right (zero, d3, 1);
+      goto last8;
+    }
+
+done:
+  h = u64x8_hxor (h0);
+  *hash0 = h;
+  *hash1 = h >> 32;
+  h = u64x8_hxor (h2);
+  *hash2 = h;
+  *hash3 = h >> 32;
+#elif defined(CLIB_HAVE_VEC256)
+  u8 *key = k->data;
+  u64x4 v4, shift = { 0, 1, 2, 3 };
+  u32x8 h0 = {}, h1 = {}, h2 = {}, h3 = {};
+
+  while (n_bytes >= 4)
+    {
+      v4 = u64x4_splat (clib_net_to_host_u64 (*(u64u *) key)) << shift;
+
+      h0 = toeplitz_hash_one_x8 (h0, v4, data0[0], 0);
+      h1 = toeplitz_hash_one_x8 (h1, v4, data1[0], 0);
+      h2 = toeplitz_hash_one_x8 (h2, v4, data2[0], 0);
+      h3 = toeplitz_hash_one_x8 (h3, v4, data3[0], 0);
+
+      h0 = toeplitz_hash_one_x8 (h0, v4, data0[1], 1);
+      h1 = toeplitz_hash_one_x8 (h1, v4, data1[1], 1);
+      h2 = toeplitz_hash_one_x8 (h2, v4, data2[1], 1);
+      h3 = toeplitz_hash_one_x8 (h3, v4, data3[1], 1);
+
+      h0 = toeplitz_hash_one_x8 (h0, v4, data0[2], 2);
+      h1 = toeplitz_hash_one_x8 (h1, v4, data1[2], 2);
+      h2 = toeplitz_hash_one_x8 (h2, v4, data2[2], 2);
+      h3 = toeplitz_hash_one_x8 (h3, v4, data3[2], 2);
+
+      h0 = toeplitz_hash_one_x8 (h0, v4, data0[3], 3);
+      h1 = toeplitz_hash_one_x8 (h1, v4, data1[3], 3);
+      h2 = toeplitz_hash_one_x8 (h2, v4, data2[3], 3);
+      h3 = toeplitz_hash_one_x8 (h3, v4, data3[3], 3);
+
+      data0 += 4;
+      data1 += 4;
+      data2 += 4;
+      data3 += 4;
+      key += 4;
+      n_bytes -= 4;
+    }
+
+  if (n_bytes)
+    {
+      u64 v = (u64) clib_net_to_host_u32 ((u64) (*(u32u *) key)) << 32;
+      v |= (u64) key[4] << 24;
+
+      if (n_bytes == 3)
+       {
+         v |= (u64) key[5] << 16;
+         v |= (u64) key[6] << 8;
+         v4 = u64x4_splat (v) << shift;
+         h0 = toeplitz_hash_one_x8 (h0, v4, data0[0], 0);
+         h1 = toeplitz_hash_one_x8 (h1, v4, data1[0], 0);
+         h2 = toeplitz_hash_one_x8 (h2, v4, data2[0], 0);
+         h3 = toeplitz_hash_one_x8 (h3, v4, data3[0], 0);
+
+         h0 = toeplitz_hash_one_x8 (h0, v4, data0[1], 1);
+         h1 = toeplitz_hash_one_x8 (h1, v4, data1[1], 1);
+         h2 = toeplitz_hash_one_x8 (h2, v4, data2[1], 1);
+         h3 = toeplitz_hash_one_x8 (h3, v4, data3[1], 1);
+
+         h0 = toeplitz_hash_one_x8 (h0, v4, data0[2], 2);
+         h1 = toeplitz_hash_one_x8 (h1, v4, data1[2], 2);
+         h2 = toeplitz_hash_one_x8 (h2, v4, data2[2], 2);
+         h3 = toeplitz_hash_one_x8 (h3, v4, data3[2], 2);
+       }
+      else if (n_bytes == 2)
+       {
+         v |= (u64) key[5] << 16;
+         v4 = u64x4_splat (v) << shift;
+         h0 = toeplitz_hash_one_x8 (h0, v4, data0[0], 0);
+         h1 = toeplitz_hash_one_x8 (h1, v4, data1[0], 0);
+         h2 = toeplitz_hash_one_x8 (h2, v4, data2[0], 0);
+         h3 = toeplitz_hash_one_x8 (h3, v4, data3[0], 0);
+
+         h0 = toeplitz_hash_one_x8 (h0, v4, data0[1], 1);
+         h1 = toeplitz_hash_one_x8 (h1, v4, data1[1], 1);
+         h2 = toeplitz_hash_one_x8 (h2, v4, data2[1], 1);
+         h3 = toeplitz_hash_one_x8 (h3, v4, data3[1], 1);
+       }
+      else
+       {
+         v4 = u64x4_splat (v) << shift;
+         h0 = toeplitz_hash_one_x8 (h0, v4, data0[0], 0);
+         h1 = toeplitz_hash_one_x8 (h1, v4, data1[0], 0);
+         h2 = toeplitz_hash_one_x8 (h2, v4, data2[0], 0);
+         h3 = toeplitz_hash_one_x8 (h3, v4, data3[0], 0);
+       }
+    }
+
+  *hash0 = u32x8_hxor (h0);
+  *hash1 = u32x8_hxor (h1);
+  *hash2 = u32x8_hxor (h2);
+  *hash3 = u32x8_hxor (h3);
+#else
+  u8 *key = k->data;
+  u64 v, h0 = 0, h1 = 0, h2 = 0, h3 = 0;
+
+  while (n_bytes >= 4)
+    {
+      v = clib_net_to_host_u64 (*(u64u *) key);
+
+      for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1)
+       {
+         h0 ^= data0[0] & bit ? v : 0;
+         h1 ^= data1[0] & bit ? v : 0;
+         h2 ^= data2[0] & bit ? v : 0;
+         h3 ^= data3[0] & bit ? v : 0;
+       }
+      for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1)
+       {
+         h0 ^= data0[1] & bit ? v : 0;
+         h1 ^= data1[1] & bit ? v : 0;
+         h2 ^= data2[1] & bit ? v : 0;
+         h3 ^= data3[1] & bit ? v : 0;
+       }
+      for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1)
+       {
+         h0 ^= data0[2] & bit ? v : 0;
+         h1 ^= data1[2] & bit ? v : 0;
+         h2 ^= data2[2] & bit ? v : 0;
+         h3 ^= data3[2] & bit ? v : 0;
+       }
+      for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1)
+       {
+         h0 ^= data0[3] & bit ? v : 0;
+         h1 ^= data1[3] & bit ? v : 0;
+         h2 ^= data2[3] & bit ? v : 0;
+         h3 ^= data3[3] & bit ? v : 0;
+       }
+
+      data0 += 4;
+      data1 += 4;
+      data2 += 4;
+      data3 += 4;
+      key += 4;
+      n_bytes -= 4;
+    }
+
+  if (n_bytes)
+    {
+      v = (u64) clib_net_to_host_u32 ((u64) (*(u32u *) key)) << 32;
+      v |= (u64) key[4] << 24;
+      for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1)
+       {
+         h0 ^= data0[0] & bit ? v : 0;
+         h1 ^= data1[0] & bit ? v : 0;
+         h2 ^= data2[0] & bit ? v : 0;
+         h3 ^= data3[0] & bit ? v : 0;
+       }
+      if (n_bytes > 1)
+       {
+         v |= (u64) key[5] << 24;
+         for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1)
+           {
+             h0 ^= data0[1] & bit ? v : 0;
+             h1 ^= data1[1] & bit ? v : 0;
+             h2 ^= data2[1] & bit ? v : 0;
+             h3 ^= data3[1] & bit ? v : 0;
+           }
+       }
+      if (n_bytes > 2)
+       {
+         v |= (u64) key[6] << 24;
+         for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1)
+           {
+             h0 ^= data0[2] & bit ? v : 0;
+             h1 ^= data1[2] & bit ? v : 0;
+             h2 ^= data2[2] & bit ? v : 0;
+             h3 ^= data3[2] & bit ? v : 0;
+           }
+       }
+    }
+  *hash0 = h0 >> 32;
+  *hash1 = h1 >> 32;
+  *hash2 = h2 >> 32;
+  *hash3 = h3 >> 32;
+#endif
+}
+
 #endif

diff --git a/src/vppinfra/vector_avx2.h b/src/vppinfra/vector_avx2.h
index 5985718..6a363cc 100644 (file)
--- a/src/vppinfra/vector_avx2.h
+++ b/src/vppinfra/vector_avx2.h
@@ -203,6 +203,16 @@ u32x8_hadd (u32x8 v1, u32x8 v2)
   return (u32x8) _mm256_hadd_epi32 ((__m256i) v1, (__m256i) v2);
 }
 
+static_always_inline u32
+u32x8_hxor (u32x8 v)
+{
+  u32x4 v4;
+  v4 = u32x8_extract_lo (v) ^ u32x8_extract_hi (v);
+  v4 ^= (u32x4) u8x16_align_right (v4, v4, 8);
+  v4 ^= (u32x4) u8x16_align_right (v4, v4, 4);
+  return v4[0];
+}
+
 static_always_inline u16x16
 u16x16_mask_last (u16x16 v, u8 n_last)
 {

diff --git a/src/vppinfra/vector_avx512.h b/src/vppinfra/vector_avx512.h
index 3505961..e71a8a7 100644 (file)
--- a/src/vppinfra/vector_avx512.h
+++ b/src/vppinfra/vector_avx512.h
@@ -322,9 +322,16 @@ u8x64_mask_blend (u8x64 a, u8x64 b, u64 mask)
 }
 
 static_always_inline u8x64
-u8x64_permute (u8x64 v, u8x64 idx)
+u8x64_permute (u8x64 idx, u8x64 a)
 {
-  return (u8x64) _mm512_permutexvar_epi8 ((__m512i) v, (__m512i) idx);
+  return (u8x64) _mm512_permutexvar_epi8 ((__m512i) idx, (__m512i) a);
+}
+
+static_always_inline u8x64
+u8x64_permute2 (u8x64 idx, u8x64 a, u8x64 b)
+{
+  return (u8x64) _mm512_permutex2var_epi8 ((__m512i) a, (__m512i) idx,
+                                          (__m512i) b);
 }
 
 #define _(t, m, e, p, it)                                                     \
@@ -436,6 +443,14 @@ u16x8_compress (u16x8 v, u8 mask)
 }
 #endif
 
+static_always_inline u64
+u64x8_hxor (u64x8 v)
+{
+  v ^= u64x8_align_right (v, v, 4);
+  v ^= u64x8_align_right (v, v, 2);
+  return v[0] ^ v[1];
+}
+
 static_always_inline void
 u32x16_transpose (u32x16 m[16])
 {