src/vppinfra/vector/toeplitz.c

   1 /* SPDX-License-Identifier: Apache-2.0
   2  * Copyright(c) 2021 Cisco Systems, Inc.
   3  */
   4
   5 #include <vppinfra/clib.h>
   6 #include <vppinfra/mem.h>
   7 #include <vppinfra/vector/toeplitz.h>
   8
   9 static u8 default_key[40] = {
  10   0x6d, 0x5a, 0x56, 0xda, 0x25, 0x5b, 0x0e, 0xc2, 0x41, 0x67,
  11   0x25, 0x3d, 0x43, 0xa3, 0x8f, 0xb0, 0xd0, 0xca, 0x2b, 0xcb,
  12   0xae, 0x7b, 0x30, 0xb4, 0x77, 0xcb, 0x2d, 0xa3, 0x80, 0x30,
  13   0xf2, 0x0c, 0x6a, 0x42, 0xb7, 0x3b, 0xbe, 0xac, 0x01, 0xfa,
  14 };
  15
  16 #ifdef __x86_64__
  17 static_always_inline void
  18 clib_toeplitz_hash_key_expand_8 (u64x2 kv, u64x8u *m)
  19 {
  20   u64x8 kv4, a, b, shift = { 0, 1, 2, 3, 4, 5, 6, 7 };
  21
  22   kv4 = (u64x8){ kv[0], kv[1], kv[0], kv[1], kv[0], kv[1], kv[0], kv[1] };
  23
  24   /* clang-format off */
  25   /* create 8 byte-swapped copies of the bytes 0 - 7 */
  26   a = (u64x8) u8x64_shuffle (kv4,
  27     0x7, 0x6, 0x5, 0x4, 0x3, 0x2, 0x1, 0x0,
  28     0x7, 0x6, 0x5, 0x4, 0x3, 0x2, 0x1, 0x0,
  29     0x7, 0x6, 0x5, 0x4, 0x3, 0x2, 0x1, 0x0,
  30     0x7, 0x6, 0x5, 0x4, 0x3, 0x2, 0x1, 0x0,
  31     0x7, 0x6, 0x5, 0x4, 0x3, 0x2, 0x1, 0x0,
  32     0x7, 0x6, 0x5, 0x4, 0x3, 0x2, 0x1, 0x0,
  33     0x7, 0x6, 0x5, 0x4, 0x3, 0x2, 0x1, 0x0,
  34     0x7, 0x6, 0x5, 0x4, 0x3, 0x2, 0x1, 0x0);
  35   /* create 8 byte-swapped copies of the bytes 4 - 11 */
  36   b = (u64x8) u8x64_shuffle (kv4,
  37     0xb, 0xa, 0x9, 0x8, 0x7, 0x6, 0x5, 0x4,
  38     0xb, 0xa, 0x9, 0x8, 0x7, 0x6, 0x5, 0x4,
  39     0xb, 0xa, 0x9, 0x8, 0x7, 0x6, 0x5, 0x4,
  40     0xb, 0xa, 0x9, 0x8, 0x7, 0x6, 0x5, 0x4,
  41     0xb, 0xa, 0x9, 0x8, 0x7, 0x6, 0x5, 0x4,
  42     0xb, 0xa, 0x9, 0x8, 0x7, 0x6, 0x5, 0x4,
  43     0xb, 0xa, 0x9, 0x8, 0x7, 0x6, 0x5, 0x4,
  44     0xb, 0xa, 0x9, 0x8, 0x7, 0x6, 0x5, 0x4);
  45   /* clang-format on */
  46
  47   /* shift each 64-bit element for 0 - 7 bits */
  48   a <<= shift;
  49   b <<= shift;
  50
  51   /* clang-format off */
  52   /* construct eight 8x8 bit matrix used by gf2p8affine */
  53   * m = (u64x8) u8x64_shuffle2 (a, b,
  54     0x07, 0x0f, 0x17, 0x1f, 0x27, 0x2f, 0x37, 0x3f,
  55     0x06, 0x0e, 0x16, 0x1e, 0x26, 0x2e, 0x36, 0x3e,
  56     0x05, 0x0d, 0x15, 0x1d, 0x25, 0x2d, 0x35, 0x3d,
  57     0x04, 0x0c, 0x14, 0x1c, 0x24, 0x2c, 0x34, 0x3c,
  58     0x47, 0x4f, 0x57, 0x5f, 0x67, 0x6f, 0x77, 0x7f,
  59     0x46, 0x4e, 0x56, 0x5e, 0x66, 0x6e, 0x76, 0x7e,
  60     0x45, 0x4d, 0x55, 0x5d, 0x65, 0x6d, 0x75, 0x7d,
  61     0x44, 0x4c, 0x54, 0x5c, 0x64, 0x6c, 0x74, 0x7c);
  62   /* clang-format on */
  63 }
  64
  65 void
  66 clib_toeplitz_hash_key_expand (u64 *matrixes, u8 *key, int size)
  67 {
  68   u64x8u *m = (u64x8u *) matrixes;
  69   u64x2 kv, zero = {};
  70
  71   while (size >= 8)
  72     {
  73       kv = *(u64x2u *) key;
  74       clib_toeplitz_hash_key_expand_8 (kv, m);
  75       key += 8;
  76       m++;
  77       size -= 8;
  78     }
  79
  80   kv = u64x2_shuffle2 (kv, zero, 1, 2);
  81   clib_toeplitz_hash_key_expand_8 (kv, m);
  82 }
  83 #endif
  84
  85 __clib_export clib_toeplitz_hash_key_t *
  86 clib_toeplitz_hash_key_init (u8 *key, u32 keylen)
  87 {
  88   clib_toeplitz_hash_key_t *k;
  89   u32 size, gfni_size = 0;
  90
  91   if (key == 0)
  92     {
  93       key = default_key;
  94       keylen = sizeof (default_key);
  95     }
  96
  97   size =
  98     round_pow2 (sizeof (clib_toeplitz_hash_key_t) + round_pow2 (keylen, 16),
  99                 CLIB_CACHE_LINE_BYTES);
 100 #ifdef __x86_64__
 101   gfni_size = round_pow2 ((keylen + 1) * 8, CLIB_CACHE_LINE_BYTES);
 102 #endif
 103
 104   k = clib_mem_alloc_aligned (size + gfni_size, CLIB_CACHE_LINE_BYTES);
 105   clib_memset_u8 (k, 0, size + gfni_size);
 106   k->key_length = keylen;
 107   k->gfni_offset = size;
 108   clib_memcpy_fast (k->data, key, keylen);
 109
 110 #ifdef __x86_64__
 111   clib_toeplitz_hash_key_expand ((u64 *) ((u8 *) k + k->gfni_offset), k->data,
 112                                  k->key_length);
 113 #endif
 114
 115   return k;
 116 }
 117
 118 __clib_export void
 119 clib_toeplitz_hash_key_free (clib_toeplitz_hash_key_t *k)
 120 {
 121   clib_mem_free (k);
 122 }