| 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 |