Logo Search packages:      
Sourcecode: qpdf version File versions  Download package

QPDF_linearization.cc

// See doc/linearization.

#include <qpdf/QPDF.hh>

#include <qpdf/QPDFExc.hh>
#include <qpdf/QTC.hh>
#include <qpdf/QUtil.hh>
#include <qpdf/PCRE.hh>
#include <qpdf/Pl_Buffer.hh>
#include <qpdf/Pl_Flate.hh>
#include <qpdf/Pl_Count.hh>
#include <qpdf/BitWriter.hh>
#include <qpdf/BitStream.hh>

#include <iostream>
#include <algorithm>
#include <assert.h>
#include <math.h>
#include <string.h>

template <class T>
static void
load_vector_int(BitStream& bit_stream, int nitems, std::vector<T>& vec,
            int bits_wanted, int T::*field)
{
    // nitems times, read bits_wanted from the given bit stream,
    // storing results in the ith vector entry.

    for (int i = 0; i < nitems; ++i)
    {
      vec[i].*field = bit_stream.getBits(bits_wanted);
    }
    // The PDF spec says that each hint table starts at a byte
    // boundary.  Each "row" actually must start on a byte boundary.
    bit_stream.skipToNextByte();
}

template <class T>
static void
load_vector_vector(BitStream& bit_stream,
               int nitems1, std::vector<T>& vec1, int T::*nitems2,
               int bits_wanted, std::vector<int> T::*vec2)
{
    // nitems1 times, read nitems2 (from the ith element of vec1) items
    // into the vec2 vector field of the ith item of vec1.
    for (int i1 = 0; i1 < nitems1; ++i1)
    {
      for (int i2 = 0; i2 < vec1[i1].*nitems2; ++i2)
      {
          (vec1[i1].*vec2).push_back(bit_stream.getBits(bits_wanted));
      }
    }
    bit_stream.skipToNextByte();
}

bool
QPDF::checkLinearization()
{
    bool result = false;
    try
    {
      readLinearizationData();
      result = checkLinearizationInternal();
    }
    catch (QPDFExc& e)
    {
      std::cout << e.what() << std::endl;
    }
    return result;
}

bool
QPDF::isLinearized()
{
    // If the first object in the file is a dictionary with a suitable
    // /Linearized key and has an /L key that accurately indicates the
    // file size, initialize this->lindict and return true.

    // A linearized PDF spec's first object will be contained within
    // the first 1024 bytes of the file and will be a dictionary with
    // a valid /Linearized key.  This routine looks for that and does
    // no additional validation.

    // The PDF spec says the linearization dictionary must be
    // completely contained within the first 1024 bytes of the file.
    // Add a byte for a null terminator.
    static int const tbuf_size = 1025;

    char* buf = new char[tbuf_size];
    this->file.seek(0, SEEK_SET);
    PointerHolder<char> b(buf);     // guarantee deletion
    memset(buf, '\0', tbuf_size);
    this->file.read(buf, tbuf_size - 1);

    static PCRE lindict_re("(?s:(\\d+)\\s+0\\s+obj\\s*<<)");

    off_t offset = -1;
    int lindict_obj = 0;
    char* p = buf;
    while (lindict_obj == 0)
    {
      PCRE::Match m(lindict_re.match(p));
      if (m)
      {
          offset = m.getOffset(0) + (p - buf);
          lindict_obj = atoi(m.getMatch(1).c_str());
          if (m.getMatch(0).find('\n') != std::string::npos)
          {
            QTC::TC("qpdf", "QPDF lindict found newline");
          }
      }
      else
      {
          if ((p = (char*)memchr(p, '\0', tbuf_size - (p - buf))) != 0)
          {
            QTC::TC("qpdf", "QPDF lindict null found");
            while ((p - buf < tbuf_size) && (*p == 0))
            {
                ++p;
            }
            if ((p - buf) == tbuf_size)
            {
                break;
            }
            QTC::TC("qpdf", "QPDF lindict searching after null");
          }
      }
    }

    if (lindict_obj == 0)
    {
      return false;
    }

    QPDFObjectHandle candidate = QPDFObjectHandle::Factory::newIndirect(
      this, lindict_obj, 0);
    if (! candidate.isDictionary())
    {
      return false;
    }

    QPDFObjectHandle linkey = candidate.getKey("/Linearized");
    if (! (linkey.isNumber() && ((int)floor(linkey.getNumericValue()) == 1)))
    {
      return false;
    }

    QPDFObjectHandle L = candidate.getKey("/L");
    if (L.isInteger())
    {
      int Li = L.getIntValue();
      this->file.seek(0, SEEK_END);
      if (Li != this->file.tell())
      {
          QTC::TC("qpdf", "QPDF /L mismatch");
          return false;
      }
      else
      {
          this->linp.file_size = Li;
      }
    }

    this->lindict = candidate;

    return true;
}

void
QPDF::readLinearizationData()
{
    // This function throws an exception (which is trapped by
    // checkLinearization()) for any errors that prevent loading.

    // Hint table parsing code needs at least 32 bits in a long.
    assert(sizeof(long) >= 4);

    if (! isLinearized())
    {
      throw QPDFExc(this->file.getName() + " is not linearized");
    }

    // /L is read and stored in linp by isLinearized()
    QPDFObjectHandle H = lindict.getKey("/H");
    QPDFObjectHandle O = lindict.getKey("/O");
    QPDFObjectHandle E = lindict.getKey("/E");
    QPDFObjectHandle N = lindict.getKey("/N");
    QPDFObjectHandle T = lindict.getKey("/T");
    QPDFObjectHandle P = lindict.getKey("/P");

    if (! (H.isArray() &&
         O.isInteger() &&
         E.isInteger() &&
         N.isInteger() &&
         T.isInteger() &&
         (P.isInteger() || P.isNull())))
    {
      throw QPDFExc("some keys in linearization dictionary are of "
                  "the wrong type");
    }

    // Hint table array: offset length [ offset length ]
    unsigned int n_H_items = H.getArrayNItems();
    if (! ((n_H_items == 2) || (n_H_items == 4)))
    {
      throw QPDFExc("H has the wrong number of items");
    }

    std::vector<int> H_items;
    for (unsigned int i = 0; i < n_H_items; ++i)
    {
      QPDFObjectHandle oh(H.getArrayItem(i));
      if (oh.isInteger())
      {
          H_items.push_back(oh.getIntValue());
      }
      else
      {
          throw QPDFExc("some H items are of the wrong type");
      }
    }

    // H: hint table offset/length for primary and overflow hint tables
    int H0_offset = H_items[0];
    int H0_length = H_items[1];
    int H1_offset = 0;
    int H1_length = 0;
    if (H_items.size() == 4)
    {
      // Acrobat doesn't read or write these (as PDF 1.4), so we
      // don't have a way to generate a test case.
      // QTC::TC("qpdf", "QPDF overflow hint table");
      H1_offset = H_items[2];
      H1_length = H_items[3];
    }

    // P: first page number
    int first_page = 0;
    if (P.isInteger())
    {
      QTC::TC("qpdf", "QPDF P present in lindict");
      first_page = P.getIntValue();
    }
    else
    {
      QTC::TC("qpdf", "QPDF P absent in lindict");
    }

    // Store linearization parameter data

    // file_size initialized by isLinearized()
    this->linp.first_page_object = O.getIntValue();
    this->linp.first_page_end = E.getIntValue();
    this->linp.npages = N.getIntValue();
    this->linp.xref_zero_offset = T.getIntValue();
    this->linp.first_page = first_page;
    this->linp.H_offset = H0_offset;
    this->linp.H_length = H0_length;

    // Read hint streams

    Pl_Buffer pb("hint buffer");
    QPDFObjectHandle H0 = readHintStream(pb, H0_offset, H0_length);
    if (H1_offset)
    {
      (void) readHintStream(pb, H1_offset, H1_length);
    }

    // PDF 1.4 hint tables that we ignore:

    //  /T    thumbnail
    //  /A    thread information
    //  /E    named destination
    //  /V    interactive form
    //  /I    information dictionary
    //  /C    logical structure
    //  /L    page label

    // Individual hint table offsets
    QPDFObjectHandle HS = H0.getKey("/S"); // shared object
    QPDFObjectHandle HO = H0.getKey("/O"); // outline

    PointerHolder<Buffer> hbp = pb.getBuffer();
    Buffer* hb = hbp.getPointer();
    unsigned char const* h_buf = hb->getBuffer();
    int h_size = hb->getSize();

    readHPageOffset(BitStream(h_buf, h_size));

    int HSi = HS.getIntValue();
    readHSharedObject(BitStream(h_buf + HSi, h_size - HSi));

    if (HO.isInteger())
    {
      int HOi = HO.getIntValue();
      readHGeneric(BitStream(h_buf + HOi, h_size - HOi),
                 this->outline_hints);
    }
}

QPDFObjectHandle
QPDF::readHintStream(Pipeline& pl, off_t offset, size_t length)
{
    int obj;
    int gen;
    QPDFObjectHandle H = readObjectAtOffset(offset, 0, 0, obj, gen);
    ObjCache& oc = this->obj_cache[ObjGen(obj, gen)];
    off_t min_end_offset = oc.end_before_space;
    off_t max_end_offset = oc.end_after_space;
    if (! H.isStream())
    {
      throw QPDFExc("hint table is not a stream");
    }

    QPDFObjectHandle Hdict = H.getDict();

    // Some versions of Acrobat make /Length indirect and place it
    // immediately after the stream, increasing length to cover it,
    // even though the specification says all objects in the
    // linearization parameter dictionary must be direct.  We have to
    // get the file position of the end of length in this case.
    QPDFObjectHandle length_obj = Hdict.getKey("/Length");
    if (length_obj.isIndirect())
    {
      QTC::TC("qpdf", "QPDF hint table length indirect");
      // Force resolution
      (void) length_obj.getIntValue();
      ObjCache& oc = this->obj_cache
          [ObjGen(length_obj.getObjectID(),
                length_obj.getGeneration())];
      min_end_offset = oc.end_before_space;
      max_end_offset = oc.end_after_space;
    }
    else
    {
      QTC::TC("qpdf", "QPDF hint table length direct");
    }
    off_t computed_end = offset + length;
    if ((computed_end < min_end_offset) ||
      (computed_end > max_end_offset))
    {
      std::cout << "expected = " << computed_end
              << "; actual = " << min_end_offset << ".."
              << max_end_offset << std::endl;
      throw QPDFExc("hint table length mismatch");
    }
    H.pipeStreamData(&pl, true, false, false);
    return Hdict;
}

void
QPDF::readHPageOffset(BitStream h)
{
    // All comments referring to the PDF spec refer to the spec for
    // version 1.4.

    HPageOffset& t = this->page_offset_hints;

    t.min_nobjects = h.getBits(32);                 // 1
    t.first_page_offset = h.getBits(32);            // 2
    t.nbits_delta_nobjects = h.getBits(16);               // 3
    t.min_page_length = h.getBits(32);                    // 4
    t.nbits_delta_page_length = h.getBits(16);            // 5
    t.min_content_offset = h.getBits(32);           // 6
    t.nbits_delta_content_offset = h.getBits(16);         // 7
    t.min_content_length = h.getBits(32);           // 8
    t.nbits_delta_content_length = h.getBits(16);         // 9
    t.nbits_nshared_objects = h.getBits(16);              // 10
    t.nbits_shared_identifier = h.getBits(16);            // 11
    t.nbits_shared_numerator = h.getBits(16);             // 12
    t.shared_denominator = h.getBits(16);           // 13

    unsigned int nitems = this->linp.npages;
    std::vector<HPageOffsetEntry>& entries = t.entries;
    entries = std::vector<HPageOffsetEntry>(nitems);

    load_vector_int(h, nitems, entries,
                t.nbits_delta_nobjects,
                &HPageOffsetEntry::delta_nobjects);
    load_vector_int(h, nitems, entries,
                t.nbits_delta_page_length,
                &HPageOffsetEntry::delta_page_length);
    load_vector_int(h, nitems, entries,
                t.nbits_nshared_objects,
                &HPageOffsetEntry::nshared_objects);
    load_vector_vector(h, nitems, entries,
                   &HPageOffsetEntry::nshared_objects,
                   t.nbits_shared_identifier,
                   &HPageOffsetEntry::shared_identifiers);
    load_vector_vector(h, nitems, entries,
                   &HPageOffsetEntry::nshared_objects,
                   t.nbits_shared_numerator,
                   &HPageOffsetEntry::shared_numerators);
    load_vector_int(h, nitems, entries,
                t.nbits_delta_content_offset,
                &HPageOffsetEntry::delta_content_offset);
    load_vector_int(h, nitems, entries,
                t.nbits_delta_content_length,
                &HPageOffsetEntry::delta_content_length);
}

void
QPDF::readHSharedObject(BitStream h)
{
    HSharedObject& t = this->shared_object_hints;

    t.first_shared_obj = h.getBits(32);                   // 1
    t.first_shared_offset = h.getBits(32);                // 2
    t.nshared_first_page = h.getBits(32);           // 3
    t.nshared_total = h.getBits(32);                      // 4
    t.nbits_nobjects = h.getBits(16);                     // 5
    t.min_group_length = h.getBits(32);                   // 6
    t.nbits_delta_group_length = h.getBits(16);           // 7

    QTC::TC("qpdf", "QPDF lin nshared_total > nshared_first_page",
          (t.nshared_total > t.nshared_first_page) ? 1 : 0);

    int nitems = t.nshared_total;
    std::vector<HSharedObjectEntry>& entries = t.entries;
    entries = std::vector<HSharedObjectEntry>(nitems);

    load_vector_int(h, nitems, entries,
                t.nbits_delta_group_length,
                &HSharedObjectEntry::delta_group_length);
    load_vector_int(h, nitems, entries,
                1, &HSharedObjectEntry::signature_present);
    for (int i = 0; i < nitems; ++i)
    {
      if (entries[i].signature_present)
      {
          // Skip 128-bit MD5 hash.  These are not supported by
          // acrobat, so they should probably never be there.  We
          // have no test case for this.
          for (int j = 0; j < 4; ++j)
          {
            (void) h.getBits(32);
          }
      }
    }
    load_vector_int(h, nitems, entries,
                t.nbits_nobjects,
                &HSharedObjectEntry::nobjects_minus_one);
}

void
QPDF::readHGeneric(BitStream h, HGeneric& t)
{
    t.first_object = h.getBits(32);                 // 1
    t.first_object_offset = h.getBits(32);                // 2
    t.nobjects = h.getBits(32);                           // 3
    t.group_length = h.getBits(32);                 // 4
}

bool
QPDF::checkLinearizationInternal()
{
    // All comments referring to the PDF spec refer to the spec for
    // version 1.4.

    std::list<std::string> errors;
    std::list<std::string> warnings;

    // Check all values in linearization parameter dictionary

    LinParameters& p = this->linp;

    // L: file size in bytes -- checked by isLinearized

    // O: object number of first page
    std::vector<QPDFObjectHandle> const& pages = getAllPages();
    if (p.first_page_object != pages[0].getObjectID())
    {
      QTC::TC("qpdf", "QPDF err /O mismatch");
      errors.push_back("first page object (/O) mismatch");
    }

    // N: number of pages
    int npages = pages.size();
    if (p.npages != npages)
    {
      // Not tested in the test suite
      errors.push_back("page count (/N) mismatch");
    }

    for (int i = 0; i < npages; ++i)
    {
      QPDFObjectHandle const& page = pages[i];
      ObjGen og(page.getObjectID(), page.getGeneration());
      if (this->xref_table[og].getType() == 2)
      {
          errors.push_back("page dictionary for page " +
                       QUtil::int_to_string(i) + " is compressed");
      }
    }

    // T: offset of whitespace character preceding xref entry for object 0
    this->file.seek(p.xref_zero_offset, SEEK_SET);
    while (1)
    {
      char ch;
      this->file.read(&ch, 1);
      if (! ((ch == ' ') || (ch == '\r') || (ch == '\n')))
      {
          this->file.seek(-1, SEEK_CUR);
          break;
      }
    }
    if (this->file.tell() != this->first_xref_item_offset)
    {
      QTC::TC("qpdf", "QPDF err /T mismatch");
      errors.push_back("space before first xref item (/T) mismatch "
                   "(computed = " +
                   QUtil::int_to_string(this->first_xref_item_offset) +
                   "; file = " + QUtil::int_to_string(this->file.tell()));
    }

    // P: first page number -- Implementation note 124 says Acrobat
    // ignores this value, so we will too.

    // Check numbering of compressed objects in each xref section.
    // For linearized files, all compressed objects are supposed to be
    // at the end of the containing xref section if any object streams
    // are in use.

    if (this->uncompressed_after_compressed)
    {
      errors.push_back("linearized file contains an uncompressed object"
                   " after a compressed one in a cross-reference stream");
    }

    // Further checking requires optimization and order calculation.
    // Don't allow optimization to make changes.  If it has to, then
    // the file is not properly linearized.  We use the xref table to
    // figure out which objects are compressed and which are
    // uncompressed.
    { // local scope
      std::map<int, int> object_stream_data;
      for (std::map<ObjGen, QPDFXRefEntry>::const_iterator iter =
             this->xref_table.begin();
           iter != this->xref_table.end(); ++iter)
      {
          ObjGen const& og = (*iter).first;
          QPDFXRefEntry const& entry = (*iter).second;
          if (entry.getType() == 2)
          {
            object_stream_data[og.obj] = entry.getObjStreamNumber();
          }
      }
      optimize(object_stream_data, false);
      calculateLinearizationData(object_stream_data);
    }

    // E: offset of end of first page -- Implementation note 123 says
    // Acrobat includes on extra object here by mistake.  pdlin fails
    // to place thumbnail images in section 9, so when thumbnails are
    // present, it also gets the wrong value for /E.  It also doesn't
    // count outlines here when it should even though it places them
    // in part 6.  This code fails to put thread information
    // dictionaries in part 9, so it actually gets the wrong value for
    // E when threads are present.  In that case, it would probably
    // agree with pdlin.  As of this writing, the test suite doesn't
    // contain any files with threads.

    assert(! this->part6.empty());
    int min_E = -1;
    int max_E = -1;
    for (std::vector<QPDFObjectHandle>::iterator iter = this->part6.begin();
       iter != this->part6.end(); ++iter)
    {
      ObjGen og((*iter).getObjectID(), (*iter).getGeneration());
      // All objects have to have been dereferenced to be classified.
      assert(this->obj_cache.count(og) > 0);
      ObjCache const& oc = this->obj_cache[og];
      min_E = std::max(min_E, (int)oc.end_before_space);
      max_E = std::max(max_E, (int)oc.end_after_space);
    }
    if ((p.first_page_end < min_E) || (p.first_page_end > max_E))
    {
      QTC::TC("qpdf", "QPDF warn /E mismatch");
      warnings.push_back("end of first page section (/E) mismatch: /E = " +
                     QUtil::int_to_string(p.first_page_end) +
                     "; computed = " +
                     QUtil::int_to_string(min_E) + ".." +
                     QUtil::int_to_string(max_E));
    }

    // Check hint tables

    std::map<int, int> shared_idx_to_obj;
    checkHSharedObject(errors, warnings, pages, shared_idx_to_obj);
    checkHPageOffset(errors, warnings, pages, shared_idx_to_obj);
    checkHOutlines(warnings);

    // Report errors

    bool result = true;

    if (! errors.empty())
    {
      result = false;
      for (std::list<std::string>::iterator iter = errors.begin();
           iter != errors.end(); ++iter)
      {
          std::cout << "ERROR: " << (*iter) << std::endl;
      }
    }

    if (! warnings.empty())
    {
      result = false;
      for (std::list<std::string>::iterator iter = warnings.begin();
           iter != warnings.end(); ++iter)
      {
          std::cout << "WARNING: " << (*iter) << std::endl;
      }
    }

    return result;
}

int
QPDF::maxEnd(ObjUser const& ou)
{
    assert(this->obj_user_to_objects.count(ou) > 0);
    std::set<ObjGen> const& ogs = this->obj_user_to_objects[ou];
    int end = 0;
    for (std::set<ObjGen>::iterator iter = ogs.begin();
       iter != ogs.end(); ++iter)
    {
      ObjGen const& og = *iter;
      assert(this->obj_cache.count(og) > 0);
      end = std::max(
          end, (int)(this->obj_cache[og].end_after_space));
    }
    return end;
}

int
QPDF::getLinearizationOffset(ObjGen const& og)
{
    QPDFXRefEntry entry = this->xref_table[og];
    int result = 0;
    switch (entry.getType())
    {
      case 1:
      result = entry.getOffset();
      break;

      case 2:
      // For compressed objects, return the offset of the object
      // stream that contains them.
      result = getLinearizationOffset(ObjGen(entry.getObjStreamNumber(), 0));
      break;

      default:
      throw QPDFExc(
          this->file.getName(), 0,
          "getLinearizationOffset called for xref entry not of type 1 or 2");
      break;
    }
    return result;
}

QPDFObjectHandle
QPDF::getUncompressedObject(QPDFObjectHandle& obj,
                      std::map<int, int> const& object_stream_data)
{
    if (obj.isNull() || (object_stream_data.count(obj.getObjectID()) == 0))
    {
      return obj;
    }
    else
    {
      int repl = (*(object_stream_data.find(obj.getObjectID()))).second;
      return objGenToIndirect(ObjGen(repl, 0));
    }
}

int
QPDF::lengthNextN(int first_object, int n,
              std::list<std::string>& errors)
{
    int length = 0;
    for (int i = 0; i < n; ++i)
    {
      ObjGen og(first_object + i, 0);
      if (this->xref_table.count(og) == 0)
      {
          errors.push_back(
            "no xref table entry for " +
            QUtil::int_to_string(first_object + i) + " 0");
      }
      else
      {
          assert(this->obj_cache.count(og) > 0);
          length += this->obj_cache[og].end_after_space -
            getLinearizationOffset(og);
      }
    }
    return length;
}

void
QPDF::checkHPageOffset(std::list<std::string>& errors,
                   std::list<std::string>& warnings,
                   std::vector<QPDFObjectHandle> const& pages,
                   std::map<int, int>& shared_idx_to_obj)
{
    // Implementation note 126 says Acrobat always sets
    // delta_content_offset and delta_content_length in the page
    // offset header dictionary to 0.  It also states that
    // min_content_offset in the per-page information is always 0,
    // which is an incorrect value.

    // Implementation note 127 explains that Acrobat always sets item
    // 8 (min_content_length) to zero, item 9
    // (nbits_delta_content_length) to the value of item 5
    // (nbits_delta_page_length), and item 7 of each per-page hint
    // table (delta_content_length) to item 2 (delta_page_length) of
    // that entry.  Acrobat ignores these values when reading files.

    // Empirically, it also seems that Acrobat sometimes puts items
    // under a page's /Resources dictionary in with shared objects
    // even when they are private.

    unsigned int npages = pages.size();
    int table_offset = adjusted_offset(
      this->page_offset_hints.first_page_offset);
    ObjGen first_page_og(pages[0].getObjectID(), pages[0].getGeneration());
    assert(this->xref_table.count(first_page_og) > 0);
    int offset = getLinearizationOffset(first_page_og);
    if (table_offset != offset)
    {
      warnings.push_back("first page object offset mismatch");
    }

    for (unsigned int pageno = 0; pageno < npages; ++pageno)
    {
      ObjGen page_og(pages[pageno].getObjectID(),
                   pages[pageno].getGeneration());
      int first_object = page_og.obj;
      assert(this->xref_table.count(page_og) > 0);
      offset = getLinearizationOffset(page_og);

      HPageOffsetEntry& he = this->page_offset_hints.entries[pageno];
      CHPageOffsetEntry& ce = this->c_page_offset_data.entries[pageno];
      int h_nobjects = he.delta_nobjects +
          this->page_offset_hints.min_nobjects;
      if (h_nobjects != ce.nobjects)
      {
          // This happens with pdlin when there are thumbnails.
          warnings.push_back(
            "object count mismatch for page " +
            QUtil::int_to_string(pageno) + ": hint table = " +
            QUtil::int_to_string(h_nobjects) + "; computed = " +
            QUtil::int_to_string(ce.nobjects));
      }

      // Use value for number of objects in hint table rather than
      // computed value if there is a discrepancy.
      int length = lengthNextN(first_object, h_nobjects, errors);
      int h_length = he.delta_page_length +
          this->page_offset_hints.min_page_length;
      if (length != h_length)
      {
          // This condition almost certainly indicates a bad hint
          // table or a bug in this code.
          errors.push_back(
            "page length mismatch for page " +
            QUtil::int_to_string(pageno) + ": hint table = " +
            QUtil::int_to_string(h_length) + "; computed length = " +
            QUtil::int_to_string(length) + " (offset = " +
            QUtil::int_to_string(offset) + ")");
      }

      offset += h_length;

      // Translate shared object indexes to object numbers.
      std::set<int> hint_shared;
      std::set<int> computed_shared;

      if ((pageno == 0) && (he.nshared_objects > 0))
      {
          // pdlin and Acrobat both do this even though the spec
          // states clearly and unambiguously that they should not.
          warnings.push_back("page 0 has shared identifier entries");
      }

      for (int i = 0; i < he.nshared_objects; ++i)
      {
          int idx = he.shared_identifiers[i];
          assert(shared_idx_to_obj.count(idx) > 0);
          hint_shared.insert(shared_idx_to_obj[idx]);
      }

      for (int i = 0; i < ce.nshared_objects; ++i)
      {
          int idx = ce.shared_identifiers[i];
          assert(idx < this->c_shared_object_data.nshared_total);
          int obj = this->c_shared_object_data.entries[idx].object;
          computed_shared.insert(obj);
      }

      for (std::set<int>::iterator iter = hint_shared.begin();
           iter != hint_shared.end(); ++iter)
      {
          if (! computed_shared.count(*iter))
          {
            // pdlin puts thumbnails here even though it shouldn't
            warnings.push_back(
                "page " + QUtil::int_to_string(pageno) +
                ": shared object " + QUtil::int_to_string(*iter) +
                ": in hint table but not computed list");
          }
      }

      for (std::set<int>::iterator iter = computed_shared.begin();
           iter != computed_shared.end(); ++iter)
      {
          if (! hint_shared.count(*iter))
          {
            // Acrobat does not put some things including at least
            // built-in fonts and procsets here, at least in some
            // cases.
            warnings.push_back(
                "page " + QUtil::int_to_string(pageno) +
                ": shared object " + QUtil::int_to_string(*iter) +
                ": in computed list but not hint table");
          }
      }
    }
}

void
QPDF::checkHSharedObject(std::list<std::string>& errors,
                   std::list<std::string>& warnings,
                   std::vector<QPDFObjectHandle> const& pages,
                   std::map<int, int>& idx_to_obj)
{
    // Implementation note 125 says shared object groups always
    // contain only one object.  Implementation note 128 says that
    // Acrobat always nbits_nobjects to zero.  Implementation note 130
    // says that Acrobat does not support more than one shared object
    // per group.  These are all consistent.

    // Implementation note 129 states that MD5 signatures are not
    // implemented in Acrobat, so signature_present must always be
    // zero.

    // Implementation note 131 states that first_shared_obj and
    // first_shared_offset have meaningless values for single-page
    // files.

    // Empirically, Acrobat and pdlin generate incorrect values for
    // these whenever there are no shared objects not referenced by
    // the first page (i.e., nshared_total == nshared_first_page).

    HSharedObject& so = this->shared_object_hints;
    if (so.nshared_total < so.nshared_first_page)
    {
      errors.push_back("shared object hint table: ntotal < nfirst_page");
    }
    else
    {
      // The first nshared_first_page objects are consecutive
      // objects starting with the first page object.  The rest are
      // consecutive starting from the first_shared_obj object.
      int cur_object = pages[0].getObjectID();
      for (int i = 0; i < so.nshared_total; ++i)
      {
          if (i == so.nshared_first_page)
          {
            QTC::TC("qpdf", "QPDF lin check shared past first page");
            if (this->part8.empty())
            {
                errors.push_back(
                  "part 8 is empty but nshared_total > "
                  "nshared_first_page");
            }
            else
            {
                int obj = this->part8[0].getObjectID();
                if (obj != so.first_shared_obj)
                {
                  errors.push_back(
                      "first shared object number mismatch: "
                      "hint table = " +
                      QUtil::int_to_string(so.first_shared_obj) +
                      "; computed = " +
                      QUtil::int_to_string(obj));
                }
            }

            cur_object = so.first_shared_obj;

            ObjGen og(cur_object, 0);
            assert(this->xref_table.count(og) > 0);
            int offset = getLinearizationOffset(og);
            int h_offset = adjusted_offset(so.first_shared_offset);
            if (offset != h_offset)
            {
                errors.push_back(
                  "first shared object offset mismatch: hint table = " +
                  QUtil::int_to_string(h_offset) + "; computed = " +
                  QUtil::int_to_string(offset));
            }
          }

          idx_to_obj[i] = cur_object;
          HSharedObjectEntry& se = so.entries[i];
          int nobjects = se.nobjects_minus_one + 1;
          int length = lengthNextN(cur_object, nobjects, errors);
          int h_length = so.min_group_length + se.delta_group_length;
          if (length != h_length)
          {
            errors.push_back(
                "shared object " + QUtil::int_to_string(i) +
                " length mismatch: hint table = " +
                QUtil::int_to_string(h_length) + "; computed = " +
                QUtil::int_to_string(length));
          }
          cur_object += nobjects;
      }
    }
}

void
QPDF::checkHOutlines(std::list<std::string>& warnings)
{
    // Empirically, Acrobat generates the correct value for the object
    // number but incorrectly stores the next object number's offset
    // as the offset, at least when outlines appear in part 6.  It
    // also generates an incorrect value for length (specifically, the
    // length that would cover the correct number of objects from the
    // wrong starting place).  pdlin appears to generate correct
    // values in those cases.

    if (this->c_outline_data.nobjects == this->outline_hints.nobjects)
    {
      if (this->c_outline_data.nobjects == 0)
      {
          return;
      }

      if (this->c_outline_data.first_object ==
          this->outline_hints.first_object)
      {
          // Check length and offset.  Acrobat gets these wrong.
          QPDFObjectHandle outlines = getRoot().getKey("/Outlines");
          ObjGen og(outlines.getObjectID(), outlines.getGeneration());
          assert(this->xref_table.count(og) > 0);
          int offset = getLinearizationOffset(og);
          ObjUser ou(ObjUser::ou_root_key, "/Outlines");
          int length = maxEnd(ou) - offset;
          int table_offset =
            adjusted_offset(this->outline_hints.first_object_offset);
          if (offset != table_offset)
          {
            warnings.push_back(
                "incorrect offset in outlines table: hint table = " +
                QUtil::int_to_string(table_offset) +
                "; computed = " + QUtil::int_to_string(offset));
          }
          int table_length = this->outline_hints.group_length;
          if (length != table_length)
          {
            warnings.push_back(
                "incorrect length in outlines table: hint table = " +
                QUtil::int_to_string(table_length) +
                "; computed = " + QUtil::int_to_string(length));
          }
      }
      else
      {
          warnings.push_back("incorrect first object number in outline "
                         "hints table.");
      }
    }
    else
    {
      warnings.push_back("incorrect object count in outline hint table");
    }
}

void
QPDF::showLinearizationData()
{
    try
    {
      readLinearizationData();
      checkLinearizationInternal();
      dumpLinearizationDataInternal();
    }
    catch (QPDFExc& e)
    {
      std::cout << e.what() << std::endl;
    }
}

void
QPDF::dumpLinearizationDataInternal()
{
    std::cout << this->file.getName() << ": linearization data:" << std::endl
            << std::endl;

    std::cout
      << "file_size: " << this->linp.file_size << std::endl
      << "first_page_object: " << this->linp.first_page_object << std::endl
      << "first_page_end: " << this->linp.first_page_end << std::endl
      << "npages: " << this->linp.npages << std::endl
      << "xref_zero_offset: " << this->linp.xref_zero_offset << std::endl
      << "first_page: " << this->linp.first_page << std::endl
      << "H_offset: " << this->linp.H_offset << std::endl
      << "H_length: " << this->linp.H_length << std::endl
      << std::endl;

    std::cout << "Page Offsets Hint Table" << std::endl
            << std::endl;
    dumpHPageOffset();
    std::cout << std::endl
            << "Shared Objects Hint Table" << std::endl
            << std::endl;
    dumpHSharedObject();

    if (this->outline_hints.nobjects > 0)
    {
      std::cout << std::endl
              << "Outlines Hint Table" << std::endl
              << std::endl;
      dumpHGeneric(this->outline_hints);
    }
}

int
QPDF::adjusted_offset(int offset)
{
    // All offsets >= H_offset have to be increased by H_length
    // since all hint table location values disregard the hint table
    // itself.
    if (offset >= this->linp.H_offset)
    {
      return offset + this->linp.H_length;
    }
    return offset;
}


void
QPDF::dumpHPageOffset()
{
    HPageOffset& t = this->page_offset_hints;
    std::cout
      << "min_nobjects: " << t.min_nobjects
      << std::endl
      << "first_page_offset: " << adjusted_offset(t.first_page_offset)
      << std::endl
      << "nbits_delta_nobjects: " << t.nbits_delta_nobjects
      << std::endl
      << "min_page_length: " << t.min_page_length
      << std::endl
      << "nbits_delta_page_length: " << t.nbits_delta_page_length
      << std::endl
      << "min_content_offset: " << t.min_content_offset
      << std::endl
      << "nbits_delta_content_offset: " << t.nbits_delta_content_offset
      << std::endl
      << "min_content_length: " << t.min_content_length
      << std::endl
      << "nbits_delta_content_length: " << t.nbits_delta_content_length
      << std::endl
      << "nbits_nshared_objects: " << t.nbits_nshared_objects
      << std::endl
      << "nbits_shared_identifier: " << t.nbits_shared_identifier
      << std::endl
      << "nbits_shared_numerator: " << t.nbits_shared_numerator
      << std::endl
      << "shared_denominator: " << t.shared_denominator
      << std::endl;

    for (int i1 = 0; i1 < this->linp.npages; ++i1)
    {
      HPageOffsetEntry& pe = t.entries[i1];
      std::cout
          << "Page " << i1 << ":" << std::endl
          << "  nobjects: " << pe.delta_nobjects + t.min_nobjects
          << std::endl
          << "  length: " << pe.delta_page_length + t.min_page_length
          << std::endl
          // content offset is relative to page, not file
          << "  content_offset: "
          << pe.delta_content_offset + t.min_content_offset << std::endl
          << "  content_length: "
          << pe.delta_content_length + t.min_content_length << std::endl
          << "  nshared_objects: " << pe.nshared_objects << std::endl;
      for (int i2 = 0; i2 < pe.nshared_objects; ++i2)
      {
          std::cout << "    identifier " << i2 << ": "
                  << pe.shared_identifiers[i2] << std::endl;
          std::cout << "    numerator " << i2 << ": "
                  << pe.shared_numerators[i2] << std::endl;
      }
    }
}

void
QPDF::dumpHSharedObject()
{
    HSharedObject& t = this->shared_object_hints;
    std::cout
      << "first_shared_obj: " << t.first_shared_obj
      << std::endl
      << "first_shared_offset: " << adjusted_offset(t.first_shared_offset)
      << std::endl
      << "nshared_first_page: " << t.nshared_first_page
      << std::endl
      << "nshared_total: " << t.nshared_total
      << std::endl
      << "nbits_nobjects: " << t.nbits_nobjects
      << std::endl
      << "min_group_length: " << t.min_group_length
      << std::endl
      << "nbits_delta_group_length: " << t.nbits_delta_group_length
      << std::endl;

    for (int i = 0; i < t.nshared_total; ++i)
    {
      HSharedObjectEntry& se = t.entries[i];
      std::cout << "Shared Object " << i << ":" << std::endl;
      std::cout << "  group length: "
              << se.delta_group_length + t.min_group_length << std::endl;
      // PDF spec says signature present nobjects_minus_one are
      // always 0, so print them only if they have a non-zero value.
      if (se.signature_present)
      {
          std::cout << "  signature present" << std::endl;
      }
      if (se.nobjects_minus_one != 0)
      {
          std::cout << "  nobjects: "
                  << se.nobjects_minus_one + 1 << std::endl;
      }
    }
}

void
QPDF::dumpHGeneric(HGeneric& t)
{
    std::cout
      << "first_object: " << t.first_object
      << std::endl
      << "first_object_offset: " << adjusted_offset(t.first_object_offset)
      << std::endl
      << "nobjects: " << t.nobjects
      << std::endl
      << "group_length: " << t.group_length
      << std::endl;
}

QPDFObjectHandle
QPDF::objGenToIndirect(ObjGen const& og)
{
    return getObjectByID(og.obj, og.gen);
}

void
QPDF::calculateLinearizationData(std::map<int, int> const& object_stream_data)
{
    // This function calculates the ordering of objects, divides them
    // into the appropriate parts, and computes some values for the
    // linearization parameter dictionary and hint tables.  The file
    // must be optimized (via calling optimize()) prior to calling
    // this function.  Note that actual offsets and lengths are not
    // computed here, but anything related to object ordering is.

    if (this->object_to_obj_users.empty())
    {
      // Note that we can't call optimize here because we don't know
      // whether it should be called with or without allow changes.
      throw QEXC::Internal("QPDF::calculateLinearizationData "
                       "called before optimize()");
    }

    // Separate objects into the categories sufficient for us to
    // determine which part of the linearized file should contain the
    // object.  This categorization is useful for other purposes as
    // well.  Part numbers refer to version 1.4 of the PDF spec.

    // Parts 1, 3, 5, 10, and 11 don't contain any objects from the
    // original file (except the trailer dictionary in part 11).

    // Part 4 is the document catalog (root) and the following root
    // keys: /ViewerPreferences, /PageMode, /Threads, /OpenAction,
    // /AcroForm, /Encrypt.  Note that Thread information dictionaries
    // are supposed to appear in part 9, but we are disregarding that
    // recommendation for now.

    // Part 6 is the first page section.  It includes all remaining
    // objects referenced by the first page including shared objects
    // but not including thumbnails.  Additionally, if /PageMode is
    // /Outlines, then information from /Outlines also appears here.

    // Part 7 contains remaining objects private to pages other than
    // the first page.

    // Part 8 contains all remaining shared objects except those that
    // are shared only within thumbnails.

    // Part 9 contains all remaining objects.

    // We sort objects into the following categories:

    //   * open_document: part 4

    //   * first_page_private: part 6

    //   * first_page_shared: part 6

    //   * other_page_private: part 7

    //   * other_page_shared: part 8

    //   * thumbnail_private: part 9

    //   * thumbnail_shared: part 9

    //   * other: part 9

    //   * outlines: part 6 or 9

    QPDFObjectHandle root = getRoot();
    bool outlines_in_first_page = false;
    QPDFObjectHandle pagemode = root.getKey("/PageMode");
    QTC::TC("qpdf", "QPDF categorize pagemode present",
          pagemode.isName() ? 1 : 0);
    if (pagemode.isName())
    {
      if (pagemode.getName() == "/UseOutlines")
      {
          if (root.hasKey("/Outlines"))
          {
            outlines_in_first_page = true;
          }
          else
          {
            QTC::TC("qpdf", "QPDF UseOutlines but no Outlines");
          }
      }
      QTC::TC("qpdf", "QPDF categorize pagemode outlines",
            outlines_in_first_page ? 1 : 0);
    }

    std::set<std::string> open_document_keys;
    open_document_keys.insert("/ViewerPreferences");
    open_document_keys.insert("/PageMode");
    open_document_keys.insert("/Threads");
    open_document_keys.insert("/OpenAction");
    open_document_keys.insert("/AcroForm");

    std::set<ObjGen> lc_open_document;
    std::set<ObjGen> lc_first_page_private;
    std::set<ObjGen> lc_first_page_shared;
    std::set<ObjGen> lc_other_page_private;
    std::set<ObjGen> lc_other_page_shared;
    std::set<ObjGen> lc_thumbnail_private;
    std::set<ObjGen> lc_thumbnail_shared;
    std::set<ObjGen> lc_other;
    std::set<ObjGen> lc_outlines;
    std::set<ObjGen> lc_root;

    for (std::map<ObjGen, std::set<ObjUser> >::iterator oiter =
           this->object_to_obj_users.begin();
       oiter != this->object_to_obj_users.end(); ++oiter)
    {
      ObjGen const& og = (*oiter).first;

      std::set<ObjUser>& ous = (*oiter).second;

      bool in_open_document = false;
      bool in_first_page = false;
      int other_pages = 0;
      int thumbs = 0;
      int others = 0;
      bool in_outlines = false;
      bool is_root = false;

      for (std::set<ObjUser>::iterator uiter = ous.begin();
           uiter != ous.end(); ++uiter)
      {
          ObjUser const& ou = *uiter;
          switch (ou.ou_type)
          {
            case ObjUser::ou_trailer_key:
            if (ou.key == "/Encrypt")
            {
                in_open_document = true;
            }
            else
            {
                ++others;
            }
            break;

            case ObjUser::ou_thumb:
            ++thumbs;
            break;

            case ObjUser::ou_root_key:
            if (open_document_keys.count(ou.key) > 0)
            {
                in_open_document = true;
            }
            else if (ou.key == "/Outlines")
            {
                in_outlines = true;
            }
            else
            {
                ++others;
            }
            break;

            case ObjUser::ou_page:
            if (ou.pageno == 0)
            {
                in_first_page = true;
            }
            else
            {
                ++other_pages;
            }
            break;

            case ObjUser::ou_root:
            is_root = true;
            break;

            case ObjUser::ou_bad:
            throw QEXC::Internal("QPDF::calculateLinearizationData: "
                             "invalid user type");
            break;
          }
      }

      if (is_root)
      {
          lc_root.insert(og);
      }
      else if (in_outlines)
      {
          lc_outlines.insert(og);
      }
      else if (in_open_document)
      {
          lc_open_document.insert(og);
      }
      else if ((in_first_page) &&
             (others == 0) && (other_pages == 0) && (thumbs == 0))
      {
          lc_first_page_private.insert(og);
      }
      else if (in_first_page)
      {
          lc_first_page_shared.insert(og);
      }
      else if ((other_pages == 1) && (others == 0) && (thumbs == 0))
      {
          lc_other_page_private.insert(og);
      }
      else if (other_pages > 1)
      {
          lc_other_page_shared.insert(og);
      }
      else if ((thumbs == 1) && (others == 0))
      {
          lc_thumbnail_private.insert(og);
      }
      else if (thumbs > 1)
      {
          lc_thumbnail_shared.insert(og);
      }
      else
      {
          lc_other.insert(og);
      }
    }

    // Generate ordering for objects in the output file.  Sometimes we
    // just dump right from a set into a vector.  Rather than
    // optimizing this by going straight into the vector, we'll leave
    // these phases separate for now.  That way, this section can be
    // concerned only with ordering, and the above section can be
    // considered only with categorization.  Note that sets of ObjGens
    // are sorted by ObjGen.  In a linearized file, objects appear in
    // sequence with the possible exception of hints tables which we
    // won't see here anyway.  That means that running
    // calculateLinearizationData() on a linearized file should give
    // results identical to the original file ordering.

    // We seem to traverse the page tree a lot in this code, but we
    // can address this for a future code optimization if necessary.
    // Premature optimization is the root of all evil.
    std::vector<QPDFObjectHandle> pages;
    { // local scope
      // Map all page objects to the containing object stream.  This
      // should be a no-op in a properly linearized file.
      std::vector<QPDFObjectHandle> t = getAllPages();
      for (std::vector<QPDFObjectHandle>::iterator iter = t.begin();
           iter != t.end(); ++iter)
      {
          pages.push_back(getUncompressedObject(*iter, object_stream_data));
      }
    }
    unsigned int npages = pages.size();

    // We will be initializing some values of the computed hint
    // tables.  Specifically, we can initialize any items that deal
    // with object numbers or counts but not any items that deal with
    // lengths or offsets.  The code that writes linearized files will
    // have to fill in these values during the first pass.  The
    // validation code can compute them relatively easily given the
    // rest of the information.

    this->c_linp.npages = npages;
    this->c_page_offset_data.entries =    std::vector<CHPageOffsetEntry>(npages);

    // Part 4: open document objects.  We don't care about the order.

    assert(lc_root.size() == 1);
    this->part4.push_back(objGenToIndirect(*(lc_root.begin())));
    for (std::set<ObjGen>::iterator iter = lc_open_document.begin();
       iter != lc_open_document.end(); ++iter)
    {
      this->part4.push_back(objGenToIndirect(*iter));
    }

    // Part 6: first page objects.  Note: implementation note 124
    // states that Acrobat always treats page 0 as the first page for
    // linearization regardless of /OpenAction.  pdlin doesn't provide
    // any option to set this and also disregards /OpenAction.  We
    // will do the same.

    // First, place the actual first page object itself.
    ObjGen first_page_og(pages[0].getObjectID(), pages[0].getGeneration());
    if (! lc_first_page_private.count(first_page_og))
    {
      throw QEXC::Internal("QPDF::calculateLinearizationData: first page "
                       "object not in lc_first_page_private");
    }
    lc_first_page_private.erase(first_page_og);
    this->c_linp.first_page_object = pages[0].getObjectID();
    this->part6.push_back(pages[0]);

    // The PDF spec "recommends" an order for the rest of the objects,
    // but we are going to disregard it except to the extent that it
    // groups private and shared objects contiguously for the sake of
    // hint tables.

    for (std::set<ObjGen>::iterator iter = lc_first_page_private.begin();
       iter != lc_first_page_private.end(); ++iter)
    {
      this->part6.push_back(objGenToIndirect(*iter));
    }

    for (std::set<ObjGen>::iterator iter = lc_first_page_shared.begin();
       iter != lc_first_page_shared.end(); ++iter)
    {
      this->part6.push_back(objGenToIndirect(*iter));
    }

    // Place the outline dictionary if it goes in the first page section.
    if (outlines_in_first_page)
    {
      pushOutlinesToPart(this->part6, lc_outlines, object_stream_data);
    }

    // Fill in page offset hint table information for the first page.
    // The PDF spec says that nshared_objects should be zero for the
    // first page.  pdlin does not appear to obey this, but it fills
    // in garbage values for all the shared object identifiers on the
    // first page.

    this->c_page_offset_data.entries[0].nobjects = this->part6.size();

    // Part 7: other pages' private objects

    // For each page in order:
    for (unsigned int i = 1; i < npages; ++i)
    {
      // Place this page's page object

      ObjGen page_og(pages[i].getObjectID(), pages[i].getGeneration());
      if (! lc_other_page_private.count(page_og))
      {
          throw QEXC::Internal(
            "QPDF::calculateLinearizationData: page object for page " +
            QUtil::int_to_string(i) + " not in lc_other_page_private");
      }
      lc_other_page_private.erase(page_og);
      this->part7.push_back(pages[i]);

      // Place all non-shared objects referenced by this page,
      // updating the page object count for the hint table.

      this->c_page_offset_data.entries[i].nobjects = 1;

      ObjUser ou(ObjUser::ou_page, i);
      assert(this->obj_user_to_objects.count(ou) > 0);
      std::set<ObjGen> ogs = this->obj_user_to_objects[ou];
      for (std::set<ObjGen>::iterator iter = ogs.begin();
           iter != ogs.end(); ++iter)
      {
          ObjGen const& og = (*iter);
          if (lc_other_page_private.count(og))
          {
            lc_other_page_private.erase(og);
            this->part7.push_back(objGenToIndirect(og));
            ++this->c_page_offset_data.entries[i].nobjects;
          }
      }
    }
    // That should have covered all part7 objects.
    if (! lc_other_page_private.empty())
    {
      throw QEXC::Internal(
          "QPDF::calculateLinearizationData: lc_other_page_private is "
          "not empty after generation of part7");
    }

    // Part 8: other pages' shared objects

    // Order is unimportant.
    for (std::set<ObjGen>::iterator iter = lc_other_page_shared.begin();
       iter != lc_other_page_shared.end(); ++iter)
    {
      this->part8.push_back(objGenToIndirect(*iter));
    }

    // Part 9: other objects

    // The PDF specification makes recommendations on ordering here.
    // We follow them only to a limited extent.  Specifically, we put
    // the pages tree first, then private thumbnail objects in page
    // order, then shared thumbnail objects, and then outlines (unless
    // in part 6).  After that, we throw all remaining objects in
    // arbitrary order.

    // Place the pages tree.
    std::set<ObjGen> pages_ogs =
      this->obj_user_to_objects[ObjUser(ObjUser::ou_root_key, "/Pages")];
    assert(! pages_ogs.empty());
    for (std::set<ObjGen>::iterator iter = pages_ogs.begin();
       iter != pages_ogs.end(); ++iter)
    {
      ObjGen const& og = *iter;
      if (lc_other.count(og))
      {
          lc_other.erase(og);
          this->part9.push_back(objGenToIndirect(og));
      }
    }

    // Place private thumbnail images in page order.  Slightly more
    // information would be required if we were going to bother with
    // thumbnail hint tables.
    for (unsigned int i = 0; i < npages; ++i)
    {
      QPDFObjectHandle thumb = pages[i].getKey("/Thumb");
      thumb = getUncompressedObject(thumb, object_stream_data);
      if (! thumb.isNull())
      {
          // Output the thumbnail itself
          ObjGen thumb_og(thumb.getObjectID(), thumb.getGeneration());
          if (lc_thumbnail_private.count(thumb_og))
          {
            lc_thumbnail_private.erase(thumb_og);
            this->part9.push_back(thumb);
          }
          else
          {
            // No internal error this time...there's nothing to
            // stop this object from having been referred to
            // somewhere else outside of a page's /Thumb, and if
            // it had been, there's nothing to prevent it from
            // having been in some set other than
            // lc_thumbnail_private.
          }
          std::set<ObjGen>& ogs =
            this->obj_user_to_objects[ObjUser(ObjUser::ou_thumb, i)];
          for (std::set<ObjGen>::iterator iter = ogs.begin();
             iter != ogs.end(); ++iter)
          {
            ObjGen const& og = *iter;
            if (lc_thumbnail_private.count(og))
            {
                lc_thumbnail_private.erase(og);
                this->part9.push_back(objGenToIndirect(og));
            }
          }
      }
    }
    if (! lc_thumbnail_private.empty())
    {
      throw QEXC::Internal(
          "QPDF::calculateLinearizationData: lc_thumbnail_private "
          "not empty after placing thumbnails");
    }

    // Place shared thumbnail objects
    for (std::set<ObjGen>::iterator iter = lc_thumbnail_shared.begin();
       iter != lc_thumbnail_shared.end(); ++iter)
    {
      this->part9.push_back(objGenToIndirect(*iter));
    }

    // Place outlines unless in first page
    if (! outlines_in_first_page)
    {
      pushOutlinesToPart(this->part9, lc_outlines, object_stream_data);
    }

    // Place all remaining objects
    for (std::set<ObjGen>::iterator iter = lc_other.begin();
       iter != lc_other.end(); ++iter)
    {
      this->part9.push_back(objGenToIndirect(*iter));
    }

    // Make sure we got everything exactly once.

    unsigned int num_placed = this->part4.size() + this->part6.size() +
      this->part7.size() + this->part8.size() + this->part9.size();
    unsigned int num_wanted = this->object_to_obj_users.size();
    if (num_placed != num_wanted)
    {
      throw QEXC::Internal("QPDF::calculateLinearizationData: wrong "
                       "number of objects placed (num_placed = " +
                       QUtil::int_to_string(num_placed) +
                       "; number of objects: " +
                       QUtil::int_to_string(num_wanted));
    }

    // Calculate shared object hint table information including
    // references to shared objects from page offset hint data.

    // The shared object hint table consists of all part 6 (whether
    // shared or not) in order followed by all part 8 objects in
    // order.  Add the objects to shared object data keeping a map of
    // object number to index.  Then populate the shared object
    // information for the pages.

    // Note that two objects never have the same object number, so we
    // can map from object number only without regards to generation.
    std::map<int, int> obj_to_index;

    this->c_shared_object_data.nshared_first_page = this->part6.size();
    this->c_shared_object_data.nshared_total =
      this->c_shared_object_data.nshared_first_page +
      this->part8.size();

    std::vector<CHSharedObjectEntry>& shared =
      this->c_shared_object_data.entries;
    for (std::vector<QPDFObjectHandle>::iterator iter = this->part6.begin();
       iter != this->part6.end(); ++iter)
    {
      QPDFObjectHandle& oh = *iter;
      int obj = oh.getObjectID();
      obj_to_index[obj] = shared.size();
      shared.push_back(CHSharedObjectEntry(obj));
    }
    QTC::TC("qpdf", "QPDF lin part 8 empty", this->part8.empty() ? 1 : 0);
    if (! this->part8.empty())
    {
      this->c_shared_object_data.first_shared_obj =
          this->part8[0].getObjectID();
      for (std::vector<QPDFObjectHandle>::iterator iter =
             this->part8.begin();
           iter != this->part8.end(); ++iter)
      {
          QPDFObjectHandle& oh = *iter;
          int obj = oh.getObjectID();
          obj_to_index[obj] = shared.size();
          shared.push_back(CHSharedObjectEntry(obj));
      }
    }
    assert(this->c_shared_object_data.nshared_total ==
         (int) this->c_shared_object_data.entries.size());

    // Now compute the list of shared objects for each page after the
    // first page.

    for (unsigned int i = 1; i < npages; ++i)
    {
      CHPageOffsetEntry& pe = this->c_page_offset_data.entries[i];
      ObjUser ou(ObjUser::ou_page, i);
      assert(this->obj_user_to_objects.count(ou) > 0);
      std::set<ObjGen> const& ogs = this->obj_user_to_objects[ou];
      for (std::set<ObjGen>::const_iterator iter = ogs.begin();
           iter != ogs.end(); ++iter)
      {
          ObjGen const& og = *iter;
          if ((this->object_to_obj_users[og].size() > 1) &&
            (obj_to_index.count(og.obj) > 0))
          {
            int idx = obj_to_index[og.obj];
            ++pe.nshared_objects;
            pe.shared_identifiers.push_back(idx);
          }
      }
    }
}

void
QPDF::pushOutlinesToPart(
    std::vector<QPDFObjectHandle>& part,
    std::set<ObjGen>& lc_outlines,
    std::map<int, int> const& object_stream_data)
{
    QPDFObjectHandle root = getRoot();
    QPDFObjectHandle outlines = root.getKey("/Outlines");
    if (outlines.isNull())
    {
      return;
    }
    outlines = getUncompressedObject(outlines, object_stream_data);
    ObjGen outlines_og(outlines.getObjectID(), outlines.getGeneration());
    QTC::TC("qpdf", "QPDF lin outlines in part",
          ((&part == (&this->part6)) ? 0
           : (&part == (&this->part9)) ? 1
           : 9999));          // can't happen
    this->c_outline_data.first_object = outlines_og.obj;
    this->c_outline_data.nobjects = 1;
    lc_outlines.erase(outlines_og);
    part.push_back(outlines);
    for (std::set<ObjGen>::iterator iter = lc_outlines.begin();
       iter != lc_outlines.end(); ++iter)
    {
      part.push_back(objGenToIndirect(*iter));
      ++this->c_outline_data.nobjects;
    }
}

void
QPDF::getLinearizedParts(
    std::map<int, int> const& object_stream_data,
    std::vector<QPDFObjectHandle>& part4,
    std::vector<QPDFObjectHandle>& part6,
    std::vector<QPDFObjectHandle>& part7,
    std::vector<QPDFObjectHandle>& part8,
    std::vector<QPDFObjectHandle>& part9)
{
    calculateLinearizationData(object_stream_data);
    part4 = this->part4;
    part6 = this->part6;
    part7 = this->part7;
    part8 = this->part8;
    part9 = this->part9;
}

static inline int nbits(int val)
{
    return (val == 0 ? 0 : (1 + nbits(val >> 1)));
}

int
QPDF::outputLengthNextN(
    int in_object, int n,
    std::map<int, size_t> const& lengths,
    std::map<int, int> const& obj_renumber)
{
    // Figure out the length of a series of n consecutive objects in
    // the output file starting with whatever object in_object from
    // the input file mapped to.

    assert(obj_renumber.count(in_object) > 0);
    int first = (*(obj_renumber.find(in_object))).second;
    int length = 0;
    for (int i = 0; i < n; ++i)
    {
      assert(lengths.count(first + i) > 0);
      length += (*(lengths.find(first + i))).second;
    }
    return length;
}

void
QPDF::calculateHPageOffset(
    std::map<int, QPDFXRefEntry> const& xref,
    std::map<int, size_t> const& lengths,
    std::map<int, int> const& obj_renumber)
{
    // Page Offset Hint Table

    // We are purposely leaving some values set to their initial zero
    // values.

    std::vector<QPDFObjectHandle> const& pages = getAllPages();
    unsigned int npages = pages.size();
    CHPageOffset& cph = this->c_page_offset_data;
    std::vector<CHPageOffsetEntry>& cphe = cph.entries;

    // Calculate minimum and maximum values for number of objects per
    // page and page length.

    int min_nobjects = cphe[0].nobjects;
    int max_nobjects = min_nobjects;
    int min_length = outputLengthNextN(
      pages[0].getObjectID(), min_nobjects, lengths, obj_renumber);
    int max_length = min_length;
    int max_shared = cphe[0].nshared_objects;

    HPageOffset& ph = this->page_offset_hints;
    std::vector<HPageOffsetEntry>& phe = ph.entries;
    phe = std::vector<HPageOffsetEntry>(npages);

    for (unsigned int i = 0; i < npages; ++i)
    {
      // Calculate values for each page, assigning full values to
      // the delta items.  They will be adjusted later.

      // Repeat calculations for page 0 so we can assign to phe[i]
      // without duplicating those assignments.

      int nobjects = cphe[i].nobjects;
      int length = outputLengthNextN(
          pages[i].getObjectID(), nobjects, lengths, obj_renumber);
      int nshared = cphe[i].nshared_objects;

      min_nobjects = std::min(min_nobjects, nobjects);
      max_nobjects = std::max(max_nobjects, nobjects);
      min_length = std::min(min_length, length);
      max_length = std::max(max_length, length);
      max_shared = std::max(max_shared, nshared);

      phe[i].delta_nobjects = nobjects;
      phe[i].delta_page_length = length;
      phe[i].nshared_objects = nshared;
    }

    ph.min_nobjects = min_nobjects;
    int in_page0_id = pages[0].getObjectID();
    int out_page0_id = (*(obj_renumber.find(in_page0_id))).second;
    ph.first_page_offset = (*(xref.find(out_page0_id))).second.getOffset();
    ph.nbits_delta_nobjects = nbits(max_nobjects - min_nobjects);
    ph.min_page_length = min_length;
    ph.nbits_delta_page_length = nbits(max_length - min_length);
    ph.nbits_nshared_objects = nbits(max_shared);
    ph.nbits_shared_identifier =
      nbits(this->c_shared_object_data.nshared_total);
    ph.shared_denominator = 4;      // doesn't matter

    // It isn't clear how to compute content offset and content
    // length.  Since we are not interleaving page objects with the
    // content stream, we'll use the same values for content length as
    // page length.  We will use 0 as content offset because this is
    // what Adobe does (implementation note 127) and pdlin as well.
    ph.nbits_delta_content_length = ph.nbits_delta_page_length;
    ph.min_content_length = ph.min_page_length;

    for (unsigned int i = 0; i < npages; ++i)
    {
      // Adjust delta entries
      assert(phe[i].delta_nobjects >= min_nobjects);
      assert(phe[i].delta_page_length >= min_length);
      phe[i].delta_nobjects -= min_nobjects;
      phe[i].delta_page_length -= min_length;
      phe[i].delta_content_length = phe[i].delta_page_length;

      for (int j = 0; j < cphe[i].nshared_objects; ++j)
      {
          phe[i].shared_identifiers.push_back(
            cphe[i].shared_identifiers[j]);
          phe[i].shared_numerators.push_back(0);
      }
    }
}

void
QPDF::calculateHSharedObject(
    std::map<int, QPDFXRefEntry> const& xref,
    std::map<int, size_t> const& lengths,
    std::map<int, int> const& obj_renumber)
{
    CHSharedObject& cso = this->c_shared_object_data;
    std::vector<CHSharedObjectEntry>& csoe = cso.entries;
    HSharedObject& so = this->shared_object_hints;
    std::vector<HSharedObjectEntry>& soe = so.entries;
    soe = std::vector<HSharedObjectEntry>(cso.nshared_total);

    int min_length = outputLengthNextN(
      csoe[0].object, 1, lengths, obj_renumber);
    int max_length = min_length;

    for (int i = 0; i < cso.nshared_total; ++i)
    {
      // Assign absolute numbers to deltas; adjust later
      int length = outputLengthNextN(
          csoe[i].object, 1, lengths, obj_renumber);
      min_length = std::min(min_length, length);
      max_length = std::max(max_length, length);
      soe[i].delta_group_length = length;
    }

    so.nshared_total = cso.nshared_total;
    so.nshared_first_page = cso.nshared_first_page;
    if (so.nshared_total > so.nshared_first_page)
    {
      so.first_shared_obj =
          (*(obj_renumber.find(cso.first_shared_obj))).second;
      so.first_shared_offset =
          (*(xref.find(so.first_shared_obj))).second.getOffset();
    }
    so.min_group_length = min_length;
    so.nbits_delta_group_length = nbits(max_length - min_length);

    for (int i = 0; i < cso.nshared_total; ++i)
    {
      // Adjust deltas
      assert(soe[i].delta_group_length >= min_length);
      soe[i].delta_group_length -= min_length;
    }
}

void
QPDF::calculateHOutline(
    std::map<int, QPDFXRefEntry> const& xref,
    std::map<int, size_t> const& lengths,
    std::map<int, int> const& obj_renumber)
{
    HGeneric& cho = this->c_outline_data;

    if (cho.nobjects == 0)
    {
      return;
    }

    HGeneric& ho = this->outline_hints;

    ho.first_object =
      (*(obj_renumber.find(cho.first_object))).second;
    ho.first_object_offset =
      (*(xref.find(ho.first_object))).second.getOffset();
    ho.nobjects = cho.nobjects;
    ho.group_length = outputLengthNextN(
      cho.first_object, ho.nobjects, lengths, obj_renumber);
}

template <class T>
static void
write_vector_int(BitWriter& w, int nitems, std::vector<T>& vec,
             int bits, int T::*field)
{
    // nitems times, write bits bits from the given field of the ith
    // vector to the given bit writer.

    for (int i = 0; i < nitems; ++i)
    {
      w.writeBits(vec[i].*field, bits);
    }
    // The PDF spec says that each hint table starts at a byte
    // boundary.  Each "row" actually must start on a byte boundary.
    w.flush();
}

template <class T>
static void
write_vector_vector(BitWriter& w,
                int nitems1, std::vector<T>& vec1, int T::*nitems2,
                int bits, std::vector<int> T::*vec2)
{
    // nitems1 times, write nitems2 (from the ith element of vec1) items
    // from the vec2 vector field of the ith item of vec1.
    for (int i1 = 0; i1 < nitems1; ++i1)
    {
      for (int i2 = 0; i2 < vec1[i1].*nitems2; ++i2)
      {
          w.writeBits((vec1[i1].*vec2)[i2], bits);
      }
    }
    w.flush();
}


void
QPDF::writeHPageOffset(BitWriter& w)
{
    HPageOffset& t = this->page_offset_hints;

    w.writeBits(t.min_nobjects, 32);                      // 1
    w.writeBits(t.first_page_offset, 32);           // 2
    w.writeBits(t.nbits_delta_nobjects, 16);              // 3
    w.writeBits(t.min_page_length, 32);                   // 4
    w.writeBits(t.nbits_delta_page_length, 16);           // 5
    w.writeBits(t.min_content_offset, 32);                // 6
    w.writeBits(t.nbits_delta_content_offset, 16);        // 7
    w.writeBits(t.min_content_length, 32);                // 8
    w.writeBits(t.nbits_delta_content_length, 16);        // 9
    w.writeBits(t.nbits_nshared_objects, 16);             // 10
    w.writeBits(t.nbits_shared_identifier, 16);           // 11
    w.writeBits(t.nbits_shared_numerator, 16);            // 12
    w.writeBits(t.shared_denominator, 16);                // 13

    unsigned int nitems = getAllPages().size();
    std::vector<HPageOffsetEntry>& entries = t.entries;

    write_vector_int(w, nitems, entries,
                 t.nbits_delta_nobjects,
                 &HPageOffsetEntry::delta_nobjects);
    write_vector_int(w, nitems, entries,
                 t.nbits_delta_page_length,
                 &HPageOffsetEntry::delta_page_length);
    write_vector_int(w, nitems, entries,
                 t.nbits_nshared_objects,
                 &HPageOffsetEntry::nshared_objects);
    write_vector_vector(w, nitems, entries,
                  &HPageOffsetEntry::nshared_objects,
                  t.nbits_shared_identifier,
                  &HPageOffsetEntry::shared_identifiers);
    write_vector_vector(w, nitems, entries,
                  &HPageOffsetEntry::nshared_objects,
                  t.nbits_shared_numerator,
                  &HPageOffsetEntry::shared_numerators);
    write_vector_int(w, nitems, entries,
                 t.nbits_delta_content_offset,
                 &HPageOffsetEntry::delta_content_offset);
    write_vector_int(w, nitems, entries,
                 t.nbits_delta_content_length,
                 &HPageOffsetEntry::delta_content_length);
}

void
QPDF::writeHSharedObject(BitWriter& w)
{
    HSharedObject& t = this->shared_object_hints;

    w.writeBits(t.first_shared_obj, 32);            // 1
    w.writeBits(t.first_shared_offset, 32);               // 2
    w.writeBits(t.nshared_first_page, 32);                // 3
    w.writeBits(t.nshared_total, 32);                     // 4
    w.writeBits(t.nbits_nobjects, 16);                    // 5
    w.writeBits(t.min_group_length, 32);            // 6
    w.writeBits(t.nbits_delta_group_length, 16);          // 7

    QTC::TC("qpdf", "QPDF lin write nshared_total > nshared_first_page",
          (t.nshared_total > t.nshared_first_page) ? 1 : 0);

    int nitems = t.nshared_total;
    std::vector<HSharedObjectEntry>& entries = t.entries;

    write_vector_int(w, nitems, entries,
                 t.nbits_delta_group_length,
                 &HSharedObjectEntry::delta_group_length);
    write_vector_int(w, nitems, entries,
                 1, &HSharedObjectEntry::signature_present);
    for (int i = 0; i < nitems; ++i)
    {
      // If signature were present, we'd have to write a 128-bit hash.
      assert(entries[i].signature_present == 0);
    }
    write_vector_int(w, nitems, entries,
                 t.nbits_nobjects,
                 &HSharedObjectEntry::nobjects_minus_one);
}

void
QPDF::writeHGeneric(BitWriter& w, HGeneric& t)
{
    w.writeBits(t.first_object, 32);                      // 1
    w.writeBits(t.first_object_offset, 32);               // 2
    w.writeBits(t.nobjects, 32);                    // 3
    w.writeBits(t.group_length, 32);                      // 4
}

void
QPDF::generateHintStream(std::map<int, QPDFXRefEntry> const& xref,
                   std::map<int, size_t> const& lengths,
                   std::map<int, int> const& obj_renumber,
                   PointerHolder<Buffer>& hint_buffer,
                   int& S, int& O)
{
    // Populate actual hint table values
    calculateHPageOffset(xref, lengths, obj_renumber);
    calculateHSharedObject(xref, lengths, obj_renumber);
    calculateHOutline(xref, lengths, obj_renumber);

    // Write the hint stream itself into a compressed memory buffer.
    // Write through a couter so we can get offsets.
    Pl_Buffer hint_stream("hint stream");
    Pl_Flate f("compress hint stream", &hint_stream, Pl_Flate::a_deflate);
    Pl_Count c("count", &f);
    BitWriter w(&c);

    writeHPageOffset(w);
    S = c.getCount();
    writeHSharedObject(w);
    O = 0;
    if (this->outline_hints.nobjects > 0)
    {
      O = c.getCount();
      writeHGeneric(w, this->outline_hints);
    }
    c.finish();

    hint_buffer = hint_stream.getBuffer();
}

Generated by  Doxygen 1.6.0   Back to index