### 3 unstable releases

0.2.0 | May 1, 2021 |
---|---|

0.1.1 | Apr 6, 2018 |

0.1.0 | Apr 5, 2018 |

#**1359** in Algorithms

**83** downloads per month

Used in fastfibonacci

**MIT**license

19KB

327 lines

# Fibonacci coding for primitive integers in Rust

This crate implements the Fibonacci
coding technique for
storing integers as variable bit length code words. It implements an
encoder consuming an interator over various primitive unsigned integer
types (

through `u8`

), and a decoder to reverse the process.`u64`

## Restrictions

Due to the way the coding scheme works, the number

can't be
encoded.`0`

###
`lib.rs`

:

Traits and functions for encoding and decoding (slices of) positive integers using Fibonacci Coding.

Fibonacci coding is a method for representing a continuous stream
of (positive) integers using a variable number of bits -- e.g.,
instead of taking up 2*32 bits for storing two

words, these
words will take up however many bits their fibonacci-encoded
representation takes up.`u32`

Fibonacci coding yields better results for smaller numbers than
larger ones: The largest 32-bit words can take up to 47 bits, but
to encode the number

, you only need 2 bits.`1`

Fibonacci coding is self-synchronizing: If a single bit is altered, a single number could be decoded as two (or two numbers decoded as one), but the remaining numbers will be read correctly.

## Value range

Fibonacci coding can represent any number that can be expressed as addition of one or more Fibonacci numbers, so any integer greater than 1, up to the range of the given machine integer type. This means that the integer zero can not be encoded.

If you should need to encode

, it is advisable to encode
numbers incremented by one (preventing overflow by upgrading to
the next-biggest integer type, or by not encoding the maximum
value), and to subtract one from the decoded result.
.`0`

# Examples

## Encoding a slice of numbers:

`use` `fibonacci_codec``::`Encode`;`
`let` numbers`:` `Vec``<``u16``>` `=` `vec!``[``1``,` `50``,` `3003``]``;`
`let` encoded `=` `&`numbers`.``fib_encode``(``)``.``unwrap``(``)``;`
`//` code words: "11" (1), "001001011" (50), "000010010000100011" (3003)
`//` These encoded words take up 4 bytes instead of 6 (3*16 bits)!
`assert_eq!``(`encoded`.``to_bytes``(``)``,` `[``0b11001001``,` `0b01100001``,` `0b00100001``,` `0b00011000``]``)``;`

## Encoding the value zero:

`use` `fibonacci_codec``::`Encode`;`
`let` numbers`:` `Vec``<``u16``>` `=` `vec!``[``0``,` `49``,` `3002``]``;`
`let` adjusted`:` `Vec``<``u32``>` `=` numbers`.``iter``(``)``.``map``(``|``n``|` `*`n `as` `u32` `+` `1``)``.``collect``(``)``;`
`let` encoded `=` `&`adjusted`.``fib_encode``(``)``.``unwrap``(``)``;`
`//` code words: "11" (1), "001001011" (50), "000010010000100011" (3003)
`//` These encoded words take up 4 bytes instead of 6 (3*16 bits)!
`assert_eq!``(`encoded`.``to_bytes``(``)``,` `[``0b11001001``,` `0b01100001``,` `0b00100001``,` `0b00011000``]``)``;`

# References:

#### Dependencies

~2MB

~48K SLoC