lib/string.c

   1 /*
   2  *  linux/lib/string.c
   3  *
   4  *  Copyright (C) 1991, 1992  Linus Torvalds
   5  */
   6
   7 /*
   8  * stupid library routines.. The optimized versions should generally be found
   9  * as inline code in <asm-xx/string.h>
  10  *
  11  * These are buggy as well..
  12  *
  13  * * Fri Jun 25 1999, Ingo Oeser <ioe@informatik.tu-chemnitz.de>
  14  * -  Added strsep() which will replace strtok() soon (because strsep() is
  15  *    reentrant and should be faster). Use only strsep() in new code, please.
  16  */
  17
  18 #include <config.h>
  19 #include <linux/compiler.h>
  20 #include <linux/types.h>
  21 #include <linux/string.h>
  22 #include <linux/ctype.h>
  23 #include <malloc.h>
  24
  25
  26 /**
  27  * strncasecmp - Case insensitive, length-limited string comparison
  28  * @s1: One string
  29  * @s2: The other string
  30  * @len: the maximum number of characters to compare
  31  */
  32 int strncasecmp(const char *s1, const char *s2, size_t len)
  33 {
  34         /* Yes, Virginia, it had better be unsigned */
  35         unsigned char c1, c2;
  36
  37         c1 = 0; c2 = 0;
  38         if (len) {
  39                 do {
  40                         c1 = *s1; c2 = *s2;
  41                         s1++; s2++;
  42                         if (!c1)
  43                                 break;
  44                         if (!c2)
  45                                 break;
  46                         if (c1 == c2)
  47                                 continue;
  48                         c1 = tolower(c1);
  49                         c2 = tolower(c2);
  50                         if (c1 != c2)
  51                                 break;
  52                 } while (--len);
  53         }
  54         return (int)c1 - (int)c2;
  55 }
  56
  57 /**
  58  * strcasecmp - Case insensitive string comparison
  59  * @s1: One string
  60  * @s2: The other string
  61  */
  62 int strcasecmp(const char *s1, const char *s2)
  63 {
  64         return strncasecmp(s1, s2, -1U);
  65 }
  66
  67 char * ___strtok;
  68
  69 #ifndef __HAVE_ARCH_STRCPY
  70 /**
  71  * strcpy - Copy a %NUL terminated string
  72  * @dest: Where to copy the string to
  73  * @src: Where to copy the string from
  74  */
  75 char * strcpy(char * dest,const char *src)
  76 {
  77         char *tmp = dest;
  78
  79         while ((*dest++ = *src++) != '\0')
  80                 /* nothing */;
  81         return tmp;
  82 }
  83 #endif
  84
  85 #ifndef __HAVE_ARCH_STRNCPY
  86 /**
  87  * strncpy - Copy a length-limited, %NUL-terminated string
  88  * @dest: Where to copy the string to
  89  * @src: Where to copy the string from
  90  * @count: The maximum number of bytes to copy
  91  *
  92  * Note that unlike userspace strncpy, this does not %NUL-pad the buffer.
  93  * However, the result is not %NUL-terminated if the source exceeds
  94  * @count bytes.
  95  */
  96 char * strncpy(char * dest,const char *src,size_t count)
  97 {
  98         char *tmp = dest;
  99
 100         while (count-- && (*dest++ = *src++) != '\0')
 101                 /* nothing */;
 102
 103         return tmp;
 104 }
 105 #endif
 106
 107 #ifndef __HAVE_ARCH_STRLCPY
 108 /**
 109  * strlcpy - Copy a C-string into a sized buffer
 110  * @dest: Where to copy the string to
 111  * @src: Where to copy the string from
 112  * @size: size of destination buffer
 113  *
 114  * Compatible with *BSD: the result is always a valid
 115  * NUL-terminated string that fits in the buffer (unless,
 116  * of course, the buffer size is zero). It does not pad
 117  * out the result like strncpy() does.
 118  *
 119  * Return: strlen(src)
 120  */
 121 size_t strlcpy(char *dest, const char *src, size_t size)
 122 {
 123         size_t ret = strlen(src);
 124
 125         if (size) {
 126                 size_t len = (ret >= size) ? size - 1 : ret;
 127                 memcpy(dest, src, len);
 128                 dest[len] = '\0';
 129         }
 130         return ret;
 131 }
 132 #endif
 133
 134 #ifndef __HAVE_ARCH_STRCAT
 135 /**
 136  * strcat - Append one %NUL-terminated string to another
 137  * @dest: The string to be appended to
 138  * @src: The string to append to it
 139  */
 140 char * strcat(char * dest, const char * src)
 141 {
 142         char *tmp = dest;
 143
 144         while (*dest)
 145                 dest++;
 146         while ((*dest++ = *src++) != '\0')
 147                 ;
 148
 149         return tmp;
 150 }
 151 #endif
 152
 153 #ifndef __HAVE_ARCH_STRNCAT
 154 /**
 155  * strncat - Append a length-limited, %NUL-terminated string to another
 156  * @dest: The string to be appended to
 157  * @src: The string to append to it
 158  * @count: The maximum numbers of bytes to copy
 159  *
 160  * Note that in contrast to strncpy, strncat ensures the result is
 161  * terminated.
 162  */
 163 char * strncat(char *dest, const char *src, size_t count)
 164 {
 165         char *tmp = dest;
 166
 167         if (count) {
 168                 while (*dest)
 169                         dest++;
 170                 while ((*dest++ = *src++)) {
 171                         if (--count == 0) {
 172                                 *dest = '\0';
 173                                 break;
 174                         }
 175                 }
 176         }
 177
 178         return tmp;
 179 }
 180 #endif
 181
 182 #ifndef __HAVE_ARCH_STRLCAT
 183 /**
 184  * strlcat - Append a length-limited, %NUL-terminated string to another
 185  * @dest: The string to be appended to
 186  * @src: The string to append to it
 187  * @size: The size of @dest
 188  *
 189  * Compatible with *BSD: the result is always a valid NUL-terminated string that
 190  * fits in the buffer (unless, of course, the buffer size is zero). It does not
 191  * write past @size like strncat() does.
 192  *
 193  * Return: min(strlen(dest), size) + strlen(src)
 194  */
 195 size_t strlcat(char *dest, const char *src, size_t size)
 196 {
 197         size_t len = strnlen(dest, size);
 198
 199         return len + strlcpy(dest + len, src, size - len);
 200 }
 201 #endif
 202
 203 #ifndef __HAVE_ARCH_STRCMP
 204 /**
 205  * strcmp - Compare two strings
 206  * @cs: One string
 207  * @ct: Another string
 208  */
 209 int strcmp(const char *cs, const char *ct)
 210 {
 211         int ret;
 212
 213         while (1) {
 214                 unsigned char a = *cs++;
 215                 unsigned char b = *ct++;
 216
 217                 ret = a - b;
 218                 if (ret || !b)
 219                         break;
 220         }
 221
 222         return ret;
 223 }
 224 #endif
 225
 226 #ifndef __HAVE_ARCH_STRNCMP
 227 /**
 228  * strncmp - Compare two length-limited strings
 229  * @cs: One string
 230  * @ct: Another string
 231  * @count: The maximum number of bytes to compare
 232  */
 233 int strncmp(const char *cs, const char *ct, size_t count)
 234 {
 235         int ret = 0;
 236
 237         while (count--) {
 238                 unsigned char a = *cs++;
 239                 unsigned char b = *ct++;
 240
 241                 ret = a - b;
 242                 if (ret || !b)
 243                         break;
 244         }
 245
 246         return ret;
 247 }
 248 #endif
 249
 250 #ifndef __HAVE_ARCH_STRCHR
 251 /**
 252  * strchr - Find the first occurrence of a character in a string
 253  * @s: The string to be searched
 254  * @c: The character to search for
 255  */
 256 char * strchr(const char * s, int c)
 257 {
 258         for(; *s != (char) c; ++s)
 259                 if (*s == '\0')
 260                         return NULL;
 261         return (char *) s;
 262 }
 263 #endif
 264
 265 const char *strchrnul(const char *s, int c)
 266 {
 267         for (; *s != (char)c; ++s)
 268                 if (*s == '\0')
 269                         break;
 270         return s;
 271 }
 272
 273 #ifndef __HAVE_ARCH_STRRCHR
 274 /**
 275  * strrchr - Find the last occurrence of a character in a string
 276  * @s: The string to be searched
 277  * @c: The character to search for
 278  */
 279 char * strrchr(const char * s, int c)
 280 {
 281        const char *p = s + strlen(s);
 282        do {
 283            if (*p == (char)c)
 284                return (char *)p;
 285        } while (--p >= s);
 286        return NULL;
 287 }
 288 #endif
 289
 290 #ifndef __HAVE_ARCH_STRLEN
 291 /**
 292  * strlen - Find the length of a string
 293  * @s: The string to be sized
 294  */
 295 size_t strlen(const char * s)
 296 {
 297         const char *sc;
 298
 299         for (sc = s; *sc != '\0'; ++sc)
 300                 /* nothing */;
 301         return sc - s;
 302 }
 303 #endif
 304
 305 #ifndef __HAVE_ARCH_STRNLEN
 306 /**
 307  * strnlen - Find the length of a length-limited string
 308  * @s: The string to be sized
 309  * @count: The maximum number of bytes to search
 310  */
 311 size_t strnlen(const char * s, size_t count)
 312 {
 313         const char *sc;
 314
 315         for (sc = s; count-- && *sc != '\0'; ++sc)
 316                 /* nothing */;
 317         return sc - s;
 318 }
 319 #endif
 320
 321 #ifndef __HAVE_ARCH_STRCSPN
 322 /**
 323  * strcspn - Calculate the length of the initial substring of @s which does
 324  * not contain letters in @reject
 325  * @s: The string to be searched
 326  * @reject: The string to avoid
 327  */
 328 size_t strcspn(const char *s, const char *reject)
 329 {
 330         const char *p;
 331         const char *r;
 332         size_t count = 0;
 333
 334         for (p = s; *p != '\0'; ++p) {
 335                 for (r = reject; *r != '\0'; ++r) {
 336                         if (*p == *r)
 337                                 return count;
 338                 }
 339                 ++count;
 340         }
 341         return count;
 342 }
 343 #endif
 344
 345 #ifndef __HAVE_ARCH_STRDUP
 346 char * strdup(const char *s)
 347 {
 348         char *new;
 349
 350         if ((s == NULL) ||
 351             ((new = malloc (strlen(s) + 1)) == NULL) ) {
 352                 return NULL;
 353         }
 354
 355         strcpy (new, s);
 356         return new;
 357 }
 358
 359 char * strndup(const char *s, size_t n)
 360 {
 361         size_t len;
 362         char *new;
 363
 364         if (s == NULL)
 365                 return NULL;
 366
 367         len = strlen(s);
 368
 369         if (n < len)
 370                 len = n;
 371
 372         new = malloc(len + 1);
 373         if (new == NULL)
 374                 return NULL;
 375
 376         strncpy(new, s, len);
 377         new[len] = '\0';
 378
 379         return new;
 380 }
 381 #endif
 382
 383 #ifndef __HAVE_ARCH_STRSPN
 384 /**
 385  * strspn - Calculate the length of the initial substring of @s which only
 386  *      contain letters in @accept
 387  * @s: The string to be searched
 388  * @accept: The string to search for
 389  */
 390 size_t strspn(const char *s, const char *accept)
 391 {
 392         const char *p;
 393         const char *a;
 394         size_t count = 0;
 395
 396         for (p = s; *p != '\0'; ++p) {
 397                 for (a = accept; *a != '\0'; ++a) {
 398                         if (*p == *a)
 399                                 break;
 400                 }
 401                 if (*a == '\0')
 402                         return count;
 403                 ++count;
 404         }
 405
 406         return count;
 407 }
 408 #endif
 409
 410 #ifndef __HAVE_ARCH_STRPBRK
 411 /**
 412  * strpbrk - Find the first occurrence of a set of characters
 413  * @cs: The string to be searched
 414  * @ct: The characters to search for
 415  */
 416 char * strpbrk(const char * cs,const char * ct)
 417 {
 418         const char *sc1,*sc2;
 419
 420         for( sc1 = cs; *sc1 != '\0'; ++sc1) {
 421                 for( sc2 = ct; *sc2 != '\0'; ++sc2) {
 422                         if (*sc1 == *sc2)
 423                                 return (char *) sc1;
 424                 }
 425         }
 426         return NULL;
 427 }
 428 #endif
 429
 430 #ifndef __HAVE_ARCH_STRTOK
 431 /**
 432  * strtok - Split a string into tokens
 433  * @s: The string to be searched
 434  * @ct: The characters to search for
 435  *
 436  * WARNING: strtok is deprecated, use strsep instead.
 437  */
 438 char * strtok(char * s,const char * ct)
 439 {
 440         char *sbegin, *send;
 441
 442         sbegin  = s ? s : ___strtok;
 443         if (!sbegin) {
 444                 return NULL;
 445         }
 446         sbegin += strspn(sbegin,ct);
 447         if (*sbegin == '\0') {
 448                 ___strtok = NULL;
 449                 return( NULL );
 450         }
 451         send = strpbrk( sbegin, ct);
 452         if (send && *send != '\0')
 453                 *send++ = '\0';
 454         ___strtok = send;
 455         return (sbegin);
 456 }
 457 #endif
 458
 459 #ifndef __HAVE_ARCH_STRSEP
 460 /**
 461  * strsep - Split a string into tokens
 462  * @s: The string to be searched
 463  * @ct: The characters to search for
 464  *
 465  * strsep() updates @s to point after the token, ready for the next call.
 466  *
 467  * It returns empty tokens, too, behaving exactly like the libc function
 468  * of that name. In fact, it was stolen from glibc2 and de-fancy-fied.
 469  * Same semantics, slimmer shape. ;)
 470  */
 471 char * strsep(char **s, const char *ct)
 472 {
 473         char *sbegin = *s, *end;
 474
 475         if (sbegin == NULL)
 476                 return NULL;
 477
 478         end = strpbrk(sbegin, ct);
 479         if (end)
 480                 *end++ = '\0';
 481         *s = end;
 482
 483         return sbegin;
 484 }
 485 #endif
 486
 487 #ifndef __HAVE_ARCH_STRSWAB
 488 /**
 489  * strswab - swap adjacent even and odd bytes in %NUL-terminated string
 490  * s: address of the string
 491  *
 492  * returns the address of the swapped string or NULL on error. If
 493  * string length is odd, last byte is untouched.
 494  */
 495 char *strswab(const char *s)
 496 {
 497         char *p, *q;
 498
 499         if ((NULL == s) || ('\0' == *s)) {
 500                 return (NULL);
 501         }
 502
 503         for (p=(char *)s, q=p+1; (*p != '\0') && (*q != '\0'); p+=2, q+=2) {
 504                 char  tmp;
 505
 506                 tmp = *p;
 507                 *p  = *q;
 508                 *q  = tmp;
 509         }
 510
 511         return (char *) s;
 512 }
 513 #endif
 514
 515 #ifndef __HAVE_ARCH_MEMSET
 516 /**
 517  * memset - Fill a region of memory with the given value
 518  * @s: Pointer to the start of the area.
 519  * @c: The byte to fill the area with
 520  * @count: The size of the area.
 521  *
 522  * Do not use memset() to access IO space, use memset_io() instead.
 523  */
 524 __used void * memset(void * s,int c,size_t count)
 525 {
 526         unsigned long *sl = (unsigned long *) s;
 527         char *s8;
 528
 529 #if !CONFIG_IS_ENABLED(TINY_MEMSET)
 530         unsigned long cl = 0;
 531         int i;
 532
 533         /* do it one word at a time (32 bits or 64 bits) while possible */
 534         if ( ((ulong)s & (sizeof(*sl) - 1)) == 0) {
 535                 for (i = 0; i < sizeof(*sl); i++) {
 536                         cl <<= 8;
 537                         cl |= c & 0xff;
 538                 }
 539                 while (count >= sizeof(*sl)) {
 540                         *sl++ = cl;
 541                         count -= sizeof(*sl);
 542                 }
 543         }
 544 #endif  /* fill 8 bits at a time */
 545         s8 = (char *)sl;
 546         while (count--)
 547                 *s8++ = c;
 548
 549         return s;
 550 }
 551 #endif
 552
 553 #ifndef __HAVE_ARCH_MEMCPY
 554 /**
 555  * memcpy - Copy one area of memory to another
 556  * @dest: Where to copy to
 557  * @src: Where to copy from
 558  * @count: The size of the area.
 559  *
 560  * You should not use this function to access IO space, use memcpy_toio()
 561  * or memcpy_fromio() instead.
 562  */
 563 __used void * memcpy(void *dest, const void *src, size_t count)
 564 {
 565         unsigned long *dl = (unsigned long *)dest, *sl = (unsigned long *)src;
 566         char *d8, *s8;
 567
 568         if (src == dest)
 569                 return dest;
 570
 571         /* while all data is aligned (common case), copy a word at a time */
 572         if ( (((ulong)dest | (ulong)src) & (sizeof(*dl) - 1)) == 0) {
 573                 while (count >= sizeof(*dl)) {
 574                         *dl++ = *sl++;
 575                         count -= sizeof(*dl);
 576                 }
 577         }
 578         /* copy the reset one byte at a time */
 579         d8 = (char *)dl;
 580         s8 = (char *)sl;
 581         while (count--)
 582                 *d8++ = *s8++;
 583
 584         return dest;
 585 }
 586 #endif
 587
 588 #ifndef __HAVE_ARCH_MEMMOVE
 589 /**
 590  * memmove - Copy one area of memory to another
 591  * @dest: Where to copy to
 592  * @src: Where to copy from
 593  * @count: The size of the area.
 594  *
 595  * Unlike memcpy(), memmove() copes with overlapping areas.
 596  */
 597 __used void * memmove(void * dest,const void *src,size_t count)
 598 {
 599         char *tmp, *s;
 600
 601         if (dest <= src || (src + count) <= dest) {
 602         /*
 603          * Use the fast memcpy implementation (ARCH optimized or lib/string.c) when it is possible:
 604          * - when dest is before src (assuming that memcpy is doing forward-copying)
 605          * - when destination don't overlap the source buffer (src + count <= dest)
 606          *
 607          * WARNING: the first optimisation cause an issue, when __HAVE_ARCH_MEMCPY is defined,
 608          *          __HAVE_ARCH_MEMMOVE is not defined and if the memcpy ARCH-specific
 609          *          implementation is not doing a forward-copying.
 610          *
 611          * No issue today because memcpy is doing a forward-copying in lib/string.c and for ARM32
 612          * architecture; no other arches use __HAVE_ARCH_MEMCPY without __HAVE_ARCH_MEMMOVE.
 613          */
 614                 memcpy(dest, src, count);
 615         } else {
 616                 tmp = (char *) dest + count;
 617                 s = (char *) src + count;
 618                 while (count--)
 619                         *--tmp = *--s;
 620                 }
 621
 622         return dest;
 623 }
 624 #endif
 625
 626 #ifndef __HAVE_ARCH_MEMCMP
 627 /**
 628  * memcmp - Compare two areas of memory
 629  * @cs: One area of memory
 630  * @ct: Another area of memory
 631  * @count: The size of the area.
 632  */
 633 __used int memcmp(const void * cs,const void * ct,size_t count)
 634 {
 635         const unsigned char *su1, *su2;
 636         int res = 0;
 637
 638         for( su1 = cs, su2 = ct; 0 < count; ++su1, ++su2, count--)
 639                 if ((res = *su1 - *su2) != 0)
 640                         break;
 641         return res;
 642 }
 643 #endif
 644
 645 #ifndef __HAVE_ARCH_MEMSCAN
 646 /**
 647  * memscan - Find a character in an area of memory.
 648  * @addr: The memory area
 649  * @c: The byte to search for
 650  * @size: The size of the area.
 651  *
 652  * returns the address of the first occurrence of @c, or 1 byte past
 653  * the area if @c is not found
 654  */
 655 void * memscan(void * addr, int c, size_t size)
 656 {
 657         unsigned char * p = (unsigned char *) addr;
 658
 659         while (size) {
 660                 if (*p == c)
 661                         return (void *) p;
 662                 p++;
 663                 size--;
 664         }
 665         return (void *) p;
 666 }
 667 #endif
 668
 669 char *memdup(const void *src, size_t len)
 670 {
 671         char *p;
 672
 673         p = malloc(len);
 674         if (!p)
 675                 return NULL;
 676
 677         memcpy(p, src, len);
 678
 679         return p;
 680 }
 681
 682 #ifndef __HAVE_ARCH_STRSTR
 683 /**
 684  * strstr - Find the first substring in a %NUL terminated string
 685  * @s1: The string to be searched
 686  * @s2: The string to search for
 687  */
 688 char * strstr(const char * s1,const char * s2)
 689 {
 690         int l1, l2;
 691
 692         l2 = strlen(s2);
 693         if (!l2)
 694                 return (char *) s1;
 695         l1 = strlen(s1);
 696         while (l1 >= l2) {
 697                 l1--;
 698                 if (!memcmp(s1,s2,l2))
 699                         return (char *) s1;
 700                 s1++;
 701         }
 702         return NULL;
 703 }
 704 #endif
 705
 706 #ifndef __HAVE_ARCH_MEMCHR
 707 /**
 708  * memchr - Find a character in an area of memory.
 709  * @s: The memory area
 710  * @c: The byte to search for
 711  * @n: The size of the area.
 712  *
 713  * returns the address of the first occurrence of @c, or %NULL
 714  * if @c is not found
 715  */
 716 void *memchr(const void *s, int c, size_t n)
 717 {
 718         const unsigned char *p = s;
 719         while (n-- != 0) {
 720                 if ((unsigned char)c == *p++) {
 721                         return (void *)(p-1);
 722                 }
 723         }
 724         return NULL;
 725 }
 726
 727 #endif
 728 #ifndef __HAVE_ARCH_MEMCHR_INV
 729 static void *check_bytes8(const u8 *start, u8 value, unsigned int bytes)
 730 {
 731         while (bytes) {
 732                 if (*start != value)
 733                         return (void *)start;
 734                 start++;
 735                 bytes--;
 736         }
 737         return NULL;
 738 }
 739 /**
 740  * memchr_inv - Find an unmatching character in an area of memory.
 741  * @start: The memory area
 742  * @c: Find a character other than c
 743  * @bytes: The size of the area.
 744  *
 745  * returns the address of the first character other than @c, or %NULL
 746  * if the whole buffer contains just @c.
 747  */
 748 void *memchr_inv(const void *start, int c, size_t bytes)
 749 {
 750         u8 value = c;
 751         u64 value64;
 752         unsigned int words, prefix;
 753
 754         if (bytes <= 16)
 755                 return check_bytes8(start, value, bytes);
 756
 757         value64 = value;
 758         value64 |= value64 << 8;
 759         value64 |= value64 << 16;
 760         value64 |= value64 << 32;
 761
 762         prefix = (unsigned long)start % 8;
 763         if (prefix) {
 764                 u8 *r;
 765
 766                 prefix = 8 - prefix;
 767                 r = check_bytes8(start, value, prefix);
 768                 if (r)
 769                         return r;
 770                 start += prefix;
 771                 bytes -= prefix;
 772         }
 773
 774         words = bytes / 8;
 775
 776         while (words) {
 777                 if (*(u64 *)start != value64)
 778                         return check_bytes8(start, value, 8);
 779                 start += 8;
 780                 words--;
 781         }
 782
 783         return check_bytes8(start, value, bytes % 8);
 784 }
 785 #endif