stack_trace_compressor.cpp revision 360784 
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