Add unjpeg.c, frmo an earlier project.
[fjl] / unjpeg.c
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 struct huffman_table {
5         unsigned num_codes[17];     /* BITS */
6         unsigned char codes[256];   /* HUFFVAL */
7         
8         /* derived values */
9         unsigned huffsize[256];
10         unsigned huffcode[256];
11         int maxcode[16];
12         int mincode[16];
13         unsigned valptr[16];
14 };
15 struct huffman_table huffman_tables[2][4];
16
17 struct mem_stream {
18         unsigned char *buf;
19         unsigned used, room;
20 };
21 struct mem_stream streams[128];
22
23 void *xmalloc(size_t size)
24 {
25         void *buf = malloc(size);
26         if (buf == NULL) {
27                 perror("malloc");
28                 exit(1);
29         }
30
31         return buf;
32 }
33         
34 static int numch = 0;
35
36 unsigned char mygetc()
37 {
38         int ch = getchar();
39         ++numch;
40         if (ch == EOF) {
41                 if (feof(stdin)) {
42                         fprintf(stderr, "Error: Unexpected end of file.\n");
43                         exit(1);
44                 } else {
45                         perror("getchar()");
46                         exit(1);
47                 }
48         }
49
50         return ((unsigned char)ch);
51 }
52
53 void putchar_stream(int stream, unsigned char ch)
54 {
55         int used = streams[stream].used;
56
57         if (streams[stream].used == streams[stream].room) {
58                 streams[stream].room <<= 1;
59                 streams[stream].buf = (unsigned char *)realloc(streams[stream].buf, streams[stream].room);
60         }
61
62         streams[stream].buf[streams[stream].used++] = ch;
63 }
64
65 void flush_stream(int stream)
66 {
67         fwrite(streams[stream].buf, streams[stream].used, 1, stdout);
68         streams[stream].used = 0;
69 }
70
71 unsigned char mygetc_limit(unsigned *len)
72 {
73         if (*len == 0) {
74                 fprintf(stderr, "Error: Premature end of segment\n");
75                 exit(1);
76         }
77         --*len;
78         return mygetc();
79 }
80         
81 unsigned read_length()
82 {
83         unsigned char len1 = mygetc();
84         unsigned char len2 = mygetc();
85         unsigned len = (len1 << 8) | len2;
86
87         if (len < 2) {
88                 fprintf(stderr, "Error: Got length %u, expected at least 2\n", len);
89                 exit(1);
90         }
91
92         return len;
93 }
94                         
95 void copy_segment(unsigned char marker_code)
96 {
97         unsigned len = read_length();
98         unsigned i;
99
100         /* marker segment header */
101         putchar(0xff);
102         putchar(marker_code);
103         putchar(len >> 8);
104         putchar(len & 0xff);
105
106         for (i = 0; i < len - 2; ++i) {
107                 putchar(mygetc());
108         }
109 }
110
111 void read_huffman_tables()
112 {
113         unsigned len = read_length() - 2;
114
115         putchar(0xff);
116         putchar(0xda);
117         putchar(len >> 8);
118         putchar(len & 0xff);
119
120         for ( ;; ) {
121                 unsigned char tc_th = mygetc_limit(&len);
122                 unsigned table_class = tc_th >> 4;
123                 unsigned table_dest = tc_th & 0x0f;
124                 unsigned i, j, k, si;
125                 struct huffman_table *tbl;
126
127                 if (table_class != 0 && table_class != 1) {
128                         fprintf(stderr, "Error: Unknown table class %u\n", table_class);
129                         exit(1);
130                 }
131                 if (table_dest >= 4) {
132                         fprintf(stderr, "Error: Unknown table destination %u\n", table_dest);
133                         exit(1);
134                 }
135
136                 putchar(tc_th);
137                 tbl = &huffman_tables[table_class][table_dest];
138
139                 for (i = 0; i < 16; ++i) {
140                         tbl->num_codes[i] = mygetc_limit(&len);
141                         putchar(tbl->num_codes[i]);
142                         fprintf(stderr, "%u ", tbl->num_codes[i]);
143                 }
144                 fprintf(stderr, "\ndumping tc=%u td=%u\n", table_class, table_dest);
145                 for (i = 0, k = 0; i < 16; ++i) {
146                         for (j = 0; j < tbl->num_codes[i]; ++j, ++k) {
147                                 tbl->codes[k] = mygetc_limit(&len);
148                                 putchar(tbl->codes[k]);
149                                 fprintf(stderr, "%u: len=%u, ind=%u: code=0x%02x\n", k, i+1, j, tbl->codes[k]);
150                         }
151                 }
152
153                 /* generate derived tables */
154
155                 /* generate_size_table (figure C.1) */
156                 k = 0;
157                 for (i = 0; i < 16; ++i) {
158                         for (j = 0; j < tbl->num_codes[i]; ++j, ++k) {
159                                 tbl->huffsize[k] = i+1;
160                         }
161                 }
162                 tbl->huffsize[k] = 0;
163                 fprintf(stderr, "k=%u\n", k);
164
165                 /* generate_code_table (figure C.2) */
166                 si = tbl->huffsize[0];
167                 for (i = 0, j = 0;; ) {
168                         fprintf(stderr, "%u = %u [si=%u]\n", i, j, si);
169
170                         tbl->huffcode[i++] = j++;
171                         if (tbl->huffsize[i] == si) {
172                                 continue;
173                         }
174
175                         if (tbl->huffsize[i] == 0) {
176                                 break;
177                         }
178
179                         do {
180                                 j <<= 1;
181                         } while (++si != tbl->huffsize[i]);
182                 }
183
184                 /* decoder_tables (figure F.15) */
185                 for (i = 0, j = 0; i < 16; ++i) {
186                         if (tbl->num_codes[i] == 0) {
187                                 tbl->maxcode[i] = -1;
188                                 continue;
189                         }
190
191                         tbl->valptr[i] = j;
192                         //fprintf(stderr, "minind=%u\n", j);
193                         tbl->mincode[i] = tbl->huffcode[j];
194                         j += tbl->num_codes[i];
195                         //fprintf(stderr, "maxind=%u\n", j-1);
196                         tbl->maxcode[i] = tbl->huffcode[j - 1];
197
198                         //fprintf(stderr, "%u: min=%u, max=%u\n", i, tbl->mincode[i], tbl->maxcode[i]);
199                 }
200
201                 if (len == 0) {
202                         break;
203                 }
204         }
205 }
206
207 /* procedure NEXTBIT */
208 unsigned get_bit(unsigned *bits_available, unsigned char *bit_reservoir)
209 {
210         unsigned bit;
211
212         if (*bits_available == 0) {
213                 *bit_reservoir = mygetc();
214                 //fprintf(stderr, "Read byte (0x%02x)\n", *bit_reservoir);
215                 if (*bit_reservoir == 0xff) {
216                         unsigned char ch = mygetc();
217                         if (ch != 0) {
218                                 int i;
219                                 for (i = 0; i < 128; ++i) {
220                                         flush_stream(i);
221                                 }
222
223                                 fprintf(stderr, "Error: Couldn't handle marker 0x%02x\n", ch);
224                                 exit(1);
225                         }
226                         //fprintf(stderr, "Read stuff byte (%u)\n", ch);
227                 }
228
229                 *bits_available = 8;
230         }
231
232         bit = *bit_reservoir >> 7;
233         *bit_reservoir = (*bit_reservoir & 0x7f) << 1;
234         --*bits_available;
235
236         //fprintf(stderr, "%u\n", bit);
237
238         return bit;
239 }
240
241 /* procedure DECODE (figure F.16) */
242 unsigned char get_huffman_byte(unsigned *bits_available, unsigned char *bit_reservoir, struct huffman_table* huff_tbl)
243 {
244         unsigned code = get_bit(bits_available, bit_reservoir);
245         int i = 1;
246
247         while (code > huff_tbl->maxcode[i - 1] || huff_tbl->maxcode[i - 1] == -1) {
248                 code = (code << 1) | get_bit(bits_available, bit_reservoir);
249                 ++i;
250
251                 if (i > 16) {
252                         fprintf(stderr, "Error in Huffman decoding: Too long code (%x).numch=%u\n", code, numch);
253                         exit(1);
254                 }
255         }
256
257         /*fprintf(stderr, "h=%d => code=0x%02x\n", huff_tbl->valptr[i - 1] + code - huff_tbl->mincode[i - 1],
258                 huff_tbl->codes[huff_tbl->valptr[i - 1] + code - huff_tbl->mincode[i - 1]]);*/
259         return huff_tbl->codes[huff_tbl->valptr[i - 1] + code - huff_tbl->mincode[i - 1]];
260 }
261                         
262 /* procedure RECEIVE */
263 unsigned get_bits(unsigned num_bits, unsigned *bits_available, unsigned char *bit_reservoir)
264 {
265         unsigned val = 0, i;
266
267         for (i = 0; i < num_bits; ++i) {
268                 val <<= 1;
269                 val |= get_bit(bits_available, bit_reservoir);
270         }
271
272         return val;
273 }
274
275 /* procedure EXTEND (figure F.12) */
276 unsigned extend(int val, int bits)
277 {
278         if (val < (1 << (bits - 1))) {
279                 return val + (-1 << bits) + 1;
280         } else {
281                 return val;
282         }
283 }
284
285 void read_scan()
286 {
287         unsigned len = read_length() - 2;
288         unsigned bits_available;
289         unsigned char bit_reservoir;
290         unsigned num_components = mygetc_limit(&len);
291         unsigned i;
292         unsigned component_num[256];
293         unsigned dc_huffman_table[256], ac_huffman_table[256];
294         unsigned ss, se, ah_al;
295         int last_dc[256];
296         int last_ac[256];
297
298         for (i = 0; i < num_components; ++i) {
299                 unsigned char td_ta;
300                 component_num[i] = mygetc_limit(&len);
301                 td_ta = mygetc_limit(&len);
302                 dc_huffman_table[i] = td_ta >> 4;
303                 ac_huffman_table[i] = td_ta & 0x0f;
304                 last_dc[i] = 0;
305
306                 {
307                         unsigned j;
308                         for (j = 0; j < 64; ++j) {
309                                 last_ac[j] = 0;
310                         }
311                 }
312         }
313
314         ss = mygetc_limit(&len); 
315         se = mygetc_limit(&len); 
316         ah_al = mygetc_limit(&len); 
317
318         if (len != 0) {
319                 fprintf(stderr, "Error: %u unused bytes at end of SOS segment\n", len);
320         }
321
322         bits_available = 0;
323
324         for ( ;; ) {
325                 //fprintf(stderr, "\n");
326
327                 int c;
328                 for (c = 0; c < num_components; ++c) {
329                         int zz[63];
330                         /*fprintf(stderr, "coeff %u\n", c);
331                         fprintf(stderr, "getting dc (table %u)\n", dc_huffman_table[c]); */
332
333                         /* decode DC component */
334                         unsigned char dc_category = get_huffman_byte(&bits_available, &bit_reservoir, &huffman_tables[0][dc_huffman_table[c]]);
335                         int dc_diff;
336                         int i;
337
338                         dc_diff = get_bits(dc_category, &bits_available, &bit_reservoir);
339                         last_dc[c] += extend(dc_diff, dc_category);
340
341                         /*putchar_stream(0, last_dc[c] >> 8);
342                         putchar_stream(0, last_dc[c] & 0xff); */
343                         putchar_stream(0, dc_diff >> 8);
344                         putchar_stream(0, dc_diff & 0xff); 
345                         
346                         for (i = 0; i < 63; ++i) {
347                                 zz[i] = 0;
348                         }
349                         
350                         for (i = 0; i < 63; ++i) {
351                                 unsigned char rs = get_huffman_byte(&bits_available, &bit_reservoir, &huffman_tables[1][ac_huffman_table[c]]);
352                                 unsigned char r = rs >> 4;
353                                 unsigned char s = rs & 0xf;
354
355                                 if (rs == 0x00) {
356                                         /* end of block */
357                                         break;
358                                 }
359                                 if (rs == 0xf0) {
360                                         /* 16 zero coefficients */
361                                         i += 15;
362                                         continue;
363                                 }
364
365                                 i += r;
366                                 zz[i] = extend(get_bits(s, &bits_available, &bit_reservoir), s);
367                         }
368                         
369                         for (i = 0; i < 63; ++i) {
370                                 int s = i;
371                                 if (s > 54) {
372                                         s = 54;
373                                 }
374
375                                 int m;
376                                 if (zz[i] >= 0) {
377                                         m = zz[i] * 2;
378                                 } else {
379                                         m = (1 - zz[i] * 2);
380                                 }
381                                 putchar_stream(s * 2 + 2, m >> 8);
382                                 putchar_stream(s * 2 + 3, m & 0xff);
383                         }
384                 }
385         }
386 }
387
388 int main(void)
389 {
390         int i;
391         for (i = 0; i < 128; ++i) {
392                 streams[i].buf = (unsigned char *)malloc(4096);
393                 streams[i].used = 0;
394                 streams[i].room = 4096;
395         }
396
397         for ( ;; ) {
398                 unsigned char m1 = mygetc();
399                 unsigned char m2 = mygetc();
400
401                 if (m1 != 0xff) {
402                         fprintf(stderr, "Error: Expected marker (0xff), got 0x%02x\n", m1);
403                         exit(1);
404                 }
405
406                 switch (m2) {
407                 case 0xe0:
408                 case 0xe1:
409                 case 0xe2:
410                 case 0xe3:
411                 case 0xe4:
412                 case 0xe5:
413                 case 0xe6:
414                 case 0xe7:
415                 case 0xe8:
416                 case 0xe9:
417                 case 0xea:
418                 case 0xeb:
419                 case 0xec:
420                 case 0xed:
421                 case 0xee:
422                 case 0xef:
423                         /* APP0 through APPF */
424                 case 0xdb:
425                         /* DQT */
426                 case 0xc0:
427                         /* SOF0 (baseline DCT, Huffman encoded) */
428                         copy_segment(m2);
429                         break;
430                 case 0xd8:
431                         /* SOI */
432                         putchar(m1);
433                         putchar(m2);
434                         break;
435                 case 0xc4:
436                         /* DHT (define Huffman tables) */
437                         read_huffman_tables();
438                         break;
439                 case 0xda:
440                         /* SOS (start of scan) */
441                         read_scan();
442                         break;
443                 default:
444                         fprintf(stderr, "Error: Unknown marker 0x%02x\n", m2);
445                         exit(1);
446                 }
447         }
448 }