1 /*
2 * Copyright (c) 2011 Apple Inc. All rights reserved.
3 *
4 * @APPLE_APACHE_LICENSE_HEADER_START@
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License") ;
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 *
18 * @APPLE_APACHE_LICENSE_HEADER_END@
19 */
20
21 /*
22 File: ag_dec.c
23
24 Contains: Adaptive Golomb decode routines.
25
26 Copyright: (c) 2001-2011 Apple, Inc.
27 */
28
29 #include <math.h>
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <string.h>
33
34 #include "aglib.h"
35 #include "ALACBitUtilities.h"
36 #include "ALACAudioTypes.h"
37
38 #define CODE_TO_LONG_MAXBITS 32
39 #define N_MAX_MEAN_CLAMP 0xffff
40 #define N_MEAN_CLAMP_VAL 0xffff
41 #define REPORT_VAL 40
42
43 #if __GNUC__
44 #define ALWAYS_INLINE __attribute__ ((always_inline))
45 #else
46 #define ALWAYS_INLINE
47 #endif
48
49 /* And on the subject of the CodeWarrior x86 compiler and inlining, I reworked a lot of this
50 to help the compiler out. In many cases this required manual inlining or a macro. Sorry
51 if it is ugly but the performance gains are well worth it.
52 - WSK 5/19/04
53 */
54
set_standard_ag_params(AGParamRecPtr params,uint32_t fullwidth,uint32_t sectorwidth)55 void set_standard_ag_params (AGParamRecPtr params, uint32_t fullwidth, uint32_t sectorwidth)
56 {
57 /* Use
58 fullwidth = sectorwidth = numOfSamples, for analog 1-dimensional type-short data,
59 but use
60 fullwidth = full image width, sectorwidth = sector (patch) width
61 for such as image (2-dim.) data.
62 */
63 set_ag_params (params, MB0, PB0, KB0, fullwidth, sectorwidth, MAX_RUN_DEFAULT) ;
64 }
65
set_ag_params(AGParamRecPtr params,uint32_t m,uint32_t p,uint32_t k,uint32_t f,uint32_t s,uint32_t maxrun)66 void set_ag_params (AGParamRecPtr params, uint32_t m, uint32_t p, uint32_t k, uint32_t f, uint32_t s, uint32_t maxrun)
67 {
68 params->mb = params->mb0 = m ;
69 params->pb = p ;
70 params->kb = k ;
71 params->wb = (1u << params->kb) - 1 ;
72 params->qb = QB-params->pb ;
73 params->fw = f ;
74 params->sw = s ;
75 params->maxrun = maxrun ;
76 }
77
78 #if PRAGMA_MARK
79 #pragma mark -
80 #endif
81
82
83 // note: implementing this with some kind of "count leading zeros" assembly is a big performance win
lead(int32_t m)84 static inline int32_t lead (int32_t m)
85 {
86 long j ;
87 unsigned long c = (1ul << 31) ;
88
89 for (j = 0 ; j < 32 ; j++)
90 {
91 if ((c & m) != 0)
92 break ;
93 c >>= 1 ;
94 }
95 return j ;
96 }
97
98 #define arithmin(a, b) ((a) < (b) ? (a) : (b))
99
lg3a(int32_t x)100 static inline int32_t ALWAYS_INLINE lg3a (int32_t x)
101 {
102 int32_t result ;
103
104 x += 3 ;
105 result = lead (x) ;
106
107 return 31 - result ;
108 }
109
read32bit(uint8_t * buffer)110 static inline uint32_t ALWAYS_INLINE read32bit (uint8_t * buffer)
111 {
112 // embedded CPUs typically can't read unaligned 32-bit words so just read the bytes
113 uint32_t value ;
114
115 value = ((uint32_t) buffer [0] << 24) | ((uint32_t) buffer [1] << 16) |
116 ((uint32_t) buffer [2] << 8) | (uint32_t) buffer [3] ;
117 return value ;
118
119 }
120
121 #if PRAGMA_MARK
122 #pragma mark -
123 #endif
124
125 #define get_next_fromlong(inlong, suff) ((inlong) >> (32 - (suff)))
126
127
128 static inline uint32_t ALWAYS_INLINE
getstreambits(uint8_t * in,int32_t bitoffset,int32_t numbits)129 getstreambits (uint8_t *in, int32_t bitoffset, int32_t numbits)
130 {
131 uint32_t load1, load2 ;
132 uint32_t byteoffset = bitoffset / 8 ;
133 uint32_t result ;
134
135 //Assert (numbits <= 32) ;
136
137 load1 = read32bit (in + byteoffset) ;
138
139 if ((numbits + (bitoffset & 0x7)) > 32)
140 {
141 int32_t load2shift ;
142
143 result = load1 << (bitoffset & 0x7) ;
144 load2 = (uint32_t) in [byteoffset + 4] ;
145 load2shift = (8 - (numbits + (bitoffset & 0x7) - 32)) ;
146 load2 >>= load2shift ;
147 result >>= (32 - numbits) ;
148 result |= load2 ;
149 }
150 else
151 {
152 result = load1 >> (32 - numbits - (bitoffset & 7)) ;
153 }
154
155 // a shift of >= "the number of bits in the type of the value being shifted" results in undefined
156 // behavior so don't try to shift by 32
157 if (numbits != (sizeof (result) * 8))
158 result &= ~ (0xfffffffful << numbits) ;
159
160 return result ;
161 }
162
163
dyn_get(unsigned char * in,uint32_t * bitPos,uint32_t m,uint32_t k)164 static inline int32_t dyn_get (unsigned char *in, uint32_t *bitPos, uint32_t m, uint32_t k)
165 {
166 uint32_t tempbits = *bitPos ;
167 uint32_t result ;
168 uint32_t pre = 0, v ;
169 uint32_t streamlong ;
170
171 streamlong = read32bit (in + (tempbits >> 3)) ;
172 streamlong <<= (tempbits & 7) ;
173
174 /* find the number of bits in the prefix */
175 {
176 uint32_t notI = ~streamlong ;
177 pre = lead (notI) ;
178 }
179
180 if (pre >= MAX_PREFIX_16)
181 {
182 pre = MAX_PREFIX_16 ;
183 tempbits += pre ;
184 streamlong <<= pre ;
185 result = get_next_fromlong (streamlong, MAX_DATATYPE_BITS_16) ;
186 tempbits += MAX_DATATYPE_BITS_16 ;
187
188 }
189 else
190 {
191 // all of the bits must fit within the long we have loaded
192 //Assert (pre+1+k <= 32) ;
193
194 tempbits += pre ;
195 tempbits += 1 ;
196 streamlong <<= pre + 1 ;
197 v = get_next_fromlong (streamlong, k) ;
198 tempbits += k ;
199
200 result = pre*m + v-1 ;
201
202 if (v < 2)
203 {
204 result -= (v-1) ;
205 tempbits -= 1 ;
206 }
207 }
208
209 *bitPos = tempbits ;
210 return result ;
211 }
212
213
dyn_get_32bit(uint8_t * in,uint32_t * bitPos,int32_t m,int32_t k,int32_t maxbits)214 static inline int32_t dyn_get_32bit (uint8_t * in, uint32_t * bitPos, int32_t m, int32_t k, int32_t maxbits)
215 {
216 uint32_t tempbits = *bitPos ;
217 uint32_t v ;
218 uint32_t streamlong ;
219 uint32_t result ;
220
221 streamlong = read32bit (in + (tempbits >> 3)) ;
222 streamlong <<= (tempbits & 7) ;
223
224 /* find the number of bits in the prefix */
225 {
226 uint32_t notI = ~streamlong ;
227 result = lead (notI) ;
228 }
229
230 if (result >= MAX_PREFIX_32)
231 {
232 result = getstreambits (in, tempbits+MAX_PREFIX_32, maxbits) ;
233 tempbits += MAX_PREFIX_32 + maxbits ;
234 }
235 else
236 {
237 /* all of the bits must fit within the long we have loaded*/
238 //Assert (k<=14) ;
239 //Assert (result<MAX_PREFIX_32) ;
240 //Assert (result+1+k <= 32) ;
241
242 tempbits += result ;
243 tempbits += 1 ;
244
245 if (k != 1)
246 {
247 streamlong <<= result + 1 ;
248 v = get_next_fromlong (streamlong, k) ;
249 tempbits += k ;
250 tempbits -= 1 ;
251 result = result*m ;
252
253 if (v >= 2)
254 {
255 result += (v-1) ;
256 tempbits += 1 ;
257 }
258 }
259 }
260
261 *bitPos = tempbits ;
262
263 return result ;
264 }
265
dyn_decomp(AGParamRecPtr params,BitBuffer * bitstream,int32_t * pc,int32_t numSamples,int32_t maxSize,uint32_t * outNumBits)266 int32_t dyn_decomp (AGParamRecPtr params, BitBuffer * bitstream, int32_t * pc, int32_t numSamples, int32_t maxSize, uint32_t * outNumBits)
267 {
268 uint8_t *in ;
269 int32_t *outPtr = pc ;
270 uint32_t bitPos, startPos, maxPos ;
271 uint32_t j, m, k, n, c, mz ;
272 int32_t del, zmode ;
273 uint32_t mb ;
274 uint32_t pb_local = params->pb ;
275 uint32_t kb_local = params->kb ;
276 uint32_t wb_local = params->wb ;
277 int32_t status ;
278
279 RequireAction ((bitstream != NULL) && (pc != NULL) && (outNumBits != NULL), return kALAC_ParamError ;) ;
280 *outNumBits = 0 ;
281
282 in = bitstream->cur ;
283 startPos = bitstream->bitIndex ;
284 maxPos = bitstream->byteSize * 8 ;
285 bitPos = startPos ;
286
287 mb = params->mb0 ;
288 zmode = 0 ;
289
290 c = 0 ;
291 status = ALAC_noErr ;
292
293 while (c < (uint32_t) numSamples)
294 {
295 // bail if we've run off the end of the buffer
296 RequireAction (bitPos < maxPos, status = kALAC_ParamError ; goto Exit ;) ;
297
298 m = (mb) >> QBSHIFT ;
299 k = lg3a (m) ;
300
301 k = arithmin (k, kb_local) ;
302 m = (1 << k) - 1 ;
303
304 n = dyn_get_32bit (in, &bitPos, m, k, maxSize) ;
305
306 // least significant bit is sign bit
307 {
308 uint32_t ndecode = n + zmode ;
309 int32_t multiplier = - (int) (ndecode & 1) ;
310
311 multiplier |= 1 ;
312 del = ((ndecode+1) >> 1) * (multiplier) ;
313 }
314
315 *outPtr++ = del ;
316
317 c++ ;
318
319 mb = pb_local * (n + zmode) + mb - ((pb_local * mb) >> QBSHIFT) ;
320
321 // update mean tracking
322 if (n > N_MAX_MEAN_CLAMP)
323 mb = N_MEAN_CLAMP_VAL ;
324
325 zmode = 0 ;
326
327 if (((mb << MMULSHIFT) < QB) && (c < (uint32_t) numSamples))
328 {
329 zmode = 1 ;
330 k = lead (mb) - BITOFF + ((mb + MOFF) >> MDENSHIFT) ;
331 mz = ((1 << k) - 1) & wb_local ;
332
333 n = dyn_get (in, &bitPos, mz, k) ;
334
335 RequireAction (c+n <= (uint32_t) numSamples, status = kALAC_ParamError ; goto Exit ;) ;
336
337 for (j = 0 ; j < n ; j++)
338 {
339 *outPtr++ = 0 ;
340 ++c ;
341 }
342
343 if (n >= 65535)
344 zmode = 0 ;
345
346 mb = 0 ;
347 }
348 }
349
350 Exit:
351 *outNumBits = (bitPos - startPos) ;
352 BitBufferAdvance (bitstream, *outNumBits) ;
353 RequireAction (bitstream->cur <= bitstream->end, status = kALAC_ParamError ;) ;
354
355 return status ;
356 }
357