]> git.cworth.org Git - apitrace/blob - thirdparty/snappy/snappy.cc
Merge branch 'master' into compression
[apitrace] / thirdparty / snappy / snappy.cc
1 // Copyright 2005 Google Inc. All Rights Reserved.
2 //
3 // Redistribution and use in source and binary forms, with or without
4 // modification, are permitted provided that the following conditions are
5 // met:
6 //
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
12 // distribution.
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.
16 //
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.
28
29 #include "snappy.h"
30 #include "snappy-internal.h"
31 #include "snappy-sinksource.h"
32
33 #include <stdio.h>
34
35 #include <algorithm>
36 #include <string>
37 #include <vector>
38
39
40 namespace snappy {
41
42 // Any hash function will produce a valid compressed bitstream, but a good
43 // hash function reduces the number of collisions and thus yields better
44 // compression for compressible input, and more speed for incompressible
45 // input. Of course, it doesn't hurt if the hash function is reasonably fast
46 // either, as it gets called a lot.
47 static inline uint32 HashBytes(uint32 bytes, int shift) {
48   uint32 kMul = 0x1e35a7bd;
49   return (bytes * kMul) >> shift;
50 }
51 static inline uint32 Hash(const char* p, int shift) {
52   return HashBytes(UNALIGNED_LOAD32(p), shift);
53 }
54
55 size_t MaxCompressedLength(size_t source_len) {
56   // Compressed data can be defined as:
57   //    compressed := item* literal*
58   //    item       := literal* copy
59   //
60   // The trailing literal sequence has a space blowup of at most 62/60
61   // since a literal of length 60 needs one tag byte + one extra byte
62   // for length information.
63   //
64   // Item blowup is trickier to measure.  Suppose the "copy" op copies
65   // 4 bytes of data.  Because of a special check in the encoding code,
66   // we produce a 4-byte copy only if the offset is < 65536.  Therefore
67   // the copy op takes 3 bytes to encode, and this type of item leads
68   // to at most the 62/60 blowup for representing literals.
69   //
70   // Suppose the "copy" op copies 5 bytes of data.  If the offset is big
71   // enough, it will take 5 bytes to encode the copy op.  Therefore the
72   // worst case here is a one-byte literal followed by a five-byte copy.
73   // I.e., 6 bytes of input turn into 7 bytes of "compressed" data.
74   //
75   // This last factor dominates the blowup, so the final estimate is:
76   return 32 + source_len + source_len/6;
77 }
78
79 enum {
80   LITERAL = 0,
81   COPY_1_BYTE_OFFSET = 1,  // 3 bit length + 3 bits of offset in opcode
82   COPY_2_BYTE_OFFSET = 2,
83   COPY_4_BYTE_OFFSET = 3
84 };
85
86 // Copy "len" bytes from "src" to "op", one byte at a time.  Used for
87 // handling COPY operations where the input and output regions may
88 // overlap.  For example, suppose:
89 //    src    == "ab"
90 //    op     == src + 2
91 //    len    == 20
92 // After IncrementalCopy(src, op, len), the result will have
93 // eleven copies of "ab"
94 //    ababababababababababab
95 // Note that this does not match the semantics of either memcpy()
96 // or memmove().
97 static inline void IncrementalCopy(const char* src, char* op, int len) {
98   DCHECK_GT(len, 0);
99   do {
100     *op++ = *src++;
101   } while (--len > 0);
102 }
103
104 // Equivalent to IncrementalCopy except that it can write up to ten extra
105 // bytes after the end of the copy, and that it is faster.
106 //
107 // The main part of this loop is a simple copy of eight bytes at a time until
108 // we've copied (at least) the requested amount of bytes.  However, if op and
109 // src are less than eight bytes apart (indicating a repeating pattern of
110 // length < 8), we first need to expand the pattern in order to get the correct
111 // results. For instance, if the buffer looks like this, with the eight-byte
112 // <src> and <op> patterns marked as intervals:
113 //
114 //    abxxxxxxxxxxxx
115 //    [------]           src
116 //      [------]         op
117 //
118 // a single eight-byte copy from <src> to <op> will repeat the pattern once,
119 // after which we can move <op> two bytes without moving <src>:
120 //
121 //    ababxxxxxxxxxx
122 //    [------]           src
123 //        [------]       op
124 //
125 // and repeat the exercise until the two no longer overlap.
126 //
127 // This allows us to do very well in the special case of one single byte
128 // repeated many times, without taking a big hit for more general cases.
129 //
130 // The worst case of extra writing past the end of the match occurs when
131 // op - src == 1 and len == 1; the last copy will read from byte positions
132 // [0..7] and write to [4..11], whereas it was only supposed to write to
133 // position 1. Thus, ten excess bytes.
134
135 namespace {
136
137 const int kMaxIncrementCopyOverflow = 10;
138
139 }  // namespace
140
141 static inline void IncrementalCopyFastPath(const char* src, char* op, int len) {
142   while (op - src < 8) {
143     UNALIGNED_STORE64(op, UNALIGNED_LOAD64(src));
144     len -= op - src;
145     op += op - src;
146   }
147   while (len > 0) {
148     UNALIGNED_STORE64(op, UNALIGNED_LOAD64(src));
149     src += 8;
150     op += 8;
151     len -= 8;
152   }
153 }
154
155 static inline char* EmitLiteral(char* op,
156                                 const char* literal,
157                                 int len,
158                                 bool allow_fast_path) {
159   int n = len - 1;      // Zero-length literals are disallowed
160   if (n < 60) {
161     // Fits in tag byte
162     *op++ = LITERAL | (n << 2);
163
164     // The vast majority of copies are below 16 bytes, for which a
165     // call to memcpy is overkill. This fast path can sometimes
166     // copy up to 15 bytes too much, but that is okay in the
167     // main loop, since we have a bit to go on for both sides:
168     //
169     //   - The input will always have kInputMarginBytes = 15 extra
170     //     available bytes, as long as we're in the main loop, and
171     //     if not, allow_fast_path = false.
172     //   - The output will always have 32 spare bytes (see
173     //     MaxCompressedLength).
174     if (allow_fast_path && len <= 16) {
175       UNALIGNED_STORE64(op, UNALIGNED_LOAD64(literal));
176       UNALIGNED_STORE64(op + 8, UNALIGNED_LOAD64(literal + 8));
177       return op + len;
178     }
179   } else {
180     // Encode in upcoming bytes
181     char* base = op;
182     int count = 0;
183     op++;
184     while (n > 0) {
185       *op++ = n & 0xff;
186       n >>= 8;
187       count++;
188     }
189     assert(count >= 1);
190     assert(count <= 4);
191     *base = LITERAL | ((59+count) << 2);
192   }
193   memcpy(op, literal, len);
194   return op + len;
195 }
196
197 static inline char* EmitCopyLessThan64(char* op, int offset, int len) {
198   DCHECK_LE(len, 64);
199   DCHECK_GE(len, 4);
200   DCHECK_LT(offset, 65536);
201
202   if ((len < 12) && (offset < 2048)) {
203     int len_minus_4 = len - 4;
204     assert(len_minus_4 < 8);            // Must fit in 3 bits
205     *op++ = COPY_1_BYTE_OFFSET | ((len_minus_4) << 2) | ((offset >> 8) << 5);
206     *op++ = offset & 0xff;
207   } else {
208     *op++ = COPY_2_BYTE_OFFSET | ((len-1) << 2);
209     LittleEndian::Store16(op, offset);
210     op += 2;
211   }
212   return op;
213 }
214
215 static inline char* EmitCopy(char* op, int offset, int len) {
216   // Emit 64 byte copies but make sure to keep at least four bytes reserved
217   while (len >= 68) {
218     op = EmitCopyLessThan64(op, offset, 64);
219     len -= 64;
220   }
221
222   // Emit an extra 60 byte copy if have too much data to fit in one copy
223   if (len > 64) {
224     op = EmitCopyLessThan64(op, offset, 60);
225     len -= 60;
226   }
227
228   // Emit remainder
229   op = EmitCopyLessThan64(op, offset, len);
230   return op;
231 }
232
233
234 bool GetUncompressedLength(const char* start, size_t n, size_t* result) {
235   uint32 v = 0;
236   const char* limit = start + n;
237   if (Varint::Parse32WithLimit(start, limit, &v) != NULL) {
238     *result = v;
239     return true;
240   } else {
241     return false;
242   }
243 }
244
245 namespace internal {
246 uint16* WorkingMemory::GetHashTable(size_t input_size, int* table_size) {
247   // Use smaller hash table when input.size() is smaller, since we
248   // fill the table, incurring O(hash table size) overhead for
249   // compression, and if the input is short, we won't need that
250   // many hash table entries anyway.
251   assert(kMaxHashTableSize >= 256);
252   int htsize = 256;
253   while (htsize < kMaxHashTableSize && htsize < input_size) {
254     htsize <<= 1;
255   }
256   CHECK_EQ(0, htsize & (htsize - 1)) << ": must be power of two";
257   CHECK_LE(htsize, kMaxHashTableSize) << ": hash table too large";
258
259   uint16* table;
260   if (htsize <= ARRAYSIZE(small_table_)) {
261     table = small_table_;
262   } else {
263     if (large_table_ == NULL) {
264       large_table_ = new uint16[kMaxHashTableSize];
265     }
266     table = large_table_;
267   }
268
269   *table_size = htsize;
270   memset(table, 0, htsize * sizeof(*table));
271   return table;
272 }
273 }  // end namespace internal
274
275 // For 0 <= offset <= 4, GetUint32AtOffset(UNALIGNED_LOAD64(p), offset) will
276 // equal UNALIGNED_LOAD32(p + offset).  Motivation: On x86-64 hardware we have
277 // empirically found that overlapping loads such as
278 //  UNALIGNED_LOAD32(p) ... UNALIGNED_LOAD32(p+1) ... UNALIGNED_LOAD32(p+2)
279 // are slower than UNALIGNED_LOAD64(p) followed by shifts and casts to uint32.
280 static inline uint32 GetUint32AtOffset(uint64 v, int offset) {
281   DCHECK(0 <= offset && offset <= 4) << offset;
282   return v >> (LittleEndian::IsLittleEndian() ? 8 * offset : 32 - 8 * offset);
283 }
284
285 // Flat array compression that does not emit the "uncompressed length"
286 // prefix. Compresses "input" string to the "*op" buffer.
287 //
288 // REQUIRES: "input" is at most "kBlockSize" bytes long.
289 // REQUIRES: "op" points to an array of memory that is at least
290 // "MaxCompressedLength(input.size())" in size.
291 // REQUIRES: All elements in "table[0..table_size-1]" are initialized to zero.
292 // REQUIRES: "table_size" is a power of two
293 //
294 // Returns an "end" pointer into "op" buffer.
295 // "end - op" is the compressed size of "input".
296 namespace internal {
297 char* CompressFragment(const char* const input,
298                        const size_t input_size,
299                        char* op,
300                        uint16* table,
301                        const int table_size) {
302   // "ip" is the input pointer, and "op" is the output pointer.
303   const char* ip = input;
304   CHECK_LE(input_size, kBlockSize);
305   CHECK_EQ(table_size & (table_size - 1), 0) << ": table must be power of two";
306   const int shift = 32 - Bits::Log2Floor(table_size);
307   DCHECK_EQ(kuint32max >> shift, table_size - 1);
308   const char* ip_end = input + input_size;
309   const char* base_ip = ip;
310   // Bytes in [next_emit, ip) will be emitted as literal bytes.  Or
311   // [next_emit, ip_end) after the main loop.
312   const char* next_emit = ip;
313
314   const int kInputMarginBytes = 15;
315   if (PREDICT_TRUE(input_size >= kInputMarginBytes)) {
316     const char* ip_limit = input + input_size - kInputMarginBytes;
317
318     for (uint32 next_hash = Hash(++ip, shift); ; ) {
319       DCHECK_LT(next_emit, ip);
320       // The body of this loop calls EmitLiteral once and then EmitCopy one or
321       // more times.  (The exception is that when we're close to exhausting
322       // the input we goto emit_remainder.)
323       //
324       // In the first iteration of this loop we're just starting, so
325       // there's nothing to copy, so calling EmitLiteral once is
326       // necessary.  And we only start a new iteration when the
327       // current iteration has determined that a call to EmitLiteral will
328       // precede the next call to EmitCopy (if any).
329       //
330       // Step 1: Scan forward in the input looking for a 4-byte-long match.
331       // If we get close to exhausting the input then goto emit_remainder.
332       //
333       // Heuristic match skipping: If 32 bytes are scanned with no matches
334       // found, start looking only at every other byte. If 32 more bytes are
335       // scanned, look at every third byte, etc.. When a match is found,
336       // immediately go back to looking at every byte. This is a small loss
337       // (~5% performance, ~0.1% density) for compressible data due to more
338       // bookkeeping, but for non-compressible data (such as JPEG) it's a huge
339       // win since the compressor quickly "realizes" the data is incompressible
340       // and doesn't bother looking for matches everywhere.
341       //
342       // The "skip" variable keeps track of how many bytes there are since the
343       // last match; dividing it by 32 (ie. right-shifting by five) gives the
344       // number of bytes to move ahead for each iteration.
345       uint32 skip = 32;
346
347       const char* next_ip = ip;
348       const char* candidate;
349       do {
350         ip = next_ip;
351         uint32 hash = next_hash;
352         DCHECK_EQ(hash, Hash(ip, shift));
353         uint32 bytes_between_hash_lookups = skip++ >> 5;
354         next_ip = ip + bytes_between_hash_lookups;
355         if (PREDICT_FALSE(next_ip > ip_limit)) {
356           goto emit_remainder;
357         }
358         next_hash = Hash(next_ip, shift);
359         candidate = base_ip + table[hash];
360         DCHECK_GE(candidate, base_ip);
361         DCHECK_LT(candidate, ip);
362
363         table[hash] = ip - base_ip;
364       } while (PREDICT_TRUE(UNALIGNED_LOAD32(ip) !=
365                             UNALIGNED_LOAD32(candidate)));
366
367       // Step 2: A 4-byte match has been found.  We'll later see if more
368       // than 4 bytes match.  But, prior to the match, input
369       // bytes [next_emit, ip) are unmatched.  Emit them as "literal bytes."
370       DCHECK_LE(next_emit + 16, ip_end);
371       op = EmitLiteral(op, next_emit, ip - next_emit, true);
372
373       // Step 3: Call EmitCopy, and then see if another EmitCopy could
374       // be our next move.  Repeat until we find no match for the
375       // input immediately after what was consumed by the last EmitCopy call.
376       //
377       // If we exit this loop normally then we need to call EmitLiteral next,
378       // though we don't yet know how big the literal will be.  We handle that
379       // by proceeding to the next iteration of the main loop.  We also can exit
380       // this loop via goto if we get close to exhausting the input.
381       uint64 input_bytes = 0;
382       uint32 candidate_bytes = 0;
383
384       do {
385         // We have a 4-byte match at ip, and no need to emit any
386         // "literal bytes" prior to ip.
387         const char* base = ip;
388         int matched = 4 + FindMatchLength(candidate + 4, ip + 4, ip_end);
389         ip += matched;
390         int offset = base - candidate;
391         DCHECK_EQ(0, memcmp(base, candidate, matched));
392         op = EmitCopy(op, offset, matched);
393         // We could immediately start working at ip now, but to improve
394         // compression we first update table[Hash(ip - 1, ...)].
395         const char* insert_tail = ip - 1;
396         next_emit = ip;
397         if (PREDICT_FALSE(ip >= ip_limit)) {
398           goto emit_remainder;
399         }
400         input_bytes = UNALIGNED_LOAD64(insert_tail);
401         uint32 prev_hash = HashBytes(GetUint32AtOffset(input_bytes, 0), shift);
402         table[prev_hash] = ip - base_ip - 1;
403         uint32 cur_hash = HashBytes(GetUint32AtOffset(input_bytes, 1), shift);
404         candidate = base_ip + table[cur_hash];
405         candidate_bytes = UNALIGNED_LOAD32(candidate);
406         table[cur_hash] = ip - base_ip;
407       } while (GetUint32AtOffset(input_bytes, 1) == candidate_bytes);
408
409       next_hash = HashBytes(GetUint32AtOffset(input_bytes, 2), shift);
410       ++ip;
411     }
412   }
413
414  emit_remainder:
415   // Emit the remaining bytes as a literal
416   if (next_emit < ip_end) {
417     op = EmitLiteral(op, next_emit, ip_end - next_emit, false);
418   }
419
420   return op;
421 }
422 }  // end namespace internal
423
424 // Signature of output types needed by decompression code.
425 // The decompression code is templatized on a type that obeys this
426 // signature so that we do not pay virtual function call overhead in
427 // the middle of a tight decompression loop.
428 //
429 // class DecompressionWriter {
430 //  public:
431 //   // Called before decompression
432 //   void SetExpectedLength(size_t length);
433 //
434 //   // Called after decompression
435 //   bool CheckLength() const;
436 //
437 //   // Called repeatedly during decompression
438 //   bool Append(const char* ip, uint32 length, bool allow_fast_path);
439 //   bool AppendFromSelf(uint32 offset, uint32 length);
440 // };
441 //
442 // "allow_fast_path" is a parameter that says if there is at least 16
443 // readable bytes in "ip". It is currently only used by SnappyArrayWriter.
444
445 // -----------------------------------------------------------------------
446 // Lookup table for decompression code.  Generated by ComputeTable() below.
447 // -----------------------------------------------------------------------
448
449 // Mapping from i in range [0,4] to a mask to extract the bottom 8*i bits
450 static const uint32 wordmask[] = {
451   0u, 0xffu, 0xffffu, 0xffffffu, 0xffffffffu
452 };
453
454 // Data stored per entry in lookup table:
455 //      Range   Bits-used       Description
456 //      ------------------------------------
457 //      1..64   0..7            Literal/copy length encoded in opcode byte
458 //      0..7    8..10           Copy offset encoded in opcode byte / 256
459 //      0..4    11..13          Extra bytes after opcode
460 //
461 // We use eight bits for the length even though 7 would have sufficed
462 // because of efficiency reasons:
463 //      (1) Extracting a byte is faster than a bit-field
464 //      (2) It properly aligns copy offset so we do not need a <<8
465 static const uint16 char_table[256] = {
466   0x0001, 0x0804, 0x1001, 0x2001, 0x0002, 0x0805, 0x1002, 0x2002,
467   0x0003, 0x0806, 0x1003, 0x2003, 0x0004, 0x0807, 0x1004, 0x2004,
468   0x0005, 0x0808, 0x1005, 0x2005, 0x0006, 0x0809, 0x1006, 0x2006,
469   0x0007, 0x080a, 0x1007, 0x2007, 0x0008, 0x080b, 0x1008, 0x2008,
470   0x0009, 0x0904, 0x1009, 0x2009, 0x000a, 0x0905, 0x100a, 0x200a,
471   0x000b, 0x0906, 0x100b, 0x200b, 0x000c, 0x0907, 0x100c, 0x200c,
472   0x000d, 0x0908, 0x100d, 0x200d, 0x000e, 0x0909, 0x100e, 0x200e,
473   0x000f, 0x090a, 0x100f, 0x200f, 0x0010, 0x090b, 0x1010, 0x2010,
474   0x0011, 0x0a04, 0x1011, 0x2011, 0x0012, 0x0a05, 0x1012, 0x2012,
475   0x0013, 0x0a06, 0x1013, 0x2013, 0x0014, 0x0a07, 0x1014, 0x2014,
476   0x0015, 0x0a08, 0x1015, 0x2015, 0x0016, 0x0a09, 0x1016, 0x2016,
477   0x0017, 0x0a0a, 0x1017, 0x2017, 0x0018, 0x0a0b, 0x1018, 0x2018,
478   0x0019, 0x0b04, 0x1019, 0x2019, 0x001a, 0x0b05, 0x101a, 0x201a,
479   0x001b, 0x0b06, 0x101b, 0x201b, 0x001c, 0x0b07, 0x101c, 0x201c,
480   0x001d, 0x0b08, 0x101d, 0x201d, 0x001e, 0x0b09, 0x101e, 0x201e,
481   0x001f, 0x0b0a, 0x101f, 0x201f, 0x0020, 0x0b0b, 0x1020, 0x2020,
482   0x0021, 0x0c04, 0x1021, 0x2021, 0x0022, 0x0c05, 0x1022, 0x2022,
483   0x0023, 0x0c06, 0x1023, 0x2023, 0x0024, 0x0c07, 0x1024, 0x2024,
484   0x0025, 0x0c08, 0x1025, 0x2025, 0x0026, 0x0c09, 0x1026, 0x2026,
485   0x0027, 0x0c0a, 0x1027, 0x2027, 0x0028, 0x0c0b, 0x1028, 0x2028,
486   0x0029, 0x0d04, 0x1029, 0x2029, 0x002a, 0x0d05, 0x102a, 0x202a,
487   0x002b, 0x0d06, 0x102b, 0x202b, 0x002c, 0x0d07, 0x102c, 0x202c,
488   0x002d, 0x0d08, 0x102d, 0x202d, 0x002e, 0x0d09, 0x102e, 0x202e,
489   0x002f, 0x0d0a, 0x102f, 0x202f, 0x0030, 0x0d0b, 0x1030, 0x2030,
490   0x0031, 0x0e04, 0x1031, 0x2031, 0x0032, 0x0e05, 0x1032, 0x2032,
491   0x0033, 0x0e06, 0x1033, 0x2033, 0x0034, 0x0e07, 0x1034, 0x2034,
492   0x0035, 0x0e08, 0x1035, 0x2035, 0x0036, 0x0e09, 0x1036, 0x2036,
493   0x0037, 0x0e0a, 0x1037, 0x2037, 0x0038, 0x0e0b, 0x1038, 0x2038,
494   0x0039, 0x0f04, 0x1039, 0x2039, 0x003a, 0x0f05, 0x103a, 0x203a,
495   0x003b, 0x0f06, 0x103b, 0x203b, 0x003c, 0x0f07, 0x103c, 0x203c,
496   0x0801, 0x0f08, 0x103d, 0x203d, 0x1001, 0x0f09, 0x103e, 0x203e,
497   0x1801, 0x0f0a, 0x103f, 0x203f, 0x2001, 0x0f0b, 0x1040, 0x2040
498 };
499
500 // In debug mode, allow optional computation of the table at startup.
501 // Also, check that the decompression table is correct.
502 #ifndef NDEBUG
503 DEFINE_bool(snappy_dump_decompression_table, false,
504             "If true, we print the decompression table at startup.");
505
506 static uint16 MakeEntry(unsigned int extra,
507                         unsigned int len,
508                         unsigned int copy_offset) {
509   // Check that all of the fields fit within the allocated space
510   DCHECK_EQ(extra,       extra & 0x7);          // At most 3 bits
511   DCHECK_EQ(copy_offset, copy_offset & 0x7);    // At most 3 bits
512   DCHECK_EQ(len,         len & 0x7f);           // At most 7 bits
513   return len | (copy_offset << 8) | (extra << 11);
514 }
515
516 static void ComputeTable() {
517   uint16 dst[256];
518
519   // Place invalid entries in all places to detect missing initialization
520   int assigned = 0;
521   for (int i = 0; i < 256; i++) {
522     dst[i] = 0xffff;
523   }
524
525   // Small LITERAL entries.  We store (len-1) in the top 6 bits.
526   for (unsigned int len = 1; len <= 60; len++) {
527     dst[LITERAL | ((len-1) << 2)] = MakeEntry(0, len, 0);
528     assigned++;
529   }
530
531   // Large LITERAL entries.  We use 60..63 in the high 6 bits to
532   // encode the number of bytes of length info that follow the opcode.
533   for (unsigned int extra_bytes = 1; extra_bytes <= 4; extra_bytes++) {
534     // We set the length field in the lookup table to 1 because extra
535     // bytes encode len-1.
536     dst[LITERAL | ((extra_bytes+59) << 2)] = MakeEntry(extra_bytes, 1, 0);
537     assigned++;
538   }
539
540   // COPY_1_BYTE_OFFSET.
541   //
542   // The tag byte in the compressed data stores len-4 in 3 bits, and
543   // offset/256 in 5 bits.  offset%256 is stored in the next byte.
544   //
545   // This format is used for length in range [4..11] and offset in
546   // range [0..2047]
547   for (unsigned int len = 4; len < 12; len++) {
548     for (unsigned int offset = 0; offset < 2048; offset += 256) {
549       dst[COPY_1_BYTE_OFFSET | ((len-4)<<2) | ((offset>>8)<<5)] =
550         MakeEntry(1, len, offset>>8);
551       assigned++;
552     }
553   }
554
555   // COPY_2_BYTE_OFFSET.
556   // Tag contains len-1 in top 6 bits, and offset in next two bytes.
557   for (unsigned int len = 1; len <= 64; len++) {
558     dst[COPY_2_BYTE_OFFSET | ((len-1)<<2)] = MakeEntry(2, len, 0);
559     assigned++;
560   }
561
562   // COPY_4_BYTE_OFFSET.
563   // Tag contents len-1 in top 6 bits, and offset in next four bytes.
564   for (unsigned int len = 1; len <= 64; len++) {
565     dst[COPY_4_BYTE_OFFSET | ((len-1)<<2)] = MakeEntry(4, len, 0);
566     assigned++;
567   }
568
569   // Check that each entry was initialized exactly once.
570   CHECK_EQ(assigned, 256);
571   for (int i = 0; i < 256; i++) {
572     CHECK_NE(dst[i], 0xffff);
573   }
574
575   if (FLAGS_snappy_dump_decompression_table) {
576     printf("static const uint16 char_table[256] = {\n  ");
577     for (int i = 0; i < 256; i++) {
578       printf("0x%04x%s",
579              dst[i],
580              ((i == 255) ? "\n" : (((i%8) == 7) ? ",\n  " : ", ")));
581     }
582     printf("};\n");
583   }
584
585   // Check that computed table matched recorded table
586   for (int i = 0; i < 256; i++) {
587     CHECK_EQ(dst[i], char_table[i]);
588   }
589 }
590 REGISTER_MODULE_INITIALIZER(snappy, ComputeTable());
591 #endif /* !NDEBUG */
592
593 // Helper class for decompression
594 class SnappyDecompressor {
595  private:
596   Source*       reader_;         // Underlying source of bytes to decompress
597   const char*   ip_;             // Points to next buffered byte
598   const char*   ip_limit_;       // Points just past buffered bytes
599   uint32        peeked_;         // Bytes peeked from reader (need to skip)
600   bool          eof_;            // Hit end of input without an error?
601   char          scratch_[5];     // Temporary buffer for PeekFast() boundaries
602
603   // Ensure that all of the tag metadata for the next tag is available
604   // in [ip_..ip_limit_-1].  Also ensures that [ip,ip+4] is readable even
605   // if (ip_limit_ - ip_ < 5).
606   //
607   // Returns true on success, false on error or end of input.
608   bool RefillTag();
609
610  public:
611   explicit SnappyDecompressor(Source* reader)
612       : reader_(reader),
613         ip_(NULL),
614         ip_limit_(NULL),
615         peeked_(0),
616         eof_(false) {
617   }
618
619   ~SnappyDecompressor() {
620     // Advance past any bytes we peeked at from the reader
621     reader_->Skip(peeked_);
622   }
623
624   // Returns true iff we have hit the end of the input without an error.
625   bool eof() const {
626     return eof_;
627   }
628
629   // Read the uncompressed length stored at the start of the compressed data.
630   // On succcess, stores the length in *result and returns true.
631   // On failure, returns false.
632   bool ReadUncompressedLength(uint32* result) {
633     DCHECK(ip_ == NULL);       // Must not have read anything yet
634     // Length is encoded in 1..5 bytes
635     *result = 0;
636     uint32 shift = 0;
637     while (true) {
638       if (shift >= 32) return false;
639       size_t n;
640       const char* ip = reader_->Peek(&n);
641       if (n == 0) return false;
642       const unsigned char c = *(reinterpret_cast<const unsigned char*>(ip));
643       reader_->Skip(1);
644       *result |= static_cast<uint32>(c & 0x7f) << shift;
645       if (c < 128) {
646         break;
647       }
648       shift += 7;
649     }
650     return true;
651   }
652
653   // Process the next item found in the input.
654   // Returns true if successful, false on error or end of input.
655   template <class Writer>
656   void DecompressAllTags(Writer* writer) {
657     const char* ip = ip_;
658     for ( ;; ) {
659       if (ip_limit_ - ip < 5) {
660         ip_ = ip;
661         if (!RefillTag()) return;
662         ip = ip_;
663       }
664
665       const unsigned char c = *(reinterpret_cast<const unsigned char*>(ip++));
666       const uint32 entry = char_table[c];
667       const uint32 trailer = LittleEndian::Load32(ip) & wordmask[entry >> 11];
668       ip += entry >> 11;
669       const uint32 length = entry & 0xff;
670
671       if ((c & 0x3) == LITERAL) {
672         uint32 literal_length = length + trailer;
673         uint32 avail = ip_limit_ - ip;
674         while (avail < literal_length) {
675           bool allow_fast_path = (avail >= 16);
676           if (!writer->Append(ip, avail, allow_fast_path)) return;
677           literal_length -= avail;
678           reader_->Skip(peeked_);
679           size_t n;
680           ip = reader_->Peek(&n);
681           avail = n;
682           peeked_ = avail;
683           if (avail == 0) return;  // Premature end of input
684           ip_limit_ = ip + avail;
685         }
686         bool allow_fast_path = (avail >= 16);
687         if (!writer->Append(ip, literal_length, allow_fast_path)) {
688           return;
689         }
690         ip += literal_length;
691       } else {
692         // copy_offset/256 is encoded in bits 8..10.  By just fetching
693         // those bits, we get copy_offset (since the bit-field starts at
694         // bit 8).
695         const uint32 copy_offset = entry & 0x700;
696         if (!writer->AppendFromSelf(copy_offset + trailer, length)) {
697           return;
698         }
699       }
700     }
701   }
702 };
703
704 bool SnappyDecompressor::RefillTag() {
705   const char* ip = ip_;
706   if (ip == ip_limit_) {
707     // Fetch a new fragment from the reader
708     reader_->Skip(peeked_);   // All peeked bytes are used up
709     size_t n;
710     ip = reader_->Peek(&n);
711     peeked_ = n;
712     if (n == 0) {
713       eof_ = true;
714       return false;
715     }
716     ip_limit_ = ip + n;
717   }
718
719   // Read the tag character
720   DCHECK_LT(ip, ip_limit_);
721   const unsigned char c = *(reinterpret_cast<const unsigned char*>(ip));
722   const uint32 entry = char_table[c];
723   const uint32 needed = (entry >> 11) + 1;  // +1 byte for 'c'
724   DCHECK_LE(needed, sizeof(scratch_));
725
726   // Read more bytes from reader if needed
727   uint32 nbuf = ip_limit_ - ip;
728   if (nbuf < needed) {
729     // Stitch together bytes from ip and reader to form the word
730     // contents.  We store the needed bytes in "scratch_".  They
731     // will be consumed immediately by the caller since we do not
732     // read more than we need.
733     memmove(scratch_, ip, nbuf);
734     reader_->Skip(peeked_);  // All peeked bytes are used up
735     peeked_ = 0;
736     while (nbuf < needed) {
737       size_t length;
738       const char* src = reader_->Peek(&length);
739       if (length == 0) return false;
740       uint32 to_add = min<uint32>(needed - nbuf, length);
741       memcpy(scratch_ + nbuf, src, to_add);
742       nbuf += to_add;
743       reader_->Skip(to_add);
744     }
745     DCHECK_EQ(nbuf, needed);
746     ip_ = scratch_;
747     ip_limit_ = scratch_ + needed;
748   } else if (nbuf < 5) {
749     // Have enough bytes, but move into scratch_ so that we do not
750     // read past end of input
751     memmove(scratch_, ip, nbuf);
752     reader_->Skip(peeked_);  // All peeked bytes are used up
753     peeked_ = 0;
754     ip_ = scratch_;
755     ip_limit_ = scratch_ + nbuf;
756   } else {
757     // Pass pointer to buffer returned by reader_.
758     ip_ = ip;
759   }
760   return true;
761 }
762
763 template <typename Writer>
764 static bool InternalUncompress(Source* r,
765                                Writer* writer,
766                                uint32 max_len) {
767   // Read the uncompressed length from the front of the compressed input
768   SnappyDecompressor decompressor(r);
769   uint32 uncompressed_len = 0;
770   if (!decompressor.ReadUncompressedLength(&uncompressed_len)) return false;
771   // Protect against possible DoS attack
772   if (static_cast<uint64>(uncompressed_len) > max_len) {
773     return false;
774   }
775
776   writer->SetExpectedLength(uncompressed_len);
777
778   // Process the entire input
779   decompressor.DecompressAllTags(writer);
780   return (decompressor.eof() && writer->CheckLength());
781 }
782
783 bool GetUncompressedLength(Source* source, uint32* result) {
784   SnappyDecompressor decompressor(source);
785   return decompressor.ReadUncompressedLength(result);
786 }
787
788 size_t Compress(Source* reader, Sink* writer) {
789   size_t written = 0;
790   int N = reader->Available();
791   char ulength[Varint::kMax32];
792   char* p = Varint::Encode32(ulength, N);
793   writer->Append(ulength, p-ulength);
794   written += (p - ulength);
795
796   internal::WorkingMemory wmem;
797   char* scratch = NULL;
798   char* scratch_output = NULL;
799
800   while (N > 0) {
801     // Get next block to compress (without copying if possible)
802     size_t fragment_size;
803     const char* fragment = reader->Peek(&fragment_size);
804     DCHECK_NE(fragment_size, 0) << ": premature end of input";
805     const int num_to_read = min(N, kBlockSize);
806     size_t bytes_read = fragment_size;
807
808     int pending_advance = 0;
809     if (bytes_read >= num_to_read) {
810       // Buffer returned by reader is large enough
811       pending_advance = num_to_read;
812       fragment_size = num_to_read;
813     } else {
814       // Read into scratch buffer
815       if (scratch == NULL) {
816         // If this is the last iteration, we want to allocate N bytes
817         // of space, otherwise the max possible kBlockSize space.
818         // num_to_read contains exactly the correct value
819         scratch = new char[num_to_read];
820       }
821       memcpy(scratch, fragment, bytes_read);
822       reader->Skip(bytes_read);
823
824       while (bytes_read < num_to_read) {
825         fragment = reader->Peek(&fragment_size);
826         size_t n = min<size_t>(fragment_size, num_to_read - bytes_read);
827         memcpy(scratch + bytes_read, fragment, n);
828         bytes_read += n;
829         reader->Skip(n);
830       }
831       DCHECK_EQ(bytes_read, num_to_read);
832       fragment = scratch;
833       fragment_size = num_to_read;
834     }
835     DCHECK_EQ(fragment_size, num_to_read);
836
837     // Get encoding table for compression
838     int table_size;
839     uint16* table = wmem.GetHashTable(num_to_read, &table_size);
840
841     // Compress input_fragment and append to dest
842     const int max_output = MaxCompressedLength(num_to_read);
843
844     // Need a scratch buffer for the output, in case the byte sink doesn't
845     // have room for us directly.
846     if (scratch_output == NULL) {
847       scratch_output = new char[max_output];
848     } else {
849       // Since we encode kBlockSize regions followed by a region
850       // which is <= kBlockSize in length, a previously allocated
851       // scratch_output[] region is big enough for this iteration.
852     }
853     char* dest = writer->GetAppendBuffer(max_output, scratch_output);
854     char* end = internal::CompressFragment(fragment, fragment_size,
855                                            dest, table, table_size);
856     writer->Append(dest, end - dest);
857     written += (end - dest);
858
859     N -= num_to_read;
860     reader->Skip(pending_advance);
861   }
862
863   delete[] scratch;
864   delete[] scratch_output;
865
866   return written;
867 }
868
869 // -----------------------------------------------------------------------
870 // Flat array interfaces
871 // -----------------------------------------------------------------------
872
873 // A type that writes to a flat array.
874 // Note that this is not a "ByteSink", but a type that matches the
875 // Writer template argument to SnappyDecompressor::DecompressAllTags().
876 class SnappyArrayWriter {
877  private:
878   char* base_;
879   char* op_;
880   char* op_limit_;
881
882  public:
883   inline explicit SnappyArrayWriter(char* dst)
884       : base_(dst),
885         op_(dst) {
886   }
887
888   inline void SetExpectedLength(size_t len) {
889     op_limit_ = op_ + len;
890   }
891
892   inline bool CheckLength() const {
893     return op_ == op_limit_;
894   }
895
896   inline bool Append(const char* ip, uint32 len, bool allow_fast_path) {
897     char* op = op_;
898     const int space_left = op_limit_ - op;
899     if (allow_fast_path && len <= 16 && space_left >= 16) {
900       // Fast path, used for the majority (about 90%) of dynamic invocations.
901       UNALIGNED_STORE64(op, UNALIGNED_LOAD64(ip));
902       UNALIGNED_STORE64(op + 8, UNALIGNED_LOAD64(ip + 8));
903     } else {
904       if (space_left < len) {
905         return false;
906       }
907       memcpy(op, ip, len);
908     }
909     op_ = op + len;
910     return true;
911   }
912
913   inline bool AppendFromSelf(uint32 offset, uint32 len) {
914     char* op = op_;
915     const int space_left = op_limit_ - op;
916
917     if (op - base_ <= offset - 1u) {  // -1u catches offset==0
918       return false;
919     }
920     if (len <= 16 && offset >= 8 && space_left >= 16) {
921       // Fast path, used for the majority (70-80%) of dynamic invocations.
922       UNALIGNED_STORE64(op, UNALIGNED_LOAD64(op - offset));
923       UNALIGNED_STORE64(op + 8, UNALIGNED_LOAD64(op - offset + 8));
924     } else {
925       if (space_left >= len + kMaxIncrementCopyOverflow) {
926         IncrementalCopyFastPath(op - offset, op, len);
927       } else {
928         if (space_left < len) {
929           return false;
930         }
931         IncrementalCopy(op - offset, op, len);
932       }
933     }
934
935     op_ = op + len;
936     return true;
937   }
938 };
939
940 bool RawUncompress(const char* compressed, size_t n, char* uncompressed) {
941   ByteArraySource reader(compressed, n);
942   return RawUncompress(&reader, uncompressed);
943 }
944
945 bool RawUncompress(Source* compressed, char* uncompressed) {
946   SnappyArrayWriter output(uncompressed);
947   return InternalUncompress(compressed, &output, kuint32max);
948 }
949
950 bool Uncompress(const char* compressed, size_t n, string* uncompressed) {
951   size_t ulength;
952   if (!GetUncompressedLength(compressed, n, &ulength)) {
953     return false;
954   }
955   // Protect against possible DoS attack
956   if ((static_cast<uint64>(ulength) + uncompressed->size()) >
957       uncompressed->max_size()) {
958     return false;
959   }
960   STLStringResizeUninitialized(uncompressed, ulength);
961   return RawUncompress(compressed, n, string_as_array(uncompressed));
962 }
963
964
965 // A Writer that drops everything on the floor and just does validation
966 class SnappyDecompressionValidator {
967  private:
968   size_t expected_;
969   size_t produced_;
970
971  public:
972   inline SnappyDecompressionValidator() : produced_(0) { }
973   inline void SetExpectedLength(size_t len) {
974     expected_ = len;
975   }
976   inline bool CheckLength() const {
977     return expected_ == produced_;
978   }
979   inline bool Append(const char* ip, uint32 len, bool allow_fast_path) {
980     produced_ += len;
981     return produced_ <= expected_;
982   }
983   inline bool AppendFromSelf(uint32 offset, uint32 len) {
984     if (produced_ <= offset - 1u) return false;  // -1u catches offset==0
985     produced_ += len;
986     return produced_ <= expected_;
987   }
988 };
989
990 bool IsValidCompressedBuffer(const char* compressed, size_t n) {
991   ByteArraySource reader(compressed, n);
992   SnappyDecompressionValidator writer;
993   return InternalUncompress(&reader, &writer, kuint32max);
994 }
995
996 void RawCompress(const char* input,
997                  size_t input_length,
998                  char* compressed,
999                  size_t* compressed_length) {
1000   ByteArraySource reader(input, input_length);
1001   UncheckedByteArraySink writer(compressed);
1002   Compress(&reader, &writer);
1003
1004   // Compute how many bytes were added
1005   *compressed_length = (writer.CurrentDestination() - compressed);
1006 }
1007
1008 size_t Compress(const char* input, size_t input_length, string* compressed) {
1009   // Pre-grow the buffer to the max length of the compressed output
1010   compressed->resize(MaxCompressedLength(input_length));
1011
1012   size_t compressed_length;
1013   RawCompress(input, input_length, string_as_array(compressed),
1014               &compressed_length);
1015   compressed->resize(compressed_length);
1016   return compressed_length;
1017 }
1018
1019
1020 } // end namespace snappy
1021