FD.io VPP  v20.01-48-g3e0dafb74
Vector Packet Processing
ghash.h
Go to the documentation of this file.
1 /*
2  *------------------------------------------------------------------
3  * Copyright (c) 2019 Cisco and/or its affiliates.
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at:
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  *------------------------------------------------------------------
16  */
17 
18 /*
19  *------------------------------------------------------------------
20  * Copyright(c) 2018, Intel Corporation All rights reserved.
21  *
22  * Redistribution and use in source and binary forms, with or without
23  * modification, are permitted provided that the following conditions
24  * are met:
25  * * Redistributions of source code must retain the above copyright
26  * notice, this list of conditions and the following disclaimer.
27  * * Redistributions in binary form must reproduce the above copyright
28  * notice, this list of conditions and the following disclaimer in
29  * the documentation and/or other materials provided with the
30  * distribution.
31  * * Neither the name of Intel Corporation nor the names of its
32  * contributors may be used to endorse or promote products derived
33  * from this software without specific prior written permission.
34  *
35  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
36  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
37  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
38  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
39  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES * LOSS OF USE,
42  * DATA, OR PROFITS * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
43  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
44  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
45  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
46  *------------------------------------------------------------------
47  */
48 
49 /*
50  * Based on work by: Shay Gueron, Michael E. Kounavis, Erdinc Ozturk,
51  * Vinodh Gopal, James Guilford, Tomasz Kantecki
52  *
53  * References:
54  * [1] Vinodh Gopal et. al. Optimized Galois-Counter-Mode Implementation on
55  * Intel Architecture Processors. August, 2010
56  * [2] Erdinc Ozturk et. al. Enabling High-Performance Galois-Counter-Mode on
57  * Intel Architecture Processors. October, 2012.
58  * [3] intel-ipsec-mb library, https://github.com/01org/intel-ipsec-mb.git
59  *
60  * Definitions:
61  * GF Galois Extension Field GF(2^128) - finite field where elements are
62  * represented as polynomials with coefficients in GF(2) with the
63  * highest degree of 127. Polynomials are represented as 128-bit binary
64  * numbers where each bit represents one coefficient.
65  * e.g. polynomial x^5 + x^3 + x + 1 is represented in binary 101011.
66  * H hash key (128 bit)
67  * POLY irreducible polynomial x^127 + x^7 + x^2 + x + 1
68  * RPOLY irreducible polynomial x^128 + x^127 + x^126 + x^121 + 1
69  * + addition in GF, which equals to XOR operation
70  * * multiplication in GF
71  *
72  * GF multiplication consists of 2 steps:
73  * - carry-less multiplication of two 128-bit operands into 256-bit result
74  * - reduction of 256-bit result into 128-bit with modulo POLY
75  *
76  * GHash is calculated on 128-bit blocks of data according to the following
77  * formula:
78  * GH = (GH + data) * hash_key
79  *
80  * To avoid bit-reflection of data, this code uses GF multipication
81  * with reversed polynomial:
82  * a * b * x^-127 mod RPOLY
83  *
84  * To improve computation speed table Hi is precomputed with powers of H',
85  * where H' is calculated as H<<1 mod RPOLY.
86  * This allows us to improve performance by deferring reduction. For example
87  * to caclulate ghash of 4 128-bit blocks of data (b0, b1, b2, b3), we can do:
88  *
89  * __i128 Hi[4];
90  * ghash_precompute (H, Hi, 4);
91  *
92  * ghash_data_t _gd, *gd = &_gd;
93  * ghash_mul_first (gd, GH ^ b0, Hi[3]);
94  * ghash_mul_next (gd, b1, Hi[2]);
95  * ghash_mul_next (gd, b2, Hi[1]);
96  * ghash_mul_next (gd, b3, Hi[0]);
97  * ghash_reduce (gd);
98  * ghash_reduce2 (gd);
99  * GH = ghash_final (gd);
100  *
101  * Reduction step is split into 3 functions so it can be better interleaved
102  * with other code, (i.e. with AES computation).
103  */
104 
105 #ifndef __ghash_h__
106 #define __ghash_h__
107 
108 /* on AVX-512 systems we can save a clock cycle by using ternary logic
109  instruction to calculate a XOR b XOR c */
110 static_always_inline __m128i
111 ghash_xor3 (__m128i a, __m128i b, __m128i c)
112 {
113 #if defined (__AVX512F__)
114  return _mm_ternarylogic_epi32 (a, b, c, 0x96);
115 #endif
116  return a ^ b ^ c;
117 }
118 
119 typedef struct
120 {
121  __m128i mid, hi, lo, tmp_lo, tmp_hi;
122  int pending;
123 } ghash_data_t;
124 
125 static const __m128i ghash_poly = { 1, 0xC200000000000000 };
126 static const __m128i ghash_poly2 = { 0x1C2000000, 0xC200000000000000 };
127 
129 ghash_mul_first (ghash_data_t * gd, __m128i a, __m128i b)
130 {
131  /* a1 * b1 */
132  gd->hi = _mm_clmulepi64_si128 (a, b, 0x11);
133  /* a0 * b0 */
134  gd->lo = _mm_clmulepi64_si128 (a, b, 0x00);
135  /* a0 * b1 ^ a1 * b0 */
136  gd->mid = (_mm_clmulepi64_si128 (a, b, 0x01) ^
137  _mm_clmulepi64_si128 (a, b, 0x10));
138 
139  /* set gd->pending to 0 so next invocation of ghash_mul_next(...) knows that
140  there is no pending data in tmp_lo and tmp_hi */
141  gd->pending = 0;
142 }
143 
145 ghash_mul_next (ghash_data_t * gd, __m128i a, __m128i b)
146 {
147  /* a1 * b1 */
148  __m128i hi = _mm_clmulepi64_si128 (a, b, 0x11);
149  /* a0 * b0 */
150  __m128i lo = _mm_clmulepi64_si128 (a, b, 0x00);
151 
152  /* this branch will be optimized out by the compiler, and it allows us to
153  reduce number of XOR operations by using ternary logic */
154  if (gd->pending)
155  {
156  /* there is peding data from previous invocation so we can XOR */
157  gd->hi = ghash_xor3 (gd->hi, gd->tmp_hi, hi);
158  gd->lo = ghash_xor3 (gd->lo, gd->tmp_lo, lo);
159  gd->pending = 0;
160  }
161  else
162  {
163  /* there is no peding data from previous invocation so we postpone XOR */
164  gd->tmp_hi = hi;
165  gd->tmp_lo = lo;
166  gd->pending = 1;
167  }
168 
169  /* gd->mid ^= a0 * b1 ^ a1 * b0 */
170  gd->mid = ghash_xor3 (gd->mid,
171  _mm_clmulepi64_si128 (a, b, 0x01),
172  _mm_clmulepi64_si128 (a, b, 0x10));
173 }
174 
177 {
178  __m128i r;
179 
180  /* Final combination:
181  gd->lo ^= gd->mid << 64
182  gd->hi ^= gd->mid >> 64 */
183  __m128i midl = _mm_slli_si128 (gd->mid, 8);
184  __m128i midr = _mm_srli_si128 (gd->mid, 8);
185 
186  if (gd->pending)
187  {
188  gd->lo = ghash_xor3 (gd->lo, gd->tmp_lo, midl);
189  gd->hi = ghash_xor3 (gd->hi, gd->tmp_hi, midr);
190  }
191  else
192  {
193  gd->lo ^= midl;
194  gd->hi ^= midr;
195  }
196 
197  r = _mm_clmulepi64_si128 (ghash_poly2, gd->lo, 0x01);
198  gd->lo ^= _mm_slli_si128 (r, 8);
199 }
200 
203 {
204  gd->tmp_lo = _mm_clmulepi64_si128 (ghash_poly2, gd->lo, 0x00);
205  gd->tmp_hi = _mm_clmulepi64_si128 (ghash_poly2, gd->lo, 0x10);
206 }
207 
208 static_always_inline __m128i
210 {
211  return ghash_xor3 (gd->hi, _mm_srli_si128 (gd->tmp_lo, 4),
212  _mm_slli_si128 (gd->tmp_hi, 4));
213 }
214 
215 static_always_inline __m128i
216 ghash_mul (__m128i a, __m128i b)
217 {
218  ghash_data_t _gd, *gd = &_gd;
219  ghash_mul_first (gd, a, b);
220  ghash_reduce (gd);
221  ghash_reduce2 (gd);
222  return ghash_final (gd);
223 }
224 
226 ghash_precompute (__m128i H, __m128i * Hi, int count)
227 {
228  __m128i r;
229  /* calcullate H<<1 mod poly from the hash key */
230  r = _mm_srli_epi64 (H, 63);
231  H = _mm_slli_epi64 (H, 1);
232  H |= _mm_slli_si128 (r, 8);
233  r = _mm_srli_si128 (r, 8);
234  r = _mm_shuffle_epi32 (r, 0x24);
235  /* *INDENT-OFF* */
236  r = _mm_cmpeq_epi32 (r, (__m128i) (u32x4) {1, 0, 0, 1});
237  /* *INDENT-ON* */
238  Hi[0] = H ^ (r & ghash_poly);
239 
240  /* calculate H^(i + 1) */
241  for (int i = 1; i < count; i++)
242  Hi[i] = ghash_mul (Hi[0], Hi[i - 1]);
243 }
244 
245 #endif /* __ghash_h__ */
246 
247 /*
248  * fd.io coding-style-patch-verification: ON
249  *
250  * Local Variables:
251  * eval: (c-set-style "gnu")
252  * End:
253  */
u8 count
Definition: dhcp.api:208
static const __m128i ghash_poly
Definition: ghash.h:125
__m128i mid
Definition: ghash.h:121
a
Definition: bitmap.h:538
int i
static_always_inline void ghash_precompute(__m128i H, __m128i *Hi, int count)
Definition: ghash.h:226
#define static_always_inline
Definition: clib.h:99
static_always_inline void ghash_reduce(ghash_data_t *gd)
Definition: ghash.h:176
static_always_inline void ghash_reduce2(ghash_data_t *gd)
Definition: ghash.h:202
__m128i lo
Definition: ghash.h:121
lo
static_always_inline __m128i ghash_final(ghash_data_t *gd)
Definition: ghash.h:209
svmdb_client_t * c
__m128i hi
Definition: ghash.h:121
vl_api_ip4_address_t hi
Definition: arp.api:37
__m128i tmp_hi
Definition: ghash.h:121
int pending
Definition: ghash.h:122
static_always_inline __m128i ghash_mul(__m128i a, __m128i b)
Definition: ghash.h:216
__m128i tmp_lo
Definition: ghash.h:121
unsigned long long u32x4
Definition: ixge.c:28
static_always_inline void ghash_mul_next(ghash_data_t *gd, __m128i a, __m128i b)
Definition: ghash.h:145
static const __m128i ghash_poly2
Definition: ghash.h:126
static_always_inline __m128i ghash_xor3(__m128i a, __m128i b, __m128i c)
Definition: ghash.h:111
static_always_inline void ghash_mul_first(ghash_data_t *gd, __m128i a, __m128i b)
Definition: ghash.h:129