1 #include "declarations.h"
2 #include "ribbon.h"
3
4 #include "config.mach"
5
6 #if defined(HAVE_XMMINTRIN_H)
7 #include <xmmintrin.h>
8 #endif
9
10
11
str_boyermoore(char * haystack,long haylen,char * needle,long neelen)12 char *str_boyermoore(char *haystack, long haylen, char *needle, long neelen) {
13 long i, j;
14
15 long *d1, *d2;
16
17 if((d1 = malloc((size_t) 255 * sizeof(long))) == NULL) return(NULL);
18 if((d2 = malloc((size_t) neelen * sizeof(long))) == NULL) {
19 (void) free(d1);
20
21 return(NULL);
22 }
23
24 (void) str_boyermoore_it1(d1, needle, neelen);
25 (void) str_boyermoore_it2(d2, needle, neelen);
26
27 i = neelen - 1;
28
29 while(i < haylen) {
30 j = neelen - 1;
31
32 while(j >= 0 && (haystack[i] == needle[j])) {
33 --i;
34 --j;
35 }
36
37 if(j < 0) {
38 (void) free(d1);
39 (void) free(d2);
40
41 return(haystack + i + 1);
42 }
43
44 i += str_boyermoore_max(d1[(long) haystack[i]], d2[j]);
45 }
46
47 (void) free(d1);
48 (void) free(d2);
49
50 return(NULL);
51 }
52
str_boyermoore_it1(long * d1,char * needle,long neelen)53 static void str_boyermoore_it1(long *d1, char *needle, long neelen) {
54 long i;
55
56 for(i = 0; i < 255; i++) d1[i] = neelen;
57 for(i = 0; i < neelen - 1; i++) d1[(long) needle[i]] = neelen - 1 - i;
58 }
59
str_boyermoore_it2(long * d2,char * needle,long neelen)60 static void str_boyermoore_it2(long *d2, char *needle, long neelen) {
61 long i, p, s;
62
63 i = neelen - 1;
64
65 for(p = neelen - 1; p >= 0; p--) {
66 if(str_boyermoore_ispref(needle, neelen, p + 1)) i = p + 1;
67
68 d2[p] = i + (neelen - 1 - p);
69 }
70
71 for(p = 0; p < neelen - 1; p++) {
72 s = str_boyermoore_suflen(needle, neelen, p);
73
74 if(needle[p - s] != needle[neelen - 1 - s]) d2[neelen - 1 - s] = neelen - 1 - p + s;
75 }
76 }
77
str_boyermoore_suflen(char * needle,long neelen,long p)78 static long str_boyermoore_suflen(char *needle, long neelen, long p) {
79 long i;
80
81 for(i = 0; (needle[p - i] == needle[neelen - 1 - i]) && (i < p); i++) {}
82
83 return(i);
84 }
85
str_boyermoore_ispref(char * needle,long neelen,long p)86 static long str_boyermoore_ispref(char *needle, long neelen, long p) {
87 long i, k;
88
89 k = neelen - p;
90
91 for(i = 0; i < k; i++) {
92 if(needle[i] != needle[p + i]) return(0);
93 }
94
95 return(1);
96 }
97
str_bitap(char * haystack,char * needle)98 char *str_bitap(char *haystack, char *needle) {
99 int i, m;
100 unsigned long c;
101
102 unsigned long p[CHAR_MAX + 1];
103
104 m = ascii_len(needle);
105
106 if(m == 0 || m > 31) return(NULL);
107
108 c = ~1;
109
110 for(i = 0; i <= CHAR_MAX; ++i) p[i] = ~0;
111 for(i = 0; i < m; ++i) p[(int) needle[i]] &= ~(1UL << i);
112
113 for(i = 0; haystack[i] != 0; ++i) {
114 c |= p[(int) haystack[i]];
115 c <<= 1;
116
117 if(0 == (c & (1UL << m))) return(haystack + i - m) + 1;
118 }
119
120 return(NULL);
121 }
122
str_fuzzybitap(char * haystack,char * needle,int k)123 char *str_fuzzybitap(char *haystack, char *needle, int k) {
124 int i, j, m;
125 unsigned long o, t;
126
127 char *r;
128 unsigned long *c;
129
130 unsigned long p[CHAR_MAX + 1];
131
132 m = ascii_len(needle);
133
134 if(m == 0 || m > 31) return(NULL);
135 if((c = malloc((size_t) (k + 1) * sizeof(*c))) == NULL) return(NULL);
136
137 for(i = 0; i <= k; ++i) c[i] = ~1;
138 for(i = 0; i <= CHAR_MAX; ++i) p[i] = ~0;
139 for(i = 0; i < m; ++i) p[(int) needle[i]] &= ~(1UL << i);
140
141 r = NULL;
142
143 for(i = 0; haystack[i] != 0; ++i) {
144 o = c[0];
145
146 c[0] |= p[(int) haystack[i]];
147 c[0] <<= 1;
148
149 for(j = 1; j <= k; ++j) {
150 t = c[j];
151
152 c[j] = (o & (c[j] | p[(int) haystack[i]])) << 1;
153
154 o = t;
155 }
156
157 if(0 == (c[k] & (1UL << m))) {
158 r = (haystack + i - m) + 1;
159
160 break;
161 }
162 }
163
164 (void) free(c);
165
166 return(r);
167 }
168
169 /**
170 * @brief Convert integer to string.
171 *
172 * r should be long enough to contain any possible value.
173 *
174 * @param[in] n Integer to convert
175 * @param[out] r Converted string
176 * @param[in] b Base for integer to convert (2-36)
177 *
178 * @retval Pointer to converted string, same as r
179 *
180 */
181
str_itoa(int n,char * r,int b)182 char *str_itoa(int n, char *r, int b) {
183 int t;
184 char c;
185
186 char *e, *f;
187
188 e = r;
189 f = r;
190
191 if(b < 2 || b > 36) {
192 *r = 0;
193
194 return(r);
195 }
196
197 do {
198 t = n;
199 n /= b;
200
201 *e++ = itoa_str[35 + (t - (n * b))];
202 } while(n);
203
204 if(t < 0) *e++ = '-';
205
206 *e-- = 0;
207
208 while(f < e) {
209 c = *e;
210 *e-- = *f;
211 *f++ = c;
212 }
213
214 return(r);
215 }
216
217 /**
218 * @brief Locate character in string.
219 *
220 * Works exactly like system strchr(). See strchr(3).
221 *
222 * @param[in] s String
223 * @param[in] c Character to locate (converted to a char)
224 *
225 * @retval Pointer to located character
226 * @retval NULL if character was not found
227 *
228 */
229
str_chr(const char * s,int c)230 char *str_chr(const char *s, int c) {
231 return(strchr(s, c));
232 /* Disabled for now */
233 unsigned char n;
234 unsigned long m, i;
235
236 unsigned long *r;
237
238 n = (unsigned char) c;
239
240 if(!STRCHR_UNALIGN(s)) {
241 for(i = 0, m = 0; i < sizeof(long); i++) m = (m << 8) | n;
242
243 r = (unsigned long *) s;
244
245 while(!STRCHR_TSTNULL(*r) && !STRCHR_TSTCHAR(*r, m)) ++r;
246
247 s = (char *) r;
248 }
249
250 while(*s && *s != n) ++s;
251
252 if(*s == n) return((char *) s);
253
254 return(NULL);
255 }
256
257 /**
258 * @brief Make a copy of a string.
259 *
260 * Works exactly like system strdup(). See strdup(3).
261 *
262 * @param[in] s String to copy
263 * @param[in] c String character type (STRING_*)
264 *
265 * @retval Copy of a string
266 * @retval NULL on failure
267 *
268 */
269
str_dup(const char * s,unsigned int c)270 char *str_dup(const char *s, unsigned int c) {
271 (void) c;
272
273 return(strdup(s));
274 /* Disabled for now */
275 char *r;
276
277 size_t t;
278
279 /* Get string length in bytes for memcpy(), not in chars */
280 switch(c) {
281 case STRING_ASCII:
282 case STRING_UTF8:
283 t = str_len(s, STRING_ASCII);
284
285 break;
286 case STRING_UTF32:
287 t = str_len(s, STRING_UTF32) * sizeof(uint32_t);
288
289 break;
290 default:
291 (void) fprintf(
292 stderr,
293 _("String type %u is not supported by this implementation.%c"),
294 c, CONFIG_LINE_FEED
295 );
296
297 return(NULL);
298 }
299
300 APP_MALLOC_RET_VALUE(r, t + sizeof(uint32_t), NULL);
301
302 (void) memcpy((void *) r, (const void *) s, t);
303
304 r[t] = L'\0';
305
306 return(r);
307 }
308
309 /**
310 * @brief Computes the length of the string.
311 *
312 * Works exactly like system strlen(). See strlen(3).
313 *
314 * @param[in] s String
315 * @param[in] c String character type (STRING_*)
316 *
317 * @retval Number of characters in string
318 *
319 */
320
str_len(const char * s,unsigned int c)321 size_t str_len(const char *s, unsigned int c) {
322 switch(c) {
323 case STRING_ASCII:
324 return(ascii_len(s));
325 case STRING_UTF8:
326 return(utf8_len(s));
327 case STRING_UTF32:
328 return(utf32_len(s));
329 default:
330 (void) fprintf(
331 stderr,
332 _("String type %u is not supported by this implementation.%c"),
333 c, CONFIG_LINE_FEED
334 );
335
336 break;
337 }
338
339 return(0);
340 }
341 #if defined(HAVE_XMMINTRIN_H)
ascii_len(const char * s)342 static size_t ascii_len(const char *s) {
343 int m;
344
345 size_t l;
346
347 __m128i xmm0, xmm1;
348
349 l = 0;
350
351 while((((intptr_t) s) & (sizeof(__m128i) - 1)) != 0) {
352 if(*s++ == 0) return(l);
353
354 ++l;
355 }
356
357 xmm0 = _mm_setzero_si128();
358
359 for(;;) {
360 xmm1 = _mm_load_si128((__m128i *) s);
361 xmm1 = _mm_cmpeq_epi8(xmm1, xmm0);
362
363 if((m = _mm_movemask_epi8(xmm1)) != 0) {
364 #if ((__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4)))
365 l += __builtin_ctz(m);
366 #elif defined(__GNUC__) && (defined(__i386__) || (defined(__x86_64__) || defined(_M_AMD64) || defined(_M_X64)))
367 unsigned int p;
368
369 __asm__ (
370 " bsf %1, %0 \n"
371 " \n"
372 : "=r" (p)
373 : "rm" (m)
374 : "cc"
375 );
376
377 l += (size_t) p;
378 #else
379 l += (size_t) ascii_len_cb(m);
380 #endif
381 break;
382 }
383
384 s += sizeof(__m128i);
385 l += sizeof(__m128i);
386 }
387
388 return(l);
389 }
390 #else
ascii_len(const char * s)391 static size_t ascii_len(const char *s) {
392 return(strlen(s));
393 }
394 #endif
395 #if defined(IS_BIGENDIAN)
ascii_len_cb(unsigned int x)396 static int ascii_len_cb(unsigned int x) {
397 int n;
398
399 n = 0;
400
401 if(x <= 0x000000ff) {
402 n += 8;
403 x <<= 8;
404 }
405
406 if(x <= 0x00000fff) {
407 n += 4;
408 x <<= 4;
409 }
410
411 if(x <= 0x00003fff) {
412 n += 2;
413 x <<= 2;
414 }
415
416 if(x <= 0x00007fff) {
417 ++n;
418 }
419
420 return(n);
421 }
422 #else
ascii_len_cb(unsigned int x)423 static int ascii_len_cb(unsigned int x) {
424 int n;
425
426 n = 1;
427
428 if((x & 0x000000ff) == 0) {
429 n += 8;
430 x >>= 8;
431 }
432
433 if((x & 0x0000000f) == 0) {
434 n += 4;
435 x >>= 4;
436 }
437
438 if((x & 0x00000003) == 0) {
439 n += 2;
440 x >>= 2;
441 }
442
443 return(n - (x & 1));
444 }
445 #endif
utf8_len(const char * s)446 static size_t utf8_len(const char *s) {
447 unsigned char b;
448
449 const char *p;
450
451 size_t t, u;
452
453 t = 0;
454
455 for(p = s; (uintptr_t) (p) & (sizeof(size_t) - 1); p++) {
456 b = *p;
457
458 if(b == 0) goto utf8_len_done;
459
460 t += (b >> 7) & ((~b) >> 6);
461 }
462
463 for(; ; p += sizeof(size_t)) {
464 u = *(size_t *) (p);
465
466 if((u - utf8_len_mask) & (~u) & (utf8_len_mask * 0x80)) break;
467
468 u = ((u & (utf8_len_mask * 0x80)) >> 7) & ((~u) >> 6);
469
470 t += (u * utf8_len_mask) >> ((sizeof(size_t) - 1) * CHAR_BIT);
471 }
472
473 for(; ; p++) {
474 b = *p;
475
476 if(b == 0) break;
477
478 t += (b >> 7) & ((~b) >> 6);
479 }
480
481 utf8_len_done:
482
483 t = (p - s) - t;
484
485 /* Skip over byte order mark if present */
486 if(t >= 3 &&
487 (unsigned char) s[0] == 0xef && (unsigned char) s[1] == 0xbb && (unsigned char) s[2] == 0xbf) t -= 3;
488
489 return(t);
490 }
491
utf32_len(const char * s)492 static size_t utf32_len(const char *s) {
493 uint32_t *p;
494
495 size_t t;
496
497 t = 0;
498 p = (uint32_t *) s;
499
500 /* Skip over byte order mark if present */
501 if(*p == 0x0000feff || *p == 0xfffe0000) s += sizeof(uint32_t);
502
503 while(1) {
504 p = (uint32_t *) s + t;
505
506 if(*p == L'\0') break;
507
508 ++t;
509 }
510
511 return(t);
512 }
513
514 /**
515 * @brief Computes the length of the string in bytes.
516 *
517 * Works exactly like system strnlen(). See strnlen(3).
518 *
519 * @param[in] s String
520 * @param[in] n String maximum length in bytes
521 *
522 * @retval Number of bytes in string
523 *
524 */
525
strn_len(const char * s,size_t n)526 size_t strn_len(const char *s, size_t n) {
527 char *r;
528
529 r = (char *) memchr((const void *) s, 0, n);
530
531 return(r ? (size_t) (r - s) : n);
532 }
533
534 /**
535 * @brief Compare two strings securely.
536 *
537 * Compare two strings in a way that it takes exactly same time whether the strings match or not.
538 *
539 * @param[in] a First string to compare
540 * @param[in] b Second string to compare
541 *
542 * @retval Zero if strings are equal, nonzero if not
543 *
544 */
545
str_cmp_secure(const char * a,const char * b)546 int str_cmp_secure(const char *a, const char *b) {
547 size_t i, e, f, r;
548
549 e = str_len(a, STRING_ASCII);
550 f = str_len(b, STRING_ASCII);
551
552 r = e ^ f;
553 #if defined(HAVE_TIMINGSAFE_BCMP)
554 i = VALUE_MIN2(e, f);
555
556 r |= timingsafe_bcmp((const void *) a, (const void *) b, i);
557 #elif defined(HAVE_TIMINGSAFE_MEMCMP)
558 i = VALUE_MIN2(e, f);
559
560 r |= timingsafe_memcmp((const void *) a, (const void *) b, i);
561 #elif defined(HAVE_CONSTTIME_MEMEQUAL)
562 i = VALUE_MIN2(e, f);
563
564 r |= !consttime_memequal((void *) a, (void *) b, i);
565 #else
566 for(i = 0; i < e && i < f; i++) r |= (a[i] ^ b[i]);
567 #endif
568 return((r != 0) ? 1 : 0);
569 }
570
571 /**
572 * @brief Clear string securely.
573 *
574 * Clear string in a way that it is guaranteed not optimized away by the compiler.
575 *
576 * @param[in] s String to clear
577 *
578 */
579
str_zero_secure(char * s)580 void str_zero_secure(char *s) {
581 #if defined(HAVE_EXPLICIT_BZERO)
582 (void) explicit_bzero((void *) s, str_len(s, STRING_ASCII));
583 #elif defined(HAVE_EXPLICIT_MEMSET)
584 (void) explicit_memset((void *) s, 0, str_len(s, STRING_ASCII));
585 #else
586 (void) s;
587
588 LOGWARN(
589 ERROR_FATAL, SUBSYSTEM,
590 _("Mandatory explicit_[bzero|memset]() function calls are not supported by this implementation (%s)"),
591 CONFIG_MACH
592 );
593 #endif
594 }
595