#347 Wasteful encoding of AZTEC symbols reduces capacity by 25% for random data

[Francois Grieu]

With zint-2.16.0, for some kind of data, including sequences of random bytes, the encoding used in AZTEC symbols often eats 35% more bits than necessary, reducing the symbol capacity by >25%.
For example, with the default level of compression, ZINT most often fails to encode 1430 random bytes, when the limit should be like 1910 random bytes. Here is a 1359-byte failing example that should pass:

zint --barcode=AZTEC --binary --esc --data=\xbd\x3e\x3e\x61\xfb\x2d\x37\x44\x7c\xe8\x67\xa8\x29\x35\x5e\x6c\x0e\xf3\x92\x51\x18\xa0\xf6\x59\xd4\xcd\xf1\x92\xb6\x35\x7f\x77\x8c\x6b\xf9\xd0\x9a\x71\x2b\xf1\xf5\x3e\x37\x60\x57\xe2\x6c\x68\x94\xee\xca\xca\xae\xda\x81\x0b\xfb\x39\xc8\x1d\xaf\x19\x2b\x41\xbb\xc3\x3d\x8b\xb9\xfa\x7b\x85\x21\x06\x29\x79\xf9\xb4\x16\xc7\x63\x8a\x64\x3e\x94\xc9\x89\x03\xe2\xd9\xa5\xee\xb6\x79\xd1\x1e\x04\xa1\x7c\xdb\x9c\xed\x2e\xe7\x8c\x43\xb1\x66\xed\xc0\x12\x7b\x78\x17\xf6\x90\x11\x98\x06\x4d\xf2\x3e\x90\x0e\xf8\x99\xc1\x04\x56\x69\xc2\x6e\x02\x9a\xbd\x81\x8c\xe0\x4c\xe6\x9c\x43\x05\x82\x63\xf2\x58\xf2\xba\x3c\xfb\xe8\x9e\xe9\xba\x2d\x56\xd8\x6a\xbc\x0c\x8a\x07\xf7\x0a\xc6\x9a\x25\x10\x79\xe9\x9b\x61\xd2\xd4\x70\x40\x66\x95\x0f\x36\xf3\x2e\xa9\x4d\x6c\xd6\x11\x45\x93\x58\x6a\xbc\x06\x2e\xd7\xfe\xb7\xce\x24\x63\x86\xe0\x67\xc7\x14\xf5\x05\xab\x83\x30\x78\x31\x95\xc5\x6a\x59\xd3\x53\x8b\x5f\x7e\x30\x4d\x70\x02\x62\x46\xdd\xfc\x66\xf6\x0e\xef\xec\x4a\x6a\xaa\xee\x8f\x0d\x88\x3d\x03\x2a\x37\x90\xb6\x1f\x74\x15\x3f\x3d\xbe\xdd\xc8\xa6\x43\x74\xdb\x29\x64\xee\xd9\xf7\xcb\x31\x16\xfe\x74\x60\x95\xcf\xe4\x50\x6c\x3d\xf1\x89\xc4\x12\x30\x35\x1e\x21\x29\x7e\x98\x73\x06\xd1\x66\x6a\x73\x5c\x66\xdd\xae\x7c\x43\x7c\x8a\xa3\x2d\xc9\xf6\x67\x3c\x89\x8d\x64\x3b\x82\xad\xdb\x2c\xbb\x95\xce\xc9\xba\x51\x21\xa6\xf7\x0a\xea\x49\x8b\x35\xa0\x11\xc1\x07\xd2\x8f\x0a\x24\x10\x8c\x19\x68\x49\x0e\x34\xee\x5a\xb4\x8e\x52\xf8\x83\x47\x83\x2e\x49\xc3\x8f\xb1\x06\x97\x8c\xa5\x1f\xe9\x24\x86\x39\x03\xb9\xba\x64\x0c\xcb\x2a\x8e\xf4\x0c\x68\xec\x46\xa7\x03\x13\xb5\x54\xed\x51\xb6\x1d\x92\xaa\x67\x78\x90\x4b\xea\xdf\x6d\xa1\x3f\x64\x2d\xef\x69\x9b\xf3\x12\x1c\xbe\xcb\xd3\xda\x3e\xec\x11\xda\x31\xba\xd6\xf7\xef\x76\xa3\xc6\x38\x49\x8a\xa3\xd7\x21\xea\x44\x6a\x9c\x0c\x11\x33\x57\x27\xd9\xc1\x6c\x3a\xe5\xe0\x2e\x04\xfd\xfd\x18\x3e\x81\x7d\x92\x72\xd2\xaf\x85\xdd\xca\x5e\x81\x21\x57\x62\x48\xae\x06\x05\x3e\x30\xe9\x3a\xe5\x7a\x08\xc3\x2b\x83\x33\x2a\x02\xde\x26\x65\xc6\x95\x54\x72\xd5\x9c\x36\x7f\x4c\x06\x39\xe2\x13\x22\x7a\xc8\x86\x41\xa3\x56\x1b\x1c\x42\x90\xf2\x08\x17\xf5\x9e\x5d\xbd\x06\x37\x8e\x60\x57\x12\x57\x29\xc4\x3e\xee\x2b\xdd\xd3\xc9\xf3\xef\xab\x7b\x05\x6a\x9e\x44\xfe\xea\x9b\x1d\xe1\xd4\x3a\xe2\xc3\xec\xdf\x54\x7c\x36\x34\x0b\xaa\x2f\x1e\xfa\xc3\xd6\x54\x02\xf8\xe7\x9b\x9b\xa9\xf0\x71\x52\xcd\x67\xf1\x94\xa2\xf8\x6d\x4b\x4f\x38\x22\xe5\xda\x99\xbf\x8b\x3f\xa2\x5f\x54\x33\x93\xbc\xa7\x97\x1d\xb0\xd2\x91\x3a\x86\xd0\x88\x68\x55\x1b\x32\xda\x76\xfa\x2c\x55\x97\xc6\xaf\x4d\x9f\x22\x65\x6b\xb6\x6b\x76\x1a\x55\x6d\xfc\xd3\x52\xaf\x1c\x8f\x1c\xc5\x08\x9d\xb5\x3d\x8d\x3b\x81\x06\xfc\xd7\x25\x84\xb5\x58\xfa\xae\x16\x58\x42\x40\xef\x79\x07\x1b\x45\x9d\x3d\x84\x29\x2e\x7a\x4d\x96\x5e\xd7\xbd\xf4\x7f\x12\x75\xf1\x76\x1a\x92\x35\x95\x88\x65\x66\x3c\x0b\x33\xaa\x13\x90\xf4\x0a\xe9\x82\x36\x04\x58\xc1\x12\x44\x27\x0e\x8e\xdf\x7d\x59\x07\x75\x4a\x23\x0c\x18\x91\x12\x18\x8c\x8d\xe5\x43\x25\x2a\x81\xbe\x0e\x5a\x45\xcc\x24\x7e\x9c\x8c\x97\x35\x76\x88\xb8\x49\xf4\x57\xd2\x12\xec\xac\x60\x95\xca\x05\xc6\x87\x38\xe9\x4c\x67\x50\xef\x95\x43\xcb\x46\x6d\x7a\x7e\x44\x3e\xf4\x14\x57\xd3\x68\xd1\x57\x15\x85\x72\x87\x69\x9f\x37\x18\xa7\x39\x56\x15\x64\xb4\x95\xf2\xf5\x22\x9f\x48\x19\x1b\xb3\x59\xf4\xd0\x2b\x83\x43\xa5\xf6\xd9\xad\x38\x11\xa8\x54\xa8\x79\x31\x01\x16\x37\x77\x30\x68\xaf\xb4\xb9\xf6\xb3\xac\xa5\x1c\x96\x6b\xac\x11\xd2\x55\xe1\x36\xc7\x01\x27\x9d\xde\x1c\x59\x2f\x3a\x37\x60\x74\x0a\x4e\xde\xe4\x26\x05\x71\x30\x40\x25\xcb\x47\xb9\xb4\x67\x23\xd4\xc5\x7e\x64\xd8\x4b\xce\x56\xa9\xbe\x94\x37\x9a\x66\x20\x60\xa5\x50\x2c\x75\x49\x0a\x1c\x49\xb6\x86\xb0\x73\xa1\x47\x39\x80\x69\xbd\x2c\x29\x2d\x9a\x04\x96\x40\xfc\x3c\xfc\x58\xf0\x65\x52\xa2\xaf\xfd\x5c\xc1\xbf\xde\xf2\xc0\x06\x2d\x2f\x33\x6b\x4a\xb7\x1e\x85\xc2\xf0\x85\xd3\x2a\xb8\xa2\xc3\x35\xca\xb0\x10\x65\x21\x10\xd3\x6d\x8c\x92\x8f\x7b\xb5\xf3\x32\xbf\x04\x0f\x76\x93\xaa\x68\x8d\xa3\x17\x44\x23\x4f\x1c\x14\x76\x45\x2e\x6c\x25\xdd\x77\x1f\x0c\xf2\xd8\x51\x92\xdc\x39\x40\x60\xf1\x84\xe3\xc2\xba\x3d\x89\x8b\xc2\x6a\xef\xf8\x77\x1a\x32\xca\x58\x92\x2c\xd9\x66\x27\x41\x4c\xb1\xaf\x34\xc7\xa3\x8c\xef\x4f\xbd\xac\xcf\x41\xed\xf3\x65\x32\x3d\xf0\x06\x41\x36\xad\x8d\x77\xf6\x78\xe9\x63\xaa\x06\xbe\xdd\xf4\xf5\x14\x66\x3c\x46\x13\xee\xd8\x0a\x04\x74\xbd\x3b\x2e\xef\xf0\xe3\xe4\x43\x7b\xf6\xa2\x5b\xbe\xb1\xbf\x92\xe3\xf5\x58\x43\xaf\x7c\xa1\x1e\x09\x47\x6a\xbd\xf8\x1c\x8b\x4e\x82\xaa\xa1\x36\x0e\x58\xaa\xce\x58\xca\x15\x93\xa3\xd0\x05\x9f\x89\xa2\xbc\xdc\x2b\x62\xd6\x89\x02\xb9\xa8\x77\x95\x7f\x31\x96\x7f\xd4\x72\x58\xbe\xb7\x02\x63\x55\x05\x18\x53\xeb\x21\x20\x8d\x3e\x7a\xf0\x4a\xb3\xcb\x20\x2d\x0b\xc2\x9f\x36\x08\x8d\x62\x50\xac\xed\xa1\xea\x60\x13\x68\xe9\x3b\xc0\xca\x3c\xb4\x44\x5e\xfe\x35\xfc\xd2\x28\x22\xee\xbd\x63\xba\xe5\x13\x3a\xf9\xb9\x90\x24\x1e\xc8\xba\x7a\x79\x51\x28\x83\x57\xcf\x3b\x50\x0b\x16\xbc\xb3\xec\xe4\xac\xf3\xbf\xa1\xfc\xf4\x34\xb2\xf9\x2d\x1a\xc6\xee\x0f\x75\x69\x78\x3d\x5a\x80\xd0\xa2\x47\x92\xc5\xf0\x41\x90\x90\xf5\x6d\xe8\xc8\x9f\x23\xf1\x2f\x28\x41\xf5\xae\x57\x8c\x2e\x98\xdd\x83\x5c\xd2\xf6\xd1\x5b\x6b\x96\xee\x4f\x65\xab\x02\x79\x01\x02\xc4\xd8\x60\xeb\x85\x74\x0e\x93\xf7\xee\x25\xba\x0b\xd8\xcc\xf6\x16\x95\x33\xbc\xd9\xe7\x55\x1c\xa3\x57\x8f\xde\x6a\x26\x26\x24\x93\x94\x4e\x85\x04\x2f\x40\x71\x44\x62\x0a\x9f\x2c\xcd\x6c\x66\xc3\x0b\x03\x36\xf4\xfe\x3d\x1d\x17\x30\x8b\x03\x25\xaa\x8f\x7c\x21\xd6\xfd\xa5\x2b\x4e\xc7\x48\x52\xdb\xa8\xde\x59\x64\x11\xb3\x32\x70\x98\x60\x12\x52\x1b\x39\xc2\xc3\x17\xd3\xd1\x40\x6c\x4b\x24\x57\x18
Error 707: Input too long for ECC level 2, requires too many codewords (maximum 1279)

The problem mostly lies in function aztec_text_process of file aztec.c, which fails to use mode 'B' (binary) when that would be the most compact encoding method for the data segment. It's relatively easy to modify this code to use mode 'B' for the whole segment when that's more compact than what's achieved by the current code, but unfortunately that would still give poor density for data that's partially random (e.g. 200 random digits followed by 1800 random bytes). An algorithm even close to optimal is non-trivial.

As an aside: a sequence of up to 1915 bytes all 0xAA is encoded with the default error correction level, when that limit should be 1914. The reason is an incorrect rounding mode when computing the minimum number of symbols devoted to error correction: that should be S×P/100+3 rounding UP (as implied by the wording and example in ISO 24778), where S is the total number of symbols and P is a percentage of spares.

Note:assuming that later issue corrected, 1914 random bytes will sometime not be encodable with the default error correction level, due to insertion of dummy bits. However 1914 random bytes all in 0x01..0xFE should be always encodable.

[Git Lost]

Re optimal encodation, yes, this has been on the to-do list, will see what I do over the coming week or so.

Re error correction, thanks for pointing that out, will adjust the calculations.

[Git Lost]

Re error correction, adjusted with commit [0efc4f].

[Git Lost]

Re encodation, almost optimal algorithm added with commit [bcb3ce].