nestegg/src/nestegg.c

   1 /*
   2  * Copyright © 2010 Mozilla Foundation
   3  *
   4  * This program is made available under an ISC-style license.  See the
   5  * accompanying file LICENSE for details.
   6  */
   7 #include <assert.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10
  11 #include "nestegg/halloc/halloc.h"
  12 #include "nestegg/include/nestegg/nestegg.h"
  13
  14 /* EBML Elements */
  15 #define ID_EBML                 0x1a45dfa3
  16 #define ID_EBML_VERSION         0x4286
  17 #define ID_EBML_READ_VERSION    0x42f7
  18 #define ID_EBML_MAX_ID_LENGTH   0x42f2
  19 #define ID_EBML_MAX_SIZE_LENGTH 0x42f3
  20 #define ID_DOCTYPE              0x4282
  21 #define ID_DOCTYPE_VERSION      0x4287
  22 #define ID_DOCTYPE_READ_VERSION 0x4285
  23
  24 /* Global Elements */
  25 #define ID_VOID                 0xec
  26 #define ID_CRC32                0xbf
  27
  28 /* WebMedia Elements */
  29 #define ID_SEGMENT              0x18538067
  30
  31 /* Seek Head Elements */
  32 #define ID_SEEK_HEAD            0x114d9b74
  33 #define ID_SEEK                 0x4dbb
  34 #define ID_SEEK_ID              0x53ab
  35 #define ID_SEEK_POSITION        0x53ac
  36
  37 /* Info Elements */
  38 #define ID_INFO                 0x1549a966
  39 #define ID_TIMECODE_SCALE       0x2ad7b1
  40 #define ID_DURATION             0x4489
  41
  42 /* Cluster Elements */
  43 #define ID_CLUSTER              0x1f43b675
  44 #define ID_TIMECODE             0xe7
  45 #define ID_BLOCK_GROUP          0xa0
  46 #define ID_SIMPLE_BLOCK         0xa3
  47
  48 /* BlockGroup Elements */
  49 #define ID_BLOCK                0xa1
  50 #define ID_BLOCK_DURATION       0x9b
  51 #define ID_REFERENCE_BLOCK      0xfb
  52
  53 /* Tracks Elements */
  54 #define ID_TRACKS               0x1654ae6b
  55 #define ID_TRACK_ENTRY          0xae
  56 #define ID_TRACK_NUMBER         0xd7
  57 #define ID_TRACK_UID            0x73c5
  58 #define ID_TRACK_TYPE           0x83
  59 #define ID_FLAG_ENABLED         0xb9
  60 #define ID_FLAG_DEFAULT         0x88
  61 #define ID_FLAG_LACING          0x9c
  62 #define ID_TRACK_TIMECODE_SCALE 0x23314f
  63 #define ID_LANGUAGE             0x22b59c
  64 #define ID_CODEC_ID             0x86
  65 #define ID_CODEC_PRIVATE        0x63a2
  66
  67 /* Video Elements */
  68 #define ID_VIDEO                0xe0
  69 #define ID_PIXEL_WIDTH          0xb0
  70 #define ID_PIXEL_HEIGHT         0xba
  71 #define ID_PIXEL_CROP_BOTTOM    0x54aa
  72 #define ID_PIXEL_CROP_TOP       0x54bb
  73 #define ID_PIXEL_CROP_LEFT      0x54cc
  74 #define ID_PIXEL_CROP_RIGHT     0x54dd
  75 #define ID_DISPLAY_WIDTH        0x54b0
  76 #define ID_DISPLAY_HEIGHT       0x54ba
  77
  78 /* Audio Elements */
  79 #define ID_AUDIO                0xe1
  80 #define ID_SAMPLING_FREQUENCY   0xb5
  81 #define ID_CHANNELS             0x9f
  82 #define ID_BIT_DEPTH            0x6264
  83
  84 /* Cues Elements */
  85 #define ID_CUES                 0x1c53bb6b
  86 #define ID_CUE_POINT            0xbb
  87 #define ID_CUE_TIME             0xb3
  88 #define ID_CUE_TRACK_POSITIONS  0xb7
  89 #define ID_CUE_TRACK            0xf7
  90 #define ID_CUE_CLUSTER_POSITION 0xf1
  91 #define ID_CUE_BLOCK_NUMBER     0x5378
  92
  93 /* EBML Types */
  94 enum ebml_type_enum {
  95   TYPE_UNKNOWN,
  96   TYPE_MASTER,
  97   TYPE_UINT,
  98   TYPE_FLOAT,
  99   TYPE_INT,
 100   TYPE_STRING,
 101   TYPE_BINARY
 102 };
 103
 104 #define LIMIT_STRING            (1 << 20)
 105 #define LIMIT_BINARY            (1 << 24)
 106 #define LIMIT_BLOCK             (1 << 30)
 107 #define LIMIT_FRAME             (1 << 28)
 108
 109 /* Field Flags */
 110 #define DESC_FLAG_NONE          0
 111 #define DESC_FLAG_MULTI         (1 << 0)
 112 #define DESC_FLAG_SUSPEND       (1 << 1)
 113 #define DESC_FLAG_OFFSET        (1 << 2)
 114
 115 /* Block Header Flags */
 116 #define BLOCK_FLAGS_LACING      6
 117
 118 /* Lacing Constants */
 119 #define LACING_NONE             0
 120 #define LACING_XIPH             1
 121 #define LACING_FIXED            2
 122 #define LACING_EBML             3
 123
 124 /* Track Types */
 125 #define TRACK_TYPE_VIDEO        1
 126 #define TRACK_TYPE_AUDIO        2
 127
 128 /* Track IDs */
 129 #define TRACK_ID_VP8            "V_VP8"
 130 #define TRACK_ID_VORBIS         "A_VORBIS"
 131
 132 enum vint_mask {
 133   MASK_NONE,
 134   MASK_FIRST_BIT
 135 };
 136
 137 struct ebml_binary {
 138   unsigned char * data;
 139   size_t length;
 140 };
 141
 142 struct ebml_list_node {
 143   struct ebml_list_node * next;
 144   uint64_t id;
 145   void * data;
 146 };
 147
 148 struct ebml_list {
 149   struct ebml_list_node * head;
 150   struct ebml_list_node * tail;
 151 };
 152
 153 struct ebml_type {
 154   union ebml_value {
 155     uint64_t u;
 156     double f;
 157     int64_t i;
 158     char * s;
 159     struct ebml_binary b;
 160   } v;
 161   enum ebml_type_enum type;
 162   int read;
 163 };
 164
 165 /* EBML Definitions */
 166 struct ebml {
 167   struct ebml_type ebml_version;
 168   struct ebml_type ebml_read_version;
 169   struct ebml_type ebml_max_id_length;
 170   struct ebml_type ebml_max_size_length;
 171   struct ebml_type doctype;
 172   struct ebml_type doctype_version;
 173   struct ebml_type doctype_read_version;
 174 };
 175
 176 /* Matroksa Definitions */
 177 struct seek {
 178   struct ebml_type id;
 179   struct ebml_type position;
 180 };
 181
 182 struct seek_head {
 183   struct ebml_list seek;
 184 };
 185
 186 struct info {
 187   struct ebml_type timecode_scale;
 188   struct ebml_type duration;
 189 };
 190
 191 struct block_group {
 192   struct ebml_type duration;
 193   struct ebml_type reference_block;
 194 };
 195
 196 struct cluster {
 197   struct ebml_type timecode;
 198   struct ebml_list block_group;
 199 };
 200
 201 struct video {
 202   struct ebml_type pixel_width;
 203   struct ebml_type pixel_height;
 204   struct ebml_type pixel_crop_bottom;
 205   struct ebml_type pixel_crop_top;
 206   struct ebml_type pixel_crop_left;
 207   struct ebml_type pixel_crop_right;
 208   struct ebml_type display_width;
 209   struct ebml_type display_height;
 210 };
 211
 212 struct audio {
 213   struct ebml_type sampling_frequency;
 214   struct ebml_type channels;
 215   struct ebml_type bit_depth;
 216 };
 217
 218 struct track_entry {
 219   struct ebml_type number;
 220   struct ebml_type uid;
 221   struct ebml_type type;
 222   struct ebml_type flag_enabled;
 223   struct ebml_type flag_default;
 224   struct ebml_type flag_lacing;
 225   struct ebml_type track_timecode_scale;
 226   struct ebml_type language;
 227   struct ebml_type codec_id;
 228   struct ebml_type codec_private;
 229   struct video video;
 230   struct audio audio;
 231 };
 232
 233 struct tracks {
 234   struct ebml_list track_entry;
 235 };
 236
 237 struct cue_track_positions {
 238   struct ebml_type track;
 239   struct ebml_type cluster_position;
 240   struct ebml_type block_number;
 241 };
 242
 243 struct cue_point {
 244   struct ebml_type time;
 245   struct ebml_list cue_track_positions;
 246 };
 247
 248 struct cues {
 249   struct ebml_list cue_point;
 250 };
 251
 252 struct segment {
 253   struct ebml_list seek_head;
 254   struct info info;
 255   struct ebml_list cluster;
 256   struct tracks tracks;
 257   struct cues cues;
 258 };
 259
 260 /* Misc. */
 261 struct pool_ctx {
 262   char dummy;
 263 };
 264
 265 struct list_node {
 266   struct list_node * previous;
 267   struct ebml_element_desc * node;
 268   unsigned char * data;
 269 };
 270
 271 struct saved_state {
 272   int64_t stream_offset;
 273   struct list_node * ancestor;
 274   uint64_t last_id;
 275   uint64_t last_size;
 276 };
 277
 278 struct frame {
 279   unsigned char * data;
 280   size_t length;
 281   struct frame * next;
 282 };
 283
 284 /* Public (opaque) Structures */
 285 struct nestegg {
 286   nestegg_io * io;
 287   nestegg_log log;
 288   struct pool_ctx * alloc_pool;
 289   uint64_t last_id;
 290   uint64_t last_size;
 291   struct list_node * ancestor;
 292   struct ebml ebml;
 293   struct segment segment;
 294   int64_t segment_offset;
 295   unsigned int track_count;
 296 };
 297
 298 struct nestegg_packet {
 299   uint64_t track;
 300   uint64_t timecode;
 301   struct frame * frame;
 302 };
 303
 304 /* Element Descriptor */
 305 struct ebml_element_desc {
 306   char const * name;
 307   uint64_t id;
 308   enum ebml_type_enum type;
 309   size_t offset;
 310   unsigned int flags;
 311   struct ebml_element_desc * children;
 312   size_t size;
 313   size_t data_offset;
 314 };
 315
 316 #define E_FIELD(ID, TYPE, STRUCT, FIELD) \
 317   { #ID, ID, TYPE, offsetof(STRUCT, FIELD), DESC_FLAG_NONE, NULL, 0, 0 }
 318 #define E_MASTER(ID, TYPE, STRUCT, FIELD) \
 319   { #ID, ID, TYPE, offsetof(STRUCT, FIELD), DESC_FLAG_MULTI, ne_ ## FIELD ## _elements, \
 320       sizeof(struct FIELD), 0 }
 321 #define E_SINGLE_MASTER_O(ID, TYPE, STRUCT, FIELD) \
 322   { #ID, ID, TYPE, offsetof(STRUCT, FIELD), DESC_FLAG_OFFSET, ne_ ## FIELD ## _elements, 0, \
 323       offsetof(STRUCT, FIELD ## _offset) }
 324 #define E_SINGLE_MASTER(ID, TYPE, STRUCT, FIELD) \
 325   { #ID, ID, TYPE, offsetof(STRUCT, FIELD), DESC_FLAG_NONE, ne_ ## FIELD ## _elements, 0, 0 }
 326 #define E_SUSPEND(ID, TYPE) \
 327   { #ID, ID, TYPE, 0, DESC_FLAG_SUSPEND, NULL, 0, 0 }
 328 #define E_LAST \
 329   { NULL, 0, 0, 0, DESC_FLAG_NONE, NULL, 0, 0 }
 330
 331 /* EBML Element Lists */
 332 static struct ebml_element_desc ne_ebml_elements[] = {
 333   E_FIELD(ID_EBML_VERSION, TYPE_UINT, struct ebml, ebml_version),
 334   E_FIELD(ID_EBML_READ_VERSION, TYPE_UINT, struct ebml, ebml_read_version),
 335   E_FIELD(ID_EBML_MAX_ID_LENGTH, TYPE_UINT, struct ebml, ebml_max_id_length),
 336   E_FIELD(ID_EBML_MAX_SIZE_LENGTH, TYPE_UINT, struct ebml, ebml_max_size_length),
 337   E_FIELD(ID_DOCTYPE, TYPE_STRING, struct ebml, doctype),
 338   E_FIELD(ID_DOCTYPE_VERSION, TYPE_UINT, struct ebml, doctype_version),
 339   E_FIELD(ID_DOCTYPE_READ_VERSION, TYPE_UINT, struct ebml, doctype_read_version),
 340   E_LAST
 341 };
 342
 343 /* WebMedia Element Lists */
 344 static struct ebml_element_desc ne_seek_elements[] = {
 345   E_FIELD(ID_SEEK_ID, TYPE_BINARY, struct seek, id),
 346   E_FIELD(ID_SEEK_POSITION, TYPE_UINT, struct seek, position),
 347   E_LAST
 348 };
 349
 350 static struct ebml_element_desc ne_seek_head_elements[] = {
 351   E_MASTER(ID_SEEK, TYPE_MASTER, struct seek_head, seek),
 352   E_LAST
 353 };
 354
 355 static struct ebml_element_desc ne_info_elements[] = {
 356   E_FIELD(ID_TIMECODE_SCALE, TYPE_UINT, struct info, timecode_scale),
 357   E_FIELD(ID_DURATION, TYPE_FLOAT, struct info, duration),
 358   E_LAST
 359 };
 360
 361 static struct ebml_element_desc ne_block_group_elements[] = {
 362   E_SUSPEND(ID_BLOCK, TYPE_BINARY),
 363   E_FIELD(ID_BLOCK_DURATION, TYPE_UINT, struct block_group, duration),
 364   E_FIELD(ID_REFERENCE_BLOCK, TYPE_INT, struct block_group, reference_block),
 365   E_LAST
 366 };
 367
 368 static struct ebml_element_desc ne_cluster_elements[] = {
 369   E_FIELD(ID_TIMECODE, TYPE_UINT, struct cluster, timecode),
 370   E_MASTER(ID_BLOCK_GROUP, TYPE_MASTER, struct cluster, block_group),
 371   E_SUSPEND(ID_SIMPLE_BLOCK, TYPE_BINARY),
 372   E_LAST
 373 };
 374
 375 static struct ebml_element_desc ne_video_elements[] = {
 376   E_FIELD(ID_PIXEL_WIDTH, TYPE_UINT, struct video, pixel_width),
 377   E_FIELD(ID_PIXEL_HEIGHT, TYPE_UINT, struct video, pixel_height),
 378   E_FIELD(ID_PIXEL_CROP_BOTTOM, TYPE_UINT, struct video, pixel_crop_bottom),
 379   E_FIELD(ID_PIXEL_CROP_TOP, TYPE_UINT, struct video, pixel_crop_top),
 380   E_FIELD(ID_PIXEL_CROP_LEFT, TYPE_UINT, struct video, pixel_crop_left),
 381   E_FIELD(ID_PIXEL_CROP_RIGHT, TYPE_UINT, struct video, pixel_crop_right),
 382   E_FIELD(ID_DISPLAY_WIDTH, TYPE_UINT, struct video, display_width),
 383   E_FIELD(ID_DISPLAY_HEIGHT, TYPE_UINT, struct video, display_height),
 384   E_LAST
 385 };
 386
 387 static struct ebml_element_desc ne_audio_elements[] = {
 388   E_FIELD(ID_SAMPLING_FREQUENCY, TYPE_FLOAT, struct audio, sampling_frequency),
 389   E_FIELD(ID_CHANNELS, TYPE_UINT, struct audio, channels),
 390   E_FIELD(ID_BIT_DEPTH, TYPE_UINT, struct audio, bit_depth),
 391   E_LAST
 392 };
 393
 394 static struct ebml_element_desc ne_track_entry_elements[] = {
 395   E_FIELD(ID_TRACK_NUMBER, TYPE_UINT, struct track_entry, number),
 396   E_FIELD(ID_TRACK_UID, TYPE_UINT, struct track_entry, uid),
 397   E_FIELD(ID_TRACK_TYPE, TYPE_UINT, struct track_entry, type),
 398   E_FIELD(ID_FLAG_ENABLED, TYPE_UINT, struct track_entry, flag_enabled),
 399   E_FIELD(ID_FLAG_DEFAULT, TYPE_UINT, struct track_entry, flag_default),
 400   E_FIELD(ID_FLAG_LACING, TYPE_UINT, struct track_entry, flag_lacing),
 401   E_FIELD(ID_TRACK_TIMECODE_SCALE, TYPE_FLOAT, struct track_entry, track_timecode_scale),
 402   E_FIELD(ID_LANGUAGE, TYPE_STRING, struct track_entry, language),
 403   E_FIELD(ID_CODEC_ID, TYPE_STRING, struct track_entry, codec_id),
 404   E_FIELD(ID_CODEC_PRIVATE, TYPE_BINARY, struct track_entry, codec_private),
 405   E_SINGLE_MASTER(ID_VIDEO, TYPE_MASTER, struct track_entry, video),
 406   E_SINGLE_MASTER(ID_AUDIO, TYPE_MASTER, struct track_entry, audio),
 407   E_LAST
 408 };
 409
 410 static struct ebml_element_desc ne_tracks_elements[] = {
 411   E_MASTER(ID_TRACK_ENTRY, TYPE_MASTER, struct tracks, track_entry),
 412   E_LAST
 413 };
 414
 415 static struct ebml_element_desc ne_cue_track_positions_elements[] = {
 416   E_FIELD(ID_CUE_TRACK, TYPE_UINT, struct cue_track_positions, track),
 417   E_FIELD(ID_CUE_CLUSTER_POSITION, TYPE_UINT, struct cue_track_positions, cluster_position),
 418   E_FIELD(ID_CUE_BLOCK_NUMBER, TYPE_UINT, struct cue_track_positions, block_number),
 419   E_LAST
 420 };
 421
 422 static struct ebml_element_desc ne_cue_point_elements[] = {
 423   E_FIELD(ID_CUE_TIME, TYPE_UINT, struct cue_point, time),
 424   E_MASTER(ID_CUE_TRACK_POSITIONS, TYPE_MASTER, struct cue_point, cue_track_positions),
 425   E_LAST
 426 };
 427
 428 static struct ebml_element_desc ne_cues_elements[] = {
 429   E_MASTER(ID_CUE_POINT, TYPE_MASTER, struct cues, cue_point),
 430   E_LAST
 431 };
 432
 433 static struct ebml_element_desc ne_segment_elements[] = {
 434   E_MASTER(ID_SEEK_HEAD, TYPE_MASTER, struct segment, seek_head),
 435   E_SINGLE_MASTER(ID_INFO, TYPE_MASTER, struct segment, info),
 436   E_MASTER(ID_CLUSTER, TYPE_MASTER, struct segment, cluster),
 437   E_SINGLE_MASTER(ID_TRACKS, TYPE_MASTER, struct segment, tracks),
 438   E_SINGLE_MASTER(ID_CUES, TYPE_MASTER, struct segment, cues),
 439   E_LAST
 440 };
 441
 442 static struct ebml_element_desc ne_top_level_elements[] = {
 443   E_SINGLE_MASTER(ID_EBML, TYPE_MASTER, nestegg, ebml),
 444   E_SINGLE_MASTER_O(ID_SEGMENT, TYPE_MASTER, nestegg, segment),
 445   E_LAST
 446 };
 447
 448 #undef E_FIELD
 449 #undef E_MASTER
 450 #undef E_SINGLE_MASTER_O
 451 #undef E_SINGLE_MASTER
 452 #undef E_SUSPEND
 453 #undef E_LAST
 454
 455 static struct pool_ctx *
 456 ne_pool_init(void)
 457 {
 458   struct pool_ctx * pool;
 459
 460   pool = h_malloc(sizeof(*pool));
 461   if (!pool)
 462     abort();
 463   return pool;
 464 }
 465
 466 static void
 467 ne_pool_destroy(struct pool_ctx * pool)
 468 {
 469   h_free(pool);
 470 }
 471
 472 static void *
 473 ne_pool_alloc(size_t size, struct pool_ctx * pool)
 474 {
 475   void * p;
 476
 477   p = h_malloc(size);
 478   if (!p)
 479     abort();
 480   hattach(p, pool);
 481   memset(p, 0, size);
 482   return p;
 483 }
 484
 485 static void *
 486 ne_alloc(size_t size)
 487 {
 488   void * p;
 489
 490   p = calloc(1, size);
 491   if (!p)
 492     abort();
 493   return p;
 494 }
 495
 496 static int
 497 ne_io_read(nestegg_io * io, void * buffer, size_t length)
 498 {
 499   return io->read(buffer, length, io->userdata);
 500 }
 501
 502 static int
 503 ne_io_seek(nestegg_io * io, int64_t offset, int whence)
 504 {
 505   return io->seek(offset, whence, io->userdata);
 506 }
 507
 508 static int
 509 ne_io_read_skip(nestegg_io * io, size_t length)
 510 {
 511   size_t get;
 512   unsigned char buf[8192];
 513   int r = 1;
 514
 515   while (length > 0) {
 516     get = length < sizeof(buf) ? length : sizeof(buf);
 517     r = ne_io_read(io, buf, get);
 518     if (r != 1)
 519       break;
 520     length -= get;
 521   }
 522
 523   return r;
 524 }
 525
 526 static int64_t
 527 ne_io_tell(nestegg_io * io)
 528 {
 529   return io->tell(io->userdata);
 530 }
 531
 532 static int
 533 ne_bare_read_vint(nestegg_io * io, uint64_t * value, uint64_t * length, enum vint_mask maskflag)
 534 {
 535   int r;
 536   unsigned char b;
 537   size_t maxlen = 8;
 538   unsigned int count = 1, mask = 1 << 7;
 539
 540   r = ne_io_read(io, &b, 1);
 541   if (r != 1)
 542     return r;
 543
 544   while (count < maxlen) {
 545     if ((b & mask) != 0)
 546       break;
 547     mask >>= 1;
 548     count += 1;
 549   }
 550
 551   if (length)
 552     *length = count;
 553   *value = b;
 554
 555   if (maskflag == MASK_FIRST_BIT)
 556     *value = b & ~mask;
 557
 558   while (--count) {
 559     r = ne_io_read(io, &b, 1);
 560     if (r != 1)
 561       return r;
 562     *value <<= 8;
 563     *value |= b;
 564   }
 565
 566   return 1;
 567 }
 568
 569 static int
 570 ne_read_id(nestegg_io * io, uint64_t * value, uint64_t * length)
 571 {
 572   return ne_bare_read_vint(io, value, length, MASK_NONE);
 573 }
 574
 575 static int
 576 ne_read_vint(nestegg_io * io, uint64_t * value, uint64_t * length)
 577 {
 578   return ne_bare_read_vint(io, value, length, MASK_FIRST_BIT);
 579 }
 580
 581 static int
 582 ne_read_svint(nestegg_io * io, int64_t * value, uint64_t * length)
 583 {
 584   int r;
 585   uint64_t uvalue;
 586   uint64_t ulength;
 587   int64_t svint_subtr[] = {
 588     0x3f, 0x1fff,
 589     0xfffff, 0x7ffffff,
 590     0x3ffffffffLL, 0x1ffffffffffLL,
 591     0xffffffffffffLL, 0x7fffffffffffffLL
 592   };
 593
 594   r = ne_bare_read_vint(io, &uvalue, &ulength, MASK_FIRST_BIT);
 595   if (r != 1)
 596     return r;
 597   *value = uvalue - svint_subtr[ulength - 1];
 598   if (length)
 599     *length = ulength;
 600   return r;
 601 }
 602
 603 static int
 604 ne_read_uint(nestegg_io * io, uint64_t * val, uint64_t length)
 605 {
 606   unsigned char b;
 607   int r;
 608
 609   if (length == 0 || length > 8)
 610     return -1;
 611   r = ne_io_read(io, &b, 1);
 612   if (r != 1)
 613     return r;
 614   *val = b;
 615   while (--length) {
 616     r = ne_io_read(io, &b, 1);
 617     if (r != 1)
 618       return r;
 619     *val <<= 8;
 620     *val |= b;
 621   }
 622   return 1;
 623 }
 624
 625 static int
 626 ne_read_int(nestegg_io * io, int64_t * val, uint64_t length)
 627 {
 628   int r;
 629   uint64_t uval, base;
 630
 631   r = ne_read_uint(io, &uval, length);
 632   if (r != 1)
 633     return r;
 634
 635   if (length < sizeof(int64_t)) {
 636     base = 1;
 637     base <<= length * 8 - 1;
 638     if (uval >= base) {
 639         base = 1;
 640         base <<= length * 8;
 641     } else {
 642       base = 0;
 643     }
 644     *val = uval - base;
 645   } else {
 646     *val = (int64_t) uval;
 647   }
 648
 649   return 1;
 650 }
 651
 652 static int
 653 ne_read_float(nestegg_io * io, double * val, uint64_t length)
 654 {
 655   union {
 656     uint64_t u;
 657     float f;
 658     double d;
 659   } value;
 660   int r;
 661
 662   /* length == 10 not implemented */
 663   if (length != 4 && length != 8)
 664     return -1;
 665   r = ne_read_uint(io, &value.u, length);
 666   if (r != 1)
 667     return r;
 668   if (length == 4)
 669     *val = value.f;
 670   else
 671     *val = value.d;
 672   return 1;
 673 }
 674
 675 static int
 676 ne_read_string(nestegg * ctx, char ** val, uint64_t length)
 677 {
 678   char * str;
 679   int r;
 680
 681   if (length == 0 || length > LIMIT_STRING)
 682     return -1;
 683   str = ne_pool_alloc(length + 1, ctx->alloc_pool);
 684   r = ne_io_read(ctx->io, (unsigned char *) str, length);
 685   if (r != 1)
 686     return r;
 687   str[length] = '\0';
 688   *val = str;
 689   return 1;
 690 }
 691
 692 static int
 693 ne_read_binary(nestegg * ctx, struct ebml_binary * val, uint64_t length)
 694 {
 695   if (length == 0 || length > LIMIT_BINARY)
 696     return -1;
 697   val->data = ne_pool_alloc(length, ctx->alloc_pool);
 698   val->length = length;
 699   return ne_io_read(ctx->io, val->data, length);
 700 }
 701
 702 static int
 703 ne_get_uint(struct ebml_type type, uint64_t * value)
 704 {
 705   if (!type.read)
 706     return -1;
 707
 708   assert(type.type == TYPE_UINT);
 709
 710   *value = type.v.u;
 711
 712   return 0;
 713 }
 714
 715 static int
 716 ne_get_float(struct ebml_type type, double * value)
 717 {
 718   if (!type.read)
 719     return -1;
 720
 721   assert(type.type == TYPE_FLOAT);
 722
 723   *value = type.v.f;
 724
 725   return 0;
 726 }
 727
 728 static int
 729 ne_get_string(struct ebml_type type, char ** value)
 730 {
 731   if (!type.read)
 732     return -1;
 733
 734   assert(type.type == TYPE_STRING);
 735
 736   *value = type.v.s;
 737
 738   return 0;
 739 }
 740
 741 static int
 742 ne_get_binary(struct ebml_type type, struct ebml_binary * value)
 743 {
 744   if (!type.read)
 745     return -1;
 746
 747   assert(type.type == TYPE_BINARY);
 748
 749   *value = type.v.b;
 750
 751   return 0;
 752 }
 753
 754 static int
 755 ne_is_ancestor_element(uint64_t id, struct list_node * ancestor)
 756 {
 757   struct ebml_element_desc * element;
 758
 759   for (; ancestor; ancestor = ancestor->previous)
 760     for (element = ancestor->node; element->id; ++element)
 761       if (element->id == id)
 762         return 1;
 763
 764   return 0;
 765 }
 766
 767 static struct ebml_element_desc *
 768 ne_find_element(uint64_t id, struct ebml_element_desc * elements)
 769 {
 770   struct ebml_element_desc * element;
 771
 772   for (element = elements; element->id; ++element)
 773     if (element->id == id)
 774       return element;
 775
 776   return NULL;
 777 }
 778
 779 static void
 780 ne_ctx_push(nestegg * ctx, struct ebml_element_desc * ancestor, void * data)
 781 {
 782   struct list_node * item;
 783
 784   item = ne_alloc(sizeof(*item));
 785   item->previous = ctx->ancestor;
 786   item->node = ancestor;
 787   item->data = data;
 788   ctx->ancestor = item;
 789 }
 790
 791 static void
 792 ne_ctx_pop(nestegg * ctx)
 793 {
 794   struct list_node * item;
 795
 796   item = ctx->ancestor;
 797   ctx->ancestor = item->previous;
 798   free(item);
 799 }
 800
 801 static int
 802 ne_ctx_save(nestegg * ctx, struct saved_state * s)
 803 {
 804   s->stream_offset = ne_io_tell(ctx->io);
 805   if (s->stream_offset < 0)
 806     return -1;
 807   s->ancestor = ctx->ancestor;
 808   s->last_id = ctx->last_id;
 809   s->last_size = ctx->last_size;
 810   return 0;
 811 }
 812
 813 static int
 814 ne_ctx_restore(nestegg * ctx, struct saved_state * s)
 815 {
 816   int r;
 817
 818   r = ne_io_seek(ctx->io, s->stream_offset, NESTEGG_SEEK_SET);
 819   if (r != 0)
 820     return -1;
 821   ctx->ancestor = s->ancestor;
 822   ctx->last_id = s->last_id;
 823   ctx->last_size = s->last_size;
 824   return 0;
 825 }
 826
 827 static int
 828 ne_peek_element(nestegg * ctx, uint64_t * id, uint64_t * size)
 829 {
 830   int r;
 831
 832   if (ctx->last_id && ctx->last_size) {
 833     if (id)
 834       *id = ctx->last_id;
 835     if (size)
 836       *size = ctx->last_size;
 837     return 1;
 838   }
 839
 840   r = ne_read_id(ctx->io, &ctx->last_id, NULL);
 841   if (r != 1)
 842     return r;
 843
 844   r = ne_read_vint(ctx->io, &ctx->last_size, NULL);
 845   if (r != 1)
 846     return r;
 847
 848   if (id)
 849     *id = ctx->last_id;
 850   if (size)
 851     *size = ctx->last_size;
 852
 853   return 1;
 854 }
 855
 856 static int
 857 ne_read_element(nestegg * ctx, uint64_t * id, uint64_t * size)
 858 {
 859   int r;
 860
 861   r = ne_peek_element(ctx, id, size);
 862   if (r != 1)
 863     return r;
 864
 865   ctx->last_id = 0;
 866   ctx->last_size = 0;
 867
 868   return 1;
 869 }
 870
 871 static void
 872 ne_read_master(nestegg * ctx, struct ebml_element_desc * desc)
 873 {
 874   struct ebml_list * list;
 875   struct ebml_list_node * node, * oldtail;
 876
 877   assert(desc->type == TYPE_MASTER && desc->flags & DESC_FLAG_MULTI);
 878
 879   ctx->log(ctx, NESTEGG_LOG_DEBUG, "multi master element %llx (%s)",
 880            desc->id, desc->name);
 881
 882   list = (struct ebml_list *) (ctx->ancestor->data + desc->offset);
 883
 884   node = ne_pool_alloc(sizeof(*node), ctx->alloc_pool);
 885   node->id = desc->id;
 886   node->data = ne_pool_alloc(desc->size, ctx->alloc_pool);
 887
 888   oldtail = list->tail;
 889   if (oldtail)
 890     oldtail->next = node;
 891   list->tail = node;
 892   if (!list->head)
 893     list->head = node;
 894
 895   ctx->log(ctx, NESTEGG_LOG_DEBUG, " -> using data %p", node->data);
 896
 897   ne_ctx_push(ctx, desc->children, node->data);
 898 }
 899
 900 static void
 901 ne_read_single_master(nestegg * ctx, struct ebml_element_desc * desc)
 902 {
 903   assert(desc->type == TYPE_MASTER && !(desc->flags & DESC_FLAG_MULTI));
 904
 905   ctx->log(ctx, NESTEGG_LOG_DEBUG, "single master element %llx (%s)",
 906            desc->id, desc->name);
 907   ctx->log(ctx, NESTEGG_LOG_DEBUG, " -> using data %p (%u)",
 908            ctx->ancestor->data + desc->offset, desc->offset);
 909
 910   ne_ctx_push(ctx, desc->children, ctx->ancestor->data + desc->offset);
 911 }
 912
 913 static int
 914 ne_read_simple(nestegg * ctx, struct ebml_element_desc * desc, size_t length)
 915 {
 916   struct ebml_type * storage;
 917   int r;
 918
 919   storage = (struct ebml_type *) (ctx->ancestor->data + desc->offset);
 920
 921   if (storage->read) {
 922     ctx->log(ctx, NESTEGG_LOG_DEBUG, "element %llx (%s) already read, skipping",
 923              desc->id, desc->name);
 924     return 0;
 925   }
 926
 927   storage->type = desc->type;
 928
 929   ctx->log(ctx, NESTEGG_LOG_DEBUG, "element %llx (%s) -> %p (%u)",
 930            desc->id, desc->name, storage, desc->offset);
 931
 932   r = -1;
 933
 934   switch (desc->type) {
 935   case TYPE_UINT:
 936     r = ne_read_uint(ctx->io, &storage->v.u, length);
 937     break;
 938   case TYPE_FLOAT:
 939     r = ne_read_float(ctx->io, &storage->v.f, length);
 940     break;
 941   case TYPE_INT:
 942     r = ne_read_int(ctx->io, &storage->v.i, length);
 943     break;
 944   case TYPE_STRING:
 945     r = ne_read_string(ctx, &storage->v.s, length);
 946     break;
 947   case TYPE_BINARY:
 948     r = ne_read_binary(ctx, &storage->v.b, length);
 949     break;
 950   case TYPE_MASTER:
 951   case TYPE_UNKNOWN:
 952     assert(0);
 953     break;
 954   }
 955
 956   if (r == 1)
 957     storage->read = 1;
 958
 959   return r;
 960 }
 961
 962 static int
 963 ne_parse(nestegg * ctx, struct ebml_element_desc * top_level)
 964 {
 965   int r;
 966   int64_t * data_offset;
 967   uint64_t id, size;
 968   struct ebml_element_desc * element;
 969
 970   /* loop until we need to return:
 971      - hit suspend point
 972      - parse complete
 973      - error occurred */
 974
 975   /* loop over elements at current level reading them if sublevel found,
 976      push ctx onto stack and continue if sublevel ended, pop ctx off stack
 977      and continue */
 978
 979   if (!ctx->ancestor)
 980     return -1;
 981
 982   for (;;) {
 983     r = ne_peek_element(ctx, &id, &size);
 984     if (r != 1)
 985       break;
 986
 987     element = ne_find_element(id, ctx->ancestor->node);
 988     if (element) {
 989       if (element->flags & DESC_FLAG_SUSPEND) {
 990         assert(element->type == TYPE_BINARY);
 991         ctx->log(ctx, NESTEGG_LOG_DEBUG, "suspend parse at %llx", id);
 992         r = 1;
 993         break;
 994       }
 995
 996       r = ne_read_element(ctx, &id, &size);
 997       if (r != 1)
 998         break;
 999
1000       if (element->flags & DESC_FLAG_OFFSET) {
1001         data_offset = (int64_t *) (ctx->ancestor->data + element->data_offset);
1002         *data_offset = ne_io_tell(ctx->io);
1003         if (*data_offset < 0) {
1004           r = -1;
1005           break;
1006         }
1007       }
1008
1009       if (element->type == TYPE_MASTER) {
1010         if (element->flags & DESC_FLAG_MULTI)
1011           ne_read_master(ctx, element);
1012         else
1013           ne_read_single_master(ctx, element);
1014         continue;
1015       } else {
1016         r = ne_read_simple(ctx, element, size);
1017         if (r < 0)
1018           break;
1019       }
1020     } else if (ne_is_ancestor_element(id, ctx->ancestor->previous)) {
1021       ctx->log(ctx, NESTEGG_LOG_DEBUG, "parent element %llx", id);
1022       if (top_level && ctx->ancestor->node == top_level) {
1023         ctx->log(ctx, NESTEGG_LOG_DEBUG, "*** parse about to back up past top_level");
1024         r = 1;
1025         break;
1026       }
1027       ne_ctx_pop(ctx);
1028     } else {
1029       r = ne_read_element(ctx, &id, &size);
1030       if (r != 1)
1031         break;
1032
1033       if (id != ID_VOID && id != ID_CRC32)
1034         ctx->log(ctx, NESTEGG_LOG_DEBUG, "unknown element %llx", id);
1035       r = ne_io_read_skip(ctx->io, size);
1036       if (r != 1)
1037         break;
1038     }
1039   }
1040
1041   if (r != 1)
1042     while (ctx->ancestor)
1043       ne_ctx_pop(ctx);
1044
1045   return r;
1046 }
1047
1048 static uint64_t
1049 ne_xiph_lace_value(unsigned char ** np)
1050 {
1051   uint64_t lace;
1052   uint64_t value;
1053   unsigned char * p = *np;
1054
1055   lace = *p++;
1056   value = lace;
1057   while (lace == 255) {
1058     lace = *p++;
1059     value += lace;
1060   }
1061
1062   *np = p;
1063
1064   return value;
1065 }
1066
1067 static int
1068 ne_read_xiph_lace_value(nestegg_io * io, uint64_t * value, size_t * consumed)
1069 {
1070   int r;
1071   uint64_t lace;
1072
1073   r = ne_read_uint(io, &lace, 1);
1074   if (r != 1)
1075     return r;
1076   *consumed += 1;
1077
1078   *value = lace;
1079   while (lace == 255) {
1080     r = ne_read_uint(io, &lace, 1);
1081     if (r != 1)
1082       return r;
1083     *consumed += 1;
1084     *value += lace;
1085   }
1086
1087   return 1;
1088 }
1089
1090 static int
1091 ne_read_xiph_lacing(nestegg_io * io, size_t block, size_t * read, uint64_t n, uint64_t * sizes)
1092 {
1093   int r;
1094   size_t i = 0;
1095   uint64_t sum = 0;
1096
1097   while (--n) {
1098     r = ne_read_xiph_lace_value(io, &sizes[i], read);
1099     if (r != 1)
1100       return r;
1101     sum += sizes[i];
1102     i += 1;
1103   }
1104
1105   if (*read + sum > block)
1106     return -1;
1107
1108   /* last frame is the remainder of the block */
1109   sizes[i] = block - *read - sum;
1110   return 1;
1111 }
1112
1113 static int
1114 ne_read_ebml_lacing(nestegg_io * io, size_t block, size_t * read, uint64_t n, uint64_t * sizes)
1115 {
1116   int r;
1117   uint64_t lace, sum, length;
1118   int64_t slace;
1119   size_t i = 0;
1120
1121   r = ne_read_vint(io, &lace, &length);
1122   if (r != 1)
1123     return r;
1124   *read += length;
1125
1126   sizes[i] = lace;
1127   sum = sizes[i];
1128
1129   i += 1;
1130   n -= 1;
1131
1132   while (--n) {
1133     r = ne_read_svint(io, &slace, &length);
1134     if (r != 1)
1135       return r;
1136     *read += length;
1137     sizes[i] = sizes[i - 1] + slace;
1138     sum += sizes[i];
1139     i += 1;
1140   }
1141
1142   if (*read + sum > block)
1143     return -1;
1144
1145   /* last frame is the remainder of the block */
1146   sizes[i] = block - *read - sum;
1147   return 1;
1148 }
1149
1150 static uint64_t
1151 ne_get_timecode_scale(nestegg * ctx)
1152 {
1153   uint64_t scale;
1154
1155   if (ne_get_uint(ctx->segment.info.timecode_scale, &scale) != 0)
1156     scale = 1000000;
1157
1158   return scale;
1159 }
1160
1161 static struct track_entry *
1162 ne_find_track_entry(nestegg * ctx, unsigned int track)
1163 {
1164   struct ebml_list_node * node;
1165   unsigned int tracks = 0;
1166
1167   node = ctx->segment.tracks.track_entry.head;
1168   while (node) {
1169     assert(node->id == ID_TRACK_ENTRY);
1170     if (track == tracks)
1171       return node->data;
1172     tracks += 1;
1173     node = node->next;
1174   }
1175
1176   return NULL;
1177 }
1178
1179 static int
1180 ne_read_block(nestegg * ctx, uint64_t block_id, uint64_t block_size, nestegg_packet ** data)
1181 {
1182   int r;
1183   int64_t timecode, abs_timecode;
1184   nestegg_packet * pkt;
1185   struct cluster * cluster;
1186   struct frame * f, * last;
1187   struct track_entry * entry;
1188   double track_scale;
1189   uint64_t track, length, frame_sizes[256], cluster_tc, flags, frames, tc_scale, total;
1190   unsigned int i, lacing;
1191   size_t consumed = 0;
1192
1193   *data = NULL;
1194
1195   if (block_size > LIMIT_BLOCK)
1196     return -1;
1197
1198   r = ne_read_vint(ctx->io, &track, &length);
1199   if (r != 1)
1200     return r;
1201
1202   if (track == 0 || track > ctx->track_count)
1203     return -1;
1204
1205   consumed += length;
1206
1207   r = ne_read_int(ctx->io, &timecode, 2);
1208   if (r != 1)
1209     return r;
1210
1211   consumed += 2;
1212
1213   r = ne_read_uint(ctx->io, &flags, 1);
1214   if (r != 1)
1215     return r;
1216
1217   consumed += 1;
1218
1219   frames = 0;
1220
1221   /* flags are different between block and simpleblock, but lacing is
1222      encoded the same way */
1223   lacing = (flags & BLOCK_FLAGS_LACING) >> 1;
1224
1225   switch (lacing) {
1226   case LACING_NONE:
1227     frames = 1;
1228     break;
1229   case LACING_XIPH:
1230   case LACING_FIXED:
1231   case LACING_EBML:
1232     r = ne_read_uint(ctx->io, &frames, 1);
1233     if (r != 1)
1234       return r;
1235     consumed += 1;
1236     frames += 1;
1237   }
1238
1239   if (frames > 256)
1240     return -1;
1241
1242   switch (lacing) {
1243   case LACING_NONE:
1244     frame_sizes[0] = block_size - consumed;
1245     break;
1246   case LACING_XIPH:
1247     if (frames == 1)
1248       return -1;
1249     r = ne_read_xiph_lacing(ctx->io, block_size, &consumed, frames, frame_sizes);
1250     if (r != 1)
1251       return r;
1252     break;
1253   case LACING_FIXED:
1254     if ((block_size - consumed) % frames)
1255       return -1;
1256     for (i = 0; i < frames; ++i)
1257       frame_sizes[i] = (block_size - consumed) / frames;
1258     break;
1259   case LACING_EBML:
1260     if (frames == 1)
1261       return -1;
1262     r = ne_read_ebml_lacing(ctx->io, block_size, &consumed, frames, frame_sizes);
1263     if (r != 1)
1264       return r;
1265     break;
1266   }
1267
1268   /* sanity check unlaced frame sizes against total block size. */
1269   total = consumed;
1270   for (i = 0; i < frames; ++i)
1271     total += frame_sizes[i];
1272   if (total > block_size)
1273     return -1;
1274
1275   entry = ne_find_track_entry(ctx, track - 1);
1276   if (!entry)
1277     return -1;
1278
1279   track_scale = 1.0;
1280
1281   tc_scale = ne_get_timecode_scale(ctx);
1282
1283   assert(ctx->segment.cluster.tail->id == ID_CLUSTER);
1284   cluster = ctx->segment.cluster.tail->data;
1285   if (ne_get_uint(cluster->timecode, &cluster_tc) != 0)
1286     return -1;
1287
1288   abs_timecode = timecode + cluster_tc;
1289   if (abs_timecode < 0)
1290     return -1;
1291
1292   pkt = ne_alloc(sizeof(*pkt));
1293   pkt->track = track - 1;
1294   pkt->timecode = abs_timecode * tc_scale * track_scale;
1295
1296   ctx->log(ctx, NESTEGG_LOG_DEBUG, "%sblock t %lld pts %f f %llx frames: %llu",
1297            block_id == ID_BLOCK ? "" : "simple", pkt->track, pkt->timecode / 1e9, flags, frames);
1298
1299   last = NULL;
1300   for (i = 0; i < frames; ++i) {
1301     if (frame_sizes[i] > LIMIT_FRAME) {
1302       nestegg_free_packet(pkt);
1303       return -1;
1304     }
1305     f = ne_alloc(sizeof(*f));
1306     f->data = ne_alloc(frame_sizes[i]);
1307     f->length = frame_sizes[i];
1308     r = ne_io_read(ctx->io, f->data, frame_sizes[i]);
1309     if (r != 1) {
1310       free(f->data);
1311       free(f);
1312       nestegg_free_packet(pkt);
1313       return -1;
1314     }
1315
1316     if (!last)
1317       pkt->frame = f;
1318     else
1319       last->next = f;
1320     last = f;
1321   }
1322
1323   *data = pkt;
1324
1325   return 1;
1326 }
1327
1328 static uint64_t
1329 ne_buf_read_id(unsigned char const * p, size_t length)
1330 {
1331   uint64_t id = 0;
1332
1333   while (length--) {
1334     id <<= 8;
1335     id |= *p++;
1336   }
1337
1338   return id;
1339 }
1340
1341 static struct seek *
1342 ne_find_seek_for_id(struct ebml_list_node * seek_head, uint64_t id)
1343 {
1344   struct ebml_list * head;
1345   struct ebml_list_node * seek;
1346   struct ebml_binary binary_id;
1347   struct seek * s;
1348
1349   while (seek_head) {
1350     assert(seek_head->id == ID_SEEK_HEAD);
1351     head = seek_head->data;
1352     seek = head->head;
1353
1354     while (seek) {
1355       assert(seek->id == ID_SEEK);
1356       s = seek->data;
1357
1358       if (ne_get_binary(s->id, &binary_id) == 0 &&
1359           ne_buf_read_id(binary_id.data, binary_id.length) == id)
1360         return s;
1361
1362       seek = seek->next;
1363     }
1364
1365     seek_head = seek_head->next;
1366   }
1367
1368   return NULL;
1369 }
1370
1371 static struct cue_point *
1372 ne_find_cue_point_for_tstamp(struct ebml_list_node * cue_point, uint64_t scale, uint64_t tstamp)
1373 {
1374   uint64_t time;
1375   struct cue_point * c, * prev = NULL;
1376
1377   while (cue_point) {
1378     assert(cue_point->id == ID_CUE_POINT);
1379     c = cue_point->data;
1380
1381     if (!prev)
1382       prev = c;
1383
1384     if (ne_get_uint(c->time, &time) == 0 && time * scale > tstamp)
1385       break;
1386
1387     prev = cue_point->data;
1388     cue_point = cue_point->next;
1389   }
1390
1391   return prev;
1392 }
1393
1394 static int
1395 ne_is_suspend_element(uint64_t id)
1396 {
1397   /* this could search the tree of elements for DESC_FLAG_SUSPEND */
1398   if (id == ID_SIMPLE_BLOCK || id == ID_BLOCK)
1399     return 1;
1400   return 0;
1401 }
1402
1403 static void
1404 ne_null_log_callback(nestegg * ctx, unsigned int severity, char const * fmt, ...)
1405 {
1406   if (ctx && severity && fmt)
1407     return;
1408 }
1409
1410 int
1411 nestegg_init(nestegg ** context, nestegg_io io, nestegg_log callback)
1412 {
1413   int r;
1414   uint64_t id, version, docversion;
1415   struct ebml_list_node * track;
1416   char * doctype;
1417   nestegg * ctx = NULL;
1418
1419   if (!(io.read && io.seek && io.tell))
1420     return -1;
1421
1422   ctx = ne_alloc(sizeof(*ctx));
1423
1424   ctx->io = ne_alloc(sizeof(*ctx->io));
1425   *ctx->io = io;
1426   ctx->log = callback;
1427   ctx->alloc_pool = ne_pool_init();
1428
1429   if (!ctx->log)
1430     ctx->log = ne_null_log_callback;
1431
1432   r = ne_peek_element(ctx, &id, NULL);
1433   if (r != 1) {
1434     nestegg_destroy(ctx);
1435     return -1;
1436   }
1437
1438   if (id != ID_EBML) {
1439     nestegg_destroy(ctx);
1440     return -1;
1441   }
1442
1443   ctx->log(ctx, NESTEGG_LOG_DEBUG, "ctx %p", ctx);
1444
1445   ne_ctx_push(ctx, ne_top_level_elements, ctx);
1446
1447   r = ne_parse(ctx, NULL);
1448
1449   if (r != 1) {
1450     nestegg_destroy(ctx);
1451     return -1;
1452   }
1453
1454   if (ne_get_uint(ctx->ebml.ebml_read_version, &version) != 0)
1455     version = 1;
1456   if (version != 1) {
1457     nestegg_destroy(ctx);
1458     return -1;
1459   }
1460
1461   if (ne_get_string(ctx->ebml.doctype, &doctype) != 0)
1462     doctype = "matroska";
1463   if (strcmp(doctype, "webm") != 0) {
1464     nestegg_destroy(ctx);
1465     return -1;
1466   }
1467
1468   if (ne_get_uint(ctx->ebml.doctype_read_version, &docversion) != 0)
1469     docversion = 1;
1470   if (docversion < 1 || docversion > 2) {
1471     nestegg_destroy(ctx);
1472     return -1;
1473   }
1474
1475   if (!ctx->segment.tracks.track_entry.head) {
1476     nestegg_destroy(ctx);
1477     return -1;
1478   }
1479
1480   track = ctx->segment.tracks.track_entry.head;
1481   ctx->track_count = 0;
1482
1483   while (track) {
1484     ctx->track_count += 1;
1485     track = track->next;
1486   }
1487
1488   *context = ctx;
1489
1490   return 0;
1491 }
1492
1493 void
1494 nestegg_destroy(nestegg * ctx)
1495 {
1496   while (ctx->ancestor)
1497     ne_ctx_pop(ctx);
1498   ne_pool_destroy(ctx->alloc_pool);
1499   free(ctx->io);
1500   free(ctx);
1501 }
1502
1503 int
1504 nestegg_duration(nestegg * ctx, uint64_t * duration)
1505 {
1506   uint64_t tc_scale;
1507   double unscaled_duration;
1508
1509   if (ne_get_float(ctx->segment.info.duration, &unscaled_duration) != 0)
1510     return -1;
1511
1512   tc_scale = ne_get_timecode_scale(ctx);
1513
1514   *duration = (uint64_t) (unscaled_duration * tc_scale);
1515   return 0;
1516 }
1517
1518 int
1519 nestegg_tstamp_scale(nestegg * ctx, uint64_t * scale)
1520 {
1521   *scale = ne_get_timecode_scale(ctx);
1522   return 0;
1523 }
1524
1525 int
1526 nestegg_track_count(nestegg * ctx, unsigned int * tracks)
1527 {
1528   *tracks = ctx->track_count;
1529   return 0;
1530 }
1531
1532 int
1533 nestegg_track_seek(nestegg * ctx, unsigned int track, uint64_t tstamp)
1534 {
1535   int r;
1536   struct cue_point * cue_point;
1537   struct cue_track_positions * pos;
1538   struct saved_state state;
1539   struct seek * found;
1540   uint64_t seek_pos, tc_scale, t, id;
1541   struct ebml_list_node * node = ctx->segment.cues.cue_point.head;
1542
1543   /* If there are no cues loaded, check for cues element in the seek head
1544      and load it. */
1545   if (!node) {
1546     found = ne_find_seek_for_id(ctx->segment.seek_head.head, ID_CUES);
1547     if (!found)
1548       return -1;
1549
1550     if (ne_get_uint(found->position, &seek_pos) != 0)
1551       return -1;
1552
1553     /* Save old parser state. */
1554     r = ne_ctx_save(ctx, &state);
1555     if (r != 0)
1556       return -1;
1557
1558     /* Seek and set up parser state for segment-level element (Cues). */
1559     r = ne_io_seek(ctx->io, ctx->segment_offset + seek_pos, NESTEGG_SEEK_SET);
1560     if (r != 0)
1561       return -1;
1562     ctx->last_id = 0;
1563     ctx->last_size = 0;
1564
1565     r = ne_read_element(ctx, &id, NULL);
1566     if (r != 1)
1567       return -1;
1568
1569     if (id != ID_CUES)
1570       return -1;
1571
1572     ctx->ancestor = NULL;
1573     ne_ctx_push(ctx, ne_top_level_elements, ctx);
1574     ne_ctx_push(ctx, ne_segment_elements, &ctx->segment);
1575     ne_ctx_push(ctx, ne_cues_elements, &ctx->segment.cues);
1576     /* parser will run until end of cues element. */
1577     ctx->log(ctx, NESTEGG_LOG_DEBUG, "seek: parsing cue elements");
1578     r = ne_parse(ctx, ne_cues_elements);
1579     while (ctx->ancestor)
1580       ne_ctx_pop(ctx);
1581
1582     /* Reset parser state to original state and seek back to old position. */
1583     if (ne_ctx_restore(ctx, &state) != 0)
1584       return -1;
1585
1586     if (r < 0)
1587       return -1;
1588   }
1589
1590   tc_scale = ne_get_timecode_scale(ctx);
1591
1592   cue_point = ne_find_cue_point_for_tstamp(ctx->segment.cues.cue_point.head, tc_scale, tstamp);
1593   if (!cue_point)
1594     return -1;
1595
1596   node = cue_point->cue_track_positions.head;
1597
1598   seek_pos = 0;
1599
1600   while (node) {
1601     assert(node->id == ID_CUE_TRACK_POSITIONS);
1602     pos = node->data;
1603     if (ne_get_uint(pos->track, &t) == 0 && t - 1 == track) {
1604       if (ne_get_uint(pos->cluster_position, &seek_pos) != 0)
1605         return -1;
1606       break;
1607     }
1608     node = node->next;
1609   }
1610
1611   /* Seek and set up parser state for segment-level element (Cluster). */
1612   r = ne_io_seek(ctx->io, ctx->segment_offset + seek_pos, NESTEGG_SEEK_SET);
1613   if (r != 0)
1614     return -1;
1615   ctx->last_id = 0;
1616   ctx->last_size = 0;
1617
1618   while (ctx->ancestor)
1619     ne_ctx_pop(ctx);
1620
1621   ne_ctx_push(ctx, ne_top_level_elements, ctx);
1622   ne_ctx_push(ctx, ne_segment_elements, &ctx->segment);
1623   ctx->log(ctx, NESTEGG_LOG_DEBUG, "seek: parsing cluster elements");
1624   r = ne_parse(ctx, NULL);
1625   if (r != 1)
1626     return -1;
1627
1628   if (!ne_is_suspend_element(ctx->last_id))
1629     return -1;
1630
1631   return 0;
1632 }
1633
1634 int
1635 nestegg_track_type(nestegg * ctx, unsigned int track)
1636 {
1637   struct track_entry * entry;
1638   uint64_t type;
1639
1640   entry = ne_find_track_entry(ctx, track);
1641   if (!entry)
1642     return -1;
1643
1644   if (ne_get_uint(entry->type, &type) != 0)
1645     return -1;
1646
1647   if (type & TRACK_TYPE_VIDEO)
1648     return NESTEGG_TRACK_VIDEO;
1649
1650   if (type & TRACK_TYPE_AUDIO)
1651     return NESTEGG_TRACK_AUDIO;
1652
1653   return -1;
1654 }
1655
1656 int
1657 nestegg_track_codec_id(nestegg * ctx, unsigned int track)
1658 {
1659   char * codec_id;
1660   struct track_entry * entry;
1661
1662   entry = ne_find_track_entry(ctx, track);
1663   if (!entry)
1664     return -1;
1665
1666   if (ne_get_string(entry->codec_id, &codec_id) != 0)
1667     return -1;
1668
1669   if (strcmp(codec_id, TRACK_ID_VP8) == 0)
1670     return NESTEGG_CODEC_VP8;
1671
1672   if (strcmp(codec_id, TRACK_ID_VORBIS) == 0)
1673     return NESTEGG_CODEC_VORBIS;
1674
1675   return -1;
1676 }
1677
1678 int
1679 nestegg_track_codec_data_count(nestegg * ctx, unsigned int track,
1680                                unsigned int * count)
1681 {
1682   struct track_entry * entry;
1683   struct ebml_binary codec_private;
1684   unsigned char * p;
1685
1686   *count = 0;
1687
1688   entry = ne_find_track_entry(ctx, track);
1689   if (!entry)
1690     return -1;
1691
1692   if (nestegg_track_codec_id(ctx, track) != NESTEGG_CODEC_VORBIS)
1693     return -1;
1694
1695   if (ne_get_binary(entry->codec_private, &codec_private) != 0)
1696     return -1;
1697
1698   if (codec_private.length < 1)
1699     return -1;
1700
1701   p = codec_private.data;
1702   *count = *p + 1;
1703
1704   if (*count > 3)
1705     return -1;
1706
1707   return 0;
1708 }
1709
1710 int
1711 nestegg_track_codec_data(nestegg * ctx, unsigned int track, unsigned int item,
1712                          unsigned char ** data, size_t * length)
1713 {
1714   struct track_entry * entry;
1715   struct ebml_binary codec_private;
1716   uint64_t sizes[3], total;
1717   unsigned char * p;
1718   unsigned int count, i;
1719
1720   *data = NULL;
1721   *length = 0;
1722
1723   entry = ne_find_track_entry(ctx, track);
1724   if (!entry)
1725     return -1;
1726
1727   if (nestegg_track_codec_id(ctx, track) != NESTEGG_CODEC_VORBIS)
1728     return -1;
1729
1730   if (ne_get_binary(entry->codec_private, &codec_private) != 0)
1731     return -1;
1732
1733   p = codec_private.data;
1734   count = *p++ + 1;
1735
1736   if (count > 3)
1737     return -1;
1738
1739   i = 0;
1740   total = 0;
1741   while (--count) {
1742     sizes[i] = ne_xiph_lace_value(&p);
1743     total += sizes[i];
1744     i += 1;
1745   }
1746   sizes[i] = codec_private.length - total - (p - codec_private.data);
1747
1748   for (i = 0; i < item; ++i) {
1749     if (sizes[i] > LIMIT_FRAME)
1750       return -1;
1751     p += sizes[i];
1752   }
1753   *data = p;
1754   *length = sizes[item];
1755
1756   return 0;
1757 }
1758
1759 int
1760 nestegg_track_video_params(nestegg * ctx, unsigned int track,
1761                            nestegg_video_params * params)
1762 {
1763   struct track_entry * entry;
1764   uint64_t value;
1765
1766   memset(params, 0, sizeof(*params));
1767
1768   entry = ne_find_track_entry(ctx, track);
1769   if (!entry)
1770     return -1;
1771
1772   if (nestegg_track_type(ctx, track) != NESTEGG_TRACK_VIDEO)
1773     return -1;
1774
1775   if (ne_get_uint(entry->video.pixel_width, &value) != 0)
1776     return -1;
1777   params->width = value;
1778
1779   if (ne_get_uint(entry->video.pixel_height, &value) != 0)
1780     return -1;
1781   params->height = value;
1782
1783   value = 0;
1784   ne_get_uint(entry->video.pixel_crop_bottom, &value);
1785   params->crop_bottom = value;
1786
1787   value = 0;
1788   ne_get_uint(entry->video.pixel_crop_top, &value);
1789   params->crop_top = value;
1790
1791   value = 0;
1792   ne_get_uint(entry->video.pixel_crop_left, &value);
1793   params->crop_left = value;
1794
1795   value = 0;
1796   ne_get_uint(entry->video.pixel_crop_right, &value);
1797   params->crop_right = value;
1798
1799   value = params->width;
1800   ne_get_uint(entry->video.display_width, &value);
1801   params->display_width = value;
1802
1803   value = params->height;
1804   ne_get_uint(entry->video.display_height, &value);
1805   params->display_height = value;
1806
1807   return 0;
1808 }
1809
1810 int
1811 nestegg_track_audio_params(nestegg * ctx, unsigned int track,
1812                            nestegg_audio_params * params)
1813 {
1814   struct track_entry * entry;
1815   uint64_t value;
1816
1817   memset(params, 0, sizeof(*params));
1818
1819   entry = ne_find_track_entry(ctx, track);
1820   if (!entry)
1821     return -1;
1822
1823   if (nestegg_track_type(ctx, track) != NESTEGG_TRACK_AUDIO)
1824     return -1;
1825
1826   params->rate = 8000;
1827   ne_get_float(entry->audio.sampling_frequency, &params->rate);
1828
1829   value = 1;
1830   ne_get_uint(entry->audio.channels, &value);
1831   params->channels = value;
1832
1833   value = 16;
1834   ne_get_uint(entry->audio.bit_depth, &value);
1835   params->depth = value;
1836
1837   return 0;
1838 }
1839
1840 int
1841 nestegg_read_packet(nestegg * ctx, nestegg_packet ** pkt)
1842 {
1843   int r;
1844   uint64_t id, size;
1845
1846   *pkt = NULL;
1847
1848   for (;;) {
1849     r = ne_peek_element(ctx, &id, &size);
1850     if (r != 1)
1851       return r;
1852
1853     /* any suspend fields must be handled here */
1854     if (ne_is_suspend_element(id)) {
1855       r = ne_read_element(ctx, &id, &size);
1856       if (r != 1)
1857         return r;
1858
1859       /* the only suspend fields are blocks and simple blocks, which we
1860          handle directly. */
1861       r = ne_read_block(ctx, id, size, pkt);
1862       return r;
1863     }
1864
1865     r =  ne_parse(ctx, NULL);
1866     if (r != 1)
1867       return r;
1868   }
1869
1870   return 1;
1871 }
1872
1873 void
1874 nestegg_free_packet(nestegg_packet * pkt)
1875 {
1876   struct frame * frame;
1877
1878   while (pkt->frame) {
1879     frame = pkt->frame;
1880     pkt->frame = frame->next;
1881     free(frame->data);
1882     free(frame);
1883   }
1884
1885  free(pkt);
1886 }
1887
1888 int
1889 nestegg_packet_track(nestegg_packet * pkt, unsigned int * track)
1890 {
1891   *track = pkt->track;
1892   return 0;
1893 }
1894
1895 int
1896 nestegg_packet_tstamp(nestegg_packet * pkt, uint64_t * tstamp)
1897 {
1898   *tstamp = pkt->timecode;
1899   return 0;
1900 }
1901
1902 int
1903 nestegg_packet_count(nestegg_packet * pkt, unsigned int * count)
1904 {
1905   struct frame * f = pkt->frame;
1906
1907   *count = 0;
1908
1909   while (f) {
1910     *count += 1;
1911     f = f->next;
1912   }
1913
1914   return 0;
1915 }
1916
1917 int
1918 nestegg_packet_data(nestegg_packet * pkt, unsigned int item,
1919                     unsigned char ** data, size_t * length)
1920 {
1921   struct frame * f = pkt->frame;
1922   unsigned int count = 0;
1923
1924   *data = NULL;
1925   *length = 0;
1926
1927   while (f) {
1928     if (count == item) {
1929       *data = f->data;
1930       *length = f->length;
1931       return 0;
1932     }
1933     count += 1;
1934     f = f->next;
1935   }
1936
1937   return -1;
1938 }