pst-shrn.h 14 KB

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