1 //===- BitstreamReader.h - Low-level bitstream reader interface -*- 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 // This header defines the BitstreamReader class. This class can be used to
10 // read an arbitrary bitstream, regardless of its contents.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_BITSTREAM_BITSTREAMREADER_H
15 #define LLVM_BITSTREAM_BITSTREAMREADER_H
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/Bitstream/BitCodes.h"
20 #include "llvm/Support/Endian.h"
21 #include "llvm/Support/ErrorHandling.h"
22 #include "llvm/Support/MathExtras.h"
23 #include "llvm/Support/MemoryBuffer.h"
36 /// This class maintains the abbreviations read from a block info block.
37 class BitstreamBlockInfo
{
39 /// This contains information emitted to BLOCKINFO_BLOCK blocks. These
40 /// describe abbreviations that all blocks of the specified ID inherit.
43 std::vector
<std::shared_ptr
<BitCodeAbbrev
>> Abbrevs
;
45 std::vector
<std::pair
<unsigned, std::string
>> RecordNames
;
49 std::vector
<BlockInfo
> BlockInfoRecords
;
52 /// If there is block info for the specified ID, return it, otherwise return
54 const BlockInfo
*getBlockInfo(unsigned BlockID
) const {
55 // Common case, the most recent entry matches BlockID.
56 if (!BlockInfoRecords
.empty() && BlockInfoRecords
.back().BlockID
== BlockID
)
57 return &BlockInfoRecords
.back();
59 for (unsigned i
= 0, e
= static_cast<unsigned>(BlockInfoRecords
.size());
61 if (BlockInfoRecords
[i
].BlockID
== BlockID
)
62 return &BlockInfoRecords
[i
];
66 BlockInfo
&getOrCreateBlockInfo(unsigned BlockID
) {
67 if (const BlockInfo
*BI
= getBlockInfo(BlockID
))
68 return *const_cast<BlockInfo
*>(BI
);
70 // Otherwise, add a new record.
71 BlockInfoRecords
.emplace_back();
72 BlockInfoRecords
.back().BlockID
= BlockID
;
73 return BlockInfoRecords
.back();
77 /// This represents a position within a bitstream. There may be multiple
78 /// independent cursors reading within one bitstream, each maintaining their
80 class SimpleBitstreamCursor
{
81 ArrayRef
<uint8_t> BitcodeBytes
;
85 /// This is the current data we have pulled from the stream but have not
86 /// returned to the client. This is specifically and intentionally defined to
87 /// follow the word size of the host machine for efficiency. We use word_t in
88 /// places that are aware of this to make it perfectly explicit what is going
90 using word_t
= size_t;
95 /// This is the number of bits in CurWord that are valid. This is always from
96 /// [0...bits_of(size_t)-1] inclusive.
97 unsigned BitsInCurWord
= 0;
100 static const constexpr size_t MaxChunkSize
= sizeof(word_t
) * 8;
102 SimpleBitstreamCursor() = default;
103 explicit SimpleBitstreamCursor(ArrayRef
<uint8_t> BitcodeBytes
)
104 : BitcodeBytes(BitcodeBytes
) {}
105 explicit SimpleBitstreamCursor(StringRef BitcodeBytes
)
106 : BitcodeBytes(arrayRefFromStringRef(BitcodeBytes
)) {}
107 explicit SimpleBitstreamCursor(MemoryBufferRef BitcodeBytes
)
108 : SimpleBitstreamCursor(BitcodeBytes
.getBuffer()) {}
110 bool canSkipToPos(size_t pos
) const {
111 // pos can be skipped to if it is a valid address or one byte past the end.
112 return pos
<= BitcodeBytes
.size();
115 bool AtEndOfStream() {
116 return BitsInCurWord
== 0 && BitcodeBytes
.size() <= NextChar
;
119 /// Return the bit # of the bit we are reading.
120 uint64_t GetCurrentBitNo() const {
121 return NextChar
*CHAR_BIT
- BitsInCurWord
;
124 // Return the byte # of the current bit.
125 uint64_t getCurrentByteNo() const { return GetCurrentBitNo() / 8; }
127 ArrayRef
<uint8_t> getBitcodeBytes() const { return BitcodeBytes
; }
129 /// Reset the stream to the specified bit number.
130 Error
JumpToBit(uint64_t BitNo
) {
131 size_t ByteNo
= size_t(BitNo
/8) & ~(sizeof(word_t
)-1);
132 unsigned WordBitNo
= unsigned(BitNo
& (sizeof(word_t
)*8-1));
133 assert(canSkipToPos(ByteNo
) && "Invalid location");
135 // Move the cursor to the right word.
139 // Skip over any bits that are already consumed.
141 if (Expected
<word_t
> Res
= Read(WordBitNo
))
142 return Error::success();
144 return Res
.takeError();
147 return Error::success();
150 /// Get a pointer into the bitstream at the specified byte offset.
151 const uint8_t *getPointerToByte(uint64_t ByteNo
, uint64_t NumBytes
) {
152 return BitcodeBytes
.data() + ByteNo
;
155 /// Get a pointer into the bitstream at the specified bit offset.
157 /// The bit offset must be on a byte boundary.
158 const uint8_t *getPointerToBit(uint64_t BitNo
, uint64_t NumBytes
) {
159 assert(!(BitNo
% 8) && "Expected bit on byte boundary");
160 return getPointerToByte(BitNo
/ 8, NumBytes
);
163 Error
fillCurWord() {
164 if (NextChar
>= BitcodeBytes
.size())
165 return createStringError(std::errc::io_error
,
166 "Unexpected end of file reading %u of %u bytes",
167 NextChar
, BitcodeBytes
.size());
169 // Read the next word from the stream.
170 const uint8_t *NextCharPtr
= BitcodeBytes
.data() + NextChar
;
172 if (BitcodeBytes
.size() >= NextChar
+ sizeof(word_t
)) {
173 BytesRead
= sizeof(word_t
);
175 support::endian::read
<word_t
, support::little
, support::unaligned
>(
179 BytesRead
= BitcodeBytes
.size() - NextChar
;
181 for (unsigned B
= 0; B
!= BytesRead
; ++B
)
182 CurWord
|= uint64_t(NextCharPtr
[B
]) << (B
* 8);
184 NextChar
+= BytesRead
;
185 BitsInCurWord
= BytesRead
* 8;
186 return Error::success();
189 Expected
<word_t
> Read(unsigned NumBits
) {
190 static const unsigned BitsInWord
= MaxChunkSize
;
192 assert(NumBits
&& NumBits
<= BitsInWord
&&
193 "Cannot return zero or more than BitsInWord bits!");
195 static const unsigned Mask
= sizeof(word_t
) > 4 ? 0x3f : 0x1f;
197 // If the field is fully contained by CurWord, return it quickly.
198 if (BitsInCurWord
>= NumBits
) {
199 word_t R
= CurWord
& (~word_t(0) >> (BitsInWord
- NumBits
));
201 // Use a mask to avoid undefined behavior.
202 CurWord
>>= (NumBits
& Mask
);
204 BitsInCurWord
-= NumBits
;
208 word_t R
= BitsInCurWord
? CurWord
: 0;
209 unsigned BitsLeft
= NumBits
- BitsInCurWord
;
211 if (Error fillResult
= fillCurWord())
212 return std::move(fillResult
);
214 // If we run out of data, abort.
215 if (BitsLeft
> BitsInCurWord
)
216 return createStringError(std::errc::io_error
,
217 "Unexpected end of file reading %u of %u bits",
218 BitsInCurWord
, BitsLeft
);
220 word_t R2
= CurWord
& (~word_t(0) >> (BitsInWord
- BitsLeft
));
222 // Use a mask to avoid undefined behavior.
223 CurWord
>>= (BitsLeft
& Mask
);
225 BitsInCurWord
-= BitsLeft
;
227 R
|= R2
<< (NumBits
- BitsLeft
);
232 Expected
<uint32_t> ReadVBR(unsigned NumBits
) {
233 Expected
<unsigned> MaybeRead
= Read(NumBits
);
236 uint32_t Piece
= MaybeRead
.get();
238 if ((Piece
& (1U << (NumBits
-1))) == 0)
242 unsigned NextBit
= 0;
244 Result
|= (Piece
& ((1U << (NumBits
-1))-1)) << NextBit
;
246 if ((Piece
& (1U << (NumBits
-1))) == 0)
249 NextBit
+= NumBits
-1;
250 MaybeRead
= Read(NumBits
);
253 Piece
= MaybeRead
.get();
257 // Read a VBR that may have a value up to 64-bits in size. The chunk size of
258 // the VBR must still be <= 32 bits though.
259 Expected
<uint64_t> ReadVBR64(unsigned NumBits
) {
260 Expected
<uint64_t> MaybeRead
= Read(NumBits
);
263 uint32_t Piece
= MaybeRead
.get();
265 if ((Piece
& (1U << (NumBits
-1))) == 0)
266 return uint64_t(Piece
);
269 unsigned NextBit
= 0;
271 Result
|= uint64_t(Piece
& ((1U << (NumBits
-1))-1)) << NextBit
;
273 if ((Piece
& (1U << (NumBits
-1))) == 0)
276 NextBit
+= NumBits
-1;
277 MaybeRead
= Read(NumBits
);
280 Piece
= MaybeRead
.get();
284 void SkipToFourByteBoundary() {
285 // If word_t is 64-bits and if we've read less than 32 bits, just dump
286 // the bits we have up to the next 32-bit boundary.
287 if (sizeof(word_t
) > 4 &&
288 BitsInCurWord
>= 32) {
289 CurWord
>>= BitsInCurWord
-32;
297 /// Return the size of the stream in bytes.
298 size_t SizeInBytes() const { return BitcodeBytes
.size(); }
300 /// Skip to the end of the file.
301 void skipToEnd() { NextChar
= BitcodeBytes
.size(); }
304 /// When advancing through a bitstream cursor, each advance can discover a few
305 /// different kinds of entries:
306 struct BitstreamEntry
{
308 Error
, // Malformed bitcode was found.
309 EndBlock
, // We've reached the end of the current block, (or the end of the
310 // file, which is treated like a series of EndBlock records.
311 SubBlock
, // This is the start of a new subblock of a specific ID.
312 Record
// This is a record with a specific AbbrevID.
317 static BitstreamEntry
getError() {
318 BitstreamEntry E
; E
.Kind
= Error
; return E
;
321 static BitstreamEntry
getEndBlock() {
322 BitstreamEntry E
; E
.Kind
= EndBlock
; return E
;
325 static BitstreamEntry
getSubBlock(unsigned ID
) {
326 BitstreamEntry E
; E
.Kind
= SubBlock
; E
.ID
= ID
; return E
;
329 static BitstreamEntry
getRecord(unsigned AbbrevID
) {
330 BitstreamEntry E
; E
.Kind
= Record
; E
.ID
= AbbrevID
; return E
;
334 /// This represents a position within a bitcode file, implemented on top of a
335 /// SimpleBitstreamCursor.
337 /// Unlike iterators, BitstreamCursors are heavy-weight objects that should not
338 /// be passed by value.
339 class BitstreamCursor
: SimpleBitstreamCursor
{
340 // This is the declared size of code values used for the current block, in
342 unsigned CurCodeSize
= 2;
344 /// Abbrevs installed at in this block.
345 std::vector
<std::shared_ptr
<BitCodeAbbrev
>> CurAbbrevs
;
348 unsigned PrevCodeSize
;
349 std::vector
<std::shared_ptr
<BitCodeAbbrev
>> PrevAbbrevs
;
351 explicit Block(unsigned PCS
) : PrevCodeSize(PCS
) {}
354 /// This tracks the codesize of parent blocks.
355 SmallVector
<Block
, 8> BlockScope
;
357 BitstreamBlockInfo
*BlockInfo
= nullptr;
360 static const size_t MaxChunkSize
= sizeof(word_t
) * 8;
362 BitstreamCursor() = default;
363 explicit BitstreamCursor(ArrayRef
<uint8_t> BitcodeBytes
)
364 : SimpleBitstreamCursor(BitcodeBytes
) {}
365 explicit BitstreamCursor(StringRef BitcodeBytes
)
366 : SimpleBitstreamCursor(BitcodeBytes
) {}
367 explicit BitstreamCursor(MemoryBufferRef BitcodeBytes
)
368 : SimpleBitstreamCursor(BitcodeBytes
) {}
370 using SimpleBitstreamCursor::AtEndOfStream
;
371 using SimpleBitstreamCursor::canSkipToPos
;
372 using SimpleBitstreamCursor::fillCurWord
;
373 using SimpleBitstreamCursor::getBitcodeBytes
;
374 using SimpleBitstreamCursor::GetCurrentBitNo
;
375 using SimpleBitstreamCursor::getCurrentByteNo
;
376 using SimpleBitstreamCursor::getPointerToByte
;
377 using SimpleBitstreamCursor::JumpToBit
;
378 using SimpleBitstreamCursor::Read
;
379 using SimpleBitstreamCursor::ReadVBR
;
380 using SimpleBitstreamCursor::ReadVBR64
;
381 using SimpleBitstreamCursor::SizeInBytes
;
382 using SimpleBitstreamCursor::skipToEnd
;
384 /// Return the number of bits used to encode an abbrev #.
385 unsigned getAbbrevIDWidth() const { return CurCodeSize
; }
387 /// Flags that modify the behavior of advance().
389 /// If this flag is used, the advance() method does not automatically pop
390 /// the block scope when the end of a block is reached.
391 AF_DontPopBlockAtEnd
= 1,
393 /// If this flag is used, abbrev entries are returned just like normal
395 AF_DontAutoprocessAbbrevs
= 2
398 /// Advance the current bitstream, returning the next entry in the stream.
399 Expected
<BitstreamEntry
> advance(unsigned Flags
= 0) {
402 return BitstreamEntry::getError();
404 Expected
<unsigned> MaybeCode
= ReadCode();
406 return MaybeCode
.takeError();
407 unsigned Code
= MaybeCode
.get();
409 if (Code
== bitc::END_BLOCK
) {
410 // Pop the end of the block unless Flags tells us not to.
411 if (!(Flags
& AF_DontPopBlockAtEnd
) && ReadBlockEnd())
412 return BitstreamEntry::getError();
413 return BitstreamEntry::getEndBlock();
416 if (Code
== bitc::ENTER_SUBBLOCK
) {
417 if (Expected
<unsigned> MaybeSubBlock
= ReadSubBlockID())
418 return BitstreamEntry::getSubBlock(MaybeSubBlock
.get());
420 return MaybeSubBlock
.takeError();
423 if (Code
== bitc::DEFINE_ABBREV
&&
424 !(Flags
& AF_DontAutoprocessAbbrevs
)) {
425 // We read and accumulate abbrev's, the client can't do anything with
427 if (Error Err
= ReadAbbrevRecord())
428 return std::move(Err
);
432 return BitstreamEntry::getRecord(Code
);
436 /// This is a convenience function for clients that don't expect any
437 /// subblocks. This just skips over them automatically.
438 Expected
<BitstreamEntry
> advanceSkippingSubblocks(unsigned Flags
= 0) {
440 // If we found a normal entry, return it.
441 Expected
<BitstreamEntry
> MaybeEntry
= advance(Flags
);
444 BitstreamEntry Entry
= MaybeEntry
.get();
446 if (Entry
.Kind
!= BitstreamEntry::SubBlock
)
449 // If we found a sub-block, just skip over it and check the next entry.
450 if (Error Err
= SkipBlock())
451 return std::move(Err
);
455 Expected
<unsigned> ReadCode() { return Read(CurCodeSize
); }
458 // [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen]
460 /// Having read the ENTER_SUBBLOCK code, read the BlockID for the block.
461 Expected
<unsigned> ReadSubBlockID() { return ReadVBR(bitc::BlockIDWidth
); }
463 /// Having read the ENTER_SUBBLOCK abbrevid and a BlockID, skip over the body
466 // Read and ignore the codelen value.
467 if (Expected
<uint32_t> Res
= ReadVBR(bitc::CodeLenWidth
))
468 ; // Since we are skipping this block, we don't care what code widths are
469 // used inside of it.
471 return Res
.takeError();
473 SkipToFourByteBoundary();
474 Expected
<unsigned> MaybeNum
= Read(bitc::BlockSizeWidth
);
476 return MaybeNum
.takeError();
477 size_t NumFourBytes
= MaybeNum
.get();
479 // Check that the block wasn't partially defined, and that the offset isn't
481 size_t SkipTo
= GetCurrentBitNo() + NumFourBytes
* 4 * 8;
483 return createStringError(std::errc::illegal_byte_sequence
,
484 "can't skip block: already at end of stream");
485 if (!canSkipToPos(SkipTo
/ 8))
486 return createStringError(std::errc::illegal_byte_sequence
,
487 "can't skip to bit %zu from %" PRIu64
, SkipTo
,
490 if (Error Res
= JumpToBit(SkipTo
))
493 return Error::success();
496 /// Having read the ENTER_SUBBLOCK abbrevid, and enter the block.
497 Error
EnterSubBlock(unsigned BlockID
, unsigned *NumWordsP
= nullptr);
499 bool ReadBlockEnd() {
500 if (BlockScope
.empty()) return true;
503 // [END_BLOCK, <align4bytes>]
504 SkipToFourByteBoundary();
511 void popBlockScope() {
512 CurCodeSize
= BlockScope
.back().PrevCodeSize
;
514 CurAbbrevs
= std::move(BlockScope
.back().PrevAbbrevs
);
515 BlockScope
.pop_back();
518 //===--------------------------------------------------------------------===//
520 //===--------------------------------------------------------------------===//
523 /// Return the abbreviation for the specified AbbrevId.
524 const BitCodeAbbrev
*getAbbrev(unsigned AbbrevID
) {
525 unsigned AbbrevNo
= AbbrevID
- bitc::FIRST_APPLICATION_ABBREV
;
526 if (AbbrevNo
>= CurAbbrevs
.size())
527 report_fatal_error("Invalid abbrev number");
528 return CurAbbrevs
[AbbrevNo
].get();
531 /// Read the current record and discard it, returning the code for the record.
532 Expected
<unsigned> skipRecord(unsigned AbbrevID
);
534 Expected
<unsigned> readRecord(unsigned AbbrevID
,
535 SmallVectorImpl
<uint64_t> &Vals
,
536 StringRef
*Blob
= nullptr);
538 //===--------------------------------------------------------------------===//
540 //===--------------------------------------------------------------------===//
541 Error
ReadAbbrevRecord();
543 /// Read and return a block info block from the bitstream. If an error was
544 /// encountered, return None.
546 /// \param ReadBlockInfoNames Whether to read block/record name information in
547 /// the BlockInfo block. Only llvm-bcanalyzer uses this.
548 Expected
<Optional
<BitstreamBlockInfo
>>
549 ReadBlockInfoBlock(bool ReadBlockInfoNames
= false);
551 /// Set the block info to be used by this BitstreamCursor to interpret
552 /// abbreviated records.
553 void setBlockInfo(BitstreamBlockInfo
*BI
) { BlockInfo
= BI
; }
556 } // end llvm namespace
558 #endif // LLVM_BITSTREAM_BITSTREAMREADER_H