1    :  // Copyright 2012 Google Inc.
   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  i :    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  E :      bool have_source1 = block1->source_ranges().size() > 0;
  44  E :      bool have_source2 = block2->source_ranges().size() > 0;
  45    :  
  46    :      // Blocks with source data go to the beginning.
  47  E :      if (have_source1 != have_source2)
  48  E :        return have_source1;
  49    :  
  50    :      // If both blocks have source data the block with earlier source
  51    :      // data wins.
  52  E :      if (have_source1 && have_source2) {
  53    :        BlockGraph::Block::SourceRanges::RangePairs::const_iterator it1 =
  54  E :            block1->source_ranges().range_pairs().begin();
  55    :        BlockGraph::Block::SourceRanges::RangePairs::const_iterator it2 =
  56  E :            block2->source_ranges().range_pairs().begin();
  57  E :        if (it1->second.start() != it2->second.start())
  58  E :          return it1->second.start() < it2->second.start();
  59  E :      }
  60    :  
  61    :      // After source addresses we use initialized/uninitialized data as a key.
  62    :      // Blocks containing strictly unitialized data go to the end.
  63  E :      bool is_zeros1 = BlockIsZeros(block1);
  64  E :      bool is_zeros2 = BlockIsZeros(block2);
  65  E :      if (is_zeros1 != is_zeros2)
  66  E :        return is_zeros2;
  67    :  
  68    :      // Finally we break ties using the block ID.
  69  E :      return block1->id() < block2->id();
  70  E :    }
  71    :  };
  72    :  
  73    :  struct SectionCompareFunctor {
  74    :    bool operator()(const BlockGraph::Section* section1,
  75  E :                    const BlockGraph::Section* section2) {
  76  E :      DCHECK(section1 != NULL);
  77  E :      DCHECK(section2 != NULL);
  78    :  
  79    :      // Simply sort by section ID.
  80  E :      return section1->id() < section2->id();
  81  E :    }
  82    :  };
  83    :  
  84    :  }  // namespace
  85    :  
  86    :  const char OriginalOrderer::kOrdererName[] = "OriginalOrderer";
  87    :  
  88    :  bool OriginalOrderer::OrderBlockGraph(OrderedBlockGraph* ordered_block_graph,
  89  E :                                        BlockGraph::Block* header_block) {
  90  E :    DCHECK(ordered_block_graph != NULL);
  91  E :    DCHECK(header_block != NULL);
  92    :  
  93    :    // Sort the sections.
  94  E :    ordered_block_graph->Sort(SectionCompareFunctor());
  95    :  
  96    :    // Sort the blocks in each section.
  97  E :    const BlockGraph* bg = ordered_block_graph->block_graph();
  98  E :    BlockGraph::SectionMap::const_iterator section_it = bg->sections().begin();
  99  E :    for (; section_it != bg->sections().end(); ++section_it) {
 100  E :      const BlockGraph::Section* section = &section_it->second;
 101  E :      ordered_block_graph->Sort(section, BlockCompareFunctor());
 102  E :    }
 103    :  
 104  E :    return true;
 105  E :  }
 106    :  
 107    :  }  // namespace orderers
 108    :  }  // namespace block_graph