. /src /grammar /ci_string.cpp
98.44% Lines (63/64) 100.00% Functions (4/4)
[ ] prev/next file n p prev/next uncovered line
TLA Baseline Branch
Line Hits Code Line Hits Code
1   // 1   //
2   // Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com) 2   // Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com)
3   // 3   //
4   // Distributed under the Boost Software License, Version 1.0. (See accompanying 4   // Distributed under the Boost Software License, Version 1.0. (See accompanying
5   // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5   // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6   // 6   //
7   // Official repository: https://github.com/boostorg/url 7   // Official repository: https://github.com/boostorg/url
8   // 8   //
9   9  
10   10  
11   #include <boost/url/detail/config.hpp> 11   #include <boost/url/detail/config.hpp>
12   #include <boost/url/grammar/ci_string.hpp> 12   #include <boost/url/grammar/ci_string.hpp>
13   13  
14   // FNV-1a (in ci_digest below) relies on modular multiplication 14   // FNV-1a (in ci_digest below) relies on modular multiplication
15   // of unsigned values, which Clang's -fsanitize=integer flags as 15   // of unsigned values, which Clang's -fsanitize=integer flags as
16   // overflow. Suppress the check for that function only. GCC has 16   // overflow. Suppress the check for that function only. GCC has
17   // no equivalent sanitizer (it does not flag unsigned overflow), 17   // no equivalent sanitizer (it does not flag unsigned overflow),
18   // so the annotation is Clang-only — applying it on GCC produces 18   // so the annotation is Clang-only — applying it on GCC produces
19   // "attribute directive ignored" under -Werror=attributes. 19   // "attribute directive ignored" under -Werror=attributes.
20   #if defined(__clang__) && defined(__has_attribute) 20   #if defined(__clang__) && defined(__has_attribute)
21   # if __has_attribute(no_sanitize) 21   # if __has_attribute(no_sanitize)
22   # define BOOST_URL_NO_SANITIZE_INT_OVERFLOW \ 22   # define BOOST_URL_NO_SANITIZE_INT_OVERFLOW \
23   __attribute__((no_sanitize("unsigned-integer-overflow"))) 23   __attribute__((no_sanitize("unsigned-integer-overflow")))
24   # endif 24   # endif
25   #endif 25   #endif
26   #ifndef BOOST_URL_NO_SANITIZE_INT_OVERFLOW 26   #ifndef BOOST_URL_NO_SANITIZE_INT_OVERFLOW
27   # define BOOST_URL_NO_SANITIZE_INT_OVERFLOW 27   # define BOOST_URL_NO_SANITIZE_INT_OVERFLOW
28   #endif 28   #endif
29   29  
30   namespace boost { 30   namespace boost {
31   namespace urls { 31   namespace urls {
32   namespace grammar { 32   namespace grammar {
33   33  
34   namespace detail { 34   namespace detail {
35   35  
36   //------------------------------------------------ 36   //------------------------------------------------
37   37  
38   // https://lemire.me/blog/2020/04/30/for-case-insensitive-string-comparisons-avoid-char-by-char-functions/ 38   // https://lemire.me/blog/2020/04/30/for-case-insensitive-string-comparisons-avoid-char-by-char-functions/
39   // https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2020/04/30/tolower.cpp 39   // https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2020/04/30/tolower.cpp
40   40  
41   bool 41   bool
HITCBC 42   8 ci_is_equal( 42   8 ci_is_equal(
43   core::string_view s0, 43   core::string_view s0,
44   core::string_view s1) noexcept 44   core::string_view s1) noexcept
45   { 45   {
HITCBC 46   8 auto n = s0.size(); 46   8 auto n = s0.size();
HITCBC 47   8 auto p1 = s0.data(); 47   8 auto p1 = s0.data();
HITCBC 48   8 auto p2 = s1.data(); 48   8 auto p2 = s1.data();
49   char a, b; 49   char a, b;
50   // fast loop 50   // fast loop
HITCBC 51   13 while(n != 0) 51   13 while(n != 0)
52   { 52   {
HITCBC 53   10 --n; 53   10 --n;
HITCBC 54   10 a = *p1++; 54   10 a = *p1++;
HITCBC 55   10 b = *p2++; 55   10 b = *p2++;
HITCBC 56   10 if(a != b) 56   10 if(a != b)
HITCBC 57   5 goto slow; 57   5 goto slow;
58   } 58   }
HITCBC 59   3 return true; 59   3 return true;
60   for(;;) 60   for(;;)
61   { 61   {
HITCBC 62   8 a = *p1++; 62   8 a = *p1++;
HITCBC 63   8 b = *p2++; 63   8 b = *p2++;
HITCBC 64   13 slow: 64   13 slow:
HITCBC 65   26 if( to_lower(a) != 65   26 if( to_lower(a) !=
HITCBC 66   13 to_lower(b)) 66   13 to_lower(b))
MISUBC 67   ✗ return false; 67   ✗ return false;
HITCBC 68   13 if(n == 0) 68   13 if(n == 0)
HITCBC 69   5 break; 69   5 break;
HITCBC 70   8 --n; 70   8 --n;
71   } 71   }
HITCBC 72   5 return true; 72   5 return true;
73   } 73   }
74   74  
75   //------------------------------------------------ 75   //------------------------------------------------
76   76  
77   bool 77   bool
HITCBC 78   5 ci_is_less( 78   5 ci_is_less(
79   core::string_view s0, 79   core::string_view s0,
80   core::string_view s1) noexcept 80   core::string_view s1) noexcept
81   { 81   {
HITCBC 82   5 auto p1 = s0.data(); 82   5 auto p1 = s0.data();
HITCBC 83   5 auto p2 = s1.data(); 83   5 auto p2 = s1.data();
HITCBC 84   5 auto n = s0.size() < s1.size() 84   5 auto n = s0.size() < s1.size()
HITCBC 85   5 ? s0.size() : s1.size(); 85   5 ? s0.size() : s1.size();
HITCBC 86   18 while(n != 0) 86   18 while(n != 0)
87   { 87   {
HITCBC 88   15 --n; 88   15 --n;
HITCBC 89   15 auto c1 = to_lower(*p1++); 89   15 auto c1 = to_lower(*p1++);
HITCBC 90   15 auto c2 = to_lower(*p2++); 90   15 auto c2 = to_lower(*p2++);
HITCBC 91   15 if(c1 != c2) 91   15 if(c1 != c2)
HITCBC 92   2 return c1 < c2; 92   2 return c1 < c2;
93   } 93   }
HITCBC 94   3 return s0.size() < s1.size(); 94   3 return s0.size() < s1.size();
95   } 95   }
96   96  
97   } // detail 97   } // detail
98   98  
99   //------------------------------------------------ 99   //------------------------------------------------
100   100  
101   int 101   int
HITCBC 102   21 ci_compare( 102   21 ci_compare(
103   core::string_view s0, 103   core::string_view s0,
104   core::string_view s1) noexcept 104   core::string_view s1) noexcept
105   { 105   {
106   int bias; 106   int bias;
107   std::size_t n; 107   std::size_t n;
HITCBC 108   42 if( s0.size() < 108   42 if( s0.size() <
HITCBC 109   21 s1.size()) 109   21 s1.size())
110   { 110   {
HITCBC 111   2 bias = -1; 111   2 bias = -1;
HITCBC 112   2 n = s0.size(); 112   2 n = s0.size();
113   } 113   }
114   else 114   else
115   { 115   {
HITCBC 116   38 if( s0.size() > 116   38 if( s0.size() >
HITCBC 117   19 s1.size()) 117   19 s1.size())
HITCBC 118   2 bias = 1; 118   2 bias = 1;
119   else 119   else
HITCBC 120   17 bias = 0; 120   17 bias = 0;
HITCBC 121   19 n = s1.size(); 121   19 n = s1.size();
122   } 122   }
HITCBC 123   21 auto it0 = s0.data(); 123   21 auto it0 = s0.data();
HITCBC 124   21 auto it1 = s1.data(); 124   21 auto it1 = s1.data();
HITCBC 125   38 while(n != 0) 125   38 while(n != 0)
126   { 126   {
HITCBC 127   29 --n; 127   29 --n;
128   auto c0 = 128   auto c0 =
HITCBC 129   29 to_lower(*it0++); 129   29 to_lower(*it0++);
130   auto c1 = 130   auto c1 =
HITCBC 131   29 to_lower(*it1++); 131   29 to_lower(*it1++);
HITCBC 132   29 if(c0 == c1) 132   29 if(c0 == c1)
HITCBC 133   17 continue; 133   17 continue;
HITCBC 134   12 if(c0 < c1) 134   12 if(c0 < c1)
HITCBC 135   8 return -1; 135   8 return -1;
HITCBC 136   4 return 1; 136   4 return 1;
137   } 137   }
HITCBC 138   9 return bias; 138   9 return bias;
139   } 139   }
140   140  
141   //------------------------------------------------ 141   //------------------------------------------------
142   142  
143   BOOST_URL_NO_SANITIZE_INT_OVERFLOW 143   BOOST_URL_NO_SANITIZE_INT_OVERFLOW
144   std::size_t 144   std::size_t
HITCBC 145   18 ci_digest( 145   18 ci_digest(
146   core::string_view s) noexcept 146   core::string_view s) noexcept
147   { 147   {
148   // Only 4 and 8 byte sizes are supported 148   // Only 4 and 8 byte sizes are supported
149   static_assert( 149   static_assert(
150   sizeof(std::size_t) == 4 || 150   sizeof(std::size_t) == 4 ||
151   sizeof(std::size_t) == 8, ""); 151   sizeof(std::size_t) == 8, "");
HITCBC 152   18 constexpr std::size_t prime = ( 152   18 constexpr std::size_t prime = (
153   sizeof(std::size_t) == 8) ? 153   sizeof(std::size_t) == 8) ?
154   0x100000001B3ULL : 154   0x100000001B3ULL :
155   0x01000193UL; 155   0x01000193UL;
HITCBC 156   18 constexpr std::size_t hash0 = ( 156   18 constexpr std::size_t hash0 = (
157   sizeof(std::size_t) == 8) ? 157   sizeof(std::size_t) == 8) ?
158   0xcbf29ce484222325ULL : 158   0xcbf29ce484222325ULL :
159   0x811C9DC5UL; 159   0x811C9DC5UL;
HITCBC 160   18 auto hash = hash0; 160   18 auto hash = hash0;
HITCBC 161   18 auto p = s.data(); 161   18 auto p = s.data();
HITCBC 162   18 auto n = s.size(); 162   18 auto n = s.size();
HITCBC 163   56 for(; n != 0; --n, ++p) 163   56 for(; n != 0; --n, ++p)
164   { 164   {
165   // VFALCO NOTE Consider using a lossy 165   // VFALCO NOTE Consider using a lossy
166   // to_lower which works 4 or 8 chars at a time. 166   // to_lower which works 4 or 8 chars at a time.
HITCBC 167   38 hash = (to_lower(*p) ^ hash) * prime; 167   38 hash = (to_lower(*p) ^ hash) * prime;
168   } 168   }
HITCBC 169   18 return hash; 169   18 return hash;
170   } 170   }
171   171  
172   } // grammar 172   } // grammar
173   } // urls 173   } // urls
174   } // boost 174   } // boost
175   175