1//===- BitstreamReader.cpp - BitstreamReader implementation ---------------===//
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 "llvm/Bitstream/BitstreamReader.h"
10#include "llvm/ADT/StringRef.h"
11#include <cassert>
12#include <cstring>
13#include <optional>
14#include <string>
15
16using namespace llvm;
17
18//===----------------------------------------------------------------------===//
19// BitstreamCursor implementation
20//===----------------------------------------------------------------------===//
21//
22static Error error(const char *Message) {
23 return createStringError(EC: std::errc::illegal_byte_sequence, Fmt: Message);
24}
25
26Expected<SimpleBitstreamCursor::word_t>
27SimpleBitstreamCursor::readSlow(unsigned NumBits) {
28 if (NumBits > sizeInBits() - std::min(a: BitNo, b: sizeInBits()))
29 return createStringError(EC: std::errc::io_error,
30 Fmt: "Unexpected end of file reading %u bits at bit "
31 "%" PRIu64 " of %" PRIu64,
32 Vals: NumBits, Vals: BitNo, Vals: sizeInBits());
33
34 // Copy the rest of the stream into a zero-padded buffer to read from.
35 uint8_t Buf[2 * sizeof(word_t)] = {};
36 size_t ByteNo = BitNo / 8;
37 std::memcpy(dest: Buf, src: BitcodeBytes.data() + ByteNo,
38 n: std::min(a: sizeof(Buf), b: BitcodeBytes.size() - ByteNo));
39 word_t R =
40 support::endian::readAtBitAlignment<word_t, llvm::endianness::little,
41 support::unaligned>(memory: Buf, startBit: BitNo % 8);
42 BitNo += NumBits;
43 return R & (~word_t(0) >> (BitsInWord - NumBits));
44}
45
46/// Having read the ENTER_SUBBLOCK abbrevid, enter the block.
47Error BitstreamCursor::EnterSubBlock(unsigned BlockID, unsigned *NumWordsP) {
48 // Save the current block's state on BlockScope.
49 BlockScope.push_back(Elt: Block(CurCodeSize));
50 BlockScope.back().PrevAbbrevs.swap(x&: CurAbbrevs);
51
52 // Add the abbrevs specific to this block to the CurAbbrevs list.
53 if (BlockInfo) {
54 if (const BitstreamBlockInfo::BlockInfo *Info =
55 BlockInfo->getBlockInfo(BlockID)) {
56 llvm::append_range(C&: CurAbbrevs, R: Info->Abbrevs);
57 }
58 }
59
60 // Get the codesize of this block.
61 Expected<uint32_t> MaybeVBR = ReadVBR(NumBits: bitc::CodeLenWidth);
62 if (!MaybeVBR)
63 return MaybeVBR.takeError();
64 CurCodeSize = MaybeVBR.get();
65
66 if (CurCodeSize > MaxChunkSize)
67 return llvm::createStringError(
68 EC: std::errc::illegal_byte_sequence,
69 Fmt: "can't read more than %zu at a time, trying to read %u", Vals: +MaxChunkSize,
70 Vals: CurCodeSize);
71
72 SkipToFourByteBoundary();
73 Expected<word_t> MaybeNum = Read(NumBits: bitc::BlockSizeWidth);
74 if (!MaybeNum)
75 return MaybeNum.takeError();
76 word_t NumWords = MaybeNum.get();
77 if (NumWordsP)
78 *NumWordsP = NumWords;
79
80 if (CurCodeSize == 0)
81 return llvm::createStringError(
82 EC: std::errc::illegal_byte_sequence,
83 Fmt: "can't enter sub-block: current code size is 0");
84 if (AtEndOfStream())
85 return llvm::createStringError(
86 EC: std::errc::illegal_byte_sequence,
87 Fmt: "can't enter sub block: already at end of stream");
88
89 return Error::success();
90}
91
92static Expected<uint64_t> readAbbreviatedField(BitstreamCursor &Cursor,
93 const BitCodeAbbrevOp &Op) {
94 assert(!Op.isLiteral() && "Not to be used with literals!");
95
96 // Decode the value as we are commanded.
97 switch (Op.getEncoding()) {
98 case BitCodeAbbrevOp::Array:
99 case BitCodeAbbrevOp::Blob:
100 llvm_unreachable("Should not reach here");
101 case BitCodeAbbrevOp::Fixed:
102 assert((unsigned)Op.getEncodingData() <= Cursor.MaxChunkSize);
103 return Cursor.Read(NumBits: (unsigned)Op.getEncodingData());
104 case BitCodeAbbrevOp::VBR:
105 assert((unsigned)Op.getEncodingData() <= Cursor.MaxChunkSize);
106 return Cursor.ReadVBR64(NumBits: (unsigned)Op.getEncodingData());
107 case BitCodeAbbrevOp::Char6:
108 if (Expected<unsigned> Res = Cursor.Read(NumBits: 6))
109 return BitCodeAbbrevOp::DecodeChar6(V: Res.get());
110 else
111 return Res.takeError();
112 }
113 llvm_unreachable("invalid abbreviation encoding");
114}
115
116/// skipRecord - Read the current record and discard it.
117Expected<unsigned> BitstreamCursor::skipRecord(unsigned AbbrevID) {
118 // Skip unabbreviated records by reading past their entries.
119 if (AbbrevID == bitc::UNABBREV_RECORD) {
120 Expected<uint32_t> MaybeCode = ReadVBR(NumBits: 6);
121 if (!MaybeCode)
122 return MaybeCode.takeError();
123 unsigned Code = MaybeCode.get();
124 Expected<uint32_t> MaybeVBR = ReadVBR(NumBits: 6);
125 if (!MaybeVBR)
126 return MaybeVBR.takeError();
127 unsigned NumElts = MaybeVBR.get();
128 for (unsigned i = 0; i != NumElts; ++i)
129 if (Expected<uint64_t> Res = ReadVBR64(NumBits: 6))
130 ; // Skip!
131 else
132 return Res.takeError();
133 return Code;
134 }
135
136 Expected<const BitCodeAbbrev *> MaybeAbbv = getAbbrev(AbbrevID);
137 if (!MaybeAbbv)
138 return MaybeAbbv.takeError();
139
140 const BitCodeAbbrev *Abbv = MaybeAbbv.get();
141 const BitCodeAbbrevOp &CodeOp = Abbv->getOperandInfo(N: 0);
142 unsigned Code;
143 if (CodeOp.isLiteral())
144 Code = CodeOp.getLiteralValue();
145 else {
146 if (CodeOp.getEncoding() == BitCodeAbbrevOp::Array ||
147 CodeOp.getEncoding() == BitCodeAbbrevOp::Blob)
148 return llvm::createStringError(
149 EC: std::errc::illegal_byte_sequence,
150 Fmt: "Abbreviation starts with an Array or a Blob");
151 Expected<uint64_t> MaybeCode = readAbbreviatedField(Cursor&: *this, Op: CodeOp);
152 if (!MaybeCode)
153 return MaybeCode.takeError();
154 Code = MaybeCode.get();
155 }
156
157 for (unsigned i = 1, e = Abbv->getNumOperandInfos(); i < e; ++i) {
158 const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(N: i);
159 if (Op.isLiteral())
160 continue;
161
162 if (Op.getEncoding() != BitCodeAbbrevOp::Array &&
163 Op.getEncoding() != BitCodeAbbrevOp::Blob) {
164 if (Expected<uint64_t> MaybeField = readAbbreviatedField(Cursor&: *this, Op))
165 continue;
166 else
167 return MaybeField.takeError();
168 }
169
170 if (Op.getEncoding() == BitCodeAbbrevOp::Array) {
171 // Array case. Read the number of elements as a vbr6.
172 Expected<uint32_t> MaybeNum = ReadVBR(NumBits: 6);
173 if (!MaybeNum)
174 return MaybeNum.takeError();
175 unsigned NumElts = MaybeNum.get();
176
177 // Get the element encoding.
178 assert(i+2 == e && "array op not second to last?");
179 const BitCodeAbbrevOp &EltEnc = Abbv->getOperandInfo(N: ++i);
180
181 // Read all the elements.
182 // Decode the value as we are commanded.
183 switch (EltEnc.getEncoding()) {
184 default:
185 return error(Message: "Array element type can't be an Array or a Blob");
186 case BitCodeAbbrevOp::Fixed:
187 assert((unsigned)EltEnc.getEncodingData() <= MaxChunkSize);
188 if (Error Err =
189 JumpToBit(NewBitNo: GetCurrentBitNo() + static_cast<uint64_t>(NumElts) *
190 EltEnc.getEncodingData()))
191 return Err;
192 break;
193 case BitCodeAbbrevOp::VBR:
194 assert((unsigned)EltEnc.getEncodingData() <= MaxChunkSize);
195 for (; NumElts; --NumElts)
196 if (Expected<uint64_t> Res =
197 ReadVBR64(NumBits: (unsigned)EltEnc.getEncodingData()))
198 ; // Skip!
199 else
200 return Res.takeError();
201 break;
202 case BitCodeAbbrevOp::Char6:
203 if (Error Err = JumpToBit(NewBitNo: GetCurrentBitNo() + NumElts * 6))
204 return Err;
205 break;
206 }
207 continue;
208 }
209
210 assert(Op.getEncoding() == BitCodeAbbrevOp::Blob);
211 // Blob case. Read the number of bytes as a vbr6.
212 Expected<uint32_t> MaybeNum = ReadVBR(NumBits: 6);
213 if (!MaybeNum)
214 return MaybeNum.takeError();
215 unsigned NumElts = MaybeNum.get();
216 SkipToFourByteBoundary(); // 32-bit alignment
217
218 // Figure out where the end of this blob will be including tail padding.
219 const size_t NewEnd = GetCurrentBitNo() + alignTo(Value: NumElts, Align: 4) * 8;
220
221 // If this would read off the end of the bitcode file, just set the
222 // record to empty and return.
223 if (!canSkipToPos(pos: NewEnd/8)) {
224 skipToEnd();
225 break;
226 }
227
228 // Skip over the blob.
229 if (Error Err = JumpToBit(NewBitNo: NewEnd))
230 return Err;
231 }
232 return Code;
233}
234
235Expected<unsigned> BitstreamCursor::readRecord(unsigned AbbrevID,
236 SmallVectorImpl<uint64_t> &Vals,
237 StringRef *Blob) {
238 if (AbbrevID == bitc::UNABBREV_RECORD) {
239 Expected<uint32_t> MaybeCode = ReadVBR(NumBits: 6);
240 if (!MaybeCode)
241 return MaybeCode.takeError();
242 uint32_t Code = MaybeCode.get();
243 Expected<uint32_t> MaybeNumElts = ReadVBR(NumBits: 6);
244 if (!MaybeNumElts)
245 return error(
246 Message: ("Failed to read size: " + toString(E: MaybeNumElts.takeError()))
247 .c_str());
248 uint32_t NumElts = MaybeNumElts.get();
249 if (!isSizePlausible(Size: NumElts))
250 return error(Message: "Size is not plausible");
251 Vals.reserve(N: Vals.size() + NumElts);
252
253 for (unsigned i = 0; i != NumElts; ++i)
254 if (Expected<uint64_t> MaybeVal = ReadVBR64(NumBits: 6))
255 Vals.push_back(Elt: MaybeVal.get());
256 else
257 return MaybeVal.takeError();
258 return Code;
259 }
260
261 Expected<const BitCodeAbbrev *> MaybeAbbv = getAbbrev(AbbrevID);
262 if (!MaybeAbbv)
263 return MaybeAbbv.takeError();
264 const BitCodeAbbrev *Abbv = MaybeAbbv.get();
265
266 // Read the record code first.
267 assert(Abbv->getNumOperandInfos() != 0 && "no record code in abbreviation?");
268 const BitCodeAbbrevOp &CodeOp = Abbv->getOperandInfo(N: 0);
269 unsigned Code;
270 if (CodeOp.isLiteral())
271 Code = CodeOp.getLiteralValue();
272 else {
273 if (CodeOp.getEncoding() == BitCodeAbbrevOp::Array ||
274 CodeOp.getEncoding() == BitCodeAbbrevOp::Blob)
275 return error(Message: "Abbreviation starts with an Array or a Blob");
276 if (Expected<uint64_t> MaybeCode = readAbbreviatedField(Cursor&: *this, Op: CodeOp))
277 Code = MaybeCode.get();
278 else
279 return MaybeCode.takeError();
280 }
281
282 for (unsigned i = 1, e = Abbv->getNumOperandInfos(); i != e; ++i) {
283 const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(N: i);
284 if (Op.isLiteral()) {
285 Vals.push_back(Elt: Op.getLiteralValue());
286 continue;
287 }
288
289 if (Op.getEncoding() != BitCodeAbbrevOp::Array &&
290 Op.getEncoding() != BitCodeAbbrevOp::Blob) {
291 if (Expected<uint64_t> MaybeVal = readAbbreviatedField(Cursor&: *this, Op))
292 Vals.push_back(Elt: MaybeVal.get());
293 else
294 return MaybeVal.takeError();
295 continue;
296 }
297
298 if (Op.getEncoding() == BitCodeAbbrevOp::Array) {
299 // Array case. Read the number of elements as a vbr6.
300 Expected<uint32_t> MaybeNumElts = ReadVBR(NumBits: 6);
301 if (!MaybeNumElts)
302 return error(
303 Message: ("Failed to read size: " + toString(E: MaybeNumElts.takeError()))
304 .c_str());
305 uint32_t NumElts = MaybeNumElts.get();
306 if (!isSizePlausible(Size: NumElts))
307 return error(Message: "Size is not plausible");
308 Vals.reserve(N: Vals.size() + NumElts);
309
310 // Get the element encoding.
311 if (i + 2 != e)
312 return error(Message: "Array op not second to last");
313 const BitCodeAbbrevOp &EltEnc = Abbv->getOperandInfo(N: ++i);
314 if (!EltEnc.isEncoding())
315 return error(
316 Message: "Array element type has to be an encoding of a type");
317
318 // Read all the elements.
319 switch (EltEnc.getEncoding()) {
320 default:
321 return error(Message: "Array element type can't be an Array or a Blob");
322 case BitCodeAbbrevOp::Fixed:
323 for (; NumElts; --NumElts)
324 if (Expected<SimpleBitstreamCursor::word_t> MaybeVal =
325 Read(NumBits: (unsigned)EltEnc.getEncodingData()))
326 Vals.push_back(Elt: MaybeVal.get());
327 else
328 return MaybeVal.takeError();
329 break;
330 case BitCodeAbbrevOp::VBR:
331 for (; NumElts; --NumElts)
332 if (Expected<uint64_t> MaybeVal =
333 ReadVBR64(NumBits: (unsigned)EltEnc.getEncodingData()))
334 Vals.push_back(Elt: MaybeVal.get());
335 else
336 return MaybeVal.takeError();
337 break;
338 case BitCodeAbbrevOp::Char6:
339 for (; NumElts; --NumElts)
340 if (Expected<SimpleBitstreamCursor::word_t> MaybeVal = Read(NumBits: 6))
341 Vals.push_back(Elt: BitCodeAbbrevOp::DecodeChar6(V: MaybeVal.get()));
342 else
343 return MaybeVal.takeError();
344 }
345 continue;
346 }
347
348 assert(Op.getEncoding() == BitCodeAbbrevOp::Blob);
349 // Blob case. Read the number of bytes as a vbr6.
350 Expected<uint32_t> MaybeNumElts = ReadVBR(NumBits: 6);
351 if (!MaybeNumElts)
352 return MaybeNumElts.takeError();
353 uint32_t NumElts = MaybeNumElts.get();
354 SkipToFourByteBoundary(); // 32-bit alignment
355
356 // Figure out where the end of this blob will be including tail padding.
357 size_t CurBitPos = GetCurrentBitNo();
358 const size_t NewEnd =
359 CurBitPos + static_cast<uint64_t>(alignTo(Value: NumElts, Align: 4)) * 8;
360
361 // Make sure the bitstream is large enough to contain the blob.
362 if (!canSkipToPos(pos: NewEnd/8))
363 return error(Message: "Blob ends too soon");
364
365 // Otherwise, inform the streamer that we need these bytes in memory. Skip
366 // over tail padding first, in case jumping to NewEnd invalidates the Blob
367 // pointer.
368 if (Error Err = JumpToBit(NewBitNo: NewEnd))
369 return Err;
370 const char *Ptr = (const char *)getPointerToBit(BitNo: CurBitPos, NumBytes: NumElts);
371
372 // If we can return a reference to the data, do so to avoid copying it.
373 if (Blob) {
374 *Blob = StringRef(Ptr, NumElts);
375 } else {
376 // Otherwise, unpack into Vals with zero extension.
377 auto *UPtr = reinterpret_cast<const unsigned char *>(Ptr);
378 Vals.append(in_start: UPtr, in_end: UPtr + NumElts);
379 }
380 }
381
382 return Code;
383}
384
385Error BitstreamCursor::ReadAbbrevRecord() {
386 auto Abbv = std::make_shared<BitCodeAbbrev>();
387 Expected<uint32_t> MaybeNumOpInfo = ReadVBR(NumBits: 5);
388 if (!MaybeNumOpInfo)
389 return MaybeNumOpInfo.takeError();
390 unsigned NumOpInfo = MaybeNumOpInfo.get();
391 for (unsigned i = 0; i != NumOpInfo; ++i) {
392 Expected<word_t> MaybeIsLiteral = Read(NumBits: 1);
393 if (!MaybeIsLiteral)
394 return MaybeIsLiteral.takeError();
395 bool IsLiteral = MaybeIsLiteral.get();
396 if (IsLiteral) {
397 Expected<uint64_t> MaybeOp = ReadVBR64(NumBits: 8);
398 if (!MaybeOp)
399 return MaybeOp.takeError();
400 Abbv->Add(OpInfo: BitCodeAbbrevOp(MaybeOp.get()));
401 continue;
402 }
403
404 Expected<word_t> MaybeEncoding = Read(NumBits: 3);
405 if (!MaybeEncoding)
406 return MaybeEncoding.takeError();
407 if (!BitCodeAbbrevOp::isValidEncoding(E: MaybeEncoding.get()))
408 return error(Message: "Invalid encoding");
409
410 BitCodeAbbrevOp::Encoding E =
411 (BitCodeAbbrevOp::Encoding)MaybeEncoding.get();
412 if (BitCodeAbbrevOp::hasEncodingData(E)) {
413 Expected<uint64_t> MaybeData = ReadVBR64(NumBits: 5);
414 if (!MaybeData)
415 return MaybeData.takeError();
416 uint64_t Data = MaybeData.get();
417
418 // As a special case, handle fixed(0) (i.e., a fixed field with zero bits)
419 // and vbr(0) as a literal zero. This is decoded the same way, and avoids
420 // a slow path in Read() to have to handle reading zero bits.
421 if ((E == BitCodeAbbrevOp::Fixed || E == BitCodeAbbrevOp::VBR) &&
422 Data == 0) {
423 Abbv->Add(OpInfo: BitCodeAbbrevOp(0));
424 continue;
425 }
426
427 if ((E == BitCodeAbbrevOp::Fixed || E == BitCodeAbbrevOp::VBR) &&
428 Data > MaxChunkSize)
429 return error(Message: "Fixed or VBR abbrev record with size > MaxChunkData");
430
431 Abbv->Add(OpInfo: BitCodeAbbrevOp(E, Data));
432 } else
433 Abbv->Add(OpInfo: BitCodeAbbrevOp(E));
434 }
435
436 if (Abbv->getNumOperandInfos() == 0)
437 return error(Message: "Abbrev record with no operands");
438 CurAbbrevs.push_back(x: std::move(Abbv));
439
440 return Error::success();
441}
442
443Expected<std::optional<BitstreamBlockInfo>>
444BitstreamCursor::ReadBlockInfoBlock(bool ReadBlockInfoNames) {
445 if (llvm::Error Err = EnterSubBlock(BlockID: bitc::BLOCKINFO_BLOCK_ID))
446 return Err;
447
448 BitstreamBlockInfo NewBlockInfo;
449
450 SmallVector<uint64_t, 64> Record;
451 BitstreamBlockInfo::BlockInfo *CurBlockInfo = nullptr;
452
453 // Read all the records for this module.
454 while (true) {
455 Expected<BitstreamEntry> MaybeEntry =
456 advanceSkippingSubblocks(Flags: AF_DontAutoprocessAbbrevs);
457 if (!MaybeEntry)
458 return MaybeEntry.takeError();
459 BitstreamEntry Entry = MaybeEntry.get();
460
461 switch (Entry.Kind) {
462 case llvm::BitstreamEntry::SubBlock: // Handled for us already.
463 case llvm::BitstreamEntry::Error:
464 return std::nullopt;
465 case llvm::BitstreamEntry::EndBlock:
466 return std::move(NewBlockInfo);
467 case llvm::BitstreamEntry::Record:
468 // The interesting case.
469 break;
470 }
471
472 // Read abbrev records, associate them with CurBID.
473 if (Entry.ID == bitc::DEFINE_ABBREV) {
474 if (!CurBlockInfo)
475 return std::nullopt;
476 if (Error Err = ReadAbbrevRecord())
477 return Err;
478
479 // ReadAbbrevRecord installs the abbrev in CurAbbrevs. Move it to the
480 // appropriate BlockInfo.
481 CurBlockInfo->Abbrevs.push_back(x: std::move(CurAbbrevs.back()));
482 CurAbbrevs.pop_back();
483 continue;
484 }
485
486 // Read a record.
487 Record.clear();
488 Expected<unsigned> MaybeBlockInfo = readRecord(AbbrevID: Entry.ID, Vals&: Record);
489 if (!MaybeBlockInfo)
490 return MaybeBlockInfo.takeError();
491 switch (MaybeBlockInfo.get()) {
492 default:
493 break; // Default behavior, ignore unknown content.
494 case bitc::BLOCKINFO_CODE_SETBID:
495 if (Record.size() < 1)
496 return std::nullopt;
497 CurBlockInfo = &NewBlockInfo.getOrCreateBlockInfo(BlockID: (unsigned)Record[0]);
498 break;
499 case bitc::BLOCKINFO_CODE_BLOCKNAME: {
500 if (!CurBlockInfo)
501 return std::nullopt;
502 if (!ReadBlockInfoNames)
503 break; // Ignore name.
504 CurBlockInfo->Name = std::string(Record.begin(), Record.end());
505 break;
506 }
507 case bitc::BLOCKINFO_CODE_SETRECORDNAME: {
508 if (!CurBlockInfo)
509 return std::nullopt;
510 if (!ReadBlockInfoNames)
511 break; // Ignore name.
512 CurBlockInfo->RecordNames.emplace_back(
513 args: (unsigned)Record[0], args: std::string(Record.begin() + 1, Record.end()));
514 break;
515 }
516 }
517 }
518}
519