| <!DOCTYPE html><html lang="en"><head><meta charset="utf-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="generator" content="rustdoc"><meta name="description" content="Examples without delta-encoding"><meta name="keywords" content="rust, rustlang, rust-lang, BitPacker"><title>BitPacker in bitpacking - Rust</title><link rel="preload" as="font" type="font/woff2" crossorigin href="../SourceSerif4-Regular.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../FiraSans-Regular.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../FiraSans-Medium.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../SourceCodePro-Regular.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../SourceSerif4-Bold.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../SourceCodePro-Semibold.ttf.woff2"><link rel="stylesheet" href="../normalize.css"><link rel="stylesheet" href="../rustdoc.css" id="mainThemeStyle"><link rel="stylesheet" href="../ayu.css" disabled><link rel="stylesheet" href="../dark.css" disabled><link rel="stylesheet" href="../light.css" id="themeStyle"><script id="default-settings" ></script><script src="../storage.js"></script><script defer src="sidebar-items.js"></script><script defer src="../main.js"></script><noscript><link rel="stylesheet" href="../noscript.css"></noscript><link rel="alternate icon" type="image/png" href="../favicon-16x16.png"><link rel="alternate icon" type="image/png" href="../favicon-32x32.png"><link rel="icon" type="image/svg+xml" href="../favicon.svg"></head><body class="rustdoc trait"><!--[if lte IE 11]><div class="warning">This old browser is unsupported and will most likely display funky things.</div><![endif]--><nav class="mobile-topbar"><button class="sidebar-menu-toggle">☰</button><a class="sidebar-logo" href="../bitpacking/index.html"><div class="logo-container"><img class="rust-logo" src="../rust-logo.svg" alt="logo"></div></a><h2></h2></nav><nav class="sidebar"><a class="sidebar-logo" href="../bitpacking/index.html"><div class="logo-container"><img class="rust-logo" src="../rust-logo.svg" alt="logo"></div></a><h2 class="location"><a href="#">BitPacker</a></h2><div class="sidebar-elems"><section><h3><a href="#required-associated-consts">Required Associated Constants</a></h3><ul class="block"><li><a href="#associatedconstant.BLOCK_LEN">BLOCK_LEN</a></li></ul><h3><a href="#required-methods">Required Methods</a></h3><ul class="block"><li><a href="#tymethod.compress">compress</a></li><li><a href="#tymethod.compress_sorted">compress_sorted</a></li><li><a href="#tymethod.decompress">decompress</a></li><li><a href="#tymethod.decompress_sorted">decompress_sorted</a></li><li><a href="#tymethod.new">new</a></li><li><a href="#tymethod.num_bits">num_bits</a></li><li><a href="#tymethod.num_bits_sorted">num_bits_sorted</a></li></ul><h3><a href="#provided-methods">Provided Methods</a></h3><ul class="block"><li><a href="#method.compressed_block_size">compressed_block_size</a></li></ul><h3><a href="#implementors">Implementors</a></h3></section><h2><a href="index.html">In bitpacking</a></h2></div></nav><main><div class="width-limiter"><nav class="sub"><form class="search-form"><div class="search-container"><span></span><input class="search-input" name="search" autocomplete="off" spellcheck="false" placeholder="Click or press ‘S’ to search, ‘?’ for more options…" type="search"><div id="help-button" title="help" tabindex="-1"><a href="../help.html">?</a></div><div id="settings-menu" tabindex="-1"><a href="../settings.html" title="settings"><img width="22" height="22" alt="Change settings" src="../wheel.svg"></a></div></div></form></nav><section id="main-content" class="content"><div class="main-heading"><h1 class="fqn">Trait <a href="index.html">bitpacking</a>::<wbr><a class="trait" href="#">BitPacker</a><button id="copy-path" onclick="copy_path(this)" title="Copy item path to clipboard"><img src="../clipboard.svg" width="19" height="18" alt="Copy item path"></button></h1><span class="out-of-band"><a class="srclink" href="../src/bitpacking/lib.rs.html#162-263">source</a> · <a id="toggle-all-docs" href="javascript:void(0)" title="collapse all docs">[<span class="inner">−</span>]</a></span></div><div class="item-decl"><pre class="rust trait"><code>pub trait BitPacker: Sized + Clone + Copy { |
| const <a href="#associatedconstant.BLOCK_LEN" class="constant">BLOCK_LEN</a>: usize; |
| |
| fn <a href="#tymethod.new" class="fnname">new</a>() -> Self; |
| <span class="item-spacer"></span> fn <a href="#tymethod.compress" class="fnname">compress</a>(<br> &self,<br> decompressed: &[u32],<br> compressed: &mut [u8],<br> num_bits: u8<br> ) -> usize; |
| <span class="item-spacer"></span> fn <a href="#tymethod.compress_sorted" class="fnname">compress_sorted</a>(<br> &self,<br> initial: u32,<br> decompressed: &[u32],<br> compressed: &mut [u8],<br> num_bits: u8<br> ) -> usize; |
| <span class="item-spacer"></span> fn <a href="#tymethod.decompress" class="fnname">decompress</a>(<br> &self,<br> compressed: &[u8],<br> decompressed: &mut [u32],<br> num_bits: u8<br> ) -> usize; |
| <span class="item-spacer"></span> fn <a href="#tymethod.decompress_sorted" class="fnname">decompress_sorted</a>(<br> &self,<br> initial: u32,<br> compressed: &[u8],<br> decompressed: &mut [u32],<br> num_bits: u8<br> ) -> usize; |
| <span class="item-spacer"></span> fn <a href="#tymethod.num_bits" class="fnname">num_bits</a>(&self, decompressed: &[u32]) -> u8; |
| <span class="item-spacer"></span> fn <a href="#tymethod.num_bits_sorted" class="fnname">num_bits_sorted</a>(&self, initial: u32, decompressed: &[u32]) -> u8; |
| |
| fn <a href="#method.compressed_block_size" class="fnname">compressed_block_size</a>(num_bits: u8) -> usize { ... } |
| }</code></pre></div><details class="rustdoc-toggle top-doc" open><summary class="hideme"><span>Expand description</span></summary><div class="docblock"><h2 id="examples-without-delta-encoding"><a href="#examples-without-delta-encoding">Examples without delta-encoding</a></h2> |
| <div class="example-wrap"><pre class="rust rust-example-rendered"><code><span class="kw">extern crate </span>bitpacking; |
| |
| <span class="kw">use </span>bitpacking::{BitPacker4x, BitPacker}; |
| |
| |
| <span class="kw">let </span>bitpacker = BitPacker4x::new(); |
| |
| <span class="kw">let </span>num_bits: u8 = bitpacker.num_bits(<span class="kw-2">&</span>my_data); |
| |
| <span class="comment">// A block will be take at most 4 bytes per-integers. |
| </span><span class="kw">let </span><span class="kw-2">mut </span>compressed = <span class="macro">vec!</span>[<span class="number">0u8</span>; <span class="number">4 </span>* BitPacker4x::BLOCK_LEN]; |
| |
| <span class="kw">let </span>compressed_len = bitpacker.compress(<span class="kw-2">&</span>my_data, <span class="kw-2">&mut </span>compressed[..], num_bits); |
| |
| <span class="macro">assert_eq!</span>((num_bits <span class="kw">as </span>usize) * BitPacker4x::BLOCK_LEN / <span class="number">8</span>, compressed_len); |
| |
| <span class="comment">// Decompressing |
| </span><span class="kw">let </span><span class="kw-2">mut </span>decompressed = <span class="macro">vec!</span>[<span class="number">0u32</span>; BitPacker4x::BLOCK_LEN]; |
| bitpacker.decompress(<span class="kw-2">&</span>compressed[..compressed_len], <span class="kw-2">&mut </span>decompressed[..], num_bits); |
| |
| <span class="macro">assert_eq!</span>(<span class="kw-2">&</span>my_data, <span class="kw-2">&</span>decompressed);</code></pre></div> |
| <h2 id="examples-with-delta-encoding"><a href="#examples-with-delta-encoding">Examples with delta-encoding</a></h2> |
| <p>Delta-encoding makes it possible to store sorted integers in an efficient manner. |
| Rather than encoding the integers directly, the interval (or deltas) between each of them |
| are computed and then encoded.</p> |
| <p>Decoding then requires to first decode the deltas and then operate a cumulative sum (also called |
| integration or prefix sum) on them.</p> |
| |
| <div class="example-wrap"><pre class="rust rust-example-rendered"><code><span class="kw">extern crate </span>bitpacking; |
| |
| <span class="kw">use </span>bitpacking::{BitPacker4x, BitPacker}; |
| |
| |
| |
| <span class="comment">// The initial value is used to compute the first delta. |
| // In most use cases, you will be compressing long increasing |
| // integer sequences. |
| // |
| // You should probably pass an initial value of `0u32` to the |
| // first block if you do not have any information. |
| // |
| // When encoding the second block however, you will want to pass the last |
| // value of the first block. |
| </span><span class="kw">let </span>initial_value = <span class="number">0u32</span>; |
| |
| <span class="kw">let </span>bitpacker = BitPacker4x::new(); |
| |
| <span class="kw">let </span>num_bits: u8 = bitpacker.num_bits_sorted(initial_value, <span class="kw-2">&</span>my_data); |
| |
| <span class="comment">// A block will be take at most 4 bytes per-integers. |
| </span><span class="kw">let </span><span class="kw-2">mut </span>compressed = <span class="macro">vec!</span>[<span class="number">0u8</span>; <span class="number">4 </span>* BitPacker4x::BLOCK_LEN]; |
| |
| |
| <span class="kw">let </span>compressed_len = bitpacker.compress_sorted(initial_value, <span class="kw-2">&</span>my_data, <span class="kw-2">&mut </span>compressed[..], num_bits); |
| |
| <span class="macro">assert_eq!</span>((num_bits <span class="kw">as </span>usize) * BitPacker4x::BLOCK_LEN / <span class="number">8</span>, compressed_len); |
| |
| <span class="comment">// Decompressing |
| </span><span class="kw">let </span><span class="kw-2">mut </span>decompressed = <span class="macro">vec!</span>[<span class="number">0u32</span>; BitPacker4x::BLOCK_LEN]; |
| |
| <span class="comment">// The initial value must be the same as the one passed |
| // when compressing the block. |
| </span>bitpacker.decompress_sorted(initial_value, <span class="kw-2">&</span>compressed[..compressed_len], <span class="kw-2">&mut </span>decompressed[..], num_bits); |
| |
| <span class="macro">assert_eq!</span>(<span class="kw-2">&</span>my_data, <span class="kw-2">&</span>decompressed);</code></pre></div> |
| </div></details><h2 id="required-associated-consts" class="small-section-header">Required Associated Constants<a href="#required-associated-consts" class="anchor"></a></h2><div class="methods"><details class="rustdoc-toggle method-toggle" open><summary><section id="associatedconstant.BLOCK_LEN" class="method has-srclink"><a class="srclink rightside" href="../src/bitpacking/lib.rs.html#164">source</a><h4 class="code-header">const <a href="#associatedconstant.BLOCK_LEN" class="constant">BLOCK_LEN</a>: usize</h4></section></summary><div class="docblock"><p>Number of <code>u32</code> per compressed block</p> |
| </div></details></div><h2 id="required-methods" class="small-section-header">Required Methods<a href="#required-methods" class="anchor"></a></h2><div class="methods"><details class="rustdoc-toggle method-toggle" open><summary><section id="tymethod.new" class="method has-srclink"><a class="srclink rightside" href="../src/bitpacking/lib.rs.html#172">source</a><h4 class="code-header">fn <a href="#tymethod.new" class="fnname">new</a>() -> Self</h4></section></summary><div class="docblock"><p>Checks the available instructions set on the current |
| CPU and returns the best available implementation.</p> |
| <p>Calling <code>.new()</code> is extremely cheap, and does not |
| require any heap allocation. It is <em>not</em> required to cache |
| its result too aggressively.</p> |
| </div></details><details class="rustdoc-toggle method-toggle" open><summary><section id="tymethod.compress" class="method has-srclink"><a class="srclink rightside" href="../src/bitpacking/lib.rs.html#185">source</a><h4 class="code-header">fn <a href="#tymethod.compress" class="fnname">compress</a>(<br> &self,<br> decompressed: &[u32],<br> compressed: &mut [u8],<br> num_bits: u8<br>) -> usize</h4></section></summary><div class="docblock"><p>Compress a block of <code>u32</code>.</p> |
| <p>Assumes that the integers are all lower than <code>2^num_bits</code>. |
| The result is undefined if they are larger.</p> |
| <p>Returns the amount of bytes of the compressed block.</p> |
| <h5 id="panics"><a href="#panics">Panics</a></h5> |
| <ul> |
| <li>Panics if the compressed destination array is too small</li> |
| <li>Panics if <code>decompressed</code> length is not exactly the <code>BLOCK_LEN</code>.</li> |
| </ul> |
| </div></details><details class="rustdoc-toggle method-toggle" open><summary><section id="tymethod.compress_sorted" class="method has-srclink"><a class="srclink rightside" href="../src/bitpacking/lib.rs.html#206-212">source</a><h4 class="code-header">fn <a href="#tymethod.compress_sorted" class="fnname">compress_sorted</a>(<br> &self,<br> initial: u32,<br> decompressed: &[u32],<br> compressed: &mut [u8],<br> num_bits: u8<br>) -> usize</h4></section></summary><div class="docblock"><p>Delta encode and compressed the <code>decompressed</code> array.</p> |
| <p>Assumes that the elements in the <code>decompressed</code> array are sorted. |
| <code>initial</code> will be used to compute the first <code>delta</code>.</p> |
| <h5 id="panics-1"><a href="#panics-1">Panics</a></h5> |
| <ul> |
| <li>Panics if <code>initial</code> is greater than <code>decompressed[0]</code></li> |
| <li>Panics if <code>decompressed</code> is not sorted</li> |
| <li>Panics if <code>decompressed</code>’s length is not exactly <code>BLOCK_LEN</code></li> |
| <li>Panics if <code>compressed</code> is not large enough to receive the compressed data</li> |
| <li>Panics if the compressed destination array is too small.</li> |
| </ul> |
| <p>Returns the amount of bytes of the compressed block.</p> |
| <h5 id="panics-2"><a href="#panics-2">Panics</a></h5> |
| <ul> |
| <li>Panics if the compressed array is too short.</li> |
| <li>Panics if the decompressed array is not exactly the <code>BLOCK_LEN</code>.</li> |
| </ul> |
| </div></details><details class="rustdoc-toggle method-toggle" open><summary><section id="tymethod.decompress" class="method has-srclink"><a class="srclink rightside" href="../src/bitpacking/lib.rs.html#221">source</a><h4 class="code-header">fn <a href="#tymethod.decompress" class="fnname">decompress</a>(<br> &self,<br> compressed: &[u8],<br> decompressed: &mut [u32],<br> num_bits: u8<br>) -> usize</h4></section></summary><div class="docblock"><p>Decompress the <code>compress</code> array to the <code>decompressed</code> array.</p> |
| <p>Returns the amount of bytes that were consumed.</p> |
| <h5 id="panics-3"><a href="#panics-3">Panics</a></h5> |
| <p>Panics if the compressed array is too short, or the decompressed array is too short.</p> |
| </div></details><details class="rustdoc-toggle method-toggle" open><summary><section id="tymethod.decompress_sorted" class="method has-srclink"><a class="srclink rightside" href="../src/bitpacking/lib.rs.html#235-241">source</a><h4 class="code-header">fn <a href="#tymethod.decompress_sorted" class="fnname">decompress_sorted</a>(<br> &self,<br> initial: u32,<br> compressed: &[u8],<br> decompressed: &mut [u32],<br> num_bits: u8<br>) -> usize</h4></section></summary><div class="docblock"><p>Decompress the<code>compress</code>array to the <code>decompressed</code> array. |
| The <code>compressed</code> array is assumed to have been delta-encoded and compressed.</p> |
| <p><code>initial</code> must be the value that was passed as the <code>initial</code> argument compressing |
| the block.</p> |
| <p>Returns the amount of bytes that have been read.</p> |
| <h5 id="panics-4"><a href="#panics-4">Panics</a></h5> |
| <ul> |
| <li>Panics if the compressed array is too short to contain <code>BLOCK_LEN</code> elements</li> |
| <li>Panics if the decompressed array is too short.</li> |
| </ul> |
| </div></details><details class="rustdoc-toggle method-toggle" open><summary><section id="tymethod.num_bits" class="method has-srclink"><a class="srclink rightside" href="../src/bitpacking/lib.rs.html#249">source</a><h4 class="code-header">fn <a href="#tymethod.num_bits" class="fnname">num_bits</a>(&self, decompressed: &[u32]) -> u8</h4></section></summary><div class="docblock"><p>Returns the minimum number of bits used to represent the largest integer in the |
| <code>decompressed</code> block.</p> |
| <h5 id="panics-5"><a href="#panics-5">Panics</a></h5> |
| <p>Panics if <code>decompressed</code>’s len is not exactly <code>BLOCK_LEN</code>.</p> |
| </div></details><details class="rustdoc-toggle method-toggle" open><summary><section id="tymethod.num_bits_sorted" class="method has-srclink"><a class="srclink rightside" href="../src/bitpacking/lib.rs.html#257">source</a><h4 class="code-header">fn <a href="#tymethod.num_bits_sorted" class="fnname">num_bits_sorted</a>(&self, initial: u32, decompressed: &[u32]) -> u8</h4></section></summary><div class="docblock"><p>Returns the minimum number of bits used to represent the largest <code>delta</code> in the deltas in the |
| <code>decompressed</code> block.</p> |
| <h5 id="panics-6"><a href="#panics-6">Panics</a></h5> |
| <p>Panics if <code>decompressed</code>’s len is not exactly <code>BLOCK_LEN</code>.</p> |
| </div></details></div><h2 id="provided-methods" class="small-section-header">Provided Methods<a href="#provided-methods" class="anchor"></a></h2><div class="methods"><details class="rustdoc-toggle method-toggle" open><summary><section id="method.compressed_block_size" class="method has-srclink"><a class="srclink rightside" href="../src/bitpacking/lib.rs.html#260-262">source</a><h4 class="code-header">fn <a href="#method.compressed_block_size" class="fnname">compressed_block_size</a>(num_bits: u8) -> usize</h4></section></summary><div class="docblock"><p>Returns the size of a compressed block.</p> |
| </div></details></div><h2 id="implementors" class="small-section-header">Implementors<a href="#implementors" class="anchor"></a></h2><div id="implementors-list"><details class="rustdoc-toggle implementors-toggle"><summary><section id="impl-BitPacker-for-BitPacker4x" class="impl has-srclink"><a class="srclink rightside" href="../src/bitpacking/bitpacker4x_simple.rs.html#90-147">source</a><a href="#impl-BitPacker-for-BitPacker4x" class="anchor"></a><h3 class="code-header">impl <a class="trait" href="trait.BitPacker.html" title="trait bitpacking::BitPacker">BitPacker</a> for <a class="struct" href="struct.BitPacker4x.html" title="struct bitpacking::BitPacker4x">BitPacker4x</a></h3></section></summary><div class="impl-items"><section id="associatedconstant.BLOCK_LEN-1" class="associatedconstant trait-impl has-srclink"><a class="srclink rightside" href="../src/bitpacking/bitpacker4x_simple.rs.html#91">source</a><a href="#associatedconstant.BLOCK_LEN-1" class="anchor"></a><h4 class="code-header">const <a href="#associatedconstant.BLOCK_LEN" class="constant">BLOCK_LEN</a>: usize = 128usize</h4></section></div></details></div><script src="../implementors/bitpacking/trait.BitPacker.js" async></script></section></div></main><div id="rustdoc-vars" data-root-path="../" data-current-crate="bitpacking" data-themes="ayu,dark,light" data-resource-suffix="" data-rustdoc-version="1.66.0-nightly (5c8bff74b 2022-10-21)" ></div></body></html> |