From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Sun, 25 May 2008 22:30:39 +0400 From: Alexey Tourbin To: ALT Linux Team development discussions Message-ID: <20080525183039.GH7996@solemn.turbinal> Mail-Followup-To: ALT Linux Team development discussions References: <20080524142114.GI7750@solemn.turbinal> <6062a6e60805240751s4d30a9c4hc29e2232382dea1c@mail.gmail.com> <20080524153509.GK7750@solemn.turbinal> <6062a6e60805240853o254c656bi989903eef98417a6@mail.gmail.com> <20080525075404.GD7996@solemn.turbinal> <6062a6e60805250108w439e5ca6x4207e401dfb72e49@mail.gmail.com> <20080525081838.GE7996@solemn.turbinal> <6062a6e60805250131w7de349fqde0064d3e8a1d97d@mail.gmail.com> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="v2/QI0iRXglpx0hK" Content-Disposition: inline In-Reply-To: <6062a6e60805250131w7de349fqde0064d3e8a1d97d@mail.gmail.com> Subject: [devel] rsync_roll X-BeenThere: devel@lists.altlinux.org X-Mailman-Version: 2.1.10b3 Precedence: list Reply-To: ALT Linux Team development discussions List-Id: ALT Linux Team development discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 25 May 2008 18:27:51 -0000 Archived-At: List-Archive: List-Post: --v2/QI0iRXglpx0hK Content-Type: multipart/mixed; boundary="EemXnrF2ob+xzFeB" Content-Disposition: inline --EemXnrF2ob+xzFeB Content-Type: text/plain; charset=koi8-r Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sun, May 25, 2008 at 12:31:24PM +0400, Alexander Bokovoy wrote: > =F0=C1=D4=DE, =CB=CF=D4=CF=D2=D9=CA =C2=D2=C1=CC =D4=D9, =CF=CE =CF=D4=CC= =C9=DE=C1=C5=D4=D3=D1 =CF=D4 =D2=C5=CB=CF=CD=C5=CE=C4=D5=C5=CD=CF=C7=CF > http://ozlabs.org/~rusty/gzip.rsync.patch2, =CE=C1 =CB=CF=D4=CF=D2=D9=CA = =D3=D3=D9=CC=C1=C0=D4=D3=D1 =CB=C1=CB > =E4=D6=C5=C6=C6, =D4=C1=CB =C9 =FC=C7=CD=CF=CE=D4. =FE=D4=CF =C4=C5=CC=C1=C5=D4 =DC=D4=CF=D4 =D0=C1=D4=DE? =F0=CF=DE=C5=CD=D5= "=DC=D4=CF =D2=C1=C2=CF=D4=C1=C5=D4"? =F0=D2=CF=DB=D5 =D0=CF=C4=D3=CB=C1=DA=C1=D4=D8, =D0=D2=C1=D7=C9=CC=D8=CE=CF= =CC=C9 =D1 =D0=CF=CE=C9=CD=C1=C0 =DC=D4=CF =C4=C5=CC=CF =C9=CC=C9 =CE=C5= =D4. =FC=D4=CF=D4 =D0=C1=D4=DE =CF=D0=C5=D2=C9=D2=D5=C5=D4 =CE=C1 =D7=C8=CF=C4= =CE=CF=CD (=CE=C5=D3=D6=C1=D4=CF=CD) =D0=CF=D4=CF=CB=C5 =C2=C1=CA=D4=CF=D7 |---------------------------------------------------------> =F7=D9=DE=C9=D3=CC=D1=C5=D4=D3=D1 "=CB=CF=CE=D4=D2=CF=CC=D8=CE=C1=D1 =D3=D5= =CD=CD=C1" (=D3 =D0=C5=D2=C5=D0=CF=CC=CE=C5=CE=C9=C5=CD) "=CF=CB=CE=C1" =D2=C1=DA=CD=C5=D2=CF=CD RSYNC_WIN =C2=C1=CA=D4=CF=D7 =D7=C8=CF=C4=CE=CF=C7= =CF =D0=CF=D4=CF=CB=C1. |---------------------------------------------------------> |___________| RSYNC_WIN =F0=D2=C9 =C4=CF=C2=C1=D7=CC=C5=CE=C9=C9 =CB=C1=D6=C4=CF=C7=CF =CE=CF=D7=CF= =C7=CF =C2=C1=CA=D4=C1 =CF=CB=CE=CF "=D3=C4=D7=C9=C7=C1=C5=D4=D3=D1" =C9 = =D7=D9=DE=C9=D3=CC=D1=C5=D4=D3=D1 =CE=CF=D7=C1=D1 =D3=D5=CD=CD=C1. |---------------------------------------------------------> -|__________+| RSYNC_WIN =EF=D3=CF=C2=C5=CE=CE=CF=D3=D4=D8 =D7=D9=DE=C9=D3=CC=C5=CE=C9=D1 =DC=D4=CF= =CA =D3=D5=CD=CD=D9 =D3=CF=D3=D4=CF=C9=D4 =D7 =D4=CF=CD, =DE=D4=CF =C4=CF= =D3=D4=C1=D4=CF=DE=CE=CF =D7=D9=DE=C5=D3=D4=D8 =D3=D4=C1=D2=D9=CA "=D7=D9=C2=D9=D7=DB=C9=CA" =DC=CC= =C5=CD=C5=CE=D4 (=D3=CC=C5=D7=C1, =CF=D4=CD=C5=DE=C5=CE =DA=CE=C1=CB=CF=CD = =CD=C9=CE=D5=D3) =C9 =C4=CF=C2=C1=D7=C9=D4=D8 =CE=CF=D7=D9=CA =DC=CC=C5=CD=C5=CE=D4 (=CF=D4= =CD=C5=DE=C5=CE =DA=CE=C1=CB=CF=CD =D0=CC=C0=D3). =EB=CF=C7=C4=C1 =D3=D5=CD=CD=C1 =D0=D2=C9=CE=C9=CD=C1=C5=D4 =CF=D0=D2=C5=C4= =C5=CC=A3=CE=CE=CF=C5 =DA=CE=C1=DE=C5=CE=C9=C5 (=C1 =C9=CD=C5=CE=CE=CF, =CB= =CF=C7=C4=C1 sum % RSYNC_WIN =3D=3D 0) =D4=CF =D7 =CB=CF=CE=C3=C5 =CF=CB=CE=C1 =D0=D2=C9= =CE=C9=CD=C1=C5=D4=D3=D1 =D2=C5=DB=C5=CE=C9=C5 "=D3=C2=CF=D2=CF=D3=C9=D4=D8 =C2=CC=CF=CB" =C9 =DA=C1=CE=CF=D7=CF =C9=CE=C9= =C3=C9=C1=CC=C9=DA=C9=D2=CF=D7=C1=D4=D8 =D0=D2=CF=C3=C5=C4=D5=D2=D5 =D3=D6= =C1=D4=C9=D1. |---------------------------------------------------------> |_____0_____| RSYNC_WIN \ `reset compression here! =20 =FC=D4=CF =CF=DA=CE=C1=DE=C1=C5=D4, =DE=D4=CF =D7 =DC=D4=CF=CA =D4=CF=DE=CB= =C5 =CB=C1=CB =C2=D9 =CE=C1=DE=C9=CE=C1=C5=D4=D3=D1 "=CE=CF=D7=D9=CA =C6=C1= =CA=CC", =CB=CF=D4=CF=D2=D9=CA gzip =C2=D5=C4=C5=D4 =D6=C1=D4=D8 =CF=D4=C4=C5=CC=D8= =CE=CF; =C5=D3=CC=C9 =D7 =C4=D7=D5=C8 =D2=C1=DA=CE=D9=C8 =D7=C8=CF=C4=CE=D9= =C8 =D0=CF=D4=CF=CB=C1=C8 =D7 =D4=CF=DE=CB=C5 =CF=C2=CE=D5=CC=C5=CE=C9=D1 =D3= =D5=CD=CD=D9 =CE=C5=D3=D6=C1=D4=D9=C5 =C4=C1=CE=CE=D9=C5 =C9=C4=D5=D4 =CF= =C4=C9=CE=C1=CB=CF=D7=D9=C5, =D4=CF =C9 =D3=D6=C1=D4=D9=C5 =C4=C1=CE=CE=D9=C5 =D0=CF=CA=C4=D5=D4 =CF=C4= =C9=CE=C1=CB=CF=D7=D9=C5. =F1 =D7=D3=A3 =D2=C1=D7=CE=CF =D0=CC=CF=C8=CF =D0=CF=CE=C9=CD=C1=C0, =D0=CF= =DE=C5=CD=D5 "=DC=D4=CF =D2=C1=C2=CF=D4=C1=C5=D4", =D4=CF =C5=D3=D4=D8 =CB= =C1=CB =DC=D4=CF =D3=D0=CF=D3=CF=C2=D3=D4=D7=D5=C5=D4 =D0=CF=D7=D9=DB=C5=CE=C9=C0 rsyncabili= ty. =F4=C5=D0=C5=D2=D8 =C4=C1=CC=D8=DB=C5 =D7=CF=D0=D2=CF=D3, =DE=D4=CF =C4=C5= =CC=C1=C5=D4 gzip =D0=D2=C9 =CF=C2=CE=D5=CC=C5=CE=C9=C9 =D3=D5=CD=CD=D9? =EF=CE =D0=CF=CC=CE=CF=D3=D4=D8=C0 =DA=C1=D0=C9=D3=D9=D7=C1=C5=D4 =C2=CC=CF= =CB? =EE=CF =D7=C5=C4=D8 =CE=CF=D2=CD=C1=CC=D8=CE=D9=CA =D2=C1=DA=CD=C5=D2= =C2=CC=CF=CB=C1 32K, =C1 =D2=C1=DA=CD=C5=D2 =CF=CB=CE=C1 4K. =F0=CF=D3=CB=CF=CC=D8=CB=D5 =CC=C0= =C2=CF=C5 =DA=CE=C1=DE=C5=CE=C9=C5 =D3=D5=CD=CD=D9 =D0=CF =CD=CF=C4=D5=CC= =C0 4096 =CD=CF=D6=CE=CF =D3=DE=C9=D4=C1=D4=D8 =D2=C1=D7=CE=CF=D7=C5=D2=CF=D1=D4=CE= =D9=CD, =D4=CF, =D7=D9=C8=CF=C4=C9=D4, =DE=D4=CF =D7=CD=C5=D3=D4=CF =C2=CC= =CF=CB=C1 32K gzip =C2=D5=C4=C5=D4 =C4=C5=CC=C1=D4=D8 =C2=CC=CF=CB=C9 =D7 =D3=D2=C5=C4=CE= =C5=CD =D0=CF 4K. =E9=CC=C9 =CE=C5=D4? =FE=D4=CF=C2=D9 =D0=CF=CE=D1=D4=D8, =CB=C1=CB =D2=C1=C2=CF=D4=C5=D4 =DC=D4= =CF=D4 =CB=CF=C4, =CD=CE=C5 =CE=D5=D6=CE=CF =D0=C5=D2=C5-=D2=C5=C1=CC=C9=DA= =CF=D7=C1=D4=D8 =C5=C7=CF =C2=C5=DA =D0=D2=C9=D7=D1=DA=CB=C9 =CB =C7=DA=C9=D0=D5. =F1 =D0=D2=C9=CC= =CF=D6=C9=CC =C6=C1=CA=CC rsyncable.=D3, =D7 =CB=CF=D4=CF=D2=CF=CD =D0=CF= =D0=D9=D4=C1=CC=D3=D1 =D7=CF=D3=D0=D2=CF=C9=DA=D7=C5=D3=D4=C9 =D4=CF, =CF =DE=A3=CD =C9=C4=A3=D4 = =D2=C5=DE=D8. $ ./rsyncable #include #define RSYNC_WIN 4096 struct rsync_state { uint64_t n; /* number of elements in the window */ uint64_t sum; /* current sum */ unsigned char win[RSYNC_WIN]; /* window elements */ }; static inline bool rsync_next(struct rsync_state *s, unsigned char c) { if (s->n < RSYNC_WIN) { /* not enough elements */ s->sum += c; /* update the sum */ s->win[s->n++] = c; /* remember the element */ return false; /* no match */ } int i = s->n++ % RSYNC_WIN; /* wrap up */ s->sum -= s->win[i]; /* move the window on */ s->sum += c; s->win[i] = c; if (s->sum % RSYNC_WIN == 0) { /* match */ s->n = 0; /* reset */ s->sum = 0; return true; } return false; } #include int main() { struct rsync_state rs = { 0, 0 }; int c; while ((c = getc(stdin)) != EOF) if (rsync_next(&rs, c)) printf("sync at %ld\n", ftell(stdin)); return 0; } --EemXnrF2ob+xzFeB-- --v2/QI0iRXglpx0hK Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) iEYEARECAAYFAkg5sE4ACgkQfBKgtDjnu0bwUgCgqg3d7cDFuptBGg72ayqJtbIU GX4An2Xv/3oWLqJZboL3iPqoPLMdB1So =gFlz -----END PGP SIGNATURE----- --v2/QI0iRXglpx0hK--