[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v5 2/9] Add rle_encode and rle_decode functions
From: |
Avi Kivity |
Subject: |
Re: [Qemu-devel] [PATCH v5 2/9] Add rle_encode and rle_decode functions Implement Run Length Encoding compression |
Date: |
Wed, 04 Jan 2012 14:59:45 +0200 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:8.0) Gecko/20111115 Thunderbird/8.0 |
On 01/03/2012 05:34 PM, Orit Wasserman wrote:
>
> +/* XBRLE (Xor Based Run-Length Encoding) */
> +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen)
> +{
> + int d = 0, ch_run = 0, i;
> + uint8_t prev = 0, ch = 0;
> +
> + for (i = 0; i <= slen; i++) {
> + if (i != slen) {
> + ch = src[i];
> + }
> +
> + if (!i || (i != slen && ch == prev && ch_run < 255)) {
> + ch_run++;
> + } else {
> + if (d+2 > dlen) {
> + return -1;
> + }
> + *dst++ = ch_run;
> + *dst++ = prev;
> + d += 2;
> + ch_run = 1;
> + }
> +
> + prev = ch;
> + }
> + return d;
> +}
> +
I think we should specialize this for out case, where we expect runs of
zeros (so no need to encode the repeated byte) and runs of non-repeating
nonzeros. I propose this encoding:
page = zrun
| zrun nzrun
| zrun nzrun page
zrun = length
nzrun = length byte...
length = uleb128 encoded integer
take for example a xor-encoded page:
{ 1000*0, 1, 2, 3, 4, 3092*0 }
representing a page that had a single 32-bit write in the middle. The
current encoding would generate
ff 00 ff 00 ff 00 eb 00 01 01 01 02 01 03 01 04 ff 00 ff 00 ff 00 ff
00 ff 00 ff 00ff 00 ff 00 ff 00 ff 00 ff 00 ff 00 20 00
while the zrle encoding generates
e8 07 04 01 02 03 04 94 18
(e8 07 = uleb128 encoding for 1000)
--
error compiling committee.c: too many arguments to function
- Re: [Qemu-devel] [PATCH v5 1/9] Add cache handling functions, (continued)
[Qemu-devel] [PATCH v5 3/9] Add save_block_hdr function, Orit Wasserman, 2012/01/03
[Qemu-devel] [PATCH v5 5/9] Add XBRLE to ram_save_block and ram_save_live, Orit Wasserman, 2012/01/03
[Qemu-devel] [PATCH v5 9/9] Add XBRLE statistics information, Orit Wasserman, 2012/01/03
[Qemu-devel] [PATCH v5 8/9] QMP commands changes, Orit Wasserman, 2012/01/03