contrib/llvm/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp

   1 //===- PDBStringTableBuilder.cpp - PDB String Table -------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/DebugInfo/PDB/Native/PDBStringTableBuilder.h"
  11
  12 #include "llvm/ADT/ArrayRef.h"
  13 #include "llvm/DebugInfo/PDB/Native/Hash.h"
  14 #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
  15 #include "llvm/Support/BinaryStreamWriter.h"
  16 #include "llvm/Support/Endian.h"
  17
  18 #include <map>
  19
  20 using namespace llvm;
  21 using namespace llvm::msf;
  22 using namespace llvm::support;
  23 using namespace llvm::support::endian;
  24 using namespace llvm::pdb;
  25
  26 StringTableHashTraits::StringTableHashTraits(PDBStringTableBuilder &Table)
  27     : Table(&Table) {}
  28
  29 uint32_t StringTableHashTraits::hashLookupKey(StringRef S) const {
  30   return Table->getIdForString(S);
  31 }
  32
  33 StringRef StringTableHashTraits::storageKeyToLookupKey(uint32_t Offset) const {
  34   return Table->getStringForId(Offset);
  35 }
  36
  37 uint32_t StringTableHashTraits::lookupKeyToStorageKey(StringRef S) {
  38   return Table->insert(S);
  39 }
  40
  41 uint32_t PDBStringTableBuilder::insert(StringRef S) {
  42   return Strings.insert(S);
  43 }
  44
  45 uint32_t PDBStringTableBuilder::getIdForString(StringRef S) const {
  46   return Strings.getIdForString(S);
  47 }
  48
  49 StringRef PDBStringTableBuilder::getStringForId(uint32_t Id) const {
  50   return Strings.getStringForId(Id);
  51 }
  52
  53 // This is a precomputed list of Buckets given the specified number of
  54 // strings.  Matching the reference algorithm exactly is not strictly
  55 // necessary for correctness, but it helps when comparing LLD's PDBs with
  56 // Microsoft's PDBs so as to eliminate superfluous differences.
  57 static std::map<uint32_t, uint32_t> StringsToBuckets = {
  58     {1, 2},
  59     {2, 4},
  60     {4, 7},
  61     {6, 11},
  62     {9, 17},
  63     {13, 26},
  64     {20, 40},
  65     {31, 61},
  66     {46, 92},
  67     {70, 139},
  68     {105, 209},
  69     {157, 314},
  70     {236, 472},
  71     {355, 709},
  72     {532, 1064},
  73     {799, 1597},
  74     {1198, 2396},
  75     {1798, 3595},
  76     {2697, 5393},
  77     {4045, 8090},
  78     {6068, 12136},
  79     {9103, 18205},
  80     {13654, 27308},
  81     {20482, 40963},
  82     {30723, 61445},
  83     {46084, 92168},
  84     {69127, 138253},
  85     {103690, 207380},
  86     {155536, 311071},
  87     {233304, 466607},
  88     {349956, 699911},
  89     {524934, 1049867},
  90     {787401, 1574801},
  91     {1181101, 2362202},
  92     {1771652, 3543304},
  93     {2657479, 5314957},
  94     {3986218, 7972436},
  95     {5979328, 11958655},
  96     {8968992, 17937983},
  97     {13453488, 26906975},
  98     {20180232, 40360463},
  99     {30270348, 60540695},
 100     {45405522, 90811043},
 101     {68108283, 136216565},
 102     {102162424, 204324848},
 103     {153243637, 306487273},
 104     {229865455, 459730910},
 105     {344798183, 689596366},
 106     {517197275, 1034394550},
 107     {775795913, 1551591826}};
 108
 109 static uint32_t computeBucketCount(uint32_t NumStrings) {
 110   auto Entry = StringsToBuckets.lower_bound(NumStrings);
 111   assert(Entry != StringsToBuckets.end());
 112   return Entry->second;
 113 }
 114
 115 uint32_t PDBStringTableBuilder::calculateHashTableSize() const {
 116   uint32_t Size = sizeof(uint32_t); // Hash table begins with 4-byte size field.
 117   Size += sizeof(uint32_t) * computeBucketCount(Strings.size());
 118
 119   return Size;
 120 }
 121
 122 uint32_t PDBStringTableBuilder::calculateSerializedSize() const {
 123   uint32_t Size = 0;
 124   Size += sizeof(PDBStringTableHeader);
 125   Size += Strings.calculateSerializedSize();
 126   Size += calculateHashTableSize();
 127   Size += sizeof(uint32_t); // The /names stream ends with the string count.
 128   return Size;
 129 }
 130
 131 void PDBStringTableBuilder::setStrings(
 132     const codeview::DebugStringTableSubsection &Strings) {
 133   this->Strings = Strings;
 134 }
 135
 136 Error PDBStringTableBuilder::writeHeader(BinaryStreamWriter &Writer) const {
 137   // Write a header
 138   PDBStringTableHeader H;
 139   H.Signature = PDBStringTableSignature;
 140   H.HashVersion = 1;
 141   H.ByteSize = Strings.calculateSerializedSize();
 142   if (auto EC = Writer.writeObject(H))
 143     return EC;
 144   assert(Writer.bytesRemaining() == 0);
 145   return Error::success();
 146 }
 147
 148 Error PDBStringTableBuilder::writeStrings(BinaryStreamWriter &Writer) const {
 149   if (auto EC = Strings.commit(Writer))
 150     return EC;
 151
 152   assert(Writer.bytesRemaining() == 0);
 153   return Error::success();
 154 }
 155
 156 Error PDBStringTableBuilder::writeHashTable(BinaryStreamWriter &Writer) const {
 157   // Write a hash table.
 158   uint32_t BucketCount = computeBucketCount(Strings.size());
 159   if (auto EC = Writer.writeInteger(BucketCount))
 160     return EC;
 161   std::vector<ulittle32_t> Buckets(BucketCount);
 162
 163   for (auto &Pair : Strings) {
 164     StringRef S = Pair.getKey();
 165     uint32_t Offset = Pair.getValue();
 166     uint32_t Hash = hashStringV1(S);
 167
 168     for (uint32_t I = 0; I != BucketCount; ++I) {
 169       uint32_t Slot = (Hash + I) % BucketCount;
 170       if (Buckets[Slot] != 0)
 171         continue;
 172       Buckets[Slot] = Offset;
 173       break;
 174     }
 175   }
 176
 177   if (auto EC = Writer.writeArray(ArrayRef<ulittle32_t>(Buckets)))
 178     return EC;
 179
 180   assert(Writer.bytesRemaining() == 0);
 181   return Error::success();
 182 }
 183
 184 Error PDBStringTableBuilder::writeEpilogue(BinaryStreamWriter &Writer) const {
 185   if (auto EC = Writer.writeInteger<uint32_t>(Strings.size()))
 186     return EC;
 187   assert(Writer.bytesRemaining() == 0);
 188   return Error::success();
 189 }
 190
 191 Error PDBStringTableBuilder::commit(BinaryStreamWriter &Writer) const {
 192   BinaryStreamWriter SectionWriter;
 193
 194   std::tie(SectionWriter, Writer) = Writer.split(sizeof(PDBStringTableHeader));
 195   if (auto EC = writeHeader(SectionWriter))
 196     return EC;
 197
 198   std::tie(SectionWriter, Writer) =
 199       Writer.split(Strings.calculateSerializedSize());
 200   if (auto EC = writeStrings(SectionWriter))
 201     return EC;
 202
 203   std::tie(SectionWriter, Writer) = Writer.split(calculateHashTableSize());
 204   if (auto EC = writeHashTable(SectionWriter))
 205     return EC;
 206
 207   std::tie(SectionWriter, Writer) = Writer.split(sizeof(uint32_t));
 208   if (auto EC = writeEpilogue(SectionWriter))
 209     return EC;
 210
 211   return Error::success();
 212 }