I'm not certain I fully understand the problem, but this would seem to cry out for using bitvectors and bitwise operations. Then you could just:

foreach my $bigfile_bitvector (@bigfile_bitvectors) {
  foreach my $smallfile_bitvector (@smallfile_bitvectors) {
    my $diff_bitvector = $bigfile_bitvector ^ $smallfile_bitvector;
    write_diffs($diff_bitvector);
  }
}
[download]

You'll have to craft an appropriate write_diffs function to look for the 1s in the diff bitvector and write them in your necessary format.