from FPGA Resources by GateForge Consulting Ltd.

In Hacker's Delight, Section
2-12, *How the Computer Sets the Comparison Predicates*, Henry S. Warren
Jr. describes how to compute all the integer comparisons, based on the
condition flags generated after a (2's-complement) subtraction *x - y*,
which I reproduce below.

Given the following four condition flags after computing *x - y*:

- C
_{o}: Carry out of the MSB (Most-Significant Bit) - C
_{i}: Carry into the MSB - N: sign bit of the result
- Z: 1 if result is zero, regardless of C
_{o}

We can compute all the integer comparisons like so:

Comparison | Calculation | Notes |
---|---|---|

V | C_{i} ⊕ C_{o} | signed overflow |

x = y: | Z | |

x ≠ y | ¬Z | |

x < y | N ⊕ V | |

x ≤ y | (N ⊕ V) ∨ Z | |

x > y | (N ≡ V) ∧ ¬Z | ≡ means XNOR |

x ≥ y | N ≡ V | |

x < y | ¬C_{o} | unsigned |

x ≤ y | ¬C_{o} ∨ Z | unsigned |

x > y | C_{o} ∧ ¬Z | unsigned |

x ≥ y | C_{o} | unsigned |

It so happens that we can arrange the four basic conditions as two groups, A and B, where a Boolean combination of any pair with one member from from each group suffices to reconstruct all the integer comparisons:

- Group A contains N (Negative) and Z (Zero)
- Group B contains C
_{o}(Carry-out) and N⊕V (Less-Than)

But in a modern FPGA, 4:1 multiplexers naturally map 1:1 onto 6-LUTs (6-input Look-Up Tables), so we can extend groups A and B to contain more kinds of conditions commonly encountered in software, which we can now check with programmable hardware: checks for sentinel values (e.g.: the string-terminating NULL), counters (e.g.: counted loops, software timers), and external inputs (e.g.: test an input pin). The external inputs also act as a generic place to add special conditions, or for chaining previous predicate calculations.

The groups now are:

- Group A contains N (Negative), C
_{o}(Carry-out), a Sentinel flag (SV_{1p}), and an External input (I_{1}). - Group B contains N⊕V (Less-Than), a Counter flag (CTR
_{p}), a Sentinel flag (SV_{2p}), and an External input (I_{2}).

Selecting from 4 inputs each requires 2 bits, plus 4 bits to select one of the 16 possible dyadic Boolean operations, resulting in 256 possible comparisons. There is some redundancy: 16 cases always output 0 or 1 so we keep 2 for use, and 32 cases always output the selected member from A or B so we keep 8 for use (one per input condition), leaving us with 202 non-redundant comparison predicates (CP).

*It's interesting to think of the non-redundant fraction of the possible
outputs of a logic circuit as a potential measure of its quality.
(This one sits at 202/256 = 0.789.)
Fewer redundant cases suggests a more "significant" computation.*

To implement this condition predicate calculator, we first need to define the conditions and operations (which remain constant anywhere, and so by convention are created as macros rather than parameters).

`ifndef CONDITION_PREDICATE_OPERATIONS `define CONDITION_PREDICATE_OPERATIONS // Never changes `define GROUP_SELECTOR_WIDTH 2 // First, the A/B group condition flag selectors `define A_GROUP_NEGATIVE 2'd0 `define A_GROUP_CARRYOUT 2'd1 `define A_GROUP_SENTINEL 2'd2 `define A_GROUP_EXTERNAL 2'd3 `define B_GROUP_LESSTHAN 2'd0 `define B_GROUP_COUNTER 2'd1 `define B_GROUP_SENTINEL 2'd2 `define B_GROUP_EXTERNAL 2'd3 // Second, for the combining stage `include "Dyadic_Boolean_Operations.vh" `endif

Then is it simply a matter of instantiating two Addressed Multiplexers and one Universal Dyadic Boolean Operator. The resulting circuit consumes only three 6-LUTs, making quite small and fast. You can implement multiple instances to compute multiple arbitrary comparison predicates in parallel.

// Computes a true/false value based on a Boolean combination of selected // input conditional predicates, each selected from one of two groups. // (See Hacker's Delight, 2-12) `default_nettype none module Condition_Predicate ( input wire [`GROUP_SELECTOR_WIDTH-1:0] A_selector, input wire A_negative, input wire A_carryout, input wire A_sentinel, input wire A_external, input wire [`GROUP_SELECTOR_WIDTH-1:0] B_selector, input wire B_lessthan, input wire B_counter, input wire B_sentinel, input wire B_external, input wire [`DYADIC_CTRL_WIDTH-1:0] AB_operator, output wire predicate ); // -------------------------------------------------------------------- localparam WORD_WIDTH = 1; // Predicates are 1/0 // -------------------------------------------------------------------- wire selected_A; Addressed_Mux #( .WORD_WIDTH (WORD_WIDTH), .ADDR_WIDTH (`GROUP_SELECTOR_WIDTH), .INPUT_COUNT (2**`GROUP_SELECTOR_WIDTH) ) Select_A ( .addr (A_selector), .in ({A_external,A_sentinel,A_carryout,A_negative}), .out (selected_A) ); // -------------------------------------------------------------------- wire selected_B; Addressed_Mux #( .WORD_WIDTH (WORD_WIDTH), .ADDR_WIDTH (`GROUP_SELECTOR_WIDTH), .INPUT_COUNT (2**`GROUP_SELECTOR_WIDTH) ) Select_B ( .addr (B_selector), .in ({B_external,B_sentinel,B_counter,B_lessthan}), .out (selected_B) ); // -------------------------------------------------------------------- Dyadic_Boolean_Operator #( .WORD_WIDTH (WORD_WIDTH) ) AB_Combiner ( .op (AB_operator), .a (selected_A), .b (selected_B), .o (predicate) ); endmodule

fpgacpu.ca