Improve FontSelectionAlgorithm, including moving from IntegerHasher to Hasher
[WebKit-https.git] / Source / WebCore / platform / graphics / FontSelectionAlgorithm.h
1 /*
2  * Copyright (C) 2017 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #pragma once
27
28 #include "TextFlags.h"
29 #include <algorithm>
30 #include <tuple>
31 #include <wtf/Hasher.h>
32 #include <wtf/Optional.h>
33
34 namespace WebCore {
35
36 // Unclamped, unchecked, signed fixed-point number representing a value used for font variations.
37 // Sixteen bits in total, one sign bit, two fractional bits, smallest positive value is 0.25,
38 // maximum value is 8191.75, and minimum value is -8192.
39 class FontSelectionValue {
40 public:
41     using BackingType = int16_t;
42
43     FontSelectionValue() = default;
44
45     // Explicit because it won't work correctly for values outside the representable range.
46     explicit constexpr FontSelectionValue(int);
47
48     // Explicit because it won't work correctly for values outside the representable range and because precision can be lost.
49     explicit constexpr FontSelectionValue(float);
50
51     // Precision can be lost, but value will be clamped to the representable range.
52     static constexpr FontSelectionValue clampFloat(float);
53
54     // Since floats have 23 mantissa bits, every value can be represented losslessly.
55     constexpr operator float() const;
56
57     static constexpr FontSelectionValue maximumValue();
58     static constexpr FontSelectionValue minimumValue();
59
60     friend constexpr FontSelectionValue operator+(FontSelectionValue, FontSelectionValue);
61     friend constexpr FontSelectionValue operator-(FontSelectionValue, FontSelectionValue);
62     friend constexpr FontSelectionValue operator*(FontSelectionValue, FontSelectionValue);
63     friend constexpr FontSelectionValue operator/(FontSelectionValue, FontSelectionValue);
64     friend constexpr FontSelectionValue operator-(FontSelectionValue);
65
66     constexpr BackingType rawValue() const { return m_backing; }
67
68 private:
69     enum class RawTag { RawTag };
70     constexpr FontSelectionValue(int, RawTag);
71
72     static constexpr int fractionalEntropy = 4;
73     BackingType m_backing { 0 };
74 };
75
76 constexpr FontSelectionValue::FontSelectionValue(int x)
77     : m_backing(x * fractionalEntropy)
78 {
79     // FIXME: Should we assert the passed in value was in range?
80 }
81
82 constexpr FontSelectionValue::FontSelectionValue(float x)
83     : m_backing(x * fractionalEntropy)
84 {
85     // FIXME: Should we assert the passed in value was in range?
86 }
87
88 constexpr FontSelectionValue::operator float() const
89 {
90     return m_backing / static_cast<float>(fractionalEntropy);
91 }
92
93 constexpr FontSelectionValue FontSelectionValue::maximumValue()
94 {
95     return { std::numeric_limits<BackingType>::max(), RawTag::RawTag };
96 }
97
98 constexpr FontSelectionValue FontSelectionValue::minimumValue()
99 {
100     return { std::numeric_limits<BackingType>::min(), RawTag::RawTag };
101 }
102
103 constexpr FontSelectionValue FontSelectionValue::clampFloat(float value)
104 {
105     return FontSelectionValue { std::max<float>(minimumValue(), std::min<float>(value, maximumValue())) };
106 }
107
108 constexpr FontSelectionValue::FontSelectionValue(int rawValue, RawTag)
109     : m_backing(rawValue)
110 {
111 }
112
113 constexpr FontSelectionValue operator+(FontSelectionValue a, FontSelectionValue b)
114 {
115     return { a.m_backing + b.m_backing, FontSelectionValue::RawTag::RawTag };
116 }
117
118 constexpr FontSelectionValue operator-(FontSelectionValue a, FontSelectionValue b)
119 {
120     return { a.m_backing - b.m_backing, FontSelectionValue::RawTag::RawTag };
121 }
122
123 constexpr FontSelectionValue operator*(FontSelectionValue a, FontSelectionValue b)
124 {
125     return { a.m_backing * b.m_backing / FontSelectionValue::fractionalEntropy, FontSelectionValue::RawTag::RawTag };
126 }
127
128 constexpr FontSelectionValue operator/(FontSelectionValue a, FontSelectionValue b)
129 {
130     return { a.m_backing * FontSelectionValue::fractionalEntropy / b.m_backing, FontSelectionValue::RawTag::RawTag };
131 }
132
133 constexpr FontSelectionValue operator-(FontSelectionValue value)
134 {
135     return { -value.m_backing, FontSelectionValue::RawTag::RawTag };
136 }
137
138 constexpr bool operator==(FontSelectionValue a, FontSelectionValue b)
139 {
140     return a.rawValue() == b.rawValue();
141 }
142
143 constexpr bool operator!=(FontSelectionValue a, FontSelectionValue b)
144 {
145     return a.rawValue() != b.rawValue();
146 }
147
148 constexpr bool operator<(FontSelectionValue a, FontSelectionValue b)
149 {
150     return a.rawValue() < b.rawValue();
151 }
152
153 constexpr bool operator<=(FontSelectionValue a, FontSelectionValue b)
154 {
155     return a.rawValue() <= b.rawValue();
156 }
157
158 constexpr bool operator>(FontSelectionValue a, FontSelectionValue b)
159 {
160     return a.rawValue() > b.rawValue();
161 }
162
163 constexpr bool operator>=(FontSelectionValue a, FontSelectionValue b)
164 {
165     return a.rawValue() >= b.rawValue();
166 }
167
168 constexpr FontSelectionValue italicThreshold()
169 {
170     return FontSelectionValue { 20 };
171 }
172
173 constexpr bool isItalic(FontSelectionValue fontWeight)
174 {
175     return fontWeight >= italicThreshold();
176 }
177
178 constexpr FontSelectionValue normalItalicValue()
179 {
180     return FontSelectionValue { 0 };
181 }
182
183 constexpr FontSelectionValue italicValue()
184 {
185     return FontSelectionValue { 20 };
186 }
187
188 constexpr FontSelectionValue boldThreshold()
189 {
190     return FontSelectionValue { 600 };
191 }
192
193 constexpr FontSelectionValue boldWeightValue()
194 {
195     return FontSelectionValue { 700 };
196 }
197
198 constexpr FontSelectionValue normalWeightValue()
199 {
200     return FontSelectionValue { 400 };
201 }
202
203 constexpr FontSelectionValue lightWeightValue()
204 {
205     return FontSelectionValue { 200 };
206 }
207
208 constexpr bool isFontWeightBold(FontSelectionValue fontWeight)
209 {
210     return fontWeight >= boldThreshold();
211 }
212
213 constexpr FontSelectionValue lowerWeightSearchThreshold()
214 {
215     return FontSelectionValue { 400 };
216 }
217
218 constexpr FontSelectionValue upperWeightSearchThreshold()
219 {
220     return FontSelectionValue { 500 };
221 }
222
223 constexpr FontSelectionValue ultraCondensedStretchValue()
224 {
225     return FontSelectionValue { 50 };
226 }
227
228 constexpr FontSelectionValue extraCondensedStretchValue()
229 {
230     return FontSelectionValue { 62.5f };
231 }
232
233 constexpr FontSelectionValue condensedStretchValue()
234 {
235     return FontSelectionValue { 75 };
236 }
237
238 constexpr FontSelectionValue semiCondensedStretchValue()
239 {
240     return FontSelectionValue { 87.5f };
241 }
242
243 constexpr FontSelectionValue normalStretchValue()
244 {
245     return FontSelectionValue { 100 };
246 }
247
248 constexpr FontSelectionValue semiExpandedStretchValue()
249 {
250     return FontSelectionValue { 112.5f };
251 }
252
253 constexpr FontSelectionValue expandedStretchValue()
254 {
255     return FontSelectionValue { 125 };
256 }
257
258 constexpr FontSelectionValue extraExpandedStretchValue()
259 {
260     return FontSelectionValue { 150 };
261 }
262
263 constexpr FontSelectionValue ultraExpandedStretchValue()
264 {
265     return FontSelectionValue { 200 };
266 }
267
268 // [Inclusive, Inclusive]
269 struct FontSelectionRange {
270     using Value = FontSelectionValue;
271
272     constexpr FontSelectionRange(Value minimum, Value maximum)
273         : minimum(minimum)
274         , maximum(maximum)
275     {
276     }
277
278     explicit constexpr FontSelectionRange(Value value)
279         : minimum(value)
280         , maximum(value)
281     {
282     }
283
284     constexpr bool operator==(const FontSelectionRange& other) const
285     {
286         return std::tie(minimum, maximum) == std::tie(other.minimum, other.maximum);
287     }
288
289     constexpr bool isValid() const
290     {
291         return minimum <= maximum;
292     }
293
294     void expand(const FontSelectionRange& other)
295     {
296         ASSERT(other.isValid());
297         if (!isValid())
298             *this = other;
299         else {
300             minimum = std::min(minimum, other.minimum);
301             maximum = std::max(maximum, other.maximum);
302         }
303         ASSERT(isValid());
304     }
305
306     constexpr bool includes(Value target) const
307     {
308         return target >= minimum && target <= maximum;
309     }
310
311     // FIXME: This name is not so great. Move this into the add function below
312     // once we move FontPlatformDataCacheKeyHash from IntegerHasher to Hasher,
313     // and then it doesn't need to have a name.
314     constexpr uint32_t uniqueValue() const
315     {
316         return minimum.rawValue() << 16 | maximum.rawValue();
317     }
318
319     Value minimum { 1 };
320     Value maximum { 0 };
321 };
322
323 inline void add(Hasher& hasher, const FontSelectionRange& range)
324 {
325     add(hasher, range.uniqueValue());
326 }
327
328 struct FontSelectionRequest {
329     using Value = FontSelectionValue;
330
331     Value weight;
332     Value width;
333     Value slope;
334
335     constexpr std::tuple<Value, Value, Value> tied() const
336     {
337         return std::tie(weight, width, slope);
338     }
339
340 #if !COMPILER_SUPPORTS(NSDMI_FOR_AGGREGATES)
341     FontSelectionRequest() = default;
342
343     constexpr FontSelectionRequest(Value weight, Value width, Value slope)
344         : weight(weight)
345         , width(width)
346         , slope(slope)
347     {
348     }
349 #endif
350 };
351
352 constexpr bool operator==(const FontSelectionRequest& a, const FontSelectionRequest& b)
353 {
354     return a.tied() == b.tied();
355 }
356
357 constexpr bool operator!=(const FontSelectionRequest& a, const FontSelectionRequest& b)
358 {
359     return !(a == b);
360 }
361
362 inline void add(Hasher& hasher, const FontSelectionRequest& request)
363 {
364     add(hasher, request.tied());
365 }
366
367 struct FontSelectionCapabilities {
368     using Range = FontSelectionRange;
369
370     FontSelectionCapabilities& operator=(const FontSelectionCapabilities&) = default;
371
372     constexpr std::tuple<Range, Range, Range> tied() const
373     {
374         return std::tie(weight, width, slope);
375     }
376
377     void expand(const FontSelectionCapabilities& capabilities)
378     {
379         weight.expand(capabilities.weight);
380         width.expand(capabilities.width);
381         slope.expand(capabilities.slope);
382     }
383
384     Range weight { normalWeightValue() };
385     Range width { normalStretchValue() };
386     Range slope { normalItalicValue() };
387
388 #if !COMPILER_SUPPORTS(NSDMI_FOR_AGGREGATES)
389     FontSelectionCapabilities() = default;
390
391     constexpr FontSelectionCapabilities(Range weight, Range width, Range slope)
392         : weight(weight)
393         , width(width)
394         , slope(slope)
395     {
396     }
397 #endif
398 };
399
400 constexpr bool operator==(const FontSelectionCapabilities& a, const FontSelectionCapabilities& b)
401 {
402     return a.tied() == b.tied();
403 }
404
405 constexpr bool operator!=(const FontSelectionCapabilities& a, const FontSelectionCapabilities& b)
406 {
407     return !(a == b);
408 }
409
410 struct FontSelectionSpecifiedCapabilities {
411     using Capabilities = FontSelectionCapabilities;
412     using Range = FontSelectionRange;
413     using OptionalRange = std::optional<Range>;
414
415     constexpr Capabilities computeFontSelectionCapabilities() const
416     {
417         return { computeWeight(), computeWidth(), computeSlope() };
418     }
419
420     constexpr std::tuple<OptionalRange&, OptionalRange&, OptionalRange&> tied()
421     {
422         return std::tie(weight, width, slope);
423     }
424
425     constexpr std::tuple<const OptionalRange&, const OptionalRange&, const OptionalRange&> tied() const
426     {
427         return std::tie(weight, width, slope);
428     }
429
430     FontSelectionSpecifiedCapabilities& operator=(const Capabilities& other)
431     {
432         tied() = other.tied();
433         return *this;
434     }
435
436     constexpr Range computeWeight() const
437     {
438         return weight.value_or(Range { normalWeightValue() });
439     }
440
441     constexpr Range computeWidth() const
442     {
443         return width.value_or(Range { normalStretchValue() });
444     }
445
446     constexpr Range computeSlope() const
447     {
448         return slope.value_or(Range { normalItalicValue() });
449     }
450
451     OptionalRange weight;
452     OptionalRange width;
453     OptionalRange slope;
454 };
455
456 constexpr bool operator==(const FontSelectionSpecifiedCapabilities& a, const FontSelectionSpecifiedCapabilities& b)
457 {
458     return a.tied() == b.tied();
459 }
460
461 constexpr bool operator!=(const FontSelectionSpecifiedCapabilities& a, const FontSelectionSpecifiedCapabilities& b)
462 {
463     return !(a == b);
464 }
465
466 class FontSelectionAlgorithm {
467 public:
468     using Capabilities = FontSelectionCapabilities;
469
470     FontSelectionAlgorithm() = delete;
471     FontSelectionAlgorithm(FontSelectionRequest, const Vector<Capabilities>&, std::optional<Capabilities> capabilitiesBounds = std::nullopt);
472
473     struct DistanceResult {
474         FontSelectionValue distance;
475         FontSelectionValue value;
476     };
477     DistanceResult stretchDistance(Capabilities) const;
478     DistanceResult styleDistance(Capabilities) const;
479     DistanceResult weightDistance(Capabilities) const;
480
481     size_t indexOfBestCapabilities();
482
483 private:
484     using DistanceFunction = DistanceResult (FontSelectionAlgorithm::*)(Capabilities) const;
485     using CapabilitiesRange = FontSelectionRange Capabilities::*;
486     FontSelectionValue bestValue(const bool eliminated[], DistanceFunction) const;
487     void filterCapability(bool eliminated[], DistanceFunction, CapabilitiesRange);
488
489     FontSelectionRequest m_request;
490     Capabilities m_capabilitiesBounds;
491     const Vector<Capabilities>& m_capabilities;
492 };
493
494 }