WO2004012037A2

WO2004012037A2 - On-the-fly mpeg trick mode processing

Info

Publication number: WO2004012037A2
Application number: PCT/US2003/022604
Authority: WO
Inventors: Khoi Hoang; Hans Wang; Jih-Shan Wang
Original assignee: Prediwave Corporation
Priority date: 2002-07-26
Filing date: 2003-07-18
Publication date: 2004-02-05
Also published as: WO2004012037A3; AU2003256624A1; AU2003256624A8; CN1496120A

Abstract

A method and apparatus for managing data for display, the method comprisnig using a dual ring buffer cache (258 and 262) for generating index on-the-fly for location of each element in the data.

Description

ON-THE_FLY MPEG TRICK MODE PROCESSING

RELATED APPLICATIONS AND CROSS REFERENCES

This application incorporates by reference the following patent applications: SYSTEM AND METHODS FOR PROVIDING VIDEO ON DEMAND

SERVICES FOR BROADCASTING SYSTEMS filed on May 31, 2000, bearing application number 09/548, 832;

METHODS FOR PROVIDING VIDEO ON DEMAND filed on November 10,

2000, bearing application number 09/709,948; UNIVERSAL DIGITAL BROADCAST SYSTEM AND METHODS filed on

April 24, 2001, bearing application number 09/841,792;

UNIVERSAL STB ARCHITECTURES AND CONTROL METHODS filed on

May 30, 2001, bearing application number 09/870,879.

FIELD OF THE INVENTION

This invention relates to MPEG-2 data and, more specifically, to managing MPEG-2 data for display for a video-on-demand system. BACKGROUND OF THE INVENTION Typically, a customer of video on demand services who is watching a video in association with a set-top box, for example, often wishes to rewind, fast forward, play in slow motion, etc., the video that the customer is watching. In order to accomplish rewinding, fast forwarding, etc., indexes are created for locating the start and end points of picture elements within the MPEG-2 data file that is associated with the video. Once the index is available, it is a simple procedure to extract the desired picture frames based on the index. The extracted picture elements are then sent to the MPEG-2 decoder for decoding.

Typically, indexes of picture frames for a given MPEG-2 data file are generated ahead of time and stored in a separate index file. The separate index file can be sent to the set-top box at the same time that the MPEG-2 data is sent to the set-top box. Thus, in such an approach, the MPEG-2 data is said to be "pre-indexed." However, pre-indexing only works for MPEG-2 data that is sent sequentially to the set-top box and not for nonsequential MPEG-2 data. Further, pre-indexing is not appropriate for repeating MPEG-2 data. Repeating MPEG-2 data occurs when MPEG-2 is sent by a remote server to the set- top box in order to compensate for data corruption or data loss.

Based on the foregoing, there is a need for a method or mechanism for generating indexes on-the-fly in association with MPEG-2 data that is sent in a non-sequential fashion to the set-top box.

SUMMARY OF THE INVENTION

The present invention comprises, in one aspect, a method for managing data for ' display, the method comprising using a dual ring buffer cache for generating a indexes on-the-fly for the locations of each element in the data.

In other aspects, the invention encompasses a computer apparatus, a computer readable medium configured to carry out the foregoing steps. BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

FIG. 1 is a block diagram that illustrates a high-level overview of a VOD system; FIG. 2 A is a block diagram that illustrates the hardware architecture of a set top box that can be used to implement the invention; FIG. 2B is a flowchart that illustrates a high-level overview of an operation for satisfying any given trick mode command from a customer;

FIG. 3 is a block diagram that illustrates a ready-for-indexing data file that is divided into chunks of MPEG-2 data that are of arbitrary fixed size;

FIG. 4 is a diagram that illustrates a dual-ring structure of a buffer cache that can be used in certain embodiments of the invention; and

FIG. 5 is a flowchart that illustrates some of the computer-implemented acts performed by an on-the-fly-indexer.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT A method and system are described for on-the-fly MPEG trick mode processing.

In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

FUNCTIONAL AND OPERATIONAL OVERVIEW In the context of video-on-demand (VOD) services, a remote VOD server sends data such as MPEG-2 data to a set-top box that is associated with a requester who is requesting the VOD services. The requester who is requesting the VOD services is herein referred to as the "customer". FIG. 1 is a block diagram that illustrates a high-level overview of a VOD system. In system 100 of FIG. 1, VOD server 102 communicates ^■ with set-top box 104. Typically, VOD server 102 communicates with set-top box 104 via a network such as cable or satellite (not shown in FIG. 1).

For purposes of explanation, certain embodiments are described in the context of MPEG-2 data. The scope of the invention includes other types of data. For example, the embodiments apply, without limitation, to any digital data, and other types of MPEG data, etc. According to certain embodiments of the invention, FIG. 2 A is a block diagram that illustrates the hardware architecture of a set top box that can be used to implement the invention. The set top box 200 comprises a quadrature amplitude modulation (QAM) demodulator 202, a central processing unit (CPU) 204, a local memory 208, a buffer cache 210, a decoder 212 having video and audio decoding capabilities, a graphics overlay module 214, a user interface 218, a communications link 220, and a fast data bus 222. The CPU 204 controls overall operation of the set top box 200 in order to select data in response to a customer's request, decode selected data, decompress decoded data, reassemble decoded data, store decoded data in local memory 208 or the buffer cache 210, and deliver the stored data to decoder 212. In an exemplary embodiment, local memory 208 comprises non-volatile memory (e.g. a hard drive) and the buffer cache comprises volatile memory.

According to certain embodiments, the QAM demodulator 202 comprises transmitter and receiver modules and one or more of the following: 1) privacy encryption decryption module, 2) forward error correction decoder/encoder, 3) tuner control, 4) downstream and upstream processors, and 5) CPU and memory interface circuits. QAM demodulator 202 receives modulated intermediate frequency (IF) signals, samples and demodulates the signals to restore data. In an exemplary embodiment, when access is granted, decoder 212 decodes at least one data block to transform the data block into images displayable on an output screen. Specifically, video decoder 212a transforms the video portion of the data block into displayable images. Audio decoder 212b transforms the audio portion of the data block into audible sound. Decoder 212 supports commands from a customer that is subscribing to the VOD services. Examples of such commands are play, stop, pause, step, rewind, fast forward, etc. Decoder 212 provides decoded data to output device 224 for use by the customer. Output device 224 may be any suitable device such as a television, computer, any appropriate display monitor, a VCR, etc. The graphics overlay module 214 enhances displayed graphics quality by, for example, providing alpha blending or picture-in-picture capabilities.

User interface 218 enables the user control, i.e., control by the customer, of the set-top box 200. User interface 218 may be any suitable device such as a remote control device, a keyboard, a smart card, etc. Communications link 220 provides an additional communications connection.

Communications link 220 may be operatively coupled to another computer, or communications link 220 may be used to implement bi-directional communication.

Data bus 222 may be a commercially available "fast" data bus that is suitable for performing data communications in a real time manner. Suitable examples of data buses are PCI, etc.

According to certain embodiments of the invention, commands from a customer, such as fast forward, rewind, slow motion, single step, etc., can be satisfied in an efficient manner by method 250 of FIG. 2B. For the purpose of explanation, the mode of operation of the set top box for satisfying a command, such as fast forward, rewind, slow motion, single step, etc., is herein referred to as "trick mode." Likewise, commands such as fast forward, rewind, slow motion, single step, etc., are herein referred to as a "trick mode commands."

The specific portion of a given MPEG-2 data file that is sent to the decoder for decoding in order to satisfy a given trick mode command from the customer is herein after referred to as "target MPEG-2 data." The MPEG-2 data that is to be examined for locating "target MPEG-2 data" is herein referred to as the "ready-for-indexing data file."

FIG. 2B is a flowchart that illustrates a high-level overview of an operation for satisfying any given trick mode command from a customer. For purposes of explanation, certain embodiments are described in the context of set-top boxes. However, the scope of the invention is not limited to set-top boxes and includes managing data in systems that are not set-top boxes. For example, the embodiments apply, without limitation, to any system that is associated with cable companies, and or other providers of VOD services. At block 252 of operation 250, a trick mode command is received and is made known to the CPU of the set top box.

At block 254, a ready-for-indexing data file is retrieved either from some portion of the buffer cache or from persistent memory. For example, the CPU of the set top box causes the relevant ready-for-indexing data file to be retrieved from the buffer cache or from persistent storage such as a disk. At block 256, the ready-for-indexing data file is divided into chunks of MPEG-2 data. For example, CPU 204 of the set top box causes the ready-for-indexing data file to be divided into chunks of MPEG-2 data. The manner in which the ready-for-indexing data file is to be divided into chunks of MPEG-2 data is further described in greater detail herein with reference to FIG. 3. In certain other embodiments, the ready-for-indexing data file is already divided into chunks of MPEG-2 data by the time a trick mode command is received from a customer.

For purposes of explanation, certain embodiments are described in the context of a dual ring buffer cache. However, the scope of the invention is not limited to a dual ring structure for buffer cache. For example, the embodiments apply, without limitation, to any buffer cache structure that is suitable for generating and storing indexes associated with the picture elements in the chunks of MPEG-2 data.

Assume that a portion of the buffer cache that is associated with the CPU has a dual ring structure. At block 258, the chunks of MPEG-2 data are read into an outer ring of the dual structure one at a time. For example, CPU 204 causes the chunks of MPEG-2 data to be read into an outer ring of that portion of buffer cache 210 that has the dual ring structure. The manner in which the chunks of MPEG-2 data is read into an outer ring of the dual ring structure is further described in greater detail herein with reference to FIG. 4. At block 260, an on-the-fly index is created corresponding to each chunk of

MPEG-2 data. The on-the fly indexing is performed on each chunk as the chunk is read into the outer ring of the dual structure. For example, CPU 204 causes an on-the-fly index to be created corresponding to each chunk of MPEG-2 data. The manner in which the on-the-fly index is created for each chunk of MPEG-2 data is described in greater detail herein with reference to FIG. 4 and FIG. 5.

At block 262, the index that is created is stored in an inner ring of the dual ring structure. For example, CPU 204 causes the created index to be stored in an inner ring of that portion of buffer cache 210 that has the dual ring structure. The manner in which the on-the-fly index is stored in the inner ring of the dual ring structure is described in greater detail herein with reference to FIG. 4 and FIG. 5.

When a customer issues a trick mode command such as rewind, for example, the on-the-fly index that is stored in the inner ring of the dual ring structure is used to locate the target MPEG-2 data in the outer ring that is needed to satisfy the customer's command. Once the target MPEG-2 data is located, the target MPEG-2 data is sent to the decoder. The decoder then decodes the target MPEG-2 data into displayable images for the customer.

DIVISION OF MPEG-2 DATA FILE According to certain embodiments, the ready-for-indexing data file, is divided into chunks of MPEG-2 data of arbitrary fixed size. In certain implementations the ready-for- indexing data file is already divided into chunks by the time a trick mode command is issued to the set top box. However, if a ready-for-indexing data file is not already divided into chunks, the ready-for-indexing data file can be divided in a manner as explained with reference to FIG. 3.

FIG. 3 is a block diagram that illustrates a ready-for-indexing data file that is divided into chunks of MPEG-2 data that are of arbitrary fixed size. In FIG. 3, a given ready-for-indexing data file 300 is divided into chunks of MPEG-2 data, such as chunk_0 304, chunk_l 306, chunk_2 308, chunk_3 310, chunk_4 312, chunk_5 314. The ready- for-indexing data file of FIG. 3 is merely illustrative and may vary from implementation to implementation.

Each chunk of MPEG-2 data may contain one or more picture frames. A picture frame has a "picture-type". Picture-types include: 1) an Intraframe (I) picture type, 2) a Bi-directional-predicted (B) picture-type; and 3) a Predicted (P) picture-type. An I picture-type frame acts as a reference for frames that follow it. B picture- type frames are composed by comparing the contents of future frames (i.e., P picture-type frames) and past frames (i.e., I picture-type frames). P picture-type frames are derived from forward prediction of the change in content of a preceding I or P picture-type frame. For convenience, an I picture-type frame will simply be referred to as an "I frame" hereinafter. Similarly, a B picture-type frame will be referred to as a "B frame", and a P picture-type frame will be referred to as a "P frame."

In FIG. 3, the boundaries of each picture-type frame is represented by dashed lines. Chunk_0 in FIG. 3 includes two complete B frames and a portion of an I frame that spans chunk_0 and chunk_l . In addition to the I frame that spans chunk O and chunk_l, chunk_l includes a portion of a P frame that spans chunk_l and chunk_2. In addition to P frame that spans chunk l and chunk_2, chunk_2 includes two complete B frames, one complete P frame and a portion of a B frame that spans chunk_2 and chunk_3. In addition to the B frame that spans chunk_2 and chunk_3, chunk_3 includes a complete B frame and a portion of an I frame that spans chunk_3 and chunk_4- In addition to the I frame that spans chunk_3 and chunk_4, chunk_4 includes a complete P frame and a portion of a B frame that spans chunk_4 and chunk_5. In addition to the B frame that spans chunk_4 and chunk_5, chrjnk_5 includes a complete B frame and a complete P frame.

DUAL RING BUFFER CACHE

When a trick mode command is received by the CPU in the set top box, a ready- for-indexing data file is retrieved either from the buffer cache or from persistent memory for dividing into chunks of MPEG-2 data as described herein with reference to FIG. 3. The ready-for-indexing data file is selected for retrieval based on the following: 1) the trick mode command that is currently issued by the customer, and 2) the chunk of data that is being displayed to the customer at the time the trick mode command is issued by the customer. If the MPEG_2 data that is stored either in buffer cache or in persistent memory is already divided into chunks of MPEG-2 data, then the relevant chunks of MPEG-2 data that are to be indexed are retrieved for loading into the outer ring of the dual ring structure. For example, if the 100^th chunk of MPEG-2 data is being displayed to the customer at the time that the customer issues the "rewind" command, then the relevant chunks of MPEG-2 data that are retrieved from persistent memory start from the 99^th chunk MPEG-2 data. Further, assume that even if the MPEG-2 data is received in a non-sequential fashion from a remote server, the MPEG-2 data is sequential by the time a trick mode command issued by the customer. This is because the MPEG-2 data that is ready for sending to the decoder for displaying in the "play" mode is sequential regardless of the manner in which the MPEG-2 data was received at the set top box or the manner in which the MPEG-2 data is stored in persistent memory.

FIG. 4 is a diagram that illustrates a dual-ring structure of a buffer cache that can be used in certain embodiments of the invention. The dual ring structure 400 of FIG. 4 comprises an outer ring buffer cache 402 and an inner ring buffer cache 450. Outer ring 402 comprises buffer segments 404, 406, 408, 410, 412, 414, 416, 418. The number of buffer segments that are shown in FIG. 4 are merely illustrative. The number of buffer segments may vary from implementation to implementation. Each of the buffer segments holds one chunk of MPEG-2 data. For the purpose of explanation, assume that the relevant chunks of MPEG-2 data that are to be loaded into the dual ring structure in response to a given trick mode command are those that are described herein with reference to FIG. 3. The number of chunks of MPEG-2 data may vary from implementation to implementation depending on the selected size of the chunk and the trick mode command that is issued by the customer. However, the size of the outer ring of the buffer cache is of a fixed arbitrary size. The chunks are gradually and sequentially loaded onto the dual ring structure as the chunks are consumed by the decoder.

To begin, FIG. 4 is explained in a clockwise direction of operation. The clockwise direction of operation is also referred to as the forward direction of operation. In other words, the buffer segments of the dual ring structure of the buffer cache are used in a clockwise direction. A counter-clockwise direction of operation is also described herein.

Buffer segment 404 in outer ring 402 is loaded with chunk_0. As soon as chunk_0 is loaded into outer ring 402, an on-the-fly indexer parses chunkj) in the clockwise or forward direction to determine the starting locations of all the I, P and B frames that are within chunkj) . The starting location of each I, P, or B frame is herein referred to as an index. The indexes are stored in inner ring 450. Note that is the starting locations of all picture frames are located, that would imply that the end locations of the picture frames are also located because the start of one picture frame is the end location of the previous adjacent picture frame.

As shown in FIG. 4, chunkj) contains the starting location for B frame 416, for B frame 418 and for I frame 420. It does not matter that I frame 420 spans chunkj) and chunk_l. It is the starting location that is indexed. Thus, the index entry that corresponds to the starting location for B frame 416 is stored in the inner ring as index entry 452. Similarly, the index entry that corresponds to the starting location for B frame 418 is stored in the inner ring as index entry 454. The index entry that corresponds to the starting location for I frame 420 is stored in the inner ring as index entry 456. The inner ring is also referred to herein as the "index ring." To satisfy the given trick mode command, the portion of the index ring that corresponds to chunkj) is stepped through to determine the location of the desired picture-types. For example, to satisfy the trick mode command (e.g., fast forward), assume that only the locations of all I frames are determined. Once the desired picture- types are found, the MPEG-2 data that corresponds to the index is extracted from the outer ring and sent to the decoder for display.

With respect to chunkj), index 456 gave the starting location in chunkj) of an I frame. The ending location of this particular I frame is found in index entry 458, which is the next index entry in the index ring going in the clockwise direction of operation. Thus, the MPEG-2 data that corresponds to index 456 and index entry 458 (i.e., starting and ending locations of the given I frame), which is in chunk_0 and chunk_l respectively, is extracted and sent to the decoder for display. Of course, chunk_l has to be processed before the MPEG-2 data that corresponds to index 456 and index entry 458 can be extracted from chunkj) and chunk_l, respectively.

The above sequence of steps is repeated for each chunk of MPEG-2 data that is loaded

Next, chunk_l is fed into outer ring 402 into the next buffer segment in the clockwise direction. The next buffer segment in the clockwise direction is buffer segment 406. The on-the-fly indexer parses chunk_l in the clockwise or forward direction to determine the starting locations of all the I, P and B frames that are within chunk_l. Chunk_l contains the starting location for P frame 422. The index entry that corresponds to the starting location for P frame 422 is stored in the index ring as index entry 458. To satisfy the given trick mode command, the portion of the index ring that corresponds to the chunk_l is stepped through to determine the location of the desired picture-types, which are I frames, in this particular example. Since no I frame is found in the portion of the index ring that corresponds to the chunk_l, no data is extracted from chunk_l for sending to the decoder.

Next, chunk_2 is fed into outer ring 402 into the next buffer segment in the clockwise direction. The next buffer segment in the clockwise direction is buffer segment 408. The on-the-fly indexer parses chunk_2 in the clockwise or forward direction to determine the starting locations of all the I, P and B frames that are within chunk_2. Chunk_2 contains the starting location for B frame 424, B frame 426, P frame 428, and B frame 430. The index entry that corresponds to the starting location for B frame 424, B frame 426, P frame 428 and B frame 430 are stored in the index ring as index entry 460, index entry 462, index entry 464, and index entry 466, respectively. To satisfy the given trick mode command, the portion of the index ring that corresponds to the chunk_2 is stepped through to determine the location of the desired picture-types, which are I frames, in this particular example. Since no I frame is found in the portion of the index ring that corresponds to the chunk_2, no data is extracted from chunk_2 for sending to the decoder. Next, chunk_3 is fed into outer ring 402 into the next buffer segment in the clockwise direction. The next buffer segment in the clockwise direction is buffer segment 410. The on-the-fly indexer parses chunk_3 in the clockwise or forward direction to determine the starting locations of all the I, P and B frames that are within chunk_3. Chunk_3 contains the starting location for B frame 432, and I frame 434. The index entry that corresponds to the starting location for B frame 432, and I frame 434 are stored in the index ring as index entry 468, and index entry 470, respectively. To satisfy the given trick mode command, the portion of the index ring that corresponds to the chunk_3 is stepped through to determine the location of the desired picture-types, which are I frames, in this particular example. One I frame is found in the portion of the index ring that corresponds to the chunk_3. Index entry 470 gives the starting location of the only I frame in chunkj?. The ending location of this particular I frame is found in index entry 472, which is the next index entry in the index ring going in the clockwise direction of operation. Thus, the MPEG-2 data that corresponds to index 470 and index entry 472 (i.e., starting and ending locations of the given I frame), which is in chunk_3 and chunk_4 respectively, is extracted and sent to the decoder for display. Of course, chunk_4 has to be processed before the MPEG-2 data that corresponds to index 470 and index entry 472 can be extracted from chunk_3 and chunk_4, respectively.

Next, chunk_4 is fed into outer ring 402 into the next buffer segment in the clockwise direction. The next buffer segment in the clockwise direction is buffer segment 412. The on-the-fly indexer parses chunk_4 in the clockwise or forward direction to determine the starting locations of all the I, P and B frames that are within chunk k Chunk_4 contains the starting location for P frame 436, and B frame 438. The index entry that corresponds to the starting location for P frame 436, and B frame 438 are stored in the index ring as index entry 472, and index entry 474, respectively. To satisfy the given trick mode command, the portion of the index ring that corresponds to the chunk_4 is stepped through to determine the location of the desired picture-types, which are I frames, in this particular example. Since no I frame is found in the portion of the index ring that corresponds to the chunk_4, no data is extracted from chunk_4 for sending to the decoder.

Next, chunk_5 is fed into outer ring 402 into the next buffer segment in the clockwise direction. The next buffer segment in the clockwise direction is buffer segment 414. The on-the-fly indexer parses chunk_5 in the clockwise or forward direction to determine the starting locations of all the I, P and B frames that are within chunk_5. Chunk_5 contains the starting location for B frame 440, and P frame 442. The index entry that corresponds to the starting location for B frame 440, and P frame 442 are stored in the index ring as index entry 476, and index entry 478, respectively. To satisfy the given trick mode command, the portion of the index ring that corresponds to the chunk_5 is stepped through to determine the location of the desired picture-types, which are I frames, in this particular example. Since no I frame is found in the portion of the index ring that corresponds to the chunk_5, no data is extracted from chunk_5 for sendmg to the decoder.

In the present example, the outer ring is not completely filled. However, had the outer ring been completely filled and there are remaining chunks MPEG-2 data to be indexed, then the remaining chunks of MPEG-2 data over-write the chunks MPEG-2 data that are existing in the outer ring.

COUNTER-CLOCKWISE DIRECTION OF OPERATION

In the counter-clockwise or reverse direction of operation, the outer and inner rings of the dual ring buffer cache are filled in the counter-clockwise direction of operation.

For the purpose of explanation, assume that chunk_5 is the first chunk that is fed to the outer ring for the reverse direction of operation. Further assume that chunk-5 is fed to the outer ring at the position labeled as buffer segment 414 in FIG. 4. The present invention is not restricted to using any particular buffer segment during the commencement of either the forward direction or reverse direction of operation due to the ring structure of the buffer cache.

The on-the-fly indexer parses chunk_5 in the clockwise or forward direction to determine the starting locations of all the I, P and B frames that are within chunk_5. Despite the reverse direction of operation, parsing is performed in the forward direction according to certain embodiments of the invention.

By parsing chunk_5, the starting locations of B frame 440 and P frame 442 are found in the order {B, P} . For the reverse direction of operation, the starting locations of {B, P} are transferred to the index ring 450 in the reverse order, namely {P, B} . In other words the starting locations are transferred to the index ring in the counter-clockwise direction. Thus, the starting location of P frame 442 is transferred to index entry 478, and going in the counter-clockwise direction, the starting location of B frame 440 is transferred to index entry 476. After each chunk is indexed, the index ring is searched to locate the starting and ending locations of picture frames with the desired picture type. If the starting and ending locations of picture frames with the desired picture type are found, the corresponding data is extracted and displayed to the customer.

Next, chunk_4 is fed into the outer ring 402 in the next buffer segment position in the counter-clockwise direction. By parsing chunk_4 in the forward direction, the starting locations of P frame 436 and B frame 438 are found in the order {P, B} . For the reverse direction of operation, the starting locations of {P, B} are transferred to the index ring 450 in the reverse order, namely {B, P}. In other words the starting locations are transferred to the index ring in the counter-clockwise direction. Thus, the starting location of B frame 438 is transferred to index entry 474, and going in the counterclockwise direction, the starting location of P frame 436 is transferred to index entry 472.

Similarly, the rest of the chunks of MPEG-2 data, namely, chunk_3 to chunkj) are fed into the outer ring 402 in the reverse direction of operation, parsed in the forward direction for starting locations of picture frames, and the corresponding indexes are transferred in the reverse direction into the index ring 450. As indicated in FIG. 4, once a given set of chunks of data is parsed in the clockwise direction, there is no need to parse the same set of chunks of data if the direction of operation is changed to counterclockwise direction. Similarly, if a given set of chunks of data is parsed in the counterclockwise direction, there is no need to parse the same set of chunks of data if the direction of operation is changed to the clockwise direction, as long as the data has not been over-written in the 2 rings.

When the indexes in the index ring are examined to determine the location of desired picture frames, the index ring is traversed in the counter-clockwise direction. For example, if in chunk_4, B frames are the desired picture frames, then the index entry 474 gives the starting location of B frame 438. However, even though both the index ring and the outer ring are examined in the counter-clockwise direction of operation, the end location of B frame 438 is»given by the index entry 476, which is the next index entry from index entry 474 in the clockwise direction.

MPEG-2 DATA PARSER

According to certain embodiments of the invention, after it is determined what chunks of MPEG-2 data are to be selected for parsing in response to the issued trick mode command, the on-the-fly-indexer performs a search through each selected chunk of MPEG-2 data. FIG. 5 is a flowchart that illustrates some of the computer-implemented acts performed by an on-the-fly-indexer, which uses a dual ring buffer cache for parsing MPEG-2 data. Operation 500 describes the use of dual ring buffers in the clockwise (forward) direction of operation. For purposes of explanation, assume that the relevant MPEG-2 data is selected based on the current trick mode command that is issued by the customer. Further, assume that the relevant MPEG-2 data is already divided into chunks of MPEG-2 data of suitable size by the time operation 500 begins. Also, assume that the MPEG-2 data is in sequential order by the time operation 500 commences.

Operation 500 locates the start of each picture frame in a given chunk of MPEG-2 data. Each element in an MPEG-2 data stream begins with a "start code" such as 0x000001. Elements in MPEG-2 data including picture frames. Thus, a search is made for every null byte because a null byte is potentially the start of a picture frame. The third byte after the start code identifies the picture-type (I, P, or B). A small buffer is used as a temporary holding place for saving bytes when a null byte is found. Such a buffer is used to handle bytes associated with a start code that can span the boundaries of chunks of MPEG-2 data. A local index list is maintained to keep track of the starting locations of all picture frames that are found in each chunk of MPEG-2 data. When the index, i.e., starting location, of all picture frames are determined in a given chunk, then the local index list is transferred to the inner ring of the dual ring structure of the buffer cache. It is to be noted that a picture frame can span chunks of MPEG-2 data. The indexes only take into account the starting location of any given picture frame. The starting location is the location of the first null byte of the start code associated with the given picture frame. Thus, as long as the starting location of a picture is within the boundaries of a given chunk of MPEG-2 data, the index is included as an index entry in the local index list that correspond to the given chunk of MPEG-2 data.

At block 502 of FIG. 5, the 0^th chunk of MPEG-2 data is loaded into a buffer segment of the outer ring of the dual ring structure buffer cache. Due to the ring structure of the buffer cache, any buffer segment can be used for loading the 0^th chunk of MPEG-2 data. For the purpose of explanation, the buffer segment that is used for loading the 0^th chunk of MPEG-2 data is referred to as the 0 buffer segment. The next chunk of MPEG-2 data that is to be loaded into the outer ring will be loaded in the buffer segment that is adjacent to the 0^th buffer segment in the clockwise direction, and so on. At block 504, the chunk of MPEG-2 data is parsed to locate the first null byte in the chunk of MPEG-2 data by beginning at the first byte of the chunk of MPEG-2 data. At block 506, it is determined whether a null byte is located. If it is determined that a null byte is not yet located, then at block 508, the search for a null byte in the chunk of MPEG-2 data continues and control is returned to block 506. However, if at block 506, a null byte is found, then at block 510, an operation starts saving bytes to a small buffer. At block 512, it is determined whether the end of the chunk of MPEG-2 data is reached. If the end of the chunk of MPEG-2 data is not reached, then at block 516, it is determined whether the next few bytes that are located subsequently to the null byte found at block 506 indicate a "start code", which is the start of an element in the MPEG-2 data chunk.

If it is determined that the next few bytes that are located subsequently to the null byte found at block 506 do not indicate a "start code", then at block 518, the small buffer is flushed. Next control is passed to block 542, where a search is performed for the next null byte. If however, at block 516 it is determined that the next few bytes that are located subsequently to the null byte found at block 506 do indicate a "start code", then at block 524, it is again determined whether the end of the chunk of MPEG-2 data is reached. If at block 524, it is determined that the end of the chunk of MPEG-2 data is reached, then at block 530, the next the next chunk of MPEG-2 data is loaded into the next buffer segment of the outer ring in the clockwise direction.

If at block 524, it is determined that the end of the chunk of MPEG-2 data is not reached, then at block 526, it is determined whether the byte after the start code indicates a picture element. In other words, is the element in the chunk a picture frame? If it is determined at block 526 that the byte after the start code indicates a picture element, i.e., a picture frame, then at block 532, it is again determined whether the end of the chunk of MPEG-2 data is reached. If at block 532, it is determined that the end of the chunk of MPEG-2 data is reached, then control is passed to block 534. At block 534, the next chunk of MPEG-2 data is loaded into the next buffer segment of the outer ring in the clockwise direction.

If it is determined at block 532 that the end of the chunk of MPEG-2 data is not reached, then at block 540, the following acts are performed: 1) determine picture-type (e.g., I, P, or B picture type), 2) make new entry in local index list, wherein the new entry gives the starting location of the picture frame based on information in the small buffer, and 3) flush small buffer. Next control is passed to block 542, where a search is performed for the next null byte.

If at block 512, it is determined that the end of the chunk of MPEG-2 data is reached, then at block 514, the next chunk of MPEG-2 data is loaded into the next buffer segment of the outer ring in the clockwise direction.

At block 520, it is determined whether the next few bytes at the beginning of the chunk of MPEG-2 data that is loaded at block 514 indicate a "start code".

If it is determined that the next few bytes do not indicate a "start code", then at block 522, the small buffer is flushed. Next control is passed to block 542, where a search is performed for the next null byte.

If however, at block 520 it is determined that the next few bytes do indicate a "start code", then at block 528, it is determined whether the byte after the start code indicates a picture element. In other words, is the element in the chunk a picture frame?

If it is determined at block 528 that the byte after the start code does not indicate a picture element, then at block 522, the small buffer is flushed. Control is passed to block 542 where a search is performed for the next null byte.

However, if it is determined at block 528 that the byte after the start code indicates a picture element, i.e., a picture frame, then at block 536, the following acts are performed: 1) determine picture-type (e.g., I, P, or B picture type), 2) make new entry in local index list, wherein the new entry gives the starting location of the picture frame based on information in the small buffer, 3) flush small buffer, 4) transfer local index list for the chunk of MPEG-2 data that is most recently been completely parsed to inner ring (index ring) of the dual structure buffer cache to be stored as an index entries that correspond to starting locations of picture frames for the chunk of MPEG-2 data that is most recently been completely parsed.

At block 538, a new local index list is started. At block 542, a search is performed for the next null byte. Next, control is returned to block 506.

In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.

Claims

CLAIMSWhat is claimed is:

1. A method for delivering target MPEG-2 data, the method comprising the computer-implemented acts of: receiving an MPEG-2 data file at a set-top-box; dividing said MPEG-2 data file into chunks of MPEG-2 data; reading each of said chunks of MPEG-2 data into a first ring of a buffer cache; after reading each of said chunks of MPEG-2 data into said first ring, parsing each of said chunks of MPEG-2 data for generating one or more indexes that are associated with corresponding picture elements in each of said chunks of MPEG-2 data; storing said one or more indexes in a second ring of said buffer cache; and using said one or more indexes for locating said target MPEG-2 data for delivering for display.

2. The method of Claim 1 wherein: said first ring and said second ring are capable of being used in a clockwise direction and in a counter-clockwise direction for performing a rewind trick mode and a fast-forward trick mode, respectively, based on said one or more indexes.

3. The method of Claim 1 wherein: said first ring and said second ring are concentric.

4. The method of Claim 1 wherein: said buffer cache is associated with said set-top box.

5. The metho4 of Claim 1 wherein: said chunks of MPEG-2 data are of arbitrary fixed size.

6. The method of Claim 1 wherein: said second ring has a smaller radius than that of said first ring.

7. The method of Claim 1 wherein: said first ring comprises a plurality of buffer segments; wherein each buffer segment is of an arbitrary fixed size.

8. The method of Claim 1 wherein: said first ring is of a size that is at least large enough to hold a largest picture element that is found in said MPEG-2 data file.

9. The method of Claim 1 wherein: said second ring is of a size that is at least large enough to hold all of said indexes that are associated with said chunks of MPEG-2 data.

10. The method of Claim 1 wherein: said second ring is of a size that is at least large enough to find a start and an end of a target picture element.

11. The method of Claim 1 , wherein the act of parsing each of said chunks of MPEG-2 data further comprises the acts of: searching for null bytes in said chunk of MPEG-2 data; determining whether said null bytes are starting locations of said picture elements.

12. The method of Claim 11 , wherein the act of determining whether said null bytes are starting locations of picture elements further comprises: determining whether bytes that are next to and subsequent to each null byte of said null bytes indicate a start code that is associated with each picture element of said picture elements; and determining a picture element type if said start code is determined.

13. A method for delivering target data, the method comprising the computer- implemented acts of: receiving at a receiver a data file that is associated with said target data; dividing said data file into chunks of data; reading each of said chunks of data into a first ring of a buffer cache; after reading each of said chunks of data into said first ring, parsing each of said chunks of data for generating one or more indexes that are associated with corresponding elements in each of said chunks of data; storing said one or more indexes in a second ring of said buffer cache.

14. The method of Claim 13 wherein: said first ring and said second ring are capable of being used in a clockwise direction and in a counter-clockwise direction.

15. The method of Claim 13 wherein: said first ring and said second ring are concentric.

16. The method of Claim 13 wherein: said buffer cache is associated with said receiver.

17. The method of Claim 13 wherein: said chunks of data are of arbitrary fixed size.

18. The method of Claim 13 wherein: said second ring has a smaller radius than that of said first ring.

19. The method of Claim 1 wherein: said first ring comprises a plurality of buffer segments; wherein each buffer segment is of an arbitrary fixed size.

20. The method of Claim 13 wherein: said first ring is of a size that is at least large enough to hold a largest element that is found in said data file.

21. The method of Claim 13 wherein: said second ring is of a size that is at least large enough to hold all of said indexes that are associated with said chunks of data.

22. The method of Claim 13 wherein: said second ring is of a size that is at least large enough to find a start and an end of an element that is of a desired type.

23. The method of Claim 13, wherein the act of parsing each of said chunks of data further comprises the acts of: searching for null bytes in said chunk of data; determining whether said null bytes are starting locations of said elements in each of said chunks of data.

24. The method of Claim 23, wherein the act of determining whether said null bytes are starting locations of elements further comprises: determining whether bytes that are next to and subsequent to each null byte oζsaid null bytes indicate a start code that is associated with each element of said elements; and determining an element type if said start code is determined.

25. A method for delivering target data, the method comprising the computer- implemented acts of: receiving at a receiver a data file that is associated with said target data after receiving said data file, generating indexes corresponding to elements in said data file.

26. The method of Claim 25, wherein the act of generating indexes corresponding to elements in said data file comprises the computer- implemented acts of: reading a portion of said data file into a first ring of a buffer cache; after reading said portion into said first ring, parsing said portion for generating one or more indexes that are associated with corresponding elements in said portion.

27. The method of Claim 26, wherein the act of parsing further comprises the acts of: searching for null bytes in said portion; determining whether said null bytes are starting locations of one or more elements in said portion.

28. The method of Claim 27, wherein the act of determining whether said null bytes are starting locations of one or more elements further comprises: determining whether bytes that are next to and subsequent to each null byte of said null bytes indicate a start code that is associated with each 90 element of said one or more elements; and determining an element type if said start code is determined.

29. The method of Claim 26, wherein said portion of data comprises one or more chunks of data form said data file storing said one or more indexes in a second ring of said buffer cache.

95 30. The method of Claim 26, further comprising storing said one or more indexes in a second ring of said buffer cache.

31. The method of Claim 26, wherein said buffer cache is associated with said receiver.

32. A method for delivering target data, the method comprising the computer- 100 implemented acts of: using a buffer cache for: generating one or more indexes that are associated with corresponding elements in a data file that is associated with said target data ; storing said one or more indexes; and 105 using said one or more indexes for locating said target data. i

33. The method of Claim 32, wherein said buffer cache has a structure suitable for generating and storing said one or more indexes.

34. The method of Claim 33, wherein said structure suitable is a dual ring structure.

110 35. A computer-readable medium carrying one or more sequences of instructions for delivering target MPEG-2 data in a computer system, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the acts of: receiving an MPEG-2 data file at a set-top-box; 115 dividing said MPEG-2 data file into chunks of MPEG-2 data; reading each of said chunks of MPEG-2 data into a first ring of a buffer cache; after reading each of said chunks of MPEG-2 data into said first ring, parsing each of said chunks of MPEG-2 data for generating one or more indexes that are associated with corresponding picture elements in each of said chunks 120 of MPEG-2 data; storing said one or more indexes in a second ring of said buffer cache; and using said one or more indexes for locating said target MPEG-2 data for delivering for display.

36. A computer-readable medium carrying one or more sequences of 125 instructions for delivering target data in a computer system, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the acts of: receiving at a receiver a data file that is associated with said target data ; dividing said data file into chunks of data; 130 reading each of said chunks of data into a first ring of a buffer cache; after reading each of said chunks of data into said first ring, parsing each of said chunks of data for generating one or more indexes that are associated with corresponding elements in each of said chunks of data; storing said one or more indexes in a second ring of said buffer cache.

135 37. A computer-readable medium carrying one or more sequences of instructions for delivering target data in a computer system, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the acts of: receiving at a receiver a data file that is associated with said target data;

140 after receiving said data file, generating indexes corresponding to elements in said data file.