画面転送でVNCがX11 Forwardingより高速な理由

Why

遠隔Linux画面を転送する場合に、Virtual Network Computing(VNC)による転送がX11 Forwardingによる転送よりもかなり高速で気になった。

https://zenn.dev/headwaters/articles/14d0a927fa3759

結論

VNCでは、前フレームとの差分が発生した最小の長方形領域のみを転送しているため。
（時間方向の補間アルゴリズムの恩恵もありそう）

How: TigerVNCの差分検知アルゴリズム

上の記事内では内部的にTigerVNCと呼ばれる仮想デスクトップライブラリが使用されいます。ここで実装されている差分検知アルゴリズムを深堀します。TigerVNCでは、Remote FrameBuffer (RFB) プロトコルという標準化されたプロトコルを実装しています。RFBプロトコルはGUIの遠隔操作通信を定義するプロトコルとのこと。

RFB仕様書(和訳)には、リモート側はホストの要求に応じて更新のあった矩形のピクセルデータを送信することが記載されおり、前フレームとの差分情報のみが転送対象になることがわかります。

RFB仕様には差分検知アルゴリズムの記載がなく、ここが実装側(TigerVNC)の腕の見せ所です。（もし、あったらごめんなさい。）
それでは、TigerVNCでの実装を見てみます。

まず、エントリーポイントの直後でX11のDisplayインスタンスdpyを生成し、画面情報を取得しているようです。Here

if (!(dpy = XOpenDisplay(displayname))) {
    // FIXME: Why not vlog.error(...)?
    fprintf(stderr,"%s: Unable to open display \"%s\"\r\n",
            programName, XDisplayName(displayname));
    exit(1);
}

その画像情報をもとにして、前フレームとの差分検知を行っています。

コードは最後に示します。難解に見えます。
まずは#define BLOCK_SIZE 64の正方形ブロックごとに差分を検知し、その後でさらにブロック内で行と列の単位で差分検知走査を行い、最終的な差分発生矩形領域を計算しているようです。

本当に最小の長方形領域のみを送付している点に驚きました。計算量をある程度犠牲にしてでも通信量を最小にしようという意気込みを感じます。

コードはこちら。Here

void ComparingUpdateTracker::compareRect(const Rect& r, Region* newChanged)
{
  if (!r.enclosed_by(fb->getRect())) {
    Rect safe;
    // Crop the rect and try again
    safe = r.intersect(fb->getRect());
    if (!safe.is_empty())
      compareRect(safe, newChanged);
    return;
  }

  int bytesPerPixel = fb->getPF().bpp/8;
  int oldStride;
  uint8_t* oldData = oldFb.getBufferRW(r, &oldStride);
  int oldStrideBytes = oldStride * bytesPerPixel;

  // Used to efficiently crop the left and right of the change rectangle
  int minCompareWidthInPixels = BLOCK_SIZE / 8;
  int minCompareWidthInBytes = minCompareWidthInPixels * bytesPerPixel;

  for (int blockTop = r.tl.y; blockTop < r.br.y; blockTop += BLOCK_SIZE)
  {
    // Get a strip of the source buffer
    Rect pos(r.tl.x, blockTop, r.br.x, __rfbmin(r.br.y, blockTop+BLOCK_SIZE));
    int fbStride;
    const uint8_t* newBlockPtr = fb->getBuffer(pos, &fbStride);
    int newStrideBytes = fbStride * bytesPerPixel;

    uint8_t* oldBlockPtr = oldData;
    int blockBottom = __rfbmin(blockTop+BLOCK_SIZE, r.br.y);

    for (int blockLeft = r.tl.x; blockLeft < r.br.x; blockLeft += BLOCK_SIZE)
    {
      const uint8_t* newPtr = newBlockPtr;
      uint8_t* oldPtr = oldBlockPtr;

      int blockRight = __rfbmin(blockLeft+BLOCK_SIZE, r.br.x);
      int blockWidthInBytes = (blockRight-blockLeft) * bytesPerPixel;

      // Scan the block top to bottom, to identify the first row of change
      for (int y = blockTop; y < blockBottom; y++)
      {
        if (memcmp(oldPtr, newPtr, blockWidthInBytes) != 0)
        {
          // Define the change rectangle using pessimistic values to start
          int changeHeight = blockBottom - y;
          int changeLeft = blockLeft;
          int changeRight = blockRight;

          // For every unchanged row at the bottom of the block, decrement change height
          {
            const uint8_t* newRowPtr = newPtr + ((changeHeight - 1) * newStrideBytes);
            const uint8_t* oldRowPtr = oldPtr + ((changeHeight - 1) * oldStrideBytes);
            while (changeHeight > 1 && memcmp(oldRowPtr, newRowPtr, blockWidthInBytes) == 0)
            {
              newRowPtr -= newStrideBytes;
              oldRowPtr -= oldStrideBytes;

              changeHeight--;
            }
          }

          // For every unchanged column at the left of the block, increment change left
          {
            const uint8_t* newColumnPtr = newPtr;
            const uint8_t* oldColumnPtr = oldPtr;
            while (changeLeft + minCompareWidthInPixels < changeRight)
            {
              const uint8_t* newRowPtr = newColumnPtr;
              const uint8_t* oldRowPtr = oldColumnPtr;
              for (int row = 0; row < changeHeight; row++)
              {
                if (memcmp(oldRowPtr, newRowPtr, minCompareWidthInBytes) != 0)
                  goto endOfChangeLeft;

                newRowPtr += newStrideBytes;
                oldRowPtr += oldStrideBytes;
              }

              newColumnPtr += minCompareWidthInBytes;
              oldColumnPtr += minCompareWidthInBytes;

              changeLeft += minCompareWidthInPixels;
            }
          }
        endOfChangeLeft:

          // For every unchanged column at the right of the block, decrement change right
          {
            const uint8_t* newColumnPtr = newPtr + blockWidthInBytes;
            const uint8_t* oldColumnPtr = oldPtr + blockWidthInBytes;
            while (changeLeft + minCompareWidthInPixels < changeRight)
            {
              newColumnPtr -= minCompareWidthInBytes;
              oldColumnPtr -= minCompareWidthInBytes;

              const uint8_t* newRowPtr = newColumnPtr;
              const uint8_t* oldRowPtr = oldColumnPtr;
              for (int row = 0; row < changeHeight; row++)
              {
                if (memcmp(oldRowPtr, newRowPtr, minCompareWidthInBytes) != 0)
                  goto endOfChangeRight;

                newRowPtr += newStrideBytes;
                oldRowPtr += oldStrideBytes;
              }

              changeRight -= minCompareWidthInPixels;
            }
          }
        endOfChangeRight:

          // Block change extends from (changeLeft, y) to (changeRight, y + changeHeight)
          newChanged->assign_union(Region(Rect(changeLeft, y, changeRight, y + changeHeight)));

          // Copy the change from fb to oldFb to allow future changes to be identified
          for (int row = 0; row < changeHeight; row++)
          {
            memcpy(oldPtr, newPtr, blockWidthInBytes);
            newPtr += newStrideBytes;
            oldPtr += oldStrideBytes;
          }

          // No further processing is required for this block
          break;
        }

        newPtr += newStrideBytes;
        oldPtr += oldStrideBytes;
      }

      oldBlockPtr += blockWidthInBytes;
      newBlockPtr += blockWidthInBytes;
    }

    oldData += oldStrideBytes * BLOCK_SIZE;
  }

  oldFb.commitBufferRW(r);
}

以上、先人の知恵からでした。