Boolean Function

Boolean functions are used to represent the functionality of each gate within the netlist. HAL enables the reverse engineer to operate upon these functions by providing a set of functions to extend, optimize, and evaluate them. In general, they consist of a set of variables that are connected using Boolean operators.

Accessing Boolean Functions

If available, the user can retrieve the Boolean functions of a gate by using get_boolean_function and get_boolean_functions respectively. While the first command requires the name of the desired Boolean function as input, the latter simply returns a list of all available Boolean functions.

gate = netlist.get_gate_by_id(1)                # get gate with ID 1
func = gate.get_boolean_function("func_name")   # return only the Boolean function specified by "func_name"
func_list = gate.get_boolean_functions()        # return a list of all Boolean functions of that gate

While for most gates the Boolean functions are actually associated with their gate type, some special gates like LUTs may feature individual functions independent of their gate type. Hence, we recommend always retrieving the Boolean function of a gate from the gate itself and not its gate type, despite the gate type offering similar functionality.

Creating Boolean Functions

The reverse engineer may also create new Boolean functions by constructing them from a string as follows:

func = hal_py.BooleanFunction.from_string("(A & B) + C").  # constructs a Boolean function object from string

In general, Boolean functions support NOT ("!", "'"), AND ("&", "*", " "), OR ("|", "+"), and XOR ("^") operations as well as brackets ("(", ")") when being parsed from a string. If any of the variables used within the function contains brackets, it is required to additionally specify the variable names of the function as follows:

func = hal_py.BooleanFunction.from_string("A(1) & A(2)", ["A(1)", "A(2)"])

The string representation of a Boolean function is available via the str function. To print a Boolean function, it suffices to call print on the function itself.

func_str = str(func)   # returns the string representation of the Boolean function
print(func)            # prints the Boolean function

In addition to the construction from a string, Boolean functions can also be composed by using their constructors and provided operators. By calling the Boolean function constructor on a string like "A", a Boolean function containing only that variable is constructed. To construct a constant Boolean function, the enum Value may be used instead.

func_A = hal_py.BooleanFunction("A")                                # Boolean function containing only variable A
func_1 = hal_py.BooleanFunction(hal_py.BooleanFunction.Value.ONE)   # constant 1

Combining Boolean Functions

Two Boolean functions can be joined using the &, |, and ^ operators and negated using the ~ operator. Most of these operations are also available in-place.

func_A = hal_py.BooleanFunction("A")                                # Boolean function containing only variable A
func_B = hal_py.BooleanFunction("B")                                # Boolean function containing only variable B
func_1 = hal_py.BooleanFunction(hal_py.BooleanFunction.Value.ONE)   # constant 1
nand_func = ~(func_A & func_B)                                      # build a NAND from A and B
nand_func |= func_1                                                 # in-place OR

Additionally, two Boolean functions may also be combined by replacing a variable in one function with the other function using substitute. This allows to retrieve the combined Boolean function of gates that are connected in series. Combining two Boolean functions in this way may require the renaming of some variables before substitution. In the example below, func_1 represents the function of an OR gate, while func_2 gives the function of an AND gate. Both gates use the variables "A"and "B" as inputs, although they are not connected to the same net and may thus have different values. Therefore, when replacing "B" of func_1 with func_2, at least "A" of func_2 should be renamed.

func_1 = hal_py.BooleanFunction.from_string("A + B")   # create OR function
func_2 = hal_py.BooleanFunction.from_string("A & B")   # create AND function
func_2 = func_2.substitute("A", "C")                   # rename "A" of func_2 to "C"
func_1 = func_1.substitute("B", func_2)                # substitute "B" of func_1 with func_2
print(func_1)                                          # prints "A + (C & B)"

Note: For more information on how to combine multiple gates and generate a Boolean Function depending on multiple gates and inputs, have a look at the netlist utilities class

Optimizing Boolean Functions

A Boolean function may be optimized by either converting it to disjunctive normale form (DNF) using to_dnf or applying the Quine-McCluskey algorithm using optimize. Furthermore, is_dnf can be used to verify whether a function is already in DNF.

Warning: The runtime of optimize depends on the the underlying Quine–McCluskey algorithm (QMC), which may be exponential in the number of variables, so be careful with the Boolean functions you provide it with.

func_dnf = func.to_dnf()
func_opt = func.optimize()

Evaluating Boolean Functions

Evaluation of a Boolean function can be done using the evaluate function. It takes a dict from variable names to values as input and outputs the result. Values are always given using the Value enum. Furthermore, the functions is_constant_one and is_constant_zero can be used to determine whether a Boolean function always returns a constant output.

func = hal_py.BooleanFunction.from_string("A & B")                                                       # create Boolean function
res = func.evaluate({"A" : hal_py.BooleanFunction.Value.ONE, "B" : hal_py.BooleanFunction.Value.ZERO})   # return hal_py.BooleanFunction.Value.ZERO
const_one = func.is_constant_one()                                                                       # return false

Finally, get_truth_table may be used to generate the truth table outputs of a Boolean function. If provided with a list of variables, the truth table is generated using the variable order of that list for the inputs. Otherwise, the variables are ordered alphabetically.

Warning: The runtime of get_truth_table is exponential in the number of variables by nature, so be careful with the Boolean functions you provide it with.

func = hal_py.BooleanFunction.from_string("(A + B) & C")   # create Boolean function
tt_alph = func.get_truth_table()                           # get truth table outputs for input order A, B, C
tt_cust = func.get_truth_table(["A", "C", "B"])            # get truth table outputs for input order A, C, B