tools/qbytearraymatcher.cpp

Source code Switch to Preprocessed file

Line Source Code Coverage

1 /**************************************************************************** -

2 ** -

4 ** Contact: http://www.qt-project.org/legal -

5 ** -

6 ** This file is part of the QtCore module of the Qt Toolkit. -

7 ** -

8 ** $QT_BEGIN_LICENSE:LGPL$ -

9 ** Commercial License Usage -

10 ** Licensees holding valid commercial Qt licenses may use this file in -

11 ** accordance with the commercial license agreement provided with the -

12 ** Software or, alternatively, in accordance with the terms contained in -

13 ** a written agreement between you and Digia. For licensing terms and -

14 ** conditions see http://qt.digia.com/licensing. For further information -

15 ** use the contact form at http://qt.digia.com/contact-us. -

16 ** -

17 ** GNU Lesser General Public License Usage -

18 ** Alternatively, this file may be used under the terms of the GNU Lesser -

19 ** General Public License version 2.1 as published by the Free Software -

20 ** Foundation and appearing in the file LICENSE.LGPL included in the -

21 ** packaging of this file. Please review the following information to -

22 ** ensure the GNU Lesser General Public License version 2.1 requirements -

23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. -

24 ** -

25 ** In addition, as a special exception, Digia gives you certain additional -

26 ** rights. These rights are described in the Digia Qt LGPL Exception -

27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. -

28 ** -

29 ** GNU General Public License Usage -

30 ** Alternatively, this file may be used under the terms of the GNU -

31 ** General Public License version 3.0 as published by the Free Software -

32 ** Foundation and appearing in the file LICENSE.GPL included in the -

33 ** packaging of this file. Please review the following information to -

34 ** ensure the GNU General Public License version 3.0 requirements will be -

35 ** met: http://www.gnu.org/copyleft/gpl.html. -

36 ** -

37 ** -

38 ** $QT_END_LICENSE$ -

39 ** -

40 ****************************************************************************/ -

41 -

42 #include "qbytearraymatcher.h" -

43 -

44 #include <limits.h> -

45 -

46 QT_BEGIN_NAMESPACE -

47 -

48 static inline void bm_init_skiptable(const uchar *cc, int len, uchar *skiptable) -

49 { -

int l = qMin(len, 255);

executed (the execution status of this line is deduced): int l = qMin(len, 255);

memset(skiptable, l, 256*sizeof(uchar));

executed (the execution status of this line is deduced): memset(skiptable, l, 256*sizeof(uchar));

cc += len - l;

executed (the execution status of this line is deduced): cc += len - l;

while (l--)

evaluated: l--

TRUE	FALSE
yes Evaluation Count:55651	yes Evaluation Count:5606

5606-55651

skiptable[*cc++] = l;

executed: skiptable[*cc++] = l;

Execution Count:55651

55651

}

executed: }

Execution Count:5606

5606

56 -

57 static inline int bm_find(const uchar *cc, int l, int index, const uchar *puc, uint pl, -

58 const uchar *skiptable) -

59 { -

if (pl == 0)

evaluated: pl == 0

TRUE	FALSE
yes Evaluation Count:8	yes Evaluation Count:15876

8-15876

return index > l ? -1 : index;

executed: return index > l ? -1 : index;

Execution Count:8

const uint pl_minus_one = pl - 1;

executed (the execution status of this line is deduced): const uint pl_minus_one = pl - 1;

63 -

executed (the execution status of this line is deduced): register const uchar *current = cc + index + pl_minus_one;

const uchar *end = cc + l;

executed (the execution status of this line is deduced): const uchar *end = cc + l;

while (current < end) {

evaluated: current < end

TRUE	FALSE
yes Evaluation Count:11650951	yes Evaluation Count:2673

2673-11650951

uint skip = skiptable[*current];

executed (the execution status of this line is deduced): uint skip = skiptable[*current];

if (!skip) {

evaluated: !skip

TRUE	FALSE
yes Evaluation Count:13824	yes Evaluation Count:11637127

13824-11637127

69 // possible match -

while (skip < pl) {

evaluated: skip < pl

TRUE	FALSE
yes Evaluation Count:72826	yes Evaluation Count:12661

12661-72826

if (*(current - skip) != puc[pl_minus_one - skip])

evaluated: *(current - skip) != puc[pl_minus_one - skip]

TRUE	FALSE
yes Evaluation Count:1163	yes Evaluation Count:71663

1163-71663

break;

executed: break;

Execution Count:1163

1163

skip++;

executed (the execution status of this line is deduced): skip++;

}

executed: }

Execution Count:71663

71663

if (skip > pl_minus_one) // we have a match

evaluated: skip > pl_minus_one

TRUE	FALSE
yes Evaluation Count:12661	yes Evaluation Count:1163

1163-12661

return (current - cc) - skip + 1;

executed: return (current - cc) - skip + 1;

Execution Count:12661

12661

77 -

78 // in case we don't have a match we are a bit inefficient as we only skip by one -

79 // when we have the non matching char in the string. -

if (skiptable[*(current - skip)] == pl)

evaluated: skiptable[*(current - skip)] == pl

TRUE	FALSE
yes Evaluation Count:312	yes Evaluation Count:851

312-851

skip = pl - skip;

executed: skip = pl - skip;

Execution Count:312

312

82 else -

skip = 1;

executed: skip = 1;

Execution Count:851

851

84 } -

if (current > end - skip)

evaluated: current > end - skip

TRUE	FALSE
yes Evaluation Count:542	yes Evaluation Count:11637748

542-11637748

break;

executed: break;

Execution Count:542

542

current += skip;

executed (the execution status of this line is deduced): current += skip;

}

executed: }

Execution Count:11637748

11637748

return -1; // not found

executed: return -1;

Execution Count:3215

3215

90 } -

91 -

92 /*! \class QByteArrayMatcher -

93 \inmodule QtCore -

94 \brief The QByteArrayMatcher class holds a sequence of bytes that -

95 can be quickly matched in a byte array. -

96 -

97 \ingroup tools -

98 \ingroup string-processing -

99 -

100 This class is useful when you have a sequence of bytes that you -

101 want to repeatedly match against some byte arrays (perhaps in a -

102 loop), or when you want to search for the same sequence of bytes -

103 multiple times in the same byte array. Using a matcher object and -

104 indexIn() is faster than matching a plain QByteArray with -

105 QByteArray::indexOf() if repeated matching takes place. This -

106 class offers no benefit if you are doing one-off byte array -

107 matches. -

108 -

109 Create the QByteArrayMatcher with the QByteArray you want to -

110 search for. Then call indexIn() on the QByteArray that you want to -

111 search. -

112 -

113 \sa QByteArray, QStringMatcher -

114 */ -

115 -

116 /*! -

117 Constructs an empty byte array matcher that won't match anything. -

118 Call setPattern() to give it a pattern to match. -

119 */ -

120 QByteArrayMatcher::QByteArrayMatcher() -

121 : d(0) -

122 { -

123

p.p = 0;

executed (the execution status of this line is deduced): p.p = 0;

124

p.l = 0;

executed (the execution status of this line is deduced): p.l = 0;

125

memset(p.q_skiptable, 0, sizeof(p.q_skiptable));

executed (the execution status of this line is deduced): memset(p.q_skiptable, 0, sizeof(p.q_skiptable));

126

}

executed: }

Execution Count:2

127 -

128 /*! -

129 Constructs a byte array matcher from \a pattern. \a pattern -

130 has the given \a length. \a pattern must remain in scope, but -

131 the destructor does not delete \a pattern. -

132 */ -

133 QByteArrayMatcher::QByteArrayMatcher(const char *pattern, int length) -

134 : d(0) -

135 { -

136

p.p = reinterpret_cast<const uchar *>(pattern);

executed (the execution status of this line is deduced): p.p = reinterpret_cast<const uchar *>(pattern);

137

p.l = length;

executed (the execution status of this line is deduced): p.l = length;

138

bm_init_skiptable(p.p, p.l, p.q_skiptable);

executed (the execution status of this line is deduced): bm_init_skiptable(p.p, p.l, p.q_skiptable);

139

}

executed: }

Execution Count:1779

1779

140 -

141 /*! -

142 Constructs a byte array matcher that will search for \a pattern. -

143 Call indexIn() to perform a search. -

144 */ -

145 QByteArrayMatcher::QByteArrayMatcher(const QByteArray &pattern) -

146 : d(0), q_pattern(pattern) -

147 { -

148

p.p = reinterpret_cast<const uchar *>(pattern.constData());

executed (the execution status of this line is deduced): p.p = reinterpret_cast<const uchar *>(pattern.constData());

149

p.l = pattern.size();

executed (the execution status of this line is deduced): p.l = pattern.size();

150

bm_init_skiptable(p.p, p.l, p.q_skiptable);

executed (the execution status of this line is deduced): bm_init_skiptable(p.p, p.l, p.q_skiptable);

151

}

executed: }

Execution Count:1684

1684

152 -

153 /*! -

154 Copies the \a other byte array matcher to this byte array matcher. -

155 */ -

156 QByteArrayMatcher::QByteArrayMatcher(const QByteArrayMatcher &other) -

157 : d(0) -

158 { -

159

operator=(other);

executed (the execution status of this line is deduced): operator=(other);

160

}

executed: }

Execution Count:1

161 -

162 /*! -

163 Destroys the byte array matcher. -

164 */ -

165 QByteArrayMatcher::~QByteArrayMatcher() -

166 { -

167 } -

168 -

169 /*! -

170 Assigns the \a other byte array matcher to this byte array matcher. -

171 */ -

172 QByteArrayMatcher &QByteArrayMatcher::operator=(const QByteArrayMatcher &other) -

173 { -

174

q_pattern = other.q_pattern;

executed (the execution status of this line is deduced): q_pattern = other.q_pattern;

175

memcpy(&p, &other.p, sizeof(p));

executed (the execution status of this line is deduced): memcpy(&p, &other.p, sizeof(p));

176

return *this;

executed: return *this;

Execution Count:5

177 } -

178 -

179 /*! -

180 Sets the byte array that this byte array matcher will search for -

181 to \a pattern. -

182 -

183 \sa pattern(), indexIn() -

184 */ -

185 void QByteArrayMatcher::setPattern(const QByteArray &pattern) -

186 { -

187

q_pattern = pattern;

executed (the execution status of this line is deduced): q_pattern = pattern;

188

p.p = reinterpret_cast<const uchar *>(pattern.constData());

executed (the execution status of this line is deduced): p.p = reinterpret_cast<const uchar *>(pattern.constData());

189

p.l = pattern.size();

executed (the execution status of this line is deduced): p.l = pattern.size();

190

bm_init_skiptable(p.p, p.l, p.q_skiptable);

executed (the execution status of this line is deduced): bm_init_skiptable(p.p, p.l, p.q_skiptable);

191

}

executed: }

Execution Count:3

192 -

193 /*! -

194 Searches the byte array \a ba, from byte position \a from (default -

195 0, i.e. from the first byte), for the byte array pattern() that -

196 was set in the constructor or in the most recent call to -

197 setPattern(). Returns the position where the pattern() matched in -

198 \a ba, or -1 if no match was found. -

199 */ -

200 int QByteArrayMatcher::indexIn(const QByteArray &ba, int from) const -

201 { -

202

if (from < 0)

partially evaluated: from < 0

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:13741

0-13741

203

from = 0;

never executed: from = 0;

204

return bm_find(reinterpret_cast<const uchar *>(ba.constData()), ba.size(), from,

executed: return bm_find(reinterpret_cast<const uchar *>(ba.constData()), ba.size(), from, p.p, p.l, p.q_skiptable);

Execution Count:13741

13741

205

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

206 } -

207 -

208 /*! -

209 Searches the char string \a str, which has length \a len, from -

210 byte position \a from (default 0, i.e. from the first byte), for -

211 the byte array pattern() that was set in the constructor or in the -

212 most recent call to setPattern(). Returns the position where the -

213 pattern() matched in \a str, or -1 if no match was found. -

214 */ -

215 int QByteArrayMatcher::indexIn(const char *str, int len, int from) const -

216 { -

217

if (from < 0)

partially evaluated: from < 0

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:3

0-3

218

from = 0;

never executed: from = 0;

219

return bm_find(reinterpret_cast<const uchar *>(str), len, from,

executed: return bm_find(reinterpret_cast<const uchar *>(str), len, from, p.p, p.l, p.q_skiptable);

Execution Count:3

220

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

221 } -

222 -

223 /*! -

224 \fn QByteArray QByteArrayMatcher::pattern() const -

225 -

226 Returns the byte array pattern that this byte array matcher will -

227 search for. -

228 -

229 \sa setPattern() -

230 */ -

231 -

232 -

233 static int findChar(const char *str, int len, char ch, int from) -

234 { -

235

const uchar *s = (const uchar *)str;

never executed (the execution status of this line is deduced): const uchar *s = (const uchar *)str;

236

uchar c = (uchar)ch;

never executed (the execution status of this line is deduced): uchar c = (uchar)ch;

237

if (from < 0)

never evaluated: from < 0

238

from = qMax(from + len, 0);

never executed: from = qMax(from + len, 0);

239

if (from < len) {

never evaluated: from < len

240

const uchar *n = s + from - 1;

never executed (the execution status of this line is deduced): const uchar *n = s + from - 1;

241

const uchar *e = s + len;

never executed (the execution status of this line is deduced): const uchar *e = s + len;

242

while (++n != e)

never evaluated: ++n != e

243

if (*n == c)

never evaluated: *n == c

244

return n - s;

never executed: return n - s;

never executed: }

never executed: return -1;

247 } -

248 -

249 /*! -

250 \internal -

251 */ -

252 static int qFindByteArrayBoyerMoore( -

253 const char *haystack, int haystackLen, int haystackOffset, -

254 const char *needle, int needleLen) -

255 { -

256

uchar skiptable[256];

executed (the execution status of this line is deduced): uchar skiptable[256];

257

bm_init_skiptable((const uchar *)needle, needleLen, skiptable);

executed (the execution status of this line is deduced): bm_init_skiptable((const uchar *)needle, needleLen, skiptable);

258

if (haystackOffset < 0)

partially evaluated: haystackOffset < 0

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:2140

0-2140

259

haystackOffset = 0;

never executed: haystackOffset = 0;

260

return bm_find((const uchar *)haystack, haystackLen, haystackOffset,

executed: return bm_find((const uchar *)haystack, haystackLen, haystackOffset, (const uchar *)needle, needleLen, skiptable);

Execution Count:2140

2140

261

(const uchar *)needle, needleLen, skiptable);

executed: return bm_find((const uchar *)haystack, haystackLen, haystackOffset, (const uchar *)needle, needleLen, skiptable);

Execution Count:2140

2140

262 } -

263 -

264 #define REHASH(a) \ -

265 if (sl_minus_1 < sizeof(uint) * CHAR_BIT) \ -

266 hashHaystack -= (a) << sl_minus_1; \ -

267 hashHaystack <<= 1 -

268 -

269 /*! -

270 \internal -

271 */ -

272 int qFindByteArray( -

273 const char *haystack0, int haystackLen, int from, -

274 const char *needle, int needleLen) -

275 { -

276

const int l = haystackLen;

executed (the execution status of this line is deduced): const int l = haystackLen;

277

const int sl = needleLen;

executed (the execution status of this line is deduced): const int sl = needleLen;

278

if (from < 0)

partially evaluated: from < 0

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:674620

0-674620

279

from += l;

never executed: from += l;

280

if (uint(sl + from) > (uint)l)

partially evaluated: uint(sl + from) > (uint)l

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:674620

0-674620

281

return -1;

never executed: return -1;

282

if (!sl)

partially evaluated: !sl

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:674620

0-674620

283

return from;

never executed: return from;

284

if (!l)

partially evaluated: !l

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:674620

0-674620

285

return -1;

never executed: return -1;

286 -

287

if (sl == 1)

partially evaluated: sl == 1

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:674620

0-674620

288

return findChar(haystack0, haystackLen, needle[0], from);

never executed: return findChar(haystack0, haystackLen, needle[0], from);

289 -

290 /* -

291 We use the Boyer-Moore algorithm in cases where the overhead -

292 for the skip table should pay off, otherwise we use a simple -

293 hash function. -

294 */ -

295

if (l > 500 && sl > 5)

evaluated: l > 500

TRUE	FALSE
yes Evaluation Count:2144	yes Evaluation Count:672476

evaluated: sl > 5

TRUE	FALSE
yes Evaluation Count:2140	yes Evaluation Count:4

4-672476

296

return qFindByteArrayBoyerMoore(haystack0, haystackLen, from,

executed: return qFindByteArrayBoyerMoore(haystack0, haystackLen, from, needle, needleLen);

Execution Count:2140

2140

297

needle, needleLen);

executed: return qFindByteArrayBoyerMoore(haystack0, haystackLen, from, needle, needleLen);

Execution Count:2140

2140

298 -

299 /* -

300 We use some hashing for efficiency's sake. Instead of -

301 comparing strings, we compare the hash value of str with that -

302 of a part of this QString. Only if that matches, we call memcmp(). -

303 */ -

304

const char *haystack = haystack0 + from;

executed (the execution status of this line is deduced): const char *haystack = haystack0 + from;

305

const char *end = haystack0 + (l - sl);

executed (the execution status of this line is deduced): const char *end = haystack0 + (l - sl);

306

const uint sl_minus_1 = sl - 1;

executed (the execution status of this line is deduced): const uint sl_minus_1 = sl - 1;

307

uint hashNeedle = 0, hashHaystack = 0;

executed (the execution status of this line is deduced): uint hashNeedle = 0, hashHaystack = 0;

308

int idx;

executed (the execution status of this line is deduced): int idx;

309

for (idx = 0; idx < sl; ++idx) {

evaluated: idx < sl

TRUE	FALSE
yes Evaluation Count:4574888	yes Evaluation Count:672480

672480-4574888

310

hashNeedle = ((hashNeedle<<1) + needle[idx]);

executed (the execution status of this line is deduced): hashNeedle = ((hashNeedle<<1) + needle[idx]);

311

hashHaystack = ((hashHaystack<<1) + haystack[idx]);

executed (the execution status of this line is deduced): hashHaystack = ((hashHaystack<<1) + haystack[idx]);

312

}

executed: }

Execution Count:4574888

4574888

313

hashHaystack -= *(haystack + sl_minus_1);

executed (the execution status of this line is deduced): hashHaystack -= *(haystack + sl_minus_1);

314 -

315

while (haystack <= end) {

evaluated: haystack <= end

TRUE	FALSE
yes Evaluation Count:17366215	yes Evaluation Count:519157

519157-17366215

316

hashHaystack += *(haystack + sl_minus_1);

executed (the execution status of this line is deduced): hashHaystack += *(haystack + sl_minus_1);

317

if (hashHaystack == hashNeedle && *needle == *haystack

evaluated: hashHaystack == hashNeedle

TRUE	FALSE
yes Evaluation Count:153325	yes Evaluation Count:17212890

partially evaluated: *needle == *haystack

TRUE	FALSE
yes Evaluation Count:153325	no Evaluation Count:0

0-17212890

318

&& memcmp(needle, haystack, sl) == 0)

evaluated: memcmp(needle, haystack, sl) == 0

TRUE	FALSE
yes Evaluation Count:153323	yes Evaluation Count:2

2-153323

319

return haystack - haystack0;

executed: return haystack - haystack0;

Execution Count:153323

153323

320 -

321

REHASH(*haystack);

executed: hashHaystack -= (*haystack) << sl_minus_1;

Execution Count:17212476

evaluated: sl_minus_1 < sizeof(uint) * 8

TRUE	FALSE
yes Evaluation Count:17212476	yes Evaluation Count:416

416-17212476

322

++haystack;

executed (the execution status of this line is deduced): ++haystack;

323

}

executed: }

Execution Count:17212892

17212892

324

return -1;

executed: return -1;

Execution Count:519157

519157

325 } -

326 -

327 QT_END_NAMESPACE -

328 -

Source code Switch to Preprocessed file

Generated by Squish Coco Non-Commercial