1/*
2 * Copyright (c) 2015-2016, 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 Bounded repeat compile-time code.
31 */
32#include "repeatcompile.h"
33#include "util/bitutils.h"
34#include "util/charreach.h"
35#include "util/depth.h"
36#include "util/dump_charclass.h"
37#include "util/multibit_build.h"
38#include "util/verify_types.h"
39
40#include <algorithm>
41#include <cstring> // memset
42#include <utility>
43
44using namespace std;
45
46namespace ue2 {
47
48/** \brief Calculate the number of slots required to store the given repeat in
49 * a RANGE model. */
50static
51u32 numRangeSlots(u32 repeatMin, u32 repeatMax) {
52 assert(repeatMax > repeatMin);
53
54 u32 d = repeatMax - repeatMin;
55 u32 slots = 2 * ((repeatMax / d) + 1);
56 return slots;
57}
58
59static
60u32 calcPackedBits(u64a val) {
61 assert(val);
62 if (val <= 1) {
63 return 1;
64 }
65 u32 bits = lg2_64(val - 1) + 1U; /* lg2 rounds down */
66 DEBUG_PRINTF("packing %llu into %u bits\n", val, bits);
67 return bits;
68}
69
70/* returns the min number of bytes required to represent val options */
71u32 calcPackedBytes(u64a val) {
72 u32 rv = (calcPackedBits(val) + 7U) / 8U;
73 DEBUG_PRINTF("packing %llu into %u bytes\n", val, rv);
74 return rv;
75}
76
77static
78u32 repeatRecurTable(struct RepeatStateInfo *info, const depth &repeatMax,
79 const u32 minPeriod) {
80 u32 repeatTmp = info->patchCount > 2 ? 64 : (u32)repeatMax;
81 u32 repeat_index = repeatTmp < minPeriod ? repeatTmp : minPeriod;
82 for (u32 i = 0; i <= repeat_index; i++) {
83 info->table.push_back(i + 1);
84 }
85 for (u32 i = minPeriod + 1; i <= repeatTmp; i++) {
86 info->table.push_back(info->table[i - 1] + info->table[i - minPeriod]);
87 if (info->table[i] < info->table[i - 1]) {
88 return i - 1;
89 }
90 }
91 return 0;
92}
93
94static
95u32 findOptimalPatchSize(struct RepeatStateInfo *info, const depth &repeatMax,
96 const u32 minPeriod, u32 rv) {
97 u32 cnt = 0;
98 u32 patch_bits = 0;
99 u32 total_size = 0;
100 u32 min = ~0U;
101 u32 patch_len = 0;
102
103 if (!rv) {
104 rv = repeatMax;
105 }
106
107 for (u32 i = minPeriod; i <= rv; i++) {
108 cnt = ((u32)repeatMax + (i - 1)) / i + 1;
109
110 // no bit packing version
111 patch_bits = calcPackedBits(info->table[i]);
112 total_size = (patch_bits + 7U) / 8U * cnt;
113
114 if (total_size < min) {
115 patch_len = i;
116 min = total_size;
117 info->patchCount = cnt;
118 }
119 }
120 return patch_len;
121}
122
123RepeatStateInfo::RepeatStateInfo(enum RepeatType type, const depth &repeatMin,
124 const depth &repeatMax, u32 minPeriod)
125 : stateSize(0), packedCtrlSize(0), horizon(0), patchCount(0),
126 patchSize(0), encodingSize(0), patchesOffset(0) {
127 assert(repeatMin <= repeatMax);
128 assert(repeatMax.is_reachable());
129 assert(minPeriod || type != REPEAT_SPARSE_OPTIMAL_P);
130
131 switch (type) {
132 case REPEAT_FIRST:
133 assert(repeatMin.is_finite());
134 stateSize = 0; // everything is in the control block.
135 horizon = repeatMin;
136 packedCtrlSize = calcPackedBytes(horizon + 1);
137 break;
138 case REPEAT_LAST:
139 assert(repeatMax.is_finite());
140 stateSize = 0; // everything is in the control block.
141 horizon = repeatMax + 1;
142 packedCtrlSize = calcPackedBytes(horizon + 1);
143 break;
144 case REPEAT_RING:
145 assert(repeatMax.is_finite());
146 stateSize = mmbit_size(repeatMax + 1);
147 horizon = repeatMax * 2 + 1; /* TODO: investigate tightening */
148 // Packed offset member, plus two bytes for each ring index, reduced to
149 // one byte each if they'll fit in eight bits.
150 {
151 u32 offset_len = calcPackedBytes(horizon + 1);
152 u32 ring_indices_len = repeatMax < depth(254) ? 2 : 4;
153 packedCtrlSize = offset_len + ring_indices_len;
154 }
155 break;
156 case REPEAT_RANGE:
157 assert(repeatMax.is_finite());
158 assert(repeatMin < repeatMax);
159 stateSize = numRangeSlots(repeatMin, repeatMax) * sizeof(u16);
160 horizon = repeatMax * 2 + 1;
161 // Packed offset member, plus one byte for the number of range
162 // elements.
163 packedCtrlSize = calcPackedBytes(horizon + 1) + 1;
164 break;
165 case REPEAT_BITMAP:
166 stateSize = 0; // everything is in the control block.
167 horizon = 0; // unused
168 packedCtrlSize = ROUNDUP_N(repeatMax + 1, 8) / 8;
169 break;
170 case REPEAT_SPARSE_OPTIMAL_P:
171 assert(minPeriod);
172 assert(repeatMax.is_finite());
173 {
174 u32 rv = repeatRecurTable(this, repeatMax, minPeriod);
175 u32 repeatTmp = 0;
176 if ((u32)repeatMax < minPeriod) {
177 repeatTmp = repeatMax;
178 patchCount = 1;
179 } else {
180 // find optimal patch size
181 repeatTmp =
182 findOptimalPatchSize(this, repeatMax, minPeriod, rv);
183 assert(patchCount < 65536);
184 }
185 DEBUG_PRINTF("repeat[%u %u], period=%u\n", (u32)repeatMin,
186 (u32)repeatMax, minPeriod);
187 u64a maxVal = table[repeatTmp];
188 encodingSize = calcPackedBytes(maxVal);
189 patchSize = repeatTmp;
190 assert(encodingSize <= 64);
191
192 patchesOffset = mmbit_size(patchCount);
193 stateSize = patchesOffset + encodingSize * patchCount;
194 horizon = (repeatTmp * patchCount) * 2 + 1;
195 u32 ring_indices_len = patchCount < depth(254) ? 2 : 4;
196 packedCtrlSize = calcPackedBytes(horizon + 1) + ring_indices_len;
197 }
198 break;
199 case REPEAT_TRAILER:
200 assert(repeatMax.is_finite());
201 assert(repeatMin <= depth(64));
202 stateSize = 0; // everything is in the control block.
203 horizon = repeatMax + 1;
204 packedFieldSizes.resize(2);
205 packedFieldSizes[0] = calcPackedBits(horizon + 1);
206 packedFieldSizes[1] = repeatMin;
207 packedCtrlSize = (packedFieldSizes[0] + packedFieldSizes[1] + 7U) / 8U;
208 break;
209 case REPEAT_ALWAYS:
210 assert(repeatMin == 0ULL);
211 assert(repeatMax.is_infinite());
212 stateSize = 0; // everything is in the control block.
213 horizon = 0;
214 packedCtrlSize = 0;
215 break;
216 }
217 DEBUG_PRINTF("stateSize=%u, packedCtrlSize=%u, horizon=%u\n", stateSize,
218 packedCtrlSize, horizon);
219
220 assert(packedCtrlSize <= sizeof(RepeatControl));
221}
222
223/** \brief Returns the packed control block size in bytes for a given bounded
224 * repeat. */
225static
226u32 packedSize(enum RepeatType type, const depth &repeatMin,
227 const depth &repeatMax, u32 minPeriod) {
228 RepeatStateInfo rsi(type, repeatMin, repeatMax, minPeriod);
229 return rsi.packedCtrlSize;
230}
231
232/** \brief Returns the stream state size in bytes for a given bounded
233 * repeat. */
234static
235u32 streamStateSize(enum RepeatType type, const depth &repeatMin,
236 const depth &repeatMax, u32 minPeriod) {
237 RepeatStateInfo rsi(type, repeatMin, repeatMax, minPeriod);
238 return rsi.stateSize;
239}
240
241enum RepeatType chooseRepeatType(const depth &repeatMin, const depth &repeatMax,
242 u32 minPeriod, bool is_reset,
243 bool has_external_guard) {
244 if (repeatMax.is_infinite()) {
245 if (has_external_guard && !repeatMin) {
246 return REPEAT_ALWAYS;
247 } else {
248 return REPEAT_FIRST;
249 }
250 }
251
252 if (repeatMin == depth(0) || is_reset) {
253 return REPEAT_LAST;
254 }
255
256 // Cases with max < 64 can be handled with either bitmap or trailer. We use
257 // whichever has smaller packed state.
258
259 if (repeatMax < depth(64)) {
260 u32 bitmap_len =
261 packedSize(REPEAT_BITMAP, repeatMin, repeatMax, minPeriod);
262 u32 trailer_len =
263 packedSize(REPEAT_TRAILER, repeatMin, repeatMax, minPeriod);
264 return bitmap_len <= trailer_len ? REPEAT_BITMAP : REPEAT_TRAILER;
265 }
266
267 if (repeatMin <= depth(64)) {
268 return REPEAT_TRAILER;
269 }
270
271 u32 range_len = ~0U;
272 if (repeatMax > repeatMin &&
273 numRangeSlots(repeatMin, repeatMax) <= REPEAT_RANGE_MAX_SLOTS) {
274 assert(numRangeSlots(repeatMin, repeatMax) < 256); // stored in u8
275 range_len =
276 streamStateSize(REPEAT_RANGE, repeatMin, repeatMax, minPeriod);
277 }
278
279 assert(repeatMax.is_finite());
280
281 u32 sparse_len = ~0U;
282 if (minPeriod > 6) {
283 sparse_len =
284 streamStateSize(REPEAT_SPARSE_OPTIMAL_P, repeatMin, repeatMax, minPeriod);
285 }
286
287 if (range_len != ~0U || sparse_len != ~0U) {
288 return range_len < sparse_len ? REPEAT_RANGE : REPEAT_SPARSE_OPTIMAL_P;
289 }
290
291 return REPEAT_RING;
292}
293
294bool matches(vector<CharReach>::const_iterator a_it,
295 vector<CharReach>::const_iterator a_ite,
296 vector<CharReach>::const_iterator b_it,
297 UNUSED vector<CharReach>::const_iterator b_ite) {
298 for (; a_it != a_ite; ++a_it, ++b_it) {
299 assert(b_it != b_ite);
300 if ((*a_it & *b_it).none()) {
301 return false;
302 }
303 }
304 assert(b_it == b_ite);
305 return true;
306}
307
308static
309u32 minDistAfterA(const vector<CharReach> &a, const vector<CharReach> &b) {
310 /* we do not count the case where b can end at the same position as a */
311
312 for (u32 i = 1; i < b.size(); i++) {
313 u32 overlap_len = b.size() - i;
314 if (overlap_len <= a.size()) {
315 if (matches(a.end() - overlap_len, a.end(),
316 b.begin(), b.end() - i)) {
317 return i;
318 }
319 } else {
320 assert(overlap_len > a.size());
321 if (matches(a.begin(), a.end(),
322 b.end() - i - a.size(), b.end() - i)) {
323 return i;
324 }
325 }
326 }
327
328 return b.size();
329}
330
331vector<size_t> minResetDistToEnd(const vector<vector<CharReach>> &triggers,
332 const CharReach &cr) {
333 /* if a trigger does not reset the repeat, it gets a distance of trigger
334 length */
335 vector<size_t> out;
336 for (const auto &trig : triggers) {
337 size_t size = trig.size();
338 size_t i = 0;
339 for (; i < size; i++) {
340 if ((trig[size - i - 1] & cr).none()) {
341 break;
342 }
343 }
344 out.push_back(i);
345 }
346
347 return out;
348}
349
350#if defined(DEBUG) || defined(DUMP_SUPPORT)
351
352static UNUSED
353string dumpTrigger(const vector<CharReach> &trigger) {
354 string s;
355 for (const auto &cr : trigger) {
356 s += describeClass(cr);
357 }
358 return s;
359}
360
361#endif
362
363u32 minPeriod(const vector<vector<CharReach>> &triggers, const CharReach &cr,
364 bool *can_reset) {
365 assert(!triggers.empty());
366
367 u32 rv = ~0U;
368 *can_reset = true;
369 vector<size_t> min_reset_dist = minResetDistToEnd(triggers, cr);
370
371 for (const auto &trigger : triggers) {
372 DEBUG_PRINTF("trigger: %s\n", dumpTrigger(trigger).c_str());
373 for (size_t j = 0; j < triggers.size(); j++) {
374 u32 min_ext = minDistAfterA(trigger, triggers[j]);
375 rv = min(rv, min_ext);
376 if (min_ext <= min_reset_dist[j]) {
377 *can_reset = false;
378 }
379 }
380 }
381
382 DEBUG_PRINTF("min period %u\n", rv);
383 return rv;
384}
385
386} // namespace ue2
387