Granted Patent B2

US 7,403,203 · App. 11/179,221 · Granted Jul 22, 2008

Abstract

Claims (73)

1. A method for efficiently storing frames of data in a plurality of contiguous frame buffers in a frame buffer memory when a frame size of the frames of data is not a power-of-two number of bytes, comprising:

partitioning the frame buffer memory into N frame-independent buffers, where N is a power-of-two, each frame-independent buffer representable by a M-bit frame-independent buffer number and having a frame-independent buffer size chosen to be a largest power-of-two value less than the frame size;

computing a residual buffer size as a difference between the frame size and the frame-independent buffer size; and

for each frame of data to be stored,

computing a frame buffer address S utilizing a particular frame-independent buffer number, the frame-independent buffer size and the residual buffer size, and

storing the frame of data into the frame buffer having the frame buffer address S, each frame buffer sized to match the non-power-of-two frame size of the frames of data.

2. The method as recited in claim 1 , further comprising:

for each frame of data to be stored, obtaining the particular frame-independent buffer number of a free frame-independent buffer.

3. The method as recited in claim 2 , further comprising:

storing the frame-independent buffer numbers of the free frame-independent buffers in a queue; and

for each frame of data to be stored, obtaining the particular frame-independent buffer number by popping it off the queue.

4. The method as recited in claim 1 , the step of computing a frame buffer address S further comprising:

multiplying the particular frame-independent buffer number and the frame-independent buffer size and adding a base address to obtain a partial frame buffer address Q;

multiplying the particular frame-independent buffer number and the residual buffer size to obtain a residual frame buffer address R; and

adding the partial frame buffer address Q and the residual frame buffer address R to obtain the frame buffer address S.

5. The method as recited in claim 1 , wherein when the residual buffer size is a power-of-two value, the step of computing a frame buffer address S further comprises:

shifting the particular frame-independent buffer number by a partial frame buffer shift value T, where T=log 2 (frame-independent buffer size), and adding a base address to obtain a partial frame buffer address Q;

shifting the particular frame-independent buffer number by a residual frame buffer shift value U, where U=log 2 (residual buffer size), to obtain a residual frame buffer address R; and

adding the partial frame buffer address Q and the residual frame buffer address R to obtain the frame buffer address S.

6. The method as recited in claim 1 , wherein when the residual buffer size is a power-of-two value, the step of computing a frame buffer address S further comprises:

loading the particular frame-independent buffer number into a partial frame buffer register with zeroes in the T Least Significant Bits (LSBs), where T=log 2 (frame-independent buffer size), and loading a base address into the Most Significant Bits (MSBs) of the partial frame buffer register to obtain a partial frame buffer address Q;

loading the particular frame-independent buffer number into a residual frame buffer register with zeroes in the U LSBs, where U=log 2 (residual buffer size), and loading zeroes into the MSBs of the residual frame buffer register, to obtain a residual frame buffer address R; and

adding the partial frame buffer address Q and the residual frame buffer address R to obtain the frame buffer address S.

7. The method as recited in claim 1 , wherein when a difference between the frame size and the frame-independent buffer size is a sum of a first power-of-two value and a second power-of-two value, the method further comprises:

determining the residual buffer size as the first power-of-two value rather than the difference between the frame size and the frame-independent buffer size;

determining a second residual buffer size as the second power-of-two value; and

computing the frame buffer address S by

shifting the particular frame-independent buffer number by a partial frame buffer shift value T, where T=log 2 (frame-independent buffer size), and adding a base address to obtain a partial frame buffer address Q,

shifting the particular frame-independent buffer number by a residual frame buffer shift value U, where U=log 2 (residual buffer size), to obtain a residual frame buffer address R,

shifting the particular frame-independent buffer number by a second residual frame buffer shift value V, where U=log 2 (second residual buffer size), to obtain a second residual frame buffer address W, and

adding the partial frame buffer address Q, the residual frame buffer address R, and the second residual frame buffer address W to obtain the frame buffer address S.

8. The method as recited in claim 1 , wherein when a difference between the frame size and the frame-independent buffer size is a sum of a first power-of-two value and a second power-of-two value, the method further comprises:

determining the residual buffer size as the first power-of-two value rather than the difference between the frame size and the frame-independent buffer size;

determining a second residual buffer size as the second power-of-two value; and

computing the frame buffer address S by

loading the particular frame-independent buffer number into a partial frame buffer register with zeroes in the T Least Significant Bits (LSBs), where T=log 2 (frame-independent buffer size), and loading a base address into the Most Significant Bits (MSBs) of the partial frame buffer register to obtain a partial frame buffer address Q,

loading the particular frame-independent buffer number into a residual frame buffer register with zeroes in the U LSBs, where U=log 2 (residual buffer size), and loading zeroes into the MSBs of the residual frame buffer register, to obtain a residual frame buffer address R,

loading the particular frame-independent buffer number into a second residual frame buffer register with zeroes in the V LSBs, where V=log 2 (second residual buffer size), and loading zeroes into the MSBs of the residual frame buffer register, to obtain a second residual frame buffer address W, and

adding the partial frame buffer address Q, the residual frame buffer address R, and the second residual frame buffer address W to obtain the frame buffer address S.

9. A system for efficiently storing frames of data in a plurality of contiguous frame buffers in a frame buffer memory when a frame size of the frames of data is not a power-of-two number of bytes, comprising:

a frame buffer memory partitioned into N frame-independent buffers, where N is a power-of-two, each frame-independent buffer representable by a M-bit frame-independent buffer number and having a frame-independent buffer size chosen to be a largest power-of-two value less than the frame size; and

a frame buffer address generator coupled to the frame buffer memory, the frame buffer address generator configured for storing a residual buffer size equal to a difference between the frame size and the frame-independent buffer size, and, for each frame of data to be stored, computing a frame buffer address S utilizing a particular frame-independent buffer number, the frame-independent buffer size and the residual buffer size, and storing the frame of data into the frame buffer having the frame buffer address S, each frame buffer sized to match the non-power-of-two frame size of the frames of data.

10. The system as recited in claim 9 , further comprising a queue coupled to the frame buffer address generator for storing the frame-independent buffer numbers of free frame-independent buffers and providing the particular frame-independent buffer number to the frame buffer address generator for each frame of data to be stored.

11. The system as recited in claim 9 , the frame buffer address generator further configured for computing the frame buffer address S by:

multiplying the particular frame-independent buffer number and the frame-independent buffer size and adding a base address to obtain a partial frame buffer address Q;

multiplying the particular frame-independent buffer number and the residual buffer size to obtain a residual frame buffer address R; and

adding the partial frame buffer address Q and the residual frame buffer address R to obtain the frame buffer address S.

12. The system as recited in claim 9 , the frame buffer address generator further configured such that when the residual buffer size is a power-of-two value, the frame buffer address generator computes the frame buffer address S by:

shifting the particular frame-independent buffer number by a partial frame buffer shift value T, where T=log 2 (frame-independent buffer size), and adding a base address to obtain a partial frame buffer address Q;

shifting the particular frame-independent buffer number by a residual frame buffer shift value U, where U=log 2 (residual buffer size), to obtain a residual frame buffer address R; and

adding the partial frame buffer address Q and the residual frame buffer address R to obtain the frame buffer address S.

13. The system as recited in claim 9 , the frame buffer address generator comprising:

a partial frame buffer register for loading the particular frame-independent buffer number into the partial frame buffer register with zeroes in the T Least Significant Bits (LSBs), where T=log 2 (frame-independent buffer size), and loading a base address into the Most Significant Bits (MSBs) of the partial frame buffer register to obtain a partial frame buffer address Q when the residual buffer size is a power-of-two value;

a residual frame buffer register for loading the particular frame-independent buffer number into the residual frame buffer register with zeroes in the U LSBs, where U=log 2 (residual buffer size), and loading zeroes into the MSBs of the residual frame buffer register to obtain a residual frame buffer address R when the residual buffer size is a power-of-two value; and

an adder coupled to the partial frame buffer register and the residual frame buffer register for adding the partial frame buffer address Q and the residual frame buffer address R to obtain the frame buffer address S when the residual buffer size is a power-of-two value.

14. The system as recited in claim 9 , the frame buffer address generator further configured such that when a difference between the frame size and the frame-independent buffer size is a sum of a first power-of-two value and a second power-of-two value, the frame buffer address generator computes the frame buffer address S by:

determining the residual buffer size as the first power-of-two value rather than the difference between the frame size and the frame-independent buffer size;

determining a second residual buffer size as the second power-of-two value;

shifting the particular frame-independent buffer number by a partial frame buffer shift value T, where T=log 2 (frame-independent buffer size), and adding a base address to obtain a partial frame buffer address Q;

shifting the particular frame-independent buffer number by a residual frame buffer shift value U, where U=log 2 (residual buffer size), to obtain a residual frame buffer address R;

shifting the particular frame-independent buffer number by a second residual frame buffer shift value V, where U=log 2 (second residual buffer size), to obtain a second residual frame buffer address W; and

adding the partial frame buffer address Q, the residual frame buffer address R, and the second residual frame buffer address W to obtain the frame buffer address S.

15. The system as recited in claim 9 , the frame buffer address generator further configured such that when a difference between the frame size and the frame-independent buffer size is a sum of a first power-of-two value and a second power-of-two value, the frame buffer address generator:

determines the residual buffer size as the first power-of-two value rather than the difference between the frame size and the frame-independent buffer size; and

determines a second residual buffer size as the second power-of-two value; and

wherein the frame buffer address generator further comprises

a partial frame buffer register for loading the particular frame-independent buffer number with zeroes in the T Least Significant Bits (LSBs), where T=log 2 (frame-independent buffer size), and loading a base address into the Most Significant Bits (MSBs) of the partial frame buffer register to obtain a partial frame buffer address Q,

a residual frame buffer register for loading the particular frame-independent buffer number with zeroes in the U LSBs, where U=log 2 (residual buffer size), and loading zeroes into the MSBs of the residual frame buffer register to obtain a residual frame buffer address R,

a second residual frame buffer register for loading the particular frame-independent buffer number with zeroes in the V LSBs, where V=log 2 (second residual buffer size), and loading zeroes into the MSBs of the residual frame buffer register to obtain a second residual frame buffer address W, and

an adder for adding the partial frame buffer address Q, the residual frame buffer address R, and the second residual frame buffer address W to obtain the frame buffer address S.

16. A Host Bus Adapter (HBA) comprising the system of claim 9 .

17. A host computer comprising the HBA of claim 16 .

18. A Storage Area Network (SAN) comprising the host computer of claim 17 .

Assignments (6)