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

[Anthony Liguori <anthony@codemonkey.ws>]

On 01/03/2012 09:34 AM, Orit Wasserman wrote:
> Signed-off-by: Orit Wasserman<owasserm@redhat.com>
> ---
>   arch_init.c |   58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>   1 files changed, 58 insertions(+), 0 deletions(-)
>
> diff --git a/arch_init.c b/arch_init.c
> index fdda277..426b34d 100644
> --- a/arch_init.c
> +++ b/arch_init.c
> @@ -139,6 +139,9 @@ typedef struct XBRLEHeader {
>       uint32_t xh_cksum;
>   } XBRLEHeader;
>
> +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen);
> +static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen);
> +
>   /***********************************************************/
>   /* XBRLE page cache implementation */
>   static CacheItem *cache_item_get(unsigned long pos, int item)
> @@ -277,6 +280,61 @@ static void cache_insert(unsigned long addr, uint8_t *pdata)
>       it->it_addr = addr;
>   }
>
> +/* 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;
> +}
> +
> +static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen)
> +{
> +    int d = 0, s;
> +
> +    for (s = 0; s<  slen-1; s += 2) {
> +        uint8_t ch_run = src[s];
> +        uint8_t ch = src[s+1];
> +        while (ch_run--) {
> +            if (d == dlen) {
> +                return -1;
> +            }
> +            dst[d] = ch;
> +            d++;
> +        }
> +    }
> +    return d;
> +}
> +
> +static void xor_encode(uint8_t *dst, uint8_t *src1, uint8_t *src2)
> +{
> +    int i;
> +
> +    for (i = 0; i<  TARGET_PAGE_SIZE; i++) {
> +        dst[i] = src1[i] ^ src2[i];
> +    }
> +}
> +

I don't think any of these need to be in arch_init.c.  It would be nicer to make 
a xbzrle.c file for this stuff.

Regards,

Anthony Liguori

>   static int is_dup_page(uint8_t *page, uint8_t ch)
>   {
>       uint32_t val = ch<<  24 | ch<<  16 | ch<<  8 | ch;