From patchwork Tue Jan 3 15:34:32 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Orit Wasserman X-Patchwork-Id: 134030 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [140.186.70.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id DE026B6F9B for ; Wed, 4 Jan 2012 03:08:37 +1100 (EST) Received: from localhost ([::1]:51936 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ri6PX-0007c4-I9 for incoming@patchwork.ozlabs.org; Tue, 03 Jan 2012 10:36:23 -0500 Received: from eggs.gnu.org ([140.186.70.92]:34575) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ri6Oo-0005hI-AC for qemu-devel@nongnu.org; Tue, 03 Jan 2012 10:35:40 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Ri6Oi-0006x6-S0 for qemu-devel@nongnu.org; Tue, 03 Jan 2012 10:35:38 -0500 Received: from mx1.redhat.com ([209.132.183.28]:54243) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ri6Oi-0006wv-LV for qemu-devel@nongnu.org; Tue, 03 Jan 2012 10:35:32 -0500 Received: from int-mx12.intmail.prod.int.phx2.redhat.com (int-mx12.intmail.prod.int.phx2.redhat.com [10.5.11.25]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id q03FZUBO014212 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Tue, 3 Jan 2012 10:35:30 -0500 Received: from dhcp-1-120.tlv.redhat.com (vpn-202-200.tlv.redhat.com [10.35.202.200]) by int-mx12.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id q03FZNnv003527; Tue, 3 Jan 2012 10:35:29 -0500 From: Orit Wasserman To: qemu-devel@nongnu.org Date: Tue, 3 Jan 2012 17:34:32 +0200 Message-Id: <1325604879-15862-3-git-send-email-owasserm@redhat.com> In-Reply-To: <1325604879-15862-1-git-send-email-owasserm@redhat.com> References: <1325604879-15862-1-git-send-email-owasserm@redhat.com> X-Scanned-By: MIMEDefang 2.68 on 10.5.11.25 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 209.132.183.28 Cc: blauwirbel@gmail.com, stefanha@gmail.com, Orit Wasserman , quintela@redhat.com Subject: [Qemu-devel] [PATCH v5 2/9] Add rle_encode and rle_decode functions Implement Run Length Encoding compression X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Signed-off-by: Orit Wasserman --- 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]; + } +} + static int is_dup_page(uint8_t *page, uint8_t ch) { uint32_t val = ch << 24 | ch << 16 | ch << 8 | ch;