string/strlen.c

   1 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3    Written by Torbjorn Granlund (tege@sics.se),
   4    with help from Dan Sahlin (dan@sics.se);
   5    commentary by Jim Blandy (jimb@ai.mit.edu).
   6
   7    The GNU C Library is free software; you can redistribute it and/or
   8    modify it under the terms of the GNU Lesser General Public
   9    License as published by the Free Software Foundation; either
  10    version 2.1 of the License, or (at your option) any later version.
  11
  12    The GNU C Library is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    Lesser General Public License for more details.
  16
  17    You should have received a copy of the GNU Lesser General Public
  18    License along with the GNU C Library; if not, see
  19    <http://www.gnu.org/licenses/>.  */
  20
  21 #include <string.h>
  22 #include <stdlib.h>
  23
  24 #undef strlen
  25
  26 /* Return the length of the null-terminated string STR.  Scan for
  27    the null terminator quickly by testing four bytes at a time.  */
  28 size_t
  29 strlen (const char *str)
  30 {
  31   const char *char_ptr;
  32   const unsigned long int *longword_ptr;
  33   unsigned long int longword, himagic, lomagic;
  34
  35   /* Handle the first few characters by reading one character at a time.
  36      Do this until CHAR_PTR is aligned on a longword boundary.  */
  37   for (char_ptr = str; ((unsigned long int) char_ptr
  38                         & (sizeof (longword) - 1)) != 0;
  39        ++char_ptr)
  40     if (*char_ptr == '\0')
  41       return char_ptr - str;
  42
  43   /* All these elucidatory comments refer to 4-byte longwords,
  44      but the theory applies equally well to 8-byte longwords.  */
  45
  46   longword_ptr = (unsigned long int *) char_ptr;
  47
  48   /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
  49      the "holes."  Note that there is a hole just to the left of
  50      each byte, with an extra at the end:
  51
  52      bits:  01111110 11111110 11111110 11111111
  53      bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
  54
  55      The 1-bits make sure that carries propagate to the next 0-bit.
  56      The 0-bits provide holes for carries to fall into.  */
  57   himagic = 0x80808080L;
  58   lomagic = 0x01010101L;
  59   if (sizeof (longword) > 4)
  60     {
  61       /* 64-bit version of the magic.  */
  62       /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
  63       himagic = ((himagic << 16) << 16) | himagic;
  64       lomagic = ((lomagic << 16) << 16) | lomagic;
  65     }
  66   if (sizeof (longword) > 8)
  67     abort ();
  68
  69   /* Instead of the traditional loop which tests each character,
  70      we will test a longword at a time.  The tricky part is testing
  71      if *any of the four* bytes in the longword in question are zero.  */
  72   for (;;)
  73     {
  74       longword = *longword_ptr++;
  75
  76       if (((longword - lomagic) & ~longword & himagic) != 0)
  77         {
  78           /* Which of the bytes was the zero?  If none of them were, it was
  79              a misfire; continue the search.  */
  80
  81           const char *cp = (const char *) (longword_ptr - 1);
  82
  83           if (cp[0] == 0)
  84             return cp - str;
  85           if (cp[1] == 0)
  86             return cp - str + 1;
  87           if (cp[2] == 0)
  88             return cp - str + 2;
  89           if (cp[3] == 0)
  90             return cp - str + 3;
  91           if (sizeof (longword) > 4)
  92             {
  93               if (cp[4] == 0)
  94                 return cp - str + 4;
  95               if (cp[5] == 0)
  96                 return cp - str + 5;
  97               if (cp[6] == 0)
  98                 return cp - str + 6;
  99               if (cp[7] == 0)
 100                 return cp - str + 7;
 101             }
 102         }
 103     }
 104 }
 105 libc_hidden_builtin_def (strlen)