1 /*
2  * Copyright 2007 ZXing authors
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 package com.google.zxing.qrcode.decoder;
18
19 import com.google.zxing.FormatException;
20 import com.google.zxing.common.BitMatrix;
21
22 /**
23  * See ISO 18004:2006 Annex D
24  *
25  * @author Sean Owen
26  */
27 public final class Version {
28
29   /**
30    * See ISO 18004:2006 Annex D.
31    * Element i represents the raw version bits that specify version i + 7
32    */
33   private static final int[] VERSION_DECODE_INFO = {
34       0x07C94, 0x085BC, 0x09A99, 0x0A4D3, 0x0BBF6,
35       0x0C762, 0x0D847, 0x0E60D, 0x0F928, 0x10B78,
36       0x1145D, 0x12A17, 0x13532, 0x149A6, 0x15683,
37       0x168C9, 0x177EC, 0x18EC4, 0x191E1, 0x1AFAB,
38       0x1B08E, 0x1CC1A, 0x1D33F, 0x1ED75, 0x1F250,
39       0x209D5, 0x216F0, 0x228BA, 0x2379F, 0x24B0B,
40       0x2542E, 0x26A64, 0x27541, 0x28C69
41   };
42
43   private static final Version[] VERSIONS = buildVersions();
44
45   private final int versionNumber;
46   private final int[] alignmentPatternCenters;
47   private final ECBlocks[] ecBlocks;
48   private final int totalCodewords;
49
50   private Version(int versionNumber,
51                   int[] alignmentPatternCenters,
52                   ECBlocks... ecBlocks) {
53     this.versionNumber = versionNumber;
54     this.alignmentPatternCenters = alignmentPatternCenters;
55     this.ecBlocks = ecBlocks;
56     int total = 0;
57     int ecCodewords = ecBlocks[0].getECCodewordsPerBlock();
58     ECB[] ecbArray = ecBlocks[0].getECBlocks();
59     for (ECB ecBlock : ecbArray) {
60       total += ecBlock.getCount() * (ecBlock.getDataCodewords() + ecCodewords);
61     }
62     this.totalCodewords = total;
63   }
64
65   public int getVersionNumber() {
66     return versionNumber;
67   }
68
69   public int[] getAlignmentPatternCenters() {
70     return alignmentPatternCenters;
71   }
72
73   public int getTotalCodewords() {
74     return totalCodewords;
75   }
76
77   public int getDimensionForVersion() {
78     return 17 + 4 * versionNumber;
79   }
80
81   public ECBlocks getECBlocksForLevel(ErrorCorrectionLevel ecLevel) {
82     return ecBlocks[ecLevel.ordinal()];
83   }
84
85   /**
86    * <p>Deduces version information purely from QR Code dimensions.</p>
87    *
88    * @param dimension dimension in modules
89    * @return Version for a QR Code of that dimension
90    * @throws FormatException if dimension is not 1 mod 4
91    */
92   public static Version getProvisionalVersionForDimension(int dimension) throws FormatException {
93     if (dimension % 4 != 1) {
94       throw FormatException.getFormatInstance();
95     }
96     try {
97       return getVersionForNumber((dimension - 17) / 4);
98     } catch (IllegalArgumentException ignored) {
99       throw FormatException.getFormatInstance();
100     }
101   }
102
103   public static Version getVersionForNumber(int versionNumber) {
104     if (versionNumber < 1 || versionNumber > 40) {
105       throw new IllegalArgumentException();
106     }
107     return VERSIONS[versionNumber - 1];
108   }
109
110   static Version decodeVersionInformation(int versionBits) {
111     int bestDifference = Integer.MAX_VALUE;
112     int bestVersion = 0;
113     for (int i = 0; i < VERSION_DECODE_INFO.length; i++) {
114       int targetVersion = VERSION_DECODE_INFO[i];
115       // Do the version info bits match exactly? done.
116       if (targetVersion == versionBits) {
117         return getVersionForNumber(i + 7);
118       }
119       // Otherwise see if this is the closest to a real version info bit string
120       // we have seen so far
121       int bitsDifference = FormatInformation.numBitsDiffering(versionBits, targetVersion);
122       if (bitsDifference < bestDifference) {
123         bestVersion = i + 7;
124         bestDifference = bitsDifference;
125       }
126     }
127     // We can tolerate up to 3 bits of error since no two version info codewords will
128     // differ in less than 8 bits.
129     if (bestDifference <= 3) {
130       return getVersionForNumber(bestVersion);
131     }
132     // If we didn't find a close enough match, fail
133     return null;
134   }
135
136   /**
137    * See ISO 18004:2006 Annex E
138    */
139   BitMatrix buildFunctionPattern() {
140     int dimension = getDimensionForVersion();
141     BitMatrix bitMatrix = new BitMatrix(dimension);
142
143     // Top left finder pattern + separator + format
144     bitMatrix.setRegion(0, 0, 9, 9);
145     // Top right finder pattern + separator + format
146     bitMatrix.setRegion(dimension - 8, 0, 8, 9);
147     // Bottom left finder pattern + separator + format
148     bitMatrix.setRegion(0, dimension - 8, 9, 8);
149
150     // Alignment patterns
151     int max = alignmentPatternCenters.length;
152     for (int x = 0; x < max; x++) {
153       int i = alignmentPatternCenters[x] - 2;
154       for (int y = 0; y < max; y++) {
155         if ((x != 0 || (y != 0 && y != max - 1)) && (x != max - 1 || y != 0)) {
156           bitMatrix.setRegion(alignmentPatternCenters[y] - 2, i, 5, 5);
157         }
158         // else no o alignment patterns near the three finder patterns
159       }
160     }
161
162     // Vertical timing pattern
163     bitMatrix.setRegion(6, 9, 1, dimension - 17);
164     // Horizontal timing pattern
165     bitMatrix.setRegion(9, 6, dimension - 17, 1);
166
167     if (versionNumber > 6) {
168       // Version info, top right
169       bitMatrix.setRegion(dimension - 11, 0, 3, 6);
170       // Version info, bottom left
171       bitMatrix.setRegion(0, dimension - 11, 6, 3);
172     }
173
174     return bitMatrix;
175   }
176
177   /**
178    * <p>Encapsulates a set of error-correction blocks in one symbol version. Most versions will
179    * use blocks of differing sizes within one version, so, this encapsulates the parameters for
180    * each set of blocks. It also holds the number of error-correction codewords per block since it
181    * will be the same across all blocks within one version.</p>
182    */
183   public static final class ECBlocks {
184     private final int ecCodewordsPerBlock;
185     private final ECB[] ecBlocks;
186
187     ECBlocks(int ecCodewordsPerBlock, ECB... ecBlocks) {
188       this.ecCodewordsPerBlock = ecCodewordsPerBlock;
189       this.ecBlocks = ecBlocks;
190     }
191
192     public int getECCodewordsPerBlock() {
193       return ecCodewordsPerBlock;
194     }
195
196     public int getNumBlocks() {
197       int total = 0;
198       for (ECB ecBlock : ecBlocks) {
199         total += ecBlock.getCount();
200       }
201       return total;
202     }
203
204     public int getTotalECCodewords() {
205       return ecCodewordsPerBlock * getNumBlocks();
206     }
207
208     public ECB[] getECBlocks() {
209       return ecBlocks;
210     }
211   }
212
213   /**
214    * <p>Encapsulates the parameters for one error-correction block in one symbol version.
215    * This includes the number of data codewords, and the number of times a block with these
216    * parameters is used consecutively in the QR code version's format.</p>
217    */
218   public static final class ECB {
219     private final int count;
220     private final int dataCodewords;
221
222     ECB(int count, int dataCodewords) {
223       this.count = count;
224       this.dataCodewords = dataCodewords;
225     }
226
227     public int getCount() {
228       return count;
229     }
230
231     public int getDataCodewords() {
232       return dataCodewords;
233     }
234   }
235
236   @Override
237   public String toString() {
238     return String.valueOf(versionNumber);
239   }
240
241   /**
242    * See ISO 18004:2006 6.5.1 Table 9
243    */
244   private static Version[] buildVersions() {
245     return new Version[]{
246         new Version(1, new int[]{},
247             new ECBlocks(7, new ECB(1, 19)),
248             new ECBlocks(10, new ECB(1, 16)),
249             new ECBlocks(13, new ECB(1, 13)),
250             new ECBlocks(17, new ECB(1, 9))),
251         new Version(2, new int[]{6, 18},
252             new ECBlocks(10, new ECB(1, 34)),
253             new ECBlocks(16, new ECB(1, 28)),
254             new ECBlocks(22, new ECB(1, 22)),
255             new ECBlocks(28, new ECB(1, 16))),
256         new Version(3, new int[]{6, 22},
257             new ECBlocks(15, new ECB(1, 55)),
258             new ECBlocks(26, new ECB(1, 44)),
259             new ECBlocks(18, new ECB(2, 17)),
260             new ECBlocks(22, new ECB(2, 13))),
261         new Version(4, new int[]{6, 26},
262             new ECBlocks(20, new ECB(1, 80)),
263             new ECBlocks(18, new ECB(2, 32)),
264             new ECBlocks(26, new ECB(2, 24)),
265             new ECBlocks(16, new ECB(4, 9))),
266         new Version(5, new int[]{6, 30},
267             new ECBlocks(26, new ECB(1, 108)),
268             new ECBlocks(24, new ECB(2, 43)),
269             new ECBlocks(18, new ECB(2, 15),
270                 new ECB(2, 16)),
271             new ECBlocks(22, new ECB(2, 11),
272                 new ECB(2, 12))),
273         new Version(6, new int[]{6, 34},
274             new ECBlocks(18, new ECB(2, 68)),
275             new ECBlocks(16, new ECB(4, 27)),
276             new ECBlocks(24, new ECB(4, 19)),
277             new ECBlocks(28, new ECB(4, 15))),
278         new Version(7, new int[]{6, 22, 38},
279             new ECBlocks(20, new ECB(2, 78)),
280             new ECBlocks(18, new ECB(4, 31)),
281             new ECBlocks(18, new ECB(2, 14),
282                 new ECB(4, 15)),
283             new ECBlocks(26, new ECB(4, 13),
284                 new ECB(1, 14))),
285         new Version(8, new int[]{6, 24, 42},
286             new ECBlocks(24, new ECB(2, 97)),
287             new ECBlocks(22, new ECB(2, 38),
288                 new ECB(2, 39)),
289             new ECBlocks(22, new ECB(4, 18),
290                 new ECB(2, 19)),
291             new ECBlocks(26, new ECB(4, 14),
292                 new ECB(2, 15))),
293         new Version(9, new int[]{6, 26, 46},
294             new ECBlocks(30, new ECB(2, 116)),
295             new ECBlocks(22, new ECB(3, 36),
296                 new ECB(2, 37)),
297             new ECBlocks(20, new ECB(4, 16),
298                 new ECB(4, 17)),
299             new ECBlocks(24, new ECB(4, 12),
300                 new ECB(4, 13))),
301         new Version(10, new int[]{6, 28, 50},
302             new ECBlocks(18, new ECB(2, 68),
303                 new ECB(2, 69)),
304             new ECBlocks(26, new ECB(4, 43),
305                 new ECB(1, 44)),
306             new ECBlocks(24, new ECB(6, 19),
307                 new ECB(2, 20)),
308             new ECBlocks(28, new ECB(6, 15),
309                 new ECB(2, 16))),
310         new Version(11, new int[]{6, 30, 54},
311             new ECBlocks(20, new ECB(4, 81)),
312             new ECBlocks(30, new ECB(1, 50),
313                 new ECB(4, 51)),
314             new ECBlocks(28, new ECB(4, 22),
315                 new ECB(4, 23)),
316             new ECBlocks(24, new ECB(3, 12),
317                 new ECB(8, 13))),
318         new Version(12, new int[]{6, 32, 58},
319             new ECBlocks(24, new ECB(2, 92),
320                 new ECB(2, 93)),
321             new ECBlocks(22, new ECB(6, 36),
322                 new ECB(2, 37)),
323             new ECBlocks(26, new ECB(4, 20),
324                 new ECB(6, 21)),
325             new ECBlocks(28, new ECB(7, 14),
326                 new ECB(4, 15))),
327         new Version(13, new int[]{6, 34, 62},
328             new ECBlocks(26, new ECB(4, 107)),
329             new ECBlocks(22, new ECB(8, 37),
330                 new ECB(1, 38)),
331             new ECBlocks(24, new ECB(8, 20),
332                 new ECB(4, 21)),
333             new ECBlocks(22, new ECB(12, 11),
334                 new ECB(4, 12))),
335         new Version(14, new int[]{6, 26, 46, 66},
336             new ECBlocks(30, new ECB(3, 115),
337                 new ECB(1, 116)),
338             new ECBlocks(24, new ECB(4, 40),
339                 new ECB(5, 41)),
340             new ECBlocks(20, new ECB(11, 16),
341                 new ECB(5, 17)),
342             new ECBlocks(24, new ECB(11, 12),
343                 new ECB(5, 13))),
344         new Version(15, new int[]{6, 26, 48, 70},
345             new ECBlocks(22, new ECB(5, 87),
346                 new ECB(1, 88)),
347             new ECBlocks(24, new ECB(5, 41),
348                 new ECB(5, 42)),
349             new ECBlocks(30, new ECB(5, 24),
350                 new ECB(7, 25)),
351             new ECBlocks(24, new ECB(11, 12),
352                 new ECB(7, 13))),
353         new Version(16, new int[]{6, 26, 50, 74},
354             new ECBlocks(24, new ECB(5, 98),
355                 new ECB(1, 99)),
356             new ECBlocks(28, new ECB(7, 45),
357                 new ECB(3, 46)),
358             new ECBlocks(24, new ECB(15, 19),
359                 new ECB(2, 20)),
360             new ECBlocks(30, new ECB(3, 15),
361                 new ECB(13, 16))),
362         new Version(17, new int[]{6, 30, 54, 78},
363             new ECBlocks(28, new ECB(1, 107),
364                 new ECB(5, 108)),
365             new ECBlocks(28, new ECB(10, 46),
366                 new ECB(1, 47)),
367             new ECBlocks(28, new ECB(1, 22),
368                 new ECB(15, 23)),
369             new ECBlocks(28, new ECB(2, 14),
370                 new ECB(17, 15))),
371         new Version(18, new int[]{6, 30, 56, 82},
372             new ECBlocks(30, new ECB(5, 120),
373                 new ECB(1, 121)),
374             new ECBlocks(26, new ECB(9, 43),
375                 new ECB(4, 44)),
376             new ECBlocks(28, new ECB(17, 22),
377                 new ECB(1, 23)),
378             new ECBlocks(28, new ECB(2, 14),
379                 new ECB(19, 15))),
380         new Version(19, new int[]{6, 30, 58, 86},
381             new ECBlocks(28, new ECB(3, 113),
382                 new ECB(4, 114)),
383             new ECBlocks(26, new ECB(3, 44),
384                 new ECB(11, 45)),
385             new ECBlocks(26, new ECB(17, 21),
386                 new ECB(4, 22)),
387             new ECBlocks(26, new ECB(9, 13),
388                 new ECB(16, 14))),
389         new Version(20, new int[]{6, 34, 62, 90},
390             new ECBlocks(28, new ECB(3, 107),
391                 new ECB(5, 108)),
392             new ECBlocks(26, new ECB(3, 41),
393                 new ECB(13, 42)),
394             new ECBlocks(30, new ECB(15, 24),
395                 new ECB(5, 25)),
396             new ECBlocks(28, new ECB(15, 15),
397                 new ECB(10, 16))),
398         new Version(21, new int[]{6, 28, 50, 72, 94},
399             new ECBlocks(28, new ECB(4, 116),
400                 new ECB(4, 117)),
401             new ECBlocks(26, new ECB(17, 42)),
402             new ECBlocks(28, new ECB(17, 22),
403                 new ECB(6, 23)),
404             new ECBlocks(30, new ECB(19, 16),
405                 new ECB(6, 17))),
406         new Version(22, new int[]{6, 26, 50, 74, 98},
407             new ECBlocks(28, new ECB(2, 111),
408                 new ECB(7, 112)),
409             new ECBlocks(28, new ECB(17, 46)),
410             new ECBlocks(30, new ECB(7, 24),
411                 new ECB(16, 25)),
412             new ECBlocks(24, new ECB(34, 13))),
413         new Version(23, new int[]{6, 30, 54, 78, 102},
414             new ECBlocks(30, new ECB(4, 121),
415                 new ECB(5, 122)),
416             new ECBlocks(28, new ECB(4, 47),
417                 new ECB(14, 48)),
418             new ECBlocks(30, new ECB(11, 24),
419                 new ECB(14, 25)),
420             new ECBlocks(30, new ECB(16, 15),
421                 new ECB(14, 16))),
422         new Version(24, new int[]{6, 28, 54, 80, 106},
423             new ECBlocks(30, new ECB(6, 117),
424                 new ECB(4, 118)),
425             new ECBlocks(28, new ECB(6, 45),
426                 new ECB(14, 46)),
427             new ECBlocks(30, new ECB(11, 24),
428                 new ECB(16, 25)),
429             new ECBlocks(30, new ECB(30, 16),
430                 new ECB(2, 17))),
431         new Version(25, new int[]{6, 32, 58, 84, 110},
432             new ECBlocks(26, new ECB(8, 106),
433                 new ECB(4, 107)),
434             new ECBlocks(28, new ECB(8, 47),
435                 new ECB(13, 48)),
436             new ECBlocks(30, new ECB(7, 24),
437                 new ECB(22, 25)),
438             new ECBlocks(30, new ECB(22, 15),
439                 new ECB(13, 16))),
440         new Version(26, new int[]{6, 30, 58, 86, 114},
441             new ECBlocks(28, new ECB(10, 114),
442                 new ECB(2, 115)),
443             new ECBlocks(28, new ECB(19, 46),
444                 new ECB(4, 47)),
445             new ECBlocks(28, new ECB(28, 22),
446                 new ECB(6, 23)),
447             new ECBlocks(30, new ECB(33, 16),
448                 new ECB(4, 17))),
449         new Version(27, new int[]{6, 34, 62, 90, 118},
450             new ECBlocks(30, new ECB(8, 122),
451                 new ECB(4, 123)),
452             new ECBlocks(28, new ECB(22, 45),
453                 new ECB(3, 46)),
454             new ECBlocks(30, new ECB(8, 23),
455                 new ECB(26, 24)),
456             new ECBlocks(30, new ECB(12, 15),
457                 new ECB(28, 16))),
458         new Version(28, new int[]{6, 26, 50, 74, 98, 122},
459             new ECBlocks(30, new ECB(3, 117),
460                 new ECB(10, 118)),
461             new ECBlocks(28, new ECB(3, 45),
462                 new ECB(23, 46)),
463             new ECBlocks(30, new ECB(4, 24),
464                 new ECB(31, 25)),
465             new ECBlocks(30, new ECB(11, 15),
466                 new ECB(31, 16))),
467         new Version(29, new int[]{6, 30, 54, 78, 102, 126},
468             new ECBlocks(30, new ECB(7, 116),
469                 new ECB(7, 117)),
470             new ECBlocks(28, new ECB(21, 45),
471                 new ECB(7, 46)),
472             new ECBlocks(30, new ECB(1, 23),
473                 new ECB(37, 24)),
474             new ECBlocks(30, new ECB(19, 15),
475                 new ECB(26, 16))),
476         new Version(30, new int[]{6, 26, 52, 78, 104, 130},
477             new ECBlocks(30, new ECB(5, 115),
478                 new ECB(10, 116)),
479             new ECBlocks(28, new ECB(19, 47),
480                 new ECB(10, 48)),
481             new ECBlocks(30, new ECB(15, 24),
482                 new ECB(25, 25)),
483             new ECBlocks(30, new ECB(23, 15),
484                 new ECB(25, 16))),
485         new Version(31, new int[]{6, 30, 56, 82, 108, 134},
486             new ECBlocks(30, new ECB(13, 115),
487                 new ECB(3, 116)),
488             new ECBlocks(28, new ECB(2, 46),
489                 new ECB(29, 47)),
490             new ECBlocks(30, new ECB(42, 24),
491                 new ECB(1, 25)),
492             new ECBlocks(30, new ECB(23, 15),
493                 new ECB(28, 16))),
494         new Version(32, new int[]{6, 34, 60, 86, 112, 138},
495             new ECBlocks(30, new ECB(17, 115)),
496             new ECBlocks(28, new ECB(10, 46),
497                 new ECB(23, 47)),
498             new ECBlocks(30, new ECB(10, 24),
499                 new ECB(35, 25)),
500             new ECBlocks(30, new ECB(19, 15),
501                 new ECB(35, 16))),
502         new Version(33, new int[]{6, 30, 58, 86, 114, 142},
503             new ECBlocks(30, new ECB(17, 115),
504                 new ECB(1, 116)),
505             new ECBlocks(28, new ECB(14, 46),
506                 new ECB(21, 47)),
507             new ECBlocks(30, new ECB(29, 24),
508                 new ECB(19, 25)),
509             new ECBlocks(30, new ECB(11, 15),
510                 new ECB(46, 16))),
511         new Version(34, new int[]{6, 34, 62, 90, 118, 146},
512             new ECBlocks(30, new ECB(13, 115),
513                 new ECB(6, 116)),
514             new ECBlocks(28, new ECB(14, 46),
515                 new ECB(23, 47)),
516             new ECBlocks(30, new ECB(44, 24),
517                 new ECB(7, 25)),
518             new ECBlocks(30, new ECB(59, 16),
519                 new ECB(1, 17))),
520         new Version(35, new int[]{6, 30, 54, 78, 102, 126, 150},
521             new ECBlocks(30, new ECB(12, 121),
522                 new ECB(7, 122)),
523             new ECBlocks(28, new ECB(12, 47),
524                 new ECB(26, 48)),
525             new ECBlocks(30, new ECB(39, 24),
526                 new ECB(14, 25)),
527             new ECBlocks(30, new ECB(22, 15),
528                 new ECB(41, 16))),
529         new Version(36, new int[]{6, 24, 50, 76, 102, 128, 154},
530             new ECBlocks(30, new ECB(6, 121),
531                 new ECB(14, 122)),
532             new ECBlocks(28, new ECB(6, 47),
533                 new ECB(34, 48)),
534             new ECBlocks(30, new ECB(46, 24),
535                 new ECB(10, 25)),
536             new ECBlocks(30, new ECB(2, 15),
537                 new ECB(64, 16))),
538         new Version(37, new int[]{6, 28, 54, 80, 106, 132, 158},
539             new ECBlocks(30, new ECB(17, 122),
540                 new ECB(4, 123)),
541             new ECBlocks(28, new ECB(29, 46),
542                 new ECB(14, 47)),
543             new ECBlocks(30, new ECB(49, 24),
544                 new ECB(10, 25)),
545             new ECBlocks(30, new ECB(24, 15),
546                 new ECB(46, 16))),
547         new Version(38, new int[]{6, 32, 58, 84, 110, 136, 162},
548             new ECBlocks(30, new ECB(4, 122),
549                 new ECB(18, 123)),
550             new ECBlocks(28, new ECB(13, 46),
551                 new ECB(32, 47)),
552             new ECBlocks(30, new ECB(48, 24),
553                 new ECB(14, 25)),
554             new ECBlocks(30, new ECB(42, 15),
555                 new ECB(32, 16))),
556         new Version(39, new int[]{6, 26, 54, 82, 110, 138, 166},
557             new ECBlocks(30, new ECB(20, 117),
558                 new ECB(4, 118)),
559             new ECBlocks(28, new ECB(40, 47),
560                 new ECB(7, 48)),
561             new ECBlocks(30, new ECB(43, 24),
562                 new ECB(22, 25)),
563             new ECBlocks(30, new ECB(10, 15),
564                 new ECB(67, 16))),
565         new Version(40, new int[]{6, 30, 58, 86, 114, 142, 170},
566             new ECBlocks(30, new ECB(19, 118),
567                 new ECB(6, 119)),
568             new ECBlocks(28, new ECB(18, 47),
569                 new ECB(31, 48)),
570             new ECBlocks(30, new ECB(34, 24),
571                 new ECB(34, 25)),
572             new ECBlocks(30, new ECB(20, 15),
573                 new ECB(61, 16)))
574     };
575   }
576
577 }
578