blockmap.c

   1 #include <stdio.h>
   2 #include <unistd.h>
   3 #include <fcntl.h>
   4 #include <sys/mman.h>
   5 #include <sys/stat.h>
   6
   7 static void *map_file(char *fname, size_t *size)
   8 {
   9         int fd = open(fname, O_RDONLY);
  10         struct stat st;
  11         void *p;
  12
  13         fstat(fd, &st);
  14         p = mmap(0, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
  15         close(fd);
  16
  17         *size = st.st_size;
  18         return p;
  19 }
  20
  21 static int block_match(unsigned char *p1, unsigned char *p2)
  22 {
  23         int i;
  24         int ret=0;
  25         if (memcmp(p1, p2, 512) == 0) return 512;
  26         for (i=0;i<512;i++) if (p1[i] && p1[i] != 0xff && p1[i] == p2[i]) ret++;
  27         return ret;
  28 }
  29
  30 static int best_block(char *p1, char *p2, int nblocks, int *x, int hint)
  31 {
  32         int i;
  33         int besti = 0;
  34         int bestv = -1;
  35         for (i=0; i<nblocks && bestv < 512; i++) {
  36                 int ri;
  37                 int v;
  38
  39                 ri = hint + i;
  40                 if (ri < nblocks) {
  41                         v = block_match(p1, p2+ri*512);
  42                         if (v > bestv) {
  43                                 besti = ri;
  44                                 bestv = v;
  45                         }
  46                 }
  47
  48                 ri = hint - i;
  49                 if (ri >= 0) {
  50                         v = block_match(p1, p2+ri*512);
  51                         if (v > bestv) {
  52                                 besti = ri;
  53                                 bestv = v;
  54                         }
  55                 }
  56         }
  57         *x = bestv;
  58         return besti;
  59 }
  60
  61 int main(int argc, char *argv[])
  62 {
  63         size_t size1, size2;
  64         int blocks1, blocks2;
  65         char *p1, *p2;
  66
  67         int i;
  68         static char zblock[512];
  69
  70         p1 = map_file(argv[1], &size1);
  71         p2 = map_file(argv[2], &size2);
  72
  73         blocks1 = size1>>9;
  74         blocks2 = size2>>9;
  75
  76         for (i=0;i<blocks1;i++) {
  77                 int j, v;
  78                 if (memcmp(p1+i*512, zblock, 512) == 0) continue;
  79                 j = best_block(p1+i*512, p2, blocks2, &v, i);
  80                 printf("block %d best is %d\tv=%d\tdiff=%d\n",
  81                                    i, j, v, i-j);
  82         }
  83         return 0;
  84 }