1// Copyright (c) 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "media/webm/webm_parser.h"
6
7// This file contains code to parse WebM file elements. It was created
8// from information in the Matroska spec.
9// http://www.matroska.org/technical/specs/index.html
10// This file contains code for encrypted WebM. Current WebM
11// encrypted request for comments specification is here
12// http://wiki.webmproject.org/encryption/webm-encryption-rfc
13
14#include <iomanip>
15
16#include "base/logging.h"
17#include "media/webm/webm_constants.h"
18
19namespace media {
20
21enum ElementType {
22  UNKNOWN,
23  LIST,  // Referred to as Master Element in the Matroska spec.
24  UINT,
25  FLOAT,
26  BINARY,
27  STRING,
28  SKIP,
29};
30
31struct ElementIdInfo {
32  ElementType type_;
33  int id_;
34};
35
36struct ListElementInfo {
37  int id_;
38  int level_;
39  const ElementIdInfo* id_info_;
40  int id_info_count_;
41};
42
43// The following are tables indicating what IDs are valid sub-elements
44// of particular elements. If an element is encountered that doesn't
45// appear in the list, a parsing error is signalled. Some elements are
46// marked as SKIP because they are valid, but we don't care about them
47// right now.
48static const ElementIdInfo kEBMLHeaderIds[] = {
49  {UINT, kWebMIdEBMLVersion},
50  {UINT, kWebMIdEBMLReadVersion},
51  {UINT, kWebMIdEBMLMaxIDLength},
52  {UINT, kWebMIdEBMLMaxSizeLength},
53  {STRING, kWebMIdDocType},
54  {UINT, kWebMIdDocTypeVersion},
55  {UINT, kWebMIdDocTypeReadVersion},
56};
57
58static const ElementIdInfo kSegmentIds[] = {
59  {LIST, kWebMIdSeekHead},
60  {LIST, kWebMIdInfo},
61  {LIST, kWebMIdCluster},
62  {LIST, kWebMIdTracks},
63  {LIST, kWebMIdCues},
64  {LIST, kWebMIdAttachments},
65  {LIST, kWebMIdChapters},
66  {LIST, kWebMIdTags},
67};
68
69static const ElementIdInfo kSeekHeadIds[] = {
70  {LIST, kWebMIdSeek},
71};
72
73static const ElementIdInfo kSeekIds[] = {
74  {BINARY, kWebMIdSeekID},
75  {UINT, kWebMIdSeekPosition},
76};
77
78static const ElementIdInfo kInfoIds[] = {
79  {BINARY, kWebMIdSegmentUID},
80  {STRING, kWebMIdSegmentFilename},
81  {BINARY, kWebMIdPrevUID},
82  {STRING, kWebMIdPrevFilename},
83  {BINARY, kWebMIdNextUID},
84  {STRING, kWebMIdNextFilename},
85  {BINARY, kWebMIdSegmentFamily},
86  {LIST, kWebMIdChapterTranslate},
87  {UINT, kWebMIdTimecodeScale},
88  {FLOAT, kWebMIdDuration},
89  {BINARY, kWebMIdDateUTC},
90  {STRING, kWebMIdTitle},
91  {STRING, kWebMIdMuxingApp},
92  {STRING, kWebMIdWritingApp},
93};
94
95static const ElementIdInfo kChapterTranslateIds[] = {
96  {UINT, kWebMIdChapterTranslateEditionUID},
97  {UINT, kWebMIdChapterTranslateCodec},
98  {BINARY, kWebMIdChapterTranslateID},
99};
100
101static const ElementIdInfo kClusterIds[] = {
102  {BINARY, kWebMIdSimpleBlock},
103  {UINT, kWebMIdTimecode},
104  {LIST, kWebMIdSilentTracks},
105  {UINT, kWebMIdPosition},
106  {UINT, kWebMIdPrevSize},
107  {LIST, kWebMIdBlockGroup},
108};
109
110static const ElementIdInfo kSilentTracksIds[] = {
111  {UINT, kWebMIdSilentTrackNumber},
112};
113
114static const ElementIdInfo kBlockGroupIds[] = {
115  {BINARY, kWebMIdBlock},
116  {LIST, kWebMIdBlockAdditions},
117  {UINT, kWebMIdBlockDuration},
118  {UINT, kWebMIdReferencePriority},
119  {BINARY, kWebMIdReferenceBlock},
120  {BINARY, kWebMIdCodecState},
121  {LIST, kWebMIdSlices},
122};
123
124static const ElementIdInfo kBlockAdditionsIds[] = {
125  {LIST, kWebMIdBlockMore},
126};
127
128static const ElementIdInfo kBlockMoreIds[] = {
129  {UINT, kWebMIdBlockAddID},
130  {BINARY, kWebMIdBlockAdditional},
131};
132
133static const ElementIdInfo kSlicesIds[] = {
134  {LIST, kWebMIdTimeSlice},
135};
136
137static const ElementIdInfo kTimeSliceIds[] = {
138  {UINT, kWebMIdLaceNumber},
139};
140
141static const ElementIdInfo kTracksIds[] = {
142  {LIST, kWebMIdTrackEntry},
143};
144
145static const ElementIdInfo kTrackEntryIds[] = {
146  {UINT, kWebMIdTrackNumber},
147  {UINT, kWebMIdTrackUID},
148  {UINT, kWebMIdTrackType},
149  {UINT, kWebMIdFlagEnabled},
150  {UINT, kWebMIdFlagDefault},
151  {UINT, kWebMIdFlagForced},
152  {UINT, kWebMIdFlagLacing},
153  {UINT, kWebMIdMinCache},
154  {UINT, kWebMIdMaxCache},
155  {UINT, kWebMIdDefaultDuration},
156  {FLOAT, kWebMIdTrackTimecodeScale},
157  {UINT, kWebMIdMaxBlockAdditionId},
158  {STRING, kWebMIdName},
159  {STRING, kWebMIdLanguage},
160  {STRING, kWebMIdCodecID},
161  {BINARY, kWebMIdCodecPrivate},
162  {STRING, kWebMIdCodecName},
163  {UINT, kWebMIdAttachmentLink},
164  {UINT, kWebMIdCodecDecodeAll},
165  {UINT, kWebMIdTrackOverlay},
166  {LIST, kWebMIdTrackTranslate},
167  {LIST, kWebMIdVideo},
168  {LIST, kWebMIdAudio},
169  {LIST, kWebMIdTrackOperation},
170  {LIST, kWebMIdContentEncodings},
171};
172
173static const ElementIdInfo kTrackTranslateIds[] = {
174  {UINT, kWebMIdTrackTranslateEditionUID},
175  {UINT, kWebMIdTrackTranslateCodec},
176  {BINARY, kWebMIdTrackTranslateTrackID},
177};
178
179static const ElementIdInfo kVideoIds[] = {
180  {UINT, kWebMIdFlagInterlaced},
181  {UINT, kWebMIdStereoMode},
182  {UINT, kWebMIdAlphaMode},
183  {UINT, kWebMIdPixelWidth},
184  {UINT, kWebMIdPixelHeight},
185  {UINT, kWebMIdPixelCropBottom},
186  {UINT, kWebMIdPixelCropTop},
187  {UINT, kWebMIdPixelCropLeft},
188  {UINT, kWebMIdPixelCropRight},
189  {UINT, kWebMIdDisplayWidth},
190  {UINT, kWebMIdDisplayHeight},
191  {UINT, kWebMIdDisplayUnit},
192  {UINT, kWebMIdAspectRatioType},
193  {BINARY, kWebMIdColorSpace},
194};
195
196static const ElementIdInfo kAudioIds[] = {
197  {FLOAT, kWebMIdSamplingFrequency},
198  {FLOAT, kWebMIdOutputSamplingFrequency},
199  {UINT, kWebMIdChannels},
200  {UINT, kWebMIdBitDepth},
201};
202
203static const ElementIdInfo kTrackOperationIds[] = {
204  {LIST, kWebMIdTrackCombinePlanes},
205  {LIST, kWebMIdJoinBlocks},
206};
207
208static const ElementIdInfo kTrackCombinePlanesIds[] = {
209  {LIST, kWebMIdTrackPlane},
210};
211
212static const ElementIdInfo kTrackPlaneIds[] = {
213  {UINT, kWebMIdTrackPlaneUID},
214  {UINT, kWebMIdTrackPlaneType},
215};
216
217static const ElementIdInfo kJoinBlocksIds[] = {
218  {UINT, kWebMIdTrackJoinUID},
219};
220
221static const ElementIdInfo kContentEncodingsIds[] = {
222  {LIST, kWebMIdContentEncoding},
223};
224
225static const ElementIdInfo kContentEncodingIds[] = {
226  {UINT, kWebMIdContentEncodingOrder},
227  {UINT, kWebMIdContentEncodingScope},
228  {UINT, kWebMIdContentEncodingType},
229  {LIST, kWebMIdContentCompression},
230  {LIST, kWebMIdContentEncryption},
231};
232
233static const ElementIdInfo kContentCompressionIds[] = {
234  {UINT, kWebMIdContentCompAlgo},
235  {BINARY, kWebMIdContentCompSettings},
236};
237
238static const ElementIdInfo kContentEncryptionIds[] = {
239  {LIST, kWebMIdContentEncAESSettings},
240  {UINT, kWebMIdContentEncAlgo},
241  {BINARY, kWebMIdContentEncKeyID},
242  {BINARY, kWebMIdContentSignature},
243  {BINARY, kWebMIdContentSigKeyID},
244  {UINT, kWebMIdContentSigAlgo},
245  {UINT, kWebMIdContentSigHashAlgo},
246};
247
248static const ElementIdInfo kContentEncAESSettingsIds[] = {
249  {UINT, kWebMIdAESSettingsCipherMode},
250};
251
252static const ElementIdInfo kCuesIds[] = {
253  {LIST, kWebMIdCuePoint},
254};
255
256static const ElementIdInfo kCuePointIds[] = {
257  {UINT, kWebMIdCueTime},
258  {LIST, kWebMIdCueTrackPositions},
259};
260
261static const ElementIdInfo kCueTrackPositionsIds[] = {
262  {UINT, kWebMIdCueTrack},
263  {UINT, kWebMIdCueClusterPosition},
264  {UINT, kWebMIdCueBlockNumber},
265  {UINT, kWebMIdCueCodecState},
266  {LIST, kWebMIdCueReference},
267};
268
269static const ElementIdInfo kCueReferenceIds[] = {
270  {UINT, kWebMIdCueRefTime},
271};
272
273static const ElementIdInfo kAttachmentsIds[] = {
274  {LIST, kWebMIdAttachedFile},
275};
276
277static const ElementIdInfo kAttachedFileIds[] = {
278  {STRING, kWebMIdFileDescription},
279  {STRING, kWebMIdFileName},
280  {STRING, kWebMIdFileMimeType},
281  {BINARY, kWebMIdFileData},
282  {UINT, kWebMIdFileUID},
283};
284
285static const ElementIdInfo kChaptersIds[] = {
286  {LIST, kWebMIdEditionEntry},
287};
288
289static const ElementIdInfo kEditionEntryIds[] = {
290  {UINT, kWebMIdEditionUID},
291  {UINT, kWebMIdEditionFlagHidden},
292  {UINT, kWebMIdEditionFlagDefault},
293  {UINT, kWebMIdEditionFlagOrdered},
294  {LIST, kWebMIdChapterAtom},
295};
296
297static const ElementIdInfo kChapterAtomIds[] = {
298  {UINT, kWebMIdChapterUID},
299  {UINT, kWebMIdChapterTimeStart},
300  {UINT, kWebMIdChapterTimeEnd},
301  {UINT, kWebMIdChapterFlagHidden},
302  {UINT, kWebMIdChapterFlagEnabled},
303  {BINARY, kWebMIdChapterSegmentUID},
304  {UINT, kWebMIdChapterSegmentEditionUID},
305  {UINT, kWebMIdChapterPhysicalEquiv},
306  {LIST, kWebMIdChapterTrack},
307  {LIST, kWebMIdChapterDisplay},
308  {LIST, kWebMIdChapProcess},
309};
310
311static const ElementIdInfo kChapterTrackIds[] = {
312  {UINT, kWebMIdChapterTrackNumber},
313};
314
315static const ElementIdInfo kChapterDisplayIds[] = {
316  {STRING, kWebMIdChapString},
317  {STRING, kWebMIdChapLanguage},
318  {STRING, kWebMIdChapCountry},
319};
320
321static const ElementIdInfo kChapProcessIds[] = {
322  {UINT, kWebMIdChapProcessCodecID},
323  {BINARY, kWebMIdChapProcessPrivate},
324  {LIST, kWebMIdChapProcessCommand},
325};
326
327static const ElementIdInfo kChapProcessCommandIds[] = {
328  {UINT, kWebMIdChapProcessTime},
329  {BINARY, kWebMIdChapProcessData},
330};
331
332static const ElementIdInfo kTagsIds[] = {
333  {LIST, kWebMIdTag},
334};
335
336static const ElementIdInfo kTagIds[] = {
337  {LIST, kWebMIdTargets},
338  {LIST, kWebMIdSimpleTag},
339};
340
341static const ElementIdInfo kTargetsIds[] = {
342  {UINT, kWebMIdTargetTypeValue},
343  {STRING, kWebMIdTargetType},
344  {UINT, kWebMIdTagTrackUID},
345  {UINT, kWebMIdTagEditionUID},
346  {UINT, kWebMIdTagChapterUID},
347  {UINT, kWebMIdTagAttachmentUID},
348};
349
350static const ElementIdInfo kSimpleTagIds[] = {
351  {STRING, kWebMIdTagName},
352  {STRING, kWebMIdTagLanguage},
353  {UINT, kWebMIdTagDefault},
354  {STRING, kWebMIdTagString},
355  {BINARY, kWebMIdTagBinary},
356};
357
358#define LIST_ELEMENT_INFO(id, level, id_info) \
359    { (id), (level), (id_info), arraysize(id_info) }
360
361static const ListElementInfo kListElementInfo[] = {
362  LIST_ELEMENT_INFO(kWebMIdCluster, 1, kClusterIds),
363  LIST_ELEMENT_INFO(kWebMIdEBMLHeader, 0, kEBMLHeaderIds),
364  LIST_ELEMENT_INFO(kWebMIdSegment, 0, kSegmentIds),
365  LIST_ELEMENT_INFO(kWebMIdSeekHead, 1, kSeekHeadIds),
366  LIST_ELEMENT_INFO(kWebMIdSeek, 2, kSeekIds),
367  LIST_ELEMENT_INFO(kWebMIdInfo, 1, kInfoIds),
368  LIST_ELEMENT_INFO(kWebMIdChapterTranslate, 2, kChapterTranslateIds),
369  LIST_ELEMENT_INFO(kWebMIdSilentTracks, 2, kSilentTracksIds),
370  LIST_ELEMENT_INFO(kWebMIdBlockGroup, 2, kBlockGroupIds),
371  LIST_ELEMENT_INFO(kWebMIdBlockAdditions, 3, kBlockAdditionsIds),
372  LIST_ELEMENT_INFO(kWebMIdBlockMore, 4, kBlockMoreIds),
373  LIST_ELEMENT_INFO(kWebMIdSlices, 3, kSlicesIds),
374  LIST_ELEMENT_INFO(kWebMIdTimeSlice, 4, kTimeSliceIds),
375  LIST_ELEMENT_INFO(kWebMIdTracks, 1, kTracksIds),
376  LIST_ELEMENT_INFO(kWebMIdTrackEntry, 2, kTrackEntryIds),
377  LIST_ELEMENT_INFO(kWebMIdTrackTranslate, 3, kTrackTranslateIds),
378  LIST_ELEMENT_INFO(kWebMIdVideo, 3, kVideoIds),
379  LIST_ELEMENT_INFO(kWebMIdAudio, 3, kAudioIds),
380  LIST_ELEMENT_INFO(kWebMIdTrackOperation, 3, kTrackOperationIds),
381  LIST_ELEMENT_INFO(kWebMIdTrackCombinePlanes, 4, kTrackCombinePlanesIds),
382  LIST_ELEMENT_INFO(kWebMIdTrackPlane, 5, kTrackPlaneIds),
383  LIST_ELEMENT_INFO(kWebMIdJoinBlocks, 4, kJoinBlocksIds),
384  LIST_ELEMENT_INFO(kWebMIdContentEncodings, 3, kContentEncodingsIds),
385  LIST_ELEMENT_INFO(kWebMIdContentEncoding, 4, kContentEncodingIds),
386  LIST_ELEMENT_INFO(kWebMIdContentCompression, 5, kContentCompressionIds),
387  LIST_ELEMENT_INFO(kWebMIdContentEncryption, 5, kContentEncryptionIds),
388  LIST_ELEMENT_INFO(kWebMIdContentEncAESSettings, 6, kContentEncAESSettingsIds),
389  LIST_ELEMENT_INFO(kWebMIdCues, 1, kCuesIds),
390  LIST_ELEMENT_INFO(kWebMIdCuePoint, 2, kCuePointIds),
391  LIST_ELEMENT_INFO(kWebMIdCueTrackPositions, 3, kCueTrackPositionsIds),
392  LIST_ELEMENT_INFO(kWebMIdCueReference, 4, kCueReferenceIds),
393  LIST_ELEMENT_INFO(kWebMIdAttachments, 1, kAttachmentsIds),
394  LIST_ELEMENT_INFO(kWebMIdAttachedFile, 2, kAttachedFileIds),
395  LIST_ELEMENT_INFO(kWebMIdChapters, 1, kChaptersIds),
396  LIST_ELEMENT_INFO(kWebMIdEditionEntry, 2, kEditionEntryIds),
397  LIST_ELEMENT_INFO(kWebMIdChapterAtom, 3, kChapterAtomIds),
398  LIST_ELEMENT_INFO(kWebMIdChapterTrack, 4, kChapterTrackIds),
399  LIST_ELEMENT_INFO(kWebMIdChapterDisplay, 4, kChapterDisplayIds),
400  LIST_ELEMENT_INFO(kWebMIdChapProcess, 4, kChapProcessIds),
401  LIST_ELEMENT_INFO(kWebMIdChapProcessCommand, 5, kChapProcessCommandIds),
402  LIST_ELEMENT_INFO(kWebMIdTags, 1, kTagsIds),
403  LIST_ELEMENT_INFO(kWebMIdTag, 2, kTagIds),
404  LIST_ELEMENT_INFO(kWebMIdTargets, 3, kTargetsIds),
405  LIST_ELEMENT_INFO(kWebMIdSimpleTag, 3, kSimpleTagIds),
406};
407
408// Parses an element header id or size field. These fields are variable length
409// encoded. The first byte indicates how many bytes the field occupies.
410// |buf|  - The buffer to parse.
411// |size| - The number of bytes in |buf|
412// |max_bytes| - The maximum number of bytes the field can be. ID fields
413//               set this to 4 & element size fields set this to 8. If the
414//               first byte indicates a larger field size than this it is a
415//               parser error.
416// |mask_first_byte| - For element size fields the field length encoding bits
417//                     need to be masked off. This parameter is true for
418//                     element size fields and is false for ID field values.
419//
420// Returns: The number of bytes parsed on success. -1 on error.
421static int ParseWebMElementHeaderField(const uint8* buf, int size,
422                                       int max_bytes, bool mask_first_byte,
423                                       int64* num) {
424  DCHECK(buf);
425  DCHECK(num);
426
427  if (size < 0)
428    return -1;
429
430  if (size == 0)
431    return 0;
432
433  int mask = 0x80;
434  uint8 ch = buf[0];
435  int extra_bytes = -1;
436  bool all_ones = false;
437  for (int i = 0; i < max_bytes; ++i) {
438    if ((ch & mask) != 0) {
439      mask = ~mask & 0xff;
440      *num = mask_first_byte ? ch & mask : ch;
441      all_ones = (ch & mask) == mask;
442      extra_bytes = i;
443      break;
444    }
445    mask = 0x80 | mask >> 1;
446  }
447
448  if (extra_bytes == -1)
449    return -1;
450
451  // Return 0 if we need more data.
452  if ((1 + extra_bytes) > size)
453    return 0;
454
455  int bytes_used = 1;
456
457  for (int i = 0; i < extra_bytes; ++i) {
458    ch = buf[bytes_used++];
459    all_ones &= (ch == 0xff);
460    *num = (*num << 8) | ch;
461  }
462
463  if (all_ones)
464    *num = kint64max;
465
466  return bytes_used;
467}
468
469int WebMParseElementHeader(const uint8* buf, int size,
470                           int* id, int64* element_size) {
471  DCHECK(buf);
472  DCHECK_GE(size, 0);
473  DCHECK(id);
474  DCHECK(element_size);
475
476  if (size == 0)
477    return 0;
478
479  int64 tmp = 0;
480  int num_id_bytes = ParseWebMElementHeaderField(buf, size, 4, false, &tmp);
481
482  if (num_id_bytes <= 0)
483    return num_id_bytes;
484
485  if (tmp == kint64max)
486    tmp = kWebMReservedId;
487
488  *id = static_cast<int>(tmp);
489
490  int num_size_bytes = ParseWebMElementHeaderField(buf + num_id_bytes,
491                                                   size - num_id_bytes,
492                                                   8, true, &tmp);
493
494  if (num_size_bytes <= 0)
495    return num_size_bytes;
496
497  if (tmp == kint64max)
498    tmp = kWebMUnknownSize;
499
500  *element_size = tmp;
501  DVLOG(3) << "WebMParseElementHeader() : id " << std::hex << *id << std::dec
502           << " size " << *element_size;
503  return num_id_bytes + num_size_bytes;
504}
505
506// Finds ElementType for a specific ID.
507static ElementType FindIdType(int id,
508                              const ElementIdInfo* id_info,
509                              int id_info_count) {
510
511  // Check for global element IDs that can be anywhere.
512  if (id == kWebMIdVoid || id == kWebMIdCRC32)
513    return SKIP;
514
515  for (int i = 0; i < id_info_count; ++i) {
516    if (id == id_info[i].id_)
517      return id_info[i].type_;
518  }
519
520  return UNKNOWN;
521}
522
523// Finds ListElementInfo for a specific ID.
524static const ListElementInfo* FindListInfo(int id) {
525  for (size_t i = 0; i < arraysize(kListElementInfo); ++i) {
526    if (id == kListElementInfo[i].id_)
527      return &kListElementInfo[i];
528  }
529
530  return NULL;
531}
532
533static int FindListLevel(int id) {
534  const ListElementInfo* list_info = FindListInfo(id);
535  if (list_info)
536    return list_info->level_;
537
538  return -1;
539}
540
541static int ParseUInt(const uint8* buf, int size, int id,
542                     WebMParserClient* client) {
543  if ((size <= 0) || (size > 8))
544    return -1;
545
546  // Read in the big-endian integer.
547  int64 value = 0;
548  for (int i = 0; i < size; ++i)
549    value = (value << 8) | buf[i];
550
551  if (!client->OnUInt(id, value))
552    return -1;
553
554  return size;
555}
556
557static int ParseFloat(const uint8* buf, int size, int id,
558                      WebMParserClient* client) {
559
560  if ((size != 4) && (size != 8))
561    return -1;
562
563  double value = -1;
564
565  // Read the bytes from big-endian form into a native endian integer.
566  int64 tmp = 0;
567  for (int i = 0; i < size; ++i)
568    tmp = (tmp << 8) | buf[i];
569
570  // Use a union to convert the integer bit pattern into a floating point
571  // number.
572  if (size == 4) {
573    union {
574      int32 src;
575      float dst;
576    } tmp2;
577    tmp2.src = static_cast<int32>(tmp);
578    value = tmp2.dst;
579  } else if (size == 8) {
580    union {
581      int64 src;
582      double dst;
583    } tmp2;
584    tmp2.src = tmp;
585    value = tmp2.dst;
586  } else {
587    return -1;
588  }
589
590  if (!client->OnFloat(id, value))
591    return -1;
592
593  return size;
594}
595
596static int ParseBinary(const uint8* buf, int size, int id,
597                       WebMParserClient* client) {
598  return client->OnBinary(id, buf, size) ? size : -1;
599}
600
601static int ParseString(const uint8* buf, int size, int id,
602                       WebMParserClient* client) {
603  const uint8* end = static_cast<const uint8*>(memchr(buf, '\0', size));
604  int length = (end != NULL) ? static_cast<int>(end - buf) : size;
605  std::string str(reinterpret_cast<const char*>(buf), length);
606  return client->OnString(id, str) ? size : -1;
607}
608
609static int ParseNonListElement(ElementType type, int id, int64 element_size,
610                               const uint8* buf, int size,
611                               WebMParserClient* client) {
612  DCHECK_GE(size, element_size);
613
614  int result = -1;
615  switch(type) {
616    case LIST:
617      NOTIMPLEMENTED();
618      result = -1;
619      break;
620    case UINT:
621      result = ParseUInt(buf, element_size, id, client);
622      break;
623    case FLOAT:
624      result = ParseFloat(buf, element_size, id, client);
625      break;
626    case BINARY:
627      result = ParseBinary(buf, element_size, id, client);
628      break;
629    case STRING:
630      result = ParseString(buf, element_size, id, client);
631      break;
632    case SKIP:
633      result = element_size;
634      break;
635    default:
636      DVLOG(1) << "Unhandled ID type " << type;
637      return -1;
638  };
639
640  DCHECK_LE(result, size);
641  return result;
642}
643
644WebMParserClient::WebMParserClient() {}
645WebMParserClient::~WebMParserClient() {}
646
647WebMParserClient* WebMParserClient::OnListStart(int id) {
648  DVLOG(1) << "Unexpected list element start with ID " << std::hex << id;
649  return NULL;
650}
651
652bool WebMParserClient::OnListEnd(int id) {
653  DVLOG(1) << "Unexpected list element end with ID " << std::hex << id;
654  return false;
655}
656
657bool WebMParserClient::OnUInt(int id, int64 val) {
658  DVLOG(1) << "Unexpected unsigned integer element with ID " << std::hex << id;
659  return false;
660}
661
662bool WebMParserClient::OnFloat(int id, double val) {
663  DVLOG(1) << "Unexpected float element with ID " << std::hex << id;
664  return false;
665}
666
667bool WebMParserClient::OnBinary(int id, const uint8* data, int size) {
668  DVLOG(1) << "Unexpected binary element with ID " << std::hex << id;
669  return false;
670}
671
672bool WebMParserClient::OnString(int id, const std::string& str) {
673  DVLOG(1) << "Unexpected string element with ID " << std::hex << id;
674  return false;
675}
676
677WebMListParser::WebMListParser(int id, WebMParserClient* client)
678    : state_(NEED_LIST_HEADER),
679      root_id_(id),
680      root_level_(FindListLevel(id)),
681      root_client_(client) {
682  DCHECK_GE(root_level_, 0);
683  DCHECK(client);
684}
685
686WebMListParser::~WebMListParser() {}
687
688void WebMListParser::Reset() {
689  ChangeState(NEED_LIST_HEADER);
690  list_state_stack_.clear();
691}
692
693int WebMListParser::Parse(const uint8* buf, int size) {
694  DCHECK(buf);
695
696  if (size < 0 || state_ == PARSE_ERROR || state_ == DONE_PARSING_LIST)
697    return -1;
698
699  if (size == 0)
700    return 0;
701
702  const uint8* cur = buf;
703  int cur_size = size;
704  int bytes_parsed = 0;
705
706  while (cur_size > 0 && state_ != PARSE_ERROR && state_ != DONE_PARSING_LIST) {
707    int element_id = 0;
708    int64 element_size = 0;
709    int result = WebMParseElementHeader(cur, cur_size, &element_id,
710                                        &element_size);
711
712    if (result < 0)
713      return result;
714
715    if (result == 0)
716      return bytes_parsed;
717
718    switch(state_) {
719      case NEED_LIST_HEADER: {
720        if (element_id != root_id_) {
721          ChangeState(PARSE_ERROR);
722          return -1;
723        }
724
725        // Only allow Segment & Cluster to have an unknown size.
726        if (element_size == kWebMUnknownSize &&
727            (element_id != kWebMIdSegment) &&
728            (element_id != kWebMIdCluster)) {
729          ChangeState(PARSE_ERROR);
730          return -1;
731        }
732
733        ChangeState(INSIDE_LIST);
734        if (!OnListStart(root_id_, element_size))
735          return -1;
736
737        break;
738      }
739
740      case INSIDE_LIST: {
741        int header_size = result;
742        const uint8* element_data = cur + header_size;
743        int element_data_size = cur_size - header_size;
744
745        if (element_size < element_data_size)
746          element_data_size = element_size;
747
748        result = ParseListElement(header_size, element_id, element_size,
749                                  element_data, element_data_size);
750
751        DCHECK_LE(result, header_size + element_data_size);
752        if (result < 0) {
753          ChangeState(PARSE_ERROR);
754          return -1;
755        }
756
757        if (result == 0)
758          return bytes_parsed;
759
760        break;
761      }
762      case DONE_PARSING_LIST:
763      case PARSE_ERROR:
764        // Shouldn't be able to get here.
765        NOTIMPLEMENTED();
766        break;
767    }
768
769    cur += result;
770    cur_size -= result;
771    bytes_parsed += result;
772  }
773
774  return (state_ == PARSE_ERROR) ? -1 : bytes_parsed;
775}
776
777bool WebMListParser::IsParsingComplete() const {
778  return state_ == DONE_PARSING_LIST;
779}
780
781void WebMListParser::ChangeState(State new_state) {
782  state_ = new_state;
783}
784
785int WebMListParser::ParseListElement(int header_size,
786                                     int id, int64 element_size,
787                                     const uint8* data, int size) {
788  DCHECK_GT(list_state_stack_.size(), 0u);
789
790  ListState& list_state = list_state_stack_.back();
791  DCHECK(list_state.element_info_);
792
793  const ListElementInfo* element_info = list_state.element_info_;
794  ElementType id_type =
795      FindIdType(id, element_info->id_info_, element_info->id_info_count_);
796
797  // Unexpected ID.
798  if (id_type == UNKNOWN) {
799    if (list_state.size_ != kWebMUnknownSize ||
800        !IsSiblingOrAncestor(list_state.id_, id)) {
801      DVLOG(1) << "No ElementType info for ID 0x" << std::hex << id;
802      return -1;
803    }
804
805    // We've reached the end of a list of unknown size. Update the size now that
806    // we know it and dispatch the end of list calls.
807    list_state.size_ = list_state.bytes_parsed_;
808
809    if (!OnListEnd())
810      return -1;
811
812    // Check to see if all open lists have ended.
813    if (list_state_stack_.size() == 0)
814      return 0;
815
816    list_state = list_state_stack_.back();
817  }
818
819  // Make sure the whole element can fit inside the current list.
820  int64 total_element_size = header_size + element_size;
821  if (list_state.size_ != kWebMUnknownSize &&
822      list_state.size_ < list_state.bytes_parsed_ + total_element_size) {
823    return -1;
824  }
825
826  if (id_type == LIST) {
827    list_state.bytes_parsed_ += header_size;
828
829    if (!OnListStart(id, element_size))
830      return -1;
831    return header_size;
832  }
833
834  // Make sure we have the entire element before trying to parse a non-list
835  // element.
836  if (size < element_size)
837    return 0;
838
839  int bytes_parsed = ParseNonListElement(id_type, id, element_size,
840                                         data, size, list_state.client_);
841  DCHECK_LE(bytes_parsed, size);
842
843  // Return if an error occurred or we need more data.
844  // Note: bytes_parsed is 0 for a successful parse of a size 0 element. We
845  // need to check the element_size to disambiguate the "need more data" case
846  // from a successful parse.
847  if (bytes_parsed < 0 || (bytes_parsed == 0 && element_size != 0))
848    return bytes_parsed;
849
850  int result = header_size + bytes_parsed;
851  list_state.bytes_parsed_ += result;
852
853  // See if we have reached the end of the current list.
854  if (list_state.bytes_parsed_ == list_state.size_) {
855    if (!OnListEnd())
856      return -1;
857  }
858
859  return result;
860}
861
862bool WebMListParser::OnListStart(int id, int64 size) {
863  const ListElementInfo* element_info = FindListInfo(id);
864  if (!element_info)
865    return false;
866
867  int current_level = root_level_ + list_state_stack_.size() - 1;
868  if (current_level + 1 != element_info->level_)
869    return false;
870
871  WebMParserClient* current_list_client = NULL;
872  if (!list_state_stack_.empty()) {
873    // Make sure the new list doesn't go past the end of the current list.
874    ListState current_list_state = list_state_stack_.back();
875    if (current_list_state.size_ != kWebMUnknownSize &&
876        current_list_state.size_ < current_list_state.bytes_parsed_ + size)
877      return false;
878    current_list_client = current_list_state.client_;
879  } else {
880    current_list_client = root_client_;
881  }
882
883  WebMParserClient* new_list_client = current_list_client->OnListStart(id);
884  if (!new_list_client)
885    return false;
886
887  ListState new_list_state = { id, size, 0, element_info, new_list_client };
888  list_state_stack_.push_back(new_list_state);
889
890  if (size == 0)
891    return OnListEnd();
892
893  return true;
894}
895
896bool WebMListParser::OnListEnd() {
897  int lists_ended = 0;
898  for (; !list_state_stack_.empty(); ++lists_ended) {
899    const ListState& list_state = list_state_stack_.back();
900
901    if (list_state.bytes_parsed_ != list_state.size_)
902      break;
903
904    list_state_stack_.pop_back();
905
906    int64 bytes_parsed = list_state.bytes_parsed_;
907    WebMParserClient* client = NULL;
908    if (!list_state_stack_.empty()) {
909      // Update the bytes_parsed_ for the parent element.
910      list_state_stack_.back().bytes_parsed_ += bytes_parsed;
911      client = list_state_stack_.back().client_;
912    } else {
913      client = root_client_;
914    }
915
916    if (!client->OnListEnd(list_state.id_))
917      return false;
918  }
919
920  DCHECK_GE(lists_ended, 1);
921
922  if (list_state_stack_.empty())
923    ChangeState(DONE_PARSING_LIST);
924
925  return true;
926}
927
928bool WebMListParser::IsSiblingOrAncestor(int id_a, int id_b) const {
929  DCHECK((id_a == kWebMIdSegment) || (id_a == kWebMIdCluster));
930
931  if (id_a == kWebMIdCluster) {
932    // kWebMIdCluster siblings.
933    for (size_t i = 0; i < arraysize(kSegmentIds); i++) {
934      if (kSegmentIds[i].id_ == id_b)
935        return true;
936    }
937  }
938
939  // kWebMIdSegment siblings.
940  return ((id_b == kWebMIdSegment) || (id_b == kWebMIdEBMLHeader));
941}
942
943}  // namespace media
944