From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([208.118.235.92]:49645) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Sm92G-0000ZE-Rc for qemu-devel@nongnu.org; Tue, 03 Jul 2012 15:45:26 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Sm92B-0005cS-Lm for qemu-devel@nongnu.org; Tue, 03 Jul 2012 15:45:20 -0400 Received: from mx1.redhat.com ([209.132.183.28]:55413) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Sm92B-0005bl-Bw for qemu-devel@nongnu.org; Tue, 03 Jul 2012 15:45:15 -0400 Message-ID: <4FF34BC1.5030604@redhat.com> Date: Tue, 03 Jul 2012 13:45:05 -0600 From: Eric Blake MIME-Version: 1.0 References: <1341323574-23206-1-git-send-email-owasserm@redhat.com> <1341323574-23206-4-git-send-email-owasserm@redhat.com> In-Reply-To: <1341323574-23206-4-git-send-email-owasserm@redhat.com> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="------------enig54ADE105C27CD2D6100782C8" Subject: Re: [Qemu-devel] [PATCH v14 03/13] Add XBZRLE documentation List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Orit Wasserman 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 This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig54ADE105C27CD2D6100782C8 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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 6= 9 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 =3D> 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? 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 --=20 Eric Blake eblake@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org --------------enig54ADE105C27CD2D6100782C8 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) Comment: Public key at http://people.redhat.com/eblake/eblake.gpg Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBCAAGBQJP80vBAAoJEKeha0olJ0Nq0TsIAI8cD6/r2usTiHz7dyWnxgt4 mVoSKm10zaHumhTGuLxooSSCdaKNGDUMLhcaCu5/9nal5ITBHE156aXHGqpUDH0N nPoHlULpkY9t7Adm9auJCt0uZ8aJfZtPy46tmropAT8ctf0Alvj++3KBITfXOzuT jl+yhCUl3dkzR5bX4NHn+UFqPTMxM1LSz9CAB2X6bSIibH+AO6PKsx3XjPbDIYLE zcYVmQCocY59L/LB0l8wvR8aSycy443x1xHBePP1/GHptJ7YMFpE1BjR14f30UnP pvBYGAVyRhagiIrvgS14mUCXsF1TPbbu/X63R3KxVkeL0OgNUhss4xrnpVhHTow= =H+5p -----END PGP SIGNATURE----- --------------enig54ADE105C27CD2D6100782C8--