1use vortex_buffer::BitBuffer;
10use vortex_buffer::BitBufferMut;
11use vortex_error::VortexResult;
12use vortex_mask::Mask;
13
14use crate::ArrayRef;
15use crate::ExecutionCtx;
16use crate::IntoArray;
17use crate::arrays::BoolArray;
18use crate::arrays::ConstantArray;
19use crate::arrays::PrimitiveArray;
20use crate::arrays::bool::BoolArrayExt;
21use crate::arrays::runend::iter::trimmed_ends_iter;
22use crate::dtype::DType;
23use crate::dtype::Nullability;
24use crate::match_each_unsigned_integer_ptype;
25use crate::scalar::Scalar;
26use crate::validity::Validity;
27
28const PREFILL_RUN_THRESHOLD: usize = 32;
31
32pub fn runend_decode_bools(
38 ends: PrimitiveArray,
39 values: BoolArray,
40 offset: usize,
41 length: usize,
42 ctx: &mut ExecutionCtx,
43) -> VortexResult<ArrayRef> {
44 assert_eq!(
49 ends.len(),
50 values.len(),
51 "run ends and values must have the same length"
52 );
53
54 let validity = values
55 .as_ref()
56 .validity()?
57 .execute_mask(values.as_ref().len(), ctx)?;
58 let values_buf = values.to_bit_buffer();
59 let nullability = values.dtype().nullability();
60
61 let num_runs = values_buf.len();
63 if offset == 0 && num_runs < PREFILL_RUN_THRESHOLD {
64 return Ok(match_each_unsigned_integer_ptype!(ends.ptype(), |E| {
65 decode_few_runs_no_offset(
66 ends.as_slice::<E>(),
67 &values_buf,
68 validity,
69 nullability,
70 length,
71 )
72 }));
73 }
74
75 Ok(match_each_unsigned_integer_ptype!(ends.ptype(), |E| {
76 runend_decode_typed_bool(
77 trimmed_ends_iter(ends.as_slice::<E>(), offset, length),
78 &values_buf,
79 validity,
80 nullability,
81 length,
82 )
83 }))
84}
85
86pub fn runend_decode_typed_bool(
94 run_ends: impl Iterator<Item = usize>,
95 values: &BitBuffer,
96 values_validity: Mask,
97 values_nullability: Nullability,
98 length: usize,
99) -> ArrayRef {
100 match values_validity {
101 Mask::AllTrue(_) => {
102 decode_bool_non_nullable(run_ends, values, values_nullability, length).into_array()
103 }
104 Mask::AllFalse(_) => {
105 ConstantArray::new(Scalar::null(DType::Bool(Nullability::Nullable)), length)
106 .into_array()
107 }
108 Mask::Values(mask) => {
109 decode_bool_nullable(run_ends, values, mask.bit_buffer(), length).into_array()
110 }
111 }
112}
113
114#[allow(clippy::inline_always)]
118#[inline(always)]
119fn decode_few_runs_no_offset<E: crate::dtype::IntegerPType>(
120 ends: &[E],
121 values: &BitBuffer,
122 validity: Mask,
123 nullability: Nullability,
124 length: usize,
125) -> ArrayRef {
126 match validity {
127 Mask::AllTrue(_) => {
128 let mut decoded = BitBufferMut::with_capacity(length);
129 let mut prev_end = 0usize;
130 for (i, &end) in ends.iter().enumerate() {
131 let end = end.as_().min(length);
132 decoded.append_n(values.value(i), end - prev_end);
133 prev_end = end;
134 }
135 BoolArray::new(decoded.freeze(), nullability.into()).into_array()
136 }
137 Mask::AllFalse(_) => {
138 ConstantArray::new(Scalar::null(DType::Bool(Nullability::Nullable)), length)
139 .into_array()
140 }
141 Mask::Values(mask) => {
142 let validity_buf = mask.bit_buffer();
143 let mut decoded = BitBufferMut::with_capacity(length);
144 let mut decoded_validity = BitBufferMut::with_capacity(length);
145 let mut prev_end = 0usize;
146 for (i, &end) in ends.iter().enumerate() {
147 let end = end.as_().min(length);
148 let run_len = end - prev_end;
149 let is_valid = validity_buf.value(i);
150 if is_valid {
151 decoded_validity.append_n(true, run_len);
152 decoded.append_n(values.value(i), run_len);
153 } else {
154 decoded_validity.append_n(false, run_len);
155 decoded.append_n(false, run_len);
156 }
157 prev_end = end;
158 }
159 BoolArray::new(decoded.freeze(), Validity::from(decoded_validity.freeze())).into_array()
160 }
161 }
162}
163
164fn decode_bool_non_nullable(
166 run_ends: impl Iterator<Item = usize>,
167 values: &BitBuffer,
168 nullability: Nullability,
169 length: usize,
170) -> BoolArray {
171 let num_runs = values.len();
172
173 if num_runs < PREFILL_RUN_THRESHOLD {
175 let mut decoded = BitBufferMut::with_capacity(length);
176 for (end, value) in run_ends.zip(values.iter()) {
177 decoded.append_n(value, end - decoded.len());
178 }
179 return BoolArray::new(decoded.freeze(), nullability.into());
180 }
181
182 let prefill = values.true_count() > num_runs - values.true_count();
184 let mut decoded = BitBufferMut::full(prefill, length);
185 let mut current_pos = 0usize;
186
187 for (end, value) in run_ends.zip(values.iter()) {
188 if end > current_pos && value != prefill {
189 unsafe { decoded.fill_range_unchecked(current_pos, end, value) };
191 }
192 current_pos = end;
193 }
194 BoolArray::new(decoded.freeze(), nullability.into())
195}
196
197fn decode_bool_nullable(
199 run_ends: impl Iterator<Item = usize>,
200 values: &BitBuffer,
201 validity_mask: &BitBuffer,
202 length: usize,
203) -> BoolArray {
204 let num_runs = values.len();
205
206 if num_runs < PREFILL_RUN_THRESHOLD {
208 return decode_nullable_sequential(run_ends, values, validity_mask, length);
209 }
210
211 let prefill_decoded = values.true_count() > num_runs - values.true_count();
213 let prefill_valid = validity_mask.true_count() > num_runs - validity_mask.true_count();
214
215 let mut decoded = BitBufferMut::full(prefill_decoded, length);
216 let mut decoded_validity = BitBufferMut::full(prefill_valid, length);
217 let mut current_pos = 0usize;
218
219 for (end, (value, is_valid)) in run_ends.zip(values.iter().zip(validity_mask.iter())) {
220 if end > current_pos {
221 if is_valid != prefill_valid {
223 unsafe { decoded_validity.fill_range_unchecked(current_pos, end, is_valid) };
224 }
225 let want_decoded = is_valid && value;
227 if want_decoded != prefill_decoded {
228 unsafe { decoded.fill_range_unchecked(current_pos, end, want_decoded) };
229 }
230 current_pos = end;
231 }
232 }
233 BoolArray::new(decoded.freeze(), Validity::from(decoded_validity.freeze()))
234}
235
236#[allow(clippy::inline_always)]
238#[inline(always)]
239fn decode_nullable_sequential(
240 run_ends: impl Iterator<Item = usize>,
241 values: &BitBuffer,
242 validity_mask: &BitBuffer,
243 length: usize,
244) -> BoolArray {
245 let mut decoded = BitBufferMut::with_capacity(length);
246 let mut decoded_validity = BitBufferMut::with_capacity(length);
247
248 for (end, (value, is_valid)) in run_ends.zip(values.iter().zip(validity_mask.iter())) {
249 let run_len = end - decoded.len();
250 if is_valid {
251 decoded_validity.append_n(true, run_len);
252 decoded.append_n(value, run_len);
253 } else {
254 decoded_validity.append_n(false, run_len);
255 decoded.append_n(false, run_len);
256 }
257 }
258
259 BoolArray::new(decoded.freeze(), Validity::from(decoded_validity.freeze()))
260}
261
262#[cfg(test)]
263mod tests {
264 use std::sync::LazyLock;
265
266 use vortex_buffer::BitBuffer;
267 use vortex_error::VortexResult;
268 use vortex_session::VortexSession;
269
270 use super::runend_decode_bools;
271 use crate::VortexSessionExecute;
272 use crate::arrays::BoolArray;
273 use crate::arrays::PrimitiveArray;
274 use crate::assert_arrays_eq;
275 use crate::validity::Validity;
276
277 static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
278
279 #[test]
280 fn decode_bools_alternating() -> VortexResult<()> {
281 let mut ctx = SESSION.create_execution_ctx();
282 let ends = PrimitiveArray::from_iter([2u32, 5, 10]);
284 let values = BoolArray::from(BitBuffer::from(vec![true, false, true]));
285 let decoded = runend_decode_bools(ends, values, 0, 10, &mut ctx)?;
286
287 let expected = BoolArray::from(BitBuffer::from(vec![
288 true, true, false, false, false, true, true, true, true, true,
289 ]));
290 assert_arrays_eq!(decoded, expected, &mut ctx);
291 Ok(())
292 }
293
294 #[test]
295 fn decode_bools_mostly_true() -> VortexResult<()> {
296 let mut ctx = SESSION.create_execution_ctx();
297 let ends = PrimitiveArray::from_iter([5u32, 6, 10]);
299 let values = BoolArray::from(BitBuffer::from(vec![true, false, true]));
300 let decoded = runend_decode_bools(ends, values, 0, 10, &mut ctx)?;
301
302 let expected = BoolArray::from(BitBuffer::from(vec![
303 true, true, true, true, true, false, true, true, true, true,
304 ]));
305 assert_arrays_eq!(decoded, expected, &mut ctx);
306 Ok(())
307 }
308
309 #[test]
310 fn decode_bools_mostly_false() -> VortexResult<()> {
311 let mut ctx = SESSION.create_execution_ctx();
312 let ends = PrimitiveArray::from_iter([5u32, 6, 10]);
314 let values = BoolArray::from(BitBuffer::from(vec![false, true, false]));
315 let decoded = runend_decode_bools(ends, values, 0, 10, &mut ctx)?;
316
317 let expected = BoolArray::from(BitBuffer::from(vec![
318 false, false, false, false, false, true, false, false, false, false,
319 ]));
320 assert_arrays_eq!(decoded, expected, &mut ctx);
321 Ok(())
322 }
323
324 #[test]
325 fn decode_bools_all_true_single_run() -> VortexResult<()> {
326 let mut ctx = SESSION.create_execution_ctx();
327 let ends = PrimitiveArray::from_iter([10u32]);
328 let values = BoolArray::from(BitBuffer::from(vec![true]));
329 let decoded = runend_decode_bools(ends, values, 0, 10, &mut ctx)?;
330
331 let expected = BoolArray::from(BitBuffer::from(vec![
332 true, true, true, true, true, true, true, true, true, true,
333 ]));
334 assert_arrays_eq!(decoded, expected, &mut ctx);
335 Ok(())
336 }
337
338 #[test]
339 fn decode_bools_all_false_single_run() -> VortexResult<()> {
340 let mut ctx = SESSION.create_execution_ctx();
341 let ends = PrimitiveArray::from_iter([10u32]);
342 let values = BoolArray::from(BitBuffer::from(vec![false]));
343 let decoded = runend_decode_bools(ends, values, 0, 10, &mut ctx)?;
344
345 let expected = BoolArray::from(BitBuffer::from(vec![
346 false, false, false, false, false, false, false, false, false, false,
347 ]));
348 assert_arrays_eq!(decoded, expected, &mut ctx);
349 Ok(())
350 }
351
352 #[test]
353 fn decode_bools_with_offset() -> VortexResult<()> {
354 let mut ctx = SESSION.create_execution_ctx();
355 let ends = PrimitiveArray::from_iter([2u32, 5, 10]);
357 let values = BoolArray::from(BitBuffer::from(vec![true, false, true]));
358 let decoded = runend_decode_bools(ends, values, 2, 6, &mut ctx)?;
359
360 let expected =
361 BoolArray::from(BitBuffer::from(vec![false, false, false, true, true, true]));
362 assert_arrays_eq!(decoded, expected, &mut ctx);
363 Ok(())
364 }
365
366 #[test]
367 fn decode_bools_nullable() -> VortexResult<()> {
368 use crate::validity::Validity;
369
370 let mut ctx = SESSION.create_execution_ctx();
371 let ends = PrimitiveArray::from_iter([2u32, 5, 10]);
373 let values = BoolArray::new(
374 BitBuffer::from(vec![true, false, true]),
375 Validity::from(BitBuffer::from(vec![true, false, true])),
376 );
377 let decoded = runend_decode_bools(ends, values, 0, 10, &mut ctx)?;
378
379 let expected = BoolArray::new(
381 BitBuffer::from(vec![
382 true, true, false, false, false, true, true, true, true, true,
383 ]),
384 Validity::from(BitBuffer::from(vec![
385 true, true, false, false, false, true, true, true, true, true,
386 ])),
387 );
388 assert_arrays_eq!(decoded, expected, &mut ctx);
389 Ok(())
390 }
391
392 #[test]
393 fn decode_bools_nullable_few_runs() -> VortexResult<()> {
394 let mut ctx = SESSION.create_execution_ctx();
395 let ends = PrimitiveArray::from_iter([2000u32, 4000, 6000, 8000, 10000]);
397 let values = BoolArray::new(
398 BitBuffer::from(vec![true, false, true, false, true]),
399 Validity::from(BitBuffer::from(vec![true, false, true, false, true])),
400 );
401 let decoded = runend_decode_bools(ends, values, 0, 10000, &mut ctx)?;
402
403 let expected =
404 BoolArray::from_iter((0..10000).map(|i| ((i / 2000) % 2 == 0).then_some(true)));
405 assert_arrays_eq!(decoded, expected, &mut ctx);
406 Ok(())
407 }
408}