APPARATUS AND METHOD FOR PARTITIONING DATA BLOCKS

• US 20090265397A1
• Filed: 04/16/2008
• Published: 10/22/2009
• Est. Priority Date: 04/16/2008
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Williams, Ross N.
• Granted Patent: US 7,933,939 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 13/385 for adaptation of a particular data processing system to different peripheral devices

Abstract

A method and apparatus for increasing the speed at which a block of data can be partitioning into variable-length subblocks is provided. The method combines a relatively high-speed partitioning algorithm (that can only partition a block into relatively small mean-length subblocks) with a relatively low-speed algorithm (that can partition a block into subblocks of any mean length) to yield a relatively high-speed partitioning algorithm that can partition blocks into subblocks of any mean-length.

Claims

1. A method for partitioning a data block comprising:

determining a first boundary condition for the data block at a first data position using a first algorithm;

determining whether a boundary is needed based on a result of the first algorithm; and

determining the boundary location using a second algorithm if the first algorithm result indicates the boundary is needed.

2. The method of claim 1, wherein the first equation uses a first range of mean subblock length to determining the first boundary condition

3. The method of claim 2, wherein the second equation uses a second range of mean subblock length to determining the second boundary condition

4. The method of claim 2, wherein the first range comprises a range of 0 to 4095.

5. The method of claim 1, wherein the second range is larger than the first range.

6. The method of claim 1, wherein the first equation is represented by:

HSPA(b1,b2,b3)=(((b1<

<

8) xor (b2<

<

4) xor b3)|p)==v, wherein HSPA is a Boolean function to test for boundary condition, wherein b1, b2, and b3 are bytes preceding the first data position, wherein <

<

is left bit shift and >

>

is right bit shift, wherein p is a target mean subblock length having a range of 0 to 65535, and wherein v is a constant in the range [0,p−

1].

7. The method of claim 6, wherein p has a range of 0 to 4095.

8. The method of claim 6, wherein the second equation is represented by:

LSPA(c[−

15..0])=((md5(c[−

15..0])|2³²)|q)=w, wherein md5 is a cryptographic hash algorithm, c[15..0] comprises 16 bytes to the left of the first data position, q is a target mean subblock length having a range of 0−

2<sup>32−

1</sup>, and wherein w is a constant in the range [0,q−

1].

9. The method of claim 1, wherein the first and second equations are executed concurrently.

10. The method of claim 1, wherein the first equation is a high-speed data partitioning algorithm and the second equation is a low-speed data partitioning algorithm.

11. The method of claim 1, wherein the second equation is executed based on a result from the first equation.

12. A computer program product comprising a computer useable medium having computer readable program code functions embedded in the medium for partitioning a data block comprising:

computer readable program code that causes the computer to determine a first boundary condition for the data block at a first data position using a first algorithm

computer readable program code that causes the computer to determine whether a boundary is needed based on a result of the first algorithm;

and

computer readable program code that causes the computer to determine the boundary location using a second algorithm if the first algorithm indicates the boundary is needed.

13. The computer program product of claim 12, further comprising a computer readable program code that causes the computer to use a first range of mean subblock length to determining the first boundary condition

14. The computer program product of claim 12, further comprising a computer readable program code that causes the computer to use a second range of mean subblock length to determining the second boundary condition

15. The computer program product of claim 13, wherein the first range comprises a range of 0 to 4095.

16. The computer program product of claim 15, wherein the second range is larger than the first range.

17. The computer program product of claim 12, wherein the first equation is represented by:

HSPA(b1,b2,b3)=(((b1<

<

8) xor (b2<

<

4) xor b3)|p)==v, wherein HSPA is a Boolean function to test for boundary condition, wherein b1, b2, and b3 are bytes preceding the first data position, wherein <

<

is left bit shift and >

>

is right bit shift, wherein p is a target mean subblock length having a range of 0 to 65535, and wherein v is a constant in the range [0,p−

1].

18. The computer program product of claim 12, wherein the second equation is represented by:

LSPA(c[−

15..0])=((md5(c[−

15..0])|2³²)|q)=w, wherein md5 is a cryptographic hash algorithm, c[15..0] comprises 16 bytes to the left of the first data position, q is a target mean subblock length having a range of 0−

2<sup>32−

1</sup>, and wherein w is a constant in the range [0,q−

1].

19. The computer program product of claim 12, wherein the first and second equations are executed concurrently.

20. The computer program product of claim 12, wherein the second equation is executed based on a result from the first equation.

21. The computer program product of claim 12, wherein the first equation is a high-speed data partitioning algorithm and the second equation is a low-speed data partitioning algorithm.