arcode 0.2.4

An Arithmetic Coder (lossless entropy encoder)
Documentation 
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

use crate::Model;

pub struct Range {
    high: u64,
    low: u64,
    half: u64,
    one_quarter_mark: u64,
    three_quarter_mark: u64,
}

impl Range {
    pub fn new(precision: u64) -> Self {
        assert!(precision < 64);

        let high: u64 = 1 << precision;
        Self {
            high,
            low: 0,
            half: high / 2,
            one_quarter_mark: high / 4,
            three_quarter_mark: (high / 4) * 3,
        }
    }

    pub const fn in_bottom_half(&self) -> bool {
        self.high < self.half
    }

    pub const fn in_upper_half(&self) -> bool {
        self.low > self.half
    }

    pub const fn in_middle_half(&self) -> bool {
        self.low > self.one_quarter_mark && self.high < self.three_quarter_mark
    }

    pub const fn in_bottom_quarter(&self) -> bool {
        self.low <= self.one_quarter_mark
    }

    /// scaling the upper half is a left shift, to avoid overflow we minus a 1/2
    /// first
    pub fn scale_upper_half(&mut self) {
        self.low = (self.low - self.half) << 1;
        self.high = (self.high - self.half) << 1;
    }

    /// subtract a quarter is the same as shifting out the second most
    /// significant bit
    pub fn scale_middle_half(&mut self) {
        self.low = (self.low - self.one_quarter_mark) << 1;
        self.high = (self.high - self.one_quarter_mark) << 1;
    }

    /// scaling the bottom half in a left shift
    pub fn scale_bottom_half(&mut self) {
        self.low <<= 1;
        self.high <<= 1;
    }

    /// returns (low, high)
    pub fn calculate_range(&self, symbol: u32, source_model: &Model) -> (u64, u64) {
        let new_width = self.high - self.low;
        let (low, high) = source_model.probability(symbol);
        (
            (self.low + (new_width as f64 * low) as u64),
            (self.low + (new_width as f64 * high) as u64),
        )
    }

    pub fn update_range(&mut self, (low, high): (u64, u64)) {
        self.low = low;
        self.high = high;
    }

    pub const fn half(&self) -> u64 {
        self.half
    }

    pub const fn quarter(&self) -> u64 {
        self.one_quarter_mark
    }
}

#[cfg(test)]
mod tests {
    use crate::{Model, Range};

    #[test]
    fn constructor() {
        let range = Range::new(5);
        assert_eq!(range.high, 32);
        assert_eq!(range.one_quarter_mark, range.high / 4);
        assert_eq!(range.half, range.high / 2);
        assert_eq!(
            range.three_quarter_mark,
            range.high - range.one_quarter_mark
        );

        assert_eq!(range.half, range.half());
        assert_eq!(range.one_quarter_mark, range.quarter());
    }

    #[test]
    fn calculate_range() {
        let model = Model::builder().num_symbols(3).build();

        let range = Range::new(8);
        assert_eq!(range.calculate_range(0, &model), (0, 85));
        assert_eq!(range.calculate_range(1, &model), (85, 170));
        assert_eq!(range.calculate_range(2, &model), (170, 256));
    }

    #[test]
    fn test_range() {
        let model = Model::builder().num_symbols(3).build();

        let mut range = Range::new(8);
        range.update_range(range.calculate_range(0, &model));
        assert!(range.in_bottom_half());
        assert!(!range.in_upper_half());
        assert!(!range.in_middle_half());
        assert!(range.in_bottom_quarter());

        let model = Model::builder().num_symbols(3).build();

        let mut range = Range::new(8);
        range.update_range(range.calculate_range(2, &model));
        assert!(!range.in_bottom_half());
        assert!(range.in_upper_half());
        assert!(!range.in_middle_half());
        assert!(!range.in_bottom_quarter());

        let model = Model::builder().num_symbols(100).build();

        let mut range = Range::new(12);
        range.update_range(range.calculate_range(50, &model));
        assert!(!range.in_bottom_half());
        assert!(!range.in_upper_half());
        assert!(range.in_middle_half());
        assert!(!range.in_bottom_quarter());
    }
}