Ghidra is a software reverse engineering (SRE) framework
/* ###
* IP: GHIDRA
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package db;
import java.util.*;
import org.apache.commons.lang3.ArrayUtils;
import db.Field.UnsupportedFieldException;
import ghidra.util.exception.AssertException;
/**
* Class for definining the columns in a Ghidra Database table.
*/
public class Schema {
private static final String NAME_SEPARATOR = ";";
static final byte FIELD_EXTENSION_INDICATOR = -1;
private static final byte SPARSE_FIELD_LIST_EXTENSION = 1;
private int version;
private Field keyType;
private String keyName;
private Field[] fields;
private String[] fieldNames;
private Set<Integer> sparseColumnSet;
private boolean isVariableLength;
private int fixedLength;
private boolean forceUseVariableLengthKeyNodes;
/**
* Construct a new Schema.
* @param version schema version
* @param keyField field associated with primary key (representative instance)
* @param keyName primary key name
* @param fields array of column fields (representative instances)
* @param fieldNames array of column field names
* @param sparseColumns column indexes corresponding to those
* columns which utilize sparse storage (null if no sparse columns).
* Valid sparse column indexes are in the range 0..127.
* @throws IllegalArgumentException invalid parameters
*/
public Schema(int version, Field keyField, String keyName, Field[] fields,
String[] fieldNames, int[] sparseColumns) {
this.version = version;
this.keyType = keyField;
this.keyName = keyName;
this.fields = fields;
this.fieldNames = fieldNames;
if (fields.length != fieldNames.length) {
throw new IllegalArgumentException("fieldNames and fields lengths differ");
}
isVariableLength = false;
fixedLength = 0;
for (int colIndex = 0; colIndex < fields.length; colIndex++) {
Field field = fields[colIndex];
if (field.isVariableLength()) {
isVariableLength = true;
}
fixedLength += field.length();
if (fieldNames[colIndex].indexOf(NAME_SEPARATOR) >= 0) {
throw new IllegalArgumentException("field names may not contain ';'");
}
}
try {
initializeSparseColumnSet(ArrayUtils.toObject(sparseColumns));
}
catch (UnsupportedFieldException e) {
throw new IllegalArgumentException(e);
}
if (isVariableLength) {
fixedLength = 0;
}
}
/**
* Construct a new Schema.
* @param version schema version
* @param keyField field associated with primary key (representative instance)
* @param keyName primary key name
* @param fields array of column fields (representative instances)
* @param fieldNames array of column field names
* @throws IllegalArgumentException invalid parameters
*/
public Schema(int version, Field keyField, String keyName, Field[] fields,
String[] fieldNames) {
this(version, keyField, keyName, fields, fieldNames, null);
}
/**
* Construct a new Schema which uses a long key.
* @param version schema version
* @param keyName primary key name
* @param fields array of column fields (representative instances)
* @param fieldNames array of column field names
* @throws IllegalArgumentException invalid parameters
*/
public Schema(int version, String keyName, Field[] fields, String[] fieldNames) {
this(version, LongField.INSTANCE, keyName, fields, fieldNames, null);
}
/**
* Construct a new Schema which uses a long key.
* @param version schema version
* @param keyName primary key name
* @param fields array of column fields (representative instances)
* @param fieldNames array of column field names
* @param sparseColumns column indexes corresponding to those
* columns which utilize sparse storage (null if no sparse columns).
* Valid sparse column indexes are in the range 0..127.
* @throws IllegalArgumentException invalid parameters
*/
public Schema(int version, String keyName, Field[] fields, String[] fieldNames,
int[] sparseColumns) {
this(version, LongField.INSTANCE, keyName, fields, fieldNames, sparseColumns);
}
/**
* Construct a new Schema.
* @param version schema version
* @param keyClass field class associated with primary key
* @param keyName primary key name
* @param fieldClasses array of column field classes
* @param fieldNames array of column field names
* @throws IllegalArgumentException invalid parameters
*/
public Schema(int version, Class<?> keyClass, String keyName, Class<?>[] fieldClasses,
String[] fieldNames) {
this(version, getField(keyClass), keyName, getFields(fieldClasses), fieldNames, null);
}
/**
* Construct a new Schema.
* @param version schema version
* @param keyClass field class associated with primary key
* @param keyName primary key name
* @param fieldClasses array of column field classes
* @param fieldNames array of column field names
* @param sparseColumns column indexes corresponding to those
* columns which utilize sparse storage (null if no sparse columns).
* Valid sparse column indexes are in the range 0..127.
* @throws IllegalArgumentException invalid parameters
*/
public Schema(int version, Class<?> keyClass, String keyName, Class<?>[] fieldClasses,
String[] fieldNames, int[] sparseColumns) {
this(version, getField(keyClass), keyName, getFields(fieldClasses), fieldNames,
sparseColumns);
}
/**
* Construct a new Schema which uses a long key.
* @param version schema version
* @param keyName primary key name
* @param fieldClasses array of column field classes
* @param fieldNames array of column field names
* @throws IllegalArgumentException invalid parameters
*/
public Schema(int version, String keyName, Class<?>[] fieldClasses, String[] fieldNames) {
this(version, LongField.INSTANCE, keyName, getFields(fieldClasses), fieldNames, null);
}
/**
* Construct a new Schema which uses a long key.
* @param version schema version
* @param keyName primary key name
* @param fieldClasses array of column field classes
* @param fieldNames array of column field names
* @param sparseColumns column indexes corresponding to those
* columns which utilize sparse storage (null if no sparse columns).
* Valid sparse column indexes are in the range 0..127.
* @throws IllegalArgumentException invalid parameters
*/
public Schema(int version, String keyName, Class<?>[] fieldClasses, String[] fieldNames,
int[] sparseColumns) {
this(version, LongField.INSTANCE, keyName, getFields(fieldClasses), fieldNames,
sparseColumns);
}
/**
* Construct a Schema based upon encoded
* @param version schema version
* @param encodedKeyFieldType key field type
* @param encodedFieldTypes encoded field types array.
* @param packedFieldNames packed list of field names separated by ';'.
* The first field name corresponds to the key name.
* @throws UnsupportedFieldException if unsupported fieldType specified
*/
Schema(int version, byte encodedKeyFieldType, byte[] encodedFieldTypes, String packedFieldNames)
throws UnsupportedFieldException {
this.version = version;
this.keyType = Field.getField(encodedKeyFieldType);
parseNames(packedFieldNames);
isVariableLength = false;
fixedLength = 0;
initializeFields(encodedFieldTypes); // initializes fields and sparseColumns
if (fieldNames.length != fields.length) {
throw new IllegalArgumentException("fieldNames and column types differ in length");
}
}
/**
* Determine if schema employs sparse column storage
* @return true if schema employs sparse column storage
*/
public boolean hasSparseColumns() {
return sparseColumnSet != null;
}
/**
* Determine if the specified column index has been designated as a sparse
* column within the associated record storage
* @param columnIndex column index
* @return true if designated column uses sparse storage
*/
public boolean isSparseColumn(int columnIndex) {
return sparseColumnSet != null && sparseColumnSet.contains(columnIndex);
}
/**
* Initialize field types and related field extensions (e.g., sparse field list).
* The presence of field extensions within the encodedFieldTypes is indicated by a
* -1 (field extension indicator) following the encoded field types.
* The byte value following the field extension indicator
* is the extension type which is followed by the extension data if applicable.
* A -1 byte is used to separate each extension byte sequence.
* @param encodedFieldTypes encoded field type data
* @throws UnsupportedFieldException if decoding of the encodedFieldTypes fails
*/
private void initializeFields(byte[] encodedFieldTypes) throws UnsupportedFieldException {
if (encodedFieldTypes.length == 0) {
fields = new Field[0];
return;
}
int index = 0;
ArrayList<Field> fieldList = new ArrayList<>();
while (index < encodedFieldTypes.length) {
byte b = encodedFieldTypes[index++];
if (b == FIELD_EXTENSION_INDICATOR) {
break;
}
Field f = Field.getField(b);
fieldList.add(f);
if (f.isVariableLength()) {
isVariableLength = true;
}
fixedLength += f.length();
}
fields = fieldList.toArray(new Field[fieldList.size()]);
while (index < encodedFieldTypes.length) {
int extensionType = encodedFieldTypes[index++];
if (extensionType == SPARSE_FIELD_LIST_EXTENSION) {
index += parseSparseColumnIndexes(encodedFieldTypes, index);
}
else {
throw new UnsupportedFieldException(
"Unsupported field extension type: " + extensionType);
}
}
if (isVariableLength) {
fixedLength = 0;
}
}
private void initializeSparseColumnSet(Integer[] sparseColumns) throws UnsupportedFieldException {
if (sparseColumns == null || sparseColumns.length == 0) {
return;
}
Set<Integer> builder = new HashSet<>();
for (int i : sparseColumns) {
if (i < 0 || i > Byte.MAX_VALUE || i >= fields.length) {
throw new UnsupportedFieldException("Sparse column entry out of range: " + i);
}
builder.add(i);
}
sparseColumnSet = Set.copyOf(builder);
if (sparseColumnSet.size() != sparseColumns.length) {
throw new UnsupportedFieldException("Sparse column set contains duplicate entry");
}
isVariableLength = true; // sparse records are variable length
}
/**
* Parse the sparse column indexes contained within the encodedFieldTypes data
* @param encodedFieldTypes encoded data bytes
* @param index of first extension data byte within encodedFieldTypes array
* @return number of encoded data bytes consumed
*/
private int parseSparseColumnIndexes(byte[] encodedFieldTypes, int index)
throws UnsupportedFieldException {
try {
int consumed = 0;
ArrayList<Integer> columnIndexes = new ArrayList<>();
while (index < encodedFieldTypes.length &&
encodedFieldTypes[index] != FIELD_EXTENSION_INDICATOR) {
columnIndexes.add((int) encodedFieldTypes[index++]);
++consumed;
}
Integer[] sparseColumns = columnIndexes.toArray(new Integer[columnIndexes.size()]);
initializeSparseColumnSet(sparseColumns);
return consumed;
}
catch (IndexOutOfBoundsException e) {
throw new UnsupportedFieldException("Incomplete sparse column data");
}
}
private static Field getField(Class<?> fieldClass) {
if (!Field.class.isAssignableFrom(fieldClass) || fieldClass == Field.class ||
IndexField.class.isAssignableFrom(fieldClass)) {
throw new IllegalArgumentException("Invalid Field class: " + fieldClass.getName());
}
try {
return (Field) fieldClass.getConstructor().newInstance();
}
catch (Exception e) {
throw new RuntimeException("Failed to construct: " + fieldClass.getName(), e);
}
}
private static Field[] getFields(Class<?>[] fieldClasses) {
Field[] fields = new Field[fieldClasses.length];
for (int i = 0; i < fieldClasses.length; i++) {
fields[i] = getField(fieldClasses[i]);
}
return fields;
}
/**
* Determine if this schema can use LongKeyNode's within a table.
* @return true if LongKeyNode's can be used to store records produced with this schema.
*/
boolean useLongKeyNodes() {
return !forceUseVariableLengthKeyNodes && keyType instanceof LongField;
}
/**
* Determine if this schema uses VarKeyNode's within a table.
* @return true if VarKeyNode's are be used to store records produced with this schema.
*/
boolean useVariableKeyNodes() {
return forceUseVariableLengthKeyNodes || keyType.isVariableLength();
}
/**
* Determine if this schema can use FixedKeyNode's within a table.
* @return true if FixedKeyNode's can be used to store records produced with this schema.
*/
boolean useFixedKeyNodes() {
return !useVariableKeyNodes() && !useLongKeyNodes();
}
/**
* Force use of variable-length key nodes.
* <br>
* This method provides a work-around for legacy schemas which
* employ primitive fixed-length keys other than LongField
* and improperly employ a variable-length-key storage schema.
* Although rare, this may be neccessary to ensure backward compatibility
* with legacy DB storage (example ByteField key employed by old table).
*/
void forceUseOfVariableLengthKeyNodes() {
forceUseVariableLengthKeyNodes = true;
}
/**
* Get the Field type for the key.
* @return key Field type
*/
public Field getKeyFieldType() {
return keyType;
}
/**
* Get the key name
* @return key name
*/
public String getKeyName() {
return keyName;
}
/**
* Get the list of data Field classes for this schema.
* The returned list is ordered consistent with the schema definition.
* @return data Field classes
*/
public Field[] getFields() {
return fields;
}
/**
* Get the list of data Field names for this schema.
* The returned list is ordered consistent with the schema definition.
* @return data Field names
*/
public String[] getFieldNames() {
return fieldNames;
}
/**
* Get the number of data Fields
* @return data Field count
*/
public int getFieldCount() {
return fields.length;
}
/**
* Parse the packed list of data Field names.
* The fieldNames array is initialized with the individual Field names.
* @param packedNames packed name list produced by the getPackedFieldNames() method.
*/
private void parseNames(String packedNames) {
ArrayList<String> nameList = new ArrayList<String>();
StringTokenizer st = new StringTokenizer(packedNames, NAME_SEPARATOR);
while (st.hasMoreElements()) {
nameList.add(st.nextToken());
}
keyName = nameList.remove(0);
fieldNames = new String[nameList.size()];
nameList.toArray(fieldNames);
}
/**
* Get the packed list of data Field names.
* @return packed name list.
*/
String getPackedFieldNames() {
StringBuffer buf = new StringBuffer();
buf.append(keyName);
buf.append(NAME_SEPARATOR);
for (String fieldName : fieldNames) {
buf.append(fieldName);
buf.append(NAME_SEPARATOR);
}
return buf.toString();
}
byte getEncodedKeyFieldType() {
return keyType.getFieldType();
}
/**
* Get the schema field types as an encoded byte array.
* @return byte[] field type list as an encoded byte array.
*/
byte[] getEncodedFieldTypes() {
ArrayList<Byte> encodedDataList = new ArrayList<>();
// add field type encodings
for (Field field : fields) {
encodedDataList.add(field.getFieldType());
}
// add sparse field extension data
if (sparseColumnSet != null) {
encodedDataList.add(FIELD_EXTENSION_INDICATOR);
encodedDataList.add(SPARSE_FIELD_LIST_EXTENSION);
for (int col : sparseColumnSet) {
encodedDataList.add((byte) col);
}
}
return ArrayUtils.toPrimitive(encodedDataList.toArray(Byte[]::new));
}
/**
* Get the schema version.
* @return schema version
*/
public int getVersion() {
return version;
}
/**
* Returns true if records for this Schema can be of variable lengths.
* @return true if records with this Schema are variable length.
*/
public boolean isVariableLength() {
return isVariableLength;
}
/**
* Get length of fixed-length schema record.
* @return record length or 0 for variable length.
*/
public int getFixedLength() {
return fixedLength;
}
/**
* Create an empty record for the specified key.
* @param key long key
* @return new record
*/
public DBRecord createRecord(long key) {
return createRecord(new LongField(key));
}
/**
* Create an empty record for the specified key.
* @param key record key field
* @return new record
*/
public DBRecord createRecord(Field key) {
return hasSparseColumns() ? new SparseRecord(this, key) : new DBRecord(this, key);
}
/**
* Get a new instance of a data Field object for the specified column.
* @param colIndex field index
* @return new Field object suitable for data reading/writing.
*/
Field getField(int colIndex) {
try {
return fields[colIndex].newField();
}
catch (Exception e) {
throw new AssertException(e.getMessage());
}
}
/**
* Compare two schemas for equality.
* Field names are ignored in this comparison. Instance variables such as {@link #fixedLength},
* {@link Schema#isVariableLength} and {@link #forceUseVariableLengthKeyNodes} are also ignored.
* @see java.lang.Object#equals(java.lang.Object)
*/
@Override
public boolean equals(Object obj) {
if (!(obj instanceof Schema)) {
return false;
}
Schema otherSchema = (Schema) obj;
if (version != otherSchema.version ||
!keyType.getClass().equals(otherSchema.keyType.getClass()) ||
fields.length != otherSchema.fields.length) {
return false;
}
for (int i = 0; i < fields.length; i++) {
if (!fields[i].getClass().equals(otherSchema.fields[i].getClass())) {
return false;
}
}
if (!Objects.equals(sparseColumnSet, otherSchema.sparseColumnSet)) {
return false;
}
return true;
}
@Override
public int hashCode() {
// Schemas are not intended to be hashed
return super.hashCode();
}
@Override
public String toString() {
StringBuilder buf = new StringBuilder();
buf.append(keyName);
buf.append("(key,");
buf.append(keyType.getClass().getSimpleName());
buf.append(")");
for (int i = 0; i < fieldNames.length; i++) {
buf.append("\n");
buf.append(fieldNames[i]);
buf.append("(");
buf.append(fields[i].getClass().getSimpleName());
buf.append(")");
}
return buf.toString();
}
}