Crate zeck

Expand description

Zeckendorf compression and decompression library

This library provides functionality for compressing and decompressing data using the Zeckendorf algorithm.

The Zeckendorf algorithm is a way to represent numbers as a sum of non-consecutive Fibonacci numbers. If we first interpret the input data as a big integer, we can then represent the integer as a sum of non-consecutive Fibonacci numbers. Sometimes this results in a more compact representation of the data, but it is not guaranteed. Learn more about the Zeckendorf Theorem in the Zeckendorf’s Theorem Wikipedia article.

§⚠️ Warning

Compressing or decompressing files larger than 10KB (10,000 bytes) is unstable due to time and memory pressure. The library may experience performance issues, excessive memory usage, or failures when processing files exceeding this size.

This library is also available as a WebAssembly module for use in web browsers. Available functions are marked with the #[wasm_bindgen] attribute. The WebAssembly module can be built using the convenience script at scripts/build_wasm_bundle.sh that builds the WebAssembly module with the wasm-pack tool.

You can see a live demo of the WebAssembly module in action at https://prizz.github.io/zeckendorf-webapp/. The source code for the demo is available at https://github.com/pRizz/zeckendorf-webapp.

§Command-Line Tools

This library includes two command-line tools for compressing and decompressing data. They can be installed globally via:

cargo install zeck (from crates.io)
cargo install --git https://github.com/pRizz/zeckendorf zeck (from GitHub)

After installation, zeck-compress and zeck-decompress will be available in your PATH.

The compression tool automatically uses .zbe extension for big-endian compression and .zle extension for little-endian compression. The decompression tool automatically detects endianness from these file extensions.

§zeck-compress

Compresses data using the Zeckendorf representation algorithm. Supports reading from files or stdin, writing to files or stdout, and choosing between big-endian, little-endian, or automatic best compression. Automatically adds the appropriate file extension (.zbe or .zle) based on the endianness used.

When using --endian best, if neither compression method produces a smaller output, the tool will exit with an error showing compression statistics. When writing to a file, the output filename is printed to stdout. Verbose statistics are shown by default and include descriptive compression ratio messages.

# Compress a file (output filename automatically created from input with extension)
zeck-compress input.bin
# Creates input.bin.zbe or input.bin.zle depending on which endianness was used

# Compress with best endianness (statistics shown by default)
zeck-compress input.bin --endian best

# Compress from stdin to stdout
cat input.bin | zeck-compress

§zeck-decompress

Decompresses data that was compressed using the Zeckendorf representation algorithm. Supports reading from files or stdin, writing to files or stdout. Automatically detects endianness from file extension (.zbe for big-endian, .zle for little-endian), but allows manual override with the --endian flag.

# Decompress a file (endianness detected from .zbe extension, output filename automatically created)
zeck-decompress input.zbe
# Automatically uses big-endian decompression, creates output file "input"

# Decompress to a specific output file
zeck-decompress input.zbe -o output.bin
# Automatically uses big-endian decompression

# Override automatic detection
zeck-decompress input.zbe --endian little -o output.bin

# Decompress from stdin to stdout (--endian is required)
cat input.zbe | zeck-decompress --endian big

Re-exports§

pub use zeck_file_format::ZeckFile;
pub use zeck_file_format::ZeckFormatError;
pub use zeck_file_format::compress::compress_zeck_be;
pub use zeck_file_format::compress::compress_zeck_best;
pub use zeck_file_format::compress::compress_zeck_le;
pub use zeck_file_format::decompress::decompress_zeck_file;
pub use zeck_file_format::file::deserialize_zeck_file;

Modules§

zeck_file_format: .zeck file format module

Enums§

PadlessCompressionResult: Result of attempting padless compression by interpreting the input data as both big endian and little endian big integers.

Constants§

PHI: Golden ratio constant. This constant is in the rust standard library as std::f64::consts::PHI, but only available on nightly.
PHI_SQUARED: Phi squared constant. This also equals the golden ratio plus one.
SKIP_BIT: Bit flag indicating that an effective Fibonacci index (EFI) should be skipped in the Zeckendorf representation.
USE_BIT: Bit flag indicating that an effective Fibonacci index (EFI) should be used in the Zeckendorf representation.

Statics§

FAST_DOUBLING_FIBONACCI_BIGUINT_CACHE: Sparse cache for fast doubling Fibonacci algorithm

Functions§

all_ones_zeckendorf_to_biguint: Creates an “all ones Zeckendorf number”, or AOZN, by creating an Effective Zeckendorf Bits Ascending (EZBA) with n consecutive ones, then converting it to a BigUint.
bit_count_for_number: Returns the number of bits required to represent the given number. Returns 0 if the number is less than or equal to 0.
efi_to_fi: Effective Fibonacci Index to Fibonacci Index: FI(efi) === efi + 2, where efi is the Effective Fibonacci Index
efi_to_fi_biguint: Effective Fibonacci Index to Fibonacci Index: FI(efi) === efi + 2, where efi is the Effective Fibonacci Index
efi_to_fi_ref: Effective Fibonacci Index to Fibonacci Index: FI(efi) === efi + 2, where efi is the Effective Fibonacci Index
ezba_from_ezld: ezba is Effective Zeckendorf Bits Ascending ; ezld is Effective Zeckendorf List Descending
ezba_to_ezla: Converts a vector of bits (0s and 1s) from an ezba (Effective Zeckendorf Bits Ascending) into a vector of effective Fibonacci indices, the Effective Zeckendorf List Ascending.
ezl_to_zl: Converts an Effective Zeckendorf List to a Zeckendorf List. It does not matter if the list is ascending or descending; it retains the directionality of the original list.
fast_doubling_fibonacci_biguint: fibonacci(x) is equal to 0 if x is 0; 1 if x is 1; else return fibonacci(x - 1) + fibonacci(x - 2) fi stands for Fibonacci Index
fi_to_efi: Fibonacci Index to Effective Fibonacci Index: EFI(fi) === fi - 2, where fi is the Fibonacci Index
fi_to_efi_biguint: Fibonacci Index to Effective Fibonacci Index: EFI(fi) === fi - 2, where fi is the Fibonacci Index
fi_to_efi_ref: Fibonacci Index to Effective Fibonacci Index: EFI(fi) === fi - 2, where fi is the Fibonacci Index
highest_one_bit: Returns a u64 value with only the most significant set bit of n preserved.
memoized_effective_fibonacci: The memoized Fibonacci function taking an Effective Fibonacci Index as input.
memoized_fast_doubling_fibonacci_biguint: fibonacci(x) is equal to 0 if x is 0; 1 if x is 1; else return fibonacci(x - 1) + fibonacci(x - 2) fi stands for Fibonacci Index
memoized_slow_fibonacci_biguint_iterative: fibonacci(x) is equal to 0 if x is 0; 1 if x is 1; else return fibonacci(x - 1) + fibonacci(x - 2) fi stands for Fibonacci Index
memoized_slow_fibonacci_recursive: fibonacci(x) is equal to 0 if x is 0; 1 if x is 1; else return fibonacci(x - 1) + fibonacci(x - 2)
memoized_zeckendorf_list_descending_for_biguint: A descending Zeckendorf list is a sorted list of unique Fibonacci indices, in descending order, that sum to the given number.
memoized_zeckendorf_list_descending_for_integer: A descending Zeckendorf list is a sorted list of unique Fibonacci indices, in descending order, that sum to the given number.
pack_ezba_bits_to_bytes: Packs a slice of bits (0s and 1s) from an ezba (Effective Zeckendorf Bits Ascending) into bytes.
padless_zeckendorf_compress_be_dangerous: Compresses a slice of bytes using the Padless Zeckendorf Compression algorithm.
padless_zeckendorf_compress_best_dangerous: Attempts to compress the input data using both big endian and little endian interpretations, and returns the best result.
padless_zeckendorf_compress_le_dangerous: Compresses a slice of bytes using the Padless Zeckendorf Compression algorithm.
padless_zeckendorf_decompress_be_dangerous: Decompresses a slice of bytes compressed using the Zeckendorf algorithm, assuming the original data was compressed using the big endian bytes interpretation.
padless_zeckendorf_decompress_le_dangerous: Decompresses a slice of bytes compressed using the Zeckendorf algorithm, assuming the original data was compressed using the little endian bytes interpretation.
slow_fibonacci_biguint_iterative: fibonacci(x) is equal to 0 if x is 0; 1 if x is 1; else return fibonacci(x - 1) + fibonacci(x - 2) fi stands for Fibonacci Index
unpack_bytes_to_ezba_bits: Unpacks a vector of bytes into a vector of bits (0s and 1s) from an ezba (Effective Zeckendorf Bits Ascending).
zl_to_biguint: Converts a Zeckendorf List to a BigUint.
zl_to_ezl: An Effective Zeckendorf List (EZL) has a lowest EFI of 0, which is an FI of 2. This is because it doesn’t make sense for the lists to contain FIs 0 or 1 because 0 can never be added to a number and will therefore never be in a Zeckendorf List and an FI of 1 is equivalent to an FI of 2 which has a Fibonacci value of 1 so let’s just use FI starting at 2, which is an EFI of 0. It does not matter if the list is ascending or descending; it retains the directionality of the original list.

Crate zeck

Crate zeck Copy item path

§⚠️ Warning

§Command-Line Tools

§zeck-compress

§zeck-decompress

Re-exports§

Modules§

Enums§

Constants§

Statics§

Functions§

Crate zeck