Add a file with arrays with lots of nulls to the test suite

A bug was fixed between qpdf 8.4.2 and 9.0.0 regarding this type of
file (see #305 and #311), but it was necessary to retest after some
major refactoring work at the lexical and parsing layers. This lays
the groundwork for including this in performance benchmarks and in the
qpdf test suite rather than having to keep a large,
non-redistributable file around.

20 arrays of 20K nulls is plenty for performance memory testing and
doesn't take too long to run. Compared to qpdf 8.4.2, in qpdf 11.0.0,
the file generated here uses 3% of the RAM and runs over 4 times
faster.

6 files changed, 86 insertions, 3 deletions

diff --git a/TODO b/TODO
index f664353e..a637ef84 100644
--- a/TODO
+++ b/TODO
@@ -7,9 +7,9 @@ Before Release:
 * Review in order #726
 * Make ./performance_check usable by other people by having published
   files to use for testing.
-  * https://opensource.adobe.com/dc-acrobat-sdk-docs/standards/pdfstandards/pdf/PDF32000_2008.pdf
-* Incorporate --report-mem-usage into performance testing. Make sure
-  there is some test somewhere that exercises the millions of nulls case.
+  * Site https://opensource.adobe.com/dc-acrobat-sdk-docs/standards/pdfstandards/pdf/PDF32000_2008.pdf
+  * Incorporate --report-mem-usage into performance testing.
+  * Include output of test_many_nulls
 * Evaluate issues tagged with `next`
 * Stay on top of https://github.com/pikepdf/pikepdf/pull/315
 
diff --git a/qpdf/CMakeLists.txt b/qpdf/CMakeLists.txt
index bc4ddf11..cf2f53c4 100644
--- a/qpdf/CMakeLists.txt
+++ b/qpdf/CMakeLists.txt
@@ -5,6 +5,7 @@ set(MAIN_CXX_PROGRAMS
   sizes
   test_driver
   test_large_file
+  test_many_nulls
   test_parsedoffset
   test_pdf_doc_encoding
   test_pdf_unicode
diff --git a/qpdf/qtest/many-nulls.test b/qpdf/qtest/many-nulls.test
new file mode 100644
index 00000000..c3eefa1f
--- /dev/null
+++ b/qpdf/qtest/many-nulls.test
@@ -0,0 +1,34 @@
+#!/usr/bin/env perl
+require 5.008;
+use warnings;
+use strict;
+
+unshift(@INC, '.');
+require qpdf_test_helpers;
+
+chdir("qpdf") or die "chdir testdir failed: $!\n";
+
+require TestDriver;
+
+cleanup();
+
+my $td = new TestDriver('many-nulls');
+
+# The output of test_many_nulls is also used in performance testing.
+# If it changes, consider whether it should be updated in
+# performance-test-files as well. See performance_check at the top of
+# the source tree.
+$td->runtest("create file with many nulls",
+             {$td->COMMAND => "test_many_nulls a.pdf"},
+             {$td->STRING => "", $td->EXIT_STATUS => 0},
+             $td->NORMALIZE_NEWLINES);
+$td->runtest("compare output",
+             {$td->FILE => "a.pdf"},
+             {$td->FILE => "many-nulls.pdf"},
+             $td->NORMALIZE_NEWLINES);
+$td->runtest("run check file",
+             {$td->COMMAND => "qpdf --check a.pdf"},
+             {$td->FILE => "many-nulls.out", $td->EXIT_STATUS => 0},
+             $td->NORMALIZE_NEWLINES);
+cleanup();
+$td->report(3);
diff --git a/qpdf/qtest/qpdf/many-nulls.out b/qpdf/qtest/qpdf/many-nulls.out
new file mode 100644
index 00000000..f95a8ecc
--- /dev/null
+++ b/qpdf/qtest/qpdf/many-nulls.out
@@ -0,0 +1,6 @@
+checking a.pdf
+PDF Version: 1.5
+File is not encrypted
+File is not linearized
+No syntax or stream encoding errors found; the file may still contain
+errors that qpdf cannot detect
diff --git a/qpdf/qtest/qpdf/many-nulls.pdf b/qpdf/qtest/qpdf/many-nulls.pdf
new file mode 100644
index 00000000..7dab77d7
--- /dev/null
+++ b/qpdf/qtest/qpdf/many-nulls.pdf
diff --git a/qpdf/test_many_nulls.cc b/qpdf/test_many_nulls.cc
new file mode 100644
index 00000000..07e81afe
--- /dev/null
+++ b/qpdf/test_many_nulls.cc
@@ -0,0 +1,42 @@
+#include <qpdf/QPDF.hh>
+#include <qpdf/QPDFObjectHandle.hh>
+#include <qpdf/QPDFWriter.hh>
+#include <qpdf/QUtil.hh>
+#include <cstdlib>
+#include <iostream>
+
+int
+main(int argc, char* argv[])
+{
+    auto whoami = QUtil::getWhoami(argv[0]);
+    if (argc != 2) {
+        std::cerr << "Usage: " << whoami << " outfile.pdf" << std::endl;
+        exit(2);
+    }
+    char const* outfile = argv[1];
+
+    // Create a file with lots of arrays containing very large numbers
+    // of nulls. Prior to qpdf 9.0.0, qpdf had a lot of trouble with
+    // this kind of file. This program is used to generate a file that
+    // can be used in the test suite and performance benchmarking.
+    QPDF q;
+    q.emptyPDF();
+    auto null = QPDFObjectHandle::newNull();
+    auto top = "[]"_qpdf;
+    for (int i = 0; i < 20; ++i) {
+        auto inner = "[]"_qpdf;
+        for (int j = 0; j < 20000; ++j) {
+            inner.appendItem(null);
+        }
+        top.appendItem(inner);
+    }
+    q.getTrailer().replaceKey("/Nulls", q.makeIndirectObject(top));
+    auto page = "<< /Type /Page /MediaBox [0 0 612 792] >>"_qpdf;
+    page = q.makeIndirectObject(page);
+    q.getRoot().getKey("/Pages").getKey("/Kids").appendItem(page);
+    QPDFWriter w(q, outfile);
+    w.setObjectStreamMode(qpdf_o_generate);
+    w.setDeterministicID(true);
+    w.write();
+    return 0;
+}