1use crate::basic::SortOrder;
6use crate::column::writer::{compare_greater, is_nan};
7use crate::data_type::private::ParquetValueType;
8use crate::schema::types::BasicTypeInfo;
9
10const LANES_32: usize = 16;
13const LANES_64: usize = 8;
14
15#[inline(always)]
18fn min_max_by_key<T: Copy, K: Copy + Ord, const LANES: usize>(
19 values: &[T],
20 key: impl Fn(T) -> K,
21 key_min: K,
22 key_max: K,
23) -> Option<(K, K)> {
24 if values.is_empty() {
25 return None;
26 }
27
28 let mut mins = [key_max; LANES];
29 let mut maxs = [key_min; LANES];
30
31 let (chunks, remainder) = values.as_chunks::<LANES>();
32 for chunk in chunks {
33 for i in 0..LANES {
34 let k = key(chunk[i]);
35 mins[i] = mins[i].min(k);
36 maxs[i] = maxs[i].max(k);
37 }
38 }
39 for (i, v) in remainder.iter().enumerate() {
40 let k = key(*v);
41 mins[i] = mins[i].min(k);
42 maxs[i] = maxs[i].max(k);
43 }
44
45 let min = mins.into_iter().min().unwrap();
46 let max = maxs.into_iter().max().unwrap();
47 Some((min, max))
48}
49
50#[inline]
51fn is_unsigned(basic_type_info: &BasicTypeInfo) -> bool {
52 matches!(basic_type_info.sort_order(), SortOrder::UNSIGNED)
53}
54
55pub(crate) fn min_max_i32(basic_type_info: &BasicTypeInfo, values: &[i32]) -> Option<(i32, i32)> {
57 if is_unsigned(basic_type_info) {
58 min_max_by_key::<_, _, LANES_32>(values, |v| v as u32, u32::MIN, u32::MAX)
59 .map(|(min, max)| (min as i32, max as i32))
60 } else {
61 min_max_by_key::<_, _, LANES_32>(values, |v| v, i32::MIN, i32::MAX)
62 }
63}
64
65pub(crate) fn min_max_i64(basic_type_info: &BasicTypeInfo, values: &[i64]) -> Option<(i64, i64)> {
67 if is_unsigned(basic_type_info) {
68 min_max_by_key::<_, _, LANES_64>(values, |v| v as u64, u64::MIN, u64::MAX)
69 .map(|(min, max)| (min as i64, max as i64))
70 } else {
71 min_max_by_key::<_, _, LANES_64>(values, |v| v, i64::MIN, i64::MAX)
72 }
73}
74
75macro_rules! float_min_max {
76 ($name:ident, $float:ty, $int:ty, $uint:ty, $lanes:expr) => {
77 pub(crate) fn $name(values: &[$float]) -> Option<($float, $float, u64)> {
84 const SIGN_SHIFT: u32 = <$int>::BITS - 1;
85
86 #[inline(always)]
99 fn total_order_key(bits: $int) -> $int {
100 bits ^ ((((bits >> SIGN_SHIFT) as $uint) >> 1) as $int)
101 }
102
103 const BLOCK: usize = 1 << 30;
106
107 let mut min = <$int>::MAX;
108 let mut max = <$int>::MIN;
109 let mut nan_count = 0u64;
110
111 for block in values.chunks(BLOCK) {
112 let mut mins = [<$int>::MAX; $lanes];
113 let mut maxs = [<$int>::MIN; $lanes];
114 let mut nans = [<$uint>::MIN; $lanes];
115
116 let mut accumulate = |i: usize, v: $float| {
119 let bits = v.to_bits();
120 let is_nan = v.is_nan();
121 let key = total_order_key(bits as $int);
122 mins[i] = mins[i].min(if is_nan { <$int>::MAX } else { key });
123 maxs[i] = maxs[i].max(if is_nan { <$int>::MIN } else { key });
124 nans[i] += is_nan as $uint;
125 };
126
127 let (chunks, remainder) = block.as_chunks::<$lanes>();
128 for chunk in chunks {
129 for i in 0..$lanes {
130 accumulate(i, chunk[i]);
131 }
132 }
133 for (i, v) in remainder.iter().enumerate() {
134 accumulate(i, *v);
135 }
136
137 min = min.min(mins.into_iter().min().unwrap());
138 max = max.max(maxs.into_iter().max().unwrap());
139 nan_count += nans.into_iter().map(u64::from).sum::<u64>();
140 }
141
142 if nan_count as usize == values.len() {
143 return None;
144 }
145
146 let min = <$float>::from_bits(total_order_key(min) as $uint);
147 let max = <$float>::from_bits(total_order_key(max) as $uint);
148 Some((min, max, nan_count))
149 }
150 };
151}
152
153float_min_max!(min_max_f32, f32, i32, u32, LANES_32);
154float_min_max!(min_max_f64, f64, i64, u64, LANES_64);
155
156pub(crate) fn fallback_min_max<'a, T, I>(
163 basic_type_info: &BasicTypeInfo,
164 mut iter: I,
165) -> Option<(T, T, u64)>
166where
167 T: ParquetValueType + 'a,
168 I: Iterator<Item = &'a T>,
169{
170 let first = iter.next()?;
171 let mut min_max_nan = is_nan(basic_type_info, first);
172 let mut nan_count = min_max_nan as u64;
173
174 let mut min = first;
175 let mut max = first;
176 for val in iter {
177 match (min_max_nan, is_nan(basic_type_info, val)) {
178 (false, true) => {
180 nan_count += 1;
181 }
182 (true, false) => {
184 min = val;
185 max = val;
186 min_max_nan = false;
187 }
188 (_, val_is_nan) => {
190 nan_count += val_is_nan as u64;
191 if compare_greater(basic_type_info, min, val) {
194 min = val;
195 } else if compare_greater(basic_type_info, val, max) {
196 max = val;
197 }
198 }
199 }
200 }
201
202 Some((min.clone(), max.clone(), nan_count))
203}
204
205#[cfg(test)]
206mod tests {
207 use super::*;
208 use crate::basic::{ConvertedType, IntType, LogicalType, Type as PhysicalType};
209 use crate::schema::types::Type;
210 use rand::prelude::*;
211
212 fn type_info(physical: PhysicalType, logical: Option<LogicalType>) -> BasicTypeInfo {
213 Type::primitive_type_builder("col", physical)
214 .with_logical_type(logical)
215 .build()
216 .unwrap()
217 .get_basic_info()
218 .clone()
219 }
220
221 fn signed_int(bits: u8) -> Option<LogicalType> {
222 Some(LogicalType::Integer(IntType {
223 bit_width: bits as i8,
224 is_signed: true,
225 }))
226 }
227
228 fn unsigned_int(bits: u8) -> Option<LogicalType> {
229 Some(LogicalType::Integer(IntType {
230 bit_width: bits as i8,
231 is_signed: false,
232 }))
233 }
234
235 fn lengths() -> impl Iterator<Item = usize> {
237 (0..=70).chain([127, 128, 129, 1000, 4097])
238 }
239
240 fn check_ints<T, F>(
241 rng: &mut StdRng,
242 info: &BasicTypeInfo,
243 kernel: F,
244 gen_value: impl Fn(&mut StdRng) -> T,
245 ) where
246 T: crate::data_type::private::ParquetValueType + Copy,
247 F: Fn(&BasicTypeInfo, &[T]) -> Option<(T, T)>,
248 {
249 for len in lengths() {
250 let values: Vec<T> = (0..len).map(|_| gen_value(rng)).collect();
251 let expected = fallback_min_max(info, values.iter());
252 let actual = kernel(info, &values).map(|(min, max)| (min, max, 0));
253 assert_eq!(actual, expected, "len {len}: {values:?}");
254 }
255 }
256
257 #[test]
258 fn test_min_max_i32() {
259 let mut rng = StdRng::seed_from_u64(42);
260 let edges = [i32::MIN, i32::MIN + 1, -1, 0, 1, i32::MAX - 1, i32::MAX];
261 for info in [
262 type_info(PhysicalType::INT32, None),
263 type_info(PhysicalType::INT32, signed_int(32)),
264 type_info(PhysicalType::INT32, unsigned_int(32)),
265 type_info(PhysicalType::INT32, unsigned_int(8)),
266 ] {
267 check_ints(&mut rng, &info, min_max_i32, |r| r.random());
268 check_ints(&mut rng, &info, min_max_i32, |r| *edges.choose(r).unwrap());
269 check_ints(&mut rng, &info, min_max_i32, |r| r.random_range(-3..3));
270 }
271 }
272
273 #[test]
274 fn test_min_max_i64() {
275 let mut rng = StdRng::seed_from_u64(42);
276 let edges = [i64::MIN, i64::MIN + 1, -1, 0, 1, i64::MAX - 1, i64::MAX];
277 for info in [
278 type_info(PhysicalType::INT64, None),
279 type_info(PhysicalType::INT64, signed_int(64)),
280 type_info(PhysicalType::INT64, unsigned_int(64)),
281 ] {
282 check_ints(&mut rng, &info, min_max_i64, |r| r.random());
283 check_ints(&mut rng, &info, min_max_i64, |r| *edges.choose(r).unwrap());
284 check_ints(&mut rng, &info, min_max_i64, |r| r.random_range(-3..3));
285 }
286 }
287
288 #[test]
289 fn test_unsigned_int32_converted_type() {
290 let info = Type::primitive_type_builder("col", PhysicalType::INT32)
291 .with_converted_type(ConvertedType::UINT_32)
292 .build()
293 .unwrap()
294 .get_basic_info()
295 .clone();
296 assert_eq!(min_max_i32(&info, &[-1, 0, 5]), Some((0, -1)));
297 }
298
299 macro_rules! float_tests {
300 ($test:ident, $float:ty, $uint:ty, $kernel:ident, $physical:expr) => {
301 #[test]
302 fn $test() {
303 let info = type_info($physical, None);
304 let mut rng = StdRng::seed_from_u64(42);
305
306 let quiet_nan = <$float>::NAN;
307 let neg_nan = -<$float>::NAN;
308 let payload_nan = <$float>::from_bits(<$float>::NAN.to_bits() | 1);
309 let max_nan = <$float>::from_bits(<$uint>::MAX >> 1);
310 let edges = [
311 <$float>::NEG_INFINITY,
312 <$float>::MIN,
313 -1.0,
314 -<$float>::MIN_POSITIVE,
315 -0.0,
316 0.0,
317 <$float>::MIN_POSITIVE,
318 <$float>::from_bits(1),
319 1.0,
320 <$float>::MAX,
321 <$float>::INFINITY,
322 quiet_nan,
323 neg_nan,
324 payload_nan,
325 max_nan,
326 ];
327 let nans = [quiet_nan, neg_nan, payload_nan, max_nan];
328
329 let generators: [&dyn Fn(&mut StdRng) -> $float; 5] = [
330 &|r| r.random::<$float>() * 2.0 - 1.0,
331 &|r| <$float>::from_bits(r.random()),
332 &|r| *edges.choose(r).unwrap(),
333 &|r| *nans.choose(r).unwrap(),
334 &|r| {
335 if r.random_bool(0.95) {
336 quiet_nan
337 } else {
338 r.random()
339 }
340 },
341 ];
342
343 for generator in generators {
344 for len in lengths() {
345 let values: Vec<$float> = (0..len).map(|_| generator(&mut rng)).collect();
346 let expected = fallback_min_max(&info, values.iter());
347 match $kernel(&values) {
348 Some(actual) => {
349 let to_bits = |(min, max, nans): ($float, $float, u64)| {
351 (min.to_bits(), max.to_bits(), nans)
352 };
353 assert_eq!(
354 to_bits(actual),
355 to_bits(expected.unwrap()),
356 "len {len}: {values:?}"
357 );
358 }
359 None => assert!(values.iter().all(|v| v.is_nan()), "{values:?}"),
361 }
362 }
363 }
364 }
365 };
366 }
367
368 float_tests!(test_min_max_f32, f32, u32, min_max_f32, PhysicalType::FLOAT);
369 float_tests!(
370 test_min_max_f64,
371 f64,
372 u64,
373 min_max_f64,
374 PhysicalType::DOUBLE
375 );
376}