Newsgroups: comp.sys.apple2.programmer Path: blue.weeg.uiowa.edu!news.uiowa.edu!uunet!comp.vuw.ac.nz!actrix.gen.nz!dempson From: dempson@atlantis.actrix.gen.nz (David Empson) Subject: Re: Data Compression & Need 2 Replace Chip Message-ID: Sender: news@actrix.gen.nz (News Administrator) Organization: Actrix - New Zealand Internet Service Providers Date: Fri, 10 Feb 1995 12:27:13 GMT References: <1995Feb6.214709.1@cnsvax.uwec.edu> X-Nntp-Posting-Host: atlantis.actrix.gen.nz Lines: 116 In article <1995Feb6.214709.1@cnsvax.uwec.edu>, wrote: > I'm wondering if there are any ways to highly compress Apple II > images. [snip] > Another thing I've taken an interest in is recording 1-bit music using > the paddle/joystick button ports, and here too compression would be > helpful (I'd also like to get any such programs others have put together > over the years). The output data is 0 for no sound, and 1 for sound, so > the data sometimes has long series of zeroes that I wish I could compress > to get more out of what RAM I've got. > RLE (run-length encoding) is vaguely okay, but it only works on data > that has long sequences of repeating data, and will oftentimes make > complex data files larger than their original size. If you have long streams of 1 and 0 bits in your input data, you can do a simple run-length compression on the 1-bit data, e.g. count up to 128 consecutive values and use the high order bit to indicate whether it was a one or a zero. The lower seven bits should be (number of samples minus 1). e.g. $00 means "0 input for 1 sample", $9E means "1 input for 31 ($1E + 1) samples". If the bursts tend to be shorter than 8 bits, this won't help. You could use a similar technique with 4 bit codes, i.e. a value and a count from 1 to 8. 3 bits could be messy to deal with, and doesn't give much compression. If your data is somewhat scattered, with several short bursts and occasional long ones, you could use some kind of table-based method. For example, a long sequence of zeros is quite likely (pauses in the sound), so an efficient method of encoding a large number of consecutive zeros is more likely to be useful than a large number of consecutive ones. Here is a simple example, using a fixed 4-bit code: 0000 = one 0 bit 0001 = one 1 bit 0010 = two 0 bits 0011 = two 1 bits 0100 = three 0 bits 0101 = three 1 bits 0110 = four 0 bits 0111 = four 1 bits 1000 = five 0 bits 1001 = five 1 bits 1010 = six 0 bits 1011 = six 1 bits 1100 = eight 0 bits 1101 = eight 1 bits 1110 = sixteen 0 bits 1111 = sixty four 0 bits You could get more elaborate that this, and use a variable length code, with shorter codes for more common run lengths and longer codes for less common ones. This is basically how Group 3 faxes are encoded - consecutive pixels of the same colour are counted, and a variable length code is used to represent the number of pixels. There are codes up to 13 bits long for run lengths of up to 63 pixels, then special codes for handling multiples of 64 pixels. Black and white runs always alternate, so different tables are used to handle each colour. In effect, this is a Huffman coding technique, using a fixed dictionary. There are three general types of compression: 1. Run-length encoding, where repeating bits, bytes or patterns are counted. 2. Huffman coding, where elements that appear most often are replaced by short codes, and elements that are less common are replaced by long codes. Some kind of dictionary usually needs to be generated and sent with these techniques, unless it is known in advance. 3. Repeated pattern coding, where sequences of characters that appear frequently in the output are replaced by a short code, used as an index into a dictionary, or referring to earlier data. This is the basis for LZW and similar scheme. > I don't really understand the other compression systems, and I don't > know where to find out more. Could someone reccommend some books on > the subject? I haven't read any books on data compression, other than general information in Computer Science texts. If you find any good books, can you post a message here listing them? > Also, I have managed to accidently blow up button 0 while trying to > record music [snip] > I've got a Rev B or later Enhanced 128k Apple IIe with (thank the > Gods) a board with every single chip in a socket so I can just > replace the one 79 cent chip instead of buying a whole new board > for $150... > Anyone got a IIe Technical Reference Manual handy? I need to > know which chip I need to replace, and what the chip's markings are. According to the circuit diagram, the button 0 signal on the game port and joystick port, and the Open Apple key are all connected together, and go to pin 3 of UC12, which is a 74LS251 8-to-1 multiplexor. I don't have an American IIe handy, but in the International IIe, this chip is at board location D13, near the front right corner. This chip is used to collect together the signals that are accessed via bit 7 of locations $C060 through $C067 (tape input, the three buttons and the four paddle "timeout complete" signals). -- David Empson dempson@actrix.gen.nz Snail mail: P.O. Box 27-103, Wellington, New Zealand