1use super::{Encode, EncodingStrategy, Small, ULessThan};
2use crate::{Incompressible, Sorted};
3
4macro_rules! impl_uint {
5 ($t:ident, $mod:ident, $bits:literal) => {
6 mod $mod {
7 use super::*;
8
9 #[derive(Clone, Copy)]
10 pub struct Context {
11 leading_zero: [<bool as Encode>::Context; $bits],
12 context: [<bool as Encode>::Context; $bits],
13 }
14 impl Default for Context {
15 #[inline]
16 fn default() -> Self {
17 Self {
18 leading_zero: [Default::default(); $bits],
19 context: [Default::default(); $bits],
20 }
21 }
22 }
23
24 impl Encode for $t {
25 type Context = Context;
26 #[inline]
27 fn encode<E: super::super::EntropyCoder>(
28 &self,
29 writer: &mut E,
30 ctx: &mut Self::Context,
31 ) {
32 let mut am_leading = true;
33 for i in (0..$bits).rev() {
34 let bit = (*self & (1 << i)) != 0;
35 if am_leading {
36 bit.encode(writer, &mut ctx.leading_zero[i]);
37 am_leading = !bit;
38 } else {
39 bit.encode(writer, &mut ctx.context[i]);
40 }
41 }
42 }
43 #[inline]
44 fn decode<D: super::super::EntropyDecoder>(
45 reader: &mut D,
46 ctx: &mut Self::Context,
47 ) -> Result<Self, std::io::Error> {
48 let mut v = 0;
49 let mut am_leading = true;
50 for i in (0..$bits).rev() {
51 let bit = if am_leading {
52 let bit = bool::decode(reader, &mut ctx.leading_zero[i])?;
53 am_leading = !bit;
54 bit
55 } else {
56 bool::decode(reader, &mut ctx.context[i])?
57 };
58 if bit {
59 v |= 1 << i;
60 }
61 }
62 Ok(v)
63 }
64 }
65
66 #[derive(Default, Clone)]
67 pub struct SortedContext {
68 previous: Option<$t>,
69 not_sorted: <bool as Encode>::Context,
70 value: <Small as EncodingStrategy<$t>>::Context,
71 difference: <Small as EncodingStrategy<$t>>::Context,
72 }
73
74 impl EncodingStrategy<$t> for Sorted {
75 type Context = SortedContext;
76 fn encode<E: super::super::EntropyCoder>(
77 value: &$t,
78 writer: &mut E,
79 ctx: &mut Self::Context,
80 ) {
81 if let Some(previous) = ctx.previous.take() {
82 let not_sorted = *value < previous;
83 not_sorted.encode(writer, &mut ctx.not_sorted);
84 if not_sorted {
85 Small::encode(value, writer, &mut ctx.value);
86 } else {
87 Small::encode(&(*value - previous), writer, &mut ctx.difference);
88 }
89 } else {
90 Small::encode(value, writer, &mut ctx.value);
91 }
92 ctx.previous = Some(*value);
93 }
94 fn decode<D: super::super::EntropyDecoder>(
95 reader: &mut D,
96 ctx: &mut Self::Context,
97 ) -> Result<$t, std::io::Error> {
98 let out = if let Some(previous) = ctx.previous.take() {
99 let not_sorted = bool::decode(reader, &mut ctx.not_sorted)?;
100 if not_sorted {
101 Small::decode(reader, &mut ctx.value)?
102 } else {
103 previous
104 + <Small as EncodingStrategy<$t>>::decode(
105 reader,
106 &mut ctx.difference,
107 )?
108 }
109 } else {
110 Small::decode(reader, &mut ctx.value)?
111 };
112 ctx.previous = Some(out);
113 Ok(out)
114 }
115 }
116
117 impl EncodingStrategy<$t> for Incompressible {
118 type Context = ();
119 fn encode<E: super::super::EntropyCoder>(
120 value: &$t,
121 writer: &mut E,
122 _ctx: &mut Self::Context,
123 ) {
124 writer.encode_incompressible_bytes(&value.to_le_bytes())
125 }
126 fn decode<D: super::super::EntropyDecoder>(
127 reader: &mut D,
128 _ctx: &mut Self::Context,
129 ) -> Result<$t, std::io::Error> {
130 let mut b = [0; std::mem::size_of::<$t>()];
131 reader.decode_incompressible_bytes(&mut b)?;
132 Ok($t::from_le_bytes(b))
133 }
134 }
135 }
136 };
137}
138impl_uint!(u64, u64_mod, 64);
139impl_uint!(u32, u32_mod, 32);
140impl_uint!(u16, u16_mod, 16);
141
142#[test]
143fn size_u64() {
144 use super::assert_bits;
145 for sz in 0..1024_u64 {
146 println!("Trying with {sz}");
147 assert_bits!(sz, 64);
148 }
149 for sz in [1_000_000_u64] {
150 println!("Trying with {sz}");
151 assert_bits!(sz, 64);
152 }
153 for sz in [u64::MAX] {
154 println!("Trying with {sz}");
155 assert_bits!(sz, 25);
156 }
157 assert_bits!([0_u64; 128], 430);
158 assert_bits!([1_u64; 2], 101);
159 assert_bits!([1_u64; 19], 274);
160 assert_bits!(
161 [0_u64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
162 306
163 );
164}
165
166#[test]
167fn size_u32() {
168 use super::assert_bits;
169 for sz in [u32::MAX] {
170 println!("Trying with {sz}");
171 assert_bits!(sz, 12);
172 }
173 assert_bits!([0_u32; 128], 215);
174 assert_bits!([u32::MAX; 128], 175);
175 assert_bits!([1_u32; 2], 51);
176 assert_bits!([1_u32; 19], 137);
177 assert_bits!(
178 [0_u32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
179 155
180 );
181 for sz in 0..32768_u32 {
182 println!("Trying with {sz}");
183 assert_bits!(sz, 32);
184 }
185 for sz in 999_990_u32..1_000_000 {
186 println!("Trying with {sz}");
187 assert_bits!(sz, 32);
188 }
189}
190
191#[test]
192fn size_u16() {
193 use super::assert_bits;
194 for sz in 0..1_u16 {
195 println!("Trying with {sz}");
196 assert_bits!(sz, 16);
197 }
198 for sz in 1..21845_u16 {
199 println!("Trying with {sz}");
200 assert_bits!(sz, 16);
201 }
202 for sz in [u16::MAX] {
203 println!("Trying with {sz}");
204 assert_bits!(sz, 7);
205 }
206 assert_bits!([0_u16; 128], 108);
207 assert_bits!([u16::MAX; 128], 98);
208 assert_bits!([1_u16; 2], 25);
209 assert_bits!([1_u16; 19], 69);
210 assert_bits!(
211 [0_u16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
212 80
213 );
214}
215
216macro_rules! impl_compact {
217 ($t:ident, $context:ident, $bits:literal) => {
218 #[derive(Clone)]
219 pub struct $context {
220 leading_zeros: <ULessThan<{ $bits + 1 }> as Encode>::Context,
221 context: [<bool as Encode>::Context; $bits],
222 }
223 impl Default for $context {
224 fn default() -> Self {
225 Self {
226 leading_zeros: Default::default(),
227 context: [Default::default(); $bits],
228 }
229 }
230 }
231
232 impl EncodingStrategy<$t> for Small {
233 type Context = $context;
234 fn encode<E: super::EntropyCoder>(value: &$t, writer: &mut E, ctx: &mut Self::Context) {
235 let uleading = value.leading_zeros() as usize;
236 let leading_zeros = ULessThan::<{ $bits + 1 }>::new(uleading);
237 leading_zeros.encode(writer, &mut ctx.leading_zeros);
238 if uleading >= $bits - 1 {
239 return;
240 }
241 for i in 0..($bits - 1) - uleading {
242 ((value >> i) & 1 == 1).encode(writer, &mut ctx.context[i]);
243 }
244 }
245 fn decode<D: super::EntropyDecoder>(
246 reader: &mut D,
247 ctx: &mut Self::Context,
248 ) -> Result<$t, std::io::Error> {
249 let leading_zeros =
250 ULessThan::<{ $bits + 1 }>::decode(reader, &mut ctx.leading_zeros)?;
251 let uleading = usize::from(leading_zeros);
252 if uleading >= $bits - 1 {
253 if uleading == $bits {
254 return Ok(0);
255 } else {
256 return Ok(1);
257 }
258 }
259 let mut out = 1 << ($bits - 1 - uleading);
260 for i in 0..($bits - 1) - uleading {
261 if bool::decode(reader, &mut ctx.context[i])? {
262 out |= 1 << i;
263 }
264 }
265 Ok(out)
266 }
267 }
268 };
269}
270
271impl_compact!(u64, U64Compact, 64);
272impl_compact!(u32, U32Compact, 32);
273impl_compact!(u16, U16Compact, 16);
274
275#[test]
276fn compact_u16() {
277 use super::assert_bits;
278 use crate::{Encoded, Small};
279 assert_bits!(Encoded::<_, Small>::new(0_u16), 2);
280 assert_bits!(Encoded::<_, Small>::new(1_u16), 5);
281 assert_bits!(Encoded::<_, Small>::new(2_u16), 5);
282 assert_bits!(Encoded::<_, Small>::new(3_u16), 5);
283 assert_bits!(Encoded::<_, Small>::new(4_u16), 6);
284 assert_bits!(Encoded::<_, Small>::new(5_u16), 6);
285 assert_bits!(Encoded::<_, Small>::new(6_u16), 6);
286 assert_bits!(Encoded::<_, Small>::new(7_u16), 6);
287 assert_bits!(Encoded::<_, Small>::new(8_u16), 7);
288 assert_bits!(Encoded::<_, Small>::new(u16::MAX), 19);
289 assert_bits!([Encoded::<_, Small>::new(0_u16); 128], 30);
290 assert_bits!([Encoded::<_, Small>::new(u16::MAX); 128], 128);
291 assert_bits!([Encoded::<_, Small>::new(1_u16); 2], 8);
292 assert_bits!([Encoded::<_, Small>::new(1_u16); 19], 22);
293 assert_bits!(
294 [0_u16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
295 .map(Encoded::<_, Small>::new),
296 28
297 );
298}
299
300#[test]
301fn compact_u32() {
302 use super::assert_bits;
303 use crate::{Encoded, Small};
304 assert_bits!(Encoded::<_, Small>::new(0_u32), 3);
305 assert_bits!(Encoded::<_, Small>::new(1_u32), 6);
306 assert_bits!(Encoded::<_, Small>::new(2_u32), 6);
307 assert_bits!(Encoded::<_, Small>::new(3_u32), 6);
308 assert_bits!(Encoded::<_, Small>::new(4_u32), 7);
309 assert_bits!(Encoded::<_, Small>::new(5_u32), 7);
310 assert_bits!(Encoded::<_, Small>::new(6_u32), 7);
311 assert_bits!(Encoded::<_, Small>::new(7_u32), 7);
312 assert_bits!(Encoded::<_, Small>::new(8_u32), 8);
313 assert_bits!(Encoded::<_, Small>::new(u32::MAX), 36);
314 assert_bits!([Encoded::<_, Small>::new(0_u32); 128], 40);
315 assert_bits!([Encoded::<_, Small>::new(u32::MAX); 128], 242);
316 assert_bits!([Encoded::<_, Small>::new(1_u32); 2], 10);
317 assert_bits!([Encoded::<_, Small>::new(1_u32); 19], 26);
318 assert_bits!(
319 [0_u32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
320 .map(Encoded::<_, Small>::new),
321 33
322 );
323
324 for i in 0_u32..4096 {
325 assert_eq!(
326 super::encode(&Encoded::<_, Small>::new(i)),
327 super::encode_with(Small, &i)
328 );
329 }
330}
331
332macro_rules! impl_signed {
333 ($signed:ident, $unsigned:ident, $context:ident) => {
334 impl Encode for $signed {
335 type Context = <$unsigned as Encode>::Context;
336 #[inline]
337 fn encode<E: super::EntropyCoder>(&self, writer: &mut E, ctx: &mut Self::Context) {
338 $unsigned::from_le_bytes(self.to_le_bytes()).encode(writer, ctx)
339 }
340 #[inline]
341 fn decode<D: super::EntropyDecoder>(
342 reader: &mut D,
343 ctx: &mut Self::Context,
344 ) -> Result<Self, std::io::Error> {
345 let v = $unsigned::decode(reader, ctx)?;
346 Ok($signed::from_le_bytes(v.to_le_bytes()))
347 }
348 }
349
350 #[derive(Clone)]
351 pub struct $context {
352 is_negative: <bool as Encode>::Context,
353 positive: <Small as EncodingStrategy<$unsigned>>::Context,
354 negative: <Small as EncodingStrategy<$unsigned>>::Context,
355 }
356 impl Default for $context {
357 #[inline]
358 fn default() -> Self {
359 Self {
360 is_negative: Default::default(),
361 positive: Default::default(),
362 negative: Default::default(),
363 }
364 }
365 }
366
367 impl EncodingStrategy<$signed> for Small {
368 type Context = $context;
369 #[inline]
370 fn encode<E: super::EntropyCoder>(
371 value: &$signed,
372 writer: &mut E,
373 ctx: &mut Self::Context,
374 ) {
375 (*value < 0).encode(writer, &mut ctx.is_negative);
376 if *value < 0 {
377 Small::encode(&value.abs_diff(-1), writer, &mut ctx.negative)
378 } else {
379 Small::encode(&value.abs_diff(0), writer, &mut ctx.positive)
380 }
381 }
382 #[inline]
383 fn decode<D: super::EntropyDecoder>(
384 reader: &mut D,
385 ctx: &mut Self::Context,
386 ) -> Result<$signed, std::io::Error> {
387 if bool::decode(reader, &mut ctx.is_negative)? {
388 let p =
389 <Small as EncodingStrategy<$unsigned>>::decode(reader, &mut ctx.negative)?;
390 Ok(-1 - (p as $signed))
391 } else {
392 let p =
393 <Small as EncodingStrategy<$unsigned>>::decode(reader, &mut ctx.positive)?;
394 Ok(p as $signed)
395 }
396 }
397 }
398 };
399}
400
401impl_signed!(i16, u16, SignedI16Context);
402impl_signed!(i32, u32, SignedI32Context);
403impl_signed!(i64, u64, SignedI64Context);
404
405#[test]
406fn signed() {
407 use super::assert_bits;
408 use crate::{Encoded, Small};
409
410 assert_bits!(Encoded::<_, Small>::new(0_i32), 7);
411 assert_bits!(Encoded::<_, Small>::new(1_i32), 7);
412 assert_bits!(Encoded::<_, Small>::new(-1_i32), 3);
413 assert_bits!(Encoded::<_, Small>::new(i32::MAX), 36);
414 assert_bits!(Encoded::<_, Small>::new(i32::MIN), 36);
415 for v in [i32::MIN, i32::MAX, 0, 1, 7, 137, i32::MAX - 1] {
416 println!("testing {v}");
417 assert_bits!(v, 32);
418 }
419 for v in [-1i32] {
420 println!("testing {v}");
421 assert_bits!(v, 12);
422 }
423
424 assert_bits!(Encoded::<_, Small>::new(0_i16), 6);
425 assert_bits!(Encoded::<_, Small>::new(1_i16), 6);
426 assert_bits!(Encoded::<_, Small>::new(-1_i16), 3);
427 assert_bits!(Encoded::<_, Small>::new(i16::MAX), 19);
428 assert_bits!(Encoded::<_, Small>::new(i16::MIN), 19);
429 for v in [i16::MIN, i16::MAX, 0, 1, 7, 137, i16::MAX - 1] {
430 println!("testing {v}");
431 assert_bits!(v, 16);
432 }
433
434 assert_bits!(Encoded::<_, Small>::new(0_i64), 8);
435 assert_bits!(Encoded::<_, Small>::new(1_i64), 8);
436 assert_bits!(Encoded::<_, Small>::new(-1_i64), 3);
437 assert_bits!(Encoded::<_, Small>::new(i64::MAX), 68);
438 assert_bits!(Encoded::<_, Small>::new(i64::MIN), 68);
439 for v in [i64::MIN, 0, 1, 7, 137, i64::MAX - 1] {
440 println!("testing {v}");
441 assert_bits!(v, 64);
442 }
443 for v in [-1i64] {
444 println!("testing {v}");
445 assert_bits!(v, 25);
446 }
447}