Effective QR-code compression

Intro

In the previous article, I described how to extract a QR code from the following message:

{
    "n0": 7,
    "x": 21,
    "c": "AcO9w7fDuCDCoMOdKXbDqkvCt11dwoLCqg/DtV/DgCwBF1/CksKVwqfCiwvDrALDtcKfeQcAw6vDv8O0E8Kgwp/Dg3Vyw6vCpMKmw503Mghkw7/Dk8Kl"
}

The Origin

This message is generated by the service qrshare.io, which serves well in the following cases:

1. Transferring a file from a desktop to a mobile.
2. Sharing a file with multiple recipients (e.g., presentations, lecture materials).
3. Sharing a file during an online meeting, especially on Google Meet calls, using this Chrome Extension.

Explanation of the Format

But why is the QR code data transferred in such a strange format in the first place? This is the logic behind using such a format:

• A QR code is a square matrix of zeroes and ones, which can be represented as a one-dimensional array.
• The array of 0s and 1s can be split into groups of 8 elements, each representing one byte. This significantly reduces the amount of data to be sent over the network.
• The array should be padded with leading zeros so that its length is divisible by 8.
• Since JSON is a text-based format and the string obtained in the previous steps is binary, it has to be base64 encoded.

The Code

The code below takes a string as input and produces that magically ciphered QR code, where:

• n0 - the number of leading zeroes that should be removed before restoring the matrix.
• x - the side length of the square matrix.
• c - the base64-encoded binary string representing the sequence of 0s and 1s.

import com.google.zxing.EncodeHintType;
import com.google.zxing.qrcode.decoder.ErrorCorrectionLevel;
import com.google.zxing.qrcode.encoder.Encoder;
import lombok.SneakyThrows;

import java.nio.charset.StandardCharsets;
import java.util.Base64;
import java.util.Map;

public class QRCodeGenerator {

    public static int[] toBinary(int c) {
        if (c < 0 || c > 255) {
            throw new IllegalArgumentException("Input should be withing the range [0, 255], got: " + c);
        }

        int[] bits = new int[8];
        int i = 7;
        while (c > 0) {
            bits[i--] = c & 0x1;
            c = c >> 1;
        }
        return bits;
    }

    private static char oneCharFromBinary(int[] eightBits) {
        int code = 0;
        for (int i = 7; i >= 0; i--) {
            code += eightBits[i] * (1 << (7 - i));
        }
        return (char) code;
    }

    private static String stringFromBinary(int[] bits) {
        if (bits.length % 8 != 0) {
            throw new IllegalArgumentException("Number of bits should be divisible by 8");
        }
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < bits.length; i += 8) {
            int[] charBits = new int[8];
            System.arraycopy(bits, i, charBits, 0, 8);
            str.append(oneCharFromBinary(charBits));
        }
        return str.toString();
    }

    @SneakyThrows
    public static QR encode(String data) {
        if (data == null || data.length() == 0) {
            throw new IllegalArgumentException("Data is empty");
        }
        var hints = Map.of(EncodeHintType.CHARACTER_SET, "UTF-8");
        var qrCode = Encoder.encode(data, ErrorCorrectionLevel.M, hints);
        var m = qrCode.getMatrix();
        var size = m.getWidth() * m.getHeight();
        var zeroesCount = size % 8 == 0 ? 0 : (8 - (size % 8));

        var bits = new int[size + zeroesCount];

        int i = 0;
        for (int y = 0; y < m.getHeight(); y++) {
            for (int x = 0; x < m.getWidth(); x++) {
                bits[(i++) + zeroesCount] = m.get(x, y);
            }
        }

        var rawCode = stringFromBinary(bits);
        var code = Base64.getEncoder().encodeToString(rawCode.getBytes(StandardCharsets.UTF_8));

        return new QR(zeroesCount, m.getWidth(), code);
    }

    // used for testing encoded
    public static int[][] decode(QR qr) {
        var decoded = new String(Base64.getDecoder().decode(qr.code), StandardCharsets.UTF_8);
        var data = decoded.toCharArray();

        var bits = new int[data.length * 8];
        for (int i = 0; i < data.length; i++) {
            var byteBits = toBinary(data[i]);
            System.arraycopy(byteBits, 0, bits, i * 8, 8);
        }

        var matrix = new int[qr.size][qr.size];
        int i = qr.zeroesCount;
        for (int y = 0; y < qr.size; y++) {
            for (int x = 0; x < qr.size; x++) {
                matrix[y][x] = bits[i++];
            }
        }
        return matrix;
    }

    public record QR(int zeroesCount, int size, String code) {
    }
}

The code uses the zxing library for generating QR codes.

Thanks for reading this far!
Try sharing a file with qrshare.io or use the Chrome Extension!

Next time, we'll discuss how to create that beautiful animation when the code is generated. Stay tuned!