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