The copy tracking in the current code is very simplistic and basically just keeps track of one copied area at a time. This seemed insufficient so the last few weeks I've been playing with a more advanced tracker that catches more or less everything.
Unfortunately, it seems all of it might have been a wasted effort. The new code catches some extra copies, but not enough to warrant the extra complexity and CPU time. I'm posting the patch here anyway for posterity. Please test it though and see if you find any scenarios where there is an noticeable improvement over the existing code. Rgds -- Pierre Ossman OpenSource-based Thin Client Technology System Developer Telephone: +46-13-21 46 00 Cendio AB Web: http://www.cendio.com
Index: common/rfb/ComparingUpdateTracker.cxx
===================================================================
--- common/rfb/ComparingUpdateTracker.cxx (revision 3829)
+++ common/rfb/ComparingUpdateTracker.cxx (working copy)
@@ -39,6 +39,7 @@
void ComparingUpdateTracker::compare()
{
+ UpdateCopyList::const_iterator cli;
std::vector<Rect> rects;
std::vector<Rect>::iterator i;
@@ -54,18 +55,24 @@
}
firstCompare = false;
} else {
- copied.get_rects(&rects, copy_delta.x<=0, copy_delta.y<=0);
- for (i = rects.begin(); i != rects.end(); i++)
- oldFb.copyRect(*i, copy_delta);
+ Region to_check = changed;
- Region to_check = changed.union_(copied);
+ for (cli = copied.begin();cli != copied.end();++cli) {
+ cli->first.get_rects(&rects, cli->second.x<=0, cli->second.y<=0);
+ for (i = rects.begin(); i != rects.end(); i++)
+ oldFb.copyRect(*i, cli->second);
+
+ to_check.assign_union(cli->first);
+ }
+
to_check.get_rects(&rects);
Region newChanged;
for (i = rects.begin(); i != rects.end(); i++)
compareRect(*i, &newChanged);
- copied.assign_subtract(newChanged);
+ subtract_copied(newChanged);
+
changed = newChanged;
}
}
Index: common/rfb/UpdateTracker.cxx
===================================================================
--- common/rfb/UpdateTracker.cxx (revision 3829)
+++ common/rfb/UpdateTracker.cxx (working copy)
@@ -71,86 +71,185 @@
void SimpleUpdateTracker::enable_copyrect(bool enable) {
if (!enable && copy_enabled) {
- add_changed(copied);
+ UpdateCopyList::const_iterator cli;
+ for (cli = copied.begin();cli != copied.end();++cli)
+ add_changed(cli->first);
copied.clear();
}
copy_enabled=enable;
}
void SimpleUpdateTracker::add_changed(const Region ®ion) {
+ if (region.is_empty())
+ return;
changed.assign_union(region);
+ subtract_copied(region);
}
void SimpleUpdateTracker::add_copied(const Region &dest, const Point &delta) {
+ UpdateCopyList::iterator cli, ncli, smallest;
+ UpdateCopyList new_copies;
+ Region src, new_changed;
+
+ // Is there anything to do?
+ if (dest.is_empty())
+ return;
+
// Do we support copyrect?
if (!copy_enabled) {
add_changed(dest);
return;
}
- // Is there anything to do?
- if (dest.is_empty()) return;
-
- // Calculate whether any of this copy can be treated as a continuation
- // of an earlier one
- Region src = dest;
+ // We cannot copy from an area that's been modified since the last
+ // update
+ src = dest;
src.translate(delta.negate());
- Region overlap = src.intersect(copied);
+ new_changed = src.intersect(changed);
+ src.assign_subtract(new_changed);
+ new_changed.translate(delta);
- if (overlap.is_empty()) {
- // There is no overlap
-
- Rect newbr = dest.get_bounding_rect();
- Rect oldbr = copied.get_bounding_rect();
- if (oldbr.area() > newbr.area()) {
- // Old copyrect is (probably) bigger - use it
- changed.assign_union(dest);
- } else {
- // New copyrect is probably bigger
- // Use the new one
- // But be careful not to copy stuff that still needs
- // to be updated.
- Region invalid_src = src.intersect(changed);
- invalid_src.translate(delta);
- changed.assign_union(invalid_src);
- changed.assign_union(copied);
- copied = dest;
- copy_delta = delta;
- }
+ // Anything left?
+ if (src.is_empty()) {
+ add_changed(new_changed);
return;
}
- Region invalid_src = overlap.intersect(changed);
- invalid_src.translate(delta);
- changed.assign_union(invalid_src);
-
- overlap.translate(delta);
+ // See if we copy from a copy and adjust the source if so
+ // (this can split up the copy into several ones)
+ for (cli = copied.begin();cli != copied.end();++cli) {
+ Region overlap;
+ Point newdelta;
- Region nonoverlapped_copied = dest.union_(copied).subtract(overlap);
- changed.assign_union(nonoverlapped_copied);
+ overlap = src.intersect(cli->first);
+ if (overlap.is_empty())
+ continue;
- copied = overlap;
- copy_delta = copy_delta.translate(delta);
+ // Remove the overlap from the current region
+ src.assign_subtract(overlap);
- return;
+ // Compute the new copy
+ overlap.translate(delta);
+ newdelta = cli->second.translate(delta);
+
+ // And store it for later
+ new_copies.push_back(UpdateCopy(overlap, newdelta));
+
+ // Anything left?
+ if (src.is_empty())
+ break;
+ }
+
+ // Anything left of the original copy?
+ if (!src.is_empty()) {
+ Region newdest;
+
+ // Recreate the dest
+ newdest = src;
+ newdest.translate(delta);
+
+ // Add it to the list to handle
+ new_copies.push_back(UpdateCopy(newdest, delta));
+ }
+
+
+ //////// HERE WE START MODIFYING THE LIST OF COPIES ////////
+
+
+ // Handle any changes we've gotten earlier
+ add_changed(new_changed);
+
+ for (ncli = new_copies.begin();ncli != new_copies.end();++ncli) {
+ // An area copied to is no longer changed
+ changed.assign_subtract(ncli->first);
+
+ // Try to find an existing entry with the same delta
+ for (cli = copied.begin();cli != copied.end();++cli) {
+ if (cli->second.equals(ncli->second)) {
+ cli->first.assign_union(ncli->first);
+ break;
+ }
+ }
+
+ // We have handled this entry, so continue with the next
+ if (cli != copied.end())
+ continue;
+
+ // Remove any overlaps in older copies
+ subtract_copied(ncli->first);
+
+ // We put a limit on the number of copies we track so that we don't
+ // gobble up too much memory and cpu
+ if (copied.size() >= 20) {
+ smallest = copied.begin();
+
+ // Find the smallest copy
+ for (cli = copied.begin();cli != copied.end();++cli) {
+ if (smallest->first.get_bounding_rect().area() >
+ cli->first.get_bounding_rect().area())
+ smallest = cli;
+ }
+
+ // If the new copy is smaller, then just abort
+ if (smallest->first.get_bounding_rect().area() >
+ ncli->first.get_bounding_rect().area()) {
+ changed.assign_union(ncli->first);
+ continue;
+ }
+
+ // Otherwise replace the smallest copy
+ changed.assign_union(smallest->first);
+ *smallest = *ncli;
+
+ continue;
+ }
+
+ // Add new entry in the list
+ copied.push_back(*ncli);
+ }
}
void SimpleUpdateTracker::subtract(const Region& region) {
- copied.assign_subtract(region);
changed.assign_subtract(region);
+ subtract_copied(region);
}
void SimpleUpdateTracker::getUpdateInfo(UpdateInfo* info, const Region& clip)
{
- copied.assign_subtract(changed);
+ UpdateCopyList::const_iterator cli;
+ Region clipped;
+
info->changed = changed.intersect(clip);
- info->copied = copied.intersect(clip);
- info->copy_delta = copy_delta;
+
+ info->copied.clear();
+
+ for (cli = copied.begin();cli != copied.end();++cli) {
+ clipped = cli->first.intersect(clip);
+ if (clipped.is_empty())
+ continue;
+
+ info->copied.push_back(UpdateCopy(clipped, cli->second));
+ }
}
void SimpleUpdateTracker::copyTo(UpdateTracker* to) const {
- if (!copied.is_empty())
- to->add_copied(copied, copy_delta);
+ if (!copied.empty()) {
+ UpdateCopyList::const_iterator cli;
+ for (cli = copied.begin();cli != copied.end();++cli)
+ to->add_copied(cli->first, cli->second);
+ }
if (!changed.is_empty())
to->add_changed(changed);
}
+
+void SimpleUpdateTracker::subtract_copied(const Region& region) {
+ UpdateCopyList::iterator cli, cli_next;
+
+ for (cli = copied.begin();cli != copied.end();cli = cli_next) {
+ cli_next = cli; cli_next++;
+
+ cli->first.assign_subtract(region);
+ if (cli->first.is_empty())
+ copied.erase(cli);
+ }
+}
Index: common/rfb/UpdateTracker.h
===================================================================
--- common/rfb/UpdateTracker.h (revision 3829)
+++ common/rfb/UpdateTracker.h (working copy)
@@ -23,15 +23,19 @@
#include <rfb/Region.h>
#include <rfb/PixelBuffer.h>
+#include <list>
+
namespace rfb {
+ typedef std::pair<Region, Point> UpdateCopy;
+ typedef std::list<UpdateCopy> UpdateCopyList;
+
class UpdateInfo {
public:
Region changed;
- Region copied;
- Point copy_delta;
+ UpdateCopyList copied;
bool is_empty() const {
- return copied.is_empty() && changed.is_empty();
+ return copied.empty() && changed.is_empty();
}
// NOTE: We do not ever use UpdateInfo::numRects(), because Tight encoding
// complicates computing the number of rectangles.
@@ -85,15 +89,16 @@
virtual void copyTo(UpdateTracker* to) const;
// Move the entire update region by an offset
- void translate(const Point& p) {changed.translate(p); copied.translate(p);}
+ //void translate(const Point& p) {changed.translate(p); copied.translate(p);}
- virtual bool is_empty() const {return changed.is_empty() && copied.is_empty();}
+ virtual bool is_empty() const {return changed.is_empty() && copied.empty();}
virtual void clear() {changed.clear(); copied.clear();};
protected:
+ virtual void subtract_copied(const Region& region);
+ protected:
Region changed;
- Region copied;
- Point copy_delta;
+ UpdateCopyList copied;
bool copy_enabled;
};
Index: common/rfb/SMsgWriter.cxx
===================================================================
--- common/rfb/SMsgWriter.cxx (revision 3829)
+++ common/rfb/SMsgWriter.cxx (working copy)
@@ -145,15 +145,20 @@
void SMsgWriter::writeRects(const UpdateInfo& ui, ImageGetter* ig,
Region* updatedRegion)
{
+ UpdateCopyList::const_iterator cli;
std::vector<Rect> rects;
std::vector<Rect>::const_iterator i;
+
updatedRegion->copyFrom(ui.changed);
- updatedRegion->assign_union(ui.copied);
- ui.copied.get_rects(&rects, ui.copy_delta.x <= 0, ui.copy_delta.y <= 0);
- for (i = rects.begin(); i != rects.end(); i++)
- writeCopyRect(*i, i->tl.x - ui.copy_delta.x, i->tl.y - ui.copy_delta.y);
+ for (cli = ui.copied.begin();cli != ui.copied.end();++cli) {
+ cli->first.get_rects(&rects, cli->second.x <= 0, cli->second.y <= 0);
+ for (i = rects.begin(); i != rects.end(); i++)
+ writeCopyRect(*i, i->tl.x - cli->second.x, i->tl.y - cli->second.y);
+ updatedRegion->assign_union(cli->first);
+ }
+
ui.changed.get_rects(&rects);
for (i = rects.begin(); i != rects.end(); i++) {
Rect actual;
Index: common/rfb/VNCServerST.cxx
===================================================================
--- common/rfb/VNCServerST.cxx (revision 3829)
+++ common/rfb/VNCServerST.cxx (working copy)
@@ -523,6 +523,8 @@
void VNCServerST::checkUpdate()
{
UpdateInfo ui;
+ UpdateCopyList::const_iterator cli;
+
comparer->getUpdateInfo(&ui, pb->getRect());
bool renderCursor = needRenderedCursor();
@@ -530,7 +532,9 @@
if (ui.is_empty() && !(renderCursor && renderedCursorInvalid))
return;
- Region toCheck = ui.changed.union_(ui.copied);
+ Region toCheck = ui.changed;
+ for (cli = ui.copied.begin();cli != ui.copied.end();++cli)
+ toCheck.assign_union(cli->first);
if (renderCursor) {
Rect clippedCursorRect
@@ -566,7 +570,10 @@
std::list<VNCSConnectionST*>::iterator ci, ci_next;
for (ci = clients.begin(); ci != clients.end(); ci = ci_next) {
ci_next = ci; ci_next++;
- (*ci)->add_copied(ui.copied, ui.copy_delta);
+ // Copies first as an UpdateTracker will not copy from a
+ // changed area.
+ for (cli = ui.copied.begin();cli != ui.copied.end();++cli)
+ (*ci)->add_copied(cli->first, cli->second);
(*ci)->add_changed(ui.changed);
}
Index: common/rfb/VNCSConnectionST.cxx
===================================================================
--- common/rfb/VNCSConnectionST.cxx (revision 3829)
+++ common/rfb/VNCSConnectionST.cxx (working copy)
@@ -628,6 +628,9 @@
void VNCSConnectionST::writeFramebufferUpdate()
{
+ UpdateInfo ui;
+ UpdateCopyList::const_iterator cli;
+
if (state() != RFBSTATE_NORMAL || requested.is_empty())
return;
@@ -647,7 +650,6 @@
// getUpdateInfo() will normalize the `updates' object such way that its
// `changed' and `copied' regions would not intersect.
- UpdateInfo ui;
updates.getUpdateInfo(&ui, requested);
bool needNewUpdateInfo = false;
@@ -655,12 +657,16 @@
// copy, then when the copy happens the corresponding rectangle in the
// destination will be wrong, so add it to the changed region.
- if (!ui.copied.is_empty() && !renderedCursorRect.is_empty()) {
- Rect bogusCopiedCursor = (renderedCursorRect.translate(ui.copy_delta)
+ if (!ui.copied.empty() && !renderedCursorRect.is_empty()) {
+ Rect bogusCopiedCursor;
+
+ for (cli = ui.copied.begin();cli != ui.copied.end();++cli) {
+ bogusCopiedCursor = (renderedCursorRect.translate(cli->second)
.intersect(server->pb->getRect()));
- if (!ui.copied.intersect(bogusCopiedCursor).is_empty()) {
- updates.add_changed(bogusCopiedCursor);
- needNewUpdateInfo = true;
+ if (cli->first.intersect(bogusCopiedCursor).is_empty()) {
+ updates.add_changed(bogusCopiedCursor);
+ needNewUpdateInfo = true;
+ }
}
}
@@ -696,9 +702,15 @@
if (renderedCursorRect.is_empty()) {
drawRenderedCursor = false;
- } else if (!ui.changed.union_(ui.copied)
- .intersect(renderedCursorRect).is_empty()) {
- drawRenderedCursor = true;
+ } else {
+ Region changed;
+
+ changed = ui.changed;
+ for (cli = ui.copied.begin();cli != ui.copied.end();++cli)
+ changed.assign_union(cli->first);
+
+ if (!changed.intersect(renderedCursorRect).is_empty())
+ drawRenderedCursor = true;
}
// We could remove the new cursor rect from updates here. It's not clear
@@ -716,8 +728,7 @@
// Compute the number of rectangles. Tight encoder makes the things more
// complicated as compared to the original VNC4.
writer()->setupCurrentEncoder();
- int nRects = (ui.copied.numRects() +
- (drawRenderedCursor ? 1 : 0));
+ int nRects = drawRenderedCursor ? 1 : 0;
std::vector<Rect> rects;
std::vector<Rect>::const_iterator i;
@@ -726,7 +737,10 @@
if (i->width() && i->height())
nRects += writer()->getNumRects(*i);
}
-
+
+ for (cli = ui.copied.begin();cli != ui.copied.end();++cli)
+ nRects += cli->first.numRects();
+
writer()->writeFramebufferUpdateStart(nRects);
Region updatedRegion;
writer()->writeRects(ui, &image_getter, &updatedRegion);
signature.asc
Description: PGP signature
------------------------------------------------------------------------------ OpenSolaris 2009.06 is a cutting edge operating system for enterprises looking to deploy the next generation of Solaris that includes the latest innovations from Sun and the OpenSource community. Download a copy and enjoy capabilities such as Networking, Storage and Virtualization. Go to: http://p.sf.net/sfu/opensolaris-get
_______________________________________________ Tigervnc-devel mailing list Tigervnc-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/tigervnc-devel
