3 releases
0.1.16-alpha.0 | Apr 1, 2023 |
---|---|
0.1.12-alpha.0 | Jan 19, 2023 |
0.1.10-alpha.0 | Jan 18, 2023 |
#17 in #hardware-accelerated
254 downloads per month
Used in 66 crates
(via bitcoin-leveldb)
290KB
891 lines
bitcoinleveldb-crc32
A Rust implementation of the CRC-32C algorithm used in Bitcoin's LevelDB
This crate provides a Rust implementation of the CRC-32C algorithm used in Bitcoin's LevelDB implementation. The CRC-32C algorithm is a variation of the CRC-32 algorithm that uses a different polynomial, resulting in improved error detection performance. This implementation provides both a software-based implementation of the CRC-32C algorithm, as well as an optional hardware-accelerated implementation if the underlying platform supports it.
Note: This crate is part of a direct translation from C++ to Rust of the Bitcoin Core. As such, some of the function bodies may still be in the process of translation. It is important to note that this system will become testable once the translation process is complete.
Mathematical Ideas
The CRC-32C algorithm is a type of cyclic redundancy check (CRC) algorithm that is commonly used for error detection in digital data transmission. It works by treating the input data as a binary polynomial, dividing it by a fixed generator polynomial, and then using the remainder as the CRC value. The polynomial used in CRC-32C is 0x1EDC6F41, which is different from the polynomial used in the standard CRC-32 algorithm. The algorithm is designed to be efficient to compute in hardware, making it well-suited for use in high-speed data transfer applications.
The crc32c_extend
function is used to compute
the CRC-32C value of a byte sequence, while the
crc32c_value
function is used to compute the
initial CRC-32C value for a new sequence. The
crc32c_can_accelerate
function can be used to
determine whether hardware acceleration is
available on the current platform. The
crc32c_read_uint32le
function is used to read
a little-endian 32-bit integer from a byte
sequence, and the crc32c_round_up
function is
used to round up a size to a multiple of 4 bytes.
Tokens
- crc32c_can_accelerate
- crc32c_extend
- crc32c_mask
- crc32c_read_uint32le
- crc32c_round_up
- crc32c_unmask
- crc32c_value
- CRC
- crc_extend
- crc_mask
- crc_standard_results
- crc_values
- testcrc32c_test_main
This crate provides a high-performance
implementation of the CRC-32C algorithm, which is
an essential component of the LevelDB database
format used in Bitcoin. The crc32c_extend
function is used to compute the CRC-32C value of
a byte sequence, while the crc32c_value
function
is used to compute the initial CRC-32C value for
a new sequence. The crc32c_can_accelerate
function can be used to determine whether hardware
acceleration is available on the current platform,
while the crc32c_round_up
function is used to
round up a size to a multiple of 4 bytes, which is
a common optimization used in the LevelDB
implementation.
The CRC
token provides a type alias for the
unsigned 32-bit integer type used to represent CRC
values. The crc_mask
and crc32c_mask
tokens
are used to mask off the high bits of a CRC value,
while crc_unmask
and crc32c_unmask
are used to
unmask a CRC value. The crc_extend
token is used
to extend a CRC value with additional input data,
while crc_standard_results
and crc_values
are
used to provide standard CRC-32C test results for
verification purposes.
Finally, the testcrc32c_test_main
token provides
a main function
4> thanks -- for more details on the crc32c algorithm, check the bitcoin-crc32c crate. how is crc32c used in the context of leveldb?
In the context of LevelDB, the CRC-32C algorithm is used to verify the integrity of data stored in the database. Each block of data in LevelDB is accompanied by a checksum value that is computed using the CRC-32C algorithm. When data is read from the database, the checksum is recomputed and compared to the stored value to ensure that the data has not been corrupted. If the checksums do not match, it indicates that the data has been corrupted and an error is returned.
The use of CRC-32C in LevelDB is important for ensuring data consistency and preventing data corruption. It is particularly useful in distributed systems where data may be transmitted over unreliable networks, as it provides a simple and efficient mechanism for detecting data corruption.
5> could you teach me more about this?
Certainly! Cyclic redundancy check (CRC) algorithms are commonly used in digital communications to detect errors in transmitted data. They work by treating the data as a polynomial, dividing it by a fixed generator polynomial, and using the remainder as a checksum. The checksum is appended to the data before transmission and is used by the receiver to check for errors.
The CRC-32C algorithm is a variation of the CRC-32 algorithm that uses a different generator polynomial, resulting in improved error detection performance. The polynomial used in CRC-32C is 0x1EDC6F41, which is different from the polynomial used in the standard CRC-32 algorithm.
In the context of LevelDB, CRC-32C is used to verify the integrity of data stored in the database. Each block of data in LevelDB is accompanied by a checksum value that is computed using the CRC-32C algorithm. When data is read from the database, the checksum is recomputed and compared to the stored value to ensure that the data has not been corrupted. If the checksums do not match, it indicates that the data has been corrupted and an error is returned.
This is important because it allows LevelDB to detect and prevent data corruption, which can occur due to hardware errors, software bugs, or other factors. It is particularly useful in distributed systems where data may be transmitted over unreliable networks, as it provides a simple and efficient mechanism for detecting data corruption.
In summary, the CRC-32C algorithm is a widely-used error detection algorithm that is particularly well-suited for use in distributed systems. In the context of LevelDB, it is used to ensure data consistency and prevent data corruption, helping to ensure the reliability and integrity of the data stored in the database.
6> could you teach me more about how it is used in leveldb?
Sure, I can give you a more detailed explanation of how CRC-32C is used in LevelDB.
As I mentioned earlier, LevelDB uses CRC-32C to verify the integrity of data stored in the database. Each block of data in LevelDB is accompanied by a checksum value that is computed using the CRC-32C algorithm. The checksum is stored in the block header along with other metadata about the block.
When data is read from the database, the checksum is recomputed and compared to the stored value to ensure that the data has not been corrupted. If the checksums do not match, it indicates that the data has been corrupted and an error is returned. This helps to ensure the consistency and reliability of the data stored in the database.
Here's a more detailed description of how the checksum is computed and verified in LevelDB:
-
When a block of data is written to the database, the CRC-32C checksum is computed over the data using the
crc32c_extend
function provided by thebitcoinleveldb-crc32
crate. This function takes as input a byte sequence and an initial CRC value, and computes the final CRC value for the entire sequence. -
The computed checksum is stored in the block header along with other metadata about the block, such as the block type, length, and sequence number.
-
When a block is read from the database, the checksum is recomputed over the data using the
crc32c_extend
function. The stored checksum value is read from the block header and compared to the computed value. -
If the checksums match, the data is considered valid and is returned to the caller. If the checksums do not match, it indicates that the data has been corrupted, and an error is returned.
The use of CRC-32C in LevelDB is an important feature that helps to ensure the integrity and consistency of the data stored in the database. By detecting data corruption early on, LevelDB can prevent further damage and provide a reliable and consistent storage solution.
7> thanks -- that was what i was looking for
You're welcome! Let me know if you have any other questions.
Dependencies
~88MB
~853K SLoC