0: "", # EXT 1

1: "commit",

2: "tree",

3: "blob",

4: "tag",

5: "", # EXT 2

OFS_DELTA: "OFS_DELTA", # OFFSET DELTA

REF_DELTA: "REF_DELTA" # REFERENCE DELTA

commit=1,

tree=2,

blob=3,

tag=4,

OFS_DELTA=OFS_DELTA,

REF_DELTA=REF_DELTA

"""Truncate the given delta to the given size

d.ts = size

# NOTE: data is truncated automatically when applying the delta

# MUST NOT DO THIS HERE

"""Move the delta by the given amount of bytes, reducing its size so that its

if bytes == 0:

return

d.to += bytes

d.so += bytes

d.ts -= bytes

if d.data is not None:

d.data = d.data[bytes:]

# END handle data

"""Apply own data to the target buffer

if dc.data is None:

# COPY DATA FROM SOURCE

write(buffer(bbuf, dc.so, dc.ts))

else:

# APPEND DATA

# whats faster: if + 4 function calls or just a write with a slice ?

# Considering data can be larger than 127 bytes now, it should be worth it

if dc.ts < len(dc.data):

write(dc.data[:dc.ts])

else:

write(dc.data)

# END handle truncation

"""Represents a piece of a delta, it can either add new data, or copy existing

__slots__ = (

'to', # start offset in the target buffer in bytes

'ts', # size of this chunk in the target buffer in bytes

'so', # start offset in the source buffer in bytes or None

'data', # chunk of bytes to be added to the target buffer,

# DeltaChunkList to use as base, or None

)

def __init__(self, to, ts, so, data):

self.to = to

self.ts = ts

self.so = so

self.data = data

def __repr__(self):

return "DeltaChunk(%i, %i, %s, %s)" % (self.to, self.ts, self.so, self.data or "")

#{ Interface

def rbound(self):

return self.to + self.ts

def has_data(self):

""":return: True if the instance has data to add to the target stream"""

return self.data is not None

""":return: index at which the given absofs should be inserted. The index points

lo = 0

hi = len(dcl)

while lo < hi:

mid = (lo + hi) / 2

dc = dcl[mid]

if dc.to > absofs:

hi = mid

elif dc.rbound() > absofs or dc.to == absofs:

return mid

else:

lo = mid + 1

# END handle bound

# END for each delta absofs

"""Apply the chain's changes and write the final result using the passed

for dc in dcl:

delta_chunk_apply(dc, bbuf, write)

""":return: Subsection of this list at the given absolute offset, with the given

cdi = _closest_index(dcl, absofs) # delta start index

cd = dcl[cdi]

slen = len(dcl)

lappend = ndcl.append

if cd.to != absofs:

tcd = DeltaChunk(cd.to, cd.ts, cd.so, cd.data)

_move_delta_lbound(tcd, absofs - cd.to)

tcd.ts = min(tcd.ts, size)

lappend(tcd)

size -= tcd.ts

cdi += 1

# END lbound overlap handling

while cdi < slen and size:

# are we larger than the current block

cd = dcl[cdi]

if cd.ts <= size:

lappend(DeltaChunk(cd.to, cd.ts, cd.so, cd.data))

size -= cd.ts

else:

tcd = DeltaChunk(cd.to, cd.ts, cd.so, cd.data)

tcd.ts = size

lappend(tcd)

size -= tcd.ts

break

# END hadle size

cdi += 1

"""List with special functionality to deal with DeltaChunks.

__slots__ = tuple()

def rbound(self):

""":return: rightmost extend in bytes, absolute"""

if len(self) == 0:

return 0

return self[-1].rbound()

def lbound(self):

""":return: leftmost byte at which this chunklist starts"""

if len(self) == 0:

return 0

return self[0].to

def size(self):

""":return: size of bytes as measured by our delta chunks"""

return self.rbound() - self.lbound()

def apply(self, bbuf, write):

"""Only used by public clients, internally we only use the global routines

return delta_list_apply(self, bbuf, write)

def compress(self):

"""Alter the list to reduce the amount of nodes. Currently we concatenate

slen = len(self)

if slen < 2:

return self

i = 0

slen_orig = slen

first_data_index = None

while i < slen:

dc = self[i]

i += 1

if dc.data is None:

if first_data_index is not None and i - 2 - first_data_index > 1:

# if first_data_index is not None:

nd = StringIO() # new data

so = self[first_data_index].to # start offset in target buffer

for x in xrange(first_data_index, i - 1):

xdc = self[x]

nd.write(xdc.data[:xdc.ts])

# END collect data

del(self[first_data_index:i - 1])

buf = nd.getvalue()

self.insert(first_data_index, DeltaChunk(so, len(buf), 0, buf))

slen = len(self)

i = first_data_index + 1

# END concatenate data

first_data_index = None

continue

# END skip non-data chunks

if first_data_index is None:

first_data_index = i - 1

# END iterate list

# if slen_orig != len(self):

# print "INFO: Reduced delta list len to %f %% of former size" % ((float(len(self)) / slen_orig) * 100)

return self

def check_integrity(self, target_size=-1):

"""Verify the list has non-overlapping chunks only, and the total size matches

if target_size > -1:

assert self[-1].rbound() == target_size

assert reduce(lambda x, y: x + y, (d.ts for d in self), 0) == target_size

# END target size verification

if len(self) < 2:

return

# check data

for dc in self:

assert dc.ts > 0

if dc.has_data():

assert len(dc.data) >= dc.ts

# END for each dc

left = islice(self, 0, len(self) - 1)

right = iter(self)

right.next()

# this is very pythonic - we might have just use index based access here,

# but this could actually be faster

for lft, rgt in izip(left, right):

assert lft.rbound() == rgt.to

assert lft.to + lft.ts == rgt.to

"""Represents a list which is generated by feeding its ancestor streams one by

__slots__ = tuple()

def connect_with_next_base(self, bdcl):

"""Connect this chain with the next level of our base delta chunklist.

nfc = 0 # number of frozen chunks

dci = 0 # delta chunk index

slen = len(self) # len of self

ccl = list() # temporary list

while dci < slen:

dc = self[dci]

dci += 1

# all add-chunks which are already topmost don't need additional processing

if dc.data is not None:

nfc += 1

continue

# END skip add chunks

# copy chunks

# integrate the portion of the base list into ourselves. Lists

# dont support efficient insertion ( just one at a time ), but for now

# we live with it. Internally, its all just a 32/64bit pointer, and

# the portions of moved memory should be smallish. Maybe we just rebuild

# ourselves in order to reduce the amount of insertions ...

del(ccl[:])

delta_list_slice(bdcl, dc.so, dc.ts, ccl)

# move the target bounds into place to match with our chunk

ofs = dc.to - dc.so

for cdc in ccl:

cdc.to += ofs

# END update target bounds

if len(ccl) == 1:

self[dci - 1] = ccl[0]

else:

# maybe try to compute the expenses here, and pick the right algorithm

# It would normally be faster than copying everything physically though

# TODO: Use a deque here, and decide by the index whether to extend

# or extend left !

post_dci = self[dci:]

del(self[dci - 1:]) # include deletion of dc

self.extend(ccl)

self.extend(post_dci)

slen = len(self)

dci += len(ccl) - 1 # deleted dc, added rest

# END handle chunk replacement

# END for each chunk

if nfc == slen:

return False

# END handle completeness

"""

b0, b1 = map(ord, m[:2])

word = (b0 << 8) + b1

"""

decompress_size = 8192 # is used in cgit as well

hdr = decompressobj().decompress(m, decompress_size)

type_name, size = hdr[:hdr.find("\0")].split(" ")

"""

c = ord(data[0]) # first byte

i = 1 # next char to read

type_id = (c >> 4) & 7 # numeric type

size = c & 15 # starting size

s = 4 # starting bit-shift size

while c & 0x80:

c = ord(data[i])

i += 1

size += (c & 0x7f) << s

s += 7

# END character loop

""":return: string defining the pack header comprised of the object type

c = 0 # 1 byte

hdr = str() # output string

c = (obj_type << 4) | (obj_size & 0xf)

obj_size >>= 4

while obj_size:

hdr += chr(c | 0x80)

c = obj_size & 0x7f

obj_size >>= 7

# END until size is consumed

hdr += chr(c)

"""

size = 0

i = 0

l = len(data)

hit_msb = False

while i < l:

c = ord(data[i + offset])

size |= (c & 0x7f) << i * 7

i += 1

if not c & 0x80:

hit_msb = True

break

# END check msb bit

# END while in range

if not hit_msb:

raise AssertionError("Could not find terminating MSB byte in data stream")

"""

"""

tbw = 0 # total num bytes written

# WRITE HEADER: type SP size NULL

tbw += write(loose_object_header(type, size))

tbw += stream_copy(read, write, size, chunk_size)

"""

dbw = 0 # num data bytes written

# WRITE ALL DATA UP TO SIZE

while True:

cs = min(chunk_size, size - dbw)

# NOTE: not all write methods return the amount of written bytes, like

# mmap.write. Its bad, but we just deal with it ... perhaps its not

# even less efficient

# data_len = write(read(cs))

# dbw += data_len

data = read(cs)

data_len = len(data)

dbw += data_len

write(data)

if data_len < cs or dbw == size:

break

# END check for stream end

# END duplicate data

"""

tdcl = None # topmost dcl

dcl = tdcl = TopdownDeltaChunkList()

for dsi, ds in enumerate(dstreams):

# print "Stream", dsi

db = ds.read()

delta_buf_size = ds.size

# read header

i, base_size = msb_size(db)

i, target_size = msb_size(db, i)

# interpret opcodes

tbw = 0 # amount of target bytes written

while i < delta_buf_size:

c = ord(db[i])

i += 1

if c & 0x80:

cp_off, cp_size = 0, 0

if (c & 0x01):

cp_off = ord(db[i])

i += 1

if (c & 0x02):

cp_off |= (ord(db[i]) << 8)

i += 1

if (c & 0x04):

cp_off |= (ord(db[i]) << 16)

i += 1

if (c & 0x08):

cp_off |= (ord(db[i]) << 24)

i += 1

if (c & 0x10):

cp_size = ord(db[i])

i += 1

if (c & 0x20):

cp_size |= (ord(db[i]) << 8)

i += 1

if (c & 0x40):

cp_size |= (ord(db[i]) << 16)

i += 1

if not cp_size:

cp_size = 0x10000

rbound = cp_off + cp_size

if (rbound < cp_size or

rbound > base_size):

break

dcl.append(DeltaChunk(tbw, cp_size, cp_off, None))

tbw += cp_size

elif c:

# NOTE: in C, the data chunks should probably be concatenated here.

# In python, we do it as a post-process

dcl.append(DeltaChunk(tbw, c, 0, db[i:i + c]))

i += c

tbw += c

else:

raise ValueError("unexpected delta opcode 0")

# END handle command byte

# END while processing delta data

dcl.compress()

# merge the lists !

if dsi > 0:

if not tdcl.connect_with_next_base(dcl):

break

# END handle merge

# prepare next base

dcl = DeltaChunkList()

# END for each delta stream

"""

i = 0

db = delta_buf

while i < delta_buf_size:

c = ord(db[i])

i += 1

if c & 0x80:

cp_off, cp_size = 0, 0

if (c & 0x01):

cp_off = ord(db[i])

i += 1

if (c & 0x02):

cp_off |= (ord(db[i]) << 8)

i += 1

if (c & 0x04):

cp_off |= (ord(db[i]) << 16)

i += 1

if (c & 0x08):

cp_off |= (ord(db[i]) << 24)

i += 1

if (c & 0x10):

cp_size = ord(db[i])

i += 1

if (c & 0x20):

cp_size |= (ord(db[i]) << 8)

i += 1

if (c & 0x40):

cp_size |= (ord(db[i]) << 16)

i += 1

if not cp_size:

cp_size = 0x10000

rbound = cp_off + cp_size

if (rbound < cp_size or

rbound > src_buf_size):

break

write(buffer(src_buf, cp_off, cp_size))

elif c:

write(db[i:i + c])

i += c

else:

raise ValueError("unexpected delta opcode 0")

# END handle command byte

# END while processing delta data

# yes, lets use the exact same error message that git uses :)

"""

binary_length = canonical_length / 2

if match[:binary_length] != sha1[:binary_length]:

return False

if canonical_length - binary_length and \

(ord(match[-1]) ^ ord(sha1[len(match) - 1])) & 0xf0:

return False

# END handle uneven canonnical length