1 // Copyright 2014 The PDFium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6 // Original code is licensed as follows:
7 /*
8 * Copyright 2006 Jeremias Maerki.
9 *
10 * Licensed under the Apache License, Version 2.0 (the "License");
11 * you may not use this file except in compliance with the License.
12 * You may obtain a copy of the License at
13 *
14 * http://www.apache.org/licenses/LICENSE-2.0
15 *
16 * Unless required by applicable law or agreed to in writing, software
17 * distributed under the License is distributed on an "AS IS" BASIS,
18 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19 * See the License for the specific language governing permissions and
20 * limitations under the License.
21 */
22
23 #include "fxbarcode/datamatrix/BC_ErrorCorrection.h"
24
25 #include <stdint.h>
26
27 #include <algorithm>
28 #include <array>
29 #include <vector>
30
31 #include "core/fxcrt/check.h"
32 #include "core/fxcrt/fixed_size_data_vector.h"
33 #include "core/fxcrt/span.h"
34 #include "fxbarcode/datamatrix/BC_Encoder.h"
35 #include "fxbarcode/datamatrix/BC_SymbolInfo.h"
36
37 namespace {
38
39 constexpr std::array<uint8_t, 5> FACTORS_0 = {{228, 48, 15, 111, 62}};
40
41 constexpr std::array<uint8_t, 7> FACTORS_1 = {{23, 68, 144, 134, 240, 92, 254}};
42
43 constexpr std::array<uint8_t, 10> FACTORS_2 = {
44 {28, 24, 185, 166, 223, 248, 116, 255, 110, 61}};
45
46 constexpr std::array<uint8_t, 11> FACTORS_3 = {
47 {175, 138, 205, 12, 194, 168, 39, 245, 60, 97, 120}};
48
49 constexpr std::array<uint8_t, 12> FACTORS_4 = {
50 {41, 153, 158, 91, 61, 42, 142, 213, 97, 178, 100, 242}};
51
52 constexpr std::array<uint8_t, 14> FACTORS_5 = {
53 {156, 97, 192, 252, 95, 9, 157, 119, 138, 45, 18, 186, 83, 185}};
54
55 constexpr std::array<uint8_t, 18> FACTORS_6 = {{83, 195, 100, 39, 188, 75, 66,
56 61, 241, 213, 109, 129, 94, 254,
57 225, 48, 90, 188}};
58
59 constexpr std::array<uint8_t, 20> FACTORS_7 = {
60 {15, 195, 244, 9, 233, 71, 168, 2, 188, 160,
61 153, 145, 253, 79, 108, 82, 27, 174, 186, 172}};
62
63 constexpr std::array<uint8_t, 24> FACTORS_8 = {
64 {52, 190, 88, 205, 109, 39, 176, 21, 155, 197, 251, 223,
65 155, 21, 5, 172, 254, 124, 12, 181, 184, 96, 50, 193}};
66
67 constexpr std::array<uint8_t, 28> FACTORS_9 = {
68 {211, 231, 43, 97, 71, 96, 103, 174, 37, 151, 170, 53, 75, 34,
69 249, 121, 17, 138, 110, 213, 141, 136, 120, 151, 233, 168, 93, 255}};
70
71 constexpr std::array<uint8_t, 36> FACTORS_10 = {
72 {245, 127, 242, 218, 130, 250, 162, 181, 102, 120, 84, 179,
73 220, 251, 80, 182, 229, 18, 2, 4, 68, 33, 101, 137,
74 95, 119, 115, 44, 175, 184, 59, 25, 225, 98, 81, 112}};
75
76 constexpr std::array<uint8_t, 42> FACTORS_11 = {
77 {77, 193, 137, 31, 19, 38, 22, 153, 247, 105, 122, 2, 245, 133,
78 242, 8, 175, 95, 100, 9, 167, 105, 214, 111, 57, 121, 21, 1,
79 253, 57, 54, 101, 248, 202, 69, 50, 150, 177, 226, 5, 9, 5}};
80
81 constexpr std::array<uint8_t, 48> FACTORS_12 = {
82 {245, 132, 172, 223, 96, 32, 117, 22, 238, 133, 238, 231,
83 205, 188, 237, 87, 191, 106, 16, 147, 118, 23, 37, 90,
84 170, 205, 131, 88, 120, 100, 66, 138, 186, 240, 82, 44,
85 176, 87, 187, 147, 160, 175, 69, 213, 92, 253, 225, 19}};
86
87 constexpr std::array<uint8_t, 56> FACTORS_13 = {
88 {175, 9, 223, 238, 12, 17, 220, 208, 100, 29, 175, 170, 230, 192,
89 215, 235, 150, 159, 36, 223, 38, 200, 132, 54, 228, 146, 218, 234,
90 117, 203, 29, 232, 144, 238, 22, 150, 201, 117, 62, 207, 164, 13,
91 137, 245, 127, 67, 247, 28, 155, 43, 203, 107, 233, 53, 143, 46}};
92
93 constexpr std::array<uint8_t, 62> FACTORS_14 = {
94 {242, 93, 169, 50, 144, 210, 39, 118, 202, 188, 201, 189, 143,
95 108, 196, 37, 185, 112, 134, 230, 245, 63, 197, 190, 250, 106,
96 185, 221, 175, 64, 114, 71, 161, 44, 147, 6, 27, 218, 51,
97 63, 87, 10, 40, 130, 188, 17, 163, 31, 176, 170, 4, 107,
98 232, 7, 94, 166, 224, 124, 86, 47, 11, 204}};
99
100 constexpr std::array<uint8_t, 68> FACTORS_15 = {
101 {220, 228, 173, 89, 251, 149, 159, 56, 89, 33, 147, 244, 154, 36,
102 73, 127, 213, 136, 248, 180, 234, 197, 158, 177, 68, 122, 93, 213,
103 15, 160, 227, 236, 66, 139, 153, 185, 202, 167, 179, 25, 220, 232,
104 96, 210, 231, 136, 223, 239, 181, 241, 59, 52, 172, 25, 49, 232,
105 211, 189, 64, 54, 108, 153, 132, 63, 96, 103, 82, 186}};
106
107 constexpr std::array<pdfium::span<const uint8_t>, 16> FACTORS = {
108 {FACTORS_0, FACTORS_1, FACTORS_2, FACTORS_3, FACTORS_4, FACTORS_5,
109 FACTORS_6, FACTORS_7, FACTORS_8, FACTORS_9, FACTORS_10, FACTORS_11,
110 FACTORS_12, FACTORS_13, FACTORS_14, FACTORS_15}};
111
112 constexpr std::array<uint8_t, 256> LOG = {
113 {0, 0, 1, 240, 2, 225, 241, 53, 3, 38, 226, 133, 242, 43, 54,
114 210, 4, 195, 39, 114, 227, 106, 134, 28, 243, 140, 44, 23, 55, 118,
115 211, 234, 5, 219, 196, 96, 40, 222, 115, 103, 228, 78, 107, 125, 135,
116 8, 29, 162, 244, 186, 141, 180, 45, 99, 24, 49, 56, 13, 119, 153,
117 212, 199, 235, 91, 6, 76, 220, 217, 197, 11, 97, 184, 41, 36, 223,
118 253, 116, 138, 104, 193, 229, 86, 79, 171, 108, 165, 126, 145, 136, 34,
119 9, 74, 30, 32, 163, 84, 245, 173, 187, 204, 142, 81, 181, 190, 46,
120 88, 100, 159, 25, 231, 50, 207, 57, 147, 14, 67, 120, 128, 154, 248,
121 213, 167, 200, 63, 236, 110, 92, 176, 7, 161, 77, 124, 221, 102, 218,
122 95, 198, 90, 12, 152, 98, 48, 185, 179, 42, 209, 37, 132, 224, 52,
123 254, 239, 117, 233, 139, 22, 105, 27, 194, 113, 230, 206, 87, 158, 80,
124 189, 172, 203, 109, 175, 166, 62, 127, 247, 146, 66, 137, 192, 35, 252,
125 10, 183, 75, 216, 31, 83, 33, 73, 164, 144, 85, 170, 246, 65, 174,
126 61, 188, 202, 205, 157, 143, 169, 82, 72, 182, 215, 191, 251, 47, 178,
127 89, 151, 101, 94, 160, 123, 26, 112, 232, 21, 51, 238, 208, 131, 58,
128 69, 148, 18, 15, 16, 68, 17, 121, 149, 129, 19, 155, 59, 249, 70,
129 214, 250, 168, 71, 201, 156, 64, 60, 237, 130, 111, 20, 93, 122, 177,
130 150}};
131
132 constexpr std::array<uint8_t, 256> ALOG = {
133 {1, 2, 4, 8, 16, 32, 64, 128, 45, 90, 180, 69, 138, 57, 114,
134 228, 229, 231, 227, 235, 251, 219, 155, 27, 54, 108, 216, 157, 23, 46,
135 92, 184, 93, 186, 89, 178, 73, 146, 9, 18, 36, 72, 144, 13, 26,
136 52, 104, 208, 141, 55, 110, 220, 149, 7, 14, 28, 56, 112, 224, 237,
137 247, 195, 171, 123, 246, 193, 175, 115, 230, 225, 239, 243, 203, 187, 91,
138 182, 65, 130, 41, 82, 164, 101, 202, 185, 95, 190, 81, 162, 105, 210,
139 137, 63, 126, 252, 213, 135, 35, 70, 140, 53, 106, 212, 133, 39, 78,
140 156, 21, 42, 84, 168, 125, 250, 217, 159, 19, 38, 76, 152, 29, 58,
141 116, 232, 253, 215, 131, 43, 86, 172, 117, 234, 249, 223, 147, 11, 22,
142 44, 88, 176, 77, 154, 25, 50, 100, 200, 189, 87, 174, 113, 226, 233,
143 255, 211, 139, 59, 118, 236, 245, 199, 163, 107, 214, 129, 47, 94, 188,
144 85, 170, 121, 242, 201, 191, 83, 166, 97, 194, 169, 127, 254, 209, 143,
145 51, 102, 204, 181, 71, 142, 49, 98, 196, 165, 103, 206, 177, 79, 158,
146 17, 34, 68, 136, 61, 122, 244, 197, 167, 99, 198, 161, 111, 222, 145,
147 15, 30, 60, 120, 240, 205, 183, 67, 134, 33, 66, 132, 37, 74, 148,
148 5, 10, 20, 40, 80, 160, 109, 218, 153, 31, 62, 124, 248, 221, 151,
149 3, 6, 12, 24, 48, 96, 192, 173, 119, 238, 241, 207, 179, 75, 150,
150 0}};
151
CreateECCBlock(const WideString & codewords,size_t numECWords)152 WideString CreateECCBlock(const WideString& codewords, size_t numECWords) {
153 DCHECK(numECWords > 0);
154
155 const size_t len = codewords.GetLength();
156 static constexpr size_t kFactorTableNum = std::size(FACTORS);
157 size_t table = 0;
158 while (table < kFactorTableNum && FACTORS[table].size() != numECWords) {
159 ++table;
160 }
161
162 if (table >= kFactorTableNum)
163 return WideString();
164
165 auto ecc = FixedSizeDataVector<uint16_t>::Zeroed(numECWords);
166 pdfium::span<uint16_t> ecc_span = ecc.span();
167 for (size_t i = 0; i < len; ++i) {
168 uint16_t m = ecc_span[numECWords - 1] ^ codewords[i];
169 for (int32_t j = numECWords - 1; j > 0; --j) {
170 if (m != 0 && FACTORS[table][j] != 0) {
171 ecc_span[j] = static_cast<uint16_t>(
172 ecc_span[j - 1] ^ ALOG[(LOG[m] + LOG[FACTORS[table][j]]) % 255]);
173 } else {
174 ecc_span[j] = ecc_span[j - 1];
175 }
176 }
177 if (m != 0 && FACTORS[table][0] != 0) {
178 ecc_span[0] =
179 static_cast<uint16_t>(ALOG[(LOG[m] + LOG[FACTORS[table][0]]) % 255]);
180 } else {
181 ecc_span[0] = 0;
182 }
183 }
184 WideString strecc;
185 strecc.Reserve(numECWords);
186 for (size_t i = 0; i < numECWords; ++i)
187 strecc.InsertAtBack(static_cast<wchar_t>(ecc_span[numECWords - i - 1]));
188
189 DCHECK(!strecc.IsEmpty());
190 return strecc;
191 }
192
193 } // namespace
194
EncodeECC200(const WideString & codewords,const CBC_SymbolInfo * symbolInfo)195 WideString CBC_ErrorCorrection::EncodeECC200(const WideString& codewords,
196 const CBC_SymbolInfo* symbolInfo) {
197 if (codewords.GetLength() != symbolInfo->data_capacity())
198 return WideString();
199
200 WideString sb = codewords;
201 size_t blockCount = symbolInfo->GetInterleavedBlockCount();
202 if (blockCount == 1) {
203 WideString ecc = CreateECCBlock(codewords, symbolInfo->error_codewords());
204 if (ecc.IsEmpty())
205 return WideString();
206 sb += ecc;
207 } else {
208 std::vector<size_t> dataSizes(blockCount);
209 std::vector<size_t> errorSizes(blockCount);
210 std::vector<size_t> startPos(blockCount);
211 for (size_t i = 0; i < blockCount; ++i) {
212 dataSizes[i] = symbolInfo->GetDataLengthForInterleavedBlock();
213 errorSizes[i] = symbolInfo->GetErrorLengthForInterleavedBlock();
214 startPos[i] = i > 0 ? startPos[i - 1] + dataSizes[i] : 0;
215 }
216
217 size_t max_error_sizes =
218 *std::max_element(errorSizes.begin(), errorSizes.end()) * blockCount;
219 sb.Reserve(sb.GetLength() + max_error_sizes);
220 for (size_t i = 0; i < max_error_sizes; ++i)
221 sb.InsertAtBack(0);
222
223 for (size_t block = 0; block < blockCount; ++block) {
224 WideString temp;
225 if (symbolInfo->data_capacity() > block)
226 temp.Reserve((symbolInfo->data_capacity() - block / blockCount) + 1);
227 for (size_t d = block; d < symbolInfo->data_capacity(); d += blockCount)
228 temp.InsertAtBack(static_cast<wchar_t>(codewords[d]));
229
230 WideString ecc = CreateECCBlock(temp, errorSizes[block]);
231 if (ecc.IsEmpty())
232 return WideString();
233
234 for (size_t pos = 0, i = block; i < errorSizes[block] * blockCount;
235 ++pos, i += blockCount) {
236 sb.SetAt(symbolInfo->data_capacity() + i, ecc[pos]);
237 }
238 }
239 }
240 DCHECK(!sb.IsEmpty());
241 return sb;
242 }
243