123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664 |
- #ifndef __RDPF_HPP__
- #define __RDPF_HPP__
- #include <array>
- #include <vector>
- #include <iostream>
- #include "mpcio.hpp"
- #include "coroutine.hpp"
- #include "types.hpp"
- #include "bitutils.hpp"
- #include "dpf.hpp"
- template <nbits_t WIDTH>
- struct RDPF : public DPF {
- template <typename T>
- using W = std::array<T, WIDTH>;
-
- using RegASW = W<RegAS>;
- using RegXSW = W<RegXS>;
-
-
- static const nbits_t LWIDTH = 1 + (WIDTH/2);
- using LeafNode = std::array<DPFnode,LWIDTH>;
-
-
-
- struct LeafInfo {
- static const nbits_t W = WIDTH;
-
- LeafNode leaf_cw;
-
-
- value_t unit_sum_inverse;
-
-
- std::array<RegAS,WIDTH> scaled_sum;
-
-
- std::array<RegXS,WIDTH> scaled_xor;
-
- std::vector<LeafNode> expansion;
- LeafInfo() : unit_sum_inverse(0) {}
- };
-
-
-
-
-
-
- nbits_t maxdepth, curdepth;
-
-
-
-
-
- std::vector<LeafInfo> li;
-
-
-
-
- value_t leaf_cfbits;
- RDPF() {}
-
-
-
-
-
-
-
-
-
-
-
-
- RDPF(MPCTIO &tio, yield_t &yield,
- RegXS target, nbits_t depth, bool incremental = false,
- bool save_expansion = false);
-
- inline bool has_expansion() const {
- return li[maxdepth-curdepth].expansion.size() > 0;
- }
-
- inline LeafNode get_expansion(address_t index) const {
- return li[maxdepth-curdepth].expansion[index];
- }
-
- inline nbits_t depth() const { return curdepth; }
-
-
- inline void depth(nbits_t newdepth) {
- if (newdepth > 0 && newdepth < maxdepth) {
- curdepth = newdepth;
- } else {
- curdepth = maxdepth;
- }
- }
-
-
-
- LeafNode leaf(address_t input, size_t &aes_ops) const;
-
- void expand(size_t &aes_ops);
-
-
-
-
-
- inline LeafNode descend_to_leaf(const DPFnode &parent,
- nbits_t parentdepth, bit_t whichchild, size_t &aes_ops) const;
-
- inline RegBS unit_bs(const LeafNode &leaf) const {
- RegBS b;
- b.bshare = get_lsb(leaf[0]);
- return b;
- }
-
- inline RegAS unit_as(const LeafNode &leaf) const {
- RegAS a;
- value_t lowword = value_t(_mm_cvtsi128_si64x(leaf[0]));
- if (whichhalf == 1) {
- lowword = -lowword;
- }
- a.ashare = lowword * li[maxdepth-curdepth].unit_sum_inverse;
- return a;
- }
-
- inline RegXSW scaled_xs(const LeafNode &leaf) const {
- RegXSW x;
- nbits_t j = 0;
- value_t highword =
- value_t(_mm_cvtsi128_si64x(_mm_srli_si128(leaf[0],8)));
- x[j++].xshare = highword;
- for (nbits_t i=1;i<LWIDTH;++i) {
- value_t lowword =
- value_t(_mm_cvtsi128_si64x(leaf[i]));
- value_t highword =
- value_t(_mm_cvtsi128_si64x(_mm_srli_si128(leaf[i],8)));
- x[j++].xshare = lowword;
- if (j < WIDTH) {
- x[j++].xshare = highword;
- }
- }
- return x;
- }
-
- inline RegASW scaled_as(const LeafNode &leaf) const {
- RegASW a;
- nbits_t j = 0;
- value_t highword =
- value_t(_mm_cvtsi128_si64x(_mm_srli_si128(leaf[0],8)));
- if (whichhalf == 1) {
- highword = -highword;
- }
- a[j++].ashare = highword;
- for (nbits_t i=1;i<WIDTH;++i) {
- value_t lowword =
- value_t(_mm_cvtsi128_si64x(leaf[i]));
- value_t highword =
- value_t(_mm_cvtsi128_si64x(_mm_srli_si128(leaf[i],8)));
- if (whichhalf == 1) {
- lowword = -lowword;
- highword = -highword;
- }
- a[j++].ashare = lowword;
- if (j < WIDTH) {
- a[j++].ashare = highword;
- }
- }
- return a;
- }
- private:
-
- void expand_leaf_layer(nbits_t li_index, size_t &aes_ops);
- };
- template <nbits_t WIDTH>
- struct RDPFTriple {
- template <typename T>
- using Triple = std::tuple<T, T, T>;
- template <typename T>
- using WTriple = std::tuple<
- typename std::array<T,WIDTH>,
- typename std::array<T,WIDTH>,
- typename std::array<T,WIDTH> >;
-
-
- using node = Triple<DPFnode>;
- using LeafNode = Triple<typename RDPF<WIDTH>::LeafNode>;
- using RegASWT = WTriple<RegAS>;
- using RegXSWT = WTriple<RegXS>;
- RegAS as_target;
- RegXS xs_target;
- RDPF<WIDTH> dpf[3];
-
- inline nbits_t depth() const { return dpf[0].depth(); }
-
-
- inline void depth(nbits_t newdepth) {
- dpf[0].depth(newdepth);
- dpf[1].depth(newdepth);
- dpf[2].depth(newdepth);
- }
-
- inline node get_seed() const {
- return std::make_tuple(dpf[0].get_seed(), dpf[1].get_seed(),
- dpf[2].get_seed());
- }
-
- inline bool has_expansion() const {
- int li_index = dpf[0].maxdepth - dpf[0].curdepth;
- return dpf[0].li[li_index].expansion.size() > 0;
- }
-
- inline LeafNode get_expansion(address_t index) const {
- return std::make_tuple(dpf[0].get_expansion(index),
- dpf[1].get_expansion(index), dpf[2].get_expansion(index));
- }
- RDPFTriple() {}
-
-
- RDPFTriple(MPCTIO &tio, yield_t &yield,
- nbits_t depth, bool incremental = false, bool save_expansion = false);
-
- node descend(const node &parent, nbits_t parentdepth,
- bit_t whichchild, size_t &aes_ops) const;
-
- LeafNode descend_to_leaf(const node &parent, nbits_t parentdepth,
- bit_t whichchild, size_t &aes_ops) const;
-
-
-
-
- inline void get_target(RegAS &target) const { target = as_target; }
- inline void get_target(RegXS &target) const {
- target = xs_target >> (dpf[0].maxdepth - dpf[0].curdepth);
- }
-
-
- inline void scaled_value(RegASWT &v) const {
- int li_index = dpf[0].maxdepth - dpf[0].curdepth;
- std::get<0>(v) = dpf[0].li[li_index].scaled_sum;
- std::get<1>(v) = dpf[1].li[li_index].scaled_sum;
- std::get<2>(v) = dpf[2].li[li_index].scaled_sum;
- }
-
-
- inline void scaled_value(RegXSWT &v) const {
- int li_index = dpf[0].maxdepth - dpf[0].curdepth;
- std::get<0>(v) = dpf[0].li[li_index].scaled_xor;
- std::get<1>(v) = dpf[1].li[li_index].scaled_xor;
- std::get<2>(v) = dpf[2].li[li_index].scaled_xor;
- }
-
- inline void unit(std::tuple<RegAS,RegAS,RegAS> &u, const LeafNode &leaf) const {
- std::get<0>(u) = dpf[0].unit_as(std::get<0>(leaf));
- std::get<1>(u) = dpf[1].unit_as(std::get<1>(leaf));
- std::get<2>(u) = dpf[2].unit_as(std::get<2>(leaf));
- }
-
- inline void unit(std::tuple<RegXS,RegXS,RegXS> &u, const LeafNode &leaf) const {
- std::get<0>(u) = dpf[0].unit_bs(std::get<0>(leaf));
- std::get<1>(u) = dpf[1].unit_bs(std::get<1>(leaf));
- std::get<2>(u) = dpf[2].unit_bs(std::get<2>(leaf));
- }
-
-
- template <typename T>
- inline void unit(std::tuple<T,T,T> &u, const LeafNode &leaf) const {
- std::get<0>(u).unit(dpf[0], std::get<0>(leaf));
- std::get<1>(u).unit(dpf[1], std::get<1>(leaf));
- std::get<2>(u).unit(dpf[2], std::get<2>(leaf));
- }
-
- inline void scaled(RegASWT &s, const LeafNode &leaf) const {
- std::get<0>(s) = dpf[0].scaled_as(std::get<0>(leaf));
- std::get<1>(s) = dpf[1].scaled_as(std::get<1>(leaf));
- std::get<2>(s) = dpf[2].scaled_as(std::get<2>(leaf));
- }
-
- inline void scaled(RegXSWT &s, const LeafNode &leaf) const {
- std::get<0>(s) = dpf[0].scaled_xs(std::get<0>(leaf));
- std::get<1>(s) = dpf[1].scaled_xs(std::get<1>(leaf));
- std::get<2>(s) = dpf[2].scaled_xs(std::get<2>(leaf));
- }
- };
- template <nbits_t WIDTH>
- struct RDPFPair {
- template <typename T>
- using Pair = std::tuple<T, T>;
- template <typename T>
- using WPair = std::tuple<
- typename std::array<T,WIDTH>,
- typename std::array<T,WIDTH> >;
-
-
- using node = Pair<DPFnode>;
- using LeafNode = Pair<typename RDPF<WIDTH>::LeafNode>;
- using RegASWP = WPair<RegAS>;
- using RegXSWP = WPair<RegXS>;
- RDPF<WIDTH> dpf[2];
- RDPFPair() {}
-
- inline nbits_t depth() const { return dpf[0].depth(); }
-
-
- inline void depth(nbits_t newdepth) {
- dpf[0].depth(newdepth);
- dpf[1].depth(newdepth);
- }
-
- inline node get_seed() const {
- return std::make_tuple(dpf[0].get_seed(), dpf[1].get_seed());
- }
-
- inline bool has_expansion() const {
- int li_index = dpf[0].maxdepth - dpf[0].curdepth;
- return dpf[0].li[li_index].expansion.size() > 0;
- }
-
- inline LeafNode get_expansion(address_t index) const {
- return std::make_tuple(dpf[0].get_expansion(index),
- dpf[1].get_expansion(index));
- }
-
- node descend(const node &parent, nbits_t parentdepth,
- bit_t whichchild, size_t &aes_ops) const;
-
- LeafNode descend_to_leaf(const node &parent, nbits_t parentdepth,
- bit_t whichchild, size_t &aes_ops) const;
-
-
-
-
-
- inline void scaled_value(RegASWP &v) const {
- std::get<0>(v) = dpf[0].scaled_sum;
- std::get<1>(v) = dpf[1].scaled_sum;
- }
-
-
- inline void scaled_value(RegXSWP &v) const {
- std::get<0>(v) = dpf[0].scaled_xor;
- std::get<1>(v) = dpf[1].scaled_xor;
- }
-
- inline void unit(std::tuple<RegAS,RegAS> &u, const LeafNode &leaf) const {
- std::get<0>(u) = dpf[0].unit_as(std::get<0>(leaf));
- std::get<1>(u) = dpf[1].unit_as(std::get<1>(leaf));
- }
-
- inline void unit(std::tuple<RegXS,RegXS> &u, const LeafNode &leaf) const {
- std::get<0>(u) = dpf[0].unit_bs(std::get<0>(leaf));
- std::get<1>(u) = dpf[1].unit_bs(std::get<1>(leaf));
- }
-
-
- template <typename T>
- inline void unit(std::tuple<T,T> &u, const LeafNode &leaf) const {
- std::get<0>(u).unit(dpf[0], std::get<0>(leaf));
- std::get<1>(u).unit(dpf[1], std::get<1>(leaf));
- }
-
- inline void scaled(RegASWP &s, const LeafNode &leaf) const {
- std::get<0>(s) = dpf[0].scaled_as(std::get<0>(leaf));
- std::get<1>(s) = dpf[1].scaled_as(std::get<1>(leaf));
- }
-
- inline void scaled(RegXSWP &s, const LeafNode &leaf) const {
- std::get<0>(s) = dpf[0].scaled_xs(std::get<0>(leaf));
- std::get<1>(s) = dpf[1].scaled_xs(std::get<1>(leaf));
- }
- };
- template <nbits_t WIDTH>
- struct RDPF2of3 {
- template <typename T>
- using Pair = std::tuple<T, T>;
- template <typename T>
- using WPair = std::tuple<
- typename std::array<T,WIDTH>,
- typename std::array<T,WIDTH> >;
-
-
- using node = Pair<DPFnode>;
- using LeafNode = Pair<typename RDPF<WIDTH>::LeafNode>;
- using RegASWP = WPair<RegAS>;
- using RegXSWP = WPair<RegXS>;
- const RDPF<WIDTH> &dpf0, &dpf1;
-
-
-
-
- RDPF2of3(const RDPFTriple<WIDTH> &trip, int which0, int which1) :
- dpf0(trip.dpf[which0]), dpf1(trip.dpf[which1]) {}
-
- inline nbits_t depth() const { return dpf0.depth(); }
-
-
- inline void depth(nbits_t newdepth) {
- dpf0.depth(newdepth);
- dpf1.depth(newdepth);
- }
-
- inline node get_seed() const {
- return std::make_tuple(dpf0.get_seed(), dpf1.get_seed());
- }
-
- inline bool has_expansion() const {
- int li_index = dpf0.maxdepth - dpf0.curdepth;
- return dpf0.li[li_index].expansion.size() > 0;
- }
-
- inline LeafNode get_expansion(address_t index) const {
- return std::make_tuple(dpf0.get_expansion(index),
- dpf1.get_expansion(index));
- }
-
- node descend(const node &parent, nbits_t parentdepth,
- bit_t whichchild, size_t &aes_ops) const;
-
- LeafNode descend_to_leaf(const node &parent, nbits_t parentdepth,
- bit_t whichchild, size_t &aes_ops) const;
-
-
-
-
-
- inline void scaled_value(RegASWP &v) const {
- std::get<0>(v) = dpf0.scaled_sum;
- std::get<1>(v) = dpf1.scaled_sum;
- }
-
-
- inline void scaled_value(RegXSWP &v) const {
- std::get<0>(v) = dpf0.scaled_xor;
- std::get<1>(v) = dpf1.scaled_xor;
- }
-
- inline void unit(std::tuple<RegAS,RegAS> &u, const LeafNode &leaf) const {
- std::get<0>(u) = dpf0.unit_as(std::get<0>(leaf));
- std::get<1>(u) = dpf1.unit_as(std::get<1>(leaf));
- }
-
- inline void unit(std::tuple<RegXS,RegXS> &u, const LeafNode &leaf) const {
- std::get<0>(u) = dpf0.unit_bs(std::get<0>(leaf));
- std::get<1>(u) = dpf1.unit_bs(std::get<1>(leaf));
- }
-
-
- template <typename T>
- inline void unit(std::tuple<T,T> &u, const LeafNode &leaf) const {
- std::get<0>(u).unit(dpf0, std::get<0>(leaf));
- std::get<1>(u).unit(dpf1, std::get<1>(leaf));
- }
-
- inline void scaled(RegASWP &s, const LeafNode &leaf) const {
- std::get<0>(s) = dpf0.scaled_as(std::get<0>(leaf));
- std::get<1>(s) = dpf1.scaled_as(std::get<1>(leaf));
- }
-
- inline void scaled(RegXSWP &s, const LeafNode &leaf) const {
- std::get<0>(s) = dpf0.scaled_xs(std::get<0>(leaf));
- std::get<1>(s) = dpf1.scaled_xs(std::get<1>(leaf));
- }
- };
- template <typename T>
- class StreamEval {
- const T &rdpf;
- size_t &aes_ops;
- bool use_expansion;
- nbits_t depth;
- address_t counter_xor_offset;
- address_t indexmask;
- address_t pathindex;
- address_t nextindex;
- std::vector<typename T::node> path;
- public:
-
-
-
-
-
-
-
-
-
-
- StreamEval(const T &rdpf, address_t start,
- address_t xor_offset, size_t &aes_ops,
- bool use_expansion = true);
-
- typename T::LeafNode next();
- };
- template <typename T>
- struct ParallelEval {
- const T &rdpf;
- address_t start;
- address_t xor_offset;
- address_t num_evals;
- int num_threads;
- size_t &aes_ops;
-
-
-
-
-
-
-
-
- ParallelEval(const T &rdpf, address_t start,
- address_t xor_offset, address_t num_evals,
- int num_threads, size_t &aes_ops) :
- rdpf(rdpf), start(start), xor_offset(xor_offset),
- num_evals(num_evals), num_threads(num_threads),
- aes_ops(aes_ops) {}
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template <typename V, typename W>
- inline V reduce(V init, W process);
- };
- #include "rdpf.tcc"
- #endif
|