base/crc.cc - Issue 624713003: Keep only base/extractor.[cc|h].

Unified Diff: base/crc.cc

Issue 624713003: Keep only base/extractor.[cc|h]. (Closed) Base URL: https://chromium.googlesource.com/external/omaha.git@master

Patch Set: Created 6 years, 2 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View side-by-side diff with in-line comments

Download patch

Index: base/crc.cc

diff --git a/base/crc.cc b/base/crc.cc

deleted file mode 100644

index fe3cb25c56dc314d3737fe35595cc59b916565df..0000000000000000000000000000000000000000

--- a/base/crc.cc

+++ /dev/null

@@ -1,899 +0,0 @@

-//

-// Licensed under the Apache License, Version 2.0 (the "License");

-// you may not use this file except in compliance with the License.

-// You may obtain a copy of the License at

-//

-// http://www.apache.org/licenses/LICENSE-2.0

-//

-// Unless required by applicable law or agreed to in writing, software

-// distributed under the License is distributed on an "AS IS" BASIS,

-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

-// See the License for the specific language governing permissions and

-// limitations under the License.

-// ========================================================================

-//

-// Implemetation of CRCs (aka Rabin Fingerprints).

-// Treats the input as a polynomial with coefficients in Z(2),

-// and finds the remainder when divided by an irreducible polynomial

-// of the appropriate length.

-// It handles all CRC sizes from 8 to 128 bits.

-// It's somewhat complicated by having separate implementations optimized for

-// CRC's <=32 bits, <= 64 bits, and <= 128 bits.

-// The input string is prefixed with a "1" bit, and has "degree" "0" bits

-// appended to it before the remainder is found. This ensures that

-// short strings are scrambled somewhat and that strings consisting

-// of all nulls have a non-zero CRC.

-#include <stddef.h>

-#include "omaha/base/crc.h"

-#include "omaha/base/debug.h"

-#include "omaha/base/commontypes.h"

-namespace omaha {

-static const int SMALL_BITS = 8;

- // When extending an input with a string of zeroes,

- // if the number of zeroes is less than 2**SMALL_BITS,

- // a normal Extend is done, rather than a polynomial

- // multiplication.

-static const char zeroes[1 << SMALL_BITS] = { 0 }; // an array of zeroes

-static const uint8 *zero_ptr = 0; // The 0 pointer---used for alignment

-// These are used to index a 2-entry array of words that together

-// for a longer integer. LO indexes the low-order half.

-#define LO 0

-#define HI (1-LO)

-// Constructor and destructor for baseclase CRC.

-CRC::~CRC() {}

-CRC::CRC() {}

-struct CRC_pair { // Used to represent a 128-bit value

- uint64 lo;

- uint64 hi;

-};

-class CRCImpl : public CRC { // Implemention of the abstract class CRC

- public:

- CRCImpl() {}

- virtual ~CRCImpl() {}

- // The internal version of CRC::New().

- static CRCImpl *NewInternal(uint64 lo, uint64 hi,

- int degree, size_t roll_length);

- virtual void Empty(uint64 *lo, uint64 *hi) const;

- size_t roll_length_; // length of window in rolling CRC

- int degree_; // bits in the CRC

- uint64 poly_lo_; // The CRC of the empty string, low part

- uint64 poly_hi_; // The CRC of the empty string, high part

- private:

- DISALLOW_EVIL_CONSTRUCTORS(CRCImpl);

-};

-// This is the 32-bit implementation. It handles all sizes from 8 to 32.

-class CRC32 : public CRCImpl {

- public:

- CRC32() {}

- virtual ~CRC32() {}

- virtual void Extend(uint64 *lo, uint64 *hi,

- const void *bytes, size_t length) const;

- virtual void ExtendByZeroes(uint64 *lo, uint64 *hi, size_t length) const;

- virtual void Roll(uint64 *lo, uint64 *hi, uint8 o_byte, uint8 i_byte) const;

- uint32 table0_[256]; // table of byte extensions

- uint32 table1_[256]; // table of byte extensions, shifted by 1 byte

- uint32 table2_[256]; // table of byte extensions, shifted by 2 bytes

- uint32 table3_[256]; // table of byte extensions, shifted by 3 bytes

- uint32 roll_[256]; // table of byte roll values

- uint32 zeroes_[256]; // table of zero extensions

- private:

- DISALLOW_EVIL_CONSTRUCTORS(CRC32);

-};

-static const uint64 UINT64_ZERO = 0; // a 64-bit zero

-static const uint64 UINT64_ONE = 1; // a 64-bit 1

-// The B() macro sets the bit corresponding to X**(_x) in the polynomial

-#define B(_x) (UINT64_ONE << ((_x) < 64?(63-(_x)):(127-(_x))))

-// Used to initialize polynomials.

-// The redundant tests on _len are to avoid warnings from the

-// compiler about inappropriate shift lengths. These shifts

-// occur on not-taken branch of the ?: in some cases.

-#define kDefPoly(_h,_l,_len) \

- { ((_len) <= 64 ? (_l) >> ((_len) <= 64? 64 - (_len): 0) : \

- (_len) == 128 ? (_h) : \

- ((_h) >> ((_len) > 64? 128 - (_len): 0)) | \

- ((_l) << ((_len) > 64 && (_len) < 128? (_len)-64: 0))), \

- ((_len) <= 64 ? 0 : \

- (_len) == 128 ? (_l) : \

- (_l) >> ((_len) > 64? 128 - (_len): 0)), \

- (_len) }

-// A table of irreducible polynomials suitable for use with the implementation.

-// Indexes 0...1 have degree 32 polynomials.

-// Indexes 2...3 have degree 64 polynomials.

-// Indexes 4...5 have degree 96 polynomials.

-// Indexes 6...7 have degree 128 polynomials.

-// Index i=8...128 has a degree i polynomial.

-// All polynomials in the table are guaranteed distinct.

-// lint -save -e572 -e648 -e778 Excessive shift value, expression evaluates to 0

-static const struct CRC::Poly poly_list[] = {

- kDefPoly(UINT64_ZERO, B(30)+B(27)+B(26)+B(25)+B(23)+B(20)+B(17)+B(15)+B(14)+

- B(12)+B(6)+B(5)+B(2)+B(0), 32),

- kDefPoly(UINT64_ZERO, B(31)+B(28)+B(27)+B(26)+B(24)+B(22)+B(19)+B(18)+B(16)+

- B(13)+B(11)+B(10)+B(9)+B(4)+B(2)+B(0), 32),

- kDefPoly(UINT64_ZERO, B(60)+B(59)+B(58)+B(56)+B(55)+B(54)+B(51)+B(50)+B(49)+

- B(48)+B(47)+B(45)+B(44)+B(42)+B(40)+B(39)+B(38)+B(36)+B(34)+B(33)+

- B(32)+B(31)+B(30)+B(27)+B(25)+B(23)+B(22)+B(21)+B(20)+B(19)+

- B(17)+B(16)+B(15)+B(8)+B(7)+B(6)+B(5)+B(0), 64),

- kDefPoly(UINT64_ZERO, B(63)+B(62)+B(60)+B(58)+B(57)+B(56)+B(54)+B(52)+B(46)+

- B(45)+B(43)+B(40)+B(37)+B(36)+B(34)+B(33)+B(32)+B(31)+B(30)+B(29)+

- B(28)+B(27)+B(26)+B(23)+B(19)+B(18)+B(15)+B(14)+B(13)+B(9)+B(8)+

- B(0), 64),

- kDefPoly(B(95)+B(94)+B(91)+B(90)+B(89)+B(88)+B(87)+B(86)+B(79)+B(78)+

- B(77)+B(76)+B(75)+B(74)+B(73)+B(69)+B(68)+B(66), B(63)+B(61)+

- B(59)+B(57)+B(53)+B(51)+B(50)+B(47)+B(40)+B(39)+B(38)+B(36)+

- B(35)+B(33)+B(29)+B(28)+B(27)+B(25)+B(24)+B(23)+B(21)+B(19)+

- B(18)+B(17)+B(16)+B(13)+B(12)+B(10)+B(9)+B(7)+B(4)+B(2)+B(1)+

- B(0), 96),

- kDefPoly(B(95)+B(92)+B(89)+B(88)+B(87)+B(85)+B(84)+B(82)+B(81)+B(80)+

- B(79)+B(78)+B(76)+B(75)+B(70)+B(69)+B(66)+B(65), B(60)+B(56)+

- B(55)+B(52)+B(51)+B(49)+B(48)+B(46)+B(44)+B(42)+B(41)+B(39)+

- B(38)+B(37)+B(35)+B(33)+B(32)+B(30)+B(28)+B(27)+B(25)+B(22)+

- B(19)+B(17)+B(14)+B(12)+B(10)+B(0), 96),

- kDefPoly(B(122)+B(121)+B(120)+B(119)+B(117)+B(116)+B(114)+B(113)+B(112)+

- B(111)+B(109)+B(107)+B(104)+B(102)+B(100)+B(98)+B(96)+B(94)+

- B(93)+B(92)+B(91)+B(90)+B(88)+B(87)+B(86)+B(84)+B(82)+B(80)+

- B(75)+B(74)+B(73)+B(69), B(62)+B(61)+B(58)+B(52)+B(48)+B(47)+

- B(46)+B(45)+B(42)+B(41)+B(38)+B(37)+B(35)+B(33)+B(32)+B(31)+

- B(30)+B(28)+B(26)+B(24)+B(22)+B(21)+B(20)+B(19)+B(18)+B(17)+

- B(10)+B(9)+B(8)+B(7)+B(5)+B(2)+B(1)+B(0), 128),

- kDefPoly(B(127)+B(126)+B(124)+B(121)+B(117)+B(116)+B(115)+B(113)+B(112)+

- B(111)+B(108)+B(105)+B(104)+B(103)+B(100)+B(98)+B(96)+B(93)+

- B(92)+B(90)+B(89)+B(88)+B(86)+B(85)+B(80)+B(77)+B(76)+B(72)+

- B(70)+B(69)+B(68)+B(65)+B(64), B(62)+B(61)+B(59)+B(58)+B(56)+

- B(53)+B(52)+B(51)+B(50)+B(48)+B(46)+B(39)+B(35)+B(34)+B(33)+

- B(32)+B(30)+B(29)+B(28)+B(22)+B(21)+B(19)+B(18)+B(17)+B(14)+

- B(10)+B(9)+B(7)+B(5)+B(4)+B(3)+B(2)+B(0), 128),

- kDefPoly(UINT64_ZERO, B(7)+B(6)+B(5)+B(4)+B(2)+B(0), 8),

- kDefPoly(UINT64_ZERO, B(8)+B(4)+B(3)+B(2)+B(1)+B(0), 9),

- kDefPoly(UINT64_ZERO, B(8)+B(6)+B(5)+B(3)+B(1)+B(0), 10),

- kDefPoly(UINT64_ZERO, B(10)+B(9)+B(7)+B(5)+B(1)+B(0), 11),

- kDefPoly(UINT64_ZERO, B(11)+B(10)+B(5)+B(2)+B(1)+B(0), 12),

- kDefPoly(UINT64_ZERO, B(12)+B(11)+B(10)+B(8)+B(5)+B(3)+B(2)+B(0), 13),

- kDefPoly(UINT64_ZERO, B(11)+B(10)+B(9)+B(8)+B(7)+B(5)+B(4)+B(2)+B(1)+

- B(0), 14),

- kDefPoly(UINT64_ZERO, B(14)+B(12)+B(11)+B(10)+B(9)+B(5)+B(3)+B(2)+B(1)+

- B(0), 15),

- kDefPoly(UINT64_ZERO, B(12)+B(11)+B(7)+B(6)+B(5)+B(4)+B(3)+B(0), 16),

- kDefPoly(UINT64_ZERO, B(16)+B(14)+B(11)+B(10)+B(8)+B(3)+B(1)+B(0), 17),

- kDefPoly(UINT64_ZERO, B(12)+B(11)+B(9)+B(8)+B(7)+B(4)+B(3)+B(0), 18),

- kDefPoly(UINT64_ZERO, B(12)+B(11)+B(8)+B(7)+B(6)+B(5)+B(2)+B(0), 19),

- kDefPoly(UINT64_ZERO, B(18)+B(15)+B(14)+B(12)+B(9)+B(6)+B(3)+B(0), 20),

- kDefPoly(UINT64_ZERO, B(20)+B(19)+B(14)+B(13)+B(12)+B(11)+B(8)+B(7)+B(6)+

- B(5)+B(2)+B(0), 21),

- kDefPoly(UINT64_ZERO, B(21)+B(20)+B(18)+B(16)+B(15)+B(14)+B(12)+B(9)+B(7)+

- B(2)+B(1)+B(0), 22),

- kDefPoly(UINT64_ZERO, B(22)+B(21)+B(17)+B(16)+B(15)+B(14)+B(12)+B(10)+B(7)+

- B(4)+B(1)+B(0), 23),

- kDefPoly(UINT64_ZERO, B(23)+B(22)+B(21)+B(18)+B(17)+B(15)+B(14)+B(12)+B(4)+

- B(0), 24),

- kDefPoly(UINT64_ZERO, B(24)+B(23)+B(22)+B(20)+B(18)+B(17)+B(14)+B(13)+B(9)+

- B(0), 25),

- kDefPoly(UINT64_ZERO, B(25)+B(22)+B(21)+B(19)+B(17)+B(15)+B(14)+B(12)+B(11)+

- B(10)+B(6)+B(4)+B(3)+B(0), 26),

- kDefPoly(UINT64_ZERO, B(26)+B(25)+B(19)+B(17)+B(16)+B(13)+B(5)+B(4)+B(1)+

- B(0), 27),

- kDefPoly(UINT64_ZERO, B(23)+B(22)+B(21)+B(20)+B(19)+B(18)+B(13)+B(12)+B(10)+

- B(9)+B(8)+B(6)+B(5)+B(3)+B(1)+B(0), 28),

- kDefPoly(UINT64_ZERO, B(27)+B(26)+B(25)+B(23)+B(22)+B(20)+B(19)+B(15)+B(14)+

- B(11)+B(10)+B(8)+B(7)+B(6)+B(4)+B(0), 29),

- kDefPoly(UINT64_ZERO, B(29)+B(27)+B(25)+B(23)+B(20)+B(19)+B(18)+B(17)+B(16)+

- B(14)+B(11)+B(10)+B(9)+B(7)+B(6)+B(5)+B(4)+B(0), 30),

- kDefPoly(UINT64_ZERO, B(30)+B(29)+B(28)+B(27)+B(25)+B(23)+B(22)+B(21)+B(20)+

- B(19)+B(18)+B(16)+B(15)+B(10)+B(9)+B(8)+B(4)+B(3)+B(1)+B(0), 31),

- kDefPoly(UINT64_ZERO, B(31)+B(29)+B(28)+B(27)+B(21)+B(20)+B(15)+B(13)+B(10)+

- B(9)+B(8)+B(7)+B(4)+B(3)+B(2)+B(0), 32),

- kDefPoly(UINT64_ZERO, B(32)+B(31)+B(30)+B(29)+B(27)+B(25)+B(24)+B(22)+B(21)+

- B(19)+B(15)+B(10)+B(4)+B(3)+B(2)+B(0), 33),

- kDefPoly(UINT64_ZERO, B(30)+B(27)+B(26)+B(25)+B(24)+B(20)+B(19)+B(18)+B(16)+

- B(15)+B(14)+B(12)+B(9)+B(8)+B(7)+B(5)+B(1)+B(0), 34),

- kDefPoly(UINT64_ZERO, B(34)+B(32)+B(28)+B(27)+B(26)+B(22)+B(21)+B(20)+B(19)+

- B(14)+B(13)+B(12)+B(10)+B(6)+B(5)+B(4)+B(3)+B(0), 35),

- kDefPoly(UINT64_ZERO, B(35)+B(34)+B(33)+B(32)+B(31)+B(28)+B(26)+B(24)+B(22)+

- B(21)+B(20)+B(19)+B(18)+B(14)+B(13)+B(12)+B(10)+B(9)+B(8)+B(6)+B(5)+

- B(4)+B(3)+B(0), 36),

- kDefPoly(UINT64_ZERO, B(36)+B(35)+B(31)+B(30)+B(28)+B(26)+B(25)+B(23)+B(22)+

- B(20)+B(19)+B(18)+B(16)+B(13)+B(12)+B(7)+B(6)+B(4)+B(3)+B(0), 37),

- kDefPoly(UINT64_ZERO, B(37)+B(34)+B(33)+B(32)+B(31)+B(30)+B(29)+B(28)+B(27)+

- B(26)+B(25)+B(23)+B(18)+B(16)+B(15)+B(13)+B(12)+B(11)+B(10)+B(9)+

- B(8)+B(7)+B(6)+B(2)+B(1)+B(0), 38),

- kDefPoly(UINT64_ZERO, B(38)+B(37)+B(33)+B(32)+B(31)+B(27)+B(25)+B(24)+B(21)+

- B(20)+B(19)+B(18)+B(17)+B(15)+B(14)+B(8)+B(7)+B(6)+B(3)+B(2)+B(1)+

- B(0), 39),

- kDefPoly(UINT64_ZERO, B(38)+B(37)+B(35)+B(34)+B(32)+B(31)+B(30)+B(27)+B(24)+

- B(21)+B(20)+B(14)+B(13)+B(11)+B(8)+B(4)+B(2)+B(0), 40),

- kDefPoly(UINT64_ZERO, B(38)+B(36)+B(35)+B(34)+B(33)+B(31)+B(30)+B(29)+B(28)+

- B(27)+B(23)+B(22)+B(20)+B(19)+B(18)+B(17)+B(15)+B(14)+B(11)+B(5)+

- B(4)+B(0), 41),

- kDefPoly(UINT64_ZERO, B(41)+B(37)+B(36)+B(35)+B(32)+B(31)+B(30)+B(29)+B(28)+

- B(25)+B(19)+B(18)+B(14)+B(13)+B(12)+B(7)+B(6)+B(4)+B(2)+B(0), 42),

- kDefPoly(UINT64_ZERO, B(42)+B(40)+B(38)+B(37)+B(36)+B(35)+B(34)+B(33)+B(31)+

- B(29)+B(27)+B(26)+B(25)+B(23)+B(21)+B(20)+B(19)+B(15)+B(11)+B(10)+

- B(9)+B(8)+B(6)+B(5)+B(3)+B(0), 43),

- kDefPoly(UINT64_ZERO, B(43)+B(42)+B(40)+B(39)+B(37)+B(35)+B(32)+B(30)+B(26)+

- B(25)+B(24)+B(20)+B(16)+B(13)+B(12)+B(11)+B(8)+B(6)+B(5)+B(4)+B(1)+

- B(0), 44),

- kDefPoly(UINT64_ZERO, B(43)+B(42)+B(41)+B(40)+B(39)+B(38)+B(33)+B(32)+B(27)+

- B(26)+B(25)+B(23)+B(20)+B(18)+B(17)+B(16)+B(14)+B(11)+B(10)+B(9)+

- B(6)+B(5)+B(1)+B(0), 45),

- kDefPoly(UINT64_ZERO, B(45)+B(43)+B(42)+B(41)+B(40)+B(39)+B(32)+B(31)+B(30)+

- B(29)+B(27)+B(25)+B(23)+B(18)+B(17)+B(16)+B(10)+B(9)+B(7)+B(6)+B(4)+

- B(3)+B(2)+B(0), 46),

- kDefPoly(UINT64_ZERO, B(45)+B(44)+B(43)+B(41)+B(40)+B(39)+B(38)+B(37)+B(32)+

- B(30)+B(23)+B(21)+B(20)+B(17)+B(15)+B(13)+B(11)+B(10)+B(7)+B(5)+

- B(3)+B(0), 47),

- kDefPoly(UINT64_ZERO, B(46)+B(42)+B(41)+B(39)+B(37)+B(36)+B(35)+B(29)+B(28)+

- B(25)+B(24)+B(21)+B(20)+B(18)+B(17)+B(13)+B(12)+B(11)+B(10)+B(9)+

- B(8)+B(5)+B(1)+B(0), 48),

- kDefPoly(UINT64_ZERO, B(48)+B(44)+B(41)+B(40)+B(39)+B(38)+B(37)+B(36)+B(35)+

- B(34)+B(30)+B(28)+B(27)+B(24)+B(21)+B(18)+B(17)+B(8)+B(3)+B(0), 49),

- kDefPoly(UINT64_ZERO, B(48)+B(47)+B(46)+B(45)+B(44)+B(43)+B(42)+B(35)+B(33)+

- B(29)+B(26)+B(24)+B(23)+B(21)+B(18)+B(16)+B(14)+B(13)+B(12)+B(9)+

- B(7)+B(6)+B(5)+B(4)+B(3)+B(0), 50),

- kDefPoly(UINT64_ZERO, B(47)+B(46)+B(45)+B(44)+B(43)+B(40)+B(39)+B(38)+B(36)+

- B(35)+B(30)+B(29)+B(28)+B(26)+B(25)+B(24)+B(23)+B(22)+B(20)+B(19)+

- B(18)+B(17)+B(15)+B(11)+B(7)+B(4)+B(3)+B(0), 51),

- kDefPoly(UINT64_ZERO, B(51)+B(46)+B(43)+B(38)+B(37)+B(36)+B(34)+B(31)+B(27)+

- B(26)+B(20)+B(17)+B(16)+B(15)+B(13)+B(12)+B(11)+B(9)+B(7)+B(5)+B(1)+

- B(0), 52),

- kDefPoly(UINT64_ZERO, B(50)+B(49)+B(47)+B(46)+B(44)+B(42)+B(41)+B(37)+B(36)+

- B(35)+B(33)+B(29)+B(28)+B(26)+B(24)+B(23)+B(21)+B(20)+B(14)+B(13)+

- B(12)+B(11)+B(10)+B(9)+B(8)+B(6)+B(3)+B(2)+B(1)+B(0), 53),

- kDefPoly(UINT64_ZERO, B(52)+B(47)+B(46)+B(44)+B(43)+B(42)+B(40)+B(36)+B(32)+

- B(31)+B(30)+B(29)+B(28)+B(26)+B(25)+B(24)+B(23)+B(22)+B(20)+B(19)+

- B(17)+B(16)+B(15)+B(14)+B(13)+B(12)+B(11)+B(10)+B(7)+B(4)+B(2)+

- B(0), 54),

- kDefPoly(UINT64_ZERO, B(53)+B(50)+B(48)+B(47)+B(37)+B(35)+B(31)+B(30)+B(25)+

- B(22)+B(21)+B(20)+B(19)+B(18)+B(15)+B(10)+B(8)+B(6)+B(3)+B(2)+B(1)+

- B(0), 55),

- kDefPoly(UINT64_ZERO, B(54)+B(52)+B(51)+B(49)+B(48)+B(42)+B(38)+B(37)+B(31)+

- B(30)+B(27)+B(26)+B(24)+B(23)+B(22)+B(19)+B(16)+B(12)+B(11)+B(8)+

- B(6)+B(4)+B(3)+B(0), 56),

- kDefPoly(UINT64_ZERO, B(55)+B(54)+B(51)+B(49)+B(48)+B(47)+B(46)+B(44)+B(43)+

- B(42)+B(41)+B(40)+B(39)+B(38)+B(32)+B(29)+B(27)+B(26)+B(23)+B(21)+

- B(20)+B(15)+B(12)+B(7)+B(6)+B(5)+B(3)+B(0), 57),

- kDefPoly(UINT64_ZERO, B(57)+B(54)+B(52)+B(47)+B(45)+B(42)+B(41)+B(40)+B(39)+

- B(36)+B(34)+B(33)+B(31)+B(28)+B(26)+B(21)+B(20)+B(18)+B(17)+B(16)+

- B(13)+B(11)+B(8)+B(7)+B(4)+B(2)+B(1)+B(0), 58),

- kDefPoly(UINT64_ZERO, B(58)+B(56)+B(54)+B(49)+B(47)+B(46)+B(43)+B(40)+B(38)+

- B(36)+B(35)+B(33)+B(32)+B(31)+B(30)+B(27)+B(24)+B(22)+B(21)+B(19)+

- B(17)+B(16)+B(11)+B(10)+B(9)+B(8)+B(7)+B(4)+B(3)+B(2)+B(1)+B(0),

- 59),

- kDefPoly(UINT64_ZERO, B(56)+B(54)+B(51)+B(46)+B(43)+B(42)+B(40)+B(39)+B(37)+

- B(35)+B(34)+B(33)+B(32)+B(31)+B(30)+B(29)+B(27)+B(25)+B(22)+B(21)+

- B(20)+B(19)+B(17)+B(16)+B(15)+B(14)+B(13)+B(12)+B(9)+B(7)+B(4)+

- B(3)+B(1)+B(0), 60),

- kDefPoly(UINT64_ZERO, B(59)+B(58)+B(57)+B(56)+B(54)+B(53)+B(50)+B(49)+B(47)+

- B(44)+B(42)+B(41)+B(40)+B(37)+B(35)+B(34)+B(32)+B(30)+B(29)+B(27)+

- B(26)+B(22)+B(21)+B(20)+B(17)+B(14)+B(13)+B(12)+B(8)+B(5)+B(4)+

- B(0), 61),

- kDefPoly(UINT64_ZERO, B(61)+B(59)+B(57)+B(55)+B(54)+B(53)+B(52)+B(51)+B(50)+

- B(49)+B(48)+B(45)+B(44)+B(40)+B(37)+B(35)+B(32)+B(31)+B(29)+B(25)+

- B(24)+B(23)+B(20)+B(17)+B(16)+B(15)+B(13)+B(12)+B(11)+B(10)+B(6)+

- B(5)+B(2)+B(0), 62),

- kDefPoly(UINT64_ZERO, B(62)+B(57)+B(56)+B(53)+B(52)+B(51)+B(50)+B(46)+B(41)+

- B(38)+B(35)+B(34)+B(33)+B(31)+B(27)+B(25)+B(23)+B(21)+B(19)+B(18)+

- B(17)+B(16)+B(13)+B(11)+B(7)+B(5)+B(1)+B(0), 63),

- kDefPoly(UINT64_ZERO, B(62)+B(61)+B(60)+B(57)+B(55)+B(54)+B(53)+B(49)+B(48)+

- B(46)+B(44)+B(42)+B(40)+B(39)+B(37)+B(36)+B(28)+B(27)+B(25)+B(23)+

- B(22)+B(21)+B(17)+B(15)+B(13)+B(7)+B(6)+B(4)+B(2)+B(0), 64),

- kDefPoly(UINT64_ZERO, B(63)+B(62)+B(59)+B(57)+B(54)+B(53)+B(51)+B(48)+

- B(47)+B(46)+B(45)+B(44)+B(41)+B(40)+B(38)+B(36)+B(35)+B(28)+

- B(25)+B(24)+B(21)+B(20)+B(18)+B(16)+B(15)+B(13)+B(11)+B(8)+B(7)+

- B(3)+B(1)+B(0), 65),

- kDefPoly(UINT64_ZERO, B(63)+B(58)+B(57)+B(56)+B(52)+B(51)+B(50)+B(44)+

- B(41)+B(40)+B(36)+B(34)+B(32)+B(31)+B(27)+B(25)+B(23)+B(21)+

- B(20)+B(19)+B(18)+B(17)+B(15)+B(14)+B(12)+B(11)+B(10)+B(8)+B(5)+

- B(4)+B(3)+B(0), 66),

- kDefPoly(B(66), B(62)+B(60)+B(59)+B(58)+B(57)+B(56)+B(55)+B(54)+B(52)+

- B(50)+B(47)+B(46)+B(45)+B(43)+B(42)+B(41)+B(38)+B(37)+B(36)+

- B(33)+B(32)+B(31)+B(30)+B(28)+B(27)+B(26)+B(24)+B(21)+B(18)+

- B(17)+B(14)+B(13)+B(12)+B(11)+B(10)+B(7)+B(4)+B(3)+B(0), 67),

- kDefPoly(B(67)+B(66), B(63)+B(61)+B(57)+B(55)+B(51)+B(47)+B(45)+B(43)+

- B(42)+B(41)+B(40)+B(39)+B(32)+B(31)+B(30)+B(28)+B(27)+B(25)+

- B(19)+B(18)+B(17)+B(15)+B(11)+B(9)+B(8)+B(7)+B(6)+B(5)+B(4)+B(3)+

- B(1)+B(0), 68),

- kDefPoly(B(68), B(60)+B(57)+B(55)+B(54)+B(52)+B(50)+B(49)+B(48)+B(44)+

- B(40)+B(38)+B(37)+B(33)+B(31)+B(28)+B(25)+B(22)+B(21)+B(20)+

- B(19)+B(18)+B(17)+B(13)+B(12)+B(9)+B(8)+B(6)+B(5)+B(4)+B(1)+

- B(0), 69),

- kDefPoly(B(69)+B(68)+B(67)+B(66), B(63)+B(62)+B(61)+B(59)+B(51)+B(49)+

- B(48)+B(46)+B(45)+B(42)+B(40)+B(38)+B(36)+B(35)+B(33)+B(32)+

- B(30)+B(29)+B(27)+B(23)+B(22)+B(21)+B(16)+B(12)+B(5)+B(4)+B(1)+

- B(0), 70),

- kDefPoly(B(70)+B(69)+B(68)+B(64), B(63)+B(62)+B(61)+B(60)+B(59)+B(57)+

- B(56)+B(55)+B(54)+B(53)+B(51)+B(50)+B(47)+B(44)+B(43)+B(41)+

- B(39)+B(37)+B(36)+B(33)+B(32)+B(26)+B(25)+B(24)+B(23)+B(21)+

- B(20)+B(19)+B(17)+B(12)+B(11)+B(10)+B(8)+B(6)+B(5)+B(4)+B(2)+

- B(0), 71),

- kDefPoly(B(71)+B(69)+B(68)+B(65)+B(64), B(62)+B(61)+B(59)+B(58)+B(55)+

- B(53)+B(51)+B(49)+B(48)+B(47)+B(43)+B(40)+B(38)+B(37)+B(36)+

- B(35)+B(33)+B(32)+B(31)+B(30)+B(29)+B(26)+B(24)+B(19)+B(18)+

- B(15)+B(13)+B(9)+B(7)+B(6)+B(3)+B(1)+B(0), 72),

- kDefPoly(B(71)+B(70)+B(69)+B(67)+B(65), B(63)+B(62)+B(61)+B(58)+B(57)+

- B(56)+B(55)+B(52)+B(51)+B(50)+B(49)+B(46)+B(45)+B(44)+B(43)+

- B(41)+B(37)+B(36)+B(34)+B(33)+B(27)+B(26)+B(25)+B(21)+B(19)+

- B(18)+B(16)+B(15)+B(14)+B(13)+B(9)+B(8)+B(6)+B(5)+B(2)+B(1)+

- B(0), 73),

- kDefPoly(B(73)+B(71)+B(70)+B(65)+B(64), B(62)+B(60)+B(55)+B(54)+B(52)+

- B(50)+B(48)+B(47)+B(46)+B(44)+B(41)+B(40)+B(31)+B(29)+B(28)+

- B(27)+B(26)+B(24)+B(23)+B(22)+B(20)+B(16)+B(12)+B(9)+B(6)+B(5)+

- B(4)+B(2)+B(0), 74),

- kDefPoly(B(74)+B(73)+B(72)+B(67)+B(64), B(63)+B(61)+B(60)+B(58)+B(57)+

- B(56)+B(54)+B(52)+B(51)+B(50)+B(44)+B(43)+B(42)+B(41)+B(40)+

- B(39)+B(38)+B(36)+B(35)+B(33)+B(32)+B(31)+B(29)+B(28)+B(26)+

- B(23)+B(21)+B(19)+B(18)+B(16)+B(15)+B(13)+B(12)+B(11)+B(7)+B(6)+

- B(5)+B(4)+B(3)+B(2)+B(0), 75),

- kDefPoly(B(75)+B(74)+B(71)+B(70)+B(66), B(63)+B(61)+B(59)+B(57)+B(53)+

- B(50)+B(49)+B(48)+B(44)+B(43)+B(42)+B(37)+B(33)+B(30)+B(27)+

- B(24)+B(23)+B(20)+B(18)+B(15)+B(12)+B(11)+B(9)+B(7)+B(6)+B(4)+

- B(3)+B(2)+B(0), 76),

- kDefPoly(B(73)+B(71)+B(70)+B(68)+B(67)+B(66)+B(65), B(63)+B(60)+B(59)+

- B(58)+B(57)+B(54)+B(49)+B(47)+B(46)+B(45)+B(43)+B(41)+B(38)+

- B(34)+B(33)+B(31)+B(30)+B(29)+B(27)+B(25)+B(24)+B(21)+B(20)+

- B(19)+B(16)+B(15)+B(14)+B(13)+B(10)+B(8)+B(6)+B(5)+B(4)+B(2)+

- B(0), 77),

- kDefPoly(B(77)+B(76)+B(75)+B(74)+B(70)+B(66)+B(65)+B(64), B(63)+B(62)+

- B(60)+B(58)+B(57)+B(55)+B(52)+B(51)+B(44)+B(41)+B(39)+B(38)+

- B(35)+B(31)+B(30)+B(29)+B(26)+B(22)+B(21)+B(20)+B(19)+B(15)+

- B(13)+B(11)+B(6)+B(4)+B(1)+B(0), 78),

- kDefPoly(B(78)+B(76)+B(75)+B(71)+B(68)+B(67)+B(65), B(63)+B(61)+B(60)+

- B(55)+B(54)+B(51)+B(50)+B(48)+B(44)+B(42)+B(41)+B(40)+B(38)+

- B(35)+B(34)+B(32)+B(28)+B(26)+B(23)+B(22)+B(19)+B(15)+B(13)+

- B(12)+B(8)+B(7)+B(5)+B(2)+B(0), 79),

- kDefPoly(B(77)+B(76)+B(75)+B(73)+B(70)+B(66), B(63)+B(61)+B(60)+B(59)+

- B(56)+B(54)+B(53)+B(52)+B(50)+B(44)+B(43)+B(40)+B(39)+B(38)+

- B(35)+B(34)+B(33)+B(29)+B(28)+B(27)+B(26)+B(25)+B(24)+B(23)+

- B(22)+B(21)+B(20)+B(18)+B(16)+B(13)+B(12)+B(11)+B(10)+B(8)+B(7)+

- B(6)+B(3)+B(2)+B(1)+B(0), 80),

- kDefPoly(B(78)+B(77)+B(76)+B(75)+B(73)+B(71)+B(67)+B(66)+B(65)+

- B(64), B(61)+B(54)+B(53)+B(52)+B(49)+B(47)+B(44)+B(41)+B(40)+

- B(35)+B(33)+B(31)+B(30)+B(28)+B(27)+B(26)+B(25)+B(22)+B(21)+

- B(20)+B(16)+B(15)+B(13)+B(12)+B(11)+B(0), 81),

- kDefPoly(B(81)+B(80)+B(79)+B(77)+B(76)+B(74)+B(73)+B(72)+B(68)+B(67)+

- B(66)+B(64), B(62)+B(51)+B(50)+B(49)+B(47)+B(46)+B(45)+B(43)+

- B(41)+B(38)+B(37)+B(34)+B(32)+B(30)+B(27)+B(26)+B(25)+B(24)+

- B(23)+B(22)+B(20)+B(19)+B(16)+B(15)+B(13)+B(12)+B(9)+B(7)+B(5)+

- B(4)+B(1)+B(0), 82),

- kDefPoly(B(82)+B(81)+B(79)+B(78)+B(77)+B(75)+B(72)+B(71)+B(69)+B(68)+

- B(67)+B(66)+B(65)+B(64), B(60)+B(58)+B(57)+B(56)+B(53)+B(52)+

- B(51)+B(49)+B(48)+B(45)+B(43)+B(41)+B(40)+B(39)+B(38)+B(37)+

- B(36)+B(35)+B(33)+B(26)+B(24)+B(21)+B(19)+B(16)+B(13)+B(12)+

- B(11)+B(9)+B(7)+B(5)+B(4)+B(3)+B(1)+B(0), 83),

- kDefPoly(B(79)+B(77)+B(73)+B(72)+B(71)+B(66)+B(64), B(62)+B(61)+B(59)+

- B(58)+B(57)+B(56)+B(53)+B(52)+B(51)+B(48)+B(47)+B(46)+B(45)+

- B(43)+B(42)+B(41)+B(38)+B(37)+B(35)+B(33)+B(32)+B(29)+B(24)+

- B(22)+B(17)+B(16)+B(15)+B(13)+B(11)+B(10)+B(9)+B(7)+B(6)+B(5)+

- B(0), 84),

- kDefPoly(B(83)+B(78)+B(76)+B(73)+B(70)+B(69)+B(68)+B(67)+B(66)+

- B(64), B(62)+B(61)+B(60)+B(59)+B(54)+B(51)+B(50)+B(48)+B(47)+

- B(42)+B(41)+B(40)+B(38)+B(37)+B(36)+B(34)+B(31)+B(30)+B(28)+

- B(27)+B(26)+B(24)+B(22)+B(21)+B(20)+B(19)+B(18)+B(16)+B(15)+

- B(14)+B(13)+B(12)+B(10)+B(6)+B(4)+B(0), 85),

- kDefPoly(B(84)+B(77)+B(76)+B(75)+B(71)+B(70)+B(69)+B(67)+B(65), B(63)+

- B(62)+B(59)+B(58)+B(57)+B(55)+B(53)+B(52)+B(51)+B(48)+B(47)+

- B(45)+B(43)+B(40)+B(38)+B(36)+B(34)+B(33)+B(31)+B(27)+B(25)+

- B(24)+B(23)+B(22)+B(19)+B(15)+B(13)+B(12)+B(11)+B(8)+B(6)+B(4)+

- B(0), 86),

- kDefPoly(B(85)+B(84)+B(83)+B(81)+B(80)+B(78)+B(73)+B(72)+B(70)+B(68)+

- B(67)+B(64), B(61)+B(60)+B(58)+B(57)+B(55)+B(52)+B(50)+B(49)+

- B(47)+B(44)+B(37)+B(36)+B(35)+B(34)+B(32)+B(31)+B(30)+B(25)+

- B(24)+B(23)+B(20)+B(13)+B(12)+B(11)+B(10)+B(9)+B(7)+B(6)+B(4)+

- B(3)+B(2)+B(0), 87),

- kDefPoly(B(86)+B(85)+B(84)+B(83)+B(82)+B(80)+B(77)+B(74)+B(70)+B(69)+

- B(65), B(63)+B(60)+B(59)+B(57)+B(56)+B(55)+B(53)+B(50)+B(49)+

- B(48)+B(45)+B(42)+B(41)+B(40)+B(39)+B(38)+B(37)+B(36)+B(25)+

- B(21)+B(19)+B(13)+B(11)+B(8)+B(5)+B(4)+B(2)+B(1)+B(0), 88),

- kDefPoly(B(86)+B(85)+B(83)+B(82)+B(81)+B(78)+B(77)+B(74)+B(73)+B(72)+

- B(70)+B(69)+B(68)+B(65)+B(64), B(59)+B(57)+B(55)+B(54)+B(51)+

- B(50)+B(46)+B(45)+B(44)+B(43)+B(42)+B(40)+B(38)+B(37)+B(33)+

- B(31)+B(30)+B(29)+B(28)+B(27)+B(23)+B(22)+B(21)+B(20)+B(18)+

- B(17)+B(16)+B(15)+B(10)+B(9)+B(3)+B(1)+B(0), 89),

- kDefPoly(B(86)+B(83)+B(82)+B(80)+B(79)+B(73)+B(70)+B(69)+B(67)+

- B(64), B(63)+B(62)+B(61)+B(57)+B(56)+B(54)+B(51)+B(49)+B(47)+

- B(46)+B(45)+B(40)+B(39)+B(37)+B(35)+B(33)+B(32)+B(29)+B(28)+

- B(27)+B(25)+B(24)+B(23)+B(22)+B(21)+B(20)+B(19)+B(18)+B(17)+

- B(15)+B(9)+B(8)+B(7)+B(3)+B(2)+B(0), 90),

- kDefPoly(B(90)+B(89)+B(84)+B(81)+B(80)+B(78)+B(74)+B(73)+B(71)+B(68)+

- B(64), B(60)+B(59)+B(58)+B(57)+B(55)+B(54)+B(52)+B(50)+B(49)+

- B(47)+B(45)+B(42)+B(41)+B(39)+B(38)+B(36)+B(32)+B(28)+B(25)+

- B(21)+B(20)+B(19)+B(15)+B(12)+B(11)+B(9)+B(8)+B(3)+

- B(0), 91),

- kDefPoly(B(91)+B(89)+B(88)+B(87)+B(86)+B(85)+B(84)+B(83)+B(80)+B(78)+

- B(76)+B(72)+B(70)+B(68), B(63)+B(62)+B(61)+B(59)+B(57)+B(56)+

- B(52)+B(51)+B(50)+B(49)+B(43)+B(40)+B(39)+B(37)+B(36)+B(35)+

- B(34)+B(33)+B(32)+B(26)+B(25)+B(24)+B(23)+B(22)+B(18)+B(15)+

- B(12)+B(11)+B(9)+B(7)+B(6)+B(3)+B(1)+B(0), 92),

- kDefPoly(B(86)+B(85)+B(83)+B(82)+B(79)+B(78)+B(77)+B(75)+B(74)+B(73)+

- B(66)+B(64), B(59)+B(57)+B(56)+B(55)+B(54)+B(52)+B(51)+B(40)+

- B(38)+B(36)+B(34)+B(33)+B(28)+B(27)+B(26)+B(25)+B(23)+B(22)+

- B(21)+B(20)+B(19)+B(18)+B(16)+B(15)+B(14)+B(13)+B(12)+B(11)+B(8)+

- B(7)+B(6)+B(5)+B(4)+B(0), 93),

- kDefPoly(B(93)+B(92)+B(91)+B(89)+B(88)+B(87)+B(86)+B(81)+B(80)+B(75)+

- B(66)+B(64), B(62)+B(61)+B(60)+B(59)+B(58)+B(57)+B(56)+B(54)+

- B(48)+B(47)+B(46)+B(45)+B(44)+B(42)+B(41)+B(38)+B(37)+B(36)+

- B(34)+B(33)+B(31)+B(30)+B(27)+B(26)+B(25)+B(22)+B(13)+B(12)+

- B(11)+B(10)+B(8)+B(7)+B(4)+B(0), 94),

- kDefPoly(B(94)+B(88)+B(87)+B(82)+B(79)+B(78)+B(76)+B(73)+B(65)+

- B(64), B(62)+B(61)+B(60)+B(59)+B(58)+B(57)+B(53)+B(51)+B(50)+

- B(49)+B(48)+B(47)+B(46)+B(44)+B(40)+B(36)+B(34)+B(33)+B(30)+

- B(28)+B(27)+B(25)+B(22)+B(19)+B(18)+B(17)+B(16)+B(14)+B(7)+B(5)+

- B(3)+B(2)+B(1)+B(0), 95),

- kDefPoly(B(92)+B(89)+B(88)+B(86)+B(83)+B(79)+B(78)+B(76)+B(75)+B(74)+

- B(72)+B(70)+B(67)+B(66), B(63)+B(60)+B(57)+B(55)+B(53)+B(51)+

- B(47)+B(46)+B(44)+B(43)+B(42)+B(39)+B(38)+B(36)+B(34)+B(32)+

- B(31)+B(30)+B(27)+B(26)+B(25)+B(22)+B(21)+B(19)+B(17)+B(13)+

- B(11)+B(10)+B(9)+B(8)+B(7)+B(4)+B(1)+B(0), 96),

- kDefPoly(B(96)+B(94)+B(93)+B(91)+B(89)+B(87)+B(85)+B(83)+B(81)+B(78)+

- B(76)+B(74)+B(73)+B(68)+B(67)+B(64), B(62)+B(61)+B(57)+B(55)+

- B(54)+B(53)+B(49)+B(47)+B(41)+B(38)+B(35)+B(33)+B(28)+B(27)+

- B(24)+B(23)+B(21)+B(19)+B(18)+B(17)+B(15)+B(13)+B(12)+B(11)+B(8)+

- B(6)+B(4)+B(3)+B(1)+B(0), 97),

- kDefPoly(B(97)+B(93)+B(92)+B(91)+B(90)+B(87)+B(83)+B(82)+B(80)+B(77)+

- B(76)+B(75)+B(74)+B(73)+B(72)+B(70)+B(69)+B(68)+B(66)+B(65)+

- B(64), B(63)+B(62)+B(61)+B(60)+B(59)+B(57)+B(55)+B(53)+B(50)+

- B(49)+B(48)+B(45)+B(44)+B(43)+B(42)+B(40)+B(38)+B(36)+B(35)+

- B(34)+B(28)+B(27)+B(24)+B(22)+B(21)+B(18)+B(17)+B(16)+B(15)+

- B(14)+B(12)+B(11)+B(9)+B(8)+B(2)+B(1)+B(0), 98),

- kDefPoly(B(96)+B(94)+B(92)+B(86)+B(85)+B(84)+B(78)+B(77)+B(76)+B(75)+

- B(73)+B(71)+B(69)+B(68)+B(65), B(61)+B(59)+B(57)+B(56)+B(54)+

- B(50)+B(47)+B(46)+B(44)+B(41)+B(38)+B(36)+B(35)+B(34)+B(33)+

- B(32)+B(29)+B(27)+B(26)+B(25)+B(23)+B(22)+B(21)+B(19)+B(17)+

- B(16)+B(11)+B(9)+B(7)+B(6)+B(3)+B(2)+B(0), 99),

- kDefPoly(B(99)+B(96)+B(95)+B(93)+B(92)+B(88)+B(87)+B(83)+B(78)+B(77)+

- B(76)+B(75)+B(74)+B(73)+B(70)+B(66)+B(64), B(63)+B(62)+B(60)+

- B(59)+B(57)+B(56)+B(53)+B(50)+B(47)+B(41)+B(39)+B(38)+B(37)+

- B(34)+B(25)+B(23)+B(21)+B(20)+B(19)+B(18)+B(17)+B(16)+B(13)+B(9)+

- B(8)+B(6)+B(5)+B(1)+B(0), 100),

- kDefPoly(B(100)+B(98)+B(97)+B(95)+B(93)+B(92)+B(91)+B(89)+B(87)+B(85)+

- B(84)+B(82)+B(81)+B(80)+B(79)+B(76)+B(68)+B(66)+B(65), B(63)+

- B(62)+B(59)+B(57)+B(52)+B(51)+B(50)+B(47)+B(46)+B(45)+B(42)+

- B(41)+B(40)+B(39)+B(38)+B(37)+B(36)+B(34)+B(32)+B(31)+B(30)+

- B(24)+B(22)+B(21)+B(20)+B(18)+B(17)+B(16)+B(14)+B(12)+B(11)+

- B(10)+B(8)+B(7)+B(5)+B(4)+B(2)+B(1)+B(0), 101),

- kDefPoly(B(101)+B(99)+B(97)+B(96)+B(92)+B(89)+B(88)+B(87)+B(86)+B(84)+

- B(82)+B(81)+B(80)+B(78)+B(77)+B(76)+B(75)+B(74)+B(73)+

- B(69), B(60)+B(59)+B(57)+B(56)+B(55)+B(54)+B(53)+B(51)+B(50)+

- B(49)+B(47)+B(45)+B(43)+B(41)+B(35)+B(34)+B(32)+B(31)+B(29)+

- B(27)+B(26)+B(25)+B(24)+B(21)+B(13)+B(12)+B(9)+B(8)+B(6)+B(5)+

- B(3)+B(0), 102),

- kDefPoly(B(101)+B(98)+B(97)+B(96)+B(94)+B(93)+B(92)+B(90)+B(89)+B(88)+

- B(87)+B(85)+B(83)+B(81)+B(80)+B(79)+B(76)+B(75)+B(71)+B(70)+

- B(69)+B(66), B(63)+B(62)+B(60)+B(59)+B(58)+B(56)+B(54)+B(53)+

- B(48)+B(45)+B(43)+B(42)+B(41)+B(37)+B(36)+B(32)+B(31)+B(30)+

- B(27)+B(25)+B(23)+B(22)+B(19)+B(16)+B(15)+B(11)+B(9)+B(5)+B(3)+

- B(0), 103),

- kDefPoly(B(98)+B(97)+B(95)+B(94)+B(91)+B(89)+B(88)+B(86)+B(85)+B(84)+

- B(81)+B(79)+B(78)+B(76)+B(74)+B(73)+B(70)+B(69)+B(68)+B(67)+

- B(66)+B(64), B(59)+B(53)+B(52)+B(51)+B(48)+B(46)+B(45)+B(43)+

- B(37)+B(34)+B(33)+B(31)+B(30)+B(28)+B(25)+B(22)+B(21)+B(20)+

- B(19)+B(14)+B(10)+B(8)+B(4)+B(2)+B(1)+B(0), 104),

- kDefPoly(B(103)+B(100)+B(99)+B(98)+B(94)+B(90)+B(89)+B(86)+B(84)+B(82)+

- B(79)+B(76)+B(74)+B(73)+B(72)+B(71)+B(70)+B(69)+B(67)+

- B(66), B(63)+B(62)+B(59)+B(58)+B(57)+B(55)+B(51)+B(49)+B(48)+

- B(47)+B(46)+B(43)+B(42)+B(38)+B(36)+B(34)+B(33)+B(31)+B(30)+

- B(29)+B(28)+B(27)+B(24)+B(21)+B(20)+B(18)+B(17)+B(16)+B(14)+

- B(13)+B(11)+B(9)+B(7)+B(6)+B(5)+B(0), 105),

- kDefPoly(B(105)+B(104)+B(103)+B(102)+B(100)+B(98)+B(94)+B(93)+B(92)+B(91)+

- B(90)+B(89)+B(87)+B(86)+B(85)+B(83)+B(82)+B(81)+B(79)+B(77)+

- B(69)+B(68)+B(67)+B(64), B(61)+B(60)+B(59)+B(58)+B(56)+B(55)+

- B(53)+B(50)+B(48)+B(44)+B(40)+B(38)+B(37)+B(36)+B(35)+B(34)+

- B(33)+B(30)+B(29)+B(26)+B(22)+B(20)+B(13)+B(10)+B(8)+B(7)+B(5)+

- B(0), 106),

- kDefPoly(B(105)+B(101)+B(100)+B(98)+B(97)+B(96)+B(93)+B(92)+B(91)+B(90)+

- B(87)+B(86)+B(81)+B(79)+B(77)+B(75)+B(74)+B(72)+B(68)+B(67)+

- B(64), B(63)+B(62)+B(61)+B(60)+B(59)+B(58)+B(54)+B(53)+B(52)+

- B(50)+B(48)+B(47)+B(45)+B(42)+B(41)+B(38)+B(32)+B(29)+B(27)+

- B(26)+B(24)+B(21)+B(19)+B(18)+B(16)+B(15)+B(14)+B(13)+B(12)+

- B(10)+B(7)+B(6)+B(4)+B(1)+B(0), 107),

- kDefPoly(B(106)+B(105)+B(102)+B(100)+B(97)+B(95)+B(90)+B(89)+B(88)+B(86)+

- B(83)+B(82)+B(81)+B(79)+B(78)+B(75)+B(72)+B(66)+B(64), B(63)+

- B(62)+B(59)+B(58)+B(56)+B(54)+B(52)+B(51)+B(50)+B(48)+B(46)+

- B(45)+B(44)+B(42)+B(40)+B(37)+B(36)+B(35)+B(33)+B(29)+B(27)+

- B(22)+B(19)+B(17)+B(14)+B(12)+B(11)+B(10)+B(9)+B(8)+B(7)+B(6)+

- B(5)+B(3)+B(0), 108),

- kDefPoly(B(108)+B(102)+B(101)+B(100)+B(99)+B(98)+B(96)+B(95)+B(94)+B(90)+

- B(89)+B(88)+B(87)+B(84)+B(83)+B(81)+B(80)+B(77)+B(76)+B(75)+

- B(71)+B(67)+B(65), B(63)+B(61)+B(60)+B(54)+B(50)+B(49)+B(48)+

- B(43)+B(40)+B(39)+B(38)+B(36)+B(34)+B(29)+B(28)+B(27)+B(22)+

- B(21)+B(19)+B(16)+B(14)+B(13)+B(12)+B(10)+B(9)+B(7)+B(6)+B(5)+

- B(3)+B(2)+B(0), 109),

- kDefPoly(B(109)+B(108)+B(107)+B(102)+B(101)+B(98)+B(97)+B(96)+B(94)+B(92)+

- B(91)+B(90)+B(88)+B(87)+B(85)+B(84)+B(83)+B(82)+B(81)+B(80)+

- B(79)+B(78)+B(74)+B(73)+B(71)+B(70)+B(69)+B(66)+B(64), B(61)+

- B(58)+B(57)+B(56)+B(50)+B(49)+B(46)+B(44)+B(43)+B(41)+B(36)+

- B(35)+B(34)+B(30)+B(29)+B(26)+B(25)+B(24)+B(22)+B(21)+B(17)+

- B(13)+B(11)+B(9)+B(4)+B(1)+B(0), 110),

- kDefPoly(B(110)+B(109)+B(105)+B(98)+B(97)+B(95)+B(94)+B(93)+B(92)+B(90)+

- B(88)+B(84)+B(83)+B(82)+B(80)+B(77)+B(75)+B(72)+B(71)+B(70)+

- B(69)+B(66), B(63)+B(61)+B(60)+B(59)+B(57)+B(56)+B(55)+B(52)+

- B(51)+B(50)+B(49)+B(47)+B(43)+B(40)+B(36)+B(35)+B(34)+B(33)+

- B(31)+B(27)+B(26)+B(21)+B(20)+B(19)+B(17)+B(16)+B(12)+B(8)+B(6)+

- B(4)+B(3)+B(2)+B(1)+B(0), 111),

- kDefPoly(B(109)+B(107)+B(106)+B(104)+B(100)+B(98)+B(96)+B(95)+B(94)+B(92)+

- B(91)+B(90)+B(89)+B(88)+B(86)+B(84)+B(81)+B(79)+B(78)+B(77)+

- B(75)+B(73)+B(71)+B(70)+B(69)+B(67)+B(64), B(63)+B(62)+B(61)+

- B(60)+B(58)+B(56)+B(54)+B(52)+B(51)+B(49)+B(48)+B(45)+B(44)+

- B(39)+B(38)+B(37)+B(36)+B(35)+B(34)+B(32)+B(30)+B(26)+B(25)+

- B(24)+B(23)+B(22)+B(21)+B(19)+B(16)+B(15)+B(11)+B(10)+B(9)+B(8)+

- B(3)+B(1)+B(0), 112),

- kDefPoly(B(111)+B(107)+B(102)+B(100)+B(99)+B(98)+B(97)+B(96)+B(95)+B(94)+

- B(93)+B(92)+B(87)+B(86)+B(82)+B(81)+B(80)+B(79)+B(77)+B(76)+

- B(75)+B(72)+B(69)+B(64), B(61)+B(58)+B(56)+B(54)+B(53)+B(52)+

- B(51)+B(49)+B(46)+B(43)+B(40)+B(39)+B(37)+B(36)+B(35)+B(34)+

- B(33)+B(31)+B(29)+B(24)+B(22)+B(21)+B(20)+B(15)+B(14)+B(12)+

- B(10)+B(6)+B(1)+B(0), 113),

- kDefPoly(B(112)+B(111)+B(110)+B(104)+B(102)+B(101)+B(100)+B(92)+B(89)+

- B(87)+B(83)+B(82)+B(80)+B(79)+B(75)+B(74)+B(73)+B(72)+B(71)+

- B(70)+B(68)+B(67)+B(65), B(60)+B(59)+B(57)+B(56)+B(55)+B(52)+

- B(50)+B(47)+B(44)+B(41)+B(36)+B(35)+B(30)+B(29)+B(26)+B(25)+

- B(24)+B(21)+B(18)+B(17)+B(16)+B(14)+B(12)+B(10)+B(7)+B(6)+

- B(0), 114),

- kDefPoly(B(114)+B(112)+B(111)+B(110)+B(108)+B(107)+B(103)+B(102)+B(98)+

- B(97)+B(96)+B(90)+B(88)+B(87)+B(86)+B(83)+B(82)+B(80)+B(79)+

- B(77)+B(75)+B(70)+B(66)+B(65)+B(64), B(61)+B(60)+B(59)+B(58)+

- B(57)+B(53)+B(52)+B(51)+B(50)+B(47)+B(45)+B(43)+B(39)+B(38)+

- B(33)+B(32)+B(31)+B(29)+B(27)+B(21)+B(17)+B(14)+B(12)+B(10)+B(7)+

- B(4)+B(2)+B(1)+B(0), 115),

- kDefPoly(B(113)+B(110)+B(108)+B(106)+B(105)+B(102)+B(101)+B(100)+B(98)+

- B(96)+B(92)+B(89)+B(87)+B(86)+B(84)+B(81)+B(79)+B(78)+B(76)+

- B(75)+B(73)+B(72)+B(71)+B(70)+B(67)+B(64), B(63)+B(62)+B(61)+

- B(52)+B(47)+B(45)+B(44)+B(42)+B(40)+B(39)+B(35)+B(34)+B(33)+

- B(31)+B(29)+B(25)+B(18)+B(15)+B(14)+B(10)+B(8)+B(6)+B(1)+

- B(0), 116),

- kDefPoly(B(113)+B(111)+B(110)+B(109)+B(107)+B(106)+B(103)+B(102)+B(100)+

- B(96)+B(95)+B(94)+B(91)+B(90)+B(89)+B(86)+B(82)+B(81)+B(78)+

- B(77)+B(76)+B(75)+B(74)+B(73)+B(70)+B(67)+B(66), B(63)+B(61)+

- B(59)+B(57)+B(56)+B(55)+B(53)+B(52)+B(51)+B(50)+B(47)+B(45)+

- B(42)+B(40)+B(37)+B(35)+B(32)+B(30)+B(29)+B(25)+B(22)+B(21)+

- B(20)+B(19)+B(16)+B(15)+B(14)+B(12)+B(8)+B(5)+B(0), 117),

- kDefPoly(B(117)+B(113)+B(110)+B(108)+B(105)+B(104)+B(103)+B(102)+B(99)+

- B(98)+B(97)+B(94)+B(93)+B(91)+B(90)+B(89)+B(85)+B(84)+B(82)+

- B(81)+B(79)+B(78)+B(77)+B(74)+B(73)+B(69)+B(67)+B(64), B(63)+

- B(62)+B(61)+B(57)+B(55)+B(51)+B(50)+B(46)+B(45)+B(43)+B(42)+

- B(41)+B(37)+B(33)+B(32)+B(30)+B(27)+B(26)+B(21)+B(19)+B(18)+

- B(17)+B(15)+B(14)+B(12)+B(10)+B(8)+B(7)+B(3)+B(2)+B(1)+

- B(0), 118),

- kDefPoly(B(118)+B(111)+B(109)+B(107)+B(106)+B(105)+B(104)+B(101)+B(99)+

- B(98)+B(97)+B(94)+B(92)+B(91)+B(89)+B(83)+B(82)+B(80)+B(79)+

- B(67)+B(66), B(62)+B(61)+B(60)+B(58)+B(57)+B(52)+B(48)+B(46)+

- B(44)+B(42)+B(40)+B(39)+B(38)+B(36)+B(34)+B(33)+B(32)+B(29)+

- B(23)+B(22)+B(20)+B(19)+B(18)+B(15)+B(13)+B(12)+B(11)+B(6)+B(5)+

- B(4)+B(3)+B(1)+B(0), 119),

- kDefPoly(B(116)+B(115)+B(113)+B(112)+B(110)+B(107)+B(106)+B(104)+B(103)+

- B(101)+B(100)+B(99)+B(98)+B(90)+B(89)+B(88)+B(87)+B(82)+B(80)+

- B(79)+B(77)+B(76)+B(75)+B(74)+B(73)+B(71)+B(70)+B(68)+B(65)+

- B(64), B(63)+B(62)+B(59)+B(55)+B(54)+B(48)+B(47)+B(45)+B(44)+

- B(40)+B(39)+B(38)+B(35)+B(33)+B(29)+B(27)+B(26)+B(25)+B(24)+

- B(23)+B(22)+B(21)+B(18)+B(17)+B(15)+B(13)+B(12)+B(10)+B(8)+B(3)+

- B(2)+B(0), 120),

- kDefPoly(B(118)+B(117)+B(114)+B(113)+B(112)+B(110)+B(109)+B(104)+B(103)+

- B(101)+B(99)+B(97)+B(96)+B(95)+B(93)+B(92)+B(91)+B(90)+B(89)+

- B(87)+B(85)+B(84)+B(82)+B(81)+B(79)+B(73)+B(72)+B(68)+B(67)+

- B(66)+B(64), B(60)+B(58)+B(57)+B(56)+B(54)+B(53)+B(52)+B(51)+

- B(49)+B(48)+B(47)+B(45)+B(44)+B(38)+B(37)+B(36)+B(35)+B(33)+

- B(32)+B(31)+B(30)+B(27)+B(26)+B(24)+B(23)+B(22)+B(20)+B(19)+

- B(18)+B(16)+B(15)+B(12)+B(6)+B(5)+B(4)+B(2)+B(0), 121),

- kDefPoly(B(121)+B(118)+B(114)+B(112)+B(109)+B(106)+B(103)+B(102)+B(101)+

- B(100)+B(97)+B(95)+B(90)+B(89)+B(87)+B(83)+B(81)+B(80)+B(79)+

- B(78)+B(77)+B(76)+B(75)+B(74)+B(72)+B(71)+B(70)+B(69)+B(68)+

- B(66)+B(64), B(61)+B(57)+B(51)+B(50)+B(47)+B(46)+B(43)+B(39)+

- B(38)+B(37)+B(36)+B(34)+B(33)+B(32)+B(30)+B(28)+B(27)+B(24)+

- B(22)+B(20)+B(18)+B(17)+B(14)+B(12)+B(11)+B(9)+B(7)+B(2)+

- B(0), 122),

- kDefPoly(B(122)+B(121)+B(120)+B(119)+B(118)+B(117)+B(116)+B(113)+B(112)+

- B(111)+B(109)+B(106)+B(105)+B(103)+B(100)+B(98)+B(97)+B(95)+

- B(93)+B(92)+B(90)+B(87)+B(86)+B(85)+B(83)+B(81)+B(78)+B(77)+

- B(75)+B(74)+B(73)+B(72)+B(71)+B(70)+B(69)+B(68)+B(67)+B(65)+

- B(64), B(63)+B(62)+B(60)+B(55)+B(52)+B(51)+B(49)+B(47)+B(45)+

- B(43)+B(42)+B(41)+B(37)+B(36)+B(35)+B(34)+B(32)+B(28)+B(27)+

- B(26)+B(24)+B(23)+B(21)+B(20)+B(16)+B(13)+B(10)+B(9)+B(8)+B(7)+

- B(5)+B(2)+B(0), 123),

- kDefPoly(B(123)+B(121)+B(120)+B(118)+B(117)+B(116)+B(115)+B(112)+B(111)+

- B(110)+B(109)+B(107)+B(104)+B(102)+B(101)+B(100)+B(99)+B(98)+

- B(97)+B(94)+B(90)+B(87)+B(86)+B(84)+B(83)+B(82)+B(79)+B(75)+

- B(72)+B(71)+B(70)+B(64), B(63)+B(56)+B(54)+B(51)+B(50)+B(47)+

- B(45)+B(44)+B(42)+B(39)+B(38)+B(36)+B(34)+B(33)+B(29)+B(26)+

- B(24)+B(20)+B(16)+B(14)+B(11)+B(10)+B(8)+B(7)+B(6)+B(4)+B(2)+

- B(0), 124),

- kDefPoly(B(124)+B(123)+B(121)+B(119)+B(118)+B(116)+B(115)+B(114)+B(107)+

- B(105)+B(104)+B(103)+B(102)+B(99)+B(98)+B(96)+B(94)+B(93)+B(89)+

- B(83)+B(82)+B(81)+B(80)+B(79)+B(78)+B(75)+B(74)+B(73)+B(72)+

- B(70)+B(69)+B(68)+B(64), B(63)+B(59)+B(56)+B(55)+B(52)+B(51)+

- B(50)+B(49)+B(48)+B(44)+B(42)+B(38)+B(37)+B(36)+B(33)+B(31)+

- B(29)+B(27)+B(26)+B(25)+B(23)+B(21)+B(19)+B(18)+B(16)+B(14)+

- B(11)+B(8)+B(7)+B(6)+B(4)+B(1)+B(0), 125),

- kDefPoly(B(124)+B(122)+B(121)+B(120)+B(119)+B(117)+B(113)+B(110)+B(108)+

- B(105)+B(103)+B(102)+B(101)+B(97)+B(93)+B(91)+B(90)+B(88)+B(86)+

- B(84)+B(82)+B(81)+B(79)+B(77)+B(76)+B(75)+B(73)+B(72)+B(71)+

- B(69)+B(67)+B(64), B(63)+B(62)+B(61)+B(60)+B(58)+B(56)+B(55)+

- B(52)+B(51)+B(48)+B(47)+B(45)+B(44)+B(42)+B(41)+B(40)+B(39)+

- B(37)+B(33)+B(32)+B(30)+B(29)+B(28)+B(27)+B(26)+B(25)+B(24)+

- B(23)+B(19)+B(18)+B(17)+B(16)+B(14)+B(13)+B(11)+B(9)+B(8)+B(7)+

- B(4)+B(2)+B(1)+B(0), 126),

- kDefPoly(B(125)+B(124)+B(121)+B(116)+B(115)+B(105)+B(103)+B(101)+B(94)+

- B(93)+B(91)+B(90)+B(88)+B(87)+B(86)+B(85)+B(77)+B(73)+B(72)+

- B(70)+B(68)+B(67), B(63)+B(62)+B(61)+B(59)+B(57)+B(53)+B(52)+

- B(51)+B(49)+B(48)+B(46)+B(44)+B(41)+B(39)+B(38)+B(36)+B(35)+

- B(30)+B(27)+B(25)+B(23)+B(20)+B(19)+B(13)+B(12)+B(11)+B(10)+B(8)+

- B(7)+B(5)+B(4)+B(3)+B(2)+B(0), 127),

- kDefPoly(B(127)+B(122)+B(121)+B(118)+B(117)+B(116)+B(109)+B(108)+B(107)+

- B(106)+B(104)+B(103)+B(102)+B(101)+B(96)+B(93)+B(92)+B(91)+B(89)+

- B(86)+B(85)+B(80)+B(78)+B(77)+B(76)+B(75)+B(74)+B(73)+B(72)+

- B(71)+B(66), B(60)+B(56)+B(53)+B(52)+B(50)+B(47)+B(45)+B(41)+

- B(39)+B(38)+B(37)+B(35)+B(34)+B(33)+B(30)+B(28)+B(25)+B(24)+

- B(23)+B(21)+B(20)+B(19)+B(14)+B(13)+B(10)+B(8)+B(5)+B(4)+B(2)+

- B(1)+B(0), 128),

-};

-// lint -restore

-// The number of polynomials in POLYS[].

-SELECTANY const int CRC::N_POLYS = sizeof (poly_list) / sizeof (poly_list[0]);

-// The externally visible name of poly_list.

-// This guarantees that the size of poly_list is opaque.

-SELECTANY const struct CRC::Poly *const CRC::POLYS = poly_list;

-// The "constructor" for a CRC with an default polynomial.

-CRC *CRC::Default(int degree, size_t roll_length) {

- ASSERT1(32 == degree);

- CRC *crc = CRCImpl::NewInternal(CRC::POLYS[degree].lo, CRC::POLYS[degree].hi,

- degree, roll_length); // Build the table

- return crc;

-// The "constructor" for a CRC with an arbitrary polynomial.

-CRC *CRC::New(uint64 lo, uint64 hi, int degree, size_t roll_length) {

- return CRCImpl::NewInternal(lo, hi, degree, roll_length);

-// Internal version of the "constructor".

-CRCImpl *CRCImpl::NewInternal(uint64 lo, uint64 hi,

- int degree, size_t roll_length) {

- ASSERT1(8 <= degree && degree <= 64); // precondition

- ASSERT1(lo != 0 || hi != 0); // precondition

- // Generate the tables for extending a CRC by 4 bytes at a time.

- // Why 4 and not 8? Because Pentium 4 has such small caches.

- struct CRC_pair t[4][256];

- for (int j = 0; j != 4; j++) { // for each byte of extension....

- t[j][0].lo = 0; // a zero has no effect

- t[j][0].hi = 0;

- for (int i = 128; i != 0; i >>= 1) { // fill in entries for powers of 2

- if (j == 0 && i == 128) {

- t[j][i].lo = lo; // top bit in first byte is easy---it's the polynomial

- t[j][i].hi = hi;

- } else {

- // each successive power of two is derive from the previous

- // one, either in this table, or the last table

- struct CRC_pair pred;

- if (i == 128) {

- pred = t[j-1][1];

- } else {

- pred = t[j][i << 1];

- }

- // Advance the CRC by one bit (multiply by X, and take remainder

- // through one step of polynomial long division)

- if (pred.lo & 1) {

- t[j][i].lo = (pred.lo >> 1) ^ (pred.hi << 63) ^ lo;

- t[j][i].hi = (pred.hi >> 1) ^ hi;

- } else {

- t[j][i].lo = (pred.lo >> 1) ^ (pred.hi << 63);

- t[j][i].hi = pred.hi >> 1;

- }

- // CRCs have the property that CRC(a xor b) == CRC(a) xor CRC(b)

- // so we can make all the tables for non-powers of two by

- // xoring previously created entries.

- for (int i = 2; i != 256; i <<= 1) {

- for (int k = i+1; k != (i << 1); k++) {

- t[j][k].lo = t[j][i].lo ^ t[j][k-i].lo;

- t[j][k].hi = t[j][i].hi ^ t[j][k-i].hi;

- }

- // Copy the newly built tables in t[] into an appropriate

- // CRC implenentation object.

- CRCImpl *result = 0;

- CRC32 *crc32 = 0;

- crc32 = new CRC32();

- for (int i = 0; i != 256; i++) {

- crc32->table0_[i] = static_cast<uint32>(t[0][i].lo);

- crc32->table1_[i] = static_cast<uint32>(t[1][i].lo);

- crc32->table2_[i] = static_cast<uint32>(t[2][i].lo);

- crc32->table3_[i] = static_cast<uint32>(t[3][i].lo);

- }

- result = crc32;

- // "result" is now a CRC object of the right type to handle

- // the polynomial of the right degree.

- result->roll_length_ = roll_length;

- result->degree_ = degree;

- result->poly_lo_ = lo;

- result->poly_hi_ = hi;

- // Build the table for extending by zeroes.

- // Entry i=a-1+3*b (a in {1, 2, 3}, b in {0, 1, 2, 3, ...}

- // contains a polynomial Pi such that multiplying

- // a CRC by Pi mod P, where P is the CRC polynomial, is equivalent to

- // appending a*2**(2*b+SMALL_BITS) zero bytes to the original string.

- // Entry is generated by calling ExtendByZeroes() twice using

- // half the length from the previous entry.

- int pos = 0;

- for (uint64 inc_len = (1 << SMALL_BITS); inc_len != 0; inc_len <<= 2) {

- result->Empty(&lo, &hi);

- for (int k = 0; k != 3; k++) {

- result->ExtendByZeroes(&lo, &hi, (size_t) (inc_len >> 1));

- crc32->zeroes_[pos] = static_cast<uint32>(lo);

- pos++;

- }

- // Calculate the entries in the roll table, used for rolling checksums

- // of a fixed length.

- // Extend the powers of two in the one-byte extension table by the roll

- // length.

- int bit = 256;

- do {

- bit >>= 1;

- result->ExtendByZeroes(&t[0][bit].lo, &t[0][bit].hi, roll_length);

- } while (bit != 0);

- // Calculate the non-powers of two using CRC(a xor b) == CRC(a) xor CRC(b)

- for (int i = 2; i != 256; i <<= 1) {

- for (int j = i+1; j != (i << 1); j++) {

- t[0][j].lo = t[0][i].lo ^ t[0][j-i].lo;

- t[0][j].hi = t[0][i].hi ^ t[0][j-i].hi;

- }

- // Now xor the CRC of (binary) 100000001 followed by

- // the roll length of zeroes. This will be xored into every

- // entry. This will simultaneously roll out the CRC

- // of the empty string that's been pushed one byte too far,

- // and roll in the CRC of the empty string in the correct place again.

- result->Empty(&lo, &hi);

- const uint8 x = 0x80;

- result->Extend(&lo, &hi, &x, 1);

- result->ExtendByZeroes(&lo, &hi, roll_length);

- for (int i = 0; i != 256; i++) {

- t[0][i].lo ^= lo;

- t[0][i].hi ^= hi;

- }

- // Put the roll table into the object.

- for (int i = 0; i != 256; i++) {

- crc32->roll_[i] = static_cast<uint32>(t[0][i].lo);

- }

- return result;

-// The CRC of the empty string is always the CRC polynomial itself.

-void CRCImpl::Empty(uint64 *lo, uint64 *hi) const {

- ASSERT1(hi);

- ASSERT1(lo);

- *lo = this->poly_lo_;

- *hi = this->poly_hi_;

-// The 32-bit implementation

-void CRC32::Extend(uint64 *lo, uint64 *hi, const void *bytes, size_t length)

- const {

- ASSERT1(hi);

- ASSERT1(lo);

- hi; // unreferenced formal parameter

- const uint8 *p = static_cast<const uint8 *>(bytes);

- const uint8 *e = p + length;

- uint32 l = static_cast<uint32>(*lo);

- // point x at MIN(first 4-byte aligned byte in string, end of string)

- const uint8 *x = p + ((zero_ptr - p) & 3);

- if (x > e) {

- x = e;

- }

- // Process bytes until finished or p is 4-byte aligned

- while (p != x) {

- int c = (l & 0xff) ^ *p++;

- l = this->table0_[c] ^ (l >> 8);

- }

- // point x at MIN(last 4-byte aligned byte in string, end of string)

- x = e - ((e - zero_ptr) & 3);

- // Process bytes 4 at a time

- while (p < x) {

- uint32 c = l ^ *reinterpret_cast<const uint32*>(p);

- p += 4;

- l = this->table3_[c & 0xff] ^

- this->table2_[(c >> 8) & 0xff] ^

- this->table1_[(c >> 16) & 0xff] ^

- this->table0_[c >> 24];

- }

- // Process the last few bytes

- while (p != e) {

- int c = (l & 0xff) ^ *p++;

- l = this->table0_[c] ^ (l >> 8);

- }

- *lo = l;

-void CRC32::ExtendByZeroes(uint64 *lo, uint64 *hi, size_t length) const {

- ASSERT1(hi);

- ASSERT1(lo);

- // Process the low order SMALL_BITS of the length by simply

- // using Extend() on an array of bytes that are zero.

- int small_part = (length & ((1 << SMALL_BITS)-1));

- if (small_part != 0) {

- this->Extend(lo, hi, zeroes, small_part);

- }

- length >>= SMALL_BITS;

- if (length != 0) { // if the length was at least 2**SMALL_BITS

- uint32 l = static_cast<uint32>(*lo);

- uint32 onebit = 1;

- onebit <<= this->degree_ - 1;

- // For each pair of bits in length

- // (after the low-oder bits have been removed)

- // we lookup the appropriate polynomial in the zeroes_ array

- // and do a polynomial long multiplication (mod the CRC polynomial)

- // to extend the CRC by the appropriate number of bits.

- for (int i = 0; length != 0; i += 3, length >>= 2) {

- int c = length & 3; // pick next two bits

- if (c != 0) { // if they are not zero,

- // multiply by entry in table

- uint32 m = this->zeroes_[c+i-1];

- uint32 result = 0;

- for (uint32 one = onebit; one != 0; one >>= 1) {

- if ((l & one) != 0) {

- result ^= m;

- }

- if (m & 1) {

- m = (m >> 1) ^ static_cast<uint32>(poly_lo_);

- } else {

- m = (m >> 1);

- }

- l = result;

- }

- *lo = l;

- }

-void CRC32::Roll(uint64 *lo, uint64 *hi, uint8 o_byte, uint8 i_byte) const {

- ASSERT1(hi);

- ASSERT1(lo);

- hi; // unreferenced formal parameter

- uint32 l = static_cast<uint32>(*lo);

- // Roll in i_byte and out o_byte

- *lo = this->table0_[(l & 0xff) ^ i_byte] ^ (l >> 8) ^ this->roll_[o_byte];

-} // namespace omaha

« no previous file with comments | « base/crc.h ('k') | base/debug.h » ('j') | no next file with comments »