lib/string.c

   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  */
  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
  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
  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
  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
 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                 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
 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);
 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
 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
 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
 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         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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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
 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
 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  */
 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  */
 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  */
 481 char *strpbrk(const char *cs, const char *ct)
 482 {
 483         const char *sc1, *sc2;
 484
 485         for (sc1 = cs; *sc1 != '\0'; ++sc1) {
 486                 for (sc2 = ct; *sc2 != '\0'; ++sc2) {
 487                         if (*sc1 == *sc2)
 488                                 return (char *)sc1;
 489                 }
 490         }
 491         return NULL;
 492 }
 493 EXPORT_SYMBOL(strpbrk);
 494 #endif
 495
 496 #ifndef __HAVE_ARCH_STRSEP
 497 /**
 498  * strsep - Split a string into tokens
 499  * @s: The string to be searched
 500  * @ct: The characters to search for
 501  *
 502  * strsep() updates @s to point after the token, ready for the next call.
 503  *
 504  * It returns empty tokens, too, behaving exactly like the libc function
 505  * of that name. In fact, it was stolen from glibc2 and de-fancy-fied.
 506  * Same semantics, slimmer shape. ;)
 507  */
 508 char *strsep(char **s, const char *ct)
 509 {
 510         char *sbegin = *s;
 511         char *end;
 512
 513         if (sbegin == NULL)
 514                 return NULL;
 515
 516         end = strpbrk(sbegin, ct);
 517         if (end)
 518                 *end++ = '\0';
 519         *s = end;
 520         return sbegin;
 521 }
 522 EXPORT_SYMBOL(strsep);
 523 #endif
 524
 525 #ifndef __HAVE_ARCH_MEMSET
 526 /**
 527  * memset - Fill a region of memory with the given value
 528  * @s: Pointer to the start of the area.
 529  * @c: The byte to fill the area with
 530  * @count: The size of the area.
 531  *
 532  * Do not use memset() to access IO space, use memset_io() instead.
 533  */
 534 void *memset(void *s, int c, size_t count)
 535 {
 536         char *xs = s;
 537
 538         while (count--)
 539                 *xs++ = c;
 540         return s;
 541 }
 542 EXPORT_SYMBOL(memset);
 543 #endif
 544
 545 #ifndef __HAVE_ARCH_MEMSET16
 546 /**
 547  * memset16() - Fill a memory area with a uint16_t
 548  * @s: Pointer to the start of the area.
 549  * @v: The value to fill the area with
 550  * @count: The number of values to store
 551  *
 552  * Differs from memset() in that it fills with a uint16_t instead
 553  * of a byte.  Remember that @count is the number of uint16_ts to
 554  * store, not the number of bytes.
 555  */
 556 void *memset16(uint16_t *s, uint16_t v, size_t count)
 557 {
 558         uint16_t *xs = s;
 559
 560         while (count--)
 561                 *xs++ = v;
 562         return s;
 563 }
 564 EXPORT_SYMBOL(memset16);
 565 #endif
 566
 567 #ifndef __HAVE_ARCH_MEMSET32
 568 /**
 569  * memset32() - Fill a memory area with a uint32_t
 570  * @s: Pointer to the start of the area.
 571  * @v: The value to fill the area with
 572  * @count: The number of values to store
 573  *
 574  * Differs from memset() in that it fills with a uint32_t instead
 575  * of a byte.  Remember that @count is the number of uint32_ts to
 576  * store, not the number of bytes.
 577  */
 578 void *memset32(uint32_t *s, uint32_t v, size_t count)
 579 {
 580         uint32_t *xs = s;
 581
 582         while (count--)
 583                 *xs++ = v;
 584         return s;
 585 }
 586 EXPORT_SYMBOL(memset32);
 587 #endif
 588
 589 #ifndef __HAVE_ARCH_MEMSET64
 590 /**
 591  * memset64() - Fill a memory area with a uint64_t
 592  * @s: Pointer to the start of the area.
 593  * @v: The value to fill the area with
 594  * @count: The number of values to store
 595  *
 596  * Differs from memset() in that it fills with a uint64_t instead
 597  * of a byte.  Remember that @count is the number of uint64_ts to
 598  * store, not the number of bytes.
 599  */
 600 void *memset64(uint64_t *s, uint64_t v, size_t count)
 601 {
 602         uint64_t *xs = s;
 603
 604         while (count--)
 605                 *xs++ = v;
 606         return s;
 607 }
 608 EXPORT_SYMBOL(memset64);
 609 #endif
 610
 611 #ifndef __HAVE_ARCH_MEMCPY
 612 /**
 613  * memcpy - Copy one area of memory to another
 614  * @dest: Where to copy to
 615  * @src: Where to copy from
 616  * @count: The size of the area.
 617  *
 618  * You should not use this function to access IO space, use memcpy_toio()
 619  * or memcpy_fromio() instead.
 620  */
 621 void *memcpy(void *dest, const void *src, size_t count)
 622 {
 623         char *tmp = dest;
 624         const char *s = src;
 625
 626         while (count--)
 627                 *tmp++ = *s++;
 628         return dest;
 629 }
 630 EXPORT_SYMBOL(memcpy);
 631 #endif
 632
 633 #ifndef __HAVE_ARCH_MEMMOVE
 634 /**
 635  * memmove - Copy one area of memory to another
 636  * @dest: Where to copy to
 637  * @src: Where to copy from
 638  * @count: The size of the area.
 639  *
 640  * Unlike memcpy(), memmove() copes with overlapping areas.
 641  */
 642 void *memmove(void *dest, const void *src, size_t count)
 643 {
 644         char *tmp;
 645         const char *s;
 646
 647         if (dest <= src) {
 648                 tmp = dest;
 649                 s = src;
 650                 while (count--)
 651                         *tmp++ = *s++;
 652         } else {
 653                 tmp = dest;
 654                 tmp += count;
 655                 s = src;
 656                 s += count;
 657                 while (count--)
 658                         *--tmp = *--s;
 659         }
 660         return dest;
 661 }
 662 EXPORT_SYMBOL(memmove);
 663 #endif
 664
 665 #ifndef __HAVE_ARCH_MEMCMP
 666 /**
 667  * memcmp - Compare two areas of memory
 668  * @cs: One area of memory
 669  * @ct: Another area of memory
 670  * @count: The size of the area.
 671  */
 672 #undef memcmp
 673 __visible int memcmp(const void *cs, const void *ct, size_t count)
 674 {
 675         const unsigned char *su1, *su2;
 676         int res = 0;
 677
 678 #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
 679         if (count >= sizeof(unsigned long)) {
 680                 const unsigned long *u1 = cs;
 681                 const unsigned long *u2 = ct;
 682                 do {
 683                         if (get_unaligned(u1) != get_unaligned(u2))
 684                                 break;
 685                         u1++;
 686                         u2++;
 687                         count -= sizeof(unsigned long);
 688                 } while (count >= sizeof(unsigned long));
 689                 cs = u1;
 690                 ct = u2;
 691         }
 692 #endif
 693         for (su1 = cs, su2 = ct; 0 < count; ++su1, ++su2, count--)
 694                 if ((res = *su1 - *su2) != 0)
 695                         break;
 696         return res;
 697 }
 698 EXPORT_SYMBOL(memcmp);
 699 #endif
 700
 701 #ifndef __HAVE_ARCH_BCMP
 702 /**
 703  * bcmp - returns 0 if and only if the buffers have identical contents.
 704  * @a: pointer to first buffer.
 705  * @b: pointer to second buffer.
 706  * @len: size of buffers.
 707  *
 708  * The sign or magnitude of a non-zero return value has no particular
 709  * meaning, and architectures may implement their own more efficient bcmp(). So
 710  * while this particular implementation is a simple (tail) call to memcmp, do
 711  * not rely on anything but whether the return value is zero or non-zero.
 712  */
 713 int bcmp(const void *a, const void *b, size_t len)
 714 {
 715         return memcmp(a, b, len);
 716 }
 717 EXPORT_SYMBOL(bcmp);
 718 #endif
 719
 720 #ifndef __HAVE_ARCH_MEMSCAN
 721 /**
 722  * memscan - Find a character in an area of memory.
 723  * @addr: The memory area
 724  * @c: The byte to search for
 725  * @size: The size of the area.
 726  *
 727  * returns the address of the first occurrence of @c, or 1 byte past
 728  * the area if @c is not found
 729  */
 730 void *memscan(void *addr, int c, size_t size)
 731 {
 732         unsigned char *p = addr;
 733
 734         while (size) {
 735                 if (*p == (unsigned char)c)
 736                         return (void *)p;
 737                 p++;
 738                 size--;
 739         }
 740         return (void *)p;
 741 }
 742 EXPORT_SYMBOL(memscan);
 743 #endif
 744
 745 #ifndef __HAVE_ARCH_STRSTR
 746 /**
 747  * strstr - Find the first substring in a %NUL terminated string
 748  * @s1: The string to be searched
 749  * @s2: The string to search for
 750  */
 751 char *strstr(const char *s1, const char *s2)
 752 {
 753         size_t l1, l2;
 754
 755         l2 = strlen(s2);
 756         if (!l2)
 757                 return (char *)s1;
 758         l1 = strlen(s1);
 759         while (l1 >= l2) {
 760                 l1--;
 761                 if (!memcmp(s1, s2, l2))
 762                         return (char *)s1;
 763                 s1++;
 764         }
 765         return NULL;
 766 }
 767 EXPORT_SYMBOL(strstr);
 768 #endif
 769
 770 #ifndef __HAVE_ARCH_STRNSTR
 771 /**
 772  * strnstr - Find the first substring in a length-limited string
 773  * @s1: The string to be searched
 774  * @s2: The string to search for
 775  * @len: the maximum number of characters to search
 776  */
 777 char *strnstr(const char *s1, const char *s2, size_t len)
 778 {
 779         size_t l2;
 780
 781         l2 = strlen(s2);
 782         if (!l2)
 783                 return (char *)s1;
 784         while (len >= l2) {
 785                 len--;
 786                 if (!memcmp(s1, s2, l2))
 787                         return (char *)s1;
 788                 s1++;
 789         }
 790         return NULL;
 791 }
 792 EXPORT_SYMBOL(strnstr);
 793 #endif
 794
 795 #ifndef __HAVE_ARCH_MEMCHR
 796 /**
 797  * memchr - Find a character in an area of memory.
 798  * @s: The memory area
 799  * @c: The byte to search for
 800  * @n: The size of the area.
 801  *
 802  * returns the address of the first occurrence of @c, or %NULL
 803  * if @c is not found
 804  */
 805 void *memchr(const void *s, int c, size_t n)
 806 {
 807         const unsigned char *p = s;
 808         while (n-- != 0) {
 809                 if ((unsigned char)c == *p++) {
 810                         return (void *)(p - 1);
 811                 }
 812         }
 813         return NULL;
 814 }
 815 EXPORT_SYMBOL(memchr);
 816 #endif
 817
 818 static void *check_bytes8(const u8 *start, u8 value, unsigned int bytes)
 819 {
 820         while (bytes) {
 821                 if (*start != value)
 822                         return (void *)start;
 823                 start++;
 824                 bytes--;
 825         }
 826         return NULL;
 827 }
 828
 829 /**
 830  * memchr_inv - Find an unmatching character in an area of memory.
 831  * @start: The memory area
 832  * @c: Find a character other than c
 833  * @bytes: The size of the area.
 834  *
 835  * returns the address of the first character other than @c, or %NULL
 836  * if the whole buffer contains just @c.
 837  */
 838 void *memchr_inv(const void *start, int c, size_t bytes)
 839 {
 840         u8 value = c;
 841         u64 value64;
 842         unsigned int words, prefix;
 843
 844         if (bytes <= 16)
 845                 return check_bytes8(start, value, bytes);
 846
 847         value64 = value;
 848 #if defined(CONFIG_ARCH_HAS_FAST_MULTIPLIER) && BITS_PER_LONG == 64
 849         value64 *= 0x0101010101010101ULL;
 850 #elif defined(CONFIG_ARCH_HAS_FAST_MULTIPLIER)
 851         value64 *= 0x01010101;
 852         value64 |= value64 << 32;
 853 #else
 854         value64 |= value64 << 8;
 855         value64 |= value64 << 16;
 856         value64 |= value64 << 32;
 857 #endif
 858
 859         prefix = (unsigned long)start % 8;
 860         if (prefix) {
 861                 u8 *r;
 862
 863                 prefix = 8 - prefix;
 864                 r = check_bytes8(start, value, prefix);
 865                 if (r)
 866                         return r;
 867                 start += prefix;
 868                 bytes -= prefix;
 869         }
 870
 871         words = bytes / 8;
 872
 873         while (words) {
 874                 if (*(u64 *)start != value64)
 875                         return check_bytes8(start, value, 8);
 876                 start += 8;
 877                 words--;
 878         }
 879
 880         return check_bytes8(start, value, bytes % 8);
 881 }
 882 EXPORT_SYMBOL(memchr_inv);