memmem.c
上传用户:hongyu5696
上传日期:2018-01-22
资源大小:391k
文件大小:4k
源码类别:

PlugIns编程

开发平台:

Unix_Linux

  1. /* This file implements memmem, a function to find the first occurrence
  2.    of the contents of a memory area in another memory area.
  3.    Copyright (C) 2003 Martin Dickopp
  4.   
  5.    This file is free software; you can redistribute it and/or modify
  6.    it under the terms of the GNU General Public License as published by
  7.    the Free Software Foundation; either version 2 of the License, or
  8.    (at your option) any later version.
  9.   
  10.    This file is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.    GNU General Public License for more details.
  14.   
  15.    You should have received a copy of the GNU General Public License
  16.    along with this file; if not, write to the Free Software
  17.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
  18.    USA.  */
  19. #include <stddef.h>
  20. #include <stdlib.h>
  21. /* This function implements the Boyer-Moore algorithm.
  22.    It is assumed that chars have eight bits.  */
  23. void *memmem(const void *haystack, const size_t haystack_len,
  24.      const void *needle, const size_t needle_len)
  25. {
  26.     const unsigned char *const haystack_endptr =
  27. (const unsigned char *) haystack + haystack_len;
  28.     const unsigned char *const needle_endptr =
  29. (const unsigned char *) needle + needle_len;
  30.     const unsigned char *haystack_shifting_ptr;
  31.     size_t *shift_good_suffix;
  32.     size_t shift_last_occurrence[256];
  33.     if (needle_len > haystack_len)
  34. return 0;
  35.     haystack_shifting_ptr = (const unsigned char *) haystack + needle_len;
  36.     /* Compute good suffix function.  */
  37.     shift_good_suffix = (size_t*)malloc(2 * needle_len * sizeof *shift_good_suffix);
  38.     if (shift_good_suffix != 0) {
  39. const unsigned char *needle_ptr;
  40. size_t i, j;
  41. shift_good_suffix[0] = 0;
  42. needle_ptr = (const unsigned char *) needle + 1;
  43. for (i = 1, j = 0; i < needle_len; ++i) {
  44.     while (j > 0
  45.    && ((const unsigned char *) needle)[j] != *needle_ptr)
  46. j = shift_good_suffix[j - 1];
  47.     if (((const unsigned char *) needle)[j] == *needle_ptr)
  48. ++j;
  49.     shift_good_suffix[i] = j;
  50.     ++needle_ptr;
  51. }
  52. shift_good_suffix[needle_len] = 0;
  53. needle_ptr = (const unsigned char *) needle + needle_len - 1;
  54. for (i = 1, j = 0; i < needle_len; ++i) {
  55.     --needle_ptr;
  56.     while (j > 0
  57.    && ((const unsigned char *) needle)[needle_len - 1 -
  58.        j] != *needle_ptr)
  59. j = shift_good_suffix[needle_len - 1 + j];
  60.     if (((const unsigned char *) needle)[needle_len - 1 - j] ==
  61. *needle_ptr)
  62. ++j;
  63.     shift_good_suffix[needle_len + i] = j;
  64. }
  65. for (i = 0; i < needle_len; ++i)
  66.     shift_good_suffix[i] = needle_len - shift_good_suffix[i];
  67. for (i = 0; i < needle_len; ++i) {
  68.     j = needle_len - 1 - shift_good_suffix[needle_len + i];
  69.     if (shift_good_suffix[j] >
  70. i + 1 - shift_good_suffix[needle_len + i])
  71. shift_good_suffix[j] =
  72.     i + 1 - shift_good_suffix[needle_len + i];
  73. }
  74.     }
  75.     /* Compute last occurence function.  */
  76.     {
  77. const unsigned char *needle_ptr = (const unsigned char *)needle;
  78. size_t i;
  79. for (i = 0; i < 256; ++i)
  80.     shift_last_occurrence[i] = 0;
  81. for (i = 0; i < needle_len; ++i)
  82.     shift_last_occurrence[*needle_ptr++] = i + 1;
  83.     }
  84.     /* Matching algorithm.  */
  85.     while (haystack_shifting_ptr <= haystack_endptr) {
  86. const unsigned char *haystack_ptr = haystack_shifting_ptr;
  87. const unsigned char *needle_ptr = needle_endptr;
  88. size_t len = needle_len;
  89. while (len > 0 && *--haystack_ptr == *--needle_ptr)
  90.     --len;
  91. if (len == 0) {
  92.     if (shift_good_suffix != 0)
  93. free(shift_good_suffix);
  94.     return (void *) haystack_ptr;
  95. }
  96. {
  97.     const size_t shift1 =
  98. shift_good_suffix != 0 ? shift_good_suffix[len - 1] : 1;
  99.     const size_t shift2 =
  100. (len > shift_last_occurrence[*haystack_ptr]
  101.  ? len - shift_last_occurrence[*haystack_ptr] : 1);
  102.     haystack_shifting_ptr += shift1 > shift2 ? shift1 : shift2;
  103. }
  104.     }
  105.     if (shift_good_suffix != 0)
  106. free(shift_good_suffix);
  107.     return 0;
  108. }