15d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved.
25d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be
35d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// found in the LICENSE file.
45d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
55d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "net/spdy/hpack_string_util.h"
65d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
75d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include <cstddef>
85d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include <cstring>
95d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "base/basictypes.h"
115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "base/logging.h"
125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "base/strings/string_piece.h"
135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "testing/gtest/include/gtest/gtest.h"
145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)namespace net {
165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)namespace {
185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)using std::string;
205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Make sure StringPiecesEqualConstantTime() behaves like the regular
225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// string equality operator.
235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)TEST(HpackStringUtilTest, StringPiecesEqualConstantTime) {
245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  EXPECT_TRUE(StringPiecesEqualConstantTime("foo", "foo"));
255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  EXPECT_FALSE(StringPiecesEqualConstantTime("foo", "foox"));
265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  EXPECT_FALSE(StringPiecesEqualConstantTime("foo", "bar"));
275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)}
285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// TODO(jgraettinger): Support this benchmark.
305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)/*
315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)enum BM_StringPieceEqualityType {
325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  STRCMP_EQUAL,
335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  STRCMP_FIRST_CHAR_DIFFERS,
345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  STRING_PIECES_EQUAL_CONSTANT_TIME_EQUAL,
355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  STRING_PIECES_EQUAL_CONSTANT_TIME_FIRST_CHAR_DIFFERS,
365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)};
375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void BM_StringPieceEquality(int iters, int size, int type_int) {
395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  BM_StringPieceEqualityType type =
405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      static_cast<BM_StringPieceEqualityType>(type_int);
415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  string str_a(size, 'x');
425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  string str_b(size, 'x');
435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  int result = 0;
445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  switch (type) {
455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    case STRCMP_EQUAL:
465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      for (int i = 0; i < iters; ++i) {
475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        result |= std::strcmp(str_a.c_str(), str_b.c_str());
485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      }
495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      CHECK_EQ(result, 0);
505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      return;
515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    case STRCMP_FIRST_CHAR_DIFFERS:
535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      str_b[0] = 'y';
545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      for (int i = 0; i < iters; ++i) {
555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        result |= std::strcmp(str_a.c_str(), str_b.c_str());
565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      }
575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      CHECK_LT(result, 0);
585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      return;
595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    case STRING_PIECES_EQUAL_CONSTANT_TIME_EQUAL:
615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      for (int i = 0; i < iters; ++i) {
625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        result |= StringPiecesEqualConstantTime(str_a, str_b);
635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      }
645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      CHECK_EQ(result, 1);
655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      return;
665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    case STRING_PIECES_EQUAL_CONSTANT_TIME_FIRST_CHAR_DIFFERS:
685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      str_b[0] = 'y';
695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      for (int i = 0; i < iters; ++i) {
705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        result |= StringPiecesEqualConstantTime(str_a, str_b);
715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      }
725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      CHECK_EQ(result, 0);
735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      return;
745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  }
755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  DCHECK(false);
775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)}
785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Results should resemble the table below, where 0 and 1 are clearly
805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// different (STRCMP), but 2 and 3 are roughly the same
815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// (STRING_PIECES_EQUAL_CONSTANT_TIME).
825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)//
835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// DEBUG: Benchmark                     Time(ns)    CPU(ns) Iterations
845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// -------------------------------------------------------------------
855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// DEBUG: BM_StringPieceEquality/1M/0      77796      77141       7778
865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// DEBUG: BM_StringPieceEquality/1M/1         10         10   70000000
875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// DEBUG: BM_StringPieceEquality/1M/2    7729735    7700000        100
885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// DEBUG: BM_StringPieceEquality/1M/3    7803051    7800000        100
895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)BENCHMARK(BM_StringPieceEquality)
905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  ->ArgPair(1<<20, STRCMP_EQUAL)
915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  ->ArgPair(1<<20, STRCMP_FIRST_CHAR_DIFFERS)
925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  ->ArgPair(1<<20, STRING_PIECES_EQUAL_CONSTANT_TIME_EQUAL)
935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  ->ArgPair(1<<20, STRING_PIECES_EQUAL_CONSTANT_TIME_FIRST_CHAR_DIFFERS);
945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)*/
955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)}  // namespace
975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)}  // namespace net
99