1/*
2 * Copyright (c) 2015-2018, 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#ifndef MCCLELLAN_INTERNAL_H
30#define MCCLELLAN_INTERNAL_H
31
32#include "nfa_internal.h"
33
34#ifdef __cplusplus
35extern "C"
36{
37#endif
38
39#define ACCEPT_FLAG 0x8000
40#define ACCEL_FLAG 0x4000
41#define STATE_MASK 0x3fff
42
43#define SHERMAN_STATE 1
44
45#define SHERMAN_TYPE_OFFSET 0
46#define SHERMAN_FIXED_SIZE 32
47
48#define SHERMAN_LEN_OFFSET 1
49#define SHERMAN_DADDY_OFFSET 2
50#define SHERMAN_CHARS_OFFSET 4
51#define SHERMAN_STATES_OFFSET(sso_len) (4 + (sso_len))
52
53#define WIDE_STATE 2
54#define WIDE_ENTRY_OFFSET8(weo_pos) (2 + (weo_pos))
55#define WIDE_ENTRY_OFFSET16(weo_pos) (4 + (weo_pos))
56
57#define WIDE_WIDTH_OFFSET 0
58#define WIDE_SYMBOL_OFFSET8 1
59#define WIDE_TRANSITION_OFFSET8(wto_width) (1 + (wto_width))
60#define WIDE_SYMBOL_OFFSET16 2
61#define WIDE_TRANSITION_OFFSET16(wto_width) (2 + ROUNDUP_N(wto_width, 2))
62
63struct report_list {
64 u32 count;
65 ReportID report[];
66};
67
68struct mstate_aux {
69 u32 accept;
70 u32 accept_eod;
71 u16 top;
72 u32 accel_offset; /* relative to start of struct mcclellan; 0 if no accel */
73};
74
75#define MCCLELLAN_FLAG_SINGLE 1 /**< we raise only single accept id */
76
77struct mcclellan {
78 u16 state_count; /**< total number of states */
79 u32 length; /**< length of dfa in bytes */
80 u16 start_anchored; /**< anchored start state */
81 u16 start_floating; /**< floating start state */
82 u32 aux_offset; /**< offset of the aux structures relative to the start of
83 * the nfa structure */
84 u32 sherman_offset; /**< offset of array of sherman state offsets the
85 * state_info structures relative to the start of the
86 * nfa structure */
87 u32 sherman_end; /**< offset of the end of the state_info structures
88 * relative to the start of the nfa structure */
89 u16 accel_limit_8; /**< 8 bit, lowest accelerable state */
90 u16 accept_limit_8; /**< 8 bit, lowest accept state */
91 u16 sherman_limit; /**< lowest sherman state */
92 u16 wide_limit; /**< 8/16 bit, lowest wide head state */
93 u8 alphaShift;
94 u8 flags;
95 u8 has_accel; /**< 1 iff there are any accel plans */
96 u8 has_wide; /**< 1 iff there exists any wide state */
97 u8 remap[256]; /**< remaps characters to a smaller alphabet */
98 ReportID arb_report; /**< one of the accepts that this dfa may raise */
99 u32 accel_offset; /**< offset of accel structures from start of McClellan */
100 u32 haig_offset; /**< reserved for use by Haig, relative to start of NFA */
101 u32 wide_offset; /**< offset of the wide state entries to the start of the
102 * nfa structure */
103};
104
105static really_inline
106const char *findShermanState(UNUSED const struct mcclellan *m,
107 const char *sherman_base_offset, u32 sherman_base,
108 u32 s) {
109 const char *rv
110 = sherman_base_offset + SHERMAN_FIXED_SIZE * (s - sherman_base);
111 assert(rv < (const char *)m + m->length - sizeof(struct NFA));
112 UNUSED u8 type = *(const u8 *)(rv + SHERMAN_TYPE_OFFSET);
113 assert(type == SHERMAN_STATE);
114 return rv;
115}
116
117static really_inline
118char *findMutableShermanState(char *sherman_base_offset, u16 sherman_base,
119 u32 s) {
120 return sherman_base_offset + SHERMAN_FIXED_SIZE * (s - sherman_base);
121}
122
123static really_inline
124const char *findWideEntry8(UNUSED const struct mcclellan *m,
125 const char *wide_base, u32 wide_limit, u32 s) {
126 UNUSED u8 type = *(const u8 *)wide_base;
127 assert(type == WIDE_STATE);
128 const u32 entry_offset
129 = *(const u32 *)(wide_base
130 + WIDE_ENTRY_OFFSET8((s - wide_limit) * sizeof(u32)));
131
132 const char *rv = wide_base + entry_offset;
133 assert(rv < (const char *)m + m->length - sizeof(struct NFA));
134 return rv;
135}
136
137static really_inline
138const char *findWideEntry16(UNUSED const struct mcclellan *m,
139 const char *wide_base, u32 wide_limit, u32 s) {
140 UNUSED u8 type = *(const u8 *)wide_base;
141 assert(type == WIDE_STATE);
142 const u32 entry_offset
143 = *(const u32 *)(wide_base
144 + WIDE_ENTRY_OFFSET16((s - wide_limit) * sizeof(u32)));
145
146 const char *rv = wide_base + entry_offset;
147 assert(rv < (const char *)m + m->length - sizeof(struct NFA));
148 return rv;
149}
150
151static really_inline
152char *findMutableWideEntry16(char *wide_base, u32 wide_limit, u32 s) {
153 u32 entry_offset
154 = *(const u32 *)(wide_base
155 + WIDE_ENTRY_OFFSET16((s - wide_limit) * sizeof(u32)));
156
157 return wide_base + entry_offset;
158}
159
160#ifdef __cplusplus
161}
162#endif
163
164#endif
165