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