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