236 lines · cpp
1//===- StringTableBuilder.cpp - String table building utility -------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/MC/StringTableBuilder.h"10#include "llvm/ADT/ArrayRef.h"11#include "llvm/ADT/CachedHashString.h"12#include "llvm/ADT/SmallString.h"13#include "llvm/ADT/StringRef.h"14#include "llvm/BinaryFormat/COFF.h"15#include "llvm/Support/Endian.h"16#include "llvm/Support/MathExtras.h"17#include "llvm/Support/raw_ostream.h"18#include <cassert>19#include <cstddef>20#include <cstdint>21#include <cstring>22#include <utility>23#include <vector>24 25using namespace llvm;26 27StringTableBuilder::~StringTableBuilder() = default;28 29void StringTableBuilder::initSize() {30 // Account for leading bytes in table so that offsets returned from add are31 // correct.32 switch (K) {33 case RAW:34 case DWARF:35 Size = 0;36 break;37 case MachOLinked:38 case MachO64Linked:39 Size = 2;40 break;41 case MachO:42 case MachO64:43 case ELF:44 case DXContainer:45 // Start the table with a NUL byte.46 Size = 1;47 break;48 case XCOFF:49 case WinCOFF:50 // Make room to write the table size later.51 Size = 4;52 break;53 }54}55 56StringTableBuilder::StringTableBuilder(Kind K, Align Alignment)57 : K(K), Alignment(Alignment) {58 initSize();59}60 61void StringTableBuilder::write(raw_ostream &OS) const {62 assert(isFinalized());63 SmallString<0> Data;64 Data.resize(getSize());65 write((uint8_t *)Data.data());66 OS << Data;67}68 69using StringPair = std::pair<CachedHashStringRef, size_t>;70 71void StringTableBuilder::write(uint8_t *Buf) const {72 assert(isFinalized());73 for (const StringPair &P : StringIndexMap) {74 StringRef Data = P.first.val();75 if (!Data.empty())76 memcpy(Buf + P.second, Data.data(), Data.size());77 }78 // The COFF formats store the size of the string table in the first 4 bytes.79 // For Windows, the format is little-endian; for AIX, it is big-endian.80 if (K == WinCOFF)81 support::endian::write32le(Buf, Size);82 else if (K == XCOFF)83 support::endian::write32be(Buf, Size);84}85 86// Returns the character at Pos from end of a string.87static int charTailAt(StringPair *P, size_t Pos) {88 StringRef S = P->first.val();89 if (Pos >= S.size())90 return -1;91 return (unsigned char)S[S.size() - Pos - 1];92}93 94// Three-way radix quicksort. This is much faster than std::sort with strcmp95// because it does not compare characters that we already know the same.96static void multikeySort(MutableArrayRef<StringPair *> Vec, int Pos) {97tailcall:98 if (Vec.size() <= 1)99 return;100 101 // Partition items so that items in [0, I) are greater than the pivot,102 // [I, J) are the same as the pivot, and [J, Vec.size()) are less than103 // the pivot.104 int Pivot = charTailAt(Vec[0], Pos);105 size_t I = 0;106 size_t J = Vec.size();107 for (size_t K = 1; K < J;) {108 int C = charTailAt(Vec[K], Pos);109 if (C > Pivot)110 std::swap(Vec[I++], Vec[K++]);111 else if (C < Pivot)112 std::swap(Vec[--J], Vec[K]);113 else114 K++;115 }116 117 multikeySort(Vec.slice(0, I), Pos);118 multikeySort(Vec.slice(J), Pos);119 120 // multikeySort(Vec.slice(I, J - I), Pos + 1), but with121 // tail call optimization.122 if (Pivot != -1) {123 Vec = Vec.slice(I, J - I);124 ++Pos;125 goto tailcall;126 }127}128 129void StringTableBuilder::finalize() {130 assert(K != DWARF);131 finalizeStringTable(/*Optimize=*/true);132}133 134void StringTableBuilder::finalizeInOrder() {135 finalizeStringTable(/*Optimize=*/false);136}137 138void StringTableBuilder::finalizeStringTable(bool Optimize) {139 Finalized = true;140 141 if (Optimize && StringIndexMap.size()) {142 std::vector<StringPair *> Strings;143 Strings.reserve(StringIndexMap.size());144 for (StringPair &P : StringIndexMap)145 Strings.push_back(&P);146 147 size_t RangeBegin = 0;148 MutableArrayRef<StringPair *> StringsRef(Strings);149 if (StringPriorityMap.size()) {150 llvm::sort(Strings,151 [&](const StringPair *LHS, const StringPair *RHS) -> bool {152 return StringPriorityMap.lookup(LHS->first) >153 StringPriorityMap.lookup(RHS->first);154 });155 uint8_t RangePriority = StringPriorityMap.lookup(Strings[0]->first);156 for (size_t I = 1, E = Strings.size(); I != E && RangePriority; ++I) {157 uint8_t Priority = StringPriorityMap.lookup(Strings[I]->first);158 if (Priority != RangePriority) {159 multikeySort(StringsRef.slice(RangeBegin, I - RangeBegin), 0);160 RangePriority = Priority;161 RangeBegin = I;162 }163 }164 }165 multikeySort(StringsRef.slice(RangeBegin), 0);166 initSize();167 168 StringRef Previous;169 for (StringPair *P : Strings) {170 StringRef S = P->first.val();171 if (Previous.ends_with(S)) {172 size_t Pos = Size - S.size() - (K != RAW);173 if (isAligned(Alignment, Pos)) {174 P->second = Pos;175 continue;176 }177 }178 179 Size = alignTo(Size, Alignment);180 P->second = Size;181 182 Size += S.size();183 if (K != RAW)184 ++Size;185 Previous = S;186 }187 }188 189 if (K == MachO || K == MachOLinked || K == DXContainer)190 Size = alignTo(Size, 4); // Pad to multiple of 4.191 if (K == MachO64 || K == MachO64Linked)192 Size = alignTo(Size, 8); // Pad to multiple of 8.193 194 // According to ld64 the string table of a final linked Mach-O binary starts195 // with " ", i.e. the first byte is ' ' and the second byte is zero. In196 // 'initSize()' we reserved the first two bytes for holding this string.197 if (K == MachOLinked || K == MachO64Linked)198 StringIndexMap[CachedHashStringRef(" ")] = 0;199 200 // The first byte in an ELF string table must be null, according to the ELF201 // specification. In 'initSize()' we reserved the first byte to hold null for202 // this purpose and here we actually add the string to allow 'getOffset()' to203 // be called on an empty string.204 if (K == ELF)205 StringIndexMap[CachedHashStringRef("")] = 0;206}207 208void StringTableBuilder::clear() {209 Finalized = false;210 StringIndexMap.clear();211}212 213size_t StringTableBuilder::getOffset(CachedHashStringRef S) const {214 assert(isFinalized());215 auto I = StringIndexMap.find(S);216 assert(I != StringIndexMap.end() && "String is not in table!");217 return I->second;218}219 220size_t StringTableBuilder::add(CachedHashStringRef S, uint8_t Priority) {221 if (K == WinCOFF)222 assert(S.size() > COFF::NameSize && "Short string in COFF string table!");223 224 assert(!isFinalized());225 if (Priority)226 StringPriorityMap[S] = std::max(Priority, StringPriorityMap[S]);227 228 auto P = StringIndexMap.try_emplace(S);229 if (P.second) {230 size_t Start = alignTo(Size, Alignment);231 P.first->second = Start;232 Size = Start + S.size() + (K != RAW);233 }234 return P.first->second;235}236