112 lines · cpp
1//===-- stack_trace_compressor.cpp ------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "gwp_asan/stack_trace_compressor.h"10 11namespace gwp_asan {12namespace compression {13namespace {14// Encodes `Value` as a variable-length integer to `Out`. Returns zero if there15// was not enough space in the output buffer to write the complete varInt.16// Otherwise returns the length of the encoded integer.17size_t varIntEncode(uintptr_t Value, uint8_t *Out, size_t OutLen) {18 for (size_t i = 0; i < OutLen; ++i) {19 Out[i] = Value & 0x7f;20 Value >>= 7;21 if (!Value)22 return i + 1;23 24 Out[i] |= 0x80;25 }26 27 return 0;28}29 30// Decodes a variable-length integer to `Out`. Returns zero if the integer was31// too large to be represented in a uintptr_t, or if the input buffer finished32// before the integer was decoded (either case meaning that the `In` does not33// point to a valid varInt buffer). Otherwise, returns the number of bytes that34// were used to store the decoded integer.35size_t varIntDecode(const uint8_t *In, size_t InLen, uintptr_t *Out) {36 *Out = 0;37 uint8_t Shift = 0;38 39 for (size_t i = 0; i < InLen; ++i) {40 *Out |= (static_cast<uintptr_t>(In[i]) & 0x7f) << Shift;41 42 if (In[i] < 0x80)43 return i + 1;44 45 Shift += 7;46 47 // Disallow overflowing the range of the output integer.48 if (Shift >= sizeof(uintptr_t) * 8)49 return 0;50 }51 return 0;52}53 54uintptr_t zigzagEncode(uintptr_t Value) {55 uintptr_t Encoded = Value << 1;56 if (static_cast<intptr_t>(Value) >= 0)57 return Encoded;58 return ~Encoded;59}60 61uintptr_t zigzagDecode(uintptr_t Value) {62 uintptr_t Decoded = Value >> 1;63 if (!(Value & 1))64 return Decoded;65 return ~Decoded;66}67} // anonymous namespace68 69size_t pack(const uintptr_t *Unpacked, size_t UnpackedSize, uint8_t *Packed,70 size_t PackedMaxSize) {71 size_t Index = 0;72 for (size_t CurrentDepth = 0; CurrentDepth < UnpackedSize; CurrentDepth++) {73 uintptr_t Diff = Unpacked[CurrentDepth];74 if (CurrentDepth > 0)75 Diff -= Unpacked[CurrentDepth - 1];76 size_t EncodedLength =77 varIntEncode(zigzagEncode(Diff), Packed + Index, PackedMaxSize - Index);78 if (!EncodedLength)79 break;80 81 Index += EncodedLength;82 }83 84 return Index;85}86 87size_t unpack(const uint8_t *Packed, size_t PackedSize, uintptr_t *Unpacked,88 size_t UnpackedMaxSize) {89 size_t CurrentDepth;90 size_t Index = 0;91 for (CurrentDepth = 0; CurrentDepth < UnpackedMaxSize; CurrentDepth++) {92 uintptr_t EncodedDiff;93 size_t DecodedLength =94 varIntDecode(Packed + Index, PackedSize - Index, &EncodedDiff);95 if (!DecodedLength)96 break;97 Index += DecodedLength;98 99 Unpacked[CurrentDepth] = zigzagDecode(EncodedDiff);100 if (CurrentDepth > 0)101 Unpacked[CurrentDepth] += Unpacked[CurrentDepth - 1];102 }103 104 if (Index != PackedSize && CurrentDepth != UnpackedMaxSize)105 return 0;106 107 return CurrentDepth;108}109 110} // namespace compression111} // namespace gwp_asan112