Error detecting code with partial update
An approach for generating updated error detecting code for a partial update of data is disclosed. The techniques include receiving data representing a change to a portion of a data object, the data object having a first error detecting code, and the portion of the data object having an offset from the beginning of the data object; generating a combination term by combining the data and the portion of the data object; and computing a second error detecting code based on the combination term. The techniques may further include computing a third error detecting code by combining the first error detecting code and the second error detecting code, the third error detecting code being configured to detect an error in the data object as changed by the data, and storing the data and the third error detecting code.
1. A computer-implemented method comprising:
receiving modification data representing a change to a portion of a data object stored in a storage device, the data object having a length and a first error detecting code, and the portion of the data object starting at a beginning offset that is offset from a beginning of the data object and ending at an ending offset located past the beginning offset;
generating a combination term by combining the modification data representing the change to the portion of the data object and the portion of the data object;
computing a second error detecting code based on the combination term;
computing a third error detecting code by combining the first error detecting code and the second error detecting code, the third error detecting code being configured to detect an error in the data object as changed by the modification data; and
verifying, using the third error detecting code computed by combining the first error detecting code and the second error detecting code, an integrity of the data object as changed by the modification data.
2. The computer-implemented method of claim 1 , wherein generating the combination term by combining the modification data and the portion of the data object includes:
generating a first part of the combination term by writing a plurality of zeros equal to a length of the beginning offset of the portion of the data object; and
generating a second part of the combination term by performing a bitwise exclusive OR operation on the modification data and the portion of the data object.
3. The computer-implemented method of claim 2 , wherein computing the third error detecting code includes performing a bitwise exclusive OR operation on the first error detecting code and the second error detecting code.
4. The computer-implemented method of claim 1 , wherein generating the combination term by combining the modification data and the portion of the data object includes performing a bitwise exclusive OR operation on the modification data and the portion of the data object.
5. The computer-implemented method of claim 4 , wherein computing the third error detecting code includes:
computing a modification factor based on the offset;
generating an update term by combining the modification factor and the second error detecting code; and
combining the update term and the first error detecting code.
6. The computer-implemented method of claim 5 , wherein computing the modification factor based on the offset includes precomputing a portion of the modification factor.
7. The computer-implemented method of claim 1 , wherein the first error detecting code, the second error detecting code, and the third error detecting code include cyclic redundancy check code.
8. The computer-implemented method of claim 1 , further comprising updating the data object based on the modification data without reading the entire data object from the storage device.
9. A system comprising:
one or more processors; and
a memory storing instructions that, when executed by the one or more processors, cause the system to:
receive modification data representing a change to a portion of a data object stored in a storage device, the data object having a length and a first error detecting code, and the portion of the data object starting at a beginning offset that is offset from a beginning of the data object and ending at an ending offset located past the beginning offset;
generate a combination term by combining the modification data representing the change to the portion of the data object and the portion of the data object;
compute a second error detecting code based on the combination term;
compute a third error detecting code by combining the first error detecting code and the second error detecting code, the third error detecting code being configured to detect an error in the data object as changed by the modification data; and
verify, using the third error detecting code computed by combining the first error detecting code and the second error detecting code, an integrity of the data object as changed by the modification data.
10. The system of claim 9 , wherein to generate the combination term by combining the modification data and the portion of the data object includes to:
generate a first part of the combination term by writing a plurality of zeros equal to a length of the beginning offset of the portion of the data object; and
generate a second part of the combination term by performing a bitwise exclusive OR operation on the modification data and the portion of the data object.
11. The system of claim 10 , wherein to compute the third error detecting code includes to perform a bitwise exclusive OR operation on the first error detecting code and the second error detecting code.
12. The system of claim 9 , wherein to generate the combination term by combining the modification data and the portion of the data object includes to perform a bitwise exclusive OR operation on the modification data and the portion of the data object.
13. The system of claim 12 , wherein to compute the third error detecting code includes to:
compute a modification factor based on the beginning offset;
generate an update term by combining the modification factor and the second error detecting code; and
combine the update term and the first error detecting code.
14. The system of claim 13 , wherein to compute the modification factor based on the beginning offset includes to precompute a portion of the modification factor.
15. The system of claim 9 , wherein the first error detecting code, the second error detecting code, and the third error detecting code include cyclic redundancy check code.
16. The system of claim 9 , wherein the instructions, when executed by the one or more processors, further cause the system to modify the data object based on the modification data without reading the entire data object from the storage device.
17. A computer-implemented method comprising:
storing a data object in a storage device, the data object having a first cyclic redundancy check (CRC);
receiving modification data representing a modification to a portion of the data object, the portion of the data object being offset from a beginning of the data object and an ending of the data object in the storage device;
performing an exclusive OR operation on the modification data and the portion of the data object to generate a combination term;
computing a second CRC based on the combination term;
generating an update term based on the second CRC and the offset;
combining the first CRC and the update term to generate a third CRC, the third CRC being capable of checking for errors in the data object as modified by the modification data; and
verifying, using the third CRC generated by combining the first CRC and the update term, an integrity of the data object as modified by the modification data.
18. The computer-implemented method of claim 17 , further comprising:
modifying the portion of the data object in the storage device using the modification data to generate a modified data object; and
storing the third CRC in the storage device.
19. The computer-implemented method of claim 18 , further comprising checking the modified data object for errors using the third CRC.
20. The computer-implemented method of claim 17 , wherein the offset includes a number of bits between the beginning of the data object and a beginning of the portion of the data object.