From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([208.118.235.92]:45025) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SmKxo-0005Ty-Ek for qemu-devel@nongnu.org; Wed, 04 Jul 2012 04:29:44 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SmKxi-000462-HE for qemu-devel@nongnu.org; Wed, 04 Jul 2012 04:29:32 -0400 Received: from mx1.redhat.com ([209.132.183.28]:59368) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SmKxi-00044W-9a for qemu-devel@nongnu.org; Wed, 04 Jul 2012 04:29:26 -0400 Message-ID: <4FF3FEE9.2080501@redhat.com> Date: Wed, 04 Jul 2012 11:29:29 +0300 From: Orit Wasserman MIME-Version: 1.0 References: <1341323574-23206-1-git-send-email-owasserm@redhat.com> <1341323574-23206-4-git-send-email-owasserm@redhat.com> <4FF34BC1.5030604@redhat.com> In-Reply-To: <4FF34BC1.5030604@redhat.com> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [PATCH v14 03/13] Add XBZRLE documentation List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Eric Blake Cc: peter.maydell@linaro.org, aliguori@us.ibm.com, quintela@redhat.com, stefanha@gmail.com, qemu-devel@nongnu.org, mdroth@linux.vnet.ibm.com, blauwirbel@gmail.com, avi@redhat.com, pbonzini@redhat.com, chegu_vinod@hp.com On 07/03/2012 10:45 PM, Eric Blake wrote: > On 07/03/2012 07:52 AM, Orit Wasserman wrote: >> Signed-off-by: Orit Wasserman >> --- >> docs/xbzrle.txt | 133 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ >> 1 files changed, 133 insertions(+), 0 deletions(-) >> create mode 100644 docs/xbzrle.txt > >> + >> +Example >> +old buffer: >> +1000 zeros >> +05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 00 00 6b 00 6d >> +3072 zeros > > That's only 4092 bytes, but a page is typically 4096. I think you meant > 3076 trailing zeros. > >> + >> +new buffer: >> +1000 zeros >> +01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 00 00 67 00 69 >> +3702 zeros > > That's 4722 bytes; looks like a transposition error, and given the above > comment, I still think you want 3076 trailing zeros. > >> + >> +encoded buffer: >> + >> +encoded length 29 >> +e8 07 18 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 00 00 67 00 69 00 00 >> +00 80 18 > > Looks better, but still not quite accurate. Per the spec, you always > end on a nzrun, which means you should not have transmitted the last two > bytes (80 18 => 3072, which is the length of your trailing zrun). I > also find it weak that your example never shows an unchanged byte on > anything other than 00; having at least one non-zero unchanged byte may > make it more obvious in the encoded example that it is the xor > difference that determines a zrun vs. nzrun, and not the old or new > buffer contents. > > Also, reading that encoding says you have 1000 zrun, then 24 bytes of > nzrun starting with a leading 00, but based on your old and new buffer, > the only way to have a leading 00 in your nzrun is if you count a zrun > of 999 bytes. Are you sure you didn't test with a buffer of 1001 > leading zeros, then 20 bytes of interest, then 3073 trailing zeros? yes you are right 1001 zeros ... I fix it . > > Given your old and new buffer as-is, and my assumption that you are > compressing a page of exactly 4096 bytes (3076 trailing zeros after your > 20-byte window of interesting data), I see at least the following four > valid encodings, listed in increasing difficulty of computation: > > 8-byte long at a time; all chunks that differ in at least one byte are > treated as at least 8 bytes of nzrun, transmit 27 bytes > e8 07 18 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 00 00 67 00 69 00 > 00 00 00 > > 4 bytes at a time; all chunks that differ in at least one byte are > treated as at least 4 bytes of nzrun, transmit 23 bytes > e8 07 14 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 00 00 67 00 69 > > list every single zrun (except trailing), even if only one byte long, > transmit 24 bytes > e8 07 0f 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 02 01 67 01 01 69 > > avoid a 1-byte zrun, transmit 23 bytes > e8 07 0f 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 02 03 67 00 69 >