zigzag_rs/
lib.rs

1#![no_std]
2
3//! # zigzag-rs
4//!
5//! A dependency-free (including no std) ZigZag encoding/decoding Rust library.
6//! ZigZag encoding is a method for mapping signed integers to unsigned integers,
7//! commonly used in variable-length encoding and data compression.
8//!
9//! ## Features
10//!
11//! - Completely dependency-free, usable in `#![no_std]` environments
12//! - Supports all Rust native signed integer types (i8, i16, i32, i64, i128)
13//! - Simple and easy-to-use API
14//! - Efficient implementation
15//!
16//! ## Usage
17//!
18//! Add the dependency to your `Cargo.toml`:
19//!
20//! ```toml
21//! [dependencies]
22//! zigzag-rs = "0.1.0"
23//! ```
24//!
25//! Example code:
26//!
27//! ```rust
28//! use zigzag_rs::ZigZag;
29//!
30//! fn main() {
31//!     // Encoding
32//!     let encoded = i32::zigzag_encode(-1);
33//!     assert_eq!(encoded, 1u32);
34//!     
35//!     // Decoding
36//!     let decoded = i32::zigzag_decode(1u32);
37//!     assert_eq!(decoded, -1i32);
38//! }
39//! ```
40//!
41//! ## ZigZag Encoding Principle
42//!
43//! ZigZag encoding maps signed integers to unsigned integers as follows:
44//! - 0 -> 0
45//! - -1 -> 1
46//! - 1 -> 2
47//! - -2 -> 3
48//! - 2 -> 4
49//! ...
50//!
51//! This encoding method ensures that small absolute values (whether positive or negative)
52//! are mapped to small unsigned integers, which is ideal for subsequent variable-length encoding.
53/// Trait for ZigZag encoding, used to convert signed integers to unsigned integers
54pub trait ZigZag {
55    /// The corresponding unsigned type
56    type UInt;
57    
58    /// Encode a signed integer to an unsigned integer
59    fn zigzag_encode(value: Self) -> Self::UInt;
60    
61    /// Decode an unsigned integer back to a signed integer
62    fn zigzag_decode(value: Self::UInt) -> Self;
63}
64
65macro_rules! impl_zigzag {
66    ($signed:ty, $unsigned:ty, $bits:expr) => {
67        impl ZigZag for $signed {
68            type UInt = $unsigned;
69            
70            #[inline]
71            fn zigzag_encode(value: Self) -> Self::UInt {
72                // Left shift by one bit, then XOR with arithmetic right shift result
73                ((value << 1) ^ (value >> ($bits - 1))) as $unsigned
74            }
75            
76            #[inline]
77            fn zigzag_decode(value: Self::UInt) -> Self {
78                // Right shift by one bit
79                let shr1 = (value >> 1) as $signed;
80                // Lowest bit is 1 for negative, 0 for positive
81                let neg_mask = -((value & 1) as $signed);
82                // XOR operation to restore the original value
83                shr1 ^ neg_mask
84            }
85        }
86    };
87}
88
89// Implement ZigZag trait for various integer types
90impl_zigzag!(i8, u8, 8);
91impl_zigzag!(i16, u16, 16);
92impl_zigzag!(i32, u32, 32);
93impl_zigzag!(i64, u64, 64);
94impl_zigzag!(i128, u128, 128);
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99    
100    #[test]
101    fn test_encode_decode_i32() {
102        // Test specific values
103        assert_eq!(i32::zigzag_encode(0), 0u32);
104        assert_eq!(i32::zigzag_encode(-1), 1u32);
105        assert_eq!(i32::zigzag_encode(1), 2u32);
106        assert_eq!(i32::zigzag_encode(-2), 3u32);
107        
108        // Test boundary values
109        assert_eq!(i32::zigzag_encode(i32::MAX), 4294967294u32);
110        assert_eq!(i32::zigzag_encode(i32::MIN), 4294967295u32);
111        
112        // Test round-trip conversion
113        for i in [-100, -10, -1, 0, 1, 10, 100].iter() {
114            let encoded = i32::zigzag_encode(*i);
115            let decoded = i32::zigzag_decode(encoded);
116            assert_eq!(*i, decoded);
117        }
118    }
119    
120    #[test]
121    fn test_encode_decode_i8() {
122        // Test round-trip conversion for i8 type
123        for i in i8::MIN..=i8::MAX {
124            let encoded = i8::zigzag_encode(i);
125            let decoded = i8::zigzag_decode(encoded);
126            assert_eq!(i, decoded);
127        }
128    }
129    
130    #[test]
131    fn test_encode_decode_i16() {
132        // Test some i16 values
133        for i in [-1000, -100, -1, 0, 1, 100, 1000].iter() {
134            let encoded = i16::zigzag_encode(*i);
135            let decoded = i16::zigzag_decode(encoded);
136            assert_eq!(*i, decoded);
137        }
138    }
139}
zigzag_rs/lib.rs

zigzag_rs/
lib.rs
