diff options
author | f0b0s <f0b0s@yandex-team.ru> | 2022-02-10 16:46:51 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:46:51 +0300 |
commit | cdae02d225fb5b3afbb28990e79a7ac6c9125327 (patch) | |
tree | 49e222ea1c5804306084bb3ae065bb702625360f /contrib/libs/crcutil/gf_util.h | |
parent | deabc5260ac2e17b8f5152ee060bec1740613540 (diff) | |
download | ydb-cdae02d225fb5b3afbb28990e79a7ac6c9125327.tar.gz |
Restoring authorship annotation for <f0b0s@yandex-team.ru>. Commit 2 of 2.
Diffstat (limited to 'contrib/libs/crcutil/gf_util.h')
-rw-r--r-- | contrib/libs/crcutil/gf_util.h | 608 |
1 files changed, 304 insertions, 304 deletions
diff --git a/contrib/libs/crcutil/gf_util.h b/contrib/libs/crcutil/gf_util.h index 2a98dfd9e4..43c1d6b216 100644 --- a/contrib/libs/crcutil/gf_util.h +++ b/contrib/libs/crcutil/gf_util.h @@ -1,304 +1,304 @@ -// Copyright 2010 Google Inc. All rights reserved. -// -// 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. - -// Defines GfUtil template class which implements -// 1. some useful operations in GF(2^n), -// 2. CRC helper function (e.g. concatenation of CRCs) which are -// not affected by specific implemenation of CRC computation per se. -// -// Please read crc.pdf to understand how it all works. - -#ifndef CRCUTIL_GF_UTIL_H_ -#define CRCUTIL_GF_UTIL_H_ - -#include "base_types.h" // uint8, uint64 -#include "crc_casts.h" // TO_BYTE() -#include "platform.h" // GCC_ALIGN_ATTRIBUTE(16), SHIFT_*_SAFE - -namespace crcutil { - -#pragma pack(push, 16) - -// "Crc" is the type used internally and to return values of N-bit CRC. -template<typename Crc> class GfUtil { - public: - // Initializes the tables given generating polynomial of degree (degree). - // If "canonical" is true, starting CRC value and computed CRC value will be - // XOR-ed with 111...111. - GfUtil() {} - GfUtil(const Crc &generating_polynomial, size_t degree, bool canonical) { - Init(generating_polynomial, degree, canonical); - } - void Init(const Crc &generating_polynomial, size_t degree, bool canonical) { - Crc one = 1; - one <<= degree - 1; - this->generating_polynomial_ = generating_polynomial; - this->crc_bytes_ = (degree + 7) >> 3; - this->degree_ = degree; - this->one_ = one; - if (canonical) { - this->canonize_ = one | (one - 1); - } else { - this->canonize_ = 0; - } - this->normalize_[0] = 0; - this->normalize_[1] = generating_polynomial; - - Crc k = one >> 1; - for (size_t i = 0; i < sizeof(uint64) * 8; ++i) { - this->x_pow_2n_[i] = k; - k = Multiply(k, k); - } - - this->crc_of_crc_ = Multiply(this->canonize_, - this->one_ ^ Xpow8N((degree + 7) >> 3)); - - FindLCD(Xpow8N(this->crc_bytes_), &this->x_pow_minus_W_); - } - - // Returns generating polynomial. - Crc GeneratingPolynomial() const { - return this->generating_polynomial_; - } - - // Returns number of bits in CRC (degree of generating polynomial). - size_t Degree() const { - return this->degree_; - } - - // Returns start/finish adjustment constant. - Crc Canonize() const { - return this->canonize_; - } - - // Returns normalized value of 1. - Crc One() const { - return this->one_; - } - - // Returns value of CRC(A, |A|, start_new) given known - // crc=CRC(A, |A|, start_old) -- without touching the data. - Crc ChangeStartValue(const Crc &crc, uint64 bytes, - const Crc &start_old, - const Crc &start_new) const { - return (crc ^ Multiply(start_new ^ start_old, Xpow8N(bytes))); - } - - // Returns CRC of concatenation of blocks A and B when CRCs - // of blocks A and B are known -- without touching the data. - // - // To be precise, given CRC(A, |A|, startA) and CRC(B, |B|, 0), - // returns CRC(AB, |AB|, startA). - Crc Concatenate(const Crc &crc_A, const Crc &crc_B, uint64 bytes_B) const { - return ChangeStartValue(crc_B, bytes_B, 0 /* start_B */, crc_A); - } - - // Returns CRC of sequence of zeroes -- without touching the data. - Crc CrcOfZeroes(uint64 bytes, const Crc &start) const { - Crc tmp = Multiply(start ^ this->canonize_, Xpow8N(bytes)); - return (tmp ^ this->canonize_); - } - - // Given CRC of a message, stores extra (degree + 7)/8 bytes after - // the message so that CRC(message+extra, start) = result. - // Does not change CRC start value (use ChangeStartValue for that). - // Returns number of stored bytes. - size_t StoreComplementaryCrc(void *dst, - const Crc &message_crc, - const Crc &result) const { - Crc crc0 = Multiply(result ^ this->canonize_, this->x_pow_minus_W_); - crc0 ^= message_crc ^ this->canonize_; - uint8 *d = reinterpret_cast<uint8 *>(dst); - for (size_t i = 0; i < this->crc_bytes_; ++i) { - d[i] = TO_BYTE(crc0); - crc0 >>= 8; - } - return this->crc_bytes_; - } - - // Stores given CRC of a message as (degree + 7)/8 bytes filled - // with 0s to the right. Returns number of stored bytes. - // CRC of the message and stored CRC is a constant value returned - // by CrcOfCrc() -- it does not depend on contents of the message. - size_t StoreCrc(void *dst, const Crc &crc) const { - uint8 *d = reinterpret_cast<uint8 *>(dst); - Crc crc0 = crc; - for (size_t i = 0; i < this->crc_bytes_; ++i) { - d[i] = TO_BYTE(crc0); - crc0 >>= 8; - } - return this->crc_bytes_; - } - - // Returns expected CRC value of CRC(Message,CRC(Message)) - // when CRC is stored after the message. This value is fixed - // and does not depend on the message or CRC start value. - Crc CrcOfCrc() const { - return this->crc_of_crc_; - } - - // Returns ((a * b) mod P) where "a" and "b" are of degree <= (D-1). - Crc Multiply(const Crc &aa, const Crc &bb) const { - Crc a = aa; - Crc b = bb; - if ((a ^ (a - 1)) < (b ^ (b - 1))) { - Crc temp = a; - a = b; - b = temp; - } - - if (a == 0) { - return a; - } - - Crc product = 0; - Crc one = this->one_; - for (; a != 0; a <<= 1) { - if ((a & one) != 0) { - product ^= b; - a ^= one; - } - b = (b >> 1) ^ this->normalize_[Downcast<Crc, size_t>(b & 1)]; - } - - return product; - } - - // Returns ((unnorm * m) mod P) where degree of m is <= (D-1) - // and degree of value "unnorm" is provided explicitly. - Crc MultiplyUnnormalized(const Crc &unnorm, size_t degree, - const Crc &m) const { - Crc v = unnorm; - Crc result = 0; - while (degree > this->degree_) { - degree -= this->degree_; - Crc value = v & (this->one_ | (this->one_ - 1)); - result ^= Multiply(value, Multiply(m, XpowN(degree))); - v >>= this->degree_; - } - result ^= Multiply(v << (this->degree_ - degree), m); - return result; - } - - // returns ((x ** n) mod P). - Crc XpowN(uint64 n) const { - Crc one = this->one_; - Crc result = one; - - for (size_t i = 0; n != 0; ++i, n >>= 1) { - if (n & 1) { - result = Multiply(result, this->x_pow_2n_[i]); - } - } - - return result; - } - - // Returns (x ** (8 * n) mod P). - Crc Xpow8N(uint64 n) const { - return XpowN(n << 3); - } - - // Returns remainder (A mod B) and sets *q = (A/B) of division - // of two polynomials: - // A = dividend + dividend_x_pow_D_coef * x**degree, - // B = divisor. - Crc Divide(const Crc ÷nd0, int dividend_x_pow_D_coef, - const Crc &divisor0, Crc *q) const { - Crc divisor = divisor0; - Crc dividend = dividend0; - Crc quotient = 0; - Crc coef = this->one_; - - while ((divisor & 1) == 0) { - divisor >>= 1; - coef >>= 1; - } - - if (dividend_x_pow_D_coef) { - quotient = coef >> 1; - dividend ^= divisor >> 1; - } - - Crc x_pow_degree_b = 1; - for (;;) { - if ((dividend & x_pow_degree_b) != 0) { - dividend ^= divisor; - quotient ^= coef; - } - if (coef == this->one_) { - break; - } - coef <<= 1; - x_pow_degree_b <<= 1; - divisor <<= 1; - } - - *q = quotient; - return dividend; - } - - // Extended Euclid's algorith -- for given A finds LCD(A, P) and - // value B such that (A * B) mod P = LCD(A, P). - Crc FindLCD(const Crc &A, Crc *B) const { - if (A == 0 || A == this->one_) { - *B = A; - return A; - } - - // Actually, generating polynomial is - // (generating_polynomial_ + x**degree). - int r0_x_pow_D_coef = 1; - Crc r0 = this->generating_polynomial_; - Crc b0 = 0; - Crc r1 = A; - Crc b1 = this->one_; - - for (;;) { - Crc q; - Crc r = Divide(r0, r0_x_pow_D_coef, r1, &q); - if (r == 0) { - break; - } - r0_x_pow_D_coef = 0; - - r0 = r1; - r1 = r; - - Crc b = b0 ^ Multiply(q, b1); - b0 = b1; - b1 = b; - } - - *B = b1; - return r1; - } - - protected: - Crc canonize_; - Crc x_pow_2n_[sizeof(uint64) * 8]; - Crc generating_polynomial_; - Crc one_; - Crc x_pow_minus_W_; - Crc crc_of_crc_; - Crc normalize_[2]; - size_t crc_bytes_; - size_t degree_; -} GCC_ALIGN_ATTRIBUTE(16); - -#pragma pack(pop) - -} // namespace crcutil - -#endif // CRCUTIL_GF_UTIL_H_ +// Copyright 2010 Google Inc. All rights reserved. +// +// 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. + +// Defines GfUtil template class which implements +// 1. some useful operations in GF(2^n), +// 2. CRC helper function (e.g. concatenation of CRCs) which are +// not affected by specific implemenation of CRC computation per se. +// +// Please read crc.pdf to understand how it all works. + +#ifndef CRCUTIL_GF_UTIL_H_ +#define CRCUTIL_GF_UTIL_H_ + +#include "base_types.h" // uint8, uint64 +#include "crc_casts.h" // TO_BYTE() +#include "platform.h" // GCC_ALIGN_ATTRIBUTE(16), SHIFT_*_SAFE + +namespace crcutil { + +#pragma pack(push, 16) + +// "Crc" is the type used internally and to return values of N-bit CRC. +template<typename Crc> class GfUtil { + public: + // Initializes the tables given generating polynomial of degree (degree). + // If "canonical" is true, starting CRC value and computed CRC value will be + // XOR-ed with 111...111. + GfUtil() {} + GfUtil(const Crc &generating_polynomial, size_t degree, bool canonical) { + Init(generating_polynomial, degree, canonical); + } + void Init(const Crc &generating_polynomial, size_t degree, bool canonical) { + Crc one = 1; + one <<= degree - 1; + this->generating_polynomial_ = generating_polynomial; + this->crc_bytes_ = (degree + 7) >> 3; + this->degree_ = degree; + this->one_ = one; + if (canonical) { + this->canonize_ = one | (one - 1); + } else { + this->canonize_ = 0; + } + this->normalize_[0] = 0; + this->normalize_[1] = generating_polynomial; + + Crc k = one >> 1; + for (size_t i = 0; i < sizeof(uint64) * 8; ++i) { + this->x_pow_2n_[i] = k; + k = Multiply(k, k); + } + + this->crc_of_crc_ = Multiply(this->canonize_, + this->one_ ^ Xpow8N((degree + 7) >> 3)); + + FindLCD(Xpow8N(this->crc_bytes_), &this->x_pow_minus_W_); + } + + // Returns generating polynomial. + Crc GeneratingPolynomial() const { + return this->generating_polynomial_; + } + + // Returns number of bits in CRC (degree of generating polynomial). + size_t Degree() const { + return this->degree_; + } + + // Returns start/finish adjustment constant. + Crc Canonize() const { + return this->canonize_; + } + + // Returns normalized value of 1. + Crc One() const { + return this->one_; + } + + // Returns value of CRC(A, |A|, start_new) given known + // crc=CRC(A, |A|, start_old) -- without touching the data. + Crc ChangeStartValue(const Crc &crc, uint64 bytes, + const Crc &start_old, + const Crc &start_new) const { + return (crc ^ Multiply(start_new ^ start_old, Xpow8N(bytes))); + } + + // Returns CRC of concatenation of blocks A and B when CRCs + // of blocks A and B are known -- without touching the data. + // + // To be precise, given CRC(A, |A|, startA) and CRC(B, |B|, 0), + // returns CRC(AB, |AB|, startA). + Crc Concatenate(const Crc &crc_A, const Crc &crc_B, uint64 bytes_B) const { + return ChangeStartValue(crc_B, bytes_B, 0 /* start_B */, crc_A); + } + + // Returns CRC of sequence of zeroes -- without touching the data. + Crc CrcOfZeroes(uint64 bytes, const Crc &start) const { + Crc tmp = Multiply(start ^ this->canonize_, Xpow8N(bytes)); + return (tmp ^ this->canonize_); + } + + // Given CRC of a message, stores extra (degree + 7)/8 bytes after + // the message so that CRC(message+extra, start) = result. + // Does not change CRC start value (use ChangeStartValue for that). + // Returns number of stored bytes. + size_t StoreComplementaryCrc(void *dst, + const Crc &message_crc, + const Crc &result) const { + Crc crc0 = Multiply(result ^ this->canonize_, this->x_pow_minus_W_); + crc0 ^= message_crc ^ this->canonize_; + uint8 *d = reinterpret_cast<uint8 *>(dst); + for (size_t i = 0; i < this->crc_bytes_; ++i) { + d[i] = TO_BYTE(crc0); + crc0 >>= 8; + } + return this->crc_bytes_; + } + + // Stores given CRC of a message as (degree + 7)/8 bytes filled + // with 0s to the right. Returns number of stored bytes. + // CRC of the message and stored CRC is a constant value returned + // by CrcOfCrc() -- it does not depend on contents of the message. + size_t StoreCrc(void *dst, const Crc &crc) const { + uint8 *d = reinterpret_cast<uint8 *>(dst); + Crc crc0 = crc; + for (size_t i = 0; i < this->crc_bytes_; ++i) { + d[i] = TO_BYTE(crc0); + crc0 >>= 8; + } + return this->crc_bytes_; + } + + // Returns expected CRC value of CRC(Message,CRC(Message)) + // when CRC is stored after the message. This value is fixed + // and does not depend on the message or CRC start value. + Crc CrcOfCrc() const { + return this->crc_of_crc_; + } + + // Returns ((a * b) mod P) where "a" and "b" are of degree <= (D-1). + Crc Multiply(const Crc &aa, const Crc &bb) const { + Crc a = aa; + Crc b = bb; + if ((a ^ (a - 1)) < (b ^ (b - 1))) { + Crc temp = a; + a = b; + b = temp; + } + + if (a == 0) { + return a; + } + + Crc product = 0; + Crc one = this->one_; + for (; a != 0; a <<= 1) { + if ((a & one) != 0) { + product ^= b; + a ^= one; + } + b = (b >> 1) ^ this->normalize_[Downcast<Crc, size_t>(b & 1)]; + } + + return product; + } + + // Returns ((unnorm * m) mod P) where degree of m is <= (D-1) + // and degree of value "unnorm" is provided explicitly. + Crc MultiplyUnnormalized(const Crc &unnorm, size_t degree, + const Crc &m) const { + Crc v = unnorm; + Crc result = 0; + while (degree > this->degree_) { + degree -= this->degree_; + Crc value = v & (this->one_ | (this->one_ - 1)); + result ^= Multiply(value, Multiply(m, XpowN(degree))); + v >>= this->degree_; + } + result ^= Multiply(v << (this->degree_ - degree), m); + return result; + } + + // returns ((x ** n) mod P). + Crc XpowN(uint64 n) const { + Crc one = this->one_; + Crc result = one; + + for (size_t i = 0; n != 0; ++i, n >>= 1) { + if (n & 1) { + result = Multiply(result, this->x_pow_2n_[i]); + } + } + + return result; + } + + // Returns (x ** (8 * n) mod P). + Crc Xpow8N(uint64 n) const { + return XpowN(n << 3); + } + + // Returns remainder (A mod B) and sets *q = (A/B) of division + // of two polynomials: + // A = dividend + dividend_x_pow_D_coef * x**degree, + // B = divisor. + Crc Divide(const Crc ÷nd0, int dividend_x_pow_D_coef, + const Crc &divisor0, Crc *q) const { + Crc divisor = divisor0; + Crc dividend = dividend0; + Crc quotient = 0; + Crc coef = this->one_; + + while ((divisor & 1) == 0) { + divisor >>= 1; + coef >>= 1; + } + + if (dividend_x_pow_D_coef) { + quotient = coef >> 1; + dividend ^= divisor >> 1; + } + + Crc x_pow_degree_b = 1; + for (;;) { + if ((dividend & x_pow_degree_b) != 0) { + dividend ^= divisor; + quotient ^= coef; + } + if (coef == this->one_) { + break; + } + coef <<= 1; + x_pow_degree_b <<= 1; + divisor <<= 1; + } + + *q = quotient; + return dividend; + } + + // Extended Euclid's algorith -- for given A finds LCD(A, P) and + // value B such that (A * B) mod P = LCD(A, P). + Crc FindLCD(const Crc &A, Crc *B) const { + if (A == 0 || A == this->one_) { + *B = A; + return A; + } + + // Actually, generating polynomial is + // (generating_polynomial_ + x**degree). + int r0_x_pow_D_coef = 1; + Crc r0 = this->generating_polynomial_; + Crc b0 = 0; + Crc r1 = A; + Crc b1 = this->one_; + + for (;;) { + Crc q; + Crc r = Divide(r0, r0_x_pow_D_coef, r1, &q); + if (r == 0) { + break; + } + r0_x_pow_D_coef = 0; + + r0 = r1; + r1 = r; + + Crc b = b0 ^ Multiply(q, b1); + b0 = b1; + b1 = b; + } + + *B = b1; + return r1; + } + + protected: + Crc canonize_; + Crc x_pow_2n_[sizeof(uint64) * 8]; + Crc generating_polynomial_; + Crc one_; + Crc x_pow_minus_W_; + Crc crc_of_crc_; + Crc normalize_[2]; + size_t crc_bytes_; + size_t degree_; +} GCC_ALIGN_ATTRIBUTE(16); + +#pragma pack(pop) + +} // namespace crcutil + +#endif // CRCUTIL_GF_UTIL_H_ |