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