* [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module
@ 2010-11-11 16:56 Corentin Chary
2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 01/15] vnc: don't set the quality if lossy encoding are disabled Corentin Chary
` (15 more replies)
0 siblings, 16 replies; 21+ messages in thread
From: Corentin Chary @ 2010-11-11 16:56 UTC (permalink / raw)
To: Qemu-development List
Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara
Hi,
I rebased the series against current master, it contains:
- Adaptive Tight Encoding: send lossy or lossless updates depending on the
update frequency of the screen region. If a lossy update is forced, then
it will be refreshed with a lossless update as soon as the update frequency
goes back to 0.
- ZRLE/ZYWRLE Encodings: ZYWRLE use less bandwidth than tight, but the result
is also probably more lossy. I wanted to make ZRLE/ZYWRLE adaptive, but this
is not possible because most of the vnc clients can't switch between ZRLE and
ZYWRLE. But a possible solution is to use another encoding for lossless updates,
like zlib or tight.
- Bitmap module: create bitmap.h and bitops.h, and remove duplicate code
from vnc.c
It was my last series from GSoC 2010 context, if necessary I can send different
series for adaptive vnc, zrle and bitmap stuff.
Thanks,
Corentin Chary (15):
vnc: don't set the quality if lossy encoding are disabled
vnc: add a way to get the update frequency for a given region
vnc: refresh lossy rect after a given timeout
vnc: tight: use the update frequency to choose between lossy and
lossless
vnc: palette: use a pool to reduce memory allocations
vnc: palette: add palette_init calls
vnc: palette: and fill and color calls.
vnc: Add ZRLE and ZYWRLE encodings.
vnc: fix uint8_t comparisons with negative values
vnc: fix lossy rect refreshing
bitmap: add a generic bitmap and bitops library
vnc: use the new generic bitmap functions
vnc: don't try to send bigger updates that client height
vnc: tight: tweak adaptive tight settings
vnc: add a non-adaptive option
Makefile.objs | 2 +
bitmap.c | 255 ++++++++++++++++
bitmap.h | 222 ++++++++++++++
bitops.c | 142 +++++++++
bitops.h | 272 ++++++++++++++++++
osdep.h | 4 +
qemu-options.hx | 9 +
ui/vnc-enc-tight.c | 75 ++++-
ui/vnc-enc-zrle-template.c | 275 ++++++++++++++++++
ui/vnc-enc-zrle.c | 390 +++++++++++++++++++++++++
ui/vnc-enc-zrle.h | 40 +++
ui/vnc-enc-zywrle-template.c | 170 +++++++++++
ui/vnc-enc-zywrle.h | 652 ++++++++++++++++++++++++++++++++++++++++++
ui/vnc-jobs-async.c | 4 +
ui/vnc-palette.c | 59 +++--
ui/vnc-palette.h | 7 +-
ui/vnc.c | 283 ++++++++++++++-----
ui/vnc.h | 57 ++++-
18 files changed, 2810 insertions(+), 108 deletions(-)
create mode 100644 bitmap.c
create mode 100644 bitmap.h
create mode 100644 bitops.c
create mode 100644 bitops.h
create mode 100644 ui/vnc-enc-zrle-template.c
create mode 100644 ui/vnc-enc-zrle.c
create mode 100644 ui/vnc-enc-zrle.h
create mode 100644 ui/vnc-enc-zywrle-template.c
create mode 100644 ui/vnc-enc-zywrle.h
--
1.7.3.2
^ permalink raw reply [flat|nested] 21+ messages in thread* [Qemu-devel] [PATCH v2 01/15] vnc: don't set the quality if lossy encoding are disabled 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary @ 2010-11-11 16:56 ` Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 02/15] vnc: add a way to get the update frequency for a given region Corentin Chary ` (14 subsequent siblings) 15 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:56 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara This should not change the current behavior, but if any new encoding try to use the tight quality, it will always be set to -1 when lossy encodings are disabled. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- ui/vnc.c | 4 +++- 1 files changed, 3 insertions(+), 1 deletions(-) diff --git a/ui/vnc.c b/ui/vnc.c index 864342e..7391311 100644 --- a/ui/vnc.c +++ b/ui/vnc.c @@ -1780,7 +1780,9 @@ static void set_encodings(VncState *vs, int32_t *encodings, size_t n_encodings) vs->tight.compression = (enc & 0x0F); break; case VNC_ENCODING_QUALITYLEVEL0 ... VNC_ENCODING_QUALITYLEVEL0 + 9: - vs->tight.quality = (enc & 0x0F); + if (vs->vd->lossy) { + vs->tight.quality = (enc & 0x0F); + } break; default: VNC_DEBUG("Unknown encoding: %d (0x%.8x): %d\n", i, enc, enc); -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 02/15] vnc: add a way to get the update frequency for a given region 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 01/15] vnc: don't set the quality if lossy encoding are disabled Corentin Chary @ 2010-11-11 16:56 ` Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 03/15] vnc: refresh lossy rect after a given timeout Corentin Chary ` (13 subsequent siblings) 15 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:56 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara This patch compute the update frequency (in Hz) for each 64x64 rects. Any adaptive encoding can get this value using vnc_update_freq(), and switch to a lossy encoding if the value is too high. The frequency is pre-calculated every 500ms, based on the last 10 updates per 64x64 rect. If a 64x64 rect was not updated in the last 2 second, then the frequency became 0, and all the stored timestamp are reseted. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- ui/vnc.c | 101 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ui/vnc.h | 19 +++++++++++ 2 files changed, 120 insertions(+), 0 deletions(-) diff --git a/ui/vnc.c b/ui/vnc.c index 7391311..b6e18b3 100644 --- a/ui/vnc.c +++ b/ui/vnc.c @@ -35,6 +35,8 @@ #define VNC_REFRESH_INTERVAL_BASE 30 #define VNC_REFRESH_INTERVAL_INC 50 #define VNC_REFRESH_INTERVAL_MAX 2000 +static const struct timeval VNC_REFRESH_STATS = { 0, 500000 }; +static const struct timeval VNC_REFRESH_LOSSY = { 2, 0 }; #include "vnc_keysym.h" #include "d3des.h" @@ -2257,6 +2259,99 @@ static int protocol_version(VncState *vs, uint8_t *version, size_t len) return 0; } +static VncRectStat *vnc_stat_rect(VncDisplay *vd, int x, int y) +{ + struct VncSurface *vs = &vd->guest; + + return &vs->stats[y / VNC_STAT_RECT][x / VNC_STAT_RECT]; +} + +static void vnc_update_stats(VncDisplay *vd, struct timeval * tv) +{ + int x, y; + struct timeval res; + + for (y = 0; y < vd->guest.ds->height; y += VNC_STAT_RECT) { + for (x = 0; x < vd->guest.ds->width; x += VNC_STAT_RECT) { + VncRectStat *rect = vnc_stat_rect(vd, x, y); + + rect->updated = false; + } + } + + timersub(tv, &VNC_REFRESH_STATS, &res); + + if (timercmp(&vd->guest.last_freq_check, &res, >)) { + return ; + } + vd->guest.last_freq_check = *tv; + + for (y = 0; y < vd->guest.ds->height; y += VNC_STAT_RECT) { + for (x = 0; x < vd->guest.ds->width; x += VNC_STAT_RECT) { + VncRectStat *rect= vnc_stat_rect(vd, x, y); + int count = ARRAY_SIZE(rect->times); + struct timeval min, max; + + if (!timerisset(&rect->times[count - 1])) { + continue ; + } + + max = rect->times[(rect->idx + count - 1) % count]; + timersub(tv, &max, &res); + + if (timercmp(&res, &VNC_REFRESH_LOSSY, >)) { + rect->freq = 0; + memset(rect->times, 0, sizeof (rect->times)); + continue ; + } + + min = rect->times[rect->idx]; + max = rect->times[(rect->idx + count - 1) % count]; + timersub(&max, &min, &res); + + rect->freq = res.tv_sec + res.tv_usec / 1000000.; + rect->freq /= count; + rect->freq = 1. / rect->freq; + } + } +} + +double vnc_update_freq(VncState *vs, int x, int y, int w, int h) +{ + int i, j; + double total = 0; + int num = 0; + + x = (x / VNC_STAT_RECT) * VNC_STAT_RECT; + y = (y / VNC_STAT_RECT) * VNC_STAT_RECT; + + for (j = y; j <= y + h; j += VNC_STAT_RECT) { + for (i = x; i <= x + w; i += VNC_STAT_RECT) { + total += vnc_stat_rect(vs->vd, i, j)->freq; + num++; + } + } + + if (num) { + return total / num; + } else { + return 0; + } +} + +static void vnc_rect_updated(VncDisplay *vd, int x, int y, struct timeval * tv) +{ + VncRectStat *rect; + + rect = vnc_stat_rect(vd, x, y); + if (rect->updated) { + return ; + } + rect->times[rect->idx] = *tv; + rect->idx = (rect->idx + 1) % ARRAY_SIZE(rect->times); + rect->updated = true; +} + static int vnc_refresh_server_surface(VncDisplay *vd) { int y; @@ -2267,6 +2362,11 @@ static int vnc_refresh_server_surface(VncDisplay *vd) VncState *vs; int has_dirty = 0; + struct timeval tv; + + gettimeofday(&tv, NULL); + vnc_update_stats(vd, &tv); + /* * Walk through the guest dirty map. * Check and copy modified bits from guest to server surface. @@ -2293,6 +2393,7 @@ static int vnc_refresh_server_surface(VncDisplay *vd) if (memcmp(server_ptr, guest_ptr, cmp_bytes) == 0) continue; memcpy(server_ptr, guest_ptr, cmp_bytes); + vnc_rect_updated(vd, x, y, &tv); QTAILQ_FOREACH(vs, &vd->clients, next) { vnc_set_bit(vs->dirty[y], (x / 16)); } diff --git a/ui/vnc.h b/ui/vnc.h index 9619b24..f10fa3c 100644 --- a/ui/vnc.h +++ b/ui/vnc.h @@ -80,6 +80,10 @@ typedef void VncSendHextileTile(VncState *vs, #define VNC_MAX_HEIGHT 2048 #define VNC_DIRTY_WORDS (VNC_MAX_WIDTH / (16 * 32)) +#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) + #define VNC_AUTH_CHALLENGE_SIZE 16 typedef struct VncDisplay VncDisplay; @@ -92,9 +96,23 @@ typedef struct VncDisplay VncDisplay; #include "vnc-auth-sasl.h" #endif +struct VncRectStat +{ + /* time of last 10 updates, to find update frequency */ + struct timeval times[10]; + int idx; + + double freq; /* Update frequency (in Hz) */ + bool updated; /* Already updated during this refresh */ +}; + +typedef struct VncRectStat VncRectStat; + struct VncSurface { + struct timeval last_freq_check; uint32_t dirty[VNC_MAX_HEIGHT][VNC_DIRTY_WORDS]; + VncRectStat stats[VNC_STAT_ROWS][VNC_STAT_COLS]; DisplaySurface *ds; }; @@ -478,6 +496,7 @@ void vnc_framebuffer_update(VncState *vs, int x, int y, int w, int h, int32_t encoding); void vnc_convert_pixel(VncState *vs, uint8_t *buf, uint32_t v); +double vnc_update_freq(VncState *vs, int x, int y, int w, int h); /* Encodings */ int vnc_send_framebuffer_update(VncState *vs, int x, int y, int w, int h); -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 03/15] vnc: refresh lossy rect after a given timeout 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 01/15] vnc: don't set the quality if lossy encoding are disabled Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 02/15] vnc: add a way to get the update frequency for a given region Corentin Chary @ 2010-11-11 16:56 ` Corentin Chary 2010-11-11 18:44 ` Blue Swirl 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 04/15] vnc: tight: use the update frequency to choose between lossy and lossless Corentin Chary ` (12 subsequent siblings) 15 siblings, 1 reply; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:56 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara If an adaptive encoding has choosen to send a lossy update based on the result of vnc_update_freq(), then it should advertise it with vnc_sent_lossy_rect(). This will allow to automatically refresh this rect once it's static again. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- ui/vnc-jobs-async.c | 2 + ui/vnc.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++--- ui/vnc.h | 3 ++ 3 files changed, 68 insertions(+), 4 deletions(-) diff --git a/ui/vnc-jobs-async.c b/ui/vnc-jobs-async.c index 6e9cf08..31f8436 100644 --- a/ui/vnc-jobs-async.c +++ b/ui/vnc-jobs-async.c @@ -166,6 +166,7 @@ static void vnc_async_encoding_start(VncState *orig, VncState *local) local->features = orig->features; local->ds = orig->ds; local->vd = orig->vd; + local->lossy_rect = orig->lossy_rect; local->write_pixels = orig->write_pixels; local->clientds = orig->clientds; local->tight = orig->tight; @@ -182,6 +183,7 @@ static void vnc_async_encoding_end(VncState *orig, VncState *local) orig->tight = local->tight; orig->zlib = local->zlib; orig->hextile = local->hextile; + orig->lossy_rect = local->lossy_rect; } static int vnc_worker_thread_loop(VncJobQueue *queue) diff --git a/ui/vnc.c b/ui/vnc.c index b6e18b3..e1643d1 100644 --- a/ui/vnc.c +++ b/ui/vnc.c @@ -1014,6 +1014,8 @@ static void vnc_disconnect_start(VncState *vs) static void vnc_disconnect_finish(VncState *vs) { + int i; + vnc_jobs_join(vs); /* Wait encoding jobs */ vnc_lock_output(vs); @@ -1050,7 +1052,11 @@ static void vnc_disconnect_finish(VncState *vs) #ifdef CONFIG_VNC_THREAD qemu_mutex_destroy(&vs->output_mutex); #endif - qemu_free(vs); + for (i = 0; i < VNC_STAT_ROWS; ++i) { + qemu_free(vs->lossy_rect[i]); + } + qemu_free(vs->lossy_rect); + qemu_free(vs); } int vnc_client_io_error(VncState *vs, int ret, int last_errno) @@ -2266,10 +2272,55 @@ static VncRectStat *vnc_stat_rect(VncDisplay *vd, int x, int y) return &vs->stats[y / VNC_STAT_RECT][x / VNC_STAT_RECT]; } -static void vnc_update_stats(VncDisplay *vd, struct timeval * tv) +void vnc_sent_lossy_rect(VncState *vs, int x, int y, int w, int h) +{ + int i, j; + + w = (x + w) / VNC_STAT_RECT; + h = (y + h) / VNC_STAT_RECT; + x /= VNC_STAT_RECT; + y /= VNC_STAT_RECT; + + for (j = y; j <= y + h; j++) { + for (i = x; i <= x + w; i++) { + vs->lossy_rect[j][i] = 1; + } + } +} + +static int vnc_refresh_lossy_rect(VncDisplay *vd, int x, int y) +{ + VncState *vs; + int sty = y / VNC_STAT_RECT; + int stx = x / VNC_STAT_RECT; + int has_dirty = 0; + + y = y / VNC_STAT_RECT * VNC_STAT_RECT; + x = x / VNC_STAT_RECT * VNC_STAT_RECT; + + QTAILQ_FOREACH(vs, &vd->clients, next) { + int j ; + + /* kernel send buffers are full -> refresh later */ + if (vs->output.offset) + continue ; + + if (!vs->lossy_rect[sty][stx]) + continue ; + vs->lossy_rect[sty][stx] = 0; + for (j = 0; j < VNC_STAT_RECT; ++j) { + vnc_set_bits(vs->dirty[y + j], x / 16, VNC_STAT_RECT / 16); + } + has_dirty++; + } + return has_dirty; +} + +static int vnc_update_stats(VncDisplay *vd, struct timeval * tv) { int x, y; struct timeval res; + int has_dirty = 0; for (y = 0; y < vd->guest.ds->height; y += VNC_STAT_RECT) { for (x = 0; x < vd->guest.ds->width; x += VNC_STAT_RECT) { @@ -2282,7 +2333,7 @@ static void vnc_update_stats(VncDisplay *vd, struct timeval * tv) timersub(tv, &VNC_REFRESH_STATS, &res); if (timercmp(&vd->guest.last_freq_check, &res, >)) { - return ; + return has_dirty; } vd->guest.last_freq_check = *tv; @@ -2301,6 +2352,7 @@ static void vnc_update_stats(VncDisplay *vd, struct timeval * tv) if (timercmp(&res, &VNC_REFRESH_LOSSY, >)) { rect->freq = 0; + has_dirty += vnc_refresh_lossy_rect(vd, x, y); memset(rect->times, 0, sizeof (rect->times)); continue ; } @@ -2314,6 +2366,7 @@ static void vnc_update_stats(VncDisplay *vd, struct timeval * tv) rect->freq = 1. / rect->freq; } } + return has_dirty; } double vnc_update_freq(VncState *vs, int x, int y, int w, int h) @@ -2365,7 +2418,7 @@ static int vnc_refresh_server_surface(VncDisplay *vd) struct timeval tv; gettimeofday(&tv, NULL); - vnc_update_stats(vd, &tv); + has_dirty = vnc_update_stats(vd, &tv); /* * Walk through the guest dirty map. @@ -2467,7 +2520,13 @@ static void vnc_remove_timer(VncDisplay *vd) static void vnc_connect(VncDisplay *vd, int csock) { VncState *vs = qemu_mallocz(sizeof(VncState)); + int i; + vs->csock = csock; + vs->lossy_rect = qemu_mallocz(VNC_STAT_ROWS * sizeof (*vs->lossy_rect)); + for (i = 0; i < VNC_STAT_ROWS; ++i) { + vs->lossy_rect[i] = qemu_mallocz(VNC_STAT_COLS * sizeof (uint8_t)); + } VNC_DEBUG("New client on socket %d\n", csock); dcl->idle = 0; diff --git a/ui/vnc.h b/ui/vnc.h index f10fa3c..00bd21c 100644 --- a/ui/vnc.h +++ b/ui/vnc.h @@ -216,6 +216,8 @@ struct VncState DisplayState *ds; uint32_t dirty[VNC_MAX_HEIGHT][VNC_DIRTY_WORDS]; + uint8_t **lossy_rect; /* Not an Array to avoid costly memcpy in + * vnc-jobs-async.c */ VncDisplay *vd; int need_update; @@ -497,6 +499,7 @@ void vnc_framebuffer_update(VncState *vs, int x, int y, int w, int h, void vnc_convert_pixel(VncState *vs, uint8_t *buf, uint32_t v); double vnc_update_freq(VncState *vs, int x, int y, int w, int h); +void vnc_sent_lossy_rect(VncState *vs, int x, int y, int w, int h); /* Encodings */ int vnc_send_framebuffer_update(VncState *vs, int x, int y, int w, int h); -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* Re: [Qemu-devel] [PATCH v2 03/15] vnc: refresh lossy rect after a given timeout 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 03/15] vnc: refresh lossy rect after a given timeout Corentin Chary @ 2010-11-11 18:44 ` Blue Swirl 0 siblings, 0 replies; 21+ messages in thread From: Blue Swirl @ 2010-11-11 18:44 UTC (permalink / raw) To: Corentin Chary Cc: Anthony Liguori, Andre Przywara, Qemu-development List, Alexander Graf On Thu, Nov 11, 2010 at 4:56 PM, Corentin Chary <corentincj@iksaif.net> wrote: > If an adaptive encoding has choosen to send a lossy update > based on the result of vnc_update_freq(), then it should advertise > it with vnc_sent_lossy_rect(). This will allow to automatically refresh > this rect once it's static again. > > Signed-off-by: Corentin Chary <corentincj@iksaif.net> > --- > ui/vnc-jobs-async.c | 2 + > ui/vnc.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++--- > ui/vnc.h | 3 ++ > 3 files changed, 68 insertions(+), 4 deletions(-) > > diff --git a/ui/vnc-jobs-async.c b/ui/vnc-jobs-async.c > index 6e9cf08..31f8436 100644 > --- a/ui/vnc-jobs-async.c > +++ b/ui/vnc-jobs-async.c > @@ -166,6 +166,7 @@ static void vnc_async_encoding_start(VncState *orig, VncState *local) > local->features = orig->features; > local->ds = orig->ds; > local->vd = orig->vd; > + local->lossy_rect = orig->lossy_rect; > local->write_pixels = orig->write_pixels; > local->clientds = orig->clientds; > local->tight = orig->tight; > @@ -182,6 +183,7 @@ static void vnc_async_encoding_end(VncState *orig, VncState *local) > orig->tight = local->tight; > orig->zlib = local->zlib; > orig->hextile = local->hextile; > + orig->lossy_rect = local->lossy_rect; > } > > static int vnc_worker_thread_loop(VncJobQueue *queue) > diff --git a/ui/vnc.c b/ui/vnc.c > index b6e18b3..e1643d1 100644 > --- a/ui/vnc.c > +++ b/ui/vnc.c > @@ -1014,6 +1014,8 @@ static void vnc_disconnect_start(VncState *vs) > > static void vnc_disconnect_finish(VncState *vs) > { > + int i; > + > vnc_jobs_join(vs); /* Wait encoding jobs */ > > vnc_lock_output(vs); > @@ -1050,7 +1052,11 @@ static void vnc_disconnect_finish(VncState *vs) > #ifdef CONFIG_VNC_THREAD > qemu_mutex_destroy(&vs->output_mutex); > #endif > - qemu_free(vs); > + for (i = 0; i < VNC_STAT_ROWS; ++i) { > + qemu_free(vs->lossy_rect[i]); > + } > + qemu_free(vs->lossy_rect); > + qemu_free(vs); Odd spacing. > } > > int vnc_client_io_error(VncState *vs, int ret, int last_errno) > @@ -2266,10 +2272,55 @@ static VncRectStat *vnc_stat_rect(VncDisplay *vd, int x, int y) > return &vs->stats[y / VNC_STAT_RECT][x / VNC_STAT_RECT]; > } > > -static void vnc_update_stats(VncDisplay *vd, struct timeval * tv) > +void vnc_sent_lossy_rect(VncState *vs, int x, int y, int w, int h) > +{ > + int i, j; > + > + w = (x + w) / VNC_STAT_RECT; > + h = (y + h) / VNC_STAT_RECT; > + x /= VNC_STAT_RECT; > + y /= VNC_STAT_RECT; > + > + for (j = y; j <= y + h; j++) { > + for (i = x; i <= x + w; i++) { > + vs->lossy_rect[j][i] = 1; > + } > + } > +} > + > +static int vnc_refresh_lossy_rect(VncDisplay *vd, int x, int y) > +{ > + VncState *vs; > + int sty = y / VNC_STAT_RECT; > + int stx = x / VNC_STAT_RECT; > + int has_dirty = 0; > + > + y = y / VNC_STAT_RECT * VNC_STAT_RECT; > + x = x / VNC_STAT_RECT * VNC_STAT_RECT; > + > + QTAILQ_FOREACH(vs, &vd->clients, next) { > + int j ; Extra space between identifier and semicolon. > + > + /* kernel send buffers are full -> refresh later */ > + if (vs->output.offset) Missing braces. > + continue ; Extra space. > + > + if (!vs->lossy_rect[sty][stx]) > + continue ; See above. ^ permalink raw reply [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 04/15] vnc: tight: use the update frequency to choose between lossy and lossless 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (2 preceding siblings ...) 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 03/15] vnc: refresh lossy rect after a given timeout Corentin Chary @ 2010-11-11 16:56 ` Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 05/15] vnc: palette: use a pool to reduce memory allocations Corentin Chary ` (11 subsequent siblings) 15 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:56 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara Use the new update frequency infrastructure to use jpeg for regions with high update frequency. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- ui/vnc-enc-tight.c | 75 +++++++++++++++++++++++++++++++++++++++++++--------- 1 files changed, 62 insertions(+), 13 deletions(-) diff --git a/ui/vnc-enc-tight.c b/ui/vnc-enc-tight.c index af45edd..ad9a9a8 100644 --- a/ui/vnc-enc-tight.c +++ b/ui/vnc-enc-tight.c @@ -72,6 +72,26 @@ static const struct { static int tight_send_framebuffer_update(VncState *vs, int x, int y, int w, int h); +#ifdef CONFIG_VNC_JPEG +static const struct { + double jpeg_freq_min; /* Don't send JPEG if the freq is bellow */ + double jpeg_freq_threshold; /* Always send JPEG if the freq is above */ + int jpeg_idx; /* Allow indexed JPEG */ + int jpeg_full; /* Allow full color JPEG */ +} tight_jpeg_conf[] = { + { 0, 4, 1, 1 }, + { 0, 4, 1, 1 }, + { 0, 4, 1, 1 }, + { 0, 4, 1, 1 }, + { 0, 4, 0, 1 }, + { 0.1, 4, 0, 1 }, + { 0.2, 4, 0, 1 }, + { 0.3, 6, 0, 0 }, + { 0.4, 8, 0, 0 }, + { 0.5, 10, 0, 0 }, +}; +#endif + #ifdef CONFIG_VNC_PNG static const struct { int png_zlib_level, png_filters; @@ -1476,12 +1496,13 @@ static int send_sub_rect_nojpeg(VncState *vs, int x, int y, int w, int h, #ifdef CONFIG_VNC_JPEG static int send_sub_rect_jpeg(VncState *vs, int x, int y, int w, int h, int bg, int fg, int colors, - VncPalette *palette) + VncPalette *palette, bool force) { int ret; if (colors == 0) { - if (tight_detect_smooth_image(vs, w, h)) { + if (force || (tight_jpeg_conf[vs->tight.quality].jpeg_full && + tight_detect_smooth_image(vs, w, h))) { int quality = tight_conf[vs->tight.quality].jpeg_quality; ret = send_jpeg_rect(vs, x, y, w, h, quality); @@ -1493,8 +1514,9 @@ static int send_sub_rect_jpeg(VncState *vs, int x, int y, int w, int h, } else if (colors == 2) { ret = send_mono_rect(vs, x, y, w, h, bg, fg); } else if (colors <= 256) { - if (colors > 96 && - tight_detect_smooth_image(vs, w, h)) { + if (force || (colors > 96 && + tight_jpeg_conf[vs->tight.quality].jpeg_idx && + tight_detect_smooth_image(vs, w, h))) { int quality = tight_conf[vs->tight.quality].jpeg_quality; ret = send_jpeg_rect(vs, x, y, w, h, quality); @@ -1514,6 +1536,8 @@ static int send_sub_rect(VncState *vs, int x, int y, int w, int h) uint32_t bg = 0, fg = 0; int colors; int ret = 0; + bool force_jpeg = false; + bool allow_jpeg = true; vnc_framebuffer_update(vs, x, y, w, h, vs->tight.type); @@ -1521,11 +1545,26 @@ static int send_sub_rect(VncState *vs, int x, int y, int w, int h) vnc_raw_send_framebuffer_update(vs, x, y, w, h); vnc_tight_stop(vs); +#ifdef CONFIG_VNC_JPEG + if (vs->tight.quality != -1) { + double freq = vnc_update_freq(vs, x, y, w, h); + + if (freq < tight_jpeg_conf[vs->tight.quality].jpeg_freq_min) { + allow_jpeg = false; + } + if (freq >= tight_jpeg_conf[vs->tight.quality].jpeg_freq_threshold) { + force_jpeg = true; + vnc_sent_lossy_rect(vs, x, y, w, h); + } + } +#endif + colors = tight_fill_palette(vs, x, y, w * h, &fg, &bg, &palette); #ifdef CONFIG_VNC_JPEG - if (vs->tight.quality != (uint8_t)-1) { - ret = send_sub_rect_jpeg(vs, x, y, w, h, bg, fg, colors, palette); + if (allow_jpeg && vs->tight.quality != (uint8_t)-1) { + ret = send_sub_rect_jpeg(vs, x, y, w, h, bg, fg, colors, palette, + force_jpeg); } else { ret = send_sub_rect_nojpeg(vs, x, y, w, h, bg, fg, colors, palette); } @@ -1548,7 +1587,8 @@ static int send_sub_rect_solid(VncState *vs, int x, int y, int w, int h) return send_solid_rect(vs); } -static int send_rect_simple(VncState *vs, int x, int y, int w, int h) +static int send_rect_simple(VncState *vs, int x, int y, int w, int h, + bool split) { int max_size, max_width; int max_sub_width, max_sub_height; @@ -1559,7 +1599,7 @@ static int send_rect_simple(VncState *vs, int x, int y, int w, int h) max_size = tight_conf[vs->tight.compression].max_rect_size; max_width = tight_conf[vs->tight.compression].max_rect_width; - if (w > max_width || w * h > max_size) { + if (split && (w > max_width || w * h > max_size)) { max_sub_width = (w > max_width) ? max_width : w; max_sub_height = max_size / max_sub_width; @@ -1590,7 +1630,7 @@ static int find_large_solid_color_rect(VncState *vs, int x, int y, /* If a rectangle becomes too large, send its upper part now. */ if (dy - y >= max_rows) { - n += send_rect_simple(vs, x, y, w, max_rows); + n += send_rect_simple(vs, x, y, w, max_rows, true); y += max_rows; h -= max_rows; } @@ -1629,7 +1669,7 @@ static int find_large_solid_color_rect(VncState *vs, int x, int y, /* Send rectangles at top and left to solid-color area. */ if (y_best != y) { - n += send_rect_simple(vs, x, y, w, y_best-y); + n += send_rect_simple(vs, x, y, w, y_best-y, true); } if (x_best != x) { n += tight_send_framebuffer_update(vs, x, y_best, @@ -1656,7 +1696,7 @@ static int find_large_solid_color_rect(VncState *vs, int x, int y, return n; } } - return n + send_rect_simple(vs, x, y, w, h); + return n + send_rect_simple(vs, x, y, w, h, true); } static int tight_send_framebuffer_update(VncState *vs, int x, int y, @@ -1671,8 +1711,17 @@ static int tight_send_framebuffer_update(VncState *vs, int x, int y, vs->tight.pixel24 = false; } - if (w * h < VNC_TIGHT_MIN_SPLIT_RECT_SIZE) - return send_rect_simple(vs, x, y, w, h); + if (vs->tight.quality != -1) { + double freq = vnc_update_freq(vs, x, y, w, h); + + if (freq > tight_jpeg_conf[vs->tight.quality].jpeg_freq_threshold) { + return send_rect_simple(vs, x, y, w, h, false); + } + } + + if (w * h < VNC_TIGHT_MIN_SPLIT_RECT_SIZE) { + return send_rect_simple(vs, x, y, w, h, true); + } /* Calculate maximum number of rows in one non-solid rectangle. */ -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 05/15] vnc: palette: use a pool to reduce memory allocations 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (3 preceding siblings ...) 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 04/15] vnc: tight: use the update frequency to choose between lossy and lossless Corentin Chary @ 2010-11-11 16:56 ` Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 06/15] vnc: palette: add palette_init calls Corentin Chary ` (10 subsequent siblings) 15 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:56 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara We now that the palette will never have more than 256 elements. Let's use a pool to reduce malloc calls. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- ui/vnc-palette.c | 18 ++---------------- ui/vnc-palette.h | 3 ++- 2 files changed, 4 insertions(+), 17 deletions(-) diff --git a/ui/vnc-palette.c b/ui/vnc-palette.c index bff6445..c47420b 100644 --- a/ui/vnc-palette.c +++ b/ui/vnc-palette.c @@ -63,23 +63,9 @@ VncPalette *palette_new(size_t max, int bpp) void palette_destroy(VncPalette *palette) { - int i; - if (palette == NULL) { - return ; + qemu_free(palette); } - - for (i = 0; i < VNC_PALETTE_HASH_SIZE; i++) { - VncPaletteEntry *entry = QLIST_FIRST(&palette->table[i]); - while (entry) { - VncPaletteEntry *tmp = QLIST_NEXT(entry, next); - QLIST_REMOVE(entry, next); - qemu_free(entry); - entry = tmp; - } - } - - qemu_free(palette); } int palette_put(VncPalette *palette, uint32_t color) @@ -97,7 +83,7 @@ int palette_put(VncPalette *palette, uint32_t color) if (!entry) { VncPaletteEntry *entry; - entry = qemu_mallocz(sizeof(*entry)); + entry = &palette->pool[palette->size]; entry->color = color; entry->idx = idx; QLIST_INSERT_HEAD(&palette->table[hash], entry, next); diff --git a/ui/vnc-palette.h b/ui/vnc-palette.h index d0645eb..f57d0e7 100644 --- a/ui/vnc-palette.h +++ b/ui/vnc-palette.h @@ -34,6 +34,7 @@ #include <stdint.h> #define VNC_PALETTE_HASH_SIZE 256 +#define VNC_PALETTE_MAX_SIZE 256 typedef struct VncPaletteEntry { int idx; @@ -42,7 +43,7 @@ typedef struct VncPaletteEntry { } VncPaletteEntry; typedef struct VncPalette { - QObject_HEAD; + VncPaletteEntry pool[VNC_PALETTE_MAX_SIZE]; size_t size; size_t max; int bpp; -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 06/15] vnc: palette: add palette_init calls 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (4 preceding siblings ...) 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 05/15] vnc: palette: use a pool to reduce memory allocations Corentin Chary @ 2010-11-11 16:56 ` Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 07/15] vnc: palette: and fill and color calls Corentin Chary ` (9 subsequent siblings) 15 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:56 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara This allow to use palette on the stack instead of always allocating them. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- ui/vnc-palette.c | 8 +++++++- ui/vnc-palette.h | 1 + 2 files changed, 8 insertions(+), 1 deletions(-) diff --git a/ui/vnc-palette.c b/ui/vnc-palette.c index c47420b..f93250b 100644 --- a/ui/vnc-palette.c +++ b/ui/vnc-palette.c @@ -56,9 +56,15 @@ VncPalette *palette_new(size_t max, int bpp) VncPalette *palette; palette = qemu_mallocz(sizeof(*palette)); + palette_init(palette, max, bpp); + return palette; +} + +void palette_init(VncPalette *palette, size_t max, int bpp) +{ + memset(palette, 0, sizeof (*palette)); palette->max = max; palette->bpp = bpp; - return palette; } void palette_destroy(VncPalette *palette) diff --git a/ui/vnc-palette.h b/ui/vnc-palette.h index f57d0e7..c646e4d 100644 --- a/ui/vnc-palette.h +++ b/ui/vnc-palette.h @@ -51,6 +51,7 @@ typedef struct VncPalette { } VncPalette; VncPalette *palette_new(size_t max, int bpp); +void palette_init(VncPalette *palette, size_t max, int bpp); void palette_destroy(VncPalette *palette); int palette_put(VncPalette *palette, uint32_t color); -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 07/15] vnc: palette: and fill and color calls. 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (5 preceding siblings ...) 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 06/15] vnc: palette: add palette_init calls Corentin Chary @ 2010-11-11 16:56 ` Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 08/15] vnc: Add ZRLE and ZYWRLE encodings Corentin Chary ` (8 subsequent siblings) 15 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:56 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara These two helpers are needed for zrle and zywrle. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- ui/vnc-palette.c | 33 +++++++++++++++++++++++++++++++++ ui/vnc-palette.h | 3 +++ 2 files changed, 36 insertions(+), 0 deletions(-) diff --git a/ui/vnc-palette.c b/ui/vnc-palette.c index f93250b..d691a0c 100644 --- a/ui/vnc-palette.c +++ b/ui/vnc-palette.c @@ -126,3 +126,36 @@ void palette_iter(const VncPalette *palette, } } } + +uint32_t palette_color(const VncPalette *palette, int idx, bool *found) +{ + int i; + VncPaletteEntry *entry; + + for (i = 0; i < VNC_PALETTE_HASH_SIZE; i++) { + QLIST_FOREACH(entry, &palette->table[i], next) { + if (entry->idx == idx) { + *found = true; + return entry->color; + } + } + } + + *found = false; + return -1; +} + +static void palette_fill_cb(int idx, uint32_t color, void *opaque) +{ + uint32_t *colors = opaque; + + colors[idx] = color; +} + +size_t palette_fill(const VncPalette *palette, + uint32_t colors[VNC_PALETTE_MAX_SIZE]) +{ + palette_iter(palette, palette_fill_cb, colors); + return palette_size(palette); +} + diff --git a/ui/vnc-palette.h b/ui/vnc-palette.h index c646e4d..3260885 100644 --- a/ui/vnc-palette.h +++ b/ui/vnc-palette.h @@ -61,5 +61,8 @@ size_t palette_size(const VncPalette *palette); void palette_iter(const VncPalette *palette, void (*iter)(int idx, uint32_t color, void *opaque), void *opaque); +uint32_t palette_color(const VncPalette *palette, int idx, bool *found); +size_t palette_fill(const VncPalette *palette, + uint32_t colors[VNC_PALETTE_MAX_SIZE]); #endif /* VNC_PALETTE_H */ -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 08/15] vnc: Add ZRLE and ZYWRLE encodings. 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (6 preceding siblings ...) 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 07/15] vnc: palette: and fill and color calls Corentin Chary @ 2010-11-11 16:56 ` Corentin Chary 2010-11-11 18:58 ` Blue Swirl 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 09/15] vnc: fix uint8_t comparisons with negative values Corentin Chary ` (7 subsequent siblings) 15 siblings, 1 reply; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:56 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara Add ZRLE [1] and ZYWRLE [2] encodings. The code is inspire^W stolen from libvncserver (again), but have been rewriten to match QEMU coding style. [1] http://www.realvnc.com/docs/rfbproto.pdf [2] http://micro-vnc.jp/research/remote_desktop_ng/ZYWRLE/publications/ Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- Makefile.objs | 1 + ui/vnc-enc-zrle-template.c | 275 ++++++++++++++++++ ui/vnc-enc-zrle.c | 389 +++++++++++++++++++++++++ ui/vnc-enc-zrle.h | 40 +++ ui/vnc-enc-zywrle-template.c | 170 +++++++++++ ui/vnc-enc-zywrle.h | 652 ++++++++++++++++++++++++++++++++++++++++++ ui/vnc-jobs-async.c | 2 + ui/vnc.c | 15 + ui/vnc.h | 27 ++- 9 files changed, 1570 insertions(+), 1 deletions(-) create mode 100644 ui/vnc-enc-zrle-template.c create mode 100644 ui/vnc-enc-zrle.c create mode 100644 ui/vnc-enc-zrle.h create mode 100644 ui/vnc-enc-zywrle-template.c create mode 100644 ui/vnc-enc-zywrle.h diff --git a/Makefile.objs b/Makefile.objs index 15569af..3da959c 100644 --- a/Makefile.objs +++ b/Makefile.objs @@ -121,6 +121,7 @@ ui-obj-$(CONFIG_CURSES) += curses.o ui-obj-y += vnc.o d3des.o ui-obj-y += vnc-enc-zlib.o vnc-enc-hextile.o ui-obj-y += vnc-enc-tight.o vnc-palette.o +ui-obj-y += vnc-enc-zrle.o ui-obj-$(CONFIG_VNC_TLS) += vnc-tls.o vnc-auth-vencrypt.o ui-obj-$(CONFIG_VNC_SASL) += vnc-auth-sasl.o ui-obj-$(CONFIG_COCOA) += cocoa.o diff --git a/ui/vnc-enc-zrle-template.c b/ui/vnc-enc-zrle-template.c new file mode 100644 index 0000000..94e92fb --- /dev/null +++ b/ui/vnc-enc-zrle-template.c @@ -0,0 +1,275 @@ +/* + * QEMU VNC display driver: Zlib Run-length Encoding (ZRLE) + * + * From libvncserver/libvncserver/zrleencodetemplate.c + * Copyright (C) 2002 RealVNC Ltd. All Rights Reserved. + * Copyright (C) 2003 Sun Microsystems, Inc. + * + * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> + * + * This is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This software is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this software; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, + * USA. + */ + +/* + * Before including this file, you must define a number of CPP macros. + * + * ZRLE_BPP should be 8, 16 or 32 depending on the bits per pixel. + * + * Note that the buf argument to ZRLE_ENCODE needs to be at least one pixel + * bigger than the largest tile of pixel data, since the ZRLE encoding + * algorithm writes to the position one past the end of the pixel data. + */ + + +#include <assert.h> + +#undef ZRLE_ENDIAN_SUFFIX + +#if ZYWRLE_ENDIAN == ENDIAN_LITTLE +#define ZRLE_ENDIAN_SUFFIX le +#elif ZYWRLE_ENDIAN == ENDIAN_BIG +#define ZRLE_ENDIAN_SUFFIX be +#else +#define ZRLE_ENDIAN_SUFFIX ne +#endif + +#ifndef ZRLE_CONCAT +#define ZRLE_CONCAT_I(a, b) a##b +#define ZRLE_CONCAT2(a, b) ZRLE_CONCAT_I(a, b) +#define ZRLE_CONCAT3(a, b, c) ZRLE_CONCAT2(a, ZRLE_CONCAT2(b, c)) +#endif + +#ifdef ZRLE_COMPACT_PIXEL +#define ZRLE_ENCODE_SUFFIX ZRLE_CONCAT2(ZRLE_COMPACT_PIXEL,ZRLE_ENDIAN_SUFFIX) +#define ZRLE_WRITE_SUFFIX ZRLE_COMPACT_PIXEL +#define ZRLE_PIXEL ZRLE_CONCAT3(uint,ZRLE_BPP,_t) +#define ZRLE_BPP_OUT 24 +#elif ZRLE_BPP == 15 +#define ZRLE_ENCODE_SUFFIX ZRLE_CONCAT2(ZRLE_BPP,ZRLE_ENDIAN_SUFFIX) +#define ZRLE_WRITE_SUFFIX 16 +#define ZRLE_PIXEL uint16_t +#define ZRLE_BPP_OUT 16 +#else +#define ZRLE_ENCODE_SUFFIX ZRLE_CONCAT2(ZRLE_BPP,ZRLE_ENDIAN_SUFFIX) +#define ZRLE_WRITE_SUFFIX ZRLE_BPP +#define ZRLE_BPP_OUT ZRLE_BPP +#define ZRLE_PIXEL ZRLE_CONCAT3(uint,ZRLE_BPP,_t) +#endif + +#define ZRLE_WRITE_PIXEL ZRLE_CONCAT2(zrle_write_u, ZRLE_WRITE_SUFFIX) +#define ZRLE_ENCODE ZRLE_CONCAT2(zrle_encode_, ZRLE_ENCODE_SUFFIX) +#define ZRLE_ENCODE_TILE ZRLE_CONCAT2(zrle_encode_tile, ZRLE_ENCODE_SUFFIX) +#define ZRLE_WRITE_PALETTE ZRLE_CONCAT2(zrle_write_palette,ZRLE_ENCODE_SUFFIX) + +static void ZRLE_ENCODE_TILE(VncState *vs, ZRLE_PIXEL *data, int w, int h, + int zywrle_level); + +#if ZRLE_BPP != 8 +#include "vnc-enc-zywrle-template.c" +#endif + + +static void ZRLE_ENCODE(VncState *vs, int x, int y, int w, int h, + int zywrle_level) +{ + int ty; + + for (ty = y; ty < y + h; ty += VNC_ZRLE_TILE_HEIGHT) { + + int tx, th; + + th = MIN(VNC_ZRLE_TILE_HEIGHT, y + h - ty); + + for (tx = x; tx < x + w; tx += VNC_ZRLE_TILE_WIDTH) { + int tw; + ZRLE_PIXEL *buf; + + tw = MIN(VNC_ZRLE_TILE_WIDTH, x + w - tx); + + buf = zrle_convert_fb(vs, tx, ty, tw, th, ZRLE_BPP); + ZRLE_ENCODE_TILE(vs, buf, tw, th, zywrle_level); + } + } +} + +static void ZRLE_ENCODE_TILE(VncState *vs, ZRLE_PIXEL *data, int w, int h, + int zywrle_level) +{ + VncPalette *palette = &vs->zrle.palette; + + int runs = 0; + int single_pixels = 0; + + bool use_rle; + bool use_palette; + + int i; + + ZRLE_PIXEL *ptr = data; + ZRLE_PIXEL *end = ptr + h * w; + *end = ~*(end-1); /* one past the end is different so the while loop ends */ + + /* Real limit is 127 but we wan't a way to know if there is more than 127 */ + palette_init(palette, 256, ZRLE_BPP); + + while (ptr < end) { + ZRLE_PIXEL pix = *ptr; + if (*++ptr != pix) { /* FIXME */ + single_pixels++; + } else { + while (*++ptr == pix) ; + runs++; + } + palette_put(palette, pix); + } + + /* Solid tile is a special case */ + + if (palette_size(palette) == 1) { + bool found; + + vnc_write_u8(vs, 1); + ZRLE_WRITE_PIXEL(vs, palette_color(palette, 0, &found)); + return; + } + + zrle_choose_palette_rle(vs, w, h, palette, ZRLE_BPP_OUT, + runs, single_pixels, zywrle_level, + &use_rle, &use_palette); + + if (!use_palette) { + vnc_write_u8(vs, (use_rle ? 128 : 0)); + } else { + uint32_t colors[VNC_PALETTE_MAX_SIZE]; + size_t size = palette_size(palette); + + vnc_write_u8(vs, (use_rle ? 128 : 0) | size); + palette_fill(palette, colors); + + for (i = 0; i < size; i++) { + ZRLE_WRITE_PIXEL(vs, colors[i]); + } + } + + if (use_rle) { + ZRLE_PIXEL *ptr = data; + ZRLE_PIXEL *end = ptr + w * h; + ZRLE_PIXEL *run_start; + ZRLE_PIXEL pix; + + while (ptr < end) { + int len; + int index = 0; + + run_start = ptr; + pix = *ptr++; + + while (*ptr == pix && ptr < end) { + ptr++; + } + + len = ptr - run_start; + + if (use_palette) + index = palette_idx(palette, pix); + + if (len <= 2 && use_palette) { + if (len == 2) { + vnc_write_u8(vs, index); + } + vnc_write_u8(vs, index); + continue; + } + if (use_palette) { + vnc_write_u8(vs, index | 128); + } else { + ZRLE_WRITE_PIXEL(vs, pix); + } + + len -= 1; + + while (len >= 255) { + vnc_write_u8(vs, 255); + len -= 255; + } + + vnc_write_u8(vs, len); + } + } else if (use_palette) { /* no RLE */ + int bppp; + ZRLE_PIXEL *ptr = data; + + /* packed pixels */ + + assert (palette_size(palette) < 17); + + bppp = bits_per_packed_pixel[palette_size(palette)-1]; + + for (i = 0; i < h; i++) { + uint8_t nbits = 0; + uint8_t byte = 0; + + ZRLE_PIXEL *eol = ptr + w; + + while (ptr < eol) { + ZRLE_PIXEL pix = *ptr++; + uint8_t index = palette_idx(palette, pix); + + byte = (byte << bppp) | index; + nbits += bppp; + if (nbits >= 8) { + vnc_write_u8(vs, byte); + nbits = 0; + } + } + if (nbits > 0) { + byte <<= 8 - nbits; + vnc_write_u8(vs, byte); + } + } + } else { + + /* raw */ + +#if ZRLE_BPP != 8 + if (zywrle_level > 0 && !(zywrle_level & 0x80)) { + ZYWRLE_ANALYZE(data, data, w, h, w, zywrle_level, vs->zywrle.buf); + ZRLE_ENCODE_TILE(vs, data, w, h, zywrle_level | 0x80); + } + else +#endif + { +#ifdef ZRLE_COMPACT_PIXEL + ZRLE_PIXEL *ptr; + + for (ptr = data; ptr < data + w * h; ptr++) { + ZRLE_WRITE_PIXEL(vs, *ptr); + } +#else + vnc_write(vs, data, w * h * (ZRLE_BPP / 8)); +#endif + } + } +} + +#undef ZRLE_PIXEL +#undef ZRLE_WRITE_PIXEL +#undef ZRLE_ENCODE +#undef ZRLE_ENCODE_TILE +#undef ZYWRLE_ENCODE_TILE +#undef ZRLE_BPP_OUT +#undef ZRLE_WRITE_SUFFIX +#undef ZRLE_ENCODE_SUFFIX diff --git a/ui/vnc-enc-zrle.c b/ui/vnc-enc-zrle.c new file mode 100644 index 0000000..4460890 --- /dev/null +++ b/ui/vnc-enc-zrle.c @@ -0,0 +1,389 @@ +/* + * QEMU VNC display driver: Zlib Run-length Encoding (ZRLE) + * + * From libvncserver/libvncserver/zrle.c + * Copyright (C) 2002 RealVNC Ltd. All Rights Reserved. + * Copyright (C) 2003 Sun Microsystems, Inc. + * + * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#include "vnc.h" +#include "vnc-enc-zrle.h" + +static const int bits_per_packed_pixel[] = { + 0, 1, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 +}; + + +static void vnc_zrle_start(VncState *vs) +{ + buffer_reset(&vs->zrle.zrle); + + // make the output buffer be the zlib buffer, so we can compress it later + vs->zrle.tmp = vs->output; + vs->output = vs->zrle.zrle; +} + +static void vnc_zrle_stop(VncState *vs) +{ + // switch back to normal output/zlib buffers + vs->zrle.zrle = vs->output; + vs->output = vs->zrle.tmp; +} + +static void *zrle_convert_fb(VncState *vs, int x, int y, int w, int h, + int bpp) +{ + Buffer tmp; + + buffer_reset(&vs->zrle.fb); + buffer_reserve(&vs->zrle.fb, w * h * bpp + bpp); + + tmp = vs->output; + vs->output = vs->zrle.fb; + + vnc_raw_send_framebuffer_update(vs, x, y, w, h); + + vs->zrle.fb = vs->output; + vs->output = tmp; + return vs->zrle.fb.buffer; +} + +static int zrle_compress_data(VncState *vs, int level) +{ + z_streamp zstream = &vs->zrle.stream; + + buffer_reset(&vs->zrle.zlib); + + if (zstream->opaque != vs) { + int err; + + zstream->zalloc = vnc_zlib_zalloc; + zstream->zfree = vnc_zlib_zfree; + + err = deflateInit2(zstream, level, Z_DEFLATED, MAX_WBITS, + MAX_MEM_LEVEL, Z_DEFAULT_STRATEGY); + + if (err != Z_OK) { + fprintf(stderr, "VNC: error initializing zlib\n"); + return -1; + } + + zstream->opaque = vs; + } + + /* reserve memory in output buffer */ + buffer_reserve(&vs->zrle.zlib, vs->zrle.zrle.offset + 64); + + /* set pointers */ + zstream->next_in = vs->zrle.zrle.buffer; + zstream->avail_in = vs->zrle.zrle.offset; + zstream->next_out = vs->zrle.zlib.buffer + vs->zrle.zlib.offset; + zstream->avail_out = vs->zrle.zlib.capacity - vs->zrle.zlib.offset; + zstream->data_type = Z_BINARY; + + /* start encoding */ + if (deflate(zstream, Z_SYNC_FLUSH) != Z_OK) { + fprintf(stderr, "VNC: error during zrle compression\n"); + return -1; + } + + vs->zrle.zlib.offset = vs->zrle.zlib.capacity - zstream->avail_out; + return vs->zrle.zlib.offset; +} + +/* Try to work out whether to use RLE and/or a palette. We do this by + * estimating the number of bytes which will be generated and picking the + * method which results in the fewest bytes. Of course this may not result + * in the fewest bytes after compression... */ +static void zrle_choose_palette_rle(VncState *vs, int w, int h, + VncPalette *palette, int bpp_out, + int runs, int single_pixels, + int zywrle_level, + bool *use_rle, bool *use_palette) +{ + size_t estimated_bytes; + size_t plain_rle_bytes; + + *use_palette = *use_rle = false; + + estimated_bytes = w * h * (bpp_out / 8); /* start assuming raw */ + + if (bpp_out != 8) { + if (zywrle_level > 0 && !(zywrle_level & 0x80)) + estimated_bytes >>= zywrle_level; + } + + plain_rle_bytes = ((bpp_out / 8) + 1) * (runs + single_pixels); + + if (plain_rle_bytes < estimated_bytes) { + *use_rle = true; + estimated_bytes = plain_rle_bytes; + } + + if (palette_size(palette) < 128) { + int palette_rle_bytes; + + palette_rle_bytes = (bpp_out / 8) * palette_size(palette); + palette_rle_bytes += 2 * runs + single_pixels; + + if (palette_rle_bytes < estimated_bytes) { + *use_rle = true; + *use_palette = true; + estimated_bytes = palette_rle_bytes; + } + + if (palette_size(palette) < 17) { + int packed_bytes; + + packed_bytes = (bpp_out / 8) * palette_size(palette); + packed_bytes += w * h * + bits_per_packed_pixel[palette_size(palette)-1] / 8; + + if (packed_bytes < estimated_bytes) { + *use_rle = false; + *use_palette = true; + estimated_bytes = packed_bytes; + } + } + } +} + +static void zrle_write_u32(VncState *vs, uint32_t value) +{ + uint8_t buf[4]; + + buf[0] = ((uint8_t *)&value)[0]; + buf[1] = ((uint8_t *)&value)[1]; + buf[2] = ((uint8_t *)&value)[2]; + buf[3] = ((uint8_t *)&value)[3]; + + vnc_write(vs, buf, 4); +} + +static void zrle_write_u24a(VncState *vs, uint32_t value) +{ + uint8_t buf[3]; + + buf[0] = ((uint8_t *)&value)[0]; + buf[1] = ((uint8_t *)&value)[1]; + buf[2] = ((uint8_t *)&value)[2]; + + vnc_write(vs, buf, 3); +} + +static void zrle_write_u24b(VncState *vs, uint32_t value) +{ + uint8_t buf[3]; + + buf[0] = ((uint8_t *)&value)[1]; + buf[1] = ((uint8_t *)&value)[2]; + buf[2] = ((uint8_t *)&value)[3]; + + vnc_write(vs, buf, 3); +} + +static void zrle_write_u16(VncState *vs, uint16_t value) +{ + uint8_t buf[2]; + + buf[0] = ((uint8_t *)&value)[0]; + buf[1] = ((uint8_t *)&value)[1]; + + vnc_write(vs, buf, 2); +} + +static void zrle_write_u8(VncState *vs, uint8_t value) +{ + vnc_write_u8(vs, value); +} + +#define ENDIAN_LITTLE 0 +#define ENDIAN_BIG 1 +#define ENDIAN_NO 2 + +#define ZRLE_BPP 8 +#define ZYWRLE_ENDIAN ENDIAN_NO +#include "vnc-enc-zrle-template.c" +#undef ZRLE_BPP + +#define ZRLE_BPP 15 +#undef ZYWRLE_ENDIAN +#define ZYWRLE_ENDIAN ENDIAN_LITTLE +#include "vnc-enc-zrle-template.c" + +#undef ZYWRLE_ENDIAN +#define ZYWRLE_ENDIAN ENDIAN_BIG +#include "vnc-enc-zrle-template.c" + +#undef ZRLE_BPP +#define ZRLE_BPP 16 +#undef ZYWRLE_ENDIAN +#define ZYWRLE_ENDIAN ENDIAN_LITTLE +#include "vnc-enc-zrle-template.c" + +#undef ZYWRLE_ENDIAN +#define ZYWRLE_ENDIAN ENDIAN_BIG +#include "vnc-enc-zrle-template.c" + +#undef ZRLE_BPP +#define ZRLE_BPP 32 +#undef ZYWRLE_ENDIAN +#define ZYWRLE_ENDIAN ENDIAN_LITTLE +#include "vnc-enc-zrle-template.c" + +#undef ZYWRLE_ENDIAN +#define ZYWRLE_ENDIAN ENDIAN_BIG +#include "vnc-enc-zrle-template.c" + +#define ZRLE_COMPACT_PIXEL 24a +#undef ZYWRLE_ENDIAN +#define ZYWRLE_ENDIAN ENDIAN_LITTLE +#include "vnc-enc-zrle-template.c" + +#undef ZYWRLE_ENDIAN +#define ZYWRLE_ENDIAN ENDIAN_BIG +#include "vnc-enc-zrle-template.c" + +#undef ZRLE_COMPACT_PIXEL +#define ZRLE_COMPACT_PIXEL 24b +#undef ZYWRLE_ENDIAN +#define ZYWRLE_ENDIAN ENDIAN_LITTLE +#include "vnc-enc-zrle-template.c" + +#undef ZYWRLE_ENDIAN +#define ZYWRLE_ENDIAN ENDIAN_BIG +#include "vnc-enc-zrle-template.c" +#undef ZRLE_COMPACT_PIXEL +#undef ZRLE_BPP + +static int zrle_send_framebuffer_update(VncState *vs, int x, int y, + int w, int h) +{ + bool be = !!(vs->clientds.flags & QEMU_BIG_ENDIAN_FLAG); + size_t bytes; + int zywrle_level; + + if (vs->zrle.type == VNC_ENCODING_ZYWRLE) { + if (!vs->vd->lossy || vs->tight.quality < 0 || vs->tight.quality == 9) { + zywrle_level = 0; + vs->zrle.type = VNC_ENCODING_ZRLE; + } else if (vs->tight.quality < 3) { + zywrle_level = 3; + } else if (vs->tight.quality < 6) { + zywrle_level = 2; + } else { + zywrle_level = 1; + } + } else { + zywrle_level = 0; + } + + vnc_zrle_start(vs); + + switch(vs->clientds.pf.bytes_per_pixel) { + case 1: + zrle_encode_8ne(vs, x, y, w, h, zywrle_level); + break; + + case 2: + if (vs->clientds.pf.gmax > 0x1F) { + if (be) { + zrle_encode_16be(vs, x, y, w, h, zywrle_level); + } else { + zrle_encode_16le(vs, x, y, w, h, zywrle_level); + } + } else { + if (be) { + zrle_encode_15be(vs, x, y, w, h, zywrle_level); + } else { + zrle_encode_15le(vs, x, y, w, h, zywrle_level); + } + } + break; + + case 4: + { + bool fits_in_ls3bytes; + bool fits_in_ms3bytes; + + fits_in_ls3bytes = + ((vs->clientds.pf.rmax << vs->clientds.pf.rshift) < (1 << 24) && + (vs->clientds.pf.gmax << vs->clientds.pf.gshift) < (1 << 24) && + (vs->clientds.pf.bmax << vs->clientds.pf.bshift) < (1 << 24)); + + fits_in_ms3bytes = (vs->clientds.pf.rshift > 7 && + vs->clientds.pf.gshift > 7 && + vs->clientds.pf.bshift > 7); + + if ((fits_in_ls3bytes && !be) || (fits_in_ms3bytes && be)) { + if (be) { + zrle_encode_24abe(vs, x, y, w, h, zywrle_level); + } else { + zrle_encode_24ale(vs, x, y, w, h, zywrle_level); + } + } else if ((fits_in_ls3bytes && be) || (fits_in_ms3bytes && !be)) { + if (be) { + zrle_encode_24bbe(vs, x, y, w, h, zywrle_level); + } else { + zrle_encode_24ble(vs, x, y, w, h, zywrle_level); + } + } else { + if (be) { + zrle_encode_32be(vs, x, y, w, h, zywrle_level); + } else { + zrle_encode_32le(vs, x, y, w, h, zywrle_level); + } + } + } + break; + } + + vnc_zrle_stop(vs); + bytes = zrle_compress_data(vs, Z_DEFAULT_COMPRESSION); + vnc_framebuffer_update(vs, x, y, w, h, vs->zrle.type); + vnc_write_u32(vs, bytes); + vnc_write(vs, vs->zrle.zlib.buffer, vs->zrle.zlib.offset); + return 1; +} + +int vnc_zrle_send_framebuffer_update(VncState *vs, int x, int y, int w, int h) +{ + vs->zrle.type = VNC_ENCODING_ZRLE; + return zrle_send_framebuffer_update(vs, x, y, w, h); +} + +int vnc_zywrle_send_framebuffer_update(VncState *vs, int x, int y, int w, int h) +{ + vs->zrle.type = VNC_ENCODING_ZYWRLE; + return zrle_send_framebuffer_update(vs, x, y, w, h); +} + +void vnc_zrle_clear(VncState *vs) +{ + if (vs->zrle.stream.opaque) { + deflateEnd(&vs->zrle.stream); + } + buffer_free(&vs->zrle.zrle); + buffer_free(&vs->zrle.fb); + buffer_free(&vs->zrle.zlib); +} diff --git a/ui/vnc-enc-zrle.h b/ui/vnc-enc-zrle.h new file mode 100644 index 0000000..6b18213 --- /dev/null +++ b/ui/vnc-enc-zrle.h @@ -0,0 +1,40 @@ +/* + * QEMU VNC display driver: Zlib Run-length Encoding (ZRLE) + * + * From libvncserver/libvncserver/zrle.c + * Copyright (C) 2002 RealVNC Ltd. All Rights Reserved. + * Copyright (C) 2003 Sun Microsystems, Inc. + * + * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#ifndef VNC_ENCODING_ZRLE_H +#define VNC_ENCODING_ZRLE_H + +/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - + * ZRLE - encoding combining Zlib compression, tiling, palettisation and + * run-length encoding. + */ + +#define VNC_ZRLE_TILE_WIDTH 64 +#define VNC_ZRLE_TILE_HEIGHT 64 + +#endif diff --git a/ui/vnc-enc-zywrle-template.c b/ui/vnc-enc-zywrle-template.c new file mode 100644 index 0000000..4cde6e4 --- /dev/null +++ b/ui/vnc-enc-zywrle-template.c @@ -0,0 +1,170 @@ + +/******************************************************************** + * * + * THIS FILE IS PART OF THE 'ZYWRLE' VNC CODEC SOURCE CODE. * + * * + * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * + * GOVERNED BY A FOLLOWING BSD-STYLE SOURCE LICENSE. * + * PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * + * * + * THE 'ZYWRLE' VNC CODEC SOURCE CODE IS (C) COPYRIGHT 2006 * + * BY Hitachi Systems & Services, Ltd. * + * (Noriaki Yamazaki, Research & Developement Center) * + * * + * * + ******************************************************************** +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions +are met: + +- Redistributions of source code must retain the above copyright +notice, this list of conditions and the following disclaimer. + +- Redistributions in binary form must reproduce the above copyright +notice, this list of conditions and the following disclaimer in the +documentation and/or other materials provided with the distribution. + +- Neither the name of the Hitachi Systems & Services, Ltd. nor +the names of its contributors may be used to endorse or promote +products derived from this software without specific prior written +permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + ********************************************************************/ + +/* Change Log: + V0.02 : 2008/02/04 : Fix mis encode/decode when width != scanline + (Thanks Johannes Schindelin, author of LibVNC + Server/Client) + V0.01 : 2007/02/06 : Initial release +*/ + +/* +[References] + PLHarr: + Senecal, J. G., P. Lindstrom, M. A. Duchaineau, and K. I. Joy, + "An Improved N-Bit to N-Bit Reversible Haar-Like Transform," + Pacific Graphics 2004, October 2004, pp. 371-380. + EZW: + Shapiro, JM: Embedded Image Coding Using Zerotrees of Wavelet Coefficients, + IEEE Trans. Signal. Process., Vol.41, pp.3445-3462 (1993). +*/ + + +/* Template Macro stuffs. */ +#undef ZYWRLE_ANALYZE +#undef ZYWRLE_SYNTHESIZE + +#define ZYWRLE_SUFFIX ZRLE_CONCAT2(ZRLE_BPP,ZRLE_ENDIAN_SUFFIX) + +#define ZYWRLE_ANALYZE ZRLE_CONCAT2(zywrle_analyze_, ZYWRLE_SUFFIX) +#define ZYWRLE_SYNTHESIZE ZRLE_CONCAT2(zywrle_synthesize_,ZYWRLE_SUFFIX) + +#define ZYWRLE_RGBYUV ZRLE_CONCAT2(zywrle_rgbyuv_, ZYWRLE_SUFFIX) +#define ZYWRLE_YUVRGB ZRLE_CONCAT2(zywrle_yuvrgb_, ZYWRLE_SUFFIX) +#define ZYWRLE_YMASK ZRLE_CONCAT2(ZYWRLE_YMASK, ZRLE_BPP) +#define ZYWRLE_UVMASK ZRLE_CONCAT2(ZYWRLE_UVMASK, ZRLE_BPP) +#define ZYWRLE_LOAD_PIXEL ZRLE_CONCAT2(ZYWRLE_LOAD_PIXEL, ZRLE_BPP) +#define ZYWRLE_SAVE_PIXEL ZRLE_CONCAT2(ZYWRLE_SAVE_PIXEL, ZRLE_BPP) + +/* Packing/Unpacking pixel stuffs. + Endian conversion stuffs. */ +#undef S_0 +#undef S_1 +#undef L_0 +#undef L_1 +#undef L_2 + +#if ZYWRLE_ENDIAN == ENDIAN_BIG +# define S_0 1 +# define S_1 0 +# define L_0 3 +# define L_1 2 +# define L_2 1 +#else +# define S_0 0 +# define S_1 1 +# define L_0 0 +# define L_1 1 +# define L_2 2 +#endif + +#define ZYWRLE_QUANTIZE +#include "vnc-enc-zywrle.h" + +#ifndef ZRLE_COMPACT_PIXEL +static inline void ZYWRLE_RGBYUV(int *buf, ZRLE_PIXEL *data, + int width, int height, int scanline) +{ + int r, g, b; + int y, u, v; + int *line; + int *end; + + end = buf + height * width; + while (buf < end) { + line = buf + width; + while (buf < line) { + ZYWRLE_LOAD_PIXEL(data, r, g, b); + ZYWRLE_RGBYUV_(r, g, b, y, u, v, ZYWRLE_YMASK, ZYWRLE_UVMASK); + ZYWRLE_SAVE_COEFF(buf, v, y, u); + buf++; + data++; + } + data += scanline - width; + } +} + +static ZRLE_PIXEL *ZYWRLE_ANALYZE(ZRLE_PIXEL *dst, ZRLE_PIXEL *src, + int w, int h, int scanline, int level, + int *buf) { + int l; + int uw = w; + int uh = h; + int *top; + int *end; + int *line; + ZRLE_PIXEL *p; + int r, g, b; + int s; + int *ph; + + zywrle_calc_size(&w, &h, level); + + if (w == 0 || h == 0) { + return NULL; + } + uw -= w; + uh -= h; + + p = dst; + ZYWRLE_LOAD_UNALIGN(src,*(ZRLE_PIXEL*)top = *p;); + ZYWRLE_RGBYUV(buf, src, w, h, scanline); + wavelet(buf, w, h, level); + for (l = 0; l < level; l++) { + ZYWRLE_PACK_COEFF(buf, dst, 3, w, h, scanline, l); + ZYWRLE_PACK_COEFF(buf, dst, 2, w, h, scanline, l); + ZYWRLE_PACK_COEFF(buf, dst, 1, w, h, scanline, l); + if (l == level - 1) { + ZYWRLE_PACK_COEFF(buf, dst, 0, w, h, scanline, l); + } + } + ZYWRLE_SAVE_UNALIGN(dst,*dst = *(ZRLE_PIXEL*)top;); + return dst; +} +#endif /* ZRLE_COMPACT_PIXEL */ + +#undef ZYWRLE_RGBYUV +#undef ZYWRLE_YUVRGB +#undef ZYWRLE_LOAD_PIXEL +#undef ZYWRLE_SAVE_PIXEL diff --git a/ui/vnc-enc-zywrle.h b/ui/vnc-enc-zywrle.h new file mode 100644 index 0000000..722bd7d --- /dev/null +++ b/ui/vnc-enc-zywrle.h @@ -0,0 +1,652 @@ +/******************************************************************** + * * + * THIS FILE IS PART OF THE 'ZYWRLE' VNC CODEC SOURCE CODE. * + * * + * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * + * GOVERNED BY A FOLLOWING BSD-STYLE SOURCE LICENSE. * + * PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * + * * + * THE 'ZYWRLE' VNC CODEC SOURCE CODE IS (C) COPYRIGHT 2006 * + * BY Hitachi Systems & Services, Ltd. * + * (Noriaki Yamazaki, Research & Developement Center) * + * * + * * + ******************************************************************** +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions +are met: + +- Redistributions of source code must retain the above copyright +notice, this list of conditions and the following disclaimer. + +- Redistributions in binary form must reproduce the above copyright +notice, this list of conditions and the following disclaimer in the +documentation and/or other materials provided with the distribution. + +- Neither the name of the Hitachi Systems & Services, Ltd. nor +the names of its contributors may be used to endorse or promote +products derived from this software without specific prior written +permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + ********************************************************************/ + +#ifndef VNC_ENCODING_ZYWRLE_H +#define VNC_ENCODING_ZYWRLE_H + +/* Tables for Coefficients filtering. */ +#ifndef ZYWRLE_QUANTIZE +/* Type A:lower bit omitting of EZW style. */ +const static unsigned int zywrle_param[3][3]={ + {0x0000F000,0x00000000,0x00000000}, + {0x0000C000,0x00F0F0F0,0x00000000}, + {0x0000C000,0x00C0C0C0,0x00F0F0F0}, +/* {0x0000FF00,0x00000000,0x00000000}, + {0x0000FF00,0x00FFFFFF,0x00000000}, + {0x0000FF00,0x00FFFFFF,0x00FFFFFF}, */ +}; +#else +/* Type B:Non liner quantization filter. */ +static const signed char zywrle_conv[4][256]={ +{ /* bi=5, bo=5 r=0.0:PSNR=24.849 */ + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, +}, +{ /* bi=5, bo=5 r=2.0:PSNR=74.031 */ + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 32, + 32, 32, 32, 32, 32, 32, 32, 32, + 32, 32, 32, 32, 32, 32, 32, 32, + 48, 48, 48, 48, 48, 48, 48, 48, + 48, 48, 48, 56, 56, 56, 56, 56, + 56, 56, 56, 56, 64, 64, 64, 64, + 64, 64, 64, 64, 72, 72, 72, 72, + 72, 72, 72, 72, 80, 80, 80, 80, + 80, 80, 88, 88, 88, 88, 88, 88, + 88, 88, 88, 88, 88, 88, 96, 96, + 96, 96, 96, 104, 104, 104, 104, 104, + 104, 104, 104, 104, 104, 112, 112, 112, + 112, 112, 112, 112, 112, 112, 120, 120, + 120, 120, 120, 120, 120, 120, 120, 120, + 0, -120, -120, -120, -120, -120, -120, -120, + -120, -120, -120, -112, -112, -112, -112, -112, + -112, -112, -112, -112, -104, -104, -104, -104, + -104, -104, -104, -104, -104, -104, -96, -96, + -96, -96, -96, -88, -88, -88, -88, -88, + -88, -88, -88, -88, -88, -88, -88, -80, + -80, -80, -80, -80, -80, -72, -72, -72, + -72, -72, -72, -72, -72, -64, -64, -64, + -64, -64, -64, -64, -64, -56, -56, -56, + -56, -56, -56, -56, -56, -56, -48, -48, + -48, -48, -48, -48, -48, -48, -48, -48, + -48, -32, -32, -32, -32, -32, -32, -32, + -32, -32, -32, -32, -32, -32, -32, -32, + -32, -32, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, +}, +{ /* bi=5, bo=4 r=2.0:PSNR=64.441 */ + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 48, 48, 48, 48, 48, 48, 48, 48, + 48, 48, 48, 48, 48, 48, 48, 48, + 48, 48, 48, 48, 48, 48, 48, 48, + 64, 64, 64, 64, 64, 64, 64, 64, + 64, 64, 64, 64, 64, 64, 64, 64, + 80, 80, 80, 80, 80, 80, 80, 80, + 80, 80, 80, 80, 80, 88, 88, 88, + 88, 88, 88, 88, 88, 88, 88, 88, + 104, 104, 104, 104, 104, 104, 104, 104, + 104, 104, 104, 112, 112, 112, 112, 112, + 112, 112, 112, 112, 120, 120, 120, 120, + 120, 120, 120, 120, 120, 120, 120, 120, + 0, -120, -120, -120, -120, -120, -120, -120, + -120, -120, -120, -120, -120, -112, -112, -112, + -112, -112, -112, -112, -112, -112, -104, -104, + -104, -104, -104, -104, -104, -104, -104, -104, + -104, -88, -88, -88, -88, -88, -88, -88, + -88, -88, -88, -88, -80, -80, -80, -80, + -80, -80, -80, -80, -80, -80, -80, -80, + -80, -64, -64, -64, -64, -64, -64, -64, + -64, -64, -64, -64, -64, -64, -64, -64, + -64, -48, -48, -48, -48, -48, -48, -48, + -48, -48, -48, -48, -48, -48, -48, -48, + -48, -48, -48, -48, -48, -48, -48, -48, + -48, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, +}, +{ /* bi=5, bo=2 r=2.0:PSNR=43.175 */ + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 88, 88, 88, 88, 88, 88, 88, 88, + 88, 88, 88, 88, 88, 88, 88, 88, + 88, 88, 88, 88, 88, 88, 88, 88, + 88, 88, 88, 88, 88, 88, 88, 88, + 88, 88, 88, 88, 88, 88, 88, 88, + 88, 88, 88, 88, 88, 88, 88, 88, + 88, 88, 88, 88, 88, 88, 88, 88, + 88, 88, 88, 88, 88, 88, 88, 88, + 0, -88, -88, -88, -88, -88, -88, -88, + -88, -88, -88, -88, -88, -88, -88, -88, + -88, -88, -88, -88, -88, -88, -88, -88, + -88, -88, -88, -88, -88, -88, -88, -88, + -88, -88, -88, -88, -88, -88, -88, -88, + -88, -88, -88, -88, -88, -88, -88, -88, + -88, -88, -88, -88, -88, -88, -88, -88, + -88, -88, -88, -88, -88, -88, -88, -88, + -88, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, +} +}; + +static const signed char *zywrle_param[3][3][3]={ + {{zywrle_conv[0], zywrle_conv[2], zywrle_conv[0]}, + {zywrle_conv[0], zywrle_conv[0], zywrle_conv[0]}, + {zywrle_conv[0], zywrle_conv[0], zywrle_conv[0]}}, + {{zywrle_conv[0], zywrle_conv[3], zywrle_conv[0]}, + {zywrle_conv[1], zywrle_conv[1], zywrle_conv[1]}, + {zywrle_conv[0], zywrle_conv[0], zywrle_conv[0]}}, + {{zywrle_conv[0], zywrle_conv[3], zywrle_conv[0]}, + {zywrle_conv[2], zywrle_conv[2], zywrle_conv[2]}, + {zywrle_conv[1], zywrle_conv[1], zywrle_conv[1]}}, +}; +#endif + +/* Load/Save pixel stuffs. */ +#define ZYWRLE_YMASK15 0xFFFFFFF8 +#define ZYWRLE_UVMASK15 0xFFFFFFF8 +#define ZYWRLE_LOAD_PIXEL15(src, r, g, b) \ + do { \ + r = (((uint8_t*)src)[S_1]<< 1)& 0xF8; \ + g = (((uint8_t*)src)[S_1]<< 6) | (((uint8_t*)src)[S_0]>> 2); \ + g &= 0xF8; \ + b = (((uint8_t*)src)[S_0]<< 3)& 0xF8; \ + } while (0) + +#define ZYWRLE_SAVE_PIXEL15(dst, r, g, b) \ + do { \ + r &= 0xF8; \ + g &= 0xF8; \ + b &= 0xF8; \ + ((uint8_t*)dst)[S_1] = (uint8_t)((r >> 1)|(g >> 6)); \ + ((uint8_t*)dst)[S_0] = (uint8_t)(((b >> 3)|(g << 2))& 0xFF); \ + } while (0) + +#define ZYWRLE_YMASK16 0xFFFFFFFC +#define ZYWRLE_UVMASK16 0xFFFFFFF8 +#define ZYWRLE_LOAD_PIXEL16(src, r, g, b) \ + do { \ + r = ((uint8_t*)src)[S_1] & 0xF8; \ + g = (((uint8_t*)src)[S_1]<< 5) | (((uint8_t*)src)[S_0] >> 3); \ + g &= 0xFC; \ + b = (((uint8_t*)src)[S_0]<< 3) & 0xF8; \ + } while (0) + +#define ZYWRLE_SAVE_PIXEL16(dst, r, g,b) \ + do { \ + r &= 0xF8; \ + g &= 0xFC; \ + b &= 0xF8; \ + ((uint8_t*)dst)[S_1] = (uint8_t)(r | (g >> 5)); \ + ((uint8_t*)dst)[S_0] = (uint8_t)(((b >> 3)|(g << 3)) & 0xFF); \ + } while (0) + +#define ZYWRLE_YMASK32 0xFFFFFFFF +#define ZYWRLE_UVMASK32 0xFFFFFFFF +#define ZYWRLE_LOAD_PIXEL32(src, r, g, b) \ + do { \ + r = ((uint8_t*)src)[L_2]; \ + g = ((uint8_t*)src)[L_1]; \ + b = ((uint8_t*)src)[L_0]; \ + } while (0) +#define ZYWRLE_SAVE_PIXEL32(dst, r, g, b) \ + do { \ + ((uint8_t*)dst)[L_2] = (uint8_t)r; \ + ((uint8_t*)dst)[L_1] = (uint8_t)g; \ + ((uint8_t*)dst)[L_0] = (uint8_t)b; \ + } while (0) + +static inline void harr(int8_t *px0, int8_t *px1) +{ + /* Piecewise-Linear Harr(PLHarr) */ + int x0 = (int)*px0, x1 = (int)*px1; + int orgx0 = x0, orgx1 = x1; + + if ((x0 ^ x1) & 0x80) { + /* differ sign */ + x1 += x0; + if (((x1 ^ orgx1) & 0x80) == 0) { + /* |x1| > |x0| */ + x0 -= x1; /* H = -B */ + } + } else { + /* same sign */ + x0 -= x1; + if (((x0 ^ orgx0) & 0x80) == 0) { + /* |x0| > |x1| */ + x1 += x0; /* L = A */ + } + } + *px0 = (int8_t)x1; + *px1 = (int8_t)x0; +} + +/* + 1D-Wavelet transform. + + In coefficients array, the famous 'pyramid' decomposition is well used. + + 1D Model: + |L0L0L0L0|L0L0L0L0|H0H0H0H0|H0H0H0H0| : level 0 + |L1L1L1L1|H1H1H1H1|H0H0H0H0|H0H0H0H0| : level 1 + + But this method needs line buffer because H/L is different position from X0/X1. + So, I used 'interleave' decomposition instead of it. + + 1D Model: + |L0H0L0H0|L0H0L0H0|L0H0L0H0|L0H0L0H0| : level 0 + |L1H0H1H0|L1H0H1H0|L1H0H1H0|L1H0H1H0| : level 1 + + In this method, H/L and X0/X1 is always same position. + This lead us to more speed and less memory. + Of cause, the result of both method is quite same + because it's only difference that coefficient position. +*/ +static inline void wavelet_level(int *data, int size, int l, int skip_pixel) +{ + int s, ofs; + int8_t *px0; + int8_t *end; + + px0 = (int8_t*)data; + s = (8 << l) * skip_pixel; + end = px0 + (size >> (l + 1)) * s; + s -= 2; + ofs = (4 << l) * skip_pixel; + + while (px0 < end) { + harr(px0, px0 + ofs); + px0++; + harr(px0, px0 + ofs); + px0++; + harr(px0, px0 + ofs); + px0 += s; + } +} + +#ifndef ZYWRLE_QUANTIZE +/* Type A:lower bit omitting of EZW style. */ +static inline void filter_wavelet_square(int *buf, int width, int height, + int level, int l) +{ + int r, s; + int x, y; + int *h; + const unsigned int *m; + + m = &(zywrle_param[level - 1][l]); + s = 2 << l; + + for (r = 1; r < 4; r++) { + h = buf; + if (r & 0x01) + h += s >> 1; + if (r & 0x02) + h += (s >> 1) * width; + for (y = 0; y < height / s; y++) { + for (x = 0; x < width / s; x++) { + /* + these are same following code. + h[x] = h[x] / (~m[x]+1) * (~m[x]+1); + ( round h[x] with m[x] bit ) + '&' operator isn't 'round' but is 'floor'. + So, we must offset when h[x] is negative. + */ + if (((int8_t*)h)[0] & 0x80) + ((int8_t*)h)[0] += ~((int8_t*)m)[0]; + if (((int8_t*)h)[1] & 0x80) + ((int8_t*)h)[1] += ~((int8_t*)m)[1]; + if (((int8_t*)h)[2] & 0x80) + ((int8_t*)h)[2] += ~((int8_t*)m)[2]; + *h &= *m; + h += s; + } + h += (s-1)*width; + } + } +} +#else +/* + Type B:Non liner quantization filter. + + Coefficients have Gaussian curve and smaller value which is + large part of coefficients isn't more important than larger value. + So, I use filter of Non liner quantize/dequantize table. + In general, Non liner quantize formula is explained as following. + + y=f(x) = sign(x)*round( ((abs(x)/(2^7))^ r )* 2^(bo-1) )*2^(8-bo) + x=f-1(y) = sign(y)*round( ((abs(y)/(2^7))^(1/r))* 2^(bi-1) )*2^(8-bi) + ( r:power coefficient bi:effective MSB in input bo:effective MSB in output ) + + r < 1.0 : Smaller value is more important than larger value. + r > 1.0 : Larger value is more important than smaller value. + r = 1.0 : Liner quantization which is same with EZW style. + + r = 0.75 is famous non liner quantization used in MP3 audio codec. + In contrast to audio data, larger value is important in wavelet coefficients. + So, I select r = 2.0 table( quantize is x^2, dequantize sqrt(x) ). + + As compared with EZW style liner quantization, this filter tended to be + more sharp edge and be more compression rate but be more blocking noise and be + less quality. Especially, the surface of graphic objects has distinguishable + noise in middle quality mode. + + We need only quantized-dequantized(filtered) value rather than quantized value + itself because all values are packed or palette-lized in later ZRLE section. + This lead us not to need to modify client decoder when we change + the filtering procedure in future. + Client only decodes coefficients given by encoder. +*/ +static inline void filter_wavelet_square(int *buf, int width, int height, + int level, int l) +{ + int r, s; + int x, y; + int *h; + const int8_t **m; + + m = zywrle_param[level - 1][l]; + s = 2 << l; + + for (r = 1; r < 4; r++) { + h = buf; + if (r & 0x01) + h += s >> 1; + if (r & 0x02) + h += (s >> 1) * width; + for (y = 0; y < height / s; y++) { + for (x = 0; x < width / s; x++) { + ((int8_t*)h)[0] = m[0][((uint8_t*)h)[0]]; + ((int8_t*)h)[1] = m[1][((uint8_t*)h)[1]]; + ((int8_t*)h)[2] = m[2][((uint8_t*)h)[2]]; + h += s; + } + h += (s - 1) * width; + } + } +} +#endif + +static inline void wavelet(int *buf, int width, int height, int level) +{ + int l, s; + int *top; + int *end; + + for (l = 0; l < level; l++) { + top = buf; + end = buf + height * width; + s = width << l; + while (top < end) { + wavelet_level(top, width, l, 1); + top += s; + } + top = buf; + end = buf + width; + s = 1<<l; + while (top < end) { + wavelet_level(top, height, l, width); + top += s; + } + filter_wavelet_square(buf, width, height, level, l); + } +} + + +/* Load/Save coefficients stuffs. + Coefficients manages as 24 bits little-endian pixel. */ +#define ZYWRLE_LOAD_COEFF(src, r, g, b) \ + do { \ + r = ((int8_t*)src)[2]; \ + g = ((int8_t*)src)[1]; \ + b = ((int8_t*)src)[0]; \ + } while (0) + +#define ZYWRLE_SAVE_COEFF(dst, r, g, b) \ + do { \ + ((int8_t*)dst)[2] = (int8_t)r; \ + ((int8_t*)dst)[1] = (int8_t)g; \ + ((int8_t*)dst)[0] = (int8_t)b; \ + } while (0) + +/* + RGB <=> YUV conversion stuffs. + YUV coversion is explained as following formula in strict meaning: + Y = 0.299R + 0.587G + 0.114B ( 0<=Y<=255) + U = -0.169R - 0.331G + 0.500B (-128<=U<=127) + V = 0.500R - 0.419G - 0.081B (-128<=V<=127) + + I use simple conversion RCT(reversible color transform) which is described + in JPEG-2000 specification. + Y = (R + 2G + B)/4 ( 0<=Y<=255) + U = B-G (-256<=U<=255) + V = R-G (-256<=V<=255) +*/ + +/* RCT is N-bit RGB to N-bit Y and N+1-bit UV. + For make Same N-bit, UV is lossy. + More exact PLHarr, we reduce to odd range(-127<=x<=127). */ +#define ZYWRLE_RGBYUV_(r, g, b, y, u, v, ymask, uvmask) \ + do { \ + y = (r + (g << 1) + b) >> 2; \ + u = b - g; \ + v = r - g; \ + y -= 128; \ + u >>= 1; \ + v >>= 1; \ + y &= ymask; \ + u &= uvmask; \ + v &= uvmask; \ + if (y == -128) { \ + y += (0xFFFFFFFF - ymask + 1); \ + } \ + if (u == -128) { \ + u += (0xFFFFFFFF - uvmask + 1); \ + } \ + if (v == -128) { \ + v += (0xFFFFFFFF - uvmask + 1); \ + } \ + } while (0) + + +/* + coefficient packing/unpacking stuffs. + Wavelet transform makes 4 sub coefficient image from 1 original image. + + model with pyramid decomposition: + +------+------+ + | | | + | L | Hx | + | | | + +------+------+ + | | | + | H | Hxy | + | | | + +------+------+ + + So, we must transfer each sub images individually in strict meaning. + But at least ZRLE meaning, following one decompositon image is same as + avobe individual sub image. I use this format. + (Strictly saying, transfer order is reverse(Hxy->Hy->Hx->L) + for simplified procedure for any wavelet level.) + + +------+------+ + | L | + +------+------+ + | Hx | + +------+------+ + | Hy | + +------+------+ + | Hxy | + +------+------+ +*/ +#define ZYWRLE_INC_PTR(data) \ + do { \ + data++; \ + if( data - p >= (w + uw) ) { \ + data += scanline-(w + uw); \ + p = data; \ + } \ + } while (0) + +#define ZYWRLE_TRANSFER_COEFF(buf, data, t, w, h, scanline, level, TRANS) \ + do { \ + ph = buf; \ + s = 2 << level; \ + if (t & 0x01) { \ + ph += s >> 1; \ + } \ + if (t & 0x02) { \ + ph += (s >> 1) * w; \ + } \ + end = ph + h * w; \ + while (ph < end) { \ + line = ph + w; \ + while (ph < line) { \ + TRANS \ + ZYWRLE_INC_PTR(data); \ + ph += s; \ + } \ + ph += (s - 1) * w; \ + } \ + } while (0) + +#define ZYWRLE_PACK_COEFF(buf, data, t, width, height, scanline, level) \ + ZYWRLE_TRANSFER_COEFF(buf, data, t, width, height, scanline, level, \ + ZYWRLE_LOAD_COEFF(ph, r, g, b); \ + ZYWRLE_SAVE_PIXEL(data, r, g, b);) + +#define ZYWRLE_UNPACK_COEFF(buf, data, t, width, height, scanline, level) \ + ZYWRLE_TRANSFER_COEFF(buf, data, t, width, height, scanline, level, \ + ZYWRLE_LOAD_PIXEL(data, r, g, b); \ + ZYWRLE_SAVE_COEFF(ph, r, g, b);) + +#define ZYWRLE_SAVE_UNALIGN(data, TRANS) \ + do { \ + top = buf + w * h; \ + end = buf + (w + uw) * (h + uh); \ + while (top < end) { \ + TRANS \ + ZYWRLE_INC_PTR(data); \ + top++; \ + } \ + } while (0) + +#define ZYWRLE_LOAD_UNALIGN(data,TRANS) \ + do { \ + top = buf + w * h; \ + if (uw) { \ + p = data + w; \ + end = (int*)(p + h * scanline); \ + while (p < (ZRLE_PIXEL*)end) { \ + line = (int*)(p + uw); \ + while (p < (ZRLE_PIXEL*)line) { \ + TRANS \ + p++; \ + top++; \ + } \ + p += scanline - uw; \ + } \ + } \ + if (uh) { \ + p = data + h * scanline; \ + end = (int*)(p + uh * scanline); \ + while (p < (ZRLE_PIXEL*)end) { \ + line = (int*)(p + w); \ + while (p < (ZRLE_PIXEL*)line) { \ + TRANS \ + p++; \ + top++; \ + } \ + p += scanline - w; \ + } \ + } \ + if (uw && uh) { \ + p= data + w + h * scanline; \ + end = (int*)(p + uh * scanline); \ + while (p < (ZRLE_PIXEL*)end) { \ + line = (int*)(p + uw); \ + while (p < (ZRLE_PIXEL*)line) { \ + TRANS \ + p++; \ + top++; \ + } \ + p += scanline-uw; \ + } \ + } \ + } while (0) + +static inline void zywrle_calc_size(int *w, int *h, int level) +{ + *w &= ~((1 << level) - 1); + *h &= ~((1 << level) - 1); +} + +#endif diff --git a/ui/vnc-jobs-async.c b/ui/vnc-jobs-async.c index 31f8436..b98dc79 100644 --- a/ui/vnc-jobs-async.c +++ b/ui/vnc-jobs-async.c @@ -172,6 +172,7 @@ static void vnc_async_encoding_start(VncState *orig, VncState *local) local->tight = orig->tight; local->zlib = orig->zlib; local->hextile = orig->hextile; + local->zrle = orig->zrle; local->output = queue->buffer; local->csock = -1; /* Don't do any network work on this thread */ @@ -183,6 +184,7 @@ static void vnc_async_encoding_end(VncState *orig, VncState *local) orig->tight = local->tight; orig->zlib = local->zlib; orig->hextile = local->hextile; + orig->zrle = local->zrle; orig->lossy_rect = local->lossy_rect; } diff --git a/ui/vnc.c b/ui/vnc.c index e1643d1..227efb6 100644 --- a/ui/vnc.c +++ b/ui/vnc.c @@ -696,6 +696,12 @@ int vnc_send_framebuffer_update(VncState *vs, int x, int y, int w, int h) case VNC_ENCODING_TIGHT_PNG: n = vnc_tight_png_send_framebuffer_update(vs, x, y, w, h); break; + case VNC_ENCODING_ZRLE: + n = vnc_zrle_send_framebuffer_update(vs, x, y, w, h); + break; + case VNC_ENCODING_ZYWRLE: + n = vnc_zywrle_send_framebuffer_update(vs, x, y, w, h); + break; default: vnc_framebuffer_update(vs, x, y, w, h, VNC_ENCODING_RAW); n = vnc_raw_send_framebuffer_update(vs, x, y, w, h); @@ -1028,6 +1034,7 @@ static void vnc_disconnect_finish(VncState *vs) vnc_zlib_clear(vs); vnc_tight_clear(vs); + vnc_zrle_clear(vs); #ifdef CONFIG_VNC_TLS vnc_tls_client_cleanup(vs); @@ -1766,6 +1773,14 @@ static void set_encodings(VncState *vs, int32_t *encodings, size_t n_encodings) vs->features |= VNC_FEATURE_ZLIB_MASK; vs->vnc_encoding = enc; break; + case VNC_ENCODING_ZRLE: + vs->features |= VNC_FEATURE_ZRLE_MASK; + vs->vnc_encoding = enc; + break; + case VNC_ENCODING_ZYWRLE: + vs->features |= VNC_FEATURE_ZYWRLE_MASK; + vs->vnc_encoding = enc; + break; case VNC_ENCODING_DESKTOPRESIZE: vs->features |= VNC_FEATURE_RESIZE_MASK; break; diff --git a/ui/vnc.h b/ui/vnc.h index 00bd21c..5cfa247 100644 --- a/ui/vnc.h +++ b/ui/vnc.h @@ -39,6 +39,8 @@ #include <stdbool.h> #include "keymaps.h" +#include "vnc-palette.h" +#include "vnc-enc-zrle.h" // #define _VNC_DEBUG 1 @@ -179,6 +181,20 @@ typedef struct VncZlib { int level; } VncZlib; +typedef struct VncZrle { + int type; + Buffer fb; + Buffer zrle; + Buffer tmp; + Buffer zlib; + z_stream stream; + VncPalette palette; +} VncZrle; + +typedef struct VncZywrle { + int buf[VNC_ZRLE_TILE_WIDTH * VNC_ZRLE_TILE_HEIGHT]; +} VncZywrle; + #ifdef CONFIG_VNC_THREAD struct VncRect { @@ -272,7 +288,8 @@ struct VncState VncTight tight; VncZlib zlib; VncHextile hextile; - + VncZrle zrle; + VncZywrle zywrle; Notifier mouse_mode_notifier; @@ -376,6 +393,8 @@ enum { #define VNC_FEATURE_COPYRECT 6 #define VNC_FEATURE_RICH_CURSOR 7 #define VNC_FEATURE_TIGHT_PNG 8 +#define VNC_FEATURE_ZRLE 9 +#define VNC_FEATURE_ZYWRLE 10 #define VNC_FEATURE_RESIZE_MASK (1 << VNC_FEATURE_RESIZE) #define VNC_FEATURE_HEXTILE_MASK (1 << VNC_FEATURE_HEXTILE) @@ -386,6 +405,8 @@ enum { #define VNC_FEATURE_COPYRECT_MASK (1 << VNC_FEATURE_COPYRECT) #define VNC_FEATURE_RICH_CURSOR_MASK (1 << VNC_FEATURE_RICH_CURSOR) #define VNC_FEATURE_TIGHT_PNG_MASK (1 << VNC_FEATURE_TIGHT_PNG) +#define VNC_FEATURE_ZRLE_MASK (1 << VNC_FEATURE_ZRLE) +#define VNC_FEATURE_ZYWRLE_MASK (1 << VNC_FEATURE_ZYWRLE) /* Client -> Server message IDs */ @@ -520,4 +541,8 @@ int vnc_tight_png_send_framebuffer_update(VncState *vs, int x, int y, int w, int h); void vnc_tight_clear(VncState *vs); +int vnc_zrle_send_framebuffer_update(VncState *vs, int x, int y, int w, int h); +int vnc_zywrle_send_framebuffer_update(VncState *vs, int x, int y, int w, int h); +void vnc_zrle_clear(VncState *vs); + #endif /* __QEMU_VNC_H */ -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* Re: [Qemu-devel] [PATCH v2 08/15] vnc: Add ZRLE and ZYWRLE encodings. 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 08/15] vnc: Add ZRLE and ZYWRLE encodings Corentin Chary @ 2010-11-11 18:58 ` Blue Swirl 0 siblings, 0 replies; 21+ messages in thread From: Blue Swirl @ 2010-11-11 18:58 UTC (permalink / raw) To: Corentin Chary Cc: Anthony Liguori, Andre Przywara, Qemu-development List, Alexander Graf On Thu, Nov 11, 2010 at 4:56 PM, Corentin Chary <corentincj@iksaif.net> wrote: > Add ZRLE [1] and ZYWRLE [2] encodings. The code is inspire^W stolen > from libvncserver (again), but have been rewriten to match QEMU coding > style. > > [1] http://www.realvnc.com/docs/rfbproto.pdf > [2] http://micro-vnc.jp/research/remote_desktop_ng/ZYWRLE/publications/ > > Signed-off-by: Corentin Chary <corentincj@iksaif.net> > --- > Makefile.objs | 1 + > ui/vnc-enc-zrle-template.c | 275 ++++++++++++++++++ > ui/vnc-enc-zrle.c | 389 +++++++++++++++++++++++++ > ui/vnc-enc-zrle.h | 40 +++ > ui/vnc-enc-zywrle-template.c | 170 +++++++++++ > ui/vnc-enc-zywrle.h | 652 ++++++++++++++++++++++++++++++++++++++++++ > ui/vnc-jobs-async.c | 2 + > ui/vnc.c | 15 + > ui/vnc.h | 27 ++- > 9 files changed, 1570 insertions(+), 1 deletions(-) > create mode 100644 ui/vnc-enc-zrle-template.c > create mode 100644 ui/vnc-enc-zrle.c > create mode 100644 ui/vnc-enc-zrle.h > create mode 100644 ui/vnc-enc-zywrle-template.c > create mode 100644 ui/vnc-enc-zywrle.h > > diff --git a/Makefile.objs b/Makefile.objs > index 15569af..3da959c 100644 > --- a/Makefile.objs > +++ b/Makefile.objs > @@ -121,6 +121,7 @@ ui-obj-$(CONFIG_CURSES) += curses.o > ui-obj-y += vnc.o d3des.o > ui-obj-y += vnc-enc-zlib.o vnc-enc-hextile.o > ui-obj-y += vnc-enc-tight.o vnc-palette.o > +ui-obj-y += vnc-enc-zrle.o > ui-obj-$(CONFIG_VNC_TLS) += vnc-tls.o vnc-auth-vencrypt.o > ui-obj-$(CONFIG_VNC_SASL) += vnc-auth-sasl.o > ui-obj-$(CONFIG_COCOA) += cocoa.o > diff --git a/ui/vnc-enc-zrle-template.c b/ui/vnc-enc-zrle-template.c > new file mode 100644 > index 0000000..94e92fb > --- /dev/null > +++ b/ui/vnc-enc-zrle-template.c > @@ -0,0 +1,275 @@ > +/* > + * QEMU VNC display driver: Zlib Run-length Encoding (ZRLE) > + * > + * From libvncserver/libvncserver/zrleencodetemplate.c > + * Copyright (C) 2002 RealVNC Ltd. All Rights Reserved. > + * Copyright (C) 2003 Sun Microsystems, Inc. > + * > + * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> > + * > + * This is free software; you can redistribute it and/or modify > + * it under the terms of the GNU General Public License as published by > + * the Free Software Foundation; either version 2 of the License, or > + * (at your option) any later version. > + * > + * This software is distributed in the hope that it will be useful, > + * but WITHOUT ANY WARRANTY; without even the implied warranty of > + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the > + * GNU General Public License for more details. > + * > + * You should have received a copy of the GNU General Public License > + * along with this software; if not, write to the Free Software > + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, > + * USA. The current address of FSF is: 51 Franklin Street, Fifth Floor Boston, MA 02110-1301 USA However, please use the URL version like used elsewhere. > + */ > + > +/* > + * Before including this file, you must define a number of CPP macros. > + * > + * ZRLE_BPP should be 8, 16 or 32 depending on the bits per pixel. > + * > + * Note that the buf argument to ZRLE_ENCODE needs to be at least one pixel > + * bigger than the largest tile of pixel data, since the ZRLE encoding > + * algorithm writes to the position one past the end of the pixel data. > + */ > + > + > +#include <assert.h> > + > +#undef ZRLE_ENDIAN_SUFFIX > + > +#if ZYWRLE_ENDIAN == ENDIAN_LITTLE > +#define ZRLE_ENDIAN_SUFFIX le > +#elif ZYWRLE_ENDIAN == ENDIAN_BIG > +#define ZRLE_ENDIAN_SUFFIX be > +#else > +#define ZRLE_ENDIAN_SUFFIX ne > +#endif > + > +#ifndef ZRLE_CONCAT > +#define ZRLE_CONCAT_I(a, b) a##b > +#define ZRLE_CONCAT2(a, b) ZRLE_CONCAT_I(a, b) > +#define ZRLE_CONCAT3(a, b, c) ZRLE_CONCAT2(a, ZRLE_CONCAT2(b, c)) > +#endif > + > +#ifdef ZRLE_COMPACT_PIXEL > +#define ZRLE_ENCODE_SUFFIX ZRLE_CONCAT2(ZRLE_COMPACT_PIXEL,ZRLE_ENDIAN_SUFFIX) > +#define ZRLE_WRITE_SUFFIX ZRLE_COMPACT_PIXEL > +#define ZRLE_PIXEL ZRLE_CONCAT3(uint,ZRLE_BPP,_t) > +#define ZRLE_BPP_OUT 24 > +#elif ZRLE_BPP == 15 > +#define ZRLE_ENCODE_SUFFIX ZRLE_CONCAT2(ZRLE_BPP,ZRLE_ENDIAN_SUFFIX) > +#define ZRLE_WRITE_SUFFIX 16 > +#define ZRLE_PIXEL uint16_t > +#define ZRLE_BPP_OUT 16 > +#else > +#define ZRLE_ENCODE_SUFFIX ZRLE_CONCAT2(ZRLE_BPP,ZRLE_ENDIAN_SUFFIX) > +#define ZRLE_WRITE_SUFFIX ZRLE_BPP > +#define ZRLE_BPP_OUT ZRLE_BPP > +#define ZRLE_PIXEL ZRLE_CONCAT3(uint,ZRLE_BPP,_t) > +#endif > + > +#define ZRLE_WRITE_PIXEL ZRLE_CONCAT2(zrle_write_u, ZRLE_WRITE_SUFFIX) > +#define ZRLE_ENCODE ZRLE_CONCAT2(zrle_encode_, ZRLE_ENCODE_SUFFIX) > +#define ZRLE_ENCODE_TILE ZRLE_CONCAT2(zrle_encode_tile, ZRLE_ENCODE_SUFFIX) > +#define ZRLE_WRITE_PALETTE ZRLE_CONCAT2(zrle_write_palette,ZRLE_ENCODE_SUFFIX) > + > +static void ZRLE_ENCODE_TILE(VncState *vs, ZRLE_PIXEL *data, int w, int h, > + int zywrle_level); > + > +#if ZRLE_BPP != 8 > +#include "vnc-enc-zywrle-template.c" > +#endif > + > + > +static void ZRLE_ENCODE(VncState *vs, int x, int y, int w, int h, > + int zywrle_level) > +{ > + int ty; > + > + for (ty = y; ty < y + h; ty += VNC_ZRLE_TILE_HEIGHT) { > + > + int tx, th; > + > + th = MIN(VNC_ZRLE_TILE_HEIGHT, y + h - ty); > + > + for (tx = x; tx < x + w; tx += VNC_ZRLE_TILE_WIDTH) { > + int tw; > + ZRLE_PIXEL *buf; > + > + tw = MIN(VNC_ZRLE_TILE_WIDTH, x + w - tx); > + > + buf = zrle_convert_fb(vs, tx, ty, tw, th, ZRLE_BPP); > + ZRLE_ENCODE_TILE(vs, buf, tw, th, zywrle_level); > + } > + } > +} > + > +static void ZRLE_ENCODE_TILE(VncState *vs, ZRLE_PIXEL *data, int w, int h, > + int zywrle_level) > +{ > + VncPalette *palette = &vs->zrle.palette; > + > + int runs = 0; > + int single_pixels = 0; > + > + bool use_rle; > + bool use_palette; > + > + int i; > + > + ZRLE_PIXEL *ptr = data; > + ZRLE_PIXEL *end = ptr + h * w; > + *end = ~*(end-1); /* one past the end is different so the while loop ends */ > + > + /* Real limit is 127 but we wan't a way to know if there is more than 127 */ > + palette_init(palette, 256, ZRLE_BPP); > + > + while (ptr < end) { > + ZRLE_PIXEL pix = *ptr; > + if (*++ptr != pix) { /* FIXME */ > + single_pixels++; > + } else { > + while (*++ptr == pix) ; > + runs++; > + } > + palette_put(palette, pix); > + } > + > + /* Solid tile is a special case */ > + > + if (palette_size(palette) == 1) { > + bool found; > + > + vnc_write_u8(vs, 1); > + ZRLE_WRITE_PIXEL(vs, palette_color(palette, 0, &found)); > + return; > + } > + > + zrle_choose_palette_rle(vs, w, h, palette, ZRLE_BPP_OUT, > + runs, single_pixels, zywrle_level, > + &use_rle, &use_palette); > + > + if (!use_palette) { > + vnc_write_u8(vs, (use_rle ? 128 : 0)); > + } else { > + uint32_t colors[VNC_PALETTE_MAX_SIZE]; > + size_t size = palette_size(palette); > + > + vnc_write_u8(vs, (use_rle ? 128 : 0) | size); > + palette_fill(palette, colors); > + > + for (i = 0; i < size; i++) { > + ZRLE_WRITE_PIXEL(vs, colors[i]); > + } > + } > + > + if (use_rle) { > + ZRLE_PIXEL *ptr = data; > + ZRLE_PIXEL *end = ptr + w * h; > + ZRLE_PIXEL *run_start; > + ZRLE_PIXEL pix; > + > + while (ptr < end) { > + int len; > + int index = 0; > + > + run_start = ptr; > + pix = *ptr++; > + > + while (*ptr == pix && ptr < end) { > + ptr++; > + } > + > + len = ptr - run_start; > + > + if (use_palette) > + index = palette_idx(palette, pix); > + > + if (len <= 2 && use_palette) { > + if (len == 2) { > + vnc_write_u8(vs, index); > + } > + vnc_write_u8(vs, index); > + continue; > + } > + if (use_palette) { > + vnc_write_u8(vs, index | 128); > + } else { > + ZRLE_WRITE_PIXEL(vs, pix); > + } > + > + len -= 1; > + > + while (len >= 255) { > + vnc_write_u8(vs, 255); > + len -= 255; > + } > + > + vnc_write_u8(vs, len); > + } > + } else if (use_palette) { /* no RLE */ > + int bppp; > + ZRLE_PIXEL *ptr = data; > + > + /* packed pixels */ > + > + assert (palette_size(palette) < 17); > + > + bppp = bits_per_packed_pixel[palette_size(palette)-1]; > + > + for (i = 0; i < h; i++) { > + uint8_t nbits = 0; > + uint8_t byte = 0; > + > + ZRLE_PIXEL *eol = ptr + w; > + > + while (ptr < eol) { > + ZRLE_PIXEL pix = *ptr++; > + uint8_t index = palette_idx(palette, pix); > + > + byte = (byte << bppp) | index; > + nbits += bppp; > + if (nbits >= 8) { > + vnc_write_u8(vs, byte); > + nbits = 0; > + } > + } > + if (nbits > 0) { > + byte <<= 8 - nbits; > + vnc_write_u8(vs, byte); > + } > + } > + } else { > + > + /* raw */ > + > +#if ZRLE_BPP != 8 > + if (zywrle_level > 0 && !(zywrle_level & 0x80)) { > + ZYWRLE_ANALYZE(data, data, w, h, w, zywrle_level, vs->zywrle.buf); > + ZRLE_ENCODE_TILE(vs, data, w, h, zywrle_level | 0x80); > + } > + else > +#endif > + { > +#ifdef ZRLE_COMPACT_PIXEL > + ZRLE_PIXEL *ptr; > + > + for (ptr = data; ptr < data + w * h; ptr++) { > + ZRLE_WRITE_PIXEL(vs, *ptr); > + } > +#else > + vnc_write(vs, data, w * h * (ZRLE_BPP / 8)); > +#endif > + } > + } > +} > + > +#undef ZRLE_PIXEL > +#undef ZRLE_WRITE_PIXEL > +#undef ZRLE_ENCODE > +#undef ZRLE_ENCODE_TILE > +#undef ZYWRLE_ENCODE_TILE > +#undef ZRLE_BPP_OUT > +#undef ZRLE_WRITE_SUFFIX > +#undef ZRLE_ENCODE_SUFFIX > diff --git a/ui/vnc-enc-zrle.c b/ui/vnc-enc-zrle.c > new file mode 100644 > index 0000000..4460890 > --- /dev/null > +++ b/ui/vnc-enc-zrle.c > @@ -0,0 +1,389 @@ > +/* > + * QEMU VNC display driver: Zlib Run-length Encoding (ZRLE) > + * > + * From libvncserver/libvncserver/zrle.c > + * Copyright (C) 2002 RealVNC Ltd. All Rights Reserved. > + * Copyright (C) 2003 Sun Microsystems, Inc. > + * > + * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> > + * > + * Permission is hereby granted, free of charge, to any person obtaining a copy > + * of this software and associated documentation files (the "Software"), to deal > + * in the Software without restriction, including without limitation the rights > + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell > + * copies of the Software, and to permit persons to whom the Software is > + * furnished to do so, subject to the following conditions: > + * > + * The above copyright notice and this permission notice shall be included in > + * all copies or substantial portions of the Software. > + * > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL > + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, > + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN > + * THE SOFTWARE. > + */ > + > +#include "vnc.h" > +#include "vnc-enc-zrle.h" > + > +static const int bits_per_packed_pixel[] = { > + 0, 1, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 > +}; > + > + > +static void vnc_zrle_start(VncState *vs) > +{ > + buffer_reset(&vs->zrle.zrle); > + > + // make the output buffer be the zlib buffer, so we can compress it later Please use C89 comments. > + vs->zrle.tmp = vs->output; > + vs->output = vs->zrle.zrle; > +} > + > +static void vnc_zrle_stop(VncState *vs) > +{ > + // switch back to normal output/zlib buffers > + vs->zrle.zrle = vs->output; > + vs->output = vs->zrle.tmp; > +} > + > +static void *zrle_convert_fb(VncState *vs, int x, int y, int w, int h, > + int bpp) > +{ > + Buffer tmp; > + > + buffer_reset(&vs->zrle.fb); > + buffer_reserve(&vs->zrle.fb, w * h * bpp + bpp); > + > + tmp = vs->output; > + vs->output = vs->zrle.fb; > + > + vnc_raw_send_framebuffer_update(vs, x, y, w, h); > + > + vs->zrle.fb = vs->output; > + vs->output = tmp; > + return vs->zrle.fb.buffer; > +} > + > +static int zrle_compress_data(VncState *vs, int level) > +{ > + z_streamp zstream = &vs->zrle.stream; > + > + buffer_reset(&vs->zrle.zlib); > + > + if (zstream->opaque != vs) { > + int err; > + > + zstream->zalloc = vnc_zlib_zalloc; > + zstream->zfree = vnc_zlib_zfree; > + > + err = deflateInit2(zstream, level, Z_DEFLATED, MAX_WBITS, > + MAX_MEM_LEVEL, Z_DEFAULT_STRATEGY); > + > + if (err != Z_OK) { > + fprintf(stderr, "VNC: error initializing zlib\n"); > + return -1; > + } > + > + zstream->opaque = vs; > + } > + > + /* reserve memory in output buffer */ > + buffer_reserve(&vs->zrle.zlib, vs->zrle.zrle.offset + 64); > + > + /* set pointers */ > + zstream->next_in = vs->zrle.zrle.buffer; > + zstream->avail_in = vs->zrle.zrle.offset; > + zstream->next_out = vs->zrle.zlib.buffer + vs->zrle.zlib.offset; > + zstream->avail_out = vs->zrle.zlib.capacity - vs->zrle.zlib.offset; > + zstream->data_type = Z_BINARY; > + > + /* start encoding */ > + if (deflate(zstream, Z_SYNC_FLUSH) != Z_OK) { > + fprintf(stderr, "VNC: error during zrle compression\n"); > + return -1; > + } > + > + vs->zrle.zlib.offset = vs->zrle.zlib.capacity - zstream->avail_out; > + return vs->zrle.zlib.offset; > +} > + > +/* Try to work out whether to use RLE and/or a palette. We do this by > + * estimating the number of bytes which will be generated and picking the > + * method which results in the fewest bytes. Of course this may not result > + * in the fewest bytes after compression... */ > +static void zrle_choose_palette_rle(VncState *vs, int w, int h, > + VncPalette *palette, int bpp_out, > + int runs, int single_pixels, > + int zywrle_level, > + bool *use_rle, bool *use_palette) > +{ > + size_t estimated_bytes; > + size_t plain_rle_bytes; > + > + *use_palette = *use_rle = false; > + > + estimated_bytes = w * h * (bpp_out / 8); /* start assuming raw */ > + > + if (bpp_out != 8) { > + if (zywrle_level > 0 && !(zywrle_level & 0x80)) > + estimated_bytes >>= zywrle_level; > + } > + > + plain_rle_bytes = ((bpp_out / 8) + 1) * (runs + single_pixels); > + > + if (plain_rle_bytes < estimated_bytes) { > + *use_rle = true; > + estimated_bytes = plain_rle_bytes; > + } > + > + if (palette_size(palette) < 128) { > + int palette_rle_bytes; > + > + palette_rle_bytes = (bpp_out / 8) * palette_size(palette); > + palette_rle_bytes += 2 * runs + single_pixels; > + > + if (palette_rle_bytes < estimated_bytes) { > + *use_rle = true; > + *use_palette = true; > + estimated_bytes = palette_rle_bytes; > + } > + > + if (palette_size(palette) < 17) { > + int packed_bytes; > + > + packed_bytes = (bpp_out / 8) * palette_size(palette); > + packed_bytes += w * h * > + bits_per_packed_pixel[palette_size(palette)-1] / 8; > + > + if (packed_bytes < estimated_bytes) { > + *use_rle = false; > + *use_palette = true; > + estimated_bytes = packed_bytes; > + } > + } > + } > +} > + > +static void zrle_write_u32(VncState *vs, uint32_t value) > +{ > + uint8_t buf[4]; > + > + buf[0] = ((uint8_t *)&value)[0]; > + buf[1] = ((uint8_t *)&value)[1]; > + buf[2] = ((uint8_t *)&value)[2]; > + buf[3] = ((uint8_t *)&value)[3]; These don't look endian safe, please use for example buf[0] = value & 0xff; etc. Also below. > + > + vnc_write(vs, buf, 4); > +} > + > +static void zrle_write_u24a(VncState *vs, uint32_t value) > +{ > + uint8_t buf[3]; > + > + buf[0] = ((uint8_t *)&value)[0]; > + buf[1] = ((uint8_t *)&value)[1]; > + buf[2] = ((uint8_t *)&value)[2]; > + > + vnc_write(vs, buf, 3); > +} > + > +static void zrle_write_u24b(VncState *vs, uint32_t value) > +{ > + uint8_t buf[3]; > + > + buf[0] = ((uint8_t *)&value)[1]; > + buf[1] = ((uint8_t *)&value)[2]; > + buf[2] = ((uint8_t *)&value)[3]; > + > + vnc_write(vs, buf, 3); > +} > + > +static void zrle_write_u16(VncState *vs, uint16_t value) > +{ > + uint8_t buf[2]; > + > + buf[0] = ((uint8_t *)&value)[0]; > + buf[1] = ((uint8_t *)&value)[1]; > + > + vnc_write(vs, buf, 2); > +} > + > +static void zrle_write_u8(VncState *vs, uint8_t value) > +{ > + vnc_write_u8(vs, value); > +} > + > +#define ENDIAN_LITTLE 0 > +#define ENDIAN_BIG 1 > +#define ENDIAN_NO 2 > + > +#define ZRLE_BPP 8 > +#define ZYWRLE_ENDIAN ENDIAN_NO > +#include "vnc-enc-zrle-template.c" > +#undef ZRLE_BPP > + > +#define ZRLE_BPP 15 > +#undef ZYWRLE_ENDIAN > +#define ZYWRLE_ENDIAN ENDIAN_LITTLE > +#include "vnc-enc-zrle-template.c" > + > +#undef ZYWRLE_ENDIAN > +#define ZYWRLE_ENDIAN ENDIAN_BIG > +#include "vnc-enc-zrle-template.c" > + > +#undef ZRLE_BPP > +#define ZRLE_BPP 16 > +#undef ZYWRLE_ENDIAN > +#define ZYWRLE_ENDIAN ENDIAN_LITTLE > +#include "vnc-enc-zrle-template.c" > + > +#undef ZYWRLE_ENDIAN > +#define ZYWRLE_ENDIAN ENDIAN_BIG > +#include "vnc-enc-zrle-template.c" > + > +#undef ZRLE_BPP > +#define ZRLE_BPP 32 > +#undef ZYWRLE_ENDIAN > +#define ZYWRLE_ENDIAN ENDIAN_LITTLE > +#include "vnc-enc-zrle-template.c" > + > +#undef ZYWRLE_ENDIAN > +#define ZYWRLE_ENDIAN ENDIAN_BIG > +#include "vnc-enc-zrle-template.c" > + > +#define ZRLE_COMPACT_PIXEL 24a > +#undef ZYWRLE_ENDIAN > +#define ZYWRLE_ENDIAN ENDIAN_LITTLE > +#include "vnc-enc-zrle-template.c" > + > +#undef ZYWRLE_ENDIAN > +#define ZYWRLE_ENDIAN ENDIAN_BIG > +#include "vnc-enc-zrle-template.c" > + > +#undef ZRLE_COMPACT_PIXEL > +#define ZRLE_COMPACT_PIXEL 24b > +#undef ZYWRLE_ENDIAN > +#define ZYWRLE_ENDIAN ENDIAN_LITTLE > +#include "vnc-enc-zrle-template.c" > + > +#undef ZYWRLE_ENDIAN > +#define ZYWRLE_ENDIAN ENDIAN_BIG > +#include "vnc-enc-zrle-template.c" > +#undef ZRLE_COMPACT_PIXEL > +#undef ZRLE_BPP > + > +static int zrle_send_framebuffer_update(VncState *vs, int x, int y, > + int w, int h) > +{ > + bool be = !!(vs->clientds.flags & QEMU_BIG_ENDIAN_FLAG); The indentation is too small. > + size_t bytes; > + int zywrle_level; > + > + if (vs->zrle.type == VNC_ENCODING_ZYWRLE) { > + if (!vs->vd->lossy || vs->tight.quality < 0 || vs->tight.quality == 9) { > + zywrle_level = 0; > + vs->zrle.type = VNC_ENCODING_ZRLE; > + } else if (vs->tight.quality < 3) { > + zywrle_level = 3; > + } else if (vs->tight.quality < 6) { > + zywrle_level = 2; > + } else { > + zywrle_level = 1; > + } > + } else { > + zywrle_level = 0; > + } > + > + vnc_zrle_start(vs); > + > + switch(vs->clientds.pf.bytes_per_pixel) { > + case 1: > + zrle_encode_8ne(vs, x, y, w, h, zywrle_level); > + break; > + > + case 2: > + if (vs->clientds.pf.gmax > 0x1F) { > + if (be) { > + zrle_encode_16be(vs, x, y, w, h, zywrle_level); > + } else { > + zrle_encode_16le(vs, x, y, w, h, zywrle_level); > + } > + } else { > + if (be) { > + zrle_encode_15be(vs, x, y, w, h, zywrle_level); > + } else { > + zrle_encode_15le(vs, x, y, w, h, zywrle_level); > + } > + } > + break; > + > + case 4: > + { > + bool fits_in_ls3bytes; > + bool fits_in_ms3bytes; > + > + fits_in_ls3bytes = > + ((vs->clientds.pf.rmax << vs->clientds.pf.rshift) < (1 << 24) && > + (vs->clientds.pf.gmax << vs->clientds.pf.gshift) < (1 << 24) && > + (vs->clientds.pf.bmax << vs->clientds.pf.bshift) < (1 << 24)); > + > + fits_in_ms3bytes = (vs->clientds.pf.rshift > 7 && > + vs->clientds.pf.gshift > 7 && > + vs->clientds.pf.bshift > 7); > + > + if ((fits_in_ls3bytes && !be) || (fits_in_ms3bytes && be)) { > + if (be) { > + zrle_encode_24abe(vs, x, y, w, h, zywrle_level); > + } else { > + zrle_encode_24ale(vs, x, y, w, h, zywrle_level); > + } > + } else if ((fits_in_ls3bytes && be) || (fits_in_ms3bytes && !be)) { > + if (be) { > + zrle_encode_24bbe(vs, x, y, w, h, zywrle_level); > + } else { > + zrle_encode_24ble(vs, x, y, w, h, zywrle_level); > + } > + } else { > + if (be) { > + zrle_encode_32be(vs, x, y, w, h, zywrle_level); > + } else { > + zrle_encode_32le(vs, x, y, w, h, zywrle_level); > + } > + } > + } > + break; > + } > + > + vnc_zrle_stop(vs); > + bytes = zrle_compress_data(vs, Z_DEFAULT_COMPRESSION); > + vnc_framebuffer_update(vs, x, y, w, h, vs->zrle.type); > + vnc_write_u32(vs, bytes); > + vnc_write(vs, vs->zrle.zlib.buffer, vs->zrle.zlib.offset); > + return 1; > +} > + > +int vnc_zrle_send_framebuffer_update(VncState *vs, int x, int y, int w, int h) > +{ > + vs->zrle.type = VNC_ENCODING_ZRLE; > + return zrle_send_framebuffer_update(vs, x, y, w, h); > +} > + > +int vnc_zywrle_send_framebuffer_update(VncState *vs, int x, int y, int w, int h) > +{ > + vs->zrle.type = VNC_ENCODING_ZYWRLE; > + return zrle_send_framebuffer_update(vs, x, y, w, h); > +} > + > +void vnc_zrle_clear(VncState *vs) > +{ > + if (vs->zrle.stream.opaque) { > + deflateEnd(&vs->zrle.stream); > + } > + buffer_free(&vs->zrle.zrle); > + buffer_free(&vs->zrle.fb); > + buffer_free(&vs->zrle.zlib); > +} > diff --git a/ui/vnc-enc-zrle.h b/ui/vnc-enc-zrle.h > new file mode 100644 > index 0000000..6b18213 > --- /dev/null > +++ b/ui/vnc-enc-zrle.h > @@ -0,0 +1,40 @@ > +/* > + * QEMU VNC display driver: Zlib Run-length Encoding (ZRLE) > + * > + * From libvncserver/libvncserver/zrle.c > + * Copyright (C) 2002 RealVNC Ltd. All Rights Reserved. > + * Copyright (C) 2003 Sun Microsystems, Inc. > + * > + * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> > + * > + * Permission is hereby granted, free of charge, to any person obtaining a copy > + * of this software and associated documentation files (the "Software"), to deal > + * in the Software without restriction, including without limitation the rights > + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell > + * copies of the Software, and to permit persons to whom the Software is > + * furnished to do so, subject to the following conditions: > + * > + * The above copyright notice and this permission notice shall be included in > + * all copies or substantial portions of the Software. > + * > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL > + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, > + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN > + * THE SOFTWARE. > + */ > + > +#ifndef VNC_ENCODING_ZRLE_H > +#define VNC_ENCODING_ZRLE_H > + > +/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - > + * ZRLE - encoding combining Zlib compression, tiling, palettisation and > + * run-length encoding. > + */ > + > +#define VNC_ZRLE_TILE_WIDTH 64 > +#define VNC_ZRLE_TILE_HEIGHT 64 > + > +#endif > diff --git a/ui/vnc-enc-zywrle-template.c b/ui/vnc-enc-zywrle-template.c > new file mode 100644 > index 0000000..4cde6e4 > --- /dev/null > +++ b/ui/vnc-enc-zywrle-template.c > @@ -0,0 +1,170 @@ > + > +/******************************************************************** > + * * > + * THIS FILE IS PART OF THE 'ZYWRLE' VNC CODEC SOURCE CODE. * > + * * > + * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * > + * GOVERNED BY A FOLLOWING BSD-STYLE SOURCE LICENSE. * > + * PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * > + * * > + * THE 'ZYWRLE' VNC CODEC SOURCE CODE IS (C) COPYRIGHT 2006 * > + * BY Hitachi Systems & Services, Ltd. * > + * (Noriaki Yamazaki, Research & Developement Center) * > + * * > + * * > + ******************************************************************** > +Redistribution and use in source and binary forms, with or without > +modification, are permitted provided that the following conditions > +are met: > + > +- Redistributions of source code must retain the above copyright > +notice, this list of conditions and the following disclaimer. > + > +- Redistributions in binary form must reproduce the above copyright > +notice, this list of conditions and the following disclaimer in the > +documentation and/or other materials provided with the distribution. > + > +- Neither the name of the Hitachi Systems & Services, Ltd. nor > +the names of its contributors may be used to endorse or promote > +products derived from this software without specific prior written > +permission. > + > +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS > +``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT > +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR > +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION > +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, > +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT > +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, > +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY > +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT > +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE > +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. > + ********************************************************************/ > + > +/* Change Log: > + V0.02 : 2008/02/04 : Fix mis encode/decode when width != scanline > + (Thanks Johannes Schindelin, author of LibVNC > + Server/Client) > + V0.01 : 2007/02/06 : Initial release > +*/ > + > +/* > +[References] > + PLHarr: > + Senecal, J. G., P. Lindstrom, M. A. Duchaineau, and K. I. Joy, > + "An Improved N-Bit to N-Bit Reversible Haar-Like Transform," > + Pacific Graphics 2004, October 2004, pp. 371-380. > + EZW: > + Shapiro, JM: Embedded Image Coding Using Zerotrees of Wavelet Coefficients, > + IEEE Trans. Signal. Process., Vol.41, pp.3445-3462 (1993). > +*/ > + > + > +/* Template Macro stuffs. */ > +#undef ZYWRLE_ANALYZE > +#undef ZYWRLE_SYNTHESIZE > + > +#define ZYWRLE_SUFFIX ZRLE_CONCAT2(ZRLE_BPP,ZRLE_ENDIAN_SUFFIX) > + > +#define ZYWRLE_ANALYZE ZRLE_CONCAT2(zywrle_analyze_, ZYWRLE_SUFFIX) > +#define ZYWRLE_SYNTHESIZE ZRLE_CONCAT2(zywrle_synthesize_,ZYWRLE_SUFFIX) > + > +#define ZYWRLE_RGBYUV ZRLE_CONCAT2(zywrle_rgbyuv_, ZYWRLE_SUFFIX) > +#define ZYWRLE_YUVRGB ZRLE_CONCAT2(zywrle_yuvrgb_, ZYWRLE_SUFFIX) > +#define ZYWRLE_YMASK ZRLE_CONCAT2(ZYWRLE_YMASK, ZRLE_BPP) > +#define ZYWRLE_UVMASK ZRLE_CONCAT2(ZYWRLE_UVMASK, ZRLE_BPP) > +#define ZYWRLE_LOAD_PIXEL ZRLE_CONCAT2(ZYWRLE_LOAD_PIXEL, ZRLE_BPP) > +#define ZYWRLE_SAVE_PIXEL ZRLE_CONCAT2(ZYWRLE_SAVE_PIXEL, ZRLE_BPP) > + > +/* Packing/Unpacking pixel stuffs. > + Endian conversion stuffs. */ > +#undef S_0 > +#undef S_1 > +#undef L_0 > +#undef L_1 > +#undef L_2 > + > +#if ZYWRLE_ENDIAN == ENDIAN_BIG > +# define S_0 1 > +# define S_1 0 > +# define L_0 3 > +# define L_1 2 > +# define L_2 1 > +#else > +# define S_0 0 > +# define S_1 1 > +# define L_0 0 > +# define L_1 1 > +# define L_2 2 > +#endif > + > +#define ZYWRLE_QUANTIZE > +#include "vnc-enc-zywrle.h" > + > +#ifndef ZRLE_COMPACT_PIXEL > +static inline void ZYWRLE_RGBYUV(int *buf, ZRLE_PIXEL *data, > + int width, int height, int scanline) > +{ > + int r, g, b; > + int y, u, v; > + int *line; > + int *end; > + > + end = buf + height * width; > + while (buf < end) { > + line = buf + width; > + while (buf < line) { > + ZYWRLE_LOAD_PIXEL(data, r, g, b); > + ZYWRLE_RGBYUV_(r, g, b, y, u, v, ZYWRLE_YMASK, ZYWRLE_UVMASK); > + ZYWRLE_SAVE_COEFF(buf, v, y, u); > + buf++; > + data++; > + } > + data += scanline - width; > + } > +} > + > +static ZRLE_PIXEL *ZYWRLE_ANALYZE(ZRLE_PIXEL *dst, ZRLE_PIXEL *src, > + int w, int h, int scanline, int level, > + int *buf) { > + int l; > + int uw = w; > + int uh = h; > + int *top; > + int *end; > + int *line; > + ZRLE_PIXEL *p; > + int r, g, b; > + int s; > + int *ph; > + > + zywrle_calc_size(&w, &h, level); > + > + if (w == 0 || h == 0) { > + return NULL; > + } > + uw -= w; > + uh -= h; > + > + p = dst; > + ZYWRLE_LOAD_UNALIGN(src,*(ZRLE_PIXEL*)top = *p;); > + ZYWRLE_RGBYUV(buf, src, w, h, scanline); > + wavelet(buf, w, h, level); > + for (l = 0; l < level; l++) { > + ZYWRLE_PACK_COEFF(buf, dst, 3, w, h, scanline, l); > + ZYWRLE_PACK_COEFF(buf, dst, 2, w, h, scanline, l); > + ZYWRLE_PACK_COEFF(buf, dst, 1, w, h, scanline, l); > + if (l == level - 1) { > + ZYWRLE_PACK_COEFF(buf, dst, 0, w, h, scanline, l); > + } > + } > + ZYWRLE_SAVE_UNALIGN(dst,*dst = *(ZRLE_PIXEL*)top;); > + return dst; > +} > +#endif /* ZRLE_COMPACT_PIXEL */ > + > +#undef ZYWRLE_RGBYUV > +#undef ZYWRLE_YUVRGB > +#undef ZYWRLE_LOAD_PIXEL > +#undef ZYWRLE_SAVE_PIXEL > diff --git a/ui/vnc-enc-zywrle.h b/ui/vnc-enc-zywrle.h > new file mode 100644 > index 0000000..722bd7d > --- /dev/null > +++ b/ui/vnc-enc-zywrle.h > @@ -0,0 +1,652 @@ > +/******************************************************************** > + * * > + * THIS FILE IS PART OF THE 'ZYWRLE' VNC CODEC SOURCE CODE. * > + * * > + * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * > + * GOVERNED BY A FOLLOWING BSD-STYLE SOURCE LICENSE. * > + * PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * > + * * > + * THE 'ZYWRLE' VNC CODEC SOURCE CODE IS (C) COPYRIGHT 2006 * > + * BY Hitachi Systems & Services, Ltd. * > + * (Noriaki Yamazaki, Research & Developement Center) * > + * * > + * * > + ******************************************************************** > +Redistribution and use in source and binary forms, with or without > +modification, are permitted provided that the following conditions > +are met: > + > +- Redistributions of source code must retain the above copyright > +notice, this list of conditions and the following disclaimer. > + > +- Redistributions in binary form must reproduce the above copyright > +notice, this list of conditions and the following disclaimer in the > +documentation and/or other materials provided with the distribution. > + > +- Neither the name of the Hitachi Systems & Services, Ltd. nor > +the names of its contributors may be used to endorse or promote > +products derived from this software without specific prior written > +permission. > + > +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS > +``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT > +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR > +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION > +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, > +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT > +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, > +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY > +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT > +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE > +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. > + ********************************************************************/ > + > +#ifndef VNC_ENCODING_ZYWRLE_H > +#define VNC_ENCODING_ZYWRLE_H > + > +/* Tables for Coefficients filtering. */ > +#ifndef ZYWRLE_QUANTIZE > +/* Type A:lower bit omitting of EZW style. */ > +const static unsigned int zywrle_param[3][3]={ This should be 'static const'. > + {0x0000F000,0x00000000,0x00000000}, There should be a space after commas. > + {0x0000C000,0x00F0F0F0,0x00000000}, > + {0x0000C000,0x00C0C0C0,0x00F0F0F0}, > +/* {0x0000FF00,0x00000000,0x00000000}, > + {0x0000FF00,0x00FFFFFF,0x00000000}, > + {0x0000FF00,0x00FFFFFF,0x00FFFFFF}, */ > +}; > +#else > +/* Type B:Non liner quantization filter. */ > +static const signed char zywrle_conv[4][256]={ I'd use int8_t here. > +{ /* bi=5, bo=5 r=0.0:PSNR=24.849 */ > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > +}, > +{ /* bi=5, bo=5 r=2.0:PSNR=74.031 */ > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 32, > + 32, 32, 32, 32, 32, 32, 32, 32, > + 32, 32, 32, 32, 32, 32, 32, 32, > + 48, 48, 48, 48, 48, 48, 48, 48, > + 48, 48, 48, 56, 56, 56, 56, 56, > + 56, 56, 56, 56, 64, 64, 64, 64, > + 64, 64, 64, 64, 72, 72, 72, 72, > + 72, 72, 72, 72, 80, 80, 80, 80, > + 80, 80, 88, 88, 88, 88, 88, 88, > + 88, 88, 88, 88, 88, 88, 96, 96, > + 96, 96, 96, 104, 104, 104, 104, 104, > + 104, 104, 104, 104, 104, 112, 112, 112, > + 112, 112, 112, 112, 112, 112, 120, 120, > + 120, 120, 120, 120, 120, 120, 120, 120, > + 0, -120, -120, -120, -120, -120, -120, -120, > + -120, -120, -120, -112, -112, -112, -112, -112, > + -112, -112, -112, -112, -104, -104, -104, -104, > + -104, -104, -104, -104, -104, -104, -96, -96, > + -96, -96, -96, -88, -88, -88, -88, -88, > + -88, -88, -88, -88, -88, -88, -88, -80, > + -80, -80, -80, -80, -80, -72, -72, -72, > + -72, -72, -72, -72, -72, -64, -64, -64, > + -64, -64, -64, -64, -64, -56, -56, -56, > + -56, -56, -56, -56, -56, -56, -48, -48, > + -48, -48, -48, -48, -48, -48, -48, -48, > + -48, -32, -32, -32, -32, -32, -32, -32, > + -32, -32, -32, -32, -32, -32, -32, -32, > + -32, -32, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > +}, > +{ /* bi=5, bo=4 r=2.0:PSNR=64.441 */ > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 48, 48, 48, 48, 48, 48, 48, 48, > + 48, 48, 48, 48, 48, 48, 48, 48, > + 48, 48, 48, 48, 48, 48, 48, 48, > + 64, 64, 64, 64, 64, 64, 64, 64, > + 64, 64, 64, 64, 64, 64, 64, 64, > + 80, 80, 80, 80, 80, 80, 80, 80, > + 80, 80, 80, 80, 80, 88, 88, 88, > + 88, 88, 88, 88, 88, 88, 88, 88, > + 104, 104, 104, 104, 104, 104, 104, 104, > + 104, 104, 104, 112, 112, 112, 112, 112, > + 112, 112, 112, 112, 120, 120, 120, 120, > + 120, 120, 120, 120, 120, 120, 120, 120, > + 0, -120, -120, -120, -120, -120, -120, -120, > + -120, -120, -120, -120, -120, -112, -112, -112, > + -112, -112, -112, -112, -112, -112, -104, -104, > + -104, -104, -104, -104, -104, -104, -104, -104, > + -104, -88, -88, -88, -88, -88, -88, -88, > + -88, -88, -88, -88, -80, -80, -80, -80, > + -80, -80, -80, -80, -80, -80, -80, -80, > + -80, -64, -64, -64, -64, -64, -64, -64, > + -64, -64, -64, -64, -64, -64, -64, -64, > + -64, -48, -48, -48, -48, -48, -48, -48, > + -48, -48, -48, -48, -48, -48, -48, -48, > + -48, -48, -48, -48, -48, -48, -48, -48, > + -48, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > +}, > +{ /* bi=5, bo=2 r=2.0:PSNR=43.175 */ > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 88, 88, 88, 88, 88, 88, 88, 88, > + 88, 88, 88, 88, 88, 88, 88, 88, > + 88, 88, 88, 88, 88, 88, 88, 88, > + 88, 88, 88, 88, 88, 88, 88, 88, > + 88, 88, 88, 88, 88, 88, 88, 88, > + 88, 88, 88, 88, 88, 88, 88, 88, > + 88, 88, 88, 88, 88, 88, 88, 88, > + 88, 88, 88, 88, 88, 88, 88, 88, > + 0, -88, -88, -88, -88, -88, -88, -88, > + -88, -88, -88, -88, -88, -88, -88, -88, > + -88, -88, -88, -88, -88, -88, -88, -88, > + -88, -88, -88, -88, -88, -88, -88, -88, > + -88, -88, -88, -88, -88, -88, -88, -88, > + -88, -88, -88, -88, -88, -88, -88, -88, > + -88, -88, -88, -88, -88, -88, -88, -88, > + -88, -88, -88, -88, -88, -88, -88, -88, > + -88, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > + 0, 0, 0, 0, 0, 0, 0, 0, > +} > +}; > + > +static const signed char *zywrle_param[3][3][3]={ > + {{zywrle_conv[0], zywrle_conv[2], zywrle_conv[0]}, > + {zywrle_conv[0], zywrle_conv[0], zywrle_conv[0]}, > + {zywrle_conv[0], zywrle_conv[0], zywrle_conv[0]}}, > + {{zywrle_conv[0], zywrle_conv[3], zywrle_conv[0]}, > + {zywrle_conv[1], zywrle_conv[1], zywrle_conv[1]}, > + {zywrle_conv[0], zywrle_conv[0], zywrle_conv[0]}}, > + {{zywrle_conv[0], zywrle_conv[3], zywrle_conv[0]}, > + {zywrle_conv[2], zywrle_conv[2], zywrle_conv[2]}, > + {zywrle_conv[1], zywrle_conv[1], zywrle_conv[1]}}, > +}; > +#endif > + > +/* Load/Save pixel stuffs. */ > +#define ZYWRLE_YMASK15 0xFFFFFFF8 > +#define ZYWRLE_UVMASK15 0xFFFFFFF8 > +#define ZYWRLE_LOAD_PIXEL15(src, r, g, b) \ > + do { \ > + r = (((uint8_t*)src)[S_1]<< 1)& 0xF8; \ > + g = (((uint8_t*)src)[S_1]<< 6) | (((uint8_t*)src)[S_0]>> 2); \ > + g &= 0xF8; \ > + b = (((uint8_t*)src)[S_0]<< 3)& 0xF8; \ > + } while (0) > + > +#define ZYWRLE_SAVE_PIXEL15(dst, r, g, b) \ > + do { \ > + r &= 0xF8; \ > + g &= 0xF8; \ > + b &= 0xF8; \ > + ((uint8_t*)dst)[S_1] = (uint8_t)((r >> 1)|(g >> 6)); \ > + ((uint8_t*)dst)[S_0] = (uint8_t)(((b >> 3)|(g << 2))& 0xFF); \ > + } while (0) > + > +#define ZYWRLE_YMASK16 0xFFFFFFFC > +#define ZYWRLE_UVMASK16 0xFFFFFFF8 > +#define ZYWRLE_LOAD_PIXEL16(src, r, g, b) \ > + do { \ > + r = ((uint8_t*)src)[S_1] & 0xF8; \ > + g = (((uint8_t*)src)[S_1]<< 5) | (((uint8_t*)src)[S_0] >> 3); \ > + g &= 0xFC; \ > + b = (((uint8_t*)src)[S_0]<< 3) & 0xF8; \ > + } while (0) > + > +#define ZYWRLE_SAVE_PIXEL16(dst, r, g,b) \ > + do { \ > + r &= 0xF8; \ > + g &= 0xFC; \ > + b &= 0xF8; \ > + ((uint8_t*)dst)[S_1] = (uint8_t)(r | (g >> 5)); \ > + ((uint8_t*)dst)[S_0] = (uint8_t)(((b >> 3)|(g << 3)) & 0xFF); \ > + } while (0) > + > +#define ZYWRLE_YMASK32 0xFFFFFFFF > +#define ZYWRLE_UVMASK32 0xFFFFFFFF > +#define ZYWRLE_LOAD_PIXEL32(src, r, g, b) \ > + do { \ > + r = ((uint8_t*)src)[L_2]; \ > + g = ((uint8_t*)src)[L_1]; \ > + b = ((uint8_t*)src)[L_0]; \ > + } while (0) > +#define ZYWRLE_SAVE_PIXEL32(dst, r, g, b) \ > + do { \ > + ((uint8_t*)dst)[L_2] = (uint8_t)r; \ > + ((uint8_t*)dst)[L_1] = (uint8_t)g; \ > + ((uint8_t*)dst)[L_0] = (uint8_t)b; \ > + } while (0) > + > +static inline void harr(int8_t *px0, int8_t *px1) > +{ > + /* Piecewise-Linear Harr(PLHarr) */ > + int x0 = (int)*px0, x1 = (int)*px1; > + int orgx0 = x0, orgx1 = x1; > + > + if ((x0 ^ x1) & 0x80) { > + /* differ sign */ > + x1 += x0; > + if (((x1 ^ orgx1) & 0x80) == 0) { > + /* |x1| > |x0| */ > + x0 -= x1; /* H = -B */ > + } > + } else { > + /* same sign */ > + x0 -= x1; > + if (((x0 ^ orgx0) & 0x80) == 0) { > + /* |x0| > |x1| */ > + x1 += x0; /* L = A */ > + } > + } > + *px0 = (int8_t)x1; > + *px1 = (int8_t)x0; > +} > + > +/* > + 1D-Wavelet transform. > + > + In coefficients array, the famous 'pyramid' decomposition is well used. > + > + 1D Model: > + |L0L0L0L0|L0L0L0L0|H0H0H0H0|H0H0H0H0| : level 0 > + |L1L1L1L1|H1H1H1H1|H0H0H0H0|H0H0H0H0| : level 1 > + > + But this method needs line buffer because H/L is different position from X0/X1. > + So, I used 'interleave' decomposition instead of it. > + > + 1D Model: > + |L0H0L0H0|L0H0L0H0|L0H0L0H0|L0H0L0H0| : level 0 > + |L1H0H1H0|L1H0H1H0|L1H0H1H0|L1H0H1H0| : level 1 > + > + In this method, H/L and X0/X1 is always same position. > + This lead us to more speed and less memory. > + Of cause, the result of both method is quite same > + because it's only difference that coefficient position. > +*/ > +static inline void wavelet_level(int *data, int size, int l, int skip_pixel) > +{ > + int s, ofs; > + int8_t *px0; > + int8_t *end; > + > + px0 = (int8_t*)data; > + s = (8 << l) * skip_pixel; > + end = px0 + (size >> (l + 1)) * s; > + s -= 2; > + ofs = (4 << l) * skip_pixel; > + > + while (px0 < end) { > + harr(px0, px0 + ofs); > + px0++; > + harr(px0, px0 + ofs); > + px0++; > + harr(px0, px0 + ofs); > + px0 += s; > + } > +} > + > +#ifndef ZYWRLE_QUANTIZE > +/* Type A:lower bit omitting of EZW style. */ > +static inline void filter_wavelet_square(int *buf, int width, int height, > + int level, int l) > +{ > + int r, s; > + int x, y; > + int *h; > + const unsigned int *m; > + > + m = &(zywrle_param[level - 1][l]); > + s = 2 << l; > + > + for (r = 1; r < 4; r++) { > + h = buf; > + if (r & 0x01) > + h += s >> 1; Missing braces, also below. ^ permalink raw reply [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 09/15] vnc: fix uint8_t comparisons with negative values 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (7 preceding siblings ...) 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 08/15] vnc: Add ZRLE and ZYWRLE encodings Corentin Chary @ 2010-11-11 16:56 ` Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 10/15] vnc: fix lossy rect refreshing Corentin Chary ` (6 subsequent siblings) 15 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:56 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- ui/vnc-enc-tight.c | 4 ++-- ui/vnc-enc-zrle.c | 3 ++- 2 files changed, 4 insertions(+), 3 deletions(-) diff --git a/ui/vnc-enc-tight.c b/ui/vnc-enc-tight.c index ad9a9a8..81024d5 100644 --- a/ui/vnc-enc-tight.c +++ b/ui/vnc-enc-tight.c @@ -1546,7 +1546,7 @@ static int send_sub_rect(VncState *vs, int x, int y, int w, int h) vnc_tight_stop(vs); #ifdef CONFIG_VNC_JPEG - if (vs->tight.quality != -1) { + if (vs->tight.quality != (uint8_t)-1) { double freq = vnc_update_freq(vs, x, y, w, h); if (freq < tight_jpeg_conf[vs->tight.quality].jpeg_freq_min) { @@ -1711,7 +1711,7 @@ static int tight_send_framebuffer_update(VncState *vs, int x, int y, vs->tight.pixel24 = false; } - if (vs->tight.quality != -1) { + if (vs->tight.quality != (uint8_t)-1) { double freq = vnc_update_freq(vs, x, y, w, h); if (freq > tight_jpeg_conf[vs->tight.quality].jpeg_freq_threshold) { diff --git a/ui/vnc-enc-zrle.c b/ui/vnc-enc-zrle.c index 4460890..b5a245a 100644 --- a/ui/vnc-enc-zrle.c +++ b/ui/vnc-enc-zrle.c @@ -284,7 +284,8 @@ static int zrle_send_framebuffer_update(VncState *vs, int x, int y, int zywrle_level; if (vs->zrle.type == VNC_ENCODING_ZYWRLE) { - if (!vs->vd->lossy || vs->tight.quality < 0 || vs->tight.quality == 9) { + if (!vs->vd->lossy || vs->tight.quality == (uint8_t)-1 + || vs->tight.quality == 9) { zywrle_level = 0; vs->zrle.type = VNC_ENCODING_ZRLE; } else if (vs->tight.quality < 3) { -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 10/15] vnc: fix lossy rect refreshing 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (8 preceding siblings ...) 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 09/15] vnc: fix uint8_t comparisons with negative values Corentin Chary @ 2010-11-11 16:56 ` Corentin Chary 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 11/15] bitmap: add a generic bitmap and bitops library Corentin Chary ` (5 subsequent siblings) 15 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:56 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara The for loop in send_lossy_rect was totally wrong, and we can't call vnc_set_bits() because it does not really do what it should. Use vnc_set_bit() directly instead. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- ui/vnc.c | 12 ++++++++---- 1 files changed, 8 insertions(+), 4 deletions(-) diff --git a/ui/vnc.c b/ui/vnc.c index 227efb6..fc2be61 100644 --- a/ui/vnc.c +++ b/ui/vnc.c @@ -2296,8 +2296,8 @@ void vnc_sent_lossy_rect(VncState *vs, int x, int y, int w, int h) x /= VNC_STAT_RECT; y /= VNC_STAT_RECT; - for (j = y; j <= y + h; j++) { - for (i = x; i <= x + w; i++) { + for (j = y; j <= h; j++) { + for (i = x; i <= w; i++) { vs->lossy_rect[j][i] = 1; } } @@ -2314,7 +2314,7 @@ static int vnc_refresh_lossy_rect(VncDisplay *vd, int x, int y) x = x / VNC_STAT_RECT * VNC_STAT_RECT; QTAILQ_FOREACH(vs, &vd->clients, next) { - int j ; + int j, i; /* kernel send buffers are full -> refresh later */ if (vs->output.offset) @@ -2322,12 +2322,16 @@ static int vnc_refresh_lossy_rect(VncDisplay *vd, int x, int y) if (!vs->lossy_rect[sty][stx]) continue ; + vs->lossy_rect[sty][stx] = 0; for (j = 0; j < VNC_STAT_RECT; ++j) { - vnc_set_bits(vs->dirty[y + j], x / 16, VNC_STAT_RECT / 16); + for (i = x / 16; i < VNC_STAT_RECT / 16 + x / 16; ++i) { + vnc_set_bit(vs->dirty[y + j], i); + } } has_dirty++; } + return has_dirty; } -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 11/15] bitmap: add a generic bitmap and bitops library 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (9 preceding siblings ...) 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 10/15] vnc: fix lossy rect refreshing Corentin Chary @ 2010-11-11 16:57 ` Corentin Chary 2010-11-11 19:07 ` Blue Swirl 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 12/15] vnc: use the new generic bitmap functions Corentin Chary ` (4 subsequent siblings) 15 siblings, 1 reply; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:57 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara Add most used bitmap and bitops functions into bitmap.c and bitops.c. Theses functions are mostly copied from Linux kernel source. Some of these functions are already redefined in the VNC server. Some of them could be used for some block stuff. The yet yo be submitted NUMA work also need bitmaps. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- Makefile.objs | 1 + bitmap.c | 255 +++++++++++++++++++++++++++++++++++++++++++++++++++++ bitmap.h | 222 ++++++++++++++++++++++++++++++++++++++++++++++ bitops.c | 142 ++++++++++++++++++++++++++++++ bitops.h | 272 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ osdep.h | 4 + 6 files changed, 896 insertions(+), 0 deletions(-) create mode 100644 bitmap.c create mode 100644 bitmap.h create mode 100644 bitops.c create mode 100644 bitops.h diff --git a/Makefile.objs b/Makefile.objs index 3da959c..e9ee4a8 100644 --- a/Makefile.objs +++ b/Makefile.objs @@ -92,6 +92,7 @@ common-obj-y += msmouse.o ps2.o common-obj-y += qdev.o qdev-properties.o common-obj-y += block-migration.o common-obj-y += pflib.o +common-obj-y += bitmap.c bitops.c common-obj-$(CONFIG_BRLAPI) += baum.o common-obj-$(CONFIG_POSIX) += migration-exec.o migration-unix.o migration-fd.o diff --git a/bitmap.c b/bitmap.c new file mode 100644 index 0000000..eaafbea --- /dev/null +++ b/bitmap.c @@ -0,0 +1,255 @@ +/* + * Bitmap Module + * + * Stolen from linux/src/lib/bitmap.c + * + * Copyright (C) 2010 Corentin Chary + * + * This source code is licensed under the GNU General Public License, + * Version 2. + */ + +#include "bitops.h" +#include "bitmap.h" + +/* + * bitmaps provide an array of bits, implemented using an an + * array of unsigned longs. The number of valid bits in a + * given bitmap does _not_ need to be an exact multiple of + * BITS_PER_LONG. + * + * The possible unused bits in the last, partially used word + * of a bitmap are 'don't care'. The implementation makes + * no particular effort to keep them zero. It ensures that + * their value will not affect the results of any operation. + * The bitmap operations that return Boolean (bitmap_empty, + * for example) or scalar (bitmap_weight, for example) results + * carefully filter out these unused bits from impacting their + * results. + * + * These operations actually hold to a slightly stronger rule: + * if you don't input any bitmaps to these ops that have some + * unused bits set, then they won't output any set unused bits + * in output bitmaps. + * + * The byte ordering of bitmaps is more natural on little + * endian architectures. + */ + +int __bitmap_empty(const unsigned long *bitmap, int bits) +{ + int k, lim = bits/BITS_PER_LONG; + + for (k = 0; k < lim; ++k) { + if (bitmap[k]) { + return 0; + } + } + if (bits % BITS_PER_LONG) { + if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) { + return 0; + } + } + + return 1; +} + +int __bitmap_full(const unsigned long *bitmap, int bits) +{ + int k, lim = bits/BITS_PER_LONG; + + for (k = 0; k < lim; ++k) { + if (~bitmap[k]) { + return 0; + } + } + + if (bits % BITS_PER_LONG) { + if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) { + return 0; + } + } + + return 1; +} + +int __bitmap_equal(const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits) +{ + int k, lim = bits/BITS_PER_LONG; + + for (k = 0; k < lim; ++k) { + if (bitmap1[k] != bitmap2[k]) { + return 0; + } + } + + if (bits % BITS_PER_LONG) { + if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) { + return 0; + } + } + + return 1; +} + +void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits) +{ + int k, lim = bits/BITS_PER_LONG; + + for (k = 0; k < lim; ++k) { + dst[k] = ~src[k]; + } + + if (bits % BITS_PER_LONG) { + dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits); + } +} + +int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits) +{ + int k; + int nr = BITS_TO_LONGS(bits); + unsigned long result = 0; + + for (k = 0; k < nr; k++) { + result |= (dst[k] = bitmap1[k] & bitmap2[k]); + } + return result != 0; +} + +void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits) +{ + int k; + int nr = BITS_TO_LONGS(bits); + + for (k = 0; k < nr; k++) { + dst[k] = bitmap1[k] | bitmap2[k]; + } +} + +void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits) +{ + int k; + int nr = BITS_TO_LONGS(bits); + + for (k = 0; k < nr; k++) { + dst[k] = bitmap1[k] ^ bitmap2[k]; + } +} + +int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits) +{ + int k; + int nr = BITS_TO_LONGS(bits); + unsigned long result = 0; + + for (k = 0; k < nr; k++) { + result |= (dst[k] = bitmap1[k] & ~bitmap2[k]); + } + return result != 0; +} + +#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) + +void bitmap_set(unsigned long *map, int start, int nr) +{ + unsigned long *p = map + BIT_WORD(start); + const int size = start + nr; + int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); + + while (nr - bits_to_set >= 0) { + *p |= mask_to_set; + nr -= bits_to_set; + bits_to_set = BITS_PER_LONG; + mask_to_set = ~0UL; + p++; + } + if (nr) { + mask_to_set &= BITMAP_LAST_WORD_MASK(size); + *p |= mask_to_set; + } +} + +void bitmap_clear(unsigned long *map, int start, int nr) +{ + unsigned long *p = map + BIT_WORD(start); + const int size = start + nr; + int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); + + while (nr - bits_to_clear >= 0) { + *p &= ~mask_to_clear; + nr -= bits_to_clear; + bits_to_clear = BITS_PER_LONG; + mask_to_clear = ~0UL; + p++; + } + if (nr) { + mask_to_clear &= BITMAP_LAST_WORD_MASK(size); + *p &= ~mask_to_clear; + } +} + +#define __ALIGN_MASK(x,mask) (((x)+(mask))&~(mask)) + +/** + * bitmap_find_next_zero_area - find a contiguous aligned zero area + * @map: The address to base the search on + * @size: The bitmap size in bits + * @start: The bitnumber to start searching at + * @nr: The number of zeroed bits we're looking for + * @align_mask: Alignment mask for zero area + * + * The @align_mask should be one less than a power of 2; the effect is that + * the bit offset of all zero areas this function finds is multiples of that + * power of 2. A @align_mask of 0 means no alignment is required. + */ +unsigned long bitmap_find_next_zero_area(unsigned long *map, + unsigned long size, + unsigned long start, + unsigned int nr, + unsigned long align_mask) +{ + unsigned long index, end, i; +again: + index = find_next_zero_bit(map, size, start); + + /* Align allocation */ + index = __ALIGN_MASK(index, align_mask); + + end = index + nr; + if (end > size) { + return end; + } + i = find_next_bit(map, end, index); + if (i < end) { + start = i + 1; + goto again; + } + return index; +} + +int __bitmap_intersects(const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits) +{ + int k, lim = bits/BITS_PER_LONG; + + for (k = 0; k < lim; ++k) { + if (bitmap1[k] & bitmap2[k]) { + return 1; + } + } + + if (bits % BITS_PER_LONG) { + if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) { + return 1; + } + } + return 0; +} diff --git a/bitmap.h b/bitmap.h new file mode 100644 index 0000000..a8280b0 --- /dev/null +++ b/bitmap.h @@ -0,0 +1,222 @@ +/* + * Bitmap Module + * + * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> + * + * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h + * + * This work is licensed under the terms of the GNU LGPL, version 2.1 or later. + * See the COPYING.LIB file in the top-level directory. + */ + +#ifndef BITMAP_H +#define BITMAP_H + +#include "qemu-common.h" +#include "bitops.h" + +/* + * The available bitmap operations and their rough meaning in the + * case that the bitmap is a single unsigned long are thus: + * + * Note that nbits should be always a compile time evaluable constant. + * Otherwise many inlines will generate horrible code. + * + * bitmap_zero(dst, nbits) *dst = 0UL + * bitmap_fill(dst, nbits) *dst = ~0UL + * bitmap_copy(dst, src, nbits) *dst = *src + * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2 + * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2 + * bitmap_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2 + * bitmap_andnot(dst, src1, src2, nbits) *dst = *src1 & ~(*src2) + * bitmap_complement(dst, src, nbits) *dst = ~(*src) + * bitmap_equal(src1, src2, nbits) Are *src1 and *src2 equal? + * bitmap_intersects(src1, src2, nbits) Do *src1 and *src2 overlap? + * bitmap_empty(src, nbits) Are all bits zero in *src? + * bitmap_full(src, nbits) Are all bits set in *src? + * bitmap_set(dst, pos, nbits) Set specified bit area + * bitmap_clear(dst, pos, nbits) Clear specified bit area + * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area + */ + +/* + * Also the following operations apply to bitmaps. + * + * set_bit(bit, addr) *addr |= bit + * clear_bit(bit, addr) *addr &= ~bit + * change_bit(bit, addr) *addr ^= bit + * test_bit(bit, addr) Is bit set in *addr? + * test_and_set_bit(bit, addr) Set bit and return old value + * test_and_clear_bit(bit, addr) Clear bit and return old value + * test_and_change_bit(bit, addr) Change bit and return old value + * find_first_zero_bit(addr, nbits) Position first zero bit in *addr + * find_first_bit(addr, nbits) Position first set bit in *addr + * find_next_zero_bit(addr, nbits, bit) Position next zero bit in *addr >= bit + * find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit + */ + +#define BITMAP_LAST_WORD_MASK(nbits) \ + ( \ + ((nbits) % BITS_PER_LONG) ? \ + (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \ + ) + +#define DECLARE_BITMAP(name,bits) \ + unsigned long name[BITS_TO_LONGS(bits)] + +#define small_nbits(nbits) \ + ((nbits) <= BITS_PER_LONG) + +int __bitmap_empty(const unsigned long *bitmap, int bits); +int __bitmap_full(const unsigned long *bitmap, int bits); +int __bitmap_equal(const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits); +void __bitmap_complement(unsigned long *dst, const unsigned long *src, + int bits); +void __bitmap_shift_right(unsigned long *dst, + const unsigned long *src, int shift, int bits); +void __bitmap_shift_left(unsigned long *dst, + const unsigned long *src, int shift, int bits); +int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits); +void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits); +void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits); +int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits); +int __bitmap_intersects(const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits); + +static inline unsigned long *bitmap_new(int nbits) +{ + int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); + return qemu_mallocz(len); +} + +static inline void bitmap_zero(unsigned long *dst, int nbits) +{ + if (small_nbits(nbits)) { + *dst = 0UL; + } else { + int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); + memset(dst, 0, len); + } +} + +static inline void bitmap_fill(unsigned long *dst, int nbits) +{ + size_t nlongs = BITS_TO_LONGS(nbits); + if (!small_nbits(nbits)) { + int len = (nlongs - 1) * sizeof(unsigned long); + memset(dst, 0xff, len); + } + dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits); +} + +static inline void bitmap_copy(unsigned long *dst, const unsigned long *src, + int nbits) +{ + if (small_nbits(nbits)) { + *dst = *src; + } else { + int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); + memcpy(dst, src, len); + } +} + +static inline int bitmap_and(unsigned long *dst, const unsigned long *src1, + const unsigned long *src2, int nbits) +{ + if (small_nbits(nbits)) { + return (*dst = *src1 & *src2) != 0; + } + return __bitmap_and(dst, src1, src2, nbits); +} + +static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, + const unsigned long *src2, int nbits) +{ + if (small_nbits(nbits)) { + *dst = *src1 | *src2; + } else { + __bitmap_or(dst, src1, src2, nbits); + } +} + +static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1, + const unsigned long *src2, int nbits) +{ + if (small_nbits(nbits)) { + *dst = *src1 ^ *src2; + } else { + __bitmap_xor(dst, src1, src2, nbits); + } +} + +static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1, + const unsigned long *src2, int nbits) +{ + if (small_nbits(nbits)) { + return (*dst = *src1 & ~(*src2)) != 0; + } + return __bitmap_andnot(dst, src1, src2, nbits); +} + +static inline void bitmap_complement(unsigned long *dst, const unsigned long *src, + int nbits) +{ + if (small_nbits(nbits)) { + *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits); + } else { + __bitmap_complement(dst, src, nbits); + } +} + +static inline int bitmap_equal(const unsigned long *src1, + const unsigned long *src2, int nbits) +{ + if (small_nbits(nbits)) { + return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)); + } else { + return __bitmap_equal(src1, src2, nbits); + } +} + +static inline int bitmap_empty(const unsigned long *src, int nbits) +{ + if (small_nbits(nbits)) { + return ! (*src & BITMAP_LAST_WORD_MASK(nbits)); + } else { + return __bitmap_empty(src, nbits); + } +} + +static inline int bitmap_full(const unsigned long *src, int nbits) +{ + if (small_nbits(nbits)) { + return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits)); + } else { + return __bitmap_full(src, nbits); + } +} + +static inline int bitmap_intersects(const unsigned long *src1, + const unsigned long *src2, int nbits) +{ + if (small_nbits(nbits)) { + return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; + } else { + return __bitmap_intersects(src1, src2, nbits); + } +} + +void bitmap_set(unsigned long *map, int i, int len); +void bitmap_clear(unsigned long *map, int start, int nr); +unsigned long bitmap_find_next_zero_area(unsigned long *map, + unsigned long size, + unsigned long start, + unsigned int nr, + unsigned long align_mask); + +#endif /* BITMAP_H */ diff --git a/bitops.c b/bitops.c new file mode 100644 index 0000000..730739c --- /dev/null +++ b/bitops.c @@ -0,0 +1,142 @@ +/* + * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. + * Written by David Howells (dhowells@redhat.com) + * Copyright (C) 2008 IBM Corporation + * Written by Rusty Russell <rusty@rustcorp.com.au> + * (Inspired by David Howell's find_next_bit implementation) + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version + * 2 of the License, or (at your option) any later version. + */ + +#include "bitops.h" + +#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) + +/* + * Find the next set bit in a memory region. + */ +unsigned long find_next_bit(const unsigned long *addr, unsigned long size, + unsigned long offset) +{ + const unsigned long *p = addr + BITOP_WORD(offset); + unsigned long result = offset & ~(BITS_PER_LONG-1); + unsigned long tmp; + + if (offset >= size) { + return size; + } + size -= result; + offset %= BITS_PER_LONG; + if (offset) { + tmp = *(p++); + tmp &= (~0UL << offset); + if (size < BITS_PER_LONG) { + goto found_first; + } + if (tmp) { + goto found_middle; + } + size -= BITS_PER_LONG; + result += BITS_PER_LONG; + } + while (size & ~(BITS_PER_LONG-1)) { + if ((tmp = *(p++))) { + goto found_middle; + } + result += BITS_PER_LONG; + size -= BITS_PER_LONG; + } + if (!size) { + return result; + } + tmp = *p; + +found_first: + tmp &= (~0UL >> (BITS_PER_LONG - size)); + if (tmp == 0UL) { /* Are any bits set? */ + return result + size; /* Nope. */ + } +found_middle: + return result + __ffs(tmp); +} + +/* + * This implementation of find_{first,next}_zero_bit was stolen from + * Linus' asm-alpha/bitops.h. + */ +unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, + unsigned long offset) +{ + const unsigned long *p = addr + BITOP_WORD(offset); + unsigned long result = offset & ~(BITS_PER_LONG-1); + unsigned long tmp; + + if (offset >= size) { + return size; + } + size -= result; + offset %= BITS_PER_LONG; + if (offset) { + tmp = *(p++); + tmp |= ~0UL >> (BITS_PER_LONG - offset); + if (size < BITS_PER_LONG) { + goto found_first; + } + if (~tmp) { + goto found_middle; + } + size -= BITS_PER_LONG; + result += BITS_PER_LONG; + } + while (size & ~(BITS_PER_LONG-1)) { + if (~(tmp = *(p++))) { + goto found_middle; + } + result += BITS_PER_LONG; + size -= BITS_PER_LONG; + } + if (!size) { + return result; + } + tmp = *p; + +found_first: + tmp |= ~0UL << size; + if (tmp == ~0UL) { /* Are any bits zero? */ + return result + size; /* Nope. */ + } +found_middle: + return result + ffz(tmp); +} + +unsigned long find_last_bit(const unsigned long *addr, unsigned long size) +{ + unsigned long words; + unsigned long tmp; + + /* Start at final word. */ + words = size / BITS_PER_LONG; + + /* Partial final word? */ + if (size & (BITS_PER_LONG-1)) { + tmp = (addr[words] & (~0UL >> (BITS_PER_LONG + - (size & (BITS_PER_LONG-1))))); + if (tmp) { + goto found; + } + } + + while (words) { + tmp = addr[--words]; + if (tmp) { + found: + return words * BITS_PER_LONG + __fls(tmp); + } + } + + /* Not found */ + return size; +} diff --git a/bitops.h b/bitops.h new file mode 100644 index 0000000..dcd3da9 --- /dev/null +++ b/bitops.h @@ -0,0 +1,272 @@ +/* + * Bitops Module + * + * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> + * + * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h + * + * This work is licensed under the terms of the GNU LGPL, version 2.1 or later. + * See the COPYING.LIB file in the top-level directory. + */ + +#ifndef BITOPS_H +#define BITOPS_H + +#include "qemu-common.h" + +#define BITS_PER_BYTE CHAR_BIT +#define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) + +#define BIT(nr) (1UL << (nr)) +#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) +#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) + +/** + * __ffs - find first bit in word. + * @word: The word to search + * + * Undefined if no bit exists, so code should check against 0 first. + */ +static unsigned long __ffs(unsigned long word) +{ + int num = 0; + +#if LONG_MAX > 0x7FFFFFFF + if ((word & 0xffffffff) == 0) { + num += 32; + word >>= 32; + } +#endif + if ((word & 0xffff) == 0) { + num += 16; + word >>= 16; + } + if ((word & 0xff) == 0) { + num += 8; + word >>= 8; + } + if ((word & 0xf) == 0) { + num += 4; + word >>= 4; + } + if ((word & 0x3) == 0) { + num += 2; + word >>= 2; + } + if ((word & 0x1) == 0) { + num += 1; + } + return num; +} + +/** + * __fls - find last (most-significant) set bit in a long word + * @word: the word to search + * + * Undefined if no set bit exists, so code should check against 0 first. + */ +static __always_inline unsigned long __fls(unsigned long word) +{ + int num = BITS_PER_LONG - 1; + +#if LONG_MAX > 0x7FFFFFFF + if (!(word & (~0ul << 32))) { + num -= 32; + word <<= 32; + } +#endif + if (!(word & (~0ul << (BITS_PER_LONG-16)))) { + num -= 16; + word <<= 16; + } + if (!(word & (~0ul << (BITS_PER_LONG-8)))) { + num -= 8; + word <<= 8; + } + if (!(word & (~0ul << (BITS_PER_LONG-4)))) { + num -= 4; + word <<= 4; + } + if (!(word & (~0ul << (BITS_PER_LONG-2)))) { + num -= 2; + + word <<= 2; + } + if (!(word & (~0ul << (BITS_PER_LONG-1)))) + num -= 1; + return num; +} + +/** + * ffz - find first zero in word. + * @word: The word to search + * + * Undefined if no zero exists, so code should check against ~0UL first. + */ +static inline unsigned long ffz(unsigned long word) +{ + return __ffs(~word); +} + +/** + * set_bit - Set a bit in memory + * @nr: the bit to set + * @addr: the address to start counting from + */ +static inline void set_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + + *p |= mask; +} + +/** + * clear_bit - Clears a bit in memory + * @nr: Bit to clear + * @addr: Address to start counting from + */ +static inline void clear_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + + *p &= ~mask; +} + +/** + * change_bit - Toggle a bit in memory + * @nr: Bit to change + * @addr: Address to start counting from + */ +static inline void change_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + + *p ^= mask; +} + +/** + * test_and_set_bit - Set a bit and return its old value + * @nr: Bit to set + * @addr: Address to count from + */ +static inline int test_and_set_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + unsigned long old = *p; + + *p = old | mask; + return (old & mask) != 0; +} + +/** + * test_and_clear_bit - Clear a bit and return its old value + * @nr: Bit to clear + * @addr: Address to count from + */ +static inline int test_and_clear_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + unsigned long old = *p; + + *p = old & ~mask; + return (old & mask) != 0; +} + +/** + * test_and_change_bit - Change a bit and return its old value + * @nr: Bit to change + * @addr: Address to count from + */ +static inline int test_and_change_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + unsigned long old; + + *p = old ^ mask; + return (old & mask) != 0; +} + +/** + * test_bit - Determine whether a bit is set + * @nr: bit number to test + * @addr: Address to start counting from + */ +static inline int test_bit(int nr, const volatile unsigned long *addr) +{ + return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); +} + +/** + * find_last_bit - find the last set bit in a memory region + * @addr: The address to start the search at + * @size: The maximum size to search + * + * Returns the bit number of the first set bit, or size. + */ +unsigned long find_last_bit(const unsigned long *addr, + unsigned long size); + +/** + * find_next_bit - find the next set bit in a memory region + * @addr: The address to base the search on + * @offset: The bitnumber to start searching at + * @size: The bitmap size in bits + */ +unsigned long find_next_bit(const unsigned long *addr, + unsigned long size, unsigned long offset); + +/** + * find_next_zero_bit - find the next cleared bit in a memory region + * @addr: The address to base the search on + * @offset: The bitnumber to start searching at + * @size: The bitmap size in bits + */ + +unsigned long find_next_zero_bit(const unsigned long *addr, + unsigned long size, + unsigned long offset); + +/** + * find_first_bit - find the first set bit in a memory region + * @addr: The address to start the search at + * @size: The maximum size to search + * + * Returns the bit number of the first set bit. + */ +static inline unsigned long find_first_bit(const unsigned long *addr, + unsigned long size) +{ + return find_next_bit(addr, size, 0); +} + +/** + * find_first_zero_bit - find the first cleared bit in a memory region + * @addr: The address to start the search at + * @size: The maximum size to search + * + * Returns the bit number of the first cleared bit. + */ +static inline unsigned long find_first_zero_bit(const unsigned long *addr, + unsigned long size) +{ + return find_next_zero_bit(addr, size, 0); +} + +static inline unsigned long hweight_long(unsigned long w) +{ + unsigned long count; + + for (count = 0; w; w >>= 1) { + count += w & 1; + } + return count; +} + +#endif diff --git a/osdep.h b/osdep.h index 8bd30d7..27eedcf 100644 --- a/osdep.h +++ b/osdep.h @@ -57,6 +57,10 @@ #define MAX(a, b) (((a) > (b)) ? (a) : (b)) #endif +#ifndef DIV_ROUND_UP +#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d)) +#endif + #ifndef ARRAY_SIZE #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) #endif -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* Re: [Qemu-devel] [PATCH v2 11/15] bitmap: add a generic bitmap and bitops library 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 11/15] bitmap: add a generic bitmap and bitops library Corentin Chary @ 2010-11-11 19:07 ` Blue Swirl 2010-11-11 21:25 ` Corentin Chary 0 siblings, 1 reply; 21+ messages in thread From: Blue Swirl @ 2010-11-11 19:07 UTC (permalink / raw) To: Corentin Chary Cc: Anthony Liguori, Andre Przywara, Qemu-development List, Alexander Graf On Thu, Nov 11, 2010 at 4:57 PM, Corentin Chary <corentincj@iksaif.net> wrote: > Add most used bitmap and bitops functions into bitmap.c and bitops.c. > Theses functions are mostly copied from Linux kernel source. > > Some of these functions are already redefined in the VNC server. Some > of them could be used for some block stuff. The yet yo be submitted > NUMA work also need bitmaps. > > Signed-off-by: Corentin Chary <corentincj@iksaif.net> > --- > Makefile.objs | 1 + > bitmap.c | 255 +++++++++++++++++++++++++++++++++++++++++++++++++++++ > bitmap.h | 222 ++++++++++++++++++++++++++++++++++++++++++++++ > bitops.c | 142 ++++++++++++++++++++++++++++++ > bitops.h | 272 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ > osdep.h | 4 + > 6 files changed, 896 insertions(+), 0 deletions(-) > create mode 100644 bitmap.c > create mode 100644 bitmap.h > create mode 100644 bitops.c > create mode 100644 bitops.h > > diff --git a/Makefile.objs b/Makefile.objs > index 3da959c..e9ee4a8 100644 > --- a/Makefile.objs > +++ b/Makefile.objs > @@ -92,6 +92,7 @@ common-obj-y += msmouse.o ps2.o > common-obj-y += qdev.o qdev-properties.o > common-obj-y += block-migration.o > common-obj-y += pflib.o > +common-obj-y += bitmap.c bitops.c > > common-obj-$(CONFIG_BRLAPI) += baum.o > common-obj-$(CONFIG_POSIX) += migration-exec.o migration-unix.o migration-fd.o > diff --git a/bitmap.c b/bitmap.c > new file mode 100644 > index 0000000..eaafbea > --- /dev/null > +++ b/bitmap.c > @@ -0,0 +1,255 @@ > +/* > + * Bitmap Module > + * > + * Stolen from linux/src/lib/bitmap.c > + * > + * Copyright (C) 2010 Corentin Chary > + * > + * This source code is licensed under the GNU General Public License, > + * Version 2. > + */ > + > +#include "bitops.h" > +#include "bitmap.h" > + > +/* > + * bitmaps provide an array of bits, implemented using an an > + * array of unsigned longs. The number of valid bits in a > + * given bitmap does _not_ need to be an exact multiple of > + * BITS_PER_LONG. > + * > + * The possible unused bits in the last, partially used word > + * of a bitmap are 'don't care'. The implementation makes > + * no particular effort to keep them zero. It ensures that > + * their value will not affect the results of any operation. > + * The bitmap operations that return Boolean (bitmap_empty, > + * for example) or scalar (bitmap_weight, for example) results > + * carefully filter out these unused bits from impacting their > + * results. > + * > + * These operations actually hold to a slightly stronger rule: > + * if you don't input any bitmaps to these ops that have some > + * unused bits set, then they won't output any set unused bits > + * in output bitmaps. > + * > + * The byte ordering of bitmaps is more natural on little > + * endian architectures. > + */ > + > +int __bitmap_empty(const unsigned long *bitmap, int bits) Please don't use identifiers starting with underscore. > +{ > + int k, lim = bits/BITS_PER_LONG; > + > + for (k = 0; k < lim; ++k) { > + if (bitmap[k]) { > + return 0; > + } > + } > + if (bits % BITS_PER_LONG) { > + if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) { > + return 0; > + } > + } > + > + return 1; > +} > + > +int __bitmap_full(const unsigned long *bitmap, int bits) > +{ > + int k, lim = bits/BITS_PER_LONG; > + > + for (k = 0; k < lim; ++k) { > + if (~bitmap[k]) { > + return 0; > + } > + } > + > + if (bits % BITS_PER_LONG) { > + if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) { > + return 0; > + } > + } > + > + return 1; > +} > + > +int __bitmap_equal(const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits) > +{ > + int k, lim = bits/BITS_PER_LONG; > + > + for (k = 0; k < lim; ++k) { > + if (bitmap1[k] != bitmap2[k]) { > + return 0; > + } > + } > + > + if (bits % BITS_PER_LONG) { > + if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) { > + return 0; > + } > + } > + > + return 1; > +} > + > +void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits) > +{ > + int k, lim = bits/BITS_PER_LONG; > + > + for (k = 0; k < lim; ++k) { > + dst[k] = ~src[k]; > + } > + > + if (bits % BITS_PER_LONG) { > + dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits); > + } > +} > + > +int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits) > +{ > + int k; > + int nr = BITS_TO_LONGS(bits); > + unsigned long result = 0; > + > + for (k = 0; k < nr; k++) { > + result |= (dst[k] = bitmap1[k] & bitmap2[k]); > + } > + return result != 0; > +} > + > +void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits) > +{ > + int k; > + int nr = BITS_TO_LONGS(bits); > + > + for (k = 0; k < nr; k++) { > + dst[k] = bitmap1[k] | bitmap2[k]; > + } > +} > + > +void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits) > +{ > + int k; > + int nr = BITS_TO_LONGS(bits); > + > + for (k = 0; k < nr; k++) { > + dst[k] = bitmap1[k] ^ bitmap2[k]; > + } > +} > + > +int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits) > +{ > + int k; > + int nr = BITS_TO_LONGS(bits); > + unsigned long result = 0; > + > + for (k = 0; k < nr; k++) { > + result |= (dst[k] = bitmap1[k] & ~bitmap2[k]); > + } > + return result != 0; > +} > + > +#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) > + > +void bitmap_set(unsigned long *map, int start, int nr) > +{ > + unsigned long *p = map + BIT_WORD(start); > + const int size = start + nr; > + int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); > + unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); > + > + while (nr - bits_to_set >= 0) { > + *p |= mask_to_set; > + nr -= bits_to_set; > + bits_to_set = BITS_PER_LONG; > + mask_to_set = ~0UL; > + p++; > + } > + if (nr) { > + mask_to_set &= BITMAP_LAST_WORD_MASK(size); > + *p |= mask_to_set; > + } > +} > + > +void bitmap_clear(unsigned long *map, int start, int nr) > +{ > + unsigned long *p = map + BIT_WORD(start); > + const int size = start + nr; > + int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); > + unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); > + > + while (nr - bits_to_clear >= 0) { > + *p &= ~mask_to_clear; > + nr -= bits_to_clear; > + bits_to_clear = BITS_PER_LONG; > + mask_to_clear = ~0UL; > + p++; > + } > + if (nr) { > + mask_to_clear &= BITMAP_LAST_WORD_MASK(size); > + *p &= ~mask_to_clear; > + } > +} > + > +#define __ALIGN_MASK(x,mask) (((x)+(mask))&~(mask)) > + > +/** > + * bitmap_find_next_zero_area - find a contiguous aligned zero area > + * @map: The address to base the search on > + * @size: The bitmap size in bits > + * @start: The bitnumber to start searching at > + * @nr: The number of zeroed bits we're looking for > + * @align_mask: Alignment mask for zero area > + * > + * The @align_mask should be one less than a power of 2; the effect is that > + * the bit offset of all zero areas this function finds is multiples of that > + * power of 2. A @align_mask of 0 means no alignment is required. > + */ > +unsigned long bitmap_find_next_zero_area(unsigned long *map, > + unsigned long size, > + unsigned long start, > + unsigned int nr, > + unsigned long align_mask) > +{ > + unsigned long index, end, i; > +again: > + index = find_next_zero_bit(map, size, start); > + > + /* Align allocation */ > + index = __ALIGN_MASK(index, align_mask); > + > + end = index + nr; > + if (end > size) { > + return end; > + } > + i = find_next_bit(map, end, index); > + if (i < end) { > + start = i + 1; > + goto again; > + } > + return index; > +} > + > +int __bitmap_intersects(const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits) > +{ > + int k, lim = bits/BITS_PER_LONG; > + > + for (k = 0; k < lim; ++k) { > + if (bitmap1[k] & bitmap2[k]) { > + return 1; > + } > + } > + > + if (bits % BITS_PER_LONG) { > + if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) { > + return 1; > + } > + } > + return 0; > +} > diff --git a/bitmap.h b/bitmap.h > new file mode 100644 > index 0000000..a8280b0 > --- /dev/null > +++ b/bitmap.h > @@ -0,0 +1,222 @@ > +/* > + * Bitmap Module > + * > + * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> > + * > + * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h > + * > + * This work is licensed under the terms of the GNU LGPL, version 2.1 or later. > + * See the COPYING.LIB file in the top-level directory. > + */ > + > +#ifndef BITMAP_H > +#define BITMAP_H > + > +#include "qemu-common.h" > +#include "bitops.h" > + > +/* > + * The available bitmap operations and their rough meaning in the > + * case that the bitmap is a single unsigned long are thus: > + * > + * Note that nbits should be always a compile time evaluable constant. > + * Otherwise many inlines will generate horrible code. > + * > + * bitmap_zero(dst, nbits) *dst = 0UL > + * bitmap_fill(dst, nbits) *dst = ~0UL > + * bitmap_copy(dst, src, nbits) *dst = *src > + * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2 > + * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2 > + * bitmap_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2 > + * bitmap_andnot(dst, src1, src2, nbits) *dst = *src1 & ~(*src2) > + * bitmap_complement(dst, src, nbits) *dst = ~(*src) > + * bitmap_equal(src1, src2, nbits) Are *src1 and *src2 equal? > + * bitmap_intersects(src1, src2, nbits) Do *src1 and *src2 overlap? > + * bitmap_empty(src, nbits) Are all bits zero in *src? > + * bitmap_full(src, nbits) Are all bits set in *src? > + * bitmap_set(dst, pos, nbits) Set specified bit area > + * bitmap_clear(dst, pos, nbits) Clear specified bit area > + * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area > + */ > + > +/* > + * Also the following operations apply to bitmaps. > + * > + * set_bit(bit, addr) *addr |= bit > + * clear_bit(bit, addr) *addr &= ~bit > + * change_bit(bit, addr) *addr ^= bit > + * test_bit(bit, addr) Is bit set in *addr? > + * test_and_set_bit(bit, addr) Set bit and return old value > + * test_and_clear_bit(bit, addr) Clear bit and return old value > + * test_and_change_bit(bit, addr) Change bit and return old value > + * find_first_zero_bit(addr, nbits) Position first zero bit in *addr > + * find_first_bit(addr, nbits) Position first set bit in *addr > + * find_next_zero_bit(addr, nbits, bit) Position next zero bit in *addr >= bit > + * find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit > + */ > + > +#define BITMAP_LAST_WORD_MASK(nbits) \ > + ( \ > + ((nbits) % BITS_PER_LONG) ? \ > + (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \ > + ) > + > +#define DECLARE_BITMAP(name,bits) \ > + unsigned long name[BITS_TO_LONGS(bits)] > + > +#define small_nbits(nbits) \ > + ((nbits) <= BITS_PER_LONG) > + > +int __bitmap_empty(const unsigned long *bitmap, int bits); > +int __bitmap_full(const unsigned long *bitmap, int bits); > +int __bitmap_equal(const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits); > +void __bitmap_complement(unsigned long *dst, const unsigned long *src, > + int bits); > +void __bitmap_shift_right(unsigned long *dst, > + const unsigned long *src, int shift, int bits); > +void __bitmap_shift_left(unsigned long *dst, > + const unsigned long *src, int shift, int bits); > +int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits); > +void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits); > +void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits); > +int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits); > +int __bitmap_intersects(const unsigned long *bitmap1, > + const unsigned long *bitmap2, int bits); > + > +static inline unsigned long *bitmap_new(int nbits) > +{ > + int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); > + return qemu_mallocz(len); > +} > + > +static inline void bitmap_zero(unsigned long *dst, int nbits) > +{ > + if (small_nbits(nbits)) { > + *dst = 0UL; > + } else { > + int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); > + memset(dst, 0, len); > + } > +} > + > +static inline void bitmap_fill(unsigned long *dst, int nbits) > +{ > + size_t nlongs = BITS_TO_LONGS(nbits); > + if (!small_nbits(nbits)) { > + int len = (nlongs - 1) * sizeof(unsigned long); > + memset(dst, 0xff, len); > + } > + dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits); > +} > + > +static inline void bitmap_copy(unsigned long *dst, const unsigned long *src, > + int nbits) > +{ > + if (small_nbits(nbits)) { > + *dst = *src; > + } else { > + int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); > + memcpy(dst, src, len); > + } > +} > + > +static inline int bitmap_and(unsigned long *dst, const unsigned long *src1, > + const unsigned long *src2, int nbits) > +{ > + if (small_nbits(nbits)) { > + return (*dst = *src1 & *src2) != 0; > + } > + return __bitmap_and(dst, src1, src2, nbits); > +} > + > +static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, > + const unsigned long *src2, int nbits) > +{ > + if (small_nbits(nbits)) { > + *dst = *src1 | *src2; > + } else { > + __bitmap_or(dst, src1, src2, nbits); > + } > +} > + > +static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1, > + const unsigned long *src2, int nbits) > +{ > + if (small_nbits(nbits)) { > + *dst = *src1 ^ *src2; > + } else { > + __bitmap_xor(dst, src1, src2, nbits); > + } > +} > + > +static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1, > + const unsigned long *src2, int nbits) > +{ > + if (small_nbits(nbits)) { > + return (*dst = *src1 & ~(*src2)) != 0; > + } > + return __bitmap_andnot(dst, src1, src2, nbits); > +} > + > +static inline void bitmap_complement(unsigned long *dst, const unsigned long *src, > + int nbits) > +{ > + if (small_nbits(nbits)) { > + *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits); > + } else { > + __bitmap_complement(dst, src, nbits); > + } > +} > + > +static inline int bitmap_equal(const unsigned long *src1, > + const unsigned long *src2, int nbits) > +{ > + if (small_nbits(nbits)) { > + return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)); > + } else { > + return __bitmap_equal(src1, src2, nbits); > + } > +} > + > +static inline int bitmap_empty(const unsigned long *src, int nbits) > +{ > + if (small_nbits(nbits)) { > + return ! (*src & BITMAP_LAST_WORD_MASK(nbits)); > + } else { > + return __bitmap_empty(src, nbits); > + } > +} > + > +static inline int bitmap_full(const unsigned long *src, int nbits) > +{ > + if (small_nbits(nbits)) { > + return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits)); > + } else { > + return __bitmap_full(src, nbits); > + } > +} > + > +static inline int bitmap_intersects(const unsigned long *src1, > + const unsigned long *src2, int nbits) > +{ > + if (small_nbits(nbits)) { > + return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; > + } else { > + return __bitmap_intersects(src1, src2, nbits); > + } > +} > + > +void bitmap_set(unsigned long *map, int i, int len); > +void bitmap_clear(unsigned long *map, int start, int nr); > +unsigned long bitmap_find_next_zero_area(unsigned long *map, > + unsigned long size, > + unsigned long start, > + unsigned int nr, > + unsigned long align_mask); > + > +#endif /* BITMAP_H */ > diff --git a/bitops.c b/bitops.c > new file mode 100644 > index 0000000..730739c > --- /dev/null > +++ b/bitops.c > @@ -0,0 +1,142 @@ > +/* > + * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. > + * Written by David Howells (dhowells@redhat.com) > + * Copyright (C) 2008 IBM Corporation > + * Written by Rusty Russell <rusty@rustcorp.com.au> > + * (Inspired by David Howell's find_next_bit implementation) > + * > + * This program is free software; you can redistribute it and/or > + * modify it under the terms of the GNU General Public License > + * as published by the Free Software Foundation; either version > + * 2 of the License, or (at your option) any later version. > + */ > + > +#include "bitops.h" > + > +#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) > + > +/* > + * Find the next set bit in a memory region. > + */ > +unsigned long find_next_bit(const unsigned long *addr, unsigned long size, > + unsigned long offset) > +{ > + const unsigned long *p = addr + BITOP_WORD(offset); > + unsigned long result = offset & ~(BITS_PER_LONG-1); > + unsigned long tmp; > + > + if (offset >= size) { > + return size; > + } > + size -= result; > + offset %= BITS_PER_LONG; > + if (offset) { > + tmp = *(p++); > + tmp &= (~0UL << offset); > + if (size < BITS_PER_LONG) { > + goto found_first; > + } > + if (tmp) { > + goto found_middle; > + } > + size -= BITS_PER_LONG; > + result += BITS_PER_LONG; > + } > + while (size & ~(BITS_PER_LONG-1)) { > + if ((tmp = *(p++))) { > + goto found_middle; > + } > + result += BITS_PER_LONG; > + size -= BITS_PER_LONG; > + } > + if (!size) { > + return result; > + } > + tmp = *p; > + > +found_first: > + tmp &= (~0UL >> (BITS_PER_LONG - size)); > + if (tmp == 0UL) { /* Are any bits set? */ > + return result + size; /* Nope. */ > + } > +found_middle: > + return result + __ffs(tmp); > +} > + > +/* > + * This implementation of find_{first,next}_zero_bit was stolen from > + * Linus' asm-alpha/bitops.h. > + */ > +unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, > + unsigned long offset) > +{ > + const unsigned long *p = addr + BITOP_WORD(offset); > + unsigned long result = offset & ~(BITS_PER_LONG-1); > + unsigned long tmp; > + > + if (offset >= size) { > + return size; > + } > + size -= result; > + offset %= BITS_PER_LONG; > + if (offset) { > + tmp = *(p++); > + tmp |= ~0UL >> (BITS_PER_LONG - offset); > + if (size < BITS_PER_LONG) { > + goto found_first; > + } > + if (~tmp) { > + goto found_middle; > + } > + size -= BITS_PER_LONG; > + result += BITS_PER_LONG; > + } > + while (size & ~(BITS_PER_LONG-1)) { > + if (~(tmp = *(p++))) { > + goto found_middle; > + } > + result += BITS_PER_LONG; > + size -= BITS_PER_LONG; > + } > + if (!size) { > + return result; > + } > + tmp = *p; > + > +found_first: > + tmp |= ~0UL << size; > + if (tmp == ~0UL) { /* Are any bits zero? */ > + return result + size; /* Nope. */ > + } > +found_middle: > + return result + ffz(tmp); > +} > + > +unsigned long find_last_bit(const unsigned long *addr, unsigned long size) > +{ > + unsigned long words; > + unsigned long tmp; > + > + /* Start at final word. */ > + words = size / BITS_PER_LONG; > + > + /* Partial final word? */ > + if (size & (BITS_PER_LONG-1)) { > + tmp = (addr[words] & (~0UL >> (BITS_PER_LONG > + - (size & (BITS_PER_LONG-1))))); > + if (tmp) { > + goto found; > + } > + } > + > + while (words) { > + tmp = addr[--words]; > + if (tmp) { > + found: > + return words * BITS_PER_LONG + __fls(tmp); > + } > + } > + > + /* Not found */ > + return size; > +} > diff --git a/bitops.h b/bitops.h > new file mode 100644 > index 0000000..dcd3da9 > --- /dev/null > +++ b/bitops.h > @@ -0,0 +1,272 @@ > +/* > + * Bitops Module > + * > + * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> > + * > + * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h > + * > + * This work is licensed under the terms of the GNU LGPL, version 2.1 or later. > + * See the COPYING.LIB file in the top-level directory. > + */ > + > +#ifndef BITOPS_H > +#define BITOPS_H > + > +#include "qemu-common.h" > + > +#define BITS_PER_BYTE CHAR_BIT > +#define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) > + > +#define BIT(nr) (1UL << (nr)) > +#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) > +#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) > +#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) > + > +/** > + * __ffs - find first bit in word. > + * @word: The word to search > + * > + * Undefined if no bit exists, so code should check against 0 first. > + */ > +static unsigned long __ffs(unsigned long word) We already have ffs() in qemu-common.h and oslib-win32.c. Please use the same method. ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [Qemu-devel] [PATCH v2 11/15] bitmap: add a generic bitmap and bitops library 2010-11-11 19:07 ` Blue Swirl @ 2010-11-11 21:25 ` Corentin Chary 0 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 21:25 UTC (permalink / raw) To: Blue Swirl Cc: Anthony Liguori, Andre Przywara, Qemu-development List, Alexander Graf On Thu, Nov 11, 2010 at 8:07 PM, Blue Swirl <blauwirbel@gmail.com> wrote: > Please don't use identifiers starting with underscore. Ok, I think __bitmap_* could become slow__bitmap_* (because they are the slow path) > We already have ffs() in qemu-common.h and oslib-win32.c. Please use > the same method. > This is not a standard ffs, this is the ffs used in the kernel, where I stealed all those bitop functions. std ffs: return the position of the first bit set, or 0 if no bits are set in i. kernel ffs: Undefined if no bit exists, so code should check against 0 first. __ffs(0): 31 ffs(0): 0 __ffs(1): 0 ffs(1): 1 This behavior is needed for all the other function to work (and makes more sense that the normal ffs). But .. maybe I should just use ffs() - 1 -- Corentin Chary http://xf.iksaif.net ^ permalink raw reply [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 12/15] vnc: use the new generic bitmap functions 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (10 preceding siblings ...) 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 11/15] bitmap: add a generic bitmap and bitops library Corentin Chary @ 2010-11-11 16:57 ` Corentin Chary 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 13/15] vnc: don't try to send bigger updates that client height Corentin Chary ` (3 subsequent siblings) 15 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:57 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara Switch to bitmap.h and bitops.h instead of redefining our own bitmap helpers. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- ui/vnc.c | 91 ++++++++++++++----------------------------------------------- ui/vnc.h | 7 +++-- 2 files changed, 25 insertions(+), 73 deletions(-) diff --git a/ui/vnc.c b/ui/vnc.c index fc2be61..600ea75 100644 --- a/ui/vnc.c +++ b/ui/vnc.c @@ -41,13 +41,6 @@ static const struct timeval VNC_REFRESH_LOSSY = { 2, 0 }; #include "vnc_keysym.h" #include "d3des.h" -#define count_bits(c, v) { \ - for (c = 0; v; v >>= 1) \ - { \ - c += v & 1; \ - } \ -} - static VncDisplay *vnc_display; /* needed for info vnc */ static DisplayChangeListener *dcl; @@ -378,47 +371,6 @@ static void framebuffer_update_request(VncState *vs, int incremental, static void vnc_refresh(void *opaque); static int vnc_refresh_server_surface(VncDisplay *vd); -static inline void vnc_set_bit(uint32_t *d, int k) -{ - d[k >> 5] |= 1 << (k & 0x1f); -} - -static inline void vnc_clear_bit(uint32_t *d, int k) -{ - d[k >> 5] &= ~(1 << (k & 0x1f)); -} - -static inline void vnc_set_bits(uint32_t *d, int n, int nb_words) -{ - int j; - - j = 0; - while (n >= 32) { - d[j++] = -1; - n -= 32; - } - if (n > 0) - d[j++] = (1 << n) - 1; - while (j < nb_words) - d[j++] = 0; -} - -static inline int vnc_get_bit(const uint32_t *d, int k) -{ - return (d[k >> 5] >> (k & 0x1f)) & 1; -} - -static inline int vnc_and_bits(const uint32_t *d1, const uint32_t *d2, - int nb_words) -{ - int i; - for(i = 0; i < nb_words; i++) { - if ((d1[i] & d2[i]) != 0) - return 1; - } - return 0; -} - static void vnc_dpy_update(DisplayState *ds, int x, int y, int w, int h) { int i; @@ -441,7 +393,7 @@ static void vnc_dpy_update(DisplayState *ds, int x, int y, int w, int h) for (; y < h; y++) for (i = 0; i < w; i += 16) - vnc_set_bit(s->dirty[y], (x + i) / 16); + set_bit((x + i) / 16, s->dirty[y]); } void vnc_framebuffer_update(VncState *vs, int x, int y, int w, int h, @@ -780,7 +732,7 @@ static void vnc_dpy_copy(DisplayState *ds, int src_x, int src_y, int dst_x, int memmove(dst_row, src_row, cmp_bytes); QTAILQ_FOREACH(vs, &vd->clients, next) { if (!vnc_has_feature(vs, VNC_FEATURE_COPYRECT)) { - vnc_set_bit(vs->dirty[y], ((x + dst_x) / 16)); + set_bit(((x + dst_x) / 16), vs->dirty[y]); } } } @@ -850,10 +802,12 @@ static int find_and_clear_dirty_height(struct VncState *vs, for (h = 1; h < (vd->server->height - y); h++) { int tmp_x; - if (!vnc_get_bit(vs->dirty[y + h], last_x)) + if (!test_bit(last_x, vs->dirty[y + h])) { break; - for (tmp_x = last_x; tmp_x < x; tmp_x++) - vnc_clear_bit(vs->dirty[y + h], tmp_x); + } + for (tmp_x = last_x; tmp_x < x; tmp_x++) { + clear_bit(tmp_x, vs->dirty[y + h]); + } } return h; @@ -905,11 +859,10 @@ static int vnc_update_client(VncState *vs, int has_dirty) int x; int last_x = -1; for (x = 0; x < width / 16; x++) { - if (vnc_get_bit(vs->dirty[y], x)) { + if (test_and_clear_bit(x, vs->dirty[y])) { if (last_x == -1) { last_x = x; } - vnc_clear_bit(vs->dirty[y], x); } else { if (last_x != -1) { int h = find_and_clear_dirty_height(vs, y, last_x, x); @@ -1702,8 +1655,7 @@ static void framebuffer_update_request(VncState *vs, int incremental, if (!incremental) { vs->force_update = 1; for (i = 0; i < h; i++) { - vnc_set_bits(vs->dirty[y_position + i], - (ds_get_width(vs->ds) / 16), VNC_DIRTY_WORDS); + bitmap_set(vs->dirty[y_position + i], x_position / 16, w / 16); } } } @@ -1842,15 +1794,15 @@ static void set_pixel_format(VncState *vs, vs->clientds = *(vs->vd->guest.ds); vs->clientds.pf.rmax = red_max; - count_bits(vs->clientds.pf.rbits, red_max); + vs->clientds.pf.rbits = hweight_long(red_max); vs->clientds.pf.rshift = red_shift; vs->clientds.pf.rmask = red_max << red_shift; vs->clientds.pf.gmax = green_max; - count_bits(vs->clientds.pf.gbits, green_max); + vs->clientds.pf.gbits = hweight_long(green_max); vs->clientds.pf.gshift = green_shift; vs->clientds.pf.gmask = green_max << green_shift; vs->clientds.pf.bmax = blue_max; - count_bits(vs->clientds.pf.bbits, blue_max); + vs->clientds.pf.bbits = hweight_long(blue_max); vs->clientds.pf.bshift = blue_shift; vs->clientds.pf.bmask = blue_max << blue_shift; vs->clientds.pf.bits_per_pixel = bits_per_pixel; @@ -2314,7 +2266,7 @@ static int vnc_refresh_lossy_rect(VncDisplay *vd, int x, int y) x = x / VNC_STAT_RECT * VNC_STAT_RECT; QTAILQ_FOREACH(vs, &vd->clients, next) { - int j, i; + int j; /* kernel send buffers are full -> refresh later */ if (vs->output.offset) @@ -2325,9 +2277,7 @@ static int vnc_refresh_lossy_rect(VncDisplay *vd, int x, int y) vs->lossy_rect[sty][stx] = 0; for (j = 0; j < VNC_STAT_RECT; ++j) { - for (i = x / 16; i < VNC_STAT_RECT / 16 + x / 16; ++i) { - vnc_set_bit(vs->dirty[y + j], i); - } + bitmap_set(vs->dirty[y + j], x / 16, VNC_STAT_RECT / 16); } has_dirty++; } @@ -2430,7 +2380,7 @@ static int vnc_refresh_server_surface(VncDisplay *vd) uint8_t *guest_row; uint8_t *server_row; int cmp_bytes; - uint32_t width_mask[VNC_DIRTY_WORDS]; + unsigned long width_mask[VNC_DIRTY_WORDS]; VncState *vs; int has_dirty = 0; @@ -2444,12 +2394,14 @@ static int vnc_refresh_server_surface(VncDisplay *vd) * Check and copy modified bits from guest to server surface. * Update server dirty map. */ - vnc_set_bits(width_mask, (ds_get_width(vd->ds) / 16), VNC_DIRTY_WORDS); + bitmap_set(width_mask, 0, (ds_get_width(vd->ds) / 16)); + bitmap_clear(width_mask, (ds_get_width(vd->ds) / 16), + VNC_DIRTY_WORDS * BITS_PER_LONG); cmp_bytes = 16 * ds_get_bytes_per_pixel(vd->ds); guest_row = vd->guest.ds->data; server_row = vd->server->data; for (y = 0; y < vd->guest.ds->height; y++) { - if (vnc_and_bits(vd->guest.dirty[y], width_mask, VNC_DIRTY_WORDS)) { + if (bitmap_intersects(vd->guest.dirty[y], width_mask, VNC_DIRTY_WORDS)) { int x; uint8_t *guest_ptr; uint8_t *server_ptr; @@ -2459,15 +2411,14 @@ static int vnc_refresh_server_surface(VncDisplay *vd) for (x = 0; x < vd->guest.ds->width; x += 16, guest_ptr += cmp_bytes, server_ptr += cmp_bytes) { - if (!vnc_get_bit(vd->guest.dirty[y], (x / 16))) + if (!test_and_clear_bit((x / 16), vd->guest.dirty[y])) continue; - vnc_clear_bit(vd->guest.dirty[y], (x / 16)); if (memcmp(server_ptr, guest_ptr, cmp_bytes) == 0) continue; memcpy(server_ptr, guest_ptr, cmp_bytes); vnc_rect_updated(vd, x, y, &tv); QTAILQ_FOREACH(vs, &vd->clients, next) { - vnc_set_bit(vs->dirty[y], (x / 16)); + set_bit((x / 16), vs->dirty[y]); } has_dirty++; } diff --git a/ui/vnc.h b/ui/vnc.h index 5cfa247..979467b 100644 --- a/ui/vnc.h +++ b/ui/vnc.h @@ -35,6 +35,7 @@ #include "console.h" #include "monitor.h" #include "audio/audio.h" +#include "bitmap.h" #include <zlib.h> #include <stdbool.h> @@ -80,7 +81,7 @@ typedef void VncSendHextileTile(VncState *vs, #define VNC_MAX_WIDTH 2560 #define VNC_MAX_HEIGHT 2048 -#define VNC_DIRTY_WORDS (VNC_MAX_WIDTH / (16 * 32)) +#define VNC_DIRTY_WORDS (VNC_MAX_WIDTH / (16 * BITS_PER_LONG)) #define VNC_STAT_RECT 64 #define VNC_STAT_COLS (VNC_MAX_WIDTH / VNC_STAT_RECT) @@ -113,7 +114,7 @@ typedef struct VncRectStat VncRectStat; struct VncSurface { struct timeval last_freq_check; - uint32_t dirty[VNC_MAX_HEIGHT][VNC_DIRTY_WORDS]; + unsigned long dirty[VNC_MAX_HEIGHT][VNC_DIRTY_WORDS]; VncRectStat stats[VNC_STAT_ROWS][VNC_STAT_COLS]; DisplaySurface *ds; }; @@ -231,7 +232,7 @@ struct VncState int csock; DisplayState *ds; - uint32_t dirty[VNC_MAX_HEIGHT][VNC_DIRTY_WORDS]; + unsigned long dirty[VNC_MAX_HEIGHT][VNC_DIRTY_WORDS]; uint8_t **lossy_rect; /* Not an Array to avoid costly memcpy in * vnc-jobs-async.c */ -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 13/15] vnc: don't try to send bigger updates that client height 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (11 preceding siblings ...) 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 12/15] vnc: use the new generic bitmap functions Corentin Chary @ 2010-11-11 16:57 ` Corentin Chary 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 14/15] vnc: tight: tweak adaptive tight settings Corentin Chary ` (2 subsequent siblings) 15 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:57 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara Respect client size if it doesn't not support desktop resizing. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- ui/vnc.c | 10 +++++----- 1 files changed, 5 insertions(+), 5 deletions(-) diff --git a/ui/vnc.c b/ui/vnc.c index 600ea75..9189014 100644 --- a/ui/vnc.c +++ b/ui/vnc.c @@ -795,12 +795,11 @@ static void vnc_dpy_cursor_define(QEMUCursor *c) } static int find_and_clear_dirty_height(struct VncState *vs, - int y, int last_x, int x) + int y, int last_x, int x, int height) { int h; - VncDisplay *vd = vs->vd; - for (h = 1; h < (vd->server->height - y); h++) { + for (h = 1; h < (height - y); h++) { int tmp_x; if (!test_bit(last_x, vs->dirty[y + h])) { break; @@ -865,7 +864,8 @@ static int vnc_update_client(VncState *vs, int has_dirty) } } else { if (last_x != -1) { - int h = find_and_clear_dirty_height(vs, y, last_x, x); + int h = find_and_clear_dirty_height(vs, y, last_x, x, + height); n += vnc_job_add_rect(job, last_x * 16, y, (x - last_x) * 16, h); @@ -874,7 +874,7 @@ static int vnc_update_client(VncState *vs, int has_dirty) } } if (last_x != -1) { - int h = find_and_clear_dirty_height(vs, y, last_x, x); + int h = find_and_clear_dirty_height(vs, y, last_x, x, height); n += vnc_job_add_rect(job, last_x * 16, y, (x - last_x) * 16, h); } -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 14/15] vnc: tight: tweak adaptive tight settings 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (12 preceding siblings ...) 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 13/15] vnc: don't try to send bigger updates that client height Corentin Chary @ 2010-11-11 16:57 ` Corentin Chary 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 15/15] vnc: add a non-adaptive option Corentin Chary 2010-11-11 17:02 ` [Qemu-devel] Re: [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Alexander Graf 15 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:57 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara The force_jpeg threshold was too low. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- ui/vnc-enc-tight.c | 20 ++++++++++---------- 1 files changed, 10 insertions(+), 10 deletions(-) diff --git a/ui/vnc-enc-tight.c b/ui/vnc-enc-tight.c index 81024d5..82c1e96 100644 --- a/ui/vnc-enc-tight.c +++ b/ui/vnc-enc-tight.c @@ -79,16 +79,16 @@ static const struct { int jpeg_idx; /* Allow indexed JPEG */ int jpeg_full; /* Allow full color JPEG */ } tight_jpeg_conf[] = { - { 0, 4, 1, 1 }, - { 0, 4, 1, 1 }, - { 0, 4, 1, 1 }, - { 0, 4, 1, 1 }, - { 0, 4, 0, 1 }, - { 0.1, 4, 0, 1 }, - { 0.2, 4, 0, 1 }, - { 0.3, 6, 0, 0 }, - { 0.4, 8, 0, 0 }, - { 0.5, 10, 0, 0 }, + { 0, 8, 1, 1 }, + { 0, 8, 1, 1 }, + { 0, 8, 1, 1 }, + { 0, 8, 1, 1 }, + { 0, 10, 1, 1 }, + { 0.1, 10, 1, 1 }, + { 0.2, 10, 1, 1 }, + { 0.3, 12, 0, 0 }, + { 0.4, 14, 0, 0 }, + { 0.5, 16, 0, 0 }, }; #endif -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* [Qemu-devel] [PATCH v2 15/15] vnc: add a non-adaptive option 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (13 preceding siblings ...) 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 14/15] vnc: tight: tweak adaptive tight settings Corentin Chary @ 2010-11-11 16:57 ` Corentin Chary 2010-11-11 17:02 ` [Qemu-devel] Re: [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Alexander Graf 15 siblings, 0 replies; 21+ messages in thread From: Corentin Chary @ 2010-11-11 16:57 UTC (permalink / raw) To: Qemu-development List Cc: Corentin Chary, Anthony Liguori, Alexander Graf, Andre Przywara This option allow to disable adaptive behaviors in some encodings. Signed-off-by: Corentin Chary <corentincj@iksaif.net> --- qemu-options.hx | 9 +++++++++ ui/vnc-enc-tight.c | 2 +- ui/vnc.c | 13 +++++++++---- ui/vnc.h | 1 + 4 files changed, 20 insertions(+), 5 deletions(-) diff --git a/qemu-options.hx b/qemu-options.hx index 4d99a58..fc532b6 100644 --- a/qemu-options.hx +++ b/qemu-options.hx @@ -909,6 +909,15 @@ option is set, VNC client may receive lossy framebuffer updates depending on its encoding settings. Enabling this option can save a lot of bandwidth at the expense of quality. +@item non-adaptive + +Disable adaptive encodings. Adaptive encodings are enabled by default. +An adaptive encoding will try to detect frequently updated screen regions, +and send updates in these regions using a lossy encoding (like JPEG). +This can be really helpfull to save bandwidth when playing videos. Disabling +adaptive encodings allow to restore the original static behavior of encodings +like Tight. + @end table ETEXI diff --git a/ui/vnc-enc-tight.c b/ui/vnc-enc-tight.c index 82c1e96..5933394 100644 --- a/ui/vnc-enc-tight.c +++ b/ui/vnc-enc-tight.c @@ -1546,7 +1546,7 @@ static int send_sub_rect(VncState *vs, int x, int y, int w, int h) vnc_tight_stop(vs); #ifdef CONFIG_VNC_JPEG - if (vs->tight.quality != (uint8_t)-1) { + if (!vs->vd->non_adaptive && vs->tight.quality != (uint8_t)-1) { double freq = vnc_update_freq(vs, x, y, w, h); if (freq < tight_jpeg_conf[vs->tight.quality].jpeg_freq_min) { diff --git a/ui/vnc.c b/ui/vnc.c index 9189014..24c5f7e 100644 --- a/ui/vnc.c +++ b/ui/vnc.c @@ -2384,10 +2384,12 @@ static int vnc_refresh_server_surface(VncDisplay *vd) VncState *vs; int has_dirty = 0; - struct timeval tv; + struct timeval tv = { 0, 0 }; - gettimeofday(&tv, NULL); - has_dirty = vnc_update_stats(vd, &tv); + if (!vd->non_adaptive) { + gettimeofday(&tv, NULL); + has_dirty = vnc_update_stats(vd, &tv); + } /* * Walk through the guest dirty map. @@ -2416,7 +2418,8 @@ static int vnc_refresh_server_surface(VncDisplay *vd) if (memcmp(server_ptr, guest_ptr, cmp_bytes) == 0) continue; memcpy(server_ptr, guest_ptr, cmp_bytes); - vnc_rect_updated(vd, x, y, &tv); + if (!vd->non_adaptive) + vnc_rect_updated(vd, x, y, &tv); QTAILQ_FOREACH(vs, &vd->clients, next) { set_bit((x / 16), vs->dirty[y]); } @@ -2725,6 +2728,8 @@ int vnc_display_open(DisplayState *ds, const char *display) #endif } else if (strncmp(options, "lossy", 5) == 0) { vs->lossy = true; + } else if (strncmp(options, "non-adapative", 13) == 0) { + vs->non_adaptive = true; } } diff --git a/ui/vnc.h b/ui/vnc.h index 979467b..f502690 100644 --- a/ui/vnc.h +++ b/ui/vnc.h @@ -143,6 +143,7 @@ struct VncDisplay char *password; int auth; bool lossy; + bool non_adaptive; #ifdef CONFIG_VNC_TLS int subauth; /* Used by VeNCrypt */ VncDisplayTLS tls; -- 1.7.3.2 ^ permalink raw reply related [flat|nested] 21+ messages in thread
* [Qemu-devel] Re: [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary ` (14 preceding siblings ...) 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 15/15] vnc: add a non-adaptive option Corentin Chary @ 2010-11-11 17:02 ` Alexander Graf 15 siblings, 0 replies; 21+ messages in thread From: Alexander Graf @ 2010-11-11 17:02 UTC (permalink / raw) To: Corentin Chary; +Cc: Anthony Liguori, Qemu-development List, Andre Przywara Corentin Chary wrote: > Hi, > > I rebased the series against current master, it contains: > > - Adaptive Tight Encoding: send lossy or lossless updates depending on the > update frequency of the screen region. If a lossy update is forced, then > it will be refreshed with a lossless update as soon as the update frequency > goes back to 0. > > - ZRLE/ZYWRLE Encodings: ZYWRLE use less bandwidth than tight, but the result > is also probably more lossy. I wanted to make ZRLE/ZYWRLE adaptive, but this > is not possible because most of the vnc clients can't switch between ZRLE and > ZYWRLE. But a possible solution is to use another encoding for lossless updates, > like zlib or tight. > > - Bitmap module: create bitmap.h and bitops.h, and remove duplicate code > from vnc.c > > It was my last series from GSoC 2010 context, if necessary I can send different > series for adaptive vnc, zrle and bitmap stuff. > Thanks a lot for doing this much during GSoC! Needless to say, we would all love to still have you around afterwards still, even without Google being involved :). Working with you was an amazing experience :). Alex ^ permalink raw reply [flat|nested] 21+ messages in thread
end of thread, other threads:[~2010-11-11 21:25 UTC | newest] Thread overview: 21+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2010-11-11 16:56 [Qemu-devel] [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 01/15] vnc: don't set the quality if lossy encoding are disabled Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 02/15] vnc: add a way to get the update frequency for a given region Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 03/15] vnc: refresh lossy rect after a given timeout Corentin Chary 2010-11-11 18:44 ` Blue Swirl 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 04/15] vnc: tight: use the update frequency to choose between lossy and lossless Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 05/15] vnc: palette: use a pool to reduce memory allocations Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 06/15] vnc: palette: add palette_init calls Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 07/15] vnc: palette: and fill and color calls Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 08/15] vnc: Add ZRLE and ZYWRLE encodings Corentin Chary 2010-11-11 18:58 ` Blue Swirl 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 09/15] vnc: fix uint8_t comparisons with negative values Corentin Chary 2010-11-11 16:56 ` [Qemu-devel] [PATCH v2 10/15] vnc: fix lossy rect refreshing Corentin Chary 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 11/15] bitmap: add a generic bitmap and bitops library Corentin Chary 2010-11-11 19:07 ` Blue Swirl 2010-11-11 21:25 ` Corentin Chary 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 12/15] vnc: use the new generic bitmap functions Corentin Chary 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 13/15] vnc: don't try to send bigger updates that client height Corentin Chary 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 14/15] vnc: tight: tweak adaptive tight settings Corentin Chary 2010-11-11 16:57 ` [Qemu-devel] [PATCH v2 15/15] vnc: add a non-adaptive option Corentin Chary 2010-11-11 17:02 ` [Qemu-devel] Re: [PATCH v2 00/15] vnc: adapative tight, zrle, zywrle, and bitmap module Alexander Graf
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).