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 <cstring>
#include <new>
#include <climits>

mkvparser::IMkvReader::~IMkvReader()
{
}

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

long long mkvparser::ReadUInt(IMkvReader* pReader, long long pos, long& len)
{
    assert(pReader);
    assert(pos >= 0);

    int status;

//#ifdef _DEBUG
//    long long total, available;
//    status = pReader->Length(&total, &available);
//    assert(status >= 0);
//    assert((total < 0) || (available <= total));
//    assert(pos < available);
//    assert((available - pos) >= 1);  //assume here max u-int len is 8
//#endif

    len = 1;

    unsigned char b;

    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;
    }

//#ifdef _DEBUG
//    assert((available - pos) >= len);
//#endif

    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 mkvparser::GetUIntLength(
    IMkvReader* pReader,
    long long pos,
    long& len)
{
    assert(pReader);
    assert(pos >= 0);

    long long total, available;

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

    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;

    assert(status == 0);

    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
}


long long mkvparser::UnserializeUInt(
    IMkvReader* pReader,
    long long pos,
    long long size)
{
    assert(pReader);
    assert(pos >= 0);

    if ((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 mkvparser::UnserializeFloat(
    IMkvReader* pReader,
    long long pos,
    long long size_,
    double& result)
{
    assert(pReader);
    assert(pos >= 0);

    if ((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
    {
        assert(size == 8);

        union
        {
            double d;
            unsigned long long dd;
        };

        dd = 0;

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

            if (++i >= 8)
                break;

            dd <<= 8;
        }

        result = d;
    }

    return 0;
}


long mkvparser::UnserializeInt(
    IMkvReader* pReader,
    long long pos,
    long size,
    long long& result)
{
    assert(pReader);
    assert(pos >= 0);
    assert(size > 0);
    assert(size <= 8);

    {
        signed char b;

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

        if (status < 0)
            return status;

        result = b;

        ++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;
    }

    return 0;  //success
}


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

    if (size_ >= LONG_MAX)  //we need (size+1) chars
        return E_FILE_FORMAT_INVALID;

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

    str = new (std::nothrow) char[size+1];

    if (str == NULL)
        return -1;

    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[size] = '\0';

    return 0;  //success
}


long mkvparser::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 = ReadUInt(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)
        return E_FILE_FORMAT_INVALID;

    pos += len;  //consume length of size

    //pos now designates payload

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

    return 0;  //success
}


bool mkvparser::Match(
    IMkvReader* pReader,
    long long& pos,
    unsigned long id_,
    long long& val)
{
    assert(pReader);
    assert(pos >= 0);

    long long total, available;

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

    long len;

    const long long id = ReadUInt(pReader, pos, len);
    assert(id >= 0);
    assert(len > 0);
    assert(len <= 8);
    assert((pos + len) <= available);

    if ((unsigned long)id != id_)
        return false;

    pos += len;  //consume id

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

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

    val = UnserializeUInt(pReader, pos, size);
    assert(val >= 0);

    pos += size;  //consume size of payload

    return true;
}

bool mkvparser::Match(
    IMkvReader* pReader,
    long long& pos,
    unsigned long id_,
    unsigned char*& buf,
    size_t& buflen)
{
    assert(pReader);
    assert(pos >= 0);

    long long total, available;

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

    long len;
    const long long id = ReadUInt(pReader, pos, len);
    assert(id >= 0);
    assert(len > 0);
    assert(len <= 8);
    assert((pos + len) <= available);

    if ((unsigned long)id != id_)
        return false;

    pos += len;  //consume id

    const long long size_ = ReadUInt(pReader, pos, len);
    assert(size_ >= 0);
    assert(len > 0);
    assert(len <= 8);
    assert((pos + len) <= available);

    pos += len;  //consume length of size of payload
    assert((pos + size_) <= available);

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

    buf = new (std::nothrow) unsigned char[buflen_];
    assert(buf);  //TODO

    status = pReader->Read(pos, buflen_, buf);
    assert(status == 0);  //TODO

    buflen = buflen_;

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


namespace mkvparser
{

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)
{
    assert(pReader);

    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;

    assert(len > 0);
    assert(len <= 8);

    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;
    }

    assert(pos == end);
    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_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++;
        assert(p);

        delete p;
    }

    delete[] m_clusters;

    delete m_pTracks;
    delete m_pInfo;
    delete m_pCues;
    delete m_pSeekHead;
}


long long Segment::CreateInstance(
    IMkvReader* pReader,
    long long pos,
    Segment*& pSegment)
{
    assert(pReader);
    assert(pos >= 0);

    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 = ReadUInt(pReader, pos, len);

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

        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;

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

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

    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;

        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)  //underflow (weird)
            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 = ReadUInt(m_pReader, idpos, len);

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

        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)  //underflow (weird)
            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)  //error
            return size;

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

        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;
            }
        }

        m_pos = pos + size;  //consume payload
    }

    assert((segment_stop < 0) || (m_pos <= segment_stop));

    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;

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

    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 = ReadUInt(m_pReader, idpos, len);

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

        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 0  //we must handle this to support live webm
        if (size == unknown_size)
            return E_FILE_FORMAT_INVALID;  //TODO: allow this
#endif

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

#if 0  //commented-out, to support incremental cluster parsing
        len = static_cast<long>(size);

        if ((pos + size) > avail)
            return E_BUFFER_NOT_FULL;
#endif

        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 Cues(this,
                                   pos,
                                   size,
                                   idpos,
                                   element_size);
                assert(m_pCues);  //TODO
            }

            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;
    }

    assert(cluster_off >= 0);  //have cluster

    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)
    {
        assert(idx < m_clusterSize);

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

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

        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
            assert((segment_stop < 0) || (m_pos <= segment_stop));

            return 0;  //success
        }
    }

    if (status == 0)  //no entries found
    {
        if (cluster_size < 0)
            return E_FILE_FORMAT_INVALID;  //TODO: handle this

        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);
                                              //element_size);
    assert(pCluster);

    AppendCluster(pCluster);
    assert(m_clusters);
    assert(idx < m_clusterSize);
    assert(m_clusters[idx] == pCluster);

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

        m_pos = pos;
        assert((segment_stop < 0) || (m_pos <= segment_stop));

        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)

#if 0

    if (cluster_size < 0)  //unknown size
    {
        const long long payload_pos = pos;  //absolute pos of cluster payload

        for (;;)  //determine cluster size
        {
            if ((total >= 0) && (pos >= total))
                break;

            if ((segment_stop >= 0) && (pos >= segment_stop))
                break;  //no more clusters

            //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 = ReadUInt(m_pReader, idpos, len);

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

            //This is the distinguished set of ID's we use to determine
            //that we have exhausted the sub-element's inside the cluster
            //whose ID we parsed earlier.

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

            if (id == 0x0C53BB6B)  //Cues ID
                break;

            switch (id)
            {
                case 0x20:  //BlockGroup
                case 0x23:  //Simple Block
                case 0x67:  //TimeCode
                case 0x2B:  //PrevSize
                    break;

                default:
                    assert(false);
                    break;
            }

            pos += len;  //consume ID (of sub-element)

            //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 of element

            //pos now points to start of sub-element's payload

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

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

            if (size == unknown_size)
                return E_FILE_FORMAT_INVALID;  //not allowed for sub-elements

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

            pos += size;  //consume payload of sub-element
            assert((segment_stop < 0) || (pos <= segment_stop));
        }  //determine cluster size

        cluster_size = pos - payload_pos;
        assert(cluster_size >= 0);

        pos = payload_pos;  //reset and re-parse original cluster
    }

    if (m_clusterPreloadCount > 0)
    {
        assert(idx < m_clusterSize);

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

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

        if (off == cluster_off)  //preloaded already
            return E_FILE_FORMAT_INVALID;  //subtle
    }

    m_pos = pos + cluster_size;  //consume payload
    assert((segment_stop < 0) || (m_pos <= segment_stop));

    return 2;     //try to find another cluster

#endif

}


long Segment::DoLoadClusterUnknownSize(
    long long& pos,
    long& len)
{
    assert(m_pos < 0);
    assert(m_pUnknownSize);

#if 0
    assert(m_pUnknownSize->GetElementSize() < 0);  //TODO: verify this

    const long long element_start = m_pUnknownSize->m_element_start;

    pos = -m_pos;
    assert(pos > element_start);

    //We have already consumed the (cluster) ID and size fields.
    //We just need to consume the blocks and other sub-elements
    //of this cluster, until we discover the boundary.

    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;

    long long element_size = -1;

    for (;;)  //determine cluster size
    {
        if ((total >= 0) && (pos >= total))
        {
            element_size = total - element_start;
            assert(element_size > 0);

            break;
        }

        if ((segment_stop >= 0) && (pos >= segment_stop))
        {
            element_size = segment_stop - element_start;
            assert(element_size > 0);

            break;
        }

        //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 = ReadUInt(m_pReader, idpos, len);

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

        //This is the distinguished set of ID's we use to determine
        //that we have exhausted the sub-element's inside the cluster
        //whose ID we parsed earlier.

        if ((id == 0x0F43B675) || (id == 0x0C53BB6B)) //Cluster ID or Cues ID
        {
            element_size = pos - element_start;
            assert(element_size > 0);

            break;
        }

#ifdef _DEBUG
        switch (id)
        {
            case 0x20:  //BlockGroup
            case 0x23:  //Simple Block
            case 0x67:  //TimeCode
            case 0x2B:  //PrevSize
                break;

            default:
                assert(false);
                break;
        }
#endif

        pos += len;  //consume ID (of sub-element)

        //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 of element

        //pos now points to start of sub-element's payload

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

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

        if (size == unknown_size)
            return E_FILE_FORMAT_INVALID;  //not allowed for sub-elements

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

        pos += size;  //consume payload of sub-element
        assert((segment_stop < 0) || (pos <= segment_stop));
    }  //determine cluster size

    assert(element_size >= 0);

    m_pos = element_start + element_size;
    m_pUnknownSize = 0;

    return 2;  //continue parsing
#else
    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

    assert(status > 0);   //nothing left to parse of this cluster

    const long long start = m_pUnknownSize->m_element_start;

    const long long size = m_pUnknownSize->GetElementSize();
    assert(size >= 0);

    pos = start + size;
    m_pos = pos;

    m_pUnknownSize = 0;

    return 2;  //continue parsing
#endif
}


void Segment::AppendCluster(Cluster* pCluster)
{
    assert(pCluster);
    assert(pCluster->m_index >= 0);

    const long count = m_clusterCount + m_clusterPreloadCount;

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

    const long idx = pCluster->m_index;
    assert(idx == m_clusterCount);

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

        Cluster** const qq = new Cluster*[n];
        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)
    {
        assert(m_clusters);

        Cluster** const p = m_clusters + m_clusterCount;
        assert(*p);
        assert((*p)->m_index < 0);

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

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

            *q = *qq;
            q = qq;

            if (q == p)
                break;
        }
    }

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


void 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 Cluster*[n];
        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;
}


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;

    assert(m_pInfo);
    assert(m_pTracks);

    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
        assert(pos <= stop);
    }

    assert(pos == stop);

    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
        assert(pos <= stop);
    }

    assert(pos == stop);

    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;
}


#if 0
void Segment::ParseCues(long long off)
{
    if (m_pCues)
        return;

    //odbgstream os;
    //os << "Segment::ParseCues (begin)" << endl;

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

    long len;

    long long result = GetUIntLength(m_pReader, pos, len);
    assert(result == 0);
    assert((pos + len) <= stop);

    const long long idpos = pos;

    const long long id = ReadUInt(m_pReader, idpos, len);
    assert(id == 0x0C53BB6B);  //Cues ID

    pos += len;  //consume ID
    assert(pos < stop);

    //Read Size

    result = GetUIntLength(m_pReader, pos, len);
    assert(result == 0);
    assert((pos + len) <= stop);

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

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

    const long long element_size = size + pos - element_start;

    //Pos now points to start of payload

    m_pCues = new Cues(this, pos, size, element_start, element_size);
    assert(m_pCues);  //TODO

    //os << "Segment::ParseCues (end)" << endl;
}
#else
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 = ReadUInt(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);
    assert(m_pCues);  //TODO

    return 0;  //success
}
#endif


#if 0
void Segment::ParseSeekEntry(
    long long start,
    long long size_)
{
    long long pos = start;

    const long long stop = start + size_;

    long len;

    const long long seekIdId = ReadUInt(m_pReader, pos, len);
    //seekIdId;
    assert(seekIdId == 0x13AB);  //SeekID ID
    assert((pos + len) <= stop);

    pos += len;  //consume id

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

    pos += len;  //consume size

    const long long seekId = ReadUInt(m_pReader, pos, len);  //payload
    assert(seekId >= 0);
    assert(len == seekIdSize);
    assert((pos + len) <= stop);

    pos += seekIdSize;  //consume payload

    const long long seekPosId = ReadUInt(m_pReader, pos, len);
    //seekPosId;
    assert(seekPosId == 0x13AC);  //SeekPos ID
    assert((pos + len) <= stop);

    pos += len;  //consume id

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

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

    const long long seekOff = UnserializeUInt(m_pReader, pos, seekPosSize);
    assert(seekOff >= 0);
    assert(seekOff < m_size);

    pos += seekPosSize;  //consume payload
    assert(pos == stop);

    const long long seekPos = m_start + seekOff;
    assert(seekPos < (m_start + m_size));

    if (seekId == 0x0C53BB6B)  //Cues ID
        ParseCues(seekOff);
}
#else
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 = ReadUInt(pReader, pos, len);
    //seekIdId;

    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;
}
#endif


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);
}


void Cues::Init() const
{
    if (m_cue_points)
        return;

    assert(m_count == 0);
    assert(m_preload_count == 0);

    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 = ReadUInt(pReader, pos, len);
        assert(id >= 0);  //TODO
        assert((pos + len) <= stop);

        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 == 0x3B)  //CuePoint ID
            PreloadCuePoint(cue_points_size, idpos);

        pos += size;  //consume payload
        assert(pos <= stop);
    }
}


void Cues::PreloadCuePoint(
    long& cue_points_size,
    long long pos) const
{
    assert(m_count == 0);

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

        CuePoint** const qq = new CuePoint*[n];
        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 CuePoint(m_preload_count, pos);
    m_cue_points[m_preload_count++] = pCP;
}


bool Cues::LoadCuePoint() const
{
    //odbgstream os;
    //os << "Cues::LoadCuePoint" << endl;

    const long long stop = m_start + m_size;

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

    Init();

    IMkvReader* const pReader = m_pSegment->m_pReader;

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

        long len;

        const long long id = ReadUInt(pReader, m_pos, len);
        assert(id >= 0);  //TODO
        assert((m_pos + len) <= stop);

        m_pos += len;  //consume ID

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

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

        if (id != 0x3B)  //CuePoint ID
        {
            m_pos += size;  //consume payload
            assert(m_pos <= stop);

            continue;
        }

        assert(m_preload_count > 0);

        CuePoint* const pCP = m_cue_points[m_count];
        assert(pCP);
        assert((pCP->GetTimeCode() >= 0) || (-pCP->GetTimeCode() == idpos));

        pCP->Load(pReader);
        ++m_count;
        --m_preload_count;

        m_pos += size;  //consume payload
        assert(m_pos <= stop);

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

    //return (m_pos < stop);
    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
{
    assert(time_ns >= 0);
    assert(pTrack);

#if 0
    LoadCuePoint();  //establish invariant

    assert(m_cue_points);
    assert(m_count > 0);

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

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

    pCP = *i;
    assert(pCP);

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

    IMkvReader* const pReader = m_pSegment->m_pReader;

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

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

        CuePoint* const pCP = *k;
        assert(pCP);

        pCP->Load(pReader);

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

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

        assert(i <= j);
    }

    assert(i == j);
    assert(i <= jj);
    assert(i > ii);

    pCP = *--i;
    assert(pCP);
    assert(pCP->GetTime(m_pSegment) <= time_ns);
#else
    if (m_cue_points == NULL)
        return false;

    if (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;
    assert(pCP);

    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;
        assert(k < jj);

        CuePoint* const pCP = *k;
        assert(pCP);

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

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

        assert(i <= j);
    }

    assert(i == j);
    assert(i <= jj);
    assert(i > ii);

    pCP = *--i;
    assert(pCP);
    assert(pCP->GetTime(m_pSegment) <= time_ns);
#endif

    //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);
}


#if 0
bool Cues::FindNext(
    long long time_ns,
    const Track* pTrack,
    const CuePoint*& pCP,
    const CuePoint::TrackPosition*& pTP) const
{
    pCP = 0;
    pTP = 0;