Skip to main content

grib/encoder/
complex.rs

1use crate::{
2    WriteToBuffer,
3    def::grib2::{
4        table::{ComplexPackingMissingValueManagement, GroupSplittingMethod},
5        template::param_set::{ComplexPacking, SimplePacking},
6    },
7    encoder::{
8        Encode, SimplePackingStrategy, WriteGrib2DataSections, bitmap::Bitmap,
9        helpers::BitsRequired, writer,
10    },
11};
12
13/// Strategies applied when performing complex packing on numerical sequences.
14/// Complex packing is a method that divides a sequence of numbers into groups
15/// and efficiently compresses each group to improve the overall compression
16/// ratio of the data.
17#[derive(Debug, PartialEq, Eq, Clone)]
18#[non_exhaustive]
19pub enum ComplexPackingStrategy {
20    /// A strategy that pre-reads a specified number of elements to determine
21    /// whether to add an element to the current group.
22    LookAhead(usize),
23}
24
25#[derive(Debug, PartialEq, Eq, Clone)]
26#[non_exhaustive]
27pub enum SpatialDifferencingOption {
28    None,
29}
30
31pub(crate) struct Encoder<'a> {
32    data: &'a [f64],
33    simple_packing_strategy: SimplePackingStrategy,
34    complex_packing_strategy: ComplexPackingStrategy,
35}
36
37impl<'a> Encoder<'a> {
38    pub(crate) fn new(
39        data: &'a [f64],
40        simple_packing_strategy: SimplePackingStrategy,
41        complex_packing_strategy: ComplexPackingStrategy,
42    ) -> Self {
43        Self {
44            data,
45            simple_packing_strategy,
46            complex_packing_strategy,
47        }
48    }
49}
50
51impl<'a> Encode for Encoder<'a> {
52    type Output = Encoded;
53
54    fn encode(&self) -> Self::Output {
55        match self.complex_packing_strategy {
56            ComplexPackingStrategy::LookAhead(num) => {
57                let (mut simple, scaled, bitmap) = match self.simple_packing_strategy {
58                    SimplePackingStrategy::Decimal(decimal) => {
59                        super::determine_simple_packing_params(self.data, decimal)
60                    }
61                };
62                let (complex, coded) = if simple.num_bits == 0 {
63                    let len = scaled.len();
64                    (
65                        ComplexPacking::for_unique_values(len),
66                        CodedValues::Unique(len),
67                    )
68                } else {
69                    let exp = 2_f64.powf(simple.exp as f64);
70                    let integers = scaled
71                        .iter()
72                        .map(|value| ((value - simple.ref_val as f64) / exp).round() as u32)
73                        .collect::<Vec<_>>();
74                    let num_bits = integers.iter().max().unwrap().bits_required();
75                    simple.num_bits = num_bits;
76                    let groups = Groups::from_values(&integers, num);
77                    (
78                        ComplexPacking::from(&groups),
79                        CodedValues::NonUnique(groups),
80                    )
81                };
82                Encoded::new(simple, complex, coded, bitmap)
83            }
84        }
85    }
86}
87
88impl ComplexPacking {
89    fn for_unique_values(len: usize) -> Self {
90        let len = len as u32;
91        Self {
92            group_splitting_method: GroupSplittingMethod(1),
93            missing_value_management: ComplexPackingMissingValueManagement(0),
94            primary_missing_value: 0xffffffff,
95            secondary_missing_value: 0xffffffff,
96            num_groups: 1,
97            group_width_ref: 0,
98            num_group_width_bits: 0,
99            group_len_ref: len,
100            group_len_inc: 1,
101            group_len_last: len,
102            num_group_len_bits: 0,
103        }
104    }
105}
106
107#[derive(Debug)]
108pub(crate) struct Encoded {
109    simple: SimplePacking,
110    complex: ComplexPacking,
111    coded: CodedValues,
112    bitmap: Bitmap,
113}
114
115impl Encoded {
116    fn new(
117        simple: SimplePacking,
118        complex: ComplexPacking,
119        coded: CodedValues,
120        bitmap: Bitmap,
121    ) -> Self {
122        Self {
123            simple,
124            complex,
125            coded,
126            bitmap,
127        }
128    }
129
130    pub(crate) fn params(&self) -> (&SimplePacking, &ComplexPacking) {
131        (&self.simple, &self.complex)
132    }
133}
134
135impl WriteGrib2DataSections for Encoded {
136    fn section5_len(&self) -> usize {
137        47
138    }
139
140    fn write_section5(&self, buf: &mut [u8]) -> Result<usize, &'static str> {
141        let len = self.section5_len();
142        if buf.len() < len {
143            return Err("destination buffer is too small");
144        }
145
146        let mut pos = 0;
147        pos += super::write_section_header(len as u32, 5, &mut buf[pos..])?;
148        pos += (self.coded.num_values() as u32).write_to_buffer(&mut buf[pos..])?; // payload.num_encoded_points
149        pos += 2_u16.write_to_buffer(&mut buf[pos..])?; // payload.template_num
150        pos += self.simple.write_to_buffer(&mut buf[pos..])?;
151        pos += 0_u8.write_to_buffer(&mut buf[pos..])?; // payload.template.orig_field_type
152        pos += self.complex.write_to_buffer(&mut buf[pos..])?;
153
154        Ok(pos)
155    }
156
157    fn section6_len(&self) -> usize {
158        let bitmap_size = if self.bitmap.has_nan() {
159            self.bitmap.num_bytes_required()
160        } else {
161            0
162        };
163        6 + bitmap_size
164    }
165
166    fn write_section6(&self, buf: &mut [u8]) -> Result<usize, &'static str> {
167        let len = self.section6_len();
168        if buf.len() < len {
169            return Err("destination buffer is too small");
170        }
171
172        let mut pos = 0;
173        pos += super::write_section_header(len as u32, 6, &mut buf[pos..])?;
174        if self.bitmap.has_nan() {
175            pos += 0_u8.write_to_buffer(&mut buf[pos..])?;
176            pos += self.bitmap.write_to_buffer(&mut buf[pos..])?;
177        } else {
178            pos += 255_u8.write_to_buffer(&mut buf[pos..])?;
179        }
180
181        Ok(pos)
182    }
183
184    fn section7_len(&self) -> usize {
185        let len = match &self.coded {
186            CodedValues::NonUnique(Groups(inner)) => {
187                let num_groups = self.complex.num_groups as usize;
188                let bits_refs = self.simple.num_bits as usize * num_groups;
189                let bits_widths = self.complex.num_group_width_bits as usize * num_groups;
190                let bits_lengths = self.complex.num_group_len_bits as usize * num_groups;
191                let bits_values: usize = inner.iter().map(|g| g.len() * g.width as usize).sum();
192                bits_refs.div_ceil(8)
193                    + bits_widths.div_ceil(8)
194                    + bits_lengths.div_ceil(8)
195                    + bits_values.div_ceil(8)
196            }
197            CodedValues::Unique(_) => 0,
198        };
199        5 + len
200    }
201
202    fn write_section7(&self, buf: &mut [u8]) -> Result<usize, &'static str> {
203        let len = self.section7_len();
204        if buf.len() < len {
205            return Err("destination buffer is too small");
206        }
207
208        let mut pos = 0;
209        pos += super::write_section_header(len as u32, 7, &mut buf[pos..])?;
210        match &self.coded {
211            CodedValues::NonUnique(Groups(inner)) => {
212                if self.simple.num_bits != 0 {
213                    let refs = inner.iter().map(|g| g.ref_val).collect::<Vec<_>>();
214                    let nbitwise = writer::NBitwise::new(&refs, self.simple.num_bits as usize);
215                    pos += nbitwise.write_to_buffer(&mut buf[pos..])?;
216                }
217
218                if self.complex.num_group_width_bits != 0 {
219                    let widths = inner
220                        .iter()
221                        .map(|g| (g.width - self.complex.group_width_ref) as u32)
222                        .collect::<Vec<_>>();
223                    let nbitwise =
224                        writer::NBitwise::new(&widths, self.complex.num_group_width_bits as usize);
225                    pos += nbitwise.write_to_buffer(&mut buf[pos..])?;
226                }
227
228                if self.complex.group_len_inc != 0 && self.complex.num_group_len_bits != 0 {
229                    let lengths = inner
230                        .iter()
231                        .take(self.complex.num_groups as usize - 1)
232                        .map(|g| {
233                            (g.len() as u32 - self.complex.group_len_ref)
234                                / self.complex.group_len_inc as u32
235                        })
236                        .chain(std::iter::once(0))
237                        .collect::<Vec<_>>();
238                    let nbitwise =
239                        writer::NBitwise::new(&lengths, self.complex.num_group_len_bits as usize);
240                    pos += nbitwise.write_to_buffer(&mut buf[pos..])?;
241                }
242
243                let mut start_offset_bits = 0;
244                for group in inner {
245                    if group.width != 0 {
246                        let nbitwise = writer::NBitwise::new(&group.values, group.width as usize)
247                            .with_offset_bits(start_offset_bits);
248                        nbitwise.write_to_buffer(&mut buf[pos..])?;
249                        let (pos_shifted, new_offset) = nbitwise.new_pos();
250                        pos += pos_shifted;
251                        start_offset_bits = new_offset;
252                    }
253                }
254                if start_offset_bits != 0 {
255                    pos += 1;
256                }
257            }
258            CodedValues::Unique(_) => {}
259        }
260
261        Ok(pos)
262    }
263}
264
265#[derive(Debug)]
266enum CodedValues {
267    NonUnique(Groups),
268    Unique(usize),
269}
270
271impl CodedValues {
272    pub(crate) fn num_values(&self) -> usize {
273        match self {
274            Self::NonUnique(vec) => vec.num_values(),
275            Self::Unique(size) => *size,
276        }
277    }
278}
279
280#[derive(Debug, PartialEq, Eq)]
281struct Groups(Vec<Group>);
282
283impl Groups {
284    fn from_values(values: &[u32], num_lookahead: usize) -> Self {
285        let mut groups = Vec::new();
286        let mut start = 0;
287
288        while start < values.len() {
289            let mut end = start + 1;
290
291            let v = values[start];
292            let (mut min, mut max) = (v, v);
293            let mut width = 0;
294
295            while end < values.len() {
296                let v = values[end];
297                let (new_min, new_max) = (min.min(v), max.max(v));
298                let new_width = (new_max - new_min).bits_required();
299
300                let len = end - start;
301                let cost_extend = group_cost(len + 1, new_width);
302                let cost_keep = group_cost(len, width)
303                    + new_group_cost_estimated(&values[end..], num_lookahead);
304                if cost_keep < cost_extend {
305                    break;
306                }
307
308                min = new_min;
309                max = new_max;
310                width = new_width;
311                end += 1;
312            }
313
314            groups.push(Group::from_values(&values[start..end]));
315            start = end;
316        }
317
318        Self(groups)
319    }
320
321    fn optimal_length_params(&self) -> Option<OptimalLengthParams> {
322        let Self(inner) = self;
323        let num_lengths = inner.len() - 1; // the last group is treated separately
324        if num_lengths == 0 {
325            None
326        } else {
327            let lengths = inner
328                .iter()
329                .take(num_lengths)
330                .map(|g| g.values.len())
331                .collect::<Vec<_>>();
332            Some(OptimalLengthParams::from(&lengths[..]))
333        }
334    }
335
336    fn num_values(&self) -> usize {
337        let Self(inner) = self;
338        inner.iter().map(|g| g.values.len()).sum()
339    }
340}
341
342fn group_cost(len: usize, width: u8) -> usize {
343    len * width as usize
344}
345
346fn new_group_cost_estimated(values: &[u32], num_lookahead: usize) -> usize {
347    if values.is_empty() {
348        return 0;
349    }
350
351    let lookahead = values.iter().take(num_lookahead);
352
353    let (mut min, mut max) = (u32::MAX, u32::MIN);
354    let mut len = 0;
355
356    for &v in lookahead {
357        (min, max) = (min.min(v), max.max(v));
358        len += 1;
359    }
360    let width = (max - min).bits_required();
361    group_cost(len, width)
362}
363
364impl From<&Groups> for ComplexPacking {
365    fn from(value: &Groups) -> Self {
366        let Groups(inner) = value;
367        let group_width_ref = inner.iter().map(|g| g.width).min().unwrap();
368        let max_width = inner.iter().map(|g| g.width).max().unwrap();
369        let num_group_width_bits = (max_width - group_width_ref).bits_required();
370        let (group_len_ref, group_len_inc, num_group_len_bits) =
371            if let Some(length_params) = value.optimal_length_params() {
372                (
373                    length_params.ref_ as u32,
374                    length_params.inc as u8,
375                    length_params.num_bits,
376                )
377            } else {
378                (0, 0, 0)
379            };
380        Self {
381            group_splitting_method: GroupSplittingMethod(1),
382            missing_value_management: ComplexPackingMissingValueManagement(0),
383            primary_missing_value: 0xffffffff,
384            secondary_missing_value: 0xffffffff,
385            num_groups: inner.len() as u32,
386            group_width_ref,
387            num_group_width_bits,
388            group_len_ref,
389            group_len_inc,
390            group_len_last: inner.last().unwrap().values.len() as u32,
391            num_group_len_bits,
392        }
393    }
394}
395
396#[derive(Debug, PartialEq, Eq)]
397struct Group {
398    pub ref_val: u32,
399    pub width: u8,
400    pub values: Vec<u32>,
401}
402
403impl Group {
404    fn from_values(values: &[u32]) -> Self {
405        let ref_val = *values.iter().min().unwrap();
406        let mut max_diff = u32::MIN;
407        let diffs = values
408            .iter()
409            .map(|v| {
410                let diff = v - ref_val;
411                max_diff = max_diff.max(diff);
412                diff
413            })
414            .collect();
415        let width = max_diff.bits_required();
416
417        Group {
418            ref_val,
419            width,
420            values: diffs,
421        }
422    }
423
424    fn len(&self) -> usize {
425        self.values.len()
426    }
427}
428
429#[derive(Debug, PartialEq, Eq)]
430struct OptimalLengthParams {
431    ref_: usize,
432    inc: usize,
433    num_bits: u8,
434    total_bits: usize,
435}
436
437impl OptimalLengthParams {
438    fn new(ref_: usize, inc: usize, num_bits: u8, total_bits: usize) -> Self {
439        Self {
440            ref_,
441            inc,
442            num_bits,
443            total_bits,
444        }
445    }
446}
447
448impl From<&[usize]> for OptimalLengthParams {
449    fn from(value: &[usize]) -> Self {
450        let ref_ = value.iter().min().unwrap();
451        let diffs = value.iter().map(|&l| l - ref_).collect::<Vec<_>>();
452        let gcd_ = diffs.iter().copied().reduce(gcd).unwrap_or(0);
453
454        if gcd_ == 0 {
455            return Self::new(*ref_, 0, 0, 0);
456        }
457
458        let max_code = diffs.iter().map(|d| d / gcd_).max().unwrap();
459        let num_bits = max_code.bits_required();
460        let total_bits = num_bits as usize * value.len();
461
462        Self::new(*ref_, gcd_, num_bits, total_bits)
463    }
464}
465
466fn gcd(m: usize, n: usize) -> usize {
467    let (m, n) = if m > n { (m, n) } else { (n, m) };
468    if n == 0 { m } else { gcd(n, m % n) }
469}
470
471#[cfg(test)]
472mod tests {
473    use super::*;
474
475    #[test]
476    fn grouping() {
477        let mut values = (0_u32..24).collect::<Vec<_>>();
478        values[10] = 64;
479        values[21] = 128;
480        values[22] = 256;
481        let actual = Groups::from_values(&values, 4);
482        let expected = Groups(vec![
483            Group {
484                ref_val: 0,
485                width: 4,
486                values: vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
487            },
488            Group {
489                ref_val: 64,
490                width: 0,
491                values: vec![0],
492            },
493            Group {
494                ref_val: 11,
495                width: 4,
496                values: vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
497            },
498            Group {
499                ref_val: 128,
500                width: 8,
501                values: vec![0, 128],
502            },
503            Group {
504                ref_val: 23,
505                width: 0,
506                values: vec![0],
507            },
508        ]);
509        assert_eq!(actual, expected);
510    }
511
512    macro_rules! test_optimal_length_params {
513        ($((
514            $name:ident,
515            $input:expr,
516            $expected:expr $(,)?
517        )),* $(,)?) => ($(
518            #[test]
519            fn $name() {
520                let lengths = $input;
521                let actual = OptimalLengthParams::from(&lengths[..]);
522                let expected = $expected;
523                assert_eq!(actual, expected);
524            }
525        )*);
526    }
527
528    test_optimal_length_params! {
529        (
530            optimal_length_params_for_all_zero,
531            vec![0, 0, 0, 0, 0],
532            OptimalLengthParams::new(0, 0, 0, 0),
533        ),
534        (
535            optimal_length_params_for_all_same_nonzero,
536            vec![5, 5, 5, 5, 5],
537            OptimalLengthParams::new(5, 0, 0, 0),
538        ),
539        (
540            optimal_length_params_for_gcd_being_one,
541            vec![26, 24, 20, 14, 13],
542            OptimalLengthParams::new(13, 1, 4, 20),
543        ),
544        (
545            optimal_length_params_for_gcd_being_integer_other_than_zero_and_one,
546            vec![13, 19, 22, 16, 25],
547            OptimalLengthParams::new(13, 3, 3, 15),
548        ),
549    }
550
551    #[test]
552    fn constant_fields_ignore_requested_decimal_scale() -> Result<(), Box<dyn std::error::Error>> {
553        for dec in [-2, 2] {
554            let values = [1.25; 4];
555            let encoded = Encoder::new(
556                &values,
557                SimplePackingStrategy::Decimal(dec),
558                ComplexPackingStrategy::LookAhead(4),
559            )
560            .encode();
561            let mut sect5 = vec![0; encoded.section5_len()];
562            encoded.write_section5(&mut sect5)?;
563            assert_eq!(&sect5[11..15], &1.25_f32.to_be_bytes());
564            assert_eq!(&sect5[17..19], &[0, 0]);
565            let mut sect6 = vec![0; encoded.section6_len()];
566            encoded.write_section6(&mut sect6)?;
567            let mut sect7 = vec![0; encoded.section7_len()];
568            encoded.write_section7(&mut sect7)?;
569            let decoder = crate::Grib2SubmessageDecoder::new(values.len(), sect5, sect6, sect7)?;
570            assert_eq!(decoder.dispatch()?.collect::<Vec<_>>(), vec![1.25; 4]);
571        }
572        Ok(())
573    }
574
575    macro_rules! grib2_coded_values_roundtrip_tests {
576        ($(($name:ident, $input:expr $(,)?)),* $(,)?) => ($(
577            #[test]
578            fn $name() -> Result<(), Box<dyn std::error::Error>> {
579                let values = $input;
580                let encoder = Encoder::new(
581                    &values,
582                    SimplePackingStrategy::Decimal(0),
583                    ComplexPackingStrategy::LookAhead(4),
584                );
585                let encoded = encoder.encode();
586                let mut sect5 = vec![0; encoded.section5_len()];
587                let pos = encoded.write_section5(&mut sect5)?;
588                assert_eq!(pos, sect5.len());
589                let mut sect6 = vec![0; encoded.section6_len()];
590                let pos = encoded.write_section6(&mut sect6)?;
591                assert_eq!(pos, sect6.len());
592                let mut sect7 = vec![0; encoded.section7_len()];
593                let pos = encoded.write_section7(&mut sect7)?;
594                assert_eq!(pos, sect7.len());
595                let decoder = crate::Grib2SubmessageDecoder::new(values.len(), sect5, sect6, sect7)?;
596                let actual = decoder.dispatch()?.collect::<Vec<_>>();
597                let expected = values.iter().map(|val| *val as f32).collect::<Vec<_>>();
598                assert_eq!(actual.len(), expected.len());
599                actual
600                    .iter()
601                    .zip(expected.iter())
602                    .all(|(a, b)| (a.is_nan() && b.is_nan()) || (a == b));
603                Ok(())
604            }
605        )*);
606    }
607
608    grib2_coded_values_roundtrip_tests! {
609        (
610            grib2_coded_values_roundtrip_test_with_nonunique_values,
611            (2..11).map(|val| val as f64).collect::<Vec<_>>(),
612        ),
613        (
614            grib2_coded_values_roundtrip_test_with_nonunique_values_and_group_len_inc_being_0,
615            (2..5).map(|val| val as f64).collect::<Vec<_>>(),
616        ),
617        (
618            grib2_coded_values_roundtrip_test_with_large_finite_range,
619            vec![0.0, 1.0e20],
620        ),
621        (
622            grib2_coded_values_roundtrip_test_with_unique_values,
623            vec![10.0_f64; 256],
624        ),
625        (
626            grib2_coded_values_roundtrip_test_with_zero_only_groups,
627            vec![0, 0, 0, 100, 10, 2, 2, 1]
628                .into_iter()
629                .flat_map(|val| [val as f64; 8])
630                .collect::<Vec<_>>(),
631        ),
632        (
633            grib2_coded_values_roundtrip_test_with_body_data_affected_by_offsets,
634            vec![0.; 32]
635                .into_iter()
636                .chain([7., 15., 90.].into_iter())
637                .chain([0.; 32].into_iter())
638                .chain([114., 104., 92., 225.].into_iter())
639                .chain([0.; 32].into_iter())
640                .chain([114., 104., 92., 225.].into_iter())
641                .collect::<Vec<_>>(),
642        ),
643    }
644}