INCLUDE AINCLUDE:IncDirs.i *sets all includedirs, needed for my ASM INCLUDE HUFF/xpkLibHUFF.i include "xpk/xpk.i" include "xpk/xpksub.i" INCLUDE exec/memory.i ; License/Disclaimer ; ------------------ ; ; This source may be freely distributed with the XPK compression package, ;as long as it is kept in its original, complete, and unmodified form. It ;may not be distributed by itself or in a commercial package of any kind ;without my permission. ; ; This source is distributed in the hope that it will be useful, but ;WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY ;or FITNESS FOR A PARTICULAR PURPOSE. ; ; M.Zimmermann (zimmerma@helios.ibr.cs.tu-bs.de) DecrunchCode equ 1 ;0: first code ;1: byte oriented, chache optimized ; decrunching ;2: word oriented decrunching (probably best ; on 68000) ;3: 68030+ cache oriented decrunching ;4: long oriented decrunching ;CrunchMethodIdentifier: CMI_NORMAL equ 0 ;maybe there will be other crunch ;methods/formats l8er ;History: ; ; V 0.1 - 12-Jul-1992 : first version ; V x.yy - 18-Jul-1992 : first OK version ; V x.yy - 19-Jul-1992 : sped up decrunching ; V x.yy - 21-Jul-1992 : bug fixed in word/long decrunching: min pack ; chunk size now 3/5 ; V x.yy - 21-Jul-1992 : replaced many subq/bxx with dbf (ie sped up ; crunching a little bit), bug fixed: there was ; a dbf counter wrong (one of my favorite 0/1 ; problem bugs) ; V 0.50 - 29-Jul-1992 : added 68030+ cache optimized decrunch code ; V 0.51 - 01-Aug-1992 : byte decrunch improved, first code added, ; indicator byte for crunchmethod used added, ; 68030+ chache optimized code does not make ; sense any more, since byte decrunch fits to ; cache completely, now ; V 0.52 - 01-Aug-1992 : unsafe encryption supported ; V 0.53 - 03-Aug-1992 : slight improvements made to crunch code ; (+ 6K/s) ; V 0.54 - 03-Aug-1992 : inconsistence in expansion handling fixed ; V 0.55 - 03-Aug-1992 : bug fixed: expansion handling now considers ; table creation, too ; V 0.56 - 03-Aug-1992 : bug fixed: HUFF now can crunch files ; consisting of always the same byte (shame ; on me, termination criterium was wrong) ; V 0.57 - 03-Aug-1992 : Tree creation code partially rewritten ; V 0.58 - 05-Aug-1992 : bug fixed: wrong termination criterium for ; expansion check (my favorite 0/1 problem) ; V 0.59 - 06-Aug-1992 : now decrypting in a special buffer, not using ; InBuf (this is read only, I was told) any more ; V 0.60 - 07-Aug-1992 : added extra memory required during ; packing/unpacking ; V 0.61 - 08-Aug-1992 : expansion check changed, renamed from ; xpkDHUF.library to xpkHUFF.library thus ; corresponding to the possibility of handling ; adaptive huffman codes later without having ; an inconsistence in the name ; V 0.62 - 10-Aug-1992 : Flag XPKIF_MODES removed (I don't have modes ; yet (but I have a mapping code :-=)) ;********************************* ;*** xpk specific declarations *** ;********************************* MaxPackChunkSize EQU 65534 ;Max input chunk size for processing IFEQ DecrunchCode-0 MinPackChunkSize equ 1 ;Min input chunk size for ENDC ;processing IFEQ DecrunchCode-1 MinPackChunkSize equ 1 ;Min input chunk size for ENDC ;processing IFEQ DecrunchCode-2 MinPackChunkSize equ 3 ;Min input chunk size for ENDC ;processing IFEQ DecrunchCode-3 MinPackChunkSize equ 5 ;Min input chunk size for ENDC ;processing IFEQ DecrunchCode-4 MinPackChunkSize equ 5 ;Min input chunk size for ENDC ;processing DefPackChunkSize equ MaxPackChunkSize ;Default processing input size (must be lower tahn or equal to MaxPackChunkSize) DefMode equ 50 ;Default mode/efficiency, ranges from [0..100] ;******************************** ;*** xpk sublibrary functions *** ;******************************** _XpksPackerInfo: LEA HUFFXpkInfo,A0 MOVE.L A0,D0 RTS ;********************** ;*** un-/pack modes *** ;********************** ;mode 0 performs: dynamic huffman crunching _XpksPackChunk ;in: ; ; a0 : *XpkSubParams ; a6 : *xpkHUFF.library ;out: ; d0 : err ; in XpkSubParams : xsp_OutLen ; ;registers trashed: MOVEM.L D2-D7/A2-A6,-(A7) BSR.B PackMode0 MOVEM.L (A7)+,D2-D7/A2-A6 RTS ;****************************** ;*** huffman node structure *** ;****************************** UNUSED equ 0 NODEUSED equ 1 NODEUNUSED equ 2 LEAFLINKED equ 3 ;leaf already is linked somewhere in the tree LEAFUNLINKED equ 4 ;leaf is not yet linked to any node in the tree ROOTNODE equ 5 LEFTSUBTREE equ 0 ;indicates that this node is at the left branch of it's parent RIGHTSUBTREE equ 1 ;indicates that this node is at the right branch of it's parent NODIRECTION equ -1 ;for root node only NOLISTLINKYET equ -1 HuffmanNodeStructure RSRESET xpkHUFF_LinkToNextNodeOrLeaf RS.L 1 ;* for fast tree creation xpkHUFF_Sum RS.W 1 ;sum of left and right subtree sums xpkHUFF_Char RS.B 1 ;byte # (0..255) if leaf, invalid else xpkHUFF_Type RS.B 1 ;UNUSED|NODEUSED|NODEUNUSED| ;LEAFUSED|LEAFUNUSED xpkHUFF_Parent RS.L 1 ;*parent node or 0 xpkHUFF_Left RS.L 1 ;*left subtree xpkHUFF_Right: rs.l 1 ;*right subtree xpkHUFF_Direction: rs.w 1 ;direction which to take from ;parent to this node xpkHUFF_pad1: rs.w 1 xpkHUFF_pad2: rs.l 1 xpkHUFF_pad3: rs.l 1 xpkHUFF_HuffmanNodeStruct_SIZEOF: rs.b 0 ;size: 8 longs ==> ;shifing for size ;correction possible ;************************* ;*** reentry structure *** ;************************* MAXHUFFMANCODELENGTH equ 256/8 CrunchReentryStructure: rsreset xpkHUFF_CRS_xpkSubParams: rs.l 1 ;*SubParamsStructure xpkHUFF_CRS_xpkSubLibBase: rs.l 1 ;the pointer to my sublibrary xpkHUFF_CRS_StatisticArray: rs.b 256*2 ;Word_SIZEOF: max InputBuffer allowed is 64K! xpkHUFF_CRS_InBuf: rs.l 1 ;*input buffer xpkHUFF_CRS_InLen: rs.l 1 ;size of input buffer in bytes xpkHUFF_CRS_OutBuf: rs.l 1 ;*output buffer xpkHUFF_CRS_OutLen: rs.l 1 ;will be set to output buffer size after crunching xpkHUFF_CRS_OutBufLen: rs.l 1 ;for overflow check when crunching (recognize expansion) xpkHUFF_CRS_CrunchedLength: rs.l 1 xpkHUFF_CRS_DynamicHuffmanTreeLeafs: rs.b 256*xpkHUFF_HuffmanNodeStruct_SIZEOF xpkHUFF_CRS_DynamicHuffmanTerminatorLeaf: rs.b xpkHUFF_HuffmanNodeStruct_SIZEOF ;MUST stay uninitialized for a terminating condition below xpkHUFF_CRS_DynamicHuffmanTreeNodes: rs.b 255*xpkHUFF_HuffmanNodeStruct_SIZEOF xpkHUFF_CRS_RootNode: rs.l 1 xpkHUFF_CRS_PtrTableToSizesAndCodes: rs.l 256*4 xpkHUFF_CRS_SpaceForLengthsAndCodes: rs.b 256*MAXHUFFMANCODELENGTH+256 ;size will be stored in bytes here xpkHUFF_CRS_SIZEOF: rs.b 0 ;************ ;*** main *** ;************ PackMode0: move.l a0,a2 ;keep subparams in mind move.l a6,a3 ;keep xpkHUFF base in mind move.l #xpkHUFF_CRS_SIZEOF,d0 move.l #MEMF_CLEAR|MEMF_PUBLIC,d1 move.l 4.w,a6 jsr _LVOAllocMem(a6) tst.l d0 beq xpkHUFF_AllocReentryBufferFailed move.l d0,a5 ;reentry buffer in a5, now move.l a3,xpkHUFF_CRS_xpkSubLibBase(a5) ;store xpkHUFF base ;in the reentry structure move.l a2,xpkHUFF_CRS_xpkSubParams(a5) ;store xpksubparams ;in reentry structure ;******************************************** ;*** get data from xpksubparams structure *** ;******************************************** move.l xsp_InBuf(a2),xpkHUFF_CRS_InBuf(a5) move.l xsp_InLen(a2),xpkHUFF_CRS_InLen(a5) move.l xsp_OutBuf(a2),xpkHUFF_CRS_OutBuf(a5) move.l xsp_OutBufLen(a2),xpkHUFF_CRS_OutBufLen(a5) ;******************************* ;*** create statistics table *** ;******************************* xpkHUFF_StatisticLoopInit: move.l xpkHUFF_CRS_InBuf(a5),a0 move.l xpkHUFF_CRS_InLen(a5),d0 ;InLen <= MaxPackChunkSize! subq.l #1,d0 ;dbf lea xpkHUFF_CRS_StatisticArray(a5),a1 xpkHUFF_StatisticLoop: moveq #0,d1 move.b (a0)+,d1 add.w d1,d1 ;byte offset ;-> word offset addq.w #1,0(a1,d1.w) dbf d0,xpkHUFF_StatisticLoop ;*************************************** ;*** init leafs in reentry structure *** ;*************************************** xpkHUFF_InitLeafs: lea xpkHUFF_CRS_StatisticArray(a5),a0 lea xpkHUFF_CRS_DynamicHuffmanTreeLeafs(a5),a1 moveq #-1,d0 ;current byte # moveq #LEAFUNLINKED,d1 moveq #-2,d2 ;current byte's ;word offset move.w #255,d3 ;256 runs (bytes range ;from 0..255) moveq #NOLISTLINKYET,d4 xpkHUFF_InitLeafsLoop: addq.l #1,d0 ;next byte number addq.l #2,d2 ;next word offset move.w 0(a0,d2.w),d5 beq.s xpkHUFF_ILL_DontConsiderEmptyLeaf move.b d0,xpkHUFF_Char(a1) ;current byte # move.b d1,xpkHUFF_Type(a1) ;type := LEAFUNLINKED move.w d5,xpkHUFF_Sum(a1) move.l d4,xpkHUFF_LinkToNextNodeOrLeaf(a1) lea xpkHUFF_HuffmanNodeStruct_SIZEOF(a1),a1 ;proceed to next leaf xpkHUFF_ILL_DontConsiderEmptyLeaf: dbf d3,xpkHUFF_InitLeafsLoop ;*********************************** ;*** link leafs from low to high *** ;*********************************** FindHighestSum MACRO ;finds highest sum of all currently unlinked nodes and returns a pointer to ;that node in a2 ; ;registers trashed: a0, d1, a2 xpkHUFF_LL_FindHighestSum: lea xpkHUFF_CRS_DynamicHuffmanTreeLeafs(a5),a0 moveq #0,d1 ;initial sum sub.l a2,a2 ;currently no node ;with highest sum xpkHUFF_LL_FindHighestSumLoop: tst.b xpkHUFF_Type(a0) ;= cmp.w #UNUSED, ;pkHUFF_Type, ie did beq.s xpkHUFF_LL_FoundHighestSum ; we reach the end of ;the list? cmp.l xpkHUFF_LinkToNextNodeOrLeaf(a0),d3 ;already considered? bne.s xpkHUFF_LL_AlreadyConsidered cmp.w xpkHUFF_Sum(a0),d1 bhi.s xpkHUFF_LL_NoHigherSum move.w xpkHUFF_Sum(a0),d1 ;current sum move.l a0,a2 ;remember this adr xpkHUFF_LL_AlreadyConsidered: xpkHUFF_LL_NoHigherSum: lea xpkHUFF_HuffmanNodeStruct_SIZEOF(a0),a0 bra.s xpkHUFF_LL_FindHighestSumLoop xpkHUFF_LL_FoundHighestSum: ENDM ;register usage: ; ; a1: *last node xpkHUFF_LinkLeafs: moveq #0,d2 ;for a fast cmp below sub.l a1,a1 ;keep 'last' node in ;mind (in this case no ;last node) moveq #NOLISTLINKYET,d3 ;for cmp below xpkHUFF_LinkLeafsLoop: FindHighestSum ;here a2 contains the adr of the node with the highest sum or 0, if all nodes ;are linked already cmp.l d2,a2 ;no highest sum any ;more? beq.s xpkHUFF_LeavesLinked ;nope: ==> done move.l a1,xpkHUFF_LinkToNextNodeOrLeaf(a2) move.l a2,a1 bra.s xpkHUFF_LinkLeafsLoop xpkHUFF_LeavesLinked: move.l a1,a4 ;here a4 contains the currently first node ;********************* ;*** CreateNewNode *** ;********************* CreateNewNode MACRO ;in: a0: *A ; a1: *N move.l a1,a2 move.l xpkHUFF_LinkToNextNodeOrLeaf(a0),a1 ;a0: *A ;a1: *B ;a2: *N move.w #LEFTSUBTREE,xpkHUFF_Direction(a0) move.w #RIGHTSUBTREE,xpkHUFF_Direction(a1) move.w xpkHUFF_Sum(a0),d0 add.w xpkHUFF_Sum(a1),d0 move.w d0,xpkHUFF_Sum(a2) move.b #NODEUSED,xpkHUFF_Type(a2) ; move.b #LEAFLINKED,xpkHUFF_Type(a0) ;not necessary, therefore not assembled ; move.b #LEAFLINKED,xpkHUFF_Type(a1) ;not necessary, therefore not assembled move.l a0,xpkHUFF_Left(a2) move.l a1,xpkHUFF_Right(a2) move.l a2,xpkHUFF_Parent(a0) move.l a2,xpkHUFF_Parent(a1) move.l xpkHUFF_LinkToNextNodeOrLeaf(a1),a0 lea xpkHUFF_HuffmanNodeStruct_SIZEOF(a2),a1 ;a0: *C ;a1: *O ;a2: *N ENDM ;*************************** ;*** insert node to list *** ;*************************** InsertTreeNodeToList MACRO ;in: a0: *first node in list ; a2: *node to insert in list ;a0: *first node in list (*C) ;a1: MUST BE LEFT UNTOUCHED ;a2: *node to insert (*N) ;have the last two nodes been linked to a lonely (ie in this case root) node? ;if so, we are ready cmp.l a0,d7 ;d7 = 0 bne.s HSH1L_a2IsNoLonelyNode move.l a2,a0 bra.s xpkHUFF_InsertionComplete HSH1L_a2IsNoLonelyNode: move.w xpkHUFF_Sum(a2),d0 ;_____________ cmp.w xpkHUFF_Sum(a0),d0 bhi.s xpkHUFF_DontInsertAsHeadOfList xpkHUFF_InsertAsHeadOfList: ;case: 3 5 7 ... insert 2 before 3 move.l a0,xpkHUFF_LinkToNextNodeOrLeaf(a2) move.l a2,a0 bra.s xpkHUFF_InsertionComplete ;_____________ xpkHUFF_DontInsertAsHeadOfList: move.l a0,a3 ;*first node in list xpkHUFF_ProceedToNextNode: cmp.l xpkHUFF_LinkToNextNodeOrLeaf(a3),d7 beq.s xpkHUFF_InsertAtEndOfList move.l a3,a4 move.l xpkHUFF_LinkToNextNodeOrLeaf(a3),a3 cmp.w xpkHUFF_Sum(a3),d0 bhi.s xpkHUFF_ProceedToNextNode ;_____________ xpkHUFF_InsertInMiddleOfList: ;case: 3 5 ... insert 4 between 3 and 5 move.l a2,xpkHUFF_LinkToNextNodeOrLeaf(a4) move.l a3,xpkHUFF_LinkToNextNodeOrLeaf(a2) bra.s xpkHUFF_InsertionComplete ;_____________ xpkHUFF_InsertAtEndOfList: ;in: a3: *last node in list ;case: 3 5 7 insert 8 behind 7 move.l a2,xpkHUFF_LinkToNextNodeOrLeaf(a3) move.l d7,xpkHUFF_LinkToNextNodeOrLeaf(a2) ; bra.s xpkHUFF_InsertionComplete ;_____________ xpkHUFF_InsertionComplete: ;a0: *first node in list ENDM ;******************* ;*** create tree *** ;******************* ;Here we have all leafs lying next to each other, in order 0..255. They are ;linked via a single pointer (xpkHUFF_LinkToNextNodeOrLeaf). If you start ;with a4 here and proceed using the link pointers, you will find all leaves ;in ascending order (order: low to high by xpkHUFF_Sum). ; ;suggest we have the nodes ; ; A B C D E F G H . . . N O P ; 3 5 6 7 8 9 10 11 new (currently unused) nodes ; ;Now we have to create a new node N with A as xpkHUFF_Left and B as ;xpkHUFF_Right. This new node N has to be sorted into he list (ie between D ;and E). The nodes A and B are excluded from the list when creating the new ;node N. This will go on until there are only two nodes left. These will be ;linked by the root node of the huffman tree. ;register usage: ; a0: *current root of used nodes (at the beginning *A) ; a1: *currently first unused node (at the beginning *N) move.l a4,a0 ;a0: *A lea xpkHUFF_CRS_DynamicHuffmanTreeNodes(a5),a1 ;a1: *N moveq #0,d7 cmp.l xpkHUFF_LinkToNextNodeOrLeaf(a0),d7 ;is there only ;one node? bne.s xpkHUFF_CreateTreeLoop ;nope: construct ; tree xpkHUFF_ThereIsOnlyOneNode: ;create tree ;containing ;only one leaf ;create new root node at (a1) move.w #LEFTSUBTREE,xpkHUFF_Direction(a0) ; move.w xpkHUFF_Sum(a0),xpkHUFF_Sum(a1) move.l a0,xpkHUFF_Left(a1) move.l a1,xpkHUFF_Parent(a0) move.l a1,a2 ;new root ;in a2 bra.s xpkHUFF_TreeCreationComplete xpkHUFF_CreateTreeLoop: cmp.l xpkHUFF_LinkToNextNodeOrLeaf(a0),d7 beq.s xpkHUFF_TreeCreationComplete CreateNewNode ;creates new node from a0 (A) and the ;sequel node of A (B) in node a1 (N). ;increments a0 (will point to C ;afterwards) and a1 (will point to O ;afterwards). ;returns adr of N in a2 InsertTreeNodeToList ;insert the node we just created ;(a2: N) into the list (a0: C) ;positioned according to it's ;xpkHUFF_Sum field. bra.s xpkHUFF_CreateTreeLoop xpkHUFF_TreeCreationComplete: ;a2: *root node of huffman tree move.b #ROOTNODE,xpkHUFF_Type(a2) move.w #NODIRECTION,xpkHUFF_Direction(a2) move.l a2,xpkHUFF_CRS_RootNode(a5) xpkHUFF_CreateTranslationTableSizesAndCodes: ;********************************************************** ;*** create translation table, sizes of codes and codes *** ;********************************************************** lea xpkHUFF_CRS_DynamicHuffmanTreeLeafs(a5),a0 lea xpkHUFF_CRS_PtrTableToSizesAndCodes(a5),a3 lea xpkHUFF_CRS_SpaceForLengthsAndCodes(a5),a4 xpkHUFF_CreateTranslationTableSizesAndCodesLoop: ;____________________________ xpkHUFF_GetOneLeafsCode: ;get code of leaf a0 ;write length as byte to (a4)+ ;write bitcode of leaf pointed to by a0 to (a4)+ behind size move.b xpkHUFF_Char(a0),d5 ;keep char in mind moveq #0,d6 move.b d5,d6 add.w d6,d6 ;offset: add.w d6,d6 ;.b -> .l move.l a4,0(a3,d6.w) ;put pointer to table moveq #-1,d1 ;bit counter (dbf) move.l a0,a1 xpkHUFF_GetOneLeafsCodeLoop: moveq #0,d0 move.w xpkHUFF_Direction(a1),d0 ;root reached? bmi.s xpkHUFF_PutOneLeafsCompleteCodeOnStack ;yep addq.l #1,d1 ;one more bit for code move.w d0,-(a7) move.l xpkHUFF_Parent(a1),a1 ;go up bra.s xpkHUFF_GetOneLeafsCodeLoop xpkHUFF_PutOneLeafsCompleteCodeOnStack: ;here all bits are on the stack, d1 is a dbf counter for composition move.b d1,(a4)+ xpkHUFF_ComposeHuffmanCode: moveq #0,d2 ;will contain ;composed code moveq #7,d3 ;# of bits not yet ;used in dest ;register (dbf) xpkHUFF_ComposeHuffmanCodeLoop: move.w (a7)+,d0 roxr.b #1,d0 ;code bit to x & c ;flag addx.b d2,d2 ;code bit to composed ;code register dbf d3,xpkHUFF_CHCL_DontWriteCodeByte moveq #7,d3 ;reset counter move.b d2,(a4)+ ;write to buffer xpkHUFF_CHCL_DontWriteCodeByte: dbf d1,xpkHUFF_ComposeHuffmanCodeLoop ;write the last byte (this could contain 1 to 7 bits) if not already written cmp.w #7,d3 ;last byte already ;written? beq.s xpkHUFF_CHCL_DontWriteLastByte ;yep addq.w #1,d3 ;was dbf counter lsl.b d3,d2 ;shift bits to left ;edge of byte move.b d2,(a4)+ ;write last byte ;to buffer xpkHUFF_CHCL_DontWriteLastByte: ;____________________________ lea xpkHUFF_HuffmanNodeStruct_SIZEOF(a0),a0 ;proceed to next leaf tst.b xpkHUFF_Type(a0) ;equ cmp.b #UNUSED,... bne.s xpkHUFF_CreateTranslationTableSizesAndCodesLoop ;************************************** ;*** identifier & password handling *** ;************************************** cmp.l #6,xpkHUFF_CRS_OutBufLen(a5) ;2: indicator word, ;4: password checksum bls xpkHUFF_C_Expansion ;***************************** ;*** write identifier word *** ;***************************** move.l xpkHUFF_CRS_OutBuf(a5),a1 move.w #CMI_NORMAL,(a1)+ ;word indicating ;crunchmethod used ;____________________________ ;************************* ;*** password handling *** ;************************* move.l xpkHUFF_DRS_xpkSubParams(a5),a0 xpkHUFF_C_CalcPasswordCheckSum: move.l #$ABADCAFE,d0 move.l xsp_Password(a0),d2 beq.s xpkHUFF_C_CPCS_NoPassword move.w #$C0DE,d1 move.l d2,a2 xpkHUFF_C_CalcPasswordChecksumLoop1: move.b (a2)+,d1 beq.s xpkHUFF_C_CalcPasswordChecksumLoop1End add.w d1,d0 bra.s xpkHUFF_C_CalcPasswordChecksumLoop1 xpkHUFF_C_CalcPasswordChecksumLoop1End: move.l xsp_Password(a0),a2 swap d0 xpkHUFF_C_CalcPasswordChecksumLoop2: move.b (a2)+,d1 beq.s xpkHUFF_C_CalcPasswordChecksumLoop2End eor.w d1,d0 rol.w #8,d0 bra.s xpkHUFF_C_CalcPasswordChecksumLoop2 xpkHUFF_C_CalcPasswordChecksumLoop2End: xpkHUFF_C_CPCS_NoPassword: move.l d0,(a1)+ ;____________________________ ;******************************************************* ;*** write translation sizes & codes to outputbuffer *** ;******************************************************* ;Format: size.b ;If size <> 0 (or, in this representation -1 (because of size beeing a dbf ;counter)) there is the full code following, byte aligned, thus saving ;diskspace. If size = 0 (ie -1 (dbf, see above)) no code will follow, coz ;size = 0 indicates that this code won't be used. xpkHUFF_WriteTranslationSizesAndCodesToOuputBuffer: lea xpkHUFF_CRS_PtrTableToSizesAndCodes(a5),a0 move.l xpkHUFF_CRS_OutBuf(a5),a4 add.l xpkHUFF_CRS_InLen(a5),a4 ;a4: *to check for ;expansion ; add.l #XPKMARGIN,a4 ;a cruncher that ;expands data makes no ;sense move.w #255,d0 ;dbf counter over ;all table entries moveq #-1,d3 xpkHUFF_WriteTranslationSizesAndCodesToOuputBufferLoop: move.l (a0)+,d2 ;d2: *size beq.s xpkHUFF_WTSACTOB_DontWriteCodeJustMinusOne move.l d2,a2 moveq #0,d1 move.b (a2)+,d1 ;a2: *code move.b d1,(a1)+ cmp.l a4,a1 ;check for expansion bhs xpkHUFF_C_Expansion ;Uh, Oh, expansion xpkHUFF_WTSACTOB_WriteCode: lsr.b #3,d1 ;8 bits = 1 byte ;(worx! :-) xpkHUFF_WTSACTOB_WriteCodeLoop: move.b (a2)+,(a1)+ cmp.l a4,a1 ;check for expansion bhs xpkHUFF_C_Expansion ;Uh, Oh, expansion dbf d1,xpkHUFF_WTSACTOB_WriteCodeLoop dbf d0,xpkHUFF_WriteTranslationSizesAndCodesToOuputBufferLoop bra.s xpkHUFF_WTSACTOB_Done xpkHUFF_WTSACTOB_DontWriteCodeJustMinusOne: move.b d3,(a1)+ ;-1 (= dbf 0) cmp.l a4,a1 ;check for expansion bhs xpkHUFF_C_Expansion ;Uh, Oh, expansion dbf d0,xpkHUFF_WriteTranslationSizesAndCodesToOuputBufferLoop xpkHUFF_WTSACTOB_Done: ;******************************************** ;*** write crunched data to output buffer *** ;******************************************** xpkHUFF_WriteCrunchedDataToOutputBuffer: xpkHUFF_WCDTOB_Init: ;here a1 contains *OutBuf, right behind the table move.l xpkHUFF_CRS_InBuf(a5),a0 move.l xpkHUFF_CRS_InLen(a5),d0 subq.l #1,d0 ;dbf lea xpkHUFF_CRS_PtrTableToSizesAndCodes(a5),a2 moveq #7,d4 ;# of bits not yet ;used in dest ;representation (dbf) move.l xpkHUFF_CRS_OutBuf(a5),a4 add.l xpkHUFF_CRS_InLen(a5),a4 ; add.l #XPKMARGIN,a4 xpkHUFF_WCDTOB_OuterLoop: ;******************************************************************************* ;*** This part will write one byte in it's crunched representation to OutBuf *** ;******************************************************************************* moveq #0,d1 move.b (a0)+,d1 ;byte to crunch add.w d1,d1 ;make long add.w d1,d1 ;offset move.l 0(a2,d1.w),a3 ;*size of bytes' ;huffman ;representation moveq #0,d2 move.b (a3)+,d2 ;number of bits in ;byte representation ;(dbf counter) ;register usage here: ; d0: MUST NOT BE TOUCHED ; d1: (current byte to be coded)*4 ; d2: #of bits in huffamn representation for byte in d1 ; d4: #of bits not yet used in dest byte (dbf) ; a0: MUST NOT BE TOUCHED ; a1: MUST NOT BE TOUCHED ; a3: *code of byte in d1:8 moveq #0,d3 ;force read of first ;byte below xpkHUFF_WCDTOB_WriteHuffmanRepresentationOfOneByteLoop: ;register usage here: ; d3: #of not yet used bits in source representation (dbf) ; d5:8: contains (partial) huffman code ; d6: compose register dbf d3,xpkHUFF_WCDTOB_DontGetNewSourceRepresentationByte moveq #7,d3 move.b (a3)+,d5 xpkHUFF_WCDTOB_DontGetNewSourceRepresentationByte: addx.b d5,d5 addx.b d6,d6 dbf d4,xpkHUFF_WCDTOB_DontWriteDestByte moveq #7,d4 move.b d6,(a1)+ cmp.l a4,a1 ;check for expansion bhs.s xpkHUFF_C_Expansion ;Uh, Oh, expansion xpkHUFF_WCDTOB_DontWriteDestByte: dbf d2,xpkHUFF_WCDTOB_WriteHuffmanRepresentationOfOneByteLoop ;============================ dbf d0,xpkHUFF_WCDTOB_OuterLoop cmp.b #7,d4 beq.s xpkHUFF_DontWriteLastPartialByte cmp.l a4,a1 bhs.s xpkHUFF_C_Expansion addq.l #1,d4 ;former dbf counter lsl.b d4,d6 move.b d6,(a1)+ xpkHUFF_DontWriteLastPartialByte: move.l a1,d1 ;end of crunched data sub.l xpkHUFF_CRS_OutBuf(a5),d1 move.l d1,xpkHUFF_CRS_OutLen(a5) move.l d1,xpkHUFF_CRS_CrunchedLength(a5) move.l xpkHUFF_CRS_xpkSubParams(a5),a0 move.l d1,xsp_OutLen(a0) ;__________________________________________________________ xpkHUFF_Encrypt: move.l xpkHUFF_CRS_xpkSubParams(a5),a0 move.l xsp_Password(a0),d3 beq.s xpkHUFF_DontEncrypt move.l d3,a3 move.l xsp_OutBuf(a0),a1 addq.l #6,a1 ;skip indicator word ;& password checksum move.l xsp_OutLen(a0),d0 move.b (a3),d3 ;get encryptor for first byte (for the ;other bytes it's always the ;predecessor) subq.w #7,d0 ;dbf, skip indicator word, password ;checksum ;register usage: ; ;d0: Length of buffer to work on (dbf) ;d1: current byte to encrypt ;d2: byte out of passkey for encryption ;d3: last encrypted byte for more encrytion on next byte ;a1: *Buffer ;a3: *password xpkHUFF_EncryptLoop: move.b (a1),d1 ;byte that is to be coded move.b (a3)+,d2 ;byte of password bne.s xpkHUFF_EncryptLoopDontResetPasskeyPtr move.l xsp_Password(a0),a3 ;reset *password move.b (a3)+,d2 ;get first byte of passkey xpkHUFF_EncryptLoopDontResetPasskeyPtr: eor.b d2,d1 ;password byte as encryptor add.b d3,d1 ;last encrypted byte as ;encryptor move.b d1,(a1)+ ;write current encrypted byte move.b d1,d3 ;last byte is encryptor for ;next byte dbf d0,xpkHUFF_EncryptLoop xpkHUFF_DontEncrypt: ;__________________________________________________________ xpkHUFF_FreeReentry: move.l xpkHUFF_CRS_xpkSubParams(a5),-(a7) move.l #xpkHUFF_CRS_SIZEOF,d0 move.l a5,a1 move.l 4.w,a6 jsr _LVOFreeMem(a6) sub.l a5,a5 move.l (a7)+,a0 moveq #XPKERR_OK,d0 rts ;exit back to mapping code xpkHUFF_AllocReentryBufferFailed: move.l a2,a0 ;subparams moveq #XPKERR_NOMEM,d0 rts ;don't crunch xpkHUFF_C_Expansion: move.l xpkHUFF_CRS_xpkSubParams(a5),-(a7) move.l #xpkHUFF_CRS_SIZEOF,d0 move.l a5,a1 move.l 4.w,a6 jsr _LVOFreeMem(a6) sub.l a5,a5 move.l (a7)+,a0 tst.l xsp_Password(a0) beq.s XPKHUFF_C_NormalExpansion xpkHUFF_C_CantEncryptBecauseOfExpansion: ;if file would expand I would have to copy data to OutBuf and encrypt there ;without trying to crunch. But my buffer would be 6 bytes larger than the ;original one, for I add an identifier and the password checksum at the ;beginning of buffer. This means I would exceed my buffer, which is (with ;the current version of xpkmaster.library (V 2.1)) not allowed. Therefore I ;return this error, to make sure user notices that data WILL NOT BE ;ENCRYPTED. ; ;Should only occur with short files (I have an indicator word, a password ;checksum and a table size of >256 bytes which I put to OutBuf, so indicator ;word, password checksum, tablesize and crunched data must be smaller than ;InLen) or files that have already been crunched. moveq #XPKERR_SMALLBUF,d0 ;indicates that outbuf was ;too small rts XPKHUFF_C_NormalExpansion: moveq #XPKERR_EXPANSION,d0 rts ;back to mapping code ;__________________________________________________________ _XpksUnpackChunk: ;in: ; ; a0 : *XpkSubParams ; a6 : *xpkHUFF.library ;out: ; d0 : err ; in XpkSubParams : xsp_OutLen ; ;registers trashed: ; MOVEM.L D2-D7/A2-A6,-(A7) BSR.B UnPackMode0 MOVEM.L (A7)+,D2-D7/A2-A6 RTS ROOT equ 0 NODE equ 0 LEAF equ $ff ;leftmost bit set in ;word TypeAndChar ;for bpl below xpkHUFF_DecrunchTreeNodeStruct: rsreset xpkHUFF_DTNS_TypeAndChar: rs.b 0 ;for fast decrunching xpkHUFF_DTNS_Type: rs.b 1 ;ROOT|NODE|LEAF xpkHUFF_DTNS_Char: rs.b 1 ;only for leafs xpkHUFF_DTNS_LeftSubTree: rs.l 1 ;*left subtree xpkHUFF_DTNS_RightSubTree: rs.l 1 ;*righ subtree xpkHUFF_DRS_TreeNode_SIZEOF: rs.b 0 xpkHUFF_DecrunchReentryStructure: rsreset xpkHUFF_DRS_xpkSubParams: rs.l 1 xpkHUFF_DRS_xpkSubLibBase: rs.l 1 xpkHUFF_DRS_CrunchMethodIdentifier: rs.w 1 ;to ensure I can distuinguish old crunches from new ones xpkHUFF_DRS_PasswordChecksum: rs.l 1 ;space for checksum of password, if password was used, a constant (currently '$ABADCAFE') otherwise xpkHUFF_DRS_CrunchedDataTreeBuffer: rs.l 1 ;*decrunch tree in crunched data buffer xpkHUFF_DRS_CrunchedDataBuffer: rs.l 1 ;*crunched data xpkHUFF_DRS_DecrunchedDataBuffer: rs.l 1 ;*buffer to decrunch to xpkHUFF_DRS_CrunchedLength: rs.l 1 ;size of crunched data in bytes xpkHUFF_DRS_DecrunchedLength: rs.l 1 ;size of decrunched data in bytes xpkHUFF_DRS_RootNode: rs.l 1 ;*root node of decrunch tree xpkHUFF_DRS_SpaceForDecrunchTree: rs.b (256+255)*xpkHUFF_DRS_TreeNode_SIZEOF xpkHUFF_DRS_DecryptBuffer: rs.b MaxPackChunkSize xpkHUFF_DRS_SIZEOF: rs.b 0 UnPackMode0: move.l a0,a2 ;keep xpksubparams ;in mind move.l a6,a3 ;keep xpkHUFF base ;in mind move.l #xpkHUFF_DRS_SIZEOF,d0 move.l #MEMF_CLEAR|MEMF_PUBLIC,d1 move.l 4.w,a6 jsr _LVOAllocMem(a6) tst.l d0 beq xpkHUFF_AllocDecrunchReentryBufferFailed move.l d0,a5 ;reentry buffer ;now in a5 move.l a3,xpkHUFF_DRS_xpkSubLibBase(a5) ;store xpkHUFF base in ;the reentry structure move.l a2,xpkHUFF_DRS_xpkSubParams(a5) ;store subparams in ;the reentry structure ;****************************** ;*** fill reentry structure *** ;****************************** move.l xsp_InBuf(a2),a0 move.l xsp_InLen(a2),xpkHUFF_DRS_CrunchedLength(a5) subq.l #6,xpkHUFF_DRS_CrunchedLength(a5);indicator word, password checksum move.l xsp_OutBuf(a2),xpkHUFF_DRS_DecrunchedDataBuffer(a5) move.l xsp_OutLen(a2),xpkHUFF_DRS_DecrunchedLength(a5) move.w (a0)+,xpkHUFF_DRS_CrunchMethodIdentifier(a5) move.l (a0)+,xpkHUFF_DRS_PasswordChecksum(a5) cmp.w #CMI_NORMAL,xpkHUFF_DRS_CrunchMethodIdentifier(a5) bne xpkHUFF_UnknownCrunchMethod ;I cant't ;handle this tst.l xsp_Password(a2) beq.s xpkHUFF_D_InBufNotEncrypted ;__________________________________________________________ ;*************************** ;*** decryption handling *** ;*************************** xpkHUFF_D_CalcPasswordCheckSum: move.l xsp_Password(a2),a3 move.l #$ABADCAFE,d0 move.w #$C0DE,d1 xpkHUFF_D_CalcPasswordChecksumLoop1: move.b (a3)+,d1 beq.s xpkHUFF_D_CalcPasswordChecksumLoop1End add.w d1,d0 bra.s xpkHUFF_D_CalcPasswordChecksumLoop1 xpkHUFF_D_CalcPasswordChecksumLoop1End: move.l xsp_Password(a2),a3 swap d0 xpkHUFF_D_CalcPasswordChecksumLoop2: move.b (a3)+,d1 beq.s xpkHUFF_D_CalcPasswordChecksumLoop2End eor.w d1,d0 rol.w #8,d0 bra.s xpkHUFF_D_CalcPasswordChecksumLoop2 xpkHUFF_D_CalcPasswordChecksumLoop2End: cmp.l xpkHUFF_DRS_PasswordChecksum(a5),d0 beq.s xpkHUFF_D_PasswordProbablyOK bsr xpkHUFF_FreeMem moveq #XPKERR_WRONGPW,d0 ;wrong password used to decrunch rts xpkHUFF_D_PasswordProbablyOK: ;*************** ;*** decrypt *** ;*************** move.l xpkHUFF_DRS_CrunchedLength(a5),d0 subq.w #1,d0 ;dbf move.l a0,a1 ;*InBuf move.l a2,a0 ;*xpk sub params lea xpkHUFF_DRS_DecryptBuffer(a5),a2 move.l xsp_Password(a0),a3 move.b (a3),d3 ;get decryptor for first byte (for the ;other bytes it's always the ;predecessor) ;register usage: ; ;d0: Length of buffer to work on ;d1: current byte to encrypt ;d2: byte out of passkey for encryption ;d3: last encrypted byte for more encrytion on next byte ;a0: *xpk sub params ;a1: *InBuf ;a2: *DecryptBuffer ;a3: *password xpkHUFF_DecryptLoop: move.b (a1)+,d1 ;byte that is to be decoded move.b d1,d4 move.b (a3)+,d2 ;byte of password bne.s xpkHUFF_DontResetPassWordPointer move.l xsp_Password(a0),a3 ;reset *password move.b (a3)+,d2 ;get first byte of password xpkHUFF_DontResetPassWordPointer: sub.b d3,d1 ;last encrypted byte as decryptor eor.b d2,d1 ;password byte as decryptor move.b d1,(a2)+ ;write current decrypted byte move.b d4,d3 ;last encrypted byte is decryptor for ;next byte dbf d0,xpkHUFF_DecryptLoop lea xpkHUFF_DRS_DecryptBuffer(a5),a0 ; bra.s xpkHUFF_D_OKToDecrunch ;__________________________________________________________ xpkHUFF_D_InBufNotEncrypted: xpkHUFF_D_OKToDecrunch: move.l a0,xpkHUFF_DRS_CrunchedDataTreeBuffer(a5) ;**************************** ;*** create decrunch tree *** ;**************************** xpkHUFF_D_CreateDecrunchTree: move.l xpkHUFF_DRS_CrunchedDataTreeBuffer(a5),a0 lea xpkHUFF_DRS_SpaceForDecrunchTree(a5),a1 move.l a1,xpkHUFF_DRS_RootNode(a5) move.l a1,a3 move.b #ROOT,xpkHUFF_DTNS_Type(a1) lea xpkHUFF_DRS_TreeNode_SIZEOF(a1),a1 ;proceed to next node move.l #255,d0 ;256 runs moveq #-1,d1 ;for fast cmp.b below moveq #-1,d2 ;initial byte xpkHUFF_D_CreateDecrunchTreeLeafLoop: addq.b #1,d2 moveq #0,d3 move.b (a0)+,d3 ;d3:Length cmp.b d3,d1 ;length = -1 (ie 0)? ;(255 can't occur!) beq.s xpkHUFF_D_CDTL_DoneWithChar moveq #0,d5 ;force dbf below ;to read next byte move.l a3,a2 ;*root node xpkHUFF_D_CreateDecrunchTreeNodeLoop: dbf d5,xpkHUFF_D_CDTN_DontGetNextCodeByte move.b (a0)+,d4 moveq #7,d5 xpkHUFF_D_CDTN_DontGetNextCodeByte: add.b d4,d4 ;leftmost bit to carry bcs.s xpkHUFF_D_CDTN_RightSubTree ;____________________________ xpkHUFF_D_CDTN_LeftSubTree: move.l xpkHUFF_DTNS_LeftSubTree(a2),d6 beq.s xpkHUFF_D_CDTN_LeftSubTree_CreateNewNode move.l d6,a2 dbf d3,xpkHUFF_D_CreateDecrunchTreeNodeLoop bra.s xpkHUFF_D_CDTN_WriteCharDataToLeaf xpkHUFF_D_CDTN_LeftSubTree_CreateNewNode: move.l a1,xpkHUFF_DTNS_LeftSubTree(a2) move.l a1,a2 lea xpkHUFF_DRS_TreeNode_SIZEOF(a1),a1 dbf d3,xpkHUFF_D_CreateDecrunchTreeNodeLoop bra.s xpkHUFF_D_CDTN_WriteCharDataToLeaf ;____________________________ xpkHUFF_D_CDTN_RightSubTree: move.l xpkHUFF_DTNS_RightSubTree(a2),d6 beq.s xpkHUFF_D_CDTN_RightSubTree_CreateNewNode move.l d6,a2 dbf d3,xpkHUFF_D_CreateDecrunchTreeNodeLoop bra.s xpkHUFF_D_CDTN_WriteCharDataToLeaf xpkHUFF_D_CDTN_RightSubTree_CreateNewNode: move.l a1,xpkHUFF_DTNS_RightSubTree(a2) move.l a1,a2 lea xpkHUFF_DRS_TreeNode_SIZEOF(a1),a1 dbf d3,xpkHUFF_D_CreateDecrunchTreeNodeLoop ; bra.s xpkHUFF_D_CDTN_WriteCharDataToLeaf ;____________________________ xpkHUFF_D_CDTN_WriteCharDataToLeaf: move.b d2,xpkHUFF_DTNS_Char(a2) move.b #LEAF,xpkHUFF_DTNS_Type(a2) xpkHUFF_D_CDTL_DoneWithChar: dbf d0,xpkHUFF_D_CreateDecrunchTreeLeafLoop move.l a0,xpkHUFF_DRS_CrunchedDataBuffer(a5) ;********************* ;*** decrunch data *** ;********************* DecrunchData: ;__________________________________________________________ IFEQ DecrunchCode move.l xpkHUFF_DRS_DecrunchedLength(a5),d0 subq.l #1,d0 move.l xpkHUFF_DRS_CrunchedDataBuffer(a5),a0 move.l xpkHUFF_DRS_DecrunchedDataBuffer(a5),a1 moveq #0,d1 ;force read of first byte below ;register move.l xpkHUFF_DRS_RootNode(a5),a3 xpkHUFF_DD_ByteLoop: move.l a3,a2 ;root node xpkHUFF_DD_InnerLoop: dbf d1,xpkHUFF_DD_IL_DontGetNewSourceByte move.b (a0)+,d2 moveq #7,d1 xpkHUFF_DD_IL_DontGetNewSourceByte: add.b d2,d2 bcs.s xpkHUFF_DD_RightSubTree xpkHUFF_DD_LeftSubTree: move.l xpkHUFF_DTNS_LeftSubTree(a2),a2 move.w xpkHUFF_DTNS_TypeAndChar(a2),d3 bpl.s xpkHUFF_DD_InnerLoop bra.s xpkHUFF_DD_WriteChar xpkHUFF_DD_RightSubTree: move.l xpkHUFF_DTNS_RightSubTree(a2),a2 move.w xpkHUFF_DTNS_TypeAndChar(a2),d3 bpl.s xpkHUFF_DD_InnerLoop ; bra.s xpkHUFF_DD_WriteChar xpkHUFF_DD_WriteChar: move.b d3,(a1)+ dbf d0,xpkHUFF_DD_ByteLoop bsr.s xpkHUFF_FreeMem moveq #XPKERR_OK,d0 rts ;back to mapping code xpkHUFF_AllocDecrunchReentryBufferFailed: moveq #XPKERR_NOMEM,d0 rts ENDC ;of IFEQ DecrunchCode ;__________________________________________________________ IFEQ ((DecrunchCode-1)*(DecrunchCode-2)*(DecrunchCode-3)*(DecrunchCode-4)) ;************************************************* ;*** calculate crunched length (without table) *** ;************************************************* move.l xpkHUFF_DRS_CrunchedDataTreeBuffer(a5),d0 add.l xpkHUFF_DRS_CrunchedLength(a5),d0 ;equ *byte behind ;crunched data sub.l xpkHUFF_DRS_CrunchedDataBuffer(a5),d0 ;equ size of crunched ;data without tree ;information IFEQ ((DecrunchCode-1)*(DecrunchCode-2)*(DecrunchCode-4)) ;****************************************************************************** ;*** here the size of the crunched data excluding tree information is in d0 *** ;****************************************************************************** subq.l #1,d0 ;-1: last byte might ;not be used ;completely IFEQ DecrunchCode-2 lsr.l #1,d0 ;we are processing a ENDC ;word below IFEQ DecrunchCode-4 lsr.l #2,d0 ;we are processing a ENDC ;long below subq.l #1,d0 ;-1: dbf move.l xpkHUFF_DRS_CrunchedDataBuffer(a5),a0 move.l xpkHUFF_DRS_DecrunchedDataBuffer(a5),a1 move.l xpkHUFF_DRS_RootNode(a5),a3 move.l a3,a2 ;root node DD_ProcessOneCrunchedByteWordLongLoop: IFEQ DecrunchCode-1 move.b (a0)+,d2 ENDC IFEQ DecrunchCode-2 move.w (a0)+,d2 ENDC IFEQ DecrunchCode-4 move.l (a0)+,d2 ENDC ProcessOneBit MACRO IFEQ DecrunchCode-1 add.b d2,d2 ;leftmost bit to carry ENDC IFEQ DecrunchCode-2 add.w d2,d2 ;leftmost bit to carry ENDC IFEQ DecrunchCode-4 add.l d2,d2 ;leftmost bit to carry ENDC bcc.s DD_LeftSubTree\@ DD_RightSubTree\@: move.l xpkHUFF_DTNS_RightSubTree(a2),a2 move.w xpkHUFF_DTNS_TypeAndChar(a2),d3 bpl.s DD_ProceedWithNextBit\@ move.b d3,(a1)+ ;write char move.l a3,a2 ;start again at root node bra.s DD_CharWritten\@ DD_LeftSubTree\@: move.l xpkHUFF_DTNS_LeftSubTree(a2),a2 move.w xpkHUFF_DTNS_TypeAndChar(a2),d3 bpl.s DD_ProceedWithNextBit\@ move.b d3,(a1)+ ;write char move.l a3,a2 ;start again at root node ; bra.s DD_CharWritten\@ DD_CharWritten\@: DD_ProceedWithNextBit\@: ENDM IFEQ DecrunchCode-1 ProcessOneBit ;1 ProcessOneBit ;2 ProcessOneBit ;3 ProcessOneBit ;4 ProcessOneBit ;5 ProcessOneBit ;6 ProcessOneBit ;7 ProcessOneBit ;8 ENDC IFEQ DecrunchCode-2 ;I know I could use a smarter ;condition here, but I'm lazy ;and it doesn't affect ;executable speed ProcessOneBit ;1 ProcessOneBit ;2 ProcessOneBit ;3 ProcessOneBit ;4 ProcessOneBit ;5 ProcessOneBit ;6 ProcessOneBit ;7 ProcessOneBit ;8 ProcessOneBit ;9 ProcessOneBit ;10 ProcessOneBit ;11 ProcessOneBit ;12 ProcessOneBit ;13 ProcessOneBit ;14 ProcessOneBit ;15 ProcessOneBit ;16 ENDC IFEQ DecrunchCode-4 ProcessOneBit ;1 ProcessOneBit ;2 ProcessOneBit ;3 ProcessOneBit ;4 ProcessOneBit ;5 ProcessOneBit ;6 ProcessOneBit ;7 ProcessOneBit ;8 ProcessOneBit ;9 ProcessOneBit ;10 ProcessOneBit ;11 ProcessOneBit ;12 ProcessOneBit ;13 ProcessOneBit ;14 ProcessOneBit ;15 ProcessOneBit ;16 ProcessOneBit ;17 ProcessOneBit ;18 ProcessOneBit ;19 ProcessOneBit ;20 ProcessOneBit ;21 ProcessOneBit ;22 ProcessOneBit ;23 ProcessOneBit ;24 ProcessOneBit ;25 ProcessOneBit ;26 ProcessOneBit ;27 ProcessOneBit ;28 ProcessOneBit ;29 ProcessOneBit ;30 ProcessOneBit ;31 ProcessOneBit ;32 ENDC dbf d0,DD_ProcessOneCrunchedByteWordLongLoop ENDC ;of IFEQ ((DecrunchCode-1)*(DecrunchCode-2)*(DecrunchCode-4)) ;__________________________________________________________ IFEQ DecrunchCode-3 ;68030+ cache oriented decrunch code ;****************************************************************************** ;*** here the size of the crunched data excluding tree information is in d0 *** ;****************************************************************************** subq.l #1,d0 ;-1: last byte might not be used completely lsr.l #2,d0 ;we are processing a whole long below subq.l #1,d0 ;-1: dbf move.l xpkHUFF_DRS_CrunchedDataBuffer(a5),a0 move.l xpkHUFF_DRS_DecrunchedDataBuffer(a5),a1 move.l xpkHUFF_DRS_RootNode(a5),a3 move.l a3,a2 ;root node DD_ProcessOneCrunchedByteLoop: move.l (a0)+,d2 bsr.s DD_ProcessFourBitSubRoutine ; 1- 4 bsr.s DD_ProcessFourBitSubRoutine ; 5- 8 bsr.s DD_ProcessFourBitSubRoutine ; 9-12 bsr.s DD_ProcessFourBitSubRoutine ;13-16 bsr.s DD_ProcessFourBitSubRoutine ;17-20 bsr.s DD_ProcessFourBitSubRoutine ;21-24 bsr.s DD_ProcessFourBitSubRoutine ;25-28 bsr.s DD_ProcessFourBitSubRoutine ;29-32 dbf d0,DD_ProcessOneCrunchedByteLoop bra DD_AlmostDone DD_ProcessFourBitSubRoutine: ;____________________________ ProcessOneBitCodeMACRO MACRO add.l d2,d2 ;leftmost bit to carry bcc.s DD_LeftSubTree\@ DD_RightSubTree\@: move.l xpkHUFF_DTNS_RightSubTree(a2),a2 move.w xpkHUFF_DTNS_TypeAndChar(a2),d3 bpl.s DD_ProceedWithNextBit\@ move.b d3,(a1)+ ;write char move.l a3,a2 ;start again at root node IFEQ \1-0 bra.s DD_CharWritten\@ ENDC IFEQ \1-1 rts ENDC DD_LeftSubTree\@: move.l xpkHUFF_DTNS_LeftSubTree(a2),a2 move.w xpkHUFF_DTNS_TypeAndChar(a2),d3 bpl.s DD_ProceedWithNextBit\@ move.b d3,(a1)+ ;write char move.l a3,a2 ;start again at root node ; bra.s DD_CharWritten\@ DD_CharWritten\@: DD_ProceedWithNextBit\@: IFEQ \1-1 rts ENDC ENDM ;____________________________ ProcessOneBitCodeMACRO 0 ;1 ProcessOneBitCodeMACRO 0 ;2 ProcessOneBitCodeMACRO 0 ;3 ProcessOneBitCodeMACRO 1 ;4 ;last MACRO will have rts ;instead of bra DD_AlmostDone: ENDC ;of IFEQ DecrunchCode-3 ;68030+ cache oriented decrunch code ;__________________________________________________________ ProcessLastByteOrBytesOfCrunchedData: move.l a1,d1 sub.l xpkHUFF_DRS_DecrunchedDataBuffer(a5),d1 ;= number of bytes already decrunched to output buffer move.l xpkHUFF_DRS_DecrunchedLength(a5),d0 sub.l d1,d0 ;= number of bytes still to decrunch (ranges from 1..31, depending on decrunch code, too) beq.s DD_Done subq.l #1,d0 ;dbf moveq #0,d4 ;force read of next byte below ;note: the loop above was over the crunched bytes, the loop below is over ; uncrunched bytes, therefore we have a different code here ;____________________________ DD_Loop: dbf d4,DD_DontGetNewByte move.b (a0)+,d2 moveq #7,d4 DD_DontGetNewByte: add.b d2,d2 ;leftmost bit to carry bcc.s DD_LeftSubTree DD_RightSubTree: move.l xpkHUFF_DTNS_RightSubTree(a2),a2 move.w xpkHUFF_DTNS_TypeAndChar(a2),d3 bpl.s DD_Loop bra.s DD_WriteChar DD_LeftSubTree: move.l xpkHUFF_DTNS_LeftSubTree(a2),a2 move.w xpkHUFF_DTNS_TypeAndChar(a2),d3 bpl.s DD_Loop ; bra.s DD_WriteChar DD_WriteChar: move.b d3,(a1)+ ;write decrunched byte move.l a3,a2 ;start again at root node dbf d0,DD_Loop ;____________________________ DD_Done: move.l xpkHUFF_CRS_xpkSubParams(a5),a0 bsr.s xpkHUFF_FreeMem moveq #XPKERR_OK,d0 rts ;back to mapping code xpkHUFF_AllocDecrunchReentryBufferFailed: move.l a2,a0 ;subparams moveq #XPKERR_NOMEM,d0 rts ENDC ;of IFEQ ((DecrunchCode-1)*(DecrunchCode-2)*(DecrunchCode-3)*(DecrunchCode-4)) xpkHUFF_UnknownCrunchMethod: move.l xpkHUFF_DRS_xpkSubParams(a5),a0 bsr.s xpkHUFF_FreeMem moveq #XPKERR_OLDSUBLIB,d0 rts xpkHUFF_FreeMem: movem.l d0/d1/a0/a1,-(a7) move.l #xpkHUFF_DRS_SIZEOF,d0 move.l a5,a1 move.l 4.w,a6 JSR _LVOFreeMem(A6) movem.l (a7)+,d0/d1/a0/a1 rts HUFFXpkInfo DC.W 1 ; Version number of this structure DC.W VERSION ; The version of this sublibrary DC.W 1 ; The required master lib version DC.W 0 ; Longword align DC.L BriefName ; Brief name of the packer DC.L FullName ; Full name of the packer DC.L Description ; One line description of packer DC.L 'HUFF' ; ID the packer goes by (XPK format) DC.L XPKIF_PK_CHUNK|XPKIF_UP_CHUNK|XPKIF_ENCRYPTION DC.L MaxPackChunkSize; Max input chunk size for packing DC.L MinPackChunkSize; Min input chunk size for packing DC.L DefPackChunkSize; Default packing chunk size DC.L PackMsg ; Packing message, present tense DC.L UnpackMsg ; Unpacking message, present tense DC.L PackedMsg ; Packing message, past tense DC.L UnpackedMsg ; Unpacking message, past tense DC.W DefMode ; Default mode number DC.W 0 ; for future use DC.L HUFFXpkMode ; Array of compression modes DC.L 0,0,0,0,0,0 ; Future expansion - set to zero HUFFXpkMode DC.L 0 ; Chain to next descriptor for ModeDesc list DC.L 100 ; Maximum efficiency handled by this mode DC.L XPKMF_A3000SPEED DC.L xpkHUFF_CRS_SIZEOF ; Extra memory required during packing DC.L xpkHUFF_DRS_SIZEOF ; Extra memory during unpacking DC.L 88 ; Approx packing speed in K per second IFEQ DecrunchCode-0 DC.L 100 ; Approx unpacking speed in K per second ENDC IFEQ DecrunchCode-1 DC.L 138 ; Approx unpacking speed in K per second ENDC IFEQ DecrunchCode-2 DC.L 89 ; Approx unpacking speed in K per second ENDC IFEQ DecrunchCode-3 DC.L 93 ; Approx unpacking speed in K per second ENDC IFEQ DecrunchCode-4 DC.L 91 ; Approx unpacking speed in K per second ENDC DC.W 241 ; CF in 0.1% for AmigaVision executable DC.W MaxPackChunkSize/1024 ; Desired chunk size in K (!!) for this mode DC.B 'normal',0,0,0,0 ;8 character mode description PackMsg DC.B 'Crunching',0 UnpackMsg DC.B 'Decrunching',0 PackedMsg DC.B 'Crunched',0 UnpackedMsg DC.B 'Decrunched',0 BriefName DC.B 'HUFF',0 FullName DC.B 'Huffman',0 Description IFEQ DecrunchCode-0 dc.b "Dynamic huffman crunch algorithm, " dc.b "very simple decrunch algorithm",00 ENDC IFEQ DecrunchCode-1 dc.b "Dynamic huffman crunch algorithm, " dc.b "cache optimized byte decrunch algorithm",00 ENDC IFEQ DecrunchCode-2 dc.b "Dynamic huffman crunch algorithm, " dc.b "word oriented decrunch algorithm",00 ENDC IFEQ DecrunchCode-3 dc.b "Dynamic huffman crunch algorithm, " dc.b "68030+ cache oriented decrunch algorithm",00 ENDC IFEQ DecrunchCode-4 dc.b "Dynamic huffman crunch algorithm, " dc.b "long oriented decrunch algorithm",00 ENDC END