2
0

huffman.c 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462
  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. * Fixed-point MP3 decoder
  37. * Jon Recker (jrecker@real.com), Ken Cooke (kenc@real.com)
  38. * July 2003
  39. *
  40. * huffman.c - Huffman decoding of transform coefficients
  41. **************************************************************************************/
  42. #include "coder.h"
  43. #define PGM_READ_UNALIGNED 0 // Only support aligned reads, faster
  44. /* helper macros - see comments in hufftabs.c about the format of the huffman tables */
  45. #define GetMaxbits(x) ((int)( (((unsigned short)(x)) >> 0) & 0x000f))
  46. #define GetHLen(x) ((int)( (((unsigned short)(x)) >> 12) & 0x000f))
  47. #define GetCWY(x) ((int)( (((unsigned short)(x)) >> 8) & 0x000f))
  48. #define GetCWX(x) ((int)( (((unsigned short)(x)) >> 4) & 0x000f))
  49. #define GetSignBits(x) ((int)( (((unsigned short)(x)) >> 0) & 0x000f))
  50. #define GetHLenQ(x) ((int)( (((unsigned char)(x)) >> 4) & 0x0f))
  51. #define GetCWVQ(x) ((int)( (((unsigned char)(x)) >> 3) & 0x01))
  52. #define GetCWWQ(x) ((int)( (((unsigned char)(x)) >> 2) & 0x01))
  53. #define GetCWXQ(x) ((int)( (((unsigned char)(x)) >> 1) & 0x01))
  54. #define GetCWYQ(x) ((int)( (((unsigned char)(x)) >> 0) & 0x01))
  55. /* apply sign of s to the positive number x (save in MSB, will do two's complement in dequant) */
  56. #define ApplySign(x, s) { (x) |= ((s) & 0x80000000); }
  57. /**************************************************************************************
  58. * Function: DecodeHuffmanPairs
  59. *
  60. * Description: decode 2-way vector Huffman codes in the "bigValues" region of spectrum
  61. *
  62. * Inputs: valid BitStreamInfo struct, pointing to start of pair-wise codes
  63. * pointer to xy buffer to received decoded values
  64. * number of codewords to decode
  65. * index of Huffman table to use
  66. * number of bits remaining in bitstream
  67. *
  68. * Outputs: pairs of decoded coefficients in vwxy
  69. * updated BitStreamInfo struct
  70. *
  71. * Return: number of bits used, or -1 if out of bits
  72. *
  73. * Notes: assumes that nVals is an even number
  74. * si_huff.bit tests every Huffman codeword in every table (though not
  75. * necessarily all linBits outputs for x,y > 15)
  76. **************************************************************************************/
  77. // no improvement with section=data
  78. static int DecodeHuffmanPairs(int *xy, int nVals, int tabIdx, int bitsLeft, unsigned char *buf, int bitOffset)
  79. {
  80. int i, x, y;
  81. int cachedBits, padBits, len, startBits, linBits, maxBits, minBits;
  82. HuffTabType tabType;
  83. unsigned short cw, *tBase, *tCurr;
  84. unsigned int cache;
  85. if(nVals <= 0)
  86. return 0;
  87. if (bitsLeft < 0)
  88. return -1;
  89. startBits = bitsLeft;
  90. tBase = (unsigned short *)(huffTable + huffTabOffset[tabIdx]);
  91. linBits = huffTabLookup[tabIdx].linBits;
  92. tabType = huffTabLookup[tabIdx].tabType;
  93. ASSERT(!(nVals & 0x01));
  94. ASSERT(tabIdx < HUFF_PAIRTABS);
  95. ASSERT(tabIdx >= 0);
  96. ASSERT(tabType != invalidTab);
  97. /* initially fill cache with any partial byte */
  98. cache = 0;
  99. cachedBits = (8 - bitOffset) & 0x07;
  100. if (cachedBits)
  101. cache = (unsigned int)(*buf++) << (32 - cachedBits);
  102. bitsLeft -= cachedBits;
  103. if (tabType == noBits) {
  104. /* table 0, no data, x = y = 0 */
  105. for (i = 0; i < nVals; i+=2) {
  106. xy[i+0] = 0;
  107. xy[i+1] = 0;
  108. }
  109. return 0;
  110. } else if (tabType == oneShot) {
  111. /* single lookup, no escapes */
  112. maxBits = GetMaxbits(pgm_read_word(&tBase[0]));
  113. tBase++;
  114. padBits = 0;
  115. while (nVals > 0) {
  116. /* refill cache - assumes cachedBits <= 16 */
  117. if (bitsLeft >= 16) {
  118. /* load 2 new bytes into left-justified cache */
  119. cache |= (unsigned int)(*buf++) << (24 - cachedBits);
  120. cache |= (unsigned int)(*buf++) << (16 - cachedBits);
  121. cachedBits += 16;
  122. bitsLeft -= 16;
  123. } else {
  124. /* last time through, pad cache with zeros and drain cache */
  125. if (cachedBits + bitsLeft <= 0) return -1;
  126. if (bitsLeft > 0) cache |= (unsigned int)(*buf++) << (24 - cachedBits);
  127. if (bitsLeft > 8) cache |= (unsigned int)(*buf++) << (16 - cachedBits);
  128. cachedBits += bitsLeft;
  129. bitsLeft = 0;
  130. cache &= (signed int)0x80000000 >> (cachedBits - 1);
  131. padBits = 11;
  132. cachedBits += padBits; /* okay if this is > 32 (0's automatically shifted in from right) */
  133. }
  134. /* largest maxBits = 9, plus 2 for sign bits, so make sure cache has at least 11 bits */
  135. while (nVals > 0 && cachedBits >= 11 ) {
  136. cw = pgm_read_word(&tBase[cache >> (32 - maxBits)]);
  137. len = GetHLen(cw);
  138. cachedBits -= len;
  139. cache <<= len;
  140. x = GetCWX(cw); if (x) {ApplySign(x, cache); cache <<= 1; cachedBits--;}
  141. y = GetCWY(cw); if (y) {ApplySign(y, cache); cache <<= 1; cachedBits--;}
  142. /* ran out of bits - should never have consumed padBits */
  143. if (cachedBits < padBits)
  144. return -1;
  145. *xy++ = x;
  146. *xy++ = y;
  147. nVals -= 2;
  148. }
  149. }
  150. bitsLeft += (cachedBits - padBits);
  151. return (startBits - bitsLeft);
  152. } else if (tabType == loopLinbits || tabType == loopNoLinbits) {
  153. tCurr = tBase;
  154. padBits = 0;
  155. while (nVals > 0) {
  156. /* refill cache - assumes cachedBits <= 16 */
  157. if (bitsLeft >= 16) {
  158. /* load 2 new bytes into left-justified cache */
  159. cache |= (unsigned int)(*buf++) << (24 - cachedBits);
  160. cache |= (unsigned int)(*buf++) << (16 - cachedBits);
  161. cachedBits += 16;
  162. bitsLeft -= 16;
  163. } else {
  164. /* last time through, pad cache with zeros and drain cache */
  165. if (cachedBits + bitsLeft <= 0) return -1;
  166. if (bitsLeft > 0) cache |= (unsigned int)(*buf++) << (24 - cachedBits);
  167. if (bitsLeft > 8) cache |= (unsigned int)(*buf++) << (16 - cachedBits);
  168. cachedBits += bitsLeft;
  169. bitsLeft = 0;
  170. cache &= (signed int)0x80000000 >> (cachedBits - 1);
  171. padBits = 11;
  172. cachedBits += padBits; /* okay if this is > 32 (0's automatically shifted in from right) */
  173. }
  174. /* largest maxBits = 9, plus 2 for sign bits, so make sure cache has at least 11 bits */
  175. while (nVals > 0 && cachedBits >= 11 ) {
  176. maxBits = GetMaxbits(pgm_read_word(&tCurr[0]));
  177. cw = pgm_read_word(&tCurr[(cache >> (32 - maxBits)) + 1]);
  178. len = GetHLen(cw);
  179. if (!len) {
  180. cachedBits -= maxBits;
  181. cache <<= maxBits;
  182. tCurr += cw;
  183. continue;
  184. }
  185. cachedBits -= len;
  186. cache <<= len;
  187. x = GetCWX(cw);
  188. y = GetCWY(cw);
  189. if (x == 15 && tabType == loopLinbits) {
  190. minBits = linBits + 1 + (y ? 1 : 0);
  191. if (cachedBits + bitsLeft < minBits)
  192. return -1;
  193. while (cachedBits < minBits) {
  194. cache |= (unsigned int)(*buf++) << (24 - cachedBits);
  195. cachedBits += 8;
  196. bitsLeft -= 8;
  197. }
  198. if (bitsLeft < 0) {
  199. cachedBits += bitsLeft;
  200. bitsLeft = 0;
  201. cache &= (signed int)0x80000000 >> (cachedBits - 1);
  202. }
  203. x += (int)(cache >> (32 - linBits));
  204. cachedBits -= linBits;
  205. cache <<= linBits;
  206. }
  207. if (x) {ApplySign(x, cache); cache <<= 1; cachedBits--;}
  208. if (y == 15 && tabType == loopLinbits) {
  209. minBits = linBits + 1;
  210. if (cachedBits + bitsLeft < minBits)
  211. return -1;
  212. while (cachedBits < minBits) {
  213. cache |= (unsigned int)(*buf++) << (24 - cachedBits);
  214. cachedBits += 8;
  215. bitsLeft -= 8;
  216. }
  217. if (bitsLeft < 0) {
  218. cachedBits += bitsLeft;
  219. bitsLeft = 0;
  220. cache &= (signed int)0x80000000 >> (cachedBits - 1);
  221. }
  222. y += (int)(cache >> (32 - linBits));
  223. cachedBits -= linBits;
  224. cache <<= linBits;
  225. }
  226. if (y) {ApplySign(y, cache); cache <<= 1; cachedBits--;}
  227. /* ran out of bits - should never have consumed padBits */
  228. if (cachedBits < padBits)
  229. return -1;
  230. *xy++ = x;
  231. *xy++ = y;
  232. nVals -= 2;
  233. tCurr = tBase;
  234. }
  235. }
  236. bitsLeft += (cachedBits - padBits);
  237. return (startBits - bitsLeft);
  238. }
  239. /* error in bitstream - trying to access unused Huffman table */
  240. return -1;
  241. }
  242. /**************************************************************************************
  243. * Function: DecodeHuffmanQuads
  244. *
  245. * Description: decode 4-way vector Huffman codes in the "count1" region of spectrum
  246. *
  247. * Inputs: valid BitStreamInfo struct, pointing to start of quadword codes
  248. * pointer to vwxy buffer to received decoded values
  249. * maximum number of codewords to decode
  250. * index of quadword table (0 = table A, 1 = table B)
  251. * number of bits remaining in bitstream
  252. *
  253. * Outputs: quadruples of decoded coefficients in vwxy
  254. * updated BitStreamInfo struct
  255. *
  256. * Return: index of the first "zero_part" value (index of the first sample
  257. * of the quad word after which all samples are 0)
  258. *
  259. * Notes: si_huff.bit tests every vwxy output in both quad tables
  260. **************************************************************************************/
  261. // no improvement with section=data
  262. static int DecodeHuffmanQuads(int *vwxy, int nVals, int tabIdx, int bitsLeft, unsigned char *buf, int bitOffset)
  263. {
  264. int i, v, w, x, y;
  265. int len, maxBits, cachedBits, padBits;
  266. unsigned int cache;
  267. unsigned char cw, *tBase;
  268. if (bitsLeft <= 0)
  269. return 0;
  270. tBase = (unsigned char *)quadTable + quadTabOffset[tabIdx];
  271. maxBits = quadTabMaxBits[tabIdx];
  272. /* initially fill cache with any partial byte */
  273. cache = 0;
  274. cachedBits = (8 - bitOffset) & 0x07;
  275. if (cachedBits)
  276. cache = (unsigned int)(*buf++) << (32 - cachedBits);
  277. bitsLeft -= cachedBits;
  278. i = padBits = 0;
  279. while (i < (nVals - 3)) {
  280. /* refill cache - assumes cachedBits <= 16 */
  281. if (bitsLeft >= 16) {
  282. /* load 2 new bytes into left-justified cache */
  283. cache |= (unsigned int)(*buf++) << (24 - cachedBits);
  284. cache |= (unsigned int)(*buf++) << (16 - cachedBits);
  285. cachedBits += 16;
  286. bitsLeft -= 16;
  287. } else {
  288. /* last time through, pad cache with zeros and drain cache */
  289. if (cachedBits + bitsLeft <= 0) return i;
  290. if (bitsLeft > 0) cache |= (unsigned int)(*buf++) << (24 - cachedBits);
  291. if (bitsLeft > 8) cache |= (unsigned int)(*buf++) << (16 - cachedBits);
  292. cachedBits += bitsLeft;
  293. bitsLeft = 0;
  294. cache &= (signed int)0x80000000 >> (cachedBits - 1);
  295. padBits = 10;
  296. cachedBits += padBits; /* okay if this is > 32 (0's automatically shifted in from right) */
  297. }
  298. /* largest maxBits = 6, plus 4 for sign bits, so make sure cache has at least 10 bits */
  299. while (i < (nVals - 3) && cachedBits >= 10 ) {
  300. cw = pgm_read_byte(&tBase[cache >> (32 - maxBits)]);
  301. len = GetHLenQ(cw);
  302. cachedBits -= len;
  303. cache <<= len;
  304. v = GetCWVQ(cw); if(v) {ApplySign(v, cache); cache <<= 1; cachedBits--;}
  305. w = GetCWWQ(cw); if(w) {ApplySign(w, cache); cache <<= 1; cachedBits--;}
  306. x = GetCWXQ(cw); if(x) {ApplySign(x, cache); cache <<= 1; cachedBits--;}
  307. y = GetCWYQ(cw); if(y) {ApplySign(y, cache); cache <<= 1; cachedBits--;}
  308. /* ran out of bits - okay (means we're done) */
  309. if (cachedBits < padBits)
  310. return i;
  311. *vwxy++ = v;
  312. *vwxy++ = w;
  313. *vwxy++ = x;
  314. *vwxy++ = y;
  315. i += 4;
  316. }
  317. }
  318. /* decoded max number of quad values */
  319. return i;
  320. }
  321. /**************************************************************************************
  322. * Function: DecodeHuffman
  323. *
  324. * Description: decode one granule, one channel worth of Huffman codes
  325. *
  326. * Inputs: MP3DecInfo structure filled by UnpackFrameHeader(), UnpackSideInfo(),
  327. * and UnpackScaleFactors() (for this granule)
  328. * buffer pointing to start of Huffman data in MP3 frame
  329. * pointer to bit offset (0-7) indicating starting bit in buf[0]
  330. * number of bits in the Huffman data section of the frame
  331. * (could include padding bits)
  332. * index of current granule and channel
  333. *
  334. * Outputs: decoded coefficients in hi->huffDecBuf[ch] (hi pointer in mp3DecInfo)
  335. * updated bitOffset
  336. *
  337. * Return: length (in bytes) of Huffman codes
  338. * bitOffset also returned in parameter (0 = MSB, 7 = LSB of
  339. * byte located at buf + offset)
  340. * -1 if null input pointers, huffBlockBits < 0, or decoder runs
  341. * out of bits prematurely (invalid bitstream)
  342. **************************************************************************************/
  343. // .data about 1ms faster per frame
  344. /* __attribute__ ((section (".data"))) */ int DecodeHuffman(MP3DecInfo *mp3DecInfo, unsigned char *buf, int *bitOffset, int huffBlockBits, int gr, int ch)
  345. {
  346. int r1Start, r2Start, rEnd[4]; /* region boundaries */
  347. int i, w, bitsUsed, bitsLeft;
  348. unsigned char *startBuf = buf;
  349. FrameHeader *fh;
  350. SideInfo *si;
  351. SideInfoSub *sis;
  352. //ScaleFactorInfo *sfi;
  353. HuffmanInfo *hi;
  354. /* validate pointers */
  355. if (!mp3DecInfo || !mp3DecInfo->FrameHeaderPS || !mp3DecInfo->SideInfoPS || !mp3DecInfo->ScaleFactorInfoPS || !mp3DecInfo->HuffmanInfoPS)
  356. return -1;
  357. fh = ((FrameHeader *)(mp3DecInfo->FrameHeaderPS));
  358. si = ((SideInfo *)(mp3DecInfo->SideInfoPS));
  359. sis = &si->sis[gr][ch];
  360. //sfi = ((ScaleFactorInfo *)(mp3DecInfo->ScaleFactorInfoPS));
  361. hi = (HuffmanInfo*)(mp3DecInfo->HuffmanInfoPS);
  362. if (huffBlockBits < 0)
  363. return -1;
  364. /* figure out region boundaries (the first 2*bigVals coefficients divided into 3 regions) */
  365. if (sis->winSwitchFlag && sis->blockType == 2) {
  366. if (sis->mixedBlock == 0) {
  367. r1Start = fh->sfBand->s[(sis->region0Count + 1)/3] * 3;
  368. } else {
  369. if (fh->ver == MPEG1) {
  370. r1Start = fh->sfBand->l[sis->region0Count + 1];
  371. } else {
  372. /* see MPEG2 spec for explanation */
  373. w = fh->sfBand->s[4] - fh->sfBand->s[3];
  374. r1Start = fh->sfBand->l[6] + 2*w;
  375. }
  376. }
  377. r2Start = MAX_NSAMP; /* short blocks don't have region 2 */
  378. } else {
  379. r1Start = fh->sfBand->l[sis->region0Count + 1];
  380. r2Start = fh->sfBand->l[sis->region0Count + 1 + sis->region1Count + 1];
  381. }
  382. /* offset rEnd index by 1 so first region = rEnd[1] - rEnd[0], etc. */
  383. rEnd[3] = MIN(MAX_NSAMP, 2 * sis->nBigvals);
  384. rEnd[2] = MIN(r2Start, rEnd[3]);
  385. rEnd[1] = MIN(r1Start, rEnd[3]);
  386. rEnd[0] = 0;
  387. /* rounds up to first all-zero pair (we don't check last pair for (x,y) == (non-zero, zero)) */
  388. hi->nonZeroBound[ch] = rEnd[3];
  389. /* decode Huffman pairs (rEnd[i] are always even numbers) */
  390. bitsLeft = huffBlockBits;
  391. for (i = 0; i < 3; i++) {
  392. bitsUsed = DecodeHuffmanPairs(hi->huffDecBuf[ch] + rEnd[i], rEnd[i+1] - rEnd[i], sis->tableSelect[i], bitsLeft, buf, *bitOffset);
  393. if (bitsUsed < 0 || bitsUsed > bitsLeft) /* error - overran end of bitstream */
  394. return -1;
  395. /* update bitstream position */
  396. buf += (bitsUsed + *bitOffset) >> 3;
  397. *bitOffset = (bitsUsed + *bitOffset) & 0x07;
  398. bitsLeft -= bitsUsed;
  399. }
  400. /* decode Huffman quads (if any) */
  401. hi->nonZeroBound[ch] += DecodeHuffmanQuads(hi->huffDecBuf[ch] + rEnd[3], MAX_NSAMP - rEnd[3], sis->count1TableSelect, bitsLeft, buf, *bitOffset);
  402. ASSERT(hi->nonZeroBound[ch] <= MAX_NSAMP);
  403. for (i = hi->nonZeroBound[ch]; i < MAX_NSAMP; i++)
  404. hi->huffDecBuf[ch][i] = 0;
  405. /* If bits used for 576 samples < huffBlockBits, then the extras are considered
  406. * to be stuffing bits (throw away, but need to return correct bitstream position)
  407. */
  408. buf += (bitsLeft + *bitOffset) >> 3;
  409. *bitOffset = (bitsLeft + *bitOffset) & 0x07;
  410. return (buf - startBuf);
  411. }