On Wed, Apr 03, 2019 at 12:02:07PM -0400, Barret Rhoden wrote: > diff --git a/blame.c b/blame.c > index c06cbd906658..50511a300059 100644 > --- a/blame.c > +++ b/blame.c > @@ -915,27 +915,109 @@ static int are_lines_adjacent(struct blame_line_tracker *first, > first->s_lno + 1 == second->s_lno; > } > > -/* > - * This cheap heuristic assigns lines in the chunk to their relative location in > - * the parent's chunk. Any additional lines are left with the target. > +/* https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel */ > +static int bitcount(uint32_t v) > +{ > + v = v - ((v >> 1) & 0x55555555u); > + v = (v & 0x33333333u) + ((v >> 2) & 0x33333333u); > + return (((v + (v >> 4)) & 0xf0f0f0fu) * 0x1010101u) >> 24; > +} > + > +#define FINGERPRINT_LENGTH (8 * 256) > +#define FINGERPRINT_THRESHOLD 1 > +/* This is just a bitset indicating which byte pairs are present. > + * e.g. the string "good goo" has pairs "go", "oo", "od", "d ", " g" > + * String similarity is calculated as a bitwise or and counting the set bits. > + * > + * TODO for the string lengths we typically deal with, this would probably be > + * implemented more efficiently with a set data structure. > */ > +struct fingerprint { > + uint32_t bits[FINGERPRINT_LENGTH]; > +}; > + > +static void get_fingerprint(struct fingerprint *result, const char *line_begin, > + const char *line_end) > +{ > + for (const char *p = line_begin; p + 1 < line_end; ++p) { We still stick to C89, which doesn't support for loop initial declarations yet. Please declare the loop variable as a regular local variable. This also applies to the several 'for (int i = 0; ...)' loops in the functions below. > + unsigned int c = tolower(*p) | (tolower(*(p + 1)) << 8); > + > + result->bits[c >> 5] |= 1u << (c & 0x1f); > + } > +} > + > +static int fingerprint_similarity(const struct fingerprint *a, > + const struct fingerprint *b) > +{ > + int intersection = 0; > + > + for (int i = 0; i < FINGERPRINT_LENGTH; ++i) > + intersection += bitcount(a->bits[i] & b->bits[i]); > + return intersection; > +} > + > +static void get_chunk_fingerprints(struct fingerprint *fingerprints, > + const char *content, > + const int *line_starts, > + long chunk_start, > + long chunk_length) > +{ > + line_starts += chunk_start; > + for (int i = 0; i != chunk_length; ++i) { > + const char *linestart = content + line_starts[i]; > + const char *lineend = content + line_starts[i + 1]; > + > + get_fingerprint(fingerprints + i, linestart, lineend); > + } > +} > + > static void guess_line_blames(struct blame_entry *e, > struct blame_origin *parent, > struct blame_origin *target, > int offset, int delta, > struct blame_line_tracker *line_blames) > { > + struct fingerprint *fp_parent, *fp_target; > int nr_parent_lines = e->num_lines - delta; > > + fp_parent = xcalloc(sizeof(struct fingerprint), nr_parent_lines); > + fp_target = xcalloc(sizeof(struct fingerprint), e->num_lines); > + > + get_chunk_fingerprints(fp_parent, parent->file.ptr, > + parent->line_starts, > + e->s_lno + offset, nr_parent_lines); > + get_chunk_fingerprints(fp_target, target->file.ptr, > + target->line_starts, > + e->s_lno, e->num_lines); > + > for (int i = 0; i < e->num_lines; i++) { > - if (i < nr_parent_lines) { > + int best_sim_val = FINGERPRINT_THRESHOLD; > + int best_sim_idx = -1; > + int sim; > + > + for (int j = 0; j < nr_parent_lines; j++) { > + sim = fingerprint_similarity(&fp_target[i], > + &fp_parent[j]); > + if (sim < best_sim_val) > + continue; > + /* Break ties with the closest-to-target line number */ > + if (sim == best_sim_val && best_sim_idx != -1 && > + abs(best_sim_idx - i) < abs(j - i)) > + continue; > + best_sim_val = sim; > + best_sim_idx = j; > + } > + if (best_sim_idx >= 0) { > line_blames[i].is_parent = 1; > - line_blames[i].s_lno = e->s_lno + i + offset; > + line_blames[i].s_lno = e->s_lno + offset + best_sim_idx; > } else { > line_blames[i].is_parent = 0; > line_blames[i].s_lno = e->s_lno + i; > } > } > + > + free(fp_parent); > + free(fp_target); > } > > /* > -- > 2.21.0.392.gf8f6787159e-goog >
