1 /*
2 * jpeg-hash.cc --
3 *
4 * FIXME: This file needs a description here.
5 */
6
7 /*
8 * This code is derived from the Independent JPEG Group's JPEG software:
9 *
10 * Copyright (C) 1991, 1992, Thomas G. Lane.
11 * This file is part of the Independent JPEG Group's software.
12 * For conditions of distribution and use, see the accompanying
13 * README.IJPG file.
14 */
15
16 #include "jpeg.h"
17 #include "endian.h"
18
19 #include <stdlib.h>
20 #include <stdio.h>
21 #include <sys/param.h>
22 #include <netinet/in.h>
23
24 extern "C" {
25 void j_rev_dct_c(short*, u_char*);
26 void j_rev_dct(short*);
27 void init_pre_idct();
28 }
29
30 #if defined(__osf__) || defined(sgi)
31 #include <string.h>
32 #ifdef sgi
33 #include <bstring.h>
34 #endif
35 #elif !defined(__svr4__)
36 #include <bstring.h>
37 #endif
38
39 #define u_word u_int
40
41 /*
42 * These two macros stolen from nv.
43 */
44 /* Sick little macro which will limit x to [0..255] with logical ops */
45 #define UCLIMIT(x) ((t = (x)), (t &= ~(t>>31)), (t | ~((t-256) >> 31)))
46 /* A variant of above which will limit x to [-128..127] */
47 #define SCLIMIT(x) (UCLIMIT((x)+128)-128)
48
49 /*
50 * ZAG[i] is the natural-order position of the i'th element of zigzag order.
51 * If the incoming data is corrupted, huff_decode_mcu could attempt to
52 * reference values beyond the end of the array. To avoid a wild store,
53 * we put some extra zeroes after the real entries.
54 */
55 static const int ZAG[] = {
56 0, 1, 8, 16, 9, 2, 3, 10,
57 17, 24, 32, 25, 18, 11, 4, 5,
58 12, 19, 26, 33, 40, 48, 41, 34,
59 27, 20, 13, 6, 7, 14, 21, 28,
60 35, 42, 49, 56, 57, 50, 43, 36,
61 29, 22, 15, 23, 30, 37, 44, 51,
62 58, 59, 52, 45, 38, 31, 39, 46,
63 53, 60, 61, 54, 47, 55, 62, 63,
64 /* extra entries in case k>63 below */
65 0, 0, 0, 0, 0, 0, 0, 0,
66 0, 0, 0, 0, 0, 0, 0, 0
67 };
68
69 class JpegDecoder_420 : public JpegDecoder {
70 public:
71 JpegDecoder_420(const config&);
72 virtual int decode(u_char* in, int len);
73 };
74
75 class JpegDecoder_422 : public JpegDecoder {
76 public:
77 JpegDecoder_422(const config&);
78 virtual int decode(u_char* in, int len);
79 };
80
81 JpegDecoder_420::JpegDecoder_420(const config& c) : JpegDecoder(c)
82 {
83 csss_ = 420;
84 }
85
86 JpegDecoder_422::JpegDecoder_422(const config& c) : JpegDecoder(c)
87 {
88 csss_ = 422;
89 }
90
91 JpegDecoder* JpegDecoder::create(const config& c)
92 {
93 if (c.ncomp == 3 && c.comp[0].hsf == 2 &&
94 c.comp[1].hsf == 1 && c.comp[1].vsf == 1 &&
95 c.comp[2].hsf == 1 && c.comp[2].vsf == 1) {
96 if (c.comp[0].vsf == 2)
97 return (new JpegDecoder_420(c));
98 if (c.comp[0].vsf == 1)
99 return (new JpegDecoder_422(c));
100 }
101 return (0);
102 }
103
104 int quality_to_qfactor(int v)
105 {
106 if (v < 1)
107 v = 5000;
108 else if (v < 50)
109 v = 5000 / v;
110 else if (v < 100)
111 v = 200 - v * 2;
112 else
113 v = 1;
114
115 return (v);
116 }
117
118 /*
119 * Tables from IJPG software
120 */
121 static const int std_luminance_quant_tbl[64] = {
122 16, 11, 12, 14, 12, 10, 16, 14, 13, 14, 18, 17, 16, 19, 24, 40,
123 26, 24, 22, 22, 24, 49, 35, 37, 29, 40, 58, 51, 61, 60, 57, 51,
124 56, 55, 64, 72, 92, 78, 64, 68, 87, 69, 55, 56, 80, 109, 81, 87,
125 95, 98, 103, 104, 103, 62, 77, 113, 121, 112, 100, 120, 92, 101, 103, 99
126 };
127
128 static const int std_chrominance_quant_tbl[64] = {
129 17, 18, 18, 24, 21, 24, 47, 26, 26, 47, 99, 66, 56, 66, 99, 99,
130 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99,
131 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99,
132 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99
133 };
134
135 static const unsigned char dc_luminance_bits[17] =
136 { /* 0-base */ 0, 0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 };
137 static const unsigned char dc_luminance_val[] =
138 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
139
140 static const unsigned char dc_chrominance_bits[17] =
141 { /* 0-base */ 0, 0, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0 };
142 static const unsigned char dc_chrominance_val[] =
143 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
144
145 static const unsigned char ac_luminance_bits[17] =
146 { /* 0-base */ 0, 0, 2, 1, 3, 3, 2, 4, 3, 5, 5, 4, 4, 0, 0, 1, 0x7d };
147 static const unsigned char ac_luminance_val[] =
148 { 0x01, 0x02, 0x03, 0x00, 0x04, 0x11, 0x05, 0x12,
149 0x21, 0x31, 0x41, 0x06, 0x13, 0x51, 0x61, 0x07,
150 0x22, 0x71, 0x14, 0x32, 0x81, 0x91, 0xa1, 0x08,
151 0x23, 0x42, 0xb1, 0xc1, 0x15, 0x52, 0xd1, 0xf0,
152 0x24, 0x33, 0x62, 0x72, 0x82, 0x09, 0x0a, 0x16,
153 0x17, 0x18, 0x19, 0x1a, 0x25, 0x26, 0x27, 0x28,
154 0x29, 0x2a, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39,
155 0x3a, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49,
156 0x4a, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59,
157 0x5a, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69,
158 0x6a, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79,
159 0x7a, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89,
160 0x8a, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98,
161 0x99, 0x9a, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
162 0xa8, 0xa9, 0xaa, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6,
163 0xb7, 0xb8, 0xb9, 0xba, 0xc2, 0xc3, 0xc4, 0xc5,
164 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xd2, 0xd3, 0xd4,
165 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xe1, 0xe2,
166 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea,
167 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8,
168 0xf9, 0xfa };
169
170 static const unsigned char ac_chrominance_bits[17] =
171 { /* 0-base */ 0, 0, 2, 1, 2, 4, 4, 3, 4, 7, 5, 4, 4, 0, 1, 2, 0x77 };
172 static const unsigned char ac_chrominance_val[] =
173 { 0x00, 0x01, 0x02, 0x03, 0x11, 0x04, 0x05, 0x21,
174 0x31, 0x06, 0x12, 0x41, 0x51, 0x07, 0x61, 0x71,
175 0x13, 0x22, 0x32, 0x81, 0x08, 0x14, 0x42, 0x91,
176 0xa1, 0xb1, 0xc1, 0x09, 0x23, 0x33, 0x52, 0xf0,
177 0x15, 0x62, 0x72, 0xd1, 0x0a, 0x16, 0x24, 0x34,
178 0xe1, 0x25, 0xf1, 0x17, 0x18, 0x19, 0x1a, 0x26,
179 0x27, 0x28, 0x29, 0x2a, 0x35, 0x36, 0x37, 0x38,
180 0x39, 0x3a, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48,
181 0x49, 0x4a, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58,
182 0x59, 0x5a, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68,
183 0x69, 0x6a, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
184 0x79, 0x7a, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
185 0x88, 0x89, 0x8a, 0x92, 0x93, 0x94, 0x95, 0x96,
186 0x97, 0x98, 0x99, 0x9a, 0xa2, 0xa3, 0xa4, 0xa5,
187 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xb2, 0xb3, 0xb4,
188 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xc2, 0xc3,
189 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xd2,
190 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda,
191 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9,
192 0xea, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8,
193 0xf9, 0xfa };
194
195 void JpegDecoder::defaults(JpegDecoder::config& c)
196 {
197 c.width = 0;
198 c.height = 0;
199
200 c.precision = 8;
201 c.ncomp = 3;
202 /* Y */
203 c.comp[0].id = 0;
204 c.comp[0].hsf = 2;
205 c.comp[0].vsf = 1;
206 c.comp[0].quant_tbl_no = 0;
207 /* U */
208 c.comp[1].id = 1;
209 c.comp[1].hsf = 1;
210 c.comp[1].vsf = 1;
211 c.comp[1].quant_tbl_no = 1;
212 /* V */
213 c.comp[2].id = 2;
214 c.comp[2].hsf = 1;
215 c.comp[2].vsf = 1;
216 c.comp[2].quant_tbl_no = 1;
217
218 c.dc_huffbits[0] = dc_luminance_bits;
219 c.dc_huffval[0] = dc_luminance_val;
220 c.dc_huffbits[1] = dc_chrominance_bits;
221 c.dc_huffval[1] = dc_chrominance_val;
222 c.ac_huffbits[0] = ac_luminance_bits;
223 c.ac_huffval[0] = ac_luminance_val;
224 c.ac_huffbits[1] = ac_chrominance_bits;
225 c.ac_huffval[1] = ac_chrominance_val;
226 for (int i = 2; i < 4; ++i) {
227 c.ac_huffbits[i] = 0;
228 c.ac_huffval[i] = 0;
229 c.dc_huffbits[i] = 0;
230 c.dc_huffval[i] = 0;
231 }
232 c.comp[0].dc_tbl_no = 0;
233 c.comp[0].ac_tbl_no = 0;
234 c.comp[1].dc_tbl_no = 1;
235 c.comp[1].ac_tbl_no = 1;
236 c.comp[2].dc_tbl_no = 1;
237 c.comp[2].ac_tbl_no = 1;
238 }
239
240 void JpegDecoder::quantizer(JpegDecoder::config& c, int q)
241 {
242 q = quality_to_qfactor(q);
243 for (int i = 0; i < 64; i++) {
244 int val = (q * std_luminance_quant_tbl[i] + 50) / 100;
245 if (val < 0)
246 val = 1;
247 if (val > 32768)
248 val = 32768;
249 c.qtab[0][i] = val;
250 }
251 for (i = 0; i < 64; i++) {
252 int val = (q * std_chrominance_quant_tbl[i] + 50) / 100;
253 if (val < 0)
254 val = 1;
255 if (val > 32768)
256 val = 32768;
257 c.qtab[1][i] = val;
258 }
259 }
260
261 JpegDecoder::JpegDecoder(const config& c) : color_(1), nojfif_(1),
262 width_(-1), height_(-1), csss_(0)
263 {
264 for (int i = NUM_HUFF_TBLS; --i >= 0; ) {
265 dcht_[i] = 0;
266 acht_[i] = 0;
267 }
268 for (i = MAX_COMPS_IN_SCAN; --i >= 0; )
269 comp_[i].frm = 0;
270
271 bzero((char*)comp_, sizeof(comp_));
272 init(c);
273 }
274
275 JpegDecoder::~JpegDecoder()
276 {
277 freehufftab();
278 delete comp_[0].frm;
279 }
280
281 void JpegDecoder::init(const config& c)
282 {
283 restart_interval_ = 0;
284 bcopy((char*)c.qtab, (char*)qt_, sizeof(qt_));
285 ncomp_ = c.ncomp;/*FIXME*/
286 if (width_ != c.width || height_ != c.height) {
287 width_ = c.width;
288 height_ = c.height;
289
290 /*
291 * Allocate the frame store
292 */
293 delete comp_[0].frm;
294 int size = width_ * height_;
295 #ifdef notyet
296 /*FIXME*/
297 #else
298 /*FIXME this allocates more than we need for 4:1:1*/
299 /*FIXME compute sizes based on csss factors*/
300 u_char* p = new u_char[2 * size];
301 comp_[0].frm = p;
302 p += size;
303 comp_[1].frm = p;
304 p += size / 2;
305 comp_[2].frm = p;
306 comp_[3].frm = 0;
307 /* Initialize u,v planes to gray */
308 memset((char*)comp_[1].frm, 0x80, size);
309 #endif
310 }
311 for (int i = ncomp_; --i >= 0; ) {
312 int id = c.comp[i].id;
313 comp_[id].hsf = c.comp[i].hsf;
314 comp_[id].vsf = c.comp[i].vsf;
315 comp_[id].quant_tbl_no = c.comp[i].quant_tbl_no;
316 comp_[id].dc_tbl_no = c.comp[i].dc_tbl_no;
317 comp_[id].ac_tbl_no = c.comp[i].ac_tbl_no;
318 }
319 /*
320 * FIXME should check if huffman table won't change
321 * before reallocating.
322 */
323 freehufftab();
324 for (i = 0; i < 4; ++i) {
325 if (c.dc_huffval[i] != 0) {
326 int id = c.comp[i].id;
327 dcht_[id] = huffbuild(c.dc_huffbits[i],
328 c.dc_huffval[i]);
329 }
330 if (c.ac_huffval[i] != 0) {
331 int id = c.comp[i].id;
332 acht_[id] = huffbuild(c.ac_huffbits[i],
333 c.ac_huffval[i]);
334 }
335 }
336
337 int maxh = 1;
338 int maxv = 1;
339 for (i = ncomp_; --i >= 0; ) {
340 if (maxh < comp_[i].hsf)
341 maxh = comp_[i].hsf;
342 if (maxv < comp_[i].vsf)
343 maxh = comp_[i].vsf;
344 }
345 mcu_cols_ = (width_ + 8 * maxh - 1) / (8 * maxh);
346 mcu_rows_ = (height_ + 8 * maxv - 1) / (8 * maxv);
347 }
348
349 void JpegDecoder::freehufftab()
350 {
351 for (int i = 0; i < 4; ++i) {
352 if (dcht_[i] != 0)
353 free(dcht_[i]);
354 if (acht_[i] != 0)
355 free(acht_[i]);
356 }
357 }
358
359 void JpegDecoder::fill(u_int dc, u_char* out, int stride) const
360 {
361 int t;
362 dc = UCLIMIT(dc) & 0xff;
363 dc |= dc << 8;
364 dc |= dc << 16;
365 #ifdef INT_64
366 INT_64 xdc = dc;
367 xdc |= xdc << 32;
368 *(INT_64 *)out = xdc;
369 out += stride;
370 *(INT_64 *)out = xdc;
371 out += stride;
372 *(INT_64 *)out = xdc;
373 out += stride;
374 *(INT_64 *)out = xdc;
375 out += stride;
376 *(INT_64 *)out = xdc;
377 out += stride;
378 *(INT_64 *)out = xdc;
379 out += stride;
380 *(INT_64 *)out = xdc;
381 out += stride;
382 *(INT_64 *)out = xdc;
383 #else
384 *(u_word*)out = dc;
385 *(u_word*)(out + 4) = dc;
386 out += stride;
387 *(u_word*)out = dc;
388 *(u_word*)(out + 4) = dc;
389 out += stride;
390 *(u_word*)out = dc;
391 *(u_word*)(out + 4) = dc;
392 out += stride;
393 *(u_word*)out = dc;
394 *(u_word*)(out + 4) = dc;
395 out += stride;
396 *(u_word*)out = dc;
397 *(u_word*)(out + 4) = dc;
398 out += stride;
399 *(u_word*)out = dc;
400 *(u_word*)(out + 4) = dc;
401 out += stride;
402 *(u_word*)out = dc;
403 *(u_word*)(out + 4) = dc;
404 out += stride;
405 *(u_word*)out = dc;
406 *(u_word*)(out + 4) = dc;
407 #endif
408 }
409
410 /*
411 * This routine mixes the DC & AC components of an 8x8 block of
412 * pixels. This routine is called for every block decoded so it
413 * needs to be efficient. It tries to do as many pixels in parallel
414 * as will fit in a word. The one complication is that it has to
415 * deal with overflow (sum > 255) and underflow (sum < 0). Underflow
416 * & overflow are only possible if both terms have the same sign and
417 * are indicated by the result having a different sign than the terms.
418 * Note that underflow is more worrisome than overflow since it results
419 * in bright white dots in a black field.
420 * The DC term and sum are biased by 128 so a negative number has the
421 * 2^7 bit = 0. The AC term is not biased so a negative number has
422 * the 2^7 bit = 1. So underflow is indicated by (DC & AC & sum) != 0;
423 */
424 #define JPEG_MIX_LOGIC \
425 sum = dc + ac; \
426 uflo = (dc ^ ac) & (dc ^ sum) & omask; \
427 if (uflo) { \
428 if ((ac = uflo & dc) != 0) { \
429 /* integer overflows */ \
430 ac |= ac >> 1; \
431 ac |= ac >> 2; \
432 ac |= ac >> 4; \
433 sum |= ac; \
434 } \
435 if ((uflo &=~ ac) != 0) { \
436 /* integer underflow(s) */ \
437 uflo |= uflo >> 1; \
438 uflo |= uflo >> 2; \
439 uflo |= uflo >> 4; \
440 sum &= ~uflo; \
441 } \
442 }
443
444 #ifdef INT_64
445 #define JPEG_MIX8(bp, out) \
446 ac = *(INT_64*)(bp); \
447 JPEG_MIX_LOGIC \
448 *(INT_64*)(out) = sum; \
449 (bp) += 8; \
450 (out) += stride;
451 #else
452 #define JPEG_MIX4(bp, out) \
453 ac = *(u_word*)(bp); \
454 JPEG_MIX_LOGIC \
455 *(u_word*)(out) = sum;
456
457 #define JPEG_MIX8(bp, out) \
458 JPEG_MIX4(bp, out) \
459 JPEG_MIX4(bp + 4, out + 4) \
460 bp += 8; \
461 out += stride;
462 #endif
463
464
465 void JpegDecoder::mix(u_int idc, const u_char* bp, u_char* out, int stride) const
466 {
467 register int t;
468
469 idc = UCLIMIT(idc) & 0xff;
470 idc |= idc << 8;
471 idc |= idc << 16;
472 #ifdef INT_64
473 INT_64 dc = idc, ac, sum;
474 dc |= dc << 32;
475 INT_64 uflo, omask = 0x8080808080808080;
476 #else
477 u_word dc = idc, ac, sum;
478 u_word uflo, omask = 0x80808080;
479 #endif
480
481 JPEG_MIX8(bp, out)
482 JPEG_MIX8(bp, out)
483 JPEG_MIX8(bp, out)
484 JPEG_MIX8(bp, out)
485 JPEG_MIX8(bp, out)
486 JPEG_MIX8(bp, out)
487 JPEG_MIX8(bp, out)
488 JPEG_MIX8(bp, out)
489 }
490
491 #define MAXCODE 64
492 struct hcnode {
493 struct hcnode *next;
494 u_char pix[64];
495 u_word n;
496 u_word code[MAXCODE];
497 };
498
499 #define HASHSIZE (2*4096)
500 static struct hcnode *hashtab[HASHSIZE];
501 /*FIXME*/
502 #define NHC (2*HASHSIZE)
503 static struct hcnode *hcpool;
504 static int nhc;
505
506 static struct hcnode *
507 scavenge()
508 {
509 register struct hcnode *p;
510
511 int i = nhc;
512 if (i >= NHC) {
513 static int rover = 0;
514
515 i = rover;
516 do
517 i = (i + 1) & (HASHSIZE - 1);
518 while ((p = hashtab[i]) == 0);
519 rover = i;
520 hashtab[i] = p->next;
521 } else {
522 if (hcpool == 0)
523 hcpool = new hcnode[NHC];
524 p = &hcpool[i];
525 nhc = i + 1;
526 }
527 return (p);
528 }
529
530 static inline int
531 hchash(int n, u_word *code)
532 {
533 int v = 0;
534
535 while (--n >= 0)
536 v += code[n] + 37;
537 return ((v ^ v >> 16) & (HASHSIZE - 1));
538 }
539
540 static inline struct hcnode *
541 hclookup(int h, int n, u_word *code)
542 {
543 struct hcnode *p;
544
545 for (p = hashtab[h]; p != 0; p = p->next)
546 if (p->n == n &&
547 bcmp((char*)p->code, (char*)code, n * sizeof(*code)) == 0)
548 break;
549
550 return (p);
551 }
552
553 static void
554 hcenter(struct hcnode *p, int h, int n, u_word *code, short* dctcoef)
555 {
556 bcopy((char*)code, (char*)p->code, n * sizeof(*code));
557 p->n = n;
558
559 dctcoef[0] = 0;
560 //j_rev_dct(dctcoef, p->pix);
561 j_rev_dct(dctcoef);
562 register u_int* pp = (u_int*)&p->pix[0];
563 for (register int i = 0; i < 64; i += 4) {
564 register int r, t;
565 #if BYTE_ORDER == LITTLE_ENDIAN
566 r = SCLIMIT(dctcoef[i+3]) & 0xff;
567 r = (r << 8) | (SCLIMIT(dctcoef[i+2]) & 0xff);
568 r = (r << 8) | (SCLIMIT(dctcoef[i+1]) & 0xff);
569 r = (r << 8) | (SCLIMIT(dctcoef[i]) & 0xff);
570 #else
571 r = SCLIMIT(dctcoef[i]) & 0xff;
572 r = (r << 8) | (SCLIMIT(dctcoef[i+1]) & 0xff);
573 r = (r << 8) | (SCLIMIT(dctcoef[i+2]) & 0xff);
574 r = (r << 8) | (SCLIMIT(dctcoef[i+3]) & 0xff);
575 #endif
576 *pp++ = r;
577 }
578
579 p->next = hashtab[h];
580 hashtab[h] = p;
581 }
582
583 int hcmiss;
584 int hchit;
585 int dcblk;
586 int bblk;
587 int sblk;
588
589 static int
590 length(struct hcnode *p)
591 {
592 int n = 0;
593 for (; p != 0; p = p->next)
594 ++n;
595 return (n);
596 }
597
598 void
599 pstats()
600 {
601 int i;
602 int len;
603 int bucket = 0;
604 int maxlen = 0;
605
606 for (i = 0; i < HASHSIZE; ++i) {
607 if (hashtab[i] == 0)
608 continue;
609 ++bucket;
610 len = length(hashtab[i]);
611 if (len > maxlen)
612 maxlen = len;
613 }
614 printf("hit\t%d\n", hchit);
615 printf("miss\t%d\n", hcmiss);
616 printf("bucket\t%d\n", bucket);
617 printf("maxlen\t%d\n", maxlen);
618 printf("dcblk\t%d\n", dcblk);
619 printf("bblk\t%d\n", bblk);
620 printf("sblk\t%d\n", sblk);
621 }
622
623 #ifdef notdef
624 int JpegDecoder::decode_block(int ci, int off, int stride)
625 {
626 int n, h;
627 struct hcnode *p;
628 const short* qt;
629 int dc;
630 short block[64];
631 u_word code[128];
632
633 /*FIXME*/
634 component& c = comp_[ci];
635 qt = qt_[c.quant_tbl_no];
636
637 n = huffparse(ci, code);
638 if (n == 0) {
639 dc = c.dc * qt[0];
640 fill((dc >> 3) + 128, c.frm + off, stride);
641 ++dcblk;
642 } else if (n < MAXCODE) {
643 ++sblk;
644 h = hchash(n, code);
645 p = hclookup(h, n, code);
646 if (p == 0) {
647 ++hcmiss;
648 p = scavenge();
649 if (huffblock(ci, n, code, block) < 0)
650 return (-1);
651 hcenter(p, h, n, code, block);
652 } else
653 ++hchit;
654 dc = c.dc * qt[0];
655 mix((dc >> 3) + 128, p->pix, c.frm + off, stride);
656 } else {
657 u_char pix[64];
658
659 ++bblk;
660 if (huffblock(ci, n, code, block) < 0)
661 return (-1);
662 //j_rev_dct_c(block, pix);
663 j_rev_dct(block);
664 for (register int i = 0; i < 64; ++i) {
665 register int t;
666 pix[i] = SCLIMIT(block[i]) & 0xff;
667 //pix[i] = block[i];
668 }
669 mix(0, pix, c.frm + off, stride);
670 }
671 return (0);
672 }
673 #endif
674
675 short blk[320*240/64][64];
676 int skip;
677
678 int blkthresh = 100;
679
680 int blkdiff(short* b0, short* b1)
681 {
682 int d = 0;
683 for (int i = 0; i < 32; ++i) {
684 int k = ZAG[i];
685 int t = b0[k] - b1[k];
686 if (t < 0)
687 t = -t;
688 d += t;
689 }
690 return (d < blkthresh);
691 }
692
693 /*FIXME*/
694 static int blkno;
695
696 int JpegDecoder::decode_block(int ci, int off, int stride)
697 {
698 /*FIXME*/
699 u_word code[128];
700 int n = huffparse(ci, code);
701 short block[64];
702 if (huffblock(ci, n, code, block) < 0)
703 return (-1);
704
705 if (ci == 0) {
706 int b = blkno++;
707 if (blkdiff(block, blk[b])) {
708 skip = 1;
709 return (0);
710 }
711 bcopy((char*)block, (char*)blk[b], 64 * 2);
712 }
713
714 j_rev_dct(block);
715 u_long Pix[64 / sizeof(u_long)];
716 u_char* pix = (u_char*)Pix;
717
718 for (int i = 0; i < 64; ++i) {
719 int t;
720 pix[i] = SCLIMIT(block[i]) & 0xff;
721 }
722 mix(128, pix, comp_[ci].frm + off, stride);
723
724 return (0);
725 }
726 #ifdef notdef
727 #endif
728
729 int JpegDecoder::rdqt(const u_char* p)
730 {
731 int len = *p++ << 8;
732 len |= *p++;
733
734 const u_char* ep = p + len - 2;
735 while (p < ep) {
736 int n = *p++;
737 int prec = n >> 4;
738 n &= 0x0F;
739 if (n >= 4) {
740 /*FIXME illegal number*/
741 return (-1);
742 }
743 short* qt = qt_[n];
744 for (int i = 0; i < 64; i++) {
745 int v = *p++;
746 if (prec)
747 v = (v << 8) + *p++;
748 qt[i] = v;
749 }
750 }
751 return (len);
752 }
753
754 void JpegDecoder::restart()
755 {
756 int c;
757 nbb_ = 0;
758 /*FIXMEwhat if ff is sitting in bit buffer?*/
759 /* Scan for next JPEG marker */
760 do {
761 do { /* skip any non-FF bytes */
762 c = *inb_++;
763 } while (c != 0xFF);
764 do {
765 /* skip any duplicate FFs */
766 /* we don't increment nbytes here since extra FFs are legal */
767 c = *inb_++;
768 } while (c == 0xFF);
769 } while (c == 0); /* repeat if it was a stuffed FF/00 */
770 #ifdef notdef
771 if (nbytes != 1)
772 WARNMS2(cinfo->emethods,
773 "Corrupt JPEG data: %d extraneous bytes before marker 0x%02x",
774 nbytes-1, c);
775
776 #endif
777 #ifdef notdef
778 if (c != (RST0 + cinfo->next_restart_num)) {
779 /* Uh-oh, the restart markers have been messed up too. */
780 /* Let the file-format module try to figure out how to resync. */
781 (*cinfo->methods->resync_to_restart) (cinfo, c);
782 } else
783 TRACEMS1(cinfo->emethods, 2, "RST%d", cinfo->next_restart_num);
784 #endif
785 /* Re-initialize DC predictions to 0 */
786 for (int i = 0; i < MAX_COMPS_IN_SCAN; ++i)
787 comp_[i].dc = 0;
788 #ifdef notdef
789 cinfo->next_restart_num = (cinfo->next_restart_num + 1) & 7;
790 #endif
791 }
792
793 u_char* JpegDecoder::parseFIF(u_char* in)
794 {
795 int t;
796 while (in < end_) {
797 if (*in++ != 0xff)
798 continue;
799 /*FIXME need more checks for buffer overflow*/
800 switch (*in++) {
801
802 default:
803 /* Don't know. Keep looking for SOS. */
804 continue;
805
806 case 0xdb:
807 /* quantization table */
808 t = rdqt(in);
809 if (t < 0)
810 /*FIXME*/
811 return (end_);
812 in += t;
813 continue;
814
815 case 0xdd:
816 /* restart interval definition */
817 t = *in++ << 8;
818 t |= *in++;
819 if (t != 4)
820 /* FIXME bad length */
821 ;
822 restart_interval_ = *in++ << 8;
823 restart_interval_ |= *in++;
824 restart_counter_ = 0;
825 continue;
826
827 case 0xda:
828 /* start-of-scan marker */
829 if (in + 2 <= end_) {
830 /* skip over SOS */
831 int t = *in++ << 8;
832 t |= *in++;
833 in += (t - 2);
834 }
835 return (in);
836 }
837 }
838 /*FIXME*/
839 return (end_);
840 }
841
842 int JpegDecoder_422::decode(u_char* in, int len)
843 {
844 /*FIXME*/
845 if (*in == 0xff)
846 nojfif_ = 0;
847
848 inb_ = in;
849 end_ = in + len;
850 nbb_ = 0;
851 /*
852 * FIXME break this into a separate routine that gets called
853 * only when this crap is present
854 */
855 if (!nojfif_)
856 inb_ = parseFIF(inb_);
857
858 int off0 = 0;
859 int off1 = 0;
860 huffreset();
861 blkno = 0;/*FIXME*/
862 for (int y = mcu_rows_; --y >= 0; ) {
863 for (int x = mcu_cols_; --x >= 0; ) {
864 if (restart_interval_) {
865 if (--restart_counter_ <= 0) {
866 restart_counter_ = restart_interval_;
867 restart();
868 }
869 }
870 skip = 0;
871 if (decode_block(0, off0, width_) < 0)
872 return (-1);
873 off0 += 8;
874 /*FIXME*/
875 if (skip) {
876 skip = 0;
877 if (decode_block(0, off0, width_) < 0)
878 return (-1);
879 if (skip) {
880 u_word code[128];
881 off0 += 8;
882 off1 += 8;
883 (void)huffparse(1, code);
884 (void)huffparse(2, code);
885 continue;
886 }
887 } else
888 if (decode_block(0, off0, width_) < 0)
889 return (-1);
890 off0 += 8;
891 if (color_) {
892 if (decode_block(1, off1, width_ / 2) < 0)
893 return (-1);
894 if (decode_block(2, off1, width_ / 2) < 0)
895 return (-1);
896 off1 += 8;
897 } else if (huffskip(1) < 0 || huffskip(2) < 0)
898 return (-1);
899 }
900 off0 -= width_;
901 off0 += 8 * width_;
902 off1 -= width_ / 2;
903 off1 += 8 * width_ / 2;
904 }
905 return (0);
906 }
907
908 int JpegDecoder_420::decode(u_char* in, int len)
909 {
910 /*FIXME*/
911 if (*in == 0xff)
912 nojfif_ = 0;
913
914 inb_ = in;
915 end_ = in + len;
916 nbb_ = 0;
917 /*
918 * FIXME break this into a separate routine that gets called
919 * only when this crap is present
920 */
921 if (!nojfif_)
922 inb_ = parseFIF(inb_);
923
924 int off0 = 0;
925 int off1 = 0;
926 huffreset();
927 for (int y = mcu_rows_ / 2; --y >= 0; ) {
928 for (int x = mcu_cols_; --x >= 0; ) {
929 if (restart_interval_) {
930 if (--restart_counter_ <= 0) {
931 restart_counter_ = restart_interval_;
932 restart();
933 }
934 }
935 /* FIXME this works only for hsamp = 2, vsamp = 2 */
936 if (decode_block(0, off0, width_) < 0)
937 return (-1);
938 if (decode_block(0, off0 + 8, width_) < 0)
939 return (-1);
940 if (decode_block(0, off0 + 8 * width_, width_) < 0)
941 return (-1);
942 if (decode_block(0, off0 + 8 * width_ + 8, width_) < 0)
943 return (-1);
944 off0 += 16;
945 if (color_) {
946 if (decode_block(1, off1, width_ / 2) < 0)
947 return (-1);
948 if (decode_block(2, off1, width_ / 2) < 0)
949 return (-1);
950 off1 += 8;
951 } else if (huffskip(1) < 0 || huffskip(2) < 0)
952 return (-1);
953 }
954 off0 -= width_;
955 off0 += 16 * width_;
956 off1 -= width_ / 2;
957 off1 += 8 * width_ / 2;
958 }
959 return (0);
960 }
961
962 /* Figure F.12: extend sign bit */
963
964 #ifdef notdef
965 #define huff_EXTEND(x,s) ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
966
967 static const int extend_test[16] = /* entry n is 2**(n-1) */
968 { 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
969 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000 };
970
971 static const int extend_offset[16] = /* entry n is (-1 << n) + 1 */
972 { 0, ((-1)<<1) + 1, ((-1)<<2) + 1, ((-1)<<3) + 1, ((-1)<<4) + 1,
973 ((-1)<<5) + 1, ((-1)<<6) + 1, ((-1)<<7) + 1, ((-1)<<8) + 1,
974 ((-1)<<9) + 1, ((-1)<<10) + 1, ((-1)<<11) + 1, ((-1)<<12) + 1,
975 ((-1)<<13) + 1, ((-1)<<14) + 1, ((-1)<<15) + 1 };
976 #else
977 /* is this really faster? */
978 inline int
979 huff_EXTEND(int x, int s)
980 {
981 register int b = x >> (s - 1);
982 register int m = ((b & 1) - 1) << s;
983 return ((x | m) + (~b & 1));
984 }
985 #endif
986
987 #define HUFFRQ(bb) \
988 { \
989 register int v; \
990 register u_char *cp = inb_; \
991 \
992 bb <<= 16; \
993 v = *cp++; \
994 if (v == 0xff) ++cp; \
995 bb |= v << 8; \
996 v = *cp++; \
997 if (v == 0xff) ++cp; \
998 bb |= v; \
999 inb_ = cp; \
1000 \
1001 }
1002
1003 #define MASK(s) ((1 << (s)) - 1)
1004
1005 #define HUFF_DECODE(ht, nbb, bb, result) { \
1006 register int s_, v_; \
1007 \
1008 if (nbb < 16) { \
1009 HUFFRQ(bb); \
1010 nbb += 16; \
1011 } \
1012 v_ = (bb >> (nbb - 16)) & 0xffff; \
1013 s_ = (ht)[v_]; \
1014 nbb -= (s_ >> 8); \
1015 result = s_ & 0xff; \
1016 }
1017
1018 #define GET_BITS(n, nbb, bb, result) \
1019 { \
1020 nbb -= n; \
1021 if (nbb < 0) { \
1022 HUFFRQ(bb); \
1023 nbb += 16; \
1024 } \
1025 (result) = ((bb >> nbb) & MASK(n)); \
1026 }
1027
1028 #define SKIP_BITS(n, nbb, bb) \
1029 { \
1030 nbb -= n; \
1031 if (nbb < 0) { \
1032 HUFFRQ(bb); \
1033 nbb += 16; \
1034 } \
1035 }
1036
1037 int JpegDecoder::huffparse(int ci, u_word *code)
1038 {
1039 component& p = comp_[ci];
1040
1041 /* Decode a single block's worth of coefficients */
1042
1043 /* Section F.2.2.1: decode the DC coefficient difference */
1044 register int bb = bb_;
1045 register int nbb = nbb_;
1046 u_short* ht = dcht_[p.dc_tbl_no];
1047 register int s, r;
1048 HUFF_DECODE(ht, nbb, bb, s);
1049 if (s != 0) {
1050 GET_BITS(s, nbb, bb, r);
1051 s = huff_EXTEND(r, s);
1052 }
1053 /* Convert DC difference to actual value, update predictor */
1054 s += p.dc;
1055 p.dc = s;
1056
1057 /* Section F.2.2.2: decode the AC coefficients */
1058 ht = acht_[p.ac_tbl_no];
1059 register int n = 0;
1060 for (register int k = 1; k < 64; ) {
1061 /* Symbol-1 */
1062 register int v;
1063 HUFF_DECODE(ht, nbb, bb, v);
1064 s = v & 15;
1065 r = v >> 4;
1066 if (s != 0) {
1067 k += r;
1068 /* Symbol-2 */
1069 GET_BITS(s, nbb, bb, s);
1070 *code++ = (s << 8) | v;
1071 ++n;
1072 ++k;
1073 } else {
1074 if (r != 15)
1075 /* end of block */
1076 break;
1077 *code++ = v;
1078 ++n;
1079 k += 16;
1080 }
1081 }
1082 nbb_ = nbb;
1083 bb_ = bb;
1084
1085 return (n);
1086 }
1087
1088 int JpegDecoder::huffskip(int ci)
1089 {
1090 /* Decode a single block's worth of coefficients */
1091
1092 /* Section F.2.2.1: decode the DC coefficient difference */
1093 register int bb = bb_;
1094 register int nbb = nbb_;
1095 component& p = comp_[ci];
1096 u_short* ht = dcht_[p.dc_tbl_no];
1097 register int s;
1098 HUFF_DECODE(ht, nbb, bb, s);
1099 if (s != 0) {
1100 SKIP_BITS(s, nbb, bb);
1101 }
1102
1103 /* Section F.2.2.2: decode the AC coefficients */
1104 ht = acht_[p.ac_tbl_no];
1105 for (register int k = 1; k < 64; ) {
1106 /* Symbol-1 */
1107 register int v;
1108 HUFF_DECODE(ht, nbb, bb, v);
1109 s = v & 15;
1110 register int r = v >> 4;
1111 if (s != 0) {
1112 k += r;
1113 /* Symbol-2 */
1114 SKIP_BITS(s, nbb, bb);
1115 ++k;
1116 } else {