Tag
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375
/*
* Copyright (C) the libgit2 contributors. All rights reserved.
*
* This file is part of libgit2, distributed under the GNU GPL v2 with
* a Linking Exception. For full terms see the included COPYING file.
*/
#include "common.h"
#include "git2/sys/hashsig.h"
#include "futils.h"
#include "util.h"
typedef uint32_t hashsig_t;
typedef uint64_t hashsig_state;
#define HASHSIG_SCALE 100
#define HASHSIG_MAX_RUN 80
#define HASHSIG_HASH_START INT64_C(0x012345678ABCDEF0)
#define HASHSIG_HASH_SHIFT 5
#define HASHSIG_HASH_MIX(S,CH) \
(S) = ((S) << HASHSIG_HASH_SHIFT) - (S) + (hashsig_state)(CH)
#define HASHSIG_HEAP_SIZE ((1 << 7) - 1)
#define HASHSIG_HEAP_MIN_SIZE 4
typedef int (*hashsig_cmp)(const void *a, const void *b, void *);
typedef struct {
int size, asize;
hashsig_cmp cmp;
hashsig_t values[HASHSIG_HEAP_SIZE];
} hashsig_heap;
struct git_hashsig {
hashsig_heap mins;
hashsig_heap maxs;
size_t lines;
git_hashsig_option_t opt;
};
#define HEAP_LCHILD_OF(I) (((I)<<1)+1)
#define HEAP_RCHILD_OF(I) (((I)<<1)+2)
#define HEAP_PARENT_OF(I) (((I)-1)>>1)
static void hashsig_heap_init(hashsig_heap *h, hashsig_cmp cmp)
{
h->size = 0;
h->asize = HASHSIG_HEAP_SIZE;
h->cmp = cmp;
}
static int hashsig_cmp_max(const void *a, const void *b, void *payload)
{
hashsig_t av = *(const hashsig_t *)a, bv = *(const hashsig_t *)b;
GIT_UNUSED(payload);
return (av < bv) ? -1 : (av > bv) ? 1 : 0;
}
static int hashsig_cmp_min(const void *a, const void *b, void *payload)
{
hashsig_t av = *(const hashsig_t *)a, bv = *(const hashsig_t *)b;
GIT_UNUSED(payload);
return (av > bv) ? -1 : (av < bv) ? 1 : 0;
}
static void hashsig_heap_up(hashsig_heap *h, int el)
{
int parent_el = HEAP_PARENT_OF(el);
while (el > 0 && h->cmp(&h->values[parent_el], &h->values[el], NULL) > 0) {
hashsig_t t = h->values[el];
h->values[el] = h->values[parent_el];
h->values[parent_el] = t;
el = parent_el;
parent_el = HEAP_PARENT_OF(el);
}
}
static void hashsig_heap_down(hashsig_heap *h, int el)
{
hashsig_t v, lv, rv;
/* 'el < h->size / 2' tests if el is bottom row of heap */
while (el < h->size / 2) {
int lel = HEAP_LCHILD_OF(el), rel = HEAP_RCHILD_OF(el), swapel;
v = h->values[el];
lv = h->values[lel];
rv = h->values[rel];
if (h->cmp(&v, &lv, NULL) < 0 && h->cmp(&v, &rv, NULL) < 0)
break;
swapel = (h->cmp(&lv, &rv, NULL) < 0) ? lel : rel;
h->values[el] = h->values[swapel];
h->values[swapel] = v;
el = swapel;
}
}
static void hashsig_heap_sort(hashsig_heap *h)
{
/* only need to do this at the end for signature comparison */
git__qsort_r(h->values, h->size, sizeof(hashsig_t), h->cmp, NULL);
}
static void hashsig_heap_insert(hashsig_heap *h, hashsig_t val)
{
/* if heap is not full, insert new element */
if (h->size < h->asize) {
h->values[h->size++] = val;
hashsig_heap_up(h, h->size - 1);
}
/* if heap is full, pop top if new element should replace it */
else if (h->cmp(&val, &h->values[0], NULL) > 0) {
h->size--;
h->values[0] = h->values[h->size];
hashsig_heap_down(h, 0);
}
}
typedef struct {
int use_ignores;
uint8_t ignore_ch[256];
} hashsig_in_progress;
static int hashsig_in_progress_init(
hashsig_in_progress *prog, git_hashsig *sig)
{
int i;
/* no more than one can be set */
GIT_ASSERT(!(sig->opt & GIT_HASHSIG_IGNORE_WHITESPACE) ||
!(sig->opt & GIT_HASHSIG_SMART_WHITESPACE));
if (sig->opt & GIT_HASHSIG_IGNORE_WHITESPACE) {
for (i = 0; i < 256; ++i)
prog->ignore_ch[i] = git__isspace_nonlf(i);
prog->use_ignores = 1;
} else if (sig->opt & GIT_HASHSIG_SMART_WHITESPACE) {
for (i = 0; i < 256; ++i)
prog->ignore_ch[i] = git__isspace(i);
prog->use_ignores = 1;
} else {
memset(prog, 0, sizeof(*prog));
}
return 0;
}
static int hashsig_add_hashes(
git_hashsig *sig,
const uint8_t *data,
size_t size,
hashsig_in_progress *prog)
{
const uint8_t *scan = data, *end = data + size;
hashsig_state state = HASHSIG_HASH_START;
int use_ignores = prog->use_ignores, len;
uint8_t ch;
while (scan < end) {
state = HASHSIG_HASH_START;
for (len = 0; scan < end && len < HASHSIG_MAX_RUN; ) {
ch = *scan;
if (use_ignores)
for (; scan < end && git__isspace_nonlf(ch); ch = *scan)
++scan;
else if (sig->opt &
(GIT_HASHSIG_IGNORE_WHITESPACE | GIT_HASHSIG_SMART_WHITESPACE))
for (; scan < end && ch == '\r'; ch = *scan)
++scan;
/* peek at next character to decide what to do next */
if (sig->opt & GIT_HASHSIG_SMART_WHITESPACE)
use_ignores = (ch == '\n');
if (scan >= end)
break;
++scan;
/* check run terminator */
if (ch == '\n' || ch == '\0') {
sig->lines++;
break;
}
++len;
HASHSIG_HASH_MIX(state, ch);
}
if (len > 0) {
hashsig_heap_insert(&sig->mins, (hashsig_t)state);
hashsig_heap_insert(&sig->maxs, (hashsig_t)state);
while (scan < end && (*scan == '\n' || !*scan))
++scan;
}
}
prog->use_ignores = use_ignores;
return 0;
}
static int hashsig_finalize_hashes(git_hashsig *sig)
{
if (sig->mins.size < HASHSIG_HEAP_MIN_SIZE &&
!(sig->opt & GIT_HASHSIG_ALLOW_SMALL_FILES)) {
git_error_set(GIT_ERROR_INVALID,
"file too small for similarity signature calculation");
return GIT_EBUFS;
}
hashsig_heap_sort(&sig->mins);
hashsig_heap_sort(&sig->maxs);
return 0;
}
static git_hashsig *hashsig_alloc(git_hashsig_option_t opts)
{
git_hashsig *sig = git__calloc(1, sizeof(git_hashsig));
if (!sig)
return NULL;
hashsig_heap_init(&sig->mins, hashsig_cmp_min);
hashsig_heap_init(&sig->maxs, hashsig_cmp_max);
sig->opt = opts;
return sig;
}
int git_hashsig_create(
git_hashsig **out,
const char *buf,
size_t buflen,
git_hashsig_option_t opts)
{
int error;
hashsig_in_progress prog;
git_hashsig *sig = hashsig_alloc(opts);
GIT_ERROR_CHECK_ALLOC(sig);
if ((error = hashsig_in_progress_init(&prog, sig)) < 0)
return error;
error = hashsig_add_hashes(sig, (const uint8_t *)buf, buflen, &prog);
if (!error)
error = hashsig_finalize_hashes(sig);
if (!error)
*out = sig;
else
git_hashsig_free(sig);
return error;
}
int git_hashsig_create_fromfile(
git_hashsig **out,
const char *path,
git_hashsig_option_t opts)
{
uint8_t buf[0x1000];
ssize_t buflen = 0;
int error = 0, fd;
hashsig_in_progress prog;
git_hashsig *sig = hashsig_alloc(opts);
GIT_ERROR_CHECK_ALLOC(sig);
if ((fd = git_futils_open_ro(path)) < 0) {
git__free(sig);
return fd;
}
if ((error = hashsig_in_progress_init(&prog, sig)) < 0) {
p_close(fd);
return error;
}
while (!error) {
if ((buflen = p_read(fd, buf, sizeof(buf))) <= 0) {
if ((error = (int)buflen) < 0)
git_error_set(GIT_ERROR_OS,
"read error on '%s' calculating similarity hashes", path);
break;
}
error = hashsig_add_hashes(sig, buf, buflen, &prog);
}
p_close(fd);
if (!error)
error = hashsig_finalize_hashes(sig);
if (!error)
*out = sig;
else
git_hashsig_free(sig);
return error;
}
void git_hashsig_free(git_hashsig *sig)
{
git__free(sig);
}
static int hashsig_heap_compare(const hashsig_heap *a, const hashsig_heap *b)
{
int matches = 0, i, j, cmp;
GIT_ASSERT_WITH_RETVAL(a->cmp == b->cmp, 0);
/* hash heaps are sorted - just look for overlap vs total */
for (i = 0, j = 0; i < a->size && j < b->size; ) {
cmp = a->cmp(&a->values[i], &b->values[j], NULL);
if (cmp < 0)
++i;
else if (cmp > 0)
++j;
else {
++i; ++j; ++matches;
}
}
return HASHSIG_SCALE * (matches * 2) / (a->size + b->size);
}
int git_hashsig_compare(const git_hashsig *a, const git_hashsig *b)
{
/* if we have no elements in either file then each file is either
* empty or blank. if we're ignoring whitespace then the files are
* similar, otherwise they're dissimilar.
*/
if (a->mins.size == 0 && b->mins.size == 0) {
if ((!a->lines && !b->lines) ||
(a->opt & GIT_HASHSIG_IGNORE_WHITESPACE))
return HASHSIG_SCALE;
else
return 0;
}
/* if we have fewer than the maximum number of elements, then just use
* one array since the two arrays will be the same
*/
if (a->mins.size < HASHSIG_HEAP_SIZE) {
return hashsig_heap_compare(&a->mins, &b->mins);
} else {
int mins, maxs;
if ((mins = hashsig_heap_compare(&a->mins, &b->mins)) < 0)
return mins;
if ((maxs = hashsig_heap_compare(&a->maxs, &b->maxs)) < 0)
return maxs;
return (mins + maxs) / 2;
}
}