MuPdf / Fitz

[Raph Levien]

On Thu, Jul 11, 2002 at 06:38:00PM +0200, Tor Andersson wrote:
> Hi all,
> 
> First, where does the name Fitz come from?

It's an Anglo-Norman prefix meaning "son", but often used to mean
"bastard son of". Fitz is the bastard son of Libart and the Ghostscript
graphics library.

Actually, there's thought of calling it "Libart 2" or somesuch, because
there's pretty good brand name recognition.

> Raph, will you set up mailing list and wiki?

Yes. Actually, Ralph will do the actual work.

[...]

> > My reimplementation of the Tex H&J algorithms is LibHnj. You might be
> > interested in the code; it's has some thought put in to efficient
> > implementation. The whole-paragraph justification is based on a
> > priority queue, but the implementation actually in LibHnj is the dumb
> > O(n) one. I have O(log n) priority queue code in the new Libart
> > intersector. Even with the O(n) code, it's pretty fast.
> 
> The code I wrote for that works in nearly linear time and deals with
> discretionary hyphens, different stretch-ratios for different types
> of spaces, penalties, margin adjustments and different glyph-and-kern
> sequences for different choices of line-breaks. It's quite impressive
> that I got it all to work, considering that I can only understand what
> I'm doing five seconds every two months. The only problem I have is
> processing a unicode text string to feed my algorithm with all the data
> it needs.  There are still some tricky issues as to how grouping glyphs
> and inserting potential breaks influence ligatures and contextual glyph
> substitution.

Yup, these are pretty hard problems.

> Oh, and your hyphenation code breaks down in mysterious ways when fed
> patterns for Italian and Latin languages. I think something fishy is
> going on with that statemachine, I never really understood how it works.

I'm not too surprised that there are problems. I never tested on
dictionaries other than the English. There are also issues with
character sets and case conversions.

> Anyway, it's right now a python/c hybrid and I can typeset around 10 or 20
> pages per second on a 300 Mhz sparc.

Now you're making me want to benchmark libhnj :)

> > Raster rendering is a top priority. Higher level output is not an
> > immediate priority for me, but is obviously important. In any case,
> > the "display tree" in Fitz preserves the graphics structure at a
> > relatively high level, so outputting it to printable formats makes
> > sense. The big trick is (as always) putting an interface on the fonts
> > so they can be exported and embedded into PS and PDF files. There's
> > a ton of logic for this in GS's PS->PDF conversion code paths.
> 
> Would it be possible to shift the font definition logic into another
> layer so that all Fitz works with is a collection of glyphs and an
> encoding vector of size 256? How do CID fonts work? I haven't had time
> to investigate.

Well, restricting to size 256 sounds like a pretty big lose. It _is_
reasonable, I think, to treat fonts as integer-subscripted arrays of
glyphs, and have the next level above deal with the encoding issues.

CID was an attempt by Adobe to work around the problems of Type0
composite fonts, which were largely a kluge to get around the
256-character limit of original Type1. One of the main advantages is
that it can be random-accessed, so you don't have to load the whole
font if you just need a subset of the characters.

Encoding in CID fonts is a rather complex multistep process. In the
font itself, glyphs are indexed by a CID ("character id"). These CID's
don't correspond to actual charset encodings. Among other things, they
tend to start from 0 and be fairly densely packed.

Thus, Adobe relies on an indirection table (called a CMap, but not to
be confused with the cmap table in a TT font). This CMap maps code
points in some character encoding (such as Shift-JIS or Big 5) into
the CID's. In fact, Adobe issues lots of fonts with the same CID
conventions, so the CMap tables can be reused between lots of fonts.

Among other things, CID fonts provide an answer to certain problems
that come up in CJK unification. For example, a font can store both
the simplified and traditional Hanzi for the same Unicode code point,
with different CID's. Then, you can have different Unicode->CID
CMap's, one for traditional and one for simplified.

> > Good font substitution is critical for PDF rendering. Note that PDF
> > embeds a "Widths" array even when the glyph outlines are not present.
> > Thus, it's possible to synthesize reasonably good-looking output from
> > suitable multiple master fonts. GS can render MM fonts, but there are
> > no free ones available, and GS lacks the logic to automatically
> > instantiate the MM font from the Widths table. Over the longer term,
> > I'd like to see free MM fonts drawn.
> 
> Again, part of a separate library for font synthesizing that a potential
> PDF renderer can use?

Possibly.

> > But, again, are we doing rendering or layout? PDF specifies the interface
> > after layout but before rendering. Thus, results are quite consistent,
> > even when a font has to get substituted.
> 
> The way I see it, I am interested in making a "brother" library to Fitz,
> that does text layout. Getting text APIs right is harder and Fitz is not
> really the place for it. Let's call it Rune.
> 
> However, it would be most pleasant to get at font data from one place,
> so that I wouldn't have to duplicate all the font handling code.
> What is your position regarding FreeType? Or do we roll our own?

I'm ok with a big fat dependency on FreeType.

> > > Do we use floats or fixed point math?
> >
> > Big question. I'm still grappling with it.
> 
> Floats are faster on new machines, but fixed point feels safer as it's more
> predictable. Numerical instability won't bite us, and division by zero can
> be avoided without the EPSILON hack.

Yes. The other issues are the size of the coordinate space, and the
memory taken by coordinates. Happily, the impact of this choice on
performance is a quantitative problem and can be measured and
analyzed.

> > Doing aa in a luminance-linear space is not _always_ better than doing
> > it in a perceptually linear space.
> 
> Could it be possible to use another color space than RGB altogether?
> Say L*a*b or YCbCr or something based more on physics.
> Or will performance hurt too much in the last stage of converting to RGB?

My feeling is that the library needs to be capable of working in many
different color spaces (of varying dimensionality, as well), and do
the transformations between them as needed. If you have a sequence of
transformations (for example, CalibratedRGB->XYZ as specified in the
input colorspace, followed by XYZ->sRGB), you often win big by
composing the transoformations and doing individual color mapping
through the composed result. In the RGB->XYZ->RGB example above, the
composite transform can be done in 8 bits without serious loss of
accuracy, while the intermediate XYZ requires at least 16 bits.

My personal feeling is that doing aa in either the source space or the
target space is fine. The differences in doing aa in gamma-adjusted
spaces are subtle. We don't need to rule out the possibility, but I
don't think we need to spend too much time on it either.

> > > I presume Fitz will be written in ANSI C.
> >
> > That's where I'm leaning. C++ is also on the table, though.
> 
> I wouldn't go down the C++ way. I'm very biased here, but going C++ will
> not get rid of the worst deficiencies of C and add plenty of new ones.
> A C++ program can use a C library, but the reverse is sadly not true.
> If we leave the safe haven of C, I'm sure there are better alternatives
> than C++.

My feeling is that the implementation of C++ is getting better. It
is possible to provide C bindings for a C++ library, which is pretty
much what you have to do for other language bindings, but I agree,
the pain is probably not worth it.

So let's say C.

Raph