1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306 |
- // Copyright (c) 2011 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "base/memory/raw_ptr.h"
- #include "courgette/adjustment_method.h"
- #include <stddef.h>
- #include <stdint.h>
- #include <algorithm>
- #include <limits>
- #include <list>
- #include <map>
- #include <set>
- #include <string>
- #include <vector>
- #include "base/format_macros.h"
- #include "base/logging.h"
- #include "base/strings/stringprintf.h"
- #include "base/time/time.h"
- #include "courgette/assembly_program.h"
- #include "courgette/courgette.h"
- #include "courgette/encoded_program.h"
- /*
- Shingle weighting matching.
- We have a sequence S1 of symbols from alphabet A1={A,B,C,...} called the 'model'
- and a second sequence of S2 of symbols from alphabet A2={U,V,W,....} called the
- 'program'. Each symbol in A1 has a unique numerical name or index. We can
- transcribe the sequence S1 to a sequence T1 of indexes of the symbols. We wish
- to assign indexes to the symbols in A2 so that when we transcribe S2 into T2, T2
- has long subsequences that occur in T1. This will ensure that the sequence
- T1;T2 compresses to be only slightly larger than the compressed T1.
- The algorithm for matching members of S2 with members of S1 is eager - it makes
- matches without backtracking, until no more matches can be made. Each variable
- (symbol) U,V,... in A2 has a set of candidates from A1, each candidate with a
- weight summarizing the evidence for the match. We keep a VariableQueue of
- U,V,... sorted by how much the evidence for the best choice outweighs the
- evidence for the second choice, i.e. prioritized by how 'clear cut' the best
- assignment is. We pick the variable with the most clear-cut candidate, make the
- assignment, adjust the evidence and repeat.
- What has not been described so far is how the evidence is gathered and
- maintained. We are working under the assumption that S1 and S2 are largely
- similar. (A different assumption might be that S1 and S2 are dissimilar except
- for many long subsequences.)
- A naive algorithm would consider all pairs (A,U) and for each pair assess the
- benefit, or score, the assignment U:=A. The score might count the number of
- occurrences of U in S2 which appear in similar contexts to A in S1.
- To distinguish contexts we view S1 and S2 as a sequence of overlapping k-length
- substrings or 'shingles'. Two shingles are compatible if the symbols in one
- shingle could be matched with the symbols in the other symbol. For example, ABC
- is *not* compatible with UVU because it would require conflicting matches A=U
- and C=U. ABC is compatible with UVW, UWV, WUV, VUW etc. We can't tell which
- until we make an assignment - the compatible shingles form an equivalence class.
- After assigning U:=A then only UVW and UWV (equivalently AVW, AWV) are
- compatible. As we make assignments the number of equivalence classes of
- shingles increases and the number of members of each equivalence class
- decreases. The compatibility test becomes more restrictive.
- We gather evidence for the potential assignment U:=A by counting how many
- shingles containing U are compatible with shingles containing A. Thus symbols
- occurring a large number of times in compatible contexts will be assigned first.
- Finding the 'most clear-cut' assignment by considering all pairs symbols and for
- each pair comparing the contexts of each pair of occurrences of the symbols is
- computationally infeasible. We get the job done in a reasonable time by
- approaching it 'backwards' and making incremental changes as we make
- assignments.
- First the shingles are partitioned according to compatibility. In S1=ABCDD and
- S2=UVWXX we have a total of 6 shingles, each occuring once. (ABC:1 BCD:1 CDD:1;
- UVW:1 VWX: WXX:1) all fit the pattern <V0 V1 V2> or the pattern <V0 V1 V1>. The
- first pattern indicates that each position matches a different symbol, the
- second pattern indicates that the second symbol is repeated.
- pattern S1 members S2 members
- <V0 V1 V2>: {ABC:1, BCD:1}; {UVW:1, VWX:1}
- <V0 V1 V1>: {CDD:1} {WXX:1}
- The second pattern appears to have a unique assignment but we don't make the
- assignment on such scant evidence. If S1 and S2 do not match exactly, there
- will be numerous spurious low-score matches like this. Instead we must see what
- assignments are indicated by considering all of the evidence.
- First pattern has 2 x 2 = 4 shingle pairs. For each pair we count the number
- of symbol assignments. For ABC:a * UVW:b accumulate min(a,b) to each of
- {U:=A, V:=B, W:=C}.
- After accumulating over all 2 x 2 pairs:
- U: {A:1 B:1}
- V: {A:1 B:2 C:1}
- W: {B:1 C:2 D:1 }
- X: {C:1 D:1}
- The second pattern contributes:
- W: {C:1}
- X: {D:2}
- Sum:
- U: {A:1 B:1}
- V: {A:1 B:2 C:1}
- W: {B:1 C:3 D:1}
- X: {C:1 D:3}
- From this we decide to assign X:=D (because this assignment has both the largest
- difference above the next candidate (X:=C) and this is also the largest
- proportionately over the sum of alternatives).
- Lets assume D has numerical 'name' 77. The assignment X:=D sets X to 77 too.
- Next we repartition all the shingles containing X or D:
- pattern S1 members S2 members
- <V0 V1 V2>: {ABC:1}; {UVW:1}
- <V0 V1 77>: {BCD:1}; {VWX:1}
- <V0 77 77>: {CDD:1} {WXX:1}
- As we repartition, we recalculate the contributions to the scores:
- U: {A:1}
- V: {B:2}
- W: {C:3}
- All the remaining assignments are now fixed.
- There is one step in the incremental algorithm that is still infeasibly
- expensive: the contributions due to the cross product of large equivalence
- classes. We settle for making an approximation by computing the contribution of
- the cross product of only the most common shingles. The hope is that the noise
- from the long tail of uncounted shingles is well below the scores being used to
- pick assignments. The second hope is that as assignment are made, the large
- equivalence class will be partitioned into smaller equivalence classes, reducing
- the noise over time.
- In the code below the shingles are bigger (Shingle::kWidth = 5).
- Class ShinglePattern holds the data for one pattern.
- There is an optimization for this case:
- <V0 V1 V1>: {CDD:1} {WXX:1}
- Above we said that we don't make an assignment on this "scant evidence". There
- is an exception: if there is only one variable unassigned (more like the <V0 77
- 77> pattern) AND there are no occurrences of C and W other than those counted in
- this pattern, then there is no competing evidence and we go ahead with the
- assignment immediately. This produces slightly better results because these
- cases tend to be low-scoring and susceptible to small mistakes made in
- low-scoring assignments in the approximation for large equivalence classes.
- */
- namespace courgette {
- namespace adjustment_method_2 {
- ////////////////////////////////////////////////////////////////////////////////
- class AssignmentCandidates;
- class LabelInfoMaker;
- class Shingle;
- class ShinglePattern;
- // The purpose of adjustment is to assign indexes to Labels of a program 'p' to
- // make the sequence of indexes similar to a 'model' program 'm'. Labels
- // themselves don't have enough information to do this job, so we work with a
- // LabelInfo surrogate for each label.
- //
- class LabelInfo {
- public:
- // Just a no-argument constructor and copy constructor. Actual LabelInfo
- // objects are allocated in std::pair structs in a std::map.
- LabelInfo()
- : label_(nullptr),
- is_model_(false),
- debug_index_(0),
- refs_(0),
- assignment_(nullptr),
- candidates_(nullptr) {}
- ~LabelInfo();
- AssignmentCandidates* candidates();
- raw_ptr<Label> label_; // The label that this info a surrogate for.
- uint32_t is_model_ : 1; // Is the label in the model?
- uint32_t debug_index_ : 31; // A small number for naming the label in debug
- // output. The pair (is_model_, debug_index_) is
- // unique.
- int refs_; // Number of times this Label is referenced.
- raw_ptr<LabelInfo>
- assignment_; // Label from other program corresponding to this.
- std::vector<uint32_t> positions_; // Offsets into the trace of references.
- private:
- raw_ptr<AssignmentCandidates> candidates_;
- void operator=(const LabelInfo*); // Disallow assignment only.
- // Public compiler generated copy constructor is needed to constuct
- // std::pair<Label*, LabelInfo> so that fresh LabelInfos can be allocated
- // inside a std::map.
- };
- typedef std::vector<LabelInfo*> Trace;
- std::string ToString(const LabelInfo* info) {
- std::string s;
- base::StringAppendF(&s, "%c%d", "pm"[info->is_model_], info->debug_index_);
- if (info->label_->index_ != Label::kNoIndex)
- base::StringAppendF(&s, " (%d)", info->label_->index_);
- base::StringAppendF(&s, " #%u", info->refs_);
- return s;
- }
- // LabelInfoMaker maps labels to their surrogate LabelInfo objects.
- class LabelInfoMaker {
- public:
- LabelInfoMaker() : debug_label_index_gen_(0) {}
- LabelInfoMaker(const LabelInfoMaker&) = delete;
- LabelInfoMaker& operator=(const LabelInfoMaker&) = delete;
- LabelInfo* MakeLabelInfo(Label* label, bool is_model, uint32_t position) {
- LabelInfo& slot = label_infos_[label];
- if (slot.label_ == nullptr) {
- slot.label_ = label;
- slot.is_model_ = is_model;
- slot.debug_index_ = ++debug_label_index_gen_;
- }
- slot.positions_.push_back(position);
- ++slot.refs_;
- return &slot;
- }
- void ResetDebugLabel() { debug_label_index_gen_ = 0; }
- private:
- int debug_label_index_gen_;
- // Note LabelInfo is allocated 'flat' inside map::value_type, so the LabelInfo
- // lifetimes are managed by the map.
- std::map<Label*, LabelInfo> label_infos_;
- };
- struct OrderLabelInfo {
- bool operator()(const LabelInfo* a, const LabelInfo* b) const {
- if (a->label_->rva_ < b->label_->rva_) return true;
- if (a->label_->rva_ > b->label_->rva_) return false;
- if (a == b) return false;
- return a->positions_ < b->positions_; // Lexicographic ordering of vector.
- }
- };
- // AssignmentCandidates is a priority queue of candidate assignments to
- // a single program LabelInfo, |program_info_|.
- class AssignmentCandidates {
- public:
- explicit AssignmentCandidates(LabelInfo* program_info)
- : program_info_(program_info) {}
- LabelInfo* program_info() const { return program_info_; }
- bool empty() const { return label_to_score_.empty(); }
- LabelInfo* top_candidate() const { return queue_.begin()->second; }
- void Update(LabelInfo* model_info, int delta_score) {
- LOG_ASSERT(delta_score != 0);
- int old_score = 0;
- int new_score = 0;
- LabelToScore::iterator p = label_to_score_.find(model_info);
- if (p != label_to_score_.end()) {
- old_score = p->second;
- new_score = old_score + delta_score;
- queue_.erase(ScoreAndLabel(old_score, p->first));
- if (new_score == 0) {
- label_to_score_.erase(p);
- } else {
- p->second = new_score;
- queue_.insert(ScoreAndLabel(new_score, model_info));
- }
- } else {
- new_score = delta_score;
- label_to_score_.insert(std::make_pair(model_info, new_score));
- queue_.insert(ScoreAndLabel(new_score, model_info));
- }
- LOG_ASSERT(queue_.size() == label_to_score_.size());
- }
- int TopScore() const {
- int first_value = 0;
- int second_value = 0;
- Queue::const_iterator p = queue_.begin();
- if (p != queue_.end()) {
- first_value = p->first;
- ++p;
- if (p != queue_.end()) {
- second_value = p->first;
- }
- }
- return first_value - second_value;
- }
- bool HasPendingUpdates() { return !pending_updates_.empty(); }
- void AddPendingUpdate(LabelInfo* model_info, int delta_score) {
- LOG_ASSERT(delta_score != 0);
- pending_updates_[model_info] += delta_score;
- }
- void ApplyPendingUpdates() {
- // TODO(sra): try to walk |pending_updates_| and |label_to_score_| in
- // lockstep. Try to batch updates to |queue_|.
- for (LabelToScore::iterator p = pending_updates_.begin();
- p != pending_updates_.end();
- ++p) {
- if (p->second != 0)
- Update(p->first, p->second);
- }
- pending_updates_.clear();
- }
- void Print(int max) {
- VLOG(2) << "score " << TopScore() << " " << ToString(program_info_)
- << " := ?";
- if (!pending_updates_.empty())
- VLOG(2) << pending_updates_.size() << " pending";
- int count = 0;
- for (Queue::iterator q = queue_.begin(); q != queue_.end(); ++q) {
- if (++count > max) break;
- VLOG(2) << " " << q->first << " " << ToString(q->second);
- }
- }
- private:
- typedef std::map<LabelInfo*, int, OrderLabelInfo> LabelToScore;
- typedef std::pair<int, LabelInfo*> ScoreAndLabel;
- struct OrderScoreAndLabelByScoreDecreasing {
- OrderLabelInfo tie_breaker;
- bool operator()(const ScoreAndLabel& a, const ScoreAndLabel& b) const {
- if (a.first > b.first) return true;
- if (a.first < b.first) return false;
- return tie_breaker(a.second, b.second);
- }
- };
- typedef std::set<ScoreAndLabel, OrderScoreAndLabelByScoreDecreasing> Queue;
- raw_ptr<LabelInfo> program_info_;
- LabelToScore label_to_score_;
- LabelToScore pending_updates_;
- Queue queue_;
- };
- AssignmentCandidates* LabelInfo::candidates() {
- if (candidates_ == nullptr)
- candidates_ = new AssignmentCandidates(this);
- return candidates_;
- }
- LabelInfo::~LabelInfo() {
- delete candidates_;
- }
- // A Shingle is a short fixed-length string of LabelInfos that actually occurs
- // in a Trace. A Shingle may occur many times. We repesent the Shingle by the
- // position of one of the occurrences in the Trace.
- class Shingle {
- public:
- static const uint8_t kWidth = 5;
- struct InterningLess {
- bool operator()(const Shingle& a, const Shingle& b) const;
- };
- typedef std::set<Shingle, InterningLess> OwningSet;
- // We can't disallow the copy constructor because we use std::set<Shingle> and
- // VS2005's implementation of std::set<T>::set() requires T to have a copy
- // constructor.
- Shingle(const Shingle&) = default;
- Shingle& operator=(const Shingle&) = delete; // Disallow assignment only.
- static Shingle* Find(const Trace& trace, size_t position,
- OwningSet* owning_set) {
- std::pair<OwningSet::iterator, bool> pair =
- owning_set->insert(Shingle(trace, position));
- // pair.first iterator 'points' to the newly inserted Shingle or the
- // previouly inserted one that looks the same according to the comparator.
- // const_cast required because key is const. We modify the Shingle
- // extensively but not in a way that affects InterningLess.
- Shingle* shingle = const_cast<Shingle*>(&*pair.first);
- shingle->add_position(position);
- return shingle;
- }
- LabelInfo* at(size_t i) const { return trace_[exemplar_position_ + i]; }
- void add_position(size_t position) {
- positions_.push_back(static_cast<uint32_t>(position));
- }
- int position_count() const { return static_cast<int>(positions_.size()); }
- bool InModel() const { return at(0)->is_model_; }
- ShinglePattern* pattern() const { return pattern_; }
- void set_pattern(ShinglePattern* pattern) { pattern_ = pattern; }
- struct PointerLess {
- bool operator()(const Shingle* a, const Shingle* b) const {
- // Arbitrary but repeatable (memory-address) independent ordering:
- return a->exemplar_position_ < b->exemplar_position_;
- // return InterningLess()(*a, *b);
- }
- };
- private:
- Shingle(const Trace& trace, size_t exemplar_position)
- : trace_(trace),
- exemplar_position_(exemplar_position),
- pattern_(nullptr) {}
- const Trace& trace_; // The shingle lives inside trace_.
- size_t exemplar_position_; // At this position (and other positions).
- std::vector<uint32_t> positions_; // Includes exemplar_position_.
- raw_ptr<ShinglePattern>
- pattern_; // Pattern changes as LabelInfos are assigned.
- friend std::string ToString(const Shingle* instance);
- };
- std::string ToString(const Shingle* instance) {
- std::string s;
- const char* sep = "<";
- for (uint8_t i = 0; i < Shingle::kWidth; ++i) {
- // base::StringAppendF(&s, "%s%x ", sep, instance.at(i)->label_->rva_);
- s += sep;
- s += ToString(instance->at(i));
- sep = ", ";
- }
- base::StringAppendF(&s, ">(%" PRIuS ")@{%d}",
- instance->exemplar_position_,
- instance->position_count());
- return s;
- }
- bool Shingle::InterningLess::operator()(
- const Shingle& a,
- const Shingle& b) const {
- for (uint8_t i = 0; i < kWidth; ++i) {
- LabelInfo* info_a = a.at(i);
- LabelInfo* info_b = b.at(i);
- if (info_a->label_->rva_ < info_b->label_->rva_)
- return true;
- if (info_a->label_->rva_ > info_b->label_->rva_)
- return false;
- if (info_a->is_model_ < info_b->is_model_)
- return true;
- if (info_a->is_model_ > info_b->is_model_)
- return false;
- if (info_a != info_b) {
- NOTREACHED();
- }
- }
- return false;
- }
- class ShinglePattern {
- public:
- enum { kOffsetMask = 7, // Offset lives in low bits.
- kFixed = 0, // kind & kVariable == 0 => fixed.
- kVariable = 8 // kind & kVariable == 1 => variable.
- };
- // sequence[position + (kinds_[i] & kOffsetMask)] gives LabelInfo for position
- // i of shingle. Below, second 'A' is duplicate of position 1, second '102'
- // is duplicate of position 0.
- //
- // <102, A, 103, A , 102>
- // --> <kFixed+0, kVariable+1, kFixed+2, kVariable+1, kFixed+0>
- struct Index {
- explicit Index(const Shingle* instance);
- uint8_t kinds_[Shingle::kWidth];
- uint8_t variables_;
- uint8_t unique_variables_;
- uint8_t first_variable_index_;
- uint32_t hash_;
- int assigned_indexes_[Shingle::kWidth];
- };
- // ShinglePattern keeps histograms of member Shingle instances, ordered by
- // decreasing number of occurrences. We don't have a pair (occurrence count,
- // Shingle instance), so we use a FreqView adapter to make the instance
- // pointer look like the pair.
- class FreqView {
- public:
- explicit FreqView(const Shingle* instance) : instance_(instance) {}
- int count() const { return instance_->position_count(); }
- const Shingle* instance() const { return instance_; }
- struct Greater {
- bool operator()(const FreqView& a, const FreqView& b) const {
- if (a.count() > b.count()) return true;
- if (a.count() < b.count()) return false;
- return resolve_ties(a.instance(), b.instance());
- }
- private:
- Shingle::PointerLess resolve_ties;
- };
- private:
- const Shingle* instance_;
- };
- typedef std::set<FreqView, FreqView::Greater> Histogram;
- ShinglePattern()
- : index_(nullptr), model_coverage_(0), program_coverage_(0) {}
- raw_ptr<const Index>
- index_; // Points to the key in the owning map value_type.
- Histogram model_histogram_;
- Histogram program_histogram_;
- int model_coverage_;
- int program_coverage_;
- };
- std::string ToString(const ShinglePattern::Index* index) {
- std::string s;
- if (index == nullptr) {
- s = "<null>";
- } else {
- base::StringAppendF(&s, "<%d: ", index->variables_);
- const char* sep = "";
- for (uint8_t i = 0; i < Shingle::kWidth; ++i) {
- s += sep;
- sep = ", ";
- uint32_t kind = index->kinds_[i];
- int offset = kind & ShinglePattern::kOffsetMask;
- if (kind & ShinglePattern::kVariable)
- base::StringAppendF(&s, "V%d", offset);
- else
- base::StringAppendF(&s, "%d", index->assigned_indexes_[offset]);
- }
- base::StringAppendF(&s, " %x", index->hash_);
- s += ">";
- }
- return s;
- }
- std::string HistogramToString(const ShinglePattern::Histogram& histogram,
- size_t snippet_max) {
- std::string s;
- size_t histogram_size = histogram.size();
- size_t snippet_size = 0;
- for (ShinglePattern::Histogram::const_iterator p = histogram.begin();
- p != histogram.end();
- ++p) {
- if (++snippet_size > snippet_max && snippet_size != histogram_size) {
- s += " ...";
- break;
- }
- base::StringAppendF(&s, " %d", p->count());
- }
- return s;
- }
- std::string HistogramToStringFull(const ShinglePattern::Histogram& histogram,
- const char* indent,
- size_t snippet_max) {
- std::string s;
- size_t histogram_size = histogram.size();
- size_t snippet_size = 0;
- for (ShinglePattern::Histogram::const_iterator p = histogram.begin();
- p != histogram.end();
- ++p) {
- s += indent;
- if (++snippet_size > snippet_max && snippet_size != histogram_size) {
- s += "...\n";
- break;
- }
- base::StringAppendF(&s, "(%d) ", p->count());
- s += ToString(&(*p->instance()));
- s += "\n";
- }
- return s;
- }
- std::string ToString(const ShinglePattern* pattern, size_t snippet_max = 3) {
- std::string s;
- if (pattern == nullptr) {
- s = "<null>";
- } else {
- s = "{";
- s += ToString(pattern->index_);
- base::StringAppendF(&s, "; %d(%d):",
- static_cast<int>(pattern->model_histogram_.size()),
- pattern->model_coverage_);
- s += HistogramToString(pattern->model_histogram_, snippet_max);
- base::StringAppendF(&s, "; %d(%d):",
- static_cast<int>(pattern->program_histogram_.size()),
- pattern->program_coverage_);
- s += HistogramToString(pattern->program_histogram_, snippet_max);
- s += "}";
- }
- return s;
- }
- std::string ShinglePatternToStringFull(const ShinglePattern* pattern,
- size_t max) {
- std::string s;
- s += ToString(pattern->index_);
- s += "\n";
- size_t model_size = pattern->model_histogram_.size();
- size_t program_size = pattern->program_histogram_.size();
- base::StringAppendF(&s, " model shingles %" PRIuS "\n", model_size);
- s += HistogramToStringFull(pattern->model_histogram_, " ", max);
- base::StringAppendF(&s, " program shingles %" PRIuS "\n", program_size);
- s += HistogramToStringFull(pattern->program_histogram_, " ", max);
- return s;
- }
- struct ShinglePatternIndexLess {
- bool operator()(const ShinglePattern::Index& a,
- const ShinglePattern::Index& b) const {
- if (a.hash_ < b.hash_) return true;
- if (a.hash_ > b.hash_) return false;
- for (uint8_t i = 0; i < Shingle::kWidth; ++i) {
- if (a.kinds_[i] < b.kinds_[i]) return true;
- if (a.kinds_[i] > b.kinds_[i]) return false;
- if ((a.kinds_[i] & ShinglePattern::kVariable) == 0) {
- if (a.assigned_indexes_[i] < b.assigned_indexes_[i])
- return true;
- if (a.assigned_indexes_[i] > b.assigned_indexes_[i])
- return false;
- }
- }
- return false;
- }
- };
- static uint32_t hash_combine(uint32_t h, uint32_t v) {
- h += v;
- return (h * (37 + 0x0000d100)) ^ (h >> 13);
- }
- ShinglePattern::Index::Index(const Shingle* instance) {
- uint32_t hash = 0;
- variables_ = 0;
- unique_variables_ = 0;
- first_variable_index_ = 255;
- for (uint8_t i = 0; i < Shingle::kWidth; ++i) {
- LabelInfo* info = instance->at(i);
- uint8_t kind = 0;
- int code = -1;
- uint8_t j = 0;
- for ( ; j < i; ++j) {
- if (info == instance->at(j)) { // Duplicate LabelInfo
- kind = kinds_[j];
- break;
- }
- }
- if (j == i) { // Not found above.
- if (info->assignment_) {
- code = info->label_->index_;
- assigned_indexes_[i] = code;
- kind = kFixed + i;
- } else {
- kind = kVariable + i;
- ++unique_variables_;
- if (i < first_variable_index_)
- first_variable_index_ = i;
- }
- }
- if (kind & kVariable) ++variables_;
- hash = hash_combine(hash, code);
- hash = hash_combine(hash, kind);
- kinds_[i] = kind;
- assigned_indexes_[i] = code;
- }
- hash_ = hash;
- }
- struct ShinglePatternLess {
- bool operator()(const ShinglePattern& a, const ShinglePattern& b) const {
- return index_less(*a.index_, *b.index_);
- }
- ShinglePatternIndexLess index_less;
- };
- struct ShinglePatternPointerLess {
- bool operator()(const ShinglePattern* a, const ShinglePattern* b) const {
- return pattern_less(*a, *b);
- }
- ShinglePatternLess pattern_less;
- };
- template<int (*Scorer)(const ShinglePattern*)>
- struct OrderShinglePatternByScoreDescending {
- bool operator()(const ShinglePattern* a, const ShinglePattern* b) const {
- int score_a = Scorer(a);
- int score_b = Scorer(b);
- if (score_a > score_b) return true;
- if (score_a < score_b) return false;
- return break_ties(a, b);
- }
- ShinglePatternPointerLess break_ties;
- };
- // Returns a score for a 'Single Use' rule. Returns -1 if the rule is not
- // applicable.
- int SingleUseScore(const ShinglePattern* pattern) {
- if (pattern->index_->variables_ != 1)
- return -1;
- if (pattern->model_histogram_.size() != 1 ||
- pattern->program_histogram_.size() != 1)
- return -1;
- // Does this pattern account for all uses of the variable?
- const ShinglePattern::FreqView& program_freq =
- *pattern->program_histogram_.begin();
- const ShinglePattern::FreqView& model_freq =
- *pattern->model_histogram_.begin();
- int p1 = program_freq.count();
- int m1 = model_freq.count();
- if (p1 == m1) {
- const Shingle* program_instance = program_freq.instance();
- const Shingle* model_instance = model_freq.instance();
- size_t variable_index = pattern->index_->first_variable_index_;
- LabelInfo* program_info = program_instance->at(variable_index);
- LabelInfo* model_info = model_instance->at(variable_index);
- if (!program_info->assignment_) {
- if (program_info->refs_ == p1 && model_info->refs_ == m1) {
- return p1;
- }
- }
- }
- return -1;
- }
- // The VariableQueue is a priority queue of unassigned LabelInfos from
- // the 'program' (the 'variables') and their AssignmentCandidates.
- class VariableQueue {
- public:
- typedef std::pair<int, LabelInfo*> ScoreAndLabel;
- VariableQueue() = default;
- VariableQueue(const VariableQueue&) = delete;
- VariableQueue& operator=(const VariableQueue&) = delete;
- bool empty() const { return queue_.empty(); }
- const ScoreAndLabel& first() const { return *queue_.begin(); }
- // For debugging only.
- void Print() const {
- for (Queue::const_iterator p = queue_.begin(); p != queue_.end(); ++p) {
- AssignmentCandidates* candidates = p->second->candidates();
- candidates->Print(std::numeric_limits<int>::max());
- }
- }
- void AddPendingUpdate(LabelInfo* program_info, LabelInfo* model_info,
- int delta_score) {
- AssignmentCandidates* candidates = program_info->candidates();
- if (!candidates->HasPendingUpdates()) {
- pending_update_candidates_.push_back(candidates);
- }
- candidates->AddPendingUpdate(model_info, delta_score);
- }
- void ApplyPendingUpdates() {
- for (size_t i = 0; i < pending_update_candidates_.size(); ++i) {
- AssignmentCandidates* candidates = pending_update_candidates_[i];
- int old_score = candidates->TopScore();
- queue_.erase(ScoreAndLabel(old_score, candidates->program_info()));
- candidates->ApplyPendingUpdates();
- if (!candidates->empty()) {
- int new_score = candidates->TopScore();
- queue_.insert(ScoreAndLabel(new_score, candidates->program_info()));
- }
- }
- pending_update_candidates_.clear();
- }
- private:
- struct OrderScoreAndLabelByScoreDecreasing {
- bool operator()(const ScoreAndLabel& a, const ScoreAndLabel& b) const {
- if (a.first > b.first) return true;
- if (a.first < b.first) return false;
- return OrderLabelInfo()(a.second, b.second);
- }
- };
- typedef std::set<ScoreAndLabel, OrderScoreAndLabelByScoreDecreasing> Queue;
- Queue queue_;
- std::vector<AssignmentCandidates*> pending_update_candidates_;
- };
- class AssignmentProblem {
- public:
- AssignmentProblem(const Trace& trace, size_t model_end)
- : trace_(trace),
- model_end_(model_end) {
- VLOG(2) << "AssignmentProblem::AssignmentProblem " << model_end << ", "
- << trace.size();
- }
- AssignmentProblem(const AssignmentProblem&) = delete;
- AssignmentProblem& operator=(const AssignmentProblem&) = delete;
- bool Solve() {
- if (model_end_ < Shingle::kWidth ||
- trace_.size() - model_end_ < Shingle::kWidth) {
- // Nothing much we can do with such a short problem.
- return true;
- }
- instances_.resize(trace_.size() - Shingle::kWidth + 1, nullptr);
- AddShingles(0, model_end_);
- AddShingles(model_end_, trace_.size());
- InitialClassify();
- AddPatternsNeedingUpdatesToQueues();
- patterns_needing_updates_.clear();
- while (FindAndAssignBestLeader())
- patterns_needing_updates_.clear();
- PrintActivePatterns();
- return true;
- }
- private:
- typedef std::set<Shingle*, Shingle::PointerLess> ShingleSet;
- typedef std::set<const ShinglePattern*, ShinglePatternPointerLess>
- ShinglePatternSet;
- // Patterns are partitioned into the following sets:
- // * Retired patterns (not stored). No shingles exist for this pattern (they
- // all now match more specialized patterns).
- // * Useless patterns (not stored). There are no 'program' shingles for this
- // pattern (they all now match more specialized patterns).
- // * Single-use patterns - single_use_pattern_queue_.
- // * Other patterns - active_non_single_use_patterns_ / variable_queue_.
- typedef std::set<const ShinglePattern*,
- OrderShinglePatternByScoreDescending<&SingleUseScore> >
- SingleUsePatternQueue;
- void PrintPatternsHeader() const {
- VLOG(2) << shingle_instances_.size() << " instances "
- << trace_.size() << " trace length "
- << patterns_.size() << " shingle indexes "
- << single_use_pattern_queue_.size() << " single use patterns "
- << active_non_single_use_patterns_.size() << " active patterns";
- }
- void PrintActivePatterns() const {
- for (ShinglePatternSet::const_iterator p =
- active_non_single_use_patterns_.begin();
- p != active_non_single_use_patterns_.end();
- ++p) {
- const ShinglePattern* pattern = *p;
- VLOG(2) << ToString(pattern, 10);
- }
- }
- void PrintPatterns() const {
- PrintAllPatterns();
- PrintActivePatterns();
- PrintAllShingles();
- }
- void PrintAllPatterns() const {
- for (IndexToPattern::const_iterator p = patterns_.begin();
- p != patterns_.end();
- ++p) {
- const ShinglePattern& pattern = p->second;
- VLOG(2) << ToString(&pattern, 10);
- }
- }
- void PrintAllShingles() const {
- for (Shingle::OwningSet::const_iterator p = shingle_instances_.begin();
- p != shingle_instances_.end();
- ++p) {
- const Shingle& instance = *p;
- VLOG(2) << ToString(&instance) << " " << ToString(instance.pattern());
- }
- }
- void AddShingles(size_t begin, size_t end) {
- for (size_t i = begin; i + Shingle::kWidth - 1 < end; ++i) {
- instances_[i] = Shingle::Find(trace_, i, &shingle_instances_);
- }
- }
- void Declassify(Shingle* shingle) {
- ShinglePattern* pattern = shingle->pattern();
- if (shingle->InModel()) {
- pattern->model_histogram_.erase(ShinglePattern::FreqView(shingle));
- pattern->model_coverage_ -= shingle->position_count();
- } else {
- pattern->program_histogram_.erase(ShinglePattern::FreqView(shingle));
- pattern->program_coverage_ -= shingle->position_count();
- }
- shingle->set_pattern(nullptr);
- }
- void Reclassify(Shingle* shingle) {
- ShinglePattern* pattern = shingle->pattern();
- LOG_ASSERT(pattern == nullptr);
- ShinglePattern::Index index(shingle);
- if (index.variables_ == 0)
- return;
- std::pair<IndexToPattern::iterator, bool> inserted =
- patterns_.insert(std::make_pair(index, ShinglePattern()));
- pattern = &inserted.first->second;
- pattern->index_ = &inserted.first->first;
- shingle->set_pattern(pattern);
- patterns_needing_updates_.insert(pattern);
- if (shingle->InModel()) {
- pattern->model_histogram_.insert(ShinglePattern::FreqView(shingle));
- pattern->model_coverage_ += shingle->position_count();
- } else {
- pattern->program_histogram_.insert(ShinglePattern::FreqView(shingle));
- pattern->program_coverage_ += shingle->position_count();
- }
- }
- void InitialClassify() {
- for (Shingle::OwningSet::iterator p = shingle_instances_.begin();
- p != shingle_instances_.end();
- ++p) {
- // GCC's set<T>::iterator::operator *() returns a const object.
- Reclassify(const_cast<Shingle*>(&*p));
- }
- }
- // For the positions in |info|, find the shingles that overlap that position.
- void AddAffectedPositions(LabelInfo* info, ShingleSet* affected_shingles) {
- const uint8_t kWidth = Shingle::kWidth;
- for (size_t i = 0; i < info->positions_.size(); ++i) {
- size_t position = info->positions_[i];
- // Find bounds to the subrange of |trace_| we are in.
- size_t start = position < model_end_ ? 0 : model_end_;
- size_t end = position < model_end_ ? model_end_ : trace_.size();
- // Clip [position-kWidth+1, position+1)
- size_t low =
- position > start + kWidth - 1 ? position - kWidth + 1 : start;
- size_t high = position + kWidth < end ? position + 1 : end - kWidth + 1;
- for (size_t shingle_position = low;
- shingle_position < high;
- ++shingle_position) {
- Shingle* overlapping_shingle = instances_.at(shingle_position);
- affected_shingles->insert(overlapping_shingle);
- }
- }
- }
- void RemovePatternsNeedingUpdatesFromQueues() {
- for (ShinglePatternSet::iterator p = patterns_needing_updates_.begin();
- p != patterns_needing_updates_.end();
- ++p) {
- RemovePatternFromQueues(*p);
- }
- }
- void AddPatternsNeedingUpdatesToQueues() {
- for (ShinglePatternSet::iterator p = patterns_needing_updates_.begin();
- p != patterns_needing_updates_.end();
- ++p) {
- AddPatternToQueues(*p);
- }
- variable_queue_.ApplyPendingUpdates();
- }
- void RemovePatternFromQueues(const ShinglePattern* pattern) {
- int single_use_score = SingleUseScore(pattern);
- if (single_use_score > 0) {
- size_t n = single_use_pattern_queue_.erase(pattern);
- LOG_ASSERT(n == 1);
- } else if (pattern->program_histogram_.empty() &&
- pattern->model_histogram_.empty()) {
- NOTREACHED(); // Should not come back to life.
- } else if (pattern->program_histogram_.empty()) {
- // Useless pattern.
- } else {
- active_non_single_use_patterns_.erase(pattern);
- AddPatternToLabelQueue(pattern, -1);
- }
- }
- void AddPatternToQueues(const ShinglePattern* pattern) {
- int single_use_score = SingleUseScore(pattern);
- if (single_use_score > 0) {
- single_use_pattern_queue_.insert(pattern);
- } else if (pattern->program_histogram_.empty() &&
- pattern->model_histogram_.empty()) {
- } else if (pattern->program_histogram_.empty()) {
- // Useless pattern.
- } else {
- active_non_single_use_patterns_.insert(pattern);
- AddPatternToLabelQueue(pattern, +1);
- }
- }
- void AddPatternToLabelQueue(const ShinglePattern* pattern, int sign) {
- // For each possible assignment in this pattern, update the potential
- // contributions to the LabelInfo queues.
- // We want to find for each symbol (LabelInfo) the maximum contribution that
- // could be achieved by making shingle-wise assignments between shingles in
- // the model and shingles in the program.
- //
- // If the shingles in the histograms are independent (no two shingles have a
- // symbol in common) then any permutation of the assignments is possible,
- // and the maximum contribution can be found by taking the maximum over all
- // the pairs.
- //
- // If the shingles are dependent two things happen. The maximum
- // contribution to any given symbol is a sum because the symbol has
- // contributions from all the shingles containing it. Second, some
- // assignments are blocked by previous incompatible assignments. We want to
- // avoid a combinatorial search, so we ignore the blocking.
- const size_t kUnwieldy = 5;
- typedef std::map<LabelInfo*, int> LabelToScore;
- typedef std::map<LabelInfo*, LabelToScore > ScoreSet;
- ScoreSet maxima;
- size_t n_model_samples = 0;
- for (ShinglePattern::Histogram::const_iterator model_iter =
- pattern->model_histogram_.begin();
- model_iter != pattern->model_histogram_.end();
- ++model_iter) {
- if (++n_model_samples > kUnwieldy) break;
- const ShinglePattern::FreqView& model_freq = *model_iter;
- int m1 = model_freq.count();
- const Shingle* model_instance = model_freq.instance();
- ScoreSet sums;
- size_t n_program_samples = 0;
- for (ShinglePattern::Histogram::const_iterator program_iter =
- pattern->program_histogram_.begin();
- program_iter != pattern->program_histogram_.end();
- ++program_iter) {
- if (++n_program_samples > kUnwieldy) break;
- const ShinglePattern::FreqView& program_freq = *program_iter;
- int p1 = program_freq.count();
- const Shingle* program_instance = program_freq.instance();
- // int score = p1; // ? weigh all equally??
- int score = std::min(p1, m1);
- for (uint8_t i = 0; i < Shingle::kWidth; ++i) {
- LabelInfo* program_info = program_instance->at(i);
- LabelInfo* model_info = model_instance->at(i);
- if ((model_info->assignment_ == nullptr) !=
- (program_info->assignment_ == nullptr)) {
- VLOG(2) << "ERROR " << i
- << "\n\t" << ToString(pattern, 10)
- << "\n\t" << ToString(program_instance)
- << "\n\t" << ToString(model_instance);
- }
- if (!program_info->assignment_ && !model_info->assignment_) {
- sums[program_info][model_info] += score;
- }
- }
- }
- for (ScoreSet::iterator assignee_iterator = sums.begin();
- assignee_iterator != sums.end();
- ++assignee_iterator) {
- LabelInfo* program_info = assignee_iterator->first;
- for (LabelToScore::iterator p = assignee_iterator->second.begin();
- p != assignee_iterator->second.end();
- ++p) {
- LabelInfo* model_info = p->first;
- int score = p->second;
- int* slot = &maxima[program_info][model_info];
- *slot = std::max(*slot, score);
- }
- }
- }
- for (ScoreSet::iterator assignee_iterator = maxima.begin();
- assignee_iterator != maxima.end();
- ++assignee_iterator) {
- LabelInfo* program_info = assignee_iterator->first;
- for (LabelToScore::iterator p = assignee_iterator->second.begin();
- p != assignee_iterator->second.end();
- ++p) {
- LabelInfo* model_info = p->first;
- int score = sign * p->second;
- variable_queue_.AddPendingUpdate(program_info, model_info, score);
- }
- }
- }
- void AssignOne(LabelInfo* model_info, LabelInfo* program_info) {
- LOG_ASSERT(!model_info->assignment_);
- LOG_ASSERT(!program_info->assignment_);
- LOG_ASSERT(model_info->is_model_);
- LOG_ASSERT(!program_info->is_model_);
- VLOG(3) << "Assign " << ToString(program_info)
- << " := " << ToString(model_info);
- ShingleSet affected_shingles;
- AddAffectedPositions(model_info, &affected_shingles);
- AddAffectedPositions(program_info, &affected_shingles);
- for (ShingleSet::iterator p = affected_shingles.begin();
- p != affected_shingles.end();
- ++p) {
- patterns_needing_updates_.insert((*p)->pattern());
- }
- RemovePatternsNeedingUpdatesFromQueues();
- for (ShingleSet::iterator p = affected_shingles.begin();
- p != affected_shingles.end();
- ++p) {
- Declassify(*p);
- }
- program_info->label_->index_ = model_info->label_->index_;
- // Mark as assigned
- model_info->assignment_ = program_info;
- program_info->assignment_ = model_info;
- for (ShingleSet::iterator p = affected_shingles.begin();
- p != affected_shingles.end();
- ++p) {
- Reclassify(*p);
- }
- AddPatternsNeedingUpdatesToQueues();
- }
- bool AssignFirstVariableOfHistogramHead(const ShinglePattern& pattern) {
- const ShinglePattern::FreqView& program_1 =
- *pattern.program_histogram_.begin();
- const ShinglePattern::FreqView& model_1 = *pattern.model_histogram_.begin();
- const Shingle* program_instance = program_1.instance();
- const Shingle* model_instance = model_1.instance();
- size_t variable_index = pattern.index_->first_variable_index_;
- LabelInfo* program_info = program_instance->at(variable_index);
- LabelInfo* model_info = model_instance->at(variable_index);
- AssignOne(model_info, program_info);
- return true;
- }
- bool FindAndAssignBestLeader() {
- LOG_ASSERT(patterns_needing_updates_.empty());
- if (!single_use_pattern_queue_.empty()) {
- const ShinglePattern& pattern = **single_use_pattern_queue_.begin();
- return AssignFirstVariableOfHistogramHead(pattern);
- }
- if (variable_queue_.empty())
- return false;
- const VariableQueue::ScoreAndLabel best = variable_queue_.first();
- int score = best.first;
- LabelInfo* assignee = best.second;
- // TODO(sra): score (best.first) can be zero. A zero score means we are
- // blindly picking between two (or more) alternatives which look the same.
- // If we exit on the first zero-score we sometimes get 3-4% better total
- // compression. This indicates that 'infill' is doing a better job than
- // picking blindly. Perhaps we can use an extended region around the
- // undistinguished competing alternatives to break the tie.
- if (score == 0) {
- variable_queue_.Print();
- return false;
- }
- AssignmentCandidates* candidates = assignee->candidates();
- if (candidates->empty())
- return false; // Should not happen.
- AssignOne(candidates->top_candidate(), assignee);
- return true;
- }
- private:
- // The trace vector contains the model sequence [0, model_end_) followed by
- // the program sequence [model_end_, trace.end())
- const Trace& trace_;
- size_t model_end_;
- // |shingle_instances_| is the set of 'interned' shingles.
- Shingle::OwningSet shingle_instances_;
- // |instances_| maps from position in |trace_| to Shingle at that position.
- std::vector<Shingle*> instances_;
- SingleUsePatternQueue single_use_pattern_queue_;
- ShinglePatternSet active_non_single_use_patterns_;
- VariableQueue variable_queue_;
- // Transient information: when we make an assignment, we need to recompute
- // priority queue information derived from these ShinglePatterns.
- ShinglePatternSet patterns_needing_updates_;
- typedef std::map<ShinglePattern::Index,
- ShinglePattern, ShinglePatternIndexLess> IndexToPattern;
- IndexToPattern patterns_;
- };
- class Adjuster : public AdjustmentMethod {
- public:
- Adjuster() : prog_(nullptr), model_(nullptr) {}
- Adjuster(const Adjuster&) = delete;
- Adjuster& operator=(const Adjuster&) = delete;
- ~Adjuster() = default;
- bool Adjust(const AssemblyProgram& model, AssemblyProgram* program) {
- VLOG(1) << "Adjuster::Adjust";
- prog_ = program;
- model_ = &model;
- return Finish();
- }
- bool Finish() {
- prog_->UnassignIndexes();
- Trace abs32_trace_;
- Trace rel32_trace_;
- CollectTraces(model_, &abs32_trace_, &rel32_trace_, true);
- size_t abs32_model_end = abs32_trace_.size();
- size_t rel32_model_end = rel32_trace_.size();
- CollectTraces(prog_, &abs32_trace_, &rel32_trace_, false);
- Solve(abs32_trace_, abs32_model_end);
- Solve(rel32_trace_, rel32_model_end);
- prog_->AssignRemainingIndexes();
- return true;
- }
- private:
- void CollectTraces(const AssemblyProgram* program, Trace* abs32, Trace* rel32,
- bool is_model) {
- label_info_maker_.ResetDebugLabel();
- for (Label* label : program->abs32_label_annotations())
- ReferenceLabel(abs32, is_model, label);
- for (Label* label : program->rel32_label_annotations())
- ReferenceLabel(rel32, is_model, label);
- // TODO(sra): we could simply append all the labels in index order to
- // incorporate some costing for entropy (bigger deltas) that will be
- // introduced into the label address table by non-monotonic ordering. This
- // would have some knock-on effects to parts of the algorithm that work on
- // single-occurrence labels.
- }
- void Solve(const Trace& model, size_t model_end) {
- base::Time start_time = base::Time::Now();
- AssignmentProblem a(model, model_end);
- a.Solve();
- VLOG(1) << " Adjuster::Solve "
- << (base::Time::Now() - start_time).InSecondsF();
- }
- void ReferenceLabel(Trace* trace, bool is_model, Label* label) {
- trace->push_back(label_info_maker_.MakeLabelInfo(
- label, is_model, static_cast<uint32_t>(trace->size())));
- }
- raw_ptr<AssemblyProgram> prog_; // Program to be adjusted, owned by caller.
- raw_ptr<const AssemblyProgram>
- model_; // Program to be mimicked, owned by caller.
- LabelInfoMaker label_info_maker_;
- };
- ////////////////////////////////////////////////////////////////////////////////
- } // namespace adjustment_method_2
- AdjustmentMethod* AdjustmentMethod::MakeShingleAdjustmentMethod() {
- return new adjustment_method_2::Adjuster();
- }
- } // namespace courgette
|