src/libserialize/ebml.rs

   1 // Copyright 2012-2014 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 #![allow(missing_doc)]
  12
  13 use std::io;
  14 use std::str;
  15
  16 // Simple Extensible Binary Markup Language (ebml) reader and writer on a
  17 // cursor model. See the specification here:
  18 //     http://www.matroska.org/technical/specs/rfc/index.html
  19
  20 // Common data structures
  21 #[deriving(Clone)]
  22 pub struct Doc<'a> {
  23     pub data: &'a [u8],
  24     pub start: uint,
  25     pub end: uint,
  26 }
  27
  28 impl<'doc> Doc<'doc> {
  29     pub fn new(data: &'doc [u8]) -> Doc<'doc> {
  30         Doc { data: data, start: 0u, end: data.len() }
  31     }
  32
  33     pub fn get<'a>(&'a self, tag: uint) -> Doc<'a> {
  34         reader::get_doc(*self, tag)
  35     }
  36
  37     pub fn as_str_slice<'a>(&'a self) -> &'a str {
  38         str::from_utf8(self.data.slice(self.start, self.end)).unwrap()
  39     }
  40
  41     pub fn as_str(&self) -> String {
  42         self.as_str_slice().to_string()
  43     }
  44 }
  45
  46 pub struct TaggedDoc<'a> {
  47     tag: uint,
  48     pub doc: Doc<'a>,
  49 }
  50
  51 #[deriving(Show)]
  52 pub enum EbmlEncoderTag {
  53     EsUint,     // 0
  54     EsU64,      // 1
  55     EsU32,      // 2
  56     EsU16,      // 3
  57     EsU8,       // 4
  58     EsInt,      // 5
  59     EsI64,      // 6
  60     EsI32,      // 7
  61     EsI16,      // 8
  62     EsI8,       // 9
  63     EsBool,     // 10
  64     EsChar,     // 11
  65     EsStr,      // 12
  66     EsF64,      // 13
  67     EsF32,      // 14
  68     EsFloat,    // 15
  69     EsEnum,     // 16
  70     EsEnumVid,  // 17
  71     EsEnumBody, // 18
  72     EsVec,      // 19
  73     EsVecLen,   // 20
  74     EsVecElt,   // 21
  75     EsMap,      // 22
  76     EsMapLen,   // 23
  77     EsMapKey,   // 24
  78     EsMapVal,   // 25
  79
  80     EsOpaque,
  81
  82     EsLabel, // Used only when debugging
  83 }
  84
  85 #[deriving(Show)]
  86 pub enum Error {
  87     IntTooBig(uint),
  88     Expected(String),
  89     IoError(io::IoError)
  90 }
  91 // --------------------------------------
  92
  93 pub mod reader {
  94     use std::char;
  95
  96     use std::mem::transmute;
  97     use std::int;
  98     use std::option::{None, Option, Some};
  99     use std::io::extensions::u64_from_be_bytes;
 100
 101     use serialize;
 102
 103     use super::{ EsVec, EsMap, EsEnum, EsVecLen, EsVecElt, EsMapLen, EsMapKey,
 104         EsEnumVid, EsU64, EsU32, EsU16, EsU8, EsInt, EsI64, EsI32, EsI16, EsI8,
 105         EsBool, EsF64, EsF32, EsChar, EsStr, EsMapVal, EsEnumBody, EsUint,
 106         EsOpaque, EsLabel, EbmlEncoderTag, Doc, TaggedDoc, Error, IntTooBig,
 107         Expected };
 108
 109     pub type DecodeResult<T> = Result<T, Error>;
 110     // ebml reading
 111
 112     macro_rules! try_or(
 113         ($e:expr, $r:expr) => (
 114             match $e {
 115                 Ok(e) => e,
 116                 Err(e) => {
 117                     debug!("ignored error: {}", e);
 118                     return $r
 119                 }
 120             }
 121         )
 122     )
 123
 124     pub struct Res {
 125         pub val: uint,
 126         pub next: uint
 127     }
 128
 129     #[inline(never)]
 130     fn vuint_at_slow(data: &[u8], start: uint) -> DecodeResult<Res> {
 131         let a = data[start];
 132         if a & 0x80u8 != 0u8 {
 133             return Ok(Res {val: (a & 0x7fu8) as uint, next: start + 1u});
 134         }
 135         if a & 0x40u8 != 0u8 {
 136             return Ok(Res {val: ((a & 0x3fu8) as uint) << 8u |
 137                         (data[start + 1u] as uint),
 138                     next: start + 2u});
 139         }
 140         if a & 0x20u8 != 0u8 {
 141             return Ok(Res {val: ((a & 0x1fu8) as uint) << 16u |
 142                         (data[start + 1u] as uint) << 8u |
 143                         (data[start + 2u] as uint),
 144                     next: start + 3u});
 145         }
 146         if a & 0x10u8 != 0u8 {
 147             return Ok(Res {val: ((a & 0x0fu8) as uint) << 24u |
 148                         (data[start + 1u] as uint) << 16u |
 149                         (data[start + 2u] as uint) << 8u |
 150                         (data[start + 3u] as uint),
 151                     next: start + 4u});
 152         }
 153         Err(IntTooBig(a as uint))
 154     }
 155
 156     pub fn vuint_at(data: &[u8], start: uint) -> DecodeResult<Res> {
 157         if data.len() - start < 4 {
 158             return vuint_at_slow(data, start);
 159         }
 160
 161         // Lookup table for parsing EBML Element IDs as per http://ebml.sourceforge.net/specs/
 162         // The Element IDs are parsed by reading a big endian u32 positioned at data[start].
 163         // Using the four most significant bits of the u32 we lookup in the table below how the
 164         // element ID should be derived from it.
 165         //
 166         // The table stores tuples (shift, mask) where shift is the number the u32 should be right
 167         // shifted with and mask is the value the right shifted value should be masked with.
 168         // If for example the most significant bit is set this means it's a class A ID and the u32
 169         // should be right shifted with 24 and masked with 0x7f. Therefore we store (24, 0x7f) at
 170         // index 0x8 - 0xF (four bit numbers where the most significant bit is set).
 171         //
 172         // By storing the number of shifts and masks in a table instead of checking in order if
 173         // the most significant bit is set, the second most significant bit is set etc. we can
 174         // replace up to three "and+branch" with a single table lookup which gives us a measured
 175         // speedup of around 2x on x86_64.
 176         static SHIFT_MASK_TABLE: [(uint, u32), ..16] = [
 177             (0, 0x0), (0, 0x0fffffff),
 178             (8, 0x1fffff), (8, 0x1fffff),
 179             (16, 0x3fff), (16, 0x3fff), (16, 0x3fff), (16, 0x3fff),
 180             (24, 0x7f), (24, 0x7f), (24, 0x7f), (24, 0x7f),
 181             (24, 0x7f), (24, 0x7f), (24, 0x7f), (24, 0x7f)
 182         ];
 183
 184         unsafe {
 185             let ptr = data.as_ptr().offset(start as int) as *const u32;
 186             let val = Int::from_be(*ptr);
 187
 188             let i = (val >> 28u) as uint;
 189             let (shift, mask) = SHIFT_MASK_TABLE[i];
 190             Ok(Res {
 191                 val: ((val >> shift) & mask) as uint,
 192                 next: start + (((32 - shift) >> 3) as uint)
 193             })
 194         }
 195     }
 196
 197     pub fn doc_at<'a>(data: &'a [u8], start: uint) -> DecodeResult<TaggedDoc<'a>> {
 198         let elt_tag = try!(vuint_at(data, start));
 199         let elt_size = try!(vuint_at(data, elt_tag.next));
 200         let end = elt_size.next + elt_size.val;
 201         Ok(TaggedDoc {
 202             tag: elt_tag.val,
 203             doc: Doc { data: data, start: elt_size.next, end: end }
 204         })
 205     }
 206
 207     pub fn maybe_get_doc<'a>(d: Doc<'a>, tg: uint) -> Option<Doc<'a>> {
 208         let mut pos = d.start;
 209         while pos < d.end {
 210             let elt_tag = try_or!(vuint_at(d.data, pos), None);
 211             let elt_size = try_or!(vuint_at(d.data, elt_tag.next), None);
 212             pos = elt_size.next + elt_size.val;
 213             if elt_tag.val == tg {
 214                 return Some(Doc { data: d.data, start: elt_size.next,
 215                                   end: pos });
 216             }
 217         }
 218         None
 219     }
 220
 221     pub fn get_doc<'a>(d: Doc<'a>, tg: uint) -> Doc<'a> {
 222         match maybe_get_doc(d, tg) {
 223             Some(d) => d,
 224             None => {
 225                 error!("failed to find block with tag {}", tg);
 226                 fail!();
 227             }
 228         }
 229     }
 230
 231     pub fn docs<'a>(d: Doc<'a>, it: |uint, Doc<'a>| -> bool) -> bool {
 232         let mut pos = d.start;
 233         while pos < d.end {
 234             let elt_tag = try_or!(vuint_at(d.data, pos), false);
 235             let elt_size = try_or!(vuint_at(d.data, elt_tag.next), false);
 236             pos = elt_size.next + elt_size.val;
 237             let doc = Doc { data: d.data, start: elt_size.next, end: pos };
 238             if !it(elt_tag.val, doc) {
 239                 return false;
 240             }
 241         }
 242         return true;
 243     }
 244
 245     pub fn tagged_docs<'a>(d: Doc<'a>, tg: uint, it: |Doc<'a>| -> bool) -> bool {
 246         let mut pos = d.start;
 247         while pos < d.end {
 248             let elt_tag = try_or!(vuint_at(d.data, pos), false);
 249             let elt_size = try_or!(vuint_at(d.data, elt_tag.next), false);
 250             pos = elt_size.next + elt_size.val;
 251             if elt_tag.val == tg {
 252                 let doc = Doc { data: d.data, start: elt_size.next,
 253                                 end: pos };
 254                 if !it(doc) {
 255                     return false;
 256                 }
 257             }
 258         }
 259         return true;
 260     }
 261
 262     pub fn with_doc_data<'a, T>(d: Doc<'a>, f: |x: &'a [u8]| -> T) -> T {
 263         f(d.data.slice(d.start, d.end))
 264     }
 265
 266
 267     pub fn doc_as_u8(d: Doc) -> u8 {
 268         assert_eq!(d.end, d.start + 1u);
 269         d.data[d.start]
 270     }
 271
 272     pub fn doc_as_u16(d: Doc) -> u16 {
 273         assert_eq!(d.end, d.start + 2u);
 274         u64_from_be_bytes(d.data, d.start, 2u) as u16
 275     }
 276
 277     pub fn doc_as_u32(d: Doc) -> u32 {
 278         assert_eq!(d.end, d.start + 4u);
 279         u64_from_be_bytes(d.data, d.start, 4u) as u32
 280     }
 281
 282     pub fn doc_as_u64(d: Doc) -> u64 {
 283         assert_eq!(d.end, d.start + 8u);
 284         u64_from_be_bytes(d.data, d.start, 8u)
 285     }
 286
 287     pub fn doc_as_i8(d: Doc) -> i8 { doc_as_u8(d) as i8 }
 288     pub fn doc_as_i16(d: Doc) -> i16 { doc_as_u16(d) as i16 }
 289     pub fn doc_as_i32(d: Doc) -> i32 { doc_as_u32(d) as i32 }
 290     pub fn doc_as_i64(d: Doc) -> i64 { doc_as_u64(d) as i64 }
 291
 292     pub struct Decoder<'a> {
 293         parent: Doc<'a>,
 294         pos: uint,
 295     }
 296
 297     impl<'doc> Decoder<'doc> {
 298         pub fn new(d: Doc<'doc>) -> Decoder<'doc> {
 299             Decoder {
 300                 parent: d,
 301                 pos: d.start
 302             }
 303         }
 304
 305         fn _check_label(&mut self, lbl: &str) -> DecodeResult<()> {
 306             if self.pos < self.parent.end {
 307                 let TaggedDoc { tag: r_tag, doc: r_doc } =
 308                     try!(doc_at(self.parent.data, self.pos));
 309
 310                 if r_tag == (EsLabel as uint) {
 311                     self.pos = r_doc.end;
 312                     let str = r_doc.as_str_slice();
 313                     if lbl != str {
 314                         return Err(Expected(format!("Expected label {} but \
 315                                                      found {}", lbl, str)));
 316                     }
 317                 }
 318             }
 319             Ok(())
 320         }
 321
 322         fn next_doc(&mut self, exp_tag: EbmlEncoderTag) -> DecodeResult<Doc<'doc>> {
 323             debug!(". next_doc(exp_tag={})", exp_tag);
 324             if self.pos >= self.parent.end {
 325                 return Err(Expected(format!("no more documents in \
 326                                              current node!")));
 327             }
 328             let TaggedDoc { tag: r_tag, doc: r_doc } =
 329                 try!(doc_at(self.parent.data, self.pos));
 330             debug!("self.parent={}-{} self.pos={} r_tag={} r_doc={}-{}",
 331                    self.parent.start,
 332                    self.parent.end,
 333                    self.pos,
 334                    r_tag,
 335                    r_doc.start,
 336                    r_doc.end);
 337             if r_tag != (exp_tag as uint) {
 338                 return Err(Expected(format!("expected EBML doc with tag {} but \
 339                                              found tag {}", exp_tag, r_tag)));
 340             }
 341             if r_doc.end > self.parent.end {
 342                 return Err(Expected(format!("invalid EBML, child extends to \
 343                                              {:#x}, parent to {:#x}",
 344                                             r_doc.end, self.parent.end)));
 345             }
 346             self.pos = r_doc.end;
 347             Ok(r_doc)
 348         }
 349
 350         fn push_doc<T>(&mut self, exp_tag: EbmlEncoderTag,
 351                        f: |&mut Decoder<'doc>| -> DecodeResult<T>) -> DecodeResult<T> {
 352             let d = try!(self.next_doc(exp_tag));
 353             let old_parent = self.parent;
 354             let old_pos = self.pos;
 355             self.parent = d;
 356             self.pos = d.start;
 357             let r = try!(f(self));
 358             self.parent = old_parent;
 359             self.pos = old_pos;
 360             Ok(r)
 361         }
 362
 363         fn _next_uint(&mut self, exp_tag: EbmlEncoderTag) -> DecodeResult<uint> {
 364             let r = doc_as_u32(try!(self.next_doc(exp_tag)));
 365             debug!("_next_uint exp_tag={} result={}", exp_tag, r);
 366             Ok(r as uint)
 367         }
 368
 369         pub fn read_opaque<R>(&mut self,
 370                               op: |&mut Decoder<'doc>, Doc| -> DecodeResult<R>) -> DecodeResult<R> {
 371             let doc = try!(self.next_doc(EsOpaque));
 372
 373             let (old_parent, old_pos) = (self.parent, self.pos);
 374             self.parent = doc;
 375             self.pos = doc.start;
 376
 377             let result = try!(op(self, doc));
 378
 379             self.parent = old_parent;
 380             self.pos = old_pos;
 381             Ok(result)
 382         }
 383     }
 384
 385     impl<'doc> serialize::Decoder<Error> for Decoder<'doc> {
 386         fn read_nil(&mut self) -> DecodeResult<()> { Ok(()) }
 387
 388         fn read_u64(&mut self) -> DecodeResult<u64> { Ok(doc_as_u64(try!(self.next_doc(EsU64)))) }
 389         fn read_u32(&mut self) -> DecodeResult<u32> { Ok(doc_as_u32(try!(self.next_doc(EsU32)))) }
 390         fn read_u16(&mut self) -> DecodeResult<u16> { Ok(doc_as_u16(try!(self.next_doc(EsU16)))) }
 391         fn read_u8 (&mut self) -> DecodeResult<u8 > { Ok(doc_as_u8 (try!(self.next_doc(EsU8 )))) }
 392         fn read_uint(&mut self) -> DecodeResult<uint> {
 393             let v = doc_as_u64(try!(self.next_doc(EsUint)));
 394             if v > (::std::uint::MAX as u64) {
 395                 Err(IntTooBig(v as uint))
 396             } else {
 397                 Ok(v as uint)
 398             }
 399         }
 400
 401         fn read_i64(&mut self) -> DecodeResult<i64> {
 402             Ok(doc_as_u64(try!(self.next_doc(EsI64))) as i64)
 403         }
 404         fn read_i32(&mut self) -> DecodeResult<i32> {
 405             Ok(doc_as_u32(try!(self.next_doc(EsI32))) as i32)
 406         }
 407         fn read_i16(&mut self) -> DecodeResult<i16> {
 408             Ok(doc_as_u16(try!(self.next_doc(EsI16))) as i16)
 409         }
 410         fn read_i8 (&mut self) -> DecodeResult<i8> {
 411             Ok(doc_as_u8(try!(self.next_doc(EsI8 ))) as i8)
 412         }
 413         fn read_int(&mut self) -> DecodeResult<int> {
 414             let v = doc_as_u64(try!(self.next_doc(EsInt))) as i64;
 415             if v > (int::MAX as i64) || v < (int::MIN as i64) {
 416                 debug!("FIXME \\#6122: Removing this makes this function miscompile");
 417                 Err(IntTooBig(v as uint))
 418             } else {
 419                 Ok(v as int)
 420             }
 421         }
 422
 423         fn read_bool(&mut self) -> DecodeResult<bool> {
 424             Ok(doc_as_u8(try!(self.next_doc(EsBool))) != 0)
 425         }
 426
 427         fn read_f64(&mut self) -> DecodeResult<f64> {
 428             let bits = doc_as_u64(try!(self.next_doc(EsF64)));
 429             Ok(unsafe { transmute(bits) })
 430         }
 431         fn read_f32(&mut self) -> DecodeResult<f32> {
 432             let bits = doc_as_u32(try!(self.next_doc(EsF32)));
 433             Ok(unsafe { transmute(bits) })
 434         }
 435         fn read_char(&mut self) -> DecodeResult<char> {
 436             Ok(char::from_u32(doc_as_u32(try!(self.next_doc(EsChar)))).unwrap())
 437         }
 438         fn read_str(&mut self) -> DecodeResult<String> {
 439             Ok(try!(self.next_doc(EsStr)).as_str())
 440         }
 441
 442         // Compound types:
 443         fn read_enum<T>(&mut self,
 444                         name: &str,
 445                         f: |&mut Decoder<'doc>| -> DecodeResult<T>) -> DecodeResult<T> {
 446             debug!("read_enum({})", name);
 447             try!(self._check_label(name));
 448
 449             let doc = try!(self.next_doc(EsEnum));
 450
 451             let (old_parent, old_pos) = (self.parent, self.pos);
 452             self.parent = doc;
 453             self.pos = self.parent.start;
 454
 455             let result = try!(f(self));
 456
 457             self.parent = old_parent;
 458             self.pos = old_pos;
 459             Ok(result)
 460         }
 461
 462         fn read_enum_variant<T>(&mut self,
 463                                 _: &[&str],
 464                                 f: |&mut Decoder<'doc>, uint| -> DecodeResult<T>)
 465                                 -> DecodeResult<T> {
 466             debug!("read_enum_variant()");
 467             let idx = try!(self._next_uint(EsEnumVid));
 468             debug!("  idx={}", idx);
 469
 470             let doc = try!(self.next_doc(EsEnumBody));
 471
 472             let (old_parent, old_pos) = (self.parent, self.pos);
 473             self.parent = doc;
 474             self.pos = self.parent.start;
 475
 476             let result = try!(f(self, idx));
 477
 478             self.parent = old_parent;
 479             self.pos = old_pos;
 480             Ok(result)
 481         }
 482
 483         fn read_enum_variant_arg<T>(&mut self,
 484                                     idx: uint,
 485                                     f: |&mut Decoder<'doc>| -> DecodeResult<T>) -> DecodeResult<T> {
 486             debug!("read_enum_variant_arg(idx={})", idx);
 487             f(self)
 488         }
 489
 490         fn read_enum_struct_variant<T>(&mut self,
 491                                        _: &[&str],
 492                                        f: |&mut Decoder<'doc>, uint| -> DecodeResult<T>)
 493                                        -> DecodeResult<T> {
 494             debug!("read_enum_struct_variant()");
 495             let idx = try!(self._next_uint(EsEnumVid));
 496             debug!("  idx={}", idx);
 497
 498             let doc = try!(self.next_doc(EsEnumBody));
 499
 500             let (old_parent, old_pos) = (self.parent, self.pos);
 501             self.parent = doc;
 502             self.pos = self.parent.start;
 503
 504             let result = try!(f(self, idx));
 505
 506             self.parent = old_parent;
 507             self.pos = old_pos;
 508             Ok(result)
 509         }
 510
 511         fn read_enum_struct_variant_field<T>(&mut self,
 512                                              name: &str,
 513                                              idx: uint,
 514                                              f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 515                                              -> DecodeResult<T> {
 516             debug!("read_enum_struct_variant_arg(name={}, idx={})", name, idx);
 517             f(self)
 518         }
 519
 520         fn read_struct<T>(&mut self,
 521                           name: &str,
 522                           _: uint,
 523                           f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 524                           -> DecodeResult<T> {
 525             debug!("read_struct(name={})", name);
 526             f(self)
 527         }
 528
 529         fn read_struct_field<T>(&mut self,
 530                                 name: &str,
 531                                 idx: uint,
 532                                 f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 533                                 -> DecodeResult<T> {
 534             debug!("read_struct_field(name={}, idx={})", name, idx);
 535             try!(self._check_label(name));
 536             f(self)
 537         }
 538
 539         fn read_tuple<T>(&mut self,
 540                          f: |&mut Decoder<'doc>, uint| -> DecodeResult<T>) -> DecodeResult<T> {
 541             debug!("read_tuple()");
 542             self.read_seq(f)
 543         }
 544
 545         fn read_tuple_arg<T>(&mut self, idx: uint, f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 546                              -> DecodeResult<T> {
 547             debug!("read_tuple_arg(idx={})", idx);
 548             self.read_seq_elt(idx, f)
 549         }
 550
 551         fn read_tuple_struct<T>(&mut self,
 552                                 name: &str,
 553                                 f: |&mut Decoder<'doc>, uint| -> DecodeResult<T>)
 554                                 -> DecodeResult<T> {
 555             debug!("read_tuple_struct(name={})", name);
 556             self.read_tuple(f)
 557         }
 558
 559         fn read_tuple_struct_arg<T>(&mut self,
 560                                     idx: uint,
 561                                     f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 562                                     -> DecodeResult<T> {
 563             debug!("read_tuple_struct_arg(idx={})", idx);
 564             self.read_tuple_arg(idx, f)
 565         }
 566
 567         fn read_option<T>(&mut self,
 568                           f: |&mut Decoder<'doc>, bool| -> DecodeResult<T>) -> DecodeResult<T> {
 569             debug!("read_option()");
 570             self.read_enum("Option", |this| {
 571                 this.read_enum_variant(["None", "Some"], |this, idx| {
 572                     match idx {
 573                         0 => f(this, false),
 574                         1 => f(this, true),
 575                         _ => {
 576                             Err(Expected(format!("Expected None or Some")))
 577                         }
 578                     }
 579                 })
 580             })
 581         }
 582
 583         fn read_seq<T>(&mut self,
 584                        f: |&mut Decoder<'doc>, uint| -> DecodeResult<T>) -> DecodeResult<T> {
 585             debug!("read_seq()");
 586             self.push_doc(EsVec, |d| {
 587                 let len = try!(d._next_uint(EsVecLen));
 588                 debug!("  len={}", len);
 589                 f(d, len)
 590             })
 591         }
 592
 593         fn read_seq_elt<T>(&mut self, idx: uint, f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 594                            -> DecodeResult<T> {
 595             debug!("read_seq_elt(idx={})", idx);
 596             self.push_doc(EsVecElt, f)
 597         }
 598
 599         fn read_map<T>(&mut self,
 600                        f: |&mut Decoder<'doc>, uint| -> DecodeResult<T>) -> DecodeResult<T> {
 601             debug!("read_map()");
 602             self.push_doc(EsMap, |d| {
 603                 let len = try!(d._next_uint(EsMapLen));
 604                 debug!("  len={}", len);
 605                 f(d, len)
 606             })
 607         }
 608
 609         fn read_map_elt_key<T>(&mut self, idx: uint, f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 610                                -> DecodeResult<T> {
 611             debug!("read_map_elt_key(idx={})", idx);
 612             self.push_doc(EsMapKey, f)
 613         }
 614
 615         fn read_map_elt_val<T>(&mut self, idx: uint, f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 616                                -> DecodeResult<T> {
 617             debug!("read_map_elt_val(idx={})", idx);
 618             self.push_doc(EsMapVal, f)
 619         }
 620     }
 621 }
 622
 623 pub mod writer {
 624     use std::clone::Clone;
 625     use std::io::extensions::u64_to_be_bytes;
 626     use std::io::{Writer, Seek};
 627     use std::io;
 628     use std::mem;
 629
 630     use super::{ EsVec, EsMap, EsEnum, EsVecLen, EsVecElt, EsMapLen, EsMapKey,
 631         EsEnumVid, EsU64, EsU32, EsU16, EsU8, EsInt, EsI64, EsI32, EsI16, EsI8,
 632         EsBool, EsF64, EsF32, EsChar, EsStr, EsMapVal, EsEnumBody, EsUint,
 633         EsOpaque, EsLabel, EbmlEncoderTag };
 634
 635     use serialize;
 636
 637
 638     pub type EncodeResult = io::IoResult<()>;
 639
 640     // ebml writing
 641     pub struct Encoder<'a, W> {
 642         pub writer: &'a mut W,
 643         size_positions: Vec<uint>,
 644     }
 645
 646     fn write_sized_vuint<W: Writer>(w: &mut W, n: uint, size: uint) -> EncodeResult {
 647         match size {
 648             1u => w.write(&[0x80u8 | (n as u8)]),
 649             2u => w.write(&[0x40u8 | ((n >> 8_u) as u8), n as u8]),
 650             3u => w.write(&[0x20u8 | ((n >> 16_u) as u8), (n >> 8_u) as u8,
 651                             n as u8]),
 652             4u => w.write(&[0x10u8 | ((n >> 24_u) as u8), (n >> 16_u) as u8,
 653                             (n >> 8_u) as u8, n as u8]),
 654             _ => Err(io::IoError {
 655                 kind: io::OtherIoError,
 656                 desc: "int too big",
 657                 detail: Some(format!("{}", n))
 658             })
 659         }
 660     }
 661
 662     fn write_vuint<W: Writer>(w: &mut W, n: uint) -> EncodeResult {
 663         if n < 0x7f_u { return write_sized_vuint(w, n, 1u); }
 664         if n < 0x4000_u { return write_sized_vuint(w, n, 2u); }
 665         if n < 0x200000_u { return write_sized_vuint(w, n, 3u); }
 666         if n < 0x10000000_u { return write_sized_vuint(w, n, 4u); }
 667         Err(io::IoError {
 668             kind: io::OtherIoError,
 669             desc: "int too big",
 670             detail: Some(format!("{}", n))
 671         })
 672     }
 673
 674     // FIXME (#2741): Provide a function to write the standard ebml header.
 675     impl<'a, W: Writer + Seek> Encoder<'a, W> {
 676         pub fn new(w: &'a mut W) -> Encoder<'a, W> {
 677             Encoder {
 678                 writer: w,
 679                 size_positions: vec!(),
 680             }
 681         }
 682
 683         /// FIXME(pcwalton): Workaround for badness in trans. DO NOT USE ME.
 684         pub unsafe fn unsafe_clone(&self) -> Encoder<'a, W> {
 685             Encoder {
 686                 writer: mem::transmute_copy(&self.writer),
 687                 size_positions: self.size_positions.clone(),
 688             }
 689         }
 690
 691         pub fn start_tag(&mut self, tag_id: uint) -> EncodeResult {
 692             debug!("Start tag {}", tag_id);
 693
 694             // Write the enum ID:
 695             try!(write_vuint(self.writer, tag_id));
 696
 697             // Write a placeholder four-byte size.
 698             self.size_positions.push(try!(self.writer.tell()) as uint);
 699             let zeroes: &[u8] = &[0u8, 0u8, 0u8, 0u8];
 700             self.writer.write(zeroes)
 701         }
 702
 703         pub fn end_tag(&mut self) -> EncodeResult {
 704             let last_size_pos = self.size_positions.pop().unwrap();
 705             let cur_pos = try!(self.writer.tell());
 706             try!(self.writer.seek(last_size_pos as i64, io::SeekSet));
 707             let size = cur_pos as uint - last_size_pos - 4;
 708             try!(write_sized_vuint(self.writer, size, 4u));
 709             let r = try!(self.writer.seek(cur_pos as i64, io::SeekSet));
 710
 711             debug!("End tag (size = {})", size);
 712             Ok(r)
 713         }
 714
 715         pub fn wr_tag(&mut self, tag_id: uint, blk: || -> EncodeResult) -> EncodeResult {
 716             try!(self.start_tag(tag_id));
 717             try!(blk());
 718             self.end_tag()
 719         }
 720
 721         pub fn wr_tagged_bytes(&mut self, tag_id: uint, b: &[u8]) -> EncodeResult {
 722             try!(write_vuint(self.writer, tag_id));
 723             try!(write_vuint(self.writer, b.len()));
 724             self.writer.write(b)
 725         }
 726
 727         pub fn wr_tagged_u64(&mut self, tag_id: uint, v: u64) -> EncodeResult {
 728             u64_to_be_bytes(v, 8u, |v| {
 729                 self.wr_tagged_bytes(tag_id, v)
 730             })
 731         }
 732
 733         pub fn wr_tagged_u32(&mut self, tag_id: uint, v: u32)  -> EncodeResult{
 734             u64_to_be_bytes(v as u64, 4u, |v| {
 735                 self.wr_tagged_bytes(tag_id, v)
 736             })
 737         }
 738
 739         pub fn wr_tagged_u16(&mut self, tag_id: uint, v: u16) -> EncodeResult {
 740             u64_to_be_bytes(v as u64, 2u, |v| {
 741                 self.wr_tagged_bytes(tag_id, v)
 742             })
 743         }
 744
 745         pub fn wr_tagged_u8(&mut self, tag_id: uint, v: u8) -> EncodeResult {
 746             self.wr_tagged_bytes(tag_id, &[v])
 747         }
 748
 749         pub fn wr_tagged_i64(&mut self, tag_id: uint, v: i64) -> EncodeResult {
 750             u64_to_be_bytes(v as u64, 8u, |v| {
 751                 self.wr_tagged_bytes(tag_id, v)
 752             })
 753         }
 754
 755         pub fn wr_tagged_i32(&mut self, tag_id: uint, v: i32) -> EncodeResult {
 756             u64_to_be_bytes(v as u64, 4u, |v| {
 757                 self.wr_tagged_bytes(tag_id, v)
 758             })
 759         }
 760
 761         pub fn wr_tagged_i16(&mut self, tag_id: uint, v: i16) -> EncodeResult {
 762             u64_to_be_bytes(v as u64, 2u, |v| {
 763                 self.wr_tagged_bytes(tag_id, v)
 764             })
 765         }
 766
 767         pub fn wr_tagged_i8(&mut self, tag_id: uint, v: i8) -> EncodeResult {
 768             self.wr_tagged_bytes(tag_id, &[v as u8])
 769         }
 770
 771         pub fn wr_tagged_str(&mut self, tag_id: uint, v: &str) -> EncodeResult {
 772             self.wr_tagged_bytes(tag_id, v.as_bytes())
 773         }
 774
 775         pub fn wr_bytes(&mut self, b: &[u8]) -> EncodeResult {
 776             debug!("Write {} bytes", b.len());
 777             self.writer.write(b)
 778         }
 779
 780         pub fn wr_str(&mut self, s: &str) -> EncodeResult {
 781             debug!("Write str: {}", s);
 782             self.writer.write(s.as_bytes())
 783         }
 784     }
 785
 786     // FIXME (#2743): optionally perform "relaxations" on end_tag to more
 787     // efficiently encode sizes; this is a fixed point iteration
 788
 789     // Set to true to generate more debugging in EBML code.
 790     // Totally lame approach.
 791     static DEBUG: bool = true;
 792
 793     impl<'a, W: Writer + Seek> Encoder<'a, W> {
 794         // used internally to emit things like the vector length and so on
 795         fn _emit_tagged_uint(&mut self, t: EbmlEncoderTag, v: uint) -> EncodeResult {
 796             assert!(v <= 0xFFFF_FFFF_u);
 797             self.wr_tagged_u32(t as uint, v as u32)
 798         }
 799
 800         fn _emit_label(&mut self, label: &str) -> EncodeResult {
 801             // There are various strings that we have access to, such as
 802             // the name of a record field, which do not actually appear in
 803             // the encoded EBML (normally).  This is just for
 804             // efficiency.  When debugging, though, we can emit such
 805             // labels and then they will be checked by decoder to
 806             // try and check failures more quickly.
 807             if DEBUG { self.wr_tagged_str(EsLabel as uint, label) }
 808             else { Ok(()) }
 809         }
 810
 811         pub fn emit_opaque(&mut self, f: |&mut Encoder<W>| -> EncodeResult) -> EncodeResult {
 812             try!(self.start_tag(EsOpaque as uint));
 813             try!(f(self));
 814             self.end_tag()
 815         }
 816     }
 817
 818     impl<'a, W: Writer + Seek> serialize::Encoder<io::IoError> for Encoder<'a, W> {
 819         fn emit_nil(&mut self) -> EncodeResult {
 820             Ok(())
 821         }
 822
 823         fn emit_uint(&mut self, v: uint) -> EncodeResult {
 824             self.wr_tagged_u64(EsUint as uint, v as u64)
 825         }
 826         fn emit_u64(&mut self, v: u64) -> EncodeResult {
 827             self.wr_tagged_u64(EsU64 as uint, v)
 828         }
 829         fn emit_u32(&mut self, v: u32) -> EncodeResult {
 830             self.wr_tagged_u32(EsU32 as uint, v)
 831         }
 832         fn emit_u16(&mut self, v: u16) -> EncodeResult {
 833             self.wr_tagged_u16(EsU16 as uint, v)
 834         }
 835         fn emit_u8(&mut self, v: u8) -> EncodeResult {
 836             self.wr_tagged_u8(EsU8 as uint, v)
 837         }
 838
 839         fn emit_int(&mut self, v: int) -> EncodeResult {
 840             self.wr_tagged_i64(EsInt as uint, v as i64)
 841         }
 842         fn emit_i64(&mut self, v: i64) -> EncodeResult {
 843             self.wr_tagged_i64(EsI64 as uint, v)
 844         }
 845         fn emit_i32(&mut self, v: i32) -> EncodeResult {
 846             self.wr_tagged_i32(EsI32 as uint, v)
 847         }
 848         fn emit_i16(&mut self, v: i16) -> EncodeResult {
 849             self.wr_tagged_i16(EsI16 as uint, v)
 850         }
 851         fn emit_i8(&mut self, v: i8) -> EncodeResult {
 852             self.wr_tagged_i8(EsI8 as uint, v)
 853         }
 854
 855         fn emit_bool(&mut self, v: bool) -> EncodeResult {
 856             self.wr_tagged_u8(EsBool as uint, v as u8)
 857         }
 858
 859         fn emit_f64(&mut self, v: f64) -> EncodeResult {
 860             let bits = unsafe { mem::transmute(v) };
 861             self.wr_tagged_u64(EsF64 as uint, bits)
 862         }
 863         fn emit_f32(&mut self, v: f32) -> EncodeResult {
 864             let bits = unsafe { mem::transmute(v) };
 865             self.wr_tagged_u32(EsF32 as uint, bits)
 866         }
 867         fn emit_char(&mut self, v: char) -> EncodeResult {
 868             self.wr_tagged_u32(EsChar as uint, v as u32)
 869         }
 870
 871         fn emit_str(&mut self, v: &str) -> EncodeResult {
 872             self.wr_tagged_str(EsStr as uint, v)
 873         }
 874
 875         fn emit_enum(&mut self,
 876                      name: &str,
 877                      f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 878             try!(self._emit_label(name));
 879             try!(self.start_tag(EsEnum as uint));
 880             try!(f(self));
 881             self.end_tag()
 882         }
 883
 884         fn emit_enum_variant(&mut self,
 885                              _: &str,
 886                              v_id: uint,
 887                              _: uint,
 888                              f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 889             try!(self._emit_tagged_uint(EsEnumVid, v_id));
 890             try!(self.start_tag(EsEnumBody as uint));
 891             try!(f(self));
 892             self.end_tag()
 893         }
 894
 895         fn emit_enum_variant_arg(&mut self,
 896                                  _: uint,
 897                                  f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 898             f(self)
 899         }
 900
 901         fn emit_enum_struct_variant(&mut self,
 902                                     v_name: &str,
 903                                     v_id: uint,
 904                                     cnt: uint,
 905                                     f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 906             self.emit_enum_variant(v_name, v_id, cnt, f)
 907         }
 908
 909         fn emit_enum_struct_variant_field(&mut self,
 910                                           _: &str,
 911                                           idx: uint,
 912                                           f: |&mut Encoder<'a, W>| -> EncodeResult)
 913             -> EncodeResult {
 914             self.emit_enum_variant_arg(idx, f)
 915         }
 916
 917         fn emit_struct(&mut self,
 918                        _: &str,
 919                        _len: uint,
 920                        f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 921             f(self)
 922         }
 923
 924         fn emit_struct_field(&mut self,
 925                              name: &str,
 926                              _: uint,
 927                              f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 928             try!(self._emit_label(name));
 929             f(self)
 930         }
 931
 932         fn emit_tuple(&mut self,
 933                       len: uint,
 934                       f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 935             self.emit_seq(len, f)
 936         }
 937         fn emit_tuple_arg(&mut self,
 938                           idx: uint,
 939                           f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 940             self.emit_seq_elt(idx, f)
 941         }
 942
 943         fn emit_tuple_struct(&mut self,
 944                              _: &str,
 945                              len: uint,
 946                              f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 947             self.emit_seq(len, f)
 948         }
 949         fn emit_tuple_struct_arg(&mut self,
 950                                  idx: uint,
 951                                  f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 952             self.emit_seq_elt(idx, f)
 953         }
 954
 955         fn emit_option(&mut self,
 956                        f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 957             self.emit_enum("Option", f)
 958         }
 959         fn emit_option_none(&mut self) -> EncodeResult {
 960             self.emit_enum_variant("None", 0, 0, |_| Ok(()))
 961         }
 962         fn emit_option_some(&mut self,
 963                             f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 964
 965             self.emit_enum_variant("Some", 1, 1, f)
 966         }
 967
 968         fn emit_seq(&mut self,
 969                     len: uint,
 970                     f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 971
 972             try!(self.start_tag(EsVec as uint));
 973             try!(self._emit_tagged_uint(EsVecLen, len));
 974             try!(f(self));
 975             self.end_tag()
 976         }
 977
 978         fn emit_seq_elt(&mut self,
 979                         _idx: uint,
 980                         f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 981
 982             try!(self.start_tag(EsVecElt as uint));
 983             try!(f(self));
 984             self.end_tag()
 985         }
 986
 987         fn emit_map(&mut self,
 988                     len: uint,
 989                     f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 990
 991             try!(self.start_tag(EsMap as uint));
 992             try!(self._emit_tagged_uint(EsMapLen, len));
 993             try!(f(self));
 994             self.end_tag()
 995         }
 996
 997         fn emit_map_elt_key(&mut self,
 998                             _idx: uint,
 999                             f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
1000
1001             try!(self.start_tag(EsMapKey as uint));
1002             try!(f(self));
1003             self.end_tag()
1004         }
1005
1006         fn emit_map_elt_val(&mut self,
1007                             _idx: uint,
1008                             f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
1009             try!(self.start_tag(EsMapVal as uint));
1010             try!(f(self));
1011             self.end_tag()
1012         }
1013     }
1014 }
1015
1016 // ___________________________________________________________________________
1017 // Testing
1018
1019 #[cfg(test)]
1020 mod tests {
1021     use super::Doc;
1022     use ebml::reader;
1023     use ebml::writer;
1024     use {Encodable, Decodable};
1025
1026     use std::io::{IoError, IoResult, SeekStyle};
1027     use std::io;
1028     use std::option::{None, Option, Some};
1029     use std::slice;
1030
1031     static BUF_CAPACITY: uint = 128;
1032
1033     fn combine(seek: SeekStyle, cur: uint, end: uint, offset: i64) -> IoResult<u64> {
1034         // compute offset as signed and clamp to prevent overflow
1035         let pos = match seek {
1036             io::SeekSet => 0,
1037             io::SeekEnd => end,
1038             io::SeekCur => cur,
1039         } as i64;
1040
1041         if offset + pos < 0 {
1042             Err(IoError {
1043                 kind: io::InvalidInput,
1044                 desc: "invalid seek to a negative offset",
1045                 detail: None
1046             })
1047         } else {
1048             Ok((offset + pos) as u64)
1049         }
1050     }
1051
1052     /// Writes to an owned, growable byte vector that supports seeking.
1053     ///
1054     /// # Example
1055     ///
1056     /// ```rust
1057     /// # #![allow(unused_must_use)]
1058     /// use std::io::SeekableMemWriter;
1059     ///
1060     /// let mut w = SeekableMemWriter::new();
1061     /// w.write([0, 1, 2]);
1062     ///
1063     /// assert_eq!(w.unwrap(), vec!(0, 1, 2));
1064     /// ```
1065     pub struct SeekableMemWriter {
1066         buf: Vec<u8>,
1067         pos: uint,
1068     }
1069
1070     impl SeekableMemWriter {
1071         /// Create a new `SeekableMemWriter`.
1072         #[inline]
1073         pub fn new() -> SeekableMemWriter {
1074             SeekableMemWriter::with_capacity(BUF_CAPACITY)
1075         }
1076         /// Create a new `SeekableMemWriter`, allocating at least `n` bytes for
1077         /// the internal buffer.
1078         #[inline]
1079         pub fn with_capacity(n: uint) -> SeekableMemWriter {
1080             SeekableMemWriter { buf: Vec::with_capacity(n), pos: 0 }
1081         }
1082
1083         /// Acquires an immutable reference to the underlying buffer of this
1084         /// `SeekableMemWriter`.
1085         ///
1086         /// No method is exposed for acquiring a mutable reference to the buffer
1087         /// because it could corrupt the state of this `MemWriter`.
1088         #[inline]
1089         pub fn get_ref<'a>(&'a self) -> &'a [u8] { self.buf.as_slice() }
1090
1091         /// Unwraps this `SeekableMemWriter`, returning the underlying buffer
1092         #[inline]
1093         pub fn unwrap(self) -> Vec<u8> { self.buf }
1094     }
1095
1096     impl Writer for SeekableMemWriter {
1097         #[inline]
1098         fn write(&mut self, buf: &[u8]) -> IoResult<()> {
1099             if self.pos == self.buf.len() {
1100                 self.buf.push_all(buf)
1101             } else {
1102                 // Make sure the internal buffer is as least as big as where we
1103                 // currently are
1104                 let difference = self.pos as i64 - self.buf.len() as i64;
1105                 if difference > 0 {
1106                     self.buf.grow(difference as uint, &0);
1107                 }
1108
1109                 // Figure out what bytes will be used to overwrite what's currently
1110                 // there (left), and what will be appended on the end (right)
1111                 let cap = self.buf.len() - self.pos;
1112                 let (left, right) = if cap <= buf.len() {
1113                     (buf.slice_to(cap), buf.slice_from(cap))
1114                 } else {
1115                     (buf, &[])
1116                 };
1117
1118                 // Do the necessary writes
1119                 if left.len() > 0 {
1120                     slice::bytes::copy_memory(self.buf.mut_slice_from(self.pos), left);
1121                 }
1122                 if right.len() > 0 {
1123                     self.buf.push_all(right);
1124                 }
1125             }
1126
1127             // Bump us forward
1128             self.pos += buf.len();
1129             Ok(())
1130         }
1131     }
1132
1133     impl Seek for SeekableMemWriter {
1134         #[inline]
1135         fn tell(&self) -> IoResult<u64> { Ok(self.pos as u64) }
1136
1137         #[inline]
1138         fn seek(&mut self, pos: i64, style: SeekStyle) -> IoResult<()> {
1139             let new = try!(combine(style, self.pos, self.buf.len(), pos));
1140             self.pos = new as uint;
1141             Ok(())
1142         }
1143     }
1144
1145     #[test]
1146     fn test_vuint_at() {
1147         let data = [
1148             0x80,
1149             0xff,
1150             0x40, 0x00,
1151             0x7f, 0xff,
1152             0x20, 0x00, 0x00,
1153             0x3f, 0xff, 0xff,
1154             0x10, 0x00, 0x00, 0x00,
1155             0x1f, 0xff, 0xff, 0xff
1156         ];
1157
1158         let mut res: reader::Res;
1159
1160         // Class A
1161         res = reader::vuint_at(data, 0).unwrap();
1162         assert_eq!(res.val, 0);
1163         assert_eq!(res.next, 1);
1164         res = reader::vuint_at(data, res.next).unwrap();
1165         assert_eq!(res.val, (1 << 7) - 1);
1166         assert_eq!(res.next, 2);
1167
1168         // Class B
1169         res = reader::vuint_at(data, res.next).unwrap();
1170         assert_eq!(res.val, 0);
1171         assert_eq!(res.next, 4);
1172         res = reader::vuint_at(data, res.next).unwrap();
1173         assert_eq!(res.val, (1 << 14) - 1);
1174         assert_eq!(res.next, 6);
1175
1176         // Class C
1177         res = reader::vuint_at(data, res.next).unwrap();
1178         assert_eq!(res.val, 0);
1179         assert_eq!(res.next, 9);
1180         res = reader::vuint_at(data, res.next).unwrap();
1181         assert_eq!(res.val, (1 << 21) - 1);
1182         assert_eq!(res.next, 12);
1183
1184         // Class D
1185         res = reader::vuint_at(data, res.next).unwrap();
1186         assert_eq!(res.val, 0);
1187         assert_eq!(res.next, 16);
1188         res = reader::vuint_at(data, res.next).unwrap();
1189         assert_eq!(res.val, (1 << 28) - 1);
1190         assert_eq!(res.next, 20);
1191     }
1192
1193     #[test]
1194     fn test_option_int() {
1195         fn test_v(v: Option<int>) {
1196             debug!("v == {}", v);
1197             let mut wr = SeekableMemWriter::new();
1198             {
1199                 let mut ebml_w = writer::Encoder::new(&mut wr);
1200                 let _ = v.encode(&mut ebml_w);
1201             }
1202             let ebml_doc = Doc::new(wr.get_ref());
1203             let mut deser = reader::Decoder::new(ebml_doc);
1204             let v1 = Decodable::decode(&mut deser).unwrap();
1205             debug!("v1 == {}", v1);
1206             assert_eq!(v, v1);
1207         }
1208
1209         test_v(Some(22));
1210         test_v(None);
1211         test_v(Some(3));
1212     }
1213 }
1214
1215 #[cfg(test)]
1216 mod bench {
1217     #![allow(non_snake_case_functions)]
1218     extern crate test;
1219     use self::test::Bencher;
1220     use ebml::reader;
1221
1222     #[bench]
1223     pub fn vuint_at_A_aligned(b: &mut Bencher) {
1224         let data = Vec::from_fn(4*100, |i| {
1225             match i % 2 {
1226               0 => 0x80u8,
1227               _ => i as u8,
1228             }
1229         });
1230         let mut sum = 0u;
1231         b.iter(|| {
1232             let mut i = 0;
1233             while i < data.len() {
1234                 sum += reader::vuint_at(data.as_slice(), i).unwrap().val;
1235                 i += 4;
1236             }
1237         });
1238     }
1239
1240     #[bench]
1241     pub fn vuint_at_A_unaligned(b: &mut Bencher) {
1242         let data = Vec::from_fn(4*100+1, |i| {
1243             match i % 2 {
1244               1 => 0x80u8,
1245               _ => i as u8
1246             }
1247         });
1248         let mut sum = 0u;
1249         b.iter(|| {
1250             let mut i = 1;
1251             while i < data.len() {
1252                 sum += reader::vuint_at(data.as_slice(), i).unwrap().val;
1253                 i += 4;
1254             }
1255         });
1256     }
1257
1258     #[bench]
1259     pub fn vuint_at_D_aligned(b: &mut Bencher) {
1260         let data = Vec::from_fn(4*100, |i| {
1261             match i % 4 {
1262               0 => 0x10u8,
1263               3 => i as u8,
1264               _ => 0u8
1265             }
1266         });
1267         let mut sum = 0u;
1268         b.iter(|| {
1269             let mut i = 0;
1270             while i < data.len() {
1271                 sum += reader::vuint_at(data.as_slice(), i).unwrap().val;
1272                 i += 4;
1273             }
1274         });
1275     }
1276
1277     #[bench]
1278     pub fn vuint_at_D_unaligned(b: &mut Bencher) {
1279         let data = Vec::from_fn(4*100+1, |i| {
1280             match i % 4 {
1281               1 => 0x10u8,
1282               0 => i as u8,
1283               _ => 0u8
1284             }
1285         });
1286         let mut sum = 0u;
1287         b.iter(|| {
1288             let mut i = 1;
1289             while i < data.len() {
1290                 sum += reader::vuint_at(data.as_slice(), i).unwrap().val;
1291                 i += 4;
1292             }
1293         });
1294     }
1295 }