1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
//Copyright Paul Reiche, Fred Ford. 1992-2002
/*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program 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. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
#include <string.h>
#include "lzh.h"
static void
reconst (void)
{
COUNT i, j;
/* halven cumulative freq for leaf nodes */
j = 0;
for (i = 0; i < T; i++)
{
if (_lpCurCodeDesc->son[i] >= T)
{
_lpCurCodeDesc->freq[j] = (_lpCurCodeDesc->freq[i] + 1) >> 1;
_lpCurCodeDesc->son[j] = _lpCurCodeDesc->son[i];
j++;
}
}
/* make a tree : first, connect children nodes */
for (i = 0, j = N_CHAR; j < T; i += 2, j++)
{
SWORD k;
UWORD f, l;
k = i + 1;
f = _lpCurCodeDesc->freq[j] = _lpCurCodeDesc->freq[i] + _lpCurCodeDesc->freq[k];
for (k = j - 1; f < _lpCurCodeDesc->freq[k]; k--)
;
k++;
l = (j - k);
memmove (_lpCurCodeDesc->freq + k + 1, _lpCurCodeDesc->freq + k,
sizeof(_lpCurCodeDesc->freq[0]) * l);
_lpCurCodeDesc->freq[k] = f;
memmove (_lpCurCodeDesc->son + k + 1, _lpCurCodeDesc->son + k,
sizeof(_lpCurCodeDesc->son[0]) * l);
_lpCurCodeDesc->son[k] = i;
}
/* connect parent nodes */
for (i = 0; i < T; i++)
{
if ((j = _lpCurCodeDesc->son[i]) >= T)
_lpCurCodeDesc->prnt[j] = i;
else
_lpCurCodeDesc->prnt[j] = _lpCurCodeDesc->prnt[j + 1] = i;
}
}
/* update freq tree */
void
_update (COUNT c)
{
PLZHCODE_DESC lpCD;
if ((lpCD = _lpCurCodeDesc)->freq[R] == MAX_FREQ)
reconst ();
c = lpCD->prnt[c];
do
{
COUNT i, l;
i = ++lpCD->freq[c];
/* swap nodes to keep the tree freq-ordered */
if (i > lpCD->freq[l = c + 1])
{
COUNT j;
while (i > lpCD->freq[++l])
;
l--;
lpCD->freq[c] = lpCD->freq[l];
lpCD->freq[l] = i;
i = lpCD->son[c];
j = lpCD->son[l];
lpCD->son[l] = i;
lpCD->son[c] = j;
lpCD->prnt[i] = l;
if (i < T)
lpCD->prnt[i + 1] = l;
lpCD->prnt[j] = c;
if (j < T)
lpCD->prnt[j + 1] = c;
c = l;
}
} while ((c = lpCD->prnt[c]) != 0); /* do it until reaching the root */
}
|
