#include "cache.h" | |

#include "sha1-lookup.h" | |

static uint32_t take2(const unsigned char *sha1) | |

{ | |

return ((sha1[0] << 8) | sha1[1]); | |

} | |

/* | |

* Conventional binary search loop looks like this: | |

* | |

* do { | |

* int mi = (lo + hi) / 2; | |

* int cmp = "entry pointed at by mi" minus "target"; | |

* if (!cmp) | |

* return (mi is the wanted one) | |

* if (cmp > 0) | |

* hi = mi; "mi is larger than target" | |

* else | |

* lo = mi+1; "mi is smaller than target" | |

* } while (lo < hi); | |

* | |

* The invariants are: | |

* | |

* - When entering the loop, lo points at a slot that is never | |

* above the target (it could be at the target), hi points at a | |

* slot that is guaranteed to be above the target (it can never | |

* be at the target). | |

* | |

* - We find a point 'mi' between lo and hi (mi could be the same | |

* as lo, but never can be the same as hi), and check if it hits | |

* the target. There are three cases: | |

* | |

* - if it is a hit, we are happy. | |

* | |

* - if it is strictly higher than the target, we update hi with | |

* it. | |

* | |

* - if it is strictly lower than the target, we update lo to be | |

* one slot after it, because we allow lo to be at the target. | |

* | |

* When choosing 'mi', we do not have to take the "middle" but | |

* anywhere in between lo and hi, as long as lo <= mi < hi is | |

* satisfied. When we somehow know that the distance between the | |

* target and lo is much shorter than the target and hi, we could | |

* pick mi that is much closer to lo than the midway. | |

*/ | |

/* | |

* The table should contain "nr" elements. | |

* The sha1 of element i (between 0 and nr - 1) should be returned | |

* by "fn(i, table)". | |

*/ | |

int sha1_pos(const unsigned char *sha1, void *table, size_t nr, | |

sha1_access_fn fn) | |

{ | |

size_t hi = nr; | |

size_t lo = 0; | |

size_t mi = 0; | |

if (!nr) | |

return -1; | |

if (nr != 1) { | |

size_t lov, hiv, miv, ofs; | |

for (ofs = 0; ofs < 18; ofs += 2) { | |

lov = take2(fn(0, table) + ofs); | |

hiv = take2(fn(nr - 1, table) + ofs); | |

miv = take2(sha1 + ofs); | |

if (miv < lov) | |

return -1; | |

if (hiv < miv) | |

return -1 - nr; | |

if (lov != hiv) { | |

/* | |

* At this point miv could be equal | |

* to hiv (but sha1 could still be higher); | |

* the invariant of (mi < hi) should be | |

* kept. | |

*/ | |

mi = (nr - 1) * (miv - lov) / (hiv - lov); | |

if (lo <= mi && mi < hi) | |

break; | |

die("BUG: assertion failed in binary search"); | |

} | |

} | |

if (18 <= ofs) | |

die("cannot happen -- lo and hi are identical"); | |

} | |

do { | |

int cmp; | |

cmp = hashcmp(fn(mi, table), sha1); | |

if (!cmp) | |

return mi; | |

if (cmp > 0) | |

hi = mi; | |

else | |

lo = mi + 1; | |

mi = (hi + lo) / 2; | |

} while (lo < hi); | |

return -lo-1; | |

} | |

/* | |

* Conventional binary search loop looks like this: | |

* | |

* unsigned lo, hi; | |

* do { | |

* unsigned mi = (lo + hi) / 2; | |

* int cmp = "entry pointed at by mi" minus "target"; | |

* if (!cmp) | |

* return (mi is the wanted one) | |

* if (cmp > 0) | |

* hi = mi; "mi is larger than target" | |

* else | |

* lo = mi+1; "mi is smaller than target" | |

* } while (lo < hi); | |

* | |

* The invariants are: | |

* | |

* - When entering the loop, lo points at a slot that is never | |

* above the target (it could be at the target), hi points at a | |

* slot that is guaranteed to be above the target (it can never | |

* be at the target). | |

* | |

* - We find a point 'mi' between lo and hi (mi could be the same | |

* as lo, but never can be as same as hi), and check if it hits | |

* the target. There are three cases: | |

* | |

* - if it is a hit, we are happy. | |

* | |

* - if it is strictly higher than the target, we set it to hi, | |

* and repeat the search. | |

* | |

* - if it is strictly lower than the target, we update lo to | |

* one slot after it, because we allow lo to be at the target. | |

* | |

* If the loop exits, there is no matching entry. | |

* | |

* When choosing 'mi', we do not have to take the "middle" but | |

* anywhere in between lo and hi, as long as lo <= mi < hi is | |

* satisfied. When we somehow know that the distance between the | |

* target and lo is much shorter than the target and hi, we could | |

* pick mi that is much closer to lo than the midway. | |

* | |

* Now, we can take advantage of the fact that SHA-1 is a good hash | |

* function, and as long as there are enough entries in the table, we | |

* can expect uniform distribution. An entry that begins with for | |

* example "deadbeef..." is much likely to appear much later than in | |

* the midway of the table. It can reasonably be expected to be near | |

* 87% (222/256) from the top of the table. | |

* | |

* However, we do not want to pick "mi" too precisely. If the entry at | |

* the 87% in the above example turns out to be higher than the target | |

* we are looking for, we would end up narrowing the search space down | |

* only by 13%, instead of 50% we would get if we did a simple binary | |

* search. So we would want to hedge our bets by being less aggressive. | |

* | |

* The table at "table" holds at least "nr" entries of "elem_size" | |

* bytes each. Each entry has the SHA-1 key at "key_offset". The | |

* table is sorted by the SHA-1 key of the entries. The caller wants | |

* to find the entry with "key", and knows that the entry at "lo" is | |

* not higher than the entry it is looking for, and that the entry at | |

* "hi" is higher than the entry it is looking for. | |

*/ | |

int sha1_entry_pos(const void *table, | |

size_t elem_size, | |

size_t key_offset, | |

unsigned lo, unsigned hi, unsigned nr, | |

const unsigned char *key) | |

{ | |

const unsigned char *base = table; | |

const unsigned char *hi_key, *lo_key; | |

unsigned ofs_0; | |

static int debug_lookup = -1; | |

if (debug_lookup < 0) | |

debug_lookup = !!getenv("GIT_DEBUG_LOOKUP"); | |

if (!nr || lo >= hi) | |

return -1; | |

if (nr == hi) | |

hi_key = NULL; | |

else | |

hi_key = base + elem_size * hi + key_offset; | |

lo_key = base + elem_size * lo + key_offset; | |

ofs_0 = 0; | |

do { | |

int cmp; | |

unsigned ofs, mi, range; | |

unsigned lov, hiv, kyv; | |

const unsigned char *mi_key; | |

range = hi - lo; | |

if (hi_key) { | |

for (ofs = ofs_0; ofs < 20; ofs++) | |

if (lo_key[ofs] != hi_key[ofs]) | |

break; | |

ofs_0 = ofs; | |

/* | |

* byte 0 thru (ofs-1) are the same between | |

* lo and hi; ofs is the first byte that is | |

* different. | |

* | |

* If ofs==20, then no bytes are different, | |

* meaning we have entries with duplicate | |

* keys. We know that we are in a solid run | |

* of this entry (because the entries are | |

* sorted, and our lo and hi are the same, | |

* there can be nothing but this single key | |

* in between). So we can stop the search. | |

* Either one of these entries is it (and | |

* we do not care which), or we do not have | |

* it. | |

* | |

* Furthermore, we know that one of our | |

* endpoints must be the edge of the run of | |

* duplicates. For example, given this | |

* sequence: | |

* | |

* idx 0 1 2 3 4 5 | |

* key A C C C C D | |

* | |

* If we are searching for "B", we might | |

* hit the duplicate run at lo=1, hi=3 | |

* (e.g., by first mi=3, then mi=0). But we | |

* can never have lo > 1, because B < C. | |

* That is, if our key is less than the | |

* run, we know that "lo" is the edge, but | |

* we can say nothing of "hi". Similarly, | |

* if our key is greater than the run, we | |

* know that "hi" is the edge, but we can | |

* say nothing of "lo". | |

* | |

* Therefore if we do not find it, we also | |

* know where it would go if it did exist: | |

* just on the far side of the edge that we | |

* know about. | |

*/ | |

if (ofs == 20) { | |

mi = lo; | |

mi_key = base + elem_size * mi + key_offset; | |

cmp = memcmp(mi_key, key, 20); | |

if (!cmp) | |

return mi; | |

if (cmp < 0) | |

return -1 - hi; | |

else | |

return -1 - lo; | |

} | |

hiv = hi_key[ofs_0]; | |

if (ofs_0 < 19) | |

hiv = (hiv << 8) | hi_key[ofs_0+1]; | |

} else { | |

hiv = 256; | |

if (ofs_0 < 19) | |

hiv <<= 8; | |

} | |

lov = lo_key[ofs_0]; | |

kyv = key[ofs_0]; | |

if (ofs_0 < 19) { | |

lov = (lov << 8) | lo_key[ofs_0+1]; | |

kyv = (kyv << 8) | key[ofs_0+1]; | |

} | |

assert(lov < hiv); | |

if (kyv < lov) | |

return -1 - lo; | |

if (hiv < kyv) | |

return -1 - hi; | |

/* | |

* Even if we know the target is much closer to 'hi' | |

* than 'lo', if we pick too precisely and overshoot | |

* (e.g. when we know 'mi' is closer to 'hi' than to | |

* 'lo', pick 'mi' that is higher than the target), we | |

* end up narrowing the search space by a smaller | |

* amount (i.e. the distance between 'mi' and 'hi') | |

* than what we would have (i.e. about half of 'lo' | |

* and 'hi'). Hedge our bets to pick 'mi' less | |

* aggressively, i.e. make 'mi' a bit closer to the | |

* middle than we would otherwise pick. | |

*/ | |

kyv = (kyv * 6 + lov + hiv) / 8; | |

if (lov < hiv - 1) { | |

if (kyv == lov) | |

kyv++; | |

else if (kyv == hiv) | |

kyv--; | |

} | |

mi = (range - 1) * (kyv - lov) / (hiv - lov) + lo; | |

if (debug_lookup) { | |

printf("lo %u hi %u rg %u mi %u ", lo, hi, range, mi); | |

printf("ofs %u lov %x, hiv %x, kyv %x\n", | |

ofs_0, lov, hiv, kyv); | |

} | |

if (!(lo <= mi && mi < hi)) | |

die("assertion failure lo %u mi %u hi %u %s", | |

lo, mi, hi, sha1_to_hex(key)); | |

mi_key = base + elem_size * mi + key_offset; | |

cmp = memcmp(mi_key + ofs_0, key + ofs_0, 20 - ofs_0); | |

if (!cmp) | |

return mi; | |

if (cmp > 0) { | |

hi = mi; | |

hi_key = mi_key; | |

} else { | |

lo = mi + 1; | |

lo_key = mi_key + elem_size; | |

} | |

} while (lo < hi); | |

return -lo-1; | |

} |