Code Coverage Report for src/decode/seek.c


Hit Total Coverage
Lines: 312 312 100.0%
Branches: 414 428 96.7%

1 /*
2 * libnogg: a decoder library for Ogg Vorbis streams
3 * Copyright (c) 2014-2019 Andrew Church <achurch@achurch.org>
4 *
5 * This software may be copied and redistributed under certain conditions;
6 * see the file "COPYING" in the source code distribution for details.
7 * NO WARRANTY is provided with this software.
8 */
9
10 #include "include/nogg.h"
11 #include "src/common.h"
12 #include "src/decode/common.h"
13 #include "src/decode/crc32.h"
14 #include "src/decode/decode.h"
15 #include "src/decode/inlines.h"
16 #include "src/decode/io.h"
17 #include "src/decode/packet.h"
18 #include "src/util/memory.h"
19
20 #include <math.h>
21 #include <stdlib.h>
22 #include <string.h>
23
24 /*************************************************************************/
25 /**************************** Helper routines ****************************/
26 /*************************************************************************/
27
28 /**
29 * set_file_offset: Set the stream read position to the given offset from
30 * the beginning of the stream. If the stream is not seekable, this
31 * function does nothing.
32 *
33 * [Parameters]
34 * handle: Stream handle.
35 * offset: New stream read position, in bytes from the beginning of
36 * the stream.
37 */
38 static void set_file_offset(stb_vorbis *handle, int64_t offset)
39 {
40 handle->eof = false;
41 (*handle->seek_callback)(handle->opaque, offset);
42 }
43
44 /*-----------------------------------------------------------------------*/
45
46 /**
47 * get_file_offset: Return the current stream read position.
48 *
49 * [Parameters]
50 * handle: Stream handle.
51 * [Return value]
52 * Current stream read position, in bytes from the beginning of the
53 * stream, or 0 if the stream is not seekable.
54 */
55 static int64_t get_file_offset(stb_vorbis *handle)
56 {
57 return (*handle->tell_callback)(handle->opaque);
58 }
59
60 /*-----------------------------------------------------------------------*/
61
62 /**
63 * find_page: Locate the first page starting at or after the current read
64 * position in the stream. On success, the stream read position is set to
65 * the start of the page.
66 *
67 * [Parameters]
68 * handle: Stream handle.
69 * end_ret: Pointer to variable to receive the file offset of one byte
70 * past the end of the page. May be NULL if not needed.
71 * last_ret: Pointer to variable to receive the "last page" flag of
72 * the page. May be NULL if not needed.
73 * [Return value]
74 * True if a page was found, false if not.
75 */
76 static bool find_page(stb_vorbis *handle, int64_t *end_ret, bool *last_ret)
77 {
78 uint8_t readbuf[4096];
79
80 (4/4) while (!handle->eof) {
81
82 /* See if we have the first byte of an Ogg page. */
83 const uint8_t byte = get8(handle);
84 (4/4) if (byte != 'O') {
85 continue;
86 }
87
88 /* Read in the rest of the (possible) page header. */
89 const int64_t page_start = get_file_offset(handle) - 1;
90 uint8_t header[27];
91 header[0] = byte;
92 (4/4) if (!getn(handle, &header[1], sizeof(header)-1)) {
93 break;
94 }
95
96 /* See if this really is an Ogg page (as opposed to a random 'O'
97 * byte in the middle of audio data). */
98 (12/12) if (header[1] == 'g' && header[2] == 'g' && header[3] == 'S'
99 (4/4) && header[4] == 0 /*Ogg version*/) {
100
101 /* Check the page CRC to make the final determination of whether
102 * this is a valid page. */
103 const uint32_t expected_crc = extract_32(&header[22]);
104 (4/4) for (int i = 22; i < 26; i++) {
105 header[i] = 0;
106 }
107 uint32_t crc = 0;
108 (4/4) for (int i = 0; i < 27; i++) {
109 crc = crc32_update(crc, header[i]);
110 }
111 unsigned int len = 0;
112 getn(handle, readbuf, header[26]);
113 (4/4) for (int i = 0; i < header[26]; i++) {
114 const unsigned int seglen = readbuf[i];
115 crc = crc32_update(crc, seglen);
116 len += seglen;
117 }
118 (4/4) while (len > 0) {
119 const unsigned int readcount = min(len, sizeof(readbuf));
120 getn(handle, readbuf, readcount);
121 (4/4) for (unsigned int i = 0; i < readcount; i++) {
122 crc = crc32_update(crc, readbuf[i]);
123 }
124 len -= readcount;
125 }
126 (4/4) if (handle->eof) {
127 break;
128 }
129
130 (4/4) if (crc == expected_crc) {
131 /* We found a valid page! */
132 (4/4) if (end_ret) {
133 *end_ret = get_file_offset(handle);
134 }
135 (4/4) if (last_ret) {
136 *last_ret = ((header[5] & 0x04) != 0);
137 }
138 set_file_offset(handle, page_start);
139 return true;
140 }
141 }
142
143 /* It wasn't a valid page, so seek back to the byte after the
144 * first one we tested and try again. */
145 set_file_offset(handle, page_start + 1);
146
147 } // while (!handle->eof)
148
149 return false;
150 }
151
152 /*-----------------------------------------------------------------------*/
153
154 /**
155 * test_page: Check whether the given pointer points to the beginning of
156 * a valid Ogg page, and return its length if so. The data buffer is
157 * assumed to start with the "OggS" capture pattern and a version byte of
158 * zero.
159 *
160 * The data at ptr is destroyed whether the page is valid or not.
161 *
162 * [Parameters]
163 * ptr: Pointer to data to check.
164 * size: Amount of valid data at ptr, in bytes.
165 * [Return value]
166 * Ogg page length in bytes if the page is valid, otherwise 0.
167 */
168 static unsigned int test_page(uint8_t *ptr, unsigned int size)
169 {
170 ASSERT(ptr != NULL);
171 ASSERT(size >= 27);
172 ASSERT(ptr[0] == 'O');
173 ASSERT(ptr[1] == 'g');
174 ASSERT(ptr[2] == 'g');
175 ASSERT(ptr[3] == 'S');
176 ASSERT(ptr[4] == 0);
177
178 unsigned int len = 27 + ptr[26];
179 (4/4) if (size < len) {
180 return 0; // Buffer too small for segment length list.
181 }
182 (4/4) for (int i = 0; i < ptr[26]; i++) {
183 len += ptr[27+i];
184 }
185 (4/4) if (size < len) {
186 return 0; // Buffer too small for page data.
187 }
188
189 const uint32_t expected_crc = extract_32(&ptr[22]);
190 (4/4) for (int i = 22; i < 26; i++) {
191 ptr[i] = 0;
192 }
193 uint32_t crc = 0;
194 (4/4) for (unsigned int i = 0; i < len; i++) {
195 crc = crc32_update(crc, ptr[i]);
196 }
197 (4/4) if (crc == expected_crc) {
198 return len;
199 } else {
200 return 0;
201 }
202 }
203
204 /*-----------------------------------------------------------------------*/
205
206 /**
207 * analyze_page: Scan an Ogg page starting at the current read position
208 * to determine the page's file and sample offset bounds. The page header
209 * is assumed to be valid.
210 *
211 * [Parameters]
212 * handle: Stream handle.
213 * page_ret: Pointer to variable to receive the page data.
214 * [Return value]
215 * True on success, false on error.
216 */
217 static int analyze_page(stb_vorbis *handle, ProbedPage *page_ret)
218 {
219 /* The page start position is easy. */
220 page_ret->page_start = get_file_offset(handle);
221
222 /* Parse the header to determine the page length. */
223 uint8_t header[27], lacing[255];
224 (4/4) if (!getn(handle, header, 27)) {
225 goto bail;
226 }
227 const int num_segments = header[26];
228 (4/4) if (!getn(handle, lacing, num_segments)) {
229 goto bail;
230 }
231 unsigned int payload_len = 0;
232 (4/4) for (int i = 0; i < num_segments; i++) {
233 payload_len += lacing[i];
234 }
235 page_ret->page_end = page_ret->page_start + 27 + num_segments + payload_len;
236
237 /* The header contains the sample offset of the end of the page.
238 * If this value is -1, there are no complete packets (i.e., frames)
239 * on the page. (The end sample offset points to the middle of the
240 * window, but if the last frame of the page is a long block and the
241 * first one on the next page is a short one, the frame contains data
242 * beyond that point. We don't worry about that here because we may
243 * not be able to do anything about it, such as if the long block is
244 * the only frame on the page.) */
245 page_ret->last_decoded_sample = extract_64(&header[6]);
246 (4/4) if (page_ret->last_decoded_sample == (uint64_t)-1) {
247 page_ret->first_decoded_sample = -1;
248 goto done;
249 }
250
251 /* The header does _not_ contain the sample offset of the beginning of
252 * the page, so we have to go through ridiculous contortions to figure
253 * it out ourselves, if it's even possible for the page in question.
254 * Presumably the Ogg format developers thought it so important to save
255 * an extra 64 bits per page that they didn't care about the impact on
256 * decoder implementations. */
257
258 /* On the last page of a stream, the end sample position is overloaded
259 * to also declare the true length of the final frame (to allow for a
260 * stream length of an arbitrary number of samples). This means we
261 * have no way to work out the first sample on the page. Sigh deeply
262 * and give up. */
263 (4/4) if (header[5] & 4) {
264 page_ret->first_decoded_sample = page_ret->last_decoded_sample;
265 goto done;
266 }
267
268 /* Scan the page to find the number of (complete) frames and the type
269 * of each one. */
270 bool frame_long[255];
271 int num_frames = 0;
272 bool last_packet_was_audio = false;
273 bool packet_start = !(header[5] & PAGEFLAG_continued_packet);
274 const int mode_bits = handle->mode_bits;
275 (4/4) for (int i = 0; i < num_segments; i++) {
276 (4/4) if (packet_start) {
277 last_packet_was_audio = false;
278 (4/4) if (UNLIKELY(lacing[i] == 0)) {
279 continue;
280 }
281 const uint8_t packet_header = get8(handle);
282 const int mode = (packet_header >> 1) & ((1 << mode_bits) - 1);
283 (4/4) if (UNLIKELY(packet_header & 0x01) // Not an audio packet.
284 (4/4) || UNLIKELY(mode >= handle->mode_count)) {
285 skip(handle, lacing[i] - 1);
286 } else {
287 last_packet_was_audio = true;
288 frame_long[num_frames] = handle->mode_config[mode].blockflag;
289 skip(handle, lacing[i] - 1);
290 num_frames++;
291 }
292 } else {
293 skip(handle, lacing[i]);
294 }
295 packet_start = (lacing[i] < 255);
296 }
297 (4/4) if (UNLIKELY(num_frames == 0)) {
298 /* The page claimed to have an end sample position, but there were
299 * no frames that completed on the page. This can never occur for
300 * a well-formed stream. */
301 page_ret->first_decoded_sample = -1;
302 page_ret->last_decoded_sample = -1;
303 goto done;
304 }
305 (8/8) if (!packet_start && last_packet_was_audio) {
306 /* The last packet is incomplete, so ignore that frame. */
307 num_frames--;
308 }
309 (4/4) if (num_frames == 0) {
310 /* The page did not contain any complete frames, so we can't use
311 * it as a seek anchor. Unlike the case above, this case can occur
312 * in a legal stream (though it's probably unlikely in real-life
313 * streams, since the reference encoder uses a target page size of
314 * 4k while Vorbis packets seem to be rarely longer than 1k). */
315 page_ret->first_decoded_sample = -1;
316 page_ret->last_decoded_sample = -1;
317 goto done;
318 }
319
320 /* Count backwards from the end of the page to find the beginning
321 * sample offset of the first fully-decoded sample on this page (this
322 * is the beginning of the _second_ frame, since the first frame will
323 * overlap with the last frame of the previous page). */
324 uint64_t sample_pos = page_ret->last_decoded_sample;
325 (4/4) for (int i = num_frames-1; i >= 1; i--) {
326 sample_pos -= (handle->blocksize[frame_long[i]] / 4
327 + handle->blocksize[frame_long[i-1]] / 4);
328 }
329 page_ret->first_decoded_sample = sample_pos;
330
331 done:
332 set_file_offset(handle, page_ret->page_start);
333 return true;
334
335 /* Error conditions come down here. */
336 bail:
337 set_file_offset(handle, page_ret->page_start);
338 return false;
339 }
340
341 /*-----------------------------------------------------------------------*/
342
343 /**
344 * scan_frame: Find the next valid frame and return its window parameters.
345 * Helper function for seek_frame_from_page().
346 *
347 * [Parameters]
348 * handle: Stream handle.
349 * left_start_ret, left_end_ret, right_start_ret, mode_index_ret:
350 * Pointers to variables to receive the frame's window parameters.
351 * [Return value]
352 * True on success, false on error.
353 */
354 static bool scan_frame(stb_vorbis *handle, int *left_start_ret,
355 int *left_end_ret, int *right_start_ret,
356 int *mode_index_ret)
357 {
358 bool decode_ok;
359 do {
360 int right_end;
361 decode_ok = vorbis_decode_initial(handle, left_start_ret, left_end_ret,
362 right_start_ret, &right_end,
363 mode_index_ret);
364 (4/4) if (!flush_packet(handle)
365 (4/4) || (!decode_ok
366 (4/4) && handle->error != VORBIS_invalid_packet
367 (4/4) && handle->error != VORBIS_continued_packet_flag_invalid
368 (4/4) && handle->error != VORBIS_wrong_page_number)) {
369 return false;
370 }
371 (4/4) } while (!decode_ok);
372 return true;
373 }
374
375 /*-----------------------------------------------------------------------*/
376
377 /**
378 * seek_frame_from_page: Seek to the frame containing the given target
379 * sample by scanning forward from the page beginning at the given offset.
380 *
381 * [Parameters]
382 * handle: Stream handle.
383 * page_start: File offset of the beginning of the page.
384 * first_sample: Sample offset of the middle of the first complete
385 * frame on the page.
386 * target_sample: Sample to seek to. Must be no less than first_sample.
387 * [Return value]
388 * Number of samples that must be discarded from the beginning of the
389 * frame to reach the target sample.
390 */
391 static int seek_frame_from_page(stb_vorbis *handle, int64_t page_start,
392 uint64_t first_sample, uint64_t target_sample)
393 {
394 ASSERT(target_sample >= first_sample);
395
396 /* Reset the read position to the beginning of the page's first
397 * complete frame. */
398 set_file_offset(handle, page_start);
399 (4/4) if (UNLIKELY(!start_page(handle, false))) {
400 return error(handle, VORBIS_seek_failed);
401 }
402 (4/4) if (handle->page_flag & PAGEFLAG_continued_packet) {
403 ASSERT(start_packet(handle));
404 (4/4) if (UNLIKELY(!flush_packet(handle))) {
405 return error(handle, VORBIS_seek_failed);
406 }
407 }
408
409 int left_start, left_end, right_start;
410
411 /* Scan the first frame to get its window parameters, and shift
412 * first_sample so it points at the first sample returned from that
413 * frame. */
414 {
415 int mode_index;
416 (4/4) if (!scan_frame(handle, &left_start, &left_end, &right_start,
417 &mode_index)) {
418 return error(handle, VORBIS_seek_failed);
419 }
420 const Mode *mode = &handle->mode_config[mode_index];
421 /* The frame we just scanned will give fully decoded samples in
422 * the window range [left_start,right_start). However, if it's the
423 * very first frame in the file, we need to skip the left half of
424 * the window. */
425 (4/4) if (first_sample == 0) {
426 left_start = left_end = handle->blocksize[mode->blockflag] / 2;
427 }
428 first_sample -= (handle->blocksize[mode->blockflag] / 2) - left_start;
429 }
430
431 /* Find the frame which, when decoded, will generate the target sample.
432 * (This will not necessarily be in the same page, but we only use the
433 * passed-in page data as an anchor, so that's not a problem.) */
434 int frame = 0; // Offset from the first complete frame.
435 /* frame_start is the position of the first fully decoded sample in
436 * frame number 'frame'. */
437 uint64_t frame_start = first_sample;
438 (4/4) while (target_sample >= frame_start + (right_start - left_start)) {
439 frame++;
440 frame_start += right_start - left_start;
441 int mode_index;
442 (4/4) if (!scan_frame(handle, &left_start, &left_end, &right_start,
443 &mode_index)) {
444 return error(handle, VORBIS_seek_failed);
445 }
446 }
447
448 /* Determine where we need to start decoding in order to get the
449 * desired sample. */
450 int frames_to_skip;
451 bool decode_one_frame;
452 (4/4) if (target_sample >= frame_start + (left_end - left_start)) {
453 /* In this case, the sample is outside the overlapped window
454 * segments and doesn't require the previous frame to decode.
455 * This can only happen in a long frame preceded or followed by a
456 * short frame. */
457 frames_to_skip = frame;
458 decode_one_frame = false;
459 } else {
460 /* The sample is in the overlapped portion of the window, so we'll
461 * need to decode the previous frame first. */
462 ASSERT(frame > 0); // Guaranteed by function precondition.
463 frames_to_skip = frame - 1;
464 decode_one_frame = true;
465 }
466
467 /* Set up the stream state so the next decode call returns the frame
468 * containing the target sample, and return the offset of that sample
469 * within the frame. */
470 set_file_offset(handle, page_start);
471 (4/4) if (UNLIKELY(!start_page(handle, false))) {
472 return error(handle, VORBIS_seek_failed);
473 }
474 (4/4) if (handle->page_flag & PAGEFLAG_continued_packet) {
475 ASSERT(start_packet(handle));
476 (4/4) if (!flush_packet(handle)) {
477 return error(handle, VORBIS_seek_failed);
478 }
479 }
480 (4/4) for (int i = 0; i < frames_to_skip; i++) {
481 (4/4) if (UNLIKELY(!start_packet(handle))
482 (4/4) || UNLIKELY(!flush_packet(handle))) {
483 return error(handle, VORBIS_seek_failed);
484 }
485 }
486 handle->previous_length = 0;
487 (8/8) handle->first_decode = (first_sample == 0 && frames_to_skip == 0);
488 (4/4) if (decode_one_frame) {
489 (4/4) if (UNLIKELY(!vorbis_decode_packet(handle, NULL))) {
490 return error(handle, VORBIS_seek_failed);
491 }
492 }
493 handle->current_loc = frame_start;
494 handle->current_loc_valid = true;
495 handle->error = VORBIS__no_error;
496 return (int)(target_sample - frame_start);
497 }
498
499 /*************************************************************************/
500 /************************** Interface routines ***************************/
501 /*************************************************************************/
502
503 int stb_vorbis_seek(stb_vorbis *handle, uint64_t sample_number)
504 {
505 /* Fail early for unseekable streams. */
506 (4/4) if (handle->stream_len < 0) {
507 return error(handle, VORBIS_cant_find_last_page);
508 }
509
510 /* Find the first and last pages if they have not yet been looked up. */
511 (4/4) if (handle->p_first.page_end == 0) {
512 ASSERT(handle->first_decode);
513 (4/4) if (UNLIKELY(!start_packet(handle))) {
514 return error(handle, VORBIS_cant_find_last_page);
515 }
516 flush_packet(handle);
517 handle->first_decode = false;
518 }
519 (4/4) if (handle->p_last.page_start == 0) {
520 (void) stb_vorbis_stream_length_in_samples(handle);
521 (4/4) if (handle->total_samples == (uint64_t)-1) {
522 return 0;
523 }
524 }
525
526 /* If we're seeking to/past the end of the stream, just do that. */
527 (4/4) if (sample_number >= handle->total_samples) {
528 set_file_offset(handle, handle->stream_len);
529 reset_page(handle);
530 handle->current_loc = handle->total_samples;
531 handle->current_loc_valid = true;
532 return 0;
533 }
534
535 /* If the sample is known to be on the first page, we don't need to
536 * search for the correct page. */
537 (4/4) if (sample_number < handle->p_first.last_decoded_sample) {
538 return seek_frame_from_page(handle, handle->p_first.page_start,
539 0, sample_number);
540 }
541
542 /* Otherwise, perform an interpolated binary search (biased toward
543 * where we expect the page to be located) for the page containing
544 * the target sample. */
545 ProbedPage low = handle->p_first;
546 ProbedPage high = handle->p_last;
547 /* Conceptually, we iterate until low.page_end and high.page_start
548 * are equal, indicating that they represent two consecutive pages.
549 * However, if there's junk data between the two pages, the two
550 * positions will never converge, so instead we use
551 * high.after_previous_page_start, which is guaranteed to (eventually)
552 * fall somewhere in the low page if the two pages are consecutive. */
553 (4/4) while (low.page_end < high.after_previous_page_start) {
554 /* Bounds for the search. We use low.page_start+1 instead of
555 * low.page_end as the lower bound to bias the search toward the
556 * beginning of the stream, since find_page() scans forward. */
557 const int64_t low_offset = low.page_start + 1;
558 const int64_t high_offset = high.after_previous_page_start - 1;
559 const uint64_t low_sample = low.last_decoded_sample;
560 const uint64_t high_sample = high.first_decoded_sample;
561 /* These assertions express the search loop invariant that the
562 * target sample is located strictly between the low and high
563 * bound pages. */
564 ASSERT(low_sample <= sample_number);
565 ASSERT(sample_number < high_sample);
566
567 /* Pick a probe point for the next iteration. As we get closer to
568 * the target, we reduce the amount of bias, since there may be up
569 * to a page's worth of variance in the relative positions of the
570 * low and high bounds within their respective pages. */
571 float lerp_frac = ((float)(sample_number - low_sample)
572 / (float)(high_sample - low_sample));
573 (4/4) if (high_offset - low_offset < 8192) {
574 lerp_frac = 0.5f;
575 (4/4) } else if (high_offset - low_offset < 65536) {
576 lerp_frac = 0.25f + lerp_frac*0.5f;
577 }
578 const int64_t probe = low_offset
579 + (int64_t)floorf(lerp_frac * (float)(high_offset - low_offset));
580
581 /* Look for the next page starting after the probe point. If it's
582 * a page without a known sample position, continue scanning forward
583 * and use the sample position from the next page that has one. */
584 set_file_offset(handle, probe);
585 ProbedPage page;
586 /* These calls can only fail on a read error. */
587 (4/4) if (UNLIKELY(!find_page(handle, NULL, NULL))
588 (4/4) || UNLIKELY(!analyze_page(handle, &page))) {
589 return error(handle, VORBIS_seek_failed);
590 }
591 (4/4) while (page.first_decoded_sample == (uint64_t)-1) {
592 set_file_offset(handle, page.page_end);
593 (4/4) if (UNLIKELY(!find_page(handle, NULL, NULL))
594 (4/4) || UNLIKELY(!analyze_page(handle, &page))) {
595 return error(handle, VORBIS_seek_failed);
596 }
597 }
598 page.after_previous_page_start = probe;
599
600 /* Choose one or the other side of the range and iterate (unless
601 * we happened to find the right page, in which case we just stop). */
602 (4/4) if (sample_number >= page.first_decoded_sample) {
603 (4/4) if (sample_number < page.last_decoded_sample) {
604 return seek_frame_from_page(handle, page.page_start,
605 page.first_decoded_sample,
606 sample_number);
607 } else {
608 low = page;
609 }
610 } else {
611 high = page;
612 }
613 }
614
615 return seek_frame_from_page(handle, low.page_start,
616 low.first_decoded_sample, sample_number);
617 }
618
619 /*-----------------------------------------------------------------------*/
620
621 uint64_t stb_vorbis_stream_length_in_samples(stb_vorbis *handle)
622 {
623 (4/4) if (!handle->total_samples) {
624 /* Fail early for unseekable streams. */
625 (4/4) if (handle->stream_len < 0) {
626 handle->total_samples = -1;
627 return error(handle, VORBIS_cant_find_last_page);
628 }
629
630 /* Save the current file position so we can restore it when done. */
631 const int64_t restore_offset = get_file_offset(handle);
632
633 const int64_t first_page_start = handle->p_first.page_start;
634
635 /*
636 * We need to find the last Ogg page in the file. An Ogg page can
637 * have up to 255*255 bytes of data; for simplicity, but typical
638 * sizes are in the 4k-8k range; we don't want to waste time
639 * scanning through 64k of data if we don't have to. So we make
640 * the assumptions that (A) the last page of the stream is less
641 * than 8k long and (B) the capture pattern ("OggS") is unlikely
642 * to occur within the last page of the stream and use the
643 * following algorithm:
644 *
645 * 1) Read the last 8k of the stream (or the entire stream if
646 * it is less than 8k long).
647 *
648 * 2a) Starting from a position 4k from the end of the stream,
649 * scan backward until we find an occurrence of the capture
650 * pattern or reach the beginning of the data read in step 1.
651 *
652 * 2b) If no capture pattern was found in step 2a, start from
653 * the same position and search forward instead.
654 *
655 * 2c) If no capture pattern was found in step 2b, fall back to
656 * a linear search of the last 64k of the stream.
657 *
658 * 3) Check whether the capture pattern starts a new page.
659 *
660 * 4a) If it does, continue scanning pages after the end of that
661 * page until the end of the stream is reached.
662 *
663 * 4b) Otherwise, fall back to a linear search of the last 64k of
664 * the stream.
665 */
666 const int64_t stream_len = handle->stream_len - first_page_start;
667 int64_t in_prev_page;
668 (4/4) if (stream_len >= 65536) {
669 in_prev_page = handle->stream_len - 65536;
670 } else {
671 in_prev_page = first_page_start;
672 }
673 int64_t last_page_loc = -1;
674 int64_t page_end = -1;
675 bool last;
676
677 uint8_t search_buf[8192];
678 const int search_bufsize = sizeof(search_buf);
679 (4/4) if (stream_len > search_bufsize) {
680 const int64_t search_start = handle->stream_len - search_bufsize;
681 set_file_offset(handle, search_start);
682 (4/4) if (getn(handle, search_buf, search_bufsize)) {
683 int capture_offset = -1;
684 (4/4) for (int i = search_bufsize/2-1; i >= 0; i--) {
685 (8/8) if (search_buf[i ]=='O' && search_buf[i+1]=='g'
686 (4/8) && search_buf[i+2]=='g' && search_buf[i+3]=='S'
687 (2/4) && search_buf[i+4]==0) {
688 capture_offset = i;
689 break;
690 }
691 }
692 (4/4) if (capture_offset < 0) {
693 (4/4) for (int i = search_bufsize/2; i < search_bufsize-27; i++) {
694 (6/8) if (search_buf[i ]=='O' && search_buf[i+1]=='g'
695 (4/8) && search_buf[i+2]=='g' && search_buf[i+3]=='S'
696 (2/4) && search_buf[i+4]==0) {
697 capture_offset = i;
698 break;
699 }
700 }
701 }
702 (4/4) if (capture_offset >= 0) {
703 int page_len =
704 test_page(search_buf + capture_offset,
705 sizeof(search_buf) - capture_offset);
706 (4/4) if (page_len > 0) {
707 last_page_loc = search_start + capture_offset;
708 in_prev_page = last_page_loc+1;
709 page_end = last_page_loc + page_len;
710 last = ((search_buf[capture_offset+5] & 0x04) != 0);
711 }
712 }
713 }
714 }
715
716 (4/4) if (last_page_loc < 0) {
717 /* The optimistic search failed or was skipped. Fall back to
718 * a linear search of the last 64k of the stream. */
719 set_file_offset(handle, in_prev_page);
720 /* Check that we can actually find a page there. */
721 (4/4) if (!find_page(handle, &page_end, &last)) {
722 handle->total_samples = -1;
723 goto done;
724 }
725 last_page_loc = get_file_offset(handle);
726 }
727
728 /* Look for subsequent pages. */
729 (4/4) if (in_prev_page == last_page_loc
730 (4/4) && in_prev_page > first_page_start) {
731 /* We happened to start exactly at a page boundary, so back up
732 * one byte for the "in previous page" location. */
733 in_prev_page--;
734 }
735 (4/4) while (!last) {
736 set_file_offset(handle, page_end);
737 (4/4) if (!find_page(handle, &page_end, &last)) {
738 /* The last page didn't have the "last page" flag set.
739 * This probably means the file is truncated, but we go
740 * on anyway. */
741 break;
742 }
743 in_prev_page = last_page_loc+1;
744 last_page_loc = get_file_offset(handle);
745 }
746
747 /* Get the sample offset at the end of the last page. */
748 set_file_offset(handle, last_page_loc+6);
749 uint8_t buf[8];
750 (4/4) if (UNLIKELY(!getn(handle, buf, 8))) {
751 goto done;
752 }
753 handle->total_samples = extract_64(buf);
754 (4/4) if (handle->total_samples == (uint64_t)-1) {
755 /* Oops, the last page didn't have a sample offset! */
756 goto done;
757 }
758
759 handle->p_last.page_start = last_page_loc;
760 handle->p_last.page_end = page_end;
761 handle->p_last.first_decoded_sample = handle->total_samples;
762 handle->p_last.last_decoded_sample = handle->total_samples;
763 handle->p_last.after_previous_page_start = in_prev_page;
764
765 done:
766 set_file_offset(handle, restore_offset);
767 } // if (!handle->total_samples)
768
769 (4/4) if (handle->total_samples == (uint64_t)-1) {
770 return error(handle, VORBIS_cant_find_last_page);
771 } else {
772 return handle->total_samples;
773 }
774 }
775
776 /*************************************************************************/
777 /*************************************************************************/