git-core-*/?*
test-date
test-delta
+test-gsimm
common-cmds.h
*.tar.gz
*.dsc
test-delta$X: test-delta.c diff-delta.o patch-delta.o
$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $^ -lz
+test-gsimm$X: test-gsimm.c gsimm.o rabinpoly.o
+ $(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $^
+
check:
for i in *.c; do sparse $(ALL_CFLAGS) $(SPARSE_FLAGS) $$i || exit; done
rm -f *.o mozilla-sha1/*.o arm/*.o ppc/*.o compat/*.o xdiff/*.o \
$(LIB_FILE) $(XDIFF_LIB)
rm -f $(ALL_PROGRAMS) $(BUILT_INS) git$X
+ rm -f test-date$X test-delta$X test-gsimm$X
rm -f *.spec *.pyc *.pyo */*.pyc */*.pyo common-cmds.h TAGS tags
rm -rf $(GIT_TARNAME)
rm -f $(GIT_TARNAME).tar.gz git-core_$(GIT_VERSION)-*.tar.gz
CMIT_FMT_FULL,
CMIT_FMT_FULLER,
CMIT_FMT_ONELINE,
+
+ CMIT_FMT_UNSPECIFIED,
};
extern enum cmit_fmt get_commit_format(const char *arg);
#include "commit.h"
#include "log-tree.h"
-static struct log_tree_opt log_tree_opt;
+static struct rev_info log_tree_opt;
static int diff_tree_commit_sha1(const unsigned char *sha1)
{
{
int nr_sha1;
char line[1000];
- unsigned char sha1[2][20];
- const char *prefix = setup_git_directory();
- static struct log_tree_opt *opt = &log_tree_opt;
+ struct object *tree1, *tree2;
+ static struct rev_info *opt = &log_tree_opt;
+ struct object_list *list;
int read_stdin = 0;
git_config(git_diff_config);
nr_sha1 = 0;
- init_log_tree_opt(opt);
+ init_revisions(opt);
+ opt->abbrev = 0;
+ argc = setup_revisions(argc, argv, opt, NULL);
- for (;;) {
- int opt_cnt;
- const char *arg;
+ while (--argc > 0) {
+ const char *arg = *++argv;
- argv++;
- argc--;
- arg = *argv;
- if (!arg)
- break;
-
- if (*arg != '-') {
- if (nr_sha1 < 2 && !get_sha1(arg, sha1[nr_sha1])) {
- nr_sha1++;
- continue;
- }
- break;
- }
-
- opt_cnt = log_tree_opt_parse(opt, argv, argc);
- if (opt_cnt < 0)
- usage(diff_tree_usage);
- else if (opt_cnt) {
- argv += opt_cnt - 1;
- argc -= opt_cnt - 1;
- continue;
- }
-
- if (!strcmp(arg, "--")) {
- argv++;
- argc--;
- break;
- }
if (!strcmp(arg, "--stdin")) {
read_stdin = 1;
continue;
usage(diff_tree_usage);
}
- if (opt->combine_merges)
- opt->ignore_merges = 0;
-
- /* We can only do dense combined merges with diff output */
- if (opt->dense_combined_merges)
- opt->diffopt.output_format = DIFF_FORMAT_PATCH;
-
- if (opt->diffopt.output_format == DIFF_FORMAT_PATCH)
- opt->diffopt.recursive = 1;
-
- diff_tree_setup_paths(get_pathspec(prefix, argv), &opt->diffopt);
- diff_setup_done(&opt->diffopt);
+ /*
+ * NOTE! "setup_revisions()" will have inserted the revisions
+ * it parsed in reverse order. So if you do
+ *
+ * git-diff-tree a b
+ *
+ * the commit list will be "b" -> "a" -> NULL, so we reverse
+ * the order of the objects if the first one is not marked
+ * UNINTERESTING.
+ */
+ nr_sha1 = 0;
+ list = opt->pending_objects;
+ if (list) {
+ nr_sha1++;
+ tree1 = list->item;
+ list = list->next;
+ if (list) {
+ nr_sha1++;
+ tree2 = tree1;
+ tree1 = list->item;
+ if (list->next)
+ usage(diff_tree_usage);
+ /* Switch them around if the second one was uninteresting.. */
+ if (tree2->flags & UNINTERESTING) {
+ struct object *tmp = tree2;
+ tree2 = tree1;
+ tree1 = tmp;
+ }
+ }
+ }
switch (nr_sha1) {
case 0:
usage(diff_tree_usage);
break;
case 1:
- diff_tree_commit_sha1(sha1[0]);
+ diff_tree_commit_sha1(tree1->sha1);
break;
case 2:
- diff_tree_sha1(sha1[0], sha1[1], "", &opt->diffopt);
+ diff_tree_sha1(tree1->sha1,
+ tree2->sha1,
+ "", &opt->diffopt);
log_tree_diff_flush(opt);
break;
}
#define LOGSIZE (65536)
-static int cmd_log(int argc, const char **argv, char **envp)
+static int cmd_log_wc(int argc, const char **argv, char **envp,
+ struct rev_info *rev)
{
- struct rev_info rev;
struct commit *commit;
char *buf = xmalloc(LOGSIZE);
- static enum cmit_fmt commit_format = CMIT_FMT_DEFAULT;
- int abbrev = DEFAULT_ABBREV;
- int abbrev_commit = 0;
const char *commit_prefix = "commit ";
- struct log_tree_opt opt;
int shown = 0;
- int do_diff = 0;
- int full_diff = 0;
-
- init_log_tree_opt(&opt);
- argc = setup_revisions(argc, argv, &rev, "HEAD");
- while (1 < argc) {
- const char *arg = argv[1];
- if (!strncmp(arg, "--pretty", 8)) {
- commit_format = get_commit_format(arg + 8);
- if (commit_format == CMIT_FMT_ONELINE)
- commit_prefix = "";
- }
- else if (!strcmp(arg, "--no-abbrev")) {
- abbrev = 0;
- }
- else if (!strcmp(arg, "--abbrev")) {
- abbrev = DEFAULT_ABBREV;
- }
- else if (!strcmp(arg, "--abbrev-commit")) {
- abbrev_commit = 1;
- }
- else if (!strncmp(arg, "--abbrev=", 9)) {
- abbrev = strtoul(arg + 9, NULL, 10);
- if (abbrev && abbrev < MINIMUM_ABBREV)
- abbrev = MINIMUM_ABBREV;
- else if (40 < abbrev)
- abbrev = 40;
- }
- else if (!strcmp(arg, "--full-diff")) {
- do_diff = 1;
- full_diff = 1;
- }
- else {
- int cnt = log_tree_opt_parse(&opt, argv+1, argc-1);
- if (0 < cnt) {
- do_diff = 1;
- argv += cnt;
- argc -= cnt;
- continue;
- }
- die("unrecognized argument: %s", arg);
- }
- argc--; argv++;
- }
+ rev->abbrev = DEFAULT_ABBREV;
+ rev->commit_format = CMIT_FMT_DEFAULT;
+ argc = setup_revisions(argc, argv, rev, "HEAD");
- if (do_diff) {
- opt.diffopt.abbrev = abbrev;
- opt.verbose_header = 0;
- opt.always_show_header = 0;
- opt.no_commit_id = 1;
- if (opt.combine_merges)
- opt.ignore_merges = 0;
- if (opt.dense_combined_merges)
- opt.diffopt.output_format = DIFF_FORMAT_PATCH;
- if (opt.diffopt.output_format == DIFF_FORMAT_PATCH)
- opt.diffopt.recursive = 1;
- if (!full_diff && rev.prune_data)
- diff_tree_setup_paths(rev.prune_data, &opt.diffopt);
- diff_setup_done(&opt.diffopt);
- }
+ if (argc > 1)
+ die("unrecognized argument: %s", argv[1]);
+ if (rev->commit_format == CMIT_FMT_ONELINE)
+ commit_prefix = "";
- prepare_revision_walk(&rev);
+ prepare_revision_walk(rev);
setup_pager();
- while ((commit = get_revision(&rev)) != NULL) {
- if (shown && do_diff && commit_format != CMIT_FMT_ONELINE)
+ while ((commit = get_revision(rev)) != NULL) {
+ unsigned long ofs = 0;
+
+ if (shown && rev->diff &&
+ rev->commit_format != CMIT_FMT_ONELINE)
putchar('\n');
- fputs(commit_prefix, stdout);
- if (abbrev_commit && abbrev)
- fputs(find_unique_abbrev(commit->object.sha1, abbrev),
- stdout);
+
+ ofs = sprintf(buf, "%s", commit_prefix);
+ if (rev->abbrev_commit && rev->abbrev)
+ ofs += sprintf(buf + ofs, "%s",
+ find_unique_abbrev(commit->object.sha1,
+ rev->abbrev));
else
- fputs(sha1_to_hex(commit->object.sha1), stdout);
- if (rev.parents) {
+ ofs += sprintf(buf + ofs, "%s",
+ sha1_to_hex(commit->object.sha1));
+ if (rev->parents) {
struct commit_list *parents = commit->parents;
while (parents) {
struct object *o = &(parents->item->object);
parents = parents->next;
if (o->flags & TMP_MARK)
continue;
- printf(" %s", sha1_to_hex(o->sha1));
+ ofs += sprintf(buf + ofs, " %s",
+ sha1_to_hex(o->sha1));
o->flags |= TMP_MARK;
}
/* TMP_MARK is a general purpose flag that can
parents = parents->next)
parents->item->object.flags &= ~TMP_MARK;
}
- if (commit_format == CMIT_FMT_ONELINE)
- putchar(' ');
- else
- putchar('\n');
- pretty_print_commit(commit_format, commit, ~0, buf,
- LOGSIZE, abbrev);
- printf("%s\n", buf);
- if (do_diff) {
- printf("---\n");
- log_tree_commit(&opt, commit);
+ buf[ofs++] =
+ (rev->commit_format == CMIT_FMT_ONELINE) ? ' ' : '\n';
+ ofs += pretty_print_commit(rev->commit_format, commit, ~0,
+ buf + ofs,
+ LOGSIZE - ofs - 20,
+ rev->abbrev);
+
+ if (rev->diff) {
+ rev->use_precomputed_header = buf;
+ strcpy(buf + ofs, "\n---\n");
+ log_tree_commit(rev, commit);
}
+ else
+ printf("%s\n", buf);
shown = 1;
free(commit->buffer);
commit->buffer = NULL;
return 0;
}
+static int cmd_wc(int argc, const char **argv, char **envp)
+{
+ struct rev_info rev;
+
+ init_revisions(&rev);
+ rev.diff = 1;
+ rev.diffopt.recursive = 1;
+ return cmd_log_wc(argc, argv, envp, &rev);
+}
+
+static int cmd_show(int argc, const char **argv, char **envp)
+{
+ struct rev_info rev;
+
+ init_revisions(&rev);
+ rev.diff = 1;
+ rev.diffopt.recursive = 1;
+ rev.combine_merges = 1;
+ rev.dense_combined_merges = 1;
+ rev.always_show_header = 1;
+ rev.ignore_merges = 0;
+ rev.no_walk = 1;
+ return cmd_log_wc(argc, argv, envp, &rev);
+}
+
+static int cmd_log(int argc, const char **argv, char **envp)
+{
+ struct rev_info rev;
+
+ init_revisions(&rev);
+ rev.always_show_header = 1;
+ rev.diffopt.recursive = 1;
+ rev.combine_merges = 1;
+ rev.ignore_merges = 0;
+ return cmd_log_wc(argc, argv, envp, &rev);
+}
+
static void handle_internal_command(int argc, const char **argv, char **envp)
{
const char *cmd = argv[0];
{ "version", cmd_version },
{ "help", cmd_help },
{ "log", cmd_log },
+ { "whatchanged", cmd_wc },
+ { "show", cmd_show },
};
int i;
--- /dev/null
+#include "rabinpoly.h"
+#include "gsimm.h"
+
+/* Has to be power of two. Since the Rabin hash only has 63
+ usable bits, the number of hashes is limited to 32.
+ Lower powers of two could be used for speeding up processing
+ of very large files. */
+#define NUM_HASHES_PER_CHAR 32
+
+/* Size of cache used to eliminate duplicate substrings.
+ Make small enough to comfortably fit in L1 cache. */
+#define DUP_CACHE_SIZE 256
+
+/* For the final counting, do not count each bit individually, but
+ group them. Must be power of two, at most NUM_HASHES_PER_CHAR.
+ However, larger sizes result in higher cache usage. Use 8 bits
+ per group for efficient processing of large files on fast machines
+ with decent caches, or 4 bits for faster processing of small files
+ and for machines with small caches. */
+#define GROUP_BITS 4
+#define GROUP_COUNTERS (1<<GROUP_BITS)
+
+static void freq_to_md(u_char *md, int *freq)
+{ int j, k;
+
+ for (j = 0; j < MD_LENGTH; j++)
+ { u_char ch = 0;
+
+ for (k = 0; k < 8; k++) ch = 2*ch + (freq[8*j+k] > 0);
+ md[j] = ch;
+ }
+ bzero (freq, sizeof(freq[0]) * MD_BITS);
+}
+
+void gb_simm_process(u_char *data, unsigned len, u_char *md)
+{ size_t j = 0;
+ u_int32_t ofs;
+ u_int32_t dup_cache[DUP_CACHE_SIZE];
+ u_int32_t count [MD_BITS * (GROUP_COUNTERS/GROUP_BITS)];
+ int freq[MD_BITS];
+
+ bzero (freq, sizeof(freq[0]) * MD_BITS);
+ bzero (dup_cache, DUP_CACHE_SIZE * sizeof (u_int32_t));
+ bzero (count, (MD_BITS * (GROUP_COUNTERS/GROUP_BITS) * sizeof (u_int32_t)));
+
+ /* Ignore incomplete substrings */
+ while (j < len && j < RABIN_WINDOW_SIZE) rabin_slide8 (data[j++]);
+
+ while (j < len)
+ { u_int64_t hash;
+ u_int32_t ofs, sum;
+ u_char idx;
+ int k;
+
+ hash = rabin_slide8 (data[j++]);
+
+ /* In order to update a much larger frequency table
+ with only 32 bits of checksum, randomly select a
+ part of the table to update. The selection should
+ only depend on the content of the represented data,
+ and be independent of the bits used for the update.
+
+ Instead of updating 32 individual counters, process
+ the checksum in MD_BITS / GROUP_BITS groups of
+ GROUP_BITS bits, and count the frequency of each bit pattern.
+ */
+
+ idx = (hash >> 32);
+ sum = (u_int32_t) hash;
+ ofs = idx % (MD_BITS / NUM_HASHES_PER_CHAR) * NUM_HASHES_PER_CHAR;
+ idx %= DUP_CACHE_SIZE;
+ if (dup_cache[idx] != sum)
+ { dup_cache[idx] = sum;
+ for (k = 0; k < NUM_HASHES_PER_CHAR / GROUP_BITS; k++)
+ { count[ofs * GROUP_COUNTERS / GROUP_BITS + (sum % GROUP_COUNTERS)]++;
+ ofs += GROUP_BITS;
+ sum >>= GROUP_BITS;
+ } } }
+
+ /* Distribute the occurrences of each bit group over the frequency table. */
+ for (ofs = 0; ofs < MD_BITS; ofs += GROUP_BITS)
+ { int j;
+ for (j = 0; j < GROUP_COUNTERS; j++)
+ { int k;
+ for (k = 0; k < GROUP_BITS; k++)
+ { freq[ofs + k] += ((1<<k) & j)
+ ? count[ofs * GROUP_COUNTERS / GROUP_BITS + j]
+ : -count[ofs * GROUP_COUNTERS / GROUP_BITS + j];
+ } } }
+
+ if (md)
+ { rabin_reset();
+ freq_to_md (md, freq);
+} }
--- /dev/null
+#ifndef GSIMM_H
+#define GSIMM_H
+
+/* Length of file message digest (MD) in bytes. Longer MD's are
+ better, but increase processing time for diminishing returns.
+ Must be multiple of NUM_HASHES_PER_CHAR / 8, and at least 24
+ for good results
+*/
+#define MD_LENGTH 32
+#define MD_BITS (MD_LENGTH * 8)
+
+/* The MIN_FILE_SIZE indicates the absolute minimal file size that
+ can be processed. As indicated above, the first and last
+ RABIN_WINDOW_SIZE - 1 bytes are skipped.
+ In order to get at least an average of 12 samples
+ per bit in the final message digest, require at least 3 * MD_LENGTH
+ complete windows in the file. */
+#define MIN_FILE_SIZE (3 * MD_LENGTH + 2 * (RABIN_WINDOW_SIZE - 1))
+
+/* Limit matching algorithm to files less than 256 MB, so we can use
+ 32 bit integers everywhere without fear of overflow. For larger
+ files we should add logic to mmap the file by piece and accumulate
+ the frequency counts. */
+#define MAX_FILE_SIZE (256*1024*1024 - 1)
+
+void gb_simm_process(u_char *data, unsigned len, u_char *md);
+
+#endif
commit_argv[3] = old_sha1_hex;
commit_argc++;
}
+ init_revisions(&revs);
setup_revisions(commit_argc, commit_argv, &revs, NULL);
free(new_sha1_hex);
if (old_sha1_hex) {
#include "commit.h"
#include "log-tree.h"
-void init_log_tree_opt(struct log_tree_opt *opt)
-{
- memset(opt, 0, sizeof *opt);
- opt->ignore_merges = 1;
- opt->header_prefix = "";
- opt->commit_format = CMIT_FMT_RAW;
- diff_setup(&opt->diffopt);
-}
-
-int log_tree_opt_parse(struct log_tree_opt *opt, const char **av, int ac)
-{
- const char *arg;
- int cnt = diff_opt_parse(&opt->diffopt, av, ac);
- if (0 < cnt)
- return cnt;
- arg = *av;
- if (!strcmp(arg, "-r"))
- opt->diffopt.recursive = 1;
- else if (!strcmp(arg, "-t")) {
- opt->diffopt.recursive = 1;
- opt->diffopt.tree_in_recursive = 1;
- }
- else if (!strcmp(arg, "-m"))
- opt->ignore_merges = 0;
- else if (!strcmp(arg, "-c"))
- opt->combine_merges = 1;
- else if (!strcmp(arg, "--cc")) {
- opt->dense_combined_merges = 1;
- opt->combine_merges = 1;
- }
- else if (!strcmp(arg, "-v")) {
- opt->verbose_header = 1;
- opt->header_prefix = "diff-tree ";
- }
- else if (!strncmp(arg, "--pretty", 8)) {
- opt->verbose_header = 1;
- opt->header_prefix = "diff-tree ";
- opt->commit_format = get_commit_format(arg+8);
- }
- else if (!strcmp(arg, "--root"))
- opt->show_root_diff = 1;
- else if (!strcmp(arg, "--no-commit-id"))
- opt->no_commit_id = 1;
- else if (!strcmp(arg, "--always"))
- opt->always_show_header = 1;
- else
- return 0;
- return 1;
-}
-
-int log_tree_diff_flush(struct log_tree_opt *opt)
+int log_tree_diff_flush(struct rev_info *opt)
{
diffcore_std(&opt->diffopt);
if (diff_queue_is_empty()) {
return 1;
}
-static int diff_root_tree(struct log_tree_opt *opt,
+static int diff_root_tree(struct rev_info *opt,
const unsigned char *new, const char *base)
{
int retval;
return retval;
}
-static const char *generate_header(struct log_tree_opt *opt,
+static const char *get_header(struct rev_info *opt,
const unsigned char *commit_sha1,
const unsigned char *parent_sha1,
const struct commit *commit)
int abbrev = opt->diffopt.abbrev;
const char *msg = commit->buffer;
+ if (opt->use_precomputed_header)
+ return opt->use_precomputed_header;
+
if (!opt->verbose_header)
return sha1_to_hex(commit_sha1);
offset += pretty_print_commit(opt->commit_format, commit, len,
this_header + offset,
sizeof(this_header) - offset, abbrev);
+ return this_header;
+}
+
+static const char *generate_header(struct rev_info *opt,
+ const unsigned char *commit_sha1,
+ const unsigned char *parent_sha1,
+ const struct commit *commit)
+{
+ const char *header = get_header(opt, commit_sha1, parent_sha1, commit);
+
if (opt->always_show_header) {
- puts(this_header);
- return NULL;
+ puts(header);
+ header = NULL;
}
- return this_header;
+ return header;
}
-static int do_diff_combined(struct log_tree_opt *opt, struct commit *commit)
+static int do_diff_combined(struct rev_info *opt, struct commit *commit)
{
unsigned const char *sha1 = commit->object.sha1;
return 0;
}
-int log_tree_commit(struct log_tree_opt *opt, struct commit *commit)
+int log_tree_commit(struct rev_info *opt, struct commit *commit)
{
struct commit_list *parents;
unsigned const char *sha1 = commit->object.sha1;
#ifndef LOG_TREE_H
#define LOG_TREE_H
-struct log_tree_opt {
- struct diff_options diffopt;
- int show_root_diff;
- int no_commit_id;
- int verbose_header;
- int ignore_merges;
- int combine_merges;
- int dense_combined_merges;
- int always_show_header;
- const char *header_prefix;
- const char *header;
- enum cmit_fmt commit_format;
-};
+#include "revision.h"
-void init_log_tree_opt(struct log_tree_opt *);
-int log_tree_diff_flush(struct log_tree_opt *);
-int log_tree_commit(struct log_tree_opt *, struct commit *);
-int log_tree_opt_parse(struct log_tree_opt *, const char **, int);
+void init_log_tree_opt(struct rev_info *);
+int log_tree_diff_flush(struct rev_info *);
+int log_tree_commit(struct rev_info *, struct commit *);
+int log_tree_opt_parse(struct rev_info *, const char **, int);
#endif
return;
if (!pager)
pager = "less";
- else if (!*pager)
+ else if (!*pager || !strcmp(pager, "cat"))
return;
if (pipe(fd) < 0)
--- /dev/null
+/*
+ *
+ * Copyright (C) 1999 David Mazieres (dm@uun.org)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2, or (at
+ * your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
+ * USA
+ *
+ */
+
+ /* Faster generic_fls */
+ /* (c) 2002, D.Phillips and Sistina Software */
+
+#include "rabinpoly.h"
+#define MSB64 0x8000000000000000ULL
+
+static inline unsigned fls8(unsigned n)
+{
+ return n & 0xf0?
+ n & 0xc0? (n >> 7) + 7: (n >> 5) + 5:
+ n & 0x0c? (n >> 3) + 3: n - ((n + 1) >> 2);
+}
+
+static inline unsigned fls16(unsigned n)
+{
+ return n & 0xff00? fls8(n >> 8) + 8: fls8(n);
+}
+
+static inline unsigned fls32(unsigned n)
+{
+ return n & 0xffff0000? fls16(n >> 16) + 16: fls16(n);
+}
+
+static inline unsigned fls64(unsigned long long n) /* should be u64 */
+{
+ return n & 0xffffffff00000000ULL? fls32(n >> 32) + 32: fls32(n);
+}
+
+
+static u_int64_t polymod (u_int64_t nh, u_int64_t nl, u_int64_t d);
+static void polymult (u_int64_t *php, u_int64_t *plp,
+ u_int64_t x, u_int64_t y);
+static u_int64_t polymmult (u_int64_t x, u_int64_t y, u_int64_t d);
+
+static u_int64_t poly = 0xb15e234bd3792f63ull; // Actual polynomial
+static u_int64_t T[256]; // Lookup table for mod
+static int shift;
+
+u_int64_t append8 (u_int64_t p, u_char m)
+{ return ((p << 8) | m) ^ T[p >> shift];
+}
+
+static u_int64_t
+polymod (u_int64_t nh, u_int64_t nl, u_int64_t d)
+{ int i, k;
+ assert (d);
+ k = fls64 (d) - 1;
+ d <<= 63 - k;
+
+ if (nh) {
+ if (nh & MSB64)
+ nh ^= d;
+ for (i = 62; i >= 0; i--)
+ if (nh & 1ULL << i) {
+ nh ^= d >> (63 - i);
+ nl ^= d << (i + 1);
+ }
+ }
+ for (i = 63; i >= k; i--)
+ if (nl & 1ULL << i)
+ nl ^= d >> (63 - i);
+ return nl;
+}
+
+static void
+polymult (u_int64_t *php, u_int64_t *plp, u_int64_t x, u_int64_t y)
+{ int i;
+ u_int64_t ph = 0, pl = 0;
+ if (x & 1)
+ pl = y;
+ for (i = 1; i < 64; i++)
+ if (x & (1ULL << i)) {
+ ph ^= y >> (64 - i);
+ pl ^= y << i;
+ }
+ if (php)
+ *php = ph;
+ if (plp)
+ *plp = pl;
+}
+
+static u_int64_t
+polymmult (u_int64_t x, u_int64_t y, u_int64_t d)
+{
+ u_int64_t h, l;
+ polymult (&h, &l, x, y);
+ return polymod (h, l, d);
+}
+
+static int size = RABIN_WINDOW_SIZE;
+static u_int64_t fingerprint = 0;
+static int bufpos = -1;
+static u_int64_t U[256];
+static u_char buf[RABIN_WINDOW_SIZE];
+
+void rabin_init ()
+{ u_int64_t sizeshift = 1;
+ u_int64_t T1;
+ int xshift;
+ int i, j;
+ assert (poly >= 0x100);
+ xshift = fls64 (poly) - 1;
+ shift = xshift - 8;
+ T1 = polymod (0, 1ULL << xshift, poly);
+ for (j = 0; j < 256; j++)
+ T[j] = polymmult (j, T1, poly) | ((u_int64_t) j << xshift);
+
+ for (i = 1; i < size; i++)
+ sizeshift = append8 (sizeshift, 0);
+ for (i = 0; i < 256; i++)
+ U[i] = polymmult (i, sizeshift, poly);
+ bzero (buf, sizeof (buf));
+}
+
+void
+rabin_reset ()
+{ rabin_init();
+ fingerprint = 0;
+ bzero (buf, sizeof (buf));
+}
+
+u_int64_t
+rabin_slide8 (u_char m)
+{ u_char om;
+ if (++bufpos >= size) bufpos = 0;
+
+ om = buf[bufpos];
+ buf[bufpos] = m;
+ fingerprint = append8 (fingerprint ^ U[om], m);
+
+ return fingerprint;
+}
+
--- /dev/null
+/*
+ *
+ * Copyright (C) 2000 David Mazieres (dm@uun.org)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2, or (at
+ * your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
+ * USA
+ *
+ * Translated to C and simplified by Geert Bosch (bosch@gnat.com)
+ */
+
+#include <assert.h>
+#include <strings.h>
+#include <sys/types.h>
+
+#ifndef RABIN_WINDOW_SIZE
+#define RABIN_WINDOW_SIZE 48
+#endif
+void rabin_reset();
+u_int64_t rabin_slide8(u_char c);
struct rev_info revs;
static int bisect_list = 0;
-static int verbose_header = 0;
-static int abbrev = DEFAULT_ABBREV;
-static int abbrev_commit = 0;
static int show_timestamp = 0;
static int hdr_termination = 0;
-static const char *commit_prefix = "";
-static enum cmit_fmt commit_format = CMIT_FMT_RAW;
static void show_commit(struct commit *commit)
{
if (show_timestamp)
printf("%lu ", commit->date);
- if (commit_prefix[0])
- fputs(commit_prefix, stdout);
+ if (*revs.header_prefix)
+ fputs(revs.header_prefix, stdout);
if (commit->object.flags & BOUNDARY)
putchar('-');
- if (abbrev_commit && abbrev)
- fputs(find_unique_abbrev(commit->object.sha1, abbrev), stdout);
+ if (revs.abbrev_commit && revs.abbrev)
+ fputs(find_unique_abbrev(commit->object.sha1, revs.abbrev),
+ stdout);
else
fputs(sha1_to_hex(commit->object.sha1), stdout);
if (revs.parents) {
parents = parents->next)
parents->item->object.flags &= ~TMP_MARK;
}
- if (commit_format == CMIT_FMT_ONELINE)
+ if (revs.commit_format == CMIT_FMT_ONELINE)
putchar(' ');
else
putchar('\n');
- if (verbose_header) {
+ if (revs.verbose_header) {
static char pretty_header[16384];
- pretty_print_commit(commit_format, commit, ~0, pretty_header, sizeof(pretty_header), abbrev);
+ pretty_print_commit(revs.commit_format, commit, ~0,
+ pretty_header, sizeof(pretty_header),
+ revs.abbrev);
printf("%s%c", pretty_header, hdr_termination);
}
fflush(stdout);
struct commit_list *list;
int i;
+ init_revisions(&revs);
+ revs.abbrev = 0;
+ revs.commit_format = CMIT_FMT_UNSPECIFIED;
argc = setup_revisions(argc, argv, &revs, NULL);
for (i = 1 ; i < argc; i++) {
const char *arg = argv[i];
- /* accept -<digit>, like traditilnal "head" */
- if ((*arg == '-') && isdigit(arg[1])) {
- revs.max_count = atoi(arg + 1);
- continue;
- }
- if (!strcmp(arg, "-n")) {
- if (++i >= argc)
- die("-n requires an argument");
- revs.max_count = atoi(argv[i]);
- continue;
- }
- if (!strncmp(arg,"-n",2)) {
- revs.max_count = atoi(arg + 2);
- continue;
- }
if (!strcmp(arg, "--header")) {
- verbose_header = 1;
- continue;
- }
- if (!strcmp(arg, "--no-abbrev")) {
- abbrev = 0;
- continue;
- }
- if (!strcmp(arg, "--abbrev")) {
- abbrev = DEFAULT_ABBREV;
- continue;
- }
- if (!strcmp(arg, "--abbrev-commit")) {
- abbrev_commit = 1;
- continue;
- }
- if (!strncmp(arg, "--abbrev=", 9)) {
- abbrev = strtoul(arg + 9, NULL, 10);
- if (abbrev && abbrev < MINIMUM_ABBREV)
- abbrev = MINIMUM_ABBREV;
- else if (40 < abbrev)
- abbrev = 40;
- continue;
- }
- if (!strncmp(arg, "--pretty", 8)) {
- commit_format = get_commit_format(arg+8);
- verbose_header = 1;
- hdr_termination = '\n';
- if (commit_format == CMIT_FMT_ONELINE)
- commit_prefix = "";
- else
- commit_prefix = "commit ";
+ revs.verbose_header = 1;
continue;
}
if (!strcmp(arg, "--timestamp")) {
usage(rev_list_usage);
}
+ if (revs.commit_format != CMIT_FMT_UNSPECIFIED) {
+ /* The command line has a --pretty */
+ hdr_termination = '\n';
+ if (revs.commit_format == CMIT_FMT_ONELINE)
+ revs.header_prefix = "";
+ else
+ revs.header_prefix = "commit ";
+ }
list = revs.commits;
- if (!list &&
- (!(revs.tag_objects||revs.tree_objects||revs.blob_objects) && !revs.pending_objects))
+ if ((!list &&
+ (!(revs.tag_objects||revs.tree_objects||revs.blob_objects) &&
+ !revs.pending_objects)) ||
+ revs.diff)
usage(rev_list_usage);
- save_commit_buffer = verbose_header;
+ save_commit_buffer = revs.verbose_header;
track_object_refs = 0;
+ if (bisect_list)
+ revs.limited = 1;
prepare_revision_walk(&revs);
if (revs.tree_objects)
add_object(obj, &revs->pending_objects, NULL, name);
}
-static struct commit *get_commit_reference(struct rev_info *revs, const char *name, const unsigned char *sha1, unsigned int flags)
+static struct object *get_reference(struct rev_info *revs, const char *name, const unsigned char *sha1, unsigned int flags)
{
struct object *object;
object = parse_object(sha1);
if (!object)
die("bad object %s", name);
+ object->flags |= flags;
+ return object;
+}
+
+static struct commit *handle_commit(struct rev_info *revs, struct object *object, const char *name)
+{
+ unsigned long flags = object->flags;
/*
* Tag object? Look what it points to..
*/
while (object->type == tag_type) {
struct tag *tag = (struct tag *) object;
- object->flags |= flags;
- if (revs->tag_objects && !(object->flags & UNINTERESTING))
+ if (revs->tag_objects && !(flags & UNINTERESTING))
add_pending_object(revs, object, tag->tag);
object = parse_object(tag->tagged->sha1);
if (!object)
*/
if (object->type == commit_type) {
struct commit *commit = (struct commit *)object;
- object->flags |= flags;
if (parse_commit(commit) < 0)
die("unable to parse commit %s", name);
if (flags & UNINTERESTING) {
return REV_TREE_DIFFERENT;
tree_difference = REV_TREE_SAME;
if (diff_tree_sha1(t1->object.sha1, t2->object.sha1, "",
- &revs->diffopt) < 0)
+ &revs->pruning) < 0)
return REV_TREE_DIFFERENT;
return tree_difference;
}
empty.size = 0;
tree_difference = 0;
- retval = diff_tree(&empty, &real, "", &revs->diffopt);
+ retval = diff_tree(&empty, &real, "", &revs->pruning);
free(tree);
return retval >= 0 && !tree_difference;
if (revs->prune_fn)
revs->prune_fn(revs, commit);
+ if (revs->no_walk)
+ return;
+
parent = commit->parents;
while (parent) {
struct commit *p = parent->item;
revs->commits = newlist;
}
-static void add_one_commit(struct commit *commit, struct rev_info *revs)
-{
- if (!commit || (commit->object.flags & SEEN))
- return;
- commit->object.flags |= SEEN;
- commit_list_insert(commit, &revs->commits);
-}
-
static int all_flags;
static struct rev_info *all_revs;
static int handle_one_ref(const char *path, const unsigned char *sha1)
{
- struct commit *commit = get_commit_reference(all_revs, path, sha1, all_flags);
- add_one_commit(commit, all_revs);
+ struct object *object = get_reference(all_revs, path, sha1, all_flags);
+ add_pending_object(all_revs, object, "");
return 0;
}
void init_revisions(struct rev_info *revs)
{
memset(revs, 0, sizeof(*revs));
- revs->diffopt.recursive = 1;
- revs->diffopt.add_remove = file_add_remove;
- revs->diffopt.change = file_change;
+
+ revs->abbrev = DEFAULT_ABBREV;
+ revs->ignore_merges = 1;
+ revs->pruning.recursive = 1;
+ revs->pruning.add_remove = file_add_remove;
+ revs->pruning.change = file_change;
revs->lifo = 1;
revs->dense = 1;
revs->prefix = setup_git_directory();
revs->topo_setter = topo_sort_default_setter;
revs->topo_getter = topo_sort_default_getter;
+
+ revs->header_prefix = "";
+ revs->commit_format = CMIT_FMT_DEFAULT;
+
+ diff_setup(&revs->diffopt);
}
/*
const char **unrecognized = argv + 1;
int left = 1;
- init_revisions(revs);
-
/* First, search for "--" */
seen_dashdash = 0;
for (i = 1; i < argc; i++) {
flags = 0;
for (i = 1; i < argc; i++) {
- struct commit *commit;
+ struct object *object;
const char *arg = argv[i];
unsigned char sha1[20];
char *dotdot;
int local_flags;
if (*arg == '-') {
+ int opts;
if (!strncmp(arg, "--max-count=", 12)) {
revs->max_count = atoi(arg + 12);
continue;
revs->unpacked = 1;
continue;
}
+ if (!strcmp(arg, "-r")) {
+ revs->diff = 1;
+ revs->diffopt.recursive = 1;
+ continue;
+ }
+ if (!strcmp(arg, "-t")) {
+ revs->diff = 1;
+ revs->diffopt.recursive = 1;
+ revs->diffopt.tree_in_recursive = 1;
+ continue;
+ }
+ if (!strcmp(arg, "-m")) {
+ revs->ignore_merges = 0;
+ continue;
+ }
+ if (!strcmp(arg, "-c")) {
+ revs->diff = 1;
+ revs->combine_merges = 1;
+ continue;
+ }
+ if (!strcmp(arg, "--cc")) {
+ revs->diff = 1;
+ revs->dense_combined_merges = 1;
+ revs->combine_merges = 1;
+ continue;
+ }
+ if (!strcmp(arg, "-v")) {
+ revs->verbose_header = 1;
+ revs->header_prefix = "diff-tree ";
+ continue;
+ }
+ if (!strncmp(arg, "--pretty", 8)) {
+ revs->verbose_header = 1;
+ revs->header_prefix = "diff-tree ";
+ revs->commit_format = get_commit_format(arg+8);
+ continue;
+ }
+ if (!strcmp(arg, "--root")) {
+ revs->show_root_diff = 1;
+ continue;
+ }
+ if (!strcmp(arg, "--no-commit-id")) {
+ revs->no_commit_id = 1;
+ continue;
+ }
+ if (!strcmp(arg, "--always")) {
+ revs->always_show_header = 1;
+ continue;
+ }
+ if (!strcmp(arg, "--no-abbrev")) {
+ revs->abbrev = 0;
+ continue;
+ }
+ if (!strcmp(arg, "--abbrev")) {
+ revs->abbrev = DEFAULT_ABBREV;
+ continue;
+ }
+ if (!strcmp(arg, "--abbrev-commit")) {
+ revs->abbrev_commit = 1;
+ continue;
+ }
+ if (!strcmp(arg, "--full-diff")) {
+ revs->diff = 1;
+ revs->full_diff = 1;
+ continue;
+ }
+ opts = diff_opt_parse(&revs->diffopt, argv+i, argc-i);
+ if (opts > 0) {
+ revs->diff = 1;
+ i += opts - 1;
+ continue;
+ }
*unrecognized++ = arg;
left++;
continue;
this = "HEAD";
if (!get_sha1(this, from_sha1) &&
!get_sha1(next, sha1)) {
- struct commit *exclude;
- struct commit *include;
+ struct object *exclude;
+ struct object *include;
- exclude = get_commit_reference(revs, this, from_sha1, flags ^ UNINTERESTING);
- include = get_commit_reference(revs, next, sha1, flags);
+ exclude = get_reference(revs, this, from_sha1, flags ^ UNINTERESTING);
+ include = get_reference(revs, next, sha1, flags);
if (!exclude || !include)
die("Invalid revision range %s..%s", arg, next);
- add_one_commit(exclude, revs);
- add_one_commit(include, revs);
+ add_pending_object(revs, exclude, this);
+ add_pending_object(revs, include, next);
continue;
}
*dotdot = '.';
revs->prune_data = get_pathspec(revs->prefix, argv + i);
break;
}
- commit = get_commit_reference(revs, arg, sha1, flags ^ local_flags);
- add_one_commit(commit, revs);
+ object = get_reference(revs, arg, sha1, flags ^ local_flags);
+ add_pending_object(revs, object, arg);
}
- if (def && !revs->commits) {
+ if (def && !revs->pending_objects) {
unsigned char sha1[20];
- struct commit *commit;
+ struct object *object;
if (get_sha1(def, sha1) < 0)
die("bad default revision '%s'", def);
- commit = get_commit_reference(revs, def, sha1, 0);
- add_one_commit(commit, revs);
+ object = get_reference(revs, def, sha1, 0);
+ add_pending_object(revs, object, def);
}
if (revs->topo_order || revs->unpacked)
revs->limited = 1;
if (revs->prune_data) {
- diff_tree_setup_paths(revs->prune_data, &revs->diffopt);
+ diff_tree_setup_paths(revs->prune_data, &revs->pruning);
revs->prune_fn = try_to_simplify_commit;
+ if (!revs->full_diff)
+ diff_tree_setup_paths(revs->prune_data, &revs->diffopt);
}
+ if (revs->combine_merges) {
+ revs->ignore_merges = 0;
+ if (revs->dense_combined_merges)
+ revs->diffopt.output_format = DIFF_FORMAT_PATCH;
+ }
+ if (revs->diffopt.output_format == DIFF_FORMAT_PATCH)
+ revs->diffopt.recursive = 1;
+ revs->diffopt.abbrev = revs->abbrev;
+ diff_setup_done(&revs->diffopt);
return left;
}
void prepare_revision_walk(struct rev_info *revs)
{
- sort_by_date(&revs->commits);
+ struct object_list *list;
+
+ list = revs->pending_objects;
+ revs->pending_objects = NULL;
+ while (list) {
+ struct commit *commit = handle_commit(revs, list->item, list->name);
+ if (commit) {
+ if (!(commit->object.flags & SEEN)) {
+ commit->object.flags |= SEEN;
+ insert_by_date(commit, &revs->commits);
+ }
+ }
+ list = list->next;
+ }
+
+ if (revs->no_walk)
+ return;
if (revs->limited)
limit_list(revs);
if (revs->topo_order)
/* Traversal flags */
unsigned int dense:1,
no_merges:1,
+ no_walk:1,
remove_empty_trees:1,
lifo:1,
topo_order:1,
boundary:1,
parents:1;
+ /* Diff flags */
+ unsigned int diff:1,
+ full_diff:1,
+ show_root_diff:1,
+ no_commit_id:1,
+ verbose_header:1,
+ ignore_merges:1,
+ combine_merges:1,
+ dense_combined_merges:1,
+ always_show_header:1;
+
+ /* Format info */
+ unsigned int abbrev_commit:1;
+ unsigned int abbrev;
+ enum cmit_fmt commit_format;
+ const char *header_prefix;
+ const char *header;
+ const char *use_precomputed_header;
+
/* special limits */
int max_count;
unsigned long max_age;
unsigned long min_age;
- /* paths limiting */
+ /* diff info for patches and for paths limiting */
struct diff_options diffopt;
+ struct diff_options pruning;
topo_sort_set_fn_t topo_setter;
topo_sort_get_fn_t topo_getter;
--- /dev/null
+#include <unistd.h>
+#include <stdlib.h>
+#include <fcntl.h>
+#include <libgen.h>
+#include <stdio.h>
+#include <assert.h>
+#include <math.h>
+#include <string.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/mman.h>
+
+#include "rabinpoly.h"
+#include "gsimm.h"
+
+#define MIN(x,y) ((y)<(x) ? (y) : (x))
+#define MAX(x,y) ((y)>(x) ? (y) : (x))
+
+/* The RABIN_WINDOW_SIZE is the size of fingerprint window used by
+ Rabin algorithm. This is not a modifiable parameter.
+
+ The first RABIN_WINDOW_SIZE - 1 bytes are skipped, in order to ensure
+ fingerprints are good hashes. This does somewhat reduce the
+ influence of the first few bytes in the file (they're part of
+ fewer windows, like the last few bytes), but that actually isn't
+ so bad as files often start with fixed content that may bias comparisons.
+*/
+
+typedef struct fileinfo
+{ char *name;
+ size_t length;
+ u_char md[MD_LENGTH];
+ int match;
+} File;
+
+int flag_verbose = 0;
+int flag_debug = 0;
+char *flag_relative = 0;
+
+char cmd[12] = " ...";
+char md_strbuf[MD_LENGTH * 2 + 1];
+u_char relative_md [MD_LENGTH];
+
+File *file;
+int file_count;
+size_t file_bytes;
+
+char hex[17] = "0123456789abcdef";
+
+void usage()
+{ fprintf (stderr, "usage: %s [-dhvw] [-r fingerprint] file ...\n", cmd);
+ fprintf (stderr, " -d\tdebug output, repeate for more verbosity\n");
+ fprintf (stderr, " -h\tshow this usage information\n");
+ fprintf (stderr, " -r\tshow distance relative to fingerprint "
+ "(%u hex digits)\n", MD_LENGTH * 2);
+ fprintf (stderr, " -v\tverbose output, repeat for even more verbosity\n");
+ fprintf (stderr, " -w\tenable warnings for suspect statistics\n");
+ exit (1);
+}
+
+int dist (u_char *l, u_char *r)
+{ int j, k;
+ int d = 0;
+
+ for (j = 0; j < MD_LENGTH; j++)
+ { u_char ch = l[j] ^ r[j];
+
+ for (k = 0; k < 8; k++) d += ((ch & (1<<k)) > 0);
+ }
+
+ return d;
+}
+
+char *md_to_str(u_char *md)
+{ int j;
+
+ for (j = 0; j < MD_LENGTH; j++)
+ { u_char ch = md[j];
+
+ md_strbuf[j*2] = hex[ch >> 4];
+ md_strbuf[j*2+1] = hex[ch & 0xF];
+ }
+
+ md_strbuf[j*2] = 0;
+ return md_strbuf;
+}
+
+void process_file (char *name)
+{ int fd;
+ struct stat fs;
+ u_char *data;
+ File *fi = file+file_count;;
+
+ fd = open (name, O_RDONLY, 0);
+ if (fd < 0)
+ { perror (name);
+ exit (2);
+ }
+
+ if (fstat (fd, &fs))
+ { perror (name);
+ exit (2);
+ }
+
+ if (fs.st_size >= MIN_FILE_SIZE
+ && fs.st_size <= MAX_FILE_SIZE)
+ { fi->length = fs.st_size;
+ fi->name = name;
+
+ data = (u_char *) mmap (0, fs.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
+
+ if (data == (u_char *) -1)
+ { perror (name);
+ exit (2);
+ }
+
+ gb_simm_process (data, fs.st_size, fi->md);
+ if (flag_relative)
+ { int d = dist (fi->md, relative_md);
+ double sim = 1.0 - MIN (1.0, (double) (d) / (MD_LENGTH * 4 - 1));
+ fprintf (stdout, "%s %llu %u %s %u %3.1f\n",
+ md_to_str (fi->md), (long long unsigned) 0,
+ (unsigned) fs.st_size, name,
+ d, 100.0 * sim);
+ }
+ else
+ {
+ fprintf (stdout, "%s %llu %u %s\n",
+ md_to_str (fi->md), (long long unsigned) 0,
+ (unsigned) fs.st_size, name);
+ }
+ munmap (data, fs.st_size);
+ file_bytes += fs.st_size;
+ file_count++;
+ } else if (flag_verbose)
+ { fprintf (stdout, "skipping %s (size %llu)\n", name, (long long unsigned) fs.st_size); }
+
+ close (fd);
+}
+
+u_char *str_to_md(char *str, u_char *md)
+{ int j;
+
+ if (!md || !str) return 0;
+
+ bzero (md, MD_LENGTH);
+
+ for (j = 0; j < MD_LENGTH * 2; j++)
+ { char ch = str[j];
+
+ if (ch >= '0' && ch <= '9')
+ { md [j/2] = (md [j/2] << 4) + (ch - '0');
+ }
+ else
+ { ch |= 32;
+
+ if (ch < 'a' || ch > 'f') break;
+ md [j/2] = (md[j/2] << 4) + (ch - 'a' + 10);
+ } }
+
+ return (j != MD_LENGTH * 2 || str[j] != 0) ? 0 : md;
+}
+
+int main (int argc, char *argv[])
+{ int ch, j;
+
+ strncpy (cmd, basename (argv[0]), 8);
+
+ while ((ch = getopt(argc, argv, "dhr:vw")) != -1)
+ { switch (ch)
+ { case 'd': flag_debug++;
+ break;
+ case 'r': if (!optarg)
+ { fprintf (stderr, "%s: missing argument for -r\n", cmd);
+ return 1;
+ }
+ if (str_to_md (optarg, relative_md)) flag_relative = optarg;
+ else
+ { fprintf (stderr, "%s: not a valid fingerprint\n", optarg);
+ return 1;
+ }
+ break;
+ case 'v': flag_verbose++;
+ break;
+ case 'w': break;
+ default : usage();
+ return (ch != 'h');
+ } }
+
+ argc -= optind;
+ argv += optind;
+
+ if (argc == 0) usage();
+
+ rabin_reset ();
+ if (flag_verbose && flag_relative)
+ { fprintf (stdout, "distances are relative to %s\n", flag_relative);
+ }
+
+ file = (File *) calloc (argc, sizeof (File));
+
+ for (j = 0; j < argc; j++) process_file (argv[j]);
+
+ if (flag_verbose)
+ { fprintf (stdout, "%li bytes in %i files\n", (long) file_bytes, file_count);
+ }
+
+ return 0;
+}