Merge WebKit at r64523 : Initial merge by git.

Change-Id: Ibb796c6802e757b1d9b40f58205cfbe4da95fcd4

2 files changed, 298 insertions, 39 deletions

diff --git a/WebCore/svg/graphics/filters/SVGFETurbulence.cpp b/WebCore/svg/graphics/filters/SVGFETurbulence.cpp
index db4b0bb..8042a47 100644
--- a/WebCore/svg/graphics/filters/SVGFETurbulence.cpp
+++ b/WebCore/svg/graphics/filters/SVGFETurbulence.cpp
@@ -2,6 +2,8 @@
     Copyright (C) 2004, 2005, 2006, 2007 Nikolas Zimmermann <zimmermann@kde.org>
                   2004, 2005 Rob Buis <buis@kde.org>
                   2005 Eric Seidel <eric@webkit.org>
+                  2009 Dirk Schulze <krit@webkit.org>
+                  2010 Renata Hodovan <reni@inf.u-szeged.hu>
 
     This library is free software; you can redistribute it and/or
     modify it under the terms of the GNU Library General Public
@@ -23,13 +25,31 @@
 
 #if ENABLE(SVG) && ENABLE(FILTERS)
 #include "SVGFETurbulence.h"
-#include "SVGRenderTreeAsText.h"
+
+#include "CanvasPixelArray.h"
 #include "Filter.h"
+#include "ImageData.h"
+#include "SVGRenderTreeAsText.h"
+
+#include <wtf/MathExtras.h>
 
 namespace WebCore {
 
-FETurbulence::FETurbulence(TurbulanceType type, const float& baseFrequencyX, const float& baseFrequencyY,
-    const int& numOctaves, const float& seed, bool stitchTiles)
+/*
+    Produces results in the range [1, 2**31 - 2]. Algorithm is:
+    r = (a * r) mod m where a = randAmplitude = 16807 and
+    m = randMaximum = 2**31 - 1 = 2147483647, r = seed.
+    See [Park & Miller], CACM vol. 31 no. 10 p. 1195, Oct. 1988
+    To test: the algorithm should produce the result 1043618065
+    as the 10,000th generated number if the original seed is 1.
+*/
+static const int s_perlinNoise = 4096;
+static const long s_randMaximum = 2147483647; // 2**31 - 1
+static const int s_randAmplitude = 16807; // 7**5; primitive root of m
+static const int s_randQ = 127773; // m / a
+static const int s_randR = 2836; // m % a
+
+FETurbulence::FETurbulence(TurbulanceType type, float baseFrequencyX, float baseFrequencyY, int numOctaves, float seed, bool stitchTiles)
     : FilterEffect()
     , m_type(type)
     , m_baseFrequencyX(baseFrequencyX)
@@ -40,8 +60,7 @@ FETurbulence::FETurbulence(TurbulanceType type, const float& baseFrequencyX, con
 {
 }
 
-PassRefPtr<FETurbulence> FETurbulence::create(TurbulanceType type, const float& baseFrequencyX, const float& baseFrequencyY,
-    const int& numOctaves, const float& seed, bool stitchTiles)
+PassRefPtr<FETurbulence> FETurbulence::create(TurbulanceType type, float baseFrequencyX, float baseFrequencyY, int numOctaves, float seed, bool stitchTiles)
 {
     return adoptRef(new FETurbulence(type, baseFrequencyX, baseFrequencyY, numOctaves, seed, stitchTiles));
 }
@@ -106,8 +125,226 @@ void FETurbulence::setStitchTiles(bool stitch)
     m_stitchTiles = stitch;
 }
 
-void FETurbulence::apply(Filter*)
+// The turbulence calculation code is an adapted version of what appears in the SVG 1.1 specification:
+// http://www.w3.org/TR/SVG11/filters.html#feTurbulence
+
+FETurbulence::PaintingData::PaintingData(long paintingSeed, const IntSize& paintingSize)
+    : seed(paintingSeed)
+    , width(0)
+    , height(0)
+    , wrapX(0)
+    , wrapY(0)
+    , channel(0)
+    , filterSize(paintingSize)
+{
+}
+
+// Compute pseudo random number.
+inline long FETurbulence::PaintingData::random()
+{
+    long result = s_randAmplitude * (seed % s_randQ) - s_randR * (seed / s_randQ);
+    if (result <= 0)
+        result += s_randMaximum;
+    seed = result;
+    return result;
+}
+
+inline float smoothCurve(float t)
+{
+    return t * t * (3 - 2 * t);
+}
+
+inline float linearInterpolation(float t, float a, float b)
+{
+    return a + t * (b - a);
+}
+
+inline void FETurbulence::initPaint(PaintingData& paintingData)
 {
+    float normalizationFactor;
+
+    // The seed value clamp to the range [1, s_randMaximum - 1].
+    if (paintingData.seed <= 0)
+        paintingData.seed = -(paintingData.seed % (s_randMaximum - 1)) + 1;
+    if (paintingData.seed > s_randMaximum - 1)
+        paintingData.seed = s_randMaximum - 1;
+
+    float* gradient;
+    for (int channel = 0; channel < 4; ++channel) {
+        for (int i = 0; i < s_blockSize; ++i) {
+            paintingData.latticeSelector[i] = i;
+            gradient = paintingData.gradient[channel][i];
+            gradient[0] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize;
+            gradient[1] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize;
+            normalizationFactor = sqrtf(gradient[0] * gradient[0] + gradient[1] * gradient[1]);
+            gradient[0] /= normalizationFactor;
+            gradient[1] /= normalizationFactor;
+        }
+    }
+    for (int i = s_blockSize - 1; i >= 0; --i) {
+        int k = paintingData.latticeSelector[i];
+        int j = paintingData.random() % s_blockSize;
+        ASSERT(j >= 0);
+        ASSERT(j < 2 * s_blockSize + 2);
+        paintingData.latticeSelector[i] = paintingData.latticeSelector[j];
+        paintingData.latticeSelector[j] = k;
+    }
+    for (int i = 0; i < s_blockSize + 2; ++i) {
+        paintingData.latticeSelector[s_blockSize + i] = paintingData.latticeSelector[i];
+        for (int channel = 0; channel < 4; ++channel) {
+            paintingData.gradient[channel][s_blockSize + i][0] = paintingData.gradient[channel][i][0];
+            paintingData.gradient[channel][s_blockSize + i][1] = paintingData.gradient[channel][i][1];
+        }
+    }
+}
+
+inline void checkNoise(int& noiseValue, int limitValue, int newValue)
+{
+    if (noiseValue >= limitValue)
+        noiseValue -= newValue;
+    if (noiseValue >= limitValue - 1)
+        noiseValue -= newValue - 1;
+}
+
+float FETurbulence::noise2D(PaintingData& paintingData, const FloatPoint& noiseVector)
+{
+    struct Noise {
+        int noisePositionIntegerValue;
+        float noisePositionFractionValue;
+
+        Noise(float component)
+        {
+            float position = component + s_perlinNoise;
+            noisePositionIntegerValue = static_cast<int>(position);
+            noisePositionFractionValue = position - noisePositionIntegerValue;
+        }
+    };
+
+    Noise noiseX(noiseVector.x());
+    Noise noiseY(noiseVector.y());
+    float* q;
+    float sx, sy, a, b, u, v;
+
+    // If stitching, adjust lattice points accordingly.
+    if (m_stitchTiles) {
+        checkNoise(noiseX.noisePositionIntegerValue, paintingData.wrapX, paintingData.width);
+        checkNoise(noiseY.noisePositionIntegerValue, paintingData.wrapY, paintingData.height);
+    }
+
+    noiseX.noisePositionIntegerValue &= s_blockMask;
+    noiseY.noisePositionIntegerValue &= s_blockMask;
+    int latticeIndex = paintingData.latticeSelector[noiseX.noisePositionIntegerValue];
+    int nextLatticeIndex = paintingData.latticeSelector[(noiseX.noisePositionIntegerValue + 1) & s_blockMask];
+
+    sx = smoothCurve(noiseX.noisePositionFractionValue);
+    sy = smoothCurve(noiseY.noisePositionFractionValue);
+
+    // This is taken 1:1 from SVG spec: http://www.w3.org/TR/SVG11/filters.html#feTurbulenceElement.
+    int temp = paintingData.latticeSelector[latticeIndex + noiseY.noisePositionIntegerValue];
+    q = paintingData.gradient[paintingData.channel][temp];
+    u = noiseX.noisePositionFractionValue * q[0] + noiseY.noisePositionFractionValue * q[1];
+    temp = paintingData.latticeSelector[nextLatticeIndex + noiseY.noisePositionIntegerValue];
+    q = paintingData.gradient[paintingData.channel][temp];
+    v = (noiseX.noisePositionFractionValue - 1) * q[0] + noiseY.noisePositionFractionValue * q[1];
+    a = linearInterpolation(sx, u, v);
+    temp = paintingData.latticeSelector[latticeIndex + noiseY.noisePositionIntegerValue + 1];
+    q = paintingData.gradient[paintingData.channel][temp];
+    u = noiseX.noisePositionFractionValue * q[0] + (noiseY.noisePositionFractionValue - 1) * q[1];
+    temp = paintingData.latticeSelector[nextLatticeIndex + noiseY.noisePositionIntegerValue + 1];
+    q = paintingData.gradient[paintingData.channel][temp];
+    v = (noiseX.noisePositionFractionValue - 1) * q[0] + (noiseY.noisePositionFractionValue - 1) * q[1];
+    b = linearInterpolation(sx, u, v);
+    return linearInterpolation(sy, a, b);
+}
+
+unsigned char FETurbulence::calculateTurbulenceValueForPoint(PaintingData& paintingData, const FloatPoint& point)
+{
+    float tileWidth = paintingData.filterSize.width();
+    ASSERT(tileWidth > 0);
+    float tileHeight = paintingData.filterSize.height();
+    ASSERT(tileHeight > 0);
+    // Adjust the base frequencies if necessary for stitching.
+    if (m_stitchTiles) {
+        // When stitching tiled turbulence, the frequencies must be adjusted
+        // so that the tile borders will be continuous.
+        if (m_baseFrequencyX) {
+            float lowFrequency = floorf(tileWidth * m_baseFrequencyX) / tileWidth;
+            float highFrequency = ceilf(tileWidth * m_baseFrequencyX) / tileWidth;
+            // BaseFrequency should be non-negative according to the standard.
+            if (m_baseFrequencyX / lowFrequency < highFrequency / m_baseFrequencyX)
+                m_baseFrequencyX = lowFrequency;
+            else
+                m_baseFrequencyX = highFrequency;
+        }
+        if (m_baseFrequencyY) {
+            float lowFrequency = floorf(tileHeight * m_baseFrequencyY) / tileHeight;
+            float highFrequency = ceilf(tileHeight * m_baseFrequencyY) / tileHeight;
+            if (m_baseFrequencyY / lowFrequency < highFrequency / m_baseFrequencyY)
+                m_baseFrequencyY = lowFrequency;
+            else
+                m_baseFrequencyY = highFrequency;
+        }
+        // Set up TurbulenceInitial stitch values.
+        paintingData.width = roundf(tileWidth * m_baseFrequencyX);
+        paintingData.wrapX = s_perlinNoise + paintingData.width;
+        paintingData.height = roundf(tileHeight * m_baseFrequencyY);
+        paintingData.wrapY = s_perlinNoise + paintingData.height;
+    }
+    float turbulenceFunctionResult = 0;
+    FloatPoint noiseVector(point.x() * m_baseFrequencyX, point.y() * m_baseFrequencyY);
+    float ratio = 1;
+    for (int octave = 0; octave < m_numOctaves; ++octave) {
+        if (m_type == FETURBULENCE_TYPE_FRACTALNOISE)
+            turbulenceFunctionResult += noise2D(paintingData, noiseVector) / ratio;
+        else
+            turbulenceFunctionResult += fabsf(noise2D(paintingData, noiseVector)) / ratio;
+        noiseVector.setX(noiseVector.x() * 2);
+        noiseVector.setY(noiseVector.y() * 2);
+        ratio *= 2;
+        if (m_stitchTiles) {
+            // Update stitch values. Subtracting s_perlinNoiseoise before the multiplication and
+            // adding it afterward simplifies to subtracting it once.
+            paintingData.width *= 2;
+            paintingData.wrapX = 2 * paintingData.wrapX - s_perlinNoise;
+            paintingData.height *= 2;
+            paintingData.wrapY = 2 * paintingData.wrapY - s_perlinNoise;
+        }
+    }
+
+    // Clamp result
+    turbulenceFunctionResult = std::max(std::min(turbulenceFunctionResult, 255.f), 0.f);
+    if (m_type == FETURBULENCE_TYPE_FRACTALNOISE)
+        return static_cast<unsigned char>(turbulenceFunctionResult * 127.5f + 127.5f); // It comes form (turbulenceFunctionResult * 255 + 255) / 2
+    return static_cast<unsigned char>(turbulenceFunctionResult * 255);
+}
+
+void FETurbulence::apply(Filter* filter)
+{
+    if (!getEffectContext())
+        return;
+
+    IntRect imageRect(IntPoint(), resultImage()->size());
+    if (!imageRect.size().width() || !imageRect.size().height())
+        return;
+
+    RefPtr<ImageData> imageData = ImageData::create(imageRect.width(), imageRect.height());
+    PaintingData paintingData(floorf(fabsf(m_seed)), imageRect.size());
+    initPaint(paintingData);
+
+    FloatRect filterRegion = filter->filterRegion();
+    FloatPoint point;
+    point.setY(filterRegion.y());
+    int indexOfPixelChannel = 0;
+    for (int y = 0; y < imageRect.height(); ++y) {
+        point.setY(point.y() + 1);
+        point.setX(filterRegion.x());
+        for (int x = 0; x < imageRect.width(); ++x) {
+            point.setX(point.x() + 1);
+            for (paintingData.channel = 0; paintingData.channel < 4; ++paintingData.channel, ++indexOfPixelChannel)
+                imageData->data()->set(indexOfPixelChannel, calculateTurbulenceValueForPoint(paintingData, point));
+        }
+    }
+    resultImage()->putUnmultipliedImageData(imageData.get(), imageRect, IntPoint());
 }
 
 void FETurbulence::dump()
diff --git a/WebCore/svg/graphics/filters/SVGFETurbulence.h b/WebCore/svg/graphics/filters/SVGFETurbulence.h
index bed0637..33e185e 100644
--- a/WebCore/svg/graphics/filters/SVGFETurbulence.h
+++ b/WebCore/svg/graphics/filters/SVGFETurbulence.h
@@ -2,6 +2,8 @@
     Copyright (C) 2004, 2005, 2006, 2007 Nikolas Zimmermann <zimmermann@kde.org>
                   2004, 2005 Rob Buis <buis@kde.org>
                   2005 Eric Seidel <eric@webkit.org>
+                  2009 Dirk Schulze <krit@webkit.org>
+                  2010 Renata Hodovan <reni@inf.u-szeged.hu>
 
     This library is free software; you can redistribute it and/or
     modify it under the terms of the GNU Library General Public
@@ -28,51 +30,71 @@
 
 namespace WebCore {
 
-    enum TurbulanceType {
-        FETURBULENCE_TYPE_UNKNOWN      = 0,
-        FETURBULENCE_TYPE_FRACTALNOISE = 1,
-        FETURBULENCE_TYPE_TURBULENCE   = 2
-    };
+enum TurbulanceType {
+    FETURBULENCE_TYPE_UNKNOWN = 0,
+    FETURBULENCE_TYPE_FRACTALNOISE = 1,
+    FETURBULENCE_TYPE_TURBULENCE = 2
+};
+
+class FETurbulence : public FilterEffect {
+public:
+    static PassRefPtr<FETurbulence> create(TurbulanceType, float, float, int, float, bool);
 
-    class FETurbulence : public FilterEffect {
-    public:
-        static PassRefPtr<FETurbulence> create(TurbulanceType, const float&, const float&, const int&, const float&,
-                bool);
+    TurbulanceType type() const;
+    void setType(TurbulanceType);
 
-        TurbulanceType type() const;
-        void setType(TurbulanceType);
+    float baseFrequencyY() const;
+    void setBaseFrequencyY(float);
 
-        float baseFrequencyY() const;
-        void setBaseFrequencyY(float);
+    float baseFrequencyX() const;
+    void setBaseFrequencyX(float);
 
-        float baseFrequencyX() const;
-        void setBaseFrequencyX(float);
+    float seed() const;
+    void setSeed(float);
 
-        float seed() const;
-        void setSeed(float);
+    int numOctaves() const;
+    void setNumOctaves(bool);
 
-        int numOctaves() const;
-        void setNumOctaves(bool);
+    bool stitchTiles() const;
+    void setStitchTiles(bool);
 
-        bool stitchTiles() const;
-        void setStitchTiles(bool);
+    void apply(Filter*);
+    void dump();
+    TextStream& externalRepresentation(TextStream&, int indent) const;
 
-        void apply(Filter*);
-        void dump();
-        TextStream& externalRepresentation(TextStream&, int indent) const;
+private:
+    static const int s_blockSize = 256;
+    static const int s_blockMask = s_blockSize - 1;
 
-    private:
-        FETurbulence(TurbulanceType, const float&, const float&, const int&, const float&,
-                bool);
+    struct PaintingData {
+        long seed;
+        int latticeSelector[2 * s_blockSize + 2];
+        float gradient[4][2 * s_blockSize + 2][2];
+        int width; // How much to subtract to wrap for stitching.
+        int height;
+        int wrapX; // Minimum value to wrap.
+        int wrapY;
+        int channel;
+        IntSize filterSize;
 
-        TurbulanceType m_type;
-        float m_baseFrequencyX;
-        float m_baseFrequencyY;
-        int m_numOctaves;
-        float m_seed;
-        bool m_stitchTiles;
+        PaintingData(long paintingSeed, const IntSize& paintingSize);
+        inline long random();
     };
 
+    FETurbulence(TurbulanceType, float, float, int, float, bool);
+
+    inline void initPaint(PaintingData&);
+    float noise2D(PaintingData&, const FloatPoint&);
+    unsigned char calculateTurbulenceValueForPoint(PaintingData&, const FloatPoint&);
+
+    TurbulanceType m_type;
+    float m_baseFrequencyX;
+    float m_baseFrequencyY;
+    int m_numOctaves;
+    float m_seed;
+    bool m_stitchTiles;
+};
+
 } // namespace WebCore
 
 #endif // ENABLE(SVG) && ENABLE(FILTERS)