Re: [Qemu-devel] [PATCH v5 2/9] Add rle_encode and rle_decode functions Implement Run Length Encoding compression

[Avi Kivity <avi@redhat.com>]

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