I wrote:
> Greg, give me until tomorrow to catch up and repolarize my neurons,
> then we can discuss what needs to be done and how to divide the work.
Well, tomorrow's long gone, but I've finally rewritten the vdelta generator!
This version is based on the algorithm Greg posted a while ago,
and also uses the hash trick. It correctly compresses the
"abcdxabcdabcdyabcdabcdabcdabcdabcdabcdz" example in Greg's mail.
Next steps:
1) Get the patches into CVS
2) Write vcdiff producer (text delta stream -> vcdiff stream)
3) Write vcdiff consumer (vcdiff stream -> text delta stream)
4) Write text delta patch (source stream + text delta stream -> target stream)
(1) needs to be done by someone with write access ...
Greg (Hudson -- too many Gregs on this list :-), we can split up the other
three tasks if you like. Take your pick, I don't really care which ones I
tackle.
Here are some of the things I had in mind for the vcdiff stuff:
- For now, only use reserved instruction table 0 (the one with
4-byte copies -- anything less than 4 bytes is nonsense for vdelta);
- Merge cross-boundary copies that were split in the delta window
when generating the vcdiff, and split them when consuming it;
- Scan long inserts for byte runs that may make the generated
vcdiff smaller;
- ...
It's possible that (2) and (3) can be done in parallel once the
basic common infrastructure is complete.
Brane
--
Branko Čibej <branko.cibej@hermes.si>
HERMES SoftLab, Litijska 51, 1000 Ljubljana, Slovenia
voice: (+386 1) 586 53 49 fax: (+386 1) 586 52 70
2000-09-11 Branko Cibej <branko.cibej@hermes.si>
Implement vdelta generator and test driver:
* include/svn_delta.h (svn_txdelta_window_t): New member ops_size.
* libsvn_delta/text_delta.c, libsvn_delta/vdelta.c: New files.
* libsvn_delta/Makefile.am: Add them to libsvn_delta_la_SOURCES.
* libsvn_delta/delta.h: Declare private interfaces for text deltas.
* libsvn_delta/tests/vdelta-test.c: New file.
* libsvn_delta/tests/Makefile.am: Add bits to build vdelta-test.
* libsvn_delta/tests/vdelta_1.txt: New testcase for vdelta-test.
Index: include/svn_delta.h
===================================================================
RCS file: /cvs/subversion/subversion/include/svn_delta.h,v
retrieving revision 1.83
diff -c -p -r1.83 svn_delta.h
*** include/svn_delta.h 2000/09/09 16:11:27 1.83
--- include/svn_delta.h 2000/09/11 07:32:01
*************** typedef struct svn_txdelta_window_t {
*** 138,143 ****
--- 138,146 ----
/* The number of instructions in this window. */
int num_ops;
+
+ /* The allocated size of the ops array. */
+ int ops_size;
/* The instructions for this window. */
svn_txdelta_op_t *ops;
Index: libsvn_delta/Makefile.am
===================================================================
RCS file: /cvs/subversion/subversion/libsvn_delta/Makefile.am,v
retrieving revision 1.8
diff -c -p -r1.8 Makefile.am
*** libsvn_delta/Makefile.am 2000/09/05 17:30:07 1.8
--- libsvn_delta/Makefile.am 2000/09/11 07:32:01
***************
*** 8,14 ****
lib_LTLIBRARIES = libsvn_delta.la
## Sources needed to build each library (names canonicalized)
! libsvn_delta_la_SOURCES = xml_parse.c vcdiff_parse.c
## Build flags ---------
--- 8,15 ----
lib_LTLIBRARIES = libsvn_delta.la
## Sources needed to build each library (names canonicalized)
! libsvn_delta_la_SOURCES = xml_parse.c vcdiff_parse.c \
! text_delta.c vdelta.c
## Build flags ---------
Index: libsvn_delta/delta.h
===================================================================
RCS file: /cvs/subversion/subversion/libsvn_delta/delta.h,v
retrieving revision 1.27
diff -c -p -r1.27 delta.h
*** libsvn_delta/delta.h 2000/09/08 21:30:03 1.27
--- libsvn_delta/delta.h 2000/09/11 07:32:01
***************
*** 61,66 ****
--- 61,93 ----
svn_error_t * svn_vcdiff_send_window (svn_vcdiff_parser_t *parser,
apr_size_t len);
+
+ /* Private interface for text deltas. */
+
+ /* Allocate and initalize a delta window. */
+ svn_error_t *svn_txdelta__init_window (svn_txdelta_window_t **window,
+ svn_txdelta_stream_t *stream);
+
+ /* Insert a delta op into the delta window. If the opcode is
+ svn_delta_new, bytes from new_data are copied into the window
+ data and offset is ignored, as it's maintained in the winfo struct.
+ Otherwise new_data is ignored and may be NULL. */
+ svn_error_t *svn_txdelta__insert_op (svn_txdelta_window_t *window,
+ int opcode,
+ apr_off_t offset,
+ apr_off_t length,
+ const char *new_data);
+
+ /* Create a vdelta window. Allocate temporary data from `pool'. */
+ svn_error_t *svn_txdelta__vdelta (svn_txdelta_window_t *window,
+ const char *const start,
+ apr_size_t source_len,
+ apr_size_t target_len,
+ apr_pool_t *pool);
+
+ /* The delta window size. */
+ extern apr_size_t svn_txdelta__window_size;
+
/* These are the in-memory tree-delta stackframes; they are used to
Index: libsvn_delta/tests/Makefile.am
===================================================================
RCS file: /cvs/subversion/subversion/libsvn_delta/tests/Makefile.am,v
retrieving revision 1.2
diff -c -p -r1.2 Makefile.am
*** libsvn_delta/tests/Makefile.am 2000/08/30 03:17:07 1.2
--- libsvn_delta/tests/Makefile.am 2000/09/11 07:32:01
***************
*** 1,7 ****
## Makefile.in is generated from this by automake.
! noinst_PROGRAMS = deltaparse-test
deltaparse_test_SOURCES = deltaparse-test.c
## Flags needed when compiling:
CFLAGS = -pthread
--- 1,8 ----
## Makefile.in is generated from this by automake.
! noinst_PROGRAMS = deltaparse-test vdelta-test
deltaparse_test_SOURCES = deltaparse-test.c
+ vdelta_test_SOURCES = vdelta-test.c
## Flags needed when compiling:
CFLAGS = -pthread
*************** deltaparse_test_LDADD = ../libsvn_delta.
*** 13,18 ****
--- 14,24 ----
../../libsvn_string/libsvn_string.la \
../../../apr/libapr.a \
../../../expat-lite/libexpat.la
+
+ vdelta_test_LDADD = ../libsvn_delta.la \
+ ../../libsvn_subr/libsvn_subr.la \
+ ../../libsvn_string/libsvn_string.la \
+ ../../../apr/libapr.a
## Automatic test scripts to run for `make check`
Received on Sat Oct 21 14:36:08 2006