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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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 *------------------------------------------------------------------
19 *------------------------------------------------------------------
20 * Copyright(c) 2018, Intel Corporation All rights reserved.
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
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
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.
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 *------------------------------------------------------------------
50 * Based on work by: Shay Gueron, Michael E. Kounavis, Erdinc Ozturk,
51 * Vinodh Gopal, James Guilford, Tomasz Kantecki
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
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
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
76 * GHash is calculated on 128-bit blocks of data according to the following
78 * GH = (GH + data) * hash_key
80 * To avoid bit-reflection of data, this code uses GF multipication
81 * with reversed polynomial:
82 * a * b * x^-127 mod RPOLY
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:
90 * ghash_precompute (H, Hi, 4);
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]);
99 * GH = ghash_final (gd);
101 * Reduction step is split into 3 functions so it can be better interleaved
102 * with other code, (i.e. with AES computation).
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 u8x16
111 ghash_xor3 (u8x16 a, u8x16 b, u8x16 c)
113 #if defined (__AVX512F__)
114 return (u8x16) _mm_ternarylogic_epi32 ((__m128i) a, (__m128i) b,
120 static_always_inline u8x16
121 gmul_lo_lo (u8x16 a, u8x16 b)
123 return (u8x16) _mm_clmulepi64_si128 ((__m128i) a, (__m128i) b, 0x00);
126 static_always_inline u8x16
127 gmul_lo_hi (u8x16 a, u8x16 b)
129 return (u8x16) _mm_clmulepi64_si128 ((__m128i) a, (__m128i) b, 0x01);
132 static_always_inline u8x16
133 gmul_hi_lo (u8x16 a, u8x16 b)
135 return (u8x16) _mm_clmulepi64_si128 ((__m128i) a, (__m128i) b, 0x10);
138 static_always_inline u8x16
139 gmul_hi_hi (u8x16 a, u8x16 b)
141 return (u8x16) _mm_clmulepi64_si128 ((__m128i) a, (__m128i) b, 0x11);
146 u8x16 mid, hi, lo, tmp_lo, tmp_hi;
150 static const u8x16 ghash_poly = {
151 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
152 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xc2
155 static const u8x16 ghash_poly2 = {
156 0x00, 0x00, 0x00, 0xc2, 0x01, 0x00, 0x00, 0x00,
157 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xc2
160 static_always_inline void
161 ghash_mul_first (ghash_data_t * gd, u8x16 a, u8x16 b)
164 gd->hi = gmul_hi_hi (a, b);
166 gd->lo = gmul_lo_lo (a, b);
167 /* a0 * b1 ^ a1 * b0 */
168 gd->mid = (gmul_lo_hi (a, b) ^ gmul_hi_lo (a, b));
170 /* set gd->pending to 0 so next invocation of ghash_mul_next(...) knows that
171 there is no pending data in tmp_lo and tmp_hi */
175 static_always_inline void
176 ghash_mul_next (ghash_data_t * gd, u8x16 a, u8x16 b)
179 u8x16 hi = gmul_hi_hi (a, b);
181 u8x16 lo = gmul_lo_lo (a, b);
183 /* this branch will be optimized out by the compiler, and it allows us to
184 reduce number of XOR operations by using ternary logic */
187 /* there is peding data from previous invocation so we can XOR */
188 gd->hi = ghash_xor3 (gd->hi, gd->tmp_hi, hi);
189 gd->lo = ghash_xor3 (gd->lo, gd->tmp_lo, lo);
194 /* there is no peding data from previous invocation so we postpone XOR */
200 /* gd->mid ^= a0 * b1 ^ a1 * b0 */
201 gd->mid = ghash_xor3 (gd->mid, gmul_lo_hi (a, b), gmul_hi_lo (a, b));
204 static_always_inline void
205 ghash_reduce (ghash_data_t * gd)
209 /* Final combination:
210 gd->lo ^= gd->mid << 64
211 gd->hi ^= gd->mid >> 64 */
212 u8x16 midl = u8x16_word_shift_left (gd->mid, 8);
213 u8x16 midr = u8x16_word_shift_right (gd->mid, 8);
217 gd->lo = ghash_xor3 (gd->lo, gd->tmp_lo, midl);
218 gd->hi = ghash_xor3 (gd->hi, gd->tmp_hi, midr);
226 r = gmul_lo_hi (ghash_poly2, gd->lo);
227 gd->lo ^= u8x16_word_shift_left (r, 8);
230 static_always_inline void
231 ghash_reduce2 (ghash_data_t * gd)
233 gd->tmp_lo = gmul_lo_lo (ghash_poly2, gd->lo);
234 gd->tmp_hi = gmul_hi_lo (ghash_poly2, gd->lo);
237 static_always_inline u8x16
238 ghash_final (ghash_data_t * gd)
240 return ghash_xor3 (gd->hi, u8x16_word_shift_right (gd->tmp_lo, 4),
241 u8x16_word_shift_left (gd->tmp_hi, 4));
244 static_always_inline u8x16
245 ghash_mul (u8x16 a, u8x16 b)
247 ghash_data_t _gd, *gd = &_gd;
248 ghash_mul_first (gd, a, b);
251 return ghash_final (gd);
254 static_always_inline void
255 ghash_precompute (u8x16 H, u8x16 * Hi, int count)
259 /* calcullate H<<1 mod poly from the hash key */
260 r8 = (u8x16) ((u64x2) H >> 63);
261 H = (u8x16) ((u64x2) H << 1);
262 H |= u8x16_word_shift_left (r8, 8);
263 r32 = (u32x4) u8x16_word_shift_right (r8, 8);
264 r32 = u32x4_shuffle (r32, 0, 1, 2, 0);
266 r32 = r32 == (u32x4) {1, 0, 0, 1};
268 Hi[0] = H ^ ((u8x16) r32 & ghash_poly);
270 /* calculate H^(i + 1) */
271 for (int i = 1; i < count; i++)
272 Hi[i] = ghash_mul (Hi[0], Hi[i - 1]);
275 #endif /* __ghash_h__ */
278 * fd.io coding-style-patch-verification: ON
281 * eval: (c-set-style "gnu")