path: root/docs/handbook/genqrcode/masking-algorithms.md

# genqrcode / libqrencode — Masking Algorithms

## Purpose

After placing data and error correction codewords in the QR Code matrix, a mask pattern is XORed with the data area to avoid unfavorable patterns (large uniform regions, patterns resembling finder patterns). The library evaluates all candidate masks using a penalty scoring system and selects the mask with the lowest penalty.

---

## Full QR Code — 8 Mask Patterns

### The MASKMAKER Macro

All 8 mask condition functions are generated by a single macro in `mask.c`:

```c
#define MASKMAKER(__exp__) \
    int x, y;\
    int b = 0;\
    for(y = 0; y < width; y++) {\
        for(x = 0; x < width; x++) {\
            if(*s & 0x80) {\
                *d = *s;\
            } else {\
                *d = *s ^ ((__exp__) == 0);\
            }\
            s++; d++;\
        }\
    }\
    return b;
```

The `0x80` bit check skips non-data modules (finder patterns, timing patterns, alignment patterns, format/version info). The expression `(__exp__) == 0` evaluates the mask condition — when the condition is true (equals 0), the module is flipped.

### Mask Pattern Definitions

```c
static int Mask_mask0(int width, const unsigned char *s, unsigned char *d)
{
    MASKMAKER((y+x) % 2)
}

static int Mask_mask1(int width, const unsigned char *s, unsigned char *d)
{
    MASKMAKER(y % 2)
}

static int Mask_mask2(int width, const unsigned char *s, unsigned char *d)
{
    MASKMAKER(x % 3)
}

static int Mask_mask3(int width, const unsigned char *s, unsigned char *d)
{
    MASKMAKER((y+x) % 3)
}

static int Mask_mask4(int width, const unsigned char *s, unsigned char *d)
{
    MASKMAKER((y/2 + x/3) % 2)
}

static int Mask_mask5(int width, const unsigned char *s, unsigned char *d)
{
    MASKMAKER(((y*x) % 2 + (y*x) % 3))
}

static int Mask_mask6(int width, const unsigned char *s, unsigned char *d)
{
    MASKMAKER(((y*x) % 2 + (y*x) % 3) % 2)
}

static int Mask_mask7(int width, const unsigned char *s, unsigned char *d)
{
    MASKMAKER(((y*x) % 3 + (y+x) % 2) % 2)
}
```

Function pointer array:

```c
typedef int MaskMaker(int, const unsigned char *, unsigned char *);
static MaskMaker *maskMakers[8] = {
    Mask_mask0, Mask_mask1, Mask_mask2, Mask_mask3,
    Mask_mask4, Mask_mask5, Mask_mask6, Mask_mask7
};
```

### Summary Table

| Mask | Condition (module inverted when true) | Pattern |
|---|---|---|
| 0 | `(y + x) % 2 == 0` | Checkerboard |
| 1 | `y % 2 == 0` | Horizontal stripes |
| 2 | `x % 3 == 0` | Vertical stripes (every 3) |
| 3 | `(y + x) % 3 == 0` | Diagonal stripes |
| 4 | `(y/2 + x/3) % 2 == 0` | Block pattern |
| 5 | `(y*x)%2 + (y*x)%3 == 0` | Complex |
| 6 | `((y*x)%2 + (y*x)%3) % 2 == 0` | Complex |
| 7 | `((y*x)%3 + (y+x)%2) % 2 == 0` | Complex |

---

## Penalty Scoring

### Penalty Constants

Defined in `mask.c`:

```c
#define N1 3
#define N2 3
#define N3 40
#define N4 10
```

### Penalty Rule N1 + N3: Run Length

`Mask_calcN1N3()` evaluates both Rule 1 (adjacent same-color modules) and Rule 3 (finder-like patterns) using run-length data:

```c
static int Mask_calcN1N3(int length, int *runLength)
{
    int i;
    int demerit = 0;
    int fact;

    for(i = 0; i < length; i++) {
        if(runLength[i] >= 5) {
            demerit += N1 + (runLength[i] - 5);
        }
        if((i & 1)) {
            // Check for 1:1:3:1:1 pattern embedded in dark-light sequence
            if(i >= 3 && i < length - 2
               && (runLength[i] % 3) == 0) {
                fact = runLength[i] / 3;
                if(runLength[i-2] == fact &&
                   runLength[i-1] == fact &&
                   runLength[i+1] == fact &&
                   runLength[i+2] == fact) {
                    // Check for 4-module light space on either side
                    if(i == 3 || runLength[i-3] >= 4 * fact) {
                        demerit += N3;
                    } else if(i+4 >= length || runLength[i+3] >= 4 * fact) {
                        demerit += N3;
                    }
                }
            }
        }
    }
    return demerit;
}
```

**Rule N1**: Run of ≥ 5 same-color modules → penalty = 3 + (run_length − 5). For example, 7 consecutive dark modules → 3 + 2 = 5 penalty.

**Rule N3**: Pattern 1:1:3:1:1 (the finder pattern ratio) with 4+ light modules on either side → 40 penalty. This prevents patterns that confuse QR Code scanners.

### Run Length Calculation

Horizontal runs via `Mask_calcRunLengthH()`:

```c
static int Mask_calcRunLengthH(int width, const unsigned char *frame, int *runLength)
{
    int i;
    int head;
    int prev;

    if(frame[0] & 1) {
        runLength[0] = -1;
        head = 1;
    } else {
        head = 0;
    }
    runLength[head] = 1;
    prev = frame[0];

    for(i = 1; i < width; i++) {
        if((frame[i] ^ prev) & 1) {
            head++;
            runLength[head] = 1;
            prev = frame[i];
        } else {
            runLength[head]++;
        }
    }
    return head + 1;
}
```

Vertical runs via `Mask_calcRunLengthV()` — same logic but iterates `frame[i * width]`.

### Penalty Rule N2: 2×2 Blocks

`Mask_calcN2()` counts 2×2 same-color blocks:

```c
static int Mask_calcN2(int width, unsigned char *frame)
{
    int x, y;
    int demerit = 0;
    unsigned char *p;

    p = frame;
    for(y = 1; y < width; y++) {
        for(x = 1; x < width; x++) {
            // Check 2x2 block using bit 0
            if(((p[0]^p[1])|(p[width]^p[width+1])) & 1) {
                // not all same
            } else {
                demerit += N2;
            }
            p++;
        }
        p++;
    }
    return demerit;
}
```

Each 2×2 same-color block adds N2 = 3 penalty points.

### Penalty Rule N4: Dark/Light Balance

The `Mask_evaluateSymbol()` function counts dark modules and applies the balance penalty:

```c
static int Mask_evaluateSymbol(int width, unsigned char *frame)
{
    int x, y;
    int demerit = 0;
    int length;
    int runLength[width + 1];
    unsigned char *p;
    int dark = 0;

    demerit += Mask_calcN2(width, frame);

    p = frame;
    for(y = 0; y < width; y++) {
        length = Mask_calcRunLengthH(width, p, runLength);
        demerit += Mask_calcN1N3(length, runLength);
        p += width;
    }

    for(x = 0; x < width; x++) {
        length = Mask_calcRunLengthV(width, frame + x, runLength);
        demerit += Mask_calcN1N3(length, runLength);
    }

    // Count dark modules for N4
    p = frame;
    for(y = 0; y < width * width; y++) {
        if(p[y] & 1) dark++;
    }

    // Calculate demerits for N4
    // dark ratio in percent, deviation from 50%
    int ratio = (200 * dark + width * width) / (2 * width * width) - 50;
    if(ratio < 0) ratio = -ratio;
    demerit += ratio / 5 * N4;

    return demerit;
}
```

N4 penalty: For each 5% deviation from 50% dark/light balance, add N4 = 10 points.

---

## Mask Selection Algorithm

`Mask_mask()` tries all 8 patterns and selects the best:

```c
unsigned char *Mask_mask(int width, unsigned char *frame, QRecLevel level)
{
    int i;
    unsigned char *mask, *bestMask;
    int minDemerit = INT_MAX;
    int bestMaskNum = 0;
    int blacks;
    int bratio;
    int demerit;

    bestMask = NULL;

    for(i = 0; i < 8; i++) {
        mask = (unsigned char *)malloc(width * width);
        if(mask == NULL) break;

        demerit = 0;
        blacks = maskMakers[i](width, frame, mask);
        demerit = Mask_evaluateSymbol(width, mask);

        if(demerit < minDemerit) {
            minDemerit = demerit;
            free(bestMask);
            bestMask = mask;
            bestMaskNum = i;
        } else {
            free(mask);
        }
    }

    Mask_writeFormatInformation(width, bestMask, bestMaskNum, level);

    return bestMask;
}
```

Key points:
- Allocates a new `width × width` buffer for each mask attempt
- Applies the mask via `maskMakers[i]`
- Evaluates penalty via `Mask_evaluateSymbol()`
- Keeps only the lowest-demerit mask, frees the rest
- Writes format information into the selected mask

### Forced Mask

`QRcode_encodeMask()` accepts a `mask` parameter. When >= 0, it skips penalty evaluation and uses the specified mask directly:

```c
if(mask < 0) {
    masked = Mask_mask(width, frame, input->level);
} else {
    masked = Mask_makeMask(width, frame, mask, input->level);
}
```

`Mask_makeMask()` applies a single mask without evaluation:

```c
unsigned char *Mask_makeMask(int width, unsigned char *frame, int mask,
                              QRecLevel level)
{
    unsigned char *masked = (unsigned char *)malloc(width * width);
    maskMakers[mask](width, frame, masked);
    Mask_writeFormatInformation(width, masked, mask, level);
    return masked;
}
```

This is used by the test suite via `QRcode_encodeMask()` (exposed in `qrencode_inner.h`).

---

## Format Information Writing

`Mask_writeFormatInformation()` embeds the 15-bit format info (EC level + mask pattern) into the symbol at two fixed locations:

```c
void Mask_writeFormatInformation(int width, unsigned char *frame,
                                  int mask, QRecLevel level)
{
    unsigned int format;
    unsigned char v;
    int i;

    format = QRspec_getFormatInfo(mask, level);

    // Horizontal strip near top-left
    for(i = 0; i < 8; i++) {
        // ... write bits to specific positions around top-left finder ...
    }

    // Vertical strip near top-left and bottom-left
    for(i = 0; i < 7; i++) {
        // ... write bits to specific positions ...
    }
}
```

The format info is retrieved from the pre-computed `formatInfo[level][mask]` table (15-bit BCH code).

---

## Micro QR Code — 4 Mask Patterns

### Mask Definitions

From `mmask.c`, only 4 patterns:

```c
static int MMask_mask0(int width, const unsigned char *s, unsigned char *d)
{
    MASKMAKER(y % 2)
}

static int MMask_mask1(int width, const unsigned char *s, unsigned char *d)
{
    MASKMAKER(((y/2) + (x/3)) % 2)
}

static int MMask_mask2(int width, const unsigned char *s, unsigned char *d)
{
    MASKMAKER((((y*x) % 2) + ((y*x) % 3)) % 2)
}

static int MMask_mask3(int width, const unsigned char *s, unsigned char *d)
{
    MASKMAKER((((y+x) % 2) + ((y*x) % 3)) % 2)
}
```

Function pointer array:
```c
static MaskMaker *maskMakers[4] = {
    MMask_mask0, MMask_mask1, MMask_mask2, MMask_mask3
};
```

| Mask | Condition |
|---|---|
| 0 | `y % 2 == 0` |
| 1 | `(y/2 + x/3) % 2 == 0` |
| 2 | `((y*x)%2 + (y*x)%3) % 2 == 0` |
| 3 | `((y+x)%2 + (y*x)%3) % 2 == 0` |

### Micro QR Mask Evaluation

Micro QR uses a completely different scoring method. Instead of penalty rules, it maximizes a quality metric.

`MMask_evaluateSymbol()`:

```c
static int MMask_evaluateSymbol(int width, unsigned char *frame)
{
    int x, y;
    int sum1 = 0, sum2 = 0;

    // Sum of bottom row (last row, only data area)
    for(x = 1; x < width; x++) {
        if(frame[width * (width-1) + x] & 1) {
            sum1++;
        }
    }
    // Sum of rightmost column (only data area)
    for(y = 1; y < width; y++) {
        if(frame[y * width + (width-1)] & 1) {
            sum2++;
        }
    }

    return sum1 * 16 + sum2;
}
```

The score favors masks that produce more dark modules along the bottom row and right column. **Unlike full QR, higher scores are better.**

### Micro QR Mask Selection

`MMask_mask()`:

```c
unsigned char *MMask_mask(int version, unsigned char *frame, QRecLevel level)
{
    int width = MQRspec_getWidth(version);
    int i;
    unsigned char *mask, *bestMask = NULL;
    int maxScore = 0;
    int bestMaskNum = 0;
    int score;

    for(i = 0; i < 4; i++) {
        mask = (unsigned char *)malloc(width * width);
        maskMakers[i](width, frame, mask);
        score = MMask_evaluateSymbol(width, mask);

        if(score > maxScore) {  // Note: MAXIMUM, not minimum
            maxScore = score;
            free(bestMask);
            bestMask = mask;
            bestMaskNum = i;
        } else {
            free(mask);
        }
    }

    MMask_writeFormatInformation(version, bestMask, bestMaskNum, level);

    return bestMask;
}
```

### Micro QR Format Information

`MMask_writeFormatInformation()` writes a 15-bit format info in a single strip around the top-left finder pattern:

```c
void MMask_writeFormatInformation(int version, unsigned char *frame,
                                   int mask, QRecLevel level)
{
    unsigned int format;
    unsigned char v;
    int i;
    int width = MQRspec_getWidth(version);

    format = MQRspec_getFormatInfo(mask, version, level);

    for(i = 0; i < 8; i++) {
        v = 0x84 | (format & 1);
        frame[width * (i + 1) + 8] = v;  // left column
        format >>= 1;
    }
    for(i = 0; i < 7; i++) {
        v = 0x84 | (format & 1);
        frame[width * 8 + 7 - i] = v;    // top row
        format >>= 1;
    }
}
```

---

## Module Bit Flags

When placing modules, the frame builder uses bit flags to mark module types:

```c
// Bit 7 (0x80): Non-data module flag
// When set, masking skips this module
// Set on: finder pattern, separator, timing, alignment, version info, format info
```

In `MASKMAKER`, this check appears as:
```c
if(*s & 0x80) {
    *d = *s;      // copy as-is (non-data module)
} else {
    *d = *s ^ ((__exp__) == 0);  // apply mask
}
```

This ensures that only the data and ECC area is affected by masking.

---

## Integration with Encoding Pipeline

In `QRcode_encodeMask()` (from `qrencode.c`):

```c
QRcode *QRcode_encodeMask(QRinput *input, int mask)
{
    // ... setup ...

    // 1. Build frame with function patterns
    frame = QRspec_createFrame(version);

    // 2. Place data/ECC codewords via FrameFiller
    filler = FrameFiller_new(width, frame, 0);
    for(i = 0; i < raw->dataLength + raw->eccLength; i++) {
        code = QRraw_getCode(raw);
        bit = 0x80;
        for(j = 0; j < 8; j++) {
            p = FrameFiller_next(filler);
            if(p == NULL) goto EXIT;
            *p = 0x02 | ((bit & code) != 0);
            bit >>= 1;
        }
    }
    // ... remainder bits ...

    // 3. Apply mask
    if(mask < 0) {
        masked = Mask_mask(width, frame, input->level);
    } else {
        masked = Mask_makeMask(width, frame, mask, input->level);
    }

    // 4. Package result
    qrcode = QRcode_new(version, width, masked);
    // ...
}
```

The same flow applies for `QRcode_encodeMaskMQR()`, using `MMask_mask()` instead.