1 /* 2 * SPDX-License-Identifier: BSD-3-Clause 3 * Copyright(c) 2023 Napatech A/S 4 */ 5 6 #include <math.h> 7 8 #include "flow_hasher.h" 9 10 static uint32_t shuffle(uint32_t x) 11 { 12 return ((x & 0x00000002) << 29) | ((x & 0xAAAAAAA8) >> 3) | ((x & 0x15555555) << 3) | 13 ((x & 0x40000000) >> 29); 14 } 15 16 static uint32_t ror_inv(uint32_t x, const int s) 17 { 18 return (x >> s) | ((~x) << (32 - s)); 19 } 20 21 static uint32_t combine(uint32_t x, uint32_t y) 22 { 23 uint32_t x1 = ror_inv(x, 15); 24 uint32_t x2 = ror_inv(x, 13); 25 uint32_t y1 = ror_inv(y, 3); 26 uint32_t y2 = ror_inv(y, 27); 27 28 return x ^ y ^ 29 ((x1 & y1 & ~x2 & ~y2) | (x1 & ~y1 & x2 & ~y2) | (x1 & ~y1 & ~x2 & y2) | 30 (~x1 & y1 & x2 & ~y2) | (~x1 & y1 & ~x2 & y2) | (~x1 & ~y1 & x2 & y2)); 31 } 32 33 static uint32_t mix(uint32_t x, uint32_t y) 34 { 35 return shuffle(combine(x, y)); 36 } 37 38 static uint64_t ror_inv3(uint64_t x) 39 { 40 const uint64_t m = 0xE0000000E0000000ULL; 41 42 return ((x >> 3) | m) ^ ((x << 29) & m); 43 } 44 45 static uint64_t ror_inv13(uint64_t x) 46 { 47 const uint64_t m = 0xFFF80000FFF80000ULL; 48 49 return ((x >> 13) | m) ^ ((x << 19) & m); 50 } 51 52 static uint64_t ror_inv15(uint64_t x) 53 { 54 const uint64_t m = 0xFFFE0000FFFE0000ULL; 55 56 return ((x >> 15) | m) ^ ((x << 17) & m); 57 } 58 59 static uint64_t ror_inv27(uint64_t x) 60 { 61 const uint64_t m = 0xFFFFFFE0FFFFFFE0ULL; 62 63 return ((x >> 27) | m) ^ ((x << 5) & m); 64 } 65 66 static uint64_t shuffle64(uint64_t x) 67 { 68 return ((x & 0x0000000200000002) << 29) | ((x & 0xAAAAAAA8AAAAAAA8) >> 3) | 69 ((x & 0x1555555515555555) << 3) | ((x & 0x4000000040000000) >> 29); 70 } 71 72 static uint64_t pair(uint32_t x, uint32_t y) 73 { 74 return ((uint64_t)x << 32) | y; 75 } 76 77 static uint64_t combine64(uint64_t x, uint64_t y) 78 { 79 uint64_t x1 = ror_inv15(x); 80 uint64_t x2 = ror_inv13(x); 81 uint64_t y1 = ror_inv3(y); 82 uint64_t y2 = ror_inv27(y); 83 84 return x ^ y ^ 85 ((x1 & y1 & ~x2 & ~y2) | (x1 & ~y1 & x2 & ~y2) | (x1 & ~y1 & ~x2 & y2) | 86 (~x1 & y1 & x2 & ~y2) | (~x1 & y1 & ~x2 & y2) | (~x1 & ~y1 & x2 & y2)); 87 } 88 89 static uint64_t mix64(uint64_t x, uint64_t y) 90 { 91 return shuffle64(combine64(x, y)); 92 } 93 94 static uint32_t calc16(const uint32_t key[16]) 95 { 96 /* 97 * 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Layer 0 98 * \./ \./ \./ \./ \./ \./ \./ \./ 99 * 0 1 2 3 4 5 6 7 Layer 1 100 * \__.__/ \__.__/ \__.__/ \__.__/ 101 * 0 1 2 3 Layer 2 102 * \______.______/ \______.______/ 103 * 0 1 Layer 3 104 * \______________.______________/ 105 * 0 Layer 4 106 * / \ 107 * \./ 108 * 0 Layer 5 109 * / \ 110 * \./ Layer 6 111 * value 112 */ 113 114 uint64_t z; 115 uint32_t x; 116 117 z = mix64(mix64(mix64(pair(key[0], key[8]), pair(key[1], key[9])), 118 mix64(pair(key[2], key[10]), pair(key[3], key[11]))), 119 mix64(mix64(pair(key[4], key[12]), pair(key[5], key[13])), 120 mix64(pair(key[6], key[14]), pair(key[7], key[15])))); 121 122 x = mix((uint32_t)(z >> 32), (uint32_t)z); 123 x = mix(x, ror_inv(x, 17)); 124 x = combine(x, ror_inv(x, 17)); 125 126 return x; 127 } 128 129 uint32_t gethash(struct hasher_s *hsh, const uint32_t key[16], int *result) 130 { 131 uint64_t val; 132 uint32_t res; 133 134 val = calc16(key); 135 res = (uint32_t)val; 136 137 if (hsh->cam_bw > 32) 138 val = (val << (hsh->cam_bw - 32)) ^ val; 139 140 for (int i = 0; i < hsh->banks; i++) { 141 result[i] = (unsigned int)(val & hsh->cam_records_bw_mask); 142 val = val >> hsh->cam_records_bw; 143 } 144 145 return res; 146 } 147 148 int init_hasher(struct hasher_s *hsh, int banks, int nb_records) 149 { 150 hsh->banks = banks; 151 hsh->cam_records_bw = (int)(log2(nb_records - 1) + 1); 152 hsh->cam_records_bw_mask = (1U << hsh->cam_records_bw) - 1; 153 hsh->cam_bw = hsh->banks * hsh->cam_records_bw; 154 155 return 0; 156 } 157