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 Renata Hodovan <reni@inf.u-szeged.hu>
7 * Copyright (C) 2011 Gabor Loki <loki@webkit.org>
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#if ENABLE(FILTERS)
28#include "FETurbulence.h"
29
30#include "Filter.h"
31#include "TextStream.h"
32
33#include <runtime/Uint8ClampedArray.h>
34#include <wtf/MathExtras.h>
35#include <wtf/ParallelJobs.h>
36
37namespace WebCore {
38
39/*
40    Produces results in the range [1, 2**31 - 2]. Algorithm is:
41    r = (a * r) mod m where a = randAmplitude = 16807 and
42    m = randMaximum = 2**31 - 1 = 2147483647, r = seed.
43    See [Park & Miller], CACM vol. 31 no. 10 p. 1195, Oct. 1988
44    To test: the algorithm should produce the result 1043618065
45    as the 10,000th generated number if the original seed is 1.
46*/
47static const int s_perlinNoise = 4096;
48static const long s_randMaximum = 2147483647; // 2**31 - 1
49static const int s_randAmplitude = 16807; // 7**5; primitive root of m
50static const int s_randQ = 127773; // m / a
51static const int s_randR = 2836; // m % a
52
53FETurbulence::FETurbulence(Filter* filter, TurbulenceType type, float baseFrequencyX, float baseFrequencyY, int numOctaves, float seed, bool stitchTiles)
54    : FilterEffect(filter)
55    , m_type(type)
56    , m_baseFrequencyX(baseFrequencyX)
57    , m_baseFrequencyY(baseFrequencyY)
58    , m_numOctaves(numOctaves)
59    , m_seed(seed)
60    , m_stitchTiles(stitchTiles)
61{
62}
63
64PassRefPtr<FETurbulence> FETurbulence::create(Filter* filter, TurbulenceType type, float baseFrequencyX, float baseFrequencyY, int numOctaves, float seed, bool stitchTiles)
65{
66    return adoptRef(new FETurbulence(filter, type, baseFrequencyX, baseFrequencyY, numOctaves, seed, stitchTiles));
67}
68
69TurbulenceType FETurbulence::type() const
70{
71    return m_type;
72}
73
74bool FETurbulence::setType(TurbulenceType type)
75{
76    if (m_type == type)
77        return false;
78    m_type = type;
79    return true;
80}
81
82float FETurbulence::baseFrequencyY() const
83{
84    return m_baseFrequencyY;
85}
86
87bool FETurbulence::setBaseFrequencyY(float baseFrequencyY)
88{
89    if (m_baseFrequencyY == baseFrequencyY)
90        return false;
91    m_baseFrequencyY = baseFrequencyY;
92    return true;
93}
94
95float FETurbulence::baseFrequencyX() const
96{
97    return m_baseFrequencyX;
98}
99
100bool FETurbulence::setBaseFrequencyX(float baseFrequencyX)
101{
102    if (m_baseFrequencyX == baseFrequencyX)
103        return false;
104    m_baseFrequencyX = baseFrequencyX;
105    return true;
106}
107
108float FETurbulence::seed() const
109{
110    return m_seed;
111}
112
113bool FETurbulence::setSeed(float seed)
114{
115    if (m_seed == seed)
116        return false;
117    m_seed = seed;
118    return true;
119}
120
121int FETurbulence::numOctaves() const
122{
123    return m_numOctaves;
124}
125
126bool FETurbulence::setNumOctaves(int numOctaves)
127{
128    if (m_numOctaves == numOctaves)
129        return false;
130    m_numOctaves = numOctaves;
131    return true;
132}
133
134bool FETurbulence::stitchTiles() const
135{
136    return m_stitchTiles;
137}
138
139bool FETurbulence::setStitchTiles(bool stitch)
140{
141    if (m_stitchTiles == stitch)
142        return false;
143    m_stitchTiles = stitch;
144    return true;
145}
146
147// The turbulence calculation code is an adapted version of what appears in the SVG 1.1 specification:
148// http://www.w3.org/TR/SVG11/filters.html#feTurbulence
149
150// Compute pseudo random number.
151inline long FETurbulence::PaintingData::random()
152{
153    long result = s_randAmplitude * (seed % s_randQ) - s_randR * (seed / s_randQ);
154    if (result <= 0)
155        result += s_randMaximum;
156    seed = result;
157    return result;
158}
159
160inline float smoothCurve(float t)
161{
162    return t * t * (3 - 2 * t);
163}
164
165inline float linearInterpolation(float t, float a, float b)
166{
167    return a + t * (b - a);
168}
169
170inline void FETurbulence::initPaint(PaintingData& paintingData)
171{
172    float normalizationFactor;
173
174    // The seed value clamp to the range [1, s_randMaximum - 1].
175    if (paintingData.seed <= 0)
176        paintingData.seed = -(paintingData.seed % (s_randMaximum - 1)) + 1;
177    if (paintingData.seed > s_randMaximum - 1)
178        paintingData.seed = s_randMaximum - 1;
179
180    float* gradient;
181    for (int channel = 0; channel < 4; ++channel) {
182        for (int i = 0; i < s_blockSize; ++i) {
183            paintingData.latticeSelector[i] = i;
184            gradient = paintingData.gradient[channel][i];
185            gradient[0] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize;
186            gradient[1] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize;
187            normalizationFactor = sqrtf(gradient[0] * gradient[0] + gradient[1] * gradient[1]);
188            gradient[0] /= normalizationFactor;
189            gradient[1] /= normalizationFactor;
190        }
191    }
192    for (int i = s_blockSize - 1; i > 0; --i) {
193        int k = paintingData.latticeSelector[i];
194        int j = paintingData.random() % s_blockSize;
195        ASSERT(j >= 0);
196        ASSERT(j < 2 * s_blockSize + 2);
197        paintingData.latticeSelector[i] = paintingData.latticeSelector[j];
198        paintingData.latticeSelector[j] = k;
199    }
200    for (int i = 0; i < s_blockSize + 2; ++i) {
201        paintingData.latticeSelector[s_blockSize + i] = paintingData.latticeSelector[i];
202        for (int channel = 0; channel < 4; ++channel) {
203            paintingData.gradient[channel][s_blockSize + i][0] = paintingData.gradient[channel][i][0];
204            paintingData.gradient[channel][s_blockSize + i][1] = paintingData.gradient[channel][i][1];
205        }
206    }
207}
208
209inline void checkNoise(int& noiseValue, int limitValue, int newValue)
210{
211    if (noiseValue >= limitValue)
212        noiseValue -= newValue;
213    if (noiseValue >= limitValue - 1)
214        noiseValue -= newValue - 1;
215}
216
217float FETurbulence::noise2D(int channel, PaintingData& paintingData, StitchData& stitchData, const FloatPoint& noiseVector)
218{
219    struct Noise {
220        int noisePositionIntegerValue;
221        float noisePositionFractionValue;
222
223        Noise(float component)
224        {
225            float position = component + s_perlinNoise;
226            noisePositionIntegerValue = static_cast<int>(position);
227            noisePositionFractionValue = position - noisePositionIntegerValue;
228        }
229    };
230
231    Noise noiseX(noiseVector.x());
232    Noise noiseY(noiseVector.y());
233    float* q;
234    float sx, sy, a, b, u, v;
235
236    // If stitching, adjust lattice points accordingly.
237    if (m_stitchTiles) {
238        checkNoise(noiseX.noisePositionIntegerValue, stitchData.wrapX, stitchData.width);
239        checkNoise(noiseY.noisePositionIntegerValue, stitchData.wrapY, stitchData.height);
240    }
241
242    noiseX.noisePositionIntegerValue &= s_blockMask;
243    noiseY.noisePositionIntegerValue &= s_blockMask;
244    int latticeIndex = paintingData.latticeSelector[noiseX.noisePositionIntegerValue];
245    int nextLatticeIndex = paintingData.latticeSelector[(noiseX.noisePositionIntegerValue + 1) & s_blockMask];
246
247    sx = smoothCurve(noiseX.noisePositionFractionValue);
248    sy = smoothCurve(noiseY.noisePositionFractionValue);
249
250    // This is taken 1:1 from SVG spec: http://www.w3.org/TR/SVG11/filters.html#feTurbulenceElement.
251    int temp = paintingData.latticeSelector[latticeIndex + noiseY.noisePositionIntegerValue];
252    q = paintingData.gradient[channel][temp];
253    u = noiseX.noisePositionFractionValue * q[0] + noiseY.noisePositionFractionValue * q[1];
254    temp = paintingData.latticeSelector[nextLatticeIndex + noiseY.noisePositionIntegerValue];
255    q = paintingData.gradient[channel][temp];
256    v = (noiseX.noisePositionFractionValue - 1) * q[0] + noiseY.noisePositionFractionValue * q[1];
257    a = linearInterpolation(sx, u, v);
258    temp = paintingData.latticeSelector[latticeIndex + noiseY.noisePositionIntegerValue + 1];
259    q = paintingData.gradient[channel][temp];
260    u = noiseX.noisePositionFractionValue * q[0] + (noiseY.noisePositionFractionValue - 1) * q[1];
261    temp = paintingData.latticeSelector[nextLatticeIndex + noiseY.noisePositionIntegerValue + 1];
262    q = paintingData.gradient[channel][temp];
263    v = (noiseX.noisePositionFractionValue - 1) * q[0] + (noiseY.noisePositionFractionValue - 1) * q[1];
264    b = linearInterpolation(sx, u, v);
265    return linearInterpolation(sy, a, b);
266}
267
268unsigned char FETurbulence::calculateTurbulenceValueForPoint(int channel, PaintingData& paintingData, StitchData& stitchData, const FloatPoint& point)
269{
270    float tileWidth = paintingData.filterSize.width();
271    float tileHeight = paintingData.filterSize.height();
272    ASSERT(tileWidth > 0 && tileHeight > 0);
273    float baseFrequencyX = m_baseFrequencyX;
274    float baseFrequencyY = m_baseFrequencyY;
275    // Adjust the base frequencies if necessary for stitching.
276    if (m_stitchTiles) {
277        // When stitching tiled turbulence, the frequencies must be adjusted
278        // so that the tile borders will be continuous.
279        if (baseFrequencyX) {
280            float lowFrequency = floorf(tileWidth * baseFrequencyX) / tileWidth;
281            float highFrequency = ceilf(tileWidth * baseFrequencyX) / tileWidth;
282            // BaseFrequency should be non-negative according to the standard.
283            if (baseFrequencyX / lowFrequency < highFrequency / baseFrequencyX)
284                baseFrequencyX = lowFrequency;
285            else
286                baseFrequencyX = highFrequency;
287        }
288        if (baseFrequencyY) {
289            float lowFrequency = floorf(tileHeight * baseFrequencyY) / tileHeight;
290            float highFrequency = ceilf(tileHeight * baseFrequencyY) / tileHeight;
291            if (baseFrequencyY / lowFrequency < highFrequency / baseFrequencyY)
292                baseFrequencyY = lowFrequency;
293            else
294                baseFrequencyY = highFrequency;
295        }
296        // Set up TurbulenceInitial stitch values.
297        stitchData.width = roundf(tileWidth * baseFrequencyX);
298        stitchData.wrapX = s_perlinNoise + stitchData.width;
299        stitchData.height = roundf(tileHeight * baseFrequencyY);
300        stitchData.wrapY = s_perlinNoise + stitchData.height;
301    }
302    float turbulenceFunctionResult = 0;
303    FloatPoint noiseVector(point.x() * baseFrequencyX, point.y() * baseFrequencyY);
304    float ratio = 1;
305    for (int octave = 0; octave < m_numOctaves; ++octave) {
306        if (m_type == FETURBULENCE_TYPE_FRACTALNOISE)
307            turbulenceFunctionResult += noise2D(channel, paintingData, stitchData, noiseVector) / ratio;
308        else
309            turbulenceFunctionResult += fabsf(noise2D(channel, paintingData, stitchData, noiseVector)) / ratio;
310        noiseVector.setX(noiseVector.x() * 2);
311        noiseVector.setY(noiseVector.y() * 2);
312        ratio *= 2;
313        if (m_stitchTiles) {
314            // Update stitch values. Subtracting s_perlinNoiseoise before the multiplication and
315            // adding it afterward simplifies to subtracting it once.
316            stitchData.width *= 2;
317            stitchData.wrapX = 2 * stitchData.wrapX - s_perlinNoise;
318            stitchData.height *= 2;
319            stitchData.wrapY = 2 * stitchData.wrapY - s_perlinNoise;
320        }
321    }
322
323    // The value of turbulenceFunctionResult comes from ((turbulenceFunctionResult * 255) + 255) / 2 by fractalNoise
324    // and (turbulenceFunctionResult * 255) by turbulence.
325    if (m_type == FETURBULENCE_TYPE_FRACTALNOISE)
326        turbulenceFunctionResult = turbulenceFunctionResult * 0.5f + 0.5f;
327    // Clamp result
328    turbulenceFunctionResult = std::max(std::min(turbulenceFunctionResult, 1.f), 0.f);
329    return static_cast<unsigned char>(turbulenceFunctionResult * 255);
330}
331
332inline void FETurbulence::fillRegion(Uint8ClampedArray* pixelArray, PaintingData& paintingData, int startY, int endY)
333{
334    IntRect filterRegion = absolutePaintRect();
335    IntPoint point(0, filterRegion.y() + startY);
336    int indexOfPixelChannel = startY * (filterRegion.width() << 2);
337    int channel;
338    StitchData stitchData;
339
340    for (int y = startY; y < endY; ++y) {
341        point.setY(point.y() + 1);
342        point.setX(filterRegion.x());
343        for (int x = 0; x < filterRegion.width(); ++x) {
344            point.setX(point.x() + 1);
345            for (channel = 0; channel < 4; ++channel, ++indexOfPixelChannel)
346                pixelArray->set(indexOfPixelChannel, calculateTurbulenceValueForPoint(channel, paintingData, stitchData, filter().mapAbsolutePointToLocalPoint(point)));
347        }
348    }
349}
350
351void FETurbulence::fillRegionWorker(FillRegionParameters* parameters)
352{
353    parameters->filter->fillRegion(parameters->pixelArray, *parameters->paintingData, parameters->startY, parameters->endY);
354}
355
356void FETurbulence::platformApplySoftware()
357{
358    Uint8ClampedArray* pixelArray = createUnmultipliedImageResult();
359    if (!pixelArray)
360        return;
361
362    if (absolutePaintRect().isEmpty()) {
363        pixelArray->zeroFill();
364        return;
365    }
366
367    PaintingData paintingData(m_seed, roundedIntSize(filterPrimitiveSubregion().size()));
368    initPaint(paintingData);
369
370    int optimalThreadNumber = (absolutePaintRect().width() * absolutePaintRect().height()) / s_minimalRectDimension;
371    if (optimalThreadNumber > 1) {
372        // Initialize parallel jobs
373        WTF::ParallelJobs<FillRegionParameters> parallelJobs(&WebCore::FETurbulence::fillRegionWorker, optimalThreadNumber);
374
375        // Fill the parameter array
376        int i = parallelJobs.numberOfJobs();
377        if (i > 1) {
378            // Split the job into "stepY"-sized jobs but there a few jobs that need to be slightly larger since
379            // stepY * jobs < total size. These extras are handled by the remainder "jobsWithExtra".
380            const int stepY = absolutePaintRect().height() / i;
381            const int jobsWithExtra = absolutePaintRect().height() % i;
382
383            int startY = 0;
384            for (; i > 0; --i) {
385                FillRegionParameters& params = parallelJobs.parameter(i-1);
386                params.filter = this;
387                params.pixelArray = pixelArray;
388                params.paintingData = &paintingData;
389                params.startY = startY;
390                startY += i < jobsWithExtra ? stepY + 1 : stepY;
391                params.endY = startY;
392            }
393
394            // Execute parallel jobs
395            parallelJobs.execute();
396            return;
397        }
398    }
399
400    // Fallback to single threaded mode if there is no room for a new thread or the paint area is too small.
401    fillRegion(pixelArray, paintingData, 0, absolutePaintRect().height());
402}
403
404void FETurbulence::dump()
405{
406}
407
408static TextStream& operator<<(TextStream& ts, const TurbulenceType& type)
409{
410    switch (type) {
411    case FETURBULENCE_TYPE_UNKNOWN:
412        ts << "UNKNOWN";
413        break;
414    case FETURBULENCE_TYPE_TURBULENCE:
415        ts << "TURBULANCE";
416        break;
417    case FETURBULENCE_TYPE_FRACTALNOISE:
418        ts << "NOISE";
419        break;
420    }
421    return ts;
422}
423
424TextStream& FETurbulence::externalRepresentation(TextStream& ts, int indent) const
425{
426    writeIndent(ts, indent);
427    ts << "[feTurbulence";
428    FilterEffect::externalRepresentation(ts);
429    ts << " type=\"" << type() << "\" "
430       << "baseFrequency=\"" << baseFrequencyX() << ", " << baseFrequencyY() << "\" "
431       << "seed=\"" << seed() << "\" "
432       << "numOctaves=\"" << numOctaves() << "\" "
433       << "stitchTiles=\"" << stitchTiles() << "\"]\n";
434    return ts;
435}
436
437} // namespace WebCore
438
439#endif // ENABLE(FILTERS)
440