xref: /aosp_15_r20/external/zlib/contrib/tests/utils_unittest.cc (revision 86ee64e75fa5f8bce2c8c356138035642429cd05) 
1 // Copyright 2020 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the Chromium source repository LICENSE file.
4 
5 #include "infcover.h"
6 
7 #include <cstddef>
8 #include <vector>
9 
10 #include "compression_utils_portable.h"
11 #include "gtest.h"
12 
13 #if !defined(CMAKE_STANDALONE_UNITTESTS)
14 #include "base/files/file_path.h"
15 #include "base/files/scoped_temp_dir.h"
16 
17 #include "third_party/zlib/contrib/minizip/unzip.h"
18 #include "third_party/zlib/contrib/minizip/zip.h"
19 #endif
20 
21 #include "zlib.h"
22 
TestPayloads(size_t input_size,zlib_internal::WrapperType type,const int compression_level=Z_DEFAULT_COMPRESSION)23 void TestPayloads(size_t input_size, zlib_internal::WrapperType type,
24                   const int compression_level = Z_DEFAULT_COMPRESSION) {
25   std::vector<unsigned char> input;
26   input.reserve(input_size);
27   for (size_t i = 1; i <= input_size; ++i)
28     input.push_back(i & 0xff);
29 
30   // If it is big enough for GZIP, will work for other wrappers.
31   std::vector<unsigned char> compressed(
32       zlib_internal::GzipExpectedCompressedSize(input.size()));
33   std::vector<unsigned char> decompressed(input.size());
34 
35   // Libcores's java/util/zip/Deflater default settings: ZLIB,
36   // DEFAULT_COMPRESSION and DEFAULT_STRATEGY.
37   unsigned long compressed_size = static_cast<unsigned long>(compressed.size());
38   int result = zlib_internal::CompressHelper(
39       type, compressed.data(), &compressed_size, input.data(), input.size(),
40       compression_level, nullptr, nullptr);
41   ASSERT_EQ(result, Z_OK);
42 
43   unsigned long decompressed_size =
44       static_cast<unsigned long>(decompressed.size());
45   result = zlib_internal::UncompressHelper(type, decompressed.data(),
46                                            &decompressed_size,
47                                            compressed.data(), compressed_size);
48   ASSERT_EQ(result, Z_OK);
49   EXPECT_EQ(input, decompressed);
50 }
51 
TEST(ZlibTest,ZlibWrapper)52 TEST(ZlibTest, ZlibWrapper) {
53   // Minimal ZLIB wrapped short stream size is about 8 bytes.
54   for (size_t i = 1; i < 1024; ++i)
55     TestPayloads(i, zlib_internal::WrapperType::ZLIB);
56 }
57 
TEST(ZlibTest,GzipWrapper)58 TEST(ZlibTest, GzipWrapper) {
59   // GZIP should be 12 bytes bigger than ZLIB wrapper.
60   for (size_t i = 1; i < 1024; ++i)
61     TestPayloads(i, zlib_internal::WrapperType::GZIP);
62 }
63 
TEST(ZlibTest,RawWrapper)64 TEST(ZlibTest, RawWrapper) {
65   // RAW has no wrapper (V8 Blobs is a known user), size
66   // should be payload_size + 2 for short payloads.
67   for (size_t i = 1; i < 1024; ++i)
68     TestPayloads(i, zlib_internal::WrapperType::ZRAW);
69 }
70 
TEST(ZlibTest,LargePayloads)71 TEST(ZlibTest, LargePayloads) {
72   static const size_t lengths[] = { 6000, 8000, 10'000, 15'000, 20'000, 30'000,
73                                     50'000, 100'000, 150'000, 2'500'000,
74                                     5'000'000, 10'000'000, 20'000'000 };
75 
76   for (size_t length: lengths) {
77     TestPayloads(length, zlib_internal::WrapperType::ZLIB);
78     TestPayloads(length, zlib_internal::WrapperType::GZIP);
79   }
80 }
81 
TEST(ZlibTest,CompressionLevels)82 TEST(ZlibTest, CompressionLevels) {
83   static const int levels[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
84   for (int level: levels) {
85     TestPayloads(5'000'000, zlib_internal::WrapperType::ZLIB, level);
86     TestPayloads(5'000'000, zlib_internal::WrapperType::GZIP, level);
87   }
88 }
89 
TEST(ZlibTest,InflateCover)90 TEST(ZlibTest, InflateCover) {
91   cover_support();
92   cover_wrap();
93   cover_back();
94   cover_inflate();
95   // TODO(cavalcantii): enable this last test.
96   // cover_trees();
97   cover_fast();
98 }
99 
TEST(ZlibTest,InflateCVE)100 TEST(ZlibTest, InflateCVE) {
101   cover_CVE_2022_37434();
102 }
103 
TEST(ZlibTest,DeflateStored)104 TEST(ZlibTest, DeflateStored) {
105   const int no_compression = 0;
106   const zlib_internal::WrapperType type = zlib_internal::WrapperType::GZIP;
107   std::vector<unsigned char> input(1 << 10, 42);
108   std::vector<unsigned char> compressed(
109       zlib_internal::GzipExpectedCompressedSize(input.size()));
110   std::vector<unsigned char> decompressed(input.size());
111   unsigned long compressed_size = static_cast<unsigned long>(compressed.size());
112   int result = zlib_internal::CompressHelper(
113       type, compressed.data(), &compressed_size, input.data(), input.size(),
114       no_compression, nullptr, nullptr);
115   ASSERT_EQ(result, Z_OK);
116 
117   unsigned long decompressed_size =
118       static_cast<unsigned long>(decompressed.size());
119   result = zlib_internal::UncompressHelper(type, decompressed.data(),
120                                            &decompressed_size,
121                                            compressed.data(), compressed_size);
122   ASSERT_EQ(result, Z_OK);
123   EXPECT_EQ(input, decompressed);
124 }
125 
TEST(ZlibTest,StreamingInflate)126 TEST(ZlibTest, StreamingInflate) {
127   uint8_t comp_buf[4096], decomp_buf[4096];
128   z_stream comp_strm, decomp_strm;
129   int ret;
130 
131   std::vector<uint8_t> src;
132   for (size_t i = 0; i < 1000; i++) {
133     for (size_t j = 0; j < 40; j++) {
134       src.push_back(j);
135     }
136   }
137 
138   // Deflate src into comp_buf.
139   comp_strm.zalloc = Z_NULL;
140   comp_strm.zfree = Z_NULL;
141   comp_strm.opaque = Z_NULL;
142   ret = deflateInit(&comp_strm, Z_BEST_COMPRESSION);
143   ASSERT_EQ(ret, Z_OK);
144   comp_strm.next_out = comp_buf;
145   comp_strm.avail_out = sizeof(comp_buf);
146   comp_strm.next_in = src.data();
147   comp_strm.avail_in = src.size();
148   ret = deflate(&comp_strm, Z_FINISH);
149   ASSERT_EQ(ret, Z_STREAM_END);
150   size_t comp_sz = sizeof(comp_buf) - comp_strm.avail_out;
151 
152   // Inflate comp_buf one 4096-byte buffer at a time.
153   decomp_strm.zalloc = Z_NULL;
154   decomp_strm.zfree = Z_NULL;
155   decomp_strm.opaque = Z_NULL;
156   ret = inflateInit(&decomp_strm);
157   ASSERT_EQ(ret, Z_OK);
158   decomp_strm.next_in = comp_buf;
159   decomp_strm.avail_in = comp_sz;
160 
161   while (decomp_strm.avail_in > 0) {
162     decomp_strm.next_out = decomp_buf;
163     decomp_strm.avail_out = sizeof(decomp_buf);
164     ret = inflate(&decomp_strm, Z_FINISH);
165     ASSERT_TRUE(ret == Z_OK || ret == Z_STREAM_END || ret == Z_BUF_ERROR);
166 
167     // Verify the output bytes.
168     size_t num_out = sizeof(decomp_buf) - decomp_strm.avail_out;
169     for (size_t i = 0; i < num_out; i++) {
170       EXPECT_EQ(decomp_buf[i], src[decomp_strm.total_out - num_out + i]);
171     }
172   }
173 
174   // Cleanup memory (i.e. makes ASAN bot happy).
175   ret = deflateEnd(&comp_strm);
176   EXPECT_EQ(ret, Z_OK);
177   ret = inflateEnd(&decomp_strm);
178   EXPECT_EQ(ret, Z_OK);
179 }
180 
TEST(ZlibTest,CRCHashBitsCollision)181 TEST(ZlibTest, CRCHashBitsCollision) {
182   // The CRC32c of the hex sequences 2a,14,14,14 and 2a,14,db,14 have the same
183   // lower 9 bits. Since longest_match doesn't check match[2], a bad match could
184   // be chosen when the number of hash bits is <= 9. For this reason, the number
185   // of hash bits must be set higher, regardless of the memlevel parameter, when
186   // using CRC32c hashing for string matching. See https://crbug.com/1113596
187 
188   std::vector<uint8_t> src = {
189       // Random byte; zlib doesn't match at offset 0.
190       123,
191 
192       // This will look like 5-byte match.
193       0x2a,
194       0x14,
195       0xdb,
196       0x14,
197       0x15,
198 
199       // Offer a 4-byte match to bump the next expected match length to 5.
200       0x2a,
201       0x14,
202       0x14,
203       0x14,
204 
205       0x2a,
206       0x14,
207       0x14,
208       0x14,
209       0x15,
210   };
211 
212   z_stream stream;
213   stream.zalloc = nullptr;
214   stream.zfree = nullptr;
215 
216   // Using a low memlevel to try to reduce the number of hash bits. Negative
217   // windowbits means raw deflate, i.e. without the zlib header.
218   int ret = deflateInit2(&stream, /*comp level*/ 2, /*method*/ Z_DEFLATED,
219                          /*windowbits*/ -15, /*memlevel*/ 2,
220                          /*strategy*/ Z_DEFAULT_STRATEGY);
221   ASSERT_EQ(ret, Z_OK);
222   std::vector<uint8_t> compressed(100, '\0');
223   stream.next_out = compressed.data();
224   stream.avail_out = compressed.size();
225   stream.next_in = src.data();
226   stream.avail_in = src.size();
227   ret = deflate(&stream, Z_FINISH);
228   ASSERT_EQ(ret, Z_STREAM_END);
229   compressed.resize(compressed.size() - stream.avail_out);
230   deflateEnd(&stream);
231 
232   ret = inflateInit2(&stream, /*windowbits*/ -15);
233   ASSERT_EQ(ret, Z_OK);
234   std::vector<uint8_t> decompressed(src.size(), '\0');
235   stream.next_in = compressed.data();
236   stream.avail_in = compressed.size();
237   stream.next_out = decompressed.data();
238   stream.avail_out = decompressed.size();
239   ret = inflate(&stream, Z_FINISH);
240   ASSERT_EQ(ret, Z_STREAM_END);
241   EXPECT_EQ(0U, stream.avail_out);
242   inflateEnd(&stream);
243 
244   EXPECT_EQ(src, decompressed);
245 }
246 
TEST(ZlibTest,CRCHashAssert)247 TEST(ZlibTest, CRCHashAssert) {
248   // The CRC32c of the hex sequences ff,ff,5e,6f and ff,ff,13,ff have the same
249   // lower 15 bits. This means longest_match's assert that match[2] == scan[2]
250   // won't hold. However, such hash collisions are only possible when one of the
251   // other four bytes also mismatch. This tests that zlib's assert handles this
252   // case.
253 
254   std::vector<uint8_t> src = {
255       // Random byte; zlib doesn't match at offset 0.
256       123,
257 
258       // This has the same hash as the last byte sequence, and the first two and
259       // last two bytes match; though the third and the fourth don't.
260       0xff,
261       0xff,
262       0x5e,
263       0x6f,
264       0x12,
265       0x34,
266 
267       // Offer a 5-byte match to bump the next expected match length to 6
268       // (because the two first and two last bytes need to match).
269       0xff,
270       0xff,
271       0x13,
272       0xff,
273       0x12,
274 
275       0xff,
276       0xff,
277       0x13,
278       0xff,
279       0x12,
280       0x34,
281   };
282 
283   z_stream stream;
284   stream.zalloc = nullptr;
285   stream.zfree = nullptr;
286 
287   int ret = deflateInit2(&stream, /*comp level*/ 5, /*method*/ Z_DEFLATED,
288                          /*windowbits*/ -15, /*memlevel*/ 8,
289                          /*strategy*/ Z_DEFAULT_STRATEGY);
290   ASSERT_EQ(ret, Z_OK);
291   std::vector<uint8_t> compressed(100, '\0');
292   stream.next_out = compressed.data();
293   stream.avail_out = compressed.size();
294   stream.next_in = src.data();
295   stream.avail_in = src.size();
296   ret = deflate(&stream, Z_FINISH);
297   ASSERT_EQ(ret, Z_STREAM_END);
298   compressed.resize(compressed.size() - stream.avail_out);
299   deflateEnd(&stream);
300 
301   ret = inflateInit2(&stream, /*windowbits*/ -15);
302   ASSERT_EQ(ret, Z_OK);
303   std::vector<uint8_t> decompressed(src.size(), '\0');
304   stream.next_in = compressed.data();
305   stream.avail_in = compressed.size();
306   stream.next_out = decompressed.data();
307   stream.avail_out = decompressed.size();
308   ret = inflate(&stream, Z_FINISH);
309   ASSERT_EQ(ret, Z_STREAM_END);
310   EXPECT_EQ(0U, stream.avail_out);
311   inflateEnd(&stream);
312 
313   EXPECT_EQ(src, decompressed);
314 }
315 
316 // Fuzzer generated.
317 static const uint8_t checkMatchCrashData[] = {
318     0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0xc5, 0x00, 0x00, 0x00, 0x00, 0x00,
319     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
320     0x00, 0x00, 0x58, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00,
321     0x00, 0x00, 0x1e, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1f, 0x00,
322     0x6e, 0x6e, 0x6e, 0x00, 0x00, 0x00, 0x00, 0x6e, 0x01, 0x39, 0x6e, 0x6e,
323     0x00, 0x00, 0x00, 0x00, 0xf7, 0xff, 0x00, 0x00, 0x00, 0x00, 0x6e, 0x6e,
324     0x00, 0x00, 0x0a, 0x9a, 0x00, 0x00, 0x6e, 0x6e, 0x6e, 0x2a, 0x00, 0x00,
325     0x00, 0xd5, 0xf0, 0x00, 0x81, 0x02, 0xf3, 0xfd, 0xff, 0xab, 0xf3, 0x6e,
326     0x7e, 0x04, 0x5b, 0xf6, 0x2a, 0x2c, 0xf8, 0x00, 0x54, 0xf3, 0xa5, 0x0e,
327     0xfd, 0x6e, 0xff, 0x00, 0xfd, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
328     0x00, 0xa4, 0x0b, 0xa5, 0x2a, 0x0d, 0x10, 0x01, 0x26, 0xf6, 0x04, 0x0e,
329     0xff, 0x6e, 0x6e, 0x6e, 0x76, 0x00, 0x00, 0x87, 0x01, 0xfe, 0x0d, 0xb6,
330     0x6e, 0x6e, 0xf7, 0x00, 0x00, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
331     0x00, 0x00, 0xfd, 0x00, 0x2a, 0x00, 0x00, 0x00, 0x00, 0x29, 0x00, 0x9b,
332     0x02, 0x00, 0x00, 0x00, 0x00, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a,
333     0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x6e, 0xff, 0xff, 0x00,
334     0x00, 0xd5, 0xf0, 0x00, 0xff, 0x40, 0x7e, 0x0b, 0xa5, 0x10, 0x67, 0x01,
335     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x58, 0x00, 0x00,
336     0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1e, 0x00, 0x00,
337     0x00, 0x00, 0x00, 0x00, 0x00, 0x1f, 0x40, 0x7e, 0x0b, 0xa5, 0x10, 0x67,
338     0x7e, 0x32, 0x6e, 0x00, 0x00, 0x00, 0x3c, 0x00, 0x00, 0x40, 0x0b, 0xa5,
339     0x10, 0x67, 0x01, 0xfe, 0x0d, 0xb6, 0x2a, 0x00, 0x00, 0x58, 0x00, 0x00,
340     0x00, 0x00, 0x00, 0x00, 0x6e, 0xfd, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
341     0x00, 0x00, 0x3d, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3d, 0x00, 0x00,
342     0x00, 0x00, 0x00, 0x00, 0xd6, 0x2d, 0x2d, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a,
343     0x8a, 0x8a, 0x8a, 0x8a, 0x66, 0x8a, 0x8a, 0x8a, 0xee, 0x1d, 0x00, 0x00,
344     0x00, 0x02, 0x00, 0x00, 0x00, 0xee, 0x0a, 0x00, 0x00, 0x00, 0x54, 0x40,
345     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
346     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
347     0x00, 0x00, 0x00, 0xf3, 0x00, 0x00, 0xff, 0xff, 0x23, 0x7e, 0x00, 0x1e,
348     0x00, 0x00, 0xd5, 0xf0, 0x00, 0xff, 0x40, 0x0b, 0xa5, 0x10, 0x67, 0x01,
349     0xfe, 0x0d, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a,
350     0x8a, 0x8a, 0x8a, 0x2d, 0x6e, 0x2d, 0x00, 0x00, 0x00, 0x00, 0x0e, 0x0e,
351     0xfb, 0x00, 0x10, 0x24, 0x00, 0x00, 0xfb, 0xff, 0x00, 0x00, 0xff, 0x1f,
352     0xb3, 0x00, 0x04, 0x3d, 0x00, 0xee, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
353     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3d, 0x00, 0x00,
354     0x00, 0x00, 0x00, 0x3d, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0e, 0x00, 0x00,
355     0x01, 0x45, 0x3d, 0x00, 0x00, 0x00, 0xfd, 0x00, 0x11, 0x21, 0x00, 0x1e,
356     0x00, 0x0c, 0xb3, 0xfe, 0x0e, 0xee, 0x02, 0x00, 0x1d, 0x00, 0x00, 0x00,
357     0x00, 0x00, 0x6e, 0x6e, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0x6e, 0x00,
358     0x00, 0x87, 0x00, 0x33, 0x38, 0x6e, 0x6e, 0x6e, 0x6e, 0x6e, 0x00, 0x00,
359     0x00, 0x38, 0x00, 0x00, 0xff, 0xff, 0xff, 0x04, 0x3f, 0xff, 0xff, 0xff,
360     0x00, 0x00, 0x00, 0x00, 0xf0, 0x00, 0xff, 0x00, 0x31, 0x13, 0x13, 0x13,
361     0x0b, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xab, 0x30, 0x83, 0x33,
362     0x00, 0x00, 0x01, 0x05, 0x00, 0x00, 0xff, 0xff, 0x7d, 0xff, 0x00, 0x01,
363     0x10, 0x0d, 0x2a, 0xa5, 0x00, 0x00, 0x00, 0x00, 0x00, 0xfd, 0x00, 0x11,
364     0x21, 0x00, 0xa5, 0x00, 0x68, 0x68, 0x68, 0x67, 0x00, 0x00, 0xff, 0xff,
365     0x02, 0x00, 0x00, 0x68, 0x68, 0x68, 0x68, 0x00, 0x00, 0xfa, 0xff, 0xff,
366     0x03, 0x01, 0xff, 0x02, 0x00, 0x00, 0x68, 0x68, 0x68, 0x68, 0x0a, 0x10,
367     0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff,
368     0x06, 0x00, 0x00, 0x2b, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
369     0x00, 0x00, 0xfa, 0xff, 0xff, 0x08, 0xff, 0xff, 0xff, 0x00, 0x06, 0x04,
370     0x00, 0xf8, 0xff, 0xff, 0x00, 0x01, 0x00, 0x00, 0x25, 0x00, 0x00, 0x00,
371     0x00, 0xff, 0x00, 0x00, 0x0b, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
372     0x78, 0x00, 0x00, 0x01, 0x00, 0xff, 0xff, 0xff, 0x00, 0x06, 0x04, 0x6e,
373     0x7e, 0x87, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3d, 0x00, 0x00,
374     0x00, 0x6e, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x87, 0x6e, 0x6e, 0x6e,
375     0x00, 0x01, 0x38, 0xd5, 0xf0, 0x00, 0x00, 0x2a, 0xfe, 0x04, 0x5b, 0x0d,
376     0xfd, 0x6e, 0x92, 0x28, 0xf9, 0xfb, 0xff, 0x07, 0xd2, 0xd6, 0x2d, 0x2d,
377     0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a, 0x8a,
378     0x8a, 0x8a, 0xc2, 0x91, 0x00, 0x5b, 0xef, 0xde, 0xf2, 0x6e, 0x6e, 0xfd,
379     0x0c, 0x02, 0x91, 0x62, 0x91, 0xfd, 0x6e, 0x6e, 0xd3, 0x06, 0x00, 0x00,
380     0x1e, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3f, 0x00,
381     0xd5, 0xf0, 0x00, 0xff, 0x00, 0x00, 0x31, 0x13, 0x13, 0x13, 0x04, 0x00,
382     0x00, 0x00, 0x00, 0x0b, 0x00, 0x00, 0x04, 0x00, 0x13, 0x0a, 0x00, 0x00,
383     0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0x6e, 0x00, 0x00, 0x01,
384     0x00, 0x00, 0x09, 0x00, 0x6a, 0x24, 0x26, 0x30, 0x01, 0x2e, 0x2a, 0xfe,
385     0x04, 0x5b, 0x0d, 0xfd, 0x6e, 0x6e, 0xd7, 0x06, 0x6e, 0x6e, 0x6e, 0x00,
386     0x00, 0xb1, 0xb1, 0xb1, 0xb1, 0x00, 0x00, 0x00, 0x6e, 0x5b, 0x00, 0x00,
387     0x58, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
388     0x58, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x00, 0x00, 0x00, 0x00, 0x00,
389     0x00, 0x00, 0x00, 0x01, 0x05, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
390     0x00, 0x00, 0x58, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
391     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00, 0x00,
392     0x1e, 0x00, 0x00, 0x00, 0x87, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x38,
393     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x6b, 0x00, 0x00, 0x00, 0x00,
394     0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
395     0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
396     0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
397     0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x0b,
398     0x00, 0x00, 0x00, 0x00, 0xff, 0x00, 0x00, 0x24, 0x2a, 0x6e, 0x5c, 0x24,
399     0x00, 0x00, 0x00, 0x0a, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
400     0x00, 0x00, 0x87, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xeb,
401     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x05, 0x00, 0x00, 0x00,
402     0x00, 0x00, 0x40, 0x00, 0x40, 0x00, 0x00, 0x00, 0x58, 0x00, 0x00, 0x00,
403     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x58, 0x00, 0x00, 0x00,
404     0x00, 0x00, 0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
405     0x05, 0x00, 0x00, 0x00, 0x5d, 0x10, 0x6e, 0x6e, 0xa5, 0x2f, 0x00, 0x00,
406     0x95, 0x87, 0x00, 0x6e};
407 
TEST(ZlibTest,CheckMatchCrash)408 TEST(ZlibTest, CheckMatchCrash) {
409   // See https://crbug.com/1113142.
410   z_stream stream;
411   stream.zalloc = nullptr;
412   stream.zfree = nullptr;
413 
414   // Low windowbits to hit window sliding also with a relatively small input.
415   int ret = deflateInit2(&stream, /*comp level*/ 5, /*method*/ Z_DEFLATED,
416                          /*windowbits*/ -9, /*memlevel*/ 8,
417                          /*strategy*/ Z_DEFAULT_STRATEGY);
418   ASSERT_EQ(ret, Z_OK);
419 
420   uint8_t compressed[sizeof(checkMatchCrashData) * 2];
421   stream.next_out = compressed;
422   stream.avail_out = sizeof(compressed);
423 
424   for (size_t i = 0; i < sizeof(checkMatchCrashData); i++) {
425     ASSERT_GT(stream.avail_out, 0U);
426     stream.next_in = (uint8_t*)&checkMatchCrashData[i];
427     stream.avail_in = 1;
428     ret = deflate(&stream, Z_NO_FLUSH);
429     ASSERT_EQ(ret, Z_OK);
430   }
431 
432   stream.next_in = nullptr;
433   stream.avail_in = 0;
434   ASSERT_GT(stream.avail_out, 0U);
435   ret = deflate(&stream, Z_FINISH);
436   ASSERT_EQ(ret, Z_STREAM_END);
437   size_t compressed_sz = sizeof(compressed) - stream.avail_out;
438   deflateEnd(&stream);
439 
440   uint8_t decompressed[sizeof(checkMatchCrashData)];
441   ret = inflateInit2(&stream, -15);
442   ASSERT_EQ(ret, Z_OK);
443   stream.next_in = compressed;
444   stream.avail_in = compressed_sz;
445   stream.next_out = decompressed;
446   stream.avail_out = sizeof(decompressed);
447   ret = inflate(&stream, Z_FINISH);
448   ASSERT_EQ(ret, Z_STREAM_END);
449   inflateEnd(&stream);
450   ASSERT_EQ(
451       memcmp(checkMatchCrashData, decompressed, sizeof(checkMatchCrashData)),
452       0);
453 }
454 
TEST(ZlibTest,DeflateRLEUninitUse)455 TEST(ZlibTest, DeflateRLEUninitUse) {
456   // MSan would complain about use of uninitialized values in deflate_rle if the
457   // window isn't zero-initialized. See crbug.com/1137613. Similar problems
458   // exist in other places in zlib, e.g. longest_match (crbug.com/1144420) but
459   // we don't have as nice test cases.
460 
461   int level = 9;
462   int windowBits = 9;
463   int memLevel = 8;
464   int strategy = Z_RLE;
465   const std::vector<uint8_t> src{
466       0x31, 0x64, 0x38, 0x32, 0x30, 0x32, 0x30, 0x36, 0x65, 0x35, 0x38, 0x35,
467       0x32, 0x61, 0x30, 0x36, 0x65, 0x35, 0x32, 0x66, 0x30, 0x34, 0x38, 0x37,
468       0x61, 0x31, 0x38, 0x36, 0x37, 0x37, 0x31, 0x39, 0x0a, 0x65, 0x62, 0x00,
469       0x9f, 0xff, 0xc6, 0xc6, 0xc6, 0xff, 0x09, 0x00, 0x62, 0x00, 0x9f, 0xff,
470       0xc6, 0xc6, 0xc6, 0xff, 0x09, 0x00, 0x62, 0x00, 0x9f, 0xff, 0xc6, 0xc6,
471       0xc6, 0xff, 0x09, 0x00, 0x62, 0x00, 0x9f, 0xff, 0xc6, 0xc6, 0xc6, 0x95,
472       0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0d, 0x0e, 0x0a, 0x54, 0x52,
473       0x58, 0x56, 0xab, 0x26, 0x13, 0x53, 0x5a, 0xb5, 0x30, 0xbb, 0x96, 0x44,
474       0x80, 0xe6, 0xc5, 0x0a, 0xd0, 0x47, 0x7a, 0xa0, 0x4e, 0xbe, 0x30, 0xdc,
475       0xa1, 0x08, 0x54, 0xe1, 0x51, 0xd1, 0xea, 0xef, 0xdb, 0xa1, 0x2d, 0xb4,
476       0xb9, 0x58, 0xb1, 0x2f, 0xf0, 0xae, 0xbc, 0x07, 0xd1, 0xba, 0x7f, 0x14,
477       0xa4, 0xde, 0x99, 0x7f, 0x4d, 0x3e, 0x25, 0xd9, 0xef, 0xee, 0x4f, 0x38,
478       0x7b, 0xaf, 0x3f, 0x6b, 0x53, 0x5a, 0xcb, 0x1f, 0x97, 0xb5, 0x43, 0xa3,
479       0xe8, 0xff, 0x09, 0x00, 0x62, 0x00, 0x9f, 0xff, 0xc6, 0xc6, 0xc6, 0xff,
480       0x09, 0x00, 0x62, 0x00, 0x9f, 0xff, 0xc6, 0xc6, 0xc6, 0xff, 0x09, 0x00,
481       0x62, 0x00, 0x9f, 0xff, 0xc6, 0xc6, 0xc6, 0xff, 0x09, 0x00, 0x62, 0x00,
482       0x9f, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
483       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
484       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
485       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
486       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
487       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
488       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
489       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
490       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
491       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
492       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
493       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
494       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
495       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
496       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
497       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
498       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
499       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
500       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
501       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
502       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
503       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x3c,
504       0x73, 0x70, 0x23, 0x87, 0xec, 0xf8, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00,
505       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
506       0xc1, 0x00, 0x00, 0x9f, 0xc6, 0xc6, 0xff, 0x09, 0x00, 0x62, 0x00, 0x9f,
507       0xff, 0xc6, 0xc6, 0xc6, 0xff, 0x09, 0x00, 0x62, 0x00, 0x9f, 0xff, 0x00,
508       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
509       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
510       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
511       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
512       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
513       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
514       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
515       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
516       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
517       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
518       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
519       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
520       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
521       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
522       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
523       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
524       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
525       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
526       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
527       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
528       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
529       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x00,
530   };
531 
532   z_stream stream;
533   stream.zalloc = Z_NULL;
534   stream.zfree = Z_NULL;
535 
536   // Compress the data one byte at a time to exercise the streaming code.
537   int ret =
538       deflateInit2(&stream, level, Z_DEFLATED, windowBits, memLevel, strategy);
539   ASSERT_EQ(ret, Z_OK);
540   std::vector<uint8_t> compressed(src.size() * 2 + 1000);
541   stream.next_out = compressed.data();
542   stream.avail_out = compressed.size();
543   for (uint8_t b : src) {
544     stream.next_in = &b;
545     stream.avail_in = 1;
546     ret = deflate(&stream, Z_NO_FLUSH);
547     ASSERT_EQ(ret, Z_OK);
548   }
549   stream.next_in = Z_NULL;
550   stream.avail_in = 0;
551   ret = deflate(&stream, Z_FINISH);
552   ASSERT_EQ(ret, Z_STREAM_END);
553   deflateEnd(&stream);
554 }
555 
556 static const char zFixedCorruptionData[] =
557     "AAABAACAADAAEAAFAAGAAHAAIAAJAAKAALAAMAANAAOAAPAAQAARAASAATAAUAAVAAWAAXAAYA"
558     "AZABBABCABDABEABFABGABHABIABJABKABLABMABNABOABPABQABRABSABTABUABVABWABXABY"
559     "ABZACBACCACDACEACFACGACHACIACJACKACLACMACNACOACPACQACRACSACTACUACVACWACXAC"
560     "YACZADBADCADDADEADFADGADHADIADJADKADLADMADNADOADPADQADRADSADTADUADVADWADXA"
561     "DYADZAEBAECAEDAEEAEFAEGAEHAEIAEJAEKAELAEMAENAEOAEPAEQAERAESAETAEUAEVAEWAEX"
562     "AEYAEZAFBAFCAFDAFEAFFAFGAFHAFIAFJAFKAFLAFMAFNAFOAFPAFQAFRAFSAFTAFUAFVAFWAF"
563     "XAFYAFZAGBAGCAGDAGEAGFAGGAGHAGIAGJAGKAGLAGMAGNAGOAGPAGQAGRAGSAGTAGUAGVAGWA"
564     "GXAGYAGZAHBAHCAHDAHEAHFAHGAHHAHIAHJAHKAHLAHMAHNAHOAHPAHQAHRAHSAHTAHUAHVAHW"
565     "AHXAHYAHZAIBAICAIDAIEAIFAIGAIHAIIAIJAIKAILAIMAINAIOAIPAIQAIRAISAITAIUAIVAI"
566     "WAIXAIYAIZAJBAJCAJDAJEAJFAJGAJHAJIAJJAJKAJLAJMAJNAJOAJPAJQAJRAJSAJTAJUAJVA"
567     "JWAJXAJYAJZAKBAKCAKDAKEAKFAKGAKHAKIAKJAKKAKLAKMAKNAKOAKPAKQAKRAKSAKTAKUAKV"
568     "AKWAKXAKYAKZALBALCALDALEALFALGALHALIALJALKALLALMALNALOALPALQALRALSALTALUAL"
569     "VALWALXALYALZAMBAMCAMDAMEAMFAMGAMHAMIAMJAMKAMLAMMAMNAMOAMPAMQAMRAMSAMTAMUA"
570     "MVAMWAMXAMYAMZANBANCANDANEANFANGANHANIANJANKANLANMANNANOANPANQANRANSANTANU"
571     "ANVANWANXANYANZAOBAOCAODAOEAOFAOGAOHAOIAOJAOKAOLAOMAONAOOAOPAOQAORAOSAOTAO"
572     "UAOVAOWAOXAOYAOZAPBAPCAPDAPEAPFAPGAPHAPIAPJAPKAPLAPMAPNAPOAPPAPQAPRAPSAPTA"
573     "PUAPVAPWAPXAPYAPZAQBAQCAQDAQEAQFAQGAQHAQIAQJAQKAQLAQMAQNAQOAQPAQQAQRAQSAQT"
574     "AQUAQVAQWAQXAQYAQZARBARCARDAREARFARGARHARIARJARKARLARMARNAROARPARQARRARSAR"
575     "TARUARVARWARXARYARZASBASCASDASEASFASGASHASIASJASKASLASMASNASOASPASQASRASSA"
576     "STASUASVASWASXASYASZATBATCATDATEATFATGATHATIATJATKATLATMATNATOATPATQATRATS"
577     "ATTATUATVATWATXATYATZAUBAUCAUDAUEAUFAUGAUHAUIAUJAUKAULAUMAUNAUOAUPAUQAURAU"
578     "SAUTAUUAUVAUWAUXAUYAUZAVBAVCAVDAVEAVFAVGAVHAVIAVJAVKAVLAVMAVNAVOAVPAVQAVRA"
579     "VSAVTAVUAVVAVWAVXAVYAVZAWBAWCAWDAWEAWFAWGAWHAWIAWJAWKAWLAWMAWNAWOAWPAWQAWR"
580     "AWSAWTAWUAWVAWWAWXAWYAWZAXBAXCAXDAXEAXFAXGAXHAXIAXJAXKAXLAXMAXNAXOAXPAXQAX"
581     "RAXSAXTAXUAXVAXWAXXAXYAXZAYBAYCAYDAYEAYFAYGAYHAYIAYJAYKAYLAYMAYNAYOAYPAYQA"
582     "YRAYSAYTAYUAYVAYWAYXAYYAYZAZBAZCAZDAZEAZFAZGAZHAZIAZJAZKAZLAZMAZNAZOAZPAZQ"
583     "AZRAZSAZTAZUAZVAZWAZXAZYAZZBBBCBBDBBEBBFBBGBBHBBIBBJBBKBBLBBMBBNBBOBBPBBQB"
584     "BRBBSBBTBBUBBVBBWBBXBBYBBZBCCBCDBCEBCFBCGBCHBCIBCJBCKBCLBCMBCNBCOBCPBCQBCR"
585     "BCSBCTBCUBCVBCWBCXBCYBCZBDCBDDBDEBDFBDGBDHBDIBDJBDKBDLBDMBDNBDOBDPBDQBDRBD"
586     "SBDTBDUBDVBDWBDXBDYBDZBECBEDBEEBEFBEGBEHBEIBEJBEKBELBEMBENBEOBEPBEQBERBESB"
587     "ETBEUBEVBEWBEXBEYBEZBFCBFDBFEBFFBFGBFHBFIBFJBFKBFLBFMBFNBFOBFPBFQBFRBFSBFT"
588     "BFUBFVBFWBFXBFYBFZBGCBGDBGEBGFBGGBGHBGIBGJBGKBGLBGMBGNBGOBGPBGQBGRBGSBGTBG"
589     "UBGVBGWBGXBGYBGZBHCBHDBHEBHFBHGBHHBHIBHJBHKBHLBHMBHNBHOBHPBHQBHRBHSBHTBHUB"
590     "HVBHWBHXBHYBHZBICBIDBIEBIFBIGBIHBIIBIJBIKBILBIMBINBIOBIPBIQBIRBISBITBIUBIV"
591     "BIWBIXBIYBIZBJCBJDBJEBJFBJGBJHBJIBJJBJKBJLBJMBJNBJOBJPBJQBJRBJSBJTBJUBJVBJ"
592     "WBJXBJYBJZBKCBKDBKEBKFBKGBKHBKIBKJBKKBKLBKMBKNBKOBKPBKQBKRBKSBKTBKUBKVBKWB"
593     "KXBKYBKZBLCBLDBLEBLFBLGBLHBLIBLJBLKBLLBLMBLNBLOBLPBLQBLRBLSBLTBLUBLVBLWBLX"
594     "BLYBLZBMCBMDBMEBMFBMGBMHBMIBMJBMKBMLBMMBMNBMOBMPBMQBMRBMSBMTBMUBMVBMWBMXBM"
595     "YBMZBNCBNDBNEBNFBNGBNHBNIBNJBNKBNLBNMBNNBNOBNPBNQBNRBNSBNTBNUBNVBNWBNXBNYB"
596     "NZBOCBODBOEBOFBOGBOHBOIBOJBOKBOLBOMBONBOOBOPBOQBORBOSBOTBOUBOVBOWBOXBOYBOZ"
597     "BPCBPDBPEBPFBPGBPHBPIBPJBPKBPLBPMBPNBPOBPPBPQBPRBPSBPTBPUBPVBPWBPXBPYBPZBQ"
598     "CBQDBQEBQFBQGBQHBQIBQJBQKBQLBQMBQNBQOBQPBQQBQRBQSBQTBQUBQVBQWBQXBQYBQZBRCB"
599     "RDBREBRFBRGBRHBRIBRJBRKBRLBRMBRNBROBRPBRQBRRBRSBRTBRUBRVBRWBRXBRYBRZBSCBSD"
600     "BSEBSFBSGBSHBSIBSJBSKBSLBSMBSNBSOBSPBSQBSRBSSBSTBSUBSVBSWBSXBSYBSZBTCBTDBT"
601     "EBTFBTGBTHBTIBTJBTKBTLBTMBTNBTOBTPBTQBTRBTSBTTBTUBTVBTWBTXBTYBTZBUCBUDBUEB"
602     "UFBUGBUHBUIBUJBUKBULBUMBUNBUOBUPBUQBURBUSBUTBUUBUVBUWBUXBUYBUZBVCBVDBVEBVF"
603     "BVGBVHBVIBVJBVKBVLBVMBVNBVOBVPBVQBVRBVSBVTBVUBVVBVWBVXBVYBVZBWCBWDBWEBWFBW"
604     "GBWHBWIBWJBWKBWLBWMBWNBWOBWPBWQBWRBWSBWTBWUBWVBWWBWXBWYBWZBXCBXDBXEBXFBXGB"
605     "XHBXIBXJBXKBXLBXMBXNBXOBXPBXQBXRBXSBXTBXUBXVBXWBXXBXYBXZBYCBYDBYEBYFBYGBYH"
606     "BYIBYJBYKBYLBYMBYNBYOBYPBYQBYRBYSBYTBYUBYVBYWBYXBYYBYZBZCBZDBZEBZFBZGBZHBZ"
607     "IBZJBZKBZLBZMBZNBZOBZPBZQBZRBZSBZTBZUBZVBZWBZXBZYBZZCCCDCCECCFCCGCCHCCICCJ"
608     "CCKCCLCCMCCNCCOCCPCCQCCRCCSCCTCCUCCVCCWCCXCCYCCZCDDCDECDFCDGCDHCDICDJCDKCD"
609     "LCDMCDNCDOCDPCDQCDRCDSCDTCDUCDVCDWCDXCDYCDZCEDCEECEFCEGCEHCEICEJCEKCELCEMC"
610     "ENCEOCEPCEQCERCESCETCEUCEVCEWCEXCEYCEZCFDCFECFFCFGCFHCFICFJCFKCFLCFMCFNCFO"
611     "CFPCFQCFRCFSCFTCFUCFVCFWCFXCFYCFZCGDCGECGFCGGCGHCGICGJCGKCGLCGMCGNCGOCGPCG"
612     "QCGRCGSCGTCGUCGVCGWCGXCGYCGZCHDCHECHFCHGCHHCHICHJCHKCHLCHMCHNCHOCHPCHQCHRC"
613     "HSCHTCHUCHVCHWCHXCHYCHZCIDCIECIFCIGCIHCIICIJCIKCILCIMCINCIOCIPCIQCIRCISCIT"
614     "CIUCIVCIWCIXCIYCIZCJDCJECJFCJGCJHCJICJJCJKCJLCJMCJNCJOCJPCJQCJRCJSCJTCJUCJ"
615     "VCJWCJXCJYCJZCKDCKECKFCKGCKHCKICKJCKKCKLCKMCKNCKOCKPCKQCKRCKSCKTCKUCKVCKWC"
616     "KXCKYCKZCLDCLECLFCLGCLHCLICLJCLKCLLCLMCLNCLOCLPCLQCLRCLSCLTCLUCLVCLWCLXCLY"
617     "CLZCMDCMECMFCMGCMHCMICMJCMKCMLCMMCMNCMOCMPCMQCMRCMSCMTCMUCMVCMWCMXCMYCMZCN"
618     "DCNECNFCNGCNHCNICNJCNKCNLCNMCNNCNOCNPCNQCNRCNSCNTCNUCNVCNWCNXCNYCNZCODCOEC"
619     "OFCOGCOHCOICOJCOKCOLCOMCONCOOCOPCOQCORCOSCOTCOUCOVCOWCOXCOYCOZCPDCPECPFCPG"
620     "CPHCPICPJCPKCPLCPMCPNCPOCPPCPQCPRCPSCPTCPUCPVCPWCPXCPYCPZCQDCQECQFCQGCQHCQ"
621     "ICQJCQKCQLCQMCQNCQOCQPCQQCQRCQSCQTCQUCQVCQWCQXCQYCQZCRDCRECRFCRGCRHCRICRJC"
622     "RKCRLCRMCRNCROCRPCRQCRRCRSCRTCRUCRVCRWCRXCRYCRZCSDCSECSFCSGCSHCSICSJCSKCSL"
623     "CSMCSNCSOCSPCSQCSRCSSCSTCSUCSVCSWCSXCSYCSZCTDCTECTFCTGCTHCTICTJCTKCTLCTMCT"
624     "NCTOCTPCTQCTRCTSCTTCTUCTVCTWCTXCTYCTZCUDCUECUFCUGCUHCUICUJCUKCULCUMCUNCUOC"
625     "UPCUQCURCUSCUTCUUCUVCUWCUXCUYCUZCVDCVECVFCVGCVHCVICVJCVKCVLCVMCVNCVOCVPCVQ"
626     "CVRCVSCVTCVUCVVCVWCVXCVYCVZCWDCWECWFCWGCWHCWICWJCWKCWLCWMCWNCWOCWPCWQCWRCW"
627     "SCWTCWUCWVCWWCWXCWYCWZCXDCXECXFCXGCXHCXICXJCXKCXLCXMCXNCXOCXPCXQCXRCXSCXTC"
628     "XUCXVCXWCXXCXYCXZCYDCYECYFCYGCYHCYICYJCYKCYLCYMCYNCYOCYPCYQCYRCYSCYTCYUCYV"
629     "CYWCYXCYYCYZCZDCZECZFCZGCZHCZICZJCZKCZLCZMCZNCZOCZPCZQCZRCZSCZTCZUCZVCZWCZ"
630     "XCZYCZZDDDEDDFDDGDDHDDIDDJDDKDDLDDMDDNDDODDPDDQDDRDDSDDTDDUDDVDDWDDXDDYDDZ"
631     "DEEDEFDEGDEHDEIDEJDEKDELDEMDENDEODEPDEQDERDESDETDEUDEVDEWDEXDEYDEZDFEDFFDF"
632     "GDFHDFIDFJDFKDFLDFMDFNDFODFPDFQDFRDFSDFTDFUDFVDFWDFXDFYDFZDGEDGFDGGDGHDGID"
633     "GJDGKDGLDGMDGNDGODGPDGQDGRDGSDGTDGUDGVDGWDGXDGYDGZDHEDHFDHGDHHDHIDHJDHKDHL"
634     "DHMDHNDHODHPDHQDHRDHSDHTDHUDHVDHWDHXDHYDHZDIEDIFDIGDIHDIIDIJDIKDILDIMDINDI"
635     "ODIPDIQDIRDISDITDIUDIVDIWDIXDIYDIZDJEDJFDJGDJHDJIDJJDJKDJLDJMDJNDJODJPDJQD"
636     "JRDJSDJTDJUDJVDJWDJXDJYDJZDKEDKFDKGDKHDKIDKJDKKDKLDKMDKNDKODKPDKQDKRDKSDKT"
637     "DKUDKVDKWDKXDKYDKZDLEDLFDLGDLHDLIDLJDLKDLLDLMDLNDLODLPDLQDLRDLSDLTDLUDLVDL"
638     "WDLXDLYDLZDMEDMFDMGDMHDMIDMJDMKDMLDMMDMNDMODMPDMQDMRDMSDMTDMUDMVDMWDMXDMYD"
639     "MZDNEDNFDNGDNHDNIDNJDNKDNLDNMDNNDNODNPDNQDNRDNSDNTDNUDNVDNWDNXDNYDNZDOEDOF"
640     "DOGDOHDOIDOJDOKDOLDOMDONDOODOPDOQDORDOSDOTDOUDOVDOWDOXDOYDOZDPEDPFDPGDPHDP"
641     "IDPJDPKDPLDPMDPNDPODPPDPQDPRDPSDPTDPUDPVDPWDPXDPYDPZDQEDQFDQGDQHDQIDQJDQKD"
642     "QLDQMDQNDQODQPDQQDQRDQSDQTDQUDQVDQWDQXDQYDQZDREDRFDRGDRHDRIDRJDRKDRLDRMDRN"
643     "DRODRPDRQDRRDRSDRTDRUDRVDRWDRXDRYDRZDSEDSFDSGDSHDSIDSJDSKDSLDSMDSNDSODSPDS"
644     "QDSRDSSDSTDSUDSVDSWDSXDSYDSZDTEDTFDTGDTHDTIDTJDTKDTLDTMDTNDTODTPDTQDTRDTSD"
645     "TTDTUDTVDTWDTXDTYDTZDUEDUFDUGDUHDUIDUJDUKDULDUMDUNDUODUPDUQDURDUSDUTDUUDUV"
646     "DUWDUXDUYDUZDVEDVFDVGDVHDVIDVJDVKDVLDVMDVNDVODVPDVQDVRDVSDVTDVUDVVDVWDVXDV"
647     "YDVZDWEDWFDWGDWHDWIDWJDWKDWLDWMDWNDWODWPDWQDWRDWSDWTDWUDWVDWWDWXDWYDWZDXED"
648     "XFDXGDXHDXIDXJDXKDXLDXMDXNDXODXPDXQDXRDXSDXTDXUDXVDXWDXXDXYDXZDYEDYFDYGDYH"
649     "DYIDYJDYKDYLDYMDYNDYODYPDYQDYRDYSDYTDYUDYVDYWDYXDYYDYZDZEDZFDZGDZHDZIDZJDZ"
650     "KDZLDZMDZNDZODZPDZQDZRDZSDZTDZUDZVDZWDZXDZYDZZEEEFEEGEEHEEIEEJEEKEELEEMEEN"
651     "EEOEEPEEQEEREESEETEEUEEVEEWEEXEEYEEZEFFEFGEFHEFIEFJEFKEFLEFMEFNEFOEFPEFQEF"
652     "REFSEFTEFUEFVEFWEFXEFYEFZEGFEGGEGHEGIEGJEGKEGLEGMEGNEGOEGPEGQEGREGSEGTEGUE"
653     "GVEGWEGXEGYEGZEHFEHGEHHEHIEHJEHKEHLEHMEHNEHOEHPEHQEHREHSEHTEHUEHVEHWEHXEHY"
654     "EHZEIFEIGEIHEIIEIJEIKEILEIMEINEIOEIPEIQEIREISEITEIUEIVEIWEIXEIYEIZEJFEJGEJ"
655     "HEJIEJJEJKEJLEJMEJNEJOEJPEJQEJREJSEJTEJUEJVEJWEJXEJYEJZEKFEKGEKHEKIEKJEKKE"
656     "KLEKMEKNEKOEKPEKQEKREKSEKTEKUEKVEKWEKXEKYEKZELFELGELHELIELJELKELLELMELNELO"
657     "ELPELQELRELSELTELUELVELWELXELYELZEMFEMGEMHEMIEMJEMKEMLEMMEMNEMOEMPEMQEMREM"
658     "SEMTEMUEMVEMWEMXEMYEMZENFENGENHENIENJENKENLENMENNENOENPENQENRENSENTENUENVE"
659     "NWENXENYENZEOFEOGEOHEOIEOJEOKEOLEOMEONEOOEOPEOQEOREOSEOTEOUEOVEOWEOXEOYEOZ"
660     "EPFEPGEPHEPIEPJEPKEPLEPMEPNEPOEPPEPQEPREPSEPTEPUEPVEPWEPXEPYEPZEQFEQGEQHEQ"
661     "IEQJEQKEQLEQMEQNEQOEQPEQQEQREQSEQTEQUEQVEQWEQXEQYEQZERFERGERHERIERJERKERLE"
662     "RMERNEROERPERQERRERSERTERUERVERWERXERYERZESFESGESHESIESJESKESLESMESNESOESP"
663     "ESQESRESSESTESUESVESWESXESYESZETFETGETHETIETJETKETLETMETNETOETPETQETRETSET"
664     "TETUETVETWETXETYETZEUFEUGEUHEUIEUJEUKEULEUMEUNEUOEUPEUQEUREUSEUTEUUEUVEUWE"
665     "UXEUYEUZEVFEVGEVHEVIEVJEVKEVLEVMEVNEVOEVPEVQEVREVSEVTEVUEVVEVWEVXEVYEVZEWF"
666     "EWGEWHEWIEWJEWKEWLEWMEWNEWOEWPEWQEWREWSEWTEWUEWVEWWEWXEWYEWZEXFEXGEXHEXIEX"
667     "JEXKEXLEXMEXNEXOEXPEXQEXREXSEXTEXUEXVEXWEXXEXYEXZEYFEYGEYHEYIEYJEYKEYLEYME"
668     "YNEYOEYPEYQEYREYSEYTEYUEYVEYWEYXEYYEYZEZFEZGEZHEZIEZJEZKEZLEZMEZNEZOEZPEZQ"
669     "EZREZSEZTEZUEZVEZWEZXEZYEZZFFFGFFHFFIFFJFFKFFLFFMFFNFFOFFPFFQFFRFFSFFTFFUF"
670     "FVFFWFFXFFYFFZFGGFGHFGIFGJFGKFGLFGMFGNFGOFGPFGQFGRFGSFGTFGUFGVFGWFGXFGYFGZ"
671     "FHGFHHFHIFHJFHKFHLFHMFHNFHOFHPFHQFHRFHSFHTFHUFHVFHWFHXFHYFHZFIGFIHFIIFIJFI"
672     "KFILFIMFINFIOFIPFIQFIRFISFITFIUFIVFIWFIXFIYFIZFJGFJHFJIFJJFJKFJLFJMFJNFJOF"
673     "JPFJQFJRFJSFJTFJUFJVFJWFJXFJYFJZFKGFKHFKIFKJFKKFKLFKMFKNFKOFKPFKQFKRFKSFKT"
674     "FKUFKVFKWFKXFKYFKZFLGFLHFLIFLJFLKFLLFLMFLNFLOFLPFLQFLRFLSFLTFLUFLVFLWFLXFL"
675     "YFLZFMGFMHFMIFMJFMKFMLFMMFMNFMOFMPFMQFMRFMSFMTFMUFMVFMWFMXFMYFMZFNGFNHFNIF"
676     "NJFNKFNLFNMFNNFNOFNPFNQFNRFNSFNTFNUFNVFNWFNXFNYFNZFOGFOHFOIFOJFOKFOLFOMFON"
677     "FOOFOPFOQFORFOSFOTFOUFOVFOWFOXFOYFOZFPGFPHFPIFPJFPKFPLFPMFPNFPOFPPFPQFPRFP"
678     "SFPTFPUFPVFPWFPXFPYFPZFQGFQHFQIFQJFQKFQLFQMFQNFQOFQPFQQFQRFQSFQTFQUFQVFQWF"
679     "QXFQYFQZFRGFRHFRIFRJFRKFRLFRMFRNFROFRPFRQFRRFRSFRTFRUFRVFRWFRXFRYFRZFSGFSH"
680     "FSIFSJFSKFSLFSMFSNFSOFSPFSQFSRFSSFSTFSUFSVFSWFSXFSYFSZFTGFTHFTIFTJFTKFTLFT"
681     "MFTNFTOFTPFTQFTRFTSFTTFTUFTVFTWFTXFTYFTZFUGFUHFUIFUJFUKFULFUMFUNFUOFUPFUQF"
682     "URFUSFUTFUUFUVFUWFUXFUYFUZFVGFVHFVIFVJFVKFVLFVMFVNFVOFVPFVQFVRFVSFVTFVUFVV"
683     "FVWFVXFVYFVZFWGFWHFWIFWJFWKFWLFWMFWNFWOFWPFWQFWRFWSFWTFWUFWVFWWFWXFWYFWZFX"
684     "GFXHFXIFXJFXKFXLFXMFXNFXOFXPFXQFXRFXSFXTFXUFXVFXWFXXFXYFXZFYGFYHFYIFYJFYKF"
685     "YLFYMFYNFYOFYPFYQFYRFYSFYTFYUFYVFYWFYXFYYFYZFZGFZHFZIFZJFZKFZLFZMFZNFZOFZP"
686     "FZQFZRFZSFZTFZUFZVFZWFZXFZYFZZGGGHGGIGGJGGKGGLGGMGGNGGOGGPGGQGGRGGSGGTGGUG"
687     "GVGGWGGXGGYGGZGHHGHIGHJGHKGHLGHMGHNGHOGHPGHQGHRGHSGHTGHUGHVGHWGHXGHYGHZGIH"
688     "GIIGIJGIKGILGIMGINGIOGIPGIQGIRGISGITGIUGIVGIWGIXGIYGIZGJHGJIGJJGJKGJLGJMGJ"
689     "NGJOGJPGJQGJRGJSGJTGJUGJVGJWGJXGJYGJZGKHGKIGKJGKKGKLGKMGKNGKOGKPGKQGKRGKSG"
690     "KTGKUGKVGKWGKXGKYGKZGLHGLIGLJGLKGLLGLMGLNGLOGLPGLQGLRGLSGLTGLUGLVGLWGLXGLY"
691     "GLZGMHGMIGMJGMKGMLGMMGMNGMOGMPGMQGMRGMSGMTGMUGMVGMWGMXGMYGMZGNHGNIGNJGNKGN"
692     "LGNMGNNGNOGNPGNQGNRGNSGNTGNUGNVGNWGNXGNYGNZGOHGOIGOJGOKGOLGOMGONGOOGOPGOQG"
693     "ORGOSGOTGOUGOVGOWGOXGOYGOZGPHGPIGPJGPKGPLGPMGPNGPOGPPGPQGPRGPSGPTGPUGPVGPW"
694     "GPXGPYGPZGQHGQIGQJGQKGQLGQMGQNGQOGQPGQQGQRGQSGQTGQUGQVGQWGQXGQYGQZGRHGRIGR"
695     "JGRKGRLGRMGRNGROGRPGRQGRRGRSGRTGRUGRVGRWGRXGRYGRZGSHGSIGSJGSKGSLGSMGSNGSOG"
696     "SPGSQGSRGSSGSTGSUGSVGSWGSXGSYGSZGTHGTIGTJGTKGTLGTMGTNGTOGTPGTQGTRGTSGTTGTU"
697     "GTVGTWGTXGTYGTZGUHGUIGUJGUKGULGUMGUNGUOGUPGUQGURGUSGUTGUUGUVGUWGUXGUYGUZGV"
698     "HGVIGVJGVKGVLGVMGVNGVOGVPGVQGVRGVSGVTGVUGVVGVWGVXGVYGVZGWHGWIGWJGWKGWLGWMG"
699     "WNGWOGWPGWQGWRGWSGWTGWUGWVGWWGWXGWYGWZGXHGXIGXJGXKGXLGXMGXNGXOGXPGXQGXRGXS"
700     "GXTGXUGXVGXWGXXGXYGXZGYHGYIGYJGYKGYLGYMGYNGYOGYPGYQGYRGYSGYTGYUGYVGYWGYXGY"
701     "YGYZGZHGZIGZJGZKGZLGZMGZNGZOGZPGZQGZRGZSGZTGZUGZVGZWGZXGZYGZZHHHIHHJHHKHHL"
702     "HHMHHNHHOHHPHHQHHRHHSHHTHHUHHVHHWHHXHHYHHZHIIHIJHIKHILHIMHINHIOHIPHIQHIRHI"
703     "SHITHIUHIVHIWHIXHIYHIZHJIHJJHJKHJLHJMHJNHJOHJPHJQHJRHJSHJTHJUHJVHJWHJXHJYH"
704     "JZHKIHKJHKKHKLHKMHKNHKOHKPHKQHKRHKSHKTHKUHKVHKWHKXHKYHKZHLIHLJHLKHLLHLMHLN"
705     "HLOHLPHLQHLRHLSHLTHLUHLVHLWHLXHLYHLZHMIHMJHMKHMLHMMHMNHMOHMPHMQHMRHMSHMTHM"
706     "UHMVHMWHMXHMYHMZHNIHNJHNKHNLHNMHNNHNOHNPHNQHNRHNSHNTHNUHNVHNWHNXHNYHNZHOIH"
707     "OJHOKHOLHOMHONHOOHOPHOQHORHOSHOTHOUHOVHOWHOXHOYHOZHPIHPJHPKHPLHPMHPNHPOHPP"
708     "HPQHPRHPSHPTHPUHPVHPWHPXHPYHPZHQIHQJHQKHQLHQMHQNHQOHQPHQQHQRHQSHQTHQUHQVHQ"
709     "WHQXHQYHQZHRIHRJHRKHRLHRMHRNHROHRPHRQHRRHRSHRTHRUHRVHRWHRXHRYHRZHSIHSJHSKH"
710     "SLHSMHSNHSOHSPHSQHSRHSSHSTHSUHSVHSWHSXHSYHSZHTIHTJHTKHTLHTMHTNHTOHTPHTQHTR"
711     "HTSHTTHTUHTVHTWHTXHTYHTZHUIHUJHUKHULHUMHUNHUOHUPHUQHURHUSHUTHUUHUVHUWHUXHU"
712     "YHUZHVIHVJHVKHVLHVMHVNHVOHVPHVQHVRHVSHVTHVUHVVHVWHVXHVYHVZHWIHWJHWKHWLHWMH"
713     "WNHWOHWPHWQHWRHWSHWTHWUHWVHWWHWXHWYHWZHXIHXJHXKHXLHXMHXNHXOHXPHXQHXRHXSHXT"
714     "HXUHXVHXWHXXHXYHXZHYIHYJHYKHYLHYMHYNHYOHYPHYQHYRHYSHYTHYUHYVHYWHYXHYYHYZHZ"
715     "IHZJHZKHZLHZMHZNHZOHZPHZQHZRHZSHZTHZUHZVHZWHZXHZYHZZIIIJIIKIILIIMIINIIOIIP"
716     "IIQIIRIISIITIIUIIVIIWIIXIIYIIZIJJIJKIJLIJMIJNIJOIJPIJQIJRIJSIJTIJUIJVIJWIJ"
717     "XIJYIJZIKJIKKIKLIKMIKNIKOIKPIKQIKRIKSIKTIKUIKVIKWIKXIKYIKZILJILKILLILMILNI"
718     "LOILPILQILRILSILTILUILVILWILXILYILZIMJIMKIMLIMMIMNIMOIMPIMQIMRIMSIMTIMUIMV"
719     "IMWIMXIMYIMZINJINKINLINMINNINOINPINQINRINSINTINUINVINWINXINYINZIOJIOKIOLIO"
720     "MIONIOOIOPIOQIORIOSIOTIOUIOVIOWIOXIOYIOZIPJIPKIPLIPMIPNIPOIPPIPQIPRIPSIPTI"
721     "PUIPVIPWIPXIPYIPZIQJIQKIQLIQMIQNIQOIQPIQQIQRIQSIQTIQUIQVIQWIQXIQYIQZIRJIRK"
722     "IRLIRMIRNIROIRPIRQIRRIRSIRTIRUIRVIRWIRXIRYIRZISJISKISLISMISNISOISPISQISRIS"
723     "SISTISUISVISWISXISYISZITJITKITLITMITNITOITPITQITRITSITTITUITVITWITXITYITZI"
724     "UJIUKIULIUMIUNIUOIUPIUQIURIUSIUTIUUIUVIUWIUXIUYIUZIVJIVKIVLIVMIVNIVOIVPIVQ"
725     "IVRIVSIVTIVUIVVIVWIVXIVYIVZIWJIWKIWLIWMIWNIWOIWPIWQIWRIWSIWTIWUIWVIWWIWXIW"
726     "YIWZIXJIXKIXLIXMIXNIXOIXPIXQIXRIXSIXTIXUIXVIXWIXXIXYIXZIYJIYKIYLIYMIYNIYOI"
727     "YPIYQIYRIYSIYTIYUIYVIYWIYXIYYIYZIZJIZKIZLIZMIZNIZOIZPIZQIZRIZSIZTIZUIZVIZW"
728     "IZXIZYIZZJJJKJJLJJMJJNJJOJJPJJQJJRJJSJJTJJUJJVJJWJJXJJYJJZJKKJKLJKMJKNJKOJ"
729     "KPJKQJKRJKSJKTJKUJKVJKWJKXJKYJKZJLKJLLJLMJLNJLOJLPJLQJLRJLSJLTJLUJLVJLWJLX"
730     "JLYJLZJMKJMLJMMJMNJMOJMPJMQJMRJMSJMTJMUJMVJMWJMXJMYJMZJNKJNLJNMJNNJNOJNPJN"
731     "QJNRJNSJNTJNUJNVJNWJNXJNYJNZJOKJOLJOMJONJOOJOPJOQJORJOSJOTJOUJOVJOWJOXJOYJ"
732     "OZJPKJPLJPMJPNJPOJPPJPQJPRJPSJPTJPUJPVJPWJPXJPYJPZJQKJQLJQMJQNJQOJQPJQQJQR"
733     "JQSJQTJQUJQVJQWJQXJQYJQZJRKJRLJRMJRNJROJRPJRQJRRJRSJRTJRUJRVJRWJRXJRYJRZJS"
734     "KJSLJSMJSNJSOJSPJSQJSRJSSJSTJSUJSVJSWJSXJSYJSZJTKJTLJTMJTNJTOJTPJTQJTRJTSJ"
735     "TTJTUJTVJTWJTXJTYJTZJUKJULJUMJUNJUOJUPJUQJURJUSJUTJUUJUVJUWJUXJUYJUZJVKJVL"
736     "JVMJVNJVOJVPJVQJVRJVSJVTJVUJVVJVWJVXJVYJVZJWKJWLJWMJWNJWOJWPJWQJWRJWSJWTJW"
737     "UJWVJWWJWXJWYJWZJXKJXLJXMJXNJXOJXPJXQJXRJXSJXTJXUJXVJXWJXXJXYJXZJYKJYLJYMJ"
738     "YNJYOJYPJYQJYRJYSJYTJYUJYVJYWJYXJYYJYZJZKJZLJZMJZNJZOJZPJZQJZRJZSJZTJZUJZV"
739     "JZWJZXJZYJZZKKKLKKMKKNKKOKKPKKQKKRKKSKKTKKUKKVKKWKKXKKYKKZKLLKLMKLNKLOKLPK"
740     "LQKLRKLSKLTKLUKLVKLWKLXKLYKLZKMLKMMKMNKMOKMPKMQKMRKMSKMTKMUKMVKMWKMXKMYKMZ"
741     "KNLKNMKNNKNOKNPKNQKNRKNSKNTKNUKNVKNWKNXKNYKNZKOLKOMKONKOOKOPKOQKORKOSKOTKO"
742     "UKOVKOWKOXKOYKOZKPLKPMKPNKPOKPPKPQKPRKPSKPTKPUKPVKPWKPXKPYKPZKQLKQMKQNKQOK"
743     "QPKQQKQRKQSKQTKQUKQVKQWKQXKQYKQZKRLKRMKRNKROKRPKRQKRRKRSKRTKRUKRVKRWKRXKRY"
744     "KRZKSLKSMKSNKSOKSPKSQKSRKSSKSTKSUKSVKSWKSXKSYKSZKTLKTMKTNKTOKTPKTQKTRKTSKT"
745     "TKTUKTVKTWKTXKTYKTZKULKUMKUNKUOKUPKUQKURKUSKUTKUUKUVKUWKUXKUYKUZKVLKVMKVNK"
746     "VOKVPKVQKVRKVSKVTKVUKVVKVWKVXKVYKVZKWLKWMKWNKWOKWPKWQKWRKWSKWTKWUKWVKWWKWX"
747     "KWYKWZKXLKXMKXNKXOKXPKXQKXRKXSKXTKXUKXVKXWKXXKXYKXZKYLKYMKYNKYOKYPKYQKYRKY"
748     "SKYTKYUKYVKYWKYXKYYKYZKZLKZMKZNKZOKZPKZQKZRKZSKZTKZUKZVKZWKZXKZYKZZLLLMLLN"
749     "LLOLLPLLQLLRLLSLLTLLULLVLLWLLXLLYLLZLMMLMNLMOLMPLMQLMRLMSLMTLMULMVLMWLMXLM"
750     "YLMZLNMLNNLNOLNPLNQLNRLNSLNTLNULNVLNWLNXLNYLNZLOMLONLOOLOPLOQLORLOSLOTLOUL"
751     "OVLOWLOXLOYLOZLPMLPNLPOLPPLPQLPRLPSLPTLPULPVLPWLPXLPYLPZLQMLQNLQOLQPLQQLQR"
752     "LQSLQTLQULQVLQWLQXLQYLQZLRMLRNLROLRPLRQLRRLRSLRTLRULRVLRWLRXLRYLRZLSMLSNLS"
753     "OLSPLSQLSRLSSLSTLSULSVLSWLSXLSYLSZLTMLTNLTOLTPLTQLTRLTSLTTLTULTVLTWLTXLTYL"
754     "TZLUMLUNLUOLUPLUQLURLUSLUTLUULUVLUWLUXLUYLUZLVMLVNLVOLVPLVQLVRLVSLVTLVULVV"
755     "LVWLVXLVYLVZLWMLWNLWOLWPLWQLWRLWSLWTLWULWVLWWLWXLWYLWZLXMLXNLXOLXPLXQLXRLX"
756     "SLXTLXULXVLXWLXXLXYLXZLYMLYNLYOLYPLYQLYRLYSLYTLYULYVLYWLYXLYYLYZLZMLZNLZOL"
757     "ZPLZQLZRLZSLZTLZULZVLZWLZXLZYLZZMMMNMMOMMPMMQMMRMMSMMTMMUMMVMMWMMXMMYMMZMN"
758     "NMNOMNPMNQMNRMNSMNTMNUMNVMNWMNXMNYMNZMONMOOMOPMOQMORMOSMOTMOUMOVMOWMOXMOYM"
759     "OZMPNMPOMPPMPQMPRMPSMPTMPUMPVMPWMPXMPYMPZMQNMQOMQPMQQMQRMQSMQTMQUMQVMQWMQX"
760     "MQYMQZMRNMROMRPMRQMRRMRSMRTMRUMRVMRWMRXMRYMRZMSNMSOMSPMSQMSRMSSMSTMSUMSVMS"
761     "WMSXMSYMSZMTNMTOMTPMTQMTRMTSMTTMTUMTVMTWMTXMTYMTZMUNMUOMUPMUQMURMUSMUTMUUM"
762     "UVMUWMUXMUYMUZMVNMVOMVPMVQMVRMVSMVTMVUMVVMVWMVXMVYMVZMWNMWOMWPMWQMWRMWSMWT"
763     "MWUMWVMWWMWXMWYMWZMXNMXOMXPMXQMXRMXSMXTMXUMXVMXWMXXMXYMXZMYNMYOMYPMYQMYRMY"
764     "SMYTMYUMYVMYWMYXMYYMYZMZNMZOMZPMZQMZRMZSMZTMZUMZVMZWMZXMZYMZZNNNONNPNNQNNR"
765     "NNSNNTNNUNNVNNWNNXNNYNNZNOONOPNOQNORNOSNOTNOUNOVNOWNOXNOYNOZNPONPPNPQNPRNP"
766     "SNPTNPUNPVNPWNPXNPYNPZNQONQPNQQNQRNQSNQTNQUNQVNQWNQXNQYNQZNRONRPNRQNRRNRSN"
767     "RTNRUNRVNRWNRXNRYNRZNSONSPNSQNSRNSSNSTNSUNSVNSWNSXNSYNSZNTONTPNTQNTRNTSNTT"
768     "NTUNTVNTWNTXNTYNTZNUONUPNUQNURNUSNUTNUUNUVNUWNUXNUYNUZNVONVPNVQNVRNVSNVTNV"
769     "UNVVNVWNVXNVYNVZNWONWPNWQNWRNWSNWTNWUNWVNWWNWXNWYNWZNXONXPNXQNXRNXSNXTNXUN"
770     "XVNXWNXXNXYNXZNYONYPNYQNYRNYSNYTNYUNYVNYWNYXNYYNYZNZONZPNZQNZRNZSNZTNZUNZV"
771     "NZWNZXNZYNZZOOOPOOQOOROOSOOTOOUOOVOOWOOXOOYOOZOPPOPQOPROPSOPTOPUOPVOPWOPXO"
772     "PYOPZOQPOQQOQROQSOQTOQUOQVOQWOQXOQYOQZORPORQORRORSORTORUORVORWORXORYORZOSP"
773     "OSQOSROSSOSTOSUOSVOSWOSXOSYOSZOTPOTQOTROTSOTTOTUOTVOTWOTXOTYOTZOUPOUQOUROU"
774     "SOUTOUUOUVOUWOUXOUYOUZOVPOVQOVROVSOVTOVUOVVOVWOVXOVYOVZOWPOWQOWROWSOWTOWUO"
775     "WVOWWOWXOWYOWZOXPOXQOXROXSOXTOXUOXVOXWOXXOXYOXZOYPOYQOYROYSOYTOYUOYVOYWOYX"
776     "OYYOYZOZPOZQOZROZSOZTOZUOZVOZWOZXOZYOZZPPPQPPRPPSPPTPPUPPVPPWPPXPPYPPZPQQP"
777     "QRPQSPQTPQUPQVPQWPQXPQYPQZPRQPRRPRSPRTPRUPRVPRWPRXPRYPRZPSQPSRPSSPSTPSUPSV"
778     "PSWPSXPSYPSZPTQPTRPTSPTTPTUPTVTABUABVABWABXABYABZACBACCACDACEACFACGACHACIA"
779     "CJACKACLACMACNACOACPACQACRACSACTACUACVACWACXACYACZADBADCADDADEADFADGADHADI"
780     "ADJADKADLADMADAAABAACAADAAEAAFAAGAAHAAIAAJAAKAALAAMAANAAOAAPAAQAARAASAATAA"
781     "UAAVAAWAAXAAYAAZABBABCABDABEABFABGABHABIABJABKABLABMABNABOABPABQABRABSABHA"
782     "FIAFJAFKAFLAFMAFNAFOAFPAFQAFRAFSAFTAFUAFVAFWAFXAFYAFZAGBAGCAGDAGEAGFAGGAGH"
783     "AGIAGJAGKAGLAGMAGNAGOAGPAGQAGRAGSAGTAGUAGVAGWAGXAGYAGZAHNADOADPADQADRADSAD"
784     "TADUADVADWADXADYADZAEBAECAEDAEEAEFAEGAEHAEIAEJAEKAELAEMAENAEOAEPAEQAERAESA"
785     "ETAEUAEVAEWAEXAEYAEZAFBAFCAFDAFEAFFAFGAFUAIVAIWAIXAIYAIZAJBAJCAJDAJEAJFAJG"
786     "AJHAJIAJJAJKAJLAJMAJNAJOAJPAJQAJRAJSAJTAJUAJVAJWAJXAJYAJZAKBAKCAKDAKEAKFAK"
787     "GAKHAKIAKJAKKAKLAKMAKNAKBAHCAHDAHEAHFAHGAHHAHIAHJAHKAHLAHMAHNAHOAHPAHQAHRA"
788     "HSAHTAHUAHVAHWAHXAHYAHZAIBAICAIDAIEAIFAIGAIHAIIAIJAIKAILAIMAINAIOAIPAIQAIR"
789     "AISAITAIIAMJAMKAMLAMMAMNAMOAMPAMQAMRAMSAMTAMUAMVAMWAMXAMYAMZANBANCANDANEAN"
790     "FANGANHANIANJANKANLANMANNANOANPANQANRANSANTANUANVANWANXANYANZAOBAOOAKPAKQA"
791     "KRAKSAKTAKUAKVAKWAKXAKYAKZALBALCALDALEALFALGALHALIALJALKALLALMALNALOALPALQ"
792     "ALRALSALTALUALVALWALXALYALZAMBAMCAMDAMEAMFAMGAMHAMVAPWAPXAPYAPZAQBAQCAQDAQ"
793     "EAQFAQGAQHAQIAQJAQKAQLAQMAQNAQOAQPAQQAQRAQSAQTAQUAQVAQWAQXAQYAQZARBARCARDA"
794     "REARFARGARHARIARJARKARLARMARNAROARCAODAOEAOFAOGAOHAOIAOJAOKAOLAOMAONAOOAOP"
795     "AOQAORAOSAOTAOUAOVAOWAOXAOYAOZAPBAPCAPDAPEAPFAPGAPHAPIAPJAPKAPLAPMAPNAPOAP"
796     "PAPQAPRAPSAPTAPUAPJATKATLATMATNATOATPATQATRATSATTATUATVATWATXATYATZAUBAUCA"
797     "UDAUEAUFAUGAUHAUIAUJAUKAULAUMAUNAUOAUPAUQAURAUSAUTAUUAUVAUWAUXAUYAUZAVBAVC"
798     "AVPARQARRARSARTARUARVARWARXARYARZASBASCASDASEASFASGASHASIASJASKASLASMASNAS"
799     "OASPASQASRASSASTASUASVASWASXASYASZATBATCATDATEATFATGATHATIATWAWXAWYAWZAXBA"
800     "XCAXDAXEAXFAXGAXHAXIAXJAXKAXLAXMAXNAXOAXPAXQAXRAXSAXTAXUAXVAXWAXXAXYAXZAYB"
801     "AYCAYDAYEAYFAYGAYHAYIAYJAYKAYLAYMAYNAYOAYPAYDAVEAVFAVGAVHAVIAVJAVKAVLAVMAV"
802     "NAVOAVPAVQAVRAVSAVTAVUAVVAVWAVXAVYAVZAWBAWCAWDAWEAWFAWGAWHAWIAWJAWKAWLAWMA"
803     "WNAWOAWPAWQAWRAWSAWTAWUAWVAWBLBBMBBNBBOBBPBBQBBRBBSBBTBBUBBVBBWBBXBBYBBZBC"
804     "CBCDBCEBCFBCGBCHBCIBCJBCKBCLBCMBCNBCOBCPBCQBCRBCSBCTBCUBCVBCWBCXBCYBCZBDCB"
805     "DDBDEBDFBDGBQAYRAYSAYTAYUAYVAYWAYXAYYAYZAZBAZCAZDAZEAZFAZGAZHAZIAZJAZKAZLA"
806     "ZMAZNAZOAZPAZQAZRAZSAZTAZUAZVAZWAZXAZYAZZBBBCBBDBBEBBFBBGBBHBBIBBJBBKBFDBF"
807     "EBFFBFGBFHBFIBFJBFKBFLBFMBFNBFOBFPBFQBFRBFSBFTBFUBFVBFWBFXBFYBFZBGCBGDBGEB"
808     "GFBGGBGHBGIBGJBGKBGLBGMBGNBGOBGPBGQBGRBGSBGTBGUBGVBGWBDHBDIBDJBDKBDLBDMBDN"
809     "BDOBDPBDQBDRBDSBDTBDUBDVBDWBDXBDYBDZBECBEDBEEBEFBEGBEHBEIBEJBEKBELBEMBENBE"
810     "OBEPBEQBERBESBETBEUBEVBEWBEXBEYBEZBFCBITBIUBIVBIWBIXBIYBIZBJCBJDBJEBJFBJGB"
811     "JHBJIBJJBJKBJLBJMBJNBJOBJPBJQBJRBJSBJTBJUBJVBJWBJXBJYBJZBKCBKDBKEBKFBKGBKH"
812     "BKIBKJBKKBKLBKMBKNBKOBGXBGYBGZBHCBHDBHEBHFBHGBHHBHIBHJBHKBHLBHMBHNBHOBHPBH"
813     "QBHRBHSBHTBHUBHVBHWBHXBHYBHZBICBIDBIEBIFBIGBIHBIIBIJBIKBILBIMBINBIOBIPBIQB"
814     "IRBISBMLBMMBMNBMOBMPBMQBMRBMSBMTBMUBMVBMWBMXBMYBMZBNCBNDBNEBNFBNGBNHBNIBNJ"
815     "BNKBNLBNMBNNBNOBNPBNQBNRBNSBNTBNUBNVBNWBNXBNYBNZBOCBODBOEBOFBOGBKPBKQBKRBK"
816     "SBKTBKUBKVBKWBKXBKYBKZBLCBLDBLEBLFBLGBLHBLIBLJBLKBLLBLMBLNBLOBLPBLQBLRBLSB"
817     "LTBLUBLVBLWBLXBLYBLZBMCBMDBMEBMFBMGBMHBMIBMJBMKBQDBQEBQFBQGBQHBQIBQJBQKBQL"
818     "BQMBQNBQOBQPBQQBQRBQSBQTBQUBQVBQWBQXBQYBQZBRCBRDBREBRFBRGBRHBRIBRJBRKBRLBR"
819     "MBRNBROBRPBRQBRRBRSBRTBRUBRVBRWBOHBOIBOJBOKBOLBOMBONBOOBOPBOQBORBOSBOTBOUB"
820     "OVBOWBOXBOYBOZBPCBPDBPEBPFBPGBPHBPIBPJBPKBPLBPMBPNBPOBPPBPQBPRBPSBPTBPUBPV"
821     "BPWBPXBPYBPZBQCBTTBTUBTVBTWBTXBTYBTZBUCBUDBUEBUFBUGBUHBUIBUJBUKBULBUMBUNBU"
822     "OBUPBUQBURBUSBUTBUUBUVBUWBUXBUYBUZBVCBVDBVEBVFBVGBVHBVIBVJBVKBVLBVMBVNBVOB"
823     "RXBRYBRZBSCBSDBSEBSFBSGBSHBSIBSJBSKBSLBSMBSNBSOBSPBSQBSRBSSBSTBSUBSVBSWBSX"
824     "BSYBSZBTCBTDBTEBTFBTGBTHBTIBTJBTKBTLBTMBTNBTOBTPBTQBTRBTSBXLBXMBXNBXOBXPBX"
825     "QBXRBXSBXTBXUBXVBXWBXXBXYBXZBYCBYDBYEBYFBYGBYHBYIBYJBYKBYLBYMBYNBYOBYPBYQB"
826     "YRBYSBYTBYUBYVBYWBYXBYYBYZBZCBZDBZEBZFBZGBVPBVQBVRBVSBVTBVUBVVBVWBVXBVYBVZ"
827     "BWCBWDBWEBWFBWGBWHBWIBWJBWKBWLBWMBWNBWOBWPBWQBWRBWSBWTBWUBWVBWWBWXBWYBWZBX"
828     "CBXDBXEBXFBXGBXHBXIBXJBXKBCDFCDGCDHCDICDJCDKCDLCDMCDNCDOCDPCDQCDRCDSCDTCDU"
829     "CDVCDWCDXCDYCDZCEDCEECEFCEGCEHCEICEJCEKCELCEMCENCEOCEPCEQCERCESCETCEUCEVCE"
830     "WCEXCEYCEZZHBZIBZJBZKBZLBZMBZNBZOBZPBZQBZRBZSBZTBZUBZVBZWBZXBZYBZZCCCDCCEC"
831     "CFCCGCCHCCICCJCCKCCLCCMCCNCCOCCPCCQCCRCCSCCTCCUCCVCCWCCXCCYCCZCDDCDECGYCGZ"
832     "CHDCHECHFCHGCHHCHICHJCHKCHLCHMCHNCHOCHPCHQCHRCHSCHTCHUCHVCHWCHXCHYCHZCIDCI"
833     "ECIFCIGCIHCIICIJCIKCILCIMCINCIOCIPCIQCIRCISCITCIUCIVCFDCFECFFCFGCFHCFICFJC"
834     "FKCFLCFMCFNCFOCFPCFQCFRCFSCFTCFUCFVCFWCFXCFYCFZCGDCGECGFCGGCGHCGICGJCGKCGL"
835     "CGMCGNCGOCGPCGQCGRCGSCGTCGUCGVCGWCGXCKUCKVCKWCKXCKYCKZCLDCLECLFCLGCLHCLICL"
836     "JCLKCLLCLMCLNCLOCLPCLQCLRCLSCLTCLUCLVCLWCLXCLYCLZCMDCMECMFCMGCMHCMICMJCMKC"
837     "MLCMMCMNCMOCMPCMQCMRCIWCIXCIYCIZCJDCJECJFCJGCJHCJICJJCJKCJLCJMCJNCJOCJPCJQ"
838     "CJRCJSCJTCJUCJVCJWCJXCJYCJZCKDCKECKFCKGCKHCKICKJCKKCKLCKMCKNCKOCKPCKQCKRCK"
839     "SCKTCOQCORCOSCOTCOUCOVCOWCOXCOYCOZCPDCPECPFCPGCPHCPICPJCPKCPLCPMCPNCPOCPPC"
840     "PQCPRCPSCPTCPUCPVCPWCPXCPYCPZCQDCQECQFCQGCQHCQICQJCQKCQLCQMCQNCMSCMTCMUCMV"
841     "CMWCMXCMYCMZCNDCNECNFCNGCNHCNICNJCNKCNLCNMCNNCNOCNPCNQCNRCNSCNTCNUCNVCNWCN"
842     "XCNYCNZCODCOECOFCOGCOHCOICOJCOKCOLCOMCONCOOCOPCSMCSNCSOCSPCSQCSRCSSCSTCSUC"
843     "SVCSWCSXCSYCSZCTDCTECTFCTGCTHCTICTJCTKCTLCTMCTNCTOCTPCTQCTRCTSCTTCTUCTVCTW"
844     "CTXCTYCTZCUDCUECUFCUGCUHCUICUJCQOCQPCQQCQRCQSCQTCQUCQVCQWCQXCQYCQZCRDCRECR"
845     "FCRGCRHCRICRJCRKCRLCRMCRNCROCRPCRQCRRCRSCRTCRUCRVCRWCRXCRYCRZCSDCSECSFCSGC"
846     "SHCSICSJCSKCSLCWICWJCWKCWLCWMCWNCWOCWPCWQCWRCWSCWTCWUCWVCWWCWXCWYCWZCXDCXE"
847     "CXFCXGCXHCXICXJCXKCXLCXMCXNCXOCXPCXQCXRCXSCXTCXUCXVCXWCXXCXYCXZCYDCYECYFCU"
848     "KCULCUMCUNCUOCUPCUQCURCUSCUTCUUCUVCUWCUXCUYCUZCVDCVECVFCVGCVHCVICVJCVKCVLC"
849     "VMCVNCVOCVPCVQCVRCVSCVTCVUCVVCVWCVXCVYCVZCWDCWECWFCWGCWHEDDFDDGDDHDDIDDJDD"
850     "KDDLDDMDDNDDODDPDDQDDRDDSDDTDDUDDVDDWDDXDDYDDZDEEDEFDEGDEHDEIDEJDEKDELDEMD"
851     "ENDEODEPDEQDERDESDETDEUDEVDEWDEXDEYDEZDFCYGCYHCYICYJCYKCYLCYMCYNCYOCYPCYQC"
852     "YRCYSCYTCYUCYVCYWCYXCYYCYZCZDCZECZFCZGCZHCZICZJCZKCZLCZMCZNCZOCZPCZQCZRCZS"
853     "CZTCZUCZVCZWCZXCZYCZZDDDEDHFDHGDHHDHIDHJDHKDHLDHMDHNDHODHPDHQDHRDHSDHTDHUD"
854     "HVDHWDHXDHYDHZDIEDIFDIGDIHDIIDIJDIKDILDIMDINDIODIPDIQDIRDISDITDIUDIVDIWDIX"
855     "DIYDIZDJEDFFDFGDFHDFIDFJDFKDFLDFMDFNDFODFPDFQDFRDFSDFTDFUDFVDFWDFXDFYDFZDG"
856     "EDGFDGGDGHDGIDGJDGKDGLDGMDGNDGODGPDGQDGRDGSDGTDGUDGVDGWDGXDGYDGZDHEDLFDLGD"
857     "LHDLIDLJDLKDLLDLMDLNDLODLPDLQDLRDLSDLTDLUDLVDLWDLXDLYDLZDMEDMFDMGDMHDMIDMJ"
858     "DMKDMLDMMDMNDMODMPDMQDMRDMSDMTDMUDMVDMWDMXDMYDMZDNEDJFDJGDJHDJIDJJDJKDJLDJ"
859     "MDJNDJODJPDJQDJRDJSDJTDJUDJVDJWDJXDJYDJZDKEDKFDKGDKHDKIDKJDKKDKLDKMDKNDKOD"
860     "KPDKQDKRDKSDKTDKUDKVDKWDKXDKYDKZDLEDPFDPGDPHDPIDPJDPKDPLDPMDPNDPODPPDPQDPR"
861     "DPSDPTDPUDPVDPWDPXDPYDPZDQEDQFDQGDQHDQIDQJDQKDQLDQMDQNDQODQPDQQDQRDQSDQTDQ"
862     "UDQVDQWDQXDQYDQZDREDNFDNGDNHDNIDNJDNKDNLDNMDNNDNODNPDNQDNRDNSDNTDNUDNVDNWD"
863     "NXDNYDNZDOEDOFDOGDOHDOIDOJDOKDOLDOMDONDOODOPDOQDORDOSDOTDOUDOVDOWDOXDOYDOZ"
864     "DPEDTFDTGDTHDTIDTJDTKDTLDTMDTNDTODTPDTQDTRDTSDTTDTUDTVDTWDTXDTYDTZDUEDUFDU"
865     "GDUHDUIDUJDUKDULDUMDUNDUODUPDUQDURDUSDUTDUUDUVDUWDUXDUYDUZDVEDRFDRGDRHDRID"
866     "RJDRKDRLDRMDRNDRODRPDRQDRRDRSDRTDRUDRVDRWDRXDRYDRZDSEDSFDSGDSHDSIDSJDSKDSL"
867     "DSMDSNDSODSPDSQDSRDSSDSTDSUDSVDSWDSXDSYDSZDTEDXFDXGDXHDXIDXJDXKDXLDXMDXNDX"
868     "ODXPDXQDXRDXSDXTDXUDXVDXWDXXDXYDXZDYEDYFDYGDYHDYIDYJDYKDYLDYMDYNDYODYPDYQD"
869     "YRDYSDYTDYUDYVDYWDYXDYYDYZDZEDVFDVGDVHDVIDVJDVKDVLDVMDVNDVODVPDVQDVRDVSDVT"
870     "DVUDVVDVWDVXDVYDVZDWEDWFDWGDWHDWIDWJDWKDWLDWMDWNDWODWPDWQDWRDWSDWTDWUDWVDW"
871     "WDWXDWYDWZDXFGEFHEFIEFJEFKEFLEFMEFNEFOEFPEFQEFREFSEFTEFUEFVEFWEFXEFYEFZEGF"
872     "EGGEGHEGIEGJEGKEGLEGMEGNEGOEGPEGQEGREGSEGTEGUEGVEGWEGXEGYEGZEHFEHGEHHEEDZF"
873     "DZGDZHDZIDZJDZKDZLDZMDZNDZODZPDZQDZRDZSDZTDZUDZVDZWDZXDZYDZZEEEFEEGEEHEEIE"
874     "EJEEKEELEEMEENEEOEEPEEQEEREESEETEEUEEVEEWEEXEEYEEZEFFEJKEJLEJMEJNEJOEJPEJQ"
875     "EJREJSEJTEJUEJVEJWEJXEJYEJZEKFEKGEKHEKIEKJEKKEKLEKMEKNEKOEKPEKQEKREKSEKTEK"
876     "UEKVEKWEKXEKYEKZELFELGELHELIELJELKELLEHIEHJEHKEHLEHMEHNEHOEHPEHQEHREHSEHTE"
877     "HUEHVEHWEHXEHYEHZEIFEIGEIHEIIEIJEIKEILEIMEINEIOEIPEIQEIREISEITEIUEIVEIWEIX"
878     "EIYEIZEJFEJGEJHEJIEJJENOENPENQENRENSENTENUENVENWENXENYENZEOFEOGEOHEOIEOJEO"
879     "KEOLEOMEONEOOEOPEOQEOREOSEOTEOUEOVEOWEOXEOYEOZEPFEPGEPHEPIEPJEPKEPLEPMEPNE"
880     "POEPPELMELNELOELPELQELRELSELTELUELVELWELXELYELZEMFEMGEMHEMIEMJEMKEMLEMMEMN"
881     "EMOEMPEMQEMREMSEMTEMUEMVEMWEMXEMYEMZENFENGENHENIENJENKENLENMENNERSERTERUER"
882     "VERWERXERYERZESFESGESHESIESJESKESLESMESNESOESPESQESRESSESTESUESVESWESXESYE"
883     "SZETFETGETHETIETJETKETLETMETNETOETPETQETRETSETTEPQEPREPSEPTEPUEPVEPWEPXEPY"
884     "EPZEQFEQGEQHEQIEQJEQKEQLEQMEQNEQOEQPEQQEQREQSEQTEQUEQVEQWEQXEQYEQZERFERGER"
885     "HERIERJERKERLERMERNEROERPERQERREVWEVXEVYEVZEWFEWGEWHEWIEWJEWKEWLEWMEWNEWOE"
886     "WPEWQEWREWSEWTEWUEWVEWWEWXEWYEWZEXFEXGEXHEXIEXJEXKEXLEXMEXNEXOEXPEXQEXREXS"
887     "EXTEXUEXVEXWEXXETUETVETWETXETYETZEUFEUGEUHEUIEUJEUKEULEUMEUNEUOEUPEUQEUREU"
888     "SEUTEUUEUVEUWEUXEUYEUZEVFEVGEVHEVIEVJEVKEVLEVMEVNEVOEVPEVQEVREVSEVTEVUEVVE"
889     "FFGFFHFFIFFJFFKFFLFFMFFNFFOFFPFFQFFRFFSFFTFFUFFVFFWFFXFFYFFZFGGFGHFGIFGJFG"
890     "KFGLFGMFGNFGOFGPFGQFGRFGSFGTFGUFGVFGWFGXFGYFGZFHGFHHFHIFHJXYEXZEYFEYGEYHEY"
891     "IEYJEYKEYLEYMEYNEYOEYPEYQEYREYSEYTEYUEYVEYWEYXEYYEYZEZFEZGEZHEZIEZJEZKEZLE"
892     "ZMEZNEZOEZPEZQEZREZSEZTEZUEZVEZWEZXEZYEZZFFJOFJPFJQFJRFJSFJTFJUFJVFJWFJXFJ"
893     "YFJZFKGFKHFKIFKJFKKFKLFKMFKNFKOFKPFKQFKRFKSFKTFKUFKVFKWFKXFKYFKZFLGFLHFLIF"
894     "LJFLKFLLFLMFLNFLOFLPFLQFLRFHKFHLFHMFHNFHOFHPFHQFHRFHSFHTFHUFHVFHWFHXFHYFHZ"
895     "FIGFIHFIIFIJFIKFILFIMFINFIOFIPFIQFIRFISFITFIUFIVFIWFIXFIYFIZFJGFJHFJIFJJFJ"
896     "KFJLFJMFJNFNWFNXFNYFNZFOGFOHFOIFOJFOKFOLFOMFONFOOFOPFOQFORFOSFOTFOUFOVFOWF"
897     "OXFOYFOZFPGFPHFPIFPJFPKFPLFPMFPNFPOFPPFPQFPRFPSFPTFPUFPVFPWFPXFPYFPZFLSFLT"
898     "FLUFLVFLWFLXFLYFLZFMGFMHFMIFMJFMKFMLFMMFMNFMOFMPFMQFMRFMSFMTFMUFMVFMWFMXFM"
899     "YFMZFNGFNHFNIFNJFNKFNLFNMFNNFNOFNPFNQFNRFNSFNTFNUFNVFSKFSLFSMFSNFSOFSPFSQF"
900     "SRFSSFSTFSUFSVFSWFSXFSYFSZFTGFTHFTIFTJFTKFTLFTMFTNFTOFTPFTQFTRFTSFTTFTUFTV"
901     "FTWFTXFTYFTZFUGFUHFUIFUJFUKFULFUMFUNFQGFQHFQIFQJFQKFQLFQMFQNFQOFQPFQQFQRFQ"
902     "SFQTFQUFQVFQWFQXFQYFQZFRGFRHFRIFRJFRKFRLFRMFRNFROFRPFRQFRRFRSFRTFRUFRVFRWF"
903     "RXFRYFRZFSGFSHFSIFSJFWSFWTFWUFWVFWWFWXFWYFWZFXGFXHFXIFXJFXKFXLFXMFXNFXOFXP"
904     "FXQFXRFXSFXTFXUFXVFXWFXXFXYFXZFYGFYHFYIFYJFYKFYLFYMFYNFYOFYPFYQFYRFYSFYTFY"
905     "UFYVFUOFUPFUQFURFUSFUTFUUFUVFUWFUXFUYFUZFVGFVHFVIFVJFVKFVLFVMFVNFVOFVPFVQF"
906     "VRFVSFVTFVUFVVFVWFVXFVYFVZFWGFWHFWIFWJFWKFWLFWMFWNFWOFWPFWQFWRHGHIGHJGHKGH"
907     "LGHMGHNGHOGHPGHQGHRGHSGHTGHUGHVGHWGHXGHYGHZGIHGIIGIJGIKGILGIMGINGIOGIPGIQG"
908     "IRGISGITGIUGIVGIWGIXGIYGIZGJHGJIGJJGJKGJLGJMGJFYWFYXFYYFYZFZGFZHFZIFZJFZKF"
909     "ZLFZMFZNFZOFZPFZQFZRFZSFZTFZUFZVFZWFZXFZYFZZGGGHGGIGGJGGKGGLGGMGGNGGOGGPGG"
910     "QGGRGGSGGTGGUGGVGGWGGXGGYGGZGHTGLUGLVGLWGLXGLYGLZGMHGMIGMJGMKGMLGMMGMNGMOG"
911     "MPGMQGMRGMSGMTGMUGMVGMWGMXGMYGMZGNHGNIGNJGNKGNLGNMGNNGNOGNPGNQGNRGNSGNTGNU"
912     "GNVGNWGNXGNYGNNGJOGJPGJQGJRGJSGJTGJUGJVGJWGJXGJYGJZGKHGKIGKJGKKGKLGKMGKNGK"
913     "OGKPGKQGKRGKSGKTGKUGKVGKWGKXGKYGKZGLHGLIGLJGLKGLLGLMGLNGLOGLPGLQGLRGLSGLMG"
914     "QNGQOGQPGQQGQRGQSGQTGQUGQVGQWGQXGQYGQZGRHGRIGRJGRKGRLGRMGRNGROGRPGRQGRRGRS"
915     "GRTGRUGRVGRWGRXGRYGRZGSHGSIGSJGSKGSLGSMGSNGSOGSPGSQGSRGSZGOHGOIGOJGOKGOLGO"
916     "MGONGOOGOPGOQGORGOSGOTGOUGOVGOWGOXGOYGOZGPHGPIGPJGPKGPLGPMGPNGPOGPPGPQGPRG"
917     "PSGPTGPUGPVGPWGPXGPYGPZGQHGQIGQJGQKGQLGQYGUZGVHGVIGVJGVKGVLGVMGVNGVOGVPGVQ"
918     "GVRGVSGVTGVUGVVGVWGVXGVYGVZGWHGWIGWJGWKGWLGWMGWNGWOGWPGWQGWRGWSGWTGWUGWVGW"
919     "WGWXGWYGWZGXHGXIGXJGXKGXSGSTGSUGSVGSWGSXGSYGSZGTHGTIGTJGTKGTLGTMGTNGTOGTPG"
920     "TQGTRGTSGTTGTUGTVGTWGTXGTYGTZGUHGUIGUJGUKGULGUMGUNGUOGUPGUQGURGUSGUTGUUGUV"
921     "GUWGUXGURGZSGZTGZUGZVGZWGZXGZYGZZHHHIHHJHHKHHLHHMHHNHHOHHPHHQHHRHHSHHTHHUH"
922     "HVHHWHHXHHYHHZHIIHIJHIKHILHIMHINHIOHIPHIQHIRHISHITHIUHIVHIWHIXHIYHLGXMGXNG"
923     "XOGXPGXQGXRGXSGXTGXUGXVGXWGXXGXYGXZGYHGYIGYJGYKGYLGYMGYNGYOGYPGYQGYRGYSGYT"
924     "GYUGYVGYWGYXGYYGYZGZHGZIGZJGZKGZLGZMGZNGZOGZPGZQGZLPHLQHLRHLSHLTHLUHLVHLWH"
925     "LXHLYHLZHMIHMJHMKHMLHMMHMNHMOHMPHMQHMRHMSHMTHMUHMVHMWHMXHMYHMZHNIHNJHNKHNL"
926     "HNMHNNHNOHNPHNQHNRHNSHNTHNUHNVHNWHIZHJIHJJHJKHJLHJMHJNHJOHJPHJQHJRHJSHJTHJ"
927     "UHJVHJWHJXHJYHJZHKIHKJHKKHKLHKMHKNHKOHKPHKQHKRHKSHKTHKUHKVHKWHKXHKYHKZHLIH"
928     "LJHLKHLLHLMHLNHLOHQNHQOHQPHQQHQRHQSHQTHQUHQVHQWHQXHQYHQZHRIHRJHRKHRLHRMHRN"
929     "HROHRPHRQHRRHRSHRTHRUHRVHRWHRXHRYHRZHSIHSJHSKHSLHSMHSNHSOHSPHSQHSRHSSHSTHS"
930     "UHNXHNYHNZHOIHOJHOKHOLHOMHONHOOHOPHOQHORHOSHOTHOUHOVHOWHOXHOYHOZHPIHPJHPKH"
931     "PLHPMHPNHPOHPPHPQHPRHPSHPTHPUHPVHPWHPXHPYHPZHQIHQJHQKHQLHQMHVLHVMHVNHVOHVP"
932     "HVQHVRHVSHVTHVUHVVHVWHVXHVYHVZHWIHWJHWKHWLHWMHWNHWOHWPHWQHWRHWSHWTHWUHWVHW"
933     "WHWXHWYHWZHXIHXJHXKHXLHXMHXNHXOHXPHXQHXRHXSHSVHSWHSXHSYHSZHTIHTJHTKHTLHTMH"
934     "TNHTOHTPHTQHTRHTSHTTHTUHTVHTWHTXHTYHTZHUIHUJHUKHULHUMHUNHUOHUPHUQHURHUSHUT"
935     "HUUHUVHUWHUXHUYHUZHVIHVJHVKHIIKIILIIMIINIIOIIPIIQIIRIISIITIIUIIVIIWIIXIIYI"
936     "IZIJJIJKIJLIJMIJNIJOIJPIJQIJRIJSIJTIJUIJVIJWIJXIJYIJZIKJIKKIKLIKMIKNIKOIKP"
937     "IKQIKRIKSIKTXTHXUHXVHXWHXXHXYHXZHYIHYJHYKHYLHYMHYNHYOHYPHYQHYRHYSHYTHYUHYV"
938     "HYWHYXHYYHYZHZIHZJHZKHZLHZMHZNHZOHZPHZQHZRHZSHZTHZUHZVHZWHZXHZYHZZIIIJINNI"
939     "NOINPINQINRINSINTINUINVINWINXINYINZIOJIOKIOLIOMIONIOOIOPIOQIORIOSIOTIOUIOV"
940     "IOWIOXIOYIOZIPJIPKIPLIPMIPNIPOIPPIPQIPRIPSIPTIPUIPVIPWIKUIKVIKWIKXIKYIKZIL"
941     "JILKILLILMILNILOILPILQILRILSILTILUILVILWILXILYILZIMJIMKIMLIMMIMNIMOIMPIMQI"
942     "MRIMSIMTIMUIMVIMWIMXIMYIMZINJINKINLINMISQISRISSISTISUISVISWISXISYISZITJITK"
943     "ITLITMITNITOITPITQITRITSITTITUITVITWITXITYITZIUJIUKIULIUMIUNIUOIUPIUQIURIU"
944     "SIUTIUUIUVIUWIUXIUYIUZIPXIPYIPZIQJIQKIQLIQMIQNIQOIQPIQQIQRIQSIQTIQUIQVIQWI"
945     "QXIQYIQZIRJIRKIRLIRMIRNIROIRPIRQIRRIRSIRTIRUIRVIRWIRXIRYIRZISJISKISLISMISN"
946     "ISOISPIXTIXUIXVIXWIXXIXYIXZIYJIYKIYLIYMIYNIYOIYPIYQIYRIYSIYTIYUIYVIYWIYXIY"
947     "YIYZIZJIZKIZLIZMIZNIZOIZPIZQIZRIZSIZTIZUIZVIZWIZXIZYIZZJJJKJJLJJIVJIVKIVLI"
948     "VMIVNIVOIVPIVQIVRIVSIVTIVUIVVIVWIVXIVYIVZIWJIWKIWLIWMIWNIWOIWPIWQIWRIWSIWT"
949     "IWUIWVIWWIWXIWYIWZIXJIXKIXLIXMIXNIXOIXPIXQIXRIXSYJLZJMKJMLJMMJMNJMOJMPJMQJ"
950     "MRJMSJMTJMUJMVJMWJMXJMYJMZJNKJNLJNMJNNJNOJNPJNQJNRJNSJNTJNUJNVJNWJNXJNYJNZ"
951     "JOKJOLJOMJONJOOJOPJOQJORJOSJOTJOMJJNJJOJJPJJQJJRJJSJJTJJUJJVJJWJJXJJYJJZJK"
952     "KJKLJKMJKNJKOJKPJKQJKRJKSJKTJKUJKVJKWJKXJKYJKZJLKJLLJLMJLNJLOJLPJLQJLRJLSJ"
953     "LTJLUJLVJLWJLXJLQJRRJRSJRTJRUJRVJRWJRXJRYJRZJSKJSLJSMJSNJSOJSPJSQJSRJSSJST"
954     "JSUJSVJSWJSXJSYJSZJTKJTLJTMJTNJTOJTPJTQJTRJTSJTTJTUJTVJTWJTXJTYJTZJUKJULJU"
955     "UJOVJOWJOXJOYJOZJPKJPLJPMJPNJPOJPPJPQJPRJPSJPTJPUJPVJPWJPXJPYJPZJQKJQLJQMJ"
956     "QNJQOJQPJQQJQRJQSJQTJQUJQVJQWJQXJQYJQZJRKJRLJRMJRNJROJRPJRYJWZJXKJXLJXMJXN"
957     "JXOJXPJXQJXRJXSJXTJXUJXVJXWJXXJXYJXZJYKJYLJYMJYNJYOJYPJYQJYRJYSJYTJYUJYVJY"
958     "WJYXJYYJYZJZKJZLJZMJZNJZOJZPJZQJZRJZSJZTJZMJUNJUOJUPJUQJURJUSJUTJUUJUVJUWJ"
959     "UXJUYJUZJVKJVLJVMJVNJVOJVPJVQJVRJVSJVTJVUJVVJVWJVXJVYJVZJWKJWLJWMJWNJWOJWP"
960     "JWQJWRJWSJWTJWUJWVJWWJWXJWMTKMUKMVKMWKMXKMYKMZKNLKNMKNNKNOKNPKNQKNRKNSKNTK"
961     "NUKNVKNWKNXKNYKNZKOLKOMKONKOOKOPKOQKORKOSKOTKOUKOVKOWKOXKOYKOZKPLKPMKPNKPO"
962     "KPPKPQKPRKUJZVJZWJZXJZYJZZKKKLKKMKKNKKOKKPKKQKKRKKSKKTKKUKKVKKWKKXKKYKKZKL"
963     "LKLMKLNKLOKLPKLQKLRKLSKLTKLUKLVKLWKLXKLYKLZKMLKMMKMNKMOKMPKMQKMRKMSKSRKSSK"
964     "STKSUKSVKSWKSXKSYKSZKTLKTMKTNKTOKTPKTQKTRKTSKTTKTUKTVKTWKTXKTYKTZKULKUMKUN"
965     "KUOKUPKUQKURKUSKUTKUUKUVKUWKUXKUYKUZKVLKVMKVNKVOKVPKPSKPTKPUKPVKPWKPXKPYKP"
966     "ZKQLKQMKQNKQOKQPKQQKQRKQSKQTKQUKQVKQWKQXKQYKQZKRLKRMKRNKROKRPKRQKRRKRSKRTK"
967     "RUKRVKRWKRXKRYKRZKSLKSMKSNKSOKSPKSQKYPKYQKYRKYSKYTKYUKYVKYWKYXKYYKYZKZLKZM"
968     "KZNKZOKZPKZQKZRKZSKZTKZUKZVKZWKZXKZYKZZLLLMLLNLLOLLPLLQLLRLLSLLTLLULLVLLWL"
969     "LXLLYLLZLMMLMNLMOLMPVQKVRKVSKVTKVUKVVKVWKVXKVYKVZKWLKWMKWNKWOKWPKWQKWRKWSK"
970     "WTKWUKWVKWWKWXKWYKWZKXLKXMKXNKXOKXPKXQKXRKXSKXTKXUKXVKXWKXXKXYKXZKYLKYMKYN"
971     "KYOKLPSLPTLPULPVLPWLPXLPYLPZLQMLQNLQOLQPLQQLQRLQSLQTLQULQVLQWLQXLQYLQZLRML"
972     "RNLROLRPLRQLRRLRSLRTLRULRVLRWLRXLRYLRZLSMLSNLSOLSPLSQLSRLSSLSTLMQLMRLMSLMT"
973     "LMULMVLMWLMXLMYLMZLNMLNNLNOLNPLNQLNRLNSLNTLNULNVLNWLNXLNYLNZLOMLONLOOLOPLO"
974     "QLORLOSLOTLOULOVLOWLOXLOYLOZLPMLPNLPOLPPLPQLPRLVWLVXLVYLVZLWMLWNLWOLWPLWQL"
975     "WRLWSLWTLWULWVLWWLWXLWYLWZLXMLXNLXOLXPLXQLXRLXSLXTLXULXVLXWLXXLXYLXZLYMLYN"
976     "LYOLYPLYQLYRLYSLYTLYULYVLYWLYXLSULSVLSWLSXLSYLSZLTMLTNLTOLTPLTQLTRLTSLTTLT"
977     "ULTVLTWLTXLTYLTZLUMLUNLUOLUPLUQLURLUSLUTLUULUVLUWLUXLUYLUZLVMLVNLVOLVPLVQL"
978     "VRLVSLVTLVULVVOMOPMOQMORMOSMOTMOUMOVMOWMOXMOYMOZMPNMPOMPPMPQMPRMPSMPTMPUMP"
979     "VMPWMPXMPYMPZMQNMQOMQPMQQMQRMQSMQTMQUMQVMQWMQXMQYMQZMRNMROMRPMRQMRRMRSMRLY"
980     "YLYZLZMLZNLZOLZPLZQLZRLZSLZTLZULZVLZWLZXLZYLZZMMMNMMOMMPMMQMMRMMSMMTMMUMMV"
981     "MMWMMXMMYMMZMNNMNOMNPMNQMNRMNSMNTMNUMNVMNWMNXMNYMNZMONMOYMUZMVNMVOMVPMVQMV"
982     "RMVSMVTMVUMVVMVWMVXMVYMVZMWNMWOMWPMWQMWRMWSMWTMWUMWVMWWMWXMWYMWZMXNMXOMXPM"
983     "XQMXRMXSMXTMXUMXVMXWMXXMXYMXZMYNMYOMYPMYTMRUMRVMRWMRXMRYMRZMSNMSOMSPMSQMSR"
984     "MSSMSTMSUMSVMSWMSXMSYMSZMTNMTOMTPMTQMTRMTSMTTMTUMTVMTWMTXMTYMTZMUNMUOMUPMU"
985     "QMURMUSMUTMUUMUVMUWMUXMUOXNOYNOZNPONPPNPQNPRNPSNPTNPUNPVNPWNPXNPYNPZNQONQP"
986     "NQQNQRNQSNQTNQUNQVNQWNQXNQYNQZNRONRPNRQNRRNRSNRTNRUNRVNRWNRXNRYNRZNSONSPNS"
987     "QNSRNSSNQMYRMYSMYTMYUMYVMYWMYXMYYMYZMZNMZOMZPMZQMZRMZSMZTMZUMZVMZWMZXMZYMZ"
988     "ZNNNONNPNNQNNRNNSNNTNNUNNVNNWNNXNNYNNZNOONOPNOQNORNOSNOTNOUNOVNOWNWPNWQNWR"
989     "NWSNWTNWUNWVNWWNWXNWYNWZNXONXPNXQNXRNXSNXTNXUNXVNXWNXXNXYNXZNYONYPNYQNYRNY"
990     "SNYTNYUNYVNYWNYXNYYNYZNZONZPNZQNZRNZSNZTNZUNZVNZWNSTNSUNSVNSWNSXNSYNSZNTON"
991     "TPNTQNTRNTSNTTNTUNTVNTWNTXNTYNTZNUONUPNUQNURNUSNUTNUUNUVNUWNUXNUYNUZNVONVP"
992     "NVQNVRNVSNVTNVUNVVNVWNVXNVYNVZNWONORXORYORZOSPOSQOSROSSOSTOSUOSVOSWOSXOSYO"
993     "SZOTPOTQOTROTSOTTOTUOTVOTWOTXOTYOTZOUPOUQOUROUSOUTOUUOUVOUWOUXOUYOUZOVPOVQ"
994     "OVROVSOVTOVUOVVOVWZXNZYNZZOOOPOOQOOROOSOOTOOUOOVOOWOOXOOYOOZOPPOPQOPROPSOP"
995     "TOPUOPVOPWOPXOPYOPZOQPOQQOQROQSOQTOQUOQVOQWOQXOQYOQZORPORQORRORSORTORUORVO"
996     "RWOZXOZYOZZPPPQPPRPPSPPTPPUPPVPPWPPXPPYPPZPQQPQRPQSPQTPQUPQVPQWPQXPQYPQZPR"
997     "QPRRPRSPRTPRUPRVPRWPRXPRYPRZPSQPSRPSSPSTPSUPSVPSWPSXPSYPSZPTOVXOVYOVZOWPOW"
998     "QOWROWSOWTOWUOWVOWWOWXOWYOWZOXPOXQOXROXSOXTOXUOXVOXWOXXOXYOXZOYPOYQOYROYSO"
999     "YTOYUOYVOYWOYXOYYOYZOZPOZQOZROZSOZTOZUOZVOZWQPTRPTSPTTPTUPTV";
1000 
TEST(ZlibTest,DeflateZFixedCorruption)1001 TEST(ZlibTest, DeflateZFixedCorruption) {
1002   // Tavis's test case from
1003   // https://www.openwall.com/lists/oss-security/2022/03/26/1
1004   // The upstream fix,
1005   // https://github.com/madler/zlib/commit/5c44459c3b28a9bd3283aaceab7c615f8020c531,
1006   // was merged in Chromium in #583975.
1007 
1008   z_stream stream;
1009   stream.zalloc = Z_NULL;
1010   stream.zfree = Z_NULL;
1011 
1012   int level = Z_DEFAULT_COMPRESSION;
1013   int windowBits = 15;
1014   int memLevel = 1;
1015   int strategy = Z_FIXED;
1016 
1017   int ret =
1018       deflateInit2(&stream, level, Z_DEFLATED, windowBits, memLevel, strategy);
1019   ASSERT_EQ(ret, Z_OK);
1020   std::vector<uint8_t> compressed(
1021       deflateBound(&stream, strlen(zFixedCorruptionData)));
1022   stream.next_out = compressed.data();
1023   stream.avail_out = compressed.size();
1024   stream.next_in = (uint8_t*)zFixedCorruptionData;
1025   stream.avail_in = strlen(zFixedCorruptionData);
1026   ret = deflate(&stream, Z_FINISH);
1027   ASSERT_EQ(ret, Z_STREAM_END);
1028   size_t compressed_sz = compressed.size() - stream.avail_out;
1029   deflateEnd(&stream);
1030 
1031   std::vector<uint8_t> decompressed(strlen(zFixedCorruptionData));
1032   ret = inflateInit2(&stream, windowBits);
1033   ASSERT_EQ(ret, Z_OK);
1034   stream.next_in = compressed.data();
1035   stream.avail_in = compressed_sz;
1036   stream.next_out = decompressed.data();
1037   stream.avail_out = decompressed.size();
1038   ret = inflate(&stream, Z_FINISH);
1039   ASSERT_EQ(ret, Z_STREAM_END);
1040   inflateEnd(&stream);
1041 
1042   EXPECT_EQ(decompressed.size(), strlen(zFixedCorruptionData));
1043   EXPECT_EQ(
1044       memcmp(zFixedCorruptionData, decompressed.data(), decompressed.size()),
1045       0);
1046 }
1047 
TEST(ZlibTest,DeflateCopy)1048 TEST(ZlibTest, DeflateCopy) {
1049   // Check that deflateCopy() works.
1050 
1051   z_stream stream1;
1052   stream1.zalloc = Z_NULL;
1053   stream1.zfree = Z_NULL;
1054   int ret =
1055       deflateInit(&stream1, Z_DEFAULT_COMPRESSION);
1056   ASSERT_EQ(ret, Z_OK);
1057   std::vector<uint8_t> compressed(
1058       deflateBound(&stream1, strlen(zFixedCorruptionData)));
1059   stream1.next_out = compressed.data();
1060   stream1.avail_out = compressed.size();
1061 
1062   // Compress the first 1000 bytes.
1063   stream1.next_in = (uint8_t*)zFixedCorruptionData;
1064   stream1.avail_in = 1000;
1065   ret = deflate(&stream1, Z_NO_FLUSH);
1066   ASSERT_EQ(ret, Z_OK);
1067 
1068   // Copy the stream state.
1069   z_stream stream2;
1070   ret = deflateCopy(&stream2, &stream1);
1071   ASSERT_EQ(ret, Z_OK);
1072   deflateEnd(&stream1);
1073 
1074   // Compress the remaining bytes.
1075   stream2.next_in = (uint8_t*)zFixedCorruptionData + (1000 - stream2.avail_in);
1076   stream2.avail_in = strlen(zFixedCorruptionData) - (1000 - stream2.avail_in);
1077   ret = deflate(&stream2, Z_FINISH);
1078   ASSERT_EQ(ret, Z_STREAM_END);
1079   size_t compressed_sz = compressed.size() - stream2.avail_out;
1080   deflateEnd(&stream2);
1081 
1082   // Check that decompression is successful.
1083   std::vector<uint8_t> decompressed(strlen(zFixedCorruptionData));
1084   z_stream stream;
1085   stream.zalloc = Z_NULL;
1086   stream.zfree = Z_NULL;
1087   ret = inflateInit(&stream);
1088   ASSERT_EQ(ret, Z_OK);
1089   stream.next_in = compressed.data();
1090   stream.avail_in = compressed_sz;
1091   stream.next_out = decompressed.data();
1092   stream.avail_out = decompressed.size();
1093   ret = inflate(&stream, Z_FINISH);
1094   ASSERT_EQ(ret, Z_STREAM_END);
1095   inflateEnd(&stream);
1096 
1097   EXPECT_EQ(decompressed.size(), strlen(zFixedCorruptionData));
1098   EXPECT_EQ(
1099       memcmp(zFixedCorruptionData, decompressed.data(), decompressed.size()),
1100       0);
1101 }
1102 
TEST(ZlibTest,GzipStored)1103 TEST(ZlibTest, GzipStored) {
1104   // Check that deflating uncompressed blocks with a gzip header doesn't write
1105   // out of bounds (crbug.com/325990053).
1106   z_stream stream;
1107   stream.zalloc = Z_NULL;
1108   stream.zfree = Z_NULL;
1109   static const int kGzipWrapper = 16;
1110   int ret = deflateInit2(&stream, Z_NO_COMPRESSION, Z_DEFLATED,
1111                          9 + kGzipWrapper, 9, Z_DEFAULT_STRATEGY);
1112   ASSERT_EQ(ret, Z_OK);
1113 
1114   const std::vector<uint8_t> src(512 * 1024);
1115   stream.next_in = (unsigned char*)src.data();
1116   stream.avail_in = src.size();
1117 
1118   std::vector<uint8_t> out(1000);
1119   stream.next_out = (unsigned char*)out.data();
1120   stream.avail_out = out.size();
1121 
1122   ret = deflate(&stream, Z_NO_FLUSH);
1123   ASSERT_EQ(ret, Z_OK);
1124 
1125   deflateEnd(&stream);
1126 }
1127 
TEST(ZlibTest,DeflateBound)1128 TEST(ZlibTest, DeflateBound) {
1129   // Check that the deflateBound() isn't too low when using non-default
1130   // parameters (crbug.com/40270738).
1131   const int level = 9;
1132   const int windowBits = 15;
1133   const int memLevel = 1;
1134   const int strategy = Z_FIXED;
1135   const uint8_t src[] = {
1136       49,  255, 255, 20,  45,  49,  167, 56,  55,  255, 255, 255, 223, 255, 49,
1137       255, 3,   78,  0,   0,   141, 253, 209, 163, 29,  195, 43,  60,  199, 123,
1138       112, 35,  134, 13,  148, 102, 212, 4,   184, 103, 7,   102, 225, 102, 156,
1139       164, 78,  48,  70,  49,  125, 162, 55,  116, 161, 174, 83,  0,   59,  0,
1140       225, 140, 0,   0,   63,  63,  4,   15,  198, 30,  126, 196, 33,  99,  135,
1141       41,  192, 82,  28,  105, 216, 170, 221, 14,  61,  1,   0,   0,   22,  195,
1142       45,  53,  244, 163, 167, 158, 229, 68,  18,  112, 49,  174, 43,  75,  90,
1143       161, 85,  19,  36,  163, 118, 228, 169, 180, 161, 237, 234, 253, 197, 234,
1144       66,  106, 12,  42,  124, 96,  160, 144, 183, 194, 157, 167, 202, 217};
1145 
1146   z_stream stream;
1147   stream.zalloc = Z_NULL;
1148   stream.zfree = Z_NULL;
1149   int ret =
1150       deflateInit2(&stream, level, Z_DEFLATED, windowBits, memLevel, strategy);
1151   ASSERT_EQ(ret, Z_OK);
1152   size_t deflate_bound = deflateBound(&stream, sizeof(src));
1153 
1154   uint8_t out[sizeof(src) * 10];
1155   stream.next_in = (uint8_t*)src;
1156   stream.avail_in = sizeof(src);
1157   stream.next_out = out;
1158   stream.avail_out = sizeof(out);
1159   ret = deflate(&stream, Z_FINISH);
1160   ASSERT_EQ(ret, Z_STREAM_END);
1161 
1162   size_t out_size = sizeof(out) - stream.avail_out;
1163   EXPECT_LE(out_size, deflate_bound);
1164 
1165   deflateEnd(&stream);
1166 }
1167 
1168 // TODO(gustavoa): make these tests run standalone.
1169 #ifndef CMAKE_STANDALONE_UNITTESTS
1170 
TEST(ZlibTest,ZipFilenameCommentSize)1171 TEST(ZlibTest, ZipFilenameCommentSize) {
1172   // Check that minizip rejects zip member filenames or comments longer than
1173   // the zip format can represent.
1174 
1175   base::ScopedTempDir temp_dir;
1176   ASSERT_TRUE(temp_dir.CreateUniqueTempDir());
1177   base::FilePath zip_file = temp_dir.GetPath().AppendASCII("crbug1470539.zip");
1178 
1179   zipFile zf = zipOpen(zip_file.AsUTF8Unsafe().c_str(), APPEND_STATUS_CREATE);
1180   ASSERT_NE(zf, nullptr);
1181 
1182   // Adding a member with 2^16 byte filename is okay.
1183   std::string long_filename(UINT16_MAX, 'a');
1184   EXPECT_EQ(zipOpenNewFileInZip(zf, long_filename.c_str(), nullptr, nullptr, 0,
1185                                 nullptr, 0, nullptr, Z_DEFLATED,
1186                                 Z_DEFAULT_COMPRESSION),
1187             ZIP_OK);
1188   EXPECT_EQ(zipWriteInFileInZip(zf, "1", 1), ZIP_OK);
1189   EXPECT_EQ(zipCloseFileInZip(zf), ZIP_OK);
1190 
1191   // Adding a member with 2^16+1 byte filename is NOT okay.
1192   std::string too_long_filename = long_filename + 'a';
1193   EXPECT_EQ(zipOpenNewFileInZip(zf, too_long_filename.c_str(), nullptr, nullptr,
1194                                 0, nullptr, 0, nullptr, Z_DEFLATED,
1195                                 Z_DEFAULT_COMPRESSION),
1196             ZIP_PARAMERROR);
1197 
1198   // Adding a member with 2^16 byte comment is okay.
1199   std::string long_comment(UINT16_MAX, 'x');
1200   EXPECT_EQ(zipOpenNewFileInZip(zf, "x", nullptr, nullptr, 0, nullptr, 0,
1201                                 long_comment.c_str(), Z_DEFLATED,
1202                                 Z_DEFAULT_COMPRESSION),
1203             ZIP_OK);
1204   EXPECT_EQ(zipCloseFileInZip(zf), ZIP_OK);
1205 
1206   // Adding a member with 2^16+1 byte comment is NOT okay.
1207   std::string too_long_comment = long_comment + 'x';
1208   EXPECT_EQ(zipOpenNewFileInZip(zf, "x", nullptr, nullptr, 0, nullptr, 0,
1209                                 too_long_comment.c_str(), Z_DEFLATED,
1210                                 Z_DEFAULT_COMPRESSION),
1211             ZIP_PARAMERROR);
1212 
1213   EXPECT_EQ(zipClose(zf, nullptr), ZIP_OK);
1214 
1215   // Check that the long filename and comment members were successfully added.
1216   unzFile uzf = unzOpen(zip_file.AsUTF8Unsafe().c_str());
1217   ASSERT_NE(uzf, nullptr);
1218   char buf[UINT16_MAX + 2];
1219 
1220   ASSERT_EQ(unzGoToFirstFile(uzf), UNZ_OK);
1221   ASSERT_EQ(unzGetCurrentFileInfo(uzf, nullptr, buf, sizeof(buf), nullptr, 0,
1222                                   nullptr, 0),
1223             UNZ_OK);
1224   EXPECT_EQ(std::string(buf), long_filename);
1225 
1226   ASSERT_EQ(unzGoToNextFile(uzf), UNZ_OK);
1227   ASSERT_EQ(unzGetCurrentFileInfo(uzf, nullptr, nullptr, 0, nullptr, 0, buf,
1228                                   sizeof(buf)),
1229             UNZ_OK);
1230   EXPECT_EQ(std::string(buf), long_comment);
1231 
1232   EXPECT_EQ(unzGoToNextFile(uzf), UNZ_END_OF_LIST_OF_FILE);
1233   EXPECT_EQ(unzClose(uzf), UNZ_OK);
1234 }
1235 
TEST(ZlibTest,ZipExtraFieldSize)1236 TEST(ZlibTest, ZipExtraFieldSize) {
1237   // Check that minizip rejects zip members with too large extra fields.
1238 
1239   std::string extra_field;
1240   extra_field.append("\x12\x34");  // Header ID.
1241   extra_field.append("\xfb\xff");  // Data size (not including the header).
1242   extra_field.append(UINT16_MAX - 4, 'a');
1243 
1244   base::ScopedTempDir temp_dir;
1245   ASSERT_TRUE(temp_dir.CreateUniqueTempDir());
1246   base::FilePath zip_file = temp_dir.GetPath().AppendASCII("extrafield.zip");
1247 
1248   zipFile zf = zipOpen(zip_file.AsUTF8Unsafe().c_str(), APPEND_STATUS_CREATE);
1249   ASSERT_NE(zf, nullptr);
1250 
1251   // Adding a member with 2^16 byte extra field should work.
1252   EXPECT_EQ(zipOpenNewFileInZip(zf, "a", nullptr, extra_field.data(),
1253                                 extra_field.size(), extra_field.data(),
1254                                 extra_field.size(), nullptr, Z_DEFLATED,
1255                                 Z_DEFAULT_COMPRESSION),
1256             ZIP_OK);
1257   EXPECT_EQ(zipWriteInFileInZip(zf, "1", 1), ZIP_OK);
1258   EXPECT_EQ(zipCloseFileInZip(zf), ZIP_OK);
1259 
1260   // More then 2^16 bytes doesn't work. Neither for size_extrafield_local, nor
1261   // size_extrafield_global.
1262   std::string extra_field_long = extra_field + 'x';
1263   EXPECT_EQ(
1264       zipOpenNewFileInZip(zf, "b", nullptr, nullptr, 0, extra_field_long.data(),
1265                           extra_field_long.size(), nullptr, Z_DEFLATED,
1266                           Z_DEFAULT_COMPRESSION),
1267       ZIP_PARAMERROR);
1268   EXPECT_EQ(zipOpenNewFileInZip(zf, "b", nullptr, extra_field_long.data(),
1269                                 extra_field_long.size(), nullptr, 0, nullptr,
1270                                 Z_DEFLATED, Z_DEFAULT_COMPRESSION),
1271             ZIP_PARAMERROR);
1272 
1273   EXPECT_EQ(zipClose(zf, nullptr), ZIP_OK);
1274 
1275   // Check that the data can be read back.
1276   unzFile uzf = unzOpen(zip_file.AsUTF8Unsafe().c_str());
1277   ASSERT_NE(uzf, nullptr);
1278   char buf[UINT16_MAX + 1] = {0};
1279 
1280   ASSERT_EQ(unzGoToFirstFile(uzf), UNZ_OK);
1281   ASSERT_EQ(unzGetCurrentFileInfo(uzf, nullptr, nullptr, 0, buf,
1282                                   sizeof(buf) - 1, nullptr, 0),
1283             UNZ_OK);
1284   EXPECT_EQ(std::string(buf), extra_field);
1285 
1286   EXPECT_EQ(unzGoToNextFile(uzf), UNZ_END_OF_LIST_OF_FILE);
1287   EXPECT_EQ(unzClose(uzf), UNZ_OK);
1288 }
1289 
1290 #endif
1291