1 // Copyright 2014 PDFium Authors. All rights reserved. 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/common/BC_CommonByteMatrix.h" 24 #include "fxbarcode/qrcode/BC_QRCoder.h" 25 #include "fxbarcode/qrcode/BC_QRCoderBitVector.h" 26 #include "fxbarcode/qrcode/BC_QRCoderErrorCorrectionLevel.h" 27 #include "fxbarcode/qrcode/BC_QRCoderMaskUtil.h" 28 #include "fxbarcode/qrcode/BC_QRCoderMatrixUtil.h" 29 #include "fxbarcode/utils.h" 30 31 const int32_t CBC_QRCoderMatrixUtil::POSITION_DETECTION_PATTERN[7][7] = { 32 {1, 1, 1, 1, 1, 1, 1}, {1, 0, 0, 0, 0, 0, 1}, {1, 0, 1, 1, 1, 0, 1}, 33 {1, 0, 1, 1, 1, 0, 1}, {1, 0, 1, 1, 1, 0, 1}, {1, 0, 0, 0, 0, 0, 1}, 34 {1, 1, 1, 1, 1, 1, 1}}; 35 const int32_t CBC_QRCoderMatrixUtil::HORIZONTAL_SEPARATION_PATTERN[1][8] = { 36 {0, 0, 0, 0, 0, 0, 0, 0}}; 37 const int32_t CBC_QRCoderMatrixUtil::VERTICAL_SEPARATION_PATTERN[7][1] = { 38 {0}, {0}, {0}, {0}, {0}, {0}, {0}}; 39 const int32_t CBC_QRCoderMatrixUtil::POSITION_ADJUSTMENT_PATTERN[5][5] = { 40 {1, 1, 1, 1, 1}, 41 {1, 0, 0, 0, 1}, 42 {1, 0, 1, 0, 1}, 43 {1, 0, 0, 0, 1}, 44 {1, 1, 1, 1, 1}}; 45 const int32_t 46 CBC_QRCoderMatrixUtil::POSITION_ADJUSTMENT_PATTERN_COORDINATE_TABLE[40][7] = 47 // NOLINTNEXTLINE 48 { 49 {-1, -1, -1, -1, -1, -1, -1}, {6, 18, -1, -1, -1, -1, -1}, 50 {6, 22, -1, -1, -1, -1, -1}, {6, 26, -1, -1, -1, -1, -1}, 51 {6, 30, -1, -1, -1, -1, -1}, {6, 34, -1, -1, -1, -1, -1}, 52 {6, 22, 38, -1, -1, -1, -1}, {6, 24, 42, -1, -1, -1, -1}, 53 {6, 26, 46, -1, -1, -1, -1}, {6, 28, 50, -1, -1, -1, -1}, 54 {6, 30, 54, -1, -1, -1, -1}, {6, 32, 58, -1, -1, -1, -1}, 55 {6, 34, 62, -1, -1, -1, -1}, {6, 26, 46, 66, -1, -1, -1}, 56 {6, 26, 48, 70, -1, -1, -1}, {6, 26, 50, 74, -1, -1, -1}, 57 {6, 30, 54, 78, -1, -1, -1}, {6, 30, 56, 82, -1, -1, -1}, 58 {6, 30, 58, 86, -1, -1, -1}, {6, 34, 62, 90, -1, -1, -1}, 59 {6, 28, 50, 72, 94, -1, -1}, {6, 26, 50, 74, 98, -1, -1}, 60 {6, 30, 54, 78, 102, -1, -1}, {6, 28, 54, 80, 106, -1, -1}, 61 {6, 32, 58, 84, 110, -1, -1}, {6, 30, 58, 86, 114, -1, -1}, 62 {6, 34, 62, 90, 118, -1, -1}, {6, 26, 50, 74, 98, 122, -1}, 63 {6, 30, 54, 78, 102, 126, -1}, {6, 26, 52, 78, 104, 130, -1}, 64 {6, 30, 56, 82, 108, 134, -1}, {6, 34, 60, 86, 112, 138, -1}, 65 {6, 30, 58, 86, 114, 142, -1}, {6, 34, 62, 90, 118, 146, -1}, 66 {6, 30, 54, 78, 102, 126, 150}, {6, 24, 50, 76, 102, 128, 154}, 67 {6, 28, 54, 80, 106, 132, 158}, {6, 32, 58, 84, 110, 136, 162}, 68 {6, 26, 54, 82, 110, 138, 166}, {6, 30, 58, 86, 114, 142, 170}, 69 }; 70 const int32_t CBC_QRCoderMatrixUtil::TYPE_INFO_COORDINATES[15][2] = { 71 {8, 0}, {8, 1}, {8, 2}, {8, 3}, {8, 4}, {8, 5}, {8, 7}, {8, 8}, 72 {7, 8}, {5, 8}, {4, 8}, {3, 8}, {2, 8}, {1, 8}, {0, 8}, 73 }; 74 const int32_t CBC_QRCoderMatrixUtil::VERSION_INFO_POLY = 0x1f25; 75 const int32_t CBC_QRCoderMatrixUtil::TYPE_INFO_POLY = 0x0537; 76 const int32_t CBC_QRCoderMatrixUtil::TYPE_INFO_MASK_PATTERN = 0x5412; 77 78 void CBC_QRCoderMatrixUtil::ClearMatrix(CBC_CommonByteMatrix* matrix, 79 int32_t& e) { 80 if (!matrix) { 81 e = BCExceptionNullPointer; 82 return; 83 } 84 matrix->clear((uint8_t)-1); 85 } 86 void CBC_QRCoderMatrixUtil::BuildMatrix( 87 CBC_QRCoderBitVector* dataBits, 88 const CBC_QRCoderErrorCorrectionLevel* ecLevel, 89 int32_t version, 90 int32_t maskPattern, 91 CBC_CommonByteMatrix* matrix, 92 int32_t& e) { 93 if (!matrix) { 94 e = BCExceptionNullPointer; 95 return; 96 } 97 ClearMatrix(matrix, e); 98 if (e != BCExceptionNO) 99 return; 100 EmbedBasicPatterns(version, matrix, e); 101 if (e != BCExceptionNO) 102 return; 103 EmbedTypeInfo(ecLevel, maskPattern, matrix, e); 104 if (e != BCExceptionNO) 105 return; 106 MaybeEmbedVersionInfo(version, matrix, e); 107 if (e != BCExceptionNO) 108 return; 109 EmbedDataBits(dataBits, maskPattern, matrix, e); 110 if (e != BCExceptionNO) 111 return; 112 } 113 void CBC_QRCoderMatrixUtil::EmbedBasicPatterns(int32_t version, 114 CBC_CommonByteMatrix* matrix, 115 int32_t& e) { 116 if (!matrix) { 117 e = BCExceptionNullPointer; 118 return; 119 } 120 EmbedPositionDetectionPatternsAndSeparators(matrix, e); 121 if (e != BCExceptionNO) 122 return; 123 EmbedDarkDotAtLeftBottomCorner(matrix, e); 124 if (e != BCExceptionNO) 125 return; 126 MaybeEmbedPositionAdjustmentPatterns(version, matrix, e); 127 if (e != BCExceptionNO) 128 return; 129 EmbedTimingPatterns(matrix, e); 130 if (e != BCExceptionNO) 131 return; 132 } 133 134 void CBC_QRCoderMatrixUtil::EmbedTypeInfo( 135 const CBC_QRCoderErrorCorrectionLevel* ecLevel, 136 int32_t maskPattern, 137 CBC_CommonByteMatrix* matrix, 138 int32_t& e) { 139 if (!matrix) { 140 e = BCExceptionNullPointer; 141 return; 142 } 143 CBC_QRCoderBitVector typeInfoBits; 144 MakeTypeInfoBits(ecLevel, maskPattern, &typeInfoBits, e); 145 if (e != BCExceptionNO) 146 return; 147 148 for (size_t i = 0; i < typeInfoBits.Size(); i++) { 149 int32_t bit = typeInfoBits.At(typeInfoBits.Size() - 1 - i, e); 150 if (e != BCExceptionNO) 151 return; 152 int32_t x1 = TYPE_INFO_COORDINATES[i][0]; 153 int32_t y1 = TYPE_INFO_COORDINATES[i][1]; 154 matrix->Set(x1, y1, bit); 155 if (i < 8) { 156 int32_t x2 = matrix->GetWidth() - i - 1; 157 int32_t y2 = 8; 158 matrix->Set(x2, y2, bit); 159 } else { 160 int32_t x2 = 8; 161 int32_t y2 = matrix->GetHeight() - 7 + (i - 8); 162 matrix->Set(x2, y2, bit); 163 } 164 } 165 } 166 167 void CBC_QRCoderMatrixUtil::MaybeEmbedVersionInfo(int32_t version, 168 CBC_CommonByteMatrix* matrix, 169 int32_t& e) { 170 if (!matrix) { 171 e = BCExceptionNullPointer; 172 return; 173 } 174 if (version < 7) { 175 return; 176 } 177 CBC_QRCoderBitVector versionInfoBits; 178 MakeVersionInfoBits(version, &versionInfoBits, e); 179 if (e != BCExceptionNO) 180 return; 181 int32_t bitIndex = 6 * 3 - 1; 182 for (int32_t i = 0; i < 6; i++) { 183 for (int32_t j = 0; j < 3; j++) { 184 int32_t bit = versionInfoBits.At(bitIndex, e); 185 if (e != BCExceptionNO) 186 return; 187 bitIndex--; 188 matrix->Set(i, matrix->GetHeight() - 11 + j, bit); 189 matrix->Set(matrix->GetHeight() - 11 + j, i, bit); 190 } 191 } 192 } 193 void CBC_QRCoderMatrixUtil::EmbedDataBits(CBC_QRCoderBitVector* dataBits, 194 int32_t maskPattern, 195 CBC_CommonByteMatrix* matrix, 196 int32_t& e) { 197 if (!matrix || !dataBits) { 198 e = BCExceptionNullPointer; 199 return; 200 } 201 size_t bitIndex = 0; 202 int32_t direction = -1; 203 int32_t x = matrix->GetWidth() - 1; 204 int32_t y = matrix->GetHeight() - 1; 205 while (x > 0) { 206 if (x == 6) { 207 x -= 1; 208 } 209 while (y >= 0 && y < matrix->GetHeight()) { 210 if (y == 6) { 211 y += direction; 212 continue; 213 } 214 for (int32_t i = 0; i < 2; i++) { 215 int32_t xx = x - i; 216 if (!IsEmpty(matrix->Get(xx, y))) { 217 continue; 218 } 219 int32_t bit; 220 if (bitIndex < dataBits->Size()) { 221 bit = dataBits->At(bitIndex, e); 222 if (e != BCExceptionNO) 223 return; 224 bitIndex++; 225 } else { 226 bit = 0; 227 } 228 if (maskPattern != -1) { 229 bool bol = CBC_QRCoderMaskUtil::GetDataMaskBit(maskPattern, xx, y, e); 230 if (e != BCExceptionNO) 231 return; 232 if (bol) { 233 bit ^= 0x01; 234 } 235 } 236 matrix->Set(xx, y, bit); 237 } 238 y += direction; 239 } 240 direction = -direction; 241 y += direction; 242 x -= 2; 243 } 244 if (bitIndex != dataBits->Size()) { 245 return; 246 } 247 } 248 int32_t CBC_QRCoderMatrixUtil::CalculateBCHCode(int32_t value, int32_t poly) { 249 int32_t msbSetInPoly = FindMSBSet(poly); 250 value <<= msbSetInPoly - 1; 251 while (FindMSBSet(value) >= msbSetInPoly) { 252 value ^= poly << (FindMSBSet(value) - msbSetInPoly); 253 } 254 return value; 255 } 256 void CBC_QRCoderMatrixUtil::MakeTypeInfoBits( 257 const CBC_QRCoderErrorCorrectionLevel* ecLevel, 258 int32_t maskPattern, 259 CBC_QRCoderBitVector* bits, 260 int32_t& e) { 261 if (!bits) { 262 e = BCExceptionNullPointer; 263 return; 264 } 265 if (!CBC_QRCoder::IsValidMaskPattern(maskPattern)) { 266 e = BCExceptionBadMask; 267 return; 268 } 269 int32_t typeInfo = (ecLevel->GetBits() << 3) | maskPattern; 270 bits->AppendBits(typeInfo, 5); 271 int32_t bchCode = CalculateBCHCode(typeInfo, TYPE_INFO_POLY); 272 bits->AppendBits(bchCode, 10); 273 CBC_QRCoderBitVector maskBits; 274 maskBits.AppendBits(TYPE_INFO_MASK_PATTERN, 15); 275 if (!bits->XOR(&maskBits)) { 276 e = BCExceptionGeneric; 277 return; 278 } 279 ASSERT(bits->Size() == 15); 280 } 281 282 void CBC_QRCoderMatrixUtil::MakeVersionInfoBits(int32_t version, 283 CBC_QRCoderBitVector* bits, 284 int32_t& e) { 285 if (!bits) { 286 e = BCExceptionNullPointer; 287 return; 288 } 289 290 bits->AppendBits(version, 6); 291 int32_t bchCode = CalculateBCHCode(version, VERSION_INFO_POLY); 292 bits->AppendBits(bchCode, 12); 293 ASSERT(bits->Size() == 18); 294 } 295 296 bool CBC_QRCoderMatrixUtil::IsEmpty(int32_t value) { 297 return (uint8_t)value == 0xff; 298 } 299 bool CBC_QRCoderMatrixUtil::IsValidValue(int32_t value) { 300 return ((uint8_t)value == 0xff || (uint8_t)value == 0x00 || 301 (uint8_t)value == 0x01); 302 } 303 304 void CBC_QRCoderMatrixUtil::EmbedTimingPatterns(CBC_CommonByteMatrix* matrix, 305 int32_t& e) { 306 if (!matrix) { 307 e = BCExceptionNullPointer; 308 return; 309 } 310 for (int32_t i = 8; i < matrix->GetWidth() - 8; i++) { 311 int32_t bit = (i + 1) % 2; 312 if (!IsValidValue(matrix->Get(i, 6))) { 313 e = BCExceptionInvalidateImageData; 314 return; 315 } 316 if (IsEmpty(matrix->Get(i, 6))) { 317 matrix->Set(i, 6, bit); 318 } 319 if (!IsValidValue(matrix->Get(6, i))) { 320 e = BCExceptionInvalidateImageData; 321 return; 322 } 323 if (IsEmpty(matrix->Get(6, i))) { 324 matrix->Set(6, i, bit); 325 } 326 } 327 } 328 void CBC_QRCoderMatrixUtil::EmbedDarkDotAtLeftBottomCorner( 329 CBC_CommonByteMatrix* matrix, 330 int32_t& e) { 331 if (!matrix) { 332 e = BCExceptionNullPointer; 333 return; 334 } 335 if (matrix->Get(8, matrix->GetHeight() - 8) == 0) { 336 e = BCExceptionHeight_8BeZero; 337 return; 338 } 339 matrix->Set(8, matrix->GetHeight() - 8, 1); 340 } 341 void CBC_QRCoderMatrixUtil::EmbedHorizontalSeparationPattern( 342 int32_t xStart, 343 int32_t yStart, 344 CBC_CommonByteMatrix* matrix, 345 int32_t& e) { 346 if (!matrix) { 347 e = BCExceptionNullPointer; 348 return; 349 } 350 for (int32_t x = 0; x < 8; x++) { 351 if (!IsEmpty(matrix->Get(xStart + x, yStart))) { 352 e = BCExceptionInvalidateData; 353 return; 354 } 355 matrix->Set(xStart + x, yStart, HORIZONTAL_SEPARATION_PATTERN[0][x]); 356 } 357 } 358 void CBC_QRCoderMatrixUtil::EmbedVerticalSeparationPattern( 359 int32_t xStart, 360 int32_t yStart, 361 CBC_CommonByteMatrix* matrix, 362 int32_t& e) { 363 if (!matrix) { 364 e = BCExceptionNullPointer; 365 return; 366 } 367 for (int32_t y = 0; y < 7; y++) { 368 if (!IsEmpty(matrix->Get(xStart, yStart + y))) { 369 e = BCExceptionInvalidateData; 370 return; 371 } 372 matrix->Set(xStart, yStart + y, VERTICAL_SEPARATION_PATTERN[y][0]); 373 } 374 } 375 void CBC_QRCoderMatrixUtil::EmbedPositionAdjustmentPattern( 376 int32_t xStart, 377 int32_t yStart, 378 CBC_CommonByteMatrix* matrix, 379 int32_t& e) { 380 if (!matrix) { 381 e = BCExceptionNullPointer; 382 if (e != BCExceptionNO) 383 return; 384 } 385 for (int32_t y = 0; y < 5; y++) { 386 for (int32_t x = 0; x < 5; x++) { 387 if (!IsEmpty(matrix->Get(xStart + x, y + yStart))) { 388 e = BCExceptionInvalidateData; 389 return; 390 } 391 matrix->Set(xStart + x, yStart + y, POSITION_ADJUSTMENT_PATTERN[y][x]); 392 } 393 } 394 } 395 void CBC_QRCoderMatrixUtil::EmbedPositionDetectionPattern( 396 int32_t xStart, 397 int32_t yStart, 398 CBC_CommonByteMatrix* matrix, 399 int32_t& e) { 400 if (!matrix) { 401 e = BCExceptionNullPointer; 402 return; 403 } 404 for (int32_t y = 0; y < 7; y++) { 405 for (int32_t x = 0; x < 7; x++) { 406 if (!IsEmpty(matrix->Get(xStart + x, yStart + y))) { 407 e = BCExceptionInvalidateData; 408 return; 409 } 410 matrix->Set(xStart + x, yStart + y, POSITION_DETECTION_PATTERN[y][x]); 411 } 412 } 413 } 414 void CBC_QRCoderMatrixUtil::EmbedPositionDetectionPatternsAndSeparators( 415 CBC_CommonByteMatrix* matrix, 416 int32_t& e) { 417 if (!matrix) { 418 e = BCExceptionNullPointer; 419 return; 420 } 421 int32_t pdpWidth = 7; 422 EmbedPositionDetectionPattern(0, 0, matrix, e); 423 if (e != BCExceptionNO) 424 return; 425 EmbedPositionDetectionPattern(matrix->GetWidth() - pdpWidth, 0, matrix, e); 426 if (e != BCExceptionNO) 427 return; 428 EmbedPositionDetectionPattern(0, matrix->GetWidth() - pdpWidth, matrix, e); 429 if (e != BCExceptionNO) 430 return; 431 int32_t hspWidth = 8; 432 EmbedHorizontalSeparationPattern(0, hspWidth - 1, matrix, e); 433 if (e != BCExceptionNO) 434 return; 435 EmbedHorizontalSeparationPattern(matrix->GetWidth() - hspWidth, hspWidth - 1, 436 matrix, e); 437 if (e != BCExceptionNO) 438 return; 439 EmbedHorizontalSeparationPattern(0, matrix->GetWidth() - hspWidth, matrix, e); 440 if (e != BCExceptionNO) 441 return; 442 int32_t vspSize = 7; 443 EmbedVerticalSeparationPattern(vspSize, 0, matrix, e); 444 if (e != BCExceptionNO) 445 return; 446 EmbedVerticalSeparationPattern(matrix->GetHeight() - vspSize - 1, 0, matrix, 447 e); 448 if (e != BCExceptionNO) 449 return; 450 EmbedVerticalSeparationPattern(vspSize, matrix->GetHeight() - vspSize, matrix, 451 e); 452 if (e != BCExceptionNO) 453 return; 454 } 455 void CBC_QRCoderMatrixUtil::MaybeEmbedPositionAdjustmentPatterns( 456 int32_t version, 457 CBC_CommonByteMatrix* matrix, 458 int32_t& e) { 459 if (!matrix) { 460 e = BCExceptionNullPointer; 461 return; 462 } 463 if (version < 2) { 464 return; 465 } 466 int32_t index = version - 1; 467 int32_t const* coordinates = 468 &(POSITION_ADJUSTMENT_PATTERN_COORDINATE_TABLE[index][0]); 469 int32_t numCoordinate = 7; 470 for (int32_t i = 0; i < numCoordinate; i++) { 471 for (int32_t j = 0; j < numCoordinate; j++) { 472 int32_t y = coordinates[i]; 473 int32_t x = coordinates[j]; 474 if (x == -1 || y == -1) { 475 continue; 476 } 477 if (IsEmpty(matrix->Get(x, y))) { 478 EmbedPositionAdjustmentPattern(x - 2, y - 2, matrix, e); 479 if (e != BCExceptionNO) 480 return; 481 } 482 } 483 } 484 } 485 int32_t CBC_QRCoderMatrixUtil::FindMSBSet(int32_t value) { 486 int32_t numDigits = 0; 487 while (value != 0) { 488 value >>= 1; 489 ++numDigits; 490 } 491 return numDigits; 492 } 493 CBC_QRCoderMatrixUtil::CBC_QRCoderMatrixUtil() {} 494 CBC_QRCoderMatrixUtil::~CBC_QRCoderMatrixUtil() {} 495
