| 1 | #[derive(Clone,Copy,Default)] |
| 2 | pub struct ProbCounter { |
| 3 | zeroes: u32, |
| 4 | total: u32, |
| 5 | } |
| 6 | |
| 7 | // bits to code zero probability multiplied by eight |
| 8 | pub const PROB_BITS: [u8; 256] = [ |
| 9 | 0, 64, 56, 51, 48, 45, 43, 42, |
| 10 | 40, 39, 37, 36, 35, 34, 34, 33, |
| 11 | 32, 31, 31, 30, 29, 29, 28, 28, |
| 12 | 27, 27, 26, 26, 26, 25, 25, 24, |
| 13 | 24, 24, 23, 23, 23, 22, 22, 22, |
| 14 | 21, 21, 21, 21, 20, 20, 20, 20, |
| 15 | 19, 19, 19, 19, 18, 18, 18, 18, |
| 16 | 18, 17, 17, 17, 17, 17, 16, 16, |
| 17 | 16, 16, 16, 15, 15, 15, 15, 15, |
| 18 | 15, 14, 14, 14, 14, 14, 14, 14, |
| 19 | 13, 13, 13, 13, 13, 13, 13, 12, |
| 20 | 12, 12, 12, 12, 12, 12, 12, 11, |
| 21 | 11, 11, 11, 11, 11, 11, 11, 11, |
| 22 | 10, 10, 10, 10, 10, 10, 10, 10, |
| 23 | 10, 9, 9, 9, 9, 9, 9, 9, |
| 24 | 9, 9, 9, 8, 8, 8, 8, 8, |
| 25 | 8, 8, 8, 8, 8, 8, 7, 7, |
| 26 | 7, 7, 7, 7, 7, 7, 7, 7, |
| 27 | 7, 7, 6, 6, 6, 6, 6, 6, |
| 28 | 6, 6, 6, 6, 6, 6, 6, 5, |
| 29 | 5, 5, 5, 5, 5, 5, 5, 5, |
| 30 | 5, 5, 5, 5, 5, 5, 4, 4, |
| 31 | 4, 4, 4, 4, 4, 4, 4, 4, |
| 32 | 4, 4, 4, 4, 4, 4, 3, 3, |
| 33 | 3, 3, 3, 3, 3, 3, 3, 3, |
| 34 | 3, 3, 3, 3, 3, 3, 3, 2, |
| 35 | 2, 2, 2, 2, 2, 2, 2, 2, |
| 36 | 2, 2, 2, 2, 2, 2, 2, 2, |
| 37 | 2, 1, 1, 1, 1, 1, 1, 1, |
| 38 | 1, 1, 1, 1, 1, 1, 1, 1, |
| 39 | 1, 1, 1, 1, 1, 1, 0, 0, |
| 40 | 0, 0, 0, 0, 0, 0, 0, 0 |
| 41 | ]; |
| 42 | |
| 43 | impl ProbCounter { |
| 44 | pub fn add(&mut self, b: bool) { |
| 45 | if !b { |
| 46 | self.zeroes += 1; |
| 47 | } |
| 48 | self.total += 1; |
| 49 | } |
| 50 | pub fn to_prob(self) -> u8 { |
| 51 | if self.total > 0 { |
| 52 | (((self.zeroes << 8) / self.total).min(254) & !1).max(1) as u8 |
| 53 | } else { |
| 54 | 128 |
| 55 | } |
| 56 | } |
| 57 | pub fn to_prob_worthy(&self, old_prob: u8) -> u8 { |
| 58 | if self.total > 0 { |
| 59 | let new_prob = self.to_prob(); |
| 60 | let new_bits = Self::est_bits(new_prob, self.zeroes, self.total); |
| 61 | let old_bits = Self::est_bits(old_prob, self.zeroes, self.total); |
| 62 | |
| 63 | if new_bits + 7 < old_bits { |
| 64 | new_prob |
| 65 | } else { |
| 66 | old_prob |
| 67 | } |
| 68 | } else { |
| 69 | old_prob |
| 70 | } |
| 71 | } |
| 72 | fn est_bits(prob: u8, zeroes: u32, total: u32) -> u32 { |
| 73 | (u32::from(PROB_BITS[prob as usize]) * zeroes + u32::from(PROB_BITS[256 - (prob as usize)]) * (total - zeroes) + 7) >> 3 |
| 74 | } |
| 75 | } |