The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/libkern/strlen.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*-
    2  * Copyright (c) 2009, 2010 Xin LI <delphij@FreeBSD.org>
    3  * All rights reserved.
    4  *
    5  * Redistribution and use in source and binary forms, with or without
    6  * modification, are permitted provided that the following conditions
    7  * are met:
    8  * 1. Redistributions of source code must retain the above copyright
    9  *    notice, this list of conditions and the following disclaimer.
   10  * 2. Redistributions in binary form must reproduce the above copyright
   11  *    notice, this list of conditions and the following disclaimer in the
   12  *    documentation and/or other materials provided with the distribution.
   13  *
   14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   24  * SUCH DAMAGE.
   25  */
   26 
   27 #include <sys/cdefs.h>
   28 __FBSDID("$FreeBSD: releng/9.2/sys/libkern/strlen.c 243809 2012-12-03 18:01:53Z delphij $");
   29 
   30 #include <sys/libkern.h>
   31 #include <sys/limits.h>
   32 
   33 /*
   34  * Portable strlen() for 32-bit and 64-bit systems.
   35  *
   36  * Rationale: it is generally much more efficient to do word length
   37  * operations and avoid branches on modern computer systems, as
   38  * compared to byte-length operations with a lot of branches.
   39  *
   40  * The expression:
   41  *
   42  *      ((x - 0x01....01) & ~x & 0x80....80)
   43  *
   44  * would evaluate to a non-zero value iff any of the bytes in the
   45  * original word is zero.
   46  *
   47  * On multi-issue processors, we can divide the above expression into:
   48  *      a)  (x - 0x01....01)
   49  *      b) (~x & 0x80....80)
   50  *      c) a & b
   51  *
   52  * Where, a) and b) can be partially computed in parallel.
   53  *
   54  * The algorithm above is found on "Hacker's Delight" by
   55  * Henry S. Warren, Jr.
   56  */
   57 
   58 /* Magic numbers for the algorithm */
   59 #if LONG_BIT == 32
   60 static const unsigned long mask01 = 0x01010101;
   61 static const unsigned long mask80 = 0x80808080;
   62 #elif LONG_BIT == 64
   63 static const unsigned long mask01 = 0x0101010101010101;
   64 static const unsigned long mask80 = 0x8080808080808080;
   65 #else
   66 #error Unsupported word size
   67 #endif
   68 
   69 #define LONGPTR_MASK (sizeof(long) - 1)
   70 
   71 /*
   72  * Helper macro to return string length if we caught the zero
   73  * byte.
   74  */
   75 #define testbyte(x)                             \
   76         do {                                    \
   77                 if (p[x] == '\0')               \
   78                     return (p - str + x);       \
   79         } while (0)
   80 
   81 size_t
   82 strlen(const char *str)
   83 {
   84         const char *p;
   85         const unsigned long *lp;
   86         long va, vb;
   87 
   88         /*
   89          * Before trying the hard (unaligned byte-by-byte access) way
   90          * to figure out whether there is a nul character, try to see
   91          * if there is a nul character is within this accessible word
   92          * first.
   93          *
   94          * p and (p & ~LONGPTR_MASK) must be equally accessible since
   95          * they always fall in the same memory page, as long as page
   96          * boundaries is integral multiple of word size.
   97          */
   98         lp = (const unsigned long *)((uintptr_t)str & ~LONGPTR_MASK);
   99         va = (*lp - mask01);
  100         vb = ((~*lp) & mask80);
  101         lp++;
  102         if (va & vb)
  103                 /* Check if we have \0 in the first part */
  104                 for (p = str; p < (const char *)lp; p++)
  105                         if (*p == '\0')
  106                                 return (p - str);
  107 
  108         /* Scan the rest of the string using word sized operation */
  109         for (; ; lp++) {
  110                 va = (*lp - mask01);
  111                 vb = ((~*lp) & mask80);
  112                 if (va & vb) {
  113                         p = (const char *)(lp);
  114                         testbyte(0);
  115                         testbyte(1);
  116                         testbyte(2);
  117                         testbyte(3);
  118 #if (LONG_BIT >= 64)
  119                         testbyte(4);
  120                         testbyte(5);
  121                         testbyte(6);
  122                         testbyte(7);
  123 #endif
  124                 }
  125         }
  126 
  127         /* NOTREACHED */
  128         return (0);
  129 }

Cache object: 4c6bfca693871b4ba574699ed243ce00


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.