#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef enum { STR, ADD, MUL, MUA, LOP, PNZ, PUT, GET, RTN } op_t;
typedef struct { int size; void *obj; } seq_t;
typedef struct _op {
void *code;
int16_t offset;
int16_t val;
int16_t opt;
seq_t loop;
} Op;
typedef struct _vm {
char* ptr;
char data[31000];
seq_t ops;
} Vm;
#define op_at(x,y) ((Op*)((x)->obj))[y]
static void op_push_back( seq_t *ops, const Op *item )
{
ops->size += 1;
if (ops->obj == NULL) {
ops
->obj
= malloc (sizeof(Op
)); } else {
ops
->obj
= realloc (ops
->obj
, sizeof(Op
)*ops
->size
); }
op_at(ops,ops->size - 1) = *item;
}
static void op_delete( seq_t *ops )
{
if(ops->obj != NULL) {
for(int i=0;i<ops->size;i++)
op_delete(&op_at(ops,i).loop);
ops->obj = NULL;
}
}
static void** eval(Vm *self, seq_t *ops)
{
static const void* const jump[] = { &&PROC_STR, &&PROC_ADD, &&PROC_MUL, &&PROC_MUA,
&&PROC_LOP, &&PROC_PNZ, &&PROC_PUT, &&PROC_GET,
&&PROC_RTN};
if(self == NULL) return (void**)jump;
char *pos = self->ptr;
Op *op=&op_at(ops,0);
goto *op->code;
#define NEXT_PROC goto *(++op)->code;
PROC_STR:
pos[op->offset] = op->val;
NEXT_PROC;
PROC_ADD:
pos[op->offset] += op->val;
NEXT_PROC;
PROC_MUL:
if (op->val == 1) pos[op->offset] = pos[op->opt];
else if (op->val == -1) pos[op->offset] = -pos[op->opt];
else pos[op->offset] = op->val * pos[op->opt];
NEXT_PROC;
PROC_MUA:
if (op->val == 1) pos[op->offset] += pos[op->opt];
else if (op->val == -1) pos[op->offset] -= pos[op->opt];
else pos[op->offset] += op->val * pos[op->opt];
NEXT_PROC;
PROC_LOP:
self->ptr = pos + op->opt;
while(*self->ptr) {
eval(self, &op->loop);
self->ptr += op->offset;
}
pos = self->ptr;
NEXT_PROC;
PROC_PNZ:
pos += op->opt;
while(*pos) pos += op->offset;
NEXT_PROC;
PROC_PUT:
printf("%c", pos
[op
->offset
]); /*fflush(stdout);*/
NEXT_PROC;
PROC_GET:
pos
[op
->offset
] = getc(stdin
); NEXT_PROC;
PROC_RTN:
self->ptr = pos;
return (void**)jump;
}
static void append_str (seq_t *ops, int16_t dst, int16_t val, void **table) {
bool done = false;
for (int i = ops->size; --i >= 0;) {
Op *it = &op_at(ops,i);
if (it->offset == dst && (it->code == table[STR] || it->code == table[ADD]
|| it->code == table[MUL] || it->code == table[MUA])) {
it->code = table[STR];
it->val = val;
it->opt = 0;
done = true;
break;
} else if (it->code == table[LOP] || it->code == table[PNZ]) {
if (dst == 0 && val == 0)
done = true;
break;
} else if (it->offset == dst || (it->opt == dst
&& (it->code == table[MUL] || it->code == table[MUA]))) {
break;
}
}
if (!done) {
Op op = { table[STR], dst, val, 0, { 0, NULL } };
op_push_back ( ops, &op );
}
}
static void append_add (seq_t *ops, int16_t dst, int16_t val, void **table) {
bool done = false;
for (int i = ops->size; --i >= 0;) {
Op *it = &op_at(ops,i);
if (it->code == table[LOP] || it->code == table[PNZ]) {
if (dst == 0) {
Op op = {table[STR], dst, val, 0, { 0, NULL } };
op_push_back ( ops, &op );
done = true;
}
break;
} else if (it->offset == dst) {
if (it->code == table[STR] || it->code == table[ADD]) {
it->val += val;
done = true;
}
break;
} else if (it->opt == dst &&
(it->code == table[MUL] || it->code == table[MUA])) {
break;
}
}
if (!done) {
Op op = { table[ADD], dst, val, 0, { 0, NULL } };
op_push_back ( ops, &op );
}
}
static void append_mua (seq_t *ops, int16_t dst, int16_t val, int16_t src, void **table) {
bool done = false;
for (int i = ops->size; --i >= 0;) {
Op *it = &op_at(ops,i);
if (it->code == table[LOP] || it->code == table[PNZ]) {
if (dst == 0) {
Op op = { table[MUL], dst, val, src, { 0, NULL } };
op_push_back ( ops, &op );
done = true;
}
break;
} else if (it->offset == dst && it->opt == src
&& (it->code == table[MUL] || it->code == table[MUA])) {
it->val += val;
done = true;
break;
} else if (it->code == table[STR] && it->offset == dst && it->val == 0) {
it->code = table[MUL];
it->val = val;
it->opt = src;
done = true;
break;
} else if (it->offset == dst || it->offset == src) {
break;
}
}
if (!done) {
Op op = { table[MUA], dst, val, src, { 0, NULL } };
op_push_back ( ops, &op );
}
}
static void append (seq_t *ops, op_t opc, int16_t dst, int16_t val,
int16_t src, seq_t *loop, void **table) {
Op op = { table[opc], dst, val, src, { loop?loop->size:0, loop?loop->obj:NULL } };
op_push_back ( ops, &op );
}
static seq_t parse( const char *text, const size_t len, int *it )
{
void** tbl = eval( NULL, NULL );
seq_t ops = { 0, NULL };
int pos = 0;
while ((size_t)*it < len) {
switch (text[(*it)++]) {
case '+': append_add( &ops, pos, 1, tbl); break;
case '-': append_add( &ops, pos, -1, tbl); break;
case '>': pos++; break;
case '<': pos--; break;
case '.': append( &ops, PUT, pos, 0, 0, NULL, tbl); break;
case ',': append( &ops, GET, pos, 0, 0, NULL, tbl); break;
case '[': {
int iter = *it;
char ch = text[iter++];
while (ch=='+' || ch=='-' ||
(ch!='>' && ch!='<' && ch!='.' && ch!='.' && ch!='[' && ch!=']'))
ch = text[iter++];
if (ch==']') {
append_str( &ops, pos, 0, tbl);
*it = iter;
break;
}
int ost = 0;
iter = *it;
ch = text[iter++];
while (ch=='>' || ch=='<' ||
(ch!='+' && ch!='-' && ch!='.' && ch!='.' && ch!='[' && ch!=']')) {
if (ch=='>') ost+=1; else if (ch=='<') ost-=1;
ch = text[iter++];
}
if (ch == ']') {
append( &ops, PNZ, ost, 0, pos, NULL, tbl);
*it = iter;
pos = 0;
break;
}
seq_t loop = parse(text,len,it);
op_t opc = MUA;
for (int i=0; i<loop.size; i++) {
Op *op = &op_at(&loop,i);
if (op->code == tbl[MUL] || op->code == tbl[MUA]) {
int j = loop.size;
while (--j >= 0) {
if (op_at(&loop,j).offset == op->opt)
break;
}
if (j >= 0) {
opc = LOP;
break;
}
} else if (op->code == tbl[STR]) {
if (op->offset == 0 && op->val == 0) {
opc = LOP;
break;
}
} else if (op->code == tbl[RTN]) {
if (op->offset != 0) {
opc = LOP;
break;
}
} else if (op->code != tbl[ADD]) {
opc = LOP;
break;
}
}
if (opc == MUA) {
int shrink = 0;
for (int i=0; i<loop.size; i++) {
Op *op = &op_at(&loop,i);
if (shrink != 0)
op_at(&loop,i-shrink) = *op;
if (op->code == tbl[ADD]) {
if (op->offset != 0 || op->val != -1)
append_mua (&ops, op->offset+pos, op->val, pos, tbl);
shrink++;
}
}
if (shrink != 0) loop.size -= shrink;
if (loop.size > 1) {
op_at(&loop,loop.size).code = tbl[RTN];
op_at(&loop,loop.size).offset = op_at(&loop,loop.size-1).offset;
op_at(&loop,loop.size-1).code = tbl[STR];
op_at(&loop,loop.size-1).offset = 0;
op_at(&loop,loop.size-1).val = 0;
loop.size += 1;
opc = LOP;
} else
append_str(&ops, pos, 0, tbl);
}
if (opc == LOP) {
ost = 0;
if (op_at(&loop,loop.size-1).code == tbl[RTN]) {
ost = op_at(&loop,loop.size-1).offset;
}
append(&ops, opc, ost, 0, pos, &loop, tbl );
pos = 0;
}
}
break;
case ']':
append( &ops, RTN, pos, 0, 0, NULL, tbl);
return ops;
}
}
append( &ops, RTN, 0, 0, 0, NULL, tbl);
return ops;
}
static void vminit(Vm *self, char *text, const size_t len)
{
int it = 0;
self->ops = parse(text, len, &it);
}
static void run(Vm *self)
{
memset( self
->data
, 0, sizeof(self
->data
)); self->ptr = self->data + 1000;
eval(self, &self->ops);
}
static char* read_file (const char* filename, size_t *length){
FILE
*stream
= fopen(filename
, "r"); fseek(stream
, 0, SEEK_END
); char* text
= (char*) malloc(*length
); if (fread(text
, *length
, 1, stream
) == 0) puts("read error"); return text;
}
int main(int argc, char** argv){
size_t length;
char *text;
if(argc<=1) {
text
= (char*) malloc (1000000); length
= fread (text
, 1, 1000000, stdin
); } else {
text = read_file(argv[1], &length);
}
Vm vm;
vminit(&vm, text, length);
run(&vm);
op_delete(&vm.ops);
return 0;
}
I2luY2x1ZGUgPHN0ZGJvb2wuaD4KI2luY2x1ZGUgPHN0ZGludC5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8c3RyaW5nLmg+CgoKdHlwZWRlZiBlbnVtIHsgU1RSLCBBREQsIE1VTCwgTVVBLCBMT1AsIFBOWiwgUFVULCBHRVQsIFJUTiB9IG9wX3Q7Cgp0eXBlZGVmIHN0cnVjdCB7IGludCBzaXplOyB2b2lkICpvYmo7IH0gc2VxX3Q7Cgp0eXBlZGVmIHN0cnVjdCBfb3AgewogICAgdm9pZCAqY29kZTsKICAgIGludDE2X3Qgb2Zmc2V0OwogICAgaW50MTZfdCB2YWw7CiAgICBpbnQxNl90IG9wdDsKICAgIHNlcV90IGxvb3A7Cn0gT3A7Cgp0eXBlZGVmIHN0cnVjdCBfdm0gewogICAgY2hhciogcHRyOwogICAgY2hhciBkYXRhWzMxMDAwXTsKICAgIHNlcV90IG9wczsKfSBWbTsKCiNkZWZpbmUgb3BfYXQoeCx5KSAoKE9wKikoKHgpLT5vYmopKVt5XQoKc3RhdGljIHZvaWQgb3BfcHVzaF9iYWNrKCBzZXFfdCAqb3BzLCBjb25zdCBPcCAqaXRlbSApCnsKICAgIG9wcy0+c2l6ZSArPSAxOwogICAgaWYgKG9wcy0+b2JqID09IE5VTEwpIHsKICAgICAgICBvcHMtPm9iaiA9IG1hbGxvYyAoc2l6ZW9mKE9wKSk7CiAgICB9IGVsc2UgewogICAgICAgIG9wcy0+b2JqID0gcmVhbGxvYyAob3BzLT5vYmosIHNpemVvZihPcCkqb3BzLT5zaXplKTsKICAgIH0KICAgIG9wX2F0KG9wcyxvcHMtPnNpemUgLSAxKSA9ICppdGVtOwp9CgpzdGF0aWMgdm9pZCBvcF9kZWxldGUoIHNlcV90ICpvcHMgKQp7CiAgICBpZihvcHMtPm9iaiAhPSBOVUxMKSB7CiAgICAgICAgZm9yKGludCBpPTA7aTxvcHMtPnNpemU7aSsrKQogICAgICAgICAgICBvcF9kZWxldGUoJm9wX2F0KG9wcyxpKS5sb29wKTsKICAgICAgICBmcmVlKG9wcy0+b2JqKTsKICAgICAgICBvcHMtPm9iaiA9IE5VTEw7CiAgICB9Cn0KCnN0YXRpYyB2b2lkKiogZXZhbChWbSAqc2VsZiwgc2VxX3QgKm9wcykKewogICAgc3RhdGljIGNvbnN0IHZvaWQqIGNvbnN0IGp1bXBbXSA9IHsgJiZQUk9DX1NUUiwgJiZQUk9DX0FERCwgJiZQUk9DX01VTCwgJiZQUk9DX01VQSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICYmUFJPQ19MT1AsICYmUFJPQ19QTlosICYmUFJPQ19QVVQsICYmUFJPQ19HRVQsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAmJlBST0NfUlROfTsKICAgIGlmKHNlbGYgPT0gTlVMTCkgcmV0dXJuICh2b2lkKiopanVtcDsKCiAgICBjaGFyICpwb3MgPSBzZWxmLT5wdHI7CiAgICBPcCAqb3A9Jm9wX2F0KG9wcywwKTsKCiAgICBnb3RvICpvcC0+Y29kZTsKI2RlZmluZSBORVhUX1BST0MgZ290byAqKCsrb3ApLT5jb2RlOwoKUFJPQ19TVFI6CiAgICBwb3Nbb3AtPm9mZnNldF0gPSBvcC0+dmFsOwogICAgTkVYVF9QUk9DOwoKUFJPQ19BREQ6CiAgICBwb3Nbb3AtPm9mZnNldF0gKz0gb3AtPnZhbDsKICAgIE5FWFRfUFJPQzsKClBST0NfTVVMOgogICAgaWYgKG9wLT52YWwgPT0gMSkgcG9zW29wLT5vZmZzZXRdID0gcG9zW29wLT5vcHRdOwogICAgZWxzZSBpZiAob3AtPnZhbCA9PSAtMSkgcG9zW29wLT5vZmZzZXRdID0gLXBvc1tvcC0+b3B0XTsKICAgIGVsc2UgcG9zW29wLT5vZmZzZXRdID0gb3AtPnZhbCAqIHBvc1tvcC0+b3B0XTsKICAgIE5FWFRfUFJPQzsKClBST0NfTVVBOgogICAgaWYgKG9wLT52YWwgPT0gMSkgcG9zW29wLT5vZmZzZXRdICs9IHBvc1tvcC0+b3B0XTsKICAgIGVsc2UgaWYgKG9wLT52YWwgPT0gLTEpIHBvc1tvcC0+b2Zmc2V0XSAtPSBwb3Nbb3AtPm9wdF07CiAgICBlbHNlIHBvc1tvcC0+b2Zmc2V0XSArPSBvcC0+dmFsICogcG9zW29wLT5vcHRdOwogICAgTkVYVF9QUk9DOwoKUFJPQ19MT1A6CiAgICBzZWxmLT5wdHIgPSBwb3MgKyBvcC0+b3B0OwogICAgd2hpbGUoKnNlbGYtPnB0cikgewogICAgICAgIGV2YWwoc2VsZiwgJm9wLT5sb29wKTsKICAgICAgICBzZWxmLT5wdHIgKz0gb3AtPm9mZnNldDsKICAgIH0KICAgIHBvcyA9IHNlbGYtPnB0cjsKICAgIE5FWFRfUFJPQzsKClBST0NfUE5aOgogICAgcG9zICs9IG9wLT5vcHQ7CiAgICB3aGlsZSgqcG9zKSBwb3MgKz0gb3AtPm9mZnNldDsKICAgIE5FWFRfUFJPQzsKClBST0NfUFVUOgogICAgcHJpbnRmKCIlYyIsIHBvc1tvcC0+b2Zmc2V0XSk7CiAgICAvKmZmbHVzaChzdGRvdXQpOyovCiAgICBORVhUX1BST0M7CgpQUk9DX0dFVDoKICAgIHBvc1tvcC0+b2Zmc2V0XSA9IGdldGMoc3RkaW4pOwogICAgTkVYVF9QUk9DOwoKUFJPQ19SVE46CiAgICBzZWxmLT5wdHIgPSBwb3M7CiAgICByZXR1cm4gKHZvaWQqKilqdW1wOwp9CgpzdGF0aWMgdm9pZCBhcHBlbmRfc3RyIChzZXFfdCAqb3BzLCBpbnQxNl90IGRzdCwgaW50MTZfdCB2YWwsIHZvaWQgKip0YWJsZSkgewogICAgYm9vbCBkb25lID0gZmFsc2U7CiAgICBmb3IgKGludCBpID0gb3BzLT5zaXplOyAtLWkgPj0gMDspIHsKICAgICAgICBPcCAqaXQgPSAmb3BfYXQob3BzLGkpOwogICAgICAgIGlmIChpdC0+b2Zmc2V0ID09IGRzdCAmJiAoaXQtPmNvZGUgPT0gdGFibGVbU1RSXSB8fCBpdC0+Y29kZSA9PSB0YWJsZVtBRERdCiAgICAgICAgICAgICAgICAgICAgfHwgaXQtPmNvZGUgPT0gdGFibGVbTVVMXSB8fCBpdC0+Y29kZSA9PSB0YWJsZVtNVUFdKSkgewogICAgICAgICAgICBpdC0+Y29kZSA9IHRhYmxlW1NUUl07CiAgICAgICAgICAgIGl0LT52YWwgPSB2YWw7CiAgICAgICAgICAgIGl0LT5vcHQgPSAwOwogICAgICAgICAgICBkb25lID0gdHJ1ZTsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfSBlbHNlIGlmIChpdC0+Y29kZSA9PSB0YWJsZVtMT1BdIHx8IGl0LT5jb2RlID09IHRhYmxlW1BOWl0pIHsKICAgICAgICAgICAgaWYgKGRzdCA9PSAwICYmIHZhbCA9PSAwKQogICAgICAgICAgICAgICAgZG9uZSA9IHRydWU7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0gZWxzZSBpZiAoaXQtPm9mZnNldCA9PSBkc3QgfHwgKGl0LT5vcHQgPT0gZHN0CiAgICAgICAgICAgICAgICAmJiAoaXQtPmNvZGUgPT0gdGFibGVbTVVMXSB8fCBpdC0+Y29kZSA9PSB0YWJsZVtNVUFdKSkpIHsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfQogICAgfQogICAgaWYgKCFkb25lKSB7CiAgICAgICAgT3Agb3AgPSB7IHRhYmxlW1NUUl0sIGRzdCwgdmFsLCAwLCB7IDAsIE5VTEwgfSB9OwogICAgICAgIG9wX3B1c2hfYmFjayAoIG9wcywgJm9wICk7CiAgICB9Cn0KCnN0YXRpYyB2b2lkIGFwcGVuZF9hZGQgKHNlcV90ICpvcHMsIGludDE2X3QgZHN0LCBpbnQxNl90IHZhbCwgdm9pZCAqKnRhYmxlKSB7CiAgICBib29sIGRvbmUgPSBmYWxzZTsKICAgIGZvciAoaW50IGkgPSBvcHMtPnNpemU7IC0taSA+PSAwOykgewogICAgICAgIE9wICppdCA9ICZvcF9hdChvcHMsaSk7CiAgICAgICAgaWYgKGl0LT5jb2RlID09IHRhYmxlW0xPUF0gfHwgaXQtPmNvZGUgPT0gdGFibGVbUE5aXSkgewogICAgICAgICAgICBpZiAoZHN0ID09IDApIHsKICAgICAgICAgICAgICAgIE9wIG9wID0ge3RhYmxlW1NUUl0sIGRzdCwgdmFsLCAwLCB7IDAsIE5VTEwgfSB9OwogICAgICAgICAgICAgICAgb3BfcHVzaF9iYWNrICggb3BzLCAmb3AgKTsKICAgICAgICAgICAgICAgIGRvbmUgPSB0cnVlOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0gZWxzZSBpZiAoaXQtPm9mZnNldCA9PSBkc3QpIHsKICAgICAgICAgICAgaWYgKGl0LT5jb2RlID09IHRhYmxlW1NUUl0gfHwgaXQtPmNvZGUgPT0gdGFibGVbQUREXSkgewogICAgICAgICAgICAgICAgaXQtPnZhbCArPSB2YWw7CiAgICAgICAgICAgICAgICBkb25lID0gdHJ1ZTsKICAgICAgICAgICAgfQogICAgICAgICAgICBicmVhazsKICAgICAgICB9IGVsc2UgaWYgKGl0LT5vcHQgPT0gZHN0ICYmCiAgICAgICAgICAgICAgICAoaXQtPmNvZGUgPT0gdGFibGVbTVVMXSB8fCBpdC0+Y29kZSA9PSB0YWJsZVtNVUFdKSkgewogICAgICAgICAgICBicmVhazsKICAgICAgICB9CiAgICB9CiAgICBpZiAoIWRvbmUpIHsKICAgICAgICBPcCBvcCA9IHsgdGFibGVbQUREXSwgZHN0LCB2YWwsIDAsIHsgMCwgTlVMTCB9IH07CiAgICAgICAgb3BfcHVzaF9iYWNrICggb3BzLCAmb3AgKTsKICAgIH0KfQoKc3RhdGljIHZvaWQgYXBwZW5kX211YSAoc2VxX3QgKm9wcywgaW50MTZfdCBkc3QsIGludDE2X3QgdmFsLCBpbnQxNl90IHNyYywgdm9pZCAqKnRhYmxlKSB7CiAgICBib29sIGRvbmUgPSBmYWxzZTsKICAgIGZvciAoaW50IGkgPSBvcHMtPnNpemU7IC0taSA+PSAwOykgewogICAgICAgIE9wICppdCA9ICZvcF9hdChvcHMsaSk7CiAgICAgICAgaWYgKGl0LT5jb2RlID09IHRhYmxlW0xPUF0gfHwgaXQtPmNvZGUgPT0gdGFibGVbUE5aXSkgewogICAgICAgICAgICBpZiAoZHN0ID09IDApIHsKICAgICAgICAgICAgICAgIE9wIG9wID0geyB0YWJsZVtNVUxdLCBkc3QsIHZhbCwgc3JjLCB7IDAsIE5VTEwgfSB9OwogICAgICAgICAgICAgICAgb3BfcHVzaF9iYWNrICggb3BzLCAmb3AgKTsKICAgICAgICAgICAgICAgIGRvbmUgPSB0cnVlOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0gZWxzZSBpZiAoaXQtPm9mZnNldCA9PSBkc3QgJiYgaXQtPm9wdCA9PSBzcmMKICAgICAgICAgICAgICAgICYmIChpdC0+Y29kZSA9PSB0YWJsZVtNVUxdIHx8IGl0LT5jb2RlID09IHRhYmxlW01VQV0pKSB7CiAgICAgICAgICAgIGl0LT52YWwgKz0gdmFsOwogICAgICAgICAgICBkb25lID0gdHJ1ZTsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfSBlbHNlIGlmIChpdC0+Y29kZSA9PSB0YWJsZVtTVFJdICYmIGl0LT5vZmZzZXQgPT0gZHN0ICYmIGl0LT52YWwgPT0gMCkgewogICAgICAgICAgICBpdC0+Y29kZSA9IHRhYmxlW01VTF07CiAgICAgICAgICAgIGl0LT52YWwgPSB2YWw7CiAgICAgICAgICAgIGl0LT5vcHQgPSBzcmM7CiAgICAgICAgICAgIGRvbmUgPSB0cnVlOwogICAgICAgICAgICBicmVhazsKICAgICAgICB9IGVsc2UgaWYgKGl0LT5vZmZzZXQgPT0gZHN0IHx8IGl0LT5vZmZzZXQgPT0gc3JjKSB7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgIH0KICAgIGlmICghZG9uZSkgewogICAgICAgIE9wIG9wID0geyB0YWJsZVtNVUFdLCBkc3QsIHZhbCwgc3JjLCB7IDAsIE5VTEwgfSB9OwogICAgICAgIG9wX3B1c2hfYmFjayAoIG9wcywgJm9wICk7CiAgICB9Cn0KCnN0YXRpYyB2b2lkIGFwcGVuZCAoc2VxX3QgKm9wcywgb3BfdCBvcGMsIGludDE2X3QgZHN0LCBpbnQxNl90IHZhbCwKICAgICAgICBpbnQxNl90IHNyYywgc2VxX3QgKmxvb3AsIHZvaWQgKip0YWJsZSkgewogICAgT3Agb3AgPSB7IHRhYmxlW29wY10sIGRzdCwgdmFsLCBzcmMsIHsgbG9vcD9sb29wLT5zaXplOjAsIGxvb3A/bG9vcC0+b2JqOk5VTEwgfSB9OwogICAgb3BfcHVzaF9iYWNrICggb3BzLCAmb3AgKTsKfQoKc3RhdGljIHNlcV90IHBhcnNlKCBjb25zdCBjaGFyICp0ZXh0LCBjb25zdCBzaXplX3QgbGVuLCBpbnQgKml0ICkKewogICAgdm9pZCoqIHRibCA9IGV2YWwoIE5VTEwsIE5VTEwgKTsKCiAgICBzZXFfdCBvcHMgPSB7IDAsIE5VTEwgfTsKICAgIGludCBwb3MgPSAwOwogICAgd2hpbGUgKChzaXplX3QpKml0IDwgbGVuKSB7CiAgICAgICAgc3dpdGNoICh0ZXh0WygqaXQpKytdKSB7CiAgICAgICAgY2FzZSAnKyc6IGFwcGVuZF9hZGQoICZvcHMsIHBvcywgMSwgdGJsKTsgYnJlYWs7CiAgICAgICAgY2FzZSAnLSc6IGFwcGVuZF9hZGQoICZvcHMsIHBvcywgLTEsIHRibCk7IGJyZWFrOwogICAgICAgIGNhc2UgJz4nOiBwb3MrKzsgYnJlYWs7CiAgICAgICAgY2FzZSAnPCc6IHBvcy0tOyBicmVhazsKICAgICAgICBjYXNlICcuJzogYXBwZW5kKCAmb3BzLCBQVVQsIHBvcywgMCwgMCwgTlVMTCwgdGJsKTsgYnJlYWs7CiAgICAgICAgY2FzZSAnLCc6IGFwcGVuZCggJm9wcywgR0VULCBwb3MsIDAsIDAsIE5VTEwsIHRibCk7IGJyZWFrOwogICAgICAgIGNhc2UgJ1snOiB7CiAgICAgICAgICAgICAgICBpbnQgaXRlciA9ICppdDsKICAgICAgICAgICAgICAgIGNoYXIgY2ggPSB0ZXh0W2l0ZXIrK107CiAgICAgICAgICAgICAgICB3aGlsZSAoY2g9PScrJyB8fCBjaD09Jy0nIHx8CiAgICAgICAgICAgICAgICAgICAgKGNoIT0nPicgJiYgY2ghPSc8JyAmJiBjaCE9Jy4nICYmIGNoIT0nLicgJiYgY2ghPSdbJyAmJiBjaCE9J10nKSkKICAgICAgICAgICAgICAgICAgICBjaCA9IHRleHRbaXRlcisrXTsKICAgICAgICAgICAgICAgIGlmIChjaD09J10nKSB7CiAgICAgICAgICAgICAgICAgICAgYXBwZW5kX3N0ciggJm9wcywgcG9zLCAwLCB0YmwpOwogICAgICAgICAgICAgICAgICAgICppdCA9IGl0ZXI7CiAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgaW50IG9zdCA9IDA7CiAgICAgICAgICAgICAgICBpdGVyID0gKml0OwogICAgICAgICAgICAgICAgY2ggPSB0ZXh0W2l0ZXIrK107CiAgICAgICAgICAgICAgICB3aGlsZSAoY2g9PSc+JyB8fCBjaD09JzwnIHx8CiAgICAgICAgICAgICAgICAgICAgKGNoIT0nKycgJiYgY2ghPSctJyAmJiBjaCE9Jy4nICYmIGNoIT0nLicgJiYgY2ghPSdbJyAmJiBjaCE9J10nKSkgewogICAgICAgICAgICAgICAgICAgIGlmIChjaD09Jz4nKSBvc3QrPTE7IGVsc2UgaWYgKGNoPT0nPCcpIG9zdC09MTsKICAgICAgICAgICAgICAgICAgICBjaCA9IHRleHRbaXRlcisrXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGlmIChjaCA9PSAnXScpIHsKICAgICAgICAgICAgICAgICAgICBhcHBlbmQoICZvcHMsIFBOWiwgb3N0LCAwLCBwb3MsIE5VTEwsIHRibCk7CiAgICAgICAgICAgICAgICAgICAgKml0ID0gaXRlcjsKICAgICAgICAgICAgICAgICAgICBwb3MgPSAwOwogICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIHNlcV90IGxvb3AgPSBwYXJzZSh0ZXh0LGxlbixpdCk7CiAgICAgICAgICAgICAgICBvcF90IG9wYyA9IE1VQTsKCiAgICAgICAgICAgICAgICBmb3IgKGludCBpPTA7IGk8bG9vcC5zaXplOyBpKyspIHsKICAgICAgICAgICAgICAgICAgICBPcCAqb3AgPSAmb3BfYXQoJmxvb3AsaSk7CiAgICAgICAgICAgICAgICAgICAgaWYgKG9wLT5jb2RlID09IHRibFtNVUxdIHx8IG9wLT5jb2RlID09IHRibFtNVUFdKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIGludCBqID0gbG9vcC5zaXplOwogICAgICAgICAgICAgICAgICAgICAgICB3aGlsZSAoLS1qID49IDApIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIChvcF9hdCgmbG9vcCxqKS5vZmZzZXQgPT0gb3AtPm9wdCkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBpZiAoaiA+PSAwKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBvcGMgPSBMT1A7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0gZWxzZSBpZiAob3AtPmNvZGUgPT0gdGJsW1NUUl0pIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKG9wLT5vZmZzZXQgPT0gMCAmJiBvcC0+dmFsID09IDApIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG9wYyA9IExPUDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfSBlbHNlIGlmIChvcC0+Y29kZSA9PSB0YmxbUlROXSkgewogICAgICAgICAgICAgICAgICAgICAgICBpZiAob3AtPm9mZnNldCAhPSAwKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBvcGMgPSBMT1A7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0gZWxzZSBpZiAob3AtPmNvZGUgIT0gdGJsW0FERF0pIHsKICAgICAgICAgICAgICAgICAgICAgICAgb3BjID0gTE9QOwogICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgaWYgKG9wYyA9PSBNVUEpIHsKICAgICAgICAgICAgICAgICAgICBpbnQgc2hyaW5rID0gMDsKICAgICAgICAgICAgICAgICAgICBmb3IgKGludCBpPTA7IGk8bG9vcC5zaXplOyBpKyspIHsKICAgICAgICAgICAgICAgICAgICAgICAgT3AgKm9wID0gJm9wX2F0KCZsb29wLGkpOwogICAgICAgICAgICAgICAgICAgICAgICBpZiAoc2hyaW5rICE9IDApCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBvcF9hdCgmbG9vcCxpLXNocmluaykgPSAqb3A7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmIChvcC0+Y29kZSA9PSB0YmxbQUREXSkgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKG9wLT5vZmZzZXQgIT0gMCB8fCBvcC0+dmFsICE9IC0xKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFwcGVuZF9tdWEgKCZvcHMsIG9wLT5vZmZzZXQrcG9zLCBvcC0+dmFsLCBwb3MsIHRibCk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBzaHJpbmsrKzsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICAgICAgaWYgKHNocmluayAhPSAwKSBsb29wLnNpemUgLT0gc2hyaW5rOwogICAgICAgICAgICAgICAgICAgIGlmIChsb29wLnNpemUgPiAxKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIG9wX2F0KCZsb29wLGxvb3Auc2l6ZSkuY29kZSA9IHRibFtSVE5dOwogICAgICAgICAgICAgICAgICAgICAgICBvcF9hdCgmbG9vcCxsb29wLnNpemUpLm9mZnNldCA9IG9wX2F0KCZsb29wLGxvb3Auc2l6ZS0xKS5vZmZzZXQ7CiAgICAgICAgICAgICAgICAgICAgICAgIG9wX2F0KCZsb29wLGxvb3Auc2l6ZS0xKS5jb2RlID0gdGJsW1NUUl07CiAgICAgICAgICAgICAgICAgICAgICAgIG9wX2F0KCZsb29wLGxvb3Auc2l6ZS0xKS5vZmZzZXQgPSAwOwogICAgICAgICAgICAgICAgICAgICAgICBvcF9hdCgmbG9vcCxsb29wLnNpemUtMSkudmFsID0gMDsKICAgICAgICAgICAgICAgICAgICAgICAgbG9vcC5zaXplICs9IDE7CiAgICAgICAgICAgICAgICAgICAgICAgIG9wYyA9IExPUDsKICAgICAgICAgICAgICAgICAgICB9IGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgYXBwZW5kX3N0cigmb3BzLCBwb3MsIDAsIHRibCk7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgaWYgKG9wYyA9PSBMT1ApIHsKICAgICAgICAgICAgICAgICAgICBvc3QgPSAwOwogICAgICAgICAgICAgICAgICAgIGlmIChvcF9hdCgmbG9vcCxsb29wLnNpemUtMSkuY29kZSA9PSB0YmxbUlROXSkgewogICAgICAgICAgICAgICAgICAgICAgICBvc3QgPSBvcF9hdCgmbG9vcCxsb29wLnNpemUtMSkub2Zmc2V0OwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBhcHBlbmQoJm9wcywgb3BjLCBvc3QsIDAsIHBvcywgJmxvb3AsIHRibCApOwogICAgICAgICAgICAgICAgICAgIHBvcyA9IDA7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgY2FzZSAnXSc6CiAgICAgICAgICAgIGFwcGVuZCggJm9wcywgUlROLCBwb3MsIDAsIDAsIE5VTEwsIHRibCk7CiAgICAgICAgICAgIHJldHVybiBvcHM7CiAgICAgICAgfQogICAgfQogICAgYXBwZW5kKCAmb3BzLCBSVE4sIDAsIDAsIDAsIE5VTEwsIHRibCk7CiAgICByZXR1cm4gb3BzOwp9CgpzdGF0aWMgdm9pZCB2bWluaXQoVm0gKnNlbGYsIGNoYXIgKnRleHQsIGNvbnN0IHNpemVfdCBsZW4pCnsKICAgIGludCBpdCA9IDA7CiAgICBzZWxmLT5vcHMgPSBwYXJzZSh0ZXh0LCBsZW4sICZpdCk7Cn0KCnN0YXRpYyB2b2lkIHJ1bihWbSAqc2VsZikKewogICAgbWVtc2V0KCBzZWxmLT5kYXRhLCAwLCBzaXplb2Yoc2VsZi0+ZGF0YSkpOwogICAgc2VsZi0+cHRyID0gc2VsZi0+ZGF0YSArIDEwMDA7CiAgICBldmFsKHNlbGYsICZzZWxmLT5vcHMpOwp9CgpzdGF0aWMgY2hhciogcmVhZF9maWxlIChjb25zdCBjaGFyKiBmaWxlbmFtZSwgc2l6ZV90ICpsZW5ndGgpewogICAgRklMRSAqc3RyZWFtID0gZm9wZW4oZmlsZW5hbWUsICJyIik7CiAgICBmc2VlayhzdHJlYW0sIDAsIFNFRUtfRU5EKTsKICAgICpsZW5ndGggPSBmdGVsbChzdHJlYW0pOwogICAgcmV3aW5kKHN0cmVhbSk7CiAgICBjaGFyKiB0ZXh0ID0gKGNoYXIqKSBtYWxsb2MoKmxlbmd0aCk7CiAgICBpZiAoZnJlYWQodGV4dCwgKmxlbmd0aCwgMSwgc3RyZWFtKSA9PSAwKSBwdXRzKCJyZWFkIGVycm9yIik7CiAgICBmY2xvc2Uoc3RyZWFtKTsKICAgIHJldHVybiB0ZXh0Owp9CgppbnQgbWFpbihpbnQgYXJnYywgY2hhcioqIGFyZ3YpewogICAgc2l6ZV90IGxlbmd0aDsKICAgIGNoYXIgKnRleHQ7CiAgICBpZihhcmdjPD0xKSB7CiAgICAgICAgdGV4dCA9IChjaGFyKikgbWFsbG9jICgxMDAwMDAwKTsKICAgICAgICBsZW5ndGggPSBmcmVhZCAodGV4dCwgMSwgMTAwMDAwMCwgc3RkaW4pOwogICAgfSBlbHNlIHsKICAgICAgICB0ZXh0ID0gcmVhZF9maWxlKGFyZ3ZbMV0sICZsZW5ndGgpOwogICAgfQogICAgVm0gdm07CiAgICB2bWluaXQoJnZtLCB0ZXh0LCBsZW5ndGgpOwogICAgcnVuKCZ2bSk7CiAgICBvcF9kZWxldGUoJnZtLm9wcyk7CiAgICByZXR1cm4gMDsKfQo=