llvm/Support/LEB128.h

0001 //===- llvm/Support/LEB128.h - [SU]LEB128 utility functions -----*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file declares some utility functions for encoding SLEB128 and
0010 // ULEB128 values.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_SUPPORT_LEB128_H
0015 #define LLVM_SUPPORT_LEB128_H
0016
0017 #include "llvm/Support/raw_ostream.h"
0018
0019 namespace llvm {
0020
0021 /// Utility function to encode a SLEB128 value to an output stream. Returns
0022 /// the length in bytes of the encoded value.
0023 inline unsigned encodeSLEB128(int64_t Value, raw_ostream &OS,
0024                               unsigned PadTo = 0) {
0025   bool More;
0026   unsigned Count = 0;
0027   do {
0028     uint8_t Byte = Value & 0x7f;
0029     // NOTE: this assumes that this signed shift is an arithmetic right shift.
0030     Value >>= 7;
0031     More = !((((Value == 0 ) && ((Byte & 0x40) == 0)) ||
0032               ((Value == -1) && ((Byte & 0x40) != 0))));
0033     Count++;
0034     if (More || Count < PadTo)
0035       Byte |= 0x80; // Mark this byte to show that more bytes will follow.
0036     OS << char(Byte);
0037   } while (More);
0038
0039   // Pad with 0x80 and emit a terminating byte at the end.
0040   if (Count < PadTo) {
0041     uint8_t PadValue = Value < 0 ? 0x7f : 0x00;
0042     for (; Count < PadTo - 1; ++Count)
0043       OS << char(PadValue | 0x80);
0044     OS << char(PadValue);
0045     Count++;
0046   }
0047   return Count;
0048 }
0049
0050 /// Utility function to encode a SLEB128 value to a buffer. Returns
0051 /// the length in bytes of the encoded value.
0052 inline unsigned encodeSLEB128(int64_t Value, uint8_t *p, unsigned PadTo = 0) {
0053   uint8_t *orig_p = p;
0054   unsigned Count = 0;
0055   bool More;
0056   do {
0057     uint8_t Byte = Value & 0x7f;
0058     // NOTE: this assumes that this signed shift is an arithmetic right shift.
0059     Value >>= 7;
0060     More = !((((Value == 0 ) && ((Byte & 0x40) == 0)) ||
0061               ((Value == -1) && ((Byte & 0x40) != 0))));
0062     Count++;
0063     if (More || Count < PadTo)
0064       Byte |= 0x80; // Mark this byte to show that more bytes will follow.
0065     *p++ = Byte;
0066   } while (More);
0067
0068   // Pad with 0x80 and emit a terminating byte at the end.
0069   if (Count < PadTo) {
0070     uint8_t PadValue = Value < 0 ? 0x7f : 0x00;
0071     for (; Count < PadTo - 1; ++Count)
0072       *p++ = (PadValue | 0x80);
0073     *p++ = PadValue;
0074   }
0075   return (unsigned)(p - orig_p);
0076 }
0077
0078 /// Utility function to encode a ULEB128 value to an output stream. Returns
0079 /// the length in bytes of the encoded value.
0080 inline unsigned encodeULEB128(uint64_t Value, raw_ostream &OS,
0081                               unsigned PadTo = 0) {
0082   unsigned Count = 0;
0083   do {
0084     uint8_t Byte = Value & 0x7f;
0085     Value >>= 7;
0086     Count++;
0087     if (Value != 0 || Count < PadTo)
0088       Byte |= 0x80; // Mark this byte to show that more bytes will follow.
0089     OS << char(Byte);
0090   } while (Value != 0);
0091
0092   // Pad with 0x80 and emit a null byte at the end.
0093   if (Count < PadTo) {
0094     for (; Count < PadTo - 1; ++Count)
0095       OS << '\x80';
0096     OS << '\x00';
0097     Count++;
0098   }
0099   return Count;
0100 }
0101
0102 /// Utility function to encode a ULEB128 value to a buffer. Returns
0103 /// the length in bytes of the encoded value.
0104 inline unsigned encodeULEB128(uint64_t Value, uint8_t *p,
0105                               unsigned PadTo = 0) {
0106   uint8_t *orig_p = p;
0107   unsigned Count = 0;
0108   do {
0109     uint8_t Byte = Value & 0x7f;
0110     Value >>= 7;
0111     Count++;
0112     if (Value != 0 || Count < PadTo)
0113       Byte |= 0x80; // Mark this byte to show that more bytes will follow.
0114     *p++ = Byte;
0115   } while (Value != 0);
0116
0117   // Pad with 0x80 and emit a null byte at the end.
0118   if (Count < PadTo) {
0119     for (; Count < PadTo - 1; ++Count)
0120       *p++ = '\x80';
0121     *p++ = '\x00';
0122   }
0123
0124   return (unsigned)(p - orig_p);
0125 }
0126
0127 /// Utility function to decode a ULEB128 value.
0128 ///
0129 /// If \p error is non-null, it will point to a static error message,
0130 /// if an error occured. It will not be modified on success.
0131 inline uint64_t decodeULEB128(const uint8_t *p, unsigned *n = nullptr,
0132                               const uint8_t *end = nullptr,
0133                               const char **error = nullptr) {
0134   const uint8_t *orig_p = p;
0135   uint64_t Value = 0;
0136   unsigned Shift = 0;
0137   do {
0138     if (LLVM_UNLIKELY(p == end)) {
0139       if (error)
0140         *error = "malformed uleb128, extends past end";
0141       Value = 0;
0142       break;
0143     }
0144     uint64_t Slice = *p & 0x7f;
0145     if (LLVM_UNLIKELY(Shift >= 63) &&
0146         ((Shift == 63 && (Slice << Shift >> Shift) != Slice) ||
0147          (Shift > 63 && Slice != 0))) {
0148       if (error)
0149         *error = "uleb128 too big for uint64";
0150       Value = 0;
0151       break;
0152     }
0153     Value += Slice << Shift;
0154     Shift += 7;
0155   } while (*p++ >= 128);
0156   if (n)
0157     *n = (unsigned)(p - orig_p);
0158   return Value;
0159 }
0160
0161 /// Utility function to decode a SLEB128 value.
0162 ///
0163 /// If \p error is non-null, it will point to a static error message,
0164 /// if an error occured. It will not be modified on success.
0165 inline int64_t decodeSLEB128(const uint8_t *p, unsigned *n = nullptr,
0166                              const uint8_t *end = nullptr,
0167                              const char **error = nullptr) {
0168   const uint8_t *orig_p = p;
0169   int64_t Value = 0;
0170   unsigned Shift = 0;
0171   uint8_t Byte;
0172   do {
0173     if (LLVM_UNLIKELY(p == end)) {
0174       if (error)
0175         *error = "malformed sleb128, extends past end";
0176       if (n)
0177         *n = (unsigned)(p - orig_p);
0178       return 0;
0179     }
0180     Byte = *p;
0181     uint64_t Slice = Byte & 0x7f;
0182     if (LLVM_UNLIKELY(Shift >= 63) &&
0183         ((Shift == 63 && Slice != 0 && Slice != 0x7f) ||
0184          (Shift > 63 && Slice != (Value < 0 ? 0x7f : 0x00)))) {
0185       if (error)
0186         *error = "sleb128 too big for int64";
0187       if (n)
0188         *n = (unsigned)(p - orig_p);
0189       return 0;
0190     }
0191     Value |= Slice << Shift;
0192     Shift += 7;
0193     ++p;
0194   } while (Byte >= 128);
0195   // Sign extend negative numbers if needed.
0196   if (Shift < 64 && (Byte & 0x40))
0197     Value |= UINT64_MAX << Shift;
0198   if (n)
0199     *n = (unsigned)(p - orig_p);
0200   return Value;
0201 }
0202
0203 inline uint64_t decodeULEB128AndInc(const uint8_t *&p, const uint8_t *end,
0204                                     const char **error = nullptr) {
0205   unsigned n;
0206   auto ret = decodeULEB128(p, &n, end, error);
0207   p += n;
0208   return ret;
0209 }
0210
0211 inline int64_t decodeSLEB128AndInc(const uint8_t *&p, const uint8_t *end,
0212                                    const char **error = nullptr) {
0213   unsigned n;
0214   auto ret = decodeSLEB128(p, &n, end, error);
0215   p += n;
0216   return ret;
0217 }
0218
0219 inline uint64_t decodeULEB128AndIncUnsafe(const uint8_t *&p) {
0220   return decodeULEB128AndInc(p, nullptr);
0221 }
0222
0223 /// Utility function to get the size of the ULEB128-encoded value.
0224 extern unsigned getULEB128Size(uint64_t Value);
0225
0226 /// Utility function to get the size of the SLEB128-encoded value.
0227 extern unsigned getSLEB128Size(int64_t Value);
0228
0229 } // namespace llvm
0230
0231 #endif // LLVM_SUPPORT_LEB128_H