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