Extended Color: ColorMatrix should support smaller matrices and be constexpr
[WebKit-https.git] / Source / WebCore / platform / graphics / filters / FEMorphology.cpp
1 /*
2  * Copyright (C) 2004, 2005, 2006, 2007 Nikolas Zimmermann <zimmermann@kde.org>
3  * Copyright (C) 2004, 2005 Rob Buis <buis@kde.org>
4  * Copyright (C) 2005 Eric Seidel <eric@webkit.org>
5  * Copyright (C) 2009 Dirk Schulze <krit@webkit.org>
6  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
7  * Copyright (C) Apple Inc. 2017-2018 All rights reserved.
8  *
9  * This library is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU Library General Public
11  * License as published by the Free Software Foundation; either
12  * version 2 of the License, or (at your option) any later version.
13  *
14  * This library is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17  * Library General Public License for more details.
18  *
19  * You should have received a copy of the GNU Library General Public License
20  * along with this library; see the file COPYING.LIB.  If not, write to
21  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
22  * Boston, MA 02110-1301, USA.
23  */
24
25 #include "config.h"
26 #include "FEMorphology.h"
27
28 #include "ColorComponents.h"
29 #include "ColorUtilities.h"
30 #include "Filter.h"
31 #include "ImageData.h"
32 #include <wtf/ParallelJobs.h>
33 #include <wtf/Vector.h>
34 #include <wtf/text/TextStream.h>
35
36 namespace WebCore {
37
38 FEMorphology::FEMorphology(Filter& filter, MorphologyOperatorType type, float radiusX, float radiusY)
39     : FilterEffect(filter)
40     , m_type(type)
41     , m_radiusX(radiusX)
42     , m_radiusY(radiusY)
43 {
44 }
45
46 Ref<FEMorphology> FEMorphology::create(Filter& filter, MorphologyOperatorType type, float radiusX, float radiusY)
47 {
48     return adoptRef(*new FEMorphology(filter, type, radiusX, radiusY));
49 }
50
51 bool FEMorphology::setMorphologyOperator(MorphologyOperatorType type)
52 {
53     if (m_type == type)
54         return false;
55     m_type = type;
56     return true;
57 }
58
59 bool FEMorphology::setRadiusX(float radiusX)
60 {
61     if (m_radiusX == radiusX)
62         return false;
63     m_radiusX = radiusX;
64     return true;
65 }
66
67 bool FEMorphology::setRadiusY(float radiusY)
68 {
69     if (m_radiusY == radiusY)
70         return false;
71     m_radiusY = radiusY;
72     return true;
73 }
74
75 void FEMorphology::determineAbsolutePaintRect()
76 {
77     FloatRect paintRect = inputEffect(0)->absolutePaintRect();
78     Filter& filter = this->filter();
79     paintRect.inflate(filter.scaledByFilterResolution({ m_radiusX, m_radiusY }));
80     if (clipsToBounds())
81         paintRect.intersect(maxEffectRect());
82     else
83         paintRect.unite(maxEffectRect());
84     setAbsolutePaintRect(enclosingIntRect(paintRect));
85 }
86
87 static inline int pixelArrayIndex(int x, int y, int width)
88 {
89     return (y * width + x) * 4;
90 }
91
92 inline ColorComponents<uint8_t> makeColorComponentsfromPixelValue(unsigned pixel)
93 {
94     return ColorComponents<uint8_t>((pixel >> 24) & 0xFF, (pixel >> 16) & 0xFF, (pixel >> 8) & 0xFF, pixel & 0xFF);
95 }
96
97 inline unsigned makePixelValueFromColorComponents(const ColorComponents<uint8_t>& components)
98 {
99     auto [r, g, b, a] = components;
100     return r << 24 | g << 16 | b << 8 | a;
101 }
102
103 template<MorphologyOperatorType type>
104 ALWAYS_INLINE ColorComponents<uint8_t> minOrMax(const ColorComponents<uint8_t>& a, const ColorComponents<uint8_t>& b)
105 {
106     if (type == FEMORPHOLOGY_OPERATOR_ERODE)
107         return perComponentMin(a, b);
108
109     return perComponentMax(a, b);
110 }
111
112 template<MorphologyOperatorType type>
113 ALWAYS_INLINE ColorComponents<uint8_t> columnExtremum(const Uint8ClampedArray& srcPixelArray, int x, int yStart, int yEnd, int width)
114 {
115     auto extremum = makeColorComponentsfromPixelValue(*reinterpret_cast<const unsigned*>(srcPixelArray.data() + pixelArrayIndex(x, yStart, width)));
116
117     for (int y = yStart + 1; y < yEnd; ++y) {
118         auto pixel = makeColorComponentsfromPixelValue(*reinterpret_cast<const unsigned*>(srcPixelArray.data() + pixelArrayIndex(x, y, width)));
119         extremum = minOrMax<type>(extremum, pixel);
120     }
121     return extremum;
122 }
123
124 ALWAYS_INLINE ColorComponents<uint8_t> columnExtremum(const Uint8ClampedArray& srcPixelArray, int x, int yStart, int yEnd, int width, MorphologyOperatorType type)
125 {
126     if (type == FEMORPHOLOGY_OPERATOR_ERODE)
127         return columnExtremum<FEMORPHOLOGY_OPERATOR_ERODE>(srcPixelArray, x, yStart, yEnd, width);
128
129     return columnExtremum<FEMORPHOLOGY_OPERATOR_DILATE>(srcPixelArray, x, yStart, yEnd, width);
130 }
131
132 using ColumnExtrema = Vector<ColorComponents<uint8_t>, 16>;
133
134 template<MorphologyOperatorType type>
135 ALWAYS_INLINE ColorComponents<uint8_t> kernelExtremum(const ColumnExtrema& kernel)
136 {
137     auto extremum = kernel[0];
138     for (size_t i = 1; i < kernel.size(); ++i)
139         extremum = minOrMax<type>(extremum, kernel[i]);
140
141     return extremum;
142 }
143
144 ALWAYS_INLINE ColorComponents<uint8_t> kernelExtremum(const ColumnExtrema& kernel, MorphologyOperatorType type)
145 {
146     if (type == FEMORPHOLOGY_OPERATOR_ERODE)
147         return kernelExtremum<FEMORPHOLOGY_OPERATOR_ERODE>(kernel);
148
149     return kernelExtremum<FEMORPHOLOGY_OPERATOR_DILATE>(kernel);
150 }
151
152 void FEMorphology::platformApplyGeneric(const PaintingData& paintingData, int startY, int endY)
153 {
154     ASSERT(endY > startY);
155
156     const auto& srcPixelArray = *paintingData.srcPixelArray;
157     auto& dstPixelArray = *paintingData.dstPixelArray;
158
159     const int radiusX = paintingData.radiusX;
160     const int radiusY = paintingData.radiusY;
161     const int width = paintingData.width;
162     const int height = paintingData.height;
163
164     ASSERT(radiusX <= width || radiusY <= height);
165     ASSERT(startY >= 0 && endY <= height && startY < endY);
166
167     ColumnExtrema extrema;
168     extrema.reserveInitialCapacity(2 * radiusX + 1);
169
170     for (int y = startY; y < endY; ++y) {
171         int yRadiusStart = std::max(0, y - radiusY);
172         int yRadiusEnd = std::min(height, y + radiusY + 1);
173
174         extrema.shrink(0);
175
176         // We start at the left edge, so compute extreme for the radiusX columns.
177         for (int x = 0; x < radiusX; ++x)
178             extrema.append(columnExtremum(srcPixelArray, x, yRadiusStart, yRadiusEnd, width, m_type));
179
180         // Kernel is filled, get extrema of next column
181         for (int x = 0; x < width; ++x) {
182             if (x < width - radiusX)
183                 extrema.append(columnExtremum(srcPixelArray, x + radiusX, yRadiusStart, yRadiusEnd, width, m_type));
184
185             if (x > radiusX)
186                 extrema.remove(0);
187
188             unsigned* destPixel = reinterpret_cast<unsigned*>(dstPixelArray.data() + pixelArrayIndex(x, y, width));
189             *destPixel = makePixelValueFromColorComponents(kernelExtremum(extrema, m_type));
190         }
191     }
192 }
193
194 void FEMorphology::platformApplyWorker(PlatformApplyParameters* param)
195 {
196     param->filter->platformApplyGeneric(*param->paintingData, param->startY, param->endY);
197 }
198
199 void FEMorphology::platformApply(const PaintingData& paintingData)
200 {
201     // Empirically, runtime is approximately linear over reasonable kernel sizes with a slope of about 0.65.
202     float kernelFactor = sqrt(paintingData.radiusX * paintingData.radiusY) * 0.65;
203
204     static const int minimalArea = (160 * 160); // Empirical data limit for parallel jobs
205     
206     unsigned maxNumThreads = paintingData.height / 8;
207     unsigned optimalThreadNumber = std::min<unsigned>((paintingData.width * paintingData.height * kernelFactor) / minimalArea, maxNumThreads);
208     if (optimalThreadNumber > 1) {
209         WTF::ParallelJobs<PlatformApplyParameters> parallelJobs(&WebCore::FEMorphology::platformApplyWorker, optimalThreadNumber);
210         auto numOfThreads = parallelJobs.numberOfJobs();
211         if (numOfThreads > 1) {
212             // Split the job into "jobSize"-sized jobs but there a few jobs that need to be slightly larger since
213             // jobSize * jobs < total size. These extras are handled by the remainder "jobsWithExtra".
214             int jobSize = paintingData.height / numOfThreads;
215             int jobsWithExtra = paintingData.height % numOfThreads;
216             int currentY = 0;
217             for (int job = numOfThreads - 1; job >= 0; --job) {
218                 PlatformApplyParameters& param = parallelJobs.parameter(job);
219                 param.filter = this;
220                 param.startY = currentY;
221                 currentY += job < jobsWithExtra ? jobSize + 1 : jobSize;
222                 param.endY = currentY;
223                 param.paintingData = &paintingData;
224             }
225             parallelJobs.execute();
226             return;
227         }
228         // Fallback to single thread model
229     }
230
231     platformApplyGeneric(paintingData, 0, paintingData.height);
232 }
233
234 bool FEMorphology::platformApplyDegenerate(Uint8ClampedArray& dstPixelArray, const IntRect& imageRect, int radiusX, int radiusY)
235 {
236     if (radiusX < 0 || radiusY < 0 || (!radiusX && !radiusY)) {
237         FilterEffect* in = inputEffect(0);
238         in->copyPremultipliedResult(dstPixelArray, imageRect);
239         return true;
240     }
241
242     return false;
243 }
244
245 void FEMorphology::platformApplySoftware()
246 {
247     FilterEffect* in = inputEffect(0);
248
249     auto* resultImage = createPremultipliedImageResult();
250     auto* dstPixelArray = resultImage ? resultImage->data() : nullptr;
251     if (!dstPixelArray)
252         return;
253
254     setIsAlphaImage(in->isAlphaImage());
255
256     IntRect effectDrawingRect = requestedRegionOfInputImageData(in->absolutePaintRect());
257
258     IntSize radius = flooredIntSize(FloatSize(m_radiusX, m_radiusY));
259     if (platformApplyDegenerate(*dstPixelArray, effectDrawingRect, radius.width(), radius.height()))
260         return;
261
262     Filter& filter = this->filter();
263     auto srcPixelArray = in->premultipliedResult(effectDrawingRect);
264     if (!srcPixelArray)
265         return;
266
267     radius = flooredIntSize(filter.scaledByFilterResolution({ m_radiusX, m_radiusY }));
268     int radiusX = std::min(effectDrawingRect.width() - 1, radius.width());
269     int radiusY = std::min(effectDrawingRect.height() - 1, radius.height());
270
271     if (platformApplyDegenerate(*dstPixelArray, effectDrawingRect, radiusX, radiusY))
272         return;
273     
274     PaintingData paintingData;
275     paintingData.srcPixelArray = srcPixelArray.get();
276     paintingData.dstPixelArray = dstPixelArray;
277     paintingData.width = ceilf(effectDrawingRect.width() * filter.filterScale());
278     paintingData.height = ceilf(effectDrawingRect.height() * filter.filterScale());
279     paintingData.radiusX = ceilf(radiusX * filter.filterScale());
280     paintingData.radiusY = ceilf(radiusY * filter.filterScale());
281
282     platformApply(paintingData);
283 }
284
285 static TextStream& operator<<(TextStream& ts, const MorphologyOperatorType& type)
286 {
287     switch (type) {
288     case FEMORPHOLOGY_OPERATOR_UNKNOWN:
289         ts << "UNKNOWN";
290         break;
291     case FEMORPHOLOGY_OPERATOR_ERODE:
292         ts << "ERODE";
293         break;
294     case FEMORPHOLOGY_OPERATOR_DILATE:
295         ts << "DILATE";
296         break;
297     }
298     return ts;
299 }
300
301 TextStream& FEMorphology::externalRepresentation(TextStream& ts, RepresentationType representation) const
302 {
303     ts << indent << "[feMorphology";
304     FilterEffect::externalRepresentation(ts, representation);
305     ts << " operator=\"" << morphologyOperator() << "\" "
306        << "radius=\"" << radiusX() << ", " << radiusY() << "\"]\n";
307
308     TextStream::IndentScope indentScope(ts);
309     inputEffect(0)->externalRepresentation(ts, representation);
310     return ts;
311 }
312
313 } // namespace WebCore