Abstract:
Apparatuses for reordering a plurality of data elements that utilize a buffer capable of storing at least one data element. The last data element (Pn) is located and moved to the buffer. The data element (Px) that should be located at the location of the last data element (Pn) is moved to fill the space vacated. If the last data element should be located at the location of Px, then the last but one (Pn- 1 ) element is located and moved to the buffer. The element (Px′) that should be located at the location of Pn- 1  is then moved to the location of Pn- 1 . The process is repeated until all the data elements are reordered.

Description:
STATEMENT OF RELATED APPLICATION  
       [0001]     This application is a continuation and claims the benefit of prior filed copending application Ser. No. 09/630,576, filed Aug. 3, 2000, which is incorporated by reference herein in its entirety. This application also claims the benefit of provisional application No. 60/146,979, filed Aug. 3, 1999, which is also incorporated by reference herein in its entirety. 
     
    
     COPYRIGHT NOTICE  
       [0002]     Appendix “A” of the disclosure of this patent application contains material, which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyrights whatsoever.  
       FIELD OF THE INVENTION  
       [0003]     Aspects of the present invention involve data reordering, and in particular apparatuses for reordering data elements, such as digital spread spectrum (DSS) data packets, using a reduced memory buffer.  
       BACKGROUND OF THE INVENTION  
       [0004]     In Direct-TV data protocol, program guides are sent as a collection of data packets.  FIG. 1A  shows a DSS transmitter  101  that transmits DSS data packets that are received by a DSS receiver  102  and routed to a SDRAM  103 . The packets are stored in a random order.  
         [0005]      FIG. 1B  shows a typical SDRAM  103  with data packets (PO-P 8 )  105  stored at different locations  104 , illustrated as LO-L 8 .  FIG. 1B  shows a first set of data packets  106  (packets PO-P 4 ) stored at memory locations L 4  to L 8  respectively and a second set of data packets (P 5 -P 8 )  107  stored at memory locations LO to L 3  respectively. However for efficient processing, the packets should be stored in the order illustrated in  FIG. 1C . i.e. packet PO should be stored in location LO, PI in location L 1  and so forth.  
         [0006]     Currently a second memory buffer is used to reorder the data packets as they are received.  FIG. 1D  shows a second memory buffer  111  used for reordering data packets. When the first set  106  is received, in step S 101 , packets PO-P 4  are moved to memory buffer  111 . In step S 102 , data packets in second set  107  (P 5 -P 8 ) are moved to the desired locations, L 5 -L 8 , as shown in  FIG. 1C . Finally, in step S 103 , data packets in set  106  are moved to locations L 0 -L 4 . Currently, the reordering system is expensive and hence increases the overall system cost.  
         [0007]     Therefore, what is needed is a system that can efficiently reorder incoming data packets without expensive memory buffer requirements.  
       SUMMARY OF THE INVENTION  
       [0008]     According to one aspect of the present invention, an apparatus for reordering a plurality of data elements stored in a memory includes a computer-readable storage medium; and a processor responsive to the computer-readable storage medium and to a computer program. When the computer program is loaded into the processor, it is operative to perform a method including: locating, within the memory, a location (Ln) of a last data element (Pn) of the plurality of data elements; moving the last data element Pn to a buffer that can at least store one data element; and locating, within the memory, a data element (Px) of the plurality of data elements, stored at a location Lx, that should be located at the location Ln.  
         [0009]     The apparatus may be a set-top device or a personal computer, and may further include an interface, operative to receive the plurality of data elements and to arrange for direction of the plurality of data elements to the memory. The interface may be a digital spread spectrum receiver or a bus. The plurality of data elements may be digital spread spectrum packets. The method may further include: if the last data element Pn should be located at the location Lx, locating, within the memory, a second last data element (Pn- 1 ) of the plurality of data elements to the buffer; locating, within the memory, a data element (Px′) of the plurality of data elements at a location Lx′, that should be located within the memory at a location Ln- 1  associated with the second last data element Pn- 1 ; determining if the second last data element Pn- 1  should be located at the location Lx′; and moving the data element Px′ to the location Ln- 1  if the second last data element Pn- 1  is not to be located at the location Lx′. Thereafter, the method may include: determining a data element (Py) of the plurality of data elements that should be located at the location Lx; and moving the data element Px′ to the location Lx; or the method may include determining a data element (Py′) of the plurality of data elements that should be located at the location Lx′; and moving the data element Py′ to the location Lx′.  
         [0010]     According to another aspect of the present invention, a data reordering apparatus includes a plurality of random access memory locations for storing a plurality of data elements; a buffer memory location arranged to receive at least one of the plurality of data elements from at least one of the plurality of random access memory locations; and an interface in communication with the plurality of random access memory locations and the buffer memory location. The interface is operative for communication with a processor, in response to execution of a computer program by the processor, to provide access to the plurality of random access memory locations and the buffer memory location. When the interface is in communication with the processor, and when the computer program is loaded into the processor, the computer program is operative to perform a method for reordering the plurality of data elements, as generally described above. The buffer memory location may have a size of about one data element. The data reordering apparatus may be a memory or a processing unit of a computer arrangement, and the plurality of data elements may be digital spread spectrum data packets.  
         [0011]     According to a further aspect of the present invention, a memory of a computer arrangement is arranged to cause the computer arrangement to: locate, within a plurality of random access memory locations, a location (Ln) of a last data element (Pn) of a plurality of digital spread spectrum (DSS) data elements; move the last data element Pn to a buffer memory location that can at least store a DSS data element; and locate a data element (Px) of the plurality of DSS data elements stored at location Lx within the plurality of random access memory locations, that should be located at the location Ln. The plurality of DSS data elements may be DSS data packets. The memory may further be arranged to cause the computer arrangement to: if the last data element Pn should be located at the location Lx, locate, within the plurality of random access memory locations, a second last data element (Pn- 1 ) of the plurality of data elements to the buffer; locate, within the plurality of random access memory locations, a data element (Px′) of the plurality of data elements at a location Lx′, that should be located within the plurality of random access memory locations at a location Ln- 1  associated with the second last data element Pn- 1 ; determine if the second last data element Pn- 1  should be located at the location Lx′; and move the data element Px′ to the location Ln- 1  if the second last data element Pn- 1  is not to be located at the location Lx′. Thereafter, the memory may further be arranged to cause the computer arrangement to: determine a data element (Py) of the plurality of data elements that should be located at the location Lx; and move the data element Px′ to the location Lx; or the method may be arranged to determine a data element (Py′) of the plurality of data elements that should be located at the location Lx′; and move the data element Py′ to the location Lx′.  
         [0012]     This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiments thereof in connection with the attached drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]      FIG. 1A  is a block diagram showing data packet movement from a DSS transmitter to a SDRAM.  
         [0014]      FIG. 1B  is a block diagram of the SDRAM showing data packet storage locations.  
         [0015]      FIG. 1C  is a block diagram of desirable data packet storage locations.  
         [0016]      FIG. 1D  is a basic flow chart showing the prior art process steps employed to reorder data packets according to conventional systems.  
         [0017]      FIG. 2  is a block diagram of a memory buffer, according to one aspect of the present invention.  
         [0018]      FIG. 3  is a block diagram of the system architecture to implement process steps according to another aspect of the present invention.  
         [0019]      FIG. 4  is a basic flow chart showing process steps according to yet another aspect of the present invention.  
         [0020]     The use of similar reference numerals in different figures indicates similar or identical items. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0021]      FIG. 2  shows a memory buffer  200  that is capable of storing data packets.  
         [0022]      FIG. 3  shows a block diagram of the architecture, according to one aspect of the present invention to implement process steps to reorder DSS data packets which are received out of order, for example as illustrated in  FIG. 1B , to a desired location, as illustrated in  FIG. 1C . It is noteworthy, that the desired locations in  FIG. 1C  are merely to illustrate one aspect of the present invention and are not meant to limit the invention.  
         [0023]     The system illustrated in the  FIG. 3  block diagram can be used for a personal computer or a set top box architecture.  FIG. 3  shows a CPU  301  for executing computer-executable (or microprocessor executable) process steps and interfaces with computer bus  300 . Also shown in  FIG. 3  is a rotating disk storage device  304  for storing data. It is noteworthy that the present invention is not limited to using a rotating disk or any specific storage device.  
         [0024]     Disk storage device  304  stores operating system program files, computer executable process steps according to one aspect of the present invention and application program files etc. Some of these files are stored on disk  304  using an installation program. For example, CPU  301  executes computer-executable process steps of an installation program so that CPU  301  can properly execute the program.  
         [0025]     A random access main memory (“RAM”)  302  also interfaces to computer bus  300  to provide CPU  301  with access to memory storage. When executing stored computer-executable process steps from disk  304 , CPU  301  stores those process steps in RAM  302  and executes the stored process steps out of RAM  302 .  
         [0026]     Read only memory (“ROM”)  303  is provided to store invariant instruction sequences such as start-up instruction sequences or basic Input/output operating system (BIOS) sequences.  
         [0027]      FIG. 3  also shows DSS receiver  102  that receives data packets from DSS transmitter  101  and then stores them in SDRAM  103 . Memory buffer  200  is used to reorder data packets received in SDRAM  103 , as described below. Typically, memory buffer  200  is capable of storing at least one data packet.  
         [0028]      FIG. 4  is a flow diagram of computer executable process steps to implement one aspect of the present invention. Generally, the  FIG. 4  process steps illustrate a methodology for reordering data packets, such that only a small memory buffer, e.g., memory buffer  200  that can store at least one DSS data packet, is utilized. Data packets are arranged according to a desired data packet location scheme, e.g., as shown in  FIG. 1C .  
         [0029]     More specifically, in step S 401 , locate the location (Ln) of the last packet (Pn) in SDRAM  103 . For illustration purposes only, location of the last packet (P 8 ) is shown as L 3  in  FIG. 1B .  
         [0030]     In step S 402 , move the last packet (P 8 ,  FIG. 1B ) to memory buffer  200  that can store at least one data packet.  
         [0031]     In step S 403 , determine the packet (Px) that should be stored at Ln. As illustrated in  FIG. 1C , location L 3  should have packet P 3 . Hence Px in this example is data packet P 3 .  
         [0032]     In step S 404 , determine if Pn should be located at location Lx (where packet Px was located). For illustration purposes, determine if P 8  is to be located at L 7  (See  FIG. 1C ).  
         [0033]     If Pn should not be stored at Ln ( FIG. 1C ), then in step S 405 , move Px (P 3  from location L 7  in  FIG. 1B ) to location Ln (L 3  of  FIG. 1C ).  
         [0034]     In step S 406  determine a packet (Py) that should be located at location Lx. For illustration purposes, packet P 7  at location L 2  should be stored at location L 7  ( FIG. 1C ). Hence Py in this case is packet P 7 .  
         [0035]     In step S 407 , move Py to location Lx. Hence packet P 7  is moved from L 2  to L 7 . ( FIG. 1C ).  
         [0036]     If in step S 404 , it is determined that Pn should be located at location Lx, then in step S 408  move packet Pn- 1  to memory buffer  200 . For illustration purposes, if packet P 8  were to be located at location L 7 , then move packet P 7  from location L 2  ( FIG. 1B ) to memory buffer  200 .  
         [0037]     In step S 409 , determine which packet (Px′) should be stored at location Ln- 1 . For illustration purposes, packet P 2  should be located at location L 2  ( FIG. 1C ).  
         [0038]     In step S 410 , move Px′ to location Ln- 1 . For illustration purposes, P 2  is moved from location L 6  to L 2  ( FIG. 1B ).  
         [0039]     The foregoing process steps are repeated until all the data packets are reordered as shown in  FIG. 1C . Appendix “A” provides an example of a DSS packet reordering system to implement the foregoing aspects of the present invention. Appendix “A” provides a sample of computer executable code for DSS packet reordering, according to one aspect of the present invention. One skilled in the art of computer programming can practice the foregoing aspects of the present invention by using the sample code disclosed in Appendix “A”.  
         [0040]     By virtue of the foregoing aspects of the present invention, a memory buffer that is smaller than conventional systems is required to reorder numerous data packets. Hence memory cost is reduced and that reduces the overall cost of the system. Furthermore, the present process is more efficient than the conventional prior art systems because data packets are only moved once, unlike conventional systems where data packets are moved more than once.  
         [0041]     Appendix “A” 
                                                                                                                                                                                                                                                                                                                                                                                     VOID            Pgl_gu_packet_reorder(USIGNED8   *buf_p,                USIGNED32   filter,           USIGNED8   max_packets,           PgSD_sat_type_t   sat_type_t cur_network)            {                register USIGNED8   *next_buf_p;           register USIGNED8   *hole_buf_p;           register USIGNED8   *temp_buf_p;           register USIGNED8   segm_packet;           register USIGNED16   max_bytes;           USIGNED8   pckt_cnt;           USIGNED8   packets;           USIGNED8   shift_index;           USIGNED8   *find_buf_p;           USIGNED8   temp_buf[127];           USIGNED8   pre_filter;                /** Find Filter **/           /** Start with last packet **/           find_buf_p = (buf_p + ((max_packets − 1) * pgPD_DIRECTV_PACKET_SIZE));           pre_filter = ((filter &gt;&gt; 24) &amp; Oxff);           for (segm_packet = 0; segm_packet &lt; max_packets; segm_packet++)           {                /**Read first byte is faster **/           jf (pgm_ut_readbyte(find_buf_p) = = pre_filter)           {                if((unsigned int)pgm_ut_read4bytes(find_buf_p) == filter)           {                break;                }                }           /**Point to previous packet **/           find_buf_p− = pgPD_DIRECTV_PACKET_SIZE;                }           if(segm_packet == max_packets)           {                /**A failure indicates that no reordering could be done**/                return;            }       /**Readjust because we started from the back of the buffer **/       segm_packet = (max_packets − segm_packet − 1);       if segm_packet == 0)       {                /** No Reordering is necessary **/           /** SEGM is first packet already **/           return;            }       /**Precalculate number of bytes in packet buffer **/       max_bytes = (max_packets*pgPD_DIRECTV_PACKET_SIZE);       /**MPG is out of sequence **/       for (packets=0, shift_index=0; packets &lt; max_packets; shift_index++)       {                next_buf_p=buf_jp=((segm_packet+shift_index)*                pgPD_DIRECTV_PACKET_SIZE);                if(next_buf_p &gt;= (buf_p + max_bytes))           {                next_buf_p = max_bytes;                }           /**Store start of copy pointer**/           temp_buf_p = next_buf_p;           /**Store packet on stack **/           memcpy (temp_buf, temp_buf_p, pgPD_DIRECTV_PACKET_SIZE);           /** Start Packet Moving **/           for (pckt_cnt=O; pckt_cnt &lt; (max_packets − 1); pckt_cnt++)           {                hole_buf_p = next_buf_p;           /** Store pointer to current hole produced by last copy **/           /**Point to next packet **/           next_buf_p+=(segm_packet*pgPD_DIRECTV _PACKET_SIZE);           if (next_buf_p &gt; + max_bytes))           {                /**Went past the end of the buffer**/           next_buf_p −= max_bytes)           }                if (next_buf_p = = temp_buf_p)            {                /**Before all the packets were copied the start                packet is the next packet to be copied. Need to shift forward           to prevent oscillation **/                break;                }           /**Copy appropriate packet into hole**/                memcpy(hole_buf_p, next_buf_p, pgPD _DIRECTV —                  PACKET_SIZE;                packets++;                }           /** Copy temp buffer into next of last packet location **/           memcpy((buf_p+(shift_index*pgPD_DIRECTV_PACKET_SIZE)),           temp_buf, pgPDDIRECTV_PACKET_SIZE);           packets++;                }            }