Implementing a "mini-LaTeX" in ~2000 lines of code

A preliminary note

The previous blog post on this subject got posted to hackernews. The comments were roughly like the following (contains exaggeration, but only a little):

The author claims to obtain superior quality compared to LaTeX but after reading the first three sentences I can say that there is nothing like that in the text so I just stopped there. Worst! Blog! Post! Ever!

So to be absolutely clear I'm not claiming to "beat" LaTeX in any sort of way (nor did I make such a claim in the original post). The quality is probably not better and the code has only a fraction of the functionality of LaTeX. Missing features include things like images, tables, cross references and even fairly basic functionality like widow and orphan control, italic text or any sort of customizability. This is just an experiment I'm doing for my own amusement.

What does it do then?

It can take a simple plain text version of The War of the Worlds, parse it into chapters, lay the text out in justified paragraphs and write the whole thing out into a PDF file. The output looks like this:

Even though the implementation is quite simple, it does have some typographical niceties. All new chapters begin on a right-hand page, the text is hyphenated, there are page numbers (but not on an empty page immediately preceding a new chapter) and the first paragraph of each chapter is not indented. The curious among you can examine the actual PDF yourselves. Just be prepared that there are known bugs in it.

Thus we can reasonably say that the code does contain an implementation of a very limited and basic form of LaTeX. The code repository has approximately 3000 total lines of C++ code but if you remove the GUI application and other helper code the core implementation only has around 2000 lines. Most of the auxiliary "heavy lifting" code is handled by Pango and Cairo.

Performance

The input text file for War of the Worlds is about 332 kB in size and the final PDF contains 221 pages. The program generates the output in 7 seconds on a Ryzen 7 3700 using only one core. This problem is fairly easily parallelizable so if one were to use all 16 cores at the same time the whole operation would take less than a second. I did not do exact measurements but the processing speed seems to be within the same order of magnitude as plain LaTeX.

The really surprising thing was that according to Massif the peak memory consumption was 5 MB. I had not tried to save memory when coding and just made copies of strings and other objects without a care in the world and still managed to almost fit the entire workload in the 4 MB L2 cache of the processor. Goes to show that premature optimization really is the root of all evil (or wasted effort at least).

Most CPU cycles are spent inside Pango. This is not due to any perf problems in Pango, but because this algorithm has an atypical work load. It keeps on asking Pango to shape and measure short text segments that are almost but not entirely identical. For each line that does get rendered, Pango had to process ~10 similar blocks of text. The code caches the results so it should only ask for the size of any individual string once, but this is still the bottleneck. On the other hand since you can process a fairly hefty book in 10 seconds or so it is arguable whether further optimizations are even necessary,

The future

I don't have any idea what I'm going to do with this code, if anything. One blue sky idea that came to mind was that it would be kind of cool to have a modern, fully color managed version of LaTeX that goes from markdown to a final PDF and ebook. This is not really feasible with the current approach since Cairo can only produce RGB files. There has been talk of adding full color space support to Cairo but nothing has happened on that front in 10 years or so.

Cairo is not really on its own in this predicament. Creating PDF files that are suitable for "commercial grade" printing using only open source is surprisingly difficult. For example LibreOffice does output text in the proper grayscale colorspace but silently converts all grayscale images (even 1-bit ones) to RGB. The only software that seems to get everything right is Scribus.

That time when I accidentally social engineered myself to a film set

I spent the last week in Toronto in the Cpp North conference. It was so much fun just to hang around with people after such a long pause.My talk was about porting large code bases from one build system to another, using LibreOffice as an example The talk should eventually show up on Youtube but there is no precise schedule for that yet.

After the conference ended I had a few spare days to do touristy stuff which was also fun. On the last day when I was packing my stuff I noticed that there was a film crew just outside the conference hotel clearly shooting something. The area did not seem to be closed off so obviously I went in to take a closer look. It was past 9 pm and I only had my phone camera so all the pictures below are a bit murky. On the other hand you can clearly see just how much lighting power you need to shoot high quality video material.

Another thing you pick up quite quickly is just how much stuff a film set requires. Here is an assorted selection of props and costumes that took up a major fraction of a side street.

After hanging around for a while a person belonging to the crew noticed me and we started chatting. Once it became known that I was from Finland we had the legally mandated Canada–Finland hockey discussion. Then he told me all things about the set, which was filming a new series for Apple TV. He also told me the name of the series and what sort of scene they were going to shoot next.

This is where things got interesting. In the couple of hours I spent looking at the set, there were tens of people who walked by and asked the security people what they were filming. They got one of two answers. The first one was a name for a series that was different than the one I was told. The second answer was "this is a new series with a largely unknown cast". This answer sounded very specific and very rehearsed. Based on some research I did later the series name I was given was probably the correct one. It's a bit strange that they had a fake name for the production but there you go (it is possible that the other name given to people was the episode name rather than the series name but this is just speculation).

Regardless of the name, the series takes place in New York so they had staged the street to look like a typical Manhattan street. This included a fair amount of detail that you might think would be done cheaply with CGI instead.

They had NY street signs and trash cans (not shown in the image, but the street name was "John st"). The things at the bottom marked with a red arrow are fake garbage bags. They even had a fake US style ATM, marked with the other red arrow. The water truck and was used to make the street wet, probably because the scene takes place after rain. They actually re-wet the street multiple times to maintain consistency. The only noticeable issue was that all cars on set had Ontario plates. Maybe they are counting on that not showing up on screen.

However the most important things you need to stage New York are actually smoke generators. Lots and lost of smoke generators. There were several big ones on the street, the garbage cans had ones, even the aforementioned ATM had its very own smoke machine. Don't really know if that is relevant to the plot or whether ATMs in New York run on steam.

As I stood on the street watching people go about their business eventually I noticed something strange. They started gathering more and more film equipment around me. There were a bunch of cameras, lights and I could clearly hear people planning the lighting et al for the shoot. Eventually I realized that they were building the "control center" (whatever its actual name is) of the set around me. This is what it looked like from the outside.

I stood next to one of the pillars shown in the middle of the picture next to a thing that looked suspiciously like a director's chair. I just leaned against the wall perfectly still while remaining calm and passive and nobody paid any attention to me at all. I could observe the crew going about their business,  browse their monitors (which, sadly, did not show anything interesting) and even see their uncannily realistic looking baby prop up close. I was probably there for around 30 minutes or so until someone finally asked me if I was part of the crew and then kindly asked me to leave which I did.

This was probably for the better as soon they started filming actual scenes and I could get a lot better look from the opposite side of the street. Watching the operation made it immediately obvious why shooting professional video is so expensive. The crew consisted of around 40-50 people who all seemed to work a full day well past midnight on a Friday. In the three hours I spent observing the operation they managed to film two scenes, each one lasting around 15 seconds.

All in all if you ever get the chance to observe a film crew in operation I highly recommend it. It is a better "making of" experience than any professionally produced featurette or documentary. The main reason being that it is about the actual making of instead of of millionaires lying through their teeth on how all other millionaires on set were so professional, super awesome and how the whole experience was the best thing ever because that is what they are contractually obligated to say. In person you get to see actually interesting things like how a camera operator puts on a weird Doctor Octopus carrying harness or how a team of tech workers builds and balances a 10+ meter long dolly track from scratch in under ten minutes. It is quite impressive.

Further adventures in creating a custom math-themed jigsaw puzzle

In the previous post we looked at creating a custom jigsaw puzzle from scratch using a laser printer and engraver because jigsaw puzzle manufacturers would not disclose their printing and cutting tolerances. As a refresher, here is what the end result looked like.

After assembling this puzzle once the main issue became apparent quite immediately. The curve needs to have a smooth linear gradient from black to white. Since this is a 256 piece puzzle it would require 256 discrete gray levels. Unfortunately the engraver can't achieve this level of precision. There are maybe 64 different achievable levels in practice and different parts of the plywood board react differently to the laser. Thus it is actually fairly difficult to judge where any given piece should go and assembling the final puzzle was not really fun. Back to the old drawing board, then.

The only other way of doing this seems to be to print the artwork to a separate sheet of paper, glue it to a plywood board and then cut the end result with a laser cutter. The problem with this is that you need to be very precise with registration. Even if you get the alignment perfect in one corner, it can be completely off in the opposite corner if the printed artwork gets glued down at an angle. Individual pieces are about two centimeters on each side so if the pattern is off by more than a few millimeters the end result looks bad.

The only real way of finding out whether this is possible is to try it out. Therefore:

Hilbert's Rainbow

Here is the artwork printed and glued to a 30 x 30 cm plywood board. If you look at the picture carefully you can see that a) the plywood is not exactly square b) its angles are not at exactly 90 degrees to each other and c) the artwork got glued at a slight angle. Moving the paper after it was first laid down was really hard, even though the glue was still wet. Those with sharp eyes might even notice the white registration marks in the corners that are used to align the laser. I had to leave additional comments for the printing shop that the things that look like crop marks are in fact not crop marks and that they need to be left in the final printout.

Onwards to the laser!

The only difference from the original laser cutting job was the prominent yellow flame when the grid was being cut. It probably comes from the paper and glue getting burned off by the laser. Fortunately this did not start a fire or char the printed surface.

After cutting the pieces can be separated.

All that's left is to assemble the puzzle.

As you can probably guess from this comparison picture, assembling the color version was much easier. For any piece it was immediately obvious where in the final puzzle it should go and classifying pieces to separate groups by color was straightforward. I did not even need to assemble the edges first as one typically does with regular jigsaw puzzles. It would have been harder than just following the color gradient line.

Putting it all together we find that with a printer, laser cutter and some ingenuity and elbow grease it is possible to create a product that, according to their own words, major jigsaw puzzle manufacturing plants were not able to produce.

Which is nice.