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), mNumOctaves(aNumOctaves) {
103 InitFromSeed(aSeed);
104 if (Stitch) {
105 AdjustBaseFrequencyForStitch(aTileRect);
106 mStitchInfo = CreateStitchInfo(aTileRect);
107 }
108 }
109
110 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
111 typename u8x16_t>
112 void SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t,
InitFromSeed(int32_t aSeed)113 u8x16_t>::InitFromSeed(int32_t aSeed) {
114 RandomNumberSource rand(aSeed);
115
116 float gradient[4][sBSize][2];
117 for (int32_t k = 0; k < 4; k++) {
118 for (int32_t i = 0; i < sBSize; i++) {
119 float a, b;
120 do {
121 a = float((rand.Next() % (sBSize + sBSize)) - sBSize) / sBSize;
122 b = float((rand.Next() % (sBSize + sBSize)) - sBSize) / sBSize;
123 } while (a == 0 && b == 0);
124 float s = sqrt(a * a + b * b);
125 gradient[k][i][0] = a / s;
126 gradient[k][i][1] = b / s;
127 }
128 }
129
130 for (int32_t i = 0; i < sBSize; i++) {
131 mLatticeSelector[i] = i;
132 }
133 for (int32_t i1 = sBSize - 1; i1 > 0; i1--) {
134 int32_t i2 = rand.Next() % sBSize;
135 Swap(mLatticeSelector[i1], mLatticeSelector[i2]);
136 }
137
138 for (int32_t i = 0; i < sBSize; i++) {
139 // Contrary to the code in the spec, we build the first lattice selector
140 // lookup into mGradient so that we don't need to do it again for every
141 // pixel.
142 // We also change the order of the gradient indexing so that we can process
143 // all four color channels at the same time.
144 uint8_t j = mLatticeSelector[i];
145 mGradient[i][0] =
146 simd::FromF32<f32x4_t>(gradient[2][j][0], gradient[1][j][0],
147 gradient[0][j][0], gradient[3][j][0]);
148 mGradient[i][1] =
149 simd::FromF32<f32x4_t>(gradient[2][j][1], gradient[1][j][1],
150 gradient[0][j][1], gradient[3][j][1]);
151 }
152 }
153
154 // Adjust aFreq such that aLength * AdjustForLength(aFreq, aLength) is integer
155 // and as close to aLength * aFreq as possible.
AdjustForLength(float aFreq,float aLength)156 static inline float AdjustForLength(float aFreq, float aLength) {
157 float lowFreq = floor(aLength * aFreq) / aLength;
158 float hiFreq = ceil(aLength * aFreq) / aLength;
159 if (aFreq / lowFreq < hiFreq / aFreq) {
160 return lowFreq;
161 }
162 return hiFreq;
163 }
164
165 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
166 typename u8x16_t>
167 void SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t, u8x16_t>::
AdjustBaseFrequencyForStitch(const Rect & aTileRect)168 AdjustBaseFrequencyForStitch(const Rect &aTileRect) {
169 mBaseFrequency =
170 Size(AdjustForLength(mBaseFrequency.width, aTileRect.Width()),
171 AdjustForLength(mBaseFrequency.height, aTileRect.Height()));
172 }
173
174 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
175 typename u8x16_t>
176 typename SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t,
177 u8x16_t>::StitchInfo
178 SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t,
CreateStitchInfo(const Rect & aTileRect)179 u8x16_t>::CreateStitchInfo(const Rect &aTileRect) const {
180 StitchInfo stitch;
181 stitch.width =
182 int32_t(floorf(aTileRect.Width() * mBaseFrequency.width + 0.5f));
183 stitch.height =
184 int32_t(floorf(aTileRect.Height() * mBaseFrequency.height + 0.5f));
185 stitch.wrapX = int32_t(aTileRect.X() * mBaseFrequency.width) + stitch.width;
186 stitch.wrapY = int32_t(aTileRect.Y() * mBaseFrequency.height) + stitch.height;
187 return stitch;
188 }
189
SCurve(Float t)190 static MOZ_ALWAYS_INLINE Float SCurve(Float t) { return t * t * (3 - 2 * t); }
191
SCurve(Point t)192 static MOZ_ALWAYS_INLINE Point SCurve(Point t) {
193 return Point(SCurve(t.x), SCurve(t.y));
194 }
195
196 template <typename f32x4_t>
BiMix(const f32x4_t & aa,const f32x4_t & ab,const f32x4_t & ba,const f32x4_t & bb,Point s)197 static MOZ_ALWAYS_INLINE f32x4_t BiMix(const f32x4_t &aa, const f32x4_t &ab,
198 const f32x4_t &ba, const f32x4_t &bb,
199 Point s) {
200 return simd::MixF32(simd::MixF32(aa, ab, s.x), simd::MixF32(ba, bb, s.x),
201 s.y);
202 }
203
204 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
205 typename u8x16_t>
206 IntPoint
AdjustForStitch(IntPoint aLatticePoint,const StitchInfo & aStitchInfo)207 SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t, u8x16_t>::AdjustForStitch(
208 IntPoint aLatticePoint, const StitchInfo &aStitchInfo) const {
209 if (Stitch) {
210 if (aLatticePoint.x >= aStitchInfo.wrapX) {
211 aLatticePoint.x -= aStitchInfo.width;
212 }
213 if (aLatticePoint.y >= aStitchInfo.wrapY) {
214 aLatticePoint.y -= aStitchInfo.height;
215 }
216 }
217 return aLatticePoint;
218 }
219
220 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
221 typename u8x16_t>
Noise2(Point aVec,const StitchInfo & aStitchInfo)222 f32x4_t SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t, u8x16_t>::Noise2(
223 Point aVec, const StitchInfo &aStitchInfo) const {
224 // aVec is guaranteed to be non-negative, so casting to int32_t always
225 // rounds towards negative infinity.
226 IntPoint topLeftLatticePoint(int32_t(aVec.x), int32_t(aVec.y));
227 Point r = aVec - topLeftLatticePoint; // fractional offset
228
229 IntPoint b0 = AdjustForStitch(topLeftLatticePoint, aStitchInfo);
230 IntPoint b1 = AdjustForStitch(b0 + IntPoint(1, 1), aStitchInfo);
231
232 uint8_t i = mLatticeSelector[b0.x & sBM];
233 uint8_t j = mLatticeSelector[b1.x & sBM];
234
235 const f32x4_t *qua = mGradient[(i + b0.y) & sBM];
236 const f32x4_t *qub = mGradient[(i + b1.y) & sBM];
237 const f32x4_t *qva = mGradient[(j + b0.y) & sBM];
238 const f32x4_t *qvb = mGradient[(j + b1.y) & sBM];
239
240 return BiMix(simd::WSumF32(qua[0], qua[1], r.x, r.y),
241 simd::WSumF32(qva[0], qva[1], r.x - 1.f, r.y),
242 simd::WSumF32(qub[0], qub[1], r.x, r.y - 1.f),
243 simd::WSumF32(qvb[0], qvb[1], r.x - 1.f, r.y - 1.f), SCurve(r));
244 }
245
246 template <typename f32x4_t, typename i32x4_t, typename u8x16_t>
ColorToBGRA(f32x4_t aUnscaledUnpreFloat)247 static inline i32x4_t ColorToBGRA(f32x4_t aUnscaledUnpreFloat) {
248 // Color is an unpremultiplied float vector where 1.0f means white. We will
249 // convert it into an integer vector where 255 means white.
250 f32x4_t alpha = simd::SplatF32<3>(aUnscaledUnpreFloat);
251 f32x4_t scaledUnpreFloat =
252 simd::MulF32(aUnscaledUnpreFloat, simd::FromF32<f32x4_t>(255));
253 i32x4_t scaledUnpreInt = simd::F32ToI32(scaledUnpreFloat);
254
255 // Multiply all channels with alpha.
256 i32x4_t scaledPreInt = simd::F32ToI32(simd::MulF32(scaledUnpreFloat, alpha));
257
258 // Use the premultiplied color channels and the unpremultiplied alpha channel.
259 i32x4_t alphaMask = simd::From32<i32x4_t>(0, 0, 0, -1);
260 return simd::Pick(alphaMask, scaledPreInt, scaledUnpreInt);
261 }
262
263 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
264 typename u8x16_t>
265 i32x4_t SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t,
Turbulence(const Point & aPoint)266 u8x16_t>::Turbulence(const Point &aPoint) const {
267 StitchInfo stitchInfo = mStitchInfo;
268 f32x4_t sum = simd::FromF32<f32x4_t>(0);
269 Point vec(aPoint.x * mBaseFrequency.width, aPoint.y * mBaseFrequency.height);
270 f32x4_t ratio = simd::FromF32<f32x4_t>(1);
271
272 for (int octave = 0; octave < mNumOctaves; octave++) {
273 f32x4_t thisOctave = Noise2(vec, stitchInfo);
274 if (Type == TURBULENCE_TYPE_TURBULENCE) {
275 thisOctave = simd::AbsF32(thisOctave);
276 }
277 sum = simd::AddF32(sum, simd::DivF32(thisOctave, ratio));
278 vec = vec * 2;
279 ratio = simd::MulF32(ratio, simd::FromF32<f32x4_t>(2));
280
281 if (Stitch) {
282 stitchInfo.width *= 2;
283 stitchInfo.wrapX *= 2;
284 stitchInfo.height *= 2;
285 stitchInfo.wrapY *= 2;
286 }
287 }
288
289 if (Type == TURBULENCE_TYPE_FRACTAL_NOISE) {
290 sum = simd::DivF32(simd::AddF32(sum, simd::FromF32<f32x4_t>(1)),
291 simd::FromF32<f32x4_t>(2));
292 }
293 return ColorToBGRA<f32x4_t, i32x4_t, u8x16_t>(sum);
294 }
295
MakeNonNegative(Float aValue,Float aIncrementSize)296 static inline Float MakeNonNegative(Float aValue, Float aIncrementSize) {
297 if (aValue >= 0) {
298 return aValue;
299 }
300 return aValue + ceilf(-aValue / aIncrementSize) * aIncrementSize;
301 }
302
303 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
304 typename u8x16_t>
305 Point SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t, u8x16_t>::
EquivalentNonNegativeOffset(const Point & aOffset)306 EquivalentNonNegativeOffset(const Point &aOffset) const {
307 Size basePeriod = Stitch ? Size(mStitchInfo.width, mStitchInfo.height)
308 : Size(sBSize, sBSize);
309 Size repeatingSize(basePeriod.width / mBaseFrequency.width,
310 basePeriod.height / mBaseFrequency.height);
311 return Point(MakeNonNegative(aOffset.x, repeatingSize.width),
312 MakeNonNegative(aOffset.y, repeatingSize.height));
313 }
314
315 template <TurbulenceType Type, bool Stitch, typename f32x4_t, typename i32x4_t,
316 typename u8x16_t>
317 already_AddRefed<DataSourceSurface>
Render(const IntSize & aSize,const Point & aOffset)318 SVGTurbulenceRenderer<Type, Stitch, f32x4_t, i32x4_t, u8x16_t>::Render(
319 const IntSize &aSize, const Point &aOffset) const {
320 RefPtr<DataSourceSurface> target =
321 Factory::CreateDataSourceSurface(aSize, SurfaceFormat::B8G8R8A8);
322 if (!target) {
323 return nullptr;
324 }
325
326 DataSourceSurface::ScopedMap map(target, DataSourceSurface::READ_WRITE);
327 uint8_t *targetData = map.GetData();
328 uint32_t stride = map.GetStride();
329
330 Point startOffset = EquivalentNonNegativeOffset(aOffset);
331
332 for (int32_t y = 0; y < aSize.height; y++) {
333 for (int32_t x = 0; x < aSize.width; x += 4) {
334 int32_t targIndex = y * stride + x * 4;
335 i32x4_t a = Turbulence(startOffset + Point(x, y));
336 i32x4_t b = Turbulence(startOffset + Point(x + 1, y));
337 i32x4_t c = Turbulence(startOffset + Point(x + 2, y));
338 i32x4_t d = Turbulence(startOffset + Point(x + 3, y));
339 u8x16_t result1234 = simd::PackAndSaturate32To8(a, b, c, d);
340 simd::Store8(&targetData[targIndex], result1234);
341 }
342 }
343
344 return target.forget();
345 }
346
347 } // namespace gfx
348 } // namespace mozilla
349