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