diff -r 57875cf423c9 -r 2372284d9457 mercurial/pvec.py --- a/mercurial/pvec.py Sat Oct 05 10:29:34 2019 -0400 +++ b/mercurial/pvec.py Sun Oct 06 09:45:02 2019 -0400 @@ -56,13 +56,14 @@ util, ) -_size = 448 # 70 chars b85-encoded +_size = 448 # 70 chars b85-encoded _bytes = _size / 8 _depthbits = 24 _depthbytes = _depthbits / 8 _vecbytes = _bytes - _depthbytes _vecbits = _vecbytes * 8 -_radius = (_vecbits - 30) / 2 # high probability vectors are related +_radius = (_vecbits - 30) / 2 # high probability vectors are related + def _bin(bs): '''convert a bytestring to a long''' @@ -71,6 +72,7 @@ v = v * 256 + ord(b) return v + def _str(v, l): bs = "" for p in pycompat.xrange(l): @@ -78,13 +80,16 @@ v >>= 8 return bs + def _split(b): '''depth and bitvec''' return _bin(b[:_depthbytes]), _bin(b[_depthbytes:]) + def _join(depth, bitvec): return _str(depth, _depthbytes) + _str(bitvec, _vecbytes) + def _hweight(x): c = 0 while x: @@ -92,17 +97,21 @@ c += 1 x >>= 1 return c + + _htab = [_hweight(x) for x in pycompat.xrange(256)] + def _hamming(a, b): '''find the hamming distance between two longs''' d = a ^ b c = 0 while d: - c += _htab[d & 0xff] + c += _htab[d & 0xFF] d >>= 8 return c + def _mergevec(x, y, c): # Ideally, this function would be x ^ y ^ ancestor, but finding # ancestors is a nuisance. So instead we find the minimal number @@ -116,7 +125,7 @@ hdist = _hamming(v1, v2) ddist = d1 - d2 v = v1 - m = v1 ^ v2 # mask of different bits + m = v1 ^ v2 # mask of different bits i = 1 if hdist > ddist: @@ -140,10 +149,12 @@ return depth, v + def _flipbit(v, node): # converting bit strings to longs is slow - bit = (hash(node) & 0xffffffff) % _vecbits - return v ^ (1< delta: return False return True