Bug Summary

File:afuzzy.c
Location:line 135, column 27
Description:The result of the '<<' expression is undefined

Annotated Source Code

1/* -*- c++ -*-
2Copyright (C) 2004-2013 Christian Wieninger
3
4This program is free software; you can redistribute it and/or
5modify it under the terms of the GNU General Public License
6as published by the Free Software Foundation; either version 2
7of the License, or (at your option) any later version.
8
9This program is distributed in the hope that it will be useful,
10but WITHOUT ANY WARRANTY; without even the implied warranty of
11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12GNU General Public License for more details.
13
14You should have received a copy of the GNU General Public License
15along with this program; if not, write to the Free Software
16Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17Or, point your browser to http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
18
19The author can be reached at cwieninger@gmx.de
20
21The project's page is at http://winni.vdr-developer.org/epgsearch
22*/
23
24#include <ctype.h>
25#include <string.h>
26#include <stdlib.h>
27
28#include "afuzzy.h"
29
30static int afuzzy_checkFLT(const char *t, AFUZZY *fuzzy);
31
32/******************************************************************************
33FUNCTION afuzzy_init()
34 Initialization of the fuzzy search routine. This applies to the consequent
35 calls of the afuzzy_CheckRTR (whole string matching) and afuzzy_CheckSUB
36 (substring match) routines. afuzzy_init() should be called for each
37 new pattern or error length. The search is case sensitive
38
39ARGUMENTS:
40 p Pattern
41 kerr Number of possible errors. Shouldn't exceed pattern length
42 UseFilter Use agrep filter algorithm that speeds up search.
43 fuzzy pointer to the structure that will be later passes to Check*
44 (the first 6 elements should be NULLs for the first call)
45
46RETURN VALUE:
47 none
48
49ALGORITHM
50 see. the article on agrep algorithms.
51 The only change is accounting transpositions as one edit operation .
52******************************************************************************/
53void afuzzy_init(const char *p, int kerr, int UseFilter, AFUZZY *fuzzy)
54{
55 int cnt, p_len, i, l, d, m;
56 char PatFilter[sizeof(Uint)*8 + 1];
57
58 fuzzy->k = kerr;
59 m = strlen(p);
60 fuzzy->FilterSet = 0;
61 memset(fuzzy->Map, 0 , sizeof(fuzzy->Map) );
62
63 if (fuzzy->S)
1
Taking false branch
→
64 free(fuzzy->S);
65 if (fuzzy->R)
2
←
Taking false branch
→
66 free(fuzzy->R);
67 if (fuzzy->R1)
3
←
Taking false branch
→
68 free(fuzzy->R1);
69 if (fuzzy->RP)
4
←
Taking false branch
→
70 free(fuzzy->RP);
71 if (fuzzy->RI)
5
←
Taking false branch
→
72 free(fuzzy->RI);
73 if (fuzzy->FilterS)
6
←
Taking false branch
→
74 free(fuzzy->FilterS);
75
76 fuzzy->FilterS = NULL__null;
77 fuzzy->S = (Uint *)calloc(m + 1, sizeof(Uint));
78 fuzzy->R = (Uint *)calloc(fuzzy->k + 1, sizeof(Uint));
79 fuzzy->R1 = (Uint *)calloc(fuzzy->k + 1, sizeof(Uint));
80 fuzzy->RI = (Uint *)calloc(fuzzy->k + 1, sizeof(Uint));
81 fuzzy->RP = (Uint *)calloc(fuzzy->k + 1, sizeof(Uint));
82
83 for (i = 0, cnt = 0; i < m; i++)
7
←
Assuming 'i' is < 'm'
→
8
←
Loop condition is true. Entering loop body
→
11
←
Assuming 'i' is >= 'm'
→
12
←
Loop condition is false. Execution continues on line 95
→
84 {
85 l = fuzzy->Map[(unsigned char)p[i]];
86 if (!l)
9
←
Assuming 'l' is not equal to 0
→
10
←
Taking false branch
→
87 {
88 l = fuzzy->Map[(unsigned char)p[i]] = ++cnt;
89 fuzzy->S[l] = 0;
90 }
91 fuzzy->S[l] |= 1 << i;
92 }
93
94
95 for (d = 0; d <= fuzzy->k; d++)
13
←
Loop condition is false. Execution continues on line 98
→
96 fuzzy->RI[d] = (1 << d) - 1;
97
98 fuzzy->mask_ok = (1 << (m - 1));
99 fuzzy->r_size = sizeof(Uint) * (fuzzy->k + 1);
100 p_len = m;
101
102 if (p_len > (int) sizeof(Uint)*8)
14
←
Taking false branch
→
103 p_len = (int) sizeof(Uint)*8;
104
105 /* If k is zero then no filter is needed! */
106 if (fuzzy->k && (p_len >= 2*(fuzzy->k + 1)) )
15
←
Taking true branch
→
107 {
108 if (UseFilter)
16
←
Assuming 'UseFilter' is not equal to 0
→
17
←
Taking true branch
→
109 {
110 fuzzy->FilterSet = 1;
111 memset(fuzzy->FilterMap, 0 , sizeof(fuzzy->FilterMap) );
112 fuzzy->FilterS = (Uint *)calloc(m + 1, sizeof(Uint));
113
114 /* Not let's fill the interleaved pattern */
115 int dd = p_len / (fuzzy->k + 1);
116 p_len = dd * (fuzzy->k + 1);
117
118 for (i = 0, cnt = 0; i < dd; i++)
18
←
Assuming 'i' is < 'dd'
→
19
←
Loop condition is true. Entering loop body
→
23
←
Assuming 'i' is >= 'dd'
→
24
←
Loop condition is false. Execution continues on line 121
→
119 for (int j = 0; j < fuzzy->k + 1; j++, cnt++)
20
←
Loop condition is true. Entering loop body
→
21
←
Loop condition is true. Entering loop body
→
22
←
Loop condition is false. Execution continues on line 118
→
120 PatFilter[cnt] = (unsigned char)p[j*dd + i];
121 PatFilter[p_len] = 0;
122
123 for (i = 0, cnt = 0; i < p_len; i++)
25
←
Assuming 'i' is < 'p_len'
→
26
←
Loop condition is true. Entering loop body
→
29
←
Assuming 'i' is >= 'p_len'
→
30
←
Loop condition is false. Execution continues on line 133
→
124 {
125 l = fuzzy->FilterMap[(unsigned char)PatFilter[i]];
126 if (!l)
27
←
Assuming 'l' is not equal to 0
→
28
←
Taking false branch
→
127 {
128 l = fuzzy->FilterMap[(unsigned char)PatFilter[i]] = ++cnt;
129 fuzzy->FilterS[l] = 0;
130 }
131 fuzzy->FilterS[l] |= 1 << i;
132 }
133 fuzzy->filter_ok = 0;
134 for (i = p_len - fuzzy->k - 1; i <= p_len - 1; i++) /* k+1 times */
31
←
Loop condition is true. Entering loop body
→
135 fuzzy->filter_ok |= 1 << i;
32
←
The result of the '<<' expression is undefined
136
137 /* k+1 first bits set to 1 */
138 fuzzy->filter_shift = (1 << (fuzzy->k + 2)) - 1;
139 }
140 }
141}
142
143/******************************************************************************
144FUNCTION afuzzy_free()
145 Cleaning up after previous afuzzy_init() call.
146
147ARGUMENTS:
148 fuzzy pointer to the afuzzy parameters structure
149
150RETURN VALUE:
151 none
152******************************************************************************/
153void afuzzy_free(AFUZZY *fuzzy)
154{
155 if (fuzzy->S)
156 {
157 free(fuzzy->S);
158 fuzzy->S = NULL__null;
159 }
160 if (fuzzy->R)
161 {
162 free(fuzzy->R);
163 fuzzy->R = NULL__null;
164 }
165 if (fuzzy->R1)
166 {
167 free(fuzzy->R1);
168 fuzzy->R1 = NULL__null;
169 }
170 if (fuzzy->RP)
171 {
172 free(fuzzy->RP);
173 fuzzy->RP = NULL__null;
174 }
175 if (fuzzy->RI)
176 {
177 free(fuzzy->RI);
178 fuzzy->RI = NULL__null;
179 }
180 if (fuzzy->FilterS)
181 {
182 free(fuzzy->FilterS);
183 fuzzy->FilterS = NULL__null;
184 }
185}
186
187
188/******************************************************************************
189FUNCTION afuzzy_CheckSUB()
190 Perform a fuzzy pattern substring matching. afuzzy_init() should be
191 called previously to initialize the pattern and error length.
192 Positive result means that some part of the string given matches the
193 pattern with no more than afuzzy->k errors (1 error = 1 letter
194 replacement or transposition)
195
196ARGUMENTS:
197 t the string to test
198 fuzzy pointer to the afuzzy parameters structure
199
200RETURN VALUE:
201 0 - no match
202 > 0 - strings match
203
204ALGORITHM
205 ????????????????
206******************************************************************************/
207int afuzzy_checkSUB(const char *t, AFUZZY *fuzzy)
208{
209 register char c;
210 register int j, d;
211
212 /* For eficciency this case should be little bit optimized */
213 if (!fuzzy->k)
214 {
215 Uint R = 0, R1;
216
217 for (j = 0; (c = t[j]) != '\0'; j++)
218 {
219 R1 = ( ((R<<1) | 1) & fuzzy->S[fuzzy->Map[(unsigned char)c]]);
220 R = R1;
221
222 if (R1 & fuzzy->mask_ok)
223 return 1;
224 } /* end for (register int j = 0 ... */
225 return 0;
226 }
227
228 if (fuzzy->FilterSet && !afuzzy_checkFLT(t, fuzzy))
229 return 0;
230
231 memcpy(fuzzy->R, fuzzy->RI, fuzzy->r_size); /* R = RI */
232
233 for (j = 0; (c = t[j]); j++)
234 {
235 for (d = 0; d <= fuzzy->k; d++)
236 {
237 fuzzy->R1[d] = (((fuzzy->R[d]<<1) | 1) &
238 fuzzy->S[fuzzy->Map[(unsigned char)c]]);
239 if (d > 0)
240 fuzzy->R1[d] |= ((fuzzy->R[d-1] | fuzzy->R1[d-1])<<1) | 1 |
241 fuzzy->R[d-1];
242 }
243 if (fuzzy->R1[fuzzy->k] & fuzzy->mask_ok)
244 return j;
245
246 memcpy(fuzzy->R, fuzzy->R1, fuzzy->r_size);
247
248 } /* end for (register int j = 0 ... */
249
250 return 0;
251}
252
253static int afuzzy_checkFLT(const char *t, AFUZZY *fuzzy)
254{
255 register Uint FilterR = 0;
256 register Uint FilterR1;
257 register int j;
258
259 for (j = 0; t[j] != '\0'; j++)
260 {
261 FilterR1 = ( ((FilterR<<(fuzzy->k+1)) | fuzzy->filter_shift) &
262 fuzzy->FilterS[fuzzy->FilterMap[(unsigned char)t[j]]]);
263 if (FilterR1 & fuzzy->filter_ok)
264 return 1;
265 FilterR = FilterR1;
266 } /* end for (register int j = 0 ... */
267
268 return 0;
269}
270
271