TrellisPath *paths;
TrellisNode *node_buf;
TrellisNode **nodep_buf;
+ uint8_t *trellis_hash;
} ADPCMContext;
#define FREEZE_INTERVAL 128
FF_ALLOC_OR_GOTO(avctx, s->paths, max_paths * sizeof(*s->paths), error);
FF_ALLOC_OR_GOTO(avctx, s->node_buf, 2 * frontier * sizeof(*s->node_buf), error);
FF_ALLOC_OR_GOTO(avctx, s->nodep_buf, 2 * frontier * sizeof(*s->nodep_buf), error);
+ FF_ALLOC_OR_GOTO(avctx, s->trellis_hash, 65536 * sizeof(*s->trellis_hash), error);
}
switch(avctx->codec->id) {
av_freep(&s->paths);
av_freep(&s->node_buf);
av_freep(&s->nodep_buf);
+ av_freep(&s->trellis_hash);
return -1;
}
av_freep(&s->paths);
av_freep(&s->node_buf);
av_freep(&s->nodep_buf);
+ av_freep(&s->trellis_hash);
return 0;
}
TrellisNode **nodep_buf = s->nodep_buf;
TrellisNode **nodes = nodep_buf; // nodes[] is always sorted by .ssd
TrellisNode **nodes_next = nodep_buf + frontier;
- int pathn = 0, froze = -1, i, j, k;
+ 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;
int heap_pos = 0;
memset(nodes_next, 0, frontier*sizeof(TrellisNode*));
for(j=0; j<frontier && nodes[j]; j++) {
- // higher j have higher ssd already, so they're unlikely to use a suboptimal next sample too
+ // higher j have higher ssd already, so they're likely to yield a suboptimal next sample too
const int range = (j < frontier/2) ? 1 : 0;
const int step = nodes[j]->step;
int nidx;
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;\
+ /* Check for wraparound, skip such samples completely. \
+ * Note, changing ssd to a 64 bit variable would be \
+ * simpler, avoiding this check, but it's slower on \
+ * x86 32 bit at the moment. */\
+ if (ssd < nodes[j]->ssd)\
+ goto next_##NAME;\
/* Collapse any two states with the same previous sample value. \
* One could also distinguish states by step and by 2nd to last
- * sample, but the effects of that are negligible. */\
- for(k=0; k<frontier && nodes_next[k]; k++) {\
- if(dec_sample == nodes_next[k]->sample1) {\
- assert(ssd >= nodes_next[k]->ssd);\
- goto next_##NAME;\
- }\
- }\
+ * sample, but the effects of that are negligible.
+ * Since nodes in the previous generation are iterated
+ * through a heap, they're roughly ordered from better to
+ * worse, but not strictly ordered. Therefore, an earlier
+ * node with the same sample value is better in most cases
+ * (and thus the current is skipped), but not strictly
+ * in all cases. Only skipping samples where ssd >=
+ * ssd of the earlier node with the same sample gives
+ * slightly worse quality, though, for some reason. */ \
+ h = &hash[(uint16_t) dec_sample];\
+ if (*h == generation)\
+ goto next_##NAME;\
if (heap_pos < frontier) {\
pos = heap_pos++;\
} else {\
- /* Find the largest node in the heap, which is one \
- * of the leaf nodes. */\
- int maxpos = 0;\
- uint32_t max_ssd = 0;\
- for (k = frontier >> 1; k < frontier; k++) {\
- if (nodes_next[k]->ssd > max_ssd) {\
- maxpos = k;\
- max_ssd = nodes_next[k]->ssd;\
- }\
- }\
- pos = maxpos;\
- if (ssd > max_ssd)\
+ /* Try to replace one of the leaf nodes with the new \
+ * one, but try a different slot each time. */\
+ 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) {\
- assert(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;\
- /* Sift the newly inserted node down in the heap to \
+ if(!u) {\
+ assert(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;\
+ /* Sift the newly inserted node up in the heap to \
* restore the heap property. */\
while (pos > 0) {\
int parent = (pos - 1) >> 1;\
nodes = nodes_next;
nodes_next = u;
+ generation++;
+ if (generation == 255) {
+ memset(hash, 0xff, 65536 * sizeof(*hash));
+ generation = 0;
+ }
+
// prevent overflow
if(nodes[0]->ssd > (1<<28)) {
for(j=1; j<frontier && nodes[j]; j++)
#if CONFIG_ENCODERS
#define ADPCM_ENCODER(id,name,long_name_) \
-AVCodec name ## _encoder = { \
+AVCodec ff_ ## name ## _encoder = { \
#name, \
AVMEDIA_TYPE_AUDIO, \
id, \
#if CONFIG_DECODERS
#define ADPCM_DECODER(id,name,long_name_) \
-AVCodec name ## _decoder = { \
+AVCodec ff_ ## name ## _decoder = { \
#name, \
AVMEDIA_TYPE_AUDIO, \
id, \