1 /**************************************************************************
2  *
3  * Copyright 2011 Maarten Lankhorst
4  * Copyright 2011 Christian König
5  * All Rights Reserved.
6  *
7  * Permission is hereby granted, free of charge, to any person obtaining a
8  * copy of this software and associated documentation files (the
9  * "Software"), to deal in the Software without restriction, including
10  * without limitation the rights to use, copy, modify, merge, publish,
11  * distribute, sub license, and/or sell copies of the Software, and to
12  * permit persons to whom the Software is furnished to do so, subject to
13  * the following conditions:
14  *
15  * The above copyright notice and this permission notice (including the
16  * next paragraph) shall be included in all copies or substantial portions
17  * of the Software.
18  *
19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
20  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
22  * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
23  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
24  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
25  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26  *
27  **************************************************************************/
28 
29 #include "pipe/p_video_codec.h"
30 #include "util/u_memory.h"
31 
32 #include "vl_vlc.h"
33 #include "vl_mpeg12_bitstream.h"
34 
35 enum {
36    dct_End_of_Block = 0xFF,
37    dct_Escape = 0xFE,
38    dct_DC = 0xFD,
39    dct_AC = 0xFC
40 };
41 
42 struct dct_coeff
43 {
44    uint8_t length;
45    uint8_t run;
46    int16_t level;
47 };
48 
49 struct dct_coeff_compressed
50 {
51    uint32_t bitcode;
52    struct dct_coeff coeff;
53 };
54 
55 /* coding table as found in the spec annex B.5 table B-1 */
56 static const struct vl_vlc_compressed macroblock_address_increment[] = {
57    { 0x8000, { 1, 1 } },
58    { 0x6000, { 3, 2 } },
59    { 0x4000, { 3, 3 } },
60    { 0x3000, { 4, 4 } },
61    { 0x2000, { 4, 5 } },
62    { 0x1800, { 5, 6 } },
63    { 0x1000, { 5, 7 } },
64    { 0x0e00, { 7, 8 } },
65    { 0x0c00, { 7, 9 } },
66    { 0x0b00, { 8, 10 } },
67    { 0x0a00, { 8, 11 } },
68    { 0x0900, { 8, 12 } },
69    { 0x0800, { 8, 13 } },
70    { 0x0700, { 8, 14 } },
71    { 0x0600, { 8, 15 } },
72    { 0x05c0, { 10, 16 } },
73    { 0x0580, { 10, 17 } },
74    { 0x0540, { 10, 18 } },
75    { 0x0500, { 10, 19 } },
76    { 0x04c0, { 10, 20 } },
77    { 0x0480, { 10, 21 } },
78    { 0x0460, { 11, 22 } },
79    { 0x0440, { 11, 23 } },
80    { 0x0420, { 11, 24 } },
81    { 0x0400, { 11, 25 } },
82    { 0x03e0, { 11, 26 } },
83    { 0x03c0, { 11, 27 } },
84    { 0x03a0, { 11, 28 } },
85    { 0x0380, { 11, 29 } },
86    { 0x0360, { 11, 30 } },
87    { 0x0340, { 11, 31 } },
88    { 0x0320, { 11, 32 } },
89    { 0x0300, { 11, 33 } }
90 };
91 
92 #define Q PIPE_MPEG12_MB_TYPE_QUANT
93 #define F PIPE_MPEG12_MB_TYPE_MOTION_FORWARD
94 #define B PIPE_MPEG12_MB_TYPE_MOTION_BACKWARD
95 #define P PIPE_MPEG12_MB_TYPE_PATTERN
96 #define I PIPE_MPEG12_MB_TYPE_INTRA
97 
98 /* coding table as found in the spec annex B.5 table B-2 */
99 static const struct vl_vlc_compressed macroblock_type_i[] = {
100    { 0x8000, { 1, I } },
101    { 0x4000, { 2, Q|I } }
102 };
103 
104 /* coding table as found in the spec annex B.5 table B-3 */
105 static const struct vl_vlc_compressed macroblock_type_p[] = {
106    { 0x8000, { 1, F|P } },
107    { 0x4000, { 2, P } },
108    { 0x2000, { 3, F } },
109    { 0x1800, { 5, I } },
110    { 0x1000, { 5, Q|F|P } },
111    { 0x0800, { 5, Q|P } },
112    { 0x0400, { 6, Q|I } }
113 };
114 
115 /* coding table as found in the spec annex B.5 table B-4 */
116 static const struct vl_vlc_compressed macroblock_type_b[] = {
117    { 0x8000, { 2, F|B } },
118    { 0xC000, { 2, F|B|P } },
119    { 0x4000, { 3, B } },
120    { 0x6000, { 3, B|P } },
121    { 0x2000, { 4, F } },
122    { 0x3000, { 4, F|P } },
123    { 0x1800, { 5, I } },
124    { 0x1000, { 5, Q|F|B|P } },
125    { 0x0C00, { 6, Q|F|P } },
126    { 0x0800, { 6, Q|B|P } },
127    { 0x0400, { 6, Q|I } }
128 };
129 
130 #undef Q
131 #undef F
132 #undef B
133 #undef P
134 #undef I
135 
136 /* coding table as found in the spec annex B.5 table B-9 */
137 static const struct vl_vlc_compressed coded_block_pattern[] = {
138    { 0xE000, { 3, 60 } },
139    { 0xD000, { 4, 4 } },
140    { 0xC000, { 4, 8 } },
141    { 0xB000, { 4, 16 } },
142    { 0xA000, { 4, 32 } },
143    { 0x9800, { 5, 12 } },
144    { 0x9000, { 5, 48 } },
145    { 0x8800, { 5, 20 } },
146    { 0x8000, { 5, 40 } },
147    { 0x7800, { 5, 28 } },
148    { 0x7000, { 5, 44 } },
149    { 0x6800, { 5, 52 } },
150    { 0x6000, { 5, 56 } },
151    { 0x5800, { 5, 1 } },
152    { 0x5000, { 5, 61 } },
153    { 0x4800, { 5, 2 } },
154    { 0x4000, { 5, 62 } },
155    { 0x3C00, { 6, 24 } },
156    { 0x3800, { 6, 36 } },
157    { 0x3400, { 6, 3 } },
158    { 0x3000, { 6, 63 } },
159    { 0x2E00, { 7, 5 } },
160    { 0x2C00, { 7, 9 } },
161    { 0x2A00, { 7, 17 } },
162    { 0x2800, { 7, 33 } },
163    { 0x2600, { 7, 6 } },
164    { 0x2400, { 7, 10 } },
165    { 0x2200, { 7, 18 } },
166    { 0x2000, { 7, 34 } },
167    { 0x1F00, { 8, 7 } },
168    { 0x1E00, { 8, 11 } },
169    { 0x1D00, { 8, 19 } },
170    { 0x1C00, { 8, 35 } },
171    { 0x1B00, { 8, 13 } },
172    { 0x1A00, { 8, 49 } },
173    { 0x1900, { 8, 21 } },
174    { 0x1800, { 8, 41 } },
175    { 0x1700, { 8, 14 } },
176    { 0x1600, { 8, 50 } },
177    { 0x1500, { 8, 22 } },
178    { 0x1400, { 8, 42 } },
179    { 0x1300, { 8, 15 } },
180    { 0x1200, { 8, 51 } },
181    { 0x1100, { 8, 23 } },
182    { 0x1000, { 8, 43 } },
183    { 0x0F00, { 8, 25 } },
184    { 0x0E00, { 8, 37 } },
185    { 0x0D00, { 8, 26 } },
186    { 0x0C00, { 8, 38 } },
187    { 0x0B00, { 8, 29 } },
188    { 0x0A00, { 8, 45 } },
189    { 0x0900, { 8, 53 } },
190    { 0x0800, { 8, 57 } },
191    { 0x0700, { 8, 30 } },
192    { 0x0600, { 8, 46 } },
193    { 0x0500, { 8, 54 } },
194    { 0x0400, { 8, 58 } },
195    { 0x0380, { 9, 31 } },
196    { 0x0300, { 9, 47 } },
197    { 0x0280, { 9, 55 } },
198    { 0x0200, { 9, 59 } },
199    { 0x0180, { 9, 27 } },
200    { 0x0100, { 9, 39 } },
201    { 0x0080, { 9, 0 } }
202 };
203 
204 /* coding table as found in the spec annex B.5 table B-10 */
205 static const struct vl_vlc_compressed motion_code[] = {
206    { 0x0320, { 11, -16 } },
207    { 0x0360, { 11, -15 } },
208    { 0x03a0, { 11, -14 } },
209    { 0x03e0, { 11, -13 } },
210    { 0x0420, { 11, -12 } },
211    { 0x0460, { 11, -11 } },
212    { 0x04c0, { 10, -10 } },
213    { 0x0540, { 10, -9 } },
214    { 0x05c0, { 10, -8 } },
215    { 0x0700, { 8, -7 } },
216    { 0x0900, { 8, -6 } },
217    { 0x0b00, { 8, -5 } },
218    { 0x0e00, { 7, -4 } },
219    { 0x1800, { 5, -3 } },
220    { 0x3000, { 4, -2 } },
221    { 0x6000, { 3, -1 } },
222    { 0x8000, { 1, 0 } },
223    { 0x4000, { 3, 1 } },
224    { 0x2000, { 4, 2 } },
225    { 0x1000, { 5, 3 } },
226    { 0x0c00, { 7, 4 } },
227    { 0x0a00, { 8, 5 } },
228    { 0x0800, { 8, 6 } },
229    { 0x0600, { 8, 7 } },
230    { 0x0580, { 10, 8 } },
231    { 0x0500, { 10, 9 } },
232    { 0x0480, { 10, 10 } },
233    { 0x0440, { 11, 11 } },
234    { 0x0400, { 11, 12 } },
235    { 0x03c0, { 11, 13 } },
236    { 0x0380, { 11, 14 } },
237    { 0x0340, { 11, 15 } },
238    { 0x0300, { 11, 16 } }
239 };
240 
241 /* coding table as found in the spec annex B.5 table B-11 */
242 static const struct vl_vlc_compressed dmvector[] = {
243    { 0x0000, { 1, 0 } },
244    { 0x8000, { 2, 1 } },
245    { 0xc000, { 2, -1 } }
246 };
247 
248 /* coding table as found in the spec annex B.5 table B-12 */
249 static const struct vl_vlc_compressed dct_dc_size_luminance[] = {
250    { 0x8000, { 3, 0 } },
251    { 0x0000, { 2, 1 } },
252    { 0x4000, { 2, 2 } },
253    { 0xA000, { 3, 3 } },
254    { 0xC000, { 3, 4 } },
255    { 0xE000, { 4, 5 } },
256    { 0xF000, { 5, 6 } },
257    { 0xF800, { 6, 7 } },
258    { 0xFC00, { 7, 8 } },
259    { 0xFE00, { 8, 9 } },
260    { 0xFF00, { 9, 10 } },
261    { 0xFF80, { 9, 11 } }
262 };
263 
264 /* coding table as found in the spec annex B.5 table B-13 */
265 static const struct vl_vlc_compressed dct_dc_size_chrominance[] = {
266    { 0x0000, { 2, 0 } },
267    { 0x4000, { 2, 1 } },
268    { 0x8000, { 2, 2 } },
269    { 0xC000, { 3, 3 } },
270    { 0xE000, { 4, 4 } },
271    { 0xF000, { 5, 5 } },
272    { 0xF800, { 6, 6 } },
273    { 0xFC00, { 7, 7 } },
274    { 0xFE00, { 8, 8 } },
275    { 0xFF00, { 9, 9 } },
276    { 0xFF80, { 10, 10 } },
277    { 0xFFC0, { 10, 11 } }
278 };
279 
280 /* coding table as found in the spec annex B.5 table B-14 */
281 static const struct dct_coeff_compressed dct_coeff_tbl_zero[] = {
282    { 0x8000, { 2, dct_End_of_Block, 0 } },
283    { 0x8000, { 1, dct_DC, 1 } },
284    { 0xC000, { 2, dct_AC, 1 } },
285    { 0x6000, { 3, 1, 1 } },
286    { 0x4000, { 4, 0, 2 } },
287    { 0x5000, { 4, 2, 1 } },
288    { 0x2800, { 5, 0, 3 } },
289    { 0x3800, { 5, 3, 1 } },
290    { 0x3000, { 5, 4, 1 } },
291    { 0x1800, { 6, 1, 2 } },
292    { 0x1C00, { 6, 5, 1 } },
293    { 0x1400, { 6, 6, 1 } },
294    { 0x1000, { 6, 7, 1 } },
295    { 0x0C00, { 7, 0, 4 } },
296    { 0x0800, { 7, 2, 2 } },
297    { 0x0E00, { 7, 8, 1 } },
298    { 0x0A00, { 7, 9, 1 } },
299    { 0x0400, { 6, dct_Escape, 0 } },
300    { 0x2600, { 8, 0, 5 } },
301    { 0x2100, { 8, 0, 6 } },
302    { 0x2500, { 8, 1, 3 } },
303    { 0x2400, { 8, 3, 2 } },
304    { 0x2700, { 8, 10, 1 } },
305    { 0x2300, { 8, 11, 1 } },
306    { 0x2200, { 8, 12, 1 } },
307    { 0x2000, { 8, 13, 1 } },
308    { 0x0280, { 10, 0, 7 } },
309    { 0x0300, { 10, 1, 4 } },
310    { 0x02C0, { 10, 2, 3 } },
311    { 0x03C0, { 10, 4, 2 } },
312    { 0x0240, { 10, 5, 2 } },
313    { 0x0380, { 10, 14, 1 } },
314    { 0x0340, { 10, 15, 1 } },
315    { 0x0200, { 10, 16, 1 } },
316    { 0x01D0, { 12, 0, 8 } },
317    { 0x0180, { 12, 0, 9 } },
318    { 0x0130, { 12, 0, 10 } },
319    { 0x0100, { 12, 0, 11 } },
320    { 0x01B0, { 12, 1, 5 } },
321    { 0x0140, { 12, 2, 4 } },
322    { 0x01C0, { 12, 3, 3 } },
323    { 0x0120, { 12, 4, 3 } },
324    { 0x01E0, { 12, 6, 2 } },
325    { 0x0150, { 12, 7, 2 } },
326    { 0x0110, { 12, 8, 2 } },
327    { 0x01F0, { 12, 17, 1 } },
328    { 0x01A0, { 12, 18, 1 } },
329    { 0x0190, { 12, 19, 1 } },
330    { 0x0170, { 12, 20, 1 } },
331    { 0x0160, { 12, 21, 1 } },
332    { 0x00D0, { 13, 0, 12 } },
333    { 0x00C8, { 13, 0, 13 } },
334    { 0x00C0, { 13, 0, 14 } },
335    { 0x00B8, { 13, 0, 15 } },
336    { 0x00B0, { 13, 1, 6 } },
337    { 0x00A8, { 13, 1, 7 } },
338    { 0x00A0, { 13, 2, 5 } },
339    { 0x0098, { 13, 3, 4 } },
340    { 0x0090, { 13, 5, 3 } },
341    { 0x0088, { 13, 9, 2 } },
342    { 0x0080, { 13, 10, 2 } },
343    { 0x00F8, { 13, 22, 1 } },
344    { 0x00F0, { 13, 23, 1 } },
345    { 0x00E8, { 13, 24, 1 } },
346    { 0x00E0, { 13, 25, 1 } },
347    { 0x00D8, { 13, 26, 1 } },
348    { 0x007C, { 14, 0, 16 } },
349    { 0x0078, { 14, 0, 17 } },
350    { 0x0074, { 14, 0, 18 } },
351    { 0x0070, { 14, 0, 19 } },
352    { 0x006C, { 14, 0, 20 } },
353    { 0x0068, { 14, 0, 21 } },
354    { 0x0064, { 14, 0, 22 } },
355    { 0x0060, { 14, 0, 23 } },
356    { 0x005C, { 14, 0, 24 } },
357    { 0x0058, { 14, 0, 25 } },
358    { 0x0054, { 14, 0, 26 } },
359    { 0x0050, { 14, 0, 27 } },
360    { 0x004C, { 14, 0, 28 } },
361    { 0x0048, { 14, 0, 29 } },
362    { 0x0044, { 14, 0, 30 } },
363    { 0x0040, { 14, 0, 31 } },
364    { 0x0030, { 15, 0, 32 } },
365    { 0x002E, { 15, 0, 33 } },
366    { 0x002C, { 15, 0, 34 } },
367    { 0x002A, { 15, 0, 35 } },
368    { 0x0028, { 15, 0, 36 } },
369    { 0x0026, { 15, 0, 37 } },
370    { 0x0024, { 15, 0, 38 } },
371    { 0x0022, { 15, 0, 39 } },
372    { 0x0020, { 15, 0, 40 } },
373    { 0x003E, { 15, 1, 8 } },
374    { 0x003C, { 15, 1, 9 } },
375    { 0x003A, { 15, 1, 10 } },
376    { 0x0038, { 15, 1, 11 } },
377    { 0x0036, { 15, 1, 12 } },
378    { 0x0034, { 15, 1, 13 } },
379    { 0x0032, { 15, 1, 14 } },
380    { 0x0013, { 16, 1, 15 } },
381    { 0x0012, { 16, 1, 16 } },
382    { 0x0011, { 16, 1, 17 } },
383    { 0x0010, { 16, 1, 18 } },
384    { 0x0014, { 16, 6, 3 } },
385    { 0x001A, { 16, 11, 2 } },
386    { 0x0019, { 16, 12, 2 } },
387    { 0x0018, { 16, 13, 2 } },
388    { 0x0017, { 16, 14, 2 } },
389    { 0x0016, { 16, 15, 2 } },
390    { 0x0015, { 16, 16, 2 } },
391    { 0x001F, { 16, 27, 1 } },
392    { 0x001E, { 16, 28, 1 } },
393    { 0x001D, { 16, 29, 1 } },
394    { 0x001C, { 16, 30, 1 } },
395    { 0x001B, { 16, 31, 1 } }
396 };
397 
398 /* coding table as found in the spec annex B.5 table B-15 */
399 static const struct dct_coeff_compressed dct_coeff_tbl_one[] = {
400    { 0x6000, { 4, dct_End_of_Block, 0 } },
401    { 0x8000, { 2, 0, 1 } },
402    { 0x4000, { 3, 1, 1 } },
403    { 0xC000, { 3, 0, 2 } },
404    { 0x2800, { 5, 2, 1 } },
405    { 0x7000, { 4, 0, 3 } },
406    { 0x3800, { 5, 3, 1 } },
407    { 0x1800, { 6, 4, 1 } },
408    { 0x3000, { 5, 1, 2 } },
409    { 0x1C00, { 6, 5, 1 } },
410    { 0x0C00, { 7, 6, 1 } },
411    { 0x0800, { 7, 7, 1 } },
412    { 0xE000, { 5, 0, 4 } },
413    { 0x0E00, { 7, 2, 2 } },
414    { 0x0A00, { 7, 8, 1 } },
415    { 0xF000, { 7, 9, 1 } },
416    { 0x0400, { 6, dct_Escape, 0 } },
417    { 0xE800, { 5, 0, 5 } },
418    { 0x1400, { 6, 0, 6 } },
419    { 0xF200, { 7, 1, 3 } },
420    { 0x2600, { 8, 3, 2 } },
421    { 0xF400, { 7, 10, 1 } },
422    { 0x2100, { 8, 11, 1 } },
423    { 0x2500, { 8, 12, 1 } },
424    { 0x2400, { 8, 13, 1 } },
425    { 0x1000, { 6, 0, 7 } },
426    { 0x2700, { 8, 1, 4 } },
427    { 0xFC00, { 8, 2, 3 } },
428    { 0xFD00, { 8, 4, 2 } },
429    { 0x0200, { 9, 5, 2 } },
430    { 0x0280, { 9, 14, 1 } },
431    { 0x0380, { 9, 15, 1 } },
432    { 0x0340, { 10, 16, 1 } },
433    { 0xF600, { 7, 0, 8 } },
434    { 0xF800, { 7, 0, 9 } },
435    { 0x2300, { 8, 0, 10 } },
436    { 0x2200, { 8, 0, 11 } },
437    { 0x2000, { 8, 1, 5 } },
438    { 0x0300, { 10, 2, 4 } },
439    { 0x01C0, { 12, 3, 3 } },
440    { 0x0120, { 12, 4, 3 } },
441    { 0x01E0, { 12, 6, 2 } },
442    { 0x0150, { 12, 7, 2 } },
443    { 0x0110, { 12, 8, 2 } },
444    { 0x01F0, { 12, 17, 1 } },
445    { 0x01A0, { 12, 18, 1 } },
446    { 0x0190, { 12, 19, 1 } },
447    { 0x0170, { 12, 20, 1 } },
448    { 0x0160, { 12, 21, 1 } },
449    { 0xFA00, { 8, 0, 12 } },
450    { 0xFB00, { 8, 0, 13 } },
451    { 0xFE00, { 8, 0, 14 } },
452    { 0xFF00, { 8, 0, 15 } },
453    { 0x00B0, { 13, 1, 6 } },
454    { 0x00A8, { 13, 1, 7 } },
455    { 0x00A0, { 13, 2, 5 } },
456    { 0x0098, { 13, 3, 4 } },
457    { 0x0090, { 13, 5, 3 } },
458    { 0x0088, { 13, 9, 2 } },
459    { 0x0080, { 13, 10, 2 } },
460    { 0x00F8, { 13, 22, 1 } },
461    { 0x00F0, { 13, 23, 1 } },
462    { 0x00E8, { 13, 24, 1 } },
463    { 0x00E0, { 13, 25, 1 } },
464    { 0x00D8, { 13, 26, 1 } },
465    { 0x007C, { 14, 0, 16 } },
466    { 0x0078, { 14, 0, 17 } },
467    { 0x0074, { 14, 0, 18 } },
468    { 0x0070, { 14, 0, 19 } },
469    { 0x006C, { 14, 0, 20 } },
470    { 0x0068, { 14, 0, 21 } },
471    { 0x0064, { 14, 0, 22 } },
472    { 0x0060, { 14, 0, 23 } },
473    { 0x005C, { 14, 0, 24 } },
474    { 0x0058, { 14, 0, 25 } },
475    { 0x0054, { 14, 0, 26 } },
476    { 0x0050, { 14, 0, 27 } },
477    { 0x004C, { 14, 0, 28 } },
478    { 0x0048, { 14, 0, 29 } },
479    { 0x0044, { 14, 0, 30 } },
480    { 0x0040, { 14, 0, 31 } },
481    { 0x0030, { 15, 0, 32 } },
482    { 0x002E, { 15, 0, 33 } },
483    { 0x002C, { 15, 0, 34 } },
484    { 0x002A, { 15, 0, 35 } },
485    { 0x0028, { 15, 0, 36 } },
486    { 0x0026, { 15, 0, 37 } },
487    { 0x0024, { 15, 0, 38 } },
488    { 0x0022, { 15, 0, 39 } },
489    { 0x0020, { 15, 0, 40 } },
490    { 0x003E, { 15, 1, 8 } },
491    { 0x003C, { 15, 1, 9 } },
492    { 0x003A, { 15, 1, 10 } },
493    { 0x0038, { 15, 1, 11 } },
494    { 0x0036, { 15, 1, 12 } },
495    { 0x0034, { 15, 1, 13 } },
496    { 0x0032, { 15, 1, 14 } },
497    { 0x0013, { 16, 1, 15 } },
498    { 0x0012, { 16, 1, 16 } },
499    { 0x0011, { 16, 1, 17 } },
500    { 0x0010, { 16, 1, 18 } },
501    { 0x0014, { 16, 6, 3 } },
502    { 0x001A, { 16, 11, 2 } },
503    { 0x0019, { 16, 12, 2 } },
504    { 0x0018, { 16, 13, 2 } },
505    { 0x0017, { 16, 14, 2 } },
506    { 0x0016, { 16, 15, 2 } },
507    { 0x0015, { 16, 16, 2 } },
508    { 0x001F, { 16, 27, 1 } },
509    { 0x001E, { 16, 28, 1 } },
510    { 0x001D, { 16, 29, 1 } },
511    { 0x001C, { 16, 30, 1 } },
512    { 0x001B, { 16, 31, 1 } }
513 };
514 
515 /* q_scale_type */
516 static const unsigned quant_scale[2][32] = {
517   { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30,
518     32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62 },
519   { 0, 1, 2, 3, 4,  5,  6,  7,  8, 10, 12, 14, 16, 18, 20, 22, 24,
520     28, 32, 36, 40, 44, 48, 52, 56, 64, 72, 80, 88, 96, 104, 112 }
521 };
522 
523 static struct vl_vlc_entry tbl_B1[1 << 11];
524 static struct vl_vlc_entry tbl_B2[1 << 2];
525 static struct vl_vlc_entry tbl_B3[1 << 6];
526 static struct vl_vlc_entry tbl_B4[1 << 6];
527 static struct vl_vlc_entry tbl_B9[1 << 9];
528 static struct vl_vlc_entry tbl_B10[1 << 11];
529 static struct vl_vlc_entry tbl_B11[1 << 2];
530 static struct vl_vlc_entry tbl_B12[1 << 10];
531 static struct vl_vlc_entry tbl_B13[1 << 10];
532 static struct dct_coeff tbl_B14_DC[1 << 17];
533 static struct dct_coeff tbl_B14_AC[1 << 17];
534 static struct dct_coeff tbl_B15[1 << 17];
535 
536 static inline void
init_dct_coeff_table(struct dct_coeff * dst,const struct dct_coeff_compressed * src,unsigned size,bool is_DC)537 init_dct_coeff_table(struct dct_coeff *dst, const struct dct_coeff_compressed *src,
538                      unsigned size, bool is_DC)
539 {
540    unsigned i;
541 
542    for (i=0;i<(1<<17);++i) {
543       dst[i].length = 0;
544       dst[i].level = 0;
545       dst[i].run = dct_End_of_Block;
546    }
547 
548    for(; size > 0; --size, ++src) {
549       struct dct_coeff coeff = src->coeff;
550       bool has_sign = true;
551 
552       switch (coeff.run) {
553       case dct_End_of_Block:
554          if (is_DC)
555             continue;
556 
557          has_sign = false;
558          break;
559 
560       case dct_Escape:
561          has_sign = false;
562          break;
563 
564       case dct_DC:
565          if (!is_DC)
566             continue;
567 
568          coeff.length += 1;
569          coeff.run = 1;
570          break;
571 
572       case dct_AC:
573          if (is_DC)
574             continue;
575 
576          coeff.length += 1;
577          coeff.run = 1;
578          break;
579 
580       default:
581          coeff.length += 1;
582          coeff.run += 1;
583          break;
584       }
585 
586       for(i = 0; i < (1u << (17 - coeff.length)); ++i)
587          dst[src->bitcode << 1 | i] = coeff;
588 
589       if (has_sign) {
590 	 coeff.level = -coeff.level;
591          for(; i < (1u << (18 - coeff.length)); ++i)
592             dst[src->bitcode << 1 | i] = coeff;
593       }
594    }
595 }
596 
597 static inline void
init_tables()598 init_tables()
599 {
600    vl_vlc_init_table(tbl_B1, ARRAY_SIZE(tbl_B1), macroblock_address_increment, ARRAY_SIZE(macroblock_address_increment));
601    vl_vlc_init_table(tbl_B2, ARRAY_SIZE(tbl_B2), macroblock_type_i, ARRAY_SIZE(macroblock_type_i));
602    vl_vlc_init_table(tbl_B3, ARRAY_SIZE(tbl_B3), macroblock_type_p, ARRAY_SIZE(macroblock_type_p));
603    vl_vlc_init_table(tbl_B4, ARRAY_SIZE(tbl_B4), macroblock_type_b, ARRAY_SIZE(macroblock_type_b));
604    vl_vlc_init_table(tbl_B9, ARRAY_SIZE(tbl_B9), coded_block_pattern, ARRAY_SIZE(coded_block_pattern));
605    vl_vlc_init_table(tbl_B10, ARRAY_SIZE(tbl_B10), motion_code, ARRAY_SIZE(motion_code));
606    vl_vlc_init_table(tbl_B11, ARRAY_SIZE(tbl_B11), dmvector, ARRAY_SIZE(dmvector));
607    vl_vlc_init_table(tbl_B12, ARRAY_SIZE(tbl_B12), dct_dc_size_luminance, ARRAY_SIZE(dct_dc_size_luminance));
608    vl_vlc_init_table(tbl_B13, ARRAY_SIZE(tbl_B13), dct_dc_size_chrominance, ARRAY_SIZE(dct_dc_size_chrominance));
609    init_dct_coeff_table(tbl_B14_DC, dct_coeff_tbl_zero, ARRAY_SIZE(dct_coeff_tbl_zero), true);
610    init_dct_coeff_table(tbl_B14_AC, dct_coeff_tbl_zero, ARRAY_SIZE(dct_coeff_tbl_zero), false);
611    init_dct_coeff_table(tbl_B15, dct_coeff_tbl_one, ARRAY_SIZE(dct_coeff_tbl_one), false);
612 }
613 
614 static inline int
DIV2DOWN(int todiv)615 DIV2DOWN(int todiv)
616 {
617    return (todiv&~1)/2;
618 }
619 
620 static inline void
motion_vector(struct vl_mpg12_bs * bs,int r,int s,int dmv,short delta[2],short dmvector[2])621 motion_vector(struct vl_mpg12_bs *bs, int r, int s, int dmv, short delta[2], short dmvector[2])
622 {
623    int t;
624    for (t = 0; t < 2; ++t) {
625       int motion_code;
626       int r_size = bs->desc->f_code[s][t];
627 
628       vl_vlc_fillbits(&bs->vlc);
629       motion_code = vl_vlc_get_vlclbf(&bs->vlc, tbl_B10, 11);
630 
631       assert(r_size >= 0);
632       if (r_size && motion_code) {
633          int residual = vl_vlc_get_uimsbf(&bs->vlc, r_size) + 1;
634          delta[t] = ((abs(motion_code) - 1) << r_size) + residual;
635          if (motion_code < 0)
636             delta[t] = -delta[t];
637       } else
638          delta[t] = motion_code;
639       if (dmv)
640          dmvector[t] = vl_vlc_get_vlclbf(&bs->vlc, tbl_B11, 2);
641    }
642 }
643 
644 static inline int
wrap(short f,int shift)645 wrap(short f, int shift)
646 {
647    if (f < (-16 << shift))
648       return f + (32 << shift);
649    else if (f >= 16 << shift)
650       return f - (32 << shift);
651    else
652       return f;
653 }
654 
655 static inline void
motion_vector_frame(struct vl_mpg12_bs * bs,int s,struct pipe_mpeg12_macroblock * mb)656 motion_vector_frame(struct vl_mpg12_bs *bs, int s, struct pipe_mpeg12_macroblock *mb)
657 {
658    int dmv = mb->macroblock_modes.bits.frame_motion_type == PIPE_MPEG12_MO_TYPE_DUAL_PRIME;
659    short dmvector[2], delta[2];
660 
661    if (mb->macroblock_modes.bits.frame_motion_type == PIPE_MPEG12_MO_TYPE_FIELD) {
662       mb->motion_vertical_field_select |= vl_vlc_get_uimsbf(&bs->vlc, 1) << s;
663       motion_vector(bs, 0, s, dmv, delta, dmvector);
664       mb->PMV[0][s][0] = wrap(mb->PMV[0][s][0] + delta[0], bs->desc->f_code[s][0]);
665       mb->PMV[0][s][1] = wrap(DIV2DOWN(mb->PMV[0][s][1]) + delta[1], bs->desc->f_code[s][1]) * 2;
666 
667       mb->motion_vertical_field_select |= vl_vlc_get_uimsbf(&bs->vlc, 1) << (s + 2);
668       motion_vector(bs, 1, s, dmv, delta, dmvector);
669       mb->PMV[1][s][0] = wrap(mb->PMV[1][s][0] + delta[0], bs->desc->f_code[s][0]);
670       mb->PMV[1][s][1] = wrap(DIV2DOWN(mb->PMV[1][s][1]) + delta[1], bs->desc->f_code[s][1]) * 2;
671 
672    } else {
673       motion_vector(bs, 0, s, dmv, delta, dmvector);
674       mb->PMV[0][s][0] = wrap(mb->PMV[0][s][0] + delta[0], bs->desc->f_code[s][0]);
675       mb->PMV[0][s][1] = wrap(mb->PMV[0][s][1] + delta[1], bs->desc->f_code[s][1]);
676    }
677 }
678 
679 static inline void
motion_vector_field(struct vl_mpg12_bs * bs,int s,struct pipe_mpeg12_macroblock * mb)680 motion_vector_field(struct vl_mpg12_bs *bs, int s, struct pipe_mpeg12_macroblock *mb)
681 {
682    int dmv = mb->macroblock_modes.bits.field_motion_type == PIPE_MPEG12_MO_TYPE_DUAL_PRIME;
683    short dmvector[2], delta[2];
684 
685    if (mb->macroblock_modes.bits.field_motion_type == PIPE_MPEG12_MO_TYPE_16x8) {
686       mb->motion_vertical_field_select |= vl_vlc_get_uimsbf(&bs->vlc, 1) << s;
687       motion_vector(bs, 0, s, dmv, delta, dmvector);
688 
689       mb->motion_vertical_field_select |= vl_vlc_get_uimsbf(&bs->vlc, 1) << (s + 2);
690       motion_vector(bs, 1, s, dmv, delta, dmvector);
691    } else {
692       if (!dmv)
693          mb->motion_vertical_field_select |= vl_vlc_get_uimsbf(&bs->vlc, 1) << s;
694       motion_vector(bs, 0, s, dmv, delta, dmvector);
695    }
696 }
697 
698 static inline void
reset_predictor(struct vl_mpg12_bs * bs)699 reset_predictor(struct vl_mpg12_bs *bs) {
700    bs->pred_dc[0] = bs->pred_dc[1] = bs->pred_dc[2] = 0;
701 }
702 
703 static inline void
decode_dct(struct vl_mpg12_bs * bs,struct pipe_mpeg12_macroblock * mb,int scale)704 decode_dct(struct vl_mpg12_bs *bs, struct pipe_mpeg12_macroblock *mb, int scale)
705 {
706    static const unsigned blk2cc[] = { 0, 0, 0, 0, 1, 2 };
707    static const struct vl_vlc_entry *blk2dcsize[] = {
708       tbl_B12, tbl_B12, tbl_B12, tbl_B12, tbl_B13, tbl_B13
709    };
710 
711    bool intra = mb->macroblock_type & PIPE_MPEG12_MB_TYPE_INTRA;
712    const struct dct_coeff *table = intra ? bs->intra_dct_tbl : tbl_B14_AC;
713    const struct dct_coeff *entry;
714    int i, cbp, blk = 0;
715    short *dst = mb->blocks;
716 
717    vl_vlc_fillbits(&bs->vlc);
718    mb->coded_block_pattern = cbp = intra ? 0x3F : vl_vlc_get_vlclbf(&bs->vlc, tbl_B9, 9);
719 
720    goto entry;
721 
722    while(1) {
723       vl_vlc_eatbits(&bs->vlc, entry->length);
724       if (entry->run == dct_End_of_Block) {
725 
726 next_d:
727          dst += 64;
728          cbp <<= 1;
729          cbp &= 0x3F;
730          blk++;
731 
732 entry:
733          if (!cbp)
734             break;
735 
736          while(!(cbp & 0x20)) {
737             cbp <<= 1;
738             blk++;
739          }
740 
741          vl_vlc_fillbits(&bs->vlc);
742 
743          if (intra) {
744             unsigned cc = blk2cc[blk];
745             unsigned size = vl_vlc_get_vlclbf(&bs->vlc, blk2dcsize[blk], 10);
746 
747             if (size) {
748                int dct_diff = vl_vlc_get_uimsbf(&bs->vlc, size);
749                int half_range = 1 << (size - 1);
750                if (dct_diff < half_range)
751                   dct_diff = (dct_diff + 1) - (2 * half_range);
752                bs->pred_dc[cc] += dct_diff;
753             }
754 
755             dst[0] = bs->pred_dc[cc];
756             i = 0;
757 
758             if (bs->desc->picture_coding_type == PIPE_MPEG12_PICTURE_CODING_TYPE_D)
759                goto next_d;
760          } else {
761             entry = tbl_B14_DC + vl_vlc_peekbits(&bs->vlc, 17);
762             i = -1;
763             continue;
764          }
765 
766       } else if (entry->run == dct_Escape &&
767                  bs->decoder->profile == PIPE_VIDEO_PROFILE_MPEG1) {
768          i += vl_vlc_get_uimsbf(&bs->vlc, 6) + 1;
769          if (i > 64)
770             break;
771 
772          dst[i] = vl_vlc_get_simsbf(&bs->vlc, 8);
773          if (dst[i] == -128)
774             dst[i] = vl_vlc_get_uimsbf(&bs->vlc, 8) - 256;
775          else if (dst[i] == 0)
776             dst[i] = vl_vlc_get_uimsbf(&bs->vlc, 8);
777 
778          dst[i] *= scale;
779       } else if (entry->run == dct_Escape) {
780          i += vl_vlc_get_uimsbf(&bs->vlc, 6) + 1;
781          if (i > 64)
782             break;
783 
784          dst[i] = vl_vlc_get_simsbf(&bs->vlc, 12) * scale;
785 
786       } else {
787          i += entry->run;
788          if (i > 64)
789             break;
790 
791          dst[i] = entry->level * scale;
792       }
793 
794       vl_vlc_fillbits(&bs->vlc);
795       entry = table + vl_vlc_peekbits(&bs->vlc, 17);
796    }
797 
798    if (bs->desc->picture_coding_type == PIPE_MPEG12_PICTURE_CODING_TYPE_D)
799       vl_vlc_eatbits(&bs->vlc, 1);
800 }
801 
802 static inline void
decode_slice(struct vl_mpg12_bs * bs,struct pipe_video_buffer * target)803 decode_slice(struct vl_mpg12_bs *bs, struct pipe_video_buffer *target)
804 {
805    struct pipe_mpeg12_macroblock mb;
806    short dct_blocks[64*6];
807    unsigned dct_scale;
808    signed x = -1;
809 
810    memset(&mb, 0, sizeof(mb));
811    mb.base.codec = PIPE_VIDEO_FORMAT_MPEG12;
812    mb.y = vl_vlc_get_uimsbf(&bs->vlc, 8) - 1;
813    mb.blocks = dct_blocks;
814 
815    reset_predictor(bs);
816    vl_vlc_fillbits(&bs->vlc);
817    dct_scale = quant_scale[bs->desc->q_scale_type][vl_vlc_get_uimsbf(&bs->vlc, 5)];
818 
819    if (vl_vlc_get_uimsbf(&bs->vlc, 1))
820       while (vl_vlc_get_uimsbf(&bs->vlc, 9) & 1)
821          vl_vlc_fillbits(&bs->vlc);
822 
823    vl_vlc_fillbits(&bs->vlc);
824    assert(vl_vlc_peekbits(&bs->vlc, 23));
825    do {
826       int inc = 0;
827 
828       while (1) {
829          /* MPEG-1 macroblock stuffing, can appear an arbitrary number of times. */
830          while (vl_vlc_peekbits(&bs->vlc, 11) == 15) {
831             vl_vlc_eatbits(&bs->vlc, 11);
832             vl_vlc_fillbits(&bs->vlc);
833          }
834 
835          if (vl_vlc_peekbits(&bs->vlc, 11) == 8) {
836             vl_vlc_eatbits(&bs->vlc, 11);
837             vl_vlc_fillbits(&bs->vlc);
838             inc += 33;
839          } else {
840             inc += vl_vlc_get_vlclbf(&bs->vlc, tbl_B1, 11);
841             break;
842          }
843       }
844 
845       if (x != -1) {
846          if (!inc)
847             return;
848          mb.num_skipped_macroblocks = inc - 1;
849          bs->decoder->decode_macroblock(bs->decoder, target, &bs->desc->base, &mb.base, 1);
850       }
851       mb.x = x += inc;
852       if (bs->decoder->profile == PIPE_VIDEO_PROFILE_MPEG1) {
853          int width = align(bs->decoder->width, 16) / 16;
854          mb.y += mb.x / width;
855          mb.x = x %= width;
856       }
857 
858       switch (bs->desc->picture_coding_type) {
859       case PIPE_MPEG12_PICTURE_CODING_TYPE_I:
860          mb.macroblock_type = vl_vlc_get_vlclbf(&bs->vlc, tbl_B2, 2);
861          break;
862 
863       case PIPE_MPEG12_PICTURE_CODING_TYPE_P:
864          mb.macroblock_type = vl_vlc_get_vlclbf(&bs->vlc, tbl_B3, 6);
865          break;
866 
867       case PIPE_MPEG12_PICTURE_CODING_TYPE_B:
868          mb.macroblock_type = vl_vlc_get_vlclbf(&bs->vlc, tbl_B4, 6);
869          break;
870 
871       case PIPE_MPEG12_PICTURE_CODING_TYPE_D:
872          vl_vlc_eatbits(&bs->vlc, 1);
873          mb.macroblock_type = PIPE_MPEG12_MB_TYPE_INTRA;
874          break;
875       }
876 
877       mb.macroblock_modes.value = 0;
878       if (mb.macroblock_type & (PIPE_MPEG12_MB_TYPE_MOTION_FORWARD | PIPE_MPEG12_MB_TYPE_MOTION_BACKWARD)) {
879          if (bs->desc->picture_structure == PIPE_MPEG12_PICTURE_STRUCTURE_FRAME) {
880             if (bs->desc->frame_pred_frame_dct == 0)
881                mb.macroblock_modes.bits.frame_motion_type = vl_vlc_get_uimsbf(&bs->vlc, 2);
882             else
883                mb.macroblock_modes.bits.frame_motion_type = 2;
884          } else
885             mb.macroblock_modes.bits.field_motion_type = vl_vlc_get_uimsbf(&bs->vlc, 2);
886 
887       } else if ((mb.macroblock_type & PIPE_MPEG12_MB_TYPE_INTRA) && bs->desc->concealment_motion_vectors) {
888          if (bs->desc->picture_structure == PIPE_MPEG12_PICTURE_STRUCTURE_FRAME)
889             mb.macroblock_modes.bits.frame_motion_type = 2;
890          else
891             mb.macroblock_modes.bits.field_motion_type = 1;
892       }
893 
894       if (bs->desc->picture_structure == PIPE_MPEG12_PICTURE_STRUCTURE_FRAME &&
895           bs->desc->frame_pred_frame_dct == 0 &&
896           mb.macroblock_type & (PIPE_MPEG12_MB_TYPE_INTRA | PIPE_MPEG12_MB_TYPE_PATTERN))
897          mb.macroblock_modes.bits.dct_type = vl_vlc_get_uimsbf(&bs->vlc, 1);
898 
899       if (mb.macroblock_type & PIPE_MPEG12_MB_TYPE_QUANT)
900          dct_scale = quant_scale[bs->desc->q_scale_type][vl_vlc_get_uimsbf(&bs->vlc, 5)];
901 
902       if (inc > 1 && bs->desc->picture_coding_type == PIPE_MPEG12_PICTURE_CODING_TYPE_P)
903          memset(mb.PMV, 0, sizeof(mb.PMV));
904 
905       mb.motion_vertical_field_select = 0;
906       if ((mb.macroblock_type & PIPE_MPEG12_MB_TYPE_MOTION_FORWARD) ||
907           (mb.macroblock_type & PIPE_MPEG12_MB_TYPE_INTRA && bs->desc->concealment_motion_vectors)) {
908          if (bs->desc->picture_structure == PIPE_MPEG12_PICTURE_STRUCTURE_FRAME)
909             motion_vector_frame(bs, 0, &mb);
910          else
911             motion_vector_field(bs, 0, &mb);
912       }
913 
914       if (mb.macroblock_type & PIPE_MPEG12_MB_TYPE_MOTION_BACKWARD) {
915          if (bs->desc->picture_structure == PIPE_MPEG12_PICTURE_STRUCTURE_FRAME)
916             motion_vector_frame(bs, 1, &mb);
917          else
918             motion_vector_field(bs, 1, &mb);
919       }
920 
921       if (mb.macroblock_type & PIPE_MPEG12_MB_TYPE_INTRA && bs->desc->concealment_motion_vectors) {
922          unsigned extra = vl_vlc_get_uimsbf(&bs->vlc, 1);
923          mb.PMV[1][0][0] = mb.PMV[0][0][0];
924          mb.PMV[1][0][1] = mb.PMV[0][0][1];
925          assert(extra);
926          (void) extra;
927       } else if (mb.macroblock_type & PIPE_MPEG12_MB_TYPE_INTRA ||
928                 !(mb.macroblock_type & (PIPE_MPEG12_MB_TYPE_MOTION_FORWARD |
929                                         PIPE_MPEG12_MB_TYPE_MOTION_BACKWARD))) {
930          memset(mb.PMV, 0, sizeof(mb.PMV));
931       }
932 
933       if ((mb.macroblock_type & PIPE_MPEG12_MB_TYPE_MOTION_FORWARD &&
934            mb.macroblock_modes.bits.frame_motion_type == 2) ||
935           (mb.macroblock_modes.bits.frame_motion_type == 3)) {
936             mb.PMV[1][0][0] = mb.PMV[0][0][0];
937             mb.PMV[1][0][1] = mb.PMV[0][0][1];
938       }
939 
940       if (mb.macroblock_type & PIPE_MPEG12_MB_TYPE_MOTION_BACKWARD &&
941           mb.macroblock_modes.bits.frame_motion_type == 2) {
942             mb.PMV[1][1][0] = mb.PMV[0][1][0];
943             mb.PMV[1][1][1] = mb.PMV[0][1][1];
944       }
945 
946       if (inc > 1 || !(mb.macroblock_type & PIPE_MPEG12_MB_TYPE_INTRA))
947          reset_predictor(bs);
948 
949       if (mb.macroblock_type & (PIPE_MPEG12_MB_TYPE_INTRA | PIPE_MPEG12_MB_TYPE_PATTERN)) {
950          memset(dct_blocks, 0, sizeof(dct_blocks));
951          decode_dct(bs, &mb, dct_scale);
952       } else
953          mb.coded_block_pattern = 0;
954 
955       vl_vlc_fillbits(&bs->vlc);
956    } while (vl_vlc_bits_left(&bs->vlc) && vl_vlc_peekbits(&bs->vlc, 23));
957 
958    mb.num_skipped_macroblocks = 0;
959    bs->decoder->decode_macroblock(bs->decoder, target, &bs->desc->base, &mb.base, 1);
960 }
961 
962 void
vl_mpg12_bs_init(struct vl_mpg12_bs * bs,struct pipe_video_codec * decoder)963 vl_mpg12_bs_init(struct vl_mpg12_bs *bs, struct pipe_video_codec *decoder)
964 {
965    static bool tables_initialized = false;
966 
967    assert(bs);
968 
969    memset(bs, 0, sizeof(struct vl_mpg12_bs));
970 
971    bs->decoder = decoder;
972 
973    if (!tables_initialized) {
974       init_tables();
975       tables_initialized = true;
976    }
977 }
978 
979 void
vl_mpg12_bs_decode(struct vl_mpg12_bs * bs,struct pipe_video_buffer * target,struct pipe_mpeg12_picture_desc * picture,unsigned num_buffers,const void * const * buffers,const unsigned * sizes)980 vl_mpg12_bs_decode(struct vl_mpg12_bs *bs,
981                    struct pipe_video_buffer *target,
982                    struct pipe_mpeg12_picture_desc *picture,
983                    unsigned num_buffers,
984                    const void * const *buffers,
985                    const unsigned *sizes)
986 {
987    assert(bs);
988 
989    bs->desc = picture;
990    bs->intra_dct_tbl = picture->intra_vlc_format ? tbl_B15 : tbl_B14_AC;
991 
992    vl_vlc_init(&bs->vlc, num_buffers, buffers, sizes);
993    while (vl_vlc_search_byte(&bs->vlc, ~0, 0x00) && vl_vlc_bits_left(&bs->vlc) > 32) {
994       uint32_t code = vl_vlc_peekbits(&bs->vlc, 32);
995 
996       if (code >= 0x101 && code <= 0x1AF) {
997          vl_vlc_eatbits(&bs->vlc, 24);
998          decode_slice(bs, target);
999 
1000          /* align to a byte again */
1001          vl_vlc_eatbits(&bs->vlc, vl_vlc_valid_bits(&bs->vlc) & 7);
1002 
1003       } else {
1004          vl_vlc_eatbits(&bs->vlc, 8);
1005       }
1006 
1007       vl_vlc_fillbits(&bs->vlc);
1008    }
1009 }
1010