Qt 4.8
Macros | Functions
qbytearraymatcher.cpp File Reference
#include "qbytearraymatcher.h"
#include <limits.h>

Go to the source code of this file.

Macros

#define REHASH(a)
 

Functions

static int bm_find (const uchar *cc, int l, int index, const uchar *puc, uint pl, const uchar *skiptable)
 
static void bm_init_skiptable (const uchar *cc, int len, uchar *skiptable)
 
static int findChar (const char *str, int len, char ch, int from)
 
int qFindByteArray (const char *haystack0, int haystackLen, int from, const char *needle, int needleLen)
 
static int qFindByteArrayBoyerMoore (const char *haystack, int haystackLen, int haystackOffset, const char *needle, int needleLen)
 

Macro Definition Documentation

◆ REHASH

#define REHASH (   a)
Value:
if (sl_minus_1 < sizeof(uint) * CHAR_BIT) \
hashHaystack -= (a) << sl_minus_1; \
hashHaystack <<= 1
long ASN1_INTEGER_get ASN1_INTEGER * a
unsigned int uint
Definition: qglobal.h:996

Definition at line 268 of file qbytearraymatcher.cpp.

Referenced by qFindByteArray().

Function Documentation

◆ bm_find()

static int bm_find ( const uchar cc,
int  l,
int  index,
const uchar puc,
uint  pl,
const uchar skiptable 
)
inlinestatic

Definition at line 57 of file qbytearraymatcher.cpp.

Referenced by QByteArrayMatcher::indexIn(), and qFindByteArrayBoyerMoore().

59 {
60  if (pl == 0)
61  return index > l ? -1 : index;
62  const uint pl_minus_one = pl - 1;
63 
64  register const uchar *current = cc + index + pl_minus_one;
65  const uchar *end = cc + l;
66  while (current < end) {
67  uint skip = skiptable[*current];
68  if (!skip) {
69  // possible match
70  while (skip < pl) {
71  if (*(current - skip) != puc[pl_minus_one - skip])
72  break;
73  skip++;
74  }
75  if (skip > pl_minus_one) // we have a match
76  return (current - cc) - skip + 1;
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.
80  if (skiptable[*(current - skip)] == pl)
81  skip = pl - skip;
82  else
83  skip = 1;
84  }
85  if (current > end - skip)
86  break;
87  current += skip;
88  }
89  return -1; // not found
90 }
unsigned char uchar
Definition: qglobal.h:994
unsigned int uint
Definition: qglobal.h:996
QFactoryLoader * l
quint16 index
static const KeyPair *const end

◆ bm_init_skiptable()

static void bm_init_skiptable ( const uchar cc,
int  len,
uchar skiptable 
)
inlinestatic

Definition at line 48 of file qbytearraymatcher.cpp.

Referenced by QByteArrayMatcher::QByteArrayMatcher(), qFindByteArrayBoyerMoore(), and QByteArrayMatcher::setPattern().

49 {
50  int l = qMin(len, 255);
51  memset(skiptable, l, 256*sizeof(uchar));
52  cc += len - l;
53  while (l--)
54  skiptable[*cc++] = l;
55 }
Q_DECL_CONSTEXPR const T & qMin(const T &a, const T &b)
Definition: qglobal.h:1215
unsigned char uchar
Definition: qglobal.h:994
QFactoryLoader * l

◆ findChar()

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

Definition at line 238 of file qbytearraymatcher.cpp.

Referenced by qFindByteArray().

239 {
240  const uchar *s = (const uchar *)str;
241  uchar c = (uchar)ch;
242  if (from < 0)
243  from = qMax(from + len, 0);
244  if (from < len) {
245  const uchar *n = s + from - 1;
246  const uchar *e = s + len;
247  while (++n != e)
248  if (*n == c)
249  return n - s;
250  }
251  return -1;
252 }
unsigned char c[8]
Definition: qnumeric_p.h:62
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
unsigned char uchar
Definition: qglobal.h:994

◆ qFindByteArray()

int qFindByteArray ( const char *  haystack0,
int  haystackLen,
int  from,
const char *  needle,
int  needleLen 
)
Warning
This function is not part of the public interface.

Definition at line 275 of file qbytearraymatcher.cpp.

Referenced by QByteArray::indexOf().

278 {
279  const int l = haystackLen;
280  const int sl = needleLen;
281  if (from < 0)
282  from += l;
283  if (uint(sl + from) > (uint)l)
284  return -1;
285  if (!sl)
286  return from;
287  if (!l)
288  return -1;
289 
290  if (sl == 1)
291  return findChar(haystack0, haystackLen, needle[0], from);
292 
293  /*
294  We use the Boyer-Moore algorithm in cases where the overhead
295  for the skip table should pay off, otherwise we use a simple
296  hash function.
297  */
298  if (l > 500 && sl > 5)
299  return qFindByteArrayBoyerMoore(haystack0, haystackLen, from,
300  needle, needleLen);
301 
302  /*
303  We use some hashing for efficiency's sake. Instead of
304  comparing strings, we compare the hash value of str with that
305  of a part of this QString. Only if that matches, we call memcmp().
306  */
307  const char *haystack = haystack0 + from;
308  const char *end = haystack0 + (l - sl);
309  const uint sl_minus_1 = sl - 1;
310  uint hashNeedle = 0, hashHaystack = 0;
311  int idx;
312  for (idx = 0; idx < sl; ++idx) {
313  hashNeedle = ((hashNeedle<<1) + needle[idx]);
314  hashHaystack = ((hashHaystack<<1) + haystack[idx]);
315  }
316  hashHaystack -= *(haystack + sl_minus_1);
317 
318  while (haystack <= end) {
319  hashHaystack += *(haystack + sl_minus_1);
320  if (hashHaystack == hashNeedle && *needle == *haystack
321  && memcmp(needle, haystack, sl) == 0)
322  return haystack - haystack0;
323 
324  REHASH(*haystack);
325  ++haystack;
326  }
327  return -1;
328 }
static int findChar(const char *str, int len, char ch, int from)
unsigned int uint
Definition: qglobal.h:996
static int qFindByteArrayBoyerMoore(const char *haystack, int haystackLen, int haystackOffset, const char *needle, int needleLen)
QFactoryLoader * l
static const KeyPair *const end
#define REHASH(a)

◆ qFindByteArrayBoyerMoore()

static int qFindByteArrayBoyerMoore ( const char *  haystack,
int  haystackLen,
int  haystackOffset,
const char *  needle,
int  needleLen 
)
static
Warning
This function is not part of the public interface.

Definition at line 256 of file qbytearraymatcher.cpp.

Referenced by qFindByteArray().

259 {
260  uchar skiptable[256];
261  bm_init_skiptable((const uchar *)needle, needleLen, skiptable);
262  if (haystackOffset < 0)
263  haystackOffset = 0;
264  return bm_find((const uchar *)haystack, haystackLen, haystackOffset,
265  (const uchar *)needle, needleLen, skiptable);
266 }
static int bm_find(const uchar *cc, int l, int index, const uchar *puc, uint pl, const uchar *skiptable)
static void bm_init_skiptable(const uchar *cc, int len, uchar *skiptable)
unsigned char uchar
Definition: qglobal.h:994