shared3p_string.sc

Module with string functions.

Functions:

CRC

CRC

Compute CRC hash of the input byte array with given initial hash.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

input

- the input byte vector

hash

- the initial hash of type xor_uint16 or xor_uint32

None

Function Overloads

D xor_uint16 CRC16(D xor_uint8[[N]] input, D xor_uint16 hash)

D xor_uint32 CRC32(D xor_uint8[[N]] input, D xor_uint32 hash)

CRC(0 initial hash)

Compute CRC hash of the input byte array with 0 initial hash.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

input

- the input byte vector

None

Function Overloads

D xor_uint16 CRC16(D xor_uint8[[N]] input)

D xor_uint32 CRC32(D xor_uint8[[N]] input)

cw128GenKey

Generates key for 128-bit Carter-Wegman hash.

Detailed Description

D - shared3p protection domain

Parameters

rowLen

- length of hash function input in bytes

None

Function Overloads

D xor_uint8 cw128GenKey(uint rowLen)

cw128Hash

Hashes values in the input vector into 128-bit hashes using the Carter-Wegman algorithm.

Detailed Description

D - shared3p protection domain

Parameters

data

- data vector

rowLen

- length of one data element in bytes

None

Function Overloads

D xor_uint8 cw128Hash(D xor_uint8[[1]] data, uint rowLen)

cw128Hash(key)

Hashes values in the input vector into 128-bit hashes using the Carter-Wegman algorithm.

Detailed Description

D - shared3p protection domain

Parameters

data

- data vector

key

- key used for hashing. See cw128GenKey cw128GenKey.

rowLen

- length of one data element in bytes

None

Function Overloads

D xor_uint8 cw128Hash(D xor_uint8[[1]] data, D xor_uint8[[1]] key, uint rowLen)

murmurHasherVec

murmurHash

Detailed Description

D - shared3p protection domain

Supported types - xor_uint32

None

Function Overloads

D xor_uint32 murmurHasherVec(D xor_uint32[[1]] hashee, public uint32[[1]] seed)

Parameters

hashee

- the string to be encrypted

seed

- the encryption seed

returns an encrypted version of hashee

shared3p_bl_string

Module with functions for bounded length strings.

Functions:

bl_strLessThan(parallel)

findSortingPermutation

tdbReadBlStringColumn

tdbVmapAddBlStringType

tdbVmapAddBlStringValue

tdbVmapGetBlString

zeroExtend

BlStringVector

bl_str

Convert a string to a vector of type xor_uint8.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Function Overloads

D xor_uint8 bl_str(string s, uint n)

returns a bounded length XOR shared string from the public string and the given bound

Parameters

- an uint type bound

- a string

the size of the given bound is no less than the length of the input string

the output string is of length n

the excess bytes in the shared string are placed in the end and are zeroed

D xor_uint8 bl_str(string s)

Parameters

s	- a string

returns a bounded length XOR shared string from the public string

the bounded length aligns with the actual length, no extra zeroed bytes are added

bl_str(struct)

Detailed Description

Parameters

- a string

- an uint type bound

returns a bounded length string vector created from the public string

the output string is of length n

the excess bytes in the shared string are placed in the end and are zeroed

Function Overloads

bl_str(string s, uint n)

bl_str(string s)

Parameters

s	- a string

returns a bounded length string vector created from the public string

bl_strCat

Function for concatenating two strings.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

s, t	- string vectors of supported type

returns a concatenation of the two input strings

None

Function Overloads

D xor_uint8 bl_strCat(D xor_uint8[[1]] s, D xor_uint8[[1]] t)

bl_strContains

function for checking if a string contains the given pattern

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

str

- input string vector of supported type

pat

- the pattern to look for

returns true if the given pattern is a substring of the given string

None

Function Overloads

D bool bl_strContains(D xor_uint8[[1]] str, D xor_uint8[[1]] pat)

bl_strDeclassify

Function for converting an array of type xor_uint8 to a string.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

ps	- a vector of supported type

returns a declassified bounded length string, extra bytes are removed

Leaks the input

Function Overloads

string bl_strDeclassify(D xor_uint8[[1]] ps)

string bl_strDeclassify(BlStringVector< D > str, uint i)

Parameters

str

- input string vector

- position of string to declassify

bl_strEmpty

Check if a bounded-length string vector contains empty strings.

Detailed Description

D - shared3p protection domain

Parameters

s	- input string vector

returns a boolean vector indicating if the string in the corresponding position in s was empty

None

Function Overloads

D bool bl_strEmpty(BlStringVector< D > s)

bl_strEqPrefixes

Function for checking whether a pattern is a substring of the input string.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

the pattern is not longer than the input string

Parameters

str

- input string vector of supported type

pat

- the pattern to look for

returns a boolean vector indicating if the pattern is a substring of the input string at that position

None

Function Overloads

D bool bl_strEqPrefixes(D xor_uint8[[1]] str, D xor_uint8[[1]] pat)

bl_strEquals

Compare two string with each other.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

s, t	- vectors of supported type

returns true if the two input strings are equal

None

Function Overloads

D bool bl_strEquals(D xor_uint8[[1]] s, D xor_uint8[[1]] t)

D bool bl_strEquals(BlStringVector< D > s, BlStringVector< D > t)

Performs pointwise equality comparison of bounded-length string vectors.

D - shared3p protection domain

Parameters

- string vector

returns a boolean indicating if the strings in the corresponding position in s and t were equal

None

bl_strFind

Searches for a string in a string vector.

Detailed Description

D - shared3p protection domain

Parameters

needle

- query string

haystack

- string vector

returns the index of the first occurence of needle in haystack if found and -1 otherwise

None

Function Overloads

D int64 bl_strFind(D xor_uint8[[1]] needle, BlStringVector< D > haystack)

bl_strHamming

Function for finding the number of bytes that the two input strings differ in.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

s, t	- input string vectors of supported type

returns the number of bytes that the inputs differ in

bl_strLength(s) == bl_strLength(t), otherwise the behaviour is undefined

None

Function Overloads

D uint bl_strHamming(D xor_uint8[[1]] s, D xor_uint8[[1]] t)

bl_strIndexOf

function for finding the index of a given pattern

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

str

- input string vector of supported type

pat

- the pattern to look for

returns the position where given pattern is contained in the string

if the string is not found returns value that is or equal to size (str)

None

Function Overloads

D uint bl_strIndexOf(D xor_uint8[[1]] str, D xor_uint8[[1]] pat)

bl_strIsEmpty

Check if the input string is empty.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

this is done by checking if all of the bytes in the string are zeroed

See bl_strEmpty for parallel version.

Parameters

s	- a vector of supported type

returns true if the given known length input string is empty

None

Function Overloads

D bool bl_strIsEmpty(D xor_uint8[[1]] s)

bl_strIsLessThan

function for comparing two strings alphabetically

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

See bl_strLessThan for parallel version.

Parameters

s, t	- input string vectors of supported type

returns true if s < t

None

Function Overloads

D bool bl_strIsLessThan(D xor_uint8[[1]] s, D xor_uint8[[1]] t)

bl_strLength

Function for finding the length of the given input string.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

s	- a vector of supported type

returns the actual length of the bounded lengthed input string

None

Function Overloads

D uint bl_strLength(D xor_uint8[[1]] s)

D uint bl_strLength(BlStringVector< D > s, uint i)

D - shared3p protection domain

param s - bounded-length string vector

param i - position of string

returns the actual length of the string at position i

None

bl_strLengthenBound

Increase the bound of a bounded-length string vector.

Detailed Description

D - shared3p protection domain

Parameters

- input string vector

biggerBound

- new bound

returns s with the bound increased to biggerBound

None

Function Overloads

bl_strLengthenBound(BlStringVector< D > s, uint biggerBound)

bl_strLessThan(parallel)

Compares two bounded-length string vectors point-wise.

Detailed Description

D - shared3p protection domain

Parameters

x, y	- input bounded-length string vectors

returns a boolean vector indicating if the element of x is less than the element of y in the corresponding position

None

Function Overloads

D bool bl_strLessThan(BlStringVector< D > x, BlStringVector< D > y)

bl_strLevenshtein

function for finding the edit distance of the two input strings

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

s, t	- input string vectors of supported type

returns the edit distance of the two input strings

the algorithm is almost identical to the known length one. The only difference is that the result is found somewhere in the middle of the 2D grid, and not in the bottom right corner. To find it we: a) compute a mask that’s one in that position and zero otherwise, b) multiply the mask with the grid, and c) return the sum of the result.

None

Function Overloads

D uint bl_strLevenshtein(D xor_uint8[[1]] s, D xor_uint8[[1]] t)

bl_strShuffle

Shuffle a bounded-length string vector.

Detailed Description

D - shared3p protection domain

Parameters

s	- input string vector

returns shuffled s

None

Function Overloads

bl_strShuffle(BlStringVector< D > s)

bl_strShuffle(key)

Shuffle a bounded-length string vector.

Detailed Description

D - shared3p protection domain

Parameters

- input string vector

sLen

- bound

key

- shuffle key

returns shuffled s

None

Function Overloads

bl_strShuffle(BlStringVector< D > s, D uint8[[1]] key)

bl_strTrim

Function for trimming a string.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

s	- a vector of supported type

returns a string with excess bytes removed

Leaks the length of the string

Function Overloads

D xor_uint8 bl_strTrim(D xor_uint8[[1]] s)

bl_strTrim(BlStringVector< D > s)

Trim a bounded-length string vector.

D - shared3p protection domain

Parameters

s	- bounded-length string vector.

returns input string vector with excess bytes removed

Leaks the length of the longest string

bl_strVectorLength

Calculate the length of a bounded-length string vector.

Detailed Description

D - shared3p protection domain

Parameters

s	- input string vector

returns the length of s

None

Function Overloads

uint bl_strVectorLength(BlStringVector< D > s)

countZeroes

Count zeroes in the input vector.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

s	- a vector of supported type

returns the number of 0 bytes in the input vector

None

Function Overloads

countZeroes(D xor_uint8[[1]] s)

findSortingPermutation

Function for finding a stable sorting permutation.

Detailed Description

D - shared3p protection domain

Supported types - bool

performs two vectorized multiplications

Parameters

arr	- a vector of supported type

returns a stable (in a sorting sense) permutation that moves false values to end

None

Function Overloads

D uint findSortingPermutation(D bool[[1]] arr)

tdbReadBlStringColumn

Read a bounded-length string vector from a table_database table.

Detailed Description

D - shared3p protection domain

Parameters

- data source name

table

- table name

col

- column index

returns the column of the table as a bounded-length string vector

None

Function Overloads

tdbReadBlStringColumn(string ds, string table, uint col)

tdbReadBlStringColumn(string ds, string table, string name)

Parameters

- data source name

table

- table name

name

- column name

tdbVmapAddBlStringType

Add bounded-length string type to a type vector in a table_database vector map.

Detailed Description

D - shared3p protection domain

Parameters

vmap

- vector map

domainProxy

- proxy value used to specify protection domain (actual value is not important)

bound

- string bound

None

Function Overloads

void tdbVmapAddBlStringType(uint vmap, D uint domainProxy, uint bound)

tdbVmapAddBlStringValue

Add a bounded-length string vector to a table_database vector map.

Detailed Description

D - shared3p protection domain

Parameters

params

- vector map

key

- key of vector in vector map

vec

- bounded length string vector

None

Function Overloads

void tdbVmapAddBlStringValue(uint params, string key, BlStringVector< D > vec)

tdbVmapGetBlString

Get bounded-length string vector from a table_database vector map.

Detailed Description

D - shared3p protection domain

Parameters

vmap

- vector map

string

- key of vector in vector map

idx

- index of bounded-length string vector in vector map vector

returns string vector in position idx

None

Function Overloads

tdbVmapGetBlString(uint vmap, string key, uint idx)

zeroExtend

Extend an input string with zeroes.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

- an input string

- minimum size that we want the resulting string to be

returns a vector that was created by zeroextending s

size (output vector) >= n

s is a prefix of the output vector

only zeroes have been added to the output vector

if size ( s ) >= n then the output vector == s

None

Function Overloads

D xor_uint8 zeroExtend(D xor_uint8[[1]] s, uint n)

BlStringVector

Bounded-length string vector type.

BlStringVector<domain D>

D xor_uint8

value

uint

bound

D - shared3p protection domain

shared3p_kl_string

Module with functions for known length strings.

Functions:

kl_str

Function for constructing a known length string from given public string.

Detailed Description

D - shared3p protection domain

Private strings are XOR shared to optimize for equality and comparison checks.

Parameters

s	- a string

XOR shared byte array of length equal to the input public string.

Function Overloads

D xor_uint8 kl_str(string s)

kl_strCat

Function for concatenating two strings.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

s, t	- string vectors of supported type

returns a concatenation of the two input strings

None

Function Overloads

D xor_uint8 kl_strCat(D xor_uint8[[1]] s, D xor_uint8[[1]] t)

kl_strContains

Function for checking whether a string contains a pattern or not.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

the needle is not longer than the haystack

Parameters

str

- the haystack

pat

- the needle

returns if the needle is found within the haystack

None

Function Overloads

D bool kl_strContains(D xor_uint8[[1]] str, D xor_uint8[[1]] pat)

kl_strDeclassify

Function for declassifying a given XOR shared byte string.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

ps	- a string vector of supported type

returns a public string

Leaks the input string

Function Overloads

string kl_strDeclassify(D xor_uint8[[1]] ps)

kl_strEqPrefixes

Function for checking whether a pattern is a substring of the input string.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

the pattern is not longer than the input string

Parameters

str

- the input string vector of supported type

pat

- the substring to look for

returns a boolean vector indicating if the pattern is a substring of the input string in that position

None

Function Overloads

D bool kl_strEqPrefixes(D xor_uint8[[1]] str, D xor_uint8[[1]] pat)

kl_strEquals

Function for checking whether two strings are equal.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

s, t	- string vectors of supported type

returns true if the input strings are equal, false it they are not

None

Function Overloads

D bool kl_strEquals(D xor_uint8[[1]] s, D xor_uint8[[1]] t)

kl_strHamming

Function for finding the number of bytes two inputs differ in.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

s, t	- input string vectors of supported type

the input strings are of equal length

returns the number of bytes that the inputs differ in

None

Function Overloads

D uint kl_strHamming(D xor_uint8[[1]] s, D xor_uint8[[1]] t)

kl_strIndexOf

Function for finding the index of a given pattern in the input string.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

the needle is not longer than the haystack

Parameters

str

- the haystack

pat

- the needle

returns the position of the needle in the haystack

returns size(str) if the pat is not a substring of str

None

Function Overloads

D uint kl_strIndexOf(D xor_uint8[[1]] str, D xor_uint8[[1]] pat)

kl_strIsLessThan

Function for comparing two strings alphabetically.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

s, t	- string vectors of supported type

returns true if the first input string is less than the second (in dictionary order)

None

Function Overloads

D bool kl_strIsLessThan(D xor_uint8[[1]] s, D xor_uint8[[1]] t)

kl_strLength

Function for getting the length of a string.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

Parameters

str	- a string vector of supported type

returns a length of the string

None

Function Overloads

uint kl_strLength(D xor_uint8[[1]] str)

kl_strLevenshtein

Function for finding the edit distance of two input strings.

Detailed Description

D - shared3p protection domain

Supported types - xor_uint8

this is the classic dynamic programming implementation of Levenshtein distance that’s simply tuned to minimize the number of the "min" syscalls. Naive approach would invoke "min" O(n*m) times for strings of length n and m. The following implementation invokes the syscall O(n+m) times by computing the table diagonal at a time.

Parameters

s, t	- input string vectors of supported type

returns the edit distance of the two input strings

None

Function Overloads

D uint kl_strLevenshtein(D xor_uint8[[1]] s, D xor_uint8[[1]] t)