/*

 * Apple ProRes encoder

 *

 * Copyright (c) 2011 Anatoliy Wasserman

 * Copyright (c) 2012 Konstantin Shishkov

 *

 * This file is part of FFmpeg.

 *

 * FFmpeg is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2.1 of the License, or (at your option) any later version.

 *

 * FFmpeg is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with FFmpeg; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

 */

#include "libavutil/mem.h"

#include "libavutil/mem_internal.h"

#include "libavutil/opt.h"

#include "libavutil/pixdesc.h"

#include "avcodec.h"

#include "codec_internal.h"

#include "encode.h"

#include "fdctdsp.h"

#include "put_bits.h"

#include "profiles.h"

#include "bytestream.h"

#include "proresdata.h"

#include "proresenc_kostya_common.h"

#define TRELLIS_WIDTH 16

#define SCORE_LIMIT   INT_MAX / 2

struct TrellisNode {

    int prev_node;

    int quant;

    int bits;

    int score;

};

typedef struct ProresThreadData {

    DECLARE_ALIGNED(16, int16_t, blocks)[MAX_PLANES][64 * 4 * MAX_MBS_PER_SLICE];

    DECLARE_ALIGNED(16, uint16_t, emu_buf)[16 * 16];

    int16_t custom_q[64];

    int16_t custom_chroma_q[64];

    struct TrellisNode *nodes;

} ProresThreadData;

static void get_slice_data(ProresContext *ctx, const uint16_t *src,

                           ptrdiff_t linesize, int x, int y, int w, int h,

                           int16_t *blocks, uint16_t *emu_buf,

                           int mbs_per_slice, int blocks_per_mb, int is_chroma)

{

    const uint16_t *esrc;

    const int mb_width = 4 * blocks_per_mb;

    ptrdiff_t elinesize;

    int i, j, k;

    for (i = 0; i < mbs_per_slice; i++, src += mb_width) {

        if (x >= w) {

            memset(blocks, 0, 64 * (mbs_per_slice - i) * blocks_per_mb

                              * sizeof(*blocks));

            return;

        }

        if (x + mb_width <= w && y + 16 <= h) {

            esrc      = src;

            elinesize = linesize;

        } else {

            int bw, bh, pix;

            esrc      = emu_buf;

            elinesize = 16 * sizeof(*emu_buf);

            bw = FFMIN(w - x, mb_width);

            bh = FFMIN(h - y, 16);

            for (j = 0; j < bh; j++) {

                memcpy(emu_buf + j * 16,

                       (const uint8_t*)src + j * linesize,

                       bw * sizeof(*src));

                pix = emu_buf[j * 16 + bw - 1];

                for (k = bw; k < mb_width; k++)

                    emu_buf[j * 16 + k] = pix;

            }

            for (; j < 16; j++)

                memcpy(emu_buf + j * 16,

                       emu_buf + (bh - 1) * 16,

                       mb_width * sizeof(*emu_buf));

        }

        if (!is_chroma) {

            ctx->fdct(&ctx->fdsp, esrc, elinesize, blocks);

            blocks += 64;

            if (blocks_per_mb > 2) {

                ctx->fdct(&ctx->fdsp, esrc + 8, elinesize, blocks);

                blocks += 64;

            }

            ctx->fdct(&ctx->fdsp, esrc + elinesize * 4, elinesize, blocks);

            blocks += 64;

            if (blocks_per_mb > 2) {

                ctx->fdct(&ctx->fdsp, esrc + elinesize * 4 + 8, elinesize, blocks);

                blocks += 64;

            }

        } else {

            ctx->fdct(&ctx->fdsp, esrc, elinesize, blocks);

            blocks += 64;

            ctx->fdct(&ctx->fdsp, esrc + elinesize * 4, elinesize, blocks);

            blocks += 64;

            if (blocks_per_mb > 2) {

                ctx->fdct(&ctx->fdsp, esrc + 8, elinesize, blocks);

                blocks += 64;

                ctx->fdct(&ctx->fdsp, esrc + elinesize * 4 + 8, elinesize, blocks);

                blocks += 64;

            }

        }

        x += mb_width;

    }

}

static void get_alpha_data(ProresContext *ctx, const uint16_t *src,

                           ptrdiff_t linesize, int x, int y, int w, int h,

                           uint16_t *blocks, int mbs_per_slice, int abits)

{

    const int slice_width = 16 * mbs_per_slice;

    int i, j, copy_w, copy_h;

    copy_w = FFMIN(w - x, slice_width);

    copy_h = FFMIN(h - y, 16);

    for (i = 0; i < copy_h; i++) {

        memcpy(blocks, src, copy_w * sizeof(*src));

        if (abits == 8)

            for (j = 0; j < copy_w; j++)

                blocks[j] >>= 2;

        else

            for (j = 0; j < copy_w; j++)

                blocks[j] = (blocks[j] << 6) | (blocks[j] >> 4);

        for (j = copy_w; j < slice_width; j++)

            blocks[j] = blocks[copy_w - 1];

        blocks += slice_width;

        src    += linesize >> 1;

    }

    for (; i < 16; i++) {

        memcpy(blocks, blocks - slice_width, slice_width * sizeof(*blocks));

        blocks += slice_width;

    }

}

/**

 * Write an unsigned rice/exp golomb codeword.

 */

static inline void encode_vlc_codeword(PutBitContext *pb, unsigned codebook, int val)

{

    unsigned int rice_order, exp_order, switch_bits, switch_val;

    int exponent;

    /* number of prefix bits to switch between Rice and expGolomb */

    switch_bits = (codebook & 3) + 1;

    rice_order  =  codebook >> 5;       /* rice code order */

    exp_order   = (codebook >> 2) & 7;  /* exp golomb code order */

    switch_val  = switch_bits << rice_order;

    if (val >= switch_val) {

        val -= switch_val - (1 << exp_order);

        exponent = av_log2(val);

        put_bits(pb, exponent - exp_order + switch_bits, 0);

        put_bits(pb, exponent + 1, val);

    } else {

        exponent = val >> rice_order;

        if (exponent)

            put_bits(pb, exponent, 0);

        put_bits(pb, 1, 1);

        if (rice_order)

            put_sbits(pb, rice_order, val);

    }

}

#define GET_SIGN(x)  ((x) >> 31)

#define MAKE_CODE(x) (((x) * 2) ^ GET_SIGN(x))

static void encode_dcs(PutBitContext *pb, int16_t *blocks,

                       int blocks_per_slice, int scale)

{

    int i;

    int codebook = 5, code, dc, prev_dc, delta, sign, new_sign;

    prev_dc = (blocks[0] - 0x4000) / scale;

    encode_vlc_codeword(pb, FIRST_DC_CB, MAKE_CODE(prev_dc));

    sign     = 0;

    blocks  += 64;

    for (i = 1; i < blocks_per_slice; i++, blocks += 64) {

        dc       = (blocks[0] - 0x4000) / scale;

        delta    = dc - prev_dc;

        new_sign = GET_SIGN(delta);

        delta    = (delta ^ sign) - sign;

        code     = MAKE_CODE(delta);

        encode_vlc_codeword(pb, ff_prores_dc_codebook[codebook], code);

        codebook = FFMIN(code, 6);

        sign     = new_sign;

        prev_dc  = dc;

    }

}

static void encode_acs(PutBitContext *pb, int16_t *blocks,

                       int blocks_per_slice,

                       const uint8_t *scan, const int16_t *qmat)

{

    int idx, i;

    int prev_run = 4;

    int prev_level = 2;

    int run = 0, level;

    int max_coeffs, abs_level;

    max_coeffs = blocks_per_slice << 6;

    for (i = 1; i < 64; i++) {

        for (idx = scan[i]; idx < max_coeffs; idx += 64) {

            level = blocks[idx] / qmat[scan[i]];

            if (level) {

                abs_level = FFABS(level);

                encode_vlc_codeword(pb, ff_prores_run_to_cb[prev_run], run);

                encode_vlc_codeword(pb, ff_prores_level_to_cb[prev_level], abs_level - 1);

                put_sbits(pb, 1, GET_SIGN(level));

                prev_run   = FFMIN(run, 15);

                prev_level = FFMIN(abs_level, 9);

                run        = 0;

            } else {

                run++;

            }

        }

    }

}

static void encode_slice_plane(ProresContext *ctx, PutBitContext *pb,

                              const uint16_t *src, ptrdiff_t linesize,

                              int mbs_per_slice, int16_t *blocks,

                              int blocks_per_mb,

                              const int16_t *qmat)

{

    int blocks_per_slice = mbs_per_slice * blocks_per_mb;

    encode_dcs(pb, blocks, blocks_per_slice, qmat[0]);

    encode_acs(pb, blocks, blocks_per_slice, ctx->scantable, qmat);

}

static void put_alpha_diff(PutBitContext *pb, int cur, int prev, int abits)

{

    const int dbits = (abits == 8) ? 4 : 7;

    const int dsize = 1 << dbits - 1;

    int diff = cur - prev;

    diff = av_zero_extend(diff, abits);

    if (diff >= (1 << abits) - dsize)

        diff -= 1 << abits;

    if (diff < -dsize || diff > dsize || !diff) {

        put_bits(pb, 1, 1);

        put_bits(pb, abits, diff);

    } else {

        put_bits(pb, 1, 0);

        put_bits(pb, dbits - 1, FFABS(diff) - 1);

        put_bits(pb, 1, diff < 0);

    }

}

static void put_alpha_run(PutBitContext *pb, int run)

{

    if (run) {

        put_bits(pb, 1, 0);

        if (run < 0x10)

            put_bits(pb, 4, run);

        else

            put_bits(pb, 15, run);

    } else {

        put_bits(pb, 1, 1);

    }

}

// todo alpha quantisation for high quants

static void encode_alpha_plane(ProresContext *ctx, PutBitContext *pb,

                              int mbs_per_slice, uint16_t *blocks,

                              int quant)

{

    const int abits = ctx->alpha_bits;

    const int mask  = (1 << abits) - 1;

    const int num_coeffs = mbs_per_slice * 256;

    int prev = mask, cur;

    int idx = 0;

    int run = 0;

    cur = blocks[idx++];

    put_alpha_diff(pb, cur, prev, abits);

    prev = cur;

    do {

        cur = blocks[idx++];

        if (cur != prev) {

            put_alpha_run (pb, run);

            put_alpha_diff(pb, cur, prev, abits);

            prev = cur;

            run  = 0;

        } else {

            run++;

        }

    } while (idx < num_coeffs);

    put_alpha_run(pb, run);

}

static int encode_slice(AVCodecContext *avctx, const AVFrame *pic,

                        PutBitContext *pb,

                        int sizes[4], int x, int y, int quant,

                        int mbs_per_slice)

{

    ProresContext *ctx = avctx->priv_data;

    int i, xp, yp;

    int total_size = 0;

    const uint16_t *src;

    int num_cblocks, pwidth, line_add;

    ptrdiff_t linesize;

    int is_chroma;

    uint16_t *qmat;

    uint16_t *qmat_chroma;

    if (ctx->pictures_per_frame == 1)

        line_add = 0;

    else

        line_add = ctx->cur_picture_idx ^ !(pic->flags & AV_FRAME_FLAG_TOP_FIELD_FIRST);

    if (ctx->force_quant) {

        qmat = ctx->quants[0];

        qmat_chroma = ctx->quants_chroma[0];

    } else if (quant < MAX_STORED_Q) {

        qmat = ctx->quants[quant];

        qmat_chroma = ctx->quants_chroma[quant];

    } else {

        qmat = ctx->custom_q;

        qmat_chroma = ctx->custom_chroma_q;

        for (i = 0; i < 64; i++) {

            qmat[i] = ctx->quant_mat[i] * quant;

            qmat_chroma[i] = ctx->quant_chroma_mat[i] * quant;

        }

    }

    for (i = 0; i < ctx->num_planes; i++) {

        is_chroma    = (i == 1 || i == 2);

        if (!is_chroma || ctx->chroma_factor == CFACTOR_Y444) {

            xp          = x << 4;

            yp          = y << 4;

            num_cblocks = 4;

            pwidth      = avctx->width;

        } else {

            xp          = x << 3;

            yp          = y << 4;

            num_cblocks = 2;

            pwidth      = avctx->width >> 1;

        }

        linesize = pic->linesize[i] * ctx->pictures_per_frame;

        src = (const uint16_t*)(pic->data[i] + yp * linesize +

                                line_add * pic->linesize[i]) + xp;

        if (i < 3) {

            get_slice_data(ctx, src, linesize, xp, yp,

                           pwidth, avctx->height / ctx->pictures_per_frame,

                           ctx->blocks[0], ctx->emu_buf,

                           mbs_per_slice, num_cblocks, is_chroma);

            if (!is_chroma) {/* luma quant */

                encode_slice_plane(ctx, pb, src, linesize,

                                   mbs_per_slice, ctx->blocks[0],

                                   num_cblocks, qmat);

            } else { /* chroma plane */

                encode_slice_plane(ctx, pb, src, linesize,

                                   mbs_per_slice, ctx->blocks[0],

                                   num_cblocks, qmat_chroma);

            }

        } else {

            get_alpha_data(ctx, src, linesize, xp, yp,

                           pwidth, avctx->height / ctx->pictures_per_frame,

                           ctx->blocks[0], mbs_per_slice, ctx->alpha_bits);

            encode_alpha_plane(ctx, pb, mbs_per_slice, ctx->blocks[0], quant);

        }

        flush_put_bits(pb);

        sizes[i]   = put_bytes_output(pb) - total_size;

        total_size = put_bytes_output(pb);

    }

    return total_size;

}

static inline int estimate_vlc(unsigned codebook, int val)

{

    unsigned int rice_order, exp_order, switch_bits, switch_val;

    int exponent;

    /* number of prefix bits to switch between Rice and expGolomb */

    switch_bits = (codebook & 3) + 1;

    rice_order  =  codebook >> 5;       /* rice code order */

    exp_order   = (codebook >> 2) & 7;  /* exp golomb code order */

    switch_val  = switch_bits << rice_order;

    if (val >= switch_val) {

        val -= switch_val - (1 << exp_order);

        exponent = av_log2(val);

        return exponent * 2 - exp_order + switch_bits + 1;

    } else {

        return (val >> rice_order) + rice_order + 1;

    }

}

static int estimate_dcs(int *error, int16_t *blocks, int blocks_per_slice,

                        int scale)

{

    int i;

    int codebook = 5, code, dc, prev_dc, delta, sign, new_sign;

    int bits;

    prev_dc  = (blocks[0] - 0x4000) / scale;

    bits     = estimate_vlc(FIRST_DC_CB, MAKE_CODE(prev_dc));

    sign     = 0;

    blocks  += 64;

    *error  += FFABS(blocks[0] - 0x4000) % scale;

    for (i = 1; i < blocks_per_slice; i++, blocks += 64) {

        dc       = (blocks[0] - 0x4000) / scale;

        *error  += FFABS(blocks[0] - 0x4000) % scale;

        delta    = dc - prev_dc;

        new_sign = GET_SIGN(delta);

        delta    = (delta ^ sign) - sign;

        code     = MAKE_CODE(delta);

        bits    += estimate_vlc(ff_prores_dc_codebook[codebook], code);

        codebook = FFMIN(code, 6);

        sign     = new_sign;

        prev_dc  = dc;

    }

    return bits;

}

static int estimate_acs(int *error, int16_t *blocks, int blocks_per_slice,

                        const uint8_t *scan, const int16_t *qmat)

{

    int idx, i;

    int prev_run = 4;

    int prev_level = 2;

    int run, level;

    int max_coeffs, abs_level;

    int bits = 0;

    max_coeffs = blocks_per_slice << 6;

    run        = 0;

    for (i = 1; i < 64; i++) {

        for (idx = scan[i]; idx < max_coeffs; idx += 64) {

            level   = blocks[idx] / qmat[scan[i]];

            *error += FFABS(blocks[idx]) % qmat[scan[i]];

            if (level) {

                abs_level = FFABS(level);

                bits += estimate_vlc(ff_prores_run_to_cb[prev_run], run);

                bits += estimate_vlc(ff_prores_level_to_cb[prev_level],

                                     abs_level - 1) + 1;

                prev_run   = FFMIN(run, 15);

                prev_level = FFMIN(abs_level, 9);

                run    = 0;

            } else {

                run++;

            }

        }

    }

    return bits;

}

static int estimate_slice_plane(ProresContext *ctx, int *error, int plane,

                                const uint16_t *src, ptrdiff_t linesize,

                                int mbs_per_slice,

                                int blocks_per_mb,

                                const int16_t *qmat, ProresThreadData *td)

{

    int blocks_per_slice;

    int bits;

    blocks_per_slice = mbs_per_slice * blocks_per_mb;

    bits  = estimate_dcs(error, td->blocks[plane], blocks_per_slice, qmat[0]);

    bits += estimate_acs(error, td->blocks[plane], blocks_per_slice, ctx->scantable, qmat);

    return FFALIGN(bits, 8);

}

static int est_alpha_diff(int cur, int prev, int abits)

{

    const int dbits = (abits == 8) ? 4 : 7;

    const int dsize = 1 << dbits - 1;

    int diff = cur - prev;

    diff = av_zero_extend(diff, abits);

    if (diff >= (1 << abits) - dsize)

        diff -= 1 << abits;

    if (diff < -dsize || diff > dsize || !diff)

        return abits + 1;

    else

        return dbits + 1;

}

static int estimate_alpha_plane(ProresContext *ctx,

                                const uint16_t *src, ptrdiff_t linesize,

                                int mbs_per_slice, int16_t *blocks)

{

    const int abits = ctx->alpha_bits;

    const int mask  = (1 << abits) - 1;

    const int num_coeffs = mbs_per_slice * 256;

    int prev = mask, cur;

    int idx = 0;

    int run = 0;

    int bits;

    cur = blocks[idx++];

    bits = est_alpha_diff(cur, prev, abits);

    prev = cur;

    do {

        cur = blocks[idx++];

        if (cur != prev) {

            if (!run)

                bits++;

            else if (run < 0x10)

                bits += 4;

            else

                bits += 15;

            bits += est_alpha_diff(cur, prev, abits);

            prev = cur;

            run  = 0;

        } else {

            run++;

        }

    } while (idx < num_coeffs);

    if (run) {

        if (run < 0x10)

            bits += 4;

        else

            bits += 15;

    }

    return bits;

}

static int find_slice_quant(AVCodecContext *avctx,

                            int trellis_node, int x, int y, int mbs_per_slice,

                            ProresThreadData *td)

{

    ProresContext *ctx = avctx->priv_data;

    int i, q, pq, xp, yp;

    const uint16_t *src;

    int num_cblocks[MAX_PLANES], pwidth;

    int is_chroma[MAX_PLANES];

    const int min_quant = ctx->profile_info->min_quant;

    const int max_quant = ctx->profile_info->max_quant;

    int error, bits, bits_limit;

    int mbs, prev, cur, new_score;

    int slice_bits[TRELLIS_WIDTH], slice_score[TRELLIS_WIDTH];

    int overquant;

    uint16_t *qmat;

    uint16_t *qmat_chroma;

    int linesize[4], line_add;

    int alpha_bits = 0;

    if (ctx->pictures_per_frame == 1)

        line_add = 0;

    else

        line_add = ctx->cur_picture_idx ^ !(ctx->pic->flags & AV_FRAME_FLAG_TOP_FIELD_FIRST);

    mbs = x + mbs_per_slice;

    for (i = 0; i < ctx->num_planes; i++) {

        is_chroma[i]    = (i == 1 || i == 2);

        if (!is_chroma[i] || ctx->chroma_factor == CFACTOR_Y444) {

            xp             = x << 4;

            yp             = y << 4;

            num_cblocks[i] = 4;

            pwidth         = avctx->width;

        } else {

            xp             = x << 3;

            yp             = y << 4;

            num_cblocks[i] = 2;

            pwidth         = avctx->width >> 1;

        }

        linesize[i] = ctx->pic->linesize[i] * ctx->pictures_per_frame;

        src = (const uint16_t *)(ctx->pic->data[i] + yp * linesize[i] +

                                 line_add * ctx->pic->linesize[i]) + xp;

        if (i < 3) {

            get_slice_data(ctx, src, linesize[i], xp, yp,

                           pwidth, avctx->height / ctx->pictures_per_frame,

                           td->blocks[i], td->emu_buf,

                           mbs_per_slice, num_cblocks[i], is_chroma[i]);

        } else {

            get_alpha_data(ctx, src, linesize[i], xp, yp,

                           pwidth, avctx->height / ctx->pictures_per_frame,

                           td->blocks[i], mbs_per_slice, ctx->alpha_bits);

        }

    }

    for (q = min_quant; q < max_quant + 2; q++) {

        td->nodes[trellis_node + q].prev_node = -1;

        td->nodes[trellis_node + q].quant     = q;

    }

    if (ctx->alpha_bits)

        alpha_bits = estimate_alpha_plane(ctx, src, linesize[3],

                                          mbs_per_slice, td->blocks[3]);

    // todo: maybe perform coarser quantising to fit into frame size when needed

    for (q = min_quant; q <= max_quant; q++) {

        bits  = alpha_bits;

        error = 0;

        bits += estimate_slice_plane(ctx, &error, 0,

                                     src, linesize[0],

                                     mbs_per_slice,

                                     num_cblocks[0],

                                     ctx->quants[q], td); /* estimate luma plane */

        for (i = 1; i < ctx->num_planes - !!ctx->alpha_bits; i++) { /* estimate chroma plane */

            bits += estimate_slice_plane(ctx, &error, i,

                                         src, linesize[i],

                                         mbs_per_slice,

                                         num_cblocks[i],

                                         ctx->quants_chroma[q], td);

        }

        if (bits > 65000 * 8)

            error = SCORE_LIMIT;

        slice_bits[q]  = bits;

        slice_score[q] = error;

    }

    if (slice_bits[max_quant] <= ctx->bits_per_mb * mbs_per_slice) {

        slice_bits[max_quant + 1]  = slice_bits[max_quant];

        slice_score[max_quant + 1] = slice_score[max_quant] + 1;

        overquant = max_quant;

    } else {

        for (q = max_quant + 1; q < 128; q++) {

            bits  = alpha_bits;

            error = 0;

            if (q < MAX_STORED_Q) {

                qmat = ctx->quants[q];

                qmat_chroma = ctx->quants_chroma[q];

            } else {

                qmat = td->custom_q;

                qmat_chroma = td->custom_chroma_q;

                for (i = 0; i < 64; i++) {

                    qmat[i] = ctx->quant_mat[i] * q;

                    qmat_chroma[i] = ctx->quant_chroma_mat[i] * q;

                }

            }

            bits += estimate_slice_plane(ctx, &error, 0,

                                         src, linesize[0],

                                         mbs_per_slice,

                                         num_cblocks[0],

                                         qmat, td);/* estimate luma plane */

            for (i = 1; i < ctx->num_planes - !!ctx->alpha_bits; i++) { /* estimate chroma plane */

                bits += estimate_slice_plane(ctx, &error, i,

                                             src, linesize[i],

                                             mbs_per_slice,

                                             num_cblocks[i],

                                             qmat_chroma, td);

            }

            if (bits <= ctx->bits_per_mb * mbs_per_slice)

                break;

        }

        slice_bits[max_quant + 1]  = bits;

        slice_score[max_quant + 1] = error;

        overquant = q;

    }

    td->nodes[trellis_node + max_quant + 1].quant = overquant;

    bits_limit = mbs * ctx->bits_per_mb;

    for (pq = min_quant; pq < max_quant + 2; pq++) {

        prev = trellis_node - TRELLIS_WIDTH + pq;

        for (q = min_quant; q < max_quant + 2; q++) {

            cur = trellis_node + q;

            bits  = td->nodes[prev].bits + slice_bits[q];

            error = slice_score[q];

            if (bits > bits_limit)

                error = SCORE_LIMIT;

            if (td->nodes[prev].score < SCORE_LIMIT && error < SCORE_LIMIT)

                new_score = td->nodes[prev].score + error;

            else

                new_score = SCORE_LIMIT;

            if (td->nodes[cur].prev_node == -1 ||

                td->nodes[cur].score >= new_score) {

                td->nodes[cur].bits      = bits;

                td->nodes[cur].score     = new_score;

                td->nodes[cur].prev_node = prev;

            }

        }

    }

    error = td->nodes[trellis_node + min_quant].score;

    pq    = trellis_node + min_quant;

    for (q = min_quant + 1; q < max_quant + 2; q++) {

        if (td->nodes[trellis_node + q].score <= error) {

            error = td->nodes[trellis_node + q].score;

            pq    = trellis_node + q;

        }

    }

    return pq;

}

static int find_quant_thread(AVCodecContext *avctx, void *arg,

                             int jobnr, int threadnr)

{

    ProresContext *ctx = avctx->priv_data;

    ProresThreadData *td = ctx->tdata + threadnr;

    int mbs_per_slice = ctx->mbs_per_slice;

    int x, y = jobnr, mb, q = 0;

    for (x = mb = 0; x < ctx->mb_width; x += mbs_per_slice, mb++) {

        while (ctx->mb_width - x < mbs_per_slice)

            mbs_per_slice >>= 1;

        q = find_slice_quant(avctx,

                             (mb + 1) * TRELLIS_WIDTH, x, y,

                             mbs_per_slice, td);

    }

    for (x = ctx->slices_width - 1; x >= 0; x--) {

        ctx->slice_q[x + y * ctx->slices_width] = td->nodes[q].quant;

        q = td->nodes[q].prev_node;

    }

    return 0;

}

static int encode_frame(AVCodecContext *avctx, AVPacket *pkt,

                        const AVFrame *pic, int *got_packet)

{

    ProresContext *ctx = avctx->priv_data;

    uint8_t *orig_buf, *buf, *slice_hdr, *slice_sizes, *tmp;

    uint8_t *picture_size_pos;

    PutBitContext pb;

    int x, y, i, mb, q = 0;

    int sizes[4] = { 0 };

    int slice_hdr_size = 2 * ctx->num_planes;

    int frame_size, picture_size, slice_size;

    int pkt_size, ret;

    int max_slice_size = (ctx->frame_size_upper_bound - 200) / (ctx->pictures_per_frame * ctx->slices_per_picture + 1);

    uint8_t frame_flags;

    ctx->pic = pic;

    pkt_size = ctx->frame_size_upper_bound;

    if ((ret = ff_alloc_packet(avctx, pkt, pkt_size + FF_INPUT_BUFFER_MIN_SIZE)) < 0)

        return ret;

    orig_buf = pkt->data;

    // frame atom

    orig_buf += 4;                              // frame size

    bytestream_put_be32  (&orig_buf, FRAME_ID); // frame container ID

    buf = orig_buf;

    // frame header

    tmp = buf;

    buf += 2;                                   // frame header size will be stored here

    bytestream_put_be16  (&buf, ctx->chroma_factor != CFACTOR_Y422 || ctx->alpha_bits ? 1 : 0);

    bytestream_put_buffer(&buf, ctx->vendor, 4);

    bytestream_put_be16  (&buf, avctx->width);

    bytestream_put_be16  (&buf, avctx->height);

    frame_flags = ctx->chroma_factor << 6;

    if (avctx->flags & AV_CODEC_FLAG_INTERLACED_DCT)

        frame_flags |= (pic->flags & AV_FRAME_FLAG_TOP_FIELD_FIRST) ? 0x04 : 0x08;

    bytestream_put_byte  (&buf, frame_flags);

    bytestream_put_byte  (&buf, 0);             // reserved

    bytestream_put_byte  (&buf, pic->color_primaries);

    bytestream_put_byte  (&buf, pic->color_trc);

    bytestream_put_byte  (&buf, pic->colorspace);

    bytestream_put_byte  (&buf, ctx->alpha_bits >> 3);

    bytestream_put_byte  (&buf, 0);             // reserved

    if (ctx->quant_sel != QUANT_MAT_DEFAULT) {

        bytestream_put_byte  (&buf, 0x03);      // matrix flags - both matrices are present

        bytestream_put_buffer(&buf, ctx->quant_mat, 64);        // luma quantisation matrix

        bytestream_put_buffer(&buf, ctx->quant_chroma_mat, 64); // chroma quantisation matrix

    } else {

        bytestream_put_byte  (&buf, 0x00);      // matrix flags - default matrices are used

    }

    bytestream_put_be16  (&tmp, buf - orig_buf); // write back frame header size

    for (ctx->cur_picture_idx = 0;

         ctx->cur_picture_idx < ctx->pictures_per_frame;

         ctx->cur_picture_idx++) {

        // picture header

        picture_size_pos = buf + 1;

        bytestream_put_byte  (&buf, 0x40);          // picture header size (in bits)

        buf += 4;                                   // picture data size will be stored here

        bytestream_put_be16  (&buf, ctx->slices_per_picture);

        bytestream_put_byte  (&buf, av_log2(ctx->mbs_per_slice) << 4); // slice width and height in MBs

        // seek table - will be filled during slice encoding

        slice_sizes = buf;

        buf += ctx->slices_per_picture * 2;

        // slices

        if (!ctx->force_quant) {

            ret = avctx->execute2(avctx, find_quant_thread, NULL, NULL,

                                  ctx->mb_height);

            if (ret)

                return ret;

        }

        for (y = 0; y < ctx->mb_height; y++) {

            int mbs_per_slice = ctx->mbs_per_slice;

            for (x = mb = 0; x < ctx->mb_width; x += mbs_per_slice, mb++) {

                q = ctx->force_quant ? ctx->force_quant

                                     : ctx->slice_q[mb + y * ctx->slices_width];

                while (ctx->mb_width - x < mbs_per_slice)

                    mbs_per_slice >>= 1;

                bytestream_put_byte(&buf, slice_hdr_size << 3);

                slice_hdr = buf;

                buf += slice_hdr_size - 1;

                if (pkt_size <= buf - orig_buf + 2 * max_slice_size) {

                    uint8_t *start = pkt->data;

                    // Recompute new size according to max_slice_size

                    // and deduce delta

                    int delta = 200 + (ctx->pictures_per_frame *

                                ctx->slices_per_picture + 1) *

                                max_slice_size - pkt_size;

                    delta = FFMAX(delta, 2 * max_slice_size);

                    ctx->frame_size_upper_bound += delta;

                    if (!ctx->warn) {

                        avpriv_request_sample(avctx,

                                              "Packet too small: is %i,"

                                              " needs %i (slice: %i). "

                                              "Correct allocation",

                                              pkt_size, delta, max_slice_size);

                        ctx->warn = 1;

                    }

                    ret = av_grow_packet(pkt, delta);

                    if (ret < 0)

                        return ret;

                    pkt_size += delta;

                    orig_buf         = pkt->data + (orig_buf         - start);

                    buf              = pkt->data + (buf              - start);

                    picture_size_pos = pkt->data + (picture_size_pos - start);

                    slice_sizes      = pkt->data + (slice_sizes      - start);

                    slice_hdr        = pkt->data + (slice_hdr        - start);

                    tmp              = pkt->data + (tmp              - start);

                }

                init_put_bits(&pb, buf, (pkt_size - (buf - orig_buf)));

                ret = encode_slice(avctx, pic, &pb, sizes, x, y, q,

                                   mbs_per_slice);

                if (ret < 0)

                    return ret;

                bytestream_put_byte(&slice_hdr, q);

                slice_size = slice_hdr_size + sizes[ctx->num_planes - 1];

                for (i = 0; i < ctx->num_planes - 1; i++) {

                    bytestream_put_be16(&slice_hdr, sizes[i]);

                    slice_size += sizes[i];

                }

                bytestream_put_be16(&slice_sizes, slice_size);

                buf += slice_size - slice_hdr_size;

                if (max_slice_size < slice_size)

                    max_slice_size = slice_size;

            }

        }

        picture_size = buf - (picture_size_pos - 1);

        bytestream_put_be32(&picture_size_pos, picture_size);

    }

    orig_buf -= 8;

    frame_size = buf - orig_buf;

    bytestream_put_be32(&orig_buf, frame_size);

    pkt->size   = frame_size;

    *got_packet = 1;

    return 0;

}

static av_cold int encode_close(AVCodecContext *avctx)

{

    ProresContext *ctx = avctx->priv_data;

    int i;

    if (ctx->tdata) {

        for (i = 0; i < avctx->thread_count; i++)

            av_freep(&ctx->tdata[i].nodes);

    }

    av_freep(&ctx->tdata);

    av_freep(&ctx->slice_q);

    return 0;

}

static void prores_fdct(FDCTDSPContext *fdsp, const uint16_t *src,

                        ptrdiff_t linesize, int16_t *block)

{

    int x, y;

    const uint16_t *tsrc = src;

    for (y = 0; y < 8; y++) {

        for (x = 0; x < 8; x++)

            block[y * 8 + x] = tsrc[x];

        tsrc += linesize >> 1;

    }

    fdsp->fdct(block);

}

static av_cold int encode_init(AVCodecContext *avctx)

{

    ProresContext *ctx = avctx->priv_data;

    int err = 0, i, j, min_quant, max_quant;

    err = ff_prores_kostya_encode_init(avctx, ctx, avctx->pix_fmt);

    if (err < 0)

        return err;

    ctx->fdct      = prores_fdct;

    ff_fdctdsp_init(&ctx->fdsp, avctx);

    if (!ctx->force_quant) {

        min_quant = ctx->profile_info->min_quant;

        max_quant = ctx->profile_info->max_quant;

        ctx->slice_q = av_malloc_array(ctx->slices_per_picture, sizeof(*ctx->slice_q));

        if (!ctx->slice_q)

            return AVERROR(ENOMEM);

        ctx->tdata = av_calloc(avctx->thread_count, sizeof(*ctx->tdata));

        if (!ctx->tdata)

            return AVERROR(ENOMEM);

        for (j = 0; j < avctx->thread_count; j++) {

            ctx->tdata[j].nodes = av_malloc_array(ctx->slices_width + 1,

                                                  TRELLIS_WIDTH

                                                  * sizeof(*ctx->tdata->nodes));

            if (!ctx->tdata[j].nodes)

                return AVERROR(ENOMEM);

            for (i = min_quant; i < max_quant + 2; i++) {

                ctx->tdata[j].nodes[i].prev_node = -1;

                ctx->tdata[j].nodes[i].bits      = 0;

                ctx->tdata[j].nodes[i].score     = 0;

            }

        }

    }

    return 0;

}

#define OFFSET(x) offsetof(ProresContext, x)

#define VE     AV_OPT_FLAG_VIDEO_PARAM | AV_OPT_FLAG_ENCODING_PARAM

static const AVOption options[] = {

    { "mbs_per_slice", "macroblocks per slice", OFFSET(mbs_per_slice),

        AV_OPT_TYPE_INT, { .i64 = 8 }, 1, MAX_MBS_PER_SLICE, VE },

    { "profile",       NULL, OFFSET(profile), AV_OPT_TYPE_INT,

        { .i64 = PRORES_PROFILE_AUTO },

        PRORES_PROFILE_AUTO, PRORES_PROFILE_4444XQ, VE, .unit = "profile" },

    { "auto",         NULL, 0, AV_OPT_TYPE_CONST, { .i64 = PRORES_PROFILE_AUTO },

        0, 0, VE, .unit = "profile" },

    { "proxy",         NULL, 0, AV_OPT_TYPE_CONST, { .i64 = PRORES_PROFILE_PROXY },

        0, 0, VE, .unit = "profile" },

    { "lt",            NULL, 0, AV_OPT_TYPE_CONST, { .i64 = PRORES_PROFILE_LT },

        0, 0, VE, .unit = "profile" },

    { "standard",      NULL, 0, AV_OPT_TYPE_CONST, { .i64 = PRORES_PROFILE_STANDARD },

        0, 0, VE, .unit = "profile" },

    { "hq",            NULL, 0, AV_OPT_TYPE_CONST, { .i64 = PRORES_PROFILE_HQ },

        0, 0, VE, .unit = "profile" },

    { "4444",          NULL, 0, AV_OPT_TYPE_CONST, { .i64 = PRORES_PROFILE_4444 },

        0, 0, VE, .unit = "profile" },

    { "4444xq",        NULL, 0, AV_OPT_TYPE_CONST, { .i64 = PRORES_PROFILE_4444XQ },

        0, 0, VE, .unit = "profile" },

    { "vendor", "vendor ID", OFFSET(vendor),

        AV_OPT_TYPE_STRING, { .str = "Lavc" }, 0, 0, VE },

    { "bits_per_mb", "desired bits per macroblock", OFFSET(bits_per_mb),

        AV_OPT_TYPE_INT, { .i64 = 0 }, 0, 8192, VE },

    { "quant_mat", "quantiser matrix", OFFSET(quant_sel), AV_OPT_TYPE_INT,

        { .i64 = -1 }, -1, QUANT_MAT_DEFAULT, VE, .unit = "quant_mat" },

    { "auto",          NULL, 0, AV_OPT_TYPE_CONST, { .i64 = -1 },

        0, 0, VE, .unit = "quant_mat" },

    { "proxy",         NULL, 0, AV_OPT_TYPE_CONST, { .i64 = QUANT_MAT_PROXY },

        0, 0, VE, .unit = "quant_mat" },

    { "lt",            NULL, 0, AV_OPT_TYPE_CONST, { .i64 = QUANT_MAT_LT },

        0, 0, VE, .unit = "quant_mat" },

    { "standard",      NULL, 0, AV_OPT_TYPE_CONST, { .i64 = QUANT_MAT_STANDARD },

        0, 0, VE, .unit = "quant_mat" },

    { "hq",            NULL, 0, AV_OPT_TYPE_CONST, { .i64 = QUANT_MAT_HQ },

        0, 0, VE, .unit = "quant_mat" },

    { "default",       NULL, 0, AV_OPT_TYPE_CONST, { .i64 = QUANT_MAT_DEFAULT },

        0, 0, VE, .unit = "quant_mat" },

    { "alpha_bits", "bits for alpha plane", OFFSET(alpha_bits), AV_OPT_TYPE_INT,

        { .i64 = 16 }, 0, 16, VE },

    { NULL }

};

static const AVClass proresenc_class = {

    .class_name = "ProRes encoder",

    .item_name  = av_default_item_name,

    .option     = options,

    .version    = LIBAVUTIL_VERSION_INT,

};

const FFCodec ff_prores_ks_encoder = {

    .p.name         = "prores_ks",

    CODEC_LONG_NAME("Apple ProRes (iCodec Pro)"),

    .p.type         = AVMEDIA_TYPE_VIDEO,

    .p.id           = AV_CODEC_ID_PRORES,

    .priv_data_size = sizeof(ProresContext),

    .init           = encode_init,