8a89d13a23c2276a818a4b508e1c6ab43a78426a
[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 "ColorUtilities.h"
29 #include "Filter.h"
30 #include "ImageData.h"
31 #include <wtf/ParallelJobs.h>
32 #include <wtf/Vector.h>
33 #include <wtf/text/TextStream.h>
34
35 namespace WebCore {
36
37 FEMorphology::FEMorphology(Filter& filter, MorphologyOperatorType type, float radiusX, float radiusY)
38     : FilterEffect(filter)
39     , m_type(type)
40     , m_radiusX(radiusX)
41     , m_radiusY(radiusY)
42 {
43 }
44
45 Ref<FEMorphology> FEMorphology::create(Filter& filter, MorphologyOperatorType type, float radiusX, float radiusY)
46 {
47     return adoptRef(*new FEMorphology(filter, type, radiusX, radiusY));
48 }
49
50 bool FEMorphology::setMorphologyOperator(MorphologyOperatorType type)
51 {
52     if (m_type == type)
53         return false;
54     m_type = type;
55     return true;
56 }
57
58 bool FEMorphology::setRadiusX(float radiusX)
59 {
60     if (m_radiusX == radiusX)
61         return false;
62     m_radiusX = radiusX;
63     return true;
64 }
65
66 bool FEMorphology::setRadiusY(float radiusY)
67 {
68     if (m_radiusY == radiusY)
69         return false;
70     m_radiusY = radiusY;
71     return true;
72 }
73
74 void FEMorphology::determineAbsolutePaintRect()
75 {
76     FloatRect paintRect = inputEffect(0)->absolutePaintRect();
77     Filter& filter = this->filter();
78     paintRect.inflate(filter.scaledByFilterResolution({ m_radiusX, m_radiusY }));
79     if (clipsToBounds())
80         paintRect.intersect(maxEffectRect());
81     else
82         paintRect.unite(maxEffectRect());
83     setAbsolutePaintRect(enclosingIntRect(paintRect));
84 }
85
86 static inline int pixelArrayIndex(int x, int y, int width)
87 {
88     return (y * width + x) * 4;
89 }
90
91 inline ColorComponents<uint8_t> makeColorComponentsfromPixelValue(unsigned pixel)
92 {
93     return ColorComponents<uint8_t>((pixel >> 24) & 0xFF, (pixel >> 16) & 0xFF, (pixel >> 8) & 0xFF, pixel & 0xFF);
94 }
95
96 inline unsigned makePixelValueFromColorComponents(const ColorComponents<uint8_t>& components)
97 {
98     auto [r, g, b, a] = components;
99     return r << 24 | g << 16 | b << 8 | a;
100 }
101
102 template<MorphologyOperatorType type>
103 ALWAYS_INLINE ColorComponents<uint8_t> minOrMax(const ColorComponents<uint8_t>& a, const ColorComponents<uint8_t>& b)
104 {
105     if (type == FEMORPHOLOGY_OPERATOR_ERODE)
106         return perComponentMin(a, b);
107
108     return perComponentMax(a, b);
109 }
110
111 template<MorphologyOperatorType type>
112 ALWAYS_INLINE ColorComponents<uint8_t> columnExtremum(const Uint8ClampedArray& srcPixelArray, int x, int yStart, int yEnd, int width)
113 {
114     auto extremum = makeColorComponentsfromPixelValue(*reinterpret_cast<const unsigned*>(srcPixelArray.data() + pixelArrayIndex(x, yStart, width)));
115
116     for (int y = yStart + 1; y < yEnd; ++y) {
117         auto pixel = makeColorComponentsfromPixelValue(*reinterpret_cast<const unsigned*>(srcPixelArray.data() + pixelArrayIndex(x, y, width)));
118         extremum = minOrMax<type>(extremum, pixel);
119     }
120     return extremum;
121 }
122
123 ALWAYS_INLINE ColorComponents<uint8_t> columnExtremum(const Uint8ClampedArray& srcPixelArray, int x, int yStart, int yEnd, int width, MorphologyOperatorType type)
124 {
125     if (type == FEMORPHOLOGY_OPERATOR_ERODE)
126         return columnExtremum<FEMORPHOLOGY_OPERATOR_ERODE>(srcPixelArray, x, yStart, yEnd, width);
127
128     return columnExtremum<FEMORPHOLOGY_OPERATOR_DILATE>(srcPixelArray, x, yStart, yEnd, width);
129 }
130
131 using ColumnExtrema = Vector<ColorComponents<uint8_t>, 16>;
132
133 template<MorphologyOperatorType type>
134 ALWAYS_INLINE ColorComponents<uint8_t> kernelExtremum(const ColumnExtrema& kernel)
135 {
136     auto extremum = kernel[0];
137     for (size_t i = 1; i < kernel.size(); ++i)
138         extremum = minOrMax<type>(extremum, kernel[i]);
139
140     return extremum;
141 }
142
143 ALWAYS_INLINE ColorComponents<uint8_t> kernelExtremum(const ColumnExtrema& kernel, MorphologyOperatorType type)
144 {
145     if (type == FEMORPHOLOGY_OPERATOR_ERODE)
146         return kernelExtremum<FEMORPHOLOGY_OPERATOR_ERODE>(kernel);
147
148     return kernelExtremum<FEMORPHOLOGY_OPERATOR_DILATE>(kernel);
149 }
150
151 void FEMorphology::platformApplyGeneric(const PaintingData& paintingData, int startY, int endY)
152 {
153     ASSERT(endY > startY);
154
155     const auto& srcPixelArray = *paintingData.srcPixelArray;
156     auto& dstPixelArray = *paintingData.dstPixelArray;
157
158     const int radiusX = paintingData.radiusX;
159     const int radiusY = paintingData.radiusY;
160     const int width = paintingData.width;
161     const int height = paintingData.height;
162
163     ASSERT(radiusX <= width || radiusY <= height);
164     ASSERT(startY >= 0 && endY <= height && startY < endY);
165
166     ColumnExtrema extrema;
167     extrema.reserveInitialCapacity(2 * radiusX + 1);
168
169     for (int y = startY; y < endY; ++y) {
170         int yRadiusStart = std::max(0, y - radiusY);
171         int yRadiusEnd = std::min(height, y + radiusY + 1);
172
173         extrema.shrink(0);
174
175         // We start at the left edge, so compute extreme for the radiusX columns.
176         for (int x = 0; x < radiusX; ++x)
177             extrema.append(columnExtremum(srcPixelArray, x, yRadiusStart, yRadiusEnd, width, m_type));
178
179         // Kernel is filled, get extrema of next column
180         for (int x = 0; x < width; ++x) {
181             if (x < width - radiusX)
182                 extrema.append(columnExtremum(srcPixelArray, x + radiusX, yRadiusStart, yRadiusEnd, width, m_type));
183
184             if (x > radiusX)
185                 extrema.remove(0);
186
187             unsigned* destPixel = reinterpret_cast<unsigned*>(dstPixelArray.data() + pixelArrayIndex(x, y, width));
188             *destPixel = makePixelValueFromColorComponents(kernelExtremum(extrema, m_type));
189         }
190     }
191 }
192
193 void FEMorphology::platformApplyWorker(PlatformApplyParameters* param)
194 {
195     param->filter->platformApplyGeneric(*param->paintingData, param->startY, param->endY);
196 }
197
198 void FEMorphology::platformApply(const PaintingData& paintingData)
199 {
200     // Empirically, runtime is approximately linear over reasonable kernel sizes with a slope of about 0.65.
201     float kernelFactor = sqrt(paintingData.radiusX * paintingData.radiusY) * 0.65;
202
203     static const int minimalArea = (160 * 160); // Empirical data limit for parallel jobs
204     
205     unsigned maxNumThreads = paintingData.height / 8;
206     unsigned optimalThreadNumber = std::min<unsigned>((paintingData.width * paintingData.height * kernelFactor) / minimalArea, maxNumThreads);
207     if (optimalThreadNumber > 1) {
208         WTF::ParallelJobs<PlatformApplyParameters> parallelJobs(&WebCore::FEMorphology::platformApplyWorker, optimalThreadNumber);
209         auto numOfThreads = parallelJobs.numberOfJobs();
210         if (numOfThreads > 1) {
211             // Split the job into "jobSize"-sized jobs but there a few jobs that need to be slightly larger since
212             // jobSize * jobs < total size. These extras are handled by the remainder "jobsWithExtra".
213             int jobSize = paintingData.height / numOfThreads;
214             int jobsWithExtra = paintingData.height % numOfThreads;
215             int currentY = 0;
216             for (int job = numOfThreads - 1; job >= 0; --job) {
217                 PlatformApplyParameters& param = parallelJobs.parameter(job);
218                 param.filter = this;
219                 param.startY = currentY;
220                 currentY += job < jobsWithExtra ? jobSize + 1 : jobSize;
221                 param.endY = currentY;
222                 param.paintingData = &paintingData;
223             }
224             parallelJobs.execute();
225             return;
226         }
227         // Fallback to single thread model
228     }
229
230     platformApplyGeneric(paintingData, 0, paintingData.height);
231 }
232
233 bool FEMorphology::platformApplyDegenerate(Uint8ClampedArray& dstPixelArray, const IntRect& imageRect, int radiusX, int radiusY)
234 {
235     if (radiusX < 0 || radiusY < 0 || (!radiusX && !radiusY)) {
236         FilterEffect* in = inputEffect(0);
237         in->copyPremultipliedResult(dstPixelArray, imageRect);
238         return true;
239     }
240
241     return false;
242 }
243
244 void FEMorphology::platformApplySoftware()
245 {
246     FilterEffect* in = inputEffect(0);
247
248     auto* resultImage = createPremultipliedImageResult();
249     auto* dstPixelArray = resultImage ? resultImage->data() : nullptr;
250     if (!dstPixelArray)
251         return;
252
253     setIsAlphaImage(in->isAlphaImage());
254
255     IntRect effectDrawingRect = requestedRegionOfInputImageData(in->absolutePaintRect());
256
257     IntSize radius = flooredIntSize(FloatSize(m_radiusX, m_radiusY));
258     if (platformApplyDegenerate(*dstPixelArray, effectDrawingRect, radius.width(), radius.height()))
259         return;
260
261     Filter& filter = this->filter();
262     auto srcPixelArray = in->premultipliedResult(effectDrawingRect);
263     if (!srcPixelArray)
264         return;
265
266     radius = flooredIntSize(filter.scaledByFilterResolution({ m_radiusX, m_radiusY }));
267     int radiusX = std::min(effectDrawingRect.width() - 1, radius.width());
268     int radiusY = std::min(effectDrawingRect.height() - 1, radius.height());
269
270     if (platformApplyDegenerate(*dstPixelArray, effectDrawingRect, radiusX, radiusY))
271         return;
272     
273     PaintingData paintingData;
274     paintingData.srcPixelArray = srcPixelArray.get();
275     paintingData.dstPixelArray = dstPixelArray;
276     paintingData.width = ceilf(effectDrawingRect.width() * filter.filterScale());
277     paintingData.height = ceilf(effectDrawingRect.height() * filter.filterScale());
278     paintingData.radiusX = ceilf(radiusX * filter.filterScale());
279     paintingData.radiusY = ceilf(radiusY * filter.filterScale());
280
281     platformApply(paintingData);
282 }
283
284 static TextStream& operator<<(TextStream& ts, const MorphologyOperatorType& type)
285 {
286     switch (type) {
287     case FEMORPHOLOGY_OPERATOR_UNKNOWN:
288         ts << "UNKNOWN";
289         break;
290     case FEMORPHOLOGY_OPERATOR_ERODE:
291         ts << "ERODE";
292         break;
293     case FEMORPHOLOGY_OPERATOR_DILATE:
294         ts << "DILATE";
295         break;
296     }
297     return ts;
298 }
299
300 TextStream& FEMorphology::externalRepresentation(TextStream& ts, RepresentationType representation) const
301 {
302     ts << indent << "[feMorphology";
303     FilterEffect::externalRepresentation(ts, representation);
304     ts << " operator=\"" << morphologyOperator() << "\" "
305        << "radius=\"" << radiusX() << ", " << radiusY() << "\"]\n";
306
307     TextStream::IndentScope indentScope(ts);
308     inputEffect(0)->externalRepresentation(ts, representation);
309     return ts;
310 }
311
312 } // namespace WebCore