finddup.c

   1
   2 /*
   3  *  finddup is a simple utility to find duplicated files, files common
   4  *  to several directories, or files present in one directory and not
   5  *  in another one.
   6  *
   7  *  Copyright (c) 2010 Francois Fleuret
   8  *  Written by Francois Fleuret <francois@fleuret.org>
   9  *
  10  *  This file is part of finddup.
  11  *
  12  *  finddup is free software: you can redistribute it and/or modify it
  13  *  under the terms of the GNU General Public License version 3 as
  14  *  published by the Free Software Foundation.
  15  *
  16  *  finddup is distributed in the hope that it will be useful, but WITHOUT
  17  *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  18  *  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  19  *  License for more details.
  20  *
  21  *  You should have received a copy of the GNU General Public License
  22  *  along with finddup.  If not, see <http://www.gnu.org/licenses/>.
  23  *
  24  */
  25
  26 #define VERSION_NUMBER "0.9"
  27
  28 #define _BSD_SOURCE
  29
  30 #include <sys/types.h>
  31 #include <sys/stat.h>
  32 #include <sys/param.h>
  33 #include <dirent.h>
  34 #include <stdlib.h>
  35 #include <stdio.h>
  36 #include <unistd.h>
  37 #include <errno.h>
  38 #include <string.h>
  39 #include <sys/ioctl.h>
  40 #include <locale.h>
  41 #include <getopt.h>
  42 #include <fcntl.h>
  43 #include <openssl/md5.h>
  44
  45 /* 1M really helps compared to 64k */
  46 #define READ_BUFFER_SIZE (1024 * 1024)
  47
  48 typedef int64_t size_sum_t;
  49
  50 /* Yeah, global variables! */
  51
  52 int ignore_dotfiles = 0; /* 1 means ignore files and directories
  53                             starting with a dot */
  54
  55 int ignore_empty_files = 0; /* 1 means ignore empty files */
  56
  57 int show_realpaths = 0; /* 1 means ignore files and directories
  58                             starting with a dot */
  59
  60 int show_progress = 0; /* 1 means show a progress bar when we are in a
  61                           tty */
  62
  63 int show_hits = 1; /* 1 means to show the files from dir2
  64                       corresponding to the ones from dir1 */
  65
  66 int show_groups = 1; /* 1 means to show the group IDs when printing
  67                         file names */
  68
  69 int ignore_same_inode = 0; /* 1 means that comparison between two file
  70                               with same inode will always be false */
  71
  72 int tty_width = -1; /* Positive value means what width to use to show
  73                        the progress bar */
  74
  75 int use_md5 = 0; /* 1 means we keep an MD5 signature for each file */
  76
  77 /********************************************************************/
  78
  79 /* malloc with error checking.  */
  80
  81 void *safe_malloc(size_t n) {
  82   void *p = malloc(n);
  83   if (!p && n != 0) {
  84     printf("Can not allocate memory: %s\n", strerror(errno));
  85     exit(EXIT_FAILURE);
  86   }
  87   return p;
  88 }
  89
  90 /********************************************************************/
  91
  92 int ignore_entry(const char *name) {
  93   return
  94     strcmp(name, ".") == 0 ||
  95     strcmp(name, "..") == 0 ||
  96     (ignore_dotfiles && name[0] == '.' && name[1] != '/');
  97 }
  98
  99 /**********************************************************************/
 100
 101 struct file_node {
 102   struct file_node *next;
 103   char *name;
 104   size_t size;
 105   ino_t inode;
 106   int group_id; /* one per identical file content */
 107   int dir_id; /* 1 for DIR1, and 2 for DIR2 */
 108   int md5_computed;
 109   unsigned char md5[MD5_DIGEST_LENGTH];
 110 };
 111
 112 void file_list_delete(struct file_node *head) {
 113   struct file_node *next;
 114   while(head) {
 115     next = head->next;
 116     free(head->name);
 117     free(head);
 118     head = next;
 119   }
 120 }
 121
 122 int file_list_length(struct file_node *head) {
 123   int l = 0;
 124   while(head) {
 125     l++;
 126     head = head->next;
 127   }
 128   return l;
 129 }
 130
 131 /**********************************************************************/
 132
 133 int same_content(struct file_node *f1, struct file_node *f2,
 134                  char *buffer1, char *buffer2) {
 135   int fd1, fd2, s1, s2;
 136   MD5_CTX c1, c2;
 137
 138   if(use_md5) {
 139     if(f1->md5_computed && f2->md5_computed &&
 140        !memcmp(f1->md5, f2->md5, MD5_DIGEST_LENGTH)) {
 141       return 0;
 142     } else {
 143       if(!f1->md5_computed) {
 144         MD5_Init(&c1);
 145       }
 146       if(!f2->md5_computed) {
 147         MD5_Init(&c2);
 148       }
 149     }
 150   }
 151
 152   fd1 = open(f1->name, O_RDONLY);
 153   fd2 = open(f2->name, O_RDONLY);
 154
 155   if(fd1 >= 0 && fd2 >= 0) {
 156     while(1) {
 157       s1 = read(fd1, buffer1, READ_BUFFER_SIZE);
 158       s2 = read(fd2, buffer2, READ_BUFFER_SIZE);
 159
 160       if(s1 < 0 || s2 < 0) {
 161         close(fd1);
 162         close(fd2);
 163         return 0;
 164       }
 165
 166       if(s1 == s2) {
 167         if(s1 == 0) {
 168           close(fd1);
 169           close(fd2);
 170           if(use_md5) {
 171             if(!f1->md5_computed) {
 172               MD5_Final(f1->md5, &c1);
 173               f1->md5_computed = 1;
 174             }
 175             if(!f2->md5_computed) {
 176               MD5_Final(f2->md5, &c2);
 177               f2->md5_computed = 1;
 178             }
 179           }
 180           return 1;
 181         } else {
 182           if(use_md5) {
 183             if(!f1->md5_computed) {
 184               MD5_Update(&c1, buffer1, s1);
 185             }
 186             if(!f2->md5_computed) {
 187               MD5_Update(&c2, buffer2, s2);
 188             }
 189           }
 190           if(memcmp(buffer1, buffer2, s1)) {
 191             close(fd1);
 192             close(fd2);
 193             return 0;
 194           }
 195         }
 196       } else {
 197         fprintf(stderr,
 198                 "Different read size without error on files of same size.\n");
 199         exit(EXIT_FAILURE);
 200       }
 201     }
 202   } else {
 203
 204     if(fd1 < 0) {
 205       fprintf(stderr,
 206               "Can not open \"%s\" error: %s\n",
 207               f1->name,
 208               strerror(errno));
 209     }
 210
 211     if(fd2 < 0) {
 212       fprintf(stderr,
 213               "Can not open \"%s\" error: %s\n",
 214               f2->name,
 215               strerror(errno));
 216     }
 217
 218     exit(EXIT_FAILURE);
 219   }
 220 }
 221
 222 int same_files(struct file_node *f1, struct file_node *f2,
 223                char *buffer1, char *buffer2) {
 224   if(ignore_same_inode && f1->inode == f2->inode) {
 225     return 0;
 226   }
 227   return f1->size == f2->size && same_content(f1, f2, buffer1, buffer2);
 228 }
 229
 230 /**********************************************************************/
 231
 232 struct file_node *scan_directory(struct file_node *tail, const char *name) {
 233   DIR *dir;
 234   struct dirent *dir_e;
 235   struct stat sb;
 236   struct file_node *tmp;
 237   char subname[PATH_MAX + 1];
 238
 239   if(lstat(name, &sb) != 0) {
 240     fprintf(stderr, "Can not stat \"%s\": %s\n", name, strerror(errno));
 241     exit(EXIT_FAILURE);
 242   }
 243
 244   if(S_ISLNK(sb.st_mode)) {
 245     return tail;
 246   }
 247
 248   dir = opendir(name);
 249
 250   if(dir) {
 251     while((dir_e = readdir(dir))) {
 252       if(!ignore_entry(dir_e->d_name)) {
 253         snprintf(subname, PATH_MAX, "%s/%s", name, dir_e->d_name);
 254         tail = scan_directory(tail, subname);
 255       }
 256     }
 257     closedir(dir);
 258   } else {
 259     if(S_ISREG(sb.st_mode)) {
 260       if(!ignore_entry(name)) {
 261         if(!ignore_empty_files || sb.st_size > 0) {
 262           tmp = safe_malloc(sizeof(struct file_node));
 263           tmp->next = tail;
 264           tmp->name = strdup(name);
 265           tmp->size = sb.st_size;
 266           tmp->inode = sb.st_ino;
 267           tmp->group_id = -1;
 268           tmp->dir_id = -1;
 269           tmp->md5_computed = 0;
 270           tail = tmp;
 271         }
 272       }
 273     }
 274   }
 275
 276   return tail;
 277 }
 278
 279 void print_file(struct file_node *node) {
 280   char tmp[PATH_MAX + 1];
 281   if(show_realpaths) {
 282     if(realpath(node->name, tmp)) {
 283       if(show_groups) {
 284         printf("%d %s\n", node->group_id, tmp);
 285       } else {
 286         printf("%s\n", tmp);
 287       }
 288     } else {
 289       printf("Can not get the realpath of \"%s\": %s\n",
 290              node->name,
 291              strerror(errno));
 292       exit(EXIT_FAILURE);
 293     }
 294   } else {
 295     if(show_groups) {
 296       printf("%d %s\n", node->group_id, node->name);
 297     } else {
 298       printf("%s\n", node->name);
 299     }
 300   }
 301 }
 302
 303 int compare_nodes(const void *x1, const void *x2) {
 304   const struct file_node **f1, **f2;
 305
 306   f1 = (const struct file_node **) x1;
 307   f2 = (const struct file_node **) x2;
 308
 309   if((*f1)->group_id < (*f2)->group_id) {
 310     return -1;
 311   } else if((*f1)->group_id > (*f2)->group_id) {
 312     return 1;
 313   } else {
 314     if((*f1)->dir_id < (*f2)->dir_id) {
 315       return -1;
 316     } else if((*f1)->dir_id > (*f2)->dir_id) {
 317       return 1;
 318     } else {
 319       return 0;
 320     }
 321   }
 322 }
 323
 324
 325 void print_result(struct file_node *list1, struct file_node *list2) {
 326   struct file_node *node1, *node2;
 327   struct file_node **nodes;
 328   int nb, n;
 329
 330   nb = 0;
 331   for(node1 = list1; node1; node1 = node1->next) {
 332     if(node1->group_id >= 0) { nb++; }
 333   }
 334
 335   if(list2) {
 336     for(node2 = list2; node2; node2 = node2->next) {
 337       if(node2->group_id >= 0) { nb++; }
 338     }
 339   }
 340
 341   nodes = safe_malloc(nb * sizeof(struct file_node *));
 342
 343   n = 0;
 344   for(node1 = list1; node1; node1 = node1->next) {
 345     if(node1->group_id >= 0) {
 346       nodes[n++] = node1;
 347     }
 348   }
 349
 350   if(list2) {
 351     for(node2 = list2; node2; node2 = node2->next) {
 352       if(node2->group_id >= 0) {
 353         nodes[n++] = node2;
 354       }
 355     }
 356   }
 357
 358   qsort(nodes, nb, sizeof(struct file_node *), compare_nodes);
 359
 360   for(n = 0; n < nb; n++) {
 361     if(!show_groups && n > 0 && nodes[n]->group_id != nodes[n-1]->group_id) {
 362       printf("\n");
 363     }
 364     print_file(nodes[n]);
 365   }
 366
 367   free(nodes);
 368 }
 369
 370 void print_progress(int max, int n, int *pp) {
 371   int p, k;
 372   int width;
 373   if(show_progress && tty_width > 0) {
 374     width = tty_width - 7;
 375     p = (width * n) / (max - 1);
 376     if(p > *pp) {
 377       for(k = 0; k < p; k++) {
 378         fprintf(stderr, "+");
 379       }
 380       for(; k < width; k++) {
 381         fprintf(stderr, "-");
 382       }
 383       *pp = p;
 384       p = (100 * n) / (max - 1);
 385       fprintf(stderr, " [%3d%%]\r", p);
 386     }
 387   }
 388 }
 389
 390 void start(const char *dirname1, const char *dirname2) {
 391   struct file_node *list1, *list2;
 392   struct file_node *node1, *node2;
 393   int not_in, found;
 394   int nb_groups, nb_nodes;
 395   int list1_length, previous_progress;
 396   struct winsize win;
 397
 398   char *buffer1 = safe_malloc(sizeof(char) * READ_BUFFER_SIZE);
 399   char *buffer2 = safe_malloc(sizeof(char) * READ_BUFFER_SIZE);
 400
 401   not_in = 0;
 402
 403   if(show_progress) {
 404     if(isatty(STDOUT_FILENO) &&
 405        !ioctl (STDOUT_FILENO, TIOCGWINSZ, (char *) &win)) {
 406       tty_width = win.ws_col;
 407     }
 408     fprintf(stderr, "Scanning %s ... ", dirname1);
 409   }
 410
 411   list1 = scan_directory(0, dirname1);
 412
 413   if(dirname2) {
 414     if(strncmp(dirname2, "not:", 4) == 0) {
 415       not_in = 1;
 416       /* groups are not computed in the not: mode */
 417       show_groups = 0;
 418       dirname2 += 4;
 419     } else if(strncmp(dirname2, "and:", 4) == 0) {
 420       dirname2 += 4;
 421     }
 422     if(show_progress) {
 423       fprintf(stderr, "%s ... ", dirname2);
 424     }
 425     list2 = scan_directory(0, dirname2);
 426   } else {
 427     list2 = list1;
 428   }
 429
 430   if(show_progress) {
 431     fprintf(stderr, "done.\n");
 432   }
 433
 434   nb_groups = 0;
 435   previous_progress = -1;
 436   nb_nodes = 0;
 437   list1_length = file_list_length(list1);
 438
 439   if(not_in) {
 440     for(node1 = list1; node1; node1 = node1->next) {
 441       print_progress(list1_length, nb_nodes, &previous_progress);
 442       nb_nodes++;
 443
 444       found = 0;
 445
 446       for(node2 = list2; !found && node2; node2 = node2->next) {
 447         if(same_files(node1, node2, buffer1, buffer2)) {
 448           found = 1;
 449         }
 450       }
 451
 452       if(!found) {
 453         if(show_realpaths) {
 454           printf("%s\n", realpath(node1->name, 0));
 455         } else {
 456           printf("%s\n", node1->name);
 457         }
 458       }
 459     }
 460
 461   } else {
 462     for(node1 = list1; node1; node1 = node1->next) {
 463       print_progress(list1_length, nb_nodes, &previous_progress);
 464       nb_nodes++;
 465
 466       for(node2 = list2; node2; node2 = node2->next) {
 467         if(node1->group_id < 0 || node2->group_id < 0) {
 468           if(same_files(node1, node2, buffer1, buffer2)) {
 469             if(node1->group_id < 0) {
 470               if(node2->group_id >= 0) {
 471                 node1->group_id = node2->group_id;
 472               } else {
 473                 node1->group_id = nb_groups;
 474                 node1->dir_id = 1;
 475                 nb_groups++;
 476               }
 477             }
 478             if(node2->group_id < 0) {
 479               node2->group_id = node1->group_id;
 480               node2->dir_id = 2;
 481             }
 482           }
 483         }
 484       }
 485     }
 486   }
 487
 488   if(show_progress) {
 489     fprintf(stderr, "\n");
 490   }
 491
 492   if(dirname2) {
 493     print_result(list1, list2);
 494     file_list_delete(list1);
 495     file_list_delete(list2);
 496   } else {
 497     print_result(list1, 0);
 498     file_list_delete(list1);
 499   }
 500
 501   free(buffer1);
 502   free(buffer2);
 503 }
 504
 505 void print_help(FILE *out) {
 506   fprintf(out, "Usage: finddup [OPTION]... DIR1 [[and:|not:]DIR2]\n");
 507   fprintf(out, "Version %s (%s)\n", VERSION_NUMBER, UNAME);
 508   fprintf(out, "Without DIR2, lists duplicated files found in DIR1. With DIR2, lists files common to both directories. With the not: prefix, lists files found in DIR1 which do not exist in DIR2. The and: prefix is the default and should be used only if you have a directory starting with 'not:'\n");
 509   fprintf(out, "\n");
 510   /*            01234567890123456789012345678901234567890123456789012345678901234567890123456789*/
 511   fprintf(out, "   -h, --help                 show this help\n");
 512   fprintf(out, "   -d, --ignore-dots          ignore dot files and directories\n");
 513   fprintf(out, "   -0, --ignore-empty         ignore empty files\n");
 514   fprintf(out, "   -c, --hide-matchings       do not show which files in DIR2 corresponds to\n");
 515   fprintf(out, "                              those in DIR1\n");
 516   fprintf(out, "   -g, --no-group-ids         do not show the file groups\n");
 517   fprintf(out, "   -p, --show-progress        show progress\n");
 518   fprintf(out, "   -r, --real-paths           show the real file paths\n");
 519   fprintf(out, "   -i, --same-inodes-are-different\n");
 520   fprintf(out, "                              consider files with same inode as different\n");
 521   fprintf(out, "   -m, --md5                  use MD5 hashing\n");
 522   fprintf(out, "\n");
 523   fprintf(out, "Report bugs and comments to <francois@fleuret.org>.\n");
 524 }
 525
 526 /**********************************************************************/
 527
 528 static struct option long_options[] = {
 529   { "help", no_argument, 0, 'h' },
 530   { "same-inodes-are-different", no_argument, 0, 'i' },
 531   { "real-paths", no_argument, 0, 'r' },
 532   { "hide-matchings", no_argument, 0, 'c' },
 533   { "no-group-ids", no_argument, 0, 'g' },
 534   { "ignore-dots", no_argument, 0, 'd' },
 535   { "ignore-empty", no_argument, 0, '0' },
 536   { "show-progress", no_argument, 0, 'p' },
 537   { "md5", no_argument, 0, 'm' },
 538   { 0, 0, 0, 0 }
 539 };
 540
 541 int main(int argc, char **argv) {
 542   int c;
 543
 544   setlocale (LC_ALL, "");
 545
 546   while ((c = getopt_long(argc, argv, "hircgd0pm",
 547                           long_options, NULL)) != -1) {
 548     switch (c) {
 549
 550     case 'h':
 551       print_help(stdout);
 552       exit(EXIT_SUCCESS);
 553
 554       break;
 555
 556     case 'd':
 557       ignore_dotfiles = 1;
 558       break;
 559
 560     case '0':
 561       ignore_empty_files = 1;
 562       break;
 563
 564     case 'r':
 565       show_realpaths = 1;
 566       break;
 567
 568     case 'i':
 569       ignore_same_inode = 1;
 570       break;
 571
 572     case 'g':
 573       show_groups = 0;
 574       break;
 575
 576     case 'p':
 577       show_progress = 1;
 578       break;
 579
 580     case 'c':
 581       show_hits = 0;
 582       break;
 583
 584     case 'm':
 585       use_md5 = 1;
 586       break;
 587
 588     default:
 589       exit(EXIT_FAILURE);
 590     }
 591   }
 592
 593   if(optind + 2 == argc) {
 594     start(argv[optind], argv[optind + 1]);
 595   } else if(optind + 1 == argc) {
 596     ignore_same_inode = 1;
 597     start(argv[optind], 0);
 598   } else {
 599     print_help(stderr);
 600     exit(EXIT_FAILURE);
 601   }
 602
 603   exit(EXIT_SUCCESS);
 604 }