1 // Copyright 2011 Google Inc. All Rights Reserved.
3 // Redistribution and use in source and binary forms, with or without
4 // modification, are permitted provided that the following conditions are
7 // * Redistributions of source code must retain the above copyright
8 // notice, this list of conditions and the following disclaimer.
9 // * Redistributions in binary form must reproduce the above
10 // copyright notice, this list of conditions and the following disclaimer
11 // in the documentation and/or other materials provided with the
13 // * Neither the name of Google Inc. nor the names of its
14 // contributors may be used to endorse or promote products derived from
15 // this software without specific prior written permission.
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 // Various stubs for the unit tests for the open-source version of Snappy.
31 #ifndef UTIL_SNAPPY_OPENSOURCE_SNAPPY_TEST_H_
32 #define UTIL_SNAPPY_OPENSOURCE_SNAPPY_TEST_H_
34 #include "snappy-stubs-internal.h"
39 #ifdef HAVE_SYS_MMAN_H
43 #ifdef HAVE_SYS_RESOURCE_H
44 #include <sys/resource.h>
50 #define WIN32_LEAN_AND_MEAN
58 #include <gtest/gtest.h>
60 #define TYPED_TEST TEST
61 #define INIT_GTEST(argc, argv) ::testing::InitGoogleTest(argc, *argv)
65 // Stubs for if the user doesn't have Google Test installed.
67 #define TEST(test_case, test_subcase) \
68 void Test_ ## test_case ## _ ## test_subcase()
69 #define INIT_GTEST(argc, argv)
71 #define TYPED_TEST TEST
72 #define EXPECT_EQ CHECK_EQ
73 #define EXPECT_NE CHECK_NE
74 #define EXPECT_FALSE(cond) CHECK(!(cond))
80 #include <gflags/gflags.h>
82 // This is tricky; both gflags and Google Test want to look at the command line
83 // arguments. Google Test seems to be the most happy with unknown arguments,
84 // though, so we call it first and hope for the best.
85 #define InitGoogle(argv0, argc, argv, remove_flags) \
86 INIT_GTEST(argc, argv); \
87 google::ParseCommandLineFlags(argc, argv, remove_flags);
91 // If we don't have the gflags package installed, these can only be
92 // changed at compile time.
93 #define DEFINE_int32(flag_name, default_value, description) \
94 static int FLAGS_ ## flag_name = default_value;
96 #define InitGoogle(argv0, argc, argv, remove_flags) \
97 INIT_GTEST(argc, argv)
106 #include "lzo/lzo1x.h"
115 #ifdef HAVE_LIBFASTLZ
119 #ifdef HAVE_LIBQUICKLZ
127 void ReadFileToStringOrDie(const char* filename, string* data) {
128 FILE* fp = fopen(filename, "rb");
137 size_t ret = fread(buf, 1, 4096, fp);
138 if (ret == 0 && ferror(fp)) {
142 data->append(string(buf, ret));
148 void ReadFileToStringOrDie(const string& filename, string* data) {
149 ReadFileToStringOrDie(filename.c_str(), data);
152 void WriteStringToFileOrDie(const string& str, const char* filename) {
153 FILE* fp = fopen(filename, "wb");
159 int ret = fwrite(str.data(), str.size(), 1, fp);
172 #define FLAGS_test_random_seed 301
173 typedef string TypeParam;
175 void Test_CorruptedTest_VerifyCorrupted();
176 void Test_Snappy_SimpleTests();
177 void Test_Snappy_MaxBlowup();
178 void Test_Snappy_RandomData();
179 void Test_Snappy_FourByteOffset();
180 void Test_SnappyCorruption_TruncatedVarint();
181 void Test_SnappyCorruption_UnterminatedVarint();
182 void Test_Snappy_ReadPastEndOfBuffer();
183 void Test_Snappy_FindMatchLength();
184 void Test_Snappy_FindMatchLengthRandom();
186 string ReadTestDataFile(const string& base);
188 // A sprintf() variant that returns a std::string.
189 // Not safe for general use due to truncation issues.
190 string StringPrintf(const char* format, ...);
192 // A simple, non-cryptographically-secure random generator.
195 explicit ACMRandom(uint32 seed) : seed_(seed) {}
199 int32 Uniform(int32 n) {
203 return static_cast<uint8>((Next() >> 1) & 0x000000ff);
205 bool OneIn(int X) { return Uniform(X) == 0; }
207 // Skewed: pick "base" uniformly from range [0,max_log] and then
208 // return "base" random bits. The effect is to pick a number in the
209 // range [0,2^max_log-1] with bias towards smaller numbers.
210 int32 Skewed(int max_log);
213 static const uint32 M = 2147483647L; // 2^31-1
217 inline int32 ACMRandom::Next() {
218 static const uint64 A = 16807; // bits 14, 8, 7, 5, 2, 1, 0
220 // seed_ = (seed_ * A) % M, where M = 2^31-1
222 // seed_ must not be zero or M, or else all subsequent computed values
223 // will be zero or M respectively. For all other values, seed_ will end
224 // up cycling through every number in [1,M-1]
225 uint64 product = seed_ * A;
227 // Compute (product % M) using the fact that ((x << 31) % M) == x.
228 seed_ = (product >> 31) + (product & M);
229 // The first reduction may overflow by 1 bit, so we may need to repeat.
230 // mod == M is not possible; using > allows the faster sign-bit-based test.
237 inline int32 ACMRandom::Skewed(int max_log) {
238 const int32 base = (Next() - 1) % (max_log+1);
239 return (Next() - 1) & ((1u << base)-1);
242 // A wall-time clock. This stub is not super-accurate, nor resistant to the
243 // system time changing.
246 CycleTimer() : real_time_us_(0) {}
250 QueryPerformanceCounter(&start_);
252 gettimeofday(&start_, NULL);
259 LARGE_INTEGER frequency;
260 QueryPerformanceCounter(&stop);
261 QueryPerformanceFrequency(&frequency);
263 double elapsed = static_cast<double>(stop.QuadPart - start_.QuadPart) /
265 real_time_us_ += elapsed * 1e6 + 0.5;
268 gettimeofday(&stop, NULL);
270 real_time_us_ += 1000000 * (stop.tv_sec - start_.tv_sec);
271 real_time_us_ += (stop.tv_usec - start_.tv_usec);
276 return real_time_us_ * 1e-6;
282 LARGE_INTEGER start_;
284 struct timeval start_;
288 // Minimalistic microbenchmark framework.
290 typedef void (*BenchmarkFunction)(int, int);
294 Benchmark(const string& name, BenchmarkFunction function) :
295 name_(name), function_(function) {}
297 Benchmark* DenseRange(int start, int stop) {
307 const BenchmarkFunction function_;
310 #define BENCHMARK(benchmark_name) \
311 Benchmark* Benchmark_ ## benchmark_name = \
312 (new Benchmark(#benchmark_name, benchmark_name))
314 extern Benchmark* Benchmark_BM_UFlat;
315 extern Benchmark* Benchmark_BM_UValidate;
316 extern Benchmark* Benchmark_BM_ZFlat;
318 void ResetBenchmarkTiming();
319 void StartBenchmarkTiming();
320 void StopBenchmarkTiming();
321 void SetBenchmarkLabel(const string& str);
322 void SetBenchmarkBytesProcessed(int64 bytes);
326 // Object-oriented wrapper around zlib.
332 // Wipe a ZLib object to a virgin state. This differs from Reset()
333 // in that it also breaks any state.
336 // Call this to make a zlib buffer as good as new. Here's the only
337 // case where they differ:
338 // CompressChunk(a); CompressChunk(b); CompressChunkDone(); vs
339 // CompressChunk(a); Reset(); CompressChunk(b); CompressChunkDone();
340 // You'll want to use Reset(), then, when you interrupt a compress
341 // (or uncompress) in the middle of a chunk and want to start over.
344 // According to the zlib manual, when you Compress, the destination
345 // buffer must have size at least src + .1%*src + 12. This function
346 // helps you calculate that. Augment this to account for a potential
347 // gzip header and footer, plus a few bytes of slack.
348 static int MinCompressbufSize(int uncompress_size) {
349 return uncompress_size + uncompress_size/1000 + 40;
352 // Compresses the source buffer into the destination buffer.
353 // sourceLen is the byte length of the source buffer.
354 // Upon entry, destLen is the total size of the destination buffer,
355 // which must be of size at least MinCompressbufSize(sourceLen).
356 // Upon exit, destLen is the actual size of the compressed buffer.
358 // This function can be used to compress a whole file at once if the
359 // input file is mmap'ed.
361 // Returns Z_OK if success, Z_MEM_ERROR if there was not
362 // enough memory, Z_BUF_ERROR if there was not enough room in the
363 // output buffer. Note that if the output buffer is exactly the same
364 // size as the compressed result, we still return Z_BUF_ERROR.
365 // (check CL#1936076)
366 int Compress(Bytef *dest, uLongf *destLen,
367 const Bytef *source, uLong sourceLen);
369 // Uncompresses the source buffer into the destination buffer.
370 // The destination buffer must be long enough to hold the entire
371 // decompressed contents.
373 // Returns Z_OK on success, otherwise, it returns a zlib error code.
374 int Uncompress(Bytef *dest, uLongf *destLen,
375 const Bytef *source, uLong sourceLen);
377 // Uncompress data one chunk at a time -- ie you can call this
378 // more than once. To get this to work you need to call per-chunk
379 // and "done" routines.
381 // Returns Z_OK if success, Z_MEM_ERROR if there was not
382 // enough memory, Z_BUF_ERROR if there was not enough room in the
385 int UncompressAtMost(Bytef *dest, uLongf *destLen,
386 const Bytef *source, uLong *sourceLen);
388 // Checks gzip footer information, as needed. Mostly this just
389 // makes sure the checksums match. Whenever you call this, it
390 // will assume the last 8 bytes from the previous UncompressChunk
391 // call are the footer. Returns true iff everything looks ok.
392 bool UncompressChunkDone();
395 int InflateInit(); // sets up the zlib inflate structure
396 int DeflateInit(); // sets up the zlib deflate structure
398 // These init the zlib data structures for compressing/uncompressing
399 int CompressInit(Bytef *dest, uLongf *destLen,
400 const Bytef *source, uLong *sourceLen);
401 int UncompressInit(Bytef *dest, uLongf *destLen,
402 const Bytef *source, uLong *sourceLen);
403 // Initialization method to be called if we hit an error while
404 // uncompressing. On hitting an error, call this method before
405 // returning the error.
406 void UncompressErrorInit();
408 // Helper function for Compress
409 int CompressChunkOrAll(Bytef *dest, uLongf *destLen,
410 const Bytef *source, uLong sourceLen,
412 int CompressAtMostOrAll(Bytef *dest, uLongf *destLen,
413 const Bytef *source, uLong *sourceLen,
416 // Likewise for UncompressAndUncompressChunk
417 int UncompressChunkOrAll(Bytef *dest, uLongf *destLen,
418 const Bytef *source, uLong sourceLen,
421 int UncompressAtMostOrAll(Bytef *dest, uLongf *destLen,
422 const Bytef *source, uLong *sourceLen,
425 // Initialization method to be called if we hit an error while
426 // compressing. On hitting an error, call this method before
427 // returning the error.
428 void CompressErrorInit();
430 int compression_level_; // compression level
431 int window_bits_; // log base 2 of the window size used in compression
432 int mem_level_; // specifies the amount of memory to be used by
434 z_stream comp_stream_; // Zlib stream data structure
435 bool comp_init_; // True if we have initialized comp_stream_
436 z_stream uncomp_stream_; // Zlib stream data structure
437 bool uncomp_init_; // True if we have initialized uncomp_stream_
439 // These are used only with chunked compression.
440 bool first_chunk_; // true if we need to emit headers with this chunk
445 } // namespace snappy
447 DECLARE_bool(run_microbenchmarks);
449 static void RunSpecifiedBenchmarks() {
450 if (!FLAGS_run_microbenchmarks) {
454 fprintf(stderr, "Running microbenchmarks.\n");
456 fprintf(stderr, "WARNING: Compiled with assertions enabled, will be slow.\n");
459 fprintf(stderr, "WARNING: Compiled without optimization, will be slow.\n");
461 fprintf(stderr, "Benchmark Time(ns) CPU(ns) Iterations\n");
462 fprintf(stderr, "---------------------------------------------------\n");
464 snappy::Benchmark_BM_UFlat->Run();
465 snappy::Benchmark_BM_UValidate->Run();
466 snappy::Benchmark_BM_ZFlat->Run();
468 fprintf(stderr, "\n");
473 static inline int RUN_ALL_TESTS() {
474 fprintf(stderr, "Running correctness tests.\n");
475 snappy::Test_CorruptedTest_VerifyCorrupted();
476 snappy::Test_Snappy_SimpleTests();
477 snappy::Test_Snappy_MaxBlowup();
478 snappy::Test_Snappy_RandomData();
479 snappy::Test_Snappy_FourByteOffset();
480 snappy::Test_SnappyCorruption_TruncatedVarint();
481 snappy::Test_SnappyCorruption_UnterminatedVarint();
482 snappy::Test_Snappy_ReadPastEndOfBuffer();
483 snappy::Test_Snappy_FindMatchLength();
484 snappy::Test_Snappy_FindMatchLengthRandom();
485 fprintf(stderr, "All tests passed.\n");
495 static void CompressFile(const char* fname);
496 static void UncompressFile(const char* fname);
497 static void MeasureFile(const char* fname);
501 using snappy::CompressFile;
502 using snappy::UncompressFile;
503 using snappy::MeasureFile;
505 #endif // UTIL_SNAPPY_OPENSOURCE_SNAPPY_TEST_H_