C语言版QR二维码算法

#include <stdio.h> //for printf #include <stdint.h> //for int16_t #include <string.h> //for strlen #include <stdlib.h> //for malloc, free #include "qr.h" #include "png_create.h" //for png_create void printArrayBYTEwithOffset(char* info, uint16_t length, unsigned char data[], unsigned char offset) { uint16_t i; printf("[size=%d] %s", length, info); printf("\n\tBYTE "); for (i = 0; i < length; i++) { printf(">%02x", data[i+offset]); if ((i+1) % 32 != 0) printf(","); if ((i+1) % 32 == 0) printf("\n\tBYTE "); } printf("\n"); } void printArrayBYTE(char* info, uint16_t length, unsigned char data[]) { printArrayBYTEwithOffset(info, length, data, 0); } //----------------------------------------------------------------------------------------------------------------- // Reed-Solomon error corretion looks very scary on th Thonky.com website, but after reading pages and pages of their examples and explanations, // it turns out the entire algorithm could be reduced to some relatively simple loops after quite a bit of trial-and-error. void reedSolomon(int16_t data_codewords, int16_t data_offset, unsigned char message[], int16_t error_codewords, unsigned char errorcode[], unsigned char generator[]) { int16_t i=0; int16_t j=0; for (i=0; i < data_codewords; i++) errorcode[i] = message[i + data_offset]; for (i=data_codewords; i < error_codewords; i++) // if error codewords > data codewords, need to initialize enough zeros for the math errorcode[i] = 0; //printArrayBYTE("init: ", error_codewords, errorcode); for (j=1; j <= data_codewords; j++) { int16_t lead_term = a_inv[errorcode[0]]; if (errorcode[0] != 0) { for (i=1; i <= error_codewords; i++) { unsigned char temp_value = 0; if (i < error_codewords) temp_value = errorcode[i]; errorcode[i-1] = temp_value ^ a[(generator[i-1] + lead_term) % 255]; } } else { // polynomial division step is greatly simiplified (just a shift of all terms left) if leading coeff. is zero for (i=1; i <= error_codewords; i++) errorcode[i-1] = errorcode[i]; } for ( i=error_codewords+1; i <= data_codewords; i++) { errorcode[i-1] = errorcode[i]; } //printArrayBYTE("iter: ", error_codewords, errorcode); } } //----------------------------------------------------------------------------------------------------------------- int is_mask_applicable(int16_t row, int16_t column, unsigned char mask_number) { switch (mask_number) { case 0: return ((row + column) % 2 == 0); case 1: return ((row % 2) == 0); case 2: return ((column % 3) == 0); case 3: return ((row + column) % 3 == 0); case 4: return ((((row / 2) + (column / 3)) % 2) == 0); //double check floor case 5: return ((((row * column) % 2) + ((row * column) % 3)) == 0); case 6: return ((((row * column) % 2) + ((row * column) % 3)) % 2 == 0); case 7: return ((((row + column) % 2) + ((row * column) % 3)) % 2 == 0); } return 0; } int parseMessage(unsigned char **imageTmp,char* freetext) { //FILE *fp; int16_t i=0; int16_t j=0; int16_t qr_version = -1; unsigned char message[1666] = {0}; // 244 valid up to VERSION 13-Q, 1666 valid up to VERSION 40-Q int16_t message_length = strlen(freetext); unsigned char* message_parameters=NULL; int16_t error_codewords = 0; int message_index = 0; int16_t total_blocks=0; unsigned char errorcode[30] = {0}; // 30 is highest EC count for Q-quality; 25 is highest dataword count for Q-quality unsigned char interleaved_output[3706] = {0}; // 532 valid up to VERSION 13-Q; 3706 valid up to VERSION 40-Q int16_t message_offset = 0; int16_t block_number = 0; int16_t groups=0; int16_t blocks=0; int16_t interleaved_output_offset =0; int16_t max_pixels = (qr_version*4)+21; int16_t output_size = 0; unsigned char **image=0; int imageWidth=0; int ii=0; int16_t finder_pattern =0; int16_t k=0; unsigned char mask_number =0; int16_t y =0; int16_t x = 0; int16_t dir = -1; int16_t primary_bits = 0; int16_t remainder_bits = 0; unsigned char working_byte = 0; int16_t interleaved_index = -1; // printf("INFO: message=[%s]\n", freetext); // printf("INFO: len of message=%d\n", message_length); //printArrayBYTE("unencoded input", message_length, (unsigned char*)&freetext[0]); for (i=0; i < 40; i++) { int16_t capacity = codeword_parameters[i][1]*codeword_parameters[i][2] + codeword_parameters[i][3]*codeword_parameters[i][4] - 2; if (i > 8) capacity--; //subtract one extra byte because of switch to 16-bit length byte in QR Version 10+ // printf("qr ver=%d capacity=%d\n", i+1, capacity); if (message_length <= capacity) { qr_version = i; printf("INFO: selected QR Version %d\n", qr_version+1); break; } } if (qr_version < 0) { printf("ERROR: Unable to find QR version capable of encoding input message. Sorry, try again.\n"); return 0; } message_parameters = codeword_parameters[qr_version]; message_index = 0; message[message_index] = 64; // "0100" Byte Encoding if (qr_version > 8) { // QR Verisons 10+ for Byte data encoding represent length as 16-bits message_index++; message[message_index++] = ((message_length & 5888) >> 4) | ((message_length & 240) >> 4); } else { // QR Verisons 1 through 9 for Byte data encoding represent length as 8-bits message[message_index++] |= ((message_length & 240) >> 4); } message[message_index++] = ((message_length & 15) << 4) | ((freetext[0] & 240) >> 4); for (i=0; i < message_length; i++) message[message_index++] = ((freetext[i] & 15) << 4) | ((freetext[i+1] & 240) >> 4); { unsigned char pad[] = {236, 17}; uint16_t pad_index = 0; uint16_t needed_pad_bytes = (message_parameters[1] * message_parameters[2]) + (message_parameters[3] * message_parameters[4]) - message_index; printf("INFO: needed pad bytes: %d\n", needed_pad_bytes); for ( i=0; i < needed_pad_bytes; i++) { message[message_index++] = pad[pad_index]; pad_index ^= 1; } } //printArrayBYTE("encoded input (with padding)", message_index, message); error_codewords = message_parameters[0]; total_blocks = message_parameters[1] + message_parameters[3]; message_offset = 0; block_number = 0; for (groups=0; groups < 2; groups++) { int16_t num_blocks = message_parameters[groups*2+1]; int16_t data_codewords = message_parameters[groups*2+2]; for (blocks=0; blocks < num_blocks; blocks++) { reedSolomon(data_codewords, message_offset, message, error_codewords, errorcode, &gen_poly[gen_offset[message_parameters[0]-13]]); //printf("REED OUTPUT: data_codewords=%d, message_offset=%d, error_codewords=%d, gen_offset=%d\n", data_codewords, message_offset, error_codewords, gen_offset[message_parameters[0]-13]); //printArrayBYTEwithOffset("Data Codewords: ", data_codewords, message, message_offset); //printArrayBYTE("Error Codewords: ", error_codewords, errorcode); interleaved_output_offset = block_number; for ( i=0; i < data_codewords; i++) { interleaved_output[interleaved_output_offset] = message[i + message_offset]; if (i+1 < message_parameters[2]) // { 18, 2, 15, 2, 16} interleaved_output_offset += message_parameters[1]; if (i+1 < message_parameters[4]) interleaved_output_offset += message_parameters[3]; } interleaved_output_offset = message_parameters[1] * message_parameters[2] + message_parameters[3] * message_parameters[4] + block_number; for (i=0; i < error_codewords; i++) { interleaved_output[interleaved_output_offset] = errorcode[i]; interleaved_output_offset += total_blocks; } message_offset += data_codewords; block_number++; } //printArrayBYTE("output: ", 346, interleaved_output); } output_size = (message_parameters[1] * message_parameters[2]) + (message_parameters[3] * message_parameter