Jan 4

iDOT:iOS/OSX的PNG多线程解码提速格式(About Precise Format of iDOT Chunk)

Lrdcq , 2022/01/04 23:22 , 程序 , 閱讀(1442) , Via 本站原創
最近网络上有这么一个帖子:https://www.da.vidbuchanan.co.uk/widgets/pngdiff/。其中展示了一张图片,下半部分在苹果的系统与其他系统上展示不一致,其中的讨论使用苹果系统(包括iOS/OS X)设计的一种私有png chunk即iDOT,在mac上通过系统截屏截取的png就可以看到这个chunk。

目前网络上能搜到关于iDOT的描述,都是以截图的这种png为基准,分析出png分为两段的情况下,双线程解析png是iDOT是如何描述的(https://www.hackerfactor.com/blog/index.php?/archives/895-Connecting-the-iDOTs.html),不过其中还包含大量不准确(unknown)的字段,并且也不清晰如何描述分为两段以上即开启更多线程解析的方式。因此本次笔者经过逆向分析,得到了准确的多线程iDOT数据结构与全部字段含义,与一部分苹果的png decoder的iDOT校验逻辑,希望对后续该格式利用有所帮助。

Demo图片:(第三方浏览器是自带png decoder的,要看苹果渲染效果,请另存为到设备上查看)
點擊在新視窗中瀏覽此圖片

该图片被分为纵向3段(苹果会3线程解析);假设苹果设备看到的3段为A / B / C,其他普通设备(或者自带decoder的软件如chrome)看到的是A / C / B;IDAT中几乎没有多余数据,对比ABC本身连在一起的普通png的文件大小:

- iDOT png:411,598 字节
- Normal png:409,438 字节

本文从3个部分描述:标准的png核心数据解析过程与多线程解析的原理,iDOT如何描述多线程解析的,苹果实际多线程解析的性能与应用前景

png解析过程(基础)

我们一般认为png从设计上是必须顺序式或者说是流式解析的。首先png本身是一chunk为单位组织起来的,一个最简单的png需要IHDR chunk来描述png基本信息,IDAT chunk来描述像素数据,IEND chunk来表示文件结束。显然这三者是有明显的顺序关系的。阅读png format文档,大部分chunk都有顺序关系才能根据前文信息有效的进行图片解析。

png的主体数据既像素数据储存在IDAT chunk里。一个png内可以包含一个或者多个IDAT chunk,他们的data部分即png核心数据流,多个IDAT的情况是所有data串在一起构成这个数据流,因此正常解析下多个IDAT和单个IDAT chunk其实没区别,遇到IDAT把data往流里塞就好。

而IDAT的数据流储存的是一个标准的LZ77压缩数据,也就是常说的标准zip数据,通过zlib默认的decompress流去解压,输出的就是png的像素数据了。我们知道lz77这种压缩格式是需要顺序式压缩或者解压的,因此压缩逻辑确定了IDAT必须顺序解析。

解压出来的像素数据就能直接从中取出某一个像素了或者从中截取一个区域生成位图了么?还是不行的,要把这个数据换为位图,还涉及到png的像素数据是有逐行滤波的(Filter Algorithms,http://www.libpng.org/pub/png/spec/1.2/PNG-Filters.html),也就是说一行数据的实际像素有可能是上一行的实际像素加上本行的数据通过滤波算法计算得到的。因此要得到实际位图数据,需要将解压出的png像素数据从上到下逐行解析,才能得到实际的像素数据。
點擊在新視窗中瀏覽此圖片

以上一系列过程即png的解码过程,显然是必须串行在cpu中完成的(显然也不适合在gpu中执行),执行后得到位图再进行渲染的成本相对来说就是小巫见大巫了,因此一般我们所说多线程解析,也是期望将这个过程多线程化。

iDOT设计

显然根据上面这个过程,要实现多线程png解码,要解决上面三个过程的并发解析的问题。从技术角度,这三个问题均有以下解决办法:

- chunk结构顺序读取问题:如果要多线程读取chunk,那么读取到png开始部分,我们就需要知道我们可以跳跃文件多少offset可以进行并发读取。由于IHDR确实没有预留这么一些字段信息,因此我们需要新增一个功能类似于IHDR的chunk来描述,文件跳跃到offset多少的位置开始,可以并发读取。——这也就是iDOT这个chunk的由来。

- 对于zlib解压是否可以支持并行,能依赖压缩时的一个功能:加入Z_FULL_FLUSH切断压缩流(注意不是Z_SYNC_FLUSH),full flush的设计目的即“the compression state is reset so that decompression can restart from this point if previous compressed data has been damaged or if random access is desired. ”因此full flush之后的位置可以视为一次新的压缩流的起始点,因此依赖这个点就可以进行前后两段的多线程解压。当然如果我们对数据不断的通过full flush进行切割,就能实现更多线程解压了。当然做了full flush由于压缩状态被重置,肯定相对于完整压缩会有更多冗余数据从而影响压缩率,所谓鱼和熊掌不可兼得。

- 对于像素数据逐行滤波,需要顺序解析的原因是,部分滤波算法是依赖上一行解析完成的像素数据的,如果多线程解析,显然多线程切断处的第一行像素解析无法执行下去。当然,解决方法也很简单——也存在两种滤波【0x00:None】与【0x01:Sub】是不依赖上一行的,因此只需要保证并行切割的位置的第一行像素数据的滤波类型是0x00或者0x01就可以完美解决了。

根据以上思路,自然而然得到的解决方案,就是苹果的iDOT chunk了。iDOT是一个紧跟在IHDR之后IDAT之前,描述苹果设备上多线程解析功能的一个私有chunk,其中包含的即上面我们所需要的全部信息。经过笔者逆向与各种测试,具体格式如下:
點擊在新視窗中瀏覽此圖片

上图分别描述了iDOT的结构,与iDOT的数据在png文件结构与png渲染中的含义。详细描述:

- 【分段信息】Height Divisor即纵向分段数,描述图片被纵向分割为了多少个段落来进行多线程解析。当然如果是1就没意义了,网络上能看到的所有含有iDOT的图片这里都是2,因为苹果设备目前实际能看到的都是生成的2的图片。当然实际测试出这里可以是2以上的数字,并且和后续section array的数据有关。当然,这个数字不可能是无限大的,测试后虽然没有报错,但是显然线程数过多对于png解析的性能必然打折扣的。如果这个数字与后续section array的长度即iDOT的长度不符,则会认为iDOT chunk无效,进入普通png解析逻辑。

- 【分段信息】Flags应该是一个预留的标志位,经测试对这个值的修改对iDOT的解析没有什么影响。

- 【分段信息】Default Section Hight即默认段高度,即多线程解析的首段的渲染高度。这一段开始的位置固定为0。如果这个值大于图片高度,也会认为iDOT无效。

- 【分段信息】Verify:iDOT Chunk Size:看起来是一个校验字段,写入的是整个iDOT的长度。当然更有可能是下下方的数组长度是依赖Height Divisor与这个值进行联合校验与读取的。如果这个值有误,也会认为iDOT无效。

- 下面进入【分段数组】Section Array区域,这个区域描述的是每一个多线程数据段的具体信息。数组长度是纵向分段数-1,比如纵向分为3段即有2个多线程段落这个数组的长度为2。Section的数组里有3个字段来描述每个section的数据来源与渲染目标。

- 【分段数组】Section Offset与Section Height是这个分段在图片上渲染的起始位置与高度,决定多线程渲染这个区域时,bitmap组合的位置。如果Section Offset+Section Height大于了图片高度,也会进入iDOT无效逻辑。

- 【分段数组】Section IDAT Offset是这个分段的IDAT数据在文件中的offset值,用于多线程处理文件时直接跳转到目标offset。如果这个值大于了文件长度,当然认为iDOT无效。

以上描述了iDOT本身的含义与iDOT Chunk解析过程。同时还有部分周边逻辑,比如iDOT如果包含多个苹果则会认为所有的iDOT均无效,或者iDOT与IDAT之间掺杂了多余chunk也是,错误信息是“Read_user_chunkIDOT:989: invalid PNG file: extra chunks between iDOT and IDAT”,和上面描述的一样,进入iDOT无效逻辑后decoder就会认为这是一个普通的png降级处理了。不过,iDOT在本身的校验之外并没有更严谨的校验了。

随后即根据iDOT进入多线程解析流程了。每一个线程均会执行以下流程:

- 根据Section IDAT Offset值直接跳转到目标offset进行IDAT解析。这个值必须是一个严格的IDAT Chunk才能被解析,否则会出现错误“Read_user_chunkIDOT:1019: invalid PNG file: iDOT doesn't point to valid IDAT chunk”,不过要注意,一旦进入多线程流程,就没有和上面一样降级成普通顺序解析的余地了,因此这里开始发生的错误都会导致图片对应的section渲染为空(既线程返回结果为空并继续后续流程)。

- 当然,解开IDAT后继续对data进行unzip与图像逐行滤波,如果unzip失败(比如实际上截断位置不是一个Z_FULL_FLUSH的切断点),或者逐行滤波出现了不被识别的type,也会渲染失败,错误信息为“imagePNG_error_break:445: *** ERROR: imagePNG_error_break”。

- 随后多线程的结果汇总为多个对应section的位图进行组合渲染,最终在GUI上得到我们所见的图像。

到此为止,iDOT的解析与多线程png解析渲染过程即清楚了。根据以上信息,我们也能得到将一个普通图片转换为一个iDOT多线程解析图片的方式

1. 读取png文件信息,根据高度与输入的切断信息进行section规划。比如一张height=800的图片,我们切断为[0, 266],[267, 532],[533, 799]三段。

2. 读取原始图片的IDAT信息,并且进行unzip还原为像素数据(包含滤波)。

3. 由于上文提到的滤波切断问题,需要关注切断的行,即第267行与533行的像素数据是否是0x00与0x01以外的滤波类型,如果是则需要将这两行的数据进行更换。最简单并且准确的方式是还原为0x00类型的原始像素数据,因此如果要进行这个过程,拷贝一份2步骤得到的像素数据(包含滤波),并且执行一次滤波还原,得到真实像素数据,再从中摘取目标行的数据替换进入即可。

4. 对修改完成的像素数据重新进行打包,不过此时需要按切分的段数在zip流中打包为n段,直到最后一段前,每一段数据流完成就执行一次zlibobj.flush(zlib.Z_FULL_FLUSH)对流进行切割。最后得到n段压缩数据。

5. 最后生成png chunk。其中png中的除了IDAT以外的chunk按原样拷贝到新png中,只在IHDR之后IDAT前按格式加入iDOT,同时写入IDAT过程中,将数据写入过程当成3次压缩数据连续写入png中,最后根据实际写入的信息维护一下iDOT中的Section IDAT Offset即可。

写入过程中也尝试了一些特殊情况来观察苹果的png decoder是如何处理iDOT的,如:

- 如果section之间的offset和height并不是连续的,即上文切分的三段不是[0, 266],[267, 532],[533, 799]三段,而是类似于[0, 100],[267, 400],[533, 700]这样的数据,会发生什么——decoder会正常按数据执行渲染,渲染的间隙产生空白区域,(但是在Preview.app中观察可能还会产生其他的渲染错误)如下图:
點擊在新視窗中瀏覽此圖片

- 既然Section IDAT Offset是一个纯粹的文件指针,能否指向不符合合理使用预期的位置呢。测试了以下几种情况:a. IDAT实际像素位置在正常像素区域以外:可以正常读取,这也是最上面Andrord和iOS查阅的不同图片的原理,普通decoder顺序解码查阅到图片上下两部分X+Y,但是我们拼接了像素Z在最末尾并且iDOT直接指向了Z,因此苹果decoder渲染出来为X+Z,当然文件中实际IDAT排列是X+Y+Z。b. 是否可以将IDAT顺序交换呢:可以比如本文贴的DEMO图,数据分为三段但是后两段IDAT实际顺序和iDOT中的顺序相反,因此正常的decoder看到的X+Y+Z但是苹果decoder看到的X+Z+Y。c. 可否将iDOT多个分段指向同一个IDAT位置:可以执行,但是多线程解析同一份数据显然吃力不讨好没有必要。d. iDOT能否指向在非Chunk数据中储存的IDAT:可以,如IDAT实际在IEND后面,一般的png遇到IEND就不会进行解析呢,但是iDAT由于强制指定offset因此可以正常执行;同时也测试了在一个自定义chunk的data内写入的一个IDAT,这样的IDAT正常是无法被读取到的,但是由于iDOT的指定,emmm也能读取了。

性能与应用前景

既然是多线程解析png,并且我们已经解锁了n线程能力,那么必然需要测评。因此在本机上进行了iDOT png转码并通过iOS模拟器计算了当前(iOS15)将图片从资源(本地url)中加载直到推入渲染完成的耗时。

- 使用了两张样本图片来代表照片级大图与常用小图,分别是(大图5083 × 3389 27.3 MB,小图654 × 578 51KB)
- 对样本图片转换为了2-5分段即能够开启2-5线程的iDOT png
- 在能耗稳定的情况下进行了5次渲染测试
- 计算平均值与相对于单线程渲染的耗时优化比

实际测试结果如下:

點擊在新視窗中瀏覽此圖片

- 无论是大图还是小图,多线程解析在耗时上有相当明确的提升

- 只是如预期小图的提升并没有大图那么明显,但是到了5线程也能有50%以上的性能提升。当然更小的图(比如icon类型)应该就完全不明显了。

- 同理目前看到4-5线程时性能还有一定提升(均为4%左右),但是和设备相关或者当前设备繁忙情况线程阈值肯定会继续向前,因此实际有可能4线程左右就是实际应用的最佳解了,需要在实际应用场景中才能得到结论。

- 测试中注意到IDAT chunk的顺序也对加载耗时有所影响,原理上如果文件能按加载顺序顺序排列,系统seek文件效率最高。当然如果有问题越大的文件影响越明显。但是实际上如果正常对IDAT按照iDOT顺序进行编码,自然就是最优的情况了,所以无需特意优化。

既然测试结果是显然正向的,原理上我们可以无脑对iOS应用全面上线该特性,当然前景应用上有针对性会更好。

- 对于iOS应用内置的静态图,无脑转换为iDOT图片是显然合理的。a. 内置图片均不会有太大的io瓶颈或延迟,因此实际提升结果会和如上测试结果相似。b. 内置图片包含launch图等大图资源,能带来更大的收益。

- 对于网络图片,可以考虑从cdn支持的方式,在cdn统一转换为iDOT图片(请求头上带有platform=ios的实际为png的cdn请求,均在cdn侧进行转码并缓存)。

- 如果cdn支持做不到,至少对于大尺寸png图片(特别是ugc的png图片)进行改操作。可以大大缓解少数性能恶劣的场景(如ugc查看大图)的图片渲染耗时。同理,启动图/开屏广告/首页弹窗这样的场景,本身也是网络图缓存到本地使用,同时使用阶段对耗时也相对敏感,我们也对启动指标敏感,因此对于该类型图片资源也是重点优化的方向。

- 另外这个思路也可以拓展到苹果以外的系统上,毕竟要做到png多线程解析,自行设计的结果应该和苹果iDOT的设计与实现八九不离十。因此在一些执行解析png(通过libpng)的场景(如类浏览器render,apng解码等),完全可以自己png decoder进行拓展,以iDOT的形式来支持多线程png解析。

——————

本文附件包含生成上文demo图的python脚本。改脚本逻辑稍作拓展即可以完成一个普通png转换为iDOT png的encoder。不过实测python进行运算密集操作性能确实不行,改写为c++可能才是正解。

——————

补充2:测试性能的代码整理后上传到github上了,仅供参考:
https://github.com/luoruidong/idot-png-encoder

——————

补充3:视频版:https://lrdcq.com/me/read.php/159.htm
关键词:ios , mac , 苹果 , idot , chunk , png , 多线程 , 解码 , 提速
logo