summaryrefslogtreecommitdiff
path: root/docs
diff options
context:
space:
mode:
Diffstat (limited to 'docs')
-rw-r--r--docs/progressive.txt289
1 files changed, 289 insertions, 0 deletions
diff --git a/docs/progressive.txt b/docs/progressive.txt
new file mode 100644
index 00000000..e626c26f
--- /dev/null
+++ b/docs/progressive.txt
@@ -0,0 +1,289 @@
+How to do progressive loading with MuPDF.
+=========================================
+
+What is progressive loading?
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+The idea of progressive loading is that as you download a PDF file
+into a browser, you can display the pages as they appear.
+
+There are 2 mechanisms by which this can be achieved. The first
+relies on the file being "linearized", the second relies on the
+caller of MuPDF having fine control over the http fetch and on
+the server supporting byte-range fetches.
+
+
+Progressive download using "linearized" files
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Adobe defines "linearized" PDFs as being ones that have both a
+specific layout of objects and a small amount of extra
+information to help avoid seeking within a file. The stated aim
+is to deliver the first page of a document in advance of the whole
+document downloading, whereupon subsequent pages will become
+available. Adobe also refers to these as "Optimized for fast web
+view" or "Web Optimized".
+
+MuPDF can actually slightly outperform this by displaying the first
+page quickly, and then providing 'incomplete' renderings of
+subsequent pages, as more and more resources are gradually delivered.
+
+Essentially the file starts with a slightly modified header, and the
+first object in the file is a special one (the linearization object)
+that a) indicates that the file is linearized, and b) gives some
+useful information (like the number of pages in the file etc).
+
+This object is then followed by all the objects required for the
+first page, then the "hint stream", then sets of object for each
+subsequent page in turn, then shared objects required for those
+pages, then various other random things.
+
+[Yes, really. While page 1 is sent with all the objects that it
+uses, shared or otherwise, subsequent pages do not get shared
+resources until after all the unshared page objects have been
+sent.]
+
+
+The Hint Stream, and why we don't use it.
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Adobe intended Hint Stream to be useful to facilitate the display
+of subsequent pages, but it has never used it. Consequently you
+can't trust people to write it properly. Consequently no one
+actually uses it. Consequently we should make do without it too.
+
+
+So how does MuPDF handle progressive loading?
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+MuPDF has made various extensions to its mechanisms for handling
+progressive loading.
+
+ + Progressive streams
+
+ At its lowest level MuPDF reads file data from an fz_stream,
+ using the fz_open_document_with_stream call. (fz_open_document
+ is implemented by calling this). We have extended the fz_stream
+ slightly, giving the system a way to ask for meta information
+ (or perform meta operations) on a stream.
+
+ Using this mechanism MuPDF can query:
+
+ + whether a stream is progressive or not (i.e. whether the
+ entire stream is accessible immediately)
+ + what the length of a stream should ultimately be (which an
+ http fetcher should know from the Content-Length header),
+
+ With this information MuPDF can decide whether to use its normal
+ object reading code, or whether to make use of a linearized
+ object. Knowing the length enables us to check with the length
+ value given in the linearized object - if these differ, the
+ assumption is that an incremental save has taken place, thus the
+ file is no longer linearized.
+
+ When data is pulled from a progressive stream, if we attempt to
+ read data that is not currently available, the stream should
+ throw an FZ_ERROR_TRYLATER error. This particular error code
+ will be interpreted by the caller as an indication that it
+ should retry the parsing of the current objects at a later time.
+
+ When a MuPDF call is made on a progressive stream, such as
+ fz_open_document_with_stream, or fz_load_page, the caller should
+ be prepared to handle an FZ_ERROR_TRYLATER error as meaning that
+ more data is required before it can continue. No indication is
+ directly given as to exactly how much more data is required, but
+ as the caller will be implementing the progressive fz_stream
+ that it has passed into MuPDF to start with, it can reasonably
+ be expected to figure out an estimate for itself.
+
+ + Cookie
+
+ Once a page has been loaded, if its contents are to be 'run'
+ as normal (using e.g. fz_run_page) any error (such as failing
+ to read a font, or an image, or even a content stream belonging
+ to the page) will result in a rendering that aborts with an
+ FZ_ERROR_TRYLATER error. The caller can catch this and display
+ a placeholder instead.
+
+ If each pages data was entirely self-contained and sent in
+ sequence this would perhaps be acceptable, with each page
+ appearing one after the other. Unfortunately, the linearization
+ procedure as laid down by Adobe does NOT do this: objects shared
+ between multiple pages (other than the first) are not sent with
+ the pages themselves, but rather AFTER all the pages have been
+ sent.
+
+ This means that a document that has a title page, then contents
+ that share a font used on pages 2 onwards, will not be able to
+ correctly display page 2 until after the font has arrived in
+ the file, which will not be until all the page data has been
+ sent.
+
+ To mitigate against this, MuPDF provides a way whereby callers
+ can indicate that they are prepared to accept an 'incomplete'
+ rendering of the file (perhaps with missing images, or with
+ substitute fonts).
+
+ Callers prepared to tolerate such renderings should set the
+ 'incomplete_ok' flag in the cookie, then call fz_run_page etc
+ as normal. If an FZ_ERROR_TRYLATER error is thrown at any point
+ during the page rendering, the error will be swallowed, the
+ 'incomplete' field in the cookie will become non-zero and
+ rendering will continue. When control returns to the caller
+ the caller can check the value of the 'incomplete' field and
+ know that the rendering it received is not authoritative.
+
+
+Progressive loading using byte range requests
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+If the caller has control over the http fetch, then it is possible
+to use byte range requests to fetch the document 'out of order'.
+This enables non-linearized files to be progressively displayed as
+they download, and fetches complete renderings of pages earlier than
+would otherwise be the case. This process requires no changes within
+MuPDF itself, but rather in the way the progressive stream learns
+from the attempts MuPDF makes to fetch data.
+
+Consider for example, an attempt to fetch a hypothetical file from
+a server.
+
+ + The initial http request for the document is sent with a "Range:"
+ header to pull down the first (say) 4k of the file.
+
+ + As soon as we get the header in from this initial request, we can
+ respond to meta stream operations to give the length, and whether
+ byte requests are accepted.
+
+ - If the header indicates that byte ranges are acceptable the
+ stream proceeds to go into a loop fetching chunks of the file
+ at a time (not necessarily in-order). Otherwise the server
+ will ignore the Range: header, and just serve the whole file.
+
+ - If the header indicates a content-length, the stream returns
+ that.
+
+ + MuPDF can then decide how to proceed based upon these flags and
+ whether the file is linearized or not. (If the file contains a
+ linearized object, and the content length matches, then the file
+ is considered to be linear, otherwise it is not).
+
+ If the file is linear:
+
+ - we proceed to read objects out of the file as it downloads.
+ This will provide us the first page and all its resources. It
+ will also enable us to read the hint streams (if present).
+
+ - Once we have read the hint streams, we unpack (and sanity
+ check) them to give us a map of where in the file each object
+ is predicted to live, and which objects are required for each
+ page. If any of these values are out of range, we treat the
+ file as if there were no hint streams.
+
+ - If we have hints, any attempt to load a subsequent page will
+ cause MuPDF to attempt to read exactly the objects required.
+ This will cause a sequence of seeks in the fz_stream followed
+ by reads. If the stream does not have the data to satisfy that
+ request yet, the stream code should remember the location that
+ was fetched (and fetch that block in the background so that
+ future retries will succeed) and should raise an
+ FZ_ERROR_TRYLATER error.
+
+ [Typically therefore when we jump to a page in a linear file
+ on a byte request capable link, we will quickly see a rough
+ rendering, which will improve fairly fast as images and fonts
+ arrive.]
+
+ - Regardless of whether we have hints or byte requests, on every
+ fz_load_page call MuPDF will attempt to process more of the
+ stream (that is assumed to be being downloaded in the
+ background). As linearized files are guaranteed to have pages
+ in order, pages will gradually become available. In the absence
+ of byte requests and hints however, we have no way of getting
+ resources early, so the renderings for these pages will remain
+ incomplete until much more of the file has arrived.
+
+ [Typically therefore when we jump to a page in a linear file
+ on a non byte request capable link, we will see a rough
+ rendering for that page as soon as data arrives for it (which
+ will typically take much longer than would be the case with
+ byte range capable downloads), and that will improve much more
+ slowly as images and fonts may not appear until almost the
+ whole file has arrived.]
+
+ - When the whole file has arrived, then we will attempt to read
+ the outlines for the file.
+
+ For a non-linearized PDF on a byte request capable stream:
+
+ - MuPDF will immediately seek to the end of the file to attempt
+ to read the trailer. This will fail with an FZ_ERROR_TRYLATER
+ due to the data not being here yet, but the stream code should
+ remember that this data is required and it should be prioritized
+ in the background fetch process.
+
+ - Repeated attempts to open the stream should eventually succeed
+ therefore. As MuPDF jumps through the file trying to read first
+ the xrefs, then the page tree objects, then the page contents
+ themselves etc, the background fetching process will be driven
+ by the attempts to read the file in the foreground.
+
+ [Typically therefore the opening of a non-linearized file will
+ be slower than a linearized one, as the xrefs/page trees for a
+ non-linear file can be 20%+ of the file data. Once past this
+ initial point however, pages and data can be pulled from the
+ file almost as fast as with a linearized file.]
+
+ For a non-linearized PDF on a non-byte request capable stream:
+
+ - MuPDF will immediately seek to the end of the file to attempt
+ to read the trailer. This will fail with an FZ_ERROR_TRYLATER
+ due to the data not being here yet. Subsequent retries will
+ continue to fail until the whole file has arrived, whereupon
+ the whole file will be instantly available.
+
+ [This is the worst case situation - nothing at all can be
+ displayed until the entire file has downloaded.]
+
+ A typical structure for a fetcher process (see curl-stream.c in
+ mupdf-curl as an example) might therefore look like this:
+
+ + We consider the file as an (initially empty) buffer which we are
+ filling by making requests. In order to ensure that we make
+ maximum use of our download link, we should ensure that whenever
+ one request finishes, we immediately launch another. Further, to
+ avoid the overheads for the request/response headers being too
+ large, we may want to divide the file into 'chunks', perhaps 4 or 32k
+ in size.
+
+ + We can then imagine a receiver process that sits there in a loop
+ requesting chunks to fill this buffer. In the absence of
+ any other impetus the receiver should request the next 'chunk'
+ of data from the file that it does not yet have, following the last
+ fill point. Initially we start the fill point at the beginning of
+ the file, but this will move around based on the requests made of
+ the progressive stream.
+
+ + We attempt to open the file, and MuPDF will read from the progressive
+ stream. It will first read the PDF file header (i.e. it will read from
+ within the area of the file we have already requested). It will then
+ attempt to seek to the end of the file to read the trailer. The
+ stream then has a choice; it can choose to block until such time as
+ data arrives (unlikely to be satisfactory as this blocks all other
+ MuPDF operations), or it can throw an FZ_ERROR_TRYLATER error.
+
+ + Whichever of these it chooses to do, it knows that the next 'block'
+ of the file that is required will be at the end of the file, so it
+ can set the desired fill pointer in the receiver process to arrange
+ that the next block requested will be that at the end of the file.
+
+ + When this data arrives, it can either unblock and continue, or
+ retry the MuPDF call that exited with the FZ_ERROR_TRYLATER error.
+
+ + When the file trailer has been read, the file will then attempt to
+ seek and read the xref information. Again this will cause the http
+ receiver to request that area of the file next.
+
+ + Accordingly, the file will be read using 'random access', where
+ the stream is in control of either blocking or asking operations
+ to retry later.