C++ Libraries for Genesis Programming

[walker7]

When programming for the Sega Genesis or any other system, it might be a good idea to write your own libraries to encode the data however you want. You can also write libraries for finding the optimal setting for some things.

For example, I recently made my own Nemesis-compressor in C++. You will need the following includes:

Code: Select all

#include <vector>
#include "GenTile.h"
#include "InternalNNode.h"

typedef unsigned char byte;
typedef signed char sbyte;
typedef unsigned short int u16;
typedef signed short int s16;
typedef unsigned int u32;
typedef signed int s32;

Here is the routine itself. Input is a set of Genesis tiles and a boolean value to determine whether to XOR or not. Output is the compressed file, as a vector of bytes:

Code: Select all

vector<byte> Nemesis_Decomp(vector<GenesisTile> &f, bool xor) {
	// f = graphic file (consisting of sega genesis tiles)
	// xor = false for normal mode, true for xor mode

	// if using xor mode, xor the file
	if(xor) XOR_File(f);

	// determine all the pixel runs in the file
	vector<byte> runs;
	u32 cursor = 0, run_begin = 0, run_end = 0; u32 nybbles = f.size() << 6;

	while(cursor < nybbles) {
		u32 nybble, cur_nybble = Read_Nybble(f, cursor);
		cursor--; run_begin = cursor;
		do {nybble = Read_Nybble(f, cursor);} while(nybble == cur_nybble);
		if(nybble != -1) cursor--; run_end = cursor - 1;
		u32 run_length = run_end - run_begin + 1;
		while(run_length) {
			u32 run_bits = (run_length > 8) ? 8 : run_length;
			runs.push_back((run_bits - 1) << 4 | cur_nybble);
			run_length -= run_bits;}}

	// build a binary tree
	vector<InternalNNode> tree;
	for(u32 i=0; i<128; i++) tree.push_back(InternalNNode(0, i, 0, true, 0, 0));

	// count run types
	u32 num_runs = runs.size(); for(u32 i=0; i<num_runs; i++) tree[runs[i]].count++;

	// strip tree of zero-count runs
	for(s32 i=127; i>=0; --i) {if(!tree[i].count) tree.erase(tree.begin()+i);}

	// number the nodes
	u32 num_nodes = tree.size(); for(u32 i=0; i<num_nodes; i++) tree[i].id = i;
	u32 unique_runs = num_nodes;

	// link the nodes together into a tree
	vector<InternalNNode> queue = tree;
	while(num_nodes > 1) {
		// find the two nodes with lowest counts
		u32 node1, node2, lowest = ULONG_MAX; num_nodes = queue.size();
		for(u32 i=0; i<num_nodes; i++) {
			if(queue[i].count < lowest) {node1 = i; lowest = queue[i].count;}}
		InternalNNode n1 = queue[node1]; queue.erase(queue.begin()+node1);
		lowest = ULONG_MAX; num_nodes = queue.size();
		for(u32 i=0; i<num_nodes; i++) {
			if(queue[i].count < lowest) {node2 = i; lowest = queue[i].count;}}
		InternalNNode n2 = queue[node2]; queue.erase(queue.begin()+node2);

		// create a new node, and append it to both the tree and queue
		// the new node has a count that is the sum of both nodes' counts
		InternalNNode n3(tree.size(), -1, n1.count+n2.count, false, n1.id, n2.id);
		tree.push_back(n3); queue.push_back(n3);
	} queue.clear();

	// figure out the codebook
	u32 codes[128] = {0}, code_lengths[128] = {0}; num_nodes = tree.size();
	for(u32 i=0; i<unique_runs; i++) {
		u32 code = 0, code_length = 0, node = i, prev_node = node; u32 mask = 1;
		do {for(u32 j=unique_runs; j<num_nodes; j++) {
				if((tree[j].left==node) || (tree[j].right==node)) {node=j; break;}}
			u32 bit = (tree[node].left == prev_node) ? 0 : ~0;
			code |= (bit & mask); code_length++; prev_node = node; mask <<= 1;
		} while(node < (num_nodes-1));
		codes[tree[i].run] = code; code_lengths[tree[i].run] = code_length;}

	// make the codebook canonical
	byte current_code = 0;
	for(u32 i=1; i<=8; i++) {
		for(u32 j=0; j<128; j++) {if(code_lengths[j] == i) {
				codes[j] = current_code; current_code++;}} current_code <<= 1;}

	// remove any illegal codes, replacing them with the run's inline code
	for(u32 i=0; i<128; i++) {
		if(!Code_Valid(code_lengths[i], codes[i])) {
			code_lengths[i] = 13; codes[i] = 0x1F80 | i;}}
	
	// build the file; start with the number of tiles
	// it's a 16-bit value; if it's in xor mode, set bit 15
	vector<byte> file; file.clear();
	u16 num_tiles = f.size(); if(xor) num_tiles |= 0x8000;
	file.push_back(num_tiles >> 8); file.push_back(num_tiles & 0xFF);

	// push the tree data
	for(int i=0; i<16; i++) {
		// check to see if the value is present in any run
		bool found = false;
		for(int j=0; j<8; j++) found |= (code_lengths[(j << 4) | i] <= 8);
		
		if(found) {file.push_back(0x80 | i);
			for(int j=0; j<8; j++) {u32 run = (j << 4) | i;
				if(code_lengths[run] <= 8) {
					file.push_back((j << 4) | code_lengths[run]);
					file.push_back(codes[run]);}}}
	} file.push_back(~0);

	// now the best part: the data
	u32 run_count = runs.size(), acc = 0, bit_count = 0;
	for(u32 i=0; i<run_count; i++) {
		// put a code into the accumulator
		u32 run = runs[i];
		bit_count += code_lengths[run];
		acc = (acc << code_lengths[run]) | codes[run];

		// if there are at least 8 bits in the accumulator, write any full bytes
		while(bit_count > 8) {
			bit_count -= 8; file.push_back((acc >> bit_count) & 0xFF);}
	}
	// if there are any bits in the accumulator, pad the remaining bits with 0s
	if(bit_count) {acc <<= (8 - bit_count); file.push_back(acc & 0xFF);}

	// shrink the file to fit, xor back if it was in xor mode, and output file
	file.shrink_to_fit(); if(xor) InvXOR_File(f); return file;
}

Here's the bit that XOR's the file. The parameter f is a pointer to the file:

Code: Select all

void XOR_File(vector<GenesisTile> &f) {
	u32 tiles = f.size(), prev_row = 0, cur_row = 0;
	for(u32 i=0; i<tiles-1; i++) {for(u32 j=0; j<8; j++) {
			cur_row = f[i].pixels[j];
			f[i].pixels[j] = cur_row ^ prev_row;
			prev_row = cur_row;}}
}

And this does the inverse:

Code: Select all

void InvXOR_File(vector<GenesisTile> &f) {
	u32 tiles = f.size(), prev_row = 0, cur_row = 0;
	for(u32 i=0; i<tiles-1; i++) {for(u32 j=0; j<8; j++) {
			cur_row = f[i].pixels[j];
			f[i].pixels[j] = cur_row ^ prev_row;
			prev_row = f[i].pixels[j];}}
}

This piece of code reads a nybble. It's listed as inline because it is called a whole lot of times for any one file. As before, parameter f is a pointer to the file, and parameter c is which nybble to extract.

Code: Select all

inline u32 Read_Nybble(vector<GenesisTile> &f, u32 &c) {
	if(c >= (f.size() << 6)) return -1;
	int tile = c >> 6; int line = (c >> 3) & 7; int shift = (~c & 7) << 2;
	c++; return (f[tile].pixels[line] >> shift) & 0xF;
}

This piece of code tells whether a binary code is valid or not. The conditions for a valid code are:

• Must be between 1-8 bits
• Must not consist of all 1's
• If the code is at least 6 bits long, it must not start with 111111

Code: Select all

inline bool Code_Valid(u32 length, u32 code) {
	/* codes are rejected under 4 conditions: */

	/* condition 1: not between 1-8 bits */
	if(!length || (length > 8)) return false;

	/* condition 2: consists of all 1-bits */
	u32 mask = (1 << length) - 1; if(code == mask) return false;

	/* condition 3: starts with six 1-bits */
	if(length >= 6) {
		u32 shift = length - 6; if(((code >> shift) & 0x3F) == 0x3F) return false;}

	/* if none of these conditions are true, the code is valid */
	return true;
}

Here's "GenTile.h". It contains the class GenesisTile. It's a 32-byte string formatted just like an 8x8 tile.

Code: Select all

typedef unsigned int uint;

class GenesisTile {
public:
	uint pixels[8];

	GenesisTile();							// constructor
	~GenesisTile();							// destructor
	GenesisTile(const GenesisTile& x);		// copy constructor
};

GenesisTile::GenesisTile() {	// constructor
	for(int i=0; i<8; i++)	pixels[i] = 0;
}
GenesisTile::~GenesisTile() { // destructor
}
GenesisTile::GenesisTile(const GenesisTile& x) {	// copy constructor
	for(int i=0; i<8; i++)
		this->pixels[i] = x.pixels[i];
}

Here's "InternalNNode.h". The class InternalNNode is used when building the binary tree.

Code: Select all

#pragma once
typedef unsigned char byte;
typedef unsigned short int u16bit;
typedef unsigned int uint;

class InternalNNode {
public:
	byte id;					// node id
	byte run;					// corresponding run (symbol)
	uint count;					// frequency count
	bool node;					// node or leaf?
	byte left;					// left child
	byte right;					// right child

	InternalNNode();			// constructor
	~InternalNNode();			// destructor
	InternalNNode(byte i, byte s, uint c, bool n, byte l, byte r);	// parametrized constructor
	InternalNNode(const InternalNNode& x);							// copy constructor
};

InternalNNode::InternalNNode() {
	this->id = 0;
	this->run = 0;
	this->count = 0;
	this->node = false;
	this->left = 0;
	this->right = 0;
}
InternalNNode::~InternalNNode() {
}
InternalNNode::InternalNNode(byte i, byte s, uint c, bool n, byte l, byte r) {
	this->id = i;
	this->run = s;
	this->count = c;
	this->node = n;
	this->left = l;
	this->right = r;
}
InternalNNode::InternalNNode(const InternalNNode& x) {
	this->id = x.id;			// copy id
	this->run = x.run;			// copy run/symbol
	this->count = x.count;		// copy frequency count
	this->node = x.node;		// copy node/leaf status
	this->left = x.left;		// copy left child
	this->right = x.right;		// copy right child
}

To figure out which encoding mode to use, you call this twice. First is normal mode, then second is XOR mode. Whichever produces the smaller file size is the best one to use.

You could include this library in an application, and call it a bunch of times to compress many files. This can be done by passing a set of strings in an array. Each string is a filename. For every filename passed, the corresponding file is Nemesis-compressed. Or, you could pass just one string for the filename, put an asterisk where the variable part goes, and pass shorter strings. The shorter strings will take place of the asterisk in the filename. That allows for batch Nemesis compression.

Or maybe, put graphics in different orders, and choose whichever produced the smallest file size.

I might think of ways to improve this later.

Next, I'll be posting my Enigma compression library.

[walker7]

Here are my routines for Enigma compression:

This routine takes a vector of 16-bit values (unsigned short ints), and returns an Enigma-compressed file in a byte-vector. Make sure you have the typedefs mentioned in the first post of this thread.

Code: Select all

vector<byte> Enigma_Decomp(vector<u16> &f) {
	// f = mappings file
	vector<byte> file; file.clear();

	// find the highest and lowest mapping values
	u16 highest = 0, lowest = ~0; u16 size = f.size();
	for(int i=0; i<size; i++) {
		u16 map = f[i];
		if(map > highest) highest = map; if(map < lowest) lowest = map;}

	// look for the most common value
	u16 common, high_count = 0;
	for(u32 i=lowest; i<=highest; i++) {
		u32 count = 0; for(u32 j=0; j<size; j++) {if(f[j] == i) count++;}
		if(count > high_count) {common = i; high_count = count;}}

	// look for the most common incrementing value
	u16 increment = common; high_count = 0;
	for(u32 i=lowest; i<=highest; i++) {
		if(i == common)	continue; u32 count = 0; u16 value = i;
		for(u32 j=0; j<size; j++) {if(f[j] == value) {count++; value++;}}
		if(count > high_count) {increment = i; high_count = count;}}

	// discover the number of bits needed as well as the flags
	u16 mask = 0; for(u32 i=0; i<size; i++) mask |= f[i];
	byte flags = mask >> 11; u32 bits = 0; mask &= 0x7FF;
	while(mask) {mask >>= 1; bits++;} if(!bits) bits++;

	// push 6 bytes to the output, in this order;
	//		bits, flags, common value, incrementing value
	file.push_back(bits); file.push_back(flags);
	file.push_back(common >> 8); file.push_back(common & 0xFF);
	file.push_back(increment >> 8); file.push_back(increment & 0xFF);
	
	u32 cursor = 0, common_inc = increment;
	u32 data_length = 0, t_flags = flags;
	while(t_flags) {t_flags >>= 1; data_length++;}
	data_length += bits; u32 acc = 0, bit_count = 0;

	// compress the data
	while(cursor < size) {
		// grab up to 16 mappings
		u32 mappings = size - cursor; if(mappings > 16) mappings = 16;
		vector<u16> m; m.clear();
		for(u32 i=0; i<mappings; i++) m.push_back(f[cursor+i]);

		// initialize opcode output counts and bit counts
		u32 count[6] = {0}, data[6] = {6,6,7,7,7,7};

		// there are six different opcodes are used in enigma decompression
		// figure out which one produces the highest number of bits saved
	
		// case 1: string of common value
		for(u32 i=0; i<mappings; i++) {
			if(m[i] == common)	count[0]++; else break;}

		// case 2: string of incrementing value
		for(u32 i=0; i<mappings; i++) {
			if(m[i] == common_inc) {count[1]++;	common_inc++;} else break;}

		// case 3: string of constant inline value
		int value1 = m[0]; for(u32 i=0; i<mappings; i++) {
			if(m[i] == value1) {count[2]++; data[2] += data_length;} else break;}

		// case 4: string of incrementing inline value
		value1 = m[0]; for(u32 i=0; i<mappings; i++) {
			if(m[i] == value1) {count[3]++; value1++; data[3] += data_length;} else break;}

		// case 5: string of decrementing inline value
		value1 = m[0]; for(u32 i=0; i<mappings; i++) {
			if(m[i] == value1) {count[4]++; value1--; data[4] += data_length;} else break;}

		// case 6: string of inline values
		count[5] = (mappings > 15) ? 15 : mappings;
		data[5] += (data_length * count[5]);

		/* figure out which opcode has the highest difference between
		compressed/uncompressed file sizes */
		u32 opcode; s32 high_diff = INT_MIN;
		for(u32 i=0; i<5; i++) {
			if(!count[i]) continue; s32 diff = count[i]*16 - data[i];
			if(diff > high_diff) {opcode = i; high_diff = diff;}}

		// output the appropriate code
		u32 advance = count[opcode];
		byte codes[6] = {0, 1, 4, 5, 6, 7};			// codes
		byte code_lengths[6] = {2, 2, 3, 3, 3, 3};	// code lengths

		// add code/length bits to the accumulator
		acc = (acc << code_lengths[opcode]) | codes[opcode];
		acc = (acc << 4) | ((advance - 1) & 0xF);
		bit_count += (code_lengths[opcode] + 4);

		switch(opcode) {
		case 0:		// write common value
		case 1:		// write incrementing value
			while(bit_count >= 8) {
				bit_count -= 8;	file.push_back((acc >> bit_count) & 0xFF);}
			break;

		case 2:		// write inline constant value
		case 3:		// write inline incrementing value
		case 4:		// write inline decrementing value
			acc = (acc << data_length) | Condense_Mapping(m[0], flags, bits);
			bit_count += data_length;
			while(bit_count >= 8) {
				bit_count -= 8;	file.push_back((acc >> bit_count) & 0xFF);}
			break;

		case 5:		// write list of values
			for(u32 i=0; i<advance; i++) {
				acc = (acc << data_length) | Condense_Mapping(m[i], flags, bits);
				bit_count += data_length;
				while(bit_count >= 8) {
					bit_count -= 8;	file.push_back((acc >> bit_count) & 0xFF);}}
			break;

		default:	break;
		}
		
		cursor += advance;
	}
	
	/* append the bit sequence 1111111; if there are any leftover bits in the
	accumulator, pad to a multiple of 8 bits */
	acc = (acc << 7) | 0x7F; bit_count += 7;
	u32 bit_count2 = ((bit_count + 7) & -8) - bit_count;
	acc <<= bit_count2; bit_count += bit_count2;
	while(bit_count >= 8) {
		bit_count -= 8; file.push_back((acc >> bit_count) & 0xFF);}

	// shrink the file container to save memory, and output file
	file.shrink_to_fit(); return file;
}

And here is a helper function that condenses the mapping down to the appropriate number of bits, and stores flags if necessary:

Code: Select all

inline u16 Condense_Mapping(u16 &value, byte f, u32 b) {
	// value = 16-bit tile index
	// f = 5-bit tile flags
	// b = # of bits for tile index (1-11)
	u16 mapping = 0, mask1 = 0x8000; byte mask2 = 0x10;

	// incorporate flags
	for(int i=0; i<5; i++) {
		if(f & mask2) {
			u32 bit = (value & mask1) ? 1 : 0; mapping = (mapping << 1) | bit;}
		mask1 >>= 1; mask2 >>= 1;}

	// incorporate tile value
	u16 mask3 = (1 << b) - 1; mapping = (mapping << b) | (value & mask3);
	return mapping;
}

Now, here is an added bonus. These two snippets will let you read any file from your computer into a byte vector, or store from a byte vector to a file on your computer.

This piece of code opens a file as a byte vector.

• filename1 is the name of your file. It usually begins with "C:"

Code: Select all

vector<unsigned char> Open_File(string filename1) {
	// file1 is the byte-vector the file will be stored in
	// filename1 is the name of the file to store
	vector<unsigned char> file1;
	ifstream file; file.open(filename1, std::ifstream::binary);		// open file
	file.seekg(0, file.end);						// point to end of file
	unsigned int file_length = (unsigned int) file.tellg();			// get file length
	file.seekg(0, file.beg);						// point to beginning of file
	for(unsigned int i=0; i<file_length; i++) {file1.push_back(file.get());}	// read characters into vector
	file.close();							// close file
	return file1;							// return file
}

And this one takes a byte vector and stores it on your computer.

• As before, filename1 is the name of the file you want to be stored.
• file1 is the name of the byte-vector you want to store as a file.

Code: Select all

void Store_File(string filename1, vector<unsigned char> file1) {
	ofstream file; file.open(filename1, std::ifstream::binary); 		// open file
	unsigned int fsize = file1.size();					// get file size
	for(unsigned int i=0; i<fsize; i++) {file << file1[i];}			// read bytes into file
	file.close();							// store file
}

[Chilly Willy]

That's pretty nifty! It would be really nice if you made arcs of the files... that would be easier for people here rather than being forced to cut-n-paste from the post.

[Miquel]

I'm very shock by the usage of STD libraries, I suppose is supported by SGDK and gcc++ but unless you use it statically, fragmentation is going to be a huge problem in time. And if you use it statically what's the point of using it?