On Sat, Jan 1, 2011 at 9:33 PM, <stef...@apache.org> wrote: > Author: stefan2 > Date: Sat Jan 1 20:33:22 2011 > New Revision: 1054286 > > URL: http://svn.apache.org/viewvc?rev=1054286&view=rev > Log: > XDelta calculation is major part of svn_txdelta_send_txstream. > Therefore, speed up string matching code and the relatively > expensive hash-code (adler32) calculations. > > * subversion/libsvn_delta/xdelta.c > (init_adler32): init adler checksum with 0 instead of 1; > use svn_adler32 for performance > (adler32_out): "-1" can / must be ommitted now that we > start at 0 instead of 1 for s1. > (adler32_replace): special, faster implementation replacing > a adler32_out(), adler32_in() sequence > > (match_length): new utility function > (find_match): speed up the main loop by calling match_length() > (compute_delta): optimize adler32 calculations > > Modified: > subversion/trunk/subversion/libsvn_delta/xdelta.c > > Modified: subversion/trunk/subversion/libsvn_delta/xdelta.c > URL: > http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_delta/xdelta.c?rev=1054286&r1=1054285&r2=1054286&view=diff > ============================================================================== > --- subversion/trunk/subversion/libsvn_delta/xdelta.c (original) > +++ subversion/trunk/subversion/libsvn_delta/xdelta.c Sat Jan 1 20:33:22 2011 > @@ -29,6 +29,8 @@ > > #include "svn_delta.h" > #include "delta.h" > + > +#include "private/svn_adler32.h" > > /* This is pseudo-adler32. It is adler32 without the prime modulus. > The idea is borrowed from monotone, and is a translation of the C++ > @@ -39,6 +41,10 @@ > #define ADLER32_MASK 0x0000ffff > #define ADLER32_CHAR_MASK 0x000000ff > > +/* Size of the blocks we compute checksums for. This was chosen out of > + thin air. Monotone used 64, xdelta1 used 64, rsync uses 128. */ > +#define MATCH_BLOCKSIZE 64 > + > /* Structure to store the state of our adler32 checksum. */ > struct adler32 > { > @@ -66,11 +72,32 @@ adler32_out(struct adler32 *ad, const ch > { > ad->s1 -= ((apr_uint32_t) (c)) & ADLER32_CHAR_MASK; > ad->s1 &= ADLER32_MASK; > - ad->s2 -= (ad->len * (((apr_uint32_t) c) & ADLER32_CHAR_MASK)) + 1; > + ad->s2 -= (ad->len * (((apr_uint32_t) c) & ADLER32_CHAR_MASK)); > ad->s2 &= ADLER32_MASK; > --ad->len; > } > > +/* Feed C_IN into the adler32 checksum and remove C_OUT at the same time. > + * This function may (and will) only be called for > + * ad->len == MATCH_BLOCKSIZE. > + */ > +static APR_INLINE void > +adler32_replace(struct adler32 *ad, const char c_out, const char c_in) > +{ > + apr_uint32_t s1 = ad->s1; > + apr_uint32_t s2 = ad->s2; > + > + s2 -= (MATCH_BLOCKSIZE * (((apr_uint32_t) c_out) & ADLER32_CHAR_MASK)); > + > + s1 -= ((apr_uint32_t) (c_out)) & ADLER32_CHAR_MASK; > + s1 += ((apr_uint32_t) (c_in)) & ADLER32_CHAR_MASK; > + > + s2 += s1; > + > + ad->s1 = s1 & ADLER32_MASK; > + ad->s2 = s2 & ADLER32_MASK; > +} > + > /* Return the current adler32 checksum in the adler32 structure. */ > > static APR_INLINE apr_uint32_t > @@ -85,18 +112,15 @@ adler32_sum(const struct adler32 *ad) > static APR_INLINE struct adler32 * > init_adler32(struct adler32 *ad, const char *data, apr_uint32_t datalen) > { > - ad->s1 = 1; > - ad->s2 = 0; > - ad->len = 0; > - while (datalen--) > - adler32_in(ad, *(data++)); > + apr_uint32_t adler32 = svn__adler32(0, data, datalen); > + > + ad->s1 = adler32 & ADLER32_MASK; > + ad->s2 = (adler32 >> 16) & ADLER32_MASK; > + ad->len = datalen; > + > return ad; > } > > -/* Size of the blocks we compute checksums for. This was chosen out of > - thin air. Monotone used 64, xdelta1 used 64, rsync uses 128. */ > -#define MATCH_BLOCKSIZE 64 > - > /* Information for a block of the delta source. The length of the > block is the smaller of MATCH_BLOCKSIZE and the difference between > the size of the source data and the position of this block. */ > @@ -201,6 +225,35 @@ init_blocks_table(const char *data, > } > } > > +/* Return the lowest position at which A and B differ. If no difference > + * can be found in the first MAX_LEN characters, MAX_LEN will be returned. > + */ > +static apr_size_t > +match_length(const char *a, const char *b, apr_size_t max_len) > +{ > + apr_size_t pos = 0; > + > +#if SVN_UNALIGNED_ACCESS_IS_OK > + > + /* Chunky operation is so much faster ... > + * > + * We can't make this work on architectures that require aligned access > + * because A and B will probably have different alignment. So, skipping > + * the first few chars until alignment is reached is not an option. > + */ > + for (; pos + sizeof(apr_size_t) <= max_len; pos += sizeof(apr_size_t)) > + if (*(const apr_size_t*)(a + pos) != *(const apr_size_t*)(b + pos)) > + break; > + > +#endif > + > + for (; pos < max_len; ++pos) > + if (a[pos] != b[pos]) > + break; > + > + return pos; > +} > + > /* Try to find a match for the target data B in BLOCKS, and then > extend the match as long as data in A and B at the match position > continues to match. We set the position in a we ended up in (in > @@ -229,6 +282,8 @@ find_match(const struct blocks *blocks, > apr_uint32_t sum = adler32_sum(rolling); > apr_size_t alen, badvance, apos; > apr_size_t tpos, tlen; > + apr_size_t delta, max_delta; > + const char *aptr, *bptr;
..\..\..\subversion\libsvn_delta\xdelta.c(286): warning C4101: 'aptr' : unreferenced local variable ..\..\..\subversion\libsvn_delta\xdelta.c(286): warning C4101: 'bptr' : unreferenced local variable -- Johan
