chrome/browser/safe_browsing/chunk_range.cc

   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   for (const base::StringPiece& chunk : base::SplitStringPiece(
  73            input, ",", base::TRIM_WHITESPACE, base::SPLIT_WANT_ALL)) {
  74     std::vector<std::string> chunk_ranges = base::SplitString(
  75         chunk, "-", base::TRIM_WHITESPACE, base::SPLIT_WANT_ALL);
  76     int start = atoi(chunk_ranges[0].c_str());
  77     int stop = start;
  78     if (chunk_ranges.size() == 2)
  79       stop = atoi(chunk_ranges[1].c_str());
  80     if (start == 0 || stop == 0) {
  81       // atoi error, since chunk numbers are guaranteed to never be 0.
  82       ranges->clear();
  83       return false;
  84     }
  85     ranges->push_back(ChunkRange(start, stop));
  86   }
  87
  88   return true;
  89 }
  90
  91 // Binary search over a series of ChunkRanges.
  92 bool IsChunkInRange(int chunk_number, const std::vector<ChunkRange>& ranges) {
  93   if (ranges.empty())
  94     return false;
  95
  96   int low = 0;
  97   int high = ranges.size() - 1;
  98
  99   while (low <= high) {
 100     // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
 101     int mid = ((unsigned int)low + (unsigned int)high) >> 1;
 102     const ChunkRange& chunk = ranges[mid];
 103     if ((chunk.stop() >= chunk_number) && (chunk.start() <= chunk_number))
 104       return true;  // chunk_number is in range.
 105
 106     // Adjust our mid point.
 107     if (chunk.stop() < chunk_number)
 108       low = mid + 1;
 109     else
 110       high = mid - 1;
 111   }
 112
 113   return false;
 114 }