courgette/encoded_program.cc

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