src/libextra/ebml.rs

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