1// Copyright (c) 2012 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#include "chrome/browser/history/select_favicon_frames.h"
6
7#include <set>
8
9#include "skia/ext/image_operations.h"
10#include "third_party/skia/include/core/SkCanvas.h"
11#include "ui/gfx/image/image.h"
12#include "ui/gfx/image/image_skia.h"
13#include "ui/gfx/size.h"
14
15namespace {
16
17size_t BiggestCandidate(const std::vector<gfx::Size>& candidate_sizes) {
18  size_t max_index = 0;
19  int max_area = candidate_sizes[0].GetArea();
20  for (size_t i = 1; i < candidate_sizes.size(); ++i) {
21    int area = candidate_sizes[i].GetArea();
22    if (area > max_area) {
23      max_area = area;
24      max_index = i;
25    }
26  }
27  return max_index;
28}
29
30SkBitmap SampleNearestNeighbor(const SkBitmap& contents, int desired_size) {
31  SkBitmap bitmap;
32  bitmap.setConfig(
33      SkBitmap::kARGB_8888_Config, desired_size, desired_size);
34  bitmap.allocPixels();
35  if (!contents.isOpaque())
36    bitmap.eraseARGB(0, 0, 0, 0);
37
38  {
39    SkCanvas canvas(bitmap);
40    SkRect dest(SkRect::MakeWH(desired_size, desired_size));
41    canvas.drawBitmapRect(contents, NULL, dest);
42  }
43
44  return bitmap;
45}
46
47enum ResizeMethod {
48NONE,
49SAMPLE_NEAREST_NEIGHBOUR,
50LANCZOS
51};
52
53size_t GetCandidateIndexWithBestScore(
54    const std::vector<gfx::Size>& candidate_sizes_in_pixel,
55    ui::ScaleFactor scale_factor,
56    int desired_size_in_dip,
57    float* score,
58    ResizeMethod* resize_method) {
59  DCHECK_NE(desired_size_in_dip, 0);
60
61  float scale = ui::GetImageScale(scale_factor);
62  int desired_size_in_pixel =
63      static_cast<int>(desired_size_in_dip * scale + 0.5f);
64
65  // Try to find an exact match.
66  for (size_t i = 0; i < candidate_sizes_in_pixel.size(); ++i) {
67    if (candidate_sizes_in_pixel[i].width() == desired_size_in_pixel &&
68        candidate_sizes_in_pixel[i].height() == desired_size_in_pixel) {
69      *score = 1;
70      *resize_method = NONE;
71      return i;
72    }
73  }
74
75  // Huge favicon bitmaps often have a completely different visual style from
76  // smaller favicon bitmaps. Avoid these favicon bitmaps when a favicon of
77  // gfx::kFaviconSize DIP is requested.
78  const int kHugeEdgeSizeInPixel = desired_size_in_pixel * 8;
79
80  // Order of preference:
81  // 1) Bitmaps with width and height smaller than |kHugeEdgeSizeInPixel|.
82  // 2) Bitmaps which need to be scaled down instead of up.
83  // 3) Bitmaps which do not need to be scaled as much.
84  int candidate_index = -1;
85  float candidate_score = 0;
86  for (size_t i = 0; i < candidate_sizes_in_pixel.size(); ++i) {
87    float average_edge_in_pixel = (candidate_sizes_in_pixel[i].width() +
88        candidate_sizes_in_pixel[i].height()) / 2.0f;
89
90    float score = 0;
91    if (candidate_sizes_in_pixel[i].width() >= kHugeEdgeSizeInPixel ||
92        candidate_sizes_in_pixel[i].height() >= kHugeEdgeSizeInPixel) {
93      score = std::min(1.0f, desired_size_in_pixel / average_edge_in_pixel) *
94          0.01f;
95    } else if (candidate_sizes_in_pixel[i].width() >= desired_size_in_pixel &&
96               candidate_sizes_in_pixel[i].height() >= desired_size_in_pixel) {
97      score = desired_size_in_pixel / average_edge_in_pixel * 0.01f + 0.15f;
98    } else {
99      score = std::min(1.0f, average_edge_in_pixel / desired_size_in_pixel) *
100          0.01f + 0.1f;
101    }
102
103    if (candidate_index == -1 || score > candidate_score) {
104      candidate_index = i;
105      candidate_score = score;
106    }
107  }
108  *score = candidate_score;
109
110  // Integer multiples are built using nearest neighbor sampling. Otherwise,
111  // Lanczos scaling is used.
112  const gfx::Size& candidate_size_in_pixel =
113      candidate_sizes_in_pixel[candidate_index];
114  if (candidate_size_in_pixel.IsEmpty()) {
115    *resize_method = NONE;
116  } else if (desired_size_in_pixel % candidate_size_in_pixel.width() == 0 &&
117             desired_size_in_pixel % candidate_size_in_pixel.height() == 0) {
118    *resize_method = SAMPLE_NEAREST_NEIGHBOUR;
119  } else {
120    *resize_method = LANCZOS;
121  }
122  return candidate_index;
123}
124
125// Represents the index of the best candidate for a |scale_factor| from the
126// |candidate_sizes| passed into GetCandidateIndicesWithBestScores().
127struct SelectionResult {
128  // index in |candidate_sizes| of the best candidate.
129  size_t index;
130
131  // The ScaleFactor for which |index| is the best candidate.
132  ui::ScaleFactor scale_factor;
133
134  // How the bitmap data that the bitmap with |candidate_sizes[index]| should
135  // be resized for displaying in the UI.
136  ResizeMethod resize_method;
137};
138
139void GetCandidateIndicesWithBestScores(
140    const std::vector<gfx::Size>& candidate_sizes,
141    const std::vector<ui::ScaleFactor>& scale_factors,
142    int desired_size,
143    float* match_score,
144    std::vector<SelectionResult>* results) {
145  if (candidate_sizes.empty()) {
146    *match_score = 0.0f;
147    return;
148  }
149
150  if (desired_size == 0) {
151    // Just return the biggest image available.
152    SelectionResult result;
153    result.index = BiggestCandidate(candidate_sizes);
154    result.scale_factor = ui::SCALE_FACTOR_100P;
155    result.resize_method = NONE;
156    results->push_back(result);
157    if (match_score)
158      *match_score = 1.0f;
159    return;
160  }
161
162  float total_score = 0;
163  for (size_t i = 0; i < scale_factors.size(); ++i) {
164    float score;
165    SelectionResult result;
166    result.scale_factor = scale_factors[i];
167    result.index = GetCandidateIndexWithBestScore(candidate_sizes,
168        result.scale_factor, desired_size, &score, &result.resize_method);
169    results->push_back(result);
170    total_score += score;
171  }
172
173  if (match_score)
174    *match_score = total_score / scale_factors.size();
175}
176
177// Resize |source_bitmap| using |resize_method|.
178SkBitmap GetResizedBitmap(const SkBitmap& source_bitmap,
179                          int desired_size_in_dip,
180                          ui::ScaleFactor scale_factor,
181                          ResizeMethod resize_method) {
182  float scale = ui::GetImageScale(scale_factor);
183  int desired_size_in_pixel = static_cast<int>(
184      desired_size_in_dip * scale + 0.5f);
185
186  switch (resize_method) {
187    case NONE:
188      return source_bitmap;
189    case SAMPLE_NEAREST_NEIGHBOUR:
190      return SampleNearestNeighbor(source_bitmap, desired_size_in_pixel);
191    case LANCZOS:
192      return skia::ImageOperations::Resize(
193          source_bitmap, skia::ImageOperations::RESIZE_LANCZOS3,
194          desired_size_in_pixel, desired_size_in_pixel);
195  }
196  return source_bitmap;
197}
198
199}  // namespace
200
201const float kSelectFaviconFramesInvalidScore = -1.0f;
202
203gfx::ImageSkia SelectFaviconFrames(
204    const std::vector<SkBitmap>& bitmaps,
205    const std::vector<gfx::Size>& original_sizes,
206    const std::vector<ui::ScaleFactor>& scale_factors,
207    int desired_size,
208    float* match_score) {
209  std::vector<SelectionResult> results;
210  GetCandidateIndicesWithBestScores(original_sizes, scale_factors,
211      desired_size, match_score, &results);
212
213  gfx::ImageSkia multi_image;
214  for (size_t i = 0; i < results.size(); ++i) {
215    const SelectionResult& result = results[i];
216    SkBitmap resized_bitmap = GetResizedBitmap(bitmaps[result.index],
217        desired_size, result.scale_factor, result.resize_method);
218    multi_image.AddRepresentation(
219        gfx::ImageSkiaRep(resized_bitmap,
220                          ui::GetImageScale(result.scale_factor)));
221  }
222  return multi_image;
223}
224
225void SelectFaviconFrameIndices(
226    const std::vector<gfx::Size>& frame_pixel_sizes,
227    const std::vector<ui::ScaleFactor>& scale_factors,
228    int desired_size,
229    std::vector<size_t>* best_indices,
230    float* match_score) {
231  std::vector<SelectionResult> results;
232  GetCandidateIndicesWithBestScores(frame_pixel_sizes, scale_factors,
233      desired_size, match_score, &results);
234
235  std::set<size_t> already_added;
236  for (size_t i = 0; i < results.size(); ++i) {
237    size_t index = results[i].index;
238    // GetCandidateIndicesWithBestScores() will return duplicate indices if the
239    // bitmap data with |frame_pixel_sizes[index]| should be used for multiple
240    // scale factors. Remove duplicates here such that |best_indices| contains
241    // no duplicates.
242    if (already_added.find(index) == already_added.end()) {
243      already_added.insert(index);
244      best_indices->push_back(index);
245    }
246  }
247}
248