1//===- llvm/Support/LEB128.h - [SU]LEB128 utility functions -----*- 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// This file declares some utility functions for encoding SLEB128 and
10// ULEB128 values.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_SUPPORT_LEB128_H
15#define LLVM_SUPPORT_LEB128_H
16
17#include "llvm/Support/raw_ostream.h"
18
19namespace llvm {
20
21/// Utility function to encode a SLEB128 value to an output stream. Returns
22/// the length in bytes of the encoded value.
23inline unsigned encodeSLEB128(int64_t Value, raw_ostream &OS,
24                              unsigned PadTo = 0) {
25  bool More;
26  unsigned Count = 0;
27  do {
28    uint8_t Byte = Value & 0x7f;
29    // NOTE: this assumes that this signed shift is an arithmetic right shift.
30    Value >>= 7;
31    More = !((((Value == 0 ) && ((Byte & 0x40) == 0)) ||
32              ((Value == -1) && ((Byte & 0x40) != 0))));
33    Count++;
34    if (More || Count < PadTo)
35      Byte |= 0x80; // Mark this byte to show that more bytes will follow.
36    OS << char(Byte);
37  } while (More);
38
39  // Pad with 0x80 and emit a terminating byte at the end.
40  if (Count < PadTo) {
41    uint8_t PadValue = Value < 0 ? 0x7f : 0x00;
42    for (; Count < PadTo - 1; ++Count)
43      OS << char(PadValue | 0x80);
44    OS << char(PadValue);
45    Count++;
46  }
47  return Count;
48}
49
50/// Utility function to encode a SLEB128 value to a buffer. Returns
51/// the length in bytes of the encoded value.
52inline unsigned encodeSLEB128(int64_t Value, uint8_t *p, unsigned PadTo = 0) {
53  uint8_t *orig_p = p;
54  unsigned Count = 0;
55  bool More;
56  do {
57    uint8_t Byte = Value & 0x7f;
58    // NOTE: this assumes that this signed shift is an arithmetic right shift.
59    Value >>= 7;
60    More = !((((Value == 0 ) && ((Byte & 0x40) == 0)) ||
61              ((Value == -1) && ((Byte & 0x40) != 0))));
62    Count++;
63    if (More || Count < PadTo)
64      Byte |= 0x80; // Mark this byte to show that more bytes will follow.
65    *p++ = Byte;
66  } while (More);
67
68  // Pad with 0x80 and emit a terminating byte at the end.
69  if (Count < PadTo) {
70    uint8_t PadValue = Value < 0 ? 0x7f : 0x00;
71    for (; Count < PadTo - 1; ++Count)
72      *p++ = (PadValue | 0x80);
73    *p++ = PadValue;
74  }
75  return (unsigned)(p - orig_p);
76}
77
78/// Utility function to encode a ULEB128 value to an output stream. Returns
79/// the length in bytes of the encoded value.
80inline unsigned encodeULEB128(uint64_t Value, raw_ostream &OS,
81                              unsigned PadTo = 0) {
82  unsigned Count = 0;
83  do {
84    uint8_t Byte = Value & 0x7f;
85    Value >>= 7;
86    Count++;
87    if (Value != 0 || Count < PadTo)
88      Byte |= 0x80; // Mark this byte to show that more bytes will follow.
89    OS << char(Byte);
90  } while (Value != 0);
91
92  // Pad with 0x80 and emit a null byte at the end.
93  if (Count < PadTo) {
94    for (; Count < PadTo - 1; ++Count)
95      OS << '\x80';
96    OS << '\x00';
97    Count++;
98  }
99  return Count;
100}
101
102/// Utility function to encode a ULEB128 value to a buffer. Returns
103/// the length in bytes of the encoded value.
104inline unsigned encodeULEB128(uint64_t Value, uint8_t *p,
105                              unsigned PadTo = 0) {
106  uint8_t *orig_p = p;
107  unsigned Count = 0;
108  do {
109    uint8_t Byte = Value & 0x7f;
110    Value >>= 7;
111    Count++;
112    if (Value != 0 || Count < PadTo)
113      Byte |= 0x80; // Mark this byte to show that more bytes will follow.
114    *p++ = Byte;
115  } while (Value != 0);
116
117  // Pad with 0x80 and emit a null byte at the end.
118  if (Count < PadTo) {
119    for (; Count < PadTo - 1; ++Count)
120      *p++ = '\x80';
121    *p++ = '\x00';
122  }
123
124  return (unsigned)(p - orig_p);
125}
126
127/// Utility function to decode a ULEB128 value.
128///
129/// If \p error is non-null, it will point to a static error message,
130/// if an error occured. It will not be modified on success.
131inline uint64_t decodeULEB128(const uint8_t *p, unsigned *n = nullptr,
132                              const uint8_t *end = nullptr,
133                              const char **error = nullptr) {
134  const uint8_t *orig_p = p;
135  uint64_t Value = 0;
136  unsigned Shift = 0;
137  do {
138    if (LLVM_UNLIKELY(p == end)) {
139      if (error)
140        *error = "malformed uleb128, extends past end";
141      Value = 0;
142      break;
143    }
144    uint64_t Slice = *p & 0x7f;
145    if (LLVM_UNLIKELY(Shift >= 63) &&
146        ((Shift == 63 && (Slice << Shift >> Shift) != Slice) ||
147         (Shift > 63 && Slice != 0))) {
148      if (error)
149        *error = "uleb128 too big for uint64";
150      Value = 0;
151      break;
152    }
153    Value += Slice << Shift;
154    Shift += 7;
155  } while (*p++ >= 128);
156  if (n)
157    *n = (unsigned)(p - orig_p);
158  return Value;
159}
160
161/// Utility function to decode a SLEB128 value.
162///
163/// If \p error is non-null, it will point to a static error message,
164/// if an error occured. It will not be modified on success.
165inline int64_t decodeSLEB128(const uint8_t *p, unsigned *n = nullptr,
166                             const uint8_t *end = nullptr,
167                             const char **error = nullptr) {
168  const uint8_t *orig_p = p;
169  int64_t Value = 0;
170  unsigned Shift = 0;
171  uint8_t Byte;
172  do {
173    if (LLVM_UNLIKELY(p == end)) {
174      if (error)
175        *error = "malformed sleb128, extends past end";
176      if (n)
177        *n = (unsigned)(p - orig_p);
178      return 0;
179    }
180    Byte = *p;
181    uint64_t Slice = Byte & 0x7f;
182    if (LLVM_UNLIKELY(Shift >= 63) &&
183        ((Shift == 63 && Slice != 0 && Slice != 0x7f) ||
184         (Shift > 63 && Slice != (Value < 0 ? 0x7f : 0x00)))) {
185      if (error)
186        *error = "sleb128 too big for int64";
187      if (n)
188        *n = (unsigned)(p - orig_p);
189      return 0;
190    }
191    Value |= Slice << Shift;
192    Shift += 7;
193    ++p;
194  } while (Byte >= 128);
195  // Sign extend negative numbers if needed.
196  if (Shift < 64 && (Byte & 0x40))
197    Value |= UINT64_MAX << Shift;
198  if (n)
199    *n = (unsigned)(p - orig_p);
200  return Value;
201}
202
203/// Utility function to get the size of the ULEB128-encoded value.
204extern unsigned getULEB128Size(uint64_t Value);
205
206/// Utility function to get the size of the SLEB128-encoded value.
207extern unsigned getSLEB128Size(int64_t Value);
208
209} // namespace llvm
210
211#endif // LLVM_SUPPORT_LEB128_H
212