From ae38d967ea4aac937e6fce5c0aa00a4fc552b637 Mon Sep 17 00:00:00 2001 From: Mark Mielke Date: Sun, 21 Jun 2020 23:54:55 -0400 Subject: [PATCH] Enhanced ComparingUpdateTracker to crop changed blocks 64x64 changed block can be large for fine changes such as cursor movement and typing in terminal windows, or an update to a clock. If the block can be efficiently cropped, this will reduce latency and bandwidth. Every pixel cropped is a pixel less to analyze, encode, transmit, and decode. The previous code already detected the top of the change in order to determine if the block had changed. However, it did not use this information to reduce the size of the change rectangle, nor did it calculate any of the other edges. The new code introduces detection of the other edges, and uses the information to build a reduced area change rectangle. This has the additional effect of reducing the number of discrete pixel values in the change block which may allow a more efficient encoding algorithm to be selected. As this section of code is performance sensitive, the method of detecting the edges has been optimized to quickly fall back to pessimistic values as soon as a single comparison fails on each edge. In the case that full 64x64 block are changing, there will be three extra comparisons per block. In cases where the change rectangle can be reduced from 64x64, the reduced size of the change rectangle represents reduced effort to encode, transfer, and decode the contained pixels. In the case of images with high frequency changes, which specifically includes text, the lossy JPEG encoding can be highly distorted, especially with JPEG level 6 or less. The quick flash from a distorted JPEG to a lossless JPEG can appear as a flickering to some people. This effect was more obvious when the surrounding area is not expected to change, but is being distorted anyways due to being part of the 64x64 blocking algorithm. In the case of a user typing in a terminal window, this change may commonly reduce the number of pixels updated with every character typed from 4096 pixels (64x64) to 640 pixels (32x20) or less. --- common/rfb/ComparingUpdateTracker.cxx | 84 +++++++++++++++++++++++++-- 1 file changed, 80 insertions(+), 4 deletions(-) diff --git a/common/rfb/ComparingUpdateTracker.cxx b/common/rfb/ComparingUpdateTracker.cxx index d5651200..14ed908c 100644 --- a/common/rfb/ComparingUpdateTracker.cxx +++ b/common/rfb/ComparingUpdateTracker.cxx @@ -120,6 +120,10 @@ void ComparingUpdateTracker::compareRect(const Rect& r, Region* newChanged) rdr::U8* 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 @@ -139,19 +143,91 @@ void ComparingUpdateTracker::compareRect(const Rect& r, Region* newChanged) 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) { - // A block has changed - copy the remainder to the oldFb - newChanged->assign_union(Region(Rect(blockLeft, blockTop, - blockRight, blockBottom))); - for (int y2 = y; y2 < blockBottom; y2++) + // 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 rdr::U8* newRowPtr = newPtr + ((changeHeight - 1) * newStrideBytes); + const rdr::U8* 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 rdr::U8* newColumnPtr = newPtr; + const rdr::U8* oldColumnPtr = oldPtr; + while (changeLeft + minCompareWidthInPixels < changeRight) + { + const rdr::U8* newRowPtr = newColumnPtr; + const rdr::U8* 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 rdr::U8* newColumnPtr = newPtr + blockWidthInBytes; + const rdr::U8* oldColumnPtr = oldPtr + blockWidthInBytes; + while (changeLeft + minCompareWidthInPixels < changeRight) + { + newColumnPtr -= minCompareWidthInBytes; + oldColumnPtr -= minCompareWidthInBytes; + + const rdr::U8* newRowPtr = newColumnPtr; + const rdr::U8* 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; } -- 2.39.5