src/libserialize/leb128.rs

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