[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Possibility of "64K only" filecracks?
On Jan 2, 12:05 pm, Steve Nickolas
<lyricalnan...@usotsuki.hoshinet.org> wrote:
> On Mon, 2 Jan 2012, BLuRry wrote:
> > Donkey Kong has a lot of empty space and repeating patterns -- I'm
> > sure that those images could be compressed down a lot smaller don't
> > you think? I'm more than happy to donate the compression/
> > decompression of Apple Game Server 3 for the cause. The decompressor
> > was written to decompress a stream of incoming data from a serial
> > port, but I'm sure that could be very easily translated to something
> > else. The compression was written in Java -- and there are conversion
> > routines to read images from gif/png so you could use screen grabs if
> > you don't feel like extracting the images directly. It shouldn't
> > munge the images with dithering if you use a close-enough palette (I
> > based the conversion palette off of a YIQ color mapping, so AppleWin
> > screen grabs that are 560x192 should come back 1:1.)
>
> > -B
>
> Hm. I *got* a compressor but I only know how to use it for SFX.
>
> http://hem.bredband.net/magli143/exo/
>
> But if it's as I think, maybe another means can be utilized, something
> like an RLE or block compression, that's simple enough to implement on
> 6502?
>
> -uso.
My compression is relatively simple: It's an RLE scheme based on
packbits, only optimized for two-byte patterns instead of one-byte
patterns. That handles solid-color filled areas in hi-res (since the
color bits flip on odd/even pixels) much more effectively. Likewise
if the number of differences is relatively low between screens you
could store successive images EOR'd from each other to maximize
compression. That's how the compression was written here, but it
should be pretty easy to adjust the code to do storage-only and keep
EOR mode off without having to rewrite it much.
DECOMPRESS ROUTINE: (Written for ACME assembler, should be pretty
easily translated to others)
----------------------------------------------------------------------------------------------------------------------------------------------------------
;NOTE: readByte should be a simple routine that does not destroy X or
Y and returns the next byte of data in A
;The data stream is zero-terminated.
decompress
; Pull destination address from first two bytes
jsr readByte
sta store+1
sta store2+1
jsr readByte
sta store+2
sta store2+2
main
jsr readByte
bne .1
rts ; Encountered 0 -- no more data
.1 bpl copy
; Copy 2-byte pattern N+2 times
and #$7f
tay
iny
iny ; $80 means 2 instances of the same pattern,
etc
jsr readByte
sta PAT1+1
XOR_FAST beq possibleSkip ;Skip over areas with zero's -- should
only happen when in XOR mode!
; lda #$15 ;Self-modifying code changes it to this
when in STORE-only mode
jsr readByte
sta PAT2+1
.2
PAT1 lda #$00
jsr store
PAT2 lda #$00
jsr store
dey
bne .2
beq main
possibleSkip
jsr readByte
sta PAT2+1
bne .2
skipPattern
tya
asl
bcc noOverflow ; Handle cases where carry set afer ASL
inc store+2
inc store2+2
noOverflow
clc
adc store+1
sta store+1
sta store2+1
lda #$00
adc store+2
sta store+2
sta store2+2
jmp main
copy ; Copy N bytes directly as-is
tay
sec
sbc #$7D ; If value <= 7D, carry will be
cleared
bcc copy1
lsr ; if value was 7e, A will be 1 -- if
7f, A will be 2
ror ; Shift 3 places over (so 1 -> 40, 2 -
> 80)
ror
adc #$0D ; Add D (carry should have been
cleared by now)
sta store ; Update opcode at "store" routine (7E
-> 4D = EOR, 7F -> 8D = STA)
; Short out the XOR logic that skips
over areas of zeros if need be...
eor #$BD ; 4D -> F0, 8D -> 30
bmi hackjob
lda #$A9 ; LDA IMM (bypasses b ranch logic
altogether)
hackjob sta XOR_FAST
jmp main ; No convenient way to do this with
relative branching (V flag, maybe?)
copy1 jsr readByte
jsr store
dey
bne copy1
beq main
store eor $1000
store2 sta $1000
inc store+1
inc store2+1
bne .4
inc store+2
inc store2+2
.4 rts
----------------------------------------------------------------------------------------------------------------------------------------------------------
COMPRESS ROUTINES: (Java)
----------------------------------------------------------------------------------------------------------------------------------------------------------
// Starts off as True because assembly code starts off with EOR
public static boolean XOR_MODE = true;
// TC7
private static boolean isInScreenhole(int i) {
// There are 64 locations unused in text modes
// There are 512 locations unused in hires modes
// Screenholes appear in each bank from x78 thru x7f and xf8
thru xff
return ((i & 0x07f) >= 0x078);
}
private static int countReps(byte[] data, int baseAddress, int
offset) {
if (offset >= data.length - 4) {
return -1;
}
// Just in case we start this within a screenhole, which might
not be as efficient!
int start = offset;
// TC8 : Scan ahead to take pattern from end of screenhole
// Results in a marginal compression increase, but introduces errors
(?)
// while (isInScreenhole(baseAddress + start) && start <
data.length-4) {
// start += 2;
// }
byte b1 = data[start];
byte b2 = data[start + 1];
int numberReps = -1;
int seek = offset+2;
while (numberReps < 127 && seek < data.length-2) {
if ((b1 == data[seek] || isInScreenhole(baseAddress +
seek))
&& (b2 == data[seek+1] || isInScreenhole(baseAddress +
seek+1))) {
seek += 2;
numberReps++;
} else {
break;
}
}
return numberReps;
}
/**
* Packbits compression scheme:
* first two bytes = base address (little endian format)
* Repetitions of:
* Length, Data 1, Data 2 ... Data (length)
* Where 00-7B = Length of uncompressed data (copy Data 1, Data
2... as is)
* and 80-FF = Length of compressed data (length - 0x7E)
repetitions of Data 1 and Data 2
* 7E = Switch to XOR (for large areas with no changes)
* 7F = Switch to write mode (for large areas of same color/
pattern)
* Until end:
* 00 = end;
* @param baseAddress destination base address
* @param xorFrame Data xor'd against previous frame, should be
same size as newFrame (or null, if not available)
* @param newFrame New frame to store
* @return packed data
*/
public static byte[] packbits(int baseAddress, byte[] xorFrame,
byte[] newFrame) {
boolean XOR_ALLOWED = true;
byte[] data = XOR_MODE ? xorFrame : newFrame;
List<Byte> out = new ArrayList<Byte>();
out.add((byte) (0x0ff & baseAddress));
out.add((byte) ((0x0ff00 & baseAddress) >> 8));
if (xorFrame == null) {
// No previous frame to work against, disable XOR support
for this frame
XOR_ALLOWED = false;
// Flip mode to write mode
out.add((byte) 0x07F);
XOR_MODE = false;
data = newFrame;
}
int offset = 0;
while (offset < newFrame.length) {
boolean rawData = true;
// Pick mode...
int xcount = (XOR_ALLOWED ? countReps(xorFrame,
baseAddress, offset) : -1);
int ccount = countReps(newFrame, baseAddress, offset);
if (xcount > -1 || ccount > -1) {
rawData = false; // We are writing out
something compressed...
int numberReps = 0;
if (ccount > xcount || (ccount == xcount && !
XOR_MODE)) {
if (XOR_MODE) {
// Flip to data store mode only if feasible
out.add((byte) 0x07F);
XOR_MODE = false;
}
numberReps = ccount;
data = newFrame;
} else if (XOR_ALLOWED && (xcount > ccount || (xcount
== ccount && XOR_MODE))) {
if (!XOR_MODE) {
// Flip to XOR mode only if feasible and
allowed
out.add((byte) 0x07E);
XOR_MODE = true;
}
numberReps = xcount;
data = xorFrame;
}
byte size = (byte) (0x0ff & (128 + numberReps));
out.add(size);
out.add(data[offset]);
out.add(data[offset + 1]);
offset += numberReps * 2 + 4;
}
// No pattern, just output raw data until
// 1) We hit a repeating pattern
// 2) We hit end of data
// 3) We hit 125 characters
if (rawData) {
int seek = offset;
boolean foundPattern = false;
int count = 0;
while (seek < data.length && !foundPattern && count <
125) {
// Evaluate if packbits data follows, but
switching XOR MODE has a slight penalty
int copyCount = (XOR_MODE ? -1 : 0) +
countReps(newFrame, baseAddress, seek);
int xorCount = XOR_ALLOWED ? (XOR_MODE ? 0 : -1) +
countReps(xorFrame, baseAddress, seek) : -1;
if (copyCount > -1 || xorCount > -1) {
foundPattern = true;
// Read ahead +1 and see if better compression
would occur there (again, with XOR_MODE switch penalty)
int copyCount2 = (XOR_MODE ? -1 : 0) +
countReps(newFrame, baseAddress, seek + 1) - 1;
int xorCount2 = XOR_ALLOWED ? (XOR_MODE ? 0 :
-1) + countReps(xorFrame, baseAddress, seek + 1) - 1 : -1;
if (copyCount2 > copyCount || xorCount2 >
xorCount) {
// If there was a better deal by going up
one, use that instead
seek++;
count++;
}
} else {
seek++;
count++;
}
}
out.add((byte) (0x0ff & count));
for (int i = 0; i < count; i++) {
out.add(data[offset + i]);
}
offset = seek;
}
}
out.add((byte) 0);
// System.out.println("Packbits: "+input.length+" bytes
compressed to "+out.size()+" bytes ("+(100-(100*out.size()/
input.length))+"% compression)");
// Convert back to native array
byte[] result = new byte[out.size()];
for (int i = 0;
i < out.size();
i++) {
result[i] = out.get(i);
}
return result;
}
public static byte[] xor(byte[] b1, byte[] b2) {
if (b1.length != b2.length) {
return null;
}
byte[] out = new byte[b1.length];
for (int i = 0; i <
b1.length; i++) {
out[i] = (byte) (0x0ff & (b1[i] ^ b2[i]));
}
return out;
}
public static int countBeginningZeros(byte[] in) {
int index = 0;
while (index < in.length && in[index] == 0) {
index++;
}
return index;
}
public static int countEndingZeros(byte[] in) {
int count = 0;
int index = in.length - 1;
while (index >= 0 && in[index] == 0) {
index--;
count++;
}
return count;
}
public static byte[] subarray(byte[] input, int start, int length)
{
byte[] out = new byte[length];
for (int i = 0; i < length; i++) {
out[i] = input[start + i];
}
return out;
}
public static byte[] packScreenUpdate(int address, byte[]
oldFrame, byte[] newFrame) {
if (oldFrame != null) {
byte[] diff = xor(oldFrame, newFrame);
int z1 = countBeginningZeros(diff);
int z2 = countEndingZeros(diff);
if (z1 == oldFrame.length) {
// Protect against empty frames, nothing to do
// So return null and let caller deal with it.
return null;
}
address += z1;
// Get frames, truncating off parts at beginning and end
that do not change
byte[] xf1 = subarray(diff, z1, oldFrame.length - z1 -
z2);
byte[] nf1 = subarray(newFrame, z1, newFrame.length - z1 -
z2);
return packbits(address, xf1, nf1);
} else {
return packbits(address, null, newFrame);
}
}