third_party/bup/bupsplit_unittest.cc

// Copyright 2017 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "peridot/third_party/bup/bupsplit.h"

#include <stdlib.h>
#include <limits>

#include <lib/fxl/logging.h>

#include "gtest/gtest.h"

namespace bup {
namespace {

class RollSumSplitTest : public ::testing::Test {
 protected:
  void SetUp() override { srand(0); }
};

std::string GetValue(size_t size) {
  std::string value(size, '\0');
  for (size_t i = 0; i < value.size(); ++i) {
    value[i] = rand();
  }
  return value;
}

TEST_F(RollSumSplitTest, CheckMinMax) {
  const size_t min = 4 * 1024;
  const size_t max = 8 * 1024;

  RollSumSplit rh(min, max);

  std::string value = GetValue(1024 * 1024);
  fxl::StringView view = value;
  while (!view.empty()) {
    size_t index = rh.Feed(view, nullptr);
    if (index > 0) {
      EXPECT_TRUE(index >= min);
      EXPECT_TRUE(index <= max);
      view = view.substr(index);
    } else {
      EXPECT_TRUE(view.size() <= max);
      view = "";
    }
  }
}

// Verifies that results are the same when we feed all data at once and when we
// feed the data byte-by-byte.
TEST_F(RollSumSplitTest, CheckSameResult) {
  struct Cut {
    size_t size;
    size_t bits;
  };

  RollSumSplit rh(4 * 1024, 64 * 1024 - 1);

  std::string value = GetValue(1024 * 1024);
  fxl::StringView view = value;
  std::vector<Cut> feed_all_cuts;
  while (!view.empty()) {
    Cut cut;
    cut.size = rh.Feed(view, &cut.bits);
    if (cut.size) {
      view = view.substr(cut.size);
      feed_all_cuts.push_back(cut);
    } else {
      view = "";
    }
  }

  view = value;
  rh.Reset();
  std::vector<Cut> feed_by_byte_cuts;
  size_t index = 0;
  for (size_t i = 0; i < view.size(); ++i) {
    Cut cut;
    size_t count = rh.Feed(view.substr(i, 1), &cut.bits);
    ++index;
    if (count) {
      cut.size = index;
      feed_by_byte_cuts.push_back(cut);
      index = 0;
    }
  }

  ASSERT_EQ(feed_all_cuts.size(), feed_by_byte_cuts.size());
  EXPECT_GT(feed_all_cuts.size(), 0u);
  for (size_t i = 0; i < feed_all_cuts.size(); ++i) {
    EXPECT_EQ(feed_all_cuts[i].size, feed_by_byte_cuts[i].size);
    EXPECT_EQ(feed_all_cuts[i].bits, feed_by_byte_cuts[i].bits);
  }
}

// Check that the roll sum hash only depends on the last |kWindowSize|
// characters.
TEST_F(RollSumSplitTest, CheckWindowed) {
  RollSumSplit r1(0, std::numeric_limits<size_t>::max());
  RollSumSplit r2(0, std::numeric_limits<size_t>::max());

  // Try different initial feeds for the first hasher until finding the case
  // where the 2 hashes do not agree at least once while consuming the
  // |kWindowSize| characters.
  bool finished = false;
  for (size_t initial_feed = 1026; !finished; ++initial_feed) {
    r1.Reset();
    r2.Reset();

    r1.Feed(GetValue(initial_feed), nullptr);

    // Feed kWindowSize characters.
    std::string value = GetValue(kWindowSize);
    fxl::StringView view = value;
    for (size_t i = 0; i < view.size(); ++i) {
      auto f1 = r1.Feed(view.substr(i, 1), nullptr);
      auto f2 = r2.Feed(view.substr(i, 1), nullptr);
      finished = finished || (f1 != f2);
    }
    value = GetValue(1024 * 1024);
    EXPECT_EQ(r1.Feed(value, nullptr), r2.Feed(value, nullptr));
  }
}

}  // namespace
}  // namespace bup