libwebm/mkvparser.cpp

// Copyright (c) 2012 The WebM project authors. All Rights Reserved.
//
// Use of this source code is governed by a BSD-style license
// that can be found in the LICENSE file in the root of the source
// tree. An additional intellectual property rights grant can be found
// in the file PATENTS.  All contributing project authors may
// be found in the AUTHORS file in the root of the source tree.

#include "mkvparser.hpp"

#include <cassert>
#include <climits>
#include <cmath>
#include <cstring>
#include <new>

#ifdef _MSC_VER
// Disable MSVC warnings that suggest making code non-portable.
#pragma warning(disable : 4996)
#endif

namespace mkvparser {

IMkvReader::~IMkvReader() {}

template<typename Type> Type* SafeArrayAlloc(unsigned long long num_elements,
                                             unsigned long long element_size) {
  if (num_elements == 0 || element_size == 0)
    return NULL;

  const size_t kMaxAllocSize = 0x80000000;  // 2GiB
  const unsigned long long num_bytes = num_elements * element_size;
  if (element_size > (kMaxAllocSize / num_elements))
    return NULL;

  return new (std::nothrow) Type[num_bytes];
}

void GetVersion(int& major, int& minor, int& build, int& revision) {
  major = 1;
  minor = 0;
  build = 0;
  revision = 30;
}

long long ReadUInt(IMkvReader* pReader, long long pos, long& len) {
  if (!pReader || pos < 0)
    return E_FILE_FORMAT_INVALID;

  len = 1;
  unsigned char b;
  int status = pReader->Read(pos, 1, &b);

  if (status < 0)  // error or underflow
    return status;

  if (status > 0)  // interpreted as "underflow"
    return E_BUFFER_NOT_FULL;

  if (b == 0)  // we can't handle u-int values larger than 8 bytes
    return E_FILE_FORMAT_INVALID;

  unsigned char m = 0x80;

  while (!(b & m)) {
    m >>= 1;
    ++len;
  }

  long long result = b & (~m);
  ++pos;

  for (int i = 1; i < len; ++i) {
    status = pReader->Read(pos, 1, &b);

    if (status < 0) {
      len = 1;
      return status;
    }

    if (status > 0) {
      len = 1;
      return E_BUFFER_NOT_FULL;
    }

    result <<= 8;
    result |= b;

    ++pos;
  }

  return result;
}

long long ReadID(IMkvReader* pReader, long long pos, long& len) {
  const long long id = ReadUInt(pReader, pos, len);
  if (id < 0 || len < 1 || len > 4) {
    // An ID must be at least 1 byte long, and cannot exceed 4.
    // See EBMLMaxIDLength: http://www.matroska.org/technical/specs/index.html
    return E_FILE_FORMAT_INVALID;
  }
  return id;
}

long long GetUIntLength(IMkvReader* pReader, long long pos, long& len) {
  if (!pReader || pos < 0)
    return E_FILE_FORMAT_INVALID;

  long long total, available;

  int status = pReader->Length(&total, &available);
  if (status < 0 || (total >= 0 && available > total))
    return E_FILE_FORMAT_INVALID;

  len = 1;

  if (pos >= available)
    return pos;  // too few bytes available

  unsigned char b;

  status = pReader->Read(pos, 1, &b);

  if (status != 0)
    return status;

  if (b == 0)  // we can't handle u-int values larger than 8 bytes
    return E_FILE_FORMAT_INVALID;

  unsigned char m = 0x80;

  while (!(b & m)) {
    m >>= 1;
    ++len;
  }

  return 0;  // success
}

// TODO(vigneshv): This function assumes that unsigned values never have their
// high bit set.
long long UnserializeUInt(IMkvReader* pReader, long long pos, long long size) {
  if (!pReader || pos < 0 || (size <= 0) || (size > 8))
    return E_FILE_FORMAT_INVALID;

  long long result = 0;

  for (long long i = 0; i < size; ++i) {
    unsigned char b;

    const long status = pReader->Read(pos, 1, &b);

    if (status < 0)
      return status;

    result <<= 8;
    result |= b;

    ++pos;
  }

  return result;
}

long UnserializeFloat(IMkvReader* pReader, long long pos, long long size_,
                      double& result) {
  if (!pReader || pos < 0 || ((size_ != 4) && (size_ != 8)))
    return E_FILE_FORMAT_INVALID;

  const long size = static_cast<long>(size_);

  unsigned char buf[8];

  const int status = pReader->Read(pos, size, buf);

  if (status < 0)  // error
    return status;

  if (size == 4) {
    union {
      float f;
      unsigned long ff;
    };

    ff = 0;

    for (int i = 0;;) {
      ff |= buf[i];

      if (++i >= 4)
        break;

      ff <<= 8;
    }

    result = f;
  } else {
    union {
      double d;
      unsigned long long dd;
    };

    dd = 0;

    for (int i = 0;;) {
      dd |= buf[i];

      if (++i >= 8)
        break;

      dd <<= 8;
    }

    result = d;
  }

  if (std::isinf(result) || std::isnan(result))
    return E_FILE_FORMAT_INVALID;

  return 0;
}

long UnserializeInt(IMkvReader* pReader, long long pos, long long size,
                    long long& result_ref) {
  if (!pReader || pos < 0 || size < 1 || size > 8)
    return E_FILE_FORMAT_INVALID;

  signed char first_byte = 0;
  const long status = pReader->Read(pos, 1, (unsigned char*)&first_byte);

  if (status < 0)
    return status;

  unsigned long long result = first_byte;
  ++pos;

  for (long i = 1; i < size; ++i) {
    unsigned char b;

    const long status = pReader->Read(pos, 1, &b);

    if (status < 0)
      return status;

    result <<= 8;
    result |= b;

    ++pos;
  }

  result_ref = static_cast<long long>(result);
  return 0;
}

long UnserializeString(IMkvReader* pReader, long long pos, long long size,
                       char*& str) {
  delete[] str;
  str = NULL;

  if (size >= LONG_MAX || size < 0)
    return E_FILE_FORMAT_INVALID;

  // +1 for '\0' terminator
  const long required_size = static_cast<long>(size) + 1;

  str = SafeArrayAlloc<char>(1, required_size);
  if (str == NULL)
    return E_FILE_FORMAT_INVALID;

  unsigned char* const buf = reinterpret_cast<unsigned char*>(str);

  const long status = pReader->Read(pos, size, buf);

  if (status) {
    delete[] str;
    str = NULL;

    return status;
  }

  str[required_size - 1] = '\0';
  return 0;
}

long ParseElementHeader(IMkvReader* pReader, long long& pos,
                        long long stop, long long& id,
                        long long& size) {
  if (stop >= 0 && pos >= stop)
    return E_FILE_FORMAT_INVALID;

  long len;

  id = ReadID(pReader, pos, len);

  if (id < 0)
    return E_FILE_FORMAT_INVALID;

  pos += len;  // consume id

  if (stop >= 0 && pos >= stop)
    return E_FILE_FORMAT_INVALID;

  size = ReadUInt(pReader, pos, len);

  if (size < 0 || len < 1 || len > 8) {
    // Invalid: Negative payload size, negative or 0 length integer, or integer
    // larger than 64 bits (libwebm cannot handle them).
    return E_FILE_FORMAT_INVALID;
  }

  // Avoid rolling over pos when very close to LONG_LONG_MAX.
  const unsigned long long rollover_check =
      static_cast<unsigned long long>(pos) + len;
  if (rollover_check > LONG_LONG_MAX)
    return E_FILE_FORMAT_INVALID;

  pos += len;  // consume length of size

  // pos now designates payload

  if (stop >= 0 && pos > stop)
    return E_FILE_FORMAT_INVALID;

  return 0;  // success
}

bool Match(IMkvReader* pReader, long long& pos, unsigned long expected_id,
           long long& val) {
  if (!pReader || pos < 0)
    return false;

  long long total = 0;
  long long available = 0;

  const long status = pReader->Length(&total, &available);
  if (status < 0 || (total >= 0 && available > total))
    return false;

  long len = 0;

  const long long id = ReadID(pReader, pos, len);
  if (id < 0 || (available - pos) > len)
    return false;

  if (static_cast<unsigned long>(id) != expected_id)
    return false;

  pos += len;  // consume id

  const long long size = ReadUInt(pReader, pos, len);
  if (size < 0 || size > 8 || len < 1 || len > 8 || (available - pos) > len)
    return false;

  pos += len;  // consume length of size of payload

  val = UnserializeUInt(pReader, pos, size);
  if (val < 0)
    return false;

  pos += size;  // consume size of payload

  return true;
}

bool Match(IMkvReader* pReader, long long& pos, unsigned long expected_id,
           unsigned char*& buf, size_t& buflen) {
  if (!pReader || pos < 0)
    return false;

  long long total = 0;
  long long available = 0;

  long status = pReader->Length(&total, &available);
  if (status < 0 || (total >= 0 && available > total))
    return false;

  long len = 0;
  const long long id = ReadID(pReader, pos, len);
  if (id < 0 || (available - pos) > len)
    return false;

  if (static_cast<unsigned long>(id) != expected_id)
    return false;

  pos += len;  // consume id

  const long long size = ReadUInt(pReader, pos, len);
  if (size < 0 || len <= 0 || len > 8 || (available - pos) > len)
    return false;

  unsigned long long rollover_check =
      static_cast<unsigned long long>(pos) + len;
  if (rollover_check > LONG_LONG_MAX)
    return false;

  pos += len;  // consume length of size of payload

  rollover_check = static_cast<unsigned long long>(pos) + size;
  if (rollover_check > LONG_LONG_MAX)
    return false;

  if ((pos + size) > available)
    return false;

  if (size >= LONG_MAX)
    return false;

  const long buflen_ = static_cast<long>(size);

  buf = SafeArrayAlloc<unsigned char>(1, buflen_);
  if (!buf)
    return false;

  status = pReader->Read(pos, buflen_, buf);
  if (status != 0)
    return false;

  buflen = buflen_;

  pos += size;  // consume size of payload
  return true;
}

EBMLHeader::EBMLHeader() : m_docType(NULL) { Init(); }

EBMLHeader::~EBMLHeader() { delete[] m_docType; }

void EBMLHeader::Init() {
  m_version = 1;
  m_readVersion = 1;
  m_maxIdLength = 4;
  m_maxSizeLength = 8;

  if (m_docType) {
    delete[] m_docType;
    m_docType = NULL;
  }

  m_docTypeVersion = 1;
  m_docTypeReadVersion = 1;
}

long long EBMLHeader::Parse(IMkvReader* pReader, long long& pos) {
  if (!pReader)
    return E_FILE_FORMAT_INVALID;

  long long total, available;

  long status = pReader->Length(&total, &available);

  if (status < 0)  // error
    return status;

  pos = 0;
  long long end = (available >= 1024) ? 1024 : available;

  for (;;) {
    unsigned char b = 0;

    while (pos < end) {
      status = pReader->Read(pos, 1, &b);

      if (status < 0)  // error
        return status;

      if (b == 0x1A)
        break;

      ++pos;
    }

    if (b != 0x1A) {
      if (pos >= 1024)
        return E_FILE_FORMAT_INVALID;  // don't bother looking anymore

      if ((total >= 0) && ((total - available) < 5))
        return E_FILE_FORMAT_INVALID;

      return available + 5;  // 5 = 4-byte ID + 1st byte of size
    }

    if ((total >= 0) && ((total - pos) < 5))
      return E_FILE_FORMAT_INVALID;

    if ((available - pos) < 5)
      return pos + 5;  // try again later

    long len;

    const long long result = ReadUInt(pReader, pos, len);

    if (result < 0)  // error
      return result;

    if (result == 0x0A45DFA3) {  // EBML Header ID
      pos += len;  // consume ID
      break;
    }

    ++pos;  // throw away just the 0x1A byte, and try again
  }

  // pos designates start of size field

  // get length of size field

  long len;
  long long result = GetUIntLength(pReader, pos, len);

  if (result < 0)  // error
    return result;

  if (result > 0)  // need more data
    return result;

  if (len < 1 || len > 8)
    return E_FILE_FORMAT_INVALID;

  if ((total >= 0) && ((total - pos) < len))
    return E_FILE_FORMAT_INVALID;

  if ((available - pos) < len)
    return pos + len;  // try again later

  // get the EBML header size

  result = ReadUInt(pReader, pos, len);

  if (result < 0)  // error
    return result;

  pos += len;  // consume size field

  // pos now designates start of payload

  if ((total >= 0) && ((total - pos) < result))
    return E_FILE_FORMAT_INVALID;

  if ((available - pos) < result)
    return pos + result;

  end = pos + result;

  Init();

  while (pos < end) {
    long long id, size;

    status = ParseElementHeader(pReader, pos, end, id, size);

    if (status < 0)  // error
      return status;

    if (size == 0)  // weird
      return E_FILE_FORMAT_INVALID;

    if (id == 0x0286) {  // version
      m_version = UnserializeUInt(pReader, pos, size);

      if (m_version <= 0)
        return E_FILE_FORMAT_INVALID;
    } else if (id == 0x02F7) {  // read version
      m_readVersion = UnserializeUInt(pReader, pos, size);

      if (m_readVersion <= 0)
        return E_FILE_FORMAT_INVALID;
    } else if (id == 0x02F2) {  // max id length
      m_maxIdLength = UnserializeUInt(pReader, pos, size);

      if (m_maxIdLength <= 0)
        return E_FILE_FORMAT_INVALID;
    } else if (id == 0x02F3) {  // max size length
      m_maxSizeLength = UnserializeUInt(pReader, pos, size);

      if (m_maxSizeLength <= 0)
        return E_FILE_FORMAT_INVALID;
    } else if (id == 0x0282) {  // doctype
      if (m_docType)
        return E_FILE_FORMAT_INVALID;

      status = UnserializeString(pReader, pos, size, m_docType);

      if (status)  // error
        return status;
    } else if (id == 0x0287) {  // doctype version
      m_docTypeVersion = UnserializeUInt(pReader, pos, size);

      if (m_docTypeVersion <= 0)
        return E_FILE_FORMAT_INVALID;
    } else if (id == 0x0285) {  // doctype read version
      m_docTypeReadVersion = UnserializeUInt(pReader, pos, size);

      if (m_docTypeReadVersion <= 0)
        return E_FILE_FORMAT_INVALID;
    }

    pos += size;
  }

  if (pos != end)
    return E_FILE_FORMAT_INVALID;

  return 0;
}

Segment::Segment(IMkvReader* pReader, long long elem_start,
                 // long long elem_size,
                 long long start, long long size)
    : m_pReader(pReader),
      m_element_start(elem_start),
      // m_element_size(elem_size),
      m_start(start),
      m_size(size),
      m_pos(start),
      m_pUnknownSize(0),
      m_pSeekHead(NULL),
      m_pInfo(NULL),
      m_pTracks(NULL),
      m_pCues(NULL),
      m_pChapters(NULL),
      m_pTags(NULL),
      m_clusters(NULL),
      m_clusterCount(0),
      m_clusterPreloadCount(0),
      m_clusterSize(0) {}

Segment::~Segment() {
  const long count = m_clusterCount + m_clusterPreloadCount;

  Cluster** i = m_clusters;
  Cluster** j = m_clusters + count;

  while (i != j) {
    Cluster* const p = *i++;
    delete p;
  }

  delete[] m_clusters;

  delete m_pTracks;
  delete m_pInfo;
  delete m_pCues;
  delete m_pChapters;
  delete m_pTags;
  delete m_pSeekHead;
}

long long Segment::CreateInstance(IMkvReader* pReader, long long pos,
                                  Segment*& pSegment) {
  if (pReader == NULL || pos < 0)
    return E_PARSE_FAILED;

  pSegment = NULL;

  long long total, available;

  const long status = pReader->Length(&total, &available);

  if (status < 0)  // error
    return status;

  if (available < 0)
    return -1;

  if ((total >= 0) && (available > total))
    return -1;

  // I would assume that in practice this loop would execute
  // exactly once, but we allow for other elements (e.g. Void)
  // to immediately follow the EBML header.  This is fine for
  // the source filter case (since the entire file is available),
  // but in the splitter case over a network we should probably
  // just give up early.  We could for example decide only to
  // execute this loop a maximum of, say, 10 times.
  // TODO:
  // There is an implied "give up early" by only parsing up
  // to the available limit.  We do do that, but only if the
  // total file size is unknown.  We could decide to always
  // use what's available as our limit (irrespective of whether
  // we happen to know the total file length).  This would have
  // as its sense "parse this much of the file before giving up",
  // which a slightly different sense from "try to parse up to
  // 10 EMBL elements before giving up".

  for (;;) {
    if ((total >= 0) && (pos >= total))
      return E_FILE_FORMAT_INVALID;

    // Read ID
    long len;
    long long result = GetUIntLength(pReader, pos, len);

    if (result)  // error, or too few available bytes
      return result;

    if ((total >= 0) && ((pos + len) > total))
      return E_FILE_FORMAT_INVALID;

    if ((pos + len) > available)
      return pos + len;

    const long long idpos = pos;
    const long long id = ReadID(pReader, pos, len);

    if (id < 0)
      return E_FILE_FORMAT_INVALID;

    pos += len;  // consume ID

    // Read Size

    result = GetUIntLength(pReader, pos, len);

    if (result)  // error, or too few available bytes
      return result;

    if ((total >= 0) && ((pos + len) > total))
      return E_FILE_FORMAT_INVALID;

    if ((pos + len) > available)
      return pos + len;

    long long size = ReadUInt(pReader, pos, len);

    if (size < 0)  // error
      return size;

    pos += len;  // consume length of size of element

    // Pos now points to start of payload

    // Handle "unknown size" for live streaming of webm files.
    const long long unknown_size = (1LL << (7 * len)) - 1;

    if (id == 0x08538067) {  // Segment ID
      if (size == unknown_size)
        size = -1;

      else if (total < 0)
        size = -1;

      else if ((pos + size) > total)
        size = -1;

      pSegment = new (std::nothrow) Segment(pReader, idpos,
                                            // elem_size
                                            pos, size);

      if (pSegment == 0)
        return -1;  // generic error

      return 0;  // success
    }

    if (size == unknown_size)
      return E_FILE_FORMAT_INVALID;

    if ((total >= 0) && ((pos + size) > total))
      return E_FILE_FORMAT_INVALID;

    if ((pos + size) > available)
      return pos + size;

    pos += size;  // consume payload
  }
}

long long Segment::ParseHeaders() {
  // Outermost (level 0) segment object has been constructed,
  // and pos designates start of payload.  We need to find the
  // inner (level 1) elements.
  long long total, available;

  const int status = m_pReader->Length(&total, &available);

  if (status < 0)  // error
    return status;

  if (total > 0 && available > total)
    return E_FILE_FORMAT_INVALID;

  const long long segment_stop = (m_size < 0) ? -1 : m_start + m_size;

  if ((segment_stop >= 0 && total >= 0 && segment_stop > total) ||
      (segment_stop >= 0 && m_pos > segment_stop)) {
    return E_FILE_FORMAT_INVALID;
  }

  for (;;) {
    if ((total >= 0) && (m_pos >= total))
      break;

    if ((segment_stop >= 0) && (m_pos >= segment_stop))
      break;

    long long pos = m_pos;
    const long long element_start = pos;

    // Avoid rolling over pos when very close to LONG_LONG_MAX.
    unsigned long long rollover_check = pos + 1ULL;
    if (rollover_check > LONG_LONG_MAX)
      return E_FILE_FORMAT_INVALID;

    if ((pos + 1) > available)
      return (pos + 1);

    long len;
    long long result = GetUIntLength(m_pReader, pos, len);

    if (result < 0)  // error
      return result;

    if (result > 0) {
      // MkvReader doesn't have enough data to satisfy this read attempt.
      return (pos + 1);
    }

    if ((segment_stop >= 0) && ((pos + len) > segment_stop))
      return E_FILE_FORMAT_INVALID;

    if ((pos + len) > available)
      return pos + len;

    const long long idpos = pos;
    const long long id = ReadID(m_pReader, idpos, len);

    if (id < 0)
      return E_FILE_FORMAT_INVALID;

    if (id == 0x0F43B675)  // Cluster ID
      break;

    pos += len;  // consume ID

    if ((pos + 1) > available)
      return (pos + 1);

    // Read Size
    result = GetUIntLength(m_pReader, pos, len);

    if (result < 0)  // error
      return result;

    if (result > 0) {
      // MkvReader doesn't have enough data to satisfy this read attempt.
      return (pos + 1);
    }

    if ((segment_stop >= 0) && ((pos + len) > segment_stop))
      return E_FILE_FORMAT_INVALID;

    if ((pos + len) > available)
      return pos + len;

    const long long size = ReadUInt(m_pReader, pos, len);

    if (size < 0 || len < 1 || len > 8) {
      // TODO(tomfinegan): ReadUInt should return an error when len is < 1 or
      // len > 8 is true instead of checking this _everywhere_.
      return size;
    }

    pos += len;  // consume length of size of element

    // Avoid rolling over pos when very close to LONG_LONG_MAX.
    rollover_check = static_cast<unsigned long long>(pos) + size;
    if (rollover_check > LONG_LONG_MAX)
      return E_FILE_FORMAT_INVALID;

    const long long element_size = size + pos - element_start;

    // Pos now points to start of payload

    if ((segment_stop >= 0) && ((pos + size) > segment_stop))
      return E_FILE_FORMAT_INVALID;

    // We read EBML elements either in total or nothing at all.

    if ((pos + size) > available)
      return pos + size;

    if (id == 0x0549A966) {  // Segment Info ID
      if (m_pInfo)
        return E_FILE_FORMAT_INVALID;

      m_pInfo = new (std::nothrow)
          SegmentInfo(this, pos, size, element_start, element_size);

      if (m_pInfo == NULL)
        return -1;

      const long status = m_pInfo->Parse();

      if (status)
        return status;
    } else if (id == 0x0654AE6B) {  // Tracks ID
      if (m_pTracks)
        return E_FILE_FORMAT_INVALID;

      m_pTracks = new (std::nothrow)
          Tracks(this, pos, size, element_start, element_size);

      if (m_pTracks == NULL)
        return -1;

      const long status = m_pTracks->Parse();

      if (status)
        return status;
    } else if (id == 0x0C53BB6B) {  // Cues ID
      if (m_pCues == NULL) {
        m_pCues = new (std::nothrow)
            Cues(this, pos, size, element_start, element_size);

        if (m_pCues == NULL)
          return -1;
      }
    } else if (id == 0x014D9B74) {  // SeekHead ID
      if (m_pSeekHead == NULL) {
        m_pSeekHead = new (std::nothrow)
            SeekHead(this, pos, size, element_start, element_size);

        if (m_pSeekHead == NULL)
          return -1;

        const long status = m_pSeekHead->Parse();

        if (status)
          return status;
      }
    } else if (id == 0x0043A770) {  // Chapters ID
      if (m_pChapters == NULL) {
        m_pChapters = new (std::nothrow)
            Chapters(this, pos, size, element_start, element_size);

        if (m_pChapters == NULL)
          return -1;

        const long status = m_pChapters->Parse();

        if (status)
          return status;
      }
    } else if (id == 0x0254C367) {  // Tags ID
      if (m_pTags == NULL) {
        m_pTags = new (std::nothrow)
            Tags(this, pos, size, element_start, element_size);

        if (m_pTags == NULL)
          return -1;

        const long status = m_pTags->Parse();

        if (status)
          return status;
      }
    }

    m_pos = pos + size;  // consume payload
  }

  if (segment_stop >= 0 && m_pos > segment_stop)
    return E_FILE_FORMAT_INVALID;

  if (m_pInfo == NULL)  // TODO: liberalize this behavior
    return E_FILE_FORMAT_INVALID;

  if (m_pTracks == NULL)
    return E_FILE_FORMAT_INVALID;

  return 0;  // success
}

long Segment::LoadCluster(long long& pos, long& len) {
  for (;;) {
    const long result = DoLoadCluster(pos, len);

    if (result <= 1)
      return result;
  }
}

long Segment::DoLoadCluster(long long& pos, long& len) {
  if (m_pos < 0)
    return DoLoadClusterUnknownSize(pos, len);

  long long total, avail;

  long status = m_pReader->Length(&total, &avail);

  if (status < 0)  // error
    return status;

  if (total >= 0 && avail > total)
    return E_FILE_FORMAT_INVALID;

  const long long segment_stop = (m_size < 0) ? -1 : m_start + m_size;

  long long cluster_off = -1;  // offset relative to start of segment
  long long cluster_size = -1;  // size of cluster payload

  for (;;) {
    if ((total >= 0) && (m_pos >= total))
      return 1;  // no more clusters

    if ((segment_stop >= 0) && (m_pos >= segment_stop))
      return 1;  // no more clusters

    pos = m_pos;

    // Read ID

    if ((pos + 1) > avail) {
      len = 1;
      return E_BUFFER_NOT_FULL;
    }

    long long result = GetUIntLength(m_pReader, pos, len);

    if (result < 0)  // error
      return static_cast<long>(result);

    if (result > 0)  // weird
      return E_BUFFER_NOT_FULL;

    if ((segment_stop >= 0) && ((pos + len) > segment_stop))
      return E_FILE_FORMAT_INVALID;

    if ((pos + len) > avail)
      return E_BUFFER_NOT_FULL;

    const long long idpos = pos;
    const long long id = ReadID(m_pReader, idpos, len);

    if (id < 0)
      return E_FILE_FORMAT_INVALID;

    pos += len;  // consume ID

    // Read Size

    if ((pos + 1) > avail) {
      len = 1;
      return E_BUFFER_NOT_FULL;
    }

    result = GetUIntLength(m_pReader, pos, len);

    if (result < 0)  // error
      return static_cast<long>(result);

    if (result > 0)  // weird
      return E_BUFFER_NOT_FULL;

    if ((segment_stop >= 0) && ((pos + len) > segment_stop))
      return E_FILE_FORMAT_INVALID;

    if ((pos + len) > avail)
      return E_BUFFER_NOT_FULL;

    const long long size = ReadUInt(m_pReader, pos, len);

    if (size < 0)  // error
      return static_cast<long>(size);

    pos += len;  // consume length of size of element

    // pos now points to start of payload

    if (size == 0) {  // weird
      m_pos = pos;
      continue;
    }

    const long long unknown_size = (1LL << (7 * len)) - 1;

    if ((segment_stop >= 0) && (size != unknown_size) &&
        ((pos + size) > segment_stop)) {
      return E_FILE_FORMAT_INVALID;
    }

    if (id == 0x0C53BB6B) {  // Cues ID
      if (size == unknown_size)
        return E_FILE_FORMAT_INVALID;  // TODO: liberalize

      if (m_pCues == NULL) {
        const long long element_size = (pos - idpos) + size;

        m_pCues = new (std::nothrow) Cues(this, pos, size, idpos, element_size);
        if (m_pCues == NULL)
          return -1;
      }

      m_pos = pos + size;  // consume payload
      continue;
    }

    if (id != 0x0F43B675) {  // Cluster ID
      if (size == unknown_size)
        return E_FILE_FORMAT_INVALID;  // TODO: liberalize

      m_pos = pos + size;  // consume payload
      continue;
    }

    // We have a cluster.

    cluster_off = idpos - m_start;  // relative pos

    if (size != unknown_size)
      cluster_size = size;

    break;
  }

  if (cluster_off < 0) {
    // No cluster, die.
    return E_FILE_FORMAT_INVALID;
  }

  long long pos_;
  long len_;

  status = Cluster::HasBlockEntries(this, cluster_off, pos_, len_);

  if (status < 0) {  // error, or underflow
    pos = pos_;
    len = len_;

    return status;
  }

  // status == 0 means "no block entries found"
  // status > 0 means "found at least one block entry"

  // TODO:
  // The issue here is that the segment increments its own
  // pos ptr past the most recent cluster parsed, and then
  // starts from there to parse the next cluster.  If we
  // don't know the size of the current cluster, then we
  // must either parse its payload (as we do below), looking
  // for the cluster (or cues) ID to terminate the parse.
  // This isn't really what we want: rather, we really need
  // a way to create the curr cluster object immediately.
  // The pity is that cluster::parse can determine its own
  // boundary, and we largely duplicate that same logic here.
  //
  // Maybe we need to get rid of our look-ahead preloading
  // in source::parse???
  //
  // As we're parsing the blocks in the curr cluster
  //(in cluster::parse), we should have some way to signal
  // to the segment that we have determined the boundary,
  // so it can adjust its own segment::m_pos member.
  //
  // The problem is that we're asserting in asyncreadinit,
  // because we adjust the pos down to the curr seek pos,
  // and the resulting adjusted len is > 2GB.  I'm suspicious
  // that this is even correct, but even if it is, we can't
  // be loading that much data in the cache anyway.

  const long idx = m_clusterCount;

  if (m_clusterPreloadCount > 0) {
    if (idx >= m_clusterSize)
      return E_FILE_FORMAT_INVALID;

    Cluster* const pCluster = m_clusters[idx];
    if (pCluster == NULL || pCluster->m_index >= 0)
      return E_FILE_FORMAT_INVALID;

    const long long off = pCluster->GetPosition();
    if (off < 0)
      return E_FILE_FORMAT_INVALID;

    if (off == cluster_off) {  // preloaded already
      if (status == 0)  // no entries found
        return E_FILE_FORMAT_INVALID;

      if (cluster_size >= 0)
        pos += cluster_size;
      else {
        const long long element_size = pCluster->GetElementSize();

        if (element_size <= 0)
          return E_FILE_FORMAT_INVALID;  // TODO: handle this case

        pos = pCluster->m_element_start + element_size;
      }

      pCluster->m_index = idx;  // move from preloaded to loaded
      ++m_clusterCount;
      --m_clusterPreloadCount;

      m_pos = pos;  // consume payload
      if (segment_stop >= 0 && m_pos > segment_stop)
        return E_FILE_FORMAT_INVALID;

      return 0;  // success
    }
  }

  if (status == 0) {  // no entries found
    if (cluster_size >= 0)
      pos += cluster_size;

    if ((total >= 0) && (pos >= total)) {
      m_pos = total;
      return 1;  // no more clusters
    }

    if ((segment_stop >= 0) && (pos >= segment_stop)) {
      m_pos = segment_stop;
      return 1;  // no more clusters
    }

    m_pos = pos;
    return 2;  // try again
  }

  // status > 0 means we have an entry

  Cluster* const pCluster = Cluster::Create(this, idx, cluster_off);
  if (pCluster == NULL)
    return -1;

  if (!AppendCluster(pCluster)) {
    delete pCluster;
    return -1;
  }

  if (cluster_size >= 0) {
    pos += cluster_size;

    m_pos = pos;

    if (segment_stop > 0 && m_pos > segment_stop)
      return E_FILE_FORMAT_INVALID;

    return 0;
  }

  m_pUnknownSize = pCluster;
  m_pos = -pos;

  return 0;  // partial success, since we have a new cluster

  // status == 0 means "no block entries found"
  // pos designates start of payload
  // m_pos has NOT been adjusted yet (in case we need to come back here)
}

long Segment::DoLoadClusterUnknownSize(long long& pos, long& len) {
  if (m_pos >= 0 || m_pUnknownSize == NULL)
    return E_PARSE_FAILED;

  const long status = m_pUnknownSize->Parse(pos, len);

  if (status < 0)  // error or underflow
    return status;

  if (status == 0)  // parsed a block
    return 2;  // continue parsing

  const long long start = m_pUnknownSize->m_element_start;
  const long long size = m_pUnknownSize->GetElementSize();

  if (size < 0)
    return E_FILE_FORMAT_INVALID;

  pos = start + size;
  m_pos = pos;

  m_pUnknownSize = 0;

  return 2;  // continue parsing
}

bool Segment::AppendCluster(Cluster* pCluster) {
  if (pCluster == NULL || pCluster->m_index < 0)
    return false;

  const long count = m_clusterCount + m_clusterPreloadCount;

  long& size = m_clusterSize;
  const long idx = pCluster->m_index;

  if (size < count || idx != m_clusterCount)
    return false;

  if (count >= size) {
    const long n = (size <= 0) ? 2048 : 2 * size;

    Cluster** const qq = new (std::nothrow) Cluster*[n];
    if (qq == NULL)
      return false;

    Cluster** q = qq;
    Cluster** p = m_clusters;
    Cluster** const pp = p + count;

    while (p != pp)
      *q++ = *p++;

    delete[] m_clusters;

    m_clusters = qq;
    size = n;
  }

  if (m_clusterPreloadCount > 0) {
    Cluster** const p = m_clusters + m_clusterCount;
    if (*p == NULL || (*p)->m_index >= 0)
      return false;

    Cluster** q = p + m_clusterPreloadCount;
    if (q >= (m_clusters + size))
      return false;

    for (;;) {
      Cluster** const qq = q - 1;
      if ((*qq)->m_index >= 0)
        return false;

      *q = *qq;
      q = qq;

      if (q == p)
        break;
    }
  }

  m_clusters[idx] = pCluster;
  ++m_clusterCount;
  return true;
}

bool Segment::PreloadCluster(Cluster* pCluster, ptrdiff_t idx) {
  assert(pCluster);
  assert(pCluster->m_index < 0);
  assert(idx >= m_clusterCount);

  const long count = m_clusterCount + m_clusterPreloadCount;

  long& size = m_clusterSize;
  assert(size >= count);

  if (count >= size) {
    const long n = (size <= 0) ? 2048 : 2 * size;

    Cluster** const qq = new (std::nothrow) Cluster*[n];
    if (qq == NULL)
      return false;
    Cluster** q = qq;

    Cluster** p = m_clusters;
    Cluster** const pp = p + count;

    while (p != pp)
      *q++ = *p++;

    delete[] m_clusters;

    m_clusters = qq;
    size = n;
  }

  assert(m_clusters);

  Cluster** const p = m_clusters + idx;

  Cluster** q = m_clusters + count;
  assert(q >= p);
  assert(q < (m_clusters + size));

  while (q > p) {
    Cluster** const qq = q - 1;
    assert((*qq)->m_index < 0);

    *q = *qq;
    q = qq;
  }

  m_clusters[idx] = pCluster;
  ++m_clusterPreloadCount;
  return true;
}

long Segment::Load() {
  assert(m_clusters == NULL);
  assert(m_clusterSize == 0);
  assert(m_clusterCount == 0);
  // assert(m_size >= 0);

  // Outermost (level 0) segment object has been constructed,
  // and pos designates start of payload.  We need to find the
  // inner (level 1) elements.

  const long long header_status = ParseHeaders();

  if (header_status < 0)  // error
    return static_cast<long>(header_status);

  if (header_status > 0)  // underflow
    return E_BUFFER_NOT_FULL;

  if (m_pInfo == NULL || m_pTracks == NULL)
    return E_FILE_FORMAT_INVALID;

  for (;;) {
    const int status = LoadCluster();

    if (status < 0)  // error
      return status;

    if (status >= 1)  // no more clusters
      return 0;
  }
}

SeekHead::SeekHead(Segment* pSegment, long long start, long long size_,
                   long long element_start, long long element_size)
    : m_pSegment(pSegment),
      m_start(start),
      m_size(size_),
      m_element_start(element_start),
      m_element_size(element_size),
      m_entries(0),
      m_entry_count(0),
      m_void_elements(0),
      m_void_element_count(0) {}

SeekHead::~SeekHead() {
  delete[] m_entries;
  delete[] m_void_elements;
}

long SeekHead::Parse() {
  IMkvReader* const pReader = m_pSegment->m_pReader;

  long long pos = m_start;
  const long long stop = m_start + m_size;

  // first count the seek head entries

  int entry_count = 0;
  int void_element_count = 0;

  while (pos < stop) {
    long long id, size;

    const long status = ParseElementHeader(pReader, pos, stop, id, size);

    if (status < 0)  // error
      return status;

    if (id == 0x0DBB)  // SeekEntry ID
      ++entry_count;
    else if (id == 0x6C)  // Void ID
      ++void_element_count;

    pos += size;  // consume payload

    if (pos > stop)
      return E_FILE_FORMAT_INVALID;
  }

  if (pos != stop)
    return E_FILE_FORMAT_INVALID;

  m_entries = new (std::nothrow) Entry[entry_count];

  if (m_entries == NULL)
    return -1;

  m_void_elements = new (std::nothrow) VoidElement[void_element_count];

  if (m_void_elements == NULL)
    return -1;

  // now parse the entries and void elements

  Entry* pEntry = m_entries;
  VoidElement* pVoidElement = m_void_elements;

  pos = m_start;

  while (pos < stop) {
    const long long idpos = pos;

    long long id, size;

    const long status = ParseElementHeader(pReader, pos, stop, id, size);

    if (status < 0)  // error
      return status;

    if (id == 0x0DBB) {  // SeekEntry ID
      if (ParseEntry(pReader, pos, size, pEntry)) {
        Entry& e = *pEntry++;

        e.element_start = idpos;
        e.element_size = (pos + size) - idpos;
      }
    } else if (id == 0x6C) {  // Void ID
      VoidElement& e = *pVoidElement++;

      e.element_start = idpos;
      e.element_size = (pos + size) - idpos;
    }

    pos += size;  // consume payload
    if (pos > stop)
      return E_FILE_FORMAT_INVALID;
  }

  if (pos != stop)
    return E_FILE_FORMAT_INVALID;

  ptrdiff_t count_ = ptrdiff_t(pEntry - m_entries);
  assert(count_ >= 0);
  assert(count_ <= entry_count);

  m_entry_count = static_cast<int>(count_);

  count_ = ptrdiff_t(pVoidElement - m_void_elements);
  assert(count_ >= 0);
  assert(count_ <= void_element_count);

  m_void_element_count = static_cast<int>(count_);

  return 0;
}

int SeekHead::GetCount() const { return m_entry_count; }

const SeekHead::Entry* SeekHead::GetEntry(int idx) const {
  if (idx < 0)
    return 0;

  if (idx >= m_entry_count)
    return 0;

  return m_entries + idx;
}

int SeekHead::GetVoidElementCount() const { return m_void_element_count; }

const SeekHead::VoidElement* SeekHead::GetVoidElement(int idx) const {
  if (idx < 0)
    return 0;

  if (idx >= m_void_element_count)
    return 0;

  return m_void_elements + idx;
}

long Segment::ParseCues(long long off, long long& pos, long& len) {
  if (m_pCues)
    return 0;  // success

  if (off < 0)
    return -1;

  long long total, avail;

  const int status = m_pReader->Length(&total, &avail);

  if (status < 0)  // error
    return status;

  assert((total < 0) || (avail <= total));

  pos = m_start + off;

  if ((total < 0) || (pos >= total))
    return 1;  // don't bother parsing cues

  const long long element_start = pos;
  const long long segment_stop = (m_size < 0) ? -1 : m_start + m_size;

  if ((pos + 1) > avail) {
    len = 1;
    return E_BUFFER_NOT_FULL;
  }

  long long result = GetUIntLength(m_pReader, pos, len);

  if (result < 0)  // error
    return static_cast<long>(result);

  if (result > 0)  // underflow (weird)
  {
    len = 1;
    return E_BUFFER_NOT_FULL;
  }

  if ((segment_stop >= 0) && ((pos + len) > segment_stop))
    return E_FILE_FORMAT_INVALID;

  if ((pos + len) > avail)
    return E_BUFFER_NOT_FULL;

  const long long idpos = pos;

  const long long id = ReadID(m_pReader, idpos, len);

  if (id != 0x0C53BB6B)  // Cues ID
    return E_FILE_FORMAT_INVALID;

  pos += len;  // consume ID
  assert((segment_stop < 0) || (pos <= segment_stop));

  // Read Size

  if ((pos + 1) > avail) {
    len = 1;
    return E_BUFFER_NOT_FULL;
  }

  result = GetUIntLength(m_pReader, pos, len);

  if (result < 0)  // error
    return static_cast<long>(result);

  if (result > 0)  // underflow (weird)
  {
    len = 1;
    return E_BUFFER_NOT_FULL;
  }

  if ((segment_stop >= 0) && ((pos + len) > segment_stop))
    return E_FILE_FORMAT_INVALID;

  if ((pos + len) > avail)
    return E_BUFFER_NOT_FULL;

  const long long size = ReadUInt(m_pReader, pos, len);

  if (size < 0)  // error
    return static_cast<long>(size);

  if (size == 0)  // weird, although technically not illegal
    return 1;  // done

  pos += len;  // consume length of size of element
  assert((segment_stop < 0) || (pos <= segment_stop));

  // Pos now points to start of payload

  const long long element_stop = pos + size;

  if ((segment_stop >= 0) && (element_stop > segment_stop))
    return E_FILE_FORMAT_INVALID;

  if ((total >= 0) && (element_stop > total))
    return 1;  // don't bother parsing anymore

  len = static_cast<long>(size);

  if (element_stop > avail)
    return E_BUFFER_NOT_FULL;

  const long long element_size = element_stop - element_start;

  m_pCues =
      new (std::nothrow) Cues(this, pos, size, element_start, element_size);
  if (m_pCues == NULL)
    return -1;

  return 0;  // success
}

bool SeekHead::ParseEntry(IMkvReader* pReader, long long start, long long size_,
                          Entry* pEntry) {
  if (size_ <= 0)
    return false;

  long long pos = start;
  const long long stop = start + size_;

  long len;

  // parse the container for the level-1 element ID

  const long long seekIdId = ReadID(pReader, pos, len);
  if (seekIdId < 0)
    return false;

  if (seekIdId != 0x13AB)  // SeekID ID
    return false;

  if ((pos + len) > stop)
    return false;

  pos += len;  // consume SeekID id

  const long long seekIdSize = ReadUInt(pReader, pos, len);

  if (seekIdSize <= 0)
    return false;

  if ((pos + len) > stop)
    return false;

  pos += len;  // consume size of field

  if ((pos + seekIdSize) > stop)
    return false;

  // Note that the SeekId payload really is serialized
  // as a "Matroska integer", not as a plain binary value.
  // In fact, Matroska requires that ID values in the
  // stream exactly match the binary representation as listed
  // in the Matroska specification.
  //
  // This parser is more liberal, and permits IDs to have
  // any width.  (This could make the representation in the stream
  // different from what's in the spec, but it doesn't matter here,
  // since we always normalize "Matroska integer" values.)

  pEntry->id = ReadUInt(pReader, pos, len);  // payload

  if (pEntry->id <= 0)
    return false;

  if (len != seekIdSize)
    return false;

  pos += seekIdSize;  // consume SeekID payload

  const long long seekPosId = ReadUInt(pReader, pos, len);

  if (seekPosId != 0x13AC)  // SeekPos ID
    return false;

  if ((pos + len) > stop)
    return false;

  pos += len;  // consume id

  const long long seekPosSize = ReadUInt(pReader, pos, len);

  if (seekPosSize <= 0)
    return false;

  if ((pos + len) > stop)
    return false;

  pos += len;  // consume size

  if ((pos + seekPosSize) > stop)
    return false;

  pEntry->pos = UnserializeUInt(pReader, pos, seekPosSize);

  if (pEntry->pos < 0)
    return false;

  pos += seekPosSize;  // consume payload

  if (pos != stop)
    return false;

  return true;
}

Cues::Cues(Segment* pSegment, long long start_, long long size_,
           long long element_start, long long element_size)
    : m_pSegment(pSegment),
      m_start(start_),
      m_size(size_),
      m_element_start(element_start),
      m_element_size(element_size),
      m_cue_points(NULL),
      m_count(0),
      m_preload_count(0),
      m_pos(start_) {}

Cues::~Cues() {
  const long n = m_count + m_preload_count;

  CuePoint** p = m_cue_points;
  CuePoint** const q = p + n;

  while (p != q) {
    CuePoint* const pCP = *p++;
    assert(pCP);

    delete pCP;
  }

  delete[] m_cue_points;
}

long Cues::GetCount() const {
  if (m_cue_points == NULL)
    return -1;

  return m_count;  // TODO: really ignore preload count?
}

bool Cues::DoneParsing() const {
  const long long stop = m_start + m_size;
  return (m_pos >= stop);
}

bool Cues::Init() const {
  if (m_cue_points)
    return true;

  if (m_count != 0 || m_preload_count != 0)
    return false;

  IMkvReader* const pReader = m_pSegment->m_pReader;

  const long long stop = m_start + m_size;
  long long pos = m_start;

  long cue_points_size = 0;

  while (pos < stop) {
    const long long idpos = pos;

    long len;

    const long long id = ReadID(pReader, pos, len);
    if (id < 0 || (pos + len) > stop) {
      return false;
    }

    pos += len;  // consume ID

    const long long size = ReadUInt(pReader, pos, len);
    if (size < 0 || (pos + len > stop)) {
      return false;
    }

    pos += len;  // consume Size field
    if (pos + size > stop) {
      return false;
    }

    if (id == 0x3B) {  // CuePoint ID
      if (!PreloadCuePoint(cue_points_size, idpos))
        return false;
    }

    pos += size;  // skip payload
  }
  return true;
}

bool Cues::PreloadCuePoint(long& cue_points_size, long long pos) const {
  if (m_count != 0)
    return false;

  if (m_preload_count >= cue_points_size) {
    const long n = (cue_points_size <= 0) ? 2048 : 2 * cue_points_size;

    CuePoint** const qq = new (std::nothrow) CuePoint*[n];
    if (qq == NULL)
      return false;

    CuePoint** q = qq;  // beginning of target

    CuePoint** p = m_cue_points;  // beginning of source
    CuePoint** const pp = p + m_preload_count;  // end of source

    while (p != pp)
      *q++ = *p++;

    delete[] m_cue_points;

    m_cue_points = qq;
    cue_points_size = n;
  }

  CuePoint* const pCP = new (std::nothrow) CuePoint(m_preload_count, pos);
  if (pCP == NULL)
    return false;

  m_cue_points[m_preload_count++] = pCP;
  return true;
}

bool Cues::LoadCuePoint() const {
  const long long stop = m_start + m_size;

  if (m_pos >= stop)
    return false;  // nothing else to do

  if (!Init()) {
    m_pos = stop;
    return false;
  }

  IMkvReader* const pReader = m_pSegment->m_pReader;

  while (m_pos < stop) {
    const long long idpos = m_pos;

    long len;

    const long long id = ReadID(pReader, m_pos, len);
    if (id < 0 || (m_pos + len) > stop)
      return false;

    m_pos += len;  // consume ID

    const long long size = ReadUInt(pReader, m_pos, len);
    if (size < 0 || (m_pos + len) > stop)
      return false;

    m_pos += len;  // consume Size field
    if ((m_pos + size) > stop)
      return false;

    if (id != 0x3B) {  // CuePoint ID
      m_pos += size;  // consume payload
      if (m_pos > stop)
        return false;

      continue;
    }

    if (m_preload_count < 1)
      return false;

    CuePoint* const pCP = m_cue_points[m_count];
    if (!pCP || (pCP->GetTimeCode() < 0 && (-pCP->GetTimeCode() != idpos)))
      return false;

    if (!pCP->Load(pReader)) {
      m_pos = stop;
      return false;
    }
    ++m_count;
    --m_preload_count;

    m_pos += size;  // consume payload
    if (m_pos > stop)
      return false;

    return true;  // yes, we loaded a cue point
  }

  return false;  // no, we did not load a cue point
}

bool Cues::Find(long long time_ns, const Track* pTrack, const CuePoint*& pCP,
                const CuePoint::TrackPosition*& pTP) const {
  if (time_ns < 0 || pTrack == NULL || m_cue_points == NULL || m_count == 0)
    return false;

  CuePoint** const ii = m_cue_points;
  CuePoint** i = ii;

  CuePoint** const jj = ii + m_count;
  CuePoint** j = jj;

  pCP = *i;
  if (pCP == NULL)
    return false;

  if (time_ns <= pCP->GetTime(m_pSegment)) {
    pTP = pCP->Find(pTrack);
    return (pTP != NULL);
  }

  while (i < j) {
    // INVARIANT:
    //[ii, i) <= time_ns
    //[i, j)  ?
    //[j, jj) > time_ns

    CuePoint** const k = i + (j - i) / 2;
    if (k >= jj)
      return false;

    CuePoint* const pCP = *k;
    if (pCP == NULL)
      return false;

    const long long t = pCP->GetTime(m_pSegment);

    if (t <= time_ns)
      i = k + 1;
    else
      j = k;

    if (i > j)
      return false;
  }

  if (i != j || i > jj || i <= ii)
    return false;

  pCP = *--i;

  if (pCP == NULL || pCP->GetTime(m_pSegment) > time_ns)
    return false;

  // TODO: here and elsewhere, it's probably not correct to search
  // for the cue point with this time, and then search for a matching
  // track.  In principle, the matching track could be on some earlier
  // cue point, and with our current algorithm, we'd miss it.  To make
  // this bullet-proof, we'd need to create a secondary structure,
  // with a list of cue points that apply to a track, and then search
  // that track-based structure for a matching cue point.

  pTP = pCP->Find(pTrack);
  return (pTP != NULL);
}

const CuePoint* Cues::GetFirst() const {
  if (m_cue_points == NULL || m_count == 0)
    return NULL;

  CuePoint* const* const pp = m_cue_points;
  if (pp == NULL)
    return NULL;

  CuePoint* const pCP = pp[0];
  if (pCP == NULL || pCP->GetTimeCode() < 0)
    return NULL;

  return pCP;
}

const CuePoint* Cues::GetLast() const {
  if (m_cue_points == NULL || m_count <= 0)
    return NULL;

  const long index = m_count - 1;

  CuePoint* const* const pp = m_cue_points;
  if (pp == NULL)
    return NULL;

  CuePoint* const pCP = pp[index];
  if (pCP == NULL || pCP->GetTimeCode() < 0)
    return NULL;

  return pCP;
}

const CuePoint* Cues::GetNext(const CuePoint* pCurr) const {
  if (pCurr == NULL || pCurr->GetTimeCode() < 0 ||
      m_cue_points == NULL || m_count < 1) {
    return NULL;
  }

  long index = pCurr->m_index;
  if (index >= m_count)
    return NULL;

  CuePoint* const* const pp = m_cue_points;
  if (pp == NULL || pp[index] != pCurr)
    return NULL;

  ++index;

  if (index >= m_count)
    return NULL;

  CuePoint* const pNext = pp[index];

  if (pNext == NULL || pNext->GetTimeCode() < 0)
    return NULL;

  return pNext;
}

const BlockEntry* Cues::GetBlock(const CuePoint* pCP,
                                 const CuePoint::TrackPosition* pTP) const {
  if (pCP == NULL || pTP == NULL)
    return NULL;

  return m_pSegment->GetBlock(*pCP, *pTP);
}

const BlockEntry* Segment::GetBlock(const CuePoint& cp,
                                    const CuePoint::TrackPosition& tp) {
  Cluster** const ii = m_clusters;
  Cluster** i = ii;

  const long count = m_clusterCount + m_clusterPreloadCount;

  Cluster** const jj = ii + count;
  Cluster** j = jj;

  while (i < j) {
    // INVARIANT:
    //[ii, i) < pTP->m_pos
    //[i, j) ?
    //[j, jj)  > pTP->m_pos

    Cluster** const k = i + (j - i) / 2;
    assert(k < jj);

    Cluster* const pCluster = *k;
    assert(pCluster);

    // const long long pos_ = pCluster->m_pos;
    // assert(pos_);
    // const long long pos = pos_ * ((pos_ < 0) ? -1 : 1);

    const long long pos = pCluster->GetPosition();
    assert(pos >= 0);

    if (pos < tp.m_pos)
      i = k + 1;
    else if (pos > tp.m_pos)
      j = k;
    else
      return pCluster->GetEntry(cp, tp);
  }

  assert(i == j);
  // assert(Cluster::HasBlockEntries(this, tp.m_pos));

  Cluster* const pCluster = Cluster::Create(this, -1, tp.m_pos);  //, -1);
  if (pCluster == NULL)
    return NULL;

  const ptrdiff_t idx = i - m_clusters;

  if (!PreloadCluster(pCluster, idx)) {
    delete pCluster;
    return NULL;
  }
  assert(m_clusters);
  assert(m_clusterPreloadCount > 0);
  assert(m_clusters[idx] == pCluster);

  return pCluster->GetEntry(cp, tp);
}

const Cluster* Segment::FindOrPreloadCluster(long long requested_pos) {
  if (requested_pos < 0)
    return 0;

  Cluster** const ii = m_clusters;
  Cluster** i = ii;

  const long count = m_clusterCount + m_clusterPreloadCount;

  Cluster** const jj = ii + count;
  Cluster** j = jj;

  while (i < j) {
    // INVARIANT:
    //[ii, i) < pTP->m_pos
    //[i, j) ?
    //[j, jj)  > pTP->m_pos

    Cluster** const k = i + (j - i) / 2;
    assert(k < jj);

    Cluster* const pCluster = *k;
    assert(pCluster);

    // const long long pos_ = pCluster->m_pos;
    // assert(pos_);
    // const long long pos = pos_ * ((pos_ < 0) ? -1 : 1);

    const long long pos = pCluster->GetPosition();
    assert(pos >= 0);

    if (pos < requested_pos)
      i = k + 1;
    else if (pos > requested_pos)
      j = k;
    else
      return pCluster;
  }

  assert(i == j);
  // assert(Cluster::HasBlockEntries(this, tp.m_pos));

  Cluster* const pCluster = Cluster::Create(this, -1, requested_pos);
  if (pCluster == NULL)
    return NULL;

  const ptrdiff_t idx = i - m_clusters;

  if (!PreloadCluster(pCluster, idx)) {
    delete pCluster;
    return NULL;
  }
  assert(m_clusters);
  assert(m_clusterPreloadCount > 0);
  assert(m_clusters[idx] == pCluster);

  return pCluster;
}

CuePoint::CuePoint(long idx, long long pos)
    : m_element_start(0),
      m_element_size(0),
      m_index(idx),
      m_timecode(-1 * pos),
      m_track_positions(NULL),
      m_track_positions_count(0) {
  assert(pos > 0);
}

CuePoint::~CuePoint() { delete[] m_track_positions; }

bool CuePoint::Load(IMkvReader* pReader) {
  // odbgstream os;
  // os << "CuePoint::Load(begin): timecode=" << m_timecode << endl;

  if (m_timecode >= 0)  // already loaded
    return true;

  assert(m_track_positions == NULL);
  assert(m_track_positions_count == 0);

  long long pos_ = -m_timecode;
  const long long element_start = pos_;

  long long stop;

  {
    long len;

    const long long id = ReadID(pReader, pos_, len);
    if (id != 0x3B)
      return false;

    pos_ += len;  // consume ID

    const long long size = ReadUInt(pReader, pos_, len);
    assert(size >= 0);

    pos_ += len;  // consume Size field
    // pos_ now points to start of payload

    stop = pos_ + size;
  }

  const long long element_size = stop - element_start;

  long long pos = pos_;

  // First count number of track positions

  while (pos < stop) {
    long len;

    const long long id = ReadID(pReader, pos, len);
    if ((id < 0) || (pos + len > stop)) {
      return false;
    }

    pos += len;  // consume ID

    const long long size = ReadUInt(pReader, pos, len);
    if ((size < 0) || (pos + len > stop)) {
      return false;
    }

    pos += len;  // consume Size field
    if ((pos + size) > stop) {
      return false;
    }

    if (id == 0x33)  // CueTime ID
      m_timecode = UnserializeUInt(pReader, pos, size);

    else if (id == 0x37)  // CueTrackPosition(s) ID
      ++m_track_positions_count;

    pos += size;  // consume payload
  }

  if (m_timecode < 0 || m_track_positions_count <= 0) {
    return false;
  }

  // os << "CuePoint::Load(cont'd): idpos=" << idpos
  //   << " timecode=" << m_timecode
  //   << endl;

  m_track_positions = new (std::nothrow) TrackPosition[m_track_positions_count];
  if (m_track_positions == NULL)
    return false;

  // Now parse track positions

  TrackPosition* p = m_track_positions;
  pos = pos_;

  while (pos < stop) {
    long len;

    const long long id = ReadID(pReader, pos, len);
    if (id < 0 || (pos + len) > stop)
      return false;

    pos += len;  // consume ID

    const long long size = ReadUInt(pReader, pos, len);
    assert(size >= 0);
    assert((pos + len) <= stop);

    pos += len;  // consume Size field
    assert((pos + size) <= stop);

    if (id == 0x37) {  // CueTrackPosition(s) ID
      TrackPosition& tp = *p++;
      if (!tp.Parse(pReader, pos, size)) {
        return false;
      }
    }

    pos += size;  // consume payload
    if (pos > stop)
      return false;
  }

  assert(size_t(p - m_track_positions) == m_track_positions_count);

  m_element_start = element_start;
  m_element_size = element_size;

  return true;
}

bool CuePoint::TrackPosition::Parse(IMkvReader* pReader, long long start_,
                                    long long size_) {
  const long long stop = start_ + size_;
  long long pos = start_;

  m_track = -1;
  m_pos = -1;
  m_block = 1;  // default

  while (pos < stop) {
    long len;

    const long long id = ReadID(pReader, pos, len);
    if ((id < 0) || ((pos + len) > stop)) {
      return false;
    }

    pos += len;  // consume ID

    const long long size = ReadUInt(pReader, pos, len);
    if ((size < 0) || ((pos + len) > stop)) {
      return false;
    }

    pos += len;  // consume Size field
    if ((pos + size) > stop) {
      return false;
    }

    if (id == 0x77)  // CueTrack ID
      m_track = UnserializeUInt(pReader, pos, size);

    else if (id == 0x71)  // CueClusterPos ID
      m_pos = UnserializeUInt(pReader, pos, size);

    else if (id == 0x1378)  // CueBlockNumber
      m_block = UnserializeUInt(pReader, pos, size);

    pos += size;  // consume payload
  }

  if ((m_pos < 0) || (m_track <= 0)) {
    return false;
  }

  return true;
}

const CuePoint::TrackPosition* CuePoint::Find(const Track* pTrack) const {
  assert(pTrack);

  const long long n = pTrack->GetNumber();

  const TrackPosition* i = m_track_positions;
  const TrackPosition* const j = i + m_track_positions_count;

  while (i != j) {
    const TrackPosition& p = *i++;

    if (p.m_track == n)
      return &p;
  }

  return NULL;  // no matching track number found
}

long long CuePoint::GetTimeCode() const { return m_timecode; }

long long CuePoint::GetTime(const Segment* pSegment) const {
  assert(pSegment);
  assert(m_timecode >= 0);

  const SegmentInfo* const pInfo = pSegment->GetInfo();
  assert(pInfo);

  const long long scale = pInfo->GetTimeCodeScale();
  assert(scale >= 1);

  const long long time = scale * m_timecode;

  return time;
}

bool Segment::DoneParsing() const {
  if (m_size < 0) {
    long long total, avail;

    const int status = m_pReader->Length(&total, &avail);

    if (status < 0)  // error
      return true;  // must assume done

    if (total < 0)
      return false;  // assume live stream

    return (m_pos >= total);
  }

  const long long stop = m_start + m_size;

  return (m_pos >= stop);
}

const Cluster* Segment::GetFirst() const {
  if ((m_clusters == NULL) || (m_clusterCount <= 0))
    return &m_eos;

  Cluster* const pCluster = m_clusters[0];
  assert(pCluster);

  return pCluster;
}

const Cluster* Segment::GetLast() const {
  if ((m_clusters == NULL) || (m_clusterCount <= 0))
    return &m_eos;

  const long idx = m_clusterCount - 1;

  Cluster* const pCluster = m_clusters[idx];
  assert(pCluster);

  return pCluster;
}

unsigned long Segment::GetCount() const { return m_clusterCount; }

const Cluster* Segment::GetNext(const Cluster* pCurr) {
  assert(pCurr);
  assert(pCurr != &m_eos);
  assert(m_clusters);

  long idx = pCurr->m_index;

  if (idx >= 0) {
    assert(m_clusterCount > 0);
    assert(idx < m_clusterCount);
    assert(pCurr == m_clusters[idx]);

    ++idx;

    if (idx >= m_clusterCount)
      return &m_eos;  // caller will LoadCluster as desired

    Cluster* const pNext = m_clusters[idx];
    assert(pNext);
    assert(pNext->m_index >= 0);
    assert(pNext->m_index == idx);

    return pNext;
  }

  assert(m_clusterPreloadCount > 0);

  long long pos = pCurr->m_element_start;

  assert(m_size >= 0);  // TODO
  const long long stop = m_start + m_size;  // end of segment

  {
    long len;

    long long result = GetUIntLength(m_pReader, pos, len);
    assert(result == 0);
    assert((pos + len) <= stop);  // TODO
    if (result != 0)
      return NULL;

    const long long id = ReadID(m_pReader, pos, len);
    if (id != 0x0F43B675)  // Cluster ID
      return NULL;

    pos += len;  // consume ID

    // Read Size
    result = GetUIntLength(m_pReader, pos, len);
    assert(result == 0);  // TODO
    assert((pos + len) <= stop);  // TODO

    const long long size = ReadUInt(m_pReader, pos, len);
    assert(size > 0);  // TODO
    // assert((pCurr->m_size <= 0) || (pCurr->m_size == size));

    pos += len;  // consume length of size of element
    assert((pos + size) <= stop);  // TODO

    // Pos now points to start of payload

    pos += size;  // consume payload
  }

  long long off_next = 0;

  while (pos < stop) {
    long len;

    long long result = GetUIntLength(m_pReader, pos, len);
    assert(result == 0);
    assert((pos + len) <= stop);  // TODO
    if (result != 0)
      return NULL;

    const long long idpos = pos;  // pos of next (potential) cluster

    const long long id = ReadID(m_pReader, idpos, len);
    if (id < 0)
      return NULL;

    pos += len;  // consume ID

    // Read Size
    result = GetUIntLength(m_pReader, pos, len);
    assert(result == 0);  // TODO
    assert((pos + len) <= stop);  // TODO

    const long long size = ReadUInt(m_pReader, pos, len);
    assert(size >= 0);  // TODO

    pos += len;  // consume length of size of element
    assert((pos + size) <= stop);  // TODO

    // Pos now points to start of payload

    if (size == 0)  // weird
      continue;

    if (id == 0x0F43B675) {  // Cluster ID
      const long long off_next_ = idpos - m_start;

      long long pos_;
      long len_;

      const long status = Cluster::HasBlockEntries(this, off_next_, pos_, len_);

      assert(status >= 0);

      if (status > 0) {
        off_next = off_next_;
        break;
      }
    }

    pos += size;  // consume payload
  }

  if (off_next <= 0)
    return 0;

  Cluster** const ii = m_clusters + m_clusterCount;
  Cluster** i = ii;

  Cluster** const jj = ii + m_clusterPreloadCount;
  Cluster** j = jj;

  while (i < j) {
    // INVARIANT:
    //[0, i) < pos_next
    //[i, j) ?
    //[j, jj)  > pos_next

    Cluster** const k = i + (j - i) / 2;
    assert(k < jj);

    Cluster* const pNext = *k;
    assert(pNext);
    assert(pNext->m_index < 0);

    // const long long pos_ = pNext->m_pos;
    // assert(pos_);
    // pos = pos_ * ((pos_ < 0) ? -1 : 1);

    pos = pNext->GetPosition();

    if (pos < off_next)
      i = k + 1;
    else if (pos > off_next)
      j = k;
    else
      return pNext;
  }

  assert(i == j);

  Cluster* const pNext = Cluster::Create(this, -1, off_next);
  if (pNext == NULL)
    return NULL;

  const ptrdiff_t idx_next = i - m_clusters;  // insertion position

  if (!PreloadCluster(pNext, idx_next)) {
    delete pNext;
    return NULL;
  }
  assert(m_clusters);
  assert(idx_next < m_clusterSize);
  assert(m_clusters[idx_next] == pNext);

  return pNext;
}

long Segment::ParseNext(const Cluster* pCurr, const Cluster*& pResult,
                        long long& pos, long& len) {
  assert(pCurr);
  assert(!pCurr->EOS());
  assert(m_clusters);

  pResult = 0;

  if (pCurr->m_index >= 0) {  // loaded (not merely preloaded)
    assert(m_clusters[pCurr->m_index] == pCurr);

    const long next_idx = pCurr->m_index + 1;

    if (next_idx < m_clusterCount) {
      pResult = m_clusters[next_idx];
      return 0;  // success
    }

    // curr cluster is last among loaded

    const long result = LoadCluster(pos, len);

    if (result < 0)  // error or underflow
      return result;

    if (result > 0)  // no more clusters
    {
      // pResult = &m_eos;
      return 1;
    }

    pResult = GetLast();
    return 0;  // success
  }

  assert(m_pos > 0);

  long long total, avail;

  long status = m_pReader->Length(&total, &avail);

  if (status < 0)  // error
    return status;

  assert((total < 0) || (avail <= total));

  const long long segment_stop = (m_size < 0) ? -1 : m_start + m_size;

  // interrogate curr cluster

  pos = pCurr->m_element_start;

  if (pCurr->m_element_size >= 0)
    pos += pCurr->m_element_size;
  else {
    if ((pos + 1) > avail) {
      len = 1;
      return E_BUFFER_NOT_FULL;
    }

    long long result = GetUIntLength(m_pReader, pos, len);

    if (result < 0)  // error
      return static_cast<long>(result);

    if (result > 0)  // weird
      return E_BUFFER_NOT_FULL;

    if ((segment_stop >= 0) && ((pos + len) > segment_stop))
      return E_FILE_FORMAT_INVALID;

    if ((pos + len) > avail)
      return E_BUFFER_NOT_FULL;

    const long long id = ReadUInt(m_pReader, pos, len);

    if (id != 0x0F43B675)  // weird: not Cluster ID
      return -1;

    pos += len;  // consume ID

    // Read Size

    if ((pos + 1) > avail) {
      len = 1;
      return E_BUFFER_NOT_FULL;
    }

    result = GetUIntLength(m_pReader, pos, len);

    if (result < 0)  // error
      return static_cast<long>(result);

    if (result > 0)  // weird
      return E_BUFFER_NOT_FULL;

    if ((segment_stop >= 0) && ((pos + len) > segment_stop))
      return E_FILE_FORMAT_INVALID;

    if ((pos + len) > avail)
      return E_BUFFER_NOT_FULL;

    const long long size = ReadUInt(m_pReader, pos, len);

    if (size < 0)  // error
      return static_cast<long>(size);

    pos += len;  // consume size field

    const long long unknown_size = (1LL << (7 * len)) - 1;

    if (size == unknown_size)  // TODO: should never happen
      return E_FILE_FORMAT_INVALID;  // TODO: resolve this

    // assert((pCurr->m_size <= 0) || (pCurr->m_size == size));

    if ((segment_stop >= 0) && ((pos + size) > segment_stop))
      return E_FILE_FORMAT_INVALID;

    // Pos now points to start of payload

    pos += size;  // consume payload (that is, the current cluster)
    if (segment_stop >= 0 && pos > segment_stop)
      return E_FILE_FORMAT_INVALID;

    // By consuming the payload, we are assuming that the curr
    // cluster isn't interesting.  That is, we don't bother checking
    // whether the payload of the curr cluster is less than what
    // happens to be available (obtained via IMkvReader::Length).
    // Presumably the caller has already dispensed with the current
    // cluster, and really does want the next cluster.
  }

  // pos now points to just beyond the last fully-loaded cluster

  for (;;) {
    const long status = DoParseNext(pResult, pos, len);

    if (status <= 1)
      return status;
  }
}

long Segment::DoParseNext(const Cluster*& pResult, long long& pos, long& len) {
  long long total, avail;

  long status = m_pReader->Length(&total, &avail);

  if (status < 0)  // error
    return status;

  assert((total < 0) || (avail <= total));

  const long long segment_stop = (m_size < 0) ? -1 : m_start + m_size;

  // Parse next cluster.  This is strictly a parsing activity.
  // Creation of a new cluster object happens later, after the
  // parsing is done.

  long long off_next = 0;
  long long cluster_size = -1;

  for (;;) {
    if ((total >= 0) && (pos >= total))
      return 1;  // EOF

    if ((segment_stop >= 0) && (pos >= segment_stop))
      return 1;  // EOF

    if ((pos + 1) > avail) {
      len = 1;
      return E_BUFFER_NOT_FULL;
    }

    long long result = GetUIntLength(m_pReader, pos, len);

    if (result < 0)  // error
      return static_cast<long>(result);

    if (result > 0)  // weird
      return E_BUFFER_NOT_FULL;

    if ((segment_stop >= 0) && ((pos + len) > segment_stop))
      return E_FILE_FORMAT_INVALID;

    if ((pos + len) > avail)
      return E_BUFFER_NOT_FULL;

    const long long idpos = pos;  // absolute
    const long long idoff = pos - m_start;  // relative

    const long long id = ReadUInt(m_pReader, idpos, len);  // absolute

    if (id < 0)  // error
      return static_cast<long>(id);

    if (id == 0)  // weird
      return -1;  // generic error

    pos += len;  // consume ID

    // Read Size

    if ((pos + 1) > avail) {
      len = 1;
      return E_BUFFER_NOT_FULL;
    }

    result = GetUIntLength(m_pReader, pos, len);

    if (result < 0)  // error
      return static_cast<long>(result);

    if (result > 0)  // weird
      return E_BUFFER_NOT_FULL;

    if ((segment_stop >= 0) && ((pos + len) > segment_stop))
      return E_FILE_FORMAT_INVALID;

    if ((pos + len) > avail)
      return E_BUFFER_NOT_FULL;

    const long long size = ReadUInt(m_pReader, pos, len);

    if (size < 0)  // error
      return static_cast<long>(size);

    pos += len;  // consume length of size of element

    // Pos now points to start of payload

    if (size == 0)  // weird
      continue;

    const long long unknown_size = (1LL << (7 * len)) - 1;

    if ((segment_stop >= 0) && (size != unknown_size) &&
        ((pos + size) > segment_stop)) {
      return E_FILE_FORMAT_INVALID;
    }

    if (id == 0x0C53BB6B) {  // Cues ID
      if (size == unknown_size)
        return E_FILE_FORMAT_INVALID;

      const long long element_stop = pos + size;

      if ((segment_stop >= 0) && (element_stop > segment_stop))
        return E_FILE_FORMAT_INVALID;

      const long long element_start = idpos;
      const long long element_size = element_stop - element_start;

      if (m_pCues == NULL) {
        m_pCues = new (std::nothrow)
            Cues(this, pos, size, element_start, element_size);
        if (m_pCues == NULL)
          return false;
      }

      pos += size;  // consume payload
      if (segment_stop >= 0 && pos > segment_stop)
        return E_FILE_FORMAT_INVALID;

      continue;
    }

    if (id != 0x0F43B675) {  // not a Cluster ID
      if (size == unknown_size)
        return E_FILE_FORMAT_INVALID;

      pos += size;  // consume payload
      if (segment_stop >= 0 && pos > segment_stop)
        return E_FILE_FORMAT_INVALID;

      continue;
    }

    // We have a cluster.
    off_next = idoff;

    if (size != unknown_size)
      cluster_size = size;

    break;
  }

  assert(off_next > 0);  // have cluster

  // We have parsed the next cluster.
  // We have not created a cluster object yet.  What we need
  // to do now is determine whether it has already be preloaded
  //(in which case, an object for this cluster has already been
  // created), and if not, create a new cluster object.

  Cluster** const ii = m_clusters + m_clusterCount;
  Cluster** i = ii;

  Cluster** const jj = ii + m_clusterPreloadCount;
  Cluster** j = jj;

  while (i < j) {
    // INVARIANT:
    //[0, i) < pos_next
    //[i, j) ?
    //[j, jj)  > pos_next

    Cluster** const k = i + (j - i) / 2;
    assert(k < jj);

    const Cluster* const pNext = *k;
    assert(pNext);
    assert(pNext->m_index < 0);

    pos = pNext->GetPosition();
    assert(pos >= 0);

    if (pos < off_next)
      i = k + 1;
    else if (pos > off_next)
      j = k;
    else {
      pResult = pNext;
      return 0;  // success
    }
  }

  assert(i == j);

  long long pos_;
  long len_;

  status = Cluster::HasBlockEntries(this, off_next, pos_, len_);

  if (status < 0) {  // error or underflow
    pos = pos_;
    len = len_;

    return status;
  }

  if (status > 0) {  // means "found at least one block entry"
    Cluster* const pNext = Cluster::Create(this,
                                           -1,  // preloaded
                                           off_next);
    if (pNext == NULL)
      return -1;

    const ptrdiff_t idx_next = i - m_clusters;  // insertion position

    if (!PreloadCluster(pNext, idx_next)) {
      delete pNext;
      return -1;
    }
    assert(m_clusters);
    assert(idx_next < m_clusterSize);
    assert(m_clusters[idx_next] == pNext);

    pResult = pNext;
    return 0;  // success
  }

  // status == 0 means "no block entries found"