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}
234