Add support for incremental cluster parsing.

media/webm/webm_parser.cc

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "media/webm/webm_parser.h"
 
 // This file contains code to parse WebM file elements. It was created
 // from information in the Matroska spec.
 // http://www.matroska.org/technical/specs/index.html
 
 #include <iomanip>
 
 #include "base/logging.h"
 #include "media/webm/webm_constants.h"
 
 namespace media {
 
 // Maximum depth of WebM elements. Some WebM elements are lists of
 // other elements. This limits the number levels of recursion allowed.
 static const int kMaxLevelDepth = 6;
 
 enum ElementType {
+  UNKNOWN,
   LIST,
   UINT,
   FLOAT,
   BINARY,
   STRING,
   SBLOCK,
   SKIP,
 };
 
 struct ElementIdInfo {
-  int level_;
   ElementType type_;
   int id_;
 };
 
 struct ListElementInfo {
   int id_;
+  int level_;
   const ElementIdInfo* id_info_;
   int id_info_size_;
 };
 
 // The following are tables indicating what IDs are valid sub-elements
 // of particular elements. If an element is encountered that doesn't
 // appear in the list, a parsing error is signalled. Some elements are
 // marked as SKIP because they are valid, but we don't care about them
 // right now.
 static const ElementIdInfo kClusterIds[] = {
-  {2, UINT, kWebMIdTimecode},
-  {2, SBLOCK, kWebMIdSimpleBlock},
-  {2, LIST, kWebMIdBlockGroup},
+  {UINT, kWebMIdTimecode},
+  {SBLOCK, kWebMIdSimpleBlock},
+  {LIST, kWebMIdBlockGroup},
+};
+
+static const ElementIdInfo kSegmentIds[] = {
+  {SKIP, kWebMIdSeekHead},  // TODO(acolwell): add SeekHead info
+  {LIST, kWebMIdInfo},
+  {LIST, kWebMIdCluster},
+  {LIST, kWebMIdTracks},
+  {SKIP, kWebMIdCues},  // TODO(acolwell): add CUES info
 };
 
 static const ElementIdInfo kInfoIds[] = {
-  {2, SKIP, kWebMIdSegmentUID},
-  {2, UINT, kWebMIdTimecodeScale},
-  {2, FLOAT, kWebMIdDuration},
-  {2, SKIP, kWebMIdDateUTC},
-  {2, SKIP, kWebMIdTitle},
-  {2, SKIP, kWebMIdMuxingApp},
-  {2, SKIP, kWebMIdWritingApp},
+  {SKIP, kWebMIdSegmentUID},
+  {UINT, kWebMIdTimecodeScale},
+  {FLOAT, kWebMIdDuration},
+  {SKIP, kWebMIdDateUTC},
+  {SKIP, kWebMIdTitle},
+  {SKIP, kWebMIdMuxingApp},
+  {SKIP, kWebMIdWritingApp},
 };
 
 static const ElementIdInfo kTracksIds[] = {
-  {2, LIST, kWebMIdTrackEntry},
+  {LIST, kWebMIdTrackEntry},
 };
 
 static const ElementIdInfo kTrackEntryIds[] = {
-  {3, UINT, kWebMIdTrackNumber},
-  {3, SKIP, kWebMIdTrackUID},
-  {3, UINT, kWebMIdTrackType},
-  {3, SKIP, kWebMIdFlagEnabled},
-  {3, SKIP, kWebMIdFlagDefault},
-  {3, SKIP, kWebMIdFlagForced},
-  {3, UINT, kWebMIdFlagLacing},
-  {3, UINT, kWebMIdDefaultDuration},
-  {3, SKIP, kWebMIdName},
-  {3, SKIP, kWebMIdLanguage},
-  {3, STRING, kWebMIdCodecID},
-  {3, BINARY, kWebMIdCodecPrivate},
-  {3, SKIP, kWebMIdCodecName},
-  {3, LIST, kWebMIdVideo},
-  {3, LIST, kWebMIdAudio},
+  {UINT, kWebMIdTrackNumber},
+  {SKIP, kWebMIdTrackUID},
+  {UINT, kWebMIdTrackType},
+  {SKIP, kWebMIdFlagEnabled},
+  {SKIP, kWebMIdFlagDefault},
+  {SKIP, kWebMIdFlagForced},
+  {UINT, kWebMIdFlagLacing},
+  {UINT, kWebMIdDefaultDuration},
+  {SKIP, kWebMIdName},
+  {SKIP, kWebMIdLanguage},
+  {STRING, kWebMIdCodecID},
+  {BINARY, kWebMIdCodecPrivate},
+  {SKIP, kWebMIdCodecName},
+  {LIST, kWebMIdVideo},
+  {LIST, kWebMIdAudio},
 };
 
 static const ElementIdInfo kVideoIds[] = {
-  {4, SKIP, kWebMIdFlagInterlaced},
-  {4, SKIP, kWebMIdStereoMode},
-  {4, UINT, kWebMIdPixelWidth},
-  {4, UINT, kWebMIdPixelHeight},
-  {4, SKIP, kWebMIdPixelCropBottom},
-  {4, SKIP, kWebMIdPixelCropTop},
-  {4, SKIP, kWebMIdPixelCropLeft},
-  {4, SKIP, kWebMIdPixelCropRight},
-  {4, SKIP, kWebMIdDisplayWidth},
-  {4, SKIP, kWebMIdDisplayHeight},
-  {4, SKIP, kWebMIdDisplayUnit},
-  {4, SKIP, kWebMIdAspectRatioType},
+  {SKIP, kWebMIdFlagInterlaced},
+  {SKIP, kWebMIdStereoMode},
+  {UINT, kWebMIdPixelWidth},
+  {UINT, kWebMIdPixelHeight},
+  {SKIP, kWebMIdPixelCropBottom},
+  {SKIP, kWebMIdPixelCropTop},
+  {SKIP, kWebMIdPixelCropLeft},
+  {SKIP, kWebMIdPixelCropRight},
+  {SKIP, kWebMIdDisplayWidth},
+  {SKIP, kWebMIdDisplayHeight},
+  {SKIP, kWebMIdDisplayUnit},
+  {SKIP, kWebMIdAspectRatioType},
 };
 
 static const ElementIdInfo kAudioIds[] = {
-  {4, SKIP, kWebMIdSamplingFrequency},
-  {4, SKIP, kWebMIdOutputSamplingFrequency},
-  {4, UINT, kWebMIdChannels},
-  {4, SKIP, kWebMIdBitDepth},
-};
-
-static const ElementIdInfo kClustersOnly[] = {
-  {1, LIST, kWebMIdCluster},
+  {SKIP, kWebMIdSamplingFrequency},
+  {SKIP, kWebMIdOutputSamplingFrequency},
+  {UINT, kWebMIdChannels},
+  {SKIP, kWebMIdBitDepth},
 };
 
 static const ListElementInfo kListElementInfo[] = {
-  { kWebMIdCluster,    kClusterIds,    sizeof(kClusterIds) },
-  { kWebMIdInfo,       kInfoIds,       sizeof(kInfoIds) },
-  { kWebMIdTracks,     kTracksIds,     sizeof(kTracksIds) },
-  { kWebMIdTrackEntry, kTrackEntryIds, sizeof(kTrackEntryIds) },
-  { kWebMIdVideo,      kVideoIds,      sizeof(kVideoIds) },
-  { kWebMIdAudio,      kAudioIds,      sizeof(kAudioIds) },
+  { kWebMIdCluster,    1, kClusterIds,    sizeof(kClusterIds) },
+  { kWebMIdSegment,    0, kSegmentIds,    sizeof(kSegmentIds) },
+  { kWebMIdInfo,       1, kInfoIds,       sizeof(kInfoIds) },
+  { kWebMIdTracks,     1, kTracksIds,     sizeof(kTracksIds) },
+  { kWebMIdTrackEntry, 2, kTrackEntryIds, sizeof(kTrackEntryIds) },
+  { kWebMIdVideo,      3, kVideoIds,      sizeof(kVideoIds) },
+  { kWebMIdAudio,      3, kAudioIds,      sizeof(kAudioIds) },
 };
 
-// Number of elements in kListElementInfo.
-const int kListElementInfoCount =
-    sizeof(kListElementInfo) / sizeof(ListElementInfo);
-
-WebMParserClient::~WebMParserClient() {}
-
 // Parses an element header id or size field. These fields are variable length
 // encoded. The first byte indicates how many bytes the field occupies.
 // |buf|  - The buffer to parse.
 // |size| - The number of bytes in |buf|
 // |max_bytes| - The maximum number of bytes the field can be. ID fields
 //               set this to 4 & element size fields set this to 8. If the
 //               first byte indicates a larger field size than this it is a
 //               parser error.
 // |mask_first_byte| - For element size fields the field length encoding bits
 //                     need to be masked off. This parameter is true for
@@ skipping 61 matching lines @@
                                                    size - num_id_bytes,
                                                    8, true, &tmp);
 
   if (num_size_bytes <= 0)
     return num_size_bytes;
 
   *element_size = tmp;
   return num_id_bytes + num_size_bytes;
 }
 
-// Finds ElementIdInfo for a specific ID.
-static const ElementIdInfo* FindIdInfo(int id,
-                                       const ElementIdInfo* id_info,
-                                       int id_info_size) {
+// Finds ElementType for a specific ID.
+static const ElementType FindIdType(int id,
+                                    const ElementIdInfo* id_info,
+                                    int id_info_size) {
+
+  // Check for global element IDs that can be anywhere.
+  if (id == kWebMIdVoid || id == kWebMIdCRC32)
+    return SKIP;
+
   int count = id_info_size / sizeof(*id_info);
   for (int i = 0; i < count; ++i) {
     if (id == id_info[i].id_)
-      return &id_info[i];
+      return id_info[i].type_;
   }
 
-  return NULL;
+  return UNKNOWN;
 }
 
 // Finds ListElementInfo for a specific ID.
 static const ListElementInfo* FindListInfo(int id) {
-  for (int i = 0; i < kListElementInfoCount; ++i) {
+  for (size_t i = 0; i < arraysize(kListElementInfo); ++i) {
     if (id == kListElementInfo[i].id_)
       return &kListElementInfo[i];
   }
 
   return NULL;
 }
 
 static int ParseSimpleBlock(const uint8* buf, int size,
                             WebMParserClient* client) {
   if (size < 4)
     return -1;
 
   // Return an error if the trackNum > 127. We just aren't
   // going to support large track numbers right now.
   if ((buf[0] & 0x80) != 0x80) {
-    VLOG(1) << "TrackNumber over 127 not supported";
+    DVLOG(1) << "TrackNumber over 127 not supported";
     return -1;
   }
 
   int track_num = buf[0] & 0x7f;
   int timecode = buf[1] << 8 | buf[2];
   int flags = buf[3] & 0xff;
   int lacing = (flags >> 1) & 0x3;
 
   if (lacing != 0) {
-    VLOG(1) << "Lacing " << lacing << " not supported yet.";
+    DVLOG(1) << "Lacing " << lacing << " not supported yet.";
     return -1;
   }
 
   // Sign extend negative timecode offsets.
   if (timecode & 0x8000)
     timecode |= (-1 << 16);
 
   const uint8* frame_data = buf + 4;
   int frame_size = size - (frame_data - buf);
   if (!client->OnSimpleBlock(track_num, timecode, flags,
                              frame_data, frame_size)) {
     return -1;
   }
 
   return size;
 }
 
-static int ParseElements(const ElementIdInfo* id_info,
-                         int id_info_size,
-                         const uint8* buf, int size, int level,
-                         WebMParserClient* client);
-
-static int ParseElementList(const uint8* buf, int size,
-                            int id, int level,
-                            WebMParserClient* client) {
-  const ListElementInfo* list_info = FindListInfo(id);
-
-  if (!list_info) {
-    VLOG(1) << "Failed to find list info for ID " << std::hex << id;
-    return -1;
-  }
-
-  if (!client->OnListStart(id))
-    return -1;
-
-  int result = ParseElements(list_info->id_info_,
-                             list_info->id_info_size_,
-                             buf, size,
-                             level + 1,
-                             client);
-
-  if (result <= 0)
-    return result;
-
-  if (!client->OnListEnd(id))
-    return -1;
-
-  DCHECK_EQ(result, size);
-  return result;
-}
 
 static int ParseUInt(const uint8* buf, int size, int id,
                      WebMParserClient* client) {
   if ((size <= 0) || (size > 8))
     return -1;
 
   // Read in the big-endian integer.
   int64 value = 0;
   for (int i = 0; i < size; ++i)
     value = (value << 8) | buf[i];
@@ skipping 36 matching lines @@
   } else {
     return -1;
   }
 
   if (!client->OnFloat(id, value))
     return -1;
 
   return size;
 }
 
-static int ParseElements(const ElementIdInfo* id_info,
-                         int id_info_size,
-                         const uint8* buf, int size, int level,
-                         WebMParserClient* client) {
-  DCHECK_GE(id_info_size, 0);
-  DCHECK_GE(size, 0);
-  DCHECK_GE(level, 0);
-
-  const uint8* cur = buf;
-  int cur_size = size;
-  int used = 0;
-
-  if (level > kMaxLevelDepth)
-    return -1;
-
-  while (cur_size > 0) {
-    int id = 0;
-    int64 element_size = 0;
-    int result = WebMParseElementHeader(cur, cur_size, &id, &element_size);
-
-    if (result <= 0)
-      return result;
-
-    cur += result;
-    cur_size -= result;
-    used += result;
-
-    // Check to see if the element is larger than the remaining data.
-    if (element_size > cur_size)
-      return 0;
-
-    const ElementIdInfo* info = FindIdInfo(id, id_info, id_info_size);
-
-    if (info == NULL) {
-      VLOG(1) << "No info for ID " << std::hex << id;
-
-      // TODO(acolwell): Change this to return -1 after the API has solidified.
-      // We don't want to allow elements we don't recognize.
-      cur += element_size;
-      cur_size -= element_size;
-      used += element_size;
-      continue;
-    }
-
-    if (info->level_ != level) {
-      VLOG(1) << "ID " << std::hex << id << std::dec << " at level "
-              << level << " instead of " << info->level_;
+static int ParseNonListElement(ElementType type, int id, int64 element_size,
+                               const uint8* buf, int size,
+                               WebMParserClient* client) {
+  DCHECK_GE(size, element_size);
+
+  int result = -1;
+  switch(type) {
+    case SBLOCK:
+      result = ParseSimpleBlock(buf, element_size, client);
+      break;
+    case LIST:
+      NOTIMPLEMENTED();
+      result = -1;
+      break;
+    case UINT:
+      result = ParseUInt(buf, element_size, id, client);
+      break;
+    case FLOAT:
+      result = ParseFloat(buf, element_size, id, client);
+      break;
+    case BINARY:
+      if (client->OnBinary(id, buf, element_size)) {
+        result = element_size;
+      } else {
+        result = -1;
+      }
+      break;
+    case STRING:
+      if (client->OnString(id,
+                           std::string(reinterpret_cast<const char*>(buf),
+                                       element_size))) {
+        result = element_size;
+      } else {
+        result = -1;
+      }
+      break;
+    case SKIP:
+      result = element_size;
+      break;
+    default:
+      DVLOG(1) << "Unhandled ID type " << type;
       return -1;
-    }
-
-    switch(info->type_) {
-      case SBLOCK:
-        if (ParseSimpleBlock(cur, element_size, client) <= 0)
-          return -1;
-        break;
-      case LIST:
-        if (ParseElementList(cur, element_size, id, level, client) < 0)
-          return -1;
-        break;
-      case UINT:
-        if (ParseUInt(cur, element_size, id, client) <= 0)
-          return -1;
-        break;
-      case FLOAT:
-        if (ParseFloat(cur, element_size, id, client) <= 0)
-          return -1;
-        break;
-      case BINARY:
-        if (!client->OnBinary(id, cur, element_size))
-          return -1;
-        break;
-      case STRING:
-        if (!client->OnString(id,
-                              std::string(reinterpret_cast<const char*>(cur),
-                                          element_size)))
-          return -1;
-        break;
-      case SKIP:
-        // Do nothing.
-        break;
-      default:
-        VLOG(1) << "Unhandled id type " << info->type_;
-        return -1;
-    };
-
-    cur += element_size;
-    cur_size -= element_size;
-    used += element_size;
-  }
-
-  return used;
-}
-
-// Parses a single list element that matches |id|. This method fails if the
-// buffer points to an element that does not match |id|.
-int WebMParseListElement(const uint8* buf, int size, int id,
-                         int level, WebMParserClient* client) {
-  if (size < 0)
+  };
+
+  DCHECK_LE(result, size);
+  return result;
+}
+
+WebMParserClient::WebMParserClient() {}
+WebMParserClient::~WebMParserClient() {}
+
+WebMListParser::WebMListParser(int id)
+    : state_(NEED_LIST_HEADER),
+      root_id_(id) {
+  const ListElementInfo* list_info = FindListInfo(id);
+
+  DCHECK(list_info);
+
+  root_level_ = list_info->level_;
+}
+
+WebMListParser::~WebMListParser() {}
+
+void WebMListParser::Reset() {
+  ChangeState(NEED_LIST_HEADER);
+  list_state_stack_.clear();
+}
+
+int WebMListParser::Parse(const uint8* buf, int size,
+                          WebMParserClient* client) {
+  DCHECK(buf);
+  DCHECK(client);
+
+  if (size < 0 || state_ == PARSE_ERROR || state_ == DONE_PARSING_LIST)
     return -1;
 
   if (size == 0)
     return 0;
 
   const uint8* cur = buf;
   int cur_size = size;
   int bytes_parsed = 0;
-  int element_id = 0;
-  int64 element_size = 0;
-  int result = WebMParseElementHeader(cur, cur_size, &element_id,
-                                      &element_size);
-
-  if (result <= 0)
-    return result;
-
-  cur += result;
-  cur_size -= result;
-  bytes_parsed += result;
-
-  if (element_id != id)
-    return -1;
-
-  if (element_size > cur_size)
-    return 0;
-
-  if (element_size > 0) {
-    result = ParseElementList(cur, element_size, element_id, level, client);
-
-    if (result <= 0)
+
+  while (cur_size > 0 && state_ != PARSE_ERROR && state_ != DONE_PARSING_LIST) {
+    int element_id = 0;
+    int64 element_size = 0;
+    int result = WebMParseElementHeader(cur, cur_size, &element_id,
+                                        &element_size);
+
+    if (result < 0)
       return result;
 
+    if (result == 0)
+      return bytes_parsed;
+
+    switch(state_) {
+      case NEED_LIST_HEADER: {
+        if (element_id != root_id_) {
+          ChangeState(PARSE_ERROR);
+          return -1;
+        }
+
+        // TODO(acolwell): Add support for lists of unknown size.
+        if (element_size == kWebMUnknownSize) {
+          ChangeState(PARSE_ERROR);
+          return -1;
+        }
+
+        ChangeState(INSIDE_LIST);
+        if (!OnListStart(root_id_, element_size, client))
+          return -1;
+
+        break;
+      }
+
+      case INSIDE_LIST: {
+        int header_size = result;
+        const uint8* element_data = cur + header_size;
+        int element_data_size = cur_size - header_size;
+
+        if (element_size < element_data_size)
+          element_data_size = element_size;
+
+        result = ParseListElement(header_size, element_id, element_size,
+                                  element_data, element_data_size, client);
+
+        DCHECK_LE(result, header_size + element_data_size);
+        if (result < 0) {
+          ChangeState(PARSE_ERROR);
+          return -1;
+        }
+
+        if (result == 0)
+          return bytes_parsed;
+
+        break;
+      }
+      case DONE_PARSING_LIST:
+      case PARSE_ERROR:
+        // Shouldn't be able to get here.
+        NOTIMPLEMENTED();
+        break;
+    }
+
     cur += result;
     cur_size -= result;
     bytes_parsed += result;
   }
 
-  return bytes_parsed;
+  return (state_ == PARSE_ERROR) ? -1 : bytes_parsed;
+}
+
+bool WebMListParser::IsParsingComplete() const {
+  return state_ == DONE_PARSING_LIST;
+}
+
+void WebMListParser::ChangeState(State new_state) {
+  state_ = new_state;
+}
+
+int WebMListParser::ParseListElement(int header_size,
+                                     int id, int64 element_size,
+                                     const uint8* data, int size,
+                                     WebMParserClient* client) {
+  DCHECK_GT(list_state_stack_.size(), 0u);
+
+  ListState& list_state = list_state_stack_.back();
+  DCHECK(list_state.element_info_);
+
+  const ListElementInfo* element_info = list_state.element_info_;
+  const ElementType id_type =
+      FindIdType(id, element_info->id_info_, element_info->id_info_size_);
+
+  // Unexpected ID.
+  if (id_type == UNKNOWN) {
+    DVLOG(1) << "No ElementType info for ID 0x" << std::hex << id;
+    return -1;
+  }
+
+  // Make sure the whole element can fit inside the current list.
+  int64 total_element_size = header_size + element_size;
+  if (list_state.size_ != kWebMUnknownSize &&
+      list_state.size_ < list_state.bytes_parsed_ + total_element_size) {
+    return -1;
+  }
+
+  if (id_type == LIST) {
+    list_state.bytes_parsed_ += header_size;
+
+    if (!OnListStart(id, element_size, client))
+      return -1;
+    return header_size;
+  }
+
+  // Make sure we have the entire element before trying to parse a non-list
+  // element.
+  if (size < element_size)
+    return 0;
+
+  int bytes_parsed = ParseNonListElement(id_type, id, element_size,
+                                         data, size, client);
+  DCHECK_LE(bytes_parsed, size);
+
+  // Return if an error occurred or we need more data.
+  // Note: bytes_parsed is 0 for a successful parse of a size 0 element. We
+  // need to check the element_size to disambiguate the "need more data" case
+  // from a successful parse.
+  if (bytes_parsed < 0 || (bytes_parsed == 0 && element_size != 0))
+    return bytes_parsed;
+
+  int result = header_size + bytes_parsed;
+  list_state.bytes_parsed_ += result;
+
+  // See if we have reached the end of the current list.
+  if (list_state.bytes_parsed_ == list_state.size_) {
+    if (!OnListEnd(client))
+      return -1;
+  }
+
+  return result;
+}
+
+bool WebMListParser::OnListStart(int id, int64 size, WebMParserClient* client) {
+  ListState list_state = { id, size, 0, FindListInfo(id)};
+
+  if (!list_state.element_info_)
+    return false;
+
+  int current_level = root_level_ + list_state_stack_.size() - 1;
+  if (current_level + 1 != list_state.element_info_->level_)
+    return false;
+
+  if (!list_state_stack_.empty()) {
+
+    // Make sure the new list doesn't go past the end of the current list.
+    ListState current_list = list_state_stack_.back();
+    if (current_list.size_ != kWebMUnknownSize &&
+        current_list.size_ < current_list.bytes_parsed_ + size)
+      return false;
+  }
+
+  if (!client->OnListStart(id))
+    return false;
+
+  list_state_stack_.push_back(list_state);
+
+  if (size == 0) {
+    return OnListEnd(client);
+  }
+
+  return true;
+}
+
+bool WebMListParser::OnListEnd(WebMParserClient* client) {
+  int lists_ended = 0;
+  for (; !list_state_stack_.empty(); ++lists_ended) {
+    const ListState& list_state = list_state_stack_.back();
+
+    if (list_state.bytes_parsed_ != list_state.size_)
+      break;
+
+    if (!client->OnListEnd(list_state.id_))
+      return false;
+
+    int64 bytes_parsed = list_state.bytes_parsed_;
+    list_state_stack_.pop_back();
+
+    if (!list_state_stack_.empty()) {
+      // Update the bytes_parsed_ for the parent element.
+      list_state_stack_.back().bytes_parsed_ += bytes_parsed;
+    }
+  }
+
+  DCHECK_GE(lists_ended, 1);
+
+  if (list_state_stack_.empty())
+    ChangeState(DONE_PARSING_LIST);
+
+  return true;
 }
 
 }  // namespace media