1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322
//! Encode and decode `u32`s with the Stream VByte format. //! //! There are two traits, `Encoder` and `Decoder`, that allow you to choose what logic to use in the //! inner hot loops. //! //! # The simple, pretty fast way //! //! Use `Scalar` for your `Encoder` and `Decoder`. It will work on all hardware, and is fast enough //! that most people will probably never notice the time taken to encode/decode. //! //! # The more complex, really fast way //! //! If you can use nightly Rust (currently needed for SIMD) and you know which hardware you'll be //! running on, or you can add runtime detection of CPU features, you can choose to use an //! implementation that takes advantage of your hardware. Something like //! [raw-cpuid](https://crates.io/crates/raw-cpuid) will probably be useful for runtime detection. //! //! Performance numbers are calculated on an E5-1650v3 on encoding/decoding 1 million random numbers //! at a time. You can run the benchmarks yourself to see how your hardware does. //! //! Both `feature`s and `target_feature`s are used because `target_feature` is not in stable Rust //! yet and this library should remain usable by stable Rust, so non-stable-friendly things are //! hidden behind `feature`s. //! //! ## Encoders //! //! | Type | Performance | Hardware | `target_feature` | `feature` | //! | -------------- | ---------------| ---------------------------------------- | ---------------- | ----------- | //! | `Scalar` | ≈140 million/s | All | none | none | //! | `x86::Sse41` | ≈1 billion/s | x86 with SSE4.1 (Penryn and above, 2008) | `sse4.1` | `x86_sse41` | //! //! ## Decoders //! //! | Type | Performance | Hardware | `target_feature` | `feature` | //! | -------------- | ---------------| ------------------------------------------ | ---------------- | ----------- | //! | `Scalar` | ≈140 million/s | All | none | none | //! | `x86::Ssse3` | ≈2.7 billion/s | x86 with SSSE3 (Woodcrest and above, 2006) | `ssse3` | `x86_ssse3` | //! //! If you have a modern x86 and you want to use the all SIMD accelerated versions, you would use //! `target_feature` in a compiler invocation like this: //! //! ```sh //! RUSTFLAGS='-C target-feature=+ssse3,+sse4.1' cargo ... //! ``` //! //! Meanwhile, `feature`s for your dependency on this crate are specified //! [in your project's Cargo.toml](http://doc.crates.io/manifest.html#the-features-section). //! //! # Example //! //! ``` //! use stream_vbyte::*; //! //! let nums: Vec<u32> = (0..12_345).collect(); //! let mut encoded_data = Vec::new(); //! // make some space to encode into //! encoded_data.resize(5 * nums.len(), 0x0); //! //! // use Scalar implementation that works on any hardware //! let encoded_len = encode::<Scalar>(&nums, &mut encoded_data); //! println!("Encoded {} u32s into {} bytes", nums.len(), encoded_len); //! //! // decode all the numbers at once //! let mut decoded_nums = Vec::new(); //! decoded_nums.resize(nums.len(), 0); //! let bytes_decoded = decode::<Scalar>(&encoded_data, nums.len(), &mut decoded_nums); //! assert_eq!(nums, decoded_nums); //! assert_eq!(encoded_len, bytes_decoded); //! //! // or maybe you want to skip some of the numbers while decoding //! decoded_nums.clear(); //! decoded_nums.resize(nums.len(), 0); //! let mut cursor = DecodeCursor::new(&encoded_data, nums.len()); //! cursor.skip(10_000); //! let count = cursor.decode::<Scalar>(&mut decoded_nums); //! assert_eq!(12_345 - 10_000, count); //! assert_eq!(&nums[10_000..], &decoded_nums[0..count]); //! assert_eq!(encoded_len, cursor.input_consumed()); //! ``` //! //! # Panics //! //! If you use undersized slices (e.g. encoding 10 numbers into 5 bytes), you will get the normal //! slice bounds check panics. //! //! # Safety //! //! SIMD code uses unsafe internally because many of the SIMD intrinsics are unsafe. //! //! The `Scalar` codec does not use unsafe. //! //! extern crate byteorder; use std::cmp; use byteorder::{ByteOrder, LittleEndian}; mod tables; mod cursor; pub use cursor::DecodeCursor; #[path="x86/x86.rs"] pub mod x86; /// Encode numbers to bytes. pub trait Encoder { /// Encode complete quads of input numbers. /// /// `control_bytes` will be exactly as long as the number of complete 4-number quads in `input`. /// /// Control bytes are written to `control_bytes` and encoded numbers to `output`. /// /// Implementations may choose to encode fewer than the full provided input, but any writes done /// must be for full quads. /// /// Implementations must not write to `output` outside of the area that will be populated by /// encoded numbers when all control bytes are processed.. /// /// Returns the number of numbers encoded and the number of bytes written to `output`. fn encode_quads(input: &[u32], control_bytes: &mut [u8], output: &mut [u8]) -> (usize, usize); } /// Decode bytes to numbers. pub trait Decoder { /// Decode encoded numbers in complete quads. /// /// Only control bytes with 4 corresponding encoded numbers will be provided as input (i.e. no /// trailing partial quad). /// /// `control_bytes` are the control bytes that correspond to `encoded_nums`. /// /// `output` is the buffer to write decoded numbers into, and must be at least /// `control_bytes_to_decode * 4` in length. /// /// `control_bytes_to_decode * 4` may be greater than the number of control bytes remaining. /// /// Implementations may decode at most `control_bytes_to_decode` control bytes, but may decode /// fewer. /// /// Implementations must not write to `output` outside of the area that will be populated by /// decoded numbers when all control bytes are processed.. /// /// Returns the number of numbers decoded into `output` and the number of bytes read from /// `encoded_nums`. fn decode_quads(control_bytes: &[u8], encoded_nums: &[u8], output: &mut [u32], control_bytes_to_decode: usize) -> (usize, usize); } /// Encoder/Decoder that works on every platform, at the cost of speed compared to the SIMD accelerated versions. pub struct Scalar; impl Encoder for Scalar { // This implementation encodes all provided input numbers. fn encode_quads(input: &[u32], control_bytes: &mut [u8], encoded_nums: &mut [u8]) -> (usize, usize) { let mut bytes_written = 0; let mut nums_encoded = 0; for quads_encoded in 0..control_bytes.len() { let num0 = input[nums_encoded]; let num1 = input[nums_encoded + 1]; let num2 = input[nums_encoded + 2]; let num3 = input[nums_encoded + 3]; let len0 = encode_num_scalar(num0, &mut encoded_nums[bytes_written..]); let len1 = encode_num_scalar(num1, &mut encoded_nums[bytes_written + len0..]); let len2 = encode_num_scalar(num2, &mut encoded_nums[bytes_written + len0 + len1..]); let len3 = encode_num_scalar(num3, &mut encoded_nums[bytes_written + len0 + len1 + len2..]); // this is a few percent faster in my testing than using control_bytes.iter_mut() control_bytes[quads_encoded] = ((len0 - 1) | (len1 - 1) << 2 | (len2 - 1) << 4 | (len3 - 1) << 6) as u8; bytes_written += len0 + len1 + len2 + len3; nums_encoded += 4; } (nums_encoded, bytes_written) } } impl Decoder for Scalar { // This implementation decodes all provided encoded data. fn decode_quads(control_bytes: &[u8], encoded_nums: &[u8], output: &mut [u32], control_bytes_to_decode: usize) -> (usize, usize) { debug_assert!(control_bytes_to_decode * 4 <= output.len()); let mut bytes_read: usize = 0; let mut nums_decoded: usize = 0; let control_byte_limit = cmp::min(control_bytes.len(), control_bytes_to_decode); for &control_byte in control_bytes[0..control_byte_limit].iter() { let (len0, len1, len2, len3) = tables::DECODE_LENGTH_PER_NUM_TABLE[control_byte as usize]; let len0 = len0 as usize; let len1 = len1 as usize; let len2 = len2 as usize; let len3 = len3 as usize; output[nums_decoded] = decode_num_scalar(len0, &encoded_nums[bytes_read..]); output[nums_decoded + 1] = decode_num_scalar(len1, &encoded_nums[bytes_read + len0..]); output[nums_decoded + 2] = decode_num_scalar(len2, &encoded_nums[bytes_read + len0 + len1..]); output[nums_decoded + 3] = decode_num_scalar(len3, &encoded_nums[bytes_read + len0 + len1 + len2..]); bytes_read += len0 + len1 + len2 + len3; nums_decoded += 4; } (nums_decoded, bytes_read) } } /// Encode the `input` slice into the `output` slice. /// /// If you don't have specific knowledge of the input that would let you determine the encoded /// length ahead of time, make `output` 5x as long as `input`. The worst-case encoded length is 4 /// bytes per `u32` plus another byte for every 4 `u32`s, including any trailing partial 4-some. /// /// Returns the number of bytes written to the `output` slice. pub fn encode<E: Encoder>(input: &[u32], output: &mut [u8]) -> usize { if input.len() == 0 { return 0; } let shape = encoded_shape(input.len()); let (control_bytes, encoded_bytes) = output.split_at_mut(shape.control_bytes_len); let (nums_encoded, mut num_bytes_written) = E::encode_quads(&input[..], &mut control_bytes[0..shape.complete_control_bytes_len], &mut encoded_bytes[..]); // may be some input left, use Scalar to finish it let control_bytes_written = nums_encoded / 4; let (more_nums_encoded, more_bytes_written) = Scalar::encode_quads(&input[nums_encoded..], &mut control_bytes[control_bytes_written..shape.complete_control_bytes_len], &mut encoded_bytes[num_bytes_written..]); num_bytes_written += more_bytes_written; debug_assert_eq!(shape.complete_control_bytes_len * 4, nums_encoded + more_nums_encoded); // last control byte, if there were leftovers if shape.leftover_numbers > 0 { let mut control_byte = 0; let mut nums_encoded = shape.complete_control_bytes_len * 4; for i in 0..shape.leftover_numbers { let num = input[nums_encoded]; let len = encode_num_scalar(num, &mut encoded_bytes[num_bytes_written..]); control_byte |= ((len - 1) as u8) << (i * 2); num_bytes_written += len; nums_encoded += 1; } control_bytes[shape.complete_control_bytes_len] = control_byte; } control_bytes.len() + num_bytes_written } /// Decode `count` numbers from `input`, writing them to `output`. /// /// The `count` must be the same as the number of items originally encoded. /// /// `output` must be at least of size 4, and must be large enough for all `count` numbers. /// /// Returns the number of bytes read from `input`. pub fn decode<D: Decoder>(input: &[u8], count: usize, output: &mut [u32]) -> usize { let mut cursor = DecodeCursor::new(&input, count); assert_eq!(count, cursor.decode::<D>(output), "output buffer was not large enough"); cursor.input_consumed() } #[derive(Debug, PartialEq)] struct EncodedShape { control_bytes_len: usize, complete_control_bytes_len: usize, leftover_numbers: usize } fn encoded_shape(count: usize) -> EncodedShape { EncodedShape { control_bytes_len: (count + 3) / 4, complete_control_bytes_len: count / 4, leftover_numbers: count % 4 } } fn encode_num_scalar(num: u32, output: &mut [u8]) -> usize { // this will calculate 0_u32 as taking 0 bytes, so ensure at least 1 byte let len = cmp::max(1_usize, 4 - num.leading_zeros() as usize / 8); let mut buf = [0_u8; 4]; LittleEndian::write_u32(&mut buf, num); for i in 0..len { output[i] = buf[i]; } len } fn decode_num_scalar(len: usize, input: &[u8]) -> u32 { let mut buf = [0_u8; 4]; &buf[0..len].copy_from_slice(&input[0..len]); LittleEndian::read_u32(&buf) } fn cumulative_encoded_len(control_bytes: &[u8]) -> usize { // sum could only overflow with an invalid encoding because the sum can be no larger than // the complete length of the encoded data, which fits in a usize control_bytes.iter() .map({ |&b| tables::DECODE_LENGTH_PER_QUAD_TABLE[b as usize] as usize }) .sum() } #[cfg(test)] mod tests;