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 {
RandomNumberSourceRandomNumberSource60 explicit RandomNumberSource(int32_t aSeed) : mLast(SetupSeed(aSeed)) {}
NextRandomNumberSource61 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
SetupSeedRandomNumberSource80 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
RandomRandomNumberSource86 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>::
SVGTurbulenceRenderer(const Size & aBaseFrequency,int32_t aSeed,int aNumOctaves,const Rect & aTileRect)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,
InitFromSeed(int32_t aSeed)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.
AdjustForLength(float aFreq,float aLength)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>::
AdjustBaseFrequencyForStitch(const Rect & aTileRect)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,
CreateStitchInfo(const Rect & aTileRect)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
SCurve(Float t)194 static MOZ_ALWAYS_INLINE Float SCurve(Float t) { return t * t * (3 - 2 * t); }
195
SCurve(Point t)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>
BiMix(const f32x4_t & aa,const f32x4_t & ab,const f32x4_t & ba,const f32x4_t & bb,Point s)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
AdjustForStitch(IntPoint aLatticePoint,const StitchInfo & aStitchInfo)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>
Noise2(Point aVec,const StitchInfo & aStitchInfo)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>
ColorToBGRA(f32x4_t aUnscaledUnpreFloat)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,
Turbulence(const Point & aPoint)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
MakeNonNegative(Float aValue,Float aIncrementSize)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
FiniteDivide(Float aValue,Float aDivisor)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>::
EquivalentNonNegativeOffset(const Point & aOffset)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>
Render(const IntSize & aSize,const Point & aOffset)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
363