1    :  // Copyright 2012 Google Inc. All Rights Reserved.
   2    :  //
   3    :  // Licensed under the Apache License, Version 2.0 (the "License");
   4    :  // you may not use this file except in compliance with the License.
   5    :  // You may obtain a copy of the License at
   6    :  //
   7    :  //     http://www.apache.org/licenses/LICENSE-2.0
   8    :  //
   9    :  // Unless required by applicable law or agreed to in writing, software
  10    :  // distributed under the License is distributed on an "AS IS" BASIS,
  11    :  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12    :  // See the License for the specific language governing permissions and
  13    :  // limitations under the License.
  14    :  
  15    :  #include "syzygy/block_graph/orderers/original_orderer.h"
  16    :  
  17    :  namespace block_graph {
  18    :  namespace orderers {
  19    :  
  20    :  namespace {
  21    :  
  22    :  // Returns true if the block contains only zeros, and may safely be left
  23    :  // implicitly initialized.
  24  E :  bool BlockIsZeros(const BlockGraph::Block* block) {
  25  E :    if (block->references().size() != 0)
  26  E :      return false;
  27  E :    const uint8* data = block->data();
  28  E :    if (data == NULL)
  29  E :      return true;
  30  E :    for (size_t i = 0; i < block->data_size(); ++i, ++data) {
  31  E :      if (*data != 0)
  32  E :        return false;
  33  E :    }
  34  E :    return true;
  35  E :  }
  36    :  
  37    :  struct BlockCompareFunctor {
  38    :    bool operator()(const BlockGraph::Block* block1,
  39  E :                    const BlockGraph::Block* block2) {
  40  E :      DCHECK(block1 != NULL);
  41  E :      DCHECK(block2 != NULL);
  42    :  
  43    :      // Determine if the blocks have source data.
  44  E :      bool have_source1 = block1->source_ranges().size() > 0;
  45  E :      bool have_source2 = block2->source_ranges().size() > 0;
  46    :  
  47    :      // If both blocks have source data the block with earlier source
  48    :      // data comes first. This preserves the original order where
  49    :      // possible.
  50  E :      if (have_source1 && have_source2) {
  51    :        BlockGraph::Block::SourceRanges::RangePairs::const_iterator it1 =
  52  E :            block1->source_ranges().range_pairs().begin();
  53    :        BlockGraph::Block::SourceRanges::RangePairs::const_iterator it2 =
  54  E :            block2->source_ranges().range_pairs().begin();
  55  E :        if (it1->second.start() != it2->second.start())
  56  E :          return it1->second.start() < it2->second.start();
  57    :      }
  58    :  
  59    :      // Next, we sort by initialized and uninitialized data. Blocks containing
  60    :      // strictly uninitialized data go to the end of the section.
  61  E :      bool is_zeros1 = BlockIsZeros(block1);
  62  E :      bool is_zeros2 = BlockIsZeros(block2);
  63  E :      if (is_zeros1 != is_zeros2)
  64  E :        return is_zeros2;
  65    :  
  66    :      // Blocks with source data go to the beginning.
  67  E :      if (have_source1 != have_source2)
  68  E :        return have_source1;
  69    :  
  70    :      // Finally we break ties using the block ID.
  71  E :      return block1->id() < block2->id();
  72  E :    }
  73    :  };
  74    :  
  75    :  struct SectionCompareFunctor {
  76    :    bool operator()(const BlockGraph::Section* section1,
  77  E :                    const BlockGraph::Section* section2) {
  78  E :      DCHECK(section1 != NULL);
  79  E :      DCHECK(section2 != NULL);
  80    :  
  81    :      // Simply sort by section ID.
  82  E :      return section1->id() < section2->id();
  83  E :    }
  84    :  };
  85    :  
  86    :  }  // namespace
  87    :  
  88    :  const char OriginalOrderer::kOrdererName[] = "OriginalOrderer";
  89    :  
  90    :  bool OriginalOrderer::OrderBlockGraph(OrderedBlockGraph* ordered_block_graph,
  91  E :                                        BlockGraph::Block* header_block) {
  92  E :    DCHECK(ordered_block_graph != NULL);
  93  E :    DCHECK(header_block != NULL);
  94    :  
  95    :    // Sort the sections.
  96  E :    ordered_block_graph->Sort(SectionCompareFunctor());
  97    :  
  98    :    // Sort the blocks in each section.
  99  E :    const BlockGraph* bg = ordered_block_graph->block_graph();
 100  E :    BlockGraph::SectionMap::const_iterator section_it = bg->sections().begin();
 101  E :    for (; section_it != bg->sections().end(); ++section_it) {
 102  E :      const BlockGraph::Section* section = &section_it->second;
 103  E :      ordered_block_graph->Sort(section, BlockCompareFunctor());
 104  E :    }
 105    :  
 106  E :    return true;
 107  E :  }
 108    :  
 109    :  }  // namespace orderers
 110    :  }  // namespace block_graph