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(Value: zigzagEncode(Value: Diff), Out: Packed + Index, OutLen: 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(In: Packed + Index, InLen: PackedSize - Index, Out: &EncodedDiff);
95 if (!DecodedLength)
96 break;
97 Index += DecodedLength;
98
99 Unpacked[CurrentDepth] = zigzagDecode(Value: 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