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