src/libserialize/leb128.rs

   1 // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 #[inline]
  12 pub fn write_to_vec(vec: &mut Vec<u8>, byte: u8) {
  13     vec.push(byte);
  14 }
  15
  16 #[cfg(target_pointer_width = "32")]
  17 const USIZE_LEB128_SIZE: usize = 5;
  18 #[cfg(target_pointer_width = "64")]
  19 const USIZE_LEB128_SIZE: usize = 10;
  20
  21 macro_rules! leb128_size {
  22     (u16) => (3);
  23     (u32) => (5);
  24     (u64) => (10);
  25     (u128) => (19);
  26     (usize) => (USIZE_LEB128_SIZE);
  27 }
  28
  29 macro_rules! impl_write_unsigned_leb128 {
  30     ($fn_name:ident, $int_ty:ident) => (
  31         #[inline]
  32         pub fn $fn_name(out: &mut Vec<u8>, mut value: $int_ty) {
  33             for _ in 0 .. leb128_size!($int_ty) {
  34                 let mut byte = (value & 0x7F) as u8;
  35                 value >>= 7;
  36                 if value != 0 {
  37                     byte |= 0x80;
  38                 }
  39
  40                 write_to_vec(out, byte);
  41
  42                 if value == 0 {
  43                     break;
  44                 }
  45             }
  46         }
  47     )
  48 }
  49
  50 impl_write_unsigned_leb128!(write_u16_leb128, u16);
  51 impl_write_unsigned_leb128!(write_u32_leb128, u32);
  52 impl_write_unsigned_leb128!(write_u64_leb128, u64);
  53 impl_write_unsigned_leb128!(write_u128_leb128, u128);
  54 impl_write_unsigned_leb128!(write_usize_leb128, usize);
  55
  56
  57 macro_rules! impl_read_unsigned_leb128 {
  58     ($fn_name:ident, $int_ty:ident) => (
  59         #[inline]
  60         pub fn $fn_name(slice: &[u8]) -> ($int_ty, usize) {
  61             let mut result: $int_ty = 0;
  62             let mut shift = 0;
  63             let mut position = 0;
  64
  65             for _ in 0 .. leb128_size!($int_ty) {
  66                 let byte = unsafe {
  67                     *slice.get_unchecked(position)
  68                 };
  69                 position += 1;
  70                 result |= ((byte & 0x7F) as $int_ty) << shift;
  71                 if (byte & 0x80) == 0 {
  72                     break;
  73                 }
  74                 shift += 7;
  75             }
  76
  77             // Do a single bounds check at the end instead of for every byte.
  78             assert!(position <= slice.len());
  79
  80             (result, position)
  81         }
  82     )
  83 }
  84
  85 impl_read_unsigned_leb128!(read_u16_leb128, u16);
  86 impl_read_unsigned_leb128!(read_u32_leb128, u32);
  87 impl_read_unsigned_leb128!(read_u64_leb128, u64);
  88 impl_read_unsigned_leb128!(read_u128_leb128, u128);
  89 impl_read_unsigned_leb128!(read_usize_leb128, usize);
  90
  91
  92
  93 #[inline]
  94 /// encodes an integer using signed leb128 encoding and stores
  95 /// the result using a callback function.
  96 ///
  97 /// The callback `write` is called once for each position
  98 /// that is to be written to with the byte to be encoded
  99 /// at that position.
 100 pub fn write_signed_leb128_to<W>(mut value: i128, mut write: W)
 101     where W: FnMut(u8)
 102 {
 103     loop {
 104         let mut byte = (value as u8) & 0x7f;
 105         value >>= 7;
 106         let more = !(((value == 0) && ((byte & 0x40) == 0)) ||
 107                      ((value == -1) && ((byte & 0x40) != 0)));
 108
 109         if more {
 110             byte |= 0x80; // Mark this byte to show that more bytes will follow.
 111         }
 112
 113         write(byte);
 114
 115         if !more {
 116             break;
 117         }
 118     }
 119 }
 120
 121 #[inline]
 122 pub fn write_signed_leb128(out: &mut Vec<u8>, value: i128) {
 123     write_signed_leb128_to(value, |v| write_to_vec(out, v))
 124 }
 125
 126 #[inline]
 127 pub fn read_signed_leb128(data: &[u8], start_position: usize) -> (i128, usize) {
 128     let mut result = 0;
 129     let mut shift = 0;
 130     let mut position = start_position;
 131     let mut byte;
 132
 133     loop {
 134         byte = data[position];
 135         position += 1;
 136         result |= ((byte & 0x7F) as i128) << shift;
 137         shift += 7;
 138
 139         if (byte & 0x80) == 0 {
 140             break;
 141         }
 142     }
 143
 144     if (shift < 64) && ((byte & 0x40) != 0) {
 145         // sign extend
 146         result |= -(1 << shift);
 147     }
 148
 149     (result, position - start_position)
 150 }
 151
 152 macro_rules! impl_test_unsigned_leb128 {
 153     ($test_name:ident, $write_fn_name:ident, $read_fn_name:ident, $int_ty:ident) => (
 154         #[test]
 155         fn $test_name() {
 156             let mut stream = Vec::new();
 157
 158             for x in 0..62 {
 159                 $write_fn_name(&mut stream, (3u64 << x) as $int_ty);
 160             }
 161
 162             let mut position = 0;
 163             for x in 0..62 {
 164                 let expected = (3u64 << x) as $int_ty;
 165                 let (actual, bytes_read) = $read_fn_name(&stream[position ..]);
 166                 assert_eq!(expected, actual);
 167                 position += bytes_read;
 168             }
 169             assert_eq!(stream.len(), position);
 170         }
 171     )
 172 }
 173
 174 impl_test_unsigned_leb128!(test_u16_leb128, write_u16_leb128, read_u16_leb128, u16);
 175 impl_test_unsigned_leb128!(test_u32_leb128, write_u32_leb128, read_u32_leb128, u32);
 176 impl_test_unsigned_leb128!(test_u64_leb128, write_u64_leb128, read_u64_leb128, u64);
 177 impl_test_unsigned_leb128!(test_u128_leb128, write_u128_leb128, read_u128_leb128, u128);
 178 impl_test_unsigned_leb128!(test_usize_leb128, write_usize_leb128, read_usize_leb128, usize);
 179
 180 #[test]
 181 fn test_signed_leb128() {
 182     let values: Vec<_> = (-500..500).map(|i| i * 0x12345789ABCDEF).collect();
 183     let mut stream = Vec::new();
 184     for &x in &values {
 185         write_signed_leb128(&mut stream, x);
 186     }
 187     let mut pos = 0;
 188     for &x in &values {
 189         let (value, bytes_read) = read_signed_leb128(&mut stream, pos);
 190         pos += bytes_read;
 191         assert_eq!(x, value);
 192     }
 193     assert_eq!(pos, stream.len());
 194 }