courgette/adjustment_method_2.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/adjustment_method.h"
   6
   7 #include <stddef.h>
   8 #include <stdint.h>
   9
  10 #include <algorithm>
  11 #include <limits>
  12 #include <list>
  13 #include <map>
  14 #include <set>
  15 #include <string>
  16 #include <vector>
  17
  18 #include "base/format_macros.h"
  19 #include "base/logging.h"
  20 #include "base/macros.h"
  21 #include "base/strings/stringprintf.h"
  22 #include "base/time/time.h"
  23 #include "courgette/assembly_program.h"
  24 #include "courgette/courgette.h"
  25 #include "courgette/encoded_program.h"
  26
  27 /*
  28
  29 Shingle weighting matching.
  30
  31 We have a sequence S1 of symbols from alphabet A1={A,B,C,...} called the 'model'
  32 and a second sequence of S2 of symbols from alphabet A2={U,V,W,....} called the
  33 'program'.  Each symbol in A1 has a unique numerical name or index.  We can
  34 transcribe the sequence S1 to a sequence T1 of indexes of the symbols. We wish
  35 to assign indexes to the symbols in A2 so that when we transcribe S2 into T2, T2
  36 has long subsequences that occur in T1.  This will ensure that the sequence
  37 T1;T2 compresses to be only slightly larger than the compressed T1.
  38
  39 The algorithm for matching members of S2 with members of S1 is eager - it makes
  40 matches without backtracking, until no more matches can be made.  Each variable
  41 (symbol) U,V,... in A2 has a set of candidates from A1, each candidate with a
  42 weight summarizing the evidence for the match.  We keep a VariableQueue of
  43 U,V,... sorted by how much the evidence for the best choice outweighs the
  44 evidence for the second choice, i.e. prioritized by how 'clear cut' the best
  45 assignment is.  We pick the variable with the most clear-cut candidate, make the
  46 assignment, adjust the evidence and repeat.
  47
  48 What has not been described so far is how the evidence is gathered and
  49 maintained.  We are working under the assumption that S1 and S2 are largely
  50 similar.  (A different assumption might be that S1 and S2 are dissimilar except
  51 for many long subsequences.)
  52
  53 A naive algorithm would consider all pairs (A,U) and for each pair assess the
  54 benefit, or score, the assignment U:=A.  The score might count the number of
  55 occurrences of U in S2 which appear in similar contexts to A in S1.
  56
  57 To distinguish contexts we view S1 and S2 as a sequence of overlapping k-length
  58 substrings or 'shingles'.  Two shingles are compatible if the symbols in one
  59 shingle could be matched with the symbols in the other symbol.  For example, ABC
  60 is *not* compatible with UVU because it would require conflicting matches A=U
  61 and C=U.  ABC is compatible with UVW, UWV, WUV, VUW etc.  We can't tell which
  62 until we make an assignment - the compatible shingles form an equivalence class.
  63 After assigning U:=A then only UVW and UWV (equivalently AVW, AWV) are
  64 compatible.  As we make assignments the number of equivalence classes of
  65 shingles increases and the number of members of each equivalence class
  66 decreases.  The compatibility test becomes more restrictive.
  67
  68 We gather evidence for the potential assignment U:=A by counting how many
  69 shingles containing U are compatible with shingles containing A.  Thus symbols
  70 occurring a large number of times in compatible contexts will be assigned first.
  71
  72 Finding the 'most clear-cut' assignment by considering all pairs symbols and for
  73 each pair comparing the contexts of each pair of occurrences of the symbols is
  74 computationally infeasible.  We get the job done in a reasonable time by
  75 approaching it 'backwards' and making incremental changes as we make
  76 assignments.
  77
  78 First the shingles are partitioned according to compatibility.  In S1=ABCDD and
  79 S2=UVWXX we have a total of 6 shingles, each occuring once. (ABC:1 BCD:1 CDD:1;
  80 UVW:1 VWX: WXX:1) all fit the pattern <V0 V1 V2> or the pattern <V0 V1 V1>.  The
  81 first pattern indicates that each position matches a different symbol, the
  82 second pattern indicates that the second symbol is repeated.
  83
  84   pattern      S1 members      S2 members
  85   <V0 V1 V2>:  {ABC:1, BCD:1}; {UVW:1, VWX:1}
  86   <V0 V1 V1>:  {CDD:1}         {WXX:1}
  87
  88 The second pattern appears to have a unique assignment but we don't make the
  89 assignment on such scant evidence.  If S1 and S2 do not match exactly, there
  90 will be numerous spurious low-score matches like this.  Instead we must see what
  91 assignments are indicated by considering all of the evidence.
  92
  93 First pattern has 2 x 2 = 4 shingle pairs.  For each pair we count the number
  94 of symbol assignments.  For ABC:a * UVW:b accumulate min(a,b) to each of
  95   {U:=A, V:=B, W:=C}.
  96 After accumulating over all 2 x 2 pairs:
  97   U: {A:1  B:1}
  98   V: {A:1  B:2  C:1}
  99   W: {B:1  C:2  D:1 }
 100   X: {C:1  D:1}
 101 The second pattern contributes:
 102   W: {C:1}
 103   X: {D:2}
 104 Sum:
 105   U: {A:1  B:1}
 106   V: {A:1  B:2  C:1}
 107   W: {B:1  C:3  D:1}
 108   X: {C:1  D:3}
 109
 110 From this we decide to assign X:=D (because this assignment has both the largest
 111 difference above the next candidate (X:=C) and this is also the largest
 112 proportionately over the sum of alternatives).
 113
 114 Lets assume D has numerical 'name' 77.  The assignment X:=D sets X to 77 too.
 115 Next we repartition all the shingles containing X or D:
 116
 117   pattern      S1 members      S2 members
 118   <V0 V1 V2>:  {ABC:1};        {UVW:1}
 119   <V0 V1 77>:  {BCD:1};        {VWX:1}
 120   <V0 77 77>:  {CDD:1}         {WXX:1}
 121 As we repartition, we recalculate the contributions to the scores:
 122   U: {A:1}
 123   V: {B:2}
 124   W: {C:3}
 125 All the remaining assignments are now fixed.
 126
 127 There is one step in the incremental algorithm that is still infeasibly
 128 expensive: the contributions due to the cross product of large equivalence
 129 classes.  We settle for making an approximation by computing the contribution of
 130 the cross product of only the most common shingles.  The hope is that the noise
 131 from the long tail of uncounted shingles is well below the scores being used to
 132 pick assignments.  The second hope is that as assignment are made, the large
 133 equivalence class will be partitioned into smaller equivalence classes, reducing
 134 the noise over time.
 135
 136 In the code below the shingles are bigger (Shingle::kWidth = 5).
 137 Class ShinglePattern holds the data for one pattern.
 138
 139 There is an optimization for this case:
 140   <V0 V1 V1>:  {CDD:1}         {WXX:1}
 141
 142 Above we said that we don't make an assignment on this "scant evidence".  There
 143 is an exception: if there is only one variable unassigned (more like the <V0 77
 144 77> pattern) AND there are no occurrences of C and W other than those counted in
 145 this pattern, then there is no competing evidence and we go ahead with the
 146 assignment immediately.  This produces slightly better results because these
 147 cases tend to be low-scoring and susceptible to small mistakes made in
 148 low-scoring assignments in the approximation for large equivalence classes.
 149
 150 */
 151
 152 namespace courgette {
 153 namespace adjustment_method_2 {
 154
 155 ////////////////////////////////////////////////////////////////////////////////
 156
 157 class AssignmentCandidates;
 158 class LabelInfoMaker;
 159 class Shingle;
 160 class ShinglePattern;
 161
 162 // The purpose of adjustment is to assign indexes to Labels of a program 'p' to
 163 // make the sequence of indexes similar to a 'model' program 'm'.  Labels
 164 // themselves don't have enough information to do this job, so we work with a
 165 // LabelInfo surrogate for each label.
 166 //
 167 class LabelInfo {
 168  public:
 169   // Just a no-argument constructor and copy constructor.  Actual LabelInfo
 170   // objects are allocated in std::pair structs in a std::map.
 171   LabelInfo()
 172       : label_(NULL), is_model_(false), debug_index_(0), refs_(0),
 173         assignment_(NULL), candidates_(NULL)
 174   {}
 175
 176   ~LabelInfo();
 177
 178   AssignmentCandidates* candidates();
 179
 180   Label* label_;             // The label that this info a surrogate for.
 181
 182   uint32_t is_model_ : 1;      // Is the label in the model?
 183   uint32_t debug_index_ : 31;  // A small number for naming the label in debug
 184                                // output. The pair (is_model_, debug_index_) is
 185                                // unique.
 186
 187   int refs_;                 // Number of times this Label is referenced.
 188
 189   LabelInfo* assignment_;    // Label from other program corresponding to this.
 190
 191   std::vector<uint32_t> positions_;  // Offsets into the trace of references.
 192
 193  private:
 194   AssignmentCandidates* candidates_;
 195
 196   void operator=(const LabelInfo*);  // Disallow assignment only.
 197   // Public compiler generated copy constructor is needed to constuct
 198   // std::pair<Label*, LabelInfo> so that fresh LabelInfos can be allocated
 199   // inside a std::map.
 200 };
 201
 202 typedef std::vector<LabelInfo*> Trace;
 203
 204 std::string ToString(const LabelInfo* info) {
 205   std::string s;
 206   base::StringAppendF(&s, "%c%d", "pm"[info->is_model_], info->debug_index_);
 207   if (info->label_->index_ != Label::kNoIndex)
 208     base::StringAppendF(&s, " (%d)", info->label_->index_);
 209
 210   base::StringAppendF(&s, " #%u", info->refs_);
 211   return s;
 212 }
 213
 214 // LabelInfoMaker maps labels to their surrogate LabelInfo objects.
 215 class LabelInfoMaker {
 216  public:
 217   LabelInfoMaker() : debug_label_index_gen_(0) {}
 218
 219   LabelInfo* MakeLabelInfo(Label* label, bool is_model, uint32_t position) {
 220     LabelInfo& slot = label_infos_[label];
 221     if (slot.label_ == NULL) {
 222       slot.label_ = label;
 223       slot.is_model_ = is_model;
 224       slot.debug_index_ = ++debug_label_index_gen_;
 225     }
 226     slot.positions_.push_back(position);
 227     ++slot.refs_;
 228     return &slot;
 229   }
 230
 231   void ResetDebugLabel() { debug_label_index_gen_ = 0; }
 232
 233  private:
 234   int debug_label_index_gen_;
 235
 236   // Note LabelInfo is allocated 'flat' inside map::value_type, so the LabelInfo
 237   // lifetimes are managed by the map.
 238   std::map<Label*, LabelInfo> label_infos_;
 239
 240   DISALLOW_COPY_AND_ASSIGN(LabelInfoMaker);
 241 };
 242
 243 struct OrderLabelInfo {
 244   bool operator()(const LabelInfo* a, const LabelInfo* b) const {
 245     if (a->label_->rva_ < b->label_->rva_) return true;
 246     if (a->label_->rva_ > b->label_->rva_) return false;
 247     if (a == b) return false;
 248     return a->positions_ < b->positions_;  // Lexicographic ordering of vector.
 249   }
 250 };
 251
 252 // AssignmentCandidates is a priority queue of candidate assignments to
 253 // a single program LabelInfo, |program_info_|.
 254 class AssignmentCandidates {
 255  public:
 256   explicit AssignmentCandidates(LabelInfo* program_info)
 257       : program_info_(program_info) {}
 258
 259   LabelInfo* program_info() const { return program_info_; }
 260
 261   bool empty() const { return label_to_score_.empty(); }
 262
 263   LabelInfo* top_candidate() const { return queue_.begin()->second; }
 264
 265   void Update(LabelInfo* model_info, int delta_score) {
 266     LOG_ASSERT(delta_score != 0);
 267     int old_score = 0;
 268     int new_score = 0;
 269     LabelToScore::iterator p = label_to_score_.find(model_info);
 270     if (p != label_to_score_.end()) {
 271       old_score = p->second;
 272       new_score = old_score + delta_score;
 273       queue_.erase(ScoreAndLabel(old_score, p->first));
 274       if (new_score == 0) {
 275         label_to_score_.erase(p);
 276       } else {
 277         p->second = new_score;
 278         queue_.insert(ScoreAndLabel(new_score, model_info));
 279       }
 280     } else {
 281       new_score = delta_score;
 282       label_to_score_.insert(std::make_pair(model_info, new_score));
 283       queue_.insert(ScoreAndLabel(new_score, model_info));
 284     }
 285     LOG_ASSERT(queue_.size() == label_to_score_.size());
 286   }
 287
 288   int TopScore() const {
 289     int first_value = 0;
 290     int second_value = 0;
 291     Queue::const_iterator p = queue_.begin();
 292     if (p != queue_.end()) {
 293       first_value = p->first;
 294       ++p;
 295       if (p != queue_.end()) {
 296         second_value = p->first;
 297       }
 298     }
 299     return first_value - second_value;
 300   }
 301
 302   bool HasPendingUpdates() { return !pending_updates_.empty(); }
 303
 304   void AddPendingUpdate(LabelInfo* model_info, int delta_score) {
 305     LOG_ASSERT(delta_score != 0);
 306     pending_updates_[model_info] += delta_score;
 307   }
 308
 309   void ApplyPendingUpdates() {
 310     // TODO(sra): try to walk |pending_updates_| and |label_to_score_| in
 311     // lockstep.  Try to batch updates to |queue_|.
 312     size_t zeroes = 0;
 313     for (LabelToScore::iterator p = pending_updates_.begin();
 314          p != pending_updates_.end();
 315          ++p) {
 316       if (p->second != 0)
 317         Update(p->first, p->second);
 318       else
 319         ++zeroes;
 320     }
 321     pending_updates_.clear();
 322   }
 323
 324   void Print(int max) {
 325     VLOG(2) << "score "  << TopScore() << "  " << ToString(program_info_)
 326             << " := ?";
 327     if (!pending_updates_.empty())
 328       VLOG(2) << pending_updates_.size() << " pending";
 329     int count = 0;
 330     for (Queue::iterator q = queue_.begin();  q != queue_.end();  ++q) {
 331       if (++count > max) break;
 332       VLOG(2) << "   " << q->first << "  " << ToString(q->second);
 333     }
 334   }
 335
 336  private:
 337   typedef std::map<LabelInfo*, int, OrderLabelInfo> LabelToScore;
 338   typedef std::pair<int, LabelInfo*> ScoreAndLabel;
 339   struct OrderScoreAndLabelByScoreDecreasing {
 340     OrderLabelInfo tie_breaker;
 341     bool operator()(const ScoreAndLabel& a, const ScoreAndLabel& b) const {
 342       if (a.first > b.first) return true;
 343       if (a.first < b.first) return false;
 344       return tie_breaker(a.second, b.second);
 345     }
 346   };
 347   typedef std::set<ScoreAndLabel, OrderScoreAndLabelByScoreDecreasing> Queue;
 348
 349   LabelInfo* program_info_;
 350   LabelToScore label_to_score_;
 351   LabelToScore pending_updates_;
 352   Queue queue_;
 353 };
 354
 355 AssignmentCandidates* LabelInfo::candidates() {
 356   if (candidates_ == NULL)
 357     candidates_ = new AssignmentCandidates(this);
 358   return candidates_;
 359 }
 360
 361 LabelInfo::~LabelInfo() {
 362   delete candidates_;
 363 }
 364
 365 // A Shingle is a short fixed-length string of LabelInfos that actually occurs
 366 // in a Trace.  A Shingle may occur many times.  We repesent the Shingle by the
 367 // position of one of the occurrences in the Trace.
 368 class Shingle {
 369  public:
 370   static const uint8_t kWidth = 5;
 371
 372   struct InterningLess {
 373     bool operator()(const Shingle& a, const Shingle& b) const;
 374   };
 375
 376   typedef std::set<Shingle, InterningLess> OwningSet;
 377
 378   static Shingle* Find(const Trace& trace, size_t position,
 379                        OwningSet* owning_set) {
 380     std::pair<OwningSet::iterator, bool> pair =
 381         owning_set->insert(Shingle(trace, position));
 382     // pair.first iterator 'points' to the newly inserted Shingle or the
 383     // previouly inserted one that looks the same according to the comparator.
 384
 385     // const_cast required because key is const.  We modify the Shingle
 386     // extensively but not in a way that affects InterningLess.
 387     Shingle* shingle = const_cast<Shingle*>(&*pair.first);
 388     shingle->add_position(position);
 389     return shingle;
 390   }
 391
 392   LabelInfo* at(size_t i) const { return trace_[exemplar_position_ + i]; }
 393   void add_position(size_t position) {
 394     positions_.push_back(static_cast<uint32_t>(position));
 395   }
 396   int position_count() const { return static_cast<int>(positions_.size()); }
 397
 398   bool InModel() const { return at(0)->is_model_; }
 399
 400   ShinglePattern* pattern() const { return pattern_; }
 401   void set_pattern(ShinglePattern* pattern) { pattern_ = pattern; }
 402
 403   struct PointerLess {
 404     bool operator()(const Shingle* a, const Shingle* b) const {
 405       // Arbitrary but repeatable (memory-address) independent ordering:
 406       return a->exemplar_position_ < b->exemplar_position_;
 407       // return InterningLess()(*a, *b);
 408     }
 409   };
 410
 411  private:
 412   Shingle(const Trace& trace, size_t exemplar_position)
 413       : trace_(trace),
 414         exemplar_position_(exemplar_position),
 415         pattern_(NULL) {
 416   }
 417
 418   const Trace& trace_;             // The shingle lives inside trace_.
 419   size_t exemplar_position_;       // At this position (and other positions).
 420   std::vector<uint32_t> positions_;  // Includes exemplar_position_.
 421
 422   ShinglePattern* pattern_;       // Pattern changes as LabelInfos are assigned.
 423
 424   friend std::string ToString(const Shingle* instance);
 425
 426   // We can't disallow the copy constructor because we use std::set<Shingle> and
 427   // VS2005's implementation of std::set<T>::set() requires T to have a copy
 428   // constructor.
 429   //   DISALLOW_COPY_AND_ASSIGN(Shingle);
 430   void operator=(const Shingle&) = delete;  // Disallow assignment only.
 431 };
 432
 433 std::string ToString(const Shingle* instance) {
 434   std::string s;
 435   const char* sep = "<";
 436   for (uint8_t i = 0; i < Shingle::kWidth; ++i) {
 437     // base::StringAppendF(&s, "%s%x ", sep, instance.at(i)->label_->rva_);
 438     s += sep;
 439     s += ToString(instance->at(i));
 440     sep = ", ";
 441   }
 442   base::StringAppendF(&s, ">(%" PRIuS ")@{%d}",
 443                       instance->exemplar_position_,
 444                       instance->position_count());
 445   return s;
 446 }
 447
 448
 449 bool Shingle::InterningLess::operator()(
 450     const Shingle& a,
 451     const Shingle& b) const {
 452   for (uint8_t i = 0; i < kWidth; ++i) {
 453     LabelInfo* info_a = a.at(i);
 454     LabelInfo* info_b = b.at(i);
 455     if (info_a->label_->rva_ < info_b->label_->rva_)
 456       return true;
 457     if (info_a->label_->rva_ > info_b->label_->rva_)
 458       return false;
 459     if (info_a->is_model_ < info_b->is_model_)
 460       return true;
 461     if (info_a->is_model_ > info_b->is_model_)
 462       return false;
 463     if (info_a != info_b) {
 464       NOTREACHED();
 465     }
 466   }
 467   return false;
 468 }
 469
 470 class ShinglePattern {
 471  public:
 472   enum { kOffsetMask = 7,  // Offset lives in low bits.
 473          kFixed    = 0,    // kind & kVariable == 0  => fixed.
 474          kVariable = 8     // kind & kVariable == 1  => variable.
 475          };
 476   // sequence[position + (kinds_[i] & kOffsetMask)] gives LabelInfo for position
 477   // i of shingle.  Below, second 'A' is duplicate of position 1, second '102'
 478   // is duplicate of position 0.
 479   //
 480   //   <102, A, 103, A , 102>
 481   //      --> <kFixed+0, kVariable+1, kFixed+2, kVariable+1, kFixed+0>
 482   struct Index {
 483     explicit Index(const Shingle* instance);
 484     uint8_t kinds_[Shingle::kWidth];
 485     uint8_t variables_;
 486     uint8_t unique_variables_;
 487     uint8_t first_variable_index_;
 488     uint32_t hash_;
 489     int assigned_indexes_[Shingle::kWidth];
 490   };
 491
 492   // ShinglePattern keeps histograms of member Shingle instances, ordered by
 493   // decreasing number of occurrences.  We don't have a pair (occurrence count,
 494   // Shingle instance), so we use a FreqView adapter to make the instance
 495   // pointer look like the pair.
 496   class FreqView {
 497    public:
 498     explicit FreqView(const Shingle* instance) : instance_(instance) {}
 499     int count() const { return instance_->position_count(); }
 500     const Shingle* instance() const { return instance_; }
 501     struct Greater {
 502       bool operator()(const FreqView& a, const FreqView& b) const {
 503         if (a.count() > b.count()) return true;
 504         if (a.count() < b.count()) return false;
 505         return resolve_ties(a.instance(), b.instance());
 506       }
 507      private:
 508       Shingle::PointerLess resolve_ties;
 509     };
 510    private:
 511     const Shingle* instance_;
 512   };
 513
 514   typedef std::set<FreqView, FreqView::Greater> Histogram;
 515
 516   ShinglePattern() : index_(NULL), model_coverage_(0), program_coverage_(0) {}
 517
 518   const Index* index_;  // Points to the key in the owning map value_type.
 519   Histogram model_histogram_;
 520   Histogram program_histogram_;
 521   int model_coverage_;
 522   int program_coverage_;
 523 };
 524
 525 std::string ToString(const ShinglePattern::Index* index) {
 526   std::string s;
 527   if (index == NULL) {
 528     s = "<null>";
 529   } else {
 530     base::StringAppendF(&s, "<%d: ", index->variables_);
 531     const char* sep = "";
 532     for (uint8_t i = 0; i < Shingle::kWidth; ++i) {
 533       s += sep;
 534       sep = ", ";
 535       uint32_t kind = index->kinds_[i];
 536       int offset = kind & ShinglePattern::kOffsetMask;
 537       if (kind & ShinglePattern::kVariable)
 538         base::StringAppendF(&s, "V%d", offset);
 539       else
 540         base::StringAppendF(&s, "%d", index->assigned_indexes_[offset]);
 541      }
 542     base::StringAppendF(&s, " %x", index->hash_);
 543     s += ">";
 544   }
 545   return s;
 546 }
 547
 548 std::string HistogramToString(const ShinglePattern::Histogram& histogram,
 549                               size_t snippet_max) {
 550   std::string s;
 551   size_t histogram_size = histogram.size();
 552   size_t snippet_size = 0;
 553   for (ShinglePattern::Histogram::const_iterator p = histogram.begin();
 554        p != histogram.end();
 555        ++p) {
 556     if (++snippet_size > snippet_max && snippet_size != histogram_size) {
 557       s += " ...";
 558       break;
 559     }
 560     base::StringAppendF(&s, " %d", p->count());
 561   }
 562   return s;
 563 }
 564
 565 std::string HistogramToStringFull(const ShinglePattern::Histogram& histogram,
 566                                   const char* indent,
 567                                   size_t snippet_max) {
 568   std::string s;
 569
 570   size_t histogram_size = histogram.size();
 571   size_t snippet_size = 0;
 572   for (ShinglePattern::Histogram::const_iterator p = histogram.begin();
 573        p != histogram.end();
 574        ++p) {
 575     s += indent;
 576     if (++snippet_size > snippet_max && snippet_size != histogram_size) {
 577       s += "...\n";
 578       break;
 579     }
 580     base::StringAppendF(&s, "(%d) ", p->count());
 581     s += ToString(&(*p->instance()));
 582     s += "\n";
 583   }
 584   return s;
 585 }
 586
 587 std::string ToString(const ShinglePattern* pattern, size_t snippet_max = 3) {
 588   std::string s;
 589   if (pattern == NULL) {
 590     s = "<null>";
 591   } else {
 592     s = "{";
 593     s += ToString(pattern->index_);
 594     base::StringAppendF(&s, ";  %d(%d):",
 595                         static_cast<int>(pattern->model_histogram_.size()),
 596                         pattern->model_coverage_);
 597
 598     s += HistogramToString(pattern->model_histogram_, snippet_max);
 599     base::StringAppendF(&s, ";  %d(%d):",
 600                         static_cast<int>(pattern->program_histogram_.size()),
 601                         pattern->program_coverage_);
 602     s += HistogramToString(pattern->program_histogram_, snippet_max);
 603     s += "}";
 604   }
 605   return s;
 606 }
 607
 608 std::string ShinglePatternToStringFull(const ShinglePattern* pattern,
 609                                        size_t max) {
 610   std::string s;
 611   s += ToString(pattern->index_);
 612   s += "\n";
 613   size_t model_size = pattern->model_histogram_.size();
 614   size_t program_size = pattern->program_histogram_.size();
 615   base::StringAppendF(&s, "  model shingles %" PRIuS "\n", model_size);
 616   s += HistogramToStringFull(pattern->model_histogram_, "    ", max);
 617   base::StringAppendF(&s, "  program shingles %" PRIuS "\n", program_size);
 618   s += HistogramToStringFull(pattern->program_histogram_, "    ", max);
 619   return s;
 620 }
 621
 622 struct ShinglePatternIndexLess {
 623   bool operator()(const ShinglePattern::Index& a,
 624                   const ShinglePattern::Index& b) const {
 625     if (a.hash_ < b.hash_) return true;
 626     if (a.hash_ > b.hash_) return false;
 627
 628     for (uint8_t i = 0; i < Shingle::kWidth; ++i) {
 629       if (a.kinds_[i] < b.kinds_[i]) return true;
 630       if (a.kinds_[i] > b.kinds_[i]) return false;
 631       if ((a.kinds_[i] & ShinglePattern::kVariable) == 0) {
 632         if (a.assigned_indexes_[i] < b.assigned_indexes_[i])
 633           return true;
 634         if (a.assigned_indexes_[i] > b.assigned_indexes_[i])
 635           return false;
 636       }
 637     }
 638     return false;
 639   }
 640 };
 641
 642 static uint32_t hash_combine(uint32_t h, uint32_t v) {
 643   h += v;
 644   return (h * (37 + 0x0000d100)) ^ (h >> 13);
 645 }
 646
 647 ShinglePattern::Index::Index(const Shingle* instance) {
 648   uint32_t hash = 0;
 649   variables_ = 0;
 650   unique_variables_ = 0;
 651   first_variable_index_ = 255;
 652
 653   for (uint8_t i = 0; i < Shingle::kWidth; ++i) {
 654     LabelInfo* info = instance->at(i);
 655     uint8_t kind = 0;
 656     int code = -1;
 657     uint8_t j = 0;
 658     for ( ; j < i; ++j) {
 659       if (info == instance->at(j)) {  // Duplicate LabelInfo
 660         kind = kinds_[j];
 661         break;
 662       }
 663     }
 664     if (j == i) {  // Not found above.
 665       if (info->assignment_) {
 666         code = info->label_->index_;
 667         assigned_indexes_[i] = code;
 668         kind = kFixed + i;
 669       } else {
 670         kind = kVariable + i;
 671         ++unique_variables_;
 672         if (i < first_variable_index_)
 673           first_variable_index_ = i;
 674       }
 675     }
 676     if (kind & kVariable) ++variables_;
 677     hash = hash_combine(hash, code);
 678     hash = hash_combine(hash, kind);
 679     kinds_[i] = kind;
 680     assigned_indexes_[i] = code;
 681   }
 682   hash_ = hash;
 683 }
 684
 685 struct ShinglePatternLess {
 686   bool operator()(const ShinglePattern& a, const ShinglePattern& b) const {
 687     return index_less(*a.index_, *b.index_);
 688   }
 689   ShinglePatternIndexLess index_less;
 690 };
 691
 692 struct ShinglePatternPointerLess {
 693   bool operator()(const ShinglePattern* a, const ShinglePattern* b) const {
 694     return pattern_less(*a, *b);
 695   }
 696   ShinglePatternLess pattern_less;
 697 };
 698
 699 template<int (*Scorer)(const ShinglePattern*)>
 700 struct OrderShinglePatternByScoreDescending {
 701   bool operator()(const ShinglePattern* a, const ShinglePattern* b) const {
 702     int score_a = Scorer(a);
 703     int score_b = Scorer(b);
 704     if (score_a > score_b) return true;
 705     if (score_a < score_b) return false;
 706     return break_ties(a, b);
 707   }
 708   ShinglePatternPointerLess break_ties;
 709 };
 710
 711 // Returns a score for a 'Single Use' rule.  Returns -1 if the rule is not
 712 // applicable.
 713 int SingleUseScore(const ShinglePattern* pattern) {
 714   if (pattern->index_->variables_ != 1)
 715     return -1;
 716
 717   if (pattern->model_histogram_.size() != 1 ||
 718       pattern->program_histogram_.size() != 1)
 719     return -1;
 720
 721   // Does this pattern account for all uses of the variable?
 722   const ShinglePattern::FreqView& program_freq =
 723       *pattern->program_histogram_.begin();
 724   const ShinglePattern::FreqView& model_freq =
 725       *pattern->model_histogram_.begin();
 726   int p1 = program_freq.count();
 727   int m1 = model_freq.count();
 728   if (p1 == m1) {
 729     const Shingle* program_instance = program_freq.instance();
 730     const Shingle* model_instance = model_freq.instance();
 731     size_t variable_index = pattern->index_->first_variable_index_;
 732     LabelInfo* program_info = program_instance->at(variable_index);
 733     LabelInfo* model_info = model_instance->at(variable_index);
 734     if (!program_info->assignment_) {
 735       if (program_info->refs_ == p1 && model_info->refs_ == m1) {
 736         return p1;
 737       }
 738     }
 739   }
 740   return -1;
 741 }
 742
 743 // The VariableQueue is a priority queue of unassigned LabelInfos from
 744 // the 'program' (the 'variables') and their AssignmentCandidates.
 745 class VariableQueue {
 746  public:
 747   typedef std::pair<int, LabelInfo*> ScoreAndLabel;
 748
 749   VariableQueue() = default;
 750
 751   bool empty() const { return queue_.empty(); }
 752
 753   const ScoreAndLabel& first() const { return *queue_.begin(); }
 754
 755   // For debugging only.
 756   void Print() const {
 757     for (Queue::const_iterator p = queue_.begin();  p != queue_.end();  ++p) {
 758       AssignmentCandidates* candidates = p->second->candidates();
 759       candidates->Print(std::numeric_limits<int>::max());
 760     }
 761   }
 762
 763   void AddPendingUpdate(LabelInfo* program_info, LabelInfo* model_info,
 764                         int delta_score) {
 765     AssignmentCandidates* candidates = program_info->candidates();
 766     if (!candidates->HasPendingUpdates()) {
 767       pending_update_candidates_.push_back(candidates);
 768     }
 769     candidates->AddPendingUpdate(model_info, delta_score);
 770   }
 771
 772   void ApplyPendingUpdates() {
 773     for (size_t i = 0;  i < pending_update_candidates_.size();  ++i) {
 774       AssignmentCandidates* candidates = pending_update_candidates_[i];
 775       int old_score = candidates->TopScore();
 776       queue_.erase(ScoreAndLabel(old_score, candidates->program_info()));
 777       candidates->ApplyPendingUpdates();
 778       if (!candidates->empty()) {
 779         int new_score = candidates->TopScore();
 780         queue_.insert(ScoreAndLabel(new_score, candidates->program_info()));
 781       }
 782     }
 783     pending_update_candidates_.clear();
 784   }
 785
 786  private:
 787   struct OrderScoreAndLabelByScoreDecreasing {
 788     bool operator()(const ScoreAndLabel& a, const ScoreAndLabel& b) const {
 789       if (a.first > b.first) return true;
 790       if (a.first < b.first) return false;
 791       return OrderLabelInfo()(a.second, b.second);
 792     }
 793   };
 794   typedef std::set<ScoreAndLabel, OrderScoreAndLabelByScoreDecreasing> Queue;
 795
 796   Queue queue_;
 797   std::vector<AssignmentCandidates*> pending_update_candidates_;
 798
 799   DISALLOW_COPY_AND_ASSIGN(VariableQueue);
 800 };
 801
 802
 803 class AssignmentProblem {
 804  public:
 805   AssignmentProblem(const Trace& trace, size_t model_end)
 806       : trace_(trace),
 807         model_end_(model_end) {
 808     VLOG(2) << "AssignmentProblem::AssignmentProblem  " << model_end << ", "
 809             << trace.size();
 810   }
 811
 812   bool Solve() {
 813     if (model_end_ < Shingle::kWidth ||
 814         trace_.size() - model_end_ < Shingle::kWidth) {
 815       // Nothing much we can do with such a short problem.
 816       return true;
 817     }
 818     instances_.resize(trace_.size() - Shingle::kWidth + 1, NULL);
 819     AddShingles(0, model_end_);
 820     AddShingles(model_end_, trace_.size());
 821     InitialClassify();
 822     AddPatternsNeedingUpdatesToQueues();
 823
 824     patterns_needing_updates_.clear();
 825     while (FindAndAssignBestLeader())
 826       patterns_needing_updates_.clear();
 827     PrintActivePatterns();
 828
 829     return true;
 830   }
 831
 832  private:
 833   typedef std::set<Shingle*, Shingle::PointerLess> ShingleSet;
 834
 835   typedef std::set<const ShinglePattern*, ShinglePatternPointerLess>
 836       ShinglePatternSet;
 837
 838   // Patterns are partitioned into the following sets:
 839
 840   // * Retired patterns (not stored).  No shingles exist for this pattern (they
 841   //   all now match more specialized patterns).
 842   // * Useless patterns (not stored).  There are no 'program' shingles for this
 843   //   pattern (they all now match more specialized patterns).
 844   // * Single-use patterns - single_use_pattern_queue_.
 845   // * Other patterns - active_non_single_use_patterns_ / variable_queue_.
 846
 847   typedef std::set<const ShinglePattern*,
 848                    OrderShinglePatternByScoreDescending<&SingleUseScore> >
 849       SingleUsePatternQueue;
 850
 851   void PrintPatternsHeader() const {
 852     VLOG(2) << shingle_instances_.size() << " instances  "
 853             << trace_.size() << " trace length  "
 854             << patterns_.size() << " shingle indexes  "
 855             << single_use_pattern_queue_.size() << " single use patterns  "
 856             << active_non_single_use_patterns_.size() << " active patterns";
 857   }
 858
 859   void PrintActivePatterns() const {
 860     for (ShinglePatternSet::const_iterator p =
 861              active_non_single_use_patterns_.begin();
 862          p != active_non_single_use_patterns_.end();
 863          ++p) {
 864       const ShinglePattern* pattern = *p;
 865       VLOG(2) << ToString(pattern, 10);
 866     }
 867   }
 868
 869   void PrintPatterns() const {
 870     PrintAllPatterns();
 871     PrintActivePatterns();
 872     PrintAllShingles();
 873   }
 874
 875   void PrintAllPatterns() const {
 876     for (IndexToPattern::const_iterator p = patterns_.begin();
 877          p != patterns_.end();
 878          ++p) {
 879       const ShinglePattern& pattern = p->second;
 880       VLOG(2) << ToString(&pattern, 10);
 881     }
 882   }
 883
 884   void PrintAllShingles() const {
 885     for (Shingle::OwningSet::const_iterator p = shingle_instances_.begin();
 886          p != shingle_instances_.end();
 887          ++p) {
 888       const Shingle& instance = *p;
 889       VLOG(2) << ToString(&instance) << "   " << ToString(instance.pattern());
 890     }
 891   }
 892
 893
 894   void AddShingles(size_t begin, size_t end) {
 895     for (size_t i = begin; i + Shingle::kWidth - 1 < end; ++i) {
 896       instances_[i] = Shingle::Find(trace_, i, &shingle_instances_);
 897     }
 898   }
 899
 900   void Declassify(Shingle* shingle) {
 901     ShinglePattern* pattern = shingle->pattern();
 902     if (shingle->InModel()) {
 903       pattern->model_histogram_.erase(ShinglePattern::FreqView(shingle));
 904       pattern->model_coverage_ -= shingle->position_count();
 905     } else {
 906       pattern->program_histogram_.erase(ShinglePattern::FreqView(shingle));
 907       pattern->program_coverage_ -= shingle->position_count();
 908     }
 909     shingle->set_pattern(NULL);
 910   }
 911
 912   void Reclassify(Shingle* shingle) {
 913     ShinglePattern* pattern = shingle->pattern();
 914     LOG_ASSERT(pattern == NULL);
 915
 916     ShinglePattern::Index index(shingle);
 917     if (index.variables_ == 0)
 918       return;
 919
 920     std::pair<IndexToPattern::iterator, bool> inserted =
 921         patterns_.insert(std::make_pair(index, ShinglePattern()));
 922
 923     pattern = &inserted.first->second;
 924     pattern->index_ = &inserted.first->first;
 925     shingle->set_pattern(pattern);
 926     patterns_needing_updates_.insert(pattern);
 927
 928     if (shingle->InModel()) {
 929       pattern->model_histogram_.insert(ShinglePattern::FreqView(shingle));
 930       pattern->model_coverage_ += shingle->position_count();
 931     } else {
 932       pattern->program_histogram_.insert(ShinglePattern::FreqView(shingle));
 933       pattern->program_coverage_ += shingle->position_count();
 934     }
 935   }
 936
 937   void InitialClassify() {
 938     for (Shingle::OwningSet::iterator p = shingle_instances_.begin();
 939          p != shingle_instances_.end();
 940          ++p) {
 941       // GCC's set<T>::iterator::operator *() returns a const object.
 942       Reclassify(const_cast<Shingle*>(&*p));
 943     }
 944   }
 945
 946   // For the positions in |info|, find the shingles that overlap that position.
 947   void AddAffectedPositions(LabelInfo* info, ShingleSet* affected_shingles) {
 948     const uint8_t kWidth = Shingle::kWidth;
 949     for (size_t i = 0;  i < info->positions_.size();  ++i) {
 950       size_t position = info->positions_[i];
 951       // Find bounds to the subrange of |trace_| we are in.
 952       size_t start = position < model_end_ ? 0 : model_end_;
 953       size_t end = position < model_end_ ? model_end_ : trace_.size();
 954
 955       // Clip [position-kWidth+1, position+1)
 956       size_t low =
 957           position > start + kWidth - 1 ? position - kWidth + 1 : start;
 958       size_t high = position + kWidth < end ? position + 1 : end - kWidth + 1;
 959
 960       for (size_t shingle_position = low;
 961            shingle_position < high;
 962            ++shingle_position) {
 963         Shingle* overlapping_shingle = instances_.at(shingle_position);
 964         affected_shingles->insert(overlapping_shingle);
 965       }
 966     }
 967   }
 968
 969   void RemovePatternsNeedingUpdatesFromQueues() {
 970     for (ShinglePatternSet::iterator p = patterns_needing_updates_.begin();
 971          p != patterns_needing_updates_.end();
 972          ++p) {
 973       RemovePatternFromQueues(*p);
 974     }
 975   }
 976
 977   void AddPatternsNeedingUpdatesToQueues() {
 978     for (ShinglePatternSet::iterator p = patterns_needing_updates_.begin();
 979          p != patterns_needing_updates_.end();
 980          ++p) {
 981       AddPatternToQueues(*p);
 982     }
 983     variable_queue_.ApplyPendingUpdates();
 984   }
 985
 986   void RemovePatternFromQueues(const ShinglePattern* pattern) {
 987     int single_use_score = SingleUseScore(pattern);
 988     if (single_use_score > 0) {
 989       size_t n = single_use_pattern_queue_.erase(pattern);
 990       LOG_ASSERT(n == 1);
 991     } else if (pattern->program_histogram_.empty() &&
 992                pattern->model_histogram_.empty()) {
 993       NOTREACHED();  // Should not come back to life.
 994     } else if (pattern->program_histogram_.empty()) {
 995       // Useless pattern.
 996     } else {
 997       active_non_single_use_patterns_.erase(pattern);
 998       AddPatternToLabelQueue(pattern, -1);
 999     }
1000   }
1001
1002   void AddPatternToQueues(const ShinglePattern* pattern) {
1003     int single_use_score = SingleUseScore(pattern);
1004     if (single_use_score > 0) {
1005       single_use_pattern_queue_.insert(pattern);
1006     } else if (pattern->program_histogram_.empty() &&
1007                pattern->model_histogram_.empty()) {
1008     } else if (pattern->program_histogram_.empty()) {
1009       // Useless pattern.
1010     } else {
1011       active_non_single_use_patterns_.insert(pattern);
1012       AddPatternToLabelQueue(pattern, +1);
1013     }
1014   }
1015
1016   void AddPatternToLabelQueue(const ShinglePattern* pattern, int sign) {
1017     // For each possible assignment in this pattern, update the potential
1018     // contributions to the LabelInfo queues.
1019
1020     // We want to find for each symbol (LabelInfo) the maximum contribution that
1021     // could be achieved by making shingle-wise assignments between shingles in
1022     // the model and shingles in the program.
1023     //
1024     // If the shingles in the histograms are independent (no two shingles have a
1025     // symbol in common) then any permutation of the assignments is possible,
1026     // and the maximum contribution can be found by taking the maximum over all
1027     // the pairs.
1028     //
1029     // If the shingles are dependent two things happen.  The maximum
1030     // contribution to any given symbol is a sum because the symbol has
1031     // contributions from all the shingles containing it.  Second, some
1032     // assignments are blocked by previous incompatible assignments.  We want to
1033     // avoid a combinatorial search, so we ignore the blocking.
1034
1035     const size_t kUnwieldy = 5;
1036
1037     typedef std::map<LabelInfo*, int> LabelToScore;
1038     typedef std::map<LabelInfo*, LabelToScore > ScoreSet;
1039     ScoreSet maxima;
1040
1041     size_t n_model_samples = 0;
1042     for (ShinglePattern::Histogram::const_iterator model_iter =
1043              pattern->model_histogram_.begin();
1044          model_iter != pattern->model_histogram_.end();
1045          ++model_iter) {
1046       if (++n_model_samples > kUnwieldy) break;
1047       const ShinglePattern::FreqView& model_freq = *model_iter;
1048       int m1 = model_freq.count();
1049       const Shingle* model_instance = model_freq.instance();
1050
1051       ScoreSet sums;
1052       size_t n_program_samples = 0;
1053       for (ShinglePattern::Histogram::const_iterator program_iter =
1054                pattern->program_histogram_.begin();
1055            program_iter != pattern->program_histogram_.end();
1056            ++program_iter) {
1057         if (++n_program_samples > kUnwieldy) break;
1058         const ShinglePattern::FreqView& program_freq = *program_iter;
1059         int p1 = program_freq.count();
1060         const Shingle* program_instance = program_freq.instance();
1061
1062         // int score = p1;  // ? weigh all equally??
1063         int score = std::min(p1, m1);
1064
1065         for (uint8_t i = 0; i < Shingle::kWidth; ++i) {
1066           LabelInfo* program_info = program_instance->at(i);
1067           LabelInfo* model_info = model_instance->at(i);
1068           if ((model_info->assignment_ == NULL) !=
1069               (program_info->assignment_ == NULL)) {
1070             VLOG(2) << "ERROR " << i
1071                     << "\n\t"  << ToString(pattern, 10)
1072                     << "\n\t" << ToString(program_instance)
1073                     << "\n\t" << ToString(model_instance);
1074           }
1075           if (!program_info->assignment_ && !model_info->assignment_) {
1076             sums[program_info][model_info] += score;
1077           }
1078         }
1079       }
1080
1081       for (ScoreSet::iterator assignee_iterator = sums.begin();
1082            assignee_iterator != sums.end();
1083            ++assignee_iterator) {
1084         LabelInfo* program_info = assignee_iterator->first;
1085         for (LabelToScore::iterator p = assignee_iterator->second.begin();
1086              p != assignee_iterator->second.end();
1087              ++p) {
1088           LabelInfo* model_info = p->first;
1089           int score = p->second;
1090           int* slot = &maxima[program_info][model_info];
1091           *slot = std::max(*slot, score);
1092         }
1093       }
1094     }
1095
1096     for (ScoreSet::iterator assignee_iterator = maxima.begin();
1097          assignee_iterator != maxima.end();
1098          ++assignee_iterator) {
1099       LabelInfo* program_info = assignee_iterator->first;
1100       for (LabelToScore::iterator p = assignee_iterator->second.begin();
1101            p != assignee_iterator->second.end();
1102            ++p) {
1103         LabelInfo* model_info = p->first;
1104         int score = sign * p->second;
1105         variable_queue_.AddPendingUpdate(program_info, model_info, score);
1106       }
1107     }
1108   }
1109
1110   void AssignOne(LabelInfo* model_info, LabelInfo* program_info) {
1111     LOG_ASSERT(!model_info->assignment_);
1112     LOG_ASSERT(!program_info->assignment_);
1113     LOG_ASSERT(model_info->is_model_);
1114     LOG_ASSERT(!program_info->is_model_);
1115
1116     VLOG(3) << "Assign " << ToString(program_info)
1117             << " := " << ToString(model_info);
1118
1119     ShingleSet affected_shingles;
1120     AddAffectedPositions(model_info, &affected_shingles);
1121     AddAffectedPositions(program_info, &affected_shingles);
1122
1123     for (ShingleSet::iterator p = affected_shingles.begin();
1124          p != affected_shingles.end();
1125          ++p) {
1126       patterns_needing_updates_.insert((*p)->pattern());
1127     }
1128
1129     RemovePatternsNeedingUpdatesFromQueues();
1130
1131     for (ShingleSet::iterator p = affected_shingles.begin();
1132          p != affected_shingles.end();
1133          ++p) {
1134       Declassify(*p);
1135     }
1136
1137     program_info->label_->index_ = model_info->label_->index_;
1138     // Mark as assigned
1139     model_info->assignment_ = program_info;
1140     program_info->assignment_ = model_info;
1141
1142     for (ShingleSet::iterator p = affected_shingles.begin();
1143          p != affected_shingles.end();
1144          ++p) {
1145       Reclassify(*p);
1146     }
1147
1148     AddPatternsNeedingUpdatesToQueues();
1149   }
1150
1151   bool AssignFirstVariableOfHistogramHead(const ShinglePattern& pattern) {
1152     const ShinglePattern::FreqView& program_1 =
1153         *pattern.program_histogram_.begin();
1154     const ShinglePattern::FreqView& model_1 = *pattern.model_histogram_.begin();
1155     const Shingle* program_instance = program_1.instance();
1156     const Shingle* model_instance = model_1.instance();
1157     size_t variable_index = pattern.index_->first_variable_index_;
1158     LabelInfo* program_info = program_instance->at(variable_index);
1159     LabelInfo* model_info = model_instance->at(variable_index);
1160     AssignOne(model_info, program_info);
1161     return true;
1162   }
1163
1164   bool FindAndAssignBestLeader() {
1165     LOG_ASSERT(patterns_needing_updates_.empty());
1166
1167     if (!single_use_pattern_queue_.empty()) {
1168       const ShinglePattern& pattern = **single_use_pattern_queue_.begin();
1169       return AssignFirstVariableOfHistogramHead(pattern);
1170     }
1171
1172     if (variable_queue_.empty())
1173       return false;
1174
1175     const VariableQueue::ScoreAndLabel best = variable_queue_.first();
1176     int score = best.first;
1177     LabelInfo* assignee = best.second;
1178
1179     // TODO(sra): score (best.first) can be zero.  A zero score means we are
1180     // blindly picking between two (or more) alternatives which look the same.
1181     // If we exit on the first zero-score we sometimes get 3-4% better total
1182     // compression.  This indicates that 'infill' is doing a better job than
1183     // picking blindly.  Perhaps we can use an extended region around the
1184     // undistinguished competing alternatives to break the tie.
1185     if (score == 0) {
1186       variable_queue_.Print();
1187       return false;
1188     }
1189
1190     AssignmentCandidates* candidates = assignee->candidates();
1191     if (candidates->empty())
1192       return false;  // Should not happen.
1193
1194     AssignOne(candidates->top_candidate(), assignee);
1195     return true;
1196   }
1197
1198  private:
1199   // The trace vector contains the model sequence [0, model_end_) followed by
1200   // the program sequence [model_end_, trace.end())
1201   const Trace& trace_;
1202   size_t model_end_;
1203
1204   // |shingle_instances_| is the set of 'interned' shingles.
1205   Shingle::OwningSet shingle_instances_;
1206
1207   // |instances_| maps from position in |trace_| to Shingle at that position.
1208   std::vector<Shingle*> instances_;
1209
1210   SingleUsePatternQueue single_use_pattern_queue_;
1211   ShinglePatternSet active_non_single_use_patterns_;
1212   VariableQueue variable_queue_;
1213
1214   // Transient information: when we make an assignment, we need to recompute
1215   // priority queue information derived from these ShinglePatterns.
1216   ShinglePatternSet patterns_needing_updates_;
1217
1218   typedef std::map<ShinglePattern::Index,
1219                    ShinglePattern, ShinglePatternIndexLess> IndexToPattern;
1220   IndexToPattern patterns_;
1221
1222   DISALLOW_COPY_AND_ASSIGN(AssignmentProblem);
1223 };
1224
1225 class Adjuster : public AdjustmentMethod {
1226  public:
1227   Adjuster() : prog_(NULL), model_(NULL) {}
1228   ~Adjuster() = default;
1229
1230   bool Adjust(const AssemblyProgram& model, AssemblyProgram* program) {
1231     VLOG(1) << "Adjuster::Adjust";
1232     prog_ = program;
1233     model_ = &model;
1234     return Finish();
1235   }
1236
1237   bool Finish() {
1238     prog_->UnassignIndexes();
1239     Trace abs32_trace_;
1240     Trace rel32_trace_;
1241     CollectTraces(model_, &abs32_trace_, &rel32_trace_, true);
1242     size_t abs32_model_end = abs32_trace_.size();
1243     size_t rel32_model_end = rel32_trace_.size();
1244     CollectTraces(prog_,  &abs32_trace_,  &rel32_trace_,  false);
1245     Solve(abs32_trace_, abs32_model_end);
1246     Solve(rel32_trace_, rel32_model_end);
1247     prog_->AssignRemainingIndexes();
1248     return true;
1249   }
1250
1251  private:
1252   void CollectTraces(const AssemblyProgram* program, Trace* abs32, Trace* rel32,
1253                      bool is_model) {
1254     label_info_maker_.ResetDebugLabel();
1255
1256     for (Label* label : program->abs32_label_annotations())
1257       ReferenceLabel(abs32, is_model, label);
1258     for (Label* label : program->rel32_label_annotations())
1259       ReferenceLabel(rel32, is_model, label);
1260
1261     // TODO(sra): we could simply append all the labels in index order to
1262     // incorporate some costing for entropy (bigger deltas) that will be
1263     // introduced into the label address table by non-monotonic ordering.  This
1264     // would have some knock-on effects to parts of the algorithm that work on
1265     // single-occurrence labels.
1266   }
1267
1268   void Solve(const Trace& model, size_t model_end) {
1269     base::Time start_time = base::Time::Now();
1270     AssignmentProblem a(model, model_end);
1271     a.Solve();
1272     VLOG(1) << " Adjuster::Solve "
1273             << (base::Time::Now() - start_time).InSecondsF();
1274   }
1275
1276   void ReferenceLabel(Trace* trace, bool is_model, Label* label) {
1277     trace->push_back(label_info_maker_.MakeLabelInfo(
1278         label, is_model, static_cast<uint32_t>(trace->size())));
1279   }
1280
1281   AssemblyProgram* prog_;         // Program to be adjusted, owned by caller.
1282   const AssemblyProgram* model_;  // Program to be mimicked, owned by caller.
1283
1284   LabelInfoMaker label_info_maker_;
1285
1286  private:
1287   DISALLOW_COPY_AND_ASSIGN(Adjuster);
1288 };
1289
1290 ////////////////////////////////////////////////////////////////////////////////
1291
1292 }  // namespace adjustment_method_2
1293
1294 AdjustmentMethod* AdjustmentMethod::MakeShingleAdjustmentMethod() {
1295   return new adjustment_method_2::Adjuster();
1296 }
1297
1298 }  // namespace courgette