base/i18n/streaming_utf8_validator_perftest.cc

   1 // Copyright 2014 The Chromium Authors
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // All data that is passed through a WebSocket with type "Text" needs to be
   6 // validated as UTF8. Since this is done on the IO thread, it needs to be
   7 // reasonably fast.
   8
   9 // We are only interested in the performance on valid UTF8. Invalid UTF8 will
  10 // result in a connection failure, so is unlikely to become a source of
  11 // performance issues.
  12
  13 #include "base/i18n/streaming_utf8_validator.h"
  14
  15 #include <stddef.h>
  16
  17 #include <string>
  18
  19 #include "base/functional/bind.h"
  20 #include "base/functional/callback.h"
  21 #include "base/strings/string_util.h"
  22 #include "base/strings/stringprintf.h"
  23 #include "base/test/perf_time_logger.h"
  24 #include "testing/gtest/include/gtest/gtest.h"
  25
  26 namespace base {
  27 namespace {
  28
  29 // We want to test ranges of valid UTF-8 sequences. These ranges are inclusive.
  30 // They are intended to be large enough that the validator needs to do
  31 // meaningful work while being in some sense "realistic" (eg. control characters
  32 // are not included).
  33 const char kOneByteSeqRangeStart[] = " ";  // U+0020
  34 const char kOneByteSeqRangeEnd[] = "~";    // U+007E
  35
  36 const char kTwoByteSeqRangeStart[] = "\xc2\xa0";  // U+00A0 non-breaking space
  37 const char kTwoByteSeqRangeEnd[] = "\xc9\x8f";    // U+024F small y with stroke
  38
  39 const char kThreeByteSeqRangeStart[] = "\xe3\x81\x82";  // U+3042 Hiragana "a"
  40 const char kThreeByteSeqRangeEnd[] = "\xe9\xbf\x83";    // U+9FC3 "to blink"
  41
  42 const char kFourByteSeqRangeStart[] = "\xf0\xa0\x80\x8b";  // U+2000B
  43 const char kFourByteSeqRangeEnd[] = "\xf0\xaa\x9a\xb2";    // U+2A6B2
  44
  45 // The different lengths of strings to test.
  46 const size_t kTestLengths[] = {1, 32, 256, 32768, 1 << 20};
  47
  48 // Simplest possible byte-at-a-time validator, to provide a baseline
  49 // for comparison. This is only tried on 1-byte UTF-8 sequences, as
  50 // the results will not be meaningful with sequences containing
  51 // top-bit-set bytes.
  52 bool IsString7Bit(const std::string& s) {
  53   for (auto it : s) {
  54     if (it & 0x80)
  55       return false;
  56   }
  57   return true;
  58 }
  59
  60 // Assumes that |previous| is a valid UTF-8 sequence, and attempts to return
  61 // the next one. Is just barely smart enough to iterate through the ranges
  62 // defined about.
  63 std::string NextUtf8Sequence(const std::string& previous) {
  64   DCHECK(StreamingUtf8Validator::Validate(previous));
  65   std::string next = previous;
  66   for (int i = static_cast<int>(previous.length() - 1); i >= 0; --i) {
  67     // All bytes in a UTF-8 sequence except the first one are
  68     // constrained to the range 0x80 to 0xbf, inclusive. When we
  69     // increment past 0xbf, we carry into the previous byte.
  70     if (i > 0 && next[i] == '\xbf') {
  71       next[i] = '\x80';
  72       continue;  // carry
  73     }
  74     ++next[i];
  75     break;  // no carry
  76   }
  77   DCHECK(StreamingUtf8Validator::Validate(next))
  78       << "Result \"" << next << "\" failed validation";
  79   return next;
  80 }
  81
  82 typedef bool (*TestTargetType)(const std::string&);
  83
  84 // Run fuction |target| over |test_string| |times| times, and report the results
  85 // using |description|.
  86 bool RunTest(const std::string& description,
  87              TestTargetType target,
  88              const std::string& test_string,
  89              int times) {
  90   base::PerfTimeLogger timer(description.c_str());
  91   bool result = true;
  92   for (int i = 0; i < times; ++i) {
  93     result = target(test_string) && result;
  94   }
  95   timer.Done();
  96   return result;
  97 }
  98
  99 // Construct a string by repeating |input| enough times to equal or exceed
 100 // |length|.
 101 std::string ConstructRepeatedTestString(const std::string& input,
 102                                         size_t length) {
 103   std::string output = input;
 104   while (output.length() * 2 < length) {
 105     output += output;
 106   }
 107   if (output.length() < length) {
 108     output += ConstructRepeatedTestString(input, length - output.length());
 109   }
 110   return output;
 111 }
 112
 113 // Construct a string by expanding the range of UTF-8 sequences
 114 // between |input_start| and |input_end|, inclusive, and then
 115 // repeating the resulting string until it equals or exceeds |length|
 116 // bytes. |input_start| and |input_end| must be valid UTF-8
 117 // sequences.
 118 std::string ConstructRangedTestString(const std::string& input_start,
 119                                       const std::string& input_end,
 120                                       size_t length) {
 121   std::string output = input_start;
 122   std::string input = input_start;
 123   while (output.length() < length && input != input_end) {
 124     input = NextUtf8Sequence(input);
 125     output += input;
 126   }
 127   if (output.length() < length) {
 128     output = ConstructRepeatedTestString(output, length);
 129   }
 130   return output;
 131 }
 132
 133 struct TestFunctionDescription {
 134   TestTargetType function;
 135   const char* function_name;
 136 };
 137
 138 bool IsStringUTF8(const std::string& str) {
 139   return base::IsStringUTF8(base::StringPiece(str));
 140 }
 141
 142 // IsString7Bit is intentionally placed last so it can be excluded easily.
 143 const TestFunctionDescription kTestFunctions[] = {
 144     {&StreamingUtf8Validator::Validate, "StreamingUtf8Validator"},
 145     {&IsStringUTF8, "IsStringUTF8"}, {&IsString7Bit, "IsString7Bit"}};
 146
 147 // Construct a test string from |construct_test_string| for each of the lengths
 148 // in |kTestLengths| in turn. For each string, run each test in |test_functions|
 149 // for a number of iterations such that the total number of bytes validated
 150 // is around 16MB.
 151 void RunSomeTests(
 152     const char format[],
 153     base::RepeatingCallback<std::string(size_t length)> construct_test_string,
 154     const TestFunctionDescription* test_functions,
 155     size_t test_count) {
 156   for (auto length : kTestLengths) {
 157     const std::string test_string = construct_test_string.Run(length);
 158     const int real_length = static_cast<int>(test_string.length());
 159     const int times = (1 << 24) / real_length;
 160     for (size_t test_index = 0; test_index < test_count; ++test_index) {
 161       EXPECT_TRUE(RunTest(StringPrintfNonConstexpr(
 162                               format, test_functions[test_index].function_name,
 163                               real_length, times),
 164                           test_functions[test_index].function, test_string,
 165                           times));
 166     }
 167   }
 168 }
 169
 170 TEST(StreamingUtf8ValidatorPerfTest, OneByteRepeated) {
 171   RunSomeTests(
 172       "%s: bytes=1 repeated length=%d repeat=%d",
 173       base::BindRepeating(ConstructRepeatedTestString, kOneByteSeqRangeStart),
 174       kTestFunctions, 3);
 175 }
 176
 177 TEST(StreamingUtf8ValidatorPerfTest, OneByteRange) {
 178   RunSomeTests("%s: bytes=1 ranged length=%d repeat=%d",
 179                base::BindRepeating(ConstructRangedTestString,
 180                                    kOneByteSeqRangeStart, kOneByteSeqRangeEnd),
 181                kTestFunctions, 3);
 182 }
 183
 184 TEST(StreamingUtf8ValidatorPerfTest, TwoByteRepeated) {
 185   RunSomeTests(
 186       "%s: bytes=2 repeated length=%d repeat=%d",
 187       base::BindRepeating(ConstructRepeatedTestString, kTwoByteSeqRangeStart),
 188       kTestFunctions, 2);
 189 }
 190
 191 TEST(StreamingUtf8ValidatorPerfTest, TwoByteRange) {
 192   RunSomeTests("%s: bytes=2 ranged length=%d repeat=%d",
 193                base::BindRepeating(ConstructRangedTestString,
 194                                    kTwoByteSeqRangeStart, kTwoByteSeqRangeEnd),
 195                kTestFunctions, 2);
 196 }
 197
 198 TEST(StreamingUtf8ValidatorPerfTest, ThreeByteRepeated) {
 199   RunSomeTests(
 200       "%s: bytes=3 repeated length=%d repeat=%d",
 201       base::BindRepeating(ConstructRepeatedTestString, kThreeByteSeqRangeStart),
 202       kTestFunctions, 2);
 203 }
 204
 205 TEST(StreamingUtf8ValidatorPerfTest, ThreeByteRange) {
 206   RunSomeTests(
 207       "%s: bytes=3 ranged length=%d repeat=%d",
 208       base::BindRepeating(ConstructRangedTestString, kThreeByteSeqRangeStart,
 209                           kThreeByteSeqRangeEnd),
 210       kTestFunctions, 2);
 211 }
 212
 213 TEST(StreamingUtf8ValidatorPerfTest, FourByteRepeated) {
 214   RunSomeTests(
 215       "%s: bytes=4 repeated length=%d repeat=%d",
 216       base::BindRepeating(ConstructRepeatedTestString, kFourByteSeqRangeStart),
 217       kTestFunctions, 2);
 218 }
 219
 220 TEST(StreamingUtf8ValidatorPerfTest, FourByteRange) {
 221   RunSomeTests(
 222       "%s: bytes=4 ranged length=%d repeat=%d",
 223       base::BindRepeating(ConstructRangedTestString, kFourByteSeqRangeStart,
 224                           kFourByteSeqRangeEnd),
 225       kTestFunctions, 2);
 226 }
 227
 228 }  // namespace
 229 }  // namespace base