text: // Copyright 2014 The Chromium Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  
  #include "components/favicon_base/select_favicon_frames.h"
  
  #include <algorithm>
  #include <cmath>
  #include <limits>
  #include <map>
  #include <set>
  
  #include "base/macros.h"
  #include "components/favicon_base/favicon_util.h"
  #include "skia/ext/image_operations.h"
  #include "third_party/skia/include/core/SkCanvas.h"
  #include "ui/gfx/geometry/size.h"
  #include "ui/gfx/image/image.h"
  #include "ui/gfx/image/image_skia.h"
  #include "ui/gfx/image/image_skia_source.h"
  
  namespace {
  
  size_t BiggestCandidate(const std::vector<gfx::Size>& candidate_sizes) {
    size_t max_index = 0;
    int max_area = candidate_sizes[0].GetArea();
    for (size_t i = 1; i < candidate_sizes.size(); ++i) {
      int area = candidate_sizes[i].GetArea();
      if (area > max_area) {
        max_area = area;
        max_index = i;
      }
    }
    return max_index;
  }
  
  SkBitmap SampleNearestNeighbor(const SkBitmap& contents, int desired_size) {
    SkBitmap bitmap;
    bitmap.allocN32Pixels(desired_size, desired_size);
    if (!contents.isOpaque())
      bitmap.eraseARGB(0, 0, 0, 0);
  
    {
      SkCanvas canvas(bitmap);
      canvas.drawBitmapRect(
          contents, SkRect::MakeIWH(desired_size, desired_size), NULL);
    }
  
    return bitmap;
  }
  
  size_t GetCandidateIndexWithBestScore(
      const std::vector<gfx::Size>& candidate_sizes,
      int desired_size,
      float* score) {
    DCHECK_NE(desired_size, 0);
  
    // Try to find an exact match.
    for (size_t i = 0; i < candidate_sizes.size(); ++i) {
      if (candidate_sizes[i].width() == desired_size &&
          candidate_sizes[i].height() == desired_size) {
        *score = 1;
        return i;
      }
    }
  
    // Huge favicon bitmaps often have a completely different visual style from
    // smaller favicon bitmaps. Avoid them.
    const int kHugeEdgeSize = desired_size * 8;
  
    // Order of preference:
    // 1) Bitmaps with width and height smaller than |kHugeEdgeSize|.
    // 2) Bitmaps which need to be scaled down instead of up.
    // 3) Bitmaps which do not need to be scaled as much.
    size_t candidate_index = std::numeric_limits<size_t>::max();
    float candidate_score = 0;
    for (size_t i = 0; i < candidate_sizes.size(); ++i) {
      float average_edge =
          (candidate_sizes[i].width() + candidate_sizes[i].height()) / 2.0f;
  
      float score = 0;
      if (candidate_sizes[i].width() >= kHugeEdgeSize ||
          candidate_sizes[i].height() >= kHugeEdgeSize) {
        score = std::min(1.0f, desired_size / average_edge) * 0.01f;
      } else if (candidate_sizes[i].width() >= desired_size &&
                 candidate_sizes[i].height() >= desired_size) {
        score = desired_size / average_edge * 0.01f + 0.15f;
      } else {
        score = std::min(1.0f, average_edge / desired_size) * 0.01f + 0.1f;
      }
  
      if (candidate_index == std::numeric_limits<size_t>::max() ||
          score > candidate_score) {
        candidate_index = i;
        candidate_score = score;
      }
    }
    *score = candidate_score;
  
    return candidate_index;
  }
  
  // Represents the index of the best candidate for |desired_size| from the
  // |candidate_sizes| passed into GetCandidateIndicesWithBestScores().
  struct SelectionResult {
    // index in |candidate_sizes| of the best candidate.
    size_t index;
  
    // The desired size for which |index| is the best candidate.
    int desired_size;
  };
  
  void GetCandidateIndicesWithBestScores(
      const std::vector<gfx::Size>& candidate_sizes,
      const std::vector<int>& desired_sizes,
      float* match_score,
      std::vector<SelectionResult>* results) {
    if (candidate_sizes.empty() || desired_sizes.empty()) {
      if (match_score)
        *match_score = 0.0f;
      return;
    }
  
    std::vector<int>::const_iterator zero_size_it =
        std::find(desired_sizes.begin(), desired_sizes.end(), 0);
    if (zero_size_it != desired_sizes.end()) {
      // Just return the biggest image available.
      SelectionResult result;
      result.index = BiggestCandidate(candidate_sizes);
      result.desired_size = 0;
      results->push_back(result);
      if (match_score)
        *match_score = 1.0f;
      return;
    }
  
    float total_score = 0;
    for (size_t i = 0; i < desired_sizes.size(); ++i) {
      float score;
      SelectionResult result;
      result.desired_size = desired_sizes[i];
      result.index = GetCandidateIndexWithBestScore(
          candidate_sizes, result.desired_size, &score);
      results->push_back(result);
      total_score += score;
    }
  
    if (match_score)
      *match_score = total_score / desired_sizes.size();
  }
  
  // Resize |source_bitmap|
  SkBitmap GetResizedBitmap(const SkBitmap& source_bitmap,
                            gfx::Size original_size,
                            int desired_size_in_pixel) {
    if (desired_size_in_pixel == 0 ||
        (original_size.width() == desired_size_in_pixel &&
         original_size.height() == desired_size_in_pixel)) {
      return source_bitmap;
    }
    if (desired_size_in_pixel % original_size.width() == 0 &&
        desired_size_in_pixel % original_size.height() == 0) {
      return SampleNearestNeighbor(source_bitmap, desired_size_in_pixel);
    }
    return skia::ImageOperations::Resize(source_bitmap,
                                         skia::ImageOperations::RESIZE_LANCZOS3,
                                         desired_size_in_pixel,
                                         desired_size_in_pixel);
  }
  
  class FaviconImageSource : public gfx::ImageSkiaSource {
   public:
    FaviconImageSource() {}
    ~FaviconImageSource() override {}
  
    // gfx::ImageSkiaSource:
    gfx::ImageSkiaRep GetImageForScale(float scale) override {
      const gfx::ImageSkiaRep* rep = NULL;
      // gfx::ImageSkia passes one of the resource scale factors. The source
      // should return:
      // 1) The ImageSkiaRep with the highest scale if all available
      // scales are smaller than |scale|.
      // 2) The ImageSkiaRep with the smallest one that is larger than |scale|.
      // Note: Keep this logic consistent with the PNGImageSource in
      // ui/gfx/image.cc.
      // TODO(oshima): consolidate these logic into one place.
      for (std::vector<gfx::ImageSkiaRep>::const_iterator iter =
               image_skia_reps_.begin();
           iter != image_skia_reps_.end(); ++iter) {
        if ((*iter).scale() == scale)
          return (*iter);
        if (!rep || rep->scale() < (*iter).scale())
          rep = &(*iter);
        if (rep->scale() >= scale)
          break;
      }
      DCHECK(rep);
      return rep ? *rep : gfx::ImageSkiaRep();
    }
  
    void AddImageSkiaRep(const gfx::ImageSkiaRep& rep) {
      image_skia_reps_.push_back(rep);
    }
  
   private:
    std::vector<gfx::ImageSkiaRep> image_skia_reps_;
    DISALLOW_COPY_AND_ASSIGN(FaviconImageSource);
  };
  
  }  // namespace
  
  const float kSelectFaviconFramesInvalidScore = -1.0f;
  
  gfx::ImageSkia CreateFaviconImageSkia(
      const std::vector<SkBitmap>& bitmaps,
      const std::vector<gfx::Size>& original_sizes,
      int desired_size_in_dip,
      float* score) {
  
    const std::vector<float>& favicon_scales = favicon_base::GetFaviconScales();
    std::vector<int> desired_sizes;
  
    if (desired_size_in_dip == 0) {
      desired_sizes.push_back(0);
    } else {
      for (std::vector<float>::const_iterator iter = favicon_scales.begin();
           iter != favicon_scales.end(); ++iter) {
        desired_sizes.push_back(
            static_cast<int>(ceil(desired_size_in_dip * (*iter))));
      }
    }
  
    std::vector<SelectionResult> results;
    GetCandidateIndicesWithBestScores(original_sizes,
                                      desired_sizes,
                                      score,
                                      &results);
    if (results.size() == 0)
      return gfx::ImageSkia();
  
    if (desired_size_in_dip == 0) {
      size_t index = results[0].index;
      return gfx::ImageSkia(gfx::ImageSkiaRep(bitmaps[index], 1.0f));
    }
  
    FaviconImageSource* image_source = new FaviconImageSource;
  
    for (size_t i = 0; i < results.size(); ++i) {
      size_t index = results[i].index;
      image_source->AddImageSkiaRep(
          gfx::ImageSkiaRep(GetResizedBitmap(bitmaps[index],
                                             original_sizes[index],
                                             desired_sizes[i]),
                            favicon_scales[i]));
    }
    return gfx::ImageSkia(image_source,
                          gfx::Size(desired_size_in_dip, desired_size_in_dip));
  }
  
  void SelectFaviconFrameIndices(const std::vector<gfx::Size>& frame_pixel_sizes,
                                 const std::vector<int>& desired_sizes,
                                 std::vector<size_t>* best_indices,
                                 float* match_score) {
    std::vector<SelectionResult> results;
    GetCandidateIndicesWithBestScores(
        frame_pixel_sizes, desired_sizes, match_score, &results);
  
    std::set<size_t> already_added;
    for (size_t i = 0; i < results.size(); ++i) {
      size_t index = results[i].index;
      // GetCandidateIndicesWithBestScores() will return duplicate indices if the
      // bitmap data with |frame_pixel_sizes[index]| should be used for multiple
      // scale factors. Remove duplicates here such that |best_indices| contains
      // no duplicates.
      if (already_added.find(index) == already_added.end()) {
        already_added.insert(index);
        best_indices->push_back(index);
      }
    }
  }
  