Minor change to TedSetup

Utilities for editing Keen:Galaxy and Keen:Dreams levels.
User avatar
Shadow Master
Posts: 129
Joined: Fri Oct 20, 2006 3:14 pm
Location: Santiago, Chile
Contact:

Post by Shadow Master »

CK Guy wrote:And ShadowMaster - does this "end of creative output" you mentioned a while ago mean no EModKeen? (TRANSLATION: Would my editor have to directly manipulate the GAMEMAPS and MAPHEAD files, or could I just manipulate the decompressed MAPTEMP and MAPTHEAD relying on your program to do the compression?).
No, EModKeen is still in my To-do list. It just probably won't have progress for half a year or more, unless your interest is strong enough to kick my back so that I feel the need to get back to work.

However, obviously an editor is never complete if it has to rely on an external application to do its job. If you can write the code for compression and such yourself, it would be great for users, doesn't matter if EModKeen is released or not, because they would not have to install or run it manually first to edit levels.

Not sure if I did make sense.
User avatar
ckguy
Posts: 465
Joined: Tue Oct 14, 2003 11:20 am
Location: Wakefield, RI, US
Contact:

Post by ckguy »

Yes, I see what you're saying. Does Mindbelt's dependence on ModKeen count as incompleteness by your definition?

In any case, I'll proceed as though no EModKeen were forthcoming, and work out (de)compression routines looking at TEDSETUP's source.
User avatar
Shadow Master
Posts: 129
Joined: Fri Oct 20, 2006 3:14 pm
Location: Santiago, Chile
Contact:

Post by Shadow Master »

CK Guy wrote:Yes, I see what you're saying. Does Mindbelt's dependence on ModKeen count as incompleteness by your definition?
Not necessarily. If you distribute EModKeen with Mindbelt, there would be no incompleteness.

Neither if you just merge EModKeen's code into your program, but we warned, I shall GNU GPL mine, so you might have trouble with that, as it forces you to release your source code under the same license if you are linking it in your program.

So if I were afraid of having to GNU GPL Mindbelt, I'd rather write my own code, or ask users to download EModKeen separately, or distribute it in binary form along with the editor. Note that asking users to download it separately would have the advantage of them always getting the last version of EModKeen (it will be likely to be updated every week)*, while distributing it in binary form with tour program will have the disadvantage of you having to worry about when I did my last release.

Think about this.

(*) the disadvantage would be none except for clueless users who can't get the concept of "back-end".
User avatar
ckguy
Posts: 465
Joined: Tue Oct 14, 2003 11:20 am
Location: Wakefield, RI, US
Contact:

Post by ckguy »

Well, I was looking at tedsetup.c. Where the heck is the un-RLE code? It seems like the program doesn't even do that - I only see where it does the LZ-esque part of decarmackization.

I see it grabs the rle magic word from maphead and makes sure it's 0xABCD. But where is the un-rle code?? I'm a bit confused ...

[edit:] I'm positive that I read that the gamemaps file is first rle-compressed. I read this in TWO places, actually. mobydoc.txt, and "plumbing the depths of keen".

[edit again:] Aha! Or does ted5 expect that the maptemp file be rle-compressed and that's why tedsetup doesn't do that? (This seems likely, I'm checking out the ted5 source now.)

[edit yet again:] Garg, TED5's source is fucling incomprehensible. "Start of the beast from hell" ... John Romero wasn't kidding.
User avatar
adurdin
Site Founder
Posts: 549
Joined: Fri Aug 29, 2003 11:27 pm
Location: Edinburgh, Scotland
Contact:

Post by adurdin »

CK Guy wrote:I'm positive that I read that the gamemaps file is first rle-compressed... Or does ted5 expect that the maptemp file be rle-compressed and that's why tedsetup doesn't do that?
That is correct.
Garg, TED5's source is fucling incomprehensible.
It probably won't help that the rle decompression routines in it are written in assembly. You might want to check out the KeenWright source for rle [de]compression routines for comparison, although they're written in basic and not as concise as a C version would be.

So, here's some code from a stillborn C++ port of KeenWright:

Code: Select all

//compressor.cpp
#include <mem.h>
#include <iostream.h>
#include <stdio.h>
#include "kwerror.h"
#include "buffer.h"

#include "compressor.h"

HuffCompressor::HuffCompressor( word *dict ) {
	//Copy the passed dictionary into ours
	for( int i = 0; i < 255; i++ ) {
		Tree[ i ].bit0 = *dict++;
		Tree[ i ].bit1 = *dict++;
	}
}

HuffCompressor::HuffCompressor( istream& dictstream ) {
	//Read the dictionary
	dictstream.read( (byte *)Tree, 255 * sizeof( HuffNode ) );
}

error HuffCompressor::compress( Buffer& in, Buffer& out ) {
	//Not currently implemented
	return e_NoError;
}

error HuffCompressor::decompress( Buffer& in, Buffer& out ) {
	int curnode;
	word leaf;
	byte c,	mask;

	curnode = 254; //start at root of tree

	do {
		//input a byte and start with its lsb
		in >> c;
		mask = 1;

		//decompress this byte
		do {
			if( c & mask ) //if bit 1 set, use right node
				leaf = Tree[ curnode ].bit1;
			else //otherwise use left node
				leaf = Tree[ curnode ].bit0;

			if( leaf < 256 ) {
				//this leaf is a byte: output it.
				out << (byte)leaf;
				curnode = 254; //back to the root node
			} else {
				//this leaf points to another node, index in the low byte
				curnode = (leaf & 0xFF);
			}
			mask <<= 1;
		} while( mask && !out.eof() ); //Keep going until we pass the high bit, or we reach the end of either stream
	} while( !in.eof() && !out.eof() ); //Keep going until we reach the end of either stream

	return e_NoError;
}

error HuffCompressor::reset() {
	//reset byte decompression status
	DecompStatus.mask = 1;
	DecompStatus.c = 0;
}

//Decompress a single byte
error HuffCompressor::decompressbyte( Buffer& in, byte& outc ) {
	word leaf;
	int curnode = 254;

	//decompress a single byte
	do {
		if( DecompStatus.mask == 0 )
			DecompStatus.mask = 1;
		if( DecompStatus.mask == 1 )
			//input a byte and start with its lsb if necessary
			in >> DecompStatus.c;
		if( DecompStatus.c & DecompStatus.mask ) //if bit 1 set, use right node
			leaf = Tree[ curnode ].bit1;
		else //otherwise use left node
			leaf = Tree[ curnode ].bit0;

		if( leaf < 256 ) {
			//this leaf is a byte: output it.
			outc = (byte)leaf;
			curnode = 254; //back to the root node
		} else {
			//this leaf points to another node, index in the low byte
			curnode = (leaf & 0xFF);
		}
		DecompStatus.mask <<= 1;
	} while( curnode != 254 ); //Keep going until we return to the head node

	return e_NoError;
}

int CarmackCompressor::decompress( Buffer& in, Buffer& out ) {
	int uncmplen = 0;

	while( !in.eof() && !out.eof() ) {
		word s;
		in >> s;
		if( (s & 0xFF00) == 0xA700 ) {
			byte m, n = (byte)(s & 0xFF);
			in >> m;
			if( n == 0 ) {	//special case: we have a word 0xA700 | m
				out << (word)(0xA700 | m );
				uncmplen += 2;
			} else {
				while( n-- ) {
					out << out.getword( uncmplen - 2*m );
					uncmplen += 2;
				}
			}
		} else if( (s & 0xFF00) == 0xA800 ) {
			word m;
			byte n = (byte)(s & 0xFF);
			in >> m;
			if( n == 0 ) {	//special case: we have a word 0xA800 | m
				out << (word)(0xA800 | m );
				uncmplen += 2;
			} else {
				while( n-- ) {
					//The -2 adjusts for the offset in the file being calculated
					//with the unrlen word still present
					out << out.getword( 2*m-2 );
					m++;
					uncmplen += 2;
				}
			}
		} else {
			out << s;
			uncmplen += 2;
		}
	}
	return uncmplen;
}

#define NEARTAG	0xa7
#define FARTAG	0xa8

int CarmackCompressor::compress( Buffer& in, Buffer& out ) {
	int cmplen;
	MemoryBuffer incopy( in );


	//long CarmackCompress (unsigned far *source,long length, unsigned far *dest)
	int length = (incopy.length()+1)/2;
	word ch,chhigh;
	word *instart, *inptr, *inscan,
		 *stopscan;
	word *bestscan, beststring;
	word dist, maxstring, string, outlength;
	word nearrepeats, farrepeats;
	word dups, count;
	word newwords;

	// this compression method produces a stream of words
	// If the words high byte is NEARTAG or FARTAG, the low byte is a word
	// copy count from a position specified by either the next byte (relative)
	// or the next word (absolute), respectively.  A copy count of 0 means to
	// insert the next byte as the low byte of the tag into the output


	// set up
	instart = inptr = (word *)incopy.pointer();

	outlength = 0;

	nearrepeats = farrepeats = dups = 0;
	count = 10;
	newwords = 0;

	// compress
	do {
		ch = *inptr;

		// scan from start for patterns that match current data
		beststring = 0;
		for( inscan = instart; inscan < inptr; inscan++ ) {
			if( *inscan != ch )
				continue;

			maxstring = inptr - inscan;
			if( maxstring > length )
				maxstring = length;
			if( maxstring > 255 )
				maxstring = 255;

			string = 1;
			while( *(inscan + string) == *(inptr + string) && string < maxstring )
				string++;

			if(string >= beststring ) {
				beststring = string;
				bestscan = inscan;
			}
		}

		if( beststring > 1 && inptr - bestscan <= 255 ) {
			// near string
			out << (word)(beststring + (NEARTAG << 8));
			out << (byte)(inptr - bestscan);
			outlength += 3;
			nearrepeats++;
			inptr += beststring;
			length -= beststring;
		} else if( beststring > 2 )	{
			// far string
			out << (word)(beststring + (FARTAG << 8));
			out << (word)(bestscan - instart);
			outlength += 4;
			farrepeats++;
			inptr += beststring;
			length -= beststring;
		} else {
			// no compression
			chhigh = ch >> 8;
			if( chhigh == NEARTAG || chhigh == FARTAG ) {
				// special case of encountering a
				// tag word in the data stream
				// send a length of 0, and follow it with the real low byte
				out << (word)(ch & 0xff00);
				out << (byte)(ch & 0xff);
				outlength += 3;
				dups++;
			} else {
				out << ch;
				outlength += 2;
			}
			inptr++;
			length--;
			newwords++;
		}
	} while( length );

	return outlength;
}

RLEWCompressor::RLEWCompressor( word f ) {
	Flag = f;
}

int RLEWCompressor::decompress( Buffer& in, Buffer& out ) {
	int uncmplen = 0;
	word count, value;

	while( !in.eof() && !out.eof() ) {
		in >> value;
		count = 1;

		if( value == Flag ) {
			in >> count;
			in >> value;
		}
		while( count-- ) {
			out << value;
			uncmplen += 2;
		}
	}
	return uncmplen;
}

int RLEWCompressor::compress( Buffer& in, Buffer& out ) {
	int cmplen = 0;
	bool done = false;
  	word value, newvalue, count;

	in >> value;
	count = 1;
	do {
		in >> newvalue;
		if( in.lasterror() == e_InputPastEnd )
			done = true;
		else if( newvalue == value )
			count++;
		if( newvalue != value || done ) {
			if( count > 3  || value == Flag ) {
				out << Flag;
				out << count;
				out << value;
				cmplen += 6;
			} else {
				while( count-- ) {
					out << value;
					cmplen += 2;
				}
			}
			value = newvalue;
			count = 1;
		}
	} while( !done );

	return cmplen;
}

Code: Select all

//compressor.h
typedef struct {
	word bit0;
	word bit1;
} HuffNode;

class HuffCompressor {
  protected:
    HuffNode Tree[255];
	struct {
		byte mask;
		byte c;
	} DecompStatus;
  public:
    HuffCompressor( word *dict );
    HuffCompressor( istream& dictstream );
	error compress( Buffer& in, Buffer& out );
	error decompress( Buffer& in, Buffer& out );
	error decompressbyte( Buffer& in, byte& outc );
	error reset();
};

class CarmackCompressor {
  protected:
  public:
	int compress( Buffer& in, Buffer& out );
	int decompress( Buffer& in, Buffer& out );
};

class RLEWCompressor {
  protected:
	word Flag;
  public:
    RLEWCompressor( word f );
	int compress( Buffer& in, Buffer& out );
	int decompress( Buffer& in, Buffer& out );
};
Edit: Do I get the prize for longest post?
User avatar
ckguy
Posts: 465
Joined: Tue Oct 14, 2003 11:20 am
Location: Wakefield, RI, US
Contact:

Post by ckguy »

adurdin wrote:Edit: Do I get the prize for longest post?
You're a contender! (I resisted the urge to quote your whole post and then say "No.")

Anyway, thanks for these, I'll definitely check it out. I have the sneaking suspicion that I've seen that code somewhere before ... like in some zip file with mobydoc.txt and other stuff. I fiddled some more with the decompression stuff after my previous post, and got nowhere - hopefully this'll help.
Post Reply