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