include/llvm/Bitcode/BitstreamWriter.h

   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
  21 namespace llvm {
  22
  23 class 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   struct Block {
  37     unsigned PrevCodeSize;
  38     unsigned StartSizeWord;
  39     std::vector<BitCodeAbbrev*> PrevAbbrevs;
  40     Block(unsigned PCS, unsigned SSW) : PrevCodeSize(PCS), StartSizeWord(SSW) {}
  41   };
  42
  43   /// BlockScope - This tracks the current blocks that we have entered.
  44   std::vector<Block> BlockScope;
  45
  46   std::vector<BitCodeAbbrev*> CurAbbrevs;
  47 public:
  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
 149     // Delete all abbrevs.
 150     for (unsigned i = 0, e = CurAbbrevs.size(); i != e; ++i)
 151       delete CurAbbrevs[i];
 152
 153     BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
 154     // Emit a placeholder, which will be replaced when the block is popped.
 155     Emit(0, bitc::BlockSizeWidth);
 156
 157     CurCodeSize = CodeLen;
 158   }
 159
 160   void ExitBlock() {
 161     assert(!BlockScope.empty() && "Block scope imbalance!");
 162     const Block &B = BlockScope.back();
 163
 164     // Block tail:
 165     //    [END_BLOCK, <align4bytes>]
 166     EmitCode(bitc::END_BLOCK);
 167     FlushToWord();
 168
 169     // Compute the size of the block, in words, not counting the size field.
 170     unsigned SizeInWords = Out.size()/4-B.StartSizeWord - 1;
 171     unsigned ByteNo = B.StartSizeWord*4;
 172
 173     // Update the block size field in the header of this sub-block.
 174     Out[ByteNo++] = (unsigned char)(SizeInWords >>  0);
 175     Out[ByteNo++] = (unsigned char)(SizeInWords >>  8);
 176     Out[ByteNo++] = (unsigned char)(SizeInWords >> 16);
 177     Out[ByteNo++] = (unsigned char)(SizeInWords >> 24);
 178
 179     // Restore the inner block's code size and abbrev table.
 180     CurCodeSize = B.PrevCodeSize;
 181     BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
 182     BlockScope.pop_back();
 183   }
 184
 185   //===--------------------------------------------------------------------===//
 186   // Record Emission
 187   //===--------------------------------------------------------------------===//
 188
 189   /// EmitRecord - Emit the specified record to the stream, using an abbrev if
 190   /// we have one to compress the output.
 191   void EmitRecord(unsigned Code, SmallVectorImpl<uint64_t> &Vals,
 192                   unsigned Abbrev = 0) {
 193     if (Abbrev) {
 194       unsigned AbbrevNo = Abbrev-bitc::FIRST_ABBREV;
 195       assert(AbbrevNo < CurAbbrevs.size() && "Invalid abbrev #!");
 196       BitCodeAbbrev *Abbv = CurAbbrevs[AbbrevNo];
 197       assert(0 && "TODO");
 198       for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) {
 199       }
 200
 201
 202     } else {
 203       // If we don't have an abbrev to use, emit this in its fully unabbreviated
 204       // form.
 205       EmitCode(bitc::UNABBREV_RECORD);
 206       EmitVBR(Code, 6);
 207       EmitVBR(Vals.size(), 6);
 208       for (unsigned i = 0, e = Vals.size(); i != e; ++i)
 209         EmitVBR64(Vals[i], 6);
 210     }
 211   }
 212
 213   /// EmitRecord - Emit the specified record to the stream, using an abbrev if
 214   /// we have one to compress the output.
 215   void EmitRecord(unsigned Code, SmallVectorImpl<unsigned> &Vals,
 216                   unsigned Abbrev = 0) {
 217     if (Abbrev) {
 218       assert(0 && "abbrevs not implemented yet!");
 219     } else {
 220       // If we don't have an abbrev to use, emit this in its fully unabbreviated
 221       // form.
 222       EmitCode(bitc::UNABBREV_RECORD);
 223       EmitVBR(Code, 6);
 224       EmitVBR(Vals.size(), 6);
 225       for (unsigned i = 0, e = Vals.size(); i != e; ++i)
 226         EmitVBR(Vals[i], 6);
 227     }
 228   }
 229
 230   //===--------------------------------------------------------------------===//
 231   // Abbrev Emission
 232   //===--------------------------------------------------------------------===//
 233
 234   /// EmitAbbrev - This emits an abbreviation to the stream.  Note that this
 235   /// method takes ownership of the specified abbrev.
 236   unsigned EmitAbbrev(BitCodeAbbrev *Abbv) {
 237     // Emit the abbreviation as a record.
 238     EmitCode(bitc::DEFINE_ABBREV);
 239     EmitVBR(Abbv->getNumOperandInfos(), 5);
 240     for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) {
 241       const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
 242       Emit(Op.isLiteral(), 1);
 243       if (Op.isLiteral()) {
 244         EmitVBR64(Op.getLiteralValue(), 8);
 245       } else {
 246         Emit(Op.getEncoding(), 3);
 247         if (Op.hasEncodingData())
 248           EmitVBR64(Op.getEncodingData(), 5);
 249       }
 250     }
 251
 252     CurAbbrevs.push_back(Abbv);
 253     return CurAbbrevs.size()-1+bitc::FIRST_ABBREV;
 254   }
 255 };
 256
 257
 258 } // End llvm namespace
 259
 260 #endif