Apparatus and method for partitioning data blocks
View Patent ↗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.
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,
where the first algorithm is a high-speed data partitioning algorithm and the second algorithm is a low-speed data partitioning algorithm.
2. The method of claim 1 , where the first algorithm uses a first range of mean subblock length to determine the first boundary condition.
3. The method of claim 2 , where the second algorithm uses a second range of mean subblock length to determine the second boundary condition.
4. The method of claim 2 , where the first range comprises a range of 0 to 4095.
5. The method of claim 1 , where the second range is larger than the first range.
6. The method of claim 1 , where the first algorithm is represented by: HSPA(b1,b2,b3)=(((b1<<8) xor (b2<<4) xor b3)|p)==v, where HSPA is a Boolean function to test for boundary condition, where b1, b2, and b3 are bytes preceding the first data position, where << is left bit shift and >> is right bit shift, where p is a target mean subblock length having a range of 0 to 65535, and where v is a constant in the range [0,p−1].
7. The method of claim 6 , where p has a range of 0 to 4095.
8. The method of claim 6 , where the second algorithm is represented by: LSPA(c[−15..0])=((md5(c[−15..0])|2 32 )|q)=w, where 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 32−1 , and where w is a constant in the range [0,q−1].
9. The method of claim 1 , where the first and second algorithms are executed concurrently.
10. The method of claim 1 , where the second algorithm is executed based on a result from the first algorithm.
11. 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, where the first algorithm is a high-speed data partitioning algorithm and the second algorithm is a low-speed data partitioning algorithm.
12. The computer program product of claim 11 , 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.
13. The computer program product of claim 11 , comprising a computer readable program code that causes the computer to use a second range of mean subblock length to determine the second boundary condition.
14. The computer program product of claim 12 , where the first range comprises a range of 0 to 4095.
15. The computer program product of claim 14 , where the second range is larger than the first range.
16. The computer program product of claim 11 , where the first algorithm is represented by: HSPA(b1,b2,b3)=(((b1<<8) xor (b2<<4) xor b3)|p)==v, where HSPA is a Boolean function to test for boundary condition, where b1, b2, and b3 are bytes preceding the first data position, where << is left bit shift and >> is right bit shift, where p is a target mean subblock length having a range of 0 to 65535, and where v is a constant in the range [0,p−1].
17. The computer program product of claim 11 , where the second algorithm is represented by: LSPA(c[−15.0])=((md5(c[−15.0])|2 32 )|q)=w, where 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 32−1 , and where w is a constant in the range [0,q−1].
18. The computer program product of claim 11 , where the first and second algorithms are executed concurrently.
19. The computer program product of claim 11 , where the second algorithm is executed based on a result from the first algorithm.