patminlex.cpp

#include "patminlex.h"

const int patminlex::minCanNineBits[512] = { //a precomputed minlexed recomposition of the bit triplets for a 9-bits input
	0, 1, 1, 3, 1, 3, 3, 7, 1, 9, 9, 11, 9, 11, 11, 15, 1, 9, 9, 11, 9, 11, 11, 15, 3, 11, 11, 27, 11,
	27, 27, 31, 1, 9, 9, 11, 9, 11, 11, 15, 3, 11, 11, 27, 11, 27, 27, 31, 3, 11, 11, 27, 11, 27, 27,
	31, 7, 15, 15, 31, 15, 31, 31, 63, 1, 9, 9, 11, 9, 11, 11, 15, 9, 73, 73, 75, 73, 75, 75, 79, 9,
	73, 73, 75, 73, 75, 75, 79, 11, 75, 75, 91, 75, 91, 91, 95, 9, 73, 73, 75, 73, 75, 75, 79, 11, 75,
	75, 91, 75, 91, 91, 95, 11, 75, 75, 91, 75, 91, 91, 95, 15, 79, 79, 95, 79, 95, 95, 127, 1, 9, 9,
	11, 9, 11, 11, 15, 9, 73, 73, 75, 73, 75, 75, 79, 9, 73, 73, 75, 73, 75, 75, 79, 11, 75, 75, 91,
	75, 91, 91, 95, 9, 73, 73, 75, 73, 75, 75, 79, 11, 75, 75, 91, 75, 91, 91, 95, 11, 75, 75, 91, 75,
	91, 91, 95, 15, 79, 79, 95, 79, 95, 95, 127, 3, 11, 11, 27, 11, 27, 27, 31, 11, 75, 75, 91, 75, 91,
	91, 95, 11, 75, 75, 91, 75, 91, 91, 95, 27, 91, 91, 219, 91, 219, 219, 223, 11, 75, 75, 91, 75, 91,
	91, 95, 27, 91, 91, 219, 91, 219, 219, 223, 27, 91, 91, 219, 91, 219, 219, 223, 31, 95, 95, 223, 95,
	223, 223, 255, 1, 9, 9, 11, 9, 11, 11, 15, 9, 73, 73, 75, 73, 75, 75, 79, 9, 73, 73, 75, 73, 75, 75,
	79, 11, 75, 75, 91, 75, 91, 91, 95, 9, 73, 73, 75, 73, 75, 75, 79, 11, 75, 75, 91, 75, 91, 91, 95,
	11, 75, 75, 91, 75, 91, 91, 95, 15, 79, 79, 95, 79, 95, 95, 127, 3, 11, 11, 27, 11, 27, 27, 31, 11,
	75, 75, 91, 75, 91, 91, 95, 11, 75, 75, 91, 75, 91, 91, 95, 27, 91, 91, 219, 91, 219, 219, 223, 11,
	75, 75, 91, 75, 91, 91, 95, 27, 91, 91, 219, 91, 219, 219, 223, 27, 91, 91, 219, 91, 219, 219, 223,
	31, 95, 95, 223, 95, 223, 223, 255, 3, 11, 11, 27, 11, 27, 27, 31, 11, 75, 75, 91, 75, 91, 91, 95,
	11, 75, 75, 91, 75, 91, 91, 95, 27, 91, 91, 219, 91, 219, 219, 223, 11, 75, 75, 91, 75, 91, 91, 95,
	27, 91, 91, 219, 91, 219, 219, 223, 27, 91, 91, 219, 91, 219, 219, 223, 31, 95, 95, 223, 95, 223,
	223, 255, 7, 15, 15, 31, 15, 31, 31, 63, 15, 79, 79, 95, 79, 95, 95, 127, 15, 79, 79, 95, 79, 95,
	95, 127, 31, 95, 95, 223, 95, 223, 223, 255, 15, 79, 79, 95, 79, 95, 95, 127, 31, 95, 95, 223, 95,
	223, 223, 255, 31, 95, 95, 223, 95, 223, 223, 255, 63, 127, 127, 255, 127, 255, 255, 511};

//for a given triplet value and permutation index mask gives:
// - the minlexed value for the triplet after any of permutations allowed in the input mask are applied
// - the output permutation index mask, possibly reduced version of the input one
// - the number of permutation indexes (bits) in the output mask (not used in this algorithm)
static const bestTripletPermutation bestTripletPermutations[8][64] = {
	{
		{65535, 0, 0},	//[0][0]=[  0][     0]->{111,     0,0}
		{0, 1, 1},	//[0][1]=[  0][     1]->{  0,     1,1}
		{0, 2, 1},	//[0][2]=[  0][    10]->{  0,    10,1}
		{0, 3, 2},	//[0][3]=[  0][    11]->{  0,    11,2}
		{0, 4, 1},	//[0][4]=[  0][   100]->{  0,   100,1}
		{0, 5, 2},	//[0][5]=[  0][   101]->{  0,   101,2}
		{0, 6, 2},	//[0][6]=[  0][   110]->{  0,   110,2}
		{0, 7, 3},	//[0][7]=[  0][   111]->{  0,   111,3}
		{0, 8, 1},	//[0][8]=[  0][  1000]->{  0,  1000,1}
		{0, 9, 2},	//[0][9]=[  0][  1001]->{  0,  1001,2}
		{0, 10, 2},	//[0][10]=[  0][  1010]->{  0,  1010,2}
		{0, 11, 3},	//[0][11]=[  0][  1011]->{  0,  1011,3}
		{0, 12, 2},	//[0][12]=[  0][  1100]->{  0,  1100,2}
		{0, 13, 3},	//[0][13]=[  0][  1101]->{  0,  1101,3}
		{0, 14, 3},	//[0][14]=[  0][  1110]->{  0,  1110,3}
		{0, 15, 4},	//[0][15]=[  0][  1111]->{  0,  1111,4}
		{0, 16, 1},	//[0][16]=[  0][ 10000]->{  0, 10000,1}
		{0, 17, 2},	//[0][17]=[  0][ 10001]->{  0, 10001,2}
		{0, 18, 2},	//[0][18]=[  0][ 10010]->{  0, 10010,2}
		{0, 19, 3},	//[0][19]=[  0][ 10011]->{  0, 10011,3}
		{0, 20, 2},	//[0][20]=[  0][ 10100]->{  0, 10100,2}
		{0, 21, 3},	//[0][21]=[  0][ 10101]->{  0, 10101,3}
		{0, 22, 3},	//[0][22]=[  0][ 10110]->{  0, 10110,3}
		{0, 23, 4},	//[0][23]=[  0][ 10111]->{  0, 10111,4}
		{0, 24, 2},	//[0][24]=[  0][ 11000]->{  0, 11000,2}
		{0, 25, 3},	//[0][25]=[  0][ 11001]->{  0, 11001,3}
		{0, 26, 3},	//[0][26]=[  0][ 11010]->{  0, 11010,3}
		{0, 27, 4},	//[0][27]=[  0][ 11011]->{  0, 11011,4}
		{0, 28, 3},	//[0][28]=[  0][ 11100]->{  0, 11100,3}
		{0, 29, 4},	//[0][29]=[  0][ 11101]->{  0, 11101,4}
		{0, 30, 4},	//[0][30]=[  0][ 11110]->{  0, 11110,4}
		{0, 31, 5},	//[0][31]=[  0][ 11111]->{  0, 11111,5}
		{0, 32, 1},	//[0][32]=[  0][100000]->{  0,100000,1}
		{0, 33, 2},	//[0][33]=[  0][100001]->{  0,100001,2}
		{0, 34, 2},	//[0][34]=[  0][100010]->{  0,100010,2}
		{0, 35, 3},	//[0][35]=[  0][100011]->{  0,100011,3}
		{0, 36, 2},	//[0][36]=[  0][100100]->{  0,100100,2}
		{0, 37, 3},	//[0][37]=[  0][100101]->{  0,100101,3}
		{0, 38, 3},	//[0][38]=[  0][100110]->{  0,100110,3}
		{0, 39, 4},	//[0][39]=[  0][100111]->{  0,100111,4}
		{0, 40, 2},	//[0][40]=[  0][101000]->{  0,101000,2}
		{0, 41, 3},	//[0][41]=[  0][101001]->{  0,101001,3}
		{0, 42, 3},	//[0][42]=[  0][101010]->{  0,101010,3}
		{0, 43, 4},	//[0][43]=[  0][101011]->{  0,101011,4}
		{0, 44, 3},	//[0][44]=[  0][101100]->{  0,101100,3}
		{0, 45, 4},	//[0][45]=[  0][101101]->{  0,101101,4}
		{0, 46, 4},	//[0][46]=[  0][101110]->{  0,101110,4}
		{0, 47, 5},	//[0][47]=[  0][101111]->{  0,101111,5}
		{0, 48, 2},	//[0][48]=[  0][110000]->{  0,110000,2}
		{0, 49, 3},	//[0][49]=[  0][110001]->{  0,110001,3}
		{0, 50, 3},	//[0][50]=[  0][110010]->{  0,110010,3}
		{0, 51, 4},	//[0][51]=[  0][110011]->{  0,110011,4}
		{0, 52, 3},	//[0][52]=[  0][110100]->{  0,110100,3}
		{0, 53, 4},	//[0][53]=[  0][110101]->{  0,110101,4}
		{0, 54, 4},	//[0][54]=[  0][110110]->{  0,110110,4}
		{0, 55, 5},	//[0][55]=[  0][110111]->{  0,110111,5}
		{0, 56, 3},	//[0][56]=[  0][111000]->{  0,111000,3}
		{0, 57, 4},	//[0][57]=[  0][111001]->{  0,111001,4}
		{0, 58, 4},	//[0][58]=[  0][111010]->{  0,111010,4}
		{0, 59, 5},	//[0][59]=[  0][111011]->{  0,111011,5}
		{0, 60, 4},	//[0][60]=[  0][111100]->{  0,111100,4}
		{0, 61, 5},	//[0][61]=[  0][111101]->{  0,111101,5}
		{0, 62, 5},	//[0][62]=[  0][111110]->{  0,111110,5}
		{0, 63, 6},	//[0][63]=[  0][111111]->{  0,111111,6}
	},
	{
		{65535, 0, 0},	//[1][0]=[  1][     0]->{111,     0,0}
		{1, 1, 1},	//[1][1]=[  1][     1]->{  1,     1,1}
		{2, 2, 1},	//[1][2]=[  1][    10]->{ 10,    10,1}
		{1, 1, 1},	//[1][3]=[  1][    11]->{  1,     1,1}
		{1, 4, 1},	//[1][4]=[  1][   100]->{  1,   100,1}
		{1, 5, 2},	//[1][5]=[  1][   101]->{  1,   101,2}
		{1, 4, 1},	//[1][6]=[  1][   110]->{  1,   100,1}
		{1, 5, 2},	//[1][7]=[  1][   111]->{  1,   101,2}
		{4, 8, 1},	//[1][8]=[  1][  1000]->{100,  1000,1}
		{1, 1, 1},	//[1][9]=[  1][  1001]->{  1,     1,1}
		{2, 2, 1},	//[1][10]=[  1][  1010]->{ 10,    10,1}
		{1, 1, 1},	//[1][11]=[  1][  1011]->{  1,     1,1}
		{1, 4, 1},	//[1][12]=[  1][  1100]->{  1,   100,1}
		{1, 5, 2},	//[1][13]=[  1][  1101]->{  1,   101,2}
		{1, 4, 1},	//[1][14]=[  1][  1110]->{  1,   100,1}
		{1, 5, 2},	//[1][15]=[  1][  1111]->{  1,   101,2}
		{2, 16, 1},	//[1][16]=[  1][ 10000]->{ 10, 10000,1}
		{1, 1, 1},	//[1][17]=[  1][ 10001]->{  1,     1,1}
		{2, 18, 2},	//[1][18]=[  1][ 10010]->{ 10, 10010,2}
		{1, 1, 1},	//[1][19]=[  1][ 10011]->{  1,     1,1}
		{1, 4, 1},	//[1][20]=[  1][ 10100]->{  1,   100,1}
		{1, 5, 2},	//[1][21]=[  1][ 10101]->{  1,   101,2}
		{1, 4, 1},	//[1][22]=[  1][ 10110]->{  1,   100,1}
		{1, 5, 2},	//[1][23]=[  1][ 10111]->{  1,   101,2}
		{2, 16, 1},	//[1][24]=[  1][ 11000]->{ 10, 10000,1}
		{1, 1, 1},	//[1][25]=[  1][ 11001]->{  1,     1,1}
		{2, 18, 2},	//[1][26]=[  1][ 11010]->{ 10, 10010,2}
		{1, 1, 1},	//[1][27]=[  1][ 11011]->{  1,     1,1}
		{1, 4, 1},	//[1][28]=[  1][ 11100]->{  1,   100,1}
		{1, 5, 2},	//[1][29]=[  1][ 11101]->{  1,   101,2}
		{1, 4, 1},	//[1][30]=[  1][ 11110]->{  1,   100,1}
		{1, 5, 2},	//[1][31]=[  1][ 11111]->{  1,   101,2}
		{4, 32, 1},	//[1][32]=[  1][100000]->{100,100000,1}
		{1, 1, 1},	//[1][33]=[  1][100001]->{  1,     1,1}
		{2, 2, 1},	//[1][34]=[  1][100010]->{ 10,    10,1}
		{1, 1, 1},	//[1][35]=[  1][100011]->{  1,     1,1}
		{1, 4, 1},	//[1][36]=[  1][100100]->{  1,   100,1}
		{1, 5, 2},	//[1][37]=[  1][100101]->{  1,   101,2}
		{1, 4, 1},	//[1][38]=[  1][100110]->{  1,   100,1}
		{1, 5, 2},	//[1][39]=[  1][100111]->{  1,   101,2}
		{4, 40, 2},	//[1][40]=[  1][101000]->{100,101000,2}
		{1, 1, 1},	//[1][41]=[  1][101001]->{  1,     1,1}
		{2, 2, 1},	//[1][42]=[  1][101010]->{ 10,    10,1}
		{1, 1, 1},	//[1][43]=[  1][101011]->{  1,     1,1}
		{1, 4, 1},	//[1][44]=[  1][101100]->{  1,   100,1}
		{1, 5, 2},	//[1][45]=[  1][101101]->{  1,   101,2}
		{1, 4, 1},	//[1][46]=[  1][101110]->{  1,   100,1}
		{1, 5, 2},	//[1][47]=[  1][101111]->{  1,   101,2}
		{2, 16, 1},	//[1][48]=[  1][110000]->{ 10, 10000,1}
		{1, 1, 1},	//[1][49]=[  1][110001]->{  1,     1,1}
		{2, 18, 2},	//[1][50]=[  1][110010]->{ 10, 10010,2}
		{1, 1, 1},	//[1][51]=[  1][110011]->{  1,     1,1}
		{1, 4, 1},	//[1][52]=[  1][110100]->{  1,   100,1}
		{1, 5, 2},	//[1][53]=[  1][110101]->{  1,   101,2}
		{1, 4, 1},	//[1][54]=[  1][110110]->{  1,   100,1}
		{1, 5, 2},	//[1][55]=[  1][110111]->{  1,   101,2}
		{2, 16, 1},	//[1][56]=[  1][111000]->{ 10, 10000,1}
		{1, 1, 1},	//[1][57]=[  1][111001]->{  1,     1,1}
		{2, 18, 2},	//[1][58]=[  1][111010]->{ 10, 10010,2}
		{1, 1, 1},	//[1][59]=[  1][111011]->{  1,     1,1}
		{1, 4, 1},	//[1][60]=[  1][111100]->{  1,   100,1}
		{1, 5, 2},	//[1][61]=[  1][111101]->{  1,   101,2}
		{1, 4, 1},	//[1][62]=[  1][111110]->{  1,   100,1}
		{1, 5, 2},	//[1][63]=[  1][111111]->{  1,   101,2}
	},
	{
		{65535, 0, 0},	//[2][0]=[ 10][     0]->{111,     0,0}
		{2, 1, 1},	//[2][1]=[ 10][     1]->{ 10,     1,1}
		{1, 2, 1},	//[2][2]=[ 10][    10]->{  1,    10,1}
		{1, 2, 1},	//[2][3]=[ 10][    11]->{  1,    10,1}
		{4, 4, 1},	//[2][4]=[ 10][   100]->{100,   100,1}
		{2, 1, 1},	//[2][5]=[ 10][   101]->{ 10,     1,1}
		{1, 2, 1},	//[2][6]=[ 10][   110]->{  1,    10,1}
		{1, 2, 1},	//[2][7]=[ 10][   111]->{  1,    10,1}
		{1, 8, 1},	//[2][8]=[ 10][  1000]->{  1,  1000,1}
		{1, 8, 1},	//[2][9]=[ 10][  1001]->{  1,  1000,1}
		{1, 10, 2},	//[2][10]=[ 10][  1010]->{  1,  1010,2}
		{1, 10, 2},	//[2][11]=[ 10][  1011]->{  1,  1010,2}
		{1, 8, 1},	//[2][12]=[ 10][  1100]->{  1,  1000,1}
		{1, 8, 1},	//[2][13]=[ 10][  1101]->{  1,  1000,1}
		{1, 10, 2},	//[2][14]=[ 10][  1110]->{  1,  1010,2}
		{1, 10, 2},	//[2][15]=[ 10][  1111]->{  1,  1010,2}
		{4, 16, 1},	//[2][16]=[ 10][ 10000]->{100, 10000,1}
		{2, 1, 1},	//[2][17]=[ 10][ 10001]->{ 10,     1,1}
		{1, 2, 1},	//[2][18]=[ 10][ 10010]->{  1,    10,1}
		{1, 2, 1},	//[2][19]=[ 10][ 10011]->{  1,    10,1}
		{4, 20, 2},	//[2][20]=[ 10][ 10100]->{100, 10100,2}
		{2, 1, 1},	//[2][21]=[ 10][ 10101]->{ 10,     1,1}
		{1, 2, 1},	//[2][22]=[ 10][ 10110]->{  1,    10,1}
		{1, 2, 1},	//[2][23]=[ 10][ 10111]->{  1,    10,1}
		{1, 8, 1},	//[2][24]=[ 10][ 11000]->{  1,  1000,1}
		{1, 8, 1},	//[2][25]=[ 10][ 11001]->{  1,  1000,1}
		{1, 10, 2},	//[2][26]=[ 10][ 11010]->{  1,  1010,2}
		{1, 10, 2},	//[2][27]=[ 10][ 11011]->{  1,  1010,2}
		{1, 8, 1},	//[2][28]=[ 10][ 11100]->{  1,  1000,1}
		{1, 8, 1},	//[2][29]=[ 10][ 11101]->{  1,  1000,1}
		{1, 10, 2},	//[2][30]=[ 10][ 11110]->{  1,  1010,2}
		{1, 10, 2},	//[2][31]=[ 10][ 11111]->{  1,  1010,2}
		{2, 32, 1},	//[2][32]=[ 10][100000]->{ 10,100000,1}
		{2, 33, 2},	//[2][33]=[ 10][100001]->{ 10,100001,2}
		{1, 2, 1},	//[2][34]=[ 10][100010]->{  1,    10,1}
		{1, 2, 1},	//[2][35]=[ 10][100011]->{  1,    10,1}
		{2, 32, 1},	//[2][36]=[ 10][100100]->{ 10,100000,1}
		{2, 33, 2},	//[2][37]=[ 10][100101]->{ 10,100001,2}
		{1, 2, 1},	//[2][38]=[ 10][100110]->{  1,    10,1}
		{1, 2, 1},	//[2][39]=[ 10][100111]->{  1,    10,1}
		{1, 8, 1},	//[2][40]=[ 10][101000]->{  1,  1000,1}
		{1, 8, 1},	//[2][41]=[ 10][101001]->{  1,  1000,1}
		{1, 10, 2},	//[2][42]=[ 10][101010]->{  1,  1010,2}
		{1, 10, 2},	//[2][43]=[ 10][101011]->{  1,  1010,2}
		{1, 8, 1},	//[2][44]=[ 10][101100]->{  1,  1000,1}
		{1, 8, 1},	//[2][45]=[ 10][101101]->{  1,  1000,1}
		{1, 10, 2},	//[2][46]=[ 10][101110]->{  1,  1010,2}
		{1, 10, 2},	//[2][47]=[ 10][101111]->{  1,  1010,2}
		{2, 32, 1},	//[2][48]=[ 10][110000]->{ 10,100000,1}
		{2, 33, 2},	//[2][49]=[ 10][110001]->{ 10,100001,2}
		{1, 2, 1},	//[2][50]=[ 10][110010]->{  1,    10,1}
		{1, 2, 1},	//[2][51]=[ 10][110011]->{  1,    10,1}
		{2, 32, 1},	//[2][52]=[ 10][110100]->{ 10,100000,1}
		{2, 33, 2},	//[2][53]=[ 10][110101]->{ 10,100001,2}
		{1, 2, 1},	//[2][54]=[ 10][110110]->{  1,    10,1}
		{1, 2, 1},	//[2][55]=[ 10][110111]->{  1,    10,1}
		{1, 8, 1},	//[2][56]=[ 10][111000]->{  1,  1000,1}
		{1, 8, 1},	//[2][57]=[ 10][111001]->{  1,  1000,1}
		{1, 10, 2},	//[2][58]=[ 10][111010]->{  1,  1010,2}
		{1, 10, 2},	//[2][59]=[ 10][111011]->{  1,  1010,2}
		{1, 8, 1},	//[2][60]=[ 10][111100]->{  1,  1000,1}
		{1, 8, 1},	//[2][61]=[ 10][111101]->{  1,  1000,1}
		{1, 10, 2},	//[2][62]=[ 10][111110]->{  1,  1010,2}
		{1, 10, 2},	//[2][63]=[ 10][111111]->{  1,  1010,2}
	},
	{
		{65535, 0, 0},	//[3][0]=[ 11][     0]->{111,     0,0}
		{3, 1, 1},	//[3][1]=[ 11][     1]->{ 11,     1,1}
		{3, 2, 1},	//[3][2]=[ 11][    10]->{ 11,    10,1}
		{3, 3, 2},	//[3][3]=[ 11][    11]->{ 11,    11,2}
		{5, 4, 1},	//[3][4]=[ 11][   100]->{101,   100,1}
		{3, 1, 1},	//[3][5]=[ 11][   101]->{ 11,     1,1}
		{3, 2, 1},	//[3][6]=[ 11][   110]->{ 11,    10,1}
		{3, 3, 2},	//[3][7]=[ 11][   111]->{ 11,    11,2}
		{5, 8, 1},	//[3][8]=[ 11][  1000]->{101,  1000,1}
		{3, 1, 1},	//[3][9]=[ 11][  1001]->{ 11,     1,1}
		{3, 2, 1},	//[3][10]=[ 11][  1010]->{ 11,    10,1}
		{3, 3, 2},	//[3][11]=[ 11][  1011]->{ 11,    11,2}
		{5, 12, 2},	//[3][12]=[ 11][  1100]->{101,  1100,2}
		{3, 1, 1},	//[3][13]=[ 11][  1101]->{ 11,     1,1}
		{3, 2, 1},	//[3][14]=[ 11][  1110]->{ 11,    10,1}
		{3, 3, 2},	//[3][15]=[ 11][  1111]->{ 11,    11,2}
		{6, 16, 1},	//[3][16]=[ 11][ 10000]->{110, 10000,1}
		{3, 1, 1},	//[3][17]=[ 11][ 10001]->{ 11,     1,1}
		{3, 2, 1},	//[3][18]=[ 11][ 10010]->{ 11,    10,1}
		{3, 3, 2},	//[3][19]=[ 11][ 10011]->{ 11,    11,2}
		{5, 4, 1},	//[3][20]=[ 11][ 10100]->{101,   100,1}
		{3, 1, 1},	//[3][21]=[ 11][ 10101]->{ 11,     1,1}
		{3, 2, 1},	//[3][22]=[ 11][ 10110]->{ 11,    10,1}
		{3, 3, 2},	//[3][23]=[ 11][ 10111]->{ 11,    11,2}
		{5, 8, 1},	//[3][24]=[ 11][ 11000]->{101,  1000,1}
		{3, 1, 1},	//[3][25]=[ 11][ 11001]->{ 11,     1,1}
		{3, 2, 1},	//[3][26]=[ 11][ 11010]->{ 11,    10,1}
		{3, 3, 2},	//[3][27]=[ 11][ 11011]->{ 11,    11,2}
		{5, 12, 2},	//[3][28]=[ 11][ 11100]->{101,  1100,2}
		{3, 1, 1},	//[3][29]=[ 11][ 11101]->{ 11,     1,1}
		{3, 2, 1},	//[3][30]=[ 11][ 11110]->{ 11,    10,1}
		{3, 3, 2},	//[3][31]=[ 11][ 11111]->{ 11,    11,2}
		{6, 32, 1},	//[3][32]=[ 11][100000]->{110,100000,1}
		{3, 1, 1},	//[3][33]=[ 11][100001]->{ 11,     1,1}
		{3, 2, 1},	//[3][34]=[ 11][100010]->{ 11,    10,1}
		{3, 3, 2},	//[3][35]=[ 11][100011]->{ 11,    11,2}
		{5, 4, 1},	//[3][36]=[ 11][100100]->{101,   100,1}
		{3, 1, 1},	//[3][37]=[ 11][100101]->{ 11,     1,1}
		{3, 2, 1},	//[3][38]=[ 11][100110]->{ 11,    10,1}
		{3, 3, 2},	//[3][39]=[ 11][100111]->{ 11,    11,2}
		{5, 8, 1},	//[3][40]=[ 11][101000]->{101,  1000,1}
		{3, 1, 1},	//[3][41]=[ 11][101001]->{ 11,     1,1}
		{3, 2, 1},	//[3][42]=[ 11][101010]->{ 11,    10,1}
		{3, 3, 2},	//[3][43]=[ 11][101011]->{ 11,    11,2}
		{5, 12, 2},	//[3][44]=[ 11][101100]->{101,  1100,2}
		{3, 1, 1},	//[3][45]=[ 11][101101]->{ 11,     1,1}
		{3, 2, 1},	//[3][46]=[ 11][101110]->{ 11,    10,1}
		{3, 3, 2},	//[3][47]=[ 11][101111]->{ 11,    11,2}
		{6, 48, 2},	//[3][48]=[ 11][110000]->{110,110000,2}
		{3, 1, 1},	//[3][49]=[ 11][110001]->{ 11,     1,1}
		{3, 2, 1},	//[3][50]=[ 11][110010]->{ 11,    10,1}
		{3, 3, 2},	//[3][51]=[ 11][110011]->{ 11,    11,2}
		{5, 4, 1},	//[3][52]=[ 11][110100]->{101,   100,1}
		{3, 1, 1},	//[3][53]=[ 11][110101]->{ 11,     1,1}
		{3, 2, 1},	//[3][54]=[ 11][110110]->{ 11,    10,1}
		{3, 3, 2},	//[3][55]=[ 11][110111]->{ 11,    11,2}
		{5, 8, 1},	//[3][56]=[ 11][111000]->{101,  1000,1}
		{3, 1, 1},	//[3][57]=[ 11][111001]->{ 11,     1,1}
		{3, 2, 1},	//[3][58]=[ 11][111010]->{ 11,    10,1}
		{3, 3, 2},	//[3][59]=[ 11][111011]->{ 11,    11,2}
		{5, 12, 2},	//[3][60]=[ 11][111100]->{101,  1100,2}
		{3, 1, 1},	//[3][61]=[ 11][111101]->{ 11,     1,1}
		{3, 2, 1},	//[3][62]=[ 11][111110]->{ 11,    10,1}
		{3, 3, 2},	//[3][63]=[ 11][111111]->{ 11,    11,2}
	},
	{
		{65535, 0, 0},	//[4][0]=[100][     0]->{111,     0,0}
		{4, 1, 1},	//[4][1]=[100][     1]->{100,     1,1}
		{4, 2, 1},	//[4][2]=[100][    10]->{100,    10,1}
		{4, 3, 2},	//[4][3]=[100][    11]->{100,    11,2}
		{2, 4, 1},	//[4][4]=[100][   100]->{ 10,   100,1}
		{2, 4, 1},	//[4][5]=[100][   101]->{ 10,   100,1}
		{2, 4, 1},	//[4][6]=[100][   110]->{ 10,   100,1}
		{2, 4, 1},	//[4][7]=[100][   111]->{ 10,   100,1}
		{2, 8, 1},	//[4][8]=[100][  1000]->{ 10,  1000,1}
		{2, 8, 1},	//[4][9]=[100][  1001]->{ 10,  1000,1}
		{2, 8, 1},	//[4][10]=[100][  1010]->{ 10,  1000,1}
		{2, 8, 1},	//[4][11]=[100][  1011]->{ 10,  1000,1}
		{2, 12, 2},	//[4][12]=[100][  1100]->{ 10,  1100,2}
		{2, 12, 2},	//[4][13]=[100][  1101]->{ 10,  1100,2}
		{2, 12, 2},	//[4][14]=[100][  1110]->{ 10,  1100,2}
		{2, 12, 2},	//[4][15]=[100][  1111]->{ 10,  1100,2}
		{1, 16, 1},	//[4][16]=[100][ 10000]->{  1, 10000,1}
		{1, 16, 1},	//[4][17]=[100][ 10001]->{  1, 10000,1}
		{1, 16, 1},	//[4][18]=[100][ 10010]->{  1, 10000,1}
		{1, 16, 1},	//[4][19]=[100][ 10011]->{  1, 10000,1}
		{1, 16, 1},	//[4][20]=[100][ 10100]->{  1, 10000,1}
		{1, 16, 1},	//[4][21]=[100][ 10101]->{  1, 10000,1}
		{1, 16, 1},	//[4][22]=[100][ 10110]->{  1, 10000,1}
		{1, 16, 1},	//[4][23]=[100][ 10111]->{  1, 10000,1}
		{1, 16, 1},	//[4][24]=[100][ 11000]->{  1, 10000,1}
		{1, 16, 1},	//[4][25]=[100][ 11001]->{  1, 10000,1}
		{1, 16, 1},	//[4][26]=[100][ 11010]->{  1, 10000,1}
		{1, 16, 1},	//[4][27]=[100][ 11011]->{  1, 10000,1}
		{1, 16, 1},	//[4][28]=[100][ 11100]->{  1, 10000,1}
		{1, 16, 1},	//[4][29]=[100][ 11101]->{  1, 10000,1}
		{1, 16, 1},	//[4][30]=[100][ 11110]->{  1, 10000,1}
		{1, 16, 1},	//[4][31]=[100][ 11111]->{  1, 10000,1}
		{1, 32, 1},	//[4][32]=[100][100000]->{  1,100000,1}
		{1, 32, 1},	//[4][33]=[100][100001]->{  1,100000,1}
		{1, 32, 1},	//[4][34]=[100][100010]->{  1,100000,1}
		{1, 32, 1},	//[4][35]=[100][100011]->{  1,100000,1}
		{1, 32, 1},	//[4][36]=[100][100100]->{  1,100000,1}
		{1, 32, 1},	//[4][37]=[100][100101]->{  1,100000,1}
		{1, 32, 1},	//[4][38]=[100][100110]->{  1,100000,1}
		{1, 32, 1},	//[4][39]=[100][100111]->{  1,100000,1}
		{1, 32, 1},	//[4][40]=[100][101000]->{  1,100000,1}
		{1, 32, 1},	//[4][41]=[100][101001]->{  1,100000,1}
		{1, 32, 1},	//[4][42]=[100][101010]->{  1,100000,1}
		{1, 32, 1},	//[4][43]=[100][101011]->{  1,100000,1}
		{1, 32, 1},	//[4][44]=[100][101100]->{  1,100000,1}
		{1, 32, 1},	//[4][45]=[100][101101]->{  1,100000,1}
		{1, 32, 1},	//[4][46]=[100][101110]->{  1,100000,1}
		{1, 32, 1},	//[4][47]=[100][101111]->{  1,100000,1}
		{1, 48, 2},	//[4][48]=[100][110000]->{  1,110000,2}
		{1, 48, 2},	//[4][49]=[100][110001]->{  1,110000,2}
		{1, 48, 2},	//[4][50]=[100][110010]->{  1,110000,2}
		{1, 48, 2},	//[4][51]=[100][110011]->{  1,110000,2}
		{1, 48, 2},	//[4][52]=[100][110100]->{  1,110000,2}
		{1, 48, 2},	//[4][53]=[100][110101]->{  1,110000,2}
		{1, 48, 2},	//[4][54]=[100][110110]->{  1,110000,2}
		{1, 48, 2},	//[4][55]=[100][110111]->{  1,110000,2}
		{1, 48, 2},	//[4][56]=[100][111000]->{  1,110000,2}
		{1, 48, 2},	//[4][57]=[100][111001]->{  1,110000,2}
		{1, 48, 2},	//[4][58]=[100][111010]->{  1,110000,2}
		{1, 48, 2},	//[4][59]=[100][111011]->{  1,110000,2}
		{1, 48, 2},	//[4][60]=[100][111100]->{  1,110000,2}
		{1, 48, 2},	//[4][61]=[100][111101]->{  1,110000,2}
		{1, 48, 2},	//[4][62]=[100][111110]->{  1,110000,2}
		{1, 48, 2},	//[4][63]=[100][111111]->{  1,110000,2}
	},
	{
		{65535, 0, 0},	//[5][0]=[101][     0]->{111,     0,0}
		{5, 1, 1},	//[5][1]=[101][     1]->{101,     1,1}
		{6, 2, 1},	//[5][2]=[101][    10]->{110,    10,1}
		{5, 1, 1},	//[5][3]=[101][    11]->{101,     1,1}
		{3, 4, 1},	//[5][4]=[101][   100]->{ 11,   100,1}
		{3, 4, 1},	//[5][5]=[101][   101]->{ 11,   100,1}
		{3, 4, 1},	//[5][6]=[101][   110]->{ 11,   100,1}
		{3, 4, 1},	//[5][7]=[101][   111]->{ 11,   100,1}
		{6, 8, 1},	//[5][8]=[101][  1000]->{110,  1000,1}
		{5, 1, 1},	//[5][9]=[101][  1001]->{101,     1,1}
		{6, 10, 2},	//[5][10]=[101][  1010]->{110,  1010,2}
		{5, 1, 1},	//[5][11]=[101][  1011]->{101,     1,1}
		{3, 4, 1},	//[5][12]=[101][  1100]->{ 11,   100,1}
		{3, 4, 1},	//[5][13]=[101][  1101]->{ 11,   100,1}
		{3, 4, 1},	//[5][14]=[101][  1110]->{ 11,   100,1}
		{3, 4, 1},	//[5][15]=[101][  1111]->{ 11,   100,1}
		{3, 16, 1},	//[5][16]=[101][ 10000]->{ 11, 10000,1}
		{3, 16, 1},	//[5][17]=[101][ 10001]->{ 11, 10000,1}
		{3, 16, 1},	//[5][18]=[101][ 10010]->{ 11, 10000,1}
		{3, 16, 1},	//[5][19]=[101][ 10011]->{ 11, 10000,1}
		{3, 20, 2},	//[5][20]=[101][ 10100]->{ 11, 10100,2}
		{3, 20, 2},	//[5][21]=[101][ 10101]->{ 11, 10100,2}
		{3, 20, 2},	//[5][22]=[101][ 10110]->{ 11, 10100,2}
		{3, 20, 2},	//[5][23]=[101][ 10111]->{ 11, 10100,2}
		{3, 16, 1},	//[5][24]=[101][ 11000]->{ 11, 10000,1}
		{3, 16, 1},	//[5][25]=[101][ 11001]->{ 11, 10000,1}
		{3, 16, 1},	//[5][26]=[101][ 11010]->{ 11, 10000,1}
		{3, 16, 1},	//[5][27]=[101][ 11011]->{ 11, 10000,1}
		{3, 20, 2},	//[5][28]=[101][ 11100]->{ 11, 10100,2}
		{3, 20, 2},	//[5][29]=[101][ 11101]->{ 11, 10100,2}
		{3, 20, 2},	//[5][30]=[101][ 11110]->{ 11, 10100,2}
		{3, 20, 2},	//[5][31]=[101][ 11111]->{ 11, 10100,2}
		{5, 32, 1},	//[5][32]=[101][100000]->{101,100000,1}
		{5, 33, 2},	//[5][33]=[101][100001]->{101,100001,2}
		{5, 32, 1},	//[5][34]=[101][100010]->{101,100000,1}
		{5, 33, 2},	//[5][35]=[101][100011]->{101,100001,2}
		{3, 4, 1},	//[5][36]=[101][100100]->{ 11,   100,1}
		{3, 4, 1},	//[5][37]=[101][100101]->{ 11,   100,1}
		{3, 4, 1},	//[5][38]=[101][100110]->{ 11,   100,1}
		{3, 4, 1},	//[5][39]=[101][100111]->{ 11,   100,1}
		{5, 32, 1},	//[5][40]=[101][101000]->{101,100000,1}
		{5, 33, 2},	//[5][41]=[101][101001]->{101,100001,2}
		{5, 32, 1},	//[5][42]=[101][101010]->{101,100000,1}
		{5, 33, 2},	//[5][43]=[101][101011]->{101,100001,2}
		{3, 4, 1},	//[5][44]=[101][101100]->{ 11,   100,1}
		{3, 4, 1},	//[5][45]=[101][101101]->{ 11,   100,1}
		{3, 4, 1},	//[5][46]=[101][101110]->{ 11,   100,1}
		{3, 4, 1},	//[5][47]=[101][101111]->{ 11,   100,1}
		{3, 16, 1},	//[5][48]=[101][110000]->{ 11, 10000,1}
		{3, 16, 1},	//[5][49]=[101][110001]->{ 11, 10000,1}
		{3, 16, 1},	//[5][50]=[101][110010]->{ 11, 10000,1}
		{3, 16, 1},	//[5][51]=[101][110011]->{ 11, 10000,1}
		{3, 20, 2},	//[5][52]=[101][110100]->{ 11, 10100,2}
		{3, 20, 2},	//[5][53]=[101][110101]->{ 11, 10100,2}
		{3, 20, 2},	//[5][54]=[101][110110]->{ 11, 10100,2}
		{3, 20, 2},	//[5][55]=[101][110111]->{ 11, 10100,2}
		{3, 16, 1},	//[5][56]=[101][111000]->{ 11, 10000,1}
		{3, 16, 1},	//[5][57]=[101][111001]->{ 11, 10000,1}
		{3, 16, 1},	//[5][58]=[101][111010]->{ 11, 10000,1}
		{3, 16, 1},	//[5][59]=[101][111011]->{ 11, 10000,1}
		{3, 20, 2},	//[5][60]=[101][111100]->{ 11, 10100,2}
		{3, 20, 2},	//[5][61]=[101][111101]->{ 11, 10100,2}
		{3, 20, 2},	//[5][62]=[101][111110]->{ 11, 10100,2}
		{3, 20, 2},	//[5][63]=[101][111111]->{ 11, 10100,2}
	},
	{
		{65535, 0, 0},	//[6][0]=[110][     0]->{111,     0,0}
		{6, 1, 1},	//[6][1]=[110][     1]->{110,     1,1}
		{5, 2, 1},	//[6][2]=[110][    10]->{101,    10,1}
		{5, 2, 1},	//[6][3]=[110][    11]->{101,    10,1}
		{6, 4, 1},	//[6][4]=[110][   100]->{110,   100,1}
		{6, 5, 2},	//[6][5]=[110][   101]->{110,   101,2}
		{5, 2, 1},	//[6][6]=[110][   110]->{101,    10,1}
		{5, 2, 1},	//[6][7]=[110][   111]->{101,    10,1}
		{3, 8, 1},	//[6][8]=[110][  1000]->{ 11,  1000,1}
		{3, 8, 1},	//[6][9]=[110][  1001]->{ 11,  1000,1}
		{3, 8, 1},	//[6][10]=[110][  1010]->{ 11,  1000,1}
		{3, 8, 1},	//[6][11]=[110][  1011]->{ 11,  1000,1}
		{3, 8, 1},	//[6][12]=[110][  1100]->{ 11,  1000,1}
		{3, 8, 1},	//[6][13]=[110][  1101]->{ 11,  1000,1}
		{3, 8, 1},	//[6][14]=[110][  1110]->{ 11,  1000,1}
		{3, 8, 1},	//[6][15]=[110][  1111]->{ 11,  1000,1}
		{5, 16, 1},	//[6][16]=[110][ 10000]->{101, 10000,1}
		{5, 16, 1},	//[6][17]=[110][ 10001]->{101, 10000,1}
		{5, 18, 2},	//[6][18]=[110][ 10010]->{101, 10010,2}
		{5, 18, 2},	//[6][19]=[110][ 10011]->{101, 10010,2}
		{5, 16, 1},	//[6][20]=[110][ 10100]->{101, 10000,1}
		{5, 16, 1},	//[6][21]=[110][ 10101]->{101, 10000,1}
		{5, 18, 2},	//[6][22]=[110][ 10110]->{101, 10010,2}
		{5, 18, 2},	//[6][23]=[110][ 10111]->{101, 10010,2}
		{3, 8, 1},	//[6][24]=[110][ 11000]->{ 11,  1000,1}
		{3, 8, 1},	//[6][25]=[110][ 11001]->{ 11,  1000,1}
		{3, 8, 1},	//[6][26]=[110][ 11010]->{ 11,  1000,1}
		{3, 8, 1},	//[6][27]=[110][ 11011]->{ 11,  1000,1}
		{3, 8, 1},	//[6][28]=[110][ 11100]->{ 11,  1000,1}
		{3, 8, 1},	//[6][29]=[110][ 11101]->{ 11,  1000,1}
		{3, 8, 1},	//[6][30]=[110][ 11110]->{ 11,  1000,1}
		{3, 8, 1},	//[6][31]=[110][ 11111]->{ 11,  1000,1}
		{3, 32, 1},	//[6][32]=[110][100000]->{ 11,100000,1}
		{3, 32, 1},	//[6][33]=[110][100001]->{ 11,100000,1}
		{3, 32, 1},	//[6][34]=[110][100010]->{ 11,100000,1}
		{3, 32, 1},	//[6][35]=[110][100011]->{ 11,100000,1}
		{3, 32, 1},	//[6][36]=[110][100100]->{ 11,100000,1}
		{3, 32, 1},	//[6][37]=[110][100101]->{ 11,100000,1}
		{3, 32, 1},	//[6][38]=[110][100110]->{ 11,100000,1}
		{3, 32, 1},	//[6][39]=[110][100111]->{ 11,100000,1}
		{3, 40, 2},	//[6][40]=[110][101000]->{ 11,101000,2}
		{3, 40, 2},	//[6][41]=[110][101001]->{ 11,101000,2}
		{3, 40, 2},	//[6][42]=[110][101010]->{ 11,101000,2}
		{3, 40, 2},	//[6][43]=[110][101011]->{ 11,101000,2}
		{3, 40, 2},	//[6][44]=[110][101100]->{ 11,101000,2}
		{3, 40, 2},	//[6][45]=[110][101101]->{ 11,101000,2}
		{3, 40, 2},	//[6][46]=[110][101110]->{ 11,101000,2}
		{3, 40, 2},	//[6][47]=[110][101111]->{ 11,101000,2}
		{3, 32, 1},	//[6][48]=[110][110000]->{ 11,100000,1}
		{3, 32, 1},	//[6][49]=[110][110001]->{ 11,100000,1}
		{3, 32, 1},	//[6][50]=[110][110010]->{ 11,100000,1}
		{3, 32, 1},	//[6][51]=[110][110011]->{ 11,100000,1}
		{3, 32, 1},	//[6][52]=[110][110100]->{ 11,100000,1}
		{3, 32, 1},	//[6][53]=[110][110101]->{ 11,100000,1}
		{3, 32, 1},	//[6][54]=[110][110110]->{ 11,100000,1}
		{3, 32, 1},	//[6][55]=[110][110111]->{ 11,100000,1}
		{3, 40, 2},	//[6][56]=[110][111000]->{ 11,101000,2}
		{3, 40, 2},	//[6][57]=[110][111001]->{ 11,101000,2}
		{3, 40, 2},	//[6][58]=[110][111010]->{ 11,101000,2}
		{3, 40, 2},	//[6][59]=[110][111011]->{ 11,101000,2}
		{3, 40, 2},	//[6][60]=[110][111100]->{ 11,101000,2}
		{3, 40, 2},	//[6][61]=[110][111101]->{ 11,101000,2}
		{3, 40, 2},	//[6][62]=[110][111110]->{ 11,101000,2}
		{3, 40, 2},	//[6][63]=[110][111111]->{ 11,101000,2}
	},
	{
		{65535, 0, 0},	//[7][0]=[111][     0]->{111,     0,0}
		{7, 1, 1},	//[7][1]=[111][     1]->{111,     1,1}
		{7, 2, 1},	//[7][2]=[111][    10]->{111,    10,1}
		{7, 3, 2},	//[7][3]=[111][    11]->{111,    11,2}
		{7, 4, 1},	//[7][4]=[111][   100]->{111,   100,1}
		{7, 5, 2},	//[7][5]=[111][   101]->{111,   101,2}
		{7, 6, 2},	//[7][6]=[111][   110]->{111,   110,2}
		{7, 7, 3},	//[7][7]=[111][   111]->{111,   111,3}
		{7, 8, 1},	//[7][8]=[111][  1000]->{111,  1000,1}
		{7, 9, 2},	//[7][9]=[111][  1001]->{111,  1001,2}
		{7, 10, 2},	//[7][10]=[111][  1010]->{111,  1010,2}
		{7, 11, 3},	//[7][11]=[111][  1011]->{111,  1011,3}
		{7, 12, 2},	//[7][12]=[111][  1100]->{111,  1100,2}
		{7, 13, 3},	//[7][13]=[111][  1101]->{111,  1101,3}
		{7, 14, 3},	//[7][14]=[111][  1110]->{111,  1110,3}
		{7, 15, 4},	//[7][15]=[111][  1111]->{111,  1111,4}
		{7, 16, 1},	//[7][16]=[111][ 10000]->{111, 10000,1}
		{7, 17, 2},	//[7][17]=[111][ 10001]->{111, 10001,2}
		{7, 18, 2},	//[7][18]=[111][ 10010]->{111, 10010,2}
		{7, 19, 3},	//[7][19]=[111][ 10011]->{111, 10011,3}
		{7, 20, 2},	//[7][20]=[111][ 10100]->{111, 10100,2}
		{7, 21, 3},	//[7][21]=[111][ 10101]->{111, 10101,3}
		{7, 22, 3},	//[7][22]=[111][ 10110]->{111, 10110,3}
		{7, 23, 4},	//[7][23]=[111][ 10111]->{111, 10111,4}
		{7, 24, 2},	//[7][24]=[111][ 11000]->{111, 11000,2}
		{7, 25, 3},	//[7][25]=[111][ 11001]->{111, 11001,3}
		{7, 26, 3},	//[7][26]=[111][ 11010]->{111, 11010,3}
		{7, 27, 4},	//[7][27]=[111][ 11011]->{111, 11011,4}
		{7, 28, 3},	//[7][28]=[111][ 11100]->{111, 11100,3}
		{7, 29, 4},	//[7][29]=[111][ 11101]->{111, 11101,4}
		{7, 30, 4},	//[7][30]=[111][ 11110]->{111, 11110,4}
		{7, 31, 5},	//[7][31]=[111][ 11111]->{111, 11111,5}
		{7, 32, 1},	//[7][32]=[111][100000]->{111,100000,1}
		{7, 33, 2},	//[7][33]=[111][100001]->{111,100001,2}
		{7, 34, 2},	//[7][34]=[111][100010]->{111,100010,2}
		{7, 35, 3},	//[7][35]=[111][100011]->{111,100011,3}
		{7, 36, 2},	//[7][36]=[111][100100]->{111,100100,2}
		{7, 37, 3},	//[7][37]=[111][100101]->{111,100101,3}
		{7, 38, 3},	//[7][38]=[111][100110]->{111,100110,3}
		{7, 39, 4},	//[7][39]=[111][100111]->{111,100111,4}
		{7, 40, 2},	//[7][40]=[111][101000]->{111,101000,2}
		{7, 41, 3},	//[7][41]=[111][101001]->{111,101001,3}
		{7, 42, 3},	//[7][42]=[111][101010]->{111,101010,3}
		{7, 43, 4},	//[7][43]=[111][101011]->{111,101011,4}
		{7, 44, 3},	//[7][44]=[111][101100]->{111,101100,3}
		{7, 45, 4},	//[7][45]=[111][101101]->{111,101101,4}
		{7, 46, 4},	//[7][46]=[111][101110]->{111,101110,4}
		{7, 47, 5},	//[7][47]=[111][101111]->{111,101111,5}
		{7, 48, 2},	//[7][48]=[111][110000]->{111,110000,2}
		{7, 49, 3},	//[7][49]=[111][110001]->{111,110001,3}
		{7, 50, 3},	//[7][50]=[111][110010]->{111,110010,3}
		{7, 51, 4},	//[7][51]=[111][110011]->{111,110011,4}
		{7, 52, 3},	//[7][52]=[111][110100]->{111,110100,3}
		{7, 53, 4},	//[7][53]=[111][110101]->{111,110101,4}
		{7, 54, 4},	//[7][54]=[111][110110]->{111,110110,4}
		{7, 55, 5},	//[7][55]=[111][110111]->{111,110111,5}
		{7, 56, 3},	//[7][56]=[111][111000]->{111,111000,3}
		{7, 57, 4},	//[7][57]=[111][111001]->{111,111001,4}
		{7, 58, 4},	//[7][58]=[111][111010]->{111,111010,4}
		{7, 59, 5},	//[7][59]=[111][111011]->{111,111011,5}
		{7, 60, 4},	//[7][60]=[111][111100]->{111,111100,4}
		{7, 61, 5},	//[7][61]=[111][111101]->{111,111101,5}
		{7, 62, 5},	//[7][62]=[111][111110]->{111,111110,5}
		{7, 63, 6},	//[7][63]=[111][111111]->{111,111111,6}
	},
};

void patminlex::candidate::expandStacks(const gridPattern * const pair, int topKey, candidate *results, int &nResults) {
	//for a top row, obtain stack and cols permutations
	const gridPattern &gr = pair[(int)isTransposed];
	int rowGivens = gr.rows[(int)mapRowsBackward[0]];
	for(int stackPerm = 0; stackPerm < 6; stackPerm++) {
		int toTriplets[3];
		toTriplets[perm[stackPerm][0]] = (rowGivens >> 6) & 7;
		toTriplets[perm[stackPerm][1]] = (rowGivens >> 3) & 7;
		toTriplets[perm[stackPerm][2]] = (rowGivens >> 0) & 7;
		const bestTripletPermutation &bt0 = bestTripletPermutations[toTriplets[0]][63];
		if(bt0.bestResult > ((topKey >> 6) & 7))
			continue;
		const bestTripletPermutation &bt1 = bestTripletPermutations[toTriplets[1]][63];
		if(bt1.bestResult > ((topKey >> 3) & 7))
			continue;
		const bestTripletPermutation &bt2 = bestTripletPermutations[toTriplets[2]][63];
		if(bt2.bestResult > ((topKey >> 0) & 7))
			continue;
		//this stack permutation results in minimal top row. Store the expanded candidate.
		candidate &res = results[nResults++];
		res = *this;
		res.stacksPerm = stackPerm;
		res.colsPermMask[0] = bt0.resultMask;
		res.colsPermMask[1] = bt1.resultMask;
		res.colsPermMask[2] = bt2.resultMask;
	}
}

int patminlex::fromString(const char *txt, gridPattern& normal, gridPattern& transposed) {
	int src = 0; //pointer to a character in the given text
	int nGivens = 0;
	//gridPattern& normal = pair[0];
	//gridPattern& transposed = pair[1];
	transposed.rows[0] = 0;
	transposed.rows[1] = 0;
	transposed.rows[2] = 0;
	transposed.rows[3] = 0;
	transposed.rows[4] = 0;
	transposed.rows[5] = 0;
	transposed.rows[6] = 0;
	transposed.rows[7] = 0;
	transposed.rows[8] = 0;
	for(int row = 0; row < 9; row++) {
		int r = 0;
		for(int col = 0; col < 9; col++) {
			int c = txt[src]; //read the character src points to
			//if(c >= '1' && c <= '9') { //it is a "given", when input is ASCII
			if(c) { //it is a "given", when input is bytes 0..9
				nGivens++;
				r |= (1 << (8 - col)); //most significant bit is for c0, less significant for c8
				transposed.rows[col] |= (1 << (8 - row));
				//normal.digits[row][col] = transposed.digits[col][row] = c - '0'; //when input is ASCII
				normal.digits[row][col] = transposed.digits[col][row] = c; //when input is bytes 0..9
			}
			else {
				normal.digits[row][col] = transposed.digits[col][row] = 0;
			}
			src++; //move to next char
		}
		normal.rows[row] = r;
	}
	return nGivens;
}

int patminlex::bestTopRowScore(gridPattern &p) {
	//returns the smallest row after canonicalization of each row independently
	int x;
	int  amin = minCanNineBits[p.rows[0]];
	if(amin > (x = minCanNineBits[p.rows[1]])) amin = x;
	if(amin > (x = minCanNineBits[p.rows[2]])) amin = x;
	if(amin > (x = minCanNineBits[p.rows[3]])) amin = x;
	if(amin > (x = minCanNineBits[p.rows[4]])) amin = x;
	if(amin > (x = minCanNineBits[p.rows[5]])) amin = x;
	if(amin > (x = minCanNineBits[p.rows[6]])) amin = x;
	if(amin > (x = minCanNineBits[p.rows[7]])) amin = x;
	if(amin > (x = minCanNineBits[p.rows[8]])) amin = x;
	return amin;
}
const int patminlex::candidate::perm[6][3] =			{{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
const patminlex::candidate patminlex::candidate::defaultCandidate = {0, {-1,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,-1,-1}, 63, {63,63,63}};

void patminlex::map(const char* src, char* results) const {
	char *r = results;
    for(patminlex::mappers::const_iterator m = theMaps.begin(); m != theMaps.end(); m++) {
   		for(int i = 0; i < 81; i++) { //debug backward mapping, should display the original
   			r[i] = m->cell[i] == 99 ? 0 : m->label[(int)src[(int)m->cell[i]]];
   		}
   		r += 81;
    }
}

int patminlex::size() const {
	return (int)theMaps.size();
}
patminlex::patminlex(const char *source, char *result, action requestedAction, res* res, const void* const data) {
	candidate candidates[CAND_LIST_SIZE]; //rows 0,2,4,6,8
	candidate candidates1[CAND_LIST_SIZE]; //rows 1,3,5,7
	int minTopRowScores[2], minTopRowScore;
	gridPattern pair[2]; //original and transposed patterns

	int nGivens = fromString(source, pair[0], pair[1]); //compose the pair of the patterns for the original and transposed morph

	theMaps.clear();

	minTopRowScores[0] = bestTopRowScore(pair[0]);
	minTopRowScores[1] = bestTopRowScore(pair[1]);
	if(minTopRowScores[0] <= minTopRowScores[1])
		minTopRowScore = minTopRowScores[0];
	else
		minTopRowScore = minTopRowScores[1];

	//at this point the pattern for the top row is fixed
	result[0] = ((minTopRowScore >> 8) & 1);
	result[1] = ((minTopRowScore >> 7) & 1);
	result[2] = ((minTopRowScore >> 6) & 1);
	result[3] = ((minTopRowScore >> 5) & 1);
	result[4] = ((minTopRowScore >> 4) & 1);
	result[5] = ((minTopRowScore >> 3) & 1);
	result[6] = ((minTopRowScore >> 2) & 1);
	result[7] = ((minTopRowScore >> 1) & 1);
	result[8] = ((minTopRowScore     ) & 1);

	if(requestedAction == action::findMinPatternLE) {
		//comparing patterns, after identifying the larger top row, we know the pattern can't be canonicalized to <= one
		int i = std::memcmp(result, data, 9);
		if(i > 0) {
			*res = patminlex::res::resGT;
			return;
		}
		if(i < 0) {
			*res = patminlex::res::resLT;
			return;
		}
	}

	//step 1: determine top rows
	int nCurCandidates;
	int nNextCandidates;
	nCurCandidates = 0;
	for(int nowTransposed = 0; nowTransposed < 2; nowTransposed++) {
		if(minTopRowScores[nowTransposed] > minTopRowScore)
			continue;
		for(int topRow = 0; topRow < 9; topRow++) {
			if(minCanNineBits[pair[nowTransposed].rows[topRow]] > minTopRowScore)
				continue;
			//here we have a top row candidate
			candidate cand;
			cand.init(nowTransposed, topRow); //in the empty template fix only the transposition and row 0
			cand.expandStacks(pair, minTopRowScore, candidates, nCurCandidates); //fix all minimal stack permutations and store for later row expansion
		}
	}
	//here we have all top row candidates with fixed top row, stacks, and column permutation masks

	//step 2: expand rows
	candidate *curCandidates = candidates;	//read from here
	candidate *nextCandidates = candidates1; //add row and write here
	nNextCandidates = 0;
	for(int toRow = 1; toRow < 9; toRow++) {
		int bestTriplets0 = 7;
		int bestTriplets1 = 7;
		int bestTriplets2 = 7;
		if(requestedAction == action::findMinPatternLE) {
			char* rd = ((char*)data) + 9 * toRow;
			bestTriplets0 = (rd[0] << 2) | (rd[1] << 1) | rd[2];
			bestTriplets1 = (rd[3] << 2) | (rd[4] << 1) | rd[5];
			bestTriplets2 = (rd[6] << 2) | (rd[7] << 1) | rd[8];
		}
		int rowInBand = toRow % 3;
		for(int curCandidateIndex = 0; curCandidateIndex < nCurCandidates; curCandidateIndex++) {
			const candidate &old = curCandidates[curCandidateIndex];
			int startRow, endRow;
			if(rowInBand) {
				//combine with unmapped rows from the same band
				int band = old.mapRowsBackward[3 * (toRow / 3)] / 3;
				startRow = band * 3;
				endRow = startRow + 3;
			}
			else {
				//try any unmapped row
				startRow = 0;
				endRow = 9;
			}
			for(int fromRow = startRow; fromRow < endRow; fromRow++) {
				if(old.mapRowsForward[fromRow] >= 0)
					continue; //skip previously mapped rows
				int toTriplets[3];
				int rowGivens = pair[(int)old.isTransposed].rows[fromRow]; //stacks unmapped
				toTriplets[candidate::perm[(int)old.stacksPerm][0]] = (rowGivens >> 6);// & 7;
				toTriplets[candidate::perm[(int)old.stacksPerm][1]] = (rowGivens >> 3) & 7;
				toTriplets[candidate::perm[(int)old.stacksPerm][2]] = (rowGivens >> 0) & 7;
				const bestTripletPermutation &bt0 = bestTripletPermutations[toTriplets[0]][old.colsPermMask[0]];
				if(bt0.bestResult > bestTriplets0)
					continue;
				if(bt0.bestResult < bestTriplets0) {
					if(requestedAction == action::findMinPatternLE) {
						*res = patminlex::res::resLT;
						return;
					}
					nNextCandidates = 0;
					bestTriplets0 = bt0.bestResult;
					bestTriplets1 = 7;
					bestTriplets2 = 7;
				}
				const bestTripletPermutation &bt1 = bestTripletPermutations[toTriplets[1]][old.colsPermMask[1]];
				if(bt1.bestResult > bestTriplets1)
					continue;
				if(bt1.bestResult < bestTriplets1) {
					if(requestedAction == action::findMinPatternLE) {
						*res = patminlex::res::resLT;
						return;
					}
					nNextCandidates = 0;
					bestTriplets1 = bt1.bestResult;
					bestTriplets2 = 7;
				}
				const bestTripletPermutation &bt2 = bestTripletPermutations[toTriplets[2]][old.colsPermMask[2]];
				if(bt2.bestResult > bestTriplets2)
					continue;
				if(bt2.bestResult < bestTriplets2) {
					if(requestedAction == action::findMinPatternLE) {
						*res = patminlex::res::resLT;
						return;
					}
					nNextCandidates = 0;
					bestTriplets2 = bt2.bestResult;
				}
				//tests passed, output the new candidate
				candidate &next = nextCandidates[nNextCandidates++];
				next = old; //copy
				next.mapRowsForward[fromRow] = toRow;
				next.mapRowsBackward[toRow] = fromRow;
				next.colsPermMask[0] = bt0.resultMask;
				next.colsPermMask[1] = bt1.resultMask;
				next.colsPermMask[2] = bt2.resultMask;
			} //fromRow
		} //oldCandidateIndex
		//flip-flop the old/new
		candidate *tmp = curCandidates;
		curCandidates = nextCandidates;
		nextCandidates = tmp;
		nCurCandidates = nNextCandidates;
		nNextCandidates = 0;
		//store the best result
		char *r = &result[9 * toRow];
		r[0] = ((bestTriplets0 >> 2) & 1);
		r[1] = ((bestTriplets0 >> 1) & 1);
		r[2] = ((bestTriplets0     ) & 1);
		r[3] = ((bestTriplets1 >> 2) & 1);
		r[4] = ((bestTriplets1 >> 1) & 1);
		r[5] = ((bestTriplets1     ) & 1);
		r[6] = ((bestTriplets2 >> 2) & 1);
		r[7] = ((bestTriplets2 >> 1) & 1);
		r[8] = ((bestTriplets2     ) & 1);
	} //toRow
	//at this point we have result populated with 0 and 1 for minlex pattern

	if(requestedAction == action::findMinPattern) return;

	if(requestedAction == action::findMinPatternLE) {
		if(nCurCandidates == 0) {
			*res = patminlex::res::resGT;
		}
		else {
			int i = std::memcmp(result, data, 81);
			if(i == 0)
				*res = patminlex::res::resEQ;
			else {
				*res = patminlex::res::resLT;
			}
		}
		return;
	}

//	if(nCurCandidates == 0) {
//		fprintf(stderr, "bad news: no candidates for minlex due to program errors\n");
//	}

	//step 3: find the lexicographically minimal representative within the morphs,
	// this time taking into account the real values of the input givens

	mapper map;
	int minLex[81]; //the best result so far
	for(int i = 0; i < 81; i++) {
		minLex[i] = (result[i] << 5); //initially set to large values
	}
	for(int curCandidateIndex = 0; curCandidateIndex < nCurCandidates; curCandidateIndex++) {
		const candidate &target = curCandidates[curCandidateIndex];
		int toTriplets[3];
		toTriplets[candidate::perm[(int)target.stacksPerm][0]] = 0;
		toTriplets[candidate::perm[(int)target.stacksPerm][1]] = 3;
		toTriplets[candidate::perm[(int)target.stacksPerm][2]] = 6;
		for(int colsPerm0 = 0; colsPerm0 < 6; colsPerm0++) {
			if(((target.colsPermMask[0] >> colsPerm0) & 1) == 0)
				continue; //forbidden permutation
			int toColsInStack[9];
			toColsInStack[candidate::perm[colsPerm0][0]] = toTriplets[0];
			toColsInStack[candidate::perm[colsPerm0][1]] = toTriplets[0] + 1;
			toColsInStack[candidate::perm[colsPerm0][2]] = toTriplets[0] + 2;
			for(int colsPerm1 = 0; colsPerm1 < 6; colsPerm1++) {
				if(((target.colsPermMask[1] >> colsPerm1) & 1) == 0)
					continue; //forbidden permutation
				toColsInStack[3 + candidate::perm[colsPerm1][0]] = toTriplets[1];
				toColsInStack[3 + candidate::perm[colsPerm1][1]] = toTriplets[1] + 1;
				toColsInStack[3 + candidate::perm[colsPerm1][2]] = toTriplets[1] + 2;
				for(int colsPerm2 = 0; colsPerm2 < 6; colsPerm2++) {
					if(((target.colsPermMask[2] >> colsPerm2) & 1) == 0)
						continue; //forbidden permutation
					toColsInStack[6 + candidate::perm[colsPerm2][0]] = toTriplets[2];
					toColsInStack[6 + candidate::perm[colsPerm2][1]] = toTriplets[2] + 1;
					toColsInStack[6 + candidate::perm[colsPerm2][2]] = toTriplets[2] + 2;
					int labelPerm[10] = {0,0,0,0,0,0,0,0,0,0}; //label mapping is unknown
					int nextFreeLabel = 1;
					int nSet = 0; //the number of givens with positions set
					for(int toRow = 0; toRow < 9; toRow++) {
						int *rowGivens = pair[(int)target.isTransposed].digits[(int)target.mapRowsBackward[toRow]];
						for(int col = 0; col < 9; col++) {
							int fromDigit = rowGivens[toColsInStack[col]];
							if(fromDigit == 0)
								continue;
							if(labelPerm[fromDigit] == 0) {
								labelPerm[fromDigit] = nextFreeLabel++;
							}
							if(labelPerm[fromDigit] > minLex[toRow * 9 + col])
								goto nextColsPerm;
							nSet++;
							if(labelPerm[fromDigit] < minLex[toRow * 9 + col]) {
								//if(minLex[toRow * 9 + col] >= (1 << 5)) { //invalidate the rest only if they are touched
								//the following puzzle demonstrates this is a bug
								//................12.....1345..6.74..1.7.8.6.348.4312.76.8..25.635..6.7.2.6.2138.57
									for(int i = toRow * 9 + col + 1; i < 81; i++) {
										minLex[i] = (result[i] << 5); //invalidate the rest
									}
								//}
								minLex[toRow * 9 + col] = labelPerm[fromDigit]; //the best result so far
								//the buffered transformations become invalid at this point
								theMaps.clear();
							}
							if(nSet == nGivens) {
								//an isomorph of the currently best ordering
								//at this point we have the necessary information for the transformation and can buffer it (if eventually it is one of the best ones)
								for(int r = 0; r < 9; r++) {
									for(int c = 0; c < 9; c++) {
										int src = target.isTransposed ? target.mapRowsBackward[r] + 9 * toColsInStack[c] : target.mapRowsBackward[r] * 9 + toColsInStack[c]; //source cell index for target rc
										map.cell[src] = minLex[r * 9 + c] ? r * 9 + c : 99; //map all non-givens to 99, this masking irrelevant permutations
									}
								}
								for(int d = 0; d < 10; d++)
									map.label[d] = 0;
								for(int d = 0; d < 10; d++)
									map.label[labelPerm[d]] = d;
								map.label[0] = 0; //don't map zero to non-zero
								theMaps.insert(map); //this will automatically ignore duplicates
							}
						} //col
					} //toRow
nextColsPerm:
					;
				} //colsPerm2
			} //colsPerm1
		} //colsPerm0
	} //candidate
//	//if we expect result in ASCII
//	for(int i = 0; i < 81; i++) {
//		result[i] = minLex[i] ? minLex[i] + '0' : '.'; //copy the integers to chars
//	}
	for(int i = 0; i < 81; i++) {
		result[i] = minLex[i];
	}
}