|
Size: |
1 Kb
|
|
Upload Date: |
18.02.2013 - 0:05
|
|
Vote for us thanks! |
Note
0
bei
0
Bewertungen
|
|
Titel:
|
XIP
|
|
Total Downloads: |
3
|
|
Last Download Date: |
11.09.2014 - 17:07
|
|
Views:
|
122
|
|
Picture: |
|
|
Download Link:
|
|
|
Description: |
Sprache:
Englisch
xip -- small file smoosher
by S. Judd, July 2002
>>> PLEASE read this document carefully before using xip <<<
There are two very, very important things you *must* do to your program
if you want it to work with xip:
1) Change all instances of JSR $FFD2 to JSR $F1CA
2) Set the program origin to $7ae7
Where your program begins executing doesn't matter (you can set the JMP
address), but it will be decompressed to $7ae7, and JSR $FFD2 will no
longer work.
In place of 1) above, you might have to put a JSR $FF8A at the beginning
of your code if you use certain kernal routines (for printing numbers or
strings), or else replace those routines.
Once compressed, xip programs are autobooting and loaded ,8,1.
Explanation
-----------
"Every byte is sacred..."
Xip is designed for a very specific task: the 2002 1k minigame contest.
Every byte counts! It is optimized for maximum compression, and does this
by taking advantage of certain machine settings and characteristics.
To avoid having a BASIC header (SYS2059), the xip file is autobooting.
Normally this would not be practical, but xip uses a different technique:
it loads to $0326, which is the BSOUT system vector (what JSR $FFD2 jumps
through). This causes the program to run when the LOAD routine finishes
and tries to print READY. So instead of a 10-byte basic header, xip has
a 4-byte header (the first two bytes are the run address; the second two
are the STOP vector, which is called continuously by the LOAD routine).
BUT -- this means that JSR $FFD2 will no longer work. One solution is to
JSR $FF8A, but a simpler and more memory-effective technique is to just
use JSR $F1CA instead of JSR $FFD2 in your program. (Xip also hoses the
LOAD and SAVE vectors).
BUT BUT -- keep in mind that a number of kernal routines use FFD2 as well.
If you are using any kernal routines for output -- $BDCD or $AB1E for
example -- they will no longer work. If you need these routines, then
put a JSR $FF8A at the beginning of your code somewhere.
MOREOVER, to maximize space, xip uses a zero-page pointer to figure out
where to store code. And, of course, it uses the system initialized value,
to save bytes. One of the few practical (reliable, below $8000, not too
low in memory) locations is $73, part of the CHRGET routine, which contains
the value $7ae6 (inc $7a). The first thing the xip routine does is increment
this pointer, therefore it decompresses the code to $7ae7.
So, once again: change all JSR $FFD2 calls to JSR $F1CA, and make your
program assemble to $7ae7.
Using xip
---------
Well, it's super-easy. Load and run xip.
First, enter the file to load. Then enter the jump address (where the
decompression routine should JMP to to start your program). The program
will do it's thing, then ask you for a filename to save it under. Just
load that file ,8,1 and there ya go.
Troubleshooting
---------------
Really, the only thing xip messes up is the $FFD2 vector. If you have
a call to FFD2 (or a kernal routine which uses FFD2) hiding in your code
somewhere, the decompressor will get called, decode 256 bytes, and start
up your code again. It will keep doing this until it either overwrites
an important i/o location (like DCxx) or overwrites your program. So the
behavior to look for is something repetitive (like the screen continuously
clearing or flickering) and then a crash.
The only other thing xip does is write garbage to the screen area and part
of low memory ($08xx and beyond). Deterministic garbage, but garbage.
Since xip assumes certain zp values, the machine may have to be reset for
a xipped file to work correctly.
Maximizing compression
----------------------
Optimizing a program for xip is not very hard and can easily get you several
dozen more bytes.
Xip uses a very simple algorithm. It has to, to keep the decompression
routine small. All it does is assign n bits to the most common values,
and 9 bits to the rest. That's it. Here's how the decompression goes:
read the 1st bit
if bit=0, then read next n-1 bits, TAY, and look up value in table
if bit=1, then read next 8 bits
store value, increment pointers, and keep going
The decoding stops when the destination pointer hits $8000, which is one
reason the program is stored to $7ae7.
The key to maximizing compression is to maximize the frequency of the
most common bytes. For example, a common byte is $A9 (LDA #). In
zero page, location $a9 isn't used for anything, so if you choose $a9
instead of, say, $02 or $fe, you will get a lot more occurances of the
byte "$a9" in your program. Alternatively, if you have a choice between
"bcc" or "bne", opcode bne is $d0 -- and chances are there are plenty
of $d020 and such calls in your code.
The exact formula for data byte count is
literals + 1/8 (total bytes + (n-1)*(compressed bytes))
where
total bytes = literals + compressed bytes
and n is the number of bits used to compress a byte. But the table of
compressed values also has to be stored in the file, so that's another
2^(n-1) bytes. The point here is that
- uncompressed bytes (literals) are bad
- compressed bytes are good
- smaller compressed byte tables are good
So, the BEST case is having a "top-heavy" program -- just a few byte
values representing most of the program bytes. So wherever you can choose
a byte -- variables, instructions, lables, whatever -- choose wisely!
When you run the program, it lists the 64 most common bytes and how often
they occur. This is for the use of you, the programmer, as a tool to see
what you might do to get greater compression -- by switching variable names
around (both zp and absolute), perhaps using different instructions, etc.
Also it's just kind-of interesting :).
The program also lists the compression performance for various values of n,
the number of bits. If you see "USING N=5", that means that the top sixteen
bytes are being compressed (5 bits total: first bit is escape bit, 4 bits
used to represent bytes). In general, 2^(n-1) bytes are compressed, so
n=4 means 8 bytes, n=5 means 16 bytes, and n=6 means 32 compressed bytes.
In conjunction with the "64 most common bytes" printed above, this lets you
know exactly what byte values are being compressed.
Now, why $7ae7? I could have used $0801, for example, but the bit reader
works by ASLing bits out of memory. The decoder keeps reading bits and
outputting bytes until the output address hits $8000, which is a long ways
from $0801. So the bit reader is busy ASLing stuff starting at $03xx,
and the byte writer is gradually chugging towards $8000, and what happens
is that the program at $0801 gets ASL'd out of existence before the loop
gets to $8000. Make sense? Doesn't have to, just trust me :).
NOTE NOTE NOTE: the "bytes out" that xip reports DOES NOT include the
2-byte load address that heads every .PRG file. The minigame contest
counts those bytes, so don't be satisfied with $0400 bytes out!
Some common bytes and corresponding memory locations
-----------------
Remember: you can use zp locations (like $20), absolute locations like $2020,
and combined locations like $204c or whatever.
00 addr $00 don' mess wid' it!
$xx00 usually usable
10 bpl $10 basic flag; most usable
$1010 usable
$xx10 usual
18 clc $18 basic var (string pointer); most usable
$1818 usual
20 jsr $20 usable (basic var, string descriptors)
$2020 etc. etc.
30 bmi $30 usable (basic storage pointer)
38 sec $38 usable (top of BASIC mem)
4c jmp $3c usable (yet another BASIC pointer/work var)
60 rts $60 usable, if not using various BASIC routines (work var)
85 sta zp $85 part of CHRGET; usable if not using/exiting to BASIC
88 dey $88 same as above
8d sta abs $8d usable zp location -- RND seed
8e stx abs $8e usable -- RND seed
9d sta ,x $9d kernal flag; usable
a2 ldx # $a2 jiffy clock; updated by system IRQ; do not use if
system IRQ active
$a2a2 note we are now under BASIC ROMs
a5 lda zp $a5 usable; tape drive counter
a9 lda # $a9 usable zp location (RS-232 flag)
c8 iny $c8 usable if not using FFD2, PLOT, etc. (screen routines)
c9 cmp # $c9 same as above
ca dex $ca same
d0 bne, $d0 Flag used by CHRIN (input screen/keyboard); usable
i/o $d0xx i/o of course :)
$xxd0 usual
e8 inx $e8 screen line link table; ok if not using FFD2 etc.
and so on.
xip compression performance
---------------------------
Programs not optimized for compression:
Program Bytes in Bytes out Bytes saved
onek.o $0380 $036e 18
tfm.o $03fe $03d9 37
xip $04fb $04e0 27
dwcave1.prg $01f7 $0205 -14
tinyrinth $01fd $0214 -23
minima $07fb $084e -whatever
endprv2.prg $2322 $2219 264
lib3d.o $1a29 $190e 286
More optimized program:
tfm2.o $044b $0406 69
Notes:
- n=5 bits gave best performance on smaller programs; on larger programs
(minima, endprv, lib3d) n=6 gave best performance (just an observation).
- dwcave and tinyrinth are 512-byte programs
- minima is a 2k program, and already compressed (pucrunch)
- endprv2.prg is a demo page, already compressed (!)
Conclusions: this algorithm actually works, and optimizing programs really
pays off. What is amazing is that it works best for programs around 1k; I
didn't think it would perform well on large programs, but I guess byte
distributions scale with size. I am _really_ surprised that it worked so
poorly on the 512 byte programs, _esepcially_ when compared with the 1024 byte
programs -- that's what I originally designed the algorithm for! The byte
distributions must not scale downwards very well; maybe 512-byte programs must
be really optimized for this to work.
I was a little suprised that it compressed a compressed program, but then
again it's like performing Huffman compression on an LZ stream.
Anyways, comments and suggestions are always appreciated!
|
|
|
