/*	
 *	clipqr.c
 *
 *	QRコード
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2015 Naoyuki Sawa
 *
 *	* Thu Sep 03 22:37:39 JST 2015 Naoyuki Sawa
 *	- 1st リリース。
 *	* Fri Sep 04 23:00:05 JST 2015 Naoyuki Sawa
 *	- QrDecode_1()を追加しました。
 *	* Sat Sep 05 21:31:55 JST 2015 Naoyuki Sawa
 *	- 'マスク処理結果の評価'処理を、簡易的な処理から、仕様に沿った処理に変更しました。
 *	* Sun Sep 20 18:19:03 JST 2015 Naoyuki Sawa
 *	- Qr_decode_jpeg()を追加しました。
 *	  QRコード画像デコードユーティリティは、アプリケーション寄りの実装例でもあります。
 */
#include "clip.h"
/****************************************************************************
 *	
 ****************************************************************************/
//英数字モードでの符号化・復号表
static const char TBL_Ank[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:";
/*--------------------------------------------------------------------------*/
//マスクパターン
static const int QrMask(int mask, int x, int y) {
	switch(mask) {
	default:DIE();
	case 0: return !((y + x) % 2);
	case 1: return !((y    ) % 2);
	case 2: return !((    x) % 3);
	case 3: return !((y + x) % 3);
	case 4: return !((((y / 2)    ) + ((x / 3)    )) % 2);
	case 5: return !((((y * x) % 2) + ((y * x) % 3))    );
	case 6: return !((((y * x) % 2) + ((y * x) % 3)) % 2);
	case 7: return !((((y * x) % 3) + ((y + x) % 2)) % 2);
	}
}
/****************************************************************************
 *	QRコードエンコーダー	1型
 ****************************************************************************/
static const char TBL_Sym_1[21][21/*nul無し*/]={
"XXXXXXX_A    _XXXXXXX",
"X_____X_A    _X_____X",
"X_XXX_X_A    _X_XXX_X",
"X_XXX_X_A    _X_XXX_X",
"X_XXX_X_A    _X_XXX_X",
"X_____X_A    _X_____X",
"XXXXXXX_X_X_X_XXXXXXX",
"________A    ________",
">>>>>>X>A    >>>>>>>>",
"      _              ",
"      X              ",
"      _              ",
"      X              ",
"________X            ",
"XXXXXXX_A            ",
"X_____X_A            ",
"X_XXX_X_A            ",
"X_XXX_X_A            ",
"X_XXX_X_A            ",
"X_____X_A            ",
"XXXXXXX_A            "};
/*--------------------------------------------------------------------------*/
//特徴		同色の行・列の隣接モジュール
//評価条件	モジュール数=(5+i)
//失点		N1+i (N1=3)
static int QrAssess_1_1(uint8_t* sym/*[((21*21)+31)/8]*/) {
	int n = 0, i, x, y, c1, c2;
	//行
	for(y = 0; y <= 20; y++) {
		for(x = 0; x <= 20; x++) {
			c1 = bitarray_lsb1st_get(sym, (21 * y) + x, 1);
			for(i = 1; (x + i) <= 20; i++) {
				c2 = bitarray_lsb1st_get(sym, (21 * y) + (x + i), 1);
				if(c1 != c2) { break; }
			}
			if(i >= 5) { n += 3/*N1*/ + (i - 5); }
			x += i - 1/*forで進む分*/;
		}
	}
	//列
	for(x = 0; x <= 20; x++) {
		for(y = 0; y <= 20; y++) {
			c1 = bitarray_lsb1st_get(sym, (21 * y) + x, 1);
			for(i = 1; (y + i) <= 20; i++) {
				c2 = bitarray_lsb1st_get(sym, (21 * (y + i)) + x, 1);
				if(c1 != c2) { break; }
			}
			if(i >= 5) { n += 3/*N1*/ + (i - 5); }
			y += i - 1/*forで進む分*/;
		}
	}
	return n;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//特徴		同色のモジュールブロック
//評価条件	ブロックサイズ=2×2
//失点		N2 (N2=3)
static int QrAssess_1_2(uint8_t* sym/*[((21*21)+31)/8]*/) {
	int n = 0, x, y, c;
	for(y = 0; y <= (20 - 1); y++) {
		for(x = 0; x <= (20 - 1); x++) {
			c = bitarray_lsb1st_get(sym, (21 *  y     ) +  x     , 1);
			if( bitarray_lsb1st_get(sym, (21 *  y     ) + (x + 1), 1) != c) { continue; }
			if( bitarray_lsb1st_get(sym, (21 * (y + 1)) +  x     , 1) != c) { continue; }
			if( bitarray_lsb1st_get(sym, (21 * (y + 1)) + (x + 1), 1) != c) { continue; }
			n += 3/*N2*/;
		}
	}
	return n;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//特徴		行・列における1:1:3:1:1比率の(暗:明:暗:明:暗)のパターン
//評価条件	1:1:3:1:1比率のパターンの前又は後ろに比率4の幅以上の明パターンが存在する。
//失点		N3 (N3=40)
static int QrAssess_1_3(uint8_t* sym/*[((21*21)+31)/8]*/) {
	int n = 0, x, y, c;
	for(y = 0; y <= 20; y++) {
		for(x = 0; x <= 20; x++) {
			//(1:1:3:1:1:4)
			if(x < (21 - (1+1+3+1+1+4))) {
				c = bitarray_lsb1st_get(sym, (21 * y) + x, (1+1+3+1+1+4));
				if(c == 0x05D/*右←00001011101→左*/) { n += 40/*N3*/; }
			}
			//1型は一辺21だから(2:2:6:2:2:8)以上の倍率は現れない。
		}
	}
	return n;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//特徴		全体に対する暗モジュールの占める割合
//評価条件	50±(5×k)%〜50±(5×(k＋1))%
//失点		N4×k (N4=10)
static int QrAssess_1_4(uint8_t* sym/*[((21*21)+31)/8]*/) {
	int n = 0, x, y;
	for(y = 0; y <= 20; y++) {
		for(x = 0; x <= 20; x++) {
			n += bitarray_lsb1st_get(sym, (21 * y) + x, 1);
		}
	}
	n = (n * 100) / (21 * 21);	//百分率に変換する。
	n = abs(n - 50);		//±を絶対値にする。
	n = ((n + 4) / 5) * 10/*N4*/;	//5%当り10点とする。
	return n;
}
/*--------------------------------------------------------------------------*/
static void* QrEncode_1(int level, int mode, int ccnt, const void* data, int nbit) {
	uint8_t sym[((21*21)+31)/8], buf[((8*26)+31)/8];
	int pos, mask, i, k, t, v, x, y;
	//位置検出パターン,タイミングパターンの配置
	for(y = 0; y <= 20; y++) {
		for(x = 0; x <= 20; x++) {
			t = (TBL_Sym_1[y][x] == 'X');
			bitarray_lsb1st_set(sym, (21 * y) + x, 1, t);
		}
	}
	//データコード語数(モード指示子及び文字数指示子も含む)
	switch(level) {
	default:DIE();
	case 1: k = 19; break;	//L	(255,248)RS符号⇒(26,19)短縮RS符号として使用する。
	case 0: k = 16; break;	//M	(255,245)RS符号⇒(26,16)短縮RS符号として使用する。
	case 3: k = 13; break;	//Q	(255,242)RS符号⇒(26,13)短縮RS符号として使用する。
	case 2: k =  9; break;	//H	(255,238)RS符号⇒(26, 9)短縮RS符号として使用する。
	}
	//データ及び誤り訂正コード語
	{
		pos = 0;
		//モード指示子
		bitarray_msb1st_set(buf, pos, 4, mode);		pos += 4;
		//文字数指示子
		switch(mode) {
		default:DIE();
		case 1: t = 10; break;	//数字
		case 2: t =  9; break;	//英数字
		case 4: t =  8; break;	//8ビットバイト
		case 8: t =  8; break;	//漢字
		}
		bitarray_msb1st_set(buf, pos, t, ccnt);		pos += t;
		//データ
		for(i = 0; i < nbit; i++) {
			t = bitarray_msb1st_get(data, i, 1);
			bitarray_msb1st_set(buf, pos, 1, t);		pos += 1;
		}
		//終端パターン
		t = (8 * k) - pos;
		if(t < 0) { DIE(); }
		if(t > 4) { t = 4; }
		bitarray_msb1st_set(buf, pos, t, 0);		pos += t;
		//埋め草ビット
		t = -pos & 7;
		bitarray_msb1st_set(buf, pos, t, 0);		pos += t;
		//埋め草コード語
		for(;;) {
			if(pos == (8 * k)) { break; }
			bitarray_msb1st_set(buf, pos, 8, 0xEC);		pos += 8;
			if(pos == (8 * k)) { break; }
			bitarray_msb1st_set(buf, pos, 8, 0x11);		pos += 8;
		}
		//リードソロモン符号化
		{
			uint8_t a[((8*19)+31)/8], b[((8*26)+31)/8];
			ST_GaloisField* pGF = GaloisField_New(0x11D);
			ST_ReedSolomon* pRS = ReedSolomon_NewM(pGF, 26 - k);
			for(i = 0; i < k; i++) {
				t = bitarray_msb1st_get(buf, (8 * i), 8);	//┬バイトオーダー反転
				a[(k - 1) - i] = t;				//┘
			}
			ReedSolomon_EncodeN(pRS, a, b, 26);
			for(i = 0; i < 26; i++) {
				t = b[(26 - 1) - i];				//┬バイトオーダー反転
				bitarray_msb1st_set(buf, (8 * i), 8, t);	//┘
			}
			ReedSolomon_Free(pRS);
			GaloisField_Free(pGF);
		}
		//コード語の配置
		x = 20, y = 20, v = 1, i = 0;
		for(;;) {
			if(TBL_Sym_1[y][x] == ' ') {
				t = bitarray_msb1st_get(buf, i, 1);
				bitarray_lsb1st_set(sym, (21 * y) + x, 1, t);
				if(++i == (8 * 26)) { break; }
			}
			x--;
			if(TBL_Sym_1[y][x] == ' ') {
				t = bitarray_msb1st_get(buf, i, 1);
				bitarray_lsb1st_set(sym, (21 * y) + x, 1, t);
				if(++i == (8 * 26)) { break; }
			}
			x++;
			if((unsigned)(y -= v) > 20) {
				y -= (v = -v);
				x -= (x -= 2) == 6;	//仕様書からは判り辛いが、6列目を飛ばすのが正しい。
				if(x < 1) { DIE(); }
			}
		}
	}
	//マスク処理
	{
		int min  = INT_MAX;
		    mask = 0;	//警告抑制
		//マスクパターン0〜7について…
		for(i = 0; i <= 7; i++) {
			//マスク処理を適用する。
			for(y = 0; y <= 20; y++) {
				for(x = 0; x <= 20; x++) {
					if(TBL_Sym_1[y][x] == ' ') {		//マスク処理は、機能パターンには適用しない。符号化領域(形式情報及び型番情報を除く)で与えられたモジュールパターンと複数のマスク処理マトリックスパターンとで順にXOR演算による変換をする。
						t = bitarray_lsb1st_get(sym, (21 * y) + x, 1);
						if(i) { t ^= QrMask(i - 1, x, y); }	//初回以外ならば、前回のマスクパターンのマスク処理を解除する。
						        t ^= QrMask(i    , x, y);	//今回のマスクパターンのマスク処理を適用する。
						    bitarray_lsb1st_set(sym, (21 * y) + x, 1, t);
					}
				}
			}
			//マスク処理結果の評価
			t = QrAssess_1_1(sym)	//同色の行・列の隣接モジュール
			  + QrAssess_1_2(sym)	//同色のモジュールブロック
			  + QrAssess_1_3(sym)	//行・列における1:1:3:1:1比率の(暗:明:暗:明:暗)のパターン
			  + QrAssess_1_4(sym);	//全体に対する暗モジュールの占める割合
			if(t < min) {	//失点の合計が最小となるマスクパターンをシンボルに適用する。
				min  = t;
				mask = i;
			}
		}
		//選択したマスクパターンのマスク処理を適用する。
		for(y = 0; y <= 20; y++) {
			for(x = 0; x <= 20; x++) {
				if(TBL_Sym_1[y][x] == ' ') {			//マスク処理は、機能パターンには適用しない。符号化領域(形式情報及び型番情報を除く)で与えられたモジュールパターンと複数のマスク処理マトリックスパターンとで順にXOR演算による変換をする。
					t = bitarray_lsb1st_get(sym, (21 * y) + x, 1);
					t ^= QrMask(i - 1, x, y);		//最後のマスクパターンのマスク処理を解除する。
					t ^= QrMask(mask,  x, y);		//選択したマスクパターンのマスク処理を適用する。
					    bitarray_lsb1st_set(sym, (21 * y) + x, 1, t);
				}
			}
		}
	}
	//形式情報及びその誤り訂正符号
	{
		pos = 0;
		//形式情報
		bitarray_msb1st_set(buf, pos, 2, level);	pos += 2;	//誤り訂正レベル
		bitarray_msb1st_set(buf, pos, 3, mask);		pos += 3;	//マスクパターン
		//BCH符号化
		{
			uint8_t a[(5+31)/8], b[(15+31)/8];
			ST_GaloisField* pGF = GaloisField_New(0x13);
			ST_BCH* pBCH = BCH_New(pGF, 3);				//(15,5)BCH符号
			for(i = 0; i < 5; i++) {
				t = bitarray_msb1st_get(buf, i, 1);		//┬ビットオーダー反転
				bitarray_lsb1st_set(a, (5 - 1) - i, 1, t);	//┘
			}
			BCH_Encode(pBCH, a, b);
			*(uint16_t*)b ^= 0x5412;				//15ビットの誤り訂正化された形式情報は、誤り訂正レベル及びマスクパターンの組合せによってデータ文字列がすべてゼロにならないよう、特定のビットパターンとでXOR演算する。そのXOR演算用のマスクパターンは、101010000010010とする。
			for(i = 0; i < 15; i++) {
				t = bitarray_lsb1st_get(b, (15 - 1) - i, 1);	//┬ビットオーダー反転
				bitarray_msb1st_set(buf, i, 1, t);		//┘
			}
			BCH_Free(pBCH);
			GaloisField_Free(pGF);
		}
		//形式情報の配置
		x = 8, y = 20, i = 0;
		for(;;) {
			if(TBL_Sym_1[y][x] == 'A') {
				t = bitarray_msb1st_get(buf, i, 1);
				bitarray_lsb1st_set(sym, (21 * y) + x, 1, t);
				if(++i == 15) { break; }
			}
			if(--y < 0) { DIE(); }
		}
		x = 0, y = 8, i = 0;
		for(;;) {
			if(TBL_Sym_1[y][x] == '>') {
				t = bitarray_msb1st_get(buf, i, 1);
				bitarray_lsb1st_set(sym, (21 * y) + x, 1, t);
				if(++i == 15) { break; }
			}
			if(++x > 20) { DIE(); }
		}
	}
#if 0
	//開発中の結果確認用
	for(y = 0; y <= 20; y++) {
		for(x = 0; x <= 20; x++) {
			if(x) { putchar(','); }
			t = bitarray_lsb1st_get(sym, (21 * y) + x, 1);
			printf("%c", t ? 'X' : '_');
		}
		printf("\n");
	}
#endif
	//シンボルのメモリを複製して返す。
	// - メモリの内容は、1モジュール1ビットのビットマップです。
	//   呼び出し側にて、開放してください。
	return memdup(sym, sizeof sym);
}
/*--------------------------------------------------------------------------*/
//1型 数字データ
static void* QrEncode_1_N(int level, const char* data) {
	uint8_t buf[((8*19)+31)/8];
	int pos = 0, len = 0, max, c1, c2, c3;
	switch(level) {
	default:DIE();
	case 1: max = 41; break;	//L
	case 0: max = 34; break;	//M
	case 3: max = 27; break;	//Q
	case 2: max = 17; break;	//H
	}
	while((c1 = *data++)) {
		if(++len > max) { DIE(); }
		c1 -= '0';
		if((unsigned)c1 >= 10) { DIE(); }
		if((c2 = *data++)) {
			if(++len > max) { DIE(); }
			c2 -= '0';
			if((unsigned)c2 >= 10) { DIE(); }
			if((c3 = *data++)) {
				if(++len > max) { DIE(); }
				c3 -= '0';
				if((unsigned)c3 >= 10) { DIE(); }
				bitarray_msb1st_set(buf, pos, 10, (c1 * 100) + (c2 * 10) + c3);		pos += 10;
			} else {
				bitarray_msb1st_set(buf, pos, 7, (c1 * 10) + c2);			pos += 7;
				break;
			}
		} else {
			bitarray_msb1st_set(buf, pos, 4, c1);						pos += 4;
			break;
		}
	}
	return QrEncode_1(level, 1/*数字*/, len, buf, pos);
}
/*--------------------------------------------------------------------------*/
//1型 英数字データ
static void* QrEncode_1_A(int level, const char* data) {
	uint8_t buf[((8*19)+31)/8];
	int pos = 0, len = 0, max, c1, c2;
	switch(level) {
	default:DIE();
	case 1: max = 25; break;	//L
	case 0: max = 20; break;	//M
	case 3: max = 16; break;	//Q
	case 2: max = 10; break;	//H
	}
	while((c1 = *data++)) {
		if(++len > max) { DIE(); }
		c1 = strchr(TBL_Ank, c1) - TBL_Ank;
		if((unsigned)c1 >= 45) { DIE(); }
		if((c2 = *data++)) {
			if(++len > max) { DIE(); }
			c2 = strchr(TBL_Ank, c2) - TBL_Ank;
			if((unsigned)c2 >= 45) { DIE(); }
			bitarray_msb1st_set(buf, pos, 11, (c1 * 45) + c2);	pos += 11;
		} else {
			bitarray_msb1st_set(buf, pos, 6, c1);			pos += 6;
			break;
		}
	}
	return QrEncode_1(level, 2/*英数字*/, len, buf, pos);
}
/*--------------------------------------------------------------------------*/
//1型 8ビットバイトデータ
static void* QrEncode_1_B(int level, const void* data, int len) {
	uint8_t buf[((8*19)+31)/8];
	int pos = 0, max, i, c;
	switch(level) {
	default:DIE();
	case 1: max = 17; break;	//L
	case 0: max = 14; break;	//M
	case 3: max = 11; break;	//Q
	case 2: max =  7; break;	//H
	}
	if(len > max) { DIE(); }
	for(i = 0; i < len; i++) {
		c = ((uint8_t*)data)[i];
		bitarray_msb1st_set(buf, pos, 8, c);	pos += 8;
	}
	return QrEncode_1(level, 4/*8ビットバイト*/, len, buf, pos);
}
/*--------------------------------------------------------------------------*/
void* QrEncode_1L_N(const char* data) { return QrEncode_1_N(1/*L*/, data); }	//1-L型 数字データ
void* QrEncode_1M_N(const char* data) { return QrEncode_1_N(0/*M*/, data); }	//1-M型 数字データ
void* QrEncode_1Q_N(const char* data) { return QrEncode_1_N(3/*Q*/, data); }	//1-Q型 数字データ
void* QrEncode_1H_N(const char* data) { return QrEncode_1_N(2/*H*/, data); }	//1-H型 数字データ
/*--------------------------------------------------------------------------*/
void* QrEncode_1L_A(const char* data) { return QrEncode_1_A(1/*L*/, data); }	//1-L型 英数字データ
void* QrEncode_1M_A(const char* data) { return QrEncode_1_A(0/*M*/, data); }	//1-M型 英数字データ
void* QrEncode_1Q_A(const char* data) { return QrEncode_1_A(3/*Q*/, data); }	//1-Q型 英数字データ
void* QrEncode_1H_A(const char* data) { return QrEncode_1_A(2/*H*/, data); }	//1-H型 英数字データ
/*--------------------------------------------------------------------------*/
void* QrEncode_1L_B(const void* data, int len) { return QrEncode_1_B(1/*L*/, data, len); }	//1-L型 8ビットバイトデータ
void* QrEncode_1M_B(const void* data, int len) { return QrEncode_1_B(0/*M*/, data, len); }	//1-M型 8ビットバイトデータ
void* QrEncode_1Q_B(const void* data, int len) { return QrEncode_1_B(3/*Q*/, data, len); }	//1-Q型 8ビットバイトデータ
void* QrEncode_1H_B(const void* data, int len) { return QrEncode_1_B(2/*H*/, data, len); }	//1-H型 8ビットバイトデータ
/****************************************************************************
 *	QRコードデコーダー	1型
 ****************************************************************************/
//1型 数字データ
static void QrDecode_1_N(const void* buf, int pos, int ccnt, uint8_t* data) {
	int c, i = 0;
	while(ccnt) {
		if(ccnt == 1) {
			c = bitarray_msb1st_get(buf, pos, 4);	pos += 4;
			data[i + 0] = (c % 10) + '0';
			i += 1, ccnt -= 1;
		} else if(ccnt == 2) {
			c = bitarray_msb1st_get(buf, pos, 7);	pos += 7;
			data[i + 1] = (c % 10) + '0';
			c /= 10;
			data[i + 0] = (c % 10) + '0';
			i += 2, ccnt -= 2;
		} else {
			c = bitarray_msb1st_get(buf, pos, 10);	pos += 10;
			data[i + 2] = (c % 10) + '0';
			c /= 10;
			data[i + 1] = (c % 10) + '0';
			c /= 10;
			data[i + 0] = (c % 10) + '0';
			i += 3, ccnt -= 3;
		}
	}
}
/*--------------------------------------------------------------------------*/
//1型 英数字データ
static void QrDecode_1_A(const void* buf, int pos, int ccnt, uint8_t* data) {
	int c, i = 0;
	while(ccnt) {
		if(ccnt == 1) {
			c = bitarray_msb1st_get(buf, pos, 6);	pos += 6;
			data[i + 0] = TBL_Ank[c % 45];
			i += 1, ccnt -= 1;
		} else {
			c = bitarray_msb1st_get(buf, pos, 11);	pos += 11;
			data[i + 1] = TBL_Ank[c % 45];
			c /= 45;
			data[i + 0] = TBL_Ank[c % 45];
			i += 2, ccnt -= 2;
		}
	}
}
/*--------------------------------------------------------------------------*/
//1型 8ビットバイトデータ
static void QrDecode_1_B(const void* buf, int pos, int ccnt, uint8_t* data) {
	int c, i = 0;
	while(ccnt) {
		c = bitarray_msb1st_get(buf, pos, 8);		pos += 8;
		data[i + 0] = c;
		i += 1, ccnt -= 1;
	}
}
/*--------------------------------------------------------------------------*/
int QrDecode_1(const void* _sym, void* data/*[41+1],NULL可*/) {
	uint8_t sym[((21*21)+31)/8], buf[((8*26)+31)/8];
	int pos, level, mode, mask, ccnt, i, k, q, t, v, x, y;
	//シンボルのメモリをコピーする。
	// - 以下の処理でシンボルの値(モジュール)を書き換えるので、呼び出し側のメモリを破壊しないようコピーする必要が有る。
	for(y = 0; y <= 20; y++) {
		for(x = 0; x <= 20; x++) {
			t = bitarray_lsb1st_get(_sym, (21 * y) + x, 1);
			    bitarray_lsb1st_set( sym, (21 * y) + x, 1, t);
		}
	}
	//形式情報及びその誤り訂正符号
	{
		//形式情報の読み取り
		x = 8, y = 20, i = 0;
		for(;;) {
			if(TBL_Sym_1[y][x] == 'A') {
				t = bitarray_lsb1st_get(sym, (21 * y) + x, 1);
				bitarray_msb1st_set(buf, i, 1, t);
				if(++i == 15) { break; }
			}
			if(--y < 0) { DIE(); }
		}
		x = 0, y = 8, i = 0;
		for(;;) {
			if(TBL_Sym_1[y][x] == '>') {
				t = bitarray_lsb1st_get(sym, (21 * y) + x, 1);
				bitarray_msb1st_set(buf, i, 1, t);
				if(++i == 15) { break; }
			}
			if(++x > 20) { DIE(); }
		}
		//BCH復号化
		{
			uint8_t a[(15+31)/8], b[(5+31)/8];
			ST_GaloisField* pGF = GaloisField_New(0x13);
			ST_BCH* pBCH = BCH_New(pGF, 3);				//(15,5)BCH符号
			for(i = 0; i < 15; i++) {
				t = bitarray_msb1st_get(buf, i, 1);		//┬ビットオーダー反転
				bitarray_lsb1st_set(a, (15 - 1) - i, 1, t);	//┘
			}
			*(uint16_t*)a ^= 0x5412;				//15ビットの誤り訂正化された形式情報は、誤り訂正レベル及びマスクパターンの組合せによってデータ文字列がすべてゼロにならないよう、特定のビットパターンとでXOR演算する。そのXOR演算用のマスクパターンは、101010000010010とする。
			q = BCH_Decode(pBCH, a, b);
			for(i = 0; i < 5; i++) {
				t = bitarray_lsb1st_get(b, (5 - 1) - i, 1);	//┬ビットオーダー反転
				bitarray_msb1st_set(buf, i, 1, t);		//┘
			}
			BCH_Free(pBCH);
			GaloisField_Free(pGF);
			if(q == -1) { return -1; }				//BCH復号化が出来なければ、ここまで。
		}
		pos = 0;
		//形式情報
		level = bitarray_msb1st_get(buf, pos, 2);	pos += 2;	//誤り訂正レベル
		mask  = bitarray_msb1st_get(buf, pos, 3);	pos += 3;	//マスクパターン
		if(((unsigned)level > 3) ||					//誤り訂正レベルが不正ならば、ここまで。
		   ((unsigned)mask  > 7)) { return -1; }			//マスクパターンが不正ならば、ここまで。
	}
	//マスク処理
	{
		for(y = 0; y <= 20; y++) {
			for(x = 0; x <= 20; x++) {
				if(TBL_Sym_1[y][x] == ' ') {			//マスク処理は、機能パターンには適用しない。符号化領域(形式情報及び型番情報を除く)で与えられたモジュールパターンと複数のマスク処理マトリックスパターンとで順にXOR演算による変換をする。
					t = bitarray_lsb1st_get(sym, (21 * y) + x, 1);
					t ^= QrMask(mask, x, y);		//マスク処理を解除する。
					    bitarray_lsb1st_set(sym, (21 * y) + x, 1, t);
				}
			}
		}
	}
	//データコード語数(モード指示子及び文字数指示子も含む)
	switch(level) {
	default:DIE();
	case 1: k = 19; break;	//L	(255,248)RS符号⇒(26,19)短縮RS符号として使用する。
	case 0: k = 16; break;	//M	(255,245)RS符号⇒(26,16)短縮RS符号として使用する。
	case 3: k = 13; break;	//Q	(255,242)RS符号⇒(26,13)短縮RS符号として使用する。
	case 2: k =  9; break;	//H	(255,238)RS符号⇒(26, 9)短縮RS符号として使用する。
	}
	//データ及び誤り訂正コード語
	{
		//コード語の読み取り
		x = 20, y = 20, v = 1, i = 0;
		for(;;) {
			if(TBL_Sym_1[y][x] == ' ') {
				t = bitarray_lsb1st_get(sym, (21 * y) + x, 1);
				bitarray_msb1st_set(buf, i, 1, t);
				if(++i == (8 * 26)) { break; }
			}
			x--;
			if(TBL_Sym_1[y][x] == ' ') {
				t = bitarray_lsb1st_get(sym, (21 * y) + x, 1);
				bitarray_msb1st_set(buf, i, 1, t);
				if(++i == (8 * 26)) { break; }
			}
			x++;
			if((unsigned)(y -= v) > 20) {
				y -= (v = -v);
				x -= (x -= 2) == 6;
				if(x < 1) { DIE(); }
			}
		}
		//リードソロモン復号化
		{
			uint8_t a[((8*26)+31)/8], b[((8*19)+31)/8];
			ST_GaloisField* pGF = GaloisField_New(0x11D);
			ST_ReedSolomon* pRS = ReedSolomon_NewM(pGF, 26 - k);
			for(i = 0; i < 26; i++) {
				t = bitarray_msb1st_get(buf, (8 * i), 8);	//┬バイトオーダー反転
				a[(26 - 1) - i] = t;				//┘
			}
			q = ReedSolomon_DecodeN(pRS, a, b, 26);
			for(i = 0; i < k; i++) {
				t = b[(k - 1) - i];				//┬バイトオーダー反転
				bitarray_msb1st_set(buf, (8 * i), 8, t);	//┘
			}
			ReedSolomon_Free(pRS);
			GaloisField_Free(pGF);
			if(q == -1) { return -1; }				//リードソロモン復号化が出来なければ、ここまで。
		}
		pos = 0;
		//モード指示子
		mode = bitarray_msb1st_get(buf, pos, 4);	pos += 4;
		if((mode != 1) && (mode != 2) && (mode != 4) /*&& (mode != 8)*/) { return -1; }	//モードが不正ならば、ここまで。	漢字モードは未実装
		//文字数指示子
		switch(mode) {
		default:DIE();
		case 1: t = 10; break;	//数字
		case 2: t =  9; break;	//英数字
		case 4: t =  8; break;	//8ビットバイト
		case 8: t =  8; break;	//漢字
		}
		ccnt = bitarray_msb1st_get(buf, pos, t);	pos += t;
		if(ccnt > 41) { return -1; }					//文字数が不正ならば、ここまで。
		//データを格納するバッファが指定されていたら…
		if(data) {
			//データ
			switch(mode) {
			default:DIE();
			case 1: QrDecode_1_N(buf, pos, ccnt, data); break;	//数字
			case 2: QrDecode_1_A(buf, pos, ccnt, data); break;	//英数字
			case 4: QrDecode_1_B(buf, pos, ccnt, data); break;	//8ビットバイト
		    //	case 8: QrDecode_1_K(buf, pos, ccnt, data); break;	//漢字							漢字モードは未実装
			}
			//データを文字列として扱い易いように、終端にnul文字を追加する事にした。
			((uint8_t*)data)[ccnt] = '\0';
		}
	}
	//文字数を返す。(終端のnul文字は含まない)
	return ccnt;
}
/****************************************************************************
 *	QRコード画像デコードユーティリティ
 ****************************************************************************/
//画像
typedef struct _ST_QrImg {
	uint16_t	w;
	uint16_t	h;
	uint8_t		buf[0/*(w*h)*/];
} ST_QrImg;
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static int QrImg_get(ST_QrImg* img, int x, int y) {
	if(((unsigned)x > (unsigned)img->w) ||
	   ((unsigned)y > (unsigned)img->h)) { DIE(); }
	return img->buf[(img->w * y) + x];
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static void QrImg_set(ST_QrImg* img, int x, int y, int c) {
	if(((unsigned)x > (unsigned)img->w) ||
	   ((unsigned)y > (unsigned)img->h)) { DIE(); }
	img->buf[(img->w * y) + x] = c;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static void QrImg_jpeg_decode_size_proc(int w, int h, void* user_data) {
	ST_QrImg* img = user_data;
	img->w = w;
	img->h = h;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static void QrImg_jpeg_decode_draw_proc(int x, int y, int c, void* user_data) {
	ST_QrImg* img = user_data;
	QrImg_set(img, x, y, c);
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static ST_QrImg* QrImg_load_jpeg(const void* jpeg) {
	ST_QrImg* img = malloc(sizeof(ST_QrImg));
	if(!img) { DIE(); }
	jpeg_decode(jpeg, 0, QrImg_jpeg_decode_size_proc, NULL, NULL, img);
	img = realloc(img, sizeof(ST_QrImg) + (sizeof img->buf[0]) * (img->w * img->h));
	if(!img) { DIE(); }
	jpeg_decode(jpeg, 0, NULL, QrImg_jpeg_decode_draw_proc, NULL, img);
	return img;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static void QrImg_discr(ST_QrImg* img) {
	int c, t, x, y;
	t = discriminant_analysis(img->buf, img->w * img->h);
	for(y = 0; y < img->h; y++) {
		for(x = 0; x < img->w; x++) {
			c = QrImg_get(img, x, y);
			c = (c <= t);	//輝度(0〜t)を1(黒),輝度(t+1〜255)を0(白)とする。
			QrImg_set(img, x, y, c);
		}
	}
}
/*--------------------------------------------------------------------------*/
//ラベリング
typedef struct _ST_QrLab {
	uint16_t	n;
	uint16_t	w;
	uint16_t	h;
	uint16_t	buf[0/*(w*h)*/];
} ST_QrLab;
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static int QrLab_get(ST_QrLab* lab, int x, int y) {
	if(((unsigned)x > (unsigned)lab->w) ||
	   ((unsigned)y > (unsigned)lab->h)) { DIE(); }
	return lab->buf[(lab->w * y) + x];
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static ST_QrLab* QrLab_new(ST_QrImg* img) {
	ST_QrLab* lab = malloc(sizeof(ST_QrLab) + (sizeof lab->buf[0]) * (img->w * img->h));
	if(!lab) { DIE(); }
	lab->w = img->w;
	lab->h = img->h;
	{
		int parents_max = 256/*調整可*/;
		for(;;) {
			uint16_t* parents = malloc(sizeof parents[0] * parents_max);
			if(!parents) { DIE(); }
			lab->n = image_labeling(img->buf, img->w, img->h, lab->buf, 0/*4近傍*/, parents, parents_max);
			free(parents);
			if(lab->n) { break; }
			parents_max <<= 1;
		}
	}
	return lab;
}
/*--------------------------------------------------------------------------*/
//位置検出パターンを探す。
static int Qr_find_pos(ST_QrImg* img, ST_QrLab* lab, int xPos[/*3*/], int yPos[/*3*/]) {
	int nPos = 0, iLab, x, y, w, h, t;
	for(iLab = 0; iLab < lab->n; iLab++) {
		int xMin = INT_MAX, xMax = INT_MIN;
		int yMin = INT_MAX, yMax = INT_MIN;
		for(y = 0; y < lab->h; y++) {
			for(x = 0; x < lab->w; x++) {
				t = QrLab_get(lab, x, y);
				if(t == iLab) {
					t = QrImg_get(img, x, y);			//┬白ピクセルに対するラベリングは除外するために必要。こうしないと45度回転した時に全体を囲む白の領域がマーカーを検出してしまう。
					if(!t) { goto L_NEXT; }			//┘
					if(x < xMin) { xMin = x; }
					if(x > xMax) { xMax = x; }
					if(y < yMin) { yMin = y; }
					if(y > yMax) { yMax = y; }
				}
			}
		}
		w = (xMax - xMin) + 1;
		h = (yMax - yMin) + 1;
		if(w < (1+1+3+1+1)) { goto L_NEXT; }
		if(h < (1+1+3+1+1)) { goto L_NEXT; }
		{
			int a[5] = {0}, i = -1, old = 0;
			y = yMin + (h / 2);
			for(x = xMin; x <= xMax; x++) {
				t = QrImg_get(img, x, y);
				if(t != old) {
					old = t;
					i++;
				}
				if((unsigned)i < 5) {
					a[i]++;
				}
			}
			if(i < 4) { goto L_NEXT; }
			t = (a[2] * 400) / (a[0]+a[1] + a[3]+a[4]);		//┬おおよそ1:1:3:1:1になっているか?
			if(abs(t - 300) > 50/*調整可*/) { goto L_NEXT; }	//┘
		}
		if(nPos < 3) {
			xPos[nPos] = xMin + (w / 2);
			yPos[nPos] = yMin + (h / 2);
			nPos++;
		}
L_NEXT:	;
	}
	if(nPos >= 3) {
		//左上の位置検出パターンを判定する。
		{
			int x01 = xPos[1] - xPos[0], y01 = yPos[1] - yPos[0];
			int x12 = xPos[2] - xPos[1], y12 = yPos[2] - yPos[1];
			int x20 = xPos[0] - xPos[2], y20 = yPos[0] - yPos[2];
			int d01 = (x01 * x01) + (y01 * y01);
			int d12 = (x12 * x12) + (y12 * y12);
			int d20 = (x20 * x20) + (y20 * y20);
			       if((d20 >= d01) && (d20 >= d12)) {	//([2]⇒[0])が長辺 ⇒ [1]が左上
				t = xPos[0]; xPos[0] = xPos[1]; xPos[1] = t;
				t = yPos[0]; yPos[0] = yPos[1]; yPos[1] = t;
			} else if((d01 >= d12) && (d01 >= d20)) {	//([0]⇒[1])が長辺 ⇒ [2]が左上
				t = xPos[0]; xPos[0] = xPos[2]; xPos[2] = t;
				t = yPos[0]; yPos[0] = yPos[2]; yPos[2] = t;
			} else {					//([1]⇒[2])が長辺 ⇒ [0]が左上
				/** no job **/
			}
		}
		//表裏判定を行う。([0]⇒[1]⇒[2]で右回りになるようにする。)
		{
			int x20 = xPos[0] - xPos[2], y20 = yPos[0] - yPos[2];	//v20  = v0 - v2
			int x01 = xPos[1] - xPos[0], y01 = yPos[1] - yPos[0];	//v01  = v1 - v0
			t = (x20 * y01) - (y20 * x01);				//外積 = v20×v01
			if(t < 0) {	//裏?
				t = xPos[2]; xPos[2] = xPos[1]; xPos[1] = t;	//┬表にする。
				t = yPos[2]; yPos[2] = yPos[1]; yPos[1] = t;	//┘
			}
		}
	}
	return nPos;
}
/*--------------------------------------------------------------------------*/
//画像(バイト配列)からシンボル(ビット配列)を作成する。
static void Qr_load_sym(void* sym, ST_QrImg* img, const int xPos[/*3*/], const int yPos[/*3*/]) {
	int vx_x, vx_y, vy_x, vy_y, x, y, tmp_x, tmp_y, c;
	//(xPos[0],yPos[0]) = ( 3, 3)に相当する
	//(xPos[1],yPos[1]) = (17, 3)に相当する
	//(xPos[2],yPos[2]) = ( 3,17)に相当する
	vx_x = xPos[1] - xPos[0];	//(X軸の基底ベクトルのx成分)の14倍
	vx_y = yPos[1] - yPos[0];	//(X軸の基底ベクトルのy成分)の14倍
	vy_x = xPos[2] - xPos[0];	//(Y軸の基底ベクトルのx成分)の14倍
	vy_y = yPos[2] - yPos[0];	//(Y軸の基底ベクトルのy成分)の14倍
	for(y = 0; y < 21; y++) {
		for(x = 0; x < 21; x++) {
			tmp_x = xPos[0] + ((vx_x * (x - 3)) + vy_x * (y - 3)) / 14;
			tmp_y = yPos[0] + ((vx_y * (x - 3)) + vy_y * (y - 3)) / 14;
			if(((unsigned)tmp_x < img->w) &&
			   ((unsigned)tmp_y < img->h)) {
				c = QrImg_get(img, tmp_x, tmp_y);
			} else {
				c = 0;
			}
			bitarray_lsb1st_set(sym, (21 * y) + x, 1, c);
		}
	}
}
/*--------------------------------------------------------------------------*/
//QRコード画像をデコードする。
char* Qr_decode_jpeg(const void* jpeg) {
	ST_QrImg* img;
	ST_QrLab* lab;
	int nPos, xPos[3], yPos[3], nLen = -1;
	char data[41 + 1/*nul*/];
	//画像をロードする。
	img = QrImg_load_jpeg(jpeg);
	//画像を二値化する。
	QrImg_discr(img);
	//ラベリングを行う。
	lab = QrLab_new(img);
	//位置検出パターンを探す。
	nPos = Qr_find_pos(img, lab, xPos, yPos);
	//ラベリングはもう不要なので開放する。
	free(lab);
	//位置検出パターンが三箇所検出出来たら…
	if(nPos >= 3) {
		int sym[((21*21)+31)/32];
		//シンボルをロードする。
		Qr_load_sym(sym, img, xPos, yPos);
		//画像はもう不要なので開放する。
		free(img);
		//QRコード(1型)をデコードする。
		nLen = QrDecode_1(sym, data);	//成功ならば0〜41,失敗ならば-1が返される。
	} else {
		//画像を開放する。
		free(img);
	}
	if(nLen >= 0) {
		//成功ならば、文字列を複製して返す。呼び出し側でfree()で開放してください。
		char* str = strdup(data);
		if(!str) { DIE(); }
		return str;
	} else {
		//失敗ならば、NULLを返す。
		return NULL;
	}
}
