local M={}
local byte,char,sub=string.byte,string.char,string.sub

local function u32be(s,i)local a,b,c,d=byte(s,i,i+3)return((a<<24)|(b<<16)|(c<<8)|d)end
local function u16be(s,i)local a,b=byte(s,i,i+1)return(a<<8)|b end
local function u16le(s,i)local a,b=byte(s,i,i+1)return a|(b<<8)end

function M.size(d)
if sub(d,1,8)=="\137PNG\r\n\26\n"then return u32be(d,17),u32be(d,21),"png"end
if sub(d,1,4)=="GIF8"then return u16le(d,7),u16le(d,9),"gif"end
if sub(d,1,2)=="\255\216"then
local p=3
while p<#d do
if byte(d,p)~=0xFF then return nil end
local m=byte(d,p+1)
if m>=0xC0 and m<=0xCF and m~=0xC4 and m~=0xC8 and m~=0xCC then
return u16be(d,p+7),u16be(d,p+5),m==0xC2 and"jpeg-progressive"or"jpeg"
end
p=p+2+u16be(d,p+2)
end
end
if sub(d,1,4)=="RIFF"and sub(d,9,12)=="WEBP"then return nil,nil,"webp"end
return nil
end




local function inflateStream(data,emit,yield,rawSize)
local ok,comp=pcall(require,"component")
if ok and comp and comp.isAvailable and comp.isAvailable("data")and(rawSize or 0)<=256*1024 then
local ok2,res=pcall(comp.data.inflate,data)
if ok2 and res then emit(res)return end
end
local pos,bitbuf,bitcnt=3,0,0
local function bits(n)
while bitcnt<n do
bitbuf=bitbuf|((byte(data,pos)or 0)<<bitcnt)
pos=pos+1
bitcnt=bitcnt+8
end
local v=bitbuf&((1<<n)-1)
bitbuf=bitbuf>>n
bitcnt=bitcnt-n
return v
end
local function build(lengths,n)
local counts,offs,syms={},{},{}
for i=0,15 do counts[i]=0 end
for i=0,n-1 do counts[lengths[i]or 0]=counts[lengths[i]or 0]+1 end
counts[0]=0
offs[1]=0
for i=1,14 do offs[i+1]=offs[i]+counts[i]end
for i=0,n-1 do
local l=lengths[i]or 0
if l>0 then syms[offs[l]]=i;offs[l]=offs[l]+1 end
end
return{counts,syms}
end
local function decode(h)
local counts,syms=h[1],h[2]
local code,first,index=0,0,0
for l=1,15 do
code=code|bits(1)
local count=counts[l]
if code-count<first then return syms[index+(code-first)]end
index=index+count
first=(first+count)<<1
code=code<<1
end
error("inflate: bad code")
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 buf,n,hist={},0,""
local total=0
local function flush()
if n==0 then return end
local s=char(table.unpack(buf,1,n))
emit(s)
hist=hist..s
if#hist>40000 then hist=sub(hist,-32768)end
n=0
total=total+#s
if yield then yield()end
end
local function put(b)
n=n+1
buf[n]=b
if n>=4096 then flush()end
end
local function back(d)
if d<=n then return buf[n-d+1]end
return byte(hist,#hist-(d-n)+1)
end
local fixedL,fixedD
repeat
local final=bits(1)
local typ=bits(2)
if typ==0 then
bitbuf,bitcnt=0,0
local len=u16le(data,pos)
pos=pos+4
for i=0,len-1 do put(byte(data,pos+i))end
pos=pos+len
else
local lit,dist
if typ==1 then
if not fixedL 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
fixedL=build(l,288)
local d={}for i=0,29 do d[i]=5 end
fixedD=build(d,30)
end
lit,dist=fixedL,fixedD
else
local hlit,hdist,hclen=bits(5)+257,bits(5)+1,bits(4)+4
local ORDER={16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}
local cl={}
for i=1,19 do cl[ORDER[i]]=i<=hclen and bits(3)or 0 end
local clh=build(cl,19)
local lens,i={},0
while i<hlit+hdist do
local sym=decode(clh)
if sym<16 then lens[i]=sym;i=i+1
else
local rep,val=0,0
if sym==16 then val=lens[i-1];rep=3+bits(2)
elseif sym==17 then rep=3+bits(3)else rep=11+bits(7)end
for _=1,rep do lens[i]=val;i=i+1 end
end
end
local ll,dl={},{}
for k=0,hlit-1 do ll[k]=lens[k]end
for k=0,hdist-1 do dl[k]=lens[hlit+k]end
lit,dist=build(ll,hlit),build(dl,hdist)
end
while true do
local sym=decode(lit)
if sym<256 then put(sym)
elseif sym==256 then break
else
sym=sym-256
local length=LBASE[sym]+bits(LEXT[sym])
local ds=decode(dist)+1
local d=DBASE[ds]+bits(DEXT[ds])
for _=1,length do put(back(d))end
end
end
end
until final==1
flush()
end
function M.inflate(data)
local parts={}
inflateStream(data,function(s)parts[#parts+1]=s end)
return table.concat(parts)
end




M.TRANSPARENT=0x010203




local function Sink(sw,sh,tw,th)
local T=M.TRANSPARENT
local pack=string.pack
local fx,fy=sw/tw,sh/th
local cols={}
for x=0,tw-1 do
local x0=math.floor(x*fx)
local x1=math.max(x0,math.floor((x+1)*fx)-1)
local step=math.max(1,(x1-x0+1)/4)
local xs,xx={},x0
while xx<=math.min(x1,sw-1)do xs[#xs+1]=math.floor(xx);xx=xx+step end
cols[x+1]=xs
end
local rows={}
local sr,sg,sb,cnt,tr,lo,loC,hi,hiC={},{},{},{},{},{},{},{},{}
local function reset()
for i=1,tw do sr[i],sg[i],sb[i],cnt[i],tr[i],lo[i],hi[i]=0,0,0,0,0,1e9,-1 end
end
reset()
local cur=0
local function finalize()
local out={}
for i=1,tw do
local n=cnt[i]
local c
if n==0 or tr[i]>n then c=T
else
local ar,ag,ab=sr[i]//n,sg[i]//n,sb[i]//n
c=(ar<<16)|(ag<<8)|ab
if n>1 then
local function dev(v)return math.abs((v>>16)-ar)+math.abs(((v>>8)&255)-ag)+math.abs((v&255)-ab)end
local dl,dh=dev(loC[i]),dev(hiC[i])
if dl>180 or dh>180 then c=dl>=dh and loC[i]or hiC[i]end
end
if c==T then c=T+1 end
end
out[i]=pack(">I3",c)
end
return table.concat(out)
end
local sink={}
function sink.row(y,get)

local t0=math.floor(y/fy)
if t0>=th then return end
while cur<t0 do
rows[#rows+1]=finalize()
reset()
cur=cur+1
end
local y0=math.floor(cur*fy)
local stepY=math.max(1,math.floor(fy/4))
if(y-y0)%stepY~=0 then return end
for i=1,tw do
for _,sx in ipairs(cols[i])do
local c=get(sx)
if c then
sr[i],sg[i],sb[i],cnt[i]=sr[i]+(c>>16),sg[i]+((c>>8)&255),sb[i]+(c&255),cnt[i]+1
local l=(c>>16)*3+((c>>8)&255)*6+(c&255)
if l<lo[i]then lo[i],loC[i]=l,c end
if l>hi[i]then hi[i],hiC[i]=l,c end
else tr[i]=tr[i]+1 end
end
end

if fy<1 then
local tEnd=math.min(th-1,math.floor((y+1)/fy-1e-9))
local r=finalize()
while cur<=tEnd do rows[#rows+1]=r;cur=cur+1 end
reset()
end
end
function sink.result()
if cur<th and#rows<th then
local r=finalize()
while#rows<th do rows[#rows+1]=r end
end
return{w=tw,h=th,px=table.concat(rows,"",1,th)}
end
return sink
end


function M.pixel(img,x,y)
local c=string.unpack(">I3",img.px,(y*img.w+x)*3+1)
if c==M.TRANSPARENT then return false end
return c
end


local function decodePNG(d,tw,th,yield)
local w,h=u32be(d,17),u32be(d,21)
local depth,ctype,interlace=byte(d,25),byte(d,26),byte(d,29)
if interlace~=0 then return nil,"interlaced PNG"end
local idat,pal,trns={},nil,nil
local p=9
while p<#d do
local len,typ=u32be(d,p),sub(d,p+4,p+7)
if typ=="IDAT"then idat[#idat+1]=sub(d,p+8,p+7+len)
elseif typ=="PLTE"then pal=sub(d,p+8,p+7+len)
elseif typ=="tRNS"then trns=sub(d,p+8,p+7+len)
elseif typ=="IEND"then break end
p=p+12+len
end
local chans=({[0]=1,[2]=3,[3]=1,[4]=2,[6]=4})[ctype]
if not chans then return nil,"PNG colour type"end
local bpp=math.max(1,chans*depth//8)
local stride=(w*chans*depth+7)//8
local sink=Sink(w,h,tw,th)
local prev={}
for i=1,stride do prev[i]=0 end
local pend,y="",0
local cur
local function px(x)
local a,b,c,al
if depth==8 then local o=x*chans a,b,c,al=cur[o+1],cur[o+2],cur[o+3],cur[o+4]
elseif depth==16 then local o=x*chans*2 a,b,c,al=cur[o+1],cur[o+3],cur[o+5],cur[o+7]
else
local bit=x*depth
local v=(cur[(bit>>3)+1]>>(8-depth-(bit&7)))&((1<<depth)-1)
if ctype==0 then v=v*255//((1<<depth)-1)end
a=v
end
if ctype==0 then return(a<<16)|(a<<8)|a
elseif ctype==2 then return(a<<16)|(b<<8)|c
elseif ctype==3 then
if not pal then return 0 end
if trns and(byte(trns,a+1)or 255)<128 then return false end
local r,g,bb=byte(pal,a*3+1,a*3+3)
return((r or 0)<<16)|((g or 0)<<8)|(bb or 0)
elseif ctype==4 then if b<128 then return false end return(a<<16)|(a<<8)|a
else if al<128 then return false end return(a<<16)|(b<<8)|c end
end
local function onBytes(s)
pend=pend..s
local rb=stride+1
local off=1
while#pend-off+1>=rb and y<h do
local ft=byte(pend,off)
cur={byte(pend,off+1,off+stride)}
off=off+rb
if ft==1 then for i=bpp+1,stride do cur[i]=(cur[i]+cur[i-bpp])&255 end
elseif ft==2 then for i=1,stride do cur[i]=(cur[i]+prev[i])&255 end
elseif ft==3 then
for i=1,stride do cur[i]=(cur[i]+(((i>bpp and cur[i-bpp]or 0)+prev[i])>>1))&255 end
elseif ft==4 then
for i=1,stride do
local a,b,c=i>bpp and cur[i-bpp]or 0,prev[i],i>bpp and prev[i-bpp]or 0
local pp=a+b-c
local pa,pb,pc=math.abs(pp-a),math.abs(pp-b),math.abs(pp-c)
cur[i]=(cur[i]+((pa<=pb and pa<=pc)and a or(pb<=pc and b or c)))&255
end
end
sink.row(y,px)
prev=cur
y=y+1
end
pend=sub(pend,off)
end
inflateStream(table.concat(idat),onBytes,yield,(stride+1)*h)
return sink.result()
end


local function decodeGIF(d,tw,th,yield)
local w,h=u16le(d,7),u16le(d,9)
local flags=byte(d,11)
local p=14
local gpal
if flags&0x80~=0 then
local n=2<<(flags&7)
gpal=sub(d,p,p+n*3-1)
p=p+n*3
end
local transp
while p<=#d do
local b=byte(d,p)
if b==0x21 then
local label=byte(d,p+1)
p=p+2
if label==0xF9 and byte(d,p+1)&1==1 then transp=byte(d,p+4)end
while byte(d,p)~=0 do p=p+byte(d,p)+1 end
p=p+1
elseif b==0x2C then
local ix,iy,iw,ih,iflags=u16le(d,p+1),u16le(d,p+3),u16le(d,p+5),u16le(d,p+7),byte(d,p+9)
p=p+10
local pal=gpal
if iflags&0x80~=0 then
local n=2<<(iflags&7)
pal=sub(d,p,p+n*3-1)
p=p+n*3
end
local interlaced=iflags&0x40~=0
if interlaced and iw*ih>300000 then return nil,"large interlaced GIF"end
local minSize=byte(d,p)
p=p+1
local chunks={}
while byte(d,p)and byte(d,p)~=0 do
local n=byte(d,p)
chunks[#chunks+1]=sub(d,p+1,p+n)
p=p+n+1
end
local stream=table.concat(chunks)
chunks=nil

local sink=Sink(w,h,tw,th)
local stored=interlaced and{}or nil
local rowOrder={}
if interlaced then
for _,pass in ipairs({{0,8},{4,8},{2,4},{1,2}})do
for yy=pass[1],ih-1,pass[2]do rowOrder[#rowOrder+1]=yy end
end
end
local canvasY=0
local function rgbOf(idx)
if not idx or idx==transp or not pal then return false end
local rr,g,bb=byte(pal,idx*3+1,idx*3+3)
return((rr or 0)<<16)|((g or 0)<<8)|(bb or 0)
end
local function pushCanvasRow(frameRow)

sink.row(canvasY,function(x)
if not frameRow then return false end
local lx=x-ix
if lx<0 or lx>=iw then return false end
return rgbOf(byte(frameRow,lx+1))
end)
canvasY=canvasY+1
end
local done=0
local row,rn={},0
local function rowDone()
local s=char(table.unpack(row,1,rn))
if interlaced then stored[rowOrder[done+1]]=s
else
while canvasY<iy do pushCanvasRow(nil)end
pushCanvasRow(s)
end
done=done+1
rn=0
if yield and done%16==0 then yield()end
end
local function out(v)
rn=rn+1
row[rn]=v
if rn==iw then rowDone()end
end

local clear,eoi=1<<minSize,(1<<minSize)+1
local prefix,suffix,first={},{},{}
for i=0,clear-1 do suffix[i],first[i]=i,i end
local nextCode,size=eoi+1,minSize+1
local prev
local stack={}
local bitpos,total=0,#stream*8
local function emitCode(code)
local k=0
while code>=clear do
k=k+1
stack[k]=suffix[code]
code=prefix[code]
end
out(suffix[code])
for j=k,1,-1 do if done<ih then out(stack[j])end end
end
while bitpos+size<=total and done<ih do
local code=0
for k=0,size-1 do
local bi=bitpos+k
code=code|(((byte(stream,(bi>>3)+1)>>(bi&7))&1)<<k)
end
bitpos=bitpos+size
if code==clear then
nextCode,size,prev=eoi+1,minSize+1,nil
elseif code==eoi then break
else
local firstChar
if code<nextCode and(code<clear or prefix[code]~=nil or code<eoi)then
emitCode(code)
firstChar=first[code]
elseif prev then
emitCode(prev)
if done<ih then out(first[prev])end
firstChar=first[prev]
else break end
if prev and nextCode<4096 then
prefix[nextCode],suffix[nextCode],first[nextCode]=prev,firstChar,first[prev]
nextCode=nextCode+1
if nextCode==(1<<size)and size<12 then size=size+1 end
end
prev=code
end
end
if interlaced then
while canvasY<iy do pushCanvasRow(nil)end
for r=0,ih-1 do pushCanvasRow(stored[r])end
end
while canvasY<h do pushCanvasRow(nil)end
return sink.result()
elseif b==0x3B then break
else p=p+1 end
end
return nil,"GIF without image"
end





local function decodeJPEG(d,tw,th,yield)
local qt,htDC,htAC,comps,w,h={},{},{},{},0,0
local restart=0
local progressive=false
local p=3
local function buildHT(counts,syms)
local t,code,k={},0,1
for l=1,16 do
t[l]={}
for _=1,counts[l]do t[l][code]=syms[k];code=code+1;k=k+1 end
code=code<<1
end
return t
end
while p<#d do
if byte(d,p)~=0xFF then p=p+1 goto continue end
do
local m=byte(d,p+1)
if m==0xD8 or(m>=0xD0 and m<=0xD7)or m==0x01 or m==0xFF then p=p+2 goto continue end
local len=u16be(d,p+2)
local seg=p+4
if m==0xDB then
local q=seg
while q<p+2+len do
local pq,id=byte(d,q)>>4,byte(d,q)&15
local function qv(k)return pq==0 and byte(d,q+1+k)or u16be(d,q+1+k*2)end
qt[id]={qv(0),qv(1),qv(2),qv(4)}
q=q+1+(pq==0 and 64 or 128)
end
elseif m==0xC0 or m==0xC1 or m==0xC2 then
progressive=m==0xC2
h,w=u16be(d,seg+1),u16be(d,seg+3)
local n=byte(d,seg+5)
for i=0,n-1 do
local o=seg+6+i*3
comps[#comps+1]={id=byte(d,o),hs=byte(d,o+1)>>4,vs=byte(d,o+1)&15,tq=byte(d,o+2)}
end
elseif m==0xC3 or(m>=0xC5 and m<=0xCF and m~=0xC8 and m~=0xCC)then
return nil,"lossless/arithmetic JPEG"
elseif m==0xC4 then
local q=seg
while q<p+2+len do
local tc,th2=byte(d,q)>>4,byte(d,q)&15
local counts,total={},0
for l=1,16 do counts[l]=byte(d,q+l);total=total+counts[l]end
local syms={byte(d,q+17,q+16+total)}
if tc==0 then htDC[th2]=buildHT(counts,syms)else htAC[th2]=buildHT(counts,syms)end
q=q+17+total
end
elseif m==0xDD then
restart=u16be(d,seg)
elseif m==0xDA then
local ns=byte(d,seg)
for i=0,ns-1 do
local cid,tb=byte(d,seg+1+i*2),byte(d,seg+2+i*2)
for _,c in ipairs(comps)do if c.id==cid then c.td,c.ta=tb>>4,tb&15 end end
end
local ss=byte(d,seg+1+ns*2)
local ahal=byte(d,seg+3+ns*2)
local al=ahal&15
if progressive and(ss~=0 or(ahal>>4)~=0 or ns~=#comps)then
p=p+2+len
while p<#d and not(byte(d,p)==0xFF and byte(d,p+1)~=0 and not(byte(d,p+1)>=0xD0 and byte(d,p+1)<=0xD7))do p=p+1 end
goto continue
end
p=p+2+len
local hmax,vmax=1,1
for _,c in ipairs(comps)do hmax=math.max(hmax,c.hs);vmax=math.max(vmax,c.vs)end
local mcux,mcuy=(w+8*hmax-1)//(8*hmax),(h+8*vmax-1)//(8*vmax)
local S=progressive and 1 or 2
local sw,sh=(w*S+7)//8,(h*S+7)//8
local sink=Sink(sw,sh,tw,th)
for _,c in ipairs(comps)do c.bw=mcux*c.hs;c.pred=0 end
local bitbuf,bitcnt=0,0
local function fill()
local b=byte(d,p)
if not b then bitbuf=bitbuf<<8;bitcnt=bitcnt+8 return end
if b==0xFF then
local nb=byte(d,p+1)
if nb==0 then p=p+2
else bitbuf=bitbuf<<8;bitcnt=bitcnt+8 return end
else p=p+1 end
bitbuf=((bitbuf<<8)|b)&0xFFFFFFFF
bitcnt=bitcnt+8
end
local function getbit()
if bitcnt==0 then fill()end
bitcnt=bitcnt-1
return(bitbuf>>bitcnt)&1
end
local function receive(n)
local v=0
for _=1,n do v=(v<<1)|getbit()end
return v
end
local function extend(v,n)if n==0 then return 0 end if v<(1<<(n-1))then return v-(1<<n)+1 end return v end
local function huff(t)
local code=0
for l=1,16 do
code=(code<<1)|getbit()
local s=t[l][code]
if s then return s end
end
return 0
end
local function clamp(x)x=math.floor(x+0.5)return x<0 and 0 or x>255 and 255 or x end
local mcus,y=0,0
for my=0,mcuy-1 do

for _,c in ipairs(comps)do c.band={}end
for mx=0,mcux-1 do
if restart>0 and mcus>0 and mcus%restart==0 then
bitcnt=0
while p<#d and not(byte(d,p)==0xFF and byte(d,p+1)>=0xD0 and byte(d,p+1)<=0xD7)do p=p+1 end
p=p+2
for _,c in ipairs(comps)do c.pred=0 end
end
for _,c in ipairs(comps)do
local rowLen=c.bw*S
for by=0,c.vs-1 do
for bx=0,c.hs-1 do
local s=huff(htDC[c.td])
c.pred=c.pred+extend(receive(s),s)
local a1,a2,a4=0,0,0
local k=progressive and 64 or 1
while k<64 do
local rs=huff(htAC[c.ta])
local r,sz=rs>>4,rs&15
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 k==1 then a1=v elseif k==2 then a2=v elseif k==4 then a4=v end
k=k+1
end
end
local q=qt[c.tq]or{1,1,1,1}
local dc=(c.pred<<(progressive and al or 0))*q[1]/8+128
local bxAll=mx*c.hs+bx
if S==1 then
c.band[by*rowLen+bxAll]=dc
else
local h1,v1,d1=a1*q[2]/8,a2*q[3]/8,a4*q[4]/8
local base=(by*2)*rowLen+bxAll*2
c.band[base]=dc+h1+v1+d1
c.band[base+1]=dc-h1+v1-d1
c.band[base+rowLen]=dc+h1-v1-d1
c.band[base+rowLen+1]=dc-h1-v1+d1
end
end
end
end
mcus=mcus+1
end

for ry=0,vmax*S-1 do
if y>=sh then break end
sink.row(y,function(x)
local Y,Cb,Cr
for i,c in ipairs(comps)do
local cx,cy=x*c.hs//hmax,ry*c.vs//vmax
local v=c.band[cy*c.bw*S+cx]or 128
if i==1 then Y=v elseif i==2 then Cb=v else Cr=v end
end
if not Cb then local g=clamp(Y)return(g<<16)|(g<<8)|g end
local r=clamp(Y+1.402*(Cr-128))
local g=clamp(Y-0.344136*(Cb-128)-0.714136*(Cr-128))
local b=clamp(Y+1.772*(Cb-128))
return(r<<16)|(g<<8)|b
end)
y=y+1
end
if yield then yield()end
end
for _,c in ipairs(comps)do c.band=nil end
return sink.result()
elseif m==0xD9 then break end
p=p+2+len
end
::continue::
end
return nil,"JPEG without image data"
end

function M.decode(d,tw,th,yield)
local w,h,fmt=M.size(d)
if not w then return nil,fmt and(fmt.." is not supported")or"unknown image format"end
if w*h>4096*4096 then return nil,"image too large"end
local function run(y)
if fmt=="png"then return decodePNG(d,tw,th,y)
elseif fmt=="gif"then return decodeGIF(d,tw,th,y)
elseif fmt=="jpeg"or fmt=="jpeg-progressive"then return decodeJPEG(d,tw,th,y)
end
return nil,fmt.." is not supported"
end



local co=coroutine.create(function()return run(yield and coroutine.yield or nil)end)
while true do
local ok,a,b=coroutine.resume(co)
if not ok then return nil,tostring(a)end
if coroutine.status(co)=="dead"then return a,b end
if yield then yield()end
end
end

return M