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