#!/usr/bin/env python3
"""ff2dec.py - independent farbfeld v2 decoder, written from /farbfeld/spec/ to check that the spec is enough.
Slow (pure Python) and meant for small files.
  python3 ff2dec.py in.ff out.raw     # frames concatenated; 8-bit RGBA, or 16-bit big-endian RGBA for kind 5
Prints: kind width height frames loops delays_cs"""
import sys

SQT = [1, 2, 3, 6, 10, 16, 27, 45, 73, 120, 194, 310, 488, 747, 1101, 1546, 2047, 2549, 2994, 3348, 3607, 3785,
       3901, 3975, 4022, 4050, 4068, 4079, 4085, 4089, 4092, 4093, 4094]

def squash(d):
    if d > 2047: return 4095
    if d < -2047: return 0
    w = d & 127
    i = (d >> 7) + 16
    return (SQT[i] * (128 - w) + SQT[i + 1] * w + 64) >> 7

STR = [0] * 4096
_pi = 0
for _x in range(-2047, 2048):
    _v = squash(_x)
    for _i in range(_pi, _v + 1): STR[_i] = _x
    _pi = _v + 1
for _j in range(_pi, 4096): STR[_j] = 2047

RA, RB, NIN, LR, W0 = 4, 8, 7, 6, 11000

class Slots:                       # model slots: two counters each
    def __init__(self, n): self.a = [32768] * n; self.b = [32768] * n
    def p(self, i):
        v = (self.a[i] + self.b[i]) >> 5
        return 1 if v < 1 else 4095 if v > 4095 else v
    def upd(self, i, bit):
        if bit: self.a[i] -= self.a[i] >> RA; self.b[i] -= self.b[i] >> RB
        else: self.a[i] += (65536 - self.a[i]) >> RA; self.b[i] += (65536 - self.b[i]) >> RB

def c12(v):
    v >>= 4
    return 1 if v < 1 else 4095 if v > 4095 else v

class Mixer:
    def __init__(self, nsets):
        self.w = [W0 if j < 6 else 0 for _ in range(nsets) for j in range(NIN)]
        self.st = [0] * NIN; self.p = 2048

class Dec:
    def __init__(self, data, pos):
        self.d = data; self.pos = pos; self.range = 0xFFFFFFFF; self.code = 0
        for _ in range(4): self.code = ((self.code << 8) | self.nx()) & 0xFFFFFFFF
    def nx(self):
        b = self.d[self.pos] if self.pos < len(self.d) else 0
        self.pos += 1
        return b
    def _norm(self):
        while self.range < (1 << 24):
            self.range = (self.range << 8) & 0xFFFFFFFF
            self.code = ((self.code << 8) | self.nx()) & 0xFFFFFFFF
    def _bit(self, p):
        bound = (self.range >> 12) * p
        if self.code < bound: self.range = bound; b = 0
        else: self.code -= bound; self.range -= bound; b = 1
        self._norm()
        return b
    def bit(self, m, i):
        b = self._bit(m.p(i)); m.upd(i, b); return b
    def bitm(self, mx, ws, m1, i1, m2, i2, m3, i3):
        st = mx.st; o = ws * NIN; w = mx.w
        st[0] = STR[c12(m1.a[i1])]; st[1] = STR[c12(m1.b[i1])]; st[2] = STR[c12(m2.a[i2])]
        st[3] = STR[c12(m2.b[i2])]; st[4] = STR[c12(m3.a[i3])]; st[5] = STR[c12(m3.b[i3])]; st[6] = 256
        dot = 0
        for k in range(NIN): dot += st[k] * w[o + k]
        p = squash(dot >> 16); p = 1 if p < 1 else 4095 if p > 4095 else p; mx.p = p
        b = self._bit(p)
        err = ((0 if b else 4095) - p) * LR
        for k in range(NIN):
            nw = w[o + k] + ((st[k] * err + 32768) >> 16)
            w[o + k] = -98304 if nw < -98304 else 98304 if nw > 98304 else nw
        m1.upd(i1, b); m2.upd(i2, b); m3.upd(i3, b)
        return b

def tree(rd, M, base):
    node = 1
    for _ in range(8): node = (node << 1) | rd.bit(M, base + node)
    return node & 255

def leb(d, st):
    v = 0; m = 1
    for n in range(5):
        if st[0] >= len(d): raise ValueError('bad header')
        b = d[st[0]]; st[0] += 1
        v += (b & 127) * m; m *= 128
        if not b & 128: return v
    raise ValueError('bad header')

def q8(v, th):                     # index of the first threshold >= v, else 7
    for i, t in enumerate(th):
        if v <= t: return i
    return 7
TQ1 = [0, 2, 5, 10, 20, 40, 80]
TQG = [0, 2, 6, 14, 30, 62, 126]

def make_core(rd, w, h, ch, d, bl, bits, anim):
    mask = 65535 if bits == 16 else 255; S = bits + 1; sh = bits - 8; step = 2 * d + 1; NS = 2 if anim else 1
    U2 = Slots(NS * ch * 64 * S); U = Slots(NS * ch * 24 * S); U3 = Slots(NS * ch * 24 * S)
    M1 = Slots(NS * ch * 8 * S); M2 = Slots(S * bits); MX = Mixer(NS * ch * S)
    E = [[0] * (2 * w) for _ in range(ch)]
    EP = [[[0] * (2 * w) for _ in range(5)] for _ in range(ch)] if bl else None

    def frame(P, Q, bb=None):
        x0, y0, x1, y1 = bb if bb else (0, 0, w, h)
        for c in range(ch):
            E[c][:] = [0] * (2 * w)
            if bl:
                for k in range(5): EP[c][k][:] = [0] * (2 * w)
        for y in range(y0, y1):
            ro = (y & 1) * w; po = ((y + 1) & 1) * w
            for x in range(x0, x1):
                i = y * w + x
                hasL = x > 0; hasU = y > 0; hasUL = hasL and hasU; hasUR = hasU and x < w - 1
                prev_abs = 0
                for c in range(ch):
                    p = P[c]; e = E[c]; pq = Q[c] if Q else None
                    a = p[i - 1] if hasL else (p[i - w] if hasU else 0)
                    b = p[i - w] if hasU else a
                    cc = p[i - w - 1] if hasUL else b
                    mx = max(a, b); mn = min(a, b); g = a + b - cc
                    v0 = mn if cc >= mx else (mx if cc <= mn else g)
                    if bl:
                        v = [v0, a, b, (a + b + 1) >> 1, 0 if g < 0 else mask if g > mask else g]
                        ep = EP[c]; num = 0; den = 0
                        for k in range(5):
                            tk = ep[k]
                            sE = (tk[ro + x - 1] if hasL else 0) + (tk[po + x] if hasU else 0) + (tk[po + x - 1] if hasUL else 0) + (tk[po + x + 1] if hasUR else 0)
                            if k == 0 and sE == 0: num = v0; den = 1; break
                            q4 = (1 + sE) * (1 + sE); W = 1099511627776 // (q4 * q4)
                            num += v[k] * W; den += W
                        pr = (2 * num + den) // (2 * den)
                    else:
                        pr = v0
                    st = 0
                    if pq is not None and (not hasL or p[i - 1] == pq[i - 1]) and (not hasU or p[i - w] == pq[i - w]):
                        st = 1; pr = pq[i]
                    t = 2 * (e[ro + x - 1] if hasL else 0) + 2 * (e[po + x] if hasU else 0) + (e[po + x - 1] if hasUL else 0) + (e[po + x + 1] if hasUR else 0)
                    q1 = q8(t, TQ1); pa = prev_abs >> sh; q2 = 0 if pa == 0 else 1 if pa < 4 else 2
                    qg = q8((abs(a - cc) + abs(b - cc)) >> sh, TQG)
                    sc = st * ch + c
                    qd = q8((abs(a - pr) + abs(b - pr)) >> sh, TQG)
                    ub = ((sc * 8 + q1) * 3 + q2) * S; ub3 = ((sc * 8 + qd) * 3 + q2) * S; ub2 = ((sc * 8 + qg) * 8 + q1) * S
                    kk = 0
                    while kk < bits:
                        if not rd.bitm(MX, sc * S + kk, U, ub + kk, U2, ub2 + kk, U3, ub3 + kk): break
                        kk += 1
                    zz = 0 if kk == 0 else 1 << (kk - 1)
                    for pos in range(kk - 2, -1, -1):
                        bi = rd.bit(M1, (sc * 8 + q1) * S + kk) if pos == kk - 2 else rd.bit(M2, kk * bits + pos)
                        zz |= bi << pos
                    sv = -((zz + 1) >> 1) if zz & 1 else zz >> 1
                    if d:
                        rv = pr + sv * step; p[i] = 0 if rv < 0 else mask if rv > mask else rv
                    else:
                        p[i] = (pr + sv) & mask
                    val = p[i]
                    if bl:
                        vv = v
                        for k in range(5): EP[c][k][ro + x] = min(255, abs(val - vv[k]))
                    prev_abs = abs(sv); e[ro + x] = min(255, prev_abs >> sh)
    return frame

def pal_table(rd, ch, sorted_):
    CM = Slots(256); n = tree(rd, CM, 0) + 1
    PM = Slots(ch * 256); pal = []
    for k in range(n):
        row = []
        for c in range(ch):
            v = tree(rd, PM, c * 256)
            row.append((pal[k - 1][c] + v) & 255 if sorted_ and k else v)
        pal.append(row)
    return n, pal

def make_pal_frame(rd, w, h, n, sorted_):
    EC = [Slots(32) for _ in range(4)]; EN = Slots(32); TI = Slots(256); EV = Slots(8); UD = Slots(60); MD = Slots(100); mx_seen = [-1]
    def frame(I, Q, bb=None):
        x0, y0, x1, y1 = bb if bb else (0, 0, w, h)
        for y in range(y0, y1):
            for x in range(x0, x1):
                i = y * w + x
                a = I[i - 1] if x else (I[i - w] if y else 0)
                b = I[i - w] if y else a
                cc = I[i - w - 1] if x and y else b
                dd = I[i - w + 1] if y and x < w - 1 else b
                ctx = (a == b) | (b == cc) << 1 | (b == dd) << 2 | (a == cc) << 3 | (mx_seen[0] < 0) << 4
                r = -1; pv = -1
                if Q is not None:
                    pv = Q[i]
                    pc = int(I[i - 1] == Q[i - 1] if x else True) | int(I[i - w] == Q[i - w] if y else True) << 1 | int(pv == a) << 2
                    if rd.bit(EV, pc): r = pv
                if r < 0:
                    cand = [a, b, cc, dd]
                    for q in range(4):
                        cv = cand[q]
                        if cv == pv or cv in cand[:q]: continue
                        if rd.bit(EC[q], ctx): r = cv; break
                if r < 0:
                    if sorted_:
                        ab = abs(a - b); cx = 0 if ab == 0 else 1 if ab == 1 else 2 if ab < 4 else 3 if ab < 8 else 4 if ab < 16 else 5
                        kq = 1
                        while kq < 10:
                            if not rd.bit(UD, cx * 10 + kq): break
                            kq += 1
                        mm = 1 << (kq - 1)
                        for pos in range(kq - 2, -1, -1): mm |= rd.bit(MD, kq * 10 + pos) << pos
                        z2 = mm - 1; r = a + (-((z2 + 1) >> 1) if z2 & 1 else (z2 >> 1) + 1)
                    else:
                        r = mx_seen[0] + 1 if rd.bit(EN, ctx) else tree(rd, TI, 0)
                if r < 0 or r >= n: raise ValueError('bad palette index')
                if r > mx_seen[0]: mx_seen[0] = r
                I[i] = r
    return frame

def unzig(z): return -((z + 1) >> 1) if z & 1 else z >> 1

def make_info(rd, w, h):
    CHG = Slots(1); MVF = Slots(1); FULL = Slots(1); MVT = Slots(512); BT = Slots(2048)
    def v16(base): hi = tree(rd, BT, base); lo = tree(rd, BT, base + 256); return (hi << 8) | lo
    def f():
        dx = dy = 0
        if rd.bit(MVF, 0): dx = unzig(tree(rd, MVT, 0)); dy = unzig(tree(rd, MVT, 256))
        if not rd.bit(CHG, 0): return False, dx, dy, None
        if rd.bit(FULL, 0): return True, dx, dy, (0, 0, w, h)
        x0 = v16(0); y0 = v16(512); bw = v16(1024) + 1; bh = v16(1536) + 1
        if x0 + bw > w or y0 + bh > h: raise ValueError('bad frame box')
        return True, dx, dy, (x0, y0, x0 + bw, y0 + bh)
    return f

def shift(src, dx, dy, w, h):
    out = []
    for y in range(h):
        sy = min(max(y - dy, 0), h - 1)
        for x in range(w): out.append(src[sy * w + min(max(x - dx, 0), w - 1)])
    return out

def blit(P, Q, bb, w, h):
    x0, y0, x1, y1 = bb
    for c in range(len(P)):
        for y in range(h):
            for x in range(w):
                if not (y0 <= y < y1 and x0 <= x < x1): P[c][y * w + x] = Q[c][y * w + x]

def delay_reader(rd):
    SD = Slots(2); DT = Slots(512); prev = [10]
    def f():
        if not rd.bit(SD, 0):
            hi = tree(rd, DT, 0); lo = tree(rd, DT, 256); prev[0] = (hi << 8) | lo
        return prev[0]
    return f

def endmark(rd):
    m = Slots(16); v = 0
    for i in range(16): v = (v << 1) | rd.bit(m, i)
    if v != 0xA55A: raise ValueError('truncated or corrupt file')

def lebs(d, st):
    return leb(d, st)

def decode(data):
    if data[0] == 6:                       # optional metadata prefix: skip it
        st = [1]; L = leb(data, st)
        if L > (1 << 24) or st[0] + L > len(data): raise ValueError('bad metadata')
        data = data[st[0] + L:]
    kind = data[0] & 15
    if kind not in (3, 4, 5, 7): raise ValueError('bad kind')
    alpha = (data[0] >> 4) & 1; ispal = (data[0] >> 5) & 1; nl = (data[0] >> 6) & 1; bl = (data[0] >> 7) & 1
    st = [1]; w = leb(data, st); h = leb(data, st); ch = 4 if alpha else 3; n = w * h; F = 1; loops = 0; anim = kind == 4
    if anim: F = leb(data, st); loops = leb(data, st)
    ex = 0
    if kind == 7:
        if st[0] >= len(data): raise ValueError('bad header')
        ex = data[st[0]]; st[0] += 1
        if not 4 <= ex <= 12: raise ValueError('bad tile size')
    if not w or not h or n * F > ((1 << 26) if kind == 7 else (1 << 25)) or (anim and not 0 < F < 65536): raise ValueError('bad size')
    if kind == 5 and (ispal or nl or bl): raise ValueError('bad flags')
    if kind == 7 and ispal: raise ValueError('bad flags')
    if ispal and nl: raise ValueError('bad flags')
    dd = 0
    if nl:
        dd = data[st[0]]; st[0] += 1
        if not 1 <= dd <= 40: raise ValueError('bad near value')
    if kind == 7:
        T = 1 << ex; tx = -(-w // T); ty = -(-h // T)
        if tx * ty > (1 << 20): raise ValueError('too many tiles')
        lens = [leb(data, st) for _ in range(tx * ty)]; pos = st[0]; offs = []
        for L in lens:
            offs.append(pos); pos += L
            if pos > len(data): raise ValueError('truncated')
        out = bytearray(n * 4)
        for k in range(tx * ty):
            x0 = (k % tx) * T; y0 = (k // tx) * T; tw = min(T, w - x0); th = min(T, h - y0); tn = tw * th
            rdt = Dec(data[offs[k]:offs[k] + lens[k]], 0); P = [[0] * tn for _ in range(ch)]
            make_core(rdt, tw, th, ch, dd, bl, 8, False)(P, None); endmark(rdt)
            for j in range(tn):
                g = P[0][j]; r = P[1][j] if nl else (P[1][j] + g) & 255; b = P[2][j] if nl else (P[2][j] + g) & 255
                o = ((y0 + j // tw) * w + x0 + j % tw) * 4
                out[o:o + 4] = bytes((r, g, b, P[3][j] if alpha else 255))
        return kind, w, h, [bytes(out)], [], 0
    rd = Dec(data, st[0]); dl = delay_reader(rd) if anim else None; info = make_info(rd, w, h) if anim else None
    frames = []; delays = []
    if kind == 5:
        P = [[0] * n for _ in range(ch)]; make_core(rd, w, h, ch, 0, 0, 16, False)(P, None); endmark(rd)
        out = bytearray()
        for j in range(n):
            g = P[0][j]; r = (P[1][j] + g) & 65535; b = (P[2][j] + g) & 65535; a = P[3][j] if alpha else 65535
            for v in (r, g, b, a): out += bytes((v >> 8, v & 255))
        return kind, w, h, [bytes(out)], [], loops
    if ispal:
        cnt, pal = pal_table(rd, ch, bl); pf = make_pal_frame(rd, w, h, cnt, bl); prev = None
        for f in range(F):
            if dl: delays.append(dl())
            I = [0] * n
            if f == 0: pf(I, None)
            else:
                chg, dx, dy, bb = info(); Qs = shift(prev, dx, dy, w, h) if dx or dy else prev
                if not chg: I[:] = Qs
                else: blit([I], [Qs], bb, w, h); pf(I, Qs, bb)
            prev = I; out = bytearray()
            for q in range(n):
                c = pal[I[q]]; out += bytes((c[0], c[1], c[2], c[3] if alpha else 255))
            frames.append(bytes(out))
        endmark(rd)
    else:
        core = make_core(rd, w, h, ch, dd, bl, 8, anim); prev = None
        for f in range(F):
            if dl: delays.append(dl())
            P = [[0] * n for _ in range(ch)]
            if f == 0: core(P, None)
            else:
                chg, dx, dy, bb = info(); Qs = [shift(q, dx, dy, w, h) for q in prev] if dx or dy else prev
                if not chg:
                    for c in range(ch): P[c][:] = Qs[c]
                else: blit(P, Qs, bb, w, h); core(P, Qs, bb)
            prev = P; out = bytearray()
            for j in range(n):
                g = P[0][j]
                r = P[1][j] if nl else (P[1][j] + g) & 255; b = P[2][j] if nl else (P[2][j] + g) & 255
                out += bytes((r, g, b, P[3][j] if alpha else 255))
            frames.append(bytes(out))
        endmark(rd)
    return kind, w, h, frames, delays, loops

if __name__ == '__main__':
    data = open(sys.argv[1], 'rb').read()
    kind, w, h, frames, delays, loops = decode(data)
    open(sys.argv[2], 'wb').write(b''.join(frames))
    print(kind, w, h, len(frames), loops, ','.join(map(str, delays)))
