diff options
Diffstat (limited to 'merge.cc')
| -rw-r--r-- | merge.cc | 158 |
1 files changed, 131 insertions, 27 deletions
@@ -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 ); |