local fs = fs or require "filesystem"
local common = require "fs.rtfs"
local rtfs, proxy = {}, setmetatable({},{__index=common.proxy})
local ieformat = ">I2I8I8c46" -- type (4 bits) and index (12 bits), start sector (32 bits), lenth in bytes (32 bits), name/path (46 bytes)
local sbformat = ">c4I2I8c18" -- "rtfs" magic, version, index size in entries, label. label length subject to change.
local iesize = string.packsize(ieformat)
local ftypes = {
 empty = 0,
 dfile = 1,
 dfext = 2,
 ddir = 3,
 ddex = 4,
 tfile = 5,
 text = 6,
 dlink = 7,
 unused = 8,
 file = 9,
 fext = 10,
 dir = 11,
 dex = 12,
 link = 15
}

-- data mangling functions
local fnormalize = common.fnormalize
function proxy:cSOI(n)
 n=n-1
 local ms = self.capacity / self.blockSize
 local ePS = self.blockSize // iesize
 local s = n // ePS
 local so = self.blockSize - iesize - ((n % ePS) * iesize)
 local eo = so + iesize
 return ms - s, so+1, eo
end

-- superblock stuff
function proxy:updateSB()
 self:cachedWrite(1,string.pack(sbformat, "rtfs", 1, self.isize, self.label))
end 
function proxy:setISize(n)
 if self.isize ~= n then
  self.isize = n
  self:updateSB()
 end
end

-- index I/O
function proxy:readIEntry(n)
 local sector, sstart, send = self:cSOI(n)
 local rt = {string.unpack(ieformat,self:cachedRead(sector):sub(sstart, send))}
 local et, ex = rt[1]>>12, rt[1]&0x1FF
 rt[4] = rt[4]:gsub("\0","")
 rt[5] = nil
 return et, ex, table.unpack(rt,2)
end
function proxy:writeIEntry(n,et,ex,es,el,en) -- index, type, extent index, extent start, extent length, extent name
 local ne = string.pack(ieformat, (et<<12) | (ex & 0x1FF), es, el, en)
 local sector, sstart, send = self:cSOI(n)
 -- check if there's an extent in the way of this entry
 while self:findIEntry(nil,nil,nil,nil,nil,sector) do
  self:log("auto-compact triggered")
  -- compactIndex will shrink the extent if it is safe to overwrite (deleted, free, etc)
  n = self:compactIndex(n) or self.isize + 1
  local newn = n == self.isize + 1
  -- if that fails, because it can't be shrunk, we need to move it ourselves
  local fi, ft = self:findIEntry(nil,nil,nil,nil,nil,sector)
  if fi and ft[1] > ftypes.unused then
   self:log("auto-compact unsuccessful, trying to relocate extent")
   -- try to find a suitable free space
   local lfi, lfis = self:bestFree()
   local lf = {self:readIEntry(lfi)}
   -- if it's not big enough, give up.
   assert(lf[4] >= ft[4], "unable to relocate extent to write index entry")
   -- if it is, create an extent structure at the end of the free space
   local de = {ft[1], ft[2], lf[3] + lf[4]//self.blockSize - math.ceil(ft[4]/self.blockSize), ft[4], ft[5]}
   lf[4] = lf[4] - (math.ceil(ft[4] / self.blockSize) * self.blockSize)
   -- move the data to the new extent
   for i = 0, ft[4]//self.blockSize do
    self:writeExtent(de, i, self:readExtent(ft, i))
   end
   -- overwrite the old entries, which shouldn't get us back here
   self:writeIEntry(fi, table.unpack(de))
   self:writeIEntry(lfi, table.unpack(lf))
   -- and finally, make a new entry for the now old data, sans one sector
   self:writeIEntry(self:nextEntry(), ft[1]-8, ft[2], ft[3], ft[4] - self.blockSize, ft[5])
  end
  -- if the aim was to make a new entry, update n so it will do so
  n = newn and self.isize + 1 or n
  sector, sstart, send = self:cSOI(n)
 end
 local pes = self:cachedRead(sector)
 local ns = pes:sub(1, sstart - 1) .. ne .. pes:sub(send + 1)
 self:cachedWrite(sector, ns)
 self:setISize(math.max(self.isize, n))
 return n
end
function proxy:allIEntries()
 local i = 0
 return function()
  if i < self.isize then
   i = i + 1
   return i, self:readIEntry(i)
  end
  return nil
 end
end

-- for debugging
function proxy:dumpIndex()
 local t = {}
 for i, tp, ei, st, sl, n in self:allIEntries() do
  t[#t+1] = {i,tp,ei,st,sl,(st+math.ceil(sl/self.blockSize))-1,n}
 end
 table.sort(t, function(a,b) return a[4] < b[4] end)
 print(" # ty ext# init      len  end name")
 for k,v in ipairs(t) do
  if k % 23 == 0 then
   io.read()
   print(" # ty ext# init      len  end name")
  end
  print(string.format("%2i  %1x %4i %4i %8i %4i %s",table.unpack(v)))
 end
end

-- index searching
function proxy:findIEntry(et,ex,es,el,en,ef) -- number number number string number -- Find an entry matching all provided parameters and ignoring any not specified.
 local ri, rt
 for i, tp, ix, st, sl, n in self:allIEntries() do
  local sf = st + math.ceil(sl/self.blockSize) - 1
  if (et or tp) == tp and (ex or ix) == ix and (es or st) == st and (el or sl) == sl and (en or n) == n and (ef or sf) == sf then
   ri, rt = i, {self:readIEntry(i)}
   break
  end
 end
 return ri, rt
end
function proxy:nextEntry()
 local ni = self.isize+1
 for i, tp in self:allIEntries() do
  if tp == ftypes.unused then
   ni = i
   break
  end
 end
 return ni
end

-- extent allocation
function proxy:bestFree(last)
 local ri, sri
 local bs, sbs = 0, 0
 if last then
  ri, rs = self:findIEntry(nil,nil,last[3]+math.ceil(last[4]/self.blockSize))
  if ri and rs and rs[1] <= ftypes.ddex then
   return ri, false, true
  end
 end
 for i, tp, ei, st, sl, n in self:allIEntries() do
  if tp <= ftypes.ddex then
   if sl > bs then
    sri, sbs = ri, bs
    ri, bs = i, sl
   end
  end
 end
 return bs/2 > sbs and ri or sri, bs/2 > sbs
end
function proxy:allocateExtent(name, etype, ei, esize, last)
 etype, ei, esize = etype or ftypes.tfile, ei or 0, math.ceil(math.max(4096,esize or self.capacity / 256)/self.blockSize)*self.blockSize
 self:compactIndex()
 local lfi,lfis,lfext = self:bestFree(last)
 local lf = {self:readIEntry(lfi)}
 local esize = math.min(esize, lf[4])
 local lfs, es = lf[4]//self.blockSize, esize//self.blockSize
 -- if biggest available area, split and put extent in the middle
 if lfis then
  local new = {etype, ei, lf[3] + math.floor(lfs/2), esize, name}
  lf[4] = math.floor(lfs/2) * self.blockSize
  local free = {ftypes.empty, 0, new[3] + es, lfs*self.blockSize - new[4] - lf[4], ""}
  self:writeIEntry(lfi, table.unpack(lf))
  self:writeIEntry(self:nextEntry(), table.unpack(new))
  self:writeIEntry(self:nextEntry(), table.unpack(free))
  return self:findIEntry(etype, ei, nil, nil, name)
 else -- otherwise, put it at the start
  local new = {etype, ei, lf[3], esize, name}
  local free = {ftypes.empty, 0, new[3] + es, lfs*self.blockSize - new[4], ""}
  local efi, eff
  if last then
   last={table.unpack(last)}
   efi, eff = self:findIEntry(table.unpack(last))
  end
  -- if a previous entry was provided and the name matches, continue the extent
  if lfext and efi and name == eff[5] then
   last[4] = math.ceil((last[4] + new[4]) / self.blockSize) * self.blockSize
   new = last
   self:writeIEntry(efi, table.unpack(new))
   self:writeIEntry(lfi, table.unpack(free))
   lfi=efi
  -- failing that, replace the free space entry with the new extent and
  -- write a new free space entry
  else
   self:writeIEntry(lfi, table.unpack(new))
   self:writeIEntry(self:nextEntry(), table.unpack(free))
  end
  return lfi, new, lfext and new[4]
 end
 return false
end

function proxy:writeExtent(ft, o, d) -- write a sector to an extent
 assert(o >= 0 and o < (ft[4]//self.blockSize) + 1, "out of range")
 assert(#d <= self.blockSize, "block too large")
 return self.d.writeSector(ft[3] + o, d .. ("\0"):rep(self.blockSize - #d))
end
function proxy:readExtent(ft, o) -- read a sector from an extent
 assert(o >= 0 and o < (ft[4]//self.blockSize) + 1, "out of range")
 return self.d.readSector(ft[3] + o):sub(1, math.min(self.blockSize, ft[4] - (o*self.blockSize)))
end

function proxy:openHandle(name, mode, fmt)
 name, fmt = fnormalize(name), fmt or {ftypes.file, ftypes.fext, ftypes.tfile, ftypes.text}
 local handle, xt = {aft={},fmt=fmt,buffer="",bytes=0}
 for c in mode:gmatch(".") do
  handle[c] = true
 end
 local fi, oft = self:findIEntry(fmt[1], nil, nil, nil, name)
 if handle.r then
  if not fi then
   return false, "file not found"
  end
  handle.ft, handle.aft[1] = oft, oft
 elseif handle.w or handle.a then
  if handle.a and fi then
   local lfi, lf = self:findIEntry(fmt[2], oft[2], nil, nil, oft[5])
   fi, handle.ft, xt = self:allocateExtent(name, fmt[4], oft[2] + 1, nil, lf or oft)
   -- if in append mode, put the file extent into the "all extents" table to be updated later
   handle.aft[1], handle.bytes = oft, xt and (lfi and lf[4] or oft[4]) or 0
   -- read the last sector into the write buffer so it can be written back to disk with new data
   -- then rewind the counter so it does get written
   if handle.bytes%self.blockSize ~= 0 then
    handle.buffer = self:readExtent(lf or oft, handle.bytes//512)
    handle.bytes = handle.bytes - #handle.buffer
   end
  else
   -- allocate the new extent to write into
   fi, handle.ft = self:allocateExtent(name, fmt[3])
  end
  handle.aft[#handle.aft+(xt and 0 or 1)] = handle.ft
 end
 local ni = #self.handles+1
 self.handles[ni] = handle
 return ni
end

function proxy:closeHandle(h)
 local handle = self.handles[h]
 if handle.w or handle.a then
  -- flush the buffer just in case
  self:writeHandle(h, "", true)
  local fs = handle.ft[4] - handle.bytes
  -- update each index entry 
  self:compactIndex()
  -- mark any old entries with a matching name as deleted when not appending
  if not handle.a then
   for i, tp, ei, st, sl, n in self:allIEntries() do
    if n == handle.aft[1][5] and tp > 8 then
     self:writeIEntry(i, tp-8, ei, st, sl, n)
    end
   end
  end
  for k,v in ipairs(handle.aft) do
   local fi, ft = self:findIEntry(table.unpack(v))
   self:writeIEntry(fi,
    -- determine if it's the file or extent part
    (v[1] == handle.fmt[3] or v[1] == handle.fmt[1]) and handle.fmt[1] or handle.fmt[2],
    -- file part wants the number of extents, extents want their index
    (v[1] == handle.fmt[3] or v[1] == handle.fmt[1]) and handle.ft[2] or v[2],
    -- the rest is fine as is, unless it's the last item
    v[3], v == handle.ft and handle.bytes or v[4], v[5]
   )
  end
  if fs > self.blockSize then
   self:writeIEntry(self:nextEntry(), ftypes.empty, 0, handle.ft[3] + math.ceil(handle.bytes / self.blockSize), (fs//self.blockSize)*self.blockSize, "")
   self:compactIndex()
  end
 end
 self.handles[h] = nil
end

function proxy:writeHandle(h,d,f)
 local handle = self.handles[h]
 assert(handle.w or handle.a, "file not open in writable mode")
 handle.buffer = handle.buffer .. d
 local rv
 -- only attempt to write when there's enough data, or forced
 while #handle.buffer >= self.blockSize or f do 
  f = false
  -- allocate a new extent if this one is full
  if handle.bytes >= handle.ft[4] then
   local fi, ft, xt = self:allocateExtent(handle.ft[5], handle.fmt[4], handle.ft[2] + 1, nil, handle.ft)
   if xt then
    handle.aft[#handle.aft], handle.ft = ft, ft
   else
    handle.aft[#handle.aft+1], handle.ft, handle.bytes = ft, ft, 0
   end
  end
  -- write a block and increment the counter
  local wb = handle.buffer:sub(1, self.blockSize)
  handle.buffer = handle.buffer:sub(self.blockSize + 1)
  rv = self:writeExtent(handle.ft, handle.bytes//self.blockSize, wb)
  handle.bytes = handle.bytes + #wb
 end
 return rv
end

function proxy:readHandle(h)
 local handle = self.handles[h]
 assert(handle.r, "file not open in read mode")
 -- if there's no more data in the extent, find the next
 if handle.bytes >= handle.ft[4] then
  local ce = handle.ft[1] == handle.fmt[2] and handle.ft[2] or 0
  if ce >= handle.aft[1][2] then
   return nil
  end
  local fi, ft = self:findIEntry(handle.fmt[2], ce + 1, nil, nil, handle.ft[5])
  handle.aft[#handle.aft+1], handle.ft, handle.bytes = ft, ft, 0
 end
 local rb = self:readExtent(handle.ft, handle.bytes//512)
 handle.bytes = handle.bytes + #rb
 return rb
end

function proxy:compactIndex(ti)
 -- compact contingous free space
 for i, tp, ei, st, sl, n in self:allIEntries() do
  if tp <= ftypes.ddex then
   sl=math.max(sl/self.blockSize)
   local ni, nt = self:findIEntry(nil,nil,st+sl)
   if ni and nt and nt[1] <= ftypes.ddex then
    self:writeIEntry(i,tp,ei,st,(sl*self.blockSize)+nt[4],n)
    self:writeIEntry(ni,ftypes.unused,0,0,0,"")
   elseif tp <= ftypes.ddex and sl < 1 then
    self:writeIEntry(i,ftypes.unused,0,0,0,"")
   end
  end
 end
 local ri
 -- reverse walk the index to find holes
 for i = self.isize, 1, -1 do
  local ne = self:nextEntry() or self.isize
  local ft = {self:readIEntry(i)}
  if ne < i then
   self:writeIEntry(ne, table.unpack(ft))
   self:setISize(i-1)
   ri = (ti == i) and ne or ri
  end 
 end

 -- resize space at end of disk
 local li, ls, lt = 0, 0, nil
 for i, tp, ei, st, sl, n in self:allIEntries() do
  sl=math.max(sl/self.blockSize)
  if st+sl > ls then
   li, ls = i, st+sl
   lt = {tp, ei, st, sl, n}
  end
 end
 if lt[1] <= ftypes.text then
  local lastsec = (self.capacity / self.blockSize) - math.ceil(self.isize / (self.blockSize / iesize))
  self:writeIEntry(li, lt[1], lt[2], lt[3], (lastsec - lt[3])*self.blockSize, lt[5])
 end
 return ri
end

function rtfs.mount(p,ro)
 local d = common.getProxy(p)
 local p = setmetatable({}, {__index=proxy})
 p.d = d
 p.fstype, p.version, p.isize, p.label = string.unpack(sbformat,d.readSector(1))
 assert(p.fstype == "rtfs", "incorrect magic")
 assert(p.version == 1, "incompatible rtfs version")
 p.d = d
 p.cache, p.handles = {}, {}
 p.cacheHits, p.cacheMisses = 0, 0
 p.blockSize, p.capacity, p.label = d.getSectorSize(), d.getCapacity(), p.label:gsub("\0","")

 -- FS proxy functions
 function p.exists(name)
  name = fnormalize(name)
  for i, tp, ex, st, sl, n in p:allIEntries() do
   if (tp == ftypes.file or tp == ftypes.dir) and n == name then
    return true
   end
  end
 end
 function p.isDirectory(name)
  name = fnormalize(name)
  return name == "" and true or p:findIEntry(ftypes.dir, nil, nil, nil, name) ~= nil
 end
 function p.size(name)
  name = fnormalize(name)
  local rv = 0
  for i, tp, ex, st, sl, n in p:allIEntries() do
   if n == name and tp > ftypes.unused then
    rv = rv + sl
   end
  end
  return rv
 end
 function p.spaceUsed()
  local c = 0
  for i, tp, ex, st, sl, n in p:allIEntries() do
   if tp > ftypes.unused then
    c = c + sl
   end
  end
  return c
 end
 function p.spaceTotal()
  return p.capacity - (math.ceil(p.isize / (p.blockSize / iesize))*p.blockSize) - p.blockSize
 end
 p.isReadOnly = p.d.isReadOnly or function() return ro or false end

 function p.list(name)
  name = fnormalize(name)
  local rt = {}
  for i, tp, ex, st, sl, n in p:allIEntries() do
   local seg = fs.segments(n)
   local pn = table.concat(seg,"/",1,#seg-1)
   local fn = seg[#seg]
   if (tp == ftypes.file or tp == ftypes.dir) and pn == name then
    rt[#rt+1] = fn .. ((tp == ftypes.dir and "/") or "")
   end
  end
  return rt
 end
 function p.makeDirectory(name)
  name = fnormalize(name)
  if #name < 1 or p:findIEntry(nil,nil,nil,nil,name) then return false end
  local seg = fs.segments(name)
  for j = 1, #seg-1 do
   p.makeDirectory(table.concat(seg, "/", 1, j))
  end
  if not p.isDirectory(table.concat(seg,"/",1,#seg-1)) then return false end
  local ni = p:nextEntry()
  p:writeIEntry(ni, ftypes.dir, 0, 0, 0, name)
--  p:setISize(math.max(p.isize, ni))
  return true
 end

 function p.remove(name)
  name = fnormalize(name)
  for i, tp, ex, st, sl, n in p:allIEntries() do
   if n == name and tp > ftypes.unused then
    p:writeIEntry(i, tp-8, ex, st, sl, n)
   end
  end
 end

 function p.rename(from, to)
  from, to = fnormalize(from), fnormalize(to)
  if p.exists(from) then
   if p.exists(to) then
    p.remove(to)
   end
   local fi, ft = p:findIEntry(p.isDirectory(name) and ftypes.dir or ftypes.file, nil, nil, to)
   ft[5] = to
   p:writeIEntry(fi, table.unpack(ft))
  end
 end
 function p.lastModified()
  return 0
 end

 function p.open(name, mode)
  name, mode = fnormalize(name), mode or "r"
  return p:openHandle(name, mode)
 end
 function p.write(h,v)
  return p:writeHandle(h,v)
 end
 function p.read(h,v)
  return p:readHandle(h,v)
 end
 function p.close(h)
  return p:closeHandle(h)
 end

 function p.getLabel()
  return p.label
 end
 function p.setLabel(label)
  p.label = label
  p:updateSB()
 end

 return p
end

function rtfs.format(p, label)
 local d = common.getProxy(p)
 print(d.address)
 d.writeSector(1, string.pack(sbformat,"rtfs", 1, 1, label or ""))
 rtfs.mount(d):writeIEntry(1, ftypes.empty, 0, 2, d.getCapacity() - (d.getSectorSize() * 2), "")
end

return rtfs