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