1
use cssparser::Parser;
2
use markup5ever::{expanded_name, local_name, namespace_url, ns};
3

            
4
use crate::document::AcquiredNodes;
5
use crate::drawing_ctx::DrawingCtx;
6
use crate::element::{set_attribute, ElementTrait};
7
use crate::error::*;
8
use crate::node::{CascadedValues, Node};
9
use crate::parse_identifiers;
10
use crate::parsers::{NumberOptionalNumber, Parse, ParseValue};
11
use crate::properties::ColorInterpolationFilters;
12
use crate::rect::IRect;
13
use crate::rsvg_log;
14
use crate::session::Session;
15
use crate::surface_utils::{
16
    shared_surface::{ExclusiveImageSurface, SurfaceType},
17
    ImageSurfaceDataExt, Pixel, PixelOps,
18
};
19
use crate::util::clamp;
20
use crate::xml::Attributes;
21

            
22
use super::bounds::BoundsBuilder;
23
use super::context::{FilterContext, FilterOutput};
24
use super::{
25
    FilterEffect, FilterError, FilterResolveError, Primitive, PrimitiveParams, ResolvedPrimitive,
26
};
27

            
28
/// Limit the `numOctaves` parameter to avoid unbounded CPU consumption.
29
///
30
/// https://drafts.fxtf.org/filter-effects/#element-attrdef-feturbulence-numoctaves
31
const MAX_OCTAVES: i32 = 9;
32

            
33
/// Enumeration of the tile stitching modes.
34
298375
#[derive(Debug, Default, Clone, Copy, Eq, PartialEq, Hash)]
35
enum StitchTiles {
36
    Stitch,
37
    #[default]
38
19
    NoStitch,
39
}
40

            
41
/// Enumeration of the noise types.
42
769069
#[derive(Debug, Default, Clone, Copy, Eq, PartialEq, Hash)]
43
enum NoiseType {
44
    FractalNoise,
45
    #[default]
46
19
    Turbulence,
47
}
48

            
49
/// The `feTurbulence` filter primitive.
50
19
#[derive(Default)]
51
pub struct FeTurbulence {
52
19
    base: Primitive,
53
19
    params: Turbulence,
54
}
55

            
56
/// Resolved `feTurbulence` primitive for rendering.
57
38
#[derive(Clone)]
58
pub struct Turbulence {
59
19
    base_frequency: NumberOptionalNumber<f64>,
60
19
    num_octaves: i32,
61
19
    seed: f64,
62
19
    stitch_tiles: StitchTiles,
63
19
    type_: NoiseType,
64
19
    color_interpolation_filters: ColorInterpolationFilters,
65
}
66

            
67
impl Default for Turbulence {
68
    /// Constructs a new `Turbulence` with empty properties.
69
    #[inline]
70
19
    fn default() -> Turbulence {
71
19
        Turbulence {
72
19
            base_frequency: NumberOptionalNumber(0.0, 0.0),
73
            num_octaves: 1,
74
            seed: 0.0,
75
19
            stitch_tiles: Default::default(),
76
19
            type_: Default::default(),
77
19
            color_interpolation_filters: Default::default(),
78
        }
79
19
    }
80
}
81

            
82
impl ElementTrait for FeTurbulence {
83
19
    fn set_attributes(&mut self, attrs: &Attributes, session: &Session) {
84
19
        self.base.parse_no_inputs(attrs, session);
85

            
86
74
        for (attr, value) in attrs.iter() {
87
55
            match attr.expanded() {
88
                expanded_name!("", "baseFrequency") => {
89
18
                    set_attribute(&mut self.params.base_frequency, attr.parse(value), session);
90
                }
91
                expanded_name!("", "numOctaves") => {
92
8
                    set_attribute(&mut self.params.num_octaves, attr.parse(value), session);
93
9
                    if self.params.num_octaves > MAX_OCTAVES {
94
1
                        let n = self.params.num_octaves;
95
1
                        rsvg_log!(
96
                            session,
97
                            "ignoring numOctaves={n}, setting it to {MAX_OCTAVES}"
98
                        );
99
1
                        self.params.num_octaves = MAX_OCTAVES;
100
                    }
101
                }
102
                // Yes, seed needs to be parsed as a number and then truncated.
103
                expanded_name!("", "seed") => {
104
11
                    set_attribute(&mut self.params.seed, attr.parse(value), session);
105
                }
106
                expanded_name!("", "stitchTiles") => {
107
                    set_attribute(&mut self.params.stitch_tiles, attr.parse(value), session);
108
                }
109
                expanded_name!("", "type") => {
110
17
                    set_attribute(&mut self.params.type_, attr.parse(value), session)
111
                }
112
                _ => (),
113
            }
114
55
        }
115
19
    }
116
}
117

            
118
// Produces results in the range [1, 2**31 - 2].
119
// Algorithm is: r = (a * r) mod m
120
// where a = 16807 and m = 2**31 - 1 = 2147483647
121
// See [Park & Miller], CACM vol. 31 no. 10 p. 1195, Oct. 1988
122
// To test: the algorithm should produce the result 1043618065
123
// as the 10,000th generated number if the original seed is 1.
124
const RAND_M: i32 = 2147483647; // 2**31 - 1
125
const RAND_A: i32 = 16807; // 7**5; primitive root of m
126
const RAND_Q: i32 = 127773; // m / a
127
const RAND_R: i32 = 2836; // m % a
128

            
129
20
fn setup_seed(mut seed: i32) -> i32 {
130
38
    if seed <= 0 {
131
18
        seed = -(seed % (RAND_M - 1)) + 1;
132
    }
133
20
    if seed > RAND_M - 1 {
134
        seed = RAND_M - 1;
135
    }
136
20
    seed
137
20
}
138

            
139
53757
fn random(seed: i32) -> i32 {
140
53757
    let mut result = RAND_A * (seed % RAND_Q) - RAND_R * (seed / RAND_Q);
141
53757
    if result <= 0 {
142
591
        result += RAND_M;
143
    }
144
53757
    result
145
53757
}
146

            
147
const B_SIZE: usize = 0x100;
148
const PERLIN_N: i32 = 0x1000;
149

            
150
#[derive(Clone, Copy)]
151
struct NoiseGenerator {
152
    base_frequency: (f64, f64),
153
    num_octaves: i32,
154
    stitch_tiles: StitchTiles,
155
    type_: NoiseType,
156

            
157
    tile_width: f64,
158
    tile_height: f64,
159

            
160
    lattice_selector: [usize; B_SIZE + B_SIZE + 2],
161
    gradient: [[[f64; 2]; B_SIZE + B_SIZE + 2]; 4],
162
}
163

            
164
#[derive(Clone, Copy)]
165
struct StitchInfo {
166
    width: usize, // How much to subtract to wrap for stitching.
167
    height: usize,
168
    wrap_x: usize, // Minimum value to wrap.
169
    wrap_y: usize,
170
}
171

            
172
impl NoiseGenerator {
173
19
    fn new(
174
        seed: i32,
175
        base_frequency: (f64, f64),
176
        num_octaves: i32,
177
        type_: NoiseType,
178
        stitch_tiles: StitchTiles,
179
        tile_width: f64,
180
        tile_height: f64,
181
    ) -> Self {
182
19
        let mut rv = Self {
183
            base_frequency,
184
            num_octaves,
185
            type_,
186
            stitch_tiles,
187

            
188
            tile_width,
189
            tile_height,
190

            
191
19
            lattice_selector: [0; B_SIZE + B_SIZE + 2],
192
57
            gradient: [[[0.0; 2]; B_SIZE + B_SIZE + 2]; 4],
193
        };
194

            
195
19
        let mut seed = setup_seed(seed);
196

            
197
95
        for k in 0..4 {
198
19532
            for i in 0..B_SIZE {
199
19456
                rv.lattice_selector[i] = i;
200
58368
                for j in 0..2 {
201
38912
                    seed = random(seed);
202
38912
                    rv.gradient[k][i][j] =
203
38912
                        ((seed % (B_SIZE + B_SIZE) as i32) - B_SIZE as i32) as f64 / B_SIZE as f64;
204
                }
205
38912
                let s = (rv.gradient[k][i][0] * rv.gradient[k][i][0]
206
19456
                    + rv.gradient[k][i][1] * rv.gradient[k][i][1])
207
                    .sqrt();
208
19456
                rv.gradient[k][i][0] /= s;
209
19456
                rv.gradient[k][i][1] /= s;
210
            }
211
        }
212
4864
        for i in (1..B_SIZE).rev() {
213
4845
            let k = rv.lattice_selector[i];
214
4845
            seed = random(seed);
215
4845
            let j = seed as usize % B_SIZE;
216
4845
            rv.lattice_selector[i] = rv.lattice_selector[j];
217
4845
            rv.lattice_selector[j] = k;
218
        }
219
4921
        for i in 0..B_SIZE + 2 {
220
4902
            rv.lattice_selector[B_SIZE + i] = rv.lattice_selector[i];
221
24510
            for k in 0..4 {
222
58824
                for j in 0..2 {
223
39216
                    rv.gradient[k][B_SIZE + i][j] = rv.gradient[k][i][j];
224
                }
225
            }
226
        }
227

            
228
19
        rv
229
19
    }
230

            
231
771332
    fn noise2(&self, color_channel: usize, vec: [f64; 2], stitch_info: Option<StitchInfo>) -> f64 {
232
        #![allow(clippy::many_single_char_names)]
233

            
234
        const BM: usize = 0xff;
235

            
236
1537751
        let s_curve = |t| t * t * (3. - 2. * t);
237
3081925
        let lerp = |t, a, b| a + t * (b - a);
238

            
239
771332
        let t = vec[0] + f64::from(PERLIN_N);
240
771332
        let mut bx0 = t as usize;
241
771332
        let mut bx1 = bx0 + 1;
242
771332
        let rx0 = t.fract();
243
771332
        let rx1 = rx0 - 1.0;
244
771332
        let t = vec[1] + f64::from(PERLIN_N);
245
771332
        let mut by0 = t as usize;
246
771332
        let mut by1 = by0 + 1;
247
771332
        let ry0 = t.fract();
248
771332
        let ry1 = ry0 - 1.0;
249

            
250
        // If stitching, adjust lattice points accordingly.
251
771332
        if let Some(stitch_info) = stitch_info {
252
            if bx0 >= stitch_info.wrap_x {
253
                bx0 -= stitch_info.width;
254
            }
255
            if bx1 >= stitch_info.wrap_x {
256
                bx1 -= stitch_info.width;
257
            }
258
            if by0 >= stitch_info.wrap_y {
259
                by0 -= stitch_info.height;
260
            }
261
            if by1 >= stitch_info.wrap_y {
262
                by1 -= stitch_info.height;
263
            }
264
        }
265
771332
        bx0 &= BM;
266
771332
        bx1 &= BM;
267
771332
        by0 &= BM;
268
771332
        by1 &= BM;
269
771332
        let i = self.lattice_selector[bx0];
270
771332
        let j = self.lattice_selector[bx1];
271
771332
        let b00 = self.lattice_selector[i + by0];
272
771332
        let b10 = self.lattice_selector[j + by0];
273
771332
        let b01 = self.lattice_selector[i + by1];
274
771332
        let b11 = self.lattice_selector[j + by1];
275
771332
        let sx = s_curve(rx0);
276
771332
        let sy = s_curve(ry0);
277
771332
        let q = self.gradient[color_channel][b00];
278
771332
        let u = rx0 * q[0] + ry0 * q[1];
279
771332
        let q = self.gradient[color_channel][b10];
280
771332
        let v = rx1 * q[0] + ry0 * q[1];
281
771332
        let a = lerp(sx, u, v);
282
771332
        let q = self.gradient[color_channel][b01];
283
771332
        let u = rx0 * q[0] + ry1 * q[1];
284
771332
        let q = self.gradient[color_channel][b11];
285
771332
        let v = rx1 * q[0] + ry1 * q[1];
286
771332
        let b = lerp(sx, u, v);
287
771332
        lerp(sy, a, b)
288
771332
    }
289

            
290
298936
    fn turbulence(&self, color_channel: usize, point: [f64; 2], tile_x: f64, tile_y: f64) -> f64 {
291
298936
        let mut stitch_info = None;
292
298936
        let mut base_frequency = self.base_frequency;
293

            
294
        // Adjust the base frequencies if necessary for stitching.
295
298936
        if self.stitch_tiles == StitchTiles::Stitch {
296
            // When stitching tiled turbulence, the frequencies must be adjusted
297
            // so that the tile borders will be continuous.
298
            if base_frequency.0 != 0.0 {
299
                let freq_lo = (self.tile_width * base_frequency.0).floor() / self.tile_width;
300
                let freq_hi = (self.tile_width * base_frequency.0).ceil() / self.tile_width;
301
                if base_frequency.0 / freq_lo < freq_hi / base_frequency.0 {
302
                    base_frequency.0 = freq_lo;
303
                } else {
304
                    base_frequency.0 = freq_hi;
305
                }
306
            }
307
            if base_frequency.1 != 0.0 {
308
                let freq_lo = (self.tile_height * base_frequency.1).floor() / self.tile_height;
309
                let freq_hi = (self.tile_height * base_frequency.1).ceil() / self.tile_height;
310
                if base_frequency.1 / freq_lo < freq_hi / base_frequency.1 {
311
                    base_frequency.1 = freq_lo;
312
                } else {
313
                    base_frequency.1 = freq_hi;
314
                }
315
            }
316

            
317
            // Set up initial stitch values.
318
            let width = (self.tile_width * base_frequency.0 + 0.5) as usize;
319
            let height = (self.tile_height * base_frequency.1 + 0.5) as usize;
320
            stitch_info = Some(StitchInfo {
321
                width,
322
                wrap_x: (tile_x * base_frequency.0) as usize + PERLIN_N as usize + width,
323
                height,
324
                wrap_y: (tile_y * base_frequency.1) as usize + PERLIN_N as usize + height,
325
            });
326
        }
327

            
328
298936
        let mut sum = 0.0;
329
298936
        let mut vec = [point[0] * base_frequency.0, point[1] * base_frequency.1];
330
298936
        let mut ratio = 1.0;
331
1067706
        for _ in 0..self.num_octaves {
332
768770
            if self.type_ == NoiseType::FractalNoise {
333
270000
                sum += self.noise2(color_channel, vec, stitch_info) / ratio;
334
            } else {
335
498770
                sum += (self.noise2(color_channel, vec, stitch_info)).abs() / ratio;
336
            }
337
768770
            vec[0] *= 2.0;
338
768770
            vec[1] *= 2.0;
339
768770
            ratio *= 2.0;
340
768770
            if let Some(stitch_info) = stitch_info.as_mut() {
341
                // Update stitch values. Subtracting PerlinN before the multiplication and
342
                // adding it afterward simplifies to subtracting it once.
343
                stitch_info.width *= 2;
344
                stitch_info.wrap_x = 2 * stitch_info.wrap_x - PERLIN_N as usize;
345
                stitch_info.height *= 2;
346
                stitch_info.wrap_y = 2 * stitch_info.wrap_y - PERLIN_N as usize;
347
            }
348
        }
349
298936
        sum
350
298936
    }
351
}
352

            
353
impl Turbulence {
354
19
    pub fn render(
355
        &self,
356
        bounds_builder: BoundsBuilder,
357
        ctx: &FilterContext,
358
        _acquired_nodes: &mut AcquiredNodes<'_>,
359
        _draw_ctx: &mut DrawingCtx,
360
    ) -> Result<FilterOutput, FilterError> {
361
19
        let bounds: IRect = bounds_builder.compute(ctx).clipped.into();
362

            
363
19
        let affine = ctx.paffine().invert().unwrap();
364

            
365
19
        let seed = clamp(
366
19
            self.seed.trunc(), // per the spec, round towards zero
367
19
            f64::from(i32::min_value()),
368
19
            f64::from(i32::max_value()),
369
        ) as i32;
370

            
371
        // "Negative values are unsupported" -> set to the initial value which is 0.0
372
        //
373
        // https://drafts.fxtf.org/filter-effects/#element-attrdef-feturbulence-basefrequency
374
        let base_frequency = {
375
19
            let NumberOptionalNumber(base_freq_x, base_freq_y) = self.base_frequency;
376
19
            let x = base_freq_x.max(0.0);
377
19
            let y = base_freq_y.max(0.0);
378
19
            (x, y)
379
        };
380

            
381
19
        let noise_generator = NoiseGenerator::new(
382
            seed,
383
            base_frequency,
384
19
            self.num_octaves,
385
19
            self.type_,
386
19
            self.stitch_tiles,
387
19
            f64::from(bounds.width()),
388
19
            f64::from(bounds.height()),
389
        );
390

            
391
        // The generated color values are in the color space determined by
392
        // color-interpolation-filters.
393
19
        let surface_type = SurfaceType::from(self.color_interpolation_filters);
394

            
395
19
        let mut surface = ExclusiveImageSurface::new(
396
19
            ctx.source_graphic().width(),
397
19
            ctx.source_graphic().height(),
398
            surface_type,
399
        )?;
400

            
401
38
        surface.modify(&mut |data, stride| {
402
1078
            for y in bounds.y_range() {
403
75767
                for x in bounds.x_range() {
404
74708
                    let point = affine.transform_point(f64::from(x), f64::from(y));
405
74708
                    let point = [point.0, point.1];
406

            
407
373381
                    let generate = |color_channel| {
408
597346
                        let v = noise_generator.turbulence(
409
                            color_channel,
410
298673
                            point,
411
298673
                            f64::from(x - bounds.x0),
412
298673
                            f64::from(y - bounds.y0),
413
                        );
414

            
415
298673
                        let v = match self.type_ {
416
90000
                            NoiseType::FractalNoise => (v * 255.0 + 255.0) / 2.0,
417
208673
                            NoiseType::Turbulence => v * 255.0,
418
                        };
419

            
420
298673
                        (clamp(v, 0.0, 255.0) + 0.5) as u8
421
298673
                    };
422

            
423
74708
                    let pixel = Pixel {
424
74708
                        r: generate(0),
425
74708
                        g: generate(1),
426
74708
                        b: generate(2),
427
74708
                        a: generate(3),
428
                    }
429
                    .premultiply();
430

            
431
74708
                    data.set_pixel(stride, pixel, x as u32, y as u32);
432
                }
433
            }
434
19
        });
435

            
436
19
        Ok(FilterOutput {
437
19
            surface: surface.share()?,
438
19
            bounds,
439
        })
440
19
    }
441
}
442

            
443
impl FilterEffect for FeTurbulence {
444
19
    fn resolve(
445
        &self,
446
        _acquired_nodes: &mut AcquiredNodes<'_>,
447
        node: &Node,
448
    ) -> Result<Vec<ResolvedPrimitive>, FilterResolveError> {
449
19
        let cascaded = CascadedValues::new_from_node(node);
450
19
        let values = cascaded.get();
451

            
452
19
        let mut params = self.params.clone();
453
19
        params.color_interpolation_filters = values.color_interpolation_filters();
454

            
455
19
        Ok(vec![ResolvedPrimitive {
456
19
            primitive: self.base.clone(),
457
19
            params: PrimitiveParams::Turbulence(params),
458
        }])
459
19
    }
460
}
461

            
462
impl Parse for StitchTiles {
463
    fn parse<'i>(parser: &mut Parser<'i, '_>) -> Result<Self, ParseError<'i>> {
464
        Ok(parse_identifiers!(
465
            parser,
466
            "stitch" => StitchTiles::Stitch,
467
            "noStitch" => StitchTiles::NoStitch,
468
        )?)
469
    }
470
}
471

            
472
impl Parse for NoiseType {
473
17
    fn parse<'i>(parser: &mut Parser<'i, '_>) -> Result<Self, ParseError<'i>> {
474
34
        Ok(parse_identifiers!(
475
            parser,
476
            "fractalNoise" => NoiseType::FractalNoise,
477
            "turbulence" => NoiseType::Turbulence,
478
        )?)
479
17
    }
480
}
481

            
482
#[cfg(test)]
483
mod tests {
484
    use super::*;
485

            
486
    #[test]
487
2
    fn turbulence_rng() {
488
1
        let mut r = 1;
489
1
        r = setup_seed(r);
490

            
491
10001
        for _ in 0..10_000 {
492
10000
            r = random(r);
493
        }
494

            
495
1
        assert_eq!(r, 1043618065);
496
2
    }
497
}