tools/qbytearraymatcher.cpp

Switch to Source codePreprocessed file
LineSource CodeCoverage
1 -
2 -
3 -
4 -
5static inline void bm_init_skiptable(const uchar *cc, int len, uchar *skiptable) -
6{ -
7 int l = qMin(len, 255); -
8 memset(skiptable, l, 256*sizeof(uchar)); -
9 cc += len - l; -
10 while (l--)
evaluated: l--
TRUEFALSE
yes
Evaluation Count:55651
yes
Evaluation Count:5606
5606-55651
11 skiptable[*cc++] = l;
executed: skiptable[*cc++] = l;
Execution Count:55651
55651
12}
executed: }
Execution Count:5606
5606
13 -
14static inline int bm_find(const uchar *cc, int l, int index, const uchar *puc, uint pl, -
15 const uchar *skiptable) -
16{ -
17 if (pl == 0)
evaluated: pl == 0
TRUEFALSE
yes
Evaluation Count:8
yes
Evaluation Count:15876
8-15876
18 return index > l ? -1 : index;
executed: return index > l ? -1 : index;
Execution Count:8
8
19 const uint pl_minus_one = pl - 1; -
20 -
21 register const uchar *current = cc + index + pl_minus_one; -
22 const uchar *end = cc + l; -
23 while (current < end) {
evaluated: current < end
TRUEFALSE
yes
Evaluation Count:11650951
yes
Evaluation Count:2673
2673-11650951
24 uint skip = skiptable[*current]; -
25 if (!skip) {
evaluated: !skip
TRUEFALSE
yes
Evaluation Count:13824
yes
Evaluation Count:11637127
13824-11637127
26 -
27 while (skip < pl) {
evaluated: skip < pl
TRUEFALSE
yes
Evaluation Count:72826
yes
Evaluation Count:12661
12661-72826
28 if (*(current - skip) != puc[pl_minus_one - skip])
evaluated: *(current - skip) != puc[pl_minus_one - skip]
TRUEFALSE
yes
Evaluation Count:1163
yes
Evaluation Count:71663
1163-71663
29 break;
executed: break;
Execution Count:1163
1163
30 skip++; -
31 }
executed: }
Execution Count:71663
71663
32 if (skip > pl_minus_one)
evaluated: skip > pl_minus_one
TRUEFALSE
yes
Evaluation Count:12661
yes
Evaluation Count:1163
1163-12661
33 return (current - cc) - skip + 1;
executed: return (current - cc) - skip + 1;
Execution Count:12661
12661
34 -
35 -
36 -
37 if (skiptable[*(current - skip)] == pl)
evaluated: skiptable[*(current - skip)] == pl
TRUEFALSE
yes
Evaluation Count:312
yes
Evaluation Count:851
312-851
38 skip = pl - skip;
executed: skip = pl - skip;
Execution Count:312
312
39 else -
40 skip = 1;
executed: skip = 1;
Execution Count:851
851
41 } -
42 if (current > end - skip)
evaluated: current > end - skip
TRUEFALSE
yes
Evaluation Count:542
yes
Evaluation Count:11637748
542-11637748
43 break;
executed: break;
Execution Count:542
542
44 current += skip; -
45 }
executed: }
Execution Count:11637748
11637748
46 return -1;
executed: return -1;
Execution Count:3215
3215
47} -
48QByteArrayMatcher::QByteArrayMatcher() -
49 : d(0) -
50{ -
51 p.p = 0; -
52 p.l = 0; -
53 memset(p.q_skiptable, 0, sizeof(p.q_skiptable)); -
54}
executed: }
Execution Count:2
2
55 -
56 -
57 -
58 -
59 -
60 -
61QByteArrayMatcher::QByteArrayMatcher(const char *pattern, int length) -
62 : d(0) -
63{ -
64 p.p = reinterpret_cast<const uchar *>(pattern); -
65 p.l = length; -
66 bm_init_skiptable(p.p, p.l, p.q_skiptable); -
67}
executed: }
Execution Count:1779
1779
68 -
69 -
70 -
71 -
72 -
73QByteArrayMatcher::QByteArrayMatcher(const QByteArray &pattern) -
74 : d(0), q_pattern(pattern) -
75{ -
76 p.p = reinterpret_cast<const uchar *>(pattern.constData()); -
77 p.l = pattern.size(); -
78 bm_init_skiptable(p.p, p.l, p.q_skiptable); -
79}
executed: }
Execution Count:1684
1684
80 -
81 -
82 -
83 -
84QByteArrayMatcher::QByteArrayMatcher(const QByteArrayMatcher &other) -
85 : d(0) -
86{ -
87 operator=(other); -
88}
executed: }
Execution Count:1
1
89 -
90 -
91 -
92 -
93QByteArrayMatcher::~QByteArrayMatcher() -
94{ -
95} -
96 -
97 -
98 -
99 -
100QByteArrayMatcher &QByteArrayMatcher::operator=(const QByteArrayMatcher &other) -
101{ -
102 q_pattern = other.q_pattern; -
103 memcpy(&p, &other.p, sizeof(p)); -
104 return *this;
executed: return *this;
Execution Count:5
5
105} -
106 -
107 -
108 -
109 -
110 -
111 -
112 -
113void QByteArrayMatcher::setPattern(const QByteArray &pattern) -
114{ -
115 q_pattern = pattern; -
116 p.p = reinterpret_cast<const uchar *>(pattern.constData()); -
117 p.l = pattern.size(); -
118 bm_init_skiptable(p.p, p.l, p.q_skiptable); -
119}
executed: }
Execution Count:3
3
120int QByteArrayMatcher::indexIn(const QByteArray &ba, int from) const -
121{ -
122 if (from < 0)
partially evaluated: from < 0
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:13741
0-13741
123 from = 0;
never executed: from = 0;
0
124 return bm_find(reinterpret_cast<const uchar *>(ba.constData()), ba.size(), from, 13741
125 p.p, p.l, p.q_skiptable);
executed: return bm_find(reinterpret_cast<const uchar *>(ba.constData()), ba.size(), from, p.p, p.l, p.q_skiptable);
Execution Count:13741
13741
126} -
127int QByteArrayMatcher::indexIn(const char *str, int len, int from) const -
128{ -
129 if (from < 0)
partially evaluated: from < 0
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:3
0-3
130 from = 0;
never executed: from = 0;
0
131 return bm_find(reinterpret_cast<const uchar *>(str), len, from, 3
132 p.p, p.l, p.q_skiptable);
executed: return bm_find(reinterpret_cast<const uchar *>(str), len, from, p.p, p.l, p.q_skiptable);
Execution Count:3
3
133} -
134static int findChar(const char *str, int len, char ch, int from) -
135{ -
136 const uchar *s = (const uchar *)str; -
137 uchar c = (uchar)ch; -
138 if (from < 0)
never evaluated: from < 0
0
139 from = qMax(from + len, 0);
never executed: from = qMax(from + len, 0);
0
140 if (from < len) {
never evaluated: from < len
0
141 const uchar *n = s + from - 1; -
142 const uchar *e = s + len; -
143 while (++n != e)
never evaluated: ++n != e
0
144 if (*n == c)
never evaluated: *n == c
0
145 return n - s;
never executed: return n - s;
0
146 }
never executed: }
0
147 return -1;
never executed: return -1;
0
148} -
149 -
150 -
151 -
152 -
153static int qFindByteArrayBoyerMoore( -
154 const char *haystack, int haystackLen, int haystackOffset, -
155 const char *needle, int needleLen) -
156{ -
157 uchar skiptable[256]; -
158 bm_init_skiptable((const uchar *)needle, needleLen, skiptable); -
159 if (haystackOffset < 0)
partially evaluated: haystackOffset < 0
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:2140
0-2140
160 haystackOffset = 0;
never executed: haystackOffset = 0;
0
161 return bm_find((const uchar *)haystack, haystackLen, haystackOffset, 2140
162 (const uchar *)needle, needleLen, skiptable);
executed: return bm_find((const uchar *)haystack, haystackLen, haystackOffset, (const uchar *)needle, needleLen, skiptable);
Execution Count:2140
2140
163} -
164int qFindByteArray( -
165 const char *haystack0, int haystackLen, int from, -
166 const char *needle, int needleLen) -
167{ -
168 const int l = haystackLen; -
169 const int sl = needleLen; -
170 if (from < 0)
partially evaluated: from < 0
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:674620
0-674620
171 from += l;
never executed: from += l;
0
172 if (uint(sl + from) > (uint)l)
partially evaluated: uint(sl + from) > (uint)l
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:674620
0-674620
173 return -1;
never executed: return -1;
0
174 if (!sl)
partially evaluated: !sl
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:674620
0-674620
175 return from;
never executed: return from;
0
176 if (!l)
partially evaluated: !l
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:674620
0-674620
177 return -1;
never executed: return -1;
0
178 -
179 if (sl == 1)
partially evaluated: sl == 1
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:674620
0-674620
180 return findChar(haystack0, haystackLen, needle[0], from);
never executed: return findChar(haystack0, haystackLen, needle[0], from);
0
181 -
182 -
183 -
184 -
185 -
186 -
187 if (l > 500 && sl > 5)
evaluated: l > 500
TRUEFALSE
yes
Evaluation Count:2144
yes
Evaluation Count:672476
evaluated: sl > 5
TRUEFALSE
yes
Evaluation Count:2140
yes
Evaluation Count:4
4-672476
188 return qFindByteArrayBoyerMoore(haystack0, haystackLen, from, 2140
189 needle, needleLen);
executed: return qFindByteArrayBoyerMoore(haystack0, haystackLen, from, needle, needleLen);
Execution Count:2140
2140
190 -
191 -
192 -
193 -
194 -
195 -
196 const char *haystack = haystack0 + from; -
197 const char *end = haystack0 + (l - sl); -
198 const uint sl_minus_1 = sl - 1; -
199 uint hashNeedle = 0, hashHaystack = 0; -
200 int idx; -
201 for (idx = 0; idx < sl; ++idx) {
evaluated: idx < sl
TRUEFALSE
yes
Evaluation Count:4574888
yes
Evaluation Count:672480
672480-4574888
202 hashNeedle = ((hashNeedle<<1) + needle[idx]); -
203 hashHaystack = ((hashHaystack<<1) + haystack[idx]); -
204 }
executed: }
Execution Count:4574888
4574888
205 hashHaystack -= *(haystack + sl_minus_1); -
206 -
207 while (haystack <= end) {
evaluated: haystack <= end
TRUEFALSE
yes
Evaluation Count:17366215
yes
Evaluation Count:519157
519157-17366215
208 hashHaystack += *(haystack + sl_minus_1); -
209 if (hashHaystack == hashNeedle && *needle == *haystack
evaluated: hashHaystack == hashNeedle
TRUEFALSE
yes
Evaluation Count:153325
yes
Evaluation Count:17212890
partially evaluated: *needle == *haystack
TRUEFALSE
yes
Evaluation Count:153325
no
Evaluation Count:0
0-17212890
210 && memcmp(needle, haystack, sl) == 0)
evaluated: memcmp(needle, haystack, sl) == 0
TRUEFALSE
yes
Evaluation Count:153323
yes
Evaluation Count:2
2-153323
211 return haystack - haystack0;
executed: return haystack - haystack0;
Execution Count:153323
153323
212 -
213 if (sl_minus_1 < sizeof(uint) * 8) hashHaystack -= (*haystack) << sl_minus_1; hashHaystack <<= 1;
executed: hashHaystack -= (*haystack) << sl_minus_1;
Execution Count:17212476
evaluated: sl_minus_1 < sizeof(uint) * 8
TRUEFALSE
yes
Evaluation Count:17212476
yes
Evaluation Count:416
416-17212476
214 ++haystack; -
215 }
executed: }
Execution Count:17212892
17212892
216 return -1;
executed: return -1;
Execution Count:519157
519157
217} -
218 -
219 -
220 -
Switch to Source codePreprocessed file
Generated by Squish Coco Non-Commercial