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