michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* vim:set ts=2 sw=2 sts=2 et cindent: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "nsAlgorithm.h"
michael@0: #include "WebMBufferedParser.h"
michael@0: #include "mozilla/dom/TimeRanges.h"
michael@0: #include "nsThreadUtils.h"
michael@0: #include <algorithm>
michael@0: 
michael@0: namespace mozilla {
michael@0: 
michael@0: static uint32_t
michael@0: VIntLength(unsigned char aFirstByte, uint32_t* aMask)
michael@0: {
michael@0:   uint32_t count = 1;
michael@0:   uint32_t mask = 1 << 7;
michael@0:   while (count < 8) {
michael@0:     if ((aFirstByte & mask) != 0) {
michael@0:       break;
michael@0:     }
michael@0:     mask >>= 1;
michael@0:     count += 1;
michael@0:   }
michael@0:   if (aMask) {
michael@0:     *aMask = mask;
michael@0:   }
michael@0:   NS_ASSERTION(count >= 1 && count <= 8, "Insane VInt length.");
michael@0:   return count;
michael@0: }
michael@0: 
michael@0: void WebMBufferedParser::Append(const unsigned char* aBuffer, uint32_t aLength,
michael@0:                                   nsTArray<WebMTimeDataOffset>& aMapping,
michael@0:                                   ReentrantMonitor& aReentrantMonitor)
michael@0: {
michael@0:   static const unsigned char CLUSTER_ID[] = { 0x1f, 0x43, 0xb6, 0x75 };
michael@0:   static const unsigned char TIMECODE_ID = 0xe7;
michael@0:   static const unsigned char BLOCKGROUP_ID = 0xa0;
michael@0:   static const unsigned char BLOCK_ID = 0xa1;
michael@0:   static const unsigned char SIMPLEBLOCK_ID = 0xa3;
michael@0: 
michael@0:   const unsigned char* p = aBuffer;
michael@0: 
michael@0:   // Parse each byte in aBuffer one-by-one, producing timecodes and updating
michael@0:   // aMapping as we go.  Parser pauses at end of stream (which may be at any
michael@0:   // point within the parse) and resumes parsing the next time Append is
michael@0:   // called with new data.
michael@0:   while (p < aBuffer + aLength) {
michael@0:     switch (mState) {
michael@0:     case CLUSTER_SYNC:
michael@0:       if (*p++ == CLUSTER_ID[mClusterIDPos]) {
michael@0:         mClusterIDPos += 1;
michael@0:       } else {
michael@0:         mClusterIDPos = 0;
michael@0:       }
michael@0:       // Cluster ID found, it's likely this is a valid sync point.  If this
michael@0:       // is a spurious match, the later parse steps will encounter an error
michael@0:       // and return to CLUSTER_SYNC.
michael@0:       if (mClusterIDPos == sizeof(CLUSTER_ID)) {
michael@0:         mClusterIDPos = 0;
michael@0:         mState = READ_VINT;
michael@0:         mNextState = TIMECODE_SYNC;
michael@0:       }
michael@0:       break;
michael@0:     case READ_VINT: {
michael@0:       unsigned char c = *p++;
michael@0:       uint32_t mask;
michael@0:       mVIntLength = VIntLength(c, &mask);
michael@0:       mVIntLeft = mVIntLength - 1;
michael@0:       mVInt = c & ~mask;
michael@0:       mState = READ_VINT_REST;
michael@0:       break;
michael@0:     }
michael@0:     case READ_VINT_REST:
michael@0:       if (mVIntLeft) {
michael@0:         mVInt <<= 8;
michael@0:         mVInt |= *p++;
michael@0:         mVIntLeft -= 1;
michael@0:       } else {
michael@0:         mState = mNextState;
michael@0:       }
michael@0:       break;
michael@0:     case TIMECODE_SYNC:
michael@0:       if (*p++ != TIMECODE_ID) {
michael@0:         p -= 1;
michael@0:         mState = CLUSTER_SYNC;
michael@0:         break;
michael@0:       }
michael@0:       mClusterTimecode = 0;
michael@0:       mState = READ_VINT;
michael@0:       mNextState = READ_CLUSTER_TIMECODE;
michael@0:       break;
michael@0:     case READ_CLUSTER_TIMECODE:
michael@0:       if (mVInt) {
michael@0:         mClusterTimecode <<= 8;
michael@0:         mClusterTimecode |= *p++;
michael@0:         mVInt -= 1;
michael@0:       } else {
michael@0:         mState = ANY_BLOCK_SYNC;
michael@0:       }
michael@0:       break;
michael@0:     case ANY_BLOCK_SYNC: {
michael@0:       unsigned char c = *p++;
michael@0:       if (c == BLOCKGROUP_ID) {
michael@0:         mState = READ_VINT;
michael@0:         mNextState = ANY_BLOCK_SYNC;
michael@0:       } else if (c == SIMPLEBLOCK_ID || c == BLOCK_ID) {
michael@0:         mBlockOffset = mCurrentOffset + (p - aBuffer) - 1;
michael@0:         mState = READ_VINT;
michael@0:         mNextState = READ_BLOCK;
michael@0:       } else {
michael@0:         uint32_t length = VIntLength(c, nullptr);
michael@0:         if (length == 4) {
michael@0:           p -= 1;
michael@0:           mState = CLUSTER_SYNC;
michael@0:         } else {
michael@0:           mState = READ_VINT;
michael@0:           mNextState = SKIP_ELEMENT;
michael@0:         }
michael@0:       }
michael@0:       break;
michael@0:     }
michael@0:     case READ_BLOCK:
michael@0:       mBlockSize = mVInt;
michael@0:       mBlockTimecode = 0;
michael@0:       mBlockTimecodeLength = 2;
michael@0:       mState = READ_VINT;
michael@0:       mNextState = READ_BLOCK_TIMECODE;
michael@0:       break;
michael@0:     case READ_BLOCK_TIMECODE:
michael@0:       if (mBlockTimecodeLength) {
michael@0:         mBlockTimecode <<= 8;
michael@0:         mBlockTimecode |= *p++;
michael@0:         mBlockTimecodeLength -= 1;
michael@0:       } else {
michael@0:         // It's possible we've parsed this data before, so avoid inserting
michael@0:         // duplicate WebMTimeDataOffset entries.
michael@0:         {
michael@0:           ReentrantMonitorAutoEnter mon(aReentrantMonitor);
michael@0:           uint32_t idx = aMapping.IndexOfFirstElementGt(mBlockOffset);
michael@0:           if (idx == 0 || !(aMapping[idx-1] == mBlockOffset)) {
michael@0:             WebMTimeDataOffset entry(mBlockOffset, mClusterTimecode + mBlockTimecode);
michael@0:             aMapping.InsertElementAt(idx, entry);
michael@0:           }
michael@0:         }
michael@0: 
michael@0:         // Skip rest of block header and the block's payload.
michael@0:         mBlockSize -= mVIntLength;
michael@0:         mBlockSize -= 2;
michael@0:         mSkipBytes = uint32_t(mBlockSize);
michael@0:         mState = SKIP_DATA;
michael@0:         mNextState = ANY_BLOCK_SYNC;
michael@0:       }
michael@0:       break;
michael@0:     case SKIP_DATA:
michael@0:       if (mSkipBytes) {
michael@0:         uint32_t left = aLength - (p - aBuffer);
michael@0:         left = std::min(left, mSkipBytes);
michael@0:         p += left;
michael@0:         mSkipBytes -= left;
michael@0:       } else {
michael@0:         mState = mNextState;
michael@0:       }
michael@0:       break;
michael@0:     case SKIP_ELEMENT:
michael@0:       mSkipBytes = uint32_t(mVInt);
michael@0:       mState = SKIP_DATA;
michael@0:       mNextState = ANY_BLOCK_SYNC;
michael@0:       break;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   NS_ASSERTION(p == aBuffer + aLength, "Must have parsed to end of data.");
michael@0:   mCurrentOffset += aLength;
michael@0: }
michael@0: 
michael@0: bool WebMBufferedState::CalculateBufferedForRange(int64_t aStartOffset, int64_t aEndOffset,
michael@0:                                                     uint64_t* aStartTime, uint64_t* aEndTime)
michael@0: {
michael@0:   ReentrantMonitorAutoEnter mon(mReentrantMonitor);
michael@0: 
michael@0:   // Find the first WebMTimeDataOffset at or after aStartOffset.
michael@0:   uint32_t start = mTimeMapping.IndexOfFirstElementGt(aStartOffset-1);
michael@0:   if (start == mTimeMapping.Length()) {
michael@0:     return false;
michael@0:   }
michael@0: 
michael@0:   // Find the first WebMTimeDataOffset at or before aEndOffset.
michael@0:   uint32_t end = mTimeMapping.IndexOfFirstElementGt(aEndOffset-1);
michael@0:   if (end > 0) {
michael@0:     end -= 1;
michael@0:   }
michael@0: 
michael@0:   // Range is empty.
michael@0:   if (end <= start) {
michael@0:     return false;
michael@0:   }
michael@0: 
michael@0:   NS_ASSERTION(mTimeMapping[start].mOffset >= aStartOffset &&
michael@0:                mTimeMapping[end].mOffset <= aEndOffset,
michael@0:                "Computed time range must lie within data range.");
michael@0:   if (start > 0) {
michael@0:     NS_ASSERTION(mTimeMapping[start - 1].mOffset <= aStartOffset,
michael@0:                  "Must have found least WebMTimeDataOffset for start");
michael@0:   }
michael@0:   if (end < mTimeMapping.Length() - 1) {
michael@0:     NS_ASSERTION(mTimeMapping[end + 1].mOffset >= aEndOffset,
michael@0:                  "Must have found greatest WebMTimeDataOffset for end");
michael@0:   }
michael@0: 
michael@0:   // The timestamp of the first media sample, in ns. We must subtract this
michael@0:   // from the ranges' start and end timestamps, so that those timestamps are
michael@0:   // normalized in the range [0,duration].
michael@0: 
michael@0:   *aStartTime = mTimeMapping[start].mTimecode;
michael@0:   *aEndTime = mTimeMapping[end].mTimecode;
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: bool WebMBufferedState::GetOffsetForTime(uint64_t aTime, int64_t* aOffset)
michael@0: {
michael@0:   ReentrantMonitorAutoEnter mon(mReentrantMonitor);
michael@0:   WebMTimeDataOffset result(0,0);
michael@0: 
michael@0:   for (uint32_t i = 0; i < mTimeMapping.Length(); ++i) {
michael@0:     WebMTimeDataOffset o = mTimeMapping[i];
michael@0:     if (o.mTimecode < aTime && o.mTimecode > result.mTimecode) {
michael@0:       result = o;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   *aOffset = result.mOffset;
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: void WebMBufferedState::NotifyDataArrived(const char* aBuffer, uint32_t aLength, int64_t aOffset)
michael@0: {
michael@0:   NS_ASSERTION(NS_IsMainThread(), "Should be on main thread.");
michael@0:   uint32_t idx = mRangeParsers.IndexOfFirstElementGt(aOffset - 1);
michael@0:   if (idx == 0 || !(mRangeParsers[idx-1] == aOffset)) {
michael@0:     // If the incoming data overlaps an already parsed range, adjust the
michael@0:     // buffer so that we only reparse the new data.  It's also possible to
michael@0:     // have an overlap where the end of the incoming data is within an
michael@0:     // already parsed range, but we don't bother handling that other than by
michael@0:     // avoiding storing duplicate timecodes when the parser runs.
michael@0:     if (idx != mRangeParsers.Length() && mRangeParsers[idx].mStartOffset <= aOffset) {
michael@0:       // Complete overlap, skip parsing.
michael@0:       if (aOffset + aLength <= mRangeParsers[idx].mCurrentOffset) {
michael@0:         return;
michael@0:       }
michael@0: 
michael@0:       // Partial overlap, adjust the buffer to parse only the new data.
michael@0:       int64_t adjust = mRangeParsers[idx].mCurrentOffset - aOffset;
michael@0:       NS_ASSERTION(adjust >= 0, "Overlap detection bug.");
michael@0:       aBuffer += adjust;
michael@0:       aLength -= uint32_t(adjust);
michael@0:     } else {
michael@0:       mRangeParsers.InsertElementAt(idx, WebMBufferedParser(aOffset));
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   mRangeParsers[idx].Append(reinterpret_cast<const unsigned char*>(aBuffer),
michael@0:                             aLength,
michael@0:                             mTimeMapping,
michael@0:                             mReentrantMonitor);
michael@0: 
michael@0:   // Merge parsers with overlapping regions and clean up the remnants.
michael@0:   uint32_t i = 0;
michael@0:   while (i + 1 < mRangeParsers.Length()) {
michael@0:     if (mRangeParsers[i].mCurrentOffset >= mRangeParsers[i + 1].mStartOffset) {
michael@0:       mRangeParsers[i + 1].mStartOffset = mRangeParsers[i].mStartOffset;
michael@0:       mRangeParsers.RemoveElementAt(i);
michael@0:     } else {
michael@0:       i += 1;
michael@0:     }
michael@0:   }
michael@0: }
michael@0: 
michael@0: } // namespace mozilla
michael@0: