Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
969 | dimkam | 1 | #include <stdio.h> |
2 | #include <stdlib.h> |
||
3 | |||
4 | #include "mhmt-types.h" |
||
5 | #include "mhmt-optimal.h" |
||
6 | |||
7 | |||
8 | // allocate place for optimal chain building amd initialize it |
||
9 | struct optchain * make_optch(ULONG actual_len) |
||
10 | { |
||
11 | struct optchain * optch; |
||
12 | |||
13 | ULONG i; |
||
14 | |||
15 | // we allocate length+1 because all codes at the end of input stream will point |
||
16 | // to the length+1 place. Also we'll start reversing from length+1 position in optch array |
||
17 | optch = (struct optchain *)malloc( (actual_len+1)*sizeof(struct optchain) ); |
||
18 | |||
19 | if( optch ) |
||
20 | { |
||
21 | optch[0].code.length = 1; // 1st byte is always copied 'as-is', however, this is just filler, |
||
22 | optch[0].code.disp = 0; // not accounted elsewhere |
||
23 | |||
24 | // init prices to absolute maximum for optimal chain build-up |
||
25 | optch[0].price = 0; |
||
26 | optch[1].price = 8; |
||
27 | for(i=2;i<(actual_len+1);i++) |
||
28 | optch[i].price = 0xFFFFFFFF; |
||
29 | } |
||
30 | |||
31 | return optch; |
||
32 | } |
||
33 | |||
34 | struct optch_hst ** make_optch_hst(ULONG actual_len) |
||
35 | { |
||
36 | struct optch_hst ** optch_bunch; |
||
37 | |||
38 | ULONG i,j; |
||
39 | |||
40 | |||
41 | optch_bunch = (struct optch_hst **)calloc( 8, sizeof(struct optch_hst *) ); |
||
42 | |||
43 | if( optch_bunch ) |
||
44 | { |
||
45 | for(i=0;i<8;i++) |
||
46 | { |
||
47 | optch_bunch[i] = (struct optch_hst *)malloc( (actual_len+1)*sizeof(struct optch_hst) ); |
||
48 | if( !optch_bunch[i] ) |
||
49 | { // error recovery (free allocated mem) |
||
50 | free_optch_hst(optch_bunch); |
||
51 | return NULL; |
||
52 | } |
||
53 | } |
||
54 | |||
55 | for(i=0;i<8;i++) |
||
56 | { |
||
57 | for(j=0;j<(actual_len+1);j++) |
||
58 | { |
||
59 | optch_bunch[i][j].code.length = 0; |
||
60 | optch_bunch[i][j].code.disp = 0; |
||
61 | optch_bunch[i][j].path = (-1); |
||
62 | optch_bunch[i][j].price = 0xFFFFFFFF; |
||
63 | } |
||
64 | } |
||
65 | |||
66 | optch_bunch[0][0].code.length = 1; |
||
67 | optch_bunch[0][0].code.disp = 0; |
||
68 | |||
69 | optch_bunch[0][0].price = 0; |
||
70 | optch_bunch[0][1].price = 8; |
||
71 | |||
72 | optch_bunch[0][0].path = 0; |
||
73 | optch_bunch[0][1].path = 0; |
||
74 | } |
||
75 | |||
76 | return optch_bunch; |
||
77 | } |
||
78 | |||
79 | |||
80 | |||
81 | |||
82 | // free optchain array |
||
83 | void free_optch(struct optchain * optch) |
||
84 | { |
||
85 | if( optch ) |
||
86 | free( optch ); |
||
87 | } |
||
88 | |||
89 | void free_optch_hst(struct optch_hst ** optch) |
||
90 | { |
||
91 | ULONG i; |
||
92 | |||
93 | if( optch ) |
||
94 | { |
||
95 | for(i=0;i<8;i++) |
||
96 | { |
||
97 | if( optch[i] ) |
||
98 | free( optch[i] ); |
||
99 | } |
||
100 | free( optch ); |
||
101 | } |
||
102 | } |
||
103 | |||
104 | |||
105 | |||
106 | |||
107 | |||
108 | // update prices at the position given all lzcodes. |
||
109 | // it also needs pointer to the function that calculates bit length of given LZ code |
||
110 | void update_optch(ULONG position, struct lzcode * codes, ULONG (*get_lz_price)(OFFSET position, struct lzcode * lzcode), struct optchain * optch) |
||
111 | { |
||
112 | ULONG codepos; |
||
113 | ULONG bitlen; |
||
114 | ULONG newpos; |
||
115 | LONG len; |
||
116 | |||
117 | for( codepos = 0; len=codes[codepos].length; codepos++ ) // loop through all existing lz codes |
||
118 | { |
||
119 | bitlen = (*get_lz_price)(position, &codes[codepos]); // get bit length of given lz code |
||
120 | if( !bitlen ) |
||
121 | { |
||
122 | printf("mhmt-optimal.c: update_optch() found zero bitlength of lz code. Fatal error.\n"); |
||
123 | exit(1); |
||
124 | } |
||
125 | else |
||
126 | { |
||
127 | if( len<0 ) len=(-len); // deal with negative lengths (special markers) |
||
128 | |||
129 | newpos = position + len; // look where current lz code points to and take from there old price reaching that location |
||
130 | |||
131 | if( optch[newpos].price > bitlen + optch[position].price ) // if oldprice is worse than with current lz code |
||
132 | { |
||
133 | optch[newpos].price = bitlen + optch[position].price; |
||
134 | optch[newpos].code = codes[codepos]; |
||
135 | } |
||
136 | } |
||
137 | } |
||
138 | } |
||
139 | |||
140 | |||
141 | |||
142 | |||
143 | |||
144 | |||
145 | // reverses optimal chain making it ready for scanning (fetching optimal chain) |
||
146 | // |
||
147 | void reverse_optch(struct optchain * optch, ULONG actual_len) |
||
148 | { |
||
149 | struct lzcode curr, temp; |
||
150 | ULONG position; |
||
151 | LONG len; |
||
152 | |||
153 | position = actual_len; |
||
154 | |||
155 | temp = optch[position].code; |
||
156 | |||
157 | while(position>1) |
||
158 | { |
||
159 | len = temp.length; |
||
160 | if( len<0 ) len=(-len); |
||
161 | |||
162 | position -= len; |
||
163 | |||
164 | curr = temp; |
||
165 | |||
166 | temp = optch[position].code; |
||
167 | optch[position].code = curr; |
||
168 | } |
||
169 | } |
||
170 | |||
171 |