Butchering HQX pixel art scaling filters

http://blog.pkh.me/p/19-butchering-hqx-scaling-filters.html

by ux • 12 years ago

114 11 12 years ago

blog.pkh.me

byuu5• 12 years ago

Unfortunately, the reference code is more than 12.000 lines of unrolled C code. This code is basically duplicated without a thought in every single project.

Not by me. Overly bulky code is one of my pet peeves[1]. Here is my implementation of HQ2x in 6KB, 188 lines of code (not including the header file, which is 1KB and used for external linking.)

http://pastebin.com/raw.php?i=DsNupdbc

I devised a few observations to reduce the code. First is that the 256 patterns have four cases for each corner. If you rotate the eight surrounding pixels twice, the case blending rules match another corner (sans two cases which appear to be typos in the original algorithm. I asked the author, he apparently made the entire unrolled table by hand.) Now that the algorithm is cut down by 75%, put the switch statement into a lookup table.

To speed up the algorithm (and which further reduces its size), I use an old 16<>32-bit expand/compact trick, a YUV lookup table, and a really clever mask compare that blargg came up with. At this point, my version is already significant faster than the original algorithm. But I also added in OpenMP parallelization support, which really makes things run fast on multicore systems.

But anyway ... this guy clearly bested me. 560 lines with HQ3x and HQ4x included is even more impressive. Hats off to him!

([1] I also have inflate in 8kb of code, unzip in (inflate+2KB) of code, PNG decompression in (inflate+8kb) of code, SHA256 hashing in 4KB of code, an SMTP client with authentication+MIME attachments+HTML in 8KB of code, an XML parser (sans DTDs) in 6KB of code, etc.)

ux2• 12 years ago

Oh that's awesome. May I ask what method you used to figure out the algorithm?

I asked the author, he apparently made the entire unrolled table by hand.

what the hell...

byuu5• 12 years ago

It was a mostly manual process. I was trying to understand why four rules (one for each output pixel) were needed inside every case statement. So I wrote a parser for the original source file that turned each output pixel rule into an integer representing what the code for it was actually doing.

From here I noticed the strong symmetry when you rotated the pixels. Which of course makes perfect sense, I was just able to confirm it here.

So I tried to reproduce the same tables using a LUT and rotate table, and matched all but two instances. This seemed really weird to me, since I figured this would have to be generated unrolled code, right? So I asked Maxim about it, and he said that they were probably mistakes. I was pretty shocked myself that he did this by hand.

I did a few blind comparison photos on my board to see if anyone could tell the difference (in practice it amounted to one or two pixel differences in each 256x224 upscaled image), and everyone actually favored mine, so I just went ahead and ignored those two differences.

I'm curious if the blog author noticed the same thing, or if he noticed the rotation quicker and only built his tables off of the top-left output rules.

Ultimately it looks like the blog author found a better route to reducing the comparison rules than I did. But I still don't think we've 100% cracked how and why the original author chose the rules he did. And since it sounds like it was done almost by sight, we probably never will.

Still, I'd really like to see if someone could find a way to generate the comparison rules mathematically. It's very likely that if we had some sort of scientific basis for when and why to blend each case, we could improve the visual appearance beyond that of the original algorithm. Obviously perfection doesn't exist. I'd expect the end result to be a function that takes tuning variables, and different input images would look better with different tuning values. But even for the default case, I bet we could do better.

floatingatoll2• 12 years ago

"sans two cases which appear to be typos in the original algorithm."

By chance, do you have more details on which two specific cases are 'typos'? It would be fun to try fixing them in the original code and see what kind of change occurs in the output.

byuu5• 12 years ago

I posted this below to ux, but I'll repeat it here so you see it.

Sorry, but I was unable to find which ones were at issue. I wrote this code in 2005 - 2006, and have forgotten the relevant details by this point.

The info on how I did the symmetry and rotation was posted here, where it looks like I said there were six differences, but was still unsure of the exact number: http://forums.nesdev.com/viewtopic.php?p=82794#p82794

I'm a bit too swamped to do it myself, but if you or anyone else would be up for repeating my steps to determine which rules have the symmetry issues, please do post here.

atesti• 12 years ago

Is your other code like the SMTP client also available for download? I love looking at small but elegant code

byuu5• 12 years ago

Sure, it's part of a header library I use in all of my projects.

Download the "higan v094 (source)" link on this page: http://byuu.org/higan/

And find the relevant code inside the nall/ subfolder. Note that the code inside nall/ (and libco/, ruby/, phoenix/) is public domain, or ISC if you prefer. The rest is GPLv3.

madlag• 12 years ago

Nice stuff ! I am wondering how we could use it to improve some of our stuff with this ...

Butchering HQX pixel art scaling filters

Related Stories