BitstreamWriter.h revision a0c96a068ca7027644b5f1972f9c388fa542d278 
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 "llvm/ADT/SmallVector.h"
20#include "llvm/Support/DataTypes.h"
21#include <cassert>
22#include <vector>
23
24namespace llvm {
25
26class BitstreamWriter {
27  std::vector<unsigned char> &Out;
28
29  /// CurBit - Always between 0 and 31 inclusive, specifies the next bit to use.
30  unsigned CurBit;
31
32  /// CurValue - The current value.  Only bits < CurBit are valid.
33  uint32_t CurValue;
34
35  // CurCodeSize - This is the declared size of code values used for the current
36  // block, in bits.
37  unsigned CurCodeSize;
38
39  struct Block {
40    unsigned PrevCodeSize;
41    unsigned StartSizeWord;
42    Block(unsigned PCS, unsigned SSW) : PrevCodeSize(PCS), StartSizeWord(SSW) {}
43  };
44
45  /// BlockScope - This tracks the current blocks that we have entered.
46  std::vector<Block> BlockScope;
47public:
48  BitstreamWriter(std::vector<unsigned char> &O)
49    : Out(O), CurBit(0), CurValue(0), CurCodeSize(2) {}
50
51  ~BitstreamWriter() {
52    assert(CurBit == 0 && "Unflused data remaining");
53    assert(BlockScope.empty() && "Block imbalance");
54  }
55  //===--------------------------------------------------------------------===//
56  // Basic Primitives for emitting bits to the stream.
57  //===--------------------------------------------------------------------===//
58
59  void Emit(uint32_t Val, unsigned NumBits) {
60    assert(NumBits <= 32 && "Invalid value size!");
61    assert((Val & ~(~0U >> (32-NumBits))) == 0 && "High bits set!");
62    CurValue |= Val << CurBit;
63    if (CurBit + NumBits < 32) {
64      CurBit += NumBits;
65      return;
66    }
67
68    // Add the current word.
69    unsigned V = CurValue;
70    Out.push_back((unsigned char)(V >>  0));
71    Out.push_back((unsigned char)(V >>  8));
72    Out.push_back((unsigned char)(V >> 16));
73    Out.push_back((unsigned char)(V >> 24));
74
75    if (CurBit)
76      CurValue = Val >> (32-CurBit);
77    else
78      CurValue = 0;
79    CurBit = (CurBit+NumBits) & 31;
80  }
81
82  void Emit64(uint64_t Val, unsigned NumBits) {
83    if (NumBits <= 32)
84      Emit((uint32_t)Val, NumBits);
85    else {
86      Emit((uint32_t)Val, 32);
87      Emit((uint32_t)(Val >> 32), NumBits-32);
88    }
89  }
90
91  void FlushToWord() {
92    if (CurBit) {
93      unsigned V = CurValue;
94      Out.push_back((unsigned char)(V >>  0));
95      Out.push_back((unsigned char)(V >>  8));
96      Out.push_back((unsigned char)(V >> 16));
97      Out.push_back((unsigned char)(V >> 24));
98      CurBit = 0;
99      CurValue = 0;
100    }
101  }
102
103  void EmitVBR(uint32_t Val, unsigned NumBits) {
104    uint32_t Threshold = 1U << (NumBits-1);
105
106    // Emit the bits with VBR encoding, NumBits-1 bits at a time.
107    while (Val >= Threshold) {
108      Emit((Val & ((1 << (NumBits-1))-1)) | (1 << (NumBits-1)), NumBits);
109      Val >>= NumBits-1;
110    }
111
112    Emit(Val, NumBits);
113  }
114
115  void EmitVBR64(uint64_t Val, unsigned NumBits) {
116    if ((uint32_t)Val == Val)
117      return EmitVBR((uint32_t)Val, NumBits);
118
119    uint64_t Threshold = 1U << (NumBits-1);
120
121    // Emit the bits with VBR encoding, NumBits-1 bits at a time.
122    while (Val >= Threshold) {
123      Emit(((uint32_t)Val & ((1 << (NumBits-1))-1)) |
124           (1 << (NumBits-1)), NumBits);
125      Val >>= NumBits-1;
126    }
127
128    Emit((uint32_t)Val, NumBits);
129  }
130
131  /// EmitCode - Emit the specified code.
132  void EmitCode(unsigned Val) {
133    Emit(Val, CurCodeSize);
134  }
135
136  //===--------------------------------------------------------------------===//
137  // Block Manipulation
138  //===--------------------------------------------------------------------===//
139
140  void EnterSubblock(unsigned BlockID, unsigned CodeLen) {
141    // Block header:
142    //    [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen]
143    EmitCode(bitc::ENTER_SUBBLOCK);
144    EmitVBR(BlockID, bitc::BlockIDWidth);
145    EmitVBR(CodeLen, bitc::CodeLenWidth);
146    FlushToWord();
147    BlockScope.push_back(Block(CurCodeSize, Out.size()/4));
148    // Emit a placeholder, which will be replaced when the block is popped.
149    Emit(0, bitc::BlockSizeWidth);
150
151    CurCodeSize = CodeLen;
152  }
153
154  void ExitBlock() {
155    assert(!BlockScope.empty() && "Block scope imbalance!");
156    Block B = BlockScope.back();
157    BlockScope.pop_back();
158
159    // Block tail:
160    //    [END_BLOCK, <align4bytes>]
161    EmitCode(bitc::END_BLOCK);
162    FlushToWord();
163
164    // Compute the size of the block, in words, not counting the size field.
165    unsigned SizeInWords = Out.size()/4-B.StartSizeWord - 1;
166    unsigned ByteNo = B.StartSizeWord*4;
167
168    // Update the block size field in the header of this sub-block.
169    Out[ByteNo++] = (unsigned char)(SizeInWords >>  0);
170    Out[ByteNo++] = (unsigned char)(SizeInWords >>  8);
171    Out[ByteNo++] = (unsigned char)(SizeInWords >> 16);
172    Out[ByteNo++] = (unsigned char)(SizeInWords >> 24);
173
174    // Restore the outer block's code size.
175    CurCodeSize = B.PrevCodeSize;
176  }
177
178  //===--------------------------------------------------------------------===//
179  // Record Emission
180  //===--------------------------------------------------------------------===//
181
182  /// EmitRecord - Emit the specified record to the stream, using an abbrev if
183  /// we have one to compress the output.
184  void EmitRecord(unsigned Code, SmallVectorImpl<uint64_t> &Vals,
185                  unsigned Abbrev = 0) {
186    if (Abbrev) {
187      assert(0 && "abbrevs not implemented yet!");
188    } else {
189      // If we don't have an abbrev to use, emit this in its fully unabbreviated
190      // form.
191      EmitCode(bitc::UNABBREV_RECORD);
192      EmitVBR(Code, 6);
193      EmitVBR(Vals.size(), 6);
194      for (unsigned i = 0, e = Vals.size(); i != e; ++i)
195        EmitVBR64(Vals[i], 6);
196    }
197  }
198
199  /// EmitRecord - Emit the specified record to the stream, using an abbrev if
200  /// we have one to compress the output.
201  void EmitRecord(unsigned Code, SmallVectorImpl<unsigned> &Vals,
202                  unsigned Abbrev = 0) {
203    if (Abbrev) {
204      assert(0 && "abbrevs not implemented yet!");
205    } else {
206      // If we don't have an abbrev to use, emit this in its fully unabbreviated
207      // form.
208      EmitCode(bitc::UNABBREV_RECORD);
209      EmitVBR(Code, 6);
210      EmitVBR(Vals.size(), 6);
211      for (unsigned i = 0, e = Vals.size(); i != e; ++i)
212        EmitVBR(Vals[i], 6);
213    }
214  }
215};
216
217
218} // End llvm namespace
219
220#endif
221