tiny_skia/
alpha_runs.rs

Help
1// Copyright 2006 The Android Open Source Project
2// Copyright 2020 Yevhenii Reizner
3//
4// Use of this source code is governed by a BSD-style license that can be
5// found in the LICENSE file.
6
7use alloc::vec;
8use alloc::vec::Vec;
9use core::convert::TryFrom;
10use core::num::NonZeroU16;
11
12use crate::color::AlphaU8;
13use crate::LengthU32;
14
15pub type AlphaRun = Option<NonZeroU16>;
16
17/// Sparse array of run-length-encoded alpha (supersampling coverage) values.
18///
19/// Sparseness allows us to independently compose several paths into the
20/// same AlphaRuns buffer.
21pub struct AlphaRuns {
22    pub runs: Vec<AlphaRun>,
23    pub alpha: Vec<u8>,
24}
25
26impl AlphaRuns {
27    pub fn new(width: LengthU32) -> Self {
28        let mut runs = AlphaRuns {
29            runs: vec![None; (width.get() + 1) as usize],
30            alpha: vec![0; (width.get() + 1) as usize],
31        };
32        runs.reset(width);
33        runs
34    }
35
36    /// Returns 0-255 given 0-256.
37    pub fn catch_overflow(alpha: u16) -> AlphaU8 {
38        debug_assert!(alpha <= 256);
39        (alpha - (alpha >> 8)) as u8
40    }
41
42    /// Returns true if the scanline contains only a single run, of alpha value 0.
43    pub fn is_empty(&self) -> bool {
44        debug_assert!(self.runs[0].is_some());
45        match self.runs[0] {
46            Some(run) => self.alpha[0] == 0 && self.runs[usize::from(run.get())].is_none(),
47            None => true,
48        }
49    }
50
51    /// Reinitialize for a new scanline.
52    pub fn reset(&mut self, width: LengthU32) {
53        let run = u16::try_from(width.get()).unwrap();
54        self.runs[0] = NonZeroU16::new(run);
55        self.runs[width.get() as usize] = None;
56        self.alpha[0] = 0;
57    }
58
59    /// Insert into the buffer a run starting at (x-offset_x).
60    ///
61    /// if start_alpha > 0
62    ///     one pixel with value += start_alpha,
63    ///         max 255
64    /// if middle_count > 0
65    ///     middle_count pixels with value += max_value
66    /// if stop_alpha > 0
67    ///     one pixel with value += stop_alpha
68    ///
69    /// Returns the offset_x value that should be passed on the next call,
70    /// assuming we're on the same scanline. If the caller is switching
71    /// scanlines, then offset_x should be 0 when this is called.
72    pub fn add(
73        &mut self,
74        x: u32,
75        start_alpha: AlphaU8,
76        mut middle_count: usize,
77        stop_alpha: AlphaU8,
78        max_value: u8,
79        offset_x: usize,
80    ) -> usize {
81        let mut x = x as usize;
82
83        let mut runs_offset = offset_x;
84        let mut alpha_offset = offset_x;
85        let mut last_alpha_offset = offset_x;
86        x -= offset_x;
87
88        if start_alpha != 0 {
89            Self::break_run(
90                &mut self.runs[runs_offset..],
91                &mut self.alpha[alpha_offset..],
92                x,
93                1,
94            );
95            // I should be able to just add alpha[x] + start_alpha.
96            // However, if the trailing edge of the previous span and the leading
97            // edge of the current span round to the same super-sampled x value,
98            // I might overflow to 256 with this add, hence the funny subtract (crud).
99            let tmp = u16::from(self.alpha[alpha_offset + x]) + u16::from(start_alpha);
100            debug_assert!(tmp <= 256);
101            // was (tmp >> 7), but that seems wrong if we're trying to catch 256
102            self.alpha[alpha_offset + x] = (tmp - (tmp >> 8)) as u8;
103
104            runs_offset += x + 1;
105            alpha_offset += x + 1;
106            x = 0;
107        }
108
109        if middle_count != 0 {
110            Self::break_run(
111                &mut self.runs[runs_offset..],
112                &mut self.alpha[alpha_offset..],
113                x,
114                middle_count,
115            );
116            alpha_offset += x;
117            runs_offset += x;
118            x = 0;
119            loop {
120                let a = Self::catch_overflow(
121                    u16::from(self.alpha[alpha_offset]) + u16::from(max_value),
122                );
123                self.alpha[alpha_offset] = a;
124
125                let n = usize::from(self.runs[runs_offset].unwrap().get());
126                debug_assert!(n <= middle_count);
127                alpha_offset += n;
128                runs_offset += n;
129                middle_count -= n;
130
131                if middle_count == 0 {
132                    break;
133                }
134            }
135
136            last_alpha_offset = alpha_offset;
137        }
138
139        if stop_alpha != 0 {
140            Self::break_run(
141                &mut self.runs[runs_offset..],
142                &mut self.alpha[alpha_offset..],
143                x,
144                1,
145            );
146            alpha_offset += x;
147            self.alpha[alpha_offset] += stop_alpha;
148            last_alpha_offset = alpha_offset;
149        }
150
151        // new offset_x
152        last_alpha_offset
153    }
154
155    /// Break the runs in the buffer at offsets x and x+count, properly
156    /// updating the runs to the right and left.
157    ///
158    /// i.e. from the state AAAABBBB, run-length encoded as A4B4,
159    /// break_run(..., 2, 5) would produce AAAABBBB rle as A2A2B3B1.
160    /// Allows add() to sum another run to some of the new sub-runs.
161    /// i.e. adding ..CCCCC. would produce AADDEEEB, rle as A2D2E3B1.
162    fn break_run(runs: &mut [AlphaRun], alpha: &mut [u8], mut x: usize, count: usize) {
163        debug_assert!(count > 0);
164
165        let orig_x = x;
166        let mut runs_offset = 0;
167        let mut alpha_offset = 0;
168
169        while x > 0 {
170            let n = usize::from(runs[runs_offset].unwrap().get());
171            debug_assert!(n > 0);
172
173            if x < n {
174                alpha[alpha_offset + x] = alpha[alpha_offset];
175                runs[runs_offset + 0] = NonZeroU16::new(x as u16);
176                runs[runs_offset + x] = NonZeroU16::new((n - x) as u16);
177                break;
178            }
179            runs_offset += n;
180            alpha_offset += n;
181            x -= n;
182        }
183
184        runs_offset = orig_x;
185        alpha_offset = orig_x;
186        x = count;
187
188        loop {
189            let n = usize::from(runs[runs_offset].unwrap().get());
190            debug_assert!(n > 0);
191
192            if x < n {
193                alpha[alpha_offset + x] = alpha[alpha_offset];
194                runs[runs_offset + 0] = NonZeroU16::new(x as u16);
195                runs[runs_offset + x] = NonZeroU16::new((n - x) as u16);
196                break;
197            }
198
199            x -= n;
200            if x == 0 {
201                break;
202            }
203
204            runs_offset += n;
205            alpha_offset += n;
206        }
207    }
208
209    /// Cut (at offset x in the buffer) a run into two shorter runs with
210    /// matching alpha values.
211    ///
212    /// Used by the RectClipBlitter to trim a RLE encoding to match the
213    /// clipping rectangle.
214    pub fn break_at(alpha: &mut [AlphaU8], runs: &mut [AlphaRun], mut x: i32) {
215        let mut alpha_i = 0;
216        let mut run_i = 0;
217        while x > 0 {
218            let n = runs[run_i].unwrap().get();
219            let n_usize = usize::from(n);
220            let n_i32 = i32::from(n);
221            if x < n_i32 {
222                alpha[alpha_i + x as usize] = alpha[alpha_i];
223                runs[0] = NonZeroU16::new(x as u16);
224                runs[x as usize] = NonZeroU16::new((n_i32 - x) as u16);
225                break;
226            }
227
228            run_i += n_usize;
229            alpha_i += n_usize;
230            x -= n_i32;
231        }
232    }
233}
tiny_skia/alpha_runs.rs

tiny_skia/
alpha_runs.rs
