Plato: A document reader for PDF, ePUB, DjVu, etc.

[baskerville]

mupdf's ePUB engine has several problems:

- It randomly swallows text at the end of chapters.
- It consumes a gigantic amount of memory.
- It doesn't hyphenate.

I'm therefore in the process of writing an HTML renderer!

I've already written the first, and most important, piece of the puzzle: the line breaking algorithm.

[sjfan]

Originally Posted by baskerville

I'm therefore in the process of writing an HTML renderer!

I've already written the first, and most important, piece of the puzzle: the line breaking algorithm.

Knuth-Plass is not suitable for use with HTML in general; floats can cause the line width to vary based on the line height of preceding lines, which can in turn vary if you use dynamic line breaks the way K-P does.

Basically, you don't know the allowed width of a given line without having already fixed the layout of the lines above it.

Jonathan Kew discusses here (in the item explaining why Firefox doesn't use K-P):

Lines of different widths are not a problem in themselves. They become a problem when those widths are not known in advance, as when (for example) a float takes a "chunk" out of the side of the paragraph for text to wrap around it. The length required for any given line may depend on its exact vertical position; but that in turn might depend on which breaks end up getting chosen on earlier lines - and that choice may not be determined until _later_ in the paragraph, if there are several "active" possibilities under consideration.

This can be difficult even with a fixed-position float, if line heights vary (due to font changes, inline images, or all sorts of other factors); it gets worse if the float itself is anchored to a position within the text of the paragraph, and so the position of the float is not known in advance of line-breaking the text that contains it.

The good news is that the simple case (fixed- or at least known-width lines) should be sufficient for many ebooks, and K-P is ideal there, but you're going to have to think about how to determine ahead of time whether you can precalculate the line widths, and how to fall back to a different line-breaking algorithm if you cannot. “I don't support floats” is one possible answer, but many ebooks do use inline images so it's probably not acceptable.

You may also want to detect long paragraphs, since K-P is quadratic on the length of lines. If you can find it, P.I Cooper's article in the July 1966 Advances in Computer Typesetting discusses a way to break paragraphs into overlapping chunks to avoid degenerate behavior in long paragraphs.

[TnS]

I guess using Servo would be an overkill.

[sjfan]

Originally Posted by TnS

I guess using Servo would be an overkill.

That basically looks like a Rust translation of the gecko algorithms with respect to text layout. I took a quick look at components/layout/text.rs; it doesn't look like that solves the line breaking problem that baskerville's interested with Knuth-Plass wrapping, though it does handle hyphenation.

[sherman]

Originally Posted by sjfan

Knuth-Plass is not suitable for use with HTML in general; floats can cause the line width to vary based on the line height of preceding lines, which can in turn vary if you use dynamic line breaks the way K-P does.

Basically, you don't know the allowed width of a given line without having already fixed the layout of the lines above it.

Jonathan Kew discusses here (in the item explaining why Firefox doesn't use K-P):


The good news is that the simple case (fixed- or at least known-width lines) should be sufficient for many ebooks, and K-P is ideal there, but you're going to have to think about how to determine ahead of time whether you can precalculate the line widths, and how to fall back to a different line-breaking algorithm if you cannot. “I don't support floats” is one possible answer, but many ebooks do use inline images so it's probably not acceptable.

You may also want to detect long paragraphs, since K-P is quadratic on the length of lines. If you can find it, P.I Cooper's article in the July 1966 Advances in Computer Typesetting discusses a way to break paragraphs into overlapping chunks to avoid degenerate behavior in long paragraphs.

Note that TeX and it's variants use K&P, and they also support floats, so it's not an insurmountable problem. Whether you can do it quick enough on the other hand...

Chances are especially in an ebook, a float is going to occur at the beginning of a paragraph. If the float is not moved up, then it's a simple matter of placing it before setting the rest of the paragraphs. The float will be of a fixed dimensions by this point.

If the float is raised, then it becomes more complicated, and you probably have to re-break the preceding paragraph(s) one or more times until it fits. An expensive operation to be sure, but if one only has to re-break the occasional paragraph in a book, it's probably not too much of an issue.


(Note, I'm not an expert on these matters, but it is of interest for me. I've long wanted to see K&P or a similar algorithm implemented in an HTML renderer for ebooks.)

[sjfan]

Originally Posted by sherman

Note that TeX and it's variants use K&P, and they also support floats, so it's not an insurmountable problem.

As Boris Zbarsky summarizes in the issue I linked above, “In CSS layout, the available width for a line depends on the exact line break positions of all previous lines. It also depends on the height of the line, which depends on the exact items that end on the line and their vertical alignment”.

That causes Knuth-Plass to fail: K-P is trying to use information about the current line to help inform where the line breaks should be on previous lines. But HTML/CSS needs the line break information about previous lines before it can even determine the width and height of the current line.

TeX, on the other hand, places floats before they wrap the surrounding text. That allows them to know the line widths ahead of time.

That issue has further discussion. The Firefox folks are familiar with TeX and would love to have better word wrapping. But it's a lot more complex problem in the case of HTML+CSS than it is in a purpose-designed typography language.

(Note, I'm not an expert on these matters, but it is of interest for me. I've long wanted to see K&P or a similar algorithm implemented in an HTML renderer for ebooks.)

Me, too. I implement K-P for a primitive HTML 1.0 engine back in my college days.

[sherman]

I guess a pragmatic approach to dealing with floats (some might consider it a dirty hack, which it is) would be to lay out the offending paragraph(s) using a first fit algorithm, place the float(s) then re-layout the paragraph(s) using K&P. Sure the final layout might have the float start a line too early or late, but I wager most people would never notice...

And if dealing with floats that are meant to line up with the top of a paragraph (like drop caps) is simple enough. Place it first, use it's known height and width to feed to the K&P algorithm. Although, now that I've thought of it some more, changing the line-height mid paragraph would throw a spanner in the works now wouldn't it...

Interesting problems.

[sherman]

Also note that a general use web browser like Firefox can not make any sort of assumptions about the content it handles. It must assume that a web developer will use floats everywhere, and they expect the browser to follow the CSS layout spec to the letter.

Therefore, implementing an algorithm like K&P, which may or may not be feasible to follow all the rules, would be opening up a huge can of worms that they probably don't want to deal with.

An ebook renderer I feel has a much narrower scope of the content it is expected to layout. One can make (some) assumptions about content. Also every ebook renderer has its quirks, so what's another reader that doesn't quite lay out a float in the exact manner that CSS says it should be, so long as it's close enough?

[sjfan]

Originally Posted by sherman

Also note that a general use web browser like Firefox can not make any sort of assumptions about the content it handles. It must assume that a web developer will use floats everywhere, and they expect the browser to follow the CSS layout spec to the letter.

Therefore, implementing an algorithm like K&P, which may or may not be feasible to follow all the rules, would be opening up a huge can of worms that they probably don't want to deal with.

An ebook renderer I feel has a much narrower scope of the content it is expected to layout.

Yeah, hence my last observation in the first reply on the subject. You just need a way to detect whether there are problematic floats and degrade gracefully; that could be ugly or jarring on full-blown web pages, but for most epub purposes is probably sufficient.

Of course “just” doing that may be tricky in itself.

[baskerville]

I've released 0.3.5:

Plato now has an emulator based on SDL2: this greatly improves the quality of the debugging workflow.

New features:

• Mark a page as the first page of a book: hold the page indicator to bring the corresponding menu. You can then go to the nth page of a book by specifying "n in the go to page input field.
• Table of contents: the approach I've taken is to create an HTML document on the fly and feed it to the reader view.

I also fixed a crash that would trigger when the search bar was closed in the absence of matches.

[tshering]

@baskerville could you please have a look at this post concerning a problem with H2O2?

[baskerville]

Originally Posted by tshering

@baskerville could you please have a look at this post concerning a problem with H2O2?

This should already be fixed by d4647a9, I'll release a new version soon.

Thanks for the report.

[baskerville]

I've released 0.3.6.

New features:

• Find a word in a document.
• Add/remove bookmarks.
• Follow links.
• New touch regions.

[gilali]

H2Ov2+ ksm09 + plato 0.3.6
Same result but another error in crash.log :

thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Error { repr: Os { code: 6, message: "No such device or address" } }', /checkout/src/libcore/result.rs:916:5
note: Run with `RUST_BACKTRACE=1` for a backtrace.

[baskerville]

Originally Posted by gilali

H2Ov2+ ksm09 + plato 0.3.6
Same result but another error in crash.log :

thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Error { repr: Os { code: 6, message: "No such device or address" } }', /checkout/src/libcore/result.rs:916:5
note: Run with `RUST_BACKTRACE=1` for a backtrace.

I'm afraid I might need a backtrace: could you edit /adds/kbmenu/onstart/start_plato.sh and replace:

./plato > info.log 2>&1 || mv info.log crash.log

with

RUST_BACKTRACE=1 ./plato > info.log 2>&1 || mv info.log crash.log

and try again?