#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#ifndef MYALGORITHMS_H
#define MYALGORITHMS_H
#include <stdlib.h>
#define STRINGIZE(x) #x
/* Bitwise operations */
#define setbit(number, bit) ((number) |= 1 << (bit))
#define clearbit(number, bit) ((number) &= ~(1 << (bit)))
#define switchbit(number, bit) ((number) ^= 1 << (bit))
#define checkbit(number, bit) ((number) & (1 << bit))
typedef struct NODE* link;
typedef struct NODE {
int data;
link next;
} NODE;
char* repr_array(const int* A, const size_t N);
void print_array(const int* A, const size_t N);
void insertion_sort(int* A, const size_t N);
void insertion_sort_2(int* A, const size_t N);
int randrange(unsigned int n);
int random_in_range(unsigned int min, unsigned int max);
int rand_range(unsigned int n);
inline void swap(void* A, void* B, size_t bytes);
void shuffle(void* A, size_t membercount, size_t membersize);
void my_bubble_sort(int* A, const size_t N);
void bubble_sort(int* A, const size_t N);
void selection_sort(int* A, const size_t N);
void merge(int* left, int n_left, int* right, int n_right, int* out);
void recurse(int* A, int* temp, int N);
void merge_sort(int* A, int N);
int* range(size_t N);
inline void reverse(void* sequence, const size_t membercount, const size_t membersize);
void test_reverse(void);
char* getstring(void);
int getinteger(void);
void sort_trial(void);
link insert_node(link A, link newnode);
int delete_node(link A, link unwanted_node);
int pop_node(link list);
link append_node(link list, link newnode);
void print_node(link node);
void traverse_list(link node);
link reverse_list(link head);
link create_empty_node(void);
link append_new_node(link tail, int data);
link create_list_from_array(const int* A, const size_t N);
size_t list_length(NODE const *list);
void delete_list(link head);
inline void swap_node(link A, link B);
link getnode(const link head, size_t N);
void* list_to_array(NODE const *list, const size_t list_length, const size_t data_size);
link* create_link_array(link head, size_t length);
inline int cmp_int_asc(const void* A, const void* B);
inline int cmp_int_desc(const void* A, const void* B);
/* Generic insertion sort algorithm. */
#define isort(base, num, size, comparator) \
{ \
void *left, *right, *key; \
if ((key = malloc(size))) \
{ \
for (right = (base + size); ((size_t) right - (size_t) base)/size < num; right += size) \
{ \
memcpy(key, right, size); \
for (left = right; (size_t) left > (size_t) base && comparator((left - size), key) > 0; left -= size) \
{ \
memcpy(left, left - size, size); \
} \
memcpy(left, key, size); \
} \
free(key); \
} \
}
#endif // MYALGORITHMS_H
#define PLACES_MAX (strlen(STRINGIZE(INT_MAX)) + 1)
#define ARRLEN(A) (sizeof(A) / sizeof(0[A]))
char* repr_array(const int* A, const size_t N)
{
char* result;
size_t len_result, p;
#define ARRAY_BEGIN '['
#define DELIMITERS ", "
#define ARRAY_END "]"
result = NULL;
len_result
= ((N
- 1) * (PLACES_MAX
+ strlen(DELIMITERS
))) + PLACES_MAX
; len_result += 3;
if ((result
= realloc(result
, sizeof(*result
) * len_result
))) {
char* s;
s = result + 1;
result[0] = ARRAY_BEGIN;
for (p = 0; p < (N-1); ++p)
{
s
+= sprintf(s
, "%d"DELIMITERS
, A
[p
]); }
}
else
{
fprintf(stderr
, "\n%s\n", "repr_array malloc failed: out of memory."); }
return result;
#undef ARRAY_END
#undef DELIMITERS
#undef ARRAY_BEGIN
}
void print_array(const int* A, const size_t N)
{
char* a = repr_array(A, N);
}
void insertion_sort(int* A, const size_t N)
{
size_t i, j;
int key;
for (i = 1; i < N; ++i)
{
key = A[i];
for (j = i; j > 0 && A[j - 1] > key; --j)
{
A[j] = A[j - 1];
}
A[j] = key;
}
}
void insertion_sort_2(int* A, const size_t N)
{
size_t i, j;
int key;
for (i = 1; i < N; ++i)
{
//key = A[i];
memcpy(&key
, A
+i
, sizeof(*A
)); for (j = i; j > 0 && A[j - 1] > key; --j)
{
//A[j] = A[j - 1];
memcpy(A
+j
, A
+j
-1, sizeof(*A
)); }
//A[j] = key;
memcpy(A
+j
, &key
, sizeof(*A
)); }
}
int randrange(unsigned int n)
{
int randint, rand_max;
rand_max = RAND_MAX - (RAND_MAX % n);
while ((randint
= rand()) >= rand_max
); return randint / (rand_max / n);
}
int random_in_range(unsigned int min, unsigned int max)
{
int base_random, range, remainder, bucket;
if (RAND_MAX == base_random)
{
return random_in_range(min, max);
}
range = max - min;
remainder = RAND_MAX % range;
bucket = RAND_MAX / range;
if (base_random < (RAND_MAX - remainder))
{
return min + (base_random / bucket);
}
else
{
return random_in_range(min, max);
}
}
int rand_range(unsigned int n)
{
return random_in_range(0, n);
}
inline void swap(void* A, void* B, size_t bytes)
{
void* temp;
if (temp)
{
}
}
void shuffle(void* A, size_t membercount, size_t membersize)
{
size_t k;
while (membercount > 1)
{
k = rand_range(membercount);
--membercount;
swap(A + (membercount * membersize), A + (k * membersize), membersize);
}
}
void my_bubble_sort(int* A, const size_t N)
{
size_t i, j;
int *keydex, *next;
for (i = 0; i < N; ++i)
{
for (j = 0; j < (N - i - 1); ++j)
{
keydex = A + j;
next = keydex + 1;
if (*keydex > *next)
{
swap(keydex, next, sizeof(*A));
}
}
}
}
void bubble_sort(int* A, const size_t N)
{
int n, i, newn;
n = N;
do
{
newn = 0;
for (i = 1; i < n; ++i)
{
if (A[i-1] > A[i])
{
swap(A + i - 1, A + i, sizeof(*A));
newn = i;
}
}
n = newn;
} while (n > 0);
}
void selection_sort(int* A, const size_t N)
{
int *keydex, *mindex, *index;
for (keydex = A; keydex - N < A; ++keydex)
{
mindex = keydex;
for (index = (keydex + 1); index < (A + N); ++index)
{
if (*index < *mindex)
{
mindex = index;
}
}
if (keydex != mindex)
{
swap(keydex, mindex, sizeof(*A));
}
}
}
void merge(int* left, int n_left, int* right, int n_right, int* out)
{
int i, j, k;
for (i = j = k = 0; i < n_left && j < n_right; ++k)
{
if (left[i] < right[j])
{
out[k] = left[i];
++i;
}
else
{
out[k] = right[j];
++j;
}
}
while (i < n_left)
{
out[k] = left[i];
++i;
++k;
}
while (j < n_right)
{
out[k] = right[j];
++j;
++k;
}
}
void recurse(int* A, int* temp, int N)
{
int mid;
mid = N / 2;
if (N <= 1)
{
return;
}
recurse(temp, A, mid);
recurse(temp + mid, A + mid, N - mid);
merge(temp, mid, temp + mid, N - mid, A);
}
void merge_sort(int* A, int N)
{
int* temp;
temp
= malloc(sizeof(*A
) * N
); if (temp)
{
memcpy(temp
, A
, sizeof(*A
) * N
); recurse(A, temp, N);
}
}
/*typedef void(*sorting_algorithm)(int*, size_t);
void test_sorting_algorithm(int* A, const size_t N, sorting_algorithm sort, const char* sort_name)
{
printf("Before %s: ", sort_name);
print_array(A, N);
sort(A, N);
printf("After %s: ", sort_name);
print_array(A, N);
}*/
#define test_sorting_algorithm(A, N, sort, sort_name) \
{ \
printf("Before %s: ", sort_name); \
print_array(A, N); \
sort(A, N); \
printf("After %s: ", sort_name); \
print_array(A, N); \
}
#define test_sort(A, N, name) test_sorting_algorithm(A, N, name, STRINGIZE(name))
int* range(size_t N)
{
int* result;
if ((result
= malloc(sizeof(*result
) * N
))) {
int* i, num;
num = 0;
for (i = result; i < (result + N); ++i)
{
*i = num;
++num;
}
}
return result;
}
inline void reverse(void* sequence, const size_t membercount, const size_t membersize)
{
void *left, *right;
right = sequence + ((membercount - 1) * membersize);
left = sequence;
while (left < right)
{
swap(left, right, membersize);
left += membersize;
right -= membersize;
}
}
void test_reverse(void)
{
int* A = range(10);
reverse(A, 10, sizeof(*A));
print_array(A, 10);
}
char* getstring(void)
{
char* strbuffer = NULL;
size_t strbuffercapacity = 0;
size_t strbuffercharcount = 0;
int character;
while ((character
= fgetc(stdin
)) != '\n' && character
!= EOF
) {
if (strbuffercharcount + 1 > strbuffercapacity)
{
if (strbuffercapacity == 0)
{
strbuffercapacity = sizeof(char) * 4;
}
else if (strbuffercapacity < (UINT_MAX / 2))
{
strbuffercapacity *= 2;
}
else
{
return NULL;
}
char* tempbuffer
= realloc(strbuffer
, sizeof(char) * strbuffercapacity
); if (tempbuffer == NULL)
{
return NULL;
}
else
{
strbuffer = tempbuffer;
}
}
strbuffer[strbuffercharcount] = character;
++strbuffercharcount;
}
if (strbuffercharcount == 0 && character == EOF)
{
return NULL;
}
char* minstrbuffer
= malloc(sizeof(char) * (strbuffercharcount
+ 1)); strncpy(minstrbuffer
, strbuffer
, strbuffercharcount
); minstrbuffer[strbuffercharcount] = '\0';
return minstrbuffer;
}
int getinteger(void)
{
for(;;)
{
char* integers = getstring();
if (integers == NULL)
{
return INT_MAX;
}
int integer;
char character;
if (sscanf(integers
, " %d %c", &integer
, &character
) == 1) {
return integer;
}
else
{
}
}
}
void sort_trial(void)
{
int LEN, choice;
printf("Enter the size of the integer array you want: "); LEN = getinteger();
int* A = range(LEN);
printf("\n1. Random array\n2. Reversed array\n3. Sorted array\n"); choice = getinteger();
switch (choice)
{
case 1:
shuffle(A, LEN, sizeof(*A));
break;
case 2:
reverse(A, LEN, sizeof(*A));
break;
case 3:
break;
default:
break;
}
printf("\n1. Insertion sort\n2. Bubble sort 1\n3. Bubble sort 2\n4. Selection sort\n"); choice = getinteger();
switch (choice)
{
case 1:
test_sort(A, LEN, insertion_sort);
break;
case 2:
test_sort(A, LEN, my_bubble_sort);
break;
case 3:
test_sort(A, LEN, bubble_sort);
break;
case 4:
test_sort(A, LEN, selection_sort);
break;
default:
break;
}
}
link insert_node(link A, link newnode)
{
newnode->next = A->next;
A->next = newnode;
return newnode;
}
int delete_node(link A, link unwanted_node)
{
int data;
A->next = unwanted_node->next;
data = unwanted_node->data;
return data;
}
int pop_node(link list)
{
int data;
while (list->next)
{
list = list->next;
}
data = list->data;
return data;
}
link append_node(link list, link newnode)
{
while (list->next)
{
list = list->next;
}
insert_node(list, newnode);
return newnode;
}
void print_node(link node)
{
printf("%p [%d] -> %p\n", node
, node
->data
, node
->next
); }
void traverse_list(link node)
{
for (; node->next; node = node->next)
{
print_node(node);
}
print_node(node);
}
link reverse_list(link head)
{
link new_head, next;
new_head = NULL;
while (head)
{
next = head->next;
head->next = new_head;
new_head = head;
head = next;
}
return new_head;
}
link create_empty_node(void)
{
}
link append_new_node(link tail, int data)
{
link newnode;
newnode = create_empty_node();
newnode->data = data;
append_node(tail, newnode);
return tail->next;
}
link create_list_from_array(const int* A, const size_t N)
{
link head, tail;
size_t end;
head = create_empty_node();
if (head)
{
head->data = *A;
++A;
tail = head;
tail->next = NULL;
for (end = (size_t) (A + N - 1); (size_t) A < end; ++A)
{
tail = append_new_node(tail, *A);
}
}
return head;
}
size_t list_length(NODE const *list)
{
size_t length;
length = 0;
while (list)
{
list = list->next;
++length;
}
return length;
}
void delete_list(link head)
{
while (head->next)
{
delete_node(head, head->next);
}
}
inline void swap_node(link A, link B)
{
swap(A, B, sizeof(link));
}
link getnode(const link head, size_t N)
{
link node;
node = head;
size_t index;
index = 0;
while (index < N)
{
node = node->next;
++index;
}
return node;
}
void* list_to_array(NODE const *list, const size_t list_length, const size_t data_size)
{
void* array;
array
= malloc(data_size
* list_length
); if (array)
{
void* block;
size_t index;
index = 0;
block = array;
while (index < list_length)
{
memcpy(block
, &(list
->data
), data_size
); block += data_size;
list = list->next;
++index;
}
}
return array;
}
link* create_link_array(link head, size_t length)
{
link *array, *ptr;
array
= malloc(sizeof(*array
) * length
); ptr = array;
while (head->next)
{
*ptr = head;
++ptr;
head = head->next;
}
return array;
}
/*void isort(void* base, size_t num, size_t size, int (*comparator) (const void*, const void*))
{
void *left, *right, *key;
if ((key = malloc(size)))
{
for (right = (base + size); ((size_t) right - (size_t) base)/size < num; right += size)
{
memcpy(key, right, size);
for (left = right; (size_t) left > (size_t) base && comparator((left - size), key) > 0; left -= size)
{
memcpy(left, left - size, size);
}
memcpy(left, key, size);
}
free(key);
}
}*/
inline int cmp_int_asc(const void* A, const void* B)
{
int I = *((int*) A);
int J = *((int*) B);
return I < J ? -1 : I > J;
}
inline int cmp_int_desc(const void* A, const void* B)
{
int I = *((int*) A);
int J = *((int*) B);
return I > J ? -1 : I < J;
}
int main(void)
{
int A[] = {9,8,7,6,5,4,3,2,1,0};
print_array(A, 10);
insertion_sort(A, 10);
print_array(A, 10);
return 0;
}
I2luY2x1ZGUgPGxpbWl0cy5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8c3RyaW5nLmg+CiNpbmNsdWRlIDx0aW1lLmg+CiNpZm5kZWYgTVlBTEdPUklUSE1TX0gKI2RlZmluZSBNWUFMR09SSVRITVNfSAoKI2luY2x1ZGUgPHN0ZGxpYi5oPgoKI2RlZmluZSBTVFJJTkdJWkUoeCkgI3gKCi8qIEJpdHdpc2Ugb3BlcmF0aW9ucyAqLwojZGVmaW5lIHNldGJpdChudW1iZXIsIGJpdCkgKChudW1iZXIpIHw9IDEgPDwgKGJpdCkpCiNkZWZpbmUgY2xlYXJiaXQobnVtYmVyLCBiaXQpICgobnVtYmVyKSAmPSB+KDEgPDwgKGJpdCkpKQojZGVmaW5lIHN3aXRjaGJpdChudW1iZXIsIGJpdCkgKChudW1iZXIpIF49IDEgPDwgKGJpdCkpCiNkZWZpbmUgY2hlY2tiaXQobnVtYmVyLCBiaXQpICgobnVtYmVyKSAmICgxIDw8IGJpdCkpCgp0eXBlZGVmIHN0cnVjdCBOT0RFKiBsaW5rOwp0eXBlZGVmIHN0cnVjdCBOT0RFIHsKICAgIGludCBkYXRhOwogICAgbGluayBuZXh0Owp9IE5PREU7CgpjaGFyKiByZXByX2FycmF5KGNvbnN0IGludCogQSwgY29uc3Qgc2l6ZV90IE4pOwp2b2lkIHByaW50X2FycmF5KGNvbnN0IGludCogQSwgY29uc3Qgc2l6ZV90IE4pOwp2b2lkIGluc2VydGlvbl9zb3J0KGludCogQSwgY29uc3Qgc2l6ZV90IE4pOwp2b2lkIGluc2VydGlvbl9zb3J0XzIoaW50KiBBLCBjb25zdCBzaXplX3QgTik7CmludCByYW5kcmFuZ2UodW5zaWduZWQgaW50IG4pOwppbnQgcmFuZG9tX2luX3JhbmdlKHVuc2lnbmVkIGludCBtaW4sIHVuc2lnbmVkIGludCBtYXgpOwppbnQgcmFuZF9yYW5nZSh1bnNpZ25lZCBpbnQgbik7CmlubGluZSB2b2lkIHN3YXAodm9pZCogQSwgdm9pZCogQiwgc2l6ZV90IGJ5dGVzKTsKdm9pZCBzaHVmZmxlKHZvaWQqIEEsIHNpemVfdCBtZW1iZXJjb3VudCwgc2l6ZV90IG1lbWJlcnNpemUpOwp2b2lkIG15X2J1YmJsZV9zb3J0KGludCogQSwgY29uc3Qgc2l6ZV90IE4pOwp2b2lkIGJ1YmJsZV9zb3J0KGludCogQSwgY29uc3Qgc2l6ZV90IE4pOwp2b2lkIHNlbGVjdGlvbl9zb3J0KGludCogQSwgY29uc3Qgc2l6ZV90IE4pOwp2b2lkIG1lcmdlKGludCogbGVmdCwgaW50IG5fbGVmdCwgaW50KiByaWdodCwgaW50IG5fcmlnaHQsIGludCogb3V0KTsKdm9pZCByZWN1cnNlKGludCogQSwgaW50KiB0ZW1wLCBpbnQgTik7CnZvaWQgbWVyZ2Vfc29ydChpbnQqIEEsIGludCBOKTsKaW50KiByYW5nZShzaXplX3QgTik7CmlubGluZSB2b2lkIHJldmVyc2Uodm9pZCogc2VxdWVuY2UsIGNvbnN0IHNpemVfdCBtZW1iZXJjb3VudCwgY29uc3Qgc2l6ZV90IG1lbWJlcnNpemUpOwp2b2lkIHRlc3RfcmV2ZXJzZSh2b2lkKTsKY2hhciogZ2V0c3RyaW5nKHZvaWQpOwppbnQgZ2V0aW50ZWdlcih2b2lkKTsKdm9pZCBzb3J0X3RyaWFsKHZvaWQpOwpsaW5rIGluc2VydF9ub2RlKGxpbmsgQSwgbGluayBuZXdub2RlKTsKaW50IGRlbGV0ZV9ub2RlKGxpbmsgQSwgbGluayB1bndhbnRlZF9ub2RlKTsKaW50IHBvcF9ub2RlKGxpbmsgbGlzdCk7CmxpbmsgYXBwZW5kX25vZGUobGluayBsaXN0LCBsaW5rIG5ld25vZGUpOwp2b2lkIHByaW50X25vZGUobGluayBub2RlKTsKdm9pZCB0cmF2ZXJzZV9saXN0KGxpbmsgbm9kZSk7CmxpbmsgcmV2ZXJzZV9saXN0KGxpbmsgaGVhZCk7CmxpbmsgY3JlYXRlX2VtcHR5X25vZGUodm9pZCk7CmxpbmsgYXBwZW5kX25ld19ub2RlKGxpbmsgdGFpbCwgaW50IGRhdGEpOwpsaW5rIGNyZWF0ZV9saXN0X2Zyb21fYXJyYXkoY29uc3QgaW50KiBBLCBjb25zdCBzaXplX3QgTik7CnNpemVfdCBsaXN0X2xlbmd0aChOT0RFIGNvbnN0ICpsaXN0KTsKdm9pZCBkZWxldGVfbGlzdChsaW5rIGhlYWQpOwppbmxpbmUgdm9pZCBzd2FwX25vZGUobGluayBBLCBsaW5rIEIpOwpsaW5rIGdldG5vZGUoY29uc3QgbGluayBoZWFkLCBzaXplX3QgTik7CnZvaWQqIGxpc3RfdG9fYXJyYXkoTk9ERSBjb25zdCAqbGlzdCwgY29uc3Qgc2l6ZV90IGxpc3RfbGVuZ3RoLCBjb25zdCBzaXplX3QgZGF0YV9zaXplKTsKbGluayogY3JlYXRlX2xpbmtfYXJyYXkobGluayBoZWFkLCBzaXplX3QgbGVuZ3RoKTsKaW5saW5lIGludCBjbXBfaW50X2FzYyhjb25zdCB2b2lkKiBBLCBjb25zdCB2b2lkKiBCKTsKaW5saW5lIGludCBjbXBfaW50X2Rlc2MoY29uc3Qgdm9pZCogQSwgY29uc3Qgdm9pZCogQik7CgovKiBHZW5lcmljIGluc2VydGlvbiBzb3J0IGFsZ29yaXRobS4gKi8KI2RlZmluZSBpc29ydChiYXNlLCBudW0sIHNpemUsIGNvbXBhcmF0b3IpIFwKeyBcCiAgICB2b2lkICpsZWZ0LCAqcmlnaHQsICprZXk7IFwKICAgIGlmICgoa2V5ID0gbWFsbG9jKHNpemUpKSkgXAogICAgeyBcCiAgICAgICAgZm9yIChyaWdodCA9IChiYXNlICsgc2l6ZSk7ICgoc2l6ZV90KSByaWdodCAtIChzaXplX3QpIGJhc2UpL3NpemUgPCBudW07IHJpZ2h0ICs9IHNpemUpIFwKICAgICAgICB7IFwKICAgICAgICAgICAgbWVtY3B5KGtleSwgcmlnaHQsIHNpemUpOyBcCiAgICAgICAgICAgIGZvciAobGVmdCA9IHJpZ2h0OyAoc2l6ZV90KSBsZWZ0ID4gKHNpemVfdCkgYmFzZSAmJiBjb21wYXJhdG9yKChsZWZ0IC0gc2l6ZSksIGtleSkgPiAwOyBsZWZ0IC09IHNpemUpIFwKICAgICAgICAgICAgeyBcCiAgICAgICAgICAgICAgICBtZW1jcHkobGVmdCwgbGVmdCAtIHNpemUsIHNpemUpOyBcCiAgICAgICAgICAgIH0gXAogICAgICAgICAgICBtZW1jcHkobGVmdCwga2V5LCBzaXplKTsgXAogICAgICAgIH0gXAogICAgICAgIGZyZWUoa2V5KTsgXAogICAgfSBcCn0KCiNlbmRpZiAvLyBNWUFMR09SSVRITVNfSAoKCgoKI2RlZmluZSBQTEFDRVNfTUFYIChzdHJsZW4oU1RSSU5HSVpFKElOVF9NQVgpKSArIDEpCiNkZWZpbmUgQVJSTEVOKEEpIChzaXplb2YoQSkgLyBzaXplb2YoMFtBXSkpCgpjaGFyKiByZXByX2FycmF5KGNvbnN0IGludCogQSwgY29uc3Qgc2l6ZV90IE4pCnsKICAgIGNoYXIqIHJlc3VsdDsKICAgIHNpemVfdCBsZW5fcmVzdWx0LCBwOwojZGVmaW5lIEFSUkFZX0JFR0lOICdbJwojZGVmaW5lIERFTElNSVRFUlMgIiwgIgojZGVmaW5lIEFSUkFZX0VORCAiXSIKICAgIHJlc3VsdCA9IE5VTEw7CiAgICBsZW5fcmVzdWx0ID0gKChOIC0gMSkgKiAoUExBQ0VTX01BWCArIHN0cmxlbihERUxJTUlURVJTKSkpICsgUExBQ0VTX01BWDsKICAgIGxlbl9yZXN1bHQgKz0gMzsKICAgIGlmICgocmVzdWx0ID0gcmVhbGxvYyhyZXN1bHQsIHNpemVvZigqcmVzdWx0KSAqIGxlbl9yZXN1bHQpKSkKICAgIHsKICAgICAgICBjaGFyKiBzOwogICAgICAgIHMgPSByZXN1bHQgKyAxOwogICAgICAgIHJlc3VsdFswXSA9IEFSUkFZX0JFR0lOOwogICAgICAgIGZvciAocCA9IDA7IHAgPCAoTi0xKTsgKytwKQogICAgICAgIHsKICAgICAgICAgICAgcyArPSBzcHJpbnRmKHMsICIlZCJERUxJTUlURVJTLCBBW3BdKTsKICAgICAgICB9CiAgICAgICAgc3ByaW50ZihzLCAiJWQiQVJSQVlfRU5ELCBBW3BdKTsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBmcHJpbnRmKHN0ZGVyciwgIlxuJXNcbiIsICJyZXByX2FycmF5IG1hbGxvYyBmYWlsZWQ6IG91dCBvZiBtZW1vcnkuIik7CiAgICB9CiAgICByZXR1cm4gcmVzdWx0OwojdW5kZWYgQVJSQVlfRU5ECiN1bmRlZiBERUxJTUlURVJTCiN1bmRlZiBBUlJBWV9CRUdJTgp9Cgp2b2lkIHByaW50X2FycmF5KGNvbnN0IGludCogQSwgY29uc3Qgc2l6ZV90IE4pCnsKICAgIGNoYXIqIGEgPSByZXByX2FycmF5KEEsIE4pOwogICAgcHJpbnRmKCIlc1xuIiwgYSk7CiAgICBmcmVlKGEpOwp9Cgp2b2lkIGluc2VydGlvbl9zb3J0KGludCogQSwgY29uc3Qgc2l6ZV90IE4pCnsKICAgIHNpemVfdCBpLCBqOwogICAgaW50IGtleTsKICAgIGZvciAoaSA9IDE7IGkgPCBOOyArK2kpCiAgICB7CiAgICAgICAga2V5ID0gQVtpXTsKICAgICAgICBmb3IgKGogPSBpOyBqID4gMCAmJiBBW2ogLSAxXSA+IGtleTsgLS1qKQogICAgICAgIHsKICAgICAgICAgICAgQVtqXSA9IEFbaiAtIDFdOwogICAgICAgIH0KICAgICAgICBBW2pdID0ga2V5OwogICAgfQp9Cgp2b2lkIGluc2VydGlvbl9zb3J0XzIoaW50KiBBLCBjb25zdCBzaXplX3QgTikKewogICAgc2l6ZV90IGksIGo7CiAgICBpbnQga2V5OwogICAgZm9yIChpID0gMTsgaSA8IE47ICsraSkKICAgIHsKICAgICAgICAvL2tleSA9IEFbaV07CiAgICAgICAgbWVtY3B5KCZrZXksIEEraSwgc2l6ZW9mKCpBKSk7CiAgICAgICAgZm9yIChqID0gaTsgaiA+IDAgJiYgQVtqIC0gMV0gPiBrZXk7IC0taikKICAgICAgICB7CiAgICAgICAgICAgIC8vQVtqXSA9IEFbaiAtIDFdOwogICAgICAgICAgICBtZW1jcHkoQStqLCBBK2otMSwgc2l6ZW9mKCpBKSk7CiAgICAgICAgfQogICAgICAgIC8vQVtqXSA9IGtleTsKICAgICAgICBtZW1jcHkoQStqLCAma2V5LCBzaXplb2YoKkEpKTsKICAgIH0KfQoKaW50IHJhbmRyYW5nZSh1bnNpZ25lZCBpbnQgbikKewogICAgaW50IHJhbmRpbnQsIHJhbmRfbWF4OwogICAgcmFuZF9tYXggPSBSQU5EX01BWCAtIChSQU5EX01BWCAlIG4pOwogICAgd2hpbGUgKChyYW5kaW50ID0gcmFuZCgpKSA+PSByYW5kX21heCk7CiAgICByZXR1cm4gcmFuZGludCAvIChyYW5kX21heCAvIG4pOwp9CgppbnQgcmFuZG9tX2luX3JhbmdlKHVuc2lnbmVkIGludCBtaW4sIHVuc2lnbmVkIGludCBtYXgpCnsKICAgIGludCBiYXNlX3JhbmRvbSwgcmFuZ2UsIHJlbWFpbmRlciwgYnVja2V0OwogICAgYmFzZV9yYW5kb20gPSByYW5kKCk7CiAgICBpZiAoUkFORF9NQVggPT0gYmFzZV9yYW5kb20pCiAgICB7CiAgICAgICAgcmV0dXJuIHJhbmRvbV9pbl9yYW5nZShtaW4sIG1heCk7CiAgICB9CiAgICByYW5nZSA9IG1heCAtIG1pbjsKICAgIHJlbWFpbmRlciA9IFJBTkRfTUFYICUgcmFuZ2U7CiAgICBidWNrZXQgPSBSQU5EX01BWCAvIHJhbmdlOwoKICAgIGlmIChiYXNlX3JhbmRvbSA8IChSQU5EX01BWCAtIHJlbWFpbmRlcikpCiAgICB7CiAgICAgICAgcmV0dXJuIG1pbiArIChiYXNlX3JhbmRvbSAvIGJ1Y2tldCk7CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgcmV0dXJuIHJhbmRvbV9pbl9yYW5nZShtaW4sIG1heCk7CiAgICB9Cn0KCmludCByYW5kX3JhbmdlKHVuc2lnbmVkIGludCBuKQp7CiAgICByZXR1cm4gcmFuZG9tX2luX3JhbmdlKDAsIG4pOwp9CgppbmxpbmUgdm9pZCBzd2FwKHZvaWQqIEEsIHZvaWQqIEIsIHNpemVfdCBieXRlcykKewogICAgdm9pZCogdGVtcDsKICAgIHRlbXAgPSBtYWxsb2MoYnl0ZXMpOwogICAgaWYgKHRlbXApCiAgICB7CiAgICAgICAgbWVtY3B5KHRlbXAsIEEsIGJ5dGVzKTsKICAgICAgICBtZW1jcHkoQSwgQiwgYnl0ZXMpOwogICAgICAgIG1lbWNweShCLCB0ZW1wLCBieXRlcyk7CiAgICAgICAgZnJlZSh0ZW1wKTsKICAgIH0KfQoKdm9pZCBzaHVmZmxlKHZvaWQqIEEsIHNpemVfdCBtZW1iZXJjb3VudCwgc2l6ZV90IG1lbWJlcnNpemUpCnsKICAgIHNpemVfdCBrOwogICAgd2hpbGUgKG1lbWJlcmNvdW50ID4gMSkKICAgIHsKICAgICAgICBrID0gcmFuZF9yYW5nZShtZW1iZXJjb3VudCk7CiAgICAgICAgLS1tZW1iZXJjb3VudDsKICAgICAgICBzd2FwKEEgKyAobWVtYmVyY291bnQgKiBtZW1iZXJzaXplKSwgQSArIChrICogbWVtYmVyc2l6ZSksIG1lbWJlcnNpemUpOwogICAgfQp9Cgp2b2lkIG15X2J1YmJsZV9zb3J0KGludCogQSwgY29uc3Qgc2l6ZV90IE4pCnsKICAgIHNpemVfdCBpLCBqOwogICAgaW50ICprZXlkZXgsICpuZXh0OwogICAgZm9yIChpID0gMDsgaSA8IE47ICsraSkKICAgIHsKICAgICAgICBmb3IgKGogPSAwOyBqIDwgKE4gLSBpIC0gMSk7ICsraikKICAgICAgICB7CiAgICAgICAgICAgIGtleWRleCA9IEEgKyBqOwogICAgICAgICAgICBuZXh0ID0ga2V5ZGV4ICsgMTsKICAgICAgICAgICAgaWYgKCprZXlkZXggPiAqbmV4dCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgc3dhcChrZXlkZXgsIG5leHQsIHNpemVvZigqQSkpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9Cgp2b2lkIGJ1YmJsZV9zb3J0KGludCogQSwgY29uc3Qgc2l6ZV90IE4pCnsKICAgIGludCBuLCBpLCBuZXduOwogICAgbiA9IE47CiAgICBkbwogICAgewogICAgICAgIG5ld24gPSAwOwogICAgICAgIGZvciAoaSA9IDE7IGkgPCBuOyArK2kpCiAgICAgICAgewogICAgICAgICAgICBpZiAoQVtpLTFdID4gQVtpXSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgc3dhcChBICsgaSAtIDEsIEEgKyBpLCBzaXplb2YoKkEpKTsKICAgICAgICAgICAgICAgIG5ld24gPSBpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIG4gPSBuZXduOwogICAgfSB3aGlsZSAobiA+IDApOwp9Cgp2b2lkIHNlbGVjdGlvbl9zb3J0KGludCogQSwgY29uc3Qgc2l6ZV90IE4pCnsKICAgIGludCAqa2V5ZGV4LCAqbWluZGV4LCAqaW5kZXg7CiAgICBmb3IgKGtleWRleCA9IEE7IGtleWRleCAtIE4gPCBBOyArK2tleWRleCkKICAgIHsKICAgICAgICBtaW5kZXggPSBrZXlkZXg7CiAgICAgICAgZm9yIChpbmRleCA9IChrZXlkZXggKyAxKTsgaW5kZXggPCAoQSArIE4pOyArK2luZGV4KQogICAgICAgIHsKICAgICAgICAgICAgaWYgKCppbmRleCA8ICptaW5kZXgpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIG1pbmRleCA9IGluZGV4OwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGlmIChrZXlkZXggIT0gbWluZGV4KQogICAgICAgIHsKICAgICAgICAgICAgc3dhcChrZXlkZXgsIG1pbmRleCwgc2l6ZW9mKCpBKSk7CiAgICAgICAgfQogICAgfQp9Cgp2b2lkIG1lcmdlKGludCogbGVmdCwgaW50IG5fbGVmdCwgaW50KiByaWdodCwgaW50IG5fcmlnaHQsIGludCogb3V0KQp7CiAgICBpbnQgaSwgaiwgazsKICAgIGZvciAoaSA9IGogPSBrID0gMDsgaSA8IG5fbGVmdCAmJiBqIDwgbl9yaWdodDsgKytrKQogICAgewogICAgICAgIGlmIChsZWZ0W2ldIDwgcmlnaHRbal0pCiAgICAgICAgewogICAgICAgICAgICBvdXRba10gPSBsZWZ0W2ldOwogICAgICAgICAgICArK2k7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIG91dFtrXSA9IHJpZ2h0W2pdOwogICAgICAgICAgICArK2o7CiAgICAgICAgfQogICAgfQogICAgd2hpbGUgKGkgPCBuX2xlZnQpCiAgICB7CiAgICAgICAgb3V0W2tdID0gbGVmdFtpXTsKICAgICAgICArK2k7CiAgICAgICAgKytrOwogICAgfQogICAgd2hpbGUgKGogPCBuX3JpZ2h0KQogICAgewogICAgICAgIG91dFtrXSA9IHJpZ2h0W2pdOwogICAgICAgICsrajsKICAgICAgICArK2s7CiAgICB9Cn0KCnZvaWQgcmVjdXJzZShpbnQqIEEsIGludCogdGVtcCwgaW50IE4pCnsKICAgIGludCBtaWQ7CiAgICBtaWQgPSBOIC8gMjsKICAgIGlmIChOIDw9IDEpCiAgICB7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgcmVjdXJzZSh0ZW1wLCBBLCBtaWQpOwogICAgcmVjdXJzZSh0ZW1wICsgbWlkLCBBICsgbWlkLCBOIC0gbWlkKTsKICAgIG1lcmdlKHRlbXAsIG1pZCwgdGVtcCArIG1pZCwgTiAtIG1pZCwgQSk7Cn0KCnZvaWQgbWVyZ2Vfc29ydChpbnQqIEEsIGludCBOKQp7CiAgICBpbnQqIHRlbXA7CiAgICB0ZW1wID0gbWFsbG9jKHNpemVvZigqQSkgKiBOKTsKICAgIGlmICh0ZW1wKQogICAgewogICAgICAgIG1lbWNweSh0ZW1wLCBBLCBzaXplb2YoKkEpICogTik7CiAgICAgICAgcmVjdXJzZShBLCB0ZW1wLCBOKTsKICAgICAgICBmcmVlKHRlbXApOwogICAgfQp9CgovKnR5cGVkZWYgdm9pZCgqc29ydGluZ19hbGdvcml0aG0pKGludCosIHNpemVfdCk7CnZvaWQgdGVzdF9zb3J0aW5nX2FsZ29yaXRobShpbnQqIEEsIGNvbnN0IHNpemVfdCBOLCBzb3J0aW5nX2FsZ29yaXRobSBzb3J0LCBjb25zdCBjaGFyKiBzb3J0X25hbWUpCnsKICAgIHByaW50ZigiQmVmb3JlICVzOiAiLCBzb3J0X25hbWUpOwogICAgcHJpbnRfYXJyYXkoQSwgTik7CiAgICBzb3J0KEEsIE4pOwogICAgcHJpbnRmKCJBZnRlciAlczogIiwgc29ydF9uYW1lKTsKICAgIHByaW50X2FycmF5KEEsIE4pOwp9Ki8KCiNkZWZpbmUgdGVzdF9zb3J0aW5nX2FsZ29yaXRobShBLCBOLCBzb3J0LCBzb3J0X25hbWUpIFwKeyBcCiAgICBwcmludGYoIkJlZm9yZSAlczogIiwgc29ydF9uYW1lKTsgXAogICAgcHJpbnRfYXJyYXkoQSwgTik7IFwKICAgIHNvcnQoQSwgTik7IFwKICAgIHByaW50ZigiQWZ0ZXIgJXM6ICIsIHNvcnRfbmFtZSk7IFwKICAgIHByaW50X2FycmF5KEEsIE4pOyBcCn0KI2RlZmluZSB0ZXN0X3NvcnQoQSwgTiwgbmFtZSkgdGVzdF9zb3J0aW5nX2FsZ29yaXRobShBLCBOLCBuYW1lLCBTVFJJTkdJWkUobmFtZSkpCgppbnQqIHJhbmdlKHNpemVfdCBOKQp7CiAgICBpbnQqIHJlc3VsdDsKICAgIGlmICgocmVzdWx0ID0gbWFsbG9jKHNpemVvZigqcmVzdWx0KSAqIE4pKSkKICAgIHsKICAgICAgICBpbnQqIGksIG51bTsKICAgICAgICBudW0gPSAwOwogICAgICAgIGZvciAoaSA9IHJlc3VsdDsgaSA8IChyZXN1bHQgKyBOKTsgKytpKQogICAgICAgIHsKICAgICAgICAgICAgKmkgPSBudW07CiAgICAgICAgICAgICsrbnVtOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiByZXN1bHQ7Cn0KCmlubGluZSB2b2lkIHJldmVyc2Uodm9pZCogc2VxdWVuY2UsIGNvbnN0IHNpemVfdCBtZW1iZXJjb3VudCwgY29uc3Qgc2l6ZV90IG1lbWJlcnNpemUpCnsKICAgIHZvaWQgKmxlZnQsICpyaWdodDsKICAgIHJpZ2h0ID0gc2VxdWVuY2UgKyAoKG1lbWJlcmNvdW50IC0gMSkgKiBtZW1iZXJzaXplKTsKICAgIGxlZnQgPSBzZXF1ZW5jZTsKICAgIHdoaWxlIChsZWZ0IDwgcmlnaHQpCiAgICB7CiAgICAgICAgc3dhcChsZWZ0LCByaWdodCwgbWVtYmVyc2l6ZSk7CiAgICAgICAgbGVmdCArPSBtZW1iZXJzaXplOwogICAgICAgIHJpZ2h0IC09IG1lbWJlcnNpemU7CiAgICB9Cn0KCnZvaWQgdGVzdF9yZXZlcnNlKHZvaWQpCnsKICAgIGludCogQSA9IHJhbmdlKDEwKTsKICAgIHJldmVyc2UoQSwgMTAsIHNpemVvZigqQSkpOwogICAgcHJpbnRfYXJyYXkoQSwgMTApOwogICAgZnJlZShBKTsKfQoKY2hhciogZ2V0c3RyaW5nKHZvaWQpCnsKICAgIGNoYXIqIHN0cmJ1ZmZlciA9IE5VTEw7CiAgICBzaXplX3Qgc3RyYnVmZmVyY2FwYWNpdHkgPSAwOwogICAgc2l6ZV90IHN0cmJ1ZmZlcmNoYXJjb3VudCA9IDA7CiAgICBpbnQgY2hhcmFjdGVyOwogICAgd2hpbGUgKChjaGFyYWN0ZXIgPSBmZ2V0YyhzdGRpbikpICE9ICdcbicgJiYgY2hhcmFjdGVyICE9IEVPRikKICAgIHsKICAgICAgICBpZiAoc3RyYnVmZmVyY2hhcmNvdW50ICsgMSA+IHN0cmJ1ZmZlcmNhcGFjaXR5KQogICAgICAgIHsKICAgICAgICAgICAgaWYgKHN0cmJ1ZmZlcmNhcGFjaXR5ID09IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHN0cmJ1ZmZlcmNhcGFjaXR5ID0gc2l6ZW9mKGNoYXIpICogNDsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGlmIChzdHJidWZmZXJjYXBhY2l0eSA8IChVSU5UX01BWCAvIDIpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBzdHJidWZmZXJjYXBhY2l0eSAqPSAyOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZnJlZShzdHJidWZmZXIpOwogICAgICAgICAgICAgICAgcmV0dXJuIE5VTEw7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgY2hhciogdGVtcGJ1ZmZlciA9IHJlYWxsb2Moc3RyYnVmZmVyLCBzaXplb2YoY2hhcikgKiBzdHJidWZmZXJjYXBhY2l0eSk7CiAgICAgICAgICAgIGlmICh0ZW1wYnVmZmVyID09IE5VTEwpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJldHVybiBOVUxMOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgc3RyYnVmZmVyID0gdGVtcGJ1ZmZlcjsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBzdHJidWZmZXJbc3RyYnVmZmVyY2hhcmNvdW50XSA9IGNoYXJhY3RlcjsKICAgICAgICArK3N0cmJ1ZmZlcmNoYXJjb3VudDsKICAgIH0KICAgIGlmIChzdHJidWZmZXJjaGFyY291bnQgPT0gMCAmJiBjaGFyYWN0ZXIgPT0gRU9GKQogICAgewogICAgICAgIHJldHVybiBOVUxMOwogICAgfQogICAgY2hhciogbWluc3RyYnVmZmVyID0gbWFsbG9jKHNpemVvZihjaGFyKSAqIChzdHJidWZmZXJjaGFyY291bnQgKyAxKSk7CiAgICBzdHJuY3B5KG1pbnN0cmJ1ZmZlciwgc3RyYnVmZmVyLCBzdHJidWZmZXJjaGFyY291bnQpOwogICAgZnJlZShzdHJidWZmZXIpOwogICAgbWluc3RyYnVmZmVyW3N0cmJ1ZmZlcmNoYXJjb3VudF0gPSAnXDAnOwogICAgcmV0dXJuIG1pbnN0cmJ1ZmZlcjsKfQoKaW50IGdldGludGVnZXIodm9pZCkKewogICAgZm9yKDs7KQogICAgewogICAgICAgIGNoYXIqIGludGVnZXJzID0gZ2V0c3RyaW5nKCk7CiAgICAgICAgaWYgKGludGVnZXJzID09IE5VTEwpCiAgICAgICAgewogICAgICAgICAgICByZXR1cm4gSU5UX01BWDsKICAgICAgICB9CiAgICAgICAgaW50IGludGVnZXI7CiAgICAgICAgY2hhciBjaGFyYWN0ZXI7CiAgICAgICAgaWYgKHNzY2FuZihpbnRlZ2VycywgIiAlZCAlYyIsICZpbnRlZ2VyLCAmY2hhcmFjdGVyKSA9PSAxKQogICAgICAgIHsKICAgICAgICAgICAgZnJlZShpbnRlZ2Vycyk7CiAgICAgICAgICAgIHJldHVybiBpbnRlZ2VyOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBmcmVlKGludGVnZXJzKTsKICAgICAgICAgICAgcHJpbnRmKCJSZXRyeTogIik7CiAgICAgICAgfQogICAgfQp9Cgp2b2lkIHNvcnRfdHJpYWwodm9pZCkKewogICAgaW50IExFTiwgY2hvaWNlOwogICAgc3JhbmQodGltZShOVUxMKSk7CiAgICBwcmludGYoIkVudGVyIHRoZSBzaXplIG9mIHRoZSBpbnRlZ2VyIGFycmF5IHlvdSB3YW50OiAiKTsKICAgIExFTiA9IGdldGludGVnZXIoKTsKICAgIGludCogQSA9IHJhbmdlKExFTik7CiAgICBwcmludGYoIlxuMS4gUmFuZG9tIGFycmF5XG4yLiBSZXZlcnNlZCBhcnJheVxuMy4gU29ydGVkIGFycmF5XG4iKTsKICAgIGNob2ljZSA9IGdldGludGVnZXIoKTsKICAgIHN3aXRjaCAoY2hvaWNlKQogICAgewogICAgICAgIGNhc2UgMToKICAgICAgICAgICAgc2h1ZmZsZShBLCBMRU4sIHNpemVvZigqQSkpOwogICAgICAgICAgICBicmVhazsKICAgICAgICBjYXNlIDI6CiAgICAgICAgICAgIHJldmVyc2UoQSwgTEVOLCBzaXplb2YoKkEpKTsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgY2FzZSAzOgogICAgICAgICAgICBicmVhazsKICAgICAgICBkZWZhdWx0OgogICAgICAgICAgICBicmVhazsKICAgIH0KICAgIHByaW50ZigiXG4xLiBJbnNlcnRpb24gc29ydFxuMi4gQnViYmxlIHNvcnQgMVxuMy4gQnViYmxlIHNvcnQgMlxuNC4gU2VsZWN0aW9uIHNvcnRcbiIpOwogICAgY2hvaWNlID0gZ2V0aW50ZWdlcigpOwogICAgc3dpdGNoIChjaG9pY2UpCiAgICB7CiAgICAgICAgY2FzZSAxOgogICAgICAgICAgICB0ZXN0X3NvcnQoQSwgTEVOLCBpbnNlcnRpb25fc29ydCk7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIGNhc2UgMjoKICAgICAgICAgICAgdGVzdF9zb3J0KEEsIExFTiwgbXlfYnViYmxlX3NvcnQpOwogICAgICAgICAgICBicmVhazsKICAgICAgICBjYXNlIDM6CiAgICAgICAgICAgIHRlc3Rfc29ydChBLCBMRU4sIGJ1YmJsZV9zb3J0KTsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgY2FzZSA0OgogICAgICAgICAgICB0ZXN0X3NvcnQoQSwgTEVOLCBzZWxlY3Rpb25fc29ydCk7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIGRlZmF1bHQ6CiAgICAgICAgICAgIGJyZWFrOwogICAgfQogICAgZnJlZShBKTsKfQoKbGluayBpbnNlcnRfbm9kZShsaW5rIEEsIGxpbmsgbmV3bm9kZSkKewogICAgbmV3bm9kZS0+bmV4dCA9IEEtPm5leHQ7CiAgICBBLT5uZXh0ID0gbmV3bm9kZTsKICAgIHJldHVybiBuZXdub2RlOwp9CgppbnQgZGVsZXRlX25vZGUobGluayBBLCBsaW5rIHVud2FudGVkX25vZGUpCnsKICAgIGludCBkYXRhOwogICAgQS0+bmV4dCA9IHVud2FudGVkX25vZGUtPm5leHQ7CiAgICBkYXRhID0gdW53YW50ZWRfbm9kZS0+ZGF0YTsKICAgIGZyZWUodW53YW50ZWRfbm9kZSk7CiAgICByZXR1cm4gZGF0YTsKfQoKaW50IHBvcF9ub2RlKGxpbmsgbGlzdCkKewogICAgaW50IGRhdGE7CiAgICB3aGlsZSAobGlzdC0+bmV4dCkKICAgIHsKICAgICAgICBsaXN0ID0gbGlzdC0+bmV4dDsKICAgIH0KICAgIGRhdGEgPSBsaXN0LT5kYXRhOwogICAgZnJlZShsaXN0KTsKICAgIHJldHVybiBkYXRhOwp9CgpsaW5rIGFwcGVuZF9ub2RlKGxpbmsgbGlzdCwgbGluayBuZXdub2RlKQp7CiAgICB3aGlsZSAobGlzdC0+bmV4dCkKICAgIHsKICAgICAgICBsaXN0ID0gbGlzdC0+bmV4dDsKICAgIH0KICAgIGluc2VydF9ub2RlKGxpc3QsIG5ld25vZGUpOwogICAgcmV0dXJuIG5ld25vZGU7Cn0KCnZvaWQgcHJpbnRfbm9kZShsaW5rIG5vZGUpCnsKICAgIHByaW50ZigiJXAgWyVkXSAtPiAlcFxuIiwgbm9kZSwgbm9kZS0+ZGF0YSwgbm9kZS0+bmV4dCk7Cn0KCnZvaWQgdHJhdmVyc2VfbGlzdChsaW5rIG5vZGUpCnsKICAgIGZvciAoOyBub2RlLT5uZXh0OyBub2RlID0gbm9kZS0+bmV4dCkKICAgIHsKICAgICAgICBwcmludF9ub2RlKG5vZGUpOwogICAgfQogICAgcHJpbnRfbm9kZShub2RlKTsKfQoKbGluayByZXZlcnNlX2xpc3QobGluayBoZWFkKQp7CiAgICBsaW5rIG5ld19oZWFkLCBuZXh0OwogICAgbmV3X2hlYWQgPSBOVUxMOwogICAgd2hpbGUgKGhlYWQpCiAgICB7CiAgICAgICAgbmV4dCA9IGhlYWQtPm5leHQ7CiAgICAgICAgaGVhZC0+bmV4dCA9IG5ld19oZWFkOwogICAgICAgIG5ld19oZWFkID0gaGVhZDsKICAgICAgICBoZWFkID0gbmV4dDsKICAgIH0KICAgIHJldHVybiBuZXdfaGVhZDsKfQoKbGluayBjcmVhdGVfZW1wdHlfbm9kZSh2b2lkKQp7CiAgICByZXR1cm4gbWFsbG9jKHNpemVvZihOT0RFKSk7Cn0KCmxpbmsgYXBwZW5kX25ld19ub2RlKGxpbmsgdGFpbCwgaW50IGRhdGEpCnsKICAgIGxpbmsgbmV3bm9kZTsKICAgIG5ld25vZGUgPSBjcmVhdGVfZW1wdHlfbm9kZSgpOwogICAgbmV3bm9kZS0+ZGF0YSA9IGRhdGE7CiAgICBhcHBlbmRfbm9kZSh0YWlsLCBuZXdub2RlKTsKICAgIHJldHVybiB0YWlsLT5uZXh0Owp9CgpsaW5rIGNyZWF0ZV9saXN0X2Zyb21fYXJyYXkoY29uc3QgaW50KiBBLCBjb25zdCBzaXplX3QgTikKewogICAgbGluayBoZWFkLCB0YWlsOwogICAgc2l6ZV90IGVuZDsKICAgIGhlYWQgPSBjcmVhdGVfZW1wdHlfbm9kZSgpOwogICAgaWYgKGhlYWQpCiAgICB7CiAgICAgICAgaGVhZC0+ZGF0YSA9ICpBOwogICAgICAgICsrQTsKICAgICAgICB0YWlsID0gaGVhZDsKICAgICAgICB0YWlsLT5uZXh0ID0gTlVMTDsKICAgICAgICBmb3IgKGVuZCA9IChzaXplX3QpIChBICsgTiAtIDEpOyAoc2l6ZV90KSBBIDwgZW5kOyArK0EpCiAgICAgICAgewogICAgICAgICAgICB0YWlsID0gYXBwZW5kX25ld19ub2RlKHRhaWwsICpBKTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gaGVhZDsKfQoKc2l6ZV90IGxpc3RfbGVuZ3RoKE5PREUgY29uc3QgKmxpc3QpCnsKICAgIHNpemVfdCBsZW5ndGg7CiAgICBsZW5ndGggPSAwOwogICAgd2hpbGUgKGxpc3QpCiAgICB7CiAgICAgICAgbGlzdCA9IGxpc3QtPm5leHQ7CiAgICAgICAgKytsZW5ndGg7CiAgICB9CiAgICByZXR1cm4gbGVuZ3RoOwp9Cgp2b2lkIGRlbGV0ZV9saXN0KGxpbmsgaGVhZCkKewogICAgd2hpbGUgKGhlYWQtPm5leHQpCiAgICB7CiAgICAgICAgZGVsZXRlX25vZGUoaGVhZCwgaGVhZC0+bmV4dCk7CiAgICB9CiAgICBmcmVlKGhlYWQpOwp9CgppbmxpbmUgdm9pZCBzd2FwX25vZGUobGluayBBLCBsaW5rIEIpCnsKICAgIHN3YXAoQSwgQiwgc2l6ZW9mKGxpbmspKTsKfQoKbGluayBnZXRub2RlKGNvbnN0IGxpbmsgaGVhZCwgc2l6ZV90IE4pCnsKICAgIGxpbmsgbm9kZTsKICAgIG5vZGUgPSBoZWFkOwogICAgc2l6ZV90IGluZGV4OwogICAgaW5kZXggPSAwOwogICAgd2hpbGUgKGluZGV4IDwgTikKICAgIHsKICAgICAgICBub2RlID0gbm9kZS0+bmV4dDsKICAgICAgICArK2luZGV4OwogICAgfQogICAgcmV0dXJuIG5vZGU7Cn0KCnZvaWQqIGxpc3RfdG9fYXJyYXkoTk9ERSBjb25zdCAqbGlzdCwgY29uc3Qgc2l6ZV90IGxpc3RfbGVuZ3RoLCBjb25zdCBzaXplX3QgZGF0YV9zaXplKQp7CiAgICB2b2lkKiBhcnJheTsKICAgIGFycmF5ID0gbWFsbG9jKGRhdGFfc2l6ZSAqIGxpc3RfbGVuZ3RoKTsKICAgIGlmIChhcnJheSkKICAgIHsKICAgICAgICB2b2lkKiBibG9jazsKICAgICAgICBzaXplX3QgaW5kZXg7CiAgICAgICAgaW5kZXggPSAwOwogICAgICAgIGJsb2NrID0gYXJyYXk7CiAgICAgICAgd2hpbGUgKGluZGV4IDwgbGlzdF9sZW5ndGgpCiAgICAgICAgewogICAgICAgICAgICBtZW1jcHkoYmxvY2ssICYobGlzdC0+ZGF0YSksIGRhdGFfc2l6ZSk7CiAgICAgICAgICAgIGJsb2NrICs9IGRhdGFfc2l6ZTsKICAgICAgICAgICAgbGlzdCA9IGxpc3QtPm5leHQ7CiAgICAgICAgICAgICsraW5kZXg7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIGFycmF5Owp9CgpsaW5rKiBjcmVhdGVfbGlua19hcnJheShsaW5rIGhlYWQsIHNpemVfdCBsZW5ndGgpCnsKICAgIGxpbmsgKmFycmF5LCAqcHRyOwogICAgYXJyYXkgPSBtYWxsb2Moc2l6ZW9mKCphcnJheSkgKiBsZW5ndGgpOwogICAgcHRyID0gYXJyYXk7CiAgICB3aGlsZSAoaGVhZC0+bmV4dCkKICAgIHsKICAgICAgICAqcHRyID0gaGVhZDsKICAgICAgICArK3B0cjsKICAgICAgICBoZWFkID0gaGVhZC0+bmV4dDsKICAgIH0KICAgIHJldHVybiBhcnJheTsKfQoKLyp2b2lkIGlzb3J0KHZvaWQqIGJhc2UsIHNpemVfdCBudW0sIHNpemVfdCBzaXplLCBpbnQgKCpjb21wYXJhdG9yKSAoY29uc3Qgdm9pZCosIGNvbnN0IHZvaWQqKSkKewogICAgdm9pZCAqbGVmdCwgKnJpZ2h0LCAqa2V5OwogICAgaWYgKChrZXkgPSBtYWxsb2Moc2l6ZSkpKQogICAgewogICAgICAgIGZvciAocmlnaHQgPSAoYmFzZSArIHNpemUpOyAoKHNpemVfdCkgcmlnaHQgLSAoc2l6ZV90KSBiYXNlKS9zaXplIDwgbnVtOyByaWdodCArPSBzaXplKQogICAgICAgIHsKICAgICAgICAgICAgbWVtY3B5KGtleSwgcmlnaHQsIHNpemUpOwogICAgICAgICAgICBmb3IgKGxlZnQgPSByaWdodDsgKHNpemVfdCkgbGVmdCA+IChzaXplX3QpIGJhc2UgJiYgY29tcGFyYXRvcigobGVmdCAtIHNpemUpLCBrZXkpID4gMDsgbGVmdCAtPSBzaXplKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBtZW1jcHkobGVmdCwgbGVmdCAtIHNpemUsIHNpemUpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIG1lbWNweShsZWZ0LCBrZXksIHNpemUpOwogICAgICAgIH0KICAgICAgICBmcmVlKGtleSk7CiAgICB9Cn0qLwoKaW5saW5lIGludCBjbXBfaW50X2FzYyhjb25zdCB2b2lkKiBBLCBjb25zdCB2b2lkKiBCKQp7CiAgICBpbnQgSSA9ICooKGludCopIEEpOwogICAgaW50IEogPSAqKChpbnQqKSBCKTsKICAgIHJldHVybiBJIDwgSiA/IC0xIDogSSA+IEo7Cn0KCmlubGluZSBpbnQgY21wX2ludF9kZXNjKGNvbnN0IHZvaWQqIEEsIGNvbnN0IHZvaWQqIEIpCnsKICAgIGludCBJID0gKigoaW50KikgQSk7CiAgICBpbnQgSiA9ICooKGludCopIEIpOwogICAgcmV0dXJuIEkgPiBKID8gLTEgOiBJIDwgSjsKfQoKaW50IG1haW4odm9pZCkKewogICAgaW50IEFbXSA9IHs5LDgsNyw2LDUsNCwzLDIsMSwwfTsKICAgIHByaW50X2FycmF5KEEsIDEwKTsKICAgIGluc2VydGlvbl9zb3J0KEEsIDEwKTsKICAgIHByaW50X2FycmF5KEEsIDEwKTsKICAgIHJldHVybiAwOwp9