arm - 运行长度编码 - SIMD

Question

我正在尝试优化运行长度编码。我正在考虑在 SIMD 中实现它。我花了几个小时在算法上工作，但没有太多进展。值得试一试吗？我正在研究霓虹灯。

谢谢。

Answer 1

我假设您的问题与 JPEG 中 AC 块系数编码中的 RLE 有关。

JPEG 中使用的 RLE 的变体非常具体。每个 8x8 像素块都用 DCT 进行转换和量化。然后将 DCT 输出（64 个系数）分离为第一个 DC 系数和 63 个 AC 系数。使用 Zig-Zag 模式将 8x8 块 AC 系数转换为线性阵列，然后进行 RLE 编码

ZigZag 通常与 RLE 运行结合使用，因此我们有具有非线性内存访问的 RLE，并且应该优化这两个功能。

警告！JPEG 中的 RLE 仅用于零元素！请查看ISO/IEC 10918-1 : 1993标准的F.1.2.2.1、 F.1.2.2.3和图 F.2 。

一些实现：

有libjpeg-tubro（主页是libjpeg-turbo.org），其中一些分支由 Linaro 在 2010-2011 年针对 ARM进行了优化。

此分叉中有优化列表：

• 10 - 'forward_DCT' 中量化代码的 ARM NEON 优化（整数除法替换为浮点乘法。......这个优化的函数现在几乎比原始 C 变体快 3 倍 - jcdctmgr.c - Siarhei Siamashka 2010-11-10
• 9 - 'encode_one_block' 的ARM 程序集优化（'encode_one_block' 的 ARM 程序集优化。几乎比原始 C 变体快 2 倍。） - jchuff.c - Siarhei Siamashka 2010-11-10
• 8 - 'rgb_ycc_convert' 的 ARM NEON 优化版本 - Siarhei Siamashka 2010-11-10
• 7 - 'ycc_rgb_convert' 的 ARM NEON 优化版本 - Siarhei Siamashka 2010-11-10
• 6 - “convsamp”的小 ARM NEON 优化 - Siarhei Siamashka 2010-11-10
• 5 - 'jpeg_fdct_ifast' 的 ARM NEON 优化版本 - Siarhei Siamashka 2010-11-10
• 4 - 'jpeg_idct_ifast' 的 ARM NEON 优化版本 - Siarhei Siamashka 2010-11-10
• 3 - 'jpeg_idct_4x4' 的 ARM NEON 优化版本 - Siarhei Siamashka 2010-11-10

修订版 9是jchuff.c文件的 ARM 优化，用于函数encode_one_block，它对块的 AC 和 DC 分量进行编码；但它是在不使用 NEON 的情况下完成的

/* Encode a single block's worth of coefficients */
LOCAL(boolean)   encode_one_block 

事实上，RLE 并没有优化；但是 ZigZag 和最后一个零系数检测是在 ARM 程序集中的 find_last_nonzero_index辅助函数中实现的。（它是使用ruby​​ generator 生成的）或在 linaro git 中生成。它计划用于双发 Cortex-A8：

* Find last nonzero coefficient and produce output in natural order,
* instructions are scheduled to make use of ARM Cortex-A8 dual-issue
* capability

这是函数对应的C代码：

LOCAL(int)
find_last_nonzero_index (JCOEFPTR block, JCOEFPTR out)
{
  int tmp, i, n = 0;
  for (i = 1; i < DCTSIZE2; i++) {
    if ((tmp = block[jpeg_natural_order[i]]) != 0)
      n = i;
    out[i] = tmp;
}
return n;

这里有 RLE 本身的 ARM 或 NEON 优化，但我认为这个 asm 代码有助于 RLE，将其转换为线性内存访问版本（encode_one_block, under ifdef __arm__）：

  for (k = 2; k <= last_nonzero_index; k += 2) {
      innerloop(k);
  }

rinnerloop宏中使用的是 RLE 计数器。

这种带有手动编码之字折线（用于 Cortex-A8）的线性 RLE 应该比原始 C 版本更快，即使对于 Cortex-A9 也是如此。感谢 Siarhei Siamashka！

PS：当前版本的 libjpeg-turbo 在这个 RLE 中没有 arm 优化：encode_one_blockjchuff.c 的第 454 行，rev929 - innerloop 被稍微改写为kloop，但 RLE 仍然以非线性方式完成；之字形不与它分开。

关于NEON的一些想法

NEON 有一组 32 个寄存器，每个 64 位宽（D0..D31；根据 Anderson @ ELC 2011，第 5 页），理论上，可用于存储 64 个 16 位系数并实现 ZigZag+RLE。仍在寻找实现...

MPEG 标准中有类似的 zig-zag + RLE，在 x86 和 arm 上也有一些 SIMD 实现的努力。x264dev中有一篇博文；8x8 zigzag x264_zigzag_scan_8x8_frame是为带有 SSSE3 的 x86 实现的。但是对于 ARM，x264 中只有4x4 NEON zigzag。

PS：仅适用于我和任何不了解 Jpeg 内部结构的人。Cardiff CM0340 讲座幻灯片中对 JPEG 编码进行了简短易懂的介绍。

PPS（2013 年 2 月 18 日 13:30 更新）：为了优化 RLE 编码，我们可以进行预扫描，在 AC 系数中间搜索零，然后使用这些预先计算的数据。我们甚至可以将它保存为半字节或一些 NEON regs 中的位

2 月 18 日更新：补丁作者说提交 9 的评论不准确。将此代码与 jpeg6b（而不是 libjpeg-turbo）进行比较时，改进了 2 倍。他说 unroll by 63（如在 libjpeg-tubro 中）与这个 asm 解决方案的速度几乎相同（在某些测试中，它在其他测试中稍好一些）。