SidIdV2.java
package libsidutils.sidid;
import libsidutils.stringsearch.BNDMWildcards;
import java.io.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Locale;
import java.util.StringTokenizer;
import static java.nio.charset.StandardCharsets.UTF_8;
/**
* Scan tune files to find out the player ID. A configuration file is used with patterns of well-known players.
*
* @author Ken Händel
*
*/
public final class SidIdV2 extends SidIdBase {
/**
* This is a single pattern to match a player.
*
* @author Ken Händel
*
*/
private static class Pattern {
/**
* Pattern to search for.
*/
private final byte[] pattern;
/**
* Pre-processed search pattern.
*/
private final Object preProcessedPattern;
/**
* Is this a split sub pattern to match?
*/
private final boolean isSubPattern;
/**
* Create a new pattern.
*
* @param p pattern of the player
* @param pre pre-processed pattern
* @param subPattern Is this a split sub pattern to match?
*/
public Pattern(final byte[] p, final Object pre, final boolean subPattern) {
this.pattern = p;
this.preProcessedPattern = pre;
this.isSubPattern = subPattern;
}
/**
* Get a search pattern.
*
* @return pattern of the player
*/
public byte[] getPattern() {
return pattern;
}
/**
* Get a pre-processed search pattern.
*
* @return pre-processed pattern
*/
public Object getPreProcessedPattern() {
return preProcessedPattern;
}
/**
* Is this a split sub pattern to match?
*
* @return true -for sub-patterns, else false
*/
public boolean isSubPattern() {
return isSubPattern;
}
}
/**
* Player section of the SID-ID configuration file.
*
* @author Ken Händel
*
*/
private static class PlayerSection {
/**
* Player name.
*/
private final String playerName;
/**
* Patterns to match.<BR> OR(AND(bytes, ...), ...)
*/
private final ArrayList<ArrayList<Pattern>> orList;
/**
* Create a new section. This creates the pattern lists, also.
*
* @param name player name
*/
public PlayerSection(final String name) {
this.playerName = name;
this.orList = new ArrayList<>();
this.orList.add(new ArrayList<>());
}
/**
* Get the players' name.
*
* @return player name
*/
public final String getPlayerName() {
return playerName;
}
/**
* Get a pattern list: OR(AND(bytes, ...), ...).
*
* @return pattern list
*/
public final ArrayList<ArrayList<Pattern>> getOrList() {
return orList;
}
}
/**
* Package of the internal configuration file.
*/
private static final String SID_ID_PKG = "libsidutils/sidid/";
/**
* Name of the configuration file.
*/
private static final String FNAME = "sidid.cfg";
/**
* Integer base for hexadecimals.
*/
private static final int HEX_RADIX = 16;
/**
* Maximum pattern length.
*/
private static final int MAX_KEY_LENGTH = 32;
/**
* Search algorithm to be used.
*/
private final BNDMWildcards search;
/**
* Configuration sections.
*/
private ArrayList<PlayerSection> sections = new ArrayList<>();
/**
* Scan multiple times.
*/
private boolean multiScan;
/**
* Scan the file for multiple player IDs.
*
* @param m on/off multi scan
*/
public void setMultiScan(final boolean m) {
this.multiScan = m;
}
/**
* Constructor. Enable use of the BNDM algorithm.
*/
public SidIdV2() {
search = new BNDMWildcards();
}
/**
* Search player ID of a tune file.
*
* @param filename file name
* @return list of players (depending on multiScan one or more entries)
* @throws IOException read error
*/
public ArrayList<String> identify(final String filename) throws IOException {
return identify(load(filename));
}
/**
* Search player ID of a program.
*
* @param prg program to identify
* @return list of players (depending on multiScan one or more entries)
*/
public ArrayList<String> identify(final byte[] prg) {
final ArrayList<String> result = new ArrayList<>();
for (final PlayerSection section : sections) {
if (matchOneOf(section.getOrList(), prg)) {
result.add(section.getPlayerName());
if (!multiScan) {
return result;
}
}
}
return result;
}
/**
* Match one of the patterns in the list.
*
* @param orList the list of patterns to match
* @param prg the byte array containing the text
* @return true - one of the patterns has matched, false otherwise
*/
private boolean matchOneOf(final ArrayList<ArrayList<Pattern>> orList, final byte[] prg) {
for (final ArrayList<Pattern> andList : orList) {
if (matchAllOf(andList, prg)) {
return true;
}
}
return false;
}
/**
* Match all patterns in the list.
*
* @param andList the list of patterns to match
* @param prg the byte array containing the text
* @return true - all patterns have matched, false otherwise
*/
private boolean matchAllOf(final ArrayList<Pattern> andList, final byte[] prg) {
int prgOffset = 0;
for (final Pattern pattern : andList) {
// Determine the range to search for
int prgEnd = prg.length - prgOffset;
if (pattern.isSubPattern()) {
// A sub pattern is expected to be exactly behind the last match
// This is forced here, by reducing the search area!
prgEnd = prgOffset + pattern.getPattern().length;
if (prgEnd > prg.length) {
return false;
}
}
// search for the pattern
final int index = search.searchBytes(prg, prgOffset, prgEnd, pattern.getPattern(),
pattern.getPreProcessedPattern());
if (index == -1) {
// not found
return false;
}
// XXX Next search is done behind the last occurrence.
// So, The patterns have to be sorted according to their expected
// memory location. This is true at least for split sub-patterns
// of the maximum pattern length, but maybe not for all SID-ID
// entries.
prgOffset = index + pattern.getPattern().length;
}
return true;
}
/**
* Read the configuration file and configure the SID-ID class.
*
* @throws IOException I/O error
*/
public void readconfig() throws NumberFormatException, IOException {
readconfig(readConfiguration(FNAME, SID_ID_PKG));
}
/**
* Read the configuration file and configure the SID-ID class.
*
* @throws IOException configuration file read error
* @throws NumberFormatException error in number format
*/
public void readconfig(byte[] sidIdCfgBin) throws NumberFormatException, IOException {
sections = new ArrayList<>();
PlayerSection section = null;
final ArrayList<Byte> byteList = new ArrayList<>();
String line;
final BufferedReader br = new BufferedReader(
new InputStreamReader(new ByteArrayInputStream(sidIdCfgBin), UTF_8));
nextLine:
while ((line = br.readLine()) != null) {
if (line.isEmpty()) {
continue;
}
final StringTokenizer stok = new StringTokenizer(line, " ");
while (stok.hasMoreTokens()) {
final String origToken = stok.nextToken();
final String token = origToken.toLowerCase(Locale.ENGLISH);
if (!token.isEmpty()) {
if ("??".equals(token)) {
// Add wild-card
byteList.add((byte) '?');
} else if ("end".equals(token)) {
assert section != null;
// logical AND of last read bytes
andBytes(section, byteList);
// Append a new orList entry for further contents
final ArrayList<Pattern> orList = new ArrayList<>();
section.getOrList().add(orList);
continue nextLine;
} else if ("and".equals(token) || "&&".equals(token)) {
assert section != null;
// logical AND of last read bytes
andBytes(section, byteList);
} else if (token.length() == 2) {
// Add hex value
byteList.add(Integer.valueOf(token, HEX_RADIX).byteValue());
} else {
// Create a new player section
if (section != null) {
// the last section is always empty. (refer to
// "end")
section.getOrList().remove(section.getOrList().size() - 1);
}
section = new PlayerSection(origToken);
sections.add(section);
continue nextLine;
}
}
}
// logical AND of last read bytes
andBytes(section, byteList);
// Append a new orList entry for further contents
final ArrayList<Pattern> orList = new ArrayList<>();
section.getOrList().add(orList);
}
if (section != null) {
// the last section is always empty. (refer to
// "end")
section.getOrList().remove(section.getOrList().size() - 1);
}
}
/**
* Add all bytes of the byte list to the last element of the orList.
*
* @param section the current section
* @param byteList the bytes to add
*/
private void andBytes(final PlayerSection section, final ArrayList<Byte> byteList) {
// get last orList entry
final ArrayList<Pattern> lastOr = section.getOrList().get(section.getOrList().size() - 1);
// If patterns exceed the maximum pattern length,
// create logical ANDed sup-patterns
int byteListOffset = 0;
int byteCount = byteList.size();
boolean isSubPattern = false;
while (byteCount > MAX_KEY_LENGTH) {
// add up to the maximum pattern length
andBytesMaxPtnLength(lastOr, byteList, byteListOffset, MAX_KEY_LENGTH, isSubPattern);
byteCount -= MAX_KEY_LENGTH;
byteListOffset += MAX_KEY_LENGTH;
isSubPattern = true;
}
// add the remaining bytes to the last entry (AND)
andBytesMaxPtnLength(lastOr, byteList, byteListOffset, byteCount, isSubPattern);
// empty read bytes
byteList.clear();
}
/**
* Add a pattern to the pattern search list.
*
* @param ptnList the pattern list to add a new pattern for
* @param byteList the list of bytes to add
* @param byteListOffset Current offset of the bytes to add
* @param byteCount length of bytes to add (will become the search pattern length and must not exceed the
* maximum pattern length)
* @param isSubPattern is this a split sub-pattern?
*/
private void andBytesMaxPtnLength(final ArrayList<Pattern> ptnList, final ArrayList<Byte> byteList,
final int byteListOffset, final int byteCount, final boolean isSubPattern) {
assert byteCount <= MAX_KEY_LENGTH;
final byte[] and = new byte[byteCount];
for (int i = 0; i < and.length; i++) {
and[i] = byteList.get(i + byteListOffset);
}
ptnList.add(new Pattern(and, search.processBytes(and, (byte) '?'), isSubPattern));
}
}