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 2008 ZXing authors
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/qrcode/BC_QRCoderEncoder.h"
24
25 #include <stdint.h>
26
27 #include <algorithm>
28 #include <memory>
29 #include <utility>
30 #include <vector>
31
32 #include "core/fxcrt/data_vector.h"
33 #include "core/fxcrt/fx_string.h"
34 #include "core/fxcrt/span_util.h"
35 #include "fxbarcode/common/BC_CommonByteMatrix.h"
36 #include "fxbarcode/common/reedsolomon/BC_ReedSolomon.h"
37 #include "fxbarcode/common/reedsolomon/BC_ReedSolomonGF256.h"
38 #include "fxbarcode/qrcode/BC_QRCoder.h"
39 #include "fxbarcode/qrcode/BC_QRCoderBitVector.h"
40 #include "fxbarcode/qrcode/BC_QRCoderECBlocks.h"
41 #include "fxbarcode/qrcode/BC_QRCoderMaskUtil.h"
42 #include "fxbarcode/qrcode/BC_QRCoderMatrixUtil.h"
43 #include "fxbarcode/qrcode/BC_QRCoderMode.h"
44 #include "fxbarcode/qrcode/BC_QRCoderVersion.h"
45 #include "third_party/abseil-cpp/absl/types/optional.h"
46 #include "third_party/base/check.h"
47 #include "third_party/base/check_op.h"
48
49 using ModeStringPair = std::pair<CBC_QRCoderMode*, ByteString>;
50
51 namespace {
52
53 CBC_ReedSolomonGF256* g_QRCodeField = nullptr;
54
55 struct QRCoderBlockPair {
56 DataVector<uint8_t> data;
57 DataVector<uint8_t> ecc;
58 };
59
60 // This is a mapping for an ASCII table, starting at an index of 32.
61 const int8_t kAlphaNumericTable[] = {
62 36, -1, -1, -1, 37, 38, -1, -1, -1, -1, 39, 40, -1, 41, 42, 43, // 32-47
63 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 44, -1, -1, -1, -1, -1, // 48-63
64 -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, // 64-79
65 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35};
66
GetAlphaNumericCode(int32_t code)67 int32_t GetAlphaNumericCode(int32_t code) {
68 if (code < 32)
69 return -1;
70 size_t code_index = static_cast<size_t>(code - 32);
71 if (code_index >= std::size(kAlphaNumericTable))
72 return -1;
73 return kAlphaNumericTable[code_index];
74 }
75
AppendNumericBytes(const ByteString & content,CBC_QRCoderBitVector * bits)76 bool AppendNumericBytes(const ByteString& content, CBC_QRCoderBitVector* bits) {
77 size_t length = content.GetLength();
78 size_t i = 0;
79 while (i < length) {
80 int32_t num1 = content[i] - '0';
81 if (i + 2 < length) {
82 int32_t num2 = content[i + 1] - '0';
83 int32_t num3 = content[i + 2] - '0';
84 bits->AppendBits(num1 * 100 + num2 * 10 + num3, 10);
85 i += 3;
86 } else if (i + 1 < length) {
87 int32_t num2 = content[i + 1] - '0';
88 bits->AppendBits(num1 * 10 + num2, 7);
89 i += 2;
90 } else {
91 bits->AppendBits(num1, 4);
92 i++;
93 }
94 }
95 return true;
96 }
97
AppendAlphaNumericBytes(const ByteString & content,CBC_QRCoderBitVector * bits)98 bool AppendAlphaNumericBytes(const ByteString& content,
99 CBC_QRCoderBitVector* bits) {
100 size_t length = content.GetLength();
101 size_t i = 0;
102 while (i < length) {
103 int32_t code1 = GetAlphaNumericCode(content[i]);
104 if (code1 == -1)
105 return false;
106
107 if (i + 1 < length) {
108 int32_t code2 = GetAlphaNumericCode(content[i + 1]);
109 if (code2 == -1)
110 return false;
111
112 bits->AppendBits(code1 * 45 + code2, 11);
113 i += 2;
114 } else {
115 bits->AppendBits(code1, 6);
116 i++;
117 }
118 }
119 return true;
120 }
121
Append8BitBytes(const ByteString & content,CBC_QRCoderBitVector * bits)122 bool Append8BitBytes(const ByteString& content, CBC_QRCoderBitVector* bits) {
123 for (char c : content)
124 bits->AppendBits(c, 8);
125 return true;
126 }
127
AppendModeInfo(CBC_QRCoderMode * mode,CBC_QRCoderBitVector * bits)128 void AppendModeInfo(CBC_QRCoderMode* mode, CBC_QRCoderBitVector* bits) {
129 bits->AppendBits(mode->GetBits(), 4);
130 }
131
AppendLengthInfo(int32_t numLetters,int32_t version,CBC_QRCoderMode * mode,CBC_QRCoderBitVector * bits)132 bool AppendLengthInfo(int32_t numLetters,
133 int32_t version,
134 CBC_QRCoderMode* mode,
135 CBC_QRCoderBitVector* bits) {
136 const auto* qcv = CBC_QRCoderVersion::GetVersionForNumber(version);
137 if (!qcv)
138 return false;
139 int32_t numBits = mode->GetCharacterCountBits(qcv->GetVersionNumber());
140 if (numBits == 0)
141 return false;
142 if (numBits > ((1 << numBits) - 1))
143 return true;
144
145 bits->AppendBits(numLetters, numBits);
146 return true;
147 }
148
AppendBytes(const ByteString & content,CBC_QRCoderMode * mode,CBC_QRCoderBitVector * bits)149 bool AppendBytes(const ByteString& content,
150 CBC_QRCoderMode* mode,
151 CBC_QRCoderBitVector* bits) {
152 if (mode == CBC_QRCoderMode::sNUMERIC)
153 return AppendNumericBytes(content, bits);
154 if (mode == CBC_QRCoderMode::sALPHANUMERIC)
155 return AppendAlphaNumericBytes(content, bits);
156 if (mode == CBC_QRCoderMode::sBYTE)
157 return Append8BitBytes(content, bits);
158 return false;
159 }
160
InitQRCode(int32_t numInputBytes,const CBC_QRCoderErrorCorrectionLevel * ecLevel,CBC_QRCoder * qrCode)161 bool InitQRCode(int32_t numInputBytes,
162 const CBC_QRCoderErrorCorrectionLevel* ecLevel,
163 CBC_QRCoder* qrCode) {
164 qrCode->SetECLevel(ecLevel);
165 for (int32_t i = 1; i <= CBC_QRCoderVersion::kMaxVersion; ++i) {
166 const auto* version = CBC_QRCoderVersion::GetVersionForNumber(i);
167 int32_t numBytes = version->GetTotalCodeWords();
168 const auto* ecBlocks = version->GetECBlocksForLevel(*ecLevel);
169 int32_t numEcBytes = ecBlocks->GetTotalECCodeWords();
170 int32_t numRSBlocks = ecBlocks->GetNumBlocks();
171 int32_t numDataBytes = numBytes - numEcBytes;
172 if (numDataBytes >= numInputBytes + 3) {
173 qrCode->SetVersion(i);
174 qrCode->SetNumTotalBytes(numBytes);
175 qrCode->SetNumDataBytes(numDataBytes);
176 qrCode->SetNumRSBlocks(numRSBlocks);
177 qrCode->SetNumECBytes(numEcBytes);
178 qrCode->SetMatrixWidth(version->GetDimensionForVersion());
179 return true;
180 }
181 }
182 return false;
183 }
184
GenerateECBytes(pdfium::span<const uint8_t> dataBytes,size_t numEcBytesInBlock)185 DataVector<uint8_t> GenerateECBytes(pdfium::span<const uint8_t> dataBytes,
186 size_t numEcBytesInBlock) {
187 // If |numEcBytesInBlock| is 0, the encoder will fail anyway.
188 DCHECK(numEcBytesInBlock > 0);
189 std::vector<int32_t> toEncode(dataBytes.size() + numEcBytesInBlock);
190 std::copy(dataBytes.begin(), dataBytes.end(), toEncode.begin());
191
192 DataVector<uint8_t> ecBytes;
193 CBC_ReedSolomonEncoder encoder(g_QRCodeField);
194 if (encoder.Encode(&toEncode, numEcBytesInBlock)) {
195 ecBytes = DataVector<uint8_t>(toEncode.begin() + dataBytes.size(),
196 toEncode.end());
197 DCHECK_EQ(ecBytes.size(), static_cast<size_t>(numEcBytesInBlock));
198 }
199 return ecBytes;
200 }
201
CalculateMaskPenalty(CBC_CommonByteMatrix * matrix)202 int32_t CalculateMaskPenalty(CBC_CommonByteMatrix* matrix) {
203 return CBC_QRCoderMaskUtil::ApplyMaskPenaltyRule1(matrix) +
204 CBC_QRCoderMaskUtil::ApplyMaskPenaltyRule2(matrix) +
205 CBC_QRCoderMaskUtil::ApplyMaskPenaltyRule3(matrix) +
206 CBC_QRCoderMaskUtil::ApplyMaskPenaltyRule4(matrix);
207 }
208
ChooseMaskPattern(CBC_QRCoderBitVector * bits,const CBC_QRCoderErrorCorrectionLevel * ecLevel,int32_t version,CBC_CommonByteMatrix * matrix)209 absl::optional<int32_t> ChooseMaskPattern(
210 CBC_QRCoderBitVector* bits,
211 const CBC_QRCoderErrorCorrectionLevel* ecLevel,
212 int32_t version,
213 CBC_CommonByteMatrix* matrix) {
214 int32_t minPenalty = 65535;
215 int32_t bestMaskPattern = -1;
216 for (int32_t maskPattern = 0; maskPattern < CBC_QRCoder::kNumMaskPatterns;
217 maskPattern++) {
218 if (!CBC_QRCoderMatrixUtil::BuildMatrix(bits, ecLevel, version, maskPattern,
219 matrix)) {
220 return absl::nullopt;
221 }
222 int32_t penalty = CalculateMaskPenalty(matrix);
223 if (penalty < minPenalty) {
224 minPenalty = penalty;
225 bestMaskPattern = maskPattern;
226 }
227 }
228 return bestMaskPattern;
229 }
230
GetNumDataBytesAndNumECBytesForBlockID(int32_t numTotalBytes,int32_t numDataBytes,int32_t numRSBlocks,int32_t blockID,int32_t * numDataBytesInBlock,int32_t * numECBytesInBlock)231 void GetNumDataBytesAndNumECBytesForBlockID(int32_t numTotalBytes,
232 int32_t numDataBytes,
233 int32_t numRSBlocks,
234 int32_t blockID,
235 int32_t* numDataBytesInBlock,
236 int32_t* numECBytesInBlock) {
237 if (blockID >= numRSBlocks)
238 return;
239
240 int32_t numRsBlocksInGroup2 = numTotalBytes % numRSBlocks;
241 int32_t numRsBlocksInGroup1 = numRSBlocks - numRsBlocksInGroup2;
242 int32_t numTotalBytesInGroup1 = numTotalBytes / numRSBlocks;
243 int32_t numTotalBytesInGroup2 = numTotalBytesInGroup1 + 1;
244 int32_t numDataBytesInGroup1 = numDataBytes / numRSBlocks;
245 int32_t numDataBytesInGroup2 = numDataBytesInGroup1 + 1;
246 int32_t numEcBytesInGroup1 = numTotalBytesInGroup1 - numDataBytesInGroup1;
247 int32_t numEcBytesInGroup2 = numTotalBytesInGroup2 - numDataBytesInGroup2;
248 if (blockID < numRsBlocksInGroup1) {
249 *numDataBytesInBlock = numDataBytesInGroup1;
250 *numECBytesInBlock = numEcBytesInGroup1;
251 } else {
252 *numDataBytesInBlock = numDataBytesInGroup2;
253 *numECBytesInBlock = numEcBytesInGroup2;
254 }
255 }
256
TerminateBits(int32_t numDataBytes,CBC_QRCoderBitVector * bits)257 bool TerminateBits(int32_t numDataBytes, CBC_QRCoderBitVector* bits) {
258 size_t capacity = numDataBytes << 3;
259 if (bits->Size() > capacity)
260 return false;
261
262 for (int32_t i = 0; i < 4 && bits->Size() < capacity; ++i)
263 bits->AppendBit(0);
264
265 int32_t numBitsInLastByte = bits->Size() % 8;
266 if (numBitsInLastByte > 0) {
267 int32_t numPaddingBits = 8 - numBitsInLastByte;
268 for (int32_t j = 0; j < numPaddingBits; ++j)
269 bits->AppendBit(0);
270 }
271
272 if (bits->Size() % 8 != 0)
273 return false;
274
275 int32_t numPaddingBytes = numDataBytes - bits->sizeInBytes();
276 for (int32_t k = 0; k < numPaddingBytes; ++k)
277 bits->AppendBits(k % 2 ? 0x11 : 0xec, 8);
278 return bits->Size() == capacity;
279 }
280
ChooseMode(const ByteString & content)281 CBC_QRCoderMode* ChooseMode(const ByteString& content) {
282 bool hasNumeric = false;
283 bool hasAlphaNumeric = false;
284 for (size_t i = 0; i < content.GetLength(); i++) {
285 if (isdigit(content[i])) {
286 hasNumeric = true;
287 } else if (GetAlphaNumericCode(content[i]) != -1) {
288 hasAlphaNumeric = true;
289 } else {
290 return CBC_QRCoderMode::sBYTE;
291 }
292 }
293 if (hasAlphaNumeric)
294 return CBC_QRCoderMode::sALPHANUMERIC;
295 if (hasNumeric)
296 return CBC_QRCoderMode::sNUMERIC;
297 return CBC_QRCoderMode::sBYTE;
298 }
299
InterleaveWithECBytes(CBC_QRCoderBitVector * bits,int32_t numTotalBytes,int32_t numDataBytes,int32_t numRSBlocks,CBC_QRCoderBitVector * result)300 bool InterleaveWithECBytes(CBC_QRCoderBitVector* bits,
301 int32_t numTotalBytes,
302 int32_t numDataBytes,
303 int32_t numRSBlocks,
304 CBC_QRCoderBitVector* result) {
305 DCHECK(numTotalBytes >= 0);
306 DCHECK(numDataBytes >= 0);
307 if (bits->sizeInBytes() != static_cast<size_t>(numDataBytes))
308 return false;
309
310 int32_t dataBytesOffset = 0;
311 size_t maxNumDataBytes = 0;
312 size_t maxNumEcBytes = 0;
313 std::vector<QRCoderBlockPair> blocks(numRSBlocks);
314 for (int32_t i = 0; i < numRSBlocks; i++) {
315 int32_t numDataBytesInBlock;
316 int32_t numEcBytesInBlock;
317 GetNumDataBytesAndNumECBytesForBlockID(numTotalBytes, numDataBytes,
318 numRSBlocks, i, &numDataBytesInBlock,
319 &numEcBytesInBlock);
320 if (numDataBytesInBlock < 0 || numEcBytesInBlock <= 0)
321 return false;
322
323 DataVector<uint8_t> dataBytes(numDataBytesInBlock);
324 fxcrt::spancpy(
325 pdfium::make_span(dataBytes),
326 bits->GetArray().subspan(dataBytesOffset, numDataBytesInBlock));
327 DataVector<uint8_t> ecBytes = GenerateECBytes(dataBytes, numEcBytesInBlock);
328 if (ecBytes.empty())
329 return false;
330
331 maxNumDataBytes = std::max(maxNumDataBytes, dataBytes.size());
332 maxNumEcBytes = std::max(maxNumEcBytes, ecBytes.size());
333 blocks[i].data = std::move(dataBytes);
334 blocks[i].ecc = std::move(ecBytes);
335 dataBytesOffset += numDataBytesInBlock;
336 }
337 if (numDataBytes != dataBytesOffset)
338 return false;
339
340 for (size_t x = 0; x < maxNumDataBytes; x++) {
341 for (size_t j = 0; j < blocks.size(); j++) {
342 const DataVector<uint8_t>& dataBytes = blocks[j].data;
343 if (x < dataBytes.size())
344 result->AppendBits(dataBytes[x], 8);
345 }
346 }
347 for (size_t y = 0; y < maxNumEcBytes; y++) {
348 for (size_t l = 0; l < blocks.size(); l++) {
349 const DataVector<uint8_t>& ecBytes = blocks[l].ecc;
350 if (y < ecBytes.size())
351 result->AppendBits(ecBytes[y], 8);
352 }
353 }
354 return static_cast<size_t>(numTotalBytes) == result->sizeInBytes();
355 }
356
357 } // namespace
358
359 // static
Initialize()360 void CBC_QRCoderEncoder::Initialize() {
361 g_QRCodeField = new CBC_ReedSolomonGF256(0x011D);
362 g_QRCodeField->Init();
363 }
364
365 // static
Finalize()366 void CBC_QRCoderEncoder::Finalize() {
367 delete g_QRCodeField;
368 g_QRCodeField = nullptr;
369 }
370
371 // static
Encode(WideStringView content,const CBC_QRCoderErrorCorrectionLevel * ecLevel,CBC_QRCoder * qrCode)372 bool CBC_QRCoderEncoder::Encode(WideStringView content,
373 const CBC_QRCoderErrorCorrectionLevel* ecLevel,
374 CBC_QRCoder* qrCode) {
375 ByteString utf8Data = FX_UTF8Encode(content);
376 CBC_QRCoderMode* mode = ChooseMode(utf8Data);
377 CBC_QRCoderBitVector dataBits;
378 if (!AppendBytes(utf8Data, mode, &dataBits))
379 return false;
380 int32_t numInputBytes = dataBits.sizeInBytes();
381 if (!InitQRCode(numInputBytes, ecLevel, qrCode))
382 return false;
383 CBC_QRCoderBitVector headerAndDataBits;
384 AppendModeInfo(mode, &headerAndDataBits);
385 int32_t numLetters = mode == CBC_QRCoderMode::sBYTE ? dataBits.sizeInBytes()
386 : content.GetLength();
387 if (!AppendLengthInfo(numLetters, qrCode->GetVersion(), mode,
388 &headerAndDataBits)) {
389 return false;
390 }
391 headerAndDataBits.AppendBitVector(&dataBits);
392 if (!TerminateBits(qrCode->GetNumDataBytes(), &headerAndDataBits))
393 return false;
394 CBC_QRCoderBitVector finalBits;
395 if (!InterleaveWithECBytes(&headerAndDataBits, qrCode->GetNumTotalBytes(),
396 qrCode->GetNumDataBytes(),
397 qrCode->GetNumRSBlocks(), &finalBits)) {
398 return false;
399 }
400
401 auto matrix = std::make_unique<CBC_CommonByteMatrix>(
402 qrCode->GetMatrixWidth(), qrCode->GetMatrixWidth());
403 absl::optional<int32_t> maskPattern = ChooseMaskPattern(
404 &finalBits, qrCode->GetECLevel(), qrCode->GetVersion(), matrix.get());
405 if (!maskPattern.has_value())
406 return false;
407
408 qrCode->SetMaskPattern(maskPattern.value());
409 if (!CBC_QRCoderMatrixUtil::BuildMatrix(
410 &finalBits, qrCode->GetECLevel(), qrCode->GetVersion(),
411 qrCode->GetMaskPattern(), matrix.get())) {
412 return false;
413 }
414
415 qrCode->SetMatrix(std::move(matrix));
416 return qrCode->IsValid();
417 }
418