courgette/encoded_program.cc

   1 // Copyright 2011 The Chromium Authors
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "courgette/encoded_program.h"
   6
   7 #include <stddef.h>
   8 #include <stdint.h>
   9
  10 #include <algorithm>
  11 #include <map>
  12 #include <string>
  13 #include <utility>
  14 #include <vector>
  15
  16 #include "base/environment.h"
  17 #include "base/logging.h"
  18 #include "base/memory/raw_ptr.h"
  19 #include "base/numerics/safe_conversions.h"
  20 #include "base/numerics/safe_math.h"
  21 #include "base/strings/string_number_conversions.h"
  22 #include "base/strings/string_util.h"
  23 #include "courgette/label_manager.h"
  24 #include "courgette/streams.h"
  25
  26 namespace courgette {
  27
  28 namespace {
  29
  30 // Serializes a vector of integral values using Varint32 coding.
  31 template<typename V>
  32 CheckBool WriteVector(const V& items, SinkStream* buffer) {
  33   size_t count = items.size();
  34   bool ok = buffer->WriteSizeVarint32(count);
  35   for (size_t i = 0; ok && i < count;  ++i) {
  36     ok = buffer->WriteSizeVarint32(items[i]);
  37   }
  38   return ok;
  39 }
  40
  41 template<typename V>
  42 bool ReadVector(V* items, SourceStream* buffer) {
  43   uint32_t count;
  44   if (!buffer->ReadVarint32(&count))
  45     return false;
  46
  47   items->clear();
  48
  49   bool ok = items->reserve(count);
  50   for (size_t i = 0;  ok && i < count;  ++i) {
  51     uint32_t item;
  52     ok = buffer->ReadVarint32(&item);
  53     if (ok)
  54       ok = items->push_back(static_cast<typename V::value_type>(item));
  55   }
  56
  57   return ok;
  58 }
  59
  60 // Serializes a vector, using delta coding followed by Varint32Signed coding.
  61 template<typename V>
  62 CheckBool WriteSigned32Delta(const V& set, SinkStream* buffer) {
  63   size_t count = set.size();
  64   bool ok = buffer->WriteSizeVarint32(count);
  65   uint32_t prev = 0;
  66   for (size_t i = 0; ok && i < count; ++i) {
  67     uint32_t current = set[i];
  68     int32_t delta = current - prev;
  69     ok = buffer->WriteVarint32Signed(delta);
  70     prev = current;
  71   }
  72   return ok;
  73 }
  74
  75 template <typename V>
  76 static CheckBool ReadSigned32Delta(V* set, SourceStream* buffer) {
  77   uint32_t count;
  78
  79   if (!buffer->ReadVarint32(&count))
  80     return false;
  81
  82   set->clear();
  83   bool ok = set->reserve(count);
  84   uint32_t prev = 0;
  85   for (size_t i = 0; ok && i < count; ++i) {
  86     int32_t delta;
  87     ok = buffer->ReadVarint32Signed(&delta);
  88     if (ok) {
  89       uint32_t current = static_cast<uint32_t>(prev + delta);
  90       ok = set->push_back(current);
  91       prev = current;
  92     }
  93   }
  94   return ok;
  95 }
  96
  97 // Write a vector as the byte representation of the contents.
  98 //
  99 // (This only really makes sense for a type T that has sizeof(T)==1, otherwise
 100 // serialized representation is not endian-agnostic.  But it is useful to keep
 101 // the possibility of a greater size for experiments comparing Varint32 encoding
 102 // of a vector of larger integrals vs a plain form.)
 103 //
 104 template<typename V>
 105 CheckBool WriteVectorU8(const V& items, SinkStream* buffer) {
 106   size_t count = items.size();
 107   bool ok = buffer->WriteSizeVarint32(count);
 108   if (count != 0 && ok) {
 109     size_t byte_count = count * sizeof(typename V::value_type);
 110     ok = buffer->Write(static_cast<const void*>(&items[0]), byte_count);
 111   }
 112   return ok;
 113 }
 114
 115 template<typename V>
 116 bool ReadVectorU8(V* items, SourceStream* buffer) {
 117   uint32_t count;
 118   if (!buffer->ReadVarint32(&count))
 119     return false;
 120
 121   items->clear();
 122   bool ok = items->resize(count, 0);
 123   if (ok && count != 0) {
 124     size_t byte_count = count * sizeof(typename V::value_type);
 125     return buffer->Read(static_cast<void*>(&((*items)[0])), byte_count);
 126   }
 127   return ok;
 128 }
 129
 130 /******** InstructionStoreReceptor ********/
 131
 132 // An InstructionReceptor that stores emitted instructions.
 133 class InstructionStoreReceptor : public InstructionReceptor {
 134  public:
 135   explicit InstructionStoreReceptor(ExecutableType exe_type,
 136                                     EncodedProgram* encoded)
 137       : exe_type_(exe_type), encoded_(encoded) {
 138     CHECK(encoded_);
 139   }
 140
 141   InstructionStoreReceptor(const InstructionStoreReceptor&) = delete;
 142   InstructionStoreReceptor& operator=(const InstructionStoreReceptor&) = delete;
 143
 144   CheckBool EmitPeRelocs() override {
 145     return encoded_->AddPeMakeRelocs(exe_type_);
 146   }
 147   CheckBool EmitElfRelocation() override {
 148     return encoded_->AddElfMakeRelocs();
 149   }
 150   CheckBool EmitOrigin(RVA rva) override { return encoded_->AddOrigin(rva); }
 151   CheckBool EmitSingleByte(uint8_t byte) override {
 152     return encoded_->AddCopy(1, &byte);
 153   }
 154   CheckBool EmitMultipleBytes(const uint8_t* bytes, size_t len) override {
 155     return encoded_->AddCopy(len, bytes);
 156   }
 157   CheckBool EmitRel32(Label* label) override {
 158     return encoded_->AddRel32(label->index_);
 159   }
 160   CheckBool EmitAbs32(Label* label) override {
 161     return encoded_->AddAbs32(label->index_);
 162   }
 163   CheckBool EmitAbs64(Label* label) override {
 164     return encoded_->AddAbs64(label->index_);
 165   }
 166
 167  private:
 168   ExecutableType exe_type_;
 169   raw_ptr<EncodedProgram> encoded_;
 170 };
 171
 172 }  // namespace
 173
 174 ////////////////////////////////////////////////////////////////////////////////
 175
 176 // Constructor is here rather than in the header. Although the constructor
 177 // appears to do nothing it is fact quite large because of the implicit calls to
 178 // field constructors. Ditto for the destructor.
 179 EncodedProgram::EncodedProgram() = default;
 180 EncodedProgram::~EncodedProgram() = default;
 181
 182 CheckBool EncodedProgram::ImportLabels(
 183     const LabelManager& abs32_label_manager,
 184     const LabelManager& rel32_label_manager) {
 185   if (!WriteRvasToList(abs32_label_manager, &abs32_rva_) ||
 186       !WriteRvasToList(rel32_label_manager, &rel32_rva_)) {
 187     return false;
 188   }
 189   FillUnassignedRvaSlots(&abs32_rva_);
 190   FillUnassignedRvaSlots(&rel32_rva_);
 191   return true;
 192 }
 193
 194 CheckBool EncodedProgram::AddOrigin(RVA origin) {
 195   return ops_.push_back(ORIGIN) && origins_.push_back(origin);
 196 }
 197
 198 CheckBool EncodedProgram::AddCopy(size_t count, const void* bytes) {
 199   const uint8_t* source = static_cast<const uint8_t*>(bytes);
 200
 201   bool ok = true;
 202
 203   // Fold adjacent COPY instructions into one.  This nearly halves the size of
 204   // an EncodedProgram with only COPY1 instructions since there are approx plain
 205   // 16 bytes per reloc.  This has a working-set benefit during decompression.
 206   // For compression of files with large differences this makes a small (4%)
 207   // improvement in size.  For files with small differences this degrades the
 208   // compressed size by 1.3%
 209   if (!ops_.empty()) {
 210     if (ops_.back() == COPY1) {
 211       ops_.back() = COPY;
 212       ok = copy_counts_.push_back(1);
 213     }
 214     if (ok && ops_.back() == COPY) {
 215       copy_counts_.back() += count;
 216       for (size_t i = 0; ok && i < count; ++i) {
 217         ok = copy_bytes_.push_back(source[i]);
 218       }
 219       return ok;
 220     }
 221   }
 222
 223   if (ok) {
 224     if (count == 1) {
 225       ok = ops_.push_back(COPY1) && copy_bytes_.push_back(source[0]);
 226     } else {
 227       ok = ops_.push_back(COPY) && copy_counts_.push_back(count);
 228       for (size_t i = 0; ok && i < count; ++i) {
 229         ok = copy_bytes_.push_back(source[i]);
 230       }
 231     }
 232   }
 233
 234   return ok;
 235 }
 236
 237 CheckBool EncodedProgram::AddAbs32(int label_index) {
 238   return ops_.push_back(ABS32) && abs32_ix_.push_back(label_index);
 239 }
 240
 241 CheckBool EncodedProgram::AddAbs64(int label_index) {
 242   return ops_.push_back(ABS64) && abs32_ix_.push_back(label_index);
 243 }
 244
 245 CheckBool EncodedProgram::AddRel32(int label_index) {
 246   return ops_.push_back(REL32) && rel32_ix_.push_back(label_index);
 247 }
 248
 249 CheckBool EncodedProgram::AddPeMakeRelocs(ExecutableType kind) {
 250   if (kind == EXE_WIN_32_X86)
 251     return ops_.push_back(MAKE_PE_RELOCATION_TABLE);
 252   return ops_.push_back(MAKE_PE64_RELOCATION_TABLE);
 253 }
 254
 255 CheckBool EncodedProgram::AddElfMakeRelocs() {
 256   return ops_.push_back(MAKE_ELF_RELOCATION_TABLE);
 257 }
 258
 259 void EncodedProgram::DebuggingSummary() {
 260   VLOG(1) << "EncodedProgram Summary"
 261           << "\n  image base  " << image_base_
 262           << "\n  abs32 rvas  " << abs32_rva_.size()
 263           << "\n  rel32 rvas  " << rel32_rva_.size()
 264           << "\n  ops         " << ops_.size()
 265           << "\n  origins     " << origins_.size()
 266           << "\n  copy_counts " << copy_counts_.size()
 267           << "\n  copy_bytes  " << copy_bytes_.size()
 268           << "\n  abs32_ix    " << abs32_ix_.size()
 269           << "\n  rel32_ix    " << rel32_ix_.size();
 270 }
 271
 272 ////////////////////////////////////////////////////////////////////////////////
 273
 274 // For algorithm refinement purposes it is useful to write subsets of the file
 275 // format.  This gives us the ability to estimate the entropy of the
 276 // differential compression of the individual streams, which can provide
 277 // invaluable insights.  The default, of course, is to include all the streams.
 278 //
 279 enum FieldSelect {
 280   INCLUDE_ABS32_ADDRESSES = 0x0001,
 281   INCLUDE_REL32_ADDRESSES = 0x0002,
 282   INCLUDE_ABS32_INDEXES   = 0x0010,
 283   INCLUDE_REL32_INDEXES   = 0x0020,
 284   INCLUDE_OPS             = 0x0100,
 285   INCLUDE_BYTES           = 0x0200,
 286   INCLUDE_COPY_COUNTS     = 0x0400,
 287   INCLUDE_MISC            = 0x1000
 288 };
 289
 290 static FieldSelect GetFieldSelect() {
 291   // TODO(sra): Use better configuration.
 292   std::unique_ptr<base::Environment> env(base::Environment::Create());
 293   std::string s;
 294   env->GetVar("A_FIELDS", &s);
 295   uint64_t fields;
 296   if (!base::StringToUint64(s, &fields))
 297     return static_cast<FieldSelect>(~0);
 298   return static_cast<FieldSelect>(fields);
 299 }
 300
 301 CheckBool EncodedProgram::WriteTo(SinkStreamSet* streams) {
 302   FieldSelect select = GetFieldSelect();
 303
 304   // The order of fields must be consistent in WriteTo and ReadFrom, regardless
 305   // of the streams used.  The code can be configured with all kStreamXXX
 306   // constants the same.
 307   //
 308   // If we change the code to pipeline reading with assembly (to avoid temporary
 309   // storage vectors by consuming operands directly from the stream) then we
 310   // need to read the base address and the random access address tables first,
 311   // the rest can be interleaved.
 312
 313   if (select & INCLUDE_MISC) {
 314     uint32_t high = static_cast<uint32_t>(image_base_ >> 32);
 315     uint32_t low = static_cast<uint32_t>(image_base_ & 0xffffffffU);
 316
 317     if (!streams->stream(kStreamMisc)->WriteVarint32(high) ||
 318         !streams->stream(kStreamMisc)->WriteVarint32(low)) {
 319       return false;
 320     }
 321   }
 322
 323   bool success = true;
 324
 325   if (select & INCLUDE_ABS32_ADDRESSES) {
 326     success &= WriteSigned32Delta(abs32_rva_,
 327                                   streams->stream(kStreamAbs32Addresses));
 328   }
 329
 330   if (select & INCLUDE_REL32_ADDRESSES) {
 331     success &= WriteSigned32Delta(rel32_rva_,
 332                                   streams->stream(kStreamRel32Addresses));
 333   }
 334
 335   if (select & INCLUDE_MISC)
 336     success &= WriteVector(origins_, streams->stream(kStreamOriginAddresses));
 337
 338   if (select & INCLUDE_OPS) {
 339     // 5 for length.
 340     success &= streams->stream(kStreamOps)->Reserve(ops_.size() + 5);
 341     success &= WriteVector(ops_, streams->stream(kStreamOps));
 342   }
 343
 344   if (select & INCLUDE_COPY_COUNTS)
 345     success &= WriteVector(copy_counts_, streams->stream(kStreamCopyCounts));
 346
 347   if (select & INCLUDE_BYTES)
 348     success &= WriteVectorU8(copy_bytes_, streams->stream(kStreamBytes));
 349
 350   if (select & INCLUDE_ABS32_INDEXES)
 351     success &= WriteVector(abs32_ix_, streams->stream(kStreamAbs32Indexes));
 352
 353   if (select & INCLUDE_REL32_INDEXES)
 354     success &= WriteVector(rel32_ix_, streams->stream(kStreamRel32Indexes));
 355
 356   return success;
 357 }
 358
 359 bool EncodedProgram::ReadFrom(SourceStreamSet* streams) {
 360   uint32_t high;
 361   uint32_t low;
 362
 363   if (!streams->stream(kStreamMisc)->ReadVarint32(&high) ||
 364       !streams->stream(kStreamMisc)->ReadVarint32(&low)) {
 365     return false;
 366   }
 367   image_base_ = (static_cast<uint64_t>(high) << 32) | low;
 368
 369   if (!ReadSigned32Delta(&abs32_rva_, streams->stream(kStreamAbs32Addresses)))
 370     return false;
 371   if (!ReadSigned32Delta(&rel32_rva_, streams->stream(kStreamRel32Addresses)))
 372     return false;
 373   if (!ReadVector(&origins_, streams->stream(kStreamOriginAddresses)))
 374     return false;
 375   if (!ReadVector(&ops_, streams->stream(kStreamOps)))
 376     return false;
 377   if (!ReadVector(&copy_counts_, streams->stream(kStreamCopyCounts)))
 378     return false;
 379   if (!ReadVectorU8(&copy_bytes_, streams->stream(kStreamBytes)))
 380     return false;
 381   if (!ReadVector(&abs32_ix_, streams->stream(kStreamAbs32Indexes)))
 382     return false;
 383   if (!ReadVector(&rel32_ix_, streams->stream(kStreamRel32Indexes)))
 384     return false;
 385
 386   // Check that streams have been completely consumed.
 387   for (int i = 0;  i < kStreamLimit;  ++i) {
 388     if (streams->stream(i)->Remaining() > 0)
 389       return false;
 390   }
 391
 392   return true;
 393 }
 394
 395 // Safe, non-throwing version of std::vector::at().  Returns 'true' for success,
 396 // 'false' for out-of-bounds index error.
 397 template<typename V, typename T>
 398 bool VectorAt(const V& v, size_t index, T* output) {
 399   if (index >= v.size())
 400     return false;
 401   *output = v[index];
 402   return true;
 403 }
 404
 405 CheckBool EncodedProgram::AssembleTo(SinkStream* final_buffer) {
 406   // For the most part, the assembly process walks the various tables.
 407   // ix_mumble is the index into the mumble table.
 408   size_t ix_origins = 0;
 409   size_t ix_copy_counts = 0;
 410   size_t ix_copy_bytes = 0;
 411   size_t ix_abs32_ix = 0;
 412   size_t ix_rel32_ix = 0;
 413
 414   RVA current_rva = 0;
 415
 416   bool pending_pe_relocation_table = false;
 417   uint8_t pending_pe_relocation_table_type = 0x03;  // IMAGE_REL_BASED_HIGHLOW
 418   Elf32_Word pending_elf_relocation_table_type = 0;
 419   SinkStream bytes_following_relocation_table;
 420
 421   SinkStream* output = final_buffer;
 422
 423   for (size_t ix_ops = 0;  ix_ops < ops_.size();  ++ix_ops) {
 424     OP op = ops_[ix_ops];
 425
 426     switch (op) {
 427       default:
 428         return false;
 429
 430       case ORIGIN: {
 431         RVA section_rva;
 432         if (!VectorAt(origins_, ix_origins, &section_rva))
 433           return false;
 434         ++ix_origins;
 435         current_rva = section_rva;
 436         break;
 437       }
 438
 439       case COPY: {
 440         size_t count;
 441         if (!VectorAt(copy_counts_, ix_copy_counts, &count))
 442           return false;
 443         ++ix_copy_counts;
 444         for (size_t i = 0;  i < count;  ++i) {
 445           uint8_t b;
 446           if (!VectorAt(copy_bytes_, ix_copy_bytes, &b))
 447             return false;
 448           ++ix_copy_bytes;
 449           if (!output->Write(&b, 1))
 450             return false;
 451         }
 452         current_rva += static_cast<RVA>(count);
 453         break;
 454       }
 455
 456       case COPY1: {
 457         uint8_t b;
 458         if (!VectorAt(copy_bytes_, ix_copy_bytes, &b))
 459           return false;
 460         ++ix_copy_bytes;
 461         if (!output->Write(&b, 1))
 462           return false;
 463         current_rva += 1;
 464         break;
 465       }
 466
 467       case REL32: {
 468         uint32_t index;
 469         if (!VectorAt(rel32_ix_, ix_rel32_ix, &index))
 470           return false;
 471         ++ix_rel32_ix;
 472         RVA rva;
 473         if (!VectorAt(rel32_rva_, index, &rva))
 474           return false;
 475         uint32_t offset = (rva - (current_rva + 4));
 476         if (!output->Write(&offset, 4))
 477           return false;
 478         current_rva += 4;
 479         break;
 480       }
 481
 482       case ABS32:
 483       case ABS64: {
 484         uint32_t index;
 485         if (!VectorAt(abs32_ix_, ix_abs32_ix, &index))
 486           return false;
 487         ++ix_abs32_ix;
 488         RVA rva;
 489         if (!VectorAt(abs32_rva_, index, &rva))
 490           return false;
 491         if (op == ABS32) {
 492           base::CheckedNumeric<uint32_t> abs32 = image_base_;
 493           abs32 += rva;
 494           uint32_t safe_abs32 = abs32.ValueOrDie();
 495           if (!abs32_relocs_.push_back(current_rva) ||
 496               !output->Write(&safe_abs32, 4)) {
 497             return false;
 498           }
 499           current_rva += 4;
 500         } else {
 501           base::CheckedNumeric<uint64_t> abs64 = image_base_;
 502           abs64 += rva;
 503           uint64_t safe_abs64 = abs64.ValueOrDie();
 504           if (!abs32_relocs_.push_back(current_rva) ||
 505               !output->Write(&safe_abs64, 8)) {
 506             return false;
 507           }
 508           current_rva += 8;
 509         }
 510         break;
 511       }
 512
 513       case MAKE_PE_RELOCATION_TABLE: {
 514         // We can see the base relocation anywhere, but we only have the
 515         // information to generate it at the very end.  So we divert the bytes
 516         // we are generating to a temporary stream.
 517         if (pending_pe_relocation_table)
 518           return false;  // Can't have two base relocation tables.
 519
 520         pending_pe_relocation_table = true;
 521         output = &bytes_following_relocation_table;
 522         break;
 523         // There is a potential problem *if* the instruction stream contains
 524         // some REL32 relocations following the base relocation and in the same
 525         // section.  We don't know the size of the table, so 'current_rva' will
 526         // be wrong, causing REL32 offsets to be miscalculated.  This never
 527         // happens; the base relocation table is usually in a section of its
 528         // own, a data-only section, and following everything else in the
 529         // executable except some padding zero bytes.  We could fix this by
 530         // emitting an ORIGIN after the MAKE_BASE_RELOCATION_TABLE.
 531       }
 532
 533       case MAKE_PE64_RELOCATION_TABLE: {
 534         if (pending_pe_relocation_table)
 535           return false;  // Can't have two base relocation tables.
 536
 537         pending_pe_relocation_table = true;
 538         pending_pe_relocation_table_type = 0x0A;  // IMAGE_REL_BASED_DIR64
 539         output = &bytes_following_relocation_table;
 540         break;
 541       }
 542
 543       case MAKE_ELF_RELOCATION_TABLE: {
 544         // We can see the base relocation anywhere, but we only have the
 545         // information to generate it at the very end.  So we divert the bytes
 546         // we are generating to a temporary stream.
 547         if (pending_elf_relocation_table_type)
 548           return false;  // Can't have two base relocation tables.
 549
 550         pending_elf_relocation_table_type = R_386_RELATIVE;
 551         output = &bytes_following_relocation_table;
 552         break;
 553       }
 554     }
 555   }
 556
 557   if (pending_pe_relocation_table) {
 558     if (!GeneratePeRelocations(final_buffer,
 559                                pending_pe_relocation_table_type) ||
 560         !final_buffer->Append(&bytes_following_relocation_table))
 561       return false;
 562   }
 563
 564   if (pending_elf_relocation_table_type) {
 565     if (!GenerateElfRelocations(pending_elf_relocation_table_type,
 566                                 final_buffer) ||
 567         !final_buffer->Append(&bytes_following_relocation_table))
 568       return false;
 569   }
 570
 571   // Final verification check: did we consume all lists?
 572   if (ix_copy_counts != copy_counts_.size())
 573     return false;
 574   if (ix_copy_bytes != copy_bytes_.size())
 575     return false;
 576   if (ix_abs32_ix != abs32_ix_.size())
 577     return false;
 578   if (ix_rel32_ix != rel32_ix_.size())
 579     return false;
 580
 581   return true;
 582 }
 583
 584 CheckBool EncodedProgram::GenerateInstructions(
 585     ExecutableType exe_type,
 586     const InstructionGenerator& gen) {
 587   InstructionStoreReceptor store_receptor(exe_type, this);
 588   return gen.Run(&store_receptor);
 589 }
 590
 591 // RelocBlock has the layout of a block of relocations in the base relocation
 592 // table file format.
 593 struct RelocBlockPOD {
 594   uint32_t page_rva;
 595   uint32_t block_size;
 596   uint16_t relocs[4096];  // Allow up to one relocation per byte of a 4k page.
 597 };
 598
 599 static_assert(offsetof(RelocBlockPOD, relocs) == 8, "reloc block header size");
 600
 601 class RelocBlock {
 602  public:
 603   RelocBlock() {
 604     pod.page_rva = 0xFFFFFFFF;
 605     pod.block_size = 8;
 606   }
 607
 608   void Add(uint16_t item) {
 609     pod.relocs[(pod.block_size-8)/2] = item;
 610     pod.block_size += 2;
 611   }
 612
 613   [[nodiscard]] CheckBool Flush(SinkStream* buffer) {
 614     bool ok = true;
 615     if (pod.block_size != 8) {
 616       if (pod.block_size % 4 != 0) {  // Pad to make size multiple of 4 bytes.
 617         Add(0);
 618       }
 619       ok = buffer->Write(&pod, pod.block_size);
 620       pod.block_size = 8;
 621     }
 622     return ok;
 623   }
 624   RelocBlockPOD pod;
 625 };
 626
 627 // static
 628 // Updates |rvas| so |rvas[label.index_] == label.rva_| for each |label| in
 629 // |label_manager|, assuming |label.index_| is properly assigned. Takes care of
 630 // |rvas| resizing. Unused slots in |rvas| are assigned |kUnassignedRVA|.
 631 // Returns true on success, and false otherwise.
 632 CheckBool EncodedProgram::WriteRvasToList(const LabelManager& label_manager,
 633                                           RvaVector* rvas) {
 634   rvas->clear();
 635   int index_bound = LabelManager::GetLabelIndexBound(label_manager.Labels());
 636   if (!rvas->resize(index_bound, kUnassignedRVA))
 637     return false;
 638
 639   // For each Label, write its RVA to assigned index.
 640   for (const Label& label : label_manager.Labels()) {
 641     DCHECK_NE(label.index_, Label::kNoIndex);
 642     DCHECK_EQ((*rvas)[label.index_], kUnassignedRVA)
 643         << "ExportToList() double assigned " << label.index_;
 644     (*rvas)[label.index_] = label.rva_;
 645   }
 646   return true;
 647 }
 648
 649 // static
 650 // Replaces all unassigned slots in |rvas| with the value at the previous index
 651 // so they delta-encode to zero. (There might be better values than zero. The
 652 // way to get that is have the higher level assembly program assign the
 653 // unassigned slots.)
 654 void EncodedProgram::FillUnassignedRvaSlots(RvaVector* rvas) {
 655   RVA previous = 0;
 656   for (RVA& rva : *rvas) {
 657     if (rva == kUnassignedRVA)
 658       rva = previous;
 659     else
 660       previous = rva;
 661   }
 662 }
 663
 664 CheckBool EncodedProgram::GeneratePeRelocations(SinkStream* buffer,
 665                                                 uint8_t type) {
 666   std::sort(abs32_relocs_.begin(), abs32_relocs_.end());
 667   DCHECK(abs32_relocs_.empty() || abs32_relocs_.back() != kUnassignedRVA);
 668
 669   RelocBlock block;
 670
 671   bool ok = true;
 672   for (size_t i = 0;  ok && i < abs32_relocs_.size();  ++i) {
 673     uint32_t rva = abs32_relocs_[i];
 674     uint32_t page_rva = rva & ~0xFFF;
 675     if (page_rva != block.pod.page_rva) {
 676       ok &= block.Flush(buffer);
 677       block.pod.page_rva = page_rva;
 678     }
 679     if (ok)
 680       block.Add(((static_cast<uint16_t>(type)) << 12) | (rva & 0xFFF));
 681   }
 682   ok &= block.Flush(buffer);
 683   return ok;
 684 }
 685
 686 CheckBool EncodedProgram::GenerateElfRelocations(Elf32_Word r_info,
 687                                                  SinkStream* buffer) {
 688   std::sort(abs32_relocs_.begin(), abs32_relocs_.end());
 689   DCHECK(abs32_relocs_.empty() || abs32_relocs_.back() != kUnassignedRVA);
 690
 691   Elf32_Rel relocation_block;
 692
 693   relocation_block.r_info = r_info;
 694
 695   bool ok = true;
 696   for (size_t i = 0;  ok && i < abs32_relocs_.size();  ++i) {
 697     relocation_block.r_offset = abs32_relocs_[i];
 698     ok = buffer->Write(&relocation_block, sizeof(Elf32_Rel));
 699   }
 700
 701   return ok;
 702 }
 703 ////////////////////////////////////////////////////////////////////////////////
 704
 705 Status WriteEncodedProgram(EncodedProgram* encoded, SinkStreamSet* sink) {
 706   if (!encoded->WriteTo(sink))
 707     return C_STREAM_ERROR;
 708   return C_OK;
 709 }
 710
 711 Status ReadEncodedProgram(SourceStreamSet* streams,
 712                           std::unique_ptr<EncodedProgram>* output) {
 713   output->reset();
 714   std::unique_ptr<EncodedProgram> encoded(new EncodedProgram());
 715   if (!encoded->ReadFrom(streams))
 716     return C_DESERIALIZATION_FAILED;
 717
 718   *output = std::move(encoded);
 719   return C_OK;
 720 }
 721
 722 Status Assemble(EncodedProgram* encoded, SinkStream* buffer) {
 723   bool assembled = encoded->AssembleTo(buffer);
 724   if (assembled)
 725     return C_OK;
 726   return C_ASSEMBLY_FAILED;
 727 }
 728
 729 }  // namespace courgette