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-exception 6// 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 there 15// 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 was 31// too large to be represented in a uintptr_t, or if the input buffer finished 32// before the integer was decoded (either case meaning that the `In` does not 33// point to a valid varInt buffer). Otherwise, returns the number of bytes that 34// 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 namespace 68 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 compression 111} // namespace gwp_asan 112