OLD | NEW |
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "courgette/adjustment_method.h" | 5 #include "courgette/adjustment_method.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <limits> | 8 #include <limits> |
9 #include <list> | 9 #include <list> |
10 #include <map> | 10 #include <map> |
(...skipping 346 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
357 | 357 |
358 LabelInfo::~LabelInfo() { | 358 LabelInfo::~LabelInfo() { |
359 delete candidates_; | 359 delete candidates_; |
360 } | 360 } |
361 | 361 |
362 // A Shingle is a short fixed-length string of LabelInfos that actually occurs | 362 // A Shingle is a short fixed-length string of LabelInfos that actually occurs |
363 // in a Trace. A Shingle may occur many times. We repesent the Shingle by the | 363 // in a Trace. A Shingle may occur many times. We repesent the Shingle by the |
364 // position of one of the occurrences in the Trace. | 364 // position of one of the occurrences in the Trace. |
365 class Shingle { | 365 class Shingle { |
366 public: | 366 public: |
367 static const size_t kWidth = 5; | 367 static const uint8 kWidth = 5; |
368 | 368 |
369 struct InterningLess { | 369 struct InterningLess { |
370 bool operator()(const Shingle& a, const Shingle& b) const; | 370 bool operator()(const Shingle& a, const Shingle& b) const; |
371 }; | 371 }; |
372 | 372 |
373 typedef std::set<Shingle, InterningLess> OwningSet; | 373 typedef std::set<Shingle, InterningLess> OwningSet; |
374 | 374 |
375 static Shingle* Find(const Trace& trace, size_t position, | 375 static Shingle* Find(const Trace& trace, size_t position, |
376 OwningSet* owning_set) { | 376 OwningSet* owning_set) { |
377 std::pair<OwningSet::iterator, bool> pair = | 377 std::pair<OwningSet::iterator, bool> pair = |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
423 // We can't disallow the copy constructor because we use std::set<Shingle> and | 423 // We can't disallow the copy constructor because we use std::set<Shingle> and |
424 // VS2005's implementation of std::set<T>::set() requires T to have a copy | 424 // VS2005's implementation of std::set<T>::set() requires T to have a copy |
425 // constructor. | 425 // constructor. |
426 // DISALLOW_COPY_AND_ASSIGN(Shingle); | 426 // DISALLOW_COPY_AND_ASSIGN(Shingle); |
427 void operator=(const Shingle&); // Disallow assignment only. | 427 void operator=(const Shingle&); // Disallow assignment only. |
428 }; | 428 }; |
429 | 429 |
430 std::string ToString(const Shingle* instance) { | 430 std::string ToString(const Shingle* instance) { |
431 std::string s; | 431 std::string s; |
432 const char* sep = "<"; | 432 const char* sep = "<"; |
433 for (size_t i = 0; i < Shingle::kWidth; ++i) { | 433 for (uint8 i = 0; i < Shingle::kWidth; ++i) { |
434 // base::StringAppendF(&s, "%s%x ", sep, instance.at(i)->label_->rva_); | 434 // base::StringAppendF(&s, "%s%x ", sep, instance.at(i)->label_->rva_); |
435 s += sep; | 435 s += sep; |
436 s += ToString(instance->at(i)); | 436 s += ToString(instance->at(i)); |
437 sep = ", "; | 437 sep = ", "; |
438 } | 438 } |
439 base::StringAppendF(&s, ">(%" PRIuS ")@{%d}", | 439 base::StringAppendF(&s, ">(%" PRIuS ")@{%d}", |
440 instance->exemplar_position_, | 440 instance->exemplar_position_, |
441 instance->position_count()); | 441 instance->position_count()); |
442 return s; | 442 return s; |
443 } | 443 } |
444 | 444 |
445 | 445 |
446 bool Shingle::InterningLess::operator()( | 446 bool Shingle::InterningLess::operator()( |
447 const Shingle& a, | 447 const Shingle& a, |
448 const Shingle& b) const { | 448 const Shingle& b) const { |
449 for (size_t i = 0; i < kWidth; ++i) { | 449 for (uint8 i = 0; i < kWidth; ++i) { |
450 LabelInfo* info_a = a.at(i); | 450 LabelInfo* info_a = a.at(i); |
451 LabelInfo* info_b = b.at(i); | 451 LabelInfo* info_b = b.at(i); |
452 if (info_a->label_->rva_ < info_b->label_->rva_) | 452 if (info_a->label_->rva_ < info_b->label_->rva_) |
453 return true; | 453 return true; |
454 if (info_a->label_->rva_ > info_b->label_->rva_) | 454 if (info_a->label_->rva_ > info_b->label_->rva_) |
455 return false; | 455 return false; |
456 if (info_a->is_model_ < info_b->is_model_) | 456 if (info_a->is_model_ < info_b->is_model_) |
457 return true; | 457 return true; |
458 if (info_a->is_model_ > info_b->is_model_) | 458 if (info_a->is_model_ > info_b->is_model_) |
459 return false; | 459 return false; |
(...skipping 59 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
519 int program_coverage_; | 519 int program_coverage_; |
520 }; | 520 }; |
521 | 521 |
522 std::string ToString(const ShinglePattern::Index* index) { | 522 std::string ToString(const ShinglePattern::Index* index) { |
523 std::string s; | 523 std::string s; |
524 if (index == NULL) { | 524 if (index == NULL) { |
525 s = "<null>"; | 525 s = "<null>"; |
526 } else { | 526 } else { |
527 base::StringAppendF(&s, "<%d: ", index->variables_); | 527 base::StringAppendF(&s, "<%d: ", index->variables_); |
528 const char* sep = ""; | 528 const char* sep = ""; |
529 for (size_t i = 0; i < Shingle::kWidth; ++i) { | 529 for (uint8 i = 0; i < Shingle::kWidth; ++i) { |
530 s += sep; | 530 s += sep; |
531 sep = ", "; | 531 sep = ", "; |
532 uint32 kind = index->kinds_[i]; | 532 uint32 kind = index->kinds_[i]; |
533 int offset = kind & ShinglePattern::kOffsetMask; | 533 int offset = kind & ShinglePattern::kOffsetMask; |
534 if (kind & ShinglePattern::kVariable) | 534 if (kind & ShinglePattern::kVariable) |
535 base::StringAppendF(&s, "V%d", offset); | 535 base::StringAppendF(&s, "V%d", offset); |
536 else | 536 else |
537 base::StringAppendF(&s, "%d", index->assigned_indexes_[offset]); | 537 base::StringAppendF(&s, "%d", index->assigned_indexes_[offset]); |
538 } | 538 } |
539 base::StringAppendF(&s, " %x", index->hash_); | 539 base::StringAppendF(&s, " %x", index->hash_); |
(...skipping 75 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
615 s += HistogramToStringFull(pattern->program_histogram_, " ", max); | 615 s += HistogramToStringFull(pattern->program_histogram_, " ", max); |
616 return s; | 616 return s; |
617 } | 617 } |
618 | 618 |
619 struct ShinglePatternIndexLess { | 619 struct ShinglePatternIndexLess { |
620 bool operator()(const ShinglePattern::Index& a, | 620 bool operator()(const ShinglePattern::Index& a, |
621 const ShinglePattern::Index& b) const { | 621 const ShinglePattern::Index& b) const { |
622 if (a.hash_ < b.hash_) return true; | 622 if (a.hash_ < b.hash_) return true; |
623 if (a.hash_ > b.hash_) return false; | 623 if (a.hash_ > b.hash_) return false; |
624 | 624 |
625 for (size_t i = 0; i < Shingle::kWidth; ++i) { | 625 for (uint8 i = 0; i < Shingle::kWidth; ++i) { |
626 if (a.kinds_[i] < b.kinds_[i]) return true; | 626 if (a.kinds_[i] < b.kinds_[i]) return true; |
627 if (a.kinds_[i] > b.kinds_[i]) return false; | 627 if (a.kinds_[i] > b.kinds_[i]) return false; |
628 if ((a.kinds_[i] & ShinglePattern::kVariable) == 0) { | 628 if ((a.kinds_[i] & ShinglePattern::kVariable) == 0) { |
629 if (a.assigned_indexes_[i] < b.assigned_indexes_[i]) | 629 if (a.assigned_indexes_[i] < b.assigned_indexes_[i]) |
630 return true; | 630 return true; |
631 if (a.assigned_indexes_[i] > b.assigned_indexes_[i]) | 631 if (a.assigned_indexes_[i] > b.assigned_indexes_[i]) |
632 return false; | 632 return false; |
633 } | 633 } |
634 } | 634 } |
635 return false; | 635 return false; |
636 } | 636 } |
637 }; | 637 }; |
638 | 638 |
639 static uint32 hash_combine(uint32 h, uint32 v) { | 639 static uint32 hash_combine(uint32 h, uint32 v) { |
640 h += v; | 640 h += v; |
641 return (h * (37 + 0x0000d100)) ^ (h >> 13); | 641 return (h * (37 + 0x0000d100)) ^ (h >> 13); |
642 } | 642 } |
643 | 643 |
644 ShinglePattern::Index::Index(const Shingle* instance) { | 644 ShinglePattern::Index::Index(const Shingle* instance) { |
645 uint32 hash = 0; | 645 uint32 hash = 0; |
646 variables_ = 0; | 646 variables_ = 0; |
647 unique_variables_ = 0; | 647 unique_variables_ = 0; |
648 first_variable_index_ = 255; | 648 first_variable_index_ = 255; |
649 | 649 |
650 for (uint32 i = 0; i < Shingle::kWidth; ++i) { | 650 for (uint8 i = 0; i < Shingle::kWidth; ++i) { |
651 LabelInfo* info = instance->at(i); | 651 LabelInfo* info = instance->at(i); |
652 uint32 kind = 0; | 652 uint8 kind = 0; |
653 int code = -1; | 653 int code = -1; |
654 size_t j = 0; | 654 uint8 j = 0; |
655 for ( ; j < i; ++j) { | 655 for ( ; j < i; ++j) { |
656 if (info == instance->at(j)) { // Duplicate LabelInfo | 656 if (info == instance->at(j)) { // Duplicate LabelInfo |
657 kind = kinds_[j]; | 657 kind = kinds_[j]; |
658 break; | 658 break; |
659 } | 659 } |
660 } | 660 } |
661 if (j == i) { // Not found above. | 661 if (j == i) { // Not found above. |
662 if (info->assignment_) { | 662 if (info->assignment_) { |
663 code = info->label_->index_; | 663 code = info->label_->index_; |
664 assigned_indexes_[i] = code; | 664 assigned_indexes_[i] = code; |
(...skipping 217 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
882 for (Shingle::OwningSet::const_iterator p = shingle_instances_.begin(); | 882 for (Shingle::OwningSet::const_iterator p = shingle_instances_.begin(); |
883 p != shingle_instances_.end(); | 883 p != shingle_instances_.end(); |
884 ++p) { | 884 ++p) { |
885 const Shingle& instance = *p; | 885 const Shingle& instance = *p; |
886 VLOG(2) << ToString(&instance) << " " << ToString(instance.pattern()); | 886 VLOG(2) << ToString(&instance) << " " << ToString(instance.pattern()); |
887 } | 887 } |
888 } | 888 } |
889 | 889 |
890 | 890 |
891 void AddShingles(size_t begin, size_t end) { | 891 void AddShingles(size_t begin, size_t end) { |
892 for (size_t i = begin; i + Shingle::kWidth - 1 < end; ++i) { | 892 for (size_t i = begin; i + Shingle::kWidth - 1 < end; ++i) { |
893 instances_[i] = Shingle::Find(trace_, i, &shingle_instances_); | 893 instances_[i] = Shingle::Find(trace_, i, &shingle_instances_); |
894 } | 894 } |
895 } | 895 } |
896 | 896 |
897 void Declassify(Shingle* shingle) { | 897 void Declassify(Shingle* shingle) { |
898 ShinglePattern* pattern = shingle->pattern(); | 898 ShinglePattern* pattern = shingle->pattern(); |
899 if (shingle->InModel()) { | 899 if (shingle->InModel()) { |
900 pattern->model_histogram_.erase(ShinglePattern::FreqView(shingle)); | 900 pattern->model_histogram_.erase(ShinglePattern::FreqView(shingle)); |
901 pattern->model_coverage_ -= shingle->position_count(); | 901 pattern->model_coverage_ -= shingle->position_count(); |
902 } else { | 902 } else { |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
935 for (Shingle::OwningSet::iterator p = shingle_instances_.begin(); | 935 for (Shingle::OwningSet::iterator p = shingle_instances_.begin(); |
936 p != shingle_instances_.end(); | 936 p != shingle_instances_.end(); |
937 ++p) { | 937 ++p) { |
938 // GCC's set<T>::iterator::operator *() returns a const object. | 938 // GCC's set<T>::iterator::operator *() returns a const object. |
939 Reclassify(const_cast<Shingle*>(&*p)); | 939 Reclassify(const_cast<Shingle*>(&*p)); |
940 } | 940 } |
941 } | 941 } |
942 | 942 |
943 // For the positions in |info|, find the shingles that overlap that position. | 943 // For the positions in |info|, find the shingles that overlap that position. |
944 void AddAffectedPositions(LabelInfo* info, ShingleSet* affected_shingles) { | 944 void AddAffectedPositions(LabelInfo* info, ShingleSet* affected_shingles) { |
945 const size_t kWidth = Shingle::kWidth; | 945 const uint8 kWidth = Shingle::kWidth; |
946 for (size_t i = 0; i < info->positions_.size(); ++i) { | 946 for (size_t i = 0; i < info->positions_.size(); ++i) { |
947 size_t position = info->positions_[i]; | 947 size_t position = info->positions_[i]; |
948 // Find bounds to the subrange of |trace_| we are in. | 948 // Find bounds to the subrange of |trace_| we are in. |
949 size_t start = position < model_end_ ? 0 : model_end_; | 949 size_t start = position < model_end_ ? 0 : model_end_; |
950 size_t end = position < model_end_ ? model_end_ : trace_.size(); | 950 size_t end = position < model_end_ ? model_end_ : trace_.size(); |
951 | 951 |
952 // Clip [position-kWidth+1, position+1) | 952 // Clip [position-kWidth+1, position+1) |
953 size_t low = position > start + kWidth - 1 | 953 size_t low = |
954 ? position - kWidth + 1 | 954 position > start + kWidth - 1 ? position - kWidth + 1 : start; |
955 : start; | |
956 size_t high = position + kWidth < end ? position + 1 : end - kWidth + 1; | 955 size_t high = position + kWidth < end ? position + 1 : end - kWidth + 1; |
957 | 956 |
958 for (size_t shingle_position = low; | 957 for (size_t shingle_position = low; |
959 shingle_position < high; | 958 shingle_position < high; |
960 ++shingle_position) { | 959 ++shingle_position) { |
961 Shingle* overlapping_shingle = instances_.at(shingle_position); | 960 Shingle* overlapping_shingle = instances_.at(shingle_position); |
962 affected_shingles->insert(overlapping_shingle); | 961 affected_shingles->insert(overlapping_shingle); |
963 } | 962 } |
964 } | 963 } |
965 } | 964 } |
(...skipping 87 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1053 program_iter != pattern->program_histogram_.end(); | 1052 program_iter != pattern->program_histogram_.end(); |
1054 ++program_iter) { | 1053 ++program_iter) { |
1055 if (++n_program_samples > kUnwieldy) break; | 1054 if (++n_program_samples > kUnwieldy) break; |
1056 const ShinglePattern::FreqView& program_freq = *program_iter; | 1055 const ShinglePattern::FreqView& program_freq = *program_iter; |
1057 int p1 = program_freq.count(); | 1056 int p1 = program_freq.count(); |
1058 const Shingle* program_instance = program_freq.instance(); | 1057 const Shingle* program_instance = program_freq.instance(); |
1059 | 1058 |
1060 // int score = p1; // ? weigh all equally?? | 1059 // int score = p1; // ? weigh all equally?? |
1061 int score = std::min(p1, m1); | 1060 int score = std::min(p1, m1); |
1062 | 1061 |
1063 for (size_t i = 0; i < Shingle::kWidth; ++i) { | 1062 for (uint8 i = 0; i < Shingle::kWidth; ++i) { |
1064 LabelInfo* program_info = program_instance->at(i); | 1063 LabelInfo* program_info = program_instance->at(i); |
1065 LabelInfo* model_info = model_instance->at(i); | 1064 LabelInfo* model_info = model_instance->at(i); |
1066 if ((model_info->assignment_ == NULL) != | 1065 if ((model_info->assignment_ == NULL) != |
1067 (program_info->assignment_ == NULL)) { | 1066 (program_info->assignment_ == NULL)) { |
1068 VLOG(2) << "ERROR " << i | 1067 VLOG(2) << "ERROR " << i |
1069 << "\n\t" << ToString(pattern, 10) | 1068 << "\n\t" << ToString(pattern, 10) |
1070 << "\n\t" << ToString(program_instance) | 1069 << "\n\t" << ToString(program_instance) |
1071 << "\n\t" << ToString(model_instance); | 1070 << "\n\t" << ToString(model_instance); |
1072 } | 1071 } |
1073 if (!program_info->assignment_ && !model_info->assignment_) { | 1072 if (!program_info->assignment_ && !model_info->assignment_) { |
(...skipping 216 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1290 | 1289 |
1291 //////////////////////////////////////////////////////////////////////////////// | 1290 //////////////////////////////////////////////////////////////////////////////// |
1292 | 1291 |
1293 } // namespace adjustment_method_2 | 1292 } // namespace adjustment_method_2 |
1294 | 1293 |
1295 AdjustmentMethod* AdjustmentMethod::MakeShingleAdjustmentMethod() { | 1294 AdjustmentMethod* AdjustmentMethod::MakeShingleAdjustmentMethod() { |
1296 return new adjustment_method_2::Adjuster(); | 1295 return new adjustment_method_2::Adjuster(); |
1297 } | 1296 } |
1298 | 1297 |
1299 } // namespace courgette | 1298 } // namespace courgette |
OLD | NEW |