-
-
-// These difference routines are straight out of the Heroinediff/Heroinepatch
-// utilities.
-
-
-// We didn't want to use the diff program because that isn't efficient enough
-// to compress EDL's. This program also handles binary data.
-
-// Algorithm 1:
-// Search from beginning for first difference.
-// Count everything up to first difference as equal.
-// Determine length of different block by searching for transposition with most
-// similar characters.
-// For every byte in different block, search for occurrence of
-// transposed copy longer than a record header in remaining old buffer.
-// If no match is found, add 1 to the different block length and try the next
-// byte. Once the most similar match is found, store the changed data leading up to it in the
-// difference record.
-// This can be real slow if there is a large transposition early in the file.
-
-// Algorithm 2:
-// Search backwards from end of both files for last difference.
-// Count all data from last same bytes as a transposition.
-// Search forwards from start of both files until last same bytes
-// for differences.
-
-
-// Minimum size of transposed block.
-// Smaller transpositions should be included in the same difference record.
-#define MIN_TRANS 16
-
-// Format for difference records.
-// The first 4 bytes are the offset of the change.
-// The next 4 bytes are the number of bytes of new data.
-// The next 4 bytes are the number of bytes of old data replaced.
-// The new data follows.
-static void append_record(unsigned char **result,
- int *result_size,
- unsigned char *new_data,
- int new_offset,
- int new_size,
- int old_size)
-{
- if( new_size || old_size ) {
- int record_size = new_size + 12;
- unsigned char *new_result = new unsigned char[(*result_size) + record_size];
- memcpy(new_result, (*result), (*result_size));
- delete [] (*result);
-
- unsigned char *new_result_ptr = new_result + (*result_size);
- *(int32_t*)new_result_ptr = new_offset;
- new_result_ptr += 4;
- *(int32_t*)new_result_ptr = new_size;
- new_result_ptr += 4;
- *(int32_t*)new_result_ptr = old_size;
- new_result_ptr += 4;
-
- memcpy(new_result_ptr, new_data, new_size);
- (*result_size) += record_size;
- (*result) = new_result;
- }
-}
-
-
-
-static unsigned char* get_difference_fast(unsigned char *before,
- int before_len,
- unsigned char *after,
- int after_len,
- int *result_len,
- int verbose)
-{
- unsigned char *result = new unsigned char[4];
- *result_len = 4;
-
-// Store size of new buffer
- *(int32_t*)result = after_len;
-
-
-
-// Get last different bytes
- unsigned char *last_difference_after = after + after_len - 1;
- unsigned char *last_difference_before = before + before_len - 1;
- for(;;) {
- if( last_difference_after < after ||
- last_difference_before < before ) break;
- if( *last_difference_after != *last_difference_before ) {
- break;
- }
- last_difference_after--;
- last_difference_before--;
- }
- last_difference_after++;
- last_difference_before++;
-
- int done = 0;
- unsigned char *before_ptr = before;
- unsigned char *after_ptr = after;
- unsigned char *before_end = before + before_len;
- unsigned char *after_end = after + after_len;
-
-// Scan forward for first difference
- while( !done ) {
- if( before_ptr < before_end &&
- after_ptr < after_end ) {
-// Both characters equal
- if( *before_ptr == *after_ptr &&
- before_ptr < last_difference_before &&
- after_ptr < last_difference_after ) {
- before_ptr++;
- after_ptr++;
- }
- else {
-// Characters differ
-// Get length of difference.
- unsigned char *before_difference_start = before_ptr;
- unsigned char *after_difference_start = after_ptr;
-
-
- while( *before_ptr != *after_ptr &&
- before_ptr < last_difference_before &&
- after_ptr < last_difference_after ) {
- before_ptr++;
- after_ptr++;
- }
-
-// Finished comparing if either pointer hits its last difference
- if( before_ptr >= last_difference_before ||
- after_ptr >= last_difference_after ) {
- done = 1;
- before_ptr = last_difference_before;
- after_ptr = last_difference_after;
- }
-
- int after_start = after_difference_start - after;
- int before_start = before_difference_start - before;
- int after_len = after_ptr - after_difference_start;
- int before_len = before_ptr - before_difference_start;
-
- if( verbose ) {
- char string[1024];
- memcpy(string, after_difference_start, MIN(after_len, 40));
- string[MIN(after_len, 40)] = 0;
- printf("after_offset=0x%x before_offset=0x%x after_size=%d before_size=%d \"%s\"\n",
- after_start, before_start, after_len, before_len, string);
- }
-
-// Create difference record
- append_record(&result, result_len, after_difference_start,
- after_start, after_len, before_len);
- }
- }
- else
- done = 1;
- }
- return result;
-}
-
-static void get_record(unsigned char **patch_ptr, unsigned char *patch_end,
- unsigned char **after_data, int *after_offset, int *after_size, int *before_size)
-{
- (*after_data) = 0;
- if( (*patch_ptr) < patch_end ) {
- (*after_offset) = *(int32_t*)(*patch_ptr); (*patch_ptr) += 4;
- (*after_size) = *(int32_t*)(*patch_ptr); (*patch_ptr) += 4;
- (*before_size) = *(int32_t*)(*patch_ptr); (*patch_ptr) += 4;
- (*after_data) = (*patch_ptr); (*patch_ptr) += (*after_size);
- }
-}
-