QR 코드에 바이너리 데이터 저장 (ZXING Java Library)

Question

내 Java 프로그램이 QR 코드를 통해 바이너리 페이로드를 보내야하지만 작동하지 않습니다. 여러 QR 코드 라이브러리와 많은 접근 방식을 시도했지만 모두이 문제가있는 것 같습니다. 내 현재 구현은 ZXING을 사용합니다.

문제는 내가 시도한 모든 Java 라이브러리가 String 페이로드에 초점을 맞춘 것처럼 보이며 이진 데이터에 대한 지원을 제공하지 않는다는 것입니다. 이에 대한 일반적인 제안 솔루션 은 바이너리 데이터를 Base64로 인코딩하는 것입니다. 그러나 내 데이터는 이미 QR 코드의 크기 제한에 가깝습니다. Base64 인코딩으로 인한 4 배 인플레이션으로 인해 데이터가 너무 큽니다. 나는 이미 페이로드의 크기를 줄이기 위해 상당한 노력을 기울였으며 현재는 새 줄로 구분 된 4 개의 문자 해시로 구성되어 있습니다. Java Deflator 클래스에 의해 모두 최대 수준 압축 내부. 더 작게 만들 수 없습니다.

데이터 인플레이션 오버 헤드를 최소화하면서 바이너리 데이터를 QR 코드에 저장하는 방법이 필요합니다.

Answer 1

저는 스토리지 효율성 손실이 -8 % 밖에되지 않는 솔루션을 개발했습니다. ZXING QR 코드 라이브러리의 내장 압축 최적화를 활용합니다.

설명

ZXING은 String 페이로드가 순전히 AlphaNumeric (자체 정의에 따라)인지 자동으로 감지하고, 그렇다면 2 개의 AlphaNumeric 문자를 11 비트로 자동 압축합니다. ZXING이 "영숫자"에 사용하는 정의는 모두 대문자, 0-9 및 몇 가지 특수 기호 ( '/', ':'등)입니다. 모두 정의하면 45 개의 가능한 값이 허용됩니다. 그런 다음이 Base45 숫자 중 2 개를 11 비트로 압축합니다.

45 진법의 2 자리는 2,025 개의 가능한 값입니다. 11 비트의 최대 저장 용량은 2,048 개의 가능한 상태입니다. 이는 원시 바이너리 뒤에있는 스토리지 효율성의 1.1 % 손실에 불과합니다.

  45 ^ 2 = 2,025
  2 ^ 11 = 2,048
  2,048 - 2,025 = 23
  23 / 2,048 = 0.01123046875 = 1.123%

그러나 이것은 이상적인 / 이론적 효율성입니다. 내 구현은 Long을 계산 버퍼로 사용하여 데이터를 청크로 처리합니다. 그러나 Java Long은 singed이므로 하위 7 바이트 만 사용할 수 있습니다. 전환 코드에는 지속적으로 양수 값이 필요합니다. 가장 높은 8 번째 바이트를 사용하면 부호 비트가 오염되고 임의로 음의 값이 생성됩니다.

실제 테스트 :

7 바이트 길이를 사용하여 임의 바이트의 2KB 버퍼를 인코딩하면 다음과 같은 결과를 얻을 수 있습니다.

  Raw Binary Size:        2,048
  Encoded String Size:    3,218
  QR Code Alphanum Size:  2,213 (after the QR Code compresses 2 base45 digits to 11 bits)

이는 실제 스토리지 효율성 손실이 8 %에 불과합니다.

  2,213 - 2,048 = 165
  165 / 2,048 = 0.08056640625 = 8.0566%

해결책

자체 포함 된 정적 유틸리티 클래스로 구현 했으므로 다음을 호출하기 만하면됩니다.

//Encode
final byte[] myBinaryData = ...;
final String encodedStr = BinaryToBase45Encoder.encodeToBase45QrPayload(myBinaryData);

//Decode
final byte[] decodedBytes = BinaryToBase45Encoder.decodeBase45QrPayload(encodedStr);

또는 InputStreams를 통해 수행 할 수도 있습니다.

//Encode
final InputStream in_1 = ... ;
final String encodedStr = BinaryToBase45Encoder.encodeToBase45QrPayload(in_1);

//Decode
final InputStream in_2 = ... ;
final byte[] decodedBytes = BinaryToBase45Encoder.decodeBase45QrPayload(in_2);

구현은 다음과 같습니다.

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * For some reason none of the Java QR Code libraries support binary payloads. At least, none that
 * I could find anyway. The commonly suggested workaround for this is to use Base64 encoding.
 * However, this results in a 4x payload size inflation. If your payload is already near the size
 * limit of QR codes, this is not possible.
 *
 * This class implements an encoder which takes advantage of a built-in compression optimization
 * of the ZXING QR Code library, to enable the storage of Binary data into a QR Code, with a
 * storage efficiency loss of only -8%.
 *
 * The built-in optimization is this: ZXING will automatically detect if your String payload is
 * purely AlphaNumeric (by their own definition), and if so, it will automatically compress 2
 * AlphaNumeric characters into 11 bits.
 *
 *
 * ----------------------
 *
 *
 * The included ALPHANUMERIC_TABLE is the conversion table used by the ZXING library as a reverse
 * index for determining if a given input data should be classified as alphanumeric.
 *
 * See:
 *
 *      com.google.zxing.qrcode.encoder.Encoder.chooseMode(String content, String encoding)
 *
 * which scans through the input string one character at a time and passes them to:
 *
 *      getAlphanumericCode(int code)
 *
 * in the same class, which uses that character as a numeric index into the the
 * ALPHANUMERIC_TABLE.
 *
 * If you examine the values, you'll notice that it ignores / disqualifies certain values, and
 * effectively converts the input into base 45 (0 -> 44; -1 is interpreted by the calling code
 * to mean a failure). This is confirmed in the function:
 *
 *      appendAlphanumericBytes(CharSequence content, BitArray bits)
 *
 * where they pack 2 of these base 45 digits into 11 bits. This presents us with an opportunity.
 * If we can take our data, and convert it into a compatible base 45 alphanumeric representation,
 * then the QR Encoder will automatically pack that data into sub-byte chunks.
 *
 * 2 digits in base 45 is 2,025 possible values. 11 bits has a maximum storage capacity of 2,048
 * possible states. This is only a loss of 1.1% in storage efficiency behind raw binary.
 *
 *      45 ^ 2 = 2,025
 *      2 ^ 11 = 2,048
 *      2,048 - 2,025 = 23
 *      23 / 2,048 = 0.01123046875 = 1.123%
 *
 * However, this is the ideal / theoretical efficiency. This implementation processes data in
 * chunks, using a Long as a computational buffer. However, since Java Long's are singed, we
 * can only use the lower 7 bytes. The conversion code requires continuously positive values;
 * using the highest 8th byte would contaminate the sign bit and randomly produce negative
 * values.
 *
 *
 * Real-World Test:
 *
 * Using a 7 byte Long to encode a 2KB buffer of random bytes, we get the following results.
 *
 *      Raw Binary Size:        2,048
 *      Encoded String Size:    3,218
 *      QR Code Alphanum Size:  2,213 (after the QR Code compresses 2 base45 digits to 11 bits)
 *
 * This is a real-world storage efficiency loss of only 8%.
 *
 *      2,213 - 2,048 = 165
 *      165 / 2,048 = 0.08056640625 = 8.0566%
 */
public class BinaryToBase45Encoder {
    public final static int[] ALPHANUMERIC_TABLE;

    /*
     * You could probably just copy & paste the array literal from the ZXING source code; it's only
     * an array definition. But I was unsure of the licensing issues with posting it on the internet,
     * so I did it this way.
     */
    static {
        final Field SOURCE_ALPHANUMERIC_TABLE;
        int[] tmp;

        //Copy lookup table from ZXING Encoder class
        try {
            SOURCE_ALPHANUMERIC_TABLE = com.google.zxing.qrcode.encoder.Encoder.class.getDeclaredField("ALPHANUMERIC_TABLE");
            SOURCE_ALPHANUMERIC_TABLE.setAccessible(true);
            tmp = (int[]) SOURCE_ALPHANUMERIC_TABLE.get(null);
        } catch (NoSuchFieldException e) {
            e.printStackTrace();//Shouldn't happen
            tmp = null;
        } catch (IllegalAccessException e) {
            e.printStackTrace();//Shouldn't happen
            tmp = null;
        }

        //Store
        ALPHANUMERIC_TABLE = tmp;
    }

    public static final int NUM_DISTINCT_ALPHANUM_VALUES = 45;
    public static final char[] alphaNumReverseIndex = new char[NUM_DISTINCT_ALPHANUM_VALUES];

    static {
        //Build AlphaNum Index
        final int len = ALPHANUMERIC_TABLE.length;
        for (int x = 0; x < len; x++) {
            // The base45 result which the alphanum lookup table produces.
            // i.e. the base45 digit value which String characters are
            // converted into.
            //
            // We use this value to build a reverse lookup table to find
            // the String character we have to send to the encoder, to
            // make it produce the given base45 digit value.
            final int base45DigitValue = ALPHANUMERIC_TABLE[x];

            //Ignore the -1 records
            if (base45DigitValue > -1) {
                //The index into the lookup table which produces the given base45 digit value.
                //
                //i.e. to produce a base45 digit with the numeric value in base45DigitValue, we need
                //to send the Encoder a String character with the numeric value in x.
                alphaNumReverseIndex[base45DigitValue] = (char) x;
            }
        }
    }

    /*
     * The storage capacity of one digit in the number system; i.e. the maximum
     * possible number of distinct values which can be stored in 1 logical digit
     */
    public static final int QR_PAYLOAD_NUMERIC_BASE = NUM_DISTINCT_ALPHANUM_VALUES;

    /*
     * We can't use all 8 bytes, because the Long is signed, and the conversion math
     * requires consistently positive values. If we populated all 8 bytes, then the
     * last byte has the potential to contaminate the sign bit, and break the
     * conversion math. So, we only use the lower 7 bytes, and avoid this problem.
     */
    public static final int LONG_USABLE_BYTES = Long.BYTES - 1;

    //The following mapping was determined by brute-forcing -1 Long (all bits 1), and compressing to base45 until it hit zero.
    public static final int[] BINARY_TO_BASE45_DIGIT_COUNT_CONVERSION = new int[] {0,2,3,5,6,8,9,11,12};
    public static final int NUM_BASE45_DIGITS_PER_LONG = BINARY_TO_BASE45_DIGIT_COUNT_CONVERSION[LONG_USABLE_BYTES];
    public static final Map<Integer, Integer> BASE45_TO_BINARY_DIGIT_COUNT_CONVERSION = new HashMap<>();

    static {
        //Build Reverse Lookup
        int len = BINARY_TO_BASE45_DIGIT_COUNT_CONVERSION.length;
        for (int x=0; x<len; x++) {
            int numB45Digits = BINARY_TO_BASE45_DIGIT_COUNT_CONVERSION[x];
            BASE45_TO_BINARY_DIGIT_COUNT_CONVERSION.put(numB45Digits, x);
        }
    }

    public static String encodeToBase45QrPayload(final byte[] inputData) throws IOException {
        return encodeToBase45QrPayload(new ByteArrayInputStream(inputData));
    }

    public static String encodeToBase45QrPayload(final InputStream in) throws IOException {
        //Init conversion state vars
        final StringBuilder strOut = new StringBuilder();
        int data;
        long buf = 0;

        // Process all input data in chunks of size LONG.BYTES, this allows for economies of scale
        // so we can process more digits of arbitrary size before we hit the wall of the binary
        // chunk size in a power of 2, and have to transmit a sub-optimal chunk of the "crumbs"
        // left over; i.e. the slack space between where the multiples of QR_PAYLOAD_NUMERIC_BASE
        // and the powers of 2 don't quite line up.
        while(in.available() > 0) {
            //Fill buffer
            int numBytesStored = 0;
            while (numBytesStored < LONG_USABLE_BYTES && in.available() > 0) {
                //Read next byte
                data = in.read();

                //Push byte into buffer
                buf = (buf << 8) | data; //8 bits per byte

                //Increment
                numBytesStored++;
            }

            //Write out in lower base
            final StringBuilder outputChunkBuffer = new StringBuilder();
            final int numBase45Digits = BINARY_TO_BASE45_DIGIT_COUNT_CONVERSION[numBytesStored];
            int numB45DigitsProcessed = 0;
            while(numB45DigitsProcessed < numBase45Digits) {
                //Chunk out a digit
                final byte digit = (byte) (buf % QR_PAYLOAD_NUMERIC_BASE);

                //Drop digit data from buffer
                buf = buf / QR_PAYLOAD_NUMERIC_BASE;

                //Write Digit
                outputChunkBuffer.append(alphaNumReverseIndex[(int) digit]);

                //Track output digits
                numB45DigitsProcessed++;
            }

            /*
             * The way this code works, the processing output results in a First-In-Last-Out digit
             * reversal. So, we need to buffer the chunk output, and feed it to the OutputStream
             * backwards to correct this.
             *
             * We could probably get away with writing the bytes out in inverted order, and then
             * flipping them back on the decode side, but just to be safe, I'm always keeping
             * them in the proper order.
             */
            strOut.append(outputChunkBuffer.reverse().toString());
        }

        //Return
        return strOut.toString();
    }

    public static byte[] decodeBase45QrPayload(final String inputStr) throws IOException {
        //Prep for InputStream
        final byte[] buf = inputStr.getBytes();//Use the default encoding (the same encoding that the 'char' primitive uses)

        return decodeBase45QrPayload(new ByteArrayInputStream(buf));
    }

    public static byte[] decodeBase45QrPayload(final InputStream in) throws IOException {
        //Init conversion state vars
        final ByteArrayOutputStream out = new ByteArrayOutputStream();
        int data;
        long buf = 0;
        int x=0;

        // Process all input data in chunks of size LONG.BYTES, this allows for economies of scale
        // so we can process more digits of arbitrary size before we hit the wall of the binary
        // chunk size in a power of 2, and have to transmit a sub-optimal chunk of the "crumbs"
        // left over; i.e. the slack space between where the multiples of QR_PAYLOAD_NUMERIC_BASE
        // and the powers of 2 don't quite line up.
        while(in.available() > 0) {
            //Convert & Fill Buffer
            int numB45Digits = 0;
            while (numB45Digits < NUM_BASE45_DIGITS_PER_LONG && in.available() > 0) {
                //Read in next char
                char c = (char) in.read();

                //Translate back through lookup table
                int digit = ALPHANUMERIC_TABLE[(int) c];

                //Shift buffer up one digit to make room
                buf *= QR_PAYLOAD_NUMERIC_BASE;

                //Append next digit
                buf += digit;

                //Increment
                numB45Digits++;
            }

            //Write out in higher base
            final LinkedList<Byte> outputChunkBuffer = new LinkedList<>();
            final int numBytes = BASE45_TO_BINARY_DIGIT_COUNT_CONVERSION.get(numB45Digits);
            int numBytesProcessed = 0;
            while(numBytesProcessed < numBytes) {
                //Chunk out 1 byte
                final byte chunk = (byte) buf;

                //Shift buffer to next byte
                buf = buf >> 8; //8 bits per byte

                //Write byte to output
                //
                //Again, we need to invert the order of the bytes, so as we chunk them off, push
                //them onto a FILO stack; inverting their order.
                outputChunkBuffer.push(chunk);

                //Increment
                numBytesProcessed++;
            }

            //Write chunk buffer to output stream (in reverse order)
            while (outputChunkBuffer.size() > 0) {
                out.write(outputChunkBuffer.pop());
            }
        }

        //Return
        out.flush();
        out.close();
        return out.toByteArray();
    }
}

다음은 코드를 확인하기 위해 실행 한 몇 가지 테스트입니다.

@Test
public void stringEncodingTest() throws IOException {
    //Init test data
    final String testStr = "Some cool input data! !@#$%^&*()_+";

    //Encode
    final String encodedStr = BinaryToBase45Encoder.encodeToBase45QrPayload(testStr.getBytes("UTF-8"));

    //Decode
    final byte[] decodedBytes = BinaryToBase45Encoder.decodeBase45QrPayload(encodedStr);
    final String decodedStr = new String(decodedBytes, "UTF-8");

    //Output
    final boolean matches = testStr.equals(decodedStr);
    assert(matches);
    System.out.println("They match!");
}

@Test
public void binaryEncodingAccuracyTest() throws IOException {
    //Init test data
    final int maxBytes = 10_000;
    for (int x=1; x<=maxBytes; x++) {
        System.out.print("x: " + x + "\t");

        //Encode
        final byte[] inputArray = getTestBytes(x);
        final String encodedStr = BinaryToBase45Encoder.encodeToBase45QrPayload(inputArray);

        //Decode
        final byte[] decodedBytes = BinaryToBase45Encoder.decodeBase45QrPayload(encodedStr);

        //Output
        for (int y=0; y<x; y++) {
            assertEquals(inputArray[y], decodedBytes[y]);
        }
        System.out.println("Passed!");
    }
}

@Test
public void binaryEncodingEfficiencyTest() throws IOException, WriterException, NoSuchMethodException, InvocationTargetException, IllegalAccessException {
    //Init test data
    final byte[] inputData = new byte[2048];
    new Random().nextBytes(inputData);

    //Encode
    final String encodedStr = BinaryToBase45Encoder.encodeToBase45QrPayload(inputData);

    //Write to QR Code Encoder // Have to use Reflection to force access, since the function is not public.
    final BitArray qrCode = new BitArray();
    final Method appendAlphanumericBytes = com.google.zxing.qrcode.encoder.Encoder.class.getDeclaredMethod("appendAlphanumericBytes", CharSequence.class, BitArray.class);
    appendAlphanumericBytes.setAccessible(true);
    appendAlphanumericBytes.invoke(null, encodedStr, qrCode);

    //Output
    final int origSize = inputData.length;
    final int qrSize = qrCode.getSizeInBytes();
    System.out.println("Raw Binary Size:\t\t" + origSize + "\nEncoded String Size:\t" + encodedStr.length() + "\nQR Code Alphanum Size:\t" + qrSize);

    //Calculate Storage Efficiency Loss
    final int delta = origSize - qrSize;
    final double efficiency = ((double) delta) / origSize;
    System.out.println("Storage Efficiency Loss: " + String.format("%.3f", efficiency * 100) + "%");
}

public static byte[] getTestBytes(int numBytes) {
    final Random rand = new Random();
    final ByteArrayOutputStream bos = new ByteArrayOutputStream();
    for (int x=0; x<numBytes; x++) {
        //bos.write(255);// -1 (byte) = 255 (int) = 1111 1111

        byte b = (byte) rand.nextInt();
        bos.write(b);
    }
    return bos.toByteArray();
}