Browse Prior Art Database

Contiguous Byte Detection By Segmentation Disclosure Number: IPCOM000200050D
Publication Date: 2010-Sep-24
Document File: 5 page(s) / 349K

Publishing Venue

The Prior Art Database


The purpose of this invention is to provide an efficient method of determining whether two sets of data are contiguous. From a high level, the solution breaks down byte enables into smaller pieces and determines whether each piece is contiguous. The results are combined to determine whether the data is contiguous.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 01 of 5

Contiguous Byte Detection By Segmentation

Store gathering is only a single potential usage of this idea; there may be other usages. An advantage of this solution versus a pre-existing address based method of keeping the next sequential starting address is that it enables the design to gather stores in incrementing or decrementing address order. The address method could also enable this feature, but with added complexity. A beginning and ending address would have to be calculated. The gathering logic would have to look at the address and length of the new store and see if the final byte of the new store would be exactly one byte address before the beginning address of the existing data. Our solution provides this functionality without having to perform any additions or compares.

Figure 1 below shows an illustration of the problem we are solving with our invention. The figure shows two different pairs of byte enables. One belongs to some previous piece of data ("Existing"), while the other shows the new data ("New") which is arriving. The first pair of byte enables is contiguous because there are no invalid bytes between the first store and the second store. Looking at the resulting byte enables, between the first valid byte and the last valid byte, there are no invalid bytes. In the second pair of byte enables, there is one invalid byte between them; so, these are discontiguous.

Figures 2 through 4 show how the contiguous detection is performed using our solution for a contiguous case. Figures 5 through 7 show the same for a discontiguous case. In our examples, the byte enable vector is 16 bits wide for illustration simplicity (representing enables for 16 bytes).

How the Detection is Performed

First, the byte enable vector is broken down into 4-bit sections. In our examples (figures 2 and 5), where the byte enable vector is 16 bits wide, it is broken down into four, 4-bit sections. For each section, a brute-force determination of contiguous is determined. Specifically, each 4-bit section is discontiguous if it is equal to 4'b0101, 4'b1001, 4'b1010, 4'b1011, or 4'b1101.

In parallel, the byte enable vector is broken down into 8-bit sections. In our examples (figures 3 and 6), where the byte enable vector is 16 bits wide, it is broken down into two, 8-bit sections. The logic determines if the...