shared3p_sort.sc :: Sharemind Developer Zone

shared3p_sort.sc

Module with functions for sorting values.

Functions:

unsafeSort

Function for sorting a vector if the vector has been shuffled.

Detailed Description

unsafeSort is stable

D - shared3p protection domain

Supported types - uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64 / float32 / float64

Parameters

vec

- input vector

indices

- an index vector indicating which indice an element of the shuffled vector originated from

ascending

- a boolean indicating if the vector should be sorted in ascending order

returns the sort permutation. The ith value of the permutation is the index of the input value that is in the ith position after sorting.

Nothing is leaked if the input has been shuffled and the indices are unique

If the input is not shuffled or the indices are not unique, leaks the relative ordering of elements possibly including whether elements are equal

Function Overloads

uint unsafeSort(D bool[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D xor_uint8[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D xor_uint16[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D xor_uint32[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D xor_uint64[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D uint8[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D uint16[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D uint32[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D uint64[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D int8[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D int16[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D int32[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D int64[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D float32[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

uint unsafeSort(D float64[[1]] vec, D xor_uint64[[1]] indices, bool ascending)

quicksort

Functions for sorting values using the quicksort algorithm.

Functions:

quicksort(matrix)

quicksort(matrix, direction)

quicksort(vector)

quicksort(vector, direction)

quicksort is stable

D - all protection domains

Supported types - xor_uint64

None

quicksort(matrix)

Functions for sorting rows in a matrix using the quicksort algorithm.

Detailed Description

quicksort is stable

D - shared3p protection domain

Supported types - bool / uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64 / float32 / float64

Parameters

matrix

- a matrix of supported type

column

- the index of the sorting column

returns a matrix where the input matrix rows are sorted based on values of the specified column

None

Function Overloads

D bool quicksort(D bool[[2]] matrix, uint column)

D xor_uint8 quicksort(D xor_uint8[[2]] matrix, uint column)

D xor_uint16 quicksort(D xor_uint16[[2]] matrix, uint column)

D xor_uint32 quicksort(D xor_uint32[[2]] matrix, uint column)

D xor_uint64 quicksort(D xor_uint64[[2]] matrix, uint column)

D uint8 quicksort(D uint8[[2]] matrix, uint column)

D uint16 quicksort(D uint16[[2]] matrix, uint column)

D uint32 quicksort(D uint32[[2]] matrix, uint column)

D uint64 quicksort(D uint64[[2]] matrix, uint column)

D int8 quicksort(D int8[[2]] matrix, uint column)

D int16 quicksort(D int16[[2]] matrix, uint column)

D int32 quicksort(D int32[[2]] matrix, uint column)

D int64 quicksort(D int64[[2]] matrix, uint column)

D float32 quicksort(D float32[[2]] matrix, uint column)

D float64 quicksort(D float64[[2]] matrix, uint column)

quicksort(matrix, direction)

Functions for sorting rows in a matrix using the quicksort algorithm.

Detailed Description

quicksort is stable

D - shared3p protection domain

Supported types - bool / uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64 / float32 / float64

Parameters

matrix

- a matrix of supported type

column

- the index of the sorting column

ascending

- a boolean indicating if the input should be sorted in ascending order

returns a matrix where the input matrix rows are sorted based on values of the specified column

None

Function Overloads

D bool quicksort(D bool[[2]] matrix, uint column, bool ascending)

D xor_uint8 quicksort(D xor_uint8[[2]] matrix, uint column, bool ascending)

D xor_uint16 quicksort(D xor_uint16[[2]] matrix, uint column, bool ascending)

D xor_uint32 quicksort(D xor_uint32[[2]] matrix, uint column, bool ascending)

D xor_uint64 quicksort(D xor_uint64[[2]] matrix, uint column, bool ascending)

D uint8 quicksort(D uint8[[2]] matrix, uint column, bool ascending)

D uint16 quicksort(D uint16[[2]] matrix, uint column, bool ascending)

D uint32 quicksort(D uint32[[2]] matrix, uint column, bool ascending)

D uint64 quicksort(D uint64[[2]] matrix, uint column, bool ascending)

D int8 quicksort(D int8[[2]] matrix, uint column, bool ascending)

D int16 quicksort(D int16[[2]] matrix, uint column, bool ascending)

D int32 quicksort(D int32[[2]] matrix, uint column, bool ascending)

D int64 quicksort(D int64[[2]] matrix, uint column, bool ascending)

D float32 quicksort(D float32[[2]] matrix, uint column, bool ascending)

D float64 quicksort(D float64[[2]] matrix, uint column, bool ascending)

quicksort(vector)

Functions for sorting values in a matrix using the quicksort algorithm.

Detailed Description

quicksort is stable

D - shared3p protection domain

Supported types - bool / uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64 / float32 / float64

Parameters

vec	- a vector of supported type

returns the input vector sorted in ascending order

None

Function Overloads

D bool quicksort(D bool[[1]] vec)

D xor_uint8 quicksort(D xor_uint8[[1]] vec)

D xor_uint16 quicksort(D xor_uint16[[1]] vec)

D xor_uint32 quicksort(D xor_uint32[[1]] vec)

D xor_uint64 quicksort(D xor_uint64[[1]] vec)

D uint8 quicksort(D uint8[[1]] vec)

D uint16 quicksort(D uint16[[1]] vec)

D uint32 quicksort(D uint32[[1]] vec)

D uint64 quicksort(D uint64[[1]] vec)

D int8 quicksort(D int8[[1]] vec)

D int16 quicksort(D int16[[1]] vec)

D int32 quicksort(D int32[[1]] vec)

D int64 quicksort(D int64[[1]] vec)

D float32 quicksort(D float32[[1]] vec)

D float64 quicksort(D float64[[1]] vec)

quicksort(vector, direction)

Functions for sorting values in a matrix using the quicksort algorithm.

Detailed Description

quicksort is stable

D - shared3p protection domain

Supported types - bool / uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64 / float32 / float64

Parameters

vec

- a vector of supported type

ascending

- whether to sort in ascending (true) or descending (false) order

returns the sorted input vector

None

Function Overloads

D bool quicksort(D bool[[1]] vec, bool ascending)

D xor_uint8 quicksort(D xor_uint8[[1]] vec, bool ascending)

D xor_uint16 quicksort(D xor_uint16[[1]] vec, bool ascending)

D xor_uint32 quicksort(D xor_uint32[[1]] vec, bool ascending)

D xor_uint64 quicksort(D xor_uint64[[1]] vec, bool ascending)

D uint8 quicksort(D uint8[[1]] vec, bool ascending)

D uint16 quicksort(D uint16[[1]] vec, bool ascending)

D uint32 quicksort(D uint32[[1]] vec, bool ascending)

D uint64 quicksort(D uint64[[1]] vec, bool ascending)

D int8 quicksort(D int8[[1]] vec, bool ascending)

D int16 quicksort(D int16[[1]] vec, bool ascending)

D int32 quicksort(D int32[[1]] vec, bool ascending)

D int64 quicksort(D int64[[1]] vec, bool ascending)

D float32 quicksort(D float32[[1]] vec, bool ascending)

D float64 quicksort(D float64[[1]] vec, bool ascending)

radixSort

Functions for sorting values using the radix sort algorithm.

Functions:

radixSort(matrix)

radixSort(vector)

radixSortWithIndex

D - all protection domains

Supported types - uint / xor_uint64

Shuffled reordering decisions are declassified

radixSort(matrix)

Functions for sorting rows in a matrix using the radix sort algorithm.

Detailed Description

D - all protection domains

Supported types - uint / xor_uint64

Parameters

array

- a vector of supported type

column

- the index of the sorting column

returns a matrix where the rows are sorted based on the column given

Shuffled reordering decisions are declassified

Function Overloads

D uint64 radixSort(D uint64[[2]] array, uint column1)

radixSort(vector)

Functions for sorting values in a vector using the radix sort algorithm.

Detailed Description

D - all protection domains

Supported types - uint / xor_uint64

Parameters

array

- a vector of supported type

returns a sorted vector from smaller to bigger values

Shuffled reordering decisions are declassified

Function Overloads

D uint64 radixSort(D uint64[[1]] array)

D xor_uint64 radixSort(D xor_uint64[[1]] array)

radixSortWithIndex

Function for sorting values in a vector using the radix sort algorithm.

Detailed Description

D - all protection domains

Supported types - uint / xor_uint64

Parameters

array

- a vector of supported type

indexVector

- a vector of indexes that correspond to a value in the input array

returns the sorted indexVector where every index corresponds to a value in the input vector

Shuffled reordering decisions are declassified

Function Overloads

D uint radixSortWithIndex(D T[[1]] array, D uint[[1]] indexVector)

selectK

Functions for selecting k values from a vector/matrix according to an ordering.

Functions:

selectK[[1]]

selectK[[2]]

D - all protection domains

Supported types uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64

selectK[[1]]

Function for selecting the k smallest elements of a vector.

Detailed Description

D - all protection domains

Supported types - uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64

Requires that the input array’s length is a power of two.

The algorithm behind this function is optimized for speed, accuracy is not guaranteed.

Parameters

vector

- a vector of supported type

k

- the number of elements to be selected

returns a vector of k elements selected from the input vector

Function Overloads

D T selectK(D T[[1]] vector, uint k)

selectK[[2]]

Function for selecting k rows from a matrix ordered by a column.

Detailed Description

D - all protection domains

Supported types - uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64

The number of rows of the input matrix has to be a power of two.

The algorithm behind this function is optimized for speed, accuracy is not guaranteed.

Parameters

matrix

- a matrix of supported type

k

- number of elements to select

column

- column to select by

returns a matrix with k rows selected from the input vector according to the input column index

Function Overloads

D uint8 selectK(D uint8[[2]] matrix, uint k, uint column)

D uint16 selectK(D uint16[[2]] matrix, uint k, uint column)

D uint32 selectK(D uint32[[2]] matrix, uint k, uint column)

D uint64 selectK(D uint64[[2]] matrix, uint k, uint column)

D int8 selectK(D int8[[2]] matrix, uint k, uint column)

D int16 selectK(D int16[[2]] matrix, uint k, uint column)

D int32 selectK(D int32[[2]] matrix, uint k, uint column)

D int64 selectK(D int64[[2]] matrix, uint k, uint column)

D xor_uint8 selectK(D xor_uint8[[2]] matrix, uint k, uint column)

D xor_uint16 selectK(D xor_uint16[[2]] matrix, uint k, uint column)

D xor_uint32 selectK(D xor_uint32[[2]] matrix, uint k, uint column)

D xor_uint64 selectK(D xor_uint64[[2]] matrix, uint k, uint column)

sort

Functions for sorting values.

Functions:

sort[[1]]

sort[[2]]

D - shared3p protection domain

T - any data type

boolean values are sorted after their numerical value. false first then true

Shuffled reordering decisions are declassified

Leaks the number of equal elements

sort[[1]]

Function for sorting values in a vector.

Detailed Description

D - shared3p protection domain

returns a sorted vector from smaller to bigger values

Shuffled reordering decisions are declassified

Leaks the number of equal elements

Function Overloads

D bool sort(D bool[[1]] arr)

Supported types - bool

boolean values are sorted after their numerical value. false first then true

Parameters

arr	- a 1-dimensonal boolean vector

D T sort(D T[[1]] vec)

T - any data type

Parameters

vec	- a 1-dimensonal supported type vector

sort[[2]]

Function for sorting rows of a matrix based on values of a column.

Detailed Description

D - shared3p protection domain

returns a matrix where the input matrix rows are sorted based on values of the specified column

Shuffled reordering decisions are declassified

Leaks the number of equal elements

Function Overloads

D bool sort(D bool[[2]] matrix, uint column)

Supported types - bool

boolean values are sorted after their numerical value. false first then true

Parameters

column

- index of the column used for ordering

matrix

- a matrix of supported type

D T sort(D T[[2]] matrix, uint column)

T - any data type

Parameters

column

- index of the column used for ordering

matrix

- a matrix of supported type

sortingNetworkSort

Functions for sorting values with sorting networks.

Functions:

sortingNetworkSort[[1]]

sortingNetworkSort[[2]](1 column)

sortingNetworkSort[[2]](2 columns)

sortingNetworkSort[[2]](3 columns)

D - all protection domains

Supported types - uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64

None

sortingNetworkSort[[1]]

Function for sorting values in a vector with sorting network.

Detailed Description

D - all protection domains

Supported types - uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64

Parameters

array

- a vector of supported type

returns a sorted vector from smaller to bigger values

None

Function Overloads

D T sortingNetworkSort(D T[[1]] array)

sortingNetworkSort[[2]](1 column)

Function for sorting rows of a matrix based on values of a column.

Detailed Description

D - all protection domains

Supported types - uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64

Parameters

column

- index of the column used for ordering rows of the matrix

matrix

- a matrix of supported type

returns a matrix with sorted rows

None

Function Overloads

D uint8 sortingNetworkSort(D uint8[[2]] matrix, uint column)

D uint16 sortingNetworkSort(D uint16[[2]] matrix, uint column)

D uint32 sortingNetworkSort(D uint32[[2]] matrix, uint column)

D uint64 sortingNetworkSort(D uint64[[2]] matrix, uint column)

D int8 sortingNetworkSort(D int8[[2]] matrix, uint column)

D int16 sortingNetworkSort(D int16[[2]] matrix, uint column)

D int32 sortingNetworkSort(D int32[[2]] matrix, uint column)

D int64 sortingNetworkSort(D int64[[2]] matrix, uint column)

D xor_uint8 sortingNetworkSort(D xor_uint8[[2]] matrix, uint column)

D xor_uint16 sortingNetworkSort(D xor_uint16[[2]] matrix, uint column)

D xor_uint32 sortingNetworkSort(D xor_uint32[[2]] matrix, uint column)

D xor_uint64 sortingNetworkSort(D xor_uint64[[2]] matrix, uint column)

sortingNetworkSort[[2]](2 columns)

Function for sorting rows of a matrix based on values of two columns.

Detailed Description

D - all protection domains

Supported types - uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64

Parameters

column1

- index of the first column used for ordering

column2

- index of the second column used for ordering

matrix

- a matrix of supported type

returns a matrix where the rows of the input matrix have been sorted. For ordering two rows, the values in column1 are compared first, if they are equal then the values in column2 are compared.

None

Function Overloads

D uint8 sortingNetworkSort(D uint8[[2]] matrix, uint column1, uint column2)

D uint16 sortingNetworkSort(D uint16[[2]] matrix, uint column1, uint column2)

D uint32 sortingNetworkSort(D uint32[[2]] matrix, uint column1, uint column2)

D uint64 sortingNetworkSort(D uint64[[2]] matrix, uint column1, uint column2)

D int8 sortingNetworkSort(D int8[[2]] matrix, uint column1, uint column2)

D int16 sortingNetworkSort(D int16[[2]] matrix, uint column1, uint column2)

D int32 sortingNetworkSort(D int32[[2]] matrix, uint column1, uint column2)

D int64 sortingNetworkSort(D int64[[2]] matrix, uint column1, uint column2)

D xor_uint8 sortingNetworkSort(D xor_uint8[[2]] matrix, uint column1, uint column2)

D xor_uint16 sortingNetworkSort(D xor_uint16[[2]] matrix, uint column1, uint column2)

D xor_uint32 sortingNetworkSort(D xor_uint32[[2]] matrix, uint column1, uint column2)

D xor_uint64 sortingNetworkSort(D xor_uint64[[2]] matrix, uint column1, uint column2)

sortingNetworkSort[[2]](3 columns)

Function for sorting rows of a matrix based on values of three columns.

Detailed Description

D - all protection domains

Supported types - uint8 / uint16 / uint32 / uint / int8 / int16 / int32 / int / xor_uint8 / xor_uint16 / xor_uint32 / xor_uint64

Parameters

column1

- index of the first column used for ordering

column2

- index of the second column used for ordering

column3

- index of the third column used for ordering

matrix

- a matrix of supported type

returns a matrix where the rows of the input matrix have been sorted. For ordering two rows, the values in column1 are compared first, if they are equal then the values in column2 are compared, if they are equal then the values in column3 are compared.

None

Function Overloads

D uint8 sortingNetworkSort(D uint8[[2]] matrix, uint column1, uint column2, uint column3)

D uint16 sortingNetworkSort(D uint16[[2]] matrix, uint column1, uint column2, uint column3)

D uint32 sortingNetworkSort(D uint32[[2]] matrix, uint column1, uint column2, uint column3)

D uint64 sortingNetworkSort(D uint64[[2]] matrix, uint column1, uint column2, uint column3)

D int8 sortingNetworkSort(D int8[[2]] matrix, uint column1, uint column2, uint column3)

D int16 sortingNetworkSort(D int16[[2]] matrix, uint column1, uint column2, uint column3)

D int32 sortingNetworkSort(D int32[[2]] matrix, uint column1, uint column2, uint column3)

D int64 sortingNetworkSort(D int64[[2]] matrix, uint column1, uint column2, uint column3)

D xor_uint8 sortingNetworkSort(D xor_uint8[[2]] matrix, uint column1, uint column2, uint column3)

D xor_uint16 sortingNetworkSort(D xor_uint16[[2]] matrix, uint column1, uint column2, uint column3)

D xor_uint32 sortingNetworkSort(D xor_uint32[[2]] matrix, uint column1, uint column2, uint column3)

D xor_uint64 sortingNetworkSort(D xor_uint64[[2]] matrix, uint column1, uint column2, uint column3)