suricata
util-memcmp.h
Go to the documentation of this file.
1 /* Copyright (C) 2007-2022 Open Information Security Foundation
2  *
3  * You can copy, redistribute or modify this Program under the terms of
4  * the GNU General Public License version 2 as published by the Free
5  * Software Foundation.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * version 2 along with this program; if not, write to the Free Software
14  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
15  * 02110-1301, USA.
16  */
17 
18 /**
19  * \file
20  *
21  * \author Victor Julien <victor@inliniac.net>
22  *
23  * Memcmp implementations for SSE3, SSE4.1, SSE4.2.
24  *
25  * Both SCMemcmp and SCMemcmpLowercase return 0 on a exact match,
26  * 1 on a failed match.
27  */
28 
29 #ifndef SURICATA_UTIL_MEMCMP_H
30 #define SURICATA_UTIL_MEMCMP_H
31 
32 #include "suricata-common.h"
33 #include "util-optimize.h"
34 
35 /** \brief compare two patterns, converting the 2nd to lowercase
36  * \warning *ONLY* the 2nd pattern is converted to lowercase
37  */
38 static inline int SCMemcmpLowercase(const void *, const void *, size_t);
39 
40 void MemcmpRegisterTests(void);
41 
42 static inline int
43 MemcmpLowercase(const void *s1, const void *s2, size_t n)
44 {
45  for (size_t i = 0; i < n; i++) {
46  if (((uint8_t *)s1)[i] != u8_tolower(((uint8_t *)s2)[i]))
47  return 1;
48  }
49 
50  return 0;
51 }
52 
53 #if defined(__SSE4_2__)
54 #include <nmmintrin.h>
55 #define SCMEMCMP_BYTES 16
56 
57 static inline int SCMemcmp(const void *s1, const void *s2, size_t n)
58 {
59  int r = 0;
60  /* counter for how far we already matched in the buffer */
61  size_t m = 0;
62  do {
63  if (likely(n - m < SCMEMCMP_BYTES)) {
64  return memcmp(s1, s2, n - m) ? 1 : 0;
65  }
66 
67  /* load the buffers into the 128bit vars */
68  __m128i b1 = _mm_loadu_si128((const __m128i *)s1);
69  __m128i b2 = _mm_loadu_si128((const __m128i *)s2);
70 
71  /* do the actual compare: _mm_cmpestri() returns the number of matching bytes */
72  r = _mm_cmpestri(b1, SCMEMCMP_BYTES, b2, SCMEMCMP_BYTES,
73  _SIDD_CMP_EQUAL_EACH | _SIDD_MASKED_NEGATIVE_POLARITY);
74  m += r;
75  s1 += SCMEMCMP_BYTES;
76  s2 += SCMEMCMP_BYTES;
77  } while (r == SCMEMCMP_BYTES);
78 
79  return ((m == n) ? 0 : 1);
80 }
81 
82 /* Range of values of uppercase characters. We only use the first 2 bytes. */
83 static char scmemcmp_uppercase[16] __attribute__((aligned(16))) = {
84  'A', 'Z', 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
85 
86 /** \brief compare two buffers in a case insensitive way
87  * \param s1 buffer already in lowercase
88  * \param s2 buffer with mixed upper and lowercase
89  */
90 static inline int SCMemcmpLowercase(const void *s1, const void *s2, size_t n)
91 {
92  /* counter for how far we already matched in the buffer */
93  size_t m = 0;
94  int r = 0;
95  __m128i ucase = _mm_load_si128((const __m128i *) scmemcmp_uppercase);
96  __m128i uplow = _mm_set1_epi8(0x20);
97 
98  do {
99  const size_t len = n - m;
100  if (likely(len < SCMEMCMP_BYTES)) {
101  return MemcmpLowercase(s1, s2, len);
102  }
103 
104  __m128i b1 = _mm_loadu_si128((const __m128i *)s1);
105  __m128i b2 = _mm_loadu_si128((const __m128i *)s2);
106  /* The first step is creating a mask that is FF for all uppercase
107  * characters, 00 for all others */
108  __m128i mask = _mm_cmpestrm(ucase, 2, b2, len, _SIDD_CMP_RANGES | _SIDD_UNIT_MASK);
109  /* Next we use that mask to create a new: this one has 0x20 for
110  * the uppercase chars, 00 for all other. */
111  mask = _mm_and_si128(uplow, mask);
112  /* finally, merge the mask and the buffer converting the
113  * uppercase to lowercase */
114  b2 = _mm_add_epi8(b2, mask);
115 
116  /* search using our converted buffer, return number of matching bytes */
117  r = _mm_cmpestri(b1, SCMEMCMP_BYTES, b2, SCMEMCMP_BYTES,
118  _SIDD_CMP_EQUAL_EACH | _SIDD_MASKED_NEGATIVE_POLARITY);
119  m += r;
120  s1 += SCMEMCMP_BYTES;
121  s2 += SCMEMCMP_BYTES;
122  } while (r == SCMEMCMP_BYTES);
123 
124  return ((m == n) ? 0 : 1);
125 }
126 
127 #elif defined(__SSE4_1__)
128 #include <smmintrin.h>
129 #define SCMEMCMP_BYTES 16
130 
131 static inline int SCMemcmp(const void *s1, const void *s2, size_t len)
132 {
133  size_t offset = 0;
134  do {
135  if (likely(len - offset < SCMEMCMP_BYTES)) {
136  return memcmp(s1, s2, len - offset) ? 1 : 0;
137  }
138 
139  /* unaligned loads */
140  __m128i b1 = _mm_loadu_si128((const __m128i *)s1);
141  __m128i b2 = _mm_loadu_si128((const __m128i *)s2);
142  __m128i c = _mm_cmpeq_epi8(b1, b2);
143 
144  if (_mm_movemask_epi8(c) != 0x0000FFFF) {
145  return 1;
146  }
147 
148  offset += SCMEMCMP_BYTES;
149  s1 += SCMEMCMP_BYTES;
150  s2 += SCMEMCMP_BYTES;
151  } while (len > offset);
152 
153  return 0;
154 }
155 
156 #define UPPER_LOW 0x40 /* "A" - 1 */
157 #define UPPER_HIGH 0x5B /* "Z" + 1 */
158 
159 static inline int SCMemcmpLowercase(const void *s1, const void *s2, size_t len)
160 {
161  size_t offset = 0;
162  __m128i b1, b2, mask1, mask2, upper1, upper2, uplow;
163 
164  /* setup registers for upper to lower conversion */
165  upper1 = _mm_set1_epi8(UPPER_LOW);
166  upper2 = _mm_set1_epi8(UPPER_HIGH);
167  uplow = _mm_set1_epi8(0x20);
168 
169  do {
170  if (likely(len - offset < SCMEMCMP_BYTES)) {
171  return MemcmpLowercase(s1, s2, len - offset);
172  }
173 
174  /* unaligned loading of the bytes to compare */
175  b1 = _mm_loadu_si128((const __m128i *) s1);
176  b2 = _mm_loadu_si128((const __m128i *) s2);
177 
178  /* mark all chars bigger than upper1 */
179  mask1 = _mm_cmpgt_epi8(b2, upper1);
180  /* mark all chars lower than upper2 */
181  mask2 = _mm_cmplt_epi8(b2, upper2);
182  /* merge the two, leaving only those that are true in both */
183  mask1 = _mm_cmpeq_epi8(mask1, mask2);
184  /* Next we use that mask to create a new: this one has 0x20 for
185  * the uppercase chars, 00 for all other. */
186  mask1 = _mm_and_si128(uplow, mask1);
187  /* add to b2, converting uppercase to lowercase */
188  b2 = _mm_add_epi8(b2, mask1);
189  /* now all is lowercase, let's do the actual compare (reuse mask1 reg) */
190  mask1 = _mm_cmpeq_epi8(b1, b2);
191 
192  if (_mm_movemask_epi8(mask1) != 0x0000FFFF) {
193  return 1;
194  }
195 
196  offset += SCMEMCMP_BYTES;
197  s1 += SCMEMCMP_BYTES;
198  s2 += SCMEMCMP_BYTES;
199  } while (len > offset);
200 
201  return 0;
202 }
203 
204 #elif defined(__SSE3__)
205 #include <pmmintrin.h> /* for SSE3 */
206 #define SCMEMCMP_BYTES 16
207 
208 static inline int SCMemcmp(const void *s1, const void *s2, size_t len)
209 {
210  size_t offset = 0;
211  __m128i b1, b2, c;
212 
213  do {
214  if (likely(len - offset < SCMEMCMP_BYTES)) {
215  return memcmp(s1, s2, len - offset) ? 1 : 0;
216  }
217 
218  /* unaligned loads */
219  b1 = _mm_loadu_si128((const __m128i *) s1);
220  b2 = _mm_loadu_si128((const __m128i *) s2);
221  c = _mm_cmpeq_epi8(b1, b2);
222 
223  if (_mm_movemask_epi8(c) != 0x0000FFFF) {
224  return 1;
225  }
226 
227  offset += SCMEMCMP_BYTES;
228  s1 += SCMEMCMP_BYTES;
229  s2 += SCMEMCMP_BYTES;
230  } while (len > offset);
231 
232  return 0;
233 }
234 
235 #define UPPER_LOW 0x40 /* "A" - 1 */
236 #define UPPER_HIGH 0x5B /* "Z" + 1 */
237 #define UPPER_DELTA 0xDF /* 0xFF - 0x20 */
238 
239 static inline int SCMemcmpLowercase(const void *s1, const void *s2, size_t len)
240 {
241  size_t offset = 0;
242  __m128i b1, b2, mask1, mask2, upper1, upper2, delta;
243 
244  /* setup registers for upper to lower conversion */
245  upper1 = _mm_set1_epi8(UPPER_LOW);
246  upper2 = _mm_set1_epi8(UPPER_HIGH);
247  delta = _mm_set1_epi8(UPPER_DELTA);
248 
249  do {
250  if (likely(len - offset < SCMEMCMP_BYTES)) {
251  return MemcmpLowercase(s1, s2, len - offset);
252  }
253 
254  /* unaligned loading of the bytes to compare */
255  b1 = _mm_loadu_si128((const __m128i *) s1);
256  b2 = _mm_loadu_si128((const __m128i *) s2);
257 
258  /* mark all chars bigger than upper1 */
259  mask1 = _mm_cmpgt_epi8(b2, upper1);
260  /* mark all chars lower than upper2 */
261  mask2 = _mm_cmplt_epi8(b2, upper2);
262  /* merge the two, leaving only those that are true in both */
263  mask1 = _mm_cmpeq_epi8(mask1, mask2);
264  /* sub delta leaves 0x20 only for uppercase positions, the
265  rest is 0x00 due to the saturation (reuse mask1 reg)*/
266  mask1 = _mm_subs_epu8(mask1, delta);
267  /* add to b2, converting uppercase to lowercase */
268  b2 = _mm_add_epi8(b2, mask1);
269 
270  /* now all is lowercase, let's do the actual compare (reuse mask1 reg) */
271  mask1 = _mm_cmpeq_epi8(b1, b2);
272 
273  if (_mm_movemask_epi8(mask1) != 0x0000FFFF) {
274  return 1;
275  }
276 
277  offset += SCMEMCMP_BYTES;
278  s1 += SCMEMCMP_BYTES;
279  s2 += SCMEMCMP_BYTES;
280  } while (len > offset);
281 
282  return 0;
283 }
284 
285 #else
286 
287 /* No SIMD support, fall back to plain memcmp and a home grown lowercase one */
288 
289 /* wrapper around memcmp to match the retvals of the SIMD implementations */
290 #define SCMemcmp(a,b,c) ({ \
291  memcmp((a), (b), (c)) ? 1 : 0; \
292 })
293 
294 static inline int SCMemcmpLowercase(const void *s1, const void *s2, size_t len)
295 {
296  return MemcmpLowercase(s1, s2, len);
297 }
298 
299 #endif /* SIMD */
300 
301 static inline int SCBufferCmp(const void *s1, size_t len1, const void *s2, size_t len2)
302 {
303  if (len1 == len2) {
304  return SCMemcmp(s1, s2, len1);
305  } else if (len1 < len2) {
306  return -1;
307  }
308  return 1;
309 }
310 
311 #endif /* SURICATA_UTIL_MEMCMP_H */
len
uint8_t len
Definition: app-layer-dnp3.h:2
offset
uint64_t offset
Definition: util-streaming-buffer.h:0
u8_tolower
#define u8_tolower(c)
Definition: suricata-common.h:436
m
SCMutex m
Definition: flow-hash.h:6
__attribute__
enum @18 __attribute__
DNP3 application header.
MemcmpRegisterTests
void MemcmpRegisterTests(void)
Definition: util-memcmp.c:350
suricata-common.h
util-optimize.h
likely
#define likely(expr)
Definition: util-optimize.h:32
SCMemcmp
#define SCMemcmp(a, b, c)
Definition: util-memcmp.h:290