当我第一次在2018年IOCCC比赛中看到“最具通货膨胀率”的获奖作品时，我感到很困惑。这个小程序由非常多产的FabriceBellard编写，只有4KB的源代码，发出了著名的Lena测试图像的128×128分辨率版本。巫毒！IOCCC的评委写道：“我们能理解一些算术，但一点魔力都看不懂。”我决心找出它的魔力，并受到法比安·桑格拉德的启发，试图写出它是如何工作的。
使用该程序非常简单，其源代码和运行细节都可以在它的IOCCC页面上找到。我用GCC编译了它，并将输出直接管道到ImageMagick查看：
GCC-O3-o程序c./prog|display-#显示嵌入图像。/prog d<；vintage_cars.bin|display-#显示外部图像。
运行它时不带参数(如第一种情况)，将解压缩嵌入的数据并生成以下图像(放大以获取详细信息)：
诚然，这有相当数量的压缩工件，但对于2439字节的图像数据和1544字节的解压缩器源代码来说，这仍然是相当令人印象深刻的。
那么让我们看看它是如何工作的。这将是一次深度潜水，也是到目前为止我最长的一次潜水(我在太多细节上犯了错误)，所以请自便！从现在开始，我将展示原始程序的片段与我的去模糊版本中的相应片段并列在一起。当我提到行号时，除非另有说明，否则我指的是后者。我通常会使用带括号的斜体数字来表示这些内容。
在我的版本中，我扩展了单独的宏(用于压缩forloop)，改革了源代码，并重命名了变量。我所做的唯一的结构改变是从更新到现代风格的函数头，并将声明压低到尽可能本地化的范围(C99风格)。在一个例子中，当我将一个变量下推到两个块中时，我给它取了不同的名称，在这两个块中，它以不同的方式被重用。
我们将从程序的末尾开始，使用main()函数，然后向后返回到开头；实际上，我们将按照控制流从上到下。下面是main()函数：
112：(D){113：int，；114：s=D>；1？256：1968；115：q()；116：g=n(5)；117：f=1<；<；g；118：n=f-n(5)；119：o=n(5)；120：p=n(5)；121：w(0，0，g)；122：printf("；P6%d%d 255&#。123：E(a，N*f){124：l=y[0][a]；125：l=y[1][a]；126：m=y[2][a]；127：D=l-L；128：k(D+M)；129：k(l+L)；130：k(D-M)；131：}132：return 0；133：}。
228：int(Int)229：{230：基=argc>；1？256：1968；231：renormalize_and_read()；232：int=decode_unsign(5)；233：width=1；<；<；level；234：int=width-decode_unsign(5)；235：luma=decode_unsign(5)；236：chroma=decode_unsign(5)；237：EXTRACT_BLOCK(0。P6%d%d 255"；，width，Height)；239：for(int=0；Pixt<；Height*Width；Pixel++)240：{241：int=image[0][Pixel]；242：int=image[1][Pixel]；243：int=image[2][Pixel]；244：int=Y-CG；245：WRITE_BYTE_CLAMPED(临时+Co)；246：WRITE_BYTE_CLAPED(Y+CG)；247：WRITE_BYTE_CLAPPED(临时-Co)；248：}249：返回0；250：}。
图像基本上编码在两个不同的层中。较低级别使用仅存储单个比特和无符号整数的无损熵编码方案。我们稍后将详细了解这一点。现在，知道第一行(230)检查参数就足够了，以确定是在标准输入上期望图像，还是从内部字符串解压缩图像。在这两种模式下，数据的存储略有不同，此处的相关值兼作标志。然后，第二行(231)启动用于解码该比特流的泵。(然而，事实证明这是多余的，因为它无论如何都会在以后被称为。)。
在较高级别，首先要解码(232-236)的是由四个整数组成的小标题。其中第一个将图像宽度存储为2的幂。由于使用固定大小的数组来存储解压缩图像，因此宽度被限制为1024。第二个整数存储图像高度与宽度相比有多少条线短。对于正方形图像，这将是零，但这意味着只有正方形或面向风景的图像才是可能的。接下来的两行解码一对与图像质量相关的参数。此处的数字越高，压缩效果越好，但会牺牲图像质量。每种方法的最低法律值都是1，应该会产生近乎无损的结果。对于内置的Lenaimage，此标头中的四个值分别为7、0、41和82。
解码后的图像以PPM文件的形式写入标准输出，这是一种非常简单的写入格式，由一个小标题表示图像类型、分辨率和最大颜色值。单个printf()就足够了(238)。接着，ImageData本身就是一系列交错RGB顺序的无符号字节，每个像素和像素从左到右、从上到下的顺序(245-247)。由于格式有损耗，解压缩的RGB值可能会超出0到255的范围，因此使用一个小帮助器函数来钳位然后写入它们：
223：int(Int)224：{225：putchar(byte<；0？0：byte>；255？255：byte)；226：}。
压缩的图像数据实际上并不是使用通常的RGB色彩空间进行编码的，尽管它当然会在最后输出该色彩空间。相反，它使用YCgCo颜色空间。这很容易转换回RGB(244-247)，但在图像压缩方面有一些很好的特性。值得注意的是，它将亮度与色度数据解除关联。
要了解这一点，让我们看看内置图像的Y(亮度)颜色通道。我们可以通过在转换回RGB之前将CG(绿色-洋红色)和CO(橙色-蓝色)色度通道归零来实现此目的：
我们还可以通过将所有像素中的Y值设置为128并将所有像素中的Co值设置为零来单独查看CG通道。这将显示添加到中性灰色图像中的CG数据的外观：
同样，我们可以通过将Y值设置为128并将Cg值设置为零来单独查看Co通道：
希望这个变换的用处现在已经很清楚了：大部分实际图像细节都包含在Y通道中，只有一小部分包含在CG和Co通道中。此外，人眼对亮度比色度更敏感，因此通过将它们分离出来，编码器可以对它们进行不同程度的有损压缩。这就是为什么不是一个而是两个图像质量因子(235-236)。
许多有损图像和视频编解码器(如JPEG)提供了一个称为色度次采样的选项。使用时，亮度通道通常以全分辨率存储，而色度通道由编码器缩小并存储为较低分辨率的图像，然后由解码器放大。微小的图像解码器不会为此费心。相反，编码图像只是增加了色度通道的损耗因子(JPEG图像通常也是如此)。
还值得注意的是(241-243)，在以PPM要求的交错形式写入转换后的RGB值之前，解码器将Y、CG和Co通道解压缩为存储器中的平面格式。
将图像实际提取到存储器中的这些平面完全发生在第237行调用的函数中。这是对图像进行较高级别解码的主例程，也是程序中目前为止最晚的函数：
61：(Z，l，g){62：int，*，；63：if(g>；5||g>；2&；&；t(g-3)){64：C=1<；<；--g；65：E(a，4)W(z+a%2*c，l+a/2*c，g)；66：}67：ELSE{68：C=1<；<；g；69：d=c*c；70：q=n(73)；71：E(A，3){72：O=y[A]+l*f+z；73：B=A>；0；74：E(a，d)i[a]=0；75：E(a，d){76：IF(t(61+g*2+B))Break；77：A+=。79：i[a]=k*(n(25+(B+(a<；d/8)*2)*10)+1)*(A？p：O)；80：}81：if(！q){82：v=0；83：e(a，c){84：v+=l？o[-f+a]：0；85：v+=z？o[a*f-1]：0；86：}87：*i+=z&；88：}89：R(i+d，1，i，1，c，c，10)；90：r(o，f，i+d，c，1，c，10+g)；91：if(Q){92：c=q<；17；93：w=C？9-q：q-25；94：e(a，c)e(j，c){95：e(i，2){96：h=a*w+w；97：j=h&。3)+j+i；99：if(k=h<；0)h=(h*8+w/2)/w-2；100：h=h<；c？h：c？h：c-1；101：i[i]=k^C？O[h*f-1]：O[-f+h]；102：}103：O[C？j*f+a：a*f+j]+=*i*(8-J)+i[1]*J+。
143：void(int，int，int)144：{145：if(level>；5||level>；2&；&；decode_bit(level-3))146：{147：int=1；<；<；--level；148：for(int=0；corner<；4；corner++)149：EXTRACT_BLOCK(Left+Corner%2*size，150：top+corner/2*size，151：level)；152：}153：Else 154：{155：int=1；<；<；level；156：int=size*size；157：int=decode_unsign(73)；158：for(int=0；channel<；3；channel++)159：{160：int*=image[channel]+top*width+Left；161：int=channel>；0；162：for(int=0；系数<；面积；系数++)163：缓冲区[系数]=。164：for(int=0；系数<；面积；系数++)165：{166：if(decode_bit(61+level*2+is_chroma))167：中断；168：系数+=decode_unsign(5+is_chroma*10)；169：int=1-2*decode_bit(3)；170：缓冲区[系数]=171：sign*172：(decode_unsign(25+(is_chroma+(173：系数<；面积/8)*2)*10)+1)*174：(通道？色度：亮度)；175：}176：IF(！Predictor)177：{178：int=0；179：for(int=0；像素<；size；像素++)180：{181：dc+=top？OUTPUT[-宽度+像素]：0；182：dc+=左？OUTPUT[像素*宽度-1]：0；183：}184：*Buffer+=Left&；&；top？DC/2：DC；185：}186：COMPUTE_idct(缓冲区+区域，1，缓冲区，1，大小，187：大小，10)；188：COMPUTE_idct(输出，宽度，缓冲区+区域，大小，1,189：大小，10+级别)；190：IF(预测器)191：{192：INT=预测器<；17；193：INT=is_leftward？9-Predictor：Predictor-25；194：For(int=0；y<=Predictor<；17；193：int=is_leftward？9-Predictor：Predictor-25；194：for(int=0；y<。Y++)195：for(int=0；x<；size；x++)196：{197：int；198：for(int=0；Neighbor<；2；Neighbor++)199：{200：int=y*SLOPE+SLOPE；201：Weight=Reference&；7；202：Reference=(Reference>；>；3)+x+Neighbor；203：Int=Reference<；0；204：IF(IS_CLIPPED)205：REFERENCE=(206：REFERENCE*8+SLOPE/2)/SLOPE-2；207：REFERENCE=REFERENCE<；SIZE？208：REFERENCE：SIZE-1；209：缓冲区[邻居]=IS_CLIPPE^IS_LEFTWARD？210：OUTPUT[REFERENCE*WIDTH-1]：211：OUTPUT[-WIDTH+REFERENCE]。X*宽度+y：214：y*宽度+x]+=215：*缓冲区*(8-权重)+216：缓冲区[1]*权重+4>；&g
让我们从函数头本身开始。前两个参数提供要提取的方块左上角的像素坐标，第三个参数提供其级别，使用2的幂来确定其大小。
提取图像开始于像素(0，0)处的块和足以覆盖整个图像的级别(237)。请注意，这就是为什么像宽必须始终是2的幂的原因。虽然高度不是必须的，但是解码器仍然会提取整个方块的图像数据，当它写入PPM(238-239)时，它只会丢弃较低的行。
此函数做的第一件事是决定是否递归拆分块。如果块大于32×32(即，级别5)，则它将始终拆分它。如果降到4×4(即2级)，那么它将永远不会拆分它。对于介于两者之间的所有级别，它解码单个位以确定是否拆分它(目前，忽略decode_bit()的参数)。因此，递归总是以4×4和32×32之间的块大小结束。
当它执行递归时，它在每个维度上将块一分为二，然后按照从左上角到右上角、从左下角到右下角的顺序对四分之一进行解码(147-151)。每个叶块的数据在熵编码位流中连续布局，因此产生了图像数据的隐式四叉树组织。以下是内部图像的递归过程和HIT的解码顺序(请注意，此图像中实际上没有任何32×32个叶块)：
如果我们按照这个顺序在每个解码块之间画一条线，我们会得到一些与Z级曲线密切相关的东西，除了图像上的非均匀级别：
那么，这种排序为什么有用呢？首先，它允许编码器选择不同的块大小，而四叉树的每个节点只有一个比特，其中分割是一个选项。细节较少的区域可以用较大的块有效地编码，而细节较好的区域可以向下编码到较小的块。这与JPEG图像形成对比，在JPEG图像中，无论细节如何，块始终为8x8。对于此特定图像，按块大小细分为：
第二个原因是，考虑排序的位置。编码中的每个连续块往往在空间上与其之前的块相当接近。这意味着每个块都有更好的机会与前一个块相似，因此很可能压缩得更好，因为压缩都是关于预测的。如果我们按块的解码顺序并排排列这些块，我们可以更好地看到这一点。请注意相邻块的大小、颜色和纹理往往是相似的：
在任何情况下，当我们到达四叉树(153)的叶节点时，就是将块实际提取到图像缓冲器中的像素的时候了。这里的第一个实现步骤是读取用于该块(157)的预测模式，该预测模式是介于0和33之间的整数，并且被重新用于构成该块(158)的所有三个颜色通道。
预测器的工作是使用当前块上方和左侧已经解码的像素来猜测当前块的尽可能多。解码器自己越能做到这一点，编码器必须编码到比特流中的次数就越少。
在34种可能的预测模式中，0是特殊的，代表“DC预测”模式(176-185)。这只是取当前块正上方和左边的像素组的平均值(正好越过它的边界)。如果块已经位于图像的顶部，则它只使用左侧的像素，反之亦然。然后在整个块中将该平均值写入为常量值。请注意，在像素上没有明显的循环来将平均值写入其中。取而代之的是，它使用了一个聪明的技巧(184)，我们稍后会再谈到这一点。
在内置图像中的493个块中，240个块中近一半使用DC预测模式。这里它们显示了预测像素，其他253个块被涂黑(请注意，最左上角的块也使用DC模式，它只是预测黑色)：
那么，其他253个块使用的33个预测模式又如何呢？从1到33的模式表示块应该使用方向预测，数字表示方向本身。以下是模数与方向的映射方式：
例如，模式9表示块紧靠左边的所有像素应该在整个块中水平向右复制。类似地，模式25将从块的正上方开始以垂直线向下复制整个块中的像素。另一方面，模式17将沿对角线从上方和左侧向下和向右复制像素。模式1和33沿另一对角线相互复制像素，模式1将像素向上和向右复制，而33将像素向下和向左复制。
这些与HEVC中使用的33个方向帧内预测模式非常接近。在方向模式从2开始之前，HEVC在1处具有附加的“平面”预测模式，但是否则基数和对角方向匹配(例如，这里的模式1等同于HEVC中的模式2，这里的模式25与HEVC中的模式26匹配，依此类推)。
一个显著的区别是，在HEVC中，方向更密集，更接近水平和垂直方向，沿对角线更稀疏。为简单起见，微型解码器对它们的处理更为均匀(192-193)：在模式17下，每个方向仅以1/8像素的斜率步进，且围绕对角线对称。
下面是使用方向预测模式和预测像素的253个内置图像块。覆盖的箭头标记先前解码的像素沿着的传播方向：
注意一些方向稍微偏离角度的块是如何沿着预测的边缘显示良好的抗锯齿效果的？让我们从图像的右上角仔细看看其中一个块：
方向预测码在块中的每个像素(194-195)上循环，然后沿着方向向量外推回到其上方的先前解码的像素行或其左侧的像素列(200-211)。
通常，这将导致两个像素之间的位置(例如，上图中的左上线)。它通过循环(198)以获取两个相邻像素到任一侧来处理此问题，并基于其与它们中的每一个的距离有多近来计算权重(201)。然后，它将该像素预测为两者的线性加权混合(213-216)。由于方向向量的斜率是1/8像素的步长，所以除数为8的0到7之间的整数权重就足够了。混合给预测带来了类似于抗锯齿的效果。
如果我们同时采用恒定DC预测器预测的块和方向预测模式预测的块，则预测像素对最终图像的贡献如下：
这实际上产生了一个出人意料的好近似值。但仅有预测像素是不够的。否则，我们只能从左上角的黑色块进行预测，而整个图像都会被预测为黑色。我们需要更多的数据来支持预测，并在预测错误时对其进行修正。校正后的像素还允许未来块中的预测做得更好(如上所述)。
这些校正被称为残差，在这里它们不是作为直接像素值存储的，而是作为离散余弦变换(DCT)计算的系数，离散余弦变换是离散傅立叶变换(DFT)的近亲。前者只使用实数，而后者可以使用复数来计算。
DCT是JPEG格式和大多数视频编解码器的核心。我们很快就会详细介绍它是如何工作的，但现在要知道的关键是它是可逆的，相对于量化是相对健壮的，并且在量化之后，自然图像的数据可以相当稀疏。
由于它们可以是如此稀疏，该格式使用游程长度编码的形式来存储已量化为零的系数组。系数(162-175)的解码开始于将工作缓冲器中的空间清零，然后在非零系数上循环。对于每个1，它首先解码单个位，该位标记块中的最后一个非零系数是否已被读取。然后，它读取要跳过的零系数的数目。然后，它读取量化级别(即，在将原始系数除以量化步长之后的商)。由于熵编码方案只存储无符号整数，因此这部分涉及读取符号位。最后，由于这是一种简单的无死区的中间均匀量化方案，因此只需将电平与量化步长相乘，然后解码，即可重构系数
.