//+------------------------------------------------------------------+
//|                                                  PdfValidate.mqh |
//|          Creating PDF Files in MQL5 (Part 2): Why PDFs Break     |
//|                                                                  |
//| A reader for PDF files that checks the four things a viewer      |
//| checks before it will draw anything:                             |
//|                                                                  |
//|     1. the file starts with %PDF-                                |
//|     2. startxref names the position of the word "xref"           |
//|     3. every entry in the xref table points at its own object    |
//|     4. every stream's /Length matches the bytes that follow it   |
//|                                                                  |
//| When a check fails the validator reports the object number, the  |
//| byte position it expected, and the byte position that is really  |
//| correct, so a broken file can be repaired rather than guessed at |
//|                                                                  |
//| This file is a debugging tool, not part of the PDF writer. It    |
//| stays in the library for the rest of the series because every    |
//| later part can break a file in a new way.                        |
//+------------------------------------------------------------------+
#ifndef PDF5_VALIDATE_MQH
#define PDF5_VALIDATE_MQH

//--- A file with more objects than this is refused rather than risking a
//--- runaway loop on a file that is not a PDF at all.
#define PDF_MAX_OBJECTS 4096

//--- How far back from the end of the file we look for "startxref". The
//--- specification allows the trailer to be long, but in practice it is a
//--- few hundred bytes, and scanning the whole file backwards is wasteful.
#define PDF_TAIL_SCAN   2048

//+------------------------------------------------------------------+
//| One problem found in the file.                                   |
//+------------------------------------------------------------------+
struct SPdfProblem
  {
   string            message;    // what is wrong, in one sentence
   long              position;   // byte position it concerns, -1 if none
   int               object_no;  // object number it concerns, -1 if none
  };

//+------------------------------------------------------------------+
//| CPdfValidator                                                    |
//|                                                                  |
//| Load a file, run the checks, read the problems out. The class    |
//| never modifies the file; it only reports.                        |
//+------------------------------------------------------------------+
class CPdfValidator
  {
private:
   uchar             m_data[];             // the whole file in memory
   int               m_size;               // its length in bytes

   //--- What the xref table claims.
   int               m_claimed[PDF_MAX_OBJECTS];
   int               m_claimed_count;

   //--- What a scan of the file actually finds.
   int               m_actual[PDF_MAX_OBJECTS];
   int               m_actual_count;

   SPdfProblem       m_problems[];
   int               m_problem_count;

   //--- byte level helpers
   bool              Load(const string filename);
   int               Find(const string needle, const int from) const;
   int               FindLast(const string needle, const int from) const;
   bool              Match(const string needle, const int at) const;
   string            Text(const int at, const int length) const;
   int               ReadInt(const int at, int &end) const;
   int               SkipSpace(const int at) const;

   //--- the four checks
   void              CheckHeader(void);
   int               CheckStartXref(void);
   void              CheckXrefTable(const int xref_pos);
   void              CheckOffsets(void);
   void              CheckStreams(void);

   //--- a full scan, used to say what the offsets should have been
   void              ScanObjects(void);

   void              Problem(const string message, const long position = -1,
                             const int object_no = -1);

public:
                     CPdfValidator(void) { Reset(); }

   void              Reset(void);
   bool              Check(const string filename);

   int               ProblemCount(void) const { return(m_problem_count); }
   SPdfProblem       ProblemAt(const int i) const { return(m_problems[i]); }
   int               ObjectCount(void) const { return(m_actual_count); }

   //--- Named ByteCount and not FileSize: a method called FileSize would
   //--- hide the terminal's FileSize() function inside every method of
   //--- this class, and Load() needs to call it.
   int               ByteCount(void) const { return(m_size); }

   void              PrintReport(const string filename);
  };

//+------------------------------------------------------------------+
//| Clears every result so one instance can check several files.     |
//+------------------------------------------------------------------+
void CPdfValidator::Reset(void)
  {
   ArrayFree(m_data);
   m_size = 0;
   m_claimed_count = 0;
   m_actual_count = 0;
   m_problem_count = 0;
   ArrayResize(m_problems, 0);
  }

//+------------------------------------------------------------------+
//| Records one problem.                                             |
//+------------------------------------------------------------------+
void CPdfValidator::Problem(const string message, const long position,
                            const int object_no)
  {
   ArrayResize(m_problems, m_problem_count + 1);
   m_problems[m_problem_count].message = message;
   m_problems[m_problem_count].position = position;
   m_problems[m_problem_count].object_no = object_no;
   m_problem_count++;
  }

//+------------------------------------------------------------------+
//| Reads the whole file into memory.                                |
//|                                                                  |
//| A PDF is read backwards from its end before it is read forwards, |
//| so streaming it makes no sense. Reports are in bytes, and bytes  |
//| are what FILE_BIN gives us.                                      |
//+------------------------------------------------------------------+
bool CPdfValidator::Load(const string filename)
  {
   int handle = FileOpen(filename, FILE_READ | FILE_BIN);
   if(handle == INVALID_HANDLE)
     {
      Problem(StringFormat("cannot open %s, error %d", filename,
                           GetLastError()));
      return(false);
     }

   m_size = (int)FileSize(handle);
   if(m_size <= 0)
     {
      FileClose(handle);
      Problem("the file is empty");
      return(false);
     }

   ArrayResize(m_data, m_size);
   int read = (int)FileReadArray(handle, m_data, 0, m_size);
   FileClose(handle);

   if(read != m_size)
     {
      Problem(StringFormat("read %d bytes of %d", read, m_size));
      return(false);
     }
   return(true);
  }

//+------------------------------------------------------------------+
//| True when the bytes at `at` equal `needle`.                      |
//+------------------------------------------------------------------+
bool CPdfValidator::Match(const string needle, const int at) const
  {
   int n = StringLen(needle);
   if(at < 0 || at + n > m_size)
      return(false);

   for(int i = 0; i < n; i++)
      if(m_data[at + i] != (uchar)StringGetCharacter(needle, i))
         return(false);
   return(true);
  }

//+------------------------------------------------------------------+
//| First position of `needle` at or after `from`, or -1.            |
//+------------------------------------------------------------------+
int CPdfValidator::Find(const string needle, const int from) const
  {
   int n = StringLen(needle);
   for(int i = MathMax(0, from); i + n <= m_size; i++)
      if(Match(needle, i))
         return(i);
   return(-1);
  }

//+------------------------------------------------------------------+
//| Last position of `needle` at or before `from`, or -1.            |
//+------------------------------------------------------------------+
int CPdfValidator::FindLast(const string needle, const int from) const
  {
   int n = StringLen(needle);
   for(int i = MathMin(from, m_size - n); i >= 0; i--)
      if(Match(needle, i))
         return(i);
   return(-1);
  }

//+------------------------------------------------------------------+
//| `length` bytes at `at`, as a printable string.                   |
//+------------------------------------------------------------------+
string CPdfValidator::Text(const int at, const int length) const
  {
   if(at < 0 || at >= m_size)
      return("");

   int n = MathMin(length, m_size - at);
   string s = CharArrayToString(m_data, at, n, CP_ACP);

//--- Line endings are escaped so a quoted fragment stays on one log line.
   StringReplace(s, "\r", "\\r");
   StringReplace(s, "\n", "\\n");
   return(s);
  }

//+------------------------------------------------------------------+
//| Skips spaces, tabs and line endings.                             |
//+------------------------------------------------------------------+
int CPdfValidator::SkipSpace(const int at) const
  {
   int i = at;
   while(i < m_size)
     {
      uchar c = m_data[i];
      if(c != ' ' && c != '\t' && c != '\r' && c != '\n')
         break;
      i++;
     }
   return(i);
  }

//+------------------------------------------------------------------+
//| Reads a decimal integer at `at`; `end` receives the position     |
//| just past the last digit. Returns -1 when there is no digit      |
//| there.                                                           |
//+------------------------------------------------------------------+
int CPdfValidator::ReadInt(const int at, int &end) const
  {
   int i = SkipSpace(at);
   int value = 0;
   bool any = false;

   while(i < m_size && m_data[i] >= '0' && m_data[i] <= '9')
     {
      value = value * 10 + (int)(m_data[i] - '0');
      any = true;
      i++;
     }

   end = i;
   return(any ? value : -1);
  }

//+------------------------------------------------------------------+
//| Check 1: the file must begin with the version marker.            |
//|                                                                  |
//| It must be at byte 0. A byte order mark in front of it is the    |
//| most common way a hand-written PDF dies, and it is invisible in  |
//| every text editor that produced it.                              |
//+------------------------------------------------------------------+
void CPdfValidator::CheckHeader(void)
  {
   if(Match("%PDF-", 0))
      return;

   int found = Find("%PDF-", 0);
   if(found > 0)
      Problem(StringFormat("%%PDF- is at byte %d, not byte 0 - there are %d "
                           "stray bytes in front of it", found, found), 0);
   else
      Problem("this file does not contain %PDF- at all", 0);
  }

//+------------------------------------------------------------------+
//| Check 2: startxref, and where it points.                         |
//|                                                                  |
//| Returns the byte position of the xref table, or -1. A viewer     |
//| does this first: it seeks to the end, reads backwards for        |
//| startxref, and jumps to the number it finds. Nothing else in     |
//| the file can be located until this succeeds.                     |
//+------------------------------------------------------------------+
int CPdfValidator::CheckStartXref(void)
  {
   int tail = MathMax(0, m_size - PDF_TAIL_SCAN);
   int at = FindLast("startxref", m_size - 1);

   if(at < 0 || at < tail)
     {
      Problem("no startxref keyword in the last " +
              IntegerToString(PDF_TAIL_SCAN) + " bytes of the file");
      return(-1);
     }

   int end = 0;
   int xref_pos = ReadInt(at + 9, end);      // 9 == StringLen("startxref")
   if(xref_pos < 0)
     {
      Problem("startxref is not followed by a number", at);
      return(-1);
     }

   if(xref_pos >= m_size)
     {
      Problem(StringFormat("startxref says %d but the file is only %d bytes",
                           xref_pos, m_size), at);
      return(-1);
     }

   if(!Match("xref", xref_pos))
     {
      Problem(StringFormat("startxref points at byte %d, which holds \"%s\" "
                           "and not \"xref\"", xref_pos,
                           Text(xref_pos, 12)), xref_pos);
      return(-1);
     }

   return(xref_pos);
  }

//+------------------------------------------------------------------+
//| Check 3a: read the table itself.                                 |
//|                                                                  |
//| The layout is: the word xref, then "first count", then `count`   |
//| entries of exactly 20 bytes each. The 20-byte rule is what makes |
//| the table seekable -- a viewer that wants object 40 jumps        |
//| straight to entry 40 rather than reading the 39 before it.       |
//+------------------------------------------------------------------+
void CPdfValidator::CheckXrefTable(const int xref_pos)
  {
   int end = 0;
   int first = ReadInt(xref_pos + 4, end);   // 4 == StringLen("xref")
   int count = ReadInt(end, end);

   if(first < 0 || count < 0)
     {
      Problem("the xref table has no \"first count\" line", xref_pos);
      return;
     }

   if(first != 0)
      Problem(StringFormat("the table starts at object %d; this series only "
                           "writes tables that start at 0", first), xref_pos);

   if(count > PDF_MAX_OBJECTS)
     {
      Problem(StringFormat("the table claims %d objects, which is more than "
                           "this validator will read", count), xref_pos);
      return;
     }

//--- The entries begin after the line ending that follows "first count".
   int at = end;
   while(at < m_size && (m_data[at] == '\r' || m_data[at] == '\n'))
      at++;

   m_claimed_count = 0;
   for(int i = 0; i < count; i++)
     {
      int entry = at + i * 20;
      if(entry + 20 > m_size)
        {
         Problem(StringFormat("the table is cut short after %d entries", i),
                 entry);
         return;
        }

      //--- Bytes 17 and 18 of every entry are the type flag and a space.
      //--- If they are not where they belong, the entries are not 20 bytes
      //--- long, and every entry after this one is being misread.
      uchar flag = m_data[entry + 17];
      if(flag != 'n' && flag != 'f')
        {
         Problem(StringFormat("entry %d does not have its type flag at byte "
                              "17 - the 20-byte rule is broken here, and "
                              "every entry below it is misaligned", i),
                 entry, i);
         return;
        }

      int unused = 0;
      int offset = ReadInt(entry, unused);
      m_claimed[m_claimed_count++] = (flag == 'f') ? -1 : offset;
     }
  }

//+------------------------------------------------------------------+
//|Finds every "N 0 obj" in the file by reading it straight through. |
//|                                                                  |
//| This is what a viewer's repair mode does. Comparing the result   |
//| against the table is what lets the report say "you wrote 247,    |
//| the object is at 257" instead of "damaged file".                 |
//+------------------------------------------------------------------+
void CPdfValidator::ScanObjects(void)
  {
   m_actual_count = 0;
   ArrayInitialize(m_actual, -1);

   int at = 0;
   while(at < m_size && m_actual_count < PDF_MAX_OBJECTS)
     {
      int found = Find(" obj", at);
      if(found < 0)
         break;

      //--- Walk backwards over " 0" and the object number to find the
      //--- first byte of "N 0 obj", which is what the offset must name.
      int i = found;
      while(i > 0 && m_data[i - 1] == ' ')
         i--;
      while(i > 0 && m_data[i - 1] >= '0' && m_data[i - 1] <= '9')
         i--;                                    // generation number
      while(i > 0 && m_data[i - 1] == ' ')
         i--;

      int start = i;
      while(start > 0 && m_data[start - 1] >= '0' && m_data[start - 1] <= '9')
         start--;                                // object number

      int unused = 0;
      int number = ReadInt(start, unused);
      if(number > 0 && number < PDF_MAX_OBJECTS)
        {
         if(number >= m_actual_count)
            m_actual_count = number + 1;
         m_actual[number] = start;
        }

      at = found + 4;
     }
  }

//+------------------------------------------------------------------+
//| Check 3b: does every claimed offset point at the right object?   |
//+------------------------------------------------------------------+
void CPdfValidator::CheckOffsets(void)
  {
   for(int i = 1; i < m_claimed_count; i++)
     {
      int offset = m_claimed[i];
      if(offset < 0)
         continue;                               // a free entry, skip it

      string expected = IntegerToString(i) + " 0 obj";

      if(offset >= m_size)
        {
         Problem(StringFormat("object %d is said to be at byte %d, past the "
                              "end of a %d byte file", i, offset, m_size),
                 offset, i);
         continue;
        }

      if(Match(expected, offset))
         continue;                               // this entry is correct

      //--- Say what is there, and where the object really is.
      string found_here = Text(offset, 16);
      int real = (i < m_actual_count) ? m_actual[i] : -1;
      if(real >= 0)
         Problem(StringFormat("object %d: the table says byte %d, but \"%s\" "
                              "is there; the object is really at byte %d, a "
                              "difference of %+d", i, offset, found_here,
                              real, real - offset), offset, i);
      else
         Problem(StringFormat("object %d: the table says byte %d, but \"%s\" "
                              "is there, and the object is nowhere in the "
                              "file", i, offset, found_here), offset, i);
     }
  }

//+------------------------------------------------------------------+
//| Check 4: every /Length must match the bytes in its stream.       |
//|                                                                  |
//| The distance is measured from the byte after the line ending     |
//| that follows the keyword "stream", to the byte before            |
//| "endstream". A viewer that trusts /Length and finds nothing      |
//| there gives up; one that searches for "endstream" forgives the   |
//| error. Files that open in one viewer and fail in another         |
//| usually fail this check.                                         |
//+------------------------------------------------------------------+
void CPdfValidator::CheckStreams(void)
  {
   int at = 0;
   while(at < m_size)
     {
      int keyword = Find("stream", at);
      if(keyword < 0)
         break;

      //--- Skip the "stream" inside the word "endstream".
      if(keyword >= 3 && Match("endstream", keyword - 3))
        {
         at = keyword + 6;
         continue;
        }

      //--- The dictionary with /Length is just above the keyword. Search
      //--- backwards for it rather than parsing the dictionary properly,
      //--- which Part 3 makes unnecessary by writing the value itself.
      int len_key = FindLast("/Length", keyword);
      if(len_key < 0)
        {
         Problem("a stream has no /Length above it", keyword);
         at = keyword + 6;
         continue;
        }

      int unused = 0;
      int claimed = ReadInt(len_key + 7, unused);   // 7 == "/Length"

      //--- The stream data starts after the end-of-line that follows the
      //--- keyword. CR LF counts as one ending, not two.
      int data = keyword + 6;
      if(data < m_size && m_data[data] == '\r')
         data++;
      if(data < m_size && m_data[data] == '\n')
         data++;

      int stop = Find("endstream", data);
      if(stop < 0)
        {
         Problem("a stream is never closed by endstream", keyword);
         return;
        }

      //--- The test a viewer applies: step /Length bytes forward and see
      //--- whether "endstream" is sitting there. The specification allows
      //--- one optional end-of-line in front of the keyword that is not
      //--- counted in /Length, so both positions are accepted. Measuring
      //--- the distance to "endstream" and comparing it instead would call
      //--- a correct file wrong whenever that optional byte is present.
      int probe = data + claimed;
      int skip = probe;
      if(skip < m_size && m_data[skip] == '\r')
         skip++;
      if(skip < m_size && m_data[skip] == '\n')
         skip++;

      bool ok = (claimed >= 0 && probe <= m_size &&
                 (Match("endstream", probe) || Match("endstream", skip)));

      if(!ok)
        {
         int actual = stop - data;
         Problem(StringFormat("a stream declares /Length %d but endstream is "
                              "%d bytes further on, a difference of %+d",
                              claimed, actual, actual - claimed), len_key);
        }

      at = stop + 9;
     }
  }

//+------------------------------------------------------------------+
//| Runs every check. Returns true when the file has no problems.    |
//+------------------------------------------------------------------+
bool CPdfValidator::Check(const string filename)
  {
   Reset();

   if(!Load(filename))
      return(false);

   ScanObjects();
   CheckHeader();

   int xref_pos = CheckStartXref();
   if(xref_pos >= 0)
     {
      CheckXrefTable(xref_pos);
      CheckOffsets();
     }

   CheckStreams();
   return(m_problem_count == 0);
  }

//+------------------------------------------------------------------+
//| Prints the findings to the Experts log.                          |
//+------------------------------------------------------------------+
void CPdfValidator::PrintReport(const string filename)
  {
   PrintFormat("--- %s: %d bytes, %d objects found by scanning",
               filename, m_size, MathMax(0, m_actual_count - 1));

   if(m_problem_count == 0)
     {
      Print("    no problems");
      return;
     }

   for(int i = 0; i < m_problem_count; i++)
     {
      string where = "";
      if(m_problems[i].position >= 0)
         where = StringFormat(" [byte %d]", m_problems[i].position);
      PrintFormat("    %d. %s%s", i + 1, m_problems[i].message, where);
     }
  }

#endif // PDF5_VALIDATE_MQH
//+------------------------------------------------------------------+