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) 2010 Zoltan Herczeg <zherczeg@webkit.org>
7 * Copyright (C) 2013 Google Inc. 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 "platform/graphics/filters/FEConvolveMatrix.h"
27
28#include "SkMatrixConvolutionImageFilter.h"
29#include "platform/graphics/filters/ParallelJobs.h"
30#include "platform/graphics/filters/SkiaImageFilterBuilder.h"
31#include "platform/text/TextStream.h"
32#include "wtf/OwnPtr.h"
33#include "wtf/Uint8ClampedArray.h"
34
35namespace blink {
36
37FEConvolveMatrix::FEConvolveMatrix(Filter* filter, const IntSize& kernelSize,
38    float divisor, float bias, const IntPoint& targetOffset, EdgeModeType edgeMode,
39    const FloatPoint& kernelUnitLength, bool preserveAlpha, const Vector<float>& kernelMatrix)
40    : FilterEffect(filter)
41    , m_kernelSize(kernelSize)
42    , m_divisor(divisor)
43    , m_bias(bias)
44    , m_targetOffset(targetOffset)
45    , m_edgeMode(edgeMode)
46    , m_kernelUnitLength(kernelUnitLength)
47    , m_preserveAlpha(preserveAlpha)
48    , m_kernelMatrix(kernelMatrix)
49{
50    ASSERT(m_kernelSize.width() > 0);
51    ASSERT(m_kernelSize.height() > 0);
52}
53
54PassRefPtr<FEConvolveMatrix> FEConvolveMatrix::create(Filter* filter, const IntSize& kernelSize,
55    float divisor, float bias, const IntPoint& targetOffset, EdgeModeType edgeMode,
56    const FloatPoint& kernelUnitLength, bool preserveAlpha, const Vector<float>& kernelMatrix)
57{
58    return adoptRef(new FEConvolveMatrix(filter, kernelSize, divisor, bias, targetOffset, edgeMode, kernelUnitLength,
59        preserveAlpha, kernelMatrix));
60}
61
62FloatRect FEConvolveMatrix::mapPaintRect(const FloatRect& rect, bool forward)
63{
64    FloatRect result = rect;
65
66    result.moveBy(forward ? -m_targetOffset : m_targetOffset - m_kernelSize);
67    result.expand(m_kernelSize);
68    return result;
69}
70
71IntSize FEConvolveMatrix::kernelSize() const
72{
73    return m_kernelSize;
74}
75
76void FEConvolveMatrix::setKernelSize(const IntSize& kernelSize)
77{
78    ASSERT(kernelSize.width() > 0);
79    ASSERT(kernelSize.height() > 0);
80    m_kernelSize = kernelSize;
81}
82
83const Vector<float>& FEConvolveMatrix::kernel() const
84{
85    return m_kernelMatrix;
86}
87
88void FEConvolveMatrix::setKernel(const Vector<float>& kernel)
89{
90    m_kernelMatrix = kernel;
91}
92
93float FEConvolveMatrix::divisor() const
94{
95    return m_divisor;
96}
97
98bool FEConvolveMatrix::setDivisor(float divisor)
99{
100    ASSERT(divisor);
101    if (m_divisor == divisor)
102        return false;
103    m_divisor = divisor;
104    return true;
105}
106
107float FEConvolveMatrix::bias() const
108{
109    return m_bias;
110}
111
112bool FEConvolveMatrix::setBias(float bias)
113{
114    if (m_bias == bias)
115        return false;
116    m_bias = bias;
117    return true;
118}
119
120IntPoint FEConvolveMatrix::targetOffset() const
121{
122    return m_targetOffset;
123}
124
125bool FEConvolveMatrix::setTargetOffset(const IntPoint& targetOffset)
126{
127    if (m_targetOffset == targetOffset)
128        return false;
129    m_targetOffset = targetOffset;
130    return true;
131}
132
133EdgeModeType FEConvolveMatrix::edgeMode() const
134{
135    return m_edgeMode;
136}
137
138bool FEConvolveMatrix::setEdgeMode(EdgeModeType edgeMode)
139{
140    if (m_edgeMode == edgeMode)
141        return false;
142    m_edgeMode = edgeMode;
143    return true;
144}
145
146FloatPoint FEConvolveMatrix::kernelUnitLength() const
147{
148    return m_kernelUnitLength;
149}
150
151bool FEConvolveMatrix::setKernelUnitLength(const FloatPoint& kernelUnitLength)
152{
153    ASSERT(kernelUnitLength.x() > 0);
154    ASSERT(kernelUnitLength.y() > 0);
155    if (m_kernelUnitLength == kernelUnitLength)
156        return false;
157    m_kernelUnitLength = kernelUnitLength;
158    return true;
159}
160
161bool FEConvolveMatrix::preserveAlpha() const
162{
163    return m_preserveAlpha;
164}
165
166bool FEConvolveMatrix::setPreserveAlpha(bool preserveAlpha)
167{
168    if (m_preserveAlpha == preserveAlpha)
169        return false;
170    m_preserveAlpha = preserveAlpha;
171    return true;
172}
173
174/*
175   -----------------------------------
176      ConvolveMatrix implementation
177   -----------------------------------
178
179   The image rectangle is split in the following way:
180
181      +---------------------+
182      |          A          |
183      +---------------------+
184      |   |             |   |
185      | B |      C      | D |
186      |   |             |   |
187      +---------------------+
188      |          E          |
189      +---------------------+
190
191   Where region C contains those pixels, whose values
192   can be calculated without crossing the edge of the rectangle.
193
194   Example:
195      Image size: width: 10, height: 10
196
197      Order (kernel matrix size): width: 3, height 4
198      Target: x:1, y:3
199
200      The following figure shows the target inside the kernel matrix:
201
202        ...
203        ...
204        ...
205        .X.
206
207   The regions in this case are the following:
208      Note: (x1, y1) top-left and (x2, y2) is the bottom-right corner
209      Note: row x2 and column y2 is not part of the region
210            only those (x, y) pixels, where x1 <= x < x2 and y1 <= y < y2
211
212      Region A: x1: 0, y1: 0, x2: 10, y2: 3
213      Region B: x1: 0, y1: 3, x2: 1, y2: 10
214      Region C: x1: 1, y1: 3, x2: 9, y2: 10
215      Region D: x1: 9, y1: 3, x2: 10, y2: 10
216      Region E: x1: 0, y1: 10, x2: 10, y2: 10 (empty region)
217
218   Since region C (often) contains most of the pixels, we implemented
219   a fast algoritm to calculate these values, called fastSetInteriorPixels.
220   For other regions, fastSetOuterPixels is used, which calls getPixelValue,
221   to handle pixels outside of the image. In a rare situations, when
222   kernel matrix is bigger than the image, all pixels are calculated by this
223   function.
224
225   Although these two functions have lot in common, I decided not to make
226   common a template for them, since there are key differences as well,
227   and would make it really hard to understand.
228*/
229
230static ALWAYS_INLINE unsigned char clampRGBAValue(float channel, unsigned char max = 255)
231{
232    if (channel <= 0)
233        return 0;
234    if (channel >= max)
235        return max;
236    return channel;
237}
238
239template<bool preserveAlphaValues>
240ALWAYS_INLINE void setDestinationPixels(Uint8ClampedArray* image, int& pixel, float* totals, float divisor, float bias, Uint8ClampedArray* src)
241{
242    unsigned char maxAlpha = preserveAlphaValues ? 255 : clampRGBAValue(totals[3] / divisor + bias);
243    for (int i = 0; i < 3; ++i)
244        image->set(pixel++, clampRGBAValue(totals[i] / divisor + bias, maxAlpha));
245
246    if (preserveAlphaValues) {
247        image->set(pixel, src->item(pixel));
248        ++pixel;
249    } else {
250        image->set(pixel++, maxAlpha);
251    }
252}
253
254#if defined(_MSC_VER) && (_MSC_VER >= 1700)
255// Incorrectly diagnosing overwrite of stack in |totals| due to |preserveAlphaValues|.
256#pragma warning(push)
257#pragma warning(disable: 4789)
258#endif
259
260// Only for region C
261template<bool preserveAlphaValues>
262ALWAYS_INLINE void FEConvolveMatrix::fastSetInteriorPixels(PaintingData& paintingData, int clipRight, int clipBottom, int yStart, int yEnd)
263{
264    // edge mode does not affect these pixels
265    int pixel = (m_targetOffset.y() * paintingData.width + m_targetOffset.x()) * 4;
266    int kernelIncrease = clipRight * 4;
267    int xIncrease = (m_kernelSize.width() - 1) * 4;
268    // Contains the sum of rgb(a) components
269    float totals[3 + (preserveAlphaValues ? 0 : 1)];
270
271    // m_divisor cannot be 0, SVGFEConvolveMatrixElement ensures this
272    ASSERT(m_divisor);
273
274    // Skip the first '(clipBottom - yEnd)' lines
275    pixel += (clipBottom - yEnd) * (xIncrease + (clipRight + 1) * 4);
276    int startKernelPixel = (clipBottom - yEnd) * (xIncrease + (clipRight + 1) * 4);
277
278    for (int y = yEnd + 1; y > yStart; --y) {
279        for (int x = clipRight + 1; x > 0; --x) {
280            int kernelValue = m_kernelMatrix.size() - 1;
281            int kernelPixel = startKernelPixel;
282            int width = m_kernelSize.width();
283
284            totals[0] = 0;
285            totals[1] = 0;
286            totals[2] = 0;
287            if (!preserveAlphaValues)
288                totals[3] = 0;
289
290            while (kernelValue >= 0) {
291                totals[0] += m_kernelMatrix[kernelValue] * static_cast<float>(paintingData.srcPixelArray->item(kernelPixel++));
292                totals[1] += m_kernelMatrix[kernelValue] * static_cast<float>(paintingData.srcPixelArray->item(kernelPixel++));
293                totals[2] += m_kernelMatrix[kernelValue] * static_cast<float>(paintingData.srcPixelArray->item(kernelPixel++));
294                if (!preserveAlphaValues)
295                    totals[3] += m_kernelMatrix[kernelValue] * static_cast<float>(paintingData.srcPixelArray->item(kernelPixel));
296                ++kernelPixel;
297                --kernelValue;
298                if (!--width) {
299                    kernelPixel += kernelIncrease;
300                    width = m_kernelSize.width();
301                }
302            }
303
304            setDestinationPixels<preserveAlphaValues>(paintingData.dstPixelArray, pixel, totals, m_divisor, paintingData.bias, paintingData.srcPixelArray);
305            startKernelPixel += 4;
306        }
307        pixel += xIncrease;
308        startKernelPixel += xIncrease;
309    }
310}
311
312ALWAYS_INLINE int FEConvolveMatrix::getPixelValue(PaintingData& paintingData, int x, int y)
313{
314    if (x >= 0 && x < paintingData.width && y >= 0 && y < paintingData.height)
315        return (y * paintingData.width + x) << 2;
316
317    switch (m_edgeMode) {
318    default: // EDGEMODE_NONE
319        return -1;
320    case EDGEMODE_DUPLICATE:
321        if (x < 0)
322            x = 0;
323        else if (x >= paintingData.width)
324            x = paintingData.width - 1;
325        if (y < 0)
326            y = 0;
327        else if (y >= paintingData.height)
328            y = paintingData.height - 1;
329        return (y * paintingData.width + x) << 2;
330    case EDGEMODE_WRAP:
331        while (x < 0)
332            x += paintingData.width;
333        x %= paintingData.width;
334        while (y < 0)
335            y += paintingData.height;
336        y %= paintingData.height;
337        return (y * paintingData.width + x) << 2;
338    }
339}
340
341// For other regions than C
342template<bool preserveAlphaValues>
343void FEConvolveMatrix::fastSetOuterPixels(PaintingData& paintingData, int x1, int y1, int x2, int y2)
344{
345    int pixel = (y1 * paintingData.width + x1) * 4;
346    int height = y2 - y1;
347    int width = x2 - x1;
348    int beginKernelPixelX = x1 - m_targetOffset.x();
349    int startKernelPixelX = beginKernelPixelX;
350    int startKernelPixelY = y1 - m_targetOffset.y();
351    int xIncrease = (paintingData.width - width) * 4;
352    // Contains the sum of rgb(a) components
353    float totals[3 + (preserveAlphaValues ? 0 : 1)];
354
355    // m_divisor cannot be 0, SVGFEConvolveMatrixElement ensures this
356    ASSERT(m_divisor);
357
358    for (int y = height; y > 0; --y) {
359        for (int x = width; x > 0; --x) {
360            int kernelValue = m_kernelMatrix.size() - 1;
361            int kernelPixelX = startKernelPixelX;
362            int kernelPixelY = startKernelPixelY;
363            int width = m_kernelSize.width();
364
365            totals[0] = 0;
366            totals[1] = 0;
367            totals[2] = 0;
368            if (!preserveAlphaValues)
369                totals[3] = 0;
370
371            while (kernelValue >= 0) {
372                int pixelIndex = getPixelValue(paintingData, kernelPixelX, kernelPixelY);
373                if (pixelIndex >= 0) {
374                    totals[0] += m_kernelMatrix[kernelValue] * static_cast<float>(paintingData.srcPixelArray->item(pixelIndex));
375                    totals[1] += m_kernelMatrix[kernelValue] * static_cast<float>(paintingData.srcPixelArray->item(pixelIndex + 1));
376                    totals[2] += m_kernelMatrix[kernelValue] * static_cast<float>(paintingData.srcPixelArray->item(pixelIndex + 2));
377                }
378                if (!preserveAlphaValues && pixelIndex >= 0)
379                    totals[3] += m_kernelMatrix[kernelValue] * static_cast<float>(paintingData.srcPixelArray->item(pixelIndex + 3));
380                ++kernelPixelX;
381                --kernelValue;
382                if (!--width) {
383                    kernelPixelX = startKernelPixelX;
384                    ++kernelPixelY;
385                    width = m_kernelSize.width();
386                }
387            }
388
389            setDestinationPixels<preserveAlphaValues>(paintingData.dstPixelArray, pixel, totals, m_divisor, paintingData.bias, paintingData.srcPixelArray);
390            ++startKernelPixelX;
391        }
392        pixel += xIncrease;
393        startKernelPixelX = beginKernelPixelX;
394        ++startKernelPixelY;
395    }
396}
397
398#if defined(_MSC_VER) && (_MSC_VER >= 1700)
399#pragma warning(pop) // Disable of 4789
400#endif
401
402ALWAYS_INLINE void FEConvolveMatrix::setInteriorPixels(PaintingData& paintingData, int clipRight, int clipBottom, int yStart, int yEnd)
403{
404    // Must be implemented here, since it refers another ALWAYS_INLINE
405    // function, which defined in this C++ source file as well
406    if (m_preserveAlpha)
407        fastSetInteriorPixels<true>(paintingData, clipRight, clipBottom, yStart, yEnd);
408    else
409        fastSetInteriorPixels<false>(paintingData, clipRight, clipBottom, yStart, yEnd);
410}
411
412ALWAYS_INLINE void FEConvolveMatrix::setOuterPixels(PaintingData& paintingData, int x1, int y1, int x2, int y2)
413{
414    // Although this function can be moved to the header, it is implemented here
415    // because setInteriorPixels is also implemented here
416    if (m_preserveAlpha)
417        fastSetOuterPixels<true>(paintingData, x1, y1, x2, y2);
418    else
419        fastSetOuterPixels<false>(paintingData, x1, y1, x2, y2);
420}
421
422void FEConvolveMatrix::setInteriorPixelsWorker(InteriorPixelParameters* param)
423{
424    param->filter->setInteriorPixels(*param->paintingData, param->clipRight, param->clipBottom, param->yStart, param->yEnd);
425}
426
427void FEConvolveMatrix::applySoftware()
428{
429    FilterEffect* in = inputEffect(0);
430
431    Uint8ClampedArray* resultImage;
432    if (m_preserveAlpha)
433        resultImage = createUnmultipliedImageResult();
434    else
435        resultImage = createPremultipliedImageResult();
436    if (!resultImage)
437        return;
438
439    IntRect effectDrawingRect = requestedRegionOfInputImageData(in->absolutePaintRect());
440
441    RefPtr<Uint8ClampedArray> srcPixelArray;
442    if (m_preserveAlpha)
443        srcPixelArray = in->asUnmultipliedImage(effectDrawingRect);
444    else
445        srcPixelArray = in->asPremultipliedImage(effectDrawingRect);
446
447    IntSize paintSize = absolutePaintRect().size();
448    PaintingData paintingData;
449    paintingData.srcPixelArray = srcPixelArray.get();
450    paintingData.dstPixelArray = resultImage;
451    paintingData.width = paintSize.width();
452    paintingData.height = paintSize.height();
453    paintingData.bias = m_bias * 255;
454
455    // Drawing fully covered pixels
456    int clipRight = paintSize.width() - m_kernelSize.width();
457    int clipBottom = paintSize.height() - m_kernelSize.height();
458
459    if (clipRight >= 0 && clipBottom >= 0) {
460
461        int optimalThreadNumber = (absolutePaintRect().width() * absolutePaintRect().height()) / s_minimalRectDimension;
462        if (optimalThreadNumber > 1) {
463            ParallelJobs<InteriorPixelParameters> parallelJobs(&FEConvolveMatrix::setInteriorPixelsWorker, optimalThreadNumber);
464            const int numOfThreads = parallelJobs.numberOfJobs();
465
466            // Split the job into "heightPerThread" jobs but there a few jobs that need to be slightly larger since
467            // heightPerThread * jobs < total size. These extras are handled by the remainder "jobsWithExtra".
468            const int heightPerThread = clipBottom / numOfThreads;
469            const int jobsWithExtra = clipBottom % numOfThreads;
470
471            int startY = 0;
472            for (int job = 0; job < numOfThreads; ++job) {
473                InteriorPixelParameters& param = parallelJobs.parameter(job);
474                param.filter = this;
475                param.paintingData = &paintingData;
476                param.clipRight = clipRight;
477                param.clipBottom = clipBottom;
478                param.yStart = startY;
479                startY += job < jobsWithExtra ? heightPerThread + 1 : heightPerThread;
480                param.yEnd = startY;
481            }
482
483            parallelJobs.execute();
484        } else {
485            // Fallback to single threaded mode.
486            setInteriorPixels(paintingData, clipRight, clipBottom, 0, clipBottom);
487        }
488
489        clipRight += m_targetOffset.x() + 1;
490        clipBottom += m_targetOffset.y() + 1;
491        if (m_targetOffset.y() > 0)
492            setOuterPixels(paintingData, 0, 0, paintSize.width(), m_targetOffset.y());
493        if (clipBottom < paintSize.height())
494            setOuterPixels(paintingData, 0, clipBottom, paintSize.width(), paintSize.height());
495        if (m_targetOffset.x() > 0)
496            setOuterPixels(paintingData, 0, m_targetOffset.y(), m_targetOffset.x(), clipBottom);
497        if (clipRight < paintSize.width())
498            setOuterPixels(paintingData, clipRight, m_targetOffset.y(), paintSize.width(), clipBottom);
499    } else {
500        // Rare situation, not optimizied for speed
501        setOuterPixels(paintingData, 0, 0, paintSize.width(), paintSize.height());
502    }
503}
504
505SkMatrixConvolutionImageFilter::TileMode toSkiaTileMode(EdgeModeType edgeMode)
506{
507    switch (edgeMode) {
508    case EDGEMODE_DUPLICATE:
509        return SkMatrixConvolutionImageFilter::kClamp_TileMode;
510    case EDGEMODE_WRAP:
511        return SkMatrixConvolutionImageFilter::kRepeat_TileMode;
512    case EDGEMODE_NONE:
513        return SkMatrixConvolutionImageFilter::kClampToBlack_TileMode;
514    default:
515        return SkMatrixConvolutionImageFilter::kClamp_TileMode;
516    }
517}
518
519PassRefPtr<SkImageFilter> FEConvolveMatrix::createImageFilter(SkiaImageFilterBuilder* builder)
520{
521    RefPtr<SkImageFilter> input(builder->build(inputEffect(0), operatingColorSpace()));
522
523    SkISize kernelSize(SkISize::Make(m_kernelSize.width(), m_kernelSize.height()));
524    int numElements = kernelSize.width() * kernelSize.height();
525    SkScalar gain = SkFloatToScalar(1.0f / m_divisor);
526    SkScalar bias = SkFloatToScalar(m_bias * 255);
527    SkIPoint target = SkIPoint::Make(m_targetOffset.x(), m_targetOffset.y());
528    SkMatrixConvolutionImageFilter::TileMode tileMode = toSkiaTileMode(m_edgeMode);
529    bool convolveAlpha = !m_preserveAlpha;
530    OwnPtr<SkScalar[]> kernel = adoptArrayPtr(new SkScalar[numElements]);
531    for (int i = 0; i < numElements; ++i)
532        kernel[i] = SkFloatToScalar(m_kernelMatrix[numElements - 1 - i]);
533    SkImageFilter::CropRect cropRect = getCropRect(builder->cropOffset());
534    return adoptRef(SkMatrixConvolutionImageFilter::Create(kernelSize, kernel.get(), gain, bias, target, tileMode, convolveAlpha, input.get(), &cropRect));
535}
536
537static TextStream& operator<<(TextStream& ts, const EdgeModeType& type)
538{
539    switch (type) {
540    case EDGEMODE_UNKNOWN:
541        ts << "UNKNOWN";
542        break;
543    case EDGEMODE_DUPLICATE:
544        ts << "DUPLICATE";
545        break;
546    case EDGEMODE_WRAP:
547        ts << "WRAP";
548        break;
549    case EDGEMODE_NONE:
550        ts << "NONE";
551        break;
552    }
553    return ts;
554}
555
556TextStream& FEConvolveMatrix::externalRepresentation(TextStream& ts, int indent) const
557{
558    writeIndent(ts, indent);
559    ts << "[feConvolveMatrix";
560    FilterEffect::externalRepresentation(ts);
561    ts << " order=\"" << m_kernelSize << "\" "
562       << "kernelMatrix=\"" << m_kernelMatrix  << "\" "
563       << "divisor=\"" << m_divisor << "\" "
564       << "bias=\"" << m_bias << "\" "
565       << "target=\"" << m_targetOffset << "\" "
566       << "edgeMode=\"" << m_edgeMode << "\" "
567       << "kernelUnitLength=\"" << m_kernelUnitLength << "\" "
568       << "preserveAlpha=\"" << m_preserveAlpha << "\"]\n";
569    inputEffect(0)->externalRepresentation(ts, indent + 1);
570    return ts;
571}
572
573}; // namespace blink
574