[DVDnav-discuss] [PATCH] "dvdnav_jump_to_sector" as an alternative to "dvdnav_time_search" (Overview: Source to follow)
gnosygnu
gnosygnu at gmail.com
Sun Nov 6 03:30:13 CET 2011
Hi all. I've written a patch for jumping to a time in searching.c. I
emailed something similar to this group a year ago, but there didn't
seem to be much interest then. I am emailing again because there is
some revived interest in the VLC community. (See
http://forum.videolan.org/viewtopic.php?f=32&t=76308&start=20#p315221)
Currently, dvdnav_time_search is marked "FIXME: right now, this
function does not use the time tables but interpolates only the cell
times". This method is usually inaccurate: it interpolates using
sectors, but one sector does not equal one fixed unit of time. For
example, if there is a 10:00 cell and the cell is 1000 sectors long,
it assumes that 5:00 is at sector 500. Jumping to sector 500 may
actually jump instead to 5:12.
My patch jumps to a time using the time map and the vobu address map.
I placed it in a new function called "dvdnav_jump_to_sector" because I
wanted to keep backward compatibility with the existing
"dvdnav_time_search" -- in case anyone wanted to keep using this
method. I provide more details on my approach below. I will include
the patch itself in the next email.
Please note that most of my work is based on reverse-engineering the
IFO files. I am not a DVD application developer, so my approach may be
flawed or may not follow DVD specification.
Also, please note that Java/C# is my primary language. I learned C for
this task, and have not used it for anything else since then. My
apologies in advance if I do something terribly stupid.
Finally, please note that my patch does not change or delete any
existing code. However, it does add a lot of code: 650+ lines. I
realize that such length makes it harder and less desirable to review.
I do think the approach needs to have this complexity, especially to
handle some outlier DVDs I've encountered.
I appreciate any feedback or review. At the very least, I hope others
will find this useful.
Thanks.
-------
Details
-------
My patch introduces a new function called "dvdnav_jump_to_sector". It
finds a sector for a given time and jumps to it.
In libdvdnav/src/dvdnav/dvdnav.h, it adds 1 line. (see dvdnav.h.patch)
In libdvdnav/src/searching.c, it adds 650+ lines. (see searching.c.patch.zip)
No other lines are modified or deleted.
>From a broad perspective, it works like this:
(1) Find the two time map entries around a given time
(2) Get the vobus of these two time map entries
(3) Get the sector of the jump_time through interpolation of the vobus
For clarity's sake, I will repeat the above with fabricated data
(1) Find the two time map entries around a given time
Given time 56...
Time map index 10 is identified as 55 seconds
56 seconds must be between entries 10 and 11
(2) Get the vobus of these two time map entries
Time entry 10 is at sector 193 which is vobu 405
Time entry 11 is at sector 303 which is vobu 455
(3) Get the sector of the jump_time through interpolation of the vobus
56 is 20% of the way between 55 and 60
415 is 20% of the way between 405 and 455
320 is the corresponding sector of vobu 415
Note that step (1) actually requires more sub-steps
(1a) Find the cell for a given time
(1b) Find the tmap entries around the cell's start sector
(1c) Find the vobus for these tmap entries and cell start
(1d) Interpolate the time of earlier tmap entry
(1e) Find the tmap entries around jump_time
(2) Get the vobus of these two time map entries
(3) Get the sector of the jump_time through interpolation of the vobus
Again, here is the above with some fabricated data.
I try to represent the tables visually below. It was written with a
fixed-width font.
My apologies if it does not show up formatted in the email.
(1a) Find the cell for a given time
Given time 56...
---- -------- -------- ---------- ----------
cell bgn_time end_time bgn_sector end_sector
---- -------- -------- ---------- ----------
1 0 28 0 99
---> 2 29 600 100 1000
3 601 900 1001 1400
...
**** Cell 2 encloses 56.
(1b) Find the tmap entries around the cell's start sector
---- ------
tmap sector
---- ------
...
3 71
---> 4 88
---> 5 108
6 121
...
**** tmap entries 4 and 5 enclose cell start sector of 100.
(1c) Find the vobus for these tmap entries and cell start
---- ------
vobu sector
---- ------
...
---> 200 88
...
---> 208 100
209 102
---> 210 108
...
**** 200, 208 and 210 are the relevant vobus
(1d) Interpolate the time of earlier tmap entry
208 is 80% of the way between 200 and 210
4 secs is 80% of 5 secs
25 is the time-point when subtracting 4 from 29 (cell_bgn)
vobu 200 is at 25 seconds
**** 25 secs is the calculated time of tmap idx 4
(1e) Find the tmap entries around jump_time
---- ---- ------
tmap time sector
---- ---- ------
4 25
5 30
6 35
7 40
8 45
9 50
---> 10 55 193
---> 11 60 303
...
**** 56 must be between tmap entries 10 and 11
(2) Get the vobus of these two time map entries
---- ------
vobu sector
---- ------
...
---> 405 193
...
415 320
...
---> 455 503
...
**** 405 and 445 are the relevant vobus
(3) Get the sector of the jump_time through interpolation of the vobus
56 is 20% of the way between 55 and 60
415 is 20% of the way between 405 and 455
320 is the corresponding sector of vobu 415
**** 320 is the closest vobu sector for 56 secs
-----------
Other notes
-----------
(1b) has a hack to handle cells that start at discontinuity entries
- Basically if a cell starts in a discontinuity entry, then the
sector/vobu data may not be good for interpolation
For example, using the same data above
---- ---- ------ ----
tmap time sector vobu
---- ---- ------ ----
4 25 88 200 <- flagged with discontinuity bit
5 30 108 210
6 35 140 218
Since there is a discontinuity occurring at tmap entry 4, the
sectors between 88 and 108 may not represent 5 seconds of data (It
usually does, but not always)
To handle this, the proc looks forward to the next tmap entry and
uses the vobu difference there to infer the vobu of the lo tmap
With data, this means
Look at tmap entry 6. It has a vobu of 218
There are 8 vobus between 218 and 210
Assume that tmap entry 10 starts at 202 (not 200)
This works in practice on a handful of DVDs I've encountered, but
the logic will probably not hold for all.
There is a small percentage of DVDs that have issues
- Time map was missing (no entries)
For these DVDs, I wrote dvdnav_find_vobu_by_cell_boundaries. This
function uses the same logic as tmap, but uses the cell_boundaries
only. It is not as accurate as a tmap, but it is close. It is more
accurate than raw sector interpolation. Roughly speaking, it is
accurate 50% of the time, and the other other 50% of the time, it is
off by 1 to 3 seconds.
- Time map has non-consecutive entries. For example, a DVD with a
time interval of 5 seconds had entries at tmap index 99 that was not
500 seconds in playback, but 521 seconds (or some other non-intuitive
number).
For these DVDs, steps (1a) - (1d) were written. If we could assume
that tmap index 99 was always at time 500 seconds, then we could skip
directly to (1e).
----------------
Function summary
----------------
Entry function:
- dvdnav_jump_to_sector_by_time
Find the nearest vobu and jump to it
Core function:
- dvdnav_find_vobu_by_tmap
Find the nearest vobu by using the tmap
Fallback function:
- dvdnav_find_vobu_by_cell_boundaries
Find the nearest vobu by using the cell boundaries
Utility functions:
- dvdnav_tmap_get_entries_for_sector
Find the tmap entries on either side of a given sector
- dvdnav_tmap_calc_time_for_tmap_entry
Given two tmap entries and a known time, calc the time for the lo tmap entry
- dvdnav_admap_interpolate_vobu
Given two sectors and a fraction, calc the corresponding vobu
- dvdnav_cell_find
Given a sector/time/idx find the cell that encloses it
- dvdnav_tmap_search
Do binary search for the earlier tmap entry near find_sector
- dvdnav_admap_search
Do a binary search for earlier admap index near find_sector
- dvdnav_tmap_get_entry
Get a sector from a tmap
Misc functions (separated for readability):
- dvdnav_tmap_get
Get a tmap, tmap_len and tmap_interval
- dvdnav_admap_get
Get an admap and admap_len
Log/Debug functions
- is_null
Check if pointer is null, and log it if it is
More information about the DVDnav-discuss
mailing list