Skip to content

Commit 1209dee

Browse files
committed
fix(alp): check ALP-RD codes against validity and tighten metadata checks
- Require u16 left parts. The decode paths read them as u16 and panicked on other ptypes. - Check only valid left-parts codes against the dictionary, and set the codes in null slots to zero, so a valid nullable array still decodes. The check moves out of alp_rd_decode into execute, where the validity is known, and uses a branch-free max when all values are valid. - Reject a right_bit_width that leaves more than 16 bits for the left part, and dictionary entries that do not fit in the left part. - Share one error for codes that are not in the dictionary. - Give the dict_len regression test a valid right_bit_width, so that it reaches the guard it tests. Signed-off-by: Robert Kruszewski <[email protected]>
1 parent d483041 commit 1209dee

3 files changed

Lines changed: 161 additions & 36 deletions

File tree

‎encodings/alp/src/alp_rd/array.rs‎

Lines changed: 72 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -54,6 +54,7 @@ use vortex_error::vortex_panic;
5454
use vortex_session::VortexSession;
5555
use vortex_session::registry::CachedId;
5656

57+
use crate::alp_rd::check_left_parts_codes;
5758
use crate::alp_rd::rules::RULES;
5859
use crate::alp_rd_decode;
5960

@@ -303,10 +304,13 @@ impl VTable for ALPRD {
303304
.validity()?
304305
.execute_mask(left_parts.as_ref().len(), ctx)?;
305306

307+
let mut left_parts = left_parts.into_buffer_mut::<u16>();
308+
check_left_parts_codes(left_parts.as_mut_slice(), &validity, left_parts_dict.len())?;
309+
306310
let decoded_array = if ptype == PType::F32 {
307311
PrimitiveArray::new(
308312
alp_rd_decode::<f32>(
309-
left_parts.into_buffer_mut::<u16>(),
313+
left_parts,
310314
&left_parts_dict,
311315
right_bit_width,
312316
right_parts.into_buffer_mut::<u32>(),
@@ -318,7 +322,7 @@ impl VTable for ALPRD {
318322
} else {
319323
PrimitiveArray::new(
320324
alp_rd_decode::<f64>(
321-
left_parts.into_buffer_mut::<u16>(),
325+
left_parts,
322326
&left_parts_dict,
323327
right_bit_width,
324328
right_parts.into_buffer_mut::<u64>(),
@@ -508,8 +512,8 @@ fn validate_parts(
508512
vortex_ensure_eq!(left_parts.len(), len);
509513
vortex_ensure_eq!(right_parts.len(), len);
510514

511-
if !left_parts.dtype().is_unsigned_int() {
512-
vortex_bail!("left_parts dtype must be uint");
515+
if !matches!(left_parts.dtype(), DType::Primitive(PType::U16, _)) {
516+
vortex_bail!("left_parts dtype must be u16, got {}", left_parts.dtype());
513517
}
514518
if dtype.is_nullable() != left_parts.dtype().is_nullable() {
515519
vortex_bail!(
@@ -548,6 +552,26 @@ fn validate_parts(
548552
float_bit_width
549553
);
550554

555+
// The left part must fit in a u16, and each dictionary entry must fit in the left part.
556+
let left_bit_width = float_bit_width - u32::from(data.right_bit_width());
557+
vortex_ensure!(
558+
left_bit_width <= u16::BITS,
559+
"ALP-RD right_bit_width {} leaves more than {} bits for the left part of a {}-bit float",
560+
data.right_bit_width(),
561+
u16::BITS,
562+
float_bit_width
563+
);
564+
if let Some(entry) = data
565+
.left_parts_dictionary()
566+
.iter()
567+
.copied()
568+
.find(|&entry| u32::from(entry) >> left_bit_width != 0)
569+
{
570+
vortex_bail!(
571+
"ALP-RD dictionary entry {entry} does not fit in the {left_bit_width}-bit left part"
572+
);
573+
}
574+
551575
if let Some(patches) = left_parts_patches {
552576
vortex_ensure_eq!(patches.array_len(), len);
553577
// Left-parts exceptions are always all-valid and are stored as the non-nullable left-parts
@@ -748,7 +772,7 @@ mod test {
748772
fn test_deserialize_rejects_dict_len_past_the_stored_dictionary() {
749773
let dtype = DType::Primitive(PType::F32, Nullability::NonNullable);
750774
let metadata = ALPRDMetadata {
751-
right_bit_width: 32,
775+
right_bit_width: 16,
752776
dict_len: 8,
753777
dict: vec![0, 1],
754778
left_parts_ptype: PType::U16 as i32,
@@ -780,14 +804,16 @@ mod test {
780804
assert!(error.to_string().contains("MAX_DICT_SIZE"));
781805
}
782806

783-
/// The decode shift `left << right_bit_width` overflows the float's bit pattern once
784-
/// `right_bit_width` reaches the width of the float, so the boundary value is rejected.
807+
/// `right_bit_width` must leave between 1 and 16 bits for the left part.
785808
#[rstest]
786-
#[case::f32(PType::F32, 32)]
787-
#[case::f64(PType::F64, 64)]
788-
fn test_deserialize_rejects_right_bit_width_at_the_float_width(
809+
#[case::f32_at_float_width(PType::F32, 32, "must be below")]
810+
#[case::f64_at_float_width(PType::F64, 64, "must be below")]
811+
#[case::f32_left_part_too_wide(PType::F32, 15, "leaves more than")]
812+
#[case::f64_left_part_too_wide(PType::F64, 47, "leaves more than")]
813+
fn test_deserialize_rejects_right_bit_width_out_of_range(
789814
#[case] float_ptype: PType,
790815
#[case] right_bit_width: u32,
816+
#[case] expected_error: &str,
791817
) {
792818
let dtype = DType::Primitive(float_ptype, Nullability::NonNullable);
793819
let metadata = ALPRDMetadata {
@@ -804,8 +830,42 @@ mod test {
804830
let children = vec![buffer![0u16].into_array(), right_parts];
805831

806832
let error = deserialize_alprd(&dtype, 1, &metadata, children)
807-
.expect_err("right_bit_width at the float width must be rejected");
808-
assert!(error.to_string().contains("right_bit_width"));
833+
.expect_err("right_bit_width out of range must be rejected");
834+
assert!(error.to_string().contains(expected_error));
835+
}
836+
837+
#[test]
838+
fn test_deserialize_rejects_dictionary_entry_wider_than_the_left_part() {
839+
let dtype = DType::Primitive(PType::F32, Nullability::NonNullable);
840+
let metadata = ALPRDMetadata {
841+
right_bit_width: 24,
842+
dict_len: 2,
843+
dict: vec![0, 256],
844+
left_parts_ptype: PType::U16 as i32,
845+
patches: None,
846+
};
847+
let children = vec![buffer![0u16].into_array(), buffer![0u32].into_array()];
848+
849+
let error = deserialize_alprd(&dtype, 1, &metadata, children)
850+
.expect_err("a dictionary entry wider than the left part must be rejected");
851+
assert!(error.to_string().contains("dictionary entry 256"));
852+
}
853+
854+
#[test]
855+
fn test_deserialize_rejects_left_parts_ptype_other_than_u16() {
856+
let dtype = DType::Primitive(PType::F32, Nullability::NonNullable);
857+
let metadata = ALPRDMetadata {
858+
right_bit_width: 16,
859+
dict_len: 2,
860+
dict: vec![0, 1],
861+
left_parts_ptype: PType::U32 as i32,
862+
patches: None,
863+
};
864+
let children = vec![buffer![0u32].into_array(), buffer![0u32].into_array()];
865+
866+
let error = deserialize_alprd(&dtype, 1, &metadata, children)
867+
.expect_err("left parts that are not u16 must be rejected");
868+
assert!(error.to_string().contains("must be u16"));
809869
}
810870

811871
/// Metadata inside the format's bounds still deserializes and decodes: code 1 maps through

‎encodings/alp/src/alp_rd/mod.rs‎

Lines changed: 43 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -25,11 +25,14 @@ use vortex_array::patches::Patches;
2525
use vortex_array::validity::Validity;
2626
use vortex_buffer::Buffer;
2727
use vortex_buffer::BufferMut;
28+
use vortex_error::VortexError;
2829
use vortex_error::VortexExpect;
2930
use vortex_error::VortexResult;
30-
use vortex_error::vortex_bail;
31+
use vortex_error::vortex_err;
3132
use vortex_error::vortex_panic;
3233
use vortex_fastlanes::bitpack_compress::bitpack_encode_unchecked;
34+
use vortex_mask::AllOr;
35+
use vortex_mask::Mask;
3336
use vortex_session::VortexSession;
3437

3538
use crate::match_each_alp_float_ptype;
@@ -136,9 +139,16 @@ where
136139
/// The decoded values are written over `right_parts`, which shares its layout with the floats they
137140
/// decode to.
138141
///
142+
/// The caller must check that each code is in `left_parts_dict`.
143+
///
144+
/// # Errors
145+
///
146+
/// Returns an error if the patches fail to execute.
147+
///
139148
/// # Panics
140149
///
141-
/// Panics if `left_parts` and `right_parts` differ in length.
150+
/// Panics if `left_parts` and `right_parts` differ in length, or if patches are set and a code is
151+
/// not in `left_parts_dict`.
142152
pub fn alp_rd_decode<T: ALPRDFloat + NativePType>(
143153
mut left_parts: BufferMut<u16>,
144154
left_parts_dict: &[u16],
@@ -154,21 +164,6 @@ where
154164
vortex_panic!("alp_rd_decode: left_parts.len != right_parts.len");
155165
}
156166

157-
// Left-parts codes are untrusted: both decode paths below index (or mask into) the
158-
// dictionary with each code, so a code outside it must be an error, not a panic or
159-
// silently decoded garbage.
160-
if let Some(code) = left_parts
161-
.as_slice()
162-
.iter()
163-
.copied()
164-
.find(|&code| code as usize >= left_parts_dict.len())
165-
{
166-
vortex_bail!(
167-
"ALP-RD left-parts code {code} is not in the {}-entry dictionary",
168-
left_parts_dict.len()
169-
);
170-
}
171-
172167
if let Some(patches) = left_parts_patches {
173168
// Patched path: some left-part codes map to exception values that live outside
174169
// the dictionary. We must dictionary-decode first, then overwrite the exceptions,
@@ -206,6 +201,37 @@ where
206201
Ok(unsafe { right_parts.transmute::<T>() }.freeze())
207202
}
208203

204+
/// Checks that each valid code is in the dictionary, and sets the codes in null slots to zero,
205+
/// because the patched decode path looks up every code.
206+
fn check_left_parts_codes(codes: &mut [u16], validity: &Mask, dict_len: usize) -> VortexResult<()> {
207+
let max_valid_code = match validity.bit_buffer() {
208+
AllOr::All => codes.iter().copied().max(),
209+
AllOr::None => {
210+
codes.fill(0);
211+
None
212+
}
213+
AllOr::Some(valid) => codes
214+
.iter_mut()
215+
.zip(valid.iter())
216+
.map(|(code, is_valid)| {
217+
if !is_valid {
218+
*code = 0;
219+
}
220+
*code
221+
})
222+
.max(),
223+
};
224+
225+
match max_valid_code {
226+
Some(code) if usize::from(code) >= dict_len => Err(code_not_in_dictionary(code, dict_len)),
227+
_ => Ok(()),
228+
}
229+
}
230+
231+
fn code_not_in_dictionary(code: u16, dict_len: usize) -> VortexError {
232+
vortex_err!("ALP-RD left-parts code {code} is not in the {dict_len}-entry dictionary")
233+
}
234+
209235
#[cfg(test)]
210236
mod tests {
211237
use vortex_array::arrays::PrimitiveArray;

‎encodings/alp/src/alp_rd/ops.rs‎

Lines changed: 46 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -8,11 +8,11 @@ use vortex_array::scalar::Scalar;
88
use vortex_array::vtable::OperationsVTable;
99
use vortex_error::VortexExpect;
1010
use vortex_error::VortexResult;
11-
use vortex_error::vortex_err;
1211

1312
use crate::ALPRD;
1413
use crate::ALPRDArrayExt;
1514
use crate::ALPRDArraySlotsExt;
15+
use crate::alp_rd::code_not_in_dictionary;
1616

1717
impl OperationsVTable<ALPRD> for ALPRD {
1818
type ProbeState = ();
@@ -41,12 +41,9 @@ impl OperationsVTable<ALPRD> for ALPRD {
4141
.as_::<u16>()
4242
.vortex_expect("left_code must be non-null");
4343
let dictionary = array.left_parts_dictionary();
44-
*dictionary.get(left_code as usize).ok_or_else(|| {
45-
vortex_err!(
46-
"ALP-RD left-parts code {left_code} is not in the {}-entry dictionary",
47-
dictionary.len()
48-
)
49-
})?
44+
*dictionary
45+
.get(usize::from(left_code))
46+
.ok_or_else(|| code_not_in_dictionary(left_code, dictionary.len()))?
5047
}
5148
};
5249

@@ -86,7 +83,9 @@ mod test {
8683
use vortex_array::dtype::NativePType;
8784
use vortex_array::dtype::Nullability;
8885
use vortex_array::dtype::PType;
86+
use vortex_array::patches::Patches;
8987
use vortex_array::scalar::Scalar;
88+
use vortex_array::validity::Validity;
9089
use vortex_buffer::buffer;
9190
use vortex_error::VortexResult;
9291
use vortex_session::VortexSession;
@@ -184,4 +183,44 @@ mod test {
184183
assert!(corrupt.execute_scalar(0, &mut ctx).is_err());
185184
Ok(())
186185
}
186+
187+
#[rstest]
188+
#[case::unpatched(false)]
189+
#[case::patched(true)]
190+
fn test_out_of_dictionary_code_in_null_slot_decodes(#[case] patched: bool) -> VortexResult<()> {
191+
let mut ctx = SESSION.create_execution_ctx();
192+
let left_parts = PrimitiveArray::new(
193+
buffer![1u16, 7, 0],
194+
Validity::from_iter([true, false, true]),
195+
);
196+
let patches = patched
197+
.then(|| {
198+
Patches::new(
199+
3,
200+
0,
201+
buffer![2u32].into_array(),
202+
buffer![30u16].into_array(),
203+
None,
204+
&mut ctx,
205+
)
206+
})
207+
.transpose()?;
208+
let array = ALPRD::try_new(
209+
DType::Primitive(PType::F32, Nullability::Nullable),
210+
left_parts.into_array(),
211+
buffer![10u16, 20],
212+
buffer![0u32, 0, 0].into_array(),
213+
16,
214+
patches,
215+
)?;
216+
217+
let last_left: u32 = if patched { 30 } else { 10 };
218+
let expected = PrimitiveArray::from_option_iter([
219+
Some(f32::from_bits(20 << 16)),
220+
None,
221+
Some(f32::from_bits(last_left << 16)),
222+
]);
223+
assert_arrays_eq!(array, expected, &mut ctx);
224+
Ok(())
225+
}
187226
}

0 commit comments

Comments
 (0)