1 | TIGCC Program Starter - Shrink92 decompression support 2 | SHRINK92 - Copyright 1998, 1999 David Kuehling 3 | Adaptation for TI-89/92+ - Copyright 2002, 2003, 2004, 2005 Patrick Pelissier 4 | Adaptation for pstarter - Copyright 2005 Kevin Kofler 5 | Additional Optimizations - By Samuel Stearley 6 | 7 | This file is based on the SHRINK92 Library. 8 | 9 | The SHRINK92 Library is free software; you can redistribute it and/or modify 10 | it under the terms of the GNU Lesser General Public License as published by 11 | the Free Software Foundation; either version 2.1 of the License, or (at your 12 | option) any later version. 13 | 14 | The SHRINK92 Library is distributed in the hope that it will be useful, but 15 | WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 16 | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 17 | License for more details. 18 | 19 | You should have received a copy of the GNU Lesser General Public License 20 | along with the SHRINK92 Library; see the file COPYING.LIB. If not, write to 21 | the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, 22 | MA 02111-1307, USA. 23 24 | Version : 1.00.P4-tigcc-2 by Kevin Kofler Apr 23 2005 25 | * adjust calling convention for pstarter changes 26 27 | Version : 1.00.P4-tigcc-1 by Kevin Kofler Mar 18 2005 28 | * change tios.h to doorsos.h 29 | * delete TI-92 support 30 | * delete archive pack support 31 | * allocate Table of Unresolved Elements on the stack 32 | * use HeapAllocPtr to allocate archive descriptor 33 | * throw an error if allocating the archive descriptor fails 34 | * don't allocate memory in Extract 35 | * free archive descriptor at end of Extract, delete CloseArchive 36 | * always extract first section 37 | * read uncompressed size in OpenArchive 38 | * adjust calling conventions for pstarter 39 | * use nostub ROM_CALL convention 40 | * convert to GNU as 41 42 | Version : 1.00.P4 by Patrick Pelissier Feb 10 2005 43 | Version : 1.00.P3 by Patrick Pelissier Nov 10 2004 44 | Version : 1.00.P2 by Patrick Pelissier Nov 24 2003 45 46 .equ RLE_ESC,256 47 .equ RLE_BITS,5 48 .equ REP_ESC,257 49 .equ START_REP_BITS,4 50 .equ START_REP_CODES,16 51 .equ REP_CODES,64 52 .equ MIN_REP,3 53 .equ CODES,256+REP_CODES+1 54 55 | GET_UNCOMPRESSED_SIZE inline function 56 | INPUT: %a3.l: pointer to compressed data 57 | OUTPUT: %d6.l: uncompressed size 58 | SIDE EFFECTS: throws a Data Type error if not a valid compressed program 59 | may throw a Memory error 60 | may advance %a3 for later decompression 61 | DESTROYS: %d0-%d2/%a0-%a1 62 .macro GET_UNCOMPRESSED_SIZE 63 | Get the length of the variable. 64 moveq.l #0,%d6 65 move.w (%a3)+,%d6 66 | Get a pointer to the data type of the variable. 67 lea.l -1(%a3,%d6.l),%a0 68 | Check if it has type "SHRN". 69 cmp.b #0xf8,(%a0) 70 jbne invalid_archive 71 tst.b -(%a0) 72 jbne invalid_archive 73 cmp.b #'N',-(%a0) 74 jbne invalid_archive 75 cmp.b #'R',-(%a0) 76 jbne invalid_archive 77 cmp.b #'H',-(%a0) 78 jbne invalid_archive 79 cmp.b #'S',-(%a0) 80 jbne invalid_archive 81 tst.b -(%a0) 82 jbeq valid_archive 83 invalid_archive: 84 .word 0xA000+210 | ER_DATATYPE 85 valid_archive: 86 bsr OpenArchive 87 .endm 88 89 | MEM_TO_MEM_DECOMPRESS inline function 90 | INPUT: %a3.l: pointer to compressed data 91 | %a0.l: pointer to buffer for uncompressed data 92 | %d6.l: uncompressed size 93 | OUTPUT: %a4.l: pointer to uncompressed data 94 | SIDE EFFECTS: may throw a Memory or Data Type error 95 | DESTROYS: %d0-%d2/%a0-%a2 96 .macro MEM_TO_MEM_DECOMPRESS 97 bsr Extract 98 .endm 99 100 || ************************************************************************** 101 | OpenArchive 102 | -------------------------------------------------------------------------- 103 | Input: %a3.l = pointer to archive 104 | Output: %a3.l = pointer to archive descriptor 105 | %d6.l = length of section 106 | Destroys: %d1-%d2/%a0-%a1 107 | Throws ER_MEMORY if not enough memory. 108 | / 109 OpenArchive: movem.l %d0/%d3-%d5/%d7/%a2/%a4/%a6,-(%a7) 110 movea.l %a7,%a6 | %a6 = saved SP for removing stack arguments later 111 movea.l %a3,%a2 | %a2 = pointer to archive (%a2 isn't modified by ROM functions) 112 113 || ***** Initialize The Table Of The Unresolved Leaves/Junctions| / 114 | Table's format: <weight (word)> <address (word)> ... 115 | <address>: pointer,relative to the huffman tree's begin 116 | if the MSB is set: it represents a compression CODE (character) 117 | / 118 || allocate memory for the table| / 119 lea -(CODES*4)(%a7),%a7 120 movea.l %a7,%a3 121 122 || uncompress frequency table from archive's begin into that table| / 123 | %a2 = pointer to archive begin (RLE compressed freqency table| each byte is a frequency) -- input 124 | %a3 = pointer to Unresolved Table -- output 125 move.w #0x8000,%d7 | %d7 = <address>-counter (code | 0x8000) 126 movea.l %a3,%a1 | %a1 = output-pointer (is increased whereas %a3 points to the table's begin) 127 clr.w %d1 | %d1.w = one byte (high byte has to be cleared) 128 moveq #-1,%d3 | %d3.w = number of entries in table - 1 129 OAExtrFreqLoop: clr.w %d0 | %d0 = RLE repetition length - 1 (0 = ONE character -- no RLE) 130 move.b (%a2)+,%d1 | %d1 = current byte / RLE ESC byte 131 cmpi.w #0xE0,%d1 | is it an RLE ESC character ? 132 blt.s OA__RLEloop | (if it isn't: cylcle one time through RLE loop) 133 andi.w #0x001F,%d1 | extract RLE length from RLE ESC byte 134 move.w %d1,%d0 135 move.b (%a2)+,%d1 | read RLE byte 136 OA__RLEloop: tst.w %d1 | don't add entries with a frequency of zero 137 beq.s OA____Skip 138 move.w %d1,(%a1)+ | copy frequency and <address> (%d7) to output table (%a1) 139 move.w %d7,(%a1)+ 140 addq.w #1,%d3 | (%d3 = number of table entries) 141 OA____Skip: addq.w #1,%d7 142 dbra %d0,OA__RLEloop 143 cmpi.w #CODES+0x8000,%d7 144 blt.s OAExtrFreqLoop 145 146 || align input address on even address| / 147 move.l %a2,%d1 148 addq.l #1,%d1 149 bclr.b #0,%d1 150 movea.l %d1,%a2 151 152 || ***** Create Archive Descriptor,Containing the Huffman Tree| / 153 | %d3 = number of entries in Table of Unresolved Elements - 1 154 | %a2 = aligned pointer directly after the RLE compressed frequency table in the input archive 155 | %a3 = pointer to first entry in Table of Unresolved Elements 156 || allocate memory for archive descriptor| / 157 move.w (%a2)+,-(%a7) | at the current position in the archive the size of the descriptor is stored 158 clr.w -(%a7) | it is a long value 159 move.l 0xa2*4(%a5),%a0 | HeapAllocPtr 160 jsr (%a0) 161 move.l %a0,%d5 | %a0 = %d5 = pointer to archive descriptor 162 beq.s OAError 163 164 move.l %a2,(%a0)+ | store archive address into descriptor 165 movea.l %a0,%a1 | %a1 = working pointer| %a0 = pointer to huffman tree 166 clr.w (%a1)+ | leave space for root pointer 167 moveq #0,%d6 | extend 2(%a2) to longword in %d6 168 move.w 2(%a2),%d6 | %d6 = length of section 169 170 || create the huffman tree| / 171 OAHuffTreeLoop: || find the two elements with the lowest weight| / 172 bsr.s OAGetMinWeight | %a2 = pointer to min element| %d0 = its weight 173 move.w %d0,%d2 | %d2 = lowest weight 1 174 move.w 2(%a2),%d4 | %d4 = relative pointer to lowest elm 1 175 move.l (%a3)+,(%a2) | "delete" element from unresolved list (replace it by first elm) 176 subq.w #1,%d3 | decrease number of entries 177 bmi.s OAHuffTreeEnd | if number of entries was #1: end of Huffman Tree creation 178 bsr.s OAGetMinWeight | %a2 = pointer to min element| %d0 = it's weight 179 180 || replace that element by a newly created junction of the two min elements| / 181 | %d2 = lowest weight1 182 | %d4 = relative pointer to lowest elm 1 183 | %a2 = pointer to entry of loweset elm1 in unresolved table: (%a2) = weight| 2(%a2) = pointer 184 add.w %d2,(%a2)+ | weight of min2 += weight of min1 185 move.l %a1,%d1 | %d1 = relative address of new junction 186 sub.l %a0,%d1 187 move.w %d4,(%a1)+ | new Huffman Tree element: set left branch of junction 188 move.w (%a2),(%a1)+ | set right branch of junction 189 move.w %d1,(%a2) | entry in Unresolved Table: set the pointer to the Huffman Tree element 190 bra.s OAHuffTreeLoop | continue... 191 192 OAHuffTreeEnd: move.w %d4,(%a0) | store root pointer to archive descriptor 193 194 movea.l %d5,%a3 | %a3 = pointer to archive descriptor 195 movea.l %a6,%a7 | restore stored %a7 -- remove all stack elements 196 movem.l (%a7)+,%d0/%d3-%d5/%d7/%a2/%a4/%a6 | restore registers 197 rts 198 OAError: 199 .word 0xa000+670 |ER_MEMORY 200 201 | 202 | Get the element witht the minimum weight in the table of unresolved tree elements. 203 | Input: %a3 = pointer to first table entry 204 | %d3 = number of entries - 1 205 | Output: %a2 = pointer to element with the minimum weight < 32767 or NULL if no such elements are left 206 | %d0 = minimum weight 207 | %a4/%d1 destroyed! 208 | / 209 OAGetMinWeight: moveq #-1,%d0 | %d0 = minimum weight = 32768 (unsigned) 210 move.w %d3,%d1 | %d1 = counter 211 movea.l %a3,%a4 | %a4 = scanning pointer 212 OACmpLoop: cmp.w (%a4),%d0 | current element's weight less than minimum weight ? 213 bls.s OA__NotLess 214 movea.l %a4,%a2 | minimum element found: update %a2 and %d0 215 move.w (%a4),%d0 216 OA__NotLess: addq.l #4,%a4 | go to next element 217 dbra %d1,OACmpLoop 218 rts 219 220 221 || ************************************************************************************************* 222 | Bitwise Input 223 | / 224 || ************************************************************************************************* 225 | ReadBit 226 | -------------------------------------------------------------------------------------------------- 227 | Input: %a2.l = pointer to next byte 228 | %d0.b = contents of current byte 229 | %d1.b = last bit number 230 | Output: zeroflag set or cleared,depending on value of bit, 231 | %a2,%d0,%d1 adjusted to current bit 232 | / 233 ReadBit: 234 subq.b #1,%d1 | increase bit number -- go to current bit 235 bne.s RBSameByte 236 move.b (%a2)+,%d0 | read new byte,begin again with bit #0 237 moveq #8,%d1 238 RBSameByte: lsr.b #1,%d0 | test bit -- set carry/extend flag accordingly 239 rts 240 241 || ************************************************************************************************* 242 | ReadNBits 243 | -------------------------------------------------------------------------------------------------- 244 | Input: %a2.l = pointer to next byte 245 | %d0.b = contents of current byte 246 | %d1.b = last bit number 247 | %d7.w = number of bits to read 248 | Output: %a2,%d0,%d1 adjusted to last bit of bits read 249 | %d7 = -1 250 | %d3 = read bits (first read bit is high bit) 251 | / 252 ReadNBits: subq.w #1,%d7 | %d7 = counter 253 moveq #0,%d3 | %d3 = bits 254 255 RNBReadLoop: bsr.s ReadBit | read a bit 256 addx.l %d3,%d3 | move in the bit 257 RNB__ZeroBit: dbra %d7,RNBReadLoop 258 rts 259 260 261 || ************************************************************************************************* 262 | Extract 263 | -------------------------------------------------------------------------------------------------- 264 | Input: %a3.l = pointer to archive descriptor 265 | %a0.l = address of extraction destination 266 | %d6.l = length of section 267 | Output: %a4.l = address of extraction destination 268 | Throws ER_DATATYPE for an invalid archive. 269 | Destroys: %d0-%d2/%a0-%a2 270 | / 271 Extract: movem.l %d3-%d7/%a3/%a6,-(%a7) 272 273 || Prepare Extraction...| / 274 move.l (%a3),%a2 | %a2 = pointer to archive data (after frequency table) 275 adda.w (%a2),%a2 | %a2 = address of first section (expect offset <32768) 276 |SNS changed it to a 1 277 moveq #1,%d1 | %d1 = bit number (1 forces 'ReadBit' to read new byte into %d0) 278 moveq #0,%d4 | %d4 = input offset 279 movea.l %a0,%a1 | %a1 = working destination pointer 280 281 | %a0 = address of destination memory block 282 | %a1 = address of destination memory block (working pointer that is increased during extraction) 283 | %a2 = address of archive section begin (is increased during extraction) 284 | %a3 = pointer to huffman tree begin (within descriptor) 285 | %d0 = current byte 286 | %d1 = bit number within current byte '%d0' 287 | %d2 = handle of allocated destination block or original value 288 | %d6 = length of section 289 | %d4 = current input offset 290 || ***** Extraction Loop| / 291 EXExtractLoop: 292 || check whether end of file| / 293 cmp.l %d6,%d4 294 beq.s EXExtractEnd 295 bgt.s EXError 296 297 || read a Huffman code| / 298 moveq #0,%d7 299 300 EX__HuffLoop: move.w 4(%a3, %d7.w),%d7| %d7 = relative pointer to root element 301 | if bit #15 in "address" is set -> it is a leaf| %d7 contains the code 302 bmi.s EX__HuffDone | %d7 points to current element| (%d7) = left branch 2(%d7) = right branch 303 bsr.s ReadBit 304 bcc.s EX__HuffLoop 305 addq.w #2,%d7 | continue with right branch 306 bra.s EX__HuffLoop 307 |SNS: unlike the previous version it has not yet cleared the high bit of d7 308 EX__HuffDone: | %d7.w = current code 309 cmp.w #256+32768,%d7 | check code 310 beq.s EX__RLE | code = 256: RLE 311 bgt.s EX__Rep | code > 256: Rep 312 313 || 'code' (%d7) is a character| / 314 move.b %d7,(%a1)+ | copy code to destination 315 addq.l #1,%d4 316 bra.s EXExtractLoop 317 318 || RLE| / 319 EX__RLE: move.b -1(%a1),%d5 | %d5 = RLE repeating character 320 moveq #RLE_BITS,%d7 | read length of RLE sequence 321 bsr ReadNBits 322 addq.w #1,%d3 | %d3 = RLE repetition length - 1 323 add.l %d3,%d4 324 addq.l #1,%d4 325 326 EX____RLEloop: move.b %d5,(%a1)+ | output characters... 327 dbra %d3,EX____RLEloop 328 bra.s EXExtractLoop 329 330 || Repetition encoding| / 331 EX__Rep: sub.w #32768+REP_ESC-MIN_REP+1,%d7 | %d7 = length of repetition - 1 332 move.w %d7,-(%a7) | store it on the stack 333 moveq #START_REP_BITS-1,%d7 | get the number of bits that is required for coding an offset 334 moveq #START_REP_CODES/2,%d3 335 EX____IncrBitN: addq.l #1,%d7 336 add.l %d3,%d3 337 move.l %d3,%d5 338 addq.l #MIN_REP,%d5 339 cmp.l %d4,%d5 | codable range is too small ? --> increase bit number and try again 340 bls.s EX____IncrBitN 341 | %d7 = number of bits 342 bsr ReadNBits | %d3 = repetition offset 343 move.w (%a7)+,%d7 | %d7 = length of repetition - 1 344 lea 0(%a0,%d3.l),%a4 | %a4 = pointer to repetition 345 add.l %d7,%d4 346 addq.l #1,%d4 347 EX____RepCopyLp: move.b (%a4)+,(%a1)+ | copy repetition to current output position... 348 dbra %d7,EX____RepCopyLp 349 bra.s EXExtractLoop 350 351 EXError: suba.l %a0,%a0 | %a0 = zero (indicates error) 352 EXExtractEnd: movea.l %a0,%a4 353 pea.l (%a3) | Free Archive Descriptor 354 move.l 0xa3*4(%a5),%a0 | HeapFreePtr 355 jsr (%a0) 356 addq.l #4,%a7 357 move.l %a4,%d0 358 beq invalid_archive 359 movem.l (%a7)+,%d3-%d7/%a3/%a6 360 rts 361