/*********************************************************************
 *  The following code is part of the power modelling feature of VTR.
 *
 * For support:
 * http://code.google.com/p/vtr-verilog-to-routing/wiki/Power
 *
 * or email:
 * vtr.power.estimation@gmail.com
 *
 * If you are using power estimation for your researach please cite:
 *
 * Jeffrey Goeders and Steven Wilton.  VersaPower: Power Estimation
 * for Diverse FPGA Architectures.  In International Conference on
 * Field Programmable Technology, 2012.
 *
 ********************************************************************/

/**
 * This file provides functions relating to the cmos technology.  It
 * includes functions to read the transistor characteristics from the
 * xml file into data structures, and functions to search within
 * these data structures.
 */

/************************* INCLUDES *********************************/
#include <cstring>
#include "vtr_assert.h"

#include "pugixml.hpp"
#include "pugixml_util.hpp"

#include "vtr_util.h"
#include "vtr_memory.h"
#include "vtr_math.h"

#include "vpr_error.h"

#include "globals.h"
#include "power_cmos_tech.h"
#include "power.h"
#include "power_util.h"
#include "read_xml_util.h"
#include "PowerSpicedComponent.h"
#include "power_callibrate.h"

/************************* FILE SCOPE **********************************/
static t_transistor_inf* f_transistor_last_searched;
static t_power_buffer_strength_inf* f_buffer_strength_last_searched;
static t_power_mux_volt_inf* f_mux_volt_last_searched;
static t_power_nmos_leakage_inf* f_power_searching_nmos_leakage_info;

/************************* FUNCTION DECLARATIONS ********************/

static void power_tech_load_xml_file(const char* cmos_tech_behavior_filepath);
static void process_tech_xml_load_transistor_info(pugi::xml_node parent, const pugiutil::loc_data& loc_data);
static void power_tech_xml_load_multiplexer_info(pugi::xml_node parent, const pugiutil::loc_data& loc_data);
static void power_tech_xml_load_nmos_st_leakages(pugi::xml_node parent, const pugiutil::loc_data& loc_data);
static int power_compare_transistor_size(const void* key_void, const void* elem_void);
static int power_compare_voltage_pair(const void* key_void, const void* elem_void);
static int power_compare_leakage_pair(const void* key_void, const void* elem_void);
//static void power_tech_xml_load_sc(pugi::xml_node parent, const pugiutil::loc_data& loc_data);
static int power_compare_buffer_strength(const void* key_void, const void* elem_void);
static int power_compare_buffer_sc_levr(const void* key_void, const void* elem_void);
static void power_tech_xml_load_components(pugi::xml_node parent, const pugiutil::loc_data& loc_data);
static void power_tech_xml_load_component(pugi::xml_node parent, const pugiutil::loc_data& loc_data, PowerSpicedComponent** component, const char* name, float (*usage_fn)(int num_inputs, float transistor_size));
/************************* FUNCTION DEFINITIONS *********************/

void power_tech_init(const char* cmos_tech_behavior_filepath) {
    power_tech_load_xml_file(cmos_tech_behavior_filepath);
}

/**
 * Reads the transistor properties from the .xml file
 */
void power_tech_load_xml_file(const char* cmos_tech_behavior_filepath) {
    pugi::xml_document doc;
    pugiutil::loc_data loc_data;
    try {
        loc_data = pugiutil::load_xml(doc, cmos_tech_behavior_filepath);
    } catch (const pugiutil::XmlError& e) {
        vpr_throw(VPR_ERROR_POWER, cmos_tech_behavior_filepath, 0,
                  "Failed to load CMOS Tech Properties file '%s' (%s).", cmos_tech_behavior_filepath, e.what());
    }

    auto technology = get_single_child(doc, "technology", loc_data);

    get_attribute(technology, "file", loc_data); //Check exists

    auto& power_ctx = g_vpr_ctx.power();

    auto tech_size = get_attribute(technology, "size", loc_data);
    power_ctx.tech->tech_size = tech_size.as_float();

    auto operating_point = get_single_child(technology, "operating_point", loc_data);
    power_ctx.tech->temperature = get_attribute(operating_point, "temperature", loc_data).as_float();
    power_ctx.tech->Vdd = get_attribute(operating_point, "Vdd", loc_data).as_float();

    auto p_to_n = get_single_child(technology, "p_to_n", loc_data);
    power_ctx.tech->PN_ratio = get_attribute(p_to_n, "ratio", loc_data).as_float();

    /* Transistor Information
     *  We expect two <transistor> sections for P and N types
     */
    auto child = get_first_child(technology, "transistor", loc_data);
    process_tech_xml_load_transistor_info(child, loc_data);

    child = child.next_sibling("transistor");

    process_tech_xml_load_transistor_info(child, loc_data);

    //Should be no more
    auto next = child.next_sibling("transistor");
    if (next) {
        vpr_throw(VPR_ERROR_POWER, loc_data.filename_c_str(), loc_data.line(next),
                  "Encountered extra <transitor> section (expect 2 only: pmos and nmos)\n");
    }

    /* Multiplexer Voltage Information */
    child = get_single_child(technology, "multiplexers", loc_data);
    power_tech_xml_load_multiplexer_info(child, loc_data);

    /* Vds Leakage Information */
    child = get_single_child(technology, "nmos_leakages", loc_data);
    power_tech_xml_load_nmos_st_leakages(child, loc_data);

    /* Buffer SC Info */
    /*
     * child = get_single_child(technology, "buffer_sc", loc_data);
     * power_tech_xml_load_sc(child);
     */

    /* Components */
    child = get_single_child(technology, "components", loc_data);
    power_tech_xml_load_components(child, loc_data);
}

static void power_tech_xml_load_component(pugi::xml_node parent, const pugiutil::loc_data& loc_data, PowerSpicedComponent** component, const char* name, float (*usage_fn)(int num_inputs, float transistor_size)) {
    std::string component_name(name);
    *component = new PowerSpicedComponent(component_name, usage_fn);

    auto cur = get_single_child(parent, name, loc_data);

    auto child = get_first_child(cur, "inputs", loc_data);
    while (child) {
        int num_inputs = get_attribute(child, "num_inputs", loc_data).as_int(0);

        auto gc = get_first_child(child, "size", loc_data);
        while (gc) {
            float transistor_size = get_attribute(gc, "transistor_size", loc_data).as_float(0.);
            float power = get_attribute(gc, "power", loc_data).as_float(0.);
            (*component)->add_data_point(num_inputs, transistor_size, power);

            gc = gc.next_sibling("size");
        }
        child = child.next_sibling("inputs");
    }
}

static void power_tech_xml_load_components(pugi::xml_node parent, const pugiutil::loc_data& loc_data) {
    auto& power_ctx = g_vpr_ctx.power();

    power_ctx.commonly_used->component_callibration = (PowerSpicedComponent**)vtr::calloc(POWER_CALLIB_COMPONENT_MAX,
                                                                                          sizeof(PowerSpicedComponent*));

    power_tech_xml_load_component(parent, loc_data,
                                  &power_ctx.commonly_used->component_callibration[POWER_CALLIB_COMPONENT_BUFFER],
                                  "buf", power_usage_buf_for_callibration);

    power_tech_xml_load_component(parent, loc_data,
                                  &power_ctx.commonly_used->component_callibration[POWER_CALLIB_COMPONENT_BUFFER_WITH_LEVR],
                                  "buf_levr", power_usage_buf_levr_for_callibration);

    power_tech_xml_load_component(parent, loc_data,
                                  &power_ctx.commonly_used->component_callibration[POWER_CALLIB_COMPONENT_FF],
                                  "dff", power_usage_ff_for_callibration);

    power_tech_xml_load_component(parent, loc_data,
                                  &power_ctx.commonly_used->component_callibration[POWER_CALLIB_COMPONENT_MUX],
                                  "mux", power_usage_mux_for_callibration);

    power_tech_xml_load_component(parent, loc_data,
                                  &power_ctx.commonly_used->component_callibration[POWER_CALLIB_COMPONENT_LUT],
                                  "lut", power_usage_lut_for_callibration);
}

/**
 *  Read NMOS subthreshold leakage currents from the .xml transistor characteristics
 *  This builds a table of (Vds,Ids) value pairs
 *  */
static void power_tech_xml_load_nmos_st_leakages(pugi::xml_node parent, const pugiutil::loc_data& loc_data) {
    int num_nmos_sizes;
    int num_leakage_pairs;
    int i;
    int nmos_idx;
    auto& power_ctx = g_vpr_ctx.power();

    num_nmos_sizes = count_children(parent, "nmos", loc_data);
    power_ctx.tech->num_nmos_leakage_info = num_nmos_sizes;
    power_ctx.tech->nmos_leakage_info = (t_power_nmos_leakage_inf*)vtr::calloc(num_nmos_sizes, sizeof(t_power_nmos_leakage_inf));

    auto me = get_first_child(parent, "nmos", loc_data);
    nmos_idx = 0;
    while (me) {
        t_power_nmos_leakage_inf* nmos_info = &power_ctx.tech->nmos_leakage_info[nmos_idx];
        nmos_info->nmos_size = get_attribute(me, "size", loc_data).as_float(0.);

        num_leakage_pairs = count_children(me, "nmos_leakage", loc_data);
        nmos_info->num_leakage_pairs = num_leakage_pairs;
        nmos_info->leakage_pairs = (t_power_nmos_leakage_pair*)vtr::calloc(num_leakage_pairs, sizeof(t_power_nmos_leakage_pair));

        auto child = get_first_child(me, "nmos_leakage", loc_data);
        i = 0;
        while (child) {
            nmos_info->leakage_pairs[i].v_ds = get_attribute(child, "Vds", loc_data).as_float(0.0);
            nmos_info->leakage_pairs[i].i_ds = get_attribute(child, "Ids", loc_data).as_float(0.0);

            child = child.next_sibling("nmos_leakage");
            i++;
        }

        me = me.next_sibling("nmos");
        nmos_idx++;
    }
}

/**
 *  Read multiplexer information from the .xml transistor characteristics.
 *  This contains the estimates of mux output voltages, depending on 1) Mux Size 2) Mux Vin
 *  */
static void power_tech_xml_load_multiplexer_info(pugi::xml_node parent, const pugiutil::loc_data& loc_data) {
    int num_nmos_sizes;
    int num_mux_sizes;
    int i, j, nmos_idx;
    auto& power_ctx = g_vpr_ctx.power();

    /* Process all nmos sizes */
    num_nmos_sizes = count_children(parent, "nmos", loc_data);
    VTR_ASSERT(num_nmos_sizes > 0);
    power_ctx.tech->num_nmos_mux_info = num_nmos_sizes;
    power_ctx.tech->nmos_mux_info = (t_power_nmos_mux_inf*)vtr::calloc(num_nmos_sizes, sizeof(t_power_nmos_mux_inf));

    auto me = get_first_child(parent, "nmos", loc_data);
    nmos_idx = 0;
    while (me) {
        t_power_nmos_mux_inf* nmos_inf = &power_ctx.tech->nmos_mux_info[nmos_idx];
        nmos_inf->nmos_size = get_attribute(me, "size", loc_data).as_float(0.0);

        /* Process all multiplexer sizes */
        num_mux_sizes = count_children(me, "multiplexer", loc_data);

        /* Add entries for 0 and 1, for convenience, although
         * they will never be used
         */
        nmos_inf->max_mux_sl_size = 1 + num_mux_sizes;
        nmos_inf->mux_voltage_inf = (t_power_mux_volt_inf*)vtr::calloc(nmos_inf->max_mux_sl_size + 1, sizeof(t_power_mux_volt_inf));

        auto child = get_first_child(me, "multiplexer", loc_data);
        i = 1;
        while (child) {
            int num_voltages;

            VTR_ASSERT(i == get_attribute(child, "size", loc_data).as_int(0));

            /* For each mux size, process all of the Vin levels */
            num_voltages = count_children(child, "voltages", loc_data);

            nmos_inf->mux_voltage_inf[i].num_voltage_pairs = num_voltages;
            nmos_inf->mux_voltage_inf[i].mux_voltage_pairs = (t_power_mux_volt_pair*)vtr::calloc(num_voltages,
                                                                                                 sizeof(t_power_mux_volt_pair));

            auto gc = get_first_child(child, "voltages", loc_data);
            j = 0;
            while (gc) {
                /* For each mux size, and Vin level, get the min/max V_out */
                nmos_inf->mux_voltage_inf[i].mux_voltage_pairs[j].v_in = get_attribute(gc, "in", loc_data).as_float(0.0);
                nmos_inf->mux_voltage_inf[i].mux_voltage_pairs[j].v_out_min = get_attribute(gc, "out_min", loc_data).as_float(0.0);
                nmos_inf->mux_voltage_inf[i].mux_voltage_pairs[j].v_out_max = get_attribute(gc, "out_max", loc_data).as_float(0.0);

                gc = gc.next_sibling("voltages");
                j++;
            }

            child = child.next_sibling("multiplexer");
            i++;
        }

        me = me.next_sibling("nmos");
        nmos_idx++;
    }
}

/**
 * Read the transistor information from the .xml transistor characteristics.
 * For each transistor size, it extracts the:
 * - transistor node capacitances
 * - subthreshold leakage
 * - gate leakage
 */
static void process_tech_xml_load_transistor_info(pugi::xml_node parent, const pugiutil::loc_data& loc_data) {
    t_transistor_inf* trans_inf;
    int i;
    auto& power_ctx = g_vpr_ctx.power();

    /* Get transistor type: NMOS or PMOS */
    auto prop = get_attribute(parent, "type", loc_data);
    trans_inf = nullptr;
    if (strcmp(prop.value(), "nmos") == 0) {
        trans_inf = &power_ctx.tech->NMOS_inf;
    } else if (strcmp(prop.value(), "pmos") == 0) {
        trans_inf = &power_ctx.tech->PMOS_inf;
    } else {
        vpr_throw(VPR_ERROR_POWER, loc_data.filename_c_str(), loc_data.line(parent),
                  "Unrecognized transistor type '%s', expected 'nmos' or 'pmos'\n", prop.value());
    }

    /* Get long transistor information (W=1,L=2) */
    trans_inf->long_trans_inf = (t_transistor_size_inf*)vtr::malloc(sizeof(t_transistor_size_inf));

    auto child = get_single_child(parent, "long_size", loc_data);
    VTR_ASSERT(get_attribute(child, "L", loc_data).as_int(0) == 2);
    trans_inf->long_trans_inf->size = get_attribute(child, "W", loc_data).as_float(0.);

    auto grandchild = get_single_child(child, "leakage_current", loc_data);
    trans_inf->long_trans_inf->leakage_subthreshold = get_attribute(grandchild, "subthreshold", loc_data).as_float(0.);

    grandchild = get_single_child(child, "capacitance", loc_data);
    trans_inf->long_trans_inf->C_g = get_attribute(grandchild, "C_g", loc_data).as_float(0);
    trans_inf->long_trans_inf->C_d = get_attribute(grandchild, "C_d", loc_data).as_float(0);
    trans_inf->long_trans_inf->C_s = get_attribute(grandchild, "C_s", loc_data).as_float(0);

    /* Process all transistor sizes */
    trans_inf->num_size_entries = count_children(parent, "size", loc_data);
    trans_inf->size_inf = (t_transistor_size_inf*)vtr::calloc(trans_inf->num_size_entries, sizeof(t_transistor_size_inf));

    child = get_first_child(parent, "size", loc_data);
    i = 0;
    while (child) {
        VTR_ASSERT(get_attribute(child, "L", loc_data).as_int(0) == 1);

        trans_inf->size_inf[i].size = get_attribute(child, "W", loc_data).as_float(0);

        /* Get leakage currents */
        grandchild = get_single_child(child, "leakage_current", loc_data);
        trans_inf->size_inf[i].leakage_subthreshold = get_attribute(grandchild, "subthreshold", loc_data).as_float(0);
        trans_inf->size_inf[i].leakage_gate = get_attribute(grandchild, "gate", loc_data).as_float(0);

        /* Get node capacitances */
        grandchild = get_single_child(child, "capacitance", loc_data);
        trans_inf->size_inf[i].C_g = get_attribute(grandchild, "C_g", loc_data).as_float(0);
        trans_inf->size_inf[i].C_s = get_attribute(grandchild, "C_s", loc_data).as_float(0);
        trans_inf->size_inf[i].C_d = get_attribute(grandchild, "C_d", loc_data).as_float(0);

        child = child.next_sibling("size");
        i++;
    }
}

/**
 * This function searches for a transistor by size
 * - lower: (Return value) The lower-bound matching transistor
 * - upper: (Return value) The upper-bound matching transistor
 * - type: The transistor type to search for
 * - size: The transistor size to search for (size = W/L)
 */
bool power_find_transistor_info(t_transistor_size_inf** lower,
                                t_transistor_size_inf** upper,
                                e_tx_type type,
                                float size) {
    char msg[1024];
    t_transistor_size_inf key;
    t_transistor_size_inf* found;
    t_transistor_inf* trans_info;
    float min_size, max_size;
    bool error = false;
    auto& power_ctx = g_vpr_ctx.power();

    key.size = size;

    /* Find the appropriate global transistor records */
    trans_info = nullptr;
    if (type == NMOS) {
        trans_info = &power_ctx.tech->NMOS_inf;
    } else if (type == PMOS) {
        trans_info = &power_ctx.tech->PMOS_inf;
    } else {
        VTR_ASSERT(0);
    }

    /* No transistor data exists */
    if (trans_info->size_inf == nullptr) {
        power_log_msg(POWER_LOG_ERROR,
                      "No transistor information exists.  Cannot determine transistor properties.");
        error = true;
        return error;
    }

    /* Make note of the transistor record we are searching in, and the bounds */
    f_transistor_last_searched = trans_info;
    min_size = trans_info->size_inf[0].size;
    max_size = trans_info->size_inf[trans_info->num_size_entries - 1].size;

    found = (t_transistor_size_inf*)bsearch(&key, trans_info->size_inf,
                                            trans_info->num_size_entries, sizeof(t_transistor_size_inf),
                                            &power_compare_transistor_size);
    VTR_ASSERT(found);

    if (size < min_size) {
        /* Too small */
        VTR_ASSERT(found == &trans_info->size_inf[0]);
        sprintf(msg,
                "Using %s transistor of size '%f', which is smaller than the smallest modeled transistor (%f) in the technology behavior file.",
                transistor_type_name(type), size, min_size);
        power_log_msg(POWER_LOG_WARNING, msg);
        *lower = nullptr;
        *upper = found;
    } else if (size > max_size) {
        /* Too large */
        VTR_ASSERT(found == &trans_info->size_inf[trans_info->num_size_entries - 1]);
        sprintf(msg,
                "Using %s transistor of size '%f', which is larger than the largest modeled transistor (%f) in the technology behavior file.",
                transistor_type_name(type), size, max_size);
        power_log_msg(POWER_LOG_WARNING, msg);
        *lower = found;
        *upper = nullptr;
    } else {
        *lower = found;
        *upper = found + 1;
    }

    return error;
}

/**
 * This function searches for the Ids leakage current, based on a given Vds.
 * This function is used for minimum-sized NMOS transistors (used in muxs).
 * - lower: (Return value) The lower-bound matching V/I pair
 * - upper: (Return value) The upper-bound matching V/I pair
 * - v_ds: The drain/source voltage to search for
 */
void power_find_nmos_leakage(t_power_nmos_leakage_inf* nmos_leakage_info,
                             t_power_nmos_leakage_pair** lower,
                             t_power_nmos_leakage_pair** upper,
                             float v_ds) {
    t_power_nmos_leakage_pair key;
    t_power_nmos_leakage_pair* found;

    key.v_ds = v_ds;

    f_power_searching_nmos_leakage_info = nmos_leakage_info;

    found = (t_power_nmos_leakage_pair*)bsearch(&key,
                                                nmos_leakage_info->leakage_pairs,
                                                nmos_leakage_info->num_leakage_pairs,
                                                sizeof(t_power_nmos_leakage_pair), power_compare_leakage_pair);
    VTR_ASSERT(found);

    if (found == &nmos_leakage_info->leakage_pairs[nmos_leakage_info->num_leakage_pairs - 1]) {
        /* The results equal to the max voltage (Vdd) */
        *lower = found;
        *upper = nullptr;
    } else {
        *lower = found;
        *upper = found + 1;
    }
}

/**
 * This function searches for the information for a given buffer strength.
 * - lower: (Return value) The lower-bound matching record
 * - upper: (Return value) The upper-bound matching record
 * - stage_gain: The buffer strength to search for
 */
void power_find_buffer_strength_inf(t_power_buffer_strength_inf** lower,
                                    t_power_buffer_strength_inf** upper,
                                    t_power_buffer_size_inf* size_inf,
                                    float stage_gain) {
    t_power_buffer_strength_inf key;
    t_power_buffer_strength_inf* found;

    float min_size;
    float max_size;

    min_size = size_inf->strength_inf[0].stage_gain;
    max_size = size_inf->strength_inf[size_inf->num_strengths - 1].stage_gain;

    VTR_ASSERT(stage_gain >= min_size && stage_gain <= max_size);

    key.stage_gain = stage_gain;

    found = (t_power_buffer_strength_inf*)bsearch(&key, size_inf->strength_inf,
                                                  size_inf->num_strengths, sizeof(t_power_buffer_strength_inf),
                                                  power_compare_buffer_strength);

    if (stage_gain == max_size) {
        *lower = found;
        *upper = nullptr;
    } else {
        *lower = found;
        *upper = found + 1;
    }
}

/**
 * This function searches for short-circuit current information for a level-restoring buffer,
 * based on the size of the multiplexer driving the input
 * - lower: (Return value) The lower-bound matching record
 * - upper: (Return value) The upper-bound matching record
 * - buffer_strength: The set of records to search withing, which are for a specific buffer size/strength
 * - input_mux_size: The input mux size to search for
 */
void power_find_buffer_sc_levr(t_power_buffer_sc_levr_inf** lower,
                               t_power_buffer_sc_levr_inf** upper,
                               t_power_buffer_strength_inf* buffer_strength,
                               int input_mux_size) {
    t_power_buffer_sc_levr_inf key;
    t_power_buffer_sc_levr_inf* found;
    char msg[1024];
    int max_size;

    VTR_ASSERT(input_mux_size >= 1);

    key.mux_size = input_mux_size;

    f_buffer_strength_last_searched = buffer_strength;
    found = (t_power_buffer_sc_levr_inf*)bsearch(&key,
                                                 buffer_strength->sc_levr_inf, buffer_strength->num_levr_entries,
                                                 sizeof(t_power_buffer_sc_levr_inf), power_compare_buffer_sc_levr);

    max_size = buffer_strength->sc_levr_inf[buffer_strength->num_levr_entries
                                            - 1]
                   .mux_size;
    if (input_mux_size > max_size) {
        /* Input mux too large */
        VTR_ASSERT(found == &buffer_strength->sc_levr_inf[buffer_strength->num_levr_entries - 1]);
        sprintf(msg,
                "Using buffer driven by mux of size '%d', which is larger than the largest modeled size (%d) in the technology behavior file.",
                input_mux_size, max_size);
        power_log_msg(POWER_LOG_WARNING, msg);
        *lower = found;
        *upper = nullptr;
    } else {
        *lower = found;
        *upper = found + 1;
    }
}

/**
 * Comparison function, used by power_find_nmos_leakage
 */
static int power_compare_leakage_pair(const void* key_void, const void* elem_void) {
    const t_power_nmos_leakage_pair* key = (const t_power_nmos_leakage_pair*)key_void;
    const t_power_nmos_leakage_pair* elem = (const t_power_nmos_leakage_pair*)elem_void;
    const t_power_nmos_leakage_pair* next = (const t_power_nmos_leakage_pair*)elem + 1;

    /* Compare against last? */
    if (elem == &f_power_searching_nmos_leakage_info->leakage_pairs[f_power_searching_nmos_leakage_info->num_leakage_pairs - 1]) {
        if (key->v_ds >= elem->v_ds) {
            return 0;
        } else {
            return -1;
        }
    }

    /* Check for exact match to Vdd (upper end) */
    if (key->v_ds == elem->v_ds) {
        return 0;
    } else if (key->v_ds < elem->v_ds) {
        return -1;
    } else if (key->v_ds > next->v_ds) {
        return 1;
    } else {
        return 0;
    }
}

/**
 * This function searches for multiplexer output voltage information, based on input voltage
 * - lower: (Return value) The lower-bound matching record
 * - upper: (Return value) The upper-bound matching record
 * - volt_inf: The set of records to search within, which are for a specific mux size
 * - v_in: The input voltage to search for
 */
void power_find_mux_volt_inf(t_power_mux_volt_pair** lower,
                             t_power_mux_volt_pair** upper,
                             t_power_mux_volt_inf* volt_inf,
                             float v_in) {
    t_power_mux_volt_pair key;
    t_power_mux_volt_pair* found;

    key.v_in = v_in;

    f_mux_volt_last_searched = volt_inf;
    found = (t_power_mux_volt_pair*)bsearch(&key, volt_inf->mux_voltage_pairs,
                                            volt_inf->num_voltage_pairs, sizeof(t_power_mux_volt_pair),
                                            power_compare_voltage_pair);
    VTR_ASSERT(found);

    if (found
        == &volt_inf->mux_voltage_pairs[volt_inf->num_voltage_pairs - 1]) {
        *lower = found;
        *upper = nullptr;
    } else {
        *lower = found;
        *upper = found + 1;
    }
}

/**
 * Comparison function, used by power_find_buffer_sc_levr
 */
static int power_compare_buffer_sc_levr(const void* key_void,
                                        const void* elem_void) {
    const t_power_buffer_sc_levr_inf* key = (const t_power_buffer_sc_levr_inf*)key_void;
    const t_power_buffer_sc_levr_inf* elem = (const t_power_buffer_sc_levr_inf*)elem_void;
    const t_power_buffer_sc_levr_inf* next;

    /* Compare against last? */
    if (elem
        == &f_buffer_strength_last_searched->sc_levr_inf[f_buffer_strength_last_searched->num_levr_entries
                                                         - 1]) {
        if (key->mux_size >= elem->mux_size) {
            return 0;
        } else {
            return -1;
        }
    }

    /* Compare against first? */
    if (elem == &f_buffer_strength_last_searched->sc_levr_inf[0]) {
        if (key->mux_size < elem->mux_size) {
            return 0;
        }
    }

    /* Check if the key is between elem and the next element */
    next = elem + 1;
    if (key->mux_size > next->mux_size) {
        return 1;
    } else if (key->mux_size < elem->mux_size) {
        return -1;
    } else {
        return 0;
    }
}

/**
 * Comparison function, used by power_find_buffer_strength_inf
 */
static int power_compare_buffer_strength(const void* key_void,
                                         const void* elem_void) {
    const t_power_buffer_strength_inf* key = (const t_power_buffer_strength_inf*)key_void;
    const t_power_buffer_strength_inf* elem = (const t_power_buffer_strength_inf*)elem_void;
    const t_power_buffer_strength_inf* next = (const t_power_buffer_strength_inf*)elem + 1;

    /* Check for exact match */
    if (key->stage_gain == elem->stage_gain) {
        return 0;
    } else if (key->stage_gain < elem->stage_gain) {
        return -1;
    } else if (key->stage_gain > next->stage_gain) {
        return 1;
    } else {
        return 0;
    }
}

/**
 * Comparison function, used by power_find_transistor_info
 */
static int power_compare_transistor_size(const void* key_void,
                                         const void* elem_void) {
    const t_transistor_size_inf* key = (const t_transistor_size_inf*)key_void;
    const t_transistor_size_inf* elem = (const t_transistor_size_inf*)elem_void;
    const t_transistor_size_inf* next;

    /* Check if we are comparing against the last element */
    if (elem
        == &f_transistor_last_searched->size_inf[f_transistor_last_searched->num_size_entries
                                                 - 1]) {
        /* Match if the desired value is larger than the largest item in the list */
        if (key->size >= elem->size) {
            return 0;
        } else {
            return -1;
        }
    }

    /* Check if we are comparing against the first element */
    if (elem == &f_transistor_last_searched->size_inf[0]) {
        /* Match the smallest if it is smaller than the smallest */
        if (key->size < elem->size) {
            return 0;
        }
    }

    /* Check if the key is between elem and the next element */
    next = elem + 1;
    if (key->size > next->size) {
        return 1;
    } else if (key->size < elem->size) {
        return -1;
    } else {
        return 0;
    }
}

/**
 * Comparison function, used by power_find_mux_volt_inf
 */
static int power_compare_voltage_pair(const void* key_void,
                                      const void* elem_void) {
    const t_power_mux_volt_pair* key = (const t_power_mux_volt_pair*)key_void;
    const t_power_mux_volt_pair* elem = (const t_power_mux_volt_pair*)elem_void;
    const t_power_mux_volt_pair* next = (const t_power_mux_volt_pair*)elem
                                        + 1;

    /* Check if we are comparing against the last element */
    if (elem
        == &f_mux_volt_last_searched->mux_voltage_pairs[f_mux_volt_last_searched->num_voltage_pairs
                                                        - 1]) {
        /* Match if the desired value is larger than the largest item in the list */
        if (key->v_in >= elem->v_in) {
            return 0;
        } else {
            return -1;
        }
    }

    /* Check for exact match to Vdd (upper end) */
    if (key->v_in == elem->v_in) {
        return 0;
    } else if (key->v_in < elem->v_in) {
        return -1;
    } else if (key->v_in > next->v_in) {
        return 1;
    } else {
        return 0;
    }
}