1/*
2 * Copyright (c) 2015, 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 ROSE_MIRACLE_H
30#define ROSE_MIRACLE_H
31
32#include "ue2common.h"
33#include "runtime.h"
34#include "rose_internal.h"
35
36/** \brief Maximum number of bytes to scan when looking for a "miracle" stop
37 * character. */
38#define MIRACLE_LEN_MAX 32
39
40static really_inline
41u64a roseMiracleScan(const u8 *stop, const u8 *d, const u8 *d_start) {
42 assert(d >= d_start);
43
44 // Note: unrolling this loop manually does appear to reduce its
45 // performance. I'm sick of tilting at this particular windmill.
46
47 u32 mshift = 0;
48 do {
49 u64a s = (u64a)stop[*d];
50 if (s) {
51 s <<= mshift;
52 return s;
53 }
54 mshift++;
55 } while (--d >= d_start);
56 return 0;
57}
58
59/**
60 * \brief "Miracle" scan: uses stop table to check if we can skip forward to a
61 * location where we know that the given rose engine will be in a known state.
62 *
63 * Scans the buffer/history between relative locations \a begin_loc and \a
64 * end_loc, and returns a miracle location (if any) that appears in the stream
65 * after \a begin_loc.
66 *
67 * Returns 1 if some bytes can be skipped and sets \a miracle_loc
68 * appropriately, 0 otherwise.
69 */
70static rose_inline
71char roseMiracleOccurs(const struct RoseEngine *t,
72 const struct LeftNfaInfo *left,
73 const struct core_info *ci, const s64a begin_loc,
74 const s64a end_loc, s64a *miracle_loc) {
75 assert(!left->transient);
76 assert(left->stopTable);
77
78 DEBUG_PRINTF("looking for miracle over [%lld,%lld], maxLag=%u\n",
79 begin_loc, end_loc, left->maxLag);
80 DEBUG_PRINTF("ci->len=%zu, ci->hlen=%zu\n", ci->len, ci->hlen);
81
82 assert(begin_loc <= end_loc);
83 assert(begin_loc >= -(s64a)ci->hlen);
84 assert(end_loc <= (s64a)ci->len);
85
86 const u8 *stop = getByOffset(t, left->stopTable);
87
88 const s64a scan_end_loc = end_loc - left->maxLag;
89 if (scan_end_loc <= begin_loc) {
90 DEBUG_PRINTF("nothing to scan\n");
91 return 0;
92 }
93
94 const s64a start = MAX(begin_loc, scan_end_loc - MIRACLE_LEN_MAX);
95 DEBUG_PRINTF("scan [%lld..%lld]\n", start, scan_end_loc);
96
97 u64a s = 0; // state, on bits are miracle locations
98
99 // Scan buffer.
100 const s64a buf_scan_start = MAX(0, start);
101 if (scan_end_loc > buf_scan_start) {
102 const u8 *buf = ci->buf;
103 const u8 *d = buf + scan_end_loc - 1;
104 const u8 *d_start = buf + buf_scan_start;
105 s = roseMiracleScan(stop, d, d_start);
106 if (s) {
107 goto miracle_found;
108 }
109 }
110
111 // Scan history.
112 if (start < 0) {
113 const u8 *hbuf_end = ci->hbuf + ci->hlen;
114 const u8 *d = hbuf_end + MIN(0, scan_end_loc) - 1;
115 const u8 *d_start = hbuf_end + start;
116 s = roseMiracleScan(stop, d, d_start);
117 if (scan_end_loc > 0) {
118 // Shift s over to account for the buffer scan above.
119 s <<= scan_end_loc;
120 }
121 }
122
123 if (s) {
124 miracle_found:
125 DEBUG_PRINTF("s=0x%llx, ctz=%u\n", s, ctz64(s));
126 s64a loc = end_loc - left->maxLag - ctz64(s) - 1;
127 if (loc > begin_loc) {
128 DEBUG_PRINTF("miracle at %lld\n", loc);
129 *miracle_loc = loc;
130 return 1;
131 }
132 }
133
134 DEBUG_PRINTF("no viable miraculous stop characters found\n");
135 return 0;
136}
137
138#endif // ROSE_MIRACLE_H
139