# genqrcode / libqrencode — Error Correction ## Overview QR Code uses Reed-Solomon error correction to enable reliable scanning even when parts of the symbol are damaged or obscured. libqrencode implements error correction through the `rsecc.c` module (GF(2^8) Reed-Solomon encoder) and coordinates block layout through `qrspec.c` / `mqrspec.c`. --- ## Error Correction Levels Four levels are defined in `QRecLevel`: ```c typedef enum { QR_ECLEVEL_L = 0, // Low — ~7% recovery QR_ECLEVEL_M, // Medium — ~15% recovery QR_ECLEVEL_Q, // Quartile — ~25% recovery QR_ECLEVEL_H // High — ~30% recovery } QRecLevel; ``` Higher error correction means more codewords are devoted to ECC, reducing data capacity. ### Micro QR Restrictions Not all Micro QR versions support all levels: | Version | Supported Levels | |---|---| | M1 | Error detection only (no EC level parameter effect) | | M2 | L, M | | M3 | L, M | | M4 | L, M, Q | Micro QR never supports `QR_ECLEVEL_H`. This is enforced in `QRinput_newMQR()` via `MQRspec_getECCLength()` returning 0 for invalid combinations. --- ## ECC Specification Tables ### Full QR Code — `eccTable` Defined in `qrspec.c`: ```c static const int eccTable[QRSPEC_VERSION_MAX+1][4][2] = { {{ 0, 0}, { 0, 0}, { 0, 0}, { 0, 0}}, // version 0 (unused) {{ 1, 0}, { 1, 0}, { 1, 0}, { 1, 0}}, // version 1 {{ 1, 0}, { 1, 0}, { 1, 0}, { 1, 0}}, // version 2 {{ 1, 0}, { 1, 0}, { 2, 0}, { 2, 0}}, // version 3 // ... through version 40 }; ``` Dimensions: `[version][ec_level][2]`. The two values are: - `eccTable[v][l][0]` — Number of RS blocks in group 1 - `eccTable[v][l][1]` — Number of RS blocks in group 2 (0 if only one group) ### ECC Spec Extraction `QRspec_getEccSpec()` computes a 5-element spec array: ```c void QRspec_getEccSpec(int version, QRecLevel level, int spec[5]) { int b1 = eccTable[version][level][0]; int b2 = eccTable[version][level][1]; int data = QRspec_getDataLength(version, level); int ecc = QRspec_getECCLength(version, level); if(b2 == 0) { spec[0] = b1; spec[1] = data / b1; spec[2] = ecc / b1; spec[3] = 0; spec[4] = 0; } else { spec[0] = b1; spec[1] = data / (b1 + b2); spec[2] = ecc / (b1 + b2); spec[3] = b2; spec[4] = spec[1] + 1; } } ``` The spec layout: - `spec[0]` — Number of RS blocks in group 1 (`b1`) - `spec[1]` — Data codewords per block in group 1 - `spec[2]` — ECC codewords per block - `spec[3]` — Number of RS blocks in group 2 (`b2`, 0 if none) - `spec[4]` — Data codewords per block in group 2 (= spec[1] + 1, or 0) Accessor macros: ```c #define QRspec_rsBlockNum(__spec__) (__spec__[0] + __spec__[3]) #define QRspec_rsBlockNum1(__spec__) (__spec__[0]) #define QRspec_rsDataCodes1(__spec__) (__spec__[1]) #define QRspec_rsEccCodes1(__spec__) (__spec__[2]) #define QRspec_rsBlockNum2(__spec__) (__spec__[3]) #define QRspec_rsDataCodes2(__spec__) (__spec__[4]) #define QRspec_rsEccCodes2(__spec__) (__spec__[2]) ``` Note that both groups share the same ECC codeword count. --- ## Capacity Tables ### Full QR — `qrspecCapacity` Defined in `qrspec.c`, 41 entries (index 0 is unused): ```c typedef struct { int width; // symbol width in modules int words; // total data codewords int remainder; // remainder bits (0–7) int ec[4]; // data codewords per EC level [L, M, Q, H] } QRspec_Capacity; static const QRspec_Capacity qrspecCapacity[QRSPEC_VERSION_MAX + 1] = { { 0, 0, 0, { 0, 0, 0, 0}}, { 21, 26, 0, { 19, 16, 13, 9}}, // v1: 21×21 { 25, 44, 7, { 34, 28, 22, 16}}, // v2: 25×25 { 29, 70, 7, { 55, 44, 34, 26}}, // v3 { 33, 100, 7, { 80, 64, 48, 36}}, // v4 // ... through version 40 {177, 3706, 0, {2956, 2334, 1666, 1276}}, // v40: 177×177 }; ``` Key accessor functions: ```c int QRspec_getDataLength(int version, QRecLevel level); // Returns qrspecCapacity[version].ec[level] int QRspec_getECCLength(int version, QRecLevel level); // Returns qrspecCapacity[version].words - qrspecCapacity[version].ec[level] int QRspec_getWidth(int version); // Returns qrspecCapacity[version].width (= version * 4 + 17) int QRspec_getRemainder(int version); // Returns qrspecCapacity[version].remainder int QRspec_getMinimumVersion(int size, QRecLevel level); // Scans versions 1-40 for first where data capacity >= size ``` ### Sample Capacities | Version | Width | Total Words | L Data | M Data | Q Data | H Data | |---|---|---|---|---|---|---| | 1 | 21 | 26 | 19 | 16 | 13 | 9 | | 5 | 37 | 134 | 108 | 86 | 62 | 46 | | 10 | 57 | 346 | 271 | 213 | 151 | 119 | | 20 | 97 | 1022 | 858 | 666 | 482 | 382 | | 40 | 177 | 3706 | 2956 | 2334 | 1666 | 1276 | ### Micro QR — `mqrspecCapacity` Defined in `mqrspec.c`, 5 entries: ```c static const MQRspec_Capacity mqrspecCapacity[MQRSPEC_VERSION_MAX + 1] = { {0, 0, {0, 0, 0, 0}}, {11, 5, {2, 0, 0, 0}}, // M1: 11×11, detection only (2 data + 3 ECC) {13, 10, {5, 4, 0, 0}}, // M2: 13×13 {15, 17, {11, 9, 7, 0}}, // M3: 15×15 {17, 24, {16, 14, 10, 0}} // M4: 17×17 }; ``` --- ## RSblock Structure In `qrencode.c`, RS blocks are organized in two structures: ```c typedef struct { int dataLength; unsigned char *data; int eccLength; unsigned char *ecc; } RSblock; ``` ### QRRawCode — Full QR ```c typedef struct { int dataLength; int eccLength; int b1; // number of group 1 blocks int b2; // number of group 2 blocks int rsblock_num; // total blocks (b1 + b2) RSblock *rsblock; int count; // interleave counter } QRRawCode; ``` ### MQRRawCode — Micro QR ```c typedef struct { int version; int dataLength; int eccLength; unsigned char *datacode; unsigned char *ecccode; int b1; int rsblock_num; RSblock *rsblock; int count; int oddbits; } MQRRawCode; ``` The `oddbits` field handles Micro QR versions where data length is specified in bits rather than bytes (M1 has odd-bit data length). ### Block Initialization `RSblock_initBlock()` calls the Reed-Solomon encoder for each block: ```c static int RSblock_initBlock(RSblock *block, int dl, unsigned char *data, int el, unsigned char *ecc, RSECC_encoder encoder) { block->dataLength = dl; block->data = data; block->eccLength = el; block->ecc = ecc; return encoder(dl, el, data, ecc); } ``` Where `encoder` is a function pointer to `RSECC_encode`. --- ## Block Interleaving The `QRraw_getCode()` function interleaves data and ECC bytes across blocks: ```c unsigned char QRraw_getCode(QRRawCode *raw) { if(raw->count < raw->dataLength) { // Data interleaving phase int blockNum = raw->count % raw->rsblock_num; int dataPos = raw->count / raw->rsblock_num; // ... skip blocks whose data is too short for this position ... unsigned char code = raw->rsblock[blockNum].data[dataPos]; } else { // ECC interleaving phase int blockNum = (raw->count - raw->dataLength) % raw->rsblock_num; int eccPos = (raw->count - raw->dataLength) / raw->rsblock_num; unsigned char code = raw->rsblock[blockNum].ecc[eccPos]; } raw->count++; return code; } ``` The interleaving ensures that consecutive codewords in the symbol come from different RS blocks, maximizing burst-error recovery. For a symbol with 2 blocks of 15 data + 1 block of 16 data: - First pass: byte 0 from block 0, byte 0 from block 1, byte 0 from block 2 - Second pass: byte 1 from block 0, byte 1 from block 1, byte 1 from block 2 - ... - The extra byte from block 2 (position 15) is appended at the end --- ## The RSECC Module The core Reed-Solomon encoder in `rsecc.c`. ### Galois Field GF(2^8) **Primitive polynomial**: `proot = 0x11d` = x^8 + x^4 + x^3 + x^2 + 1 **Log/antilog tables**: ```c static unsigned char alpha[256]; // alpha[i] = x^i mod proot static unsigned char aindex[256]; // aindex[alpha[i]] = i ``` Initialized in `RSECC_init()`: ```c static void RSECC_init(void) { int i, b; alpha[0] = 1; aindex[0] = 0; // undefined, but set to 0 aindex[1] = 0; for(i = 1; i < 255; i++) { b = alpha[i-1] << 1; if(b & 0x100) b ^= proot; // reduce mod primitive polynomial alpha[i] = (unsigned char)b; aindex[b] = i; } } ``` ### Generator Polynomial Cache Generator polynomials are cached for ECC lengths 2 through 30: ```c static int generator_initialized[29] = {0}; static unsigned char generator[29][31]; // generator[el-2] stores the polynomial ``` `generator_init()` builds the polynomial (x + α^0)(x + α^1)...(x + α^(el-1)): ```c static void generator_init(int el) { int i, j; unsigned char *g = generator[el - 2]; g[0] = 1; for(i = 0; i < el; i++) { g[i+1] = 1; for(j = i; j > 0; j--) { if(g[j] != 0) { g[j] = g[j-1] ^ alpha[(aindex[g[j]] + i) % 255]; } else { g[j] = g[j-1]; } } g[0] = alpha[(aindex[g[0]] + i) % 255]; } } ``` ### The Encode Function ```c int RSECC_encode(int data_length, int ecc_length, const unsigned char *data, unsigned char *ecc) ``` **Thread safety**: Protected by `RSECC_mutex` (pthread mutex) during initialization: ```c #ifdef HAVE_LIBPTHREAD static pthread_mutex_t RSECC_mutex = PTHREAD_MUTEX_INITIALIZER; #endif int RSECC_encode(int data_length, int ecc_length, const unsigned char *data, unsigned char *ecc) { // ... mutex lock ... if(!generator_initialized[ecc_length - 2]) { if(!initialized) RSECC_init(); generator_init(ecc_length); generator_initialized[ecc_length - 2] = 1; } // ... mutex unlock ... ``` **Encoding algorithm** — polynomial division: ```c unsigned char *gen = generator[ecc_length - 2]; unsigned char feedback; memset(ecc, 0, ecc_length); for(i = 0; i < data_length; i++) { feedback = aindex[data[i] ^ ecc[0]]; if(feedback != 255) { for(j = 1; j < ecc_length; j++) { ecc[j] ^= alpha[(feedback + aindex[gen[ecc_length - j]]) % 255]; } } memmove(&ecc[0], &ecc[1], ecc_length - 1); if(feedback != 255) { ecc[ecc_length - 1] = alpha[(feedback + aindex[gen[0]]) % 255]; } else { ecc[ecc_length - 1] = 0; } } ``` This implements systematic Reed-Solomon encoding: the `ecc` output is the remainder of dividing the data polynomial by the generator polynomial over GF(2^8). --- ## Format Information Format information encodes the EC level and mask pattern, protected by BCH(15,5). ### Full QR Format Info From `qrspec.c`, pre-computed table: ```c static const unsigned int formatInfo[4][8] = { {0x77c4, 0x72f3, 0x7daa, 0x789d, 0x662f, 0x6318, 0x6c41, 0x6976}, {0x5412, 0x5125, 0x5e7c, 0x5b4b, 0x45f9, 0x40ce, 0x4f97, 0x4aa0}, {0x355f, 0x3068, 0x3f31, 0x3a06, 0x24b4, 0x2183, 0x2eda, 0x2bed}, {0x1689, 0x13be, 0x1ce7, 0x19d0, 0x0762, 0x0255, 0x0d0c, 0x083b} }; ``` Indexed by `formatInfo[ec_level][mask_pattern]`. The 15-bit value is written into two locations in the symbol by `Mask_writeFormatInformation()`. ### Micro QR Format Info From `mqrspec.c`: ```c static const unsigned int typeTable[MQRSPEC_VERSION_MAX + 1][3] = { {0, 0, 0}, {0x4445, 0x4172, 0x4e2b}, {0x2f7f, 0x2a48, 0x2511}, // ... }; ``` --- ## How ECC Integrates Into Encoding The full encoding pipeline in `QRcode_encodeMask()`: 1. **Build byte stream**: `QRinput_getByteStream(input)` → packed data bytes 2. **Create QRRawCode**: `QRraw_new(input)` → initializes RS blocks, runs `RSECC_encode()` on each block 3. **Interleave**: `QRraw_getCode()` called repeatedly to get interleaved data+ECC bytes 4. **Place in frame**: `FrameFiller_next()` places each codeword bit in zigzag order 5. **Apply mask**: One of 8 mask patterns XORed with data area 6. **Format info**: `Mask_writeFormatInformation()` embeds EC level + mask pattern For Micro QR, `QRcode_encodeMaskMQR()` follows the same pattern but uses `MQRraw_new()`, `MQRraw_getCode()`, and `MMask_*` functions. --- ## RS Block Count Examples | Version | Level | Group 1 Blocks | Group 1 Data | Group 2 Blocks | Group 2 Data | ECC/Block | |---|---|---|---|---|---|---| | 1 | L | 1 | 19 | 0 | — | 7 | | 1 | H | 1 | 9 | 0 | — | 17 | | 5 | M | 2 | 43 | 0 | — | 24 | | 10 | Q | 6 | 24 | 2 | 25 | 26 | | 40 | L | 19 | 118 | 6 | 119 | 30 | | 40 | H | 20 | 15 | 61 | 16 | 30 | The maximum ECC codewords per block is 30, which corresponds to a degree-30 generator polynomial — the maximum cached in `generator[29]`.