From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([140.186.70.92]:58869) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RiQRe-0006Zv-U1 for qemu-devel@nongnu.org; Wed, 04 Jan 2012 07:59:58 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RiQRa-0006nj-Nd for qemu-devel@nongnu.org; Wed, 04 Jan 2012 07:59:54 -0500 Received: from mx1.redhat.com ([209.132.183.28]:25084) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RiQRa-0006nd-E0 for qemu-devel@nongnu.org; Wed, 04 Jan 2012 07:59:50 -0500 Message-ID: <4F044D41.5000200@redhat.com> Date: Wed, 04 Jan 2012 14:59:45 +0200 From: Avi Kivity MIME-Version: 1.0 References: <1325604879-15862-1-git-send-email-owasserm@redhat.com> <1325604879-15862-3-git-send-email-owasserm@redhat.com> In-Reply-To: <1325604879-15862-3-git-send-email-owasserm@redhat.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [PATCH v5 2/9] Add rle_encode and rle_decode functions Implement Run Length Encoding compression List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Orit Wasserman Cc: blauwirbel@gmail.com, stefanha@gmail.com, qemu-devel@nongnu.org, quintela@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