zigzag/
lib.rs

1//! A crate which exposes two quasi-extension traits that extend signed integers
2//! with the [`ZigZagEncode`] trait and unsigned integers with the
3//! [`ZigZagDecode`] trait.
4//!
5//! # Zigzag Encoding
6//!
7//! Zigzag encoding takes a signed integer and encodes it as an unsigned
8//! integer. It does so by counting up, starting at zero, alternating
9//! between representing a positive number and a negative number.
10//!
11//! To encode any signed integer, `x`, with a representation length—in bits,
12//! `n`, the formula is as follows:
13//!
14//! ```txt
15//! (x >> n - 1) ^ (x << 1)
16//! ```
17//!
18//! *Note*: The `^` operator *is not* exponentiation; rather, it is bitwise
19//! XOR.
20//!
21//! For instance, the simplified formula to encode a signed *32-bit* integer
22//! of value `x` would be as follows:
23//!
24//! ```txt
25//! (x >> 31) ^ (x << 1)
26//! ```
27//!
28//! # Zigzag Decoding
29//!
30//! To convert a zigzag-encoded unsigned integer, `x`, to its decoded signed
31//! counterpart, the formula is as follows:
32//!
33//! ```txt
34//! (x >>> 1) ^ -(x & 1)
35//! ```
36//!
37//! *Note*: The `>>>` operator is to represent a logical right shift as opposed
38//! to an arithmetic right shift. In Rust, unsigned integer types implement the
39//! right shift operator as logical instead of arithmetic. Therefore, the
40//! formula in Rust is simplified as `(x >> 1) ^ -(x & 1)`.
41//!
42//! # Examples
43//!
44//! Encoding a signed integer:
45//!
46//! ```
47//! use zigzag::ZigZagEncode;
48//!
49//! assert_eq!(0i8.zigzag_encode(), 0u8);
50//! assert_eq!((-1i8).zigzag_encode(), 1u8);
51//! assert_eq!(1i8.zigzag_encode(), 2u8);
52//!
53//! assert_eq!(i8::MIN.zigzag_encode(), u8::MAX);
54//! assert_eq!(i16::MIN.zigzag_encode(), u16::MAX);
55//! assert_eq!(i32::MIN.zigzag_encode(), u32::MAX);
56//! assert_eq!(i64::MIN.zigzag_encode(), u64::MAX);
57//! assert_eq!(i128::MIN.zigzag_encode(), u128::MAX);
58//!
59//! assert_eq!(isize::MIN.zigzag_encode(), usize::MAX);
60//! ```
61//!
62//! Decoding an unsigned integer:
63//!
64//! ```
65//! use zigzag::ZigZagDecode;
66//!
67//! assert_eq!(0u8.zigzag_decode(), 0i8);
68//! assert_eq!(1u8.zigzag_decode(), -1i8);
69//! assert_eq!(2u8.zigzag_decode(), 1i8);
70//!
71//! assert_eq!(u8::MAX.zigzag_decode(), i8::MIN);
72//! assert_eq!(u16::MAX.zigzag_decode(), i16::MIN);
73//! assert_eq!(u32::MAX.zigzag_decode(), i32::MIN);
74//! assert_eq!(u64::MAX.zigzag_decode(), i64::MIN);
75//! assert_eq!(u128::MAX.zigzag_decode(), i128::MIN);
76//!
77//! assert_eq!(usize::MAX.zigzag_decode(), isize::MIN);
78//! ```
79
80use std::mem::size_of;
81
82const BITS_PER_BYTE: usize = 8;
83
84/// A trait intended to extend signed integer types with the ability to get
85/// their unsigned representation as derived by zigzag encoding.
86///
87/// This trait does so by implementing the [`zigzag_encode`] method.
88///
89/// [`zigzag_encode`]: ZigZagEncode::zigzag_encode
90pub trait ZigZagEncode<U> {
91    /// Decodes `self` into its unsigned counterpart by using zigzag encoding.
92    ///
93    /// For more information on zigzag encoding, see its section in the
94    /// [crate documentation](crate).
95    ///
96    /// # Examples
97    ///
98    /// ```
99    /// use zigzag::ZigZagEncode;
100    ///
101    /// assert_eq!(0i8.zigzag_encode(), 0u8);
102    /// assert_eq!((-1i8).zigzag_encode(), 1u8);
103    /// assert_eq!(1i8.zigzag_encode(), 2u8);
104    /// ```
105    fn zigzag_encode(self) -> U;
106}
107
108macro_rules! impl_encode {
109    ($signed:ty, $unsigned:ty) => {
110        impl ZigZagEncode<$unsigned> for $signed {
111            #[inline]
112            fn zigzag_encode(self) -> $unsigned {
113                const TYPE_BITS: usize = size_of::<$unsigned>() * BITS_PER_BYTE;
114                (self >> TYPE_BITS - 1) as $unsigned ^ (self << 1) as $unsigned
115            }
116        }
117    };
118}
119
120impl_encode!(i8, u8);
121impl_encode!(i16, u16);
122impl_encode!(i32, u32);
123impl_encode!(i64, u64);
124impl_encode!(i128, u128);
125impl_encode!(isize, usize);
126
127/// A trait intended to extend unsigned integer types with the ability to get
128/// their signed representation as derived by zigzag decoding.
129///
130/// This trait does so by implementing the [`zigzag_decode`] method.
131///
132/// [`zigzag_decode`]: ZigZagDecode::zigzag_decode
133pub trait ZigZagDecode<S> {
134    /// Decodes `self` into its signed counterpart by using zigzag decoding.
135    ///
136    /// For more information on zigzag decoding, see its section in the
137    /// [crate documentation](crate).
138    ///
139    /// # Examples
140    ///
141    /// ```
142    /// use zigzag::ZigZagDecode;
143    ///
144    /// assert_eq!(0u8.zigzag_decode(), 0i8);
145    /// assert_eq!(1u8.zigzag_decode(), -1i8);
146    /// assert_eq!(2u8.zigzag_decode(), 1i8);
147    /// ```
148    fn zigzag_decode(self) -> S;
149}
150
151macro_rules! impl_decode {
152    ($unsigned:ty, $signed:ty) => {
153        impl ZigZagDecode<$signed> for $unsigned {
154            #[inline]
155            fn zigzag_decode(self) -> $signed {
156                (self >> 1) as $signed ^ -((self & 1) as $signed)
157            }
158        }
159    };
160}
161
162impl_decode!(u8, i8);
163impl_decode!(u16, i16);
164impl_decode!(u32, i32);
165impl_decode!(u64, i64);
166impl_decode!(u128, i128);
167impl_decode!(usize, isize);
zigzag/lib.rs

zigzag/
lib.rs
