class ZMBV_MKV: public AVI
{
    static const unsigned KeyInt = 30 * 10; //3600;//60;

    int pid, pip[2];

    mk_Writer* mkw;
    mk_Track *mkt_v; mk_TrackConfig mkc_v; bool cfg_v; char mkc_v_buf[40];
    mk_Track *mkt_a; mk_TrackConfig mkc_a; bool cfg_a;
    ZMBV_Codec    zmbv;
    zmbv_format_t format;
    std::vector<unsigned char> vid_buf, pal_frame;

    std::list< std::pair<bool,
                         std::vector<unsigned char>
                        > > pending_video;
    std::list< std::vector<unsigned char> > pending_audio;

    unsigned char previous_palette[256*4];
    unsigned      palette_age[256];
    int auto_palette_active;

    typedef std::map<unsigned,unsigned,
                     std::less<unsigned>,
                     FSBAllocator<int> > palette_search_t;
    palette_search_t palette_search;

    KDTree<unsigned char> palette_tree;
    double                palette_gamma[256][3];
    unsigned              luma_table[256];
    enum { CandCount = 16 };
    struct ncand { unsigned char index[CandCount]; };
    std::map<unsigned, ncand, std::less<unsigned>, FSBAllocator<int> > cache;

    unsigned long long AudioPos;
    unsigned long long VideoPos;
    timeval started_time;
public:
    #define e(call) do { \
         int r = call; \
         if(r) fprintf(stderr, "%s failed: %d\n", #call, r); } while(0)

    ZMBV_MKV() :
        mkw(0),
        mkt_v(0), mkc_v(), cfg_v(false),
        mkt_a(0), mkc_a(), cfg_a(false)
    {
        // hudmaker -> pip2 -> bufferprog -> pipe -> mkv&zmbv
        int pip2[2];
        pipe(pip2);
        pid = fork();
        if(pid)
        {
            close(pip2[0]);
            pip[1] = pip2[1];
            return;
        }
        close(pip2[1]);
        pipe(pip);
        if(!fork())
        {
            // Rename pip2[0] into 0, pip[1] into 1.
            close(pip[0]);
            if(pip[1] == 0) pip[1] = dup(pip[1]); // Ensure stdout is not 0
            if(pip2[0] != 0) { dup2(pip2[0], 0); close(pip2[0]); }
            if(pip[1]  != 1) { dup2(pip[1],  1); close(pip[1]);  }

            // Close everything except 0,1,2.
            for(int q=getdtablesize(),p=3; p<q; ++p) close(p);

            if(nice(-20) < 0) // set maximum priority for bufferprog
                perror("nice"); // doesn't really matter if it fails.
            //execlp("bufferprog", "bufferprog", "1800e6", NULL);
            execlp("bufferprog", "bufferprog", "2e5", NULL);
            _exit(-1);
        }
        close(pip2[0]);
        close(pip[1]);
        for(int q=getdtablesize(),p=0; p<q; ++p) // Close everything except
            if(p != 2 && p != pip[0]) // the pipe and stderr
                close(p);

        nice(-20);
        WaitEvents();
    }
    virtual ~ZMBV_MKV()
    {
        if(pid)
        {
            char a = 'Q';
            FullyWrite(pip[1], &a, 1);
            close(pip[1]);
            waitpid(pid, NULL, 0);
        }
    }

    virtual void AudioPtr
        (unsigned aud_rate, unsigned aud_bits, unsigned aud_chans,
         const unsigned char*d, unsigned nsamples)
    {
        unsigned bytes = nsamples * aud_chans * (aud_bits / 8);
        if(pid)
        {
            char a = 'A';
            FullyWrite(pip[1], &a, 1);
            FullyWrite(pip[1], &aud_rate, sizeof(aud_rate));
            FullyWrite(pip[1], &aud_bits, sizeof(aud_bits));
            FullyWrite(pip[1], &nsamples, sizeof(nsamples));
            FullyWrite(pip[1], &aud_chans, sizeof(aud_chans));
            FullyWrite(pip[1], d, bytes);
            std::free( (void*) d);
            return;
        }
    #if 1
        if(!cfg_a)
        {
            mkc_a.extra.audio.samplingFreq = aud_rate;
            mkc_a.extra.audio.channels     = aud_chans;
            mkc_a.extra.audio.bitDepth     = aud_bits;
            fprintf(stderr, "Begins %u Hz audio\n", aud_rate);
            cfg_a = true;
            mkt_a = mk_createTrack(mkw, &mkc_a);
            if(cfg_v) WriteHeader();
        }
        if(cfg_a && cfg_v)
        {
            while(!pending_audio.empty())
            {
                std::vector<unsigned char>& v = pending_audio.front();
                PutAudioFrame(&v[0], v.size(), v.size() / (bytes/nsamples), aud_rate);
                pending_audio.pop_front();
            }
            PutAudioFrame(d, bytes, nsamples, aud_rate);
        }
        else
        {
            pending_audio.push_back( std::vector<unsigned char> (d, d+bytes) );
        }
    #else
        if(!cfg_a && cfg_v) WriteHeader();
        cfg_a = true;
    #endif
    }

    virtual void VideoPtr
        (unsigned w,unsigned h,unsigned f, const unsigned char*d)
    {
        if(pid)
        {
            unsigned bytes = w * h * ((INPUT_BPP+7)/8);
            char v = 'V';
            FullyWrite(pip[1], &v, 1);
            FullyWrite(pip[1], &w, sizeof(w));
            FullyWrite(pip[1], &h, sizeof(h));
            FullyWrite(pip[1], &f, sizeof(f));
            FullyWrite(pip[1], &INPUT_BPP, sizeof(INPUT_BPP));
            FullyWrite(pip[1], d, bytes);
            std::free( (void*) d);
            return;
        }
        if(!cfg_v)
        {
            mkc_v.extra.video.pixelWidth = w;
            mkc_v.extra.video.pixelHeight = h;
            mkc_v.extra.video.displayWidth  = w;
            mkc_v.extra.video.displayHeight = h;
            mkc_v.extra.video.aspectRatioType = MK_ASPECTRATIO_FIXED;
            cfg_v = true;
            mkt_v = mk_createTrack(mkw, &mkc_v);

            format        = zmbv.BPPFormat(INPUT_BPP);
            vid_buf.resize( zmbv.NeededSize(w,h, ZMBV_FORMAT_32BPP) );
            e(!zmbv.SetupCompress(w,h));

            fprintf(stderr, "Begins %u x %u video, bpp %u, zmbv format %u\n",
                w,h, (unsigned)INPUT_BPP,(unsigned)format);

            if(cfg_a) WriteHeader();
        }

        std::pair<bool,size_t> frameinfo = CompressZMBV(d, w,h, f);
        bool make_keyframe = frameinfo.first;
        size_t gotsize     = frameinfo.second;

        typedef std::pair<bool, std::vector<unsigned char> > pending_frame_t;

        if(cfg_a && cfg_v)
        {
            while(!pending_video.empty())
            {
                pending_frame_t& v = pending_video.front();
                PutVideoFrame( &v.second[0], v.second.size(), f,v.first);
                pending_video.pop_front();
            }
            PutVideoFrame(&vid_buf[0], gotsize, f, make_keyframe);
        }
        else
        {
            pending_video.push_back(
                pending_frame_t(
                    make_keyframe,
                    std::vector<unsigned char> (&vid_buf[0], &vid_buf[0]+gotsize) ) );
        }
    }
private:
    void WaitEvents()
    {
        memset(&previous_palette, 0, sizeof(previous_palette));
        memset(&palette_age,      0, sizeof(palette_age));
        /*  */
        memset(&mkc_v, 0, sizeof(mkc_v));
        mkc_v.trackType  = MK_TRACK_VIDEO;
        mkc_v.flagLacing = MK_LACING_NONE;
        mkc_v.flagEnabled = 1;
        mkc_v.flagDefault = 1;
        mkc_v.defaultDuration = (6551711.0 / 39375000.0) * 1e9;
        mkc_v.name = 0;
        mkc_v.codecID   = "V_MS/VFW/FOURCC";
        mkc_v.codecName = "ZMBV";
        memcpy(mkc_v_buf+16, CODEC_4CC, 4); // MPlayer looks for fourcc in this offset
        mkc_v.codecPrivate     = mkc_v_buf;
        mkc_v.codecPrivateSize = 40;    // MPlayer requires at least this much

        /*  */
        memset(&mkc_a, 0, sizeof(mkc_a));
        mkc_a.trackType  = MK_TRACK_AUDIO;
        mkc_a.flagLacing = MK_LACING_NONE;
        mkc_a.flagEnabled = 1;
        mkc_a.flagDefault = 1;
        mkc_a.defaultDuration = 0;//(1/60.0) * 1e9;
        mkc_a.name = 0;
        mkc_a.codecID  = MK_ACODEC_PCMINTLE;

        AudioPos = 0;
        VideoPos = 0;
        gettimeofday(&started_time, NULL);
        auto_palette_active = 2;

        const char* const v = VIDEO_CMD.c_str() + 4;
        mkw = mk_createWriter(v, 1000000, 1);
        fprintf(stderr, "pid %d, mkv writer initialized: %p [%s]\n",
            (int) getpid(),
            mkw, v);

        while(!Terminate)
        {
            char c = 'Q';
            FullyRead(pip[0], &c, 1);
            switch(c)
            {
                case 'A':
                {
                    unsigned aud_rate, aud_bits, nsamples, aud_chans;
                    FullyRead(pip[0], &aud_rate, sizeof(aud_rate));
                    FullyRead(pip[0], &aud_bits, sizeof(aud_bits));
                    FullyRead(pip[0], &nsamples, sizeof(nsamples));
                    FullyRead(pip[0], &aud_chans, sizeof(aud_chans));
                    unsigned bytes = nsamples * aud_chans * (aud_bits / 8);
                    std::vector<unsigned char> d( bytes );
                    FullyRead(pip[0], &d[0], bytes);
                    AudioPtr(aud_rate,aud_bits,aud_chans, &d[0], nsamples);
                    break;
                }
                case 'V':
                {
                    unsigned w,h,f;
                    FullyRead(pip[0], &w, sizeof(w));
                    FullyRead(pip[0], &h, sizeof(h));
                    FullyRead(pip[0], &f, sizeof(f));
                    FullyRead(pip[0], &INPUT_BPP, sizeof(INPUT_BPP));
                    unsigned bytes = w * h * ((INPUT_BPP+7)/8);
                    std::vector<unsigned char> d( bytes );
                    FullyRead(pip[0], &d[0], bytes);
                    VideoPtr(w,h,f, &d[0]);
                    break;
                }
                case 'Q':
                {
                    Terminate = true;
                    break;
                }
                default:
                    fprintf(stderr, "Unknown data in pipe: %c (%02X)\n", c, (unsigned char) c);
            }
        }

        fprintf(stderr, "Closing MKV file\n");
        mk_close(mkw);
        close(pip[0]);
        _exit(0);
    }

    std::pair<bool,size_t> CompressZMBV(const unsigned char* d, unsigned w,unsigned h, unsigned fps_scaled)
    {
        #define dith(input, inmax, outmax) \
            ( (input) * qmax * outmax + (inmax+1)*q ) / (inmax*qmax)
        enum { qmax = 32*32 };
        static int q32x32[ 32*32 ], q4x4[4*4];
        static bool first = true;
        if(first)
        {
            first = false;
            for(unsigned y=0; y<32; ++y)
                for(unsigned x=0; x<32; ++x)
                {
                    unsigned M=5, L=5, v=0, offset=0, xmask=M, ymask=L;
                    unsigned xc = x, yc = y ^ (x<<L>>M);
                    for(unsigned bit=0; bit < M+L; )
                    {
                        v |= ((xc >> --xmask)&1) << bit++;
                        for(offset += L; offset >= M; offset -= M)
                            v |= ((yc >> --ymask)&1) << bit++;
                    }
                    fprintf(stderr, "%5d", v);
                    q32x32[y*32+x] = v;
                    if(x==31) fprintf(stderr,"\n");
                }
            for(unsigned y=0; y<4; ++y)
                for(unsigned x=0; x<4; ++x)
                {
                    unsigned M=2, L=2, v=0, offset=0, xmask=M, ymask=L;
                    unsigned xc = x, yc = y ^ (x<<L>>M);
                    for(unsigned bit=0; bit < M+L; )
                    {
                        v |= ((xc >> --xmask)&1) << bit++;
                        for(offset += L; offset >= M; offset -= M)
                            v |= ((yc >> --ymask)&1) << bit++;
                    }
                    fprintf(stderr, "%5d", v);
                    q4x4[y*4+x] = v;
                    if(x==3) fprintf(stderr,"\n");
                }
        }

        double time = VideoPos * 16777216. / fps_scaled;

        bool make_keyframe = (VideoPos % KeyInt) == 0 || VideoPos == 60 || VideoPos == 71;

        unsigned actual_bpp = INPUT_BPP;
        unsigned num_pixels = w * h;
        if(INPUT_BPP == 16 || INPUT_BPP == 32 || INPUT_BPP == 24)
        {
            bool paletted_okay = true;

            // Figure out which colors are repsent in the palette.
            typedef std::set<unsigned, std::less<unsigned>,
                             FSBAllocator<int> > palette_contents_t;
            palette_contents_t this_frame_used_colors;
            size_t num_colors = 0;

            #define PIX16at(a) (((const unsigned short*)d)[a])
            #define PIX32at(a) (((const unsigned      *)d)[a])
            #define PIX24at(a) (0xFFFFFF & *(const unsigned *)&d[a*3])

            if(INPUT_BPP == 16)
            {
                for(unsigned a=0; a<num_pixels; ++a)
                    if(this_frame_used_colors.insert(PIX16at(a)) . second)
                    {
                        ++num_colors;
                        if(num_colors > 256) // Too many distinct colors?
                            { paletted_okay = false; break; }
                    }
            }
            else if(INPUT_BPP == 32)
            {
                for(unsigned a=0; a<num_pixels; ++a)
                    if(this_frame_used_colors.insert(PIX32at(a)) . second)
                    {
                        ++num_colors;
                        if(num_colors > 256) // Too many distinct colors?
                            { paletted_okay = false; break; }
                    }
            }
            else if(INPUT_BPP == 24)
            {
                for(unsigned a=0; a<num_pixels; ++a)
                    if(this_frame_used_colors.insert(PIX24at(a)) . second)
                    {
                        ++num_colors;
                        if(num_colors > 256) // Too many distinct colors?
                            { paletted_okay = false; break; }
                    }
            }

            //goto Now24bpp;
            if(!paletted_okay)
            {
                // Convert to 24bpp format, and go to generic-palettizer
                static std::vector<unsigned char> frame;
                frame.resize(w*h*3);
                if(INPUT_BPP == 16)
                {
                    Convert16To24Frame(d, &frame[0], w*h, false);
                    d = &frame[0];
                }
                else if(INPUT_BPP == 32)
                {
                    Convert32To24Frame(d, &frame[0], w*h);
                    d = &frame[0];
                }
                // 
                if(auto_palette_active == 2)
                {
                    auto_palette_active = 0;
                    format = ZMBV_FORMAT_1BPP;
                    // ^Dummy value, force palette reset
                    fprintf(stderr, "ZMBV: Going for dithering...\n");
                }
                goto Now24bpp;
            }
            if(auto_palette_active == 0)
            {
                fprintf(stderr, "ZMBV: No longer dithering...\n");
                auto_palette_active = 1;
            }

            if(format == ZMBV_FORMAT_8BPP && !paletted_okay)
            {
                make_keyframe = true;
                // Must change format, palette is no longer usable
                fprintf(stderr, "ZMBV: Reverting to 16bpp format (from format %u)\n", (unsigned)format);
                format        = ZMBV_FORMAT_16BPP;
            }
            if(paletted_okay)
            {
                if(format != ZMBV_FORMAT_8BPP)
                {
                    make_keyframe = true;
                    // Must change format
                    fprintf(stderr, "ZMBV:Changing to 8bpp format (from format %u)\n", (unsigned)format);
                    format        = ZMBV_FORMAT_8BPP;
                }
                // Figure out what kind of palette we can use
                // First, mark those palette slots that we can reuse; don't change them.
                bool dontchange[256] = { false };
                unsigned n_kept = 0, n_missing = 0;
                for(palette_contents_t::iterator
                    i = this_frame_used_colors.begin();
                    i != this_frame_used_colors.end(); )
                {
                    palette_search_t::iterator j = palette_search.find( *i );
                    if(j != palette_search.end())
                    {
                        dontchange[j->second] = true;
                        palette_contents_t::iterator i2 = i++;
                        this_frame_used_colors.erase(i2);
                        ++n_kept;
                    }
                    else { ++n_missing; ++i; }
                }
                if(n_missing)
                {
                    unsigned n_added = 0, n_replaced = 0;
                    bool unused[256];
                    for(unsigned n=0; n<256; ++n) unused[n] = true;
                    // Figure out which palette entries are unused.
                    for(palette_search_t::iterator i = palette_search.begin();
                                                   i != palette_search.end();
                                                   ++i)
                    {
                        unused[i->second] = false;
                    }

                    // Now add missing colors
                    for(palette_contents_t::iterator
                        i = this_frame_used_colors.begin();
                        i != this_frame_used_colors.end();
                        ++i)
                    {
                        // Find an unused slot in the palette.
                        unsigned color = 0;
                        while(!unused[color] && color < 256) ++color;
                        if(color < 256)
                        {
                            ++n_added;
                        }
                        else
                        {
                            // None available? Replace one of don't-need colors.
                            color = 0;
                            while(dontchange[color] && color < 256) ++color;
                            if(color < 256)
                            {
                                // Find the slot that was used longest time ago
                                unsigned age = palette_age[color];
                                for(unsigned c=color+1; c<256; ++c)
                                    if(!dontchange[c] && palette_age[c] > age)
                                        { age = palette_age[c]; color = c; }
                                ++n_replaced;
                            }
                        }
                        if(color < 256)
                        {
                            // Remove the palette entrycorresponding to that slot
                            for(palette_search_t::iterator j = palette_search.begin();
                                                           j != palette_search.end();
                                                           ++j)
                            {
                                if(j->second == color)
                                    { palette_search.erase(j); break; }
                            }

                            unsigned rgb565 = *i;
                            palette_search.insert( std::make_pair(rgb565, color) );
                            if(INPUT_BPP == 16)
                                Unbuild16(&previous_palette[color*4], rgb565);
                            else
                            {
                                previous_palette[color*4+0] = (rgb565 >> 16) & 0xFF;
                                previous_palette[color*4+1] = (rgb565 >>  8) & 0xFF;
                                previous_palette[color*4+2] = (rgb565 >>  0) & 0xFF;
                            }
                            
                            fprintf(stderr, "ZMBV palette slot %u set to: %02X,%02X,%02X\n",
                                color,
                                previous_palette[color*4+0],
                                previous_palette[color*4+1],
                                previous_palette[color*4+2]);
                            unused[color]      = false;
                            dontchange[color]  = true;
                        }
                    }
                    fprintf(stderr, "ZMBV palette replaced: %u kept, %u was missing, %u added, %u replaced, %zu colors in palette\n",
                        n_kept, n_missing, n_added, n_replaced, palette_search.size());
                    auto_palette_active = 2;
                }

                pal_frame.resize(num_pixels);
                if(INPUT_BPP == 16)
                    for(unsigned a=0; a<num_pixels; ++a)
                    {
                        unsigned c     = palette_search.find(PIX16at(a))->second;
                        pal_frame[a]   = c;
                        palette_age[c] = 0;
                    }
                else if(INPUT_BPP == 32)
                    for(unsigned a=0; a<num_pixels; ++a)
                    {
                        unsigned c     = palette_search.find(PIX32at(a))->second;
                        pal_frame[a]   = c;
                        palette_age[c] = 0;
                    }
                else if(INPUT_BPP == 24)
                    for(unsigned a=0; a<num_pixels; ++a)
                    {
                        unsigned c     = palette_search.find(PIX24at(a))->second;
                        pal_frame[a]   = c;
                        palette_age[c] = 0;
                    }
                for(unsigned a=0; a<256; ++a)
                    palette_age[a] += 1;

                d          = &pal_frame[0];
                actual_bpp = 8;
            }
        }
        else if(INPUT_BPP == 24/* || INPUT_BPP == 32*/)
        {
            if(time < 0.5 || (time >= 2.0 && time < 3.0)
            /*
            || (time >= 497+0.1 && time <= 497+2.5-0.1)
            || (time >= 506+0.1 && time <= 506+2.5-0.1)
            || (time >= 531+0.1 && time <= 531+2.5-0.1)
            || (time >= 588+0.1 && time <= 588+2.5-0.1)
            || (time >= 644+0.1 && time <= 644+2.5-0.1)
            || (time >= 691+0.1 && time <= 691+2.5-0.1)
            || (time >= 742+0.1 && time <= 742+2.5-0.1)
            || (time >= 804+0.1 && time <= 804+2.5-0.1)
            */
            )
            {
                if(INPUT_BPP != 32)
                {
                    // Change into 32bpp
                    pal_frame.clear();
                    pal_frame.resize(num_pixels * 4);
                    for(unsigned a=0, y=0; y<h; ++y)
                    for(unsigned      x=0; x<w; ++x, ++a)
                        memcpy(&pal_frame[a*4], &d[a*3], 3);

                    if(format != ZMBV_FORMAT_32BPP)
                    {
                        make_keyframe = true;
                        fprintf(stderr, "ZMBV:Changing to 32bpp format (from format %u)\n", (unsigned)format);
                        format        = ZMBV_FORMAT_32BPP;
                    }
                    actual_bpp = 32;
                    d = &pal_frame[0];
                }
            }
            /*else if(time >= 1.8 && time <= 7.4)
            {
                // Change into 16bpp
                pal_frame.resize(num_pixels * 2);

                unsigned short* p = (unsigned short*) &pal_frame[0];
                for(unsigned a=0, y=0; y<h; ++y)
                    for(unsigned x=0; x<w; ++x, ++a)
                    {
                        unsigned q = q32x32[ x%32 + (y%32)*32 ];
                        p[a] = dith(d[a*3+0], 255, 31)
                             + dith(d[a*3+1], 255, 63)*32
                             + dith(d[a*3+2], 255, 31)*32*64;
                    }

                //Convert24To16Frame(d, &pal_frame[0], num_pixels, w);

                if(format != ZMBV_FORMAT_16BPP)
                {
                    make_keyframe = true;
                    fprintf(stderr, "ZMBV:Changing to 16bpp format (from format %u)\n", (unsigned)format);
                    format        = ZMBV_FORMAT_16BPP;
                }
                actual_bpp = 16;
                d = &pal_frame[0];
            }*/
            else
            {
Now24bpp:
                // Change into 8bpp, paletted (fixed palette)
                static const double Gamma = 2.0;
                if(format != ZMBV_FORMAT_8BPP)
                {
                    unsigned c=0;
                #if 1 /* Use advanced dithering */
                    static const unsigned constpal[] =
                    {
                        /*
                        // NES (ASQUIRE6)
                        0x000000,0x00273F,0x003C80,0x005400,0x00543C,0x00718B,
                        0x008400,0x008468,0x101010,0x2C4400,0x2C60C0,0x2CB4C4,
                        0x34C87C,0x3500AC,0x3C2C00,0x3CD43C,0x40207C,0x407400,
                        0x4C4C4C,0x4D00FC,0x58A0E8,0x612800,0x686000,0x707070,
                        0x740000,0x740074,0x781838,0x7AC628,0x7D36D1,0x8484FF,
                        0x904420,0x91E2E2,0xACE4C4,0xACECAC,0xAEAEAE,0xB6B6B6,
                        0xB8D0F4,0xBC2424,0xBD72FD,0xBFAF00,0xC000B8,0xC4C4FF,
                        0xC4E4A4,0xC52661,0xE08E4A,0xE0C0FC,0xE9E18D,0xECD0B0,
                        0xF55AEB,0xF8C0DC,0xFB6AAF,0xFBB5F4,0xFCC4C4,0xFF7474,
                        0xFFFFFF,
                        // Milly Logo
                        0x010439,0x030481,0x0D10D7,0x0E3516,0x153F64,0x18100D,
                        0x1A7413,0x1E50B5,0x20E7B9,0x22FDCA,0x23C6A1,0x2BBD1F,
                        0x2C72FD,0x327F70,0x3747FD,0x3AFE2A,0x3AFF2A,0x422C1B,
                        0x7A4C31,0x88E2EB,0xA1FEFF,0xA9754B,0xD0AB59,0xDEC9B6,
                        0xEC0203,0xFA715A,0xFDD068,
                        0x000019,0x000024,0x00004B,0x010230,0x010264,0x020272,
                        0x020287,0x02033D,0x020458,0x0305F0,0x0306FE,0x04059C,
                        0x0506DB,0x070C7D,0x090BAB,0x0A0A0F,0x0A0DCE,0x0D10BF,
                        0x0F1018,0x1016F5,0x15191E,0x171DE9,0x1B2D64,0x1E24DB,
                        0x1E2A4C,0x203A79,0x212B2C,0x262DF0,0x26313C,0x2C36FA,
                        0x2E4A6A,0x3054CD,0x3157C5,0x334FE0,0x354EF2,0x3742FE,
                        0x374A58,0x374CFD,0x375DC7,0x3A49FE,0x3A61D9,0x3C4A51,
                        0x3C63EC,0x40484A,0x4560FB,0x470613,0x485DFE,0x4966FF,
                        0x4976FF,0x4C4D49,0x4D70FF,0x4F7FFE,0x5190FB,0x53A0FA,
                        0x57A3F8,0x5AA4EF,0x5F483D,0x607C80,0x637A77,0x63A9DE,
                        0x67858A,0x69A9CA,0x6B716D,0x6B8D92,0x6D939A,0x6E4C3D,
                        0x6E99AA,0x6EA5BC,0x7A4D3C,0x7A7161,0x834F3B,0x85725C,
                        0x8BFBFE,0x8EFCFE,0x927158,0x954933,0x956E54,0x97FBFF,
                        0xA0FEFF,0xA27253,0xA5FEFF,0xA90709,0xAC785A,0xACF8F8,
                        0xAE7F66,0xB1E3E7,0xB2DBDF,0xB3EDF0,0xB5FEFF,0xB6FDFE,
                        0xB88D72,0xB9967E,0xBD2D21,0xC0D4D6,0xC39D86,0xC7CECE,
                        0xC9A48A,0xD2AD91,0xDAB196,0xDAD0BF,0xDBCEB9,0xDEBB9F,
                        0xE00203,0xE0C3A4,0xE5CBAD,0xED0102,0xEF0707,0xF50404,
                        0xF80101,
                        */
                        // Joe editor palette
                        0x000000,0x00005F,0x000087,0x0000AF,0x0000D7,0x0000FF,
                        0x005F00,0x005F5F,0x005F87,0x005FAF,0x005FD7,0x005FFF,
                        0x008700,0x00875F,0x008787,0x0087AF,0x0087D7,0x0087FF,
                        0x00AF00,0x00AF5F,0x00AF87,0x00AFAF,0x00AFD7,0x00AFFF,
                        0x00D700,0x00D75F,0x00D787,0x00D7AF,0x00D7D7,0x00D7FF,
                        0x00FF00,0x00FF5F,0x00FF87,0x00FFAF,0x00FFD7,0x00FFFF,
                        0x870000,0x87005F,0x870087,0x8700AF,0x8700D7,0x8700FF,
                        0x875F00,0x875F5F,0x875F87,0x875FAF,0x875FD7,0x875FFF,
                        0x878700,0x87875F,0x878787,0x8787AF,0x8787D7,0x8787FF,
                        0x87AF00,0x87AF5F,0x87AF87,0x87AFAF,0x87AFD7,0x87AFFF,
                        0x87D700,0x87D75F,0x87D787,0x87D7AF,0x87D7D7,0x87D7FF,
                        0x87FF00,0x87FF5F,0x87FF87,0x87FFAF,0x87FFD7,0x87FFFF,
                        0xAF0000,0xAF005F,0xAF0087,0xAF00AF,0xAF00D7,0xAF00FF,
                        0xAF5F00,0xAF5F5F,0xAF5F87,0xAF5FAF,0xAF5FD7,0xAF5FFF,
                        0xAFAF00,0xAFAF5F,0xAFAF87,0xAFAFAF,0xAFAFD7,0xAFAFFF,
                        0xD7AF00,0xD7AF5F,0xD7AF87,0xD7AFAF,0xD7AFD7,0xD7AFFF,
                        0xD7D700,0xD7D75F,0xD7D787,0xD7D7AF,0xD7D7D7,0xD7D7FF,
                        0xD7FF00,0xD7FF5F,0xD7FF87,0xD7FFAF,0xD7FFD7,0xD7FFFF,
                        0xFF0000,0xFF005F,0xFF0087,                  0xFF00FF,
                        0xFF8700,0xFF875F,0xFF8787                  ,0xFF87FF,
                        0xFFAF00,0xFFAF5F,0xFFAF87,0xFFAFAF         ,0xFFAFFF,
                        0xFFD700,0xFFD75F,0xFFD787,0xFFD7AF         ,0xFFD7FF,
                        0xFFFF00,0xFFFF5F,0xFFFF87         ,0xFFFFD7,0xFFFFFF,
                        // some VGA colors
                        0xAAAAAA,0x888888,0xCCCCCC,0xA5A5A5,0xAA5500,
                        0x00AA00,0xFF55FF,0x00AAAA,0x55FF55,0x0000AA,
                        // HUDmaker subtitle
0x020102,0x030107,0x03020D,0x06040A,0x0A0312,0x080518,0x12071C,
0x0C0926,0x0E0E0F,0x1A0826,0x120649,0x120E36,0x220B2F,0x181130,
0x191819,0x260D35,0x181240,0x290E3D,0x201443,0x1E154A,0x2F0E46,
0x300C5B,0x29164A,0x201953,0x222222,0x36114E,0x240DA7,0x3B0F64,
0x301956,0x37155C,0x291D59,0x3D1459,0x41165E,0x391B63,0x2D2D2C,
0x461662,0x3C1A69,0x451864,0x332168,0x451868,0x491764,0x491863,
0x3717A1,0x451A6D,0x411980,0x4B1966,0x4A1969,0x411D70,0x3C206E,
0x4B196E,0x382274,0x343434,0x3F2275,0x3F2C4A,0x4C1A89,0x4F1D77,
0x3D267C,0x373837,0x381EBB,0x412985,0x501F94,0x502B6A,0x472B8D,
0x3F403F,0x57259E,0x444444,0x5B2BAF,0x4E4E4E,0x622FC3,0x614179,
0x6D3EAE,0x595959,0x656565,0x7C568E,0x727172,0x808080,0x9175A3,
0x8C8C8C,0x99989A,0xAC95B8,0xA2A3A1,0xA5A7A4,0xAAABA9,0xAFB1AE,
0xB6B7B6,0xBFBEC0,0xCBC2CE,0xD8D7D8,0xE5E4E6,0xF2F2F2,
                        // Checkerboard
                        0x244B5B,0x204351,0x1C3C48,0x12252D,0x091216,
                        /*
                        // grayscales
                        0x270081,0x090909,0x070707,         0x030322,0x0C0C0C,
                        0x040404,0x101018,0x545454,0xF4D0B8,0xFF8484,0x8B7100,
                        0x3900BD,0xBFBFBF,         0x005468,0x6363BF,
                        */
                    };
                    const unsigned n_predefined = sizeof(constpal)/sizeof(*constpal);
                    fprintf(stderr, "%u predefined colors\n", n_predefined);
                    palette_search.clear();
                    for(unsigned n=0; n< n_predefined; ++n)
                    {
                        unsigned pal = constpal[n];
                        pal = (pal >> 16) | (pal & 0x00FF00) | ((pal << 16) & 0xFF0000);
                        if(palette_search.find(pal) != palette_search.end())
                        {
                            fprintf(stderr, "Duplicate %06X ignored\n", constpal[n]);
                            continue;
                        }
                        palette_search[pal] = c;
                        ((unsigned *)previous_palette)[c] = pal;
                        ++c;
                    }
                    /*
                    static const int sectiontable[10] =
                        {0200,0210,0220,0020,0022,0012,0002,0102,0202,0201};
                    for(int sat=0; sat<5; ++sat)
                        for(int section=0; section<10; ++section)
                            for(int bright=0; bright<5; ++bright)
                            {
                                if(c >= 256) break;
                                double gray = (sat<2 ? (2+bright) / 6.0 : (1+bright) / 5.0);
                                double cr = gray * ((sectiontable[section]>>6)&3)/2;
                                double cg = gray * ((sectiontable[section]>>3)&3)/2;
                                double cb = gray * ((sectiontable[section]>>0)&3)/2;
                                double luma = sat==3 ? gray : (cr*0.299 + cg*0.587 + cb*0.114);
                                double satfactor = sat==3?0.2:pow((sat+1) / 5.0, 1.5);
                                double r = luma + (cr-luma) * satfactor;
                                double g = luma + (cg-luma) * satfactor;
                                double b = luma + (cb-luma) * satfactor;
                                int rr = r*255.9, gg = g*255.9, bb = b*255.9;
                                previous_palette[c*4+0] = rr;
                                previous_palette[c*4+1] = gg;
                                previous_palette[c*4+2] = bb;
                                fprintf(stderr, "ZMBV color %u: %02X,%02X,%02X\n", c,rr,gg,bb);
                                ++c;
                            }*/
                #else /* Use regular palette */
                    for(unsigned r=0; r<5; ++r)
                        for(unsigned g=0; g<7; ++g)
                            for(unsigned b=0; b<7; ++b, ++c)
                            {
                                unsigned rr = r==4 ? 0x7F : r*0x55;
                                unsigned gg = g*0x55/2;
                                unsigned bb = b*0x55/2;
                                previous_palette[c*4+0] = rr;  // 00    55    AA    FF 7F
                                previous_palette[c*4+1] = gg;  // 00 2A 55 7F AA D4 FF
                                previous_palette[c*4+2] = bb;  // 00 2A 55 7F AA D4 FF
                                fprintf(stderr, "ZMBV color %u: %02X,%02X,%02X\n", c,rr,gg,bb);
                            }
                    for(unsigned y=1; y<=10; ++y, ++c) // 245..254
                    {
                        unsigned yy = y*0xFF/11.0 + 0.5;
                        previous_palette[c*4+0] = yy;
                        previous_palette[c*4+1] = yy;
                        previous_palette[c*4+2] = yy;
                        fprintf(stderr, "ZMBV color %u: %02X,%02X,%02X\n", c, yy,yy,yy);
                        // 17 2E 46 5D 74 8B A2 B9 D1 E8
                        // also have 00, 55, 7F, AA, FF
                    }
                    while(c < 256) {
                        previous_palette[c*4+0] = 0xFF;
                        previous_palette[c*4+1] = 0x00;
                        previous_palette[c*4+2] = 0xFF; ++c; } // debug
                    // Total: 5*7*7 = 245
                #endif

                    palette_tree = KDTree<unsigned char> ();
                    for(unsigned i=0; i<c; ++i)
                    {
                        for(unsigned p=0; p<3; ++p)
                        {
                            double v = previous_palette[i*4+p]/255.0;
                            v = pow(v, Gamma);
                            palette_gamma[i][p] = v;
                        }
                        fprintf(stderr, "ZMBV color %u: %6.3f,%6.3f,%6.3f\n",
                            i,
                            palette_gamma[i][0],
                            palette_gamma[i][1],
                            palette_gamma[i][2]);
                        luma_table[i] = previous_palette[i*4+0]*299
                                      + previous_palette[i*4+1]*587
                                      + previous_palette[i*4+2]*114;
                        palette_tree.insert(palette_gamma[i], i);
                    }

                    make_keyframe = true;
                    // Must change format
                    fprintf(stderr, "ZMBV:Changing to 8bpp format (from format %u)\n", (unsigned)format);
                    format        = ZMBV_FORMAT_8BPP;
                }

                pal_frame.resize(num_pixels);
                for(unsigned a=0, y=0; y<h; ++y)
                for(unsigned      x=0; x<w; ++x, ++a)
                {
                    unsigned q = q32x32[ x%32 + (y%32)*32 ];
                    // unsigned q = q4x4[ (x%4) + (y%4)*4 ];
                    int rr = d[a*3+2]; //double rf = std::pow(rr / 255.0, 1.0);
                    int gg = d[a*3+1]; //double gf = std::pow(gg / 255.0, 1.0);
                    int bb = d[a*3+0]; //double bf = std::pow(bb / 255.0, 1.0);
                #if 1 /* Use advanced dithering */
                    const unsigned key = (rr << 16) + (gg << 8) + bb;

                    std::map<unsigned,ncand>::iterator i = cache.lower_bound(key);
                    if(i != cache.end() && i->first == key)
                    {
                        unsigned k = i->second.index[ q * CandCount / (32u*32u) ];
                        pal_frame[a] = k;
                        continue;
                    }

                    ncand result;
                    unsigned char* candlist = result.index;

                    double in[3] = { rr/255.0, gg/255.0, bb/255.0 };
                    for(unsigned p=0; p<3; ++p) in[p] = pow(in[p], Gamma);

                    /*fprintf(stderr, "Trying for %06X (%6.3f,%6.3f,%6.3f); ", key,
                        in[0],in[1],in[2]);*/

                    KDTree<unsigned char>::KDPoint trying(in);
                    for(unsigned c=0; c<CandCount; ++c)
                    {
                        // Find closest match from palette
                        const unsigned char* kk = palette_tree.nearest(trying);
                        unsigned k = kk ? *kk : 4;

                        candlist[c] = k;
                        if(c+1 >= CandCount) break;
                        // Compensate for error
                        for(unsigned p=0; p<3; ++p)
                        {
                            trying.coord[p] += (in[p] - palette_gamma[k][p]) * 1.0;
                            if(trying.coord[p] < 0.0) trying.coord[p] = 0.0;
                            if(trying.coord[p] > 1.0) trying.coord[p] = 1.0;
                        }
                    }
                    // 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_table[candlist[i-1]] > luma_table[k]; --i)
                            candlist[i] = candlist[i-1];
                        candlist[i] = k;
                    }
                    /*fprintf(stderr, "Gets: ");
                    for(unsigned c=0; c<CandCount; ++c)
                        fprintf(stderr, " %02X%02X%02X", previous_palette[candlist[c]*4+0],
                                                         previous_palette[candlist[c]*4+1],
                                                         previous_palette[candlist[c]*4+2]);
                    fprintf(stderr, "\n");*/

                    cache.insert(i, std::make_pair(key, result) );

                    unsigned k = candlist[ q * CandCount / (32u*32u) ];
                    pal_frame[a] = k;
                #else /* Use regular palette */
                    //  ex. (255*64 * 7 + 256*63) / (255*64)'
                    // where 64 = qmax,,  256 = (inmax+1),  7 = outmax

                    if(std::abs(rr-gg) < 0x08
                    && std::abs(gg-bb) < 0x08
                    && std::abs(bb-rr) < 0x08)
                    {
                        // grayscale special
                        int yy = (rr * 299 + gg * 587 + bb * 114);
                        unsigned yv = dith(yy,255000, 11);
                        /**/ if(yv == 0)  pal_frame[a] = 0;                           // 00
                        else if(yy>=0x54 && yy<=0x56) pal_frame[a] = 2 + 2*7 + 7*7*1; // 55
                        else if(yy>=0x7E && yy<=0x80) pal_frame[a] = 3 + 3*7 + 7*7*4; // 7F
                        else if(yy>=0xA9 && yy<=0xAC) pal_frame[a] = 4 + 4*7 + 7*7*2; // AA
                        else if(yv == 11) pal_frame[a] = 6 + 6*7 + 7*7*3;             // FF
                        else pal_frame[a] = 245 + (yv-1);
                    }
                    else
                    {
                        unsigned r = dith(rr,255, 6);
                        if(r == 3) r = 4; else r = dith(rr,255, 3);
                        unsigned g = dith(gg,255, 6);
                        unsigned b = dith(bb,255, 6);
                        pal_frame[a] = b + g*7 + r*7*7;
                    }
                #endif
                }

                actual_bpp = 8;
                d = &pal_frame[0];
            }
            #undef dith
        }

        int bw_base = 8, bh_base = 8;/*
        int bw_base = 20;
        int bh_base = 15;                 // 15 % (2400/480) = 0
        if(time >= 11.5)
        {
            bw_base = 40;
            bh_base = 24;
        }*/

        e(!zmbv.PrepareCompressFrame(
            make_keyframe,
            format,
            (char*) previous_palette,
            &vid_buf[0], vid_buf.size(),
            bw_base, bh_base ));

        unsigned stride = w * ( (actual_bpp+7) / 8 );
        for(unsigned y=0; y<h; ++y)
        {
            void* p = (void*) &d[ y * stride ];
            zmbv.CompressLines(1, &p);
        }

        size_t gotsize = zmbv.FinishCompressFrame();
        return std::pair<bool,size_t> (make_keyframe, gotsize);
    }

    void WriteHeader()
    {
        e(mk_writeHeader(mkw, "hudmaker"));
    }
    void PutAudioFrame(const unsigned char* d, unsigned bytes, unsigned samples, unsigned rate)
    {
        unsigned long long time = AudioPos * (1e9l / rate);
        e(mk_startFrame(mkw, mkt_a));
        e(mk_addFrameData(mkw, mkt_a, d, bytes));
        e(mk_setFrameFlags(mkw, mkt_a, time, true, 0));
        e(mk_flushFrame(mkw, mkt_a));
        AudioPos += samples;
        fprintf(stderr, "AudioPos %g\n", time/1e9);
    }
    void PutVideoFrame(const unsigned char* d, unsigned bytes, unsigned fps_scaled,
                       bool is_keyframe)
    {
        timeval now;
        gettimeofday(&now, NULL);

        unsigned long long time = VideoPos * ((16777216e9l) / fps_scaled);

        e(mk_startFrame(mkw, mkt_v));
        e(mk_addFrameData(mkw, mkt_v, d,bytes));
        e(mk_setFrameFlags(mkw, mkt_v, time, is_keyframe, 0));
        e(mk_flushFrame(mkw, mkt_v));

        double start_time = started_time.tv_sec*1e9 + started_time.tv_usec*1e3;
        double now_time   =          now.tv_sec*1e9 +          now.tv_usec*1e3;
        double elapsed = now_time - start_time;

        VideoPos += 1;
        fprintf(stderr, "VideoPos %g; Average speed: %g s realtime per 1s of video\n",
            time/1e9,
            elapsed / time);
    }

    #undef e
};