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
11 namespace gwp_asan {
12 namespace compression {
13 namespace {
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.
varIntEncode(uintptr_t Value,uint8_t * Out,size_t OutLen)17 size_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.
varIntDecode(const uint8_t * In,size_t InLen,uintptr_t * Out)35 size_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
zigzagEncode(uintptr_t Value)54 uintptr_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
zigzagDecode(uintptr_t Value)61 uintptr_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
pack(const uintptr_t * Unpacked,size_t UnpackedSize,uint8_t * Packed,size_t PackedMaxSize)69 size_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
unpack(const uint8_t * Packed,size_t PackedSize,uintptr_t * Unpacked,size_t UnpackedMaxSize)87 size_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