讲一讲一维码、二维码的生成原理，长文预警！

一维码

barcode 白皮书：https://www.barcodefaq.com/1d/code-128/

一维码即条形码，由多个黑白条纹组成，基本原理就是通过二进制表示各个 ASCII 字符，以最常见最通用的 code128-B 码制为例（code128 可以表示全部的128个 ASCII 字符）

UPC 码制是国际商品条码标准，这里不讨论商品码生成的规则，下文的条形码示例用微信、支付宝的扫码工具无法识别（微信、支付宝识别的是 UPC 码，用于查询商品信息），可以用钉钉扫码测试。

条形码中，黑看做1，白看做0，code128-B 条形码的规律如下：

  • 由四部分构成，开始符、数据区、校验符、结束符
  • 开始符固定为：11010010000
  • 结束符固定为：1100011101011
  • 校验符计算规则：(104 + (字符在字符串中的索引值 * 字符在 code128 表中的索引)) % 103

以 “biz” 这个字符为例，

b i z
字符中的索引 1 2 3
code128 表中的索引 66 73 90
和 66 146 237

则校验符的索引为：(104 + (66 * 1) + (73 * 2) + (90 * 3)) % 103 = 71

码值对应表：https://zh.wikipedia.org/wiki/Code128

示意图如下：条形码.png

伪代码呼之欲出：

function barcodeEncode(value) {
    // code 128 共有 107 个字符，具体列表可查看 https://zh.wikipedia.org/wiki/Code128
  const BARS = [
    11011001100, 11001101100, 11001100110, 10010011000, 10010001100,
    10001001100, 10011001000, 10011000100, 10001100100, 11001001000,
    11001000100, 11000100100, 10110011100, 10011011100, 10011001110,
    10111001100, 10011101100, 10011100110, 11001110010, 11001011100,
    11001001110, 11011100100, 11001110100, 11101101110, 11101001100,
    11100101100, 11100100110, 11101100100, 11100110100, 11100110010,
    11011011000, 11011000110, 11000110110, 10100011000, 10001011000,
    10001000110, 10110001000, 10001101000, 10001100010, 11010001000,
    11000101000, 11000100010, 10110111000, 10110001110, 10001101110,
    10111011000, 10111000110, 10001110110, 11101110110, 11010001110,
    11000101110, 11011101000, 11011100010, 11011101110, 11101011000,
    11101000110, 11100010110, 11101101000, 11101100010, 11100011010,
    11101111010, 11001000010, 11110001010, 10100110000, 10100001100,
    10010110000, 10010000110, 10000101100, 10000100110, 10110010000,
    10110000100, 10011010000, 10011000010, 10000110100, 10000110010,
    11000010010, 11001010000, 11110111010, 11000010100, 10001111010,
    10100111100, 10010111100, 10010011110, 10111100100, 10011110100,
    10011110010, 11110100100, 11110010100, 11110010010, 11011011110,
    11011110110, 11110110110, 10101111000, 10100011110, 10001011110,
    10111101000, 10111100010, 11110101000, 11110100010, 10111011110,
    10111101110, 11101011110, 11110101110, 11010000100, 11010010000,
    11010011100, 1100011101011,
  ]

  const startCharIndex = 104;
  const endCharIndex = 106;

  // 校验符初始值为开始索引
  let checksum = startCharIndex;

  const result = [BARS[startCharIndex]];

  value.split('').forEach((char, index) => {
      const ascii = char.charCodeAt(0);
    const barIndex = ascii - 32; // ascii 字符序号与 code128-b 序号的差固定为 32

    // 每一位在 BARS 中的索引乘以字符串中的索引
    checksum += barIndex * (index + 1)

    result.push(BARS[barIndex]);
  });

  result.push(BARS[checksum % 103]);
  result.push(BARS[endCharIndex]);

  return result;
}

barcodeEncode('1234567890') // -> [11010010000, 10011100110, 11001110010, 11001011100, 11001001110, 11011100100, 11001110100, 11101101110, 11101001100, 11100101100, 10011101100, 10100011000, 1100011101011]

得到二进制的列表后，即可将 0 或 1 按顺序绘制，伪代码如下：

<!DOCTYPE html>
<html lang="en">
<body>
  <canvas id="barcode" />

  <script>
    function drawBarcode(canvasEl, barList) {
        const ctx = canvasEl.getContext('2d');
      const barJoinStr = barList.join('');

      function drawOneBar(type, index) {
          const bgColor = type === '0' ? '#ffffff' : '#000000';
        ctx.fillStyle = bgColor;
        ctx.fillRect(index * 2, 0, 2, 100)
      }

      barJoinStr.split('').forEach((char, index) => {
          drawOneBar(char, index)
      })
    }

    drawBarcode(document.querySelector('#barcode'), barcodeEncode('1234567890'))
  </script>
</body>
</html>

得到结果如下：image.png

DEMO 地址：https://codesandbox.io/s/javascript-forked-o8sfn

PS：以上代码未考虑任何边界情况，如字符合法性的判断、码制的自动选择等，请勿用于生产环境

一维码由条纹构成，所以污损上下一部分后并不影响识别。但是也正因为这个问题，如果有一个条纹被遮挡，整个条形码都无法识别，而且垂直方向的空间被浪费，能表示的信息极为的少

接下来我们看二维码

二维码

qrcode 白皮书：https://www.swisseduc.ch/informatik/theoretische_informatik/qr_codes/docs/qr_standard.pdf

二维码同样区分各种码制，目前最常用的就是 qrcode，quick response code，快速响应矩阵，我们同样从最常用的码制出发，分析二维码的生成原理

基本术语

  • 版本：可以简单理解为二维码尺寸
    • 最小版本1，尺寸为21*21
    • 最大版本40，尺寸为177*177
    • 版本号每加一，尺寸多四格

不同尺寸能够容纳的字符根据容错等级和编码模式确定，容量表如下：

版本 容错等级 数字模式 字母数字模式 字节模式 汉字模式
1 L 41 25 17 10
M 34 20 14 8
Q 27 16 11 7
H 17 10 7 4
2 L 77 47 32 20
M 63 38 26 16
Q 48 29 20 12
H 34 20 14 8
3 L 127 77 53 32
M 101 61 42 26
Q 77 47 32 20
H 58 35 24 15
4 L 187 114 78 48
M 149 90 62 38
Q 111 67 46 28
H 82 50 34 21
5 L 255 154 106 65
M 202 122 84 52
Q 144 87 60 37
H 106 64 44 27
6 L 322 195 134 82
M 255 154 106 65
Q 178 108 74 45
H 139 84 58 36
7 L 370 224 154 95
M 293 178 122 75
Q 207 125 86 53
H 154 93 64 39
8 L 461 279 192 118
M 365 221 152 93
Q 259 157 108 66
H 202 122 84 52
9 L 552 335 230 141
M 432 262 180 111
Q 312 189 130 80
H 235 143 98 60
10 L 652 395 271 167
M 513 311 213 131
Q 364 221 151 93
H 288 174 119 74
11 L 772 468 321 198
M 604 366 251 155
Q 427 259 177 109
H 331 200 137 85
12 L 883 535 367 226
M 691 419 287 177
Q 489 296 203 125
H 374 227 155 96
13 L 1022 619 425 262
M 796 483 331 204
Q 580 352 241 149
H 427 259 177 109
14 L 1101 667 458 282
M 871 528 362 223
Q 621 376 258 159
H 468 283 194 120
15 L 1250 758 520 320
M 991 600 412 254
Q 703 426 292 180
H 530 321 220 136
16 L 1408 854 586 361
M 1082 656 450 277
Q 775 470 322 198
H 602 365 250 154
17 L 1548 938 644 397
M 1212 734 504 310
Q 876 531 364 224
H 674 408 280 173
18 L 1725 1046 718 442
M 1346 816 560 345
Q 948 574 394 243
H 746 452 310 191
19 L 1903 1153 792 488
M 1500 909 624 384
Q 1063 644 442 272
H 813 493 338 208
20 L 2061 1249 858 528
M 1600 970 666 410
Q 1159 702 482 297
H 919 557 382 235
21 L 2232 1352 929 572
M 1708 1035 711 438
Q 1224 742 509 314
H 969 587 403 248
22 L 2409 1460 1003 618
M 1872 1134 779 480
Q 1358 823 565 348
H 1056 640 439 270
23 L 2620 1588 1091 672
M 2059 1248 857 528
Q 1468 890 611 376
H 1108 672 461 284
24 L 2812 1704 1171 721
M 2188 1326 911 561
Q 1588 963 661 407
H 1228 744 511 315
25 L 3057 1853 1273 784
M 2395 1451 997 614
Q 1718 1041 715 440
H 1286 779 535 330
26 L 3283 1990 1367 842
M 2544 1542 1059 652
Q 1804 1094 751 462
H 1425 864 593 365
27 L 3517 2132 1465 902
M 2701 1637 1125 692
Q 1933 1172 805 496
H 1501 910 625 385
28 L 3669 2223 1528 940
M 2857 1732 1190 732
Q 2085 1263 868 534
H 1581 958 658 405
29 L 3909 2369 1628 1002
M 3035 1839 1264 778
Q 2181 1322 908 559
H 1677 1016 698 430
30 L 4158 2520 1732 1066
M 3289 1994 1370 843
Q 2358 1429 982 604
H 1782 1080 742 457
31 L 4417 2677 1840 1132
M 3486 2113 1452 894
Q 2473 1499 1030 634
H 1897 1150 790 486
32 L 4686 2840 1952 1201
M 3693 2238 1538 947
Q 2670 1618 1112 684
H 2022 1226 842 518
33 L 4965 3009 2068 1273
M 3909 2369 1628 1002
Q 2805 1700 1168 719
H 2157 1307 898 553
34 L 5253 3183 2188 1347
M 4134 2506 1722 1060
Q 2949 1787 1228 756
H 2301 1394 958 590
35 L 5529 3351 2303 1417
M 4343 2632 1809 1113
Q 3081 1867 1283 790
H 2361 1431 983 605
36 L 5836 3537 2431 1496
M 4588 2780 1911 1176
Q 3244 1966 1351 832
H 2524 1530 1051 647
37 L 6153 3729 2563 1577
M 4775 2894 1989 1224
Q 3417 2071 1423 876
H 2625 1591 1093 673
38 L 6479 3927 2699 1661
M 5039 3054 2099 1292
Q 3599 2181 1499 923
H 2735 1658 1139 701
39 L 6743 4087 2809 1729
M 5313 3220 2213 1362
Q 3791 2298 1579 972
H 2927 1774 1219 750
40 L 7089 4296 2953 1817
M 5596 3391 2331 1435
Q 3993 2420 1663 1024
H 3057 1852 1273 784
  • 容错等级：二维码有极大的容错能力，根据可污损面积，有不同的容错等级
容错等级 可污损面积
L 7%
M 15%
Q 25%
H 30%

  • 掩码模式：共八种，根据特定规则更改方块的颜色（黑改白 or 白改黑），便于扫码器识别

  • 纠错算法：核心是里德-所罗门码，经过计算后的字符串，即使丢失某些字符，依旧可以计算出整个字符的原始值

基本构成

二维码各个区域分为功能区和数据区，先看下二维码图案的基本构成：

二维码基本构成.png

二维码版本号大于7，即尺寸大于45*45后，需增加版本信息加快识别速度，如下：

二维码 45*45.png

定位区

7*7 的回字形图案，分布在左上、右上、左下定位区.png

分隔区

围绕定位区的图案，白色

时序信息

两条从第七列或第七排开始，黑白交替，黑色开始，黑色结束的图案，用于告知扫码器识别的顺序

矫正区

5*5 的回字形图案，用于扫码器加快定位速度

矫正区.png

版本号大于等于2，需要增加矫正区，版本号越多矫正区越多，各个版本号对应的矫正区中心点坐标如下：

版本 中心点坐标 左上为 (0,0)
2 6 18
3 6 22
4 6 26
5 6 30
6 6 34
7 6 22 38
8 6 24 42
9 6 26 46
10 6 28 50
11 6 30 54
12 6 32 58
13 6 34 62
14 6 26 46 66
15 6 26 48 70
16 6 26 50 74
17 6 30 54 78
18 6 30 56 82
19 6 30 58 86
20 6 34 62 90
21 6 28 50 72 94
22 6 26 50 74 98
23 6 30 54 78 102
24 6 28 54 80 106
25 6 32 58 84 110
26 6 30 58 86 114
27 6 34 62 90 118
28 6 26 50 74 98 122
29 6 30 54 78 102 126
30 6 26 52 78 104 130
31 6 30 56 82 108 134
32 6 34 60 86 112 138
33 6 30 58 86 114 142
34 6 34 62 90 118 146
35 6 30 54 78 102 126 150
36 6 24 50 76 102 128 154
37 6 28 54 80 106 132 158
38 6 32 58 84 110 136 162
39 6 26 54 82 110 138 166
40 6 30 58 86 114 142 170

以版本号7为例，中心点坐标为 6 | 22 | 38，则需要 (6,6) (6,22) (6,38) (22,6) (22,22) (22,38) (38,6) (38,22) (38,38) 共九个矫正区，但实际绘制时，如果和定位区重叠，则不绘制此矫正区，如下：编组 8.png

格式信息

用于记录容错等级、掩码模式，并且通过纠错算法编码后得到长度为15的二进制数

容错等级对应字节：

  • L –> 01
  • M –> 00
  • Q –> 11
  • H –> 10

掩码模式，用于对二维码进行“美化”，便于机器识别，共有八种，编码从 1 到 8，比如用 Mask Pattern 4 ，格式信息中的掩码模式编码则为 (4).toString(2) = 100

计算过程：

  • 容错等级为 L: 01
  • 掩码模式为 4： 100
  • 拼接： 01100
  • 纠错码（计算过程看伪代码）： 1000111101
  • 拼接： 011001000111101
  • 用于异或计算的常量： 101010000010010
  • 异或计算： 001010011011100 ^ 101010000010010 = 110011000101111

伪代码如下：

// 二进制字符串转十进制异或再转为二进制字符串
function xorBinaryString(a, b) {
  return (parseInt(a, 2) ^ parseInt(b, 2)).toString(2);
}

function calcFormatBits(correctLevel = 'L', maskPattern = '4') {
  const correctLevelBitsMap = {
    L: '01', M: '00',
    Q: '11', H: '10',
  };

  // 二维码规范中规定的用于计算格式信息【纠错码】的固定多项式
  const errorCorrectionFixedPolynomial = '10100110111';  // x^10 + x^8 + x^5 + x^4 + x^2 + x + 1

  // 二维码规范中规定的用于计算格式信息【最终结果】的固定多项式
  const calcResultFixedPolynomial = '101010000010010'; // x^14 + x^12 + x^10 + x^4 + x

  // 容错等级
  const correctLevelBits = correctLevelBitsMap[correctLevel];

  // 掩码模式，补足 3 位
  const maskPatternBits = Number(maskPattern).toString(2).padStart(3, '0');

  // 拼接容错等级和掩码模式，右侧补 0 到 15 位，并移除左侧的 0
  const originBits = `${correctLevelBits}${maskPatternBits}`.padEnd(15, '0').replace(/0*/, '');

  // 纠错码计算逻辑
  function division(bits) {
    const currentFormattedBits = bits;
    const currentFormattedBitsLen = currentFormattedBits.length;

    // 如果多项式和当前字符串位数不同，多项式右侧补 0 到相同位数
    const paddedPolynomial = currentFormattedBitsLen > errorCorrectionFixedPolynomial.length ? errorCorrectionFixedPolynomial.padEnd(currentFormattedBitsLen, '0') : errorCorrectionFixedPolynomial;

    // 当前字符串和多项式进行异或计算，然后移除左侧的 0
    const xorResult = xorBinaryString(currentFormattedBits, paddedPolynomial).replace(/0*/, '');

    // 多次计算，直到字符串长度小于等于 10
    if (xorResult.length > 10) return division(xorResult);

    // 左侧补 0 到 10 位
    return xorResult.padStart(10, '0');
  }

  // 纠错码
  const errorCorrectionCode = division(originBits);

  // 容错等级 + 掩码模式 + 纠错码，与多项式进行异或计算，最后左侧补 0 到 15 位
  const result = xorBinaryString(`${correctLevelBits}${maskPatternBits}${errorCorrectionCode}`, calcResultFixedPolynomial).padStart(15, '0');

  // console.log(correctLevel, maskPattern, correctLevelBits, maskPatternBits, originBits.padEnd(15, ' '), errorCorrectionCode.padEnd(10, ' '), result)

  return result;
}

calcFormatBits('L', '0') // -> L 0 01 000 10000000000000  1111010110 111011111000100
calcFormatBits('L', '1') // -> L 1 01 001 10010000000000  1011100001 111001011110011
calcFormatBits('L', '2') // -> L 2 01 010 10100000000000  0110111000 111110110101010
calcFormatBits('L', '3') // -> L 3 01 011 10110000000000  0010001111 111100010011101
calcFormatBits('L', '4') // -> L 4 01 100 11000000000000  1000111101 110011000101111
calcFormatBits('L', '5') // -> L 5 01 101 11010000000000  1100001010 110001100011000
calcFormatBits('L', '6') // -> L 6 01 110 11100000000000  0001010011 110110001000001
calcFormatBits('L', '7') // -> L 7 01 111 11110000000000  0101100100 110100101110110
calcFormatBits('M', '0') // -> M 0 00 000                 0000000000 101010000010010
calcFormatBits('M', '1') // -> M 1 00 001 10000000000     0100110111 101000100100101
calcFormatBits('M', '2') // -> M 2 00 010 100000000000    1001101110 101111001111100
calcFormatBits('M', '3') // -> M 3 00 011 110000000000    1101011001 101101101001011
calcFormatBits('M', '4') // -> M 4 00 100 1000000000000   0111101011 100010111111001
calcFormatBits('M', '5') // -> M 5 00 101 1010000000000   0011011100 100000011001110
calcFormatBits('M', '6') // -> M 6 00 110 1100000000000   1110000101 100111110010111
calcFormatBits('M', '7') // -> M 7 00 111 1110000000000   1010110010 100101010100000
calcFormatBits('Q', '0') // -> Q 0 11 000 110000000000000 0101001101 011010101011111
calcFormatBits('Q', '1') // -> Q 1 11 001 110010000000000 0001111010 011000001101000
calcFormatBits('Q', '2') // -> Q 2 11 010 110100000000000 1100100011 011111100110001
calcFormatBits('Q', '3') // -> Q 3 11 011 110110000000000 1000010100 011101000000110
calcFormatBits('Q', '4') // -> Q 4 11 100 111000000000000 0010100110 010010010110100
calcFormatBits('Q', '5') // -> Q 5 11 101 111010000000000 0110010001 010000110000011
calcFormatBits('Q', '6') // -> Q 6 11 110 111100000000000 1011001000 010111011011010
calcFormatBits('Q', '7') // -> Q 7 11 111 111110000000000 1111111111 010101111101101
calcFormatBits('H', '0') // -> H 0 10 000 100000000000000 1010011011 001011010001001
calcFormatBits('H', '1') // -> H 1 10 001 100010000000000 1110101100 001001110111110
calcFormatBits('H', '2') // -> H 2 10 010 100100000000000 0011110101 001110011100111
calcFormatBits('H', '3') // -> H 3 10 011 100110000000000 0111000010 001100111010000
calcFormatBits('H', '4') // -> H 4 10 100 101000000000000 1101110000 000011101100010
calcFormatBits('H', '5') // -> H 5 10 101 101010000000000 1001000111 000001001010101
calcFormatBits('H', '6') // -> H 6 10 110 101100000000000 0100011110 000110100001100
calcFormatBits('H', '7') // -> H 7 10 111 101110000000000 0000101001 000100000111011

绘制顺序如下：格式信息.png

结果列表如下（有限值，实际应用可以先行计算完毕直接取用）：

容错等级 掩码模式 格式信息
L 0 111011111000100
L 1 111001011110011
L 2 111110110101010
L 3 111100010011101
L 4 110011000101111
L 5 110001100011000
L 6 110110001000001
L 7 110100101110110
M 0 101010000010010
M 1 101000100100101
M 2 101111001111100
M 3 101101101001011
M 4 100010111111001
M 5 100000011001110
M 6 100111110010111
M 7 100101010100000
Q 0 011010101011111
Q 1 011000001101000
Q 2 011111100110001
Q 3 011101000000110
Q 4 010010010110100
Q 5 010000110000011
Q 6 010111011011010
Q 7 010101111101101
H 0 001011010001001
H 1 001001110111110
H 2 001110011100111
H 3 001100111010000
H 4 000011101100010
H 5 000001001010101
H 6 000110100001100
H 7 000100000111011

版本信息

二维码版本号大于7需要添加版本信息，为18位二进制数，组成 3*6 的图案

计算过程：

  • 版本号为7：000111
  • 右侧补0到18位，并清楚左侧的0： 111000000000000
  • 纠错码（计算过程看伪代码）： 110010010100
  • 拼接：000111110010010100

伪代码如下：

// 二进制字符串转十进制异或再转为二进制字符串
function xorBinaryString(a, b) {
  return (parseInt(a, 2) ^ parseInt(b, 2)).toString(2);
}

function calcVersionBits(version = '7') {
  // 二维码规范中规定的用于计算版本信息【纠错码】的固定多项式
  const polynomial = '1111100100101';

  // 版本号，补足 6 位
  const versionBits = Number(version).toString(2).padStart(6, '0');

  // 右侧补 0 到 18 位，并移除左侧的 0
  const originBits = versionBits.padEnd(18, '0').replace(/0*/, '');

  // 纠错码计算逻辑
  function division(bits) {
    const currentFormattedBits = bits;
    const currentFormattedBitsLen = currentFormattedBits.length;

    // 如果多项式和当前字符串位数不同，多项式右侧补 0 到相同位数
    const paddedPolynomial = currentFormattedBitsLen > polynomial.length ? polynomial.padEnd(currentFormattedBitsLen, '0') : polynomial;

    // 当前字符串和多项式进行异或计算，然后移除左侧的 0
    const xorResult = xorBinaryString(currentFormattedBits, paddedPolynomial).replace(/0*/, '');

    // 多次计算，直到字符串长度小于等于 12
    if (xorResult.length > 12) return division(xorResult);

    // 左侧补 0 到 12 位
    return xorResult.padStart(12, '0');
  }

  // 纠错码
  const errorCorrectionCode = division(originBits);

  // 拼接
  const result = `${versionBits}${errorCorrectionCode}`;

  console.log(version.padEnd(2, ' '), versionBits, errorCorrectionCode, result)

  return result;
}

calcVersionBits('7') // -> 7  000111 110010010100 000111110010010100
calcVersionBits('8') // -> 8  001000 010110111100 001000010110111100
calcVersionBits('9') // -> 9  001001 101010011001 001001101010011001
calcVersionBits('10') // -> 10 001010 010011010011 001010010011010011
calcVersionBits('11') // -> 11 001011 101111110110 001011101111110110
calcVersionBits('12') // -> 12 001100 011101100010 001100011101100010
calcVersionBits('13') // -> 13 001101 100001000111 001101100001000111
calcVersionBits('14') // -> 14 001110 011000001101 001110011000001101
calcVersionBits('15') // -> 15 001111 100100101000 001111100100101000
calcVersionBits('16') // -> 16 010000 101101111000 010000101101111000
calcVersionBits('17') // -> 17 010001 010001011101 010001010001011101
calcVersionBits('18') // -> 18 010010 101000010111 010010101000010111
calcVersionBits('19') // -> 19 010011 010100110010 010011010100110010
calcVersionBits('20') // -> 20 010100 100110100110 010100100110100110
calcVersionBits('21') // -> 21 010101 011010000011 010101011010000011
calcVersionBits('22') // -> 22 010110 100011001001 010110100011001001
calcVersionBits('23') // -> 23 010111 011111101100 010111011111101100
calcVersionBits('24') // -> 24 011000 111011000100 011000111011000100
calcVersionBits('25') // -> 25 011001 000111100001 011001000111100001
calcVersionBits('26') // -> 26 011010 111110101011 011010111110101011
calcVersionBits('27') // -> 27 011011 000010001110 011011000010001110
calcVersionBits('28') // -> 28 011100 110000011010 011100110000011010
calcVersionBits('29') // -> 29 011101 001100111111 011101001100111111
calcVersionBits('30') // -> 30 011110 110101110101 011110110101110101
calcVersionBits('31') // -> 31 011111 001001010000 011111001001010000
calcVersionBits('32') // -> 32 100000 100111010101 100000100111010101
calcVersionBits('33') // -> 33 100001 011011110000 100001011011110000
calcVersionBits('34') // -> 34 100010 100010111010 100010100010111010
calcVersionBits('35') // -> 35 100011 011110011111 100011011110011111
calcVersionBits('36') // -> 36 100100 101100001011 100100101100001011
calcVersionBits('37') // -> 37 100101 010000101110 100101010000101110
calcVersionBits('38') // -> 38 100110 101001100100 100110101001100100
calcVersionBits('39') // -> 39 100111 010101000001 100111010101000001
calcVersionBits('40') // -> 40 101000 110001101001 101000110001101001

绘制顺序如下：方形区域.png

结果列表如下（有限值，实际应用可以先行计算完毕直接取用）：

版本号 版本信息
7 000111110010010100
8 001000010110111100
9 001001101010011001
10 001010010011010011
11 001011101111110110
12 001100011101100010
13 001101100001000111
14 001110011000001101
15 001111100100101000
16 010000101101111000
17 010001010001011101
18 010010101000010111
19 010011010100110010
20 010100100110100110
21 010101011010000011
22 010110100011001001
23 010111011111101100
24 011000111011000100
25 011001000111100001
26 011010111110101011
27 011011000010001110
28 011100110000011010
29 011101001100111111
30 011110110101110101
31 011111001001010000
32 100000100111010101
33 100001011011110000
34 100010100010111010
35 100011011110011111
36 100100101100001011
37 100101010000101110
38 100110101001100100
39 100111010101000001
40 101000110001101001

数据编码

看完其他区域，回头看数据区，本节以 HELLO WORLD 为例，讲解二维码是如何为字符串编码的

确定容错等级

确定本次编码选用哪种容错等级，如 Q

确定编码模式

根据字符串的类型，选择不同的编码模式

编码模式 判断方法 备注
数字模式 /0-9/ 数字
字母数字模式 /[0-9A-Z$%\*+-\/.:\s]/ 数字 + 大写字母 + 特殊符号（$%*+-/.:）+ 空格
字节模式 0x00 < x.charCodeAt(0) < 0xFF ISO 8859-1 编码中的字符
汉字模式 Shift JIS 中的字符 http://www.rikai.com/library/kanjitables/kanji_codes.sjis.shtml

但是，在实际应用中，字节模式不仅用来编码 ISO 8859-1 的字符，也用来编码 utf-8 的所有字符。Shift JIS 的所有字符都可以用 utf-8 来表示，所以一般来说，除了字母数字，都用字节模式来编码。

根据上表，HELLO WORLD 应该选择字母的编码模式

const ENCODING_MODE_NUMBER = 'ENCODING_MODE_NUMBER'; // 数字
const ENCODING_MODE_ALPHANUMERIC = 'ENCODING_MODE_ALPHANUMERIC'; // 字母数字
const ENCODING_MODE_BYTE = 'ENCODING_MODE_BYTE'; // ISO-8859-1
const ENCODING_MODE_KANJI = 'ENCODING_MODE_KANJI'; // 其他

function detectEncodingMode(value) {
    if (/[0-9]/.test(value)) return ENCODING_MODE_NUMBER;

  if (/[0-9A-Z$%\\*+-\\/.:\\s]/.test(value)) return ENCODING_MODE_ALPHANUMERIC;

  return ENCODING_MODE_BYTE;
}

detectEncodingMode(123456789); // -> ENCODING_MODE_NUMBER
detectEncodingMode('HELLO WORLD'); // -> ENCODING_MODE_ALPHANUMERIC
detectEncodingMode('<>'); // -> ENCODING_MODE_BYTE
detectEncodingMode('中文'); // -> ENCODING_MODE_KANJI

确定版本号

根据容错等级以及字符串的类型和长度，确定应该选用哪个版本（尺寸）的二维码

根据上文的容量表，Q 容错等级，字母的编码模式，11位长度的字符串，版本1即可满足容量需求

// 字符容量表
const CHAR_CAPACITY = [
    // 1
  [
    [41,25,17,10], // L
    [34,20,14,8], // M
    [27,16,11,7], // Q
    [17,10,7,4], // H
  ],
  // 2
  [
    [77,47,32,20],
    [63,38,26,16],
    [48,29,20,12],
    [34,20,14,8],
  ],
  // 3
  [
    [127,77,53,32],
    [101,61,42,26],
    [77,47,32,20],
    [58,35,24,15],
  ],
  // ...
  [
    [187,114,78,48],
    [149,90,62,38],
    [111,67,46,28],
    [82,50,34,21],
  ],
  [
    [255,154,106,65],
    [202,122,84,52],
    [144,87,60,37],
    [106,64,44,27],
  ],
  [
    [322,195,134,82],
    [255,154,106,65],
    [178,108,74,45],
    [139,84,58,36],
  ],
  [
    [370,224,154,95],
    [293,178,122,75],
    [207,125,86,53],
    [154,93,64,39],
  ],
  [
    [461,279,192,118],
    [365,221,152,93],
    [259,157,108,66],
    [202,122,84,52],
  ],
  [
    [552,335,230,141],
    [432,262,180,111],
    [312,189,130,80],
    [235,143,98,60],
  ],
  [
    [652,395,271,167],
    [513,311,213,131],
    [364,221,151,93],
    [288,174,119,74],
  ],
  [
    [772,468,321,198],
    [604,366,251,155],
    [427,259,177,109],
    [331,200,137,85],
  ],
  [
    [883,535,367,226],
    [691,419,287,177],
    [489,296,203,125],
    [374,227,155,96],
  ],
  [
    [1022,619,425,262],
    [796,483,331,204],
    [580,352,241,149],
    [427,259,177,109],
  ],
  [
    [1101,667,458,282],
    [871,528,362,223],
    [621,376,258,159],
    [468,283,194,120],
  ],
  [
    [1250,758,520,320],
    [991,600,412,254],
    [703,426,292,180],
    [530,321,220,136],
  ],
  [
    [1408,854,586,361],
    [1082,656,450,277],
    [775,470,322,198],
    [602,365,250,154],
  ],
  [
    [1548,938,644,397],
    [1212,734,504,310],
    [876,531,364,224],
    [674,408,280,173],
  ],
  [
    [1725,1046,718,442],
    [1346,816,560,345],
    [948,574,394,243],
    [746,452,310,191],
  ],
  [
    [1903,1153,792,488],
    [1500,909,624,384],
    [1063,644,442,272],
    [813,493,338,208],
  ],
  [
    [2061,1249,858,528],
    [1600,970,666,410],
    [1159,702,482,297],
    [919,557,382,235],
  ],
  [
    [2232,1352,929,572],
    [1708,1035,711,438],
    [1224,742,509,314],
    [969,587,403,248],
  ],
  [
    [2409,1460,1003,618],
    [1872,1134,779,480],
    [1358,823,565,348],
    [1056,640,439,270],
  ],
  [
    [2620,1588,1091,672],
    [2059,1248,857,528],
    [1468,890,611,376],
    [1108,672,461,284],
  ],
  [
    [2812,1704,1171,721],
    [2188,1326,911,561],
    [1588,963,661,407],
    [1228,744,511,315],
  ],
  [
    [3057,1853,1273,784],
    [2395,1451,997,614],
    [1718,1041,715,440],
    [1286,779,535,330],
  ],
  [
    [3283,1990,1367,842],
    [2544,1542,1059,652],
    [1804,1094,751,462],
    [1425,864,593,365],
  ],
  [
    [3517,2132,1465,902],
    [2701,1637,1125,692],
    [1933,1172,805,496],
    [1501,910,625,385],
  ],
  [
    [3669,2223,1528,940],
    [2857,1732,1190,732],
    [2085,1263,868,534],
    [1581,958,658,405],
  ],
  [
    [3909,2369,1628,1002],
    [3035,1839,1264,778],
    [2181,1322,908,559],
    [1677,1016,698,430],
  ],
  [
    [4158,2520,1732,1066],
    [3289,1994,1370,843],
    [2358,1429,982,604],
    [1782,1080,742,457],
  ],
  [
    [4417,2677,1840,1132],
    [3486,2113,1452,894],
    [2473,1499,1030,634],
    [1897,1150,790,486],
  ],
  [
    [4686,2840,1952,1201],
    [3693,2238,1538,947],
    [2670,1618,1112,684],
    [2022,1226,842,518],
  ],
  [
    [4965,3009,2068,1273],
    [3909,2369,1628,1002],
    [2805,1700,1168,719],
    [2157,1307,898,553],
  ],
  [
    [5253,3183,2188,1347],
    [4134,2506,1722,1060],
    [2949,1787,1228,756],
    [2301,1394,958,590],
  ],
  [
    [5529,3351,2303,1417],
    [4343,2632,1809,1113],
    [3081,1867,1283,790],
    [2361,1431,983,605],
  ],
  [
    [5836,3537,2431,1496],
    [4588,2780,1911,1176],
    [3244,1966,1351,832],
    [2524,1530,1051,647],
  ],
  [
    [6153,3729,2563,1577],
    [4775,2894,1989,1224],
    [3417,2071,1423,876],
    [2625,1591,1093,673],
  ],
  [
    [6479,3927,2699,1661],
    [5039,3054,2099,1292],
    [3599,2181,1499,923],
    [2735,1658,1139,701],
  ],
  [
    [6743,4087,2809,1729],
    [5313,3220,2213,1362],
    [3791,2298,1579,972],
    [2927,1774,1219,750],
  ],
  // 40
  [
    [7089,4296,2953,1817],
    [5596,3391,2331,1435],
    [3993,2420,1663,1024],
    [3057,1852,1273,784],
  ],
];

function detectVersion(value, correctLevel, encodingMode) {
  let version = '1';

  const len = value.length;

  const correctLevelIndex = [CORRECT_LEVEL_L, CORRECT_LEVEL_M, CORRECT_LEVEL_Q, CORRECT_LEVEL_H].indexOf(correctLevel);
  const encodingModeIndex = [ENCODING_MODE_NUMBER, ENCODING_MODE_ALPHANUMERIC, ENCODING_MODE_BYTE, ENCODING_MODE_KANJI].indexOf(encodingMode);

  for (let i = 0; i < CHAR_CAPACITY.length; i++) {
  if (len <= CHAR_CAPACITY[i][correctLevelIndex][encodingModeIndex]) version = i + 1;
    break;
  }

  return String(version);
}

detectVersion('HELLO WORLD', 'Q', ENCODING_MODE_ALPHANUMERIC); // -> 1

确定编码模式指示器

根据编码模式的不同，选择不同的编码模式指示器

编码模式 模式指示器
数字模式 0001
字母数字模式 0010
字节模式 0100
汉字模式 1000

根据上表，HELLO WORLD 应该选择字母的编码模式指示器，0010

function detectEncodingModeIndicator(encodingMode) {
    switch (encodingMode) {
      case ENCODING_MODE_NUMBER:
      return '0001';
    case ENCODING_MODE_ALPHANUMERIC:
      return '0010';
    case ENCODING_MODE_BYTE:
      return '0100';
    case ENCODING_MODE_KANJI:
      return '1000';
  }
}

detectEncodingModeIndicator(ENCODING_MODE_NUMBER); // -> 0001

确定字符数量指示器

字符数量指示器用来表示要编码的字符数的二进制字符串，根据版本 + 编码模式以及字符串的长度确定，列表如下：

版本号 编码模式 字符数量指示器长度
1-9 数字模式 10
字母数字模式 9
字节模式 8
汉字模式 8
10-26 数字模式 12
字母数字模式 11
字节模式 16
汉字模式 10
27-40 数字模式 14
字母数字模式 13
字节模式 16
汉字模式 12

根据上表， HELLO WORLD 的字符长度为11，转成二进制为 1011 ，版本号为1，编码模式为字母数字模式，字符数量指示器的长度为9，将 1011 左侧补0到9位，得到 000001011 

// 字符指示器长度表
const CHAR_COUNT_INDICATOR_LENGTH = [
  [10, 9, 8, 8], // version 1 - 9 [数字, 字母数字, 字节, 汉字]
  [12, 11, 16, 10], // version 10 - 26
  [14, 13, 16, 12], // version 27 - 40
];

function detectCharCountIndicator(value, version, encodingMode) {
  const encodingModeIndex = ENCODING_MODE_ORDER.indexOf(encodingMode);

  let charCountIndicatorLenTableIndex = 0;
  if (Number(version) <= 9) charCountIndicatorLenTableIndex = 0;
  if (Number(version) >= 10 && Number(version) <= 26) charCountIndicatorLenTableIndex = 1;
  if (Number(version) >= 27) charCountIndicatorLenTableIndex = 2;

  const valueLen = value.length;
  const charCountIndicatorLen = CHAR_COUNT_INDICATOR_LENGTH[charCountIndicatorLenTableIndex][encodingModeIndex];

  return valueLen.toString(2).padStart(charCountIndicatorLen, '0');
}

detectCharCountIndicator('HELLO WORLD', '1', 'ENCODING_MODE_ALPHANUMERIC'); // -> 000001011

编码

根据编码模式的不同，有不同的编码逻辑，具体如下：

  • 数字模式

    直接转成二进制数

    function encodeDataWithNumberMode(value) {
  return Number(value).toString(2);
}

  • 字母数字模式

    • 原始字符串两两分组，比如 HE LL O WO RL D
    • 从字母数字模式的字符数字对照表找到分组内各字符的数字
    • H -> 17； E -> 14
    • (45 * 17) + 14 = 779 （45 是固定值）
    • 转成二进制并左侧补 0 到 11 位，Number(779).toString(2).padStart(11, 0) = '01100001011'
    • 奇数长度字符，直接返回索引值的二进制，左侧补 0 到 6 位
字符 数字 字符 数字 字符 数字 字符 数字 字符 数字
0 0 A 10 K 20 U 30 + 40
1 1 B 11 L 21 V 31 - 41
2 2 C 12 M 22 W 32 . 42
3 3 D 13 N 23 X 33 / 43
4 4 E 14 O 24 Y 34 : 44
5 5 F 15 P 25 Z 35
6 6 G 16 Q 26 (空格) 36
7 7 H 17 R 27 $ 37
8 8 I 18 S 28 % 38
9 9 J 19 T 29 * 39 
  // 编码模式 - 字母数字模式对照表
  const ENCODING_MODE_ALPHANUMERIC_MAP = {
      0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9,
    A: 10, B: 11, C: 12, D: 13, E:14, F: 15, G: 16, H: 17, I: 18, J: 19, K: 20, L: 21, M: 22, N: 23, O: 24, P: 25, Q: 26, R: 27, S: 28, T: 29, U: 30, V: 31, W: 32, X: 33, Y: 34, Z: 35,
    [' ']: 36, $: 37,
  };
  ENCODING_MODE_ALPHANUMERIC_MAP['%'] = 38;
  ENCODING_MODE_ALPHANUMERIC_MAP['*'] = 39;
  ENCODING_MODE_ALPHANUMERIC_MAP['+'] = 40;
  ENCODING_MODE_ALPHANUMERIC_MAP['-'] = 41;
  ENCODING_MODE_ALPHANUMERIC_MAP['.'] = 42;
  ENCODING_MODE_ALPHANUMERIC_MAP['/'] = 43;
  ENCODING_MODE_ALPHANUMERIC_MAP[':'] = 44;

  function encodeDataWithAlphanumericMode(value) {
    // 两两分割
    const splittedValue = value.split(/(.{2})/).filter(i => !!i);

    return splittedValue.reduce((r, item) => {
      const current = []
      item.split('').forEach(i => {
          // 找到分组内每个字符对应的索引
        current.push(ENCODING_MODE_ALPHANUMERIC_MAP[i]);
      })

      let result = ''
      // 奇数长度字符串，索引值转二进制左侧补 0 到 6 位
      if (!current[1]) result = current[0].toString(2).padStart(6, '0');
      // 偶数长度字符串，45 * [0] + [1] 转二进制左侧补 0 到 11 位，
      if (current[1]) result = (45 * current[0] + current[1]).toString(2).padStart(11, '0');
      return `${r}${result}`;
    }, '');
  }

  encodeDataWithAlphanumericMode('HELLO WORLD'); // -> 0110000101101111000110100010111001011011100010011010100001101

  • 字节模式

    获取每个字符的 unicode 索引再转二进制，左侧补 0 到 8 位即可

    function encodeDataWithByteMode(value) {
  return value.split('').reduce((r, item) => {
    return `${r}${item.charCodeAt(0).toString(2).padStart(8, '0')}`;
  }, '');
}

encodeDataWithByteMode('Hello, world!'); // -> 01001000011001010110110001101100011011110010110000100000011101110110111101110010011011000110010000100001

  • 汉字模式

    • 获取每个字符的 Shift JIS 索引
    • 针对 0x8140 到 0x9ffc 的字符（以 “荷” <0x89d7> 为例）：
      • 0x89D7 - 0x8140 = 0x0897
      • 得到 0x08 0x97
      • (0x08 * 0xC0) + 0x97 = 0x697
      • 0x697 -> 0011010010111
    • 针对 0xE040 到 0xEBBF 的字符（以 “茗” <0xe4aa> 为例）:
      • 0xE4AA - 0xC140 = 0x236A
      • 得到 0x23 0x6A
      • (0x23 * 0xC0) + 0x6A = 0x1AAA
      • 0x1AAA -> 1101010101010
function encodeDataWithKanjiMode(value) {
    // 略
}

整合编码结果

根据以上复杂的计算后，可以获取以下的结果：

HELLO WORLD ：

编码模式指示器 字符数量指示器 内容
0010 000001011 0110000101101111000110100010111001011011100010011010100001101

最后，二维码规范规定编码后的字符串长度必须根据容错等级和版本拓展到8的倍数，所以针对上文的结果还需做额外处理。

版本、容错等级和字节长度的对应表如下：

版本号 容错等级 字节长度
1 L 19
M 16
Q 13
H 9
2 L 34
M 28
Q 22
H 16
3 L 55
M 44
Q 34
H 26
4 L 80
M 64
Q 48
H 36
5 L 108
M 86
Q 62
H 46
6 L 136
M 108
Q 76
H 60
7 L 156
M 124
Q 88
H 66
8 L 194
M 154
Q 110
H 86
9 L 232
M 182
Q 132
H 100
10 L 274
M 216
Q 154
H 122
11 L 324
M 254
Q 180
H 140
12 L 370
M 290
Q 206
H 158
13 L 428
M 334
Q 244
H 180
14 L 461
M 365
Q 261
H 197
15 L 523
M 415
Q 295
H 223
16 L 589
M 453
Q 325
H 253
17 L 647
M 507
Q 367
H 283
18 L 721
M 563
Q 397
H 313
19 L 795
M 627
Q 445
H 341
20 L 861
M 669
Q 485
H 385
21 L 932
M 714
Q 512
H 406
22 L 1006
M 782
Q 568
H 442
23 L 1094
M 860
Q 614
H 464
24 L 1174
M 914
Q 664
H 514
25 L 1276
M 1000
Q 718
H 538
26 L 1370
M 1062
Q 754
H 596
27 L 1468
M 1128
Q 808
H 628
28 L 1531
M 1193
Q 871
H 661
29 L 1631
M 1267
Q 911
H 701
30 L 1735
M 1373
Q 985
H 745
31 L 1843
M 1455
Q 1033
H 793
32 L 1955
M 1541
Q 1115
H 845
33 L 2071
M 1631
Q 1171
H 901
34 L 2191
M 1725
Q 1231
H 961
35 L 2306
M 1812
Q 1286
H 986
36 L 2434
M 1914
Q 1354
H 1054
37 L 2566
M 1992
Q 1426
H 1096
38 L 2702
M 2102
Q 1502
H 1142
39 L 2812
M 2216
Q 1582
H 1222
40 L 2956
M 2334
Q 1666
H 1276

具体流程如下：

  • 确定最终字符长度，如版本1，容错等级 Q 的 Hello World 最终比特长度应该为 13*8 = 104
  • 补0，最多补4位，比如整合前的编码是74位，小于104，而且补4个0也没到104位，那就补4个0
  • 补0，补到8的倍数，比如补完0之后只有78位，还需要补两个0，到80位，8的倍数
  • 重复补特定二进制，直到补满长度，比如80位还是小于104，用 11101100 和 00010001 重复补，一直补到104位
function mergeEncodedData(encodingModeIndicator, charCountIndicator, encodedData, version, correctLevel) {
  const repeatBits = ['11101100', '00010001'];
  const correctLevelIndex = CORRECT_LEVEL_ORDER.indexOf(correctLevel);
  const codeWordsBitsLen = CODE_WORDS_LENGTH[version - 1][correctLevelIndex] * 8; // 比特长度

  let result = `${encodingModeIndicator}${charCountIndicator}${encodedData}`;

  const codeWordsDiff = codeWordsBitsLen - result.length;

  // 直接补 0 到相应长度
  if (codeWordsDiff <= 4) return result.padEnd(codeWordsBitsLen, '0');

  // 先补四个 0
  result = result.padEnd(result.length + 4, '0');

  // 再补到 8 的倍数
  result = result.padEnd(result.length + 8 - result.length % 8, '0');

  // 长度还是不够，再补重复字节
  const len = result.length;
  for (let i = 0; i < codeWordsBitsLen - len; i += 8) {
    result = `${result}${repeatBits[(i / 8) % 2]}`;
  }

  return result;
}

mergeEncodedData('0010', '000001011', '0110000101101111000110100010111001011011100010011010100001101', '1', 'Q'); // -> 00100000010110110000101101111000110100010111001011011100010011010100001101000000111011000001000111101100

回忆下整个流程，如下图：

编组 22.png

伪代码

整合所有逻辑，伪代码如下：

// 容错等级
const CORRECT_LEVEL_L = 'L';
const CORRECT_LEVEL_M = 'M';
const CORRECT_LEVEL_Q = 'Q';
const CORRECT_LEVEL_H = 'H';

const CORRECT_LEVEL_ORDER = [CORRECT_LEVEL_L, CORRECT_LEVEL_M, CORRECT_LEVEL_Q, CORRECT_LEVEL_H];

// 编码模式
const ENCODING_MODE_NUMBER = 'ENCODING_MODE_NUMBER'; // 数字
const ENCODING_MODE_ALPHANUMERIC = 'ENCODING_MODE_ALPHANUMERIC'; // 字母数字
const ENCODING_MODE_BYTE = 'ENCODING_MODE_BYTE'; // ISO-8859-1
const ENCODING_MODE_KANJI = 'ENCODING_MODE_KANJI'; // 其他

const ENCODING_MODE_ORDER = [ENCODING_MODE_NUMBER, ENCODING_MODE_ALPHANUMERIC, ENCODING_MODE_BYTE, ENCODING_MODE_KANJI];

// 字符容量表
const CHAR_CAPACITY = [
  // 1
  [
    [41,25,17,10], // L
    [34,20,14,8], // M
    [27,16,11,7], // Q
    [17,10,7,4], // H
  ],
  // 2
  [
    [77,47,32,20],
    [63,38,26,16],
    [48,29,20,12],
    [34,20,14,8],
  ],
  // 3
  [
    [127,77,53,32],
    [101,61,42,26],
    [77,47,32,20],
    [58,35,24,15],
  ],
  // ...
  [
    [187,114,78,48],
    [149,90,62,38],
    [111,67,46,28],
    [82,50,34,21],
  ],
  [
    [255,154,106,65],
    [202,122,84,52],
    [144,87,60,37],
    [106,64,44,27],
  ],
  [
    [322,195,134,82],
    [255,154,106,65],
    [178,108,74,45],
    [139,84,58,36],
  ],
  [
    [370,224,154,95],
    [293,178,122,75],
    [207,125,86,53],
    [154,93,64,39],
  ],
  [
    [461,279,192,118],
    [365,221,152,93],
    [259,157,108,66],
    [202,122,84,52],
  ],
  [
    [552,335,230,141],
    [432,262,180,111],
    [312,189,130,80],
    [235,143,98,60],
  ],
  [
    [652,395,271,167],
    [513,311,213,131],
    [364,221,151,93],
    [288,174,119,74],
  ],
  [
    [772,468,321,198],
    [604,366,251,155],
    [427,259,177,109],
    [331,200,137,85],
  ],
  [
    [883,535,367,226],
    [691,419,287,177],
    [489,296,203,125],
    [374,227,155,96],
  ],
  [
    [1022,619,425,262],
    [796,483,331,204],
    [580,352,241,149],
    [427,259,177,109],
  ],
  [
    [1101,667,458,282],
    [871,528,362,223],
    [621,376,258,159],
    [468,283,194,120],
  ],
  [
    [1250,758,520,320],
    [991,600,412,254],
    [703,426,292,180],
    [530,321,220,136],
  ],
  [
    [1408,854,586,361],
    [1082,656,450,277],
    [775,470,322,198],
    [602,365,250,154],
  ],
  [
    [1548,938,644,397],
    [1212,734,504,310],
    [876,531,364,224],
    [674,408,280,173],
  ],
  [
    [1725,1046,718,442],
    [1346,816,560,345],
    [948,574,394,243],
    [746,452,310,191],
  ],
  [
    [1903,1153,792,488],
    [1500,909,624,384],
    [1063,644,442,272],
    [813,493,338,208],
  ],
  [
    [2061,1249,858,528],
    [1600,970,666,410],
    [1159,702,482,297],
    [919,557,382,235],
  ],
  [
    [2232,1352,929,572],
    [1708,1035,711,438],
    [1224,742,509,314],
    [969,587,403,248],
  ],
  [
    [2409,1460,1003,618],
    [1872,1134,779,480],
    [1358,823,565,348],
    [1056,640,439,270],
  ],
  [
    [2620,1588,1091,672],
    [2059,1248,857,528],
    [1468,890,611,376],
    [1108,672,461,284],
  ],
  [
    [2812,1704,1171,721],
    [2188,1326,911,561],
    [1588,963,661,407],
    [1228,744,511,315],
  ],
  [
    [3057,1853,1273,784],
    [2395,1451,997,614],
    [1718,1041,715,440],
    [1286,779,535,330],
  ],
  [
    [3283,1990,1367,842],
    [2544,1542,1059,652],
    [1804,1094,751,462],
    [1425,864,593,365],
  ],
  [
    [3517,2132,1465,902],
    [2701,1637,1125,692],
    [1933,1172,805,496],
    [1501,910,625,385],
  ],
  [
    [3669,2223,1528,940],
    [2857,1732,1190,732],
    [2085,1263,868,534],
    [1581,958,658,405],
  ],
  [
    [3909,2369,1628,1002],
    [3035,1839,1264,778],
    [2181,1322,908,559],
    [1677,1016,698,430],
  ],
  [
    [4158,2520,1732,1066],
    [3289,1994,1370,843],
    [2358,1429,982,604],
    [1782,1080,742,457],
  ],
  [
    [4417,2677,1840,1132],
    [3486,2113,1452,894],
    [2473,1499,1030,634],
    [1897,1150,790,486],
  ],
  [
    [4686,2840,1952,1201],
    [3693,2238,1538,947],
    [2670,1618,1112,684],
    [2022,1226,842,518],
  ],
  [
    [4965,3009,2068,1273],
    [3909,2369,1628,1002],
    [2805,1700,1168,719],
    [2157,1307,898,553],
  ],
  [
    [5253,3183,2188,1347],
    [4134,2506,1722,1060],
    [2949,1787,1228,756],
    [2301,1394,958,590],
  ],
  [
    [5529,3351,2303,1417],
    [4343,2632,1809,1113],
    [3081,1867,1283,790],
    [2361,1431,983,605],
  ],
  [
    [5836,3537,2431,1496],
    [4588,2780,1911,1176],
    [3244,1966,1351,832],
    [2524,1530,1051,647],
  ],
  [
    [6153,3729,2563,1577],
    [4775,2894,1989,1224],
    [3417,2071,1423,876],
    [2625,1591,1093,673],
  ],
  [
    [6479,3927,2699,1661],
    [5039,3054,2099,1292],
    [3599,2181,1499,923],
    [2735,1658,1139,701],
  ],
  [
    [6743,4087,2809,1729],
    [5313,3220,2213,1362],
    [3791,2298,1579,972],
    [2927,1774,1219,750],
  ],
  // 40
  [
    [7089,4296,2953,1817],
    [5596,3391,2331,1435],
    [3993,2420,1663,1024],
    [3057,1852,1273,784],
  ],
];

// 字符指示器长度表
const CHAR_COUNT_INDICATOR_LENGTH = [
  [10, 9, 8, 8], // version 1 - 9
  [12, 11, 16, 10], // version 10 - 26
  [14, 13, 16, 12], // version 27 - 40
];

// 编码模式 - 字母数字模式对照表
const ENCODING_MODE_ALPHANUMERIC_MAP = {
  0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9,
  A: 10, B: 11, C: 12, D: 13, E:14, F: 15, G: 16, H: 17, I: 18, J: 19, K: 20, L: 21, M: 22, N: 23, O: 24, P: 25, Q: 26, R: 27, S: 28, T: 29, U: 30, V: 31, W: 32, X: 33, Y: 34, Z: 35,
  [' ']: 36, $: 37,
};
ENCODING_MODE_ALPHANUMERIC_MAP['%'] = 38;
ENCODING_MODE_ALPHANUMERIC_MAP['*'] = 39;
ENCODING_MODE_ALPHANUMERIC_MAP['+'] = 40;
ENCODING_MODE_ALPHANUMERIC_MAP['-'] = 41;
ENCODING_MODE_ALPHANUMERIC_MAP['.'] = 42;
ENCODING_MODE_ALPHANUMERIC_MAP['/'] = 43;
ENCODING_MODE_ALPHANUMERIC_MAP[':'] = 44;

const CODE_WORDS_LENGTH = [
  // 1
  [19,16,13,9], // L M Q H
  // 2
  [34,28,22,16],
  // 3
  [55,44,34,26],
  // ...
  [80,64,48,36],
  [108,86,62,46],
  [136,108,76,60],
  [156,124,88,66],
  [194,154,110,86],
  [232,182,132,100],
  [274,216,154,122],
  [324,254,180,140],
  [370,290,206,158],
  [428,334,244,180],
  [461,365,261,197],
  [523,415,295,223],
  [589,453,325,253],
  [647,507,367,283],
  [721,563,397,313],
  [795,627,445,341],
  [861,669,485,385],
  [932,714,512,406],
  [1006,782,568,442],
  [1094,860,614,464],
  [1174,914,664,514],
  [1276,1000,718,538],
  [1370,1062,754,596],
  [1468,1128,808,628],
  [1531,1193,871,661],
  [1631,1267,911,701],
  [1735,1373,985,745],
  [1843,1455,1033,793],
  [1955,1541,1115,845],
  [2071,1631,1171,901],
  [2191,1725,1231,961],
  [2306,1812,1286,986],
  [2434,1914,1354,1054],
  [2566,1992,1426,1096],
  [2702,2102,1502,1142],
  [2812,2216,1582,1222],
  // 40
  [2956,2334,1666,1276],
]

/**
 * 确定编码模式
 * @param { string } value 原始字符串
 */
function detectEncodingMode(value) {
  if (/[0-9]/.test(value)) return ENCODING_MODE_NUMBER;

  if (/[0-9A-Z$%\\*+-\\/.:\\s]/.test(value)) return ENCODING_MODE_ALPHANUMERIC;

  return ENCODING_MODE_BYTE;
}

/**
 * 确定版本号
 * @param { string } value 原始字符串
 * @param { 'L' | 'M' | 'Q' | 'H' } correctLevel 容错等级
 * @param { 'ENCODING_MODE_NUMBER' |  'ENCODING_MODE_ALPHANUMERIC' | 'ENCODING_MODE_BYTE' | 'ENCODING_MODE_KANJI' } encodingMode 编码模式
 */
function detectVersion(value, correctLevel, encodingMode) {
  let version = '1';

  const len = value.length;

  const correctLevelIndex = CORRECT_LEVEL_ORDER.indexOf(correctLevel);
  const encodingModeIndex = ENCODING_MODE_ORDER.indexOf(encodingMode);

  for (let i = 0; i < CHAR_CAPACITY.length; i++) {
    if (len <= CHAR_CAPACITY[i][correctLevelIndex][encodingModeIndex]) version = i + 1;
    break;
  }

  return String(version);
}

/**
 * 确定编码模式指示器
 * @param { 'ENCODING_MODE_NUMBER' |  'ENCODING_MODE_ALPHANUMERIC' | 'ENCODING_MODE_BYTE' | 'ENCODING_MODE_KANJI' } encodingMode 编码模式
 */
function detectEncodingModeIndicator(encodingMode) {
  switch (encodingMode) {
    case ENCODING_MODE_NUMBER:
      return '0001';
    case ENCODING_MODE_ALPHANUMERIC:
      return '0010';
    case ENCODING_MODE_BYTE:
      return '0100';
    case ENCODING_MODE_KANJI:
      return '1000';
  }
}

/**
 * 确定字符数量指示器
 * @param { string } value 原始字符串
 * @param { string } version 版本号（1-40）
 * @param { 'ENCODING_MODE_NUMBER' |  'ENCODING_MODE_ALPHANUMERIC' | 'ENCODING_MODE_BYTE' | 'ENCODING_MODE_KANJI' } encodingMode 编码模式
 */
function detectCharCountIndicator(value, version, encodingMode) {
  const encodingModeIndex = ENCODING_MODE_ORDER.indexOf(encodingMode);

  let charCountIndicatorLenTableIndex = 0;
  if (Number(version) <= 9) charCountIndicatorLenTableIndex = 0;
  if (Number(version) >= 10 && Number(version) <= 26) charCountIndicatorLenTableIndex = 1;
  if (Number(version) >= 27) charCountIndicatorLenTableIndex = 2;

  const valueLen = value.length;
  const charCountIndicatorLen = CHAR_COUNT_INDICATOR_LENGTH[charCountIndicatorLenTableIndex][encodingModeIndex];

  return valueLen.toString(2).padStart(charCountIndicatorLen, '0');
}

/**
 * 编码数字
 * @param { string } value 原始字符串
 */
function encodeDataWithNumberMode(value) {
  return Number(value).toString(2);
}

/**
 * 编码字母数字
 * @param { string } value 原始字符串
 */
function encodeDataWithAlphanumericMode(value) {
  // 两两分割
  const splittedValue = value.split(/(.{2})/).filter(i => !!i);

  return splittedValue.reduce((r, item) => {
    const current = []
    item.split('').forEach(i => {
      // 找到分组内每个字符对应的索引
      current.push(ENCODING_MODE_ALPHANUMERIC_MAP[i]);
    })

    let result = ''
    // 奇数长度字符串，索引值转二进制左侧补 0 到 6 位
    if (!current[1]) result = current[0].toString(2).padStart(6, '0');
    // 偶数长度字符串，45 * [0] + [1] 转二进制左侧补 0 到 11 位，
    if (current[1]) result = (45 * current[0] + current[1]).toString(2).padStart(11, '0');

    return `${r}${result}`;
  }, '');
}

/**
 * 编码字节
 * @param { string } value 原始字符串
 */
function encodeDataWithByteMode(value) {
  return value.split('').reduce((r, item) => {
    return `${r}${item.charCodeAt(0).toString(2).padStart(8, '0')}`;
  }, '');
}

/**
 * 编码汉字
 * @param { string } value 原始字符串
 */
function encodeDataWithKanjiMode(value) {
  // 略
}

/**
 * 合并最终计算结果
 * @param { string } encodingModeIndicator 编码模式指示器
 * @param { string } charCountIndicator 字符数量指示器
 * @param { string } encodedData 编码后的结果
 * @param { string } version 版本号（1-40）
 * @param { 'L' | 'M' | 'Q' | 'H' } correctLevel 容错等级
 */
function mergeEncodedData(encodingModeIndicator, charCountIndicator, encodedData, version, correctLevel) {
  const repeatBits = ['11101100', '00010001'];
  const correctLevelIndex = CORRECT_LEVEL_ORDER.indexOf(correctLevel);
  const codeWordsBitsLen = CODE_WORDS_LENGTH[version - 1][correctLevelIndex] * 8; // 比特长度

  let result = `${encodingModeIndicator}${charCountIndicator}${encodedData}`;

  const codeWordsDiff = codeWordsBitsLen - result.length;

  // 直接补 0 到相应长度
  if (codeWordsDiff <= 4) return result.padEnd(codeWordsBitsLen, '0');

  // 先补四个 0
  result = result.padEnd(result.length + 4, '0');

  // 再补到 8 的倍数
  result = result.padEnd(result.length + 8 - result.length % 8, '0');

  // 长度还是不够，再补重复字节
  const len = result.length;
  for (let i = 0; i < codeWordsBitsLen - len; i += 8) {
    result = `${result}${repeatBits[(i / 8) % 2]}`;
  }

  return result;
}

/**
 * 编码
 * @param { string } value 原始字符串
 * @param { string } correctLevel 容错等级
 */
function encodeData(value, correctLevel = 'L') {
  const encodingMode = detectEncodingMode(value);
  const version = detectVersion(value, correctLevel, encodingMode);

  const encodingModeIndicator = detectEncodingModeIndicator(encodingMode);
  const charCountIndicator = detectCharCountIndicator(value, version, encodingMode)

  let encodedData = '';
  switch (encodingMode) {
    case ENCODING_MODE_NUMBER:
      encodedData = encodeDataWithNumberMode(value);
      break;
    case ENCODING_MODE_ALPHANUMERIC:
      encodedData = encodeDataWithAlphanumericMode(value);
      break;
    case ENCODING_MODE_BYTE:
      encodedData = encodeDataWithByteMode(value);
      break;
    case ENCODING_MODE_KANJI:
      encodedData = encodeDataWithKanjiMode(value);
      break;
  }

  return mergeEncodedData(encodingModeIndicator, charCountIndicator, encodedData, version, correctLevel);
}

encodeData('HELLO WORLD', 'Q'); // -> 00100000010110110000101101111000110100010111001011011100010011010100001101000000111011000001000111101100

容错和纠错

讲了这么久，终于可以来到二维码最核心的部分，容错纠错

二维码能够大规模普及的很重要因素就是容错，即使一部分画面被污损，依旧可以被识别，而容错的实现原理，就是纠错算法中的里德-所罗门码

里德-所罗门码，可以对目标信息进行冗余拓展，在传输过程中，只要出错量少于事先定义好的值，就能完美的纠错解码

本节会涉及到一些简单的数学知识，包括有限域、多项式等

有限域

熟悉的朋友可以略过

有限域是指包含有限个元素的域，这是一个封闭的域，域内元素的四则运算，总会得到域内的结果

有限域又称，伽罗瓦域（Galois field），用 GF 表示

表示含有 p 个元的有限域，p 必须是质数的方幂，如

域内有 2^8 = 256 个元

有限域的四则运算

有限域中的四则运算，加等于减，乘等于除，并且四则运算的结果也必定在域中

以

为例，域内有8个数，分别是 0 1 2 3 4 5 6 7 ，对应的二进制如下：

  • 有限域中的加减都是异或运算，如 1 + 2 = 1 ^ 2 = 001 ^ 010 = 011 = 3 ，得出

    的加法表如下：

＋ 0 1 2 3 4 5 6 7
0 0 1 2 3 4 5 6 7
1 1 0 3 2 5 4 7 6
2 2 3 0 1 6 7 4 5
3 3 2 1 0 7 8 5 4
4 4 5 6 7 0 1 2 3
5 5 4 7 6 1 0 3 2
6 6 7 4 5 2 3 0 1
7 7 6 5 4 3 2 1 0

  • 有限域中的乘除较为复杂，规则如下：

    • 两个数先做模二相乘
    • 如果结果不在域内，再除以固定值 1011，取余数作为结果

    模二加法： 0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = 0
    模二减法： 0 - 0 = 0; 0 - 1 = 1; 1 - 0 = 1; 1 - 1 = 0
    模二乘法： 0 * 0 = 0; 0 * 1 = 0; 1 * 0 = 0; 1 * 1 = 1
    模二除法： 0 / 0 = 0; 1 / 1 = 1

    以 6 * 7 为例， 6 * 7 = 110 * 111 ，模二相乘算法如下：

    结果为 10010 = 39 ，大于域中的数，所以继续做模二除法：

    结果为余数，即 100 ，得出

    的乘法表如下：

x 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 3 1 7 5
3 0 3 6 5 7 4 1 2
4 0 4 3 7 6 2 5 1
5 0 5 1 4 2 7 3 5
6 0 6 7 1 5 3 2 4
7 0 7 5 2 1 6 4 3

多项式

熟悉的朋友可以略过

多项式，英文 Polynomial ，形如

可以含有常数、变量、指数，指数只能是 0、1、2

多项式和二进制

多项式和二进制数一一对应，规则是：存在指数的项记为1，不存在的记为0

以

为例，指数存在的项分别是， 0 1 2 4 5 8 10 ，那最终二进制数的这几位（从右向左）都为1，其他为0，也就是

易得结果 10100110111

反过来，以 11111100101 为例，指数存在的项应该是 0 2 5 6 7 8 9 10 ，结果为

多项式长除法

多项式除以或者乘以多项式，结果都是多项式，为了计算除以的结果，这里讲下多项式的长除法

如

计算过程如下：

再如无法整除的例子

计算过程如下：

里德-所罗门编码

讲完基础知识，下面讲解里德-所罗门是如何做到纠错的

要做到对某个字符进行纠错，必须知道两个信息：

  • 这串字符错了
  • 错误的值与正确的值的误差是多少

先看下里德-所罗门（RS）编码的图解：

计算机体系中，一个字节有八个比特，所以最常用的RS编码是

255代表整个密语的比特数，223代表原始数据比特数，校验数据比特数则为 255 - 223 = 32 ，上图中的变量如下：

  • m = 8
  • n = 255
  • k = 223
  • 2t = 32

同样，涉及到伽罗瓦域的计算，也使用拥有255个元的

再看下RS规定的编码算法：

编组 28.png

举例，如 2021 这个字符，我们的目标是得到一串“加密”后的字符，修改加密后字符中的任意值，通过算法都可以得到 2021 这个原始值

待补充。

二维码规范中的纠错码计算

  • 分组
  • 计算
  • 合并

绘制

回顾以上所有信息，整理整个二维码各个区域的绘制顺序如下

  • 绘制定位区
  • 绘制分隔区
  • 绘制矫正区
  • 绘制时序信息
  • 绘制格式信息
  • 绘制版本信息
  • 绘制数据区

除数据区外，其他区域如何绘制都以详细讲解，本节主要关注数据区的绘制逻辑，如下：![编组 19.png](./1612510048074-c1a2d072-8874-4916-9a46-ff3f6c61c25c.png过

掩码

经过一系列复杂的步骤之后，终于来到二维码生成的最后一步，掩码

掩码之前的图案很可能如下图，特别是字符较少，大部分需要用0填充的时候：

image.png

所以掩码其实就是对最后的数据区进行操作，让图案更加零散，便于机器识别，不同的掩码模式会根据坐标和对应的计算规则进行异或运算（如 0,3 是 1，计算后公式成立，取反改为 0）

上文提到，二维码规范中的掩码模式有八种，各种掩码模式的计算逻辑如下：

掩码模式编号 计算逻辑（根据坐标计算公式，成立则取反）
0 (x + y) % 2 === 0
1 x % 2 === 0
2 y % 3 === 0
3 (x + y) % 3 === 0
4 (floor(x / 2) + floor(y / 3)) % 2 === 0
5 ((x y) % 2) + ((x y) % 3) === 0
6 (((x y) % 2) + ((x y % 3))) % 2 === 0
7 (((x + y) % 2) + ((x +*y) % 3)) % 2 === 0

当然，掩码模式的选择并不是随机任选，而是根据掩码模式计算出四个惩罚分，选择惩罚分总和最低的那种模式作为最终掩码模式。惩罚分计算逻辑如下（惩罚分的计算，需要包含二维码所有区域）：

  • 惩罚分一：

    同行或同列连续5块颜色相同记三分，每多一块加一分

    image.png

  • 惩罚分二：

    m * n 的同色色块，记分

    比如 2*2 色块相同，则记 3 分， 3*3 色块相同，则记 12 分

    image.png

  • 惩罚分三：

    同行或者同列出现 10111010000 或者 00001011101 则记 40 分

    编组 31.png

  • 惩罚分四：

    用黑色色块在整个二维码中的占比，减去50%得到绝对值，每差5%记10分，不满5%的忽略，比如黑色色块占 62%，则应该记 Math.floor(Math.abs(62 - 50) / 5) * 3 = 20 20分

    图略。

以 HELLO WORLD 容错 Q 为例，未掩码绘制的图案如下：

用八种不同的掩码模式绘制结果及惩罚分如下：

image.png

可知惩罚分最少的是掩码模式一，所以最终结果就是：

image.png

其他