binary_codec/encoding/
zigzag.rs

1// ZigZag implementations
2pub trait ZigZag {
3    type Unsigned;
4
5    // Convert signed number to unsigned number with ZigZag encoding
6    fn to_unsigned(self) -> Self::Unsigned;
7
8    // Convert unsigned number back to signed number with ZigZag encoding
9    fn to_signed(n: Self::Unsigned) -> Self;
10}
11
12impl ZigZag for i8 {
13    type Unsigned = u8;
14    fn to_unsigned(self) -> u8 {
15        ((self << 1) ^ (self >> 7)) as u8
16    }
17    fn to_signed(n: u8) -> i8 {
18        ((n >> 1) as i8) ^ -((n & 1) as i8)
19    }
20}
21
22impl ZigZag for i16 {
23    type Unsigned = u16;
24    fn to_unsigned(self) -> u16 {
25        ((self << 1) ^ (self >> 15)) as u16
26    }
27    fn to_signed(n: u16) -> i16 {
28        ((n >> 1) as i16) ^ -((n & 1) as i16)
29    }
30}
31
32impl ZigZag for i32 {
33    type Unsigned = u32;
34    fn to_unsigned(self) -> u32 {
35        ((self << 1) ^ (self >> 31)) as u32
36    }
37    fn to_signed(n: u32) -> i32 {
38        ((n >> 1) as i32) ^ -((n & 1) as i32)
39    }
40}
41
42impl ZigZag for i64 {
43    type Unsigned = u64;
44    fn to_unsigned(self) -> u64 {
45        ((self << 1) ^ (self >> 63)) as u64
46    }
47    fn to_signed(n: u64) -> i64 {
48        ((n >> 1) as i64) ^ -((n & 1) as i64)
49    }
50}
51
52impl ZigZag for i128 {
53    type Unsigned = u128;
54    fn to_unsigned(self) -> u128 {
55        ((self << 1) ^ (self >> 127)) as u128
56    }
57    fn to_signed(n: u128) -> i128 {
58        ((n >> 1) as i128) ^ -((n & 1) as i128)
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65    macro_rules! zigzag_test {
66        ($name:ident, $ty:ty, $unsigned:ty, $val:expr, $expected:expr) => {
67            #[test]
68            fn $name() {
69                let val: $ty = $val;
70                let encoded: $unsigned = val.to_unsigned();
71                assert_eq!(encoded, $expected, "ZigZag encoding failed for {}", val);
72                let decoded: $ty = <$ty>::to_signed(encoded);
73                assert_eq!(decoded, val, "ZigZag decoding failed for {}", val);
74            }
75        };
76    }
77
78    zigzag_test!(zigzag_i8_pos, i8, u8, 0b0000_0010, 0b0000_0100);
79    zigzag_test!(zigzag_i8_neg, i8, u8, -0b0000_0010, 0b0000_0011);
80
81    zigzag_test!(
82        zigzag_i16_pos,
83        i16,
84        u16,
85        0b0000_0000_0000_0010,
86        0b0000_0000_0000_0100
87    );
88    zigzag_test!(
89        zigzag_i16_neg,
90        i16,
91        u16,
92        -0b0000_0000_0000_0010,
93        0b0000_0000_0000_0011
94    );
95    zigzag_test!(
96        zigzag_i32_pos,
97        i32,
98        u32,
99        0b0000_0000_0000_0000_0000_0000_0000_0010,
100        0b0000_0000_0000_0000_0000_0000_0000_0100
101    );
102    zigzag_test!(
103        zigzag_i32_neg,
104        i32,
105        u32,
106        -0b0000_0000_0000_0000_0000_0000_0000_0010,
107        0b0000_0000_0000_0000_0000_0000_0000_0011
108    );
109    zigzag_test!(zigzag_i64_pos, i64, u64, 0b10, 0b100);
110    zigzag_test!(zigzag_i64_neg, i64, u64, -0b10, 0b11);
111    zigzag_test!(zigzag_i128_pos, i128, u128, 0b10, 0b100);
112    zigzag_test!(zigzag_i128_neg, i128, u128, -0b10, 0b11);
113
114    #[test]
115    fn we_actually_use_zigzag_encoding() {
116        assert_eq!(39, ZigZag::to_unsigned(-20i8));
117        assert_eq!(-2i8, ZigZag::to_signed(3u8));
118        assert_eq!(0, ZigZag::to_unsigned(0i32));
119        assert_eq!(20i32, ZigZag::to_signed(40u32));
120    }
121}
binary_codec/encoding/zigzag.rs

binary_codec/encoding/
zigzag.rs
