Systems and methods for packing data into a destination register

[0002] A. Field of the Invention

[0003] The present invention relates generally to communication systems and, more particularly, to systems and methods for packing data from a source register into a destination register.

[0004] B. Description of Related Art

[0005] Some conventional systems include source and destination registers. During operation, data from a source register that may contain some invalid data bytes may be transferred to a destination register that stores valid data bytes in contiguous locations. The resulting problem of transferring the valid bytes of data from the source register to contiguous locations in the destination register may be referred to as “packing.” The problem becomes particularly troublesome when the invalid data bytes are randomly located amidst valid data bytes in the source register.

[0006] As a result, a need exists for a mechanism that packs non-contiguous valid bytes of data from a source register to contiguous locations in a destination register.

[0007] Systems and methods consistent with the present invention address this need by providing a packing mechanism that permits valid bytes of data from non-contiguous locations in a source register to be transferred to contiguous locations in a destination register.

[0008] In accordance with the purpose of the invention as embodied and broadly described herein, a data packing system includes a source memory, a destination memory, and a data packer. The source memory stores data in source storage locations. The data includes valid data and invalid data. The destination memory stores at least some of the data from the source memory in destination storage locations. The destination memory stores the valid data in contiguous ones of the destination storage locations. The data packer transmits the valid data from the source storage locations to the contiguous destination storage locations.

[0009] In another implementation consistent with the present invention, a method packs data from source storage locations of a source memory to destination storage locations of a destination memory. The data includes valid data and invalid data. The method includes storing the data in the source storage locations, at least some of the invalid data being interspersed among the valid data in the source storage locations; generating addresses for each of the valid data; transferring the valid data from the source storage locations to contiguous ones of the destination storage locations using the generated addresses and the invalid data to other ones of the destination storage locations; and storing the valid data and invalid data in the destination storage locations of the destination memory.

[0010] In yet another implementation consistent with the present invention, a data packer packs data from source storage locations in a source register into destination storage locations in a destination register. The data includes valid and invalid data. The data packer includes at least one comparator and at least one multiplexer. The comparator generates at least one selection signal. The multiplexer receives the valid and invalid data from the source storage locations as inputs and transmits the valid data to contiguous ones of the destination storage locations from ones of the source storage locations in response to the selection signal.

[0011] In a further implementation consistent with the present invention, a method packs data from source storage locations in a source register into destination storage locations in a destination register. The data includes valid and invalid data. The method includes generating a plurality of selection signals; transferring the valid data from ones of the source storage locations to contiguous ones of the destination storage locations in response to the selection signals; and sending the invalid data from other ones of the source storage locations to other ones of the destination storage locations in response to the selection signals.

[0012] In another implementation consistent with the present invention, a computer-readable memory device contains a data structure, including data byte areas, valid byte indicator areas, and valid byte address areas. The data byte areas store a valid data byte or an invalid data byte. The valid byte indicator areas store indications of whether a corresponding one of the data byte areas stores a valid data byte or an invalid data byte. The valid byte address areas store addresses when a corresponding one of the data byte areas stores a valid data byte.

[0013] The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate an embodiment of the invention and, together with the description, explain the invention. In the drawings,

[0014] FIG. 1 is a diagram of an exemplary system in which systems and methods consistent with the present invention may be implemented;

[0015] FIG. 2 is a detailed diagram of the source register of FIG. 1 according to an implementation consistent with the present invention;

[0016] FIG. 3 is a detailed diagram of the destination register of FIG. 1 according to an implementation consistent with the present invention;

[0017] FIG. 4 is a detailed diagram of the data packer of FIG. 1 according to an implementation consistent with the present invention;

[0018] FIG. 5 is an exemplary flowchart of processing for packing data from the source register into the destination register according to an implementation consistent with the present invention; and

[0019] FIGS. 6A-6C are diagrams of exemplary operations performed by the system of FIG. 1 according to an implementation consistent with the present invention.

[0020] The following detailed description of the invention refers to the accompanying drawings. The same reference numbers in different drawings identify the same or similar elements. Also, the following detailed description does not limit the invention. Instead, the scope of the invention is defined by the appended claims and equivalents.

[0021] Systems and methods consistent with the present invention provide a packing mechanism that packs valid data that is not necessarily stored in contiguous locations in a source register into contiguous locations in a destination register, possibly in a single clock cycle.

[0022] FIG. 1 is an exemplary system 100 consistent with the present invention. The system 100 includes a source register 110, a destination register 120, a data packer 130, and an address generator 140. The source register 110 receives data from a source and transmits the data to the destination register 120 via the data packer 130. The source register 110 may include a conventional register that stores a number of bytes of data.

[0023] FIG. 2 is a detailed diagram of the source register 110 according to an implementation consistent with the present invention. In this implementation, the source register 110 includes sixteen storage locations 210 that store sixteen bytes of data. In other implementations, the source register 110 may contain a different number of storage locations and store a different number of bytes.

[0024] Each of the storage locations 210 may include a data buffer 220, a valid byte indicator 230, and a valid byte address 240. The data buffer 220 may store a single byte of data. The valid byte indicator 230 may store one or more bits that indicate whether the data stored in the data buffer 220 is valid. In an implementation consistent with the present invention, the valid byte indicator 230 stores a single bit that has a first value to indicate “valid” and a second value to indicate “invalid.”

[0025] The valid byte address 240 may store an address used in, the data packing process (described below). Only valid data bytes may include a valid byte address 240. The valid byte address 240 may contain a null or empty value for invalid data bytes. The address generator 140 (FIG. 1) generates the valid byte addresses 240.

[0026] Returning to FIG. 1, the address generator 140 may include a software and/or hardware address generator located within the source register 110, the data packer 130, or separate therefrom. The address generator 140 assigns an address to each of the valid data bytes in the source register 110. The address for any valid byte is an increment of one greater than the address for the preceding valid byte in the source register 110. For example, assume that the source register 110 contains four bytes of data (i.e., byte 0-byte 3), bytes 0, 1, and 3 are valid, and byte 2 is invalid. In this case, byte 0 may be assigned an address of 0 and byte 1 an address of 1 (i.e., one more than the address for byte 0). Since byte 2 is invalid, its address is nullified. Byte 3 is the next valid byte and its address is one more than the address of the previous valid byte (i.e., byte 1), or 2.

[0027] The destination register 120 may include a conventional register that receives data bytes from the source register 110 and may send the data bytes onto their intended destination. FIG. 3 is a detailed diagram of the destination register 120 according to an implementation consistent with the present invention. Like the source register 110, the destination register 120 may include sixteen storage locations 310 that store sixteen bytes of data. In other implementations, the destination register 120 stores a different number of bytes, possibly different from the number of bytes stored by the source register 110.

[0028] Each of the storage locations 310 may include a data buffer 320 and a valid byte indicator 330. The data buffer 320 may store a single byte of data. The valid byte indicator 330 may store one or more bits that indicate whether the data stored in the data buffer 320 is valid. In an implementation consistent with the present invention, the valid byte indicator 330 stores a single bit that has a first value to indicate “valid” and a second value to indicate “invalid.”

[0029] Returning to FIG. 1, the data packer 130 facilitates the transmission of data bytes from the source register 110 to the destination register 120. FIG. 4 is a detailed diagram of the data packer 130 according to an implementation consistent with the present invention. The data packer 130 may include a multiplexer 410 and a comparator 420 corresponding to each of the storage locations 310 (FIG. 3) in the destination register 120.

[0030] The multiplexer 410 may include a conventional multiplexing device that receives multiple inputs and outputs one of them in response to a selection signal. In an implementation consistent with the present invention, the multiplexer 410 includes a 16:1 multiplexer that receives the data bytes from each of the data buffers 220 (FIG. 2), and possibly the corresponding valid byte indicators 230, from the source register 110 and transmits one of the data bytes (and valid byte indicators 230) to the corresponding storage location 310 in the destination register 120. The multiplexer 410 determines which of the data bytes (and valid byte indicators 230) to send to the corresponding storage location 310 based on a value of a selection signal from the comparator 420.

[0031] The comparator 420 may include a conventional device that compares two or more values and generates a result based on the comparison. In an implementation consistent with the present invention, the comparator 420 compares each of the valid byte addresses 240 from the source register 110 to the address of the corresponding storage location 310 in the destination register 120 and generates a result based on the comparison. The comparator 420 looks for a match between one of the valid byte addresses 240 and the address of the storage location 310. When the comparator 420 discovers a match, it generates a selection signal to instruct the multiplexer 410 to select the data buffer 220 (and possibly the valid byte indicator 230) corresponding to the valid byte address 240.

[0032] When the comparator 420 finds no match such as in the case of an invalid byte of data, the comparator 420 may generate a selection signal for selecting one of the invalid bytes of data from the source register 110. The particular selection process used by the comparator 420 to select among the one or more data buffers 220 containing invalid data bytes may vary.

[0033] FIG. 5 is an exemplary flowchart of processing for packing data from the source register 110 into the destination register 120 according to an implementation consistent with the present invention. Processing begins when the source register 110 receives data from a source [step 510]. The source register 110 stores the data as data bytes in the data buffers 220 and identifies each of the data bytes as valid or invalid [step 520]. The source register 110 may use conventional techniques to determine whether a particular data byte is valid or invalid. The source register 110 stores an indication of the validity or invalidity of a data byte in the valid byte indicator 230.

[0034] The address generator 140 generates valid byte addresses 240 for each of the data buffers 220 that contain valid data bytes [step 530]. As described above, the address for any valid byte is an increment of one greater than the address for the preceding valid byte in the source register 110. The valid byte address 240 for the first valid byte may be set to “0,” or any other value.

[0035] The comparators 420 (FIG. 4) compare the valid byte addresses 240 to the addresses of the corresponding storage locations 310 in the destination register 120 to generate selection signals for the multiplexers 410 [step 540]. Each of the comparators 420 looks for a match between one of the valid byte addresses 240 and the address of the corresponding storage location 310. When a match is found, the comparator 420 generates the appropriate selection signal to instruct the associated multiplexer 410 to transmit the valid data byte from the source register 110 to the storage location 310 in the destination register 120. When no match is found, however, the comparator 420 may generate a selection signal to instruct the associated multiplexer 410 to transmit one of the invalid data bytes from the source register 110 to the storage location 310 in the destination register 120.

[0036] Each of the multiplexers 410 receives all of the data bytes from the source register 110 as inputs and transmits one of them to a corresponding storage location 310 in the destination register 120 based on the selection signal received from the associated comparator 420 [step 550]. The destination register 120 receives the data bytes (both valid and invalid) from the source register 110 and stores them as received from the multiplexers 410 [step 560].

[0037] FIGS. 6A-6C are diagrams of exemplary operations performed by the system 100 according to an implementation consistent with the present invention. In FIG. 6A, the source register 110 receives sixteen bytes of data. Storage locations S0, S1, S3, S5, S9, S10, S12, and S14 store valid data and storage locations S2, S4, S6-S8, S11, S13, and S15 store invalid data.

[0038] In FIG. 6B, the address generator 140 generates valid byte addresses for each of the valid bytes. The address generator 140 starts with storage location S0 and assigns it valid byte address 0. Storage location S1 stores the next valid byte. Therefore, the address generator 140 increments the valid byte address of the previous storage location that contains a valid byte. In this case, the address generator 140 assigns storage location S1 a valid byte address of 1. Storage location S2 stores an invalid byte and, therefore, is not assigned a valid byte address. Storage location S3 stores the next valid byte. Therefore, the address generator 140 assigns it a valid byte address of 2. The address generator 140 continues this processing to assign valid byte addresses to the storage locations as shown in FIG. 6B.

[0039] In FIG. 6C, the data bytes are transmitted from the source register 110 to the destination register 120 via the data packer 130 (not shown in FIG. 6C). The data packer 130 determines which storage locations in the destination register 120 receive which of the valid bytes from the source register 110. Based on the processing described above, storage location D0 in the destination register 120 receives the valid byte from the storage location S0 in the source register 110. Similarly, the storage locations D1-D7 receive the valid bytes from the storage locations S1, S3, S5, S9, S10, S12, and S14, respectively.

[0040] Systems and methods consistent with the present invention pack valid data from non-contiguous locations in a source register into contiguous locations in a destination register. As a result of the above systems and methods, data packing from the source register to the destination register may take place in a single clock cycle.

[0041] The foregoing description of preferred embodiments of the present invention provides illustration and description, but is not intended to be exhaustive or to limit the invention to the precise form disclosed. Modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention. For example, the source register 110 has A been described as storing a valid byte address 240 for each valid byte of data. In another implementation consistent with the present invention, the address generator 140, not the source register, 110, stores this information. In this case, the address generator 140 may include a memory device for storing the valid byte addresses.

[0042] In addition, the data packer 130 has been described as including a multiplexer 410 and comparator 420 for each storage location of the destination register 120. In another implementation consistent with the present invention, at least some of the operations performed by the data packer 130 are implemented in software. In other implementations, the data packer 130 includes different hardware elements than those shown in FIG. 4 or the same hardware elements configured differently.

[0043] Also, while the data has been described in terms of bytes, this need not be the case. Other sizes of data may be, used in other implementations consistent with the present invention.

[0044] The scope of the invention is defined by the claims and their equivalents.