Code Coverage Report for src/decode/seek.c

1 /*

2 * libnogg: a decoder library for Ogg Vorbis streams

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

	Hit	Total	Coverage
Lines:	315	315	100.0%
Branches:	1962	1962	100.0%

80 (18/18) while (!handle->eof) {

81

82 /* See if we have the first byte of an Ogg page. */

83 const uint8_t byte = get8(handle);

84 (18/18) 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 (18/18) 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 (54/54) if (header[1] == 'g' && header[2] == 'g' && header[3] == 'S'

99 (18/18) && 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 (18/18) for (int i = 22; i < 26; i++) {

105 header[i] = 0;

106 }

107 uint32_t crc = 0;

108 (18/18) for (int i = 0; i < 27; i++) {

109 crc = crc32_update(crc, header[i]);

110 }

111 unsigned int len = 0;

112 (18/18) if (!getn(handle, readbuf, header[26])) {

113 break;

114 }

115 (18/18) for (int i = 0; i < header[26]; i++) {

116 const unsigned int seglen = readbuf[i];

117 crc = crc32_update(crc, seglen);

118 len += seglen;

119 }

120 (18/18) while (len > 0) {

121 const unsigned int readcount = min(len, sizeof(readbuf));

122 (18/18) if (!getn(handle, readbuf, readcount)) {

123 ASSERT(handle->eof);

124 break;

125 }

126 (18/18) for (unsigned int i = 0; i < readcount; i++) {

127 crc = crc32_update(crc, readbuf[i]);

128 }

129 len -= readcount;

130 }

131 (18/18) if (handle->eof) {

132 break;

133 }

134

135 (18/18) if (crc == expected_crc) {

136 /* We found a valid page! */

137 (18/18) if (end_ret) {

138 *end_ret = get_file_offset(handle);

139 }

140 (18/18) if (last_ret) {

141 *last_ret = ((header[5] & 0x04) != 0);

142 }

143 set_file_offset(handle, page_start);

144 return true;

145 }

146 }

147

148 /* It wasn't a valid page, so seek back to the byte after the

149 * first one we tested and try again. */

150 set_file_offset(handle, page_start + 1);

151

152 } // while (!handle->eof)

153

154 return false;

155 }

156

157 /*-----------------------------------------------------------------------*/

158

159 /**

160 * test_page: Check whether the given pointer points to the beginning of

161 * a valid Ogg page, and return its length if so. The data buffer is

162 * assumed to start with the "OggS" capture pattern and a version byte of

163 * zero.

164 *

165 * The data at ptr is destroyed whether the page is valid or not.

166 *

167 * [Parameters]

168 * ptr: Pointer to data to check.

169 * size: Amount of valid data at ptr, in bytes.

170 * [Return value]

171 * Ogg page length in bytes if the page is valid, otherwise 0.

172 */

173 static unsigned int test_page(uint8_t *ptr, unsigned int size)

174 {

175 ASSERT(ptr != NULL);

176 ASSERT(size >= 27);

177 ASSERT(ptr[0] == 'O');

178 ASSERT(ptr[1] == 'g');

179 ASSERT(ptr[2] == 'g');

180 ASSERT(ptr[3] == 'S');

181 ASSERT(ptr[4] == 0);

182

183 unsigned int len = 27 + ptr[26];

184 (18/18) if (size < len) {

185 return 0; // Buffer too small for segment length list.

186 }

187 (18/18) for (int i = 0; i < ptr[26]; i++) {

188 len += ptr[27+i];

189 }

190 (18/18) if (size < len) {

191 return 0; // Buffer too small for page data.

192 }

193

194 const uint32_t expected_crc = extract_32(&ptr[22]);

195 (18/18) for (int i = 22; i < 26; i++) {

196 ptr[i] = 0;

197 }

198 uint32_t crc = 0;

199 (18/18) for (unsigned int i = 0; i < len; i++) {

200 crc = crc32_update(crc, ptr[i]);

201 }

202 (18/18) if (crc == expected_crc) {

203 return len;

204 } else {

205 return 0;

206 }

207 }

208

209 /*-----------------------------------------------------------------------*/

210

211 /**

212 * analyze_page: Scan an Ogg page starting at the current read position

213 * to determine the page's file and sample offset bounds. The page header

214 * is assumed to be valid.

215 *

216 * [Parameters]

217 * handle: Stream handle.

218 * page_ret: Pointer to variable to receive the page data.

219 * [Return value]

220 * True on success, false on error.

221 */

222 static int analyze_page(stb_vorbis *handle, ProbedPage *page_ret)

223 {

224 /* The page start position is easy. */

225 page_ret->page_start = get_file_offset(handle);

226

227 /* Parse the header to determine the page length. */

228 uint8_t header[27], lacing[255];

229 (18/18) if (!getn(handle, header, 27)) {

230 goto bail;

231 }

232 const int num_segments = header[26];

233 (18/18) if (!getn(handle, lacing, num_segments)) {

234 goto bail;

235 }

236 unsigned int payload_len = 0;

237 (18/18) for (int i = 0; i < num_segments; i++) {

238 payload_len += lacing[i];

239 }

240 page_ret->page_end = page_ret->page_start + 27 + num_segments + payload_len;

241

242 /* The header contains the sample offset of the end of the page.

243 * If this value is -1, there are no complete packets (i.e., frames)

244 * on the page. (The end sample offset points to the middle of the

245 * window, but if the last frame of the page is a long block and the

246 * first one on the next page is a short one, the frame contains data

247 * beyond that point. We don't worry about that here because we may

248 * not be able to do anything about it, such as if the long block is

249 * the only frame on the page.) */

250 page_ret->last_decoded_sample = extract_64(&header[6]);

251 (18/18) if (page_ret->last_decoded_sample == (uint64_t)-1) {

252 page_ret->first_decoded_sample = -1;

253 goto done;

254 }

255

256 /* The header does _not_ contain the sample offset of the beginning of

257 * the page, so we have to go through ridiculous contortions to figure

258 * it out ourselves, if it's even possible for the page in question.

259 * Presumably the Ogg format developers thought it so important to save

260 * an extra 64 bits per page that they didn't care about the impact on

261 * decoder implementations. */

262

263 /* On the last page of a stream, the end sample position is overloaded

264 * to also declare the true length of the final frame (to allow for a

265 * stream length of an arbitrary number of samples). This means we

266 * have no way to work out the first sample on the page. Sigh deeply

267 * and give up. */

268 (18/18) if (header[5] & 4) {

269 page_ret->first_decoded_sample = page_ret->last_decoded_sample;

270 goto done;

271 }

272

273 /* Scan the page to find the number of (complete) frames and the type

274 * of each one. */

275 bool frame_long[255];

276 int num_frames = 0;

277 bool last_packet_was_audio = false;

278 bool packet_start = !(header[5] & PAGEFLAG_continued_packet);

279 const int mode_bits = handle->mode_bits;

280 (18/18) for (int i = 0; i < num_segments; i++) {

281 (18/18) if (packet_start) {

282 last_packet_was_audio = false;

283 (18/18) if (UNLIKELY(lacing[i] == 0)) {

284 continue;

285 }

286 const uint8_t packet_header = get8(handle);

287 const int mode = (packet_header >> 1) & ((1 << mode_bits) - 1);

288 (18/18) if (UNLIKELY(packet_header & 0x01) // Not an audio packet.

289 (18/18) || UNLIKELY(mode >= handle->mode_count)) {

290 skip(handle, lacing[i] - 1);

291 } else {

292 last_packet_was_audio = true;

293 frame_long[num_frames] = handle->mode_config[mode].blockflag;

294 skip(handle, lacing[i] - 1);

295 num_frames++;

296 }

297 } else {

298 skip(handle, lacing[i]);

299 }

300 packet_start = (lacing[i] < 255);

301 }

302 (18/18) if (UNLIKELY(num_frames == 0)) {

303 /* The page claimed to have an end sample position, but there were

304 * no frames that completed on the page. This can never occur for

305 * a well-formed stream. */

306 page_ret->first_decoded_sample = -1;

307 page_ret->last_decoded_sample = -1;

308 goto done;

309 }

310 (36/36) if (!packet_start && last_packet_was_audio) {

311 /* The last packet is incomplete, so ignore that frame. */

312 num_frames--;

313 }

314 (18/18) if (num_frames == 0) {

315 /* The page did not contain any complete frames, so we can't use

316 * it as a seek anchor. Unlike the case above, this case can occur

317 * in a legal stream (though it's probably unlikely in real-life

318 * streams, since the reference encoder uses a target page size of

319 * 4k while Vorbis packets seem to be rarely longer than 1k). */

320 page_ret->first_decoded_sample = -1;

321 page_ret->last_decoded_sample = -1;

322 goto done;

323 }

324

325 /* Count backwards from the end of the page to find the beginning

326 * sample offset of the first fully-decoded sample on this page (this

327 * is the beginning of the _second_ frame, since the first frame will

328 * overlap with the last frame of the previous page). */

329 uint64_t sample_pos = page_ret->last_decoded_sample;

330 (18/18) for (int i = num_frames-1; i >= 1; i--) {

331 sample_pos -= (handle->blocksize[frame_long[i]] / 4

332 + handle->blocksize[frame_long[i-1]] / 4);

333 }

334 page_ret->first_decoded_sample = sample_pos;

335

336 done:

337 set_file_offset(handle, page_ret->page_start);

338 return true;

339

340 /* Error conditions come down here. */

341 bail:

342 set_file_offset(handle, page_ret->page_start);

343 return false;

344 }

345

346 /*-----------------------------------------------------------------------*/

347

348 /**

349 * scan_frame: Find the next valid frame and return its window parameters.

350 * Helper function for seek_frame_from_page().

351 *

352 * [Parameters]

353 * handle: Stream handle.

354 * left_start_ret, left_end_ret, right_start_ret, mode_index_ret:

355 * Pointers to variables to receive the frame's window parameters.

356 * [Return value]

357 * True on success, false on error.

358 */

359 static bool scan_frame(stb_vorbis *handle, int *left_start_ret,

360 int *left_end_ret, int *right_start_ret,

361 int *mode_index_ret)

362 {

363 bool decode_ok;

364 do {

365 int right_end;

366 decode_ok = vorbis_decode_initial(handle, left_start_ret, left_end_ret,

367 right_start_ret, &right_end,

368 mode_index_ret);

369 (18/18) if (!flush_packet(handle)

370 (18/18) || (!decode_ok

371 (18/18) && handle->error != VORBIS_invalid_packet

372 (18/18) && handle->error != VORBIS_continued_packet_flag_invalid

373 (18/18) && handle->error != VORBIS_wrong_page_number)) {

374 return false;

375 }

376 (18/18) } while (!decode_ok);

377 return true;

378 }

379

380 /*-----------------------------------------------------------------------*/

381

382 /**

383 * seek_frame_from_page: Seek to the frame containing the given target

384 * sample by scanning forward from the page beginning at the given offset.

385 *

386 * [Parameters]

387 * handle: Stream handle.

388 * page_start: File offset of the beginning of the page.

389 * first_sample: Sample offset of the middle of the first complete

390 * frame on the page.

391 * target_sample: Sample to seek to. Must be no less than first_sample.

392 * [Return value]

393 * Number of samples that must be discarded from the beginning of the

394 * frame to reach the target sample.

395 */

396 static int seek_frame_from_page(stb_vorbis *handle, int64_t page_start,

397 uint64_t first_sample, uint64_t target_sample)

398 {

399 ASSERT(target_sample >= first_sample);

400

401 /* Reset the read position to the beginning of the page's first

402 * complete frame. */

403 set_file_offset(handle, page_start);

404 (18/18) if (UNLIKELY(!start_page(handle, false))) {

405 return error(handle, VORBIS_seek_failed);

406 }

407 (18/18) if (handle->page_flag & PAGEFLAG_continued_packet) {

408 ASSERT(start_packet(handle));

409 (18/18) if (UNLIKELY(!flush_packet(handle))) {

410 return error(handle, VORBIS_seek_failed);

411 }

412 }

413

414 int left_start, left_end, right_start;

415

416 /* Scan the first frame to get its window parameters, and shift

417 * first_sample so it points at the first sample returned from that

418 * frame. */

419 {

420 int mode_index;

421 (18/18) if (!scan_frame(handle, &left_start, &left_end, &right_start,

422 &mode_index)) {

423 return error(handle, VORBIS_seek_failed);

424 }

425 const Mode *mode = &handle->mode_config[mode_index];

426 /* The frame we just scanned will give fully decoded samples in

427 * the window range [left_start,right_start). However, if it's the

428 * very first frame in the file, we need to skip the left half of

429 * the window. */

430 (18/18) if (first_sample == 0) {

431 left_start = left_end = handle->blocksize[mode->blockflag] / 2;

432 }

433 first_sample -= (handle->blocksize[mode->blockflag] / 2) - left_start;

434 }

435

436 /* Find the frame which, when decoded, will generate the target sample.

437 * (This will not necessarily be in the same page, but we only use the

438 * passed-in page data as an anchor, so that's not a problem.) */

439 int frame = 0; // Offset from the first complete frame.

440 /* frame_start is the position of the first fully decoded sample in

441 * frame number 'frame'. */

442 uint64_t frame_start = first_sample;

443 (18/18) while (target_sample >= frame_start + (right_start - left_start)) {

444 frame++;

445 frame_start += right_start - left_start;

446 int mode_index;

447 (18/18) if (!scan_frame(handle, &left_start, &left_end, &right_start,

448 &mode_index)) {

449 return error(handle, VORBIS_seek_failed);

450 }

451 }

452

453 /* Determine where we need to start decoding in order to get the

454 * desired sample. */

455 int frames_to_skip;

456 bool decode_one_frame;

457 (18/18) if (target_sample >= frame_start + (left_end - left_start)) {

458 /* In this case, the sample is outside the overlapped window

459 * segments and doesn't require the previous frame to decode.

460 * This can only happen in a long frame preceded or followed by a

461 * short frame. */

462 frames_to_skip = frame;

463 decode_one_frame = false;

464 } else {

465 /* The sample is in the overlapped portion of the window, so we'll

466 * need to decode the previous frame first. */

467 ASSERT(frame > 0); // Guaranteed by function precondition.

468 frames_to_skip = frame - 1;

469 decode_one_frame = true;

470 }

471

472 /* Set up the stream state so the next decode call returns the frame

473 * containing the target sample, and return the offset of that sample

474 * within the frame. */

475 set_file_offset(handle, page_start);

476 (18/18) if (UNLIKELY(!start_page(handle, false))) {

477 return error(handle, VORBIS_seek_failed);

478 }

479 (18/18) if (handle->page_flag & PAGEFLAG_continued_packet) {

480 ASSERT(start_packet(handle));

481 (18/18) if (!flush_packet(handle)) {

482 return error(handle, VORBIS_seek_failed);

483 }

484 }

485 (18/18) for (int i = 0; i < frames_to_skip; i++) {

486 (18/18) if (UNLIKELY(!start_packet(handle))

487 (18/18) || UNLIKELY(!flush_packet(handle))) {

488 return error(handle, VORBIS_seek_failed);

489 }

490 }

491 handle->previous_length = 0;

492 (36/36) handle->first_decode = (first_sample == 0 && frames_to_skip == 0);

493 (18/18) if (decode_one_frame) {

494 (18/18) if (UNLIKELY(!vorbis_decode_packet(handle, NULL))) {

495 return error(handle, VORBIS_seek_failed);

496 }

497 }

498 handle->current_loc = frame_start;

499 handle->current_loc_valid = true;

500 handle->error = VORBIS__no_error;

501 return (int)(target_sample - frame_start);

502 }

503

504 /*************************************************************************/

505 /************************** Interface routines ***************************/

506 /*************************************************************************/

507

508 int stb_vorbis_seek(stb_vorbis *handle, uint64_t sample_number)

509 {

510 /* Fail early for unseekable streams. */

511 (18/18) if (handle->stream_len < 0) {

512 return error(handle, VORBIS_cant_find_last_page);

513 }

514

515 /* Find the first and last pages if they have not yet been looked up. */

516 (18/18) if (handle->p_first.page_end == 0) {

517 ASSERT(handle->first_decode);

518 (18/18) if (UNLIKELY(!start_packet(handle))) {

519 return error(handle, VORBIS_cant_find_last_page);

520 }

521 flush_packet(handle);

522 handle->first_decode = false;

523 }

524 (18/18) if (handle->p_last.page_start == 0) {

525 (void) stb_vorbis_stream_length_in_samples(handle);

526 (18/18) if (handle->total_samples == (uint64_t)-1) {

527 return 0;

528 }

529 }

530

531 /* If we're seeking to/past the end of the stream, just do that. */

532 (18/18) if (sample_number >= handle->total_samples) {

533 set_file_offset(handle, handle->stream_len);

534 reset_page(handle);

535 handle->current_loc = handle->total_samples;

536 handle->current_loc_valid = true;

537 return 0;

538 }

539

540 /* If the sample is known to be on the first page, we don't need to

541 * search for the correct page. */

542 (18/18) if (sample_number < handle->p_first.last_decoded_sample) {

543 return seek_frame_from_page(handle, handle->p_first.page_start,

544 0, sample_number);

545 }

546

547 /* Otherwise, perform an interpolated binary search (biased toward

548 * where we expect the page to be located) for the page containing

549 * the target sample. */

550 ProbedPage low = handle->p_first;

551 ProbedPage high = handle->p_last;

552 /* Conceptually, we iterate until low.page_end and high.page_start

553 * are equal, indicating that they represent two consecutive pages.

554 * However, if there's junk data between the two pages, the two

555 * positions will never converge, so instead we use

556 * high.after_previous_page_start, which is guaranteed to (eventually)

557 * fall somewhere in the low page if the two pages are consecutive. */

558 (18/18) while (low.page_end < high.after_previous_page_start) {

559 /* Bounds for the search. We use low.page_start+1 instead of

560 * low.page_end as the lower bound to bias the search toward the

561 * beginning of the stream, since find_page() scans forward. */

562 const int64_t low_offset = low.page_start + 1;

563 const int64_t high_offset = high.after_previous_page_start - 1;

564 const uint64_t low_sample = low.last_decoded_sample;

565 const uint64_t high_sample = high.first_decoded_sample;

566 /* These assertions express the search loop invariant that the

567 * target sample is located strictly between the low and high

568 * bound pages. */

569 ASSERT(low_sample <= sample_number);

570 ASSERT(sample_number < high_sample);

571

572 /* Pick a probe point for the next iteration. As we get closer to

573 * the target, we reduce the amount of bias, since there may be up

574 * to a page's worth of variance in the relative positions of the

575 * low and high bounds within their respective pages. */

576 float lerp_frac = ((float)(sample_number - low_sample)

577 / (float)(high_sample - low_sample));

578 (18/18) if (high_offset - low_offset < 8192) {

579 lerp_frac = 0.5f;

580 (18/18) } else if (high_offset - low_offset < 65536) {

581 lerp_frac = 0.25f + lerp_frac*0.5f;

582 }

583 const int64_t probe = low_offset

584 + (int64_t)floorf(lerp_frac * (float)(high_offset - low_offset));

585

586 /* Look for the next page starting after the probe point. If it's

587 * a page without a known sample position, continue scanning forward

588 * and use the sample position from the next page that has one. */

589 set_file_offset(handle, probe);

590 ProbedPage page;

591 /* These calls can only fail on a read error. */

592 (18/18) if (UNLIKELY(!find_page(handle, NULL, NULL))

593 (18/18) || UNLIKELY(!analyze_page(handle, &page))) {

594 return error(handle, VORBIS_seek_failed);

595 }

596 (18/18) while (page.first_decoded_sample == (uint64_t)-1) {

597 set_file_offset(handle, page.page_end);

598 (18/18) if (UNLIKELY(!find_page(handle, NULL, NULL))

599 (18/18) || UNLIKELY(!analyze_page(handle, &page))) {

600 return error(handle, VORBIS_seek_failed);

601 }

602 }

603 page.after_previous_page_start = probe;

604

605 /* Choose one or the other side of the range and iterate (unless

606 * we happened to find the right page, in which case we just stop). */

607 (18/18) if (sample_number >= page.first_decoded_sample) {

608 (18/18) if (sample_number < page.last_decoded_sample) {

609 return seek_frame_from_page(handle, page.page_start,

610 page.first_decoded_sample,

611 sample_number);

612 } else {

613 low = page;

614 }

615 } else {

616 high = page;

617 }

618 }

619

620 return seek_frame_from_page(handle, low.page_start,

621 low.first_decoded_sample, sample_number);

622 }

623

624 /*-----------------------------------------------------------------------*/

625

626 uint64_t stb_vorbis_stream_length_in_samples(stb_vorbis *handle)

627 {

628 (18/18) if (!handle->total_samples) {

629 /* Fail early for unseekable streams. */

630 (18/18) if (handle->stream_len < 0) {

631 handle->total_samples = -1;

632 return error(handle, VORBIS_cant_find_last_page);

633 }

634

635 /* Save the current file position so we can restore it when done. */

636 const int64_t restore_offset = get_file_offset(handle);

637

638 const int64_t first_page_start = handle->p_first.page_start;

639

640 /*

641 * We need to find the last Ogg page in the file. An Ogg page can

642 * have up to 255*255 bytes of data, but typical sizes are in the

643 * 4k-8k range; we don't want to waste time scanning through 64k

644 * of data if we don't have to. So we make the assumptions that

645 * (A) the last page of the stream is less than 8k long and (B) the

646 * capture pattern ("OggS") is unlikely to occur within the last

647 * page of the stream, and we use the following algorithm:

648 *

649 * 1) Read the last 8k of the stream (or the entire stream if

650 * it is less than 8k long).

651 *

652 * 2a) Starting from a position 4k from the end of the stream,

653 * scan backward until we find an occurrence of the capture

654 * pattern or reach the beginning of the data read in step 1.

655 *

656 * 2b) If no capture pattern was found in step 2a, start from

657 * the same position and search forward instead.

658 *

659 * 2c) If no capture pattern was found in step 2b, fall back to

660 * a linear search of the last 64k of the stream.

661 *

662 * 3) Check whether the capture pattern starts a new page.

663 *

664 * 4a) If it does, continue scanning pages after the end of that

665 * page until the end of the stream is reached.

666 *

667 * 4b) Otherwise, fall back to a linear search of the last 64k of

668 * the stream.

669 */

670 const int64_t stream_len = handle->stream_len - first_page_start;

671 int64_t in_prev_page;

672 (18/18) if (stream_len >= 65536) {

673 in_prev_page = handle->stream_len - 65536;

674 } else {

675 in_prev_page = first_page_start;

676 }

677 int64_t last_page_loc = -1;

678 int64_t page_end = -1;

679 bool last;

680

681 uint8_t search_buf[8192];

682 const int search_bufsize = sizeof(search_buf);

683 (18/18) if (stream_len > search_bufsize) {

684 const int64_t search_start = handle->stream_len - search_bufsize;

685 set_file_offset(handle, search_start);

686 (18/18) if (getn(handle, search_buf, search_bufsize)) {

687 int capture_offset = -1;

688 (18/18) for (int i = search_bufsize/2-1; i >= 0; i--) {

689 (36/36) if (search_buf[i ]=='O' && search_buf[i+1]=='g'

690 (36/36) && search_buf[i+2]=='g' && search_buf[i+3]=='S'

691 (18/18) && search_buf[i+4]==0) {

692 capture_offset = i;

693 break;

694 }

695 }

696 (18/18) if (capture_offset < 0) {

697 (18/18) for (int i = search_bufsize/2; i < search_bufsize-27; i++) {

698 (36/36) if (search_buf[i ]=='O' && search_buf[i+1]=='g'

699 (36/36) && search_buf[i+2]=='g' && search_buf[i+3]=='S'

700 (18/18) && search_buf[i+4]==0) {

701 capture_offset = i;

702 break;

703 }

704 }

705 }

706 (18/18) if (capture_offset >= 0) {

707 int page_len =

708 test_page(search_buf + capture_offset,

709 sizeof(search_buf) - capture_offset);

710 (18/18) if (page_len > 0) {

711 last_page_loc = search_start + capture_offset;

712 in_prev_page = last_page_loc+1;

713 page_end = last_page_loc + page_len;

714 last = ((search_buf[capture_offset+5] & 0x04) != 0);

715 }

716 }

717 }

718 }

719

720 (18/18) if (last_page_loc < 0) {

721 /* The optimistic search failed or was skipped. Fall back to

722 * a linear search of the last 64k of the stream. */

723 set_file_offset(handle, in_prev_page);

724 /* Check that we can actually find a page there. */

725 (18/18) if (!find_page(handle, &page_end, &last)) {

726 handle->total_samples = -1;

727 goto done;

728 }

729 last_page_loc = get_file_offset(handle);

730 }

731

732 /* Look for subsequent pages. */

733 (18/18) if (in_prev_page == last_page_loc

734 (18/18) && in_prev_page > first_page_start) {

735 /* We happened to start exactly at a page boundary, so back up

736 * one byte for the "in previous page" location. */

737 in_prev_page--;

738 }

739 (18/18) while (!last) {

740 set_file_offset(handle, page_end);

741 (18/18) if (!find_page(handle, &page_end, &last)) {

742 /* The last page didn't have the "last page" flag set.

743 * This probably means the file is truncated, but we go

744 * on anyway. */

745 break;

746 }

747 in_prev_page = last_page_loc+1;

748 last_page_loc = get_file_offset(handle);

749 }

750

751 /* Get the sample offset at the end of the last page. */

752 set_file_offset(handle, last_page_loc+6);

753 uint8_t buf[8];

754 (18/18) if (UNLIKELY(!getn(handle, buf, 8))) {

755 goto done;

756 }

757 handle->total_samples = extract_64(buf);

758 (18/18) if (handle->total_samples == (uint64_t)-1) {

759 /* Oops, the last page didn't have a sample offset! */

760 goto done;

761 }

762

763 handle->p_last.page_start = last_page_loc;

764 handle->p_last.page_end = page_end;

765 handle->p_last.first_decoded_sample = handle->total_samples;

766 handle->p_last.last_decoded_sample = handle->total_samples;

767 handle->p_last.after_previous_page_start = in_prev_page;

768

769 done:

770 set_file_offset(handle, restore_offset);

771 } // if (!handle->total_samples)

772

773 (18/18) if (handle->total_samples == (uint64_t)-1) {

774 return error(handle, VORBIS_cant_find_last_page);

775 } else {

776 return handle->total_samples;

777 }

778 }

779

780 /*************************************************************************/

781 /*************************************************************************/