Crate zigzag

Source
Expand description

A crate which exposes two quasi-extension traits that extend signed integers with the ZigZagEncode trait and unsigned integers with the ZigZagDecode trait.

§Zigzag Encoding

Zigzag encoding takes a signed integer and encodes it as an unsigned integer. It does so by counting up, starting at zero, alternating between representing a positive number and a negative number.

To encode any signed integer, x, with a representation length—in bits, n, the formula is as follows:

(x >> n - 1) ^ (x << 1)

Note: The ^ operator is not exponentiation; rather, it is bitwise XOR.

For instance, the simplified formula to encode a signed 32-bit integer of value x would be as follows:

(x >> 31) ^ (x << 1)

§Zigzag Decoding

To convert a zigzag-encoded unsigned integer, x, to its decoded signed counterpart, the formula is as follows:

(x >>> 1) ^ -(x & 1)

Note: The >>> operator is to represent a logical right shift as opposed to an arithmetic right shift. In Rust, unsigned integer types implement the right shift operator as logical instead of arithmetic. Therefore, the formula in Rust is simplified as (x >> 1) ^ -(x & 1).

§Examples

Encoding a signed integer:

use zigzag::ZigZagEncode;

assert_eq!(0i8.zigzag_encode(), 0u8);
assert_eq!((-1i8).zigzag_encode(), 1u8);
assert_eq!(1i8.zigzag_encode(), 2u8);

assert_eq!(i8::MIN.zigzag_encode(), u8::MAX);
assert_eq!(i16::MIN.zigzag_encode(), u16::MAX);
assert_eq!(i32::MIN.zigzag_encode(), u32::MAX);
assert_eq!(i64::MIN.zigzag_encode(), u64::MAX);
assert_eq!(i128::MIN.zigzag_encode(), u128::MAX);

assert_eq!(isize::MIN.zigzag_encode(), usize::MAX);

Decoding an unsigned integer:

use zigzag::ZigZagDecode;

assert_eq!(0u8.zigzag_decode(), 0i8);
assert_eq!(1u8.zigzag_decode(), -1i8);
assert_eq!(2u8.zigzag_decode(), 1i8);

assert_eq!(u8::MAX.zigzag_decode(), i8::MIN);
assert_eq!(u16::MAX.zigzag_decode(), i16::MIN);
assert_eq!(u32::MAX.zigzag_decode(), i32::MIN);
assert_eq!(u64::MAX.zigzag_decode(), i64::MIN);
assert_eq!(u128::MAX.zigzag_decode(), i128::MIN);

assert_eq!(usize::MAX.zigzag_decode(), isize::MIN);

Traits§

  • ZigZagDecode
    A trait intended to extend unsigned integer types with the ability to get their signed representation as derived by zigzag decoding.
  • ZigZagEncode
    A trait intended to extend signed integer types with the ability to get their unsigned representation as derived by zigzag encoding.