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 <asm/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 */ 40int 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} 62EXPORT_SYMBOL(strncasecmp); 63#endif 64 65#ifndef __HAVE_ARCH_STRCASECMP 66int 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} 76EXPORT_SYMBOL(strcasecmp); 77#endif 78 79#ifndef __HAVE_ARCH_STRCPY 80char *strcpy(char *dest, const char *src) 81{ 82 char *tmp = dest; 83 84 while ((*dest++ = *src++) != '\0') 85 /* nothing */; 86 return tmp; 87} 88EXPORT_SYMBOL(strcpy); 89#endif 90 91#ifndef __HAVE_ARCH_STRNCPY 92char *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} 104EXPORT_SYMBOL(strncpy); 105#endif 106 107ssize_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} 173EXPORT_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 */ 190char *stpcpy(char *__restrict__ dest, const char *__restrict__ src); 191char *stpcpy(char *__restrict__ dest, const char *__restrict__ src) 192{ 193 while ((*dest++ = *src++) != '\0') 194 /* nothing */; 195 return --dest; 196} 197EXPORT_SYMBOL(stpcpy); 198 199#ifndef __HAVE_ARCH_STRCAT 200char *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} 210EXPORT_SYMBOL(strcat); 211#endif 212 213#ifndef __HAVE_ARCH_STRNCAT 214char *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} 230EXPORT_SYMBOL(strncat); 231#endif 232 233#ifndef __HAVE_ARCH_STRLCAT 234size_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} 251EXPORT_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 */ 260int 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} 274EXPORT_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 */ 284int 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} 299EXPORT_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 */ 311char *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} 318EXPORT_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 */ 330char *strchrnul(const char *s, int c) 331{ 332 while (*s && *s != (char)c) 333 s++; 334 return (char *)s; 335} 336EXPORT_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 */ 349char *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 */ 362char *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} 371EXPORT_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 */ 384char *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} 394EXPORT_SYMBOL(strnchr); 395#endif 396 397#ifndef __HAVE_ARCH_STRLEN 398size_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} 406EXPORT_SYMBOL(strlen); 407#endif 408 409#ifndef __HAVE_ARCH_STRNLEN 410size_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} 418EXPORT_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 */ 427size_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} 437EXPORT_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 */ 446size_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} 456EXPORT_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 */ 465char *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} 475EXPORT_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 */ 490char *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} 504EXPORT_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 */ 516void *memset(void *s, int c, size_t count) 517{ 518 char *xs = s; 519 520 while (count--) 521 *xs++ = c; 522 return s; 523} 524EXPORT_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 */ 538void *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} 546EXPORT_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 */ 560void *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} 568EXPORT_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 */ 582void *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} 590EXPORT_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 */ 603void *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} 612EXPORT_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 */ 624void *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} 644EXPORT_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} 680EXPORT_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 */ 695int bcmp(const void *a, const void *b, size_t len) 696{ 697 return memcmp(a, b, len); 698} 699EXPORT_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 */ 712void *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} 724EXPORT_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 */ 733char *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} 749EXPORT_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 */ 759char *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} 774EXPORT_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 */ 787void *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} 797EXPORT_SYMBOL(memchr); 798#endif 799 800static 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 */ 820void *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} 864EXPORT_SYMBOL(memchr_inv); 865