SVGTurbulenceRenderer-inl.h (13296B)
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