1 /*
2  * Copyright (c) 2015-2020, 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 /**
30  * \file
31  * \brief Limex NFA construction code.
32  */
33 
34 #ifndef NG_LIMEX_H
35 #define NG_LIMEX_H
36 
37 #include "ue2common.h"
38 #include "som/som.h"
39 #include "util/bytecode_ptr.h"
40 
41 #include <map>
42 #include <memory>
43 #include <vector>
44 
45 struct NFA;
46 
47 namespace ue2 {
48 
49 class CharReach;
50 class NG;
51 class NGHolder;
52 class ReportManager;
53 struct CompileContext;
54 
55 /**
56  * \brief Determine if the given graph is implementable as an NFA.
57  *
58  * Returns zero if the NFA is not implementable (usually because it has too
59  * many states for any of our models). Otherwise returns the number of states.
60  *
61  * ReportManager is used by NFA_SUFFIX and NFA_OUTFIX only. NFA_PREFIX and
62  * NFA_INFIX use unmanaged rose-local reports.
63  */
64 u32 isImplementableNFA(const NGHolder &g, const ReportManager *rm,
65                        const CompileContext &cc);
66 
67 /**
68  * \brief Late-stage graph reductions.
69  *
70  * This will call \ref removeRedundancy and apply its changes to the given
71  * holder only if it is implementable afterwards.
72  */
73 void reduceImplementableGraph(NGHolder &g, som_type som,
74                               const ReportManager *rm,
75                               const CompileContext &cc);
76 
77 /**
78  * \brief For a given graph, count the number of accel states it will have in
79  * an implementation.
80  *
81  * \return the number of accel states, or NFA_MAX_ACCEL_STATES + 1 if an
82  * implementation would not be constructible.
83  */
84 u32 countAccelStates(const NGHolder &g, const ReportManager *rm,
85                      const CompileContext &cc);
86 
87 /**
88  * \brief Construct an NFA from the given graph.
89  *
90  * Returns zero if the NFA is not implementable (usually because it has too
91  * many states for any of our models). Otherwise returns the number of states.
92  *
93  * ReportManager is used by NFA_SUFFIX and NFA_OUTFIX only. NFA_PREFIX and
94  * NFA_INFIX use unmanaged rose-local reports.
95  *
96  * Note: this variant of the function allows a model to be specified with the
97  * \a hint parameter.
98  */
99 bytecode_ptr<NFA>
100 constructNFA(const NGHolder &g, const ReportManager *rm,
101              const std::map<u32, u32> &fixed_depth_tops,
102              const std::map<u32, std::vector<std::vector<CharReach>>> &triggers,
103              bool compress_state, bool &fast, const CompileContext &cc);
104 
105 /**
106  * \brief Build a reverse NFA from the graph given, which should have already
107  * been reversed.
108  *
109  * Used for reverse NFAs used in SOM mode.
110  */
111 bytecode_ptr<NFA> constructReversedNFA(const NGHolder &h,
112                                        const CompileContext &cc);
113 
114 #ifndef RELEASE_BUILD
115 
116 /**
117  * \brief Construct an NFA (with model type hint) from the given graph.
118  *
119  * Returns zero if the NFA is not implementable (usually because it has too
120  * many states for any of our models). Otherwise returns the number of states.
121  *
122  * ReportManager is used by NFA_SUFFIX and NFA_OUTFIX only. NFA_PREFIX and
123  * NFA_INFIX use unmanaged rose-local reports.
124  *
125  * Note: this variant of the function allows a model to be specified with the
126  * \a hint parameter.
127  */
128 bytecode_ptr<NFA>
129 constructNFA(const NGHolder &g, const ReportManager *rm,
130              const std::map<u32, u32> &fixed_depth_tops,
131              const std::map<u32, std::vector<std::vector<CharReach>>> &triggers,
132              bool compress_state, bool &fast, u32 hint, const CompileContext &cc);
133 
134 /**
135  * \brief Build a reverse NFA (with model type hint) from the graph given,
136  * which should have already been reversed.
137  *
138  * Used for reverse NFAs used in SOM mode.
139  */
140 bytecode_ptr<NFA> constructReversedNFA(const NGHolder &h, u32 hint,
141                                        const CompileContext &cc);
142 
143 #endif // RELEASE_BUILD
144 
145 } // namespace ue2
146 
147 #endif // NG_METEOR_H
148