Patchwork [v5,2/9] Add rle_encode and rle_decode functions Implement Run Length Encoding compression

login
register
mail settings
Submitter Orit Wasserman
Date Jan. 3, 2012, 3:34 p.m.
Message ID <1325604879-15862-3-git-send-email-owasserm@redhat.com>
Download mbox | patch
Permalink /patch/134030/
State New
Headers show

Comments

Orit Wasserman - Jan. 3, 2012, 3:34 p.m.
Signed-off-by: Orit Wasserman <owasserm@redhat.com>
---
 arch_init.c |   58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 58 insertions(+), 0 deletions(-)
Anthony Liguori - Jan. 3, 2012, 7:57 p.m.
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;
Orit Wasserman - Jan. 4, 2012, 9:31 a.m.
On 01/03/2012 09:57 PM, Anthony Liguori wrote:
> 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.
> 

I will fix it.

> Regards,
> 
> Anthony Liguori
> 
>>   static int is_dup_page(uint8_t *page, uint8_t ch)
>>   {
>>       uint32_t val = ch<<  24 | ch<<  16 | ch<<  8 | ch;
> 
>
Avi Kivity - Jan. 4, 2012, 12:59 p.m.
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)
Stefan Hajnoczi - Jan. 4, 2012, 1:35 p.m.
On Wed, Jan 4, 2012 at 12:59 PM, Avi Kivity <avi@redhat.com> wrote:
> 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)

Had to look up the Unsigned Little-Endian Base 128 encoding, but it's
a nice idea and simple to implement (though we probably want to
constrain ULEB128 to max 32-bit or 64-bit in practice; we don't want
arbitrarily long integers).

http://en.wikipedia.org/wiki/LEB128

Stefan
Avi Kivity - Jan. 4, 2012, 1:45 p.m.
On 01/04/2012 03:35 PM, Stefan Hajnoczi wrote:
> > 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)
>
> Had to look up the Unsigned Little-Endian Base 128 encoding, but it's
> a nice idea and simple to implement (though we probably want to
> constrain ULEB128 to max 32-bit or 64-bit in practice; we don't want
> arbitrarily long integers).
>
> http://en.wikipedia.org/wiki/LEB128
>

Sorry, should have provided the URL.  And yes, for this use we're
limited to TARGET_PAGE_BITS, so having 13-bit encoders/decoders would
suffice:

   int uleb128_encode_small(uint8_t *out, uint32_t n)
   {
       if (n < 0x80) {
           *out++ = n;
           return 1;
       } else {
           *out++ = (n & 0x7f) | 0x80;
           *out++ = n >> 7;
       }
   }

   int uleb128_decode_small(const uint128 *in, uint32_t *n)
   {
       if (!(*in & 0x80)) {
           *n = *in++;
           return 1;
       } else {
           *n = *in++ & 0x7f;
           *n |= *in++ << 7;
           return 2;
       }
   }
Paolo Bonzini - Jan. 4, 2012, 4:52 p.m.
On 01/04/2012 10:31 AM, Orit Wasserman wrote:
>> >  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.
>> >
> I will fix it.
>

Or just move everything migration-related from arch_init.c to saveram.c.

Paolo

Patch

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];
+    }
+}
+
 static int is_dup_page(uint8_t *page, uint8_t ch)
 {
     uint32_t val = ch << 24 | ch << 16 | ch << 8 | ch;