find a pattern in binary file

[vizzz]

Hi there,
i need to find an hex pattern like 0x650A1010 in a binary file.
i can make a small algorithm that fetch all the file for the match,
but this file is huge, and i'm scared about performances.
Is there any stl method for a fast search?
Andrea

[vizzz]

On 21 Giu, 12:26, James Kanze <james.ka...@gm ail.comwrote:

On Jun 21, 3:59 am, "Eric Pruneau" <eric.prun...@c gocable.cawrote :

"vizzz" <andrea.visin.. [e-mail] écrit dans le message de news:
aad55897-6560-4fd7-ae4f-5b8cc810f...@a7 0g2000hsh.googl egroups.com...

i need to find an hex pattern like 0x650A1010 in a binary file.
i can make a small algorithm that fetch all the file for the match,
but this file is huge, and i'm scared about performances.
Is there any stl method for a fast search?
Andrea

Check out *boost::regex

Which requires a forward iterator, and so can't be used on data
in a file (for which he'll have at best an input iterator).

Also, if he's only looking for a fixed string, it's likely to be
significantly slower than some other algorithms.

Maybe explaining my goal can be useful.
in jpeg2000 files (jp2) there are several boxes made of 4byte length,
4byte type and then data.
i must check if box exist by searching somewhere in the file (boxes
can be anywhere in the whole file) for the box type (ex 0x650A1010).

[Kai-Uwe Bux]

James Kanze wrote:

On Jun 21, 2:13 am, Kai-Uwe Bux <jkherci...@gmx .netwrote:

>Ivan wrote:

On Jun 20, 1:11 pm, vizzz <andrea.visin.. [e-mail] e:

Hmmm... I had a look at this and ran accross a simple
problem. How do you read a binary file and just echo the
HEX for byte to the screen.

[snip]

The issue is the c++ read function doesn't return number of
bytes read... so on the last read into a buffer how do you
know how many characters to print?

>Have a look at readsome().

Yes, have a look at it. Read it's specification very carefully.
Because if you do, you're realize that it is absolutely
worthless here.

I reread it again. I fail to see why it's worthless. Obviously, I am missing
something.

The function he's looking for is istream::gcount (), which
returns the number of bytes read by the last unformatted read.
His basic loop would be:

while ( input.read( &buffer[ 0 ], buffer.size() ) ) {
process( buffer.begin(), buffer.end() ) ;
}
process( buffer.begin(), buffer.begin() + input.gcount() ) ;

On the other hand, that looks very clean.
Best

Kai-Uwe

[Mirco Wahab]

vizzz wrote:

Maybe explaining my goal can be useful.
in jpeg2000 files (jp2) there are several boxes made of 4byte length,
4byte type and then data.
i must check if box exist by searching somewhere in the file (boxes
can be anywhere in the whole file) for the box type (ex 0x650A1010).

What is the largest file size and on which system
do you want this to happen?

The C-memchr is, on modern compilers, very very
fast (it does 8 byte alignment on the pointer,
scans 32 or 64 bit at a time by bit ops and so on.)

You can't simply beat that one. Read the file
as a block (fread after stat(), ftell/SEEK_END)
or in chunks and find the first byte (and compare
the rest).

Otherwise, you could give memcmp() a shot
http://www.cplusplus.com/reference/c...ng/memcmp.html
maybe its optimized as hard as memchr() is.
I didn't look into this but know from memchr()
it would get about double speed compared to the
naive implementation: if(*p == *q) ...

But if you can't slurp the whole file at
once into memory, you have of course to
deal with the possibility of broken pattern
across the read block boundary.

Regards

M.

[Kai-Uwe Bux]

James Kanze wrote:

On Jun 21, 2:13 am, Kai-Uwe Bux <jkherci...@gmx .netwrote:

>Ivan wrote:

On Jun 20, 1:11 pm, vizzz <andrea.visin.. [e-mail] e:

Hmmm... I had a look at this and ran accross a simple
problem. How do you read a binary file and just echo the
HEX for byte to the screen.

>#include <iostream>
#include <ostream>
#include <fstream>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <cassert>

>class print_hex {

> std::ostream * ostr_ptr;
unsigned int line_length;
unsigned int index;

>public:

> print_hex ( std::ostream & str_ref, unsigned int length )
: ostr_ptr( &str_ref )
, line_length ( length )
, index ( 0 )
{}

> void operator() ( unsigned char ch ) {
++index;
if ( index >= line_length ) {
(*ostr_ptr) << std::hex << std::setw(2) << std::setfill( '0' )
<< (unsigned int)(ch) << '\n';
index = 0;
} else {
(*ostr_ptr) << std::hex << std::setw(2) << std::setfill( '0' )
<< (unsigned int)(ch) << ' ';

Wouldn't it be preferable to set the formatting flags in the
constructor?

Yup.

I'd also provide an "indent" argument; if index
were 0, I'd output indent spaces, otherwise a single space---or
perhaps the best solution would be to provide a start of line
and a separator string to the constructor, then:

Good idea.

(*ostr_ptr)
<< (inLineCount == 0 ? startString : separString)
<< std::setw( 2 ) << (unsigned int)( ch ) ;
++ inLineCount ;
if ( inLineCount == lineLength ) {
(*ostr_ptr) << endString ;
inLineCount = 0 ;
}

(This supposes that hex and fill were set in the constructor.)
Given the copying that's going on, I'd also simulate move
semantics, so that the final destructor could do something like:

if ( inLineCount != 0 ) {
(*ostr_ptr) << endString ;
}

> }
}
};

>int main ( int argn, char ** args ) {
assert( argn == 2 );
std::ifstream in ( args[1] );
std::for_each( std::istreambuf _iterator< char >( in ),
std::istreambuf _iterator< char >(),
print_hex( std::cout, 25 ) );

Unless you're doing something relatively generic, with support
for different separators, etc., this really looks like a case of
for_each abuse.

Actually, with regard to for_each, I am growing more and more comfortable
using it. Of all algorithms, for_each seems the most silly; on the other
hand it is also the one that has the largest potential for specialized
versions that take advantage of internal knowledge about the underlying
sequence. E.g., I can easily imagine a special version for iterators into a
deque (where for_each would iterate over pages and within each page would
use a very fast loop using T* where it can skip the test for reaching a
page end). Similar optimizations should be possible for stream iterators.

> std::cout << '\n';

Which results in one new line too many if the number of elements
just happened to be an exact multiple of the line length.

You are making up specs :-)

But seriously: you are right, of course.

About the only real use for this sort of output I've found is
debugging or experimenting, but there, I use it often enough
that I've a generic Dump<Tclass (and a generic function which
returns it, for automatic type deduction), so that I can write
things like:

std::cout << dump( someObject ) << std::endl ;

[snip]

Hm, I never had a use for hex dumping objects. But, maybe I should try that
out.
Best

Kai-Uwe Bux

[James Kanze]

On Jun 21, 8:35 pm, Kai-Uwe Bux <jkherci...@gmx .netwrote:

James Kanze wrote:

On Jun 21, 2:13 am, Kai-Uwe Bux <jkherci...@gmx .netwrote:

Ivan wrote:
On Jun 20, 1:11 pm, vizzz <andrea.visin.. [e-mail] e:

Hmmm... I had a look at this and ran accross a simple
problem. How do you read a binary file and just echo the
HEX for byte to the screen.

[snip]

The issue is the c++ read function doesn't return number of
bytes read... so on the last read into a buffer how do you
know how many characters to print?

Have a look at readsome().

Yes, have a look at it. Read it's specification very carefully.
Because if you do, you're realize that it is absolutely
worthless here.

I reread it again. I fail to see why it's worthless.
Obviously, I am missing something.

It will read a maximum of streambuf::in_a vail characters. If
there are no characters in the buffer, streambuf::in_a vail calls
showmanyc. And by default, all showmanyc does is return 0. An
implementation of filebuf may do more, if the system supports
some means of finding out exactly how many characters are in the
file, but it's not required to. Which means that basically,
readsome() may stop (returning 0 characters read) as soon as
there are no more characters in the buffer.

--
James Kanze (GABI Software) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[vizzz]

On 21 Giu, 20:57, Mirco Wahab <[e-mail] e:

vizzz wrote:

Maybe explaining my goal can be useful.
in jpeg2000 files (jp2) there are several boxes made of 4byte length,
4byte type and then data.
i must check if box exist by searching somewhere in the file (boxes
can be anywhere in the whole file) for the box type (ex 0x650A1010).

What is the largest file size and on which system
do you want this to happen?

About 800-900MB on win32 (i'm using VS2008)

[Ivan]

On Jun 21, 3:10*am, James Kanze <james.ka...@gm ail.comwrote:

(But IMHO, istream really isn't appropriate for binary; if I'm
really working with a binary file, I'll drop down to the system
API.)

That's exactly what was I thinking, but I wasn't sure if it was just
my lack of C++ knowledge that made it a pain to read binary data with
istream.

Thanks,
Ivan Novick
http://www.mycppquiz.com/