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