| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2003-2009 Google Inc. | |
| 2 // | |
| 3 // Licensed under the Apache License, Version 2.0 (the "License"); | |
| 4 // you may not use this file except in compliance with the License. | |
| 5 // You may obtain a copy of the License at | |
| 6 // | |
| 7 // http://www.apache.org/licenses/LICENSE-2.0 | |
| 8 // | |
| 9 // Unless required by applicable law or agreed to in writing, software | |
| 10 // distributed under the License is distributed on an "AS IS" BASIS, | |
| 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| 12 // See the License for the specific language governing permissions and | |
| 13 // limitations under the License. | |
| 14 // ======================================================================== | |
| 15 // | |
| 16 // Implemetation of CRCs (aka Rabin Fingerprints). | |
| 17 // Treats the input as a polynomial with coefficients in Z(2), | |
| 18 // and finds the remainder when divided by an irreducible polynomial | |
| 19 // of the appropriate length. | |
| 20 // It handles all CRC sizes from 8 to 128 bits. | |
| 21 // It's somewhat complicated by having separate implementations optimized for | |
| 22 // CRC's <=32 bits, <= 64 bits, and <= 128 bits. | |
| 23 // The input string is prefixed with a "1" bit, and has "degree" "0" bits | |
| 24 // appended to it before the remainder is found. This ensures that | |
| 25 // short strings are scrambled somewhat and that strings consisting | |
| 26 // of all nulls have a non-zero CRC. | |
| 27 | |
| 28 #include <stddef.h> | |
| 29 #include "omaha/base/crc.h" | |
| 30 #include "omaha/base/debug.h" | |
| 31 #include "omaha/base/commontypes.h" | |
| 32 | |
| 33 namespace omaha { | |
| 34 | |
| 35 static const int SMALL_BITS = 8; | |
| 36 // When extending an input with a string of zeroes, | |
| 37 // if the number of zeroes is less than 2**SMALL_BITS, | |
| 38 // a normal Extend is done, rather than a polynomial | |
| 39 // multiplication. | |
| 40 static const char zeroes[1 << SMALL_BITS] = { 0 }; // an array of zeroes | |
| 41 | |
| 42 static const uint8 *zero_ptr = 0; // The 0 pointer---used for alignment | |
| 43 | |
| 44 // These are used to index a 2-entry array of words that together | |
| 45 // for a longer integer. LO indexes the low-order half. | |
| 46 #define LO 0 | |
| 47 #define HI (1-LO) | |
| 48 | |
| 49 // Constructor and destructor for baseclase CRC. | |
| 50 CRC::~CRC() {} | |
| 51 CRC::CRC() {} | |
| 52 | |
| 53 struct CRC_pair { // Used to represent a 128-bit value | |
| 54 uint64 lo; | |
| 55 uint64 hi; | |
| 56 }; | |
| 57 | |
| 58 class CRCImpl : public CRC { // Implemention of the abstract class CRC | |
| 59 public: | |
| 60 CRCImpl() {} | |
| 61 virtual ~CRCImpl() {} | |
| 62 | |
| 63 // The internal version of CRC::New(). | |
| 64 static CRCImpl *NewInternal(uint64 lo, uint64 hi, | |
| 65 int degree, size_t roll_length); | |
| 66 | |
| 67 virtual void Empty(uint64 *lo, uint64 *hi) const; | |
| 68 | |
| 69 size_t roll_length_; // length of window in rolling CRC | |
| 70 int degree_; // bits in the CRC | |
| 71 uint64 poly_lo_; // The CRC of the empty string, low part | |
| 72 uint64 poly_hi_; // The CRC of the empty string, high part | |
| 73 | |
| 74 private: | |
| 75 DISALLOW_EVIL_CONSTRUCTORS(CRCImpl); | |
| 76 }; | |
| 77 | |
| 78 // This is the 32-bit implementation. It handles all sizes from 8 to 32. | |
| 79 class CRC32 : public CRCImpl { | |
| 80 public: | |
| 81 CRC32() {} | |
| 82 virtual ~CRC32() {} | |
| 83 | |
| 84 virtual void Extend(uint64 *lo, uint64 *hi, | |
| 85 const void *bytes, size_t length) const; | |
| 86 virtual void ExtendByZeroes(uint64 *lo, uint64 *hi, size_t length) const; | |
| 87 virtual void Roll(uint64 *lo, uint64 *hi, uint8 o_byte, uint8 i_byte) const; | |
| 88 | |
| 89 uint32 table0_[256]; // table of byte extensions | |
| 90 uint32 table1_[256]; // table of byte extensions, shifted by 1 byte | |
| 91 uint32 table2_[256]; // table of byte extensions, shifted by 2 bytes | |
| 92 uint32 table3_[256]; // table of byte extensions, shifted by 3 bytes | |
| 93 uint32 roll_[256]; // table of byte roll values | |
| 94 uint32 zeroes_[256]; // table of zero extensions | |
| 95 | |
| 96 private: | |
| 97 DISALLOW_EVIL_CONSTRUCTORS(CRC32); | |
| 98 }; | |
| 99 | |
| 100 static const uint64 UINT64_ZERO = 0; // a 64-bit zero | |
| 101 static const uint64 UINT64_ONE = 1; // a 64-bit 1 | |
| 102 | |
| 103 // The B() macro sets the bit corresponding to X**(_x) in the polynomial | |
| 104 #define B(_x) (UINT64_ONE << ((_x) < 64?(63-(_x)):(127-(_x)))) | |
| 105 | |
| 106 // Used to initialize polynomials. | |
| 107 // The redundant tests on _len are to avoid warnings from the | |
| 108 // compiler about inappropriate shift lengths. These shifts | |
| 109 // occur on not-taken branch of the ?: in some cases. | |
| 110 #define kDefPoly(_h,_l,_len) \ | |
| 111 { ((_len) <= 64 ? (_l) >> ((_len) <= 64? 64 - (_len): 0) : \ | |
| 112 (_len) == 128 ? (_h) : \ | |
| 113 ((_h) >> ((_len) > 64? 128 - (_len): 0)) | \ | |
| 114 ((_l) << ((_len) > 64 && (_len) < 128? (_len)-64: 0))), \ | |
| 115 ((_len) <= 64 ? 0 : \ | |
| 116 (_len) == 128 ? (_l) : \ | |
| 117 (_l) >> ((_len) > 64? 128 - (_len): 0)), \ | |
| 118 (_len) } | |
| 119 | |
| 120 // A table of irreducible polynomials suitable for use with the implementation. | |
| 121 // Indexes 0...1 have degree 32 polynomials. | |
| 122 // Indexes 2...3 have degree 64 polynomials. | |
| 123 // Indexes 4...5 have degree 96 polynomials. | |
| 124 // Indexes 6...7 have degree 128 polynomials. | |
| 125 // Index i=8...128 has a degree i polynomial. | |
| 126 // All polynomials in the table are guaranteed distinct. | |
| 127 // lint -save -e572 -e648 -e778 Excessive shift value, expression evaluates to
0 | |
| 128 static const struct CRC::Poly poly_list[] = { | |
| 129 kDefPoly(UINT64_ZERO, B(30)+B(27)+B(26)+B(25)+B(23)+B(20)+B(17)+B(15)+B(14)+ | |
| 130 B(12)+B(6)+B(5)+B(2)+B(0), 32), | |
| 131 kDefPoly(UINT64_ZERO, B(31)+B(28)+B(27)+B(26)+B(24)+B(22)+B(19)+B(18)+B(16)+ | |
| 132 B(13)+B(11)+B(10)+B(9)+B(4)+B(2)+B(0), 32), | |
| 133 kDefPoly(UINT64_ZERO, B(60)+B(59)+B(58)+B(56)+B(55)+B(54)+B(51)+B(50)+B(49)+ | |
| 134 B(48)+B(47)+B(45)+B(44)+B(42)+B(40)+B(39)+B(38)+B(36)+B(34)+B(33)+ | |
| 135 B(32)+B(31)+B(30)+B(27)+B(25)+B(23)+B(22)+B(21)+B(20)+B(19)+ | |
| 136 B(17)+B(16)+B(15)+B(8)+B(7)+B(6)+B(5)+B(0), 64), | |
| 137 kDefPoly(UINT64_ZERO, B(63)+B(62)+B(60)+B(58)+B(57)+B(56)+B(54)+B(52)+B(46)+ | |
| 138 B(45)+B(43)+B(40)+B(37)+B(36)+B(34)+B(33)+B(32)+B(31)+B(30)+B(29)+ | |
| 139 B(28)+B(27)+B(26)+B(23)+B(19)+B(18)+B(15)+B(14)+B(13)+B(9)+B(8)+ | |
| 140 B(0), 64), | |
| 141 kDefPoly(B(95)+B(94)+B(91)+B(90)+B(89)+B(88)+B(87)+B(86)+B(79)+B(78)+ | |
| 142 B(77)+B(76)+B(75)+B(74)+B(73)+B(69)+B(68)+B(66), B(63)+B(61)+ | |
| 143 B(59)+B(57)+B(53)+B(51)+B(50)+B(47)+B(40)+B(39)+B(38)+B(36)+ | |
| 144 B(35)+B(33)+B(29)+B(28)+B(27)+B(25)+B(24)+B(23)+B(21)+B(19)+ | |
| 145 B(18)+B(17)+B(16)+B(13)+B(12)+B(10)+B(9)+B(7)+B(4)+B(2)+B(1)+ | |
| 146 B(0), 96), | |
| 147 kDefPoly(B(95)+B(92)+B(89)+B(88)+B(87)+B(85)+B(84)+B(82)+B(81)+B(80)+ | |
| 148 B(79)+B(78)+B(76)+B(75)+B(70)+B(69)+B(66)+B(65), B(60)+B(56)+ | |
| 149 B(55)+B(52)+B(51)+B(49)+B(48)+B(46)+B(44)+B(42)+B(41)+B(39)+ | |
| 150 B(38)+B(37)+B(35)+B(33)+B(32)+B(30)+B(28)+B(27)+B(25)+B(22)+ | |
| 151 B(19)+B(17)+B(14)+B(12)+B(10)+B(0), 96), | |
| 152 kDefPoly(B(122)+B(121)+B(120)+B(119)+B(117)+B(116)+B(114)+B(113)+B(112)+ | |
| 153 B(111)+B(109)+B(107)+B(104)+B(102)+B(100)+B(98)+B(96)+B(94)+ | |
| 154 B(93)+B(92)+B(91)+B(90)+B(88)+B(87)+B(86)+B(84)+B(82)+B(80)+ | |
| 155 B(75)+B(74)+B(73)+B(69), B(62)+B(61)+B(58)+B(52)+B(48)+B(47)+ | |
| 156 B(46)+B(45)+B(42)+B(41)+B(38)+B(37)+B(35)+B(33)+B(32)+B(31)+ | |
| 157 B(30)+B(28)+B(26)+B(24)+B(22)+B(21)+B(20)+B(19)+B(18)+B(17)+ | |
| 158 B(10)+B(9)+B(8)+B(7)+B(5)+B(2)+B(1)+B(0), 128), | |
| 159 kDefPoly(B(127)+B(126)+B(124)+B(121)+B(117)+B(116)+B(115)+B(113)+B(112)+ | |
| 160 B(111)+B(108)+B(105)+B(104)+B(103)+B(100)+B(98)+B(96)+B(93)+ | |
| 161 B(92)+B(90)+B(89)+B(88)+B(86)+B(85)+B(80)+B(77)+B(76)+B(72)+ | |
| 162 B(70)+B(69)+B(68)+B(65)+B(64), B(62)+B(61)+B(59)+B(58)+B(56)+ | |
| 163 B(53)+B(52)+B(51)+B(50)+B(48)+B(46)+B(39)+B(35)+B(34)+B(33)+ | |
| 164 B(32)+B(30)+B(29)+B(28)+B(22)+B(21)+B(19)+B(18)+B(17)+B(14)+ | |
| 165 B(10)+B(9)+B(7)+B(5)+B(4)+B(3)+B(2)+B(0), 128), | |
| 166 kDefPoly(UINT64_ZERO, B(7)+B(6)+B(5)+B(4)+B(2)+B(0), 8), | |
| 167 kDefPoly(UINT64_ZERO, B(8)+B(4)+B(3)+B(2)+B(1)+B(0), 9), | |
| 168 kDefPoly(UINT64_ZERO, B(8)+B(6)+B(5)+B(3)+B(1)+B(0), 10), | |
| 169 kDefPoly(UINT64_ZERO, B(10)+B(9)+B(7)+B(5)+B(1)+B(0), 11), | |
| 170 kDefPoly(UINT64_ZERO, B(11)+B(10)+B(5)+B(2)+B(1)+B(0), 12), | |
| 171 kDefPoly(UINT64_ZERO, B(12)+B(11)+B(10)+B(8)+B(5)+B(3)+B(2)+B(0), 13), | |
| 172 kDefPoly(UINT64_ZERO, B(11)+B(10)+B(9)+B(8)+B(7)+B(5)+B(4)+B(2)+B(1)+ | |
| 173 B(0), 14), | |
| 174 kDefPoly(UINT64_ZERO, B(14)+B(12)+B(11)+B(10)+B(9)+B(5)+B(3)+B(2)+B(1)+ | |
| 175 B(0), 15), | |
| 176 kDefPoly(UINT64_ZERO, B(12)+B(11)+B(7)+B(6)+B(5)+B(4)+B(3)+B(0), 16), | |
| 177 kDefPoly(UINT64_ZERO, B(16)+B(14)+B(11)+B(10)+B(8)+B(3)+B(1)+B(0), 17), | |
| 178 kDefPoly(UINT64_ZERO, B(12)+B(11)+B(9)+B(8)+B(7)+B(4)+B(3)+B(0), 18), | |
| 179 kDefPoly(UINT64_ZERO, B(12)+B(11)+B(8)+B(7)+B(6)+B(5)+B(2)+B(0), 19), | |
| 180 kDefPoly(UINT64_ZERO, B(18)+B(15)+B(14)+B(12)+B(9)+B(6)+B(3)+B(0), 20), | |
| 181 kDefPoly(UINT64_ZERO, B(20)+B(19)+B(14)+B(13)+B(12)+B(11)+B(8)+B(7)+B(6)+ | |
| 182 B(5)+B(2)+B(0), 21), | |
| 183 kDefPoly(UINT64_ZERO, B(21)+B(20)+B(18)+B(16)+B(15)+B(14)+B(12)+B(9)+B(7)+ | |
| 184 B(2)+B(1)+B(0), 22), | |
| 185 kDefPoly(UINT64_ZERO, B(22)+B(21)+B(17)+B(16)+B(15)+B(14)+B(12)+B(10)+B(7)+ | |
| 186 B(4)+B(1)+B(0), 23), | |
| 187 kDefPoly(UINT64_ZERO, B(23)+B(22)+B(21)+B(18)+B(17)+B(15)+B(14)+B(12)+B(4)+ | |
| 188 B(0), 24), | |
| 189 kDefPoly(UINT64_ZERO, B(24)+B(23)+B(22)+B(20)+B(18)+B(17)+B(14)+B(13)+B(9)+ | |
| 190 B(0), 25), | |
| 191 kDefPoly(UINT64_ZERO, B(25)+B(22)+B(21)+B(19)+B(17)+B(15)+B(14)+B(12)+B(11)+ | |
| 192 B(10)+B(6)+B(4)+B(3)+B(0), 26), | |
| 193 kDefPoly(UINT64_ZERO, B(26)+B(25)+B(19)+B(17)+B(16)+B(13)+B(5)+B(4)+B(1)+ | |
| 194 B(0), 27), | |
| 195 kDefPoly(UINT64_ZERO, B(23)+B(22)+B(21)+B(20)+B(19)+B(18)+B(13)+B(12)+B(10)+ | |
| 196 B(9)+B(8)+B(6)+B(5)+B(3)+B(1)+B(0), 28), | |
| 197 kDefPoly(UINT64_ZERO, B(27)+B(26)+B(25)+B(23)+B(22)+B(20)+B(19)+B(15)+B(14)+ | |
| 198 B(11)+B(10)+B(8)+B(7)+B(6)+B(4)+B(0), 29), | |
| 199 kDefPoly(UINT64_ZERO, B(29)+B(27)+B(25)+B(23)+B(20)+B(19)+B(18)+B(17)+B(16)+ | |
| 200 B(14)+B(11)+B(10)+B(9)+B(7)+B(6)+B(5)+B(4)+B(0), 30), | |
| 201 kDefPoly(UINT64_ZERO, B(30)+B(29)+B(28)+B(27)+B(25)+B(23)+B(22)+B(21)+B(20)+ | |
| 202 B(19)+B(18)+B(16)+B(15)+B(10)+B(9)+B(8)+B(4)+B(3)+B(1)+B(0), 31), | |
| 203 kDefPoly(UINT64_ZERO, B(31)+B(29)+B(28)+B(27)+B(21)+B(20)+B(15)+B(13)+B(10)+ | |
| 204 B(9)+B(8)+B(7)+B(4)+B(3)+B(2)+B(0), 32), | |
| 205 kDefPoly(UINT64_ZERO, B(32)+B(31)+B(30)+B(29)+B(27)+B(25)+B(24)+B(22)+B(21)+ | |
| 206 B(19)+B(15)+B(10)+B(4)+B(3)+B(2)+B(0), 33), | |
| 207 kDefPoly(UINT64_ZERO, B(30)+B(27)+B(26)+B(25)+B(24)+B(20)+B(19)+B(18)+B(16)+ | |
| 208 B(15)+B(14)+B(12)+B(9)+B(8)+B(7)+B(5)+B(1)+B(0), 34), | |
| 209 kDefPoly(UINT64_ZERO, B(34)+B(32)+B(28)+B(27)+B(26)+B(22)+B(21)+B(20)+B(19)+ | |
| 210 B(14)+B(13)+B(12)+B(10)+B(6)+B(5)+B(4)+B(3)+B(0), 35), | |
| 211 kDefPoly(UINT64_ZERO, B(35)+B(34)+B(33)+B(32)+B(31)+B(28)+B(26)+B(24)+B(22)+ | |
| 212 B(21)+B(20)+B(19)+B(18)+B(14)+B(13)+B(12)+B(10)+B(9)+B(8)+B(6)+B(5)+ | |
| 213 B(4)+B(3)+B(0), 36), | |
| 214 kDefPoly(UINT64_ZERO, B(36)+B(35)+B(31)+B(30)+B(28)+B(26)+B(25)+B(23)+B(22)+ | |
| 215 B(20)+B(19)+B(18)+B(16)+B(13)+B(12)+B(7)+B(6)+B(4)+B(3)+B(0), 37), | |
| 216 kDefPoly(UINT64_ZERO, B(37)+B(34)+B(33)+B(32)+B(31)+B(30)+B(29)+B(28)+B(27)+ | |
| 217 B(26)+B(25)+B(23)+B(18)+B(16)+B(15)+B(13)+B(12)+B(11)+B(10)+B(9)+ | |
| 218 B(8)+B(7)+B(6)+B(2)+B(1)+B(0), 38), | |
| 219 kDefPoly(UINT64_ZERO, B(38)+B(37)+B(33)+B(32)+B(31)+B(27)+B(25)+B(24)+B(21)+ | |
| 220 B(20)+B(19)+B(18)+B(17)+B(15)+B(14)+B(8)+B(7)+B(6)+B(3)+B(2)+B(1)+ | |
| 221 B(0), 39), | |
| 222 kDefPoly(UINT64_ZERO, B(38)+B(37)+B(35)+B(34)+B(32)+B(31)+B(30)+B(27)+B(24)+ | |
| 223 B(21)+B(20)+B(14)+B(13)+B(11)+B(8)+B(4)+B(2)+B(0), 40), | |
| 224 kDefPoly(UINT64_ZERO, B(38)+B(36)+B(35)+B(34)+B(33)+B(31)+B(30)+B(29)+B(28)+ | |
| 225 B(27)+B(23)+B(22)+B(20)+B(19)+B(18)+B(17)+B(15)+B(14)+B(11)+B(5)+ | |
| 226 B(4)+B(0), 41), | |
| 227 kDefPoly(UINT64_ZERO, B(41)+B(37)+B(36)+B(35)+B(32)+B(31)+B(30)+B(29)+B(28)+ | |
| 228 B(25)+B(19)+B(18)+B(14)+B(13)+B(12)+B(7)+B(6)+B(4)+B(2)+B(0), 42), | |
| 229 kDefPoly(UINT64_ZERO, B(42)+B(40)+B(38)+B(37)+B(36)+B(35)+B(34)+B(33)+B(31)+ | |
| 230 B(29)+B(27)+B(26)+B(25)+B(23)+B(21)+B(20)+B(19)+B(15)+B(11)+B(10)+ | |
| 231 B(9)+B(8)+B(6)+B(5)+B(3)+B(0), 43), | |
| 232 kDefPoly(UINT64_ZERO, B(43)+B(42)+B(40)+B(39)+B(37)+B(35)+B(32)+B(30)+B(26)+ | |
| 233 B(25)+B(24)+B(20)+B(16)+B(13)+B(12)+B(11)+B(8)+B(6)+B(5)+B(4)+B(1)+ | |
| 234 B(0), 44), | |
| 235 kDefPoly(UINT64_ZERO, B(43)+B(42)+B(41)+B(40)+B(39)+B(38)+B(33)+B(32)+B(27)+ | |
| 236 B(26)+B(25)+B(23)+B(20)+B(18)+B(17)+B(16)+B(14)+B(11)+B(10)+B(9)+ | |
| 237 B(6)+B(5)+B(1)+B(0), 45), | |
| 238 kDefPoly(UINT64_ZERO, B(45)+B(43)+B(42)+B(41)+B(40)+B(39)+B(32)+B(31)+B(30)+ | |
| 239 B(29)+B(27)+B(25)+B(23)+B(18)+B(17)+B(16)+B(10)+B(9)+B(7)+B(6)+B(4)+ | |
| 240 B(3)+B(2)+B(0), 46), | |
| 241 kDefPoly(UINT64_ZERO, B(45)+B(44)+B(43)+B(41)+B(40)+B(39)+B(38)+B(37)+B(32)+ | |
| 242 B(30)+B(23)+B(21)+B(20)+B(17)+B(15)+B(13)+B(11)+B(10)+B(7)+B(5)+ | |
| 243 B(3)+B(0), 47), | |
| 244 kDefPoly(UINT64_ZERO, B(46)+B(42)+B(41)+B(39)+B(37)+B(36)+B(35)+B(29)+B(28)+ | |
| 245 B(25)+B(24)+B(21)+B(20)+B(18)+B(17)+B(13)+B(12)+B(11)+B(10)+B(9)+ | |
| 246 B(8)+B(5)+B(1)+B(0), 48), | |
| 247 kDefPoly(UINT64_ZERO, B(48)+B(44)+B(41)+B(40)+B(39)+B(38)+B(37)+B(36)+B(35)+ | |
| 248 B(34)+B(30)+B(28)+B(27)+B(24)+B(21)+B(18)+B(17)+B(8)+B(3)+B(0), 49), | |
| 249 kDefPoly(UINT64_ZERO, B(48)+B(47)+B(46)+B(45)+B(44)+B(43)+B(42)+B(35)+B(33)+ | |
| 250 B(29)+B(26)+B(24)+B(23)+B(21)+B(18)+B(16)+B(14)+B(13)+B(12)+B(9)+ | |
| 251 B(7)+B(6)+B(5)+B(4)+B(3)+B(0), 50), | |
| 252 kDefPoly(UINT64_ZERO, B(47)+B(46)+B(45)+B(44)+B(43)+B(40)+B(39)+B(38)+B(36)+ | |
| 253 B(35)+B(30)+B(29)+B(28)+B(26)+B(25)+B(24)+B(23)+B(22)+B(20)+B(19)+ | |
| 254 B(18)+B(17)+B(15)+B(11)+B(7)+B(4)+B(3)+B(0), 51), | |
| 255 kDefPoly(UINT64_ZERO, B(51)+B(46)+B(43)+B(38)+B(37)+B(36)+B(34)+B(31)+B(27)+ | |
| 256 B(26)+B(20)+B(17)+B(16)+B(15)+B(13)+B(12)+B(11)+B(9)+B(7)+B(5)+B(1)+ | |
| 257 B(0), 52), | |
| 258 kDefPoly(UINT64_ZERO, B(50)+B(49)+B(47)+B(46)+B(44)+B(42)+B(41)+B(37)+B(36)+ | |
| 259 B(35)+B(33)+B(29)+B(28)+B(26)+B(24)+B(23)+B(21)+B(20)+B(14)+B(13)+ | |
| 260 B(12)+B(11)+B(10)+B(9)+B(8)+B(6)+B(3)+B(2)+B(1)+B(0), 53), | |
| 261 kDefPoly(UINT64_ZERO, B(52)+B(47)+B(46)+B(44)+B(43)+B(42)+B(40)+B(36)+B(32)+ | |
| 262 B(31)+B(30)+B(29)+B(28)+B(26)+B(25)+B(24)+B(23)+B(22)+B(20)+B(19)+ | |
| 263 B(17)+B(16)+B(15)+B(14)+B(13)+B(12)+B(11)+B(10)+B(7)+B(4)+B(2)+ | |
| 264 B(0), 54), | |
| 265 kDefPoly(UINT64_ZERO, B(53)+B(50)+B(48)+B(47)+B(37)+B(35)+B(31)+B(30)+B(25)+ | |
| 266 B(22)+B(21)+B(20)+B(19)+B(18)+B(15)+B(10)+B(8)+B(6)+B(3)+B(2)+B(1)+ | |
| 267 B(0), 55), | |
| 268 kDefPoly(UINT64_ZERO, B(54)+B(52)+B(51)+B(49)+B(48)+B(42)+B(38)+B(37)+B(31)+ | |
| 269 B(30)+B(27)+B(26)+B(24)+B(23)+B(22)+B(19)+B(16)+B(12)+B(11)+B(8)+ | |
| 270 B(6)+B(4)+B(3)+B(0), 56), | |
| 271 kDefPoly(UINT64_ZERO, B(55)+B(54)+B(51)+B(49)+B(48)+B(47)+B(46)+B(44)+B(43)+ | |
| 272 B(42)+B(41)+B(40)+B(39)+B(38)+B(32)+B(29)+B(27)+B(26)+B(23)+B(21)+ | |
| 273 B(20)+B(15)+B(12)+B(7)+B(6)+B(5)+B(3)+B(0), 57), | |
| 274 kDefPoly(UINT64_ZERO, B(57)+B(54)+B(52)+B(47)+B(45)+B(42)+B(41)+B(40)+B(39)+ | |
| 275 B(36)+B(34)+B(33)+B(31)+B(28)+B(26)+B(21)+B(20)+B(18)+B(17)+B(16)+ | |
| 276 B(13)+B(11)+B(8)+B(7)+B(4)+B(2)+B(1)+B(0), 58), | |
| 277 kDefPoly(UINT64_ZERO, B(58)+B(56)+B(54)+B(49)+B(47)+B(46)+B(43)+B(40)+B(38)+ | |
| 278 B(36)+B(35)+B(33)+B(32)+B(31)+B(30)+B(27)+B(24)+B(22)+B(21)+B(19)+ | |
| 279 B(17)+B(16)+B(11)+B(10)+B(9)+B(8)+B(7)+B(4)+B(3)+B(2)+B(1)+B(0), | |
| 280 59), | |
| 281 kDefPoly(UINT64_ZERO, B(56)+B(54)+B(51)+B(46)+B(43)+B(42)+B(40)+B(39)+B(37)+ | |
| 282 B(35)+B(34)+B(33)+B(32)+B(31)+B(30)+B(29)+B(27)+B(25)+B(22)+B(21)+ | |
| 283 B(20)+B(19)+B(17)+B(16)+B(15)+B(14)+B(13)+B(12)+B(9)+B(7)+B(4)+ | |
| 284 B(3)+B(1)+B(0), 60), | |
| 285 kDefPoly(UINT64_ZERO, B(59)+B(58)+B(57)+B(56)+B(54)+B(53)+B(50)+B(49)+B(47)+ | |
| 286 B(44)+B(42)+B(41)+B(40)+B(37)+B(35)+B(34)+B(32)+B(30)+B(29)+B(27)+ | |
| 287 B(26)+B(22)+B(21)+B(20)+B(17)+B(14)+B(13)+B(12)+B(8)+B(5)+B(4)+ | |
| 288 B(0), 61), | |
| 289 kDefPoly(UINT64_ZERO, B(61)+B(59)+B(57)+B(55)+B(54)+B(53)+B(52)+B(51)+B(50)+ | |
| 290 B(49)+B(48)+B(45)+B(44)+B(40)+B(37)+B(35)+B(32)+B(31)+B(29)+B(25)+ | |
| 291 B(24)+B(23)+B(20)+B(17)+B(16)+B(15)+B(13)+B(12)+B(11)+B(10)+B(6)+ | |
| 292 B(5)+B(2)+B(0), 62), | |
| 293 kDefPoly(UINT64_ZERO, B(62)+B(57)+B(56)+B(53)+B(52)+B(51)+B(50)+B(46)+B(41)+ | |
| 294 B(38)+B(35)+B(34)+B(33)+B(31)+B(27)+B(25)+B(23)+B(21)+B(19)+B(18)+ | |
| 295 B(17)+B(16)+B(13)+B(11)+B(7)+B(5)+B(1)+B(0), 63), | |
| 296 kDefPoly(UINT64_ZERO, B(62)+B(61)+B(60)+B(57)+B(55)+B(54)+B(53)+B(49)+B(48)+ | |
| 297 B(46)+B(44)+B(42)+B(40)+B(39)+B(37)+B(36)+B(28)+B(27)+B(25)+B(23)+ | |
| 298 B(22)+B(21)+B(17)+B(15)+B(13)+B(7)+B(6)+B(4)+B(2)+B(0), 64), | |
| 299 kDefPoly(UINT64_ZERO, B(63)+B(62)+B(59)+B(57)+B(54)+B(53)+B(51)+B(48)+ | |
| 300 B(47)+B(46)+B(45)+B(44)+B(41)+B(40)+B(38)+B(36)+B(35)+B(28)+ | |
| 301 B(25)+B(24)+B(21)+B(20)+B(18)+B(16)+B(15)+B(13)+B(11)+B(8)+B(7)+ | |
| 302 B(3)+B(1)+B(0), 65), | |
| 303 kDefPoly(UINT64_ZERO, B(63)+B(58)+B(57)+B(56)+B(52)+B(51)+B(50)+B(44)+ | |
| 304 B(41)+B(40)+B(36)+B(34)+B(32)+B(31)+B(27)+B(25)+B(23)+B(21)+ | |
| 305 B(20)+B(19)+B(18)+B(17)+B(15)+B(14)+B(12)+B(11)+B(10)+B(8)+B(5)+ | |
| 306 B(4)+B(3)+B(0), 66), | |
| 307 kDefPoly(B(66), B(62)+B(60)+B(59)+B(58)+B(57)+B(56)+B(55)+B(54)+B(52)+ | |
| 308 B(50)+B(47)+B(46)+B(45)+B(43)+B(42)+B(41)+B(38)+B(37)+B(36)+ | |
| 309 B(33)+B(32)+B(31)+B(30)+B(28)+B(27)+B(26)+B(24)+B(21)+B(18)+ | |
| 310 B(17)+B(14)+B(13)+B(12)+B(11)+B(10)+B(7)+B(4)+B(3)+B(0), 67), | |
| 311 kDefPoly(B(67)+B(66), B(63)+B(61)+B(57)+B(55)+B(51)+B(47)+B(45)+B(43)+ | |
| 312 B(42)+B(41)+B(40)+B(39)+B(32)+B(31)+B(30)+B(28)+B(27)+B(25)+ | |
| 313 B(19)+B(18)+B(17)+B(15)+B(11)+B(9)+B(8)+B(7)+B(6)+B(5)+B(4)+B(3)+ | |
| 314 B(1)+B(0), 68), | |
| 315 kDefPoly(B(68), B(60)+B(57)+B(55)+B(54)+B(52)+B(50)+B(49)+B(48)+B(44)+ | |
| 316 B(40)+B(38)+B(37)+B(33)+B(31)+B(28)+B(25)+B(22)+B(21)+B(20)+ | |
| 317 B(19)+B(18)+B(17)+B(13)+B(12)+B(9)+B(8)+B(6)+B(5)+B(4)+B(1)+ | |
| 318 B(0), 69), | |
| 319 kDefPoly(B(69)+B(68)+B(67)+B(66), B(63)+B(62)+B(61)+B(59)+B(51)+B(49)+ | |
| 320 B(48)+B(46)+B(45)+B(42)+B(40)+B(38)+B(36)+B(35)+B(33)+B(32)+ | |
| 321 B(30)+B(29)+B(27)+B(23)+B(22)+B(21)+B(16)+B(12)+B(5)+B(4)+B(1)+ | |
| 322 B(0), 70), | |
| 323 kDefPoly(B(70)+B(69)+B(68)+B(64), B(63)+B(62)+B(61)+B(60)+B(59)+B(57)+ | |
| 324 B(56)+B(55)+B(54)+B(53)+B(51)+B(50)+B(47)+B(44)+B(43)+B(41)+ | |
| 325 B(39)+B(37)+B(36)+B(33)+B(32)+B(26)+B(25)+B(24)+B(23)+B(21)+ | |
| 326 B(20)+B(19)+B(17)+B(12)+B(11)+B(10)+B(8)+B(6)+B(5)+B(4)+B(2)+ | |
| 327 B(0), 71), | |
| 328 kDefPoly(B(71)+B(69)+B(68)+B(65)+B(64), B(62)+B(61)+B(59)+B(58)+B(55)+ | |
| 329 B(53)+B(51)+B(49)+B(48)+B(47)+B(43)+B(40)+B(38)+B(37)+B(36)+ | |
| 330 B(35)+B(33)+B(32)+B(31)+B(30)+B(29)+B(26)+B(24)+B(19)+B(18)+ | |
| 331 B(15)+B(13)+B(9)+B(7)+B(6)+B(3)+B(1)+B(0), 72), | |
| 332 kDefPoly(B(71)+B(70)+B(69)+B(67)+B(65), B(63)+B(62)+B(61)+B(58)+B(57)+ | |
| 333 B(56)+B(55)+B(52)+B(51)+B(50)+B(49)+B(46)+B(45)+B(44)+B(43)+ | |
| 334 B(41)+B(37)+B(36)+B(34)+B(33)+B(27)+B(26)+B(25)+B(21)+B(19)+ | |
| 335 B(18)+B(16)+B(15)+B(14)+B(13)+B(9)+B(8)+B(6)+B(5)+B(2)+B(1)+ | |
| 336 B(0), 73), | |
| 337 kDefPoly(B(73)+B(71)+B(70)+B(65)+B(64), B(62)+B(60)+B(55)+B(54)+B(52)+ | |
| 338 B(50)+B(48)+B(47)+B(46)+B(44)+B(41)+B(40)+B(31)+B(29)+B(28)+ | |
| 339 B(27)+B(26)+B(24)+B(23)+B(22)+B(20)+B(16)+B(12)+B(9)+B(6)+B(5)+ | |
| 340 B(4)+B(2)+B(0), 74), | |
| 341 kDefPoly(B(74)+B(73)+B(72)+B(67)+B(64), B(63)+B(61)+B(60)+B(58)+B(57)+ | |
| 342 B(56)+B(54)+B(52)+B(51)+B(50)+B(44)+B(43)+B(42)+B(41)+B(40)+ | |
| 343 B(39)+B(38)+B(36)+B(35)+B(33)+B(32)+B(31)+B(29)+B(28)+B(26)+ | |
| 344 B(23)+B(21)+B(19)+B(18)+B(16)+B(15)+B(13)+B(12)+B(11)+B(7)+B(6)+ | |
| 345 B(5)+B(4)+B(3)+B(2)+B(0), 75), | |
| 346 kDefPoly(B(75)+B(74)+B(71)+B(70)+B(66), B(63)+B(61)+B(59)+B(57)+B(53)+ | |
| 347 B(50)+B(49)+B(48)+B(44)+B(43)+B(42)+B(37)+B(33)+B(30)+B(27)+ | |
| 348 B(24)+B(23)+B(20)+B(18)+B(15)+B(12)+B(11)+B(9)+B(7)+B(6)+B(4)+ | |
| 349 B(3)+B(2)+B(0), 76), | |
| 350 kDefPoly(B(73)+B(71)+B(70)+B(68)+B(67)+B(66)+B(65), B(63)+B(60)+B(59)+ | |
| 351 B(58)+B(57)+B(54)+B(49)+B(47)+B(46)+B(45)+B(43)+B(41)+B(38)+ | |
| 352 B(34)+B(33)+B(31)+B(30)+B(29)+B(27)+B(25)+B(24)+B(21)+B(20)+ | |
| 353 B(19)+B(16)+B(15)+B(14)+B(13)+B(10)+B(8)+B(6)+B(5)+B(4)+B(2)+ | |
| 354 B(0), 77), | |
| 355 kDefPoly(B(77)+B(76)+B(75)+B(74)+B(70)+B(66)+B(65)+B(64), B(63)+B(62)+ | |
| 356 B(60)+B(58)+B(57)+B(55)+B(52)+B(51)+B(44)+B(41)+B(39)+B(38)+ | |
| 357 B(35)+B(31)+B(30)+B(29)+B(26)+B(22)+B(21)+B(20)+B(19)+B(15)+ | |
| 358 B(13)+B(11)+B(6)+B(4)+B(1)+B(0), 78), | |
| 359 kDefPoly(B(78)+B(76)+B(75)+B(71)+B(68)+B(67)+B(65), B(63)+B(61)+B(60)+ | |
| 360 B(55)+B(54)+B(51)+B(50)+B(48)+B(44)+B(42)+B(41)+B(40)+B(38)+ | |
| 361 B(35)+B(34)+B(32)+B(28)+B(26)+B(23)+B(22)+B(19)+B(15)+B(13)+ | |
| 362 B(12)+B(8)+B(7)+B(5)+B(2)+B(0), 79), | |
| 363 kDefPoly(B(77)+B(76)+B(75)+B(73)+B(70)+B(66), B(63)+B(61)+B(60)+B(59)+ | |
| 364 B(56)+B(54)+B(53)+B(52)+B(50)+B(44)+B(43)+B(40)+B(39)+B(38)+ | |
| 365 B(35)+B(34)+B(33)+B(29)+B(28)+B(27)+B(26)+B(25)+B(24)+B(23)+ | |
| 366 B(22)+B(21)+B(20)+B(18)+B(16)+B(13)+B(12)+B(11)+B(10)+B(8)+B(7)+ | |
| 367 B(6)+B(3)+B(2)+B(1)+B(0), 80), | |
| 368 kDefPoly(B(78)+B(77)+B(76)+B(75)+B(73)+B(71)+B(67)+B(66)+B(65)+ | |
| 369 B(64), B(61)+B(54)+B(53)+B(52)+B(49)+B(47)+B(44)+B(41)+B(40)+ | |
| 370 B(35)+B(33)+B(31)+B(30)+B(28)+B(27)+B(26)+B(25)+B(22)+B(21)+ | |
| 371 B(20)+B(16)+B(15)+B(13)+B(12)+B(11)+B(0), 81), | |
| 372 kDefPoly(B(81)+B(80)+B(79)+B(77)+B(76)+B(74)+B(73)+B(72)+B(68)+B(67)+ | |
| 373 B(66)+B(64), B(62)+B(51)+B(50)+B(49)+B(47)+B(46)+B(45)+B(43)+ | |
| 374 B(41)+B(38)+B(37)+B(34)+B(32)+B(30)+B(27)+B(26)+B(25)+B(24)+ | |
| 375 B(23)+B(22)+B(20)+B(19)+B(16)+B(15)+B(13)+B(12)+B(9)+B(7)+B(5)+ | |
| 376 B(4)+B(1)+B(0), 82), | |
| 377 kDefPoly(B(82)+B(81)+B(79)+B(78)+B(77)+B(75)+B(72)+B(71)+B(69)+B(68)+ | |
| 378 B(67)+B(66)+B(65)+B(64), B(60)+B(58)+B(57)+B(56)+B(53)+B(52)+ | |
| 379 B(51)+B(49)+B(48)+B(45)+B(43)+B(41)+B(40)+B(39)+B(38)+B(37)+ | |
| 380 B(36)+B(35)+B(33)+B(26)+B(24)+B(21)+B(19)+B(16)+B(13)+B(12)+ | |
| 381 B(11)+B(9)+B(7)+B(5)+B(4)+B(3)+B(1)+B(0), 83), | |
| 382 kDefPoly(B(79)+B(77)+B(73)+B(72)+B(71)+B(66)+B(64), B(62)+B(61)+B(59)+ | |
| 383 B(58)+B(57)+B(56)+B(53)+B(52)+B(51)+B(48)+B(47)+B(46)+B(45)+ | |
| 384 B(43)+B(42)+B(41)+B(38)+B(37)+B(35)+B(33)+B(32)+B(29)+B(24)+ | |
| 385 B(22)+B(17)+B(16)+B(15)+B(13)+B(11)+B(10)+B(9)+B(7)+B(6)+B(5)+ | |
| 386 B(0), 84), | |
| 387 kDefPoly(B(83)+B(78)+B(76)+B(73)+B(70)+B(69)+B(68)+B(67)+B(66)+ | |
| 388 B(64), B(62)+B(61)+B(60)+B(59)+B(54)+B(51)+B(50)+B(48)+B(47)+ | |
| 389 B(42)+B(41)+B(40)+B(38)+B(37)+B(36)+B(34)+B(31)+B(30)+B(28)+ | |
| 390 B(27)+B(26)+B(24)+B(22)+B(21)+B(20)+B(19)+B(18)+B(16)+B(15)+ | |
| 391 B(14)+B(13)+B(12)+B(10)+B(6)+B(4)+B(0), 85), | |
| 392 kDefPoly(B(84)+B(77)+B(76)+B(75)+B(71)+B(70)+B(69)+B(67)+B(65), B(63)+ | |
| 393 B(62)+B(59)+B(58)+B(57)+B(55)+B(53)+B(52)+B(51)+B(48)+B(47)+ | |
| 394 B(45)+B(43)+B(40)+B(38)+B(36)+B(34)+B(33)+B(31)+B(27)+B(25)+ | |
| 395 B(24)+B(23)+B(22)+B(19)+B(15)+B(13)+B(12)+B(11)+B(8)+B(6)+B(4)+ | |
| 396 B(0), 86), | |
| 397 kDefPoly(B(85)+B(84)+B(83)+B(81)+B(80)+B(78)+B(73)+B(72)+B(70)+B(68)+ | |
| 398 B(67)+B(64), B(61)+B(60)+B(58)+B(57)+B(55)+B(52)+B(50)+B(49)+ | |
| 399 B(47)+B(44)+B(37)+B(36)+B(35)+B(34)+B(32)+B(31)+B(30)+B(25)+ | |
| 400 B(24)+B(23)+B(20)+B(13)+B(12)+B(11)+B(10)+B(9)+B(7)+B(6)+B(4)+ | |
| 401 B(3)+B(2)+B(0), 87), | |
| 402 kDefPoly(B(86)+B(85)+B(84)+B(83)+B(82)+B(80)+B(77)+B(74)+B(70)+B(69)+ | |
| 403 B(65), B(63)+B(60)+B(59)+B(57)+B(56)+B(55)+B(53)+B(50)+B(49)+ | |
| 404 B(48)+B(45)+B(42)+B(41)+B(40)+B(39)+B(38)+B(37)+B(36)+B(25)+ | |
| 405 B(21)+B(19)+B(13)+B(11)+B(8)+B(5)+B(4)+B(2)+B(1)+B(0), 88), | |
| 406 kDefPoly(B(86)+B(85)+B(83)+B(82)+B(81)+B(78)+B(77)+B(74)+B(73)+B(72)+ | |
| 407 B(70)+B(69)+B(68)+B(65)+B(64), B(59)+B(57)+B(55)+B(54)+B(51)+ | |
| 408 B(50)+B(46)+B(45)+B(44)+B(43)+B(42)+B(40)+B(38)+B(37)+B(33)+ | |
| 409 B(31)+B(30)+B(29)+B(28)+B(27)+B(23)+B(22)+B(21)+B(20)+B(18)+ | |
| 410 B(17)+B(16)+B(15)+B(10)+B(9)+B(3)+B(1)+B(0), 89), | |
| 411 kDefPoly(B(86)+B(83)+B(82)+B(80)+B(79)+B(73)+B(70)+B(69)+B(67)+ | |
| 412 B(64), B(63)+B(62)+B(61)+B(57)+B(56)+B(54)+B(51)+B(49)+B(47)+ | |
| 413 B(46)+B(45)+B(40)+B(39)+B(37)+B(35)+B(33)+B(32)+B(29)+B(28)+ | |
| 414 B(27)+B(25)+B(24)+B(23)+B(22)+B(21)+B(20)+B(19)+B(18)+B(17)+ | |
| 415 B(15)+B(9)+B(8)+B(7)+B(3)+B(2)+B(0), 90), | |
| 416 kDefPoly(B(90)+B(89)+B(84)+B(81)+B(80)+B(78)+B(74)+B(73)+B(71)+B(68)+ | |
| 417 B(64), B(60)+B(59)+B(58)+B(57)+B(55)+B(54)+B(52)+B(50)+B(49)+ | |
| 418 B(47)+B(45)+B(42)+B(41)+B(39)+B(38)+B(36)+B(32)+B(28)+B(25)+ | |
| 419 B(21)+B(20)+B(19)+B(15)+B(12)+B(11)+B(9)+B(8)+B(3)+ | |
| 420 B(0), 91), | |
| 421 kDefPoly(B(91)+B(89)+B(88)+B(87)+B(86)+B(85)+B(84)+B(83)+B(80)+B(78)+ | |
| 422 B(76)+B(72)+B(70)+B(68), B(63)+B(62)+B(61)+B(59)+B(57)+B(56)+ | |
| 423 B(52)+B(51)+B(50)+B(49)+B(43)+B(40)+B(39)+B(37)+B(36)+B(35)+ | |
| 424 B(34)+B(33)+B(32)+B(26)+B(25)+B(24)+B(23)+B(22)+B(18)+B(15)+ | |
| 425 B(12)+B(11)+B(9)+B(7)+B(6)+B(3)+B(1)+B(0), 92), | |
| 426 kDefPoly(B(86)+B(85)+B(83)+B(82)+B(79)+B(78)+B(77)+B(75)+B(74)+B(73)+ | |
| 427 B(66)+B(64), B(59)+B(57)+B(56)+B(55)+B(54)+B(52)+B(51)+B(40)+ | |
| 428 B(38)+B(36)+B(34)+B(33)+B(28)+B(27)+B(26)+B(25)+B(23)+B(22)+ | |
| 429 B(21)+B(20)+B(19)+B(18)+B(16)+B(15)+B(14)+B(13)+B(12)+B(11)+B(8)+ | |
| 430 B(7)+B(6)+B(5)+B(4)+B(0), 93), | |
| 431 kDefPoly(B(93)+B(92)+B(91)+B(89)+B(88)+B(87)+B(86)+B(81)+B(80)+B(75)+ | |
| 432 B(66)+B(64), B(62)+B(61)+B(60)+B(59)+B(58)+B(57)+B(56)+B(54)+ | |
| 433 B(48)+B(47)+B(46)+B(45)+B(44)+B(42)+B(41)+B(38)+B(37)+B(36)+ | |
| 434 B(34)+B(33)+B(31)+B(30)+B(27)+B(26)+B(25)+B(22)+B(13)+B(12)+ | |
| 435 B(11)+B(10)+B(8)+B(7)+B(4)+B(0), 94), | |
| 436 kDefPoly(B(94)+B(88)+B(87)+B(82)+B(79)+B(78)+B(76)+B(73)+B(65)+ | |
| 437 B(64), B(62)+B(61)+B(60)+B(59)+B(58)+B(57)+B(53)+B(51)+B(50)+ | |
| 438 B(49)+B(48)+B(47)+B(46)+B(44)+B(40)+B(36)+B(34)+B(33)+B(30)+ | |
| 439 B(28)+B(27)+B(25)+B(22)+B(19)+B(18)+B(17)+B(16)+B(14)+B(7)+B(5)+ | |
| 440 B(3)+B(2)+B(1)+B(0), 95), | |
| 441 kDefPoly(B(92)+B(89)+B(88)+B(86)+B(83)+B(79)+B(78)+B(76)+B(75)+B(74)+ | |
| 442 B(72)+B(70)+B(67)+B(66), B(63)+B(60)+B(57)+B(55)+B(53)+B(51)+ | |
| 443 B(47)+B(46)+B(44)+B(43)+B(42)+B(39)+B(38)+B(36)+B(34)+B(32)+ | |
| 444 B(31)+B(30)+B(27)+B(26)+B(25)+B(22)+B(21)+B(19)+B(17)+B(13)+ | |
| 445 B(11)+B(10)+B(9)+B(8)+B(7)+B(4)+B(1)+B(0), 96), | |
| 446 kDefPoly(B(96)+B(94)+B(93)+B(91)+B(89)+B(87)+B(85)+B(83)+B(81)+B(78)+ | |
| 447 B(76)+B(74)+B(73)+B(68)+B(67)+B(64), B(62)+B(61)+B(57)+B(55)+ | |
| 448 B(54)+B(53)+B(49)+B(47)+B(41)+B(38)+B(35)+B(33)+B(28)+B(27)+ | |
| 449 B(24)+B(23)+B(21)+B(19)+B(18)+B(17)+B(15)+B(13)+B(12)+B(11)+B(8)+ | |
| 450 B(6)+B(4)+B(3)+B(1)+B(0), 97), | |
| 451 kDefPoly(B(97)+B(93)+B(92)+B(91)+B(90)+B(87)+B(83)+B(82)+B(80)+B(77)+ | |
| 452 B(76)+B(75)+B(74)+B(73)+B(72)+B(70)+B(69)+B(68)+B(66)+B(65)+ | |
| 453 B(64), B(63)+B(62)+B(61)+B(60)+B(59)+B(57)+B(55)+B(53)+B(50)+ | |
| 454 B(49)+B(48)+B(45)+B(44)+B(43)+B(42)+B(40)+B(38)+B(36)+B(35)+ | |
| 455 B(34)+B(28)+B(27)+B(24)+B(22)+B(21)+B(18)+B(17)+B(16)+B(15)+ | |
| 456 B(14)+B(12)+B(11)+B(9)+B(8)+B(2)+B(1)+B(0), 98), | |
| 457 kDefPoly(B(96)+B(94)+B(92)+B(86)+B(85)+B(84)+B(78)+B(77)+B(76)+B(75)+ | |
| 458 B(73)+B(71)+B(69)+B(68)+B(65), B(61)+B(59)+B(57)+B(56)+B(54)+ | |
| 459 B(50)+B(47)+B(46)+B(44)+B(41)+B(38)+B(36)+B(35)+B(34)+B(33)+ | |
| 460 B(32)+B(29)+B(27)+B(26)+B(25)+B(23)+B(22)+B(21)+B(19)+B(17)+ | |
| 461 B(16)+B(11)+B(9)+B(7)+B(6)+B(3)+B(2)+B(0), 99), | |
| 462 kDefPoly(B(99)+B(96)+B(95)+B(93)+B(92)+B(88)+B(87)+B(83)+B(78)+B(77)+ | |
| 463 B(76)+B(75)+B(74)+B(73)+B(70)+B(66)+B(64), B(63)+B(62)+B(60)+ | |
| 464 B(59)+B(57)+B(56)+B(53)+B(50)+B(47)+B(41)+B(39)+B(38)+B(37)+ | |
| 465 B(34)+B(25)+B(23)+B(21)+B(20)+B(19)+B(18)+B(17)+B(16)+B(13)+B(9)+ | |
| 466 B(8)+B(6)+B(5)+B(1)+B(0), 100), | |
| 467 kDefPoly(B(100)+B(98)+B(97)+B(95)+B(93)+B(92)+B(91)+B(89)+B(87)+B(85)+ | |
| 468 B(84)+B(82)+B(81)+B(80)+B(79)+B(76)+B(68)+B(66)+B(65), B(63)+ | |
| 469 B(62)+B(59)+B(57)+B(52)+B(51)+B(50)+B(47)+B(46)+B(45)+B(42)+ | |
| 470 B(41)+B(40)+B(39)+B(38)+B(37)+B(36)+B(34)+B(32)+B(31)+B(30)+ | |
| 471 B(24)+B(22)+B(21)+B(20)+B(18)+B(17)+B(16)+B(14)+B(12)+B(11)+ | |
| 472 B(10)+B(8)+B(7)+B(5)+B(4)+B(2)+B(1)+B(0), 101), | |
| 473 kDefPoly(B(101)+B(99)+B(97)+B(96)+B(92)+B(89)+B(88)+B(87)+B(86)+B(84)+ | |
| 474 B(82)+B(81)+B(80)+B(78)+B(77)+B(76)+B(75)+B(74)+B(73)+ | |
| 475 B(69), B(60)+B(59)+B(57)+B(56)+B(55)+B(54)+B(53)+B(51)+B(50)+ | |
| 476 B(49)+B(47)+B(45)+B(43)+B(41)+B(35)+B(34)+B(32)+B(31)+B(29)+ | |
| 477 B(27)+B(26)+B(25)+B(24)+B(21)+B(13)+B(12)+B(9)+B(8)+B(6)+B(5)+ | |
| 478 B(3)+B(0), 102), | |
| 479 kDefPoly(B(101)+B(98)+B(97)+B(96)+B(94)+B(93)+B(92)+B(90)+B(89)+B(88)+ | |
| 480 B(87)+B(85)+B(83)+B(81)+B(80)+B(79)+B(76)+B(75)+B(71)+B(70)+ | |
| 481 B(69)+B(66), B(63)+B(62)+B(60)+B(59)+B(58)+B(56)+B(54)+B(53)+ | |
| 482 B(48)+B(45)+B(43)+B(42)+B(41)+B(37)+B(36)+B(32)+B(31)+B(30)+ | |
| 483 B(27)+B(25)+B(23)+B(22)+B(19)+B(16)+B(15)+B(11)+B(9)+B(5)+B(3)+ | |
| 484 B(0), 103), | |
| 485 kDefPoly(B(98)+B(97)+B(95)+B(94)+B(91)+B(89)+B(88)+B(86)+B(85)+B(84)+ | |
| 486 B(81)+B(79)+B(78)+B(76)+B(74)+B(73)+B(70)+B(69)+B(68)+B(67)+ | |
| 487 B(66)+B(64), B(59)+B(53)+B(52)+B(51)+B(48)+B(46)+B(45)+B(43)+ | |
| 488 B(37)+B(34)+B(33)+B(31)+B(30)+B(28)+B(25)+B(22)+B(21)+B(20)+ | |
| 489 B(19)+B(14)+B(10)+B(8)+B(4)+B(2)+B(1)+B(0), 104), | |
| 490 kDefPoly(B(103)+B(100)+B(99)+B(98)+B(94)+B(90)+B(89)+B(86)+B(84)+B(82)+ | |
| 491 B(79)+B(76)+B(74)+B(73)+B(72)+B(71)+B(70)+B(69)+B(67)+ | |
| 492 B(66), B(63)+B(62)+B(59)+B(58)+B(57)+B(55)+B(51)+B(49)+B(48)+ | |
| 493 B(47)+B(46)+B(43)+B(42)+B(38)+B(36)+B(34)+B(33)+B(31)+B(30)+ | |
| 494 B(29)+B(28)+B(27)+B(24)+B(21)+B(20)+B(18)+B(17)+B(16)+B(14)+ | |
| 495 B(13)+B(11)+B(9)+B(7)+B(6)+B(5)+B(0), 105), | |
| 496 kDefPoly(B(105)+B(104)+B(103)+B(102)+B(100)+B(98)+B(94)+B(93)+B(92)+B(91)+ | |
| 497 B(90)+B(89)+B(87)+B(86)+B(85)+B(83)+B(82)+B(81)+B(79)+B(77)+ | |
| 498 B(69)+B(68)+B(67)+B(64), B(61)+B(60)+B(59)+B(58)+B(56)+B(55)+ | |
| 499 B(53)+B(50)+B(48)+B(44)+B(40)+B(38)+B(37)+B(36)+B(35)+B(34)+ | |
| 500 B(33)+B(30)+B(29)+B(26)+B(22)+B(20)+B(13)+B(10)+B(8)+B(7)+B(5)+ | |
| 501 B(0), 106), | |
| 502 kDefPoly(B(105)+B(101)+B(100)+B(98)+B(97)+B(96)+B(93)+B(92)+B(91)+B(90)+ | |
| 503 B(87)+B(86)+B(81)+B(79)+B(77)+B(75)+B(74)+B(72)+B(68)+B(67)+ | |
| 504 B(64), B(63)+B(62)+B(61)+B(60)+B(59)+B(58)+B(54)+B(53)+B(52)+ | |
| 505 B(50)+B(48)+B(47)+B(45)+B(42)+B(41)+B(38)+B(32)+B(29)+B(27)+ | |
| 506 B(26)+B(24)+B(21)+B(19)+B(18)+B(16)+B(15)+B(14)+B(13)+B(12)+ | |
| 507 B(10)+B(7)+B(6)+B(4)+B(1)+B(0), 107), | |
| 508 kDefPoly(B(106)+B(105)+B(102)+B(100)+B(97)+B(95)+B(90)+B(89)+B(88)+B(86)+ | |
| 509 B(83)+B(82)+B(81)+B(79)+B(78)+B(75)+B(72)+B(66)+B(64), B(63)+ | |
| 510 B(62)+B(59)+B(58)+B(56)+B(54)+B(52)+B(51)+B(50)+B(48)+B(46)+ | |
| 511 B(45)+B(44)+B(42)+B(40)+B(37)+B(36)+B(35)+B(33)+B(29)+B(27)+ | |
| 512 B(22)+B(19)+B(17)+B(14)+B(12)+B(11)+B(10)+B(9)+B(8)+B(7)+B(6)+ | |
| 513 B(5)+B(3)+B(0), 108), | |
| 514 kDefPoly(B(108)+B(102)+B(101)+B(100)+B(99)+B(98)+B(96)+B(95)+B(94)+B(90)+ | |
| 515 B(89)+B(88)+B(87)+B(84)+B(83)+B(81)+B(80)+B(77)+B(76)+B(75)+ | |
| 516 B(71)+B(67)+B(65), B(63)+B(61)+B(60)+B(54)+B(50)+B(49)+B(48)+ | |
| 517 B(43)+B(40)+B(39)+B(38)+B(36)+B(34)+B(29)+B(28)+B(27)+B(22)+ | |
| 518 B(21)+B(19)+B(16)+B(14)+B(13)+B(12)+B(10)+B(9)+B(7)+B(6)+B(5)+ | |
| 519 B(3)+B(2)+B(0), 109), | |
| 520 kDefPoly(B(109)+B(108)+B(107)+B(102)+B(101)+B(98)+B(97)+B(96)+B(94)+B(92)+ | |
| 521 B(91)+B(90)+B(88)+B(87)+B(85)+B(84)+B(83)+B(82)+B(81)+B(80)+ | |
| 522 B(79)+B(78)+B(74)+B(73)+B(71)+B(70)+B(69)+B(66)+B(64), B(61)+ | |
| 523 B(58)+B(57)+B(56)+B(50)+B(49)+B(46)+B(44)+B(43)+B(41)+B(36)+ | |
| 524 B(35)+B(34)+B(30)+B(29)+B(26)+B(25)+B(24)+B(22)+B(21)+B(17)+ | |
| 525 B(13)+B(11)+B(9)+B(4)+B(1)+B(0), 110), | |
| 526 kDefPoly(B(110)+B(109)+B(105)+B(98)+B(97)+B(95)+B(94)+B(93)+B(92)+B(90)+ | |
| 527 B(88)+B(84)+B(83)+B(82)+B(80)+B(77)+B(75)+B(72)+B(71)+B(70)+ | |
| 528 B(69)+B(66), B(63)+B(61)+B(60)+B(59)+B(57)+B(56)+B(55)+B(52)+ | |
| 529 B(51)+B(50)+B(49)+B(47)+B(43)+B(40)+B(36)+B(35)+B(34)+B(33)+ | |
| 530 B(31)+B(27)+B(26)+B(21)+B(20)+B(19)+B(17)+B(16)+B(12)+B(8)+B(6)+ | |
| 531 B(4)+B(3)+B(2)+B(1)+B(0), 111), | |
| 532 kDefPoly(B(109)+B(107)+B(106)+B(104)+B(100)+B(98)+B(96)+B(95)+B(94)+B(92)+ | |
| 533 B(91)+B(90)+B(89)+B(88)+B(86)+B(84)+B(81)+B(79)+B(78)+B(77)+ | |
| 534 B(75)+B(73)+B(71)+B(70)+B(69)+B(67)+B(64), B(63)+B(62)+B(61)+ | |
| 535 B(60)+B(58)+B(56)+B(54)+B(52)+B(51)+B(49)+B(48)+B(45)+B(44)+ | |
| 536 B(39)+B(38)+B(37)+B(36)+B(35)+B(34)+B(32)+B(30)+B(26)+B(25)+ | |
| 537 B(24)+B(23)+B(22)+B(21)+B(19)+B(16)+B(15)+B(11)+B(10)+B(9)+B(8)+ | |
| 538 B(3)+B(1)+B(0), 112), | |
| 539 kDefPoly(B(111)+B(107)+B(102)+B(100)+B(99)+B(98)+B(97)+B(96)+B(95)+B(94)+ | |
| 540 B(93)+B(92)+B(87)+B(86)+B(82)+B(81)+B(80)+B(79)+B(77)+B(76)+ | |
| 541 B(75)+B(72)+B(69)+B(64), B(61)+B(58)+B(56)+B(54)+B(53)+B(52)+ | |
| 542 B(51)+B(49)+B(46)+B(43)+B(40)+B(39)+B(37)+B(36)+B(35)+B(34)+ | |
| 543 B(33)+B(31)+B(29)+B(24)+B(22)+B(21)+B(20)+B(15)+B(14)+B(12)+ | |
| 544 B(10)+B(6)+B(1)+B(0), 113), | |
| 545 kDefPoly(B(112)+B(111)+B(110)+B(104)+B(102)+B(101)+B(100)+B(92)+B(89)+ | |
| 546 B(87)+B(83)+B(82)+B(80)+B(79)+B(75)+B(74)+B(73)+B(72)+B(71)+ | |
| 547 B(70)+B(68)+B(67)+B(65), B(60)+B(59)+B(57)+B(56)+B(55)+B(52)+ | |
| 548 B(50)+B(47)+B(44)+B(41)+B(36)+B(35)+B(30)+B(29)+B(26)+B(25)+ | |
| 549 B(24)+B(21)+B(18)+B(17)+B(16)+B(14)+B(12)+B(10)+B(7)+B(6)+ | |
| 550 B(0), 114), | |
| 551 kDefPoly(B(114)+B(112)+B(111)+B(110)+B(108)+B(107)+B(103)+B(102)+B(98)+ | |
| 552 B(97)+B(96)+B(90)+B(88)+B(87)+B(86)+B(83)+B(82)+B(80)+B(79)+ | |
| 553 B(77)+B(75)+B(70)+B(66)+B(65)+B(64), B(61)+B(60)+B(59)+B(58)+ | |
| 554 B(57)+B(53)+B(52)+B(51)+B(50)+B(47)+B(45)+B(43)+B(39)+B(38)+ | |
| 555 B(33)+B(32)+B(31)+B(29)+B(27)+B(21)+B(17)+B(14)+B(12)+B(10)+B(7)+ | |
| 556 B(4)+B(2)+B(1)+B(0), 115), | |
| 557 kDefPoly(B(113)+B(110)+B(108)+B(106)+B(105)+B(102)+B(101)+B(100)+B(98)+ | |
| 558 B(96)+B(92)+B(89)+B(87)+B(86)+B(84)+B(81)+B(79)+B(78)+B(76)+ | |
| 559 B(75)+B(73)+B(72)+B(71)+B(70)+B(67)+B(64), B(63)+B(62)+B(61)+ | |
| 560 B(52)+B(47)+B(45)+B(44)+B(42)+B(40)+B(39)+B(35)+B(34)+B(33)+ | |
| 561 B(31)+B(29)+B(25)+B(18)+B(15)+B(14)+B(10)+B(8)+B(6)+B(1)+ | |
| 562 B(0), 116), | |
| 563 kDefPoly(B(113)+B(111)+B(110)+B(109)+B(107)+B(106)+B(103)+B(102)+B(100)+ | |
| 564 B(96)+B(95)+B(94)+B(91)+B(90)+B(89)+B(86)+B(82)+B(81)+B(78)+ | |
| 565 B(77)+B(76)+B(75)+B(74)+B(73)+B(70)+B(67)+B(66), B(63)+B(61)+ | |
| 566 B(59)+B(57)+B(56)+B(55)+B(53)+B(52)+B(51)+B(50)+B(47)+B(45)+ | |
| 567 B(42)+B(40)+B(37)+B(35)+B(32)+B(30)+B(29)+B(25)+B(22)+B(21)+ | |
| 568 B(20)+B(19)+B(16)+B(15)+B(14)+B(12)+B(8)+B(5)+B(0), 117), | |
| 569 kDefPoly(B(117)+B(113)+B(110)+B(108)+B(105)+B(104)+B(103)+B(102)+B(99)+ | |
| 570 B(98)+B(97)+B(94)+B(93)+B(91)+B(90)+B(89)+B(85)+B(84)+B(82)+ | |
| 571 B(81)+B(79)+B(78)+B(77)+B(74)+B(73)+B(69)+B(67)+B(64), B(63)+ | |
| 572 B(62)+B(61)+B(57)+B(55)+B(51)+B(50)+B(46)+B(45)+B(43)+B(42)+ | |
| 573 B(41)+B(37)+B(33)+B(32)+B(30)+B(27)+B(26)+B(21)+B(19)+B(18)+ | |
| 574 B(17)+B(15)+B(14)+B(12)+B(10)+B(8)+B(7)+B(3)+B(2)+B(1)+ | |
| 575 B(0), 118), | |
| 576 kDefPoly(B(118)+B(111)+B(109)+B(107)+B(106)+B(105)+B(104)+B(101)+B(99)+ | |
| 577 B(98)+B(97)+B(94)+B(92)+B(91)+B(89)+B(83)+B(82)+B(80)+B(79)+ | |
| 578 B(67)+B(66), B(62)+B(61)+B(60)+B(58)+B(57)+B(52)+B(48)+B(46)+ | |
| 579 B(44)+B(42)+B(40)+B(39)+B(38)+B(36)+B(34)+B(33)+B(32)+B(29)+ | |
| 580 B(23)+B(22)+B(20)+B(19)+B(18)+B(15)+B(13)+B(12)+B(11)+B(6)+B(5)+ | |
| 581 B(4)+B(3)+B(1)+B(0), 119), | |
| 582 kDefPoly(B(116)+B(115)+B(113)+B(112)+B(110)+B(107)+B(106)+B(104)+B(103)+ | |
| 583 B(101)+B(100)+B(99)+B(98)+B(90)+B(89)+B(88)+B(87)+B(82)+B(80)+ | |
| 584 B(79)+B(77)+B(76)+B(75)+B(74)+B(73)+B(71)+B(70)+B(68)+B(65)+ | |
| 585 B(64), B(63)+B(62)+B(59)+B(55)+B(54)+B(48)+B(47)+B(45)+B(44)+ | |
| 586 B(40)+B(39)+B(38)+B(35)+B(33)+B(29)+B(27)+B(26)+B(25)+B(24)+ | |
| 587 B(23)+B(22)+B(21)+B(18)+B(17)+B(15)+B(13)+B(12)+B(10)+B(8)+B(3)+ | |
| 588 B(2)+B(0), 120), | |
| 589 kDefPoly(B(118)+B(117)+B(114)+B(113)+B(112)+B(110)+B(109)+B(104)+B(103)+ | |
| 590 B(101)+B(99)+B(97)+B(96)+B(95)+B(93)+B(92)+B(91)+B(90)+B(89)+ | |
| 591 B(87)+B(85)+B(84)+B(82)+B(81)+B(79)+B(73)+B(72)+B(68)+B(67)+ | |
| 592 B(66)+B(64), B(60)+B(58)+B(57)+B(56)+B(54)+B(53)+B(52)+B(51)+ | |
| 593 B(49)+B(48)+B(47)+B(45)+B(44)+B(38)+B(37)+B(36)+B(35)+B(33)+ | |
| 594 B(32)+B(31)+B(30)+B(27)+B(26)+B(24)+B(23)+B(22)+B(20)+B(19)+ | |
| 595 B(18)+B(16)+B(15)+B(12)+B(6)+B(5)+B(4)+B(2)+B(0), 121), | |
| 596 kDefPoly(B(121)+B(118)+B(114)+B(112)+B(109)+B(106)+B(103)+B(102)+B(101)+ | |
| 597 B(100)+B(97)+B(95)+B(90)+B(89)+B(87)+B(83)+B(81)+B(80)+B(79)+ | |
| 598 B(78)+B(77)+B(76)+B(75)+B(74)+B(72)+B(71)+B(70)+B(69)+B(68)+ | |
| 599 B(66)+B(64), B(61)+B(57)+B(51)+B(50)+B(47)+B(46)+B(43)+B(39)+ | |
| 600 B(38)+B(37)+B(36)+B(34)+B(33)+B(32)+B(30)+B(28)+B(27)+B(24)+ | |
| 601 B(22)+B(20)+B(18)+B(17)+B(14)+B(12)+B(11)+B(9)+B(7)+B(2)+ | |
| 602 B(0), 122), | |
| 603 kDefPoly(B(122)+B(121)+B(120)+B(119)+B(118)+B(117)+B(116)+B(113)+B(112)+ | |
| 604 B(111)+B(109)+B(106)+B(105)+B(103)+B(100)+B(98)+B(97)+B(95)+ | |
| 605 B(93)+B(92)+B(90)+B(87)+B(86)+B(85)+B(83)+B(81)+B(78)+B(77)+ | |
| 606 B(75)+B(74)+B(73)+B(72)+B(71)+B(70)+B(69)+B(68)+B(67)+B(65)+ | |
| 607 B(64), B(63)+B(62)+B(60)+B(55)+B(52)+B(51)+B(49)+B(47)+B(45)+ | |
| 608 B(43)+B(42)+B(41)+B(37)+B(36)+B(35)+B(34)+B(32)+B(28)+B(27)+ | |
| 609 B(26)+B(24)+B(23)+B(21)+B(20)+B(16)+B(13)+B(10)+B(9)+B(8)+B(7)+ | |
| 610 B(5)+B(2)+B(0), 123), | |
| 611 kDefPoly(B(123)+B(121)+B(120)+B(118)+B(117)+B(116)+B(115)+B(112)+B(111)+ | |
| 612 B(110)+B(109)+B(107)+B(104)+B(102)+B(101)+B(100)+B(99)+B(98)+ | |
| 613 B(97)+B(94)+B(90)+B(87)+B(86)+B(84)+B(83)+B(82)+B(79)+B(75)+ | |
| 614 B(72)+B(71)+B(70)+B(64), B(63)+B(56)+B(54)+B(51)+B(50)+B(47)+ | |
| 615 B(45)+B(44)+B(42)+B(39)+B(38)+B(36)+B(34)+B(33)+B(29)+B(26)+ | |
| 616 B(24)+B(20)+B(16)+B(14)+B(11)+B(10)+B(8)+B(7)+B(6)+B(4)+B(2)+ | |
| 617 B(0), 124), | |
| 618 kDefPoly(B(124)+B(123)+B(121)+B(119)+B(118)+B(116)+B(115)+B(114)+B(107)+ | |
| 619 B(105)+B(104)+B(103)+B(102)+B(99)+B(98)+B(96)+B(94)+B(93)+B(89)+ | |
| 620 B(83)+B(82)+B(81)+B(80)+B(79)+B(78)+B(75)+B(74)+B(73)+B(72)+ | |
| 621 B(70)+B(69)+B(68)+B(64), B(63)+B(59)+B(56)+B(55)+B(52)+B(51)+ | |
| 622 B(50)+B(49)+B(48)+B(44)+B(42)+B(38)+B(37)+B(36)+B(33)+B(31)+ | |
| 623 B(29)+B(27)+B(26)+B(25)+B(23)+B(21)+B(19)+B(18)+B(16)+B(14)+ | |
| 624 B(11)+B(8)+B(7)+B(6)+B(4)+B(1)+B(0), 125), | |
| 625 kDefPoly(B(124)+B(122)+B(121)+B(120)+B(119)+B(117)+B(113)+B(110)+B(108)+ | |
| 626 B(105)+B(103)+B(102)+B(101)+B(97)+B(93)+B(91)+B(90)+B(88)+B(86)+ | |
| 627 B(84)+B(82)+B(81)+B(79)+B(77)+B(76)+B(75)+B(73)+B(72)+B(71)+ | |
| 628 B(69)+B(67)+B(64), B(63)+B(62)+B(61)+B(60)+B(58)+B(56)+B(55)+ | |
| 629 B(52)+B(51)+B(48)+B(47)+B(45)+B(44)+B(42)+B(41)+B(40)+B(39)+ | |
| 630 B(37)+B(33)+B(32)+B(30)+B(29)+B(28)+B(27)+B(26)+B(25)+B(24)+ | |
| 631 B(23)+B(19)+B(18)+B(17)+B(16)+B(14)+B(13)+B(11)+B(9)+B(8)+B(7)+ | |
| 632 B(4)+B(2)+B(1)+B(0), 126), | |
| 633 kDefPoly(B(125)+B(124)+B(121)+B(116)+B(115)+B(105)+B(103)+B(101)+B(94)+ | |
| 634 B(93)+B(91)+B(90)+B(88)+B(87)+B(86)+B(85)+B(77)+B(73)+B(72)+ | |
| 635 B(70)+B(68)+B(67), B(63)+B(62)+B(61)+B(59)+B(57)+B(53)+B(52)+ | |
| 636 B(51)+B(49)+B(48)+B(46)+B(44)+B(41)+B(39)+B(38)+B(36)+B(35)+ | |
| 637 B(30)+B(27)+B(25)+B(23)+B(20)+B(19)+B(13)+B(12)+B(11)+B(10)+B(8)+ | |
| 638 B(7)+B(5)+B(4)+B(3)+B(2)+B(0), 127), | |
| 639 kDefPoly(B(127)+B(122)+B(121)+B(118)+B(117)+B(116)+B(109)+B(108)+B(107)+ | |
| 640 B(106)+B(104)+B(103)+B(102)+B(101)+B(96)+B(93)+B(92)+B(91)+B(89)+ | |
| 641 B(86)+B(85)+B(80)+B(78)+B(77)+B(76)+B(75)+B(74)+B(73)+B(72)+ | |
| 642 B(71)+B(66), B(60)+B(56)+B(53)+B(52)+B(50)+B(47)+B(45)+B(41)+ | |
| 643 B(39)+B(38)+B(37)+B(35)+B(34)+B(33)+B(30)+B(28)+B(25)+B(24)+ | |
| 644 B(23)+B(21)+B(20)+B(19)+B(14)+B(13)+B(10)+B(8)+B(5)+B(4)+B(2)+ | |
| 645 B(1)+B(0), 128), | |
| 646 }; | |
| 647 // lint -restore | |
| 648 | |
| 649 // The number of polynomials in POLYS[]. | |
| 650 SELECTANY const int CRC::N_POLYS = sizeof (poly_list) / sizeof (poly_list[0]); | |
| 651 | |
| 652 // The externally visible name of poly_list. | |
| 653 // This guarantees that the size of poly_list is opaque. | |
| 654 SELECTANY const struct CRC::Poly *const CRC::POLYS = poly_list; | |
| 655 | |
| 656 // The "constructor" for a CRC with an default polynomial. | |
| 657 CRC *CRC::Default(int degree, size_t roll_length) { | |
| 658 ASSERT1(32 == degree); | |
| 659 | |
| 660 CRC *crc = CRCImpl::NewInternal(CRC::POLYS[degree].lo, CRC::POLYS[degree].hi, | |
| 661 degree, roll_length); // Build the table | |
| 662 return crc; | |
| 663 } | |
| 664 | |
| 665 // The "constructor" for a CRC with an arbitrary polynomial. | |
| 666 CRC *CRC::New(uint64 lo, uint64 hi, int degree, size_t roll_length) { | |
| 667 return CRCImpl::NewInternal(lo, hi, degree, roll_length); | |
| 668 } | |
| 669 | |
| 670 // Internal version of the "constructor". | |
| 671 CRCImpl *CRCImpl::NewInternal(uint64 lo, uint64 hi, | |
| 672 int degree, size_t roll_length) { | |
| 673 ASSERT1(8 <= degree && degree <= 64); // precondition | |
| 674 ASSERT1(lo != 0 || hi != 0); // precondition | |
| 675 // Generate the tables for extending a CRC by 4 bytes at a time. | |
| 676 // Why 4 and not 8? Because Pentium 4 has such small caches. | |
| 677 struct CRC_pair t[4][256]; | |
| 678 for (int j = 0; j != 4; j++) { // for each byte of extension.... | |
| 679 t[j][0].lo = 0; // a zero has no effect | |
| 680 t[j][0].hi = 0; | |
| 681 for (int i = 128; i != 0; i >>= 1) { // fill in entries for powers of 2 | |
| 682 if (j == 0 && i == 128) { | |
| 683 t[j][i].lo = lo; // top bit in first byte is easy---it's the polynomial | |
| 684 t[j][i].hi = hi; | |
| 685 } else { | |
| 686 // each successive power of two is derive from the previous | |
| 687 // one, either in this table, or the last table | |
| 688 struct CRC_pair pred; | |
| 689 if (i == 128) { | |
| 690 pred = t[j-1][1]; | |
| 691 } else { | |
| 692 pred = t[j][i << 1]; | |
| 693 } | |
| 694 // Advance the CRC by one bit (multiply by X, and take remainder | |
| 695 // through one step of polynomial long division) | |
| 696 if (pred.lo & 1) { | |
| 697 t[j][i].lo = (pred.lo >> 1) ^ (pred.hi << 63) ^ lo; | |
| 698 t[j][i].hi = (pred.hi >> 1) ^ hi; | |
| 699 } else { | |
| 700 t[j][i].lo = (pred.lo >> 1) ^ (pred.hi << 63); | |
| 701 t[j][i].hi = pred.hi >> 1; | |
| 702 } | |
| 703 } | |
| 704 } | |
| 705 // CRCs have the property that CRC(a xor b) == CRC(a) xor CRC(b) | |
| 706 // so we can make all the tables for non-powers of two by | |
| 707 // xoring previously created entries. | |
| 708 for (int i = 2; i != 256; i <<= 1) { | |
| 709 for (int k = i+1; k != (i << 1); k++) { | |
| 710 t[j][k].lo = t[j][i].lo ^ t[j][k-i].lo; | |
| 711 t[j][k].hi = t[j][i].hi ^ t[j][k-i].hi; | |
| 712 } | |
| 713 } | |
| 714 } | |
| 715 | |
| 716 // Copy the newly built tables in t[] into an appropriate | |
| 717 // CRC implenentation object. | |
| 718 CRCImpl *result = 0; | |
| 719 CRC32 *crc32 = 0; | |
| 720 crc32 = new CRC32(); | |
| 721 for (int i = 0; i != 256; i++) { | |
| 722 crc32->table0_[i] = static_cast<uint32>(t[0][i].lo); | |
| 723 crc32->table1_[i] = static_cast<uint32>(t[1][i].lo); | |
| 724 crc32->table2_[i] = static_cast<uint32>(t[2][i].lo); | |
| 725 crc32->table3_[i] = static_cast<uint32>(t[3][i].lo); | |
| 726 } | |
| 727 result = crc32; | |
| 728 | |
| 729 // "result" is now a CRC object of the right type to handle | |
| 730 // the polynomial of the right degree. | |
| 731 | |
| 732 result->roll_length_ = roll_length; | |
| 733 result->degree_ = degree; | |
| 734 result->poly_lo_ = lo; | |
| 735 result->poly_hi_ = hi; | |
| 736 | |
| 737 // Build the table for extending by zeroes. | |
| 738 // Entry i=a-1+3*b (a in {1, 2, 3}, b in {0, 1, 2, 3, ...} | |
| 739 // contains a polynomial Pi such that multiplying | |
| 740 // a CRC by Pi mod P, where P is the CRC polynomial, is equivalent to | |
| 741 // appending a*2**(2*b+SMALL_BITS) zero bytes to the original string. | |
| 742 // Entry is generated by calling ExtendByZeroes() twice using | |
| 743 // half the length from the previous entry. | |
| 744 int pos = 0; | |
| 745 for (uint64 inc_len = (1 << SMALL_BITS); inc_len != 0; inc_len <<= 2) { | |
| 746 result->Empty(&lo, &hi); | |
| 747 for (int k = 0; k != 3; k++) { | |
| 748 result->ExtendByZeroes(&lo, &hi, (size_t) (inc_len >> 1)); | |
| 749 result->ExtendByZeroes(&lo, &hi, (size_t) (inc_len >> 1)); | |
| 750 crc32->zeroes_[pos] = static_cast<uint32>(lo); | |
| 751 pos++; | |
| 752 } | |
| 753 } | |
| 754 | |
| 755 // Calculate the entries in the roll table, used for rolling checksums | |
| 756 // of a fixed length. | |
| 757 // Extend the powers of two in the one-byte extension table by the roll | |
| 758 // length. | |
| 759 int bit = 256; | |
| 760 do { | |
| 761 bit >>= 1; | |
| 762 result->ExtendByZeroes(&t[0][bit].lo, &t[0][bit].hi, roll_length); | |
| 763 } while (bit != 0); | |
| 764 // Calculate the non-powers of two using CRC(a xor b) == CRC(a) xor CRC(b) | |
| 765 for (int i = 2; i != 256; i <<= 1) { | |
| 766 for (int j = i+1; j != (i << 1); j++) { | |
| 767 t[0][j].lo = t[0][i].lo ^ t[0][j-i].lo; | |
| 768 t[0][j].hi = t[0][i].hi ^ t[0][j-i].hi; | |
| 769 } | |
| 770 } | |
| 771 // Now xor the CRC of (binary) 100000001 followed by | |
| 772 // the roll length of zeroes. This will be xored into every | |
| 773 // entry. This will simultaneously roll out the CRC | |
| 774 // of the empty string that's been pushed one byte too far, | |
| 775 // and roll in the CRC of the empty string in the correct place again. | |
| 776 result->Empty(&lo, &hi); | |
| 777 const uint8 x = 0x80; | |
| 778 result->Extend(&lo, &hi, &x, 1); | |
| 779 result->ExtendByZeroes(&lo, &hi, roll_length); | |
| 780 for (int i = 0; i != 256; i++) { | |
| 781 t[0][i].lo ^= lo; | |
| 782 t[0][i].hi ^= hi; | |
| 783 } | |
| 784 | |
| 785 // Put the roll table into the object. | |
| 786 for (int i = 0; i != 256; i++) { | |
| 787 crc32->roll_[i] = static_cast<uint32>(t[0][i].lo); | |
| 788 } | |
| 789 | |
| 790 return result; | |
| 791 } | |
| 792 | |
| 793 // The CRC of the empty string is always the CRC polynomial itself. | |
| 794 void CRCImpl::Empty(uint64 *lo, uint64 *hi) const { | |
| 795 ASSERT1(hi); | |
| 796 ASSERT1(lo); | |
| 797 | |
| 798 *lo = this->poly_lo_; | |
| 799 *hi = this->poly_hi_; | |
| 800 } | |
| 801 | |
| 802 // The 32-bit implementation | |
| 803 | |
| 804 void CRC32::Extend(uint64 *lo, uint64 *hi, const void *bytes, size_t length) | |
| 805 const { | |
| 806 ASSERT1(hi); | |
| 807 ASSERT1(lo); | |
| 808 | |
| 809 hi; // unreferenced formal parameter | |
| 810 | |
| 811 const uint8 *p = static_cast<const uint8 *>(bytes); | |
| 812 const uint8 *e = p + length; | |
| 813 uint32 l = static_cast<uint32>(*lo); | |
| 814 // point x at MIN(first 4-byte aligned byte in string, end of string) | |
| 815 const uint8 *x = p + ((zero_ptr - p) & 3); | |
| 816 if (x > e) { | |
| 817 x = e; | |
| 818 } | |
| 819 // Process bytes until finished or p is 4-byte aligned | |
| 820 while (p != x) { | |
| 821 int c = (l & 0xff) ^ *p++; | |
| 822 l = this->table0_[c] ^ (l >> 8); | |
| 823 } | |
| 824 // point x at MIN(last 4-byte aligned byte in string, end of string) | |
| 825 x = e - ((e - zero_ptr) & 3); | |
| 826 // Process bytes 4 at a time | |
| 827 while (p < x) { | |
| 828 uint32 c = l ^ *reinterpret_cast<const uint32*>(p); | |
| 829 p += 4; | |
| 830 l = this->table3_[c & 0xff] ^ | |
| 831 this->table2_[(c >> 8) & 0xff] ^ | |
| 832 this->table1_[(c >> 16) & 0xff] ^ | |
| 833 this->table0_[c >> 24]; | |
| 834 } | |
| 835 | |
| 836 // Process the last few bytes | |
| 837 while (p != e) { | |
| 838 int c = (l & 0xff) ^ *p++; | |
| 839 l = this->table0_[c] ^ (l >> 8); | |
| 840 } | |
| 841 *lo = l; | |
| 842 } | |
| 843 | |
| 844 void CRC32::ExtendByZeroes(uint64 *lo, uint64 *hi, size_t length) const { | |
| 845 ASSERT1(hi); | |
| 846 ASSERT1(lo); | |
| 847 | |
| 848 // Process the low order SMALL_BITS of the length by simply | |
| 849 // using Extend() on an array of bytes that are zero. | |
| 850 int small_part = (length & ((1 << SMALL_BITS)-1)); | |
| 851 if (small_part != 0) { | |
| 852 this->Extend(lo, hi, zeroes, small_part); | |
| 853 } | |
| 854 length >>= SMALL_BITS; | |
| 855 if (length != 0) { // if the length was at least 2**SMALL_BITS | |
| 856 uint32 l = static_cast<uint32>(*lo); | |
| 857 uint32 onebit = 1; | |
| 858 onebit <<= this->degree_ - 1; | |
| 859 // For each pair of bits in length | |
| 860 // (after the low-oder bits have been removed) | |
| 861 // we lookup the appropriate polynomial in the zeroes_ array | |
| 862 // and do a polynomial long multiplication (mod the CRC polynomial) | |
| 863 // to extend the CRC by the appropriate number of bits. | |
| 864 for (int i = 0; length != 0; i += 3, length >>= 2) { | |
| 865 int c = length & 3; // pick next two bits | |
| 866 if (c != 0) { // if they are not zero, | |
| 867 // multiply by entry in table | |
| 868 uint32 m = this->zeroes_[c+i-1]; | |
| 869 uint32 result = 0; | |
| 870 for (uint32 one = onebit; one != 0; one >>= 1) { | |
| 871 if ((l & one) != 0) { | |
| 872 result ^= m; | |
| 873 } | |
| 874 if (m & 1) { | |
| 875 m = (m >> 1) ^ static_cast<uint32>(poly_lo_); | |
| 876 } else { | |
| 877 m = (m >> 1); | |
| 878 } | |
| 879 } | |
| 880 l = result; | |
| 881 } | |
| 882 } | |
| 883 *lo = l; | |
| 884 } | |
| 885 } | |
| 886 | |
| 887 void CRC32::Roll(uint64 *lo, uint64 *hi, uint8 o_byte, uint8 i_byte) const { | |
| 888 ASSERT1(hi); | |
| 889 ASSERT1(lo); | |
| 890 | |
| 891 hi; // unreferenced formal parameter | |
| 892 | |
| 893 uint32 l = static_cast<uint32>(*lo); | |
| 894 // Roll in i_byte and out o_byte | |
| 895 *lo = this->table0_[(l & 0xff) ^ i_byte] ^ (l >> 8) ^ this->roll_[o_byte]; | |
| 896 } | |
| 897 | |
| 898 } // namespace omaha | |
| 899 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 624713003:
Keep only base/extractor.[cc|h]. (Closed)
Base URL: https://chromium.googlesource.com/external/omaha.git@master