Subversion Repositories pentevo

Rev

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