15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2010 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Implementation of ChunkRange class. 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "chrome/browser/safe_browsing/chunk_range.h" 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/strings/string_number_conversions.h" 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/strings/string_split.h" 14868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/strings/string_util.h" 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ChunkRange::ChunkRange(int start) : start_(start), stop_(start) { 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ChunkRange::ChunkRange(int start, int stop) : start_(start), stop_(stop) { 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ChunkRange::ChunkRange(const ChunkRange& rhs) 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : start_(rhs.start()), stop_(rhs.stop()) { 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Helper functions ----------------------------------------------------------- 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ChunksToRangeString(const std::vector<int>& chunks, std::string* result) { 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The following code requires the range to be sorted. 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<int> sorted_chunks(chunks); 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::sort(sorted_chunks.begin(), sorted_chunks.end()); 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(result); 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->clear(); 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<int>::const_iterator iter = sorted_chunks.begin(); 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (iter != sorted_chunks.end()) { 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int range_begin = *iter; 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int range_end = *iter; 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Extend the range forward across duplicates and increments. 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (; iter != sorted_chunks.end() && *iter <= range_end + 1; ++iter) { 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) range_end = *iter; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!result->empty()) 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->append(","); 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->append(base::IntToString(range_begin)); 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (range_end > range_begin) { 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->append("-"); 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->append(base::IntToString(range_end)); 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void RangesToChunks(const std::vector<ChunkRange>& ranges, 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<int>* chunks) { 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(chunks); 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < ranges.size(); ++i) { 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const ChunkRange& range = ranges[i]; 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int chunk = range.start(); chunk <= range.stop(); ++chunk) { 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) chunks->push_back(chunk); 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool StringToRanges(const std::string& input, 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<ChunkRange>* ranges) { 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(ranges); 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Crack the string into chunk parts, then crack each part looking for a 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // range. 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<std::string> chunk_parts; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::SplitString(input, ',', &chunk_parts); 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < chunk_parts.size(); ++i) { 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<std::string> chunk_ranges; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::SplitString(chunk_parts[i], '-', &chunk_ranges); 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int start = atoi(chunk_ranges[0].c_str()); 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int stop = start; 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (chunk_ranges.size() == 2) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stop = atoi(chunk_ranges[1].c_str()); 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (start == 0 || stop == 0) { 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // atoi error, since chunk numbers are guaranteed to never be 0. 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ranges->clear(); 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ranges->push_back(ChunkRange(start, stop)); 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Binary search over a series of ChunkRanges. 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool IsChunkInRange(int chunk_number, const std::vector<ChunkRange>& ranges) { 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ranges.empty()) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int low = 0; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int high = ranges.size() - 1; 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (low <= high) { 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int mid = ((unsigned int)low + (unsigned int)high) >> 1; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const ChunkRange& chunk = ranges[mid]; 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((chunk.stop() >= chunk_number) && (chunk.start() <= chunk_number)) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; // chunk_number is in range. 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Adjust our mid point. 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (chunk.stop() < chunk_number) 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) low = mid + 1; 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) high = mid - 1; 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 117