1 // Copyright 2014 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 "components/favicon_base/select_favicon_frames.h"
6
7 #include <algorithm>
8 #include <cmath>
9 #include <limits>
10 #include <map>
11 #include <memory>
12 #include <set>
13 #include <utility>
14
15 #include "base/macros.h"
16 #include "components/favicon_base/favicon_util.h"
17 #include "skia/ext/image_operations.h"
18 #include "third_party/skia/include/core/SkCanvas.h"
19 #include "ui/gfx/geometry/size.h"
20 #include "ui/gfx/image/image.h"
21 #include "ui/gfx/image/image_skia.h"
22 #include "ui/gfx/image/image_skia_source.h"
23
24 namespace {
25
BiggestCandidate(const std::vector<gfx::Size> & candidate_sizes)26 size_t BiggestCandidate(const std::vector<gfx::Size>& candidate_sizes) {
27 size_t max_index = 0;
28 int max_area = candidate_sizes[0].GetArea();
29 for (size_t i = 1; i < candidate_sizes.size(); ++i) {
30 int area = candidate_sizes[i].GetArea();
31 if (area > max_area) {
32 max_area = area;
33 max_index = i;
34 }
35 }
36 return max_index;
37 }
38
SampleNearestNeighbor(const SkBitmap & contents,int desired_size)39 SkBitmap SampleNearestNeighbor(const SkBitmap& contents, int desired_size) {
40 SkBitmap bitmap;
41 bitmap.allocN32Pixels(desired_size, desired_size);
42 if (!contents.isOpaque())
43 bitmap.eraseARGB(0, 0, 0, 0);
44
45 {
46 SkCanvas canvas(bitmap, SkSurfaceProps{});
47 canvas.drawBitmapRect(contents, SkRect::MakeIWH(desired_size, desired_size),
48 nullptr);
49 }
50
51 return bitmap;
52 }
53
GetCandidateIndexWithBestScore(const std::vector<gfx::Size> & candidate_sizes,int desired_size,float * score)54 size_t GetCandidateIndexWithBestScore(
55 const std::vector<gfx::Size>& candidate_sizes,
56 int desired_size,
57 float* score) {
58 DCHECK_NE(desired_size, 0);
59
60 // Try to find an exact match.
61 for (size_t i = 0; i < candidate_sizes.size(); ++i) {
62 if (candidate_sizes[i].width() == desired_size &&
63 candidate_sizes[i].height() == desired_size) {
64 *score = 1;
65 return i;
66 }
67 }
68
69 // Huge favicon bitmaps often have a completely different visual style from
70 // smaller favicon bitmaps. Avoid them.
71 const int kHugeEdgeSize = desired_size * 8;
72
73 // Order of preference:
74 // 1) Bitmaps with width and height smaller than |kHugeEdgeSize|.
75 // 2) Bitmaps which need to be scaled down instead of up.
76 // 3) Bitmaps which do not need to be scaled as much.
77 size_t candidate_index = std::numeric_limits<size_t>::max();
78 float candidate_score = 0;
79 for (size_t i = 0; i < candidate_sizes.size(); ++i) {
80 float average_edge =
81 (candidate_sizes[i].width() + candidate_sizes[i].height()) / 2.0f;
82
83 float score = 0;
84 if (candidate_sizes[i].width() >= kHugeEdgeSize ||
85 candidate_sizes[i].height() >= kHugeEdgeSize) {
86 score = std::min(1.0f, desired_size / average_edge) * 0.01f;
87 } else if (candidate_sizes[i].width() >= desired_size &&
88 candidate_sizes[i].height() >= desired_size) {
89 score = desired_size / average_edge * 0.01f + 0.15f;
90 } else {
91 score = std::min(1.0f, average_edge / desired_size) * 0.01f + 0.1f;
92 }
93
94 if (candidate_index == std::numeric_limits<size_t>::max() ||
95 score > candidate_score) {
96 candidate_index = i;
97 candidate_score = score;
98 }
99 }
100 *score = candidate_score;
101
102 return candidate_index;
103 }
104
105 // Represents the index of the best candidate for |desired_size| from the
106 // |candidate_sizes| passed into GetCandidateIndicesWithBestScores().
107 struct SelectionResult {
108 // index in |candidate_sizes| of the best candidate.
109 size_t index;
110
111 // The desired size for which |index| is the best candidate.
112 int desired_size;
113 };
114
GetCandidateIndicesWithBestScores(const std::vector<gfx::Size> & candidate_sizes,const std::vector<int> & desired_sizes,float * match_score,std::vector<SelectionResult> * results)115 void GetCandidateIndicesWithBestScores(
116 const std::vector<gfx::Size>& candidate_sizes,
117 const std::vector<int>& desired_sizes,
118 float* match_score,
119 std::vector<SelectionResult>* results) {
120 if (candidate_sizes.empty() || desired_sizes.empty()) {
121 if (match_score)
122 *match_score = 0.0f;
123 return;
124 }
125
126 if (base::Contains(desired_sizes, 0)) {
127 // Just return the biggest image available.
128 SelectionResult result;
129 result.index = BiggestCandidate(candidate_sizes);
130 result.desired_size = 0;
131 results->push_back(result);
132 if (match_score)
133 *match_score = 1.0f;
134 return;
135 }
136
137 float total_score = 0;
138 for (size_t i = 0; i < desired_sizes.size(); ++i) {
139 float score;
140 SelectionResult result;
141 result.desired_size = desired_sizes[i];
142 result.index = GetCandidateIndexWithBestScore(
143 candidate_sizes, result.desired_size, &score);
144 results->push_back(result);
145 total_score += score;
146 }
147
148 if (match_score)
149 *match_score = total_score / desired_sizes.size();
150 }
151
152 // Resize |source_bitmap|
GetResizedBitmap(const SkBitmap & source_bitmap,gfx::Size original_size,int desired_size_in_pixel)153 SkBitmap GetResizedBitmap(const SkBitmap& source_bitmap,
154 gfx::Size original_size,
155 int desired_size_in_pixel) {
156 if (desired_size_in_pixel == 0 ||
157 (original_size.width() == desired_size_in_pixel &&
158 original_size.height() == desired_size_in_pixel)) {
159 return source_bitmap;
160 }
161 if (desired_size_in_pixel % original_size.width() == 0 &&
162 desired_size_in_pixel % original_size.height() == 0) {
163 return SampleNearestNeighbor(source_bitmap, desired_size_in_pixel);
164 }
165 return skia::ImageOperations::Resize(source_bitmap,
166 skia::ImageOperations::RESIZE_LANCZOS3,
167 desired_size_in_pixel,
168 desired_size_in_pixel);
169 }
170
171 class FaviconImageSource : public gfx::ImageSkiaSource {
172 public:
FaviconImageSource()173 FaviconImageSource() {}
~FaviconImageSource()174 ~FaviconImageSource() override {}
175
176 // gfx::ImageSkiaSource:
GetImageForScale(float scale)177 gfx::ImageSkiaRep GetImageForScale(float scale) override {
178 const gfx::ImageSkiaRep* rep = nullptr;
179 // gfx::ImageSkia passes one of the resource scale factors. The source
180 // should return:
181 // 1) The ImageSkiaRep with the highest scale if all available
182 // scales are smaller than |scale|.
183 // 2) The ImageSkiaRep with the smallest one that is larger than |scale|.
184 // Note: Keep this logic consistent with the PNGImageSource in
185 // ui/gfx/image.cc.
186 // TODO(oshima): consolidate these logic into one place.
187 for (std::vector<gfx::ImageSkiaRep>::const_iterator iter =
188 image_skia_reps_.begin();
189 iter != image_skia_reps_.end(); ++iter) {
190 if ((*iter).scale() == scale)
191 return (*iter);
192 if (!rep || rep->scale() < (*iter).scale())
193 rep = &(*iter);
194 if (rep->scale() >= scale)
195 break;
196 }
197 DCHECK(rep);
198 return rep ? *rep : gfx::ImageSkiaRep();
199 }
200
AddImageSkiaRep(const gfx::ImageSkiaRep & rep)201 void AddImageSkiaRep(const gfx::ImageSkiaRep& rep) {
202 image_skia_reps_.push_back(rep);
203 }
204
205 private:
206 std::vector<gfx::ImageSkiaRep> image_skia_reps_;
207 DISALLOW_COPY_AND_ASSIGN(FaviconImageSource);
208 };
209
210 } // namespace
211
212 const float kSelectFaviconFramesInvalidScore = -1.0f;
213
CreateFaviconImageSkia(const std::vector<SkBitmap> & bitmaps,const std::vector<gfx::Size> & original_sizes,int desired_size_in_dip,float * score)214 gfx::ImageSkia CreateFaviconImageSkia(
215 const std::vector<SkBitmap>& bitmaps,
216 const std::vector<gfx::Size>& original_sizes,
217 int desired_size_in_dip,
218 float* score) {
219
220 const std::vector<float>& favicon_scales = favicon_base::GetFaviconScales();
221 std::vector<int> desired_sizes;
222
223 if (desired_size_in_dip == 0) {
224 desired_sizes.push_back(0);
225 } else {
226 for (auto iter = favicon_scales.begin(); iter != favicon_scales.end();
227 ++iter) {
228 desired_sizes.push_back(
229 static_cast<int>(ceil(desired_size_in_dip * (*iter))));
230 }
231 }
232
233 std::vector<SelectionResult> results;
234 GetCandidateIndicesWithBestScores(original_sizes,
235 desired_sizes,
236 score,
237 &results);
238 if (results.size() == 0)
239 return gfx::ImageSkia();
240
241 if (desired_size_in_dip == 0) {
242 size_t index = results[0].index;
243 return gfx::ImageSkia(gfx::ImageSkiaRep(bitmaps[index], 1.0f));
244 }
245
246 auto image_source = std::make_unique<FaviconImageSource>();
247
248 for (size_t i = 0; i < results.size(); ++i) {
249 size_t index = results[i].index;
250 image_source->AddImageSkiaRep(
251 gfx::ImageSkiaRep(GetResizedBitmap(bitmaps[index],
252 original_sizes[index],
253 desired_sizes[i]),
254 favicon_scales[i]));
255 }
256 return gfx::ImageSkia(std::move(image_source),
257 gfx::Size(desired_size_in_dip, desired_size_in_dip));
258 }
259
SelectFaviconFrameIndices(const std::vector<gfx::Size> & frame_pixel_sizes,const std::vector<int> & desired_sizes,std::vector<size_t> * best_indices,float * match_score)260 void SelectFaviconFrameIndices(const std::vector<gfx::Size>& frame_pixel_sizes,
261 const std::vector<int>& desired_sizes,
262 std::vector<size_t>* best_indices,
263 float* match_score) {
264 std::vector<SelectionResult> results;
265 GetCandidateIndicesWithBestScores(
266 frame_pixel_sizes, desired_sizes, match_score, &results);
267
268 if (!best_indices)
269 return;
270
271 std::set<size_t> already_added;
272 for (size_t i = 0; i < results.size(); ++i) {
273 size_t index = results[i].index;
274 // GetCandidateIndicesWithBestScores() will return duplicate indices if the
275 // bitmap data with |frame_pixel_sizes[index]| should be used for multiple
276 // scale factors. Remove duplicates here such that |best_indices| contains
277 // no duplicates.
278 if (already_added.find(index) == already_added.end()) {
279 already_added.insert(index);
280 best_indices->push_back(index);
281 }
282 }
283 }
284