论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2007-08-21 16:25 |只看该作者 |倒序浏览

下面的代码用=G命令缩进从第72行会出问题。

/*
** $Id$
**
** acsmx2.c
**
** Multi-Pattern Search Engine
**
** Aho-Corasick State Machine - version 2.0
**
** Supports both Non-Deterministic and Deterministic Finite Automata
**
**
** Reference - Efficient String matching: An Aid to Bibliographic Search
** Alfred V Aho and Margaret J Corasick
** Bell Labratories
** Copyright(C) 1975 Association for Computing Machinery,Inc
**
** +++
** +++ Version 1.0 notes - Marc Norton:
** +++
**
** Original implementation based on the 4 algorithms in the paper by Aho & Corasick,
** some implementation ideas from 'Practical Algorithms in C', and some
** of my own.
**
** 1) Finds all occurrences of all patterns within a text.
**
** +++
** +++ Version 2.0 Notes - Marc Norton/Dan Roelker:
** +++
**
** New implementation modifies the state table storage and access model to use
** compacted sparse vector storage. Dan Roelker and I hammered this strategy out
** amongst many others in order to reduce memory usage and improve caching performance.
** The memory usage is greatly reduced, we only use 1/4 of what we use to. The caching
** performance is better in pure benchmarking tests, but does not show overall improvement
** in Snort. Unfortunately, once a pattern match test has been performed Snort moves on to doing
** performance is better in pure benchmarking tests, but does not show overall improvement
** in Snort. Unfortunately, once a pattern match test has been performed Snort moves on to doing
** many other things before we get back to a patteren match test, so the cache is voided.
**
** This versions has better caching performance characteristics, reduced memory,
** more state table storage options, and requires no a priori case conversions.
** It does maintain the same public interface. (Snort only used banded storage).
**
** 1) Supports NFA and DFA state machines, and basic keyword state machines
** 2) Initial transition table uses Linked Lists
** 3) Improved state table memory options. NFA and DFA state
** transition tables are converted to one of 4 formats during compilation.
** a) Full matrix
** b) Sparse matrix
** c) Banded matrix (Default-this is the only one used in snort)
** d) Sparse-Banded matrix
** 4) Added support for acstate_t in .h file so we can compile states as
** 16, or 32 bit state values for another reduction in memory consumption,
** smaller states allows more of the state table to be cached, and improves
** performance on x86-P4. Your mileage may vary, especially on risc systems.
** 5) Added a bool to each state transition list to indicate if there is a matching
** pattern in the state. This prevents us from accessing another data array
** and can improve caching/performance.
** 6) The search functions are very sensitive, don't change them without extensive testing,
** or you'll just spoil the caching and prefetching opportunities.
**
** Extras for fellow pattern matchers:
** The table below explains the storage format used at each step.
** You can use an NFA or DFA to match with, the NFA is slower but tiny - set the structure directly.
** You can use any of the 4 storage modes above -full,sparse,banded,sparse-bands, set the structure directly.
** For applications where you have lots of data and a pattern set to search, this version was up to 3x faster
** than the previous verion, due to caching performance. This cannot be fully realized in Snort yet,
** but other applications may have better caching opportunities.
** Snort only needs to use the banded or full storage.
**
** Transition table format at each processing stage.
** -------------------------------------------------
** Transition table format at each processing stage.
** -------------------------------------------------
** Patterns -> Keyword State Table (List)
** Keyword State Table -> NFA (List)
** NFA -> DFA (List)
** DFA (List)-> Sparse Rows O(m-avg # transitions per state)
** -> Banded Rows O(1)
** -> Sparse-Banded Rows O(nb-# bands)
** -> Full Matrix O(1)
**
** Copyright(C) 2002,2003,2004 Marc Norton
** Copyright(C) 2003,2004 Daniel Roelker
** Copyright(C) 2002,2003,2004 Sourcefire,Inc.
**
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 2 of the License, or
** (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*
* Notes:
*
* 8/28/06
* man - Sparse and SparseBands - fixed off by one in calculating matching index
* SparseBands changed ps increment to 2+n to increment between bands.
*/