From ee819ce87f261b12923680e9fe44b407ebfe8953 Mon Sep 17 00:00:00 2001 From: "Eric S. Raymond" Date: Mon, 1 Sep 2003 16:44:29 +0000 Subject: [PATCH] Reduction works. --- report.c | 340 ++++++++++++++++++++++++++++++------------------------- 1 file changed, 184 insertions(+), 156 deletions(-) diff --git a/report.c b/report.c index 7dc1ec2..f0e8b79 100644 --- a/report.c +++ b/report.c @@ -38,11 +38,17 @@ struct sorthash_t static struct sorthash_t *obarray, *np; static int hashcount; -struct match_t +struct range_t { char *file; linenum_t start, end; +}; + +struct match_t +{ struct match_t *next; + int nmatches; + struct range_t *matches; } dummy_match; static struct match_t *reduced = &dummy_match; @@ -75,163 +81,177 @@ void init_intern(const int count) } } -void file_intern(const char *file) -/* stash the name of a file */ -{ - struct item *new; - - new = (struct item *)malloc(sizeof(struct item)); - new->file = strdup(file); - new->next = head; - head = new; -} - -void hash_intern(const struct hash_t *chunk) -{ - np->file = head->file; - np->hash = *chunk; - np++; -} - -static long merge_hashes(int argc, char *argv[]) -/* merge hashes from specified files into an in-code list */ -{ - struct shif_t *shiflist, *sp; - struct stat sb; - long total, hashcount = 0; - - /* set up metadata blocks for the hash files */ - shiflist = (struct shif_t *)calloc(sizeof(struct shif_t), argc); - for (sp = shiflist; sp < shiflist + argc; sp++) - { - char buf[BUFSIZ]; - - sp->name = strdup(argv[sp - shiflist]); - sp->fp = fopen(sp->name, "r"); - fgets(buf, sizeof(buf), sp->fp); - if (strncmp(buf, "#SHIF-A ", 8)) - { - fprintf(stderr, - "shredcompare: %s is not a SHIF-A file.", - sp->name); - exit(1); - } - while (fgets(buf, sizeof(buf), sp->fp) != NULL) - { - char *value; - - if (!strcmp(buf, "%%\n")) - break; - value = strchr(buf, ':'); - *value++ = '\0'; - strchr(value, '\n')[0] = '\0'; - - if (!strcmp(buf, "Normalization")) - sp->normalization = strdup(value); - else if (!strcmp(buf, "Shred-Size")) - sp->shred_size = atoi(value); - else if (!strcmp(buf, "Hash-Method")) - sp->hash_method = strdup(value); - else if (!strcmp(buf, "Generator-Program")) - sp->generator_program = strdup(value); - } - } - - /* consistency checks */ - for (sp = shiflist; sp < shiflist + argc-1; sp++) - { - struct shif_t *next = sp + 1; - - if (strcmp(sp->normalization, next->normalization)) - { - fprintf(stderr, - "shredcompare: normalizations of %s and %s don't match\n", - sp->name, next->name); - exit(1); - } - else if (sp->shred_size != next->shred_size) - { - fprintf(stderr, - "shredcompare: shred sizes of %s and %s don't match\n", - sp->name, next->name); - exit(1); - - } - else if (strcmp(sp->hash_method, next->hash_method)) - { - fprintf(stderr, - "shredcompare: hash methods of %s and %s don't match\n", - sp->name, next->name); - exit(1); - } - } - - /* compute total data to be read, we'll use this for the progress meter */ - total = 0; - for (sp = shiflist; sp < shiflist + argc; sp++) - { - stat(sp->name, &sb); - total += sb.st_size - ftell(sp->fp); - } - fprintf(stderr, "%ld bytes to be read.\n", total); - init_intern(total/sizeof(struct hash_t)); /* real work done here */ - - /* read in all hashes */ - for (sp = shiflist; sp < shiflist + argc; sp++) - { - u_int32_t sectcount; - - fread(§count, sizeof(u_int32_t), 1, sp->fp); - sectcount = ntohl(sectcount); - while (sectcount--) - { - char buf[BUFSIZ]; - linenum_t chunks; - - fgets(buf, sizeof(buf), sp->fp); - *strchr(buf, '\n') = '\0'; - file_intern(buf); /* real work done here */ - fread(&chunks, sizeof(linenum_t), 1, sp->fp); - chunks = FROMNET(chunks); - - while (chunks--) - { - struct hash_t this; - - fread(&this, sizeof(struct hash_t), 1, sp->fp); - this.start = FROMNET(this.start); - this.end = FROMNET(this.end); - hash_intern(&this); /* real work done here */ - hashcount++; - } - } - } - - return hashcount; -} + void file_intern(const char *file) + /* stash the name of a file */ + { + struct item *new; + + new = (struct item *)malloc(sizeof(struct item)); + new->file = strdup(file); + new->next = head; + head = new; + } + + void hash_intern(const struct hash_t *chunk) + { + np->file = head->file; + np->hash = *chunk; + np++; + } + + static long merge_hashes(int argc, char *argv[]) + /* merge hashes from specified files into an in-code list */ + { + struct shif_t *shiflist, *sp; + struct stat sb; + long total, hashcount = 0; + + /* set up metadata blocks for the hash files */ + shiflist = (struct shif_t *)calloc(sizeof(struct shif_t), argc); + for (sp = shiflist; sp < shiflist + argc; sp++) + { + char buf[BUFSIZ]; + + sp->name = strdup(argv[sp - shiflist]); + sp->fp = fopen(sp->name, "r"); + fgets(buf, sizeof(buf), sp->fp); + if (strncmp(buf, "#SHIF-A ", 8)) + { + fprintf(stderr, + "shredcompare: %s is not a SHIF-A file.", + sp->name); + exit(1); + } + while (fgets(buf, sizeof(buf), sp->fp) != NULL) + { + char *value; + + if (!strcmp(buf, "%%\n")) + break; + value = strchr(buf, ':'); + *value++ = '\0'; + strchr(value, '\n')[0] = '\0'; + + if (!strcmp(buf, "Normalization")) + sp->normalization = strdup(value); + else if (!strcmp(buf, "Shred-Size")) + sp->shred_size = atoi(value); + else if (!strcmp(buf, "Hash-Method")) + sp->hash_method = strdup(value); + else if (!strcmp(buf, "Generator-Program")) + sp->generator_program = strdup(value); + } + } + + /* consistency checks */ + for (sp = shiflist; sp < shiflist + argc-1; sp++) + { + struct shif_t *next = sp + 1; + + if (strcmp(sp->normalization, next->normalization)) + { + fprintf(stderr, + "shredcompare: normalizations of %s and %s don't match\n", + sp->name, next->name); + exit(1); + } + else if (sp->shred_size != next->shred_size) + { + fprintf(stderr, + "shredcompare: shred sizes of %s and %s don't match\n", + sp->name, next->name); + exit(1); + + } + else if (strcmp(sp->hash_method, next->hash_method)) + { + fprintf(stderr, + "shredcompare: hash methods of %s and %s don't match\n", + sp->name, next->name); + exit(1); + } + } + + /* compute total data to be read, we'll use this for the progress meter */ + total = 0; + for (sp = shiflist; sp < shiflist + argc; sp++) + { + stat(sp->name, &sb); + total += sb.st_size - ftell(sp->fp); + } + fprintf(stderr, "%ld bytes to be read.\n", total); + init_intern(total/sizeof(struct hash_t)); /* real work done here */ + + /* read in all hashes */ + for (sp = shiflist; sp < shiflist + argc; sp++) + { + u_int32_t sectcount; + + fread(§count, sizeof(u_int32_t), 1, sp->fp); + sectcount = ntohl(sectcount); + while (sectcount--) + { + char buf[BUFSIZ]; + linenum_t chunks; + + fgets(buf, sizeof(buf), sp->fp); + *strchr(buf, '\n') = '\0'; + file_intern(buf); /* real work done here */ + fread(&chunks, sizeof(linenum_t), 1, sp->fp); + chunks = FROMNET(chunks); + + while (chunks--) + { + struct hash_t this; + + fread(&this, sizeof(struct hash_t), 1, sp->fp); + this.start = FROMNET(this.start); + this.end = FROMNET(this.end); + hash_intern(&this); /* real work done here */ + hashcount++; + } + } + } + + return hashcount; + } struct match_t *reduce_matches(int localdups) +/* assemble list of duplicated hashes */ { - static struct match_t dummy; - struct match_t *reduced; + static struct match_t dummy; + struct match_t *reduced = &dummy; + + for (np = obarray; np < obarray + hashcount; np++) + { + if (np < obarray + hashcount - 1 && !HASHCMP(np, np+1)) + { + struct match_t *new; + int i; + struct sorthash_t *mp; + + new = (struct match_t *)malloc(sizeof(struct match_t)); + new->next = reduced; + reduced = new; + new->nmatches = 1; + for (mp = np+1; mp < obarray + hashcount; mp++) + if (HASHCMP(np, mp)) + break; + else + new->nmatches++; + new->matches=(struct range_t *)calloc(sizeof(struct range_t),new->nmatches); + for (i = 0; i < new->nmatches; i++) + { + new->matches[i].file = np[i].file; + new->matches[i].start = np[i].hash.start; + new->matches[i].end = np[i].hash.end; + } + np = mp-1; + } + } - for (np = obarray; np < obarray + hashcount; np++) - if (np < obarray + hashcount - 1 && !HASHCMP(np, np+1)) - for (;;) - { - struct match_t *new; - - printf("Foo %d\n", np - obarray); - new = (struct match_t *)malloc(sizeof(struct match_t)); - new->file = np->file; - new->start = np->hash.start; - new->end = np->hash.end; - new->next = reduced; - reduced = new; - if (HASHCMP(np, np+1)) - break; - np++; - } + free(obarray); + return reduced; } int sortchunk(void *a, void *b) @@ -276,11 +296,19 @@ main(int argc, char *argv[]) printf("%d: %s:%d:%d (%02x%02x)\n", np-obarray, np->file, np->hash.start, np->hash.end, np->hash.hash[0], np->hash.hash[1]); reduced = reduce_matches(local_duplicates); - report_time("Reduction done.\n"); + report_time("Reduction done."); for (; reduced; reduced = reduced->next) { - printf("%s:%d:%d\n", reduced->file, reduced->start, reduced->end); + int i; + for (i=0; i < reduced->nmatches; i++) + { + struct range_t *rp = reduced->matches+i; + + printf("%s:%d:%d\n", + rp->file, rp->start, rp->end); + } + printf("-\n"); } } -- 2.43.0