summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.gitignore1
-rw-r--r--Makefile4
-rw-r--r--builtin-log.c39
-rw-r--r--builtin.h1
-rw-r--r--commit.c36
-rw-r--r--commit.h1
-rw-r--r--contrib/colordiff/README2
-rwxr-xr-xcontrib/colordiff/colordiff.perl196
-rw-r--r--daemon.c2
-rw-r--r--git.c1
-rw-r--r--gsimm.c94
-rw-r--r--gsimm.h28
-rw-r--r--log-tree.c27
-rw-r--r--rabinpoly.c154
-rw-r--r--rabinpoly.h31
-rw-r--r--test-gsimm.c209
-rw-r--r--update-index.c127
17 files changed, 939 insertions, 14 deletions
diff --git a/.gitignore b/.gitignore
index b5959d6311..145f8555ad 100644
--- a/.gitignore
+++ b/.gitignore
@@ -123,6 +123,7 @@ git-write-tree
git-core-*/?*
test-date
test-delta
+test-gsimm
common-cmds.h
*.tar.gz
*.dsc
diff --git a/Makefile b/Makefile
index d9a3a82fe2..25b99e62d1 100644
--- a/Makefile
+++ b/Makefile
@@ -611,6 +611,9 @@ test-date$X: test-date.c date.o ctype.o
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
@@ -659,6 +662,7 @@ clean:
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
diff --git a/builtin-log.c b/builtin-log.c
index 69f2911cb4..a39aed6d86 100644
--- a/builtin-log.c
+++ b/builtin-log.c
@@ -9,6 +9,7 @@
#include "diff.h"
#include "revision.h"
#include "log-tree.h"
+#include "builtin.h"
static int cmd_log_wc(int argc, const char **argv, char **envp,
struct rev_info *rev)
@@ -67,3 +68,41 @@ int cmd_log(int argc, const char **argv, char **envp)
rev.diffopt.recursive = 1;
return cmd_log_wc(argc, argv, envp, &rev);
}
+
+int cmd_format_patch(int argc, const char **argv, char **envp)
+{
+ struct commit *commit;
+ struct commit **list = NULL;
+ struct rev_info rev;
+ int nr = 0;
+
+ init_revisions(&rev);
+ rev.commit_format = CMIT_FMT_EMAIL;
+ rev.verbose_header = 1;
+ rev.diff = 1;
+ rev.diffopt.with_raw = 0;
+ rev.diffopt.with_stat = 1;
+ rev.combine_merges = 0;
+ rev.ignore_merges = 1;
+ rev.diffopt.output_format = DIFF_FORMAT_PATCH;
+ argc = setup_revisions(argc, argv, &rev, "HEAD");
+
+ prepare_revision_walk(&rev);
+ while ((commit = get_revision(&rev)) != NULL) {
+ nr++;
+ list = realloc(list, nr * sizeof(list[0]));
+ list[nr - 1] = commit;
+ }
+ while (0 <= --nr) {
+ int shown;
+ commit = list[nr];
+ shown = log_tree_commit(&rev, commit);
+ free(commit->buffer);
+ commit->buffer = NULL;
+ if (shown)
+ printf("-- \n%s\n\n", git_version_string);
+ }
+ free(list);
+ return 0;
+}
+
diff --git a/builtin.h b/builtin.h
index 47408a0585..94dc0732f9 100644
--- a/builtin.h
+++ b/builtin.h
@@ -19,5 +19,6 @@ extern int cmd_version(int argc, const char **argv, char **envp);
extern int cmd_whatchanged(int argc, const char **argv, char **envp);
extern int cmd_show(int argc, const char **argv, char **envp);
extern int cmd_log(int argc, const char **argv, char **envp);
+extern int cmd_format_patch(int argc, const char **argv, char **envp);
#endif
diff --git a/commit.c b/commit.c
index 2717dd81c3..06e00987cc 100644
--- a/commit.c
+++ b/commit.c
@@ -36,6 +36,8 @@ enum cmit_fmt get_commit_format(const char *arg)
return CMIT_FMT_FULL;
if (!strcmp(arg, "=fuller"))
return CMIT_FMT_FULLER;
+ if (!strcmp(arg, "=email"))
+ return CMIT_FMT_EMAIL;
if (!strcmp(arg, "=oneline"))
return CMIT_FMT_ONELINE;
die("invalid --pretty format");
@@ -428,6 +430,10 @@ static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf, const c
time = strtoul(date, &date, 10);
tz = strtol(date, NULL, 10);
+ if (fmt == CMIT_FMT_EMAIL) {
+ what = "From";
+ filler = "";
+ }
ret = sprintf(buf, "%s: %.*s%.*s\n", what,
(fmt == CMIT_FMT_FULLER) ? 4 : 0,
filler, namelen, line);
@@ -435,6 +441,9 @@ static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf, const c
case CMIT_FMT_MEDIUM:
ret += sprintf(buf + ret, "Date: %s\n", show_date(time, tz));
break;
+ case CMIT_FMT_EMAIL:
+ ret += sprintf(buf + ret, "Date: %s\n", show_date(time, tz));
+ break;
case CMIT_FMT_FULLER:
ret += sprintf(buf + ret, "%sDate: %s\n", what, show_date(time, tz));
break;
@@ -445,10 +454,12 @@ static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf, const c
return ret;
}
-static int is_empty_line(const char *line, int len)
+static int is_empty_line(const char *line, int *len_p)
{
+ int len = *len_p;
while (len && isspace(line[len-1]))
len--;
+ *len_p = len;
return !len;
}
@@ -457,7 +468,8 @@ static int add_merge_info(enum cmit_fmt fmt, char *buf, const struct commit *com
struct commit_list *parent = commit->parents;
int offset;
- if ((fmt == CMIT_FMT_ONELINE) || !parent || !parent->next)
+ if ((fmt == CMIT_FMT_ONELINE) || (fmt == CMIT_FMT_EMAIL) ||
+ !parent || !parent->next)
return 0;
offset = sprintf(buf, "Merge:");
@@ -480,9 +492,15 @@ unsigned long pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit
{
int hdr = 1, body = 0;
unsigned long offset = 0;
- int indent = (fmt == CMIT_FMT_ONELINE) ? 0 : 4;
+ int indent = 4;
int parents_shown = 0;
const char *msg = commit->buffer;
+ const char *subject = NULL;
+
+ if (fmt == CMIT_FMT_EMAIL)
+ subject = "Subject: [PATCH] ";
+ if (fmt == CMIT_FMT_ONELINE || fmt == CMIT_FMT_EMAIL)
+ indent = 0;
for (;;) {
const char *line = msg;
@@ -506,7 +524,7 @@ unsigned long pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit
if (hdr) {
if (linelen == 1) {
hdr = 0;
- if (fmt != CMIT_FMT_ONELINE)
+ if ((fmt != CMIT_FMT_ONELINE) && !subject)
buf[offset++] = '\n';
continue;
}
@@ -544,20 +562,28 @@ unsigned long pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit
continue;
}
- if (is_empty_line(line, linelen)) {
+ if (is_empty_line(line, &linelen)) {
if (!body)
continue;
+ if (subject)
+ continue;
if (fmt == CMIT_FMT_SHORT)
break;
} else {
body = 1;
}
+ if (subject) {
+ memcpy(buf + offset, subject, 9);
+ offset += 9;
+ }
memset(buf + offset, ' ', indent);
memcpy(buf + offset + indent, line, linelen);
offset += linelen + indent;
+ buf[offset++] = '\n';
if (fmt == CMIT_FMT_ONELINE)
break;
+ subject = NULL;
}
while (offset && isspace(buf[offset-1]))
offset--;
diff --git a/commit.h b/commit.h
index de142afe73..01eec60a1e 100644
--- a/commit.h
+++ b/commit.h
@@ -45,6 +45,7 @@ enum cmit_fmt {
CMIT_FMT_FULL,
CMIT_FMT_FULLER,
CMIT_FMT_ONELINE,
+ CMIT_FMT_EMAIL,
CMIT_FMT_UNSPECIFIED,
};
diff --git a/contrib/colordiff/README b/contrib/colordiff/README
new file mode 100644
index 0000000000..2678fdf9c2
--- /dev/null
+++ b/contrib/colordiff/README
@@ -0,0 +1,2 @@
+This is "colordiff" (http://colordiff.sourceforge.net/) by Dave
+Ewart <davee@sungate.co.uk>, modified specifically for git.
diff --git a/contrib/colordiff/colordiff.perl b/contrib/colordiff/colordiff.perl
new file mode 100755
index 0000000000..5789cfb265
--- /dev/null
+++ b/contrib/colordiff/colordiff.perl
@@ -0,0 +1,196 @@
+#!/usr/bin/perl -w
+#
+# $Id: colordiff.pl,v 1.4.2.10 2004/01/04 15:02:59 daveewart Exp $
+
+########################################################################
+# #
+# ColorDiff - a wrapper/replacment for 'diff' producing #
+# colourful output #
+# #
+# Copyright (C)2002-2004 Dave Ewart (davee@sungate.co.uk) #
+# #
+########################################################################
+# #
+# 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 of the License, 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., 675 Mass Ave, Cambridge, MA 02139, USA. #
+# #
+########################################################################
+
+use strict;
+use Getopt::Long qw(:config pass_through);
+use IPC::Open2;
+
+my $app_name = 'colordiff';
+my $version = '1.0.4';
+my $author = 'Dave Ewart';
+my $author_email = 'davee@sungate.co.uk';
+my $app_www = 'http://colordiff.sourceforge.net/';
+my $copyright = '(C)2002-2004';
+my $show_banner = 1;
+
+# ANSI sequences for colours
+my %colour;
+$colour{white} = "\033[1;37m";
+$colour{yellow} = "\033[1;33m";
+$colour{green} = "\033[1;32m";
+$colour{blue} = "\033[1;34m";
+$colour{cyan} = "\033[1;36m";
+$colour{red} = "\033[1;31m";
+$colour{magenta} = "\033[1;35m";
+$colour{black} = "\033[1;30m";
+$colour{darkwhite} = "\033[0;37m";
+$colour{darkyellow} = "\033[0;33m";
+$colour{darkgreen} = "\033[0;32m";
+$colour{darkblue} = "\033[0;34m";
+$colour{darkcyan} = "\033[0;36m";
+$colour{darkred} = "\033[0;31m";
+$colour{darkmagenta} = "\033[0;35m";
+$colour{darkblack} = "\033[0;30m";
+$colour{OFF} = "\033[0;0m";
+
+# Default colours if /etc/colordiffrc or ~/.colordiffrc do not exist
+my $plain_text = $colour{OFF};
+my $file_old = $colour{red};
+my $file_new = $colour{blue};
+my $diff_stuff = $colour{magenta};
+
+# Locations for personal and system-wide colour configurations
+my $HOME = $ENV{HOME};
+my $etcdir = '/etc';
+
+my ($setting, $value);
+my @config_files = ("$etcdir/colordiffrc", "$HOME/.colordiffrc");
+my $config_file;
+
+foreach $config_file (@config_files) {
+ if (open(COLORDIFFRC, "<$config_file")) {
+ while (<COLORDIFFRC>) {
+ chop;
+ next if (/^#/ || /^$/);
+ s/\s+//g;
+ ($setting, $value) = split ('=');
+ if ($setting eq 'banner') {
+ if ($value eq 'no') {
+ $show_banner = 0;
+ }
+ next;
+ }
+ if (!defined $colour{$value}) {
+ print "Invalid colour specification ($value) in $config_file\n";
+ next;
+ }
+ if ($setting eq 'plain') {
+ $plain_text = $colour{$value};
+ }
+ elsif ($setting eq 'oldtext') {
+ $file_old = $colour{$value};
+ }
+ elsif ($setting eq 'newtext') {
+ $file_new = $colour{$value};
+ }
+ elsif ($setting eq 'diffstuff') {
+ $diff_stuff = $colour{$value};
+ }
+ else {
+ print "Unknown option in $etcdir/colordiffrc: $setting\n";
+ }
+ }
+ close COLORDIFFRC;
+ }
+}
+
+# colordiff specfic options here. Need to pre-declare if using variables
+GetOptions(
+ "no-banner" => sub { $show_banner = 0 },
+ "plain-text=s" => \&set_color,
+ "file-old=s" => \&set_color,
+ "file-new=s" => \&set_color,
+ "diff-stuff=s" => \&set_color
+);
+
+if ($show_banner == 1) {
+ print STDERR "$app_name $version ($app_www)\n";
+ print STDERR "$copyright $author, $author_email\n\n";
+}
+
+if (defined $ARGV[0]) {
+ # More reliable way of pulling in arguments
+ open2(\*INPUTSTREAM, undef, "git", "diff", @ARGV);
+}
+else {
+ *INPUTSTREAM = \*STDIN;
+}
+
+my $record;
+my $nrecs = 0;
+my $inside_file_old = 1;
+my $nparents = undef;
+
+while (<INPUTSTREAM>) {
+ $nrecs++;
+ if (/^(\@\@+) -[-+0-9, ]+ \1/) {
+ print "$diff_stuff";
+ $nparents = length($1) - 1;
+ }
+ elsif (/^diff -/ || /^index / ||
+ /^old mode / || /^new mode / ||
+ /^deleted file mode / || /^new file mode / ||
+ /^similarity index / || /^dissimilarity index / ||
+ /^copy from / || /^copy to / ||
+ /^rename from / || /^rename to /) {
+ $nparents = undef;
+ print "$diff_stuff";
+ }
+ elsif (defined $nparents) {
+ if ($nparents == 1) {
+ if (/^\+/) {
+ print $file_new;
+ }
+ elsif (/^-/) {
+ print $file_old;
+ }
+ else {
+ print $plain_text;
+ }
+ }
+ elsif (/^ {$nparents}/) {
+ print "$plain_text";
+ }
+ elsif (/^[+ ]{$nparents}/) {
+ print "$file_new";
+ }
+ elsif (/^[- ]{$nparents}/) {
+ print "$file_old";
+ }
+ else {
+ print $plain_text;
+ }
+ }
+ elsif (/^--- / || /^\+\+\+ /) {
+ print $diff_stuff;
+ }
+ else {
+ print "$plain_text";
+ }
+ s/$/$colour{OFF}/;
+ print "$_";
+}
+close INPUTSTREAM;
+
+sub set_color {
+ my ($type, $color) = @_;
+
+ $type =~ s/-/_/;
+ eval "\$$type = \$colour{$color}";
+}
diff --git a/daemon.c b/daemon.c
index a1ccda30e2..776749e343 100644
--- a/daemon.c
+++ b/daemon.c
@@ -535,7 +535,7 @@ static int socksetup(int port, int **socklist_p)
if (set_reuse_addr(sockfd)) {
close(sockfd);
- return 0; /* not fatal */
+ continue;
}
if (bind(sockfd, ai->ai_addr, ai->ai_addrlen) < 0) {
diff --git a/git.c b/git.c
index aa2b814d93..619c6654e4 100644
--- a/git.c
+++ b/git.c
@@ -47,6 +47,7 @@ static void handle_internal_command(int argc, const char **argv, char **envp)
{ "log", cmd_log },
{ "whatchanged", cmd_whatchanged },
{ "show", cmd_show },
+ { "fmt-patch", cmd_format_patch },
};
int i;
diff --git a/gsimm.c b/gsimm.c
new file mode 100644
index 0000000000..7024bf8f58
--- /dev/null
+++ b/gsimm.c
@@ -0,0 +1,94 @@
+#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);
+} }
diff --git a/gsimm.h b/gsimm.h
new file mode 100644
index 0000000000..4b023b91a9
--- /dev/null
+++ b/gsimm.h
@@ -0,0 +1,28 @@
+#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
diff --git a/log-tree.c b/log-tree.c
index 9634c4677f..aaf2b9423f 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -37,12 +37,20 @@ void show_log(struct rev_info *opt, struct log_info *log, const char *sep)
/*
* Print header line of header..
*/
- printf("%s%s",
- opt->commit_format == CMIT_FMT_ONELINE ? "" : "commit ",
- diff_unique_abbrev(commit->object.sha1, abbrev_commit));
- if (parent)
- printf(" (from %s)", diff_unique_abbrev(parent->object.sha1, abbrev_commit));
- putchar(opt->commit_format == CMIT_FMT_ONELINE ? ' ' : '\n');
+
+ if (opt->commit_format == CMIT_FMT_EMAIL)
+ printf("From %s Thu Apr 7 15:13:13 2005\n",
+ sha1_to_hex(commit->object.sha1));
+ else {
+ printf("%s%s",
+ opt->commit_format == CMIT_FMT_ONELINE ? "" : "commit ",
+ diff_unique_abbrev(commit->object.sha1, abbrev_commit));
+ if (parent)
+ printf(" (from %s)",
+ diff_unique_abbrev(parent->object.sha1,
+ abbrev_commit));
+ putchar(opt->commit_format == CMIT_FMT_ONELINE ? ' ' : '\n');
+ }
/*
* And then the pretty-printed message itself
@@ -152,15 +160,18 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log
int log_tree_commit(struct rev_info *opt, struct commit *commit)
{
struct log_info log;
+ int shown;
log.commit = commit;
log.parent = NULL;
opt->loginfo = &log;
- if (!log_tree_diff(opt, commit, &log) && opt->loginfo && opt->always_show_header) {
+ shown = log_tree_diff(opt, commit, &log);
+ if (!shown && opt->loginfo && opt->always_show_header) {
log.parent = NULL;
show_log(opt, opt->loginfo, "");
+ shown = 1;
}
opt->loginfo = NULL;
- return 0;
+ return shown;
}
diff --git a/rabinpoly.c b/rabinpoly.c
new file mode 100644
index 0000000000..c26f3829c3
--- /dev/null
+++ b/rabinpoly.c
@@ -0,0 +1,154 @@
+/*
+ *
+ * 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;
+}
+
diff --git a/rabinpoly.h b/rabinpoly.h
new file mode 100644
index 0000000000..a19a097459
--- /dev/null
+++ b/rabinpoly.h
@@ -0,0 +1,31 @@
+/*
+ *
+ * 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);
diff --git a/test-gsimm.c b/test-gsimm.c
new file mode 100644
index 0000000000..bd28b7da28
--- /dev/null
+++ b/test-gsimm.c
@@ -0,0 +1,209 @@
+#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;
+}
diff --git a/update-index.c b/update-index.c
index 1efac27c6b..64f4c4912e 100644
--- a/update-index.c
+++ b/update-index.c
@@ -6,6 +6,7 @@
#include "cache.h"
#include "strbuf.h"
#include "quote.h"
+#include "tree-walk.h"
/*
* Default to not allowing changes to the list of files. The
@@ -471,6 +472,124 @@ static void read_index_info(int line_termination)
static const char update_index_usage[] =
"git-update-index [-q] [--add] [--replace] [--remove] [--unmerged] [--refresh] [--cacheinfo] [--chmod=(+|-)x] [--info-only] [--force-remove] [--stdin] [--index-info] [--ignore-missing] [-z] [--verbose] [--] <file>...";
+static unsigned char head_sha1[20];
+static unsigned char merge_head_sha1[20];
+
+static struct cache_entry *read_one_ent(const char *which,
+ unsigned char *ent, const char *path,
+ int namelen, int stage)
+{
+ unsigned mode;
+ unsigned char sha1[20];
+ int size;
+ struct cache_entry *ce;
+
+ if (get_tree_entry(ent, path, sha1, &mode)) {
+ error("%s: not in %s branch.", path, which);
+ return NULL;
+ }
+ if (mode == S_IFDIR) {
+ error("%s: not a blob in %s branch.", path, which);
+ return NULL;
+ }
+ size = cache_entry_size(namelen);
+ ce = xcalloc(1, size);
+
+ memcpy(ce->sha1, sha1, 20);
+ memcpy(ce->name, path, namelen);
+ ce->ce_flags = create_ce_flags(namelen, stage);
+ ce->ce_mode = create_ce_mode(mode);
+ return ce;
+}
+
+static int unresolve_one(const char *path)
+{
+ int namelen = strlen(path);
+ int pos;
+ int ret = 0;
+ struct cache_entry *ce_2 = NULL, *ce_3 = NULL;
+
+ /* See if there is such entry in the index. */
+ pos = cache_name_pos(path, namelen);
+ if (pos < 0) {
+ /* If there isn't, either it is unmerged, or
+ * resolved as "removed" by mistake. We do not
+ * want to do anything in the former case.
+ */
+ pos = -pos-1;
+ if (pos < active_nr) {
+ struct cache_entry *ce = active_cache[pos];
+ if (ce_namelen(ce) == namelen &&
+ !memcmp(ce->name, path, namelen)) {
+ fprintf(stderr,
+ "%s: skipping still unmerged path.\n",
+ path);
+ goto free_return;
+ }
+ }
+ }
+
+ /* Grab blobs from given path from HEAD and MERGE_HEAD,
+ * stuff HEAD version in stage #2,
+ * stuff MERGE_HEAD version in stage #3.
+ */
+ ce_2 = read_one_ent("our", head_sha1, path, namelen, 2);
+ ce_3 = read_one_ent("their", merge_head_sha1, path, namelen, 3);
+
+ if (!ce_2 || !ce_3) {
+ ret = -1;
+ goto free_return;
+ }
+ if (!memcmp(ce_2->sha1, ce_3->sha1, 20) &&
+ ce_2->ce_mode == ce_3->ce_mode) {
+ fprintf(stderr, "%s: identical in both, skipping.\n",
+ path);
+ goto free_return;
+ }
+
+ remove_file_from_cache(path);
+ if (add_cache_entry(ce_2, ADD_CACHE_OK_TO_ADD)) {
+ error("%s: cannot add our version to the index.", path);
+ ret = -1;
+ goto free_return;
+ }
+ if (!add_cache_entry(ce_3, ADD_CACHE_OK_TO_ADD))
+ return 0;
+ error("%s: cannot add their version to the index.", path);
+ ret = -1;
+ free_return:
+ free(ce_2);
+ free(ce_3);
+ return ret;
+}
+
+static void read_head_pointers(void)
+{
+ if (read_ref(git_path("HEAD"), head_sha1))
+ die("No HEAD -- no initial commit yet?\n");
+ if (read_ref(git_path("MERGE_HEAD"), merge_head_sha1)) {
+ fprintf(stderr, "Not in the middle of a merge.\n");
+ exit(0);
+ }
+}
+
+static int do_unresolve(int ac, const char **av)
+{
+ int i;
+ int err = 0;
+
+ /* Read HEAD and MERGE_HEAD; if MERGE_HEAD does not exist, we
+ * are not doing a merge, so exit with success status.
+ */
+ read_head_pointers();
+
+ for (i = 1; i < ac; i++) {
+ const char *arg = av[i];
+ err |= unresolve_one(arg);
+ }
+ return err;
+}
+
int main(int argc, const char **argv)
{
int i, newfd, entries, has_errors = 0, line_termination = '\n';
@@ -581,6 +700,12 @@ int main(int argc, const char **argv)
read_index_info(line_termination);
break;
}
+ if (!strcmp(path, "--unresolve")) {
+ has_errors = do_unresolve(argc - i, argv + i);
+ if (has_errors)
+ active_cache_changed = 0;
+ goto finish;
+ }
if (!strcmp(path, "--ignore-missing")) {
not_new = 1;
continue;
@@ -612,6 +737,8 @@ int main(int argc, const char **argv)
free(path_name);
}
}
+
+ finish:
if (active_cache_changed) {
if (write_cache(newfd, active_cache, active_nr) ||
commit_index_file(&cache_file))