Or you could depend on the buffering power of the IO libraries and inspect your data four-bytes at a time, rewinding three bytes if no match is found. Not as fast as fixed size records but not as bad as your probably think it is.

#!/usr/bin/perl -wd

$file = shift @ARGV || die "$0 <filename>\n";
open( FH, "<$file" ) or die "cannot open file $!\n";

#MARK

$in_read = 0;
while( read( FH, $four_bytes, 4 ) > 0 ) {

    last if( length( $four_bytes ) != 4 ); # EOF?

    if( $four_bytes eq "MARK" ) {
        print "buffer was ", $buffer, "\n" if $in_read;
        $in_read = $in_read ? 0 : 1;
        $buffer = "";
    } else {
        $buffer .= substr( $four_bytes, 0, 1 ) if $in_read;
        # back up three bytes
        $pos = tell(FH) - 3;
        seek( FH, $pos, 0 );
    }
}

# catch any trailing?
$buffer .= $four_bytes if $in_read;

# do something with the last buffer
print "dangling buffer: ", $buffer, "\n" if $buffer;
[download]

-derby