Home | History | Annotate | Download | only in safe_browsing 
      1 // Copyright (c) 2010 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 //
      5 // Implementation of ChunkRange class.
      6 
      7 #include <algorithm>
      8 
      9 #include "chrome/browser/safe_browsing/chunk_range.h"
     10 
     11 #include "base/logging.h"
     12 #include "base/strings/string_number_conversions.h"
     13 #include "base/strings/string_split.h"
     14 #include "base/strings/string_util.h"
     15 
     16 ChunkRange::ChunkRange(int start) : start_(start), stop_(start) {
     17 }
     18 
     19 ChunkRange::ChunkRange(int start, int stop) : start_(start), stop_(stop) {
     20 }
     21 
     22 ChunkRange::ChunkRange(const ChunkRange& rhs)
     23     : start_(rhs.start()), stop_(rhs.stop()) {
     24 }
     25 
     26 // Helper functions -----------------------------------------------------------
     27 
     28 void ChunksToRangeString(const std::vector<int>& chunks, std::string* result) {
     29   // The following code requires the range to be sorted.
     30   std::vector<int> sorted_chunks(chunks);
     31   std::sort(sorted_chunks.begin(), sorted_chunks.end());
     32 
     33   DCHECK(result);
     34   result->clear();
     35   std::vector<int>::const_iterator iter = sorted_chunks.begin();
     36   while (iter != sorted_chunks.end()) {
     37     const int range_begin = *iter;
     38     int range_end = *iter;
     39 
     40     // Extend the range forward across duplicates and increments.
     41     for (; iter != sorted_chunks.end() && *iter <= range_end + 1; ++iter) {
     42       range_end = *iter;
     43     }
     44 
     45     if (!result->empty())
     46       result->append(",");
     47     result->append(base::IntToString(range_begin));
     48     if (range_end > range_begin) {
     49       result->append("-");
     50       result->append(base::IntToString(range_end));
     51     }
     52   }
     53 }
     54 
     55 void RangesToChunks(const std::vector<ChunkRange>& ranges,
     56                     std::vector<int>* chunks) {
     57   DCHECK(chunks);
     58   for (size_t i = 0; i < ranges.size(); ++i) {
     59     const ChunkRange& range = ranges[i];
     60     for (int chunk = range.start(); chunk <= range.stop(); ++chunk) {
     61       chunks->push_back(chunk);
     62     }
     63   }
     64 }
     65 
     66 bool StringToRanges(const std::string& input,
     67                     std::vector<ChunkRange>* ranges) {
     68   DCHECK(ranges);
     69 
     70   // Crack the string into chunk parts, then crack each part looking for a
     71   // range.
     72   std::vector<std::string> chunk_parts;
     73   base::SplitString(input, ',', &chunk_parts);
     74 
     75   for (size_t i = 0; i < chunk_parts.size(); ++i) {
     76     std::vector<std::string> chunk_ranges;
     77     base::SplitString(chunk_parts[i], '-', &chunk_ranges);
     78     int start = atoi(chunk_ranges[0].c_str());
     79     int stop = start;
     80     if (chunk_ranges.size() == 2)
     81       stop = atoi(chunk_ranges[1].c_str());
     82     if (start == 0 || stop == 0) {
     83       // atoi error, since chunk numbers are guaranteed to never be 0.
     84       ranges->clear();
     85       return false;
     86     }
     87     ranges->push_back(ChunkRange(start, stop));
     88   }
     89 
     90   return true;
     91 }
     92 
     93 // Binary search over a series of ChunkRanges.
     94 bool IsChunkInRange(int chunk_number, const std::vector<ChunkRange>& ranges) {
     95   if (ranges.empty())
     96     return false;
     97 
     98   int low = 0;
     99   int high = ranges.size() - 1;
    100 
    101   while (low <= high) {
    102     // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
    103     int mid = ((unsigned int)low + (unsigned int)high) >> 1;
    104     const ChunkRange& chunk = ranges[mid];
    105     if ((chunk.stop() >= chunk_number) && (chunk.start() <= chunk_number))
    106       return true;  // chunk_number is in range.
    107 
    108     // Adjust our mid point.
    109     if (chunk.stop() < chunk_number)
    110       low = mid + 1;
    111     else
    112       high = mid - 1;
    113   }
    114 
    115   return false;
    116 }
    117