diff --git a/ui/vnc.c b/ui/vnc.c
index 67b1f75..edf33be 100644
--- a/ui/vnc.c
+++ b/ui/vnc.c
@@ -572,6 +572,16 @@ void *vnc_server_fb_ptr(VncDisplay *vd, int x, int y)
     ptr += x * VNC_SERVER_FB_BYTES;
     return ptr;
 }
+/* this sets only the visible pixels of a dirty bitmap */
+#define VNC_SET_VISIBLE_PIXELS_DIRTY(bitmap, w, h) {\
+        int x, y;\
+        memset(bitmap, 0x00, sizeof(bitmap));\
+        for (y = 0; y < h; y++) {\
+            for (x = 0; x < w / VNC_DIRTY_PIXELS_PER_BIT; x++) {\
+                set_bit(x, bitmap[y]);\
+            } \
+        } \
+    }
 
 static void vnc_dpy_switch(DisplayChangeListener *dcl,
                            DisplaySurface *surface)
@@ -597,7 +607,9 @@ static void vnc_dpy_switch(DisplayChangeListener *dcl,
     qemu_pixman_image_unref(vd->guest.fb);
     vd->guest.fb = pixman_image_ref(surface->image);
     vd->guest.format = surface->format;
-    memset(vd->guest.dirty, 0xFF, sizeof(vd->guest.dirty));
+    VNC_SET_VISIBLE_PIXELS_DIRTY(vd->guest.dirty,
+                                 surface_width(vd->ds),
+                                 surface_height(vd->ds));
 
     QTAILQ_FOREACH(vs, &vd->clients, next) {
         vnc_colordepth(vs);
@@ -605,7 +617,9 @@ static void vnc_dpy_switch(DisplayChangeListener *dcl,
         if (vs->vd->cursor) {
             vnc_cursor_define(vs);
         }
-        memset(vs->dirty, 0xFF, sizeof(vs->dirty));
+        VNC_SET_VISIBLE_PIXELS_DIRTY(vs->dirty,
+                                     surface_width(vd->ds),
+                                     surface_height(vd->ds));
     }
 }
 
@@ -882,6 +896,14 @@ static int vnc_update_client_sync(VncState *vs, int has_dirty)
     return ret;
 }
 
+#define VNC_CLIENT_UPDATE_RECT() \
+    if (last_x != -1) {\
+        int h = find_and_clear_dirty_height(vs, y, last_x, x, height);\
+        n += vnc_job_add_rect(job,\
+              last_x * VNC_DIRTY_PIXELS_PER_BIT, y,\
+              (x - last_x) * VNC_DIRTY_PIXELS_PER_BIT, h);\
+    }
+
 static int vnc_update_client(VncState *vs, int has_dirty)
 {
     if (vs->need_update && vs->csock != -1) {
@@ -910,35 +932,32 @@ static int vnc_update_client(VncState *vs, int has_dirty)
         width = MIN(pixman_image_get_width(vd->server), vs->client_width);
         height = MIN(pixman_image_get_height(vd->server), vs->client_height);
 
-        for (y = 0; y < height; y++) {
+        y = 0;
+        for (;;) {
             int x;
             int last_x = -1;
-            for (x = 0; x < width / VNC_DIRTY_PIXELS_PER_BIT; x++) {
+            unsigned long offset = find_next_bit((unsigned long *) &vs->dirty,
+                                                 height * VNC_DIRTY_BITS_PER_LINE(vs),
+                                                 y * VNC_DIRTY_BITS_PER_LINE(vs));
+            if (offset == height * VNC_DIRTY_BITS_PER_LINE(vs)) {
+                /* no more dirty bits */
+                break;
+            }
+            y = offset / VNC_DIRTY_BITS_PER_LINE(vs);
+
+            for (x = offset % VNC_DIRTY_BITS_PER_LINE(vs);
+                 x < width / VNC_DIRTY_PIXELS_PER_BIT; x++) {
                 if (test_and_clear_bit(x, vs->dirty[y])) {
                     if (last_x == -1) {
                         last_x = x;
                     }
                 } else {
-                    if (last_x != -1) {
-                        int h = find_and_clear_dirty_height(vs, y, last_x, x,
-                                                            height);
-
-                        n += vnc_job_add_rect(job,
-                                              last_x * VNC_DIRTY_PIXELS_PER_BIT,
-                                              y,
-                                              (x - last_x) * VNC_DIRTY_PIXELS_PER_BIT,
-                                              h);
-                    }
+                    VNC_CLIENT_UPDATE_RECT();
                     last_x = -1;
                 }
             }
-            if (last_x != -1) {
-                int h = find_and_clear_dirty_height(vs, y, last_x, x, height);
-                n += vnc_job_add_rect(job, last_x * VNC_DIRTY_PIXELS_PER_BIT,
-                                      y,
-                                      (x - last_x) * VNC_DIRTY_PIXELS_PER_BIT,
-                                      h);
-            }
+            VNC_CLIENT_UPDATE_RECT();
+            y++;
         }
 
         vnc_job_push(job);
@@ -2676,8 +2695,8 @@ static int vnc_refresh_server_surface(VncDisplay *vd)
     int width = pixman_image_get_width(vd->guest.fb);
     int height = pixman_image_get_height(vd->guest.fb);
     int y;
-    uint8_t *guest_row;
-    uint8_t *server_row;
+    uint8_t *guest_row0 = NULL, *server_row0;
+    int guest_stride, server_stride;
     int cmp_bytes;
     VncState *vs;
     int has_dirty = 0;
@@ -2702,44 +2721,57 @@ static int vnc_refresh_server_surface(VncDisplay *vd)
     if (vd->guest.format != VNC_SERVER_FB_FORMAT) {
         int width = pixman_image_get_width(vd->server);
         tmpbuf = qemu_pixman_linebuf_create(VNC_SERVER_FB_FORMAT, width);
-    }
-    guest_row = (uint8_t *)pixman_image_get_data(vd->guest.fb);
-    server_row = (uint8_t *)pixman_image_get_data(vd->server);
-    for (y = 0; y < height; y++) {
-        if (!bitmap_empty(vd->guest.dirty[y], VNC_DIRTY_BITS)) {
-            int x;
-            uint8_t *guest_ptr;
-            uint8_t *server_ptr;
+    } else {
+        guest_row0 = (uint8_t *)pixman_image_get_data(vd->guest.fb);
+    }
+    server_row0 = (uint8_t *)pixman_image_get_data(vd->server);
+    guest_stride = pixman_image_get_stride(vd->guest.fb);
+    server_stride = pixman_image_get_stride(vd->server);
+
+    y = 0;
+    for (;;) {
+        int x;
+        uint8_t *guest_ptr, *server_ptr;
+        unsigned long offset = find_next_bit((unsigned long *) &vd->guest.dirty,
+                                             height * VNC_DIRTY_BITS_PER_LINE(&vd->guest),
+                                             y * VNC_DIRTY_BITS_PER_LINE(&vd->guest));
+        if (offset == height * VNC_DIRTY_BITS_PER_LINE(&vd->guest)) {
+            /* no more dirty bits */
+            break;
+        }
+        y = offset / VNC_DIRTY_BITS_PER_LINE(&vd->guest);
 
-            if (vd->guest.format != VNC_SERVER_FB_FORMAT) {
-                qemu_pixman_linebuf_fill(tmpbuf, vd->guest.fb, width, 0, y);
-                guest_ptr = (uint8_t *)pixman_image_get_data(tmpbuf);
-            } else {
-                guest_ptr = guest_row;
-            }
-            server_ptr = server_row;
+        server_ptr = server_row0 + y * server_stride;
 
-            for (x = 0; x + VNC_DIRTY_PIXELS_PER_BIT - 1 < width;
-                 x += VNC_DIRTY_PIXELS_PER_BIT, guest_ptr += cmp_bytes,
-                 server_ptr += cmp_bytes) {
-                if (!test_and_clear_bit((x / VNC_DIRTY_PIXELS_PER_BIT),
-                    vd->guest.dirty[y])) {
-                    continue;
-                }
-                if (memcmp(server_ptr, guest_ptr, cmp_bytes) == 0) {
-                    continue;
-                }
-                memcpy(server_ptr, guest_ptr, cmp_bytes);
-                if (!vd->non_adaptive)
-                    vnc_rect_updated(vd, x, y, &tv);
-                QTAILQ_FOREACH(vs, &vd->clients, next) {
-                    set_bit((x / VNC_DIRTY_PIXELS_PER_BIT), vs->dirty[y]);
-                }
-                has_dirty++;
+        if (vd->guest.format != VNC_SERVER_FB_FORMAT) {
+            qemu_pixman_linebuf_fill(tmpbuf, vd->guest.fb, width, 0, y);
+            guest_ptr = (uint8_t *)pixman_image_get_data(tmpbuf);
+        } else {
+            guest_ptr = guest_row0 + y * guest_stride;
+        }
+
+        for (x = offset % VNC_DIRTY_BITS_PER_LINE(&vd->guest);
+             x + VNC_DIRTY_PIXELS_PER_BIT - 1 < width;
+             x += VNC_DIRTY_PIXELS_PER_BIT, guest_ptr += cmp_bytes,
+             server_ptr += cmp_bytes) {
+            if (!test_and_clear_bit((x / VNC_DIRTY_PIXELS_PER_BIT),
+                vd->guest.dirty[y])) {
+                continue;
+            }
+            if (memcmp(server_ptr, guest_ptr, cmp_bytes) == 0) {
+                continue;
+            }
+            memcpy(server_ptr, guest_ptr, cmp_bytes);
+            if (!vd->non_adaptive) {
+                vnc_rect_updated(vd, x, y, &tv);
             }
+            QTAILQ_FOREACH(vs, &vd->clients, next) {
+                set_bit((x / VNC_DIRTY_PIXELS_PER_BIT), vs->dirty[y]);
+            }
+            has_dirty++;
         }
-        guest_row  += pixman_image_get_stride(vd->guest.fb);
-        server_row += pixman_image_get_stride(vd->server);
+
+        y++;
     }
     qemu_pixman_image_unref(tmpbuf);
     return has_dirty;
diff --git a/ui/vnc.h b/ui/vnc.h
index 4a8f33c..82c8ea8 100644
--- a/ui/vnc.h
+++ b/ui/vnc.h
@@ -88,6 +88,9 @@ typedef void VncSendHextileTile(VncState *vs,
 /* VNC_DIRTY_BITS is the number of bits in the dirty bitmap. */
 #define VNC_DIRTY_BITS (VNC_MAX_WIDTH / VNC_DIRTY_PIXELS_PER_BIT)
 
+/* VNC_DIRTY_BITS_PER_LINE might be greater than VNC_DIRTY_BITS due to alignment */
+#define VNC_DIRTY_BITS_PER_LINE(x) (sizeof((x)->dirty) / VNC_MAX_HEIGHT * BITS_PER_BYTE)
+
 #define VNC_STAT_RECT  64
 #define VNC_STAT_COLS (VNC_MAX_WIDTH / VNC_STAT_RECT)
 #define VNC_STAT_ROWS (VNC_MAX_HEIGHT / VNC_STAT_RECT)
