2 * xDMS v1.3 - Portable DMS archive unpacker - Public Domain
3 * Written by Andre Rodrigues de la Rocha <adlroc@usa.net>
5 * Lempel-Ziv-DynamicHuffman decompression functions used in Deep
7 * Most routines ripped from LZHUF written by Haruyasu Yoshizaki
13 static UWORD
DecodeChar (struct xdms_data
*xdms
);
14 static UWORD
DecodePosition (struct xdms_data
*xdms
);
15 static void update (struct xdms_data
*xdms
, UWORD c
);
16 static void reconst (struct xdms_data
*xdms
);
18 #define DBITMASK 0x3fff /* uses 16Kb dictionary */
20 #define F 60 /* lookahead buffer size */
22 #define N_CHAR (256 - THRESHOLD + F) /* kinds of characters (character code = 0..N_CHAR-1) */
23 #define T (N_CHAR * 2 - 1) /* size of table */
24 #define R (T - 1) /* position of root */
25 #define MAX_FREQ 0x8000 /* updates tree when the */
28 UWORD freq
[T
+ 1]; /* frequency table */
30 UWORD prnt
[T
+ N_CHAR
]; /* pointers to parent nodes, except for the */
31 /* elements [T..T + N_CHAR - 1] which are used to get */
32 /* the positions of leaves corresponding to the codes. */
34 UWORD son
[T
]; /* pointers to child nodes (son[], son[] + 1) */
37 static void Init_DEEP_Tabs (struct xdms_data
*xdms
) {
38 UWORD
* const freq
= xdms
->u_deep
.freq
;
39 UWORD
* const prnt
= xdms
->u_deep
.prnt
;
40 UWORD
* const son
= xdms
->u_deep
.son
;
43 for (i
= 0; i
< N_CHAR
; i
++) {
45 son
[i
] = (UWORD
)(i
+ T
);
50 freq
[j
] = (UWORD
)(freq
[i
] + freq
[i
+ 1]);
52 prnt
[i
] = prnt
[i
+ 1] = j
;
58 xdms
->init_deep_tabs
= 0;
61 UWORD
Unpack_DEEP (struct xdms_data
*xdms
, UBYTE
*in
, UBYTE
*out
, UWORD origsize
) {
62 UWORD deep_text_loc
= xdms
->deep_text_loc
;
63 UBYTE
*text
= xdms
->text
;
69 if (xdms
->init_deep_tabs
) Init_DEEP_Tabs(xdms
);
71 outend
= out
+origsize
;
72 while (out
< outend
) {
75 *out
++ = text
[deep_text_loc
++ & DBITMASK
] = (UBYTE
)c
;
77 j
= (UWORD
)(c
- 255 + THRESHOLD
);
78 i
= (UWORD
)(deep_text_loc
- DecodePosition(xdms
) - 1);
79 while (j
--) *out
++ = text
[deep_text_loc
++ & DBITMASK
] = text
[i
++ & DBITMASK
];
83 xdms
->deep_text_loc
= (UWORD
)((deep_text_loc
+60) & DBITMASK
);
88 static UWORD
DecodeChar (struct xdms_data
*xdms
) {
89 UWORD
* const son
= xdms
->u_deep
.son
;
94 /* travel from root to leaf, */
95 /* choosing the smaller child node (son[]) if the read bit is 0, */
96 /* the bigger (son[]+1} if 1 */
98 c
= son
[c
+ GETBITS(1)];
107 static UWORD
DecodePosition (struct xdms_data
*xdms
) {
110 i
= GETBITS(8); DROPBITS(8);
111 c
= (UWORD
)(d_code
[i
] << 8);
113 i
= (UWORD
)(((i
<< j
) | GETBITS(j
)) & 0xff); DROPBITS(j
);
115 return (UWORD
)(c
| i
);
118 /* reconstruction of tree */
120 static void reconst (struct xdms_data
*xdms
) {
121 UWORD
* const freq
= xdms
->u_deep
.freq
;
122 UWORD
* const prnt
= xdms
->u_deep
.prnt
;
123 UWORD
* const son
= xdms
->u_deep
.son
;
126 /* collect leaf nodes in the first half of the table */
127 /* and replace the freq by (freq + 1) / 2. */
129 for (i
= 0; i
< T
; i
++) {
131 freq
[j
] = (UWORD
)((freq
[i
] + 1) / 2);
136 /* begin constructing tree by connecting sons */
137 for (i
= 0, j
= N_CHAR
; j
< T
; i
+= 2, j
++) {
139 f
= freq
[j
] = (UWORD
)(freq
[i
] + freq
[k
]);
140 for (k
= (UWORD
)(j
- 1); f
< freq
[k
]; k
--);
142 l
= (UWORD
)((j
- k
) * 2);
143 memmove(&freq
[k
+ 1], &freq
[k
], (size_t)l
);
145 memmove(&son
[k
+ 1], &son
[k
], (size_t)l
);
149 for (i
= 0; i
< T
; i
++) {
150 if ((k
= son
[i
]) >= T
) {
153 prnt
[k
] = prnt
[k
+ 1] = i
;
158 /* increment frequency of given code by one, and update tree */
160 static void update (struct xdms_data
*xdms
, UWORD c
){
161 UWORD
* const freq
= xdms
->u_deep
.freq
;
162 UWORD
* const prnt
= xdms
->u_deep
.prnt
;
163 UWORD
* const son
= xdms
->u_deep
.son
;
166 if (freq
[R
] == MAX_FREQ
) {
173 /* if the order is disturbed, exchange nodes */
174 if (k
> freq
[l
= (UWORD
)(c
+ 1)]) {
175 while (k
> freq
[++l
]);
182 if (i
< T
) prnt
[i
+ 1] = l
;
188 if (j
< T
) prnt
[j
+ 1] = c
;
193 } while ((c
= prnt
[c
]) != 0); /* repeat up to root */