From 85639d2957269393546f99888f1990022e61bea3 Mon Sep 17 00:00:00 2001 From: "Eric S. Raymond" Date: Thu, 18 Sep 2003 03:35:15 +0000 Subject: [PATCH] We do significance filtering inside comparator now. --- Makefile | 15 ++++-- comparator.py | 137 ++++------------------------------------------- comparator.xml | 34 ++++++++++-- filterator | 32 +++-------- linebyline.c | 102 ++++++++++++++--------------------- main.c | 62 ++++++++++++++++----- report.c | 39 +++++++------- scf-standard.xml | 64 ++++++++++++++-------- shred.h | 17 +++++- shredtree.c | 35 +++++++++--- 10 files changed, 252 insertions(+), 285 deletions(-) diff --git a/Makefile b/Makefile index 24c4956..d424ea8 100644 --- a/Makefile +++ b/Makefile @@ -5,7 +5,7 @@ VERS=2.0 -CODE = shredtree.c shred.h report.c hash.c main.c md5.c md5.h \ +CODE = shredtree.c shred.h report.c hash.c filter.c main.c md5.c md5.h \ hash.h hashtab.h \ filterator SCRIPTS = hashgen.py setup.py @@ -13,27 +13,32 @@ DOCS = README NEWS comparator.xml scf-standard.xml COPYING EXTRAS = shredtree.py shredcompare.py TEST = test SOURCES = $(CODE) $(DOCS) $(EXTRAS) $(TEST) comparator.spec Makefile -CFLAGS = -O3 +CFLAGS = -g #-O3 LDFLAGS = all: comparator comparator.1 main.o: main.c shred.h hash.h $(CC) -DVERSION=\"$(VERS)\" -c $(CFLAGS) main.c +filter.o: filter.c + $(CC) -c $(CFLAGS) filter.c hash.o: hash.c hash.h hashtab.h $(CC) -c $(CFLAGS) hash.c shredtree.o: shredtree.c shred.h hash.h $(CC) -c $(CFLAGS) shredtree.c report.o: report.c shred.h hash.h $(CC) -c $(CFLAGS) report.c -comparator: main.o hash.o shredtree.o md5.o report.o - $(CC) $(CFLAGS) main.o hash.o shredtree.o md5.o report.o $(LDFLAGS) -o comparator +comparator: main.o hash.o filter.o shredtree.o md5.o report.o + $(CC) $(CFLAGS) main.o hash.o filter.o shredtree.o md5.o report.o $(LDFLAGS) -o comparator hashtab.h: hashgen.py python hashgen.py >hashtab.h +filter: filter.c + $(CC) -DTEST $(CFLAGS) -o filter filter.c + clean: - rm -f comparator shredtree.o md5.o report.o main.o hash.o *~ + rm -f comparator filter *.o *~ rm -f comparator.1 filterator.1 rm -f *.dump *.scf diff --git a/comparator.py b/comparator.py index 1b852aa..cea57f4 100644 --- a/comparator.py +++ b/comparator.py @@ -1,73 +1,5 @@ import os, sys, re, exceptions -# Tokens to be removed when checking whether a shred is significant -junk = { - "C": map(re.compile, ( - # Idioms that don't convey any meaning in isolation - r"return *\(?[a-z]+\)? *;", r"return *\(?-?[01]+\)? *;", - r"goto +[a-z]+;", r"exit *\([01]\);", - # Pragmas - r'/\* *ARGSUSED *\*/', - r'/\* *NOTREACHED *\*/', - r'/\* *FALL *THRO?UG?H? *\*/', - # Bare C keywords - r'\bbreak\b', r'\bcase\b',r'\bcontinue\b', r'\bdefault\b', - r'\bdo\b', r'\belse\b', r'\benum\b', r'\bif\b', r'\bgoto\b', - r'\breturn\b', r'\bswitch\b', r'\bwhile\b', - r'enum', r'\bint\b', r'\blong\b', r'\bshort\b', r'\bstatic\b', - r'\bstruct\b', r'\btypedef\b', r'\bunion\b', r'\bvoid\b', - r'# *define',r'# *endif',r'# *else',r'# *if\b', - r'# *ifdef\b',r'# *ifndef\b', - # Comment delimiters with no content - r'/\*+', r'\*+/', r'\*+', r'^ *\\s*\n', - # Common preprocessor macros, not significant by themselves. - r'\bASSERT\b', r'\bFALSE\b', r'\bNULL\b', r'\bSTATIC\b', r'\bTRUE\b', - # Macro include lines are noise, too. - r'\s*#include.*',r'#\s*line.*', - # Common error macros. - r'\bEFAULT\b', r'\bEINVAL\b', r'\bENOSYS\b', - # Punctuation and whitespace - r'\{', r'\}', r'\(', r'\)', r'\<', r'\>', r'\[', r'\]', - r'\^', '&', r'\|', r'\*', r'\?', r'\.', r'\+', - '\\\n', ';', ':', '%', ',', '-', '/', '=', '!', '\n','\t', '\v' - )), - "shell": map(re.compile, ( - # Idioms that don't convey any meaning in isolation - r"exit *[01];?", - # Bare shell keywords - r"\bbreak\b", r"\bcase\b", r"\bdone\b", r"\bdo\b", r"\belse\b", - r"\besac\b", r"\bfi\b", r"\bif\b", r"\breturn\b", r"\bshift\b", - r"\btrue\b", r"\bwhile\b", - # Blank comment - "^#\n", - # Punctuation and whitespace - ':', ';', '\n','\t', '\v' - )), - } - -def nontrivial(filetype, text, debug=None): - "Identify a shred as trivial or nontrivial." - if filetype: - if debug: - print "New shred, type %s:" % `filetype` - sys.stdout.write(text) - # Basic theory of this function is that if we throw out all C - # syntax and and common constants, and there is still an - # identifier, we're looking at something that might be - # interesting. - text = ' ' + text - while 1: - savecopy = text - for regexp in junk[filetype]: - text = regexp.sub(' ', text) - if savecopy == text: - break - else: - if debug: - print "Reduced:", `text` - continue - return text.strip() - class ComparatorException(exceptions.Exception): def __init__(self, message, retval=1): self.message = message @@ -108,6 +40,8 @@ class CommonReport: self.merge_program = value elif tag == "Hash-Method": self.hash_method = value + elif tag == "Matches": + self.matches = int(value) # Read file properties self.trees = {} while 1: @@ -141,49 +75,21 @@ class CommonReport: if self.name: self.fp.close() - def segment_count(self): - "Number of common chunks in the report." - return len(self.cliques) - - def line_count(self, tree): - "Number of common lines from a specified tree." - lines = 0 - for clique in self.cliques: - for (file, start, end) in clique: - # We find only the first match in the clique that - # is part of the specified tree. There could be others, - # and if whitespace removal is in effect they could - # have different names. - if file.startswith(tree): - lines += end - start + 1 - break - return lines - def extract_text(self, clique): "Return text corresponding to the given clique." - text = text_type = None + text = None if self.dir: olddir = os.getcwd() os.chdir(self.dir) for (file, start, end) in clique: try: - # Try to deduce the text_type - text_type = None - if file.endswith(".c") or file.endswith(".h"): - text_type = "C" # Skip to the relevant chunk rfp = open(file) for i in range(start-1): line = rfp.readline() - if not text_type and i == 0: - if "sh" in line: - text_type = "shell" text = "" for i in range(start, end+1): nextline = rfp.readline() - if not text_type and i == 0 and start == 1: - if "sh" in line: - text_type = "shell" if nextline[0] == '%': nextline = '%' + nextline text += nextline @@ -195,7 +101,7 @@ class CommonReport: os.chdir(olddir) if not text: print >>sys.stderr, "Failed to extract text from", clique - return (text_type, text) + return text def filter_by_size(self, minsize): "Throw out all common segments below a specified size." @@ -207,34 +113,9 @@ class CommonReport: break self.cliques = filtered - def filter_by_significance(self): - "Throw out all cliques that aren't significant." - filtered = [] - for clique in self.cliques: - (type, text) = self.extract_text(clique) - if nontrivial(type, text): - filtered.append(clique) - self.cliques = filtered - - def statistics(self): - "Return a statistical summary object for the current report." - return CommonStatistics(self) - -class CommonStatistics: - "Statistical information from a report." - def __init__(self, report): - self.chunks = report.segment_count() - self.trees = [] - self.normalization = report.normalization - for (tree, chunks, lines, totallines) in report.trees.items(): - lines = report.line_count(tree) - self.trees.append((tree, lines, totallines)) +# Property flags +C_CODE = 0x01 +SHELL_CODE = 0x02 +SIGNIFICANT = 0x40 - def __str__(self): - rep = "Trees: " + " ".join(map(lambda x: x[0], self.trees)) - rep = "%d overlaps with %s normalization\n" % (self.chunks, self.normalization) - for tree in self.trees: - lines = tree['lines'] - total = tree['total'] - rep += "%s:\t%d of %d (%02.2f%%)\n" % (tree, lines, total, (lines * 100.0)/total) - return rep +# End diff --git a/comparator.xml b/comparator.xml index 42165b5..121ae00 100644 --- a/comparator.xml +++ b/comparator.xml @@ -20,11 +20,12 @@ -C -d dir -m size + -n -o file -r -s shredsize - -w -v + -w -x path @@ -124,7 +125,12 @@ smallest features we want to see in the output report. (including blank lines) to be ignored for comparison purposes (line numbers in the output report will nevertheless be correct). -The implies and also +Normally, comparator performs +insignificance filtering before emitting a span into the common-segment +report. The suppresses this, emitting all common +spans. See the discussion of significance filtering below. + +The option implies and also applies C-language-specific normalization; { and } characters are removed. This is recommended for comparing C code; it prevents the comparison from being fooled by differences in indent style. @@ -152,6 +158,25 @@ percentage of printable characters near the front of the file is above 90%. +Significance filtering + +Normally, comparator tries to +throw out common segments that are just noise. A segment is +considered noise if one of the following conditions holds: + + +Its file has a .c or .h extension, and the segment +consists entirely of whitespace, punctuation, C keywords, C include +lines, and other things that are not C identifiers, function names, or +user-defined macros. + +The file has a .sh extension or a #! first line +directing shell interpretation, and the segment consists entirely +of shell keywords and punctuation. + + + + filterator filterator is a postprocessor for the @@ -161,7 +186,7 @@ be noise. The noise test for C files is to throw away whitespace, C syntax, #include lines and a few common macros and see if anything is left. The noise test for shell files throws away Bourne-shell keywords -The suppresses noise filtering. The +The acts as it does for comparator. The option sets the minimum size of overlap to be reported. Setting this to a @@ -169,8 +194,7 @@ slightly larger number than the comparator shred size is a useful way to filter out spurious matches; thus, while comparator defaults to a shred size of 3, filterator defaults to a minimum size of -5. The enables some debugging output. It is for -developers; if you need to understand it, read the code. +5. Each filterator line beginning with % is the filename from which the following common span of lines is displayed diff --git a/filterator b/filterator index cb50fce..780e2df 100755 --- a/filterator +++ b/filterator @@ -8,7 +8,6 @@ if __name__ == '__main__': def report_common(state): "Generate a report on common code." print "Filter-Program: filterator 1.0" - print "Filtering:", ("none", "language")[dofilter] print "Hash-Method: MD5" if state.merge_program: print "Merge-Program:", state.merge_program @@ -16,8 +15,8 @@ if __name__ == '__main__': print "Shred-Size: %d" % state.shredsize if minsize: print "Minimum-Size: %d" % minsize - print 75 * '-' - sys.stdout.write(str(comparator.CommonStatistics(state))) + #print 75 * '-' + #sys.stdout.write(str(comparator.CommonStatistics(state))) print 75 * '-' for clique in state.cliques: for (file, start, end) in clique: @@ -25,18 +24,15 @@ if __name__ == '__main__': print "%% %s:%d-%d: entire (%d matches)" % \ (file, start, end, len(clique)) continue - (text_type, text) = state.extract_text(clique) print "%% %s:%d-%d: (%d matches)" % (file, start, end, len(clique)) - sys.stdout.write(state.extract_text(clique)[1]) + sys.stdout.write(state.extract_text(clique)) # Main line begins here import getopt try: - (optlist, args) = getopt.getopt(sys.argv[1:], 'd:ns:Sx') + (optlist, args) = getopt.getopt(sys.argv[1:], 'd:m') except getopt.GetoptError: - sys.stderr.write("usage: filterator [-d dir] [-m size] [-n] [-x]\n") + sys.stderr.write("usage: filterator [-d dir] [-m size]\n") sys.exit(2) - stats = debug = 0 - dofilter = 1 minsize = 5 dir = None linecounts = {} @@ -45,24 +41,12 @@ if __name__ == '__main__': dir = val elif opt == '-m': minsize = int(val) - elif opt == '-n': - dofilter = 0 - elif opt == '-S': - stats = 1 - elif opt == '-x': - debug = 1 try: state = comparator.CommonReport(sys.stdin, dir) - if minsize: - state.filter_by_size(minsize) - if dofilter: - state.filter_by_significance() - - if stats: - sys.stdout.write(str(state.statistics())) - else: - report_common(state) + #if minsize: + # state.filter_by_size(minsize) + report_common(state) except comparator.ComparatorException, e: sys.stderr.write("filterator: " + e.message + "\n") sys.exit(1) diff --git a/linebyline.c b/linebyline.c index f15611d..0547953 100644 --- a/linebyline.c +++ b/linebyline.c @@ -2,36 +2,28 @@ #include #include #include +#include #include "shred.h" static char *c_patterns[] = { /* Idioms that don't convey any meaning in isolation */ - "return *\\(?[a-z]+\\)? *;", "return *\\(?-?[01]+\\)? *;", - "goto +[a-z]+;", "exit *\\([01]\\);", + "return [a-z]+", "return -?[01]+", + "goto +[a-z]+", "exit *\\([01]\\)", /* Pragmas */ "/\\* *ARGSUSED *\\*/", "/\\* *NOTREACHED *\\*/", "/\\* *FALL *THRO?UG?H? *\\*/", /* Bare C keywords */ - " break ", " case "," continue ", - " default ", " do ", " else ", - " enum ", " if ", " goto ", - " return ", " switch ", " while ", - " enum ", " int ", " long ", - " short ", " static ", " struct ", - " typedef ", " union ", " void ", - /* Preprocessor constructs */ - "# *define","# *endif","# *else","# *if ", "# *ifdef ","# *ifndef ", - /* Comment delimiters with no content, and line continuation */ - "/\\*+", "\\*+/", "\\*+", "^ *\\s*\\n", "\\\n", + " auto ", " break ", " case "," continue ", " default ", " do ", " else ", + " enum ", " if ", " goto "," return ", " switch ", " while ", " int ", + " long ", " short ", " static ", " struct ", " typedef ", " union ", + " void ", + /* Preprocessor constructs (# has already been stripped)*/ + "^ *define","^ *endif","^ *else", "^ *ifdef ","^ *ifndef ", /* Common preprocessor macros, not significant by themselves. */ - " ASSERT ", - " FALSE ", - " NULL ", - " STATIC ", - " TRUE ", + " ASSERT ", " EXTERN ", " FALSE ", " NULL "," STATIC ", " TRUE ", /* Macro include lines are noise, too. */ - "\\s*#include.*","#\\s*line.*", + "^ *include.*","^ *line.*", /* Common error macros. */ " EFAULT ", " EINVAL ", @@ -39,32 +31,13 @@ static char *c_patterns[] = { }; static regex_t c_regexps[sizeof(c_patterns)/sizeof(*c_patterns)]; -static char c_punct[] = { - /* Punctuation and whitespace */ - '{', '}', '(', ')', '<', '>', '[', ']', - '^', '&', '|', '*', '?', '.', '+', - ';', ':', '%', ',', '-', '/', '=', '!', - ' ', '\n', '\t', '\v', -}; - static char *shell_patterns[] = { - /* Idioms that don't convey any meaning in isolation */ - "exit *[01];?", - /* Bare shell keywords */ - " break ", " case ", " done ", - " do ", " else ", " esac ", - " fi ", " if ", " return ", - " shift ", " true ", " while ", - /* Blank comment */ - "^#\n", + " break ", " case ", " done ", " do ", " else ", " esac ", " exit *[01]?", + " false ", " fi ", " for", " function", " if ", " return ", " shift ", + " true ", "until", " while ", }; static regex_t shell_regexps[sizeof(shell_patterns)/sizeof(*shell_patterns)]; -static char shell_punct[] = { - /* Punctuation and whitespace */ - ' ', ':', ';', '\n','\t', '\v', -}; - void filter_init(void) /* initialize line filtering */ { @@ -86,50 +59,53 @@ void filter_init(void) } } -static filtertype active = none; -static char *punct; +static unsigned char active = 0; static regex_t *regexps; static int nregexps; -void filter_set(filtertype newfilter) +void filter_set(int mask) { - active = newfilter; + active = mask; - if (newfilter == c) + if (mask & C_CODE) { regexps = c_regexps; - punct = c_punct; nregexps = sizeof(c_regexps)/sizeof(*c_regexps); } - else + else if (mask & SHELL_CODE) { regexps = shell_regexps; - punct = shell_punct; nregexps = sizeof(shell_regexps)/sizeof(*shell_regexps); } } int filter_pass(const char *line) +/* return flags that apply to this line */ { - if (active == none) - return(1); - else if (strspn(line, punct) == strlen(line)) - return(0); + if (active == 0) + return(SIGNIFICANT); else { char *sp, *tp; char buf[BUFSIZ]; - int changed; + int changed, significant; /* change all punctuation to spaces */ buf[0] = ' '; for (sp = (char *)line, tp = buf+1; *sp; sp++) - if (strchr(punct, *sp) && *sp != ' ') + if (ispunct(*sp) || *sp == '\n' || *sp == '\t') *tp++ = ' '; else *tp++ = *sp; *tp = '\0'; +#ifdef TEST + fprintf(stderr, "After removing punctuation: '%s'\n", buf); +#endif /* TEST */ + + if (strspn(line, " ") == strlen(line)) + return(active); + do { regex_t *re; @@ -147,12 +123,19 @@ int filter_pass(const char *line) for (start = buf+f.rm_so, end = buf+f.rm_eo; *end; end++) *start++ = *end; *start = '\0'; +#ifdef TEST + fprintf(stderr, "%d...%d -> '%s'\n", f.rm_so, f.rm_eo, buf); +#endif /* TEST */ changed++; } } } while (changed); - return !(buf[0] == '\0' || strspn(buf, " ") == strlen(buf)); + + + significant = !(buf[0] == '\0' || strspn(buf, " ") == strlen(buf)); + + return (active | (significant ? SIGNIFICANT : 0)); } } @@ -162,13 +145,10 @@ int main(int argc, char *argv[]) char buf[BUFSIZ]; filter_init(); - filter_set(c); + filter_set(C_CODE); while(fgets(buf, BUFSIZ, stdin)) { - if (filter_pass(buf)) - fputs("yes: ", stdout); - else - fputs("no: ", stdout); + printf("%02x: ", filter_pass(buf)); fputs(buf, stdout); } } diff --git a/main.c b/main.c index 83bd83c..1893626 100644 --- a/main.c +++ b/main.c @@ -10,7 +10,7 @@ #include #include "shred.h" -int verbose, debug, minsize; +int verbose, debug, minsize, nofilter; struct scf_t { @@ -28,7 +28,7 @@ static struct scf_t dummy_scf, *scflist = &dummy_scf; static struct filehdr_t dummy_filehdr, *filelist = &dummy_filehdr; -static int chunk_count, sort_count; +static int chunk_count, sort_count, dofilter; static struct hash_t *chunk_buffer; static struct sorthash_t *sort_buffer; @@ -98,7 +98,7 @@ void extend_current_chunk(void) } static void write_options(char *buf) -/* dump a Nirmalization line representing current options */ +/* dump a Normalization line representing current options */ { buf[0] = '\0'; if (remove_whitespace) @@ -173,15 +173,25 @@ static void write_scf(const char *tree, FILE *ofp) struct hash_t this = np[0]; if (debug) + { fprintf(stderr, - "%d: %s %s:%d:%d\n", + "%d: %s %s:%d:%d", np-chunk_buffer, hash_dump(this.hash), *place, this.start, this.end); + if (np->flags) + { + fputc('\t', stderr); + dump_flags(np->flags, stderr); + fprintf(stderr, " (0x%02x)", np->flags); + } + fputc('\n', stderr); + } this.start = TONET(this.start); this.end = TONET(this.end); fwrite(&this.start, sizeof(linenum_t), 1, ofp); fwrite(&this.end, sizeof(linenum_t), 1, ofp); fwrite(&this.hash, sizeof(hashval_t), 1, ofp); + fwrite(&this.flags, sizeof(flag_t), 1, ofp); } totalchunks += chunk_count; free(chunk_buffer); @@ -230,6 +240,7 @@ static void read_scf(struct scf_t *scf) fread(&this.start, sizeof(linenum_t), 1, scf->fp); fread(&this.end, sizeof(linenum_t), 1, scf->fp); fread(&this.hash, sizeof(hashval_t), 1, scf->fp); + fread(&this.flags, sizeof(flag_t), 1, scf->fp); this.start = FROMNET(this.start); this.end = FROMNET(this.end); corehook(this, filehdr); @@ -343,6 +354,18 @@ static void init_scf(char *file, struct scf_t *scf, const int readfile) } } +void dump_flags(const int flags, FILE *fp) +/* dump tokens corresponding to a flag set */ +{ + fputc(' ', fp); + if (flags & SIGNIFICANT) + fputs(" significant", fp); + if (flags & C_CODE) + fputs(" C", fp); + if (flags & SHELL_CODE) + fputs(" shell", fp); +} + void dump_array(const char *legend, struct sorthash_t *obarray, int hashcount) /* dump the contents of a sort_hash array */ @@ -351,10 +374,19 @@ void dump_array(const char *legend, fputs(legend, stdout); for (np = obarray; np < obarray + hashcount; np++) - fprintf(stdout, "%2d: %s %s:%d:%d\n", - np-obarray, - hash_dump(np->hash.hash), - np->file->name, np->hash.start, np->hash.end); + { + fprintf(stdout, "%2d: %s %s:%d:%d", + np-obarray, + hash_dump(np->hash.hash), + np->file->name, np->hash.start, np->hash.end); + if (np->hash.flags) + { + fputc('\t', stdout); + dump_flags(np->hash.flags, stdout); + fprintf(stdout, " (0x%02x)", np->hash.flags); + } + fputc('\n', stdout); + } } void report_time(char *legend, ...) @@ -397,11 +429,12 @@ static FILE *redirect(const char *outfile) static void usage(void) { - fprintf(stderr,"usage: comparator [-c] [-C] [-d dir ] [-m minsize] [-r] [-o file] [-s shredsize] [-v] [-w] [-x] path...\n"); + fprintf(stderr,"usage: comparator [-c] [-C] [-d dir ] [-m minsize] [-n] [-r] [-o file] [-s shredsize] [-v] [-w] [-x] path...\n"); fprintf(stderr," -c = generate SCF files\n"); fprintf(stderr," -C = apply C normalizations\n"); fprintf(stderr," -d dir = change directory before digesting.\n"); fprintf(stderr," -m size = set minimum size of span to be output.\n"); + fprintf(stderr," -n = suppress significance filtering.\n"); fprintf(stderr," -o file = write to the specified file.\n"); fprintf(stderr," -r = renove comments\n"); fprintf(stderr," -s size = set shred size (default %d)\n", shredsize); @@ -422,9 +455,9 @@ main(int argc, char *argv[]) struct scf_t *scf; char *dir, *outfile; - compile_only = file_only = 0; + compile_only = file_only = nofilter = 0; dir = outfile = NULL; - while ((status = getopt(argc, argv, "cCd:hm:o:rs:vwx")) != EOF) + while ((status = getopt(argc, argv, "cCd:hm:no:rs:vwx")) != EOF) { switch (status) { @@ -444,6 +477,10 @@ main(int argc, char *argv[]) minsize = atoi(optarg); break; + case 'n': + nofilter = 1; + break; + case 'o': outfile = optarg; break; @@ -484,6 +521,7 @@ main(int argc, char *argv[]) usage(); report_time(NULL); + filter_init(); /* special case if user gave exactly one tree */ if (!compile_only && argcount == 1) @@ -610,7 +648,7 @@ main(int argc, char *argv[]) puts("%%"); for (scf = scflist; scf->next; scf = scf->next) - printf("%s:%d:%d:%d\n", + printf("%s: matches=%d, matchlines=%d, totallines=%d\n", scf->name, match_count(scf->name), line_count(scf->name), diff --git a/report.c b/report.c index 763c284..5a1ff6b 100644 --- a/report.c +++ b/report.c @@ -65,6 +65,7 @@ static int merge_ranges(struct sorthash_t *p, { p[i].hash.start = min(p[i].hash.start, q[i].hash.start); p[i].hash.end = max(p[i].hash.end, q[i].hash.end); + p[i].hash.flags |= q[i].hash.flags; } return(1); } @@ -230,15 +231,15 @@ struct match_t *reduce_matches(struct sorthash_t *obarray, int *hashcountp) * The technique: first mark... */ if (SORTHASHCMP(obarray, obarray+1)) - obarray[0].hash.start = UNIQUE_FLAG; + obarray[0].hash.flags = UNIQUE_FLAG; for (np = obarray+1; np < obarray + hashcount-1; np++) if (SORTHASHCMP(np, np-1) && SORTHASHCMP(np, np+1)) - np->hash.start = UNIQUE_FLAG; + np->hash.flags = UNIQUE_FLAG; if (SORTHASHCMP(obarray+hashcount-2, obarray+hashcount-1)) - obarray[hashcount-1].hash.start = UNIQUE_FLAG; + obarray[hashcount-1].hash.flags = UNIQUE_FLAG; /* ...then sweep. */ for (mp = np = obarray; np < obarray + hashcount; np++) - if (np->hash.start != UNIQUE_FLAG) + if (np->hash.flags != UNIQUE_FLAG) *mp++ = *np; /* now we get to reduce the memory footprint */ report_time("Compaction reduced %d shreds to %d", @@ -375,24 +376,26 @@ void emit_report2(void) for (match = hitlist; match < hitlist + mergecount; match++) { - int i; + int i, flags = 0, maxsize = 0; - if (minsize) + for (i=0; i < match->nmatches; i++) { - int maxsize = 0; - - for (i=0; i < match->nmatches; i++) - { - struct sorthash_t *rp = match->matches+i; - int matchsize = rp->hash.end - rp->hash.start + 1; + struct sorthash_t *rp = match->matches+i; + int matchsize = rp->hash.end - rp->hash.start + 1; - if (matchsize >= maxsize) - maxsize = matchsize; - } - if (maxsize < minsize) - continue; + if (matchsize >= maxsize) + maxsize = matchsize; + flags |= rp->hash.flags; } + /* + * Filter for sigificance right at the last minute. The + * point of doing it this way is to allow significance bits to + * propagate through range merges. + */ + if (maxsize < minsize || !(nofilter || (flags & SIGNIFICANT))) + continue; + for (i=0; i < match->nmatches; i++) { struct sorthash_t *rp = match->matches+i; @@ -433,7 +436,7 @@ int line_count(const char *name) for (match = hitlist; match < hitlist + mergecount; match++) for (i=0; i < match->nmatches; i++) - if (strncmp(name, match->matches[i].file->name, strlen(name))) + if (!strncmp(name, match->matches[i].file->name, strlen(name))) { count += match->matches[i].hash.end - match->matches[i].hash.start + 1; break; diff --git a/scf-standard.xml b/scf-standard.xml index 56dfad2..2ef6078 100644 --- a/scf-standard.xml +++ b/scf-standard.xml @@ -273,8 +273,8 @@ Rivest XOR hash; MD5 is also a legal value. -Comment: (optional) -Arbitrary comment text for human eyes. +Matches: (mandatory) +Count of common segments in the file. @@ -286,8 +286,26 @@ records. The length of the data section is drtivable from the data lengths. A shred record consists of ushorts (start and end line numbers) -followed by a fixed-length block of hash data. For the default RXOR -hash the data is 8 bytes; for MD5, it is 16. +followed by a fixed-length block of hash data, followed by a flag +byte. For the default RXOR hash the data is 8 bytes; for MD5, it is +16. + +Defined flags are: + + + +0x40 +This chunk is deemed significant. + + +0x01 +This chunk appears to be C code + + +0x02 +This chunk appears to be shell code. + + Shreds should be ordered by start line number. Empty files should be skipped, and nonempty files should always have at least one shred. @@ -336,29 +354,31 @@ discarded. comparisons. + +The data section consists of a tree-properties block followed by +a sequence of range sets. The tree-properties block consists of any +number of property lines followed by a %%\n section marker. Each +property line consists of a tree name, followed by a set of +comma-separated property settings. Each property setting consists of +a property, followed by an equal sign, followed by a value. The +following properties are defined: + + + +matches +the count of chunks containing files from the tree + + +matchlines +the count of common lines from the tree + -Comment: (optional) -Arbitrary comment text for human eyes. +totallines +the total line count of the tree -The data section consists of a statistics block followed by a -sequence of range sets. The statistics block consists of any number -of count lines followed by a %%\n section marker. Each linecount line -consists of four colon-separated fields, - - -The name of a tree -A count of chunks containing files from the tree -A count of common lines from the tree -The total line count of the tree - - - - -a tree name and a line count. - Each range set consists of two or more ranges followed by a line containing a %%\n section marker. A range is represented as four tab-separated fields: filename, start line, end line, and length of diff --git a/shred.h b/shred.h index 33d6a7a..3270382 100644 --- a/shred.h +++ b/shred.h @@ -18,17 +18,24 @@ typedef u_int32_t linenum_t; #define FROMNET ntohl #endif #define MAX_LINENUM (linenum_t)-1 /* 2s-complement assumption */ -#define UNIQUE_FLAG MAX_LINENUM /* 2s-complement assumption */ /* use this to hold total line count of the entire source tree set */ typedef u_int32_t linecount_t; +typedef unsigned char flag_t; + #include "hash.h" struct hash_t { linenum_t start, end; hashval_t hash; + flag_t flags; +#define SIGNIFICANT 0x40 /* something in this is not pure syntax */ +#define C_CODE 0x01 /* identified as C code */ +#define SHELL_CODE 0x02 /* identified as shell code */ +#define CATEGORIZED 0x03 /* we can significance-test this */ +#define UNIQUE_FLAG 0x80 /* internal use only */ }; #define SORTHASHCMP(s, t) hash_compare((s)->hash.hash, (t)->hash.hash) @@ -49,7 +56,7 @@ struct sorthash_t extern int remove_braces; extern int remove_whitespace; extern int remove_comments; -extern int verbose, debug; +extern int verbose, debug, nofilter; extern int shredsize, minsize; /* main.c functions */ @@ -59,6 +66,7 @@ extern void corehook(struct hash_t hash, struct filehdr_t *file); extern void extend_current_chunk(void); extern void dump_array(const char *legend, struct sorthash_t *obarray, int hashcount); +extern void dump_flags(const int flags, FILE *fp); /* shredtree.c functions */ extern char **sorted_file_list(const char *, int *); @@ -66,6 +74,11 @@ extern int shredfile(struct filehdr_t *, void (*hook)(struct hash_t, struct filehdr_t *)); extern void sort_hashes(struct sorthash_t *hashlist, int hashcount); +/* filter.c functions */ +extern void filter_init(void); +extern void filter_set(int); +extern int filter_pass(const char *line); + /* shredcompare.c functions */ extern void emit_report1(struct sorthash_t *obarray, int hashcount); extern void emit_report2(void); diff --git a/shredtree.c b/shredtree.c index 8c1e701..a04537b 100644 --- a/shredtree.c +++ b/shredtree.c @@ -122,7 +122,8 @@ static int normalize(char *buf) typedef struct { char *line; - int start; + linenum_t start; + flag_t flags; } shred; @@ -133,22 +134,24 @@ static struct hash_t emit_chunk(shred *display, int linecount) struct hash_t out; /* build completed chunk onto end of array */ + out.flags = 0; hash_init(); + firstline = shredsize; + for (i = shredsize - 1; i >= 0; i--) + if (display[i].line) + firstline = i; + firstline = display[firstline].start; if (debug) - fprintf(stderr, "Chunk:\n"); + fprintf(stderr, "Chunk at line %d:\n", firstline); for (i = 0; i < shredsize; i++) if (display[i].line) { if (debug) - fprintf(stderr, "%d: '%s'\n", i, display[i].line); + fprintf(stderr, "%d (%02x): '%s'\n", i, display[i].flags, display[i].line); hash_update(display[i].line, strlen(display[i].line)); + out.flags |= display[i].flags; } hash_complete(&out.hash); - firstline = shredsize; - for (i = shredsize - 1; i >= 0; i--) - if (display[i].line) - firstline = i; - firstline = display[firstline].start; out.start = firstline; out.end = linecount; @@ -171,6 +174,15 @@ int shredfile(struct filehdr_t *file, exit(1); } + /* deduce what filtering type we should use */ +#define endswith(suff) !strcmp(suff,file->name+strlen(file->name)-strlen(suff)) + filter_set(0); + if (endswith(".c") || endswith(".h")) + filter_set(C_CODE); + else if (endswith(".sh")) + filter_set(SHELL_CODE); +#undef endswith + display = (shred *)calloc(sizeof(shred), shredsize); accepted = linecount = 0; @@ -208,9 +220,15 @@ int shredfile(struct filehdr_t *file, } accepted++; + /* maybe we can get the file type from the first line? */ + if (linecount == 1 && buf[0] == '#') + if (strstr(buf, "sh")) + filter_set(SHELL_CODE); + /* create new shred */ display[shredsize-1].line = strdup(buf); display[shredsize-1].start = linecount; + display[shredsize-1].flags = filter_pass(buf); /* flush completed chunk */ if (accepted >= shredsize) @@ -221,6 +239,7 @@ int shredfile(struct filehdr_t *file, for (i=1; i < shredsize; i++) display[i-1] = display[i]; display[shredsize-1].line = NULL; + display[shredsize-1].flags = 0; } if (accepted && accepted < shredsize) hook(emit_chunk(display, linecount), file); -- 2.43.0