1 //===-- stack_trace_compressor.cpp ------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 #include "gwp_asan/stack_trace_compressor.h"
12 namespace compression {
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;
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) {
39 for (size_t i = 0; i < InLen; ++i) {
40 *Out |= (static_cast<uintptr_t>(In[i]) & 0x7f) << Shift;
47 // Disallow overflowing the range of the output integer.
48 if (Shift >= sizeof(uintptr_t) * 8)
54 uintptr_t zigzagEncode(uintptr_t Value) {
55 uintptr_t Encoded = Value << 1;
56 if (static_cast<intptr_t>(Value) >= 0)
61 uintptr_t zigzagDecode(uintptr_t Value) {
62 uintptr_t Decoded = Value >> 1;
67 } // anonymous namespace
69 size_t pack(const uintptr_t *Unpacked, size_t UnpackedSize, uint8_t *Packed,
70 size_t PackedMaxSize) {
72 for (size_t CurrentDepth = 0; CurrentDepth < UnpackedSize; CurrentDepth++) {
73 uintptr_t Diff = Unpacked[CurrentDepth];
75 Diff -= Unpacked[CurrentDepth - 1];
76 size_t EncodedLength =
77 varIntEncode(zigzagEncode(Diff), Packed + Index, PackedMaxSize - Index);
81 Index += EncodedLength;
87 size_t unpack(const uint8_t *Packed, size_t PackedSize, uintptr_t *Unpacked,
88 size_t UnpackedMaxSize) {
91 for (CurrentDepth = 0; CurrentDepth < UnpackedMaxSize; CurrentDepth++) {
92 uintptr_t EncodedDiff;
93 size_t DecodedLength =
94 varIntDecode(Packed + Index, PackedSize - Index, &EncodedDiff);
97 Index += DecodedLength;
99 Unpacked[CurrentDepth] = zigzagDecode(EncodedDiff);
100 if (CurrentDepth > 0)
101 Unpacked[CurrentDepth] += Unpacked[CurrentDepth - 1];
104 if (Index != PackedSize && CurrentDepth != UnpackedMaxSize)
110 } // namespace compression
111 } // namespace gwp_asan