snappy.cc:_ZN6snappy8internalL15FindMatchLengthEPKcS2_S2_Pm: 181| 1.80M| uint64_t* data) { 182| 1.80M| assert(s2_limit >= s2); 183| 0| 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| 1.80M| if (SNAPPY_PREDICT_TRUE(s2 <= s2_limit - 16)) { ------------------ | | 95| 1.80M|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 1.80M, False: 563] | | ------------------ ------------------ 191| 1.80M| uint64_t a1 = UNALIGNED_LOAD64(s1); 192| 1.80M| uint64_t a2 = UNALIGNED_LOAD64(s2); 193| 1.80M| if (SNAPPY_PREDICT_TRUE(a1 != a2)) { ------------------ | | 95| 1.80M|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 1.06M, False: 740k] | | ------------------ ------------------ 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| 1.06M| uint64_t xorval = a1 ^ a2; 233| 1.06M| int shift = Bits::FindLSBSetNonZero64(xorval); 234| 1.06M| size_t matched_bytes = shift >> 3; 235| 1.06M| 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| 1.06M| asm("testl %k2, %k2\n\t" 249| 1.06M| "cmovzq %1, %0\n\t" 250| 1.06M| : "+r"(a2) 251| 1.06M| : "r"(a3), "r"(xorval) 252| 1.06M| : "cc"); 253| 1.06M|#endif 254| 1.06M| *data = a2 >> (shift & (3 * 8)); 255| 1.06M| return std::pair(matched_bytes, true); 256| 1.06M| } else { 257| 740k| matched = 8; 258| 740k| s2 += 8; 259| 740k| } 260| 1.80M| } 261| 741k| SNAPPY_PREFETCH(s1 + 64); ------------------ | | 109| 741k|#define SNAPPY_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 3) ------------------ 262| 741k| SNAPPY_PREFETCH(s2 + 64); ------------------ | | 109| 741k|#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| 7.68M| while (SNAPPY_PREDICT_TRUE(s2 <= s2_limit - 16)) { ------------------ | | 95| 7.68M|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 7.68M, False: 1.71k] | | ------------------ ------------------ 269| 7.68M| uint64_t a1 = UNALIGNED_LOAD64(s1 + matched); 270| 7.68M| uint64_t a2 = UNALIGNED_LOAD64(s2); 271| 7.68M| if (a1 == a2) { ------------------ | Branch (271:9): [True: 6.94M, False: 739k] ------------------ 272| 6.94M| s2 += 8; 273| 6.94M| matched += 8; 274| 6.94M| } else { 275| 739k| uint64_t xorval = a1 ^ a2; 276| 739k| int shift = Bits::FindLSBSetNonZero64(xorval); 277| 739k| size_t matched_bytes = shift >> 3; 278| 739k| uint64_t a3 = UNALIGNED_LOAD64(s2 + 4); 279| |#ifndef __x86_64__ 280| | a2 = static_cast(xorval) == 0 ? a3 : a2; 281| |#else 282| 739k| asm("testl %k2, %k2\n\t" 283| 739k| "cmovzq %1, %0\n\t" 284| 739k| : "+r"(a2) 285| 739k| : "r"(a3), "r"(xorval) 286| 739k| : "cc"); 287| 739k|#endif 288| 739k| *data = a2 >> (shift & (3 * 8)); 289| 739k| matched += matched_bytes; 290| 739k| assert(matched >= 8); 291| 0| return std::pair(matched, false); 292| 739k| } 293| 7.68M| } 294| 15.9k| while (SNAPPY_PREDICT_TRUE(s2 < s2_limit)) { ------------------ | | 95| 15.9k|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 14.9k, False: 1.00k] | | ------------------ ------------------ 295| 14.9k| if (s1[matched] == *s2) { ------------------ | Branch (295:9): [True: 14.2k, False: 705] ------------------ 296| 14.2k| ++s2; 297| 14.2k| ++matched; 298| 14.2k| } else { 299| 705| if (s2 <= s2_limit - 8) { ------------------ | Branch (299:11): [True: 422, False: 283] ------------------ 300| 422| *data = UNALIGNED_LOAD64(s2); 301| 422| } 302| 705| return std::pair(matched, matched < 8); 303| 705| } 304| 14.9k| } 305| 1.00k| return std::pair(matched, matched < 8); 306| 1.71k|} _ZNK6snappy8internal13WorkingMemory16GetScratchOutputEv: 128| 3.72k| char* GetScratchOutput() const { return output_; } _ZN6snappy6SourceD2Ev: 36| 5.74k|Source::~Source() = default; _ZN6snappy4SinkD2Ev: 38| 1.91k|Sink::~Sink() = default; _ZNK6snappy15ByteArraySource9AvailableEv: 68| 5.74k|size_t ByteArraySource::Available() const { return left_; } _ZN6snappy15ByteArraySource4PeekEPm: 70| 18.5k|const char* ByteArraySource::Peek(size_t* len) { 71| 18.5k| *len = left_; 72| 18.5k| return ptr_; 73| 18.5k|} _ZN6snappy15ByteArraySource4SkipEm: 75| 23.9k|void ByteArraySource::Skip(size_t n) { 76| 23.9k| left_ -= n; 77| 23.9k| ptr_ += n; 78| 23.9k|} _ZN6snappy22UncheckedByteArraySink6AppendEPKcm: 82| 5.64k|void UncheckedByteArraySink::Append(const char* data, size_t n) { 83| | // Do no copying if the caller filled in the result of GetAppendBuffer() 84| 5.64k| if (data != dest_) { ------------------ | Branch (84:7): [True: 1.91k, False: 3.72k] ------------------ 85| 1.91k| std::memcpy(dest_, data, n); 86| 1.91k| } 87| 5.64k| dest_ += n; 88| 5.64k|} _ZN6snappy22UncheckedByteArraySink15GetAppendBufferEmPc: 90| 3.72k|char* UncheckedByteArraySink::GetAppendBuffer(size_t len, char* scratch) { 91| | // TODO: Switch to [[maybe_unused]] when we can assume C++17. 92| 3.72k| (void)len; 93| 3.72k| (void)scratch; 94| | 95| 3.72k| return dest_; 96| 3.72k|} _ZN6snappy15ByteArraySourceC2EPKcm: 148| 5.74k| ByteArraySource(const char* p, size_t n) : ptr_(p), left_(n) { } _ZN6snappy6SourceC2Ev: 113| 5.74k| Source() { } _ZN6snappy22UncheckedByteArraySinkC2EPc: 161| 1.91k| explicit UncheckedByteArraySink(char* dest) : dest_(dest) { } _ZN6snappy4SinkC2Ev: 39| 1.91k| Sink() { } _ZNK6snappy22UncheckedByteArraySink18CurrentDestinationEv: 175| 1.91k| char* CurrentDestination() const { return dest_; } _ZN6snappy6Varint16Parse32WithLimitEPKcS2_Pj: 457| 1.91k| uint32_t* OUTPUT) { 458| 1.91k| const unsigned char* ptr = reinterpret_cast(p); 459| 1.91k| const unsigned char* limit = reinterpret_cast(l); 460| 1.91k| uint32_t b, result; 461| 1.91k| if (ptr >= limit) return NULL; ------------------ | Branch (461:7): [True: 0, False: 1.91k] ------------------ 462| 1.91k| b = *(ptr++); result = b & 127; if (b < 128) goto done; ------------------ | Branch (462:48): [True: 680, False: 1.23k] ------------------ 463| 1.23k| if (ptr >= limit) return NULL; ------------------ | Branch (463:7): [True: 0, False: 1.23k] ------------------ 464| 1.23k| b = *(ptr++); result |= (b & 127) << 7; if (b < 128) goto done; ------------------ | Branch (464:48): [True: 796, False: 440] ------------------ 465| 440| if (ptr >= limit) return NULL; ------------------ | Branch (465:7): [True: 0, False: 440] ------------------ 466| 440| b = *(ptr++); result |= (b & 127) << 14; if (b < 128) goto done; ------------------ | Branch (466:48): [True: 440, 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| 1.91k| done: 473| 1.91k| *OUTPUT = result; 474| 1.91k| return reinterpret_cast(ptr); 475| 0|} _ZN6snappy4Bits9Log2FloorEj: 320| 27.7k|inline int Bits::Log2Floor(uint32_t n) { 321| 27.7k| return (n == 0) ? -1 : Bits::Log2FloorNonZero(n); ------------------ | Branch (321:10): [True: 0, False: 27.7k] ------------------ 322| 27.7k|} _ZN6snappy4Bits16Log2FloorNonZeroEj: 309| 27.7k|inline int Bits::Log2FloorNonZero(uint32_t n) { 310| 27.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| 0| return 31 ^ __builtin_clz(n); 318| 27.7k|} _ZN6snappy12LittleEndian6Load32EPKv: 196| 23.9M| 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| 23.9M| uint32_t value; 207| 23.9M| std::memcpy(&value, ptr, 4); 208| 23.9M| return value; 209| 23.9M|#endif 210| 23.9M| } _ZN6snappy12LittleEndian6Load64EPKv: 212| 3.14M| 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| 3.14M| uint64_t value; 227| 3.14M| std::memcpy(&value, ptr, 8); 228| 3.14M| return value; 229| 3.14M|#endif 230| 3.14M| } _ZN6snappy16UNALIGNED_LOAD64EPKv: 145| 20.7M|inline uint64_t UNALIGNED_LOAD64(const void *p) { 146| | // Compiles to a single mov/ldr on clang/gcc/msvc. 147| 20.7M| uint64_t v; 148| 20.7M| std::memcpy(&v, p, sizeof(v)); 149| 20.7M| return v; 150| 20.7M|} _ZN6snappy4Bits19FindLSBSetNonZero64Em: 398| 1.80M|inline int Bits::FindLSBSetNonZero64(uint64_t n) { 399| 1.80M| assert(n != 0); 400| 0| return __builtin_ctzll(n); 401| 1.80M|} _ZN6snappy6Varint8Encode32EPcj: 477| 1.91k|inline char* Varint::Encode32(char* sptr, uint32_t v) { 478| | // Operate on characters as unsigneds 479| 1.91k| uint8_t* ptr = reinterpret_cast(sptr); 480| 1.91k| static const uint8_t B = 128; 481| 1.91k| if (v < (1 << 7)) { ------------------ | Branch (481:7): [True: 680, False: 1.23k] ------------------ 482| 680| *(ptr++) = static_cast(v); 483| 1.23k| } else if (v < (1 << 14)) { ------------------ | Branch (483:14): [True: 796, False: 440] ------------------ 484| 796| *(ptr++) = static_cast(v | B); 485| 796| *(ptr++) = static_cast(v >> 7); 486| 796| } else if (v < (1 << 21)) { ------------------ | Branch (486:14): [True: 440, False: 0] ------------------ 487| 440| *(ptr++) = static_cast(v | B); 488| 440| *(ptr++) = static_cast((v >> 7) | B); 489| 440| *(ptr++) = static_cast(v >> 14); 490| 440| } 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| 1.91k| return reinterpret_cast(ptr); 503| 1.91k|} _ZN6snappy28STLStringResizeUninitializedEPNSt3__112basic_stringIcNS0_11char_traitsIcEENS0_9allocatorIcEEEEm: 509| 3.83k|inline void STLStringResizeUninitialized(std::string* s, size_t new_size) { 510| 3.83k| s->resize(new_size); 511| 3.83k|} _ZN6snappy15string_as_arrayEPNSt3__112basic_stringIcNS0_11char_traitsIcEENS0_9allocatorIcEEEE: 525| 3.83k|inline char* string_as_array(std::string* str) { 526| 3.83k| return str->empty() ? NULL : &*str->begin(); ------------------ | Branch (526:10): [True: 0, False: 3.83k] ------------------ 527| 3.83k|} _ZN6snappy12LittleEndian7Store32EPvj: 244| 2.54M| 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| 2.54M| std::memcpy(dst, &value, 4); 255| 2.54M|#endif 256| 2.54M| } _ZN6snappy19MaxCompressedLengthEm: 179| 9.47k|size_t MaxCompressedLength(size_t source_bytes) { 180| | // Compressed data can be defined as: 181| | // compressed := item* literal* 182| | // item := literal* copy 183| | // 184| | // The trailing literal sequence has a space blowup of at most 62/60 185| | // since a literal of length 60 needs one tag byte + one extra byte 186| | // for length information. 187| | // 188| | // Item blowup is trickier to measure. Suppose the "copy" op copies 189| | // 4 bytes of data. Because of a special check in the encoding code, 190| | // we produce a 4-byte copy only if the offset is < 65536. Therefore 191| | // the copy op takes 3 bytes to encode, and this type of item leads 192| | // to at most the 62/60 blowup for representing literals. 193| | // 194| | // Suppose the "copy" op copies 5 bytes of data. If the offset is big 195| | // enough, it will take 5 bytes to encode the copy op. Therefore the 196| | // worst case here is a one-byte literal followed by a five-byte copy. 197| | // I.e., 6 bytes of input turn into 7 bytes of "compressed" data. 198| | // 199| | // This last factor dominates the blowup, so the final estimate is: 200| 9.47k| return 32 + source_bytes + source_bytes / 6; 201| 9.47k|} _ZN6snappy21GetUncompressedLengthEPKcmPm: 708| 1.91k|bool GetUncompressedLength(const char* start, size_t n, size_t* result) { 709| 1.91k| uint32_t v = 0; 710| 1.91k| const char* limit = start + n; 711| 1.91k| if (Varint::Parse32WithLimit(start, limit, &v) != NULL) { ------------------ | Branch (711:7): [True: 1.91k, False: 0] ------------------ 712| 1.91k| *result = v; 713| 1.91k| return true; 714| 1.91k| } else { 715| 0| return false; 716| 0| } 717| 1.91k|} _ZN6snappy8internal13WorkingMemoryC2Em: 737| 1.91k|WorkingMemory::WorkingMemory(size_t input_size) { 738| 1.91k| const size_t max_fragment_size = std::min(input_size, kBlockSize); 739| 1.91k| const size_t table_size = CalculateTableSize(max_fragment_size); 740| 1.91k| size_ = table_size * sizeof(*table_) + max_fragment_size + 741| 1.91k| MaxCompressedLength(max_fragment_size); 742| 1.91k| mem_ = std::allocator().allocate(size_); 743| 1.91k| table_ = reinterpret_cast(mem_); 744| 1.91k| input_ = mem_ + table_size * sizeof(*table_); 745| 1.91k| output_ = input_ + max_fragment_size; 746| 1.91k|} _ZN6snappy8internal13WorkingMemoryD2Ev: 748| 1.91k|WorkingMemory::~WorkingMemory() { 749| 1.91k| std::allocator().deallocate(mem_, size_); 750| 1.91k|} _ZNK6snappy8internal13WorkingMemory12GetHashTableEmPi: 753| 3.72k| int* table_size) const { 754| 3.72k| const size_t htsize = CalculateTableSize(fragment_size); 755| 3.72k| memset(table_, 0, htsize * sizeof(*table_)); 756| 3.72k| *table_size = htsize; 757| 3.72k| return table_; 758| 3.72k|} _ZN6snappy8internal16CompressFragmentEPKcmPcPti: 774| 3.72k| uint16_t* table, const int table_size) { 775| | // "ip" is the input pointer, and "op" is the output pointer. 776| 3.72k| const char* ip = input; 777| 3.72k| assert(input_size <= kBlockSize); 778| 0| assert((table_size & (table_size - 1)) == 0); // table must be power of two 779| 0| const uint32_t mask = 2 * (table_size - 1); 780| 3.72k| const char* ip_end = input + input_size; 781| 3.72k| const char* base_ip = ip; 782| | 783| 3.72k| const size_t kInputMarginBytes = 15; 784| 3.72k| if (SNAPPY_PREDICT_TRUE(input_size >= kInputMarginBytes)) { ------------------ | | 95| 3.72k|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 3.68k, False: 45] | | ------------------ ------------------ 785| 3.68k| const char* ip_limit = input + input_size - kInputMarginBytes; 786| | 787| 877k| for (uint32_t preload = LittleEndian::Load32(ip + 1);;) { 788| | // Bytes in [next_emit, ip) will be emitted as literal bytes. Or 789| | // [next_emit, ip_end) after the main loop. 790| 877k| const char* next_emit = ip++; 791| 877k| uint64_t data = LittleEndian::Load64(ip); 792| | // The body of this loop calls EmitLiteral once and then EmitCopy one or 793| | // more times. (The exception is that when we're close to exhausting 794| | // the input we goto emit_remainder.) 795| | // 796| | // In the first iteration of this loop we're just starting, so 797| | // there's nothing to copy, so calling EmitLiteral once is 798| | // necessary. And we only start a new iteration when the 799| | // current iteration has determined that a call to EmitLiteral will 800| | // precede the next call to EmitCopy (if any). 801| | // 802| | // Step 1: Scan forward in the input looking for a 4-byte-long match. 803| | // If we get close to exhausting the input then goto emit_remainder. 804| | // 805| | // Heuristic match skipping: If 32 bytes are scanned with no matches 806| | // found, start looking only at every other byte. If 32 more bytes are 807| | // scanned (or skipped), look at every third byte, etc.. When a match is 808| | // found, immediately go back to looking at every byte. This is a small 809| | // loss (~5% performance, ~0.1% density) for compressible data due to more 810| | // bookkeeping, but for non-compressible data (such as JPEG) it's a huge 811| | // win since the compressor quickly "realizes" the data is incompressible 812| | // and doesn't bother looking for matches everywhere. 813| | // 814| | // The "skip" variable keeps track of how many bytes there are since the 815| | // last match; dividing it by 32 (ie. right-shifting by five) gives the 816| | // number of bytes to move ahead for each iteration. 817| 877k| uint32_t skip = 32; 818| | 819| 877k| const char* candidate; 820| 877k| if (ip_limit - ip >= 16) { ------------------ | Branch (820:11): [True: 876k, False: 1.34k] ------------------ 821| 876k| auto delta = ip - base_ip; 822| 1.34M| for (int j = 0; j < 4; ++j) { ------------------ | Branch (822:25): [True: 1.27M, False: 65.9k] ------------------ 823| 3.66M| for (int k = 0; k < 4; ++k) { ------------------ | Branch (823:27): [True: 3.19M, False: 467k] ------------------ 824| 3.19M| int i = 4 * j + k; 825| | // These for-loops are meant to be unrolled. So we can freely 826| | // special case the first iteration to use the value already 827| | // loaded in preload. 828| 3.19M| uint32_t dword = i == 0 ? preload : static_cast(data); ------------------ | Branch (828:30): [True: 876k, False: 2.31M] ------------------ 829| 3.19M| assert(dword == LittleEndian::Load32(ip + i)); 830| 0| uint16_t* table_entry = TableEntry(table, dword, mask); 831| 3.19M| candidate = base_ip + *table_entry; 832| 3.19M| assert(candidate >= base_ip); 833| 0| assert(candidate < ip + i); 834| 0| *table_entry = delta + i; 835| 3.19M| if (SNAPPY_PREDICT_FALSE(LittleEndian::Load32(candidate) == dword)) { ------------------ | | 94| 3.19M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 810k, False: 2.38M] | | ------------------ ------------------ 836| 810k| *op = LITERAL | (i << 2); 837| 810k| UnalignedCopy128(next_emit, op + 1); 838| 810k| ip += i; 839| 810k| op = op + i + 2; 840| 810k| goto emit_match; 841| 810k| } 842| 2.38M| data >>= 8; 843| 2.38M| } 844| 467k| data = LittleEndian::Load64(ip + 4 * j + 4); 845| 467k| } 846| 65.9k| ip += 16; 847| 65.9k| skip += 16; 848| 65.9k| } 849| 2.39M| while (true) { ------------------ | Branch (849:14): [Folded - Ignored] ------------------ 850| 2.39M| assert(static_cast(data) == LittleEndian::Load32(ip)); 851| 0| uint16_t* table_entry = TableEntry(table, data, mask); 852| 2.39M| uint32_t bytes_between_hash_lookups = skip >> 5; 853| 2.39M| skip += bytes_between_hash_lookups; 854| 2.39M| const char* next_ip = ip + bytes_between_hash_lookups; 855| 2.39M| if (SNAPPY_PREDICT_FALSE(next_ip > ip_limit)) { ------------------ | | 94| 2.39M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 1.72k, False: 2.39M] | | ------------------ ------------------ 856| 1.72k| ip = next_emit; 857| 1.72k| goto emit_remainder; 858| 1.72k| } 859| 2.39M| candidate = base_ip + *table_entry; 860| 2.39M| assert(candidate >= base_ip); 861| 0| assert(candidate < ip); 862| | 863| 0| *table_entry = ip - base_ip; 864| 2.39M| if (SNAPPY_PREDICT_FALSE(static_cast(data) == ------------------ | | 94| 2.39M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 65.5k, False: 2.32M] | | ------------------ ------------------ 865| 2.39M| LittleEndian::Load32(candidate))) { 866| 65.5k| break; 867| 65.5k| } 868| 2.32M| data = LittleEndian::Load32(next_ip); 869| 2.32M| ip = next_ip; 870| 2.32M| } 871| | 872| | // Step 2: A 4-byte match has been found. We'll later see if more 873| | // than 4 bytes match. But, prior to the match, input 874| | // bytes [next_emit, ip) are unmatched. Emit them as "literal bytes." 875| 65.5k| assert(next_emit + 16 <= ip_end); 876| 0| op = EmitLiteral(op, next_emit, ip - next_emit); 877| | 878| | // Step 3: Call EmitCopy, and then see if another EmitCopy could 879| | // be our next move. Repeat until we find no match for the 880| | // input immediately after what was consumed by the last EmitCopy call. 881| | // 882| | // If we exit this loop normally then we need to call EmitLiteral next, 883| | // though we don't yet know how big the literal will be. We handle that 884| | // by proceeding to the next iteration of the main loop. We also can exit 885| | // this loop via goto if we get close to exhausting the input. 886| 875k| emit_match: 887| 1.80M| do { 888| | // We have a 4-byte match at ip, and no need to emit any 889| | // "literal bytes" prior to ip. 890| 1.80M| const char* base = ip; 891| 1.80M| std::pair p = 892| 1.80M| FindMatchLength(candidate + 4, ip + 4, ip_end, &data); 893| 1.80M| size_t matched = 4 + p.first; 894| 1.80M| ip += matched; 895| 1.80M| size_t offset = base - candidate; 896| 1.80M| assert(0 == memcmp(base, candidate, matched)); 897| 1.80M| if (p.second) { ------------------ | Branch (897:13): [True: 1.06M, False: 741k] ------------------ 898| 1.06M| op = EmitCopy(op, offset, matched); 899| 1.06M| } else { 900| 741k| op = EmitCopy(op, offset, matched); 901| 741k| } 902| 1.80M| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit)) { ------------------ | | 94| 1.80M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 1.96k, False: 1.80M] | | ------------------ ------------------ 903| 1.96k| goto emit_remainder; 904| 1.96k| } 905| | // Expect 5 bytes to match 906| 1.80M| assert((data & 0xFFFFFFFFFF) == 907| 1.80M| (LittleEndian::Load64(ip) & 0xFFFFFFFFFF)); 908| | // We are now looking for a 4-byte match again. We read 909| | // table[Hash(ip, mask)] for that. To improve compression, 910| | // we also update table[Hash(ip - 1, mask)] and table[Hash(ip, mask)]. 911| 0| *TableEntry(table, LittleEndian::Load32(ip - 1), mask) = 912| 1.80M| ip - base_ip - 1; 913| 1.80M| uint16_t* table_entry = TableEntry(table, data, mask); 914| 1.80M| candidate = base_ip + *table_entry; 915| 1.80M| *table_entry = ip - base_ip; 916| | // Measurements on the benchmarks have shown the following probabilities 917| | // for the loop to exit (ie. avg. number of iterations is reciprocal). 918| | // BM_Flat/6 txt1 p = 0.3-0.4 919| | // BM_Flat/7 txt2 p = 0.35 920| | // BM_Flat/8 txt3 p = 0.3-0.4 921| | // BM_Flat/9 txt3 p = 0.34-0.4 922| | // BM_Flat/10 pb p = 0.4 923| | // BM_Flat/11 gaviota p = 0.1 924| | // BM_Flat/12 cp p = 0.5 925| | // BM_Flat/13 c p = 0.3 926| 1.80M| } while (static_cast(data) == LittleEndian::Load32(candidate)); ------------------ | Branch (926:16): [True: 930k, False: 873k] ------------------ 927| | // Because the least significant 5 bytes matched, we can utilize data 928| | // for the next iteration. 929| 873k| preload = data >> 8; 930| 873k| } 931| 3.68k| } 932| | 933| 3.72k|emit_remainder: 934| | // Emit the remaining bytes as a literal 935| 3.72k| if (ip < ip_end) { ------------------ | Branch (935:7): [True: 2.72k, False: 1.00k] ------------------ 936| 2.72k| op = EmitLiteral(op, ip, ip_end - ip); 937| 2.72k| } 938| | 939| 3.72k| return op; 940| 3.72k|} _ZN6snappy9MemCopy64EPcPKvm: 1041| 3.37M|void MemCopy64(char* dst, const void* src, size_t size) { 1042| | // Always copy this many bytes. If that's below size then copy the full 64. 1043| 3.37M| constexpr int kShortMemCopy = 32; 1044| | 1045| 3.37M| assert(size <= 64); 1046| 0| assert(std::less_equal()(static_cast(src) + size, 1047| 3.37M| dst) || 1048| 3.37M| std::less_equal()(dst + size, src)); 1049| | 1050| | // We know that src and dst are at least size bytes apart. However, because we 1051| | // might copy more than size bytes the copy still might overlap past size. 1052| | // E.g. if src and dst appear consecutively in memory (src + size >= dst). 1053| | // TODO: Investigate wider copies on other platforms. 1054| |#if defined(__x86_64__) && defined(__AVX__) 1055| | assert(kShortMemCopy <= 32); 1056| | __m256i data = _mm256_lddqu_si256(static_cast(src)); 1057| | _mm256_storeu_si256(reinterpret_cast<__m256i *>(dst), data); 1058| | // Profiling shows that nearly all copies are short. 1059| | if (SNAPPY_PREDICT_FALSE(size > kShortMemCopy)) { 1060| | data = _mm256_lddqu_si256(static_cast(src) + 1); 1061| | _mm256_storeu_si256(reinterpret_cast<__m256i *>(dst) + 1, data); 1062| | } 1063| |#else 1064| 0| std::memmove(dst, src, kShortMemCopy); 1065| | // Profiling shows that nearly all copies are short. 1066| 3.37M| if (SNAPPY_PREDICT_FALSE(size > kShortMemCopy)) { ------------------ | | 94| 3.37M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 845k, False: 2.52M] | | ------------------ ------------------ 1067| 845k| std::memmove(dst + kShortMemCopy, 1068| 845k| static_cast(src) + kShortMemCopy, 1069| 845k| 64 - kShortMemCopy); 1070| 845k| } 1071| 3.37M|#endif 1072| 3.37M|} _ZN6snappy9MemCopy64ElPKvm: 1074| 3.37M|void MemCopy64(ptrdiff_t dst, const void* src, size_t size) { 1075| | // TODO: Switch to [[maybe_unused]] when we can assume C++17. 1076| 3.37M| (void)dst; 1077| 3.37M| (void)src; 1078| 3.37M| (void)size; 1079| 3.37M|} _ZN6snappy13ClearDeferredEPPKvPmPh: 1082| 966k| uint8_t* safe_source) { 1083| 966k| *deferred_src = safe_source; 1084| 966k| *deferred_length = 0; 1085| 966k|} _ZN6snappy12DeferMemCopyEPPKvPmS1_m: 1088| 5.87M| const void* src, size_t length) { 1089| 5.87M| *deferred_src = src; 1090| 5.87M| *deferred_length = length; 1091| 5.87M|} _ZN6snappy18SnappyDecompressor9RefillTagEv: 1517| 9.19k|bool SnappyDecompressor::RefillTag() { 1518| 9.19k| const char* ip = ip_; 1519| 9.19k| if (ip == ip_limit_) { ------------------ | Branch (1519:7): [True: 7.66k, False: 1.52k] ------------------ 1520| | // Fetch a new fragment from the reader 1521| 7.66k| reader_->Skip(peeked_); // All peeked bytes are used up 1522| 7.66k| size_t n; 1523| 7.66k| ip = reader_->Peek(&n); 1524| 7.66k| peeked_ = n; 1525| 7.66k| eof_ = (n == 0); 1526| 7.66k| if (eof_) return false; ------------------ | Branch (1526:9): [True: 3.83k, False: 3.83k] ------------------ 1527| 3.83k| ip_limit_ = ip + n; 1528| 3.83k| } 1529| | 1530| | // Read the tag character 1531| 5.35k| assert(ip < ip_limit_); 1532| 0| const unsigned char c = *(reinterpret_cast(ip)); 1533| | // At this point make sure that the data for the next tag is consecutive. 1534| | // For copy 1 this means the next 2 bytes (tag and 1 byte offset) 1535| | // For copy 2 the next 3 bytes (tag and 2 byte offset) 1536| | // For copy 4 the next 5 bytes (tag and 4 byte offset) 1537| | // For all small literals we only need 1 byte buf for literals 60...63 the 1538| | // length is encoded in 1...4 extra bytes. 1539| 5.35k| const uint32_t needed = CalculateNeeded(c); 1540| 5.35k| assert(needed <= sizeof(scratch_)); 1541| | 1542| | // Read more bytes from reader if needed 1543| 0| uint32_t nbuf = ip_limit_ - ip; 1544| 5.35k| if (nbuf < needed) { ------------------ | Branch (1544:7): [True: 0, False: 5.35k] ------------------ 1545| | // Stitch together bytes from ip and reader to form the word 1546| | // contents. We store the needed bytes in "scratch_". They 1547| | // will be consumed immediately by the caller since we do not 1548| | // read more than we need. 1549| 0| std::memmove(scratch_, ip, nbuf); 1550| 0| reader_->Skip(peeked_); // All peeked bytes are used up 1551| 0| peeked_ = 0; 1552| 0| while (nbuf < needed) { ------------------ | Branch (1552:12): [True: 0, False: 0] ------------------ 1553| 0| size_t length; 1554| 0| const char* src = reader_->Peek(&length); 1555| 0| if (length == 0) return false; ------------------ | Branch (1555:11): [True: 0, False: 0] ------------------ 1556| 0| uint32_t to_add = std::min(needed - nbuf, length); 1557| 0| std::memcpy(scratch_ + nbuf, src, to_add); 1558| 0| nbuf += to_add; 1559| 0| reader_->Skip(to_add); 1560| 0| } 1561| 0| assert(nbuf == needed); 1562| 0| ip_ = scratch_; 1563| 0| ip_limit_ = scratch_ + needed; 1564| 5.35k| } else if (nbuf < kMaximumTagLength) { ------------------ | Branch (1564:14): [True: 1.53k, False: 3.82k] ------------------ 1565| | // Have enough bytes, but move into scratch_ so that we do not 1566| | // read past end of input 1567| 1.53k| std::memmove(scratch_, ip, nbuf); 1568| 1.53k| reader_->Skip(peeked_); // All peeked bytes are used up 1569| 1.53k| peeked_ = 0; 1570| 1.53k| ip_ = scratch_; 1571| 1.53k| ip_limit_ = scratch_ + nbuf; 1572| 3.82k| } else { 1573| | // Pass pointer to buffer returned by reader_. 1574| 3.82k| ip_ = ip; 1575| 3.82k| } 1576| 5.35k| return true; 1577| 5.35k|} _ZN6snappy8CompressEPNS_6SourceEPNS_4SinkE: 1609| 1.91k|size_t Compress(Source* reader, Sink* writer) { 1610| 1.91k| size_t written = 0; 1611| 1.91k| size_t N = reader->Available(); 1612| 1.91k| const size_t uncompressed_size = N; 1613| 1.91k| char ulength[Varint::kMax32]; 1614| 1.91k| char* p = Varint::Encode32(ulength, N); 1615| 1.91k| writer->Append(ulength, p - ulength); 1616| 1.91k| written += (p - ulength); 1617| | 1618| 1.91k| internal::WorkingMemory wmem(N); 1619| | 1620| 5.64k| while (N > 0) { ------------------ | Branch (1620:10): [True: 3.72k, False: 1.91k] ------------------ 1621| | // Get next block to compress (without copying if possible) 1622| 3.72k| size_t fragment_size; 1623| 3.72k| const char* fragment = reader->Peek(&fragment_size); 1624| 3.72k| assert(fragment_size != 0); // premature end of input 1625| 0| const size_t num_to_read = std::min(N, kBlockSize); 1626| 3.72k| size_t bytes_read = fragment_size; 1627| | 1628| 3.72k| size_t pending_advance = 0; 1629| 3.72k| if (bytes_read >= num_to_read) { ------------------ | Branch (1629:9): [True: 3.72k, False: 0] ------------------ 1630| | // Buffer returned by reader is large enough 1631| 3.72k| pending_advance = num_to_read; 1632| 3.72k| fragment_size = num_to_read; 1633| 3.72k| } else { 1634| 0| char* scratch = wmem.GetScratchInput(); 1635| 0| std::memcpy(scratch, fragment, bytes_read); 1636| 0| reader->Skip(bytes_read); 1637| | 1638| 0| while (bytes_read < num_to_read) { ------------------ | Branch (1638:14): [True: 0, False: 0] ------------------ 1639| 0| fragment = reader->Peek(&fragment_size); 1640| 0| size_t n = std::min(fragment_size, num_to_read - bytes_read); 1641| 0| std::memcpy(scratch + bytes_read, fragment, n); 1642| 0| bytes_read += n; 1643| 0| reader->Skip(n); 1644| 0| } 1645| 0| assert(bytes_read == num_to_read); 1646| 0| fragment = scratch; 1647| 0| fragment_size = num_to_read; 1648| 0| } 1649| 0| assert(fragment_size == num_to_read); 1650| | 1651| | // Get encoding table for compression 1652| 0| int table_size; 1653| 3.72k| uint16_t* table = wmem.GetHashTable(num_to_read, &table_size); 1654| | 1655| | // Compress input_fragment and append to dest 1656| 3.72k| const int max_output = MaxCompressedLength(num_to_read); 1657| | 1658| | // Need a scratch buffer for the output, in case the byte sink doesn't 1659| | // have room for us directly. 1660| | 1661| | // Since we encode kBlockSize regions followed by a region 1662| | // which is <= kBlockSize in length, a previously allocated 1663| | // scratch_output[] region is big enough for this iteration. 1664| 3.72k| char* dest = writer->GetAppendBuffer(max_output, wmem.GetScratchOutput()); 1665| 3.72k| char* end = internal::CompressFragment(fragment, fragment_size, dest, table, 1666| 3.72k| table_size); 1667| 3.72k| writer->Append(dest, end - dest); 1668| 3.72k| written += (end - dest); 1669| | 1670| 3.72k| N -= num_to_read; 1671| 3.72k| reader->Skip(pending_advance); 1672| 3.72k| } 1673| | 1674| 1.91k| Report("snappy_compress", written, uncompressed_size); 1675| | 1676| 1.91k| return written; 1677| 1.91k|} _ZN6snappy13RawUncompressEPKcmPc: 2028| 1.91k| char* uncompressed) { 2029| 1.91k| ByteArraySource reader(compressed, compressed_length); 2030| 1.91k| return RawUncompress(&reader, uncompressed); 2031| 1.91k|} _ZN6snappy13RawUncompressEPNS_6SourceEPc: 2033| 1.91k|bool RawUncompress(Source* compressed, char* uncompressed) { 2034| 1.91k| SnappyArrayWriter output(uncompressed); 2035| 1.91k| return InternalUncompress(compressed, &output); 2036| 1.91k|} _ZN6snappy10UncompressEPKcmPNSt3__112basic_stringIcNS2_11char_traitsIcEENS2_9allocatorIcEEEE: 2039| 1.91k| std::string* uncompressed) { 2040| 1.91k| size_t ulength; 2041| 1.91k| if (!GetUncompressedLength(compressed, compressed_length, &ulength)) { ------------------ | Branch (2041:7): [True: 0, False: 1.91k] ------------------ 2042| 0| return false; 2043| 0| } 2044| | // On 32-bit builds: max_size() < kuint32max. Check for that instead 2045| | // of crashing (e.g., consider externally specified compressed data). 2046| 1.91k| if (ulength > uncompressed->max_size()) { ------------------ | Branch (2046:7): [True: 0, False: 1.91k] ------------------ 2047| 0| return false; 2048| 0| } 2049| 1.91k| STLStringResizeUninitialized(uncompressed, ulength); 2050| 1.91k| return RawUncompress(compressed, compressed_length, 2051| 1.91k| string_as_array(uncompressed)); 2052| 1.91k|} _ZN6snappy23IsValidCompressedBufferEPKcm: 2097| 1.91k|bool IsValidCompressedBuffer(const char* compressed, size_t compressed_length) { 2098| 1.91k| ByteArraySource reader(compressed, compressed_length); 2099| 1.91k| SnappyDecompressionValidator writer; 2100| 1.91k| return InternalUncompress(&reader, &writer); 2101| 1.91k|} _ZN6snappy11RawCompressEPKcmPcPm: 2109| 1.91k| size_t* compressed_length) { 2110| 1.91k| ByteArraySource reader(input, input_length); 2111| 1.91k| UncheckedByteArraySink writer(compressed); 2112| 1.91k| Compress(&reader, &writer); 2113| | 2114| | // Compute how many bytes were added 2115| 1.91k| *compressed_length = (writer.CurrentDestination() - compressed); 2116| 1.91k|} _ZN6snappy8CompressEPKcmPNSt3__112basic_stringIcNS2_11char_traitsIcEENS2_9allocatorIcEEEE: 2129| 1.91k| std::string* compressed) { 2130| | // Pre-grow the buffer to the max length of the compressed output 2131| 1.91k| STLStringResizeUninitialized(compressed, MaxCompressedLength(input_length)); 2132| | 2133| 1.91k| size_t compressed_length; 2134| 1.91k| RawCompress(input, input_length, string_as_array(compressed), 2135| 1.91k| &compressed_length); 2136| 1.91k| compressed->erase(compressed_length); 2137| 1.91k| return compressed_length; 2138| 1.91k|} snappy.cc:_ZN6snappy12_GLOBAL__N_118CalculateTableSizeEj: 720| 5.64k|uint32_t CalculateTableSize(uint32_t input_size) { 721| 5.64k| static_assert( 722| 5.64k| kMaxHashTableSize >= kMinHashTableSize, 723| 5.64k| "kMaxHashTableSize should be greater or equal to kMinHashTableSize."); 724| 5.64k| if (input_size > kMaxHashTableSize) { ------------------ | Branch (724:7): [True: 2.55k, False: 3.09k] ------------------ 725| 2.55k| return kMaxHashTableSize; 726| 2.55k| } 727| 3.09k| if (input_size < kMinHashTableSize) { ------------------ | Branch (727:7): [True: 2.01k, False: 1.07k] ------------------ 728| 2.01k| return kMinHashTableSize; 729| 2.01k| } 730| | // This is equivalent to Log2Ceiling(input_size), assuming input_size > 1. 731| | // 2 << Log2Floor(x - 1) is equivalent to 1 << (1 + Log2Floor(x - 1)). 732| 1.07k| return 2u << Bits::Log2Floor(input_size - 1); 733| 3.09k|} snappy.cc:_ZN6snappy12_GLOBAL__N_110TableEntryEPtjj: 153| 9.19M|inline uint16_t* TableEntry(uint16_t* table, uint32_t bytes, uint32_t mask) { 154| | // Our choice is quicker-and-dirtier than the typical hash function; 155| | // empirically, that seems beneficial. The upper bits of kMagic * bytes are a 156| | // higher-quality hash than the lower bits, so when using kMagic * bytes we 157| | // also shift right to get a higher-quality end result. There's no similar 158| | // issue with a CRC because all of the output bits of a CRC are equally good 159| | // "hashes." So, a CPU instruction for CRC, if available, tends to be a good 160| | // choice. 161| |#if SNAPPY_HAVE_NEON_CRC32 162| | // We use mask as the second arg to the CRC function, as it's about to 163| | // be used anyway; it'd be equally correct to use 0 or some constant. 164| | // Mathematically, _mm_crc32_u32 (or similar) is a function of the 165| | // xor of its arguments. 166| | const uint32_t hash = __crc32cw(bytes, mask); 167| |#elif SNAPPY_HAVE_X86_CRC32 168| | const uint32_t hash = _mm_crc32_u32(bytes, mask); 169| |#else 170| 9.19M| constexpr uint32_t kMagic = 0x1e35a7bd; 171| 9.19M| const uint32_t hash = (kMagic * bytes) >> (31 - kMaxHashTableBits); 172| 9.19M|#endif 173| 9.19M| return reinterpret_cast(reinterpret_cast(table) + 174| 9.19M| (hash & mask)); 175| 9.19M|} snappy.cc:_ZN6snappy12_GLOBAL__N_116UnalignedCopy128EPKvPv: 211| 814k|void UnalignedCopy128(const void* src, void* dst) { 212| | // std::memcpy() gets vectorized when the appropriate compiler options are 213| | // used. For example, x86 compilers targeting SSE2+ will optimize to an SSE2 214| | // load and store. 215| 814k| char tmp[16]; 216| 814k| std::memcpy(tmp, src, 16); 217| 814k| std::memcpy(dst, tmp, 16); 218| 814k|} _ZN6snappy15CalculateNeededEh: 1498| 5.35k|constexpr uint32_t CalculateNeeded(uint8_t tag) { 1499| 5.35k| return ((tag & 3) == 0 && tag >= (60 * 4)) ------------------ | Branch (1499:11): [True: 4.35k, False: 1.00k] | Branch (1499:29): [True: 596, False: 3.75k] ------------------ 1500| 5.35k| ? (tag >> 2) - 58 1501| 5.35k| : (0x05030201 >> ((tag * 8) & 31)) & 0xFF; 1502| 5.35k|} _ZN6snappy18SnappyDecompressorC2EPNS_6SourceE: 1334| 3.83k| : reader_(reader), ip_(NULL), ip_limit_(NULL), peeked_(0), eof_(false) {} _ZN6snappy18SnappyDecompressor22ReadUncompressedLengthEPj: 1347| 3.83k| bool ReadUncompressedLength(uint32_t* result) { 1348| 3.83k| assert(ip_ == NULL); // Must not have read anything yet 1349| | // Length is encoded in 1..5 bytes 1350| 0| *result = 0; 1351| 3.83k| uint32_t shift = 0; 1352| 7.18k| while (true) { ------------------ | Branch (1352:12): [Folded - Ignored] ------------------ 1353| 7.18k| if (shift >= 32) return false; ------------------ | Branch (1353:11): [True: 0, False: 7.18k] ------------------ 1354| 7.18k| size_t n; 1355| 7.18k| const char* ip = reader_->Peek(&n); 1356| 7.18k| if (n == 0) return false; ------------------ | Branch (1356:11): [True: 0, False: 7.18k] ------------------ 1357| 7.18k| const unsigned char c = *(reinterpret_cast(ip)); 1358| 7.18k| reader_->Skip(1); 1359| 7.18k| uint32_t val = c & 0x7f; 1360| 7.18k| if (LeftShiftOverflows(static_cast(val), shift)) return false; ------------------ | Branch (1360:11): [True: 0, False: 7.18k] ------------------ 1361| 7.18k| *result |= val << shift; 1362| 7.18k| if (c < 128) { ------------------ | Branch (1362:11): [True: 3.83k, False: 3.35k] ------------------ 1363| 3.83k| break; 1364| 3.83k| } 1365| 3.35k| shift += 7; 1366| 3.35k| } 1367| 3.83k| return true; 1368| 3.83k| } snappy.cc:_ZN6snappyL18LeftShiftOverflowsEhj: 1021| 7.18k|static inline bool LeftShiftOverflows(uint8_t value, uint32_t shift) { 1022| 7.18k| assert(shift < 32); 1023| 0| static const uint8_t masks[] = { 1024| 7.18k| 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 1025| 7.18k| 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 1026| 7.18k| 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 1027| 7.18k| 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe}; 1028| 7.18k| return (value & masks[shift]) != 0; 1029| 7.18k|} _ZN6snappy18SnappyDecompressorD2Ev: 1336| 3.83k| ~SnappyDecompressor() { 1337| | // Advance past any bytes we peeked at from the reader 1338| 3.83k| reader_->Skip(peeked_); 1339| 3.83k| } snappy.cc:_ZN6snappyL6ReportEPKcmm: 945| 5.74k| size_t uncompressed_size) { 946| | // TODO: Switch to [[maybe_unused]] when we can assume C++17. 947| 5.74k| (void)algorithm; 948| 5.74k| (void)compressed_size; 949| 5.74k| (void)uncompressed_size; 950| 5.74k|} _ZN6snappy17SnappyArrayWriterC2EPc: 1959| 1.91k| op_limit_min_slop_(dst) {} // Safe default see invariant. _ZN6snappy28SnappyDecompressionValidatorC2Ev: 2061| 1.91k| inline SnappyDecompressionValidator() : expected_(0), produced_(0) {} snappy.cc:_ZN6snappyL11EmitLiteralILb1EEEPcS1_PKci: 596| 65.5k|static inline char* EmitLiteral(char* op, const char* literal, int len) { 597| | // The vast majority of copies are below 16 bytes, for which a 598| | // call to std::memcpy() is overkill. This fast path can sometimes 599| | // copy up to 15 bytes too much, but that is okay in the 600| | // main loop, since we have a bit to go on for both sides: 601| | // 602| | // - The input will always have kInputMarginBytes = 15 extra 603| | // available bytes, as long as we're in the main loop, and 604| | // if not, allow_fast_path = false. 605| | // - The output will always have 32 spare bytes (see 606| | // MaxCompressedLength). 607| 65.5k| assert(len > 0); // Zero-length literals are disallowed 608| 0| int n = len - 1; 609| 65.5k| if (allow_fast_path && len <= 16) { ------------------ | Branch (609:7): [Folded - Ignored] | Branch (609:26): [True: 969, False: 64.5k] ------------------ 610| | // Fits in tag byte 611| 969| *op++ = LITERAL | (n << 2); 612| | 613| 969| UnalignedCopy128(literal, op); 614| 969| return op + len; 615| 969| } 616| | 617| 64.5k| if (n < 60) { ------------------ | Branch (617:7): [True: 39.2k, False: 25.3k] ------------------ 618| | // Fits in tag byte 619| 39.2k| *op++ = LITERAL | (n << 2); 620| 39.2k| } else { 621| 25.3k| int count = (Bits::Log2Floor(n) >> 3) + 1; 622| 25.3k| assert(count >= 1); 623| 0| assert(count <= 4); 624| 0| *op++ = LITERAL | ((59 + count) << 2); 625| | // Encode in upcoming bytes. 626| | // Write 4 bytes, though we may care about only 1 of them. The output buffer 627| | // is guaranteed to have at least 3 more spaces left as 'len >= 61' holds 628| | // here and there is a std::memcpy() of size 'len' below. 629| 25.3k| LittleEndian::Store32(op, n); 630| 25.3k| op += count; 631| 25.3k| } 632| | // When allow_fast_path is true, we can overwrite up to 16 bytes. 633| 64.5k| if (allow_fast_path) { ------------------ | Branch (633:7): [Folded - Ignored] ------------------ 634| 64.5k| char* destination = op; 635| 64.5k| const char* source = literal; 636| 64.5k| const char* end = destination + len; 637| 1.41M| do { 638| 1.41M| std::memcpy(destination, source, 16); 639| 1.41M| destination += 16; 640| 1.41M| source += 16; 641| 1.41M| } while (destination < end); ------------------ | Branch (641:14): [True: 1.34M, False: 64.5k] ------------------ 642| 64.5k| } else { 643| 0| std::memcpy(op, literal, len); 644| 0| } 645| 64.5k| return op + len; 646| 65.5k|} snappy.cc:_ZN6snappyL8EmitCopyILb1EEEPcS1_mm: 678| 1.06M|static inline char* EmitCopy(char* op, size_t offset, size_t len) { 679| 1.06M| assert(len_less_than_12 == (len < 12)); 680| 1.06M| if (len_less_than_12) { ------------------ | Branch (680:7): [Folded - Ignored] ------------------ 681| 1.06M| return EmitCopyAtMost64(op, offset, len); 682| 1.06M| } else { 683| | // A special case for len <= 64 might help, but so far measurements suggest 684| | // it's in the noise. 685| | 686| | // Emit 64 byte copies but make sure to keep at least four bytes reserved. 687| 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] | | ------------------ ------------------ 688| 0| op = EmitCopyAtMost64(op, offset, 64); 689| 0| len -= 64; 690| 0| } 691| | 692| | // One or two copies will now finish the job. 693| 0| if (len > 64) { ------------------ | Branch (693:9): [True: 0, False: 0] ------------------ 694| 0| op = EmitCopyAtMost64(op, offset, 60); 695| 0| len -= 60; 696| 0| } 697| | 698| | // Emit remainder. 699| 0| if (len < 12) { ------------------ | Branch (699:9): [True: 0, False: 0] ------------------ 700| 0| op = EmitCopyAtMost64(op, offset, len); 701| 0| } else { 702| 0| op = EmitCopyAtMost64(op, offset, len); 703| 0| } 704| 0| return op; 705| 0| } 706| 1.06M|} snappy.cc:_ZN6snappyL16EmitCopyAtMost64ILb1EEEPcS1_mm: 649| 1.08M|static inline char* EmitCopyAtMost64(char* op, size_t offset, size_t len) { 650| 1.08M| assert(len <= 64); 651| 0| assert(len >= 4); 652| 0| assert(offset < 65536); 653| 0| assert(len_less_than_12 == (len < 12)); 654| | 655| 1.08M| if (len_less_than_12) { ------------------ | Branch (655:7): [Folded - Ignored] ------------------ 656| 1.08M| uint32_t u = (len << 2) + (offset << 8); 657| 1.08M| uint32_t copy1 = COPY_1_BYTE_OFFSET - (4 << 2) + ((offset >> 3) & 0xe0); 658| 1.08M| uint32_t copy2 = COPY_2_BYTE_OFFSET - (1 << 2); 659| | // It turns out that offset < 2048 is a difficult to predict branch. 660| | // `perf record` shows this is the highest percentage of branch misses in 661| | // benchmarks. This code produces branch free code, the data dependency 662| | // chain that bottlenecks the throughput is so long that a few extra 663| | // instructions are completely free (IPC << 6 because of data deps). 664| 1.08M| u += offset < 2048 ? copy1 : copy2; ------------------ | Branch (664:10): [True: 679k, False: 401k] ------------------ 665| 1.08M| LittleEndian::Store32(op, u); 666| 1.08M| op += offset < 2048 ? 2 : 3; ------------------ | Branch (666:11): [True: 679k, False: 401k] ------------------ 667| 1.08M| } else { 668| | // Write 4 bytes, though we only care about 3 of them. The output buffer 669| | // is required to have some slack, so the extra byte won't overrun it. 670| 0| uint32_t u = COPY_2_BYTE_OFFSET + ((len - 1) << 2) + (offset << 8); 671| 0| LittleEndian::Store32(op, u); 672| 0| op += 3; 673| 0| } 674| 1.08M| return op; 675| 1.08M|} snappy.cc:_ZN6snappyL8EmitCopyILb0EEEPcS1_mm: 678| 741k|static inline char* EmitCopy(char* op, size_t offset, size_t len) { 679| 741k| assert(len_less_than_12 == (len < 12)); 680| 741k| if (len_less_than_12) { ------------------ | Branch (680:7): [Folded - Ignored] ------------------ 681| 0| return EmitCopyAtMost64(op, offset, len); 682| 741k| } else { 683| | // A special case for len <= 64 might help, but so far measurements suggest 684| | // it's in the noise. 685| | 686| | // Emit 64 byte copies but make sure to keep at least four bytes reserved. 687| 1.44M| while (SNAPPY_PREDICT_FALSE(len >= 68)) { ------------------ | | 94| 1.44M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 708k, False: 741k] | | ------------------ ------------------ 688| 708k| op = EmitCopyAtMost64(op, offset, 64); 689| 708k| len -= 64; 690| 708k| } 691| | 692| | // One or two copies will now finish the job. 693| 741k| if (len > 64) { ------------------ | Branch (693:9): [True: 4.21k, False: 736k] ------------------ 694| 4.21k| op = EmitCopyAtMost64(op, offset, 60); 695| 4.21k| len -= 60; 696| 4.21k| } 697| | 698| | // Emit remainder. 699| 741k| if (len < 12) { ------------------ | Branch (699:9): [True: 15.6k, False: 725k] ------------------ 700| 15.6k| op = EmitCopyAtMost64(op, offset, len); 701| 725k| } else { 702| 725k| op = EmitCopyAtMost64(op, offset, len); 703| 725k| } 704| 741k| return op; 705| 741k| } 706| 741k|} snappy.cc:_ZN6snappyL16EmitCopyAtMost64ILb0EEEPcS1_mm: 649| 1.43M|static inline char* EmitCopyAtMost64(char* op, size_t offset, size_t len) { 650| 1.43M| assert(len <= 64); 651| 0| assert(len >= 4); 652| 0| assert(offset < 65536); 653| 0| assert(len_less_than_12 == (len < 12)); 654| | 655| 1.43M| if (len_less_than_12) { ------------------ | Branch (655:7): [Folded - Ignored] ------------------ 656| 0| uint32_t u = (len << 2) + (offset << 8); 657| 0| uint32_t copy1 = COPY_1_BYTE_OFFSET - (4 << 2) + ((offset >> 3) & 0xe0); 658| 0| uint32_t copy2 = COPY_2_BYTE_OFFSET - (1 << 2); 659| | // It turns out that offset < 2048 is a difficult to predict branch. 660| | // `perf record` shows this is the highest percentage of branch misses in 661| | // benchmarks. This code produces branch free code, the data dependency 662| | // chain that bottlenecks the throughput is so long that a few extra 663| | // instructions are completely free (IPC << 6 because of data deps). 664| 0| u += offset < 2048 ? copy1 : copy2; ------------------ | Branch (664:10): [True: 0, False: 0] ------------------ 665| 0| LittleEndian::Store32(op, u); 666| 0| op += offset < 2048 ? 2 : 3; ------------------ | Branch (666:11): [True: 0, False: 0] ------------------ 667| 1.43M| } else { 668| | // Write 4 bytes, though we only care about 3 of them. The output buffer 669| | // is required to have some slack, so the extra byte won't overrun it. 670| 1.43M| uint32_t u = COPY_2_BYTE_OFFSET + ((len - 1) << 2) + (offset << 8); 671| 1.43M| LittleEndian::Store32(op, u); 672| 1.43M| op += 3; 673| 1.43M| } 674| 1.43M| return op; 675| 1.43M|} snappy.cc:_ZN6snappyL11EmitLiteralILb0EEEPcS1_PKci: 596| 2.72k|static inline char* EmitLiteral(char* op, const char* literal, int len) { 597| | // The vast majority of copies are below 16 bytes, for which a 598| | // call to std::memcpy() is overkill. This fast path can sometimes 599| | // copy up to 15 bytes too much, but that is okay in the 600| | // main loop, since we have a bit to go on for both sides: 601| | // 602| | // - The input will always have kInputMarginBytes = 15 extra 603| | // available bytes, as long as we're in the main loop, and 604| | // if not, allow_fast_path = false. 605| | // - The output will always have 32 spare bytes (see 606| | // MaxCompressedLength). 607| 2.72k| assert(len > 0); // Zero-length literals are disallowed 608| 0| int n = len - 1; 609| 2.72k| if (allow_fast_path && len <= 16) { ------------------ | Branch (609:7): [Folded - Ignored] | Branch (609:26): [True: 0, False: 0] ------------------ 610| | // Fits in tag byte 611| 0| *op++ = LITERAL | (n << 2); 612| | 613| 0| UnalignedCopy128(literal, op); 614| 0| return op + len; 615| 0| } 616| | 617| 2.72k| if (n < 60) { ------------------ | Branch (617:7): [True: 1.43k, False: 1.28k] ------------------ 618| | // Fits in tag byte 619| 1.43k| *op++ = LITERAL | (n << 2); 620| 1.43k| } else { 621| 1.28k| int count = (Bits::Log2Floor(n) >> 3) + 1; 622| 1.28k| assert(count >= 1); 623| 0| assert(count <= 4); 624| 0| *op++ = LITERAL | ((59 + count) << 2); 625| | // Encode in upcoming bytes. 626| | // Write 4 bytes, though we may care about only 1 of them. The output buffer 627| | // is guaranteed to have at least 3 more spaces left as 'len >= 61' holds 628| | // here and there is a std::memcpy() of size 'len' below. 629| 1.28k| LittleEndian::Store32(op, n); 630| 1.28k| op += count; 631| 1.28k| } 632| | // When allow_fast_path is true, we can overwrite up to 16 bytes. 633| 2.72k| if (allow_fast_path) { ------------------ | Branch (633:7): [Folded - Ignored] ------------------ 634| 0| char* destination = op; 635| 0| const char* source = literal; 636| 0| const char* end = destination + len; 637| 0| do { 638| 0| std::memcpy(destination, source, 16); 639| 0| destination += 16; 640| 0| source += 16; 641| 0| } while (destination < end); ------------------ | Branch (641:14): [True: 0, False: 0] ------------------ 642| 2.72k| } else { 643| 2.72k| std::memcpy(op, literal, len); 644| 2.72k| } 645| 2.72k| return op + len; 646| 2.72k|} _ZN6snappy18SnappyDecompressor10ResetLimitEPKc: 1327| 9.19k| void ResetLimit(const char* ip) { 1328| 9.19k| ip_limit_min_maxtaglen_ = 1329| 9.19k| ip_limit_ - std::min(ip_limit_ - ip, kMaximumTagLength - 1); 1330| 9.19k| } _ZN6snappy20DecompressBranchlessIPcEENSt3__14pairIPKhlEES5_S5_lT_l: 1196| 45.8k| ptrdiff_t op_limit_min_slop) { 1197| | // If deferred_src is invalid point it here. 1198| 45.8k| uint8_t safe_source[64]; 1199| 45.8k| const void* deferred_src; 1200| 45.8k| size_t deferred_length; 1201| 45.8k| ClearDeferred(&deferred_src, &deferred_length, safe_source); 1202| | 1203| | // We unroll the inner loop twice so we need twice the spare room. 1204| 45.8k| op_limit_min_slop -= kSlopBytes; 1205| 45.8k| if (2 * (kSlopBytes + 1) < ip_limit - ip && op < op_limit_min_slop) { ------------------ | Branch (1205:7): [True: 26.8k, False: 18.9k] | Branch (1205:47): [True: 26.8k, False: 0] ------------------ 1206| 26.8k| const uint8_t* const ip_limit_min_slop = ip_limit - 2 * kSlopBytes - 1; 1207| 26.8k| ip++; 1208| | // ip points just past the tag and we are touching at maximum kSlopBytes 1209| | // in an iteration. 1210| 26.8k| size_t tag = ip[-1]; 1211| |#if defined(__clang__) && defined(__aarch64__) 1212| | // Workaround for https://bugs.llvm.org/show_bug.cgi?id=51317 1213| | // when loading 1 byte, clang for aarch64 doesn't realize that it(ldrb) 1214| | // comes with free zero-extension, so clang generates another 1215| | // 'and xn, xm, 0xff' before it use that as the offset. This 'and' is 1216| | // redundant and can be removed by adding this dummy asm, which gives 1217| | // clang a hint that we're doing the zero-extension at the load. 1218| | asm("" ::"r"(tag)); 1219| |#endif 1220| 1.69M| do { 1221| | // The throughput is limited by instructions, unrolling the inner loop 1222| | // twice reduces the amount of instructions checking limits and also 1223| | // leads to reduced mov's. 1224| | 1225| 1.69M| SNAPPY_PREFETCH(ip + 128); ------------------ | | 109| 1.69M|#define SNAPPY_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 3) ------------------ 1226| 5.04M| for (int i = 0; i < 2; i++) { ------------------ | Branch (1226:23): [True: 3.37M, False: 1.66M] ------------------ 1227| 3.37M| const uint8_t* old_ip = ip; 1228| 3.37M| assert(tag == ip[-1]); 1229| | // For literals tag_type = 0, hence we will always obtain 0 from 1230| | // ExtractLowBytes. For literals offset will thus be kLiteralOffset. 1231| 0| ptrdiff_t len_minus_offset = kLengthMinusOffset[tag]; 1232| 3.37M| uint32_t next; 1233| |#if defined(__aarch64__) 1234| | size_t tag_type = AdvanceToNextTagARMOptimized(&ip, &tag); 1235| | // We never need more than 16 bits. Doing a Load16 allows the compiler 1236| | // to elide the masking operation in ExtractOffset. 1237| | next = LittleEndian::Load16(old_ip); 1238| |#else 1239| 3.37M| size_t tag_type = AdvanceToNextTagX86Optimized(&ip, &tag); 1240| 3.37M| next = LittleEndian::Load32(old_ip); 1241| 3.37M|#endif 1242| 3.37M| size_t len = len_minus_offset & 0xFF; 1243| 3.37M| ptrdiff_t extracted = ExtractOffset(next, tag_type); 1244| 3.37M| ptrdiff_t len_min_offset = len_minus_offset - extracted; 1245| 3.37M| if (SNAPPY_PREDICT_FALSE(len_minus_offset > extracted)) { ------------------ | | 94| 3.37M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 442k, False: 2.93M] | | ------------------ ------------------ 1246| 442k| if (SNAPPY_PREDICT_FALSE(len & 0x80)) { ------------------ | | 94| 442k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 26.2k, False: 415k] | | ------------------ ------------------ 1247| | // Exceptional case (long literal or copy 4). 1248| | // Actually doing the copy here is negatively impacting the main 1249| | // loop due to compiler incorrectly allocating a register for 1250| | // this fallback. Hence we just break. 1251| 26.2k| break_loop: 1252| 26.2k| ip = old_ip; 1253| 26.2k| goto exit; 1254| 26.2k| } 1255| | // Only copy-1 or copy-2 tags can get here. 1256| 415k| assert(tag_type == 1 || tag_type == 2); 1257| 0| std::ptrdiff_t delta = (op + deferred_length) + len_min_offset - len; 1258| | // Guard against copies before the buffer start. 1259| | // Execute any deferred MemCopy since we write to dst here. 1260| 415k| MemCopy64(op_base + op, deferred_src, deferred_length); 1261| 415k| op += deferred_length; 1262| 415k| ClearDeferred(&deferred_src, &deferred_length, safe_source); 1263| 415k| if (SNAPPY_PREDICT_FALSE(delta < 0 || ------------------ | | 94| 831k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 0, False: 415k] | | | Branch (94:51): [True: 0, False: 415k] | | | Branch (94:51): [True: 0, False: 415k] | | ------------------ ------------------ 1264| 415k| !Copy64BytesWithPatternExtension( 1265| 415k| op_base + op, len - len_min_offset))) { 1266| 0| goto break_loop; 1267| 0| } 1268| | // We aren't deferring this copy so add length right away. 1269| 415k| op += len; 1270| 415k| continue; 1271| 415k| } 1272| 2.93M| std::ptrdiff_t delta = (op + deferred_length) + len_min_offset - len; 1273| 2.93M| if (SNAPPY_PREDICT_FALSE(delta < 0)) { ------------------ | | 94| 2.93M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 5.71k, False: 2.93M] | | ------------------ ------------------ 1274| | // Due to the spurious offset in literals have this will trigger 1275| | // at the start of a block when op is still smaller than 256. 1276| 5.71k| if (tag_type != 0) goto break_loop; ------------------ | Branch (1276:15): [True: 0, False: 5.71k] ------------------ 1277| 5.71k| MemCopy64(op_base + op, deferred_src, deferred_length); 1278| 5.71k| op += deferred_length; 1279| 5.71k| DeferMemCopy(&deferred_src, &deferred_length, old_ip, len); 1280| 5.71k| continue; 1281| 5.71k| } 1282| | 1283| | // For copies we need to copy from op_base + delta, for literals 1284| | // we need to copy from ip instead of from the stream. 1285| 2.93M| const void* from = 1286| 2.93M| tag_type ? reinterpret_cast(op_base + delta) : old_ip; ------------------ | Branch (1286:13): [True: 2.09M, False: 840k] ------------------ 1287| 2.93M| MemCopy64(op_base + op, deferred_src, deferred_length); 1288| 2.93M| op += deferred_length; 1289| 2.93M| DeferMemCopy(&deferred_src, &deferred_length, from, len); 1290| 2.93M| } 1291| 1.69M| } while (ip < ip_limit_min_slop && ------------------ | Branch (1291:14): [True: 1.66M, False: 608] ------------------ 1292| 1.66M| (op + deferred_length) < op_limit_min_slop); ------------------ | Branch (1292:14): [True: 1.66M, False: 1] ------------------ 1293| 26.8k| exit: 1294| 26.8k| ip--; 1295| 26.8k| assert(ip <= ip_limit); 1296| 26.8k| } 1297| | // If we deferred a copy then we can perform. If we are up to date then we 1298| | // might not have enough slop bytes and could run past the end. 1299| 45.8k| if (deferred_length) { ------------------ | Branch (1299:7): [True: 21.2k, False: 24.6k] ------------------ 1300| 21.2k| MemCopy64(op_base + op, deferred_src, deferred_length); 1301| 21.2k| op += deferred_length; 1302| 21.2k| ClearDeferred(&deferred_src, &deferred_length, safe_source); 1303| 21.2k| } 1304| 45.8k| return {ip, op}; 1305| 45.8k|} _ZN6snappy28AdvanceToNextTagX86OptimizedEPPKhPm: 1117| 6.75M|inline size_t AdvanceToNextTagX86Optimized(const uint8_t** ip_p, size_t* tag) { 1118| 6.75M| const uint8_t*& ip = *ip_p; 1119| | // This section is crucial for the throughput of the decompression loop. 1120| | // The latency of an iteration is fundamentally constrained by the 1121| | // following data chain on ip. 1122| | // ip -> c = Load(ip) -> ip1 = ip + 1 + (c & 3) -> ip = ip1 or ip2 1123| | // ip2 = ip + 2 + (c >> 2) 1124| | // This amounts to 8 cycles. 1125| | // 5 (load) + 1 (c & 3) + 1 (lea ip1, [ip + (c & 3) + 1]) + 1 (cmov) 1126| 6.75M| size_t literal_len = *tag >> 2; 1127| 6.75M| size_t tag_type = *tag; 1128| 6.75M| bool is_literal; 1129| 6.75M|#if defined(__GCC_ASM_FLAG_OUTPUTS__) && defined(__x86_64__) 1130| | // TODO clang misses the fact that the (c & 3) already correctly 1131| | // sets the zero flag. 1132| 6.75M| asm("and $3, %k[tag_type]\n\t" 1133| 6.75M| : [tag_type] "+r"(tag_type), "=@ccz"(is_literal) 1134| 6.75M| :: "cc"); 1135| |#else 1136| | tag_type &= 3; 1137| | is_literal = (tag_type == 0); 1138| |#endif 1139| | // TODO 1140| | // This is code is subtle. Loading the values first and then cmov has less 1141| | // latency then cmov ip and then load. However clang would move the loads 1142| | // in an optimization phase, volatile prevents this transformation. 1143| | // Note that we have enough slop bytes (64) that the loads are always valid. 1144| 6.75M| size_t tag_literal = 1145| 6.75M| static_cast(ip)[1 + literal_len]; 1146| 6.75M| size_t tag_copy = static_cast(ip)[tag_type]; 1147| 6.75M| *tag = is_literal ? tag_literal : tag_copy; ------------------ | Branch (1147:10): [True: 1.74M, False: 5.01M] ------------------ 1148| 6.75M| const uint8_t* ip_copy = ip + 1 + tag_type; 1149| 6.75M| const uint8_t* ip_literal = ip + 2 + literal_len; 1150| 6.75M| ip = is_literal ? ip_literal : ip_copy; ------------------ | Branch (1150:8): [True: 1.74M, False: 5.01M] ------------------ 1151| 6.75M|#if defined(__GNUC__) && defined(__x86_64__) 1152| | // TODO Clang is "optimizing" zero-extension (a totally free 1153| | // operation) this means that after the cmov of tag, it emits another movzb 1154| | // tag, byte(tag). It really matters as it's on the core chain. This dummy 1155| | // asm, persuades clang to do the zero-extension at the load (it's automatic) 1156| | // removing the expensive movzb. 1157| 6.75M| asm("" ::"r"(tag_copy)); 1158| 6.75M|#endif 1159| 6.75M| return tag_type; 1160| 6.75M|} _ZN6snappy13ExtractOffsetEjm: 1163| 6.75M|inline uint32_t ExtractOffset(uint32_t val, size_t tag_type) { 1164| | // For x86 non-static storage works better. For ARM static storage is better. 1165| | // TODO: Once the array is recognized as a register, improve the 1166| | // readability for x86. 1167| 6.75M|#if defined(__x86_64__) 1168| 6.75M| constexpr uint64_t kExtractMasksCombined = 0x0000FFFF00FF0000ull; 1169| 6.75M| uint16_t result; 1170| 6.75M| memcpy(&result, 1171| 6.75M| reinterpret_cast(&kExtractMasksCombined) + 2 * tag_type, 1172| 6.75M| sizeof(result)); 1173| 6.75M| return val & result; 1174| |#elif defined(__aarch64__) 1175| | constexpr uint64_t kExtractMasksCombined = 0x0000FFFF00FF0000ull; 1176| | return val & static_cast( 1177| | (kExtractMasksCombined >> (tag_type * 16)) & 0xFFFF); 1178| |#else 1179| | static constexpr uint32_t kExtractMasks[4] = {0, 0xFF, 0xFFFF, 0}; 1180| | return val & kExtractMasks[tag_type]; 1181| |#endif 1182| 6.75M|}; snappy.cc:_ZN6snappy12_GLOBAL__N_131Copy64BytesWithPatternExtensionEPcm: 338| 415k|static inline bool Copy64BytesWithPatternExtension(char* dst, size_t offset) { 339| |#if SNAPPY_HAVE_VECTOR_BYTE_SHUFFLE 340| | if (SNAPPY_PREDICT_TRUE(offset <= 16)) { 341| | switch (offset) { 342| | case 0: 343| | return false; 344| | case 1: { 345| | // TODO: Ideally we should memset, move back once the 346| | // codegen issues are fixed. 347| | V128 pattern = V128_DupChar(dst[-1]); 348| | for (int i = 0; i < 4; i++) { 349| | V128_StoreU(reinterpret_cast(dst + 16 * i), pattern); 350| | } 351| | return true; 352| | } 353| | case 2: 354| | case 4: 355| | case 8: 356| | case 16: { 357| | V128 pattern = LoadPattern(dst - offset, offset); 358| | for (int i = 0; i < 4; i++) { 359| | V128_StoreU(reinterpret_cast(dst + 16 * i), pattern); 360| | } 361| | return true; 362| | } 363| | default: { 364| | auto pattern_and_reshuffle_mask = 365| | LoadPatternAndReshuffleMask(dst - offset, offset); 366| | V128 pattern = pattern_and_reshuffle_mask.first; 367| | V128 reshuffle_mask = pattern_and_reshuffle_mask.second; 368| | for (int i = 0; i < 4; i++) { 369| | V128_StoreU(reinterpret_cast(dst + 16 * i), pattern); 370| | pattern = V128_Shuffle(pattern, reshuffle_mask); 371| | } 372| | return true; 373| | } 374| | } 375| | } 376| |#else 377| 415k| if (SNAPPY_PREDICT_TRUE(offset < 16)) { ------------------ | | 95| 415k|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 410k, False: 5.38k] | | ------------------ ------------------ 378| 410k| if (SNAPPY_PREDICT_FALSE(offset == 0)) return false; ------------------ | | 94| 410k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 0, False: 410k] | | ------------------ ------------------ 379| | // Extend the pattern to the first 16 bytes. 380| | // The simpler formulation of `dst[i - offset]` induces undefined behavior. 381| 6.97M| for (int i = 0; i < 16; i++) dst[i] = (dst - offset)[i]; ------------------ | Branch (381:21): [True: 6.56M, False: 410k] ------------------ 382| | // Find a multiple of pattern >= 16. 383| 410k| static std::array pattern_sizes = []() { 384| 410k| std::array res; 385| 410k| for (int i = 1; i < 16; i++) res[i] = (16 / i + 1) * i; 386| 410k| return res; 387| 410k| }(); 388| 410k| offset = pattern_sizes[offset]; 389| 1.64M| for (int i = 1; i < 4; i++) { ------------------ | Branch (389:21): [True: 1.23M, False: 410k] ------------------ 390| 1.23M| std::memcpy(dst + i * 16, dst + i * 16 - offset, 16); 391| 1.23M| } 392| 410k| return true; 393| 410k| } 394| 5.38k|#endif // SNAPPY_HAVE_VECTOR_BYTE_SHUFFLE 395| | 396| | // Very rare. 397| 26.9k| for (int i = 0; i < 4; i++) { ------------------ | Branch (397:19): [True: 21.5k, False: 5.38k] ------------------ 398| 21.5k| std::memcpy(dst + i * 16, dst + i * 16 - offset, 16); 399| 21.5k| } 400| 5.38k| return true; 401| 415k|} snappy.cc:_ZZN6snappy12_GLOBAL__N_131Copy64BytesWithPatternExtensionEPcmENKUlvE_clEv: 383| 1| static std::array pattern_sizes = []() { 384| 1| std::array res; 385| 16| for (int i = 1; i < 16; i++) res[i] = (16 / i + 1) * i; ------------------ | Branch (385:23): [True: 15, False: 1] ------------------ 386| 1| return res; 387| 1| }(); snappy.cc:_ZN6snappyL15ExtractLowBytesERKji: 1008| 80.2k|static inline uint32_t ExtractLowBytes(const uint32_t& v, int n) { 1009| 80.2k| assert(n >= 0); 1010| 0| assert(n <= 4); 1011| |#if SNAPPY_HAVE_BMI2 1012| | return _bzhi_u32(v, 8 * n); 1013| |#else 1014| | // This needs to be wider than uint32_t otherwise `mask << 32` will be 1015| | // undefined. 1016| 0| uint64_t mask = 0xffffffff; 1017| 80.2k| return v & ~(mask << (8 * n)); 1018| 80.2k|#endif 1019| 80.2k|} snappy.cc:_ZN6snappy12_GLOBAL__N_115IncrementalCopyEPKcPcS3_S3_: 407| 6.41k| char* const buf_limit) { 408| |#if SNAPPY_HAVE_VECTOR_BYTE_SHUFFLE 409| | constexpr int big_pattern_size_lower_bound = 16; 410| |#else 411| 6.41k| constexpr int big_pattern_size_lower_bound = 8; 412| 6.41k|#endif 413| | 414| | // Terminology: 415| | // 416| | // slop = buf_limit - op 417| | // pat = op - src 418| | // len = op_limit - op 419| 6.41k| assert(src < op); 420| 0| assert(op < op_limit); 421| 0| assert(op_limit <= buf_limit); 422| | // NOTE: The copy tags use 3 or 6 bits to store the copy length, so len <= 64. 423| 0| assert(op_limit - op <= 64); 424| | // NOTE: In practice the compressor always emits len >= 4, so it is ok to 425| | // assume that to optimize this function, but this is not guaranteed by the 426| | // compression format, so we have to also handle len < 4 in case the input 427| | // does not satisfy these conditions. 428| | 429| 0| size_t pattern_size = op - src; 430| | // The cases are split into different branches to allow the branch predictor, 431| | // FDO, and static prediction hints to work better. For each input we list the 432| | // ratio of invocations that match each condition. 433| | // 434| | // input slop < 16 pat < 8 len > 16 435| | // ------------------------------------------ 436| | // html|html4|cp 0% 1.01% 27.73% 437| | // urls 0% 0.88% 14.79% 438| | // jpg 0% 64.29% 7.14% 439| | // pdf 0% 2.56% 58.06% 440| | // txt[1-4] 0% 0.23% 0.97% 441| | // pb 0% 0.96% 13.88% 442| | // bin 0.01% 22.27% 41.17% 443| | // 444| | // It is very rare that we don't have enough slop for doing block copies. It 445| | // is also rare that we need to expand a pattern. Small patterns are common 446| | // for incompressible formats and for those we are plenty fast already. 447| | // Lengths are normally not greater than 16 but they vary depending on the 448| | // input. In general if we always predict len <= 16 it would be an ok 449| | // prediction. 450| | // 451| | // In order to be fast we want a pattern >= 16 bytes (or 8 bytes in non-SSE) 452| | // and an unrolled loop copying 1x 16 bytes (or 2x 8 bytes in non-SSE) at a 453| | // time. 454| | 455| | // Handle the uncommon case where pattern is less than 16 (or 8 in non-SSE) 456| | // bytes. 457| 6.41k| if (pattern_size < big_pattern_size_lower_bound) { ------------------ | Branch (457:7): [True: 4.86k, False: 1.55k] ------------------ 458| |#if SNAPPY_HAVE_VECTOR_BYTE_SHUFFLE 459| | // Load the first eight bytes into an 128-bit XMM register, then use PSHUFB 460| | // to permute the register's contents in-place into a repeating sequence of 461| | // the first "pattern_size" bytes. 462| | // For example, suppose: 463| | // src == "abc" 464| | // op == op + 3 465| | // After V128_Shuffle(), "pattern" will have five copies of "abc" 466| | // followed by one byte of slop: abcabcabcabcabca. 467| | // 468| | // The non-SSE fallback implementation suffers from store-forwarding stalls 469| | // because its loads and stores partly overlap. By expanding the pattern 470| | // in-place, we avoid the penalty. 471| | 472| | // Typically, the op_limit is the gating factor so try to simplify the loop 473| | // based on that. 474| | if (SNAPPY_PREDICT_TRUE(op_limit <= buf_limit - 15)) { 475| | auto pattern_and_reshuffle_mask = 476| | LoadPatternAndReshuffleMask(src, pattern_size); 477| | V128 pattern = pattern_and_reshuffle_mask.first; 478| | V128 reshuffle_mask = pattern_and_reshuffle_mask.second; 479| | 480| | // There is at least one, and at most four 16-byte blocks. Writing four 481| | // conditionals instead of a loop allows FDO to layout the code with 482| | // respect to the actual probabilities of each length. 483| | // TODO: Replace with loop with trip count hint. 484| | V128_StoreU(reinterpret_cast(op), pattern); 485| | 486| | if (op + 16 < op_limit) { 487| | pattern = V128_Shuffle(pattern, reshuffle_mask); 488| | V128_StoreU(reinterpret_cast(op + 16), pattern); 489| | } 490| | if (op + 32 < op_limit) { 491| | pattern = V128_Shuffle(pattern, reshuffle_mask); 492| | V128_StoreU(reinterpret_cast(op + 32), pattern); 493| | } 494| | if (op + 48 < op_limit) { 495| | pattern = V128_Shuffle(pattern, reshuffle_mask); 496| | V128_StoreU(reinterpret_cast(op + 48), pattern); 497| | } 498| | return op_limit; 499| | } 500| | char* const op_end = buf_limit - 15; 501| | if (SNAPPY_PREDICT_TRUE(op < op_end)) { 502| | auto pattern_and_reshuffle_mask = 503| | LoadPatternAndReshuffleMask(src, pattern_size); 504| | V128 pattern = pattern_and_reshuffle_mask.first; 505| | V128 reshuffle_mask = pattern_and_reshuffle_mask.second; 506| | 507| | // This code path is relatively cold however so we save code size 508| | // by avoiding unrolling and vectorizing. 509| | // 510| | // TODO: Remove pragma when when cold regions don't get 511| | // vectorized or unrolled. 512| |#ifdef __clang__ 513| |#pragma clang loop unroll(disable) 514| |#endif 515| | do { 516| | V128_StoreU(reinterpret_cast(op), pattern); 517| | pattern = V128_Shuffle(pattern, reshuffle_mask); 518| | op += 16; 519| | } while (SNAPPY_PREDICT_TRUE(op < op_end)); 520| | } 521| | return IncrementalCopySlow(op - pattern_size, op, op_limit); 522| |#else // !SNAPPY_HAVE_VECTOR_BYTE_SHUFFLE 523| | // If plenty of buffer space remains, expand the pattern to at least 8 524| | // bytes. The way the following loop is written, we need 8 bytes of buffer 525| | // space if pattern_size >= 4, 11 bytes if pattern_size is 1 or 3, and 10 526| | // bytes if pattern_size is 2. Precisely encoding that is probably not 527| | // worthwhile; instead, invoke the slow path if we cannot write 11 bytes 528| | // (because 11 are required in the worst case). 529| 4.86k| if (SNAPPY_PREDICT_TRUE(op <= buf_limit - 11)) { ------------------ | | 95| 4.86k|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 4.82k, False: 37] | | ------------------ ------------------ 530| 18.4k| while (pattern_size < 8) { ------------------ | Branch (530:14): [True: 13.6k, False: 4.82k] ------------------ 531| 13.6k| UnalignedCopy64(src, op); 532| 13.6k| op += pattern_size; 533| 13.6k| pattern_size *= 2; 534| 13.6k| } 535| 4.82k| if (SNAPPY_PREDICT_TRUE(op >= op_limit)) return op_limit; ------------------ | | 95| 4.82k|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 1.57k, False: 3.24k] | | ------------------ ------------------ 536| 4.82k| } else { 537| 37| return IncrementalCopySlow(src, op, op_limit); 538| 37| } 539| 4.86k|#endif // SNAPPY_HAVE_VECTOR_BYTE_SHUFFLE 540| 4.86k| } 541| 4.80k| assert(pattern_size >= big_pattern_size_lower_bound); 542| 0| constexpr bool use_16bytes_chunk = big_pattern_size_lower_bound == 16; 543| | 544| | // Copy 1x 16 bytes (or 2x 8 bytes in non-SSE) at a time. Because op - src can 545| | // be < 16 in non-SSE, a single UnalignedCopy128 might overwrite data in op. 546| | // UnalignedCopy64 is safe because expanding the pattern to at least 8 bytes 547| | // guarantees that op - src >= 8. 548| | // 549| | // Typically, the op_limit is the gating factor so try to simplify the loop 550| | // based on that. 551| 4.80k| if (SNAPPY_PREDICT_TRUE(op_limit <= buf_limit - 15)) { ------------------ | | 95| 4.80k|#define SNAPPY_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) | | ------------------ | | | Branch (95:32): [True: 4.11k, False: 689] | | ------------------ ------------------ 552| | // There is at least one, and at most four 16-byte blocks. Writing four 553| | // conditionals instead of a loop allows FDO to layout the code with respect 554| | // to the actual probabilities of each length. 555| | // TODO: Replace with loop with trip count hint. 556| 4.11k| ConditionalUnalignedCopy128(src, op); 557| 4.11k| if (op + 16 < op_limit) { ------------------ | Branch (557:9): [True: 2.40k, False: 1.70k] ------------------ 558| 2.40k| ConditionalUnalignedCopy128(src + 16, op + 16); 559| 2.40k| } 560| 4.11k| if (op + 32 < op_limit) { ------------------ | Branch (560:9): [True: 2.10k, False: 2.00k] ------------------ 561| 2.10k| ConditionalUnalignedCopy128(src + 32, op + 32); 562| 2.10k| } 563| 4.11k| if (op + 48 < op_limit) { ------------------ | Branch (563:9): [True: 1.96k, False: 2.15k] ------------------ 564| 1.96k| ConditionalUnalignedCopy128(src + 48, op + 48); 565| 1.96k| } 566| 4.11k| return op_limit; 567| 4.11k| } 568| | 569| | // Fall back to doing as much as we can with the available slop in the 570| | // buffer. This code path is relatively cold however so we save code size by 571| | // avoiding unrolling and vectorizing. 572| | // 573| | // TODO: Remove pragma when when cold regions don't get vectorized 574| | // or unrolled. 575| 4.80k|#ifdef __clang__ 576| 4.80k|#pragma clang loop unroll(disable) 577| 689|#endif 578| 1.22k| for (char* op_end = buf_limit - 16; op < op_end; op += 16, src += 16) { ------------------ | Branch (578:39): [True: 535, False: 689] ------------------ 579| 535| ConditionalUnalignedCopy128(src, op); 580| 535| } 581| 689| if (op >= op_limit) return op_limit; ------------------ | Branch (581:7): [True: 150, False: 539] ------------------ 582| | 583| | // We only take this branch if we didn't have enough slop and we can do a 584| | // single 8 byte copy. 585| 539| if (SNAPPY_PREDICT_FALSE(op <= buf_limit - 8)) { ------------------ | | 94| 539|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 396, False: 143] | | ------------------ ------------------ 586| 396| UnalignedCopy64(src, op); 587| 396| src += 8; 588| 396| op += 8; 589| 396| } 590| 539| return IncrementalCopySlow(src, op, op_limit); 591| 689|} snappy.cc:_ZN6snappy12_GLOBAL__N_115UnalignedCopy64EPKvPv: 205| 36.2k|void UnalignedCopy64(const void* src, void* dst) { 206| 36.2k| char tmp[8]; 207| 36.2k| std::memcpy(tmp, src, 8); 208| 36.2k| std::memcpy(dst, tmp, 8); 209| 36.2k|} snappy.cc:_ZN6snappy12_GLOBAL__N_119IncrementalCopySlowEPKcPcS3_: 242| 576| char* const op_limit) { 243| | // TODO: Remove pragma when LLVM is aware this 244| | // function is only called in cold regions and when cold regions don't get 245| | // vectorized or unrolled. 246| 576|#ifdef __clang__ 247| 576|#pragma clang loop unroll(disable) 248| 576|#endif 249| 1.95k| while (op < op_limit) { ------------------ | Branch (249:10): [True: 1.37k, False: 576] ------------------ 250| 1.37k| *op++ = *src++; 251| 1.37k| } 252| 576| return op_limit; 253| 576|} snappy.cc:_ZN6snappy12_GLOBAL__N_127ConditionalUnalignedCopy128ILb0EEEvPKcPc: 221| 11.1k|inline void ConditionalUnalignedCopy128(const char* src, char* dst) { 222| 11.1k| if (use_16bytes_chunk) { ------------------ | Branch (222:7): [Folded - Ignored] ------------------ 223| 0| UnalignedCopy128(src, dst); 224| 11.1k| } else { 225| 11.1k| UnalignedCopy64(src, dst); 226| 11.1k| UnalignedCopy64(src + 8, dst + 8); 227| 11.1k| } 228| 11.1k|} _ZNK6snappy18SnappyDecompressor3eofEv: 1342| 3.83k| bool eof() const { return eof_; } snappy.cc:_ZN6snappyL18InternalUncompressINS_17SnappyArrayWriterEEEbPNS_6SourceEPT_: 1580| 1.91k|static bool InternalUncompress(Source* r, Writer* writer) { 1581| | // Read the uncompressed length from the front of the compressed input 1582| 1.91k| SnappyDecompressor decompressor(r); 1583| 1.91k| uint32_t uncompressed_len = 0; 1584| 1.91k| if (!decompressor.ReadUncompressedLength(&uncompressed_len)) return false; ------------------ | Branch (1584:7): [True: 0, False: 1.91k] ------------------ 1585| | 1586| 1.91k| return InternalUncompressAllTags(&decompressor, writer, r->Available(), 1587| 1.91k| uncompressed_len); 1588| 1.91k|} snappy.cc:_ZN6snappyL18InternalUncompressINS_28SnappyDecompressionValidatorEEEbPNS_6SourceEPT_: 1580| 1.91k|static bool InternalUncompress(Source* r, Writer* writer) { 1581| | // Read the uncompressed length from the front of the compressed input 1582| 1.91k| SnappyDecompressor decompressor(r); 1583| 1.91k| uint32_t uncompressed_len = 0; 1584| 1.91k| if (!decompressor.ReadUncompressedLength(&uncompressed_len)) return false; ------------------ | Branch (1584:7): [True: 0, False: 1.91k] ------------------ 1585| | 1586| 1.91k| return InternalUncompressAllTags(&decompressor, writer, r->Available(), 1587| 1.91k| uncompressed_len); 1588| 1.91k|} snappy.cc:_ZN6snappyL25InternalUncompressAllTagsINS_28SnappyDecompressionValidatorEEEbPNS_18SnappyDecompressorEPT_jj: 1593| 1.91k| uint32_t uncompressed_len) { 1594| 1.91k| Report("snappy_uncompress", compressed_len, uncompressed_len); 1595| | 1596| 1.91k| writer->SetExpectedLength(uncompressed_len); 1597| | 1598| | // Process the entire input 1599| 1.91k| decompressor->DecompressAllTags(writer); 1600| 1.91k| writer->Flush(); 1601| 1.91k| return (decompressor->eof() && writer->CheckLength()); ------------------ | Branch (1601:11): [True: 1.91k, False: 0] | Branch (1601:34): [True: 1.91k, False: 0] ------------------ 1602| 1.91k|} _ZN6snappy28SnappyDecompressionValidator17SetExpectedLengthEm: 2062| 1.91k| inline void SetExpectedLength(size_t len) { expected_ = len; } _ZN6snappy18SnappyDecompressor17DecompressAllTagsINS_28SnappyDecompressionValidatorEEEvPT_: 1377| 1.91k| DecompressAllTags(Writer* writer) { 1378| 1.91k| const char* ip = ip_; 1379| 1.91k| ResetLimit(ip); 1380| 1.91k| auto op = writer->GetOutputPtr(); 1381| | // We could have put this refill fragment only at the beginning of the loop. 1382| | // However, duplicating it at the end of each branch gives the compiler more 1383| | // scope to optimize the expression based on the local 1384| | // context, which overall increases speed. 1385| 1.91k|#define MAYBE_REFILL() \ 1386| 1.91k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ 1387| 1.91k| ip_ = ip; \ 1388| 1.91k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ 1389| 1.91k| ip = ip_; \ 1390| 1.91k| ResetLimit(ip); \ 1391| 1.91k| } \ 1392| 1.91k| preload = static_cast(*ip) 1393| | 1394| | // At the start of the for loop below the least significant byte of preload 1395| | // contains the tag. 1396| 1.91k| uint32_t preload; 1397| 1.91k| MAYBE_REFILL(); ------------------ | | 1386| 1.91k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 1.91k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 1.91k, False: 0] | | | | ------------------ | | ------------------ | | 1387| 1.91k| ip_ = ip; \ | | 1388| 1.91k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 1.91k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 0, False: 1.91k] | | | | ------------------ | | ------------------ | | 1389| 1.91k| ip = ip_; \ | | 1390| 1.91k| ResetLimit(ip); \ | | 1391| 1.91k| } \ | | 1392| 1.91k| preload = static_cast(*ip) ------------------ 1398| 46.3k| for (;;) { 1399| 46.3k| { 1400| 46.3k| ptrdiff_t op_limit_min_slop; 1401| 46.3k| auto op_base = writer->GetBase(&op_limit_min_slop); 1402| 46.3k| if (op_base) { ------------------ | Branch (1402:13): [True: 46.3k, False: 0] ------------------ 1403| 46.3k| auto res = 1404| 46.3k| DecompressBranchless(reinterpret_cast(ip), 1405| 46.3k| reinterpret_cast(ip_limit_), 1406| 46.3k| op - op_base, op_base, op_limit_min_slop); 1407| 46.3k| ip = reinterpret_cast(res.first); 1408| 46.3k| op = op_base + res.second; 1409| 46.3k| MAYBE_REFILL(); ------------------ | | 1386| 46.3k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 46.3k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 383, False: 45.9k] | | | | ------------------ | | ------------------ | | 1387| 383| ip_ = ip; \ | | 1388| 383| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 383|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 0, False: 383] | | | | ------------------ | | ------------------ | | 1389| 383| ip = ip_; \ | | 1390| 383| ResetLimit(ip); \ | | 1391| 383| } \ | | 1392| 46.3k| preload = static_cast(*ip) ------------------ 1410| 46.3k| } 1411| 46.3k| } 1412| 46.3k| const uint8_t c = static_cast(preload); 1413| 46.3k| ip++; 1414| | 1415| | // Ratio of iterations that have LITERAL vs non-LITERAL for different 1416| | // inputs. 1417| | // 1418| | // input LITERAL NON_LITERAL 1419| | // ----------------------------------- 1420| | // html|html4|cp 23% 77% 1421| | // urls 36% 64% 1422| | // jpg 47% 53% 1423| | // pdf 19% 81% 1424| | // txt[1-4] 25% 75% 1425| | // pb 24% 76% 1426| | // bin 24% 76% 1427| 46.3k| if (SNAPPY_PREDICT_FALSE((c & 0x3) == LITERAL)) { ------------------ | | 94| 46.3k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 32.5k, False: 13.7k] | | ------------------ ------------------ 1428| 32.5k| size_t literal_length = (c >> 2) + 1u; 1429| 32.5k| if (writer->TryFastAppend(ip, ip_limit_ - ip, literal_length, &op)) { ------------------ | Branch (1429:13): [True: 0, False: 32.5k] ------------------ 1430| 0| assert(literal_length < 61); 1431| 0| ip += literal_length; 1432| | // NOTE: There is no MAYBE_REFILL() here, as TryFastAppend() 1433| | // will not return true unless there's already at least five spare 1434| | // bytes in addition to the literal. 1435| 0| preload = static_cast(*ip); 1436| 0| continue; 1437| 0| } 1438| 32.5k| if (SNAPPY_PREDICT_FALSE(literal_length >= 61)) { ------------------ | | 94| 32.5k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 26.6k, False: 5.96k] | | ------------------ ------------------ 1439| | // Long literal. 1440| 26.6k| const size_t literal_length_length = literal_length - 60; 1441| 26.6k| literal_length = 1442| 26.6k| ExtractLowBytes(LittleEndian::Load32(ip), literal_length_length) + 1443| 26.6k| 1; 1444| 26.6k| ip += literal_length_length; 1445| 26.6k| } 1446| | 1447| 32.5k| size_t avail = ip_limit_ - ip; 1448| 32.5k| while (avail < literal_length) { ------------------ | Branch (1448:16): [True: 0, False: 32.5k] ------------------ 1449| 0| if (!writer->Append(ip, avail, &op)) goto exit; ------------------ | Branch (1449:15): [True: 0, False: 0] ------------------ 1450| 0| literal_length -= avail; 1451| 0| reader_->Skip(peeked_); 1452| 0| size_t n; 1453| 0| ip = reader_->Peek(&n); 1454| 0| avail = n; 1455| 0| peeked_ = avail; 1456| 0| if (avail == 0) goto exit; ------------------ | Branch (1456:15): [True: 0, False: 0] ------------------ 1457| 0| ip_limit_ = ip + avail; 1458| 0| ResetLimit(ip); 1459| 0| } 1460| 32.5k| if (!writer->Append(ip, literal_length, &op)) goto exit; ------------------ | Branch (1460:13): [True: 0, False: 32.5k] ------------------ 1461| 32.5k| ip += literal_length; 1462| 32.5k| MAYBE_REFILL(); ------------------ | | 1386| 32.5k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 32.5k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 1.75k, False: 30.8k] | | | | ------------------ | | ------------------ | | 1387| 1.75k| ip_ = ip; \ | | 1388| 1.75k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 1.75k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 1.66k, False: 87] | | | | ------------------ | | ------------------ | | 1389| 1.75k| ip = ip_; \ | | 1390| 87| ResetLimit(ip); \ | | 1391| 87| } \ | | 1392| 32.5k| preload = static_cast(*ip) ------------------ 1463| 30.9k| } else { 1464| 13.7k| if (SNAPPY_PREDICT_FALSE((c & 3) == COPY_4_BYTE_OFFSET)) { ------------------ | | 94| 13.7k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 0, False: 13.7k] | | ------------------ ------------------ 1465| 0| const size_t copy_offset = LittleEndian::Load32(ip); 1466| 0| const size_t length = (c >> 2) + 1; 1467| 0| ip += 4; 1468| | 1469| 0| if (!writer->AppendFromSelf(copy_offset, length, &op)) goto exit; ------------------ | Branch (1469:15): [True: 0, False: 0] ------------------ 1470| 13.7k| } else { 1471| 13.7k| const ptrdiff_t entry = kLengthMinusOffset[c]; 1472| 13.7k| preload = LittleEndian::Load32(ip); 1473| 13.7k| const uint32_t trailer = ExtractLowBytes(preload, c & 3); 1474| 13.7k| const uint32_t length = entry & 0xff; 1475| 13.7k| assert(length > 0); 1476| | 1477| | // copy_offset/256 is encoded in bits 8..10. By just fetching 1478| | // those bits, we get copy_offset (since the bit-field starts at 1479| | // bit 8). 1480| 0| const uint32_t copy_offset = trailer - entry + length; 1481| 13.7k| if (!writer->AppendFromSelf(copy_offset, length, &op)) goto exit; ------------------ | Branch (1481:15): [True: 0, False: 13.7k] ------------------ 1482| | 1483| 13.7k| ip += (c & 3); 1484| | // By using the result of the previous load we reduce the critical 1485| | // dependency chain of ip to 4 cycles. 1486| 13.7k| preload >>= (c & 3) * 8; 1487| 13.7k| if (ip < ip_limit_min_maxtaglen_) continue; ------------------ | Branch (1487:15): [True: 13.1k, False: 541] ------------------ 1488| 13.7k| } 1489| 834| MAYBE_REFILL(); ------------------ | | 1386| 541| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 541|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 541, False: 0] | | | | ------------------ | | ------------------ | | 1387| 541| ip_ = ip; \ | | 1388| 541| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 541|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 248, False: 293] | | | | ------------------ | | ------------------ | | 1389| 541| ip = ip_; \ | | 1390| 293| ResetLimit(ip); \ | | 1391| 293| } \ | | 1392| 541| preload = static_cast(*ip) ------------------ 1490| 834| } 1491| 46.3k| } 1492| 0|#undef MAYBE_REFILL 1493| 1.91k| exit: 1494| 1.91k| writer->SetOutputPtr(op); 1495| 1.91k| } _ZN6snappy28SnappyDecompressionValidator12GetOutputPtrEv: 2063| 1.91k| size_t GetOutputPtr() { return produced_; } _ZN6snappy28SnappyDecompressionValidator7GetBaseEPl: 2064| 46.3k| size_t GetBase(ptrdiff_t* op_limit_min_slop) { 2065| 46.3k| *op_limit_min_slop = std::numeric_limits::max() - kSlopBytes + 1; 2066| 46.3k| return 1; 2067| 46.3k| } _ZN6snappy20DecompressBranchlessImEENSt3__14pairIPKhlEES4_S4_lT_l: 1196| 46.3k| ptrdiff_t op_limit_min_slop) { 1197| | // If deferred_src is invalid point it here. 1198| 46.3k| uint8_t safe_source[64]; 1199| 46.3k| const void* deferred_src; 1200| 46.3k| size_t deferred_length; 1201| 46.3k| ClearDeferred(&deferred_src, &deferred_length, safe_source); 1202| | 1203| | // We unroll the inner loop twice so we need twice the spare room. 1204| 46.3k| op_limit_min_slop -= kSlopBytes; 1205| 46.3k| if (2 * (kSlopBytes + 1) < ip_limit - ip && op < op_limit_min_slop) { ------------------ | Branch (1205:7): [True: 27.2k, False: 19.0k] | Branch (1205:47): [True: 27.2k, False: 0] ------------------ 1206| 27.2k| const uint8_t* const ip_limit_min_slop = ip_limit - 2 * kSlopBytes - 1; 1207| 27.2k| ip++; 1208| | // ip points just past the tag and we are touching at maximum kSlopBytes 1209| | // in an iteration. 1210| 27.2k| size_t tag = ip[-1]; 1211| |#if defined(__clang__) && defined(__aarch64__) 1212| | // Workaround for https://bugs.llvm.org/show_bug.cgi?id=51317 1213| | // when loading 1 byte, clang for aarch64 doesn't realize that it(ldrb) 1214| | // comes with free zero-extension, so clang generates another 1215| | // 'and xn, xm, 0xff' before it use that as the offset. This 'and' is 1216| | // redundant and can be removed by adding this dummy asm, which gives 1217| | // clang a hint that we're doing the zero-extension at the load. 1218| | asm("" ::"r"(tag)); 1219| |#endif 1220| 1.69M| do { 1221| | // The throughput is limited by instructions, unrolling the inner loop 1222| | // twice reduces the amount of instructions checking limits and also 1223| | // leads to reduced mov's. 1224| | 1225| 1.69M| SNAPPY_PREFETCH(ip + 128); ------------------ | | 109| 1.69M|#define SNAPPY_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 3) ------------------ 1226| 5.04M| for (int i = 0; i < 2; i++) { ------------------ | Branch (1226:23): [True: 3.37M, False: 1.66M] ------------------ 1227| 3.37M| const uint8_t* old_ip = ip; 1228| 3.37M| assert(tag == ip[-1]); 1229| | // For literals tag_type = 0, hence we will always obtain 0 from 1230| | // ExtractLowBytes. For literals offset will thus be kLiteralOffset. 1231| 0| ptrdiff_t len_minus_offset = kLengthMinusOffset[tag]; 1232| 3.37M| uint32_t next; 1233| |#if defined(__aarch64__) 1234| | size_t tag_type = AdvanceToNextTagARMOptimized(&ip, &tag); 1235| | // We never need more than 16 bits. Doing a Load16 allows the compiler 1236| | // to elide the masking operation in ExtractOffset. 1237| | next = LittleEndian::Load16(old_ip); 1238| |#else 1239| 3.37M| size_t tag_type = AdvanceToNextTagX86Optimized(&ip, &tag); 1240| 3.37M| next = LittleEndian::Load32(old_ip); 1241| 3.37M|#endif 1242| 3.37M| size_t len = len_minus_offset & 0xFF; 1243| 3.37M| ptrdiff_t extracted = ExtractOffset(next, tag_type); 1244| 3.37M| ptrdiff_t len_min_offset = len_minus_offset - extracted; 1245| 3.37M| if (SNAPPY_PREDICT_FALSE(len_minus_offset > extracted)) { ------------------ | | 94| 3.37M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 442k, False: 2.93M] | | ------------------ ------------------ 1246| 442k| if (SNAPPY_PREDICT_FALSE(len & 0x80)) { ------------------ | | 94| 442k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 26.2k, False: 415k] | | ------------------ ------------------ 1247| | // Exceptional case (long literal or copy 4). 1248| | // Actually doing the copy here is negatively impacting the main 1249| | // loop due to compiler incorrectly allocating a register for 1250| | // this fallback. Hence we just break. 1251| 26.6k| break_loop: 1252| 26.6k| ip = old_ip; 1253| 26.6k| goto exit; 1254| 26.2k| } 1255| | // Only copy-1 or copy-2 tags can get here. 1256| 415k| assert(tag_type == 1 || tag_type == 2); 1257| 0| std::ptrdiff_t delta = (op + deferred_length) + len_min_offset - len; 1258| | // Guard against copies before the buffer start. 1259| | // Execute any deferred MemCopy since we write to dst here. 1260| 415k| MemCopy64(op_base + op, deferred_src, deferred_length); 1261| 415k| op += deferred_length; 1262| 415k| ClearDeferred(&deferred_src, &deferred_length, safe_source); 1263| 415k| if (SNAPPY_PREDICT_FALSE(delta < 0 || ------------------ | | 94| 831k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 182, False: 415k] | | | Branch (94:51): [True: 182, False: 415k] | | | Branch (94:51): [True: 0, False: 415k] | | ------------------ ------------------ 1264| 415k| !Copy64BytesWithPatternExtension( 1265| 415k| op_base + op, len - len_min_offset))) { 1266| 182| goto break_loop; 1267| 182| } 1268| | // We aren't deferring this copy so add length right away. 1269| 415k| op += len; 1270| 415k| continue; 1271| 415k| } 1272| 2.93M| std::ptrdiff_t delta = (op + deferred_length) + len_min_offset - len; 1273| 2.93M| if (SNAPPY_PREDICT_FALSE(delta < 0)) { ------------------ | | 94| 2.93M|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 5.98k, False: 2.93M] | | ------------------ ------------------ 1274| | // Due to the spurious offset in literals have this will trigger 1275| | // at the start of a block when op is still smaller than 256. 1276| 5.98k| if (tag_type != 0) goto break_loop; ------------------ | Branch (1276:15): [True: 257, False: 5.72k] ------------------ 1277| 5.72k| MemCopy64(op_base + op, deferred_src, deferred_length); 1278| 5.72k| op += deferred_length; 1279| 5.72k| DeferMemCopy(&deferred_src, &deferred_length, old_ip, len); 1280| 5.72k| continue; 1281| 5.98k| } 1282| | 1283| | // For copies we need to copy from op_base + delta, for literals 1284| | // we need to copy from ip instead of from the stream. 1285| 2.93M| const void* from = 1286| 2.93M| tag_type ? reinterpret_cast(op_base + delta) : old_ip; ------------------ | Branch (1286:13): [True: 2.09M, False: 840k] ------------------ 1287| 2.93M| MemCopy64(op_base + op, deferred_src, deferred_length); 1288| 2.93M| op += deferred_length; 1289| 2.93M| DeferMemCopy(&deferred_src, &deferred_length, from, len); 1290| 2.93M| } 1291| 1.69M| } while (ip < ip_limit_min_slop && ------------------ | Branch (1291:14): [True: 1.66M, False: 572] ------------------ 1292| 1.66M| (op + deferred_length) < op_limit_min_slop); ------------------ | Branch (1292:14): [True: 1.66M, False: 0] ------------------ 1293| 27.2k| exit: 1294| 27.2k| ip--; 1295| 27.2k| assert(ip <= ip_limit); 1296| 27.2k| } 1297| | // If we deferred a copy then we can perform. If we are up to date then we 1298| | // might not have enough slop bytes and could run past the end. 1299| 46.3k| if (deferred_length) { ------------------ | Branch (1299:7): [True: 21.2k, False: 25.1k] ------------------ 1300| 21.2k| MemCopy64(op_base + op, deferred_src, deferred_length); 1301| 21.2k| op += deferred_length; 1302| 21.2k| ClearDeferred(&deferred_src, &deferred_length, safe_source); 1303| 21.2k| } 1304| 46.3k| return {ip, op}; 1305| 46.3k|} _ZN6snappy31Copy64BytesWithPatternExtensionElm: 1031| 415k|inline bool Copy64BytesWithPatternExtension(ptrdiff_t dst, size_t offset) { 1032| | // TODO: Switch to [[maybe_unused]] when we can assume C++17. 1033| 415k| (void)dst; 1034| 415k| return offset != 0; 1035| 415k|} _ZN6snappy28SnappyDecompressionValidator13TryFastAppendEPKcmmPm: 2078| 32.5k| size_t* produced) { 2079| | // TODO: Switch to [[maybe_unused]] when we can assume C++17. 2080| 32.5k| (void)ip; 2081| 32.5k| (void)available; 2082| 32.5k| (void)length; 2083| 32.5k| (void)produced; 2084| | 2085| 32.5k| return false; 2086| 32.5k| } _ZN6snappy28SnappyDecompressionValidator6AppendEPKcmPm: 2070| 32.5k| inline bool Append(const char* ip, size_t len, size_t* produced) { 2071| | // TODO: Switch to [[maybe_unused]] when we can assume C++17. 2072| 32.5k| (void)ip; 2073| | 2074| 32.5k| *produced += len; 2075| 32.5k| return *produced <= expected_; 2076| 32.5k| } _ZN6snappy28SnappyDecompressionValidator14AppendFromSelfEmmPm: 2087| 13.7k| inline bool AppendFromSelf(size_t offset, size_t len, size_t* produced) { 2088| | // See SnappyArrayWriter::AppendFromSelf for an explanation of 2089| | // the "offset - 1u" trick. 2090| 13.7k| if (*produced <= offset - 1u) return false; ------------------ | Branch (2090:9): [True: 0, False: 13.7k] ------------------ 2091| 13.7k| *produced += len; 2092| 13.7k| return *produced <= expected_; 2093| 13.7k| } _ZN6snappy28SnappyDecompressionValidator12SetOutputPtrEm: 2068| 1.91k| void SetOutputPtr(size_t op) { produced_ = op; } _ZN6snappy28SnappyDecompressionValidator5FlushEv: 2094| 1.91k| inline void Flush() {} _ZNK6snappy28SnappyDecompressionValidator11CheckLengthEv: 2069| 1.91k| inline bool CheckLength() const { return expected_ == produced_; } snappy.cc:_ZN6snappyL25InternalUncompressAllTagsINS_17SnappyArrayWriterEEEbPNS_18SnappyDecompressorEPT_jj: 1593| 1.91k| uint32_t uncompressed_len) { 1594| 1.91k| Report("snappy_uncompress", compressed_len, uncompressed_len); 1595| | 1596| 1.91k| writer->SetExpectedLength(uncompressed_len); 1597| | 1598| | // Process the entire input 1599| 1.91k| decompressor->DecompressAllTags(writer); 1600| 1.91k| writer->Flush(); 1601| 1.91k| return (decompressor->eof() && writer->CheckLength()); ------------------ | Branch (1601:11): [True: 1.91k, False: 0] | Branch (1601:34): [True: 1.91k, False: 0] ------------------ 1602| 1.91k|} _ZN6snappy17SnappyArrayWriter17SetExpectedLengthEm: 1961| 1.91k| inline void SetExpectedLength(size_t len) { 1962| 1.91k| op_limit_ = op_ + len; 1963| | // Prevent pointer from being past the buffer. 1964| 1.91k| op_limit_min_slop_ = op_limit_ - std::min(kSlopBytes - 1, len); 1965| 1.91k| } _ZN6snappy18SnappyDecompressor17DecompressAllTagsINS_17SnappyArrayWriterEEEvPT_: 1377| 1.91k| DecompressAllTags(Writer* writer) { 1378| 1.91k| const char* ip = ip_; 1379| 1.91k| ResetLimit(ip); 1380| 1.91k| auto op = writer->GetOutputPtr(); 1381| | // We could have put this refill fragment only at the beginning of the loop. 1382| | // However, duplicating it at the end of each branch gives the compiler more 1383| | // scope to optimize the expression based on the local 1384| | // context, which overall increases speed. 1385| 1.91k|#define MAYBE_REFILL() \ 1386| 1.91k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ 1387| 1.91k| ip_ = ip; \ 1388| 1.91k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ 1389| 1.91k| ip = ip_; \ 1390| 1.91k| ResetLimit(ip); \ 1391| 1.91k| } \ 1392| 1.91k| preload = static_cast(*ip) 1393| | 1394| | // At the start of the for loop below the least significant byte of preload 1395| | // contains the tag. 1396| 1.91k| uint32_t preload; 1397| 1.91k| MAYBE_REFILL(); ------------------ | | 1386| 1.91k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 1.91k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 1.91k, False: 0] | | | | ------------------ | | ------------------ | | 1387| 1.91k| ip_ = ip; \ | | 1388| 1.91k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 1.91k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 0, False: 1.91k] | | | | ------------------ | | ------------------ | | 1389| 1.91k| ip = ip_; \ | | 1390| 1.91k| ResetLimit(ip); \ | | 1391| 1.91k| } \ | | 1392| 1.91k| preload = static_cast(*ip) ------------------ 1398| 45.8k| for (;;) { 1399| 45.8k| { 1400| 45.8k| ptrdiff_t op_limit_min_slop; 1401| 45.8k| auto op_base = writer->GetBase(&op_limit_min_slop); 1402| 45.8k| if (op_base) { ------------------ | Branch (1402:13): [True: 45.8k, False: 0] ------------------ 1403| 45.8k| auto res = 1404| 45.8k| DecompressBranchless(reinterpret_cast(ip), 1405| 45.8k| reinterpret_cast(ip_limit_), 1406| 45.8k| op - op_base, op_base, op_limit_min_slop); 1407| 45.8k| ip = reinterpret_cast(res.first); 1408| 45.8k| op = op_base + res.second; 1409| 45.8k| MAYBE_REFILL(); ------------------ | | 1386| 45.8k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 45.8k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 383, False: 45.4k] | | | | ------------------ | | ------------------ | | 1387| 383| ip_ = ip; \ | | 1388| 383| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 383|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 0, False: 383] | | | | ------------------ | | ------------------ | | 1389| 383| ip = ip_; \ | | 1390| 383| ResetLimit(ip); \ | | 1391| 383| } \ | | 1392| 45.8k| preload = static_cast(*ip) ------------------ 1410| 45.8k| } 1411| 45.8k| } 1412| 45.8k| const uint8_t c = static_cast(preload); 1413| 45.8k| ip++; 1414| | 1415| | // Ratio of iterations that have LITERAL vs non-LITERAL for different 1416| | // inputs. 1417| | // 1418| | // input LITERAL NON_LITERAL 1419| | // ----------------------------------- 1420| | // html|html4|cp 23% 77% 1421| | // urls 36% 64% 1422| | // jpg 47% 53% 1423| | // pdf 19% 81% 1424| | // txt[1-4] 25% 75% 1425| | // pb 24% 76% 1426| | // bin 24% 76% 1427| 45.8k| if (SNAPPY_PREDICT_FALSE((c & 0x3) == LITERAL)) { ------------------ | | 94| 45.8k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 32.5k, False: 13.2k] | | ------------------ ------------------ 1428| 32.5k| size_t literal_length = (c >> 2) + 1u; 1429| 32.5k| if (writer->TryFastAppend(ip, ip_limit_ - ip, literal_length, &op)) { ------------------ | Branch (1429:13): [True: 3.56k, False: 29.0k] ------------------ 1430| 3.56k| assert(literal_length < 61); 1431| 0| ip += literal_length; 1432| | // NOTE: There is no MAYBE_REFILL() here, as TryFastAppend() 1433| | // will not return true unless there's already at least five spare 1434| | // bytes in addition to the literal. 1435| 3.56k| preload = static_cast(*ip); 1436| 3.56k| continue; 1437| 3.56k| } 1438| 29.0k| if (SNAPPY_PREDICT_FALSE(literal_length >= 61)) { ------------------ | | 94| 29.0k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 26.6k, False: 2.38k] | | ------------------ ------------------ 1439| | // Long literal. 1440| 26.6k| const size_t literal_length_length = literal_length - 60; 1441| 26.6k| literal_length = 1442| 26.6k| ExtractLowBytes(LittleEndian::Load32(ip), literal_length_length) + 1443| 26.6k| 1; 1444| 26.6k| ip += literal_length_length; 1445| 26.6k| } 1446| | 1447| 29.0k| size_t avail = ip_limit_ - ip; 1448| 29.0k| while (avail < literal_length) { ------------------ | Branch (1448:16): [True: 0, False: 29.0k] ------------------ 1449| 0| if (!writer->Append(ip, avail, &op)) goto exit; ------------------ | Branch (1449:15): [True: 0, False: 0] ------------------ 1450| 0| literal_length -= avail; 1451| 0| reader_->Skip(peeked_); 1452| 0| size_t n; 1453| 0| ip = reader_->Peek(&n); 1454| 0| avail = n; 1455| 0| peeked_ = avail; 1456| 0| if (avail == 0) goto exit; ------------------ | Branch (1456:15): [True: 0, False: 0] ------------------ 1457| 0| ip_limit_ = ip + avail; 1458| 0| ResetLimit(ip); 1459| 0| } 1460| 29.0k| if (!writer->Append(ip, literal_length, &op)) goto exit; ------------------ | Branch (1460:13): [True: 0, False: 29.0k] ------------------ 1461| 29.0k| ip += literal_length; 1462| 29.0k| MAYBE_REFILL(); ------------------ | | 1386| 29.0k| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 29.0k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 1.75k, False: 27.2k] | | | | ------------------ | | ------------------ | | 1387| 1.75k| ip_ = ip; \ | | 1388| 1.75k| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 1.75k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 1.66k, False: 87] | | | | ------------------ | | ------------------ | | 1389| 1.75k| ip = ip_; \ | | 1390| 87| ResetLimit(ip); \ | | 1391| 87| } \ | | 1392| 29.0k| preload = static_cast(*ip) ------------------ 1463| 27.3k| } else { 1464| 13.2k| if (SNAPPY_PREDICT_FALSE((c & 3) == COPY_4_BYTE_OFFSET)) { ------------------ | | 94| 13.2k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 0, False: 13.2k] | | ------------------ ------------------ 1465| 0| const size_t copy_offset = LittleEndian::Load32(ip); 1466| 0| const size_t length = (c >> 2) + 1; 1467| 0| ip += 4; 1468| | 1469| 0| if (!writer->AppendFromSelf(copy_offset, length, &op)) goto exit; ------------------ | Branch (1469:15): [True: 0, False: 0] ------------------ 1470| 13.2k| } else { 1471| 13.2k| const ptrdiff_t entry = kLengthMinusOffset[c]; 1472| 13.2k| preload = LittleEndian::Load32(ip); 1473| 13.2k| const uint32_t trailer = ExtractLowBytes(preload, c & 3); 1474| 13.2k| const uint32_t length = entry & 0xff; 1475| 13.2k| assert(length > 0); 1476| | 1477| | // copy_offset/256 is encoded in bits 8..10. By just fetching 1478| | // those bits, we get copy_offset (since the bit-field starts at 1479| | // bit 8). 1480| 0| const uint32_t copy_offset = trailer - entry + length; 1481| 13.2k| if (!writer->AppendFromSelf(copy_offset, length, &op)) goto exit; ------------------ | Branch (1481:15): [True: 0, False: 13.2k] ------------------ 1482| | 1483| 13.2k| ip += (c & 3); 1484| | // By using the result of the previous load we reduce the critical 1485| | // dependency chain of ip to 4 cycles. 1486| 13.2k| preload >>= (c & 3) * 8; 1487| 13.2k| if (ip < ip_limit_min_maxtaglen_) continue; ------------------ | Branch (1487:15): [True: 12.7k, False: 541] ------------------ 1488| 13.2k| } 1489| 834| MAYBE_REFILL(); ------------------ | | 1386| 541| if (SNAPPY_PREDICT_FALSE(ip >= ip_limit_min_maxtaglen_)) { \ | | ------------------ | | | | 94| 541|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 541, False: 0] | | | | ------------------ | | ------------------ | | 1387| 541| ip_ = ip; \ | | 1388| 541| if (SNAPPY_PREDICT_FALSE(!RefillTag())) goto exit; \ | | ------------------ | | | | 94| 541|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | | | ------------------ | | | | | Branch (94:33): [True: 248, False: 293] | | | | ------------------ | | ------------------ | | 1389| 541| ip = ip_; \ | | 1390| 293| ResetLimit(ip); \ | | 1391| 293| } \ | | 1392| 541| preload = static_cast(*ip) ------------------ 1490| 834| } 1491| 45.8k| } 1492| 0|#undef MAYBE_REFILL 1493| 1.91k| exit: 1494| 1.91k| writer->SetOutputPtr(op); 1495| 1.91k| } _ZN6snappy17SnappyArrayWriter12GetOutputPtrEv: 1969| 1.91k| char* GetOutputPtr() { return op_; } _ZN6snappy17SnappyArrayWriter7GetBaseEPl: 1970| 45.8k| char* GetBase(ptrdiff_t* op_limit_min_slop) { 1971| 45.8k| *op_limit_min_slop = op_limit_min_slop_ - base_; 1972| 45.8k| return base_; 1973| 45.8k| } _ZN6snappy17SnappyArrayWriter13TryFastAppendEPKcmmPPc: 1986| 32.5k| char** op_p) { 1987| 32.5k| char* op = *op_p; 1988| 32.5k| const size_t space_left = op_limit_ - op; 1989| 32.5k| if (len <= 16 && available >= 16 + kMaximumTagLength && space_left >= 16) { ------------------ | Branch (1989:9): [True: 5.37k, False: 27.2k] | Branch (1989:22): [True: 3.56k, False: 1.81k] | Branch (1989:61): [True: 3.56k, False: 0] ------------------ 1990| | // Fast path, used for the majority (about 95%) of invocations. 1991| 3.56k| UnalignedCopy128(ip, op); 1992| 3.56k| *op_p = op + len; 1993| 3.56k| return true; 1994| 29.0k| } else { 1995| 29.0k| return false; 1996| 29.0k| } 1997| 32.5k| } _ZN6snappy17SnappyArrayWriter6AppendEPKcmPPc: 1976| 29.0k| inline bool Append(const char* ip, size_t len, char** op_p) { 1977| 29.0k| char* op = *op_p; 1978| 29.0k| const size_t space_left = op_limit_ - op; 1979| 29.0k| if (space_left < len) return false; ------------------ | Branch (1979:9): [True: 0, False: 29.0k] ------------------ 1980| 29.0k| std::memcpy(op, ip, len); 1981| 29.0k| *op_p = op + len; 1982| 29.0k| return true; 1983| 29.0k| } _ZN6snappy17SnappyArrayWriter14AppendFromSelfEmmPPc: 2000| 13.2k| inline bool AppendFromSelf(size_t offset, size_t len, char** op_p) { 2001| 13.2k| assert(len > 0); 2002| 0| char* const op = *op_p; 2003| 13.2k| assert(op >= base_); 2004| 0| char* const op_end = op + len; 2005| | 2006| | // Check if we try to append from before the start of the buffer. 2007| 13.2k| if (SNAPPY_PREDICT_FALSE(static_cast(op - base_) < offset)) ------------------ | | 94| 13.2k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 0, False: 13.2k] | | ------------------ ------------------ 2008| 0| return false; 2009| | 2010| 13.2k| if (SNAPPY_PREDICT_FALSE((kSlopBytes < 64 && len > kSlopBytes) || ------------------ | | 94| 63.6k|#define SNAPPY_PREDICT_FALSE(x) (__builtin_expect(x, 0)) | | ------------------ | | | Branch (94:33): [True: 6.41k, False: 6.86k] | | | Branch (94:51): [Folded - Ignored] | | | Branch (94:51): [True: 0, False: 0] | | | Branch (94:51): [True: 2.69k, False: 10.5k] | | | Branch (94:51): [True: 3.72k, False: 6.86k] | | ------------------ ------------------ 2011| 13.2k| op >= op_limit_min_slop_ || offset < len)) { 2012| 6.41k| if (op_end > op_limit_ || offset == 0) return false; ------------------ | Branch (2012:11): [True: 0, False: 6.41k] | Branch (2012:33): [True: 0, False: 6.41k] ------------------ 2013| 6.41k| *op_p = IncrementalCopy(op - offset, op, op_end, op_limit_); 2014| 6.41k| return true; 2015| 6.41k| } 2016| 6.86k| std::memmove(op, op - offset, kSlopBytes); 2017| 6.86k| *op_p = op_end; 2018| 6.86k| return true; 2019| 13.2k| } _ZN6snappy17SnappyArrayWriter12SetOutputPtrEPc: 1974| 1.91k| void SetOutputPtr(char* op) { op_ = op; } _ZN6snappy17SnappyArrayWriter5FlushEv: 2024| 1.91k| inline void Flush() {} _ZNK6snappy17SnappyArrayWriter11CheckLengthEv: 1967| 1.91k| inline bool CheckLength() const { return op_ == op_limit_; } LLVMFuzzerTestOneInput: 40| 1.91k|extern "C" int LLVMFuzzerTestOneInput(const uint8_t* data, size_t size) { 41| 1.91k| std::string input(reinterpret_cast(data), size); 42| | 43| 1.91k| std::string compressed; 44| 1.91k| size_t compressed_size = 45| 1.91k| snappy::Compress(input.data(), input.size(), &compressed); 46| | 47| 1.91k| (void)compressed_size; // Variable only used in debug builds. 48| 1.91k| assert(compressed_size == compressed.size()); 49| 0| assert(compressed.size() <= snappy::MaxCompressedLength(input.size())); 50| 0| assert(snappy::IsValidCompressedBuffer(compressed.data(), compressed.size())); 51| | 52| 0| std::string uncompressed_after_compress; 53| 1.91k| bool uncompress_succeeded = snappy::Uncompress( 54| 1.91k| compressed.data(), compressed.size(), &uncompressed_after_compress); 55| | 56| 1.91k| (void)uncompress_succeeded; // Variable only used in debug builds. 57| 1.91k| assert(uncompress_succeeded); 58| 0| assert(input == uncompressed_after_compress); 59| 0| return 0; 60| 1.91k|}