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