static void adpcm_compress_trellis(AVCodecContext *avctx,

                                   const int16_t *samples, uint8_t *dst,

                                   ADPCMChannelStatus *c, int n, int stride)

{

    

    ADPCMEncodeContext *s = avctx->priv_data;

    const int frontier = 1 << avctx->trellis;

    const int version  = avctx->codec->id;

    TrellisPath *paths       = s->paths, *p;

    TrellisNode *node_buf    = s->node_buf;

    TrellisNode **nodep_buf  = s->nodep_buf;

    TrellisNode **nodes      = nodep_buf; 

    TrellisNode **nodes_next = nodep_buf + frontier;

    int pathn = 0, froze = -1, i, j, k, generation = 0;

    uint8_t *hash = s->trellis_hash;

    memset(hash, 0xff, 65536 * sizeof(*hash));



    memset(nodep_buf, 0, 2 * frontier * sizeof(*nodep_buf));

    nodes[0]          = node_buf + frontier;

    nodes[0]->ssd     = 0;

    nodes[0]->path    = 0;

    nodes[0]->step    = c->step_index;

    nodes[0]->sample1 = c->sample1;

    nodes[0]->sample2 = c->sample2;

    if (version == AV_CODEC_ID_ADPCM_IMA_WAV ||

        version == AV_CODEC_ID_ADPCM_IMA_QT  ||

        version == AV_CODEC_ID_ADPCM_SWF)

        nodes[0]->sample1 = c->prev_sample;

    if (version == AV_CODEC_ID_ADPCM_MS)

        nodes[0]->step = c->idelta;

    if (version == AV_CODEC_ID_ADPCM_YAMAHA) {

        if (c->step == 0) {

            nodes[0]->step    = 127;

            nodes[0]->sample1 = 0;

        } else {

            nodes[0]->step    = c->step;

            nodes[0]->sample1 = c->predictor;

        }

    }



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

        TrellisNode *t = node_buf + frontier*(i&1);

        TrellisNode **u;

        int sample   = samples[i * stride];

        int heap_pos = 0;

        memset(nodes_next, 0, frontier * sizeof(TrellisNode*));

        for (j = 0; j < frontier && nodes[j]; j++) {

            

            

            const int range = (j < frontier / 2) ? 1 : 0;

            const int step  = nodes[j]->step;

            int nidx;

            if (version == AV_CODEC_ID_ADPCM_MS) {

                const int predictor = ((nodes[j]->sample1 * c->coeff1) +

                                       (nodes[j]->sample2 * c->coeff2)) / 64;

                const int div  = (sample - predictor) / step;

                const int nmin = av_clip(div-range, -8, 6);

                const int nmax = av_clip(div+range, -7, 7);

                for (nidx = nmin; nidx <= nmax; nidx++) {

                    const int nibble = nidx & 0xf;

                    int dec_sample   = predictor + nidx * step;

#define STORE_NODE(NAME, STEP_INDEX)\

                    int d;\

                    uint32_t ssd;\

                    int pos;\

                    TrellisNode *u;\

                    uint8_t *h;\

                    dec_sample = av_clip_int16(dec_sample);\

                    d = sample - dec_sample;\

                    ssd = nodes[j]->ssd + d*d;\

                    





\

                    if (ssd < nodes[j]->ssd)\

                        goto next_##NAME;\

                    



















 \

                    h = &hash[(uint16_t) dec_sample];\

                    if (*h == generation)\

                        goto next_##NAME;\

                    if (heap_pos < frontier) {\

                        pos = heap_pos++;\

                    } else {\

                        

\

                        pos = (frontier >> 1) +\

                              (heap_pos & ((frontier >> 1) - 1));\

                        if (ssd > nodes_next[pos]->ssd)\

                            goto next_##NAME;\

                        heap_pos++;\

                    }\

                    *h = generation;\

                    u  = nodes_next[pos];\

                    if (!u) {\

                        av_assert1(pathn < FREEZE_INTERVAL << avctx->trellis);\

                        u = t++;\

                        nodes_next[pos] = u;\

                        u->path = pathn++;\

                    }\

                    u->ssd  = ssd;\

                    u->step = STEP_INDEX;\

                    u->sample2 = nodes[j]->sample1;\

                    u->sample1 = dec_sample;\

                    paths[u->path].nibble = nibble;\

                    paths[u->path].prev   = nodes[j]->path;\

                    

\

                    while (pos > 0) {\

                        int parent = (pos - 1) >> 1;\

                        if (nodes_next[parent]->ssd <= ssd)\

                            break;\

                        FFSWAP(TrellisNode*, nodes_next[parent], nodes_next[pos]);\

                        pos = parent;\

                    }\

                    next_##NAME:;

                    STORE_NODE(ms, FFMAX(16,

                               (ff_adpcm_AdaptationTable[nibble] * step) >> 8));

                }

            } else if (version == AV_CODEC_ID_ADPCM_IMA_WAV ||

                       version == AV_CODEC_ID_ADPCM_IMA_QT  ||

                       version == AV_CODEC_ID_ADPCM_SWF) {

#define LOOP_NODES(NAME, STEP_TABLE, STEP_INDEX)\

                const int predictor = nodes[j]->sample1;\

                const int div = (sample - predictor) * 4 / STEP_TABLE;\

                int nmin = av_clip(div - range, -7, 6);\

                int nmax = av_clip(div + range, -6, 7);\

                if (nmin <= 0)\

                    nmin--; \

                if (nmax < 0)\

                    nmax--;\

                for (nidx = nmin; nidx <= nmax; nidx++) {\

                    const int nibble = nidx < 0 ? 7 - nidx : nidx;\

                    int dec_sample = predictor +\

                                    (STEP_TABLE *\

                                     ff_adpcm_yamaha_difflookup[nibble]) / 8;\

                    STORE_NODE(NAME, STEP_INDEX);\

                }

                LOOP_NODES(ima, ff_adpcm_step_table[step],

                           av_clip(step + ff_adpcm_index_table[nibble], 0, 88));

            } else { 

                LOOP_NODES(yamaha, step,

                           av_clip((step * ff_adpcm_yamaha_indexscale[nibble]) >> 8,

                                   127, 24567));

#undef LOOP_NODES

#undef STORE_NODE

            }

        }



        u = nodes;

        nodes = nodes_next;

        nodes_next = u;



        generation++;

        if (generation == 255) {

            memset(hash, 0xff, 65536 * sizeof(*hash));

            generation = 0;

        }



        

        if (nodes[0]->ssd > (1 << 28)) {

            for (j = 1; j < frontier && nodes[j]; j++)

                nodes[j]->ssd -= nodes[0]->ssd;

            nodes[0]->ssd = 0;

        }



        

        if (i == froze + FREEZE_INTERVAL) {

            p = &paths[nodes[0]->path];

            for (k = i; k > froze; k--) {

                dst[k] = p->nibble;

                p = &paths[p->prev];

            }

            froze = i;

            pathn = 0;

            

            

            

            memset(nodes + 1, 0, (frontier - 1) * sizeof(TrellisNode*));

        }

    }



    p = &paths[nodes[0]->path];

    for (i = n - 1; i > froze; i--) {

        dst[i] = p->nibble;

        p = &paths[p->prev];

    }



    c->predictor  = nodes[0]->sample1;

    c->sample1    = nodes[0]->sample1;

    c->sample2    = nodes[0]->sample2;

    c->step_index = nodes[0]->step;

    c->step       = nodes[0]->step;

    c->idelta     = nodes[0]->step;

}
