Improve FontSelectionAlgorithm, including moving from IntegerHasher to Hasher
[WebKit-https.git] / Source / WebCore / platform / graphics / FontSelectionAlgorithm.cpp
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 #include "config.h"
27 #include "FontSelectionAlgorithm.h"
28
29 namespace WebCore {
30
31 FontSelectionAlgorithm::FontSelectionAlgorithm(FontSelectionRequest request, const Vector<Capabilities>& capabilities, std::optional<Capabilities> bounds)
32     : m_request(request)
33     , m_capabilities(capabilities)
34 {
35     ASSERT(!m_capabilities.isEmpty());
36     if (bounds)
37         m_capabilitiesBounds = bounds.value();
38     else {
39         for (auto& capabilities : m_capabilities)
40             m_capabilitiesBounds.expand(capabilities);
41     }
42 }
43
44 auto FontSelectionAlgorithm::stretchDistance(Capabilities capabilities) const -> DistanceResult
45 {
46     auto width = capabilities.width;
47     ASSERT(width.isValid());
48     if (width.includes(m_request.width))
49         return { FontSelectionValue(), m_request.width };
50
51     if (m_request.width > normalStretchValue()) {
52         if (width.minimum > m_request.width)
53             return { width.minimum - m_request.width, width.minimum };
54         ASSERT(width.maximum < m_request.width);
55         auto threshold = std::max(m_request.width, m_capabilitiesBounds.width.maximum);
56         return { threshold - width.maximum, width.maximum };
57     }
58
59     if (width.maximum < m_request.width)
60         return { m_request.width - width.maximum, width.maximum };
61     ASSERT(width.minimum > m_request.width);
62     auto threshold = std::min(m_request.width, m_capabilitiesBounds.width.minimum);
63     return { width.minimum - threshold, width.minimum };
64 }
65
66 auto FontSelectionAlgorithm::styleDistance(Capabilities capabilities) const -> DistanceResult
67 {
68     auto slope = capabilities.slope;
69     ASSERT(slope.isValid());
70     if (slope.includes(m_request.slope))
71         return { FontSelectionValue(), m_request.slope };
72
73     if (m_request.slope >= italicThreshold()) {
74         if (slope.minimum > m_request.slope)
75             return { slope.minimum - m_request.slope, slope.minimum };
76         ASSERT(m_request.slope > slope.maximum);
77         auto threshold = std::max(m_request.slope, m_capabilitiesBounds.slope.maximum);
78         return { threshold - slope.maximum, slope.maximum };
79     }
80
81     if (m_request.slope >= FontSelectionValue()) {
82         if (slope.maximum >= FontSelectionValue() && slope.maximum < m_request.slope)
83             return { m_request.slope - slope.maximum, slope.maximum };
84         if (slope.minimum > m_request.slope)
85             return { slope.minimum, slope.minimum };
86         ASSERT(slope.maximum < FontSelectionValue());
87         auto threshold = std::max(m_request.slope, m_capabilitiesBounds.slope.maximum);
88         return { threshold - slope.maximum, slope.maximum };
89     }
90
91     if (m_request.slope > -italicThreshold()) {
92         if (slope.minimum > m_request.slope && slope.minimum <= FontSelectionValue())
93             return { slope.minimum - m_request.slope, slope.minimum };
94         if (slope.maximum < m_request.slope)
95             return { -slope.maximum, slope.maximum };
96         ASSERT(slope.minimum > FontSelectionValue());
97         auto threshold = std::min(m_request.slope, m_capabilitiesBounds.slope.minimum);
98         return { slope.minimum - threshold, slope.minimum };
99     }
100
101     if (slope.maximum < m_request.slope)
102         return { m_request.slope - slope.maximum, slope.maximum };
103     ASSERT(slope.minimum > m_request.slope);
104     auto threshold = std::min(m_request.slope, m_capabilitiesBounds.slope.minimum);
105     return { slope.minimum - threshold, slope.minimum };
106 }
107
108 auto FontSelectionAlgorithm::weightDistance(Capabilities capabilities) const -> DistanceResult
109 {
110     auto weight = capabilities.weight;
111     ASSERT(weight.isValid());
112     if (weight.includes(m_request.weight))
113         return { FontSelectionValue(), m_request.weight };
114
115     if (m_request.weight >= lowerWeightSearchThreshold() && m_request.weight <= upperWeightSearchThreshold()) {
116         if (weight.minimum > m_request.weight && weight.minimum <= upperWeightSearchThreshold())
117             return { weight.minimum - m_request.weight, weight.minimum };
118         if (weight.maximum < m_request.weight)
119             return { upperWeightSearchThreshold() - weight.maximum, weight.maximum };
120         ASSERT(weight.minimum > upperWeightSearchThreshold());
121         auto threshold = std::min(m_request.weight, m_capabilitiesBounds.weight.minimum);
122         return { weight.minimum - threshold, weight.minimum };
123     }
124     if (m_request.weight < lowerWeightSearchThreshold()) {
125         if (weight.maximum < m_request.weight)
126             return { m_request.weight - weight.maximum, weight.maximum };
127         ASSERT(weight.minimum > m_request.weight);
128         auto threshold = std::min(m_request.weight, m_capabilitiesBounds.weight.minimum);
129         return { weight.minimum - threshold, weight.minimum };
130     }
131     ASSERT(m_request.weight >= upperWeightSearchThreshold());
132     if (weight.minimum > m_request.weight)
133         return { weight.minimum - m_request.weight, weight.minimum };
134     ASSERT(weight.maximum < m_request.weight);
135     auto threshold = std::max(m_request.weight, m_capabilitiesBounds.weight.maximum);
136     return { threshold - weight.maximum, weight.maximum };
137 }
138
139 FontSelectionValue FontSelectionAlgorithm::bestValue(const bool eliminated[], DistanceFunction computeDistance) const
140 {
141     std::optional<DistanceResult> smallestDistance;
142     for (size_t i = 0, size = m_capabilities.size(); i < size; ++i) {
143         if (eliminated[i])
144             continue;
145         auto distanceResult = (this->*computeDistance)(m_capabilities[i]);
146         if (!smallestDistance || distanceResult.distance < smallestDistance.value().distance)
147             smallestDistance = distanceResult;
148     }
149     return smallestDistance.value().value;
150 }
151
152 void FontSelectionAlgorithm::filterCapability(bool eliminated[], DistanceFunction computeDistance, CapabilitiesRange inclusionRange)
153 {
154     auto value = bestValue(eliminated, computeDistance);
155     for (size_t i = 0, size = m_capabilities.size(); i < size; ++i) {
156         eliminated[i] = eliminated[i]
157             || !(m_capabilities[i].*inclusionRange).includes(value);
158     }
159 }
160
161 size_t FontSelectionAlgorithm::indexOfBestCapabilities()
162 {
163     Vector<bool, 256> eliminated(m_capabilities.size(), false);
164     filterCapability(eliminated.data(), &FontSelectionAlgorithm::stretchDistance, &Capabilities::width);
165     filterCapability(eliminated.data(), &FontSelectionAlgorithm::styleDistance, &Capabilities::slope);
166     filterCapability(eliminated.data(), &FontSelectionAlgorithm::weightDistance, &Capabilities::weight);
167     return eliminated.find(false);
168 }
169
170 }