// SPDX-License-Identifier: BSD-3-Clause

// Copyright (c) Contributors to the OpenEXR Project.

//-----------------------------------------------------------------------------

//

//        ID Manifest class implementation

//

//-----------------------------------------------------------------------------

#include "ImfIO.h"

#include "ImfXdr.h"

#include <Iex.h>

#include <ImfIDManifest.h>

#include <openexr_compression.h>

#include <algorithm>

#include <stdint.h>

#include <stdlib.h>

#include <string.h>

//

// debugging only

//

#ifdef DUMP_TABLE

#    include <iostream>

#endif

OPENEXR_IMF_INTERNAL_NAMESPACE_SOURCE_ENTER

using namespace OPENEXR_IMF_INTERNAL_NAMESPACE;

using std::fill;

using std::make_pair;

using std::map;

using std::pair;

using std::set;

using std::sort;

using std::string;

using std::vector;

const std::string IDManifest::UNKNOWN        = "unknown";

const std::string IDManifest::NOTHASHED      = "none";

const std::string IDManifest::CUSTOMHASH     = "custom";

const std::string IDManifest::MURMURHASH3_32 = "MurmurHash3_32";

const std::string IDManifest::MURMURHASH3_64 = "MurmurHash3_64";

const std::string IDManifest::ID_SCHEME  = "id";

const std::string IDManifest::ID2_SCHEME = "id2";

IDManifest::IDManifest ()

{}

namespace

{

// map of strings to index of string in table

typedef std::map<std::string, int> indexedStringSet;

// when handling vectors/sets of strings, the string is got by dereferencing the pointer/iterator

template <class T>

size_t

stringSize (const T& i)

{

    return i->size ();

}

Unexecuted instantiation: ImfIDManifest.cpp:unsigned long Imf_3_3::(anonymous namespace)::stringSize<std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const*> >(std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const*> const&)

Unexecuted instantiation: ImfIDManifest.cpp:unsigned long Imf_3_3::(anonymous namespace)::stringSize<std::__1::__tree_const_iterator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::__tree_node<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, void*>*, long> >(std::__1::__tree_const_iterator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::__tree_node<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, void*>*, long> const&)

template <class T>

const char*

cStr (const T& i)

{

    return i->c_str ();

}

Unexecuted instantiation: ImfIDManifest.cpp:char const* Imf_3_3::(anonymous namespace)::cStr<std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const*> >(std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const*> const&)

Unexecuted instantiation: ImfIDManifest.cpp:char const* Imf_3_3::(anonymous namespace)::cStr<std::__1::__tree_const_iterator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::__tree_node<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, void*>*, long> >(std::__1::__tree_const_iterator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::__tree_node<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, void*>*, long> const&)

/*

    // but for indexedStringSet the string is the first of the iterator pair

    size_t stringSize(indexedStringSet::const_iterator &i )

    {

        return i->first.size();

    }

    const char* cStr(indexedStringSet::const_iterator &i)

    {

       return i->first.c_str();

    }

    */

size_t

getVariableLengthIntegerSize (uint64_t value)

{

    if (value < 1llu << 7) { return 1; }

    if (value < 1llu << 14) { return 2; }

    if (value < 1llu << 21) { return 3; }

    if (value < 1llu << 28) { return 4; }

    if (value < 1llu << 35) { return 5; }

    if (value < 1llu << 42) { return 6; }

    if (value < 1llu << 49) { return 7; }

    if (value < 1llu << 56) { return 8; }

    if (value < 1llu << 63) { return 9; }

    return 10;

}

uint64_t

readVariableLengthInteger (const char*& readPtr, const char* endPtr)

{

    // bytes are stored LSB first, so each byte that is read from the stream must be

    // shifted before mixing into the existing length

    int           shift = 0;

    unsigned char byte  = 0;

    uint64_t      value = 0;

    do

    {

        if (readPtr >= endPtr)

        {

            throw IEX_NAMESPACE::InputExc (

                "IDManifest too small for variable length integer");

        }

        // Each chunk contributes at most 7 bits; shifts must stay < 64 or

        // (byte & 127) << shift has undefined behavior (C++).

        if (shift >= 64)

        {

            throw IEX_NAMESPACE::InputExc (

                "Invalid variable-length integer in IDManifest");

        }

        byte = *(unsigned char*) readPtr++;

        // top bit of byte isn't part of actual number, it just indicates there's more info to come

        // so take bottom 7 bits, shift them to the right place, and insert them

        //

        value |= (uint64_t (byte & 127)) << shift;

        shift += 7;

    } while (byte &

             128); //while top bit set on previous byte, there is more to come

    return value;

}

void

writeVariableLengthInteger (char*& outPtr, uint64_t value)

{

    do

    {

        unsigned char byte = (unsigned char) (value & 127);

        value >>= 7;

        if (value > 0) { byte |= 128; }

        *(unsigned char*) outPtr++ = byte;

    } while (value > 0);

}

//

// read a list of strings into the given container

// format is:

// numberOfStrings (unless numberOfStrings already passed in)

//  length of string 0

//  length of string 1

//  ...

//  string 0

//  string 1

//  ...

//  (the sizes come first then the strings because that helps compression performance)

//  note - updates readPtr to point to first byte after readStrings

//

template <class T>

void

readStringList (

    const char*& readPtr,

    const char*  endPtr,

    T&           outputVector,

    int          numberOfStrings = 0)

{

    if (numberOfStrings == 0)

    {

        if (readPtr + 4 > endPtr)

        {

            throw IEX_NAMESPACE::InputExc (

                "IDManifest too small for string list size");

        }

        Xdr::read<CharPtrIO> (readPtr, numberOfStrings);

    }

    vector<size_t> lengths (numberOfStrings);

    for (int i = 0; i < numberOfStrings; ++i)

    {

        lengths[i] = readVariableLengthInteger (readPtr, endPtr);

    }

    for (int i = 0; i < numberOfStrings; ++i)

    {

        if (readPtr + lengths[i] > endPtr)

        {

            throw IEX_NAMESPACE::InputExc ("IDManifest too small for string");

        }

        outputVector.insert (outputVector.end (), string (readPtr, lengths[i]));

        readPtr += lengths[i];

    }

}

Unexecuted instantiation: ImfIDManifest.cpp:void Imf_3_3::(anonymous namespace)::readStringList<std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >(char const*&, char const*, std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > >&, int)

Unexecuted instantiation: ImfIDManifest.cpp:void Imf_3_3::(anonymous namespace)::readStringList<std::__1::set<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >(char const*&, char const*, std::__1::set<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > >&, int)

//

// computes number of bytes required to serialize vector/set of strings

//

template <typename T>

int

getStringListSize (const T& stringList, size_t entries = 0)

{

    int totalSize = 0;

    if (entries == 0)

    {

        totalSize += 4; // 4 bytes to store number of entries;

    }

    else

    {

        if (stringList.size () != entries)

        {

            throw IEX_NAMESPACE::InputExc (

                "Incorrect number of components stored in ID Manifest");

        }

    }

    for (typename T::const_iterator i = stringList.begin ();

         i != stringList.end ();

         ++i)

    {

        size_t length = stringSize (i);

        totalSize += length;

        // up to five bytes for variable length encoded size

        totalSize += getVariableLengthIntegerSize (length);

    }

    return totalSize;

}

Unexecuted instantiation: ImfIDManifest.cpp:int Imf_3_3::(anonymous namespace)::getStringListSize<std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >(std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > const&, unsigned long)

Unexecuted instantiation: ImfIDManifest.cpp:int Imf_3_3::(anonymous namespace)::getStringListSize<std::__1::set<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >(std::__1::set<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > const&, unsigned long)

//

// write string list to outPtr. if entries nonzero, omits number of entries,

// but confirms 'entries' == T.size()

//

template <typename T>

void

writeStringList (char*& outPtr, const T& stringList, int entries = 0)

{

    int size = stringList.size ();

    if (entries == 0) { Xdr::write<CharPtrIO> (outPtr, size); }

    else

    {

        if (size != entries)

        {

            throw IEX_NAMESPACE::InputExc (

                "Incorrect number of components stored in ID Manifest");

        }

    }

    for (typename T::const_iterator i = stringList.begin ();

         i != stringList.end ();

         ++i)

    {

        int stringLength = stringSize (i);

        //

        // variable length encoding:

        // values between 0 and 127 inclusive are stored in a single byte

        // values between 128 and 16384 are encoded with two bytes: 1LLLLLLL 0MMMMMMMM where L and M are the least and most significant bits of the value

        // in general, values are stored least significant values first, with the top bit of each byte indicating more values follow

        // the top bit is clear in the last byte of the value

        // (this scheme requires two bytes to store values above 1<<7, and five bytes to store values above 1<<28)

        //

        writeVariableLengthInteger (outPtr, stringLength);

    }

    for (typename T::const_iterator i = stringList.begin ();

         i != stringList.end ();

         ++i)

    {

        int stringLength = stringSize (i);

        Xdr::write<CharPtrIO> (outPtr, (const char*) cStr (i), stringLength);

    }

}

Unexecuted instantiation: ImfIDManifest.cpp:void Imf_3_3::(anonymous namespace)::writeStringList<std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >(char*&, std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > const&, int)

Unexecuted instantiation: ImfIDManifest.cpp:void Imf_3_3::(anonymous namespace)::writeStringList<std::__1::set<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >(char*&, std::__1::set<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > const&, int)

int

getStringSize (const string& str)

{

    return 4 + str.size ();

}

void

readPascalString (

    const char*& readPtr, const char* endPtr, string& outputString)

{

    if (readPtr + 4 > endPtr)

    {

        throw IEX_NAMESPACE::InputExc ("IDManifest too small for string size");

    }

    unsigned int length = 0;

    Xdr::read<CharPtrIO> (readPtr, length);

    if (readPtr + length > endPtr)

    {

        throw IEX_NAMESPACE::InputExc ("IDManifest too small for string");

    }

    outputString = string ((const char*) readPtr, length);

    readPtr += length;

}

void

writePascalString (char*& outPtr, const string& str)

{

    unsigned int length = str.size ();

    Xdr::write<CharPtrIO> ((char*&) outPtr, length);

    Xdr::write<CharPtrIO> ((char*&) outPtr, (const char*) str.c_str (), length);

}

} // namespace

IDManifest::IDManifest (const char* data, const char* endOfData)

{

    init (data, endOfData);

}

void

IDManifest::init (const char* data, const char* endOfData)

{

    unsigned int version;

    Xdr::read<CharPtrIO> (data, version);

    if (version != 0)

    {

        throw IEX_NAMESPACE::InputExc ("Unrecognized IDmanifest version");

    }

    //

    // first comes list of all strings used in manifest

    //

    vector<string> stringList;

    readStringList (data, endOfData, stringList);

    //

    // expand the strings in the stringlist

    // each string begins with number of characters to copy from the previous string

    // the remainder is the 'new' bit that appears after that

    //

    for (size_t i = 1; i < stringList.size (); ++i)

    {

        size_t common; // number of characters in common with previous string

        int    stringStart = 1; // first character of string itself;

        //

        // previous string had more than 255 characters?

        //

        const size_t minPrefixLen =

            stringList[i - 1].size () > 255 ? size_t (2) : size_t (1);

        if (stringList[i].size () < minPrefixLen)

        {

            throw IEX_NAMESPACE::InputExc (

                "IDManifest string too small for common prefix length");

        }

        if (stringList[i - 1].size () > 255)

        {

            common = size_t (((unsigned char) (stringList[i][0])) << 8) +

                     size_t ((unsigned char) (stringList[i][1]));

            stringStart = 2;

        }

        else { common = (unsigned char) stringList[i][0]; }

        if (common > stringList[i - 1].size ())

        {

            throw IEX_NAMESPACE::InputExc (

                "Bad common string length in IDmanifest string table");

        }

        stringList[i] = stringList[i - 1].substr (0, common) +

                        stringList[i].substr (stringStart);

    }

    //

    // decode mapping table from indices in table to indices in string list

    // the mapping uses smaller indices for more commonly occurring strings, since these are encoded with fewer bits

    // comments in serialize function describe the format

    //

    vector<int> mapping (stringList.size ());

    //

    // overlapping sequences: A list [(4,5),(3,6)] expands to 4,5,3,6 - because 4 and 5 are including already

    // they are not included again

    // the 'seen' list indicates which values have already been used, so they are not re-referenced

    //

    vector<char> seen (stringList.size ());

    int rleLength;

    if (endOfData < data + 4)

    {

        throw IEX_NAMESPACE::InputExc ("IDManifest too small");

    }

    Xdr::read<CharPtrIO> (data, rleLength);

    int currentIndex = 0;

    for (int i = 0; i < rleLength; ++i)

    {

        int first;

        int last;

        if (endOfData < data + 8)

        {

            throw IEX_NAMESPACE::InputExc ("IDManifest too small");

        }

        Xdr::read<CharPtrIO> (data, first);

        Xdr::read<CharPtrIO> (data, last);

        if (first < 0 || last < 0 || first > last ||

            first >= int (stringList.size ()) ||

            last >= int (stringList.size ()))

        {

            throw IEX_NAMESPACE::InputExc (

                "Bad mapping table entry in IDManifest");

        }

        for (int entry = first; entry <= last; entry++)

        {

            // don't remap already mapped values

            if (seen[entry] == 0)

            {

                mapping[currentIndex] = entry;

                seen[entry]           = 1;

                currentIndex++;

            }

        }

    }

#ifdef DUMP_TABLE

    //

    // dump mapping table for debugging

    //

    for (size_t i = 0; i < mapping.size (); ++i)

    {

        std::cout << i << ' ' << mapping[i] << std::endl;

    }

#endif

    //

    // number of manifest entries comes after string list

    //

    int manifestEntries;

    if (endOfData < data + 4)

    {

        throw IEX_NAMESPACE::InputExc ("IDManifest too small");

    }

    Xdr::read<CharPtrIO> (data, manifestEntries);

    _manifest.clear ();

    _manifest.resize (manifestEntries);

    for (int manifestEntry = 0; manifestEntry < manifestEntries;

         ++manifestEntry)

    {

        ChannelGroupManifest& m = _manifest[manifestEntry];

        //

        // read header of this manifest entry

        //

        readStringList (data, endOfData, m._channels);

        readStringList (data, endOfData, m._components);

        char lifetime;

        if (endOfData < data + 4)

        {

            throw IEX_NAMESPACE::InputExc ("IDManifest too small");

        }

        Xdr::read<CharPtrIO> (data, lifetime);

        m.setLifetime (IdLifetime (lifetime));

        readPascalString (data, endOfData, m._hashScheme);

        readPascalString (data, endOfData, m._encodingScheme);

        if (endOfData < data + 5)

        {

            throw IEX_NAMESPACE::InputExc ("IDManifest too small");

        }

        char storageScheme;

        Xdr::read<CharPtrIO> (data, storageScheme);

        int tableSize;

        Xdr::read<CharPtrIO> (data, tableSize);

        uint64_t previousId = 0;

        for (int entry = 0; entry < tableSize; ++entry)

        {

            uint64_t id;

            switch (storageScheme)

            {

                case 0: {

                    if (endOfData < data + 8)

                    {

                        throw IEX_NAMESPACE::InputExc ("IDManifest too small");

                    }

                    Xdr::read<CharPtrIO> (data, id);

                    break;

                }

                case 1: {

                    if (endOfData < data + 4)

                    {

                        throw IEX_NAMESPACE::InputExc ("IDManifest too small");

                    }

                    unsigned int id32;

                    Xdr::read<CharPtrIO> (data, id32);

                    id = id32;

                    break;

                }

                default: {

                    id = readVariableLengthInteger (data, endOfData);

                }

            }

            id += previousId;

            previousId = id;

            //

            // insert into table - insert tells us if it was already there

            //

            pair<map<uint64_t, vector<string>>::iterator, bool> insertion =

                m._table.insert (make_pair (id, vector<string> ()));

            if (insertion.second == false)

            {

                throw IEX_NAMESPACE::InputExc (

                    "ID manifest contains multiple entries for the same ID");

            }

            (insertion.first)->second.resize (m.getComponents ().size ());

            for (size_t i = 0; i < m.getComponents ().size (); ++i)

            {

                int stringIndex = readVariableLengthInteger (data, endOfData);

                if (size_t (stringIndex) > stringList.size () ||

                    stringIndex < 0)

                {

                    throw IEX_NAMESPACE::InputExc (

                        "Bad string index in IDManifest");

                }

                (insertion.first)->second[i] = stringList[mapping[stringIndex]];

            }

        }

    }

}

IDManifest::IDManifest (const CompressedIDManifest& compressed)

{

    //

    // decompress the compressed manifest

    //

    vector<char> uncomp (compressed._uncompressedDataSize);

    size_t       outSize;

    size_t       inSize = static_cast<size_t> (compressed._compressedDataSize);

    if (EXR_ERR_SUCCESS != exr_uncompress_buffer (

                               nullptr,

                               compressed._data,

                               inSize,

                               uncomp.data (),

                               compressed._uncompressedDataSize,

                               &outSize))

    {

        throw IEX_NAMESPACE::InputExc (

            "IDManifest decompression (zlib) failed.");

    }

    if (outSize != compressed._uncompressedDataSize)

    {

        throw IEX_NAMESPACE::InputExc (

            "IDManifest decompression (zlib) failed: mismatch in decompressed data size");

    }

    init ((const char*) &uncomp[0], (const char*) &uncomp[0] + outSize);

}

void

IDManifest::serialize (std::vector<char>& data) const

{

    indexedStringSet stringSet;

    //

    // build string map - this turns unique strings into indices

    // the manifest stores the string indices - this allows duplicated

    // strings to point to the same place

    // grabs all the strings regardless of which manifest/mapping they are in

    //

    // at this point we just count the manifest entries

    //

    {

        //

        // over each channel group

        //

        for (size_t m = 0; m < _manifest.size (); ++m)

        {

            // over each mapping

            for (IDManifest::ChannelGroupManifest::IDTable::const_iterator i =

                     _manifest[m]._table.begin ();

                 i != _manifest[m]._table.end ();

                 ++i)

            {

                // over each string in the mapping

                for (size_t s = 0; s < i->second.size (); ++s)

                {

                    stringSet[i->second[s]]++;

                }

            }

        }

    }

    //

    // build compressed string representation - all but first string starts with number of characters to copy from previous string.

    // max 65535 bytes - use two bytes to store if previous string was more than 255 characters, big endian

    //

    vector<string> prefixedStringList (stringSet.size ());

    //

    // also make a sorted list so the most common entry appears first. Keep equally likely entries in numerical order

    //

    vector<pair<int, int>> sortedIndices (stringSet.size ());

    string prevString;

    int    index = 0;

    for (indexedStringSet::iterator i = stringSet.begin ();

         i != stringSet.end ();

         ++i)

    {

        // no prefix on first string - map stores index of each string, so use that rather than a counter;

        if (index == 0) { prefixedStringList[index] = i->first; }

        else

        {

            size_t common = 0;

            while (common < 65535 && common < prevString.size () &&

                   common < i->first.size () &&

                   prevString[common] == i->first[common])

            {

                ++common;

            }

            if (prevString.size () > 255)

            {

                //

                // long previous string - use two bytes to encode number of common chars

                //

                prefixedStringList[index] = string (1, char (common >> 8)) +

                                            string (1, char (common & 255)) +

                                            i->first.substr (common);

            }

            else

            {

                prefixedStringList[index] =

                    string (1, char (common)) + i->first.substr (common);

            }

        }

        prevString = i->first;

        sortedIndices[index].first =

            -i->second; // use negative of count so largest count appears first

        sortedIndices[index].second = index;

        //

        // also, repurpose stringSet so that it maps from string names to indices in the string table

        //

        i->second = index;

        index++;

    }

    sort (sortedIndices.begin (), sortedIndices.end ());

    //

    // the first 1<<7 characters will all be encoded with 1 byte, regardless of how common they are

    // the next 1<<14 characters will be encoded with 2 bytes

    // (a full huffman encode would do this at the bit level, not the byte level)

    //

    // the mapping table can be reduced in size by rewriting the IDs to exploit that

    // can rearrange the IDs to have more long runs by sorting numbers

    // that will need the same number of bytes to encode together

    //

    {

        size_t i = 0;

        for (; i < sortedIndices.size () && i < 1 << 7; ++i)

        {

            sortedIndices[i].first = 1;

        }

        for (; i < sortedIndices.size () && i < 1 << 14; ++i)

        {

            sortedIndices[i].first = 2;

        }

        for (; i < sortedIndices.size () && i < 1 << 21; ++i)

        {

            sortedIndices[i].first = 3;

        }

        for (; i < sortedIndices.size () && i < 1 << 28; ++i)

        {

            sortedIndices[i].first = 4;

        }

        for (; i < sortedIndices.size (); ++i)

        {

            sortedIndices[i].first = 5;

        }

    }

    sort (sortedIndices.begin (), sortedIndices.end ());

    vector<int> stringIndices (sortedIndices.size ());

    //

    // table will be stored with RLE encoding - store pairs of 'start index,end index'

    // so, the sequence 10,11,12,1,2,3,4  is stored as [ (10,12) , (1,4)]

    //

    // sequential IDs ignore already referenced IDs, so the sequence  11,9,10,12,13 can be stored as [ (11,11) , (9,13)]

    // on reading, don't reference an entry that has already been seen

    // on writing, need to track which entries have already been stored to allow this overlapping to occur

    //

    vector<pair<int, int>> RLEmapping;

    if (sortedIndices.size () > 0)

    {

        RLEmapping.resize (1);

        RLEmapping[0].first  = sortedIndices[0].second;

        RLEmapping[0].second = sortedIndices[0].second;

        fill (stringIndices.begin (), stringIndices.end (), -1);

        stringIndices[sortedIndices[0].second] = 0;

        //

        // as the loop below runs, nextToInclude tracks the value that can be merged with the current run length

        // (RLWmapping.back()) - generally this is on more than the current length, but it jumps forward

        // over values already seen

        //

        int nextToInclude = stringIndices[sortedIndices[0].second] + 1;

        for (size_t i = 1; i < sortedIndices.size (); ++i)

        {

            if (sortedIndices[i].second == nextToInclude)

            {

                //

                // this index can be treated as part of the current run, so extend the run to include it

                //

                RLEmapping.back ().second = sortedIndices[i].second;

            }

            else

            {

                pair<int, int> newEntry (

                    sortedIndices[i].second, sortedIndices[i].second);

                RLEmapping.push_back (newEntry);

            }

            // build mapping for this entry

            stringIndices[sortedIndices[i].second] = i;

            // what would the next entry have to be to be included in this run

            // skip over already mapped strings

            nextToInclude = sortedIndices[i].second + 1;

            while (nextToInclude < int (stringIndices.size ()) &&

                   stringIndices[nextToInclude] >= 0)

            {

                nextToInclude++;

            }

        }

    }

#ifdef DUMP_TABLE

    // dump RLE table for debugging

    for (size_t i = 1; i < sortedIndices.size (); ++i)

    {

        std::cout << i << ' ' << sortedIndices[i].second << std::endl;

    }

#endif

    // now compute size of uncompressed memory block for serialization

    int outputSize =

        8; // at least need four bytes for integer to store number of channel manifests, plus four bytes to indicate version pattern

    outputSize += getStringListSize (prefixedStringList);

    //

    // RLE mapping table size - number of entries followed by eight bytes for each run length

    //

    outputSize += RLEmapping.size () * 8 + 4;

    //

    // track which storage scheme is optimal for storing the IDs of each type

    // ID storage scheme: 0 = 8 bytes per ID, 1 = 4 bytes per ID, 2 = variable

    //

    std::vector<char> storageSchemes;

    for (size_t groupNumber = 0; groupNumber < _manifest.size (); ++groupNumber)

    {

        const ChannelGroupManifest& m = _manifest[groupNumber];

        outputSize += getStringListSize (m._channels); //size of channel group

        outputSize +=

            getStringListSize (m._components); //size of component list

        outputSize += 1;                       //size of lifetime enum

        outputSize += getStringSize (m._hashScheme);

        outputSize += getStringSize (m._encodingScheme);

        outputSize += 1; // ID scheme

        outputSize +=

            4; // size of storage for number of 32 bit entries in ID table

        uint64_t previousId                 = 0;

        uint64_t IdStorageForVariableScheme = 0;

        bool     canUse32Bits               = true;

        for (IDManifest::ChannelGroupManifest::IDTable::const_iterator i =

                 m._table.begin ();

             i != m._table.end ();

             ++i)

        {

            uint64_t idToStore = i->first - previousId;

            IdStorageForVariableScheme +=

                getVariableLengthIntegerSize (idToStore);

            if (idToStore >= 1llu << 32) { canUse32Bits = false; }

            previousId = i->first;

            for (size_t s = 0; s < m._components.size (); ++s)

            {

                int stringID  = stringSet[i->second[s]];

                int idToWrite = stringIndices[stringID];

                outputSize += getVariableLengthIntegerSize (idToWrite);

            }

        }

        // pick best scheme to use to store IDs

        if (canUse32Bits)

        {

            if (IdStorageForVariableScheme < m._table.size () * 4)

            {

                //

                // variable storage smaller than fixed 32 bit, so use that

                //

                storageSchemes.push_back (2);

                outputSize += IdStorageForVariableScheme;

            }

            else

            {

                //

                // variable scheme bigger than fixed 32 bit, but all ID differences fit into 32 bits

                //

                storageSchemes.push_back (1);

                outputSize += m._table.size () * 4;

            }

        }

        else

        {

            if (IdStorageForVariableScheme < m._table.size () * 8)

            {

                //

                // variable storage smaller than fixed 64 bit, so use that

                //

                storageSchemes.push_back (2);

                outputSize += IdStorageForVariableScheme;

            }

            else

            {

                //

                // variable scheme bigger than fixed 64 bit, and some ID differences bigger than 32 bit

                //

                storageSchemes.push_back (0);

                outputSize += m._table.size () * 8;

            }

        }

    }

    //

    // resize output array

    //

    data.resize (outputSize);

    //

    // populate output array

    //

    char* outPtr = &data[0];

    //

    // zeroes to indicate this is version 0 of the header

    //

    Xdr::write<CharPtrIO> (outPtr, int (0));

    //

    // table of strings

    //

    writeStringList (outPtr, prefixedStringList);

    //

    // RLE block

    //

    Xdr::write<CharPtrIO> (outPtr, int (RLEmapping.size ()));

    for (size_t i = 0; i < RLEmapping.size (); ++i)

    {

        Xdr::write<CharPtrIO> (outPtr, RLEmapping[i].first);

        Xdr::write<CharPtrIO> (outPtr, RLEmapping[i].second);

    }

    //

    // number of manifests

    //

    Xdr::write<CharPtrIO> (outPtr, int (_manifest.size ()));

    int manifestIndex = 0;

    for (size_t groupNumber = 0; groupNumber < _manifest.size (); ++groupNumber)

    {

        const ChannelGroupManifest& m = _manifest[groupNumber];

        //

        // manifest header

        //

        writeStringList (outPtr, m._channels);

        writeStringList (outPtr, m._components);

        Xdr::write<CharPtrIO> (outPtr, char (m._lifeTime));

        writePascalString (outPtr, m._hashScheme);

        writePascalString (outPtr, m._encodingScheme);

        char scheme = storageSchemes[manifestIndex];