gfx/2d/SVGTurbulenceRenderer-inl.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "2D.h"
   8 #include "Filters.h"
   9 #include "SIMD.h"
  10
  11 namespace mozilla {
  12 namespace gfx {
  13
  14 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
  15           typename u8x16_t>
  16 class SVGTurbulenceRenderer {
  17  public:
  18   SVGTurbulenceRenderer(const Size& aBaseFrequency, int32_t aSeed,
  19                         int aNumOctaves, const Rect& aTileRect);
  20
  21   already_AddRefed<DataSourceSurface> Render(const IntSize& aSize,
  22                                              const Point& aOffset) const;
  23
  24  private:
  25   /* The turbulence calculation code is an adapted version of what
  26      appears in the SVG 1.1 specification:
  27          http://www.w3.org/TR/SVG11/filters.html#feTurbulence
  28   */
  29
  30   struct StitchInfo {
  31     int32_t width;  // How much to subtract to wrap for stitching.
  32     int32_t height;
  33     int32_t wrapX;  // Minimum value to wrap.
  34     int32_t wrapY;
  35   };
  36
  37   const static int sBSize = 0x100;
  38   const static int sBM = 0xff;
  39   void InitFromSeed(int32_t aSeed);
  40   void AdjustBaseFrequencyForStitch(const Rect& aTileRect);
  41   IntPoint AdjustForStitch(IntPoint aLatticePoint,
  42                            const StitchInfo& aStitchInfo) const;
  43   StitchInfo CreateStitchInfo(const Rect& aTileRect) const;
  44   f32x4_t Noise2(Point aVec, const StitchInfo& aStitchInfo) const;
  45   i32x4_t Turbulence(const Point& aPoint) const;
  46   Point EquivalentNonNegativeOffset(const Point& aOffset) const;
  47
  48   Size mBaseFrequency;
  49   int32_t mNumOctaves;
  50   StitchInfo mStitchInfo;
  51   bool mStitchable;
  52   TurbulenceType mType;
  53   uint8_t mLatticeSelector[sBSize];
  54   f32x4_t mGradient[sBSize][2];
  55 };
  56
  57 namespace {
  58
  59 struct RandomNumberSource {
  60   explicit RandomNumberSource(int32_t aSeed) : mLast(SetupSeed(aSeed)) {}
  61   int32_t Next() {
  62     mLast = Random(mLast);
  63     return mLast;
  64   }
  65
  66  private:
  67   static const int32_t RAND_M = 2147483647; /* 2**31 - 1 */
  68   static const int32_t RAND_A = 16807;      /* 7**5; primitive root of m */
  69   static const int32_t RAND_Q = 127773;     /* m / a */
  70   static const int32_t RAND_R = 2836;       /* m % a */
  71
  72   /* Produces results in the range [1, 2**31 - 2].
  73      Algorithm is: r = (a * r) mod m
  74      where a = 16807 and m = 2**31 - 1 = 2147483647
  75      See [Park & Miller], CACM vol. 31 no. 10 p. 1195, Oct. 1988
  76      To test: the algorithm should produce the result 1043618065
  77      as the 10,000th generated number if the original seed is 1.
  78   */
  79
  80   static int32_t SetupSeed(int32_t aSeed) {
  81     if (aSeed <= 0) aSeed = -(aSeed % (RAND_M - 1)) + 1;
  82     if (aSeed > RAND_M - 1) aSeed = RAND_M - 1;
  83     return aSeed;
  84   }
  85
  86   static int32_t Random(int32_t aSeed) {
  87     int32_t result = RAND_A * (aSeed % RAND_Q) - RAND_R * (aSeed / RAND_Q);
  88     if (result <= 0) result += RAND_M;
  89     return result;
  90   }
  91
  92   int32_t mLast;
  93 };
  94
  95 }  // unnamed namespace
  96
  97 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
  98           typename u8x16_t>
  99 SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t, u8x16_t>::
 100     SVGTurbulenceRenderer(const Size& aBaseFrequency, int32_t aSeed,
 101                           int aNumOctaves, const Rect& aTileRect)
 102     : mBaseFrequency(aBaseFrequency),
 103       mNumOctaves(aNumOctaves),
 104       mStitchInfo(),
 105       mStitchable(false),
 106       mType(TURBULENCE_TYPE_TURBULENCE) {
 107   InitFromSeed(aSeed);
 108   if (Stitch) {
 109     AdjustBaseFrequencyForStitch(aTileRect);
 110     mStitchInfo = CreateStitchInfo(aTileRect);
 111   }
 112 }
 113
 114 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
 115           typename u8x16_t>
 116 void SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t,
 117                            u8x16_t>::InitFromSeed(int32_t aSeed) {
 118   RandomNumberSource rand(aSeed);
 119
 120   float gradient[4][sBSize][2];
 121   for (int32_t k = 0; k < 4; k++) {
 122     for (int32_t i = 0; i < sBSize; i++) {
 123       float a, b;
 124       do {
 125         a = float((rand.Next() % (sBSize + sBSize)) - sBSize) / sBSize;
 126         b = float((rand.Next() % (sBSize + sBSize)) - sBSize) / sBSize;
 127       } while (a == 0 && b == 0);
 128       float s = sqrt(a * a + b * b);
 129       gradient[k][i][0] = a / s;
 130       gradient[k][i][1] = b / s;
 131     }
 132   }
 133
 134   for (int32_t i = 0; i < sBSize; i++) {
 135     mLatticeSelector[i] = i;
 136   }
 137   for (int32_t i1 = sBSize - 1; i1 > 0; i1--) {
 138     int32_t i2 = rand.Next() % sBSize;
 139     std::swap(mLatticeSelector[i1], mLatticeSelector[i2]);
 140   }
 141
 142   for (int32_t i = 0; i < sBSize; i++) {
 143     // Contrary to the code in the spec, we build the first lattice selector
 144     // lookup into mGradient so that we don't need to do it again for every
 145     // pixel.
 146     // We also change the order of the gradient indexing so that we can process
 147     // all four color channels at the same time.
 148     uint8_t j = mLatticeSelector[i];
 149     mGradient[i][0] =
 150         simd::FromF32<f32x4_t>(gradient[2][j][0], gradient[1][j][0],
 151                                gradient[0][j][0], gradient[3][j][0]);
 152     mGradient[i][1] =
 153         simd::FromF32<f32x4_t>(gradient[2][j][1], gradient[1][j][1],
 154                                gradient[0][j][1], gradient[3][j][1]);
 155   }
 156 }
 157
 158 // Adjust aFreq such that aLength * AdjustForLength(aFreq, aLength) is integer
 159 // and as close to aLength * aFreq as possible.
 160 static inline float AdjustForLength(float aFreq, float aLength) {
 161   float lowFreq = floor(aLength * aFreq) / aLength;
 162   float hiFreq = ceil(aLength * aFreq) / aLength;
 163   if (aFreq / lowFreq < hiFreq / aFreq) {
 164     return lowFreq;
 165   }
 166   return hiFreq;
 167 }
 168
 169 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
 170           typename u8x16_t>
 171 void SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t, u8x16_t>::
 172     AdjustBaseFrequencyForStitch(const Rect& aTileRect) {
 173   mBaseFrequency =
 174       Size(AdjustForLength(mBaseFrequency.width, aTileRect.Width()),
 175            AdjustForLength(mBaseFrequency.height, aTileRect.Height()));
 176 }
 177
 178 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
 179           typename u8x16_t>
 180 typename SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t,
 181                                u8x16_t>::StitchInfo
 182 SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t,
 183                       u8x16_t>::CreateStitchInfo(const Rect& aTileRect) const {
 184   StitchInfo stitch;
 185   stitch.width =
 186       int32_t(floorf(aTileRect.Width() * mBaseFrequency.width + 0.5f));
 187   stitch.height =
 188       int32_t(floorf(aTileRect.Height() * mBaseFrequency.height + 0.5f));
 189   stitch.wrapX = int32_t(aTileRect.X() * mBaseFrequency.width) + stitch.width;
 190   stitch.wrapY = int32_t(aTileRect.Y() * mBaseFrequency.height) + stitch.height;
 191   return stitch;
 192 }
 193
 194 static MOZ_ALWAYS_INLINE Float SCurve(Float t) { return t * t * (3 - 2 * t); }
 195
 196 static MOZ_ALWAYS_INLINE Point SCurve(Point t) {
 197   return Point(SCurve(t.x), SCurve(t.y));
 198 }
 199
 200 template <typename f32x4_t>
 201 static MOZ_ALWAYS_INLINE f32x4_t BiMix(const f32x4_t& aa, const f32x4_t& ab,
 202                                        const f32x4_t& ba, const f32x4_t& bb,
 203                                        Point s) {
 204   return simd::MixF32(simd::MixF32(aa, ab, s.x), simd::MixF32(ba, bb, s.x),
 205                       s.y);
 206 }
 207
 208 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
 209           typename u8x16_t>
 210 IntPoint
 211 SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t, u8x16_t>::AdjustForStitch(
 212     IntPoint aLatticePoint, const StitchInfo& aStitchInfo) const {
 213   if (Stitch) {
 214     if (aLatticePoint.x >= aStitchInfo.wrapX) {
 215       aLatticePoint.x -= aStitchInfo.width;
 216     }
 217     if (aLatticePoint.y >= aStitchInfo.wrapY) {
 218       aLatticePoint.y -= aStitchInfo.height;
 219     }
 220   }
 221   return aLatticePoint;
 222 }
 223
 224 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
 225           typename u8x16_t>
 226 f32x4_t SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t, u8x16_t>::Noise2(
 227     Point aVec, const StitchInfo& aStitchInfo) const {
 228   // aVec is guaranteed to be non-negative, so casting to int32_t always
 229   // rounds towards negative infinity.
 230   IntPoint topLeftLatticePoint(int32_t(aVec.x), int32_t(aVec.y));
 231   Point r = aVec - topLeftLatticePoint;  // fractional offset
 232
 233   IntPoint b0 = AdjustForStitch(topLeftLatticePoint, aStitchInfo);
 234   IntPoint b1 = AdjustForStitch(b0 + IntPoint(1, 1), aStitchInfo);
 235
 236   uint8_t i = mLatticeSelector[b0.x & sBM];
 237   uint8_t j = mLatticeSelector[b1.x & sBM];
 238
 239   const f32x4_t* qua = mGradient[(i + b0.y) & sBM];
 240   const f32x4_t* qub = mGradient[(i + b1.y) & sBM];
 241   const f32x4_t* qva = mGradient[(j + b0.y) & sBM];
 242   const f32x4_t* qvb = mGradient[(j + b1.y) & sBM];
 243
 244   return BiMix(simd::WSumF32(qua[0], qua[1], r.x, r.y),
 245                simd::WSumF32(qva[0], qva[1], r.x - 1.f, r.y),
 246                simd::WSumF32(qub[0], qub[1], r.x, r.y - 1.f),
 247                simd::WSumF32(qvb[0], qvb[1], r.x - 1.f, r.y - 1.f), SCurve(r));
 248 }
 249
 250 template <typename f32x4_t, typename i32x4_t, typename u8x16_t>
 251 static inline i32x4_t ColorToBGRA(f32x4_t aUnscaledUnpreFloat) {
 252   // Color is an unpremultiplied float vector where 1.0f means white. We will
 253   // convert it into an integer vector where 255 means white.
 254   f32x4_t alpha = simd::SplatF32<3>(aUnscaledUnpreFloat);
 255   f32x4_t scaledUnpreFloat =
 256       simd::MulF32(aUnscaledUnpreFloat, simd::FromF32<f32x4_t>(255));
 257   i32x4_t scaledUnpreInt = simd::F32ToI32(scaledUnpreFloat);
 258
 259   // Multiply all channels with alpha.
 260   i32x4_t scaledPreInt = simd::F32ToI32(simd::MulF32(scaledUnpreFloat, alpha));
 261
 262   // Use the premultiplied color channels and the unpremultiplied alpha channel.
 263   i32x4_t alphaMask = simd::From32<i32x4_t>(0, 0, 0, -1);
 264   return simd::Pick(alphaMask, scaledPreInt, scaledUnpreInt);
 265 }
 266
 267 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
 268           typename u8x16_t>
 269 i32x4_t SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t,
 270                               u8x16_t>::Turbulence(const Point& aPoint) const {
 271   StitchInfo stitchInfo = mStitchInfo;
 272   f32x4_t sum = simd::FromF32<f32x4_t>(0);
 273   Point vec(aPoint.x * mBaseFrequency.width, aPoint.y * mBaseFrequency.height);
 274   f32x4_t ratio = simd::FromF32<f32x4_t>(1);
 275
 276   for (int octave = 0; octave < mNumOctaves; octave++) {
 277     f32x4_t thisOctave = Noise2(vec, stitchInfo);
 278     if (Type == TURBULENCE_TYPE_TURBULENCE) {
 279       thisOctave = simd::AbsF32(thisOctave);
 280     }
 281     sum = simd::AddF32(sum, simd::DivF32(thisOctave, ratio));
 282     vec = vec * 2;
 283     ratio = simd::MulF32(ratio, simd::FromF32<f32x4_t>(2));
 284
 285     if (Stitch) {
 286       stitchInfo.width *= 2;
 287       stitchInfo.wrapX *= 2;
 288       stitchInfo.height *= 2;
 289       stitchInfo.wrapY *= 2;
 290     }
 291   }
 292
 293   if (Type == TURBULENCE_TYPE_FRACTAL_NOISE) {
 294     sum = simd::DivF32(simd::AddF32(sum, simd::FromF32<f32x4_t>(1)),
 295                        simd::FromF32<f32x4_t>(2));
 296   }
 297   return ColorToBGRA<f32x4_t, i32x4_t, u8x16_t>(sum);
 298 }
 299
 300 static inline Float MakeNonNegative(Float aValue, Float aIncrementSize) {
 301   if (aIncrementSize == 0) {
 302     return 0;
 303   }
 304   if (aValue >= 0) {
 305     return aValue;
 306   }
 307   return aValue + ceilf(-aValue / aIncrementSize) * aIncrementSize;
 308 }
 309
 310 static inline Float FiniteDivide(Float aValue, Float aDivisor) {
 311   if (aDivisor == 0) {
 312     return 0;
 313   }
 314   return aValue / aDivisor;
 315 }
 316
 317 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
 318           typename u8x16_t>
 319 Point SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t, u8x16_t>::
 320     EquivalentNonNegativeOffset(const Point& aOffset) const {
 321   Size basePeriod = Stitch ? Size(mStitchInfo.width, mStitchInfo.height)
 322                            : Size(sBSize, sBSize);
 323   Size repeatingSize(FiniteDivide(basePeriod.width, mBaseFrequency.width),
 324                      FiniteDivide(basePeriod.height, mBaseFrequency.height));
 325   return Point(MakeNonNegative(aOffset.x, repeatingSize.width),
 326                MakeNonNegative(aOffset.y, repeatingSize.height));
 327 }
 328
 329 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
 330           typename u8x16_t>
 331 already_AddRefed<DataSourceSurface>
 332 SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t, u8x16_t>::Render(
 333     const IntSize& aSize, const Point& aOffset) const {
 334   RefPtr<DataSourceSurface> target =
 335       Factory::CreateDataSourceSurface(aSize, SurfaceFormat::B8G8R8A8);
 336   if (!target) {
 337     return nullptr;
 338   }
 339
 340   DataSourceSurface::ScopedMap map(target, DataSourceSurface::READ_WRITE);
 341   uint8_t* targetData = map.GetData();
 342   uint32_t stride = map.GetStride();
 343
 344   Point startOffset = EquivalentNonNegativeOffset(aOffset);
 345
 346   for (int32_t y = 0; y < aSize.height; y++) {
 347     for (int32_t x = 0; x < aSize.width; x += 4) {
 348       int32_t targIndex = y * stride + x * 4;
 349       i32x4_t a = Turbulence(startOffset + Point(x, y));
 350       i32x4_t b = Turbulence(startOffset + Point(x + 1, y));
 351       i32x4_t c = Turbulence(startOffset + Point(x + 2, y));
 352       i32x4_t d = Turbulence(startOffset + Point(x + 3, y));
 353       u8x16_t result1234 = simd::PackAndSaturate32To8(a, b, c, d);
 354       simd::Store8(&targetData[targIndex], result1234);
 355     }
 356   }
 357
 358   return target.forget();
 359 }
 360
 361 }  // namespace gfx
 362 }  // namespace mozilla