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

[Anthony Liguori]

On 01/03/2012 09:34 AM, Orit Wasserman wrote:
Signed-off-by: Orit Wasserman<owass...@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;