S = 16 # block size

# opcodes:
# 0 => copy. size (3 bytes), offset (4 bytes). => 8 bytes 
# n => insert n bytes => (1 + n)

def applyDelta(delta, src)
  tgt = ""
  delta.each do |op, arg1, arg2|
    case op
    when :insert
      tgt << arg1
    when :copy
      tgt << src[arg1, arg2]
    else
      raise
    end
  end
  tgt
end

# delta here is a delta_port
def applyExternalDelta(delta, src)
  tgt = ""
  i = 0
  while i < delta.size 
    len = delta[i, 1].unpack('C').first
    if len == 0
      # copy operation
      sz, off = delta[i, 8].unpack('NN')  
      raise unless sz
      raise unless off
      tgt << src[off, sz] 
      i += 8
    else
      # insert operation
      data = delta[i+1, len] 
      raise if data.size != len
      tgt << data  
      i += 1 + len
    end
  end
  tgt
end

def encodeOp(port, op, arg1, arg2=nil)
  case op
  when :insert
    str = arg1
    0.step(str.size, 255) do |off|
      sz = [255, str.size - off].min
      raise if sz <= 0
      port << sz.chr
      port << str[off, sz] 
    end
  when :copy
    off, sz = arg1, arg2
    raise if sz <= 0

    # split up sz in chunks of 2**24-1
    0.step(sz, 2**24-1) do |o|
      port << [[2**24-1, sz-o].min, off+o].pack("NN")
    end
  else
    raise
  end
end

def computeDelta(src, tgt)
  initMatch(src, sindex = Hash.new)
  i = 0
  last_insert_pos = nil 

  while i < tgt.size
    o, l = findMatch(src, sindex, tgt, i)
    if l < S
      last_insert_pos ||= i
      i += 1
    else
      if last_insert_pos
        yield :insert, tgt[last_insert_pos...i]
        last_insert_pos = nil
      end
      yield :copy, o, l
      i += l
    end
  end # while
  if last_insert_pos
    yield :insert, tgt[last_insert_pos...i]
    last_insert_pos = nil
  end
end

def initMatch(src, sindex=Hash.new)
  0.upto(src.size - S) do |i|
    block = src[i, S]
    sindex[block] = i
  end
end

def findMatch(src, sindex, tgt, off_tgt)
  block = tgt[off_tgt, S]
  off_src = sindex[block]
  if off_src = sindex[block]
    len = matchLength(tgt, off_tgt, src, off_src) 
    [off_src, len]
  else
    [-1, -1]
  end
end

def matchLength(tgt, off_tgt, src, off_src)
  l = 0
  l += 1 while tgt[off_tgt+l] == src[off_src+l]
  return l
end

if __FILE__ == $0
  src = File.read('/home/mneumann/xdelta.rb.old')
  tgt = File.read('xdelta.rb')
  delta = []
  extDelta = ""
  computeDelta(src, tgt) do |*x|
    delta << x
    encodeOp(extDelta, *x) 
  end

  tgt2 = applyDelta(delta, src)
  raise unless tgt == tgt2

  tgt3 = applyExternalDelta(extDelta, src)
  raise unless tgt == tgt3
end