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