C++ Libraries for Genesis Programming

Talk about anything else you want

Moderator: BigEvilCorporation

Post Reply
walker7
Interested
Posts: 38
Joined: Tue Jul 24, 2012 6:27 am

C++ Libraries for Genesis Programming

Post by walker7 » Thu Oct 05, 2017 11:57 pm

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.
When programming, you can do it if you put your mind to it.

Post Reply

Who is online

Users browsing this forum: No registered users and 2 guests