DOSBox-X
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines
src/libs/decoders/stb_vorbis.h
00001 // Ogg Vorbis audio decoder - v1.19 - public domain
00002 // http://nothings.org/stb_vorbis/
00003 //
00004 // Original version written by Sean Barrett in 2007.
00005 //
00006 // Originally sponsored by RAD Game Tools. Seeking implementation
00007 // sponsored by Phillip Bennefall, Marc Andersen, Aaron Baker,
00008 // Elias Software, Aras Pranckevicius, and Sean Barrett.
00009 //
00010 // LICENSE
00011 //
00012 //   See end of file for license information.
00013 //
00014 // Limitations:
00015 //
00016 //   - floor 0 not supported (used in old ogg vorbis files pre-2004)
00017 //   - lossless sample-truncation at beginning ignored
00018 //   - cannot concatenate multiple vorbis streams
00019 //   - sample positions are 32-bit, limiting seekable 192Khz
00020 //       files to around 6 hours (Ogg supports 64-bit)
00021 //
00022 // Feature contributors:
00023 //    Dougall Johnson (sample-exact seeking)
00024 //
00025 // Bugfix/warning contributors:
00026 //    Terje Mathisen     Niklas Frykholm     Andy Hill
00027 //    Casey Muratori     John Bolton         Gargaj
00028 //    Laurent Gomila     Marc LeBlanc        Ronny Chevalier
00029 //    Bernhard Wodo      Evan Balster        github:alxprd
00030 //    Tom Beaumont       Ingo Leitgeb        Nicolas Guillemot
00031 //    Phillip Bennefall  Rohit               Thiago Goulart
00032 //    github:manxorist   saga musix          github:infatum
00033 //    Timur Gagiev       Maxwell Koo         Peter Waller
00034 //    github:audinowho   Dougall Johnson
00035 //
00036 // Partial history:
00037 //    1.19    - 2020-02-05 - warnings
00038 //    1.18    - 2020-02-02 - fix seek bugs; parse header comments; misc warnings etc.
00039 //    1.17    - 2019-07-08 - fix CVE-2019-13217..CVE-2019-13223 (by ForAllSecure)
00040 //    1.16    - 2019-03-04 - fix warnings
00041 //    1.15    - 2019-02-07 - explicit failure if Ogg Skeleton data is found
00042 //    1.14    - 2018-02-11 - delete bogus dealloca usage
00043 //    1.13    - 2018-01-29 - fix truncation of last frame (hopefully)
00044 //    1.12    - 2017-11-21 - limit residue begin/end to blocksize/2 to avoid large temp allocs in bad/corrupt files
00045 //    1.11    - 2017-07-23 - fix MinGW compilation
00046 //    1.10    - 2017-03-03 - more robust seeking; fix negative ilog(); clear error in open_memory
00047 //    1.09    - 2016-04-04 - back out 'truncation of last frame' fix from previous version
00048 //    1.08    - 2016-04-02 - warnings; setup memory leaks; truncation of last frame
00049 //    1.07    - 2015-01-16 - fixes for crashes on invalid files; warning fixes; const
00050 //    1.06    - 2015-08-31 - full, correct support for seeking API (Dougall Johnson)
00051 //                           some crash fixes when out of memory or with corrupt files
00052 //                           fix some inappropriately signed shifts
00053 //    1.05    - 2015-04-19 - don't define __forceinline if it's redundant
00054 //    1.04    - 2014-08-27 - fix missing const-correct case in API
00055 //    1.03    - 2014-08-07 - warning fixes
00056 //    1.02    - 2014-07-09 - declare qsort comparison as explicitly _cdecl in Windows
00057 //    1.01    - 2014-06-18 - fix stb_vorbis_get_samples_float (interleaved was correct)
00058 //    1.0     - 2014-05-26 - fix memory leaks; fix warnings; fix bugs in >2-channel;
00059 //                           (API change) report sample rate for decode-full-file funcs
00060 //
00061 // See end of file for full version history.
00062 
00063 
00065 //
00066 //  HEADER BEGINS HERE
00067 //
00068 
00069 #ifndef STB_VORBIS_INCLUDE_STB_VORBIS_H
00070 #define STB_VORBIS_INCLUDE_STB_VORBIS_H
00071 
00072 #if defined(STB_VORBIS_NO_CRT) && !defined(STB_VORBIS_NO_STDIO)
00073 #define STB_VORBIS_NO_STDIO 1
00074 #endif
00075 
00076 #ifndef STB_VORBIS_NO_STDIO
00077 #include <stdio.h>
00078 #endif
00079 
00080 #ifdef __cplusplus
00081 extern "C" {
00082 #endif
00083 
00085 
00086 // Individual stb_vorbis* handles are not thread-safe; you cannot decode from
00087 // them from multiple threads at the same time. However, you can have multiple
00088 // stb_vorbis* handles and decode from them independently in multiple thrads.
00089 
00090 
00092 
00093 // normally stb_vorbis uses malloc() to allocate memory at startup,
00094 // and alloca() to allocate temporary memory during a frame on the
00095 // stack. (Memory consumption will depend on the amount of setup
00096 // data in the file and how you set the compile flags for speed
00097 // vs. size. In my test files the maximal-size usage is ~150KB.)
00098 //
00099 // You can modify the wrapper functions in the source (setup_malloc,
00100 // setup_temp_malloc, temp_malloc) to change this behavior, or you
00101 // can use a simpler allocation model: you pass in a buffer from
00102 // which stb_vorbis will allocate _all_ its memory (including the
00103 // temp memory). "open" may fail with a VORBIS_outofmem if you
00104 // do not pass in enough data; there is no way to determine how
00105 // much you do need except to succeed (at which point you can
00106 // query get_info to find the exact amount required. yes I know
00107 // this is lame).
00108 //
00109 // If you pass in a non-NULL buffer of the type below, allocation
00110 // will occur from it as described above. Otherwise just pass NULL
00111 // to use malloc()/alloca()
00112 
00113 typedef struct
00114 {
00115    char *alloc_buffer;
00116    int   alloc_buffer_length_in_bytes;
00117 } stb_vorbis_alloc;
00118 
00119 
00121 
00122 typedef struct stb_vorbis stb_vorbis;
00123 
00124 typedef struct
00125 {
00126    unsigned int sample_rate;
00127    int channels;
00128 
00129    unsigned int setup_memory_required;
00130    unsigned int setup_temp_memory_required;
00131    unsigned int temp_memory_required;
00132 
00133    int max_frame_size;
00134 } stb_vorbis_info;
00135 
00136 typedef struct
00137 {
00138    char *vendor;
00139 
00140    int comment_list_length;
00141    char **comment_list;
00142 } stb_vorbis_comment;
00143 
00144 // get general information about the file
00145 extern stb_vorbis_info stb_vorbis_get_info(stb_vorbis *f);
00146 
00147 // get ogg comments
00148 extern stb_vorbis_comment stb_vorbis_get_comment(stb_vorbis *f);
00149 
00150 // get the last error detected (clears it, too)
00151 extern int stb_vorbis_get_error(stb_vorbis *f);
00152 
00153 // close an ogg vorbis file and free all memory in use
00154 extern void stb_vorbis_close(stb_vorbis *f);
00155 
00156 // this function returns the offset (in samples) from the beginning of the
00157 // file that will be returned by the next decode, if it is known, or -1
00158 // otherwise. after a flush_pushdata() call, this may take a while before
00159 // it becomes valid again.
00160 // NOT WORKING YET after a seek with PULLDATA API
00161 extern int stb_vorbis_get_sample_offset(stb_vorbis *f);
00162 
00163 // returns the current seek point within the file, or offset from the beginning
00164 // of the memory buffer. In pushdata mode it returns 0.
00165 extern unsigned int stb_vorbis_get_file_offset(stb_vorbis *f);
00166 
00168 
00169 #ifndef STB_VORBIS_NO_PUSHDATA_API
00170 
00171 // this API allows you to get blocks of data from any source and hand
00172 // them to stb_vorbis. you have to buffer them; stb_vorbis will tell
00173 // you how much it used, and you have to give it the rest next time;
00174 // and stb_vorbis may not have enough data to work with and you will
00175 // need to give it the same data again PLUS more. Note that the Vorbis
00176 // specification does not bound the size of an individual frame.
00177 
00178 extern stb_vorbis *stb_vorbis_open_pushdata(
00179          const unsigned char * datablock, int datablock_length_in_bytes,
00180          int *datablock_memory_consumed_in_bytes,
00181          int *error,
00182          const stb_vorbis_alloc *alloc_buffer);
00183 // create a vorbis decoder by passing in the initial data block containing
00184 //    the ogg&vorbis headers (you don't need to do parse them, just provide
00185 //    the first N bytes of the file--you're told if it's not enough, see below)
00186 // on success, returns an stb_vorbis *, does not set error, returns the amount of
00187 //    data parsed/consumed on this call in *datablock_memory_consumed_in_bytes;
00188 // on failure, returns NULL on error and sets *error, does not change *datablock_memory_consumed
00189 // if returns NULL and *error is VORBIS_need_more_data, then the input block was
00190 //       incomplete and you need to pass in a larger block from the start of the file
00191 
00192 extern int stb_vorbis_decode_frame_pushdata(
00193          stb_vorbis *f,
00194          const unsigned char *datablock, int datablock_length_in_bytes,
00195          int *channels,             // place to write number of float * buffers
00196          float ***output,           // place to write float ** array of float * buffers
00197          int *samples               // place to write number of output samples
00198      );
00199 // decode a frame of audio sample data if possible from the passed-in data block
00200 //
00201 // return value: number of bytes we used from datablock
00202 //
00203 // possible cases:
00204 //     0 bytes used, 0 samples output (need more data)
00205 //     N bytes used, 0 samples output (resynching the stream, keep going)
00206 //     N bytes used, M samples output (one frame of data)
00207 // note that after opening a file, you will ALWAYS get one N-bytes,0-sample
00208 // frame, because Vorbis always "discards" the first frame.
00209 //
00210 // Note that on resynch, stb_vorbis will rarely consume all of the buffer,
00211 // instead only datablock_length_in_bytes-3 or less. This is because it wants
00212 // to avoid missing parts of a page header if they cross a datablock boundary,
00213 // without writing state-machiney code to record a partial detection.
00214 //
00215 // The number of channels returned are stored in *channels (which can be
00216 // NULL--it is always the same as the number of channels reported by
00217 // get_info). *output will contain an array of float* buffers, one per
00218 // channel. In other words, (*output)[0][0] contains the first sample from
00219 // the first channel, and (*output)[1][0] contains the first sample from
00220 // the second channel.
00221 
00222 extern void stb_vorbis_flush_pushdata(stb_vorbis *f);
00223 // inform stb_vorbis that your next datablock will not be contiguous with
00224 // previous ones (e.g. you've seeked in the data); future attempts to decode
00225 // frames will cause stb_vorbis to resynchronize (as noted above), and
00226 // once it sees a valid Ogg page (typically 4-8KB, as large as 64KB), it
00227 // will begin decoding the _next_ frame.
00228 //
00229 // if you want to seek using pushdata, you need to seek in your file, then
00230 // call stb_vorbis_flush_pushdata(), then start calling decoding, then once
00231 // decoding is returning you data, call stb_vorbis_get_sample_offset, and
00232 // if you don't like the result, seek your file again and repeat.
00233 #endif
00234 
00235 
00237 
00238 #ifndef STB_VORBIS_NO_PULLDATA_API
00239 // This API assumes stb_vorbis is allowed to pull data from a source--
00240 // either a block of memory containing the _entire_ vorbis stream, or a
00241 // FILE * that you or it create, or possibly some other reading mechanism
00242 // if you go modify the source to replace the FILE * case with some kind
00243 // of callback to your code. (But if you don't support seeking, you may
00244 // just want to go ahead and use pushdata.)
00245 
00246 #if !defined(STB_VORBIS_NO_STDIO) && !defined(STB_VORBIS_NO_INTEGER_CONVERSION)
00247 extern int stb_vorbis_decode_filename(const char *filename, int *channels, int *sample_rate, short **output);
00248 #endif
00249 #if !defined(STB_VORBIS_NO_INTEGER_CONVERSION)
00250 extern int stb_vorbis_decode_memory(const unsigned char *mem, int len, int *channels, int *sample_rate, short **output);
00251 #endif
00252 // decode an entire file and output the data interleaved into a malloc()ed
00253 // buffer stored in *output. The return value is the number of samples
00254 // decoded, or -1 if the file could not be opened or was not an ogg vorbis file.
00255 // When you're done with it, just free() the pointer returned in *output.
00256 
00257 extern stb_vorbis * stb_vorbis_open_memory(const unsigned char *data, int len,
00258                                   int *error, const stb_vorbis_alloc *alloc_buffer);
00259 // create an ogg vorbis decoder from an ogg vorbis stream in memory (note
00260 // this must be the entire stream!). on failure, returns NULL and sets *error
00261 
00262 #ifndef STB_VORBIS_NO_STDIO
00263 extern stb_vorbis * stb_vorbis_open_filename(const char *filename,
00264                                   int *error, const stb_vorbis_alloc *alloc_buffer);
00265 // create an ogg vorbis decoder from a filename via fopen(). on failure,
00266 // returns NULL and sets *error (possibly to VORBIS_file_open_failure).
00267 
00268 extern stb_vorbis * stb_vorbis_open_file(FILE *f, int close_handle_on_close,
00269                                   int *error, const stb_vorbis_alloc *alloc_buffer);
00270 // create an ogg vorbis decoder from an open FILE *, looking for a stream at
00271 // the _current_ seek point (ftell). on failure, returns NULL and sets *error.
00272 // note that stb_vorbis must "own" this stream; if you seek it in between
00273 // calls to stb_vorbis, it will become confused. Moreover, if you attempt to
00274 // perform stb_vorbis_seek_*() operations on this file, it will assume it
00275 // owns the _entire_ rest of the file after the start point. Use the next
00276 // function, stb_vorbis_open_file_section(), to limit it.
00277 
00278 extern stb_vorbis * stb_vorbis_open_file_section(FILE *f, int close_handle_on_close,
00279                 int *error, const stb_vorbis_alloc *alloc_buffer, unsigned int len);
00280 // create an ogg vorbis decoder from an open FILE *, looking for a stream at
00281 // the _current_ seek point (ftell); the stream will be of length 'len' bytes.
00282 // on failure, returns NULL and sets *error. note that stb_vorbis must "own"
00283 // this stream; if you seek it in between calls to stb_vorbis, it will become
00284 // confused.
00285 #endif
00286 
00287 #ifdef __SDL_SOUND_INTERNAL__
00288 extern stb_vorbis * stb_vorbis_open_rwops_section(SDL_RWops *rwops, int close_on_free, int *error, const stb_vorbis_alloc *alloc, unsigned int length);
00289 extern stb_vorbis * stb_vorbis_open_rwops(SDL_RWops *rwops, int close_on_free, int *error, const stb_vorbis_alloc *alloc);
00290 #endif
00291 
00292 extern int stb_vorbis_seek_frame(stb_vorbis *f, unsigned int sample_number);
00293 extern int stb_vorbis_seek(stb_vorbis *f, unsigned int sample_number);
00294 // these functions seek in the Vorbis file to (approximately) 'sample_number'.
00295 // after calling seek_frame(), the next call to get_frame_*() will include
00296 // the specified sample. after calling stb_vorbis_seek(), the next call to
00297 // stb_vorbis_get_samples_* will start with the specified sample. If you
00298 // do not need to seek to EXACTLY the target sample when using get_samples_*,
00299 // you can also use seek_frame().
00300 
00301 extern int stb_vorbis_seek_start(stb_vorbis *f);
00302 // this function is equivalent to stb_vorbis_seek(f,0)
00303 
00304 extern unsigned int stb_vorbis_stream_length_in_samples(stb_vorbis *f);
00305 extern float        stb_vorbis_stream_length_in_seconds(stb_vorbis *f);
00306 // these functions return the total length of the vorbis stream
00307 
00308 extern int stb_vorbis_get_frame_float(stb_vorbis *f, int *channels, float ***output);
00309 // decode the next frame and return the number of samples. the number of
00310 // channels returned are stored in *channels (which can be NULL--it is always
00311 // the same as the number of channels reported by get_info). *output will
00312 // contain an array of float* buffers, one per channel. These outputs will
00313 // be overwritten on the next call to stb_vorbis_get_frame_*.
00314 //
00315 // You generally should not intermix calls to stb_vorbis_get_frame_*()
00316 // and stb_vorbis_get_samples_*(), since the latter calls the former.
00317 
00318 #ifndef STB_VORBIS_NO_INTEGER_CONVERSION
00319 extern int stb_vorbis_get_frame_short_interleaved(stb_vorbis *f, int num_c, short *buffer, int num_shorts);
00320 extern int stb_vorbis_get_frame_short            (stb_vorbis *f, int num_c, short **buffer, int num_samples);
00321 #endif
00322 // decode the next frame and return the number of *samples* per channel.
00323 // Note that for interleaved data, you pass in the number of shorts (the
00324 // size of your array), but the return value is the number of samples per
00325 // channel, not the total number of samples.
00326 //
00327 // The data is coerced to the number of channels you request according to the
00328 // channel coercion rules (see below). You must pass in the size of your
00329 // buffer(s) so that stb_vorbis will not overwrite the end of the buffer.
00330 // The maximum buffer size needed can be gotten from get_info(); however,
00331 // the Vorbis I specification implies an absolute maximum of 4096 samples
00332 // per channel.
00333 
00334 // Channel coercion rules:
00335 //    Let M be the number of channels requested, and N the number of channels present,
00336 //    and Cn be the nth channel; let stereo L be the sum of all L and center channels,
00337 //    and stereo R be the sum of all R and center channels (channel assignment from the
00338 //    vorbis spec).
00339 //        M    N       output
00340 //        1    k      sum(Ck) for all k
00341 //        2    *      stereo L, stereo R
00342 //        k    l      k > l, the first l channels, then 0s
00343 //        k    l      k <= l, the first k channels
00344 //    Note that this is not _good_ surround etc. mixing at all! It's just so
00345 //    you get something useful.
00346 
00347 extern int stb_vorbis_get_samples_float_interleaved(stb_vorbis *f, int channels, float *buffer, int num_floats);
00348 extern int stb_vorbis_get_samples_float(stb_vorbis *f, int channels, float **buffer, int num_samples);
00349 // gets num_samples samples, not necessarily on a frame boundary--this requires
00350 // buffering so you have to supply the buffers. DOES NOT APPLY THE COERCION RULES.
00351 // Returns the number of samples stored per channel; it may be less than requested
00352 // at the end of the file. If there are no more samples in the file, returns 0.
00353 
00354 #ifndef STB_VORBIS_NO_INTEGER_CONVERSION
00355 extern int stb_vorbis_get_samples_short_interleaved(stb_vorbis *f, int channels, short *buffer, int num_shorts);
00356 extern int stb_vorbis_get_samples_short(stb_vorbis *f, int channels, short **buffer, int num_samples);
00357 #endif
00358 // gets num_samples samples, not necessarily on a frame boundary--this requires
00359 // buffering so you have to supply the buffers. Applies the coercion rules above
00360 // to produce 'channels' channels. Returns the number of samples stored per channel;
00361 // it may be less than requested at the end of the file. If there are no more
00362 // samples in the file, returns 0.
00363 
00364 #endif
00365 
00367 
00368 enum STBVorbisError
00369 {
00370    VORBIS__no_error = 0,
00371 
00372    VORBIS_need_more_data=1,             // not a real error
00373 
00374    VORBIS_invalid_api_mixing,           // can't mix API modes
00375    VORBIS_outofmem,                     // not enough memory
00376    VORBIS_feature_not_supported,        // uses floor 0
00377    VORBIS_too_many_channels,            // STB_VORBIS_MAX_CHANNELS is too small
00378    VORBIS_file_open_failure,            // fopen() failed
00379    VORBIS_seek_without_length,          // can't seek in unknown-length file
00380 
00381    VORBIS_unexpected_eof=10,            // file is truncated?
00382    VORBIS_seek_invalid,                 // seek past EOF
00383 
00384    // decoding errors (corrupt/invalid stream) -- you probably
00385    // don't care about the exact details of these
00386 
00387    // vorbis errors:
00388    VORBIS_invalid_setup=20,
00389    VORBIS_invalid_stream,
00390 
00391    // ogg errors:
00392    VORBIS_missing_capture_pattern=30,
00393    VORBIS_invalid_stream_structure_version,
00394    VORBIS_continued_packet_flag_invalid,
00395    VORBIS_incorrect_stream_serial_number,
00396    VORBIS_invalid_first_page,
00397    VORBIS_bad_packet_type,
00398    VORBIS_cant_find_last_page,
00399    VORBIS_seek_failed,
00400    VORBIS_ogg_skeleton_not_supported
00401 };
00402 
00403 
00404 #ifdef __cplusplus
00405 }
00406 #endif
00407 
00408 #endif // STB_VORBIS_INCLUDE_STB_VORBIS_H
00409 //
00410 //  HEADER ENDS HERE
00411 //
00413 
00414 #ifndef STB_VORBIS_HEADER_ONLY
00415 
00416 // global configuration settings (e.g. set these in the project/makefile),
00417 // or just set them in this file at the top (although ideally the first few
00418 // should be visible when the header file is compiled too, although it's not
00419 // crucial)
00420 
00421 // STB_VORBIS_NO_PUSHDATA_API
00422 //     does not compile the code for the various stb_vorbis_*_pushdata()
00423 //     functions
00424 // #define STB_VORBIS_NO_PUSHDATA_API
00425 
00426 // STB_VORBIS_NO_PULLDATA_API
00427 //     does not compile the code for the non-pushdata APIs
00428 // #define STB_VORBIS_NO_PULLDATA_API
00429 
00430 // STB_VORBIS_NO_STDIO
00431 //     does not compile the code for the APIs that use FILE *s internally
00432 //     or externally (implied by STB_VORBIS_NO_PULLDATA_API)
00433 // #define STB_VORBIS_NO_STDIO
00434 
00435 // STB_VORBIS_NO_INTEGER_CONVERSION
00436 //     does not compile the code for converting audio sample data from
00437 //     float to integer (implied by STB_VORBIS_NO_PULLDATA_API)
00438 // #define STB_VORBIS_NO_INTEGER_CONVERSION
00439 
00440 // STB_VORBIS_NO_FAST_SCALED_FLOAT
00441 //      does not use a fast float-to-int trick to accelerate float-to-int on
00442 //      most platforms which requires endianness be defined correctly.
00443 //#define STB_VORBIS_NO_FAST_SCALED_FLOAT
00444 
00445 
00446 // STB_VORBIS_MAX_CHANNELS [number]
00447 //     globally define this to the maximum number of channels you need.
00448 //     The spec does not put a restriction on channels except that
00449 //     the count is stored in a byte, so 255 is the hard limit.
00450 //     Reducing this saves about 16 bytes per value, so using 16 saves
00451 //     (255-16)*16 or around 4KB. Plus anything other memory usage
00452 //     I forgot to account for. Can probably go as low as 8 (7.1 audio),
00453 //     6 (5.1 audio), or 2 (stereo only).
00454 #ifndef STB_VORBIS_MAX_CHANNELS
00455 #define STB_VORBIS_MAX_CHANNELS    16  // enough for anyone?
00456 #endif
00457 
00458 // STB_VORBIS_PUSHDATA_CRC_COUNT [number]
00459 //     after a flush_pushdata(), stb_vorbis begins scanning for the
00460 //     next valid page, without backtracking. when it finds something
00461 //     that looks like a page, it streams through it and verifies its
00462 //     CRC32. Should that validation fail, it keeps scanning. But it's
00463 //     possible that _while_ streaming through to check the CRC32 of
00464 //     one candidate page, it sees another candidate page. This #define
00465 //     determines how many "overlapping" candidate pages it can search
00466 //     at once. Note that "real" pages are typically ~4KB to ~8KB, whereas
00467 //     garbage pages could be as big as 64KB, but probably average ~16KB.
00468 //     So don't hose ourselves by scanning an apparent 64KB page and
00469 //     missing a ton of real ones in the interim; so minimum of 2
00470 #ifndef STB_VORBIS_PUSHDATA_CRC_COUNT
00471 #define STB_VORBIS_PUSHDATA_CRC_COUNT  4
00472 #endif
00473 
00474 // STB_VORBIS_FAST_HUFFMAN_LENGTH [number]
00475 //     sets the log size of the huffman-acceleration table.  Maximum
00476 //     supported value is 24. with larger numbers, more decodings are O(1),
00477 //     but the table size is larger so worse cache missing, so you'll have
00478 //     to probe (and try multiple ogg vorbis files) to find the sweet spot.
00479 #ifndef STB_VORBIS_FAST_HUFFMAN_LENGTH
00480 #define STB_VORBIS_FAST_HUFFMAN_LENGTH   10
00481 #endif
00482 
00483 // STB_VORBIS_FAST_BINARY_LENGTH [number]
00484 //     sets the log size of the binary-search acceleration table. this
00485 //     is used in similar fashion to the fast-huffman size to set initial
00486 //     parameters for the binary search
00487 
00488 // STB_VORBIS_FAST_HUFFMAN_INT
00489 //     The fast huffman tables are much more efficient if they can be
00490 //     stored as 16-bit results instead of 32-bit results. This restricts
00491 //     the codebooks to having only 65535 possible outcomes, though.
00492 //     (At least, accelerated by the huffman table.)
00493 #ifndef STB_VORBIS_FAST_HUFFMAN_INT
00494 #define STB_VORBIS_FAST_HUFFMAN_SHORT
00495 #endif
00496 
00497 // STB_VORBIS_NO_HUFFMAN_BINARY_SEARCH
00498 //     If the 'fast huffman' search doesn't succeed, then stb_vorbis falls
00499 //     back on binary searching for the correct one. This requires storing
00500 //     extra tables with the huffman codes in sorted order. Defining this
00501 //     symbol trades off space for speed by forcing a linear search in the
00502 //     non-fast case, except for "sparse" codebooks.
00503 // #define STB_VORBIS_NO_HUFFMAN_BINARY_SEARCH
00504 
00505 // STB_VORBIS_DIVIDES_IN_RESIDUE
00506 //     stb_vorbis precomputes the result of the scalar residue decoding
00507 //     that would otherwise require a divide per chunk. you can trade off
00508 //     space for time by defining this symbol.
00509 // #define STB_VORBIS_DIVIDES_IN_RESIDUE
00510 
00511 // STB_VORBIS_DIVIDES_IN_CODEBOOK
00512 //     vorbis VQ codebooks can be encoded two ways: with every case explicitly
00513 //     stored, or with all elements being chosen from a small range of values,
00514 //     and all values possible in all elements. By default, stb_vorbis expands
00515 //     this latter kind out to look like the former kind for ease of decoding,
00516 //     because otherwise an integer divide-per-vector-element is required to
00517 //     unpack the index. If you define STB_VORBIS_DIVIDES_IN_CODEBOOK, you can
00518 //     trade off storage for speed.
00519 //#define STB_VORBIS_DIVIDES_IN_CODEBOOK
00520 
00521 #ifdef STB_VORBIS_CODEBOOK_SHORTS
00522 #error "STB_VORBIS_CODEBOOK_SHORTS is no longer supported as it produced incorrect results for some input formats"
00523 #endif
00524 
00525 // STB_VORBIS_DIVIDE_TABLE
00526 //     this replaces small integer divides in the floor decode loop with
00527 //     table lookups. made less than 1% difference, so disabled by default.
00528 
00529 // STB_VORBIS_NO_INLINE_DECODE
00530 //     disables the inlining of the scalar codebook fast-huffman decode.
00531 //     might save a little codespace; useful for debugging
00532 // #define STB_VORBIS_NO_INLINE_DECODE
00533 
00534 // STB_VORBIS_NO_DEFER_FLOOR
00535 //     Normally we only decode the floor without synthesizing the actual
00536 //     full curve. We can instead synthesize the curve immediately. This
00537 //     requires more memory and is very likely slower, so I don't think
00538 //     you'd ever want to do it except for debugging.
00539 // #define STB_VORBIS_NO_DEFER_FLOOR
00540 
00541 
00542 
00543 
00545 
00546 #ifdef STB_VORBIS_NO_PULLDATA_API
00547    #define STB_VORBIS_NO_INTEGER_CONVERSION
00548    #define STB_VORBIS_NO_STDIO
00549 #endif
00550 
00551 #if defined(STB_VORBIS_NO_CRT) && !defined(STB_VORBIS_NO_STDIO)
00552    #define STB_VORBIS_NO_STDIO 1
00553 #endif
00554 
00555 #ifndef STB_VORBIS_NO_INTEGER_CONVERSION
00556 #ifndef STB_VORBIS_NO_FAST_SCALED_FLOAT
00557 
00558    // only need endianness for fast-float-to-int, which we don't
00559    // use for pushdata
00560 
00561    #ifndef STB_VORBIS_BIG_ENDIAN
00562      #define STB_VORBIS_ENDIAN  0
00563    #else
00564      #define STB_VORBIS_ENDIAN  1
00565    #endif
00566 
00567 #endif
00568 #endif
00569 
00570 
00571 #ifndef STB_VORBIS_NO_STDIO
00572 #include <stdio.h>
00573 #endif
00574 
00575 #ifndef STB_VORBIS_NO_CRT
00576    #include <stdlib.h>
00577    #include <string.h>
00578    #include <assert.h>
00579    #include <math.h>
00580 
00581    // find definition of alloca if it's not in stdlib.h:
00582    #if defined(_MSC_VER) || defined(__MINGW32__)
00583       #include <malloc.h>
00584    #endif
00585    #if defined(__linux__) || defined(__linux) || defined(__EMSCRIPTEN__)
00586       #include <alloca.h>
00587    #endif
00588 #else // STB_VORBIS_NO_CRT
00589    #ifndef NULL
00590    #define NULL 0
00591    #endif
00592 
00593 #endif // STB_VORBIS_NO_CRT
00594 
00595 #include <limits.h>
00596 
00597 #ifdef __MINGW32__
00598    // eff you mingw:
00599    //     "fixed":
00600    //         http://sourceforge.net/p/mingw-w64/mailman/message/32882927/
00601    //     "no that broke the build, reverted, who cares about C":
00602    //         http://sourceforge.net/p/mingw-w64/mailman/message/32890381/
00603    #ifdef __forceinline
00604    #undef __forceinline
00605    #endif
00606    #define __forceinline
00607 
00608    #ifdef alloca
00609    #undef alloca
00610    #endif
00611    #define alloca __builtin_alloca
00612 #elif !defined(_MSC_VER)
00613    #if __GNUC__
00614       #define __forceinline inline
00615    #else
00616       #define __forceinline
00617    #endif
00618 #endif
00619 
00620 #if STB_VORBIS_MAX_CHANNELS > 256
00621 #error "Value of STB_VORBIS_MAX_CHANNELS outside of allowed range"
00622 #endif
00623 
00624 #if STB_VORBIS_FAST_HUFFMAN_LENGTH > 24
00625 #error "Value of STB_VORBIS_FAST_HUFFMAN_LENGTH outside of allowed range"
00626 #endif
00627 
00628 
00629 #if 0
00630 #include <crtdbg.h>
00631 #define CHECK(f)   _CrtIsValidHeapPointer(f->channel_buffers[1])
00632 #else
00633 #define CHECK(f)   ((void) 0)
00634 #endif
00635 
00636 #define MAX_BLOCKSIZE_LOG  13   // from specification
00637 #define MAX_BLOCKSIZE      (1 << MAX_BLOCKSIZE_LOG)
00638 
00639 
00640 #ifdef __SDL_SOUND_INTERNAL__
00641 typedef Uint8 uint8;
00642 typedef Sint8 int8;
00643 typedef Uint16 uint16;
00644 typedef Sint16 int16;
00645 typedef Uint32 uint32;
00646 typedef Sint32 int32;
00647 #else
00648 typedef unsigned char  uint8;
00649 typedef   signed char   int8;
00650 typedef unsigned short uint16;
00651 typedef   signed short  int16;
00652 typedef unsigned int   uint32;
00653 typedef   signed int    int32;
00654 #endif
00655 
00656 #ifndef TRUE
00657 #define TRUE 1
00658 #define FALSE 0
00659 #endif
00660 
00661 typedef float codetype;
00662 
00663 // @NOTE
00664 //
00665 // Some arrays below are tagged "//varies", which means it's actually
00666 // a variable-sized piece of data, but rather than malloc I assume it's
00667 // small enough it's better to just allocate it all together with the
00668 // main thing
00669 //
00670 // Most of the variables are specified with the smallest size I could pack
00671 // them into. It might give better performance to make them all full-sized
00672 // integers. It should be safe to freely rearrange the structures or change
00673 // the sizes larger--nothing relies on silently truncating etc., nor the
00674 // order of variables.
00675 
00676 #define FAST_HUFFMAN_TABLE_SIZE   (1 << STB_VORBIS_FAST_HUFFMAN_LENGTH)
00677 #define FAST_HUFFMAN_TABLE_MASK   (FAST_HUFFMAN_TABLE_SIZE - 1)
00678 
00679 typedef struct
00680 {
00681    int dimensions, entries;
00682    uint8 *codeword_lengths;
00683    float  minimum_value;
00684    float  delta_value;
00685    uint8  value_bits;
00686    uint8  lookup_type;
00687    uint8  sequence_p;
00688    uint8  sparse;
00689    uint32 lookup_values;
00690    codetype *multiplicands;
00691    uint32 *codewords;
00692    #ifdef STB_VORBIS_FAST_HUFFMAN_SHORT
00693     int16  fast_huffman[FAST_HUFFMAN_TABLE_SIZE];
00694    #else
00695     int32  fast_huffman[FAST_HUFFMAN_TABLE_SIZE];
00696    #endif
00697    uint32 *sorted_codewords;
00698    int    *sorted_values;
00699    int     sorted_entries;
00700 } Codebook;
00701 
00702 typedef struct
00703 {
00704    uint16 rate;
00705    uint16 bark_map_size;
00706    uint8 order;
00707    uint8 amplitude_bits;
00708    uint8 amplitude_offset;
00709    uint8 number_of_books;
00710    uint8 book_list[16]; // varies
00711 } Floor0;
00712 
00713 typedef struct
00714 {
00715    uint8 partitions;
00716    uint8 partition_class_list[32]; // varies
00717    uint8 class_dimensions[16]; // varies
00718    uint8 class_subclasses[16]; // varies
00719    uint8 class_masterbooks[16]; // varies
00720    int16 subclass_books[16][8]; // varies
00721    uint16 Xlist[31*8+2]; // varies
00722    uint8 sorted_order[31*8+2];
00723    uint8 neighbors[31*8+2][2];
00724    uint8 floor1_multiplier;
00725    uint8 rangebits;
00726    int values;
00727 } Floor1;
00728 
00729 typedef union
00730 {
00731    Floor0 floor0;
00732    Floor1 floor1;
00733 } Floor;
00734 
00735 typedef struct
00736 {
00737    uint32 begin, end;
00738    uint32 part_size;
00739    uint8 classifications;
00740    uint8 classbook;
00741    uint8 **classdata;
00742    int16 (*residue_books)[8];
00743 } Residue;
00744 
00745 typedef struct
00746 {
00747    uint8 magnitude;
00748    uint8 angle;
00749    uint8 mux;
00750 } MappingChannel;
00751 
00752 typedef struct
00753 {
00754    uint16 coupling_steps;
00755    MappingChannel *chan;
00756    uint8  submaps;
00757    uint8  submap_floor[15]; // varies
00758    uint8  submap_residue[15]; // varies
00759 } Mapping;
00760 
00761 typedef struct
00762 {
00763    uint8 blockflag;
00764    uint8 mapping;
00765    uint16 windowtype;
00766    uint16 transformtype;
00767 } Mode;
00768 
00769 typedef struct
00770 {
00771    uint32  goal_crc;    // expected crc if match
00772    int     bytes_left;  // bytes left in packet
00773    uint32  crc_so_far;  // running crc
00774    int     bytes_done;  // bytes processed in _current_ chunk
00775    uint32  sample_loc;  // granule pos encoded in page
00776 } CRCscan;
00777 
00778 typedef struct
00779 {
00780    uint32 page_start, page_end;
00781    uint32 last_decoded_sample;
00782 } ProbedPage;
00783 
00784 struct stb_vorbis
00785 {
00786   // user-accessible info
00787    unsigned int sample_rate;
00788    int channels;
00789 
00790    unsigned int setup_memory_required;
00791    unsigned int temp_memory_required;
00792    unsigned int setup_temp_memory_required;
00793 
00794    char *vendor;
00795    int comment_list_length;
00796    char **comment_list;
00797 
00798   // input config
00799 #ifndef STB_VORBIS_NO_STDIO
00800    FILE *f;
00801    uint32 f_start;
00802    int close_on_free;
00803 #endif
00804 
00805    #ifdef __SDL_SOUND_INTERNAL__
00806    SDL_RWops *rwops;
00807    uint32 rwops_start;
00808    int close_on_free;
00809    #endif
00810 
00811    uint8 *stream;
00812    uint8 *stream_start;
00813    uint8 *stream_end;
00814 
00815    uint32 stream_len;
00816 
00817    uint8  push_mode;
00818 
00819    // the page to seek to when seeking to start, may be zero
00820    uint32 first_audio_page_offset;
00821 
00822    // p_first is the page on which the first audio packet ends
00823    // (but not necessarily the page on which it starts)
00824    ProbedPage p_first, p_last;
00825 
00826   // memory management
00827    stb_vorbis_alloc alloc;
00828    int setup_offset;
00829    int temp_offset;
00830 
00831   // run-time results
00832    int eof;
00833    enum STBVorbisError error;
00834 
00835   // user-useful data
00836 
00837   // header info
00838    int blocksize[2];
00839    int blocksize_0, blocksize_1;
00840    int codebook_count;
00841    Codebook *codebooks;
00842    int floor_count;
00843    uint16 floor_types[64]; // varies
00844    Floor *floor_config;
00845    int residue_count;
00846    uint16 residue_types[64]; // varies
00847    Residue *residue_config;
00848    int mapping_count;
00849    Mapping *mapping;
00850    int mode_count;
00851    Mode mode_config[64];  // varies
00852 
00853    uint32 total_samples;
00854 
00855   // decode buffer
00856    float *channel_buffers[STB_VORBIS_MAX_CHANNELS];
00857    float *outputs        [STB_VORBIS_MAX_CHANNELS];
00858 
00859    float *previous_window[STB_VORBIS_MAX_CHANNELS];
00860    int previous_length;
00861 
00862    #ifndef STB_VORBIS_NO_DEFER_FLOOR
00863    int16 *finalY[STB_VORBIS_MAX_CHANNELS];
00864    #else
00865    float *floor_buffers[STB_VORBIS_MAX_CHANNELS];
00866    #endif
00867 
00868    uint32 current_loc; // sample location of next frame to decode
00869    int    current_loc_valid;
00870 
00871   // per-blocksize precomputed data
00872 
00873    // twiddle factors
00874    float *A[2],*B[2],*C[2];
00875    float *window[2];
00876    uint16 *bit_reverse[2];
00877 
00878   // current page/packet/segment streaming info
00879    uint32 serial; // stream serial number for verification
00880    int last_page;
00881    int segment_count;
00882    uint8 segments[255];
00883    uint8 page_flag;
00884    uint8 bytes_in_seg;
00885    uint8 first_decode;
00886    int next_seg;
00887    int last_seg;  // flag that we're on the last segment
00888    int last_seg_which; // what was the segment number of the last seg?
00889    uint32 acc;
00890    int valid_bits;
00891    int packet_bytes;
00892    int end_seg_with_known_loc;
00893    uint32 known_loc_for_packet;
00894    int discard_samples_deferred;
00895    uint32 samples_output;
00896 
00897   // push mode scanning
00898    int page_crc_tests; // only in push_mode: number of tests active; -1 if not searching
00899 #ifndef STB_VORBIS_NO_PUSHDATA_API
00900    CRCscan scan[STB_VORBIS_PUSHDATA_CRC_COUNT];
00901 #endif
00902 
00903   // sample-access
00904    int channel_buffer_start;
00905    int channel_buffer_end;
00906 };
00907 
00908 #if defined(STB_VORBIS_NO_PUSHDATA_API)
00909    #define IS_PUSH_MODE(f)   FALSE
00910 #elif defined(STB_VORBIS_NO_PULLDATA_API)
00911    #define IS_PUSH_MODE(f)   TRUE
00912 #else
00913    #define IS_PUSH_MODE(f)   ((f)->push_mode)
00914 #endif
00915 
00916 typedef struct stb_vorbis vorb;
00917 
00918 static int error(vorb *f, enum STBVorbisError e)
00919 {
00920    f->error = e;
00921    return 0;
00922 }
00923 
00924 
00925 // these functions are used for allocating temporary memory
00926 // while decoding. if you can afford the stack space, use
00927 // alloca(); otherwise, provide a temp buffer and it will
00928 // allocate out of those.
00929 
00930 #define array_size_required(count,size)  (count*(sizeof(void *)+(size)))
00931 
00932 #define temp_alloc(f,size)              (f->alloc.alloc_buffer ? setup_temp_malloc(f,size) : alloca(size))
00933 // #define temp_free(f,p)                  0
00934 #define temp_alloc_save(f)              ((f)->temp_offset)
00935 #define temp_alloc_restore(f,p)         ((f)->temp_offset = (p))
00936 
00937 #define temp_block_array(f,count,size)  make_block_array(temp_alloc(f,array_size_required(count,size)), count, size)
00938 
00939 // given a sufficiently large block of memory, make an array of pointers to subblocks of it
00940 static void *make_block_array(void *mem, int count, int size)
00941 {
00942    int i;
00943    void ** p = (void **) mem;
00944    char *q = (char *) (p + count);
00945    for (i=0; i < count; ++i) {
00946       p[i] = q;
00947       q += size;
00948    }
00949    return p;
00950 }
00951 
00952 static void *setup_malloc(vorb *f, int sz)
00953 {
00954    sz = (sz+7) & ~7; // round up to nearest 8 for alignment of future allocs.
00955    f->setup_memory_required += sz;
00956    if (f->alloc.alloc_buffer) {
00957       void *p = (char *) f->alloc.alloc_buffer + f->setup_offset;
00958       if (f->setup_offset + sz > f->temp_offset) return NULL;
00959       f->setup_offset += sz;
00960       return p;
00961    }
00962    return sz ? malloc(sz) : NULL;
00963 }
00964 
00965 static void setup_free(vorb *f, void *p)
00966 {
00967    if (f->alloc.alloc_buffer) return; // do nothing; setup mem is a stack
00968    free(p);
00969 }
00970 
00971 static void *setup_temp_malloc(vorb *f, int sz)
00972 {
00973    sz = (sz+7) & ~7; // round up to nearest 8 for alignment of future allocs.
00974    if (f->alloc.alloc_buffer) {
00975       if (f->temp_offset - sz < f->setup_offset) return NULL;
00976       f->temp_offset -= sz;
00977       return (char *) f->alloc.alloc_buffer + f->temp_offset;
00978    }
00979    return malloc(sz);
00980 }
00981 
00982 static void setup_temp_free(vorb *f, void *p, int sz)
00983 {
00984    if (f->alloc.alloc_buffer) {
00985       f->temp_offset += (sz+3)&~3;
00986       return;
00987    }
00988    free(p);
00989 }
00990 
00991 #define CRC32_POLY    0x04c11db7   // from spec
00992 
00993 static uint32 crc_table[256];
00994 static void crc32_init(void)
00995 {
00996    int i,j;
00997    uint32 s;
00998    for(i=0; i < 256; i++) {
00999       for (s=(uint32) i << 24, j=0; j < 8; ++j)
01000          s = (s << 1) ^ (s >= (1U<<31) ? CRC32_POLY : 0);
01001       crc_table[i] = s;
01002    }
01003 }
01004 
01005 static __forceinline uint32 crc32_update(uint32 crc, uint8 byte)
01006 {
01007    return (crc << 8) ^ crc_table[byte ^ (crc >> 24)];
01008 }
01009 
01010 
01011 // used in setup, and for huffman that doesn't go fast path
01012 static unsigned int bit_reverse(unsigned int n)
01013 {
01014   n = ((n & 0xAAAAAAAA) >>  1) | ((n & 0x55555555) << 1);
01015   n = ((n & 0xCCCCCCCC) >>  2) | ((n & 0x33333333) << 2);
01016   n = ((n & 0xF0F0F0F0) >>  4) | ((n & 0x0F0F0F0F) << 4);
01017   n = ((n & 0xFF00FF00) >>  8) | ((n & 0x00FF00FF) << 8);
01018   return (n >> 16) | (n << 16);
01019 }
01020 
01021 static float square(float x)
01022 {
01023    return x*x;
01024 }
01025 
01026 // this is a weird definition of log2() for which log2(1) = 1, log2(2) = 2, log2(4) = 3
01027 // as required by the specification. fast(?) implementation from stb.h
01028 // @OPTIMIZE: called multiple times per-packet with "constants"; move to setup
01029 static int ilog(int32 n)
01030 {
01031    static signed char log2_4[16] = { 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4 };
01032 
01033    if (n < 0) return 0; // signed n returns 0
01034 
01035    // 2 compares if n < 16, 3 compares otherwise (4 if signed or n > 1<<29)
01036    if (n < (1 << 14))
01037         if (n < (1 <<  4))            return  0 + log2_4[n      ];
01038         else if (n < (1 <<  9))       return  5 + log2_4[n >>  5];
01039              else                     return 10 + log2_4[n >> 10];
01040    else if (n < (1 << 24))
01041              if (n < (1 << 19))       return 15 + log2_4[n >> 15];
01042              else                     return 20 + log2_4[n >> 20];
01043         else if (n < (1 << 29))       return 25 + log2_4[n >> 25];
01044              else                     return 30 + log2_4[n >> 30];
01045 }
01046 
01047 #ifndef M_PI
01048   #define M_PI  3.14159265358979323846264f  // from CRC
01049 #endif
01050 
01051 // code length assigned to a value with no huffman encoding
01052 #define NO_CODE   255
01053 
01055 //
01056 // these functions are only called at setup, and only a few times
01057 // per file
01058 
01059 static float float32_unpack(uint32 x)
01060 {
01061    // from the specification
01062    uint32 mantissa = x & 0x1fffff;
01063    uint32 sign = x & 0x80000000;
01064    uint32 exp = (x & 0x7fe00000) >> 21;
01065    double res = sign ? -(double)mantissa : (double)mantissa;
01066    return (float) ldexp((float)res, exp-788);
01067 }
01068 
01069 
01070 // zlib & jpeg huffman tables assume that the output symbols
01071 // can either be arbitrarily arranged, or have monotonically
01072 // increasing frequencies--they rely on the lengths being sorted;
01073 // this makes for a very simple generation algorithm.
01074 // vorbis allows a huffman table with non-sorted lengths. This
01075 // requires a more sophisticated construction, since symbols in
01076 // order do not map to huffman codes "in order".
01077 static void add_entry(Codebook *c, uint32 huff_code, int symbol, int count, int len, uint32 *values)
01078 {
01079    if (!c->sparse) {
01080       c->codewords      [symbol] = huff_code;
01081    } else {
01082       c->codewords       [count] = huff_code;
01083       c->codeword_lengths[count] = len;
01084       values             [count] = symbol;
01085    }
01086 }
01087 
01088 static int compute_codewords(Codebook *c, uint8 *len, int n, uint32 *values)
01089 {
01090    int i,k,m=0;
01091    uint32 available[32];
01092 
01093    memset(available, 0, sizeof(available));
01094    // find the first entry
01095    for (k=0; k < n; ++k) if (len[k] < NO_CODE) break;
01096    if (k == n) { assert(c->sorted_entries == 0); return TRUE; }
01097    // add to the list
01098    add_entry(c, 0, k, m++, len[k], values);
01099    // add all available leaves
01100    for (i=1; i <= len[k]; ++i)
01101       available[i] = 1U << (32-i);
01102    // note that the above code treats the first case specially,
01103    // but it's really the same as the following code, so they
01104    // could probably be combined (except the initial code is 0,
01105    // and I use 0 in available[] to mean 'empty')
01106    for (i=k+1; i < n; ++i) {
01107       uint32 res;
01108       int z = len[i], y;
01109       if (z == NO_CODE) continue;
01110       // find lowest available leaf (should always be earliest,
01111       // which is what the specification calls for)
01112       // note that this property, and the fact we can never have
01113       // more than one free leaf at a given level, isn't totally
01114       // trivial to prove, but it seems true and the assert never
01115       // fires, so!
01116       while (z > 0 && !available[z]) --z;
01117       if (z == 0) { return FALSE; }
01118       res = available[z];
01119       assert(z >= 0 && z < 32);
01120       available[z] = 0;
01121       add_entry(c, bit_reverse(res), i, m++, len[i], values);
01122       // propagate availability up the tree
01123       if (z != len[i]) {
01124          assert(/*len[i] >= 0 always true, len is unsigned char ptr && */len[i] < 32u);
01125          for (y=len[i]; y > z; --y) {
01126             assert(available[y] == 0);
01127             available[y] = res + (1 << (32-y));
01128          }
01129       }
01130    }
01131    return TRUE;
01132 }
01133 
01134 // accelerated huffman table allows fast O(1) match of all symbols
01135 // of length <= STB_VORBIS_FAST_HUFFMAN_LENGTH
01136 static void compute_accelerated_huffman(Codebook *c)
01137 {
01138    int i, len;
01139    for (i=0; i < FAST_HUFFMAN_TABLE_SIZE; ++i)
01140       c->fast_huffman[i] = -1;
01141 
01142    len = c->sparse ? c->sorted_entries : c->entries;
01143    #ifdef STB_VORBIS_FAST_HUFFMAN_SHORT
01144    if (len > 32767) len = 32767; // largest possible value we can encode!
01145    #endif
01146    for (i=0; i < len; ++i) {
01147       if (c->codeword_lengths[i] <= STB_VORBIS_FAST_HUFFMAN_LENGTH) {
01148          uint32 z = c->sparse ? bit_reverse(c->sorted_codewords[i]) : c->codewords[i];
01149          // set table entries for all bit combinations in the higher bits
01150          while (z < FAST_HUFFMAN_TABLE_SIZE) {
01151              c->fast_huffman[z] = i;
01152              z += 1 << c->codeword_lengths[i];
01153          }
01154       }
01155    }
01156 }
01157 
01158 #ifdef _MSC_VER
01159 #define STBV_CDECL __cdecl
01160 #else
01161 #define STBV_CDECL
01162 #endif
01163 
01164 static int STBV_CDECL uint32_compare(const void *p, const void *q)
01165 {
01166    uint32 x = * (uint32 *) p;
01167    uint32 y = * (uint32 *) q;
01168    return x < y ? -1 : x > y;
01169 }
01170 
01171 static int include_in_sort(Codebook *c, uint8 len)
01172 {
01173    if (c->sparse) { assert(len != NO_CODE); return TRUE; }
01174    if (len == NO_CODE) return FALSE;
01175    if (len > STB_VORBIS_FAST_HUFFMAN_LENGTH) return TRUE;
01176    return FALSE;
01177 }
01178 
01179 // if the fast table above doesn't work, we want to binary
01180 // search them... need to reverse the bits
01181 static void compute_sorted_huffman(Codebook *c, uint8 *lengths, uint32 *values)
01182 {
01183    int i, len;
01184    // build a list of all the entries
01185    // OPTIMIZATION: don't include the short ones, since they'll be caught by FAST_HUFFMAN.
01186    // this is kind of a frivolous optimization--I don't see any performance improvement,
01187    // but it's like 4 extra lines of code, so.
01188    if (!c->sparse) {
01189       int k = 0;
01190       for (i=0; i < c->entries; ++i)
01191          if (include_in_sort(c, lengths[i]))
01192             c->sorted_codewords[k++] = bit_reverse(c->codewords[i]);
01193       assert(k == c->sorted_entries);
01194    } else {
01195       for (i=0; i < c->sorted_entries; ++i)
01196          c->sorted_codewords[i] = bit_reverse(c->codewords[i]);
01197    }
01198 
01199    qsort(c->sorted_codewords, c->sorted_entries, sizeof(c->sorted_codewords[0]), uint32_compare);
01200    c->sorted_codewords[c->sorted_entries] = 0xffffffff;
01201 
01202    len = c->sparse ? c->sorted_entries : c->entries;
01203    // now we need to indicate how they correspond; we could either
01204    //   #1: sort a different data structure that says who they correspond to
01205    //   #2: for each sorted entry, search the original list to find who corresponds
01206    //   #3: for each original entry, find the sorted entry
01207    // #1 requires extra storage, #2 is slow, #3 can use binary search!
01208    for (i=0; i < len; ++i) {
01209       int huff_len = c->sparse ? lengths[values[i]] : lengths[i];
01210       if (include_in_sort(c,huff_len)) {
01211          uint32 code = bit_reverse(c->codewords[i]);
01212          int x=0, n=c->sorted_entries;
01213          while (n > 1) {
01214             // invariant: sc[x] <= code < sc[x+n]
01215             int m = x + (n >> 1);
01216             if (c->sorted_codewords[m] <= code) {
01217                x = m;
01218                n -= (n>>1);
01219             } else {
01220                n >>= 1;
01221             }
01222          }
01223          assert(c->sorted_codewords[x] == code);
01224          if (c->sparse) {
01225             c->sorted_values[x] = values[i];
01226             c->codeword_lengths[x] = huff_len;
01227          } else {
01228             c->sorted_values[x] = i;
01229          }
01230       }
01231    }
01232 }
01233 
01234 // only run while parsing the header (3 times)
01235 static int vorbis_validate(uint8 *data)
01236 {
01237    static uint8 vorbis[6] = { 'v', 'o', 'r', 'b', 'i', 's' };
01238    return memcmp(data, vorbis, 6) == 0;
01239 }
01240 
01241 // called from setup only, once per code book
01242 // (formula implied by specification)
01243 static int lookup1_values(int entries, int dim)
01244 {
01245    int r = (int) floor(exp((float) log((float) entries) / dim));
01246    if ((int) floor(pow((float) r+1, dim)) <= entries)   // (int) cast for MinGW warning;
01247       ++r;                                              // floor() to avoid _ftol() when non-CRT
01248    if (pow((float) r+1, dim) <= entries)
01249       return -1;
01250    if ((int) floor(pow((float) r, dim)) > entries)
01251       return -1;
01252    return r;
01253 }
01254 
01255 // called twice per file
01256 static void compute_twiddle_factors(int n, float *A, float *B, float *C)
01257 {
01258    int n4 = n >> 2, n8 = n >> 3;
01259    int k,k2;
01260 
01261    for (k=k2=0; k < n4; ++k,k2+=2) {
01262       A[k2  ] = (float)  cos(4*k*M_PI/n);
01263       A[k2+1] = (float) -sin(4*k*M_PI/n);
01264       B[k2  ] = (float)  cos((k2+1)*M_PI/n/2) * 0.5f;
01265       B[k2+1] = (float)  sin((k2+1)*M_PI/n/2) * 0.5f;
01266    }
01267    for (k=k2=0; k < n8; ++k,k2+=2) {
01268       C[k2  ] = (float)  cos(2*(k2+1)*M_PI/n);
01269       C[k2+1] = (float) -sin(2*(k2+1)*M_PI/n);
01270    }
01271 }
01272 
01273 static void compute_window(int n, float *window)
01274 {
01275    int n2 = n >> 1, i;
01276    for (i=0; i < n2; ++i)
01277       window[i] = (float) sin(0.5 * M_PI * square((float) sin((i - 0 + 0.5) / n2 * 0.5 * M_PI)));
01278 }
01279 
01280 static void compute_bitreverse(int n, uint16 *rev)
01281 {
01282    int ld = ilog(n) - 1; // ilog is off-by-one from normal definitions
01283    int i, n8 = n >> 3;
01284    for (i=0; i < n8; ++i)
01285       rev[i] = (bit_reverse(i) >> (32-ld+3)) << 2;
01286 }
01287 
01288 static int init_blocksize(vorb *f, int b, int n)
01289 {
01290    int n2 = n >> 1, n4 = n >> 2, n8 = n >> 3;
01291    f->A[b] = (float *) setup_malloc(f, sizeof(float) * n2);
01292    f->B[b] = (float *) setup_malloc(f, sizeof(float) * n2);
01293    f->C[b] = (float *) setup_malloc(f, sizeof(float) * n4);
01294    if (!f->A[b] || !f->B[b] || !f->C[b]) return error(f, VORBIS_outofmem);
01295    compute_twiddle_factors(n, f->A[b], f->B[b], f->C[b]);
01296    f->window[b] = (float *) setup_malloc(f, sizeof(float) * n2);
01297    if (!f->window[b]) return error(f, VORBIS_outofmem);
01298    compute_window(n, f->window[b]);
01299    f->bit_reverse[b] = (uint16 *) setup_malloc(f, sizeof(uint16) * n8);
01300    if (!f->bit_reverse[b]) return error(f, VORBIS_outofmem);
01301    compute_bitreverse(n, f->bit_reverse[b]);
01302    return TRUE;
01303 }
01304 
01305 static void neighbors(uint16 *x, int n, int *plow, int *phigh)
01306 {
01307    int low = -1;
01308    int high = 65536;
01309    int i;
01310    for (i=0; i < n; ++i) {
01311       if (x[i] > low  && x[i] < x[n]) { *plow  = i; low = x[i]; }
01312       if (x[i] < high && x[i] > x[n]) { *phigh = i; high = x[i]; }
01313    }
01314 }
01315 
01316 // this has been repurposed so y is now the original index instead of y
01317 typedef struct
01318 {
01319    uint16 x,id;
01320 } stbv__floor_ordering;
01321 
01322 static int STBV_CDECL point_compare(const void *p, const void *q)
01323 {
01324    stbv__floor_ordering *a = (stbv__floor_ordering *) p;
01325    stbv__floor_ordering *b = (stbv__floor_ordering *) q;
01326    return a->x < b->x ? -1 : a->x > b->x;
01327 }
01328 
01329 //
01331 
01332 #ifdef __SDL_SOUND_INTERNAL__
01333    #define USE_MEMORY(z)    FALSE
01334 #elif defined(STB_VORBIS_NO_STDIO)
01335    #define USE_MEMORY(z)    TRUE
01336 #else
01337    #define USE_MEMORY(z)    ((z)->stream)
01338 #endif
01339 
01340 static uint8 get8(vorb *z)
01341 {
01342    if (USE_MEMORY(z)) {
01343       if (z->stream >= z->stream_end) { z->eof = TRUE; return 0; }
01344       return *z->stream++;
01345    }
01346 
01347    #ifdef __SDL_SOUND_INTERNAL__
01348    {
01349       uint8 c;
01350       if (z->rwops == NULL || SDL_RWread(z->rwops, &c, 1, 1) != 1) {
01351           z->eof = TRUE;
01352           return 0;
01353       }
01354       return c;
01355    }
01356    #endif
01357 
01358 
01359    #ifndef STB_VORBIS_NO_STDIO
01360    {
01361    int c = fgetc(z->f);
01362    if (c == EOF) { z->eof = TRUE; return 0; }
01363    return c;
01364    }
01365    #endif
01366 }
01367 
01368 static uint32 get32(vorb *f)
01369 {
01370    uint32 x;
01371    x = get8(f);
01372    x += get8(f) << 8;
01373    x += get8(f) << 16;
01374    x += (uint32) get8(f) << 24;
01375    return x;
01376 }
01377 
01378 static int getn(vorb *z, uint8 *data, int n)
01379 {
01380    if (USE_MEMORY(z)) {
01381       if (z->stream+n > z->stream_end) { z->eof = 1; return 0; }
01382       memcpy(data, z->stream, n);
01383       z->stream += n;
01384       return 1;
01385    }
01386 
01387    #ifdef __SDL_SOUND_INTERNAL__
01388    {
01389       if (SDL_RWread(z->rwops, data, n, 1) == 1) { return 1; }
01390       z->eof = 1;
01391       return 0;
01392    }
01393    #endif
01394 
01395    #ifndef STB_VORBIS_NO_STDIO   
01396    if (fread(data, n, 1, z->f) == 1)
01397       return 1;
01398    else {
01399       z->eof = 1;
01400       return 0;
01401    }
01402    #endif
01403 }
01404 
01405 static void skip(vorb *z, int n)
01406 {
01407    if (USE_MEMORY(z)) {
01408       z->stream += n;
01409       if (z->stream >= z->stream_end) z->eof = 1;
01410       return;
01411    }
01412 
01413    #ifdef __SDL_SOUND_INTERNAL__
01414    {
01415       SDL_RWseek(z->rwops, n, RW_SEEK_CUR);
01416    }
01417    #endif
01418 
01419    #ifndef STB_VORBIS_NO_STDIO
01420    {
01421       long x = ftell(z->f);
01422       fseek(z->f, x+n, SEEK_SET);
01423    }
01424    #endif
01425 }
01426 
01427 static int set_file_offset(stb_vorbis *f, unsigned int loc)
01428 {
01429    #ifndef STB_VORBIS_NO_PUSHDATA_API
01430    if (f->push_mode) return 0;
01431    #endif
01432    f->eof = 0;
01433    if (USE_MEMORY(f)) {
01434       if (f->stream_start + loc >= f->stream_end || f->stream_start + loc < f->stream_start) {
01435          f->stream = f->stream_end;
01436          f->eof = 1;
01437          return 0;
01438       } else {
01439          f->stream = f->stream_start + loc;
01440          return 1;
01441       }
01442    }
01443 
01444    #ifdef __SDL_SOUND_INTERNAL__
01445    {
01446    if (loc + f->rwops_start < loc || loc >= 0x80000000) {
01447       loc = 0x7fffffff;
01448       f->eof = 1;
01449    } else {
01450       loc += f->rwops_start;
01451    }
01452    if (SDL_RWseek(f->rwops, loc, RW_SEEK_SET) != -1)
01453       return 1;
01454    f->eof = 1;
01455    SDL_RWseek(f->rwops, f->rwops_start, RW_SEEK_END);
01456    return 0;
01457    }
01458    #endif
01459 
01460    #ifndef STB_VORBIS_NO_STDIO
01461    if (loc + f->f_start < loc || loc >= 0x80000000) {
01462       loc = 0x7fffffff;
01463       f->eof = 1;
01464    } else {
01465       loc += f->f_start;
01466    }
01467    if (!fseek(f->f, loc, SEEK_SET))
01468       return 1;
01469    f->eof = 1;
01470    fseek(f->f, f->f_start, SEEK_END);
01471    return 0;
01472    #endif
01473 }
01474 
01475 
01476 static uint8 ogg_page_header[4] = { 0x4f, 0x67, 0x67, 0x53 };
01477 
01478 static int capture_pattern(vorb *f)
01479 {
01480    if (0x4f != get8(f)) return FALSE;
01481    if (0x67 != get8(f)) return FALSE;
01482    if (0x67 != get8(f)) return FALSE;
01483    if (0x53 != get8(f)) return FALSE;
01484    return TRUE;
01485 }
01486 
01487 #define PAGEFLAG_continued_packet   1
01488 #define PAGEFLAG_first_page         2
01489 #define PAGEFLAG_last_page          4
01490 
01491 static int start_page_no_capturepattern(vorb *f)
01492 {
01493    uint32 loc0,loc1,n;
01494    if (f->first_decode && !IS_PUSH_MODE(f)) {
01495       f->p_first.page_start = stb_vorbis_get_file_offset(f) - 4;
01496    }
01497    // stream structure version
01498    if (0 != get8(f)) return error(f, VORBIS_invalid_stream_structure_version);
01499    // header flag
01500    f->page_flag = get8(f);
01501    // absolute granule position
01502    loc0 = get32(f);
01503    loc1 = get32(f);
01504    // @TODO: validate loc0,loc1 as valid positions?
01505    // stream serial number -- vorbis doesn't interleave, so discard
01506    get32(f);
01507    //if (f->serial != get32(f)) return error(f, VORBIS_incorrect_stream_serial_number);
01508    // page sequence number
01509    n = get32(f);
01510    f->last_page = n;
01511    // CRC32
01512    get32(f);
01513    // page_segments
01514    f->segment_count = get8(f);
01515    if (!getn(f, f->segments, f->segment_count))
01516       return error(f, VORBIS_unexpected_eof);
01517    // assume we _don't_ know any the sample position of any segments
01518    f->end_seg_with_known_loc = -2;
01519    if (loc0 != ~0U || loc1 != ~0U) {
01520       int i;
01521       // determine which packet is the last one that will complete
01522       for (i=f->segment_count-1; i >= 0; --i)
01523          if (f->segments[i] < 255)
01524             break;
01525       // 'i' is now the index of the _last_ segment of a packet that ends
01526       if (i >= 0) {
01527          f->end_seg_with_known_loc = i;
01528          f->known_loc_for_packet   = loc0;
01529       }
01530    }
01531    if (f->first_decode) {
01532       int i,len;
01533       len = 0;
01534       for (i=0; i < f->segment_count; ++i)
01535          len += f->segments[i];
01536       len += 27 + f->segment_count;
01537       f->p_first.page_end = f->p_first.page_start + len;
01538       f->p_first.last_decoded_sample = loc0;
01539    }
01540    f->next_seg = 0;
01541    return TRUE;
01542 }
01543 
01544 static int start_page(vorb *f)
01545 {
01546    if (!capture_pattern(f)) return error(f, VORBIS_missing_capture_pattern);
01547    return start_page_no_capturepattern(f);
01548 }
01549 
01550 static int start_packet(vorb *f)
01551 {
01552    while (f->next_seg == -1) {
01553       if (!start_page(f)) return FALSE;
01554       if (f->page_flag & PAGEFLAG_continued_packet)
01555          return error(f, VORBIS_continued_packet_flag_invalid);
01556    }
01557    f->last_seg = FALSE;
01558    f->valid_bits = 0;
01559    f->packet_bytes = 0;
01560    f->bytes_in_seg = 0;
01561    // f->next_seg is now valid
01562    return TRUE;
01563 }
01564 
01565 static int maybe_start_packet(vorb *f)
01566 {
01567    if (f->next_seg == -1) {
01568       int x = get8(f);
01569       if (f->eof) return FALSE; // EOF at page boundary is not an error!
01570       if (0x4f != x      ) return error(f, VORBIS_missing_capture_pattern);
01571       if (0x67 != get8(f)) return error(f, VORBIS_missing_capture_pattern);
01572       if (0x67 != get8(f)) return error(f, VORBIS_missing_capture_pattern);
01573       if (0x53 != get8(f)) return error(f, VORBIS_missing_capture_pattern);
01574       if (!start_page_no_capturepattern(f)) return FALSE;
01575       if (f->page_flag & PAGEFLAG_continued_packet) {
01576          // set up enough state that we can read this packet if we want,
01577          // e.g. during recovery
01578          f->last_seg = FALSE;
01579          f->bytes_in_seg = 0;
01580          return error(f, VORBIS_continued_packet_flag_invalid);
01581       }
01582    }
01583    return start_packet(f);
01584 }
01585 
01586 static int next_segment(vorb *f)
01587 {
01588    int len;
01589    if (f->last_seg) return 0;
01590    if (f->next_seg == -1) {
01591       f->last_seg_which = f->segment_count-1; // in case start_page fails
01592       if (!start_page(f)) { f->last_seg = 1; return 0; }
01593       if (!(f->page_flag & PAGEFLAG_continued_packet)) return error(f, VORBIS_continued_packet_flag_invalid);
01594    }
01595    len = f->segments[f->next_seg++];
01596    if (len < 255) {
01597       f->last_seg = TRUE;
01598       f->last_seg_which = f->next_seg-1;
01599    }
01600    if (f->next_seg >= f->segment_count)
01601       f->next_seg = -1;
01602    assert(f->bytes_in_seg == 0);
01603    f->bytes_in_seg = len;
01604    return len;
01605 }
01606 
01607 #define EOP    (-1)
01608 #define INVALID_BITS  (-1)
01609 
01610 static int get8_packet_raw(vorb *f)
01611 {
01612    if (!f->bytes_in_seg) {  // CLANG!
01613       if (f->last_seg) return EOP;
01614       else if (!next_segment(f)) return EOP;
01615    }
01616    assert(f->bytes_in_seg > 0);
01617    --f->bytes_in_seg;
01618    ++f->packet_bytes;
01619    return get8(f);
01620 }
01621 
01622 static int get8_packet(vorb *f)
01623 {
01624    int x = get8_packet_raw(f);
01625    f->valid_bits = 0;
01626    return x;
01627 }
01628 
01629 static int get32_packet(vorb *f)
01630 {
01631    uint32 x;
01632    x = get8_packet(f);
01633    x += get8_packet(f) << 8;
01634    x += get8_packet(f) << 16;
01635    x += (uint32) get8_packet(f) << 24;
01636    return x;
01637 }
01638 
01639 static void flush_packet(vorb *f)
01640 {
01641    while (get8_packet_raw(f) != EOP);
01642 }
01643 
01644 // @OPTIMIZE: this is the secondary bit decoder, so it's probably not as important
01645 // as the huffman decoder?
01646 static uint32 get_bits(vorb *f, int n)
01647 {
01648    uint32 z;
01649 
01650    if (f->valid_bits < 0) return 0;
01651    if (f->valid_bits < n) {
01652       if (n > 24) {
01653          // the accumulator technique below would not work correctly in this case
01654          z = get_bits(f, 24);
01655          z += get_bits(f, n-24) << 24;
01656          return z;
01657       }
01658       if (f->valid_bits == 0) f->acc = 0;
01659       while (f->valid_bits < n) {
01660          int z = get8_packet_raw(f);
01661          if (z == EOP) {
01662             f->valid_bits = INVALID_BITS;
01663             return 0;
01664          }
01665          f->acc += z << f->valid_bits;
01666          f->valid_bits += 8;
01667       }
01668    }
01669    z = f->acc & ((1 << n)-1);
01670    f->acc >>= n;
01671    f->valid_bits -= n;
01672    return z;
01673 }
01674 
01675 // @OPTIMIZE: primary accumulator for huffman
01676 // expand the buffer to as many bits as possible without reading off end of packet
01677 // it might be nice to allow f->valid_bits and f->acc to be stored in registers,
01678 // e.g. cache them locally and decode locally
01679 static __forceinline void prep_huffman(vorb *f)
01680 {
01681    if (f->valid_bits <= 24) {
01682       if (f->valid_bits == 0) f->acc = 0;
01683       do {
01684          int z;
01685          if (f->last_seg && !f->bytes_in_seg) return;
01686          z = get8_packet_raw(f);
01687          if (z == EOP) return;
01688          f->acc += (unsigned) z << f->valid_bits;
01689          f->valid_bits += 8;
01690       } while (f->valid_bits <= 24);
01691    }
01692 }
01693 
01694 enum
01695 {
01696    VORBIS_packet_id = 1,
01697    VORBIS_packet_comment = 3,
01698    VORBIS_packet_setup = 5
01699 };
01700 
01701 static int codebook_decode_scalar_raw(vorb *f, Codebook *c)
01702 {
01703    int i;
01704    prep_huffman(f);
01705 
01706    if (c->codewords == NULL && c->sorted_codewords == NULL)
01707       return -1;
01708 
01709    // cases to use binary search: sorted_codewords && !c->codewords
01710    //                             sorted_codewords && c->entries > 8
01711    if (c->entries > 8 ? c->sorted_codewords!=NULL : !c->codewords) {
01712       // binary search
01713       uint32 code = bit_reverse(f->acc);
01714       int x=0, n=c->sorted_entries, len;
01715 
01716       while (n > 1) {
01717          // invariant: sc[x] <= code < sc[x+n]
01718          int m = x + (n >> 1);
01719          if (c->sorted_codewords[m] <= code) {
01720             x = m;
01721             n -= (n>>1);
01722          } else {
01723             n >>= 1;
01724          }
01725       }
01726       // x is now the sorted index
01727       if (!c->sparse) x = c->sorted_values[x];
01728       // x is now sorted index if sparse, or symbol otherwise
01729       len = c->codeword_lengths[x];
01730       if (f->valid_bits >= len) {
01731          f->acc >>= len;
01732          f->valid_bits -= len;
01733          return x;
01734       }
01735 
01736       f->valid_bits = 0;
01737       return -1;
01738    }
01739 
01740    // if small, linear search
01741    assert(!c->sparse);
01742    for (i=0; i < c->entries; ++i) {
01743       if (c->codeword_lengths[i] == NO_CODE) continue;
01744       if (c->codewords[i] == (f->acc & ((1 << c->codeword_lengths[i])-1))) {
01745          if (f->valid_bits >= c->codeword_lengths[i]) {
01746             f->acc >>= c->codeword_lengths[i];
01747             f->valid_bits -= c->codeword_lengths[i];
01748             return i;
01749          }
01750          f->valid_bits = 0;
01751          return -1;
01752       }
01753    }
01754 
01755    error(f, VORBIS_invalid_stream);
01756    f->valid_bits = 0;
01757    return -1;
01758 }
01759 
01760 #ifndef STB_VORBIS_NO_INLINE_DECODE
01761 
01762 #define DECODE_RAW(var, f,c)                                  \
01763    if (f->valid_bits < STB_VORBIS_FAST_HUFFMAN_LENGTH)        \
01764       prep_huffman(f);                                        \
01765    var = f->acc & FAST_HUFFMAN_TABLE_MASK;                    \
01766    var = c->fast_huffman[var];                                \
01767    if (var >= 0) {                                            \
01768       int n = c->codeword_lengths[var];                       \
01769       f->acc >>= n;                                           \
01770       f->valid_bits -= n;                                     \
01771       if (f->valid_bits < 0) { f->valid_bits = 0; var = -1; } \
01772    } else {                                                   \
01773       var = codebook_decode_scalar_raw(f,c);                  \
01774    }
01775 
01776 #else
01777 
01778 static int codebook_decode_scalar(vorb *f, Codebook *c)
01779 {
01780    int i;
01781    if (f->valid_bits < STB_VORBIS_FAST_HUFFMAN_LENGTH)
01782       prep_huffman(f);
01783    // fast huffman table lookup
01784    i = f->acc & FAST_HUFFMAN_TABLE_MASK;
01785    i = c->fast_huffman[i];
01786    if (i >= 0) {
01787       f->acc >>= c->codeword_lengths[i];
01788       f->valid_bits -= c->codeword_lengths[i];
01789       if (f->valid_bits < 0) { f->valid_bits = 0; return -1; }
01790       return i;
01791    }
01792    return codebook_decode_scalar_raw(f,c);
01793 }
01794 
01795 #define DECODE_RAW(var,f,c)    var = codebook_decode_scalar(f,c);
01796 
01797 #endif
01798 
01799 #define DECODE(var,f,c)                                       \
01800    DECODE_RAW(var,f,c)                                        \
01801    if (c->sparse) var = c->sorted_values[var];
01802 
01803 #ifndef STB_VORBIS_DIVIDES_IN_CODEBOOK
01804   #define DECODE_VQ(var,f,c)   DECODE_RAW(var,f,c)
01805 #else
01806   #define DECODE_VQ(var,f,c)   DECODE(var,f,c)
01807 #endif
01808 
01809 
01810 
01811 
01812 
01813 
01814 // CODEBOOK_ELEMENT_FAST is an optimization for the CODEBOOK_FLOATS case
01815 // where we avoid one addition
01816 #define CODEBOOK_ELEMENT(c,off)          (c->multiplicands[off])
01817 #define CODEBOOK_ELEMENT_FAST(c,off)     (c->multiplicands[off])
01818 #define CODEBOOK_ELEMENT_BASE(c)         (0)
01819 
01820 static int codebook_decode_start(vorb *f, Codebook *c)
01821 {
01822    int z = -1;
01823 
01824    // type 0 is only legal in a scalar context
01825    if (c->lookup_type == 0)
01826       error(f, VORBIS_invalid_stream);
01827    else {
01828       DECODE_VQ(z,f,c);
01829       if (c->sparse) assert(z < c->sorted_entries);
01830       if (z < 0) {  // check for EOP
01831          if (!f->bytes_in_seg)
01832             if (f->last_seg)
01833                return z;
01834          error(f, VORBIS_invalid_stream);
01835       }
01836    }
01837    return z;
01838 }
01839 
01840 static int codebook_decode(vorb *f, Codebook *c, float *output, int len)
01841 {
01842    int i,z = codebook_decode_start(f,c);
01843    if (z < 0) return FALSE;
01844    if (len > c->dimensions) len = c->dimensions;
01845 
01846 #ifdef STB_VORBIS_DIVIDES_IN_CODEBOOK
01847    if (c->lookup_type == 1) {
01848       float last = CODEBOOK_ELEMENT_BASE(c);
01849       int div = 1;
01850       for (i=0; i < len; ++i) {
01851          int off = (z / div) % c->lookup_values;
01852          float val = CODEBOOK_ELEMENT_FAST(c,off) + last;
01853          output[i] += val;
01854          if (c->sequence_p) last = val + c->minimum_value;
01855          div *= c->lookup_values;
01856       }
01857       return TRUE;
01858    }
01859 #endif
01860 
01861    z *= c->dimensions;
01862    if (c->sequence_p) {
01863       float last = CODEBOOK_ELEMENT_BASE(c);
01864       for (i=0; i < len; ++i) {
01865          float val = CODEBOOK_ELEMENT_FAST(c,z+i) + last;
01866          output[i] += val;
01867          last = val + c->minimum_value;
01868       }
01869    } else {
01870       float last = CODEBOOK_ELEMENT_BASE(c);
01871       for (i=0; i < len; ++i) {
01872          output[i] += CODEBOOK_ELEMENT_FAST(c,z+i) + last;
01873       }
01874    }
01875 
01876    return TRUE;
01877 }
01878 
01879 static int codebook_decode_step(vorb *f, Codebook *c, float *output, int len, int step)
01880 {
01881    int i,z = codebook_decode_start(f,c);
01882    float last = CODEBOOK_ELEMENT_BASE(c);
01883    if (z < 0) return FALSE;
01884    if (len > c->dimensions) len = c->dimensions;
01885 
01886 #ifdef STB_VORBIS_DIVIDES_IN_CODEBOOK
01887    if (c->lookup_type == 1) {
01888       int div = 1;
01889       for (i=0; i < len; ++i) {
01890          int off = (z / div) % c->lookup_values;
01891          float val = CODEBOOK_ELEMENT_FAST(c,off) + last;
01892          output[i*step] += val;
01893          if (c->sequence_p) last = val;
01894          div *= c->lookup_values;
01895       }
01896       return TRUE;
01897    }
01898 #endif
01899 
01900    z *= c->dimensions;
01901    for (i=0; i < len; ++i) {
01902       float val = CODEBOOK_ELEMENT_FAST(c,z+i) + last;
01903       output[i*step] += val;
01904       if (c->sequence_p) last = val;
01905    }
01906 
01907    return TRUE;
01908 }
01909 
01910 static int codebook_decode_deinterleave_repeat(vorb *f, Codebook *c, float **outputs, int ch, int *c_inter_p, int *p_inter_p, int len, int total_decode)
01911 {
01912    int c_inter = *c_inter_p;
01913    int p_inter = *p_inter_p;
01914    int i,z, effective = c->dimensions;
01915 
01916    // type 0 is only legal in a scalar context
01917    if (c->lookup_type == 0)   return error(f, VORBIS_invalid_stream);
01918 
01919    while (total_decode > 0) {
01920       float last = CODEBOOK_ELEMENT_BASE(c);
01921       DECODE_VQ(z,f,c);
01922       #ifndef STB_VORBIS_DIVIDES_IN_CODEBOOK
01923       assert(!c->sparse || z < c->sorted_entries);
01924       #endif
01925       if (z < 0) {
01926          if (!f->bytes_in_seg)
01927             if (f->last_seg) return FALSE;
01928          return error(f, VORBIS_invalid_stream);
01929       }
01930 
01931       // if this will take us off the end of the buffers, stop short!
01932       // we check by computing the length of the virtual interleaved
01933       // buffer (len*ch), our current offset within it (p_inter*ch)+(c_inter),
01934       // and the length we'll be using (effective)
01935       if (c_inter + p_inter*ch + effective > len * ch) {
01936          effective = len*ch - (p_inter*ch - c_inter);
01937       }
01938 
01939    #ifdef STB_VORBIS_DIVIDES_IN_CODEBOOK
01940       if (c->lookup_type == 1) {
01941          int div = 1;
01942          for (i=0; i < effective; ++i) {
01943             int off = (z / div) % c->lookup_values;
01944             float val = CODEBOOK_ELEMENT_FAST(c,off) + last;
01945             if (outputs[c_inter])
01946                outputs[c_inter][p_inter] += val;
01947             if (++c_inter == ch) { c_inter = 0; ++p_inter; }
01948             if (c->sequence_p) last = val;
01949             div *= c->lookup_values;
01950          }
01951       } else
01952    #endif
01953       {
01954          z *= c->dimensions;
01955          if (c->sequence_p) {
01956             for (i=0; i < effective; ++i) {
01957                float val = CODEBOOK_ELEMENT_FAST(c,z+i) + last;
01958                if (outputs[c_inter])
01959                   outputs[c_inter][p_inter] += val;
01960                if (++c_inter == ch) { c_inter = 0; ++p_inter; }
01961                last = val;
01962             }
01963          } else {
01964             for (i=0; i < effective; ++i) {
01965                float val = CODEBOOK_ELEMENT_FAST(c,z+i) + last;
01966                if (outputs[c_inter])
01967                   outputs[c_inter][p_inter] += val;
01968                if (++c_inter == ch) { c_inter = 0; ++p_inter; }
01969             }
01970          }
01971       }
01972 
01973       total_decode -= effective;
01974    }
01975    *c_inter_p = c_inter;
01976    *p_inter_p = p_inter;
01977    return TRUE;
01978 }
01979 
01980 static int predict_point(int x, int x0, int x1, int y0, int y1)
01981 {
01982    int dy = y1 - y0;
01983    int adx = x1 - x0;
01984    // @OPTIMIZE: force int division to round in the right direction... is this necessary on x86?
01985    int err = abs(dy) * (x - x0);
01986    int off = err / adx;
01987    return dy < 0 ? y0 - off : y0 + off;
01988 }
01989 
01990 // the following table is block-copied from the specification
01991 static float inverse_db_table[256] =
01992 {
01993   1.0649863e-07f, 1.1341951e-07f, 1.2079015e-07f, 1.2863978e-07f,
01994   1.3699951e-07f, 1.4590251e-07f, 1.5538408e-07f, 1.6548181e-07f,
01995   1.7623575e-07f, 1.8768855e-07f, 1.9988561e-07f, 2.1287530e-07f,
01996   2.2670913e-07f, 2.4144197e-07f, 2.5713223e-07f, 2.7384213e-07f,
01997   2.9163793e-07f, 3.1059021e-07f, 3.3077411e-07f, 3.5226968e-07f,
01998   3.7516214e-07f, 3.9954229e-07f, 4.2550680e-07f, 4.5315863e-07f,
01999   4.8260743e-07f, 5.1396998e-07f, 5.4737065e-07f, 5.8294187e-07f,
02000   6.2082472e-07f, 6.6116941e-07f, 7.0413592e-07f, 7.4989464e-07f,
02001   7.9862701e-07f, 8.5052630e-07f, 9.0579828e-07f, 9.6466216e-07f,
02002   1.0273513e-06f, 1.0941144e-06f, 1.1652161e-06f, 1.2409384e-06f,
02003   1.3215816e-06f, 1.4074654e-06f, 1.4989305e-06f, 1.5963394e-06f,
02004   1.7000785e-06f, 1.8105592e-06f, 1.9282195e-06f, 2.0535261e-06f,
02005   2.1869758e-06f, 2.3290978e-06f, 2.4804557e-06f, 2.6416497e-06f,
02006   2.8133190e-06f, 2.9961443e-06f, 3.1908506e-06f, 3.3982101e-06f,
02007   3.6190449e-06f, 3.8542308e-06f, 4.1047004e-06f, 4.3714470e-06f,
02008   4.6555282e-06f, 4.9580707e-06f, 5.2802740e-06f, 5.6234160e-06f,
02009   5.9888572e-06f, 6.3780469e-06f, 6.7925283e-06f, 7.2339451e-06f,
02010   7.7040476e-06f, 8.2047000e-06f, 8.7378876e-06f, 9.3057248e-06f,
02011   9.9104632e-06f, 1.0554501e-05f, 1.1240392e-05f, 1.1970856e-05f,
02012   1.2748789e-05f, 1.3577278e-05f, 1.4459606e-05f, 1.5399272e-05f,
02013   1.6400004e-05f, 1.7465768e-05f, 1.8600792e-05f, 1.9809576e-05f,
02014   2.1096914e-05f, 2.2467911e-05f, 2.3928002e-05f, 2.5482978e-05f,
02015   2.7139006e-05f, 2.8902651e-05f, 3.0780908e-05f, 3.2781225e-05f,
02016   3.4911534e-05f, 3.7180282e-05f, 3.9596466e-05f, 4.2169667e-05f,
02017   4.4910090e-05f, 4.7828601e-05f, 5.0936773e-05f, 5.4246931e-05f,
02018   5.7772202e-05f, 6.1526565e-05f, 6.5524908e-05f, 6.9783085e-05f,
02019   7.4317983e-05f, 7.9147585e-05f, 8.4291040e-05f, 8.9768747e-05f,
02020   9.5602426e-05f, 0.00010181521f, 0.00010843174f, 0.00011547824f,
02021   0.00012298267f, 0.00013097477f, 0.00013948625f, 0.00014855085f,
02022   0.00015820453f, 0.00016848555f, 0.00017943469f, 0.00019109536f,
02023   0.00020351382f, 0.00021673929f, 0.00023082423f, 0.00024582449f,
02024   0.00026179955f, 0.00027881276f, 0.00029693158f, 0.00031622787f,
02025   0.00033677814f, 0.00035866388f, 0.00038197188f, 0.00040679456f,
02026   0.00043323036f, 0.00046138411f, 0.00049136745f, 0.00052329927f,
02027   0.00055730621f, 0.00059352311f, 0.00063209358f, 0.00067317058f,
02028   0.00071691700f, 0.00076350630f, 0.00081312324f, 0.00086596457f,
02029   0.00092223983f, 0.00098217216f, 0.0010459992f,  0.0011139742f,
02030   0.0011863665f,  0.0012634633f,  0.0013455702f,  0.0014330129f,
02031   0.0015261382f,  0.0016253153f,  0.0017309374f,  0.0018434235f,
02032   0.0019632195f,  0.0020908006f,  0.0022266726f,  0.0023713743f,
02033   0.0025254795f,  0.0026895994f,  0.0028643847f,  0.0030505286f,
02034   0.0032487691f,  0.0034598925f,  0.0036847358f,  0.0039241906f,
02035   0.0041792066f,  0.0044507950f,  0.0047400328f,  0.0050480668f,
02036   0.0053761186f,  0.0057254891f,  0.0060975636f,  0.0064938176f,
02037   0.0069158225f,  0.0073652516f,  0.0078438871f,  0.0083536271f,
02038   0.0088964928f,  0.009474637f,   0.010090352f,   0.010746080f,
02039   0.011444421f,   0.012188144f,   0.012980198f,   0.013823725f,
02040   0.014722068f,   0.015678791f,   0.016697687f,   0.017782797f,
02041   0.018938423f,   0.020169149f,   0.021479854f,   0.022875735f,
02042   0.024362330f,   0.025945531f,   0.027631618f,   0.029427276f,
02043   0.031339626f,   0.033376252f,   0.035545228f,   0.037855157f,
02044   0.040315199f,   0.042935108f,   0.045725273f,   0.048696758f,
02045   0.051861348f,   0.055231591f,   0.058820850f,   0.062643361f,
02046   0.066714279f,   0.071049749f,   0.075666962f,   0.080584227f,
02047   0.085821044f,   0.091398179f,   0.097337747f,   0.10366330f,
02048   0.11039993f,    0.11757434f,    0.12521498f,    0.13335215f,
02049   0.14201813f,    0.15124727f,    0.16107617f,    0.17154380f,
02050   0.18269168f,    0.19456402f,    0.20720788f,    0.22067342f,
02051   0.23501402f,    0.25028656f,    0.26655159f,    0.28387361f,
02052   0.30232132f,    0.32196786f,    0.34289114f,    0.36517414f,
02053   0.38890521f,    0.41417847f,    0.44109412f,    0.46975890f,
02054   0.50028648f,    0.53279791f,    0.56742212f,    0.60429640f,
02055   0.64356699f,    0.68538959f,    0.72993007f,    0.77736504f,
02056   0.82788260f,    0.88168307f,    0.9389798f,     1.0f
02057 };
02058 
02059 
02060 // @OPTIMIZE: if you want to replace this bresenham line-drawing routine,
02061 // note that you must produce bit-identical output to decode correctly;
02062 // this specific sequence of operations is specified in the spec (it's
02063 // drawing integer-quantized frequency-space lines that the encoder
02064 // expects to be exactly the same)
02065 //     ... also, isn't the whole point of Bresenham's algorithm to NOT
02066 // have to divide in the setup? sigh.
02067 #ifndef STB_VORBIS_NO_DEFER_FLOOR
02068 #define LINE_OP(a,b)   a *= b
02069 #else
02070 #define LINE_OP(a,b)   a = b
02071 #endif
02072 
02073 #ifdef STB_VORBIS_DIVIDE_TABLE
02074 #define DIVTAB_NUMER   32
02075 #define DIVTAB_DENOM   64
02076 int8 integer_divide_table[DIVTAB_NUMER][DIVTAB_DENOM]; // 2KB
02077 #endif
02078 
02079 static __forceinline void draw_line(float *output, int x0, int y0, int x1, int y1, int n)
02080 {
02081    int dy = y1 - y0;
02082    int adx = x1 - x0;
02083    int ady = abs(dy);
02084    int base;
02085    int x=x0,y=y0;
02086    int err = 0;
02087    int sy;
02088 
02089 #ifdef STB_VORBIS_DIVIDE_TABLE
02090    if (adx < DIVTAB_DENOM && ady < DIVTAB_NUMER) {
02091       if (dy < 0) {
02092          base = -integer_divide_table[ady][adx];
02093          sy = base-1;
02094       } else {
02095          base =  integer_divide_table[ady][adx];
02096          sy = base+1;
02097       }
02098    } else {
02099       base = dy / adx;
02100       if (dy < 0)
02101          sy = base - 1;
02102       else
02103          sy = base+1;
02104    }
02105 #else
02106    base = dy / adx;
02107    if (dy < 0)
02108       sy = base - 1;
02109    else
02110       sy = base+1;
02111 #endif
02112    ady -= abs(base) * adx;
02113    if (x1 > n) x1 = n;
02114    if (x < x1) {
02115       LINE_OP(output[x], inverse_db_table[y&255]);
02116       for (++x; x < x1; ++x) {
02117          err += ady;
02118          if (err >= adx) {
02119             err -= adx;
02120             y += sy;
02121          } else
02122             y += base;
02123          LINE_OP(output[x], inverse_db_table[y&255]);
02124       }
02125    }
02126 }
02127 
02128 static int residue_decode(vorb *f, Codebook *book, float *target, int offset, int n, int rtype)
02129 {
02130    int k;
02131    if (rtype == 0) {
02132       int step = n / book->dimensions;
02133       for (k=0; k < step; ++k)
02134          if (!codebook_decode_step(f, book, target+offset+k, n-offset-k, step))
02135             return FALSE;
02136    } else {
02137       for (k=0; k < n; ) {
02138          if (!codebook_decode(f, book, target+offset, n-k))
02139             return FALSE;
02140          k += book->dimensions;
02141          offset += book->dimensions;
02142       }
02143    }
02144    return TRUE;
02145 }
02146 
02147 // n is 1/2 of the blocksize --
02148 // specification: "Correct per-vector decode length is [n]/2"
02149 static void decode_residue(vorb *f, float *residue_buffers[], int ch, int n, int rn, uint8 *do_not_decode)
02150 {
02151    int i,j,pass;
02152    Residue *r = f->residue_config + rn;
02153    int rtype = f->residue_types[rn];
02154    int c = r->classbook;
02155    int classwords = f->codebooks[c].dimensions;
02156    unsigned int actual_size = rtype == 2 ? n*2 : n;
02157    unsigned int limit_r_begin = (r->begin < actual_size ? r->begin : actual_size);
02158    unsigned int limit_r_end   = (r->end   < actual_size ? r->end   : actual_size);
02159    int n_read = limit_r_end - limit_r_begin;
02160    int part_read = n_read / r->part_size;
02161    int temp_alloc_point = temp_alloc_save(f);
02162    #ifndef STB_VORBIS_DIVIDES_IN_RESIDUE
02163    uint8 ***part_classdata = (uint8 ***) temp_block_array(f,f->channels, part_read * sizeof(**part_classdata));
02164    #else
02165    int **classifications = (int **) temp_block_array(f,f->channels, part_read * sizeof(**classifications));
02166    #endif
02167 
02168    CHECK(f);
02169 
02170    for (i=0; i < ch; ++i)
02171       if (!do_not_decode[i])
02172          memset(residue_buffers[i], 0, sizeof(float) * n);
02173 
02174    if (rtype == 2 && ch != 1) {
02175       for (j=0; j < ch; ++j)
02176          if (!do_not_decode[j])
02177             break;
02178       if (j == ch)
02179          goto done;
02180 
02181       for (pass=0; pass < 8; ++pass) {
02182          int pcount = 0, class_set = 0;
02183          if (ch == 2) {
02184             while (pcount < part_read) {
02185                int z = r->begin + pcount*r->part_size;
02186                int c_inter = (z & 1), p_inter = z>>1;
02187                if (pass == 0) {
02188                   Codebook *c = f->codebooks+r->classbook;
02189                   int q;
02190                   DECODE(q,f,c);
02191                   if (q == EOP) goto done;
02192                   #ifndef STB_VORBIS_DIVIDES_IN_RESIDUE
02193                   part_classdata[0][class_set] = r->classdata[q];
02194                   #else
02195                   for (i=classwords-1; i >= 0; --i) {
02196                      classifications[0][i+pcount] = q % r->classifications;
02197                      q /= r->classifications;
02198                   }
02199                   #endif
02200                }
02201                for (i=0; i < classwords && pcount < part_read; ++i, ++pcount) {
02202                   int z = r->begin + pcount*r->part_size;
02203                   #ifndef STB_VORBIS_DIVIDES_IN_RESIDUE
02204                   int c = part_classdata[0][class_set][i];
02205                   #else
02206                   int c = classifications[0][pcount];
02207                   #endif
02208                   int b = r->residue_books[c][pass];
02209                   if (b >= 0) {
02210                      Codebook *book = f->codebooks + b;
02211                      #ifdef STB_VORBIS_DIVIDES_IN_CODEBOOK
02212                      if (!codebook_decode_deinterleave_repeat(f, book, residue_buffers, ch, &c_inter, &p_inter, n, r->part_size))
02213                         goto done;
02214                      #else
02215                      // saves 1%
02216                      if (!codebook_decode_deinterleave_repeat(f, book, residue_buffers, ch, &c_inter, &p_inter, n, r->part_size))
02217                         goto done;
02218                      #endif
02219                   } else {
02220                      z += r->part_size;
02221                      c_inter = z & 1;
02222                      p_inter = z >> 1;
02223                   }
02224                }
02225                #ifndef STB_VORBIS_DIVIDES_IN_RESIDUE
02226                ++class_set;
02227                #endif
02228             }
02229          } else if (ch > 2) {
02230             while (pcount < part_read) {
02231                int z = r->begin + pcount*r->part_size;
02232                int c_inter = z % ch, p_inter = z/ch;
02233                if (pass == 0) {
02234                   Codebook *c = f->codebooks+r->classbook;
02235                   int q;
02236                   DECODE(q,f,c);
02237                   if (q == EOP) goto done;
02238                   #ifndef STB_VORBIS_DIVIDES_IN_RESIDUE
02239                   part_classdata[0][class_set] = r->classdata[q];
02240                   #else
02241                   for (i=classwords-1; i >= 0; --i) {
02242                      classifications[0][i+pcount] = q % r->classifications;
02243                      q /= r->classifications;
02244                   }
02245                   #endif
02246                }
02247                for (i=0; i < classwords && pcount < part_read; ++i, ++pcount) {
02248                   int z = r->begin + pcount*r->part_size;
02249                   #ifndef STB_VORBIS_DIVIDES_IN_RESIDUE
02250                   int c = part_classdata[0][class_set][i];
02251                   #else
02252                   int c = classifications[0][pcount];
02253                   #endif
02254                   int b = r->residue_books[c][pass];
02255                   if (b >= 0) {
02256                      Codebook *book = f->codebooks + b;
02257                      if (!codebook_decode_deinterleave_repeat(f, book, residue_buffers, ch, &c_inter, &p_inter, n, r->part_size))
02258                         goto done;
02259                   } else {
02260                      z += r->part_size;
02261                      c_inter = z % ch;
02262                      p_inter = z / ch;
02263                   }
02264                }
02265                #ifndef STB_VORBIS_DIVIDES_IN_RESIDUE
02266                ++class_set;
02267                #endif
02268             }
02269          }
02270       }
02271       goto done;
02272    }
02273    CHECK(f);
02274 
02275    for (pass=0; pass < 8; ++pass) {
02276       int pcount = 0, class_set=0;
02277       while (pcount < part_read) {
02278          if (pass == 0) {
02279             for (j=0; j < ch; ++j) {
02280                if (!do_not_decode[j]) {
02281                   Codebook *c = f->codebooks+r->classbook;
02282                   int temp;
02283                   DECODE(temp,f,c);
02284                   if (temp == EOP) goto done;
02285                   #ifndef STB_VORBIS_DIVIDES_IN_RESIDUE
02286                   part_classdata[j][class_set] = r->classdata[temp];
02287                   #else
02288                   for (i=classwords-1; i >= 0; --i) {
02289                      classifications[j][i+pcount] = temp % r->classifications;
02290                      temp /= r->classifications;
02291                   }
02292                   #endif
02293                }
02294             }
02295          }
02296          for (i=0; i < classwords && pcount < part_read; ++i, ++pcount) {
02297             for (j=0; j < ch; ++j) {
02298                if (!do_not_decode[j]) {
02299                   #ifndef STB_VORBIS_DIVIDES_IN_RESIDUE
02300                   int c = part_classdata[j][class_set][i];
02301                   #else
02302                   int c = classifications[j][pcount];
02303                   #endif
02304                   int b = r->residue_books[c][pass];
02305                   if (b >= 0) {
02306                      float *target = residue_buffers[j];
02307                      int offset = r->begin + pcount * r->part_size;
02308                      int n = r->part_size;
02309                      Codebook *book = f->codebooks + b;
02310                      if (!residue_decode(f, book, target, offset, n, rtype))
02311                         goto done;
02312                   }
02313                }
02314             }
02315          }
02316          #ifndef STB_VORBIS_DIVIDES_IN_RESIDUE
02317          ++class_set;
02318          #endif
02319       }
02320    }
02321   done:
02322    CHECK(f);
02323    #ifndef STB_VORBIS_DIVIDES_IN_RESIDUE
02324    // temp_free(f,part_classdata);
02325    #else
02326    // temp_free(f,classifications);
02327    #endif
02328    temp_alloc_restore(f,temp_alloc_point);
02329 }
02330 
02331 
02332 #if 0
02333 // slow way for debugging
02334 void inverse_mdct_slow(float *buffer, int n)
02335 {
02336    int i,j;
02337    int n2 = n >> 1;
02338    float *x = (float *) malloc(sizeof(*x) * n2);
02339    memcpy(x, buffer, sizeof(*x) * n2);
02340    for (i=0; i < n; ++i) {
02341       float acc = 0;
02342       for (j=0; j < n2; ++j)
02343          // formula from paper:
02344          //acc += n/4.0f * x[j] * (float) cos(M_PI / 2 / n * (2 * i + 1 + n/2.0)*(2*j+1));
02345          // formula from wikipedia
02346          //acc += 2.0f / n2 * x[j] * (float) cos(M_PI/n2 * (i + 0.5 + n2/2)*(j + 0.5));
02347          // these are equivalent, except the formula from the paper inverts the multiplier!
02348          // however, what actually works is NO MULTIPLIER!?!
02349          //acc += 64 * 2.0f / n2 * x[j] * (float) cos(M_PI/n2 * (i + 0.5 + n2/2)*(j + 0.5));
02350          acc += x[j] * (float) cos(M_PI / 2 / n * (2 * i + 1 + n/2.0)*(2*j+1));
02351       buffer[i] = acc;
02352    }
02353    free(x);
02354 }
02355 #elif 0
02356 // same as above, but just barely able to run in real time on modern machines
02357 void inverse_mdct_slow(float *buffer, int n, vorb *f, int blocktype)
02358 {
02359    float mcos[16384];
02360    int i,j;
02361    int n2 = n >> 1, nmask = (n << 2) -1;
02362    float *x = (float *) malloc(sizeof(*x) * n2);
02363    memcpy(x, buffer, sizeof(*x) * n2);
02364    for (i=0; i < 4*n; ++i)
02365       mcos[i] = (float) cos(M_PI / 2 * i / n);
02366 
02367    for (i=0; i < n; ++i) {
02368       float acc = 0;
02369       for (j=0; j < n2; ++j)
02370          acc += x[j] * mcos[(2 * i + 1 + n2)*(2*j+1) & nmask];
02371       buffer[i] = acc;
02372    }
02373    free(x);
02374 }
02375 #elif 0
02376 // transform to use a slow dct-iv; this is STILL basically trivial,
02377 // but only requires half as many ops
02378 void dct_iv_slow(float *buffer, int n)
02379 {
02380    float mcos[16384];
02381    float x[2048];
02382    int i,j;
02383    int n2 = n >> 1, nmask = (n << 3) - 1;
02384    memcpy(x, buffer, sizeof(*x) * n);
02385    for (i=0; i < 8*n; ++i)
02386       mcos[i] = (float) cos(M_PI / 4 * i / n);
02387    for (i=0; i < n; ++i) {
02388       float acc = 0;
02389       for (j=0; j < n; ++j)
02390          acc += x[j] * mcos[((2 * i + 1)*(2*j+1)) & nmask];
02391       buffer[i] = acc;
02392    }
02393 }
02394 
02395 void inverse_mdct_slow(float *buffer, int n, vorb *f, int blocktype)
02396 {
02397    int i, n4 = n >> 2, n2 = n >> 1, n3_4 = n - n4;
02398    float temp[4096];
02399 
02400    memcpy(temp, buffer, n2 * sizeof(float));
02401    dct_iv_slow(temp, n2);  // returns -c'-d, a-b'
02402 
02403    for (i=0; i < n4  ; ++i) buffer[i] = temp[i+n4];            // a-b'
02404    for (   ; i < n3_4; ++i) buffer[i] = -temp[n3_4 - i - 1];   // b-a', c+d'
02405    for (   ; i < n   ; ++i) buffer[i] = -temp[i - n3_4];       // c'+d
02406 }
02407 #endif
02408 
02409 #ifndef LIBVORBIS_MDCT
02410 #define LIBVORBIS_MDCT 0
02411 #endif
02412 
02413 #if LIBVORBIS_MDCT
02414 // directly call the vorbis MDCT using an interface documented
02415 // by Jeff Roberts... useful for performance comparison
02416 typedef struct
02417 {
02418   int n;
02419   int log2n;
02420 
02421   float *trig;
02422   int   *bitrev;
02423 
02424   float scale;
02425 } mdct_lookup;
02426 
02427 extern void mdct_init(mdct_lookup *lookup, int n);
02428 extern void mdct_clear(mdct_lookup *l);
02429 extern void mdct_backward(mdct_lookup *init, float *in, float *out);
02430 
02431 mdct_lookup M1,M2;
02432 
02433 void inverse_mdct(float *buffer, int n, vorb *f, int blocktype)
02434 {
02435    mdct_lookup *M;
02436    if (M1.n == n) M = &M1;
02437    else if (M2.n == n) M = &M2;
02438    else if (M1.n == 0) { mdct_init(&M1, n); M = &M1; }
02439    else {
02440       if (M2.n) __asm int 3;
02441       mdct_init(&M2, n);
02442       M = &M2;
02443    }
02444 
02445    mdct_backward(M, buffer, buffer);
02446 }
02447 #endif
02448 
02449 
02450 // the following were split out into separate functions while optimizing;
02451 // they could be pushed back up but eh. __forceinline showed no change;
02452 // they're probably already being inlined.
02453 static void imdct_step3_iter0_loop(int n, float *e, int i_off, int k_off, float *A)
02454 {
02455    float *ee0 = e + i_off;
02456    float *ee2 = ee0 + k_off;
02457    int i;
02458 
02459    assert((n & 3) == 0);
02460    for (i=(n>>2); i > 0; --i) {
02461       float k00_20, k01_21;
02462       k00_20  = ee0[ 0] - ee2[ 0];
02463       k01_21  = ee0[-1] - ee2[-1];
02464       ee0[ 0] += ee2[ 0];//ee0[ 0] = ee0[ 0] + ee2[ 0];
02465       ee0[-1] += ee2[-1];//ee0[-1] = ee0[-1] + ee2[-1];
02466       ee2[ 0] = k00_20 * A[0] - k01_21 * A[1];
02467       ee2[-1] = k01_21 * A[0] + k00_20 * A[1];
02468       A += 8;
02469 
02470       k00_20  = ee0[-2] - ee2[-2];
02471       k01_21  = ee0[-3] - ee2[-3];
02472       ee0[-2] += ee2[-2];//ee0[-2] = ee0[-2] + ee2[-2];
02473       ee0[-3] += ee2[-3];//ee0[-3] = ee0[-3] + ee2[-3];
02474       ee2[-2] = k00_20 * A[0] - k01_21 * A[1];
02475       ee2[-3] = k01_21 * A[0] + k00_20 * A[1];
02476       A += 8;
02477 
02478       k00_20  = ee0[-4] - ee2[-4];
02479       k01_21  = ee0[-5] - ee2[-5];
02480       ee0[-4] += ee2[-4];//ee0[-4] = ee0[-4] + ee2[-4];
02481       ee0[-5] += ee2[-5];//ee0[-5] = ee0[-5] + ee2[-5];
02482       ee2[-4] = k00_20 * A[0] - k01_21 * A[1];
02483       ee2[-5] = k01_21 * A[0] + k00_20 * A[1];
02484       A += 8;
02485 
02486       k00_20  = ee0[-6] - ee2[-6];
02487       k01_21  = ee0[-7] - ee2[-7];
02488       ee0[-6] += ee2[-6];//ee0[-6] = ee0[-6] + ee2[-6];
02489       ee0[-7] += ee2[-7];//ee0[-7] = ee0[-7] + ee2[-7];
02490       ee2[-6] = k00_20 * A[0] - k01_21 * A[1];
02491       ee2[-7] = k01_21 * A[0] + k00_20 * A[1];
02492       A += 8;
02493       ee0 -= 8;
02494       ee2 -= 8;
02495    }
02496 }
02497 
02498 static void imdct_step3_inner_r_loop(int lim, float *e, int d0, int k_off, float *A, int k1)
02499 {
02500    int i;
02501    float k00_20, k01_21;
02502 
02503    float *e0 = e + d0;
02504    float *e2 = e0 + k_off;
02505 
02506    for (i=lim >> 2; i > 0; --i) {
02507       k00_20 = e0[-0] - e2[-0];
02508       k01_21 = e0[-1] - e2[-1];
02509       e0[-0] += e2[-0];//e0[-0] = e0[-0] + e2[-0];
02510       e0[-1] += e2[-1];//e0[-1] = e0[-1] + e2[-1];
02511       e2[-0] = (k00_20)*A[0] - (k01_21) * A[1];
02512       e2[-1] = (k01_21)*A[0] + (k00_20) * A[1];
02513 
02514       A += k1;
02515 
02516       k00_20 = e0[-2] - e2[-2];
02517       k01_21 = e0[-3] - e2[-3];
02518       e0[-2] += e2[-2];//e0[-2] = e0[-2] + e2[-2];
02519       e0[-3] += e2[-3];//e0[-3] = e0[-3] + e2[-3];
02520       e2[-2] = (k00_20)*A[0] - (k01_21) * A[1];
02521       e2[-3] = (k01_21)*A[0] + (k00_20) * A[1];
02522 
02523       A += k1;
02524 
02525       k00_20 = e0[-4] - e2[-4];
02526       k01_21 = e0[-5] - e2[-5];
02527       e0[-4] += e2[-4];//e0[-4] = e0[-4] + e2[-4];
02528       e0[-5] += e2[-5];//e0[-5] = e0[-5] + e2[-5];
02529       e2[-4] = (k00_20)*A[0] - (k01_21) * A[1];
02530       e2[-5] = (k01_21)*A[0] + (k00_20) * A[1];
02531 
02532       A += k1;
02533 
02534       k00_20 = e0[-6] - e2[-6];
02535       k01_21 = e0[-7] - e2[-7];
02536       e0[-6] += e2[-6];//e0[-6] = e0[-6] + e2[-6];
02537       e0[-7] += e2[-7];//e0[-7] = e0[-7] + e2[-7];
02538       e2[-6] = (k00_20)*A[0] - (k01_21) * A[1];
02539       e2[-7] = (k01_21)*A[0] + (k00_20) * A[1];
02540 
02541       e0 -= 8;
02542       e2 -= 8;
02543 
02544       A += k1;
02545    }
02546 }
02547 
02548 static void imdct_step3_inner_s_loop(int n, float *e, int i_off, int k_off, float *A, int a_off, int k0)
02549 {
02550    int i;
02551    float A0 = A[0];
02552    float A1 = A[0+1];
02553    float A2 = A[0+a_off];
02554    float A3 = A[0+a_off+1];
02555    float A4 = A[0+a_off*2+0];
02556    float A5 = A[0+a_off*2+1];
02557    float A6 = A[0+a_off*3+0];
02558    float A7 = A[0+a_off*3+1];
02559 
02560    float k00,k11;
02561 
02562    float *ee0 = e  +i_off;
02563    float *ee2 = ee0+k_off;
02564 
02565    for (i=n; i > 0; --i) {
02566       k00     = ee0[ 0] - ee2[ 0];
02567       k11     = ee0[-1] - ee2[-1];
02568       ee0[ 0] =  ee0[ 0] + ee2[ 0];
02569       ee0[-1] =  ee0[-1] + ee2[-1];
02570       ee2[ 0] = (k00) * A0 - (k11) * A1;
02571       ee2[-1] = (k11) * A0 + (k00) * A1;
02572 
02573       k00     = ee0[-2] - ee2[-2];
02574       k11     = ee0[-3] - ee2[-3];
02575       ee0[-2] =  ee0[-2] + ee2[-2];
02576       ee0[-3] =  ee0[-3] + ee2[-3];
02577       ee2[-2] = (k00) * A2 - (k11) * A3;
02578       ee2[-3] = (k11) * A2 + (k00) * A3;
02579 
02580       k00     = ee0[-4] - ee2[-4];
02581       k11     = ee0[-5] - ee2[-5];
02582       ee0[-4] =  ee0[-4] + ee2[-4];
02583       ee0[-5] =  ee0[-5] + ee2[-5];
02584       ee2[-4] = (k00) * A4 - (k11) * A5;
02585       ee2[-5] = (k11) * A4 + (k00) * A5;
02586 
02587       k00     = ee0[-6] - ee2[-6];
02588       k11     = ee0[-7] - ee2[-7];
02589       ee0[-6] =  ee0[-6] + ee2[-6];
02590       ee0[-7] =  ee0[-7] + ee2[-7];
02591       ee2[-6] = (k00) * A6 - (k11) * A7;
02592       ee2[-7] = (k11) * A6 + (k00) * A7;
02593 
02594       ee0 -= k0;
02595       ee2 -= k0;
02596    }
02597 }
02598 
02599 static __forceinline void iter_54(float *z)
02600 {
02601    float k00,k11,k22,k33;
02602    float y0,y1,y2,y3;
02603 
02604    k00  = z[ 0] - z[-4];
02605    y0   = z[ 0] + z[-4];
02606    y2   = z[-2] + z[-6];
02607    k22  = z[-2] - z[-6];
02608 
02609    z[-0] = y0 + y2;      // z0 + z4 + z2 + z6
02610    z[-2] = y0 - y2;      // z0 + z4 - z2 - z6
02611 
02612    // done with y0,y2
02613 
02614    k33  = z[-3] - z[-7];
02615 
02616    z[-4] = k00 + k33;    // z0 - z4 + z3 - z7
02617    z[-6] = k00 - k33;    // z0 - z4 - z3 + z7
02618 
02619    // done with k33
02620 
02621    k11  = z[-1] - z[-5];
02622    y1   = z[-1] + z[-5];
02623    y3   = z[-3] + z[-7];
02624 
02625    z[-1] = y1 + y3;      // z1 + z5 + z3 + z7
02626    z[-3] = y1 - y3;      // z1 + z5 - z3 - z7
02627    z[-5] = k11 - k22;    // z1 - z5 + z2 - z6
02628    z[-7] = k11 + k22;    // z1 - z5 - z2 + z6
02629 }
02630 
02631 static void imdct_step3_inner_s_loop_ld654(int n, float *e, int i_off, float *A, int base_n)
02632 {
02633    int a_off = base_n >> 3;
02634    float A2 = A[0+a_off];
02635    float *z = e + i_off;
02636    float *base = z - 16 * n;
02637 
02638    while (z > base) {
02639       float k00,k11;
02640 
02641       k00   = z[-0] - z[-8];
02642       k11   = z[-1] - z[-9];
02643       z[-0] = z[-0] + z[-8];
02644       z[-1] = z[-1] + z[-9];
02645       z[-8] =  k00;
02646       z[-9] =  k11 ;
02647 
02648       k00    = z[ -2] - z[-10];
02649       k11    = z[ -3] - z[-11];
02650       z[ -2] = z[ -2] + z[-10];
02651       z[ -3] = z[ -3] + z[-11];
02652       z[-10] = (k00+k11) * A2;
02653       z[-11] = (k11-k00) * A2;
02654 
02655       k00    = z[-12] - z[ -4];  // reverse to avoid a unary negation
02656       k11    = z[ -5] - z[-13];
02657       z[ -4] = z[ -4] + z[-12];
02658       z[ -5] = z[ -5] + z[-13];
02659       z[-12] = k11;
02660       z[-13] = k00;
02661 
02662       k00    = z[-14] - z[ -6];  // reverse to avoid a unary negation
02663       k11    = z[ -7] - z[-15];
02664       z[ -6] = z[ -6] + z[-14];
02665       z[ -7] = z[ -7] + z[-15];
02666       z[-14] = (k00+k11) * A2;
02667       z[-15] = (k00-k11) * A2;
02668 
02669       iter_54(z);
02670       iter_54(z-8);
02671       z -= 16;
02672    }
02673 }
02674 
02675 static void inverse_mdct(float *buffer, int n, vorb *f, int blocktype)
02676 {
02677    int n2 = n >> 1, n4 = n >> 2, n8 = n >> 3, l;
02678    int ld;
02679    // @OPTIMIZE: reduce register pressure by using fewer variables?
02680    int save_point = temp_alloc_save(f);
02681    float *buf2 = (float *) temp_alloc(f, n2 * sizeof(*buf2));
02682    float *u=NULL,*v=NULL;
02683    // twiddle factors
02684    float *A = f->A[blocktype];
02685 
02686    // IMDCT algorithm from "The use of multirate filter banks for coding of high quality digital audio"
02687    // See notes about bugs in that paper in less-optimal implementation 'inverse_mdct_old' after this function.
02688 
02689    // kernel from paper
02690 
02691 
02692    // merged:
02693    //   copy and reflect spectral data
02694    //   step 0
02695 
02696    // note that it turns out that the items added together during
02697    // this step are, in fact, being added to themselves (as reflected
02698    // by step 0). inexplicable inefficiency! this became obvious
02699    // once I combined the passes.
02700 
02701    // so there's a missing 'times 2' here (for adding X to itself).
02702    // this propagates through linearly to the end, where the numbers
02703    // are 1/2 too small, and need to be compensated for.
02704 
02705    {
02706       float *d,*e, *AA, *e_stop;
02707       d = &buf2[n2-2];
02708       AA = A;
02709       e = &buffer[0];
02710       e_stop = &buffer[n2];
02711       while (e != e_stop) {
02712          d[1] = (e[0] * AA[0] - e[2]*AA[1]);
02713          d[0] = (e[0] * AA[1] + e[2]*AA[0]);
02714          d -= 2;
02715          AA += 2;
02716          e += 4;
02717       }
02718 
02719       e = &buffer[n2-3];
02720       while (d >= buf2) {
02721          d[1] = (-e[2] * AA[0] - -e[0]*AA[1]);
02722          d[0] = (-e[2] * AA[1] + -e[0]*AA[0]);
02723          d -= 2;
02724          AA += 2;
02725          e -= 4;
02726       }
02727    }
02728 
02729    // now we use symbolic names for these, so that we can
02730    // possibly swap their meaning as we change which operations
02731    // are in place
02732 
02733    u = buffer;
02734    v = buf2;
02735 
02736    // step 2    (paper output is w, now u)
02737    // this could be in place, but the data ends up in the wrong
02738    // place... _somebody_'s got to swap it, so this is nominated
02739    {
02740       float *AA = &A[n2-8];
02741       float *d0,*d1, *e0, *e1;
02742 
02743       e0 = &v[n4];
02744       e1 = &v[0];
02745 
02746       d0 = &u[n4];
02747       d1 = &u[0];
02748 
02749       while (AA >= A) {
02750          float v40_20, v41_21;
02751 
02752          v41_21 = e0[1] - e1[1];
02753          v40_20 = e0[0] - e1[0];
02754          d0[1]  = e0[1] + e1[1];
02755          d0[0]  = e0[0] + e1[0];
02756          d1[1]  = v41_21*AA[4] - v40_20*AA[5];
02757          d1[0]  = v40_20*AA[4] + v41_21*AA[5];
02758 
02759          v41_21 = e0[3] - e1[3];
02760          v40_20 = e0[2] - e1[2];
02761          d0[3]  = e0[3] + e1[3];
02762          d0[2]  = e0[2] + e1[2];
02763          d1[3]  = v41_21*AA[0] - v40_20*AA[1];
02764          d1[2]  = v40_20*AA[0] + v41_21*AA[1];
02765 
02766          AA -= 8;
02767 
02768          d0 += 4;
02769          d1 += 4;
02770          e0 += 4;
02771          e1 += 4;
02772       }
02773    }
02774 
02775    // step 3
02776    ld = ilog(n) - 1; // ilog is off-by-one from normal definitions
02777 
02778    // optimized step 3:
02779 
02780    // the original step3 loop can be nested r inside s or s inside r;
02781    // it's written originally as s inside r, but this is dumb when r
02782    // iterates many times, and s few. So I have two copies of it and
02783    // switch between them halfway.
02784 
02785    // this is iteration 0 of step 3
02786    imdct_step3_iter0_loop(n >> 4, u, n2-1-n4*0, -(n >> 3), A);
02787    imdct_step3_iter0_loop(n >> 4, u, n2-1-n4*1, -(n >> 3), A);
02788 
02789    // this is iteration 1 of step 3
02790    imdct_step3_inner_r_loop(n >> 5, u, n2-1 - n8*0, -(n >> 4), A, 16);
02791    imdct_step3_inner_r_loop(n >> 5, u, n2-1 - n8*1, -(n >> 4), A, 16);
02792    imdct_step3_inner_r_loop(n >> 5, u, n2-1 - n8*2, -(n >> 4), A, 16);
02793    imdct_step3_inner_r_loop(n >> 5, u, n2-1 - n8*3, -(n >> 4), A, 16);
02794 
02795    l=2;
02796    for (; l < (ld-3)>>1; ++l) {
02797       int k0 = n >> (l+2), k0_2 = k0>>1;
02798       int lim = 1 << (l+1);
02799       int i;
02800       for (i=0; i < lim; ++i)
02801          imdct_step3_inner_r_loop(n >> (l+4), u, n2-1 - k0*i, -k0_2, A, 1 << (l+3));
02802    }
02803 
02804    for (; l < ld-6; ++l) {
02805       int k0 = n >> (l+2), k1 = 1 << (l+3), k0_2 = k0>>1;
02806       int rlim = n >> (l+6), r;
02807       int lim = 1 << (l+1);
02808       int i_off;
02809       float *A0 = A;
02810       i_off = n2-1;
02811       for (r=rlim; r > 0; --r) {
02812          imdct_step3_inner_s_loop(lim, u, i_off, -k0_2, A0, k1, k0);
02813          A0 += k1*4;
02814          i_off -= 8;
02815       }
02816    }
02817 
02818    // iterations with count:
02819    //   ld-6,-5,-4 all interleaved together
02820    //       the big win comes from getting rid of needless flops
02821    //         due to the constants on pass 5 & 4 being all 1 and 0;
02822    //       combining them to be simultaneous to improve cache made little difference
02823    imdct_step3_inner_s_loop_ld654(n >> 5, u, n2-1, A, n);
02824 
02825    // output is u
02826 
02827    // step 4, 5, and 6
02828    // cannot be in-place because of step 5
02829    {
02830       uint16 *bitrev = f->bit_reverse[blocktype];
02831       // weirdly, I'd have thought reading sequentially and writing
02832       // erratically would have been better than vice-versa, but in
02833       // fact that's not what my testing showed. (That is, with
02834       // j = bitreverse(i), do you read i and write j, or read j and write i.)
02835 
02836       float *d0 = &v[n4-4];
02837       float *d1 = &v[n2-4];
02838       while (d0 >= v) {
02839          int k4;
02840 
02841          k4 = bitrev[0];
02842          d1[3] = u[k4+0];
02843          d1[2] = u[k4+1];
02844          d0[3] = u[k4+2];
02845          d0[2] = u[k4+3];
02846 
02847          k4 = bitrev[1];
02848          d1[1] = u[k4+0];
02849          d1[0] = u[k4+1];
02850          d0[1] = u[k4+2];
02851          d0[0] = u[k4+3];
02852 
02853          d0 -= 4;
02854          d1 -= 4;
02855          bitrev += 2;
02856       }
02857    }
02858    // (paper output is u, now v)
02859 
02860 
02861    // data must be in buf2
02862    assert(v == buf2);
02863 
02864    // step 7   (paper output is v, now v)
02865    // this is now in place
02866    {
02867       float *C = f->C[blocktype];
02868       float *d, *e;
02869 
02870       d = v;
02871       e = v + n2 - 4;
02872 
02873       while (d < e) {
02874          float a02,a11,b0,b1,b2,b3;
02875 
02876          a02 = d[0] - e[2];
02877          a11 = d[1] + e[3];
02878 
02879          b0 = C[1]*a02 + C[0]*a11;
02880          b1 = C[1]*a11 - C[0]*a02;
02881 
02882          b2 = d[0] + e[ 2];
02883          b3 = d[1] - e[ 3];
02884 
02885          d[0] = b2 + b0;
02886          d[1] = b3 + b1;
02887          e[2] = b2 - b0;
02888          e[3] = b1 - b3;
02889 
02890          a02 = d[2] - e[0];
02891          a11 = d[3] + e[1];
02892 
02893          b0 = C[3]*a02 + C[2]*a11;
02894          b1 = C[3]*a11 - C[2]*a02;
02895 
02896          b2 = d[2] + e[ 0];
02897          b3 = d[3] - e[ 1];
02898 
02899          d[2] = b2 + b0;
02900          d[3] = b3 + b1;
02901          e[0] = b2 - b0;
02902          e[1] = b1 - b3;
02903 
02904          C += 4;
02905          d += 4;
02906          e -= 4;
02907       }
02908    }
02909 
02910    // data must be in buf2
02911 
02912 
02913    // step 8+decode   (paper output is X, now buffer)
02914    // this generates pairs of data a la 8 and pushes them directly through
02915    // the decode kernel (pushing rather than pulling) to avoid having
02916    // to make another pass later
02917 
02918    // this cannot POSSIBLY be in place, so we refer to the buffers directly
02919 
02920    {
02921       float *d0,*d1,*d2,*d3;
02922 
02923       float *B = f->B[blocktype] + n2 - 8;
02924       float *e = buf2 + n2 - 8;
02925       d0 = &buffer[0];
02926       d1 = &buffer[n2-4];
02927       d2 = &buffer[n2];
02928       d3 = &buffer[n-4];
02929       while (e >= v) {
02930          float p0,p1,p2,p3;
02931 
02932          p3 =  e[6]*B[7] - e[7]*B[6];
02933          p2 = -e[6]*B[6] - e[7]*B[7];
02934 
02935          d0[0] =   p3;
02936          d1[3] = - p3;
02937          d2[0] =   p2;
02938          d3[3] =   p2;
02939 
02940          p1 =  e[4]*B[5] - e[5]*B[4];
02941          p0 = -e[4]*B[4] - e[5]*B[5];
02942 
02943          d0[1] =   p1;
02944          d1[2] = - p1;
02945          d2[1] =   p0;
02946          d3[2] =   p0;
02947 
02948          p3 =  e[2]*B[3] - e[3]*B[2];
02949          p2 = -e[2]*B[2] - e[3]*B[3];
02950 
02951          d0[2] =   p3;
02952          d1[1] = - p3;
02953          d2[2] =   p2;
02954          d3[1] =   p2;
02955 
02956          p1 =  e[0]*B[1] - e[1]*B[0];
02957          p0 = -e[0]*B[0] - e[1]*B[1];
02958 
02959          d0[3] =   p1;
02960          d1[0] = - p1;
02961          d2[3] =   p0;
02962          d3[0] =   p0;
02963 
02964          B -= 8;
02965          e -= 8;
02966          d0 += 4;
02967          d2 += 4;
02968          d1 -= 4;
02969          d3 -= 4;
02970       }
02971    }
02972 
02973    // temp_free(f,buf2);
02974    temp_alloc_restore(f,save_point);
02975 }
02976 
02977 #if 0
02978 // this is the original version of the above code, if you want to optimize it from scratch
02979 void inverse_mdct_naive(float *buffer, int n)
02980 {
02981    float s;
02982    float A[1 << 12], B[1 << 12], C[1 << 11];
02983    int i,k,k2,k4, n2 = n >> 1, n4 = n >> 2, n8 = n >> 3, l;
02984    int n3_4 = n - n4, ld;
02985    // how can they claim this only uses N words?!
02986    // oh, because they're only used sparsely, whoops
02987    float u[1 << 13], X[1 << 13], v[1 << 13], w[1 << 13];
02988    // set up twiddle factors
02989 
02990    for (k=k2=0; k < n4; ++k,k2+=2) {
02991       A[k2  ] = (float)  cos(4*k*M_PI/n);
02992       A[k2+1] = (float) -sin(4*k*M_PI/n);
02993       B[k2  ] = (float)  cos((k2+1)*M_PI/n/2);
02994       B[k2+1] = (float)  sin((k2+1)*M_PI/n/2);
02995    }
02996    for (k=k2=0; k < n8; ++k,k2+=2) {
02997       C[k2  ] = (float)  cos(2*(k2+1)*M_PI/n);
02998       C[k2+1] = (float) -sin(2*(k2+1)*M_PI/n);
02999    }
03000 
03001    // IMDCT algorithm from "The use of multirate filter banks for coding of high quality digital audio"
03002    // Note there are bugs in that pseudocode, presumably due to them attempting
03003    // to rename the arrays nicely rather than representing the way their actual
03004    // implementation bounces buffers back and forth. As a result, even in the
03005    // "some formulars corrected" version, a direct implementation fails. These
03006    // are noted below as "paper bug".
03007 
03008    // copy and reflect spectral data
03009    for (k=0; k < n2; ++k) u[k] = buffer[k];
03010    for (   ; k < n ; ++k) u[k] = -buffer[n - k - 1];
03011    // kernel from paper
03012    // step 1
03013    for (k=k2=k4=0; k < n4; k+=1, k2+=2, k4+=4) {
03014       v[n-k4-1] = (u[k4] - u[n-k4-1]) * A[k2]   - (u[k4+2] - u[n-k4-3])*A[k2+1];
03015       v[n-k4-3] = (u[k4] - u[n-k4-1]) * A[k2+1] + (u[k4+2] - u[n-k4-3])*A[k2];
03016    }
03017    // step 2
03018    for (k=k4=0; k < n8; k+=1, k4+=4) {
03019       w[n2+3+k4] = v[n2+3+k4] + v[k4+3];
03020       w[n2+1+k4] = v[n2+1+k4] + v[k4+1];
03021       w[k4+3]    = (v[n2+3+k4] - v[k4+3])*A[n2-4-k4] - (v[n2+1+k4]-v[k4+1])*A[n2-3-k4];
03022       w[k4+1]    = (v[n2+1+k4] - v[k4+1])*A[n2-4-k4] + (v[n2+3+k4]-v[k4+3])*A[n2-3-k4];
03023    }
03024    // step 3
03025    ld = ilog(n) - 1; // ilog is off-by-one from normal definitions
03026    for (l=0; l < ld-3; ++l) {
03027       int k0 = n >> (l+2), k1 = 1 << (l+3);
03028       int rlim = n >> (l+4), r4, r;
03029       int s2lim = 1 << (l+2), s2;
03030       for (r=r4=0; r < rlim; r4+=4,++r) {
03031          for (s2=0; s2 < s2lim; s2+=2) {
03032             u[n-1-k0*s2-r4] = w[n-1-k0*s2-r4] + w[n-1-k0*(s2+1)-r4];
03033             u[n-3-k0*s2-r4] = w[n-3-k0*s2-r4] + w[n-3-k0*(s2+1)-r4];
03034             u[n-1-k0*(s2+1)-r4] = (w[n-1-k0*s2-r4] - w[n-1-k0*(s2+1)-r4]) * A[r*k1]
03035                                 - (w[n-3-k0*s2-r4] - w[n-3-k0*(s2+1)-r4]) * A[r*k1+1];
03036             u[n-3-k0*(s2+1)-r4] = (w[n-3-k0*s2-r4] - w[n-3-k0*(s2+1)-r4]) * A[r*k1]
03037                                 + (w[n-1-k0*s2-r4] - w[n-1-k0*(s2+1)-r4]) * A[r*k1+1];
03038          }
03039       }
03040       if (l+1 < ld-3) {
03041          // paper bug: ping-ponging of u&w here is omitted
03042          memcpy(w, u, sizeof(u));
03043       }
03044    }
03045 
03046    // step 4
03047    for (i=0; i < n8; ++i) {
03048       int j = bit_reverse(i) >> (32-ld+3);
03049       assert(j < n8);
03050       if (i == j) {
03051          // paper bug: original code probably swapped in place; if copying,
03052          //            need to directly copy in this case
03053          int i8 = i << 3;
03054          v[i8+1] = u[i8+1];
03055          v[i8+3] = u[i8+3];
03056          v[i8+5] = u[i8+5];
03057          v[i8+7] = u[i8+7];
03058       } else if (i < j) {
03059          int i8 = i << 3, j8 = j << 3;
03060          v[j8+1] = u[i8+1], v[i8+1] = u[j8 + 1];
03061          v[j8+3] = u[i8+3], v[i8+3] = u[j8 + 3];
03062          v[j8+5] = u[i8+5], v[i8+5] = u[j8 + 5];
03063          v[j8+7] = u[i8+7], v[i8+7] = u[j8 + 7];
03064       }
03065    }
03066    // step 5
03067    for (k=0; k < n2; ++k) {
03068       w[k] = v[k*2+1];
03069    }
03070    // step 6
03071    for (k=k2=k4=0; k < n8; ++k, k2 += 2, k4 += 4) {
03072       u[n-1-k2] = w[k4];
03073       u[n-2-k2] = w[k4+1];
03074       u[n3_4 - 1 - k2] = w[k4+2];
03075       u[n3_4 - 2 - k2] = w[k4+3];
03076    }
03077    // step 7
03078    for (k=k2=0; k < n8; ++k, k2 += 2) {
03079       v[n2 + k2 ] = ( u[n2 + k2] + u[n-2-k2] + C[k2+1]*(u[n2+k2]-u[n-2-k2]) + C[k2]*(u[n2+k2+1]+u[n-2-k2+1]))/2;
03080       v[n-2 - k2] = ( u[n2 + k2] + u[n-2-k2] - C[k2+1]*(u[n2+k2]-u[n-2-k2]) - C[k2]*(u[n2+k2+1]+u[n-2-k2+1]))/2;
03081       v[n2+1+ k2] = ( u[n2+1+k2] - u[n-1-k2] + C[k2+1]*(u[n2+1+k2]+u[n-1-k2]) - C[k2]*(u[n2+k2]-u[n-2-k2]))/2;
03082       v[n-1 - k2] = (-u[n2+1+k2] + u[n-1-k2] + C[k2+1]*(u[n2+1+k2]+u[n-1-k2]) - C[k2]*(u[n2+k2]-u[n-2-k2]))/2;
03083    }
03084    // step 8
03085    for (k=k2=0; k < n4; ++k,k2 += 2) {
03086       X[k]      = v[k2+n2]*B[k2  ] + v[k2+1+n2]*B[k2+1];
03087       X[n2-1-k] = v[k2+n2]*B[k2+1] - v[k2+1+n2]*B[k2  ];
03088    }
03089 
03090    // decode kernel to output
03091    // determined the following value experimentally
03092    // (by first figuring out what made inverse_mdct_slow work); then matching that here
03093    // (probably vorbis encoder premultiplies by n or n/2, to save it on the decoder?)
03094    s = 0.5; // theoretically would be n4
03095 
03096    // [[[ note! the s value of 0.5 is compensated for by the B[] in the current code,
03097    //     so it needs to use the "old" B values to behave correctly, or else
03098    //     set s to 1.0 ]]]
03099    for (i=0; i < n4  ; ++i) buffer[i] = s * X[i+n4];
03100    for (   ; i < n3_4; ++i) buffer[i] = -s * X[n3_4 - i - 1];
03101    for (   ; i < n   ; ++i) buffer[i] = -s * X[i - n3_4];
03102 }
03103 #endif
03104 
03105 static float *get_window(vorb *f, int len)
03106 {
03107    len <<= 1;
03108    if (len == f->blocksize_0) return f->window[0];
03109    if (len == f->blocksize_1) return f->window[1];
03110    return NULL;
03111 }
03112 
03113 #ifndef STB_VORBIS_NO_DEFER_FLOOR
03114 typedef int16 YTYPE;
03115 #else
03116 typedef int YTYPE;
03117 #endif
03118 static int do_floor(vorb *f, Mapping *map, int i, int n, float *target, YTYPE *finalY, uint8 *step2_flag)
03119 {
03120    (void)step2_flag; 
03121    int n2 = n >> 1;
03122    int s = map->chan[i].mux, floor;
03123    floor = map->submap_floor[s];
03124    if (f->floor_types[floor] == 0) {
03125       return error(f, VORBIS_invalid_stream);
03126    } else {
03127       Floor1 *g = &f->floor_config[floor].floor1;
03128       int j,q;
03129       int lx = 0, ly = finalY[0] * g->floor1_multiplier;
03130       for (q=1; q < g->values; ++q) {
03131          j = g->sorted_order[q];
03132          #ifndef STB_VORBIS_NO_DEFER_FLOOR
03133          if (finalY[j] >= 0)
03134          #else
03135          if (step2_flag[j])
03136          #endif
03137          {
03138             int hy = finalY[j] * g->floor1_multiplier;
03139             int hx = g->Xlist[j];
03140             if (lx != hx)
03141                draw_line(target, lx,ly, hx,hy, n2);
03142             CHECK(f);
03143             lx = hx, ly = hy;
03144          }
03145       }
03146       if (lx < n2) {
03147          // optimization of: draw_line(target, lx,ly, n,ly, n2);
03148          for (j=lx; j < n2; ++j)
03149             LINE_OP(target[j], inverse_db_table[ly]);
03150          CHECK(f);
03151       }
03152    }
03153    return TRUE;
03154 }
03155 
03156 // The meaning of "left" and "right"
03157 //
03158 // For a given frame:
03159 //     we compute samples from 0..n
03160 //     window_center is n/2
03161 //     we'll window and mix the samples from left_start to left_end with data from the previous frame
03162 //     all of the samples from left_end to right_start can be output without mixing; however,
03163 //        this interval is 0-length except when transitioning between short and long frames
03164 //     all of the samples from right_start to right_end need to be mixed with the next frame,
03165 //        which we don't have, so those get saved in a buffer
03166 //     frame N's right_end-right_start, the number of samples to mix with the next frame,
03167 //        has to be the same as frame N+1's left_end-left_start (which they are by
03168 //        construction)
03169 
03170 static int vorbis_decode_initial(vorb *f, int *p_left_start, int *p_left_end, int *p_right_start, int *p_right_end, int *mode)
03171 {
03172    Mode *m;
03173    int i, n, prev, next, window_center;
03174    f->channel_buffer_start = f->channel_buffer_end = 0;
03175 
03176   retry:
03177    if (f->eof) return FALSE;
03178    if (!maybe_start_packet(f))
03179       return FALSE;
03180    // check packet type
03181    if (get_bits(f,1) != 0) {
03182       if (IS_PUSH_MODE(f))
03183          return error(f,VORBIS_bad_packet_type);
03184       while (EOP != get8_packet(f));
03185       goto retry;
03186    }
03187 
03188    if (f->alloc.alloc_buffer)
03189       assert(f->alloc.alloc_buffer_length_in_bytes == f->temp_offset);
03190 
03191    i = get_bits(f, ilog(f->mode_count-1));
03192    if (i == EOP) return FALSE;
03193    if (i >= f->mode_count) return FALSE;
03194    *mode = i;
03195    m = f->mode_config + i;
03196    if (m->blockflag) {
03197       n = f->blocksize_1;
03198       prev = get_bits(f,1);
03199       next = get_bits(f,1);
03200    } else {
03201       prev = next = 0;
03202       n = f->blocksize_0;
03203    }
03204 
03205 // WINDOWING
03206 
03207    window_center = n >> 1;
03208    if (m->blockflag && !prev) {
03209       *p_left_start = (n - f->blocksize_0) >> 2;
03210       *p_left_end   = (n + f->blocksize_0) >> 2;
03211    } else {
03212       *p_left_start = 0;
03213       *p_left_end   = window_center;
03214    }
03215    if (m->blockflag && !next) {
03216       *p_right_start = (n*3 - f->blocksize_0) >> 2;
03217       *p_right_end   = (n*3 + f->blocksize_0) >> 2;
03218    } else {
03219       *p_right_start = window_center;
03220       *p_right_end   = n;
03221    }
03222 
03223    return TRUE;
03224 }
03225 
03226 static int vorbis_decode_packet_rest(vorb *f, int *len, Mode *m, int left_start, int left_end, int right_start, int right_end, int *p_left)
03227 {
03228    (void)left_end;
03229    Mapping *map;
03230    int i,j,k,n,n2;
03231    int zero_channel[256];
03232    int really_zero_channel[256];
03233 
03234 // WINDOWING
03235 
03236    n = f->blocksize[m->blockflag];
03237    map = &f->mapping[m->mapping];
03238 
03239 // FLOORS
03240    n2 = n >> 1;
03241 
03242    CHECK(f);
03243 
03244    for (i=0; i < f->channels; ++i) {
03245       int s = map->chan[i].mux, floor;
03246       zero_channel[i] = FALSE;
03247       floor = map->submap_floor[s];
03248       if (f->floor_types[floor] == 0) {
03249          return error(f, VORBIS_invalid_stream);
03250       } else {
03251          Floor1 *g = &f->floor_config[floor].floor1;
03252          if (get_bits(f, 1)) {
03253             short *finalY;
03254             uint8 step2_flag[256];
03255             static int range_list[4] = { 256, 128, 86, 64 };
03256             int range = range_list[g->floor1_multiplier-1];
03257             int offset = 2;
03258             finalY = f->finalY[i];
03259             finalY[0] = get_bits(f, ilog(range)-1);
03260             finalY[1] = get_bits(f, ilog(range)-1);
03261             for (j=0; j < g->partitions; ++j) {
03262                int pclass = g->partition_class_list[j];
03263                int cdim = g->class_dimensions[pclass];
03264                int cbits = g->class_subclasses[pclass];
03265                int csub = (1 << cbits)-1;
03266                int cval = 0;
03267                if (cbits) {
03268                   Codebook *c = f->codebooks + g->class_masterbooks[pclass];
03269                   DECODE(cval,f,c);
03270                }
03271                for (k=0; k < cdim; ++k) {
03272                   int book = g->subclass_books[pclass][cval & csub];
03273                   cval = cval >> cbits;
03274                   if (book >= 0) {
03275                      int temp;
03276                      Codebook *c = f->codebooks + book;
03277                      DECODE(temp,f,c);
03278                      finalY[offset++] = temp;
03279                   } else
03280                      finalY[offset++] = 0;
03281                }
03282             }
03283             if (f->valid_bits == INVALID_BITS) goto error; // behavior according to spec
03284             step2_flag[0] = step2_flag[1] = 1;
03285             for (j=2; j < g->values; ++j) {
03286                int low, high, pred, highroom, lowroom, room, val;
03287                low = g->neighbors[j][0];
03288                high = g->neighbors[j][1];
03289                //neighbors(g->Xlist, j, &low, &high);
03290                pred = predict_point(g->Xlist[j], g->Xlist[low], g->Xlist[high], finalY[low], finalY[high]);
03291                val = finalY[j];
03292                highroom = range - pred;
03293                lowroom = pred;
03294                if (highroom < lowroom)
03295                   room = highroom * 2;
03296                else
03297                   room = lowroom * 2;
03298                if (val) {
03299                   step2_flag[low] = step2_flag[high] = 1;
03300                   step2_flag[j] = 1;
03301                   if (val >= room) {
03302                      if (highroom <= lowroom)
03303                         finalY[j] = pred - val + highroom - 1;
03304                   }
03305                   else
03306                      if (val & 1)
03307                         finalY[j] = pred - ((val+1)>>1);
03308                      else
03309                         finalY[j] = pred + (val>>1);
03310                } else {
03311                   step2_flag[j] = 0;
03312                   finalY[j] = pred;
03313                }
03314             }
03315 
03316 #ifdef STB_VORBIS_NO_DEFER_FLOOR
03317             do_floor(f, map, i, n, f->floor_buffers[i], finalY, step2_flag);
03318 #else
03319             // defer final floor computation until _after_ residue
03320             for (j=0; j < g->values; ++j) {
03321                if (!step2_flag[j])
03322                   finalY[j] = -1;
03323             }
03324 #endif
03325          } else {
03326            error:
03327             zero_channel[i] = TRUE;
03328          }
03329          // So we just defer everything else to later
03330 
03331          // at this point we've decoded the floor into buffer
03332       }
03333    }
03334    CHECK(f);
03335    // at this point we've decoded all floors
03336 
03337    if (f->alloc.alloc_buffer)
03338       assert(f->alloc.alloc_buffer_length_in_bytes == f->temp_offset);
03339 
03340    // re-enable coupled channels if necessary
03341    memcpy(really_zero_channel, zero_channel, sizeof(really_zero_channel[0]) * f->channels);
03342    for (i=0; i < map->coupling_steps; ++i)
03343       if (!zero_channel[map->chan[i].magnitude] || !zero_channel[map->chan[i].angle]) {
03344          zero_channel[map->chan[i].magnitude] = zero_channel[map->chan[i].angle] = FALSE;
03345       }
03346 
03347    CHECK(f);
03348 // RESIDUE DECODE
03349    for (i=0; i < map->submaps; ++i) {
03350       float *residue_buffers[STB_VORBIS_MAX_CHANNELS];
03351       int r;
03352       uint8 do_not_decode[256];
03353       int ch = 0;
03354       for (j=0; j < f->channels; ++j) {
03355          if (map->chan[j].mux == i) {
03356             if (zero_channel[j]) {
03357                do_not_decode[ch] = TRUE;
03358                residue_buffers[ch] = NULL;
03359             } else {
03360                do_not_decode[ch] = FALSE;
03361                residue_buffers[ch] = f->channel_buffers[j];
03362             }
03363             ++ch;
03364          }
03365       }
03366       r = map->submap_residue[i];
03367       decode_residue(f, residue_buffers, ch, n2, r, do_not_decode);
03368    }
03369 
03370    if (f->alloc.alloc_buffer)
03371       assert(f->alloc.alloc_buffer_length_in_bytes == f->temp_offset);
03372    CHECK(f);
03373 
03374 // INVERSE COUPLING
03375    for (i = map->coupling_steps-1; i >= 0; --i) {
03376       int n2 = n >> 1;
03377       float *m = f->channel_buffers[map->chan[i].magnitude];
03378       float *a = f->channel_buffers[map->chan[i].angle    ];
03379       for (j=0; j < n2; ++j) {
03380          float a2,m2;
03381          if (m[j] > 0)
03382             if (a[j] > 0)
03383                m2 = m[j], a2 = m[j] - a[j];
03384             else
03385                a2 = m[j], m2 = m[j] + a[j];
03386          else
03387             if (a[j] > 0)
03388                m2 = m[j], a2 = m[j] + a[j];
03389             else
03390                a2 = m[j], m2 = m[j] - a[j];
03391          m[j] = m2;
03392          a[j] = a2;
03393       }
03394    }
03395    CHECK(f);
03396 
03397    // finish decoding the floors
03398 #ifndef STB_VORBIS_NO_DEFER_FLOOR
03399    for (i=0; i < f->channels; ++i) {
03400       if (really_zero_channel[i]) {
03401          memset(f->channel_buffers[i], 0, sizeof(*f->channel_buffers[i]) * n2);
03402       } else {
03403          do_floor(f, map, i, n, f->channel_buffers[i], f->finalY[i], NULL);
03404       }
03405    }
03406 #else
03407    for (i=0; i < f->channels; ++i) {
03408       if (really_zero_channel[i]) {
03409          memset(f->channel_buffers[i], 0, sizeof(*f->channel_buffers[i]) * n2);
03410       } else {
03411          for (j=0; j < n2; ++j)
03412             f->channel_buffers[i][j] *= f->floor_buffers[i][j];
03413       }
03414    }
03415 #endif
03416 
03417 // INVERSE MDCT
03418    CHECK(f);
03419    for (i=0; i < f->channels; ++i)
03420       inverse_mdct(f->channel_buffers[i], n, f, m->blockflag);
03421    CHECK(f);
03422 
03423    // this shouldn't be necessary, unless we exited on an error
03424    // and want to flush to get to the next packet
03425    flush_packet(f);
03426 
03427    if (f->first_decode) {
03428       // assume we start so first non-discarded sample is sample 0
03429       // this isn't to spec, but spec would require us to read ahead
03430       // and decode the size of all current frames--could be done,
03431       // but presumably it's not a commonly used feature
03432       f->current_loc = -n2; // start of first frame is positioned for discard
03433       // we might have to discard samples "from" the next frame too,
03434       // if we're lapping a large block then a small at the start?
03435       f->discard_samples_deferred = n - right_end;
03436       f->current_loc_valid = TRUE;
03437       f->first_decode = FALSE;
03438    } else if (f->discard_samples_deferred) {
03439       if (f->discard_samples_deferred >= right_start - left_start) {
03440          f->discard_samples_deferred -= (right_start - left_start);
03441          left_start = right_start;
03442          *p_left = left_start;
03443       } else {
03444          left_start += f->discard_samples_deferred;
03445          *p_left = left_start;
03446          f->discard_samples_deferred = 0;
03447       }
03448    } else if (f->previous_length == 0 && f->current_loc_valid) {
03449       // we're recovering from a seek... that means we're going to discard
03450       // the samples from this packet even though we know our position from
03451       // the last page header, so we need to update the position based on
03452       // the discarded samples here
03453       // but wait, the code below is going to add this in itself even
03454       // on a discard, so we don't need to do it here...
03455    }
03456 
03457    // check if we have ogg information about the sample # for this packet
03458    if (f->last_seg_which == f->end_seg_with_known_loc) {
03459       // if we have a valid current loc, and this is final:
03460       if (f->current_loc_valid && (f->page_flag & PAGEFLAG_last_page)) {
03461          uint32 current_end = f->known_loc_for_packet;
03462          // then let's infer the size of the (probably) short final frame
03463          if (current_end < f->current_loc + (right_end-left_start)) {
03464             if (current_end < f->current_loc) {
03465                // negative truncation, that's impossible!
03466                *len = 0;
03467             } else {
03468                *len = current_end - f->current_loc;
03469             }
03470             *len += left_start; // this doesn't seem right, but has no ill effect on my test files
03471             if (*len > right_end) *len = right_end; // this should never happen
03472             f->current_loc += *len;
03473             return TRUE;
03474          }
03475       }
03476       // otherwise, just set our sample loc
03477       // guess that the ogg granule pos refers to the _middle_ of the
03478       // last frame?
03479       // set f->current_loc to the position of left_start
03480       f->current_loc = f->known_loc_for_packet - (n2-left_start);
03481       f->current_loc_valid = TRUE;
03482    }
03483    if (f->current_loc_valid)
03484       f->current_loc += (right_start - left_start);
03485 
03486    if (f->alloc.alloc_buffer)
03487       assert(f->alloc.alloc_buffer_length_in_bytes == f->temp_offset);
03488    *len = right_end;  // ignore samples after the window goes to 0
03489    CHECK(f);
03490 
03491    return TRUE;
03492 }
03493 
03494 static int vorbis_decode_packet(vorb *f, int *len, int *p_left, int *p_right)
03495 {
03496    int mode, left_end, right_end;
03497    if (!vorbis_decode_initial(f, p_left, &left_end, p_right, &right_end, &mode)) return 0;
03498    return vorbis_decode_packet_rest(f, len, f->mode_config + mode, *p_left, left_end, *p_right, right_end, p_left);
03499 }
03500 
03501 static int vorbis_finish_frame(stb_vorbis *f, int len, int left, int right)
03502 {
03503    int prev,i,j;
03504    // we use right&left (the start of the right- and left-window sin()-regions)
03505    // to determine how much to return, rather than inferring from the rules
03506    // (same result, clearer code); 'left' indicates where our sin() window
03507    // starts, therefore where the previous window's right edge starts, and
03508    // therefore where to start mixing from the previous buffer. 'right'
03509    // indicates where our sin() ending-window starts, therefore that's where
03510    // we start saving, and where our returned-data ends.
03511 
03512    // mixin from previous window
03513    if (f->previous_length) {
03514       int i,j, n = f->previous_length;
03515       float *w = get_window(f, n);
03516       if (w == NULL) return 0;
03517       for (i=0; i < f->channels; ++i) {
03518          for (j=0; j < n; ++j)
03519             f->channel_buffers[i][left+j] =
03520                f->channel_buffers[i][left+j]*w[    j] +
03521                f->previous_window[i][     j]*w[n-1-j];
03522       }
03523    }
03524 
03525    prev = f->previous_length;
03526 
03527    // last half of this data becomes previous window
03528    f->previous_length = len - right;
03529 
03530    // @OPTIMIZE: could avoid this copy by double-buffering the
03531    // output (flipping previous_window with channel_buffers), but
03532    // then previous_window would have to be 2x as large, and
03533    // channel_buffers couldn't be temp mem (although they're NOT
03534    // currently temp mem, they could be (unless we want to level
03535    // performance by spreading out the computation))
03536    for (i=0; i < f->channels; ++i)
03537       for (j=0; right+j < len; ++j)
03538          f->previous_window[i][j] = f->channel_buffers[i][right+j];
03539 
03540    if (!prev)
03541       // there was no previous packet, so this data isn't valid...
03542       // this isn't entirely true, only the would-have-overlapped data
03543       // isn't valid, but this seems to be what the spec requires
03544       return 0;
03545 
03546    // truncate a short frame
03547    if (len < right) right = len;
03548 
03549    f->samples_output += right-left;
03550 
03551    return right - left;
03552 }
03553 
03554 static int vorbis_pump_first_frame(stb_vorbis *f)
03555 {
03556    int len, right, left, res;
03557    res = vorbis_decode_packet(f, &len, &left, &right);
03558    if (res)
03559       vorbis_finish_frame(f, len, left, right);
03560    return res;
03561 }
03562 
03563 #ifndef STB_VORBIS_NO_PUSHDATA_API
03564 static int is_whole_packet_present(stb_vorbis *f)
03565 {
03566    // make sure that we have the packet available before continuing...
03567    // this requires a full ogg parse, but we know we can fetch from f->stream
03568 
03569    // instead of coding this out explicitly, we could save the current read state,
03570    // read the next packet with get8() until end-of-packet, check f->eof, then
03571    // reset the state? but that would be slower, esp. since we'd have over 256 bytes
03572    // of state to restore (primarily the page segment table)
03573 
03574    int s = f->next_seg, first = TRUE;
03575    uint8 *p = f->stream;
03576 
03577    if (s != -1) { // if we're not starting the packet with a 'continue on next page' flag
03578       for (; s < f->segment_count; ++s) {
03579          p += f->segments[s];
03580          if (f->segments[s] < 255)               // stop at first short segment
03581             break;
03582       }
03583       // either this continues, or it ends it...
03584       if (s == f->segment_count)
03585          s = -1; // set 'crosses page' flag
03586       if (p > f->stream_end)                     return error(f, VORBIS_need_more_data);
03587       first = FALSE;
03588    }
03589    for (; s == -1;) {
03590       uint8 *q;
03591       int n;
03592 
03593       // check that we have the page header ready
03594       if (p + 26 >= f->stream_end)               return error(f, VORBIS_need_more_data);
03595       // validate the page
03596       if (memcmp(p, ogg_page_header, 4))         return error(f, VORBIS_invalid_stream);
03597       if (p[4] != 0)                             return error(f, VORBIS_invalid_stream);
03598       if (first) { // the first segment must NOT have 'continued_packet', later ones MUST
03599          if (f->previous_length)
03600             if ((p[5] & PAGEFLAG_continued_packet))  return error(f, VORBIS_invalid_stream);
03601          // if no previous length, we're resynching, so we can come in on a continued-packet,
03602          // which we'll just drop
03603       } else {
03604          if (!(p[5] & PAGEFLAG_continued_packet)) return error(f, VORBIS_invalid_stream);
03605       }
03606       n = p[26]; // segment counts
03607       q = p+27;  // q points to segment table
03608       p = q + n; // advance past header
03609       // make sure we've read the segment table
03610       if (p > f->stream_end)                     return error(f, VORBIS_need_more_data);
03611       for (s=0; s < n; ++s) {
03612          p += q[s];
03613          if (q[s] < 255)
03614             break;
03615       }
03616       if (s == n)
03617          s = -1; // set 'crosses page' flag
03618       if (p > f->stream_end)                     return error(f, VORBIS_need_more_data);
03619       first = FALSE;
03620    }
03621    return TRUE;
03622 }
03623 #endif // !STB_VORBIS_NO_PUSHDATA_API
03624 
03625 static int start_decoder(vorb *f)
03626 {
03627    uint8 header[6], x,y;
03628    int len,i,j,k, max_submaps = 0;
03629    int longest_floorlist=0;
03630 
03631    // first page, first packet
03632    f->first_decode = TRUE;
03633 
03634    if (!start_page(f))                              return FALSE;
03635    // validate page flag
03636    if (!(f->page_flag & PAGEFLAG_first_page))       return error(f, VORBIS_invalid_first_page);
03637    if (f->page_flag & PAGEFLAG_last_page)           return error(f, VORBIS_invalid_first_page);
03638    if (f->page_flag & PAGEFLAG_continued_packet)    return error(f, VORBIS_invalid_first_page);
03639    // check for expected packet length
03640    if (f->segment_count != 1)                       return error(f, VORBIS_invalid_first_page);
03641    if (f->segments[0] != 30) {
03642       // check for the Ogg skeleton fishead identifying header to refine our error
03643       if (f->segments[0] == 64 &&
03644           getn(f, header, 6) &&
03645           header[0] == 'f' &&
03646           header[1] == 'i' &&
03647           header[2] == 's' &&
03648           header[3] == 'h' &&
03649           header[4] == 'e' &&
03650           header[5] == 'a' &&
03651           get8(f)   == 'd' &&
03652           get8(f)   == '\0')                        return error(f, VORBIS_ogg_skeleton_not_supported);
03653       else
03654                                                     return error(f, VORBIS_invalid_first_page);
03655    }
03656 
03657    // read packet
03658    // check packet header
03659    if (get8(f) != VORBIS_packet_id)                 return error(f, VORBIS_invalid_first_page);
03660    if (!getn(f, header, 6))                         return error(f, VORBIS_unexpected_eof);
03661    if (!vorbis_validate(header))                    return error(f, VORBIS_invalid_first_page);
03662    // vorbis_version
03663    if (get32(f) != 0)                               return error(f, VORBIS_invalid_first_page);
03664    f->channels = get8(f); if (!f->channels)         return error(f, VORBIS_invalid_first_page);
03665    if (f->channels > STB_VORBIS_MAX_CHANNELS)       return error(f, VORBIS_too_many_channels);
03666    f->sample_rate = get32(f); if (!f->sample_rate)  return error(f, VORBIS_invalid_first_page);
03667    get32(f); // bitrate_maximum
03668    get32(f); // bitrate_nominal
03669    get32(f); // bitrate_minimum
03670    x = get8(f);
03671    {
03672       int log0,log1;
03673       log0 = x & 15;
03674       log1 = x >> 4;
03675       f->blocksize_0 = 1 << log0;
03676       f->blocksize_1 = 1 << log1;
03677       if (log0 < 6 || log0 > 13)                       return error(f, VORBIS_invalid_setup);
03678       if (log1 < 6 || log1 > 13)                       return error(f, VORBIS_invalid_setup);
03679       if (log0 > log1)                                 return error(f, VORBIS_invalid_setup);
03680    }
03681 
03682    // framing_flag
03683    x = get8(f);
03684    if (!(x & 1))                                    return error(f, VORBIS_invalid_first_page);
03685 
03686    // second packet!
03687    if (!start_page(f))                              return FALSE;
03688 
03689    if (!start_packet(f))                            return FALSE;
03690 
03691    if (!next_segment(f))                            return FALSE;
03692 
03693    if (get8_packet(f) != VORBIS_packet_comment)            return error(f, VORBIS_invalid_setup);
03694    for (i=0; i < 6; ++i) header[i] = get8_packet(f);
03695    if (!vorbis_validate(header))                    return error(f, VORBIS_invalid_setup);
03696    //file vendor
03697    len = get32_packet(f);
03698    f->vendor = (char*)setup_malloc(f, sizeof(char) * (len+1));
03699    for(i=0; i < len; ++i) {
03700       f->vendor[i] = get8_packet(f);
03701    }
03702    f->vendor[len] = (char)'\0';
03703    //user comments
03704    f->comment_list_length = get32_packet(f);
03705    f->comment_list = (char**)setup_malloc(f, sizeof(char*) * (f->comment_list_length));
03706 
03707    for(i=0; i < f->comment_list_length; ++i) {
03708       len = get32_packet(f);
03709       f->comment_list[i] = (char*)setup_malloc(f, sizeof(char) * (len+1));
03710 
03711       for(j=0; j < len; ++j) {
03712          f->comment_list[i][j] = get8_packet(f);
03713       }
03714       f->comment_list[i][len] = (char)'\0';
03715    }
03716 
03717    // framing_flag
03718    x = get8_packet(f);
03719    if (!(x & 1))                                    return error(f, VORBIS_invalid_setup);
03720 
03721 
03722    skip(f, f->bytes_in_seg);
03723    f->bytes_in_seg = 0;
03724 
03725    do {
03726       len = next_segment(f);
03727       skip(f, len);
03728       f->bytes_in_seg = 0;
03729    } while (len);
03730 
03731    // third packet!
03732    if (!start_packet(f))                            return FALSE;
03733 
03734    #ifndef STB_VORBIS_NO_PUSHDATA_API
03735    if (IS_PUSH_MODE(f)) {
03736       if (!is_whole_packet_present(f)) {
03737          // convert error in ogg header to write type
03738          if (f->error == VORBIS_invalid_stream)
03739             f->error = VORBIS_invalid_setup;
03740          return FALSE;
03741       }
03742    }
03743    #endif
03744 
03745    crc32_init(); // always init it, to avoid multithread race conditions
03746 
03747    if (get8_packet(f) != VORBIS_packet_setup)       return error(f, VORBIS_invalid_setup);
03748    for (i=0; i < 6; ++i) header[i] = get8_packet(f);
03749    if (!vorbis_validate(header))                    return error(f, VORBIS_invalid_setup);
03750 
03751    // codebooks
03752 
03753    f->codebook_count = get_bits(f,8) + 1;
03754    f->codebooks = (Codebook *) setup_malloc(f, sizeof(*f->codebooks) * f->codebook_count);
03755    if (f->codebooks == NULL)                        return error(f, VORBIS_outofmem);
03756    memset(f->codebooks, 0, sizeof(*f->codebooks) * f->codebook_count);
03757    for (i=0; i < f->codebook_count; ++i) {
03758       uint32 *values;
03759       int ordered, sorted_count;
03760       int total=0;
03761       uint8 *lengths;
03762       Codebook *c = f->codebooks+i;
03763       CHECK(f);
03764       x = get_bits(f, 8); if (x != 0x42)            return error(f, VORBIS_invalid_setup);
03765       x = get_bits(f, 8); if (x != 0x43)            return error(f, VORBIS_invalid_setup);
03766       x = get_bits(f, 8); if (x != 0x56)            return error(f, VORBIS_invalid_setup);
03767       x = get_bits(f, 8);
03768       c->dimensions = (get_bits(f, 8)<<8) + x;
03769       x = get_bits(f, 8);
03770       y = get_bits(f, 8);
03771       c->entries = (get_bits(f, 8)<<16) + (y<<8) + x;
03772       ordered = get_bits(f,1);
03773       c->sparse = ordered ? 0 : get_bits(f,1);
03774 
03775       if (c->dimensions == 0 && c->entries != 0)    return error(f, VORBIS_invalid_setup);
03776 
03777       if (c->sparse)
03778          lengths = (uint8 *) setup_temp_malloc(f, c->entries);
03779       else
03780          lengths = c->codeword_lengths = (uint8 *) setup_malloc(f, c->entries);
03781 
03782       if (!lengths) return error(f, VORBIS_outofmem);
03783 
03784       if (ordered) {
03785          int current_entry = 0;
03786          int current_length = get_bits(f,5) + 1;
03787          while (current_entry < c->entries) {
03788             int limit = c->entries - current_entry;
03789             int n = get_bits(f, ilog(limit));
03790             if (current_length >= 32) return error(f, VORBIS_invalid_setup);
03791             if (current_entry + n > (int) c->entries) { return error(f, VORBIS_invalid_setup); }
03792             memset(lengths + current_entry, current_length, n);
03793             current_entry += n;
03794             ++current_length;
03795          }
03796       } else {
03797          for (j=0; j < c->entries; ++j) {
03798             int present = c->sparse ? get_bits(f,1) : 1;
03799             if (present) {
03800                lengths[j] = get_bits(f, 5) + 1;
03801                ++total;
03802                if (lengths[j] == 32)
03803                   return error(f, VORBIS_invalid_setup);
03804             } else {
03805                lengths[j] = NO_CODE;
03806             }
03807          }
03808       }
03809 
03810       if (c->sparse && total >= c->entries >> 2) {
03811          // convert sparse items to non-sparse!
03812          if (c->entries > (int) f->setup_temp_memory_required)
03813             f->setup_temp_memory_required = c->entries;
03814 
03815          c->codeword_lengths = (uint8 *) setup_malloc(f, c->entries);
03816          if (c->codeword_lengths == NULL) return error(f, VORBIS_outofmem);
03817          memcpy(c->codeword_lengths, lengths, c->entries);
03818          setup_temp_free(f, lengths, c->entries); // note this is only safe if there have been no intervening temp mallocs!
03819          lengths = c->codeword_lengths;
03820          c->sparse = 0;
03821       }
03822 
03823       // compute the size of the sorted tables
03824       if (c->sparse) {
03825          sorted_count = total;
03826       } else {
03827          sorted_count = 0;
03828          #ifndef STB_VORBIS_NO_HUFFMAN_BINARY_SEARCH
03829          for (j=0; j < c->entries; ++j)
03830             if (lengths[j] > STB_VORBIS_FAST_HUFFMAN_LENGTH && lengths[j] != NO_CODE)
03831                ++sorted_count;
03832          #endif
03833       }
03834 
03835       c->sorted_entries = sorted_count;
03836       values = NULL;
03837 
03838       CHECK(f);
03839       if (!c->sparse) {
03840          c->codewords = (uint32 *) setup_malloc(f, sizeof(c->codewords[0]) * c->entries);
03841          if (!c->codewords)                  return error(f, VORBIS_outofmem);
03842       } else {
03843          unsigned int size;
03844          if (c->sorted_entries) {
03845             c->codeword_lengths = (uint8 *) setup_malloc(f, c->sorted_entries);
03846             if (!c->codeword_lengths)           return error(f, VORBIS_outofmem);
03847             c->codewords = (uint32 *) setup_temp_malloc(f, sizeof(*c->codewords) * c->sorted_entries);
03848             if (!c->codewords)                  return error(f, VORBIS_outofmem);
03849             values = (uint32 *) setup_temp_malloc(f, sizeof(*values) * c->sorted_entries);
03850             if (!values)                        return error(f, VORBIS_outofmem);
03851          }
03852          size = c->entries + (sizeof(*c->codewords) + sizeof(*values)) * c->sorted_entries;
03853          if (size > f->setup_temp_memory_required)
03854             f->setup_temp_memory_required = size;
03855       }
03856 
03857       if (!compute_codewords(c, lengths, c->entries, values)) {
03858          if (c->sparse) setup_temp_free(f, values, 0);
03859          return error(f, VORBIS_invalid_setup);
03860       }
03861 
03862       if (c->sorted_entries) {
03863          // allocate an extra slot for sentinels
03864          c->sorted_codewords = (uint32 *) setup_malloc(f, sizeof(*c->sorted_codewords) * (c->sorted_entries+1));
03865          if (c->sorted_codewords == NULL) return error(f, VORBIS_outofmem);
03866          // allocate an extra slot at the front so that c->sorted_values[-1] is defined
03867          // so that we can catch that case without an extra if
03868          c->sorted_values    = ( int   *) setup_malloc(f, sizeof(*c->sorted_values   ) * (c->sorted_entries+1));
03869          if (c->sorted_values == NULL) return error(f, VORBIS_outofmem);
03870          ++c->sorted_values;
03871          c->sorted_values[-1] = -1;
03872          compute_sorted_huffman(c, lengths, values);
03873       }
03874 
03875       if (c->sparse) {
03876          setup_temp_free(f, values, sizeof(*values)*c->sorted_entries);
03877          setup_temp_free(f, c->codewords, sizeof(*c->codewords)*c->sorted_entries);
03878          setup_temp_free(f, lengths, c->entries);
03879          c->codewords = NULL;
03880       }
03881 
03882       compute_accelerated_huffman(c);
03883 
03884       CHECK(f);
03885       c->lookup_type = get_bits(f, 4);
03886       if (c->lookup_type > 2) return error(f, VORBIS_invalid_setup);
03887       if (c->lookup_type > 0) {
03888          uint16 *mults;
03889          c->minimum_value = float32_unpack(get_bits(f, 32));
03890          c->delta_value = float32_unpack(get_bits(f, 32));
03891          c->value_bits = get_bits(f, 4)+1;
03892          c->sequence_p = get_bits(f,1);
03893          if (c->lookup_type == 1) {
03894             int values = lookup1_values(c->entries, c->dimensions);
03895             if (values < 0) return error(f, VORBIS_invalid_setup);
03896             c->lookup_values = (uint32) values;
03897          } else {
03898             c->lookup_values = c->entries * c->dimensions;
03899          }
03900          if (c->lookup_values == 0) return error(f, VORBIS_invalid_setup);
03901          mults = (uint16 *) setup_temp_malloc(f, sizeof(mults[0]) * c->lookup_values);
03902          if (mults == NULL) return error(f, VORBIS_outofmem);
03903          for (j=0; j < (int) c->lookup_values; ++j) {
03904             int q = get_bits(f, c->value_bits);
03905             if (q == EOP) { setup_temp_free(f,mults,sizeof(mults[0])*c->lookup_values); return error(f, VORBIS_invalid_setup); }
03906             mults[j] = q;
03907          }
03908 
03909 #ifndef STB_VORBIS_DIVIDES_IN_CODEBOOK
03910          if (c->lookup_type == 1) {
03911             int len, sparse = c->sparse;
03912             float last=0;
03913             // pre-expand the lookup1-style multiplicands, to avoid a divide in the inner loop
03914             if (sparse) {
03915                if (c->sorted_entries == 0) goto skip;
03916                c->multiplicands = (codetype *) setup_malloc(f, sizeof(c->multiplicands[0]) * c->sorted_entries * c->dimensions);
03917             } else
03918                c->multiplicands = (codetype *) setup_malloc(f, sizeof(c->multiplicands[0]) * c->entries        * c->dimensions);
03919             if (c->multiplicands == NULL) { setup_temp_free(f,mults,sizeof(mults[0])*c->lookup_values); return error(f, VORBIS_outofmem); }
03920             len = sparse ? c->sorted_entries : c->entries;
03921             for (j=0; j < len; ++j) {
03922                unsigned int z = sparse ? c->sorted_values[j] : j;
03923                unsigned int div=1;
03924                for (k=0; k < c->dimensions; ++k) {
03925                   int off = (z / div) % c->lookup_values;
03926                   const float val = mults[off]*c->delta_value + c->minimum_value + last;
03927                   c->multiplicands[j*c->dimensions + k] = val;
03928                   if (c->sequence_p)
03929                      last = val;
03930                   if (k+1 < c->dimensions) {
03931                      if (div > UINT_MAX / (unsigned int) c->lookup_values) {
03932                         setup_temp_free(f, mults,sizeof(mults[0])*c->lookup_values);
03933                         return error(f, VORBIS_invalid_setup);
03934                      }
03935                      div *= c->lookup_values;
03936                   }
03937                }
03938             }
03939             c->lookup_type = 2;
03940          }
03941          else
03942 #endif
03943          {
03944             float last=0;
03945             CHECK(f);
03946             c->multiplicands = (codetype *) setup_malloc(f, sizeof(c->multiplicands[0]) * c->lookup_values);
03947             if (c->multiplicands == NULL) { setup_temp_free(f, mults,sizeof(mults[0])*c->lookup_values); return error(f, VORBIS_outofmem); }
03948             for (j=0; j < (int) c->lookup_values; ++j) {
03949                float val = mults[j] * c->delta_value + c->minimum_value + last;
03950                c->multiplicands[j] = val;
03951                if (c->sequence_p)
03952                   last = val;
03953             }
03954          }
03955 #ifndef STB_VORBIS_DIVIDES_IN_CODEBOOK
03956         skip:;
03957 #endif
03958          setup_temp_free(f, mults, sizeof(mults[0])*c->lookup_values);
03959 
03960          CHECK(f);
03961       }
03962       CHECK(f);
03963    }
03964 
03965    // time domain transfers (notused)
03966 
03967    x = get_bits(f, 6) + 1;
03968    for (i=0; i < x; ++i) {
03969       uint32 z = get_bits(f, 16);
03970       if (z != 0) return error(f, VORBIS_invalid_setup);
03971    }
03972 
03973    // Floors
03974    f->floor_count = get_bits(f, 6)+1;
03975    f->floor_config = (Floor *)  setup_malloc(f, f->floor_count * sizeof(*f->floor_config));
03976    if (f->floor_config == NULL) return error(f, VORBIS_outofmem);
03977    for (i=0; i < f->floor_count; ++i) {
03978       f->floor_types[i] = get_bits(f, 16);
03979       if (f->floor_types[i] > 1) return error(f, VORBIS_invalid_setup);
03980       if (f->floor_types[i] == 0) {
03981          Floor0 *g = &f->floor_config[i].floor0;
03982          g->order = get_bits(f,8);
03983          g->rate = get_bits(f,16);
03984          g->bark_map_size = get_bits(f,16);
03985          g->amplitude_bits = get_bits(f,6);
03986          g->amplitude_offset = get_bits(f,8);
03987          g->number_of_books = get_bits(f,4) + 1;
03988          for (j=0; j < g->number_of_books; ++j)
03989             g->book_list[j] = get_bits(f,8);
03990          return error(f, VORBIS_feature_not_supported);
03991       } else {
03992          stbv__floor_ordering p[31*8+2];
03993          Floor1 *g = &f->floor_config[i].floor1;
03994          int max_class = -1;
03995          g->partitions = get_bits(f, 5);
03996          for (j=0; j < g->partitions; ++j) {
03997             g->partition_class_list[j] = get_bits(f, 4);
03998             if (g->partition_class_list[j] > max_class)
03999                max_class = g->partition_class_list[j];
04000          }
04001          for (j=0; j <= max_class; ++j) {
04002             g->class_dimensions[j] = get_bits(f, 3)+1;
04003             g->class_subclasses[j] = get_bits(f, 2);
04004             if (g->class_subclasses[j]) {
04005                g->class_masterbooks[j] = get_bits(f, 8);
04006                if (g->class_masterbooks[j] >= f->codebook_count) return error(f, VORBIS_invalid_setup);
04007             }
04008             for (k=0; k < 1 << g->class_subclasses[j]; ++k) {
04009                g->subclass_books[j][k] = get_bits(f,8)-1;
04010                if (g->subclass_books[j][k] >= f->codebook_count) return error(f, VORBIS_invalid_setup);
04011             }
04012          }
04013          g->floor1_multiplier = get_bits(f,2)+1;
04014          g->rangebits = get_bits(f,4);
04015          g->Xlist[0] = 0;
04016          g->Xlist[1] = 1 << g->rangebits;
04017          g->values = 2;
04018          for (j=0; j < g->partitions; ++j) {
04019             int c = g->partition_class_list[j];
04020             for (k=0; k < g->class_dimensions[c]; ++k) {
04021                g->Xlist[g->values] = get_bits(f, g->rangebits);
04022                ++g->values;
04023             }
04024          }
04025          // precompute the sorting
04026          for (j=0; j < g->values; ++j) {
04027             p[j].x = g->Xlist[j];
04028             p[j].id = j;
04029          }
04030          qsort(p, g->values, sizeof(p[0]), point_compare);
04031          for (j=0; j < g->values-1; ++j)
04032             if (p[j].x == p[j+1].x)
04033                return error(f, VORBIS_invalid_setup);
04034          for (j=0; j < g->values; ++j)
04035             g->sorted_order[j] = (uint8) p[j].id;
04036          // precompute the neighbors
04037          for (j=2; j < g->values; ++j) {
04038             int low = 0,hi = 0;
04039             neighbors(g->Xlist, j, &low,&hi);
04040             g->neighbors[j][0] = low;
04041             g->neighbors[j][1] = hi;
04042          }
04043 
04044          if (g->values > longest_floorlist)
04045             longest_floorlist = g->values;
04046       }
04047    }
04048 
04049    // Residue
04050    f->residue_count = get_bits(f, 6)+1;
04051    f->residue_config = (Residue *) setup_malloc(f, f->residue_count * sizeof(f->residue_config[0]));
04052    if (f->residue_config == NULL) return error(f, VORBIS_outofmem);
04053    memset(f->residue_config, 0, f->residue_count * sizeof(f->residue_config[0]));
04054    for (i=0; i < f->residue_count; ++i) {
04055       uint8 residue_cascade[64];
04056       Residue *r = f->residue_config+i;
04057       f->residue_types[i] = get_bits(f, 16);
04058       if (f->residue_types[i] > 2) return error(f, VORBIS_invalid_setup);
04059       r->begin = get_bits(f, 24);
04060       r->end = get_bits(f, 24);
04061       if (r->end < r->begin) return error(f, VORBIS_invalid_setup);
04062       r->part_size = get_bits(f,24)+1;
04063       r->classifications = get_bits(f,6)+1;
04064       r->classbook = get_bits(f,8);
04065       if (r->classbook >= f->codebook_count) return error(f, VORBIS_invalid_setup);
04066       for (j=0; j < r->classifications; ++j) {
04067          uint8 high_bits=0;
04068          uint8 low_bits=get_bits(f,3);
04069          if (get_bits(f,1))
04070             high_bits = get_bits(f,5);
04071          residue_cascade[j] = high_bits*8 + low_bits;
04072       }
04073       r->residue_books = (short (*)[8]) setup_malloc(f, sizeof(r->residue_books[0]) * r->classifications);
04074       if (r->residue_books == NULL) return error(f, VORBIS_outofmem);
04075       for (j=0; j < r->classifications; ++j) {
04076          for (k=0; k < 8; ++k) {
04077             if (residue_cascade[j] & (1 << k)) {
04078                r->residue_books[j][k] = get_bits(f, 8);
04079                if (r->residue_books[j][k] >= f->codebook_count) return error(f, VORBIS_invalid_setup);
04080             } else {
04081                r->residue_books[j][k] = -1;
04082             }
04083          }
04084       }
04085       // precompute the classifications[] array to avoid inner-loop mod/divide
04086       // call it 'classdata' since we already have r->classifications
04087       r->classdata = (uint8 **) setup_malloc(f, sizeof(*r->classdata) * f->codebooks[r->classbook].entries);
04088       if (!r->classdata) return error(f, VORBIS_outofmem);
04089       memset(r->classdata, 0, sizeof(*r->classdata) * f->codebooks[r->classbook].entries);
04090       for (j=0; j < f->codebooks[r->classbook].entries; ++j) {
04091          int classwords = f->codebooks[r->classbook].dimensions;
04092          int temp = j;
04093          r->classdata[j] = (uint8 *) setup_malloc(f, sizeof(r->classdata[j][0]) * classwords);
04094          if (r->classdata[j] == NULL) return error(f, VORBIS_outofmem);
04095          for (k=classwords-1; k >= 0; --k) {
04096             r->classdata[j][k] = temp % r->classifications;
04097             temp /= r->classifications;
04098          }
04099       }
04100    }
04101 
04102    f->mapping_count = get_bits(f,6)+1;
04103    f->mapping = (Mapping *) setup_malloc(f, f->mapping_count * sizeof(*f->mapping));
04104    if (f->mapping == NULL) return error(f, VORBIS_outofmem);
04105    memset(f->mapping, 0, f->mapping_count * sizeof(*f->mapping));
04106    for (i=0; i < f->mapping_count; ++i) {
04107       Mapping *m = f->mapping + i;
04108       int mapping_type = get_bits(f,16);
04109       if (mapping_type != 0) return error(f, VORBIS_invalid_setup);
04110       m->chan = (MappingChannel *) setup_malloc(f, f->channels * sizeof(*m->chan));
04111       if (m->chan == NULL) return error(f, VORBIS_outofmem);
04112       if (get_bits(f,1))
04113          m->submaps = get_bits(f,4)+1;
04114       else
04115          m->submaps = 1;
04116       if (m->submaps > max_submaps)
04117          max_submaps = m->submaps;
04118       if (get_bits(f,1)) {
04119          m->coupling_steps = get_bits(f,8)+1;
04120          if (m->coupling_steps > f->channels) return error(f, VORBIS_invalid_setup);
04121          for (k=0; k < m->coupling_steps; ++k) {
04122             m->chan[k].magnitude = get_bits(f, ilog(f->channels-1));
04123             m->chan[k].angle = get_bits(f, ilog(f->channels-1));
04124             if (m->chan[k].magnitude >= f->channels)        return error(f, VORBIS_invalid_setup);
04125             if (m->chan[k].angle     >= f->channels)        return error(f, VORBIS_invalid_setup);
04126             if (m->chan[k].magnitude == m->chan[k].angle)   return error(f, VORBIS_invalid_setup);
04127          }
04128       } else
04129          m->coupling_steps = 0;
04130 
04131       // reserved field
04132       if (get_bits(f,2)) return error(f, VORBIS_invalid_setup);
04133       if (m->submaps > 1) {
04134          for (j=0; j < f->channels; ++j) {
04135             m->chan[j].mux = get_bits(f, 4);
04136             if (m->chan[j].mux >= m->submaps)                return error(f, VORBIS_invalid_setup);
04137          }
04138       } else
04139          // @SPECIFICATION: this case is missing from the spec
04140          for (j=0; j < f->channels; ++j)
04141             m->chan[j].mux = 0;
04142 
04143       for (j=0; j < m->submaps; ++j) {
04144          get_bits(f,8); // discard
04145          m->submap_floor[j] = get_bits(f,8);
04146          m->submap_residue[j] = get_bits(f,8);
04147          if (m->submap_floor[j] >= f->floor_count)      return error(f, VORBIS_invalid_setup);
04148          if (m->submap_residue[j] >= f->residue_count)  return error(f, VORBIS_invalid_setup);
04149       }
04150    }
04151 
04152    // Modes
04153    f->mode_count = get_bits(f, 6)+1;
04154    for (i=0; i < f->mode_count; ++i) {
04155       Mode *m = f->mode_config+i;
04156       m->blockflag = get_bits(f,1);
04157       m->windowtype = get_bits(f,16);
04158       m->transformtype = get_bits(f,16);
04159       m->mapping = get_bits(f,8);
04160       if (m->windowtype != 0)                 return error(f, VORBIS_invalid_setup);
04161       if (m->transformtype != 0)              return error(f, VORBIS_invalid_setup);
04162       if (m->mapping >= f->mapping_count)     return error(f, VORBIS_invalid_setup);
04163    }
04164 
04165    flush_packet(f);
04166 
04167    f->previous_length = 0;
04168 
04169    for (i=0; i < f->channels; ++i) {
04170       f->channel_buffers[i] = (float *) setup_malloc(f, sizeof(float) * f->blocksize_1);
04171       f->previous_window[i] = (float *) setup_malloc(f, sizeof(float) * f->blocksize_1/2);
04172       f->finalY[i]          = (int16 *) setup_malloc(f, sizeof(int16) * longest_floorlist);
04173       if (f->channel_buffers[i] == NULL || f->previous_window[i] == NULL || f->finalY[i] == NULL) return error(f, VORBIS_outofmem);
04174       memset(f->channel_buffers[i], 0, sizeof(float) * f->blocksize_1);
04175       #ifdef STB_VORBIS_NO_DEFER_FLOOR
04176       f->floor_buffers[i]   = (float *) setup_malloc(f, sizeof(float) * f->blocksize_1/2);
04177       if (f->floor_buffers[i] == NULL) return error(f, VORBIS_outofmem);
04178       #endif
04179    }
04180 
04181    if (!init_blocksize(f, 0, f->blocksize_0)) return FALSE;
04182    if (!init_blocksize(f, 1, f->blocksize_1)) return FALSE;
04183    f->blocksize[0] = f->blocksize_0;
04184    f->blocksize[1] = f->blocksize_1;
04185 
04186 #ifdef STB_VORBIS_DIVIDE_TABLE
04187    if (integer_divide_table[1][1]==0)
04188       for (i=0; i < DIVTAB_NUMER; ++i)
04189          for (j=1; j < DIVTAB_DENOM; ++j)
04190             integer_divide_table[i][j] = i / j;
04191 #endif
04192 
04193    // compute how much temporary memory is needed
04194 
04195    // 1.
04196    {
04197       uint32 imdct_mem = (f->blocksize_1 * sizeof(float) >> 1);
04198       uint32 classify_mem;
04199       int i,max_part_read=0;
04200       for (i=0; i < f->residue_count; ++i) {
04201          Residue *r = f->residue_config + i;
04202          unsigned int actual_size = f->blocksize_1 / 2;
04203          unsigned int limit_r_begin = r->begin < actual_size ? r->begin : actual_size;
04204          unsigned int limit_r_end   = r->end   < actual_size ? r->end   : actual_size;
04205          int n_read = limit_r_end - limit_r_begin;
04206          int part_read = n_read / r->part_size;
04207          if (part_read > max_part_read)
04208             max_part_read = part_read;
04209       }
04210       #ifndef STB_VORBIS_DIVIDES_IN_RESIDUE
04211       classify_mem = f->channels * (sizeof(void*) + max_part_read * sizeof(uint8 *));
04212       #else
04213       classify_mem = f->channels * (sizeof(void*) + max_part_read * sizeof(int *));
04214       #endif
04215 
04216       // maximum reasonable partition size is f->blocksize_1
04217 
04218       f->temp_memory_required = classify_mem;
04219       if (imdct_mem > f->temp_memory_required)
04220          f->temp_memory_required = imdct_mem;
04221    }
04222 
04223 
04224    if (f->alloc.alloc_buffer) {
04225       assert(f->temp_offset == f->alloc.alloc_buffer_length_in_bytes);
04226       // check if there's enough temp memory so we don't error later
04227       if (f->setup_offset + sizeof(*f) + f->temp_memory_required > (unsigned) f->temp_offset)
04228          return error(f, VORBIS_outofmem);
04229    }
04230 
04231    // @TODO: stb_vorbis_seek_start expects first_audio_page_offset to point to a page
04232    // without PAGEFLAG_continued_packet, so this either points to the first page, or
04233    // the page after the end of the headers. It might be cleaner to point to a page
04234    // in the middle of the headers, when that's the page where the first audio packet
04235    // starts, but we'd have to also correctly skip the end of any continued packet in
04236    // stb_vorbis_seek_start.
04237    if (f->next_seg == -1) {
04238       f->first_audio_page_offset = stb_vorbis_get_file_offset(f);
04239    } else {
04240       f->first_audio_page_offset = 0;
04241    }
04242 
04243    return TRUE;
04244 }
04245 
04246 static void vorbis_deinit(stb_vorbis *p)
04247 {
04248    int i,j;
04249 
04250    setup_free(p, p->vendor);
04251    for (i=0; i < p->comment_list_length; ++i) {
04252       setup_free(p, p->comment_list[i]);
04253    }
04254    setup_free(p, p->comment_list);
04255 
04256    if (p->residue_config) {
04257       for (i=0; i < p->residue_count; ++i) {
04258          Residue *r = p->residue_config+i;
04259          if (r->classdata) {
04260             for (j=0; j < p->codebooks[r->classbook].entries; ++j)
04261                setup_free(p, r->classdata[j]);
04262             setup_free(p, r->classdata);
04263          }
04264          setup_free(p, r->residue_books);
04265       }
04266    }
04267 
04268    if (p->codebooks) {
04269       CHECK(p);
04270       for (i=0; i < p->codebook_count; ++i) {
04271          Codebook *c = p->codebooks + i;
04272          setup_free(p, c->codeword_lengths);
04273          setup_free(p, c->multiplicands);
04274          setup_free(p, c->codewords);
04275          setup_free(p, c->sorted_codewords);
04276          // c->sorted_values[-1] is the first entry in the array
04277          setup_free(p, c->sorted_values ? c->sorted_values-1 : NULL);
04278       }
04279       setup_free(p, p->codebooks);
04280    }
04281    setup_free(p, p->floor_config);
04282    setup_free(p, p->residue_config);
04283    if (p->mapping) {
04284       for (i=0; i < p->mapping_count; ++i)
04285          setup_free(p, p->mapping[i].chan);
04286       setup_free(p, p->mapping);
04287    }
04288    CHECK(p);
04289    for (i=0; i < p->channels && i < STB_VORBIS_MAX_CHANNELS; ++i) {
04290       setup_free(p, p->channel_buffers[i]);
04291       setup_free(p, p->previous_window[i]);
04292       #ifdef STB_VORBIS_NO_DEFER_FLOOR
04293       setup_free(p, p->floor_buffers[i]);
04294       #endif
04295       setup_free(p, p->finalY[i]);
04296    }
04297    for (i=0; i < 2; ++i) {
04298       setup_free(p, p->A[i]);
04299       setup_free(p, p->B[i]);
04300       setup_free(p, p->C[i]);
04301       setup_free(p, p->window[i]);
04302       setup_free(p, p->bit_reverse[i]);
04303    }
04304    #ifdef __SDL_SOUND_INTERNAL__
04305    if (p->close_on_free) SDL_RWclose(p->rwops);
04306    #endif
04307    #ifndef STB_VORBIS_NO_STDIO
04308    if (p->close_on_free) fclose(p->f);
04309    #endif
04310 }
04311 
04312 void stb_vorbis_close(stb_vorbis *p)
04313 {
04314    if (p == NULL) return;
04315    vorbis_deinit(p);
04316    setup_free(p,p);
04317 }
04318 
04319 static void vorbis_init(stb_vorbis *p, const stb_vorbis_alloc *z)
04320 {
04321    memset(p, 0, sizeof(*p)); // NULL out all malloc'd pointers to start
04322    if (z) {
04323       p->alloc = *z;
04324       p->alloc.alloc_buffer_length_in_bytes = (p->alloc.alloc_buffer_length_in_bytes+3) & ~3;
04325       p->temp_offset = p->alloc.alloc_buffer_length_in_bytes;
04326    }
04327    p->eof = 0;
04328    p->error = VORBIS__no_error;
04329    p->stream = NULL;
04330    p->codebooks = NULL;
04331    p->page_crc_tests = -1;
04332    #ifdef __SDL_SOUND_INTERNAL__
04333    p->close_on_free = FALSE;
04334    p->rwops = NULL;
04335    #endif
04336    #ifndef STB_VORBIS_NO_STDIO
04337    p->close_on_free = FALSE;
04338    p->f = NULL;
04339    #endif
04340 }
04341 
04342 int stb_vorbis_get_sample_offset(stb_vorbis *f)
04343 {
04344    if (f->current_loc_valid)
04345       return f->current_loc;
04346    else
04347       return -1;
04348 }
04349 
04350 stb_vorbis_info stb_vorbis_get_info(stb_vorbis *f)
04351 {
04352    stb_vorbis_info d;
04353    d.channels = f->channels;
04354    d.sample_rate = f->sample_rate;
04355    d.setup_memory_required = f->setup_memory_required;
04356    d.setup_temp_memory_required = f->setup_temp_memory_required;
04357    d.temp_memory_required = f->temp_memory_required;
04358    d.max_frame_size = f->blocksize_1 >> 1;
04359    return d;
04360 }
04361 
04362 stb_vorbis_comment stb_vorbis_get_comment(stb_vorbis *f)
04363 {
04364    stb_vorbis_comment d;
04365    d.vendor = f->vendor;
04366    d.comment_list_length = f->comment_list_length;
04367    d.comment_list = f->comment_list;
04368    return d;
04369 }
04370 
04371 int stb_vorbis_get_error(stb_vorbis *f)
04372 {
04373    int e = (int)(f->error);
04374    f->error = VORBIS__no_error;
04375    return e;
04376 }
04377 
04378 static stb_vorbis * vorbis_alloc(stb_vorbis *f)
04379 {
04380    stb_vorbis *p = (stb_vorbis *) setup_malloc(f, sizeof(*p));
04381    return p;
04382 }
04383 
04384 #ifndef STB_VORBIS_NO_PUSHDATA_API
04385 
04386 void stb_vorbis_flush_pushdata(stb_vorbis *f)
04387 {
04388    f->previous_length = 0;
04389    f->page_crc_tests  = 0;
04390    f->discard_samples_deferred = 0;
04391    f->current_loc_valid = FALSE;
04392    f->first_decode = FALSE;
04393    f->samples_output = 0;
04394    f->channel_buffer_start = 0;
04395    f->channel_buffer_end = 0;
04396 }
04397 
04398 static int vorbis_search_for_page_pushdata(vorb *f, uint8 *data, int data_len)
04399 {
04400    int i,n;
04401    for (i=0; i < f->page_crc_tests; ++i)
04402       f->scan[i].bytes_done = 0;
04403 
04404    // if we have room for more scans, search for them first, because
04405    // they may cause us to stop early if their header is incomplete
04406    if (f->page_crc_tests < STB_VORBIS_PUSHDATA_CRC_COUNT) {
04407       if (data_len < 4) return 0;
04408       data_len -= 3; // need to look for 4-byte sequence, so don't miss
04409                      // one that straddles a boundary
04410       for (i=0; i < data_len; ++i) {
04411          if (data[i] == 0x4f) {
04412             if (0==memcmp(data+i, ogg_page_header, 4)) {
04413                int j,len;
04414                uint32 crc;
04415                // make sure we have the whole page header
04416                if (i+26 >= data_len || i+27+data[i+26] >= data_len) {
04417                   // only read up to this page start, so hopefully we'll
04418                   // have the whole page header start next time
04419                   data_len = i;
04420                   break;
04421                }
04422                // ok, we have it all; compute the length of the page
04423                len = 27 + data[i+26];
04424                for (j=0; j < data[i+26]; ++j)
04425                   len += data[i+27+j];
04426                // scan everything up to the embedded crc (which we must 0)
04427                crc = 0;
04428                for (j=0; j < 22; ++j)
04429                   crc = crc32_update(crc, data[i+j]);
04430                // now process 4 0-bytes
04431                for (   ; j < 26; ++j)
04432                   crc = crc32_update(crc, 0);
04433                // len is the total number of bytes we need to scan
04434                n = f->page_crc_tests++;
04435                f->scan[n].bytes_left = len-j;
04436                f->scan[n].crc_so_far = crc;
04437                f->scan[n].goal_crc = data[i+22] + (data[i+23] << 8) + (data[i+24]<<16) + (data[i+25]<<24);
04438                // if the last frame on a page is continued to the next, then
04439                // we can't recover the sample_loc immediately
04440                if (data[i+27+data[i+26]-1] == 255)
04441                   f->scan[n].sample_loc = ~0;
04442                else
04443                   f->scan[n].sample_loc = data[i+6] + (data[i+7] << 8) + (data[i+ 8]<<16) + (data[i+ 9]<<24);
04444                f->scan[n].bytes_done = i+j;
04445                if (f->page_crc_tests == STB_VORBIS_PUSHDATA_CRC_COUNT)
04446                   break;
04447                // keep going if we still have room for more
04448             }
04449          }
04450       }
04451    }
04452 
04453    for (i=0; i < f->page_crc_tests;) {
04454       uint32 crc;
04455       int j;
04456       int n = f->scan[i].bytes_done;
04457       int m = f->scan[i].bytes_left;
04458       if (m > data_len - n) m = data_len - n;
04459       // m is the bytes to scan in the current chunk
04460       crc = f->scan[i].crc_so_far;
04461       for (j=0; j < m; ++j)
04462          crc = crc32_update(crc, data[n+j]);
04463       f->scan[i].bytes_left -= m;
04464       f->scan[i].crc_so_far = crc;
04465       if (f->scan[i].bytes_left == 0) {
04466          // does it match?
04467          if (f->scan[i].crc_so_far == f->scan[i].goal_crc) {
04468             // Houston, we have page
04469             data_len = n+m; // consumption amount is wherever that scan ended
04470             f->page_crc_tests = -1; // drop out of page scan mode
04471             f->previous_length = 0; // decode-but-don't-output one frame
04472             f->next_seg = -1;       // start a new page
04473             f->current_loc = f->scan[i].sample_loc; // set the current sample location
04474                                     // to the amount we'd have decoded had we decoded this page
04475             f->current_loc_valid = f->current_loc != ~0U;
04476             return data_len;
04477          }
04478          // delete entry
04479          f->scan[i] = f->scan[--f->page_crc_tests];
04480       } else {
04481          ++i;
04482       }
04483    }
04484 
04485    return data_len;
04486 }
04487 
04488 // return value: number of bytes we used
04489 int stb_vorbis_decode_frame_pushdata(
04490          stb_vorbis *f,                   // the file we're decoding
04491          const uint8 *data, int data_len, // the memory available for decoding
04492          int *channels,                   // place to write number of float * buffers
04493          float ***output,                 // place to write float ** array of float * buffers
04494          int *samples                     // place to write number of output samples
04495      )
04496 {
04497    int i;
04498    int len,right,left;
04499 
04500    if (!IS_PUSH_MODE(f)) return error(f, VORBIS_invalid_api_mixing);
04501 
04502    if (f->page_crc_tests >= 0) {
04503       *samples = 0;
04504       return vorbis_search_for_page_pushdata(f, (uint8 *) data, data_len);
04505    }
04506 
04507    f->stream     = (uint8 *) data;
04508    f->stream_end = (uint8 *) data + data_len;
04509    f->error      = VORBIS__no_error;
04510 
04511    // check that we have the entire packet in memory
04512    if (!is_whole_packet_present(f)) {
04513       *samples = 0;
04514       return 0;
04515    }
04516 
04517    if (!vorbis_decode_packet(f, &len, &left, &right)) {
04518       // save the actual error we encountered
04519       enum STBVorbisError error = f->error;
04520       if (error == VORBIS_bad_packet_type) {
04521          // flush and resynch
04522          f->error = VORBIS__no_error;
04523          while (get8_packet(f) != EOP)
04524             if (f->eof) break;
04525          *samples = 0;
04526          return (int) (f->stream - data);
04527       }
04528       if (error == VORBIS_continued_packet_flag_invalid) {
04529          if (f->previous_length == 0) {
04530             // we may be resynching, in which case it's ok to hit one
04531             // of these; just discard the packet
04532             f->error = VORBIS__no_error;
04533             while (get8_packet(f) != EOP)
04534                if (f->eof) break;
04535             *samples = 0;
04536             return (int) (f->stream - data);
04537          }
04538       }
04539       // if we get an error while parsing, what to do?
04540       // well, it DEFINITELY won't work to continue from where we are!
04541       stb_vorbis_flush_pushdata(f);
04542       // restore the error that actually made us bail
04543       f->error = error;
04544       *samples = 0;
04545       return 1;
04546    }
04547 
04548    // success!
04549    len = vorbis_finish_frame(f, len, left, right);
04550    for (i=0; i < f->channels; ++i)
04551       f->outputs[i] = f->channel_buffers[i] + left;
04552 
04553    if (channels) *channels = f->channels;
04554    *samples = len;
04555    *output = f->outputs;
04556    return (int) (f->stream - data);
04557 }
04558 
04559 stb_vorbis *stb_vorbis_open_pushdata(
04560          const unsigned char *data, int data_len, // the memory available for decoding
04561          int *data_used,              // only defined if result is not NULL
04562          int *error, const stb_vorbis_alloc *alloc)
04563 {
04564    stb_vorbis *f, p;
04565    vorbis_init(&p, alloc);
04566    p.stream     = (uint8 *) data;
04567    p.stream_end = (uint8 *) data + data_len;
04568    p.push_mode  = TRUE;
04569    if (!start_decoder(&p)) {
04570       if (p.eof)
04571          *error = VORBIS_need_more_data;
04572       else
04573          *error = p.error;
04574       return NULL;
04575    }
04576    f = vorbis_alloc(&p);
04577    if (f) {
04578       *f = p;
04579       *data_used = (int) (f->stream - data);
04580       *error = 0;
04581       return f;
04582    } else {
04583       vorbis_deinit(&p);
04584       return NULL;
04585    }
04586 }
04587 #endif // STB_VORBIS_NO_PUSHDATA_API
04588 
04589 unsigned int stb_vorbis_get_file_offset(stb_vorbis *f)
04590 {
04591    #ifndef STB_VORBIS_NO_PUSHDATA_API
04592    if (f->push_mode) return 0;
04593    #endif
04594    if (USE_MEMORY(f)) return (unsigned int) (f->stream - f->stream_start);
04595    #ifdef __SDL_SOUND_INTERNAL__
04596    return (unsigned int) (SDL_RWtell(f->rwops) - f->rwops_start);
04597    #endif
04598    #ifndef STB_VORBIS_NO_STDIO
04599    return (unsigned int) (ftell(f->f) - f->f_start);
04600    #endif
04601 }
04602 
04603 #ifndef STB_VORBIS_NO_PULLDATA_API
04604 //
04605 // DATA-PULLING API
04606 //
04607 
04608 static uint32 vorbis_find_page(stb_vorbis *f, uint32 *end, uint32 *last)
04609 {
04610    for(;;) {
04611       int n;
04612       if (f->eof) return 0;
04613       n = get8(f);
04614       if (n == 0x4f) { // page header candidate
04615          unsigned int retry_loc = stb_vorbis_get_file_offset(f);
04616          int i;
04617          // check if we're off the end of a file_section stream
04618          if (retry_loc - 25 > f->stream_len)
04619             return 0;
04620          // check the rest of the header
04621          for (i=1; i < 4; ++i)
04622             if (get8(f) != ogg_page_header[i])
04623                break;
04624          if (f->eof) return 0;
04625          if (i == 4) {
04626             uint8 header[27];
04627             uint32 i, crc, goal, len;
04628             for (i=0; i < 4; ++i)
04629                header[i] = ogg_page_header[i];
04630             for (; i < 27; ++i)
04631                header[i] = get8(f);
04632             if (f->eof) return 0;
04633             if (header[4] != 0) goto invalid;
04634             goal = header[22] + (header[23] << 8) + (header[24]<<16) + (header[25]<<24);
04635             for (i=22; i < 26; ++i)
04636                header[i] = 0;
04637             crc = 0;
04638             for (i=0; i < 27; ++i)
04639                crc = crc32_update(crc, header[i]);
04640             len = 0;
04641             for (i=0; i < header[26]; ++i) {
04642                int s = get8(f);
04643                crc = crc32_update(crc, s);
04644                len += s;
04645             }
04646             if (len && f->eof) return 0;
04647             for (i=0; i < len; ++i)
04648                crc = crc32_update(crc, get8(f));
04649             // finished parsing probable page
04650             if (crc == goal) {
04651                // we could now check that it's either got the last
04652                // page flag set, OR it's followed by the capture
04653                // pattern, but I guess TECHNICALLY you could have
04654                // a file with garbage between each ogg page and recover
04655                // from it automatically? So even though that paranoia
04656                // might decrease the chance of an invalid decode by
04657                // another 2^32, not worth it since it would hose those
04658                // invalid-but-useful files?
04659                if (end)
04660                   *end = stb_vorbis_get_file_offset(f);
04661                if (last) {
04662                   if (header[5] & 0x04)
04663                      *last = 1;
04664                   else
04665                      *last = 0;
04666                }
04667                set_file_offset(f, retry_loc-1);
04668                return 1;
04669             }
04670          }
04671         invalid:
04672          // not a valid page, so rewind and look for next one
04673          set_file_offset(f, retry_loc);
04674       }
04675    }
04676 }
04677 
04678 
04679 #define SAMPLE_unknown  0xffffffff
04680 
04681 // seeking is implemented with a binary search, which narrows down the range to
04682 // 64K, before using a linear search (because finding the synchronization
04683 // pattern can be expensive, and the chance we'd find the end page again is
04684 // relatively high for small ranges)
04685 //
04686 // two initial interpolation-style probes are used at the start of the search
04687 // to try to bound either side of the binary search sensibly, while still
04688 // working in O(log n) time if they fail.
04689 
04690 static int get_seek_page_info(stb_vorbis *f, ProbedPage *z)
04691 {
04692    uint8 header[27], lacing[255];
04693    int i,len;
04694 
04695    // record where the page starts
04696    z->page_start = stb_vorbis_get_file_offset(f);
04697 
04698    // parse the header
04699    getn(f, header, 27);
04700    if (header[0] != 'O' || header[1] != 'g' || header[2] != 'g' || header[3] != 'S')
04701       return 0;
04702    getn(f, lacing, header[26]);
04703 
04704    // determine the length of the payload
04705    len = 0;
04706    for (i=0; i < header[26]; ++i)
04707       len += lacing[i];
04708 
04709    // this implies where the page ends
04710    z->page_end = z->page_start + 27 + header[26] + len;
04711 
04712    // read the last-decoded sample out of the data
04713    z->last_decoded_sample = header[6] + (header[7] << 8) + (header[8] << 16) + (header[9] << 24);
04714 
04715    // restore file state to where we were
04716    set_file_offset(f, z->page_start);
04717    return 1;
04718 }
04719 
04720 // rarely used function to seek back to the preceding page while finding the
04721 // start of a packet
04722 static int go_to_page_before(stb_vorbis *f, unsigned int limit_offset)
04723 {
04724    unsigned int previous_safe, end;
04725 
04726    // now we want to seek back 64K from the limit
04727    if (limit_offset >= 65536 && limit_offset-65536 >= f->first_audio_page_offset)
04728       previous_safe = limit_offset - 65536;
04729    else
04730       previous_safe = f->first_audio_page_offset;
04731 
04732    set_file_offset(f, previous_safe);
04733 
04734    while (vorbis_find_page(f, &end, NULL)) {
04735       if (end >= limit_offset && stb_vorbis_get_file_offset(f) < limit_offset)
04736          return 1;
04737       set_file_offset(f, end);
04738    }
04739 
04740    return 0;
04741 }
04742 
04743 // implements the search logic for finding a page and starting decoding. if
04744 // the function succeeds, current_loc_valid will be true and current_loc will
04745 // be less than or equal to the provided sample number (the closer the
04746 // better).
04747 static int seek_to_sample_coarse(stb_vorbis *f, uint32 sample_number)
04748 {
04749    ProbedPage left, right, mid;
04750    int i, start_seg_with_known_loc, end_pos, page_start;
04751    uint32 delta, stream_length, padding, last_sample_limit;
04752    double offset = 0.0, bytes_per_sample = 0.0;
04753    int probe = 0;
04754 
04755    // find the last page and validate the target sample
04756    stream_length = stb_vorbis_stream_length_in_samples(f);
04757    if (stream_length == 0)            return error(f, VORBIS_seek_without_length);
04758    if (sample_number > stream_length) return error(f, VORBIS_seek_invalid);
04759 
04760    // this is the maximum difference between the window-center (which is the
04761    // actual granule position value), and the right-start (which the spec
04762    // indicates should be the granule position (give or take one)).
04763    padding = ((f->blocksize_1 - f->blocksize_0) >> 2);
04764    if (sample_number < padding)
04765       last_sample_limit = 0;
04766    else
04767       last_sample_limit = sample_number - padding;
04768 
04769    left = f->p_first;
04770    while (left.last_decoded_sample == ~0U) {
04771       // (untested) the first page does not have a 'last_decoded_sample'
04772       set_file_offset(f, left.page_end);
04773       if (!get_seek_page_info(f, &left)) goto error;
04774    }
04775 
04776    right = f->p_last;
04777    assert(right.last_decoded_sample != ~0U);
04778 
04779    // starting from the start is handled differently
04780    if (last_sample_limit <= left.last_decoded_sample) {
04781       if (stb_vorbis_seek_start(f)) {
04782          if (f->current_loc > sample_number)
04783             return error(f, VORBIS_seek_failed);
04784          return 1;
04785       }
04786       return 0;
04787    }
04788 
04789    while (left.page_end != right.page_start) {
04790       assert(left.page_end < right.page_start);
04791       // search range in bytes
04792       delta = right.page_start - left.page_end;
04793       if (delta <= 65536) {
04794          // there's only 64K left to search - handle it linearly
04795          set_file_offset(f, left.page_end);
04796       } else {
04797          if (probe < 2) {
04798             if (probe == 0) {
04799                // first probe (interpolate)
04800                double data_bytes = right.page_end - left.page_start;
04801                bytes_per_sample = data_bytes / right.last_decoded_sample;
04802                offset = left.page_start + bytes_per_sample * (last_sample_limit - left.last_decoded_sample);
04803             } else {
04804                // second probe (try to bound the other side)
04805                double error = ((double) last_sample_limit - mid.last_decoded_sample) * bytes_per_sample;
04806                if (error >= 0 && error <  8000) error =  8000;
04807                if (error <  0 && error > -8000) error = -8000;
04808                offset += error * 2;
04809             }
04810 
04811             // ensure the offset is valid
04812             if (offset < left.page_end)
04813                offset = left.page_end;
04814             if (offset > right.page_start - 65536)
04815                offset = right.page_start - 65536;
04816 
04817             set_file_offset(f, (unsigned int) offset);
04818          } else {
04819             // binary search for large ranges (offset by 32K to ensure
04820             // we don't hit the right page)
04821             set_file_offset(f, left.page_end + (delta / 2) - 32768);
04822          }
04823 
04824          if (!vorbis_find_page(f, NULL, NULL)) goto error;
04825       }
04826 
04827       for (;;) {
04828          if (!get_seek_page_info(f, &mid)) goto error;
04829          if (mid.last_decoded_sample != ~0U) break;
04830          // (untested) no frames end on this page
04831          set_file_offset(f, mid.page_end);
04832          assert(mid.page_start < right.page_start);
04833       }
04834 
04835       // if we've just found the last page again then we're in a tricky file,
04836       // and we're close enough (if it wasn't an interpolation probe).
04837       if (mid.page_start == right.page_start) {
04838          if (probe >= 2 || delta <= 65536)
04839             break;
04840       } else {
04841          if (last_sample_limit < mid.last_decoded_sample)
04842             right = mid;
04843          else
04844             left = mid;
04845       }
04846 
04847       ++probe;
04848    }
04849 
04850    // seek back to start of the last packet
04851    page_start = left.page_start;
04852    set_file_offset(f, page_start);
04853    if (!start_page(f)) return error(f, VORBIS_seek_failed);
04854    end_pos = f->end_seg_with_known_loc;
04855    assert(end_pos >= 0);
04856 
04857    for (;;) {
04858       for (i = end_pos; i > 0; --i)
04859          if (f->segments[i-1] != 255)
04860             break;
04861 
04862       start_seg_with_known_loc = i;
04863 
04864       if (start_seg_with_known_loc > 0 || !(f->page_flag & PAGEFLAG_continued_packet))
04865          break;
04866 
04867       // (untested) the final packet begins on an earlier page
04868       if (!go_to_page_before(f, page_start))
04869          goto error;
04870 
04871       page_start = stb_vorbis_get_file_offset(f);
04872       if (!start_page(f)) goto error;
04873       end_pos = f->segment_count - 1;
04874    }
04875 
04876    // prepare to start decoding
04877    f->current_loc_valid = FALSE;
04878    f->last_seg = FALSE;
04879    f->valid_bits = 0;
04880    f->packet_bytes = 0;
04881    f->bytes_in_seg = 0;
04882    f->previous_length = 0;
04883    f->next_seg = start_seg_with_known_loc;
04884 
04885    for (i = 0; i < start_seg_with_known_loc; i++)
04886       skip(f, f->segments[i]);
04887 
04888    // start decoding (optimizable - this frame is generally discarded)
04889    if (!vorbis_pump_first_frame(f))
04890       return 0;
04891    if (f->current_loc > sample_number)
04892       return error(f, VORBIS_seek_failed);
04893    return 1;
04894 
04895 error:
04896    // try to restore the file to a valid state
04897    stb_vorbis_seek_start(f);
04898    return error(f, VORBIS_seek_failed);
04899 }
04900 
04901 // the same as vorbis_decode_initial, but without advancing
04902 static int peek_decode_initial(vorb *f, int *p_left_start, int *p_left_end, int *p_right_start, int *p_right_end, int *mode)
04903 {
04904    int bits_read, bytes_read;
04905 
04906    if (!vorbis_decode_initial(f, p_left_start, p_left_end, p_right_start, p_right_end, mode))
04907       return 0;
04908 
04909    // either 1 or 2 bytes were read, figure out which so we can rewind
04910    bits_read = 1 + ilog(f->mode_count-1);
04911    if (f->mode_config[*mode].blockflag)
04912       bits_read += 2;
04913    bytes_read = (bits_read + 7) / 8;
04914 
04915    f->bytes_in_seg += bytes_read;
04916    f->packet_bytes -= bytes_read;
04917    skip(f, -bytes_read);
04918    if (f->next_seg == -1)
04919       f->next_seg = f->segment_count - 1;
04920    else
04921       f->next_seg--;
04922    f->valid_bits = 0;
04923 
04924    return 1;
04925 }
04926 
04927 int stb_vorbis_seek_frame(stb_vorbis *f, unsigned int sample_number)
04928 {
04929    uint32 max_frame_samples;
04930 
04931    if (IS_PUSH_MODE(f)) return error(f, VORBIS_invalid_api_mixing);
04932 
04933    // fast page-level search
04934    if (!seek_to_sample_coarse(f, sample_number))
04935       return 0;
04936 
04937    assert(f->current_loc_valid);
04938    assert(f->current_loc <= sample_number);
04939 
04940    // linear search for the relevant packet
04941    max_frame_samples = (f->blocksize_1*3 - f->blocksize_0) >> 2;
04942    while (f->current_loc < sample_number) {
04943       int left_start, left_end, right_start, right_end, mode, frame_samples;
04944       if (!peek_decode_initial(f, &left_start, &left_end, &right_start, &right_end, &mode))
04945          return error(f, VORBIS_seek_failed);
04946       // calculate the number of samples returned by the next frame
04947       frame_samples = right_start - left_start;
04948       if (f->current_loc + frame_samples > sample_number) {
04949          return 1; // the next frame will contain the sample
04950       } else if (f->current_loc + frame_samples + max_frame_samples > sample_number) {
04951          // there's a chance the frame after this could contain the sample
04952          vorbis_pump_first_frame(f);
04953       } else {
04954          // this frame is too early to be relevant
04955          f->current_loc += frame_samples;
04956          f->previous_length = 0;
04957          maybe_start_packet(f);
04958          flush_packet(f);
04959       }
04960    }
04961    // the next frame should start with the sample
04962    if (f->current_loc != sample_number) return error(f, VORBIS_seek_failed);
04963    return 1;
04964 }
04965 
04966 int stb_vorbis_seek(stb_vorbis *f, unsigned int sample_number)
04967 {
04968    if (!stb_vorbis_seek_frame(f, sample_number))
04969       return 0;
04970 
04971    if (sample_number != f->current_loc) {
04972       int n;
04973       uint32 frame_start = f->current_loc;
04974       stb_vorbis_get_frame_float(f, &n, NULL);
04975       assert(sample_number > frame_start);
04976       assert(f->channel_buffer_start + (int) (sample_number-frame_start) <= f->channel_buffer_end);
04977       f->channel_buffer_start += (sample_number - frame_start);
04978    }
04979 
04980    return 1;
04981 }
04982 
04983 int stb_vorbis_seek_start(stb_vorbis *f)
04984 {
04985    if (IS_PUSH_MODE(f)) { return error(f, VORBIS_invalid_api_mixing); }
04986    set_file_offset(f, f->first_audio_page_offset);
04987    f->previous_length = 0;
04988    f->first_decode = TRUE;
04989    f->next_seg = -1;
04990    return vorbis_pump_first_frame(f);
04991 }
04992 
04993 unsigned int stb_vorbis_stream_length_in_samples(stb_vorbis *f)
04994 {
04995    unsigned int restore_offset, previous_safe;
04996    unsigned int end, last_page_loc;
04997 
04998    if (IS_PUSH_MODE(f)) return error(f, VORBIS_invalid_api_mixing);
04999    if (!f->total_samples) {
05000       unsigned int last;
05001       uint32 lo,hi;
05002       char header[6];
05003 
05004       // first, store the current decode position so we can restore it
05005       restore_offset = stb_vorbis_get_file_offset(f);
05006 
05007       // now we want to seek back 64K from the end (the last page must
05008       // be at most a little less than 64K, but let's allow a little slop)
05009       if (f->stream_len >= 65536 && f->stream_len-65536 >= f->first_audio_page_offset)
05010          previous_safe = f->stream_len - 65536;
05011       else
05012          previous_safe = f->first_audio_page_offset;
05013 
05014       set_file_offset(f, previous_safe);
05015       // previous_safe is now our candidate 'earliest known place that seeking
05016       // to will lead to the final page'
05017 
05018       if (!vorbis_find_page(f, &end, &last)) {
05019          // if we can't find a page, we're hosed!
05020          f->error = VORBIS_cant_find_last_page;
05021          f->total_samples = 0xffffffff;
05022          goto done;
05023       }
05024 
05025       // check if there are more pages
05026       last_page_loc = stb_vorbis_get_file_offset(f);
05027 
05028       // stop when the last_page flag is set, not when we reach eof;
05029       // this allows us to stop short of a 'file_section' end without
05030       // explicitly checking the length of the section
05031       while (!last) {
05032          set_file_offset(f, end);
05033          if (!vorbis_find_page(f, &end, &last)) {
05034             // the last page we found didn't have the 'last page' flag
05035             // set. whoops!
05036             break;
05037          }
05038          last_page_loc = stb_vorbis_get_file_offset(f);
05039       }
05040 
05041       set_file_offset(f, last_page_loc);
05042 
05043       // parse the header
05044       getn(f, (unsigned char *)header, 6);
05045       // extract the absolute granule position
05046       lo = get32(f);
05047       hi = get32(f);
05048       if (lo == 0xffffffff && hi == 0xffffffff) {
05049          f->error = VORBIS_cant_find_last_page;
05050          f->total_samples = SAMPLE_unknown;
05051          goto done;
05052       }
05053       if (hi)
05054          lo = 0xfffffffe; // saturate
05055       f->total_samples = lo;
05056 
05057       f->p_last.page_start = last_page_loc;
05058       f->p_last.page_end   = end;
05059       f->p_last.last_decoded_sample = lo;
05060 
05061      done:
05062       set_file_offset(f, restore_offset);
05063    }
05064    return f->total_samples == SAMPLE_unknown ? 0 : f->total_samples;
05065 }
05066 
05067 float stb_vorbis_stream_length_in_seconds(stb_vorbis *f)
05068 {
05069    return stb_vorbis_stream_length_in_samples(f) / (float) f->sample_rate;
05070 }
05071 
05072 
05073 
05074 int stb_vorbis_get_frame_float(stb_vorbis *f, int *channels, float ***output)
05075 {
05076    int len, right,left,i;
05077    if (IS_PUSH_MODE(f)) return error(f, VORBIS_invalid_api_mixing);
05078 
05079    if (!vorbis_decode_packet(f, &len, &left, &right)) {
05080       f->channel_buffer_start = f->channel_buffer_end = 0;
05081       return 0;
05082    }
05083 
05084    len = vorbis_finish_frame(f, len, left, right);
05085    for (i=0; i < f->channels; ++i)
05086       f->outputs[i] = f->channel_buffers[i] + left;
05087 
05088    f->channel_buffer_start = left;
05089    f->channel_buffer_end   = left+len;
05090 
05091    if (channels) *channels = f->channels;
05092    if (output)   *output = f->outputs;
05093    return len;
05094 }
05095 
05096 #ifndef STB_VORBIS_NO_STDIO
05097 
05098 stb_vorbis * stb_vorbis_open_file_section(FILE *file, int close_on_free, int *error, const stb_vorbis_alloc *alloc, unsigned int length)
05099 {
05100    stb_vorbis *f, p;
05101    vorbis_init(&p, alloc);
05102    p.f = file;
05103    p.f_start = (uint32) ftell(file);
05104    p.stream_len   = length;
05105    p.close_on_free = close_on_free;
05106    if (start_decoder(&p)) {
05107       f = vorbis_alloc(&p);
05108       if (f) {
05109          *f = p;
05110          vorbis_pump_first_frame(f);
05111          return f;
05112       }
05113    }
05114    if (error) *error = p.error;
05115    vorbis_deinit(&p);
05116    return NULL;
05117 }
05118 
05119 stb_vorbis * stb_vorbis_open_file(FILE *file, int close_on_free, int *error, const stb_vorbis_alloc *alloc)
05120 {
05121    unsigned int len, start;
05122    start = (unsigned int) ftell(file);
05123    fseek(file, 0, SEEK_END);
05124    len = (unsigned int) (ftell(file) - start);
05125    fseek(file, start, SEEK_SET);
05126    return stb_vorbis_open_file_section(file, close_on_free, error, alloc, len);
05127 }
05128 
05129 stb_vorbis * stb_vorbis_open_filename(const char *filename, int *error, const stb_vorbis_alloc *alloc)
05130 {
05131    FILE *f;
05132 #if defined(_WIN32) && defined(__STDC_WANT_SECURE_LIB__)
05133    if (0 != fopen_s(&f, filename, "rb"))
05134       f = NULL;
05135 #else
05136    f = fopen(filename, "rb");
05137 #endif
05138    if (f)
05139       return stb_vorbis_open_file(f, TRUE, error, alloc);
05140    if (error) *error = VORBIS_file_open_failure;
05141    return NULL;
05142 }
05143 #endif // STB_VORBIS_NO_STDIO
05144 
05145 #ifdef __SDL_SOUND_INTERNAL__
05146 stb_vorbis * stb_vorbis_open_rwops_section(SDL_RWops *rwops, int close_on_free, int *error, const stb_vorbis_alloc *alloc, unsigned int length)
05147 {
05148    stb_vorbis *f, p;
05149    vorbis_init(&p, alloc);
05150    p.rwops = rwops;
05151    p.rwops_start = (uint32) SDL_RWtell(rwops);
05152    p.stream_len   = length;
05153    p.close_on_free = close_on_free;
05154    if (start_decoder(&p)) {
05155       f = vorbis_alloc(&p);
05156       if (f) {
05157          memcpy(f, &p, sizeof (stb_vorbis));
05158          vorbis_pump_first_frame(f);
05159          return f;
05160       }
05161    }
05162    if (error) *error = p.error;
05163    vorbis_deinit(&p);
05164    return NULL;
05165 }
05166 
05167 stb_vorbis * stb_vorbis_open_rwops(SDL_RWops *rwops, int close_on_free, int *error, const stb_vorbis_alloc *alloc)
05168 {
05169    const unsigned int start = (unsigned int) SDL_RWtell(rwops);
05170    const unsigned int len = (unsigned int) (SDL_RWseek(rwops, 0, RW_SEEK_END) - start);
05171    SDL_RWseek(rwops, start, RW_SEEK_SET);
05172    return stb_vorbis_open_rwops_section(rwops, close_on_free, error, alloc, len);
05173 }
05174 #endif
05175 
05176 stb_vorbis * stb_vorbis_open_memory(const unsigned char *data, int len, int *error, const stb_vorbis_alloc *alloc)
05177 {
05178    stb_vorbis *f, p;
05179    if (data == NULL) return NULL;
05180    vorbis_init(&p, alloc);
05181    p.stream = (uint8 *) data;
05182    p.stream_end = (uint8 *) data + len;
05183    p.stream_start = (uint8 *) p.stream;
05184    p.stream_len = len;
05185    p.push_mode = FALSE;
05186    if (start_decoder(&p)) {
05187       f = vorbis_alloc(&p);
05188       if (f) {
05189          *f = p;
05190          vorbis_pump_first_frame(f);
05191          if (error) *error = VORBIS__no_error;
05192          return f;
05193       }
05194    }
05195    if (error) *error = (int)(p.error);
05196    vorbis_deinit(&p);
05197    return NULL;
05198 }
05199 
05200 #ifndef STB_VORBIS_NO_INTEGER_CONVERSION
05201 #define PLAYBACK_MONO     1
05202 #define PLAYBACK_LEFT     2
05203 #define PLAYBACK_RIGHT    4
05204 
05205 #define L  (PLAYBACK_LEFT  | PLAYBACK_MONO)
05206 #define C  (PLAYBACK_LEFT  | PLAYBACK_RIGHT | PLAYBACK_MONO)
05207 #define R  (PLAYBACK_RIGHT | PLAYBACK_MONO)
05208 
05209 static int8 channel_position[7][6] =
05210 {
05211    { 0 },
05212    { C },
05213    { L, R },
05214    { L, C, R },
05215    { L, R, L, R },
05216    { L, C, R, L, R },
05217    { L, C, R, L, R, C },
05218 };
05219 
05220 
05221 #ifndef STB_VORBIS_NO_FAST_SCALED_FLOAT
05222    typedef union {
05223       float f;
05224       int i;
05225    } float_conv;
05226    typedef char stb_vorbis_float_size_test[sizeof(float)==4 && sizeof(int) == 4];
05227    #define FASTDEF(x) float_conv x
05228    // add (1<<23) to convert to int, then divide by 2^SHIFT, then add 0.5/2^SHIFT to round
05229    #define MAGIC(SHIFT) (1.5f * (1 << (23-SHIFT)) + 0.5f/(1 << SHIFT))
05230    #define ADDEND(SHIFT) (((150-SHIFT) << 23) + (1 << 22))
05231    #define FAST_SCALED_FLOAT_TO_INT(temp,x,s) (temp.f = (x) + MAGIC(s), temp.i - ADDEND(s))
05232    #define check_endianness()
05233 #else
05234    #define FAST_SCALED_FLOAT_TO_INT(temp,x,s) ((int) ((x) * (1 << (s))))
05235    #define check_endianness()
05236    #define FASTDEF(x)
05237 #endif
05238 
05239 static void copy_samples(short *dest, float *src, int len)
05240 {
05241    int i;
05242    check_endianness();
05243    for (i=0; i < len; ++i) {
05244       FASTDEF(temp);
05245       int v = FAST_SCALED_FLOAT_TO_INT(temp, src[i],15);
05246       if ((unsigned int) (v + 32768) > 65535)
05247          v = v < 0 ? -32768 : 32767;
05248       dest[i] = v;
05249    }
05250 }
05251 
05252 static void compute_samples(int mask, short *output, int num_c, float **data, int d_offset, int len)
05253 {
05254    #define BUFFER_SIZE  32
05255    float buffer[BUFFER_SIZE];
05256    int i,j,o,n = BUFFER_SIZE;
05257    check_endianness();
05258    for (o = 0; o < len; o += BUFFER_SIZE) {
05259       memset(buffer, 0, sizeof(buffer));
05260       if (o + n > len) n = len - o;
05261       for (j=0; j < num_c; ++j) {
05262          if (channel_position[num_c][j] & mask) {
05263             for (i=0; i < n; ++i)
05264                buffer[i] += data[j][d_offset+o+i];
05265          }
05266       }
05267       for (i=0; i < n; ++i) {
05268          FASTDEF(temp);
05269          int v = FAST_SCALED_FLOAT_TO_INT(temp,buffer[i],15);
05270          if ((unsigned int) (v + 32768) > 65535)
05271             v = v < 0 ? -32768 : 32767;
05272          output[o+i] = v;
05273       }
05274    }
05275 }
05276 
05277 static void compute_stereo_samples(short *output, int num_c, float **data, int d_offset, int len)
05278 {
05279    #define BUFFER_SIZE  32
05280    float buffer[BUFFER_SIZE];
05281    int i,j,o,n = BUFFER_SIZE >> 1;
05282    // o is the offset in the source data
05283    check_endianness();
05284    for (o = 0; o < len; o += BUFFER_SIZE >> 1) {
05285       // o2 is the offset in the output data
05286       int o2 = o << 1;
05287       memset(buffer, 0, sizeof(buffer));
05288       if (o + n > len) n = len - o;
05289       for (j=0; j < num_c; ++j) {
05290          int m = channel_position[num_c][j] & (PLAYBACK_LEFT | PLAYBACK_RIGHT);
05291          if (m == (PLAYBACK_LEFT | PLAYBACK_RIGHT)) {
05292             for (i=0; i < n; ++i) {
05293                buffer[i*2+0] += data[j][d_offset+o+i];
05294                buffer[i*2+1] += data[j][d_offset+o+i];
05295             }
05296          } else if (m == PLAYBACK_LEFT) {
05297             for (i=0; i < n; ++i) {
05298                buffer[i*2+0] += data[j][d_offset+o+i];
05299             }
05300          } else if (m == PLAYBACK_RIGHT) {
05301             for (i=0; i < n; ++i) {
05302                buffer[i*2+1] += data[j][d_offset+o+i];
05303             }
05304          }
05305       }
05306       for (i=0; i < (n<<1); ++i) {
05307          FASTDEF(temp);
05308          int v = FAST_SCALED_FLOAT_TO_INT(temp,buffer[i],15);
05309          if ((unsigned int) (v + 32768) > 65535)
05310             v = v < 0 ? -32768 : 32767;
05311          output[o2+i] = v;
05312       }
05313    }
05314 }
05315 
05316 static void convert_samples_short(int buf_c, short **buffer, int b_offset, int data_c, float **data, int d_offset, int samples)
05317 {
05318    int i;
05319    if (buf_c != data_c && buf_c <= 2 && data_c <= 6) {
05320       static int channel_selector[3][2] = { {0}, {PLAYBACK_MONO}, {PLAYBACK_LEFT, PLAYBACK_RIGHT} };
05321       for (i=0; i < buf_c; ++i)
05322          compute_samples(channel_selector[buf_c][i], buffer[i]+b_offset, data_c, data, d_offset, samples);
05323    } else {
05324       int limit = buf_c < data_c ? buf_c : data_c;
05325       for (i=0; i < limit; ++i)
05326          copy_samples(buffer[i]+b_offset, data[i]+d_offset, samples);
05327       for (   ; i < buf_c; ++i)
05328          memset(buffer[i]+b_offset, 0, sizeof(short) * samples);
05329    }
05330 }
05331 
05332 int stb_vorbis_get_frame_short(stb_vorbis *f, int num_c, short **buffer, int num_samples)
05333 {
05334    float **output = NULL;
05335    int len = stb_vorbis_get_frame_float(f, NULL, &output);
05336    if (len > num_samples) len = num_samples;
05337    if (len)
05338       convert_samples_short(num_c, buffer, 0, f->channels, output, 0, len);
05339    return len;
05340 }
05341 
05342 static void convert_channels_short_interleaved(int buf_c, short *buffer, int data_c, float **data, int d_offset, int len)
05343 {
05344    int i;
05345    check_endianness();
05346    if (buf_c != data_c && buf_c <= 2 && data_c <= 6) {
05347       assert(buf_c == 2);
05348       for (i=0; i < buf_c; ++i)
05349          compute_stereo_samples(buffer, data_c, data, d_offset, len);
05350    } else {
05351       int limit = buf_c < data_c ? buf_c : data_c;
05352       int j;
05353       for (j=0; j < len; ++j) {
05354          for (i=0; i < limit; ++i) {
05355             FASTDEF(temp);
05356             float f = data[i][d_offset+j];
05357             int v = FAST_SCALED_FLOAT_TO_INT(temp, f,15);//data[i][d_offset+j],15);
05358             if ((unsigned int) (v + 32768) > 65535)
05359                v = v < 0 ? -32768 : 32767;
05360             *buffer++ = v;
05361          }
05362          for (   ; i < buf_c; ++i)
05363             *buffer++ = 0;
05364       }
05365    }
05366 }
05367 
05368 int stb_vorbis_get_frame_short_interleaved(stb_vorbis *f, int num_c, short *buffer, int num_shorts)
05369 {
05370    float **output;
05371    int len;
05372    if (num_c == 1) return stb_vorbis_get_frame_short(f,num_c,&buffer, num_shorts);
05373    len = stb_vorbis_get_frame_float(f, NULL, &output);
05374    if (len) {
05375       if (len*num_c > num_shorts) len = num_shorts / num_c;
05376       convert_channels_short_interleaved(num_c, buffer, f->channels, output, 0, len);
05377    }
05378    return len;
05379 }
05380 
05381 int stb_vorbis_get_samples_short_interleaved(stb_vorbis *f, int channels, short *buffer, int num_shorts)
05382 {
05383    float **outputs;
05384    int len = num_shorts / channels;
05385    int n=0;
05386    while (n < len) {
05387       int k = f->channel_buffer_end - f->channel_buffer_start;
05388       if (n+k >= len) k = len - n;
05389       if (k)
05390          convert_channels_short_interleaved(channels, buffer, f->channels, f->channel_buffers, f->channel_buffer_start, k);
05391       buffer += k*channels;
05392       n += k;
05393       f->channel_buffer_start += k;
05394       if (n == len) break;
05395       if (!stb_vorbis_get_frame_float(f, NULL, &outputs)) break;
05396    }
05397    return n;
05398 }
05399 
05400 int stb_vorbis_get_samples_short(stb_vorbis *f, int channels, short **buffer, int len)
05401 {
05402    float **outputs;
05403    int n=0;
05404    while (n < len) {
05405       int k = f->channel_buffer_end - f->channel_buffer_start;
05406       if (n+k >= len) k = len - n;
05407       if (k)
05408          convert_samples_short(channels, buffer, n, f->channels, f->channel_buffers, f->channel_buffer_start, k);
05409       n += k;
05410       f->channel_buffer_start += k;
05411       if (n == len) break;
05412       if (!stb_vorbis_get_frame_float(f, NULL, &outputs)) break;
05413    }
05414    return n;
05415 }
05416 
05417 #ifndef STB_VORBIS_NO_STDIO
05418 int stb_vorbis_decode_filename(const char *filename, int *channels, int *sample_rate, short **output)
05419 {
05420    int data_len, offset, total, limit, error;
05421    short *data;
05422    stb_vorbis *v = stb_vorbis_open_filename(filename, &error, NULL);
05423    if (v == NULL) return -1;
05424    limit = v->channels * 4096;
05425    *channels = v->channels;
05426    if (sample_rate)
05427       *sample_rate = v->sample_rate;
05428    offset = data_len = 0;
05429    total = limit;
05430    data = (short *) malloc(total * sizeof(*data));
05431    if (data == NULL) {
05432       stb_vorbis_close(v);
05433       return -2;
05434    }
05435    for (;;) {
05436       int n = stb_vorbis_get_frame_short_interleaved(v, v->channels, data+offset, total-offset);
05437       if (n == 0) break;
05438       data_len += n;
05439       offset += n * v->channels;
05440       if (offset + limit > total) {
05441          short *data2;
05442          total *= 2;
05443          data2 = (short *) realloc(data, total * sizeof(*data));
05444          if (data2 == NULL) {
05445             free(data);
05446             stb_vorbis_close(v);
05447             return -2;
05448          }
05449          data = data2;
05450       }
05451    }
05452    *output = data;
05453    stb_vorbis_close(v);
05454    return data_len;
05455 }
05456 #endif // NO_STDIO
05457 
05458 int stb_vorbis_decode_memory(const uint8 *mem, int len, int *channels, int *sample_rate, short **output)
05459 {
05460    int data_len, offset, total, limit, error;
05461    short *data;
05462    stb_vorbis *v = stb_vorbis_open_memory(mem, len, &error, NULL);
05463    if (v == NULL) return -1;
05464    limit = v->channels * 4096;
05465    *channels = v->channels;
05466    if (sample_rate)
05467       *sample_rate = v->sample_rate;
05468    offset = data_len = 0;
05469    total = limit;
05470    data = (short *) malloc(total * sizeof(*data));
05471    if (data == NULL) {
05472       stb_vorbis_close(v);
05473       return -2;
05474    }
05475    for (;;) {
05476       int n = stb_vorbis_get_frame_short_interleaved(v, v->channels, data+offset, total-offset);
05477       if (n == 0) break;
05478       data_len += n;
05479       offset += n * v->channels;
05480       if (offset + limit > total) {
05481          short *data2;
05482          total *= 2;
05483          data2 = (short *) realloc(data, total * sizeof(*data));
05484          if (data2 == NULL) {
05485             free(data);
05486             stb_vorbis_close(v);
05487             return -2;
05488          }
05489          data = data2;
05490       }
05491    }
05492    *output = data;
05493    stb_vorbis_close(v);
05494    return data_len;
05495 }
05496 #endif // STB_VORBIS_NO_INTEGER_CONVERSION
05497 
05498 int stb_vorbis_get_samples_float_interleaved(stb_vorbis *f, int channels, float *buffer, int num_floats)
05499 {
05500    float **outputs;
05501    int len = num_floats / channels;
05502    int n=0;
05503    int z = f->channels;
05504    if (z > channels) z = channels;
05505    while (n < len) {
05506       int i,j;
05507       int k = f->channel_buffer_end - f->channel_buffer_start;
05508       if (n+k >= len) k = len - n;
05509       for (j=0; j < k; ++j) {
05510          for (i=0; i < z; ++i)
05511             *buffer++ = f->channel_buffers[i][f->channel_buffer_start+j];
05512          for (   ; i < channels; ++i)
05513             *buffer++ = 0;
05514       }
05515       n += k;
05516       f->channel_buffer_start += k;
05517       if (n == len)
05518          break;
05519       if (!stb_vorbis_get_frame_float(f, NULL, &outputs))
05520          break;
05521    }
05522    return n;
05523 }
05524 
05525 int stb_vorbis_get_samples_float(stb_vorbis *f, int channels, float **buffer, int num_samples)
05526 {
05527    float **outputs;
05528    int n=0;
05529    int z = f->channels;
05530    if (z > channels) z = channels;
05531    while (n < num_samples) {
05532       int i;
05533       int k = f->channel_buffer_end - f->channel_buffer_start;
05534       if (n+k >= num_samples) k = num_samples - n;
05535       if (k) {
05536          for (i=0; i < z; ++i)
05537             memcpy(buffer[i]+n, f->channel_buffers[i]+f->channel_buffer_start, sizeof(float)*k);
05538          for (   ; i < channels; ++i)
05539             memset(buffer[i]+n, 0, sizeof(float) * k);
05540       }
05541       n += k;
05542       f->channel_buffer_start += k;
05543       if (n == num_samples)
05544          break;
05545       if (!stb_vorbis_get_frame_float(f, NULL, &outputs))
05546          break;
05547    }
05548    return n;
05549 }
05550 #endif // STB_VORBIS_NO_PULLDATA_API
05551 
05552 /* Version history
05553     1.17    - 2019-07-08 - fix CVE-2019-13217, -13218, -13219, -13220, -13221, -13222, -13223
05554                            found with Mayhem by ForAllSecure
05555     1.16    - 2019-03-04 - fix warnings
05556     1.15    - 2019-02-07 - explicit failure if Ogg Skeleton data is found
05557     1.14    - 2018-02-11 - delete bogus dealloca usage
05558     1.13    - 2018-01-29 - fix truncation of last frame (hopefully)
05559     1.12    - 2017-11-21 - limit residue begin/end to blocksize/2 to avoid large temp allocs in bad/corrupt files
05560     1.11    - 2017-07-23 - fix MinGW compilation
05561     1.10    - 2017-03-03 - more robust seeking; fix negative ilog(); clear error in open_memory
05562     1.09    - 2016-04-04 - back out 'avoid discarding last frame' fix from previous version
05563     1.08    - 2016-04-02 - fixed multiple warnings; fix setup memory leaks;
05564                            avoid discarding last frame of audio data
05565     1.07    - 2015-01-16 - fixed some warnings, fix mingw, const-correct API
05566                            some more crash fixes when out of memory or with corrupt files
05567     1.06    - 2015-08-31 - full, correct support for seeking API (Dougall Johnson)
05568                            some crash fixes when out of memory or with corrupt files
05569     1.05    - 2015-04-19 - don't define __forceinline if it's redundant
05570     1.04    - 2014-08-27 - fix missing const-correct case in API
05571     1.03    - 2014-08-07 - Warning fixes
05572     1.02    - 2014-07-09 - Declare qsort compare function _cdecl on windows
05573     1.01    - 2014-06-18 - fix stb_vorbis_get_samples_float
05574     1.0     - 2014-05-26 - fix memory leaks; fix warnings; fix bugs in multichannel
05575                            (API change) report sample rate for decode-full-file funcs
05576     0.99996 - bracket #include <malloc.h> for macintosh compilation by Laurent Gomila
05577     0.99995 - use union instead of pointer-cast for fast-float-to-int to avoid alias-optimization problem
05578     0.99994 - change fast-float-to-int to work in single-precision FPU mode, remove endian-dependence
05579     0.99993 - remove assert that fired on legal files with empty tables
05580     0.99992 - rewind-to-start
05581     0.99991 - bugfix to stb_vorbis_get_samples_short by Bernhard Wodo
05582     0.9999 - (should have been 0.99990) fix no-CRT support, compiling as C++
05583     0.9998 - add a full-decode function with a memory source
05584     0.9997 - fix a bug in the read-from-FILE case in 0.9996 addition
05585     0.9996 - query length of vorbis stream in samples/seconds
05586     0.9995 - bugfix to another optimization that only happened in certain files
05587     0.9994 - bugfix to one of the optimizations that caused significant (but inaudible?) errors
05588     0.9993 - performance improvements; runs in 99% to 104% of time of reference implementation
05589     0.9992 - performance improvement of IMDCT; now performs close to reference implementation
05590     0.9991 - performance improvement of IMDCT
05591     0.999 - (should have been 0.9990) performance improvement of IMDCT
05592     0.998 - no-CRT support from Casey Muratori
05593     0.997 - bugfixes for bugs found by Terje Mathisen
05594     0.996 - bugfix: fast-huffman decode initialized incorrectly for sparse codebooks; fixing gives 10% speedup - found by Terje Mathisen
05595     0.995 - bugfix: fix to 'effective' overrun detection - found by Terje Mathisen
05596     0.994 - bugfix: garbage decode on final VQ symbol of a non-multiple - found by Terje Mathisen
05597     0.993 - bugfix: pushdata API required 1 extra byte for empty page (failed to consume final page if empty) - found by Terje Mathisen
05598     0.992 - fixes for MinGW warning
05599     0.991 - turn fast-float-conversion on by default
05600     0.990 - fix push-mode seek recovery if you seek into the headers
05601     0.98b - fix to bad release of 0.98
05602     0.98 - fix push-mode seek recovery; robustify float-to-int and support non-fast mode
05603     0.97 - builds under c++ (typecasting, don't use 'class' keyword)
05604     0.96 - somehow MY 0.95 was right, but the web one was wrong, so here's my 0.95 rereleased as 0.96, fixes a typo in the clamping code
05605     0.95 - clamping code for 16-bit functions
05606     0.94 - not publically released
05607     0.93 - fixed all-zero-floor case (was decoding garbage)
05608     0.92 - fixed a memory leak
05609     0.91 - conditional compiles to omit parts of the API and the infrastructure to support them: STB_VORBIS_NO_PULLDATA_API, STB_VORBIS_NO_PUSHDATA_API, STB_VORBIS_NO_STDIO, STB_VORBIS_NO_INTEGER_CONVERSION
05610     0.90 - first public release
05611 */
05612 
05613 #endif // STB_VORBIS_HEADER_ONLY
05614 
05615 
05616 /*
05617 ------------------------------------------------------------------------------
05618 This software is available under 2 licenses -- choose whichever you prefer.
05619 ------------------------------------------------------------------------------
05620 ALTERNATIVE A - MIT License
05621 Copyright (c) 2017 Sean Barrett
05622 Permission is hereby granted, free of charge, to any person obtaining a copy of
05623 this software and associated documentation files (the "Software"), to deal in
05624 the Software without restriction, including without limitation the rights to
05625 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
05626 of the Software, and to permit persons to whom the Software is furnished to do
05627 so, subject to the following conditions:
05628 The above copyright notice and this permission notice shall be included in all
05629 copies or substantial portions of the Software.
05630 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
05631 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
05632 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
05633 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
05634 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
05635 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
05636 SOFTWARE.
05637 ------------------------------------------------------------------------------
05638 ALTERNATIVE B - Public Domain (www.unlicense.org)
05639 This is free and unencumbered software released into the public domain.
05640 Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
05641 software, either in source code form or as a compiled binary, for any purpose,
05642 commercial or non-commercial, and by any means.
05643 In jurisdictions that recognize copyright laws, the author or authors of this
05644 software dedicate any and all copyright interest in the software to the public
05645 domain. We make this dedication for the benefit of the public at large and to
05646 the detriment of our heirs and successors. We intend this dedication to be an
05647 overt act of relinquishment in perpetuity of all present and future rights to
05648 this software under copyright law.
05649 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
05650 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
05651 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
05652 AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
05653 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
05654 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
05655 ------------------------------------------------------------------------------
05656 */