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