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 
19 namespace llvm {
20 
21 /// Utility function to encode a SLEB128 value to an output stream. Returns
22 /// the length in bytes of the encoded value.
23 inline 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.
52 inline 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.
80 inline 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.
104 inline 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.
131 inline 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.
165 inline 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.
204 extern unsigned getULEB128Size(uint64_t Value);
205 
206 /// Utility function to get the size of the SLEB128-encoded value.
207 extern unsigned getSLEB128Size(int64_t Value);
208 
209 } // namespace llvm
210 
211 #endif // LLVM_SUPPORT_LEB128_H
212