35 const std::vector<int32_t>& coefficients)
38 DCHECK(!coefficients.empty());
39 if (coefficients.size() == 1 || coefficients.front() != 0) {
40 m_coefficients = coefficients;
44 size_t firstNonZero = 1;
45 while (firstNonZero < coefficients.size() &&
46 coefficients[firstNonZero] == 0) {
49 if (firstNonZero == coefficients.size()) {
50 m_coefficients = m_field->GetZero()->GetCoefficients();
52 m_coefficients.resize(coefficients.size() - firstNonZero);
53 for (size_t i = firstNonZero, j = 0; i < coefficients.size(); i++, j++)
54 m_coefficients[j] = coefficients[i];
82CBC_ReedSolomonGF256Poly::
AddOrSubtract(
const CBC_ReedSolomonGF256Poly* other) {
84 return other->Clone();
88 std::vector<int32_t> smallerCoefficients = m_coefficients;
89 std::vector<int32_t> largerCoefficients = other->GetCoefficients();
90 if (smallerCoefficients.size() > largerCoefficients.size())
91 std::swap(smallerCoefficients, largerCoefficients);
93 std::vector<int32_t> sumDiff(largerCoefficients.size());
94 size_t lengthDiff = largerCoefficients.size() - smallerCoefficients.size();
95 for (size_t i = 0; i < lengthDiff; ++i)
96 sumDiff[i] = largerCoefficients[i];
98 for (size_t i = lengthDiff; i < largerCoefficients.size(); ++i) {
100 smallerCoefficients[i - lengthDiff]
, largerCoefficients[i]
);
102 return std::make_unique<CBC_ReedSolomonGF256Poly>(m_field, sumDiff);
106 const CBC_ReedSolomonGF256Poly* other) {
107 if (IsZero() || other->IsZero())
108 return m_field->GetZero()->Clone();
110 const std::vector<int32_t>& aCoefficients = m_coefficients;
111 const std::vector<int32_t>& bCoefficients = other->GetCoefficients();
112 size_t aLength = aCoefficients.size();
113 size_t bLength = bCoefficients.size();
114 std::vector<int32_t> product(aLength + bLength - 1);
115 for (size_t i = 0; i < aLength; i++) {
116 int32_t aCoeff = aCoefficients[i];
117 for (size_t j = 0; j < bLength; j++) {
118 product[i + j] = CBC_ReedSolomonGF256::AddOrSubtract(
119 product[i + j], m_field->Multiply(aCoeff, bCoefficients[j]));
122 return std::make_unique<CBC_ReedSolomonGF256Poly>(m_field, product);
127 int32_t coefficient)
const {
130 if (coefficient == 0)
131 return m_field->GetZero()->Clone();
133 size_t size = m_coefficients.size();
134 std::vector<int32_t> product(size + degree);
135 for (size_t i = 0; i < size; i++)
136 product[i] = m_field->Multiply(m_coefficients[i], coefficient);
138 return std::make_unique<CBC_ReedSolomonGF256Poly>(m_field, product);
142 const CBC_ReedSolomonGF256Poly* other) {
146 auto quotient = m_field->GetZero()->Clone();
149 auto remainder = Clone();
154 absl::optional<int32_t> inverseDenominatorLeadingTeam =
155 m_field->Inverse(denominatorLeadingTerm);
156 if (!inverseDenominatorLeadingTeam.has_value())
159 while (remainder->GetDegree() >= other
->GetDegree() && !remainder->IsZero()) {
160 int32_t degreeDifference = remainder->GetDegree() - other
->GetDegree();
162 m_field->Multiply(remainder->GetCoefficients((remainder->GetDegree())),
163 inverseDenominatorLeadingTeam.value());
164 auto term = other->MultiplyByMonomial(degreeDifference, scale);
167 auto iteratorQuotient = m_field->BuildMonomial(degreeDifference, scale);
168 if (!iteratorQuotient)
170 quotient = quotient->AddOrSubtract(iteratorQuotient.get());
173 remainder = remainder->AddOrSubtract(term.get());