decode_tree.cpp

這是一個arm模擬器 以C++實做 主要模擬ARM9架構

			<< endl;
#endif
	}

	if (this->scheme==DECODE_PATTERN) {	/* pattern decode */

		vector<DecodeTable *> subs = this->table->divide_by_pattern
			(minPatternMask, minPatternSignature);

		DecodeTreeNode *t1 = new DecodeTreeNode(subs[0]);
		DecodeTreeNode *t2 = new DecodeTreeNode(subs[1]);

		t1->decode(minUtilization);
		t2->decode(minUtilization);

		this->totalTableSize = t1->totalTableSize + t2->totalTableSize;
		this->totalNodeCount = t1->totalNodeCount + t2->totalNodeCount + 1; 
		this->children.push_back(t1);
		this->children.push_back(t2);

		this->height = t1->getHeight()*subs[0]->getProb() +
			t2->getHeight()*subs[1]->getProb() + 1;
		this->maxHeight = 1 + (t1->getMaxHeight()>t2->getMaxHeight()?
			t1->getMaxHeight():t2->getMaxHeight());
		this->minHeight = 1 + (t1->getMinHeight()<t2->getMinHeight()?
			t1->getMinHeight():t2->getMinHeight());

		this->pat_mask = minPatternMask;
		this->pat_signature = minPatternSignature;

	}
	else { /* table decode */ 

		vector<DecodeTable *> subs = this->table->divide_by_table(minTableMask,
			minTableBits, minTableShift);
		this->totalTableSize = 1<<minTableBits; //subs.size();
		this->totalNodeCount = 1;
		this->height = 1.0;
		this->maxHeight = 0;
		this->minHeight = (unsigned)-1;

		vector<DecodeTable *>::iterator it;
		for (it=subs.begin(); it!=subs.end(); it++) {
			DecodeTreeNode *t1 = new DecodeTreeNode(*it);
			t1->decode(minUtilization);
			this->totalTableSize += t1->totalTableSize;
			this->totalNodeCount += t1->totalNodeCount;
			this->children.push_back(t1);
			this->height += t1->getHeight()*(*it)->getProb();
			if (t1->getMaxHeight()>this->maxHeight)
				this->maxHeight = t1->getMaxHeight();
			if (t1->getMinHeight()<this->minHeight)
				this->minHeight = t1->getMinHeight();
		}

		this->maxHeight += 1;
		this->minHeight += 1;
		this->tab_mask= minTableMask;                      
		this->tab_shift = minTableShift;
	}

}

void DecodeTreeNode::emitXML(ostream& os, const string &indent)
{
	os << indent << "<table index=\"" << this->table->getIndex() 
		<< "\">" << endl;
	os << indent << "  <size>"<< this->table->getSize() << "</size>" << endl;

	switch (scheme) {
		case DECODE_NULL: {
			const vector<DecodeEntry>& entries = this->table->getEntries();
			vector<DecodeEntry>::const_iterator it;
			for (it=entries.begin(); it!=entries.end(); it++) {
				os << indent << "  <entry>"
					<< (*it).label << "  </entry>" << endl;
			}
			break;
		}
		case DECODE_PATTERN: {
			os << indent << "  <decode_pattern mask=\""
				<< PADDEDHEX << this->pat_mask
				<< "\" pattern=\""
				<< PADDEDHEX << this->pat_signature << "\"/>" << endl;
			break;
		}
		case DECODE_TABLE: {
			os << indent << "  <decode_table mask=\""
				<< PADDEDHEX << this->tab_mask
				<< "\"/>" << endl;
			break;
		}
	}

	vector<DecodeTreeNode *>::iterator it;
	for (it=children.begin(); it!=children.end(); it++)
		(*it)->emitXML(os, indent+"  ");

	os << indent <<  "  </table>" << endl;
}

static int static_label = 0;

void DecodeTreeNode::labelTableNode()
{
	switch(scheme) {
		case DECODE_TABLE: 
			this->label = static_label++;
		case DECODE_PATTERN: {
				vector<DecodeTreeNode *>::iterator it;
				for (it=children.begin(); it!=children.end(); it++) {
					(*it)->labelTableNode();
				}
			}
		default: break;
	}
}

void DecodeTreeNode::emitCStubDecs(ostream &os)
{
	switch(scheme) {
		case DECODE_TABLE: {
			vector<DecodeTreeNode *>::iterator it;
			for (it=children.begin(); it!=children.end(); it++) {
				if ((*it)->scheme!=DECODE_NULL)
					os << "_STUB_DEC(stub_" << dec << this->label
						<< "_" << (*it)->table->getIndex() << ")" << endl;
			}
		}
		case DECODE_PATTERN: {
			vector<DecodeTreeNode *>::iterator it;
			for (it=children.begin(); it!=children.end(); it++) {
				(*it)->emitCStubDecs(os);
			}
		}
		default: break;
	}
}

void DecodeTreeNode::emitCArrays(ostream &os)
{
	switch(scheme) {
		case DECODE_TABLE: {

			os << "/*" << endl << *(this->table);
			os << "Table Mask=" << PADDEDHEX
				<< this->tab_mask << "*/" << endl << endl;
			os << "_TABLE_DEF_BEGIN(table_" << dec << this->label
				<< ", " << children.size() << ")" << endl;

			vector<DecodeTreeNode *>::iterator it;
			for (it=children.begin(); it!=children.end(); it++) {
				if ((*it)->scheme!=DECODE_NULL) {
					os << "  _STUB_NAME(stub_" << dec << this->label
						<< "_" << (*it)->table->getIndex() << ")," << endl;
				}
				else if (((*it)->table)->getSize()>0) {
					DecodeTable *table = (*it)->table;
					os << "  _FUNC_NAME("
						<< (table->getEntries().front()).label
						<< ")," << endl;
				}
				else os << "  _FUNC_DEFAULT," << endl;
			}
			os << "_TABLE_DEF_END" << endl << endl;
		}
		case DECODE_PATTERN: {
			vector<DecodeTreeNode *>::iterator it;
			for (it=children.begin(); it!=children.end(); it++)
				(*it)->emitCArrays(os);
			break;
		}
		default: break;
	}
}

void DecodeTreeNode::emitCCode(ostream &os, const string& indent)
{
	switch(scheme) {
		case DECODE_TABLE:
			os << indent << "_TABLE_JUMP(table_" << dec << this->label
				<< ", " << PADDEDHEX << (this->tab_mask>>this->tab_shift)
				<< ", " << dec << this->tab_shift << ");" << endl;
			break;

		case DECODE_PATTERN:

			os << indent << "if _PATTERN_TRUE("
				<< PADDEDHEX << this->pat_mask << ", "
				<< PADDEDHEX << this->pat_signature << ") {" << endl;

			this->children[0]->emitCCode(os, indent+"  ");
			os << indent << "} else {" << endl;
			this->children[1]->emitCCode(os, indent+"  ");
			os << indent << "}" << endl;
			break;

		case DECODE_NULL:
			assert(this->table->getSize());
			os << indent << "_FUNC_CALL(" 
				<< (this->table->getEntries().front()).label
				<< ");" << endl;
		default: break;
	}
}

void DecodeTreeNode::emitCStubs(ostream &os)
{
	switch(scheme) {
		case DECODE_TABLE: {

			vector<DecodeTreeNode *>::iterator it;
			for (it=children.begin(); it!=children.end(); it++) {
				if ((*it)->scheme!=DECODE_NULL) {
					os << "_STUB_ENTRY(stub_" << dec << this->label
						<< "_" << (*it)->table->getIndex() << ")" << endl
						<< "{" << endl;
					(*it)->emitCCode(os);
					os << "}" << endl << endl;
				}
			}
		}
		case DECODE_PATTERN: {
				vector<DecodeTreeNode *>::iterator it;
				for (it=children.begin(); it!=children.end(); it++)
					(*it)->emitCStubs(os);
				break;
			}
		default:
			break;
	}
}

void DecodeTreeNode::emitC(ostream &os)
{
	/* first label all tables */
	labelTableNode();

	/* preamble of the file */
	os << "/*" << endl
		<< "Binary decoder synthesized by " PACKAGE " version " VERSION
	    << endl << endl;

	os << "Input statistics " << endl;
	os << "Total entries  : " << this->table->getEntries().size() << endl;
	os << "Unique labels  : " << this->table->getUSize() << endl;
	os << "Shannon entropy     : " << this->table->getEntropy() << endl;
	os << "Huffman tree height : " << this->table->getHTreeHeight() << endl;

	os << endl;
	os << "Decoder characteristics " << endl;
	os << "Gamma          : " << this->gamma << endl;
	os << "1 bit only     : " << do_onebit << endl;
	os << "Average height : " << this->height << endl;   
	os << "Maximum height : " << this->maxHeight << endl;   
	os << "Minimum height : " << this->minHeight << endl;   
	os << "Table entries  : " << this->totalTableSize << endl;
	os << "Total nodes    : " << this->totalNodeCount << endl;
	os << "*/" << endl << endl;

	/* include the C macro definition file */
	//os << "/* Include the C macro definition file */" << endl;
	//os << "#include \"autodecoder.h\"" << endl << endl;

	/* then emit the stubs function names */
	emitCStubDecs(os);
	os << endl;

	/* then emit the arrays */
	emitCArrays(os);
	os << endl;

	/* the emit the stubs functions */
	emitCStubs(os);
	os << endl;

	/* finally emit the decode routine */
	os << "_MAIN_DECODE_ENTRY" << endl << "{" << endl;
	emitCCode(os);
	os << "}" << endl;

	os << "/* End of decoder */" << endl;
}