OC-WEB 3.0: A Web Browser For OpenComputers!

local component = require("component")
local event = require("event")
local internet = require("internet")
local term = require("term")
local unicode = require("unicode")
local computer = require("computer")
local filesystem = require("filesystem")

local collectgarbage = collectgarbage or function() end

local okBit, bit32lib = pcall(require, "bit32")
local bit32 = okBit and bit32lib or _G.bit32
local band, lshift, rshift = bit32.band, bit32.lshift, bit32.rshift

local gpu = component.gpu
local depth = gpu.getDepth()

local renderBuffer = nil
local renderW, renderH = 0, 0

local function ensureRenderBuffer(w, h)
  if renderBuffer then
    local ok, bw, bh = pcall(gpu.getBufferSize, renderBuffer)
    if ok and bw == w and bh == h then
      return true
    end
    pcall(gpu.setActiveBuffer, 0)
    pcall(gpu.freeBuffer, renderBuffer)
    renderBuffer = nil
  end

  local ok, buf = pcall(gpu.allocateBuffer, w, h)
  if not ok or not buf then
    return false
  end
  renderBuffer = buf
  renderW, renderH = w, h
  return true
end

local function freeRenderBuffer()
  if renderBuffer then
    pcall(gpu.setActiveBuffer, 0)
    pcall(gpu.freeBuffer, renderBuffer)
    renderBuffer = nil
    renderW, renderH = 0, 0
  end
end

local function beginBufferRender(w, h)
  if not ensureRenderBuffer(w, h) then
    pcall(gpu.setActiveBuffer, 0)
    return false
  end
  local ok = pcall(gpu.setActiveBuffer, renderBuffer)
  if not ok then
    renderBuffer = nil
    return false
  end
  return true
end

local function presentBuffer(w, h)
  pcall(gpu.setActiveBuffer, 0)
  pcall(gpu.bitblt, 0, 1, 1, w, h, renderBuffer, 1, 1)
end

local realCollect = rawget(_G, "collectgarbage")
local function gc()
  if realCollect then
    pcall(realCollect)
    pcall(realCollect)
    return
  end
  local okMem, free = pcall(computer.freeMemory)
  if not okMem or type(free) ~= "number" then free = 65536 end
  local count = math.max(200, math.min(3000, math.floor(free / 8 / 64)))
  for _ = 1, 3 do
    local junk = {}
    for i = 1, count do junk[i] = {} end
    junk = nil
    os.sleep(0)
  end
end

local LOAD_IMAGES = true

local MAX_IMAGE_PIXELS = 900000
local MAX_IMAGE_BYTES = 1000000
local MAX_IMAGE_ROWS = 80

local IMAGE_MODE = "half"

local MAX_PAGE_BYTES = 1000000

local LINK_MARKERS = true
local invertImages = false

local ENABLE_FORMS = true
local TAB_FOCUS = true

local floor, ceil, abs, min, max = math.floor, math.ceil, math.abs, math.min, math.max
local byte, char = string.byte, string.char
local unpack = table.unpack or unpack

local function trim(s)
  return (s:match("^%s*(.-)%s*$"))
end

local function set(list)
  local t = {}
  for _, v in ipairs(list) do t[v] = true end
  return t
end

local function copy(t)
  local n = {}
  for k, v in pairs(t) do n[k] = v end
  return n
end

local function lum(c)
  return 0.299 * (floor(c / 65536) % 256) + 0.587 * (floor(c / 256) % 256) + 0.114 * (c % 256)
end

local function emphasize(fg, bg)
  local target = lum(fg) >= lum(bg) and 255 or 0
  local r, g, b = floor(fg / 65536) % 256, floor(fg / 256) % 256, fg % 256
  r = floor(r + (target - r) * 0.4)
  g = floor(g + (target - g) * 0.4)
  b = floor(b + (target - b) * 0.4)
  return r * 65536 + g * 256 + b
end

local function q(c)
  if depth == 1 then return lum(c) > 127 and 0xFFFFFF or 0x000000 end
  return c
end

local function status(msg)
  local w, h = gpu.getResolution()
  gpu.setBackground(q(0x333333))
  gpu.setForeground(q(0xFFFFFF))
  gpu.fill(1, h, w, 1, " ")
  gpu.set(1, h, unicode.sub(msg, 1, w))
end

local ENT = {
  lt = "<", gt = ">", amp = "&", quot = '"', apos = "'", nbsp = " ",
  mdash = "—", ndash = "–", hellip = "…", copy = "©", reg = "®", trade = "™",
  laquo = "«", raquo = "»", bull = "•", middot = "·", euro = "€", pound = "£",
  larr = "←", rarr = "→", uarr = "↑", darr = "↓", times = "×", deg = "°",
}

local function decodeEntities(t)
  return (t:gsub("&(#?%w+);", function(e)
    if e:sub(1, 1) == "#" then
      local n
      if e:match("^#[xX]%x+$") then n = tonumber(e:sub(3), 16) else n = tonumber(e:sub(2)) end
      if n == 160 then return " " end
      if n and n > 31 and n < 0x110000 then return unicode.char(n) end
      return nil
    end
    return ENT[e]
  end))
end

local NAMED = {
  black = 0x000000, white = 0xFFFFFF, red = 0xFF0000, green = 0x008000, blue = 0x0000FF,
  yellow = 0xFFFF00, cyan = 0x00FFFF, aqua = 0x00FFFF, magenta = 0xFF00FF, fuchsia = 0xFF00FF,
  gray = 0x808080, grey = 0x808080, silver = 0xC0C0C0, maroon = 0x800000, olive = 0x808000,
  lime = 0x00FF00, navy = 0x000080, teal = 0x008080, purple = 0x800080, orange = 0xFFA500,
  pink = 0xFFC0CB, brown = 0xA52A2A, gold = 0xFFD700, darkgray = 0xA9A9A9, darkgrey = 0xA9A9A9,
  lightgray = 0xD3D3D3, lightgrey = 0xD3D3D3, darkred = 0x8B0000, darkgreen = 0x006400,
  darkblue = 0x00008B, lightblue = 0xADD8E6, lightgreen = 0x90EE90, skyblue = 0x87CEEB,
  coral = 0xFF7F50, crimson = 0xDC143C, indigo = 0x4B0082, violet = 0xEE82EE, beige = 0xF5F5DC,
  ivory = 0xFFFFF0, khaki = 0xF0E68C, tan = 0xD2B48C, salmon = 0xFA8072, turquoise = 0x40E0D0,
  whitesmoke = 0xF5F5F5, dimgray = 0x696969, dimgrey = 0x696969, steelblue = 0x4682B4,
  royalblue = 0x4169E1, orangered = 0xFF4500, tomato = 0xFF6347, chocolate = 0xD2691E,
  firebrick = 0xB22222, forestgreen = 0x228B22, seagreen = 0x2E8B57, slategray = 0x708090,
  midnightblue = 0x191970, hotpink = 0xFF69B4, lavender = 0xE6E6FA, wheat = 0xF5DEB3,
}

local function parseColor(v, bare)
  if not v then return nil end
  v = trim(v:lower())
  if NAMED[v] then return NAMED[v] end
  local hex = v:match("^#(%x+)$") or (bare and v:match("^(%x%x%x%x%x%x)$"))
  if hex then
    if #hex == 3 or #hex == 4 then
      local r, g, b = hex:sub(1, 1), hex:sub(2, 2), hex:sub(3, 3)
      return tonumber(r .. r .. g .. g .. b .. b, 16)
    elseif #hex == 6 or #hex == 8 then
      return tonumber(hex:sub(1, 6), 16)
    end
    return nil
  end
  local inner = v:match("^rgba?%((.-)%)$")
  if inner then
    local c = {}
    for num, pct in inner:gmatch("([%d%.]+)(%%?)") do
      local x = tonumber(num) or 0
      if pct == "%" then x = x * 2.55 end
      c[#c + 1] = max(0, min(255, floor(x + 0.5)))
      if #c == 3 then break end
    end
    if #c == 3 then return c[1] * 65536 + c[2] * 256 + c[3] end
  end
  return nil
end

local function findColor(v)
  v = v:gsub("url%b()", "")
  local f = v:match("rgba?%b()") or v:match("#%x+")
  if f then return parseColor(f) end
  for word in v:gmatch("%a+") do
    local c = NAMED[word]
    if c then return c end
  end
  return nil
end

local function resolveURL(base, rel)
  if not rel then return nil end
  rel = trim(rel)
  if rel == "" then return nil end
  if rel:match("^https?://") then return rel end
  if rel:match("^[%a][%w%+%.%-]*:") or rel:sub(1, 1) == "#" then return nil end
  if not base then return nil end
  local scheme, host, path = base:match("^(https?)://([^/?#]+)(.*)$")
  if not scheme then return nil end
  if rel:sub(1, 2) == "//" then return scheme .. ":" .. rel end
  path = path:gsub("[#?].*$", "")
  if rel:sub(1, 1) == "?" then return scheme .. "://" .. host .. path .. rel end
  rel = rel:gsub("#.*$", "")
  local query = rel:match("(%?.*)$") or ""
  rel = rel:gsub("%?.*$", "")
  local full
  if rel:sub(1, 1) == "/" then
    full = rel
  else
    full = (path:match("^(.*/)") or "/") .. rel
  end
  local out = {}
  for seg in full:gmatch("([^/]+)") do
    if seg == ".." then out[#out] = nil elseif seg ~= "." then out[#out + 1] = seg end
  end
  local res = "/" .. table.concat(out, "/")
  if full:sub(-1) == "/" and #out > 0 then res = res .. "/" end
  return scheme .. "://" .. host .. res .. query
end

local PAGE_HEADERS = {
  ["User-Agent"] = "OpenComputers/3.0 (Compatible; OCWeb/3.0)",
  ["Accept"] = "text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8",
}
local IMG_HEADERS = {
  ["User-Agent"] = "OpenComputers/3.0 (Compatible; OCWeb/3.0)",
  ["Accept"] = "image/png,image/jpeg,image/bmp,image/gif,image/*;q=0.5,*/*;q=0.1",
}

local BROWSER_HEADERS = {
  ["User-Agent"] = "Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:109.0) Gecko/20100101 Firefox/115.0",
  ["Accept"] = "text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8",
  ["Accept-Language"] = "en-US,en;q=0.5",
}

local function header(h, name)
  if not h then return nil end
  for k, v in pairs(h) do
    if tostring(k):lower() == name then
      if type(v) == "table" then return v[1] end
      return v
    end
  end
  return nil
end

local function httpRequest(url, headers, limit)
  os.sleep(0)
  local ok, handle = pcall(internet.request, url, nil, headers)
  if not ok or not handle then
    return nil, "Failed to connect to " .. url .. ": " .. tostring(handle)
  end
  local parts, total, code, rh = {}, 0, nil, nil
  local ok2, err = pcall(function()
    for chunk in handle do
      if not code then
        local c, _, h = handle.response()
        code, rh = c, h
      end
      if chunk then
        parts[#parts + 1] = chunk
        total = total + #chunk
        if limit and total > limit then error("response too large") end
      end
      os.sleep(0)
    end
  end)
  if not ok2 then
    if handle.close then pcall(handle.close) end
    return nil, tostring(err), true
  end
  if not code then
    local ok3, c, _, h = pcall(handle.response)
    if ok3 then code, rh = c, h end
  end
  return table.concat(parts), code, rh
end

local function badRedirectTarget(msg)
  msg = tostring(msg or "")
  local u = msg:match("(https?://[^\r\n]+)")
  if not u then return nil end
  u = trim(u)
  u = u:gsub("#.*$", "")
  u = u:gsub("[%c %z\128-\255]", function(c)
    return string.format("%%%02X", byte(c))
  end)
  return u
end

local function httpFollow(url, headers, limit)
  local seen = {}
  local sawDead = false
  for _ = 1, 8 do
    if seen[url] then return nil, "Redirect loop detected" end
    seen[url] = true
    local data, code, rh = httpRequest(url, headers, limit)
    if not data then
      local dead = rh == true and badRedirectTarget(code) or nil
      if dead then sawDead = true end
      if dead and not seen[dead] then
        url = dead
      elseif dead then
        return nil, "Server redirected to a broken address: " .. tostring(code):gsub("^[^\n:]*:%d+: ", ""), true
      else
        return nil, (tostring(code):gsub("^[^\n:]*:%d+: ", "")), sawDead
      end
    elseif code and code >= 300 and code < 400 then
      local loc = header(rh, "location")
      if loc then
        local nu = resolveURL(url, loc)
        if not nu then return nil, "Invalid redirect URL: " .. loc end
        url = (nu:gsub(" ", "%%20"))
      else
        return data, url
      end
    elseif code and code >= 400 then
      return nil, "HTTP Error: " .. code
    else
      return data, url
    end
  end
  return nil, "Too many redirects"
end

local function clientRedirect(data, url)
  local function usable(u)
    if not u then return nil end
    u = trim(u)
    if u == "" or u:find("[%+]%s") or u:find("%s[%+]") or u:find("[\"'<>]") then return nil end
    local t = resolveURL(url, u)
    if not t then return nil end
    return (t:gsub(" ", "%%20"))
  end
  local target
  for tag in data:gmatch("<[mM][eE][tT][aA][^>]*>") do
    if tag:lower():find("refresh", 1, true) then
      local u = tag:match("[uU][rR][lL]%s*=%s*['\"]?([^'\">]+)")
      target = usable(u) or target
    end
  end
  if not target and #data < 1500 then
    local js = data:match("window%.location[%.%a]*%s*=%s*['\"](.-)['\"]")
    target = usable(js)
  end
  return target
end

local function loadPage(url)
  local data, finalUrl, dead = httpFollow(url, PAGE_HEADERS, MAX_PAGE_BYTES)
  if not data and dead then
    local d2, f2 = httpFollow(url, BROWSER_HEADERS, MAX_PAGE_BYTES)
    if d2 then return d2, f2 end
  end
  return data, finalUrl
end

local function fetchPage(url)
  local data, finalUrl = loadPage(url)
  if not data then return false, finalUrl end
  url = finalUrl
  local seen = {}
  for _ = 1, 6 do
    seen[url] = true
    local target = clientRedirect(data, url)
    if not target or seen[target] then break end
    local nd, nu = loadPage(target)
    if not nd then break end
    data, url = nd, nu
  end
  return true, data, url
end

local LBASE = {3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43,51,59,67,83,99,115,131,163,195,227,258}
local LEXT = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0}
local DBASE = {1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577}
local DEXT = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13}
local CLORDER = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}

local function inflate(data, pos, sink)
  local bitbuf, bitcnt = 0, 0
  local pend, pendn, hist, hlen = {}, 0, "", 0
  local ops = 0
  local fixedLit, fixedDist

  local function bits(need)
    while bitcnt < need do
      local b = byte(data, pos)
      if not b then error("inflate: unexpected end of data") end
      pos = pos + 1
      bitbuf = bitbuf + lshift(b, bitcnt)
      bitcnt = bitcnt + 8
    end
    local v = band(bitbuf, lshift(1, need) - 1)
    bitbuf = rshift(bitbuf, need)
    bitcnt = bitcnt - need
    return v
  end

  local function flush()
    if pendn > 0 then
      local s = char(unpack(pend, 1, pendn))
      sink(s)
      hist = (hist .. s):sub(-32768)
      hlen = #hist
      pendn = 0
    end
  end

  local function put(b)
    pendn = pendn + 1
    pend[pendn] = b
    if pendn >= 2048 then flush() end
  end

  local function back(dist)
    local idx = pendn - dist + 1
    if idx >= 1 then return pend[idx] end
    local h = hlen + idx
    if h < 1 then error("inflate: bad distance") end
    return byte(hist, h)
  end

  local function build(lens, n)
    local count, offs, symbol = {}, {}, {}
    for i = 0, 15 do count[i] = 0 end
    for i = 0, n - 1 do count[lens[i]] = count[lens[i]] + 1 end
    offs[1] = 0
    for i = 1, 14 do offs[i + 1] = offs[i] + count[i] end
    for i = 0, n - 1 do
      local l = lens[i]
      if l ~= 0 then
        symbol[offs[l]] = i
        offs[l] = offs[l] + 1
      end
    end
    return { count = count, symbol = symbol }
  end

  local function decode(h)
    local code, first, index = 0, 0, 0
    for len = 1, 15 do
      code = code + bits(1)
      local cnt = h.count[len]
      if code - cnt < first then return h.symbol[index + (code - first)] end
      index = index + cnt
      first = (first + cnt) * 2
      code = code * 2
    end
    error("inflate: bad huffman code")
  end

  local function codes(lit, dst)
    while true do
      local sym = decode(lit)
      if sym == nil then error("inflate: bad symbol") end
      if sym < 256 then
        put(sym)
      elseif sym == 256 then
        return
      else
        sym = sym - 256
        if sym > 29 then error("inflate: bad length symbol") end
        local len = LBASE[sym]
        if LEXT[sym] > 0 then len = len + bits(LEXT[sym]) end
        local ds = decode(dst)
        if ds == nil or ds > 29 then error("inflate: bad distance symbol") end
        ds = ds + 1
        local dist = DBASE[ds]
        if DEXT[ds] > 0 then dist = dist + bits(DEXT[ds]) end
        for _ = 1, len do put(back(dist)) end
      end
      ops = ops + 1
      if ops % 3000 == 0 then os.sleep(0) end
    end
  end

  local final
  repeat
    final = bits(1)
    local typ = bits(2)
    if typ == 0 then
      bitbuf, bitcnt = 0, 0
      local len = byte(data, pos) + byte(data, pos + 1) * 256
      pos = pos + 4
      for i = 0, len - 1 do put(byte(data, pos + i)) end
      pos = pos + len
    elseif typ == 1 then
      if not fixedLit then
        local l = {}
        for i = 0, 143 do l[i] = 8 end
        for i = 144, 255 do l[i] = 9 end
        for i = 256, 279 do l[i] = 7 end
        for i = 280, 287 do l[i] = 8 end
        fixedLit = build(l, 288)
        local d = {}
        for i = 0, 29 do d[i] = 5 end
        fixedDist = build(d, 30)
      end
      codes(fixedLit, fixedDist)
    elseif typ == 2 then
      local nlen = bits(5) + 257
      local ndist = bits(5) + 1
      local ncode = bits(4) + 4
      local lens = {}
      for i = 0, 18 do lens[i] = 0 end
      for i = 1, ncode do lens[CLORDER[i]] = bits(3) end
      local lencode = build(lens, 19)
      local all, idx = {}, 0
      while idx < nlen + ndist do
        local sym = decode(lencode)
        if sym < 16 then
          all[idx] = sym
          idx = idx + 1
        else
          local prev, rep = 0, 0
          if sym == 16 then
            prev = all[idx - 1] or 0
            rep = 3 + bits(2)
          elseif sym == 17 then
            rep = 3 + bits(3)
          else
            rep = 11 + bits(7)
          end
          for _ = 1, rep do
            all[idx] = prev
            idx = idx + 1
          end
        end
      end
      local ll, dl = {}, {}
      for i = 0, nlen - 1 do ll[i] = all[i] end
      for i = 0, ndist - 1 do dl[i] = all[nlen + i] end
      codes(build(ll, nlen), build(dl, ndist))
    else
      error("inflate: bad block type")
    end
  until final == 1
  flush()
end

local function be32(s, p)
  local a, b, c, d = byte(s, p, p + 3)
  return ((a * 256 + b) * 256 + c) * 256 + d
end
local function le16(s, p)
  local a, b = byte(s, p, p + 1)
  return a + b * 256
end
local function le32(s, p)
  local a, b, c, d = byte(s, p, p + 3)
  return a + b * 256 + c * 65536 + d * 16777216
end

local function newGrid(W, H, cols, pixPerCell)
  pixPerCell = pixPerCell or 4
  cols = max(1, min(cols, floor(W / 2)))
  local pw = cols * 2
  local ph = max(4, ceil(pw * H / W / pixPerCell) * pixPerCell)
  if ph > MAX_IMAGE_ROWS * pixPerCell then
    ph = MAX_IMAGE_ROWS * pixPerCell
    pw = max(2, 2 * floor(ph * W / H / 2 + 0.5))
  end

  local g = { W = W, H = H, pw = pw, ph = ph, acc = {}, xmap = {}, xcnt = {}, ycnt = {} }
  local xmap, xcnt, ycnt = g.xmap, g.xcnt, g.ycnt
  for i = 1, pw do xcnt[i] = 0 end
  for i = 1, ph do ycnt[i] = 0 end
  for x = 1, W do
    local c = floor((x - 1) * pw / W) + 1
    xmap[x] = c
    xcnt[c] = xcnt[c] + 1
  end
  local xmax = 0
  for i = 1, pw do if xcnt[i] > xmax then xmax = xcnt[i] end end
  local bound = xmax * ceil(H / ph)
  local sh = 0
  while bound * ((255 + ((1 << sh) >> 1)) >> sh) >= 2097152 do sh = sh + 1 end
  g.sh = sh
  g.hf = (1 << sh) >> 1
  local acc = g.acc
  for i = 1, pw * ph do acc[i] = 0 end
  return g
end

local function gridRow(g, y, rr, gg, bb)
  local ry = floor(y * g.ph / g.H)
  local ycnt = g.ycnt
  ycnt[ry + 1] = ycnt[ry + 1] + 1
  local base = ry * g.pw
  local acc, xm, sh, hf = g.acc, g.xmap, g.sh, g.hf
  for x = 1, g.W do
    local k = base + xm[x]
    local r = (floor(rr[x] + 0.5) + hf) >> sh
    local gv = (floor(gg[x] + 0.5) + hf) >> sh
    local b = (floor(bb[x] + 0.5) + hf) >> sh
    acc[k] = acc[k] + (r * 4398046511104 + gv * 2097152 + b)
  end
end

local function finishGrid(g)
  local pw, ph = g.pw, g.ph
  local acc, xcnt, ycnt = g.acc, g.xcnt, g.ycnt
  local scale = 1 << g.sh
  g.acc, g.xmap = nil, nil
  local M = 2097151

  local minr, ming, minb, maxr, maxg, maxb = 255, 255, 255, 0, 0, 0
  local i = 0
  for y = 1, ph do
    local cy = ycnt[y]
    for x = 1, pw do
      i = i + 1
      local c = cy * xcnt[x]
      local r, gv, b = 255, 255, 255
      if c > 0 then
        local a = acc[i]
        r = (a >> 42) * scale / c
        gv = ((a >> 21) & M) * scale / c
        b = (a & M) * scale / c
      end
      if r < minr then minr = r end
      if gv < ming then ming = gv end
      if b < minb then minb = b end
      if r > maxr then maxr = r end
      if gv > maxg then maxg = gv end
      if b > maxb then maxb = b end
    end
  end
  local dr, dg, db = maxr - minr, maxg - ming, maxb - minb

  local parts, pn = {}, 0
  local chunk, cn = {}, 0
  i = 0
  for y = 1, ph do
    local cy = ycnt[y]
    for x = 1, pw do
      i = i + 1
      local c = cy * xcnt[x]
      local r, gv, b = 255, 255, 255
      if c > 0 then
        local a = acc[i]
        r = (a >> 42) * scale / c
        gv = ((a >> 21) & M) * scale / c
        b = (a & M) * scale / c
      end
      if dr > 8 then r = (r - minr) * 255 / dr end
      if dg > 8 then gv = (gv - ming) * 255 / dg end
      if db > 8 then b = (b - minb) * 255 / db end
      r = floor(r + 0.5); if r < 0 then r = 0 elseif r > 255 then r = 255 end
      gv = floor(gv + 0.5); if gv < 0 then gv = 0 elseif gv > 255 then gv = 255 end
      b = floor(b + 0.5); if b < 0 then b = 0 elseif b > 255 then b = 255 end
      cn = cn + 1
      chunk[cn] = char(r, gv, b)
      if cn >= 1000 then
        pn = pn + 1
        parts[pn] = table.concat(chunk, "", 1, cn)
        cn = 0
      end
    end
    if y % 32 == 0 then os.sleep(0) end
  end
  if cn > 0 then pn = pn + 1; parts[pn] = table.concat(chunk, "", 1, cn) end
  return { pw = pw, ph = ph, rgb = table.concat(parts) }
end

local function decodePNG(box, cols, pixPerCell)
  local data = box[1]; box[1] = nil
  if data:sub(1, 8) ~= "\137PNG\r\n\26\n" then return nil, "bad PNG" end
  local pos = 9
  local W, H, bd, ct, il
  local pal = {}
  local idat = {}
  while pos <= #data - 7 do
    local len = be32(data, pos)
    local typ = data:sub(pos + 4, pos + 7)
    local body = pos + 8
    if typ == "IHDR" then
      W, H = be32(data, body), be32(data, body + 4)
      bd, ct, il = byte(data, body + 8), byte(data, body + 9), byte(data, body + 12)
    elseif typ == "PLTE" then
      for i = 0, floor(len / 3) - 1 do
        local r, g, b = byte(data, body + i * 3, body + i * 3 + 2)
        pal[i] = { r, g, b }
      end
    elseif typ == "IDAT" then
      idat[#idat + 1] = data:sub(body, body + len - 1)
    elseif typ == "IEND" then
      break
    end
    pos = body + len + 4
  end
  data = nil
  if not W or W < 1 or H < 1 then return nil, "bad PNG" end
  if il ~= 0 then return nil, "interlaced PNG" end
  if W * H > MAX_IMAGE_PIXELS then return nil, "image too large" end
  local spp = ({ [0] = 1, [2] = 3, [3] = 1, [4] = 2, [6] = 4 })[ct]
  if not spp then return nil, "bad PNG color type" end

  local bppBits = spp * bd
  local rowbytes = ceil(W * bppBits / 8)
  local fbpp = max(1, ceil(bppBits / 8))
  local g = newGrid(W, H, cols, pixPerCell)
  local prev = {}
  for i = 1, rowbytes do prev[i] = 0 end
  local rr, gg, bb = {}, {}, {}
  local scale = bd < 8 and 255 / (2 ^ bd - 1) or 1

  local function sample(cur, s)
    if bd == 8 then return cur[s + 1] end
    if bd == 16 then return cur[2 * s + 1] end
    local per = 8 / bd
    local b = cur[floor(s / per) + 1]
    local sh = 8 - bd * (s % per + 1)
    return floor(b / 2 ^ sh) % (2 ^ bd)
  end

  local function rowRGB(cur)
    if bd == 8 then
      if ct == 2 then
        for x = 1, W do
          local i = x * 3 - 2
          rr[x], gg[x], bb[x] = cur[i], cur[i + 1], cur[i + 2]
        end
      elseif ct == 6 then
        for x = 1, W do
          local i = x * 4 - 3
          local a = cur[i + 3] / 255
          rr[x] = cur[i] * a + 255 * (1 - a)
          gg[x] = cur[i + 1] * a + 255 * (1 - a)
          bb[x] = cur[i + 2] * a + 255 * (1 - a)
        end
      elseif ct == 0 then
        for x = 1, W do
          local v = cur[x]
          rr[x], gg[x], bb[x] = v, v, v
        end
      elseif ct == 4 then
        for x = 1, W do
          local a = cur[2 * x] / 255
          local v = cur[2 * x - 1] * a + 255 * (1 - a)
          rr[x], gg[x], bb[x] = v, v, v
        end
      else
        for x = 1, W do
          local p = pal[cur[x]]
          if p then rr[x], gg[x], bb[x] = p[1], p[2], p[3] end
        end
      end
      return
    end
    for x = 0, W - 1 do
      local r, gc, b
      if ct == 0 then
        local v = sample(cur, x) * scale
        r, gc, b = v, v, v
      elseif ct == 3 then
        local p = pal[sample(cur, x)]
        if p then r, gc, b = p[1], p[2], p[3] else r, gc, b = 0, 0, 0 end
      elseif ct == 2 then
        r = sample(cur, 3 * x) * scale
        gc = sample(cur, 3 * x + 1) * scale
        b = sample(cur, 3 * x + 2) * scale
      elseif ct == 4 then
        local a = sample(cur, 2 * x + 1) / 255
        local v = sample(cur, 2 * x) * scale * a + 255 * (1 - a)
        r, gc, b = v, v, v
      else
        local a = sample(cur, 4 * x + 3) / 255
        r = sample(cur, 4 * x) * scale * a + 255 * (1 - a)
        gc = sample(cur, 4 * x + 1) * scale * a + 255 * (1 - a)
        b = sample(cur, 4 * x + 2) * scale * a + 255 * (1 - a)
      end
      rr[x + 1], gg[x + 1], bb[x + 1] = r, gc, b
    end
  end

  local y, ops, buf = 0, 0, ""

  local function processRow(rs)
    local ft = byte(rs, 1)
    local cur = {}
    for i = 2, rowbytes + 1, 200 do
      local t = { byte(rs, i, min(i + 199, rowbytes + 1)) }
      for j = 1, #t do cur[i + j - 2] = t[j] end
    end
    if ft == 1 then
      for i = fbpp + 1, rowbytes do cur[i] = (cur[i] + cur[i - fbpp]) % 256 end
    elseif ft == 2 then
      for i = 1, rowbytes do cur[i] = (cur[i] + prev[i]) % 256 end
    elseif ft == 3 then
      for i = 1, rowbytes do
        local a = i > fbpp and cur[i - fbpp] or 0
        cur[i] = (cur[i] + floor((a + prev[i]) / 2)) % 256
      end
    elseif ft == 4 then
      for i = 1, rowbytes do
        local a = i > fbpp and cur[i - fbpp] or 0
        local b = prev[i]
        local c = i > fbpp and prev[i - fbpp] or 0
        local p = a + b - c
        local pa, pb, pc = abs(p - a), abs(p - b), abs(p - c)
        local pr
        if pa <= pb and pa <= pc then pr = a elseif pb <= pc then pr = b else pr = c end
        cur[i] = (cur[i] + pr) % 256
      end
    end
    rowRGB(cur)
    gridRow(g, y, rr, gg, bb)
    prev = cur
    y = y + 1
    ops = ops + W
    if ops > 20000 then ops = 0; os.sleep(0) end
  end

  local function sink(chunk)
    buf = buf .. chunk
    while y < H and #buf >= rowbytes + 1 do
      processRow(buf:sub(1, rowbytes + 1))
      buf = buf:sub(rowbytes + 2)
    end
  end

  local z = table.concat(idat)
  idat = nil
  inflate(z, 3, sink)
  return finishGrid(g)
end

local function decodeBMP(box, cols, pixPerCell)
  local data = box[1]; box[1] = nil
  if #data < 54 then return nil, "bad BMP" end
  local off, hsz = le32(data, 11), le32(data, 15)
  local W, H = le32(data, 19), le32(data, 23)
  local bpp, comp = le16(data, 29), le32(data, 31)
  if H >= 2 ^ 31 then H = H - 2 ^ 32 end
  local top = H < 0
  H = abs(H)
  if comp ~= 0 then return nil, "compressed BMP" end
  if not (bpp == 1 or bpp == 4 or bpp == 8 or bpp == 24 or bpp == 32) then return nil, "BMP depth " .. bpp end
  if W < 1 or H < 1 then return nil, "bad BMP" end
  if W * H > MAX_IMAGE_PIXELS then return nil, "image too large" end
  local pal = {}
  if bpp <= 8 then
    local n = le32(data, 47)
    if n == 0 then n = 2 ^ bpp end
    for i = 0, n - 1 do
      local b, g, r = byte(data, 15 + hsz + i * 4, 15 + hsz + i * 4 + 2)
      pal[i] = { r, g, b }
    end
  end
  local rowsize = floor((bpp * W + 31) / 32) * 4
  local g = newGrid(W, H, cols, pixPerCell)
  local rr, gg, bb = {}, {}, {}
  local ops = 0
  for y = 0, H - 1 do
    local sy = top and y or (H - 1 - y)
    local rp = off + sy * rowsize + 1
    if bpp == 24 or bpp == 32 then
      local step = bpp / 8
      for x = 0, W - 1 do
        local b, gg2, r = byte(data, rp + x * step, rp + x * step + 2)
        rr[x + 1], gg[x + 1], bb[x + 1] = r, gg2, b
      end
    elseif bpp == 8 then
      for x = 0, W - 1 do
        local p = pal[byte(data, rp + x)]
        if p then rr[x + 1], gg[x + 1], bb[x + 1] = p[1], p[2], p[3] end
      end
    else
      local per = 8 / bpp
      for x = 0, W - 1 do
        local bt = byte(data, rp + floor(x / per))
        local sh = 8 - bpp * (x % per + 1)
        local p = pal[floor(bt / 2 ^ sh) % (2 ^ bpp)]
        if p then rr[x + 1], gg[x + 1], bb[x + 1] = p[1], p[2], p[3] end
      end
    end
    gridRow(g, y, rr, gg, bb)
    ops = ops + W
    if ops > 20000 then ops = 0; os.sleep(0) end
  end
  return finishGrid(g)
end

local ZZ = {[0]=0,1,8,16,9,2,3,10,17,24,32,25,18,11,4,5,12,19,26,33,40,48,41,34,27,20,13,6,7,14,21,28,
  35,42,49,56,57,50,43,36,29,22,15,23,30,37,44,51,58,59,52,45,38,31,39,46,53,60,61,54,47,55,62,63}
local IDCT = {}
for x = 0, 7 do
  IDCT[x] = {}
  for u = 0, 7 do
    IDCT[x][u] = (u == 0 and math.sqrt(0.5) or 1) * 0.5 * math.cos((2 * x + 1) * u * math.pi / 16)
  end
end

local function idct(coef)
  local tmp, out = {}, {}
  for v = 0, 7 do
    for x = 0, 7 do
      local sum = 0
      for u = 0, 7 do
        local c = coef[v * 8 + u]
        if c ~= 0 then sum = sum + IDCT[x][u] * c end
      end
      tmp[v * 8 + x] = sum
    end
  end
  for x = 0, 7 do
    for y = 0, 7 do
      local sum = 0
      for v = 0, 7 do sum = sum + IDCT[y][v] * tmp[v * 8 + x] end
      out[y * 8 + x] = sum + 128
    end
  end
  return out
end

local function decodeJPEG(box, cols, pixPerCell)
  local data = box[1]; box[1] = nil
  if data:sub(1, 2) ~= "\255\216" then return nil, "bad JPEG" end
  local pos = 3
  local qt, hdc, hac = {}, {}, {}
  local W, H, comps, ri = nil, nil, {}, 0
  local scanStart, sosComps
  while pos < #data do
    if byte(data, pos) ~= 255 then
      pos = pos + 1
    else
      local m = byte(data, pos + 1)
      if m == 255 or m == 0 then
        pos = pos + 1
      elseif m == 0xD8 or m == 1 or (m >= 0xD0 and m <= 0xD7) then
        pos = pos + 2
      elseif m == 0xD9 then
        break
      else
        local len = byte(data, pos + 2) * 256 + byte(data, pos + 3)
        local s, e = pos + 4, pos + 1 + len
        if m == 0xDB then
          local p = s
          while p < e do
            local pq = byte(data, p)
            local prec, id = floor(pq / 16), pq % 16
            p = p + 1
            local t = {}
            for k = 0, 63 do
              if prec == 0 then t[k] = byte(data, p + k)
              else t[k] = byte(data, p + k) * 256 + byte(data, p + k + 1) end
            end
            p = p + (prec == 0 and 64 or 128)
            qt[id] = t
          end
        elseif m == 0xC4 then
          local p = s
          while p < e do
            local tc = byte(data, p)
            local cls, id = floor(tc / 16), tc % 16
            p = p + 1
            local counts, total = {}, 0
            for i = 1, 16 do counts[i] = byte(data, p + i - 1); total = total + counts[i] end
            p = p + 16
            local sym = {}
            for i = 0, total - 1 do sym[i] = byte(data, p + i) end
            p = p + total
            local h = { count = counts, symbol = sym }
            if cls == 0 then hdc[id] = h else hac[id] = h end
          end
        elseif m == 0xC0 or m == 0xC1 then
          if byte(data, s) ~= 8 then return nil, "JPEG precision" end
          H = byte(data, s + 1) * 256 + byte(data, s + 2)
          W = byte(data, s + 3) * 256 + byte(data, s + 4)
          for i = 0, byte(data, s + 5) - 1 do
            local id, hv, tq = byte(data, s + 6 + i * 3, s + 8 + i * 3)
            comps[#comps + 1] = { id = id, h = floor(hv / 16), v = hv % 16, tq = tq, pred = 0 }
          end
        elseif m == 0xC2 or (m >= 0xC3 and m <= 0xCF and m ~= 0xC4 and m ~= 0xC8 and m ~= 0xCC) then
          return nil, "progressive JPEG"
        elseif m == 0xDD then
          ri = byte(data, s) * 256 + byte(data, s + 1)
        elseif m == 0xDA then
          sosComps = {}
          for i = 0, byte(data, s) - 1 do
            local cid, tt = byte(data, s + 1 + i * 2, s + 2 + i * 2)
            sosComps[#sosComps + 1] = { id = cid, dc = floor(tt / 16), ac = tt % 16 }
          end
          scanStart = e + 1
          break
        end
        pos = e + 1
      end
    end
  end
  local nc = #comps
  if not (W and scanStart and (nc == 1 or nc == 3)) or #sosComps ~= nc then return nil, "unsupported JPEG" end
  if W * H > 4000000 then return nil, "image too large" end
  local Hmax, Vmax = 1, 1
  for _, c in ipairs(comps) do Hmax = max(Hmax, c.h); Vmax = max(Vmax, c.v) end
  if nc == 1 then comps[1].h, comps[1].v, Hmax, Vmax = 1, 1, 1, 1 end
  local mx, my = ceil(W / (8 * Hmax)), ceil(H / (8 * Vmax))
  local yc = comps[1]
  local blocksY_X = mx * yc.h
  local blocksY_Y = my * yc.v
  local full = (W * H <= 40000)

  local plane = {}
  for ci = 1, nc do
    local c = comps[ci]
    local bx = mx * c.h
    local by = my * c.v
    local rows = full and (by * 8) or by
    local p = {}
    for r = 1, rows do p[r] = {} end
    c.plane = p
  end

  local segs = {}
  do
    local p, cur = scanStart, {}
    while true do
      local f = data:find("\255", p, true)
      if not f then cur[#cur + 1] = data:sub(p); break end
      cur[#cur + 1] = data:sub(p, f - 1)
      local c = byte(data, f + 1)
      if c == 0 then
        cur[#cur + 1] = "\255"; p = f + 2
      elseif c and c >= 0xD0 and c <= 0xD7 then
        segs[#segs + 1] = table.concat(cur); cur = {}; p = f + 2
      else
        break
      end
    end
    segs[#segs + 1] = table.concat(cur)
  end
  data = nil

  local sd, sp, bitcnt, curb = "", 1, 0, 0
  local function getbit()
    if bitcnt == 0 then curb = byte(sd, sp) or 0; sp = sp + 1; bitcnt = 8 end
    bitcnt = bitcnt - 1
    return band(rshift(curb, bitcnt), 1)
  end
  local function receive(n)
    local v = 0
    for _ = 1, n do v = v * 2 + getbit() end
    return v
  end
  local function extend(v, n)
    if v < lshift(1, n - 1) then return v - lshift(1, n) + 1 end
    return v
  end
  local function decodeSym(h)
    local code, first, index = 0, 0, 0
    for len = 1, 16 do
      code = code + getbit()
      local cnt = h.count[len]
      if code - cnt < first then return h.symbol[index + (code - first)] end
      index = index + cnt
      first = (first + cnt) * 2
      code = code * 2
    end
    error("bad JPEG huffman code")
  end

  local total = mx * my
  local per = ri > 0 and ri or total
  local mcu = 0
  for si = 1, #segs do
    sd, sp, bitcnt = segs[si], 1, 0
    for _, c in ipairs(comps) do c.pred = 0 end
    for _ = 1, per do
      if mcu >= total then break end
      local mxi, myi = mcu % mx, floor(mcu / mx)
      for ci, c in ipairs(comps) do
        local dcT, acT = hdc[sosComps[ci].dc], hac[sosComps[ci].ac]
        local q = qt[c.tq]
        for by = 0, c.v - 1 do
          for bx = 0, c.h - 1 do
            local t = decodeSym(dcT)
            if t > 0 then c.pred = c.pred + extend(receive(t), t) end
            local coef
            if full then
              coef = {}
              for i = 0, 63 do coef[i] = 0 end
              coef[0] = c.pred * q[0]
            end
            local k = 1
            while k < 64 do
              local rs = decodeSym(acT)
              local r, sz = floor(rs / 16), rs % 16
              if sz == 0 then
                if r == 15 then k = k + 16 else break end
              else
                k = k + r
                local v = extend(receive(sz), sz)
                if coef and k < 64 then coef[ZZ[k]] = v * q[k] end
                k = k + 1
              end
            end
            local gx, gy = mxi * c.h + bx, myi * c.v + by
            if full then
              local o = idct(coef)
              for yy = 0, 7 do
                local row = c.plane[gy * 8 + yy + 1]
                for xx = 0, 7 do row[gx * 8 + xx + 1] = o[yy * 8 + xx] end
              end
            else
              c.plane[gy + 1][gx + 1] = c.pred * q[0] / 8 + 128
            end
          end
        end
      end
      mcu = mcu + 1
      if mcu % 64 == 0 then os.sleep(0) end
    end
  end

  local Ws, Hs = W, H
  local fullW, fullH
  if full then
    fullW = mx * yc.h * 8
    fullH = my * yc.v * 8
  else
    Ws, Hs = ceil(W / 8), ceil(H / 8)
    fullW = mx * yc.h
    fullH = my * yc.v
  end

  local g = newGrid(Ws, Hs, cols, pixPerCell)
  local rr, gg, bb = {}, {}, {}

  local function samplePlane(c, x, y, planeW, planeH)
    local sx = floor(x * c.h * (full and 8 or 1) / (yc.h * (full and 8 or 1)))
    local sy = floor(y * c.v * (full and 8 or 1) / (yc.v * (full and 8 or 1)))
    if sx < 0 then sx = 0 elseif sx >= planeW then sx = planeW - 1 end
    if sy < 0 then sy = 0 elseif sy >= planeH then sy = planeH - 1 end
    local row = c.plane[sy + 1]
    if not row then return 128 end
    local v = row[sx + 1]
    if v == nil then return 128 end
    return v
  end

  local yPlaneW = full and (mx * yc.h * 8) or (mx * yc.h)
  local yPlaneH = full and (my * yc.v * 8) or (my * yc.v)
  local cbPlaneW, cbPlaneH, crPlaneW, crPlaneH
  if nc == 3 then
    local cb = comps[2]
    local cr = comps[3]
    cbPlaneW = full and (mx * cb.h * 8) or (mx * cb.h)
    cbPlaneH = full and (my * cb.v * 8) or (my * cb.v)
    crPlaneW = full and (mx * cr.h * 8) or (mx * cr.h)
    crPlaneH = full and (my * cr.v * 8) or (my * cr.v)
  end

  for y = 0, Hs - 1 do
    for x = 0, Ws - 1 do
      local Y, Cb, Cr
      if full then
        local yrow = yc.plane[y + 1]
        Y = yrow and yrow[x + 1] or 128
      else
        local yrow = yc.plane[y + 1]
        Y = yrow and yrow[x + 1] or 128
      end
      if nc == 3 then
        Cb = samplePlane(comps[2], x, y, cbPlaneW, cbPlaneH)
        Cr = samplePlane(comps[3], x, y, crPlaneW, crPlaneH)
      else
        Cb, Cr = 128, 128
      end
      local r = Y + 1.402 * (Cr - 128)
      local gc = Y - 0.344136 * (Cb - 128) - 0.714136 * (Cr - 128)
      local b = Y + 1.772 * (Cb - 128)
      if r < 0 then r = 0 elseif r > 255 then r = 255 end
      if gc < 0 then gc = 0 elseif gc > 255 then gc = 255 end
      if b < 0 then b = 0 elseif b > 255 then b = 255 end
      rr[x + 1], gg[x + 1], bb[x + 1] = r, gc, b
    end
    gridRow(g, y, rr, gg, bb)
    if y % 32 == 31 then os.sleep(0) end
  end

  for ci = 1, nc do comps[ci].plane = nil end
  return finishGrid(g)
end

local function gifReadPalette(data, pos, count)
  local pal = {}
  for i = 0, count - 1 do
    local r, g, b = byte(data, pos, pos + 2)
    if not r or not g or not b then
      return nil, pos, "truncated GIF color table"
    end
    pal[i] = { r, g, b }
    pos = pos + 3
  end
  return pal, pos
end

local function gifSkipSubBlocks(data, pos)
  while true do
    local n = byte(data, pos)
    if not n then return nil, "truncated GIF sub-blocks" end
    pos = pos + 1
    if n == 0 then return pos end
    if pos + n - 1 > #data then
      return nil, "truncated GIF sub-block"
    end
    pos = pos + n
  end
end

local function gifReadSubBlocks(data, pos)
  local chunks = {}
  while true do
    local n = byte(data, pos)
    if not n then return nil, "truncated GIF sub-blocks" end
    pos = pos + 1
    if n == 0 then break end
    if pos + n - 1 > #data then
      return nil, "truncated GIF sub-block"
    end
    chunks[#chunks + 1] = data:sub(pos, pos + n - 1)
    pos = pos + n
  end
  return table.concat(chunks), pos
end

local function gifLZW(data, minCodeSize, expected)
  if minCodeSize < 2 or minCodeSize > 11 then
    return nil, "unsupported GIF LZW code size"
  end

  local clear = 1 << minCodeSize
  local eoi = clear + 1
  local nextCode = clear + 2
  local codeSize = minCodeSize + 1

  local prefix, suffix = {}, {}
  for i = 0, clear - 1 do
    prefix[i] = -1
    suffix[i] = i
  end

  local chunks, buf, bn, outn = {}, {}, 0, 0
  local stack = {}
  local bitPos = 0
  local totalBits = #data * 8

  local function readCode()
    if bitPos + codeSize > totalBits then return nil end
    local value = 0
    for i = 0, codeSize - 1 do
      local p = bitPos + i
      local b = byte(data, floor(p / 8) + 1)
      local bit = band(rshift(b, p % 8), 1)
      value = value + lshift(bit, i)
    end
    bitPos = bitPos + codeSize
    return value
  end

  local function put(c)
    bn = bn + 1
    buf[bn] = c
    outn = outn + 1
    if bn >= 2048 then
      chunks[#chunks + 1] = char(unpack(buf, 1, bn))
      bn = 0
    end
  end

  local function emitString(code)
    local n = 0
    while code >= clear do
      local p = prefix[code]
      if p == nil then return nil end
      n = n + 1
      stack[n] = suffix[code]
      code = p
    end
    n = n + 1
    stack[n] = code
    if outn + n > expected then return nil end
    for i = n, 1, -1 do put(stack[i]) end
    return code
  end

  local prev = nil

  while outn < expected do
    local code = readCode()
    if code == nil then break end

    if code == clear then
      nextCode = clear + 2
      codeSize = minCodeSize + 1
      prev = nil

    elseif code == eoi then
      break

    else
      if code > nextCode then
        return nil, "bad GIF LZW code"
      end

      if code == nextCode then
        if prev == nil then
          return nil, "bad GIF LZW first code"
        end
        local first = emitString(prev)
        if not first then
          return nil, "GIF image data too large"
        end
        if outn + 1 > expected then
          return nil, "GIF image data too large"
        end
        put(first)

        if nextCode < 4096 then
          prefix[nextCode] = prev
          suffix[nextCode] = first
          nextCode = nextCode + 1
          if nextCode == (1 << codeSize) and codeSize < 12 then
            codeSize = codeSize + 1
          end
        end

      else
        local first = emitString(code)
        if not first then
          return nil, "GIF image data too large"
        end

        if prev ~= nil and nextCode < 4096 then
          prefix[nextCode] = prev
          suffix[nextCode] = first
          nextCode = nextCode + 1
          if nextCode == (1 << codeSize) and codeSize < 12 then
            codeSize = codeSize + 1
          end
        end
      end

      prev = code
    end

    if outn % 20000 == 0 then
      os.sleep(0)
    end
  end

  if bn > 0 then chunks[#chunks + 1] = char(unpack(buf, 1, bn)) end
  if outn < expected then
    return nil, "truncated GIF image data"
  end
  return table.concat(chunks)
end

local function decodeGIF(box, cols, pixPerCell)
  local data = box[1]; box[1] = nil
  local sig = data:sub(1, 6)
  if sig ~= "GIF87a" and sig ~= "GIF89a" then
    return nil, "bad GIF"
  end
  if #data < 13 then
    return nil, "truncated GIF"
  end

  local W = le16(data, 7)
  local H = le16(data, 9)
  if W < 1 or H < 1 then return nil, "bad GIF dimensions" end
  if W * H > MAX_IMAGE_PIXELS then return nil, "image too large" end

  local packed = byte(data, 11)
  local hasGlobalPalette = band(packed, 0x80) ~= 0
  local globalPaletteSize = 2 ^ (band(packed, 0x07) + 1)

  local pos = 14
  local globalPalette
  if hasGlobalPalette then
    globalPalette, pos = gifReadPalette(data, pos, globalPaletteSize)
    if not globalPalette then return nil, "bad GIF global palette" end
  end

  local transparentIndex = nil

  while pos <= #data do
    local block = byte(data, pos)
    pos = pos + 1

    if block == 0x3B then
      return nil, "GIF contains no image frame"
    end

    if block == 0x21 then
      local label = byte(data, pos)
      pos = pos + 1

      if label == 0xF9 then
        local size = byte(data, pos)
        pos = pos + 1
        if size ~= 4 or pos + 4 > #data then
          return nil, "bad GIF graphic control extension"
        end
        local gcePacked = byte(data, pos)
        transparentIndex = nil
        if band(gcePacked, 1) ~= 0 then
          transparentIndex = byte(data, pos + 3)
        end
        pos = pos + 4
        if byte(data, pos) ~= 0 then
          return nil, "bad GIF graphic control terminator"
        end
        pos = pos + 1
      else
        local newPos, err = gifSkipSubBlocks(data, pos)
        if not newPos then return nil, err end
        pos = newPos
      end

    elseif block == 0x2C then
      if pos + 9 > #data then
        return nil, "truncated GIF image descriptor"
      end
      local fw = le16(data, pos + 4)
      local fh = le16(data, pos + 6)
      local ipacked = byte(data, pos + 8)
      pos = pos + 9

      if fw < 1 or fh < 1 then return nil, "bad GIF frame dimensions" end
      if fw * fh > MAX_IMAGE_PIXELS then return nil, "GIF frame too large" end

      local hasLocalPalette = band(ipacked, 0x80) ~= 0
      local interlaced = band(ipacked, 0x40) ~= 0
      local localPaletteSize = 2 ^ (band(ipacked, 0x07) + 1)

      local palette = globalPalette
      if hasLocalPalette then
        palette, pos = gifReadPalette(data, pos, localPaletteSize)
        if not palette then return nil, "bad GIF local palette" end
      end
      if not palette then return nil, "GIF has no color palette" end

      local minCodeSize = byte(data, pos)
      pos = pos + 1

      local compressed, newPos = gifReadSubBlocks(data, pos)
      if not compressed then return nil, newPos end
      data = nil

      local expected = fw * fh
      local pixels, err = gifLZW(compressed, minCodeSize, expected)
      compressed = nil
      if not pixels then return nil, err end

      local g = newGrid(fw, fh, cols, pixPerCell)
      local rr, gg, bb = {}, {}, {}

      local function renderRow(srcY, pixelOffset)
        for x = 1, fw do
          local idx = byte(pixels, pixelOffset + x - 1)
          if idx == transparentIndex then
            rr[x], gg[x], bb[x] = 255, 255, 255
          else
            local p = palette[idx]
            if p then rr[x], gg[x], bb[x] = p[1], p[2], p[3] end
          end
        end
        gridRow(g, srcY, rr, gg, bb)
      end

      if interlaced then
        local passes = {
          { start = 0, step = 8 },
          { start = 4, step = 8 },
          { start = 2, step = 4 },
          { start = 1, step = 2 },
        }
        local sourceRow = 0
        for _, pass in ipairs(passes) do
          for y = pass.start, fh - 1, pass.step do
            renderRow(y, sourceRow * fw + 1)
            sourceRow = sourceRow + 1            if sourceRow % 32 == 0 then os.sleep(0) end
          end
        end
      else
        for y = 0, fh - 1 do
          renderRow(y, y * fw + 1)
          if y % 32 == 31 then os.sleep(0) end
        end
      end

      return finishGrid(g)
    end
  end

  return nil, "GIF contains no image frame"
end

local CACHE_DIRS = { "/home/.ocweb-cache", "/var/ocweb-cache", "/usr/.ocweb-cache" }
local MAX_CACHE_BYTES = 32 * 1024 * 1024
local MAX_MEM_CACHE_BYTES = 128 * 1024
local CACHE_FREE_MARGIN = 128 * 1024
local IO_CHUNK = 2048

local imgstore = {}
do
  local dir, proxy, dirTried = nil, nil, false
  local curFile, seq = nil, 0
  local cache, cacheMem = {}, 0
  local saved = nil
  local tmpAddr
  pcall(function() tmpAddr = computer.tmpAddress() end)

  local function tryDir(path)
    local ok, p = pcall(function()
      if not filesystem.exists(path) then
        filesystem.makeDirectory(path)
      end
      if not filesystem.isDirectory(path) then return nil end
      local fsp = filesystem.get(path)
      if not fsp or fsp.isReadOnly() then return nil end
      if tmpAddr and fsp.address == tmpAddr then return nil end
      return fsp
    end)
    if ok then return p end
  end

  local function ensureDir()
    if dir then return true end
    if dirTried then return false end
    dirTried = true
    for _, path in ipairs(CACHE_DIRS) do
      local p = tryDir(path)
      if p then
        dir, proxy = path, p
        pcall(function()
          for name in filesystem.list(dir) do
            if name:match("%.bin$") then filesystem.remove(dir .. "/" .. name) end
          end
        end)
        return true
      end
    end
    return false
  end

  local function freeSpace()
    if not proxy then return 0 end
    local ok, t, u = pcall(function() return proxy.spaceTotal(), proxy.spaceUsed() end)
    if ok and type(t) == "number" and type(u) == "number" then return t - u end
    return 0
  end

  local function newFile()
    if not ensureDir() then return nil end
    seq = seq + 1
    local path = dir .. "/c" .. seq .. ".bin"
    local ok, h = pcall(filesystem.open, path, "wb")
    if not ok or not h then return nil end
    h:close()
    return { path = path, size = 0 }
  end

  local function dropFile(f)
    if not f then return end
    if f.rh then pcall(f.rh.close, f.rh); f.rh = nil end
    pcall(filesystem.remove, f.path)
  end

  local function append(f, data)
    local ok, off = pcall(function()
      if freeSpace() < #data + CACHE_FREE_MARGIN then return nil end
      local off = filesystem.size(f.path)
      local h = filesystem.open(f.path, "ab")
      if not h then return nil end
      local good = true
      for i = 1, #data, 4096 do
        if not h:write(data:sub(i, i + 4095)) then good = false; break end
      end
      h:close()
      if not good then return nil end
      f.size = off + #data
      return off
    end)
    if ok then return off end
  end

  local function readFile(f, off, len)
    local ok, res = pcall(function()
      local h = f.rh
      if not h then
        h = filesystem.open(f.path, "rb")
        if not h then return nil end
        f.rh = h
      end
      if not h:seek("set", off) then return nil end
      local parts, n, got = {}, 0, 0
      while got < len do
        local d = h:read(min(len - got, IO_CHUNK))
        if not d or d == "" then break end
        n = n + 1
        parts[n] = d
        got = got + #d
      end
      return table.concat(parts)
    end)
    if ok then return res end
    if f.rh then pcall(f.rh.close, f.rh); f.rh = nil end
  end

  function imgstore.put(img)
    local rec = { pw = img.pw, ph = img.ph }
    local data = img.rgb
    if not curFile then curFile = newFile() end
    if curFile then
      local off = append(curFile, data)
      if off then
        rec.f, rec.a = curFile, off
        return rec
      end
    end
    rec.s = data
    cacheMem = cacheMem + #data
    return rec
  end

  function imgstore.read(rec, off, len)
    local s
    if rec.s then
      s = rec.s:sub(off + 1, off + len)
    else
      s = readFile(rec.f, rec.a + off, len)
    end
    s = s or ""
    if #s < len then s = s .. string.rep("\0", len - #s) end
    return s
  end

  function imgstore.get(key) return cache[key] end
  function imgstore.set(key, v) cache[key] = v end

  function imgstore.begin()
    saved = { cache = cache, mem = cacheMem, file = curFile }
    if (curFile and curFile.size > MAX_CACHE_BYTES) or cacheMem > MAX_MEM_CACHE_BYTES then
      cache, cacheMem, curFile = {}, 0, nil
    end
  end

  function imgstore.commit()
    if saved and saved.file and saved.file ~= curFile then dropFile(saved.file) end
    saved = nil
  end

  function imgstore.abort()
    if not saved then return end
    if curFile and curFile ~= saved.file then dropFile(curFile) end
    cache, cacheMem, curFile = saved.cache, saved.mem, saved.file
    saved = nil
  end

  function imgstore.shutdown()
    if saved and saved.file and saved.file ~= curFile then dropFile(saved.file) end
    dropFile(curFile)
    curFile, saved, cache, cacheMem = nil, nil, {}, 0
    if dir then pcall(filesystem.remove, dir) end
  end
end

local function loadImage(url, cols, pixPerCell)
  local key = url .. "|" .. cols .. "|" .. pixPerCell
  local hit = imgstore.get(key)
  if hit then
    if hit.err then return nil, hit.err end
    return hit.img
  end
  local function fail(msg)
    imgstore.set(key, { err = msg })
    return nil, msg
  end
  local data, err = httpFollow(url, IMG_HEADERS, MAX_IMAGE_BYTES)
  if not data then return fail(err) end

  local head8 = data:sub(1, 8)
  local head2 = head8:sub(1, 2)
  local head6 = head8:sub(1, 6)
  local decoder
  if head8 == "\137PNG\r\n\26\n" then
    decoder = decodePNG
  elseif head2 == "BM" then
    decoder = decodeBMP
  elseif head2 == "\255\216" then
    decoder = decodeJPEG
  elseif head6 == "GIF87a" or head6 == "GIF89a" then
    decoder = decodeGIF
  else
    return fail("unknown image format")
  end

  local box = { data }
  data = nil
  local ok, img, e = pcall(decoder, box, cols, pixPerCell)
  box = nil
  if not ok then return fail("decode error: " .. tostring(img)) end
  if not img then return fail(e or "decode failed") end
  local rec = imgstore.put(img)
  img = nil
  imgstore.set(key, { img = rec })
  return rec
end

local function parseCSS(css, rules)
  css = css:gsub("/%*.-%*/", ""):gsub("<!%-%-", ""):gsub("%-%->", "")
  css = css:gsub("@[^{;]*%b{}", ""):gsub("@[^;{]*;", "")
  for sels, body in css:gmatch("([^{}]+)%{([^{}]*)%}") do
    local props = {}
    for k, v in body:gmatch("([%w%-]+)%s*:%s*([^;]+)") do
      props[#props + 1] = { k:lower(), trim(v) }
    end
    for rawSel in sels:gmatch("[^,]+") do
      local sel = trim(rawSel)
      if sel ~= "" and sel:match("^[%w%.#_%-%*]+$") then
        local tag = (sel:match("^(%a[%w]*)") or "*"):lower()
        local id = sel:match("#([%w_%-]+)")
        local classes = {}
        for c in sel:gmatch("%.([%w_%-]+)") do classes[#classes + 1] = c end
        rules[#rules + 1] = {
          tag = tag, id = id, classes = classes, props = props, idx = #rules + 1,
          spec = (id and 100 or 0) + #classes * 10 + (tag ~= "*" and 1 or 0),
        }
      end
    end
  end
end

local function ruleMatches(r, name, attrs, cset)
  if r.tag ~= "*" and r.tag ~= name then return false end
  if r.id and r.id ~= attrs.id then return false end
  for _, c in ipairs(r.classes) do
    if not cset[c] then return false end
  end
  return true
end

local function applyDecl(s, k, v)
  v = v:gsub("%s*!important", "")
  local lv = v:lower()
  if k == "color" then
    local c = parseColor(lv)
    if c then s.fg = c; s.ownFg = true end
  elseif k == "background-color" or k == "background" then
    local c = findColor(lv)
    if c then s.bg = c; s.ownBg = true end
  elseif k == "text-align" then
    if lv:find("center") then s.align = "center"
    elseif lv:find("right") or lv:find("end") then s.align = "right"
    elseif lv:find("left") or lv:find("start") or lv:find("justify") then s.align = "left" end
  elseif k == "font-weight" then
    local num = tonumber(lv)
    if lv == "bold" or lv == "bolder" or (num and num >= 600) then s.bold = true
    elseif lv == "normal" or lv == "lighter" or num then s.bold = false end
  elseif k == "display" then
    if lv:find("none") then s.hidden = true end
  elseif k == "visibility" then
    if lv == "hidden" then s.hidden = true end
  elseif k == "text-transform" then
    s.upper = (lv == "uppercase")
  end
end

local function formEncode(s)
  s = tostring(s or "")
  s = s:gsub("\n", "\r\n")
  s = s:gsub("([^%w%-%._~ ])", function(c)
    return string.format("%%%02X", byte(c))
  end)
  return s:gsub(" ", "+")
end

local function controlValue(c)
  if c.type == "checkbox" or c.type == "radio" then
    return c.checked and (c.value ~= "" and c.value or "on") or "0"
  end
  return c.value or ""
end

local function serializeForm(controls)
  local out = {}
  for _, c in ipairs(controls) do
    if c.name and c.name ~= "" and not c.disabled then
      local skip = false
      local t = c.type
      if t == "button" or t == "reset" then
        skip = true
      elseif t == "radio" or t == "checkbox" then
        if not c.checked then skip = true end
      end
      if not skip then
        out[#out + 1] = formEncode(c.name) .. "=" .. formEncode(controlValue(c))
      end
    end
  end
  return table.concat(out, "&")
end

local function findControl(doc, id)
  for _, c in ipairs(doc.controls or {}) do
    if c.id == id then return c end
  end
end

local VOID = set { "br", "hr", "img", "meta", "link", "input", "area", "base", "col", "embed", "source", "wbr", "param", "track" }
local BLOCK = set { "html", "body", "div", "p", "h1", "h2", "h3", "h4", "h5", "h6", "ul", "ol", "li", "table", "tr",
  "blockquote", "pre", "center", "section", "article", "header", "footer", "nav", "main", "aside", "form",
  "fieldset", "dl", "dt", "dd", "address", "figure", "figcaption", "details", "summary", "caption", "thead",
  "tbody", "tfoot", "hgroup", "menu" }
local MARGIN = set { "p", "h1", "h2", "h3", "h4", "h5", "h6", "ul", "ol", "table", "blockquote", "pre", "dl", "form",
  "fieldset", "figure", "address" }
local LIST = set { "ul", "ol" }
local HEADING = set { "h1", "h2", "h3", "h4", "h5", "h6" }
local HIDE = set { "head", "title", "template", "svg", "noscript", "select", "canvas", "iframe", "object" }
local P_STOP = set { "td", "th", "li", "body", "html", "table", "div", "ul", "ol", "blockquote" }
local AUTO = {
  li = { targets = set { "li" }, stop = set { "ul", "ol" } },
  dt = { targets = set { "dt", "dd" }, stop = set { "dl" } },
  dd = { targets = set { "dt", "dd" }, stop = set { "dl" } },
  td = { targets = set { "td", "th" }, stop = set { "tr", "table" } },
  th = { targets = set { "td", "th" }, stop = set { "tr", "table" } },
  tr = { targets = set { "tr" }, stop = set { "table" } },
}

local function parseAttrs(s)
  local a = {}
  for k, _, v in s:gmatch("([%w%-_:]+)%s*=%s*([\"'])(.-)%2") do a[k:lower()] = v end
  s = s:gsub("([%w%-_:]+)%s*=%s*([\"'])(.-)%2", " ")
  for k, v in s:gmatch("([%w%-_:]+)%s*=%s*([^%s\"'>]+)") do a[k:lower()] = v end
  return a
end

local function findTagEnd(s, i)
  while true do
    local p = s:find("[>\"']", i)
    if not p then return nil end
    local ch = s:sub(p, p)
    if ch == ">" then return p end
    local qq = s:find(ch, p + 1, true)
    if not qq or qq - p > 2000 then return s:find(">", i, true) end
    i = qq + 1
  end
end

local function ciPattern(name)
  return "</" .. (name:gsub("%a", function(c) return "[" .. c:lower() .. c:upper() .. "]" end))
end
local CLOSE_PAT = { script = ciPattern("script"), style = ciPattern("style") }

local function layout(html, baseURL, w, opts)
  opts = opts or {}
  local rules = {}
  for css in html:gmatch("<[sS][tT][yY][lL][eE][^>]*>(.-)</[sS][tT][yY][lL][eE]>") do
    parseCSS(css, rules)
  end
  table.sort(rules, function(a, b)
    if a.spec ~= b.spec then return a.spec < b.spec end
    return a.idx < b.idx
  end)

  local lines, links = {}, {}
  local controls, controlSeq = {}, 0
  local forms, formSeq = {}, 0
  local title = ""
  local page = { bg = 0x000000 }
  local root = {
    fg = 0xFFFFFF, bg = 0x000000, fill = 0x000000, align = "left", indent = 0,
    bold = false, pre = false, hidden = false, upper = false, listDepth = 0,
  }
  local stack = { { name = "#root", st = root } }
  local cur, pending, imageCount = nil, false, 0

  local function st() return stack[#stack].st end

  local function ensureLine()
    if not cur then
      local s = st()
      cur = { segs = {}, len = 0, align = s.align, indent = s.indent, fill = s.fill }
    end
    return cur
  end

  local function endLine()
    if cur then
      lines[#lines + 1] = cur
      cur = nil
      pending = false
    end
  end

  local function newline()
    ensureLine()
    endLine()
  end

  local function blank()
    endLine()
    if #lines == 0 or lines[#lines].len == 0 then return end
    lines[#lines + 1] = { segs = {}, len = 0, align = "left", indent = 0, fill = st().fill }
  end

  local function newControl(c)
    controlSeq = controlSeq + 1
    c.id = controlSeq
    c.defaultValue = c.value or ""
    c.defaultChecked = c.checked or false
    controls[#controls + 1] = c
    if c.form then c.form.controls[#c.form.controls + 1] = c end
    return c
  end

  local function currentForm()
    for i = #stack, 2, -1 do
      if stack[i].name == "form" then return stack[i].form end
    end
    return nil
  end

  local function addSeg(text, s)
    local l = ensureLine()
    local fg = s.bold and emphasize(s.fg, s.bg) or s.fg
    local last = l.segs[#l.segs]
    if last and last.fg == fg and last.bg == s.bg and last.link == s.link then
      last.text = last.text .. text
    else
      l.segs[#l.segs + 1] = { text = text, fg = fg, bg = s.bg, link = s.link }
    end
    l.len = l.len + unicode.len(text)
  end

  local function addControlSeg(text, c, s)
    local l = ensureLine()
    l.segs[#l.segs + 1] = {
      text = text, fg = s.fg, bg = s.bg, link = s.link,
      control = c and c.id,
    }
    l.len = l.len + unicode.len(text)
    if c then c.rendered = true end
  end

  local function pushWord(word)
    local s = st()
    if s.upper then word = unicode.upper(word) end
    local wl = unicode.len(word)
    local l = cur
    local sp = (pending and l and l.len > 0) and 1 or 0
    if l and l.len > 0 and l.len + sp + wl > max(1, w - l.indent) then
      endLine()
      sp = 0
    end
    l = ensureLine()
    local avail = max(1, w - l.indent)
    if sp == 1 then addSeg(" ", s) end
    while wl > avail - l.len do
      local room = avail - l.len
      if room > 0 then
        addSeg(unicode.sub(word, 1, room), s)
        word = unicode.sub(word, room + 1)
        wl = wl - room
      end
      endLine()
      l = ensureLine()
    end
    addSeg(word, s)
    pending = false
    if s.link then links[s.link].hasText = true end
  end

  local function addText(text)
    local s = st()

    local top = stack[#stack]
    if top.name == "textarea" and top.control then
      top.control.value = (top.control.value or "") .. decodeEntities(text)
      return
    end
    if top.name == "option" and top.option then
      top.option.text = top.option.text .. decodeEntities(text)
      return
    end
    if top.name == "button" and top.control then
      top.control.text = top.control.text .. decodeEntities(text)
      return
    end

    if s.hidden then return end
    text = decodeEntities(text)
    if s.pre then
      text = text:gsub("\r", ""):gsub("\t", "    ")
      local i = 0
      for rawPart in (text .. "\n"):gmatch("(.-)\n") do
        local part = rawPart
        i = i + 1
        if i > 1 then newline() end
        if part ~= "" then
          if unicode.len(part) > w - s.indent then part = unicode.sub(part, 1, max(1, w - s.indent)) end
          addSeg(part, s)
        end
      end
      return
    end
    if text:match("^%s") then pending = true end
    for word in text:gmatch("%S+") do
      pushWord(word)
      pending = true
    end
    if not text:match("%s$") and text:find("%S") then pending = false end
  end

  local function emitImage(img, s)
    endLine()
    local rows = floor(img.ph / 2)
    local first = #lines + 1
    local proto = {
      img = img, first = first, rows = rows, len = img.pw, link = s.link,
      align = s.align, indent = s.indent, fill = s.fill,
    }
    for r = 0, rows - 1 do lines[first + r] = proto end
    if s.link then links[s.link].hasText = true end
  end

  local function doImage(attrs, s)
    if s.hidden then return end
    local alt = attrs.alt and trim(decodeEntities(attrs.alt)) or ""
    local wpx = tonumber((attrs.width or ""):match("^%d+"))
    local hpx = tonumber((attrs.height or ""):match("^%d+"))
    if (wpx and wpx <= 4) or (hpx and hpx <= 4) then return end
    local src = attrs.src and resolveURL(baseURL, attrs.src)

    local function placeholder(reason)
      if reason and #reason > 24 then reason = "image" end
      local text = alt ~= "" and ("[" .. alt .. "]") or ("[" .. (reason or "image") .. "]")
      pending = true
      pushWord(text)
    end

    if not (opts.images and src) then return placeholder() end
    imageCount = imageCount + 1

    local pixPerCell = (IMAGE_MODE == "half" and depth > 1) and 2 or 4
    local cols = max(4, min(w - s.indent, 120))
    if wpx then cols = min(cols, max(4, ceil(wpx / 5))) end

    if opts.status then
      opts.status("Loading image " .. imageCount .. ": " .. src)
    end
    local img, err = loadImage(src, cols, pixPerCell)
    gc()
    if not img then return placeholder(err) end

    emitImage(img, s)
  end

  local function closeElement()
    local e = stack[#stack]
    local n = e.name
    if n == "a" and e.linkIdx and LINK_MARKERS and not e.st.hidden then
      if links[e.linkIdx].hasText then
        pending = true
        pushWord("[" .. e.linkIdx .. "]")
      end
    end

    if n == "textarea" and e.control then
      local c = e.control
      endLine()
      local value = c.value or ""
      local rows = {}
      for line in (value .. "\n"):gmatch("(.-)\n") do
        rows[#rows + 1] = line
      end
      if #rows == 0 then rows[1] = "" end
      for i = 1, c.rows do
        local text = rows[i] or ""
        text = unicode.sub(text, 1, c.cols)
        local shown = "| " .. text ..
          string.rep(" ", max(0, c.cols - unicode.len(text))) .. " |"
        lines[#lines + 1] = {
          segs = { { text = shown, fg = c.fg, bg = c.bg, control = c.id } },
          len = unicode.len(shown), align = e.st.align,
          indent = e.st.indent, fill = e.st.fill,
        }
      end
      endLine()
      stack[#stack] = nil
      return
    end

    if n == "select" and e.control then
      local c = e.control
      endLine()
      local option = c.options[c.selected]
      local text = option and option.text or ""
      local shown = "[ " ..
        unicode.sub(text, 1, max(5, w - e.st.indent - 6)) .. " v ]"
      lines[#lines + 1] = {
        segs = { { text = shown, fg = c.fg, bg = c.bg, control = c.id } },
        len = unicode.len(shown), align = e.st.align,
        indent = e.st.indent, fill = e.st.fill,
      }
      stack[#stack] = nil
      return
    end

    if n == "button" and e.control then
      local c = e.control
      endLine()
      local text = trim(c.text)
      if text == "" then text = "Button" end
      local shown = "[ " .. text .. " ]"
      lines[#lines + 1] = {
        segs = { { text = shown, fg = c.fg, bg = c.bg, control = c.id } },
        len = unicode.len(shown), align = e.st.align,
        indent = e.st.indent, fill = e.st.fill,
      }
      stack[#stack] = nil
      return
    end

    if BLOCK[n] then
      endLine()
      if MARGIN[n] and (not LIST[n] or e.st.listDepth <= 1) then blank() end
    end
    stack[#stack] = nil
  end

  local function closeTo(i)
    for _ = #stack, i, -1 do closeElement() end
  end

  local function closeUntilAny(targets, stop)
    for i = #stack, 2, -1 do
      local n = stack[i].name
      if targets[n] then return closeTo(i) end
      if stop[n] then return end
    end
  end

  local function closeTag(name)
    for i = #stack, 2, -1 do
      if stack[i].name == name then return closeTo(i) end
    end
  end

  local function openTag(name, attrs, selfClose)
    if BLOCK[name] and name ~= "html" and name ~= "body" then
      closeUntilAny({ p = true }, P_STOP)
    end
    if AUTO[name] then closeUntilAny(AUTO[name].targets, AUTO[name].stop) end

    local s = copy(st())
    s.ownBg, s.ownFg = false, false

    if HIDE[name] then s.hidden = true end
    if name == "body" then s.hidden = false end
    if HEADING[name] or name == "b" or name == "strong" or name == "th" then s.bold = true end
    if name == "h1" then s.upper = true end
    if name == "center" or name == "th" then s.align = "center" end
    if name == "pre" then s.pre = true end
    if LIST[name] then s.indent = s.indent + 2; s.listDepth = s.listDepth + 1 end
    if name == "blockquote" then s.indent = s.indent + 4 end

    local linkIdx
    if name == "a" and attrs.href then
      local target = resolveURL(baseURL, attrs.href)
      if target then
        links[#links + 1] = { href = target, hasText = false }
        linkIdx = #links
        s.link = linkIdx
        s.fg = s.linkColor or (lum(s.bg) < 128 and 0x66AAFF or 0x0000EE)
      end
    end

    if attrs.align and name ~= "table" then
      local a = attrs.align:lower()
      if a == "middle" then a = "center" end
      if a == "left" or a == "center" or a == "right" then s.align = a end
    end
    if attrs.bgcolor then
      local c = parseColor(attrs.bgcolor, true)
      if c then s.bg = c; s.ownBg = true end
    end
    if name == "font" and attrs.color then
      local c = parseColor(attrs.color, true)
      if c then s.fg = c; s.ownFg = true end
    end
    if name == "body" then
      if attrs.text then
        local c = parseColor(attrs.text, true)
        if c then s.fg = c; s.ownFg = true end
      end
      if attrs.link then
        local c = parseColor(attrs.link, true)
        if c then s.linkColor = c end
      end
    end

    if #rules > 0 then
      local cset = {}
      if attrs.class then
        for c in attrs.class:gmatch("%S+") do cset[c] = true end
      end
      for _, r in ipairs(rules) do
        if ruleMatches(r, name, attrs, cset) then
          for _, p in ipairs(r.props) do applyDecl(s, p[1], p[2]) end
        end
      end
    end
    if attrs.style then
      for k, v in attrs.style:gmatch("([%w%-]+)%s*:%s*([^;]+)") do
        applyDecl(s, k:lower(), trim(v))
      end
    end

    if s.ownBg and BLOCK[name] then s.fill = s.bg end
    if abs(lum(s.fg) - lum(s.bg)) < 40 then
      s.fg = lum(s.bg) > 127 and 0x000000 or 0xFFFFFF
    end
    if name == "html" or name == "body" then
      if s.ownBg then page.bg = s.bg end
    end

    local form
    if name == "form" and ENABLE_FORMS then
      formSeq = formSeq + 1
      form = {
        id = formSeq,
        action = resolveURL(baseURL, attrs.action or baseURL) or baseURL,
        method = (attrs.method or "GET"):upper(),
        controls = {},
      }
      forms[#forms + 1] = form
    end

    if VOID[name] or selfClose then
      stack[#stack + 1] = { name = name, st = s }
      if name == "br" then
        newline()
      elseif name == "hr" then
        endLine()
        local n = max(1, w - s.indent)
        lines[#lines + 1] = {
          segs = { { text = string.rep("-", n), fg = s.fg, bg = s.bg } },
          len = n, align = "left", indent = s.indent, fill = s.fill,
        }
      elseif name == "img" then
        doImage(attrs, s)
      elseif name == "input" and not s.hidden and ENABLE_FORMS then
        local t = (attrs.type or "text"):lower()
        local c = newControl({
          type = t,
          name = attrs.name,
          value = attrs.value or "",
          checked = attrs.checked ~= nil,
          disabled = attrs.disabled ~= nil,
          form = currentForm(),
          attrs = attrs,
          fg = s.fg,
          bg = s.bg,
        })

        if t == "submit" or t == "button" or t == "reset" then
          local label = attrs.value or (t == "reset" and "Reset" or "Submit")
          pending = true
          addControlSeg("[ " .. label .. " ]", c, s)
        elseif t == "checkbox" then
          pending = true
          addControlSeg(c.checked and "[x]" or "[ ]", c, s)
        elseif t == "radio" then
          pending = true
          addControlSeg(c.checked and "(o)" or "( )", c, s)
        elseif t == "hidden" then
        else
          local value = c.value
          if t == "password" then
            value = string.rep("*", unicode.len(value))
          end
          local width = tonumber(attrs.size) or 20
          width = max(4, min(width, max(4, w - s.indent - 4)))
          local shown = unicode.sub(value, 1, width)
          pending = true
          addControlSeg(
            "[" .. shown .. string.rep("_", max(0, width - unicode.len(shown))) .. "]",
            c, s
          )
        end
      end
      stack[#stack] = nil
      return
    end

    if name == "textarea" and ENABLE_FORMS then
      local c = newControl({
        type = "textarea",
        name = attrs.name,
        value = "",
        disabled = attrs.disabled ~= nil,
        form = currentForm(),
        attrs = attrs,
        fg = s.fg,
        bg = s.bg,
      })
      c.rows = max(1, min(tonumber(attrs.rows) or 3, 10))
      c.cols = max(5, min(tonumber(attrs.cols) or 30, max(5, w - s.indent - 2)))
      if c.attrs and c.attrs.value then c.value = c.attrs.value end
      stack[#stack + 1] = { name = "textarea", st = s, control = c }
      endLine()
      return
    end

    if name == "select" and ENABLE_FORMS then
      local c = newControl({
        type = "select",
        name = attrs.name,
        value = "",
        options = {},
        selected = 1,
        disabled = attrs.disabled ~= nil,
        form = currentForm(),
        attrs = attrs,
        fg = s.fg,
        bg = s.bg,
      })
      stack[#stack + 1] = { name = "select", st = s, control = c }
      endLine()
      return
    end

    if name == "option" and ENABLE_FORMS then
      local parent = stack[#stack]
      if parent and parent.name == "select" then
        local c = parent.control
        local option = {
          value = attrs.value or "",
          text = "",
          selected = attrs.selected ~= nil,
        }
        c.options[#c.options + 1] = option
        if option.selected then
          c.selected = #c.options
          c.value = option.value
        elseif #c.options == 1 then
          c.selected = 1
          c.value = option.value
        end
        stack[#stack + 1] = { name = "option", st = s, option = option }
        return
      end
    end

    if name == "button" and ENABLE_FORMS then
      local c = newControl({
        type = attrs.type or "submit",
        name = attrs.name,
        value = attrs.value or "",
        text = "",
        disabled = attrs.disabled ~= nil,
        form = currentForm(),
        fg = s.fg,
        bg = s.bg,
        attrs = attrs,
      })
      stack[#stack + 1] = { name = "button", st = s, control = c }
      return
    end

    if BLOCK[name] then endLine() end
    stack[#stack + 1] = { name = name, st = s, linkIdx = linkIdx, form = form }
    if BLOCK[name] and MARGIN[name] and (not LIST[name] or s.listDepth <= 1) then blank() end

    if name == "li" then
      local listE
      for i = #stack - 1, 1, -1 do
        if LIST[stack[i].name] then listE = stack[i]; break end
      end
      local prefix = "* "
      if listE and listE.name == "ol" then
        listE.n = (listE.n or 0) + 1
        prefix = listE.n .. ". "
      end
      ensureLine()
      pending = false
      addSeg(prefix, s)
    elseif name == "td" or name == "th" then
      for i = #stack - 1, 1, -1 do
        local n = stack[i].name
        if n == "tr" then
          local row = stack[i]
          if (row.cells or 0) > 0 then
            ensureLine()
            addSeg(" | ", row.st)
          end
          row.cells = (row.cells or 0) + 1
          pending = false
          break
        elseif n == "table" then
          break
        end
      end
    end
  end

  local pos, n, tags = 1, #html, 0
  while pos <= n do
    local lt = html:find("<", pos, true)
    if not lt then
      addText(html:sub(pos))
      break
    end
    if lt > pos then
      local t = html:sub(pos, lt - 1)
      if stack[#stack].name == "title" then title = title .. decodeEntities(t) end
      addText(t)
    end
    local nextpos
    local c2 = html:sub(lt + 1, lt + 1)
    if html:sub(lt + 1, lt + 3) == "!--" then
      local e = html:find("-->", lt + 4, true)
      nextpos = e and e + 3 or n + 1
    elseif c2 == "!" or c2 == "?" then
      local e = html:find(">", lt + 1, true)
      nextpos = e and e + 1 or n + 1
    elseif c2 ~= "" and c2:match("[%a/]") then
      local e = findTagEnd(html, lt + 1)
      if not e then
        addText(html:sub(lt))
        break
      end
      local inner = html:sub(lt + 1, e - 1)
      local closing, name, rest = inner:match("^(/?)([%a][%w%-]*)(.*)$")
      if not name then
        addText("<")
        nextpos = lt + 1
      else
        name = name:lower()
        nextpos = e + 1
        if closing == "/" then
          closeTag(name)
        elseif name == "script" or name == "style" then
          local cs = html:find(CLOSE_PAT[name], e + 1)
          if cs then
            local ce = html:find(">", cs, true)
            nextpos = (ce or n) + 1
          else
            nextpos = n + 1
          end
        else
          openTag(name, parseAttrs(rest), rest:sub(-1) == "/")
        end
      end
    else
      addText("<")
      nextpos = lt + 1
    end
    pos = nextpos
    tags = tags + 1
    if tags % 100 == 0 then os.sleep(0) end
  end

  if #stack > 1 then closeTo(2) end
  endLine()
  return {
    lines = lines,
    links = links,
    controls = controls,
    forms = forms,
    title = decodeEntities(trim(title)),
    bg = page.bg,
  }
end

local imgBlocks = {}

local function prefetchImages(doc, first, last)
  local blocks, lines = {}, doc.lines
  local i = first
  while i <= last do
    local l = lines[i]
    if l and l.img then
      local j = i
      while j < last and lines[j + 1] == l do j = j + 1 end
      local r1, r2 = i - l.first, j - l.first
      local old = imgBlocks[l]
      if old and old.r1 <= r1 and old.r2 >= r2 then
        blocks[l] = old
      else
        local a, b = max(0, r1 - 8), min(l.rows - 1, r2 + 8)
        local rowBytes = l.img.pw * 6
        blocks[l] = { r1 = a, r2 = b,
          data = imgstore.read(l.img, a * rowBytes, (b - a + 1) * rowBytes) }
      end
      i = j + 1
    else
      i = i + 1
    end
  end
  imgBlocks = blocks
  return blocks
end

local function imageSegs(l, li, blk)
  local pw = l.img.pw
  local stride = pw * 3
  local rgb = blk.data
  local top = (li - l.first - blk.r1) * 2 * stride + 1
  local segs, last, n = {}, nil, 0
  local link = l.link
  for x = 0, pw - 1 do
    local o1 = top + x * 3
    local o2 = o1 + stride
    local r1, g1, b1 = byte(rgb, o1, o1 + 2)
    local r2, g2, b2 = byte(rgb, o2, o2 + 2)
    if invertImages then
      r1, g1, b1 = 255 - r1, 255 - g1, 255 - b1
      r2, g2, b2 = 255 - r2, 255 - g2, 255 - b2
    end
    local fg = r1 * 65536 + g1 * 256 + b1
    local bg = r2 * 65536 + g2 * 256 + b2
    if last and last.fg == fg and last.bg == bg then
      last.n = last.n + 1
    else
      n = n + 1
      last = { fg = fg, bg = bg, link = link, n = 1 }
      segs[n] = last
    end
  end
  for i = 1, n do
    local sg = segs[i]
    sg.text = sg.n == 1 and "▀" or string.rep("▀", sg.n)
  end
  return segs
end

local function draw(doc, offset, w, h, url, hit, focusId)
  local ch = h - 1
  local blocks = prefetchImages(doc, offset + 1, offset + ch)

  local buffered = beginBufferRender(w, ch)

  if buffered then
    gpu.setBackground(q(doc.bg))
    gpu.fill(1, 1, w, ch, " ")
  else
    gpu.setActiveBuffer(0)
  end

  for row = 1, ch do
    local l = doc.lines[offset + row]
    hit[row] = {}

    gpu.setBackground(q(l and l.fill or doc.bg))
    gpu.fill(1, row, w, 1, " ")

    if l and l.len > 0 then
      local avail = w - l.indent
      local x = 1 + l.indent

      if l.align == "center" then
        x = x + max(0, floor((avail - l.len) / 2))
      elseif l.align == "right" then
        x = x + max(0, avail - l.len)
      end

      for _, sg in ipairs(l.segs or imageSegs(l, offset + row, blocks[l])) do
        local txt = sg.text
        local len = unicode.len(txt)

        local isFocused =
          sg.control and focusId and sg.control == focusId

        if isFocused then
          gpu.setForeground(q(0xFFFFFF))
          gpu.setBackground(q(0x0055AA))
        else
          gpu.setForeground(q(sg.fg))
          gpu.setBackground(q(sg.bg))
        end

        if x + len - 1 > w then
          txt = unicode.sub(txt, 1, max(0, w - x + 1))
          len = unicode.len(txt)
        end

        if txt ~= "" then
          gpu.set(x, row, txt)
        end

        if sg.link or sg.control then
          hit[row][#hit[row] + 1] = {
            x,
            min(w, x + len - 1),
            sg.link,
            sg.control
          }
        end

        x = x + len
      end
    end
  end

  if buffered then
    presentBuffer(w, ch)
  end

  local imageState = LOAD_IMAGES and "IMG:on" or "IMG:off"
  local total = max(1, #doc.lines - ch)
  local pct = floor(min(offset, total) * 100 / total)
  local name = doc.title ~= "" and doc.title or url

  status(string.format(
    "%d%% %s | %s | Arrows:scroll Tab:focus Enter:activate L:link U:url I:invert-img Bksp:back R:reload Q:quit",
    pct,
    name,
    imageState
  ))
end

local function normalizeURL(u)
  u = trim(u or "")
  if u == "" then return nil end
  if not u:match("^https?://") then u = "http://" .. u end
  return u
end

local function prompt(label)
  local w, h = gpu.getResolution()
  pcall(gpu.setActiveBuffer, 0)
  gpu.setForeground(0xFFFFFF)
  gpu.setBackground(0x000000)
  gpu.fill(1, h, w, 1, " ")
  term.setCursor(1, h)
  io.write(label)
  local r = io.read()
  return r
end

local function editControl(c, w, h)
  pcall(gpu.setActiveBuffer, 0)
  local value = c.value or ""
  local cursor = unicode.len(value)

  local function redraw()
    gpu.setBackground(q(0x000000))
    gpu.setForeground(q(0xFFFFFF))
    gpu.fill(1, h, w, 1, " ")

    local shown = value
    if c.type == "password" then
      shown = string.rep("*", unicode.len(value))
    end

    local maxWidth = max(1, w - 2)
    if unicode.len(shown) > maxWidth then
      shown = unicode.sub(shown, unicode.len(shown) - maxWidth + 1)
    end
    gpu.set(1, h, shown .. "_")
  end

  redraw()

  while true do
    local e = { event.pull() }
    if e[1] == "key_down" then
      local ch = e[3]
      local code = e[4]

      if code == 28 then
        c.value = value
        return true
      elseif code == 1 then
        return false
      elseif code == 14 then
        if cursor > 0 then
          value = unicode.sub(value, 1, cursor - 1) .. unicode.sub(value, cursor + 1)
          cursor = cursor - 1
        end
      elseif code == 203 then
        cursor = max(0, cursor - 1)
      elseif code == 205 then
        cursor = min(unicode.len(value), cursor + 1)
      elseif code == 199 then
        cursor = 0
      elseif code == 207 then
        cursor = unicode.len(value)
      elseif ch and ch > 0 then
        local character = unicode.char(ch)
        value = unicode.sub(value, 1, cursor) .. character .. unicode.sub(value, cursor + 1)
        cursor = cursor + unicode.len(character)
      end
      redraw()
    end
  end
end

local function submitForm(form, go, status)
  if not form then return end
  local data = serializeForm(form.controls)
  if form.method == "GET" then
    local target = form.action
    if data ~= "" then
      target = target .. (target:find("?", 1, true) and "&" or "?") .. data
    end
    go(target, true)
  else
    status("POST forms are not supported by this OC internet API yet")
  end
end

local function browse(startUrl)
  local w, h = gpu.getResolution()
  local ch = h - 1
  local url, doc, offset = nil, nil, 0
  local history = {}
  local hit = {}
  local focusedControl = nil

  local function redraw()
    draw(doc, offset, w, h, url, hit, focusedControl)
  end

  local function open(target, push)
    status("Loading " .. target .. " ...")
    local ok, data, finalUrl = fetchPage(target)
    if not ok then return false, tostring(data) end
    status("Rendering ...")
    imgstore.begin()
    local ok2, d = pcall(layout, data, finalUrl, w, { images = LOAD_IMAGES, status = status })
    data = nil
    if not ok2 then
      imgstore.abort()
      return false, "Render error: " .. tostring(d)
    end
    if push and url then history[#history + 1] = { url = url, offset = offset } end
    url, doc, offset = finalUrl, d, 0
    focusedControl = nil
    imgstore.commit()
    gc()
    return true
  end

  local ok, err = open(startUrl, false)
  if not ok then
    pcall(gpu.setActiveBuffer, 0)
    gpu.setForeground(0xFFFFFF); gpu.setBackground(0x000000)
    term.clear()
    print("Error fetching URL: " .. err)
    freeRenderBuffer()
    return
  end
  redraw()

  local function go(target, push)
    local ok2, e = open(target, push)
    if ok2 then
      redraw()
    else
      redraw()
      status("Error: " .. e)
    end
  end

  local function scrollTo(o)
    o = max(0, min(o, max(0, #doc.lines - ch)))
    if o ~= offset then
      offset = o
      redraw()
    end
  end

  local function activate(c)
    if not c or c.disabled then return end
    focusedControl = c.id

    if c.type == "text" or c.type == "password" or c.type == "search"
      or c.type == "email" or c.type == "url" or c.type == "number" then
      editControl(c, w, h)
      redraw()

    elseif c.type == "checkbox" then
      c.checked = not c.checked
      redraw()

    elseif c.type == "radio" then
      for _, other in ipairs(doc.controls) do
        if other.type == "radio" and other.name == c.name then
          other.checked = false
        end
      end
      c.checked = true
      redraw()

    elseif c.type == "reset" then
      for _, other in ipairs(doc.controls) do
        if other.form == c.form then
          other.value = other.defaultValue or ""
          other.checked = other.defaultChecked or false
        end
      end
      redraw()

    elseif c.type == "submit" or c.type == "button" then
      submitForm(c.form, go, status)
    end
  end

  while true do
    local e = { event.pull() }
    local name = e[1]
    if name == "key_down" then
      local code = e[4]
      if code == 200 then scrollTo(offset - 1)
      elseif code == 208 then scrollTo(offset + 1)
      elseif code == 201 then scrollTo(offset - (ch - 1))
      elseif code == 209 then scrollTo(offset + (ch - 1))
      elseif code == 199 then scrollTo(0)
      elseif code == 207 then scrollTo(#doc.lines)
      elseif code == 16 then break
      elseif code == 19 then go(url, false)
      elseif code == 14 then
        local prev = table.remove(history)
        if prev then
          go(prev.url, false)
          scrollTo(prev.offset)
        end
      elseif code == 23 then
        invertImages = not invertImages
        redraw()
      elseif code == 22 then
        local t = normalizeURL(prompt("URL: "))
        if t then go(t, true) else redraw() end
      elseif code == 38 then
        local n = tonumber(prompt("Link number: ") or "")
        local L = n and doc.links[n]
        if L then go(L.href, true) else redraw() end
      elseif code == 15 and TAB_FOCUS then
        local nextIndex = 1
        if focusedControl then
          for i, c in ipairs(doc.controls) do
            if c.id == focusedControl then nextIndex = i + 1; break end
          end
        end
        if nextIndex > #doc.controls then nextIndex = 1 end
        focusedControl = nil
        for i = nextIndex, #doc.controls do
          if not doc.controls[i].disabled then
            focusedControl = doc.controls[i].id
            break
          end
        end
        if not focusedControl and #doc.controls > 0 then
          focusedControl = doc.controls[1].id
        end
        redraw()
      elseif code == 28 and focusedControl then
        local c = findControl(doc, focusedControl)
        if c then activate(c) end
      end
    elseif name == "scroll" then
      scrollTo(offset - (e[5] or 0) * 3)
    elseif name == "touch" then
      local x, y = e[3], e[4]
      for _, r in ipairs(hit[y] or {}) do
        if x >= r[1] and x <= r[2] then
          if r[3] then
            focusedControl = nil
            go(doc.links[r[3]].href, true)
          elseif r[4] then
            local c = findControl(doc, r[4])
            if c then activate(c) end
          end
          break
        end
      end
    end
  end

  pcall(gpu.setActiveBuffer, 0)
  gpu.setForeground(0xFFFFFF)
  gpu.setBackground(0x000000)
  term.clear()

  freeRenderBuffer()
end

local function bootUpScreen()
  term.clear()
  local logo = [[
 ::::::::   ::::::::               :::       ::: :::::::::: :::::::::
:+:    :+: :+:    :+:              :+:       :+: :+:        :+:    :+:
+:+    +:+ +:+                     +:+       +:+ +:+        +:+    +:+
+#+    +:+ +#+       +#++:++#++:++ +#+  +:+  +#+ +#++:++#   +#++:++#+
+#+    +#+ +#+                     +#+ +#+#+ +#+ +#+        +#+    +#+
#+#    #+# #+#    #+#               #+#+# #+#+#  #+#        #+#    #+#
 ########   ########                 ###   ###   ########## #########
    ]]
  term.setCursor(1, 1)
  term.write(logo)
  print()
  print("Loading...")
  print()
  print("OC-WEB 3.0: A Web Browser For OpenComputers Coded by nonogamer9")
  os.sleep(2)
end

local function main(...)
  local args = { ... }

  for i = #args, 1, -1 do
    if args[i] == "--no-image" then
      LOAD_IMAGES = false
      table.remove(args, i)
    end
  end

  pcall(gpu.setActiveBuffer, 0)
  gpu.setForeground(0xFFFFFF)
  gpu.setBackground(0x000000)
  bootUpScreen()
  term.clear()
  local url = normalizeURL(args[1])
  if not url then
    print("Enter a URL:")
    url = normalizeURL(io.read())
  end
  if not url then
    print("No URL given.")
    return
  end
  local okb, errb = pcall(browse, url)
  imgstore.shutdown()
  if not okb then error(errb, 0) end
end

main(...)