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