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 #elif defined _MSC_VER
48 #define ALWAYS_INLINE __forceinline
49 #else
50 #define ALWAYS_INLINE
51 #endif
52
53
54 /* And on the subject of the CodeWarrior x86 compiler and inlining, I reworked a lot of this
55 to help the compiler out. In many cases this required manual inlining or a macro. Sorry
56 if it is ugly but the performance gains are well worth it.
57 - WSK 5/19/04
58 */
59
60 // note: implementing this with some kind of "count leading zeros" assembly is a big performance win
lead(int32_t m)61 static inline int32_t lead (int32_t m)
62 {
63 long j ;
64 unsigned long c = (1ul << 31) ;
65
66 for (j = 0 ; j < 32 ; j++)
67 {
68 if ((c & m) != 0)
69 break ;
70 c >>= 1 ;
71 }
72 return j ;
73 }
74
75 #define arithmin (a, b) ((a) < (b) ? (a) : (b))
76
lg3a(int32_t x)77 static inline int32_t ALWAYS_INLINE lg3a (int32_t x)
78 {
79 int32_t result ;
80
81 x += 3 ;
82 result = lead (x) ;
83
84 return 31 - result ;
85 }
86
abs_func(int32_t a)87 static inline int32_t ALWAYS_INLINE abs_func (int32_t a)
88 {
89 // note: the CW PPC intrinsic __abs () turns into these instructions so no need to try and use it
90 int32_t isneg = a >> 31 ;
91 int32_t xorval = a ^ isneg ;
92 int32_t result = xorval-isneg ;
93
94 return result ;
95 }
96
97 #if PRAGMA_MARK
98 #pragma mark -
99 #endif
100
dyn_code(int32_t m,int32_t k,int32_t n,uint32_t * outNumBits)101 static inline int32_t dyn_code (int32_t m, int32_t k, int32_t n, uint32_t *outNumBits)
102 {
103 uint32_t divx, mod, de ;
104 uint32_t numBits ;
105 uint32_t value ;
106
107 // Assert (n >= 0) ;
108
109 divx = n / m ;
110
111 if (divx >= MAX_PREFIX_16)
112 {
113 numBits = MAX_PREFIX_16 + MAX_DATATYPE_BITS_16 ;
114 value = (((1 << MAX_PREFIX_16) - 1) << MAX_DATATYPE_BITS_16) + n ;
115 }
116 else
117 {
118 mod = n%m ;
119 de = (mod == 0) ;
120 numBits = divx + k + 1 - de ;
121 value = (((1 << divx) - 1) << (numBits - divx)) + mod + 1 - de ;
122
123 // if coding this way is bigger than doing escape, then do escape
124 if (numBits > MAX_PREFIX_16 + MAX_DATATYPE_BITS_16)
125 {
126 numBits = MAX_PREFIX_16 + MAX_DATATYPE_BITS_16 ;
127 value = (((1 << MAX_PREFIX_16) - 1) << MAX_DATATYPE_BITS_16) + n ;
128 }
129 }
130
131 *outNumBits = numBits ;
132
133 return (int32_t) value ;
134 }
135
136
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)137 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)
138 {
139 uint32_t divx, mod, de ;
140 uint32_t numBits ;
141 uint32_t value ;
142 int32_t didOverflow = 0 ;
143
144 divx = n / m ;
145
146 if (divx < MAX_PREFIX_32)
147 {
148 mod = n - (m * divx) ;
149
150 de = (mod == 0) ;
151 numBits = divx + k + 1 - de ;
152 value = (((1 << divx) - 1) << (numBits - divx)) + mod + 1 - de ;
153 if (numBits > 25)
154 goto codeasescape ;
155 }
156 else
157 {
158 codeasescape:
159 numBits = MAX_PREFIX_32 ;
160 value = (((1 << MAX_PREFIX_32) - 1)) ;
161 *overflow = n ;
162 *overflowbits = maxbits ;
163 didOverflow = 1 ;
164 }
165
166 *outNumBits = numBits ;
167 *outValue = value ;
168
169 return didOverflow ;
170 }
171
172
dyn_jam_noDeref(unsigned char * out,uint32_t bitPos,uint32_t numBits,uint32_t value)173 static inline void ALWAYS_INLINE dyn_jam_noDeref (unsigned char *out, uint32_t bitPos, uint32_t numBits, uint32_t value)
174 {
175 uint32_t mask ;
176 uint32_t curr ;
177 uint32_t shift ;
178
179 //Assert (numBits <= 32) ;
180
181 curr = psf_get_be32 (out, bitPos >> 3) ;
182
183 shift = 32 - (bitPos & 7) - numBits ;
184
185 mask = ~0u >> (32 - numBits) ; // mask must be created in two steps to avoid compiler sequencing ambiguity
186 mask <<= shift ;
187
188 value = (value << shift) & mask ;
189 value |= curr & ~mask ;
190
191 psf_put_be32 (out, bitPos >> 3, value) ;
192 }
193
194
dyn_jam_noDeref_large(unsigned char * out,uint32_t bitPos,uint32_t numBits,uint32_t value)195 static inline void ALWAYS_INLINE dyn_jam_noDeref_large (unsigned char *out, uint32_t bitPos, uint32_t numBits, uint32_t value)
196 {
197 uint32_t w ;
198 uint32_t curr ;
199 uint32_t mask ;
200 int32_t shiftvalue = (32 - (bitPos & 7) - numBits) ;
201
202 //Assert (numBits <= 32) ;
203
204 curr = psf_get_be32 (out, bitPos >> 3) ;
205
206 if (shiftvalue < 0)
207 {
208 uint8_t tailbyte ;
209 uint8_t *tailptr ;
210
211 w = value >> -shiftvalue ;
212 mask = ~0u >> -shiftvalue ;
213 w |= (curr & ~mask) ;
214
215 tailptr = out + (bitPos >> 3) + 4 ;
216 tailbyte = (value << ((8+shiftvalue))) & 0xff ;
217 *tailptr = (uint8_t) tailbyte ;
218 }
219 else
220 {
221 mask = ~0u >> (32 - numBits) ;
222 mask <<= shiftvalue ; // mask must be created in two steps to avoid compiler sequencing ambiguity
223
224 w = (value << shiftvalue) & mask ;
225 w |= curr & ~mask ;
226 }
227
228 psf_put_be32 (out, bitPos >> 3, w) ;
229 }
230
231
dyn_comp(AGParamRecPtr params,int32_t * pc,BitBuffer * bitstream,int32_t numSamples,int32_t bitSize,uint32_t * outNumBits)232 int32_t dyn_comp (AGParamRecPtr params, int32_t * pc, BitBuffer * bitstream, int32_t numSamples, int32_t bitSize, uint32_t * outNumBits)
233 {
234 unsigned char * out ;
235 uint32_t bitPos, startPos ;
236 uint32_t m, k, n, c, mz, nz ;
237 uint32_t numBits ;
238 uint32_t value ;
239 int32_t del, zmode ;
240 uint32_t overflow, overflowbits ;
241 int32_t status ;
242
243 // shadow the variables in params so there's not the dereferencing overhead
244 uint32_t mb, pb, kb, wb ;
245 int32_t rowPos = 0 ;
246 int32_t rowSize = params->sw ;
247 int32_t rowJump = (params->fw) - rowSize ;
248 int32_t * inPtr = pc ;
249
250 *outNumBits = 0 ;
251 RequireAction ((bitSize >= 1) && (bitSize <= 32), return kALAC_ParamError ;) ;
252
253 out = bitstream->cur ;
254 startPos = bitstream->bitIndex ;
255 bitPos = startPos ;
256
257 mb = params->mb = params->mb0 ;
258 pb = params->pb ;
259 kb = params->kb ;
260 wb = params->wb ;
261 zmode = 0 ;
262
263 c = 0 ;
264 status = ALAC_noErr ;
265
266 while (c < (uint32_t) numSamples)
267 {
268 m = mb >> QBSHIFT ;
269 k = lg3a (m) ;
270 if (k > kb)
271 {
272 k = kb ;
273 }
274 m = (1 << k) - 1 ;
275
276 del = *inPtr++ ;
277 rowPos++ ;
278
279 n = (abs_func (del) << 1) - ((del >> 31) & 1) - zmode ;
280 //Assert (32-lead (n) <= bitSize) ;
281
282 if (dyn_code_32bit (bitSize, m, k, n, &numBits, &value, &overflow, &overflowbits))
283 {
284 dyn_jam_noDeref (out, bitPos, numBits, value) ;
285 bitPos += numBits ;
286 dyn_jam_noDeref_large (out, bitPos, overflowbits, overflow) ;
287 bitPos += overflowbits ;
288 }
289 else
290 {
291 dyn_jam_noDeref (out, bitPos, numBits, value) ;
292 bitPos += numBits ;
293 }
294
295 c++ ;
296 if (rowPos >= rowSize)
297 {
298 rowPos = 0 ;
299 inPtr += rowJump ;
300 }
301
302 mb = pb * (n + zmode) + mb - ((pb * mb) >> QBSHIFT) ;
303
304 // update mean tracking if it's overflowed
305 if (n > N_MAX_MEAN_CLAMP)
306 mb = N_MEAN_CLAMP_VAL ;
307
308 zmode = 0 ;
309
310 RequireAction (c <= (uint32_t) numSamples, status = kALAC_ParamError ; goto Exit ;) ;
311
312 if (((mb << MMULSHIFT) < QB) && (c < (uint32_t) numSamples))
313 {
314 zmode = 1 ;
315 nz = 0 ;
316
317 while (c < (uint32_t) numSamples && *inPtr == 0)
318 {
319 /* Take care of wrap-around globals. */
320 ++inPtr ;
321 ++nz ;
322 ++c ;
323 if (++rowPos >= rowSize)
324 {
325 rowPos = 0 ;
326 inPtr += rowJump ;
327 }
328
329 if (nz >= 65535)
330 {
331 zmode = 0 ;
332 break ;
333 }
334 }
335
336 k = lead (mb) - BITOFF + ((mb + MOFF) >> MDENSHIFT) ;
337 mz = ((1 << k) - 1) & wb ;
338
339 value = dyn_code (mz, k, nz, &numBits) ;
340 dyn_jam_noDeref (out, bitPos, numBits, value) ;
341 bitPos += numBits ;
342
343 mb = 0 ;
344 }
345 }
346
347 *outNumBits = (bitPos - startPos) ;
348 BitBufferAdvance (bitstream, *outNumBits) ;
349
350 Exit:
351 return status ;
352 }
353