| … | |
… | |
| 687 | } |
687 | } |
| 688 | |
688 | |
| 689 | /* merge two CRC32 such that result = crc32(dataB, lengthB, crc32(dataA, lengthA)) */ |
689 | /* merge two CRC32 such that result = crc32(dataB, lengthB, crc32(dataA, lengthA)) */ |
| 690 | uint32_t uu_crc32_combine(uint32_t crcA, uint32_t crcB, size_t lengthB) |
690 | uint32_t uu_crc32_combine(uint32_t crcA, uint32_t crcB, size_t lengthB) |
| 691 | { |
691 | { |
|
|
692 | int i; |
| 692 | /* |
693 | /* |
| 693 | * based on Mark Adler's crc_combine from |
694 | * based on Mark Adler's crc_combine from |
| 694 | * https://github.com/madler/pigz/blob/master/pigz.c |
695 | * https://github.com/madler/pigz/blob/master/pigz.c |
| 695 | |
696 | |
| 696 | * main idea: |
697 | * main idea: |
| … | |
… | |
| 728 | uint32_t odd [CrcBits]; /* odd-power-of-two zeros operator */ |
729 | uint32_t odd [CrcBits]; /* odd-power-of-two zeros operator */ |
| 729 | uint32_t even[CrcBits]; /* even-power-of-two zeros operator */ |
730 | uint32_t even[CrcBits]; /* even-power-of-two zeros operator */ |
| 730 | |
731 | |
| 731 | /* put operator for one zero bit in odd */ |
732 | /* put operator for one zero bit in odd */ |
| 732 | odd[0] = Polynomial; |
733 | odd[0] = Polynomial; |
| 733 | for (int i = 1; i < CrcBits; i++) |
734 | for (i = 1; i < CrcBits; i++) |
| 734 | odd[i] = 1 << (i - 1); |
735 | odd[i] = 1 << (i - 1); |
| 735 | |
736 | |
| 736 | /* put operator for two zero bits in even */ |
737 | /* put operator for two zero bits in even */ |
| 737 | /* same as gf2_matrix_square(even, odd); */ |
738 | /* same as gf2_matrix_square(even, odd); */ |
| 738 | for (int i = 0; i < CrcBits; i++) |
739 | for (i = 0; i < CrcBits; i++) |
| 739 | { |
740 | { |
|
|
741 | int j; |
| 740 | uint32_t vec = odd[i]; |
742 | uint32_t vec = odd[i]; |
| 741 | even[i] = 0; |
743 | even[i] = 0; |
| 742 | for (int j = 0; vec != 0; j++, vec >>= 1) |
744 | for (j = 0; vec != 0; j++, vec >>= 1) |
| 743 | if (vec & 1) |
745 | if (vec & 1) |
| 744 | even[i] ^= odd[j]; |
746 | even[i] ^= odd[j]; |
| 745 | } |
747 | } |
| 746 | /* put operator for four zero bits in odd */ |
748 | /* put operator for four zero bits in odd */ |
| 747 | /* same as gf2_matrix_square(odd, even); */ |
749 | /* same as gf2_matrix_square(odd, even); */ |
| 748 | for (int i = 0; i < CrcBits; i++) |
750 | for (i = 0; i < CrcBits; i++) |
| 749 | { |
751 | { |
|
|
752 | int j; |
| 750 | uint32_t vec = even[i]; |
753 | uint32_t vec = even[i]; |
| 751 | odd[i] = 0; |
754 | odd[i] = 0; |
| 752 | for (int j = 0; vec != 0; j++, vec >>= 1) |
755 | for (j = 0; vec != 0; j++, vec >>= 1) |
| 753 | if (vec & 1) |
756 | if (vec & 1) |
| 754 | odd[i] ^= even[j]; |
757 | odd[i] ^= even[j]; |
| 755 | } |
758 | } |
| 756 | |
759 | |
| 757 | /* the following loop becomes much shorter if I keep swapping even and odd */ |
760 | /* the following loop becomes much shorter if I keep swapping even and odd */ |
| … | |
… | |
| 759 | uint32_t* b = odd; |
762 | uint32_t* b = odd; |
| 760 | /* apply secondLength zeros to firstCrc32 */ |
763 | /* apply secondLength zeros to firstCrc32 */ |
| 761 | for (; lengthB > 0; lengthB >>= 1) |
764 | for (; lengthB > 0; lengthB >>= 1) |
| 762 | { |
765 | { |
| 763 | /* same as gf2_matrix_square(a, b); */ |
766 | /* same as gf2_matrix_square(a, b); */ |
| 764 | for (int i = 0; i < CrcBits; i++) |
767 | for (i = 0; i < CrcBits; i++) |
| 765 | { |
768 | { |
|
|
769 | int j; |
| 766 | uint32_t vec = b[i]; |
770 | uint32_t vec = b[i]; |
| 767 | a[i] = 0; |
771 | a[i] = 0; |
| 768 | for (int j = 0; vec != 0; j++, vec >>= 1) |
772 | for (j = 0; vec != 0; j++, vec >>= 1) |
| 769 | if (vec & 1) |
773 | if (vec & 1) |
| 770 | a[i] ^= b[j]; |
774 | a[i] ^= b[j]; |
| 771 | } |
775 | } |
| 772 | |
776 | |
| 773 | /* apply zeros operator for this bit */ |
777 | /* apply zeros operator for this bit */ |
| 774 | if (lengthB & 1) |
778 | if (lengthB & 1) |
| 775 | { |
779 | { |
| 776 | /* same as firstCrc32 = gf2_matrix_times(a, firstCrc32); */ |
780 | /* same as firstCrc32 = gf2_matrix_times(a, firstCrc32); */ |
| 777 | uint32_t sum = 0; |
781 | uint32_t sum = 0; |
| 778 | for (int i = 0; crcA != 0; i++, crcA >>= 1) |
782 | for (i = 0; crcA != 0; i++, crcA >>= 1) |
| 779 | if (crcA & 1) |
783 | if (crcA & 1) |
| 780 | sum ^= a[i]; |
784 | sum ^= a[i]; |
| 781 | crcA = sum; |
785 | crcA = sum; |
| 782 | } |
786 | } |
| 783 | |
787 | |
