snappy.cc:_ZN6snappy8internalL15FindMatchLengthEPKcS2_S2_Pm: 181| 3.29M| uint64_t* data) { 182| 3.29M| assert(s2_limit >= s2); 183| 3.29M| size_t matched = 0; 184| | 185| | // This block isn't necessary for correctness; we could just start looping 186| | // immediately. As an optimization though, it is useful. It creates some not 187| | // uncommon code paths that determine, without extra effort, whether the match 188| | // length is less than 8. In short, we are hoping to avoid a conditional 189| | // branch, and perhaps get better code layout from the C++ compiler. 190| 3.29M| if (SNAPPY_PREDICT_TRUE(s2 <= s2_limit - 16)) { ------------------ | | 95| 3.29M|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 3.28M, False: 1.25k] | | ------------------ ------------------ 191| 3.28M| uint64_t a1 = UNALIGNED_LOAD64(s1); 192| 3.28M| uint64_t a2 = UNALIGNED_LOAD64(s2); 193| 3.28M| if (SNAPPY_PREDICT_TRUE(a1 != a2)) { ------------------ | | 95| 3.28M|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 2.29M, False: 996k] | | ------------------ ------------------ 194| | // This code is critical for performance. The reason is that it determines 195| | // how much to advance `ip` (s2). This obviously depends on both the loads 196| | // from the `candidate` (s1) and `ip`. Furthermore the next `candidate` 197| | // depends on the advanced `ip` calculated here through a load, hash and 198| | // new candidate hash lookup (a lot of cycles). This makes s1 (ie. 199| | // `candidate`) the variable that limits throughput. This is the reason we 200| | // go through hoops to have this function update `data` for the next iter. 201| | // The straightforward code would use *data, given by 202| | // 203| | // *data = UNALIGNED_LOAD64(s2 + matched_bytes) (Latency of 5 cycles), 204| | // 205| | // as input for the hash table lookup to find next candidate. However 206| | // this forces the load on the data dependency chain of s1, because 207| | // matched_bytes directly depends on s1. However matched_bytes is 0..7, so 208| | // we can also calculate *data by 209| | // 210| | // *data = AlignRight(UNALIGNED_LOAD64(s2), UNALIGNED_LOAD64(s2 + 8), 211| | // matched_bytes); 212| | // 213| | // The loads do not depend on s1 anymore and are thus off the bottleneck. 214| | // The straightforward implementation on x86_64 would be to use 215| | // 216| | // shrd rax, rdx, cl (cl being matched_bytes * 8) 217| | // 218| | // unfortunately shrd with a variable shift has a 4 cycle latency. So this 219| | // only wins 1 cycle. The BMI2 shrx instruction is a 1 cycle variable 220| | // shift instruction but can only shift 64 bits. If we focus on just 221| | // obtaining the least significant 4 bytes, we can obtain this by 222| | // 223| | // *data = ConditionalMove(matched_bytes < 4, UNALIGNED_LOAD64(s2), 224| | // UNALIGNED_LOAD64(s2 + 4) >> ((matched_bytes & 3) * 8); 225| | // 226| | // Writen like above this is not a big win, the conditional move would be 227| | // a cmp followed by a cmov (2 cycles) followed by a shift (1 cycle). 228| | // However matched_bytes < 4 is equal to 229| | // static_cast(xorval) != 0. Writen that way, the conditional 230| | // move (2 cycles) can execute in parallel with FindLSBSetNonZero64 231| | // (tzcnt), which takes 3 cycles. 232| 2.29M| uint64_t xorval = a1 ^ a2; 233| 2.29M| int shift = Bits::FindLSBSetNonZero64(xorval); 234| 2.29M| size_t matched_bytes = shift >> 3; 235| 2.29M| uint64_t a3 = UNALIGNED_LOAD64(s2 + 4); 236| |#ifndef __x86_64__ 237| | a2 = static_cast(xorval) == 0 ? a3 : a2; 238| |#else 239| | // Ideally this would just be 240| | // 241| | // a2 = static_cast(xorval) == 0 ? a3 : a2; 242| | // 243| | // However clang correctly infers that the above statement participates on 244| | // a critical data dependency chain and thus, unfortunately, refuses to 245| | // use a conditional move (it's tuned to cut data dependencies). In this 246| | // case there is a longer parallel chain anyway AND this will be fairly 247| | // unpredictable. 248| 2.29M| asm("testl %k2, %k2\n\t" 249| 2.29M| "cmovzq %1, %0\n\t" 250| 2.29M| : "+r"(a2) 251| 2.29M| : "r"(a3), "r"(xorval) 252| 2.29M| : "cc"); 253| 2.29M|#endif 254| 2.29M| *data = a2 >> (shift & (3 * 8)); 255| 2.29M| return std::pair(matched_bytes, true); 256| 2.29M| } else { 257| 996k| matched = 8; 258| 996k| s2 += 8; 259| 996k| } 260| 3.28M| } 261| 997k| SNAPPY_PREFETCH(s1 + 64); ------------------ | | 109| 997k|#define SNAPPY_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 3) ------------------ 262| 997k| SNAPPY_PREFETCH(s2 + 64); ------------------ | | 109| 997k|#define SNAPPY_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 3) ------------------ 263| | 264| | // Find out how long the match is. We loop over the data 64 bits at a 265| | // time until we find a 64-bit block that doesn't match; then we find 266| | // the first non-matching bit and use that to calculate the total 267| | // length of the match. 268| 9.90M| while (SNAPPY_PREDICT_TRUE(s2 <= s2_limit - 16)) { ------------------ | | 95| 9.90M|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 9.90M, False: 2.71k] | | ------------------ ------------------ 269| 9.90M| uint64_t a1 = UNALIGNED_LOAD64(s1 + matched); 270| 9.90M| uint64_t a2 = UNALIGNED_LOAD64(s2); 271| 9.90M| if (a1 == a2) { ------------------ | Branch (271:9): [True: 8.90M, False: 994k] ------------------ 272| 8.90M| s2 += 8; 273| 8.90M| matched += 8; 274| 8.90M| } else { 275| 994k| uint64_t xorval = a1 ^ a2; 276| 994k| int shift = Bits::FindLSBSetNonZero64(xorval); 277| 994k| size_t matched_bytes = shift >> 3; 278| 994k| uint64_t a3 = UNALIGNED_LOAD64(s2 + 4); 279| |#ifndef __x86_64__ 280| | a2 = static_cast(xorval) == 0 ? a3 : a2; 281| |#else 282| 994k| asm("testl %k2, %k2\n\t" 283| 994k| "cmovzq %1, %0\n\t" 284| 994k| : "+r"(a2) 285| 994k| : "r"(a3), "r"(xorval) 286| 994k| : "cc"); 287| 994k|#endif 288| 994k| *data = a2 >> (shift & (3 * 8)); 289| 994k| matched += matched_bytes; 290| 994k| assert(matched >= 8); 291| 994k| return std::pair(matched, false); 292| 994k| } 293| 9.90M| } 294| 21.0k| while (SNAPPY_PREDICT_TRUE(s2 < s2_limit)) { ------------------ | | 95| 21.0k|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 19.7k, False: 1.33k] | | ------------------ ------------------ 295| 19.7k| if (s1[matched] == *s2) { ------------------ | Branch (295:9): [True: 18.3k, False: 1.38k] ------------------ 296| 18.3k| ++s2; 297| 18.3k| ++matched; 298| 18.3k| } else { 299| 1.38k| if (s2 <= s2_limit - 8) { ------------------ | Branch (299:11): [True: 1.06k, False: 319] ------------------ 300| 1.06k| *data = UNALIGNED_LOAD64(s2); 301| 1.06k| } 302| 1.38k| return std::pair(matched, matched < 8); 303| 1.38k| } 304| 19.7k| } 305| 1.33k| return std::pair(matched, matched < 8); 306| 2.71k|} snappy.cc:_ZN6snappy8internalL20FindMatchLengthPlainEPKcS2_S2_: 338| 4.21M| const char* s2_limit) { 339| | // Implementation based on the x86-64 version, above. 340| 4.21M| assert(s2_limit >= s2); 341| 4.21M| int matched = 0; 342| | 343| 15.9M| while (s2 <= s2_limit - 8 && ------------------ | Branch (343:10): [True: 15.9M, False: 1.97k] ------------------ 344| 15.9M| UNALIGNED_LOAD64(s2) == UNALIGNED_LOAD64(s1 + matched)) { ------------------ | Branch (344:10): [True: 11.7M, False: 4.21M] ------------------ 345| 11.7M| s2 += 8; 346| 11.7M| matched += 8; 347| 11.7M| } 348| 4.21M| if (LittleEndian::IsLittleEndian() && s2 <= s2_limit - 8) { ------------------ | Branch (348:7): [Folded - Ignored] | Branch (348:41): [True: 4.21M, False: 1.97k] ------------------ 349| 4.21M| uint64_t x = UNALIGNED_LOAD64(s2) ^ UNALIGNED_LOAD64(s1 + matched); 350| 4.21M| int matching_bits = Bits::FindLSBSetNonZero64(x); 351| 4.21M| matched += matching_bits >> 3; 352| 4.21M| s2 += matching_bits >> 3; 353| 4.21M| } else { 354| 8.22k| while ((s2 < s2_limit) && (s1[matched] == *s2)) { ------------------ | Branch (354:12): [True: 6.55k, False: 1.67k] | Branch (354:31): [True: 6.24k, False: 302] ------------------ 355| 6.24k| ++s2; 356| 6.24k| ++matched; 357| 6.24k| } 358| 1.97k| } 359| 4.21M| return matched; 360| 4.21M|} _ZNK6snappy8internal13WorkingMemory16GetScratchOutputEv: 128| 9.73k| char* GetScratchOutput() const { return output_; } _ZN6snappy6SourceD2Ev: 36| 15.7k|Source::~Source() = default; _ZN6snappy4SinkD2Ev: 38| 5.23k|Sink::~Sink() = default; _ZNK6snappy15ByteArraySource9AvailableEv: 68| 15.7k|size_t ByteArraySource::Available() const { return left_; } _ZN6snappy15ByteArraySource4PeekEPm: 70| 48.3k|const char* ByteArraySource::Peek(size_t* len) { 71| 48.3k| *len = left_; 72| 48.3k| return ptr_; 73| 48.3k|} _ZN6snappy15ByteArraySource4SkipEm: 75| 62.6k|void ByteArraySource::Skip(size_t n) { 76| 62.6k| left_ -= n; 77| 62.6k| ptr_ += n; 78| 62.6k|} _ZN6snappy22UncheckedByteArraySink6AppendEPKcm: 82| 14.9k|void UncheckedByteArraySink::Append(const char* data, size_t n) { 83| | // Do no copying if the caller filled in the result of GetAppendBuffer() 84| 14.9k| if (data != dest_) { ------------------ | Branch (84:7): [True: 5.23k, False: 9.73k] ------------------ 85| 5.23k| std::memcpy(dest_, data, n); 86| 5.23k| } 87| 14.9k| dest_ += n; 88| 14.9k|} _ZN6snappy22UncheckedByteArraySink15GetAppendBufferEmPc: 90| 9.73k|char* UncheckedByteArraySink::GetAppendBuffer(size_t len, char* scratch) { 91| | // TODO: Switch to [[maybe_unused]] when we can assume C++17. 92| 9.73k| (void)len; 93| 9.73k| (void)scratch; 94| | 95| 9.73k| return dest_; 96| 9.73k|} _ZN6snappy15ByteArraySourceC2EPKcm: 148| 15.7k| ByteArraySource(const char* p, size_t n) : ptr_(p), left_(n) { } _ZN6snappy6SourceC2Ev: 113| 15.7k| Source() { } _ZN6snappy22UncheckedByteArraySinkC2EPc: 161| 5.23k| explicit UncheckedByteArraySink(char* dest) : dest_(dest) { } _ZN6snappy4SinkC2Ev: 39| 5.23k| Sink() { } _ZNK6snappy22UncheckedByteArraySink18CurrentDestinationEv: 175| 5.23k| char* CurrentDestination() const { return dest_; } _ZN6snappy6Varint16Parse32WithLimitEPKcS2_Pj: 457| 5.23k| uint32_t* OUTPUT) { 458| 5.23k| const unsigned char* ptr = reinterpret_cast(p); 459| 5.23k| const unsigned char* limit = reinterpret_cast(l); 460| 5.23k| uint32_t b, result; 461| 5.23k| if (ptr >= limit) return NULL; ------------------ | Branch (461:7): [True: 0, False: 5.23k] ------------------ 462| 5.23k| b = *(ptr++); result = b & 127; if (b < 128) goto done; ------------------ | Branch (462:48): [True: 2.59k, False: 2.63k] ------------------ 463| 2.63k| if (ptr >= limit) return NULL; ------------------ | Branch (463:7): [True: 0, False: 2.63k] ------------------ 464| 2.63k| b = *(ptr++); result |= (b & 127) << 7; if (b < 128) goto done; ------------------ | Branch (464:48): [True: 1.65k, False: 982] ------------------ 465| 982| if (ptr >= limit) return NULL; ------------------ | Branch (465:7): [True: 0, False: 982] ------------------ 466| 982| b = *(ptr++); result |= (b & 127) << 14; if (b < 128) goto done; ------------------ | Branch (466:48): [True: 982, False: 0] ------------------ 467| 0| if (ptr >= limit) return NULL; ------------------ | Branch (467:7): [True: 0, False: 0] ------------------ 468| 0| b = *(ptr++); result |= (b & 127) << 21; if (b < 128) goto done; ------------------ | Branch (468:48): [True: 0, False: 0] ------------------ 469| 0| if (ptr >= limit) return NULL; ------------------ | Branch (469:7): [True: 0, False: 0] ------------------ 470| 0| b = *(ptr++); result |= (b & 127) << 28; if (b < 16) goto done; ------------------ | Branch (470:48): [True: 0, False: 0] ------------------ 471| 0| return NULL; // Value is too long to be a varint32 472| 5.23k| done: 473| 5.23k| *OUTPUT = result; 474| 5.23k| return reinterpret_cast(ptr); 475| 0|} _ZN6snappy4Bits9Log2FloorEj: 320| 85.7k|inline int Bits::Log2Floor(uint32_t n) { 321| 85.7k| return (n == 0) ? -1 : Bits::Log2FloorNonZero(n); ------------------ | Branch (321:10): [True: 0, False: 85.7k] ------------------ 322| 85.7k|} _ZN6snappy4Bits16Log2FloorNonZeroEj: 309| 85.7k|inline int Bits::Log2FloorNonZero(uint32_t n) { 310| 85.7k| assert(n != 0); 311| | // (31 ^ x) is equivalent to (31 - x) for x in [0, 31]. An easy proof 312| | // represents subtraction in base 2 and observes that there's no carry. 313| | // 314| | // GCC and Clang represent __builtin_clz on x86 as 31 ^ _bit_scan_reverse(x). 315| | // Using "31 ^" here instead of "31 -" allows the optimizer to strip the 316| | // function body down to _bit_scan_reverse(x). 317| 85.7k| return 31 ^ __builtin_clz(n); 318| 85.7k|} _ZN6snappy12LittleEndian6Load32EPKv: 196| 148M| static inline uint32_t Load32(const void *ptr) { 197| | // Compiles to a single mov/str on recent clang and gcc. 198| |#if SNAPPY_IS_BIG_ENDIAN 199| | const uint8_t* const buffer = reinterpret_cast(ptr); 200| | return (static_cast(buffer[0])) | 201| | (static_cast(buffer[1]) << 8) | 202| | (static_cast(buffer[2]) << 16) | 203| | (static_cast(buffer[3]) << 24); 204| |#else 205| | // See Load16() for the rationale of using memcpy(). 206| 148M| uint32_t value; 207| 148M| std::memcpy(&value, ptr, 4); 208| 148M| return value; 209| 148M|#endif 210| 148M| } _ZN6snappy12LittleEndian6Load64EPKv: 212| 52.7M| static inline uint64_t Load64(const void *ptr) { 213| | // Compiles to a single mov/str on recent clang and gcc. 214| |#if SNAPPY_IS_BIG_ENDIAN 215| | const uint8_t* const buffer = reinterpret_cast(ptr); 216| | return (static_cast(buffer[0])) | 217| | (static_cast(buffer[1]) << 8) | 218| | (static_cast(buffer[2]) << 16) | 219| | (static_cast(buffer[3]) << 24) | 220| | (static_cast(buffer[4]) << 32) | 221| | (static_cast(buffer[5]) << 40) | 222| | (static_cast(buffer[6]) << 48) | 223| | (static_cast(buffer[7]) << 56); 224| |#else 225| | // See Load16() for the rationale of using memcpy(). 226| 52.7M| uint64_t value; 227| 52.7M| std::memcpy(&value, ptr, 8); 228| 52.7M| return value; 229| 52.7M|#endif 230| 52.7M| } _ZN6snappy16UNALIGNED_LOAD64EPKv: 145| 69.9M|inline uint64_t UNALIGNED_LOAD64(const void *p) { 146| | // Compiles to a single mov/ldr on clang/gcc/msvc. 147| 69.9M| uint64_t v; 148| 69.9M| std::memcpy(&v, p, sizeof(v)); 149| 69.9M| return v; 150| 69.9M|} _ZN6snappy4Bits19FindLSBSetNonZero64Em: 398| 7.49M|inline int Bits::FindLSBSetNonZero64(uint64_t n) { 399| 7.49M| assert(n != 0); 400| 7.49M| return __builtin_ctzll(n); 401| 7.49M|} _ZN6snappy6Varint8Encode32EPcj: 477| 5.23k|inline char* Varint::Encode32(char* sptr, uint32_t v) { 478| | // Operate on characters as unsigneds 479| 5.23k| uint8_t* ptr = reinterpret_cast(sptr); 480| 5.23k| static const uint8_t B = 128; 481| 5.23k| if (v < (1 << 7)) { ------------------ | Branch (481:7): [True: 2.59k, False: 2.63k] ------------------ 482| 2.59k| *(ptr++) = static_cast(v); 483| 2.63k| } else if (v < (1 << 14)) { ------------------ | Branch (483:14): [True: 1.65k, False: 982] ------------------ 484| 1.65k| *(ptr++) = static_cast(v | B); 485| 1.65k| *(ptr++) = static_cast(v >> 7); 486| 1.65k| } else if (v < (1 << 21)) { ------------------ | Branch (486:14): [True: 982, False: 0] ------------------ 487| 982| *(ptr++) = static_cast(v | B); 488| 982| *(ptr++) = static_cast((v >> 7) | B); 489| 982| *(ptr++) = static_cast(v >> 14); 490| 982| } else if (v < (1 << 28)) { ------------------ | Branch (490:14): [True: 0, False: 0] ------------------ 491| 0| *(ptr++) = static_cast(v | B); 492| 0| *(ptr++) = static_cast((v >> 7) | B); 493| 0| *(ptr++) = static_cast((v >> 14) | B); 494| 0| *(ptr++) = static_cast(v >> 21); 495| 0| } else { 496| 0| *(ptr++) = static_cast(v | B); 497| 0| *(ptr++) = static_cast((v>>7) | B); 498| 0| *(ptr++) = static_cast((v>>14) | B); 499| 0| *(ptr++) = static_cast((v>>21) | B); 500| 0| *(ptr++) = static_cast(v >> 28); 501| 0| } 502| 5.23k| return reinterpret_cast(ptr); 503| 5.23k|} _ZN6snappy28STLStringResizeUninitializedEPNSt3__112basic_stringIcNS0_11char_traitsIcEENS0_9allocatorIcEEEEm: 509| 10.4k|inline void STLStringResizeUninitialized(std::string* s, size_t new_size) { 510| 10.4k| s->resize(new_size); 511| 10.4k|} _ZN6snappy15string_as_arrayEPNSt3__112basic_stringIcNS0_11char_traitsIcEENS0_9allocatorIcEEEE: 525| 10.4k|inline char* string_as_array(std::string* str) { 526| 10.4k| return str->empty() ? NULL : &*str->begin(); ------------------ | Branch (526:10): [True: 0, False: 10.4k] ------------------ 527| 10.4k|} _ZN6snappy12LittleEndian7Store32EPvj: 244| 8.76M| static void Store32(void *dst, uint32_t value) { 245| | // Compiles to a single mov/str on recent clang and gcc. 246| |#if SNAPPY_IS_BIG_ENDIAN 247| | uint8_t* const buffer = reinterpret_cast(dst); 248| | buffer[0] = static_cast(value); 249| | buffer[1] = static_cast(value >> 8); 250| | buffer[2] = static_cast(value >> 16); 251| | buffer[3] = static_cast(value >> 24); 252| |#else 253| | // See Load16() for the rationale of using memcpy(). 254| 8.76M| std::memcpy(dst, &value, 4); 255| 8.76M|#endif 256| 8.76M| } _ZN6snappy19MaxCompressedLengthEm: 197| 25.4k|size_t MaxCompressedLength(size_t source_bytes) { 198| | // Compressed data can be defined as: 199| | // compressed := item* literal* 200| | // item := literal* copy 201| | // 202| | // The trailing literal sequence has a space blowup of at most 62/60 203| | // since a literal of length 60 needs one tag byte + one extra byte 204| | // for length information. 205| | // 206| | // Item blowup is trickier to measure. Suppose the "copy" op copies 207| | // 4 bytes of data. Because of a special check in the encoding code, 208| | // we produce a 4-byte copy only if the offset is < 65536. Therefore 209| | // the copy op takes 3 bytes to encode, and this type of item leads 210| | // to at most the 62/60 blowup for representing literals. 211| | // 212| | // Suppose the "copy" op copies 5 bytes of data. If the offset is big 213| | // enough, it will take 5 bytes to encode the copy op. Therefore the 214| | // worst case here is a one-byte literal followed by a five-byte copy. 215| | // I.e., 6 bytes of input turn into 7 bytes of "compressed" data. 216| | // 217| | // This last factor dominates the blowup, so the final estimate is: 218| 25.4k| return 32 + source_bytes + source_bytes / 6; 219| 25.4k|} _ZN6snappy21GetUncompressedLengthEPKcmPm: 726| 5.23k|bool GetUncompressedLength(const char* start, size_t n, size_t* result) { 727| 5.23k| uint32_t v = 0; 728| 5.23k| const char* limit = start + n; 729| 5.23k| if (Varint::Parse32WithLimit(start, limit, &v) != NULL) { ------------------ | Branch (729:7): [True: 5.23k, False: 0] ------------------ 730| 5.23k| *result = v; 731| 5.23k| return true; 732| 5.23k| } else { 733| 0| return false; 734| 0| } 735| 5.23k|} _ZN6snappy8internal13WorkingMemoryC2Em: 755| 5.23k|WorkingMemory::WorkingMemory(size_t input_size) { 756| 5.23k| const size_t max_fragment_size = std::min(input_size, kBlockSize); 757| 5.23k| const size_t table_size = CalculateTableSize(max_fragment_size); 758| 5.23k| size_ = table_size * sizeof(*table_) + max_fragment_size + 759| 5.23k| MaxCompressedLength(max_fragment_size); 760| 5.23k| mem_ = std::allocator().allocate(size_); 761| 5.23k| table_ = reinterpret_cast(mem_); 762| 5.23k| input_ = mem_ + table_size * sizeof(*table_); 763| 5.23k| output_ = input_ + max_fragment_size; 764| 5.23k|} _ZN6snappy8internal13WorkingMemoryD2Ev: 766| 5.23k|WorkingMemory::~WorkingMemory() { 767| 5.23k| std::allocator().deallocate(mem_, size_); 768| 5.23k|} _ZNK6snappy8internal13WorkingMemory12GetHashTableEmPi: 771| 9.73k| int* table_size) const { 772| 9.73k| const size_t htsize = CalculateTableSize(fragment_size); 773| 9.73k| memset(table_, 0, htsize * sizeof(*table_)); 774| 9.73k| *table_size = htsize; 775| 9.73k| return table_; 776| 9.73k|} _ZN6snappy8internal16CompressFragmentEPKcmPcPti: 792| 4.86k| uint16_t* table, const int table_size) { 793| | // "ip" is the input pointer, and "op" is the output pointer. 794| 4.86k| const char* ip = input; 795| 4.86k| assert(input_size <= kBlockSize); 796| 4.86k| assert((table_size & (table_size - 1)) == 0); // table must be power of two 797| 4.86k| const uint32_t mask = 2 * (table_size - 1); 798| 4.86k| const char* ip_end = input + input_size; 799| 4.86k| const char* base_ip = ip; 800| | 801| 4.86k| const size_t kInputMarginBytes = 15; 802| 4.86k| if (SNAPPY_PREDICT_TRUE(input_size >= kInputMarginBytes)) { ------------------ | | 95| 4.86k|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 4.82k, False: 38] | | ------------------ ------------------ 803| 4.82k| const char* ip_limit = input + input_size - kInputMarginBytes; 804| | 805| 1.14M| for (uint32_t preload = LittleEndian::Load32(ip + 1);;) { 806| | // Bytes in [next_emit, ip) will be emitted as literal bytes. Or 807| | // [next_emit, ip_end) after the main loop. 808| 1.14M| const char* next_emit = ip++; 809| 1.14M| uint64_t data = LittleEndian::Load64(ip); 810| | // The body of this loop calls EmitLiteral once and then EmitCopy one or 811| | // more times. (The exception is that when we're close to exhausting 812| | // the input we goto emit_remainder.) 813| | // 814| | // In the first iteration of this loop we're just starting, so 815| | // there's nothing to copy, so calling EmitLiteral once is 816| | // necessary. And we only start a new iteration when the 817| | // current iteration has determined that a call to EmitLiteral will 818| | // precede the next call to EmitCopy (if any). 819| | // 820| | // Step 1: Scan forward in the input looking for a 4-byte-long match. 821| | // If we get close to exhausting the input then goto emit_remainder. 822| | // 823| | // Heuristic match skipping: If 32 bytes are scanned with no matches 824| | // found, start looking only at every other byte. If 32 more bytes are 825| | // scanned (or skipped), look at every third byte, etc.. When a match is 826| | // found, immediately go back to looking at every byte. This is a small 827| | // loss (~5% performance, ~0.1% density) for compressible data due to more 828| | // bookkeeping, but for non-compressible data (such as JPEG) it's a huge 829| | // win since the compressor quickly "realizes" the data is incompressible 830| | // and doesn't bother looking for matches everywhere. 831| | // 832| | // The "skip" variable keeps track of how many bytes there are since the 833| | // last match; dividing it by 32 (ie. right-shifting by five) gives the 834| | // number of bytes to move ahead for each iteration. 835| 1.14M| uint32_t skip = 32; 836| | 837| 1.14M| const char* candidate; 838| 1.14M| if (ip_limit - ip >= 16) { ------------------ | Branch (838:11): [True: 1.14M, False: 1.98k] ------------------ 839| 1.14M| auto delta = ip - base_ip; 840| 1.66M| for (int j = 0; j < 4; ++j) { ------------------ | Branch (840:25): [True: 1.58M, False: 72.9k] ------------------ 841| 4.46M| for (int k = 0; k < 4; ++k) { ------------------ | Branch (841:27): [True: 3.94M, False: 517k] ------------------ 842| 3.94M| int i = 4 * j + k; 843| | // These for-loops are meant to be unrolled. So we can freely 844| | // special case the first iteration to use the value already 845| | // loaded in preload. 846| 3.94M| uint32_t dword = i == 0 ? preload : static_cast(data); ------------------ | Branch (846:30): [True: 1.14M, False: 2.80M] ------------------ 847| 3.94M| assert(dword == LittleEndian::Load32(ip + i)); 848| 3.94M| uint16_t* table_entry = TableEntry(table, dword, mask); 849| 3.94M| candidate = base_ip + *table_entry; 850| 3.94M| assert(candidate >= base_ip); 851| 3.94M| assert(candidate < ip + i); 852| 3.94M| *table_entry = delta + i; 853| 3.94M| if (SNAPPY_PREDICT_FALSE(LittleEndian::Load32(candidate) == dword)) { ------------------ | | 94| 3.94M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 1.07M, False: 2.87M] | | ------------------ ------------------ 854| 1.07M| *op = LITERAL | (i << 2); 855| 1.07M| UnalignedCopy128(next_emit, op + 1); 856| 1.07M| ip += i; 857| 1.07M| op = op + i + 2; 858| 1.07M| goto emit_match; 859| 1.07M| } 860| 2.87M| data >>= 8; 861| 2.87M| } 862| 517k| data = LittleEndian::Load64(ip + 4 * j + 4); 863| 517k| } 864| 72.9k| ip += 16; 865| 72.9k| skip += 16; 866| 72.9k| } 867| 2.47M| while (true) { ------------------ | Branch (867:14): [Folded - Ignored] ------------------ 868| 2.47M| assert(static_cast(data) == LittleEndian::Load32(ip)); 869| 2.47M| uint16_t* table_entry = TableEntry(table, data, mask); 870| 2.47M| uint32_t bytes_between_hash_lookups = skip >> 5; 871| 2.47M| skip += bytes_between_hash_lookups; 872| 2.47M| const char* next_ip = ip + bytes_between_hash_lookups; 873| 2.47M| if (SNAPPY_PREDICT_FALSE(next_ip > ip_limit)) { ------------------ | | 94| 2.47M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 1.86k, False: 2.47M] | | ------------------ ------------------ 874| 1.86k| ip = next_emit; 875| 1.86k| goto emit_remainder; 876| 1.86k| } 877| 2.47M| candidate = base_ip + *table_entry; 878| 2.47M| assert(candidate >= base_ip); 879| 2.47M| assert(candidate < ip); 880| | 881| 2.47M| *table_entry = ip - base_ip; 882| 2.47M| if (SNAPPY_PREDICT_FALSE(static_cast(data) == ------------------ | | 94| 2.47M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 73.1k, False: 2.40M] | | ------------------ ------------------ 883| 2.47M| LittleEndian::Load32(candidate))) { 884| 73.1k| break; 885| 73.1k| } 886| 2.40M| data = LittleEndian::Load32(next_ip); 887| 2.40M| ip = next_ip; 888| 2.40M| } 889| | 890| | // Step 2: A 4-byte match has been found. We'll later see if more 891| | // than 4 bytes match. But, prior to the match, input 892| | // bytes [next_emit, ip) are unmatched. Emit them as "literal bytes." 893| 73.1k| assert(next_emit + 16 <= ip_end); 894| 73.1k| op = EmitLiteral(op, next_emit, ip - next_emit); 895| | 896| | // Step 3: Call EmitCopy, and then see if another EmitCopy could 897| | // be our next move. Repeat until we find no match for the 898| | // input immediately after what was consumed by the last EmitCopy call. 899| | // 900| | // If we exit this loop normally then we need to call EmitLiteral next, 901| | // though we don't yet know how big the literal will be. We handle that 902| | // by proceeding to the next iteration of the main loop. We also can exit 903| | // this loop via goto if we get close to exhausting the input. 904| 1.14M| emit_match: 905| 3.29M| do { 906| | // We have a 4-byte match at ip, and no need to emit any 907| | // "literal bytes" prior to ip. 908| 3.29M| const char* base = ip; 909| 3.29M| std::pair p = 910| 3.29M| FindMatchLength(candidate + 4, ip + 4, ip_end, &data); 911| 3.29M| size_t matched = 4 + p.first; 912| 3.29M| ip += matched; 913| 3.29M| size_t offset = base - candidate; 914| 3.29M| assert(0 == memcmp(base, candidate, matched)); 915| 3.29M| if (p.second) { ------------------ | Branch (915:13): [True: 2.29M, False: 996k] ------------------ 916| 2.29M| op = EmitCopy(op, offset, matched); 917| 2.29M| } else { 918| 996k| op = EmitCopy(op, offset, matched); 919| 996k| } 920| 3.29M| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit)) { ------------------ | | 94| 3.29M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 2.96k, False: 3.28M] | | ------------------ ------------------ 921| 2.96k| goto emit_remainder; 922| 2.96k| } 923| | // Expect 5 bytes to match 924| 3.28M| assert((data & 0xFFFFFFFFFF) == 925| 3.28M| (LittleEndian::Load64(ip) & 0xFFFFFFFFFF)); 926| | // We are now looking for a 4-byte match again. We read 927| | // table[Hash(ip, mask)] for that. To improve compression, 928| | // we also update table[Hash(ip - 1, mask)] and table[Hash(ip, mask)]. 929| 3.28M| *TableEntry(table, LittleEndian::Load32(ip - 1), mask) = 930| 3.28M| ip - base_ip - 1; 931| 3.28M| uint16_t* table_entry = TableEntry(table, data, mask); 932| 3.28M| candidate = base_ip + *table_entry; 933| 3.28M| *table_entry = ip - base_ip; 934| | // Measurements on the benchmarks have shown the following probabilities 935| | // for the loop to exit (ie. avg. number of iterations is reciprocal). 936| | // BM_Flat/6 txt1 p = 0.3-0.4 937| | // BM_Flat/7 txt2 p = 0.35 938| | // BM_Flat/8 txt3 p = 0.3-0.4 939| | // BM_Flat/9 txt3 p = 0.34-0.4 940| | // BM_Flat/10 pb p = 0.4 941| | // BM_Flat/11 gaviota p = 0.1 942| | // BM_Flat/12 cp p = 0.5 943| | // BM_Flat/13 c p = 0.3 944| 3.28M| } while (static_cast(data) == LittleEndian::Load32(candidate)); ------------------ | Branch (944:16): [True: 2.14M, False: 1.14M] ------------------ 945| | // Because the least significant 5 bytes matched, we can utilize data 946| | // for the next iteration. 947| 1.14M| preload = data >> 8; 948| 1.14M| } 949| 4.82k| } 950| | 951| 4.86k|emit_remainder: 952| | // Emit the remaining bytes as a literal 953| 4.86k| if (ip < ip_end) { ------------------ | Branch (953:7): [True: 3.53k, False: 1.33k] ------------------ 954| 3.53k| op = EmitLiteral(op, ip, ip_end - ip); 955| 3.53k| } 956| | 957| 4.86k| return op; 958| 4.86k|} _ZN6snappy8internal26CompressFragmentDoubleHashEPKcmPcPtiS4_i: 962| 4.86k| uint16_t* table2, const int table_size2) { 963| 4.86k| (void)table_size2; 964| 4.86k| assert(table_size == table_size2); 965| | // "ip" is the input pointer, and "op" is the output pointer. 966| 4.86k| const char* ip = input; 967| 4.86k| assert(input_size <= kBlockSize); 968| 4.86k| assert((table_size & (table_size - 1)) == 0); // table must be power of two 969| 4.86k| const uint32_t mask = 2 * (table_size - 1); 970| 4.86k| const char* ip_end = input + input_size; 971| 4.86k| const char* base_ip = ip; 972| | 973| 4.86k| const size_t kInputMarginBytes = 15; 974| 4.86k| if (SNAPPY_PREDICT_TRUE(input_size >= kInputMarginBytes)) { ------------------ | | 95| 4.86k|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 4.82k, False: 38] | | ------------------ ------------------ 975| 4.82k| const char* ip_limit = input + input_size - kInputMarginBytes; 976| | 977| 1.41M| for (;;) { 978| 1.41M| const char* next_emit = ip++; 979| 1.41M| uint64_t data = LittleEndian::Load64(ip); 980| 1.41M| uint32_t skip = 512; 981| | 982| 1.41M| const char* candidate; 983| 1.41M| uint32_t candidate_length; 984| 26.9M| while (true) { ------------------ | Branch (984:14): [Folded - Ignored] ------------------ 985| 26.9M| assert(static_cast(data) == LittleEndian::Load32(ip)); 986| 26.9M| uint16_t* table_entry2 = TableEntry8ByteMatch(table2, data, mask); 987| 26.9M| uint32_t bytes_between_hash_lookups = skip >> 9; 988| 26.9M| skip++; 989| 26.9M| const char* next_ip = ip + bytes_between_hash_lookups; 990| 26.9M| if (SNAPPY_PREDICT_FALSE(next_ip > ip_limit)) { ------------------ | | 94| 26.9M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 1.49k, False: 26.9M] | | ------------------ ------------------ 991| 1.49k| ip = next_emit; 992| 1.49k| goto emit_remainder; 993| 1.49k| } 994| 26.9M| candidate = base_ip + *table_entry2; 995| 26.9M| assert(candidate >= base_ip); 996| 26.9M| assert(candidate < ip); 997| | 998| 26.9M| *table_entry2 = ip - base_ip; 999| 26.9M| if (SNAPPY_PREDICT_FALSE(static_cast(data) == ------------------ | | 94| 26.9M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 651k, False: 26.3M] | | ------------------ ------------------ 1000| 26.9M| LittleEndian::Load32(candidate))) { 1001| 651k| candidate_length = 1002| 651k| FindMatchLengthPlain(candidate + 4, ip + 4, ip_end) + 4; 1003| 651k| break; 1004| 651k| } 1005| | 1006| 26.3M| uint16_t* table_entry = TableEntry4ByteMatch(table, data, mask); 1007| 26.3M| candidate = base_ip + *table_entry; 1008| 26.3M| assert(candidate >= base_ip); 1009| 26.3M| assert(candidate < ip); 1010| | 1011| 26.3M| *table_entry = ip - base_ip; 1012| 26.3M| if (SNAPPY_PREDICT_FALSE(static_cast(data) == ------------------ | | 94| 26.3M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 762k, False: 25.5M] | | ------------------ ------------------ 1013| 26.3M| LittleEndian::Load32(candidate))) { 1014| 762k| candidate_length = 1015| 762k| FindMatchLengthPlain(candidate + 4, ip + 4, ip_end) + 4; 1016| 762k| table_entry2 = 1017| 762k| TableEntry8ByteMatch(table2, LittleEndian::Load64(ip + 1), mask); 1018| 762k| auto candidate2 = base_ip + *table_entry2; 1019| 762k| size_t candidate_length2 = 1020| 762k| FindMatchLengthPlain(candidate2, ip + 1, ip_end); 1021| 762k| if (candidate_length2 > candidate_length) { ------------------ | Branch (1021:15): [True: 27.6k, False: 734k] ------------------ 1022| 27.6k| *table_entry2 = ip - base_ip; 1023| 27.6k| candidate = candidate2; 1024| 27.6k| candidate_length = candidate_length2; 1025| 27.6k| ++ip; 1026| 27.6k| } 1027| 762k| break; 1028| 762k| } 1029| 25.5M| data = LittleEndian::Load64(next_ip); 1030| 25.5M| ip = next_ip; 1031| 25.5M| } 1032| | // Backtrack to the point it matches fully. 1033| 1.55M| while (ip > next_emit && candidate > base_ip && ------------------ | Branch (1033:14): [True: 1.54M, False: 11.9k] | Branch (1033:32): [True: 1.54M, False: 7.28k] ------------------ 1034| 1.55M| *(ip - 1) == *(candidate - 1)) { ------------------ | Branch (1034:14): [True: 146k, False: 1.39M] ------------------ 1035| 146k| --ip; 1036| 146k| --candidate; 1037| 146k| ++candidate_length; 1038| 146k| } 1039| 1.41M| *TableEntry8ByteMatch(table2, LittleEndian::Load64(ip + 1), mask) = 1040| 1.41M| ip - base_ip + 1; 1041| 1.41M| *TableEntry8ByteMatch(table2, LittleEndian::Load64(ip + 2), mask) = 1042| 1.41M| ip - base_ip + 2; 1043| 1.41M| *TableEntry4ByteMatch(table, LittleEndian::Load32(ip + 1), mask) = 1044| 1.41M| ip - base_ip + 1; 1045| | // Step 2: A 4-byte or 8-byte match has been found. 1046| | // We'll later see if more than 4 bytes match. But, prior to the match, 1047| | // input bytes [next_emit, ip) are unmatched. Emit them as 1048| | // "literal bytes." 1049| 1.41M| assert(next_emit + 16 <= ip_end); 1050| 1.41M| if (ip - next_emit > 0) { ------------------ | Branch (1050:11): [True: 1.40M, False: 11.9k] ------------------ 1051| 1.40M| op = EmitLiteral(op, next_emit, 1052| 1.40M| ip - next_emit); 1053| 1.40M| } 1054| | // Step 3: Call EmitCopy, and then see if another EmitCopy could 1055| | // be our next move. Repeat until we find no match for the 1056| | // input immediately after what was consumed by the last EmitCopy call. 1057| | // 1058| | // If we exit this loop normally then we need to call EmitLiteral next, 1059| | // though we don't yet know how big the literal will be. We handle that 1060| | // by proceeding to the next iteration of the main loop. We also can exit 1061| | // this loop via goto if we get close to exhausting the input. 1062| 3.45M| do { 1063| | // We have a 4-byte match at ip, and no need to emit any 1064| | // "literal bytes" prior to ip. 1065| 3.45M| const char* base = ip; 1066| 3.45M| ip += candidate_length; 1067| 3.45M| size_t offset = base - candidate; 1068| 3.45M| if (candidate_length < 12) { ------------------ | Branch (1068:13): [True: 2.35M, False: 1.09M] ------------------ 1069| 2.35M| op = 1070| 2.35M| EmitCopy(op, offset, candidate_length); 1071| 2.35M| } else { 1072| 1.09M| op = EmitCopy(op, offset, 1073| 1.09M| candidate_length); 1074| 1.09M| } 1075| 3.45M| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit)) { ------------------ | | 94| 3.45M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 3.33k, False: 3.44M] | | ------------------ ------------------ 1076| 3.33k| goto emit_remainder; 1077| 3.33k| } 1078| | // We are now looking for a 4-byte match again. We read 1079| | // table[Hash(ip, mask)] for that. To improve compression, 1080| | // we also update several previous table entries. 1081| 3.44M| if (ip - base_ip > 7) { ------------------ | Branch (1081:13): [True: 3.44M, False: 699] ------------------ 1082| 3.44M| *TableEntry8ByteMatch(table2, LittleEndian::Load64(ip - 7), mask) = 1083| 3.44M| ip - base_ip - 7; 1084| 3.44M| *TableEntry8ByteMatch(table2, LittleEndian::Load64(ip - 4), mask) = 1085| 3.44M| ip - base_ip - 4; 1086| 3.44M| } 1087| 3.44M| *TableEntry8ByteMatch(table2, LittleEndian::Load64(ip - 3), mask) = 1088| 3.44M| ip - base_ip - 3; 1089| 3.44M| *TableEntry8ByteMatch(table2, LittleEndian::Load64(ip - 2), mask) = 1090| 3.44M| ip - base_ip - 2; 1091| 3.44M| *TableEntry4ByteMatch(table, LittleEndian::Load32(ip - 2), mask) = 1092| 3.44M| ip - base_ip - 2; 1093| 3.44M| *TableEntry4ByteMatch(table, LittleEndian::Load32(ip - 1), mask) = 1094| 3.44M| ip - base_ip - 1; 1095| | 1096| 3.44M| uint16_t* table_entry = 1097| 3.44M| TableEntry8ByteMatch(table2, LittleEndian::Load64(ip), mask); 1098| 3.44M| candidate = base_ip + *table_entry; 1099| 3.44M| *table_entry = ip - base_ip; 1100| 3.44M| if (LittleEndian::Load32(ip) == LittleEndian::Load32(candidate)) { ------------------ | Branch (1100:13): [True: 677k, False: 2.77M] ------------------ 1101| 677k| candidate_length = 1102| 677k| FindMatchLengthPlain(candidate + 4, ip + 4, ip_end) + 4; 1103| 677k| continue; 1104| 677k| } 1105| 2.77M| table_entry = 1106| 2.77M| TableEntry4ByteMatch(table, LittleEndian::Load32(ip), mask); 1107| 2.77M| candidate = base_ip + *table_entry; 1108| 2.77M| *table_entry = ip - base_ip; 1109| 2.77M| if (LittleEndian::Load32(ip) == LittleEndian::Load32(candidate)) { ------------------ | Branch (1109:13): [True: 1.35M, False: 1.41M] ------------------ 1110| 1.35M| candidate_length = 1111| 1.35M| FindMatchLengthPlain(candidate + 4, ip + 4, ip_end) + 4; 1112| 1.35M| continue; 1113| 1.35M| } 1114| 1.41M| break; 1115| 2.77M| } while (true); ------------------ | Branch (1115:16): [Folded - Ignored] ------------------ 1116| 1.41M| } 1117| 4.82k| } 1118| | 1119| 4.86k|emit_remainder: 1120| | // Emit the remaining bytes as a literal 1121| 4.86k| if (ip < ip_end) { ------------------ | Branch (1121:7): [True: 3.33k, False: 1.53k] ------------------ 1122| 3.33k| op = EmitLiteral(op, ip, ip_end - ip); 1123| 3.33k| } 1124| | 1125| 4.86k| return op; 1126| 4.86k|} _ZN6snappy9MemCopy64EPcPKvm: 1227| 11.1M|void MemCopy64(char* dst, const void* src, size_t size) { 1228| | // Always copy this many bytes. If that's below size then copy the full 64. 1229| 11.1M| constexpr int kShortMemCopy = 32; 1230| | 1231| 11.1M| assert(size <= 64); 1232| 11.1M| assert(std::less_equal()(static_cast(src) + size, 1233| 11.1M| dst) || 1234| 11.1M| std::less_equal()(dst + size, src)); 1235| | 1236| | // We know that src and dst are at least size bytes apart. However, because we 1237| | // might copy more than size bytes the copy still might overlap past size. 1238| | // E.g. if src and dst appear consecutively in memory (src + size >= dst). 1239| | // TODO: Investigate wider copies on other platforms. 1240| |#if defined(__x86_64__) && defined(__AVX__) 1241| | assert(kShortMemCopy <= 32); 1242| | __m256i data = _mm256_lddqu_si256(static_cast(src)); 1243| | _mm256_storeu_si256(reinterpret_cast<__m256i *>(dst), data); 1244| | // Profiling shows that nearly all copies are short. 1245| | if (SNAPPY_PREDICT_FALSE(size > kShortMemCopy)) { 1246| | data = _mm256_lddqu_si256(static_cast(src) + 1); 1247| | _mm256_storeu_si256(reinterpret_cast<__m256i *>(dst) + 1, data); 1248| | } 1249| |#else 1250| 11.1M| std::memmove(dst, src, kShortMemCopy); 1251| | // Profiling shows that nearly all copies are short. 1252| 11.1M| if (SNAPPY_PREDICT_FALSE(size > kShortMemCopy)) { ------------------ | | 94| 11.1M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 2.26M, False: 8.90M] | | ------------------ ------------------ 1253| 2.26M| std::memmove(dst + kShortMemCopy, 1254| 2.26M| static_cast(src) + kShortMemCopy, 1255| 2.26M| 64 - kShortMemCopy); 1256| 2.26M| } 1257| 11.1M|#endif 1258| 11.1M|} _ZN6snappy9MemCopy64ElPKvm: 1260| 11.1M|void MemCopy64(ptrdiff_t dst, const void* src, size_t size) { 1261| | // TODO: Switch to [[maybe_unused]] when we can assume C++17. 1262| 11.1M| (void)dst; 1263| 11.1M| (void)src; 1264| 11.1M| (void)size; 1265| 11.1M|} _ZN6snappy13ClearDeferredEPPKvPmPh: 1268| 3.06M| uint8_t* safe_source) { 1269| 3.06M| *deferred_src = safe_source; 1270| 3.06M| *deferred_length = 0; 1271| 3.06M|} _ZN6snappy12DeferMemCopyEPPKvPmS1_m: 1274| 19.5M| const void* src, size_t length) { 1275| 19.5M| *deferred_src = src; 1276| 19.5M| *deferred_length = length; 1277| 19.5M|} _ZN6snappy18SnappyDecompressor9RefillTagEv: 1704| 24.7k|bool SnappyDecompressor::RefillTag() { 1705| 24.7k| const char* ip = ip_; 1706| 24.7k| if (ip == ip_limit_) { ------------------ | Branch (1706:7): [True: 20.9k, False: 3.83k] ------------------ 1707| | // Fetch a new fragment from the reader 1708| 20.9k| reader_->Skip(peeked_); // All peeked bytes are used up 1709| 20.9k| size_t n; 1710| 20.9k| ip = reader_->Peek(&n); 1711| 20.9k| peeked_ = n; 1712| 20.9k| eof_ = (n == 0); 1713| 20.9k| if (eof_) return false; ------------------ | Branch (1713:9): [True: 10.4k, False: 10.4k] ------------------ 1714| 10.4k| ip_limit_ = ip + n; 1715| 10.4k| } 1716| | 1717| | // Read the tag character 1718| 14.3k| assert(ip < ip_limit_); 1719| 14.3k| const unsigned char c = *(reinterpret_cast(ip)); 1720| | // At this point make sure that the data for the next tag is consecutive. 1721| | // For copy 1 this means the next 2 bytes (tag and 1 byte offset) 1722| | // For copy 2 the next 3 bytes (tag and 2 byte offset) 1723| | // For copy 4 the next 5 bytes (tag and 4 byte offset) 1724| | // For all small literals we only need 1 byte buf for literals 60...63 the 1725| | // length is encoded in 1...4 extra bytes. 1726| 14.3k| const uint32_t needed = CalculateNeeded(c); 1727| 14.3k| assert(needed <= sizeof(scratch_)); 1728| | 1729| | // Read more bytes from reader if needed 1730| 14.3k| uint64_t nbuf = ip_limit_ - ip; 1731| 14.3k| if (nbuf < needed) { ------------------ | Branch (1731:7): [True: 0, False: 14.3k] ------------------ 1732| | // Stitch together bytes from ip and reader to form the word 1733| | // contents. We store the needed bytes in "scratch_". They 1734| | // will be consumed immediately by the caller since we do not 1735| | // read more than we need. 1736| 0| std::memmove(scratch_, ip, nbuf); 1737| 0| reader_->Skip(peeked_); // All peeked bytes are used up 1738| 0| peeked_ = 0; 1739| 0| while (nbuf < needed) { ------------------ | Branch (1739:12): [True: 0, False: 0] ------------------ 1740| 0| size_t length; 1741| 0| const char* src = reader_->Peek(&length); 1742| 0| if (length == 0) return false; ------------------ | Branch (1742:11): [True: 0, False: 0] ------------------ 1743| 0| uint64_t to_add = std::min(needed - nbuf, length); 1744| 0| std::memcpy(scratch_ + nbuf, src, to_add); 1745| 0| nbuf += to_add; 1746| 0| reader_->Skip(to_add); 1747| 0| } 1748| 0| assert(nbuf == needed); 1749| 0| ip_ = scratch_; 1750| 0| ip_limit_ = scratch_ + needed; 1751| 14.3k| } else if (nbuf < kMaximumTagLength) { ------------------ | Branch (1751:14): [True: 3.84k, False: 10.4k] ------------------ 1752| | // Have enough bytes, but move into scratch_ so that we do not 1753| | // read past end of input 1754| 3.84k| std::memmove(scratch_, ip, nbuf); 1755| 3.84k| reader_->Skip(peeked_); // All peeked bytes are used up 1756| 3.84k| peeked_ = 0; 1757| 3.84k| ip_ = scratch_; 1758| 3.84k| ip_limit_ = scratch_ + nbuf; 1759| 10.4k| } else { 1760| | // Pass pointer to buffer returned by reader_. 1761| 10.4k| ip_ = ip; 1762| 10.4k| } 1763| 14.3k| return true; 1764| 14.3k|} _ZN6snappy8CompressEPNS_6SourceEPNS_4SinkENS_18CompressionOptionsE: 1801| 5.23k|size_t Compress(Source* reader, Sink* writer, CompressionOptions options) { 1802| 5.23k| assert(options.level == 1 || options.level == 2); 1803| 5.23k| int token = 0; 1804| 5.23k| size_t written = 0; 1805| 5.23k| size_t N = reader->Available(); 1806| 5.23k| assert(N <= 0xFFFFFFFFu); 1807| 5.23k| const size_t uncompressed_size = N; 1808| 5.23k| char ulength[Varint::kMax32]; 1809| 5.23k| char* p = Varint::Encode32(ulength, N); 1810| 5.23k| writer->Append(ulength, p - ulength); 1811| 5.23k| written += (p - ulength); 1812| | 1813| 5.23k| internal::WorkingMemory wmem(N); 1814| | 1815| 14.9k| while (N > 0) { ------------------ | Branch (1815:10): [True: 9.73k, False: 5.23k] ------------------ 1816| | // Get next block to compress (without copying if possible) 1817| 9.73k| size_t fragment_size; 1818| 9.73k| const char* fragment = reader->Peek(&fragment_size); 1819| 9.73k| assert(fragment_size != 0); // premature end of input 1820| 9.73k| const size_t num_to_read = std::min(N, kBlockSize); 1821| 9.73k| size_t bytes_read = fragment_size; 1822| | 1823| 9.73k| size_t pending_advance = 0; 1824| 9.73k| if (bytes_read >= num_to_read) { ------------------ | Branch (1824:9): [True: 9.73k, False: 0] ------------------ 1825| | // Buffer returned by reader is large enough 1826| 9.73k| pending_advance = num_to_read; 1827| 9.73k| fragment_size = num_to_read; 1828| 9.73k| } else { 1829| 0| char* scratch = wmem.GetScratchInput(); 1830| 0| std::memcpy(scratch, fragment, bytes_read); 1831| 0| reader->Skip(bytes_read); 1832| | 1833| 0| while (bytes_read < num_to_read) { ------------------ | Branch (1833:14): [True: 0, False: 0] ------------------ 1834| 0| fragment = reader->Peek(&fragment_size); 1835| 0| size_t n = std::min(fragment_size, num_to_read - bytes_read); 1836| 0| std::memcpy(scratch + bytes_read, fragment, n); 1837| 0| bytes_read += n; 1838| 0| reader->Skip(n); 1839| 0| } 1840| 0| assert(bytes_read == num_to_read); 1841| 0| fragment = scratch; 1842| 0| fragment_size = num_to_read; 1843| 0| } 1844| 9.73k| assert(fragment_size == num_to_read); 1845| | 1846| | // Get encoding table for compression 1847| 9.73k| int table_size; 1848| 9.73k| uint16_t* table = wmem.GetHashTable(num_to_read, &table_size); 1849| | 1850| | // Compress input_fragment and append to dest 1851| 9.73k| int max_output = MaxCompressedLength(num_to_read); 1852| | 1853| | // Since we encode kBlockSize regions followed by a region 1854| | // which is <= kBlockSize in length, a previously allocated 1855| | // scratch_output[] region is big enough for this iteration. 1856| | // Need a scratch buffer for the output, in case the byte sink doesn't 1857| | // have room for us directly. 1858| 9.73k| char* dest = writer->GetAppendBuffer(max_output, wmem.GetScratchOutput()); 1859| 9.73k| char* end = nullptr; 1860| 9.73k| if (options.level == 1) { ------------------ | Branch (1860:9): [True: 4.86k, False: 4.86k] ------------------ 1861| 4.86k| end = internal::CompressFragment(fragment, fragment_size, dest, table, 1862| 4.86k| table_size); 1863| 4.86k| } else if (options.level == 2) { ------------------ | Branch (1863:16): [True: 4.86k, False: 0] ------------------ 1864| 4.86k| end = internal::CompressFragmentDoubleHash( 1865| 4.86k| fragment, fragment_size, dest, table, table_size >> 1, 1866| 4.86k| table + (table_size >> 1), table_size >> 1); 1867| 4.86k| } 1868| 9.73k| writer->Append(dest, end - dest); 1869| 9.73k| written += (end - dest); 1870| | 1871| 9.73k| N -= num_to_read; 1872| 9.73k| reader->Skip(pending_advance); 1873| 9.73k| } 1874| | 1875| 5.23k| Report(token, "snappy_compress", written, uncompressed_size); 1876| 5.23k| return written; 1877| 5.23k|} _ZN6snappy13RawUncompressEPKcmPc: 2228| 5.23k| char* uncompressed) { 2229| 5.23k| ByteArraySource reader(compressed, compressed_length); 2230| 5.23k| return RawUncompress(&reader, uncompressed); 2231| 5.23k|} _ZN6snappy13RawUncompressEPNS_6SourceEPc: 2233| 5.23k|bool RawUncompress(Source* compressed, char* uncompressed) { 2234| 5.23k| SnappyArrayWriter output(uncompressed); 2235| 5.23k| return InternalUncompress(compressed, &output); 2236| 5.23k|} _ZN6snappy10UncompressEPKcmPNSt3__112basic_stringIcNS2_11char_traitsIcEENS2_9allocatorIcEEEE: 2239| 5.23k| std::string* uncompressed) { 2240| 5.23k| size_t ulength; 2241| 5.23k| if (!GetUncompressedLength(compressed, compressed_length, &ulength)) { ------------------ | Branch (2241:7): [True: 0, False: 5.23k] ------------------ 2242| 0| return false; 2243| 0| } 2244| | // On 32-bit builds: max_size() < kuint32max. Check for that instead 2245| | // of crashing (e.g., consider externally specified compressed data). 2246| 5.23k| if (ulength > uncompressed->max_size()) { ------------------ | Branch (2246:7): [True: 0, False: 5.23k] ------------------ 2247| 0| return false; 2248| 0| } 2249| 5.23k| STLStringResizeUninitialized(uncompressed, ulength); 2250| 5.23k| return RawUncompress(compressed, compressed_length, 2251| 5.23k| string_as_array(uncompressed)); 2252| 5.23k|} _ZN6snappy23IsValidCompressedBufferEPKcm: 2297| 5.23k|bool IsValidCompressedBuffer(const char* compressed, size_t compressed_length) { 2298| 5.23k| ByteArraySource reader(compressed, compressed_length); 2299| 5.23k| SnappyDecompressionValidator writer; 2300| 5.23k| return InternalUncompress(&reader, &writer); 2301| 5.23k|} _ZN6snappy11RawCompressEPKcmPcPmNS_18CompressionOptionsE: 2315| 5.23k| size_t* compressed_length, CompressionOptions options) { 2316| 5.23k| ByteArraySource reader(input, input_length); 2317| 5.23k| UncheckedByteArraySink writer(compressed); 2318| 5.23k| Compress(&reader, &writer, options); 2319| | 2320| | // Compute how many bytes were added 2321| 5.23k| *compressed_length = (writer.CurrentDestination() - compressed); 2322| 5.23k|} _ZN6snappy8CompressEPKcmPNSt3__112basic_stringIcNS2_11char_traitsIcEENS2_9allocatorIcEEEENS_18CompressionOptionsE: 2347| 5.23k| CompressionOptions options) { 2348| | // Pre-grow the buffer to the max length of the compressed output 2349| 5.23k| STLStringResizeUninitialized(compressed, MaxCompressedLength(input_length)); 2350| | 2351| 5.23k| size_t compressed_length; 2352| 5.23k| RawCompress(input, input_length, string_as_array(compressed), 2353| 5.23k| &compressed_length, options); 2354| 5.23k| compressed->erase(compressed_length); 2355| 5.23k| return compressed_length; 2356| 5.23k|} snappy.cc:_ZN6snappy12_GLOBAL__N_118CalculateTableSizeEj: 738| 14.9k|uint32_t CalculateTableSize(uint32_t input_size) { 739| 14.9k| static_assert( 740| 14.9k| kMaxHashTableSize >= kMinHashTableSize, 741| 14.9k| "kMaxHashTableSize should be greater or equal to kMinHashTableSize."); 742| 14.9k| if (input_size > kMaxHashTableSize) { ------------------ | Branch (742:7): [True: 5.89k, False: 9.06k] ------------------ 743| 5.89k| return kMaxHashTableSize; 744| 5.89k| } 745| 9.06k| if (input_size < kMinHashTableSize) { ------------------ | Branch (745:7): [True: 6.60k, False: 2.46k] ------------------ 746| 6.60k| return kMinHashTableSize; 747| 6.60k| } 748| | // This is equivalent to Log2Ceiling(input_size), assuming input_size > 1. 749| | // 2 << Log2Floor(x - 1) is equivalent to 1 << (1 + Log2Floor(x - 1)). 750| 2.46k| return 2u << Bits::Log2Floor(input_size - 1); 751| 9.06k|} snappy.cc:_ZN6snappy12_GLOBAL__N_110TableEntryEPtjj: 155| 12.9M|inline uint16_t* TableEntry(uint16_t* table, uint32_t bytes, uint32_t mask) { 156| | // Our choice is quicker-and-dirtier than the typical hash function; 157| | // empirically, that seems beneficial. The upper bits of kMagic * bytes are a 158| | // higher-quality hash than the lower bits, so when using kMagic * bytes we 159| | // also shift right to get a higher-quality end result. There's no similar 160| | // issue with a CRC because all of the output bits of a CRC are equally good 161| | // "hashes." So, a CPU instruction for CRC, if available, tends to be a good 162| | // choice. 163| |#if SNAPPY_HAVE_NEON_CRC32 164| | // We use mask as the second arg to the CRC function, as it's about to 165| | // be used anyway; it'd be equally correct to use 0 or some constant. 166| | // Mathematically, _mm_crc32_u32 (or similar) is a function of the 167| | // xor of its arguments. 168| | const uint32_t hash = __crc32cw(bytes, mask); 169| |#elif SNAPPY_HAVE_X86_CRC32 170| | const uint32_t hash = _mm_crc32_u32(bytes, mask); 171| |#else 172| 12.9M| constexpr uint32_t kMagic = 0x1e35a7bd; 173| 12.9M| const uint32_t hash = (kMagic * bytes) >> (31 - kMaxHashTableBits); 174| 12.9M|#endif 175| 12.9M| return reinterpret_cast(reinterpret_cast(table) + 176| 12.9M| (hash & mask)); 177| 12.9M|} snappy.cc:_ZN6snappy12_GLOBAL__N_116UnalignedCopy128EPKvPv: 229| 2.34M|void UnalignedCopy128(const void* src, void* dst) { 230| | // std::memcpy() gets vectorized when the appropriate compiler options are 231| | // used. For example, x86 compilers targeting SSE2+ will optimize to an SSE2 232| | // load and store. 233| 2.34M| char tmp[16]; 234| 2.34M| std::memcpy(tmp, src, 16); 235| 2.34M| std::memcpy(dst, tmp, 16); 236| 2.34M|} snappy.cc:_ZN6snappy12_GLOBAL__N_120TableEntry8ByteMatchEPtmj: 188| 47.7M| uint32_t mask) { 189| 47.7M| constexpr uint64_t kMagic = 58295818150454627ULL; 190| 47.7M| const uint32_t hash = (kMagic * bytes) >> (64 - kMaxHashTableBits); 191| 47.7M| return reinterpret_cast(reinterpret_cast(table) + 192| 47.7M| (hash & mask)); 193| 47.7M|} snappy.cc:_ZN6snappy12_GLOBAL__N_120TableEntry4ByteMatchEPtjj: 180| 37.3M| uint32_t mask) { 181| 37.3M| constexpr uint32_t kMagic = 2654435761U; 182| 37.3M| const uint32_t hash = (kMagic * bytes) >> (32 - kMaxHashTableBits); 183| 37.3M| return reinterpret_cast(reinterpret_cast(table) + 184| 37.3M| (hash & mask)); 185| 37.3M|} _ZN6snappy15CalculateNeededEh: 1684| 14.3k|constexpr uint32_t CalculateNeeded(uint8_t tag) { 1685| 14.3k| return ((tag & 3) == 0 && tag >= (60 * 4)) ------------------ | Branch (1685:11): [True: 11.5k, False: 2.74k] | Branch (1685:29): [True: 1.41k, False: 10.1k] ------------------ 1686| 14.3k| ? (tag >> 2) - 58 1687| 14.3k| : (0x05030201 >> ((tag * 8) & 31)) & 0xFF; 1688| 14.3k|} _ZN6snappy18SnappyDecompressorC2EPNS_6SourceE: 1520| 10.4k| : reader_(reader), ip_(NULL), ip_limit_(NULL), peeked_(0), eof_(false) {} _ZN6snappy18SnappyDecompressor22ReadUncompressedLengthEPj: 1533| 10.4k| bool ReadUncompressedLength(uint32_t* result) { 1534| 10.4k| assert(ip_ == NULL); // Must not have read anything yet 1535| | // Length is encoded in 1..5 bytes 1536| 10.4k| *result = 0; 1537| 10.4k| uint32_t shift = 0; 1538| 17.7k| while (true) { ------------------ | Branch (1538:12): [Folded - Ignored] ------------------ 1539| 17.7k| if (shift >= 32) return false; ------------------ | Branch (1539:11): [True: 0, False: 17.7k] ------------------ 1540| 17.7k| size_t n; 1541| 17.7k| const char* ip = reader_->Peek(&n); 1542| 17.7k| if (n == 0) return false; ------------------ | Branch (1542:11): [True: 0, False: 17.7k] ------------------ 1543| 17.7k| const unsigned char c = *(reinterpret_cast(ip)); 1544| 17.7k| reader_->Skip(1); 1545| 17.7k| uint32_t val = c & 0x7f; 1546| 17.7k| if (LeftShiftOverflows(static_cast(val), shift)) return false; ------------------ | Branch (1546:11): [True: 0, False: 17.7k] ------------------ 1547| 17.7k| *result |= val << shift; 1548| 17.7k| if (c < 128) { ------------------ | Branch (1548:11): [True: 10.4k, False: 7.23k] ------------------ 1549| 10.4k| break; 1550| 10.4k| } 1551| 7.23k| shift += 7; 1552| 7.23k| } 1553| 10.4k| return true; 1554| 10.4k| } snappy.cc:_ZN6snappyL18LeftShiftOverflowsEhj: 1207| 17.7k|static inline bool LeftShiftOverflows(uint8_t value, uint32_t shift) { 1208| 17.7k| assert(shift < 32); 1209| 17.7k| static const uint8_t masks[] = { 1210| 17.7k| 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 1211| 17.7k| 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 1212| 17.7k| 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 1213| 17.7k| 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe}; 1214| 17.7k| return (value & masks[shift]) != 0; 1215| 17.7k|} _ZN6snappy18SnappyDecompressorD2Ev: 1522| 10.4k| ~SnappyDecompressor() { 1523| | // Advance past any bytes we peeked at from the reader 1524| 10.4k| reader_->Skip(peeked_); 1525| 10.4k| } snappy.cc:_ZN6snappyL6ReportEiPKcmm: 1130| 15.7k|compressed_size, size_t uncompressed_size) { 1131| | // TODO: Switch to [[maybe_unused]] when we can assume C++17. 1132| 15.7k| (void)token; 1133| 15.7k| (void)algorithm; 1134| 15.7k| (void)compressed_size; 1135| 15.7k| (void)uncompressed_size; 1136| 15.7k|} _ZN6snappy17SnappyArrayWriterC2EPc: 2156| 5.23k| : base_(dst), 2157| 5.23k| op_(dst), 2158| 5.23k| op_limit_(dst), 2159| 5.23k| op_limit_min_slop_(dst) {} // Safe default see invariant. _ZN6snappy28SnappyDecompressionValidatorC2Ev: 2261| 5.23k| inline SnappyDecompressionValidator() : expected_(0), produced_(0) {} snappy.cc:_ZN6snappyL11EmitLiteralILb1EEEPcS1_PKci: 614| 1.47M|static inline char* EmitLiteral(char* op, const char* literal, int len) { 615| | // The vast majority of copies are below 16 bytes, for which a 616| | // call to std::memcpy() is overkill. This fast path can sometimes 617| | // copy up to 15 bytes too much, but that is okay in the 618| | // main loop, since we have a bit to go on for both sides: 619| | // 620| | // - The input will always have kInputMarginBytes = 15 extra 621| | // available bytes, as long as we're in the main loop, and 622| | // if not, allow_fast_path = false. 623| | // - The output will always have 32 spare bytes (see 624| | // MaxCompressedLength). 625| 1.47M| assert(len > 0); // Zero-length literals are disallowed 626| 1.47M| int n = len - 1; 627| 1.47M| if (allow_fast_path && len <= 16) { ------------------ | Branch (627:7): [Folded - Ignored] | Branch (627:26): [True: 1.26M, False: 210k] ------------------ 628| | // Fits in tag byte 629| 1.26M| *op++ = LITERAL | (n << 2); 630| | 631| 1.26M| UnalignedCopy128(literal, op); 632| 1.26M| return op + len; 633| 1.26M| } 634| | 635| 210k| if (n < 60) { ------------------ | Branch (635:7): [True: 129k, False: 80.8k] ------------------ 636| | // Fits in tag byte 637| 129k| *op++ = LITERAL | (n << 2); 638| 129k| } else { 639| 80.8k| int count = (Bits::Log2Floor(n) >> 3) + 1; 640| 80.8k| assert(count >= 1); 641| 80.8k| assert(count <= 4); 642| 80.8k| *op++ = LITERAL | ((59 + count) << 2); 643| | // Encode in upcoming bytes. 644| | // Write 4 bytes, though we may care about only 1 of them. The output buffer 645| | // is guaranteed to have at least 3 more spaces left as 'len >= 61' holds 646| | // here and there is a std::memcpy() of size 'len' below. 647| 80.8k| LittleEndian::Store32(op, n); 648| 80.8k| op += count; 649| 80.8k| } 650| | // When allow_fast_path is true, we can overwrite up to 16 bytes. 651| 210k| if (allow_fast_path) { ------------------ | Branch (651:7): [Folded - Ignored] ------------------ 652| 210k| char* destination = op; 653| 210k| const char* source = literal; 654| 210k| const char* end = destination + len; 655| 3.56M| do { 656| 3.56M| std::memcpy(destination, source, 16); 657| 3.56M| destination += 16; 658| 3.56M| source += 16; 659| 3.56M| } while (destination < end); ------------------ | Branch (659:14): [True: 3.35M, False: 210k] ------------------ 660| 210k| } else { 661| 0| std::memcpy(op, literal, len); 662| 0| } 663| 210k| return op + len; 664| 210k|} snappy.cc:_ZN6snappyL8EmitCopyILb1EEEPcS1_mm: 696| 4.64M|static inline char* EmitCopy(char* op, size_t offset, size_t len) { 697| 4.64M| assert(len_less_than_12 == (len < 12)); 698| 4.64M| if (len_less_than_12) { ------------------ | Branch (698:7): [Folded - Ignored] ------------------ 699| 4.64M| return EmitCopyAtMost64(op, offset, len); 700| 4.64M| } else { 701| | // A special case for len <= 64 might help, but so far measurements suggest 702| | // it's in the noise. 703| | 704| | // Emit 64 byte copies but make sure to keep at least four bytes reserved. 705| 0| while (SNAPPY_PREDICT_FALSE(len >= 68)) { ------------------ | | 94| 0|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 0, False: 0] | | ------------------ ------------------ 706| 0| op = EmitCopyAtMost64(op, offset, 64); 707| 0| len -= 64; 708| 0| } 709| | 710| | // One or two copies will now finish the job. 711| 0| if (len > 64) { ------------------ | Branch (711:9): [True: 0, False: 0] ------------------ 712| 0| op = EmitCopyAtMost64(op, offset, 60); 713| 0| len -= 60; 714| 0| } 715| | 716| | // Emit remainder. 717| 0| if (len < 12) { ------------------ | Branch (717:9): [True: 0, False: 0] ------------------ 718| 0| op = EmitCopyAtMost64(op, offset, len); 719| 0| } else { 720| 0| op = EmitCopyAtMost64(op, offset, len); 721| 0| } 722| 0| return op; 723| 0| } 724| 4.64M|} snappy.cc:_ZN6snappyL16EmitCopyAtMost64ILb1EEEPcS1_mm: 667| 4.68M|static inline char* EmitCopyAtMost64(char* op, size_t offset, size_t len) { 668| 4.68M| assert(len <= 64); 669| 4.68M| assert(len >= 4); 670| 4.68M| assert(offset < 65536); 671| 4.68M| assert(len_less_than_12 == (len < 12)); 672| | 673| 4.68M| if (len_less_than_12) { ------------------ | Branch (673:7): [Folded - Ignored] ------------------ 674| 4.68M| uint32_t u = (len << 2) + (offset << 8); 675| 4.68M| uint32_t copy1 = COPY_1_BYTE_OFFSET - (4 << 2) + ((offset >> 3) & 0xe0); 676| 4.68M| uint32_t copy2 = COPY_2_BYTE_OFFSET - (1 << 2); 677| | // It turns out that offset < 2048 is a difficult to predict branch. 678| | // `perf record` shows this is the highest percentage of branch misses in 679| | // benchmarks. This code produces branch free code, the data dependency 680| | // chain that bottlenecks the throughput is so long that a few extra 681| | // instructions are completely free (IPC << 6 because of data deps). 682| 4.68M| u += offset < 2048 ? copy1 : copy2; ------------------ | Branch (682:10): [True: 2.62M, False: 2.05M] ------------------ 683| 4.68M| LittleEndian::Store32(op, u); 684| 4.68M| op += offset < 2048 ? 2 : 3; ------------------ | Branch (684:11): [True: 2.62M, False: 2.05M] ------------------ 685| 4.68M| } else { 686| | // Write 4 bytes, though we only care about 3 of them. The output buffer 687| | // is required to have some slack, so the extra byte won't overrun it. 688| 0| uint32_t u = COPY_2_BYTE_OFFSET + ((len - 1) << 2) + (offset << 8); 689| 0| LittleEndian::Store32(op, u); 690| 0| op += 3; 691| 0| } 692| 4.68M| return op; 693| 4.68M|} snappy.cc:_ZN6snappyL8EmitCopyILb0EEEPcS1_mm: 696| 2.09M|static inline char* EmitCopy(char* op, size_t offset, size_t len) { 697| 2.09M| assert(len_less_than_12 == (len < 12)); 698| 2.09M| if (len_less_than_12) { ------------------ | Branch (698:7): [Folded - Ignored] ------------------ 699| 0| return EmitCopyAtMost64(op, offset, len); 700| 2.09M| } else { 701| | // A special case for len <= 64 might help, but so far measurements suggest 702| | // it's in the noise. 703| | 704| | // Emit 64 byte copies but make sure to keep at least four bytes reserved. 705| 4.02M| while (SNAPPY_PREDICT_FALSE(len >= 68)) { ------------------ | | 94| 4.02M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 1.93M, False: 2.09M] | | ------------------ ------------------ 706| 1.93M| op = EmitCopyAtMost64(op, offset, 64); 707| 1.93M| len -= 64; 708| 1.93M| } 709| | 710| | // One or two copies will now finish the job. 711| 2.09M| if (len > 64) { ------------------ | Branch (711:9): [True: 10.9k, False: 2.08M] ------------------ 712| 10.9k| op = EmitCopyAtMost64(op, offset, 60); 713| 10.9k| len -= 60; 714| 10.9k| } 715| | 716| | // Emit remainder. 717| 2.09M| if (len < 12) { ------------------ | Branch (717:9): [True: 41.6k, False: 2.05M] ------------------ 718| 41.6k| op = EmitCopyAtMost64(op, offset, len); 719| 2.05M| } else { 720| 2.05M| op = EmitCopyAtMost64(op, offset, len); 721| 2.05M| } 722| 2.09M| return op; 723| 2.09M| } 724| 2.09M|} snappy.cc:_ZN6snappyL16EmitCopyAtMost64ILb0EEEPcS1_mm: 667| 3.99M|static inline char* EmitCopyAtMost64(char* op, size_t offset, size_t len) { 668| 3.99M| assert(len <= 64); 669| 3.99M| assert(len >= 4); 670| 3.99M| assert(offset < 65536); 671| 3.99M| assert(len_less_than_12 == (len < 12)); 672| | 673| 3.99M| if (len_less_than_12) { ------------------ | Branch (673:7): [Folded - Ignored] ------------------ 674| 0| uint32_t u = (len << 2) + (offset << 8); 675| 0| uint32_t copy1 = COPY_1_BYTE_OFFSET - (4 << 2) + ((offset >> 3) & 0xe0); 676| 0| uint32_t copy2 = COPY_2_BYTE_OFFSET - (1 << 2); 677| | // It turns out that offset < 2048 is a difficult to predict branch. 678| | // `perf record` shows this is the highest percentage of branch misses in 679| | // benchmarks. This code produces branch free code, the data dependency 680| | // chain that bottlenecks the throughput is so long that a few extra 681| | // instructions are completely free (IPC << 6 because of data deps). 682| 0| u += offset < 2048 ? copy1 : copy2; ------------------ | Branch (682:10): [True: 0, False: 0] ------------------ 683| 0| LittleEndian::Store32(op, u); 684| 0| op += offset < 2048 ? 2 : 3; ------------------ | Branch (684:11): [True: 0, False: 0] ------------------ 685| 3.99M| } else { 686| | // Write 4 bytes, though we only care about 3 of them. The output buffer 687| | // is required to have some slack, so the extra byte won't overrun it. 688| 3.99M| uint32_t u = COPY_2_BYTE_OFFSET + ((len - 1) << 2) + (offset << 8); 689| 3.99M| LittleEndian::Store32(op, u); 690| 3.99M| op += 3; 691| 3.99M| } 692| 3.99M| return op; 693| 3.99M|} snappy.cc:_ZN6snappyL11EmitLiteralILb0EEEPcS1_PKci: 614| 6.86k|static inline char* EmitLiteral(char* op, const char* literal, int len) { 615| | // The vast majority of copies are below 16 bytes, for which a 616| | // call to std::memcpy() is overkill. This fast path can sometimes 617| | // copy up to 15 bytes too much, but that is okay in the 618| | // main loop, since we have a bit to go on for both sides: 619| | // 620| | // - The input will always have kInputMarginBytes = 15 extra 621| | // available bytes, as long as we're in the main loop, and 622| | // if not, allow_fast_path = false. 623| | // - The output will always have 32 spare bytes (see 624| | // MaxCompressedLength). 625| 6.86k| assert(len > 0); // Zero-length literals are disallowed 626| 6.86k| int n = len - 1; 627| 6.86k| if (allow_fast_path && len <= 16) { ------------------ | Branch (627:7): [Folded - Ignored] | Branch (627:26): [True: 0, False: 0] ------------------ 628| | // Fits in tag byte 629| 0| *op++ = LITERAL | (n << 2); 630| | 631| 0| UnalignedCopy128(literal, op); 632| 0| return op + len; 633| 0| } 634| | 635| 6.86k| if (n < 60) { ------------------ | Branch (635:7): [True: 4.42k, False: 2.43k] ------------------ 636| | // Fits in tag byte 637| 4.42k| *op++ = LITERAL | (n << 2); 638| 4.42k| } else { 639| 2.43k| int count = (Bits::Log2Floor(n) >> 3) + 1; 640| 2.43k| assert(count >= 1); 641| 2.43k| assert(count <= 4); 642| 2.43k| *op++ = LITERAL | ((59 + count) << 2); 643| | // Encode in upcoming bytes. 644| | // Write 4 bytes, though we may care about only 1 of them. The output buffer 645| | // is guaranteed to have at least 3 more spaces left as 'len >= 61' holds 646| | // here and there is a std::memcpy() of size 'len' below. 647| 2.43k| LittleEndian::Store32(op, n); 648| 2.43k| op += count; 649| 2.43k| } 650| | // When allow_fast_path is true, we can overwrite up to 16 bytes. 651| 6.86k| if (allow_fast_path) { ------------------ | Branch (651:7): [Folded - Ignored] ------------------ 652| 0| char* destination = op; 653| 0| const char* source = literal; 654| 0| const char* end = destination + len; 655| 0| do { 656| 0| std::memcpy(destination, source, 16); 657| 0| destination += 16; 658| 0| source += 16; 659| 0| } while (destination < end); ------------------ | Branch (659:14): [True: 0, False: 0] ------------------ 660| 6.86k| } else { 661| 6.86k| std::memcpy(op, literal, len); 662| 6.86k| } 663| 6.86k| return op + len; 664| 6.86k|} _ZN6snappy18SnappyDecompressor10ResetLimitEPKc: 1513| 24.7k| void ResetLimit(const char* ip) { 1514| 24.7k| ip_limit_min_maxtaglen_ = 1515| 24.7k| ip_limit_ - std::min(ip_limit_ - ip, kMaximumTagLength - 1); 1516| 24.7k| } _ZN6snappy20DecompressBranchlessIPcEENSt3__14pairIPKhlEES5_S5_lT_l: 1382| 134k| ptrdiff_t op_limit_min_slop) { 1383| | // If deferred_src is invalid point it here. 1384| 134k| uint8_t safe_source[64]; 1385| 134k| const void* deferred_src; 1386| 134k| size_t deferred_length; 1387| 134k| ClearDeferred(&deferred_src, &deferred_length, safe_source); 1388| | 1389| | // We unroll the inner loop twice so we need twice the spare room. 1390| 134k| op_limit_min_slop -= kSlopBytes; 1391| 134k| if (2 * (kSlopBytes + 1) < ip_limit - ip && op < op_limit_min_slop) { ------------------ | Branch (1391:7): [True: 84.0k, False: 50.5k] | Branch (1391:47): [True: 84.0k, False: 0] ------------------ 1392| 84.0k| const uint8_t* const ip_limit_min_slop = ip_limit - 2 * kSlopBytes - 1; 1393| 84.0k| ip++; 1394| | // ip points just past the tag and we are touching at maximum kSlopBytes 1395| | // in an iteration. 1396| 84.0k| size_t tag = ip[-1]; 1397| |#if defined(__clang__) && defined(__aarch64__) 1398| | // Workaround for https://bugs.llvm.org/show_bug.cgi?id=51317 1399| | // when loading 1 byte, clang for aarch64 doesn't realize that it(ldrb) 1400| | // comes with free zero-extension, so clang generates another 1401| | // 'and xn, xm, 0xff' before it use that as the offset. This 'and' is 1402| | // redundant and can be removed by adding this dummy asm, which gives 1403| | // clang a hint that we're doing the zero-extension at the load. 1404| | asm("" ::"r"(tag)); 1405| |#endif 1406| 5.60M| do { 1407| | // The throughput is limited by instructions, unrolling the inner loop 1408| | // twice reduces the amount of instructions checking limits and also 1409| | // leads to reduced mov's. 1410| | 1411| 5.60M| SNAPPY_PREFETCH(ip + 128); ------------------ | | 109| 5.60M|#define SNAPPY_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 3) ------------------ 1412| 16.7M| for (int i = 0; i < 2; i++) { ------------------ | Branch (1412:23): [True: 11.1M, False: 5.52M] ------------------ 1413| 11.1M| const uint8_t* old_ip = ip; 1414| 11.1M| assert(tag == ip[-1]); 1415| | // For literals tag_type = 0, hence we will always obtain 0 from 1416| | // ExtractLowBytes. For literals offset will thus be kLiteralOffset. 1417| 11.1M| ptrdiff_t len_minus_offset = kLengthMinusOffset[tag]; 1418| 11.1M| uint32_t next; 1419| |#if defined(__aarch64__) 1420| | size_t tag_type = AdvanceToNextTagARMOptimized(&ip, &tag); 1421| | // We never need more than 16 bits. Doing a Load16 allows the compiler 1422| | // to elide the masking operation in ExtractOffset. 1423| | next = LittleEndian::Load16(old_ip); 1424| |#else 1425| 11.1M| size_t tag_type = AdvanceToNextTagX86Optimized(&ip, &tag); 1426| 11.1M| next = LittleEndian::Load32(old_ip); 1427| 11.1M|#endif 1428| 11.1M| size_t len = len_minus_offset & 0xFF; 1429| 11.1M| ptrdiff_t extracted = ExtractOffset(next, tag_type); 1430| 11.1M| ptrdiff_t len_min_offset = len_minus_offset - extracted; 1431| 11.1M| if (SNAPPY_PREDICT_FALSE(len_minus_offset > extracted)) { ------------------ | | 94| 11.1M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 1.40M, False: 9.77M] | | ------------------ ------------------ 1432| 1.40M| if (SNAPPY_PREDICT_FALSE(len & 0x80)) { ------------------ | | 94| 1.40M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 82.6k, False: 1.32M] | | ------------------ ------------------ 1433| | // Exceptional case (long literal or copy 4). 1434| | // Actually doing the copy here is negatively impacting the main 1435| | // loop due to compiler incorrectly allocating a register for 1436| | // this fallback. Hence we just break. 1437| 82.6k| break_loop: 1438| 82.6k| ip = old_ip; 1439| 82.6k| goto exit; 1440| 82.6k| } 1441| | // Only copy-1 or copy-2 tags can get here. 1442| 1.32M| assert(tag_type == 1 || tag_type == 2); 1443| 1.32M| std::ptrdiff_t delta = (op + deferred_length) + len_min_offset - len; 1444| | // Guard against copies before the buffer start. 1445| | // Execute any deferred MemCopy since we write to dst here. 1446| 1.32M| MemCopy64(op_base + op, deferred_src, deferred_length); 1447| 1.32M| op += deferred_length; 1448| 1.32M| ClearDeferred(&deferred_src, &deferred_length, safe_source); 1449| 1.32M| if (SNAPPY_PREDICT_FALSE(delta < 0 || ------------------ | | 94| 2.64M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 0, False: 1.32M] | | | Branch (94:51): [True: 0, False: 1.32M] | | | Branch (94:51): [True: 0, False: 1.32M] | | ------------------ ------------------ 1450| 1.32M| !Copy64BytesWithPatternExtension( 1451| 1.32M| op_base + op, len - len_min_offset))) { 1452| 0| goto break_loop; 1453| 0| } 1454| | // We aren't deferring this copy so add length right away. 1455| 1.32M| op += len; 1456| 1.32M| continue; 1457| 1.32M| } 1458| 9.77M| std::ptrdiff_t delta = (op + deferred_length) + len_min_offset - len; 1459| 9.77M| if (SNAPPY_PREDICT_FALSE(delta < 0)) { ------------------ | | 94| 9.77M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 13.4k, False: 9.76M] | | ------------------ ------------------ 1460| | // Due to the spurious offset in literals have this will trigger 1461| | // at the start of a block when op is still smaller than 256. 1462| 13.4k| if (tag_type != 0) goto break_loop; ------------------ | Branch (1462:15): [True: 0, False: 13.4k] ------------------ 1463| 13.4k| MemCopy64(op_base + op, deferred_src, deferred_length); 1464| 13.4k| op += deferred_length; 1465| 13.4k| DeferMemCopy(&deferred_src, &deferred_length, old_ip, len); 1466| 13.4k| continue; 1467| 13.4k| } 1468| | 1469| | // For copies we need to copy from op_base + delta, for literals 1470| | // we need to copy from ip instead of from the stream. 1471| 9.76M| const void* from = 1472| 9.76M| tag_type ? reinterpret_cast(op_base + delta) : old_ip; ------------------ | Branch (1472:13): [True: 7.32M, False: 2.44M] ------------------ 1473| 9.76M| MemCopy64(op_base + op, deferred_src, deferred_length); 1474| 9.76M| op += deferred_length; 1475| 9.76M| DeferMemCopy(&deferred_src, &deferred_length, from, len); 1476| 9.76M| } 1477| 5.60M| } while (ip < ip_limit_min_slop && ------------------ | Branch (1477:14): [True: 5.52M, False: 1.43k] ------------------ 1478| 5.52M| static_cast(op + deferred_length) < op_limit_min_slop); ------------------ | Branch (1478:14): [True: 5.52M, False: 2] ------------------ 1479| 84.0k| exit: 1480| 84.0k| ip--; 1481| 84.0k| assert(ip <= ip_limit); 1482| 84.0k| } 1483| | // If we deferred a copy then we can perform. If we are up to date then we 1484| | // might not have enough slop bytes and could run past the end. 1485| 134k| if (deferred_length) { ------------------ | Branch (1485:7): [True: 71.5k, False: 62.9k] ------------------ 1486| 71.5k| MemCopy64(op_base + op, deferred_src, deferred_length); 1487| 71.5k| op += deferred_length; 1488| 71.5k| ClearDeferred(&deferred_src, &deferred_length, safe_source); 1489| 71.5k| } 1490| 134k| return {ip, op}; 1491| 134k|} _ZN6snappy28AdvanceToNextTagX86OptimizedEPPKhPm: 1303| 22.3M|inline size_t AdvanceToNextTagX86Optimized(const uint8_t** ip_p, size_t* tag) { 1304| 22.3M| const uint8_t*& ip = *ip_p; 1305| | // This section is crucial for the throughput of the decompression loop. 1306| | // The latency of an iteration is fundamentally constrained by the 1307| | // following data chain on ip. 1308| | // ip -> c = Load(ip) -> ip1 = ip + 1 + (c & 3) -> ip = ip1 or ip2 1309| | // ip2 = ip + 2 + (c >> 2) 1310| | // This amounts to 8 cycles. 1311| | // 5 (load) + 1 (c & 3) + 1 (lea ip1, [ip + (c & 3) + 1]) + 1 (cmov) 1312| 22.3M| size_t literal_len = *tag >> 2; 1313| 22.3M| size_t tag_type = *tag; 1314| 22.3M| bool is_literal; 1315| 22.3M|#if defined(__GCC_ASM_FLAG_OUTPUTS__) && defined(__x86_64__) 1316| | // TODO clang misses the fact that the (c & 3) already correctly 1317| | // sets the zero flag. 1318| 22.3M| asm("and $3, %k[tag_type]\n\t" 1319| 22.3M| : [tag_type] "+r"(tag_type), "=@ccz"(is_literal) 1320| 22.3M| :: "cc"); 1321| |#else 1322| | tag_type &= 3; 1323| | is_literal = (tag_type == 0); 1324| |#endif 1325| | // TODO 1326| | // This is code is subtle. Loading the values first and then cmov has less 1327| | // latency then cmov ip and then load. However clang would move the loads 1328| | // in an optimization phase, volatile prevents this transformation. 1329| | // Note that we have enough slop bytes (64) that the loads are always valid. 1330| 22.3M| size_t tag_literal = 1331| 22.3M| static_cast(ip)[1 + literal_len]; 1332| 22.3M| size_t tag_copy = static_cast(ip)[tag_type]; 1333| 22.3M| *tag = is_literal ? tag_literal : tag_copy; ------------------ | Branch (1333:10): [True: 5.07M, False: 17.2M] ------------------ 1334| 22.3M| const uint8_t* ip_copy = ip + 1 + tag_type; 1335| 22.3M| const uint8_t* ip_literal = ip + 2 + literal_len; 1336| 22.3M| ip = is_literal ? ip_literal : ip_copy; ------------------ | Branch (1336:8): [True: 5.07M, False: 17.2M] ------------------ 1337| 22.3M|#if defined(__GNUC__) && defined(__x86_64__) 1338| | // TODO Clang is "optimizing" zero-extension (a totally free 1339| | // operation) this means that after the cmov of tag, it emits another movzb 1340| | // tag, byte(tag). It really matters as it's on the core chain. This dummy 1341| | // asm, persuades clang to do the zero-extension at the load (it's automatic) 1342| | // removing the expensive movzb. 1343| 22.3M| asm("" ::"r"(tag_copy)); 1344| 22.3M|#endif 1345| 22.3M| return tag_type; 1346| 22.3M|} _ZN6snappy13ExtractOffsetEjm: 1349| 22.3M|inline uint32_t ExtractOffset(uint32_t val, size_t tag_type) { 1350| | // For x86 non-static storage works better. For ARM static storage is better. 1351| | // TODO: Once the array is recognized as a register, improve the 1352| | // readability for x86. 1353| 22.3M|#if defined(__x86_64__) 1354| 22.3M| constexpr uint64_t kExtractMasksCombined = 0x0000FFFF00FF0000ull; 1355| 22.3M| uint16_t result; 1356| 22.3M| memcpy(&result, 1357| 22.3M| reinterpret_cast(&kExtractMasksCombined) + 2 * tag_type, 1358| 22.3M| sizeof(result)); 1359| 22.3M| return val & result; 1360| |#elif defined(__aarch64__) 1361| | constexpr uint64_t kExtractMasksCombined = 0x0000FFFF00FF0000ull; 1362| | return val & static_cast( 1363| | (kExtractMasksCombined >> (tag_type * 16)) & 0xFFFF); 1364| |#else 1365| | static constexpr uint32_t kExtractMasks[4] = {0, 0xFF, 0xFFFF, 0}; 1366| | return val & kExtractMasks[tag_type]; 1367| |#endif 1368| 22.3M|}; snappy.cc:_ZN6snappy12_GLOBAL__N_131Copy64BytesWithPatternExtensionEPcm: 356| 1.32M|static inline bool Copy64BytesWithPatternExtension(char* dst, size_t offset) { 357| |#if SNAPPY_HAVE_VECTOR_BYTE_SHUFFLE 358| | if (SNAPPY_PREDICT_TRUE(offset <= 16)) { 359| | switch (offset) { 360| | case 0: 361| | return false; 362| | case 1: { 363| | // TODO: Ideally we should memset, move back once the 364| | // codegen issues are fixed. 365| | V128 pattern = V128_DupChar(dst[-1]); 366| | for (int i = 0; i < 4; i++) { 367| | V128_StoreU(reinterpret_cast(dst + 16 * i), pattern); 368| | } 369| | return true; 370| | } 371| | case 2: 372| | case 4: 373| | case 8: 374| | case 16: { 375| | V128 pattern = LoadPattern(dst - offset, offset); 376| | for (int i = 0; i < 4; i++) { 377| | V128_StoreU(reinterpret_cast(dst + 16 * i), pattern); 378| | } 379| | return true; 380| | } 381| | default: { 382| | auto pattern_and_reshuffle_mask = 383| | LoadPatternAndReshuffleMask(dst - offset, offset); 384| | V128 pattern = pattern_and_reshuffle_mask.first; 385| | V128 reshuffle_mask = pattern_and_reshuffle_mask.second; 386| | for (int i = 0; i < 4; i++) { 387| | V128_StoreU(reinterpret_cast(dst + 16 * i), pattern); 388| | pattern = V128_Shuffle(pattern, reshuffle_mask); 389| | } 390| | return true; 391| | } 392| | } 393| | } 394| |#else 395| 1.32M| if (SNAPPY_PREDICT_TRUE(offset < 16)) { ------------------ | | 95| 1.32M|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 1.31M, False: 12.2k] | | ------------------ ------------------ 396| 1.31M| if (SNAPPY_PREDICT_FALSE(offset == 0)) return false; ------------------ | | 94| 1.31M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 0, False: 1.31M] | | ------------------ ------------------ 397| | // Extend the pattern to the first 16 bytes. 398| | // The simpler formulation of `dst[i - offset]` induces undefined behavior. 399| 22.2M| for (int i = 0; i < 16; i++) dst[i] = (dst - offset)[i]; ------------------ | Branch (399:21): [True: 20.9M, False: 1.31M] ------------------ 400| | // Find a multiple of pattern >= 16. 401| 1.31M| static std::array pattern_sizes = []() { 402| 1.31M| std::array res; 403| 1.31M| for (int i = 1; i < 16; i++) res[i] = (16 / i + 1) * i; 404| 1.31M| return res; 405| 1.31M| }(); 406| 1.31M| offset = pattern_sizes[offset]; 407| 5.24M| for (int i = 1; i < 4; i++) { ------------------ | Branch (407:21): [True: 3.93M, False: 1.31M] ------------------ 408| 3.93M| std::memcpy(dst + i * 16, dst + i * 16 - offset, 16); 409| 3.93M| } 410| 1.31M| return true; 411| 1.31M| } 412| 12.2k|#endif // SNAPPY_HAVE_VECTOR_BYTE_SHUFFLE 413| | 414| | // Very rare. 415| 61.4k| for (int i = 0; i < 4; i++) { ------------------ | Branch (415:19): [True: 49.1k, False: 12.2k] ------------------ 416| 49.1k| std::memcpy(dst + i * 16, dst + i * 16 - offset, 16); 417| 49.1k| } 418| 12.2k| return true; 419| 1.32M|} snappy.cc:_ZZN6snappy12_GLOBAL__N_131Copy64BytesWithPatternExtensionEPcmENKUlvE_clEv: 401| 1| static std::array pattern_sizes = []() { 402| 1| std::array res; 403| 16| for (int i = 1; i < 16; i++) res[i] = (16 / i + 1) * i; ------------------ | Branch (403:23): [True: 15, False: 1] ------------------ 404| 1| return res; 405| 1| }(); snappy.cc:_ZN6snappyL15ExtractLowBytesERKji: 1194| 241k|static inline uint32_t ExtractLowBytes(const uint32_t& v, int n) { 1195| 241k| assert(n >= 0); 1196| 241k| assert(n <= 4); 1197| |#if SNAPPY_HAVE_BMI2 1198| | return _bzhi_u32(v, 8 * n); 1199| |#else 1200| | // This needs to be wider than uint32_t otherwise `mask << 32` will be 1201| | // undefined. 1202| 241k| uint64_t mask = 0xffffffff; 1203| 241k| return v & ~(mask << (8 * n)); 1204| 241k|#endif 1205| 241k|} snappy.cc:_ZN6snappy12_GLOBAL__N_115IncrementalCopyEPKcPcS3_S3_: 425| 18.6k| char* const buf_limit) { 426| |#if SNAPPY_HAVE_VECTOR_BYTE_SHUFFLE 427| | constexpr int big_pattern_size_lower_bound = 16; 428| |#else 429| 18.6k| constexpr int big_pattern_size_lower_bound = 8; 430| 18.6k|#endif 431| | 432| | // Terminology: 433| | // 434| | // slop = buf_limit - op 435| | // pat = op - src 436| | // len = op_limit - op 437| 18.6k| assert(src < op); 438| 18.6k| assert(op < op_limit); 439| 18.6k| assert(op_limit <= buf_limit); 440| | // NOTE: The copy tags use 3 or 6 bits to store the copy length, so len <= 64. 441| 18.6k| assert(op_limit - op <= 64); 442| | // NOTE: In practice the compressor always emits len >= 4, so it is ok to 443| | // assume that to optimize this function, but this is not guaranteed by the 444| | // compression format, so we have to also handle len < 4 in case the input 445| | // does not satisfy these conditions. 446| | 447| 18.6k| size_t pattern_size = op - src; 448| | // The cases are split into different branches to allow the branch predictor, 449| | // FDO, and static prediction hints to work better. For each input we list the 450| | // ratio of invocations that match each condition. 451| | // 452| | // input slop < 16 pat < 8 len > 16 453| | // ------------------------------------------ 454| | // html|html4|cp 0% 1.01% 27.73% 455| | // urls 0% 0.88% 14.79% 456| | // jpg 0% 64.29% 7.14% 457| | // pdf 0% 2.56% 58.06% 458| | // txt[1-4] 0% 0.23% 0.97% 459| | // pb 0% 0.96% 13.88% 460| | // bin 0.01% 22.27% 41.17% 461| | // 462| | // It is very rare that we don't have enough slop for doing block copies. It 463| | // is also rare that we need to expand a pattern. Small patterns are common 464| | // for incompressible formats and for those we are plenty fast already. 465| | // Lengths are normally not greater than 16 but they vary depending on the 466| | // input. In general if we always predict len <= 16 it would be an ok 467| | // prediction. 468| | // 469| | // In order to be fast we want a pattern >= 16 bytes (or 8 bytes in non-SSE) 470| | // and an unrolled loop copying 1x 16 bytes (or 2x 8 bytes in non-SSE) at a 471| | // time. 472| | 473| | // Handle the uncommon case where pattern is less than 16 (or 8 in non-SSE) 474| | // bytes. 475| 18.6k| if (pattern_size < big_pattern_size_lower_bound) { ------------------ | Branch (475:7): [True: 15.2k, False: 3.38k] ------------------ 476| |#if SNAPPY_HAVE_VECTOR_BYTE_SHUFFLE 477| | // Load the first eight bytes into an 128-bit XMM register, then use PSHUFB 478| | // to permute the register's contents in-place into a repeating sequence of 479| | // the first "pattern_size" bytes. 480| | // For example, suppose: 481| | // src == "abc" 482| | // op == op + 3 483| | // After V128_Shuffle(), "pattern" will have five copies of "abc" 484| | // followed by one byte of slop: abcabcabcabcabca. 485| | // 486| | // The non-SSE fallback implementation suffers from store-forwarding stalls 487| | // because its loads and stores partly overlap. By expanding the pattern 488| | // in-place, we avoid the penalty. 489| | 490| | // Typically, the op_limit is the gating factor so try to simplify the loop 491| | // based on that. 492| | if (SNAPPY_PREDICT_TRUE(op_limit <= buf_limit - 15)) { 493| | auto pattern_and_reshuffle_mask = 494| | LoadPatternAndReshuffleMask(src, pattern_size); 495| | V128 pattern = pattern_and_reshuffle_mask.first; 496| | V128 reshuffle_mask = pattern_and_reshuffle_mask.second; 497| | 498| | // There is at least one, and at most four 16-byte blocks. Writing four 499| | // conditionals instead of a loop allows FDO to layout the code with 500| | // respect to the actual probabilities of each length. 501| | // TODO: Replace with loop with trip count hint. 502| | V128_StoreU(reinterpret_cast(op), pattern); 503| | 504| | if (op + 16 < op_limit) { 505| | pattern = V128_Shuffle(pattern, reshuffle_mask); 506| | V128_StoreU(reinterpret_cast(op + 16), pattern); 507| | } 508| | if (op + 32 < op_limit) { 509| | pattern = V128_Shuffle(pattern, reshuffle_mask); 510| | V128_StoreU(reinterpret_cast(op + 32), pattern); 511| | } 512| | if (op + 48 < op_limit) { 513| | pattern = V128_Shuffle(pattern, reshuffle_mask); 514| | V128_StoreU(reinterpret_cast(op + 48), pattern); 515| | } 516| | return op_limit; 517| | } 518| | char* const op_end = buf_limit - 15; 519| | if (SNAPPY_PREDICT_TRUE(op < op_end)) { 520| | auto pattern_and_reshuffle_mask = 521| | LoadPatternAndReshuffleMask(src, pattern_size); 522| | V128 pattern = pattern_and_reshuffle_mask.first; 523| | V128 reshuffle_mask = pattern_and_reshuffle_mask.second; 524| | 525| | // This code path is relatively cold however so we save code size 526| | // by avoiding unrolling and vectorizing. 527| | // 528| | // TODO: Remove pragma when when cold regions don't get 529| | // vectorized or unrolled. 530| |#ifdef __clang__ 531| |#pragma clang loop unroll(disable) 532| |#endif 533| | do { 534| | V128_StoreU(reinterpret_cast(op), pattern); 535| | pattern = V128_Shuffle(pattern, reshuffle_mask); 536| | op += 16; 537| | } while (SNAPPY_PREDICT_TRUE(op < op_end)); 538| | } 539| | return IncrementalCopySlow(op - pattern_size, op, op_limit); 540| |#else // !SNAPPY_HAVE_VECTOR_BYTE_SHUFFLE 541| | // If plenty of buffer space remains, expand the pattern to at least 8 542| | // bytes. The way the following loop is written, we need 8 bytes of buffer 543| | // space if pattern_size >= 4, 11 bytes if pattern_size is 1 or 3, and 10 544| | // bytes if pattern_size is 2. Precisely encoding that is probably not 545| | // worthwhile; instead, invoke the slow path if we cannot write 11 bytes 546| | // (because 11 are required in the worst case). 547| 15.2k| if (SNAPPY_PREDICT_TRUE(op <= buf_limit - 11)) { ------------------ | | 95| 15.2k|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 15.1k, False: 110] | | ------------------ ------------------ 548| 54.6k| while (pattern_size < 8) { ------------------ | Branch (548:14): [True: 39.5k, False: 15.1k] ------------------ 549| 39.5k| UnalignedCopy64(src, op); 550| 39.5k| op += pattern_size; 551| 39.5k| pattern_size *= 2; 552| 39.5k| } 553| 15.1k| if (SNAPPY_PREDICT_TRUE(op >= op_limit)) return op_limit; ------------------ | | 95| 15.1k|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 5.17k, False: 9.98k] | | ------------------ ------------------ 554| 15.1k| } else { 555| 110| return IncrementalCopySlow(src, op, op_limit); 556| 110| } 557| 15.2k|#endif // SNAPPY_HAVE_VECTOR_BYTE_SHUFFLE 558| 15.2k| } 559| 13.3k| assert(pattern_size >= big_pattern_size_lower_bound); 560| 13.3k| constexpr bool use_16bytes_chunk = big_pattern_size_lower_bound == 16; 561| | 562| | // Copy 1x 16 bytes (or 2x 8 bytes in non-SSE) at a time. Because op - src can 563| | // be < 16 in non-SSE, a single UnalignedCopy128 might overwrite data in op. 564| | // UnalignedCopy64 is safe because expanding the pattern to at least 8 bytes 565| | // guarantees that op - src >= 8. 566| | // 567| | // Typically, the op_limit is the gating factor so try to simplify the loop 568| | // based on that. 569| 13.3k| if (SNAPPY_PREDICT_TRUE(op_limit <= buf_limit - 15)) { ------------------ | | 95| 13.3k|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 11.5k, False: 1.79k] | | ------------------ ------------------ 570| | // There is at least one, and at most four 16-byte blocks. Writing four 571| | // conditionals instead of a loop allows FDO to layout the code with respect 572| | // to the actual probabilities of each length. 573| | // TODO: Replace with loop with trip count hint. 574| 11.5k| ConditionalUnalignedCopy128(src, op); 575| 11.5k| if (op + 16 < op_limit) { ------------------ | Branch (575:9): [True: 8.06k, False: 3.50k] ------------------ 576| 8.06k| ConditionalUnalignedCopy128(src + 16, op + 16); 577| 8.06k| } 578| 11.5k| if (op + 32 < op_limit) { ------------------ | Branch (578:9): [True: 7.59k, False: 3.97k] ------------------ 579| 7.59k| ConditionalUnalignedCopy128(src + 32, op + 32); 580| 7.59k| } 581| 11.5k| if (op + 48 < op_limit) { ------------------ | Branch (581:9): [True: 7.30k, False: 4.26k] ------------------ 582| 7.30k| ConditionalUnalignedCopy128(src + 48, op + 48); 583| 7.30k| } 584| 11.5k| return op_limit; 585| 11.5k| } 586| | 587| | // Fall back to doing as much as we can with the available slop in the 588| | // buffer. This code path is relatively cold however so we save code size by 589| | // avoiding unrolling and vectorizing. 590| | // 591| | // TODO: Remove pragma when when cold regions don't get vectorized 592| | // or unrolled. 593| 1.79k|#ifdef __clang__ 594| 1.79k|#pragma clang loop unroll(disable) 595| 1.79k|#endif 596| 3.43k| for (char* op_end = buf_limit - 16; op < op_end; op += 16, src += 16) { ------------------ | Branch (596:39): [True: 1.63k, False: 1.79k] ------------------ 597| 1.63k| ConditionalUnalignedCopy128(src, op); 598| 1.63k| } 599| 1.79k| if (op >= op_limit) return op_limit; ------------------ | Branch (599:7): [True: 341, False: 1.45k] ------------------ 600| | 601| | // We only take this branch if we didn't have enough slop and we can do a 602| | // single 8 byte copy. 603| 1.45k| if (SNAPPY_PREDICT_FALSE(op <= buf_limit - 8)) { ------------------ | | 94| 1.45k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 1.16k, False: 293] | | ------------------ ------------------ 604| 1.16k| UnalignedCopy64(src, op); 605| 1.16k| src += 8; 606| 1.16k| op += 8; 607| 1.16k| } 608| 1.45k| return IncrementalCopySlow(src, op, op_limit); 609| 1.79k|} snappy.cc:_ZN6snappy12_GLOBAL__N_115UnalignedCopy64EPKvPv: 223| 113k|void UnalignedCopy64(const void* src, void* dst) { 224| 113k| char tmp[8]; 225| 113k| std::memcpy(tmp, src, 8); 226| 113k| std::memcpy(dst, tmp, 8); 227| 113k|} snappy.cc:_ZN6snappy12_GLOBAL__N_119IncrementalCopySlowEPKcPcS3_: 260| 1.56k| char* const op_limit) { 261| | // TODO: Remove pragma when LLVM is aware this 262| | // function is only called in cold regions and when cold regions don't get 263| | // vectorized or unrolled. 264| 1.56k|#ifdef __clang__ 265| 1.56k|#pragma clang loop unroll(disable) 266| 1.56k|#endif 267| 5.01k| while (op < op_limit) { ------------------ | Branch (267:10): [True: 3.44k, False: 1.56k] ------------------ 268| 3.44k| *op++ = *src++; 269| 3.44k| } 270| 1.56k| return op_limit; 271| 1.56k|} snappy.cc:_ZN6snappy12_GLOBAL__N_127ConditionalUnalignedCopy128ILb0EEEvPKcPc: 239| 36.1k|inline void ConditionalUnalignedCopy128(const char* src, char* dst) { 240| 36.1k| if (use_16bytes_chunk) { ------------------ | Branch (240:7): [Folded - Ignored] ------------------ 241| 0| UnalignedCopy128(src, dst); 242| 36.1k| } else { 243| 36.1k| UnalignedCopy64(src, dst); 244| 36.1k| UnalignedCopy64(src + 8, dst + 8); 245| 36.1k| } 246| 36.1k|} _ZNK6snappy18SnappyDecompressor3eofEv: 1528| 10.4k| bool eof() const { return eof_; } snappy.cc:_ZN6snappyL18InternalUncompressINS_17SnappyArrayWriterEEEbPNS_6SourceEPT_: 1767| 5.23k|static bool InternalUncompress(Source* r, Writer* writer) { 1768| | // Read the uncompressed length from the front of the compressed input 1769| 5.23k| SnappyDecompressor decompressor(r); 1770| 5.23k| uint32_t uncompressed_len = 0; 1771| 5.23k| if (!decompressor.ReadUncompressedLength(&uncompressed_len)) return false; ------------------ | Branch (1771:7): [True: 0, False: 5.23k] ------------------ 1772| | 1773| 5.23k| return InternalUncompressAllTags(&decompressor, writer, r->Available(), 1774| 5.23k| uncompressed_len); 1775| 5.23k|} snappy.cc:_ZN6snappyL18InternalUncompressINS_28SnappyDecompressionValidatorEEEbPNS_6SourceEPT_: 1767| 5.23k|static bool InternalUncompress(Source* r, Writer* writer) { 1768| | // Read the uncompressed length from the front of the compressed input 1769| 5.23k| SnappyDecompressor decompressor(r); 1770| 5.23k| uint32_t uncompressed_len = 0; 1771| 5.23k| if (!decompressor.ReadUncompressedLength(&uncompressed_len)) return false; ------------------ | Branch (1771:7): [True: 0, False: 5.23k] ------------------ 1772| | 1773| 5.23k| return InternalUncompressAllTags(&decompressor, writer, r->Available(), 1774| 5.23k| uncompressed_len); 1775| 5.23k|} snappy.cc:_ZN6snappyL25InternalUncompressAllTagsINS_28SnappyDecompressionValidatorEEEbPNS_18SnappyDecompressorEPT_jj: 1780| 5.23k| uint32_t uncompressed_len) { 1781| 5.23k| int token = 0; 1782| 5.23k| Report(token, "snappy_uncompress", compressed_len, uncompressed_len); 1783| | 1784| 5.23k| writer->SetExpectedLength(uncompressed_len); 1785| | 1786| | // Process the entire input 1787| 5.23k| decompressor->DecompressAllTags(writer); 1788| 5.23k| writer->Flush(); 1789| 5.23k| return (decompressor->eof() && writer->CheckLength()); ------------------ | Branch (1789:11): [True: 5.23k, False: 0] | Branch (1789:34): [True: 5.23k, False: 0] ------------------ 1790| 5.23k|} _ZN6snappy28SnappyDecompressionValidator17SetExpectedLengthEm: 2262| 5.23k| inline void SetExpectedLength(size_t len) { expected_ = len; } _ZN6snappy18SnappyDecompressor17DecompressAllTagsINS_28SnappyDecompressionValidatorEEEvPT_: 1563| 5.23k| DecompressAllTags(Writer* writer) { 1564| 5.23k| const char* ip = ip_; 1565| 5.23k| ResetLimit(ip); 1566| 5.23k| auto op = writer->GetOutputPtr(); 1567| | // We could have put this refill fragment only at the beginning of the loop. 1568| | // However, duplicating it at the end of each branch gives the compiler more 1569| | // scope to optimize the expression based on the local 1570| | // context, which overall increases speed. 1571| 5.23k|#define MAYBE_REFILL() \ 1572| 5.23k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ 1573| 5.23k| ip_ = ip; \ 1574| 5.23k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ 1575| 5.23k| ip = ip_; \ 1576| 5.23k| ResetLimit(ip); \ 1577| 5.23k| } \ 1578| 5.23k| preload = static_cast(*ip) 1579| | 1580| | // At the start of the for loop below the least significant byte of preload 1581| | // contains the tag. 1582| 5.23k| uint32_t preload; 1583| 5.23k| MAYBE_REFILL(); ------------------ | | 1572| 5.23k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 5.23k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 5.23k, False: 0] | | | | ------------------ | | ------------------ | | 1573| 5.23k| ip_ = ip; \ | | 1574| 5.23k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 5.23k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 0, False: 5.23k] | | | | ------------------ | | ------------------ | | 1575| 5.23k| ip = ip_; \ | | 1576| 5.23k| ResetLimit(ip); \ | | 1577| 5.23k| } \ | | 1578| 5.23k| preload = static_cast(*ip) ------------------ 1584| 139k| for (;;) { 1585| 139k| { 1586| 139k| ptrdiff_t op_limit_min_slop; 1587| 139k| auto op_base = writer->GetBase(&op_limit_min_slop); 1588| 139k| if (op_base) { ------------------ | Branch (1588:13): [True: 139k, False: 0] ------------------ 1589| 139k| auto res = 1590| 139k| DecompressBranchless(reinterpret_cast(ip), 1591| 139k| reinterpret_cast(ip_limit_), 1592| 139k| op - op_base, op_base, op_limit_min_slop); 1593| 139k| ip = reinterpret_cast(res.first); 1594| 139k| op = op_base + res.second; 1595| 139k| MAYBE_REFILL(); ------------------ | | 1572| 139k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 139k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 962, False: 138k] | | | | ------------------ | | ------------------ | | 1573| 962| ip_ = ip; \ | | 1574| 962| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 962|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 0, False: 962] | | | | ------------------ | | ------------------ | | 1575| 962| ip = ip_; \ | | 1576| 962| ResetLimit(ip); \ | | 1577| 962| } \ | | 1578| 139k| preload = static_cast(*ip) ------------------ 1596| 139k| } 1597| 139k| } 1598| 139k| const uint8_t c = static_cast(preload); 1599| 139k| ip++; 1600| | 1601| | // Ratio of iterations that have LITERAL vs non-LITERAL for different 1602| | // inputs. 1603| | // 1604| | // input LITERAL NON_LITERAL 1605| | // ----------------------------------- 1606| | // html|html4|cp 23% 77% 1607| | // urls 36% 64% 1608| | // jpg 47% 53% 1609| | // pdf 19% 81% 1610| | // txt[1-4] 25% 75% 1611| | // pb 24% 76% 1612| | // bin 24% 76% 1613| 139k| if (SNAPPY_PREDICT_FALSE((c & 0x3) == LITERAL)) { ------------------ | | 94| 139k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 99.3k, False: 39.9k] | | ------------------ ------------------ 1614| 99.3k| size_t literal_length = (c >> 2) + 1u; 1615| 99.3k| if (writer->TryFastAppend(ip, ip_limit_ - ip, literal_length, &op)) { ------------------ | Branch (1615:13): [True: 0, False: 99.3k] ------------------ 1616| 0| assert(literal_length < 61); 1617| 0| ip += literal_length; 1618| | // NOTE: There is no MAYBE_REFILL() here, as TryFastAppend() 1619| | // will not return true unless there's already at least five spare 1620| | // bytes in addition to the literal. 1621| 0| preload = static_cast(*ip); 1622| 0| continue; 1623| 0| } 1624| 99.3k| if (SNAPPY_PREDICT_FALSE(literal_length >= 61)) { ------------------ | | 94| 99.3k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 83.3k, False: 16.0k] | | ------------------ ------------------ 1625| | // Long literal. 1626| 83.3k| const size_t literal_length_length = literal_length - 60; 1627| 83.3k| literal_length = 1628| 83.3k| ExtractLowBytes(LittleEndian::Load32(ip), literal_length_length) + 1629| 83.3k| 1; 1630| 83.3k| ip += literal_length_length; 1631| 83.3k| } 1632| | 1633| 99.3k| size_t avail = ip_limit_ - ip; 1634| 99.3k| while (avail < literal_length) { ------------------ | Branch (1634:16): [True: 0, False: 99.3k] ------------------ 1635| 0| if (!writer->Append(ip, avail, &op)) goto exit; ------------------ | Branch (1635:15): [True: 0, False: 0] ------------------ 1636| 0| literal_length -= avail; 1637| 0| reader_->Skip(peeked_); 1638| 0| size_t n; 1639| 0| ip = reader_->Peek(&n); 1640| 0| avail = n; 1641| 0| peeked_ = avail; 1642| 0| if (avail == 0) goto exit; ------------------ | Branch (1642:15): [True: 0, False: 0] ------------------ 1643| 0| ip_limit_ = ip + avail; 1644| 0| ResetLimit(ip); 1645| 0| } 1646| 99.3k| if (!writer->Append(ip, literal_length, &op)) goto exit; ------------------ | Branch (1646:13): [True: 0, False: 99.3k] ------------------ 1647| 99.3k| ip += literal_length; 1648| 99.3k| MAYBE_REFILL(); ------------------ | | 1572| 99.3k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 99.3k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 4.78k, False: 94.5k] | | | | ------------------ | | ------------------ | | 1573| 4.78k| ip_ = ip; \ | | 1574| 4.78k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 4.78k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 4.55k, False: 230] | | | | ------------------ | | ------------------ | | 1575| 4.78k| ip = ip_; \ | | 1576| 230| ResetLimit(ip); \ | | 1577| 230| } \ | | 1578| 99.3k| preload = static_cast(*ip) ------------------ 1649| 94.8k| } else { 1650| 39.9k| if (SNAPPY_PREDICT_FALSE((c & 3) == COPY_4_BYTE_OFFSET)) { ------------------ | | 94| 39.9k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 0, False: 39.9k] | | ------------------ ------------------ 1651| 0| const size_t copy_offset = LittleEndian::Load32(ip); 1652| 0| const size_t length = (c >> 2) + 1; 1653| 0| ip += 4; 1654| | 1655| 0| if (!writer->AppendFromSelf(copy_offset, length, &op)) goto exit; ------------------ | Branch (1655:15): [True: 0, False: 0] ------------------ 1656| 39.9k| } else { 1657| 39.9k| const ptrdiff_t entry = kLengthMinusOffset[c]; 1658| 39.9k| preload = LittleEndian::Load32(ip); 1659| 39.9k| const uint32_t trailer = ExtractLowBytes(preload, c & 3); 1660| 39.9k| const uint32_t length = entry & 0xff; 1661| 39.9k| assert(length > 0); 1662| | 1663| | // copy_offset/256 is encoded in bits 8..10. By just fetching 1664| | // those bits, we get copy_offset (since the bit-field starts at 1665| | // bit 8). 1666| 39.9k| const uint32_t copy_offset = trailer - entry + length; 1667| 39.9k| if (!writer->AppendFromSelf(copy_offset, length, &op)) goto exit; ------------------ | Branch (1667:15): [True: 0, False: 39.9k] ------------------ 1668| | 1669| 39.9k| ip += (c & 3); 1670| | // By using the result of the previous load we reduce the critical 1671| | // dependency chain of ip to 4 cycles. 1672| 39.9k| preload >>= (c & 3) * 8; 1673| 39.9k| if (ip < ip_limit_min_maxtaglen_) continue; ------------------ | Branch (1673:15): [True: 38.5k, False: 1.40k] ------------------ 1674| 39.9k| } 1675| 2.13k| MAYBE_REFILL(); ------------------ | | 1572| 1.40k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 1.40k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 1.40k, False: 0] | | | | ------------------ | | ------------------ | | 1573| 1.40k| ip_ = ip; \ | | 1574| 1.40k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 1.40k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 681, False: 726] | | | | ------------------ | | ------------------ | | 1575| 1.40k| ip = ip_; \ | | 1576| 726| ResetLimit(ip); \ | | 1577| 726| } \ | | 1578| 1.40k| preload = static_cast(*ip) ------------------ 1676| 2.13k| } 1677| 139k| } 1678| 0|#undef MAYBE_REFILL 1679| 5.23k| exit: 1680| 5.23k| writer->SetOutputPtr(op); 1681| 5.23k| } _ZN6snappy28SnappyDecompressionValidator12GetOutputPtrEv: 2263| 5.23k| size_t GetOutputPtr() { return produced_; } _ZN6snappy28SnappyDecompressionValidator7GetBaseEPl: 2264| 139k| size_t GetBase(ptrdiff_t* op_limit_min_slop) { 2265| 139k| *op_limit_min_slop = std::numeric_limits::max() - kSlopBytes + 1; 2266| 139k| return 1; 2267| 139k| } _ZN6snappy20DecompressBranchlessImEENSt3__14pairIPKhlEES4_S4_lT_l: 1382| 139k| ptrdiff_t op_limit_min_slop) { 1383| | // If deferred_src is invalid point it here. 1384| 139k| uint8_t safe_source[64]; 1385| 139k| const void* deferred_src; 1386| 139k| size_t deferred_length; 1387| 139k| ClearDeferred(&deferred_src, &deferred_length, safe_source); 1388| | 1389| | // We unroll the inner loop twice so we need twice the spare room. 1390| 139k| op_limit_min_slop -= kSlopBytes; 1391| 139k| if (2 * (kSlopBytes + 1) < ip_limit - ip && op < op_limit_min_slop) { ------------------ | Branch (1391:7): [True: 88.5k, False: 50.7k] | Branch (1391:47): [True: 88.5k, False: 0] ------------------ 1392| 88.5k| const uint8_t* const ip_limit_min_slop = ip_limit - 2 * kSlopBytes - 1; 1393| 88.5k| ip++; 1394| | // ip points just past the tag and we are touching at maximum kSlopBytes 1395| | // in an iteration. 1396| 88.5k| size_t tag = ip[-1]; 1397| |#if defined(__clang__) && defined(__aarch64__) 1398| | // Workaround for https://bugs.llvm.org/show_bug.cgi?id=51317 1399| | // when loading 1 byte, clang for aarch64 doesn't realize that it(ldrb) 1400| | // comes with free zero-extension, so clang generates another 1401| | // 'and xn, xm, 0xff' before it use that as the offset. This 'and' is 1402| | // redundant and can be removed by adding this dummy asm, which gives 1403| | // clang a hint that we're doing the zero-extension at the load. 1404| | asm("" ::"r"(tag)); 1405| |#endif 1406| 5.60M| do { 1407| | // The throughput is limited by instructions, unrolling the inner loop 1408| | // twice reduces the amount of instructions checking limits and also 1409| | // leads to reduced mov's. 1410| | 1411| 5.60M| SNAPPY_PREFETCH(ip + 128); ------------------ | | 109| 5.60M|#define SNAPPY_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 3) ------------------ 1412| 16.7M| for (int i = 0; i < 2; i++) { ------------------ | Branch (1412:23): [True: 11.1M, False: 5.51M] ------------------ 1413| 11.1M| const uint8_t* old_ip = ip; 1414| 11.1M| assert(tag == ip[-1]); 1415| | // For literals tag_type = 0, hence we will always obtain 0 from 1416| | // ExtractLowBytes. For literals offset will thus be kLiteralOffset. 1417| 11.1M| ptrdiff_t len_minus_offset = kLengthMinusOffset[tag]; 1418| 11.1M| uint32_t next; 1419| |#if defined(__aarch64__) 1420| | size_t tag_type = AdvanceToNextTagARMOptimized(&ip, &tag); 1421| | // We never need more than 16 bits. Doing a Load16 allows the compiler 1422| | // to elide the masking operation in ExtractOffset. 1423| | next = LittleEndian::Load16(old_ip); 1424| |#else 1425| 11.1M| size_t tag_type = AdvanceToNextTagX86Optimized(&ip, &tag); 1426| 11.1M| next = LittleEndian::Load32(old_ip); 1427| 11.1M|#endif 1428| 11.1M| size_t len = len_minus_offset & 0xFF; 1429| 11.1M| ptrdiff_t extracted = ExtractOffset(next, tag_type); 1430| 11.1M| ptrdiff_t len_min_offset = len_minus_offset - extracted; 1431| 11.1M| if (SNAPPY_PREDICT_FALSE(len_minus_offset > extracted)) { ------------------ | | 94| 11.1M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 1.40M, False: 9.77M] | | ------------------ ------------------ 1432| 1.40M| if (SNAPPY_PREDICT_FALSE(len & 0x80)) { ------------------ | | 94| 1.40M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 82.6k, False: 1.32M] | | ------------------ ------------------ 1433| | // Exceptional case (long literal or copy 4). 1434| | // Actually doing the copy here is negatively impacting the main 1435| | // loop due to compiler incorrectly allocating a register for 1436| | // this fallback. Hence we just break. 1437| 87.2k| break_loop: 1438| 87.2k| ip = old_ip; 1439| 87.2k| goto exit; 1440| 82.6k| } 1441| | // Only copy-1 or copy-2 tags can get here. 1442| 1.32M| assert(tag_type == 1 || tag_type == 2); 1443| 1.32M| std::ptrdiff_t delta = (op + deferred_length) + len_min_offset - len; 1444| | // Guard against copies before the buffer start. 1445| | // Execute any deferred MemCopy since we write to dst here. 1446| 1.32M| MemCopy64(op_base + op, deferred_src, deferred_length); 1447| 1.32M| op += deferred_length; 1448| 1.32M| ClearDeferred(&deferred_src, &deferred_length, safe_source); 1449| 1.32M| if (SNAPPY_PREDICT_FALSE(delta < 0 || ------------------ | | 94| 2.64M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 504, False: 1.32M] | | | Branch (94:51): [True: 504, False: 1.32M] | | | Branch (94:51): [True: 0, False: 1.32M] | | ------------------ ------------------ 1450| 1.32M| !Copy64BytesWithPatternExtension( 1451| 1.32M| op_base + op, len - len_min_offset))) { 1452| 504| goto break_loop; 1453| 504| } 1454| | // We aren't deferring this copy so add length right away. 1455| 1.32M| op += len; 1456| 1.32M| continue; 1457| 1.32M| } 1458| 9.77M| std::ptrdiff_t delta = (op + deferred_length) + len_min_offset - len; 1459| 9.77M| if (SNAPPY_PREDICT_FALSE(delta < 0)) { ------------------ | | 94| 9.77M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 17.6k, False: 9.76M] | | ------------------ ------------------ 1460| | // Due to the spurious offset in literals have this will trigger 1461| | // at the start of a block when op is still smaller than 256. 1462| 17.6k| if (tag_type != 0) goto break_loop; ------------------ | Branch (1462:15): [True: 4.12k, False: 13.5k] ------------------ 1463| 13.5k| MemCopy64(op_base + op, deferred_src, deferred_length); 1464| 13.5k| op += deferred_length; 1465| 13.5k| DeferMemCopy(&deferred_src, &deferred_length, old_ip, len); 1466| 13.5k| continue; 1467| 17.6k| } 1468| | 1469| | // For copies we need to copy from op_base + delta, for literals 1470| | // we need to copy from ip instead of from the stream. 1471| 9.76M| const void* from = 1472| 9.76M| tag_type ? reinterpret_cast(op_base + delta) : old_ip; ------------------ | Branch (1472:13): [True: 7.32M, False: 2.44M] ------------------ 1473| 9.76M| MemCopy64(op_base + op, deferred_src, deferred_length); 1474| 9.76M| op += deferred_length; 1475| 9.76M| DeferMemCopy(&deferred_src, &deferred_length, from, len); 1476| 9.76M| } 1477| 5.60M| } while (ip < ip_limit_min_slop && ------------------ | Branch (1477:14): [True: 5.51M, False: 1.31k] ------------------ 1478| 5.51M| static_cast(op + deferred_length) < op_limit_min_slop); ------------------ | Branch (1478:14): [True: 5.51M, False: 0] ------------------ 1479| 88.5k| exit: 1480| 88.5k| ip--; 1481| 88.5k| assert(ip <= ip_limit); 1482| 88.5k| } 1483| | // If we deferred a copy then we can perform. If we are up to date then we 1484| | // might not have enough slop bytes and could run past the end. 1485| 139k| if (deferred_length) { ------------------ | Branch (1485:7): [True: 74.4k, False: 64.8k] ------------------ 1486| 74.4k| MemCopy64(op_base + op, deferred_src, deferred_length); 1487| 74.4k| op += deferred_length; 1488| 74.4k| ClearDeferred(&deferred_src, &deferred_length, safe_source); 1489| 74.4k| } 1490| 139k| return {ip, op}; 1491| 139k|} _ZN6snappy31Copy64BytesWithPatternExtensionElm: 1217| 1.32M|inline bool Copy64BytesWithPatternExtension(ptrdiff_t dst, size_t offset) { 1218| | // TODO: Switch to [[maybe_unused]] when we can assume C++17. 1219| 1.32M| (void)dst; 1220| 1.32M| return offset != 0; 1221| 1.32M|} _ZN6snappy28SnappyDecompressionValidator13TryFastAppendEPKcmmPm: 2278| 99.3k| size_t* produced) { 2279| | // TODO: Switch to [[maybe_unused]] when we can assume C++17. 2280| 99.3k| (void)ip; 2281| 99.3k| (void)available; 2282| 99.3k| (void)length; 2283| 99.3k| (void)produced; 2284| | 2285| 99.3k| return false; 2286| 99.3k| } _ZN6snappy28SnappyDecompressionValidator6AppendEPKcmPm: 2270| 99.3k| inline bool Append(const char* ip, size_t len, size_t* produced) { 2271| | // TODO: Switch to [[maybe_unused]] when we can assume C++17. 2272| 99.3k| (void)ip; 2273| | 2274| 99.3k| *produced += len; 2275| 99.3k| return *produced <= expected_; 2276| 99.3k| } _ZN6snappy28SnappyDecompressionValidator14AppendFromSelfEmmPm: 2287| 39.9k| inline bool AppendFromSelf(size_t offset, size_t len, size_t* produced) { 2288| | // See SnappyArrayWriter::AppendFromSelf for an explanation of 2289| | // the "offset - 1u" trick. 2290| 39.9k| if (*produced <= offset - 1u) return false; ------------------ | Branch (2290:9): [True: 0, False: 39.9k] ------------------ 2291| 39.9k| *produced += len; 2292| 39.9k| return *produced <= expected_; 2293| 39.9k| } _ZN6snappy28SnappyDecompressionValidator12SetOutputPtrEm: 2268| 5.23k| void SetOutputPtr(size_t op) { produced_ = op; } _ZN6snappy28SnappyDecompressionValidator5FlushEv: 2294| 5.23k| inline void Flush() {} _ZNK6snappy28SnappyDecompressionValidator11CheckLengthEv: 2269| 5.23k| inline bool CheckLength() const { return expected_ == produced_; } snappy.cc:_ZN6snappyL25InternalUncompressAllTagsINS_17SnappyArrayWriterEEEbPNS_18SnappyDecompressorEPT_jj: 1780| 5.23k| uint32_t uncompressed_len) { 1781| 5.23k| int token = 0; 1782| 5.23k| Report(token, "snappy_uncompress", compressed_len, uncompressed_len); 1783| | 1784| 5.23k| writer->SetExpectedLength(uncompressed_len); 1785| | 1786| | // Process the entire input 1787| 5.23k| decompressor->DecompressAllTags(writer); 1788| 5.23k| writer->Flush(); 1789| 5.23k| return (decompressor->eof() && writer->CheckLength()); ------------------ | Branch (1789:11): [True: 5.23k, False: 0] | Branch (1789:34): [True: 5.23k, False: 0] ------------------ 1790| 5.23k|} _ZN6snappy17SnappyArrayWriter17SetExpectedLengthEm: 2161| 5.23k| inline void SetExpectedLength(size_t len) { 2162| 5.23k| op_limit_ = op_ + len; 2163| | // Prevent pointer from being past the buffer. 2164| 5.23k| op_limit_min_slop_ = op_limit_ - std::min(kSlopBytes - 1, len); 2165| 5.23k| } _ZN6snappy18SnappyDecompressor17DecompressAllTagsINS_17SnappyArrayWriterEEEvPT_: 1563| 5.23k| DecompressAllTags(Writer* writer) { 1564| 5.23k| const char* ip = ip_; 1565| 5.23k| ResetLimit(ip); 1566| 5.23k| auto op = writer->GetOutputPtr(); 1567| | // We could have put this refill fragment only at the beginning of the loop. 1568| | // However, duplicating it at the end of each branch gives the compiler more 1569| | // scope to optimize the expression based on the local 1570| | // context, which overall increases speed. 1571| 5.23k|#define MAYBE_REFILL() \ 1572| 5.23k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ 1573| 5.23k| ip_ = ip; \ 1574| 5.23k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ 1575| 5.23k| ip = ip_; \ 1576| 5.23k| ResetLimit(ip); \ 1577| 5.23k| } \ 1578| 5.23k| preload = static_cast(*ip) 1579| | 1580| | // At the start of the for loop below the least significant byte of preload 1581| | // contains the tag. 1582| 5.23k| uint32_t preload; 1583| 5.23k| MAYBE_REFILL(); ------------------ | | 1572| 5.23k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 5.23k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 5.23k, False: 0] | | | | ------------------ | | ------------------ | | 1573| 5.23k| ip_ = ip; \ | | 1574| 5.23k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 5.23k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 0, False: 5.23k] | | | | ------------------ | | ------------------ | | 1575| 5.23k| ip = ip_; \ | | 1576| 5.23k| ResetLimit(ip); \ | | 1577| 5.23k| } \ | | 1578| 5.23k| preload = static_cast(*ip) ------------------ 1584| 134k| for (;;) { 1585| 134k| { 1586| 134k| ptrdiff_t op_limit_min_slop; 1587| 134k| auto op_base = writer->GetBase(&op_limit_min_slop); 1588| 134k| if (op_base) { ------------------ | Branch (1588:13): [True: 134k, False: 0] ------------------ 1589| 134k| auto res = 1590| 134k| DecompressBranchless(reinterpret_cast(ip), 1591| 134k| reinterpret_cast(ip_limit_), 1592| 134k| op - op_base, op_base, op_limit_min_slop); 1593| 134k| ip = reinterpret_cast(res.first); 1594| 134k| op = op_base + res.second; 1595| 134k| MAYBE_REFILL(); ------------------ | | 1572| 134k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 134k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 962, False: 133k] | | | | ------------------ | | ------------------ | | 1573| 962| ip_ = ip; \ | | 1574| 962| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 962|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 0, False: 962] | | | | ------------------ | | ------------------ | | 1575| 962| ip = ip_; \ | | 1576| 962| ResetLimit(ip); \ | | 1577| 962| } \ | | 1578| 134k| preload = static_cast(*ip) ------------------ 1596| 134k| } 1597| 134k| } 1598| 134k| const uint8_t c = static_cast(preload); 1599| 134k| ip++; 1600| | 1601| | // Ratio of iterations that have LITERAL vs non-LITERAL for different 1602| | // inputs. 1603| | // 1604| | // input LITERAL NON_LITERAL 1605| | // ----------------------------------- 1606| | // html|html4|cp 23% 77% 1607| | // urls 36% 64% 1608| | // jpg 47% 53% 1609| | // pdf 19% 81% 1610| | // txt[1-4] 25% 75% 1611| | // pb 24% 76% 1612| | // bin 24% 76% 1613| 134k| if (SNAPPY_PREDICT_FALSE((c & 0x3) == LITERAL)) { ------------------ | | 94| 134k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 99.3k, False: 35.2k] | | ------------------ ------------------ 1614| 99.3k| size_t literal_length = (c >> 2) + 1u; 1615| 99.3k| if (writer->TryFastAppend(ip, ip_limit_ - ip, literal_length, &op)) { ------------------ | Branch (1615:13): [True: 8.46k, False: 90.8k] ------------------ 1616| 8.46k| assert(literal_length < 61); 1617| 8.46k| ip += literal_length; 1618| | // NOTE: There is no MAYBE_REFILL() here, as TryFastAppend() 1619| | // will not return true unless there's already at least five spare 1620| | // bytes in addition to the literal. 1621| 8.46k| preload = static_cast(*ip); 1622| 8.46k| continue; 1623| 8.46k| } 1624| 90.8k| if (SNAPPY_PREDICT_FALSE(literal_length >= 61)) { ------------------ | | 94| 90.8k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 83.3k, False: 7.54k] | | ------------------ ------------------ 1625| | // Long literal. 1626| 83.3k| const size_t literal_length_length = literal_length - 60; 1627| 83.3k| literal_length = 1628| 83.3k| ExtractLowBytes(LittleEndian::Load32(ip), literal_length_length) + 1629| 83.3k| 1; 1630| 83.3k| ip += literal_length_length; 1631| 83.3k| } 1632| | 1633| 90.8k| size_t avail = ip_limit_ - ip; 1634| 90.8k| while (avail < literal_length) { ------------------ | Branch (1634:16): [True: 0, False: 90.8k] ------------------ 1635| 0| if (!writer->Append(ip, avail, &op)) goto exit; ------------------ | Branch (1635:15): [True: 0, False: 0] ------------------ 1636| 0| literal_length -= avail; 1637| 0| reader_->Skip(peeked_); 1638| 0| size_t n; 1639| 0| ip = reader_->Peek(&n); 1640| 0| avail = n; 1641| 0| peeked_ = avail; 1642| 0| if (avail == 0) goto exit; ------------------ | Branch (1642:15): [True: 0, False: 0] ------------------ 1643| 0| ip_limit_ = ip + avail; 1644| 0| ResetLimit(ip); 1645| 0| } 1646| 90.8k| if (!writer->Append(ip, literal_length, &op)) goto exit; ------------------ | Branch (1646:13): [True: 0, False: 90.8k] ------------------ 1647| 90.8k| ip += literal_length; 1648| 90.8k| MAYBE_REFILL(); ------------------ | | 1572| 90.8k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 90.8k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 4.78k, False: 86.0k] | | | | ------------------ | | ------------------ | | 1573| 4.78k| ip_ = ip; \ | | 1574| 4.78k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 4.78k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 4.55k, False: 230] | | | | ------------------ | | ------------------ | | 1575| 4.78k| ip = ip_; \ | | 1576| 230| ResetLimit(ip); \ | | 1577| 230| } \ | | 1578| 90.8k| preload = static_cast(*ip) ------------------ 1649| 86.2k| } else { 1650| 35.2k| if (SNAPPY_PREDICT_FALSE((c & 3) == COPY_4_BYTE_OFFSET)) { ------------------ | | 94| 35.2k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 0, False: 35.2k] | | ------------------ ------------------ 1651| 0| const size_t copy_offset = LittleEndian::Load32(ip); 1652| 0| const size_t length = (c >> 2) + 1; 1653| 0| ip += 4; 1654| | 1655| 0| if (!writer->AppendFromSelf(copy_offset, length, &op)) goto exit; ------------------ | Branch (1655:15): [True: 0, False: 0] ------------------ 1656| 35.2k| } else { 1657| 35.2k| const ptrdiff_t entry = kLengthMinusOffset[c]; 1658| 35.2k| preload = LittleEndian::Load32(ip); 1659| 35.2k| const uint32_t trailer = ExtractLowBytes(preload, c & 3); 1660| 35.2k| const uint32_t length = entry & 0xff; 1661| 35.2k| assert(length > 0); 1662| | 1663| | // copy_offset/256 is encoded in bits 8..10. By just fetching 1664| | // those bits, we get copy_offset (since the bit-field starts at 1665| | // bit 8). 1666| 35.2k| const uint32_t copy_offset = trailer - entry + length; 1667| 35.2k| if (!writer->AppendFromSelf(copy_offset, length, &op)) goto exit; ------------------ | Branch (1667:15): [True: 0, False: 35.2k] ------------------ 1668| | 1669| 35.2k| ip += (c & 3); 1670| | // By using the result of the previous load we reduce the critical 1671| | // dependency chain of ip to 4 cycles. 1672| 35.2k| preload >>= (c & 3) * 8; 1673| 35.2k| if (ip < ip_limit_min_maxtaglen_) continue; ------------------ | Branch (1673:15): [True: 33.8k, False: 1.40k] ------------------ 1674| 35.2k| } 1675| 2.13k| MAYBE_REFILL(); ------------------ | | 1572| 1.40k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 1.40k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 1.40k, False: 0] | | | | ------------------ | | ------------------ | | 1573| 1.40k| ip_ = ip; \ | | 1574| 1.40k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 1.40k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 681, False: 726] | | | | ------------------ | | ------------------ | | 1575| 1.40k| ip = ip_; \ | | 1576| 726| ResetLimit(ip); \ | | 1577| 726| } \ | | 1578| 1.40k| preload = static_cast(*ip) ------------------ 1676| 2.13k| } 1677| 134k| } 1678| 0|#undef MAYBE_REFILL 1679| 5.23k| exit: 1680| 5.23k| writer->SetOutputPtr(op); 1681| 5.23k| } _ZN6snappy17SnappyArrayWriter12GetOutputPtrEv: 2169| 5.23k| char* GetOutputPtr() { return op_; } _ZN6snappy17SnappyArrayWriter7GetBaseEPl: 2170| 134k| char* GetBase(ptrdiff_t* op_limit_min_slop) { 2171| 134k| *op_limit_min_slop = op_limit_min_slop_ - base_; 2172| 134k| return base_; 2173| 134k| } _ZN6snappy17SnappyArrayWriter13TryFastAppendEPKcmmPPc: 2186| 99.3k| char** op_p) { 2187| 99.3k| char* op = *op_p; 2188| 99.3k| const size_t space_left = op_limit_ - op; 2189| 99.3k| if (len <= 16 && available >= 16 + kMaximumTagLength && space_left >= 16) { ------------------ | Branch (2189:9): [True: 14.6k, False: 84.6k] | Branch (2189:22): [True: 8.46k, False: 6.15k] | Branch (2189:61): [True: 8.46k, False: 0] ------------------ 2190| | // Fast path, used for the majority (about 95%) of invocations. 2191| 8.46k| UnalignedCopy128(ip, op); 2192| 8.46k| *op_p = op + len; 2193| 8.46k| return true; 2194| 90.8k| } else { 2195| 90.8k| return false; 2196| 90.8k| } 2197| 99.3k| } _ZN6snappy17SnappyArrayWriter6AppendEPKcmPPc: 2176| 90.8k| inline bool Append(const char* ip, size_t len, char** op_p) { 2177| 90.8k| char* op = *op_p; 2178| 90.8k| const size_t space_left = op_limit_ - op; 2179| 90.8k| if (space_left < len) return false; ------------------ | Branch (2179:9): [True: 0, False: 90.8k] ------------------ 2180| 90.8k| std::memcpy(op, ip, len); 2181| 90.8k| *op_p = op + len; 2182| 90.8k| return true; 2183| 90.8k| } _ZN6snappy17SnappyArrayWriter14AppendFromSelfEmmPPc: 2200| 35.2k| inline bool AppendFromSelf(size_t offset, size_t len, char** op_p) { 2201| 35.2k| assert(len > 0); 2202| 35.2k| char* const op = *op_p; 2203| 35.2k| assert(op >= base_); 2204| 35.2k| char* const op_end = op + len; 2205| | 2206| | // Check if we try to append from before the start of the buffer. 2207| 35.2k| if (SNAPPY_PREDICT_FALSE(static_cast(op - base_) < offset)) ------------------ | | 94| 35.2k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 0, False: 35.2k] | | ------------------ ------------------ 2208| 0| return false; 2209| | 2210| 35.2k| if (SNAPPY_PREDICT_FALSE((kSlopBytes < 64 && len > kSlopBytes) || ------------------ | | 94| 168k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 18.6k, False: 16.6k] | | | Branch (94:51): [Folded - Ignored] | | | Branch (94:51): [True: 0, False: 0] | | | Branch (94:51): [True: 7.94k, False: 27.3k] | | | Branch (94:51): [True: 10.7k, False: 16.6k] | | ------------------ ------------------ 2211| 35.2k| op >= op_limit_min_slop_ || offset < len)) { 2212| 18.6k| if (op_end > op_limit_ || offset == 0) return false; ------------------ | Branch (2212:11): [True: 0, False: 18.6k] | Branch (2212:33): [True: 0, False: 18.6k] ------------------ 2213| 18.6k| *op_p = IncrementalCopy(op - offset, op, op_end, op_limit_); 2214| 18.6k| return true; 2215| 18.6k| } 2216| 16.6k| std::memmove(op, op - offset, kSlopBytes); 2217| 16.6k| *op_p = op_end; 2218| 16.6k| return true; 2219| 35.2k| } _ZN6snappy17SnappyArrayWriter12SetOutputPtrEPc: 2174| 5.23k| void SetOutputPtr(char* op) { op_ = op; } _ZN6snappy17SnappyArrayWriter5FlushEv: 2224| 5.23k| inline void Flush() {} _ZNK6snappy17SnappyArrayWriter11CheckLengthEv: 2167| 5.23k| inline bool CheckLength() const { return op_ == op_limit_; } _ZN6snappy18CompressionOptions19MinCompressionLevelEv: 70| 2.61k| static constexpr int MinCompressionLevel() { return 1; } _ZN6snappy18CompressionOptions19MaxCompressionLevelEv: 71| 7.85k| static constexpr int MaxCompressionLevel() { return 2; } _ZN6snappy18CompressionOptionsC2Ei: 69| 5.23k| : level(compression_level) {} LLVMFuzzerTestOneInput: 40| 2.61k|extern "C" int LLVMFuzzerTestOneInput(const uint8_t* data, size_t size) { 41| 2.61k| std::string input(reinterpret_cast(data), size); 42| 2.61k| for (int level = snappy::CompressionOptions::MinCompressionLevel(); 43| 7.85k| level <= snappy::CompressionOptions::MaxCompressionLevel(); ++level) { ------------------ | Branch (43:8): [True: 5.23k, False: 2.61k] ------------------ 44| 5.23k| std::string compressed; 45| 5.23k| size_t compressed_size = 46| 5.23k| snappy::Compress(input.data(), input.size(), &compressed, 47| 5.23k| snappy::CompressionOptions{/*level=*/level}); 48| | 49| 5.23k| (void)compressed_size; // Variable only used in debug builds. 50| 5.23k| assert(compressed_size == compressed.size()); 51| 5.23k| assert(compressed.size() <= snappy::MaxCompressedLength(input.size())); 52| 5.23k| assert( 53| 5.23k| snappy::IsValidCompressedBuffer(compressed.data(), compressed.size())); 54| | 55| 5.23k| std::string uncompressed_after_compress; 56| 5.23k| bool uncompress_succeeded = snappy::Uncompress( 57| 5.23k| compressed.data(), compressed.size(), &uncompressed_after_compress); 58| | 59| 5.23k| (void)uncompress_succeeded; // Variable only used in debug builds. 60| 5.23k| assert(uncompress_succeeded); 61| 5.23k| assert(input == uncompressed_after_compress); 62| 5.23k| } 63| 2.61k| return 0; 64| 2.61k|}