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