huffman.cpp
1 /* ***** BEGIN LICENSE BLOCK ***** 2 * Version: RCSL 1.0/RPSL 1.0 3 * 4 * Portions Copyright (c) 1995-2002 RealNetworks, Inc. All Rights Reserved. 5 * 6 * The contents of this file, and the files included with this file, are 7 * subject to the current version of the RealNetworks Public Source License 8 * Version 1.0 (the "RPSL") available at 9 * http://www.helixcommunity.org/content/rpsl unless you have licensed 10 * the file under the RealNetworks Community Source License Version 1.0 11 * (the "RCSL") available at http://www.helixcommunity.org/content/rcsl, 12 * in which case the RCSL will apply. You may also obtain the license terms 13 * directly from RealNetworks. You may not use this file except in 14 * compliance with the RPSL or, if you have a valid RCSL with RealNetworks 15 * applicable to this file, the RCSL. Please see the applicable RPSL or 16 * RCSL for the rights, obligations and limitations governing use of the 17 * contents of the file. 18 * 19 * This file is part of the Helix DNA Technology. RealNetworks is the 20 * developer of the Original Code and owns the copyrights in the portions 21 * it created. 22 * 23 * This file, and the files included with this file, is distributed and made 24 * available on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 25 * EXPRESS OR IMPLIED, AND REALNETWORKS HEREBY DISCLAIMS ALL SUCH WARRANTIES, 26 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS 27 * FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 28 * 29 * Technology Compatibility Kit Test Suite(s) Location: 30 * http://www.helixcommunity.org/content/tck 31 * 32 * Contributor(s): 33 * 34 * ***** END LICENSE BLOCK ***** */ 35 36 /************************************************************************************** 37 * Fixed-point MP3 decoder 38 * Jon Recker (jrecker@real.com), Ken Cooke (kenc@real.com) 39 * July 2003 40 * 41 * huffman.c - Huffman decoding of transform coefficients 42 **************************************************************************************/ 43 44 #include "coder.h" 45 46 #include <stdio.h> 47 48 /* helper macros - see comments in hufftabs.c about the format of the huffman tables */ 49 #define GetMaxbits(x) ((int)( (((unsigned short)(x)) >> 0) & 0x000f)) 50 #define GetHLen(x) ((int)( (((unsigned short)(x)) >> 12) & 0x000f)) 51 #define GetCWY(x) ((int)( (((unsigned short)(x)) >> 8) & 0x000f)) 52 #define GetCWX(x) ((int)( (((unsigned short)(x)) >> 4) & 0x000f)) 53 #define GetSignBits(x) ((int)( (((unsigned short)(x)) >> 0) & 0x000f)) 54 55 #define GetHLenQ(x) ((int)( (((unsigned char)(x)) >> 4) & 0x0f)) 56 #define GetCWVQ(x) ((int)( (((unsigned char)(x)) >> 3) & 0x01)) 57 #define GetCWWQ(x) ((int)( (((unsigned char)(x)) >> 2) & 0x01)) 58 #define GetCWXQ(x) ((int)( (((unsigned char)(x)) >> 1) & 0x01)) 59 #define GetCWYQ(x) ((int)( (((unsigned char)(x)) >> 0) & 0x01)) 60 61 /* apply sign of s to the positive number x (save in MSB, will do two's complement in dequant) */ 62 #define ApplySign(x, s) { (x) |= ((s) & 0x80000000); } 63 64 /************************************************************************************** 65 * Function: DecodeHuffmanPairs 66 * 67 * Description: decode 2-way vector Huffman codes in the "bigValues" region of spectrum 68 * 69 * Inputs: valid BitStreamInfo struct, pointing to start of pair-wise codes 70 * pointer to xy buffer to received decoded values 71 * number of codewords to decode 72 * index of Huffman table to use 73 * number of bits remaining in bitstream 74 * 75 * Outputs: pairs of decoded coefficients in vwxy 76 * updated BitStreamInfo struct 77 * 78 * Return: number of bits used, or -1 if out of bits 79 * 80 * Notes: assumes that nVals is an even number 81 * si_huff.bit tests every Huffman codeword in every table (though not 82 * necessarily all linBits outputs for x,y > 15) 83 **************************************************************************************/ 84 // no improvement with section=data 85 static int DecodeHuffmanPairs(int *xy, int nVals, int tabIdx, int bitsLeft, unsigned char *buf, int bitOffset) 86 { 87 int i, x, y; 88 int cachedBits, padBits, len, startBits, linBits, maxBits, minBits; 89 HuffTabType tabType; 90 unsigned short cw, *tBase, *tCurr; 91 unsigned int cache; 92 93 if(nVals <= 0) 94 return 0; 95 96 if (bitsLeft < 0) 97 return -1; 98 startBits = bitsLeft; 99 100 tBase = (unsigned short *)(huffTable + huffTabOffset[tabIdx]); 101 linBits = huffTabLookup[tabIdx].linBits; 102 tabType = huffTabLookup[tabIdx].tabType; 103 104 ASSERT(!(nVals & 0x01)); 105 ASSERT(tabIdx < HUFF_PAIRTABS); 106 ASSERT(tabIdx >= 0); 107 ASSERT(tabType != invalidTab); 108 109 /* initially fill cache with any partial byte */ 110 cache = 0; 111 cachedBits = (8 - bitOffset) & 0x07; 112 if (cachedBits) 113 cache = (unsigned int)(*buf++) << (32 - cachedBits); 114 bitsLeft -= cachedBits; 115 116 if (tabType == noBits) { 117 /* table 0, no data, x = y = 0 */ 118 for (i = 0; i < nVals; i+=2) { 119 xy[i+0] = 0; 120 xy[i+1] = 0; 121 } 122 return 0; 123 } else if (tabType == oneShot) { 124 /* single lookup, no escapes */ 125 maxBits = GetMaxbits(tBase[0]); 126 tBase++; 127 padBits = 0; 128 while (nVals > 0) { 129 /* refill cache - assumes cachedBits <= 16 */ 130 if (bitsLeft >= 16) { 131 /* load 2 new bytes into left-justified cache */ 132 cache |= (unsigned int)(*buf++) << (24 - cachedBits); 133 cache |= (unsigned int)(*buf++) << (16 - cachedBits); 134 cachedBits += 16; 135 bitsLeft -= 16; 136 } else { 137 /* last time through, pad cache with zeros and drain cache */ 138 if (cachedBits + bitsLeft <= 0) return -1; 139 if (bitsLeft > 0) cache |= (unsigned int)(*buf++) << (24 - cachedBits); 140 if (bitsLeft > 8) cache |= (unsigned int)(*buf++) << (16 - cachedBits); 141 cachedBits += bitsLeft; 142 bitsLeft = 0; 143 144 cache &= (signed int)0x80000000 >> (cachedBits - 1); 145 padBits = 11; 146 cachedBits += padBits; /* okay if this is > 32 (0's automatically shifted in from right) */ 147 } 148 149 /* largest maxBits = 9, plus 2 for sign bits, so make sure cache has at least 11 bits */ 150 while (nVals > 0 && cachedBits >= 11 ) { 151 cw = tBase[cache >> (32 - maxBits)]; 152 len = GetHLen(cw); 153 cachedBits -= len; 154 cache <<= len; 155 156 x = GetCWX(cw); if (x) {ApplySign(x, cache); cache <<= 1; cachedBits--;} 157 y = GetCWY(cw); if (y) {ApplySign(y, cache); cache <<= 1; cachedBits--;} 158 159 /* ran out of bits - should never have consumed padBits */ 160 if (cachedBits < padBits) 161 return -1; 162 163 *xy++ = x; 164 *xy++ = y; 165 nVals -= 2; 166 } 167 } 168 bitsLeft += (cachedBits - padBits); 169 return (startBits - bitsLeft); 170 } else if (tabType == loopLinbits || tabType == loopNoLinbits) { 171 tCurr = tBase; 172 padBits = 0; 173 while (nVals > 0) { 174 /* refill cache - assumes cachedBits <= 16 */ 175 if (bitsLeft >= 16) { 176 /* load 2 new bytes into left-justified cache */ 177 cache |= (unsigned int)(*buf++) << (24 - cachedBits); 178 cache |= (unsigned int)(*buf++) << (16 - cachedBits); 179 cachedBits += 16; 180 bitsLeft -= 16; 181 } else { 182 /* last time through, pad cache with zeros and drain cache */ 183 if (cachedBits + bitsLeft <= 0) return -1; 184 if (bitsLeft > 0) cache |= (unsigned int)(*buf++) << (24 - cachedBits); 185 if (bitsLeft > 8) cache |= (unsigned int)(*buf++) << (16 - cachedBits); 186 cachedBits += bitsLeft; 187 bitsLeft = 0; 188 189 cache &= (signed int)0x80000000 >> (cachedBits - 1); 190 padBits = 11; 191 cachedBits += padBits; /* okay if this is > 32 (0's automatically shifted in from right) */ 192 } 193 194 /* largest maxBits = 9, plus 2 for sign bits, so make sure cache has at least 11 bits */ 195 while (nVals > 0 && cachedBits >= 11 ) { 196 maxBits = GetMaxbits(tCurr[0]); 197 cw = tCurr[(cache >> (32 - maxBits)) + 1]; 198 len = GetHLen(cw); 199 if (!len) { 200 cachedBits -= maxBits; 201 cache <<= maxBits; 202 tCurr += cw; 203 continue; 204 } 205 cachedBits -= len; 206 cache <<= len; 207 208 x = GetCWX(cw); 209 y = GetCWY(cw); 210 211 if (x == 15 && tabType == loopLinbits) { 212 minBits = linBits + 1 + (y ? 1 : 0); 213 if (cachedBits + bitsLeft < minBits) 214 return -1; 215 while (cachedBits < minBits) { 216 cache |= (unsigned int)(*buf++) << (24 - cachedBits); 217 cachedBits += 8; 218 bitsLeft -= 8; 219 } 220 if (bitsLeft < 0) { 221 cachedBits += bitsLeft; 222 bitsLeft = 0; 223 cache &= (signed int)0x80000000 >> (cachedBits - 1); 224 } 225 x += (int)(cache >> (32 - linBits)); 226 cachedBits -= linBits; 227 cache <<= linBits; 228 } 229 if (x) {ApplySign(x, cache); cache <<= 1; cachedBits--;} 230 231 if (y == 15 && tabType == loopLinbits) { 232 minBits = linBits + 1; 233 if (cachedBits + bitsLeft < minBits) 234 return -1; 235 while (cachedBits < minBits) { 236 cache |= (unsigned int)(*buf++) << (24 - cachedBits); 237 cachedBits += 8; 238 bitsLeft -= 8; 239 } 240 if (bitsLeft < 0) { 241 cachedBits += bitsLeft; 242 bitsLeft = 0; 243 cache &= (signed int)0x80000000 >> (cachedBits - 1); 244 } 245 y += (int)(cache >> (32 - linBits)); 246 cachedBits -= linBits; 247 cache <<= linBits; 248 } 249 if (y) {ApplySign(y, cache); cache <<= 1; cachedBits--;} 250 251 /* ran out of bits - should never have consumed padBits */ 252 if (cachedBits < padBits) 253 return -1; 254 255 *xy++ = x; 256 *xy++ = y; 257 nVals -= 2; 258 tCurr = tBase; 259 } 260 } 261 bitsLeft += (cachedBits - padBits); 262 return (startBits - bitsLeft); 263 } 264 265 /* error in bitstream - trying to access unused Huffman table */ 266 return -1; 267 } 268 269 /************************************************************************************** 270 * Function: DecodeHuffmanQuads 271 * 272 * Description: decode 4-way vector Huffman codes in the "count1" region of spectrum 273 * 274 * Inputs: valid BitStreamInfo struct, pointing to start of quadword codes 275 * pointer to vwxy buffer to received decoded values 276 * maximum number of codewords to decode 277 * index of quadword table (0 = table A, 1 = table B) 278 * number of bits remaining in bitstream 279 * 280 * Outputs: quadruples of decoded coefficients in vwxy 281 * updated BitStreamInfo struct 282 * 283 * Return: index of the first "zero_part" value (index of the first sample 284 * of the quad word after which all samples are 0) 285 * 286 * Notes: si_huff.bit tests every vwxy output in both quad tables 287 **************************************************************************************/ 288 // no improvement with section=data 289 static int DecodeHuffmanQuads(int *vwxy, int nVals, int tabIdx, int bitsLeft, unsigned char *buf, int bitOffset) 290 { 291 int i, v, w, x, y; 292 int len, maxBits, cachedBits, padBits; 293 unsigned int cache; 294 unsigned char cw, *tBase; 295 296 if (bitsLeft <= 0) 297 return 0; 298 299 tBase = (unsigned char *)quadTable + quadTabOffset[tabIdx]; 300 maxBits = quadTabMaxBits[tabIdx]; 301 302 /* initially fill cache with any partial byte */ 303 cache = 0; 304 cachedBits = (8 - bitOffset) & 0x07; 305 if (cachedBits) 306 cache = (unsigned int)(*buf++) << (32 - cachedBits); 307 bitsLeft -= cachedBits; 308 309 i = padBits = 0; 310 while (i < (nVals - 3)) { 311 /* refill cache - assumes cachedBits <= 16 */ 312 if (bitsLeft >= 16) { 313 /* load 2 new bytes into left-justified cache */ 314 cache |= (unsigned int)(*buf++) << (24 - cachedBits); 315 cache |= (unsigned int)(*buf++) << (16 - cachedBits); 316 cachedBits += 16; 317 bitsLeft -= 16; 318 } else { 319 /* last time through, pad cache with zeros and drain cache */ 320 if (cachedBits + bitsLeft <= 0) return i; 321 if (bitsLeft > 0) cache |= (unsigned int)(*buf++) << (24 - cachedBits); 322 if (bitsLeft > 8) cache |= (unsigned int)(*buf++) << (16 - cachedBits); 323 cachedBits += bitsLeft; 324 bitsLeft = 0; 325 326 cache &= (signed int)0x80000000 >> (cachedBits - 1); 327 padBits = 10; 328 cachedBits += padBits; /* okay if this is > 32 (0's automatically shifted in from right) */ 329 } 330 331 /* largest maxBits = 6, plus 4 for sign bits, so make sure cache has at least 10 bits */ 332 while (i < (nVals - 3) && cachedBits >= 10 ) { 333 cw = tBase[cache >> (32 - maxBits)]; 334 len = GetHLenQ(cw); 335 cachedBits -= len; 336 cache <<= len; 337 338 v = GetCWVQ(cw); if(v) {ApplySign(v, cache); cache <<= 1; cachedBits--;} 339 w = GetCWWQ(cw); if(w) {ApplySign(w, cache); cache <<= 1; cachedBits--;} 340 x = GetCWXQ(cw); if(x) {ApplySign(x, cache); cache <<= 1; cachedBits--;} 341 y = GetCWYQ(cw); if(y) {ApplySign(y, cache); cache <<= 1; cachedBits--;} 342 343 /* ran out of bits - okay (means we're done) */ 344 if (cachedBits < padBits) 345 return i; 346 347 *vwxy++ = v; 348 *vwxy++ = w; 349 *vwxy++ = x; 350 *vwxy++ = y; 351 i += 4; 352 } 353 } 354 355 /* decoded max number of quad values */ 356 return i; 357 } 358 359 /************************************************************************************** 360 * Function: DecodeHuffman 361 * 362 * Description: decode one granule, one channel worth of Huffman codes 363 * 364 * Inputs: MP3DecInfo structure filled by UnpackFrameHeader(), UnpackSideInfo(), 365 * and UnpackScaleFactors() (for this granule) 366 * buffer pointing to start of Huffman data in MP3 frame 367 * pointer to bit offset (0-7) indicating starting bit in buf[0] 368 * number of bits in the Huffman data section of the frame 369 * (could include padding bits) 370 * index of current granule and channel 371 * 372 * Outputs: decoded coefficients in hi->huffDecBuf[ch] (hi pointer in mp3DecInfo) 373 * updated bitOffset 374 * 375 * Return: length (in bytes) of Huffman codes 376 * bitOffset also returned in parameter (0 = MSB, 7 = LSB of 377 * byte located at buf + offset) 378 * -1 if null input pointers, huffBlockBits < 0, or decoder runs 379 * out of bits prematurely (invalid bitstream) 380 **************************************************************************************/ 381 // .data about 1ms faster per frame 382 int DecodeHuffman(MP3DecInfo *mp3DecInfo, unsigned char *buf, int *bitOffset, int huffBlockBits, int gr, int ch) 383 { 384 int r1Start, r2Start, rEnd[4]; /* region boundaries */ 385 int i, w, bitsUsed, bitsLeft; 386 unsigned char *startBuf = buf; 387 388 FrameHeader *fh; 389 SideInfo *si; 390 SideInfoSub *sis; 391 ScaleFactorInfo *sfi; 392 HuffmanInfo *hi; 393 394 /* validate pointers */ 395 if (!mp3DecInfo || !mp3DecInfo->FrameHeaderPS || !mp3DecInfo->SideInfoPS || !mp3DecInfo->ScaleFactorInfoPS || !mp3DecInfo->HuffmanInfoPS) 396 return -1; 397 398 fh = ((FrameHeader *)(mp3DecInfo->FrameHeaderPS)); 399 si = ((SideInfo *)(mp3DecInfo->SideInfoPS)); 400 sis = &si->sis[gr][ch]; 401 sfi = ((ScaleFactorInfo *)(mp3DecInfo->ScaleFactorInfoPS)); 402 hi = (HuffmanInfo*)(mp3DecInfo->HuffmanInfoPS); 403 404 if (huffBlockBits < 0) 405 return -1; 406 407 /* figure out region boundaries (the first 2*bigVals coefficients divided into 3 regions) */ 408 if (sis->winSwitchFlag && sis->blockType == 2) { 409 if (sis->mixedBlock == 0) { 410 r1Start = fh->sfBand->s[(sis->region0Count + 1)/3] * 3; 411 } else { 412 if (fh->ver == MPEG1) { 413 r1Start = fh->sfBand->l[sis->region0Count + 1]; 414 } else { 415 /* see MPEG2 spec for explanation */ 416 w = fh->sfBand->s[4] - fh->sfBand->s[3]; 417 r1Start = fh->sfBand->l[6] + 2*w; 418 } 419 } 420 r2Start = MAX_NSAMP; /* short blocks don't have region 2 */ 421 } else { 422 r1Start = fh->sfBand->l[sis->region0Count + 1]; 423 r2Start = fh->sfBand->l[sis->region0Count + 1 + sis->region1Count + 1]; 424 } 425 426 /* offset rEnd index by 1 so first region = rEnd[1] - rEnd[0], etc. */ 427 rEnd[3] = MIN(MAX_NSAMP, 2 * sis->nBigvals); 428 rEnd[2] = MIN(r2Start, rEnd[3]); 429 rEnd[1] = MIN(r1Start, rEnd[3]); 430 rEnd[0] = 0; 431 432 /* rounds up to first all-zero pair (we don't check last pair for (x,y) == (non-zero, zero)) */ 433 hi->nonZeroBound[ch] = rEnd[3]; 434 435 /* decode Huffman pairs (rEnd[i] are always even numbers) */ 436 bitsLeft = huffBlockBits; 437 for (i = 0; i < 3; i++) { 438 bitsUsed = DecodeHuffmanPairs(hi->huffDecBuf[ch] + rEnd[i], rEnd[i+1] - rEnd[i], sis->tableSelect[i], bitsLeft, buf, *bitOffset); 439 if (bitsUsed < 0 || bitsUsed > bitsLeft) /* error - overran end of bitstream */ 440 return -1; 441 442 /* update bitstream position */ 443 buf += (bitsUsed + *bitOffset) >> 3; 444 *bitOffset = (bitsUsed + *bitOffset) & 0x07; 445 bitsLeft -= bitsUsed; 446 } 447 448 /* decode Huffman quads (if any) */ 449 hi->nonZeroBound[ch] += DecodeHuffmanQuads(hi->huffDecBuf[ch] + rEnd[3], MAX_NSAMP - rEnd[3], sis->count1TableSelect, bitsLeft, buf, *bitOffset); 450 451 ASSERT(hi->nonZeroBound[ch] <= MAX_NSAMP); 452 for (i = hi->nonZeroBound[ch]; i < MAX_NSAMP; i++) { 453 hi->huffDecBuf[ch][i] = 0; 454 } 455 456 /* If bits used for 576 samples < huffBlockBits, then the extras are considered 457 * to be stuffing bits (throw away, but need to return correct bitstream position) 458 */ 459 buf += (bitsLeft + *bitOffset) >> 3; 460 *bitOffset = (bitsLeft + *bitOffset) & 0x07; 461 462 return (buf - startBuf); 463 } 464