Page MenuHomePhorge
Files F562158

chain_variable_ordering.hpp
No OneTemporary
Actions

Size
4 KB
Referenced Files
None
Subscribers
None

chain_variable_ordering.hpp
View Options

// Copyright 2025 Oliver Theimer
#pragma once
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <random>
#include <vector>
#define POS(in, cvo) (*cvo)[in % cvo->size()].pos
#define VAR(pos, cvo) (*cvo)[pos].in
typedef uint32_t cvo_index_t;
enum cvo_init_type {
cvo_none,
cvo_random,
cvo_even,
cvo_even_reversed,
cvo_input
};
typedef enum cvo_init_type cvo_init_t;
/**
* @class cvo_pair_t
* @brief stores primary and secondary variable
*
*/
struct cvo_pair_t {
cvo_index_t pv;
cvo_index_t sv;
};
/**
* @class cvo_element_t
* @brief stores the of the position of the current variable in the chainvariable ordering and the input at the current position
*
*/
struct cvo_element_t {
// references the position of the variable in ordering
cvo_index_t pos;
// references the input at this element index
cvo_index_t in;
};
typedef std::vector<cvo_element_t> cvo_t;
/**
* @brief dumps the current ordering to stdout in the format IN: followed by the
* indices of the inputs and pos followed by the positions of the inputs in
* ascending order
*
* @param cvo chain variable ordering that should be dumped
*/
inline void dump_ordering(cvo_t *cvo) {
std::cout << "IN: |";
for (uint32_t i = 0; i < cvo->size(); i++) {
printf(" %d |", (*cvo)[i].in);
}
std::cout << "\nPOS: |";
for (uint32_t i = 0; i < cvo->size(); i++) {
printf(" %d |", (*cvo)[i].pos);
}
std::cout << "\n";
}
/**
* @brief appends the chain variable ordering split into two comma seperated
* lists into the given file. The first list represents the ordering of the
* input, the second list prints the position of the input at the current index
*
* @param cvo chain variable ordering that should be printed
* @param file outputfile in which the output should be appended
*/
inline void dump_ordering(cvo_t *cvo, std::ofstream &file) {
file << std::to_string((*cvo)[0].in);
for (uint32_t i = 1; i < cvo->size(); i++) {
file << "," << std::to_string((*cvo)[i].in);
}
file << ";" << std::to_string((*cvo)[0].pos);
for (uint32_t i = 1; i < cvo->size(); i++) {
file << "," << std::to_string((*cvo)[i].pos);
}
}
/**
* @brief initialise ordering based on a strategy.
*
* @param inputs list of input variables
* @param cvo pointer to chain variable ordering that should be initialised
* @param opt option of the initial ordering strategy. The options are cvo_none,
* cvo_even_reversed, cvo_even, cvo_input
* @param input_order if the cvo_inout option is given, the ordering given by
* this parameter is used to initialize the ordering
*/
inline void init_ordering(
std::vector<uint64_t> inputs, cvo_t *&cvo, cvo_init_t opt,
std::vector<cvo_index_t> input_order = std::vector<cvo_index_t>()) {
cvo = new std::vector<cvo_element_t>(inputs.size());
std::vector<uint32_t> new_order;
if (opt == cvo_none) {
for (uint32_t i = 0; i < inputs.size(); i++) {
uint32_t input = inputs[i];
(*cvo)[i].in = input;
(*cvo)[input % inputs.size()].pos = i;
}
} else if (opt == cvo_random) {
for (uint32_t i = 0; i < inputs.size(); i++) {
new_order.push_back(i + 2);
}
unsigned seed = time(NULL);
printf("seed: %d\n", seed);
std::shuffle(new_order.begin(), new_order.end(),
std::default_random_engine(seed));
for (uint32_t i = 0; i < new_order.size(); i++) {
(*cvo)[i].in = new_order[i];
(*cvo)[new_order[i] % cvo->size()].pos = i;
}
} else if (opt == cvo_even || opt == cvo_even_reversed) {
assert(inputs.size() % 2 == 0);
for (uint32_t i = 0; i < inputs.size() / 2; i++) {
uint32_t input1 = inputs[i];
uint32_t input2 = inputs[i + (inputs.size() / 2)];
(*cvo)[(2 * i)].in = input1;
(*cvo)[input1 % inputs.size()].pos = (2 * i);
(*cvo)[(2 * i) + 1].in = input2;
(*cvo)[input2 % inputs.size()].pos = (2 * i) + 1;
}
if (opt == cvo_even_reversed) {
std::reverse((*cvo).begin(), (*cvo).end());
for (uint32_t i = 0; i < (*cvo).size(); i++) {
(*cvo)[(*cvo)[i].in % cvo->size()].pos = i;
}
}
} else if (opt == cvo_input) {
assert(inputs.size() == input_order.size());
for (uint32_t i = 0; i < input_order.size(); i++) {
(*cvo)[i].in = input_order[i];
(*cvo)[input_order[i] % cvo->size()].pos = i;
}
}
dump_ordering(cvo);
// correctness check
for (uint32_t i = 0; i < cvo->size(); i++) {
assert((*cvo)[(*cvo)[(i + 2) % cvo->size()].pos].in == i + 2);
}
#ifdef DEBUG
dump_ordering(cvo);
#endif
}

File Metadata

Mime Type
text/x-c
Expires
Mon, Dec 1, 5:52 PM (1 d, 11 h)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
242624
Default Alt Text
chain_variable_ordering.hpp (4 KB)

Event Timeline