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 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
use deepmesa_collections::bitvec::bitvec::BitVector; use deepmesa_collections::bitvec::BitOrder; use crate::prefix::delta; use crate::prefix::gamma; impl_encoder!( /// Encodes unsigned values using Delta Encoding. /// /// Each value is encoded in two parts - a length and an /// offset. The length is encoded in Gamma and the offset is the /// binary representation with the leading `1` removed. /// /// # Examples /// ```text /// decimal 2 = 0000_0010 /// encoding for decimal 2 = 100_0 /// /// decimal 13 = 0000_1101 /// encoding for decimal 13 = 10_1_101 /// ``` /// /// The delta encoder, encodes the data in a [`BitVector`]. The /// [`.encode()`](#method.encode) accepts a [`u128`] value and /// pushes encoded bits to the [`BitVector`]. /// /// The encoder maintains a count of number of values encoded /// ([`.elements()`](#method.elements)), the number of bits used /// to encode those elements /// ([`.encoded_len()`](#method.encoded_len)) and the compression /// ratio ([`.comp_ratio()`](#method.comp_ratio)). The compression /// ratio is the average number of bits per value needed to encode /// all the values. /// /// # Examples /// ``` /// use deepmesa::encoding::DeltaEncoder; /// /// let mut de = DeltaEncoder::new(); /// /// // encode 2 /// de.encode(2); /// assert_eq!(de.elements(), 1); /// assert_eq!(de.encoded_len(), 2); /// assert_eq!(de.comp_ratio(), 2.0); /// /// // Get the underlying BitVector. /// let encoded = de.encoded(); /// assert_eq!(encoded.read_u8(0), (0b00, 2)); /// /// // encode 13 /// de.encode(13); /// assert_eq!(de.elements(), 2); /// assert_eq!(de.encoded_len(), 8); /// assert_eq!(de.comp_ratio(), 4.0); /// /// let encoded = de.encoded(); /// assert_eq!(encoded.read_u16(2), (0b101_101, 6)); /// ``` /// /// Encoded bits can be decoded using the [`DeltaDecoder`]. DeltaEncoder, encode ); impl_decoder!( /// Decodes encoded bits using Delta Encoding. /// /// The decoder accepts a [`BitVector`] with encoded bits and /// decodes each value on each invocation of the /// [`.decode()`](#method.decode) method. /// /// The decoder returns an iterator, but is an iterator itself as /// well. /// /// # Examples /// ``` /// use deepmesa::encoding::DeltaEncoder; /// use deepmesa::encoding::DeltaDecoder; /// /// let mut de = DeltaEncoder::new(); /// de.encode(2); /// de.encode(13); /// /// // Decoder needs to be mutable to use the decode method /// /// let mut dec = DeltaDecoder::new(de.encoded()); /// assert_eq!(dec.decode(), Some(2)); /// assert_eq!(dec.decode(), Some(13)); /// assert_eq!(dec.decode(), None); /// /// // use the iterator if you don't want to use a mutable /// // decoder /// let dec = DeltaDecoder::new(de.encoded()); /// let mut iter = dec.iter(); /// /// assert_eq!(iter.next(), Some(2)); /// assert_eq!(iter.next(), Some(13)); /// assert_eq!(iter.next(), None); /// /// // Or use the decoder as an iterator /// let mut dec = DeltaDecoder::new(de.encoded()); /// for val in dec { /// println!("Value: {}", val); /// } /// ``` DeltaDecoder, decode, DeltaDecodingIterator ); decoding_iter!(DeltaDecodingIterator, delta::decode); pub(super) fn encode(bitvec: &mut BitVector, val: u128) { //Chop off the MSB 1 bit and count the remaining bits to get the offset len let lz: usize = val.leading_zeros() as usize; let offset_len = crate::prefix::U128_BITS - (lz + 1); //encode the offset in gamma code by that amount gamma::encode(bitvec, offset_len as u128); //Append the delta offset to the bitvec bitvec.push_bits_u128(val, offset_len, BitOrder::Lsb0); } pub(super) fn decode(bitvec: &BitVector, index: usize) -> Option<(u128, usize)> { //first decode the gamma prefix match gamma::decode(bitvec, index) { None => return None, Some((offset_len, gamma_bits)) => { if offset_len == 0 { return Some((1, gamma_bits)); } let cursor = index + gamma_bits; let (val, read_bits) = bitvec.read_bits_u128(cursor, offset_len as usize); debug_assert!( read_bits as u128 == offset_len, "failed to read {} bits. Only read {} bits", offset_len, read_bits ); // set the bit after the msb to 1 and return it return Some((val | (1 as u128) << offset_len, gamma_bits + read_bits)); } } } #[cfg(test)] mod tests { use super::*; #[test] fn test_encode_decode() { let mut de = DeltaEncoder::new(); de.encode(13); //Delta code: 10,1,101 let enc = de.encoded(); // assert_eq!(enc.len(), 6); assert_eq!(enc[0..6].as_u8(), (0b10_1_101, 6)); assert_eq!(de.elements(), 1); de.encode(24); // Delta Code: 110,00,1000 let enc = de.encoded(); assert_eq!(enc.len(), 15); assert_eq!(enc[6..].as_u16(), (0b110_00_1000, 9)); assert_eq!(de.elements(), 2); de.encode(511); // Delta Code: 1110,000,1111_1111 let enc = de.encoded(); assert_eq!(enc.len(), 30); assert_eq!(enc[15..].as_u16(), (0b1110_000_1111_1111, 15)); assert_eq!(de.elements(), 3); //now create a decoder let mut dec = DeltaDecoder::new(&de.encoded()); // call decode to decode the first value (13) let val = dec.decode(); assert_eq!(val, Some(13)); assert_eq!(dec.cursor, 6); //now call decode again to decode the next value (24) let val = dec.decode(); assert_eq!( val, Some(24), "val={:08b}, expected: {:08b}", val.unwrap(), 24 ); assert_eq!(dec.cursor, 15); //now call decode again to decode the next value (511) let val = dec.decode(); assert_eq!(val, Some(511)); assert_eq!(dec.cursor, 30); } #[test] fn test_encode_decode_2() { let mut de = DeltaEncoder::new(); de.encode(2); let mut dec = DeltaDecoder::new(&de.encoded()); // call decode to decode the first value (13) let val = dec.decode(); assert_eq!(val, Some(2)); } }