compiler-rt/lib/gwp_asan/stack_trace_compressor.cpp

   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