Proving the Turing Completeness of Fonts (opens in new tab)

(litherum.blogspot.com)

61 pointspixelambacht7y ago14 comments

14 comments

>But even in HarfBuzz and CoreText, there are hard limits on the recursion depth. HarfBuzz sets its limit to 6. Therefore, the above example will only work on strings of length 7 or fewer. HarfBuzz is open source, though, so I simply used a custom build of HarfBuzz which bumps up this limit to 4 billion. This let me recurse to my heart’s content. A limit of 6 is probably a good thing; I don’t think users generally expect their text engines to be running arbitrary computation during layout.

Truly, Zalgo waits just beyond the wall.

zamalek7y ago

What we need is a Regex parser written in this language, and I can finally start on my HTML renderer font.

benj1117y ago

Fonts aren't really something I've dived into.

Could someone explain at what level this is happening. What classes of software/libraries are affected?

pcwalton7y ago

GSUB handling is done by a library called a text shaper. Examples of libraries that do shaping include the cross-platform HarfBuzz, Windows DirectWrite, and macOS Core Graphics/Core Text.

benj1117y ago

Thanks

So from what I understand these would be called from the UI libraries eg GTK in Linux land. I would assume window managers also, to deal with title bars.

I would further take from this that we shouldn't expect full Unicode support in virtual terminals (not emulators) in the future.....

paradroid7y ago

Can you use this to bypass Spectre mitigations in Javascript? You would need to measure time, somehow.

XaspR8d7y ago

It's not arbitrary code execution, just a toy observation about the specification. Additionally, 1) as noted, none of the font rendering libraries used were capable of recursion without the author's modifications, 2) in a web context, Javascript is unable to access information about actual glyphs rendered or other "font-internal" calculations.

If anything, exposing glyph data to the web API would be a bigger problem for fingerprinting, and probably expose some sort of user browsing history snooping flaw...

yorwba7y ago

> Javascript is unable to access information about actual glyphs rendered or other "font-internal" calculations.

Just render the text to a canvas and read out the pixel data to see the glyphs, a.k.a. canvas fingerprinting. I'm not sure whether getting clever with the font would reveal any information you can't get more easily, though.

kccqzy7y ago

I think this is extremely interesting. Not to dismiss the author's work, but merely performing addition is far from Turing complete. Addition is primitive recursive, a much smaller class of functions than say, generally recursive. Although in this case I have no reason to doubt that GSUB isn't Turing complete, because recursive symbol substitution is powerful enough.

ericsoderstrom7y ago

Isn't basically every moderately expressive system Turing complete? Even the Magic the Gathering card game is turing complete

https://www.toothycat.net/~hologram/Turing/HowItWorks.html

zwkrt7y ago

That doesn't make it any less fun to find out /how/ they are Turing complete!

peter_d_sherman7y ago

Excerpt: "Also, each mapping in the table acts as an “if” statement because it only executes if the pattern is matched."

This can be generalized as: Pattern Matching = if statement.

I don't know nor can I prove that that's true under all circumstances, however...

But, an interesting article.

empath757y ago

Seems like lambda calculus would have been a more natural thing to implement since it’s basically just symbol substitution.

0_gravitas7y ago

Any font is turning complete if you use it in powerpoint

j / k navigate · click thread line to collapse

14 comments

mLuby7y ago

Truly, Zalgo waits just beyond the wall.

zamalek7y ago

What we need is a Regex parser written in this language, and I can finally start on my HTML renderer font.

benj1117y ago

Fonts aren't really something I've dived into.

Could someone explain at what level this is happening. What classes of software/libraries are affected?

pcwalton7y ago

GSUB handling is done by a library called a text shaper. Examples of libraries that do shaping include the cross-platform HarfBuzz, Windows DirectWrite, and macOS Core Graphics/Core Text.

benj1117y ago

Thanks

So from what I understand these would be called from the UI libraries eg GTK in Linux land. I would assume window managers also, to deal with title bars.

I would further take from this that we shouldn't expect full Unicode support in virtual terminals (not emulators) in the future.....

paradroid7y ago

Can you use this to bypass Spectre mitigations in Javascript? You would need to measure time, somehow.

XaspR8d7y ago

If anything, exposing glyph data to the web API would be a bigger problem for fingerprinting, and probably expose some sort of user browsing history snooping flaw...

yorwba7y ago

> Javascript is unable to access information about actual glyphs rendered or other "font-internal" calculations.

kccqzy7y ago

ericsoderstrom7y ago

Isn't basically every moderately expressive system Turing complete? Even the Magic the Gathering card game is turing complete

https://www.toothycat.net/~hologram/Turing/HowItWorks.html

zwkrt7y ago

That doesn't make it any less fun to find out /how/ they are Turing complete!

peter_d_sherman7y ago

Excerpt: "Also, each mapping in the table acts as an “if” statement because it only executes if the pattern is matched."

This can be generalized as: Pattern Matching = if statement.

I don't know nor can I prove that that's true under all circumstances, however...

But, an interesting article.

empath757y ago

Seems like lambda calculus would have been a more natural thing to implement since it’s basically just symbol substitution.

0_gravitas7y ago

Any font is turning complete if you use it in powerpoint

j / k navigate · click thread line to collapse