1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108

//! This module provides a compressor for `f64`s by looking at the XOR between
//! consecutive values.
//!
//! This is similar to `DoubleStream` except it uses the number of leading
//! bits and meaningful bits to keep a non-shrinking window. The only time
//! The window changes is for explict changes.

pub use stream::{Writer, Reader};
use std::cmp::min;

pub enum DoubleStreamStateLeadTrail {
    Initial,
    Following {
        value: u64,
        leading_zeros: u8,
        meaningful_count: u8,
    }
}

pub struct DoubleStreamLeadTrail {
    state: DoubleStreamStateLeadTrail
}

impl DoubleStreamLeadTrail {
    // TODO: This is in large part a verbatim copy of `impl DoubleStream` with
    // a few changes. Once a clear winner has been crowned one of the
    // implementations can be removed. If no such winner is found, some code
    // could probably be extracted.
    pub fn new() -> Self {
        DoubleStreamLeadTrail {
            state: DoubleStreamStateLeadTrail::Initial
        }
    }

    pub fn push(&mut self, number: f64, writer: &mut Writer) {
        let number_as_bits = number.to_bits();

        self.state = match self.state {
            DoubleStreamStateLeadTrail::Initial => {
                writer.write(number_as_bits, 64);
                DoubleStreamStateLeadTrail::Following {
                  value: number_as_bits,
                  leading_zeros: 64, // force window to be redefined
                  meaningful_count: 0
                }
            },
            DoubleStreamStateLeadTrail::Following { value: previous, leading_zeros: prev_lz, meaningful_count: prev_meaningful } => {
                let xored = previous ^ number_as_bits;
                match xored {
                    0 => {
                        writer.write(0, 1);

                        DoubleStreamStateLeadTrail::Following {
                            value: number_as_bits,
                            // Made a choice here to keep the current window. Seems like a good
                            leading_zeros: prev_lz,
                            meaningful_count: prev_meaningful
                        }
                    },
                    _ => {
                        let lz = min(xored.leading_zeros() as u8, 31); // [LEADING31]
                        let tz = xored.trailing_zeros() as u8;
                        assert!(lz < 32); // otherwise can't be stored in 5 bits
                        // we must assume at least one meaningful bit!

                        let prev_tz = 64 - prev_lz - prev_meaningful;

                        if lz >= prev_lz && tz >= prev_tz {
                            // fit into the previous window
                            let meaningful_bits = xored >> prev_tz;
                            let meaningful_bit_count = 64 - prev_tz - prev_lz;

                            writer.write(0b10, 2);
                            writer.write(meaningful_bits, meaningful_bit_count as u8);

                            // keep window size
                            DoubleStreamStateLeadTrail::Following {
                                value: number_as_bits,
                                leading_zeros: prev_lz,
                                meaningful_count: prev_meaningful
                            }
                        } else {
                            // create a new window with leading and trailing zeros
                            let meaningful_bits = xored >> tz;

                            // if tz and lz are 0, meaningful bits is 64, which can't be stored in 6 bits, so we
                            // must assume at least one significant bit, which we safely can since the xored
                            // value is not 0
                            let meaningful_bit_count = 64 - tz - lz;

                            assert!(meaningful_bit_count <= 64);
                            writer.write(0b11, 2);
                            writer.write(lz as u64, 5);
                            writer.write((meaningful_bit_count - 1) as u64, 6); // [MEANING64]
                            writer.write(meaningful_bits, meaningful_bit_count as u8);

                            DoubleStreamStateLeadTrail::Following {
                                value: number_as_bits,
                                leading_zeros: lz,
                                meaningful_count: meaningful_bit_count
                            }
                        }
                    }
                }
            }
        };
    }
}