home *** CD-ROM | disk | FTP | other *** search
/ Enigma Amiga Life 106 / EnigmaAmiga106CD.iso / software / utilities / xpk_source / libraries / huff / xpkhuff.a next >
Encoding:
Text File  |  1998-11-09  |  43.6 KB  |  1,697 lines
  1.     INCLUDE    AINCLUDE:IncDirs.i *sets all includedirs, needed for my ASM
  2.     INCLUDE    HUFF/xpkLibHUFF.i
  3.     include    "xpk/xpk.i"
  4.     include    "xpk/xpksub.i"
  5.     INCLUDE exec/memory.i
  6.  
  7. ;                             License/Disclaimer
  8. ;                             ------------------
  9. ;
  10. ;   This  source  may be freely distributed with the XPK compression package,
  11. ;as  long  as  it is kept in its original, complete, and unmodified form.  It
  12. ;may  not  be  distributed  by  itself or in a commercial package of any kind
  13. ;without my permission.
  14. ;
  15. ;   This  source  is  distributed  in  the  hope  that it will be useful, but
  16. ;WITHOUT  ANY  WARRANTY; without even the implied warranty of MERCHANTABILITY
  17. ;or FITNESS FOR A PARTICULAR PURPOSE.
  18. ;
  19. ; M.Zimmermann (zimmerma@helios.ibr.cs.tu-bs.de)
  20.  
  21. DecrunchCode    equ    1    ;0: first code
  22.                 ;1: byte oriented, chache optimized
  23.                 ;   decrunching
  24.                 ;2: word oriented decrunching (probably best
  25.                 ;   on 68000)
  26.                 ;3: 68030+ cache oriented decrunching
  27.                 ;4: long oriented decrunching
  28.  
  29. ;CrunchMethodIdentifier:
  30.  
  31. CMI_NORMAL    equ    0    ;maybe there will be other crunch
  32.                 ;methods/formats l8er
  33.  
  34. ;History:
  35. ;
  36. ;    V 0.1  - 12-Jul-1992 :    first version
  37. ;    V x.yy - 18-Jul-1992 :    first OK version
  38. ;    V x.yy - 19-Jul-1992 :    sped up decrunching
  39. ;    V x.yy - 21-Jul-1992 :    bug fixed in word/long decrunching: min pack
  40. ;                               chunk size now 3/5
  41. ;    V x.yy - 21-Jul-1992 :    replaced many subq/bxx with dbf (ie sped up
  42. ;                               crunching a little bit), bug fixed: there was
  43. ;                               a dbf counter wrong (one of my favorite 0/1
  44. ;                               problem bugs)
  45. ;    V 0.50 - 29-Jul-1992 :    added 68030+ cache optimized decrunch code
  46. ;    V 0.51 - 01-Aug-1992 :    byte decrunch improved, first code added,
  47. ;                indicator byte for crunchmethod used added,
  48. ;                68030+ chache optimized code does not make
  49. ;                sense any more, since byte decrunch fits to
  50. ;                cache completely, now
  51. ;    V 0.52 - 01-Aug-1992 :    unsafe encryption supported
  52. ;    V 0.53 - 03-Aug-1992 :    slight improvements made to crunch code
  53. ;                (+ 6K/s)
  54. ;    V 0.54 - 03-Aug-1992 :    inconsistence in expansion handling fixed
  55. ;    V 0.55 - 03-Aug-1992 :    bug fixed: expansion handling now considers
  56. ;                table creation, too
  57. ;    V 0.56 - 03-Aug-1992 :    bug fixed: HUFF now can crunch files
  58. ;                consisting of always the same byte (shame
  59. ;                on me, termination criterium was wrong)
  60. ;    V 0.57 - 03-Aug-1992 :    Tree creation code partially rewritten
  61. ;    V 0.58 - 05-Aug-1992 :    bug fixed: wrong termination criterium for
  62. ;                expansion check (my favorite 0/1 problem)
  63. ;    V 0.59 - 06-Aug-1992 :    now decrypting in a special buffer, not using
  64. ;                InBuf (this is read only, I was told) any more
  65. ;    V 0.60 - 07-Aug-1992 :    added extra memory required during
  66. ;                packing/unpacking
  67. ;    V 0.61 - 08-Aug-1992 :    expansion check changed, renamed from
  68. ;                xpkDHUF.library to xpkHUFF.library thus
  69. ;                corresponding to the possibility of handling
  70. ;                adaptive huffman codes later without having
  71. ;                an inconsistence in the name
  72. ;    V 0.62 - 10-Aug-1992 :    Flag XPKIF_MODES removed (I don't have modes
  73. ;                yet (but I have a mapping code :-=))
  74.  
  75. ;*********************************
  76. ;*** xpk specific declarations ***
  77. ;*********************************
  78.  
  79. MaxPackChunkSize    EQU    65534    ;Max input chunk size for processing
  80.  
  81.     IFEQ    DecrunchCode-0
  82. MinPackChunkSize        equ    1    ;Min input chunk size for
  83.     ENDC                    ;processing
  84.     IFEQ    DecrunchCode-1
  85. MinPackChunkSize        equ    1    ;Min input chunk size for
  86.     ENDC                    ;processing
  87.     IFEQ    DecrunchCode-2
  88. MinPackChunkSize        equ    3    ;Min input chunk size for
  89.     ENDC                    ;processing
  90.     IFEQ    DecrunchCode-3
  91. MinPackChunkSize        equ    5    ;Min input chunk size for
  92.     ENDC                    ;processing
  93.     IFEQ    DecrunchCode-4
  94. MinPackChunkSize        equ    5    ;Min input chunk size for
  95.     ENDC                    ;processing
  96.  
  97. DefPackChunkSize        equ    MaxPackChunkSize
  98. ;Default processing input size (must be lower tahn or equal to MaxPackChunkSize)
  99.  
  100. DefMode                equ    50
  101. ;Default mode/efficiency, ranges from [0..100]
  102.  
  103. ;********************************
  104. ;*** xpk sublibrary functions ***
  105. ;********************************
  106.  
  107. _XpksPackerInfo:
  108.     LEA    HUFFXpkInfo,A0
  109.     MOVE.L    A0,D0
  110.     RTS
  111.  
  112. ;**********************
  113. ;*** un-/pack modes ***
  114. ;**********************
  115.  
  116. ;mode 0 performs: dynamic huffman crunching
  117.  
  118. _XpksPackChunk
  119.  
  120. ;in:
  121. ;
  122. ;    a0 :    *XpkSubParams
  123. ;    a6 :    *xpkHUFF.library
  124. ;out:
  125. ;    d0 :    err
  126. ;    in XpkSubParams :    xsp_OutLen
  127. ;
  128. ;registers trashed:
  129.  
  130.     MOVEM.L    D2-D7/A2-A6,-(A7)
  131.     BSR.B    PackMode0
  132.     MOVEM.L    (A7)+,D2-D7/A2-A6
  133.     RTS
  134.  
  135. ;******************************
  136. ;*** huffman node structure ***
  137. ;******************************
  138.  
  139. UNUSED        equ    0
  140. NODEUSED    equ    1
  141. NODEUNUSED    equ    2
  142. LEAFLINKED    equ    3 ;leaf already is linked somewhere in the tree
  143. LEAFUNLINKED    equ    4 ;leaf is not yet linked to any node in the tree
  144. ROOTNODE    equ    5
  145. LEFTSUBTREE    equ    0 ;indicates that this node is at the left  branch of it's parent
  146. RIGHTSUBTREE    equ    1 ;indicates that this node is at the right branch of it's parent
  147. NODIRECTION    equ    -1 ;for root node only
  148. NOLISTLINKYET    equ    -1
  149.  
  150. HuffmanNodeStructure    RSRESET
  151. xpkHUFF_LinkToNextNodeOrLeaf    RS.L    1    ;* for fast tree creation
  152. xpkHUFF_Sum            RS.W    1    ;sum of left and right subtree sums
  153. xpkHUFF_Char            RS.B    1    ;byte # (0..255) if leaf, invalid else
  154. xpkHUFF_Type            RS.B    1    ;UNUSED|NODEUSED|NODEUNUSED|
  155.                     ;LEAFUSED|LEAFUNUSED
  156. xpkHUFF_Parent            RS.L    1    ;*parent node or 0
  157. xpkHUFF_Left            RS.L    1    ;*left subtree
  158. xpkHUFF_Right:            rs.l    1    ;*right subtree
  159. xpkHUFF_Direction:        rs.w    1    ;direction which to take from
  160.                         ;parent to this node
  161. xpkHUFF_pad1:            rs.w    1
  162. xpkHUFF_pad2:            rs.l    1
  163. xpkHUFF_pad3:            rs.l    1
  164. xpkHUFF_HuffmanNodeStruct_SIZEOF:    rs.b    0    ;size: 8 longs ==>
  165.                             ;shifing for size
  166.                             ;correction possible
  167.  
  168. ;*************************
  169. ;*** reentry structure ***
  170. ;*************************
  171.  
  172. MAXHUFFMANCODELENGTH                equ    256/8
  173.  
  174. CrunchReentryStructure:        rsreset
  175. xpkHUFF_CRS_xpkSubParams:            rs.l    1        ;*SubParamsStructure
  176. xpkHUFF_CRS_xpkSubLibBase:            rs.l    1        ;the pointer to my sublibrary
  177. xpkHUFF_CRS_StatisticArray:            rs.b    256*2        ;Word_SIZEOF: max InputBuffer allowed is 64K!
  178. xpkHUFF_CRS_InBuf:                rs.l    1        ;*input buffer
  179. xpkHUFF_CRS_InLen:                rs.l    1        ;size of input buffer in bytes
  180. xpkHUFF_CRS_OutBuf:                rs.l    1        ;*output buffer
  181. xpkHUFF_CRS_OutLen:                rs.l    1        ;will be set to output buffer size after crunching
  182. xpkHUFF_CRS_OutBufLen:                rs.l    1        ;for overflow check when crunching (recognize expansion)
  183. xpkHUFF_CRS_CrunchedLength:            rs.l    1
  184. xpkHUFF_CRS_DynamicHuffmanTreeLeafs:        rs.b    256*xpkHUFF_HuffmanNodeStruct_SIZEOF
  185. xpkHUFF_CRS_DynamicHuffmanTerminatorLeaf:    rs.b    xpkHUFF_HuffmanNodeStruct_SIZEOF    ;MUST stay uninitialized for a terminating condition below
  186. xpkHUFF_CRS_DynamicHuffmanTreeNodes:        rs.b    255*xpkHUFF_HuffmanNodeStruct_SIZEOF
  187. xpkHUFF_CRS_RootNode:                rs.l    1
  188. xpkHUFF_CRS_PtrTableToSizesAndCodes:        rs.l    256*4
  189. xpkHUFF_CRS_SpaceForLengthsAndCodes:        rs.b    256*MAXHUFFMANCODELENGTH+256    ;size will be stored in bytes here
  190. xpkHUFF_CRS_SIZEOF:                rs.b    0
  191.  
  192. ;************
  193. ;*** main ***
  194. ;************
  195.  
  196.  
  197. PackMode0:
  198.     move.l    a0,a2        ;keep subparams in mind
  199.     move.l    a6,a3        ;keep xpkHUFF base in mind
  200.     move.l    #xpkHUFF_CRS_SIZEOF,d0
  201.     move.l    #MEMF_CLEAR|MEMF_PUBLIC,d1
  202.     move.l    4.w,a6
  203.     jsr    _LVOAllocMem(a6)
  204.     tst.l    d0
  205.     beq    xpkHUFF_AllocReentryBufferFailed
  206.     move.l    d0,a5        ;reentry buffer in a5, now
  207.     move.l    a3,xpkHUFF_CRS_xpkSubLibBase(a5)    ;store xpkHUFF base
  208.                 ;in the reentry structure
  209.     move.l    a2,xpkHUFF_CRS_xpkSubParams(a5)        ;store xpksubparams
  210.                 ;in reentry structure
  211.  
  212. ;********************************************
  213. ;*** get data from xpksubparams structure ***
  214. ;********************************************
  215.  
  216.     move.l    xsp_InBuf(a2),xpkHUFF_CRS_InBuf(a5)
  217.     move.l    xsp_InLen(a2),xpkHUFF_CRS_InLen(a5)
  218.  
  219.     move.l    xsp_OutBuf(a2),xpkHUFF_CRS_OutBuf(a5)
  220.     move.l    xsp_OutBufLen(a2),xpkHUFF_CRS_OutBufLen(a5)
  221.  
  222.  
  223. ;*******************************
  224. ;*** create statistics table ***
  225. ;*******************************
  226.  
  227. xpkHUFF_StatisticLoopInit:
  228.  
  229.     move.l    xpkHUFF_CRS_InBuf(a5),a0
  230.     move.l    xpkHUFF_CRS_InLen(a5),d0        ;InLen <= MaxPackChunkSize!
  231.     subq.l    #1,d0                    ;dbf
  232.     lea    xpkHUFF_CRS_StatisticArray(a5),a1
  233.  
  234. xpkHUFF_StatisticLoop:
  235.  
  236.     moveq    #0,d1
  237.     move.b    (a0)+,d1
  238.     add.w    d1,d1                    ;byte offset
  239.                             ;-> word offset
  240.     addq.w    #1,0(a1,d1.w)
  241.  
  242.     dbf    d0,xpkHUFF_StatisticLoop
  243.  
  244.  
  245. ;***************************************
  246. ;*** init leafs in reentry structure ***
  247. ;***************************************
  248.  
  249. xpkHUFF_InitLeafs:
  250.  
  251.     lea    xpkHUFF_CRS_StatisticArray(a5),a0
  252.     lea    xpkHUFF_CRS_DynamicHuffmanTreeLeafs(a5),a1
  253.  
  254.     moveq    #-1,d0                    ;current byte #
  255.     moveq    #LEAFUNLINKED,d1
  256.     moveq    #-2,d2                    ;current byte's
  257.                             ;word offset
  258.  
  259.     move.w    #255,d3                    ;256 runs (bytes range
  260.                             ;from 0..255)
  261.  
  262.     moveq    #NOLISTLINKYET,d4
  263.  
  264. xpkHUFF_InitLeafsLoop:
  265.  
  266.     addq.l    #1,d0                    ;next byte number
  267.     addq.l    #2,d2                    ;next word offset
  268.  
  269.     move.w    0(a0,d2.w),d5
  270.     beq.s    xpkHUFF_ILL_DontConsiderEmptyLeaf
  271.  
  272.     move.b    d0,xpkHUFF_Char(a1)            ;current byte #
  273.  
  274.     move.b    d1,xpkHUFF_Type(a1)            ;type := LEAFUNLINKED
  275.  
  276.     move.w    d5,xpkHUFF_Sum(a1)
  277.  
  278.     move.l    d4,xpkHUFF_LinkToNextNodeOrLeaf(a1)
  279.  
  280.     lea    xpkHUFF_HuffmanNodeStruct_SIZEOF(a1),a1    ;proceed to next leaf
  281.  
  282. xpkHUFF_ILL_DontConsiderEmptyLeaf:
  283.  
  284.     dbf    d3,xpkHUFF_InitLeafsLoop
  285.  
  286.  
  287. ;***********************************
  288. ;*** link leafs from low to high ***
  289. ;***********************************
  290.  
  291. FindHighestSum    MACRO
  292.  
  293. ;finds  highest  sum of all currently unlinked nodes and returns a pointer to
  294. ;that node in a2
  295.  
  296. ;
  297. ;registers trashed: a0, d1, a2
  298.  
  299.  
  300. xpkHUFF_LL_FindHighestSum:
  301.  
  302.     lea    xpkHUFF_CRS_DynamicHuffmanTreeLeafs(a5),a0
  303.  
  304.     moveq    #0,d1                    ;initial sum
  305.     sub.l    a2,a2                    ;currently no node
  306.                             ;with highest sum
  307. xpkHUFF_LL_FindHighestSumLoop:
  308.  
  309.     tst.b    xpkHUFF_Type(a0)            ;= cmp.w #UNUSED,
  310.                             ;pkHUFF_Type, ie did
  311.     beq.s    xpkHUFF_LL_FoundHighestSum        ; we reach the end of
  312.                             ;the list?
  313.  
  314.     cmp.l    xpkHUFF_LinkToNextNodeOrLeaf(a0),d3    ;already considered?
  315.     bne.s    xpkHUFF_LL_AlreadyConsidered
  316.  
  317.     cmp.w    xpkHUFF_Sum(a0),d1
  318.     bhi.s    xpkHUFF_LL_NoHigherSum
  319.  
  320.     move.w    xpkHUFF_Sum(a0),d1            ;current sum
  321.     move.l    a0,a2                    ;remember this adr
  322.  
  323.  
  324. xpkHUFF_LL_AlreadyConsidered:
  325. xpkHUFF_LL_NoHigherSum:
  326.  
  327.     lea    xpkHUFF_HuffmanNodeStruct_SIZEOF(a0),a0
  328.     bra.s    xpkHUFF_LL_FindHighestSumLoop
  329.  
  330. xpkHUFF_LL_FoundHighestSum:
  331.  
  332.  
  333.         ENDM
  334.  
  335. ;register usage:
  336. ;
  337. ;    a1:    *last node
  338.  
  339. xpkHUFF_LinkLeafs:
  340.  
  341.     moveq    #0,d2                    ;for a fast cmp below
  342.     sub.l    a1,a1                    ;keep 'last' node in
  343.                             ;mind (in this case no
  344.                             ;last node)
  345.     moveq    #NOLISTLINKYET,d3            ;for cmp below
  346.  
  347. xpkHUFF_LinkLeafsLoop:
  348.  
  349.     FindHighestSum
  350.  
  351. ;here a2 contains the adr of the node with the highest sum or 0, if all nodes
  352. ;are linked already
  353.  
  354.     cmp.l    d2,a2                    ;no highest sum any
  355.                             ;more?
  356.     beq.s    xpkHUFF_LeavesLinked            ;nope: ==> done
  357.  
  358.     move.l    a1,xpkHUFF_LinkToNextNodeOrLeaf(a2)
  359.     move.l    a2,a1
  360.  
  361.     bra.s    xpkHUFF_LinkLeafsLoop
  362.  
  363. xpkHUFF_LeavesLinked:
  364.  
  365.     move.l    a1,a4
  366.  
  367.  
  368. ;here a4 contains the currently first node
  369.  
  370. ;*********************
  371. ;*** CreateNewNode ***
  372. ;*********************
  373.  
  374. CreateNewNode    MACRO
  375.  
  376. ;in:    a0: *A
  377. ;    a1: *N
  378.  
  379.     move.l    a1,a2
  380.     move.l    xpkHUFF_LinkToNextNodeOrLeaf(a0),a1
  381.  
  382.  
  383. ;a0: *A
  384. ;a1: *B
  385. ;a2: *N
  386.  
  387.     move.w    #LEFTSUBTREE,xpkHUFF_Direction(a0)
  388.     move.w    #RIGHTSUBTREE,xpkHUFF_Direction(a1)
  389.  
  390.     move.w    xpkHUFF_Sum(a0),d0
  391.     add.w    xpkHUFF_Sum(a1),d0
  392.  
  393.     move.w    d0,xpkHUFF_Sum(a2)
  394.  
  395.     move.b    #NODEUSED,xpkHUFF_Type(a2)
  396. ;    move.b    #LEAFLINKED,xpkHUFF_Type(a0)        ;not necessary, therefore not assembled
  397. ;    move.b    #LEAFLINKED,xpkHUFF_Type(a1)        ;not necessary, therefore not assembled
  398.  
  399.     move.l    a0,xpkHUFF_Left(a2)
  400.     move.l    a1,xpkHUFF_Right(a2)
  401.  
  402.     move.l    a2,xpkHUFF_Parent(a0)
  403.     move.l    a2,xpkHUFF_Parent(a1)
  404.  
  405.     move.l    xpkHUFF_LinkToNextNodeOrLeaf(a1),a0
  406.     lea    xpkHUFF_HuffmanNodeStruct_SIZEOF(a2),a1
  407.  
  408.  
  409. ;a0: *C
  410. ;a1: *O
  411. ;a2: *N
  412.  
  413.         ENDM
  414.  
  415. ;***************************
  416. ;*** insert node to list ***
  417. ;***************************
  418.  
  419.  
  420. InsertTreeNodeToList    MACRO
  421.  
  422. ;in:    a0: *first node in list
  423. ;    a2: *node to insert in list
  424.  
  425. ;a0: *first node in list (*C)
  426. ;a1: MUST BE LEFT UNTOUCHED
  427. ;a2: *node to insert (*N)
  428.  
  429.  
  430. ;have the last two nodes been linked to a lonely (ie in this case root) node?
  431. ;if so, we are ready
  432.  
  433.  
  434.     cmp.l    a0,d7            ;d7 = 0
  435.     bne.s    HSH1L_a2IsNoLonelyNode
  436.  
  437.     move.l    a2,a0
  438.     bra.s    xpkHUFF_InsertionComplete
  439.  
  440.  
  441. HSH1L_a2IsNoLonelyNode:
  442.  
  443.     move.w    xpkHUFF_Sum(a2),d0
  444.  
  445. ;_____________
  446.  
  447.     cmp.w    xpkHUFF_Sum(a0),d0
  448.     bhi.s    xpkHUFF_DontInsertAsHeadOfList
  449.  
  450. xpkHUFF_InsertAsHeadOfList:
  451.  
  452. ;case: 3 5 7 ... insert 2 before 3
  453.  
  454.     move.l    a0,xpkHUFF_LinkToNextNodeOrLeaf(a2)
  455.     move.l    a2,a0
  456.     bra.s    xpkHUFF_InsertionComplete
  457.  
  458. ;_____________
  459.  
  460.  
  461. xpkHUFF_DontInsertAsHeadOfList:
  462.  
  463.  
  464.     move.l    a0,a3                    ;*first node in list
  465.  
  466.  
  467. xpkHUFF_ProceedToNextNode:
  468.  
  469.     cmp.l    xpkHUFF_LinkToNextNodeOrLeaf(a3),d7
  470.     beq.s    xpkHUFF_InsertAtEndOfList
  471.  
  472.     move.l    a3,a4
  473.     move.l    xpkHUFF_LinkToNextNodeOrLeaf(a3),a3
  474.  
  475.     cmp.w    xpkHUFF_Sum(a3),d0
  476.     bhi.s    xpkHUFF_ProceedToNextNode
  477.  
  478.  
  479. ;_____________
  480.  
  481.  
  482. xpkHUFF_InsertInMiddleOfList:
  483.  
  484. ;case: 3 5 ... insert 4 between 3 and 5
  485.  
  486.     move.l    a2,xpkHUFF_LinkToNextNodeOrLeaf(a4)
  487.  
  488.     move.l    a3,xpkHUFF_LinkToNextNodeOrLeaf(a2)
  489.     bra.s    xpkHUFF_InsertionComplete
  490.  
  491. ;_____________
  492.  
  493.  
  494. xpkHUFF_InsertAtEndOfList:
  495.  
  496. ;in: a3: *last node in list
  497.  
  498. ;case: 3 5 7   insert 8 behind 7
  499.  
  500.     move.l    a2,xpkHUFF_LinkToNextNodeOrLeaf(a3)
  501.  
  502.     move.l    d7,xpkHUFF_LinkToNextNodeOrLeaf(a2)
  503. ;    bra.s    xpkHUFF_InsertionComplete
  504.  
  505. ;_____________
  506.  
  507.  
  508. xpkHUFF_InsertionComplete:
  509.  
  510. ;a0: *first node in list
  511.  
  512.             ENDM
  513.  
  514. ;*******************
  515. ;*** create tree ***
  516. ;*******************
  517.  
  518. ;Here  we have all leafs lying next to each other, in order 0..255.  They are
  519. ;linked  via  a  single pointer (xpkHUFF_LinkToNextNodeOrLeaf).  If you start
  520. ;with  a4  here and proceed using the link pointers, you will find all leaves
  521. ;in ascending order (order: low to high by xpkHUFF_Sum).
  522.  
  523. ;
  524. ;suggest we have the nodes
  525. ;
  526. ;  A  B  C  D  E  F   G  H . . . N O P
  527. ;  3  5  6  7  8  9  10 11       new (currently unused) nodes
  528. ;
  529.  
  530. ;Now  we  have  to  create  a  new  node  N  with  A as xpkHUFF_Left and B as
  531. ;xpkHUFF_Right.   This new node N has to be sorted into he list (ie between D
  532. ;and  E).  The nodes A and B are excluded from the list when creating the new
  533. ;node N.  This will go on until there are only two nodes left.  These will be
  534. ;linked by the root node of the huffman tree.
  535.  
  536. ;register usage:
  537.  
  538. ;    a0: *current root of used nodes  (at the beginning *A)
  539. ;    a1: *currently first unused node (at the beginning *N)
  540.  
  541.     move.l    a4,a0                        ;a0: *A
  542.     lea    xpkHUFF_CRS_DynamicHuffmanTreeNodes(a5),a1    ;a1: *N
  543.     moveq    #0,d7
  544.  
  545.  
  546.     cmp.l    xpkHUFF_LinkToNextNodeOrLeaf(a0),d7        ;is there only
  547.                                 ;one node?
  548.  
  549.     bne.s    xpkHUFF_CreateTreeLoop                ;nope: construct
  550.                                 ;      tree
  551.  
  552. xpkHUFF_ThereIsOnlyOneNode:                    ;create tree
  553.                                 ;containing
  554.                                 ;only one leaf
  555. ;create new root node at (a1)
  556.  
  557.     move.w    #LEFTSUBTREE,xpkHUFF_Direction(a0)
  558. ;    move.w    xpkHUFF_Sum(a0),xpkHUFF_Sum(a1)
  559.  
  560.     move.l    a0,xpkHUFF_Left(a1)
  561.     move.l    a1,xpkHUFF_Parent(a0)
  562.  
  563.     move.l    a1,a2                        ;new root
  564.                                 ;in a2
  565.     bra.s    xpkHUFF_TreeCreationComplete
  566.  
  567.  
  568.  
  569. xpkHUFF_CreateTreeLoop:
  570.  
  571.  
  572.     cmp.l    xpkHUFF_LinkToNextNodeOrLeaf(a0),d7
  573.     beq.s    xpkHUFF_TreeCreationComplete
  574.  
  575.     CreateNewNode            ;creates new node from a0 (A) and the
  576.                     ;sequel node of A (B) in node a1 (N).
  577.                     ;increments a0 (will point to C
  578.                     ;afterwards) and a1 (will point to O
  579.                     ;afterwards).
  580.                     ;returns adr of N in a2
  581.  
  582.     InsertTreeNodeToList        ;insert the node we just created
  583.                     ;(a2: N) into the list (a0: C)
  584.                     ;positioned according to it's
  585.                     ;xpkHUFF_Sum field.
  586.  
  587.     bra.s    xpkHUFF_CreateTreeLoop
  588.  
  589. xpkHUFF_TreeCreationComplete:
  590.  
  591. ;a2: *root node of huffman tree
  592.  
  593.     move.b    #ROOTNODE,xpkHUFF_Type(a2)
  594.     move.w    #NODIRECTION,xpkHUFF_Direction(a2)
  595.  
  596.     move.l    a2,xpkHUFF_CRS_RootNode(a5)
  597.  
  598. xpkHUFF_CreateTranslationTableSizesAndCodes:
  599.  
  600. ;**********************************************************
  601. ;*** create translation table, sizes of codes and codes ***
  602. ;**********************************************************
  603.  
  604.  
  605.     lea    xpkHUFF_CRS_DynamicHuffmanTreeLeafs(a5),a0
  606.  
  607.     lea    xpkHUFF_CRS_PtrTableToSizesAndCodes(a5),a3
  608.     lea    xpkHUFF_CRS_SpaceForLengthsAndCodes(a5),a4
  609.  
  610.  
  611. xpkHUFF_CreateTranslationTableSizesAndCodesLoop:
  612.  
  613. ;____________________________
  614.  
  615.  
  616. xpkHUFF_GetOneLeafsCode:
  617.  
  618. ;get code of leaf a0
  619. ;write length as byte to (a4)+
  620. ;write bitcode of leaf pointed to by a0 to (a4)+ behind size
  621.  
  622.     move.b    xpkHUFF_Char(a0),d5            ;keep char in mind
  623.  
  624.     moveq    #0,d6
  625.     move.b    d5,d6
  626.     add.w    d6,d6                    ;offset:
  627.     add.w    d6,d6                    ;.b -> .l
  628.  
  629.     move.l    a4,0(a3,d6.w)                ;put pointer to table
  630.  
  631.  
  632.     moveq    #-1,d1                    ;bit counter (dbf)
  633.     move.l    a0,a1
  634.  
  635. xpkHUFF_GetOneLeafsCodeLoop:
  636.  
  637.     moveq    #0,d0
  638.     move.w    xpkHUFF_Direction(a1),d0        ;root reached?
  639.     bmi.s    xpkHUFF_PutOneLeafsCompleteCodeOnStack    ;yep
  640.  
  641.     addq.l    #1,d1                    ;one more bit for code
  642.     move.w    d0,-(a7)
  643.     move.l    xpkHUFF_Parent(a1),a1            ;go up
  644.  
  645.     bra.s    xpkHUFF_GetOneLeafsCodeLoop
  646.  
  647.  
  648. xpkHUFF_PutOneLeafsCompleteCodeOnStack:
  649.  
  650. ;here all bits are on the stack, d1 is a dbf counter for composition
  651.  
  652.     move.b    d1,(a4)+
  653.  
  654. xpkHUFF_ComposeHuffmanCode:
  655.  
  656.     moveq    #0,d2                    ;will contain
  657.                             ;composed code
  658.     moveq    #7,d3                    ;# of bits not yet
  659.                             ;used in dest
  660.                             ;register (dbf)
  661.  
  662. xpkHUFF_ComposeHuffmanCodeLoop:
  663.  
  664.     move.w    (a7)+,d0
  665.  
  666.  
  667.     roxr.b    #1,d0                    ;code bit to x & c
  668.                             ;flag
  669.     addx.b    d2,d2                    ;code bit to composed
  670.                             ;code register
  671.     dbf    d3,xpkHUFF_CHCL_DontWriteCodeByte
  672.  
  673.     moveq    #7,d3                    ;reset counter
  674.     move.b    d2,(a4)+                ;write to buffer
  675.  
  676. xpkHUFF_CHCL_DontWriteCodeByte:
  677.  
  678.     dbf    d1,xpkHUFF_ComposeHuffmanCodeLoop
  679.  
  680. ;write the last byte (this could contain 1 to 7 bits) if not already written
  681.  
  682.     cmp.w    #7,d3                    ;last byte already
  683.                             ;written?
  684.     beq.s    xpkHUFF_CHCL_DontWriteLastByte        ;yep
  685.  
  686.     addq.w    #1,d3                    ;was dbf counter
  687.     lsl.b    d3,d2                    ;shift bits to left
  688.                             ;edge of byte
  689.     move.b    d2,(a4)+                ;write last byte
  690.                             ;to buffer
  691.  
  692. xpkHUFF_CHCL_DontWriteLastByte:
  693.  
  694.  
  695. ;____________________________
  696.  
  697.  
  698.     lea    xpkHUFF_HuffmanNodeStruct_SIZEOF(a0),a0    ;proceed to next leaf
  699.  
  700.     tst.b    xpkHUFF_Type(a0)            ;equ cmp.b #UNUSED,...
  701.     bne.s    xpkHUFF_CreateTranslationTableSizesAndCodesLoop
  702.  
  703. ;**************************************
  704. ;*** identifier & password handling ***
  705. ;**************************************
  706.  
  707.     cmp.l    #6,xpkHUFF_CRS_OutBufLen(a5)        ;2: indicator word,
  708.                             ;4: password checksum
  709.     bls    xpkHUFF_C_Expansion
  710.  
  711.  
  712. ;*****************************
  713. ;*** write identifier word ***
  714. ;*****************************
  715.  
  716.     move.l    xpkHUFF_CRS_OutBuf(a5),a1
  717.     move.w    #CMI_NORMAL,(a1)+            ;word indicating
  718.                             ;crunchmethod used
  719.  
  720. ;____________________________
  721.  
  722.  
  723. ;*************************
  724. ;*** password handling ***
  725. ;*************************
  726.  
  727.  
  728.     move.l    xpkHUFF_DRS_xpkSubParams(a5),a0
  729.  
  730. xpkHUFF_C_CalcPasswordCheckSum:
  731.  
  732.     move.l    #$ABADCAFE,d0
  733.  
  734.     move.l    xsp_Password(a0),d2
  735.     beq.s    xpkHUFF_C_CPCS_NoPassword
  736.     
  737.     move.w    #$C0DE,d1
  738.     move.l    d2,a2
  739.  
  740. xpkHUFF_C_CalcPasswordChecksumLoop1:
  741.  
  742.     move.b    (a2)+,d1
  743.     beq.s    xpkHUFF_C_CalcPasswordChecksumLoop1End
  744.  
  745.     add.w    d1,d0
  746.     bra.s    xpkHUFF_C_CalcPasswordChecksumLoop1
  747.  
  748. xpkHUFF_C_CalcPasswordChecksumLoop1End:
  749.  
  750.     move.l    xsp_Password(a0),a2
  751.     swap    d0
  752.  
  753. xpkHUFF_C_CalcPasswordChecksumLoop2:
  754.  
  755.     move.b    (a2)+,d1
  756.     beq.s    xpkHUFF_C_CalcPasswordChecksumLoop2End
  757.  
  758.     eor.w    d1,d0
  759.     rol.w    #8,d0
  760.     bra.s    xpkHUFF_C_CalcPasswordChecksumLoop2
  761.  
  762. xpkHUFF_C_CalcPasswordChecksumLoop2End:
  763.  
  764. xpkHUFF_C_CPCS_NoPassword:
  765.  
  766.     move.l    d0,(a1)+
  767.  
  768.  
  769. ;____________________________
  770.  
  771.  
  772. ;*******************************************************
  773. ;*** write translation sizes & codes to outputbuffer ***
  774. ;*******************************************************
  775.  
  776.  
  777. ;Format: size.b
  778. ;If  size  <>  0 (or, in this representation -1 (because of size beeing a dbf
  779. ;counter))  there  is  the  full  code  following,  byte aligned, thus saving
  780. ;diskspace.   If  size  = 0 (ie -1 (dbf, see above)) no code will follow, coz
  781. ;size = 0 indicates that this code won't be used.
  782.  
  783. xpkHUFF_WriteTranslationSizesAndCodesToOuputBuffer:
  784.  
  785.  
  786.     lea    xpkHUFF_CRS_PtrTableToSizesAndCodes(a5),a0
  787.  
  788.     move.l    xpkHUFF_CRS_OutBuf(a5),a4
  789.     add.l    xpkHUFF_CRS_InLen(a5),a4        ;a4: *to check for
  790.                             ;expansion
  791. ;    add.l    #XPKMARGIN,a4                ;a cruncher that
  792.                             ;expands data makes no
  793.                             ;sense
  794.  
  795.     move.w    #255,d0                    ;dbf counter over
  796.                             ;all table entries
  797.     moveq    #-1,d3
  798.  
  799. xpkHUFF_WriteTranslationSizesAndCodesToOuputBufferLoop:
  800.  
  801.     move.l    (a0)+,d2                ;d2: *size
  802.     beq.s    xpkHUFF_WTSACTOB_DontWriteCodeJustMinusOne
  803.  
  804.     move.l    d2,a2
  805.  
  806.     moveq    #0,d1
  807.     move.b    (a2)+,d1                ;a2: *code
  808.  
  809.     move.b    d1,(a1)+
  810.  
  811.     cmp.l    a4,a1                    ;check for expansion
  812.     bhs    xpkHUFF_C_Expansion            ;Uh, Oh, expansion
  813.  
  814.  
  815.  
  816. xpkHUFF_WTSACTOB_WriteCode:
  817.  
  818.     lsr.b    #3,d1                    ;8 bits = 1 byte
  819.                             ;(worx! :-)
  820.  
  821. xpkHUFF_WTSACTOB_WriteCodeLoop:
  822.  
  823.     move.b    (a2)+,(a1)+
  824.  
  825.     cmp.l    a4,a1                    ;check for expansion
  826.     bhs    xpkHUFF_C_Expansion            ;Uh, Oh, expansion
  827.     
  828.     dbf    d1,xpkHUFF_WTSACTOB_WriteCodeLoop
  829.  
  830.     dbf    d0,xpkHUFF_WriteTranslationSizesAndCodesToOuputBufferLoop
  831.  
  832.     bra.s    xpkHUFF_WTSACTOB_Done
  833.  
  834. xpkHUFF_WTSACTOB_DontWriteCodeJustMinusOne:
  835.  
  836.     move.b    d3,(a1)+                ;-1 (= dbf 0)
  837.  
  838.     cmp.l    a4,a1                    ;check for expansion
  839.     bhs    xpkHUFF_C_Expansion            ;Uh, Oh, expansion
  840.  
  841.     dbf    d0,xpkHUFF_WriteTranslationSizesAndCodesToOuputBufferLoop
  842.  
  843.  
  844. xpkHUFF_WTSACTOB_Done:
  845.  
  846.  
  847. ;********************************************
  848. ;*** write crunched data to output buffer ***
  849. ;********************************************
  850.  
  851.  
  852.  
  853. xpkHUFF_WriteCrunchedDataToOutputBuffer:
  854.  
  855. xpkHUFF_WCDTOB_Init:
  856.  
  857. ;here a1 contains *OutBuf, right behind the table
  858.  
  859.     move.l    xpkHUFF_CRS_InBuf(a5),a0
  860.     move.l    xpkHUFF_CRS_InLen(a5),d0
  861.     subq.l    #1,d0            ;dbf
  862.  
  863.     lea    xpkHUFF_CRS_PtrTableToSizesAndCodes(a5),a2
  864.  
  865.     moveq    #7,d4                    ;# of bits not yet
  866.                             ;used in dest
  867.                             ;representation (dbf)
  868.  
  869.     move.l    xpkHUFF_CRS_OutBuf(a5),a4
  870.     add.l    xpkHUFF_CRS_InLen(a5),a4
  871. ;    add.l    #XPKMARGIN,a4
  872.  
  873. xpkHUFF_WCDTOB_OuterLoop:
  874.  
  875. ;*******************************************************************************
  876. ;*** This part will write one byte in it's crunched representation to OutBuf ***
  877. ;*******************************************************************************
  878.  
  879.     moveq    #0,d1
  880.     move.b    (a0)+,d1                ;byte to crunch
  881.     add.w    d1,d1                    ;make long
  882.     add.w    d1,d1                    ;offset
  883.  
  884.     move.l    0(a2,d1.w),a3                ;*size of bytes'
  885.                             ;huffman
  886.                             ;representation
  887.     moveq    #0,d2
  888.     move.b    (a3)+,d2                ;number of bits in
  889.                             ;byte representation
  890.                             ;(dbf counter)
  891.  
  892. ;register usage here:
  893.  
  894. ;    d0: MUST NOT BE TOUCHED
  895. ;    d1: (current byte to be coded)*4
  896. ;    d2: #of bits in huffamn representation for byte in d1
  897. ;    d4: #of bits not yet used in dest byte (dbf)
  898. ;    a0: MUST NOT BE TOUCHED
  899. ;    a1: MUST NOT BE TOUCHED
  900. ;    a3: *code of byte in d1:8
  901.     moveq    #0,d3                    ;force read of first
  902.                             ;byte below
  903.  
  904. xpkHUFF_WCDTOB_WriteHuffmanRepresentationOfOneByteLoop:
  905.  
  906. ;register usage here:
  907. ;    d3:   #of not yet used bits in source representation (dbf)
  908. ;    d5:8: contains (partial) huffman code
  909. ;    d6:   compose register
  910.     dbf    d3,xpkHUFF_WCDTOB_DontGetNewSourceRepresentationByte
  911.     moveq    #7,d3
  912.     move.b    (a3)+,d5
  913.  
  914. xpkHUFF_WCDTOB_DontGetNewSourceRepresentationByte:
  915.     addx.b    d5,d5
  916.     addx.b    d6,d6
  917.     dbf    d4,xpkHUFF_WCDTOB_DontWriteDestByte
  918.     moveq    #7,d4
  919.     move.b    d6,(a1)+
  920.     cmp.l    a4,a1                    ;check for expansion
  921.     bhs.s    xpkHUFF_C_Expansion            ;Uh, Oh, expansion
  922.  
  923. xpkHUFF_WCDTOB_DontWriteDestByte:
  924.     dbf    d2,xpkHUFF_WCDTOB_WriteHuffmanRepresentationOfOneByteLoop
  925. ;============================
  926.     dbf    d0,xpkHUFF_WCDTOB_OuterLoop
  927.     cmp.b    #7,d4
  928.     beq.s    xpkHUFF_DontWriteLastPartialByte
  929.     cmp.l    a4,a1
  930.     bhs.s    xpkHUFF_C_Expansion
  931.     addq.l    #1,d4                    ;former dbf counter
  932.     lsl.b    d4,d6
  933.     move.b    d6,(a1)+
  934.  
  935. xpkHUFF_DontWriteLastPartialByte:
  936.     move.l    a1,d1            ;end of crunched data
  937.     sub.l    xpkHUFF_CRS_OutBuf(a5),d1
  938.     move.l    d1,xpkHUFF_CRS_OutLen(a5)
  939.     move.l    d1,xpkHUFF_CRS_CrunchedLength(a5)
  940.     move.l    xpkHUFF_CRS_xpkSubParams(a5),a0
  941.     move.l    d1,xsp_OutLen(a0)
  942.  
  943. ;__________________________________________________________
  944.  
  945. xpkHUFF_Encrypt:
  946.     move.l    xpkHUFF_CRS_xpkSubParams(a5),a0
  947.     move.l    xsp_Password(a0),d3
  948.     beq.s    xpkHUFF_DontEncrypt
  949.     move.l    d3,a3
  950.     move.l    xsp_OutBuf(a0),a1
  951.     addq.l    #6,a1            ;skip indicator word
  952.                     ;& password checksum
  953.     move.l    xsp_OutLen(a0),d0
  954.     move.b    (a3),d3            ;get encryptor for first byte (for the
  955.                     ;other bytes it's always the
  956.                     ;predecessor)
  957.     subq.w    #7,d0            ;dbf, skip indicator word, password
  958.                     ;checksum
  959.  
  960. ;register usage:
  961. ;
  962. ;d0:    Length of buffer to work on (dbf)
  963. ;d1:    current byte to encrypt
  964. ;d2:    byte out of passkey for encryption
  965. ;d3:    last encrypted byte for more encrytion on next byte
  966. ;a1:    *Buffer
  967. ;a3:    *password
  968.  
  969. xpkHUFF_EncryptLoop:
  970.     move.b    (a1),d1                ;byte that is to be coded
  971.     move.b    (a3)+,d2            ;byte of password
  972.     bne.s    xpkHUFF_EncryptLoopDontResetPasskeyPtr
  973.     move.l    xsp_Password(a0),a3        ;reset *password
  974.     move.b    (a3)+,d2            ;get first byte of passkey
  975. xpkHUFF_EncryptLoopDontResetPasskeyPtr:
  976.     eor.b    d2,d1                ;password byte as encryptor
  977.     add.b    d3,d1                ;last encrypted byte as
  978.                         ;encryptor
  979.     move.b    d1,(a1)+            ;write current encrypted byte
  980.     move.b    d1,d3                ;last byte is encryptor for
  981.                         ;next byte
  982.     dbf    d0,xpkHUFF_EncryptLoop
  983.  
  984. xpkHUFF_DontEncrypt:
  985.  
  986. ;__________________________________________________________
  987.  
  988. xpkHUFF_FreeReentry:
  989.     move.l    xpkHUFF_CRS_xpkSubParams(a5),-(a7)
  990.     move.l    #xpkHUFF_CRS_SIZEOF,d0
  991.     move.l    a5,a1
  992.     move.l    4.w,a6
  993.     jsr    _LVOFreeMem(a6)
  994.     sub.l    a5,a5
  995.     move.l    (a7)+,a0
  996.     moveq    #XPKERR_OK,d0
  997.     rts                    ;exit back to mapping code
  998.  
  999. xpkHUFF_AllocReentryBufferFailed:
  1000.     move.l    a2,a0                ;subparams
  1001.     moveq    #XPKERR_NOMEM,d0
  1002.     rts                    ;don't crunch
  1003.  
  1004. xpkHUFF_C_Expansion:
  1005.     move.l    xpkHUFF_CRS_xpkSubParams(a5),-(a7)
  1006.     move.l    #xpkHUFF_CRS_SIZEOF,d0
  1007.     move.l    a5,a1
  1008.     move.l    4.w,a6
  1009.     jsr    _LVOFreeMem(a6)
  1010.     sub.l    a5,a5
  1011.     move.l    (a7)+,a0
  1012.     tst.l    xsp_Password(a0)
  1013.     beq.s    XPKHUFF_C_NormalExpansion
  1014.  
  1015. xpkHUFF_C_CantEncryptBecauseOfExpansion:
  1016.  
  1017. ;if  file would expand I would have to copy data to OutBuf and encrypt there
  1018. ;without  trying  to crunch.  But my buffer would be 6 bytes larger than the
  1019. ;original  one,  for  I  add  an identifier and the password checksum at the
  1020. ;beginning  of  buffer.  This means I would exceed my buffer, which is (with
  1021. ;the current version of xpkmaster.library (V 2.1)) not allowed.  Therefore I
  1022. ;return  this  error,  to  make  sure  user  notices  that  data WILL NOT BE
  1023. ;ENCRYPTED.
  1024. ;
  1025. ;Should  only  occur  with short files (I have an indicator word, a password
  1026. ;checksum and a table size of >256 bytes which I put to OutBuf, so indicator
  1027. ;word,  password  checksum, tablesize and crunched data must be smaller than
  1028. ;InLen) or files that have already been crunched.
  1029.  
  1030.     moveq    #XPKERR_SMALLBUF,d0        ;indicates that outbuf was
  1031.                         ;too small
  1032.     rts
  1033.  
  1034. XPKHUFF_C_NormalExpansion:
  1035.     moveq    #XPKERR_EXPANSION,d0
  1036.     rts                    ;back to mapping code
  1037.  
  1038. ;__________________________________________________________
  1039.  
  1040. _XpksUnpackChunk:
  1041. ;in:
  1042. ;
  1043. ;    a0 :    *XpkSubParams
  1044. ;    a6 :    *xpkHUFF.library
  1045. ;out:
  1046. ;    d0 :    err
  1047. ;    in XpkSubParams :    xsp_OutLen
  1048. ;
  1049. ;registers trashed:
  1050. ;
  1051.  
  1052.     MOVEM.L    D2-D7/A2-A6,-(A7)
  1053.     BSR.B    UnPackMode0
  1054.     MOVEM.L    (A7)+,D2-D7/A2-A6
  1055.     RTS
  1056.  
  1057. ROOT    equ     0
  1058. NODE    equ     0
  1059. LEAF    equ     $ff                    ;leftmost bit set in
  1060.                             ;word TypeAndChar
  1061.                             ;for bpl below
  1062. xpkHUFF_DecrunchTreeNodeStruct:        rsreset
  1063. xpkHUFF_DTNS_TypeAndChar:        rs.b    0    ;for fast decrunching
  1064. xpkHUFF_DTNS_Type:            rs.b    1    ;ROOT|NODE|LEAF
  1065. xpkHUFF_DTNS_Char:            rs.b    1    ;only for leafs
  1066. xpkHUFF_DTNS_LeftSubTree:        rs.l    1    ;*left subtree
  1067. xpkHUFF_DTNS_RightSubTree:        rs.l    1    ;*righ subtree
  1068. xpkHUFF_DRS_TreeNode_SIZEOF:        rs.b    0
  1069.  
  1070. xpkHUFF_DecrunchReentryStructure:    rsreset
  1071. xpkHUFF_DRS_xpkSubParams:        rs.l    1
  1072. xpkHUFF_DRS_xpkSubLibBase:        rs.l    1
  1073. xpkHUFF_DRS_CrunchMethodIdentifier:    rs.w    1    ;to ensure I can distuinguish old crunches from new ones
  1074. xpkHUFF_DRS_PasswordChecksum:        rs.l    1    ;space for checksum of password, if password was used, a constant (currently '$ABADCAFE') otherwise
  1075. xpkHUFF_DRS_CrunchedDataTreeBuffer:    rs.l    1    ;*decrunch tree in crunched data buffer
  1076. xpkHUFF_DRS_CrunchedDataBuffer:        rs.l    1    ;*crunched data
  1077. xpkHUFF_DRS_DecrunchedDataBuffer:    rs.l    1    ;*buffer to decrunch to
  1078. xpkHUFF_DRS_CrunchedLength:        rs.l    1    ;size of crunched data in bytes
  1079. xpkHUFF_DRS_DecrunchedLength:        rs.l    1    ;size of decrunched data in bytes
  1080. xpkHUFF_DRS_RootNode:            rs.l    1    ;*root node of decrunch tree
  1081. xpkHUFF_DRS_SpaceForDecrunchTree:    rs.b    (256+255)*xpkHUFF_DRS_TreeNode_SIZEOF
  1082. xpkHUFF_DRS_DecryptBuffer:        rs.b    MaxPackChunkSize
  1083. xpkHUFF_DRS_SIZEOF:            rs.b    0
  1084.  
  1085. UnPackMode0:
  1086.     move.l    a0,a2                    ;keep xpksubparams
  1087.                             ;in mind
  1088.     move.l    a6,a3                    ;keep xpkHUFF base
  1089.                             ;in mind
  1090.     move.l    #xpkHUFF_DRS_SIZEOF,d0
  1091.     move.l    #MEMF_CLEAR|MEMF_PUBLIC,d1
  1092.     move.l    4.w,a6
  1093.     jsr    _LVOAllocMem(a6)
  1094.     tst.l    d0
  1095.     beq    xpkHUFF_AllocDecrunchReentryBufferFailed
  1096.     move.l    d0,a5                    ;reentry buffer
  1097.                             ;now in a5
  1098.     move.l    a3,xpkHUFF_DRS_xpkSubLibBase(a5)    ;store xpkHUFF base in
  1099.                             ;the reentry structure
  1100.     move.l    a2,xpkHUFF_DRS_xpkSubParams(a5)        ;store subparams in
  1101.                             ;the reentry structure
  1102. ;******************************
  1103. ;*** fill reentry structure ***
  1104. ;******************************
  1105.     move.l    xsp_InBuf(a2),a0
  1106.     move.l    xsp_InLen(a2),xpkHUFF_DRS_CrunchedLength(a5)
  1107.     subq.l    #6,xpkHUFF_DRS_CrunchedLength(a5);indicator word, password checksum
  1108.     move.l    xsp_OutBuf(a2),xpkHUFF_DRS_DecrunchedDataBuffer(a5)
  1109.     move.l    xsp_OutLen(a2),xpkHUFF_DRS_DecrunchedLength(a5)
  1110.     move.w    (a0)+,xpkHUFF_DRS_CrunchMethodIdentifier(a5)
  1111.     move.l    (a0)+,xpkHUFF_DRS_PasswordChecksum(a5)
  1112.     cmp.w    #CMI_NORMAL,xpkHUFF_DRS_CrunchMethodIdentifier(a5)
  1113.     bne    xpkHUFF_UnknownCrunchMethod            ;I cant't
  1114.                                 ;handle this
  1115.     tst.l    xsp_Password(a2)
  1116.     beq.s    xpkHUFF_D_InBufNotEncrypted
  1117.  
  1118. ;__________________________________________________________
  1119.  
  1120. ;***************************
  1121. ;*** decryption handling ***
  1122. ;***************************
  1123.  
  1124. xpkHUFF_D_CalcPasswordCheckSum:
  1125.     move.l    xsp_Password(a2),a3
  1126.     move.l    #$ABADCAFE,d0
  1127.     move.w    #$C0DE,d1
  1128.  
  1129. xpkHUFF_D_CalcPasswordChecksumLoop1:
  1130.     move.b    (a3)+,d1
  1131.     beq.s    xpkHUFF_D_CalcPasswordChecksumLoop1End
  1132.     add.w    d1,d0
  1133.     bra.s    xpkHUFF_D_CalcPasswordChecksumLoop1
  1134.  
  1135. xpkHUFF_D_CalcPasswordChecksumLoop1End:
  1136.     move.l    xsp_Password(a2),a3
  1137.     swap    d0
  1138.  
  1139. xpkHUFF_D_CalcPasswordChecksumLoop2:
  1140.     move.b    (a3)+,d1
  1141.     beq.s    xpkHUFF_D_CalcPasswordChecksumLoop2End
  1142.     eor.w    d1,d0
  1143.     rol.w    #8,d0
  1144.     bra.s    xpkHUFF_D_CalcPasswordChecksumLoop2
  1145.  
  1146. xpkHUFF_D_CalcPasswordChecksumLoop2End:
  1147.     cmp.l    xpkHUFF_DRS_PasswordChecksum(a5),d0
  1148.     beq.s    xpkHUFF_D_PasswordProbablyOK
  1149.     bsr    xpkHUFF_FreeMem
  1150.     moveq    #XPKERR_WRONGPW,d0    ;wrong password used to decrunch
  1151.     rts
  1152.  
  1153. xpkHUFF_D_PasswordProbablyOK:
  1154. ;***************
  1155. ;*** decrypt ***
  1156. ;***************
  1157.     move.l    xpkHUFF_DRS_CrunchedLength(a5),d0
  1158.     subq.w    #1,d0            ;dbf
  1159.     move.l    a0,a1            ;*InBuf
  1160.     move.l    a2,a0            ;*xpk sub params
  1161.     lea    xpkHUFF_DRS_DecryptBuffer(a5),a2
  1162.     move.l    xsp_Password(a0),a3
  1163.     move.b    (a3),d3            ;get decryptor for first byte (for the
  1164.                     ;other bytes it's always the
  1165.                     ;predecessor)
  1166. ;register usage:
  1167. ;
  1168. ;d0:    Length of buffer to work on
  1169. ;d1:    current byte to encrypt
  1170. ;d2:    byte out of passkey for encryption
  1171. ;d3:    last encrypted byte for more encrytion on next byte
  1172. ;a0:    *xpk sub params
  1173. ;a1:    *InBuf
  1174. ;a2:    *DecryptBuffer
  1175. ;a3:    *password
  1176.  
  1177. xpkHUFF_DecryptLoop:
  1178.     move.b    (a1)+,d1        ;byte that is to be decoded
  1179.     move.b    d1,d4
  1180.     move.b    (a3)+,d2        ;byte of password
  1181.     bne.s    xpkHUFF_DontResetPassWordPointer
  1182.     move.l    xsp_Password(a0),a3    ;reset *password
  1183.     move.b    (a3)+,d2        ;get first byte of password
  1184.  
  1185. xpkHUFF_DontResetPassWordPointer:
  1186.     sub.b    d3,d1            ;last encrypted byte as decryptor
  1187.     eor.b    d2,d1            ;password byte as decryptor
  1188.     move.b    d1,(a2)+        ;write current decrypted byte
  1189.     move.b    d4,d3            ;last encrypted byte is decryptor for
  1190.                     ;next byte
  1191.     dbf    d0,xpkHUFF_DecryptLoop
  1192.     lea    xpkHUFF_DRS_DecryptBuffer(a5),a0
  1193. ;    bra.s    xpkHUFF_D_OKToDecrunch
  1194.  
  1195. ;__________________________________________________________
  1196.  
  1197. xpkHUFF_D_InBufNotEncrypted:
  1198. xpkHUFF_D_OKToDecrunch:
  1199.     move.l    a0,xpkHUFF_DRS_CrunchedDataTreeBuffer(a5)
  1200.  
  1201. ;****************************
  1202. ;*** create decrunch tree ***
  1203. ;****************************
  1204.  
  1205. xpkHUFF_D_CreateDecrunchTree:
  1206.     move.l    xpkHUFF_DRS_CrunchedDataTreeBuffer(a5),a0
  1207.     lea    xpkHUFF_DRS_SpaceForDecrunchTree(a5),a1
  1208.     move.l    a1,xpkHUFF_DRS_RootNode(a5)
  1209.     move.l    a1,a3
  1210.     move.b    #ROOT,xpkHUFF_DTNS_Type(a1)
  1211.     lea    xpkHUFF_DRS_TreeNode_SIZEOF(a1),a1    ;proceed to next node
  1212.     move.l    #255,d0                    ;256 runs
  1213.     moveq    #-1,d1                    ;for fast cmp.b below
  1214.     moveq    #-1,d2                    ;initial byte
  1215.  
  1216. xpkHUFF_D_CreateDecrunchTreeLeafLoop:
  1217.     addq.b    #1,d2
  1218.     moveq    #0,d3
  1219.     move.b    (a0)+,d3                ;d3:Length
  1220.     cmp.b    d3,d1                    ;length = -1 (ie 0)?
  1221.                             ;(255 can't occur!)
  1222.     beq.s    xpkHUFF_D_CDTL_DoneWithChar
  1223.     moveq    #0,d5                    ;force dbf below
  1224.                             ;to read next byte
  1225.     move.l    a3,a2                    ;*root node
  1226.  
  1227. xpkHUFF_D_CreateDecrunchTreeNodeLoop:
  1228.     dbf    d5,xpkHUFF_D_CDTN_DontGetNextCodeByte
  1229.     move.b    (a0)+,d4
  1230.     moveq    #7,d5
  1231.     
  1232. xpkHUFF_D_CDTN_DontGetNextCodeByte:
  1233.     add.b    d4,d4                    ;leftmost bit to carry
  1234.     bcs.s    xpkHUFF_D_CDTN_RightSubTree
  1235.     
  1236. ;____________________________
  1237.  
  1238. xpkHUFF_D_CDTN_LeftSubTree:
  1239.     move.l    xpkHUFF_DTNS_LeftSubTree(a2),d6
  1240.     beq.s    xpkHUFF_D_CDTN_LeftSubTree_CreateNewNode
  1241.     move.l    d6,a2
  1242.     dbf    d3,xpkHUFF_D_CreateDecrunchTreeNodeLoop
  1243.     bra.s    xpkHUFF_D_CDTN_WriteCharDataToLeaf
  1244.  
  1245. xpkHUFF_D_CDTN_LeftSubTree_CreateNewNode:
  1246.     move.l    a1,xpkHUFF_DTNS_LeftSubTree(a2)
  1247.     move.l    a1,a2
  1248.     lea    xpkHUFF_DRS_TreeNode_SIZEOF(a1),a1
  1249.     dbf    d3,xpkHUFF_D_CreateDecrunchTreeNodeLoop
  1250.     bra.s    xpkHUFF_D_CDTN_WriteCharDataToLeaf
  1251.  
  1252. ;____________________________
  1253.  
  1254. xpkHUFF_D_CDTN_RightSubTree:
  1255.     move.l    xpkHUFF_DTNS_RightSubTree(a2),d6
  1256.     beq.s    xpkHUFF_D_CDTN_RightSubTree_CreateNewNode
  1257.     move.l    d6,a2
  1258.     dbf    d3,xpkHUFF_D_CreateDecrunchTreeNodeLoop
  1259.     bra.s    xpkHUFF_D_CDTN_WriteCharDataToLeaf
  1260.  
  1261. xpkHUFF_D_CDTN_RightSubTree_CreateNewNode:
  1262.     move.l    a1,xpkHUFF_DTNS_RightSubTree(a2)
  1263.     move.l    a1,a2
  1264.     lea    xpkHUFF_DRS_TreeNode_SIZEOF(a1),a1
  1265.     dbf    d3,xpkHUFF_D_CreateDecrunchTreeNodeLoop
  1266. ;    bra.s    xpkHUFF_D_CDTN_WriteCharDataToLeaf
  1267. ;____________________________
  1268.  
  1269. xpkHUFF_D_CDTN_WriteCharDataToLeaf:
  1270.     move.b    d2,xpkHUFF_DTNS_Char(a2)
  1271.     move.b    #LEAF,xpkHUFF_DTNS_Type(a2)
  1272.  
  1273. xpkHUFF_D_CDTL_DoneWithChar:
  1274.     dbf    d0,xpkHUFF_D_CreateDecrunchTreeLeafLoop
  1275.     move.l    a0,xpkHUFF_DRS_CrunchedDataBuffer(a5)
  1276.  
  1277. ;*********************
  1278. ;*** decrunch data ***
  1279. ;*********************
  1280.  
  1281. DecrunchData:
  1282.  
  1283. ;__________________________________________________________
  1284.  
  1285.     IFEQ    DecrunchCode
  1286.     move.l    xpkHUFF_DRS_DecrunchedLength(a5),d0
  1287.     subq.l    #1,d0
  1288.     move.l    xpkHUFF_DRS_CrunchedDataBuffer(a5),a0
  1289.     move.l    xpkHUFF_DRS_DecrunchedDataBuffer(a5),a1
  1290.     moveq    #0,d1            ;force read of first byte below
  1291.                     ;register
  1292.     move.l    xpkHUFF_DRS_RootNode(a5),a3
  1293.  
  1294. xpkHUFF_DD_ByteLoop:
  1295.     move.l    a3,a2            ;root node
  1296.  
  1297. xpkHUFF_DD_InnerLoop:
  1298.     dbf    d1,xpkHUFF_DD_IL_DontGetNewSourceByte
  1299.     move.b    (a0)+,d2
  1300.     moveq    #7,d1
  1301.  
  1302. xpkHUFF_DD_IL_DontGetNewSourceByte:
  1303.     add.b    d2,d2
  1304.     bcs.s    xpkHUFF_DD_RightSubTree
  1305.  
  1306. xpkHUFF_DD_LeftSubTree:
  1307.     move.l    xpkHUFF_DTNS_LeftSubTree(a2),a2
  1308.     move.w    xpkHUFF_DTNS_TypeAndChar(a2),d3
  1309.     bpl.s    xpkHUFF_DD_InnerLoop
  1310.     bra.s    xpkHUFF_DD_WriteChar
  1311.  
  1312. xpkHUFF_DD_RightSubTree:
  1313.     move.l    xpkHUFF_DTNS_RightSubTree(a2),a2
  1314.     move.w    xpkHUFF_DTNS_TypeAndChar(a2),d3
  1315.     bpl.s    xpkHUFF_DD_InnerLoop
  1316. ;    bra.s    xpkHUFF_DD_WriteChar
  1317.  
  1318. xpkHUFF_DD_WriteChar:
  1319.     move.b    d3,(a1)+
  1320.     dbf    d0,xpkHUFF_DD_ByteLoop
  1321.     bsr.s    xpkHUFF_FreeMem
  1322.     moveq    #XPKERR_OK,d0
  1323.     rts                ;back to mapping code
  1324.  
  1325. xpkHUFF_AllocDecrunchReentryBufferFailed:
  1326.     moveq    #XPKERR_NOMEM,d0
  1327.     rts
  1328.     ENDC        ;of IFEQ DecrunchCode
  1329.  
  1330. ;__________________________________________________________
  1331.     IFEQ    ((DecrunchCode-1)*(DecrunchCode-2)*(DecrunchCode-3)*(DecrunchCode-4))
  1332.  
  1333.  
  1334. ;*************************************************
  1335. ;*** calculate crunched length (without table) ***
  1336. ;*************************************************
  1337.  
  1338.     move.l    xpkHUFF_DRS_CrunchedDataTreeBuffer(a5),d0
  1339.     add.l    xpkHUFF_DRS_CrunchedLength(a5),d0    ;equ *byte behind
  1340.                             ;crunched data
  1341.     sub.l    xpkHUFF_DRS_CrunchedDataBuffer(a5),d0    ;equ size of crunched
  1342.                             ;data without tree
  1343.                             ;information
  1344.     IFEQ    ((DecrunchCode-1)*(DecrunchCode-2)*(DecrunchCode-4))
  1345. ;******************************************************************************
  1346. ;*** here the size of the crunched data excluding tree information is in d0 ***
  1347. ;******************************************************************************
  1348.     subq.l    #1,d0                    ;-1: last byte might
  1349.                             ;not be used
  1350.                             ;completely
  1351.     IFEQ    DecrunchCode-2
  1352.     lsr.l    #1,d0                    ;we are processing a
  1353.     ENDC                        ;word below
  1354.     IFEQ    DecrunchCode-4
  1355.     lsr.l    #2,d0                    ;we are processing a
  1356.     ENDC                        ;long below
  1357.     subq.l    #1,d0                    ;-1: dbf
  1358.     move.l    xpkHUFF_DRS_CrunchedDataBuffer(a5),a0
  1359.     move.l    xpkHUFF_DRS_DecrunchedDataBuffer(a5),a1
  1360.     move.l    xpkHUFF_DRS_RootNode(a5),a3
  1361.     move.l    a3,a2                    ;root node
  1362.  
  1363. DD_ProcessOneCrunchedByteWordLongLoop:
  1364.     IFEQ    DecrunchCode-1
  1365.     move.b    (a0)+,d2
  1366.     ENDC
  1367.     IFEQ    DecrunchCode-2
  1368.     move.w    (a0)+,d2
  1369.     ENDC
  1370.     IFEQ    DecrunchCode-4
  1371.     move.l    (a0)+,d2
  1372.     ENDC
  1373.  
  1374. ProcessOneBit    MACRO
  1375.     IFEQ    DecrunchCode-1
  1376.     add.b    d2,d2                ;leftmost bit to carry
  1377.     ENDC
  1378.     IFEQ    DecrunchCode-2
  1379.     add.w    d2,d2                ;leftmost bit to carry
  1380.     ENDC
  1381.     IFEQ    DecrunchCode-4
  1382.     add.l    d2,d2                ;leftmost bit to carry
  1383.     ENDC
  1384.     bcc.s    DD_LeftSubTree\@
  1385.  
  1386. DD_RightSubTree\@:
  1387.     move.l    xpkHUFF_DTNS_RightSubTree(a2),a2
  1388.     move.w    xpkHUFF_DTNS_TypeAndChar(a2),d3
  1389.     bpl.s    DD_ProceedWithNextBit\@
  1390.     move.b    d3,(a1)+            ;write char
  1391.     move.l    a3,a2                ;start again at root node
  1392.     bra.s    DD_CharWritten\@
  1393.  
  1394. DD_LeftSubTree\@:
  1395.     move.l    xpkHUFF_DTNS_LeftSubTree(a2),a2
  1396.     move.w    xpkHUFF_DTNS_TypeAndChar(a2),d3
  1397.     bpl.s    DD_ProceedWithNextBit\@
  1398.     move.b    d3,(a1)+            ;write char
  1399.     move.l    a3,a2                ;start again at root node
  1400. ;    bra.s    DD_CharWritten\@
  1401.  
  1402. DD_CharWritten\@:
  1403. DD_ProceedWithNextBit\@:
  1404.  
  1405.     ENDM
  1406.     IFEQ    DecrunchCode-1
  1407.     ProcessOneBit        ;1
  1408.     ProcessOneBit        ;2
  1409.     ProcessOneBit        ;3
  1410.     ProcessOneBit        ;4
  1411.     ProcessOneBit        ;5
  1412.     ProcessOneBit        ;6
  1413.     ProcessOneBit        ;7
  1414.     ProcessOneBit        ;8
  1415.     ENDC
  1416.     IFEQ    DecrunchCode-2            ;I know I could use a smarter
  1417.                         ;condition here, but I'm lazy
  1418.                         ;and it doesn't affect
  1419.                         ;executable speed
  1420.     ProcessOneBit        ;1
  1421.     ProcessOneBit        ;2
  1422.     ProcessOneBit        ;3
  1423.     ProcessOneBit        ;4
  1424.     ProcessOneBit        ;5
  1425.     ProcessOneBit        ;6
  1426.     ProcessOneBit        ;7
  1427.     ProcessOneBit        ;8
  1428.     ProcessOneBit        ;9
  1429.     ProcessOneBit        ;10
  1430.     ProcessOneBit        ;11
  1431.     ProcessOneBit        ;12
  1432.     ProcessOneBit        ;13
  1433.     ProcessOneBit        ;14
  1434.     ProcessOneBit        ;15
  1435.     ProcessOneBit        ;16
  1436.     ENDC
  1437.  
  1438.     IFEQ    DecrunchCode-4
  1439.     ProcessOneBit        ;1
  1440.     ProcessOneBit        ;2
  1441.     ProcessOneBit        ;3
  1442.     ProcessOneBit        ;4
  1443.     ProcessOneBit        ;5
  1444.     ProcessOneBit        ;6
  1445.     ProcessOneBit        ;7
  1446.     ProcessOneBit        ;8
  1447.     ProcessOneBit        ;9
  1448.     ProcessOneBit        ;10
  1449.     ProcessOneBit        ;11
  1450.     ProcessOneBit        ;12
  1451.     ProcessOneBit        ;13
  1452.     ProcessOneBit        ;14
  1453.     ProcessOneBit        ;15
  1454.     ProcessOneBit        ;16
  1455.     ProcessOneBit        ;17
  1456.     ProcessOneBit        ;18
  1457.     ProcessOneBit        ;19
  1458.     ProcessOneBit        ;20
  1459.     ProcessOneBit        ;21
  1460.     ProcessOneBit        ;22
  1461.     ProcessOneBit        ;23
  1462.     ProcessOneBit        ;24
  1463.     ProcessOneBit        ;25
  1464.     ProcessOneBit        ;26
  1465.     ProcessOneBit        ;27
  1466.     ProcessOneBit        ;28
  1467.     ProcessOneBit        ;29
  1468.     ProcessOneBit        ;30
  1469.     ProcessOneBit        ;31
  1470.     ProcessOneBit        ;32
  1471.     ENDC
  1472.     dbf    d0,DD_ProcessOneCrunchedByteWordLongLoop
  1473.     ENDC    ;of IFEQ ((DecrunchCode-1)*(DecrunchCode-2)*(DecrunchCode-4))
  1474.  
  1475. ;__________________________________________________________
  1476.  
  1477.     IFEQ    DecrunchCode-3        ;68030+ cache oriented decrunch code
  1478.  
  1479. ;******************************************************************************
  1480. ;*** here the size of the crunched data excluding tree information is in d0 ***
  1481. ;******************************************************************************
  1482.  
  1483.     subq.l    #1,d0                ;-1: last byte might not be used completely
  1484.     lsr.l    #2,d0                ;we are processing a whole long below
  1485.     subq.l    #1,d0                ;-1: dbf
  1486.     move.l    xpkHUFF_DRS_CrunchedDataBuffer(a5),a0
  1487.     move.l    xpkHUFF_DRS_DecrunchedDataBuffer(a5),a1
  1488.     move.l    xpkHUFF_DRS_RootNode(a5),a3
  1489.     move.l    a3,a2                ;root node
  1490.  
  1491. DD_ProcessOneCrunchedByteLoop:
  1492.     move.l    (a0)+,d2
  1493.     bsr.s    DD_ProcessFourBitSubRoutine    ; 1- 4
  1494.     bsr.s    DD_ProcessFourBitSubRoutine    ; 5- 8
  1495.     bsr.s    DD_ProcessFourBitSubRoutine    ; 9-12
  1496.     bsr.s    DD_ProcessFourBitSubRoutine    ;13-16
  1497.     bsr.s    DD_ProcessFourBitSubRoutine    ;17-20
  1498.     bsr.s    DD_ProcessFourBitSubRoutine    ;21-24
  1499.     bsr.s    DD_ProcessFourBitSubRoutine    ;25-28
  1500.     bsr.s    DD_ProcessFourBitSubRoutine    ;29-32
  1501.     dbf    d0,DD_ProcessOneCrunchedByteLoop
  1502.     bra    DD_AlmostDone
  1503.  
  1504. DD_ProcessFourBitSubRoutine:
  1505.  
  1506. ;____________________________
  1507.  
  1508. ProcessOneBitCodeMACRO    MACRO
  1509.     add.l    d2,d2                ;leftmost bit to carry
  1510.     bcc.s    DD_LeftSubTree\@
  1511.  
  1512. DD_RightSubTree\@:
  1513.     move.l    xpkHUFF_DTNS_RightSubTree(a2),a2
  1514.     move.w    xpkHUFF_DTNS_TypeAndChar(a2),d3
  1515.     bpl.s    DD_ProceedWithNextBit\@
  1516.     move.b    d3,(a1)+            ;write char
  1517.     move.l    a3,a2                ;start again at root node
  1518.     IFEQ    \1-0
  1519.     bra.s    DD_CharWritten\@
  1520.     ENDC
  1521.     IFEQ    \1-1
  1522.     rts
  1523.     ENDC
  1524.  
  1525. DD_LeftSubTree\@:
  1526.     move.l    xpkHUFF_DTNS_LeftSubTree(a2),a2
  1527.     move.w    xpkHUFF_DTNS_TypeAndChar(a2),d3
  1528.     bpl.s    DD_ProceedWithNextBit\@
  1529.     move.b    d3,(a1)+            ;write char
  1530.     move.l    a3,a2                ;start again at root node
  1531. ;    bra.s    DD_CharWritten\@
  1532.  
  1533. DD_CharWritten\@:
  1534. DD_ProceedWithNextBit\@:
  1535.     IFEQ    \1-1
  1536.     rts
  1537.     ENDC
  1538.  
  1539.     ENDM
  1540. ;____________________________
  1541.  
  1542.     ProcessOneBitCodeMACRO    0    ;1
  1543.     ProcessOneBitCodeMACRO    0    ;2
  1544.     ProcessOneBitCodeMACRO    0    ;3
  1545.     ProcessOneBitCodeMACRO    1    ;4    ;last MACRO will have rts
  1546.                         ;instead of bra
  1547. DD_AlmostDone:
  1548.     ENDC ;of IFEQ DecrunchCode-3 ;68030+ cache oriented decrunch code
  1549.  
  1550. ;__________________________________________________________
  1551.  
  1552. ProcessLastByteOrBytesOfCrunchedData:
  1553.     move.l    a1,d1
  1554.     sub.l    xpkHUFF_DRS_DecrunchedDataBuffer(a5),d1
  1555. ;= number of bytes already decrunched to output buffer
  1556.     move.l    xpkHUFF_DRS_DecrunchedLength(a5),d0
  1557.     sub.l    d1,d0
  1558. ;= number of bytes still to decrunch (ranges from 1..31, depending on decrunch code, too)
  1559.     beq.s    DD_Done
  1560.     subq.l    #1,d0                    ;dbf
  1561.     moveq    #0,d4                    ;force read of next byte below
  1562. ;note: the loop above was over the crunched bytes, the loop below is over
  1563. ;       uncrunched bytes, therefore we have a different code here
  1564.  
  1565. ;____________________________
  1566.  
  1567. DD_Loop:
  1568.     dbf    d4,DD_DontGetNewByte
  1569.     move.b    (a0)+,d2
  1570.     moveq    #7,d4
  1571.  
  1572. DD_DontGetNewByte:
  1573.     add.b    d2,d2            ;leftmost bit to carry
  1574.     bcc.s    DD_LeftSubTree
  1575.  
  1576. DD_RightSubTree:
  1577.     move.l    xpkHUFF_DTNS_RightSubTree(a2),a2
  1578.     move.w    xpkHUFF_DTNS_TypeAndChar(a2),d3
  1579.     bpl.s    DD_Loop
  1580.     bra.s    DD_WriteChar
  1581.  
  1582. DD_LeftSubTree:
  1583.     move.l    xpkHUFF_DTNS_LeftSubTree(a2),a2
  1584.     move.w    xpkHUFF_DTNS_TypeAndChar(a2),d3
  1585.     bpl.s    DD_Loop
  1586. ;    bra.s    DD_WriteChar
  1587.  
  1588. DD_WriteChar:
  1589.     move.b    d3,(a1)+    ;write decrunched byte
  1590.     move.l    a3,a2        ;start again at root node
  1591.     dbf    d0,DD_Loop
  1592. ;____________________________
  1593.  
  1594. DD_Done:
  1595.     move.l    xpkHUFF_CRS_xpkSubParams(a5),a0
  1596.     bsr.s    xpkHUFF_FreeMem
  1597.     moveq    #XPKERR_OK,d0
  1598.     rts                        ;back to mapping code
  1599.  
  1600. xpkHUFF_AllocDecrunchReentryBufferFailed:
  1601.     move.l    a2,a0                    ;subparams
  1602.     moveq    #XPKERR_NOMEM,d0
  1603.     rts
  1604.     ENDC    ;of IFEQ ((DecrunchCode-1)*(DecrunchCode-2)*(DecrunchCode-3)*(DecrunchCode-4))
  1605.  
  1606. xpkHUFF_UnknownCrunchMethod:
  1607.     move.l    xpkHUFF_DRS_xpkSubParams(a5),a0
  1608.     bsr.s    xpkHUFF_FreeMem
  1609.     moveq    #XPKERR_OLDSUBLIB,d0
  1610.     rts
  1611.  
  1612. xpkHUFF_FreeMem:
  1613.     movem.l    d0/d1/a0/a1,-(a7)
  1614.     move.l    #xpkHUFF_DRS_SIZEOF,d0
  1615.     move.l    a5,a1
  1616.     move.l    4.w,a6
  1617.     JSR    _LVOFreeMem(A6)
  1618.     movem.l    (a7)+,d0/d1/a0/a1
  1619.     rts
  1620.  
  1621. HUFFXpkInfo
  1622.     DC.W    1        ; Version number of this structure
  1623.     DC.W    VERSION        ; The version of this sublibrary
  1624.     DC.W    1        ; The required master lib version
  1625.     DC.W    0        ; Longword align
  1626.     DC.L    BriefName    ; Brief name of the packer
  1627.     DC.L    FullName    ; Full name of the packer
  1628.     DC.L    Description    ; One line description of packer
  1629.     DC.L    'HUFF'        ; ID the packer goes by (XPK format)
  1630.     DC.L    XPKIF_PK_CHUNK|XPKIF_UP_CHUNK|XPKIF_ENCRYPTION
  1631.     DC.L    MaxPackChunkSize; Max input chunk size for packing
  1632.     DC.L    MinPackChunkSize; Min input chunk size for packing
  1633.     DC.L    DefPackChunkSize; Default packing chunk size
  1634.     DC.L    PackMsg        ; Packing message, present tense
  1635.     DC.L    UnpackMsg    ; Unpacking message, present tense
  1636.     DC.L    PackedMsg    ; Packing message, past tense
  1637.     DC.L    UnpackedMsg    ; Unpacking message, past tense
  1638.     DC.W    DefMode        ; Default mode number
  1639.     DC.W    0        ; for future use
  1640.     DC.L    HUFFXpkMode    ; Array of compression modes
  1641.     DC.L    0,0,0,0,0,0    ; Future expansion - set to zero
  1642.  
  1643. HUFFXpkMode
  1644.     DC.L    0            ; Chain to next descriptor for ModeDesc list
  1645.     DC.L    100            ; Maximum efficiency handled by this mode
  1646.     DC.L    XPKMF_A3000SPEED
  1647.     DC.L    xpkHUFF_CRS_SIZEOF     ; Extra memory required during packing
  1648.     DC.L    xpkHUFF_DRS_SIZEOF     ; Extra memory during unpacking
  1649.     DC.L    88            ; Approx packing speed in K per second
  1650.     IFEQ    DecrunchCode-0
  1651.     DC.L    100            ; Approx unpacking speed in K per second
  1652.     ENDC
  1653.     IFEQ    DecrunchCode-1
  1654.     DC.L    138            ; Approx unpacking speed in K per second
  1655.     ENDC
  1656.     IFEQ    DecrunchCode-2
  1657.     DC.L    89            ; Approx unpacking speed in K per second
  1658.     ENDC
  1659.     IFEQ    DecrunchCode-3
  1660.     DC.L    93            ; Approx unpacking speed in K per second
  1661.     ENDC
  1662.     IFEQ    DecrunchCode-4
  1663.     DC.L    91            ; Approx unpacking speed in K per second
  1664.     ENDC
  1665.     DC.W    241            ; CF in 0.1% for AmigaVision executable
  1666.     DC.W    MaxPackChunkSize/1024    ; Desired chunk size in K (!!) for this mode
  1667.     DC.B    'normal',0,0,0,0    ;8 character mode description
  1668.  
  1669. PackMsg        DC.B    'Crunching',0
  1670. UnpackMsg    DC.B    'Decrunching',0
  1671. PackedMsg    DC.B    'Crunched',0
  1672. UnpackedMsg    DC.B    'Decrunched',0
  1673. BriefName    DC.B    'HUFF',0
  1674. FullName    DC.B    'Huffman',0
  1675. Description
  1676.     IFEQ    DecrunchCode-0
  1677.     dc.b    "Dynamic huffman crunch algorithm, "
  1678.     dc.b    "very simple decrunch algorithm",00
  1679.     ENDC
  1680.     IFEQ    DecrunchCode-1
  1681.     dc.b    "Dynamic huffman crunch algorithm, "
  1682.     dc.b    "cache optimized byte decrunch algorithm",00
  1683.     ENDC
  1684.     IFEQ    DecrunchCode-2
  1685.     dc.b    "Dynamic huffman crunch algorithm, "
  1686.     dc.b    "word oriented decrunch algorithm",00
  1687.     ENDC
  1688.     IFEQ    DecrunchCode-3
  1689.     dc.b    "Dynamic huffman crunch algorithm, "
  1690.     dc.b    "68030+ cache oriented decrunch algorithm",00
  1691.     ENDC
  1692.     IFEQ    DecrunchCode-4
  1693.     dc.b    "Dynamic huffman crunch algorithm, "
  1694.     dc.b    "long oriented decrunch algorithm",00
  1695.     ENDC
  1696.     END
  1697.