utils_unittest.cc

// Copyright 2020 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the Chromium source repository LICENSE file.

#include "infcover.h"

#include <cstddef>
#include <vector>

#include "compression_utils_portable.h"
#include "gtest.h"

#if !defined(CMAKE_STANDALONE_UNITTESTS)
#include "base/files/file_path.h"
#include "base/files/scoped_temp_dir.h"
#include "base/path_service.h"

#include "third_party/zlib/contrib/minizip/unzip.h"
#include "third_party/zlib/contrib/minizip/zip.h"
#endif

#include "zlib.h"

void TestPayloads(size_t input_size, zlib_internal::WrapperType type,
                  const int compression_level = Z_DEFAULT_COMPRESSION) {
  std::vector<unsigned char> input;
  input.reserve(input_size);
  for (size_t i = 1; i <= input_size; ++i)
    input.push_back(i & 0xff);

  // If it is big enough for GZIP, will work for other wrappers.
  std::vector<unsigned char> compressed(
      zlib_internal::GzipExpectedCompressedSize(input.size()));
  std::vector<unsigned char> decompressed(input.size());

  // Libcores's java/util/zip/Deflater default settings: ZLIB,
  // DEFAULT_COMPRESSION and DEFAULT_STRATEGY.
  unsigned long compressed_size = static_cast<unsigned long>(compressed.size());
  int result = zlib_internal::CompressHelper(
      type, compressed.data(), &compressed_size, input.data(), input.size(),
      compression_level, nullptr, nullptr);
  ASSERT_EQ(result, Z_OK);

  unsigned long decompressed_size =
      static_cast<unsigned long>(decompressed.size());
  result = zlib_internal::UncompressHelper(type, decompressed.data(),
                                           &decompressed_size,
                                           compressed.data(), compressed_size);
  ASSERT_EQ(result, Z_OK);
  EXPECT_EQ(input, decompressed);
}

TEST(ZlibTest, ZlibWrapper) {
  // Minimal ZLIB wrapped short stream size is about 8 bytes.
  for (size_t i = 1; i < 1024; ++i)
    TestPayloads(i, zlib_internal::WrapperType::ZLIB);
}

TEST(ZlibTest, GzipWrapper) {
  // GZIP should be 12 bytes bigger than ZLIB wrapper.
  for (size_t i = 1; i < 1024; ++i)
    TestPayloads(i, zlib_internal::WrapperType::GZIP);
}

TEST(ZlibTest, RawWrapper) {
  // RAW has no wrapper (V8 Blobs is a known user), size
  // should be payload_size + 2 for short payloads.
  for (size_t i = 1; i < 1024; ++i)
    TestPayloads(i, zlib_internal::WrapperType::ZRAW);
}

TEST(ZlibTest, LargePayloads) {
  static const size_t lengths[] = { 6000, 8000, 10'000, 15'000, 20'000, 30'000,
                                    50'000, 100'000, 150'000, 2'500'000,
                                    5'000'000, 10'000'000, 20'000'000 };

  for (size_t length: lengths) {
    TestPayloads(length, zlib_internal::WrapperType::ZLIB);
    TestPayloads(length, zlib_internal::WrapperType::GZIP);
  }
}

TEST(ZlibTest, CompressionLevels) {
  static const int levels[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  for (int level: levels) {
    TestPayloads(5'000'000, zlib_internal::WrapperType::ZLIB, level);
    TestPayloads(5'000'000, zlib_internal::WrapperType::GZIP, level);
  }
}

TEST(ZlibTest, InflateCover) {
  cover_support();
  cover_wrap();
  cover_back();
  cover_inflate();
  // TODO(cavalcantii): enable this last test.
  // cover_trees();
  cover_fast();
}

TEST(ZlibTest, InflateCVE) {
  cover_CVE_2022_37434();
}

TEST(ZlibTest, DeflateStored) {
  const int no_compression = 0;
  const zlib_internal::WrapperType type = zlib_internal::WrapperType::GZIP;
  std::vector<unsigned char> input(1 << 10, 42);
  std::vector<unsigned char> compressed(
      zlib_internal::GzipExpectedCompressedSize(input.size()));
  std::vector<unsigned char> decompressed(input.size());
  unsigned long compressed_size = static_cast<unsigned long>(compressed.size());
  int result = zlib_internal::CompressHelper(
      type, compressed.data(), &compressed_size, input.data(), input.size(),
      no_compression, nullptr, nullptr);
  ASSERT_EQ(result, Z_OK);

  unsigned long decompressed_size =
      static_cast<unsigned long>(decompressed.size());
  result = zlib_internal::UncompressHelper(type, decompressed.data(),
                                           &decompressed_size,
                                           compressed.data(), compressed_size);
  ASSERT_EQ(result, Z_OK);
  EXPECT_EQ(input, decompressed);
}

TEST(ZlibTest, StreamingInflate) {
  uint8_t comp_buf[4096], decomp_buf[4096];
  z_stream comp_strm, decomp_strm;
  int ret;

  std::vector<uint8_t> src;
  for (size_t i = 0; i < 1000; i++) {
    for (size_t j = 0; j < 40; j++) {
      src.push_back(j);
    }
  }

  // Deflate src into comp_buf.
  comp_strm.zalloc = Z_NULL;
  comp_strm.zfree = Z_NULL;
  comp_strm.opaque = Z_NULL;
  ret = deflateInit(&comp_strm, Z_BEST_COMPRESSION);
  ASSERT_EQ(ret, Z_OK);
  comp_strm.next_out = comp_buf;
  comp_strm.avail_out = sizeof(comp_buf);
  comp_strm.next_in = src.data();
  comp_strm.avail_in = src.size();
  ret = deflate(&comp_strm, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);
  size_t comp_sz = sizeof(comp_buf) - comp_strm.avail_out;

  // Inflate comp_buf one 4096-byte buffer at a time.
  decomp_strm.zalloc = Z_NULL;
  decomp_strm.zfree = Z_NULL;
  decomp_strm.opaque = Z_NULL;
  ret = inflateInit(&decomp_strm);
  ASSERT_EQ(ret, Z_OK);
  decomp_strm.next_in = comp_buf;
  decomp_strm.avail_in = comp_sz;

  while (decomp_strm.avail_in > 0) {
    decomp_strm.next_out = decomp_buf;
    decomp_strm.avail_out = sizeof(decomp_buf);
    ret = inflate(&decomp_strm, Z_FINISH);
    ASSERT_TRUE(ret == Z_OK || ret == Z_STREAM_END || ret == Z_BUF_ERROR);

    // Verify the output bytes.
    size_t num_out = sizeof(decomp_buf) - decomp_strm.avail_out;
    for (size_t i = 0; i < num_out; i++) {
      EXPECT_EQ(decomp_buf[i], src[decomp_strm.total_out - num_out + i]);
    }
  }

  // Cleanup memory (i.e. makes ASAN bot happy).
  ret = deflateEnd(&comp_strm);
  EXPECT_EQ(ret, Z_OK);
  ret = inflateEnd(&decomp_strm);
  EXPECT_EQ(ret, Z_OK);
}

TEST(ZlibTest, CRCHashBitsCollision) {
  // The CRC32c of the hex sequences 2a,14,14,14 and 2a,14,db,14 have the same
  // lower 9 bits. Since longest_match doesn't check match[2], a bad match could
  // be chosen when the number of hash bits is <= 9. For this reason, the number
  // of hash bits must be set higher, regardless of the memlevel parameter, when
  // using CRC32c hashing for string matching. See https://crbug.com/1113596

  std::vector<uint8_t> src = {
      // Random byte; zlib doesn't match at offset 0.
      123,

      // This will look like 5-byte match.
      0x2a,
      0x14,
      0xdb,
      0x14,
      0x15,

      // Offer a 4-byte match to bump the next expected match length to 5.
      0x2a,
      0x14,
      0x14,
      0x14,

      0x2a,
      0x14,
      0x14,
      0x14,
      0x15,
  };

  z_stream stream;
  stream.zalloc = nullptr;
  stream.zfree = nullptr;

  // Using a low memlevel to try to reduce the number of hash bits. Negative
  // windowbits means raw deflate, i.e. without the zlib header.
  int ret = deflateInit2(&stream, /*comp level*/ 2, /*method*/ Z_DEFLATED,
                         /*windowbits*/ -15, /*memlevel*/ 2,
                         /*strategy*/ Z_DEFAULT_STRATEGY);
  ASSERT_EQ(ret, Z_OK);
  std::vector<uint8_t> compressed(100, '\0');
  stream.next_out = compressed.data();
  stream.avail_out = compressed.size();
  stream.next_in = src.data();
  stream.avail_in = src.size();
  ret = deflate(&stream, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);
  compressed.resize(compressed.size() - stream.avail_out);
  deflateEnd(&stream);

  ret = inflateInit2(&stream, /*windowbits*/ -15);
  ASSERT_EQ(ret, Z_OK);
  std::vector<uint8_t> decompressed(src.size(), '\0');
  stream.next_in = compressed.data();
  stream.avail_in = compressed.size();
  stream.next_out = decompressed.data();
  stream.avail_out = decompressed.size();
  ret = inflate(&stream, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);
  EXPECT_EQ(0U, stream.avail_out);
  inflateEnd(&stream);

  EXPECT_EQ(src, decompressed);
}

TEST(ZlibTest, CRCHashAssert) {
  // The CRC32c of the hex sequences ff,ff,5e,6f and ff,ff,13,ff have the same
  // lower 15 bits. This means longest_match's assert that match[2] == scan[2]
  // won't hold. However, such hash collisions are only possible when one of the
  // other four bytes also mismatch. This tests that zlib's assert handles this
  // case.

  std::vector<uint8_t> src = {
      // Random byte; zlib doesn't match at offset 0.
      123,

      // This has the same hash as the last byte sequence, and the first two and
      // last two bytes match; though the third and the fourth don't.
      0xff,
      0xff,
      0x5e,
      0x6f,
      0x12,
      0x34,

      // Offer a 5-byte match to bump the next expected match length to 6
      // (because the two first and two last bytes need to match).
      0xff,
      0xff,
      0x13,
      0xff,
      0x12,

      0xff,
      0xff,
      0x13,
      0xff,
      0x12,
      0x34,
  };

  z_stream stream;
  stream.zalloc = nullptr;
  stream.zfree = nullptr;

  int ret = deflateInit2(&stream, /*comp level*/ 5, /*method*/ Z_DEFLATED,
                         /*windowbits*/ -15, /*memlevel*/ 8,
                         /*strategy*/ Z_DEFAULT_STRATEGY);
  ASSERT_EQ(ret, Z_OK);
  std::vector<uint8_t> compressed(100, '\0');
  stream.next_out = compressed.data();
  stream.avail_out = compressed.size();
  stream.next_in = src.data();
  stream.avail_in = src.size();
  ret = deflate(&stream, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);
  compressed.resize(compressed.size() - stream.avail_out);
  deflateEnd(&stream);

  ret = inflateInit2(&stream, /*windowbits*/ -15);
  ASSERT_EQ(ret, Z_OK);
  std::vector<uint8_t> decompressed(src.size(), '\0');
  stream.next_in = compressed.data();
  stream.avail_in = compressed.size();
  stream.next_out = decompressed.data();
  stream.avail_out = decompressed.size();
  ret = inflate(&stream, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);
  EXPECT_EQ(0U, stream.avail_out);
  inflateEnd(&stream);

  EXPECT_EQ(src, decompressed);
}

// Fuzzer generated.
static const uint8_t checkMatchCrashData[] = {
    0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0xc5, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x58, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x1e, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1f, 0x00,
    0x6e, 0x6e, 0x6e, 0x00, 0x00, 0x00, 0x00, 0x6e, 0x01, 0x39, 0x6e, 0x6e,
    0x00, 0x00, 0x00, 0x00, 0xf7, 0xff, 0x00, 0x00, 0x00, 0x00, 0x6e, 0x6e,
    0x00, 0x00, 0x0a, 0x9a, 0x00, 0x00, 0x6e, 0x6e, 0x6e, 0x2a, 0x00, 0x00,
    0x00, 0xd5, 0xf0, 0x00, 0x81, 0x02, 0xf3, 0xfd, 0xff, 0xab, 0xf3, 0x6e,
    0x7e, 0x04, 0x5b, 0xf6, 0x2a, 0x2c, 0xf8, 0x00, 0x54, 0xf3, 0xa5, 0x0e,
    0xfd, 0x6e, 0xff, 0x00, 0xfd, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0xa4, 0x0b, 0xa5, 0x2a, 0x0d, 0x10, 0x01, 0x26, 0xf6, 0x04, 0x0e,
    0xff, 0x6e, 0x6e, 0x6e, 0x76, 0x00, 0x00, 0x87, 0x01, 0xfe, 0x0d, 0xb6,
    0x6e, 0x6e, 0xf7, 0x00, 0x00, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0xfd, 0x00, 0x2a, 0x00, 0x00, 0x00, 0x00, 0x29, 0x00, 0x9b,
    0x02, 0x00, 0x00, 0x00, 0x00, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a,
    0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x6e, 0xff, 0xff, 0x00,
    0x00, 0xd5, 0xf0, 0x00, 0xff, 0x40, 0x7e, 0x0b, 0xa5, 0x10, 0x67, 0x01,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x58, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1e, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x1f, 0x40, 0x7e, 0x0b, 0xa5, 0x10, 0x67,
    0x7e, 0x32, 0x6e, 0x00, 0x00, 0x00, 0x3c, 0x00, 0x00, 0x40, 0x0b, 0xa5,
    0x10, 0x67, 0x01, 0xfe, 0x0d, 0xb6, 0x2a, 0x00, 0x00, 0x58, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x6e, 0xfd, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x3d, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3d, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0xd6, 0x2d, 0x2d, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a,
    0x8a, 0x8a, 0x8a, 0x8a, 0x66, 0x8a, 0x8a, 0x8a, 0xee, 0x1d, 0x00, 0x00,
    0x00, 0x02, 0x00, 0x00, 0x00, 0xee, 0x0a, 0x00, 0x00, 0x00, 0x54, 0x40,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0xf3, 0x00, 0x00, 0xff, 0xff, 0x23, 0x7e, 0x00, 0x1e,
    0x00, 0x00, 0xd5, 0xf0, 0x00, 0xff, 0x40, 0x0b, 0xa5, 0x10, 0x67, 0x01,
    0xfe, 0x0d, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a,
    0x8a, 0x8a, 0x8a, 0x2d, 0x6e, 0x2d, 0x00, 0x00, 0x00, 0x00, 0x0e, 0x0e,
    0xfb, 0x00, 0x10, 0x24, 0x00, 0x00, 0xfb, 0xff, 0x00, 0x00, 0xff, 0x1f,
    0xb3, 0x00, 0x04, 0x3d, 0x00, 0xee, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3d, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x3d, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0e, 0x00, 0x00,
    0x01, 0x45, 0x3d, 0x00, 0x00, 0x00, 0xfd, 0x00, 0x11, 0x21, 0x00, 0x1e,
    0x00, 0x0c, 0xb3, 0xfe, 0x0e, 0xee, 0x02, 0x00, 0x1d, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x6e, 0x6e, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0x6e, 0x00,
    0x00, 0x87, 0x00, 0x33, 0x38, 0x6e, 0x6e, 0x6e, 0x6e, 0x6e, 0x00, 0x00,
    0x00, 0x38, 0x00, 0x00, 0xff, 0xff, 0xff, 0x04, 0x3f, 0xff, 0xff, 0xff,
    0x00, 0x00, 0x00, 0x00, 0xf0, 0x00, 0xff, 0x00, 0x31, 0x13, 0x13, 0x13,
    0x0b, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xab, 0x30, 0x83, 0x33,
    0x00, 0x00, 0x01, 0x05, 0x00, 0x00, 0xff, 0xff, 0x7d, 0xff, 0x00, 0x01,
    0x10, 0x0d, 0x2a, 0xa5, 0x00, 0x00, 0x00, 0x00, 0x00, 0xfd, 0x00, 0x11,
    0x21, 0x00, 0xa5, 0x00, 0x68, 0x68, 0x68, 0x67, 0x00, 0x00, 0xff, 0xff,
    0x02, 0x00, 0x00, 0x68, 0x68, 0x68, 0x68, 0x00, 0x00, 0xfa, 0xff, 0xff,
    0x03, 0x01, 0xff, 0x02, 0x00, 0x00, 0x68, 0x68, 0x68, 0x68, 0x0a, 0x10,
    0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff,
    0x06, 0x00, 0x00, 0x2b, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0xfa, 0xff, 0xff, 0x08, 0xff, 0xff, 0xff, 0x00, 0x06, 0x04,
    0x00, 0xf8, 0xff, 0xff, 0x00, 0x01, 0x00, 0x00, 0x25, 0x00, 0x00, 0x00,
    0x00, 0xff, 0x00, 0x00, 0x0b, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x78, 0x00, 0x00, 0x01, 0x00, 0xff, 0xff, 0xff, 0x00, 0x06, 0x04, 0x6e,
    0x7e, 0x87, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3d, 0x00, 0x00,
    0x00, 0x6e, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x87, 0x6e, 0x6e, 0x6e,
    0x00, 0x01, 0x38, 0xd5, 0xf0, 0x00, 0x00, 0x2a, 0xfe, 0x04, 0x5b, 0x0d,
    0xfd, 0x6e, 0x92, 0x28, 0xf9, 0xfb, 0xff, 0x07, 0xd2, 0xd6, 0x2d, 0x2d,
    0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a,
    0x8a, 0x8a, 0xc2, 0x91, 0x00, 0x5b, 0xef, 0xde, 0xf2, 0x6e, 0x6e, 0xfd,
    0x0c, 0x02, 0x91, 0x62, 0x91, 0xfd, 0x6e, 0x6e, 0xd3, 0x06, 0x00, 0x00,
    0x1e, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3f, 0x00,
    0xd5, 0xf0, 0x00, 0xff, 0x00, 0x00, 0x31, 0x13, 0x13, 0x13, 0x04, 0x00,
    0x00, 0x00, 0x00, 0x0b, 0x00, 0x00, 0x04, 0x00, 0x13, 0x0a, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0x6e, 0x00, 0x00, 0x01,
    0x00, 0x00, 0x09, 0x00, 0x6a, 0x24, 0x26, 0x30, 0x01, 0x2e, 0x2a, 0xfe,
    0x04, 0x5b, 0x0d, 0xfd, 0x6e, 0x6e, 0xd7, 0x06, 0x6e, 0x6e, 0x6e, 0x00,
    0x00, 0xb1, 0xb1, 0xb1, 0xb1, 0x00, 0x00, 0x00, 0x6e, 0x5b, 0x00, 0x00,
    0x58, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x58, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x01, 0x05, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x58, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x1e, 0x00, 0x00, 0x00, 0x87, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x38,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x6b, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x0b,
    0x00, 0x00, 0x00, 0x00, 0xff, 0x00, 0x00, 0x24, 0x2a, 0x6e, 0x5c, 0x24,
    0x00, 0x00, 0x00, 0x0a, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x87, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xeb,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x05, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x40, 0x00, 0x40, 0x00, 0x00, 0x00, 0x58, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x58, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
    0x05, 0x00, 0x00, 0x00, 0x5d, 0x10, 0x6e, 0x6e, 0xa5, 0x2f, 0x00, 0x00,
    0x95, 0x87, 0x00, 0x6e};

TEST(ZlibTest, CheckMatchCrash) {
  // See https://crbug.com/1113142.
  z_stream stream;
  stream.zalloc = nullptr;
  stream.zfree = nullptr;

  // Low windowbits to hit window sliding also with a relatively small input.
  int ret = deflateInit2(&stream, /*comp level*/ 5, /*method*/ Z_DEFLATED,
                         /*windowbits*/ -9, /*memlevel*/ 8,
                         /*strategy*/ Z_DEFAULT_STRATEGY);
  ASSERT_EQ(ret, Z_OK);

  uint8_t compressed[sizeof(checkMatchCrashData) * 2];
  stream.next_out = compressed;
  stream.avail_out = sizeof(compressed);

  for (size_t i = 0; i < sizeof(checkMatchCrashData); i++) {
    ASSERT_GT(stream.avail_out, 0U);
    stream.next_in = (uint8_t*)&checkMatchCrashData[i];
    stream.avail_in = 1;
    ret = deflate(&stream, Z_NO_FLUSH);
    ASSERT_EQ(ret, Z_OK);
  }

  stream.next_in = nullptr;
  stream.avail_in = 0;
  ASSERT_GT(stream.avail_out, 0U);
  ret = deflate(&stream, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);
  size_t compressed_sz = sizeof(compressed) - stream.avail_out;
  deflateEnd(&stream);

  uint8_t decompressed[sizeof(checkMatchCrashData)];
  ret = inflateInit2(&stream, -15);
  ASSERT_EQ(ret, Z_OK);
  stream.next_in = compressed;
  stream.avail_in = compressed_sz;
  stream.next_out = decompressed;
  stream.avail_out = sizeof(decompressed);
  ret = inflate(&stream, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);
  inflateEnd(&stream);
  ASSERT_EQ(
      memcmp(checkMatchCrashData, decompressed, sizeof(checkMatchCrashData)),
      0);
}

TEST(ZlibTest, DeflateRLEUninitUse) {
  // MSan would complain about use of uninitialized values in deflate_rle if the
  // window isn't zero-initialized. See crbug.com/1137613. Similar problems
  // exist in other places in zlib, e.g. longest_match (crbug.com/1144420) but
  // we don't have as nice test cases.

  int level = 9;
  int windowBits = 9;
  int memLevel = 8;
  int strategy = Z_RLE;
  const std::vector<uint8_t> src{
      0x31, 0x64, 0x38, 0x32, 0x30, 0x32, 0x30, 0x36, 0x65, 0x35, 0x38, 0x35,
      0x32, 0x61, 0x30, 0x36, 0x65, 0x35, 0x32, 0x66, 0x30, 0x34, 0x38, 0x37,
      0x61, 0x31, 0x38, 0x36, 0x37, 0x37, 0x31, 0x39, 0x0a, 0x65, 0x62, 0x00,
      0x9f, 0xff, 0xc6, 0xc6, 0xc6, 0xff, 0x09, 0x00, 0x62, 0x00, 0x9f, 0xff,
      0xc6, 0xc6, 0xc6, 0xff, 0x09, 0x00, 0x62, 0x00, 0x9f, 0xff, 0xc6, 0xc6,
      0xc6, 0xff, 0x09, 0x00, 0x62, 0x00, 0x9f, 0xff, 0xc6, 0xc6, 0xc6, 0x95,
      0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0d, 0x0e, 0x0a, 0x54, 0x52,
      0x58, 0x56, 0xab, 0x26, 0x13, 0x53, 0x5a, 0xb5, 0x30, 0xbb, 0x96, 0x44,
      0x80, 0xe6, 0xc5, 0x0a, 0xd0, 0x47, 0x7a, 0xa0, 0x4e, 0xbe, 0x30, 0xdc,
      0xa1, 0x08, 0x54, 0xe1, 0x51, 0xd1, 0xea, 0xef, 0xdb, 0xa1, 0x2d, 0xb4,
      0xb9, 0x58, 0xb1, 0x2f, 0xf0, 0xae, 0xbc, 0x07, 0xd1, 0xba, 0x7f, 0x14,
      0xa4, 0xde, 0x99, 0x7f, 0x4d, 0x3e, 0x25, 0xd9, 0xef, 0xee, 0x4f, 0x38,
      0x7b, 0xaf, 0x3f, 0x6b, 0x53, 0x5a, 0xcb, 0x1f, 0x97, 0xb5, 0x43, 0xa3,
      0xe8, 0xff, 0x09, 0x00, 0x62, 0x00, 0x9f, 0xff, 0xc6, 0xc6, 0xc6, 0xff,
      0x09, 0x00, 0x62, 0x00, 0x9f, 0xff, 0xc6, 0xc6, 0xc6, 0xff, 0x09, 0x00,
      0x62, 0x00, 0x9f, 0xff, 0xc6, 0xc6, 0xc6, 0xff, 0x09, 0x00, 0x62, 0x00,
      0x9f, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x3c,
      0x73, 0x70, 0x23, 0x87, 0xec, 0xf8, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0xc1, 0x00, 0x00, 0x9f, 0xc6, 0xc6, 0xff, 0x09, 0x00, 0x62, 0x00, 0x9f,
      0xff, 0xc6, 0xc6, 0xc6, 0xff, 0x09, 0x00, 0x62, 0x00, 0x9f, 0xff, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x00,
  };

  z_stream stream;
  stream.zalloc = Z_NULL;
  stream.zfree = Z_NULL;

  // Compress the data one byte at a time to exercise the streaming code.
  int ret =
      deflateInit2(&stream, level, Z_DEFLATED, windowBits, memLevel, strategy);
  ASSERT_EQ(ret, Z_OK);
  std::vector<uint8_t> compressed(src.size() * 2 + 1000);
  stream.next_out = compressed.data();
  stream.avail_out = compressed.size();
  for (uint8_t b : src) {
    stream.next_in = &b;
    stream.avail_in = 1;
    ret = deflate(&stream, Z_NO_FLUSH);
    ASSERT_EQ(ret, Z_OK);
  }
  stream.next_in = Z_NULL;
  stream.avail_in = 0;
  ret = deflate(&stream, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);
  deflateEnd(&stream);
}

static const char zFixedCorruptionData[] =
    "AAABAACAADAAEAAFAAGAAHAAIAAJAAKAALAAMAANAAOAAPAAQAARAASAATAAUAAVAAWAAXAAYA"
    "AZABBABCABDABEABFABGABHABIABJABKABLABMABNABOABPABQABRABSABTABUABVABWABXABY"
    "ABZACBACCACDACEACFACGACHACIACJACKACLACMACNACOACPACQACRACSACTACUACVACWACXAC"
    "YACZADBADCADDADEADFADGADHADIADJADKADLADMADNADOADPADQADRADSADTADUADVADWADXA"
    "DYADZAEBAECAEDAEEAEFAEGAEHAEIAEJAEKAELAEMAENAEOAEPAEQAERAESAETAEUAEVAEWAEX"
    "AEYAEZAFBAFCAFDAFEAFFAFGAFHAFIAFJAFKAFLAFMAFNAFOAFPAFQAFRAFSAFTAFUAFVAFWAF"
    "XAFYAFZAGBAGCAGDAGEAGFAGGAGHAGIAGJAGKAGLAGMAGNAGOAGPAGQAGRAGSAGTAGUAGVAGWA"
    "GXAGYAGZAHBAHCAHDAHEAHFAHGAHHAHIAHJAHKAHLAHMAHNAHOAHPAHQAHRAHSAHTAHUAHVAHW"
    "AHXAHYAHZAIBAICAIDAIEAIFAIGAIHAIIAIJAIKAILAIMAINAIOAIPAIQAIRAISAITAIUAIVAI"
    "WAIXAIYAIZAJBAJCAJDAJEAJFAJGAJHAJIAJJAJKAJLAJMAJNAJOAJPAJQAJRAJSAJTAJUAJVA"
    "JWAJXAJYAJZAKBAKCAKDAKEAKFAKGAKHAKIAKJAKKAKLAKMAKNAKOAKPAKQAKRAKSAKTAKUAKV"
    "AKWAKXAKYAKZALBALCALDALEALFALGALHALIALJALKALLALMALNALOALPALQALRALSALTALUAL"
    "VALWALXALYALZAMBAMCAMDAMEAMFAMGAMHAMIAMJAMKAMLAMMAMNAMOAMPAMQAMRAMSAMTAMUA"
    "MVAMWAMXAMYAMZANBANCANDANEANFANGANHANIANJANKANLANMANNANOANPANQANRANSANTANU"
    "ANVANWANXANYANZAOBAOCAODAOEAOFAOGAOHAOIAOJAOKAOLAOMAONAOOAOPAOQAORAOSAOTAO"
    "UAOVAOWAOXAOYAOZAPBAPCAPDAPEAPFAPGAPHAPIAPJAPKAPLAPMAPNAPOAPPAPQAPRAPSAPTA"
    "PUAPVAPWAPXAPYAPZAQBAQCAQDAQEAQFAQGAQHAQIAQJAQKAQLAQMAQNAQOAQPAQQAQRAQSAQT"
    "AQUAQVAQWAQXAQYAQZARBARCARDAREARFARGARHARIARJARKARLARMARNAROARPARQARRARSAR"
    "TARUARVARWARXARYARZASBASCASDASEASFASGASHASIASJASKASLASMASNASOASPASQASRASSA"
    "STASUASVASWASXASYASZATBATCATDATEATFATGATHATIATJATKATLATMATNATOATPATQATRATS"
    "ATTATUATVATWATXATYATZAUBAUCAUDAUEAUFAUGAUHAUIAUJAUKAULAUMAUNAUOAUPAUQAURAU"
    "SAUTAUUAUVAUWAUXAUYAUZAVBAVCAVDAVEAVFAVGAVHAVIAVJAVKAVLAVMAVNAVOAVPAVQAVRA"
    "VSAVTAVUAVVAVWAVXAVYAVZAWBAWCAWDAWEAWFAWGAWHAWIAWJAWKAWLAWMAWNAWOAWPAWQAWR"
    "AWSAWTAWUAWVAWWAWXAWYAWZAXBAXCAXDAXEAXFAXGAXHAXIAXJAXKAXLAXMAXNAXOAXPAXQAX"
    "RAXSAXTAXUAXVAXWAXXAXYAXZAYBAYCAYDAYEAYFAYGAYHAYIAYJAYKAYLAYMAYNAYOAYPAYQA"
    "YRAYSAYTAYUAYVAYWAYXAYYAYZAZBAZCAZDAZEAZFAZGAZHAZIAZJAZKAZLAZMAZNAZOAZPAZQ"
    "AZRAZSAZTAZUAZVAZWAZXAZYAZZBBBCBBDBBEBBFBBGBBHBBIBBJBBKBBLBBMBBNBBOBBPBBQB"
    "BRBBSBBTBBUBBVBBWBBXBBYBBZBCCBCDBCEBCFBCGBCHBCIBCJBCKBCLBCMBCNBCOBCPBCQBCR"
    "BCSBCTBCUBCVBCWBCXBCYBCZBDCBDDBDEBDFBDGBDHBDIBDJBDKBDLBDMBDNBDOBDPBDQBDRBD"
    "SBDTBDUBDVBDWBDXBDYBDZBECBEDBEEBEFBEGBEHBEIBEJBEKBELBEMBENBEOBEPBEQBERBESB"
    "ETBEUBEVBEWBEXBEYBEZBFCBFDBFEBFFBFGBFHBFIBFJBFKBFLBFMBFNBFOBFPBFQBFRBFSBFT"
    "BFUBFVBFWBFXBFYBFZBGCBGDBGEBGFBGGBGHBGIBGJBGKBGLBGMBGNBGOBGPBGQBGRBGSBGTBG"
    "UBGVBGWBGXBGYBGZBHCBHDBHEBHFBHGBHHBHIBHJBHKBHLBHMBHNBHOBHPBHQBHRBHSBHTBHUB"
    "HVBHWBHXBHYBHZBICBIDBIEBIFBIGBIHBIIBIJBIKBILBIMBINBIOBIPBIQBIRBISBITBIUBIV"
    "BIWBIXBIYBIZBJCBJDBJEBJFBJGBJHBJIBJJBJKBJLBJMBJNBJOBJPBJQBJRBJSBJTBJUBJVBJ"
    "WBJXBJYBJZBKCBKDBKEBKFBKGBKHBKIBKJBKKBKLBKMBKNBKOBKPBKQBKRBKSBKTBKUBKVBKWB"
    "KXBKYBKZBLCBLDBLEBLFBLGBLHBLIBLJBLKBLLBLMBLNBLOBLPBLQBLRBLSBLTBLUBLVBLWBLX"
    "BLYBLZBMCBMDBMEBMFBMGBMHBMIBMJBMKBMLBMMBMNBMOBMPBMQBMRBMSBMTBMUBMVBMWBMXBM"
    "YBMZBNCBNDBNEBNFBNGBNHBNIBNJBNKBNLBNMBNNBNOBNPBNQBNRBNSBNTBNUBNVBNWBNXBNYB"
    "NZBOCBODBOEBOFBOGBOHBOIBOJBOKBOLBOMBONBOOBOPBOQBORBOSBOTBOUBOVBOWBOXBOYBOZ"
    "BPCBPDBPEBPFBPGBPHBPIBPJBPKBPLBPMBPNBPOBPPBPQBPRBPSBPTBPUBPVBPWBPXBPYBPZBQ"
    "CBQDBQEBQFBQGBQHBQIBQJBQKBQLBQMBQNBQOBQPBQQBQRBQSBQTBQUBQVBQWBQXBQYBQZBRCB"
    "RDBREBRFBRGBRHBRIBRJBRKBRLBRMBRNBROBRPBRQBRRBRSBRTBRUBRVBRWBRXBRYBRZBSCBSD"
    "BSEBSFBSGBSHBSIBSJBSKBSLBSMBSNBSOBSPBSQBSRBSSBSTBSUBSVBSWBSXBSYBSZBTCBTDBT"
    "EBTFBTGBTHBTIBTJBTKBTLBTMBTNBTOBTPBTQBTRBTSBTTBTUBTVBTWBTXBTYBTZBUCBUDBUEB"
    "UFBUGBUHBUIBUJBUKBULBUMBUNBUOBUPBUQBURBUSBUTBUUBUVBUWBUXBUYBUZBVCBVDBVEBVF"
    "BVGBVHBVIBVJBVKBVLBVMBVNBVOBVPBVQBVRBVSBVTBVUBVVBVWBVXBVYBVZBWCBWDBWEBWFBW"
    "GBWHBWIBWJBWKBWLBWMBWNBWOBWPBWQBWRBWSBWTBWUBWVBWWBWXBWYBWZBXCBXDBXEBXFBXGB"
    "XHBXIBXJBXKBXLBXMBXNBXOBXPBXQBXRBXSBXTBXUBXVBXWBXXBXYBXZBYCBYDBYEBYFBYGBYH"
    "BYIBYJBYKBYLBYMBYNBYOBYPBYQBYRBYSBYTBYUBYVBYWBYXBYYBYZBZCBZDBZEBZFBZGBZHBZ"
    "IBZJBZKBZLBZMBZNBZOBZPBZQBZRBZSBZTBZUBZVBZWBZXBZYBZZCCCDCCECCFCCGCCHCCICCJ"
    "CCKCCLCCMCCNCCOCCPCCQCCRCCSCCTCCUCCVCCWCCXCCYCCZCDDCDECDFCDGCDHCDICDJCDKCD"
    "LCDMCDNCDOCDPCDQCDRCDSCDTCDUCDVCDWCDXCDYCDZCEDCEECEFCEGCEHCEICEJCEKCELCEMC"
    "ENCEOCEPCEQCERCESCETCEUCEVCEWCEXCEYCEZCFDCFECFFCFGCFHCFICFJCFKCFLCFMCFNCFO"
    "CFPCFQCFRCFSCFTCFUCFVCFWCFXCFYCFZCGDCGECGFCGGCGHCGICGJCGKCGLCGMCGNCGOCGPCG"
    "QCGRCGSCGTCGUCGVCGWCGXCGYCGZCHDCHECHFCHGCHHCHICHJCHKCHLCHMCHNCHOCHPCHQCHRC"
    "HSCHTCHUCHVCHWCHXCHYCHZCIDCIECIFCIGCIHCIICIJCIKCILCIMCINCIOCIPCIQCIRCISCIT"
    "CIUCIVCIWCIXCIYCIZCJDCJECJFCJGCJHCJICJJCJKCJLCJMCJNCJOCJPCJQCJRCJSCJTCJUCJ"
    "VCJWCJXCJYCJZCKDCKECKFCKGCKHCKICKJCKKCKLCKMCKNCKOCKPCKQCKRCKSCKTCKUCKVCKWC"
    "KXCKYCKZCLDCLECLFCLGCLHCLICLJCLKCLLCLMCLNCLOCLPCLQCLRCLSCLTCLUCLVCLWCLXCLY"
    "CLZCMDCMECMFCMGCMHCMICMJCMKCMLCMMCMNCMOCMPCMQCMRCMSCMTCMUCMVCMWCMXCMYCMZCN"
    "DCNECNFCNGCNHCNICNJCNKCNLCNMCNNCNOCNPCNQCNRCNSCNTCNUCNVCNWCNXCNYCNZCODCOEC"
    "OFCOGCOHCOICOJCOKCOLCOMCONCOOCOPCOQCORCOSCOTCOUCOVCOWCOXCOYCOZCPDCPECPFCPG"
    "CPHCPICPJCPKCPLCPMCPNCPOCPPCPQCPRCPSCPTCPUCPVCPWCPXCPYCPZCQDCQECQFCQGCQHCQ"
    "ICQJCQKCQLCQMCQNCQOCQPCQQCQRCQSCQTCQUCQVCQWCQXCQYCQZCRDCRECRFCRGCRHCRICRJC"
    "RKCRLCRMCRNCROCRPCRQCRRCRSCRTCRUCRVCRWCRXCRYCRZCSDCSECSFCSGCSHCSICSJCSKCSL"
    "CSMCSNCSOCSPCSQCSRCSSCSTCSUCSVCSWCSXCSYCSZCTDCTECTFCTGCTHCTICTJCTKCTLCTMCT"
    "NCTOCTPCTQCTRCTSCTTCTUCTVCTWCTXCTYCTZCUDCUECUFCUGCUHCUICUJCUKCULCUMCUNCUOC"
    "UPCUQCURCUSCUTCUUCUVCUWCUXCUYCUZCVDCVECVFCVGCVHCVICVJCVKCVLCVMCVNCVOCVPCVQ"
    "CVRCVSCVTCVUCVVCVWCVXCVYCVZCWDCWECWFCWGCWHCWICWJCWKCWLCWMCWNCWOCWPCWQCWRCW"
    "SCWTCWUCWVCWWCWXCWYCWZCXDCXECXFCXGCXHCXICXJCXKCXLCXMCXNCXOCXPCXQCXRCXSCXTC"
    "XUCXVCXWCXXCXYCXZCYDCYECYFCYGCYHCYICYJCYKCYLCYMCYNCYOCYPCYQCYRCYSCYTCYUCYV"
    "CYWCYXCYYCYZCZDCZECZFCZGCZHCZICZJCZKCZLCZMCZNCZOCZPCZQCZRCZSCZTCZUCZVCZWCZ"
    "XCZYCZZDDDEDDFDDGDDHDDIDDJDDKDDLDDMDDNDDODDPDDQDDRDDSDDTDDUDDVDDWDDXDDYDDZ"
    "DEEDEFDEGDEHDEIDEJDEKDELDEMDENDEODEPDEQDERDESDETDEUDEVDEWDEXDEYDEZDFEDFFDF"
    "GDFHDFIDFJDFKDFLDFMDFNDFODFPDFQDFRDFSDFTDFUDFVDFWDFXDFYDFZDGEDGFDGGDGHDGID"
    "GJDGKDGLDGMDGNDGODGPDGQDGRDGSDGTDGUDGVDGWDGXDGYDGZDHEDHFDHGDHHDHIDHJDHKDHL"
    "DHMDHNDHODHPDHQDHRDHSDHTDHUDHVDHWDHXDHYDHZDIEDIFDIGDIHDIIDIJDIKDILDIMDINDI"
    "ODIPDIQDIRDISDITDIUDIVDIWDIXDIYDIZDJEDJFDJGDJHDJIDJJDJKDJLDJMDJNDJODJPDJQD"
    "JRDJSDJTDJUDJVDJWDJXDJYDJZDKEDKFDKGDKHDKIDKJDKKDKLDKMDKNDKODKPDKQDKRDKSDKT"
    "DKUDKVDKWDKXDKYDKZDLEDLFDLGDLHDLIDLJDLKDLLDLMDLNDLODLPDLQDLRDLSDLTDLUDLVDL"
    "WDLXDLYDLZDMEDMFDMGDMHDMIDMJDMKDMLDMMDMNDMODMPDMQDMRDMSDMTDMUDMVDMWDMXDMYD"
    "MZDNEDNFDNGDNHDNIDNJDNKDNLDNMDNNDNODNPDNQDNRDNSDNTDNUDNVDNWDNXDNYDNZDOEDOF"
    "DOGDOHDOIDOJDOKDOLDOMDONDOODOPDOQDORDOSDOTDOUDOVDOWDOXDOYDOZDPEDPFDPGDPHDP"
    "IDPJDPKDPLDPMDPNDPODPPDPQDPRDPSDPTDPUDPVDPWDPXDPYDPZDQEDQFDQGDQHDQIDQJDQKD"
    "QLDQMDQNDQODQPDQQDQRDQSDQTDQUDQVDQWDQXDQYDQZDREDRFDRGDRHDRIDRJDRKDRLDRMDRN"
    "DRODRPDRQDRRDRSDRTDRUDRVDRWDRXDRYDRZDSEDSFDSGDSHDSIDSJDSKDSLDSMDSNDSODSPDS"
    "QDSRDSSDSTDSUDSVDSWDSXDSYDSZDTEDTFDTGDTHDTIDTJDTKDTLDTMDTNDTODTPDTQDTRDTSD"
    "TTDTUDTVDTWDTXDTYDTZDUEDUFDUGDUHDUIDUJDUKDULDUMDUNDUODUPDUQDURDUSDUTDUUDUV"
    "DUWDUXDUYDUZDVEDVFDVGDVHDVIDVJDVKDVLDVMDVNDVODVPDVQDVRDVSDVTDVUDVVDVWDVXDV"
    "YDVZDWEDWFDWGDWHDWIDWJDWKDWLDWMDWNDWODWPDWQDWRDWSDWTDWUDWVDWWDWXDWYDWZDXED"
    "XFDXGDXHDXIDXJDXKDXLDXMDXNDXODXPDXQDXRDXSDXTDXUDXVDXWDXXDXYDXZDYEDYFDYGDYH"
    "DYIDYJDYKDYLDYMDYNDYODYPDYQDYRDYSDYTDYUDYVDYWDYXDYYDYZDZEDZFDZGDZHDZIDZJDZ"
    "KDZLDZMDZNDZODZPDZQDZRDZSDZTDZUDZVDZWDZXDZYDZZEEEFEEGEEHEEIEEJEEKEELEEMEEN"
    "EEOEEPEEQEEREESEETEEUEEVEEWEEXEEYEEZEFFEFGEFHEFIEFJEFKEFLEFMEFNEFOEFPEFQEF"
    "REFSEFTEFUEFVEFWEFXEFYEFZEGFEGGEGHEGIEGJEGKEGLEGMEGNEGOEGPEGQEGREGSEGTEGUE"
    "GVEGWEGXEGYEGZEHFEHGEHHEHIEHJEHKEHLEHMEHNEHOEHPEHQEHREHSEHTEHUEHVEHWEHXEHY"
    "EHZEIFEIGEIHEIIEIJEIKEILEIMEINEIOEIPEIQEIREISEITEIUEIVEIWEIXEIYEIZEJFEJGEJ"
    "HEJIEJJEJKEJLEJMEJNEJOEJPEJQEJREJSEJTEJUEJVEJWEJXEJYEJZEKFEKGEKHEKIEKJEKKE"
    "KLEKMEKNEKOEKPEKQEKREKSEKTEKUEKVEKWEKXEKYEKZELFELGELHELIELJELKELLELMELNELO"
    "ELPELQELRELSELTELUELVELWELXELYELZEMFEMGEMHEMIEMJEMKEMLEMMEMNEMOEMPEMQEMREM"
    "SEMTEMUEMVEMWEMXEMYEMZENFENGENHENIENJENKENLENMENNENOENPENQENRENSENTENUENVE"
    "NWENXENYENZEOFEOGEOHEOIEOJEOKEOLEOMEONEOOEOPEOQEOREOSEOTEOUEOVEOWEOXEOYEOZ"
    "EPFEPGEPHEPIEPJEPKEPLEPMEPNEPOEPPEPQEPREPSEPTEPUEPVEPWEPXEPYEPZEQFEQGEQHEQ"
    "IEQJEQKEQLEQMEQNEQOEQPEQQEQREQSEQTEQUEQVEQWEQXEQYEQZERFERGERHERIERJERKERLE"
    "RMERNEROERPERQERRERSERTERUERVERWERXERYERZESFESGESHESIESJESKESLESMESNESOESP"
    "ESQESRESSESTESUESVESWESXESYESZETFETGETHETIETJETKETLETMETNETOETPETQETRETSET"
    "TETUETVETWETXETYETZEUFEUGEUHEUIEUJEUKEULEUMEUNEUOEUPEUQEUREUSEUTEUUEUVEUWE"
    "UXEUYEUZEVFEVGEVHEVIEVJEVKEVLEVMEVNEVOEVPEVQEVREVSEVTEVUEVVEVWEVXEVYEVZEWF"
    "EWGEWHEWIEWJEWKEWLEWMEWNEWOEWPEWQEWREWSEWTEWUEWVEWWEWXEWYEWZEXFEXGEXHEXIEX"
    "JEXKEXLEXMEXNEXOEXPEXQEXREXSEXTEXUEXVEXWEXXEXYEXZEYFEYGEYHEYIEYJEYKEYLEYME"
    "YNEYOEYPEYQEYREYSEYTEYUEYVEYWEYXEYYEYZEZFEZGEZHEZIEZJEZKEZLEZMEZNEZOEZPEZQ"
    "EZREZSEZTEZUEZVEZWEZXEZYEZZFFFGFFHFFIFFJFFKFFLFFMFFNFFOFFPFFQFFRFFSFFTFFUF"
    "FVFFWFFXFFYFFZFGGFGHFGIFGJFGKFGLFGMFGNFGOFGPFGQFGRFGSFGTFGUFGVFGWFGXFGYFGZ"
    "FHGFHHFHIFHJFHKFHLFHMFHNFHOFHPFHQFHRFHSFHTFHUFHVFHWFHXFHYFHZFIGFIHFIIFIJFI"
    "KFILFIMFINFIOFIPFIQFIRFISFITFIUFIVFIWFIXFIYFIZFJGFJHFJIFJJFJKFJLFJMFJNFJOF"
    "JPFJQFJRFJSFJTFJUFJVFJWFJXFJYFJZFKGFKHFKIFKJFKKFKLFKMFKNFKOFKPFKQFKRFKSFKT"
    "FKUFKVFKWFKXFKYFKZFLGFLHFLIFLJFLKFLLFLMFLNFLOFLPFLQFLRFLSFLTFLUFLVFLWFLXFL"
    "YFLZFMGFMHFMIFMJFMKFMLFMMFMNFMOFMPFMQFMRFMSFMTFMUFMVFMWFMXFMYFMZFNGFNHFNIF"
    "NJFNKFNLFNMFNNFNOFNPFNQFNRFNSFNTFNUFNVFNWFNXFNYFNZFOGFOHFOIFOJFOKFOLFOMFON"
    "FOOFOPFOQFORFOSFOTFOUFOVFOWFOXFOYFOZFPGFPHFPIFPJFPKFPLFPMFPNFPOFPPFPQFPRFP"
    "SFPTFPUFPVFPWFPXFPYFPZFQGFQHFQIFQJFQKFQLFQMFQNFQOFQPFQQFQRFQSFQTFQUFQVFQWF"
    "QXFQYFQZFRGFRHFRIFRJFRKFRLFRMFRNFROFRPFRQFRRFRSFRTFRUFRVFRWFRXFRYFRZFSGFSH"
    "FSIFSJFSKFSLFSMFSNFSOFSPFSQFSRFSSFSTFSUFSVFSWFSXFSYFSZFTGFTHFTIFTJFTKFTLFT"
    "MFTNFTOFTPFTQFTRFTSFTTFTUFTVFTWFTXFTYFTZFUGFUHFUIFUJFUKFULFUMFUNFUOFUPFUQF"
    "URFUSFUTFUUFUVFUWFUXFUYFUZFVGFVHFVIFVJFVKFVLFVMFVNFVOFVPFVQFVRFVSFVTFVUFVV"
    "FVWFVXFVYFVZFWGFWHFWIFWJFWKFWLFWMFWNFWOFWPFWQFWRFWSFWTFWUFWVFWWFWXFWYFWZFX"
    "GFXHFXIFXJFXKFXLFXMFXNFXOFXPFXQFXRFXSFXTFXUFXVFXWFXXFXYFXZFYGFYHFYIFYJFYKF"
    "YLFYMFYNFYOFYPFYQFYRFYSFYTFYUFYVFYWFYXFYYFYZFZGFZHFZIFZJFZKFZLFZMFZNFZOFZP"
    "FZQFZRFZSFZTFZUFZVFZWFZXFZYFZZGGGHGGIGGJGGKGGLGGMGGNGGOGGPGGQGGRGGSGGTGGUG"
    "GVGGWGGXGGYGGZGHHGHIGHJGHKGHLGHMGHNGHOGHPGHQGHRGHSGHTGHUGHVGHWGHXGHYGHZGIH"
    "GIIGIJGIKGILGIMGINGIOGIPGIQGIRGISGITGIUGIVGIWGIXGIYGIZGJHGJIGJJGJKGJLGJMGJ"
    "NGJOGJPGJQGJRGJSGJTGJUGJVGJWGJXGJYGJZGKHGKIGKJGKKGKLGKMGKNGKOGKPGKQGKRGKSG"
    "KTGKUGKVGKWGKXGKYGKZGLHGLIGLJGLKGLLGLMGLNGLOGLPGLQGLRGLSGLTGLUGLVGLWGLXGLY"
    "GLZGMHGMIGMJGMKGMLGMMGMNGMOGMPGMQGMRGMSGMTGMUGMVGMWGMXGMYGMZGNHGNIGNJGNKGN"
    "LGNMGNNGNOGNPGNQGNRGNSGNTGNUGNVGNWGNXGNYGNZGOHGOIGOJGOKGOLGOMGONGOOGOPGOQG"
    "ORGOSGOTGOUGOVGOWGOXGOYGOZGPHGPIGPJGPKGPLGPMGPNGPOGPPGPQGPRGPSGPTGPUGPVGPW"
    "GPXGPYGPZGQHGQIGQJGQKGQLGQMGQNGQOGQPGQQGQRGQSGQTGQUGQVGQWGQXGQYGQZGRHGRIGR"
    "JGRKGRLGRMGRNGROGRPGRQGRRGRSGRTGRUGRVGRWGRXGRYGRZGSHGSIGSJGSKGSLGSMGSNGSOG"
    "SPGSQGSRGSSGSTGSUGSVGSWGSXGSYGSZGTHGTIGTJGTKGTLGTMGTNGTOGTPGTQGTRGTSGTTGTU"
    "GTVGTWGTXGTYGTZGUHGUIGUJGUKGULGUMGUNGUOGUPGUQGURGUSGUTGUUGUVGUWGUXGUYGUZGV"
    "HGVIGVJGVKGVLGVMGVNGVOGVPGVQGVRGVSGVTGVUGVVGVWGVXGVYGVZGWHGWIGWJGWKGWLGWMG"
    "WNGWOGWPGWQGWRGWSGWTGWUGWVGWWGWXGWYGWZGXHGXIGXJGXKGXLGXMGXNGXOGXPGXQGXRGXS"
    "GXTGXUGXVGXWGXXGXYGXZGYHGYIGYJGYKGYLGYMGYNGYOGYPGYQGYRGYSGYTGYUGYVGYWGYXGY"
    "YGYZGZHGZIGZJGZKGZLGZMGZNGZOGZPGZQGZRGZSGZTGZUGZVGZWGZXGZYGZZHHHIHHJHHKHHL"
    "HHMHHNHHOHHPHHQHHRHHSHHTHHUHHVHHWHHXHHYHHZHIIHIJHIKHILHIMHINHIOHIPHIQHIRHI"
    "SHITHIUHIVHIWHIXHIYHIZHJIHJJHJKHJLHJMHJNHJOHJPHJQHJRHJSHJTHJUHJVHJWHJXHJYH"
    "JZHKIHKJHKKHKLHKMHKNHKOHKPHKQHKRHKSHKTHKUHKVHKWHKXHKYHKZHLIHLJHLKHLLHLMHLN"
    "HLOHLPHLQHLRHLSHLTHLUHLVHLWHLXHLYHLZHMIHMJHMKHMLHMMHMNHMOHMPHMQHMRHMSHMTHM"
    "UHMVHMWHMXHMYHMZHNIHNJHNKHNLHNMHNNHNOHNPHNQHNRHNSHNTHNUHNVHNWHNXHNYHNZHOIH"
    "OJHOKHOLHOMHONHOOHOPHOQHORHOSHOTHOUHOVHOWHOXHOYHOZHPIHPJHPKHPLHPMHPNHPOHPP"
    "HPQHPRHPSHPTHPUHPVHPWHPXHPYHPZHQIHQJHQKHQLHQMHQNHQOHQPHQQHQRHQSHQTHQUHQVHQ"
    "WHQXHQYHQZHRIHRJHRKHRLHRMHRNHROHRPHRQHRRHRSHRTHRUHRVHRWHRXHRYHRZHSIHSJHSKH"
    "SLHSMHSNHSOHSPHSQHSRHSSHSTHSUHSVHSWHSXHSYHSZHTIHTJHTKHTLHTMHTNHTOHTPHTQHTR"
    "HTSHTTHTUHTVHTWHTXHTYHTZHUIHUJHUKHULHUMHUNHUOHUPHUQHURHUSHUTHUUHUVHUWHUXHU"
    "YHUZHVIHVJHVKHVLHVMHVNHVOHVPHVQHVRHVSHVTHVUHVVHVWHVXHVYHVZHWIHWJHWKHWLHWMH"
    "WNHWOHWPHWQHWRHWSHWTHWUHWVHWWHWXHWYHWZHXIHXJHXKHXLHXMHXNHXOHXPHXQHXRHXSHXT"
    "HXUHXVHXWHXXHXYHXZHYIHYJHYKHYLHYMHYNHYOHYPHYQHYRHYSHYTHYUHYVHYWHYXHYYHYZHZ"
    "IHZJHZKHZLHZMHZNHZOHZPHZQHZRHZSHZTHZUHZVHZWHZXHZYHZZIIIJIIKIILIIMIINIIOIIP"
    "IIQIIRIISIITIIUIIVIIWIIXIIYIIZIJJIJKIJLIJMIJNIJOIJPIJQIJRIJSIJTIJUIJVIJWIJ"
    "XIJYIJZIKJIKKIKLIKMIKNIKOIKPIKQIKRIKSIKTIKUIKVIKWIKXIKYIKZILJILKILLILMILNI"
    "LOILPILQILRILSILTILUILVILWILXILYILZIMJIMKIMLIMMIMNIMOIMPIMQIMRIMSIMTIMUIMV"
    "IMWIMXIMYIMZINJINKINLINMINNINOINPINQINRINSINTINUINVINWINXINYINZIOJIOKIOLIO"
    "MIONIOOIOPIOQIORIOSIOTIOUIOVIOWIOXIOYIOZIPJIPKIPLIPMIPNIPOIPPIPQIPRIPSIPTI"
    "PUIPVIPWIPXIPYIPZIQJIQKIQLIQMIQNIQOIQPIQQIQRIQSIQTIQUIQVIQWIQXIQYIQZIRJIRK"
    "IRLIRMIRNIROIRPIRQIRRIRSIRTIRUIRVIRWIRXIRYIRZISJISKISLISMISNISOISPISQISRIS"
    "SISTISUISVISWISXISYISZITJITKITLITMITNITOITPITQITRITSITTITUITVITWITXITYITZI"
    "UJIUKIULIUMIUNIUOIUPIUQIURIUSIUTIUUIUVIUWIUXIUYIUZIVJIVKIVLIVMIVNIVOIVPIVQ"
    "IVRIVSIVTIVUIVVIVWIVXIVYIVZIWJIWKIWLIWMIWNIWOIWPIWQIWRIWSIWTIWUIWVIWWIWXIW"
    "YIWZIXJIXKIXLIXMIXNIXOIXPIXQIXRIXSIXTIXUIXVIXWIXXIXYIXZIYJIYKIYLIYMIYNIYOI"
    "YPIYQIYRIYSIYTIYUIYVIYWIYXIYYIYZIZJIZKIZLIZMIZNIZOIZPIZQIZRIZSIZTIZUIZVIZW"
    "IZXIZYIZZJJJKJJLJJMJJNJJOJJPJJQJJRJJSJJTJJUJJVJJWJJXJJYJJZJKKJKLJKMJKNJKOJ"
    "KPJKQJKRJKSJKTJKUJKVJKWJKXJKYJKZJLKJLLJLMJLNJLOJLPJLQJLRJLSJLTJLUJLVJLWJLX"
    "JLYJLZJMKJMLJMMJMNJMOJMPJMQJMRJMSJMTJMUJMVJMWJMXJMYJMZJNKJNLJNMJNNJNOJNPJN"
    "QJNRJNSJNTJNUJNVJNWJNXJNYJNZJOKJOLJOMJONJOOJOPJOQJORJOSJOTJOUJOVJOWJOXJOYJ"
    "OZJPKJPLJPMJPNJPOJPPJPQJPRJPSJPTJPUJPVJPWJPXJPYJPZJQKJQLJQMJQNJQOJQPJQQJQR"
    "JQSJQTJQUJQVJQWJQXJQYJQZJRKJRLJRMJRNJROJRPJRQJRRJRSJRTJRUJRVJRWJRXJRYJRZJS"
    "KJSLJSMJSNJSOJSPJSQJSRJSSJSTJSUJSVJSWJSXJSYJSZJTKJTLJTMJTNJTOJTPJTQJTRJTSJ"
    "TTJTUJTVJTWJTXJTYJTZJUKJULJUMJUNJUOJUPJUQJURJUSJUTJUUJUVJUWJUXJUYJUZJVKJVL"
    "JVMJVNJVOJVPJVQJVRJVSJVTJVUJVVJVWJVXJVYJVZJWKJWLJWMJWNJWOJWPJWQJWRJWSJWTJW"
    "UJWVJWWJWXJWYJWZJXKJXLJXMJXNJXOJXPJXQJXRJXSJXTJXUJXVJXWJXXJXYJXZJYKJYLJYMJ"
    "YNJYOJYPJYQJYRJYSJYTJYUJYVJYWJYXJYYJYZJZKJZLJZMJZNJZOJZPJZQJZRJZSJZTJZUJZV"
    "JZWJZXJZYJZZKKKLKKMKKNKKOKKPKKQKKRKKSKKTKKUKKVKKWKKXKKYKKZKLLKLMKLNKLOKLPK"
    "LQKLRKLSKLTKLUKLVKLWKLXKLYKLZKMLKMMKMNKMOKMPKMQKMRKMSKMTKMUKMVKMWKMXKMYKMZ"
    "KNLKNMKNNKNOKNPKNQKNRKNSKNTKNUKNVKNWKNXKNYKNZKOLKOMKONKOOKOPKOQKORKOSKOTKO"
    "UKOVKOWKOXKOYKOZKPLKPMKPNKPOKPPKPQKPRKPSKPTKPUKPVKPWKPXKPYKPZKQLKQMKQNKQOK"
    "QPKQQKQRKQSKQTKQUKQVKQWKQXKQYKQZKRLKRMKRNKROKRPKRQKRRKRSKRTKRUKRVKRWKRXKRY"
    "KRZKSLKSMKSNKSOKSPKSQKSRKSSKSTKSUKSVKSWKSXKSYKSZKTLKTMKTNKTOKTPKTQKTRKTSKT"
    "TKTUKTVKTWKTXKTYKTZKULKUMKUNKUOKUPKUQKURKUSKUTKUUKUVKUWKUXKUYKUZKVLKVMKVNK"
    "VOKVPKVQKVRKVSKVTKVUKVVKVWKVXKVYKVZKWLKWMKWNKWOKWPKWQKWRKWSKWTKWUKWVKWWKWX"
    "KWYKWZKXLKXMKXNKXOKXPKXQKXRKXSKXTKXUKXVKXWKXXKXYKXZKYLKYMKYNKYOKYPKYQKYRKY"
    "SKYTKYUKYVKYWKYXKYYKYZKZLKZMKZNKZOKZPKZQKZRKZSKZTKZUKZVKZWKZXKZYKZZLLLMLLN"
    "LLOLLPLLQLLRLLSLLTLLULLVLLWLLXLLYLLZLMMLMNLMOLMPLMQLMRLMSLMTLMULMVLMWLMXLM"
    "YLMZLNMLNNLNOLNPLNQLNRLNSLNTLNULNVLNWLNXLNYLNZLOMLONLOOLOPLOQLORLOSLOTLOUL"
    "OVLOWLOXLOYLOZLPMLPNLPOLPPLPQLPRLPSLPTLPULPVLPWLPXLPYLPZLQMLQNLQOLQPLQQLQR"
    "LQSLQTLQULQVLQWLQXLQYLQZLRMLRNLROLRPLRQLRRLRSLRTLRULRVLRWLRXLRYLRZLSMLSNLS"
    "OLSPLSQLSRLSSLSTLSULSVLSWLSXLSYLSZLTMLTNLTOLTPLTQLTRLTSLTTLTULTVLTWLTXLTYL"
    "TZLUMLUNLUOLUPLUQLURLUSLUTLUULUVLUWLUXLUYLUZLVMLVNLVOLVPLVQLVRLVSLVTLVULVV"
    "LVWLVXLVYLVZLWMLWNLWOLWPLWQLWRLWSLWTLWULWVLWWLWXLWYLWZLXMLXNLXOLXPLXQLXRLX"
    "SLXTLXULXVLXWLXXLXYLXZLYMLYNLYOLYPLYQLYRLYSLYTLYULYVLYWLYXLYYLYZLZMLZNLZOL"
    "ZPLZQLZRLZSLZTLZULZVLZWLZXLZYLZZMMMNMMOMMPMMQMMRMMSMMTMMUMMVMMWMMXMMYMMZMN"
    "NMNOMNPMNQMNRMNSMNTMNUMNVMNWMNXMNYMNZMONMOOMOPMOQMORMOSMOTMOUMOVMOWMOXMOYM"
    "OZMPNMPOMPPMPQMPRMPSMPTMPUMPVMPWMPXMPYMPZMQNMQOMQPMQQMQRMQSMQTMQUMQVMQWMQX"
    "MQYMQZMRNMROMRPMRQMRRMRSMRTMRUMRVMRWMRXMRYMRZMSNMSOMSPMSQMSRMSSMSTMSUMSVMS"
    "WMSXMSYMSZMTNMTOMTPMTQMTRMTSMTTMTUMTVMTWMTXMTYMTZMUNMUOMUPMUQMURMUSMUTMUUM"
    "UVMUWMUXMUYMUZMVNMVOMVPMVQMVRMVSMVTMVUMVVMVWMVXMVYMVZMWNMWOMWPMWQMWRMWSMWT"
    "MWUMWVMWWMWXMWYMWZMXNMXOMXPMXQMXRMXSMXTMXUMXVMXWMXXMXYMXZMYNMYOMYPMYQMYRMY"
    "SMYTMYUMYVMYWMYXMYYMYZMZNMZOMZPMZQMZRMZSMZTMZUMZVMZWMZXMZYMZZNNNONNPNNQNNR"
    "NNSNNTNNUNNVNNWNNXNNYNNZNOONOPNOQNORNOSNOTNOUNOVNOWNOXNOYNOZNPONPPNPQNPRNP"
    "SNPTNPUNPVNPWNPXNPYNPZNQONQPNQQNQRNQSNQTNQUNQVNQWNQXNQYNQZNRONRPNRQNRRNRSN"
    "RTNRUNRVNRWNRXNRYNRZNSONSPNSQNSRNSSNSTNSUNSVNSWNSXNSYNSZNTONTPNTQNTRNTSNTT"
    "NTUNTVNTWNTXNTYNTZNUONUPNUQNURNUSNUTNUUNUVNUWNUXNUYNUZNVONVPNVQNVRNVSNVTNV"
    "UNVVNVWNVXNVYNVZNWONWPNWQNWRNWSNWTNWUNWVNWWNWXNWYNWZNXONXPNXQNXRNXSNXTNXUN"
    "XVNXWNXXNXYNXZNYONYPNYQNYRNYSNYTNYUNYVNYWNYXNYYNYZNZONZPNZQNZRNZSNZTNZUNZV"
    "NZWNZXNZYNZZOOOPOOQOOROOSOOTOOUOOVOOWOOXOOYOOZOPPOPQOPROPSOPTOPUOPVOPWOPXO"
    "PYOPZOQPOQQOQROQSOQTOQUOQVOQWOQXOQYOQZORPORQORRORSORTORUORVORWORXORYORZOSP"
    "OSQOSROSSOSTOSUOSVOSWOSXOSYOSZOTPOTQOTROTSOTTOTUOTVOTWOTXOTYOTZOUPOUQOUROU"
    "SOUTOUUOUVOUWOUXOUYOUZOVPOVQOVROVSOVTOVUOVVOVWOVXOVYOVZOWPOWQOWROWSOWTOWUO"
    "WVOWWOWXOWYOWZOXPOXQOXROXSOXTOXUOXVOXWOXXOXYOXZOYPOYQOYROYSOYTOYUOYVOYWOYX"
    "OYYOYZOZPOZQOZROZSOZTOZUOZVOZWOZXOZYOZZPPPQPPRPPSPPTPPUPPVPPWPPXPPYPPZPQQP"
    "QRPQSPQTPQUPQVPQWPQXPQYPQZPRQPRRPRSPRTPRUPRVPRWPRXPRYPRZPSQPSRPSSPSTPSUPSV"
    "PSWPSXPSYPSZPTQPTRPTSPTTPTUPTVTABUABVABWABXABYABZACBACCACDACEACFACGACHACIA"
    "CJACKACLACMACNACOACPACQACRACSACTACUACVACWACXACYACZADBADCADDADEADFADGADHADI"
    "ADJADKADLADMADAAABAACAADAAEAAFAAGAAHAAIAAJAAKAALAAMAANAAOAAPAAQAARAASAATAA"
    "UAAVAAWAAXAAYAAZABBABCABDABEABFABGABHABIABJABKABLABMABNABOABPABQABRABSABHA"
    "FIAFJAFKAFLAFMAFNAFOAFPAFQAFRAFSAFTAFUAFVAFWAFXAFYAFZAGBAGCAGDAGEAGFAGGAGH"
    "AGIAGJAGKAGLAGMAGNAGOAGPAGQAGRAGSAGTAGUAGVAGWAGXAGYAGZAHNADOADPADQADRADSAD"
    "TADUADVADWADXADYADZAEBAECAEDAEEAEFAEGAEHAEIAEJAEKAELAEMAENAEOAEPAEQAERAESA"
    "ETAEUAEVAEWAEXAEYAEZAFBAFCAFDAFEAFFAFGAFUAIVAIWAIXAIYAIZAJBAJCAJDAJEAJFAJG"
    "AJHAJIAJJAJKAJLAJMAJNAJOAJPAJQAJRAJSAJTAJUAJVAJWAJXAJYAJZAKBAKCAKDAKEAKFAK"
    "GAKHAKIAKJAKKAKLAKMAKNAKBAHCAHDAHEAHFAHGAHHAHIAHJAHKAHLAHMAHNAHOAHPAHQAHRA"
    "HSAHTAHUAHVAHWAHXAHYAHZAIBAICAIDAIEAIFAIGAIHAIIAIJAIKAILAIMAINAIOAIPAIQAIR"
    "AISAITAIIAMJAMKAMLAMMAMNAMOAMPAMQAMRAMSAMTAMUAMVAMWAMXAMYAMZANBANCANDANEAN"
    "FANGANHANIANJANKANLANMANNANOANPANQANRANSANTANUANVANWANXANYANZAOBAOOAKPAKQA"
    "KRAKSAKTAKUAKVAKWAKXAKYAKZALBALCALDALEALFALGALHALIALJALKALLALMALNALOALPALQ"
    "ALRALSALTALUALVALWALXALYALZAMBAMCAMDAMEAMFAMGAMHAMVAPWAPXAPYAPZAQBAQCAQDAQ"
    "EAQFAQGAQHAQIAQJAQKAQLAQMAQNAQOAQPAQQAQRAQSAQTAQUAQVAQWAQXAQYAQZARBARCARDA"
    "REARFARGARHARIARJARKARLARMARNAROARCAODAOEAOFAOGAOHAOIAOJAOKAOLAOMAONAOOAOP"
    "AOQAORAOSAOTAOUAOVAOWAOXAOYAOZAPBAPCAPDAPEAPFAPGAPHAPIAPJAPKAPLAPMAPNAPOAP"
    "PAPQAPRAPSAPTAPUAPJATKATLATMATNATOATPATQATRATSATTATUATVATWATXATYATZAUBAUCA"
    "UDAUEAUFAUGAUHAUIAUJAUKAULAUMAUNAUOAUPAUQAURAUSAUTAUUAUVAUWAUXAUYAUZAVBAVC"
    "AVPARQARRARSARTARUARVARWARXARYARZASBASCASDASEASFASGASHASIASJASKASLASMASNAS"
    "OASPASQASRASSASTASUASVASWASXASYASZATBATCATDATEATFATGATHATIATWAWXAWYAWZAXBA"
    "XCAXDAXEAXFAXGAXHAXIAXJAXKAXLAXMAXNAXOAXPAXQAXRAXSAXTAXUAXVAXWAXXAXYAXZAYB"
    "AYCAYDAYEAYFAYGAYHAYIAYJAYKAYLAYMAYNAYOAYPAYDAVEAVFAVGAVHAVIAVJAVKAVLAVMAV"
    "NAVOAVPAVQAVRAVSAVTAVUAVVAVWAVXAVYAVZAWBAWCAWDAWEAWFAWGAWHAWIAWJAWKAWLAWMA"
    "WNAWOAWPAWQAWRAWSAWTAWUAWVAWBLBBMBBNBBOBBPBBQBBRBBSBBTBBUBBVBBWBBXBBYBBZBC"
    "CBCDBCEBCFBCGBCHBCIBCJBCKBCLBCMBCNBCOBCPBCQBCRBCSBCTBCUBCVBCWBCXBCYBCZBDCB"
    "DDBDEBDFBDGBQAYRAYSAYTAYUAYVAYWAYXAYYAYZAZBAZCAZDAZEAZFAZGAZHAZIAZJAZKAZLA"
    "ZMAZNAZOAZPAZQAZRAZSAZTAZUAZVAZWAZXAZYAZZBBBCBBDBBEBBFBBGBBHBBIBBJBBKBFDBF"
    "EBFFBFGBFHBFIBFJBFKBFLBFMBFNBFOBFPBFQBFRBFSBFTBFUBFVBFWBFXBFYBFZBGCBGDBGEB"
    "GFBGGBGHBGIBGJBGKBGLBGMBGNBGOBGPBGQBGRBGSBGTBGUBGVBGWBDHBDIBDJBDKBDLBDMBDN"
    "BDOBDPBDQBDRBDSBDTBDUBDVBDWBDXBDYBDZBECBEDBEEBEFBEGBEHBEIBEJBEKBELBEMBENBE"
    "OBEPBEQBERBESBETBEUBEVBEWBEXBEYBEZBFCBITBIUBIVBIWBIXBIYBIZBJCBJDBJEBJFBJGB"
    "JHBJIBJJBJKBJLBJMBJNBJOBJPBJQBJRBJSBJTBJUBJVBJWBJXBJYBJZBKCBKDBKEBKFBKGBKH"
    "BKIBKJBKKBKLBKMBKNBKOBGXBGYBGZBHCBHDBHEBHFBHGBHHBHIBHJBHKBHLBHMBHNBHOBHPBH"
    "QBHRBHSBHTBHUBHVBHWBHXBHYBHZBICBIDBIEBIFBIGBIHBIIBIJBIKBILBIMBINBIOBIPBIQB"
    "IRBISBMLBMMBMNBMOBMPBMQBMRBMSBMTBMUBMVBMWBMXBMYBMZBNCBNDBNEBNFBNGBNHBNIBNJ"
    "BNKBNLBNMBNNBNOBNPBNQBNRBNSBNTBNUBNVBNWBNXBNYBNZBOCBODBOEBOFBOGBKPBKQBKRBK"
    "SBKTBKUBKVBKWBKXBKYBKZBLCBLDBLEBLFBLGBLHBLIBLJBLKBLLBLMBLNBLOBLPBLQBLRBLSB"
    "LTBLUBLVBLWBLXBLYBLZBMCBMDBMEBMFBMGBMHBMIBMJBMKBQDBQEBQFBQGBQHBQIBQJBQKBQL"
    "BQMBQNBQOBQPBQQBQRBQSBQTBQUBQVBQWBQXBQYBQZBRCBRDBREBRFBRGBRHBRIBRJBRKBRLBR"
    "MBRNBROBRPBRQBRRBRSBRTBRUBRVBRWBOHBOIBOJBOKBOLBOMBONBOOBOPBOQBORBOSBOTBOUB"
    "OVBOWBOXBOYBOZBPCBPDBPEBPFBPGBPHBPIBPJBPKBPLBPMBPNBPOBPPBPQBPRBPSBPTBPUBPV"
    "BPWBPXBPYBPZBQCBTTBTUBTVBTWBTXBTYBTZBUCBUDBUEBUFBUGBUHBUIBUJBUKBULBUMBUNBU"
    "OBUPBUQBURBUSBUTBUUBUVBUWBUXBUYBUZBVCBVDBVEBVFBVGBVHBVIBVJBVKBVLBVMBVNBVOB"
    "RXBRYBRZBSCBSDBSEBSFBSGBSHBSIBSJBSKBSLBSMBSNBSOBSPBSQBSRBSSBSTBSUBSVBSWBSX"
    "BSYBSZBTCBTDBTEBTFBTGBTHBTIBTJBTKBTLBTMBTNBTOBTPBTQBTRBTSBXLBXMBXNBXOBXPBX"
    "QBXRBXSBXTBXUBXVBXWBXXBXYBXZBYCBYDBYEBYFBYGBYHBYIBYJBYKBYLBYMBYNBYOBYPBYQB"
    "YRBYSBYTBYUBYVBYWBYXBYYBYZBZCBZDBZEBZFBZGBVPBVQBVRBVSBVTBVUBVVBVWBVXBVYBVZ"
    "BWCBWDBWEBWFBWGBWHBWIBWJBWKBWLBWMBWNBWOBWPBWQBWRBWSBWTBWUBWVBWWBWXBWYBWZBX"
    "CBXDBXEBXFBXGBXHBXIBXJBXKBCDFCDGCDHCDICDJCDKCDLCDMCDNCDOCDPCDQCDRCDSCDTCDU"
    "CDVCDWCDXCDYCDZCEDCEECEFCEGCEHCEICEJCEKCELCEMCENCEOCEPCEQCERCESCETCEUCEVCE"
    "WCEXCEYCEZZHBZIBZJBZKBZLBZMBZNBZOBZPBZQBZRBZSBZTBZUBZVBZWBZXBZYBZZCCCDCCEC"
    "CFCCGCCHCCICCJCCKCCLCCMCCNCCOCCPCCQCCRCCSCCTCCUCCVCCWCCXCCYCCZCDDCDECGYCGZ"
    "CHDCHECHFCHGCHHCHICHJCHKCHLCHMCHNCHOCHPCHQCHRCHSCHTCHUCHVCHWCHXCHYCHZCIDCI"
    "ECIFCIGCIHCIICIJCIKCILCIMCINCIOCIPCIQCIRCISCITCIUCIVCFDCFECFFCFGCFHCFICFJC"
    "FKCFLCFMCFNCFOCFPCFQCFRCFSCFTCFUCFVCFWCFXCFYCFZCGDCGECGFCGGCGHCGICGJCGKCGL"
    "CGMCGNCGOCGPCGQCGRCGSCGTCGUCGVCGWCGXCKUCKVCKWCKXCKYCKZCLDCLECLFCLGCLHCLICL"
    "JCLKCLLCLMCLNCLOCLPCLQCLRCLSCLTCLUCLVCLWCLXCLYCLZCMDCMECMFCMGCMHCMICMJCMKC"
    "MLCMMCMNCMOCMPCMQCMRCIWCIXCIYCIZCJDCJECJFCJGCJHCJICJJCJKCJLCJMCJNCJOCJPCJQ"
    "CJRCJSCJTCJUCJVCJWCJXCJYCJZCKDCKECKFCKGCKHCKICKJCKKCKLCKMCKNCKOCKPCKQCKRCK"
    "SCKTCOQCORCOSCOTCOUCOVCOWCOXCOYCOZCPDCPECPFCPGCPHCPICPJCPKCPLCPMCPNCPOCPPC"
    "PQCPRCPSCPTCPUCPVCPWCPXCPYCPZCQDCQECQFCQGCQHCQICQJCQKCQLCQMCQNCMSCMTCMUCMV"
    "CMWCMXCMYCMZCNDCNECNFCNGCNHCNICNJCNKCNLCNMCNNCNOCNPCNQCNRCNSCNTCNUCNVCNWCN"
    "XCNYCNZCODCOECOFCOGCOHCOICOJCOKCOLCOMCONCOOCOPCSMCSNCSOCSPCSQCSRCSSCSTCSUC"
    "SVCSWCSXCSYCSZCTDCTECTFCTGCTHCTICTJCTKCTLCTMCTNCTOCTPCTQCTRCTSCTTCTUCTVCTW"
    "CTXCTYCTZCUDCUECUFCUGCUHCUICUJCQOCQPCQQCQRCQSCQTCQUCQVCQWCQXCQYCQZCRDCRECR"
    "FCRGCRHCRICRJCRKCRLCRMCRNCROCRPCRQCRRCRSCRTCRUCRVCRWCRXCRYCRZCSDCSECSFCSGC"
    "SHCSICSJCSKCSLCWICWJCWKCWLCWMCWNCWOCWPCWQCWRCWSCWTCWUCWVCWWCWXCWYCWZCXDCXE"
    "CXFCXGCXHCXICXJCXKCXLCXMCXNCXOCXPCXQCXRCXSCXTCXUCXVCXWCXXCXYCXZCYDCYECYFCU"
    "KCULCUMCUNCUOCUPCUQCURCUSCUTCUUCUVCUWCUXCUYCUZCVDCVECVFCVGCVHCVICVJCVKCVLC"
    "VMCVNCVOCVPCVQCVRCVSCVTCVUCVVCVWCVXCVYCVZCWDCWECWFCWGCWHEDDFDDGDDHDDIDDJDD"
    "KDDLDDMDDNDDODDPDDQDDRDDSDDTDDUDDVDDWDDXDDYDDZDEEDEFDEGDEHDEIDEJDEKDELDEMD"
    "ENDEODEPDEQDERDESDETDEUDEVDEWDEXDEYDEZDFCYGCYHCYICYJCYKCYLCYMCYNCYOCYPCYQC"
    "YRCYSCYTCYUCYVCYWCYXCYYCYZCZDCZECZFCZGCZHCZICZJCZKCZLCZMCZNCZOCZPCZQCZRCZS"
    "CZTCZUCZVCZWCZXCZYCZZDDDEDHFDHGDHHDHIDHJDHKDHLDHMDHNDHODHPDHQDHRDHSDHTDHUD"
    "HVDHWDHXDHYDHZDIEDIFDIGDIHDIIDIJDIKDILDIMDINDIODIPDIQDIRDISDITDIUDIVDIWDIX"
    "DIYDIZDJEDFFDFGDFHDFIDFJDFKDFLDFMDFNDFODFPDFQDFRDFSDFTDFUDFVDFWDFXDFYDFZDG"
    "EDGFDGGDGHDGIDGJDGKDGLDGMDGNDGODGPDGQDGRDGSDGTDGUDGVDGWDGXDGYDGZDHEDLFDLGD"
    "LHDLIDLJDLKDLLDLMDLNDLODLPDLQDLRDLSDLTDLUDLVDLWDLXDLYDLZDMEDMFDMGDMHDMIDMJ"
    "DMKDMLDMMDMNDMODMPDMQDMRDMSDMTDMUDMVDMWDMXDMYDMZDNEDJFDJGDJHDJIDJJDJKDJLDJ"
    "MDJNDJODJPDJQDJRDJSDJTDJUDJVDJWDJXDJYDJZDKEDKFDKGDKHDKIDKJDKKDKLDKMDKNDKOD"
    "KPDKQDKRDKSDKTDKUDKVDKWDKXDKYDKZDLEDPFDPGDPHDPIDPJDPKDPLDPMDPNDPODPPDPQDPR"
    "DPSDPTDPUDPVDPWDPXDPYDPZDQEDQFDQGDQHDQIDQJDQKDQLDQMDQNDQODQPDQQDQRDQSDQTDQ"
    "UDQVDQWDQXDQYDQZDREDNFDNGDNHDNIDNJDNKDNLDNMDNNDNODNPDNQDNRDNSDNTDNUDNVDNWD"
    "NXDNYDNZDOEDOFDOGDOHDOIDOJDOKDOLDOMDONDOODOPDOQDORDOSDOTDOUDOVDOWDOXDOYDOZ"
    "DPEDTFDTGDTHDTIDTJDTKDTLDTMDTNDTODTPDTQDTRDTSDTTDTUDTVDTWDTXDTYDTZDUEDUFDU"
    "GDUHDUIDUJDUKDULDUMDUNDUODUPDUQDURDUSDUTDUUDUVDUWDUXDUYDUZDVEDRFDRGDRHDRID"
    "RJDRKDRLDRMDRNDRODRPDRQDRRDRSDRTDRUDRVDRWDRXDRYDRZDSEDSFDSGDSHDSIDSJDSKDSL"
    "DSMDSNDSODSPDSQDSRDSSDSTDSUDSVDSWDSXDSYDSZDTEDXFDXGDXHDXIDXJDXKDXLDXMDXNDX"
    "ODXPDXQDXRDXSDXTDXUDXVDXWDXXDXYDXZDYEDYFDYGDYHDYIDYJDYKDYLDYMDYNDYODYPDYQD"
    "YRDYSDYTDYUDYVDYWDYXDYYDYZDZEDVFDVGDVHDVIDVJDVKDVLDVMDVNDVODVPDVQDVRDVSDVT"
    "DVUDVVDVWDVXDVYDVZDWEDWFDWGDWHDWIDWJDWKDWLDWMDWNDWODWPDWQDWRDWSDWTDWUDWVDW"
    "WDWXDWYDWZDXFGEFHEFIEFJEFKEFLEFMEFNEFOEFPEFQEFREFSEFTEFUEFVEFWEFXEFYEFZEGF"
    "EGGEGHEGIEGJEGKEGLEGMEGNEGOEGPEGQEGREGSEGTEGUEGVEGWEGXEGYEGZEHFEHGEHHEEDZF"
    "DZGDZHDZIDZJDZKDZLDZMDZNDZODZPDZQDZRDZSDZTDZUDZVDZWDZXDZYDZZEEEFEEGEEHEEIE"
    "EJEEKEELEEMEENEEOEEPEEQEEREESEETEEUEEVEEWEEXEEYEEZEFFEJKEJLEJMEJNEJOEJPEJQ"
    "EJREJSEJTEJUEJVEJWEJXEJYEJZEKFEKGEKHEKIEKJEKKEKLEKMEKNEKOEKPEKQEKREKSEKTEK"
    "UEKVEKWEKXEKYEKZELFELGELHELIELJELKELLEHIEHJEHKEHLEHMEHNEHOEHPEHQEHREHSEHTE"
    "HUEHVEHWEHXEHYEHZEIFEIGEIHEIIEIJEIKEILEIMEINEIOEIPEIQEIREISEITEIUEIVEIWEIX"
    "EIYEIZEJFEJGEJHEJIEJJENOENPENQENRENSENTENUENVENWENXENYENZEOFEOGEOHEOIEOJEO"
    "KEOLEOMEONEOOEOPEOQEOREOSEOTEOUEOVEOWEOXEOYEOZEPFEPGEPHEPIEPJEPKEPLEPMEPNE"
    "POEPPELMELNELOELPELQELRELSELTELUELVELWELXELYELZEMFEMGEMHEMIEMJEMKEMLEMMEMN"
    "EMOEMPEMQEMREMSEMTEMUEMVEMWEMXEMYEMZENFENGENHENIENJENKENLENMENNERSERTERUER"
    "VERWERXERYERZESFESGESHESIESJESKESLESMESNESOESPESQESRESSESTESUESVESWESXESYE"
    "SZETFETGETHETIETJETKETLETMETNETOETPETQETRETSETTEPQEPREPSEPTEPUEPVEPWEPXEPY"
    "EPZEQFEQGEQHEQIEQJEQKEQLEQMEQNEQOEQPEQQEQREQSEQTEQUEQVEQWEQXEQYEQZERFERGER"
    "HERIERJERKERLERMERNEROERPERQERREVWEVXEVYEVZEWFEWGEWHEWIEWJEWKEWLEWMEWNEWOE"
    "WPEWQEWREWSEWTEWUEWVEWWEWXEWYEWZEXFEXGEXHEXIEXJEXKEXLEXMEXNEXOEXPEXQEXREXS"
    "EXTEXUEXVEXWEXXETUETVETWETXETYETZEUFEUGEUHEUIEUJEUKEULEUMEUNEUOEUPEUQEUREU"
    "SEUTEUUEUVEUWEUXEUYEUZEVFEVGEVHEVIEVJEVKEVLEVMEVNEVOEVPEVQEVREVSEVTEVUEVVE"
    "FFGFFHFFIFFJFFKFFLFFMFFNFFOFFPFFQFFRFFSFFTFFUFFVFFWFFXFFYFFZFGGFGHFGIFGJFG"
    "KFGLFGMFGNFGOFGPFGQFGRFGSFGTFGUFGVFGWFGXFGYFGZFHGFHHFHIFHJXYEXZEYFEYGEYHEY"
    "IEYJEYKEYLEYMEYNEYOEYPEYQEYREYSEYTEYUEYVEYWEYXEYYEYZEZFEZGEZHEZIEZJEZKEZLE"
    "ZMEZNEZOEZPEZQEZREZSEZTEZUEZVEZWEZXEZYEZZFFJOFJPFJQFJRFJSFJTFJUFJVFJWFJXFJ"
    "YFJZFKGFKHFKIFKJFKKFKLFKMFKNFKOFKPFKQFKRFKSFKTFKUFKVFKWFKXFKYFKZFLGFLHFLIF"
    "LJFLKFLLFLMFLNFLOFLPFLQFLRFHKFHLFHMFHNFHOFHPFHQFHRFHSFHTFHUFHVFHWFHXFHYFHZ"
    "FIGFIHFIIFIJFIKFILFIMFINFIOFIPFIQFIRFISFITFIUFIVFIWFIXFIYFIZFJGFJHFJIFJJFJ"
    "KFJLFJMFJNFNWFNXFNYFNZFOGFOHFOIFOJFOKFOLFOMFONFOOFOPFOQFORFOSFOTFOUFOVFOWF"
    "OXFOYFOZFPGFPHFPIFPJFPKFPLFPMFPNFPOFPPFPQFPRFPSFPTFPUFPVFPWFPXFPYFPZFLSFLT"
    "FLUFLVFLWFLXFLYFLZFMGFMHFMIFMJFMKFMLFMMFMNFMOFMPFMQFMRFMSFMTFMUFMVFMWFMXFM"
    "YFMZFNGFNHFNIFNJFNKFNLFNMFNNFNOFNPFNQFNRFNSFNTFNUFNVFSKFSLFSMFSNFSOFSPFSQF"
    "SRFSSFSTFSUFSVFSWFSXFSYFSZFTGFTHFTIFTJFTKFTLFTMFTNFTOFTPFTQFTRFTSFTTFTUFTV"
    "FTWFTXFTYFTZFUGFUHFUIFUJFUKFULFUMFUNFQGFQHFQIFQJFQKFQLFQMFQNFQOFQPFQQFQRFQ"
    "SFQTFQUFQVFQWFQXFQYFQZFRGFRHFRIFRJFRKFRLFRMFRNFROFRPFRQFRRFRSFRTFRUFRVFRWF"
    "RXFRYFRZFSGFSHFSIFSJFWSFWTFWUFWVFWWFWXFWYFWZFXGFXHFXIFXJFXKFXLFXMFXNFXOFXP"
    "FXQFXRFXSFXTFXUFXVFXWFXXFXYFXZFYGFYHFYIFYJFYKFYLFYMFYNFYOFYPFYQFYRFYSFYTFY"
    "UFYVFUOFUPFUQFURFUSFUTFUUFUVFUWFUXFUYFUZFVGFVHFVIFVJFVKFVLFVMFVNFVOFVPFVQF"
    "VRFVSFVTFVUFVVFVWFVXFVYFVZFWGFWHFWIFWJFWKFWLFWMFWNFWOFWPFWQFWRHGHIGHJGHKGH"
    "LGHMGHNGHOGHPGHQGHRGHSGHTGHUGHVGHWGHXGHYGHZGIHGIIGIJGIKGILGIMGINGIOGIPGIQG"
    "IRGISGITGIUGIVGIWGIXGIYGIZGJHGJIGJJGJKGJLGJMGJFYWFYXFYYFYZFZGFZHFZIFZJFZKF"
    "ZLFZMFZNFZOFZPFZQFZRFZSFZTFZUFZVFZWFZXFZYFZZGGGHGGIGGJGGKGGLGGMGGNGGOGGPGG"
    "QGGRGGSGGTGGUGGVGGWGGXGGYGGZGHTGLUGLVGLWGLXGLYGLZGMHGMIGMJGMKGMLGMMGMNGMOG"
    "MPGMQGMRGMSGMTGMUGMVGMWGMXGMYGMZGNHGNIGNJGNKGNLGNMGNNGNOGNPGNQGNRGNSGNTGNU"
    "GNVGNWGNXGNYGNNGJOGJPGJQGJRGJSGJTGJUGJVGJWGJXGJYGJZGKHGKIGKJGKKGKLGKMGKNGK"
    "OGKPGKQGKRGKSGKTGKUGKVGKWGKXGKYGKZGLHGLIGLJGLKGLLGLMGLNGLOGLPGLQGLRGLSGLMG"
    "QNGQOGQPGQQGQRGQSGQTGQUGQVGQWGQXGQYGQZGRHGRIGRJGRKGRLGRMGRNGROGRPGRQGRRGRS"
    "GRTGRUGRVGRWGRXGRYGRZGSHGSIGSJGSKGSLGSMGSNGSOGSPGSQGSRGSZGOHGOIGOJGOKGOLGO"
    "MGONGOOGOPGOQGORGOSGOTGOUGOVGOWGOXGOYGOZGPHGPIGPJGPKGPLGPMGPNGPOGPPGPQGPRG"
    "PSGPTGPUGPVGPWGPXGPYGPZGQHGQIGQJGQKGQLGQYGUZGVHGVIGVJGVKGVLGVMGVNGVOGVPGVQ"
    "GVRGVSGVTGVUGVVGVWGVXGVYGVZGWHGWIGWJGWKGWLGWMGWNGWOGWPGWQGWRGWSGWTGWUGWVGW"
    "WGWXGWYGWZGXHGXIGXJGXKGXSGSTGSUGSVGSWGSXGSYGSZGTHGTIGTJGTKGTLGTMGTNGTOGTPG"
    "TQGTRGTSGTTGTUGTVGTWGTXGTYGTZGUHGUIGUJGUKGULGUMGUNGUOGUPGUQGURGUSGUTGUUGUV"
    "GUWGUXGURGZSGZTGZUGZVGZWGZXGZYGZZHHHIHHJHHKHHLHHMHHNHHOHHPHHQHHRHHSHHTHHUH"
    "HVHHWHHXHHYHHZHIIHIJHIKHILHIMHINHIOHIPHIQHIRHISHITHIUHIVHIWHIXHIYHLGXMGXNG"
    "XOGXPGXQGXRGXSGXTGXUGXVGXWGXXGXYGXZGYHGYIGYJGYKGYLGYMGYNGYOGYPGYQGYRGYSGYT"
    "GYUGYVGYWGYXGYYGYZGZHGZIGZJGZKGZLGZMGZNGZOGZPGZQGZLPHLQHLRHLSHLTHLUHLVHLWH"
    "LXHLYHLZHMIHMJHMKHMLHMMHMNHMOHMPHMQHMRHMSHMTHMUHMVHMWHMXHMYHMZHNIHNJHNKHNL"
    "HNMHNNHNOHNPHNQHNRHNSHNTHNUHNVHNWHIZHJIHJJHJKHJLHJMHJNHJOHJPHJQHJRHJSHJTHJ"
    "UHJVHJWHJXHJYHJZHKIHKJHKKHKLHKMHKNHKOHKPHKQHKRHKSHKTHKUHKVHKWHKXHKYHKZHLIH"
    "LJHLKHLLHLMHLNHLOHQNHQOHQPHQQHQRHQSHQTHQUHQVHQWHQXHQYHQZHRIHRJHRKHRLHRMHRN"
    "HROHRPHRQHRRHRSHRTHRUHRVHRWHRXHRYHRZHSIHSJHSKHSLHSMHSNHSOHSPHSQHSRHSSHSTHS"
    "UHNXHNYHNZHOIHOJHOKHOLHOMHONHOOHOPHOQHORHOSHOTHOUHOVHOWHOXHOYHOZHPIHPJHPKH"
    "PLHPMHPNHPOHPPHPQHPRHPSHPTHPUHPVHPWHPXHPYHPZHQIHQJHQKHQLHQMHVLHVMHVNHVOHVP"
    "HVQHVRHVSHVTHVUHVVHVWHVXHVYHVZHWIHWJHWKHWLHWMHWNHWOHWPHWQHWRHWSHWTHWUHWVHW"
    "WHWXHWYHWZHXIHXJHXKHXLHXMHXNHXOHXPHXQHXRHXSHSVHSWHSXHSYHSZHTIHTJHTKHTLHTMH"
    "TNHTOHTPHTQHTRHTSHTTHTUHTVHTWHTXHTYHTZHUIHUJHUKHULHUMHUNHUOHUPHUQHURHUSHUT"
    "HUUHUVHUWHUXHUYHUZHVIHVJHVKHIIKIILIIMIINIIOIIPIIQIIRIISIITIIUIIVIIWIIXIIYI"
    "IZIJJIJKIJLIJMIJNIJOIJPIJQIJRIJSIJTIJUIJVIJWIJXIJYIJZIKJIKKIKLIKMIKNIKOIKP"
    "IKQIKRIKSIKTXTHXUHXVHXWHXXHXYHXZHYIHYJHYKHYLHYMHYNHYOHYPHYQHYRHYSHYTHYUHYV"
    "HYWHYXHYYHYZHZIHZJHZKHZLHZMHZNHZOHZPHZQHZRHZSHZTHZUHZVHZWHZXHZYHZZIIIJINNI"
    "NOINPINQINRINSINTINUINVINWINXINYINZIOJIOKIOLIOMIONIOOIOPIOQIORIOSIOTIOUIOV"
    "IOWIOXIOYIOZIPJIPKIPLIPMIPNIPOIPPIPQIPRIPSIPTIPUIPVIPWIKUIKVIKWIKXIKYIKZIL"
    "JILKILLILMILNILOILPILQILRILSILTILUILVILWILXILYILZIMJIMKIMLIMMIMNIMOIMPIMQI"
    "MRIMSIMTIMUIMVIMWIMXIMYIMZINJINKINLINMISQISRISSISTISUISVISWISXISYISZITJITK"
    "ITLITMITNITOITPITQITRITSITTITUITVITWITXITYITZIUJIUKIULIUMIUNIUOIUPIUQIURIU"
    "SIUTIUUIUVIUWIUXIUYIUZIPXIPYIPZIQJIQKIQLIQMIQNIQOIQPIQQIQRIQSIQTIQUIQVIQWI"
    "QXIQYIQZIRJIRKIRLIRMIRNIROIRPIRQIRRIRSIRTIRUIRVIRWIRXIRYIRZISJISKISLISMISN"
    "ISOISPIXTIXUIXVIXWIXXIXYIXZIYJIYKIYLIYMIYNIYOIYPIYQIYRIYSIYTIYUIYVIYWIYXIY"
    "YIYZIZJIZKIZLIZMIZNIZOIZPIZQIZRIZSIZTIZUIZVIZWIZXIZYIZZJJJKJJLJJIVJIVKIVLI"
    "VMIVNIVOIVPIVQIVRIVSIVTIVUIVVIVWIVXIVYIVZIWJIWKIWLIWMIWNIWOIWPIWQIWRIWSIWT"
    "IWUIWVIWWIWXIWYIWZIXJIXKIXLIXMIXNIXOIXPIXQIXRIXSYJLZJMKJMLJMMJMNJMOJMPJMQJ"
    "MRJMSJMTJMUJMVJMWJMXJMYJMZJNKJNLJNMJNNJNOJNPJNQJNRJNSJNTJNUJNVJNWJNXJNYJNZ"
    "JOKJOLJOMJONJOOJOPJOQJORJOSJOTJOMJJNJJOJJPJJQJJRJJSJJTJJUJJVJJWJJXJJYJJZJK"
    "KJKLJKMJKNJKOJKPJKQJKRJKSJKTJKUJKVJKWJKXJKYJKZJLKJLLJLMJLNJLOJLPJLQJLRJLSJ"
    "LTJLUJLVJLWJLXJLQJRRJRSJRTJRUJRVJRWJRXJRYJRZJSKJSLJSMJSNJSOJSPJSQJSRJSSJST"
    "JSUJSVJSWJSXJSYJSZJTKJTLJTMJTNJTOJTPJTQJTRJTSJTTJTUJTVJTWJTXJTYJTZJUKJULJU"
    "UJOVJOWJOXJOYJOZJPKJPLJPMJPNJPOJPPJPQJPRJPSJPTJPUJPVJPWJPXJPYJPZJQKJQLJQMJ"
    "QNJQOJQPJQQJQRJQSJQTJQUJQVJQWJQXJQYJQZJRKJRLJRMJRNJROJRPJRYJWZJXKJXLJXMJXN"
    "JXOJXPJXQJXRJXSJXTJXUJXVJXWJXXJXYJXZJYKJYLJYMJYNJYOJYPJYQJYRJYSJYTJYUJYVJY"
    "WJYXJYYJYZJZKJZLJZMJZNJZOJZPJZQJZRJZSJZTJZMJUNJUOJUPJUQJURJUSJUTJUUJUVJUWJ"
    "UXJUYJUZJVKJVLJVMJVNJVOJVPJVQJVRJVSJVTJVUJVVJVWJVXJVYJVZJWKJWLJWMJWNJWOJWP"
    "JWQJWRJWSJWTJWUJWVJWWJWXJWMTKMUKMVKMWKMXKMYKMZKNLKNMKNNKNOKNPKNQKNRKNSKNTK"
    "NUKNVKNWKNXKNYKNZKOLKOMKONKOOKOPKOQKORKOSKOTKOUKOVKOWKOXKOYKOZKPLKPMKPNKPO"
    "KPPKPQKPRKUJZVJZWJZXJZYJZZKKKLKKMKKNKKOKKPKKQKKRKKSKKTKKUKKVKKWKKXKKYKKZKL"
    "LKLMKLNKLOKLPKLQKLRKLSKLTKLUKLVKLWKLXKLYKLZKMLKMMKMNKMOKMPKMQKMRKMSKSRKSSK"
    "STKSUKSVKSWKSXKSYKSZKTLKTMKTNKTOKTPKTQKTRKTSKTTKTUKTVKTWKTXKTYKTZKULKUMKUN"
    "KUOKUPKUQKURKUSKUTKUUKUVKUWKUXKUYKUZKVLKVMKVNKVOKVPKPSKPTKPUKPVKPWKPXKPYKP"
    "ZKQLKQMKQNKQOKQPKQQKQRKQSKQTKQUKQVKQWKQXKQYKQZKRLKRMKRNKROKRPKRQKRRKRSKRTK"
    "RUKRVKRWKRXKRYKRZKSLKSMKSNKSOKSPKSQKYPKYQKYRKYSKYTKYUKYVKYWKYXKYYKYZKZLKZM"
    "KZNKZOKZPKZQKZRKZSKZTKZUKZVKZWKZXKZYKZZLLLMLLNLLOLLPLLQLLRLLSLLTLLULLVLLWL"
    "LXLLYLLZLMMLMNLMOLMPVQKVRKVSKVTKVUKVVKVWKVXKVYKVZKWLKWMKWNKWOKWPKWQKWRKWSK"
    "WTKWUKWVKWWKWXKWYKWZKXLKXMKXNKXOKXPKXQKXRKXSKXTKXUKXVKXWKXXKXYKXZKYLKYMKYN"
    "KYOKLPSLPTLPULPVLPWLPXLPYLPZLQMLQNLQOLQPLQQLQRLQSLQTLQULQVLQWLQXLQYLQZLRML"
    "RNLROLRPLRQLRRLRSLRTLRULRVLRWLRXLRYLRZLSMLSNLSOLSPLSQLSRLSSLSTLMQLMRLMSLMT"
    "LMULMVLMWLMXLMYLMZLNMLNNLNOLNPLNQLNRLNSLNTLNULNVLNWLNXLNYLNZLOMLONLOOLOPLO"
    "QLORLOSLOTLOULOVLOWLOXLOYLOZLPMLPNLPOLPPLPQLPRLVWLVXLVYLVZLWMLWNLWOLWPLWQL"
    "WRLWSLWTLWULWVLWWLWXLWYLWZLXMLXNLXOLXPLXQLXRLXSLXTLXULXVLXWLXXLXYLXZLYMLYN"
    "LYOLYPLYQLYRLYSLYTLYULYVLYWLYXLSULSVLSWLSXLSYLSZLTMLTNLTOLTPLTQLTRLTSLTTLT"
    "ULTVLTWLTXLTYLTZLUMLUNLUOLUPLUQLURLUSLUTLUULUVLUWLUXLUYLUZLVMLVNLVOLVPLVQL"
    "VRLVSLVTLVULVVOMOPMOQMORMOSMOTMOUMOVMOWMOXMOYMOZMPNMPOMPPMPQMPRMPSMPTMPUMP"
    "VMPWMPXMPYMPZMQNMQOMQPMQQMQRMQSMQTMQUMQVMQWMQXMQYMQZMRNMROMRPMRQMRRMRSMRLY"
    "YLYZLZMLZNLZOLZPLZQLZRLZSLZTLZULZVLZWLZXLZYLZZMMMNMMOMMPMMQMMRMMSMMTMMUMMV"
    "MMWMMXMMYMMZMNNMNOMNPMNQMNRMNSMNTMNUMNVMNWMNXMNYMNZMONMOYMUZMVNMVOMVPMVQMV"
    "RMVSMVTMVUMVVMVWMVXMVYMVZMWNMWOMWPMWQMWRMWSMWTMWUMWVMWWMWXMWYMWZMXNMXOMXPM"
    "XQMXRMXSMXTMXUMXVMXWMXXMXYMXZMYNMYOMYPMYTMRUMRVMRWMRXMRYMRZMSNMSOMSPMSQMSR"
    "MSSMSTMSUMSVMSWMSXMSYMSZMTNMTOMTPMTQMTRMTSMTTMTUMTVMTWMTXMTYMTZMUNMUOMUPMU"
    "QMURMUSMUTMUUMUVMUWMUXMUOXNOYNOZNPONPPNPQNPRNPSNPTNPUNPVNPWNPXNPYNPZNQONQP"
    "NQQNQRNQSNQTNQUNQVNQWNQXNQYNQZNRONRPNRQNRRNRSNRTNRUNRVNRWNRXNRYNRZNSONSPNS"
    "QNSRNSSNQMYRMYSMYTMYUMYVMYWMYXMYYMYZMZNMZOMZPMZQMZRMZSMZTMZUMZVMZWMZXMZYMZ"
    "ZNNNONNPNNQNNRNNSNNTNNUNNVNNWNNXNNYNNZNOONOPNOQNORNOSNOTNOUNOVNOWNWPNWQNWR"
    "NWSNWTNWUNWVNWWNWXNWYNWZNXONXPNXQNXRNXSNXTNXUNXVNXWNXXNXYNXZNYONYPNYQNYRNY"
    "SNYTNYUNYVNYWNYXNYYNYZNZONZPNZQNZRNZSNZTNZUNZVNZWNSTNSUNSVNSWNSXNSYNSZNTON"
    "TPNTQNTRNTSNTTNTUNTVNTWNTXNTYNTZNUONUPNUQNURNUSNUTNUUNUVNUWNUXNUYNUZNVONVP"
    "NVQNVRNVSNVTNVUNVVNVWNVXNVYNVZNWONORXORYORZOSPOSQOSROSSOSTOSUOSVOSWOSXOSYO"
    "SZOTPOTQOTROTSOTTOTUOTVOTWOTXOTYOTZOUPOUQOUROUSOUTOUUOUVOUWOUXOUYOUZOVPOVQ"
    "OVROVSOVTOVUOVVOVWZXNZYNZZOOOPOOQOOROOSOOTOOUOOVOOWOOXOOYOOZOPPOPQOPROPSOP"
    "TOPUOPVOPWOPXOPYOPZOQPOQQOQROQSOQTOQUOQVOQWOQXOQYOQZORPORQORRORSORTORUORVO"
    "RWOZXOZYOZZPPPQPPRPPSPPTPPUPPVPPWPPXPPYPPZPQQPQRPQSPQTPQUPQVPQWPQXPQYPQZPR"
    "QPRRPRSPRTPRUPRVPRWPRXPRYPRZPSQPSRPSSPSTPSUPSVPSWPSXPSYPSZPTOVXOVYOVZOWPOW"
    "QOWROWSOWTOWUOWVOWWOWXOWYOWZOXPOXQOXROXSOXTOXUOXVOXWOXXOXYOXZOYPOYQOYROYSO"
    "YTOYUOYVOYWOYXOYYOYZOZPOZQOZROZSOZTOZUOZVOZWQPTRPTSPTTPTUPTV";

TEST(ZlibTest, DeflateZFixedCorruption) {
  // Tavis's test case from
  // https://www.openwall.com/lists/oss-security/2022/03/26/1
  // The upstream fix,
  // https://github.com/madler/zlib/commit/5c44459c3b28a9bd3283aaceab7c615f8020c531,
  // was merged in Chromium in #583975.

  z_stream stream;
  stream.zalloc = Z_NULL;
  stream.zfree = Z_NULL;

  int level = Z_DEFAULT_COMPRESSION;
  int windowBits = 15;
  int memLevel = 1;
  int strategy = Z_FIXED;

  int ret =
      deflateInit2(&stream, level, Z_DEFLATED, windowBits, memLevel, strategy);
  ASSERT_EQ(ret, Z_OK);
  std::vector<uint8_t> compressed(
      deflateBound(&stream, strlen(zFixedCorruptionData)));
  stream.next_out = compressed.data();
  stream.avail_out = compressed.size();
  stream.next_in = (uint8_t*)zFixedCorruptionData;
  stream.avail_in = strlen(zFixedCorruptionData);
  ret = deflate(&stream, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);
  size_t compressed_sz = compressed.size() - stream.avail_out;
  deflateEnd(&stream);

  std::vector<uint8_t> decompressed(strlen(zFixedCorruptionData));
  ret = inflateInit2(&stream, windowBits);
  ASSERT_EQ(ret, Z_OK);
  stream.next_in = compressed.data();
  stream.avail_in = compressed_sz;
  stream.next_out = decompressed.data();
  stream.avail_out = decompressed.size();
  ret = inflate(&stream, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);
  inflateEnd(&stream);

  EXPECT_EQ(decompressed.size(), strlen(zFixedCorruptionData));
  EXPECT_EQ(
      memcmp(zFixedCorruptionData, decompressed.data(), decompressed.size()),
      0);
}

TEST(ZlibTest, DeflateCopy) {
  // Check that deflateCopy() works.

  z_stream stream1;
  stream1.zalloc = Z_NULL;
  stream1.zfree = Z_NULL;
  int ret =
      deflateInit(&stream1, Z_DEFAULT_COMPRESSION);
  ASSERT_EQ(ret, Z_OK);
  std::vector<uint8_t> compressed(
      deflateBound(&stream1, strlen(zFixedCorruptionData)));
  stream1.next_out = compressed.data();
  stream1.avail_out = compressed.size();

  // Compress the first 1000 bytes.
  stream1.next_in = (uint8_t*)zFixedCorruptionData;
  stream1.avail_in = 1000;
  ret = deflate(&stream1, Z_NO_FLUSH);
  ASSERT_EQ(ret, Z_OK);

  // Copy the stream state.
  z_stream stream2;
  ret = deflateCopy(&stream2, &stream1);
  ASSERT_EQ(ret, Z_OK);
  deflateEnd(&stream1);

  // Compress the remaining bytes.
  stream2.next_in = (uint8_t*)zFixedCorruptionData + (1000 - stream2.avail_in);
  stream2.avail_in = strlen(zFixedCorruptionData) - (1000 - stream2.avail_in);
  ret = deflate(&stream2, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);
  size_t compressed_sz = compressed.size() - stream2.avail_out;
  deflateEnd(&stream2);

  // Check that decompression is successful.
  std::vector<uint8_t> decompressed(strlen(zFixedCorruptionData));
  z_stream stream;
  stream.zalloc = Z_NULL;
  stream.zfree = Z_NULL;
  ret = inflateInit(&stream);
  ASSERT_EQ(ret, Z_OK);
  stream.next_in = compressed.data();
  stream.avail_in = compressed_sz;
  stream.next_out = decompressed.data();
  stream.avail_out = decompressed.size();
  ret = inflate(&stream, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);
  inflateEnd(&stream);

  EXPECT_EQ(decompressed.size(), strlen(zFixedCorruptionData));
  EXPECT_EQ(
      memcmp(zFixedCorruptionData, decompressed.data(), decompressed.size()),
      0);
}

TEST(ZlibTest, GzipStored) {
  // Check that deflating uncompressed blocks with a gzip header doesn't write
  // out of bounds (crbug.com/325990053).
  z_stream stream;
  stream.zalloc = Z_NULL;
  stream.zfree = Z_NULL;
  static const int kGzipWrapper = 16;
  int ret = deflateInit2(&stream, Z_NO_COMPRESSION, Z_DEFLATED,
                         9 + kGzipWrapper, 9, Z_DEFAULT_STRATEGY);
  ASSERT_EQ(ret, Z_OK);

  const std::vector<uint8_t> src(512 * 1024);
  stream.next_in = (unsigned char*)src.data();
  stream.avail_in = src.size();

  std::vector<uint8_t> out(1000);
  stream.next_out = (unsigned char*)out.data();
  stream.avail_out = out.size();

  ret = deflate(&stream, Z_NO_FLUSH);
  ASSERT_EQ(ret, Z_OK);

  deflateEnd(&stream);
}

TEST(ZlibTest, DeflateBound) {
  // Check that the deflateBound() isn't too low when using non-default
  // parameters (crbug.com/40270738).
  const int level = 9;
  const int windowBits = 15;
  const int memLevel = 1;
  const int strategy = Z_FIXED;
  const uint8_t src[] = {
      49,  255, 255, 20,  45,  49,  167, 56,  55,  255, 255, 255, 223, 255, 49,
      255, 3,   78,  0,   0,   141, 253, 209, 163, 29,  195, 43,  60,  199, 123,
      112, 35,  134, 13,  148, 102, 212, 4,   184, 103, 7,   102, 225, 102, 156,
      164, 78,  48,  70,  49,  125, 162, 55,  116, 161, 174, 83,  0,   59,  0,
      225, 140, 0,   0,   63,  63,  4,   15,  198, 30,  126, 196, 33,  99,  135,
      41,  192, 82,  28,  105, 216, 170, 221, 14,  61,  1,   0,   0,   22,  195,
      45,  53,  244, 163, 167, 158, 229, 68,  18,  112, 49,  174, 43,  75,  90,
      161, 85,  19,  36,  163, 118, 228, 169, 180, 161, 237, 234, 253, 197, 234,
      66,  106, 12,  42,  124, 96,  160, 144, 183, 194, 157, 167, 202, 217};

  z_stream stream;
  stream.zalloc = Z_NULL;
  stream.zfree = Z_NULL;
  int ret =
      deflateInit2(&stream, level, Z_DEFLATED, windowBits, memLevel, strategy);
  ASSERT_EQ(ret, Z_OK);
  size_t deflate_bound = deflateBound(&stream, sizeof(src));

  uint8_t out[sizeof(src) * 10];
  stream.next_in = (uint8_t*)src;
  stream.avail_in = sizeof(src);
  stream.next_out = out;
  stream.avail_out = sizeof(out);
  ret = deflate(&stream, Z_FINISH);
  ASSERT_EQ(ret, Z_STREAM_END);

  size_t out_size = sizeof(out) - stream.avail_out;
  EXPECT_LE(out_size, deflate_bound);

  deflateEnd(&stream);
}

// TODO(gustavoa): make these tests run standalone.
#ifndef CMAKE_STANDALONE_UNITTESTS

TEST(ZlibTest, ZipFilenameCommentSize) {
  // Check that minizip rejects zip member filenames or comments longer than
  // the zip format can represent.

  base::ScopedTempDir temp_dir;
  ASSERT_TRUE(temp_dir.CreateUniqueTempDir());
  base::FilePath zip_file = temp_dir.GetPath().AppendASCII("crbug1470539.zip");

  zipFile zf = zipOpen(zip_file.AsUTF8Unsafe().c_str(), APPEND_STATUS_CREATE);
  ASSERT_NE(zf, nullptr);

  // Adding a member with 2^16 byte filename is okay.
  std::string long_filename(UINT16_MAX, 'a');
  EXPECT_EQ(zipOpenNewFileInZip(zf, long_filename.c_str(), nullptr, nullptr, 0,
                                nullptr, 0, nullptr, Z_DEFLATED,
                                Z_DEFAULT_COMPRESSION),
            ZIP_OK);
  EXPECT_EQ(zipWriteInFileInZip(zf, "1", 1), ZIP_OK);
  EXPECT_EQ(zipCloseFileInZip(zf), ZIP_OK);

  // Adding a member with 2^16+1 byte filename is NOT okay.
  std::string too_long_filename = long_filename + 'a';
  EXPECT_EQ(zipOpenNewFileInZip(zf, too_long_filename.c_str(), nullptr, nullptr,
                                0, nullptr, 0, nullptr, Z_DEFLATED,
                                Z_DEFAULT_COMPRESSION),
            ZIP_PARAMERROR);

  // Adding a member with 2^16 byte comment is okay.
  std::string long_comment(UINT16_MAX, 'x');
  EXPECT_EQ(zipOpenNewFileInZip(zf, "x", nullptr, nullptr, 0, nullptr, 0,
                                long_comment.c_str(), Z_DEFLATED,
                                Z_DEFAULT_COMPRESSION),
            ZIP_OK);
  EXPECT_EQ(zipCloseFileInZip(zf), ZIP_OK);

  // Adding a member with 2^16+1 byte comment is NOT okay.
  std::string too_long_comment = long_comment + 'x';
  EXPECT_EQ(zipOpenNewFileInZip(zf, "x", nullptr, nullptr, 0, nullptr, 0,
                                too_long_comment.c_str(), Z_DEFLATED,
                                Z_DEFAULT_COMPRESSION),
            ZIP_PARAMERROR);

  EXPECT_EQ(zipClose(zf, nullptr), ZIP_OK);

  // Check that the long filename and comment members were successfully added.
  unzFile uzf = unzOpen(zip_file.AsUTF8Unsafe().c_str());
  ASSERT_NE(uzf, nullptr);
  char buf[UINT16_MAX + 2];

  ASSERT_EQ(unzGoToFirstFile(uzf), UNZ_OK);
  ASSERT_EQ(unzGetCurrentFileInfo(uzf, nullptr, buf, sizeof(buf), nullptr, 0,
                                  nullptr, 0),
            UNZ_OK);
  EXPECT_EQ(std::string(buf), long_filename);

  ASSERT_EQ(unzGoToNextFile(uzf), UNZ_OK);
  ASSERT_EQ(unzGetCurrentFileInfo(uzf, nullptr, nullptr, 0, nullptr, 0, buf,
                                  sizeof(buf)),
            UNZ_OK);
  EXPECT_EQ(std::string(buf), long_comment);

  EXPECT_EQ(unzGoToNextFile(uzf), UNZ_END_OF_LIST_OF_FILE);
  EXPECT_EQ(unzClose(uzf), UNZ_OK);
}

TEST(ZlibTest, ZipExtraFieldSize) {
  // Check that minizip rejects zip members with too large extra fields.

  std::string extra_field;
  extra_field.append("\x12\x34");  // Header ID.
  extra_field.append("\xfb\xff");  // Data size (not including the header).
  extra_field.append(UINT16_MAX - 4, 'a');

  base::ScopedTempDir temp_dir;
  ASSERT_TRUE(temp_dir.CreateUniqueTempDir());
  base::FilePath zip_file = temp_dir.GetPath().AppendASCII("extrafield.zip");

  zipFile zf = zipOpen(zip_file.AsUTF8Unsafe().c_str(), APPEND_STATUS_CREATE);
  ASSERT_NE(zf, nullptr);

  // Adding a member with 2^16 byte extra field should work.
  EXPECT_EQ(zipOpenNewFileInZip(zf, "a", nullptr, extra_field.data(),
                                extra_field.size(), extra_field.data(),
                                extra_field.size(), nullptr, Z_DEFLATED,
                                Z_DEFAULT_COMPRESSION),
            ZIP_OK);
  EXPECT_EQ(zipWriteInFileInZip(zf, "1", 1), ZIP_OK);
  EXPECT_EQ(zipCloseFileInZip(zf), ZIP_OK);

  // More then 2^16 bytes doesn't work. Neither for size_extrafield_local, nor
  // size_extrafield_global.
  std::string extra_field_long = extra_field + 'x';
  EXPECT_EQ(
      zipOpenNewFileInZip(zf, "b", nullptr, nullptr, 0, extra_field_long.data(),
                          extra_field_long.size(), nullptr, Z_DEFLATED,
                          Z_DEFAULT_COMPRESSION),
      ZIP_PARAMERROR);
  EXPECT_EQ(zipOpenNewFileInZip(zf, "b", nullptr, extra_field_long.data(),
                                extra_field_long.size(), nullptr, 0, nullptr,
                                Z_DEFLATED, Z_DEFAULT_COMPRESSION),
            ZIP_PARAMERROR);

  EXPECT_EQ(zipClose(zf, nullptr), ZIP_OK);

  // Check that the data can be read back.
  unzFile uzf = unzOpen(zip_file.AsUTF8Unsafe().c_str());
  ASSERT_NE(uzf, nullptr);
  char buf[UINT16_MAX + 1] = {0};

  ASSERT_EQ(unzGoToFirstFile(uzf), UNZ_OK);
  ASSERT_EQ(unzGetCurrentFileInfo(uzf, nullptr, nullptr, 0, buf,
                                  sizeof(buf) - 1, nullptr, 0),
            UNZ_OK);
  EXPECT_EQ(std::string(buf), extra_field);

  EXPECT_EQ(unzGoToNextFile(uzf), UNZ_END_OF_LIST_OF_FILE);
  EXPECT_EQ(unzClose(uzf), UNZ_OK);
}

static base::FilePath TestDataDir() {
  base::FilePath path;
  bool success = base::PathService::Get(base::DIR_SRC_TEST_DATA_ROOT, &path);
  EXPECT_TRUE(success);
  return path
      .AppendASCII("third_party")
      .AppendASCII("zlib")
      .AppendASCII("google")
      .AppendASCII("test")
      .AppendASCII("data");
}

TEST(ZlibTest, ZipUnicodePathExtraSizeFilenameOverflow) {
  // This is based on components/test/data/unzip_service/bug953599.zip (added
  // in https://crrev.com/1004132), with the Unicode Path Extra Field's
  // dataSize hex edited to four.
  base::FilePath zip_file = TestDataDir().AppendASCII("unicode_path_extra_overflow.zip");
  unzFile uzf = unzOpen(zip_file.AsUTF8Unsafe().c_str());
  ASSERT_NE(uzf, nullptr);
  EXPECT_EQ(unzGoToFirstFile(uzf), UNZ_ERRNO);
  EXPECT_EQ(unzClose(uzf), UNZ_OK);
}

TEST(ZlibTest, ZipUnicodePathExtra) {
  // This is components/test/data/unzip_service/bug953599.zip (added in
  // https://crrev.com/1004132).
  base::FilePath zip_file = TestDataDir().AppendASCII("unicode_path_extra.zip");
  unzFile uzf = unzOpen(zip_file.AsUTF8Unsafe().c_str());
  ASSERT_NE(uzf, nullptr);

  char long_buf[15], short_buf[3];
  unz_file_info file_info;

  ASSERT_EQ(unzGoToFirstFile(uzf), UNZ_OK);
  ASSERT_EQ(unzGetCurrentFileInfo(uzf, &file_info, long_buf, sizeof(long_buf),
                                  nullptr, 0, nullptr, 0), UNZ_OK);
  ASSERT_EQ(file_info.size_filename, 14);
  ASSERT_EQ(std::string(long_buf), "\xec\x83\x88 \xeb\xac\xb8\xec\x84\x9c.txt");

  // Even if the file name buffer is too short to hold the whole filename, the
  // unicode path extra field should get parsed correctly, size_filename set,
  // and the file name buffer should receive the first bytes.
  ASSERT_EQ(unzGoToFirstFile(uzf), UNZ_OK);
  ASSERT_EQ(unzGetCurrentFileInfo(uzf, &file_info, short_buf, sizeof(short_buf),
                                  nullptr, 0, nullptr, 0), UNZ_OK);
  ASSERT_EQ(file_info.size_filename, 14);
  ASSERT_EQ(std::string(short_buf, sizeof(short_buf)), "\xec\x83\x88");

  // Also with a null filename buffer, the unicode path extra field should get
  // parsed and size_filename set correctly.
  ASSERT_EQ(unzGoToFirstFile(uzf), UNZ_OK);
  ASSERT_EQ(unzGetCurrentFileInfo(uzf, &file_info, nullptr, 0, nullptr, 0,
                                  nullptr, 0), UNZ_OK);
  ASSERT_EQ(file_info.size_filename, 14);

  EXPECT_EQ(unzClose(uzf), UNZ_OK);
}

#endif