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 fn write_to_vec(vec: &mut Vec<u8>, position: usize, byte: u8) {
  13     if position == vec.len() {
  14         vec.push(byte);
  15     } else {
  16         vec[position] = byte;
  17     }
  18 }
  19
  20 #[inline]
  21 /// encodes an integer using unsigned leb128 encoding and stores
  22 /// the result using a callback function.
  23 ///
  24 /// The callback `write` is called once for each position
  25 /// that is to be written to with the byte to be encoded
  26 /// at that position.
  27 pub fn write_unsigned_leb128_to<W>(mut value: u128, mut write: W) -> usize
  28     where W: FnMut(usize, u8)
  29 {
  30     let mut position = 0;
  31     loop {
  32         let mut byte = (value & 0x7F) as u8;
  33         value >>= 7;
  34         if value != 0 {
  35             byte |= 0x80;
  36         }
  37
  38         write(position, byte);
  39         position += 1;
  40
  41         if value == 0 {
  42             break;
  43         }
  44     }
  45
  46     position
  47 }
  48
  49 pub fn write_unsigned_leb128(out: &mut Vec<u8>, start_position: usize, value: u128) -> usize {
  50     write_unsigned_leb128_to(value, |i, v| write_to_vec(out, start_position+i, v))
  51 }
  52
  53 #[inline]
  54 pub fn read_unsigned_leb128(data: &[u8], start_position: usize) -> (u128, usize) {
  55     let mut result = 0;
  56     let mut shift = 0;
  57     let mut position = start_position;
  58     loop {
  59         let byte = data[position];
  60         position += 1;
  61         result |= ((byte & 0x7F) as u128) << shift;
  62         if (byte & 0x80) == 0 {
  63             break;
  64         }
  65         shift += 7;
  66     }
  67
  68     (result, position - start_position)
  69 }
  70
  71 #[inline]
  72 /// encodes an integer using signed leb128 encoding and stores
  73 /// the result using a callback function.
  74 ///
  75 /// The callback `write` is called once for each position
  76 /// that is to be written to with the byte to be encoded
  77 /// at that position.
  78 pub fn write_signed_leb128_to<W>(mut value: i128, mut write: W) -> usize
  79     where W: FnMut(usize, u8)
  80 {
  81     let mut position = 0;
  82
  83     loop {
  84         let mut byte = (value as u8) & 0x7f;
  85         value >>= 7;
  86         let more = !((((value == 0) && ((byte & 0x40) == 0)) ||
  87                       ((value == -1) && ((byte & 0x40) != 0))));
  88
  89         if more {
  90             byte |= 0x80; // Mark this byte to show that more bytes will follow.
  91         }
  92
  93         write(position, byte);
  94         position += 1;
  95
  96         if !more {
  97             break;
  98         }
  99     }
 100     position
 101 }
 102
 103 pub fn write_signed_leb128(out: &mut Vec<u8>, start_position: usize, value: i128) -> usize {
 104     write_signed_leb128_to(value, |i, v| write_to_vec(out, start_position+i, v))
 105 }
 106
 107 #[inline]
 108 pub fn read_signed_leb128(data: &[u8], start_position: usize) -> (i128, usize) {
 109     let mut result = 0;
 110     let mut shift = 0;
 111     let mut position = start_position;
 112     let mut byte;
 113
 114     loop {
 115         byte = data[position];
 116         position += 1;
 117         result |= ((byte & 0x7F) as i128) << shift;
 118         shift += 7;
 119
 120         if (byte & 0x80) == 0 {
 121             break;
 122         }
 123     }
 124
 125     if (shift < 64) && ((byte & 0x40) != 0) {
 126         // sign extend
 127         result |= -(1 << shift);
 128     }
 129
 130     (result, position - start_position)
 131 }
 132
 133 #[test]
 134 fn test_unsigned_leb128() {
 135     let mut stream = Vec::with_capacity(10000);
 136
 137     for x in 0..62 {
 138         let pos = stream.len();
 139         let bytes_written = write_unsigned_leb128(&mut stream, pos, 3 << x);
 140         assert_eq!(stream.len(), pos + bytes_written);
 141     }
 142
 143     let mut position = 0;
 144     for x in 0..62 {
 145         let expected = 3 << x;
 146         let (actual, bytes_read) = read_unsigned_leb128(&stream, position);
 147         assert_eq!(expected, actual);
 148         position += bytes_read;
 149     }
 150     assert_eq!(stream.len(), position);
 151 }
 152
 153 #[test]
 154 fn test_signed_leb128() {
 155     let values: Vec<_> = (-500..500).map(|i| i * 0x12345789ABCDEF).collect();
 156     let mut stream = Vec::new();
 157     for &x in &values {
 158         let pos = stream.len();
 159         let bytes_written = write_signed_leb128(&mut stream, pos, x);
 160         assert_eq!(stream.len(), pos + bytes_written);
 161     }
 162     let mut pos = 0;
 163     for &x in &values {
 164         let (value, bytes_read) = read_signed_leb128(&mut stream, pos);
 165         pos += bytes_read;
 166         assert_eq!(x, value);
 167     }
 168     assert_eq!(pos, stream.len());
 169 }