| … | |
… | |
| 25 | */ |
25 | */ |
| 26 | |
26 | |
| 27 | #include "crc32.h" |
27 | #include "crc32.h" |
| 28 | |
28 | |
| 29 | #include "ecb.h" |
29 | #include "ecb.h" |
| 30 | #include <stdio.h>//D |
30 | |
|
|
31 | #define Polynomial 0xedb88320 |
| 31 | |
32 | |
| 32 | static const uint32_t crc32_lookup[16][256] = |
33 | static const uint32_t crc32_lookup[16][256] = |
| 33 | { |
34 | { |
| 34 | /* same algorithm as crc32_bitwise |
35 | /* same algorithm as crc32_bitwise |
| 35 | |
36 | |
| … | |
… | |
| 682 | crc = (crc >> 8) ^ crc32_lookup[0][(crc & 0xFF) ^ *current_char++]; |
683 | crc = (crc >> 8) ^ crc32_lookup[0][(crc & 0xFF) ^ *current_char++]; |
| 683 | |
684 | |
| 684 | return ~crc; |
685 | return ~crc; |
| 685 | } |
686 | } |
| 686 | |
687 | |
|
|
688 | /* merge two CRC32 such that result = crc32(dataB, lengthB, crc32(dataA, lengthA)) */ |
|
|
689 | uint32_t uu_crc32_combine(uint32_t crcA, uint32_t crcB, size_t lengthB) |
|
|
690 | { |
|
|
691 | /* |
|
|
692 | * based on Mark Adler's crc_combine from |
|
|
693 | * https://github.com/madler/pigz/blob/master/pigz.c |
|
|
694 | |
|
|
695 | * main idea: |
|
|
696 | * - if you have two equally-sized blocks A and B, |
|
|
697 | * then you can create a block C = A ^ B |
|
|
698 | * which has the property crc(C) = crc(A) ^ crc(B) |
|
|
699 | * - if you append length(B) zeros to A and call it A' (think of it as AAAA000) |
|
|
700 | * and prepend length(A) zeros to B and call it B' (think of it as 0000BBB) |
|
|
701 | * then exists a C' = A' ^ B' |
|
|
702 | * - remember: if you XOR someting with zero, it remains unchanged: X ^ 0 = X |
|
|
703 | * - that means C' = A concat B so that crc(A concat B) = crc(C') = crc(A') ^ crc(B') |
|
|
704 | * - the trick is to compute crc(A') based on crc(A) |
|
|
705 | * and crc(B') based on crc(B) |
|
|
706 | * - since B' starts with many zeros, the crc of those initial zeros is still zero |
|
|
707 | * - that means crc(B') = crc(B) |
|
|
708 | * - unfortunately the trailing zeros of A' change the crc, so usually crc(A') != crc(A) |
|
|
709 | * - the following code is a fast algorithm to compute crc(A') |
|
|
710 | * - starting with crc(A) and appending length(B) zeros, needing just log2(length(B)) iterations |
|
|
711 | * - the details are explained by the original author at |
|
|
712 | * https://stackoverflow.com/questions/23122312/crc-calculation-of-a-mostly-static-data-stream/23126768 |
|
|
713 | * |
|
|
714 | * notes: |
|
|
715 | * - I squeezed everything into one function to keep global namespace clean (original code two helper functions) |
|
|
716 | * - most original comments are still in place, I added comments where these helper functions where made inline code |
|
|
717 | * - performance-wise there isn't any differenze to the original zlib/pigz code |
|
|
718 | */ |
|
|
719 | |
|
|
720 | /* degenerated case */ |
|
|
721 | if (lengthB == 0) |
|
|
722 | return crcA; |
|
|
723 | |
|
|
724 | /* CRC32 => 32 bits */ |
|
|
725 | const uint32_t CrcBits = 32; |
|
|
726 | |
|
|
727 | uint32_t odd [CrcBits]; /* odd-power-of-two zeros operator */ |
|
|
728 | uint32_t even[CrcBits]; /* even-power-of-two zeros operator */ |
|
|
729 | |
|
|
730 | /* put operator for one zero bit in odd */ |
|
|
731 | odd[0] = Polynomial; |
|
|
732 | for (int i = 1; i < CrcBits; i++) |
|
|
733 | odd[i] = 1 << (i - 1); |
|
|
734 | |
|
|
735 | /* put operator for two zero bits in even */ |
|
|
736 | /* same as gf2_matrix_square(even, odd); */ |
|
|
737 | for (int i = 0; i < CrcBits; i++) |
|
|
738 | { |
|
|
739 | uint32_t vec = odd[i]; |
|
|
740 | even[i] = 0; |
|
|
741 | for (int j = 0; vec != 0; j++, vec >>= 1) |
|
|
742 | if (vec & 1) |
|
|
743 | even[i] ^= odd[j]; |
|
|
744 | } |
|
|
745 | /* put operator for four zero bits in odd */ |
|
|
746 | /* same as gf2_matrix_square(odd, even); */ |
|
|
747 | for (int i = 0; i < CrcBits; i++) |
|
|
748 | { |
|
|
749 | uint32_t vec = even[i]; |
|
|
750 | odd[i] = 0; |
|
|
751 | for (int j = 0; vec != 0; j++, vec >>= 1) |
|
|
752 | if (vec & 1) |
|
|
753 | odd[i] ^= even[j]; |
|
|
754 | } |
|
|
755 | |
|
|
756 | /* the following loop becomes much shorter if I keep swapping even and odd */ |
|
|
757 | uint32_t* a = even; |
|
|
758 | uint32_t* b = odd; |
|
|
759 | /* apply secondLength zeros to firstCrc32 */ |
|
|
760 | for (; lengthB > 0; lengthB >>= 1) |
|
|
761 | { |
|
|
762 | /* same as gf2_matrix_square(a, b); */ |
|
|
763 | for (int i = 0; i < CrcBits; i++) |
|
|
764 | { |
|
|
765 | uint32_t vec = b[i]; |
|
|
766 | a[i] = 0; |
|
|
767 | for (int j = 0; vec != 0; j++, vec >>= 1) |
|
|
768 | if (vec & 1) |
|
|
769 | a[i] ^= b[j]; |
|
|
770 | } |
|
|
771 | |
|
|
772 | /* apply zeros operator for this bit */ |
|
|
773 | if (lengthB & 1) |
|
|
774 | { |
|
|
775 | /* same as firstCrc32 = gf2_matrix_times(a, firstCrc32); */ |
|
|
776 | uint32_t sum = 0; |
|
|
777 | for (int i = 0; crcA != 0; i++, crcA >>= 1) |
|
|
778 | if (crcA & 1) |
|
|
779 | sum ^= a[i]; |
|
|
780 | crcA = sum; |
|
|
781 | } |
|
|
782 | |
|
|
783 | /* switch even and odd */ |
|
|
784 | uint32_t* t = a; a = b; b = t; |
|
|
785 | } |
|
|
786 | |
|
|
787 | /* return combined crc */ |
|
|
788 | return crcA ^ crcB; |
|
|
789 | } |
|
|
790 | |
