blob: 4412eb6ebb8ab114923ee1bd9588b81eac78e7c7
| 1 | /* ***** BEGIN LICENSE BLOCK ***** |
| 2 | * Source last modified: $Id: category.c,v 1.4 2005/04/27 19:20:50 hubbe Exp $ |
| 3 | * |
| 4 | * REALNETWORKS CONFIDENTIAL--NOT FOR DISTRIBUTION IN SOURCE CODE FORM |
| 5 | * Portions Copyright (c) 1995-2002 RealNetworks, Inc. |
| 6 | * All Rights Reserved. |
| 7 | * |
| 8 | * The contents of this file, and the files included with this file, |
| 9 | * are subject to the current version of the Real Format Source Code |
| 10 | * Porting and Optimization License, available at |
| 11 | * https://helixcommunity.org/2005/license/realformatsource (unless |
| 12 | * RealNetworks otherwise expressly agrees in writing that you are |
| 13 | * subject to a different license). You may also obtain the license |
| 14 | * terms directly from RealNetworks. You may not use this file except |
| 15 | * in compliance with the Real Format Source Code Porting and |
| 16 | * Optimization License. There are no redistribution rights for the |
| 17 | * source code of this file. Please see the Real Format Source Code |
| 18 | * Porting and Optimization License for the rights, obligations and |
| 19 | * limitations governing use of the contents of the file. |
| 20 | * |
| 21 | * RealNetworks is the developer of the Original Code and owns the |
| 22 | * copyrights in the portions it created. |
| 23 | * |
| 24 | * This file, and the files included with this file, is distributed and |
| 25 | * made available on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, |
| 26 | * EITHER EXPRESS OR IMPLIED, AND REALNETWORKS HEREBY DISCLAIMS ALL |
| 27 | * SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF |
| 28 | * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT |
| 29 | * OR NON-INFRINGEMENT. |
| 30 | * |
| 31 | * Technology Compatibility Kit Test Suite(s) Location: |
| 32 | * https://rarvcode-tck.helixcommunity.org |
| 33 | * |
| 34 | * Contributor(s): |
| 35 | * |
| 36 | * ***** END LICENSE BLOCK ***** */ |
| 37 | |
| 38 | /************************************************************************************** |
| 39 | * Fixed-point RealAudio 8 decoder |
| 40 | * Ken Cooke (kenc@real.com), Jon Recker (jrecker@real.com) |
| 41 | * October 2003 |
| 42 | * |
| 43 | * category.c - derivation of categorization (i.e. quantizer settings) for each frame |
| 44 | * |
| 45 | * This is Ken's super-fast version |
| 46 | * - uses incrementally updated heaps |
| 47 | * - 3x speedup vs. original |
| 48 | * |
| 49 | * Discussion of calculating the categories: |
| 50 | * This is a symmetrical operation, so the decoder goes through |
| 51 | * the same process as the encoder when computing the categorizations. |
| 52 | * The decoder first calculates a max bits/fine quantizer initial |
| 53 | * categorization based on a perceptual masking model. Then it |
| 54 | * builds them all and chooses the one given by rateCode, |
| 55 | * which is extracted from the bitstream. |
| 56 | * |
| 57 | * rmsIndex[i] is the RMS power of region i |
| 58 | * NCATZNS = (1 << RATEBITS) = max number of categorizations we can try |
| 59 | * |
| 60 | * cat runs from 0 to 7. Lower number means finer quantization. |
| 61 | * expbits_tab[i] tells us how many bits we should expect to spend |
| 62 | * coding a region with cat = i |
| 63 | **************************************************************************************/ |
| 64 | |
| 65 | #include "coder.h" |
| 66 | |
| 67 | /* heap indexing, where heap[1] is root */ |
| 68 | #define PARENT(i) ((i) >> 1) |
| 69 | #define LCHILD(i) ((i) << 1) |
| 70 | #define RCHILD(i) (LCHILD(i)+1) |
| 71 | |
| 72 | static const int expbits_tab[8] = { 52, 47, 43, 37, 29, 22, 16, 0 }; |
| 73 | |
| 74 | /************************************************************************************** |
| 75 | * Function: CategorizeAndExpand |
| 76 | * |
| 77 | * Description: derive the quantizer setting for each region, based on decoded power |
| 78 | * envelope, number of bits available, and rateCode index |
| 79 | * |
| 80 | * Inputs: pointer to initialized Gecko2Info struct |
| 81 | * number of bits remaining in bitstream for this frame |
| 82 | * |
| 83 | * Outputs: catbuf[], which contains the correct quantizer index (cat) for each |
| 84 | * region, based on the rateCode read from bitstream |
| 85 | * |
| 86 | * Return: none |
| 87 | **************************************************************************************/ |
| 88 | void CategorizeAndExpand(Gecko2Info *gi, int availbits) |
| 89 | { |
| 90 | int r, n, k, val; |
| 91 | int offset, delta, cat; |
| 92 | int expbits, maxbits, minbits; |
| 93 | int maxptr, minptr; |
| 94 | int nminheap = 0, nmaxheap = 0; |
| 95 | int *cp; |
| 96 | int *maxcat = gi->db.maxcat; |
| 97 | int *mincat = gi->db.mincat; |
| 98 | int *changes = gi->db.changes; |
| 99 | int *maxheap = gi->db.maxheap; |
| 100 | int *minheap = gi->db.minheap; |
| 101 | int *rmsIndex = gi->db.rmsIndex; |
| 102 | int *catbuf = gi->db.catbuf; |
| 103 | int rateCode = gi->rateCode; |
| 104 | |
| 105 | /* it's okay not to zero-init maxheap/minheap[1 ... MAXCREGN] |
| 106 | * we don't read maxheap/minheap[1+] without putting something in them first |
| 107 | */ |
| 108 | maxheap[0] = 0x7fffffff; /* upheap sentinel */ |
| 109 | minheap[0] = 0x80000000; /* upheap sentinel */ |
| 110 | |
| 111 | /* Hack to compensate for different statistics at higher bits/sample */ |
| 112 | if (availbits > gi->nSamples) { |
| 113 | availbits = gi->nSamples + ((availbits - gi->nSamples) * 5 / 8); |
| 114 | } |
| 115 | /* |
| 116 | * Initial categorization. |
| 117 | * |
| 118 | * This attempts to assigns categories to regions using |
| 119 | * a simple approximation of perceptual masking. |
| 120 | * Offset is chosen via binary search for desired bits. |
| 121 | */ |
| 122 | offset = -32; /* start with minimum offset */ |
| 123 | for (delta = 32; delta > 0; delta >>= 1) { |
| 124 | |
| 125 | expbits = 0; |
| 126 | for (r = 0; r < gi->cRegions; r++) { |
| 127 | |
| 128 | /* Test categorization at (offset+delta) */ |
| 129 | cat = (offset + delta - rmsIndex[r]) / 2; |
| 130 | if (cat < 0) { |
| 131 | cat = 0; /* clip */ |
| 132 | } |
| 133 | if (cat > 7) { |
| 134 | cat = 7; /* clip */ |
| 135 | } |
| 136 | expbits += expbits_tab[cat]; /* tally expected bits */ |
| 137 | } |
| 138 | /* Find largest offset such that (expbits >= availbits-32) */ |
| 139 | if (expbits >= availbits - 32) { /* if still over budget, */ |
| 140 | offset += delta; /* choose increased offset */ |
| 141 | } |
| 142 | } |
| 143 | |
| 144 | /* Use the selected categorization */ |
| 145 | expbits = 0; |
| 146 | for (r = 0; r < gi->cRegions; r++) { |
| 147 | cat = (offset - rmsIndex[r]) / 2; |
| 148 | if (cat < 0) { |
| 149 | cat = 0; /* clip */ |
| 150 | } |
| 151 | if (cat > 7) { |
| 152 | cat = 7; /* clip */ |
| 153 | } |
| 154 | expbits += expbits_tab[cat]; |
| 155 | mincat[r] = cat; /* init */ |
| 156 | maxcat[r] = cat; /* init */ |
| 157 | |
| 158 | val = offset - rmsIndex[r] - 2 * cat; |
| 159 | val = (val << 16) | r; /* max favors high r, min favors low r */ |
| 160 | |
| 161 | /* build maxheap */ |
| 162 | if (cat < 7) { |
| 163 | /* insert at heap[N+1] */ |
| 164 | k = ++nmaxheap; |
| 165 | maxheap[k] = val; |
| 166 | /* upheap */ |
| 167 | while (val > maxheap[PARENT(k)]) { |
| 168 | maxheap[k] = maxheap[PARENT(k)]; |
| 169 | k = PARENT(k); |
| 170 | } |
| 171 | maxheap[k] = val; |
| 172 | } |
| 173 | |
| 174 | /* build minheap */ |
| 175 | if (cat > 0) { |
| 176 | /* insert at heap[N+1] */ |
| 177 | k = ++nminheap; |
| 178 | minheap[k] = val; |
| 179 | /* upheap */ |
| 180 | while (val < minheap[PARENT(k)]) { |
| 181 | minheap[k] = minheap[PARENT(k)]; |
| 182 | k = PARENT(k); |
| 183 | } |
| 184 | minheap[k] = val; |
| 185 | } |
| 186 | } |
| 187 | |
| 188 | /* init */ |
| 189 | minbits = expbits; |
| 190 | maxbits = expbits; |
| 191 | minptr = gi->nCatzns; /* grows up, post-increment */ |
| 192 | maxptr = gi->nCatzns; /* grows down, pre-decrement */ |
| 193 | |
| 194 | /* |
| 195 | * Derive additional categorizations. |
| 196 | * |
| 197 | * Each new categorization differs from the last in a single region, |
| 198 | * where the categories differ by one, and are ordered by decreasing |
| 199 | * expected bits. |
| 200 | */ |
| 201 | for (n = 1; n < gi->nCatzns; n++) { |
| 202 | /* Choose whether new cat should have larger/smaller bits */ |
| 203 | |
| 204 | if (maxbits + minbits <= 2 * availbits) { |
| 205 | /* if average is low, add one with more bits */ |
| 206 | if (!nminheap) { |
| 207 | /* printf("all quants at min\n"); */ |
| 208 | break; |
| 209 | } |
| 210 | r = minheap[1] & 0xffff; |
| 211 | |
| 212 | /* bump the chosen region */ |
| 213 | changes[--maxptr] = r; /* add to change list */ |
| 214 | maxbits -= expbits_tab[maxcat[r]]; /* sub old bits */ |
| 215 | maxcat[r] -= 1; /* dec category */ |
| 216 | maxbits += expbits_tab[maxcat[r]]; /* add new bits */ |
| 217 | |
| 218 | /* update heap[1] */ |
| 219 | k = 1; |
| 220 | if (maxcat[r] == 0) { |
| 221 | minheap[k] = minheap[nminheap--]; /* remove */ |
| 222 | } else { |
| 223 | minheap[k] += (2 << 16); /* update */ |
| 224 | } |
| 225 | |
| 226 | /* downheap */ |
| 227 | val = minheap[k]; |
| 228 | while (k <= PARENT(nminheap)) { |
| 229 | int child = LCHILD(k); |
| 230 | int right = RCHILD(k); |
| 231 | if ((right <= nminheap) && (minheap[right] < minheap[child])) { |
| 232 | child = right; |
| 233 | } |
| 234 | if (val < minheap[child]) { |
| 235 | break; |
| 236 | } |
| 237 | minheap[k] = minheap[child]; |
| 238 | k = child; |
| 239 | } |
| 240 | minheap[k] = val; |
| 241 | |
| 242 | } else { |
| 243 | /* average is high, add one with less bits */ |
| 244 | if (!nmaxheap) { |
| 245 | /* printf("all quants at max\n"); */ |
| 246 | break; |
| 247 | } |
| 248 | r = maxheap[1] & 0xffff; |
| 249 | |
| 250 | /* bump the chosen region */ |
| 251 | changes[minptr++] = r; /* add to change list */ |
| 252 | minbits -= expbits_tab[mincat[r]]; /* sub old bits */ |
| 253 | mincat[r] += 1; /* inc category */ |
| 254 | minbits += expbits_tab[mincat[r]]; /* add new bits */ |
| 255 | |
| 256 | /* update heap[1] */ |
| 257 | k = 1; |
| 258 | if (mincat[r] == 7) { |
| 259 | maxheap[k] = maxheap[nmaxheap--]; /* remove */ |
| 260 | } else { |
| 261 | maxheap[k] -= (2 << 16); /* update */ |
| 262 | } |
| 263 | |
| 264 | /* downheap */ |
| 265 | val = maxheap[k]; |
| 266 | while (k <= PARENT(nmaxheap)) { |
| 267 | int child = LCHILD(k); |
| 268 | int right = RCHILD(k); |
| 269 | if ((right <= nmaxheap) && (maxheap[right] > maxheap[child])) { |
| 270 | child = right; |
| 271 | } |
| 272 | if (val > maxheap[child]) { |
| 273 | break; |
| 274 | } |
| 275 | maxheap[k] = maxheap[child]; |
| 276 | k = child; |
| 277 | } |
| 278 | maxheap[k] = val; |
| 279 | } |
| 280 | } |
| 281 | |
| 282 | /* largest categorization */ |
| 283 | for (r = 0; r < gi->cRegions; r++) { |
| 284 | catbuf[r] = maxcat[r]; |
| 285 | } |
| 286 | |
| 287 | /* make sure rateCode is not greater than number of changes in list */ |
| 288 | ASSERT(rateCode <= (minptr - maxptr)); |
| 289 | |
| 290 | /* expand categories using change list, starting at max cat |
| 291 | * we change one region at a time (cat++ = coarser quantizer) |
| 292 | */ |
| 293 | cp = &changes[maxptr]; |
| 294 | while (rateCode--) { |
| 295 | catbuf[*cp++] += 1; |
| 296 | } |
| 297 | |
| 298 | } |
| 299 |