Fast Software-based Table-less Algorithm for CRC Generation

This paper proposes a software-based CRC algorithm, which can be applied to CRCs with check values of different lengths. The proposed algorithm can be implemented by shift and XOR operations, and no look-up tables are needed. Therefore, it is suitable for processors with limited memory resources. Compared with table-based CRC algorithms, the proposed algorithm takes more instructions; however, the memory accesses are reduced significantly. As a result, for CRCs with specific generator polynomials, the implementation of the proposed algorithm achieves a high throughput. In the best cases, the proposed algorithm is 29% faster than the Sarwate algorithm for 16-bit CRC generation, and 45% faster than the Slicing-by-4 algorithm for 32-bit CRC generation. Furthermore, for 64-bit CRC generation, the proposed algorithm quadruples the throughput of the Slicing-by-4 algorithm at best.