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>, position: &mut usize, byte: u8) {
  13     if *position == vec.len() {
  14         vec.push(byte);
  15     } else {
  16         vec[*position] = byte;
  17     }
  18
  19     *position += 1;
  20 }
  21
  22 pub fn write_unsigned_leb128(out: &mut Vec<u8>, start_position: usize, mut value: u64) -> usize {
  23     let mut position = start_position;
  24     loop {
  25         let mut byte = (value & 0x7F) as u8;
  26         value >>= 7;
  27         if value != 0 {
  28             byte |= 0x80;
  29         }
  30
  31         write_to_vec(out, &mut position, byte);
  32
  33         if value == 0 {
  34             break;
  35         }
  36     }
  37
  38     return position - start_position;
  39 }
  40
  41 #[inline]
  42 pub fn read_unsigned_leb128(data: &[u8], start_position: usize) -> (u64, usize) {
  43     let mut result = 0;
  44     let mut shift = 0;
  45     let mut position = start_position;
  46     loop {
  47         let byte = data[position];
  48         position += 1;
  49         result |= ((byte & 0x7F) as u64) << shift;
  50         if (byte & 0x80) == 0 {
  51             break;
  52         }
  53         shift += 7;
  54     }
  55
  56     (result, position - start_position)
  57 }
  58
  59
  60 pub fn write_signed_leb128(out: &mut Vec<u8>, start_position: usize, mut value: i64) -> usize {
  61     let mut position = start_position;
  62
  63     loop {
  64         let mut byte = (value as u8) & 0x7f;
  65         value >>= 7;
  66         let more = !((((value == 0) && ((byte & 0x40) == 0)) ||
  67                       ((value == -1) && ((byte & 0x40) != 0))));
  68         if more {
  69             byte |= 0x80; // Mark this byte to show that more bytes will follow.
  70         }
  71
  72         write_to_vec(out, &mut position, byte);
  73
  74         if !more {
  75             break;
  76         }
  77     }
  78
  79     return position - start_position;
  80 }
  81
  82 #[inline]
  83 pub fn read_signed_leb128(data: &[u8], start_position: usize) -> (i64, usize) {
  84     let mut result = 0;
  85     let mut shift = 0;
  86     let mut position = start_position;
  87     let mut byte;
  88
  89     loop {
  90         byte = data[position];
  91         position += 1;
  92         result |= ((byte & 0x7F) as i64) << shift;
  93         shift += 7;
  94
  95         if (byte & 0x80) == 0 {
  96             break;
  97         }
  98     }
  99
 100     if (shift < 64) && ((byte & 0x40) != 0) {
 101         // sign extend
 102         result |= -(1i64 << shift);
 103     }
 104
 105     (result, position - start_position)
 106 }
 107
 108 #[test]
 109 fn test_unsigned_leb128() {
 110     let mut stream = Vec::with_capacity(10000);
 111
 112     for x in 0..62 {
 113         let pos = stream.len();
 114         let bytes_written = write_unsigned_leb128(&mut stream, pos, 3 << x);
 115         assert_eq!(stream.len(), pos + bytes_written);
 116     }
 117
 118     let mut position = 0;
 119     for x in 0..62 {
 120         let expected = 3 << x;
 121         let (actual, bytes_read) = read_unsigned_leb128(&stream, position);
 122         assert_eq!(expected, actual);
 123         position += bytes_read;
 124     }
 125     assert_eq!(stream.len(), position);
 126 }
 127
 128 #[test]
 129 fn test_signed_leb128() {
 130     let mut values = Vec::new();
 131
 132     let mut i = -500;
 133     while i < 500 {
 134         values.push(i * 123457i64);
 135         i += 1;
 136     }
 137
 138     let mut stream = Vec::new();
 139
 140     for &x in &values {
 141         let pos = stream.len();
 142         let bytes_written = write_signed_leb128(&mut stream, pos, x);
 143         assert_eq!(stream.len(), pos + bytes_written);
 144     }
 145
 146     let mut pos = 0;
 147     for &x in &values {
 148         let (value, bytes_read) = read_signed_leb128(&mut stream, pos);
 149         pos += bytes_read;
 150         assert_eq!(x, value);
 151     }
 152     assert_eq!(pos, stream.len());
 153 }