hphp/util/bstring.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include "hphp/util/bstring.h"
  18 #include <folly/Portability.h>
  19
  20 namespace HPHP {
  21 ///////////////////////////////////////////////////////////////////////////////
  22
  23 /**
  24  * The implementations below produce reasonably good machine code that
  25  * is comparable to the machine code for strcasecmp from glibc 4.4.0.
  26  */
  27
  28 bool bstrcaseeq(const char* left, const char* right, size_t n) {
  29   // Early exit if we're given the same two strings.
  30   if (left == right) return true;
  31
  32   // Fast case sensitive comparison, unrolled to do 8 bytes at a time.
  33   size_t i = 0;
  34 #if !FOLLY_SANITIZE
  35   typedef uint64_t widecmp_t;
  36   if (n >= sizeof(widecmp_t)) {
  37     while (*(const widecmp_t*)(&left[i]) == *(const widecmp_t*)(&right[i])) {
  38       i += sizeof(widecmp_t);
  39       if (i >= (n - (sizeof(widecmp_t) - 1))) break;
  40     }
  41   }
  42 #endif
  43
  44   // Finish whatever is left over.
  45   for (; i < n; ++i) {
  46     if (!chrcaseeq(left[i], right[i])) return false;
  47   }
  48   return true;
  49 }
  50
  51 int bstrcasecmp(const char* left, size_t leftSize,
  52                 const char* right, size_t rightSize) {
  53   size_t minSize = leftSize < rightSize ? leftSize : rightSize;
  54   for (size_t i = 0; i < minSize; ++i) {
  55     ssize_t ret = chrcasecmp(left[i], right[i]);
  56     if (ret) return ret;
  57   }
  58   return (leftSize > rightSize) - (leftSize < rightSize);
  59 }
  60
  61 char* bstrcasechr(const char* haystack, char needle, size_t haystackSize) {
  62   const char* haystackEnd = haystack + haystackSize;
  63   for (; haystack != haystackEnd; ++haystack) {
  64     if (chrcaseeq(*haystack, needle)) {
  65       return (char*)haystack;
  66     }
  67   }
  68   return nullptr;
  69 }
  70
  71 // Simple implementation of bstrcaseeq, used for bstrcasestr since the
  72 // above implementation is specialized for exact-matching strings.
  73 static bool bstrcasestreq(const char* left, const char* right, size_t n) {
  74   for (size_t i = 0; i < n; ++i) {
  75     if (!chrcaseeq(left[i], right[i])) return false;
  76   }
  77   return true;
  78 }
  79
  80 char* bstrcasestr(const char* haystack, size_t haystackSize,
  81                   const char* needle, size_t needleSize) {
  82   if (needleSize > haystackSize) {
  83     return nullptr;
  84   }
  85   const char* haystackLast = haystack + (haystackSize - needleSize);
  86   for (;;) {
  87     if (bstrcasestreq(haystack, needle, needleSize)) {
  88       return (char*)haystack;
  89     }
  90     if (haystack == haystackLast) return nullptr;
  91     ++haystack;
  92   }
  93 }
  94
  95 char* bstrrcasechr(const char* haystack, char needle, size_t haystackSize) {
  96   if (haystackSize == 0) {
  97     return nullptr;
  98   }
  99   const char* haystackPtr = haystack + (haystackSize - 1);
 100   for (;;) {
 101     if (chrcaseeq(*haystackPtr, needle)) {
 102       return (char*)haystackPtr;
 103     }
 104     if (haystackPtr == haystack) return nullptr;
 105     --haystackPtr;
 106   }
 107 }
 108
 109 char* bstrrcasestr(const char* haystack, size_t haystackSize,
 110                    const char* needle, size_t needleSize) {
 111   if (needleSize > haystackSize) {
 112     return nullptr;
 113   }
 114   const char* haystackPtr = haystack + (haystackSize - needleSize);
 115   for (;;) {
 116     if (bstrcaseeq(haystackPtr, needle, needleSize)) {
 117       return (char*)haystackPtr;
 118     }
 119     if (haystackPtr == haystack) return nullptr;
 120     --haystackPtr;
 121   }
 122 }
 123
 124 char* bstrrstr(const char* haystack, size_t haystackSize,
 125                const char* needle, size_t needleSize) {
 126   if (needleSize > haystackSize) {
 127     return nullptr;
 128   }
 129   const char* haystackPtr = haystack + (haystackSize - needleSize);
 130   if (needleSize == 0) {
 131     return (char*)haystackPtr;
 132   }
 133   for (;;) {
 134     size_t j = 0;
 135     for (;;) {
 136       if (haystackPtr[j] != needle[j]) break;
 137       ++j;
 138       if (j == needleSize) return (char*)haystackPtr;
 139     }
 140     if (haystackPtr == haystack) return nullptr;
 141     --haystackPtr;
 142   }
 143 }
 144
 145 ///////////////////////////////////////////////////////////////////////////////
 146 }