/*
二维码编码
二维码生成原理详见 http://coolshell.cn/articles/10590.html#jtss-tsina
蒋晓岗<kerndev@foxmail.com>
*/
#include <stddef.h>
#include <string.h>
#include "rscode.h"
#include "qrencode.h"

#define MAX_CODE_WORD   292  //最大码字容量
#define MAX_DATA_CODE   232  //最大数据码字
#define MAX_RSEC_CODE   146  //最大纠错码字
#define MAX_QRCODE_SIZE 53   //最大矩阵大小(版本9)

typedef struct
{
	unsigned short version;		          //版本1~40
	unsigned short code_word_count; 	  //码字总数=数据码字+纠错码字
	unsigned short data_code_count;	      //数据码字
	unsigned short align_point_count;	  //P61 表E1 校正图形 个数
	unsigned short align_point[6];	      //P61 表E1 校正图形	行列坐标
	unsigned short rsec_block;		      //纠错块数
	unsigned short rsec_block_code_count; //分块码字总数
	unsigned short rsec_block_data_count; //分块数据码数
} qrcode_info_t;

//P28 表9 QR码符号各版本的参数
static const qrcode_info_t m_qrcode_info[] = 
{
	{0},
	{1,  26,  19, 0,   0,   0,   0,   0,   0,   0, 1,  26,  19},
	{2,  44,  34, 1,  18,   0,   0,   0,   0,   0, 1,  44,  34},
	{3,  70,  55, 1,  22,   0,   0,   0,   0,   0, 1,  70,  55},
	{4, 100,  80, 1,  26,   0,   0,   0,   0,   0, 1, 100,  80},
	{5, 134, 108, 1,  30,   0,   0,   0,   0,   0, 1, 134, 108},
	{6, 172, 136, 1,  34,   0,   0,   0,   0,   0, 2,  86,  68},
	{7, 196, 156, 2,  22,  38,   0,   0,   0,   0, 2,  98,  78},
	{8, 242, 194, 2,  24,  42,   0,   0,   0,   0, 2, 121,  97},
	{9, 292, 232, 2,  26,  46,   0,   0,   0,   0, 2, 146, 116}
};

static unsigned char m_data_code[MAX_DATA_CODE];
static unsigned char m_rsec_code[MAX_RSEC_CODE];
static unsigned char m_code_word[MAX_CODE_WORD];
static int           m_qrcode_size;
static unsigned char m_qrcode_data[MAX_QRCODE_SIZE][MAX_QRCODE_SIZE];

//设置定位图案（Position Detection Pattern）
//3个大回字，是定位图案，用于标记二维码的矩形大小。
static void set_postion_pattern(int x, int y)
{
	const unsigned char pattern[] = {0x7f,0x41,0x5d,0x5d,0x5d,0x41,0x7f};
	int i, j;
	for (i = 0; i < 7; i++)
	{
		for (j = 0; j < 7; j++)
		{
			m_qrcode_data[x + j][y + i] = (pattern[i] & (1 << (6 - j))) ? 0x30 : 0x20;
		}
	}
}

//设置定位图案的分隔线(Separators for Postion Detection Patterns)
static void set_separator_pattern(void)
{
	int i;
	for (i = 0; i < 8; i++)
	{
		m_qrcode_data[i][7] = m_qrcode_data[7][i] = 0x20;
		m_qrcode_data[m_qrcode_size - 8][i] = m_qrcode_data[m_qrcode_size - 8 + i][7] = 0x20;
		m_qrcode_data[i][m_qrcode_size - 8] = m_qrcode_data[7][m_qrcode_size - 8 + i] = 0x20;
	}
	for (i = 0; i < 9; i++)
	{
		m_qrcode_data[i][8] = m_qrcode_data[8][i] = 0x20;
	}
	for (i = 0; i < 8; i++)
	{
		m_qrcode_data[m_qrcode_size - 8 + i][8] = m_qrcode_data[8][m_qrcode_size - 8 + i] = 0x20;
	}
}

//设置标准线（Timing Patterns）
//黑白相间的参考线，也是用于定位的。
static void set_timing_pattern(void)
{
	int i;
	for (i = 8; i <= (m_qrcode_size - 9); i++)
	{
		m_qrcode_data[i][6] = ((i % 2) == 0) ? 0x30 : 0x20;
		m_qrcode_data[6][i] = ((i % 2) == 0) ? 0x30 : 0x20;
	}
}

//设置对齐图案（Alignment Patterns ）
//是除了3个大回字，较小的回字。在Version >= 2上的二维码需要，同样是为了定位用的。
static void set_alignment_pattern(int x, int y)
{
	const unsigned char pattern[] = {0x1f,0x11,0x15,0x11,0x1f};
	int i, j;
	if (m_qrcode_data[x][y] & 0x20)
	{
		return;
	}
	x -= 2;
	y -= 2;
	for (i = 0; i < 5; i++)
	{
		for (j = 0; j < 5; j++)
		{
			m_qrcode_data[x + j][y + i] = (pattern[i] & (1 << (4 - j))) ? 0x30 : 0x20;
		}
	}
}

//设置版本信息（Version Information ）
//在Version >= 7以上，需要预留两块3 x 6的区域存放一些版本信息。
static void set_version_info(int version)
{
	int i, j;
	int ver_data;
	if (version < 7)
	{
		return;
	}
	ver_data = version << 12;
	for (i = 0; i < 6; i++)
	{
		if (ver_data & (1 << (17 - i)))
		{
			ver_data ^= (0x1f25 << (5 - i));
		}
	}
	ver_data += version << 12;
	for (i = 0; i < 6; i++)
	{
		for (j = 0; j < 3; j++)
		{
			m_qrcode_data[i][m_qrcode_size - 11 + j] = (ver_data & (1 << (i * 3 + j))) ? 0x30 : 0x20;
			m_qrcode_data[m_qrcode_size - 11 + j][i] = m_qrcode_data[i][m_qrcode_size - 11 + j];
		}
	}
}

//设置格式化信息（Format Information）
//是一个15个bits的信息，包含纠错等级(2bit)和遮蔽图形信息(3bit)
static void set_format_info(int masking)
{
	int i;
	int data;
	int info;
	info = 0x08;
	info += masking;
	data = info << 10;
	for (i = 0; i < 5; i++)
	{
		if (data & (1 << (14 - i)))
		{
			data ^= (0x0537 << (4 - i));
		}
	}
	data += info << 10;
	data ^= 0x5412;
	for (i = 0; i <= 5; i++)
	{
		m_qrcode_data[8][i] = (data & (1 << i)) ? 0x30 : 0x20;
	}
	m_qrcode_data[8][7] = (data & (1 << 6)) ? 0x30 : 0x20;
	m_qrcode_data[8][8] = (data & (1 << 7)) ? 0x30 : 0x20;
	m_qrcode_data[7][8] = (data & (1 << 8)) ? 0x30 : 0x20;
	for (i = 9; i <= 14; i++)
	{	
		m_qrcode_data[14 - i][8] = (data & (1 << i)) ? 0x30 : 0x20;
	}
	for (i = 0; i <= 7; i++)
	{	
		m_qrcode_data[m_qrcode_size - 1 - i][8] = (data & (1 << i)) ? 0x30 : 0x20;
	}
	m_qrcode_data[8][m_qrcode_size - 8] = 0x30;
	for (i = 8; i <= 14; i++)
	{
		m_qrcode_data[8][m_qrcode_size - 15 + i] = (data & (1 << i)) ? 0x30 : 0x20;
	}
}

//设置功能性图案
static void set_function_patterns(int version)
{
	int i, j;
	//三个大回字
	set_postion_pattern(0, 0);
	set_postion_pattern(m_qrcode_size - 7, 0);
	set_postion_pattern(0, m_qrcode_size - 7);
	//分隔线
	set_separator_pattern();
	//对齐图案
	for (i = 0; i < m_qrcode_info[version].align_point_count; i++)
	{
		set_alignment_pattern(m_qrcode_info[version].align_point[i], 6);
		set_alignment_pattern(6, m_qrcode_info[version].align_point[i]);
		for (j = 0; j < m_qrcode_info[version].align_point_count; j++)
		{
			set_alignment_pattern(m_qrcode_info[version].align_point[i], m_qrcode_info[version].align_point[j]);
		}
	}
	//标准线
	set_timing_pattern();
	//版本信息
	set_version_info(version);
}

//设置掩码图案(Mask Pattern)
//避免出现大量黑块或白块，有8种图案可选择，进行XOR操作
static void set_masking_pattern(int masking)
{
	int i, j;
	unsigned char mask;
	for (i = 0; i < m_qrcode_size; i++)
	{
		for (j = 0; j < m_qrcode_size; j++)
		{
			if (!(m_qrcode_data[j][i] & 0x20))
			{
				switch (masking)
				{
				case 0:
					mask = ((i + j) % 2 == 0) ? 1 : 0;
					break;
				case 1:
					mask = (i % 2 == 0) ? 1 : 0;
					break;
				case 2:
					mask = (j % 3 == 0) ? 1 : 0;
					break;
				case 3:
					mask = ((i + j) % 3 == 0) ? 1 : 0;
					break;
				case 4:
					mask = (((i / 2) + (j / 3)) % 2 == 0) ? 1 : 0;
					break;
				case 5:
					mask = (((i * j) % 2) + ((i * j) % 3) == 0) ? 1 : 0;
					break;
				case 6:
					mask = ((((i * j) % 2) + ((i * j) % 3)) % 2 == 0) ? 1 : 0;
					break;
				default:
					mask = ((((i * j) % 3) + ((i + j) % 2)) % 2 == 0) ? 1 : 0;
					break;
				}
				m_qrcode_data[j][i] = ((m_qrcode_data[j][i] & 0xfe) | (((m_qrcode_data[j][i] & 0x02) > 1) ^ mask));
			}
		}
	}
}


//图案评审，计算禁区大小
//出现连续黑块或白块越多则禁区越大
static int get_penalty_count(void)
{
	int i, j, k;
	int penalty;
	int count;
	count = 0;
	penalty = 0;
	for (i = 0; i < m_qrcode_size; i++)
	{
		for (j = 0; j < m_qrcode_size - 4; j++)
		{
			count = 1;
			for (k = j + 1; k < m_qrcode_size; k++)
			{
				if (((m_qrcode_data[i][j] & 0x11) == 0) == ((m_qrcode_data[i][k] & 0x11) == 0))
				{
					count++;
				}
				else
				{
					break;
				}
			}
			if (count >= 5)
			{
				penalty += 3 + (count - 5);
			}
			j = k - 1;
		}
	}
	for (i = 0; i < m_qrcode_size; i++)
	{
		for (j = 0; j < m_qrcode_size - 4; j++)
		{
			count = 1;
			for (k = j + 1; k < m_qrcode_size; k++)
			{
				if (((m_qrcode_data[j][i] & 0x11) == 0) == ((m_qrcode_data[k][i] & 0x11) == 0))
				{
					++count;
				}
				else
				{
					break;
				}
			}
			if (count >= 5)
			{
				penalty += 3 + (count - 5);
			}
			j = k - 1;
		}
	}
	for (i = 0; i < m_qrcode_size - 1; i++)
	{
		for (j = 0; j < m_qrcode_size - 1; j++)
		{
			if ((((m_qrcode_data[i][j] & 0x11) == 0) == ((m_qrcode_data[i + 1][j] & 0x11) == 0)) &&
				(((m_qrcode_data[i][j] & 0x11) == 0) == ((m_qrcode_data[i][j + 1] & 0x11) == 0)) &&
				(((m_qrcode_data[i][j] & 0x11) == 0) == ((m_qrcode_data[i + 1][j + 1] & 0x11) == 0)))
			{
				penalty += 3;
			}
		}
	}
	for (i = 0; i < m_qrcode_size; i++)
	{
		for (j = 0; j < m_qrcode_size - 6; j++)
		{
			if (((j == 0) || 
				(! (m_qrcode_data[i][j - 1] & 0x11))) &&
				(   m_qrcode_data[i][j]     & 0x11)   && 
				(! (m_qrcode_data[i][j + 1] & 0x11))  &&
				(   m_qrcode_data[i][j + 2] & 0x11)   &&
				(   m_qrcode_data[i][j + 3] & 0x11)   &&
				(   m_qrcode_data[i][j + 4] & 0x11)   &&
				(! (m_qrcode_data[i][j + 5] & 0x11))  &&
				(   m_qrcode_data[i][j + 6] & 0x11)   &&
				((j == m_qrcode_size - 7) || (! (m_qrcode_data[i][j + 7] & 0x11))))
			{
				if (((j < 2 || ! (m_qrcode_data[i][j - 2] & 0x11)) &&
					(j < 3 || ! (m_qrcode_data[i][j - 3] & 0x11)) &&
					(j < 4 || ! (m_qrcode_data[i][j - 4] & 0x11))) ||
					((j >= m_qrcode_size - 8  || ! (m_qrcode_data[i][j + 8]  & 0x11)) &&
					(j >= m_qrcode_size - 9  || ! (m_qrcode_data[i][j + 9]  & 0x11)) &&
					(j >= m_qrcode_size - 10 || ! (m_qrcode_data[i][j + 10] & 0x11))))
				{
					penalty += 40;
				}
			}
		}
	}
	for (i = 0; i < m_qrcode_size; i++)
	{
		for (j = 0; j < m_qrcode_size - 6; j++)
		{
			if (((j == 0) || (! (m_qrcode_data[j - 1][i] & 0x11))) && 
				(   m_qrcode_data[j][i] & 0x11)   &&
				(! (m_qrcode_data[j + 1][i] & 0x11))  &&
				(   m_qrcode_data[j + 2][i] & 0x11)   &&
				(   m_qrcode_data[j + 3][i] & 0x11)   &&
				(   m_qrcode_data[j + 4][i] & 0x11)   &&
				(! (m_qrcode_data[j + 5][i] & 0x11))  &&
				(   m_qrcode_data[j + 6][i] & 0x11)   &&
				((j == m_qrcode_size - 7) || (! (m_qrcode_data[j + 7][i] & 0x11))))
			{
				if (((j < 2 || ! (m_qrcode_data[j - 2][i] & 0x11)) &&
					(j < 3 || ! (m_qrcode_data[j - 3][i] & 0x11)) &&
					(j < 4 || ! (m_qrcode_data[j - 4][i] & 0x11))) ||
					((j >= m_qrcode_size - 8  || ! (m_qrcode_data[j + 8][i]  & 0x11)) &&
					(j >= m_qrcode_size - 9  || ! (m_qrcode_data[j + 9][i]  & 0x11)) &&
					(j >= m_qrcode_size - 10 || ! (m_qrcode_data[j + 10][i] & 0x11))))
				{
					penalty += 40;
				}
			}
		}
	}
	for (i = 0; i < m_qrcode_size; i++)
	{
		for (j = 0; j < m_qrcode_size; j++)
		{
			if (! (m_qrcode_data[i][j] & 0x11))
			{
				++count;
			}
		}
	}
	if( (50 - ((count * 100) / (m_qrcode_size * m_qrcode_size))) > 0)
	{
		count = 50 - ((count * 100) / (m_qrcode_size * m_qrcode_size));
	}
	else
	{
		count = 0 - (50 - ((count * 100) / (m_qrcode_size * m_qrcode_size)));
	}
	penalty += (count / 5) * 10;
	return penalty;
}


//从8种掩码中选择最佳掩码图形
static void get_masking_pattern(int *mask)
{
	int i;
	int masking;
	int penalty;
	int penalty_min;
	masking = 0;
	penalty_min = ((unsigned)-1)>>1;
	for(i = 0; i < 8; i++)
	{
		set_masking_pattern(i);
		set_format_info(i);
		penalty = get_penalty_count();
		if (penalty < penalty_min)
		{
			penalty_min = penalty;
			masking = i;
		}
	}
	*mask = masking;
}


//设置码字图形，把数据码和纠错码的各个codewords交替放在一起。
//规则如下：
//对于数据码：把每个块的第一个codewords先拿出来按顺度排列好，
//然后再取第一块的第二个，如此类推。如：上述示例中的Data Codewords如下
static void set_code_word_pattern(int code_word_count)
{
	int i, j;
	int x = m_qrcode_size;
	int y = m_qrcode_size - 1;
	int kx = 1;
	int ky = 1;
	for (i = 0; i < code_word_count; i++)
	{
		for (j = 0; j < 8; j++)
		{
			while(1)
			{
				x += kx;
				kx *= -1;
				if (kx < 0)
				{
					y += ky;
					if ((y < 0) || (y == m_qrcode_size))
					{
						y = (y < 0) ? 0 : (m_qrcode_size - 1);
						ky *= -1;
						x -= 2;
						if (x == 6)
						{
							x--;
						}
					}
				}
				if((m_qrcode_data[x][y] & 0x20) == 0x00)
				{
					break;
				}
			}
			m_qrcode_data[x][y] = (m_code_word[i] & (1 << (7 - j))) ? 0x02 : 0x00;
		}
	}
}

//设置数据码字流
static int set_data_code(int index, int data, int size)
{
	int i;
	for (i = 0; i < size; i++)
	{
		if (data & (1 << (size - i - 1)))
		{
			m_data_code[(index + i) / 8] |= 1 << (7 - ((index + i) % 8));
		}
	}
	return index + size;
}

//编码数据
//返回比特长度
static int set_encode_data(unsigned char *data, int size)
{
	int i;
	int count;
	if((size + 2) > MAX_DATA_CODE)
	{
		return 0;
	}
	memset(m_data_code, 0, MAX_DATA_CODE);
	count = 0;
	count = set_data_code(count, 0x04, 4); //起始符4bit表示编码类型
	count = set_data_code(count, size, 8);
	for (i = 0; i < size; i++)
	{
		count = set_data_code(count, (unsigned short)data[i], 8);
	}
	return set_data_code(count, 0x00, 4); //结束符
}

//设置补齐码（Padding Bytes）
//如果数据没有达到我们最大的bits数的限制，我们还要加一些补齐码，
//就是重复下面的两个bytes：11101100(0xEC),00010001(0x11)
static int set_padding_byte(int version, int data_bits_count)
{
	int  i;
	int  data_code_count;
	unsigned char  padding_byte = 0xec;
	data_code_count = m_qrcode_info[version].data_code_count;
	for (i = (data_bits_count + 7) / 8; i < data_code_count; i++)
	{
		m_data_code[i] = padding_byte;
		padding_byte = (padding_byte == 0xec) ? 0x11 : 0xec;
	}
	return data_code_count;
}

//选择合适的版本
static int get_encode_version(int bits_count)
{
	int i;
	for (i = 1; i <= 9; i++)
	{
		if((bits_count + 7) / 8 <= m_qrcode_info[i].data_code_count)
		{
			return i;
		}
	}
	return 0;
}

//设置纠错码
static int set_code_word(int version, int data_code_count)
{
	int i,j;
	int code_word_count;
	int cw_data_index;
	int cw_block_count;
	int cw_block_total;
	int cw_block_index;
	int cw_data_count;
	int cw_rscode_count;

	cw_data_index   = 0;
	cw_block_index  = 0;
	code_word_count = m_qrcode_info[version].code_word_count;
	cw_block_count  = m_qrcode_info[version].rsec_block;
	cw_block_total  = cw_block_count;
	cw_data_count   = m_qrcode_info[version].rsec_block_data_count;
	memset(m_code_word, 0, code_word_count);
	for (i = 0; i < cw_block_count; i++)
	{
		for (j = 0; j < cw_data_count; j++)
		{
			m_code_word[(cw_block_total * j) + cw_block_index] = m_data_code[cw_data_index++];
		}
		cw_block_index++;
	}
	cw_rscode_count = m_qrcode_info[version].rsec_block_code_count - cw_data_count;
	cw_data_index = 0;
	cw_block_index = 0;
	for (i = 0; i < cw_block_count; i++)
	{
		memset(m_rsec_code, 0, sizeof(m_rsec_code));
		memmove(m_rsec_code, m_data_code + cw_data_index, cw_data_count);
		rscode_encode(m_rsec_code, cw_data_count, cw_rscode_count);
		for (j = 0; j < cw_rscode_count; j++)
		{
			m_code_word[data_code_count + (cw_block_total * j) + cw_block_index] = m_rsec_code[j];
		}
		cw_data_index += cw_data_count;
		cw_block_index++;
	}
	return code_word_count;
}

//格式化数据
static void format_qrcode_data(int version, int code_word_count)
{
	int i, j;
	int masking;
	m_qrcode_size = version * 4 + 17;
	memset(m_qrcode_data, 0, sizeof(m_qrcode_data));
	set_function_patterns(version);
	set_code_word_pattern(code_word_count);
	get_masking_pattern(&masking);
	set_masking_pattern(masking);
	set_format_info(masking);
	for (i = 0; i < m_qrcode_size; i++)
	{
		for (j = 0; j < m_qrcode_size; j++)
		{
			m_qrcode_data[i][j] = (m_qrcode_data[i][j] & 0x11) != 0;
		}
	}
}

//编码数据
int qrcode_encode(unsigned char *data, int size, struct qrcode_bitmap *bitmap)
{
	int  version;
	int  data_bits_count;
	int  data_code_count;
	int  code_word_count;
	data_bits_count = set_encode_data(data, size);
	if(data_bits_count == 0)
	{
		return 0;
	}
	version = get_encode_version(data_bits_count);
	if(version == 0)
	{
		return 0;
	}
	data_code_count = set_padding_byte(version, data_bits_count);
	code_word_count = set_code_word(version, data_code_count);
	format_qrcode_data(version, code_word_count);
	bitmap->line_size = MAX_QRCODE_SIZE;
	bitmap->data_size = m_qrcode_size;
	bitmap->data      = (unsigned char *)m_qrcode_data;
	return 1;
}