summaryrefslogtreecommitdiffstats
path: root/merge.cc
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--merge.cc158
1 files changed, 131 insertions, 27 deletions
diff --git a/merge.cc b/merge.cc
index 2f1afdc..01a273c 100644
--- a/merge.cc
+++ b/merge.cc
@@ -1,5 +1,5 @@
/* Lziprecover - Data recovery tool for the lzip format
- Copyright (C) 2009-2016 Antonio Diaz Diaz.
+ Copyright (C) 2009-2017 Antonio Diaz Diaz.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -37,6 +37,12 @@
namespace {
+bool pending_newline = false;
+
+void print_pending_newline()
+ { if( pending_newline ) std::fputc( '\n', stdout ); pending_newline = false; }
+
+
bool file_crc( uint32_t & crc, const int infd )
{
const int buffer_size = 65536;
@@ -100,6 +106,7 @@ void combine( std::vector< Block > & block_vector, std::vector< Block > & bv )
// positions in 'block_vector' are absolute file positions.
+// blocks in 'block_vector' are ascending and don't overlap.
bool diff_member( const long long mpos, const long long msize,
const std::vector< int > & infd_vector,
std::vector< Block > & block_vector,
@@ -224,7 +231,7 @@ int open_input_files( const std::vector< std::string > & filenames,
for( int i = 0; i < files; ++i )
{
long long tmp;
- const File_index fi( infd_vector[i] );
+ const File_index fi( infd_vector[i], true, true );
if( fi.retval() == 0 ) // file format is intact
{
if( good_fi < 0 ) { good_fi = i; file_index = fi; }
@@ -283,6 +290,92 @@ int open_input_files( const std::vector< std::string > & filenames,
}
+void maybe_cluster_blocks( std::vector< Block > & block_vector,
+ const int verbosity )
+ {
+ const unsigned long old_size = block_vector.size();
+ if( old_size <= 16 ) return;
+ do {
+ int min_gap = INT_MAX;
+ bool same = true; // all gaps have the same size
+ for( unsigned i = 1; i < block_vector.size(); ++i )
+ {
+ const long long gap = block_vector[i].pos() - block_vector[i-1].end();
+ if( gap < min_gap )
+ { if( min_gap < INT_MAX ) same = false; min_gap = gap; }
+ else if( gap != min_gap ) same = false;
+ }
+ if( min_gap >= INT_MAX || same ) break;
+ for( unsigned i = block_vector.size() - 1; i > 0; --i )
+ {
+ const long long gap = block_vector[i].pos() - block_vector[i-1].end();
+ if( gap == min_gap )
+ {
+ block_vector[i-1].size( block_vector[i-1].size() + gap +
+ block_vector[i].size() );
+ block_vector.erase( block_vector.begin() + i );
+ }
+ }
+ } while( block_vector.size() > 16 );
+ if( verbosity >= 1 && old_size > block_vector.size() )
+ std::printf( " %lu errors have been grouped in %lu clusters.\n",
+ old_size, (long)block_vector.size() );
+ }
+
+
+bool color_done( const std::vector< int > & color_vector, const int i )
+ {
+ for( int j = i - 1; j >= 0; --j )
+ if( color_vector[j] == color_vector[i] ) return true;
+ return false;
+ }
+
+
+ // try dividing blocks in 2 color groups at every gap
+bool try_merge_member2( const long long mpos, const long long msize,
+ const std::vector< Block > & block_vector,
+ const std::vector< int > & color_vector,
+ const std::vector< int > & infd_vector,
+ const int verbosity )
+ {
+ const int blocks = block_vector.size();
+ const int files = infd_vector.size();
+ const int variations = files * ( files - 1 );
+
+ for( int i1 = 0; i1 < files; ++i1 )
+ for( int i2 = 0; i2 < files; ++i2 )
+ {
+ if( i1 == i2 || color_vector[i1] == color_vector[i2] ||
+ color_done( color_vector, i1 ) ) continue;
+ for( int bi = 0; bi < blocks; ++bi )
+ if( !safe_seek( infd_vector[i2], block_vector[bi].pos() ) ||
+ !safe_seek( outfd, block_vector[bi].pos() ) ||
+ !copy_file( infd_vector[i2], outfd, block_vector[bi].size() ) )
+ cleanup_and_fail( 1 );
+ const int infd = infd_vector[i1];
+ const int var = ( i1 * ( files - 1 ) ) + i2 - ( i2 > i1 ) + 1;
+ for( int bi = 0; bi + 1 < blocks; ++bi )
+ {
+ if( verbosity >= 2 )
+ {
+ std::printf( " Trying variation %d of %d, block %d \r",
+ var, variations, bi + 1 );
+ std::fflush( stdout ); pending_newline = true;
+ }
+ if( !safe_seek( infd, block_vector[bi].pos() ) ||
+ !safe_seek( outfd, block_vector[bi].pos() ) ||
+ !copy_file( infd, outfd, block_vector[bi].size() ) ||
+ !safe_seek( outfd, mpos ) )
+ cleanup_and_fail( 1 );
+ long long failure_pos = 0;
+ if( test_member_from_file( outfd, msize, &failure_pos ) ) return true;
+ if( mpos + failure_pos < block_vector[bi].end() ) break;
+ }
+ }
+ return false;
+ }
+
+
// merge block by block
bool try_merge_member( const long long mpos, const long long msize,
const std::vector< Block > & block_vector,
@@ -306,13 +399,13 @@ bool try_merge_member( const long long mpos, const long long msize,
while( bi >= 0 )
{
- if( verbosity >= 1 )
+ if( verbosity >= 2 )
{
long var = 0;
for( int i = 0; i < blocks; ++i )
var = ( var * files ) + file_idx[i];
- std::printf( "Trying variation %ld of %ld \r", var + 1, variations );
- std::fflush( stdout );
+ std::printf( " Trying variation %ld of %ld \r", var + 1, variations );
+ std::fflush( stdout ); pending_newline = true;
}
while( bi < blocks )
{
@@ -330,14 +423,8 @@ bool try_merge_member( const long long mpos, const long long msize,
while( bi > 0 && mpos + failure_pos < block_vector[bi-1].pos() ) --bi;
while( --bi >= 0 )
{
- while( ++file_idx[bi] < files )
- {
- const int color = color_vector[file_idx[bi]];
- bool done = true;
- for( int i = file_idx[bi] - 1; i >= 0; --i )
- if( color_vector[i] == color ) { done = false; break; }
- if( done ) break;
- }
+ while( ++file_idx[bi] < files &&
+ color_done( color_vector, file_idx[bi] ) );
if( file_idx[bi] < files ) break;
file_idx[bi] = 0;
}
@@ -363,7 +450,8 @@ bool try_merge_member1( const long long mpos, const long long msize,
for( int i1 = 0; i1 < files; ++i1 )
for( int i2 = 0; i2 < files; ++i2 )
{
- if( i1 == i2 || color_vector[i1] == color_vector[i2] ) continue;
+ if( i1 == i2 || color_vector[i1] == color_vector[i2] ||
+ color_done( color_vector, i1 ) ) continue;
const int infd = infd_vector[i1];
if( !safe_seek( infd, pos ) ||
!safe_seek( infd_vector[i2], pos ) ||
@@ -371,13 +459,13 @@ bool try_merge_member1( const long long mpos, const long long msize,
!copy_file( infd_vector[i2], outfd, size ) )
cleanup_and_fail( 1 );
const int var = ( i1 * ( files - 1 ) ) + i2 - ( i2 > i1 ) + 1;
- for( long long i = 0; i < size; ++i )
+ for( long long i = 0; i + 1 < size; ++i )
{
- if( verbosity >= 1 )
+ if( verbosity >= 2 )
{
- std::printf( "Trying variation %d of %d, position %lld \r",
+ std::printf( " Trying variation %d of %d, position %lld \r",
var, variations, pos + i );
- std::fflush( stdout );
+ std::fflush( stdout ); pending_newline = true;
}
if( !safe_seek( outfd, pos + i ) ||
readblock( infd, &byte, 1 ) != 1 ||
@@ -471,6 +559,7 @@ int merge_files( const std::vector< std::string > & filenames,
const long long msize = file_index.mblock( j ).size();
// vector of data blocks differing among the copies of the current member
std::vector< Block > block_vector;
+ // different color means members are different
std::vector< int > color_vector( files, 0 );
if( !diff_member( mpos, msize, infd_vector, block_vector, color_vector ) ||
!safe_seek( outfd, mpos ) )
@@ -480,31 +569,46 @@ int merge_files( const std::vector< std::string > & filenames,
{
if( file_index.members() > 1 && test_member_from_file( outfd, msize ) )
continue;
- show_error( "Input files are (partially) identical. Merging is not possible." );
+ if( verbosity >= 0 )
+ std::fprintf( stderr, "Member %ld is damaged and identical in all files."
+ " Merging is not possible.\n", j + 1 );
cleanup_and_fail( 2 );
}
- if( verbosity >= 1 && file_index.members() > 1 )
+ if( verbosity >= 2 )
{
- std::printf( "Merging member %ld of %ld\n",
- j + 1, file_index.members() );
+ std::printf( "Merging member %ld of %ld (%lu error%s)\n",
+ j + 1, file_index.members(), (long)block_vector.size(),
+ ( block_vector.size() == 1 ) ? "" : "s" );
std::fflush( stdout );
}
bool done = false;
if( file_index.members() > 1 || block_vector.size() > 1 )
{
- done = try_merge_member( mpos, msize, block_vector, color_vector,
- infd_vector, verbosity );
- if( !done && verbosity >= 1 ) std::fputc( '\n', stdout );
+ if( block_vector.size() > 1 )
+ {
+ maybe_cluster_blocks( block_vector, verbosity );
+ done = try_merge_member2( mpos, msize, block_vector, color_vector,
+ infd_vector, verbosity );
+ print_pending_newline();
+ }
+ if( !done )
+ {
+ done = try_merge_member( mpos, msize, block_vector, color_vector,
+ infd_vector, verbosity );
+ print_pending_newline();
+ }
}
if( !done )
+ {
done = try_merge_member1( mpos, msize, block_vector, color_vector,
infd_vector, verbosity );
- if( verbosity >= 1 ) std::fputc( '\n', stdout );
+ print_pending_newline();
+ }
if( !done )
{
- if( verbosity >= 2 )
+ if( verbosity >= 3 )
for( unsigned i = 0; i < block_vector.size(); ++i )
std::fprintf( stderr, "area %2d from position %6lld to %6lld\n", i + 1,
block_vector[i].pos(), block_vector[i].end() - 1 );