BitstreamWriter.h revision 2a5e354f2053fccfa35aa997935aa7100f4c2223 
1//===- BitstreamWriter.h - Low-level bitstream writer interface -*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by Chris Lattner and is distributed under
6// the University of Illinois Open Source License.  See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This header defines the BitstreamWriter class.  This class can be used to
11// write an arbitrary bitstream, regardless of its contents.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef BITSTREAM_WRITER_H
16#define BITSTREAM_WRITER_H
17
18#include "llvm/Bitcode/BitCodes.h"
19#include <vector>
20
21namespace llvm {
22
23class BitstreamWriter {
24  std::vector<unsigned char> &Out;
25
26  /// CurBit - Always between 0 and 31 inclusive, specifies the next bit to use.
27  unsigned CurBit;
28
29  /// CurValue - The current value.  Only bits < CurBit are valid.
30  uint32_t CurValue;
31
32  // CurCodeSize - This is the declared size of code values used for the current
33  // block, in bits.
34  unsigned CurCodeSize;
35
36  /// CurAbbrevs - Abbrevs installed at in this block.
37  std::vector<BitCodeAbbrev*> CurAbbrevs;
38
39  struct Block {
40    unsigned PrevCodeSize;
41    unsigned StartSizeWord;
42    std::vector<BitCodeAbbrev*> PrevAbbrevs;
43    Block(unsigned PCS, unsigned SSW) : PrevCodeSize(PCS), StartSizeWord(SSW) {}
44  };
45
46  /// BlockScope - This tracks the current blocks that we have entered.
47  std::vector<Block> BlockScope;
48
49public:
50  BitstreamWriter(std::vector<unsigned char> &O)
51    : Out(O), CurBit(0), CurValue(0), CurCodeSize(2) {}
52
53  ~BitstreamWriter() {
54    assert(CurBit == 0 && "Unflused data remaining");
55    assert(BlockScope.empty() && CurAbbrevs.empty() && "Block imbalance");
56  }
57  //===--------------------------------------------------------------------===//
58  // Basic Primitives for emitting bits to the stream.
59  //===--------------------------------------------------------------------===//
60
61  void Emit(uint32_t Val, unsigned NumBits) {
62    assert(NumBits <= 32 && "Invalid value size!");
63    assert((Val & ~(~0U >> (32-NumBits))) == 0 && "High bits set!");
64    CurValue |= Val << CurBit;
65    if (CurBit + NumBits < 32) {
66      CurBit += NumBits;
67      return;
68    }
69
70    // Add the current word.
71    unsigned V = CurValue;
72    Out.push_back((unsigned char)(V >>  0));
73    Out.push_back((unsigned char)(V >>  8));
74    Out.push_back((unsigned char)(V >> 16));
75    Out.push_back((unsigned char)(V >> 24));
76
77    if (CurBit)
78      CurValue = Val >> (32-CurBit);
79    else
80      CurValue = 0;
81    CurBit = (CurBit+NumBits) & 31;
82  }
83
84  void Emit64(uint64_t Val, unsigned NumBits) {
85    if (NumBits <= 32)
86      Emit((uint32_t)Val, NumBits);
87    else {
88      Emit((uint32_t)Val, 32);
89      Emit((uint32_t)(Val >> 32), NumBits-32);
90    }
91  }
92
93  void FlushToWord() {
94    if (CurBit) {
95      unsigned V = CurValue;
96      Out.push_back((unsigned char)(V >>  0));
97      Out.push_back((unsigned char)(V >>  8));
98      Out.push_back((unsigned char)(V >> 16));
99      Out.push_back((unsigned char)(V >> 24));
100      CurBit = 0;
101      CurValue = 0;
102    }
103  }
104
105  void EmitVBR(uint32_t Val, unsigned NumBits) {
106    uint32_t Threshold = 1U << (NumBits-1);
107
108    // Emit the bits with VBR encoding, NumBits-1 bits at a time.
109    while (Val >= Threshold) {
110      Emit((Val & ((1 << (NumBits-1))-1)) | (1 << (NumBits-1)), NumBits);
111      Val >>= NumBits-1;
112    }
113
114    Emit(Val, NumBits);
115  }
116
117  void EmitVBR64(uint64_t Val, unsigned NumBits) {
118    if ((uint32_t)Val == Val)
119      return EmitVBR((uint32_t)Val, NumBits);
120
121    uint64_t Threshold = 1U << (NumBits-1);
122
123    // Emit the bits with VBR encoding, NumBits-1 bits at a time.
124    while (Val >= Threshold) {
125      Emit(((uint32_t)Val & ((1 << (NumBits-1))-1)) |
126           (1 << (NumBits-1)), NumBits);
127      Val >>= NumBits-1;
128    }
129
130    Emit((uint32_t)Val, NumBits);
131  }
132
133  /// EmitCode - Emit the specified code.
134  void EmitCode(unsigned Val) {
135    Emit(Val, CurCodeSize);
136  }
137
138  //===--------------------------------------------------------------------===//
139  // Block Manipulation
140  //===--------------------------------------------------------------------===//
141
142  void EnterSubblock(unsigned BlockID, unsigned CodeLen) {
143    // Block header:
144    //    [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen]
145    EmitCode(bitc::ENTER_SUBBLOCK);
146    EmitVBR(BlockID, bitc::BlockIDWidth);
147    EmitVBR(CodeLen, bitc::CodeLenWidth);
148    FlushToWord();
149    BlockScope.push_back(Block(CurCodeSize, Out.size()/4));
150
151    // Delete all abbrevs.
152    for (unsigned i = 0, e = CurAbbrevs.size(); i != e; ++i)
153      delete CurAbbrevs[i];
154
155    BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
156    // Emit a placeholder, which will be replaced when the block is popped.
157    Emit(0, bitc::BlockSizeWidth);
158
159    CurCodeSize = CodeLen;
160  }
161
162  void ExitBlock() {
163    assert(!BlockScope.empty() && "Block scope imbalance!");
164    const Block &B = BlockScope.back();
165
166    // Block tail:
167    //    [END_BLOCK, <align4bytes>]
168    EmitCode(bitc::END_BLOCK);
169    FlushToWord();
170
171    // Compute the size of the block, in words, not counting the size field.
172    unsigned SizeInWords = Out.size()/4-B.StartSizeWord - 1;
173    unsigned ByteNo = B.StartSizeWord*4;
174
175    // Update the block size field in the header of this sub-block.
176    Out[ByteNo++] = (unsigned char)(SizeInWords >>  0);
177    Out[ByteNo++] = (unsigned char)(SizeInWords >>  8);
178    Out[ByteNo++] = (unsigned char)(SizeInWords >> 16);
179    Out[ByteNo++] = (unsigned char)(SizeInWords >> 24);
180
181    // Restore the inner block's code size and abbrev table.
182    CurCodeSize = B.PrevCodeSize;
183    BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
184    BlockScope.pop_back();
185  }
186
187  //===--------------------------------------------------------------------===//
188  // Record Emission
189  //===--------------------------------------------------------------------===//
190
191  /// EmitRecord - Emit the specified record to the stream, using an abbrev if
192  /// we have one to compress the output.
193  void EmitRecord(unsigned Code, SmallVectorImpl<uint64_t> &Vals,
194                  unsigned Abbrev = 0) {
195    if (Abbrev) {
196      unsigned AbbrevNo = Abbrev-bitc::FIRST_ABBREV;
197      assert(AbbrevNo < CurAbbrevs.size() && "Invalid abbrev #!");
198      BitCodeAbbrev *Abbv = CurAbbrevs[AbbrevNo];
199
200      EmitCode(Abbrev);
201
202      // Insert the code into Vals to treat it uniformly.
203      Vals.insert(Vals.begin(), Code);
204
205      unsigned RecordIdx = 0;
206      for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) {
207        assert(RecordIdx < Vals.size() && "Invalid abbrev/record");
208        const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
209        uint64_t RecordVal = Vals[RecordIdx];
210
211        if (Op.isLiteral()) {
212          // If the abbrev specifies the literal value to use, don't emit
213          // anything.
214          assert(RecordVal == Op.getLiteralValue() &&
215                 "Invalid abbrev for record!");
216          ++RecordIdx;
217        } else {
218          // Encode the value as we are commanded.
219          switch (Op.getEncoding()) {
220          default: assert(0 && "Unknown encoding!");
221          case BitCodeAbbrevOp::FixedWidth:
222            Emit64(RecordVal, Op.getEncodingData());
223            ++RecordIdx;
224            break;
225          case BitCodeAbbrevOp::VBR:
226            EmitVBR64(RecordVal, Op.getEncodingData());
227            ++RecordIdx;
228            break;
229          }
230        }
231      }
232      assert(RecordIdx == Vals.size() && "Not all record operands emitted!");
233    } else {
234      // If we don't have an abbrev to use, emit this in its fully unabbreviated
235      // form.
236      EmitCode(bitc::UNABBREV_RECORD);
237      EmitVBR(Code, 6);
238      EmitVBR(Vals.size(), 6);
239      for (unsigned i = 0, e = Vals.size(); i != e; ++i)
240        EmitVBR64(Vals[i], 6);
241    }
242  }
243
244  /// EmitRecord - Emit the specified record to the stream, using an abbrev if
245  /// we have one to compress the output.
246  void EmitRecord(unsigned Code, SmallVectorImpl<unsigned> &Vals,
247                  unsigned Abbrev = 0) {
248    if (Abbrev) {
249      unsigned AbbrevNo = Abbrev-bitc::FIRST_ABBREV;
250      assert(AbbrevNo < CurAbbrevs.size() && "Invalid abbrev #!");
251      BitCodeAbbrev *Abbv = CurAbbrevs[AbbrevNo];
252
253      EmitCode(Abbrev);
254
255      // Insert the code into Vals to treat it uniformly.
256      Vals.insert(Vals.begin(), Code);
257
258      unsigned RecordIdx = 0;
259      for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) {
260        assert(RecordIdx < Vals.size() && "Invalid abbrev/record");
261        const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
262        unsigned RecordVal = Vals[RecordIdx];
263
264        if (Op.isLiteral()) {
265          // If the abbrev specifies the literal value to use, don't emit
266          // anything.
267          assert(RecordVal == Op.getLiteralValue() &&
268                 "Invalid abbrev for record!");
269          ++RecordIdx;
270        } else {
271          // Encode the value as we are commanded.
272          switch (Op.getEncoding()) {
273          default: assert(0 && "Unknown encoding!");
274          case BitCodeAbbrevOp::FixedWidth:
275            Emit(RecordVal, Op.getEncodingData());
276            ++RecordIdx;
277            break;
278          case BitCodeAbbrevOp::VBR:
279            EmitVBR(RecordVal, Op.getEncodingData());
280            ++RecordIdx;
281            break;
282          }
283        }
284      }
285      assert(RecordIdx == Vals.size() && "Not all record operands emitted!");
286    } else {
287      // If we don't have an abbrev to use, emit this in its fully unabbreviated
288      // form.
289      EmitCode(bitc::UNABBREV_RECORD);
290      EmitVBR(Code, 6);
291      EmitVBR(Vals.size(), 6);
292      for (unsigned i = 0, e = Vals.size(); i != e; ++i)
293        EmitVBR(Vals[i], 6);
294    }
295  }
296
297  //===--------------------------------------------------------------------===//
298  // Abbrev Emission
299  //===--------------------------------------------------------------------===//
300
301  /// EmitAbbrev - This emits an abbreviation to the stream.  Note that this
302  /// method takes ownership of the specified abbrev.
303  unsigned EmitAbbrev(BitCodeAbbrev *Abbv) {
304    // Emit the abbreviation as a record.
305    EmitCode(bitc::DEFINE_ABBREV);
306    EmitVBR(Abbv->getNumOperandInfos(), 5);
307    for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) {
308      const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
309      Emit(Op.isLiteral(), 1);
310      if (Op.isLiteral()) {
311        EmitVBR64(Op.getLiteralValue(), 8);
312      } else {
313        Emit(Op.getEncoding(), 3);
314        if (Op.hasEncodingData())
315          EmitVBR64(Op.getEncodingData(), 5);
316      }
317    }
318
319    CurAbbrevs.push_back(Abbv);
320    return CurAbbrevs.size()-1+bitc::FIRST_ABBREV;
321  }
322};
323
324
325} // End llvm namespace
326
327#endif
328