Source code for Compiler.sorting

import itertools
from Compiler import types, library, instructions

def dest_comp(B):
    Bt = B.transpose()
    St_flat = Bt.get_vector().prefix_sum()
    Tt_flat = Bt.get_vector() * St_flat.get_vector()
    Tt = types.Matrix(*Bt.sizes, B.value_type)
    return sum(Tt) - 1

[docs]def reveal_sort(k, D, reverse=False): """ Sort in place according to "perfect" key. The name hints at the fact that a random order of the keys is revealed. :param k: vector or Array of sint containing exactly :math:`0,\dots,n-1` in any order :param D: Array or MultiArray to sort :param reverse: wether :py:obj:`key` is a permutation in forward or backward order """ assert len(k) == len(D) library.break_point() shuffle = types.sint.get_secure_shuffle(len(k)) k_prime = k.get_vector().secure_permute(shuffle).reveal() idx = types.Array.create_from(k_prime) if reverse: D.assign_vector(D.get_slice_vector(idx)) library.break_point() D.secure_permute(shuffle, reverse=True) else: D.secure_permute(shuffle) library.break_point() v = D.get_vector() D.assign_slice_vector(idx, v) library.break_point() instructions.delshuffle(shuffle)
[docs]def radix_sort(k, D, n_bits=None, signed=True): """ Sort in place according to key. :param k: keys (vector or Array of sint or sfix) :param D: Array or MultiArray to sort :param n_bits: number of bits in keys (int) :param signed: whether keys are signed (bool) """ assert len(k) == len(D) bs = types.Matrix.create_from(k.get_vector().bit_decompose(n_bits)) if signed and len(bs) > 1: bs[-1][:] = bs[-1][:].bit_not() radix_sort_from_matrix(bs, D)
def radix_sort_from_matrix(bs, D): n = len(D) for b in bs: assert(len(b) == n) B = types.sint.Matrix(n, 2) h = types.Array.create_from(types.sint( @library.for_range(len(bs)) def _(i): b = bs[i] B.set_column(0, 1 - b.get_vector()) B.set_column(1, b.get_vector()) c = types.Array.create_from(dest_comp(B)) reveal_sort(c, h, reverse=False) @library.if_e(i < len(bs) - 1) def _(): reveal_sort(h, bs[i + 1], reverse=True) @library.else_ def _(): reveal_sort(h, D, reverse=True)