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/string_util.h"
  16 #include "base/utf_string_conversions.h"
  17 #include "courgette/courgette.h"
  18 #include "courgette/streams.h"
  19
  20 namespace courgette {
  21
  22 // Stream indexes.
  23 const int kStreamMisc    = 0;
  24 const int kStreamOps     = 1;
  25 const int kStreamBytes   = 2;
  26 const int kStreamAbs32Indexes = 3;
  27 const int kStreamRel32Indexes = 4;
  28 const int kStreamAbs32Addresses = 5;
  29 const int kStreamRel32Addresses = 6;
  30 const int kStreamCopyCounts = 7;
  31 const int kStreamOriginAddresses = kStreamMisc;
  32
  33 const int kStreamLimit = 9;
  34
  35 // Constructor is here rather than in the header.  Although the constructor
  36 // appears to do nothing it is fact quite large because of the implicit calls to
  37 // field constructors.  Ditto for the destructor.
  38 EncodedProgram::EncodedProgram() : image_base_(0) {}
  39 EncodedProgram::~EncodedProgram() {}
  40
  41 // Serializes a vector of integral values using Varint32 coding.
  42 template<typename V>
  43 CheckBool WriteVector(const V& items, SinkStream* buffer) {
  44   size_t count = items.size();
  45   bool ok = buffer->WriteSizeVarint32(count);
  46   for (size_t i = 0; ok && i < count;  ++i) {
  47     COMPILE_ASSERT(sizeof(items[0]) <= sizeof(uint32),  // NOLINT
  48                    T_must_fit_in_uint32);
  49     ok = buffer->WriteSizeVarint32(items[i]);
  50   }
  51   return ok;
  52 }
  53
  54 template<typename V>
  55 bool ReadVector(V* items, SourceStream* buffer) {
  56   uint32 count;
  57   if (!buffer->ReadVarint32(&count))
  58     return false;
  59
  60   items->clear();
  61
  62   bool ok = items->reserve(count);
  63   for (size_t i = 0;  ok && i < count;  ++i) {
  64     uint32 item;
  65     ok = buffer->ReadVarint32(&item);
  66     if (ok)
  67       ok = items->push_back(static_cast<typename V::value_type>(item));
  68   }
  69
  70   return ok;
  71 }
  72
  73 // Serializes a vector, using delta coding followed by Varint32 coding.
  74 template<typename V>
  75 CheckBool WriteU32Delta(const V& set, SinkStream* buffer) {
  76   size_t count = set.size();
  77   bool ok = buffer->WriteSizeVarint32(count);
  78   uint32 prev = 0;
  79   for (size_t i = 0;  ok && i < count;  ++i) {
  80     uint32 current = set[i];
  81     uint32 delta = current - prev;
  82     ok = buffer->WriteVarint32(delta);
  83     prev = current;
  84   }
  85   return ok;
  86 }
  87
  88 template <typename V>
  89 static CheckBool ReadU32Delta(V* set, SourceStream* buffer) {
  90   uint32 count;
  91
  92   if (!buffer->ReadVarint32(&count))
  93     return false;
  94
  95   set->clear();
  96   bool ok = set->reserve(count);
  97   uint32 prev = 0;
  98
  99   for (size_t i = 0; ok && i < count;  ++i) {
 100     uint32 delta;
 101     ok = buffer->ReadVarint32(&delta);
 102     if (ok) {
 103       uint32 current = prev + delta;
 104       ok = set->push_back(current);
 105       prev = current;
 106     }
 107   }
 108
 109   return ok;
 110 }
 111
 112 // Write a vector as the byte representation of the contents.
 113 //
 114 // (This only really makes sense for a type T that has sizeof(T)==1, otherwise
 115 // serialized representation is not endian-agnostic.  But it is useful to keep
 116 // the possibility of a greater size for experiments comparing Varint32 encoding
 117 // of a vector of larger integrals vs a plain form.)
 118 //
 119 template<typename V>
 120 CheckBool WriteVectorU8(const V& items, SinkStream* buffer) {
 121   size_t count = items.size();
 122   bool ok = buffer->WriteSizeVarint32(count);
 123   if (count != 0 && ok) {
 124     size_t byte_count = count * sizeof(typename V::value_type);
 125     ok = buffer->Write(static_cast<const void*>(&items[0]), byte_count);
 126   }
 127   return ok;
 128 }
 129
 130 template<typename V>
 131 bool ReadVectorU8(V* items, SourceStream* buffer) {
 132   uint32 count;
 133   if (!buffer->ReadVarint32(&count))
 134     return false;
 135
 136   items->clear();
 137   bool ok = items->resize(count, 0);
 138   if (ok && count != 0) {
 139     size_t byte_count = count * sizeof(typename V::value_type);
 140     return buffer->Read(static_cast<void*>(&((*items)[0])), byte_count);
 141   }
 142   return ok;
 143 }
 144
 145 ////////////////////////////////////////////////////////////////////////////////
 146
 147 CheckBool EncodedProgram::DefineRel32Label(int index, RVA value) {
 148   return DefineLabelCommon(&rel32_rva_, index, value);
 149 }
 150
 151 CheckBool EncodedProgram::DefineAbs32Label(int index, RVA value) {
 152   return DefineLabelCommon(&abs32_rva_, index, value);
 153 }
 154
 155 static const RVA kUnassignedRVA = static_cast<RVA>(-1);
 156
 157 CheckBool EncodedProgram::DefineLabelCommon(RvaVector* rvas,
 158                                             int index,
 159                                             RVA rva) {
 160   bool ok = true;
 161   if (static_cast<int>(rvas->size()) <= index)
 162     ok = rvas->resize(index + 1, kUnassignedRVA);
 163
 164   if (ok) {
 165     DCHECK_EQ((*rvas)[index], kUnassignedRVA)
 166         << "DefineLabel double assigned " << index;
 167     (*rvas)[index] = rva;
 168   }
 169
 170   return ok;
 171 }
 172
 173 void EncodedProgram::EndLabels() {
 174   FinishLabelsCommon(&abs32_rva_);
 175   FinishLabelsCommon(&rel32_rva_);
 176 }
 177
 178 void EncodedProgram::FinishLabelsCommon(RvaVector* rvas) {
 179   // Replace all unassigned slots with the value at the previous index so they
 180   // delta-encode to zero.  (There might be better values than zero.  The way to
 181   // get that is have the higher level assembly program assign the unassigned
 182   // slots.)
 183   RVA previous = 0;
 184   size_t size = rvas->size();
 185   for (size_t i = 0;  i < size;  ++i) {
 186     if ((*rvas)[i] == kUnassignedRVA)
 187       (*rvas)[i] = previous;
 188     else
 189       previous = (*rvas)[i];
 190   }
 191 }
 192
 193 CheckBool EncodedProgram::AddOrigin(RVA origin) {
 194   return ops_.push_back(ORIGIN) && origins_.push_back(origin);
 195 }
 196
 197 CheckBool EncodedProgram::AddCopy(uint32 count, const void* bytes) {
 198   const uint8* source = static_cast<const uint8*>(bytes);
 199
 200   bool ok = true;
 201
 202   // Fold adjacent COPY instructions into one.  This nearly halves the size of
 203   // an EncodedProgram with only COPY1 instructions since there are approx plain
 204   // 16 bytes per reloc.  This has a working-set benefit during decompression.
 205   // For compression of files with large differences this makes a small (4%)
 206   // improvement in size.  For files with small differences this degrades the
 207   // compressed size by 1.3%
 208   if (!ops_.empty()) {
 209     if (ops_.back() == COPY1) {
 210       ops_.back() = COPY;
 211       ok = copy_counts_.push_back(1);
 212     }
 213     if (ok && ops_.back() == COPY) {
 214       copy_counts_.back() += count;
 215       for (uint32 i = 0; ok && i < count; ++i) {
 216         ok = copy_bytes_.push_back(source[i]);
 217       }
 218       return ok;
 219     }
 220   }
 221
 222   if (ok) {
 223     if (count == 1) {
 224       ok = ops_.push_back(COPY1) && copy_bytes_.push_back(source[0]);
 225     } else {
 226       ok = ops_.push_back(COPY) && copy_counts_.push_back(count);
 227       for (uint32 i = 0; ok && i < count; ++i) {
 228         ok = copy_bytes_.push_back(source[i]);
 229       }
 230     }
 231   }
 232
 233   return ok;
 234 }
 235
 236 CheckBool EncodedProgram::AddAbs32(int label_index) {
 237   return ops_.push_back(ABS32) && abs32_ix_.push_back(label_index);
 238 }
 239
 240 CheckBool EncodedProgram::AddRel32(int label_index) {
 241   return ops_.push_back(REL32) && rel32_ix_.push_back(label_index);
 242 }
 243
 244 CheckBool EncodedProgram::AddMakeRelocs() {
 245   return ops_.push_back(MAKE_BASE_RELOCATION_TABLE);
 246 }
 247
 248 void EncodedProgram::DebuggingSummary() {
 249   VLOG(1) << "EncodedProgram Summary"
 250           << "\n  image base  " << image_base_
 251           << "\n  abs32 rvas  " << abs32_rva_.size()
 252           << "\n  rel32 rvas  " << rel32_rva_.size()
 253           << "\n  ops         " << ops_.size()
 254           << "\n  origins     " << origins_.size()
 255           << "\n  copy_counts " << copy_counts_.size()
 256           << "\n  copy_bytes  " << copy_bytes_.size()
 257           << "\n  abs32_ix    " << abs32_ix_.size()
 258           << "\n  rel32_ix    " << rel32_ix_.size();
 259 }
 260
 261 ////////////////////////////////////////////////////////////////////////////////
 262
 263 // For algorithm refinement purposes it is useful to write subsets of the file
 264 // format.  This gives us the ability to estimate the entropy of the
 265 // differential compression of the individual streams, which can provide
 266 // invaluable insights.  The default, of course, is to include all the streams.
 267 //
 268 enum FieldSelect {
 269   INCLUDE_ABS32_ADDRESSES = 0x0001,
 270   INCLUDE_REL32_ADDRESSES = 0x0002,
 271   INCLUDE_ABS32_INDEXES   = 0x0010,
 272   INCLUDE_REL32_INDEXES   = 0x0020,
 273   INCLUDE_OPS             = 0x0100,
 274   INCLUDE_BYTES           = 0x0200,
 275   INCLUDE_COPY_COUNTS     = 0x0400,
 276   INCLUDE_MISC            = 0x1000
 277 };
 278
 279 static FieldSelect GetFieldSelect() {
 280 #if 1
 281   // TODO(sra): Use better configuration.
 282   scoped_ptr<base::Environment> env(base::Environment::Create());
 283   std::string s;
 284   env->GetVar("A_FIELDS", &s);
 285   if (!s.empty()) {
 286     return static_cast<FieldSelect>(wcstoul(ASCIIToWide(s).c_str(), 0, 0));
 287   }
 288 #endif
 289   return  static_cast<FieldSelect>(~0);
 290 }
 291
 292 CheckBool EncodedProgram::WriteTo(SinkStreamSet* streams) {
 293   FieldSelect select = GetFieldSelect();
 294
 295   // The order of fields must be consistent in WriteTo and ReadFrom, regardless
 296   // of the streams used.  The code can be configured with all kStreamXXX
 297   // constants the same.
 298   //
 299   // If we change the code to pipeline reading with assembly (to avoid temporary
 300   // storage vectors by consuming operands directly from the stream) then we
 301   // need to read the base address and the random access address tables first,
 302   // the rest can be interleaved.
 303
 304   if (select & INCLUDE_MISC) {
 305     // TODO(sra): write 64 bits.
 306     if (!streams->stream(kStreamMisc)->WriteVarint32(
 307             static_cast<uint32>(image_base_))) {
 308       return false;
 309     }
 310   }
 311
 312   bool success = true;
 313
 314   if (select & INCLUDE_ABS32_ADDRESSES) {
 315     success &= WriteU32Delta(abs32_rva_,
 316                              streams->stream(kStreamAbs32Addresses));
 317   }
 318
 319   if (select & INCLUDE_REL32_ADDRESSES) {
 320     success &= WriteU32Delta(rel32_rva_,
 321                              streams->stream(kStreamRel32Addresses));
 322   }
 323
 324   if (select & INCLUDE_MISC)
 325     success &= WriteVector(origins_, streams->stream(kStreamOriginAddresses));
 326
 327   if (select & INCLUDE_OPS) {
 328     // 5 for length.
 329     success &= streams->stream(kStreamOps)->Reserve(ops_.size() + 5);
 330     success &= WriteVector(ops_, streams->stream(kStreamOps));
 331   }
 332
 333   if (select & INCLUDE_COPY_COUNTS)
 334     success &= WriteVector(copy_counts_, streams->stream(kStreamCopyCounts));
 335
 336   if (select & INCLUDE_BYTES)
 337     success &= WriteVectorU8(copy_bytes_, streams->stream(kStreamBytes));
 338
 339   if (select & INCLUDE_ABS32_INDEXES)
 340     success &= WriteVector(abs32_ix_, streams->stream(kStreamAbs32Indexes));
 341
 342   if (select & INCLUDE_REL32_INDEXES)
 343     success &= WriteVector(rel32_ix_, streams->stream(kStreamRel32Indexes));
 344
 345   return success;
 346 }
 347
 348 bool EncodedProgram::ReadFrom(SourceStreamSet* streams) {
 349   // TODO(sra): read 64 bits.
 350   uint32 temp;
 351   if (!streams->stream(kStreamMisc)->ReadVarint32(&temp))
 352     return false;
 353   image_base_ = temp;
 354
 355   if (!ReadU32Delta(&abs32_rva_, streams->stream(kStreamAbs32Addresses)))
 356     return false;
 357   if (!ReadU32Delta(&rel32_rva_, streams->stream(kStreamRel32Addresses)))
 358     return false;
 359   if (!ReadVector(&origins_, streams->stream(kStreamOriginAddresses)))
 360     return false;
 361   if (!ReadVector(&ops_, streams->stream(kStreamOps)))
 362     return false;
 363   if (!ReadVector(&copy_counts_, streams->stream(kStreamCopyCounts)))
 364     return false;
 365   if (!ReadVectorU8(&copy_bytes_, streams->stream(kStreamBytes)))
 366     return false;
 367   if (!ReadVector(&abs32_ix_, streams->stream(kStreamAbs32Indexes)))
 368     return false;
 369   if (!ReadVector(&rel32_ix_, streams->stream(kStreamRel32Indexes)))
 370     return false;
 371
 372   // Check that streams have been completely consumed.
 373   for (int i = 0;  i < kStreamLimit;  ++i) {
 374     if (streams->stream(i)->Remaining() > 0)
 375       return false;
 376   }
 377
 378   return true;
 379 }
 380
 381 // Safe, non-throwing version of std::vector::at().  Returns 'true' for success,
 382 // 'false' for out-of-bounds index error.
 383 template<typename V, typename T>
 384 bool VectorAt(const V& v, size_t index, T* output) {
 385   if (index >= v.size())
 386     return false;
 387   *output = v[index];
 388   return true;
 389 }
 390
 391 CheckBool EncodedProgram::AssembleTo(SinkStream* final_buffer) {
 392   // For the most part, the assembly process walks the various tables.
 393   // ix_mumble is the index into the mumble table.
 394   size_t ix_origins = 0;
 395   size_t ix_copy_counts = 0;
 396   size_t ix_copy_bytes = 0;
 397   size_t ix_abs32_ix = 0;
 398   size_t ix_rel32_ix = 0;
 399
 400   RVA current_rva = 0;
 401
 402   bool pending_base_relocation_table = false;
 403   SinkStream bytes_following_base_relocation_table;
 404
 405   SinkStream* output = final_buffer;
 406
 407   for (size_t ix_ops = 0;  ix_ops < ops_.size();  ++ix_ops) {
 408     OP op = ops_[ix_ops];
 409
 410     switch (op) {
 411       default:
 412         return false;
 413
 414       case ORIGIN: {
 415         RVA section_rva;
 416         if (!VectorAt(origins_, ix_origins, &section_rva))
 417           return false;
 418         ++ix_origins;
 419         current_rva = section_rva;
 420         break;
 421       }
 422
 423       case COPY: {
 424         uint32 count;
 425         if (!VectorAt(copy_counts_, ix_copy_counts, &count))
 426           return false;
 427         ++ix_copy_counts;
 428         for (uint32 i = 0;  i < count;  ++i) {
 429           uint8 b;
 430           if (!VectorAt(copy_bytes_, ix_copy_bytes, &b))
 431             return false;
 432           ++ix_copy_bytes;
 433           if (!output->Write(&b, 1))
 434             return false;
 435         }
 436         current_rva += count;
 437         break;
 438       }
 439
 440       case COPY1: {
 441         uint8 b;
 442         if (!VectorAt(copy_bytes_, ix_copy_bytes, &b))
 443           return false;
 444         ++ix_copy_bytes;
 445         if (!output->Write(&b, 1))
 446           return false;
 447         current_rva += 1;
 448         break;
 449       }
 450
 451       case REL32: {
 452         uint32 index;
 453         if (!VectorAt(rel32_ix_, ix_rel32_ix, &index))
 454           return false;
 455         ++ix_rel32_ix;
 456         RVA rva;
 457         if (!VectorAt(rel32_rva_, index, &rva))
 458           return false;
 459         uint32 offset = (rva - (current_rva + 4));
 460         if (!output->Write(&offset, 4))
 461           return false;
 462         current_rva += 4;
 463         break;
 464       }
 465
 466       case ABS32: {
 467         uint32 index;
 468         if (!VectorAt(abs32_ix_, ix_abs32_ix, &index))
 469           return false;
 470         ++ix_abs32_ix;
 471         RVA rva;
 472         if (!VectorAt(abs32_rva_, index, &rva))
 473           return false;
 474         uint32 abs32 = static_cast<uint32>(rva + image_base_);
 475         if (!abs32_relocs_.push_back(current_rva) || !output->Write(&abs32, 4))
 476           return false;
 477         current_rva += 4;
 478         break;
 479       }
 480
 481       case MAKE_BASE_RELOCATION_TABLE: {
 482         // We can see the base relocation anywhere, but we only have the
 483         // information to generate it at the very end.  So we divert the bytes
 484         // we are generating to a temporary stream.
 485         if (pending_base_relocation_table)  // Can't have two base relocation
 486                                             // tables.
 487           return false;
 488
 489         pending_base_relocation_table = true;
 490         output = &bytes_following_base_relocation_table;
 491         break;
 492         // There is a potential problem *if* the instruction stream contains
 493         // some REL32 relocations following the base relocation and in the same
 494         // section.  We don't know the size of the table, so 'current_rva' will
 495         // be wrong, causing REL32 offsets to be miscalculated.  This never
 496         // happens; the base relocation table is usually in a section of its
 497         // own, a data-only section, and following everything else in the
 498         // executable except some padding zero bytes.  We could fix this by
 499         // emitting an ORIGIN after the MAKE_BASE_RELOCATION_TABLE.
 500       }
 501     }
 502   }
 503
 504   if (pending_base_relocation_table) {
 505     if (!GenerateBaseRelocations(final_buffer) ||
 506         !final_buffer->Append(&bytes_following_base_relocation_table))
 507       return false;
 508   }
 509
 510   // Final verification check: did we consume all lists?
 511   if (ix_copy_counts != copy_counts_.size())
 512     return false;
 513   if (ix_copy_bytes != copy_bytes_.size())
 514     return false;
 515   if (ix_abs32_ix != abs32_ix_.size())
 516     return false;
 517   if (ix_rel32_ix != rel32_ix_.size())
 518     return false;
 519
 520   return true;
 521 }
 522
 523 // RelocBlock has the layout of a block of relocations in the base relocation
 524 // table file format.
 525 //
 526 struct RelocBlockPOD {
 527   uint32 page_rva;
 528   uint32 block_size;
 529   uint16 relocs[4096];  // Allow up to one relocation per byte of a 4k page.
 530 };
 531
 532 COMPILE_ASSERT(offsetof(RelocBlockPOD, relocs) == 8, reloc_block_header_size);
 533
 534 class RelocBlock {
 535  public:
 536   RelocBlock() {
 537     pod.page_rva = ~0;
 538     pod.block_size = 8;
 539   }
 540
 541   void Add(uint16 item) {
 542     pod.relocs[(pod.block_size-8)/2] = item;
 543     pod.block_size += 2;
 544   }
 545
 546   CheckBool Flush(SinkStream* buffer) WARN_UNUSED_RESULT {
 547     bool ok = true;
 548     if (pod.block_size != 8) {
 549       if (pod.block_size % 4 != 0) {  // Pad to make size multiple of 4 bytes.
 550         Add(0);
 551       }
 552       ok = buffer->Write(&pod, pod.block_size);
 553       pod.block_size = 8;
 554     }
 555     return ok;
 556   }
 557   RelocBlockPOD pod;
 558 };
 559
 560 CheckBool EncodedProgram::GenerateBaseRelocations(SinkStream* buffer) {
 561   std::sort(abs32_relocs_.begin(), abs32_relocs_.end());
 562
 563   RelocBlock block;
 564
 565   bool ok = true;
 566   for (size_t i = 0;  ok && i < abs32_relocs_.size();  ++i) {
 567     uint32 rva = abs32_relocs_[i];
 568     uint32 page_rva = rva & ~0xFFF;
 569     if (page_rva != block.pod.page_rva) {
 570       ok &= block.Flush(buffer);
 571       block.pod.page_rva = page_rva;
 572     }
 573     if (ok)
 574       block.Add(0x3000 | (rva & 0xFFF));
 575   }
 576   ok &= block.Flush(buffer);
 577   return ok;
 578 }
 579
 580 ////////////////////////////////////////////////////////////////////////////////
 581
 582 Status WriteEncodedProgram(EncodedProgram* encoded, SinkStreamSet* sink) {
 583   if (!encoded->WriteTo(sink))
 584     return C_STREAM_ERROR;
 585   return C_OK;
 586 }
 587
 588 Status ReadEncodedProgram(SourceStreamSet* streams, EncodedProgram** output) {
 589   EncodedProgram* encoded = new EncodedProgram();
 590   if (encoded->ReadFrom(streams)) {
 591     *output = encoded;
 592     return C_OK;
 593   }
 594   delete encoded;
 595   return C_DESERIALIZATION_FAILED;
 596 }
 597
 598 Status Assemble(EncodedProgram* encoded, SinkStream* buffer) {
 599   bool assembled = encoded->AssembleTo(buffer);
 600   if (assembled)
 601     return C_OK;
 602   return C_ASSEMBLY_FAILED;
 603 }
 604
 605 void DeleteEncodedProgram(EncodedProgram* encoded) {
 606   delete encoded;
 607 }
 608
 609 }  // end namespace