1/**********
2This library is free software; you can redistribute it and/or modify it under
3the terms of the GNU Lesser General Public License as published by the
4Free Software Foundation; either version 3 of the License, or (at your
5option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)
6
7This library is distributed in the hope that it will be useful, but WITHOUT
8ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
9FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
10more details.
11
12You should have received a copy of the GNU Lesser General Public License
13along with this library; if not, write to the Free Software Foundation, Inc.,
1451 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
15**********/
16// "liveMedia"
17// Copyright (c) 1996-2020 Live Networks, Inc. All rights reserved.
18// MP3 internal implementation details (Huffman encoding)
19// Implementation
20
21#include "MP3InternalsHuffman.hh"
22#include <stdio.h>
23#include <string.h>
24#include <stdlib.h>
25
26MP3HuffmanEncodingInfo
27::MP3HuffmanEncodingInfo(Boolean includeDecodedValues) {
28 if (includeDecodedValues) {
29 decodedValues = new unsigned[(SBLIMIT*SSLIMIT + 1)*4];
30 } else {
31 decodedValues = NULL;
32 }
33}
34
35MP3HuffmanEncodingInfo::~MP3HuffmanEncodingInfo() {
36 delete[] decodedValues;
37}
38
39// This is crufty old code that needs to be cleaned up #####
40
41static unsigned debugCount = 0; /* for debugging */
42
43#define TRUNC_FAVORa
44
45void updateSideInfoForHuffman(MP3SideInfo& sideInfo, Boolean isMPEG2,
46 unsigned char const* mainDataPtr,
47 unsigned p23L0, unsigned p23L1,
48 unsigned& part23Length0a,
49 unsigned& part23Length0aTruncation,
50 unsigned& part23Length0b,
51 unsigned& part23Length0bTruncation,
52 unsigned& part23Length1a,
53 unsigned& part23Length1aTruncation,
54 unsigned& part23Length1b,
55 unsigned& part23Length1bTruncation) {
56 int i, j;
57 unsigned sfLength, origTotABsize, adjustment;
58 MP3SideInfo::gr_info_s_t* gr;
59
60 /* First, Huffman-decode each part of the segment's main data,
61 to see at which bit-boundaries the samples appear:
62 */
63 MP3HuffmanEncodingInfo hei;
64
65 ++debugCount;
66#ifdef DEBUG
67 fprintf(stderr, "usifh-start: p23L0: %d, p23L1: %d\n", p23L0, p23L1);
68#endif
69
70 /* Process granule 0 */
71 {
72 gr = &(sideInfo.ch[0].gr[0]);
73 origTotABsize = gr->part2_3_length;
74
75 MP3HuffmanDecode(gr, isMPEG2, mainDataPtr, 0, origTotABsize, sfLength, hei);
76
77 /* Begin by computing new sizes for parts a & b (& their truncations) */
78#ifdef DEBUG
79 fprintf(stderr, "usifh-0: %d, %d:%d, %d:%d, %d:%d, %d:%d, %d:%d\n",
80 hei.numSamples,
81 sfLength/8, sfLength%8,
82 hei.reg1Start/8, hei.reg1Start%8,
83 hei.reg2Start/8, hei.reg2Start%8,
84 hei.bigvalStart/8, hei.bigvalStart%8,
85 origTotABsize/8, origTotABsize%8);
86#endif
87 if (p23L0 < sfLength) {
88 /* We can't use this, so give it all to the next granule: */
89 p23L1 += p23L0;
90 p23L0 = 0;
91 }
92
93 part23Length0a = hei.bigvalStart;
94 part23Length0b = origTotABsize - hei.bigvalStart;
95 part23Length0aTruncation = part23Length0bTruncation = 0;
96 if (origTotABsize > p23L0) {
97 /* We need to shorten one or both of fields a & b */
98 unsigned truncation = origTotABsize - p23L0;
99#ifdef TRUNC_FAIRLY
100 part23Length0aTruncation = (truncation*(part23Length0a-sfLength))
101 /(origTotABsize-sfLength);
102 part23Length0bTruncation = truncation - part23Length0aTruncation;
103#endif
104#ifdef TRUNC_FAVORa
105 part23Length0bTruncation
106 = (truncation > part23Length0b) ? part23Length0b : truncation;
107 part23Length0aTruncation = truncation - part23Length0bTruncation;
108#endif
109#ifdef TRUNC_FAVORb
110 part23Length0aTruncation = (truncation > part23Length0a-sfLength)
111 ? (part23Length0a-sfLength) : truncation;
112 part23Length0bTruncation = truncation - part23Length0aTruncation;
113#endif
114 }
115 /* ASSERT: part23Length0xTruncation <= part23Length0x */
116 part23Length0a -= part23Length0aTruncation;
117 part23Length0b -= part23Length0bTruncation;
118#ifdef DEBUG
119 fprintf(stderr, "usifh-0: interim sizes: %d (%d), %d (%d)\n",
120 part23Length0a, part23Length0aTruncation,
121 part23Length0b, part23Length0bTruncation);
122#endif
123
124 /* Adjust these new lengths so they end on sample bit boundaries: */
125 for (i = 0; i < (int)hei.numSamples; ++i) {
126 if (hei.allBitOffsets[i] == part23Length0a) break;
127 else if (hei.allBitOffsets[i] > part23Length0a) {--i; break;}
128 }
129 if (i < 0) { /* should happen only if we couldn't fit sfLength */
130 i = 0; adjustment = 0;
131 } else {
132 adjustment = part23Length0a - hei.allBitOffsets[i];
133 }
134#ifdef DEBUG
135 fprintf(stderr, "%d usifh-0: adjustment 1: %d\n", debugCount, adjustment);
136#endif
137 part23Length0a -= adjustment;
138 part23Length0aTruncation += adjustment;
139 /* Assign the bits we just shaved to field b and granule 1: */
140 if (part23Length0bTruncation < adjustment) {
141 p23L1 += (adjustment - part23Length0bTruncation);
142 adjustment = part23Length0bTruncation;
143 }
144 part23Length0b += adjustment;
145 part23Length0bTruncation -= adjustment;
146 for (j = i; j < (int)hei.numSamples; ++j) {
147 if (hei.allBitOffsets[j]
148 == part23Length0a + part23Length0aTruncation + part23Length0b)
149 break;
150 else if (hei.allBitOffsets[j]
151 > part23Length0a + part23Length0aTruncation + part23Length0b)
152 {--j; break;}
153 }
154 if (j < 0) { /* should happen only if we couldn't fit sfLength */
155 j = 0; adjustment = 0;
156 } else {
157 adjustment = part23Length0a+part23Length0aTruncation+part23Length0b
158 - hei.allBitOffsets[j];
159 }
160#ifdef DEBUG
161 fprintf(stderr, "%d usifh-0: adjustment 2: %d\n", debugCount, adjustment);
162#endif
163 if (adjustment > part23Length0b) adjustment = part23Length0b; /*sanity*/
164 part23Length0b -= adjustment;
165 part23Length0bTruncation += adjustment;
166 /* Assign the bits we just shaved to granule 1 */
167 p23L1 += adjustment;
168
169 if (part23Length0aTruncation > 0) {
170 /* Change the granule's 'big_values' field to reflect the truncation */
171 gr->big_values = i;
172 }
173 }
174
175 /* Process granule 1 (MPEG-1 only) */
176
177 if (isMPEG2) {
178 part23Length1a = part23Length1b = 0;
179 part23Length1aTruncation = part23Length1bTruncation = 0;
180 } else {
181 unsigned granule1Offset
182 = origTotABsize + sideInfo.ch[1].gr[0].part2_3_length;
183
184 gr = &(sideInfo.ch[0].gr[1]);
185 origTotABsize = gr->part2_3_length;
186
187 MP3HuffmanDecode(gr, isMPEG2, mainDataPtr, granule1Offset,
188 origTotABsize, sfLength, hei);
189
190 /* Begin by computing new sizes for parts a & b (& their truncations) */
191#ifdef DEBUG
192 fprintf(stderr, "usifh-1: %d, %d:%d, %d:%d, %d:%d, %d:%d, %d:%d\n",
193 hei.numSamples,
194 sfLength/8, sfLength%8,
195 hei.reg1Start/8, hei.reg1Start%8,
196 hei.reg2Start/8, hei.reg2Start%8,
197 hei.bigvalStart/8, hei.bigvalStart%8,
198 origTotABsize/8, origTotABsize%8);
199#endif
200 if (p23L1 < sfLength) {
201 /* We can't use this, so give up on this granule: */
202 p23L1 = 0;
203 }
204
205 part23Length1a = hei.bigvalStart;
206 part23Length1b = origTotABsize - hei.bigvalStart;
207 part23Length1aTruncation = part23Length1bTruncation = 0;
208 if (origTotABsize > p23L1) {
209 /* We need to shorten one or both of fields a & b */
210 unsigned truncation = origTotABsize - p23L1;
211#ifdef TRUNC_FAIRLY
212 part23Length1aTruncation = (truncation*(part23Length1a-sfLength))
213 /(origTotABsize-sfLength);
214 part23Length1bTruncation = truncation - part23Length1aTruncation;
215#endif
216#ifdef TRUNC_FAVORa
217 part23Length1bTruncation
218 = (truncation > part23Length1b) ? part23Length1b : truncation;
219 part23Length1aTruncation = truncation - part23Length1bTruncation;
220#endif
221#ifdef TRUNC_FAVORb
222 part23Length1aTruncation = (truncation > part23Length1a-sfLength)
223 ? (part23Length1a-sfLength) : truncation;
224 part23Length1bTruncation = truncation - part23Length1aTruncation;
225#endif
226 }
227 /* ASSERT: part23Length1xTruncation <= part23Length1x */
228 part23Length1a -= part23Length1aTruncation;
229 part23Length1b -= part23Length1bTruncation;
230#ifdef DEBUG
231 fprintf(stderr, "usifh-1: interim sizes: %d (%d), %d (%d)\n",
232 part23Length1a, part23Length1aTruncation,
233 part23Length1b, part23Length1bTruncation);
234#endif
235
236 /* Adjust these new lengths so they end on sample bit boundaries: */
237 for (i = 0; i < (int)hei.numSamples; ++i) {
238 if (hei.allBitOffsets[i] == part23Length1a) break;
239 else if (hei.allBitOffsets[i] > part23Length1a) {--i; break;}
240 }
241 if (i < 0) { /* should happen only if we couldn't fit sfLength */
242 i = 0; adjustment = 0;
243 } else {
244 adjustment = part23Length1a - hei.allBitOffsets[i];
245 }
246#ifdef DEBUG
247 fprintf(stderr, "%d usifh-1: adjustment 0: %d\n", debugCount, adjustment);
248#endif
249 part23Length1a -= adjustment;
250 part23Length1aTruncation += adjustment;
251 /* Assign the bits we just shaved to field b: */
252 if (part23Length1bTruncation < adjustment) {
253 adjustment = part23Length1bTruncation;
254 }
255 part23Length1b += adjustment;
256 part23Length1bTruncation -= adjustment;
257 for (j = i; j < (int)hei.numSamples; ++j) {
258 if (hei.allBitOffsets[j]
259 == part23Length1a + part23Length1aTruncation + part23Length1b)
260 break;
261 else if (hei.allBitOffsets[j]
262 > part23Length1a + part23Length1aTruncation + part23Length1b)
263 {--j; break;}
264 }
265 if (j < 0) { /* should happen only if we couldn't fit sfLength */
266 j = 0; adjustment = 0;
267 } else {
268 adjustment = part23Length1a+part23Length1aTruncation+part23Length1b
269 - hei.allBitOffsets[j];
270 }
271#ifdef DEBUG
272 fprintf(stderr, "%d usifh-1: adjustment 1: %d\n", debugCount, adjustment);
273#endif
274 if (adjustment > part23Length1b) adjustment = part23Length1b; /*sanity*/
275 part23Length1b -= adjustment;
276 part23Length1bTruncation += adjustment;
277
278 if (part23Length1aTruncation > 0) {
279 /* Change the granule's 'big_values' field to reflect the truncation */
280 gr->big_values = i;
281 }
282 }
283#ifdef DEBUG
284 fprintf(stderr, "usifh-end, new vals: %d (%d), %d (%d), %d (%d), %d (%d)\n",
285 part23Length0a, part23Length0aTruncation,
286 part23Length0b, part23Length0bTruncation,
287 part23Length1a, part23Length1aTruncation,
288 part23Length1b, part23Length1bTruncation);
289#endif
290}
291
292static void rsf_getline(char* line, unsigned max, unsigned char**fi) {
293 unsigned i;
294 for (i = 0; i < max; ++i) {
295 line[i] = *(*fi)++;
296 if (line[i] == '\n') {
297 line[i++] = '\0';
298 return;
299 }
300 }
301 line[i] = '\0';
302}
303
304static void rsfscanf(unsigned char **fi, unsigned int* v) {
305 while (sscanf((char*)*fi, "%x", v) == 0) {
306 /* skip past the next '\0' */
307 while (*(*fi)++ != '\0') {}
308 }
309
310 /* skip past any white-space before the value: */
311 while (*(*fi) <= ' ') ++(*fi);
312
313 /* skip past the value: */
314 while (*(*fi) > ' ') ++(*fi);
315}
316
317#define HUFFBITS unsigned long int
318#define SIZEOF_HUFFBITS 4
319#define HTN 34
320#define MXOFF 250
321
322struct huffcodetab {
323 char tablename[3]; /*string, containing table_description */
324 unsigned int xlen; /*max. x-index+ */
325 unsigned int ylen; /*max. y-index+ */
326 unsigned int linbits; /*number of linbits */
327 unsigned int linmax; /*max number to be stored in linbits */
328 int ref; /*a positive value indicates a reference*/
329 HUFFBITS *table; /*pointer to array[xlen][ylen] */
330 unsigned char *hlen; /*pointer to array[xlen][ylen] */
331 unsigned char(*val)[2];/*decoder tree */
332 unsigned int treelen; /*length of decoder tree */
333};
334
335static struct huffcodetab rsf_ht[HTN]; // array of all huffcodetable headers
336 /* 0..31 Huffman code table 0..31 */
337 /* 32,33 count1-tables */
338
339/* read the huffman decoder table */
340static int read_decoder_table(unsigned char* fi) {
341 int n,i,nn,t;
342 unsigned int v0,v1;
343 char command[100],line[100];
344 for (n=0;n<HTN;n++) {
345 rsf_ht[n].table = NULL;
346 rsf_ht[n].hlen = NULL;
347
348 /* .table number treelen xlen ylen linbits */
349 do {
350 rsf_getline(line,99,&fi);
351 } while ((line[0] == '#') || (line[0] < ' '));
352
353 sscanf(line,"%s %s %u %u %u %u",command,rsf_ht[n].tablename,
354 &rsf_ht[n].treelen, &rsf_ht[n].xlen, &rsf_ht[n].ylen, &rsf_ht[n].linbits);
355 if (strcmp(command,".end")==0)
356 return n;
357 else if (strcmp(command,".table")!=0) {
358#ifdef DEBUG
359 fprintf(stderr,"huffman table %u data corrupted\n",n);
360#endif
361 return -1;
362 }
363 rsf_ht[n].linmax = (1<<rsf_ht[n].linbits)-1;
364
365 sscanf(rsf_ht[n].tablename,"%u",&nn);
366 if (nn != n) {
367#ifdef DEBUG
368 fprintf(stderr,"wrong table number %u\n",n);
369#endif
370 return(-2);
371 }
372 do {
373 rsf_getline(line,99,&fi);
374 } while ((line[0] == '#') || (line[0] < ' '));
375
376 sscanf(line,"%s %u",command,&t);
377 if (strcmp(command,".reference")==0) {
378 rsf_ht[n].ref = t;
379 rsf_ht[n].val = rsf_ht[t].val;
380 rsf_ht[n].treelen = rsf_ht[t].treelen;
381 if ( (rsf_ht[n].xlen != rsf_ht[t].xlen) ||
382 (rsf_ht[n].ylen != rsf_ht[t].ylen) ) {
383#ifdef DEBUG
384 fprintf(stderr,"wrong table %u reference\n",n);
385#endif
386 return (-3);
387 };
388 while ((line[0] == '#') || (line[0] < ' ') ) {
389 rsf_getline(line,99,&fi);
390 }
391 }
392 else if (strcmp(command,".treedata")==0) {
393 rsf_ht[n].ref = -1;
394 rsf_ht[n].val = (unsigned char (*)[2])
395 new unsigned char[2*(rsf_ht[n].treelen)];
396 if ((rsf_ht[n].val == NULL) && ( rsf_ht[n].treelen != 0 )){
397#ifdef DEBUG
398 fprintf(stderr, "heaperror at table %d\n",n);
399#endif
400 return -1;
401 }
402 for (i=0;(unsigned)i<rsf_ht[n].treelen; i++) {
403 rsfscanf(&fi, &v0);
404 rsfscanf(&fi, &v1);
405/*replaces fscanf(fi,"%x %x",&v0, &v1);*/
406 rsf_ht[n].val[i][0]=(unsigned char)v0;
407 rsf_ht[n].val[i][1]=(unsigned char)v1;
408 }
409 rsf_getline(line,99,&fi); /* read the rest of the line */
410 }
411 else {
412#ifdef DEBUG
413 fprintf(stderr,"huffman decodertable error at table %d\n",n);
414#endif
415 }
416 }
417 return n;
418}
419
420static void initialize_huffman() {
421 static Boolean huffman_initialized = False;
422
423 if (huffman_initialized) return;
424
425 if (read_decoder_table(huffdec) != HTN) {
426#ifdef DEBUG
427 fprintf(stderr,"decoder table read error\n");
428#endif
429 return;
430 }
431 huffman_initialized = True;
432}
433
434static unsigned char const slen[2][16] = {
435 {0, 0, 0, 0, 3, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4},
436 {0, 1, 2, 3, 0, 1, 2, 3, 1, 2, 3, 1, 2, 3, 2, 3}
437};
438
439static unsigned char const stab[3][6][4] = {
440 { { 6, 5, 5,5 } , { 6, 5, 7,3 } , { 11,10,0,0} ,
441 { 7, 7, 7,0 } , { 6, 6, 6,3 } , { 8, 8,5,0} } ,
442 { { 9, 9, 9,9 } , { 9, 9,12,6 } , { 18,18,0,0} ,
443 {12,12,12,0 } , {12, 9, 9,6 } , { 15,12,9,0} } ,
444 { { 6, 9, 9,9 } , { 6, 9,12,6 } , { 15,18,0,0} ,
445 { 6,15,12,0 } , { 6,12, 9,6 } , { 6,18,9,0} }
446};
447
448static unsigned rsf_get_scale_factors_1(MP3SideInfo::gr_info_s_t *gr_info) {
449 int numbits;
450 int num0 = slen[0][gr_info->scalefac_compress];
451 int num1 = slen[1][gr_info->scalefac_compress];
452
453 if (gr_info->block_type == 2)
454 {
455 numbits = (num0 + num1) * 18;
456
457 if (gr_info->mixed_block_flag) {
458 numbits -= num0; /* num0 * 17 + num1 * 18 */
459 }
460 }
461 else
462 {
463 int scfsi = gr_info->scfsi;
464
465 if(scfsi < 0) { /* scfsi < 0 => granule == 0 */
466 numbits = (num0 + num1) * 10 + num0;
467 }
468 else {
469 numbits = 0;
470 if(!(scfsi & 0x8)) {
471 numbits += num0 * 6;
472 }
473 else {
474 }
475
476 if(!(scfsi & 0x4)) {
477 numbits += num0 * 5;
478 }
479 else {
480 }
481
482 if(!(scfsi & 0x2)) {
483 numbits += num1 * 5;
484 }
485 else {
486 }
487
488 if(!(scfsi & 0x1)) {
489 numbits += num1 * 5;
490 }
491 else {
492 }
493 }
494 }
495
496 return numbits;
497}
498
499extern unsigned n_slen2[];
500extern unsigned i_slen2[];
501
502static unsigned rsf_get_scale_factors_2(MP3SideInfo::gr_info_s_t *gr_info) {
503 unsigned char const* pnt;
504 int i;
505 unsigned int slen;
506 int n = 0;
507 int numbits = 0;
508
509 slen = n_slen2[gr_info->scalefac_compress];
510
511 gr_info->preflag = (slen>>15) & 0x1;
512
513 n = 0;
514 if( gr_info->block_type == 2 ) {
515 n++;
516 if(gr_info->mixed_block_flag)
517 n++;
518 }
519
520 pnt = stab[n][(slen>>12)&0x7];
521
522 for(i=0;i<4;i++) {
523 int num = slen & 0x7;
524 slen >>= 3;
525 numbits += pnt[i] * num;
526 }
527
528 return numbits;
529}
530
531static unsigned getScaleFactorsLength(MP3SideInfo::gr_info_s_t* gr,
532 Boolean isMPEG2) {
533 return isMPEG2 ? rsf_get_scale_factors_2(gr)
534 : rsf_get_scale_factors_1(gr);
535}
536
537static int rsf_huffman_decoder(BitVector& bv,
538 struct huffcodetab const* h,
539 int* x, int* y, int* v, int* w); // forward
540
541void MP3HuffmanDecode(MP3SideInfo::gr_info_s_t* gr, Boolean isMPEG2,
542 unsigned char const* fromBasePtr,
543 unsigned fromBitOffset, unsigned fromLength,
544 unsigned& scaleFactorsLength,
545 MP3HuffmanEncodingInfo& hei) {
546 unsigned i;
547 int x, y, v, w;
548 struct huffcodetab *h;
549 BitVector bv((unsigned char*)fromBasePtr, fromBitOffset, fromLength);
550
551 /* Compute the size of the scale factors (& also advance bv): */
552 scaleFactorsLength = getScaleFactorsLength(gr, isMPEG2);
553 bv.skipBits(scaleFactorsLength);
554
555 initialize_huffman();
556
557 hei.reg1Start = hei.reg2Start = hei.numSamples = 0;
558
559 /* Read bigvalues area. */
560 if (gr->big_values < gr->region1start + gr->region2start) {
561 gr->big_values = gr->region1start + gr->region2start; /* sanity check */
562 }
563 for (i = 0; i < gr->big_values; ++i) {
564 if (i < gr->region1start) {
565 /* in region 0 */
566 h = &rsf_ht[gr->table_select[0]];
567 } else if (i < gr->region2start) {
568 /* in region 1 */
569 h = &rsf_ht[gr->table_select[1]];
570 if (hei.reg1Start == 0) {
571 hei.reg1Start = bv.curBitIndex();
572 }
573 } else {
574 /* in region 2 */
575 h = &rsf_ht[gr->table_select[2]];
576 if (hei.reg2Start == 0) {
577 hei.reg2Start = bv.curBitIndex();
578 }
579 }
580
581 hei.allBitOffsets[i] = bv.curBitIndex();
582 rsf_huffman_decoder(bv, h, &x, &y, &v, &w);
583 if (hei.decodedValues != NULL) {
584 // Record the decoded values:
585 unsigned* ptr = &hei.decodedValues[4*i];
586 ptr[0] = x; ptr[1] = y; ptr[2] = v; ptr[3] = w;
587 }
588 }
589 hei.bigvalStart = bv.curBitIndex();
590
591 /* Read count1 area. */
592 h = &rsf_ht[gr->count1table_select+32];
593 while (bv.curBitIndex() < bv.totNumBits() && i < SSLIMIT*SBLIMIT) {
594 hei.allBitOffsets[i] = bv.curBitIndex();
595 rsf_huffman_decoder(bv, h, &x, &y, &v, &w);
596 if (hei.decodedValues != NULL) {
597 // Record the decoded values:
598 unsigned* ptr = &hei.decodedValues[4*i];
599 ptr[0] = x; ptr[1] = y; ptr[2] = v; ptr[3] = w;
600 }
601 ++i;
602 }
603
604 hei.allBitOffsets[i] = bv.curBitIndex();
605 hei.numSamples = i;
606}
607
608HUFFBITS dmask = 1 << (SIZEOF_HUFFBITS*8-1);
609unsigned int hs = SIZEOF_HUFFBITS*8;
610
611/* do the huffman-decoding */
612static int rsf_huffman_decoder(BitVector& bv,
613 struct huffcodetab const* h, // ptr to huffman code record
614 /* unsigned */ int *x, // returns decoded x value
615 /* unsigned */ int *y, // returns decoded y value
616 int* v, int* w) {
617 HUFFBITS level;
618 unsigned point = 0;
619 int error = 1;
620 level = dmask;
621 *x = *y = *v = *w = 0;
622 if (h->val == NULL) return 2;
623
624 /* table 0 needs no bits */
625 if (h->treelen == 0) return 0;
626
627 /* Lookup in Huffman table. */
628
629 do {
630 if (h->val[point][0]==0) { /*end of tree*/
631 *x = h->val[point][1] >> 4;
632 *y = h->val[point][1] & 0xf;
633
634 error = 0;
635 break;
636 }
637 if (bv.get1Bit()) {
638 while (h->val[point][1] >= MXOFF) point += h->val[point][1];
639 point += h->val[point][1];
640 }
641 else {
642 while (h->val[point][0] >= MXOFF) point += h->val[point][0];
643 point += h->val[point][0];
644 }
645 level >>= 1;
646 } while (level || (point < h->treelen) );
647///// } while (level || (point < rsf_ht->treelen) );
648
649 /* Check for error. */
650
651 if (error) { /* set x and y to a medium value as a simple concealment */
652 printf("Illegal Huffman code in data.\n");
653 *x = ((h->xlen-1) << 1);
654 *y = ((h->ylen-1) << 1);
655 }
656
657 /* Process sign encodings for quadruples tables. */
658
659 if (h->tablename[0] == '3'
660 && (h->tablename[1] == '2' || h->tablename[1] == '3')) {
661 *v = (*y>>3) & 1;
662 *w = (*y>>2) & 1;
663 *x = (*y>>1) & 1;
664 *y = *y & 1;
665
666 if (*v)
667 if (bv.get1Bit() == 1) *v = -*v;
668 if (*w)
669 if (bv.get1Bit() == 1) *w = -*w;
670 if (*x)
671 if (bv.get1Bit() == 1) *x = -*x;
672 if (*y)
673 if (bv.get1Bit() == 1) *y = -*y;
674 }
675
676 /* Process sign and escape encodings for dual tables. */
677
678 else {
679 if (h->linbits)
680 if ((h->xlen-1) == (unsigned)*x)
681 *x += bv.getBits(h->linbits);
682 if (*x)
683 if (bv.get1Bit() == 1) *x = -*x;
684 if (h->linbits)
685 if ((h->ylen-1) == (unsigned)*y)
686 *y += bv.getBits(h->linbits);
687 if (*y)
688 if (bv.get1Bit() == 1) *y = -*y;
689 }
690
691 return error;
692}
693
694#ifdef DO_HUFFMAN_ENCODING
695inline int getNextSample(unsigned char const*& fromPtr) {
696 int sample
697#ifdef FOUR_BYTE_SAMPLES
698 = (fromPtr[0]<<24) | (fromPtr[1]<<16) | (fromPtr[2]<<8) | fromPtr[3];
699#else
700#ifdef TWO_BYTE_SAMPLES
701 = (fromPtr[0]<<8) | fromPtr[1];
702#else
703 // ONE_BYTE_SAMPLES
704 = fromPtr[0];
705#endif
706#endif
707 fromPtr += BYTES_PER_SAMPLE_VALUE;
708 return sample;
709}
710
711static void rsf_huffman_encoder(BitVector& bv,
712 struct huffcodetab* h,
713 int x, int y, int v, int w); // forward
714
715unsigned MP3HuffmanEncode(MP3SideInfo::gr_info_s_t const* gr,
716 unsigned char const* fromPtr,
717 unsigned char* toPtr, unsigned toBitOffset,
718 unsigned numHuffBits) {
719 unsigned i;
720 struct huffcodetab *h;
721 int x, y, v, w;
722 BitVector bv(toPtr, toBitOffset, numHuffBits);
723
724 initialize_huffman();
725
726 // Encode big_values area:
727 unsigned big_values = gr->big_values;
728 if (big_values < gr->region1start + gr->region2start) {
729 big_values = gr->region1start + gr->region2start; /* sanity check */
730 }
731 for (i = 0; i < big_values; ++i) {
732 if (i < gr->region1start) {
733 /* in region 0 */
734 h = &rsf_ht[gr->table_select[0]];
735 } else if (i < gr->region2start) {
736 /* in region 1 */
737 h = &rsf_ht[gr->table_select[1]];
738 } else {
739 /* in region 2 */
740 h = &rsf_ht[gr->table_select[2]];
741 }
742
743 x = getNextSample(fromPtr);
744 y = getNextSample(fromPtr);
745 v = getNextSample(fromPtr);
746 w = getNextSample(fromPtr);
747 rsf_huffman_encoder(bv, h, x, y, v, w);
748 }
749
750 // Encode count1 area:
751 h = &rsf_ht[gr->count1table_select+32];
752 while (bv.curBitIndex() < bv.totNumBits() && i < SSLIMIT*SBLIMIT) {
753 x = getNextSample(fromPtr);
754 y = getNextSample(fromPtr);
755 v = getNextSample(fromPtr);
756 w = getNextSample(fromPtr);
757 rsf_huffman_encoder(bv, h, x, y, v, w);
758 ++i;
759 }
760
761 return i;
762}
763
764static Boolean lookupHuffmanTableEntry(struct huffcodetab const* h,
765 HUFFBITS bits, unsigned bitsLength,
766 unsigned char& xy) {
767 unsigned point = 0;
768 unsigned mask = 1;
769 unsigned numBitsTestedSoFar = 0;
770 do {
771 if (h->val[point][0]==0) { // end of tree
772 xy = h->val[point][1];
773 if (h->hlen[xy] == 0) { // this entry hasn't already been used
774 h->table[xy] = bits;
775 h->hlen[xy] = bitsLength;
776 return True;
777 } else { // this entry has already been seen
778 return False;
779 }
780 }
781
782 if (numBitsTestedSoFar++ == bitsLength) {
783 // We don't yet have enough bits for this prefix
784 return False;
785 }
786 if (bits&mask) {
787 while (h->val[point][1] >= MXOFF) point += h->val[point][1];
788 point += h->val[point][1];
789 } else {
790 while (h->val[point][0] >= MXOFF) point += h->val[point][0];
791 point += h->val[point][0];
792 }
793 mask <<= 1;
794 } while (mask || (point < h->treelen));
795
796 return False;
797}
798
799static void buildHuffmanEncodingTable(struct huffcodetab* h) {
800 h->table = new unsigned long[256];
801 h->hlen = new unsigned char[256];
802 if (h->table == NULL || h->hlen == NULL) { h->table = NULL; return; }
803 for (unsigned i = 0; i < 256; ++i) {
804 h->table[i] = 0; h->hlen[i] = 0;
805 }
806
807 // Look up entries for each possible bit sequence length:
808 unsigned maxNumEntries = h->xlen * h->ylen;
809 unsigned numEntries = 0;
810 unsigned powerOf2 = 1;
811 for (unsigned bitsLength = 1;
812 bitsLength <= 8*SIZEOF_HUFFBITS; ++bitsLength) {
813 powerOf2 *= 2;
814 for (HUFFBITS bits = 0; bits < powerOf2; ++bits) {
815 // Find the table value - if any - for 'bits' (length 'bitsLength'):
816 unsigned char xy;
817 if (lookupHuffmanTableEntry(h, bits, bitsLength, xy)) {
818 ++numEntries;
819 if (numEntries == maxNumEntries) return; // we're done
820 }
821 }
822 }
823#ifdef DEBUG
824 fprintf(stderr, "Didn't find enough entries!\n"); // shouldn't happen
825#endif
826}
827
828static void lookupXYandPutBits(BitVector& bv, struct huffcodetab const* h,
829 unsigned char xy) {
830 HUFFBITS bits = h->table[xy];
831 unsigned bitsLength = h->hlen[xy];
832
833 // Note that "bits" is in reverse order, so read them from right-to-left:
834 while (bitsLength-- > 0) {
835 bv.put1Bit(bits&0x00000001);
836 bits >>= 1;
837 }
838}
839
840static void putLinbits(BitVector& bv, struct huffcodetab const* h,
841 HUFFBITS bits) {
842 bv.putBits(bits, h->linbits);
843}
844
845static void rsf_huffman_encoder(BitVector& bv,
846 struct huffcodetab* h,
847 int x, int y, int v, int w) {
848 if (h->val == NULL) return;
849
850 /* table 0 produces no bits */
851 if (h->treelen == 0) return;
852
853 if (h->table == NULL) {
854 // We haven't yet built the encoding array for this table; do it now:
855 buildHuffmanEncodingTable(h);
856 if (h->table == NULL) return;
857 }
858
859 Boolean xIsNeg = False, yIsNeg = False, vIsNeg = False, wIsNeg = False;
860 unsigned char xy;
861
862#ifdef FOUR_BYTE_SAMPLES
863#else
864#ifdef TWO_BYTE_SAMPLES
865 // Convert 2-byte negative numbers to their 4-byte equivalents:
866 if (x&0x8000) x |= 0xFFFF0000;
867 if (y&0x8000) y |= 0xFFFF0000;
868 if (v&0x8000) v |= 0xFFFF0000;
869 if (w&0x8000) w |= 0xFFFF0000;
870#else
871 // ONE_BYTE_SAMPLES
872 // Convert 1-byte negative numbers to their 4-byte equivalents:
873 if (x&0x80) x |= 0xFFFFFF00;
874 if (y&0x80) y |= 0xFFFFFF00;
875 if (v&0x80) v |= 0xFFFFFF00;
876 if (w&0x80) w |= 0xFFFFFF00;
877#endif
878#endif
879
880 if (h->tablename[0] == '3'
881 && (h->tablename[1] == '2' || h->tablename[1] == '3')) {// quad tables
882 if (x < 0) { xIsNeg = True; x = -x; }
883 if (y < 0) { yIsNeg = True; y = -y; }
884 if (v < 0) { vIsNeg = True; v = -v; }
885 if (w < 0) { wIsNeg = True; w = -w; }
886
887 // Sanity check: x,y,v,w must all be 0 or 1:
888 if (x>1 || y>1 || v>1 || w>1) {
889#ifdef DEBUG
890 fprintf(stderr, "rsf_huffman_encoder quad sanity check fails: %x,%x,%x,%x\n", x, y, v, w);
891#endif
892 }
893
894 xy = (v<<3)|(w<<2)|(x<<1)|y;
895 lookupXYandPutBits(bv, h, xy);
896
897 if (v) bv.put1Bit(vIsNeg);
898 if (w) bv.put1Bit(wIsNeg);
899 if (x) bv.put1Bit(xIsNeg);
900 if (y) bv.put1Bit(yIsNeg);
901 } else { // dual tables
902 // Sanity check: v and w must be 0:
903 if (v != 0 || w != 0) {
904#ifdef DEBUG
905 fprintf(stderr, "rsf_huffman_encoder dual sanity check 1 fails: %x,%x,%x,%x\n", x, y, v, w);
906#endif
907 }
908
909 if (x < 0) { xIsNeg = True; x = -x; }
910 if (y < 0) { yIsNeg = True; y = -y; }
911
912 // Sanity check: x and y must be <= 255:
913 if (x > 255 || y > 255) {
914#ifdef DEBUG
915 fprintf(stderr, "rsf_huffman_encoder dual sanity check 2 fails: %x,%x,%x,%x\n", x, y, v, w);
916#endif
917 }
918
919 int xl1 = h->xlen-1;
920 int yl1 = h->ylen-1;
921 unsigned linbitsX = 0; unsigned linbitsY = 0;
922
923 if (((x < xl1) || (xl1 == 0)) && (y < yl1)) {
924 // normal case
925 xy = (x<<4)|y;
926 lookupXYandPutBits(bv, h, xy);
927 if (x) bv.put1Bit(xIsNeg);
928 if (y) bv.put1Bit(yIsNeg);
929 } else if (x >= xl1) {
930 linbitsX = (unsigned)(x - xl1);
931 if (linbitsX > h->linmax) {
932#ifdef DEBUG
933 fprintf(stderr,"warning: Huffman X table overflow\n");
934#endif
935 linbitsX = h->linmax;
936 };
937
938 if (y >= yl1) {
939 xy = (xl1<<4)|yl1;
940 lookupXYandPutBits(bv, h, xy);
941 linbitsY = (unsigned)(y - yl1);
942 if (linbitsY > h->linmax) {
943#ifdef DEBUG
944 fprintf(stderr,"warning: Huffman Y table overflow\n");
945#endif
946 linbitsY = h->linmax;
947 };
948
949 if (h->linbits) putLinbits(bv, h, linbitsX);
950 if (x) bv.put1Bit(xIsNeg);
951 if (h->linbits) putLinbits(bv, h, linbitsY);
952 if (y) bv.put1Bit(yIsNeg);
953 } else { /* x >= h->xlen, y < h->ylen */
954 xy = (xl1<<4)|y;
955 lookupXYandPutBits(bv, h, xy);
956 if (h->linbits) putLinbits(bv, h, linbitsX);
957 if (x) bv.put1Bit(xIsNeg);
958 if (y) bv.put1Bit(yIsNeg);
959 }
960 } else { /* ((x < h->xlen) && (y >= h->ylen)) */
961 xy = (x<<4)|yl1;
962 lookupXYandPutBits(bv, h, xy);
963 linbitsY = y-yl1;
964 if (linbitsY > h->linmax) {
965#ifdef DEBUG
966 fprintf(stderr,"warning: Huffman Y table overflow\n");
967#endif
968 linbitsY = h->linmax;
969 };
970 if (x) bv.put1Bit(xIsNeg);
971 if (h->linbits) putLinbits(bv, h, linbitsY);
972 if (y) bv.put1Bit(yIsNeg);
973 }
974 }
975}
976#endif
977