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:53468
yes
Evaluation Count:5443
5443-53468
11 skiptable[*cc++] = l;
executed: skiptable[*cc++] = l;
Execution Count:53468
53468
12}
executed: }
Execution Count:5443
5443
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:15194
8-15194
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:11639432
yes
Evaluation Count:2634
2634-11639432
24 uint skip = skiptable[*current]; -
25 if (!skip) {
evaluated: !skip
TRUEFALSE
yes
Evaluation Count:13151
yes
Evaluation Count:11626281
13151-11626281
26 -
27 while (skip < pl) {
evaluated: skip < pl
TRUEFALSE
yes
Evaluation Count:70127
yes
Evaluation Count:12025
12025-70127
28 if (*(current - skip) != puc[pl_minus_one - skip])
evaluated: *(current - skip) != puc[pl_minus_one - skip]
TRUEFALSE
yes
Evaluation Count:1126
yes
Evaluation Count:69001
1126-69001
29 break;
executed: break;
Execution Count:1126
1126
30 skip++; -
31 }
executed: }
Execution Count:69001
69001
32 if (skip > pl_minus_one)
evaluated: skip > pl_minus_one
TRUEFALSE
yes
Evaluation Count:12025
yes
Evaluation Count:1126
1126-12025
33 return (current - cc) - skip + 1;
executed: return (current - cc) - skip + 1;
Execution Count:12025
12025
34 -
35 -
36 -
37 if (skiptable[*(current - skip)] == pl)
evaluated: skiptable[*(current - skip)] == pl
TRUEFALSE
yes
Evaluation Count:276
yes
Evaluation Count:850
276-850
38 skip = pl - skip;
executed: skip = pl - skip;
Execution Count:276
276
39 else -
40 skip = 1;
executed: skip = 1;
Execution Count:850
850
41 } -
42 if (current > end - skip)
evaluated: current > end - skip
TRUEFALSE
yes
Evaluation Count:535
yes
Evaluation Count:11626872
535-11626872
43 break;
executed: break;
Execution Count:535
535
44 current += skip; -
45 }
executed: }
Execution Count:11626872
11626872
46 return -1;
executed: return -1;
Execution Count:3169
3169
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:1606
1606
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:13144
0-13144
123 from = 0;
never executed: from = 0;
0
124 return bm_find(reinterpret_cast<const uchar *>(ba.constData()), ba.size(), from, 13144
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:13144
13144
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:2055
0-2055
160 haystackOffset = 0;
never executed: haystackOffset = 0;
0
161 return bm_find((const uchar *)haystack, haystackLen, haystackOffset, 2055
162 (const uchar *)needle, needleLen, skiptable);
executed: return bm_find((const uchar *)haystack, haystackLen, haystackOffset, (const uchar *)needle, needleLen, skiptable);
Execution Count:2055
2055
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:674294
0-674294
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:674294
0-674294
173 return -1;
never executed: return -1;
0
174 if (!sl)
partially evaluated: !sl
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:674294
0-674294
175 return from;
never executed: return from;
0
176 if (!l)
partially evaluated: !l
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:674294
0-674294
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:674294
0-674294
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:2059
yes
Evaluation Count:672235
evaluated: sl > 5
TRUEFALSE
yes
Evaluation Count:2055
yes
Evaluation Count:4
4-672235
188 return qFindByteArrayBoyerMoore(haystack0, haystackLen, from, 2055
189 needle, needleLen);
executed: return qFindByteArrayBoyerMoore(haystack0, haystackLen, from, needle, needleLen);
Execution Count:2055
2055
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:4571834
yes
Evaluation Count:672239
672239-4571834
202 hashNeedle = ((hashNeedle<<1) + needle[idx]); -
203 hashHaystack = ((hashHaystack<<1) + haystack[idx]); -
204 }
executed: }
Execution Count:4571834
4571834
205 hashHaystack -= *(haystack + sl_minus_1); -
206 -
207 while (haystack <= end) {
evaluated: haystack <= end
TRUEFALSE
yes
Evaluation Count:17361454
yes
Evaluation Count:518927
518927-17361454
208 hashHaystack += *(haystack + sl_minus_1); -
209 if (hashHaystack == hashNeedle && *needle == *haystack
evaluated: hashHaystack == hashNeedle
TRUEFALSE
yes
Evaluation Count:153314
yes
Evaluation Count:17208140
partially evaluated: *needle == *haystack
TRUEFALSE
yes
Evaluation Count:153314
no
Evaluation Count:0
0-17208140
210 && memcmp(needle, haystack, sl) == 0)
evaluated: memcmp(needle, haystack, sl) == 0
TRUEFALSE
yes
Evaluation Count:153312
yes
Evaluation Count:2
2-153312
211 return haystack - haystack0;
executed: return haystack - haystack0;
Execution Count:153312
153312
212 -
213 if (sl_minus_1 < sizeof(uint) * 8) hashHaystack -= (*haystack) << sl_minus_1; hashHaystack <<= 1;
executed: hashHaystack -= (*haystack) << sl_minus_1;
Execution Count:17207726
evaluated: sl_minus_1 < sizeof(uint) * 8
TRUEFALSE
yes
Evaluation Count:17207726
yes
Evaluation Count:416
416-17207726
214 ++haystack; -
215 }
executed: }
Execution Count:17208142
17208142
216 return -1;
executed: return -1;
Execution Count:518927
518927
217} -
218 -
219 -
220 -
Switch to Source codePreprocessed file
Generated by Squish Coco Non-Commercial