1 /*
2 * Copyright (c) 2011 Apple Inc. All rights reserved.
3 * Copyright (C) 2013-2014 Erik de Castro Lopo <erikd@mega-nerd.com>
4 *
5 * @APPLE_APACHE_LICENSE_HEADER_START@
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License") ;
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 *
19 * @APPLE_APACHE_LICENSE_HEADER_END@
20 */
21
22 /*
23 File: ag_enc.c
24
25 Contains: Adaptive Golomb encode routines.
26
27 Copyright: (c) 2001-2011 Apple, Inc.
28 */
29
30 #include "aglib.h"
31 #include "ALACBitUtilities.h"
32 #include "EndianPortable.h"
33 #include "ALACAudioTypes.h"
34
35 #include <math.h>
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <string.h>
39
40 #define CODE_TO_LONG_MAXBITS 32
41 #define N_MAX_MEAN_CLAMP 0xffff
42 #define N_MEAN_CLAMP_VAL 0xffff
43 #define REPORT_VAL 40
44
45 #if __GNUC__
46 #define ALWAYS_INLINE __attribute__ ((always_inline))
47 #else
48 #define ALWAYS_INLINE
49 #endif
50
51
52 /* And on the subject of the CodeWarrior x86 compiler and inlining, I reworked a lot of this
53 to help the compiler out. In many cases this required manual inlining or a macro. Sorry
54 if it is ugly but the performance gains are well worth it.
55 - WSK 5/19/04
56 */
57
58 // note: implementing this with some kind of "count leading zeros" assembly is a big performance win
lead(int32_t m)59 static inline int32_t lead (int32_t m)
60 {
61 long j ;
62 unsigned long c = (1ul << 31) ;
63
64 for (j = 0 ; j < 32 ; j++)
65 {
66 if ((c & m) != 0)
67 break ;
68 c >>= 1 ;
69 }
70 return j ;
71 }
72
73 #define arithmin (a, b) ((a) < (b) ? (a) : (b))
74
lg3a(int32_t x)75 static inline int32_t ALWAYS_INLINE lg3a (int32_t x)
76 {
77 int32_t result ;
78
79 x += 3 ;
80 result = lead (x) ;
81
82 return 31 - result ;
83 }
84
abs_func(int32_t a)85 static inline int32_t ALWAYS_INLINE abs_func (int32_t a)
86 {
87 // note: the CW PPC intrinsic __abs () turns into these instructions so no need to try and use it
88 int32_t isneg = a >> 31 ;
89 int32_t xorval = a ^ isneg ;
90 int32_t result = xorval-isneg ;
91
92 return result ;
93 }
94
95 #if PRAGMA_MARK
96 #pragma mark -
97 #endif
98
dyn_code(int32_t m,int32_t k,int32_t n,uint32_t * outNumBits)99 static inline int32_t dyn_code (int32_t m, int32_t k, int32_t n, uint32_t *outNumBits)
100 {
101 uint32_t divx, mod, de ;
102 uint32_t numBits ;
103 uint32_t value ;
104
105 // Assert (n >= 0) ;
106
107 divx = n / m ;
108
109 if (divx >= MAX_PREFIX_16)
110 {
111 numBits = MAX_PREFIX_16 + MAX_DATATYPE_BITS_16 ;
112 value = (((1 << MAX_PREFIX_16) - 1) << MAX_DATATYPE_BITS_16) + n ;
113 }
114 else
115 {
116 mod = n%m ;
117 de = (mod == 0) ;
118 numBits = divx + k + 1 - de ;
119 value = (((1 << divx) - 1) << (numBits - divx)) + mod + 1 - de ;
120
121 // if coding this way is bigger than doing escape, then do escape
122 if (numBits > MAX_PREFIX_16 + MAX_DATATYPE_BITS_16)
123 {
124 numBits = MAX_PREFIX_16 + MAX_DATATYPE_BITS_16 ;
125 value = (((1 << MAX_PREFIX_16) - 1) << MAX_DATATYPE_BITS_16) + n ;
126 }
127 }
128
129 *outNumBits = numBits ;
130
131 return (int32_t) value ;
132 }
133
134
dyn_code_32bit(int32_t maxbits,uint32_t m,uint32_t k,uint32_t n,uint32_t * outNumBits,uint32_t * outValue,uint32_t * overflow,uint32_t * overflowbits)135 static inline int32_t dyn_code_32bit (int32_t maxbits, uint32_t m, uint32_t k, uint32_t n, uint32_t *outNumBits, uint32_t *outValue, uint32_t *overflow, uint32_t *overflowbits)
136 {
137 uint32_t divx, mod, de ;
138 uint32_t numBits ;
139 uint32_t value ;
140 int32_t didOverflow = 0 ;
141
142 divx = n / m ;
143
144 if (divx < MAX_PREFIX_32)
145 {
146 mod = n - (m * divx) ;
147
148 de = (mod == 0) ;
149 numBits = divx + k + 1 - de ;
150 value = (((1 << divx) - 1) << (numBits - divx)) + mod + 1 - de ;
151 if (numBits > 25)
152 goto codeasescape ;
153 }
154 else
155 {
156 codeasescape:
157 numBits = MAX_PREFIX_32 ;
158 value = (((1 << MAX_PREFIX_32) - 1)) ;
159 *overflow = n ;
160 *overflowbits = maxbits ;
161 didOverflow = 1 ;
162 }
163
164 *outNumBits = numBits ;
165 *outValue = value ;
166
167 return didOverflow ;
168 }
169
170
dyn_jam_noDeref(unsigned char * out,uint32_t bitPos,uint32_t numBits,uint32_t value)171 static inline void ALWAYS_INLINE dyn_jam_noDeref (unsigned char *out, uint32_t bitPos, uint32_t numBits, uint32_t value)
172 {
173 uint32_t mask ;
174 uint32_t curr ;
175 uint32_t shift ;
176
177 //Assert (numBits <= 32) ;
178
179 curr = psf_get_be32 (out, bitPos >> 3) ;
180
181 shift = 32 - (bitPos & 7) - numBits ;
182
183 mask = ~0u >> (32 - numBits) ; // mask must be created in two steps to avoid compiler sequencing ambiguity
184 mask <<= shift ;
185
186 value = (value << shift) & mask ;
187 value |= curr & ~mask ;
188
189 psf_put_be32 (out, bitPos >> 3, value) ;
190 }
191
192
dyn_jam_noDeref_large(unsigned char * out,uint32_t bitPos,uint32_t numBits,uint32_t value)193 static inline void ALWAYS_INLINE dyn_jam_noDeref_large (unsigned char *out, uint32_t bitPos, uint32_t numBits, uint32_t value)
194 {
195 uint32_t w ;
196 uint32_t curr ;
197 uint32_t mask ;
198 int32_t shiftvalue = (32 - (bitPos & 7) - numBits) ;
199
200 //Assert (numBits <= 32) ;
201
202 curr = psf_get_be32 (out, bitPos >> 3) ;
203
204 if (shiftvalue < 0)
205 {
206 uint8_t tailbyte ;
207 uint8_t *tailptr ;
208
209 w = value >> -shiftvalue ;
210 mask = ~0u >> -shiftvalue ;
211 w |= (curr & ~mask) ;
212
213 tailptr = out + (bitPos >> 3) + 4 ;
214 tailbyte = (value << ((8+shiftvalue))) & 0xff ;
215 *tailptr = (uint8_t) tailbyte ;
216 }
217 else
218 {
219 mask = ~0u >> (32 - numBits) ;
220 mask <<= shiftvalue ; // mask must be created in two steps to avoid compiler sequencing ambiguity
221
222 w = (value << shiftvalue) & mask ;
223 w |= curr & ~mask ;
224 }
225
226 psf_put_be32 (out, bitPos >> 3, w) ;
227 }
228
229
dyn_comp(AGParamRecPtr params,int32_t * pc,BitBuffer * bitstream,int32_t numSamples,int32_t bitSize,uint32_t * outNumBits)230 int32_t dyn_comp (AGParamRecPtr params, int32_t * pc, BitBuffer * bitstream, int32_t numSamples, int32_t bitSize, uint32_t * outNumBits)
231 {
232 unsigned char * out ;
233 uint32_t bitPos, startPos ;
234 uint32_t m, k, n, c, mz, nz ;
235 uint32_t numBits ;
236 uint32_t value ;
237 int32_t del, zmode ;
238 uint32_t overflow, overflowbits ;
239 int32_t status ;
240
241 // shadow the variables in params so there's not the dereferencing overhead
242 uint32_t mb, pb, kb, wb ;
243 int32_t rowPos = 0 ;
244 int32_t rowSize = params->sw ;
245 int32_t rowJump = (params->fw) - rowSize ;
246 int32_t * inPtr = pc ;
247
248 *outNumBits = 0 ;
249 RequireAction ((bitSize >= 1) && (bitSize <= 32), return kALAC_ParamError ;) ;
250
251 out = bitstream->cur ;
252 startPos = bitstream->bitIndex ;
253 bitPos = startPos ;
254
255 mb = params->mb = params->mb0 ;
256 pb = params->pb ;
257 kb = params->kb ;
258 wb = params->wb ;
259 zmode = 0 ;
260
261 c = 0 ;
262 status = ALAC_noErr ;
263
264 while (c < (uint32_t) numSamples)
265 {
266 m = mb >> QBSHIFT ;
267 k = lg3a (m) ;
268 if (k > kb)
269 {
270 k = kb ;
271 }
272 m = (1 << k) - 1 ;
273
274 del = *inPtr++ ;
275 rowPos++ ;
276
277 n = (abs_func (del) << 1) - ((del >> 31) & 1) - zmode ;
278 //Assert (32-lead (n) <= bitSize) ;
279
280 if (dyn_code_32bit (bitSize, m, k, n, &numBits, &value, &overflow, &overflowbits))
281 {
282 dyn_jam_noDeref (out, bitPos, numBits, value) ;
283 bitPos += numBits ;
284 dyn_jam_noDeref_large (out, bitPos, overflowbits, overflow) ;
285 bitPos += overflowbits ;
286 }
287 else
288 {
289 dyn_jam_noDeref (out, bitPos, numBits, value) ;
290 bitPos += numBits ;
291 }
292
293 c++ ;
294 if (rowPos >= rowSize)
295 {
296 rowPos = 0 ;
297 inPtr += rowJump ;
298 }
299
300 mb = pb * (n + zmode) + mb - ((pb * mb) >> QBSHIFT) ;
301
302 // update mean tracking if it's overflowed
303 if (n > N_MAX_MEAN_CLAMP)
304 mb = N_MEAN_CLAMP_VAL ;
305
306 zmode = 0 ;
307
308 RequireAction (c <= (uint32_t) numSamples, status = kALAC_ParamError ; goto Exit ;) ;
309
310 if (((mb << MMULSHIFT) < QB) && (c < (uint32_t) numSamples))
311 {
312 zmode = 1 ;
313 nz = 0 ;
314
315 while (c < (uint32_t) numSamples && *inPtr == 0)
316 {
317 /* Take care of wrap-around globals. */
318 ++inPtr ;
319 ++nz ;
320 ++c ;
321 if (++rowPos >= rowSize)
322 {
323 rowPos = 0 ;
324 inPtr += rowJump ;
325 }
326
327 if (nz >= 65535)
328 {
329 zmode = 0 ;
330 break ;
331 }
332 }
333
334 k = lead (mb) - BITOFF + ((mb + MOFF) >> MDENSHIFT) ;
335 mz = ((1 << k) - 1) & wb ;
336
337 value = dyn_code (mz, k, nz, &numBits) ;
338 dyn_jam_noDeref (out, bitPos, numBits, value) ;
339 bitPos += numBits ;
340
341 mb = 0 ;
342 }
343 }
344
345 *outNumBits = (bitPos - startPos) ;
346 BitBufferAdvance (bitstream, *outNumBits) ;
347
348 Exit:
349 return status ;
350 }
351