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   *data_size=0;
 719
 720   if(buf==NULL && buf_size==0){
 721       return 0;
 722   }
 723
 724   /* initialize bit buffer */
 725   init_get_bits(&s->gb,buf,buf_size*8);
 726
 727   /* decode frame header */
 728   s->f_code = get_bits (&s->gb, 22);
 729
 730   if ((s->f_code & ~0x70) || !(s->f_code & 0x60))
 731     return -1;
 732
 733   /* swap some header bytes (why?) */
 734   if (s->f_code != 0x20) {
 735     uint32_t *src = (uint32_t *) (buf + 4);
 736
 737     for (i=0; i < 4; i++) {
 738       src[i] = ((src[i] << 16) | (src[i] >> 16)) ^ src[7 - i];
 739     }
 740   }
 741
 742   result = svq1_decode_frame_header (&s->gb, s);
 743
 744   if (result != 0)
 745   {
 746 #ifdef DEBUG_SVQ1
 747     av_log(s->avctx, AV_LOG_INFO, "Error in svq1_decode_frame_header %i\n",result);
 748 #endif
 749     return result;
 750   }
 751
 752   //FIXME this avoids some confusion for "B frames" without 2 references
 753   //this should be removed after libavcodec can handle more flexible picture types & ordering
 754   if(s->pict_type==B_TYPE && s->last_picture_ptr==NULL) return buf_size;
 755
 756   if(avctx->hurry_up && s->pict_type==B_TYPE) return buf_size;
 757
 758   if(MPV_frame_start(s, avctx) < 0)
 759       return -1;
 760
 761   /* decode y, u and v components */
 762   for (i=0; i < 3; i++) {
 763     int linesize;
 764     if (i == 0) {
 765       width  = (s->width+15)&~15;
 766       height = (s->height+15)&~15;
 767       linesize= s->linesize;
 768     } else {
 769       if(s->flags&CODEC_FLAG_GRAY) break;
 770       width  = (s->width/4+15)&~15;
 771       height = (s->height/4+15)&~15;
 772       linesize= s->uvlinesize;
 773     }
 774
 775     current  = s->current_picture.data[i];
 776
 777     if(s->pict_type==B_TYPE){
 778         previous = s->next_picture.data[i];
 779     }else{
 780         previous = s->last_picture.data[i];
 781     }
 782
 783     if (s->pict_type == I_TYPE) {
 784       /* keyframe */
 785       for (y=0; y < height; y+=16) {
 786         for (x=0; x < width; x+=16) {
 787           result = svq1_decode_block_intra (&s->gb, &current[x], linesize);
 788           if (result != 0)
 789           {
 790 //#ifdef DEBUG_SVQ1
 791             av_log(s->avctx, AV_LOG_INFO, "Error in svq1_decode_block %i (keyframe)\n",result);
 792 //#endif
 793             return result;
 794           }
 795         }
 796         current += 16*linesize;
 797       }
 798     } else {
 799       svq1_pmv_t pmv[width/8+3];
 800       /* delta frame */
 801       memset (pmv, 0, ((width / 8) + 3) * sizeof(svq1_pmv_t));
 802
 803       for (y=0; y < height; y+=16) {
 804         for (x=0; x < width; x+=16) {
 805           result = svq1_decode_delta_block (s, &s->gb, &current[x], previous,
 806                                             linesize, pmv, x, y);
 807           if (result != 0)
 808           {
 809 #ifdef DEBUG_SVQ1
 810     av_log(s->avctx, AV_LOG_INFO, "Error in svq1_decode_delta_block %i\n",result);
 811 #endif
 812             return result;
 813           }
 814         }
 815
 816         pmv[0].x =
 817         pmv[0].y = 0;
 818
 819         current += 16*linesize;
 820       }
 821     }
 822   }
 823
 824   *pict = *(AVFrame*)&s->current_picture;
 825
 826
 827   MPV_frame_end(s);
 828
 829   *data_size=sizeof(AVFrame);
 830   return buf_size;
 831 }
 832
 833 static int svq1_decode_init(AVCodecContext *avctx)
 834 {
 835     MpegEncContext *s = avctx->priv_data;
 836     int i;
 837
 838     MPV_decode_defaults(s);
 839
 840     s->avctx = avctx;
 841     s->width = (avctx->width+3)&~3;
 842     s->height = (avctx->height+3)&~3;
 843     s->codec_id= avctx->codec->id;
 844     avctx->pix_fmt = PIX_FMT_YUV410P;
 845     avctx->has_b_frames= 1; // not true, but DP frames and these behave like unidirectional b frames
 846     s->flags= avctx->flags;
 847     if (MPV_common_init(s) < 0) return -1;
 848
 849     init_vlc(&svq1_block_type, 2, 4,
 850         &svq1_block_type_vlc[0][1], 2, 1,
 851         &svq1_block_type_vlc[0][0], 2, 1);
 852
 853     init_vlc(&svq1_motion_component, 7, 33,
 854         &mvtab[0][1], 2, 1,
 855         &mvtab[0][0], 2, 1);
 856
 857     for (i = 0; i < 6; i++) {
 858         init_vlc(&svq1_intra_multistage[i], 3, 8,
 859             &svq1_intra_multistage_vlc[i][0][1], 2, 1,
 860             &svq1_intra_multistage_vlc[i][0][0], 2, 1);
 861         init_vlc(&svq1_inter_multistage[i], 3, 8,
 862             &svq1_inter_multistage_vlc[i][0][1], 2, 1,
 863             &svq1_inter_multistage_vlc[i][0][0], 2, 1);
 864     }
 865
 866     init_vlc(&svq1_intra_mean, 8, 256,
 867         &svq1_intra_mean_vlc[0][1], 4, 2,
 868         &svq1_intra_mean_vlc[0][0], 4, 2);
 869
 870     init_vlc(&svq1_inter_mean, 9, 512,
 871         &svq1_inter_mean_vlc[0][1], 4, 2,
 872         &svq1_inter_mean_vlc[0][0], 4, 2);
 873
 874     return 0;
 875 }
 876
 877 static int svq1_decode_end(AVCodecContext *avctx)
 878 {
 879     MpegEncContext *s = avctx->priv_data;
 880
 881     MPV_common_end(s);
 882     return 0;
 883 }
 884
 885 static void svq1_write_header(SVQ1Context *s, int frame_type)
 886 {
 887     /* frame code */
 888     put_bits(&s->pb, 22, 0x20);
 889
 890     /* temporal reference (sure hope this is a "don't care") */
 891     put_bits(&s->pb, 8, 0x00);
 892
 893     /* frame type */
 894     put_bits(&s->pb, 2, frame_type - 1);
 895
 896     if (frame_type == I_TYPE) {
 897
 898         /* no checksum since frame code is 0x20 */
 899
 900         /* no embedded string either */
 901
 902         /* output 5 unknown bits (2 + 2 + 1) */
 903         put_bits(&s->pb, 5, 0);
 904
 905         /* forget about matching up resolutions, just use the free-form
 906          * resolution code (7) for now */
 907         put_bits(&s->pb, 3, 7);
 908         put_bits(&s->pb, 12, s->frame_width);
 909         put_bits(&s->pb, 12, s->frame_height);
 910
 911     }
 912
 913     /* no checksum or extra data (next 2 bits get 0) */
 914     put_bits(&s->pb, 2, 0);
 915 }
 916
 917 int level_sizes[6] =      { 8, 16, 32, 64, 128, 256 };
 918 int level_log2_sizes[6] = { 3,  4,  5,  6,   7,   8 };
 919
 920 #define IABS(x) ((x < 0) ? (-(x)) : x)
 921
 922
 923
 924 //#define USE_MAD_ALGORITHM
 925
 926 #ifdef USE_MAD_ALGORITHM
 927
 928 #define QUALITY_THRESHOLD 100
 929 #define THRESHOLD_MULTIPLIER 0.6
 930
 931 /* This function calculates vector differences using mean absolute
 932  * difference (MAD). */
 933
 934 static int encode_vector(SVQ1Context *s, unsigned char *vector,
 935     unsigned int level, int threshold)
 936 {
 937     int i, j, k;
 938     int mean;
 939     signed short work_vector[256];
 940     int best_codebook;
 941     int best_score;
 942     int multistage_codebooks[6];
 943     int number_of_stages = 0;
 944     int8_t *current_codebook;
 945     int total_deviation;
 946     int ret;
 947
 948 #ifdef DEBUG_SVQ1
 949 av_log(s->avctx, AV_LOG_INFO, "  ** recursive entry point: encoding level %d vector at threshold %d\n",
 950   level, threshold);
 951 #endif
 952     if (level > 5) {
 953         av_log(s->avctx, AV_LOG_INFO, " help! level %d > 5\n", level);
 954         return 0;
 955     }
 956
 957 #ifdef DEBUG_SVQ1
 958 for (i = 0; i < level_sizes[level]; i++)
 959   av_log(s->avctx, AV_LOG_INFO, " %02X", vector[i]);
 960 av_log(s->avctx, AV_LOG_INFO, "\n");
 961 #endif
 962
 963     /* calculate the mean */
 964     mean = 0;
 965     for (i = 0; i < level_sizes[level]; i++)
 966         mean += vector[i];
 967     mean >>= level_log2_sizes[level];
 968
 969 #ifdef DEBUG_SVQ1
 970 av_log(s->avctx, AV_LOG_INFO, " vector mean = 0x%02X\n", mean);
 971 #endif
 972
 973     /* remove the mean from the vector */
 974     total_deviation = 0;
 975     for (i = 0; i < level_sizes[level]; i++) {
 976         work_vector[i] = (signed short)vector[i] - mean;
 977         total_deviation += IABS(work_vector[i]);
 978 #ifdef DEBUG_SVQ1
 979 av_log(s->avctx, AV_LOG_INFO, " %d", work_vector[i]);
 980 #endif
 981     }
 982
 983 #ifdef DEBUG_SVQ1
 984 av_log(s->avctx, AV_LOG_INFO, "\n  total deviation = %d\n", total_deviation);
 985 #endif
 986
 987     if (total_deviation < threshold) {
 988
 989 #ifdef DEBUG_SVQ1
 990     av_log(s->avctx, AV_LOG_INFO, " mean-only encoding found for level %d vector, mean = %d\n",
 991       level, mean);
 992 #endif
 993
 994         /* indicate that this is the end of the subdivisions */
 995         if (level > 0)
 996             put_bits(&s->pb, 1, 0);
 997
 998         /* index 1 in the table indicates mean-only encoding */
 999         put_bits(&s->pb, svq1_intra_multistage_vlc[level][1][1],
1000             svq1_intra_multistage_vlc[level][1][0]);
1001         put_bits(&s->pb, svq1_intra_mean_vlc[mean][1],
1002             svq1_intra_mean_vlc[mean][0]);
1003
1004 #ifdef DEBUG_SVQ1
1005 av_log(s->avctx, AV_LOG_INFO, "  mean-only L%d, VLC = (0x%X, %d), mean = %d (0x%X, %d)\n",
1006   level,
1007   svq1_intra_multistage_vlc[level][1 + number_of_stages][0],
1008   svq1_intra_multistage_vlc[level][1 + number_of_stages][1],
1009   mean,
1010   svq1_intra_mean_vlc[mean][0],
1011   svq1_intra_mean_vlc[mean][1]);
1012 #endif
1013
1014         ret = 0;
1015
1016     } else {
1017
1018         if (level <= 3) {
1019
1020 #ifdef DEBUG_SVQ1
1021 av_log(s->avctx, AV_LOG_INFO, " multistage VQ search...\n");
1022 #endif
1023             /* conduct multistage VQ search, for each stage... */
1024             for (i = 0; i < 6; i++) {
1025
1026                 best_codebook = 0;
1027                 best_score = 0x7FFFFFFF;
1028                 /* for each codebook in stage */
1029                 for (j = 0; j < 16; j++) {
1030
1031                     total_deviation = 0;
1032                     current_codebook =
1033                         &svq1_intra_codebooks[level]
1034                         [i * level_sizes[level] * 16 + j * level_sizes[level]];
1035                     /* calculate the total deviation for the vector */
1036                     for (k = 0; k < level_sizes[level]; k++) {
1037                         total_deviation +=
1038                             IABS(work_vector[k] - current_codebook[k]);
1039                     }
1040
1041                     /* lowest score so far? */
1042                     if (total_deviation < best_score) {
1043                         best_score = total_deviation;
1044                         best_codebook = j;
1045                     }
1046 #ifdef DEBUG_SVQ1
1047 av_log(s->avctx, AV_LOG_INFO, "  after %d, %d, best codebook is %d with a score of %d (score was %d)\n",
1048   i, j, best_codebook, best_score, total_deviation);
1049 #endif
1050                 }
1051
1052                 /* apply the winning codebook to the work vector and check if
1053                  * the vector meets the quality threshold */
1054                 total_deviation = 0;
1055                 current_codebook =
1056                     &svq1_intra_codebooks[level]
1057                     [i * level_sizes[level] * 16 + j * level_sizes[level]];
1058                 multistage_codebooks[number_of_stages++] = best_codebook;
1059                 for (j = 0; j < level_sizes[level]; j++) {
1060                     work_vector[j] = work_vector[j] - current_codebook[j];
1061                     total_deviation += IABS(work_vector[j]);
1062                 }
1063
1064                 /* do not go forward with the rest of the search if an acceptable
1065                  * codebook combination has been found */
1066                 if (total_deviation < threshold)
1067                     break;
1068             }
1069         }
1070
1071         if ((total_deviation < threshold) || (level == 0)) {
1072 #ifdef DEBUG_SVQ1
1073       av_log(s->avctx, AV_LOG_INFO, " level %d VQ encoding found using mean %d and codebooks", level, mean);
1074       for (i = 0; i < number_of_stages; i++)
1075         av_log(s->avctx, AV_LOG_INFO, " %d", multistage_codebooks[i]);
1076       av_log(s->avctx, AV_LOG_INFO, "\n");
1077 #endif
1078
1079             /* indicate that this is the end of the subdivisions */
1080             if (level > 0)
1081                 put_bits(&s->pb, 1, 0);
1082
1083             /* output the encoding */
1084             put_bits(&s->pb,
1085                 svq1_intra_multistage_vlc[level][1 + number_of_stages][1],
1086                 svq1_intra_multistage_vlc[level][1 + number_of_stages][0]);
1087             put_bits(&s->pb, svq1_intra_mean_vlc[mean][1],
1088                 svq1_intra_mean_vlc[mean][0]);
1089 #ifdef DEBUG_SVQ1
1090 av_log(s->avctx, AV_LOG_INFO, "  L%d: multistage = %d (0x%X, %d), mean = %d (0x%X, %d), codebooks = ",
1091   level,
1092   number_of_stages,
1093   svq1_intra_multistage_vlc[level][1 + number_of_stages][0],
1094   svq1_intra_multistage_vlc[level][1 + number_of_stages][1],
1095   mean,
1096   svq1_intra_mean_vlc[mean][0],
1097   svq1_intra_mean_vlc[mean][1]);
1098 #endif
1099
1100             for (i = 0; i < number_of_stages; i++)
1101 {
1102 #ifdef DEBUG_SVQ1
1103 av_log(s->avctx, AV_LOG_INFO, "%d ", multistage_codebooks[i]);
1104 #endif
1105                 put_bits(&s->pb, 4, multistage_codebooks[i]);
1106 }
1107 #ifdef DEBUG_SVQ1
1108 av_log(s->avctx, AV_LOG_INFO, "\n");
1109 #endif
1110
1111             ret = 0;
1112
1113         } else {
1114
1115             /* output a subdivision bit to the encoded stream and signal to
1116              * the calling function that this vector could not be
1117              * coded at the requested threshold and needs to be subdivided */
1118             put_bits(&s->pb, 1, 1);
1119             ret = 1;
1120         }
1121     }
1122
1123     return ret;
1124 }
1125
1126 #else
1127
1128 #define QUALITY_THRESHOLD 100
1129 #define THRESHOLD_MULTIPLIER 0.6
1130
1131 /* This function calculates vector differences using mean square
1132  * error (MSE). */
1133
1134 static int encode_vector(SVQ1Context *s, unsigned char *vector,
1135     unsigned int level, int threshold)
1136 {
1137     int i, j, k;
1138     int mean;
1139     signed short work_vector[256];
1140     int best_codebook;
1141     int best_score;
1142     int multistage_codebooks[6];
1143     int number_of_stages = 0;
1144     int8_t *current_codebook;
1145     int mse;
1146     int diff;
1147     int ret;
1148
1149 #ifdef DEBUG_SVQ1
1150 av_log(s->avctx, AV_LOG_INFO, "  ** recursive entry point: encoding level %d vector at threshold %d\n",
1151   level, threshold);
1152 #endif
1153     if (level > 5) {
1154         av_log(s->avctx, AV_LOG_INFO, " help! level %d > 5\n", level);
1155         return 0;
1156     }
1157
1158 #ifdef DEBUG_SVQ1
1159 for (i = 0; i < level_sizes[level]; i++)
1160   av_log(s->avctx, AV_LOG_INFO, " %02X", vector[i]);
1161 av_log(s->avctx, AV_LOG_INFO, "\n");
1162 #endif
1163
1164     /* calculate the mean */
1165     mean = 0;
1166     for (i = 0; i < level_sizes[level]; i++)
1167         mean += vector[i];
1168     mean >>= level_log2_sizes[level];
1169
1170 #ifdef DEBUG_SVQ1
1171 av_log(s->avctx, AV_LOG_INFO, " vector mean = 0x%02X\n", mean);
1172 #endif
1173
1174     /* remove the mean from the vector and compute the resulting MSE */
1175     mse = 0;
1176     for (i = 0; i < level_sizes[level]; i++) {
1177         work_vector[i] = (signed short)vector[i] - mean;
1178         mse += (work_vector[i] * work_vector[i]);
1179 #ifdef DEBUG_SVQ1
1180 av_log(s->avctx, AV_LOG_INFO, " %d", work_vector[i]);
1181 #endif
1182     }
1183     mse >>= level_log2_sizes[level];
1184
1185 #ifdef DEBUG_SVQ1
1186 av_log(s->avctx, AV_LOG_INFO, "\n  MSE = %d\n", mse);
1187 #endif
1188
1189     if (mse < threshold) {
1190
1191 #ifdef DEBUG_SVQ1
1192     av_log(s->avctx, AV_LOG_INFO, " mean-only encoding found for level %d vector, mean = %d\n",
1193       level, mean);
1194 #endif
1195
1196         /* indicate that this is the end of the subdivisions */
1197         if (level > 0)
1198             put_bits(&s->pb, 1, 0);
1199
1200         /* index 1 in the table indicates mean-only encoding */
1201         put_bits(&s->pb, svq1_intra_multistage_vlc[level][1][1],
1202             svq1_intra_multistage_vlc[level][1][0]);
1203         put_bits(&s->pb, svq1_intra_mean_vlc[mean][1],
1204             svq1_intra_mean_vlc[mean][0]);
1205
1206 #ifdef DEBUG_SVQ1
1207 av_log(s->avctx, AV_LOG_INFO, "  mean-only L%d, VLC = (0x%X, %d), mean = %d (0x%X, %d)\n",
1208   level,
1209   svq1_intra_multistage_vlc[level][1 + number_of_stages][0],
1210   svq1_intra_multistage_vlc[level][1 + number_of_stages][1],
1211   mean,
1212   svq1_intra_mean_vlc[mean][0],
1213   svq1_intra_mean_vlc[mean][1]);
1214 #endif
1215
1216         ret = 0;
1217
1218     } else {
1219
1220         if (level <= 3) {
1221
1222 #ifdef DEBUG_SVQ1
1223 av_log(s->avctx, AV_LOG_INFO, " multistage VQ search...\n");
1224 #endif
1225             /* conduct multistage VQ search, for each stage... */
1226             for (i = 0; i < 6; i++) {
1227
1228                 best_codebook = 0;
1229                 best_score = 0x7FFFFFFF;
1230                 /* for each codebook in stage */
1231                 for (j = 0; j < 16; j++) {
1232
1233                     mse = 0;
1234                     current_codebook =
1235                         &svq1_intra_codebooks[level]
1236                         [i * level_sizes[level] * 16 + j * level_sizes[level]];
1237                     /* calculate the MSE for this vector */
1238                     for (k = 0; k < level_sizes[level]; k++) {
1239                         diff = work_vector[k] - current_codebook[k];
1240                         mse += (diff * diff);
1241                     }
1242                     mse >>= level_log2_sizes[level];
1243
1244                     /* lowest score so far? */
1245                     if (mse < best_score) {
1246                         best_score = mse;
1247                         best_codebook = j;
1248                     }
1249 #ifdef DEBUG_SVQ1
1250 av_log(s->avctx, AV_LOG_INFO, "  after %d, %d, best codebook is %d with a score of %d (score was %d)\n",
1251   i, j, best_codebook, best_score, mse);
1252 #endif
1253                 }
1254
1255                 /* apply the winning codebook to the work vector and check if
1256                  * the vector meets the quality threshold */
1257                 mse = 0;
1258                 current_codebook =
1259                     &svq1_intra_codebooks[level]
1260                     [i * level_sizes[level] * 16 + j * level_sizes[level]];
1261                 multistage_codebooks[number_of_stages++] = best_codebook;
1262                 for (j = 0; j < level_sizes[level]; j++) {
1263                     work_vector[j] = work_vector[j] - current_codebook[j];
1264                     mse += (work_vector[j] * work_vector[j]);
1265                 }
1266                 mse >>= level_log2_sizes[level];
1267
1268                 /* do not go forward with the rest of the search if an acceptable
1269                  * codebook combination has been found */
1270                 if (mse < threshold)
1271                     break;
1272             }
1273         }
1274
1275         if ((mse < threshold) || (level == 0)) {
1276 #ifdef DEBUG_SVQ1
1277       av_log(s->avctx, AV_LOG_INFO, " level %d VQ encoding found using mean %d and codebooks", level, mean);
1278       for (i = 0; i < number_of_stages; i++)
1279         av_log(s->avctx, AV_LOG_INFO, " %d", multistage_codebooks[i]);
1280       av_log(s->avctx, AV_LOG_INFO, "\n");
1281 #endif
1282
1283             /* indicate that this is the end of the subdivisions */
1284             if (level > 0)
1285                 put_bits(&s->pb, 1, 0);
1286
1287             /* output the encoding */
1288             put_bits(&s->pb,
1289                 svq1_intra_multistage_vlc[level][1 + number_of_stages][1],
1290                 svq1_intra_multistage_vlc[level][1 + number_of_stages][0]);
1291             put_bits(&s->pb, svq1_intra_mean_vlc[mean][1],
1292                 svq1_intra_mean_vlc[mean][0]);
1293 #ifdef DEBUG_SVQ1
1294 av_log(s->avctx, AV_LOG_INFO, "  L%d: multistage = %d (0x%X, %d), mean = %d (0x%X, %d), codebooks = ",
1295   level,
1296   number_of_stages,
1297   svq1_intra_multistage_vlc[level][1 + number_of_stages][0],
1298   svq1_intra_multistage_vlc[level][1 + number_of_stages][1],
1299   mean,
1300   svq1_intra_mean_vlc[mean][0],
1301   svq1_intra_mean_vlc[mean][1]);
1302 #endif
1303
1304             for (i = 0; i < number_of_stages; i++)
1305 {
1306 #ifdef DEBUG_SVQ1
1307 av_log(s->avctx, AV_LOG_INFO, "%d ", multistage_codebooks[i]);
1308 #endif
1309                 put_bits(&s->pb, 4, multistage_codebooks[i]);
1310 }
1311 #ifdef DEBUG_SVQ1
1312 av_log(s->avctx, AV_LOG_INFO, "\n");
1313 #endif
1314
1315             ret = 0;
1316
1317         } else {
1318
1319             /* output a subdivision bit to the encoded stream and signal to
1320              * the calling function that this vector could not be
1321              * coded at the requested threshold and needs to be subdivided */
1322             put_bits(&s->pb, 1, 1);
1323             ret = 1;
1324         }
1325     }
1326
1327     return ret;
1328 }
1329 #endif
1330
1331 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){
1332     int count, y, x, i, j, split, best_mean, best_score, best_count;
1333     int best_vector[6];
1334     int block_sum[7]= {0, 0, 0, 0, 0, 0};
1335     int w= 2<<((level+2)>>1);
1336     int h= 2<<((level+1)>>1);
1337     int size=w*h;
1338     int16_t block[7][256];
1339     const int8_t *codebook_sum, *codebook;
1340     const uint16_t (*mean_vlc)[2];
1341     const uint8_t (*multistage_vlc)[2];
1342
1343     best_score=0;
1344     //FIXME optimize, this doenst need to be done multiple times
1345     if(intra){
1346         codebook_sum= svq1_intra_codebook_sum[level];
1347         codebook= svq1_intra_codebooks[level];
1348         mean_vlc= svq1_intra_mean_vlc;
1349         multistage_vlc= svq1_intra_multistage_vlc[level];
1350         for(y=0; y<h; y++){
1351             for(x=0; x<w; x++){
1352                 int v= src[x + y*stride];
1353                 block[0][x + w*y]= v;
1354                 best_score += v*v;
1355                 block_sum[0] += v;
1356             }
1357         }
1358     }else{
1359         codebook_sum= svq1_inter_codebook_sum[level];
1360         codebook= svq1_inter_codebooks[level];
1361         mean_vlc= svq1_inter_mean_vlc + 256;
1362         multistage_vlc= svq1_inter_multistage_vlc[level];
1363         for(y=0; y<h; y++){
1364             for(x=0; x<w; x++){
1365                 int v= src[x + y*stride] - ref[x + y*stride];
1366                 block[0][x + w*y]= v;
1367                 best_score += v*v;
1368                 block_sum[0] += v;
1369             }
1370         }
1371     }
1372
1373     best_count=0;
1374     best_score -= ((block_sum[0]*block_sum[0])>>(level+3));
1375     best_mean= (block_sum[0] + (size>>1)) >> (level+3);
1376
1377     if(level<4){
1378         for(count=1; count<7; count++){
1379             int best_vector_score= INT_MAX;
1380             int best_vector_sum=-999, best_vector_mean=-999;
1381             const int stage= count-1;
1382             const int8_t *vector;
1383
1384             for(i=0; i<16; i++){
1385                 int sum= codebook_sum[stage*16 + i];
1386                 int sqr=0;
1387                 int diff, mean, score;
1388
1389                 vector = codebook + stage*size*16 + i*size;
1390
1391                 for(j=0; j<size; j++){
1392                     int v= vector[j];
1393                     sqr += (v - block[stage][j])*(v - block[stage][j]);
1394                 }
1395                 diff= block_sum[stage] - sum;
1396                 mean= (diff + (size>>1)) >> (level+3);
1397                 assert(mean >-300 && mean<300);
1398                 if(intra) mean= clip(mean, 0, 255);
1399                 else      mean= clip(mean, -256, 255);
1400                 score= sqr - ((diff*(int64_t)diff)>>(level+3)); //FIXME 64bit slooow
1401                 if(score < best_vector_score){
1402                     best_vector_score= score;
1403                     best_vector[stage]= i;
1404                     best_vector_sum= sum;
1405                     best_vector_mean= mean;
1406                 }
1407             }
1408             assert(best_vector_mean != -999);
1409             vector= codebook + stage*size*16 + best_vector[stage]*size;
1410             for(j=0; j<size; j++){
1411                 block[stage+1][j] = block[stage][j] - vector[j];
1412             }
1413             block_sum[stage+1]= block_sum[stage] - best_vector_sum;
1414             best_vector_score +=
1415                 lambda*(+ 1 + 4*count
1416                         + multistage_vlc[1+count][1]
1417                         + mean_vlc[best_vector_mean][1]);
1418
1419             if(best_vector_score < best_score){
1420                 best_score= best_vector_score;
1421                 best_count= count;
1422                 best_mean= best_vector_mean;
1423             }
1424         }
1425     }
1426
1427     split=0;
1428     if(best_score > threshold && level){
1429         int score=0;
1430         int offset= (level&1) ? stride*h/2 : w/2;
1431         PutBitContext backup[6];
1432
1433         for(i=level-1; i>=0; i--){
1434             backup[i]= s->reorder_pb[i];
1435         }
1436         score += encode_block(s, src         , ref         , decoded         , stride, level-1, threshold>>1, lambda, intra);
1437         score += encode_block(s, src + offset, ref + offset, decoded + offset, stride, level-1, threshold>>1, lambda, intra);
1438         score += lambda;
1439
1440         if(score < best_score){
1441             best_score= score;
1442             split=1;
1443         }else{
1444             for(i=level-1; i>=0; i--){
1445                 s->reorder_pb[i]= backup[i];
1446             }
1447         }
1448     }
1449     if (level > 0)
1450         put_bits(&s->reorder_pb[level], 1, split);
1451
1452     if(!split){
1453         assert((best_mean >= 0 && best_mean<256) || !intra);
1454         assert(best_mean >= -256 && best_mean<256);
1455         assert(best_count >=0 && best_count<7);
1456         assert(level<4 || best_count==0);
1457
1458         /* output the encoding */
1459         put_bits(&s->reorder_pb[level],
1460             multistage_vlc[1 + best_count][1],
1461             multistage_vlc[1 + best_count][0]);
1462         put_bits(&s->reorder_pb[level], mean_vlc[best_mean][1],
1463             mean_vlc[best_mean][0]);
1464
1465         for (i = 0; i < best_count; i++){
1466             assert(best_vector[i]>=0 && best_vector[i]<16);
1467             put_bits(&s->reorder_pb[level], 4, best_vector[i]);
1468         }
1469
1470         for(y=0; y<h; y++){
1471             for(x=0; x<w; x++){
1472                 decoded[x + y*stride]= src[x + y*stride] - block[best_count][x + w*y] + best_mean;
1473             }
1474         }
1475     }
1476
1477     return best_score;
1478 }
1479
1480 static void svq1_encode_plane(SVQ1Context *s, int plane, unsigned char *src_plane, unsigned char *ref_plane, unsigned char *decoded_plane,
1481     int width, int height, int src_stride, int stride)
1482 {
1483     unsigned char buffer0[256];
1484     unsigned char buffer1[256];
1485     int current_buffer;
1486     unsigned char *vector;
1487     unsigned char *subvectors;
1488     int vector_count;
1489     int subvector_count;
1490     int x, y;
1491     int i, j;
1492     int block_width, block_height;
1493     int left_edge;
1494     int level;
1495     int threshold[6];
1496     const int lambda= (s->picture.quality*s->picture.quality) >> (2*FF_LAMBDA_SHIFT);
1497
1498 static int frame = 0;
1499
1500 #ifdef DEBUG_SVQ1
1501 av_log(s->avctx, AV_LOG_INFO, "********* frame #%d\n", frame++);
1502 #endif
1503
1504     /* figure out the acceptable level thresholds in advance */
1505     threshold[5] = QUALITY_THRESHOLD;
1506     for (level = 4; level >= 0; level--)
1507         threshold[level] = threshold[level + 1] * THRESHOLD_MULTIPLIER;
1508
1509     block_width = (width + 15) / 16;
1510     block_height = (height + 15) / 16;
1511
1512     if(s->picture.pict_type == P_TYPE){
1513         s->m.avctx= s->avctx;
1514         s->m.current_picture_ptr= &s->m.current_picture;
1515         s->m.last_picture_ptr   = &s->m.last_picture;
1516         s->m.last_picture.data[0]= ref_plane;
1517         s->m.linesize=
1518         s->m.last_picture.linesize[0]=
1519         s->m.new_picture.linesize[0]=
1520         s->m.current_picture.linesize[0]= stride;
1521         s->m.width= width;
1522         s->m.height= height;
1523         s->m.mb_width= block_width;
1524         s->m.mb_height= block_height;
1525         s->m.mb_stride= s->m.mb_width+1;
1526         s->m.b8_stride= 2*s->m.mb_width+1;
1527         s->m.f_code=1;
1528         s->m.pict_type= s->picture.pict_type;
1529         s->m.qscale= s->picture.quality/FF_QP2LAMBDA;
1530         s->m.me_method= s->avctx->me_method;
1531
1532         if(!s->motion_val8[plane]){
1533             s->motion_val8 [plane]= av_mallocz(s->m.b8_stride*block_height*2*2*sizeof(int16_t));
1534             s->motion_val16[plane]= av_mallocz(s->m.mb_stride*block_height*2*sizeof(int16_t));
1535         }
1536
1537         s->m.mb_type= s->mb_type;
1538
1539         //dummies, to avoid segfaults
1540         s->m.current_picture.mb_mean= s->dummy;
1541         s->m.current_picture.mb_var= s->dummy;
1542         s->m.current_picture.mc_mb_var= s->dummy;
1543         s->m.current_picture.mb_type= s->dummy;
1544
1545         s->m.current_picture.motion_val[0]= s->motion_val8[plane];
1546         s->m.p_mv_table= s->motion_val16[plane];
1547         s->m.dsp= s->dsp; //move
1548         ff_init_me(&s->m);
1549
1550         s->m.me.dia_size= s->avctx->dia_size;
1551         s->m.first_slice_line=1;
1552         for (y = 0; y < block_height; y++) {
1553             uint8_t src[stride*16];
1554
1555             s->m.new_picture.data[0]= src - y*16*stride; //ugly
1556             s->m.mb_y= y;
1557
1558             for(i=0; i<16 && i + 16*y<height; i++){
1559                 memcpy(&src[i*stride], &src_plane[(i+16*y)*src_stride], width);
1560                 for(x=width; x<16*block_width; x++)
1561                     src[i*stride+x]= src[i*stride+x-1];
1562             }
1563             for(; i<16 && i + 16*y<16*block_height; i++)
1564                 memcpy(&src[i*stride], &src[(i-1)*stride], 16*block_width);
1565
1566             for (x = 0; x < block_width; x++) {
1567                 s->m.mb_x= x;
1568                 ff_init_block_index(&s->m);
1569                 ff_update_block_index(&s->m);
1570
1571                 ff_estimate_p_frame_motion(&s->m, x, y);
1572             }
1573             s->m.first_slice_line=0;
1574         }
1575
1576         ff_fix_long_p_mvs(&s->m);
1577         ff_fix_long_mvs(&s->m, NULL, 0, s->m.p_mv_table, s->m.f_code, CANDIDATE_MB_TYPE_INTER, 0);
1578     }
1579
1580     s->m.first_slice_line=1;
1581     for (y = 0; y < block_height; y++) {
1582         uint8_t src[stride*16];
1583
1584         for(i=0; i<16 && i + 16*y<height; i++){
1585             memcpy(&src[i*stride], &src_plane[(i+16*y)*src_stride], width);
1586             for(x=width; x<16*block_width; x++)
1587                 src[i*stride+x]= src[i*stride+x-1];
1588         }
1589         for(; i<16 && i + 16*y<16*block_height; i++)
1590             memcpy(&src[i*stride], &src[(i-1)*stride], 16*block_width);
1591
1592         s->m.mb_y= y;
1593         for (x = 0; x < block_width; x++) {
1594             uint8_t reorder_buffer[3][6][7*32];
1595             int count[3][6];
1596             int offset = y * 16 * stride + x * 16;
1597             uint8_t *decoded= decoded_plane + offset;
1598             uint8_t *ref= ref_plane + offset;
1599             int score[4]={0,0,0,0}, best;
1600             uint8_t temp[16*stride];
1601
1602             s->m.mb_x= x;
1603             ff_init_block_index(&s->m);
1604             ff_update_block_index(&s->m);
1605 #ifdef DEBUG_SVQ1
1606 av_log(s->avctx, AV_LOG_INFO, "* level 5 vector @ %d, %d:\n", x * 16, y * 16);
1607 #endif
1608
1609             if(s->picture.pict_type == I_TYPE || (s->m.mb_type[x + y*s->m.mb_stride]&CANDIDATE_MB_TYPE_INTRA)){
1610                 for(i=0; i<6; i++){
1611                     init_put_bits(&s->reorder_pb[i], reorder_buffer[0][i], 7*32);
1612                 }
1613                 if(s->picture.pict_type == P_TYPE){
1614                     const uint8_t *vlc= svq1_block_type_vlc[SVQ1_BLOCK_INTRA];
1615                     put_bits(&s->reorder_pb[5], vlc[1], vlc[0]);
1616                     score[0]= vlc[1]*lambda;
1617                 }
1618                 score[0]+= encode_block(s, src+16*x, NULL, temp, stride, 5, 64, lambda, 1);
1619                 for(i=0; i<6; i++){
1620                     count[0][i]= put_bits_count(&s->reorder_pb[i]);
1621                     flush_put_bits(&s->reorder_pb[i]);
1622                 }
1623             }else
1624                 score[0]= INT_MAX;
1625
1626             best=0;
1627
1628             if(s->picture.pict_type == P_TYPE){
1629                 const uint8_t *vlc= svq1_block_type_vlc[SVQ1_BLOCK_INTER];
1630                 int mx, my, pred_x, pred_y, dxy;
1631                 int16_t *motion_ptr;
1632
1633                 motion_ptr= h263_pred_motion(&s->m, 0, 0, &pred_x, &pred_y);
1634                 if(s->m.mb_type[x + y*s->m.mb_stride]&CANDIDATE_MB_TYPE_INTER){
1635                     for(i=0; i<6; i++)
1636                         init_put_bits(&s->reorder_pb[i], reorder_buffer[1][i], 7*32);
1637
1638                     put_bits(&s->reorder_pb[5], vlc[1], vlc[0]);
1639
1640                     s->m.pb= s->reorder_pb[5];
1641                     mx= motion_ptr[0];
1642                     my= motion_ptr[1];
1643                     assert(mx>=-32 && mx<=31);
1644                     assert(my>=-32 && my<=31);
1645                     assert(pred_x>=-32 && pred_x<=31);
1646                     assert(pred_y>=-32 && pred_y<=31);
1647                     ff_h263_encode_motion(&s->m, mx - pred_x, 1);
1648                     ff_h263_encode_motion(&s->m, my - pred_y, 1);
1649                     s->reorder_pb[5]= s->m.pb;
1650                     score[1] += lambda*put_bits_count(&s->reorder_pb[5]);
1651
1652                     dxy= (mx&1) + 2*(my&1);
1653
1654                     s->dsp.put_pixels_tab[0][dxy](temp+16, ref + (mx>>1) + stride*(my>>1), stride, 16);
1655
1656                     score[1]+= encode_block(s, src+16*x, temp+16, decoded, stride, 5, 64, lambda, 0);
1657                     best= score[1] <= score[0];
1658
1659                     vlc= svq1_block_type_vlc[SVQ1_BLOCK_SKIP];
1660                     score[2]= s->dsp.sse[0](NULL, src+16*x, ref, stride, 16);
1661                     score[2]+= vlc[1]*lambda;
1662                     if(score[2] < score[best] && mx==0 && my==0){
1663                         best=2;
1664                         s->dsp.put_pixels_tab[0][0](decoded, ref, stride, 16);
1665                         for(i=0; i<6; i++){
1666                             count[2][i]=0;
1667                         }
1668                         put_bits(&s->pb, vlc[1], vlc[0]);
1669                     }
1670                 }
1671
1672                 if(best==1){
1673                     for(i=0; i<6; i++){
1674                         count[1][i]= put_bits_count(&s->reorder_pb[i]);
1675                         flush_put_bits(&s->reorder_pb[i]);
1676                     }
1677                 }else{
1678                     motion_ptr[0                 ] = motion_ptr[1                 ]=
1679                     motion_ptr[2                 ] = motion_ptr[3                 ]=
1680                     motion_ptr[0+2*s->m.b8_stride] = motion_ptr[1+2*s->m.b8_stride]=
1681                     motion_ptr[2+2*s->m.b8_stride] = motion_ptr[3+2*s->m.b8_stride]=0;
1682                 }
1683             }
1684
1685             s->rd_total += score[best];
1686
1687             for(i=5; i>=0; i--){
1688                 ff_copy_bits(&s->pb, reorder_buffer[best][i], count[best][i]);
1689             }
1690             if(best==0){
1691                 s->dsp.put_pixels_tab[0][0](decoded, temp, stride, 16);
1692             }
1693
1694 #if 0
1695             for (i = 0; i < 256; i += 16) {
1696                 memcpy(&buffer0[i], &plane[left_edge], 16);
1697                 left_edge += stride;
1698             }
1699             current_buffer = 1;  /* this will toggle to 0 immediately */
1700
1701             /* perform a breadth-first tree encoding for each vector level */
1702             subvector_count = 1;  /* one subvector at level 5 */
1703             for (level = 5; level >= 0; level--) {
1704
1705                 vector_count = subvector_count;
1706                 subvector_count = 0;
1707
1708                 if (current_buffer == 0) {
1709                     current_buffer = 1;
1710                     vector = buffer1;
1711                     subvectors = buffer0;
1712                 } else {
1713                     current_buffer = 0;
1714                     vector = buffer0;
1715                     subvectors = buffer1;
1716                 }
1717
1718                 /* iterate through each vector in the list */
1719                 for (i = 0; i < vector_count; i++) {
1720
1721                     if (encode_vector(s, vector, level, threshold[level])) {
1722
1723 #ifdef DEBUG_SVQ1
1724 av_log(s->avctx, AV_LOG_INFO, "  split to level %d\n", level - 1);
1725 #endif
1726                         /* subdivide into 2 subvectors for later processing */
1727                         subvector_count += 2;
1728
1729                         if (level - 1 == 3) {
1730                             /* subdivide 16x8 -> 2 8x8 */
1731                             for (j = 0; j < 8; j++) {
1732                                 /* left half */
1733                                 memcpy(subvectors + j * 8, vector + j * 16, 8);
1734                                 /* right half */
1735                                 memcpy(subvectors + 64 + j * 8,
1736                                     vector + 8 + j * 16, 8);
1737                             }
1738                             subvectors += 128;
1739                         } else if (level - 1 == 1) {
1740                             /* subdivide 8x4 -> 2 4x4 */
1741                             for (j = 0; j < 4; j++) {
1742                                 /* left half */
1743                                 memcpy(subvectors + j * 4, vector + j * 8, 4);
1744                                 /* right half */
1745                                 memcpy(subvectors + 16 + j * 4,
1746                                     vector + 4 + j * 8, 4);
1747                             }
1748                             subvectors += 32;
1749                         } else {
1750                             /* first half */
1751                             memcpy(subvectors, vector, level_sizes[level - 1]);
1752                             subvectors += level_sizes[level - 1];
1753                             /* second half */
1754                             memcpy(subvectors, vector + level_sizes[level - 1],
1755                                 level_sizes[level - 1]);
1756                             subvectors += level_sizes[level - 1];
1757                         }
1758                     }
1759
1760                     vector += level_sizes[level];
1761                 }
1762
1763                 /* if there are no more subvectors, break early */
1764                 if (!subvector_count)
1765                     break;
1766             }
1767 #endif
1768         }
1769         s->m.first_slice_line=0;
1770     }
1771 }
1772
1773 /* output a plane with a constant mean value; good for debugging and for
1774  * greyscale encoding but only valid for intra frames */
1775 static void svq1_output_intra_constant_mean(SVQ1Context *s, int block_width,
1776     int block_height, unsigned char mean)
1777 {
1778     int i;
1779
1780     /* for each level 5 vector, output the specified mean value */
1781     for (i = 0; i < block_width * block_height; i++) {
1782
1783         /* output a 0 before each vector indicating no subdivision */
1784         put_bits(&s->pb, 1, 0);
1785
1786         /* output a 0 indicating mean-only encoding; use index 1 as that
1787          * maps to code 0 */
1788         put_bits(&s->pb, svq1_intra_multistage_vlc[5][1][1],
1789             svq1_intra_multistage_vlc[5][1][0]);
1790
1791         /* output a constant mean */
1792         put_bits(&s->pb, svq1_intra_mean_vlc[mean][1],
1793             svq1_intra_mean_vlc[mean][0]);
1794 #ifdef DEBUG_SVQ1
1795 av_log(s->avctx, AV_LOG_INFO, "  const L5 %d/%d: multistage = 0 (0x%X, %d), mean = %d (0x%X, %d)\n",
1796   i, block_width * block_height,
1797   svq1_intra_multistage_vlc[5][1][0],
1798   svq1_intra_multistage_vlc[5][1][1],
1799   mean,
1800   svq1_intra_mean_vlc[mean][0],
1801   svq1_intra_mean_vlc[mean][1]);
1802 #endif
1803     }
1804 }
1805
1806 static int svq1_encode_init(AVCodecContext *avctx)
1807 {
1808     SVQ1Context * const s = avctx->priv_data;
1809     int i;
1810     unsigned char least_bits_value = 0;
1811     int least_bits;
1812
1813     dsputil_init(&s->dsp, avctx);
1814     avctx->coded_frame= (AVFrame*)&s->picture;
1815
1816     s->frame_width = avctx->width;
1817     s->frame_height = avctx->height;
1818
1819     s->y_block_width = (s->frame_width + 15) / 16;
1820     s->y_block_height = (s->frame_height + 15) / 16;
1821
1822     s->c_block_width = (s->frame_width / 4 + 15) / 16;
1823     s->c_block_height = (s->frame_height / 4 + 15) / 16;
1824
1825     s->avctx= avctx;
1826     s->m.me.scratchpad= av_mallocz((avctx->width+64)*2*16*2*sizeof(uint8_t));
1827     s->m.me.map       = av_mallocz(ME_MAP_SIZE*sizeof(uint32_t));
1828     s->m.me.score_map = av_mallocz(ME_MAP_SIZE*sizeof(uint32_t));
1829     s->mb_type        = av_mallocz((s->y_block_width+1)*s->y_block_height*sizeof(int16_t));
1830     s->dummy          = av_mallocz((s->y_block_width+1)*s->y_block_height*sizeof(int32_t));
1831     h263_encode_init(&s->m); //mv_penalty
1832
1833 av_log(s->avctx, AV_LOG_INFO, " Hey: %d x %d, %d x %d, %d x %d\n",
1834   s->frame_width, s->frame_height,
1835   s->y_block_width, s->y_block_height,
1836   s->c_block_width, s->c_block_height);
1837
1838     /* allocate a plane for the U & V planes (color, or C, planes) and
1839      * initialize them to the value that is represented by the fewest bits
1840      * in the mean table; the reasoning behind this is that when the border
1841      * vectors are operated upon and possibly subdivided, the mean will be
1842      * removed resulting in a perfect deviation score of 0 and encoded with
1843      * the minimal possible bits */
1844     s->c_plane = av_malloc(s->c_block_width * s->c_block_height * 16 * 16);
1845     least_bits = 10000;
1846     for (i = 0; i < 256; i++)
1847         if (svq1_intra_mean_vlc[i][1] < least_bits) {
1848             least_bits = svq1_intra_mean_vlc[i][1];
1849             least_bits_value = i;
1850         }
1851     memset(s->c_plane, least_bits_value,
1852         s->c_block_width * s->c_block_height * 16 * 16);
1853
1854     return 0;
1855 }
1856
1857 static int svq1_encode_frame(AVCodecContext *avctx, unsigned char *buf,
1858     int buf_size, void *data)
1859 {
1860     SVQ1Context * const s = avctx->priv_data;
1861     AVFrame *pict = data;
1862     AVFrame * const p= (AVFrame*)&s->picture;
1863     AVFrame temp;
1864     int i;
1865
1866     if(avctx->pix_fmt != PIX_FMT_YUV410P){
1867         av_log(avctx, AV_LOG_ERROR, "unsupported pixel format\n");
1868         return -1;
1869     }
1870
1871     if(!s->current_picture.data[0]){
1872         avctx->get_buffer(avctx, &s->current_picture);
1873         avctx->get_buffer(avctx, &s->last_picture);
1874     }
1875
1876     temp= s->current_picture;
1877     s->current_picture= s->last_picture;
1878     s->last_picture= temp;
1879
1880     init_put_bits(&s->pb, buf, buf_size);
1881
1882     *p = *pict;
1883     p->pict_type = avctx->frame_number % avctx->gop_size ? P_TYPE : I_TYPE;
1884     p->key_frame = p->pict_type == I_TYPE;
1885
1886     svq1_write_header(s, p->pict_type);
1887     for(i=0; i<3; i++){
1888         svq1_encode_plane(s, i,
1889             s->picture.data[i], s->last_picture.data[i], s->current_picture.data[i],
1890             s->frame_width / (i?4:1), s->frame_height / (i?4:1),
1891             s->picture.linesize[i], s->current_picture.linesize[i]);
1892     }
1893
1894 //    align_put_bits(&s->pb);
1895     while(put_bits_count(&s->pb) & 31)
1896         put_bits(&s->pb, 1, 0);
1897
1898     flush_put_bits(&s->pb);
1899
1900     return (put_bits_count(&s->pb) / 8);
1901 }
1902
1903 static int svq1_encode_end(AVCodecContext *avctx)
1904 {
1905     SVQ1Context * const s = avctx->priv_data;
1906     int i;
1907
1908     av_log(avctx, AV_LOG_DEBUG, "RD: %f\n", s->rd_total/(double)(avctx->width*avctx->height*avctx->frame_number));
1909
1910     av_freep(&s->c_plane);
1911     av_freep(&s->m.me.scratchpad);
1912     av_freep(&s->m.me.map);
1913     av_freep(&s->m.me.score_map);
1914     av_freep(&s->mb_type);
1915     av_freep(&s->dummy);
1916
1917     for(i=0; i<3; i++){
1918         av_freep(&s->motion_val8[i]);
1919         av_freep(&s->motion_val16[i]);
1920     }
1921
1922     return 0;
1923 }
1924
1925 AVCodec svq1_decoder = {
1926     "svq1",
1927     CODEC_TYPE_VIDEO,
1928     CODEC_ID_SVQ1,
1929     sizeof(MpegEncContext),
1930     svq1_decode_init,
1931     NULL,
1932     svq1_decode_end,
1933     svq1_decode_frame,
1934     CODEC_CAP_DR1,
1935     .flush= ff_mpeg_flush,
1936     .pix_fmts= (enum PixelFormat[]){PIX_FMT_YUV410P, -1},
1937 };
1938
1939 #ifdef CONFIG_ENCODERS
1940
1941 AVCodec svq1_encoder = {
1942     "svq1",
1943     CODEC_TYPE_VIDEO,
1944     CODEC_ID_SVQ1,
1945     sizeof(SVQ1Context),
1946     svq1_encode_init,
1947     svq1_encode_frame,
1948     svq1_encode_end,
1949     .pix_fmts= (enum PixelFormat[]){PIX_FMT_YUV410P, -1},
1950 };
1951
1952 #endif //CONFIG_ENCODERS