changeset 11353:1ea249b4c6e7 libavcodec

Delay translating DCT tokens into coefficients until immediately before IDCT This is generally around 12% faster than the prior method of creating a linked list for each block as tokens are read, but can be anywhere from 8% to 28% faster depending on file and CPU.
author conrad
date Wed, 03 Mar 2010 23:27:43 +0000
parents 6e0af2cfdcfe
children 2a9acfd46715
files vp3.c
diffstat 1 files changed, 177 insertions(+), 178 deletions(-) [+]
line wrap: on
line diff
--- a/vp3.c	Wed Mar 03 23:27:40 2010 +0000
+++ b/vp3.c	Wed Mar 03 23:27:43 2010 +0000
@@ -44,15 +44,9 @@
 
 static av_cold int vp3_decode_end(AVCodecContext *avctx);
 
-typedef struct Coeff {
-    struct Coeff *next;
-    DCTELEM coeff;
-    uint8_t index;
-} Coeff;
-
 //FIXME split things out into their own arrays
 typedef struct Vp3Fragment {
-    Coeff *next_coeff;
+    int16_t dc;
     uint8_t coding_method;
     int8_t motion_x;
     int8_t motion_y;
@@ -168,9 +162,6 @@
     int fragment_height;
 
     Vp3Fragment *all_fragments;
-    uint8_t *coeff_counts;
-    Coeff *coeffs;
-    Coeff *next_coeff;
     int fragment_start[3];
     int data_offset[3];
 
@@ -184,18 +175,38 @@
     uint8_t qr_size [2][3][64];
     uint16_t qr_base[2][3][64];
 
+    /**
+     * This is a list of all tokens in bitstream order. Reordering takes place
+     * by pulling from each level during IDCT. As a consequence, IDCT must be
+     * in Hilbert order, making the minimum slice height 64 for 4:2:0 and 32
+     * otherwise. The 32 different tokens with up to 12 bits of extradata are
+     * collapsed into 3 types, packed as follows:
+     *   (from the low to high bits)
+     *
+     * 2 bits: type (0,1,2)
+     *   0: EOB run, 14 bits for run length (12 needed)
+     *   1: zero run, 7 bits for run length
+     *                7 bits for the next coefficient (3 needed)
+     *   2: coefficient, 14 bits (11 needed)
+     *
+     * Coefficients are signed, so are packed in the highest bits for automatic
+     * sign extension.
+     */
+    int16_t *dct_tokens[3][64];
+    int16_t *dct_tokens_base;
+#define TOKEN_EOB(eob_run)              ((eob_run) << 2)
+#define TOKEN_ZERO_RUN(coeff, zero_run) (((coeff) << 9) + ((zero_run) << 2) + 1)
+#define TOKEN_COEFF(coeff)              (((coeff) << 2) + 2)
+
+    /**
+     * number of blocks that contain DCT coefficients at the given level or higher
+     */
+    int num_coded_frags[3][64];
+    int total_num_coded_frags;
+
     /* this is a list of indexes into the all_fragments array indicating
      * which of the fragments are coded */
-    int *coded_fragment_list;
-    int coded_fragment_list_index;
-
-    /* track which fragments have already been decoded; called 'fast'
-     * because this data structure avoids having to iterate through every
-     * fragment in coded_fragment_list; once a fragment has been fully
-     * decoded, it is removed from this list */
-    int *fast_fragment_list;
-    int fragment_list_y_head;
-    int fragment_list_c_head;
+    int *coded_fragment_list[3];
 
     VLC dc_vlc[16];
     VLC ac_vlc_1[16];
@@ -222,11 +233,6 @@
      * is coded. */
     unsigned char *macroblock_coding;
 
-    int first_coded_y_fragment;
-    int first_coded_c_fragment;
-    int last_coded_y_fragment;
-    int last_coded_c_fragment;
-
     uint8_t edge_emu_buffer[9*2048]; //FIXME dynamic alloc
     int8_t qscale_table[2048]; //FIXME dynamic alloc (width+15)/16
 
@@ -366,16 +372,11 @@
     int i;
 
     /* zero out all of the fragment information */
-    s->coded_fragment_list_index = 0;
     for (i = 0; i < s->fragment_count; i++) {
-        s->coeff_counts[i] = 0;
         s->all_fragments[i].motion_x = 127;
         s->all_fragments[i].motion_y = 127;
-        s->all_fragments[i].next_coeff= NULL;
+        s->all_fragments[i].dc = 0;
         s->all_fragments[i].qpi = 0;
-        s->coeffs[i].index=
-        s->coeffs[i].coeff=0;
-        s->coeffs[i].next= NULL;
     }
 }
 
@@ -459,7 +460,6 @@
     int current_superblock = 0;
     int current_run = 0;
     int num_partial_superblocks = 0;
-    int first_c_fragment_seen;
 
     int i, j;
     int current_fragment;
@@ -543,16 +543,13 @@
 
     /* figure out which fragments are coded; iterate through each
      * superblock (all planes) */
-    s->coded_fragment_list_index = 0;
-    s->next_coeff= s->coeffs + s->fragment_count;
-    s->first_coded_y_fragment = s->first_coded_c_fragment = 0;
-    s->last_coded_y_fragment = s->last_coded_c_fragment = -1;
-    first_c_fragment_seen = 0;
+    s->total_num_coded_frags = 0;
     memset(s->macroblock_coding, MODE_COPY, s->macroblock_count);
 
     for (plane = 0; plane < 3; plane++) {
         int sb_start = (int[]){ 0, s->u_superblock_start, s->v_superblock_start }[plane];
         int sb_end = sb_start + (plane ? s->c_superblock_count : s->y_superblock_count);
+        int num_coded_frags = 0;
 
     for (i = sb_start; i < sb_end; i++) {
 
@@ -586,15 +583,8 @@
                          * the next phase */
                         s->all_fragments[current_fragment].coding_method =
                             MODE_INTER_NO_MV;
-                        s->all_fragments[current_fragment].next_coeff= s->coeffs + current_fragment;
-                        s->coded_fragment_list[s->coded_fragment_list_index] =
+                        s->coded_fragment_list[plane][num_coded_frags++] =
                             current_fragment;
-                        if (plane && !first_c_fragment_seen) {
-                            s->first_coded_c_fragment = s->coded_fragment_list_index;
-                            s->last_coded_y_fragment = s->first_coded_c_fragment - 1;
-                            first_c_fragment_seen = 1;
-                        }
-                        s->coded_fragment_list_index++;
                     } else {
                         /* not coded; copy this fragment from the prior frame */
                         s->all_fragments[current_fragment].coding_method =
@@ -603,34 +593,12 @@
             }
         }
     }
-    }
-
-    if (!first_c_fragment_seen)
-        /* only Y fragments coded in this frame */
-        s->last_coded_y_fragment = s->coded_fragment_list_index - 1;
-    else
-        /* end the list of coded C fragments */
-        s->last_coded_c_fragment = s->coded_fragment_list_index - 1;
-
-    for (i = 0; i < s->fragment_count - 1; i++) {
-        s->fast_fragment_list[i] = i + 1;
+        s->total_num_coded_frags += num_coded_frags;
+        for (i = 0; i < 64; i++)
+            s->num_coded_frags[plane][i] = num_coded_frags;
+        if (plane < 2)
+            s->coded_fragment_list[plane+1] = s->coded_fragment_list[plane] + num_coded_frags;
     }
-    s->fast_fragment_list[s->fragment_count - 1] = -1;
-
-    if (s->last_coded_y_fragment == -1)
-        s->fragment_list_y_head = -1;
-    else {
-        s->fragment_list_y_head = s->first_coded_y_fragment;
-        s->fast_fragment_list[s->last_coded_y_fragment] = -1;
-    }
-
-    if (s->last_coded_c_fragment == -1)
-        s->fragment_list_c_head = -1;
-    else {
-        s->fragment_list_c_head = s->first_coded_c_fragment;
-        s->fast_fragment_list[s->last_coded_c_fragment] = -1;
-    }
-
     return 0;
 }
 
@@ -887,7 +855,7 @@
 static int unpack_block_qpis(Vp3DecodeContext *s, GetBitContext *gb)
 {
     int qpi, i, j, bit, run_length, blocks_decoded, num_blocks_at_qpi;
-    int num_blocks = s->coded_fragment_list_index;
+    int num_blocks = s->total_num_coded_frags;
 
     for (qpi = 0; qpi < s->nqps-1 && num_blocks > 0; qpi++) {
         i = blocks_decoded = num_blocks_at_qpi = 0;
@@ -904,11 +872,11 @@
                 num_blocks_at_qpi += run_length;
 
             for (j = 0; j < run_length; i++) {
-                if (i >= s->coded_fragment_list_index)
+                if (i >= s->total_num_coded_frags)
                     return -1;
 
-                if (s->all_fragments[s->coded_fragment_list[i]].qpi == qpi) {
-                    s->all_fragments[s->coded_fragment_list[i]].qpi += bit;
+                if (s->all_fragments[s->coded_fragment_list[0][i]].qpi == qpi) {
+                    s->all_fragments[s->coded_fragment_list[0][i]].qpi += bit;
                     j++;
                 }
             }
@@ -939,49 +907,40 @@
  */
 static int unpack_vlcs(Vp3DecodeContext *s, GetBitContext *gb,
                         VLC *table, int coeff_index,
-                        int y_plane,
+                        int plane,
                         int eob_run)
 {
-    int i;
+    int i, j = 0;
     int token;
     int zero_run = 0;
     DCTELEM coeff = 0;
-    Vp3Fragment *fragment;
     int bits_to_get;
-    int next_fragment;
-    int previous_fragment;
-    int fragment_num;
-    int *list_head;
+    int blocks_ended;
+    int coeff_i = 0;
+    int num_coeffs = s->num_coded_frags[plane][coeff_index];
+    int16_t *dct_tokens = s->dct_tokens[plane][coeff_index];
 
     /* local references to structure members to avoid repeated deferences */
-    uint8_t *perm= s->scantable.permutated;
-    int *coded_fragment_list = s->coded_fragment_list;
+    int *coded_fragment_list = s->coded_fragment_list[plane];
     Vp3Fragment *all_fragments = s->all_fragments;
-    uint8_t *coeff_counts = s->coeff_counts;
     VLC_TYPE (*vlc_table)[2] = table->table;
-    int *fast_fragment_list = s->fast_fragment_list;
+
+    if (num_coeffs < 0)
+        av_log(s->avctx, AV_LOG_ERROR, "Invalid number of coefficents at level %d\n", coeff_index);
 
-    if (y_plane) {
-        next_fragment = s->fragment_list_y_head;
-        list_head = &s->fragment_list_y_head;
+    if (eob_run > num_coeffs) {
+        coeff_i = blocks_ended = num_coeffs;
+        eob_run -= num_coeffs;
     } else {
-        next_fragment = s->fragment_list_c_head;
-        list_head = &s->fragment_list_c_head;
+        coeff_i = blocks_ended = eob_run;
+        eob_run = 0;
     }
 
-    i = next_fragment;
-    previous_fragment = -1;  /* this indicates that the previous fragment is actually the list head */
-    while (i != -1) {
-        fragment_num = coded_fragment_list[i];
+    // insert fake EOB token to cover the split between planes or zzi
+    if (blocks_ended)
+        dct_tokens[j++] = blocks_ended << 2;
 
-        if (coeff_counts[fragment_num] > coeff_index) {
-            previous_fragment = i;
-            i = fast_fragment_list[i];
-            continue;
-        }
-        fragment = &all_fragments[fragment_num];
-
-        if (!eob_run) {
+    while (coeff_i < num_coeffs) {
             /* decode a VLC into a token */
             token = get_vlc2(gb, vlc_table, 5, 3);
             /* use the token to get a zero run, a coefficient, and an eob run */
@@ -989,7 +948,20 @@
                 eob_run = eob_run_base[token];
                 if (eob_run_get_bits[token])
                     eob_run += get_bits(gb, eob_run_get_bits[token]);
-                coeff = zero_run = 0;
+
+                // record only the number of blocks ended in this plane,
+                // any spill will be recorded in the next plane.
+                if (eob_run > num_coeffs - coeff_i) {
+                    dct_tokens[j++] = TOKEN_EOB(num_coeffs - coeff_i);
+                    blocks_ended   += num_coeffs - coeff_i;
+                    eob_run        -= num_coeffs - coeff_i;
+                    coeff_i         = num_coeffs;
+                } else {
+                    dct_tokens[j++] = TOKEN_EOB(eob_run);
+                    blocks_ended   += eob_run;
+                    coeff_i        += eob_run;
+                    eob_run = 0;
+                }
             } else {
                 bits_to_get = coeff_get_bits[token];
                 if (bits_to_get)
@@ -999,33 +971,48 @@
                 zero_run = zero_run_base[token];
                 if (zero_run_get_bits[token])
                     zero_run += get_bits(gb, zero_run_get_bits[token]);
-            }
-        }
+
+                if (zero_run) {
+                    dct_tokens[j++] = TOKEN_ZERO_RUN(coeff, zero_run);
+                } else {
+                    // Save DC into the fragment structure. DC prediction is
+                    // done in raster order, so the actual DC can't be in with
+                    // other tokens. We still need the token in dct_tokens[]
+                    // however, or else the structure collapses on itself.
+                    if (!coeff_index)
+                        all_fragments[coded_fragment_list[coeff_i]].dc = coeff;
 
-        if (!eob_run) {
-            coeff_counts[fragment_num] += zero_run;
-            if (coeff_counts[fragment_num] < 64){
-                fragment->next_coeff->coeff= coeff;
-                fragment->next_coeff->index= perm[coeff_counts[fragment_num]++]; //FIXME perm here already?
-                fragment->next_coeff->next= s->next_coeff;
-                s->next_coeff->next=NULL;
-                fragment->next_coeff= s->next_coeff++;
+                    dct_tokens[j++] = TOKEN_COEFF(coeff);
+                }
+
+                if (coeff_index + zero_run > 64) {
+                    av_log(s->avctx, AV_LOG_ERROR, "Invalid zero run of %d with"
+                           " %d coeffs left\n", zero_run, 64-coeff_index);
+                    zero_run = 64 - coeff_index;
+                }
+
+                // zero runs code multiple coefficients,
+                // so don't try to decode coeffs for those higher levels
+                for (i = coeff_index+1; i <= coeff_index+zero_run; i++)
+                    s->num_coded_frags[plane][i]--;
+                coeff_i++;
             }
-            /* previous fragment is now this fragment */
-            previous_fragment = i;
-        } else {
-            coeff_counts[fragment_num] |= 128;
-            eob_run--;
-            /* remove this fragment from the list */
-            if (previous_fragment != -1)
-                fast_fragment_list[previous_fragment] = fast_fragment_list[i];
-            else
-                *list_head = fast_fragment_list[i];
-            /* previous fragment remains unchanged */
-        }
+    }
+
+    if (blocks_ended > s->num_coded_frags[plane][coeff_index])
+        av_log(s->avctx, AV_LOG_ERROR, "More blocks ended than coded!\n");
 
-        i = fast_fragment_list[i];
-    }
+    // decrement the number of blocks that have higher coeffecients for each
+    // EOB run at this level
+    if (blocks_ended)
+        for (i = coeff_index+1; i < 64; i++)
+            s->num_coded_frags[plane][i] -= blocks_ended;
+
+    // setup the next buffer
+    if (plane < 2)
+        s->dct_tokens[plane+1][coeff_index] = dct_tokens + j;
+    else if (coeff_index < 63)
+        s->dct_tokens[0][coeff_index+1] = dct_tokens + j;
 
     return eob_run;
 }
@@ -1049,20 +1036,24 @@
     VLC *y_tables[64];
     VLC *c_tables[64];
 
+    s->dct_tokens[0][0] = s->dct_tokens_base;
+
     /* fetch the DC table indexes */
     dc_y_table = get_bits(gb, 4);
     dc_c_table = get_bits(gb, 4);
 
     /* unpack the Y plane DC coefficients */
     residual_eob_run = unpack_vlcs(s, gb, &s->dc_vlc[dc_y_table], 0,
-        1, residual_eob_run);
+        0, residual_eob_run);
 
     /* reverse prediction of the Y-plane DC coefficients */
     reverse_dc_prediction(s, 0, s->fragment_width, s->fragment_height);
 
     /* unpack the C plane DC coefficients */
     residual_eob_run = unpack_vlcs(s, gb, &s->dc_vlc[dc_c_table], 0,
-        0, residual_eob_run);
+        1, residual_eob_run);
+    residual_eob_run = unpack_vlcs(s, gb, &s->dc_vlc[dc_c_table], 0,
+        2, residual_eob_run);
 
     /* reverse prediction of the C-plane DC coefficients */
     if (!(s->avctx->flags & CODEC_FLAG_GRAY))
@@ -1097,13 +1088,13 @@
 
     /* decode all AC coefficents */
     for (i = 1; i <= 63; i++) {
-        if (s->fragment_list_y_head != -1)
             residual_eob_run = unpack_vlcs(s, gb, y_tables[i], i,
-                1, residual_eob_run);
+                0, residual_eob_run);
 
-        if (s->fragment_list_c_head != -1)
             residual_eob_run = unpack_vlcs(s, gb, c_tables[i], i,
-                0, residual_eob_run);
+                1, residual_eob_run);
+            residual_eob_run = unpack_vlcs(s, gb, c_tables[i], i,
+                2, residual_eob_run);
     }
 
     return 0;
@@ -1116,7 +1107,7 @@
  */
 #define COMPATIBLE_FRAME(x) \
   (compatible_frame[s->all_fragments[x].coding_method] == current_frame_type)
-#define DC_COEFF(u) (s->coeffs[u].index ? 0 : s->coeffs[u].coeff) //FIXME do somethin to simplify this
+#define DC_COEFF(u) s->all_fragments[u].dc
 
 static void reverse_dc_prediction(Vp3DecodeContext *s,
                                   int first_fragment,
@@ -1260,21 +1251,9 @@
                 }
 
                 /* at long last, apply the predictor */
-                if(s->coeffs[i].index){
-                    *s->next_coeff= s->coeffs[i];
-                    s->coeffs[i].index=0;
-                    s->coeffs[i].coeff=0;
-                    s->coeffs[i].next= s->next_coeff++;
-                }
-                s->coeffs[i].coeff += predicted_dc;
+                DC_COEFF(i) += predicted_dc;
                 /* save the DC */
                 last_dc[current_frame_type] = DC_COEFF(i);
-                if(DC_COEFF(i) && !(s->coeff_counts[i]&127)){
-                    s->coeff_counts[i]= 129;
-//                    s->all_fragments[i].next_coeff= s->next_coeff;
-                    s->coeffs[i].next= s->next_coeff;
-                    (s->next_coeff++)->next=NULL;
-                }
             }
         }
     }
@@ -1344,6 +1323,47 @@
 }
 
 /**
+ * Pulls DCT tokens from the 64 levels to decode and dequant the coefficients
+ * for the next block in coding order
+ */
+static inline int vp3_dequant(Vp3DecodeContext *s, Vp3Fragment *frag,
+                              int plane, int inter, DCTELEM block[64])
+{
+    int16_t *dequantizer = s->qmat[frag->qpi][inter][plane];
+    uint8_t *perm = s->scantable.permutated;
+    int i = 0;
+
+    do {
+        int token = *s->dct_tokens[plane][i];
+        switch (token & 3) {
+        case 0: // EOB
+            if (--token < 4) // 0-3 are token types, so the EOB run must now be 0
+                s->dct_tokens[plane][i]++;
+            else
+                *s->dct_tokens[plane][i] = token & ~3;
+            goto end;
+        case 1: // zero run
+            s->dct_tokens[plane][i]++;
+            i += (token >> 2) & 0x7f;
+            block[perm[i]] = (token >> 9) * dequantizer[perm[i]];
+            i++;
+            break;
+        case 2: // coeff
+            block[perm[i]] = (token >> 2) * dequantizer[perm[i]];
+            s->dct_tokens[plane][i++]++;
+            break;
+        default:
+            av_log(s->avctx, AV_LOG_ERROR, "internal: invalid token type\n");
+            return i;
+        }
+    } while (i < 64);
+end:
+    // the actual DC+prediction is in the fragment structure
+    block[0] = frag->dc * s->qmat[0][inter][plane][0];
+    return i;
+}
+
+/**
  * called when all pixels up to row y are complete
  */
 static void vp3_draw_horiz_band(Vp3DecodeContext *s, int y)
@@ -1381,7 +1401,6 @@
 static void render_slice(Vp3DecodeContext *s, int slice)
 {
     int x, y, i, j;
-    int16_t *dequantizer;
     LOCAL_ALIGNED_16(DCTELEM, block, [64]);
     int motion_x = 0xdeadbeef, motion_y = 0xdeadbeef;
     int motion_halfpel_index;
@@ -1436,6 +1455,7 @@
 
                 /* transform if this block was coded */
                 if (s->all_fragments[i].coding_method != MODE_COPY) {
+                    int intra = s->all_fragments[i].coding_method == MODE_INTRA;
 
                     if ((s->all_fragments[i].coding_method == MODE_USING_GOLDEN) ||
                         (s->all_fragments[i].coding_method == MODE_GOLDEN_MV))
@@ -1499,27 +1519,10 @@
                                 motion_source + stride + 1 + d,
                                 stride, 8);
                         }
-                        dequantizer = s->qmat[s->all_fragments[i].qpi][1][plane];
-                    }else{
-                        dequantizer = s->qmat[s->all_fragments[i].qpi][0][plane];
                     }
 
-                    /* dequantize the DCT coefficients */
-                    if(s->avctx->idct_algo==FF_IDCT_VP3){
-                        Coeff *coeff= s->coeffs + i;
                         s->dsp.clear_block(block);
-                        while(coeff->next){
-                            block[coeff->index]= coeff->coeff * dequantizer[coeff->index];
-                            coeff= coeff->next;
-                        }
-                    }else{
-                        Coeff *coeff= s->coeffs + i;
-                        s->dsp.clear_block(block);
-                        while(coeff->next){
-                            block[coeff->index]= (coeff->coeff * dequantizer[coeff->index] + 2)>>2;
-                            coeff= coeff->next;
-                        }
-                    }
+                        vp3_dequant(s, s->all_fragments + i, plane, !intra, block);
 
                     /* invert DCT and place (or add) in final output */
 
@@ -1624,12 +1627,10 @@
     s->fragment_start[2] = s->fragment_width * s->fragment_height * 5 / 4;
 
     s->all_fragments = av_malloc(s->fragment_count * sizeof(Vp3Fragment));
-    s->coeff_counts = av_malloc(s->fragment_count * sizeof(*s->coeff_counts));
-    s->coeffs = av_malloc(s->fragment_count * sizeof(Coeff) * 65);
-    s->coded_fragment_list = av_malloc(s->fragment_count * sizeof(int));
-    s->fast_fragment_list = av_malloc(s->fragment_count * sizeof(int));
-    if (!s->superblock_coding || !s->all_fragments || !s->coeff_counts ||
-        !s->coeffs || !s->coded_fragment_list || !s->fast_fragment_list) {
+    s->coded_fragment_list[0] = av_malloc(s->fragment_count * sizeof(int));
+    s->dct_tokens_base = av_malloc(64*s->fragment_count * sizeof(*s->dct_tokens_base));
+    if (!s->superblock_coding || !s->all_fragments || !s->dct_tokens_base ||
+        !s->coded_fragment_list[0]) {
         vp3_decode_end(avctx);
         return -1;
     }
@@ -1928,10 +1929,8 @@
 
     av_free(s->superblock_coding);
     av_free(s->all_fragments);
-    av_free(s->coeff_counts);
-    av_free(s->coeffs);
-    av_free(s->coded_fragment_list);
-    av_free(s->fast_fragment_list);
+    av_free(s->coded_fragment_list[0]);
+    av_free(s->dct_tokens_base);
     av_free(s->superblock_fragments);
     av_free(s->macroblock_coding);