1 /*
2 * Copyright 2020 The Netty Project
3 *
4 * The Netty Project licenses this file to you under the Apache License, version 2.0 (the
5 * "License"); you may not use this file except in compliance with the License. You may obtain a
6 * copy of the License at:
7 *
8 * https://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software distributed under the License
11 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
12 * or implied. See the License for the specific language governing permissions and limitations under
13 * the License.
14 */
15 package io.netty.buffer.search;
16
17 import io.netty.util.internal.PlatformDependent;
18
19 /**
20 * Implements <a href="https://en.wikipedia.org/wiki/Bitap_algorithm">Bitap</a> string search algorithm.
21 * Use static {@link AbstractSearchProcessorFactory#newBitapSearchProcessorFactory}
22 * to create an instance of this factory.
23 * Use {@link BitapSearchProcessorFactory#newSearchProcessor} to get an instance of {@link io.netty.util.ByteProcessor}
24 * implementation for performing the actual search.
25 * @see AbstractSearchProcessorFactory
26 */
27 public class BitapSearchProcessorFactory extends AbstractSearchProcessorFactory {
28
29 private final long[] bitMasks = new long[256];
30 private final long successBit;
31
32 public static class Processor implements SearchProcessor {
33
34 private final long[] bitMasks;
35 private final long successBit;
36 private long currentMask;
37
38 Processor(long[] bitMasks, long successBit) {
39 this.bitMasks = bitMasks;
40 this.successBit = successBit;
41 }
42
43 @Override
44 public boolean process(byte value) {
45 currentMask = ((currentMask << 1) | 1) & PlatformDependent.getLong(bitMasks, value & 0xffL);
46 return (currentMask & successBit) == 0;
47 }
48
49 @Override
50 public void reset() {
51 currentMask = 0;
52 }
53 }
54
55 BitapSearchProcessorFactory(byte[] needle) {
56 if (needle.length > 64) {
57 throw new IllegalArgumentException("Maximum supported search pattern length is 64, got " + needle.length);
58 }
59
60 long bit = 1L;
61 for (byte c: needle) {
62 bitMasks[c & 0xff] |= bit;
63 bit <<= 1;
64 }
65
66 successBit = 1L << (needle.length - 1);
67 }
68
69 /**
70 * Returns a new {@link Processor}.
71 */
72 @Override
73 public Processor newSearchProcessor() {
74 return new Processor(bitMasks, successBit);
75 }
76
77 }