#define __STDC_CONSTANT_MACROS
extern "C" {
}
#include <libswscale/swscale.h>
#include <libavcodec/avcodec.h>
#include <libavformat/avformat.h>

extern URLProtocol ff_file_protocol;
extern AVInputFormat ff_bink_demuxer;
extern AVCodec ff_bink_decoder;
//extern AVCodec ff_binkaudio_dct_decoder;
//extern AVCodec ff_binkaudio_rdft_decoder;

#include <math.h>

//#define SCALE_METHOD SWS_POINT
#define SCALE_METHOD    SWS_LANCZOS

struct Vector
{
    double d[3];

    Vector operator- ( const Vector& b) const
        { Vector result = {{ d[0]-b.d[0], d[1]-b.d[1], d[2]-b.d[2] }}; return result; }

    bool operator==( const Vector& b) const
        { return d[0]==b.d[0] && d[1]==b.d[1] && d[2]==b.d[2]; }

    void operator+=( const Vector& b)
        { for(unsigned n=0; n<3; ++n) d[n] += b.d[n]; }

    inline double Dot(const Vector& b) const
    { return d[0]*b.d[0] + d[1]*b.d[1] + d[2]*b.d[2]; }
    inline double Squared() const     { return Dot(*this); }
    inline double Luma() const
    { return d[0]*0.299 + d[1]*0.587 + d[2]*0.114; }
    Vector Pow(double b) const
    { Vector tmp = {{ pow(d[0],b), pow(d[1],b), pow(d[2],b) }}; return tmp; }

    void Clamp()
    {
        for(unsigned n=0; n<3; ++n)
            /**/ if(d[n] < 0.0) d[n] = 0.0;
            else if(d[n] > 1.0) d[n] = 1.0;
    }
};
class KDTree
{
    static const unsigned K = 3;
private:
    struct KDRect
    {
        Vector min, max;
        Vector bound(const Vector& t) const
        {
            Vector p;
            for(unsigned i=0; i<K; ++i)
                /**/ if(t.d[i] <= min.d[i]) p.d[i] = min.d[i];
                else if(t.d[i] >= max.d[i]) p.d[i] = max.d[i];
                else                        p.d[i] = t.d[i];
            return p;
        }
        void MakeInfinite()
        {
            for(unsigned i=0; i<K; ++i)
            {
                min.d[i] = -1e99;
                max.d[i] =  1e99;
            }
        }
    };
    struct KDNode
    {
        Vector        k;
        unsigned char v;
        KDNode        *lt, *rt;
    public:
        KDNode() : k(), v(), lt(0),rt(0) { }
        KDNode(const Vector& kk, unsigned char vv) : k(kk), v(vv), lt(0), rt(0) { }
        virtual ~KDNode() { delete lt; delete rt; }
        static KDNode* ins(const Vector& key, unsigned val, KDNode*& t, int lev)
        {
            if(!t) return (t = new KDNode(key, val));
            else if(key == t->k) return 0; // key dupliate
            else if(key.d[lev] > t->k.d[lev])
                return ins(key, val, t->rt, (lev+1)%K);
            else
                return ins(key, val, t->lt,  (lev+1)%K);
        }
        struct Nearest
        {
            const KDNode* kd;
            double        dist_sqd;
        };
        // Method Nearest Neighbor from Andrew Moore's thesis. Numbered
        // comments are direct quotes from there. Step "SDL" is added to
        // make the algorithm work correctly.
        static void nnbr(const KDNode* kd, const Vector& target,
                         KDRect& hr, // in-param and a temporary
                         int lev, Nearest& nearest)
        {
            // 1. if kd is empty then set dist-sqd to infinity and exit.
            if (!kd) return;

            // 2. s := split field of kd
            int s = lev % K;

            // 3. pivot := dom-elt field of kd
            const Vector& pivot = kd->k;
            double pivot_to_target = (pivot-target).Squared();

            // 4. Cut hr into to sub-hyperrectangles lt-hr and rt-hr.
            //    The cut plane is through pivot and perpendicular to the s
            //    dimension.
            KDRect& lt_hr = hr; // optimize by not cloning
            KDRect rt_hr = hr;
            lt_hr.max.d[s]  = pivot.d[s];
            rt_hr.min.d[s] = pivot.d[s];

            // 5. target-in-lt := target_s <= pivot_s
            bool target_in_lt = target.d[s] < pivot.d[s];

            const KDNode* nearer_kd;  KDRect nearer_hr;
            const KDNode* further_kd; KDRect further_hr;

            // 6. if target-in-lt then nearer is lt, further is rt
            if (target_in_lt) {
                nearer_kd = kd->lt;   further_kd = kd->rt;
                nearer_hr = lt_hr;    further_hr = rt_hr;
            }
            // 7. if not target-in-lt then nearer is rt, further is lt
            else {
                nearer_kd = kd->rt;  further_kd = kd->lt;
                nearer_hr = rt_hr;   further_hr = lt_hr;
            }

            // 8. Recursively call Nearest Neighbor with parameters
            //    (nearer-kd, target, nearer-hr, max-dist-sqd), storing the
            //    results in nearest and dist-sqd
            nnbr(nearer_kd, target, nearer_hr, lev + 1, nearest);

            // 10. A nearer point could only lie in further-kd if there were some
            //     part of further-hr within distance sqrt(max-dist-sqd) of
            //     target.  If this is the case then
            const Vector closest = further_hr.bound(target);
            if ((closest-target).Squared() < nearest.dist_sqd)
            {
                // 10.1 if (pivot-target)^2 < dist-sqd then
                if (pivot_to_target < nearest.dist_sqd)
                {
                    // 10.1.1 nearest := (pivot, range-elt field of kd)
                    nearest.kd = kd;
                    // 10.1.2 dist-sqd = (pivot-target)^2
                    nearest.dist_sqd = pivot_to_target;
                }

                // 10.2 Recursively call Nearest Neighbor with parameters
                //      (further-kd, target, further-hr, max-dist_sqd)
                nnbr(further_kd, target, further_hr, lev + 1, nearest);
            }
            // SDL: otherwise, current point is nearest
            else if (pivot_to_target < nearest.dist_sqd)
            {
                nearest.kd       = kd;
                nearest.dist_sqd = pivot_to_target;
            }
        }
    private:
        void operator=(const KDNode&);
        KDNode(const KDNode&);
    };
private:
    KDNode* m_root;
public:
    KDTree() : m_root(0) { }
    virtual ~KDTree() { delete m_root; }
    void insert(const Vector& k, unsigned v) { KDNode::ins(k,v,m_root,0); }
    unsigned nearest(const Vector& key) const
    {
        KDRect hr; hr.MakeInfinite();
        KDNode::Nearest nn = { 0, 1e99 };
        KDNode::nnbr(m_root, key, hr, 0, nn);
        return nn.kd ? nn.kd->v : 4;
    }
private:
    void operator=(const KDTree&);
    KDTree(const KDTree&);
};

#include <pc.h>
#include <go32.h>
#include <dpmi.h>
#include <conio.h>
#include <sys/farptr.h>

namespace PC
{
    const unsigned W = 320, H = 200;

    namespace Dither
    {
        // Declarations for the 8x8 Knoll-Yliluoma dithering
        const unsigned CandCount = 16, MaxColors = 253;
        const double Gamma = 2.2;
        unsigned Dither8x8[8][8];
        KDTree PalTree;
        Vector PalG[MaxColors];
        unsigned luma[MaxColors];
        static Vector MakeVGAcolor(double r,double g,double b)
        {
            Vector result = { { r, g, b } };
            outportb(0x3C9, (int)(r*63.9));
            outportb(0x3C9, (int)(g*63.9));
            outportb(0x3C9, (int)(b*63.9));
            return result;
        }
        static void Init()
        {
            // Create a 256-color VGA palette.
            outportb(0x3C8, 0); // Begin programming the VGA.
            Vector Pal[MaxColors];
            unsigned p=0;
            static const int sectiontable[10] =
                {0200,0210,0220,0020,0022,0012,0002,0102,0202,0201};
            // Create a wide selection of colors with different
            // saturation levels and different brightness levels.
            Pal[p++] = MakeVGAcolor(0,0,0); // Black
            Pal[p++] = MakeVGAcolor(1,1,1); // White
            Pal[p++] = MakeVGAcolor(0x4B/255.0, 0x90/255.0, 0xA4/255.0);
            // ^Aperture Science cyan
            for(int sat=0; sat<5; ++sat)
                for(int section=0; section<10; ++section)
                    for(int bright=0; bright<5; ++bright)
                    {
                        double gray = (sat<2 ? (2+bright) / 6.0 : (1+bright) / 5.0);
                        Vector c = { { gray * ((sectiontable[section]>>6)&3)/2,
                                       gray * ((sectiontable[section]>>3)&3)/2,
                                       gray * ((sectiontable[section]>>0)&3)/2 } };
                        double luma = sat==3?gray:c.Luma();
                        double satfactor = sat==3?0.2:pow((sat+1) / 5.0, 1.5);
                        if(p >= MaxColors) abort();
                        Pal[p++] = MakeVGAcolor(luma + (c.d[0]-luma) * satfactor,
                                                luma + (c.d[1]-luma) * satfactor,
                                                luma + (c.d[2]-luma) * satfactor);
                    }
            for(unsigned i=0; i<MaxColors; ++i)
            {
                PalG[i] = Pal[i].Pow(Gamma);
                luma[i] = Pal[i].Luma()*2e7;
                PalTree.insert(PalG[i], i);
            }
            // Create bayer dithering matrix, adjusted for candidate count
            for(unsigned y=0; y<8; ++y)
                for(unsigned x=0; x<8; ++x)
                {
                    unsigned i = x ^ y, j;
                    j = (x & 4)/4u + (x & 2)*2u + (x & 1)*16u;
                    i = (i & 4)/2u + (i & 2)*4u + (i & 1)*32u;
                    Dither8x8[y][x] = (j+i)*CandCount/64u;
                }
            // Render the color table on screen for user to ogle at
            for(unsigned y=0; y<H; ++y)
                for(unsigned x=0; x<MaxColors; ++x)
                    _farpokeb(_dos_ds, 0xA0000+y*W+x, x);
        }
        struct Result
        {
            unsigned char candlist[CandCount];
            void Make(uint32_t rgb)
            {
                Vector in = { { ((rgb>>16)&0xFF)/255.0,
                                ((rgb>> 8)&0xFF)/255.0,
                                ((rgb>> 0)&0xFF)/255.0 } };
                Vector inG = in.Pow(Gamma), qtryG = inG;
                for(unsigned i=0; i<CandCount; ++i)
                {
                    // Find closest match from palette
                    unsigned k = PalTree.nearest(qtryG);
                    candlist[i] = k;
                    if(i+1 >= CandCount) break;
                    // Compensate for error
                    qtryG += (inG - PalG[k]);
                    qtryG.Clamp();
                }
                // Order candidates by luminosity, using insertion sort.
                for(unsigned j=1; j<CandCount; ++j)
                {
                    unsigned k = candlist[j], i;
                    for(i=j; i>=1 && luma[candlist[i-1]] > luma[k]; --i)
                        candlist[i] = candlist[i-1];
                    candlist[i] = k;
                }
            }
        };
        static unsigned Dither(unsigned x,unsigned y, uint32_t rgb)
        {
            Result res; res.Make(rgb);
            // Plot pixel to the frame buffer.
            return res.candlist[Dither8x8[x & 7][y & 7]];
        }
    }
    static const int TickRate = 173;
    unsigned long BIOStimer_begin;
    static unsigned ReadTimer()
    {
        return _farpeekl(_dos_ds, 0x46C);
    }
    void Init()
    {
        unsigned TimerPeriod = 0x1234DDul / TickRate;
        BIOStimer_begin = ReadTimer();
        outportb(0x43, 0x34);
        outportb(0x40, TimerPeriod & 0xFF);
        outportb(0x40, TimerPeriod >>   8);
        __dpmi_regs regs = { };
        regs.x.ax = 0x13; // set mode 13h
        __dpmi_int(0x10, &regs);
        Dither::Init();
    }
    void Close()
    {
        // Fix the skewed clock and reset BIOS tick rate
        _farpokel(_dos_ds, 0x46C, BIOStimer_begin +
            (ReadTimer() - BIOStimer_begin)
            * (0x1234DD/65536.0) / TickRate );
        outportb(0x43, 0x34);
        outportb(0x40, 0);
        outportb(0x40, 0);
        textmode(C80); // set textmode again
    }
    void PutFrame(const uint32_t* rgbframe)
    {
        _farsetsel(_dos_ds);
        for(unsigned y=0; y<H; ++y)
            for(unsigned o=y*W, x=0; x<W; ++x,++o)
                _farnspokeb(0xA0000+o, Dither::Dither(x,y, rgbframe[o]) );
    }
}

int main(int argc, char** argv)
{
    av_register_protocol2(&ff_file_protocol, sizeof(ff_file_protocol));
    av_register_input_format(&ff_bink_demuxer);
    avcodec_register(&ff_bink_decoder);
    //avcodec_register(&ff_binkaudio_dct_decoder);
    //avcodec_register(&ff_binkaudio_rdft_decoder);

    printf("codecs registered\n"); fflush(stdout);

    AVFormatContext* ic;
    int o = av_open_input_file(
        &ic, argv[1],
        &ff_bink_demuxer,
        16384, 0);

    printf("file opened 1, gets %d\n", o); fflush(stdout);
    if(o < 0) { perror(argv[1]); return -1; }

    av_find_stream_info(ic);

    AVCodec* decoder;
    int streamnumber = av_find_best_stream(ic, AVMEDIA_TYPE_VIDEO,
                                           -1, -1, &decoder, 0);
    AVCodecContext* ctx = ic->streams[streamnumber]->codec;
    printf("stream %d selected\n", streamnumber); fflush(stdout);

    double timebase = av_q2d(ic->streams[streamnumber]->time_base);
    printf("fps = %8.3f\n", 1.0 / timebase);
    timebase *= PC::TickRate;

    uint8_t bink_extradata[4] = { 0 } ;
    ctx->extradata      = bink_extradata;
    ctx->extradata_size = sizeof(bink_extradata);
    int a = avcodec_open(ctx, decoder);
    printf("ctx=%p, decoder=%p, a=%d\n", ctx,decoder, a); fflush(stdout);

    AVPacket packet;
    av_init_packet(&packet);
    AVFrame* frame = avcodec_alloc_frame();
    avcodec_default_get_buffer(ctx, frame);

    printf("Input video size: %dx%d\n", ctx->width, ctx->height);
    SwsContext* sws = sws_getCachedContext(0,
        ctx->width, ctx->height, ctx->pix_fmt,
        PC::W, PC::H, PIX_FMT_RGB32,
        SCALE_METHOD, 0,0,0);

    PC::Init();

    long begin_time = PC::ReadTimer();
    while(!kbhit())
    {
        int r = av_read_frame(ic, &packet);
        if(r < 0) break;
        if(packet.stream_index == streamnumber)
        {
            int pic_ptr = 0;
            avcodec_decode_video2(ctx, frame, &pic_ptr, &packet);
            long wait_until = begin_time + packet.pts * timebase;

            while(PC::ReadTimer() < wait_until)
                { __asm__ volatile("hlt"); }

            uint32_t dst[PC::W * PC::H] = { 0 };
            uint8_t* slices[3] = {(uint8_t*)&dst[0], 0, 0};
            int      strides[3] = {PC::W*4, 0, 0};

            sws_scale(sws, frame->data, frame->linesize, 0, ctx->height,
                      slices, strides);
            // Decoded RGB frame is now in dst[]
            PC::PutFrame(dst);
        }
    }

    PC::Close();

    avcodec_default_release_buffer(ctx, frame);
    av_free(frame);
    av_destruct_packet(&packet);

    decoder->close(ctx);
    av_free(ctx);

    return 0;
}