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 61static 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 77static 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 87static 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 101static 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 137static 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 { 158codeasescape: 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 173static 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 195static 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 232int32_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 350Exit: 351 return status ; 352} 353