1 /*
2  * Copyright (c) 2015-2017, Intel Corporation
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  *  * Redistributions of source code must retain the above copyright notice,
8  *    this list of conditions and the following disclaimer.
9  *  * Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *  * Neither the name of Intel Corporation nor the names of its contributors
13  *    may be used to endorse or promote products derived from this software
14  *    without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26  * POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 /** \file
30  * \brief NFA acceleration analysis code.
31  */
32 
33 #ifndef NG_LIMEX_ACCEL_H
34 #define NG_LIMEX_ACCEL_H
35 
36 #include "ng_holder.h"
37 #include "ng_misc_opt.h"
38 #include "ue2common.h"
39 #include "nfa/accelcompile.h"
40 #include "util/accel_scheme.h"
41 #include "util/charreach.h"
42 #include "util/flat_containers.h"
43 #include "util/order_check.h"
44 
45 #include <map>
46 #include <vector>
47 
48 namespace ue2 {
49 
50 /* compile time accel defs */
51 #define MAX_MERGED_ACCEL_STOPS 200
52 #define ACCEL_MAX_STOP_CHAR 24
53 #define ACCEL_MAX_FLOATING_STOP_CHAR 192 /* accelerating sds is important */
54 
55 // forward-declaration of CompileContext
56 struct CompileContext;
57 
58 void findAccelFriends(const NGHolder &g, NFAVertex v,
59                   const std::map<NFAVertex, BoundedRepeatSummary> &br_cyclic,
60                   u32 offset, flat_set<NFAVertex> *friends);
61 
62 #define DOUBLE_SHUFTI_LIMIT 20
63 
64 NFAVertex get_sds_or_proxy(const NGHolder &g);
65 
66 AccelScheme nfaFindAccel(const NGHolder &g, const std::vector<NFAVertex> &verts,
67                     const std::vector<CharReach> &refined_cr,
68                     const std::map<NFAVertex, BoundedRepeatSummary> &br_cyclic,
69                     bool allow_wide, bool look_for_double_byte = false);
70 
71 AccelScheme findBestAccelScheme(std::vector<std::vector<CharReach> > paths,
72                                 const CharReach &terminating,
73                                 bool look_for_double_byte = false);
74 
75 /** \brief Check if vertex \a v is an accelerable state (for a limex NFA). If a
76  *  single byte accel scheme is found it is placed into *as
77  */
78 bool nfaCheckAccel(const NGHolder &g, NFAVertex v,
79                    const std::vector<CharReach> &refined_cr,
80                    const std::map<NFAVertex, BoundedRepeatSummary> &br_cyclic,
81                    AccelScheme *as, bool allow_wide);
82 
83 
84 } // namespace ue2
85 
86 #endif
87