1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  *  linux/lib/string.c
4  *
5  *  Copyright (C) 1991, 1992  Linus Torvalds
6  */
7 
8 /*
9  * This file should be used only for "library" routines that may have
10  * alternative implementations on specific architectures (generally
11  * found in <asm-xx/string.h>), or get overloaded by FORTIFY_SOURCE.
12  * (Specifically, this file is built with __NO_FORTIFY.)
13  *
14  * Other helper functions should live in string_helpers.c.
15  */
16 
17 #define __NO_FORTIFY
18 #include <linux/types.h>
19 #include <linux/string.h>
20 #include <linux/ctype.h>
21 #include <linux/kernel.h>
22 #include <linux/export.h>
23 #include <linux/bug.h>
24 #include <linux/errno.h>
25 #include <linux/slab.h>
26 
27 #include <asm/unaligned.h>
28 #include <asm/byteorder.h>
29 #include <asm/word-at-a-time.h>
30 #include <asm/page.h>
31 
32 #ifndef __HAVE_ARCH_STRNCASECMP
33 /**
34  * strncasecmp - Case insensitive, length-limited string comparison
35  * @s1: One string
36  * @s2: The other string
37  * @len: the maximum number of characters to compare
38  */
strncasecmp(const char * s1,const char * s2,size_t len)39 int strncasecmp(const char *s1, const char *s2, size_t len)
40 {
41 	/* Yes, Virginia, it had better be unsigned */
42 	unsigned char c1, c2;
43 
44 	if (!len)
45 		return 0;
46 
47 	do {
48 		c1 = *s1++;
49 		c2 = *s2++;
50 		if (!c1 || !c2)
51 			break;
52 		if (c1 == c2)
53 			continue;
54 		c1 = tolower(c1);
55 		c2 = tolower(c2);
56 		if (c1 != c2)
57 			break;
58 	} while (--len);
59 	return (int)c1 - (int)c2;
60 }
61 EXPORT_SYMBOL(strncasecmp);
62 #endif
63 
64 #ifndef __HAVE_ARCH_STRCASECMP
strcasecmp(const char * s1,const char * s2)65 int strcasecmp(const char *s1, const char *s2)
66 {
67 	int c1, c2;
68 
69 	do {
70 		c1 = tolower(*s1++);
71 		c2 = tolower(*s2++);
72 	} while (c1 == c2 && c1 != 0);
73 	return c1 - c2;
74 }
75 EXPORT_SYMBOL(strcasecmp);
76 #endif
77 
78 #ifndef __HAVE_ARCH_STRCPY
strcpy(char * dest,const char * src)79 char *strcpy(char *dest, const char *src)
80 {
81 	char *tmp = dest;
82 
83 	while ((*dest++ = *src++) != '\0')
84 		/* nothing */;
85 	return tmp;
86 }
87 EXPORT_SYMBOL(strcpy);
88 #endif
89 
90 #ifndef __HAVE_ARCH_STRNCPY
strncpy(char * dest,const char * src,size_t count)91 char *strncpy(char *dest, const char *src, size_t count)
92 {
93 	char *tmp = dest;
94 
95 	while (count) {
96 		if ((*tmp = *src) != 0)
97 			src++;
98 		tmp++;
99 		count--;
100 	}
101 	return dest;
102 }
103 EXPORT_SYMBOL(strncpy);
104 #endif
105 
106 #ifndef __HAVE_ARCH_STRLCPY
strlcpy(char * dest,const char * src,size_t size)107 size_t strlcpy(char *dest, const char *src, size_t size)
108 {
109 	size_t ret = strlen(src);
110 
111 	if (size) {
112 		size_t len = (ret >= size) ? size - 1 : ret;
113 		__builtin_memcpy(dest, src, len);
114 		dest[len] = '\0';
115 	}
116 	return ret;
117 }
118 EXPORT_SYMBOL(strlcpy);
119 #endif
120 
121 #ifndef __HAVE_ARCH_STRSCPY
strscpy(char * dest,const char * src,size_t count)122 ssize_t strscpy(char *dest, const char *src, size_t count)
123 {
124 	const struct word_at_a_time constants = WORD_AT_A_TIME_CONSTANTS;
125 	size_t max = count;
126 	long res = 0;
127 
128 	if (count == 0 || WARN_ON_ONCE(count > INT_MAX))
129 		return -E2BIG;
130 
131 #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
132 	/*
133 	 * If src is unaligned, don't cross a page boundary,
134 	 * since we don't know if the next page is mapped.
135 	 */
136 	if ((long)src & (sizeof(long) - 1)) {
137 		size_t limit = PAGE_SIZE - ((long)src & (PAGE_SIZE - 1));
138 		if (limit < max)
139 			max = limit;
140 	}
141 #else
142 	/* If src or dest is unaligned, don't do word-at-a-time. */
143 	if (((long) dest | (long) src) & (sizeof(long) - 1))
144 		max = 0;
145 #endif
146 
147 	/*
148 	 * read_word_at_a_time() below may read uninitialized bytes after the
149 	 * trailing zero and use them in comparisons. Disable this optimization
150 	 * under KMSAN to prevent false positive reports.
151 	 */
152 	if (IS_ENABLED(CONFIG_KMSAN))
153 		max = 0;
154 
155 	while (max >= sizeof(unsigned long)) {
156 		unsigned long c, data;
157 
158 		c = read_word_at_a_time(src+res);
159 		if (has_zero(c, &data, &constants)) {
160 			data = prep_zero_mask(c, data, &constants);
161 			data = create_zero_mask(data);
162 			*(unsigned long *)(dest+res) = c & zero_bytemask(data);
163 			return res + find_zero(data);
164 		}
165 		*(unsigned long *)(dest+res) = c;
166 		res += sizeof(unsigned long);
167 		count -= sizeof(unsigned long);
168 		max -= sizeof(unsigned long);
169 	}
170 
171 	while (count) {
172 		char c;
173 
174 		c = src[res];
175 		dest[res] = c;
176 		if (!c)
177 			return res;
178 		res++;
179 		count--;
180 	}
181 
182 	/* Hit buffer length without finding a NUL; force NUL-termination. */
183 	if (res)
184 		dest[res-1] = '\0';
185 
186 	return -E2BIG;
187 }
188 EXPORT_SYMBOL(strscpy);
189 #endif
190 
191 /**
192  * stpcpy - copy a string from src to dest returning a pointer to the new end
193  *          of dest, including src's %NUL-terminator. May overrun dest.
194  * @dest: pointer to end of string being copied into. Must be large enough
195  *        to receive copy.
196  * @src: pointer to the beginning of string being copied from. Must not overlap
197  *       dest.
198  *
199  * stpcpy differs from strcpy in a key way: the return value is a pointer
200  * to the new %NUL-terminating character in @dest. (For strcpy, the return
201  * value is a pointer to the start of @dest). This interface is considered
202  * unsafe as it doesn't perform bounds checking of the inputs. As such it's
203  * not recommended for usage. Instead, its definition is provided in case
204  * the compiler lowers other libcalls to stpcpy.
205  */
206 char *stpcpy(char *__restrict__ dest, const char *__restrict__ src);
stpcpy(char * __restrict__ dest,const char * __restrict__ src)207 char *stpcpy(char *__restrict__ dest, const char *__restrict__ src)
208 {
209 	while ((*dest++ = *src++) != '\0')
210 		/* nothing */;
211 	return --dest;
212 }
213 EXPORT_SYMBOL(stpcpy);
214 
215 #ifndef __HAVE_ARCH_STRCAT
strcat(char * dest,const char * src)216 char *strcat(char *dest, const char *src)
217 {
218 	char *tmp = dest;
219 
220 	while (*dest)
221 		dest++;
222 	while ((*dest++ = *src++) != '\0')
223 		;
224 	return tmp;
225 }
226 EXPORT_SYMBOL(strcat);
227 #endif
228 
229 #ifndef __HAVE_ARCH_STRNCAT
strncat(char * dest,const char * src,size_t count)230 char *strncat(char *dest, const char *src, size_t count)
231 {
232 	char *tmp = dest;
233 
234 	if (count) {
235 		while (*dest)
236 			dest++;
237 		while ((*dest++ = *src++) != 0) {
238 			if (--count == 0) {
239 				*dest = '\0';
240 				break;
241 			}
242 		}
243 	}
244 	return tmp;
245 }
246 EXPORT_SYMBOL(strncat);
247 #endif
248 
249 #ifndef __HAVE_ARCH_STRLCAT
strlcat(char * dest,const char * src,size_t count)250 size_t strlcat(char *dest, const char *src, size_t count)
251 {
252 	size_t dsize = strlen(dest);
253 	size_t len = strlen(src);
254 	size_t res = dsize + len;
255 
256 	/* This would be a bug */
257 	BUG_ON(dsize >= count);
258 
259 	dest += dsize;
260 	count -= dsize;
261 	if (len >= count)
262 		len = count-1;
263 	__builtin_memcpy(dest, src, len);
264 	dest[len] = 0;
265 	return res;
266 }
267 EXPORT_SYMBOL(strlcat);
268 #endif
269 
270 #ifndef __HAVE_ARCH_STRCMP
271 /**
272  * strcmp - Compare two strings
273  * @cs: One string
274  * @ct: Another string
275  */
strcmp(const char * cs,const char * ct)276 int strcmp(const char *cs, const char *ct)
277 {
278 	unsigned char c1, c2;
279 
280 	while (1) {
281 		c1 = *cs++;
282 		c2 = *ct++;
283 		if (c1 != c2)
284 			return c1 < c2 ? -1 : 1;
285 		if (!c1)
286 			break;
287 	}
288 	return 0;
289 }
290 EXPORT_SYMBOL(strcmp);
291 #endif
292 
293 #ifndef __HAVE_ARCH_STRNCMP
294 /**
295  * strncmp - Compare two length-limited strings
296  * @cs: One string
297  * @ct: Another string
298  * @count: The maximum number of bytes to compare
299  */
strncmp(const char * cs,const char * ct,size_t count)300 int strncmp(const char *cs, const char *ct, size_t count)
301 {
302 	unsigned char c1, c2;
303 
304 	while (count) {
305 		c1 = *cs++;
306 		c2 = *ct++;
307 		if (c1 != c2)
308 			return c1 < c2 ? -1 : 1;
309 		if (!c1)
310 			break;
311 		count--;
312 	}
313 	return 0;
314 }
315 EXPORT_SYMBOL(strncmp);
316 #endif
317 
318 #ifndef __HAVE_ARCH_STRCHR
319 /**
320  * strchr - Find the first occurrence of a character in a string
321  * @s: The string to be searched
322  * @c: The character to search for
323  *
324  * Note that the %NUL-terminator is considered part of the string, and can
325  * be searched for.
326  */
strchr(const char * s,int c)327 char *strchr(const char *s, int c)
328 {
329 	for (; *s != (char)c; ++s)
330 		if (*s == '\0')
331 			return NULL;
332 	return (char *)s;
333 }
334 EXPORT_SYMBOL(strchr);
335 #endif
336 
337 #ifndef __HAVE_ARCH_STRCHRNUL
338 /**
339  * strchrnul - Find and return a character in a string, or end of string
340  * @s: The string to be searched
341  * @c: The character to search for
342  *
343  * Returns pointer to first occurrence of 'c' in s. If c is not found, then
344  * return a pointer to the null byte at the end of s.
345  */
strchrnul(const char * s,int c)346 char *strchrnul(const char *s, int c)
347 {
348 	while (*s && *s != (char)c)
349 		s++;
350 	return (char *)s;
351 }
352 EXPORT_SYMBOL(strchrnul);
353 #endif
354 
355 /**
356  * strnchrnul - Find and return a character in a length limited string,
357  * or end of string
358  * @s: The string to be searched
359  * @count: The number of characters to be searched
360  * @c: The character to search for
361  *
362  * Returns pointer to the first occurrence of 'c' in s. If c is not found,
363  * then return a pointer to the last character of the string.
364  */
strnchrnul(const char * s,size_t count,int c)365 char *strnchrnul(const char *s, size_t count, int c)
366 {
367 	while (count-- && *s && *s != (char)c)
368 		s++;
369 	return (char *)s;
370 }
371 
372 #ifndef __HAVE_ARCH_STRRCHR
373 /**
374  * strrchr - Find the last occurrence of a character in a string
375  * @s: The string to be searched
376  * @c: The character to search for
377  */
strrchr(const char * s,int c)378 char *strrchr(const char *s, int c)
379 {
380 	const char *last = NULL;
381 	do {
382 		if (*s == (char)c)
383 			last = s;
384 	} while (*s++);
385 	return (char *)last;
386 }
387 EXPORT_SYMBOL(strrchr);
388 #endif
389 
390 #ifndef __HAVE_ARCH_STRNCHR
391 /**
392  * strnchr - Find a character in a length limited string
393  * @s: The string to be searched
394  * @count: The number of characters to be searched
395  * @c: The character to search for
396  *
397  * Note that the %NUL-terminator is considered part of the string, and can
398  * be searched for.
399  */
strnchr(const char * s,size_t count,int c)400 char *strnchr(const char *s, size_t count, int c)
401 {
402 	while (count--) {
403 		if (*s == (char)c)
404 			return (char *)s;
405 		if (*s++ == '\0')
406 			break;
407 	}
408 	return NULL;
409 }
410 EXPORT_SYMBOL(strnchr);
411 #endif
412 
413 #ifndef __HAVE_ARCH_STRLEN
strlen(const char * s)414 size_t strlen(const char *s)
415 {
416 	const char *sc;
417 
418 	for (sc = s; *sc != '\0'; ++sc)
419 		/* nothing */;
420 	return sc - s;
421 }
422 EXPORT_SYMBOL(strlen);
423 #endif
424 
425 #ifndef __HAVE_ARCH_STRNLEN
strnlen(const char * s,size_t count)426 size_t strnlen(const char *s, size_t count)
427 {
428 	const char *sc;
429 
430 	for (sc = s; count-- && *sc != '\0'; ++sc)
431 		/* nothing */;
432 	return sc - s;
433 }
434 EXPORT_SYMBOL(strnlen);
435 #endif
436 
437 #ifndef __HAVE_ARCH_STRSPN
438 /**
439  * strspn - Calculate the length of the initial substring of @s which only contain letters in @accept
440  * @s: The string to be searched
441  * @accept: The string to search for
442  */
strspn(const char * s,const char * accept)443 size_t strspn(const char *s, const char *accept)
444 {
445 	const char *p;
446 
447 	for (p = s; *p != '\0'; ++p) {
448 		if (!strchr(accept, *p))
449 			break;
450 	}
451 	return p - s;
452 }
453 EXPORT_SYMBOL(strspn);
454 #endif
455 
456 #ifndef __HAVE_ARCH_STRCSPN
457 /**
458  * strcspn - Calculate the length of the initial substring of @s which does not contain letters in @reject
459  * @s: The string to be searched
460  * @reject: The string to avoid
461  */
strcspn(const char * s,const char * reject)462 size_t strcspn(const char *s, const char *reject)
463 {
464 	const char *p;
465 
466 	for (p = s; *p != '\0'; ++p) {
467 		if (strchr(reject, *p))
468 			break;
469 	}
470 	return p - s;
471 }
472 EXPORT_SYMBOL(strcspn);
473 #endif
474 
475 #ifndef __HAVE_ARCH_STRPBRK
476 /**
477  * strpbrk - Find the first occurrence of a set of characters
478  * @cs: The string to be searched
479  * @ct: The characters to search for
480  */
strpbrk(const char * cs,const char * ct)481 char *strpbrk(const char *cs, const char *ct)
482 {
483 	const char *sc;
484 
485 	for (sc = cs; *sc != '\0'; ++sc) {
486 		if (strchr(ct, *sc))
487 			return (char *)sc;
488 	}
489 	return NULL;
490 }
491 EXPORT_SYMBOL(strpbrk);
492 #endif
493 
494 #ifndef __HAVE_ARCH_STRSEP
495 /**
496  * strsep - Split a string into tokens
497  * @s: The string to be searched
498  * @ct: The characters to search for
499  *
500  * strsep() updates @s to point after the token, ready for the next call.
501  *
502  * It returns empty tokens, too, behaving exactly like the libc function
503  * of that name. In fact, it was stolen from glibc2 and de-fancy-fied.
504  * Same semantics, slimmer shape. ;)
505  */
strsep(char ** s,const char * ct)506 char *strsep(char **s, const char *ct)
507 {
508 	char *sbegin = *s;
509 	char *end;
510 
511 	if (sbegin == NULL)
512 		return NULL;
513 
514 	end = strpbrk(sbegin, ct);
515 	if (end)
516 		*end++ = '\0';
517 	*s = end;
518 	return sbegin;
519 }
520 EXPORT_SYMBOL(strsep);
521 #endif
522 
523 #ifndef __HAVE_ARCH_MEMSET
524 /**
525  * memset - Fill a region of memory with the given value
526  * @s: Pointer to the start of the area.
527  * @c: The byte to fill the area with
528  * @count: The size of the area.
529  *
530  * Do not use memset() to access IO space, use memset_io() instead.
531  */
memset(void * s,int c,size_t count)532 void *memset(void *s, int c, size_t count)
533 {
534 	char *xs = s;
535 
536 	while (count--)
537 		*xs++ = c;
538 	return s;
539 }
540 EXPORT_SYMBOL(memset);
541 #endif
542 
543 #ifndef __HAVE_ARCH_MEMSET16
544 /**
545  * memset16() - Fill a memory area with a uint16_t
546  * @s: Pointer to the start of the area.
547  * @v: The value to fill the area with
548  * @count: The number of values to store
549  *
550  * Differs from memset() in that it fills with a uint16_t instead
551  * of a byte.  Remember that @count is the number of uint16_ts to
552  * store, not the number of bytes.
553  */
memset16(uint16_t * s,uint16_t v,size_t count)554 void *memset16(uint16_t *s, uint16_t v, size_t count)
555 {
556 	uint16_t *xs = s;
557 
558 	while (count--)
559 		*xs++ = v;
560 	return s;
561 }
562 EXPORT_SYMBOL(memset16);
563 #endif
564 
565 #ifndef __HAVE_ARCH_MEMSET32
566 /**
567  * memset32() - Fill a memory area with a uint32_t
568  * @s: Pointer to the start of the area.
569  * @v: The value to fill the area with
570  * @count: The number of values to store
571  *
572  * Differs from memset() in that it fills with a uint32_t instead
573  * of a byte.  Remember that @count is the number of uint32_ts to
574  * store, not the number of bytes.
575  */
memset32(uint32_t * s,uint32_t v,size_t count)576 void *memset32(uint32_t *s, uint32_t v, size_t count)
577 {
578 	uint32_t *xs = s;
579 
580 	while (count--)
581 		*xs++ = v;
582 	return s;
583 }
584 EXPORT_SYMBOL(memset32);
585 #endif
586 
587 #ifndef __HAVE_ARCH_MEMSET64
588 /**
589  * memset64() - Fill a memory area with a uint64_t
590  * @s: Pointer to the start of the area.
591  * @v: The value to fill the area with
592  * @count: The number of values to store
593  *
594  * Differs from memset() in that it fills with a uint64_t instead
595  * of a byte.  Remember that @count is the number of uint64_ts to
596  * store, not the number of bytes.
597  */
memset64(uint64_t * s,uint64_t v,size_t count)598 void *memset64(uint64_t *s, uint64_t v, size_t count)
599 {
600 	uint64_t *xs = s;
601 
602 	while (count--)
603 		*xs++ = v;
604 	return s;
605 }
606 EXPORT_SYMBOL(memset64);
607 #endif
608 
609 #ifndef __HAVE_ARCH_MEMCPY
610 /**
611  * memcpy - Copy one area of memory to another
612  * @dest: Where to copy to
613  * @src: Where to copy from
614  * @count: The size of the area.
615  *
616  * You should not use this function to access IO space, use memcpy_toio()
617  * or memcpy_fromio() instead.
618  */
memcpy(void * dest,const void * src,size_t count)619 void *memcpy(void *dest, const void *src, size_t count)
620 {
621 	char *tmp = dest;
622 	const char *s = src;
623 
624 	while (count--)
625 		*tmp++ = *s++;
626 	return dest;
627 }
628 EXPORT_SYMBOL(memcpy);
629 #endif
630 
631 #ifndef __HAVE_ARCH_MEMMOVE
632 /**
633  * memmove - Copy one area of memory to another
634  * @dest: Where to copy to
635  * @src: Where to copy from
636  * @count: The size of the area.
637  *
638  * Unlike memcpy(), memmove() copes with overlapping areas.
639  */
memmove(void * dest,const void * src,size_t count)640 void *memmove(void *dest, const void *src, size_t count)
641 {
642 	char *tmp;
643 	const char *s;
644 
645 	if (dest <= src) {
646 		tmp = dest;
647 		s = src;
648 		while (count--)
649 			*tmp++ = *s++;
650 	} else {
651 		tmp = dest;
652 		tmp += count;
653 		s = src;
654 		s += count;
655 		while (count--)
656 			*--tmp = *--s;
657 	}
658 	return dest;
659 }
660 EXPORT_SYMBOL(memmove);
661 #endif
662 
663 #ifndef __HAVE_ARCH_MEMCMP
664 /**
665  * memcmp - Compare two areas of memory
666  * @cs: One area of memory
667  * @ct: Another area of memory
668  * @count: The size of the area.
669  */
670 #undef memcmp
memcmp(const void * cs,const void * ct,size_t count)671 __visible int memcmp(const void *cs, const void *ct, size_t count)
672 {
673 	const unsigned char *su1, *su2;
674 	int res = 0;
675 
676 #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
677 	if (count >= sizeof(unsigned long)) {
678 		const unsigned long *u1 = cs;
679 		const unsigned long *u2 = ct;
680 		do {
681 			if (get_unaligned(u1) != get_unaligned(u2))
682 				break;
683 			u1++;
684 			u2++;
685 			count -= sizeof(unsigned long);
686 		} while (count >= sizeof(unsigned long));
687 		cs = u1;
688 		ct = u2;
689 	}
690 #endif
691 	for (su1 = cs, su2 = ct; 0 < count; ++su1, ++su2, count--)
692 		if ((res = *su1 - *su2) != 0)
693 			break;
694 	return res;
695 }
696 EXPORT_SYMBOL(memcmp);
697 #endif
698 
699 #ifndef __HAVE_ARCH_BCMP
700 /**
701  * bcmp - returns 0 if and only if the buffers have identical contents.
702  * @a: pointer to first buffer.
703  * @b: pointer to second buffer.
704  * @len: size of buffers.
705  *
706  * The sign or magnitude of a non-zero return value has no particular
707  * meaning, and architectures may implement their own more efficient bcmp(). So
708  * while this particular implementation is a simple (tail) call to memcmp, do
709  * not rely on anything but whether the return value is zero or non-zero.
710  */
bcmp(const void * a,const void * b,size_t len)711 int bcmp(const void *a, const void *b, size_t len)
712 {
713 	return memcmp(a, b, len);
714 }
715 EXPORT_SYMBOL(bcmp);
716 #endif
717 
718 #ifndef __HAVE_ARCH_MEMSCAN
719 /**
720  * memscan - Find a character in an area of memory.
721  * @addr: The memory area
722  * @c: The byte to search for
723  * @size: The size of the area.
724  *
725  * returns the address of the first occurrence of @c, or 1 byte past
726  * the area if @c is not found
727  */
memscan(void * addr,int c,size_t size)728 void *memscan(void *addr, int c, size_t size)
729 {
730 	unsigned char *p = addr;
731 
732 	while (size) {
733 		if (*p == (unsigned char)c)
734 			return (void *)p;
735 		p++;
736 		size--;
737 	}
738   	return (void *)p;
739 }
740 EXPORT_SYMBOL(memscan);
741 #endif
742 
743 #ifndef __HAVE_ARCH_STRSTR
744 /**
745  * strstr - Find the first substring in a %NUL terminated string
746  * @s1: The string to be searched
747  * @s2: The string to search for
748  */
strstr(const char * s1,const char * s2)749 char *strstr(const char *s1, const char *s2)
750 {
751 	size_t l1, l2;
752 
753 	l2 = strlen(s2);
754 	if (!l2)
755 		return (char *)s1;
756 	l1 = strlen(s1);
757 	while (l1 >= l2) {
758 		l1--;
759 		if (!memcmp(s1, s2, l2))
760 			return (char *)s1;
761 		s1++;
762 	}
763 	return NULL;
764 }
765 EXPORT_SYMBOL(strstr);
766 #endif
767 
768 #ifndef __HAVE_ARCH_STRNSTR
769 /**
770  * strnstr - Find the first substring in a length-limited string
771  * @s1: The string to be searched
772  * @s2: The string to search for
773  * @len: the maximum number of characters to search
774  */
strnstr(const char * s1,const char * s2,size_t len)775 char *strnstr(const char *s1, const char *s2, size_t len)
776 {
777 	size_t l2;
778 
779 	l2 = strlen(s2);
780 	if (!l2)
781 		return (char *)s1;
782 	while (len >= l2) {
783 		len--;
784 		if (!memcmp(s1, s2, l2))
785 			return (char *)s1;
786 		s1++;
787 	}
788 	return NULL;
789 }
790 EXPORT_SYMBOL(strnstr);
791 #endif
792 
793 #ifndef __HAVE_ARCH_MEMCHR
794 /**
795  * memchr - Find a character in an area of memory.
796  * @s: The memory area
797  * @c: The byte to search for
798  * @n: The size of the area.
799  *
800  * returns the address of the first occurrence of @c, or %NULL
801  * if @c is not found
802  */
memchr(const void * s,int c,size_t n)803 void *memchr(const void *s, int c, size_t n)
804 {
805 	const unsigned char *p = s;
806 	while (n-- != 0) {
807         	if ((unsigned char)c == *p++) {
808 			return (void *)(p - 1);
809 		}
810 	}
811 	return NULL;
812 }
813 EXPORT_SYMBOL(memchr);
814 #endif
815 
check_bytes8(const u8 * start,u8 value,unsigned int bytes)816 static void *check_bytes8(const u8 *start, u8 value, unsigned int bytes)
817 {
818 	while (bytes) {
819 		if (*start != value)
820 			return (void *)start;
821 		start++;
822 		bytes--;
823 	}
824 	return NULL;
825 }
826 
827 /**
828  * memchr_inv - Find an unmatching character in an area of memory.
829  * @start: The memory area
830  * @c: Find a character other than c
831  * @bytes: The size of the area.
832  *
833  * returns the address of the first character other than @c, or %NULL
834  * if the whole buffer contains just @c.
835  */
memchr_inv(const void * start,int c,size_t bytes)836 void *memchr_inv(const void *start, int c, size_t bytes)
837 {
838 	u8 value = c;
839 	u64 value64;
840 	unsigned int words, prefix;
841 
842 	if (bytes <= 16)
843 		return check_bytes8(start, value, bytes);
844 
845 	value64 = value;
846 #if defined(CONFIG_ARCH_HAS_FAST_MULTIPLIER) && BITS_PER_LONG == 64
847 	value64 *= 0x0101010101010101ULL;
848 #elif defined(CONFIG_ARCH_HAS_FAST_MULTIPLIER)
849 	value64 *= 0x01010101;
850 	value64 |= value64 << 32;
851 #else
852 	value64 |= value64 << 8;
853 	value64 |= value64 << 16;
854 	value64 |= value64 << 32;
855 #endif
856 
857 	prefix = (unsigned long)start % 8;
858 	if (prefix) {
859 		u8 *r;
860 
861 		prefix = 8 - prefix;
862 		r = check_bytes8(start, value, prefix);
863 		if (r)
864 			return r;
865 		start += prefix;
866 		bytes -= prefix;
867 	}
868 
869 	words = bytes / 8;
870 
871 	while (words) {
872 		if (*(u64 *)start != value64)
873 			return check_bytes8(start, value, 8);
874 		start += 8;
875 		words--;
876 	}
877 
878 	return check_bytes8(start, value, bytes % 8);
879 }
880 EXPORT_SYMBOL(memchr_inv);
881