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