adjustment_method_2.cc 45 KB

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