Modules/audioop.c

   1
   2 /* audioopmodule - Module to detect peak values in arrays */
   3
   4 #include "Python.h"
   5
   6 #if SIZEOF_INT == 4
   7 typedef int Py_Int32;
   8 typedef unsigned int Py_UInt32;
   9 #else
  10 #if SIZEOF_LONG == 4
  11 typedef long Py_Int32;
  12 typedef unsigned long Py_UInt32;
  13 #else
  14 #error "No 4-byte integral type"
  15 #endif
  16 #endif
  17
  18 typedef short PyInt16;
  19
  20 #if defined(__CHAR_UNSIGNED__)
  21 #if defined(signed)
  22 /* This module currently does not work on systems where only unsigned
  23    characters are available.  Take it out of Setup.  Sorry. */
  24 #endif
  25 #endif
  26
  27 /* Code shamelessly stolen from sox, 12.17.7, g711.c
  28 ** (c) Craig Reese, Joe Campbell and Jeff Poskanzer 1989 */
  29
  30 /* From g711.c:
  31  *
  32  * December 30, 1994:
  33  * Functions linear2alaw, linear2ulaw have been updated to correctly
  34  * convert unquantized 16 bit values.
  35  * Tables for direct u- to A-law and A- to u-law conversions have been
  36  * corrected.
  37  * Borge Lindberg, Center for PersonKommunikation, Aalborg University.
  38  * bli@cpk.auc.dk
  39  *
  40  */
  41 #define BIAS 0x84   /* define the add-in bias for 16 bit samples */
  42 #define CLIP 32635
  43 #define SIGN_BIT        (0x80)          /* Sign bit for a A-law byte. */
  44 #define QUANT_MASK      (0xf)           /* Quantization field mask. */
  45 #define SEG_SHIFT       (4)             /* Left shift for segment number. */
  46 #define SEG_MASK        (0x70)          /* Segment field mask. */
  47
  48 static PyInt16 seg_aend[8] = {0x1F, 0x3F, 0x7F, 0xFF,
  49                               0x1FF, 0x3FF, 0x7FF, 0xFFF};
  50 static PyInt16 seg_uend[8] = {0x3F, 0x7F, 0xFF, 0x1FF,
  51                               0x3FF, 0x7FF, 0xFFF, 0x1FFF};
  52
  53 static PyInt16
  54 search(PyInt16 val, PyInt16 *table, int size)
  55 {
  56     int i;
  57
  58     for (i = 0; i < size; i++) {
  59         if (val <= *table++)
  60             return (i);
  61     }
  62     return (size);
  63 }
  64 #define st_ulaw2linear16(uc) (_st_ulaw2linear16[uc])
  65 #define st_alaw2linear16(uc) (_st_alaw2linear16[uc])
  66
  67 static PyInt16 _st_ulaw2linear16[256] = {
  68     -32124,  -31100,  -30076,  -29052,  -28028,  -27004,  -25980,
  69     -24956,  -23932,  -22908,  -21884,  -20860,  -19836,  -18812,
  70     -17788,  -16764,  -15996,  -15484,  -14972,  -14460,  -13948,
  71     -13436,  -12924,  -12412,  -11900,  -11388,  -10876,  -10364,
  72      -9852,   -9340,   -8828,   -8316,   -7932,   -7676,   -7420,
  73      -7164,   -6908,   -6652,   -6396,   -6140,   -5884,   -5628,
  74      -5372,   -5116,   -4860,   -4604,   -4348,   -4092,   -3900,
  75      -3772,   -3644,   -3516,   -3388,   -3260,   -3132,   -3004,
  76      -2876,   -2748,   -2620,   -2492,   -2364,   -2236,   -2108,
  77      -1980,   -1884,   -1820,   -1756,   -1692,   -1628,   -1564,
  78      -1500,   -1436,   -1372,   -1308,   -1244,   -1180,   -1116,
  79      -1052,    -988,    -924,    -876,    -844,    -812,    -780,
  80       -748,    -716,    -684,    -652,    -620,    -588,    -556,
  81       -524,    -492,    -460,    -428,    -396,    -372,    -356,
  82       -340,    -324,    -308,    -292,    -276,    -260,    -244,
  83       -228,    -212,    -196,    -180,    -164,    -148,    -132,
  84       -120,    -112,    -104,     -96,     -88,     -80,     -72,
  85        -64,     -56,     -48,     -40,     -32,     -24,     -16,
  86     -8,       0,   32124,   31100,   30076,   29052,   28028,
  87      27004,   25980,   24956,   23932,   22908,   21884,   20860,
  88      19836,   18812,   17788,   16764,   15996,   15484,   14972,
  89      14460,   13948,   13436,   12924,   12412,   11900,   11388,
  90      10876,   10364,    9852,    9340,    8828,    8316,    7932,
  91       7676,    7420,    7164,    6908,    6652,    6396,    6140,
  92       5884,    5628,    5372,    5116,    4860,    4604,    4348,
  93       4092,    3900,    3772,    3644,    3516,    3388,    3260,
  94       3132,    3004,    2876,    2748,    2620,    2492,    2364,
  95       2236,    2108,    1980,    1884,    1820,    1756,    1692,
  96       1628,    1564,    1500,    1436,    1372,    1308,    1244,
  97       1180,    1116,    1052,     988,     924,     876,     844,
  98        812,     780,     748,     716,     684,     652,     620,
  99        588,     556,     524,     492,     460,     428,     396,
 100        372,     356,     340,     324,     308,     292,     276,
 101        260,     244,     228,     212,     196,     180,     164,
 102        148,     132,     120,     112,     104,      96,      88,
 103     80,      72,      64,      56,      48,      40,      32,
 104     24,      16,       8,       0
 105 };
 106
 107 /*
 108  * linear2ulaw() accepts a 14-bit signed integer and encodes it as u-law data
 109  * stored in a unsigned char.  This function should only be called with
 110  * the data shifted such that it only contains information in the lower
 111  * 14-bits.
 112  *
 113  * In order to simplify the encoding process, the original linear magnitude
 114  * is biased by adding 33 which shifts the encoding range from (0 - 8158) to
 115  * (33 - 8191). The result can be seen in the following encoding table:
 116  *
 117  *      Biased Linear Input Code        Compressed Code
 118  *      ------------------------        ---------------
 119  *      00000001wxyza                   000wxyz
 120  *      0000001wxyzab                   001wxyz
 121  *      000001wxyzabc                   010wxyz
 122  *      00001wxyzabcd                   011wxyz
 123  *      0001wxyzabcde                   100wxyz
 124  *      001wxyzabcdef                   101wxyz
 125  *      01wxyzabcdefg                   110wxyz
 126  *      1wxyzabcdefgh                   111wxyz
 127  *
 128  * Each biased linear code has a leading 1 which identifies the segment
 129  * number. The value of the segment number is equal to 7 minus the number
 130  * of leading 0's. The quantization interval is directly available as the
 131  * four bits wxyz.  * The trailing bits (a - h) are ignored.
 132  *
 133  * Ordinarily the complement of the resulting code word is used for
 134  * transmission, and so the code word is complemented before it is returned.
 135  *
 136  * For further information see John C. Bellamy's Digital Telephony, 1982,
 137  * John Wiley & Sons, pps 98-111 and 472-476.
 138  */
 139 static unsigned char
 140 st_14linear2ulaw(PyInt16 pcm_val)       /* 2's complement (14-bit range) */
 141 {
 142     PyInt16         mask;
 143     PyInt16         seg;
 144     unsigned char   uval;
 145
 146     /* The original sox code does this in the calling function, not here */
 147     pcm_val = pcm_val >> 2;
 148
 149     /* u-law inverts all bits */
 150     /* Get the sign and the magnitude of the value. */
 151     if (pcm_val < 0) {
 152         pcm_val = -pcm_val;
 153         mask = 0x7F;
 154     } else {
 155         mask = 0xFF;
 156     }
 157     if ( pcm_val > CLIP ) pcm_val = CLIP;           /* clip the magnitude */
 158     pcm_val += (BIAS >> 2);
 159
 160     /* Convert the scaled magnitude to segment number. */
 161     seg = search(pcm_val, seg_uend, 8);
 162
 163     /*
 164      * Combine the sign, segment, quantization bits;
 165      * and complement the code word.
 166      */
 167     if (seg >= 8)           /* out of range, return maximum value. */
 168         return (unsigned char) (0x7F ^ mask);
 169     else {
 170         uval = (unsigned char) (seg << 4) | ((pcm_val >> (seg + 1)) & 0xF);
 171         return (uval ^ mask);
 172     }
 173
 174 }
 175
 176 static PyInt16 _st_alaw2linear16[256] = {
 177      -5504,   -5248,   -6016,   -5760,   -4480,   -4224,   -4992,
 178      -4736,   -7552,   -7296,   -8064,   -7808,   -6528,   -6272,
 179      -7040,   -6784,   -2752,   -2624,   -3008,   -2880,   -2240,
 180      -2112,   -2496,   -2368,   -3776,   -3648,   -4032,   -3904,
 181      -3264,   -3136,   -3520,   -3392,  -22016,  -20992,  -24064,
 182     -23040,  -17920,  -16896,  -19968,  -18944,  -30208,  -29184,
 183     -32256,  -31232,  -26112,  -25088,  -28160,  -27136,  -11008,
 184     -10496,  -12032,  -11520,   -8960,   -8448,   -9984,   -9472,
 185     -15104,  -14592,  -16128,  -15616,  -13056,  -12544,  -14080,
 186     -13568,    -344,    -328,    -376,    -360,    -280,    -264,
 187       -312,    -296,    -472,    -456,    -504,    -488,    -408,
 188       -392,    -440,    -424,     -88,     -72,    -120,    -104,
 189        -24,      -8,     -56,     -40,    -216,    -200,    -248,
 190       -232,    -152,    -136,    -184,    -168,   -1376,   -1312,
 191      -1504,   -1440,   -1120,   -1056,   -1248,   -1184,   -1888,
 192      -1824,   -2016,   -1952,   -1632,   -1568,   -1760,   -1696,
 193       -688,    -656,    -752,    -720,    -560,    -528,    -624,
 194       -592,    -944,    -912,   -1008,    -976,    -816,    -784,
 195       -880,    -848,    5504,    5248,    6016,    5760,    4480,
 196       4224,    4992,    4736,    7552,    7296,    8064,    7808,
 197       6528,    6272,    7040,    6784,    2752,    2624,    3008,
 198       2880,    2240,    2112,    2496,    2368,    3776,    3648,
 199       4032,    3904,    3264,    3136,    3520,    3392,   22016,
 200      20992,   24064,   23040,   17920,   16896,   19968,   18944,
 201      30208,   29184,   32256,   31232,   26112,   25088,   28160,
 202      27136,   11008,   10496,   12032,   11520,    8960,    8448,
 203       9984,    9472,   15104,   14592,   16128,   15616,   13056,
 204      12544,   14080,   13568,     344,     328,     376,     360,
 205        280,     264,     312,     296,     472,     456,     504,
 206        488,     408,     392,     440,     424,      88,      72,
 207        120,     104,      24,       8,      56,      40,     216,
 208        200,     248,     232,     152,     136,     184,     168,
 209       1376,    1312,    1504,    1440,    1120,    1056,    1248,
 210       1184,    1888,    1824,    2016,    1952,    1632,    1568,
 211       1760,    1696,     688,     656,     752,     720,     560,
 212        528,     624,     592,     944,     912,    1008,     976,
 213        816,     784,     880,     848
 214 };
 215
 216 /*
 217  * linear2alaw() accepts an 13-bit signed integer and encodes it as A-law data
 218  * stored in a unsigned char.  This function should only be called with
 219  * the data shifted such that it only contains information in the lower
 220  * 13-bits.
 221  *
 222  *              Linear Input Code       Compressed Code
 223  *      ------------------------        ---------------
 224  *      0000000wxyza                    000wxyz
 225  *      0000001wxyza                    001wxyz
 226  *      000001wxyzab                    010wxyz
 227  *      00001wxyzabc                    011wxyz
 228  *      0001wxyzabcd                    100wxyz
 229  *      001wxyzabcde                    101wxyz
 230  *      01wxyzabcdef                    110wxyz
 231  *      1wxyzabcdefg                    111wxyz
 232  *
 233  * For further information see John C. Bellamy's Digital Telephony, 1982,
 234  * John Wiley & Sons, pps 98-111 and 472-476.
 235  */
 236 static unsigned char
 237 st_linear2alaw(PyInt16 pcm_val) /* 2's complement (13-bit range) */
 238 {
 239     PyInt16         mask;
 240     short           seg;
 241     unsigned char   aval;
 242
 243     /* The original sox code does this in the calling function, not here */
 244     pcm_val = pcm_val >> 3;
 245
 246     /* A-law using even bit inversion */
 247     if (pcm_val >= 0) {
 248         mask = 0xD5;            /* sign (7th) bit = 1 */
 249     } else {
 250         mask = 0x55;            /* sign bit = 0 */
 251         pcm_val = -pcm_val - 1;
 252     }
 253
 254     /* Convert the scaled magnitude to segment number. */
 255     seg = search(pcm_val, seg_aend, 8);
 256
 257     /* Combine the sign, segment, and quantization bits. */
 258
 259     if (seg >= 8)           /* out of range, return maximum value. */
 260         return (unsigned char) (0x7F ^ mask);
 261     else {
 262         aval = (unsigned char) seg << SEG_SHIFT;
 263         if (seg < 2)
 264             aval |= (pcm_val >> 1) & QUANT_MASK;
 265         else
 266             aval |= (pcm_val >> seg) & QUANT_MASK;
 267         return (aval ^ mask);
 268     }
 269 }
 270 /* End of code taken from sox */
 271
 272 /* Intel ADPCM step variation table */
 273 static int indexTable[16] = {
 274     -1, -1, -1, -1, 2, 4, 6, 8,
 275     -1, -1, -1, -1, 2, 4, 6, 8,
 276 };
 277
 278 static int stepsizeTable[89] = {
 279     7, 8, 9, 10, 11, 12, 13, 14, 16, 17,
 280     19, 21, 23, 25, 28, 31, 34, 37, 41, 45,
 281     50, 55, 60, 66, 73, 80, 88, 97, 107, 118,
 282     130, 143, 157, 173, 190, 209, 230, 253, 279, 307,
 283     337, 371, 408, 449, 494, 544, 598, 658, 724, 796,
 284     876, 963, 1060, 1166, 1282, 1411, 1552, 1707, 1878, 2066,
 285     2272, 2499, 2749, 3024, 3327, 3660, 4026, 4428, 4871, 5358,
 286     5894, 6484, 7132, 7845, 8630, 9493, 10442, 11487, 12635, 13899,
 287     15289, 16818, 18500, 20350, 22385, 24623, 27086, 29794, 32767
 288 };
 289
 290 #define CHARP(cp, i) ((signed char *)(cp+i))
 291 #define SHORTP(cp, i) ((short *)(cp+i))
 292 #define LONGP(cp, i) ((Py_Int32 *)(cp+i))
 293
 294
 295
 296 static PyObject *AudioopError;
 297
 298 static PyObject *
 299 audioop_getsample(PyObject *self, PyObject *args)
 300 {
 301     signed char *cp;
 302     int len, size, val = 0;
 303     int i;
 304
 305     if ( !PyArg_ParseTuple(args, "s#ii:getsample", &cp, &len, &size, &i) )
 306         return 0;
 307     if ( size != 1 && size != 2 && size != 4 ) {
 308         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 309         return 0;
 310     }
 311     if ( i < 0 || i >= len/size ) {
 312         PyErr_SetString(AudioopError, "Index out of range");
 313         return 0;
 314     }
 315     if ( size == 1 )      val = (int)*CHARP(cp, i);
 316     else if ( size == 2 ) val = (int)*SHORTP(cp, i*2);
 317     else if ( size == 4 ) val = (int)*LONGP(cp, i*4);
 318     return PyLong_FromLong(val);
 319 }
 320
 321 static PyObject *
 322 audioop_max(PyObject *self, PyObject *args)
 323 {
 324     signed char *cp;
 325     int len, size, val = 0;
 326     int i;
 327     int max = 0;
 328
 329     if ( !PyArg_ParseTuple(args, "s#i:max", &cp, &len, &size) )
 330         return 0;
 331     if ( size != 1 && size != 2 && size != 4 ) {
 332         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 333         return 0;
 334     }
 335     for ( i=0; i<len; i+= size) {
 336         if ( size == 1 )      val = (int)*CHARP(cp, i);
 337         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
 338         else if ( size == 4 ) val = (int)*LONGP(cp, i);
 339         if ( val < 0 ) val = (-val);
 340         if ( val > max ) max = val;
 341     }
 342     return PyLong_FromLong(max);
 343 }
 344
 345 static PyObject *
 346 audioop_minmax(PyObject *self, PyObject *args)
 347 {
 348     signed char *cp;
 349     int len, size, val = 0;
 350     int i;
 351     int min = 0x7fffffff, max = -0x7fffffff;
 352
 353     if (!PyArg_ParseTuple(args, "s#i:minmax", &cp, &len, &size))
 354         return NULL;
 355     if (size != 1 && size != 2 && size != 4) {
 356         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 357         return NULL;
 358     }
 359     for (i = 0; i < len; i += size) {
 360         if (size == 1) val = (int) *CHARP(cp, i);
 361         else if (size == 2) val = (int) *SHORTP(cp, i);
 362         else if (size == 4) val = (int) *LONGP(cp, i);
 363         if (val > max) max = val;
 364         if (val < min) min = val;
 365     }
 366     return Py_BuildValue("(ii)", min, max);
 367 }
 368
 369 static PyObject *
 370 audioop_avg(PyObject *self, PyObject *args)
 371 {
 372     signed char *cp;
 373     int len, size, val = 0;
 374     int i;
 375     double avg = 0.0;
 376
 377     if ( !PyArg_ParseTuple(args, "s#i:avg", &cp, &len, &size) )
 378         return 0;
 379     if ( size != 1 && size != 2 && size != 4 ) {
 380         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 381         return 0;
 382     }
 383     for ( i=0; i<len; i+= size) {
 384         if ( size == 1 )      val = (int)*CHARP(cp, i);
 385         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
 386         else if ( size == 4 ) val = (int)*LONGP(cp, i);
 387         avg += val;
 388     }
 389     if ( len == 0 )
 390         val = 0;
 391     else
 392         val = (int)(avg / (double)(len/size));
 393     return PyLong_FromLong(val);
 394 }
 395
 396 static PyObject *
 397 audioop_rms(PyObject *self, PyObject *args)
 398 {
 399     signed char *cp;
 400     int len, size, val = 0;
 401     int i;
 402     double sum_squares = 0.0;
 403
 404     if ( !PyArg_ParseTuple(args, "s#i:rms", &cp, &len, &size) )
 405         return 0;
 406     if ( size != 1 && size != 2 && size != 4 ) {
 407         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 408         return 0;
 409     }
 410     for ( i=0; i<len; i+= size) {
 411         if ( size == 1 )      val = (int)*CHARP(cp, i);
 412         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
 413         else if ( size == 4 ) val = (int)*LONGP(cp, i);
 414         sum_squares += (double)val*(double)val;
 415     }
 416     if ( len == 0 )
 417         val = 0;
 418     else
 419         val = (int)sqrt(sum_squares / (double)(len/size));
 420     return PyLong_FromLong(val);
 421 }
 422
 423 static double _sum2(short *a, short *b, int len)
 424 {
 425     int i;
 426     double sum = 0.0;
 427
 428     for( i=0; i<len; i++) {
 429         sum = sum + (double)a[i]*(double)b[i];
 430     }
 431     return sum;
 432 }
 433
 434 /*
 435 ** Findfit tries to locate a sample within another sample. Its main use
 436 ** is in echo-cancellation (to find the feedback of the output signal in
 437 ** the input signal).
 438 ** The method used is as follows:
 439 **
 440 ** let R be the reference signal (length n) and A the input signal (length N)
 441 ** with N > n, and let all sums be over i from 0 to n-1.
 442 **
 443 ** Now, for each j in {0..N-n} we compute a factor fj so that -fj*R matches A
 444 ** as good as possible, i.e. sum( (A[j+i]+fj*R[i])^2 ) is minimal. This
 445 ** equation gives fj = sum( A[j+i]R[i] ) / sum(R[i]^2).
 446 **
 447 ** Next, we compute the relative distance between the original signal and
 448 ** the modified signal and minimize that over j:
 449 ** vj = sum( (A[j+i]-fj*R[i])^2 ) / sum( A[j+i]^2 )  =>
 450 ** vj = ( sum(A[j+i]^2)*sum(R[i]^2) - sum(A[j+i]R[i])^2 ) / sum( A[j+i]^2 )
 451 **
 452 ** In the code variables correspond as follows:
 453 ** cp1          A
 454 ** cp2          R
 455 ** len1         N
 456 ** len2         n
 457 ** aj_m1        A[j-1]
 458 ** aj_lm1       A[j+n-1]
 459 ** sum_ri_2     sum(R[i]^2)
 460 ** sum_aij_2    sum(A[i+j]^2)
 461 ** sum_aij_ri   sum(A[i+j]R[i])
 462 **
 463 ** sum_ri is calculated once, sum_aij_2 is updated each step and sum_aij_ri
 464 ** is completely recalculated each step.
 465 */
 466 static PyObject *
 467 audioop_findfit(PyObject *self, PyObject *args)
 468 {
 469     short *cp1, *cp2;
 470     int len1, len2;
 471     int j, best_j;
 472     double aj_m1, aj_lm1;
 473     double sum_ri_2, sum_aij_2, sum_aij_ri, result, best_result, factor;
 474
 475     /* Passing a short** for an 's' argument is correct only
 476        if the string contents is aligned for interpretation
 477        as short[]. Due to the definition of PyBytesObject,
 478        this is currently (Python 2.6) the case. */
 479     if ( !PyArg_ParseTuple(args, "s#s#:findfit",
 480                            (char**)&cp1, &len1, (char**)&cp2, &len2) )
 481         return 0;
 482     if ( len1 & 1 || len2 & 1 ) {
 483         PyErr_SetString(AudioopError, "Strings should be even-sized");
 484         return 0;
 485     }
 486     len1 >>= 1;
 487     len2 >>= 1;
 488
 489     if ( len1 < len2 ) {
 490         PyErr_SetString(AudioopError, "First sample should be longer");
 491         return 0;
 492     }
 493     sum_ri_2 = _sum2(cp2, cp2, len2);
 494     sum_aij_2 = _sum2(cp1, cp1, len2);
 495     sum_aij_ri = _sum2(cp1, cp2, len2);
 496
 497     result = (sum_ri_2*sum_aij_2 - sum_aij_ri*sum_aij_ri) / sum_aij_2;
 498
 499     best_result = result;
 500     best_j = 0;
 501     j = 0;
 502
 503     for ( j=1; j<=len1-len2; j++) {
 504         aj_m1 = (double)cp1[j-1];
 505         aj_lm1 = (double)cp1[j+len2-1];
 506
 507         sum_aij_2 = sum_aij_2 + aj_lm1*aj_lm1 - aj_m1*aj_m1;
 508         sum_aij_ri = _sum2(cp1+j, cp2, len2);
 509
 510         result = (sum_ri_2*sum_aij_2 - sum_aij_ri*sum_aij_ri)
 511             / sum_aij_2;
 512
 513         if ( result < best_result ) {
 514             best_result = result;
 515             best_j = j;
 516         }
 517
 518     }
 519
 520     factor = _sum2(cp1+best_j, cp2, len2) / sum_ri_2;
 521
 522     return Py_BuildValue("(if)", best_j, factor);
 523 }
 524
 525 /*
 526 ** findfactor finds a factor f so that the energy in A-fB is minimal.
 527 ** See the comment for findfit for details.
 528 */
 529 static PyObject *
 530 audioop_findfactor(PyObject *self, PyObject *args)
 531 {
 532     short *cp1, *cp2;
 533     int len1, len2;
 534     double sum_ri_2, sum_aij_ri, result;
 535
 536     if ( !PyArg_ParseTuple(args, "s#s#:findfactor",
 537                            (char**)&cp1, &len1, (char**)&cp2, &len2) )
 538         return 0;
 539     if ( len1 & 1 || len2 & 1 ) {
 540         PyErr_SetString(AudioopError, "Strings should be even-sized");
 541         return 0;
 542     }
 543     if ( len1 != len2 ) {
 544         PyErr_SetString(AudioopError, "Samples should be same size");
 545         return 0;
 546     }
 547     len2 >>= 1;
 548     sum_ri_2 = _sum2(cp2, cp2, len2);
 549     sum_aij_ri = _sum2(cp1, cp2, len2);
 550
 551     result = sum_aij_ri / sum_ri_2;
 552
 553     return PyFloat_FromDouble(result);
 554 }
 555
 556 /*
 557 ** findmax returns the index of the n-sized segment of the input sample
 558 ** that contains the most energy.
 559 */
 560 static PyObject *
 561 audioop_findmax(PyObject *self, PyObject *args)
 562 {
 563     short *cp1;
 564     int len1, len2;
 565     int j, best_j;
 566     double aj_m1, aj_lm1;
 567     double result, best_result;
 568
 569     if ( !PyArg_ParseTuple(args, "s#i:findmax",
 570                            (char**)&cp1, &len1, &len2) )
 571         return 0;
 572     if ( len1 & 1 ) {
 573         PyErr_SetString(AudioopError, "Strings should be even-sized");
 574         return 0;
 575     }
 576     len1 >>= 1;
 577
 578     if ( len2 < 0 || len1 < len2 ) {
 579         PyErr_SetString(AudioopError, "Input sample should be longer");
 580         return 0;
 581     }
 582
 583     result = _sum2(cp1, cp1, len2);
 584
 585     best_result = result;
 586     best_j = 0;
 587     j = 0;
 588
 589     for ( j=1; j<=len1-len2; j++) {
 590         aj_m1 = (double)cp1[j-1];
 591         aj_lm1 = (double)cp1[j+len2-1];
 592
 593         result = result + aj_lm1*aj_lm1 - aj_m1*aj_m1;
 594
 595         if ( result > best_result ) {
 596             best_result = result;
 597             best_j = j;
 598         }
 599
 600     }
 601
 602     return PyLong_FromLong(best_j);
 603 }
 604
 605 static PyObject *
 606 audioop_avgpp(PyObject *self, PyObject *args)
 607 {
 608     signed char *cp;
 609     int len, size, val = 0, prevval = 0, prevextremevalid = 0,
 610         prevextreme = 0;
 611     int i;
 612     double avg = 0.0;
 613     int diff, prevdiff, extremediff, nextreme = 0;
 614
 615     if ( !PyArg_ParseTuple(args, "s#i:avgpp", &cp, &len, &size) )
 616         return 0;
 617     if ( size != 1 && size != 2 && size != 4 ) {
 618         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 619         return 0;
 620     }
 621     /* Compute first delta value ahead. Also automatically makes us
 622     ** skip the first extreme value
 623     */
 624     if ( size == 1 )      prevval = (int)*CHARP(cp, 0);
 625     else if ( size == 2 ) prevval = (int)*SHORTP(cp, 0);
 626     else if ( size == 4 ) prevval = (int)*LONGP(cp, 0);
 627     if ( size == 1 )      val = (int)*CHARP(cp, size);
 628     else if ( size == 2 ) val = (int)*SHORTP(cp, size);
 629     else if ( size == 4 ) val = (int)*LONGP(cp, size);
 630     prevdiff = val - prevval;
 631
 632     for ( i=size; i<len; i+= size) {
 633         if ( size == 1 )      val = (int)*CHARP(cp, i);
 634         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
 635         else if ( size == 4 ) val = (int)*LONGP(cp, i);
 636         diff = val - prevval;
 637         if ( diff*prevdiff < 0 ) {
 638             /* Derivative changed sign. Compute difference to last
 639             ** extreme value and remember.
 640             */
 641             if ( prevextremevalid ) {
 642                 extremediff = prevval - prevextreme;
 643                 if ( extremediff < 0 )
 644                     extremediff = -extremediff;
 645                 avg += extremediff;
 646                 nextreme++;
 647             }
 648             prevextremevalid = 1;
 649             prevextreme = prevval;
 650         }
 651         prevval = val;
 652         if ( diff != 0 )
 653             prevdiff = diff;
 654     }
 655     if ( nextreme == 0 )
 656         val = 0;
 657     else
 658         val = (int)(avg / (double)nextreme);
 659     return PyLong_FromLong(val);
 660 }
 661
 662 static PyObject *
 663 audioop_maxpp(PyObject *self, PyObject *args)
 664 {
 665     signed char *cp;
 666     int len, size, val = 0, prevval = 0, prevextremevalid = 0,
 667         prevextreme = 0;
 668     int i;
 669     int max = 0;
 670     int diff, prevdiff, extremediff;
 671
 672     if ( !PyArg_ParseTuple(args, "s#i:maxpp", &cp, &len, &size) )
 673         return 0;
 674     if ( size != 1 && size != 2 && size != 4 ) {
 675         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 676         return 0;
 677     }
 678     /* Compute first delta value ahead. Also automatically makes us
 679     ** skip the first extreme value
 680     */
 681     if ( size == 1 )      prevval = (int)*CHARP(cp, 0);
 682     else if ( size == 2 ) prevval = (int)*SHORTP(cp, 0);
 683     else if ( size == 4 ) prevval = (int)*LONGP(cp, 0);
 684     if ( size == 1 )      val = (int)*CHARP(cp, size);
 685     else if ( size == 2 ) val = (int)*SHORTP(cp, size);
 686     else if ( size == 4 ) val = (int)*LONGP(cp, size);
 687     prevdiff = val - prevval;
 688
 689     for ( i=size; i<len; i+= size) {
 690         if ( size == 1 )      val = (int)*CHARP(cp, i);
 691         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
 692         else if ( size == 4 ) val = (int)*LONGP(cp, i);
 693         diff = val - prevval;
 694         if ( diff*prevdiff < 0 ) {
 695             /* Derivative changed sign. Compute difference to
 696             ** last extreme value and remember.
 697             */
 698             if ( prevextremevalid ) {
 699                 extremediff = prevval - prevextreme;
 700                 if ( extremediff < 0 )
 701                     extremediff = -extremediff;
 702                 if ( extremediff > max )
 703                     max = extremediff;
 704             }
 705             prevextremevalid = 1;
 706             prevextreme = prevval;
 707         }
 708         prevval = val;
 709         if ( diff != 0 )
 710             prevdiff = diff;
 711     }
 712     return PyLong_FromLong(max);
 713 }
 714
 715 static PyObject *
 716 audioop_cross(PyObject *self, PyObject *args)
 717 {
 718     signed char *cp;
 719     int len, size, val = 0;
 720     int i;
 721     int prevval, ncross;
 722
 723     if ( !PyArg_ParseTuple(args, "s#i:cross", &cp, &len, &size) )
 724         return 0;
 725     if ( size != 1 && size != 2 && size != 4 ) {
 726         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 727         return 0;
 728     }
 729     ncross = -1;
 730     prevval = 17; /* Anything <> 0,1 */
 731     for ( i=0; i<len; i+= size) {
 732         if ( size == 1 )      val = ((int)*CHARP(cp, i)) >> 7;
 733         else if ( size == 2 ) val = ((int)*SHORTP(cp, i)) >> 15;
 734         else if ( size == 4 ) val = ((int)*LONGP(cp, i)) >> 31;
 735         val = val & 1;
 736         if ( val != prevval ) ncross++;
 737         prevval = val;
 738     }
 739     return PyLong_FromLong(ncross);
 740 }
 741
 742 static PyObject *
 743 audioop_mul(PyObject *self, PyObject *args)
 744 {
 745     signed char *cp, *ncp;
 746     int len, size, val = 0;
 747     double factor, fval, maxval;
 748     PyObject *rv;
 749     int i;
 750
 751     if ( !PyArg_ParseTuple(args, "s#id:mul", &cp, &len, &size, &factor ) )
 752         return 0;
 753
 754     if ( size == 1 ) maxval = (double) 0x7f;
 755     else if ( size == 2 ) maxval = (double) 0x7fff;
 756     else if ( size == 4 ) maxval = (double) 0x7fffffff;
 757     else {
 758         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 759         return 0;
 760     }
 761
 762     rv = PyBytes_FromStringAndSize(NULL, len);
 763     if ( rv == 0 )
 764         return 0;
 765     ncp = (signed char *)PyBytes_AsString(rv);
 766
 767
 768     for ( i=0; i < len; i += size ) {
 769         if ( size == 1 )      val = (int)*CHARP(cp, i);
 770         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
 771         else if ( size == 4 ) val = (int)*LONGP(cp, i);
 772         fval = (double)val*factor;
 773         if ( fval > maxval ) fval = maxval;
 774         else if ( fval < -maxval ) fval = -maxval;
 775         val = (int)fval;
 776         if ( size == 1 )      *CHARP(ncp, i) = (signed char)val;
 777         else if ( size == 2 ) *SHORTP(ncp, i) = (short)val;
 778         else if ( size == 4 ) *LONGP(ncp, i) = (Py_Int32)val;
 779     }
 780     return rv;
 781 }
 782
 783 static PyObject *
 784 audioop_tomono(PyObject *self, PyObject *args)
 785 {
 786     Py_buffer pcp;
 787     signed char *cp, *ncp;
 788     int len, size, val1 = 0, val2 = 0;
 789     double fac1, fac2, fval, maxval;
 790     PyObject *rv;
 791     int i;
 792
 793     if ( !PyArg_ParseTuple(args, "s*idd:tomono",
 794                            &pcp, &size, &fac1, &fac2 ) )
 795         return 0;
 796     cp = pcp.buf;
 797     len = pcp.len;
 798
 799     if ( size == 1 ) maxval = (double) 0x7f;
 800     else if ( size == 2 ) maxval = (double) 0x7fff;
 801     else if ( size == 4 ) maxval = (double) 0x7fffffff;
 802     else {
 803         PyBuffer_Release(&pcp);
 804         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 805         return 0;
 806     }
 807
 808     rv = PyBytes_FromStringAndSize(NULL, len/2);
 809     if ( rv == 0 )
 810         return 0;
 811     ncp = (signed char *)PyBytes_AsString(rv);
 812
 813
 814     for ( i=0; i < len; i += size*2 ) {
 815         if ( size == 1 )      val1 = (int)*CHARP(cp, i);
 816         else if ( size == 2 ) val1 = (int)*SHORTP(cp, i);
 817         else if ( size == 4 ) val1 = (int)*LONGP(cp, i);
 818         if ( size == 1 )      val2 = (int)*CHARP(cp, i+1);
 819         else if ( size == 2 ) val2 = (int)*SHORTP(cp, i+2);
 820         else if ( size == 4 ) val2 = (int)*LONGP(cp, i+4);
 821         fval = (double)val1*fac1 + (double)val2*fac2;
 822         if ( fval > maxval ) fval = maxval;
 823         else if ( fval < -maxval ) fval = -maxval;
 824         val1 = (int)fval;
 825         if ( size == 1 )      *CHARP(ncp, i/2) = (signed char)val1;
 826         else if ( size == 2 ) *SHORTP(ncp, i/2) = (short)val1;
 827         else if ( size == 4 ) *LONGP(ncp, i/2)= (Py_Int32)val1;
 828     }
 829     PyBuffer_Release(&pcp);
 830     return rv;
 831 }
 832
 833 static PyObject *
 834 audioop_tostereo(PyObject *self, PyObject *args)
 835 {
 836     signed char *cp, *ncp;
 837     int len, size, val1, val2, val = 0;
 838     double fac1, fac2, fval, maxval;
 839     PyObject *rv;
 840     int i;
 841
 842     if ( !PyArg_ParseTuple(args, "s#idd:tostereo",
 843                            &cp, &len, &size, &fac1, &fac2 ) )
 844         return 0;
 845
 846     if ( size == 1 ) maxval = (double) 0x7f;
 847     else if ( size == 2 ) maxval = (double) 0x7fff;
 848     else if ( size == 4 ) maxval = (double) 0x7fffffff;
 849     else {
 850         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 851         return 0;
 852     }
 853
 854     if (len > INT_MAX/2) {
 855         PyErr_SetString(PyExc_MemoryError,
 856                         "not enough memory for output buffer");
 857         return 0;
 858     }
 859
 860     rv = PyBytes_FromStringAndSize(NULL, len*2);
 861     if ( rv == 0 )
 862         return 0;
 863     ncp = (signed char *)PyBytes_AsString(rv);
 864
 865
 866     for ( i=0; i < len; i += size ) {
 867         if ( size == 1 )      val = (int)*CHARP(cp, i);
 868         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
 869         else if ( size == 4 ) val = (int)*LONGP(cp, i);
 870
 871         fval = (double)val*fac1;
 872         if ( fval > maxval ) fval = maxval;
 873         else if ( fval < -maxval ) fval = -maxval;
 874         val1 = (int)fval;
 875
 876         fval = (double)val*fac2;
 877         if ( fval > maxval ) fval = maxval;
 878         else if ( fval < -maxval ) fval = -maxval;
 879         val2 = (int)fval;
 880
 881         if ( size == 1 )      *CHARP(ncp, i*2) = (signed char)val1;
 882         else if ( size == 2 ) *SHORTP(ncp, i*2) = (short)val1;
 883         else if ( size == 4 ) *LONGP(ncp, i*2) = (Py_Int32)val1;
 884
 885         if ( size == 1 )      *CHARP(ncp, i*2+1) = (signed char)val2;
 886         else if ( size == 2 ) *SHORTP(ncp, i*2+2) = (short)val2;
 887         else if ( size == 4 ) *LONGP(ncp, i*2+4) = (Py_Int32)val2;
 888     }
 889     return rv;
 890 }
 891
 892 static PyObject *
 893 audioop_add(PyObject *self, PyObject *args)
 894 {
 895     signed char *cp1, *cp2, *ncp;
 896     int len1, len2, size, val1 = 0, val2 = 0, maxval, newval;
 897     PyObject *rv;
 898     int i;
 899
 900     if ( !PyArg_ParseTuple(args, "s#s#i:add",
 901                       &cp1, &len1, &cp2, &len2, &size ) )
 902         return 0;
 903
 904     if ( len1 != len2 ) {
 905         PyErr_SetString(AudioopError, "Lengths should be the same");
 906         return 0;
 907     }
 908
 909     if ( size == 1 ) maxval = 0x7f;
 910     else if ( size == 2 ) maxval = 0x7fff;
 911     else if ( size == 4 ) maxval = 0x7fffffff;
 912     else {
 913         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 914         return 0;
 915     }
 916
 917     rv = PyBytes_FromStringAndSize(NULL, len1);
 918     if ( rv == 0 )
 919         return 0;
 920     ncp = (signed char *)PyBytes_AsString(rv);
 921
 922     for ( i=0; i < len1; i += size ) {
 923         if ( size == 1 )      val1 = (int)*CHARP(cp1, i);
 924         else if ( size == 2 ) val1 = (int)*SHORTP(cp1, i);
 925         else if ( size == 4 ) val1 = (int)*LONGP(cp1, i);
 926
 927         if ( size == 1 )      val2 = (int)*CHARP(cp2, i);
 928         else if ( size == 2 ) val2 = (int)*SHORTP(cp2, i);
 929         else if ( size == 4 ) val2 = (int)*LONGP(cp2, i);
 930
 931         newval = val1 + val2;
 932         /* truncate in case of overflow */
 933         if (newval > maxval) newval = maxval;
 934         else if (newval < -maxval) newval = -maxval;
 935         else if (size == 4 && (newval^val1) < 0 && (newval^val2) < 0)
 936             newval = val1 > 0 ? maxval : - maxval;
 937
 938         if ( size == 1 )      *CHARP(ncp, i) = (signed char)newval;
 939         else if ( size == 2 ) *SHORTP(ncp, i) = (short)newval;
 940         else if ( size == 4 ) *LONGP(ncp, i) = (Py_Int32)newval;
 941     }
 942     return rv;
 943 }
 944
 945 static PyObject *
 946 audioop_bias(PyObject *self, PyObject *args)
 947 {
 948     signed char *cp, *ncp;
 949     int len, size, val = 0;
 950     PyObject *rv;
 951     int i;
 952     int bias;
 953
 954     if ( !PyArg_ParseTuple(args, "s#ii:bias",
 955                       &cp, &len, &size , &bias) )
 956         return 0;
 957
 958     if ( size != 1 && size != 2 && size != 4) {
 959         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 960         return 0;
 961     }
 962
 963     rv = PyBytes_FromStringAndSize(NULL, len);
 964     if ( rv == 0 )
 965         return 0;
 966     ncp = (signed char *)PyBytes_AsString(rv);
 967
 968
 969     for ( i=0; i < len; i += size ) {
 970         if ( size == 1 )      val = (int)*CHARP(cp, i);
 971         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
 972         else if ( size == 4 ) val = (int)*LONGP(cp, i);
 973
 974         if ( size == 1 )      *CHARP(ncp, i) = (signed char)(val+bias);
 975         else if ( size == 2 ) *SHORTP(ncp, i) = (short)(val+bias);
 976         else if ( size == 4 ) *LONGP(ncp, i) = (Py_Int32)(val+bias);
 977     }
 978     return rv;
 979 }
 980
 981 static PyObject *
 982 audioop_reverse(PyObject *self, PyObject *args)
 983 {
 984     signed char *cp;
 985     unsigned char *ncp;
 986     int len, size, val = 0;
 987     PyObject *rv;
 988     int i, j;
 989
 990     if ( !PyArg_ParseTuple(args, "s#i:reverse",
 991                       &cp, &len, &size) )
 992         return 0;
 993
 994     if ( size != 1 && size != 2 && size != 4 ) {
 995         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
 996         return 0;
 997     }
 998
 999     rv = PyBytes_FromStringAndSize(NULL, len);
1000     if ( rv == 0 )
1001         return 0;
1002     ncp = (unsigned char *)PyBytes_AsString(rv);
1003
1004     for ( i=0; i < len; i += size ) {
1005         if ( size == 1 )      val = ((int)*CHARP(cp, i)) << 8;
1006         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
1007         else if ( size == 4 ) val = ((int)*LONGP(cp, i)) >> 16;
1008
1009         j = len - i - size;
1010
1011         if ( size == 1 )      *CHARP(ncp, j) = (signed char)(val >> 8);
1012         else if ( size == 2 ) *SHORTP(ncp, j) = (short)(val);
1013         else if ( size == 4 ) *LONGP(ncp, j) = (Py_Int32)(val<<16);
1014     }
1015     return rv;
1016 }
1017
1018 static PyObject *
1019 audioop_lin2lin(PyObject *self, PyObject *args)
1020 {
1021     signed char *cp;
1022     unsigned char *ncp;
1023     int len, size, size2, val = 0;
1024     PyObject *rv;
1025     int i, j;
1026
1027     if ( !PyArg_ParseTuple(args, "s#ii:lin2lin",
1028                       &cp, &len, &size, &size2) )
1029         return 0;
1030
1031     if ( (size != 1 && size != 2 && size != 4) ||
1032          (size2 != 1 && size2 != 2 && size2 != 4)) {
1033         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
1034         return 0;
1035     }
1036
1037     if (len/size > INT_MAX/size2) {
1038         PyErr_SetString(PyExc_MemoryError,
1039                         "not enough memory for output buffer");
1040         return 0;
1041     }
1042     rv = PyBytes_FromStringAndSize(NULL, (len/size)*size2);
1043     if ( rv == 0 )
1044         return 0;
1045     ncp = (unsigned char *)PyBytes_AsString(rv);
1046
1047     for ( i=0, j=0; i < len; i += size, j += size2 ) {
1048         if ( size == 1 )      val = ((int)*CHARP(cp, i)) << 8;
1049         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
1050         else if ( size == 4 ) val = ((int)*LONGP(cp, i)) >> 16;
1051
1052         if ( size2 == 1 )  *CHARP(ncp, j) = (signed char)(val >> 8);
1053         else if ( size2 == 2 ) *SHORTP(ncp, j) = (short)(val);
1054         else if ( size2 == 4 ) *LONGP(ncp, j) = (Py_Int32)(val<<16);
1055     }
1056     return rv;
1057 }
1058
1059 static int
1060 gcd(int a, int b)
1061 {
1062     while (b > 0) {
1063         int tmp = a % b;
1064         a = b;
1065         b = tmp;
1066     }
1067     return a;
1068 }
1069
1070 static PyObject *
1071 audioop_ratecv(PyObject *self, PyObject *args)
1072 {
1073     char *cp, *ncp;
1074     int len, size, nchannels, inrate, outrate, weightA, weightB;
1075     int chan, d, *prev_i, *cur_i, cur_o;
1076     PyObject *state, *samps, *str, *rv = NULL;
1077     int bytes_per_frame;
1078
1079     weightA = 1;
1080     weightB = 0;
1081     if (!PyArg_ParseTuple(args, "s#iiiiO|ii:ratecv", &cp, &len, &size,
1082                           &nchannels, &inrate, &outrate, &state,
1083                           &weightA, &weightB))
1084         return NULL;
1085     if (size != 1 && size != 2 && size != 4) {
1086         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
1087         return NULL;
1088     }
1089     if (nchannels < 1) {
1090         PyErr_SetString(AudioopError, "# of channels should be >= 1");
1091         return NULL;
1092     }
1093     bytes_per_frame = size * nchannels;
1094     if (bytes_per_frame / nchannels != size) {
1095         /* This overflow test is rigorously correct because
1096            both multiplicands are >= 1.  Use the argument names
1097            from the docs for the error msg. */
1098         PyErr_SetString(PyExc_OverflowError,
1099                         "width * nchannels too big for a C int");
1100         return NULL;
1101     }
1102     if (weightA < 1 || weightB < 0) {
1103         PyErr_SetString(AudioopError,
1104             "weightA should be >= 1, weightB should be >= 0");
1105         return NULL;
1106     }
1107     if (len % bytes_per_frame != 0) {
1108         PyErr_SetString(AudioopError, "not a whole number of frames");
1109         return NULL;
1110     }
1111     if (inrate <= 0 || outrate <= 0) {
1112         PyErr_SetString(AudioopError, "sampling rate not > 0");
1113         return NULL;
1114     }
1115     /* divide inrate and outrate by their greatest common divisor */
1116     d = gcd(inrate, outrate);
1117     inrate /= d;
1118     outrate /= d;
1119
1120     if ((size_t)nchannels > PY_SIZE_MAX/sizeof(int)) {
1121         PyErr_SetString(PyExc_MemoryError,
1122                         "not enough memory for output buffer");
1123         return 0;
1124     }
1125     prev_i = (int *) malloc(nchannels * sizeof(int));
1126     cur_i = (int *) malloc(nchannels * sizeof(int));
1127     if (prev_i == NULL || cur_i == NULL) {
1128         (void) PyErr_NoMemory();
1129         goto exit;
1130     }
1131
1132     len /= bytes_per_frame; /* # of frames */
1133
1134     if (state == Py_None) {
1135         d = -outrate;
1136         for (chan = 0; chan < nchannels; chan++)
1137             prev_i[chan] = cur_i[chan] = 0;
1138     }
1139     else {
1140         if (!PyArg_ParseTuple(state,
1141                         "iO!;audioop.ratecv: illegal state argument",
1142                         &d, &PyTuple_Type, &samps))
1143             goto exit;
1144         if (PyTuple_Size(samps) != nchannels) {
1145             PyErr_SetString(AudioopError,
1146                             "illegal state argument");
1147             goto exit;
1148         }
1149         for (chan = 0; chan < nchannels; chan++) {
1150             if (!PyArg_ParseTuple(PyTuple_GetItem(samps, chan),
1151                                   "ii:ratecv", &prev_i[chan],
1152                                                &cur_i[chan]))
1153                 goto exit;
1154         }
1155     }
1156
1157     /* str <- Space for the output buffer. */
1158     {
1159         /* There are len input frames, so we need (mathematically)
1160            ceiling(len*outrate/inrate) output frames, and each frame
1161            requires bytes_per_frame bytes.  Computing this
1162            without spurious overflow is the challenge; we can
1163            settle for a reasonable upper bound, though, in this
1164            case ceiling(len/inrate) * outrate. */
1165
1166         /* compute ceiling(len/inrate) without overflow */
1167         int q = len > 0 ? 1 + (len - 1) / inrate : 0;
1168         if (outrate > INT_MAX / q / bytes_per_frame)
1169             str = NULL;
1170         else
1171             str = PyBytes_FromStringAndSize(NULL,
1172                                             q * outrate * bytes_per_frame);
1173
1174         if (str == NULL) {
1175             PyErr_SetString(PyExc_MemoryError,
1176                 "not enough memory for output buffer");
1177             goto exit;
1178         }
1179     }
1180     ncp = PyBytes_AsString(str);
1181
1182     for (;;) {
1183         while (d < 0) {
1184             if (len == 0) {
1185                 samps = PyTuple_New(nchannels);
1186                 if (samps == NULL)
1187                     goto exit;
1188                 for (chan = 0; chan < nchannels; chan++)
1189                     PyTuple_SetItem(samps, chan,
1190                         Py_BuildValue("(ii)",
1191                                       prev_i[chan],
1192                                       cur_i[chan]));
1193                 if (PyErr_Occurred())
1194                     goto exit;
1195                 /* We have checked before that the length
1196                  * of the string fits into int. */
1197                 len = (int)(ncp - PyBytes_AsString(str));
1198                 rv = PyBytes_FromStringAndSize
1199                     (PyBytes_AsString(str), len);
1200                 Py_DECREF(str);
1201                 str = rv;
1202                 if (str == NULL)
1203                     goto exit;
1204                 rv = Py_BuildValue("(O(iO))", str, d, samps);
1205                 Py_DECREF(samps);
1206                 Py_DECREF(str);
1207                 goto exit; /* return rv */
1208             }
1209             for (chan = 0; chan < nchannels; chan++) {
1210                 prev_i[chan] = cur_i[chan];
1211                 if (size == 1)
1212                     cur_i[chan] = ((int)*CHARP(cp, 0)) << 8;
1213                 else if (size == 2)
1214                     cur_i[chan] = (int)*SHORTP(cp, 0);
1215                 else if (size == 4)
1216                     cur_i[chan] = ((int)*LONGP(cp, 0)) >> 16;
1217                 cp += size;
1218                 /* implements a simple digital filter */
1219                 cur_i[chan] =
1220                     (weightA * cur_i[chan] +
1221                      weightB * prev_i[chan]) /
1222                     (weightA + weightB);
1223             }
1224             len--;
1225             d += outrate;
1226         }
1227         while (d >= 0) {
1228             for (chan = 0; chan < nchannels; chan++) {
1229                 cur_o = (prev_i[chan] * d +
1230                          cur_i[chan] * (outrate - d)) /
1231                     outrate;
1232                 if (size == 1)
1233                     *CHARP(ncp, 0) = (signed char)(cur_o >> 8);
1234                 else if (size == 2)
1235                     *SHORTP(ncp, 0) = (short)(cur_o);
1236                 else if (size == 4)
1237                     *LONGP(ncp, 0) = (Py_Int32)(cur_o<<16);
1238                 ncp += size;
1239             }
1240             d -= inrate;
1241         }
1242     }
1243   exit:
1244     if (prev_i != NULL)
1245         free(prev_i);
1246     if (cur_i != NULL)
1247         free(cur_i);
1248     return rv;
1249 }
1250
1251 static PyObject *
1252 audioop_lin2ulaw(PyObject *self, PyObject *args)
1253 {
1254     signed char *cp;
1255     unsigned char *ncp;
1256     int len, size, val = 0;
1257     PyObject *rv;
1258     int i;
1259
1260     if ( !PyArg_ParseTuple(args, "s#i:lin2ulaw",
1261                            &cp, &len, &size) )
1262         return 0 ;
1263
1264     if ( size != 1 && size != 2 && size != 4) {
1265         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
1266         return 0;
1267     }
1268
1269     rv = PyBytes_FromStringAndSize(NULL, len/size);
1270     if ( rv == 0 )
1271         return 0;
1272     ncp = (unsigned char *)PyBytes_AsString(rv);
1273
1274     for ( i=0; i < len; i += size ) {
1275         if ( size == 1 )      val = ((int)*CHARP(cp, i)) << 8;
1276         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
1277         else if ( size == 4 ) val = ((int)*LONGP(cp, i)) >> 16;
1278
1279         *ncp++ = st_14linear2ulaw(val);
1280     }
1281     return rv;
1282 }
1283
1284 static PyObject *
1285 audioop_ulaw2lin(PyObject *self, PyObject *args)
1286 {
1287     unsigned char *cp;
1288     unsigned char cval;
1289     signed char *ncp;
1290     int len, size, val;
1291     PyObject *rv;
1292     int i;
1293
1294     if ( !PyArg_ParseTuple(args, "s#i:ulaw2lin",
1295                            &cp, &len, &size) )
1296         return 0;
1297
1298     if ( size != 1 && size != 2 && size != 4) {
1299         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
1300         return 0;
1301     }
1302
1303     if (len > INT_MAX/size) {
1304         PyErr_SetString(PyExc_MemoryError,
1305                         "not enough memory for output buffer");
1306         return 0;
1307     }
1308     rv = PyBytes_FromStringAndSize(NULL, len*size);
1309     if ( rv == 0 )
1310         return 0;
1311     ncp = (signed char *)PyBytes_AsString(rv);
1312
1313     for ( i=0; i < len*size; i += size ) {
1314         cval = *cp++;
1315         val = st_ulaw2linear16(cval);
1316
1317         if ( size == 1 )      *CHARP(ncp, i) = (signed char)(val >> 8);
1318         else if ( size == 2 ) *SHORTP(ncp, i) = (short)(val);
1319         else if ( size == 4 ) *LONGP(ncp, i) = (Py_Int32)(val<<16);
1320     }
1321     return rv;
1322 }
1323
1324 static PyObject *
1325 audioop_lin2alaw(PyObject *self, PyObject *args)
1326 {
1327     signed char *cp;
1328     unsigned char *ncp;
1329     int len, size, val = 0;
1330     PyObject *rv;
1331     int i;
1332
1333     if ( !PyArg_ParseTuple(args, "s#i:lin2alaw",
1334                            &cp, &len, &size) )
1335         return 0;
1336
1337     if ( size != 1 && size != 2 && size != 4) {
1338         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
1339         return 0;
1340     }
1341
1342     rv = PyBytes_FromStringAndSize(NULL, len/size);
1343     if ( rv == 0 )
1344         return 0;
1345     ncp = (unsigned char *)PyBytes_AsString(rv);
1346
1347     for ( i=0; i < len; i += size ) {
1348         if ( size == 1 )      val = ((int)*CHARP(cp, i)) << 8;
1349         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
1350         else if ( size == 4 ) val = ((int)*LONGP(cp, i)) >> 16;
1351
1352         *ncp++ = st_linear2alaw(val);
1353     }
1354     return rv;
1355 }
1356
1357 static PyObject *
1358 audioop_alaw2lin(PyObject *self, PyObject *args)
1359 {
1360     unsigned char *cp;
1361     unsigned char cval;
1362     signed char *ncp;
1363     int len, size, val;
1364     PyObject *rv;
1365     int i;
1366
1367     if ( !PyArg_ParseTuple(args, "s#i:alaw2lin",
1368                            &cp, &len, &size) )
1369         return 0;
1370
1371     if ( size != 1 && size != 2 && size != 4) {
1372         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
1373         return 0;
1374     }
1375
1376     if (len > INT_MAX/size) {
1377         PyErr_SetString(PyExc_MemoryError,
1378                         "not enough memory for output buffer");
1379         return 0;
1380     }
1381     rv = PyBytes_FromStringAndSize(NULL, len*size);
1382     if ( rv == 0 )
1383         return 0;
1384     ncp = (signed char *)PyBytes_AsString(rv);
1385
1386     for ( i=0; i < len*size; i += size ) {
1387         cval = *cp++;
1388         val = st_alaw2linear16(cval);
1389
1390         if ( size == 1 )      *CHARP(ncp, i) = (signed char)(val >> 8);
1391         else if ( size == 2 ) *SHORTP(ncp, i) = (short)(val);
1392         else if ( size == 4 ) *LONGP(ncp, i) = (Py_Int32)(val<<16);
1393     }
1394     return rv;
1395 }
1396
1397 static PyObject *
1398 audioop_lin2adpcm(PyObject *self, PyObject *args)
1399 {
1400     signed char *cp;
1401     signed char *ncp;
1402     int len, size, val = 0, step, valpred, delta,
1403         index, sign, vpdiff, diff;
1404     PyObject *rv, *state, *str;
1405     int i, outputbuffer = 0, bufferstep;
1406
1407     if ( !PyArg_ParseTuple(args, "s#iO:lin2adpcm",
1408                            &cp, &len, &size, &state) )
1409         return 0;
1410
1411
1412     if ( size != 1 && size != 2 && size != 4) {
1413         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
1414         return 0;
1415     }
1416
1417     str = PyBytes_FromStringAndSize(NULL, len/(size*2));
1418     if ( str == 0 )
1419         return 0;
1420     ncp = (signed char *)PyBytes_AsString(str);
1421
1422     /* Decode state, should have (value, step) */
1423     if ( state == Py_None ) {
1424         /* First time, it seems. Set defaults */
1425         valpred = 0;
1426         step = 7;
1427         index = 0;
1428     } else if ( !PyArg_ParseTuple(state, "ii", &valpred, &index) )
1429         return 0;
1430
1431     step = stepsizeTable[index];
1432     bufferstep = 1;
1433
1434     for ( i=0; i < len; i += size ) {
1435         if ( size == 1 )      val = ((int)*CHARP(cp, i)) << 8;
1436         else if ( size == 2 ) val = (int)*SHORTP(cp, i);
1437         else if ( size == 4 ) val = ((int)*LONGP(cp, i)) >> 16;
1438
1439         /* Step 1 - compute difference with previous value */
1440         diff = val - valpred;
1441         sign = (diff < 0) ? 8 : 0;
1442         if ( sign ) diff = (-diff);
1443
1444         /* Step 2 - Divide and clamp */
1445         /* Note:
1446         ** This code *approximately* computes:
1447         **    delta = diff*4/step;
1448         **    vpdiff = (delta+0.5)*step/4;
1449         ** but in shift step bits are dropped. The net result of this
1450         ** is that even if you have fast mul/div hardware you cannot
1451         ** put it to good use since the fixup would be too expensive.
1452         */
1453         delta = 0;
1454         vpdiff = (step >> 3);
1455
1456         if ( diff >= step ) {
1457             delta = 4;
1458             diff -= step;
1459             vpdiff += step;
1460         }
1461         step >>= 1;
1462         if ( diff >= step  ) {
1463             delta |= 2;
1464             diff -= step;
1465             vpdiff += step;
1466         }
1467         step >>= 1;
1468         if ( diff >= step ) {
1469             delta |= 1;
1470             vpdiff += step;
1471         }
1472
1473         /* Step 3 - Update previous value */
1474         if ( sign )
1475             valpred -= vpdiff;
1476         else
1477             valpred += vpdiff;
1478
1479         /* Step 4 - Clamp previous value to 16 bits */
1480         if ( valpred > 32767 )
1481             valpred = 32767;
1482         else if ( valpred < -32768 )
1483             valpred = -32768;
1484
1485         /* Step 5 - Assemble value, update index and step values */
1486         delta |= sign;
1487
1488         index += indexTable[delta];
1489         if ( index < 0 ) index = 0;
1490         if ( index > 88 ) index = 88;
1491         step = stepsizeTable[index];
1492
1493         /* Step 6 - Output value */
1494         if ( bufferstep ) {
1495             outputbuffer = (delta << 4) & 0xf0;
1496         } else {
1497             *ncp++ = (delta & 0x0f) | outputbuffer;
1498         }
1499         bufferstep = !bufferstep;
1500     }
1501     rv = Py_BuildValue("(O(ii))", str, valpred, index);
1502     Py_DECREF(str);
1503     return rv;
1504 }
1505
1506 static PyObject *
1507 audioop_adpcm2lin(PyObject *self, PyObject *args)
1508 {
1509     signed char *cp;
1510     signed char *ncp;
1511     int len, size, valpred, step, delta, index, sign, vpdiff;
1512     PyObject *rv, *str, *state;
1513     int i, inputbuffer = 0, bufferstep;
1514
1515     if ( !PyArg_ParseTuple(args, "s#iO:adpcm2lin",
1516                            &cp, &len, &size, &state) )
1517         return 0;
1518
1519     if ( size != 1 && size != 2 && size != 4) {
1520         PyErr_SetString(AudioopError, "Size should be 1, 2 or 4");
1521         return 0;
1522     }
1523
1524     /* Decode state, should have (value, step) */
1525     if ( state == Py_None ) {
1526         /* First time, it seems. Set defaults */
1527         valpred = 0;
1528         step = 7;
1529         index = 0;
1530     } else if ( !PyArg_ParseTuple(state, "ii", &valpred, &index) )
1531         return 0;
1532
1533     if (len > (INT_MAX/2)/size) {
1534         PyErr_SetString(PyExc_MemoryError,
1535                         "not enough memory for output buffer");
1536         return 0;
1537     }
1538     str = PyBytes_FromStringAndSize(NULL, len*size*2);
1539     if ( str == 0 )
1540         return 0;
1541     ncp = (signed char *)PyBytes_AsString(str);
1542
1543     step = stepsizeTable[index];
1544     bufferstep = 0;
1545
1546     for ( i=0; i < len*size*2; i += size ) {
1547         /* Step 1 - get the delta value and compute next index */
1548         if ( bufferstep ) {
1549             delta = inputbuffer & 0xf;
1550         } else {
1551             inputbuffer = *cp++;
1552             delta = (inputbuffer >> 4) & 0xf;
1553         }
1554
1555         bufferstep = !bufferstep;
1556
1557         /* Step 2 - Find new index value (for later) */
1558         index += indexTable[delta];
1559         if ( index < 0 ) index = 0;
1560         if ( index > 88 ) index = 88;
1561
1562         /* Step 3 - Separate sign and magnitude */
1563         sign = delta & 8;
1564         delta = delta & 7;
1565
1566         /* Step 4 - Compute difference and new predicted value */
1567         /*
1568         ** Computes 'vpdiff = (delta+0.5)*step/4', but see comment
1569         ** in adpcm_coder.
1570         */
1571         vpdiff = step >> 3;
1572         if ( delta & 4 ) vpdiff += step;
1573         if ( delta & 2 ) vpdiff += step>>1;
1574         if ( delta & 1 ) vpdiff += step>>2;
1575
1576         if ( sign )
1577             valpred -= vpdiff;
1578         else
1579             valpred += vpdiff;
1580
1581         /* Step 5 - clamp output value */
1582         if ( valpred > 32767 )
1583             valpred = 32767;
1584         else if ( valpred < -32768 )
1585             valpred = -32768;
1586
1587         /* Step 6 - Update step value */
1588         step = stepsizeTable[index];
1589
1590         /* Step 6 - Output value */
1591         if ( size == 1 ) *CHARP(ncp, i) = (signed char)(valpred >> 8);
1592         else if ( size == 2 ) *SHORTP(ncp, i) = (short)(valpred);
1593         else if ( size == 4 ) *LONGP(ncp, i) = (Py_Int32)(valpred<<16);
1594     }
1595
1596     rv = Py_BuildValue("(O(ii))", str, valpred, index);
1597     Py_DECREF(str);
1598     return rv;
1599 }
1600
1601 static PyMethodDef audioop_methods[] = {
1602     { "max", audioop_max, METH_VARARGS },
1603     { "minmax", audioop_minmax, METH_VARARGS },
1604     { "avg", audioop_avg, METH_VARARGS },
1605     { "maxpp", audioop_maxpp, METH_VARARGS },
1606     { "avgpp", audioop_avgpp, METH_VARARGS },
1607     { "rms", audioop_rms, METH_VARARGS },
1608     { "findfit", audioop_findfit, METH_VARARGS },
1609     { "findmax", audioop_findmax, METH_VARARGS },
1610     { "findfactor", audioop_findfactor, METH_VARARGS },
1611     { "cross", audioop_cross, METH_VARARGS },
1612     { "mul", audioop_mul, METH_VARARGS },
1613     { "add", audioop_add, METH_VARARGS },
1614     { "bias", audioop_bias, METH_VARARGS },
1615     { "ulaw2lin", audioop_ulaw2lin, METH_VARARGS },
1616     { "lin2ulaw", audioop_lin2ulaw, METH_VARARGS },
1617     { "alaw2lin", audioop_alaw2lin, METH_VARARGS },
1618     { "lin2alaw", audioop_lin2alaw, METH_VARARGS },
1619     { "lin2lin", audioop_lin2lin, METH_VARARGS },
1620     { "adpcm2lin", audioop_adpcm2lin, METH_VARARGS },
1621     { "lin2adpcm", audioop_lin2adpcm, METH_VARARGS },
1622     { "tomono", audioop_tomono, METH_VARARGS },
1623     { "tostereo", audioop_tostereo, METH_VARARGS },
1624     { "getsample", audioop_getsample, METH_VARARGS },
1625     { "reverse", audioop_reverse, METH_VARARGS },
1626     { "ratecv", audioop_ratecv, METH_VARARGS },
1627     { 0,          0 }
1628 };
1629
1630
1631 static struct PyModuleDef audioopmodule = {
1632     PyModuleDef_HEAD_INIT,
1633     "audioop",
1634     NULL,
1635     -1,
1636     audioop_methods,
1637     NULL,
1638     NULL,
1639     NULL,
1640     NULL
1641 };
1642
1643 PyMODINIT_FUNC
1644 PyInit_audioop(void)
1645 {
1646     PyObject *m, *d;
1647     m = PyModule_Create(&audioopmodule);
1648     if (m == NULL)
1649         return NULL;
1650     d = PyModule_GetDict(m);
1651     if (d == NULL)
1652         return NULL;
1653     AudioopError = PyErr_NewException("audioop.error", NULL, NULL);
1654     if (AudioopError != NULL)
1655          PyDict_SetItemString(d,"error",AudioopError);
1656     return m;
1657 }