diff options
Diffstat (limited to 'src/main/java/org/challman/pantheon_parser/algorithm/BooyerMoore.java')
| -rw-r--r-- | src/main/java/org/challman/pantheon_parser/algorithm/BooyerMoore.java | 194 |
1 files changed, 194 insertions, 0 deletions
diff --git a/src/main/java/org/challman/pantheon_parser/algorithm/BooyerMoore.java b/src/main/java/org/challman/pantheon_parser/algorithm/BooyerMoore.java new file mode 100644 index 0000000..1f05652 --- /dev/null +++ b/src/main/java/org/challman/pantheon_parser/algorithm/BooyerMoore.java @@ -0,0 +1,194 @@ +package org.challman.pantheon_parser.algorithm; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + + +public class BooyerMoore { + private final List<byte[]> patterns = new ArrayList<>(); + + public void addPattern(byte[] pattern) { + patterns.add(pattern); + } + + public void addPattern(String hexPattern) { + hexPattern = hexPattern.replaceAll("xx", "fe"); + addPattern(hexToBytes(hexPattern)); + } + + public List<MatchResult> search(byte[] data) { + List<MatchResult> results = new ArrayList<>(); + + for (byte[] pattern : patterns) { + for (int i = 0; i <= data.length - pattern.length; i++) { + boolean match = true; + for (int j = 0; j < pattern.length; j++) { + if (pattern[j] != (byte) 0xFE && data[i + j] != pattern[j]) { + match = false; + break; + } + } + if (match) { + results.add(new MatchResult(data, pattern, i, i + pattern.length - 1)); + i += pattern.length - 1; // Skip ahead to avoid overlapping matches + } + } + } + + return results; + } + + public static class MatchResult { + public final byte[] packet; + public final byte[] pattern; + public final int startIndex; + public final int endIndex; + + public MatchResult(byte[] packet, byte[] pattern, int startIndex, int endIndex) { + this.packet = packet; + this.pattern = pattern; + this.startIndex = startIndex; + this.endIndex = endIndex; + } + + @Override + public String toString() { + return String.format(bytesToHex(pattern)); + } + } + + // Utility methods + private static byte[] hexToBytes(String hex) { + hex = hex.replaceAll("\\s+", ""); + byte[] data = new byte[hex.length() / 2]; + for (int i = 0; i < data.length; i++) { + data[i] = (byte) Integer.parseInt(hex.substring(i * 2, i * 2 + 2), 16); + } + return data; + } + + private static String bytesToHex(byte[] bytes) { + StringBuilder sb = new StringBuilder(); + for (byte b : bytes) { + sb.append(String.format("%02x ", b)); + } + return sb.toString().trim(); + } +} +// +//public class BooyerMoore { +// private final List<PatternInfo> patterns = new ArrayList<>(); +// private static final byte WILDCARD = (byte) 0xFE; +// +// public void addPattern(byte[] pattern) { +// patterns.add(new PatternInfo(pattern, buildBadCharTable(pattern))); +// } +// +// public void addPattern(String hexPattern) { +// hexPattern = hexPattern.replaceAll("xx", "fe"); +// addPattern(hexToBytes(hexPattern)); +// } +// +// public List<MatchResult> search(byte[] data) { +// List<MatchResult> results = new ArrayList<>(); +// +// for (PatternInfo patternInfo : patterns) { +// int i = 0; +// while (i <= data.length - patternInfo.pattern.length) { +// int j = patternInfo.pattern.length - 1; +// +// // Check from right to left +// while (j >= 0 && (patternInfo.pattern[j] == WILDCARD || +// data[i + j] == patternInfo.pattern[j])) { +// j--; +// } +// +// if (j < 0) { +// // Match found +// results.add(new MatchResult(data, patternInfo.pattern, i, i + patternInfo.pattern.length - 1)); +// i += patternInfo.pattern.length; // Move to next position +// } else { +// // Use bad character rule to skip ahead +// int skip = patternInfo.badCharTable.getOrDefault(data[i + j], patternInfo.pattern.length); +// // If the pattern byte at mismatch position is wildcard, we can't skip +// if (patternInfo.pattern[j] == WILDCARD) { +// i += 1; // Just move one position +// } else { +// i += Math.max(1, skip - (patternInfo.pattern.length - 1 - j)); +// } +// } +// } +// } +// +// return results; +// } +// +// private Map<Byte, Integer> buildBadCharTable(byte[] pattern) { +// Map<Byte, Integer> table = new HashMap<>(); +// for (int i = 0; i < pattern.length - 1; i++) { +// if (pattern[i] != WILDCARD) { +// // Only add non-wildcard bytes to the table +// table.put(pattern[i], pattern.length - 1 - i); +// } +// } +// return table; +// } +// +// private static class PatternInfo { +// final byte[] pattern; +// final Map<Byte, Integer> badCharTable; +// +// PatternInfo(byte[] pattern, Map<Byte, Integer> badCharTable) { +// this.pattern = pattern; +// this.badCharTable = badCharTable; +// } +// } +// +// +// private static class Node { +// Map<Byte, Node> children = new HashMap<>(); +// Node failure = null; +// boolean isEnd = false; +// List<byte[]> patterns = new ArrayList<>(); +// List<byte[]> output = new ArrayList<>(); +// } +// +// public static class MatchResult { +// public final byte[] packet; +// public final byte[] pattern; +// public final int startIndex; +// public final int endIndex; +// +// public MatchResult(byte[] packet, byte[] pattern, int startIndex, int endIndex) { +// this.packet = packet; +// this.pattern = pattern; +// this.startIndex = startIndex; +// this.endIndex = endIndex; +// } +// +// @Override +// public String toString() { +// return String.format(bytesToHex(pattern)); +// } +// } +// +// // Utility methods +// private static byte[] hexToBytes(String hex) { +// hex = hex.replaceAll("\\s+", ""); +// byte[] data = new byte[hex.length() / 2]; +// for (int i = 0; i < data.length; i++) { +// data[i] = (byte) Integer.parseInt(hex.substring(i * 2, i * 2 + 2), 16); +// } +// return data; +// } +// +// private static String bytesToHex(byte[] bytes) { +// StringBuilder sb = new StringBuilder(); +// for (byte b : bytes) { +// sb.append(String.format("%02x ", b)); +// } +// return sb.toString().trim(); +// } +//}
\ No newline at end of file |