← Back to branch summary

~ubuntu-branches/ubuntu/wily/mplayerplug-in/wily

« back to all changes in this revision

Viewing changes to extras/memmem.c~

  • Committer: Bazaar Package Importer
  • Author(s): Cesare Tirabassi
  • Date: 2008-07-06 23:35:53 UTC
  • mfrom: (1.1.11 upstream)
  • Revision ID: james.westby@ubuntu.com-20080706233553-tfxk1bnjr8uewq0c
Tags: 3.55-1ubuntu1
* Merge from Debian unstable. Remaining Ubuntu changes:
  - debian/control
    + replace iceweasel with firefox3.0 | firefox 2
    + replace iceape-browser with seamonkey-browser
    + add Depends on | mplayer-nogui (>= 1.0~rc2)
    + add Xb-Npp-xxx tags accordingly to "firefox distro add-on support"
      spec
    + Modify Maintainer value to match the DebianMaintainerField
      specification.
  - debian/mozilla-mplayer.links:
    + add firefox and xulrunner symlinks
* Replace iceape-dev b-d with libxul-dev.
* Add xulrunner in lists of possible "browsers".
* Following upstream suggestion, change required mplayer version
  to be (>= 1.0~rc2).

Show diffs side-by-side

added added

removed removed

Lines of Context:
extras/memmem.c~
 
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
 
 
20
#include <stddef.h>
 
21
#include <stdlib.h>
 
22
 
 
23
 
 
24
 
 
25
/* This function implements the Boyer-Moore algorithm.
 
26
   It is assumed that chars have eight bits.  */
 
27
void *memmem(const void *haystack, const size_t haystack_len,
 
28
             const void *needle, const size_t needle_len)
 
29
{
 
30
    const unsigned char *const haystack_endptr =
 
31
        (const unsigned char *) haystack + haystack_len;
 
32
    const unsigned char *const needle_endptr =
 
33
        (const unsigned char *) needle + needle_len;
 
34
    const unsigned char *haystack_shifting_ptr;
 
35
 
 
36
    size_t *shift_good_suffix;
 
37
    size_t shift_last_occurrence[256];
 
38
 
 
39
 
 
40
printf("memmem called\n");
 
41
    if (needle_len > haystack_len)
 
42
        return 0;
 
43
 
 
44
    haystack_shifting_ptr = (const unsigned char *) haystack + needle_len;
 
45
 
 
46
 
 
47
    /* Compute good suffix function.  */
 
48
    shift_good_suffix = (size_t*)malloc(2 * needle_len * sizeof *shift_good_suffix);
 
49
    if (shift_good_suffix != 0) {
 
50
        const unsigned char *needle_ptr;
 
51
        size_t i, j;
 
52
 
 
53
        shift_good_suffix[0] = 0;
 
54
        needle_ptr = (const unsigned char *) needle + 1;
 
55
        for (i = 1, j = 0; i < needle_len; ++i) {
 
56
            while (j > 0
 
57
                   && ((const unsigned char *) needle)[j] != *needle_ptr)
 
58
                j = shift_good_suffix[j - 1];
 
59
            if (((const unsigned char *) needle)[j] == *needle_ptr)
 
60
                ++j;
 
61
            shift_good_suffix[i] = j;
 
62
            ++needle_ptr;
 
63
        }
 
64
 
 
65
        shift_good_suffix[needle_len] = 0;
 
66
        needle_ptr = (const unsigned char *) needle + needle_len - 1;
 
67
        for (i = 1, j = 0; i < needle_len; ++i) {
 
68
            --needle_ptr;
 
69
            while (j > 0
 
70
                   && ((const unsigned char *) needle)[needle_len - 1 -
 
71
                                                       j] != *needle_ptr)
 
72
                j = shift_good_suffix[needle_len - 1 + j];
 
73
            if (((const unsigned char *) needle)[needle_len - 1 - j] ==
 
74
                *needle_ptr)
 
75
                ++j;
 
76
            shift_good_suffix[needle_len + i] = j;
 
77
        }
 
78
 
 
79
        for (i = 0; i < needle_len; ++i)
 
80
            shift_good_suffix[i] = needle_len - shift_good_suffix[i];
 
81
 
 
82
        for (i = 0; i < needle_len; ++i) {
 
83
            j = needle_len - 1 - shift_good_suffix[needle_len + i];
 
84
            if (shift_good_suffix[j] >
 
85
                i + 1 - shift_good_suffix[needle_len + i])
 
86
                shift_good_suffix[j] =
 
87
                    i + 1 - shift_good_suffix[needle_len + i];
 
88
        }
 
89
    }
 
90
 
 
91
 
 
92
    /* Compute last occurence function.  */
 
93
    {
 
94
        const unsigned char *needle_ptr = (const unsigned char *)needle;
 
95
        size_t i;
 
96
 
 
97
        for (i = 0; i < 256; ++i)
 
98
            shift_last_occurrence[i] = 0;
 
99
        for (i = 0; i < needle_len; ++i)
 
100
            shift_last_occurrence[*needle_ptr++] = i + 1;
 
101
    }
 
102
 
 
103
 
 
104
    /* Matching algorithm.  */
 
105
    while (haystack_shifting_ptr <= haystack_endptr) {
 
106
        const unsigned char *haystack_ptr = haystack_shifting_ptr;
 
107
        const unsigned char *needle_ptr = needle_endptr;
 
108
        size_t len = needle_len;
 
109
 
 
110
        while (len > 0 && *--haystack_ptr == *--needle_ptr)
 
111
            --len;
 
112
 
 
113
        if (len == 0) {
 
114
            if (shift_good_suffix != 0)
 
115
                free(shift_good_suffix);
 
116
            return (void *) haystack_ptr;
 
117
        }
 
118
 
 
119
        {
 
120
            const size_t shift1 =
 
121
                shift_good_suffix != 0 ? shift_good_suffix[len - 1] : 1;
 
122
            const size_t shift2 =
 
123
                (len > shift_last_occurrence[*haystack_ptr]
 
124
                 ? len - shift_last_occurrence[*haystack_ptr] : 1);
 
125
 
 
126
            haystack_shifting_ptr += shift1 > shift2 ? shift1 : shift2;
 
127
        }
 
128
    }
 
129
 
 
130
 
 
131
    if (shift_good_suffix != 0)
 
132
        free(shift_good_suffix);
 
133
printf("memmem exited\n");
 
134
    return 0;
 
135
}