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.
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.
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 
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 
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 
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 
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