git.sesse.net Git - ffmpeg/blob - libavcodec/svq1.c

   1 /*
   2  *
   3  * Copyright (C) 2002 the xine project
   4  * Copyright (C) 2002 the ffmpeg project
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  *
  20  * (SVQ1 Decoder)
  21  * Ported to mplayer by Arpi <arpi@thot.banki.hu>
  22  * Ported to libavcodec by Nick Kurshev <nickols_k@mail.ru>
  23  *
  24  * SVQ1 Encoder (c) 2004 Mike Melanson <melanson@pcisys.net>
  25  */
  26
  27 /**
  28  * @file svq1.c
  29  * Sorenson Vector Quantizer #1 (SVQ1) video codec.
  30  * For more information of the SVQ1 algorithm, visit:
  31  *   http://www.pcisys.net/~melanson/codecs/
  32  */
  33
  34
  35 //#define DEBUG_SVQ1
  36 #include <stdio.h>
  37 #include <stdlib.h>
  38 #include <string.h>
  39 #include <unistd.h>
  40 #include <limits.h>
  41
  42 #include "common.h"
  43 #include "avcodec.h"
  44 #include "dsputil.h"
  45 #include "mpegvideo.h"
  46 #include "bswap.h"
  47
  48 #undef NDEBUG
  49 #include <assert.h>
  50
  51 extern const uint8_t mvtab[33][2];
  52
  53 static VLC svq1_block_type;
  54 static VLC svq1_motion_component;
  55 static VLC svq1_intra_multistage[6];
  56 static VLC svq1_inter_multistage[6];
  57 static VLC svq1_intra_mean;
  58 static VLC svq1_inter_mean;
  59
  60 #define SVQ1_BLOCK_SKIP         0
  61 #define SVQ1_BLOCK_INTER        1
  62 #define SVQ1_BLOCK_INTER_4V     2
  63 #define SVQ1_BLOCK_INTRA        3
  64
  65 typedef struct SVQ1Context {
  66     MpegEncContext m; // needed for motion estimation, should not be used for anything else, the idea is to make the motion estimation eventually independant of MpegEncContext, so this will be removed then (FIXME/XXX)
  67     AVCodecContext *avctx;
  68     DSPContext dsp;
  69     AVFrame picture;
  70     AVFrame current_picture;
  71     AVFrame last_picture;
  72     PutBitContext pb;
  73     GetBitContext gb;
  74
  75     PutBitContext reorder_pb[6]; //why ooh why this sick breadth first order, everything is slower and more complex
  76
  77     int frame_width;
  78     int frame_height;
  79
  80     /* Y plane block dimensions */
  81     int y_block_width;
  82     int y_block_height;
  83
  84     /* U & V plane (C planes) block dimensions */
  85     int c_block_width;
  86     int c_block_height;
  87
  88     unsigned char *c_plane;
  89
  90     uint16_t *mb_type;
  91     uint32_t *dummy;
  92     int16_t (*motion_val8[3])[2];
  93     int16_t (*motion_val16[3])[2];
  94
  95     int64_t rd_total;
  96 } SVQ1Context;
  97
  98 /* motion vector (prediction) */
  99 typedef struct svq1_pmv_s {
 100   int            x;
 101   int            y;
 102 } svq1_pmv_t;
 103
 104 #include "svq1_cb.h"
 105 #include "svq1_vlc.h"
 106
 107 static const uint16_t checksum_table[256] = {
 108   0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,
 109   0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,
 110   0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
 111   0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE,
 112   0x2462, 0x3443, 0x0420, 0x1401, 0x64E6, 0x74C7, 0x44A4, 0x5485,
 113   0xA56A, 0xB54B, 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
 114   0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6, 0x5695, 0x46B4,
 115   0xB75B, 0xA77A, 0x9719, 0x8738, 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC,
 116   0x48C4, 0x58E5, 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823,
 117   0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969, 0xA90A, 0xB92B,
 118   0x5AF5, 0x4AD4, 0x7AB7, 0x6A96, 0x1A71, 0x0A50, 0x3A33, 0x2A12,
 119   0xDBFD, 0xCBDC, 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
 120   0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03, 0x0C60, 0x1C41,
 121   0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD, 0xAD2A, 0xBD0B, 0x8D68, 0x9D49,
 122   0x7E97, 0x6EB6, 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70,
 123   0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A, 0x9F59, 0x8F78,
 124   0x9188, 0x81A9, 0xB1CA, 0xA1EB, 0xD10C, 0xC12D, 0xF14E, 0xE16F,
 125   0x1080, 0x00A1, 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,
 126   0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C, 0xE37F, 0xF35E,
 127   0x02B1, 0x1290, 0x22F3, 0x32D2, 0x4235, 0x5214, 0x6277, 0x7256,
 128   0xB5EA, 0xA5CB, 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D,
 129   0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
 130   0xA7DB, 0xB7FA, 0x8799, 0x97B8, 0xE75F, 0xF77E, 0xC71D, 0xD73C,
 131   0x26D3, 0x36F2, 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,
 132   0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9, 0xB98A, 0xA9AB,
 133   0x5844, 0x4865, 0x7806, 0x6827, 0x18C0, 0x08E1, 0x3882, 0x28A3,
 134   0xCB7D, 0xDB5C, 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,
 135   0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0, 0x2AB3, 0x3A92,
 136   0xFD2E, 0xED0F, 0xDD6C, 0xCD4D, 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9,
 137   0x7C26, 0x6C07, 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
 138   0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA, 0x8FD9, 0x9FF8,
 139   0x6E17, 0x7E36, 0x4E55, 0x5E74, 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
 140 };
 141
 142 static const uint8_t string_table[256] = {
 143   0x00, 0xD5, 0x7F, 0xAA, 0xFE, 0x2B, 0x81, 0x54,
 144   0x29, 0xFC, 0x56, 0x83, 0xD7, 0x02, 0xA8, 0x7D,
 145   0x52, 0x87, 0x2D, 0xF8, 0xAC, 0x79, 0xD3, 0x06,
 146   0x7B, 0xAE, 0x04, 0xD1, 0x85, 0x50, 0xFA, 0x2F,
 147   0xA4, 0x71, 0xDB, 0x0E, 0x5A, 0x8F, 0x25, 0xF0,
 148   0x8D, 0x58, 0xF2, 0x27, 0x73, 0xA6, 0x0C, 0xD9,
 149   0xF6, 0x23, 0x89, 0x5C, 0x08, 0xDD, 0x77, 0xA2,
 150   0xDF, 0x0A, 0xA0, 0x75, 0x21, 0xF4, 0x5E, 0x8B,
 151   0x9D, 0x48, 0xE2, 0x37, 0x63, 0xB6, 0x1C, 0xC9,
 152   0xB4, 0x61, 0xCB, 0x1E, 0x4A, 0x9F, 0x35, 0xE0,
 153   0xCF, 0x1A, 0xB0, 0x65, 0x31, 0xE4, 0x4E, 0x9B,
 154   0xE6, 0x33, 0x99, 0x4C, 0x18, 0xCD, 0x67, 0xB2,
 155   0x39, 0xEC, 0x46, 0x93, 0xC7, 0x12, 0xB8, 0x6D,
 156   0x10, 0xC5, 0x6F, 0xBA, 0xEE, 0x3B, 0x91, 0x44,
 157   0x6B, 0xBE, 0x14, 0xC1, 0x95, 0x40, 0xEA, 0x3F,
 158   0x42, 0x97, 0x3D, 0xE8, 0xBC, 0x69, 0xC3, 0x16,
 159   0xEF, 0x3A, 0x90, 0x45, 0x11, 0xC4, 0x6E, 0xBB,
 160   0xC6, 0x13, 0xB9, 0x6C, 0x38, 0xED, 0x47, 0x92,
 161   0xBD, 0x68, 0xC2, 0x17, 0x43, 0x96, 0x3C, 0xE9,
 162   0x94, 0x41, 0xEB, 0x3E, 0x6A, 0xBF, 0x15, 0xC0,
 163   0x4B, 0x9E, 0x34, 0xE1, 0xB5, 0x60, 0xCA, 0x1F,
 164   0x62, 0xB7, 0x1D, 0xC8, 0x9C, 0x49, 0xE3, 0x36,
 165   0x19, 0xCC, 0x66, 0xB3, 0xE7, 0x32, 0x98, 0x4D,
 166   0x30, 0xE5, 0x4F, 0x9A, 0xCE, 0x1B, 0xB1, 0x64,
 167   0x72, 0xA7, 0x0D, 0xD8, 0x8C, 0x59, 0xF3, 0x26,
 168   0x5B, 0x8E, 0x24, 0xF1, 0xA5, 0x70, 0xDA, 0x0F,
 169   0x20, 0xF5, 0x5F, 0x8A, 0xDE, 0x0B, 0xA1, 0x74,
 170   0x09, 0xDC, 0x76, 0xA3, 0xF7, 0x22, 0x88, 0x5D,
 171   0xD6, 0x03, 0xA9, 0x7C, 0x28, 0xFD, 0x57, 0x82,
 172   0xFF, 0x2A, 0x80, 0x55, 0x01, 0xD4, 0x7E, 0xAB,
 173   0x84, 0x51, 0xFB, 0x2E, 0x7A, 0xAF, 0x05, 0xD0,
 174   0xAD, 0x78, 0xD2, 0x07, 0x53, 0x86, 0x2C, 0xF9
 175 };
 176
 177 #define SVQ1_PROCESS_VECTOR()\
 178     for (; level > 0; i++) {\
 179       /* process next depth */\
 180       if (i == m) {\
 181         m = n;\
 182         if (--level == 0)\
 183           break;\
 184       }\
 185       /* divide block if next bit set */\
 186       if (get_bits (bitbuf, 1) == 0)\
 187         break;\
 188       /* add child nodes */\
 189       list[n++] = list[i];\
 190       list[n++] = list[i] + (((level & 1) ? pitch : 1) << ((level / 2) + 1));\
 191     }
 192
 193 #define SVQ1_ADD_CODEBOOK()\
 194           /* add codebook entries to vector */\
 195           for (j=0; j < stages; j++) {\
 196             n3  = codebook[entries[j]] ^ 0x80808080;\
 197             n1 += ((n3 & 0xFF00FF00) >> 8);\
 198             n2 +=  (n3 & 0x00FF00FF);\
 199           }\
 200 \
 201           /* clip to [0..255] */\
 202           if (n1 & 0xFF00FF00) {\
 203             n3  = ((( n1 >> 15) & 0x00010001) | 0x01000100) - 0x00010001;\
 204             n1 += 0x7F007F00;\
 205             n1 |= (((~n1 >> 15) & 0x00010001) | 0x01000100) - 0x00010001;\
 206             n1 &= (n3 & 0x00FF00FF);\
 207           }\
 208 \
 209           if (n2 & 0xFF00FF00) {\
 210             n3  = ((( n2 >> 15) & 0x00010001) | 0x01000100) - 0x00010001;\
 211             n2 += 0x7F007F00;\
 212             n2 |= (((~n2 >> 15) & 0x00010001) | 0x01000100) - 0x00010001;\
 213             n2 &= (n3 & 0x00FF00FF);\
 214           }
 215
 216 #define SVQ1_DO_CODEBOOK_INTRA()\
 217       for (y=0; y < height; y++) {\
 218         for (x=0; x < (width / 4); x++, codebook++) {\
 219         n1 = n4;\
 220         n2 = n4;\
 221         SVQ1_ADD_CODEBOOK()\
 222         /* store result */\
 223         dst[x] = (n1 << 8) | n2;\
 224         }\
 225         dst += (pitch / 4);\
 226       }
 227
 228 #define SVQ1_DO_CODEBOOK_NONINTRA()\
 229       for (y=0; y < height; y++) {\
 230         for (x=0; x < (width / 4); x++, codebook++) {\
 231         n3 = dst[x];\
 232         /* add mean value to vector */\
 233         n1 = ((n3 & 0xFF00FF00) >> 8) + n4;\
 234         n2 =  (n3 & 0x00FF00FF)   + n4;\
 235         SVQ1_ADD_CODEBOOK()\
 236         /* store result */\
 237         dst[x] = (n1 << 8) | n2;\
 238         }\
 239         dst += (pitch / 4);\
 240       }
 241
 242 #define SVQ1_CALC_CODEBOOK_ENTRIES(cbook)\
 243       codebook = (const uint32_t *) cbook[level];\
 244       bit_cache = get_bits (bitbuf, 4*stages);\
 245       /* calculate codebook entries for this vector */\
 246       for (j=0; j < stages; j++) {\
 247         entries[j] = (((bit_cache >> (4*(stages - j - 1))) & 0xF) + 16*j) << (level + 1);\
 248       }\
 249       mean -= (stages * 128);\
 250       n4    = ((mean + (mean >> 31)) << 16) | (mean & 0xFFFF);
 251
 252 static int svq1_decode_block_intra (GetBitContext *bitbuf, uint8_t *pixels, int pitch ) {
 253   uint32_t    bit_cache;
 254   uint8_t    *list[63];
 255   uint32_t   *dst;
 256   const uint32_t *codebook;
 257   int         entries[6];
 258   int         i, j, m, n;
 259   int         mean, stages;
 260   unsigned    x, y, width, height, level;
 261   uint32_t    n1, n2, n3, n4;
 262
 263   /* initialize list for breadth first processing of vectors */
 264   list[0] = pixels;
 265
 266   /* recursively process vector */
 267   for (i=0, m=1, n=1, level=5; i < n; i++) {
 268     SVQ1_PROCESS_VECTOR();
 269
 270     /* destination address and vector size */
 271     dst = (uint32_t *) list[i];
 272     width = 1 << ((4 + level) /2);
 273     height = 1 << ((3 + level) /2);
 274
 275     /* get number of stages (-1 skips vector, 0 for mean only) */
 276     stages = get_vlc2(bitbuf, svq1_intra_multistage[level].table, 3, 3) - 1;
 277
 278     if (stages == -1) {
 279         for (y=0; y < height; y++) {
 280           memset (&dst[y*(pitch / 4)], 0, width);
 281         }
 282       continue;         /* skip vector */
 283     }
 284
 285     if ((stages > 0) && (level >= 4)) {
 286 #ifdef DEBUG_SVQ1
 287     av_log(s->avctx, AV_LOG_INFO, "Error (svq1_decode_block_intra): invalid vector: stages=%i level=%i\n",stages,level);
 288 #endif
 289       return -1;        /* invalid vector */
 290     }
 291
 292     mean = get_vlc2(bitbuf, svq1_intra_mean.table, 8, 3);
 293
 294     if (stages == 0) {
 295       for (y=0; y < height; y++) {
 296         memset (&dst[y*(pitch / 4)], mean, width);
 297       }
 298     } else {
 299       SVQ1_CALC_CODEBOOK_ENTRIES(svq1_intra_codebooks);
 300       SVQ1_DO_CODEBOOK_INTRA()
 301     }
 302   }
 303
 304   return 0;
 305 }
 306
 307 static int svq1_decode_block_non_intra (GetBitContext *bitbuf, uint8_t *pixels, int pitch ) {
 308   uint32_t    bit_cache;
 309   uint8_t    *list[63];
 310   uint32_t   *dst;
 311   const uint32_t *codebook;
 312   int         entries[6];
 313   int         i, j, m, n;
 314   int         mean, stages;
 315   int         x, y, width, height, level;
 316   uint32_t    n1, n2, n3, n4;
 317
 318   /* initialize list for breadth first processing of vectors */
 319   list[0] = pixels;
 320
 321   /* recursively process vector */
 322   for (i=0, m=1, n=1, level=5; i < n; i++) {
 323     SVQ1_PROCESS_VECTOR();
 324
 325     /* destination address and vector size */
 326     dst = (uint32_t *) list[i];
 327     width = 1 << ((4 + level) /2);
 328     height = 1 << ((3 + level) /2);
 329
 330     /* get number of stages (-1 skips vector, 0 for mean only) */
 331     stages = get_vlc2(bitbuf, svq1_inter_multistage[level].table, 3, 2) - 1;
 332
 333     if (stages == -1) continue; /* skip vector */
 334
 335     if ((stages > 0) && (level >= 4)) {
 336 #ifdef DEBUG_SVQ1
 337     av_log(s->avctx, AV_LOG_INFO, "Error (svq1_decode_block_non_intra): invalid vector: stages=%i level=%i\n",stages,level);
 338 #endif
 339       return -1;        /* invalid vector */
 340     }
 341
 342     mean = get_vlc2(bitbuf, svq1_inter_mean.table, 9, 3) - 256;
 343
 344     SVQ1_CALC_CODEBOOK_ENTRIES(svq1_inter_codebooks);
 345     SVQ1_DO_CODEBOOK_NONINTRA()
 346   }
 347   return 0;
 348 }
 349
 350 static int svq1_decode_motion_vector (GetBitContext *bitbuf, svq1_pmv_t *mv, svq1_pmv_t **pmv) {
 351   int         diff;
 352   int         i;
 353
 354   for (i=0; i < 2; i++) {
 355
 356     /* get motion code */
 357     diff = get_vlc2(bitbuf, svq1_motion_component.table, 7, 2);
 358     if(diff<0)
 359         return -1;
 360     else if(diff){
 361         if(get_bits1(bitbuf)) diff= -diff;
 362     }
 363
 364     /* add median of motion vector predictors and clip result */
 365     if (i == 1)
 366       mv->y = ((diff + mid_pred(pmv[0]->y, pmv[1]->y, pmv[2]->y)) << 26) >> 26;
 367     else
 368       mv->x = ((diff + mid_pred(pmv[0]->x, pmv[1]->x, pmv[2]->x)) << 26) >> 26;
 369   }
 370
 371   return 0;
 372 }
 373
 374 static void svq1_skip_block (uint8_t *current, uint8_t *previous, int pitch, int x, int y) {
 375   uint8_t *src;
 376   uint8_t *dst;
 377   int      i;
 378
 379   src = &previous[x + y*pitch];
 380   dst = current;
 381
 382   for (i=0; i < 16; i++) {
 383     memcpy (dst, src, 16);
 384     src += pitch;
 385     dst += pitch;
 386   }
 387 }
 388
 389 static int svq1_motion_inter_block (MpegEncContext *s, GetBitContext *bitbuf,
 390                                uint8_t *current, uint8_t *previous, int pitch,
 391                                svq1_pmv_t *motion, int x, int y) {
 392   uint8_t    *src;
 393   uint8_t    *dst;
 394   svq1_pmv_t  mv;
 395   svq1_pmv_t *pmv[3];
 396   int         result;
 397
 398   /* predict and decode motion vector */
 399   pmv[0] = &motion[0];
 400   if (y == 0) {
 401     pmv[1] =
 402     pmv[2] = pmv[0];
 403   }
 404   else {
 405     pmv[1] = &motion[(x / 8) + 2];
 406     pmv[2] = &motion[(x / 8) + 4];
 407   }
 408
 409   result = svq1_decode_motion_vector (bitbuf, &mv, pmv);
 410
 411   if (result != 0)
 412     return result;
 413
 414   motion[0].x           =
 415   motion[(x / 8) + 2].x =
 416   motion[(x / 8) + 3].x = mv.x;
 417   motion[0].y           =
 418   motion[(x / 8) + 2].y =
 419   motion[(x / 8) + 3].y = mv.y;
 420
 421   if(y + (mv.y >> 1)<0)
 422      mv.y= 0;
 423   if(x + (mv.x >> 1)<0)
 424      mv.x= 0;
 425
 426 #if 0
 427   int w= (s->width+15)&~15;
 428   int h= (s->height+15)&~15;
 429   if(x + (mv.x >> 1)<0 || y + (mv.y >> 1)<0 || x + (mv.x >> 1) + 16 > w || y + (mv.y >> 1) + 16> h)
 430       av_log(s->avctx, AV_LOG_INFO, "%d %d %d %d\n", x, y, x + (mv.x >> 1), y + (mv.y >> 1));
 431 #endif
 432
 433   src = &previous[(x + (mv.x >> 1)) + (y + (mv.y >> 1))*pitch];
 434   dst = current;
 435
 436   s->dsp.put_pixels_tab[0][((mv.y & 1) << 1) | (mv.x & 1)](dst,src,pitch,16);
 437
 438   return 0;
 439 }
 440
 441 static int svq1_motion_inter_4v_block (MpegEncContext *s, GetBitContext *bitbuf,
 442                                   uint8_t *current, uint8_t *previous, int pitch,
 443                                   svq1_pmv_t *motion,int x, int y) {
 444   uint8_t    *src;
 445   uint8_t    *dst;
 446   svq1_pmv_t  mv;
 447   svq1_pmv_t *pmv[4];
 448   int         i, result;
 449
 450   /* predict and decode motion vector (0) */
 451   pmv[0] = &motion[0];
 452   if (y == 0) {
 453     pmv[1] =
 454     pmv[2] = pmv[0];
 455   }
 456   else {
 457     pmv[1] = &motion[(x / 8) + 2];
 458     pmv[2] = &motion[(x / 8) + 4];
 459   }
 460
 461   result = svq1_decode_motion_vector (bitbuf, &mv, pmv);
 462
 463   if (result != 0)
 464     return result;
 465
 466   /* predict and decode motion vector (1) */
 467   pmv[0] = &mv;
 468   if (y == 0) {
 469     pmv[1] =
 470     pmv[2] = pmv[0];
 471   }
 472   else {
 473     pmv[1] = &motion[(x / 8) + 3];
 474   }
 475   result = svq1_decode_motion_vector (bitbuf, &motion[0], pmv);
 476
 477   if (result != 0)
 478     return result;
 479
 480   /* predict and decode motion vector (2) */
 481   pmv[1] = &motion[0];
 482   pmv[2] = &motion[(x / 8) + 1];
 483
 484   result = svq1_decode_motion_vector (bitbuf, &motion[(x / 8) + 2], pmv);
 485
 486   if (result != 0)
 487     return result;
 488
 489   /* predict and decode motion vector (3) */
 490   pmv[2] = &motion[(x / 8) + 2];
 491   pmv[3] = &motion[(x / 8) + 3];
 492
 493   result = svq1_decode_motion_vector (bitbuf, pmv[3], pmv);
 494
 495   if (result != 0)
 496     return result;
 497
 498   /* form predictions */
 499   for (i=0; i < 4; i++) {
 500     int mvx= pmv[i]->x + (i&1)*16;
 501     int mvy= pmv[i]->y + (i>>1)*16;
 502
 503     ///XXX /FIXME cliping or padding?
 504     if(y + (mvy >> 1)<0)
 505        mvy= 0;
 506     if(x + (mvx >> 1)<0)
 507        mvx= 0;
 508
 509 #if 0
 510   int w= (s->width+15)&~15;
 511   int h= (s->height+15)&~15;
 512   if(x + (mvx >> 1)<0 || y + (mvy >> 1)<0 || x + (mvx >> 1) + 8 > w || y + (mvy >> 1) + 8> h)
 513       av_log(s->avctx, AV_LOG_INFO, "%d %d %d %d\n", x, y, x + (mvx >> 1), y + (mvy >> 1));
 514 #endif
 515     src = &previous[(x + (mvx >> 1)) + (y + (mvy >> 1))*pitch];
 516     dst = current;
 517
 518     s->dsp.put_pixels_tab[1][((mvy & 1) << 1) | (mvx & 1)](dst,src,pitch,8);
 519
 520     /* select next block */
 521     if (i & 1) {
 522       current  += 8*(pitch - 1);
 523     } else {
 524       current  += 8;
 525     }
 526   }
 527
 528   return 0;
 529 }
 530
 531 static int svq1_decode_delta_block (MpegEncContext *s, GetBitContext *bitbuf,
 532                         uint8_t *current, uint8_t *previous, int pitch,
 533                         svq1_pmv_t *motion, int x, int y) {
 534   uint32_t block_type;
 535   int      result = 0;
 536
 537   /* get block type */
 538   block_type = get_vlc2(bitbuf, svq1_block_type.table, 2, 2);
 539
 540   /* reset motion vectors */
 541   if (block_type == SVQ1_BLOCK_SKIP || block_type == SVQ1_BLOCK_INTRA) {
 542     motion[0].x           =
 543     motion[0].y           =
 544     motion[(x / 8) + 2].x =
 545     motion[(x / 8) + 2].y =
 546     motion[(x / 8) + 3].x =
 547     motion[(x / 8) + 3].y = 0;
 548   }
 549
 550   switch (block_type) {
 551   case SVQ1_BLOCK_SKIP:
 552     svq1_skip_block (current, previous, pitch, x, y);
 553     break;
 554
 555   case SVQ1_BLOCK_INTER:
 556     result = svq1_motion_inter_block (s, bitbuf, current, previous, pitch, motion, x, y);
 557
 558     if (result != 0)
 559     {
 560 #ifdef DEBUG_SVQ1
 561     av_log(s->avctx, AV_LOG_INFO, "Error in svq1_motion_inter_block %i\n",result);
 562 #endif
 563       break;
 564     }
 565     result = svq1_decode_block_non_intra (bitbuf, current, pitch);
 566     break;
 567
 568   case SVQ1_BLOCK_INTER_4V:
 569     result = svq1_motion_inter_4v_block (s, bitbuf, current, previous, pitch, motion, x, y);
 570
 571     if (result != 0)
 572     {
 573 #ifdef DEBUG_SVQ1
 574     av_log(s->avctx, AV_LOG_INFO, "Error in svq1_motion_inter_4v_block %i\n",result);
 575 #endif
 576       break;
 577     }
 578     result = svq1_decode_block_non_intra (bitbuf, current, pitch);
 579     break;
 580
 581   case SVQ1_BLOCK_INTRA:
 582     result = svq1_decode_block_intra (bitbuf, current, pitch);
 583     break;
 584   }
 585
 586   return result;
 587 }
 588
 589 /* standard video sizes */
 590 static struct { int width; int height; } svq1_frame_size_table[8] = {
 591   { 160, 120 }, { 128,  96 }, { 176, 144 }, { 352, 288 },
 592   { 704, 576 }, { 240, 180 }, { 320, 240 }, {  -1,  -1 }
 593 };
 594
 595 static uint16_t svq1_packet_checksum (uint8_t *data, int length, int value) {
 596   int i;
 597
 598   for (i=0; i < length; i++) {
 599     value = checksum_table[data[i] ^ (value >> 8)] ^ ((value & 0xFF) << 8);
 600   }
 601
 602   return value;
 603 }
 604
 605 static uint16_t svq1_component_checksum (uint16_t *pixels, int pitch,
 606                                          int width, int height, int value) {
 607   int x, y;
 608
 609   for (y=0; y < height; y++) {
 610     for (x=0; x < width; x++) {
 611       value = checksum_table[pixels[x] ^ (value >> 8)] ^ ((value & 0xFF) << 8);
 612     }
 613
 614     pixels += pitch;
 615   }
 616
 617   return value;
 618 }
 619
 620 static void svq1_parse_string (GetBitContext *bitbuf, uint8_t *out) {
 621   uint8_t seed;
 622   int     i;
 623
 624   out[0] = get_bits (bitbuf, 8);
 625
 626   seed = string_table[out[0]];
 627
 628   for (i=1; i <= out[0]; i++) {
 629     out[i] = get_bits (bitbuf, 8) ^ seed;
 630     seed   = string_table[out[i] ^ seed];
 631   }
 632 }
 633
 634 static int svq1_decode_frame_header (GetBitContext *bitbuf,MpegEncContext *s) {
 635   int frame_size_code;
 636   int temporal_reference;
 637
 638   temporal_reference = get_bits (bitbuf, 8);
 639
 640   /* frame type */
 641   s->pict_type= get_bits (bitbuf, 2)+1;
 642   if(s->pict_type==4)
 643       return -1;
 644
 645   if (s->pict_type == I_TYPE) {
 646
 647     /* unknown fields */
 648     if (s->f_code == 0x50 || s->f_code == 0x60) {
 649       int csum = get_bits (bitbuf, 16);
 650
 651       csum = svq1_packet_checksum ((uint8_t *)bitbuf->buffer, bitbuf->size_in_bits>>3, csum);
 652
 653 //      av_log(s->avctx, AV_LOG_INFO, "%s checksum (%02x) for packet data\n",
 654 //              (csum == 0) ? "correct" : "incorrect", csum);
 655     }
 656
 657     if ((s->f_code ^ 0x10) >= 0x50) {
 658       char msg[256];
 659
 660       svq1_parse_string (bitbuf, (char *) msg);
 661
 662       av_log(s->avctx, AV_LOG_INFO, "embedded message: \"%s\"\n", (char *) msg);
 663     }
 664
 665     skip_bits (bitbuf, 2);
 666     skip_bits (bitbuf, 2);
 667     skip_bits1 (bitbuf);
 668
 669     /* load frame size */
 670     frame_size_code = get_bits (bitbuf, 3);
 671
 672     if (frame_size_code == 7) {
 673       /* load width, height (12 bits each) */
 674       s->width = get_bits (bitbuf, 12);
 675       s->height = get_bits (bitbuf, 12);
 676
 677       if (!s->width || !s->height)
 678         return -1;
 679     } else {
 680       /* get width, height from table */
 681       s->width = svq1_frame_size_table[frame_size_code].width;
 682       s->height = svq1_frame_size_table[frame_size_code].height;
 683     }
 684   }
 685
 686   /* unknown fields */
 687   if (get_bits (bitbuf, 1) == 1) {
 688     skip_bits1 (bitbuf);       /* use packet checksum if (1) */
 689     skip_bits1 (bitbuf);       /* component checksums after image data if (1) */
 690
 691     if (get_bits (bitbuf, 2) != 0)
 692       return -1;
 693   }
 694
 695   if (get_bits (bitbuf, 1) == 1) {
 696     skip_bits1 (bitbuf);
 697     skip_bits (bitbuf, 4);
 698     skip_bits1 (bitbuf);
 699     skip_bits (bitbuf, 2);
 700
 701     while (get_bits (bitbuf, 1) == 1) {
 702       skip_bits (bitbuf, 8);
 703     }
 704   }
 705
 706   return 0;
 707 }
 708
 709 static int svq1_decode_frame(AVCodecContext *avctx,
 710                              void *data, int *data_size,
 711                              uint8_t *buf, int buf_size)
 712 {
 713   MpegEncContext *s=avctx->priv_data;
 714   uint8_t      *current, *previous;
 715   int           result, i, x, y, width, height;
 716   AVFrame *pict = data;
 717
 718   /* initialize bit buffer */
 719   init_get_bits(&s->gb,buf,buf_size*8);
 720
 721   /* decode frame header */
 722   s->f_code = get_bits (&s->gb, 22);
 723
 724   if ((s->f_code & ~0x70) || !(s->f_code & 0x60))
 725     return -1;
 726
 727   /* swap some header bytes (why?) */
 728   if (s->f_code != 0x20) {
 729     uint32_t *src = (uint32_t *) (buf + 4);
 730
 731     for (i=0; i < 4; i++) {
 732       src[i] = ((src[i] << 16) | (src[i] >> 16)) ^ src[7 - i];
 733     }
 734   }
 735
 736   result = svq1_decode_frame_header (&s->gb, s);
 737
 738   if (result != 0)
 739   {
 740 #ifdef DEBUG_SVQ1
 741     av_log(s->avctx, AV_LOG_INFO, "Error in svq1_decode_frame_header %i\n",result);
 742 #endif
 743     return result;
 744   }
 745
 746   //FIXME this avoids some confusion for "B frames" without 2 references
 747   //this should be removed after libavcodec can handle more flexible picture types & ordering
 748   if(s->pict_type==B_TYPE && s->last_picture_ptr==NULL) return buf_size;
 749
 750   if(avctx->hurry_up && s->pict_type==B_TYPE) return buf_size;
 751
 752   if(MPV_frame_start(s, avctx) < 0)
 753       return -1;
 754
 755   /* decode y, u and v components */
 756   for (i=0; i < 3; i++) {
 757     int linesize;
 758     if (i == 0) {
 759       width  = (s->width+15)&~15;
 760       height = (s->height+15)&~15;
 761       linesize= s->linesize;
 762     } else {
 763       if(s->flags&CODEC_FLAG_GRAY) break;
 764       width  = (s->width/4+15)&~15;
 765       height = (s->height/4+15)&~15;
 766       linesize= s->uvlinesize;
 767     }
 768
 769     current  = s->current_picture.data[i];
 770
 771     if(s->pict_type==B_TYPE){
 772         previous = s->next_picture.data[i];
 773     }else{
 774         previous = s->last_picture.data[i];
 775     }
 776
 777     if (s->pict_type == I_TYPE) {
 778       /* keyframe */
 779       for (y=0; y < height; y+=16) {
 780         for (x=0; x < width; x+=16) {
 781           result = svq1_decode_block_intra (&s->gb, &current[x], linesize);
 782           if (result != 0)
 783           {
 784 //#ifdef DEBUG_SVQ1
 785             av_log(s->avctx, AV_LOG_INFO, "Error in svq1_decode_block %i (keyframe)\n",result);
 786 //#endif
 787             return result;
 788           }
 789         }
 790         current += 16*linesize;
 791       }
 792     } else {
 793       svq1_pmv_t pmv[width/8+3];
 794       /* delta frame */
 795       memset (pmv, 0, ((width / 8) + 3) * sizeof(svq1_pmv_t));
 796
 797       for (y=0; y < height; y+=16) {
 798         for (x=0; x < width; x+=16) {
 799           result = svq1_decode_delta_block (s, &s->gb, &current[x], previous,
 800                                             linesize, pmv, x, y);
 801           if (result != 0)
 802           {
 803 #ifdef DEBUG_SVQ1
 804     av_log(s->avctx, AV_LOG_INFO, "Error in svq1_decode_delta_block %i\n",result);
 805 #endif
 806             return result;
 807           }
 808         }
 809
 810         pmv[0].x =
 811         pmv[0].y = 0;
 812
 813         current += 16*linesize;
 814       }
 815     }
 816   }
 817
 818   *pict = *(AVFrame*)&s->current_picture;
 819
 820
 821   MPV_frame_end(s);
 822
 823   *data_size=sizeof(AVFrame);
 824   return buf_size;
 825 }
 826
 827 static int svq1_decode_init(AVCodecContext *avctx)
 828 {
 829     MpegEncContext *s = avctx->priv_data;
 830     int i;
 831
 832     MPV_decode_defaults(s);
 833
 834     s->avctx = avctx;
 835     s->width = (avctx->width+3)&~3;
 836     s->height = (avctx->height+3)&~3;
 837     s->codec_id= avctx->codec->id;
 838     avctx->pix_fmt = PIX_FMT_YUV410P;
 839     avctx->has_b_frames= 1; // not true, but DP frames and these behave like unidirectional b frames
 840     s->flags= avctx->flags;
 841     if (MPV_common_init(s) < 0) return -1;
 842
 843     init_vlc(&svq1_block_type, 2, 4,
 844         &svq1_block_type_vlc[0][1], 2, 1,
 845         &svq1_block_type_vlc[0][0], 2, 1);
 846
 847     init_vlc(&svq1_motion_component, 7, 33,
 848         &mvtab[0][1], 2, 1,
 849         &mvtab[0][0], 2, 1);
 850
 851     for (i = 0; i < 6; i++) {
 852         init_vlc(&svq1_intra_multistage[i], 3, 8,
 853             &svq1_intra_multistage_vlc[i][0][1], 2, 1,
 854             &svq1_intra_multistage_vlc[i][0][0], 2, 1);
 855         init_vlc(&svq1_inter_multistage[i], 3, 8,
 856             &svq1_inter_multistage_vlc[i][0][1], 2, 1,
 857             &svq1_inter_multistage_vlc[i][0][0], 2, 1);
 858     }
 859
 860     init_vlc(&svq1_intra_mean, 8, 256,
 861         &svq1_intra_mean_vlc[0][1], 4, 2,
 862         &svq1_intra_mean_vlc[0][0], 4, 2);
 863
 864     init_vlc(&svq1_inter_mean, 9, 512,
 865         &svq1_inter_mean_vlc[0][1], 4, 2,
 866         &svq1_inter_mean_vlc[0][0], 4, 2);
 867
 868     return 0;
 869 }
 870
 871 static int svq1_decode_end(AVCodecContext *avctx)
 872 {
 873     MpegEncContext *s = avctx->priv_data;
 874
 875     MPV_common_end(s);
 876     return 0;
 877 }
 878
 879 static void svq1_write_header(SVQ1Context *s, int frame_type)
 880 {
 881     /* frame code */
 882     put_bits(&s->pb, 22, 0x20);
 883
 884     /* temporal reference (sure hope this is a "don't care") */
 885     put_bits(&s->pb, 8, 0x00);
 886
 887     /* frame type */
 888     put_bits(&s->pb, 2, frame_type - 1);
 889
 890     if (frame_type == I_TYPE) {
 891
 892         /* no checksum since frame code is 0x20 */
 893
 894         /* no embedded string either */
 895
 896         /* output 5 unknown bits (2 + 2 + 1) */
 897         put_bits(&s->pb, 5, 0);
 898
 899         /* forget about matching up resolutions, just use the free-form
 900          * resolution code (7) for now */
 901         put_bits(&s->pb, 3, 7);
 902         put_bits(&s->pb, 12, s->frame_width);
 903         put_bits(&s->pb, 12, s->frame_height);
 904
 905     }
 906
 907     /* no checksum or extra data (next 2 bits get 0) */
 908     put_bits(&s->pb, 2, 0);
 909 }
 910
 911 int level_sizes[6] =      { 8, 16, 32, 64, 128, 256 };
 912 int level_log2_sizes[6] = { 3,  4,  5,  6,   7,   8 };
 913
 914 #define IABS(x) ((x < 0) ? (-(x)) : x)
 915
 916
 917
 918 //#define USE_MAD_ALGORITHM
 919
 920 #ifdef USE_MAD_ALGORITHM
 921
 922 #define QUALITY_THRESHOLD 100
 923 #define THRESHOLD_MULTIPLIER 0.6
 924
 925 /* This function calculates vector differences using mean absolute
 926  * difference (MAD). */
 927
 928 static int encode_vector(SVQ1Context *s, unsigned char *vector,
 929     unsigned int level, int threshold)
 930 {
 931     int i, j, k;
 932     int mean;
 933     signed short work_vector[256];
 934     int best_codebook;
 935     int best_score;
 936     int multistage_codebooks[6];
 937     int number_of_stages = 0;
 938     int8_t *current_codebook;
 939     int total_deviation;
 940     int ret;
 941
 942 #ifdef DEBUG_SVQ1
 943 av_log(s->avctx, AV_LOG_INFO, "  ** recursive entry point: encoding level %d vector at threshold %d\n",
 944   level, threshold);
 945 #endif
 946     if (level > 5) {
 947         av_log(s->avctx, AV_LOG_INFO, " help! level %d > 5\n", level);
 948         return 0;
 949     }
 950
 951 #ifdef DEBUG_SVQ1
 952 for (i = 0; i < level_sizes[level]; i++)
 953   av_log(s->avctx, AV_LOG_INFO, " %02X", vector[i]);
 954 av_log(s->avctx, AV_LOG_INFO, "\n");
 955 #endif
 956
 957     /* calculate the mean */
 958     mean = 0;
 959     for (i = 0; i < level_sizes[level]; i++)
 960         mean += vector[i];
 961     mean >>= level_log2_sizes[level];
 962
 963 #ifdef DEBUG_SVQ1
 964 av_log(s->avctx, AV_LOG_INFO, " vector mean = 0x%02X\n", mean);
 965 #endif
 966
 967     /* remove the mean from the vector */
 968     total_deviation = 0;
 969     for (i = 0; i < level_sizes[level]; i++) {
 970         work_vector[i] = (signed short)vector[i] - mean;
 971         total_deviation += IABS(work_vector[i]);
 972 #ifdef DEBUG_SVQ1
 973 av_log(s->avctx, AV_LOG_INFO, " %d", work_vector[i]);
 974 #endif
 975     }
 976
 977 #ifdef DEBUG_SVQ1
 978 av_log(s->avctx, AV_LOG_INFO, "\n  total deviation = %d\n", total_deviation);
 979 #endif
 980
 981     if (total_deviation < threshold) {
 982
 983 #ifdef DEBUG_SVQ1
 984     av_log(s->avctx, AV_LOG_INFO, " mean-only encoding found for level %d vector, mean = %d\n",
 985       level, mean);
 986 #endif
 987
 988         /* indicate that this is the end of the subdivisions */
 989         if (level > 0)
 990             put_bits(&s->pb, 1, 0);
 991
 992         /* index 1 in the table indicates mean-only encoding */
 993         put_bits(&s->pb, svq1_intra_multistage_vlc[level][1][1],
 994             svq1_intra_multistage_vlc[level][1][0]);
 995         put_bits(&s->pb, svq1_intra_mean_vlc[mean][1],
 996             svq1_intra_mean_vlc[mean][0]);
 997
 998 #ifdef DEBUG_SVQ1
 999 av_log(s->avctx, AV_LOG_INFO, "  mean-only L%d, VLC = (0x%X, %d), mean = %d (0x%X, %d)\n",
1000   level,
1001   svq1_intra_multistage_vlc[level][1 + number_of_stages][0],
1002   svq1_intra_multistage_vlc[level][1 + number_of_stages][1],
1003   mean,
1004   svq1_intra_mean_vlc[mean][0],
1005   svq1_intra_mean_vlc[mean][1]);
1006 #endif
1007
1008         ret = 0;
1009
1010     } else {
1011
1012         if (level <= 3) {
1013
1014 #ifdef DEBUG_SVQ1
1015 av_log(s->avctx, AV_LOG_INFO, " multistage VQ search...\n");
1016 #endif
1017             /* conduct multistage VQ search, for each stage... */
1018             for (i = 0; i < 6; i++) {
1019
1020                 best_codebook = 0;
1021                 best_score = 0x7FFFFFFF;
1022                 /* for each codebook in stage */
1023                 for (j = 0; j < 16; j++) {
1024
1025                     total_deviation = 0;
1026                     current_codebook =
1027                         &svq1_intra_codebooks[level]
1028                         [i * level_sizes[level] * 16 + j * level_sizes[level]];
1029                     /* calculate the total deviation for the vector */
1030                     for (k = 0; k < level_sizes[level]; k++) {
1031                         total_deviation +=
1032                             IABS(work_vector[k] - current_codebook[k]);
1033                     }
1034
1035                     /* lowest score so far? */
1036                     if (total_deviation < best_score) {
1037                         best_score = total_deviation;
1038                         best_codebook = j;
1039                     }
1040 #ifdef DEBUG_SVQ1
1041 av_log(s->avctx, AV_LOG_INFO, "  after %d, %d, best codebook is %d with a score of %d (score was %d)\n",
1042   i, j, best_codebook, best_score, total_deviation);
1043 #endif
1044                 }
1045
1046                 /* apply the winning codebook to the work vector and check if
1047                  * the vector meets the quality threshold */
1048                 total_deviation = 0;
1049                 current_codebook =
1050                     &svq1_intra_codebooks[level]
1051                     [i * level_sizes[level] * 16 + j * level_sizes[level]];
1052                 multistage_codebooks[number_of_stages++] = best_codebook;
1053                 for (j = 0; j < level_sizes[level]; j++) {
1054                     work_vector[j] = work_vector[j] - current_codebook[j];
1055                     total_deviation += IABS(work_vector[j]);
1056                 }
1057
1058                 /* do not go forward with the rest of the search if an acceptable
1059                  * codebook combination has been found */
1060                 if (total_deviation < threshold)
1061                     break;
1062             }
1063         }
1064
1065         if ((total_deviation < threshold) || (level == 0)) {
1066 #ifdef DEBUG_SVQ1
1067       av_log(s->avctx, AV_LOG_INFO, " level %d VQ encoding found using mean %d and codebooks", level, mean);
1068       for (i = 0; i < number_of_stages; i++)
1069         av_log(s->avctx, AV_LOG_INFO, " %d", multistage_codebooks[i]);
1070       av_log(s->avctx, AV_LOG_INFO, "\n");
1071 #endif
1072
1073             /* indicate that this is the end of the subdivisions */
1074             if (level > 0)
1075                 put_bits(&s->pb, 1, 0);
1076
1077             /* output the encoding */
1078             put_bits(&s->pb,
1079                 svq1_intra_multistage_vlc[level][1 + number_of_stages][1],
1080                 svq1_intra_multistage_vlc[level][1 + number_of_stages][0]);
1081             put_bits(&s->pb, svq1_intra_mean_vlc[mean][1],
1082                 svq1_intra_mean_vlc[mean][0]);
1083 #ifdef DEBUG_SVQ1
1084 av_log(s->avctx, AV_LOG_INFO, "  L%d: multistage = %d (0x%X, %d), mean = %d (0x%X, %d), codebooks = ",
1085   level,
1086   number_of_stages,
1087   svq1_intra_multistage_vlc[level][1 + number_of_stages][0],
1088   svq1_intra_multistage_vlc[level][1 + number_of_stages][1],
1089   mean,
1090   svq1_intra_mean_vlc[mean][0],
1091   svq1_intra_mean_vlc[mean][1]);
1092 #endif
1093
1094             for (i = 0; i < number_of_stages; i++)
1095 {
1096 #ifdef DEBUG_SVQ1
1097 av_log(s->avctx, AV_LOG_INFO, "%d ", multistage_codebooks[i]);
1098 #endif
1099                 put_bits(&s->pb, 4, multistage_codebooks[i]);
1100 }
1101 #ifdef DEBUG_SVQ1
1102 av_log(s->avctx, AV_LOG_INFO, "\n");
1103 #endif
1104
1105             ret = 0;
1106
1107         } else {
1108
1109             /* output a subdivision bit to the encoded stream and signal to
1110              * the calling function that this vector could not be
1111              * coded at the requested threshold and needs to be subdivided */
1112             put_bits(&s->pb, 1, 1);
1113             ret = 1;
1114         }
1115     }
1116
1117     return ret;
1118 }
1119
1120 #else
1121
1122 #define QUALITY_THRESHOLD 100
1123 #define THRESHOLD_MULTIPLIER 0.6
1124
1125 /* This function calculates vector differences using mean square
1126  * error (MSE). */
1127
1128 static int encode_vector(SVQ1Context *s, unsigned char *vector,
1129     unsigned int level, int threshold)
1130 {
1131     int i, j, k;
1132     int mean;
1133     signed short work_vector[256];
1134     int best_codebook;
1135     int best_score;
1136     int multistage_codebooks[6];
1137     int number_of_stages = 0;
1138     int8_t *current_codebook;
1139     int mse;
1140     int diff;
1141     int ret;
1142
1143 #ifdef DEBUG_SVQ1
1144 av_log(s->avctx, AV_LOG_INFO, "  ** recursive entry point: encoding level %d vector at threshold %d\n",
1145   level, threshold);
1146 #endif
1147     if (level > 5) {
1148         av_log(s->avctx, AV_LOG_INFO, " help! level %d > 5\n", level);
1149         return 0;
1150     }
1151
1152 #ifdef DEBUG_SVQ1
1153 for (i = 0; i < level_sizes[level]; i++)
1154   av_log(s->avctx, AV_LOG_INFO, " %02X", vector[i]);
1155 av_log(s->avctx, AV_LOG_INFO, "\n");
1156 #endif
1157
1158     /* calculate the mean */
1159     mean = 0;
1160     for (i = 0; i < level_sizes[level]; i++)
1161         mean += vector[i];
1162     mean >>= level_log2_sizes[level];
1163
1164 #ifdef DEBUG_SVQ1
1165 av_log(s->avctx, AV_LOG_INFO, " vector mean = 0x%02X\n", mean);
1166 #endif
1167
1168     /* remove the mean from the vector and compute the resulting MSE */
1169     mse = 0;
1170     for (i = 0; i < level_sizes[level]; i++) {
1171         work_vector[i] = (signed short)vector[i] - mean;
1172         mse += (work_vector[i] * work_vector[i]);
1173 #ifdef DEBUG_SVQ1
1174 av_log(s->avctx, AV_LOG_INFO, " %d", work_vector[i]);
1175 #endif
1176     }
1177     mse >>= level_log2_sizes[level];
1178
1179 #ifdef DEBUG_SVQ1
1180 av_log(s->avctx, AV_LOG_INFO, "\n  MSE = %d\n", mse);
1181 #endif
1182
1183     if (mse < threshold) {
1184
1185 #ifdef DEBUG_SVQ1
1186     av_log(s->avctx, AV_LOG_INFO, " mean-only encoding found for level %d vector, mean = %d\n",
1187       level, mean);
1188 #endif
1189
1190         /* indicate that this is the end of the subdivisions */
1191         if (level > 0)
1192             put_bits(&s->pb, 1, 0);
1193
1194         /* index 1 in the table indicates mean-only encoding */
1195         put_bits(&s->pb, svq1_intra_multistage_vlc[level][1][1],
1196             svq1_intra_multistage_vlc[level][1][0]);
1197         put_bits(&s->pb, svq1_intra_mean_vlc[mean][1],
1198             svq1_intra_mean_vlc[mean][0]);
1199
1200 #ifdef DEBUG_SVQ1
1201 av_log(s->avctx, AV_LOG_INFO, "  mean-only L%d, VLC = (0x%X, %d), mean = %d (0x%X, %d)\n",
1202   level,
1203   svq1_intra_multistage_vlc[level][1 + number_of_stages][0],
1204   svq1_intra_multistage_vlc[level][1 + number_of_stages][1],
1205   mean,
1206   svq1_intra_mean_vlc[mean][0],
1207   svq1_intra_mean_vlc[mean][1]);
1208 #endif
1209
1210         ret = 0;
1211
1212     } else {
1213
1214         if (level <= 3) {
1215
1216 #ifdef DEBUG_SVQ1
1217 av_log(s->avctx, AV_LOG_INFO, " multistage VQ search...\n");
1218 #endif
1219             /* conduct multistage VQ search, for each stage... */
1220             for (i = 0; i < 6; i++) {
1221
1222                 best_codebook = 0;
1223                 best_score = 0x7FFFFFFF;
1224                 /* for each codebook in stage */
1225                 for (j = 0; j < 16; j++) {
1226
1227                     mse = 0;
1228                     current_codebook =
1229                         &svq1_intra_codebooks[level]
1230                         [i * level_sizes[level] * 16 + j * level_sizes[level]];
1231                     /* calculate the MSE for this vector */
1232                     for (k = 0; k < level_sizes[level]; k++) {
1233                         diff = work_vector[k] - current_codebook[k];
1234                         mse += (diff * diff);
1235                     }
1236                     mse >>= level_log2_sizes[level];
1237
1238                     /* lowest score so far? */
1239                     if (mse < best_score) {
1240                         best_score = mse;
1241                         best_codebook = j;
1242                     }
1243 #ifdef DEBUG_SVQ1
1244 av_log(s->avctx, AV_LOG_INFO, "  after %d, %d, best codebook is %d with a score of %d (score was %d)\n",
1245   i, j, best_codebook, best_score, mse);
1246 #endif
1247                 }
1248
1249                 /* apply the winning codebook to the work vector and check if
1250                  * the vector meets the quality threshold */
1251                 mse = 0;
1252                 current_codebook =
1253                     &svq1_intra_codebooks[level]
1254                     [i * level_sizes[level] * 16 + j * level_sizes[level]];
1255                 multistage_codebooks[number_of_stages++] = best_codebook;
1256                 for (j = 0; j < level_sizes[level]; j++) {
1257                     work_vector[j] = work_vector[j] - current_codebook[j];
1258                     mse += (work_vector[j] * work_vector[j]);
1259                 }
1260                 mse >>= level_log2_sizes[level];
1261
1262                 /* do not go forward with the rest of the search if an acceptable
1263                  * codebook combination has been found */
1264                 if (mse < threshold)
1265                     break;
1266             }
1267         }
1268
1269         if ((mse < threshold) || (level == 0)) {
1270 #ifdef DEBUG_SVQ1
1271       av_log(s->avctx, AV_LOG_INFO, " level %d VQ encoding found using mean %d and codebooks", level, mean);
1272       for (i = 0; i < number_of_stages; i++)
1273         av_log(s->avctx, AV_LOG_INFO, " %d", multistage_codebooks[i]);
1274       av_log(s->avctx, AV_LOG_INFO, "\n");
1275 #endif
1276
1277             /* indicate that this is the end of the subdivisions */
1278             if (level > 0)
1279                 put_bits(&s->pb, 1, 0);
1280
1281             /* output the encoding */
1282             put_bits(&s->pb,
1283                 svq1_intra_multistage_vlc[level][1 + number_of_stages][1],
1284                 svq1_intra_multistage_vlc[level][1 + number_of_stages][0]);
1285             put_bits(&s->pb, svq1_intra_mean_vlc[mean][1],
1286                 svq1_intra_mean_vlc[mean][0]);
1287 #ifdef DEBUG_SVQ1
1288 av_log(s->avctx, AV_LOG_INFO, "  L%d: multistage = %d (0x%X, %d), mean = %d (0x%X, %d), codebooks = ",
1289   level,
1290   number_of_stages,
1291   svq1_intra_multistage_vlc[level][1 + number_of_stages][0],
1292   svq1_intra_multistage_vlc[level][1 + number_of_stages][1],
1293   mean,
1294   svq1_intra_mean_vlc[mean][0],
1295   svq1_intra_mean_vlc[mean][1]);
1296 #endif
1297
1298             for (i = 0; i < number_of_stages; i++)
1299 {
1300 #ifdef DEBUG_SVQ1
1301 av_log(s->avctx, AV_LOG_INFO, "%d ", multistage_codebooks[i]);
1302 #endif
1303                 put_bits(&s->pb, 4, multistage_codebooks[i]);
1304 }
1305 #ifdef DEBUG_SVQ1
1306 av_log(s->avctx, AV_LOG_INFO, "\n");
1307 #endif
1308
1309             ret = 0;
1310
1311         } else {
1312
1313             /* output a subdivision bit to the encoded stream and signal to
1314              * the calling function that this vector could not be
1315              * coded at the requested threshold and needs to be subdivided */
1316             put_bits(&s->pb, 1, 1);
1317             ret = 1;
1318         }
1319     }
1320
1321     return ret;
1322 }
1323 #endif
1324
1325 static int encode_block(SVQ1Context *s, uint8_t *src, uint8_t *ref, uint8_t *decoded, int stride, int level, int threshold, int lambda, int intra){
1326     int count, y, x, i, j, split, best_mean, best_score, best_count;
1327     int best_vector[6];
1328     int block_sum[7]= {0, 0, 0, 0, 0, 0};
1329     int w= 2<<((level+2)>>1);
1330     int h= 2<<((level+1)>>1);
1331     int size=w*h;
1332     int16_t block[7][256];
1333     const int8_t *codebook_sum, *codebook;
1334     const uint16_t (*mean_vlc)[2];
1335     const uint8_t (*multistage_vlc)[2];
1336
1337     best_score=0;
1338     //FIXME optimize, this doenst need to be done multiple times
1339     if(intra){
1340         codebook_sum= svq1_intra_codebook_sum[level];
1341         codebook= svq1_intra_codebooks[level];
1342         mean_vlc= svq1_intra_mean_vlc;
1343         multistage_vlc= svq1_intra_multistage_vlc[level];
1344         for(y=0; y<h; y++){
1345             for(x=0; x<w; x++){
1346                 int v= src[x + y*stride];
1347                 block[0][x + w*y]= v;
1348                 best_score += v*v;
1349                 block_sum[0] += v;
1350             }
1351         }
1352     }else{
1353         codebook_sum= svq1_inter_codebook_sum[level];
1354         codebook= svq1_inter_codebooks[level];
1355         mean_vlc= svq1_inter_mean_vlc + 256;
1356         multistage_vlc= svq1_inter_multistage_vlc[level];
1357         for(y=0; y<h; y++){
1358             for(x=0; x<w; x++){
1359                 int v= src[x + y*stride] - ref[x + y*stride];
1360                 block[0][x + w*y]= v;
1361                 best_score += v*v;
1362                 block_sum[0] += v;
1363             }
1364         }
1365     }
1366
1367     best_count=0;
1368     best_score -= ((block_sum[0]*block_sum[0])>>(level+3));
1369     best_mean= (block_sum[0] + (size>>1)) >> (level+3);
1370
1371     if(level<4){
1372         for(count=1; count<7; count++){
1373             int best_vector_score= INT_MAX;
1374             int best_vector_sum=-999, best_vector_mean=-999;
1375             const int stage= count-1;
1376             const int8_t *vector;
1377
1378             for(i=0; i<16; i++){
1379                 int sum= codebook_sum[stage*16 + i];
1380                 int sqr=0;
1381                 int diff, mean, score;
1382
1383                 vector = codebook + stage*size*16 + i*size;
1384
1385                 for(j=0; j<size; j++){
1386                     int v= vector[j];
1387                     sqr += (v - block[stage][j])*(v - block[stage][j]);
1388                 }
1389                 diff= block_sum[stage] - sum;
1390                 mean= (diff + (size>>1)) >> (level+3);
1391                 assert(mean >-300 && mean<300);
1392                 if(intra) mean= clip(mean, 0, 255);
1393                 else      mean= clip(mean, -256, 255);
1394                 score= sqr - ((diff*(int64_t)diff)>>(level+3)); //FIXME 64bit slooow
1395                 if(score < best_vector_score){
1396                     best_vector_score= score;
1397                     best_vector[stage]= i;
1398                     best_vector_sum= sum;
1399                     best_vector_mean= mean;
1400                 }
1401             }
1402             assert(best_vector_mean != -999);
1403             vector= codebook + stage*size*16 + best_vector[stage]*size;
1404             for(j=0; j<size; j++){
1405                 block[stage+1][j] = block[stage][j] - vector[j];
1406             }
1407             block_sum[stage+1]= block_sum[stage] - best_vector_sum;
1408             best_vector_score +=
1409                 lambda*(+ 1 + 4*count
1410                         + multistage_vlc[1+count][1]
1411                         + mean_vlc[best_vector_mean][1]);
1412
1413             if(best_vector_score < best_score){
1414                 best_score= best_vector_score;
1415                 best_count= count;
1416                 best_mean= best_vector_mean;
1417             }
1418         }
1419     }
1420
1421     split=0;
1422     if(best_score > threshold && level){
1423         int score=0;
1424         int offset= (level&1) ? stride*h/2 : w/2;
1425         PutBitContext backup[6];
1426
1427         for(i=level-1; i>=0; i--){
1428             backup[i]= s->reorder_pb[i];
1429         }
1430         score += encode_block(s, src         , ref         , decoded         , stride, level-1, threshold>>1, lambda, intra);
1431         score += encode_block(s, src + offset, ref + offset, decoded + offset, stride, level-1, threshold>>1, lambda, intra);
1432         score += lambda;
1433
1434         if(score < best_score){
1435             best_score= score;
1436             split=1;
1437         }else{
1438             for(i=level-1; i>=0; i--){
1439                 s->reorder_pb[i]= backup[i];
1440             }
1441         }
1442     }
1443     if (level > 0)
1444         put_bits(&s->reorder_pb[level], 1, split);
1445
1446     if(!split){
1447         assert((best_mean >= 0 && best_mean<256) || !intra);
1448         assert(best_mean >= -256 && best_mean<256);
1449         assert(best_count >=0 && best_count<7);
1450         assert(level<4 || best_count==0);
1451
1452         /* output the encoding */
1453         put_bits(&s->reorder_pb[level],
1454             multistage_vlc[1 + best_count][1],
1455             multistage_vlc[1 + best_count][0]);
1456         put_bits(&s->reorder_pb[level], mean_vlc[best_mean][1],
1457             mean_vlc[best_mean][0]);
1458
1459         for (i = 0; i < best_count; i++){
1460             assert(best_vector[i]>=0 && best_vector[i]<16);
1461             put_bits(&s->reorder_pb[level], 4, best_vector[i]);
1462         }
1463
1464         for(y=0; y<h; y++){
1465             for(x=0; x<w; x++){
1466                 decoded[x + y*stride]= src[x + y*stride] - block[best_count][x + w*y] + best_mean;
1467             }
1468         }
1469     }
1470
1471     return best_score;
1472 }
1473
1474 static void svq1_encode_plane(SVQ1Context *s, int plane, unsigned char *src_plane, unsigned char *ref_plane, unsigned char *decoded_plane,
1475     int width, int height, int src_stride, int stride)
1476 {
1477     unsigned char buffer0[256];
1478     unsigned char buffer1[256];
1479     int current_buffer;
1480     unsigned char *vector;
1481     unsigned char *subvectors;
1482     int vector_count;
1483     int subvector_count;
1484     int x, y;
1485     int i, j;
1486     int block_width, block_height;
1487     int left_edge;
1488     int level;
1489     int threshold[6];
1490     const int lambda= (s->picture.quality*s->picture.quality) >> (2*FF_LAMBDA_SHIFT);
1491
1492 static int frame = 0;
1493
1494 #ifdef DEBUG_SVQ1
1495 av_log(s->avctx, AV_LOG_INFO, "********* frame #%d\n", frame++);
1496 #endif
1497
1498     /* figure out the acceptable level thresholds in advance */
1499     threshold[5] = QUALITY_THRESHOLD;
1500     for (level = 4; level >= 0; level--)
1501         threshold[level] = threshold[level + 1] * THRESHOLD_MULTIPLIER;
1502
1503     block_width = (width + 15) / 16;
1504     block_height = (height + 15) / 16;
1505
1506     if(s->picture.pict_type == P_TYPE){
1507         s->m.avctx= s->avctx;
1508         s->m.current_picture_ptr= &s->m.current_picture;
1509         s->m.last_picture_ptr   = &s->m.last_picture;
1510         s->m.last_picture.data[0]= ref_plane;
1511         s->m.linesize=
1512         s->m.last_picture.linesize[0]=
1513         s->m.new_picture.linesize[0]=
1514         s->m.current_picture.linesize[0]= stride;
1515         s->m.width= width;
1516         s->m.height= height;
1517         s->m.mb_width= block_width;
1518         s->m.mb_height= block_height;
1519         s->m.mb_stride= s->m.mb_width+1;
1520         s->m.b8_stride= 2*s->m.mb_width+1;
1521         s->m.f_code=1;
1522         s->m.pict_type= s->picture.pict_type;
1523         s->m.qscale= s->picture.quality/FF_QP2LAMBDA;
1524         s->m.me_method= s->avctx->me_method;
1525
1526         if(!s->motion_val8[plane]){
1527             s->motion_val8 [plane]= av_mallocz(s->m.b8_stride*block_height*2*2*sizeof(int16_t));
1528             s->motion_val16[plane]= av_mallocz(s->m.mb_stride*block_height*2*sizeof(int16_t));
1529         }
1530
1531         s->m.mb_type= s->mb_type;
1532
1533         //dummies, to avoid segfaults
1534         s->m.current_picture.mb_mean= s->dummy;
1535         s->m.current_picture.mb_var= s->dummy;
1536         s->m.current_picture.mc_mb_var= s->dummy;
1537         s->m.current_picture.mb_type= s->dummy;
1538
1539         s->m.current_picture.motion_val[0]= s->motion_val8[plane];
1540         s->m.p_mv_table= s->motion_val16[plane];
1541         s->m.dsp= s->dsp; //move
1542         ff_init_me(&s->m);
1543
1544         s->m.me.dia_size= s->avctx->dia_size;
1545         s->m.first_slice_line=1;
1546         for (y = 0; y < block_height; y++) {
1547             uint8_t src[stride*16];
1548
1549             s->m.new_picture.data[0]= src - y*16*stride; //ugly
1550             s->m.mb_y= y;
1551
1552             for(i=0; i<16 && i + 16*y<height; i++){
1553                 memcpy(&src[i*stride], &src_plane[(i+16*y)*src_stride], width);
1554                 for(x=width; x<16*block_width; x++)
1555                     src[i*stride+x]= src[i*stride+x-1];
1556             }
1557             for(; i<16 && i + 16*y<16*block_height; i++)
1558                 memcpy(&src[i*stride], &src[(i-1)*stride], 16*block_width);
1559
1560             for (x = 0; x < block_width; x++) {
1561                 s->m.mb_x= x;
1562                 ff_init_block_index(&s->m);
1563                 ff_update_block_index(&s->m);
1564
1565                 ff_estimate_p_frame_motion(&s->m, x, y);
1566             }
1567             s->m.first_slice_line=0;
1568         }
1569
1570         ff_fix_long_p_mvs(&s->m);
1571         ff_fix_long_mvs(&s->m, NULL, 0, s->m.p_mv_table, s->m.f_code, CANDIDATE_MB_TYPE_INTER, 0);
1572     }
1573
1574     s->m.first_slice_line=1;
1575     for (y = 0; y < block_height; y++) {
1576         uint8_t src[stride*16];
1577
1578         for(i=0; i<16 && i + 16*y<height; i++){
1579             memcpy(&src[i*stride], &src_plane[(i+16*y)*src_stride], width);
1580             for(x=width; x<16*block_width; x++)
1581                 src[i*stride+x]= src[i*stride+x-1];
1582         }
1583         for(; i<16 && i + 16*y<16*block_height; i++)
1584             memcpy(&src[i*stride], &src[(i-1)*stride], 16*block_width);
1585
1586         s->m.mb_y= y;
1587         for (x = 0; x < block_width; x++) {
1588             uint8_t reorder_buffer[3][6][7*32];
1589             int count[3][6];
1590             int offset = y * 16 * stride + x * 16;
1591             uint8_t *decoded= decoded_plane + offset;
1592             uint8_t *ref= ref_plane + offset;
1593             int score[4]={0,0,0,0}, best;
1594             uint8_t temp[16*stride];
1595
1596             s->m.mb_x= x;
1597             ff_init_block_index(&s->m);
1598             ff_update_block_index(&s->m);
1599 #ifdef DEBUG_SVQ1
1600 av_log(s->avctx, AV_LOG_INFO, "* level 5 vector @ %d, %d:\n", x * 16, y * 16);
1601 #endif
1602
1603             if(s->picture.pict_type == I_TYPE || (s->m.mb_type[x + y*s->m.mb_stride]&CANDIDATE_MB_TYPE_INTRA)){
1604                 for(i=0; i<6; i++){
1605                     init_put_bits(&s->reorder_pb[i], reorder_buffer[0][i], 7*32);
1606                 }
1607                 if(s->picture.pict_type == P_TYPE){
1608                     const uint8_t *vlc= svq1_block_type_vlc[SVQ1_BLOCK_INTRA];
1609                     put_bits(&s->reorder_pb[5], vlc[1], vlc[0]);
1610                     score[0]= vlc[1]*lambda;
1611                 }
1612                 score[0]+= encode_block(s, src+16*x, NULL, temp, stride, 5, 64, lambda, 1);
1613                 for(i=0; i<6; i++){
1614                     count[0][i]= put_bits_count(&s->reorder_pb[i]);
1615                     flush_put_bits(&s->reorder_pb[i]);
1616                 }
1617             }else
1618                 score[0]= INT_MAX;
1619
1620             best=0;
1621
1622             if(s->picture.pict_type == P_TYPE){
1623                 const uint8_t *vlc= svq1_block_type_vlc[SVQ1_BLOCK_INTER];
1624                 int mx, my, pred_x, pred_y, dxy;
1625                 int16_t *motion_ptr;
1626
1627                 motion_ptr= h263_pred_motion(&s->m, 0, 0, &pred_x, &pred_y);
1628                 if(s->m.mb_type[x + y*s->m.mb_stride]&CANDIDATE_MB_TYPE_INTER){
1629                     for(i=0; i<6; i++)
1630                         init_put_bits(&s->reorder_pb[i], reorder_buffer[1][i], 7*32);
1631
1632                     put_bits(&s->reorder_pb[5], vlc[1], vlc[0]);
1633
1634                     s->m.pb= s->reorder_pb[5];
1635                     mx= motion_ptr[0];
1636                     my= motion_ptr[1];
1637                     assert(mx>=-32 && mx<=31);
1638                     assert(my>=-32 && my<=31);
1639                     assert(pred_x>=-32 && pred_x<=31);
1640                     assert(pred_y>=-32 && pred_y<=31);
1641                     ff_h263_encode_motion(&s->m, mx - pred_x, 1);
1642                     ff_h263_encode_motion(&s->m, my - pred_y, 1);
1643                     s->reorder_pb[5]= s->m.pb;
1644                     score[1] += lambda*put_bits_count(&s->reorder_pb[5]);
1645
1646                     dxy= (mx&1) + 2*(my&1);
1647
1648                     s->dsp.put_pixels_tab[0][dxy](temp+16, ref + (mx>>1) + stride*(my>>1), stride, 16);
1649
1650                     score[1]+= encode_block(s, src+16*x, temp+16, decoded, stride, 5, 64, lambda, 0);
1651                     best= score[1] <= score[0];
1652
1653                     vlc= svq1_block_type_vlc[SVQ1_BLOCK_SKIP];
1654                     score[2]= s->dsp.sse[0](NULL, src+16*x, ref, stride, 16);
1655                     score[2]+= vlc[1]*lambda;
1656                     if(score[2] < score[best] && mx==0 && my==0){
1657                         best=2;
1658                         s->dsp.put_pixels_tab[0][0](decoded, ref, stride, 16);
1659                         for(i=0; i<6; i++){
1660                             count[2][i]=0;
1661                         }
1662                         put_bits(&s->pb, vlc[1], vlc[0]);
1663                     }
1664                 }
1665
1666                 if(best==1){
1667                     for(i=0; i<6; i++){
1668                         count[1][i]= put_bits_count(&s->reorder_pb[i]);
1669                         flush_put_bits(&s->reorder_pb[i]);
1670                     }
1671                 }else{
1672                     motion_ptr[0                 ] = motion_ptr[1                 ]=
1673                     motion_ptr[2                 ] = motion_ptr[3                 ]=
1674                     motion_ptr[0+2*s->m.b8_stride] = motion_ptr[1+2*s->m.b8_stride]=
1675                     motion_ptr[2+2*s->m.b8_stride] = motion_ptr[3+2*s->m.b8_stride]=0;
1676                 }
1677             }
1678
1679             s->rd_total += score[best];
1680
1681             for(i=5; i>=0; i--){
1682                 ff_copy_bits(&s->pb, reorder_buffer[best][i], count[best][i]);
1683             }
1684             if(best==0){
1685                 s->dsp.put_pixels_tab[0][0](decoded, temp, stride, 16);
1686             }
1687
1688 #if 0
1689             for (i = 0; i < 256; i += 16) {
1690                 memcpy(&buffer0[i], &plane[left_edge], 16);
1691                 left_edge += stride;
1692             }
1693             current_buffer = 1;  /* this will toggle to 0 immediately */
1694
1695             /* perform a breadth-first tree encoding for each vector level */
1696             subvector_count = 1;  /* one subvector at level 5 */
1697             for (level = 5; level >= 0; level--) {
1698
1699                 vector_count = subvector_count;
1700                 subvector_count = 0;
1701
1702                 if (current_buffer == 0) {
1703                     current_buffer = 1;
1704                     vector = buffer1;
1705                     subvectors = buffer0;
1706                 } else {
1707                     current_buffer = 0;
1708                     vector = buffer0;
1709                     subvectors = buffer1;
1710                 }
1711
1712                 /* iterate through each vector in the list */
1713                 for (i = 0; i < vector_count; i++) {
1714
1715                     if (encode_vector(s, vector, level, threshold[level])) {
1716
1717 #ifdef DEBUG_SVQ1
1718 av_log(s->avctx, AV_LOG_INFO, "  split to level %d\n", level - 1);
1719 #endif
1720                         /* subdivide into 2 subvectors for later processing */
1721                         subvector_count += 2;
1722
1723                         if (level - 1 == 3) {
1724                             /* subdivide 16x8 -> 2 8x8 */
1725                             for (j = 0; j < 8; j++) {
1726                                 /* left half */
1727                                 memcpy(subvectors + j * 8, vector + j * 16, 8);
1728                                 /* right half */
1729                                 memcpy(subvectors + 64 + j * 8,
1730                                     vector + 8 + j * 16, 8);
1731                             }
1732                             subvectors += 128;
1733                         } else if (level - 1 == 1) {
1734                             /* subdivide 8x4 -> 2 4x4 */
1735                             for (j = 0; j < 4; j++) {
1736                                 /* left half */
1737                                 memcpy(subvectors + j * 4, vector + j * 8, 4);
1738                                 /* right half */
1739                                 memcpy(subvectors + 16 + j * 4,
1740                                     vector + 4 + j * 8, 4);
1741                             }
1742                             subvectors += 32;
1743                         } else {
1744                             /* first half */
1745                             memcpy(subvectors, vector, level_sizes[level - 1]);
1746                             subvectors += level_sizes[level - 1];
1747                             /* second half */
1748                             memcpy(subvectors, vector + level_sizes[level - 1],
1749                                 level_sizes[level - 1]);
1750                             subvectors += level_sizes[level - 1];
1751                         }
1752                     }
1753
1754                     vector += level_sizes[level];
1755                 }
1756
1757                 /* if there are no more subvectors, break early */
1758                 if (!subvector_count)
1759                     break;
1760             }
1761 #endif
1762         }
1763         s->m.first_slice_line=0;
1764     }
1765 }
1766
1767 /* output a plane with a constant mean value; good for debugging and for
1768  * greyscale encoding but only valid for intra frames */
1769 static void svq1_output_intra_constant_mean(SVQ1Context *s, int block_width,
1770     int block_height, unsigned char mean)
1771 {
1772     int i;
1773
1774     /* for each level 5 vector, output the specified mean value */
1775     for (i = 0; i < block_width * block_height; i++) {
1776
1777         /* output a 0 before each vector indicating no subdivision */
1778         put_bits(&s->pb, 1, 0);
1779
1780         /* output a 0 indicating mean-only encoding; use index 1 as that
1781          * maps to code 0 */
1782         put_bits(&s->pb, svq1_intra_multistage_vlc[5][1][1],
1783             svq1_intra_multistage_vlc[5][1][0]);
1784
1785         /* output a constant mean */
1786         put_bits(&s->pb, svq1_intra_mean_vlc[mean][1],
1787             svq1_intra_mean_vlc[mean][0]);
1788 #ifdef DEBUG_SVQ1
1789 av_log(s->avctx, AV_LOG_INFO, "  const L5 %d/%d: multistage = 0 (0x%X, %d), mean = %d (0x%X, %d)\n",
1790   i, block_width * block_height,
1791   svq1_intra_multistage_vlc[5][1][0],
1792   svq1_intra_multistage_vlc[5][1][1],
1793   mean,
1794   svq1_intra_mean_vlc[mean][0],
1795   svq1_intra_mean_vlc[mean][1]);
1796 #endif
1797     }
1798 }
1799
1800 static int svq1_encode_init(AVCodecContext *avctx)
1801 {
1802     SVQ1Context * const s = avctx->priv_data;
1803     int i;
1804     unsigned char least_bits_value = 0;
1805     int least_bits;
1806
1807     dsputil_init(&s->dsp, avctx);
1808     avctx->coded_frame= (AVFrame*)&s->picture;
1809
1810     s->frame_width = avctx->width;
1811     s->frame_height = avctx->height;
1812
1813     s->y_block_width = (s->frame_width + 15) / 16;
1814     s->y_block_height = (s->frame_height + 15) / 16;
1815
1816     s->c_block_width = (s->frame_width / 4 + 15) / 16;
1817     s->c_block_height = (s->frame_height / 4 + 15) / 16;
1818
1819     s->avctx= avctx;
1820     s->m.me.scratchpad= av_mallocz((avctx->width+64)*2*16*2*sizeof(uint8_t));
1821     s->m.me.map       = av_mallocz(ME_MAP_SIZE*sizeof(uint32_t));
1822     s->m.me.score_map = av_mallocz(ME_MAP_SIZE*sizeof(uint32_t));
1823     s->mb_type        = av_mallocz((s->y_block_width+1)*s->y_block_height*sizeof(int16_t));
1824     s->dummy          = av_mallocz((s->y_block_width+1)*s->y_block_height*sizeof(int32_t));
1825     h263_encode_init(&s->m); //mv_penalty
1826
1827 av_log(s->avctx, AV_LOG_INFO, " Hey: %d x %d, %d x %d, %d x %d\n",
1828   s->frame_width, s->frame_height,
1829   s->y_block_width, s->y_block_height,
1830   s->c_block_width, s->c_block_height);
1831
1832     /* allocate a plane for the U & V planes (color, or C, planes) and
1833      * initialize them to the value that is represented by the fewest bits
1834      * in the mean table; the reasoning behind this is that when the border
1835      * vectors are operated upon and possibly subdivided, the mean will be
1836      * removed resulting in a perfect deviation score of 0 and encoded with
1837      * the minimal possible bits */
1838     s->c_plane = av_malloc(s->c_block_width * s->c_block_height * 16 * 16);
1839     least_bits = 10000;
1840     for (i = 0; i < 256; i++)
1841         if (svq1_intra_mean_vlc[i][1] < least_bits) {
1842             least_bits = svq1_intra_mean_vlc[i][1];
1843             least_bits_value = i;
1844         }
1845     memset(s->c_plane, least_bits_value,
1846         s->c_block_width * s->c_block_height * 16 * 16);
1847
1848     return 0;
1849 }
1850
1851 static int svq1_encode_frame(AVCodecContext *avctx, unsigned char *buf,
1852     int buf_size, void *data)
1853 {
1854     SVQ1Context * const s = avctx->priv_data;
1855     AVFrame *pict = data;
1856     AVFrame * const p= (AVFrame*)&s->picture;
1857     AVFrame temp;
1858     int i;
1859
1860     if(avctx->pix_fmt != PIX_FMT_YUV410P){
1861         av_log(avctx, AV_LOG_ERROR, "unsupported pixel format\n");
1862         return -1;
1863     }
1864
1865     if(!s->current_picture.data[0]){
1866         avctx->get_buffer(avctx, &s->current_picture);
1867         avctx->get_buffer(avctx, &s->last_picture);
1868     }
1869
1870     temp= s->current_picture;
1871     s->current_picture= s->last_picture;
1872     s->last_picture= temp;
1873
1874     init_put_bits(&s->pb, buf, buf_size);
1875
1876     *p = *pict;
1877     p->pict_type = avctx->frame_number % avctx->gop_size ? P_TYPE : I_TYPE;
1878     p->key_frame = p->pict_type == I_TYPE;
1879
1880     svq1_write_header(s, p->pict_type);
1881     for(i=0; i<3; i++){
1882         svq1_encode_plane(s, i,
1883             s->picture.data[i], s->last_picture.data[i], s->current_picture.data[i],
1884             s->frame_width / (i?4:1), s->frame_height / (i?4:1),
1885             s->picture.linesize[i], s->current_picture.linesize[i]);
1886     }
1887
1888 //    align_put_bits(&s->pb);
1889     while(put_bits_count(&s->pb) & 31)
1890         put_bits(&s->pb, 1, 0);
1891
1892     flush_put_bits(&s->pb);
1893
1894     return (put_bits_count(&s->pb) / 8);
1895 }
1896
1897 static int svq1_encode_end(AVCodecContext *avctx)
1898 {
1899     SVQ1Context * const s = avctx->priv_data;
1900     int i;
1901
1902     av_log(avctx, AV_LOG_DEBUG, "RD: %f\n", s->rd_total/(double)(avctx->width*avctx->height*avctx->frame_number));
1903
1904     av_freep(&s->c_plane);
1905     av_freep(&s->m.me.scratchpad);
1906     av_freep(&s->m.me.map);
1907     av_freep(&s->m.me.score_map);
1908     av_freep(&s->mb_type);
1909     av_freep(&s->dummy);
1910
1911     for(i=0; i<3; i++){
1912         av_freep(&s->motion_val8[i]);
1913         av_freep(&s->motion_val16[i]);
1914     }
1915
1916     return 0;
1917 }
1918
1919 AVCodec svq1_decoder = {
1920     "svq1",
1921     CODEC_TYPE_VIDEO,
1922     CODEC_ID_SVQ1,
1923     sizeof(MpegEncContext),
1924     svq1_decode_init,
1925     NULL,
1926     svq1_decode_end,
1927     svq1_decode_frame,
1928     CODEC_CAP_DR1,
1929     .flush= ff_mpeg_flush,
1930 };
1931
1932 #ifdef CONFIG_ENCODERS
1933
1934 AVCodec svq1_encoder = {
1935     "svq1",
1936     CODEC_TYPE_VIDEO,
1937     CODEC_ID_SVQ1,
1938     sizeof(SVQ1Context),
1939     svq1_encode_init,
1940     svq1_encode_frame,
1941     svq1_encode_end,
1942 };
1943
1944 #endif //CONFIG_ENCODERS