#ifdef _MSC_VER
#pragma comment(linker, "/SUBSYSTEM:CONSOLE /ENTRY:mainCRTStartup")
#endif
#include <limits.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#define SHR_BYTES( VAL, BYTES ) (VAL >> (CHAR_BIT * BYTES))
#if UINT_MAX == UCHAR_MAX
#define INT_SIZE 1
#elif UINT_MAX == USHRT_MAX
#define INT_SIZE 2
#elif SHR_BYTES(UINT_MAX,4) == 0
#define INT_SIZE 4
#else
#define INT_SIZE 8
#endif
#if SHR_BYTES(ULONG_MAX,4) == 0
#define LONG_SIZE 4
#else
#define LONG_SIZE 8
#endif
#define LLONG_SIZE 8
#define SHRT_BIT (2 * CHAR_BIT)
#define INT_BIT (INT_SIZE * CHAR_BIT)
#define LONG_BIT (LONG_SIZE * CHAR_BIT)
#define LLONG_BIT (8 * CHAR_BIT)
#ifndef __nothrow
#if defined( __attribute__ )
#define __nothrow __attribute__((nothrow))
#elif defined( __declspec )
#define __nothrow __declspec(nothrow)
#elif defined(__nothrow__)
#define __nothrow __nothrow
#else
#define __nothrow
#endif
#endif
#ifndef __stdcall
#if defined( __attribute__ )
#define __stdcall __attribute__((stdcall))
#elif defined( __declspec )
#define __stdcall __declspec(stdcall)
#elif defined( __stdcall__ )
#define __stdcall __stdcall__
#else
#define __stdcall
#endif
#endif
typedef unsigned char uchar;
typedef signed char schar;
typedef unsigned short ushort;
typedef unsigned int uint;
typedef unsigned long ulong;
#define LLONG long long int
typedef LLONG llong;
typedef unsigned LLONG ullong;
typedef union PTRU_
{
void *vptr;
uchar *cptr;
uint *iptr;
intptr_t sptr;
uintptr_t uptr;
} PTRU;
typedef struct PTRS_
{
void *SRC;
size_t size;
char endian;
char padding[3];
PTRU beg;
PTRU end;
schar pos1;
schar pos2;
schar neg1;
schar neg2;
} PTRS;
#define LIMITS(UI,SI,UMAX,SMAX,SMIN,ONE)\
static const uchar UI##_bit = sizeof(SI) * CHAR_BIT;\
static const uchar UI##_mov = (sizeof(SI) * CHAR_BIT) - 1;\
static const UI UI##_end = ONE << ((sizeof(SI) * CHAR_BIT) - 1);\
static const UI UI##_max = UMAX;\
static const SI SI##_max = SMAX;\
static const SI SI##_min = SMIN
LIMITS( uchar, schar, UCHAR_MAX, SCHAR_MAX, SCHAR_MIN, 1U );
LIMITS( ushort, short, USHRT_MAX, SHRT_MAX, SHRT_MIN, 1U );
LIMITS( uint, int, UINT_MAX, INT_MAX, INT_MIN, 1U );
LIMITS( ulong, long, ULONG_MAX, LONG_MAX, LONG_MIN, 1UL );
LIMITS( ullong, llong, ULLONG_MAX, LLONG_MAX, LLONG_MIN, 1ULL );
#define UPTR_IS0( M_0, M_LAST, M_I1, M_I2 ) (!M_0 || !M_LAST || M_I1 == 0 || M_I2 == 0)
PTRS
__nothrow __stdcall
endian( void *SRC, size_t srcSize, char srcEndian )
{
PTRS num;
PTRU BEG, END;
num.SRC = SRC;
num.size = srcSize;
num.endian = srcEndian;
BEG.vptr = SRC;
END.uptr = BEG.uptr + ( srcSize - 1 );
switch( num.endian )
{
// 0x78563412
case 'B':
case 'b':
num.pos1 = num.pos2 = -1;
num.end = BEG;
num.beg = END;
return num;
// 0x12345678
case 'L':
case 'l':
num.pos1 = num.pos2 = 1;
num.end = END;
num.beg = BEG;
goto done;
// 0x56781234
case 'R':
case 'r':
num.pos1 = -1;
num.pos2 = 4;
num.end.uptr = ++BEG.uptr;
num.beg.uptr = --END.uptr;
goto done;
}
// 0x34127856
num.endian = 'M';
num.pos1 = 1;
num.pos2 = -4;
num.end.uptr = --END.uptr;
num.beg.uptr = ++BEG.uptr;
done:
num.neg1 = -num.pos1;
num.neg2 = -num.pos2;
return num;
}
uchar
__nothrow __stdcall
eis0( PTRS src, void **S )
{
for( uchar i = 1; src.size--; src.end.uptr += i ? src.neg1 : src.neg2, i ^= 1 )
{
if( *src.end.cptr )
{
if( S ) { *S = src.end.vptr; }
return 0;
}
}
if( S ) { *S = NULL; }
return 1;
}
uchar
__nothrow __stdcall
eiseq( PTRS src, PTRS num, void **S, void **N )
{
for( uchar i = 1; src.size && num.size;
src.end.uptr += i ? src.neg1 : src.neg2,
num.end.uptr += i ? num.neg1 : num.neg2,
--src.size, --num.size, i ^= 1 )
{
if( *src.end.cptr != *num.end.cptr ) { goto stop; }
}
if( !src.size )
{
if( N ) { *N = num.end.vptr; }
if( S ) { *S = src.end.vptr; }
if( !num.size ) { return 1; }
return 0;
}
if( !num.size )
{
stop:
if( N ) { *N = num.end.vptr; }
if( S ) { *S = src.end.vptr; }
return 0;
}
if( N ) { *N = num.end.vptr; }
if( S ) { *S = src.end.vptr; }
return 1;
}
uchar
__nothrow __stdcall
emteq( PTRS src, PTRS num, void **S, void **N )
{
void *s, *n;
if( !S ) { S = &s; }
if( !N ) { N = &n; }
if( eiseq( src, num, S, N ) || **( ( uchar** )S ) > **( ( uchar** )N ) )
{ return 1; }
return 0;
}
uchar
__nothrow __stdcall
emt( PTRS src, PTRS num, void **S, void **N )
{
void *s, *n;
if( !S ) { S = &s; }
if( !N ) { N = &n; }
if( !eiseq( src, num, S, N ) && **( ( uchar** )S ) > **( ( uchar** )N ) )
{ return 1; }
return 0;
}
uchar
__nothrow __stdcall
elteq( PTRS src, PTRS num, void **S, void **N )
{
void *s, *n;
if( !S ) { S = &s; }
if( !N ) { N = &n; }
if( eiseq( src, num, S, N ) || **( ( uchar** )S ) < **( ( uchar** )N ) )
{ return 1; }
return 0;
}
uchar
__nothrow __stdcall
elt( PTRS src, PTRS num, void **S, void **N )
{
void *s, *n;
if( !S ) { S = &s; }
if( !N ) { N = &n; }
if( !eiseq( src, num, S, N ) && **( ( uchar** )S ) < **( ( uchar** )N ) )
{ return 1; }
return 0;
}
PTRS
__nothrow __stdcall
eshr( PTRS src, ullong bits )
{
if( !bits ) { return src; }
PTRS def = src;
PTRS dst = src;
uchar di = 1, ni = 1, rbits = 0, lbits = 0;
while( bits >= uchar_bit && dst.size-- )
{
dst.beg.uptr += di ? dst.pos1 : dst.pos2;
bits -= uchar_bit;
}
if( bits >= uchar_bit )
{
( void )memset( src.
SRC, 0, src.
size ); return def;
}
if( dst.size < src.size )
{
while( dst.size-- )
{
*src.beg.cptr = *dst.beg.cptr;
*dst.beg.cptr = 0;
dst.beg.uptr += di ? dst.pos1 : dst.pos2;
src.beg.uptr += ni ? src.pos1 : src.pos2;
}
}
ullong move = CHAR_BIT - bits;
while( src.size-- )
{
rbits = lbits;
lbits = *src.end.cptr << move;
*src.end.cptr >>= bits;
*src.end.cptr |= rbits;
src.end.uptr += ni ? src.neg1 : src.neg2;
ni ^= 1;
}
return def;
}
PTRS
__nothrow __stdcall
eshl( PTRS src, ullong bits )
{
if( !bits ) { return src; }
PTRS def = src;
PTRS dst = src;
uchar di = 1, si = 1, rbits = 0, lbits = 0;
while( bits >= uchar_bit && dst.size-- )
{
dst.end.uptr += di ? dst.neg1 : dst.neg2;
bits -= uchar_bit;
}
if( bits >= uchar_bit )
{
( void )memset( src.
SRC, 0, src.
size ); return def;
}
if( dst.size < src.size )
{
while( dst.size-- )
{
*src.end.cptr = *dst.end.cptr;
*dst.end.cptr = 0;
dst.end.uptr += di ? dst.neg1 : dst.neg2;
src.end.uptr += si ? src.neg1 : src.neg2;
}
}
si = 1;
ullong move = CHAR_BIT - bits;
while( src.size-- )
{
lbits = rbits;
rbits = *src.beg.cptr >> move;
*src.beg.cptr <<= bits;
*src.beg.cptr |= lbits;
src.beg.uptr += si ? src.pos1 : src.pos2;
si ^= 1;
}
return def;
}
PTRS
__nothrow __stdcall
eshl1( PTRS src )
{
PTRS def = src;
uchar i = 1, rbits = 0, lbits = 0;
for( ; src.size--; i ^= 1 )
{
lbits = rbits;
rbits = *src.beg.cptr >> uchar_mov;
*src.beg.cptr <<= 1;
*src.beg.cptr |= lbits;
src.beg.uptr += i ? src.pos1 : src.pos2;
}
return def;
}
PTRS
__nothrow __stdcall
eshr1( PTRS src )
{
PTRS def = src;
uchar i = 1, rbits = 0, lbits = 0;
for( ; src.size--; i ^= 1 )
{
rbits = lbits;
lbits = *src.beg.cptr << uchar_mov;
*src.beg.cptr >>= 1;
*src.beg.cptr |= rbits;
src.beg.uptr += i ? src.pos1 : src.pos2;
}
return def;
}
PTRS
__nothrow __stdcall
eand( PTRS src, PTRS num )
{
PTRS def = src;
for( uchar i = 1; src.size-- && num.size--; i ^= 1 )
{
*src.beg.cptr &= *num.beg.cptr;
src.beg.uptr += i ? src.pos1 : src.pos2;
num.beg.uptr += i ? num.pos1 : src.pos2;
}
return def;
}
uchar
__nothrow __stdcall
einc( PTRS num )
{
uchar bit, i = 1;
for( ; num.size--; i ^= 1, num.beg.uptr += i ? num.pos1 : num.pos2 )
{
for( bit = 1; bit; bit <<= 1 )
{
if( *num.beg.cptr & bit )
{
*num.beg.cptr ^= bit;
}
else
{
*num.beg.cptr |= bit;
return 1;
}
}
}
return 1;
}
PTRS
__nothrow __stdcall
eadd( PTRS src, PTRS num )
{
PTRS def = src;
uchar carry = 0, bit;
for( uchar i = 1; src.size-- && num.size--; i ^= 1,
src.beg.uptr += i ? src.pos1 : src.pos2,
num.beg.uptr += i ? num.pos1 : num.pos2 )
{
for( bit = 1; bit; bit <<= 1 )
{
if( carry )
{
if( *src.beg.cptr & bit )
{
*src.beg.cptr ^= bit;
}
else
{
*src.beg.cptr |= bit;
carry = 0;
}
}
if( *src.beg.cptr & bit )
{
if( *num.beg.cptr & bit )
{
*src.beg.cptr ^= bit;
carry = 1;
}
}
else if( *num.beg.cptr & bit )
{
*src.beg.cptr |= bit;
}
}
}
return def;
}
PTRS
__nothrow __stdcall
esub( PTRS src, PTRS num )
{
PTRS def = src;
uchar carry = 0, bit = uchar_end, clr = 0, i = 1;
for( size_t srcSize = src.size; !( *src.end.cptr ) && srcSize--; i ^= 1 )
{
src.end.uptr += i ? src.neg1 : src.neg2;
}
while( bit && !( *src.end.cptr & bit ) )
{
clr |= bit;
bit >>= 1;
}
clr = ~clr;
for( i = 1; src.size-- && num.size--;
src.beg.uptr += i ? src.pos1 : src.pos2,
num.beg.uptr += i ? num.pos1 : num.pos2, i ^= 1 )
{
for( bit = 1; bit; bit <<= 1 )
{
if( carry )
{
if( *( src.beg.cptr ) & bit )
{
*( src.beg.cptr ) ^= bit;
carry = 0;
}
else
{
*( src.beg.cptr ) |= bit;
}
}
if( *( src.beg.cptr ) & bit )
{
if( *( num.beg.cptr ) & bit )
{
*( src.beg.cptr ) ^= bit;
}
}
else if( *( num.beg.cptr ) & bit )
{
*( src.beg.cptr ) |= bit;
carry = 1;
}
}
}
*( src.beg.cptr ) &= clr;
return def;
}
PTRS
__nothrow __stdcall
ecpy( PTRS src, PTRS num )
{
PTRS def = src;
for( uchar i = 1; src.size-- && num.size--; i ^= 1,
src.beg.uptr += i ? src.pos1 : src.pos2,
num.beg.uptr += i ? num.pos1 : num.pos2 )
{
*src.beg.cptr = *num.beg.cptr;
}
return def;
}
PTRS
__nothrow __stdcall
ediv( PTRS quo, PTRS src, PTRS num, ullong *radix, ullong radix_max )
{
if( !quo.SRC || !quo.size ) { return ( PTRS ) { NULL }; }
( void )memset( quo.
SRC, 0, quo.
size ); if( eis0( src, NULL ) || eis0( num, NULL ) ) { return quo; }
void *TMP
= calloc( 1, src.
size ); if( !TMP ) return ( PTRS ) { NULL };
PTRS tmp = endian( TMP, src.size, src.endian );
uchar i = 1, bit;
size_t size = src.size;
//
for( ; !( *src.end.cptr ) && size--; i ^= 1 )
{
src.end.uptr += i ? src.neg1 : src.neg2;
}
//*/
//PTRS def = src;
for( ; size--;//&& emteq( src, num, NULL, NULL );
src.end.uptr += i ? src.neg1 : src.neg2, i ^= 1 )
{
for( bit = uchar_end; bit; bit >>= 1 )
{
( void )eshl1( quo );
( void )eshl1( tmp );
if( *src.end.cptr & bit )
{
*tmp.beg.cptr |= 1;
*src.end.cptr ^= bit;
}
if( emteq( tmp, num, NULL, NULL ) )
{
*quo.beg.cptr |= 1;
( void )esub( tmp, num );
}
}
}
if( radix )
{
for( *radix = 0; *radix < radix_max && !eis0( tmp, NULL ); ++( *radix ) )
{
( void )eshl1( quo );
( void )eshl1( tmp );
if( emteq( tmp, num, NULL, NULL ) )
{
*quo.beg.cptr |= 1;
( void )esub( tmp, num );
}
}
}
( void )memcpy( src.
SRC, TMP
, tmp.
size ); //free( tmp.SRC );
return quo;
}
// Normal Shift & Add Algorithm
PTRS
__nothrow __stdcall
emul( PTRS src, PTRS num )
{
if( UPTR_IS0( src.SRC, src.size, src.pos1, src.pos2 )
|| UPTR_IS0( num.SRC, num.size, num.pos1, num.pos2 ) )
return ( PTRS ) {NULL};
if( eis0( src, NULL ) )
{ return src; }
if( eis0( num, NULL ) )
{
( void )memset( src.
SRC, 0, src.
size ); return src;
}
PTRS def = src;
uchar
*TMP
= calloc( src.
size, 1 ); if( !TMP ) return ( ( PTRS ) {NULL} );
PTRS tmp = endian( TMP, src.size, src.endian );
uchar bit;
for( uchar i = 1; num.size--; i ^= 1, num.beg.uptr += i ? num.pos1 : num.pos2 )
{
for( bit = 1; bit; bit <<= 1, eshl1( src ) )
{
if( *num.beg.cptr & bit ) { ( void )eadd( tmp, src ); }
}
}
( void )memcpy( src.
SRC, TMP
, src.
size ); return def;
}
char
__nothrow __stdcall
getIntEndianEx( schar *i1, schar *i2 )
{
uint num = 0x12345678;
uchar *buf = ( uchar* )( &num );
switch( buf[0] )
{
// 0x123465678
case 0x12:
if( i1 ) { *i1 = -1; }
if( i2 ) { *i2 = -1; }
return 'B';
// 0x78563412
case 0x78:
if( i1 ) { *i1 = 1; }
if( i2 ) { *i2 = 1; }
return 'L';
// 0x56781234
case 0x56:
if( i1 ) { *i1 = 1; }
if( i2 ) { *i2 = -4; }
return 'R';
}
// 0x34127856
if( i1 ) { *i1 = -1; }
if( i2 ) { *i2 = 3; }
return 'M';
}
#define getIntEndian() getIntEndianEx(NULL, NULL)
char
__nothrow __stdcall
getShortEndianEx( schar *i )
{
ushort value = 0x1234;
uchar *buff = ( uchar* )( &value );
switch( *buff )
{
case 0x12:
if( i ) { *i = -1; }
return 'B';
case 0x34:
if( i ) { *i = 1; }
return 'L';
}
if( i ) { *i = 0; }
return 0;
}
#define getShortEndian() getShortEndianEx(NULL)
PTRS
__nothrow __stdcall
emul_karatsuba( PTRS SRC, PTRS NUM )
{
//#error "Bug causing write to BEFORE buffer"
if( SRC.size < 2 || NUM.size < 2
|| elteq( SRC, endian( ( void* )&ushort_max, sizeof( short ),
getShortEndian() ), NULL, NULL ) )
{
return emul( SRC, NUM );
}
PTRS low1 = endian( SRC.SRC, SRC.size / 2, SRC.endian ), high1 = low1;
PTRS low2 = endian( NUM.SRC, NUM.size / 2, NUM.endian ), high2 = low2;
void *SCPY
= malloc( low1.
size ); if( !SCPY ) return ( PTRS ) {NULL};
void *NCPY
= malloc( low2.
size ); if( !NCPY )
{
return ( PTRS ) {NULL};
}
PTRS scpy = endian( SCPY, low1.size, SRC.endian );
PTRS ncpy = endian( NCPY, low2.size, NUM.endian );
uchar si = 1, ni = 1;
( void )memcpy( SCPY
, SRC.
SRC, low1.
size ); ( void )memcpy( NCPY
, NUM.
SRC, low2.
size ); while( SRC.size-- > low1.size )
{
low1.end.uptr += si ? low1.neg1 : low1.neg2;
scpy.end.uptr += si ? low1.neg1 : low1.neg2;
si ^= 1;
}
while( NUM.size-- > low2.size )
{
low2.end.uptr += ni ? low2.neg1 : low2.neg2;
ncpy.end.uptr += ni ? low2.neg1 : low2.neg2;
ni ^= 1;
}
PTRS z0 = emul_karatsuba( endian( scpy.beg.vptr, low1.size, SRC.endian ),
endian( ncpy.beg.vptr, low2.size, NUM.endian ) );
PTRS z2 = emul_karatsuba( endian( scpy.end.vptr, low1.size, SRC.endian ),
endian( ncpy.end.vptr, low2.size, NUM.endian ) );
PTRS z1 = emul_karatsuba( eadd( low1, high1 ), eadd( low2, high2 ) );
eadd( eadd( emul( esub( esub( z1, z2 ), z0 ), endian( &low1.size,
sizeof( size_t ), getIntEndian() ) ), z0 ), emul( z2, endian( &low1.size,
sizeof( size_t ), getIntEndian() ) ) );
return low1;
}
void
__nothrow __stdcall
putt( char *text, uchar result )
{
puts( result
? " succeeded" : " failed" ); }
void
__nothrow __stdcall
puti( char* text, ullong i1, ullong i2, ullong q1, ullong q2 )
{
ullong last = LLONG_BIT, i = last - 1, bit = 1;
char b1[ LLONG_BIT + 1] = "";
char b2[ LLONG_BIT + 1] = "";
char b3[ LLONG_BIT + 1] = "";
char b4[ LLONG_BIT + 1] = "";
do
{
b1[i] = ( i1 & bit ) ? '1' : '0';
b2[i] = ( i2 & bit ) ? '1' : '0';
b3[i] = ( q1 & bit ) ? '1' : '0';
b4[i] = ( q2 & bit ) ? '1' : '0';
bit <<= 1;
--i;
}
while( bit );
b1[last] = b2[last] = b3[last] = b4[last] = '\0';
}
int
main( void )
{
ullong i1 = 9999, i2 = 9999 << 1, q1 = 0, q2 = 0, i = 0;
PTRS Q1 = endian( &q1, sizeof( llong ), getIntEndian() );
//PTRS Q2 = endian( &q2, sizeof( int ), getIntEndian());
PTRS I = endian( &i, sizeof( llong ), getIntEndian() );
PTRS I1 = endian( &i1, sizeof( llong ), getIntEndian() );
//*
PTRS I2 = endian( &i2, sizeof( llong ), getIntEndian() );
putt( "eiseq", !eiseq( I1, I2, NULL, NULL ) );
putt( " emt", !emt( I1, I2, NULL, NULL ) );
putt( "emteq", !emteq( I1, I2, NULL, NULL ) );
putt( " elt", elt( I1, I2, NULL, NULL ) );
putt( "elteq", elteq( I1, I2, NULL, NULL ) );
putt( " eis0", !eis0( I1, NULL ) );
//*/
eshl( I1, 1 );
puti( "<< 1:", i1, i2, q1, q2 );
i2 >>= 7;
eshr( I1, 7 );
puti( ">> 7:", i1, i2, q1, q2 );
i = 177777;
i2 += i;
eadd( I1, I );
puti( "+ 177777:", i1, i2, q1, q2 );
i = 3;
for( i1 = 0; i1 < 3; ++i1 ) { putt( "emteq", !emteq( I1, I, NULL, NULL ) ); }
for( ; i1 < 8; ++i1 ) { putt( "emteq", emteq( I1, I, NULL, NULL ) ); }
i1 = i2 = 3;
i2 -= i;
esub( I1, I );
puti( "3 - 3:", i1, i2, q1, q2 );
i = 55;
i1 = i2 = 55;
i2 *= i;
emul( I1, I );
puti( "55 * 55:", i1, i2, q1, q2 );
i = 88963;
i2 *= i;
emul_karatsuba( I1, I );
puti( "* 88963:", i1, i2, q1, q2 );
i = 3;
q2 = i2 % i;
i2 /= i;
ediv( Q1, I1, I, NULL, 0 );
puti( "/ 3:", i1, i2, q1, q2 );
i1 = q1;
q1 = 0;
q2 = 0;
puts( "Press any key to continue..." ); return 0;
}
I2lmZGVmIF9NU0NfVkVSCiNwcmFnbWEgY29tbWVudChsaW5rZXIsICIvU1VCU1lTVEVNOkNPTlNPTEUgL0VOVFJZOm1haW5DUlRTdGFydHVwIikKI2VuZGlmCiNpbmNsdWRlIDxsaW1pdHMuaD4KI2luY2x1ZGUgPHN0ZGludC5oPgojaW5jbHVkZSA8c3RyaW5nLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIFNIUl9CWVRFUyggVkFMLCBCWVRFUyApIChWQUwgPj4gKENIQVJfQklUICogQllURVMpKQoKI2lmIFVJTlRfTUFYID09IFVDSEFSX01BWAojZGVmaW5lIElOVF9TSVpFIDEKI2VsaWYgVUlOVF9NQVggPT0gVVNIUlRfTUFYCiNkZWZpbmUgSU5UX1NJWkUgMgojZWxpZiBTSFJfQllURVMoVUlOVF9NQVgsNCkgPT0gMAojZGVmaW5lIElOVF9TSVpFIDQKI2Vsc2UKI2RlZmluZSBJTlRfU0laRSA4CiNlbmRpZgoKI2lmIFNIUl9CWVRFUyhVTE9OR19NQVgsNCkgPT0gMAojZGVmaW5lIExPTkdfU0laRSA0CiNlbHNlCiNkZWZpbmUgTE9OR19TSVpFIDgKI2VuZGlmCgojZGVmaW5lIExMT05HX1NJWkUgOAoKI2RlZmluZSAgU0hSVF9CSVQgKDIgKiBDSEFSX0JJVCkKI2RlZmluZSAgIElOVF9CSVQgKElOVF9TSVpFICogQ0hBUl9CSVQpCiNkZWZpbmUgIExPTkdfQklUIChMT05HX1NJWkUgKiBDSEFSX0JJVCkKI2RlZmluZSBMTE9OR19CSVQgKDggKiBDSEFSX0JJVCkKCiNpZm5kZWYgX19ub3Rocm93CiNpZiBkZWZpbmVkKCBfX2F0dHJpYnV0ZV9fICkKI2RlZmluZSBfX25vdGhyb3cgX19hdHRyaWJ1dGVfXygobm90aHJvdykpCiNlbGlmIGRlZmluZWQoIF9fZGVjbHNwZWMgKQojZGVmaW5lIF9fbm90aHJvdyBfX2RlY2xzcGVjKG5vdGhyb3cpCiNlbGlmIGRlZmluZWQoX19ub3Rocm93X18pCiNkZWZpbmUgX19ub3Rocm93IF9fbm90aHJvdwojZWxzZQojZGVmaW5lIF9fbm90aHJvdwojZW5kaWYKI2VuZGlmCgojaWZuZGVmIF9fc3RkY2FsbAojaWYgZGVmaW5lZCggX19hdHRyaWJ1dGVfXyApCiNkZWZpbmUgX19zdGRjYWxsIF9fYXR0cmlidXRlX18oKHN0ZGNhbGwpKQojZWxpZiBkZWZpbmVkKCBfX2RlY2xzcGVjICkKI2RlZmluZSBfX3N0ZGNhbGwgX19kZWNsc3BlYyhzdGRjYWxsKQojZWxpZiBkZWZpbmVkKCBfX3N0ZGNhbGxfXyApCiNkZWZpbmUgX19zdGRjYWxsIF9fc3RkY2FsbF9fCiNlbHNlCiNkZWZpbmUgX19zdGRjYWxsCiNlbmRpZgojZW5kaWYKCnR5cGVkZWYgdW5zaWduZWQgIGNoYXIgIHVjaGFyOwp0eXBlZGVmICAgc2lnbmVkICBjaGFyICBzY2hhcjsKdHlwZWRlZiB1bnNpZ25lZCBzaG9ydCB1c2hvcnQ7CnR5cGVkZWYgdW5zaWduZWQgICBpbnQgICB1aW50Owp0eXBlZGVmIHVuc2lnbmVkICBsb25nICB1bG9uZzsKI2RlZmluZSBMTE9ORyBsb25nIGxvbmcgaW50CnR5cGVkZWYgICAgICAgICAgTExPTkcgIGxsb25nOwp0eXBlZGVmIHVuc2lnbmVkIExMT05HIHVsbG9uZzsKdHlwZWRlZiB1bmlvbiBQVFJVXwp7Cgl2b2lkICAgICAqdnB0cjsKCXVjaGFyICAgICpjcHRyOwoJdWludCAgICAgKmlwdHI7CglpbnRwdHJfdCAgc3B0cjsKCXVpbnRwdHJfdCB1cHRyOwp9IFBUUlU7CnR5cGVkZWYgc3RydWN0IFBUUlNfCnsKCXZvaWQgICAqU1JDOwoJc2l6ZV90IHNpemU7CgljaGFyIGVuZGlhbjsKCWNoYXIgcGFkZGluZ1szXTsKCVBUUlUgICAgYmVnOwoJUFRSVSAgICBlbmQ7CglzY2hhciAgcG9zMTsKCXNjaGFyICBwb3MyOwoJc2NoYXIgIG5lZzE7CglzY2hhciAgbmVnMjsKfSBQVFJTOwoKI2RlZmluZSBMSU1JVFMoVUksU0ksVU1BWCxTTUFYLFNNSU4sT05FKVwKICBzdGF0aWMgY29uc3QgdWNoYXIgVUkjI19iaXQgPSBzaXplb2YoU0kpICogQ0hBUl9CSVQ7XAogIHN0YXRpYyBjb25zdCB1Y2hhciBVSSMjX21vdiA9IChzaXplb2YoU0kpICogQ0hBUl9CSVQpIC0gMTtcCiAgc3RhdGljIGNvbnN0ICAgIFVJIFVJIyNfZW5kID0gT05FIDw8ICgoc2l6ZW9mKFNJKSAqIENIQVJfQklUKSAtIDEpO1wKICBzdGF0aWMgY29uc3QgICAgVUkgVUkjI19tYXggPSBVTUFYO1wKICBzdGF0aWMgY29uc3QgICAgU0kgU0kjI19tYXggPSBTTUFYO1wKICBzdGF0aWMgY29uc3QgICAgU0kgU0kjI19taW4gPSBTTUlOCkxJTUlUUyggdWNoYXIsIHNjaGFyLCAgVUNIQVJfTUFYLCBTQ0hBUl9NQVgsIFNDSEFSX01JTiwgMVUgKTsKTElNSVRTKCB1c2hvcnQsIHNob3J0LCAgVVNIUlRfTUFYLCAgU0hSVF9NQVgsICBTSFJUX01JTiwgMVUgKTsKTElNSVRTKCB1aW50LCAgIGludCwgICBVSU5UX01BWCwgICBJTlRfTUFYLCAgIElOVF9NSU4sIDFVICk7CkxJTUlUUyggdWxvbmcsICBsb25nLCAgVUxPTkdfTUFYLCAgTE9OR19NQVgsICBMT05HX01JTiwgMVVMICk7CkxJTUlUUyggdWxsb25nLCBsbG9uZywgVUxMT05HX01BWCwgTExPTkdfTUFYLCBMTE9OR19NSU4sIDFVTEwgKTsKCiNkZWZpbmUgVVBUUl9JUzAoIE1fMCwgTV9MQVNULCBNX0kxLCBNX0kyICkgKCFNXzAgfHwgIU1fTEFTVCB8fCBNX0kxID09IDAgfHwgTV9JMiA9PSAwKQpQVFJTCl9fbm90aHJvdyBfX3N0ZGNhbGwKZW5kaWFuKCB2b2lkICpTUkMsIHNpemVfdCBzcmNTaXplLCBjaGFyIHNyY0VuZGlhbiApCnsKCVBUUlMgbnVtOwoJUFRSVSBCRUcsIEVORDsKCW51bS5TUkMgPSBTUkM7CgludW0uc2l6ZSA9IHNyY1NpemU7CgludW0uZW5kaWFuID0gc3JjRW5kaWFuOwoJQkVHLnZwdHIgPSBTUkM7CglFTkQudXB0ciA9IEJFRy51cHRyICsgKCBzcmNTaXplIC0gMSApOwoJc3dpdGNoKCBudW0uZW5kaWFuICkKCXsKCS8vIDB4Nzg1NjM0MTIKCWNhc2UgJ0InOgoJY2FzZSAnYic6CgkJbnVtLnBvczEgPSBudW0ucG9zMiA9IC0xOwoJCW51bS5lbmQgPSBCRUc7CgkJbnVtLmJlZyA9IEVORDsKCQlyZXR1cm4gbnVtOwoJLy8gMHgxMjM0NTY3OAoJY2FzZSAnTCc6CgljYXNlICdsJzoKCQludW0ucG9zMSA9IG51bS5wb3MyID0gMTsKCQludW0uZW5kID0gRU5EOwoJCW51bS5iZWcgPSBCRUc7CgkJZ290byBkb25lOwoJLy8gMHg1Njc4MTIzNAoJY2FzZSAnUic6CgljYXNlICdyJzoKCQludW0ucG9zMSA9IC0xOwoJCW51bS5wb3MyID0gNDsKCQludW0uZW5kLnVwdHIgPSArK0JFRy51cHRyOwoJCW51bS5iZWcudXB0ciA9IC0tRU5ELnVwdHI7CgkJZ290byBkb25lOwoJfQoJLy8gMHgzNDEyNzg1NgoJbnVtLmVuZGlhbiA9ICdNJzsKCW51bS5wb3MxID0gMTsKCW51bS5wb3MyID0gLTQ7CgludW0uZW5kLnVwdHIgPSAtLUVORC51cHRyOwoJbnVtLmJlZy51cHRyID0gKytCRUcudXB0cjsKZG9uZToKCW51bS5uZWcxID0gLW51bS5wb3MxOwoJbnVtLm5lZzIgPSAtbnVtLnBvczI7CglyZXR1cm4gbnVtOwp9CnVjaGFyCl9fbm90aHJvdyBfX3N0ZGNhbGwKZWlzMCggUFRSUyBzcmMsIHZvaWQgKipTICkKewoJZm9yKCB1Y2hhciBpID0gMTsgc3JjLnNpemUtLTsgc3JjLmVuZC51cHRyICs9IGkgPyBzcmMubmVnMSA6IHNyYy5uZWcyLCBpIF49IDEgKQoJewoJCWlmKCAqc3JjLmVuZC5jcHRyICkKCQl7CgkJCWlmKCBTICkgeyAqUyA9IHNyYy5lbmQudnB0cjsgfQoJCQlyZXR1cm4gMDsKCQl9Cgl9CglpZiggUyApIHsgKlMgPSBOVUxMOyB9CglyZXR1cm4gMTsKfQp1Y2hhcgpfX25vdGhyb3cgX19zdGRjYWxsCmVpc2VxKCBQVFJTIHNyYywgUFRSUyBudW0sIHZvaWQgKipTLCB2b2lkICoqTiApCnsKCWZvciggdWNoYXIgaSA9IDE7IHNyYy5zaXplICYmIG51bS5zaXplOwoJICAgICBzcmMuZW5kLnVwdHIgKz0gaSA/IHNyYy5uZWcxIDogc3JjLm5lZzIsCgkgICAgIG51bS5lbmQudXB0ciArPSBpID8gbnVtLm5lZzEgOiBudW0ubmVnMiwKCSAgICAgLS1zcmMuc2l6ZSwgLS1udW0uc2l6ZSwgaSBePSAxICkKCXsKCQlpZiggKnNyYy5lbmQuY3B0ciAhPSAqbnVtLmVuZC5jcHRyICkgeyBnb3RvIHN0b3A7IH0KCX0KCWlmKCAhc3JjLnNpemUgKQoJewoJCWlmKCBOICkgeyAqTiA9IG51bS5lbmQudnB0cjsgfQoJCWlmKCBTICkgeyAqUyA9IHNyYy5lbmQudnB0cjsgfQoJCWlmKCAhbnVtLnNpemUgKSB7IHJldHVybiAxOyB9CgkJcmV0dXJuIDA7Cgl9CglpZiggIW51bS5zaXplICkKCXsKc3RvcDoKCQlpZiggTiApIHsgKk4gPSBudW0uZW5kLnZwdHI7IH0KCQlpZiggUyApIHsgKlMgPSBzcmMuZW5kLnZwdHI7IH0KCQlyZXR1cm4gMDsKCX0KCWlmKCBOICkgeyAqTiA9IG51bS5lbmQudnB0cjsgfQoJaWYoIFMgKSB7ICpTID0gc3JjLmVuZC52cHRyOyB9CglyZXR1cm4gMTsKfQp1Y2hhcgpfX25vdGhyb3cgX19zdGRjYWxsCmVtdGVxKCBQVFJTIHNyYywgUFRSUyBudW0sIHZvaWQgKipTLCB2b2lkICoqTiApCnsKCXZvaWQgKnMsICpuOwoJaWYoICFTICkgeyBTID0gJnM7IH0KCWlmKCAhTiApIHsgTiA9ICZuOyB9CglpZiggZWlzZXEoIHNyYywgbnVtLCBTLCBOICkgfHwgKiooICggdWNoYXIqKiApUyApID4gKiooICggdWNoYXIqKiApTiApICkKCXsgcmV0dXJuIDE7IH0KCXJldHVybiAwOwp9CnVjaGFyCl9fbm90aHJvdyBfX3N0ZGNhbGwKZW10KCBQVFJTIHNyYywgUFRSUyBudW0sIHZvaWQgKipTLCB2b2lkICoqTiApCnsKCXZvaWQgKnMsICpuOwoJaWYoICFTICkgeyBTID0gJnM7IH0KCWlmKCAhTiApIHsgTiA9ICZuOyB9CglpZiggIWVpc2VxKCBzcmMsIG51bSwgUywgTiApICYmICoqKCAoIHVjaGFyKiogKVMgKSA+ICoqKCAoIHVjaGFyKiogKU4gKSApCgl7IHJldHVybiAxOyB9CglyZXR1cm4gMDsKfQp1Y2hhcgpfX25vdGhyb3cgX19zdGRjYWxsCmVsdGVxKCBQVFJTIHNyYywgUFRSUyBudW0sIHZvaWQgKipTLCB2b2lkICoqTiApCnsKCXZvaWQgKnMsICpuOwoJaWYoICFTICkgeyBTID0gJnM7IH0KCWlmKCAhTiApIHsgTiA9ICZuOyB9CglpZiggZWlzZXEoIHNyYywgbnVtLCBTLCBOICkgfHwgKiooICggdWNoYXIqKiApUyApIDwgKiooICggdWNoYXIqKiApTiApICkKCXsgcmV0dXJuIDE7IH0KCXJldHVybiAwOwp9CnVjaGFyCl9fbm90aHJvdyBfX3N0ZGNhbGwKZWx0KCBQVFJTIHNyYywgUFRSUyBudW0sIHZvaWQgKipTLCB2b2lkICoqTiApCnsKCXZvaWQgKnMsICpuOwoJaWYoICFTICkgeyBTID0gJnM7IH0KCWlmKCAhTiApIHsgTiA9ICZuOyB9CglpZiggIWVpc2VxKCBzcmMsIG51bSwgUywgTiApICYmICoqKCAoIHVjaGFyKiogKVMgKSA8ICoqKCAoIHVjaGFyKiogKU4gKSApCgl7IHJldHVybiAxOyB9CglyZXR1cm4gMDsKfQpQVFJTCl9fbm90aHJvdyBfX3N0ZGNhbGwKZXNociggUFRSUyBzcmMsIHVsbG9uZyBiaXRzICkKewoJaWYoICFiaXRzICkgeyByZXR1cm4gc3JjOyB9CglQVFJTIGRlZiA9IHNyYzsKCVBUUlMgZHN0ID0gc3JjOwoJdWNoYXIgZGkgPSAxLCBuaSA9IDEsIHJiaXRzID0gMCwgbGJpdHMgPSAwOwoJd2hpbGUoIGJpdHMgPj0gdWNoYXJfYml0ICYmIGRzdC5zaXplLS0gKQoJewoJCWRzdC5iZWcudXB0ciArPSBkaSA/IGRzdC5wb3MxIDogZHN0LnBvczI7CgkJYml0cyAtPSB1Y2hhcl9iaXQ7Cgl9CglpZiggYml0cyA+PSB1Y2hhcl9iaXQgKQoJewoJCSggdm9pZCApbWVtc2V0KCBzcmMuU1JDLCAwLCBzcmMuc2l6ZSApOwoJCXJldHVybiBkZWY7Cgl9CglpZiggZHN0LnNpemUgPCBzcmMuc2l6ZSApCgl7CgkJd2hpbGUoIGRzdC5zaXplLS0gKQoJCXsKCQkJKnNyYy5iZWcuY3B0ciA9ICpkc3QuYmVnLmNwdHI7CgkJCSpkc3QuYmVnLmNwdHIgPSAwOwoJCQlkc3QuYmVnLnVwdHIgKz0gZGkgPyBkc3QucG9zMSA6IGRzdC5wb3MyOwoJCQlzcmMuYmVnLnVwdHIgKz0gbmkgPyBzcmMucG9zMSA6IHNyYy5wb3MyOwoJCX0KCX0KCXVsbG9uZyBtb3ZlID0gQ0hBUl9CSVQgLSBiaXRzOwoJd2hpbGUoIHNyYy5zaXplLS0gKQoJewoJCXJiaXRzID0gbGJpdHM7CgkJbGJpdHMgPSAqc3JjLmVuZC5jcHRyIDw8IG1vdmU7CgkJKnNyYy5lbmQuY3B0ciA+Pj0gYml0czsKCQkqc3JjLmVuZC5jcHRyIHw9IHJiaXRzOwoJCXNyYy5lbmQudXB0ciArPSBuaSA/IHNyYy5uZWcxIDogc3JjLm5lZzI7CgkJbmkgXj0gMTsKCX0KCXJldHVybiBkZWY7Cn0KUFRSUwpfX25vdGhyb3cgX19zdGRjYWxsCmVzaGwoIFBUUlMgc3JjLCB1bGxvbmcgYml0cyApCnsKCWlmKCAhYml0cyApIHsgcmV0dXJuIHNyYzsgfQoJUFRSUyBkZWYgPSBzcmM7CglQVFJTIGRzdCA9IHNyYzsKCXVjaGFyIGRpID0gMSwgc2kgPSAxLCByYml0cyA9IDAsIGxiaXRzID0gMDsKCXdoaWxlKCBiaXRzID49IHVjaGFyX2JpdCAmJiBkc3Quc2l6ZS0tICkKCXsKCQlkc3QuZW5kLnVwdHIgKz0gZGkgPyBkc3QubmVnMSA6IGRzdC5uZWcyOwoJCWJpdHMgLT0gdWNoYXJfYml0OwoJfQoJaWYoIGJpdHMgPj0gdWNoYXJfYml0ICkKCXsKCQkoIHZvaWQgKW1lbXNldCggc3JjLlNSQywgMCwgc3JjLnNpemUgKTsKCQlyZXR1cm4gZGVmOwoJfQoJaWYoIGRzdC5zaXplIDwgc3JjLnNpemUgKQoJewoJCXdoaWxlKCBkc3Quc2l6ZS0tICkKCQl7CgkJCSpzcmMuZW5kLmNwdHIgPSAqZHN0LmVuZC5jcHRyOwoJCQkqZHN0LmVuZC5jcHRyID0gMDsKCQkJZHN0LmVuZC51cHRyICs9IGRpID8gZHN0Lm5lZzEgOiBkc3QubmVnMjsKCQkJc3JjLmVuZC51cHRyICs9IHNpID8gc3JjLm5lZzEgOiBzcmMubmVnMjsKCQl9Cgl9CglzaSA9IDE7Cgl1bGxvbmcgbW92ZSA9IENIQVJfQklUIC0gYml0czsKCXdoaWxlKCBzcmMuc2l6ZS0tICkKCXsKCQlsYml0cyA9IHJiaXRzOwoJCXJiaXRzID0gKnNyYy5iZWcuY3B0ciA+PiBtb3ZlOwoJCSpzcmMuYmVnLmNwdHIgPDw9IGJpdHM7CgkJKnNyYy5iZWcuY3B0ciB8PSBsYml0czsKCQlzcmMuYmVnLnVwdHIgKz0gc2kgPyBzcmMucG9zMSA6IHNyYy5wb3MyOwoJCXNpIF49IDE7Cgl9CglyZXR1cm4gZGVmOwp9ClBUUlMKX19ub3Rocm93IF9fc3RkY2FsbAplc2hsMSggUFRSUyBzcmMgKQp7CglQVFJTIGRlZiA9IHNyYzsKCXVjaGFyIGkgPSAxLCByYml0cyA9IDAsIGxiaXRzID0gMDsKCWZvciggOyBzcmMuc2l6ZS0tOyBpIF49IDEgKQoJewoJCWxiaXRzID0gcmJpdHM7CgkJcmJpdHMgPSAqc3JjLmJlZy5jcHRyID4+IHVjaGFyX21vdjsKCQkqc3JjLmJlZy5jcHRyIDw8PSAxOwoJCSpzcmMuYmVnLmNwdHIgfD0gbGJpdHM7CgkJc3JjLmJlZy51cHRyICs9IGkgPyBzcmMucG9zMSA6IHNyYy5wb3MyOwoJfQoJcmV0dXJuIGRlZjsKfQpQVFJTCl9fbm90aHJvdyBfX3N0ZGNhbGwKZXNocjEoIFBUUlMgc3JjICkKewoJUFRSUyBkZWYgPSBzcmM7Cgl1Y2hhciBpID0gMSwgcmJpdHMgPSAwLCBsYml0cyA9IDA7Cglmb3IoIDsgc3JjLnNpemUtLTsgaSBePSAxICkKCXsKCQlyYml0cyA9IGxiaXRzOwoJCWxiaXRzID0gKnNyYy5iZWcuY3B0ciA8PCB1Y2hhcl9tb3Y7CgkJKnNyYy5iZWcuY3B0ciA+Pj0gMTsKCQkqc3JjLmJlZy5jcHRyIHw9IHJiaXRzOwoJCXNyYy5iZWcudXB0ciArPSBpID8gc3JjLnBvczEgOiBzcmMucG9zMjsKCX0KCXJldHVybiBkZWY7Cn0KUFRSUwpfX25vdGhyb3cgX19zdGRjYWxsCmVhbmQoIFBUUlMgc3JjLCBQVFJTIG51bSApCnsKCVBUUlMgZGVmID0gc3JjOwoJZm9yKCB1Y2hhciBpID0gMTsgc3JjLnNpemUtLSAmJiBudW0uc2l6ZS0tOyBpIF49IDEgKQoJewoJCSpzcmMuYmVnLmNwdHIgJj0gKm51bS5iZWcuY3B0cjsKCQlzcmMuYmVnLnVwdHIgKz0gaSA/IHNyYy5wb3MxIDogc3JjLnBvczI7CgkJbnVtLmJlZy51cHRyICs9IGkgPyBudW0ucG9zMSA6IHNyYy5wb3MyOwoJfQoJcmV0dXJuIGRlZjsKfQp1Y2hhcgpfX25vdGhyb3cgX19zdGRjYWxsCmVpbmMoIFBUUlMgbnVtICkKewoJdWNoYXIgYml0LCBpID0gMTsKCWZvciggOyBudW0uc2l6ZS0tOyBpIF49IDEsIG51bS5iZWcudXB0ciArPSBpID8gbnVtLnBvczEgOiBudW0ucG9zMiApCgl7CgkJZm9yKCBiaXQgPSAxOyBiaXQ7IGJpdCA8PD0gMSApCgkJewoJCQlpZiggKm51bS5iZWcuY3B0ciAmIGJpdCApCgkJCXsKCQkJCSpudW0uYmVnLmNwdHIgXj0gYml0OwoJCQl9CgkJCWVsc2UKCQkJewoJCQkJKm51bS5iZWcuY3B0ciB8PSBiaXQ7CgkJCQlyZXR1cm4gMTsKCQkJfQoJCX0KCX0KCXJldHVybiAxOwp9ClBUUlMKX19ub3Rocm93IF9fc3RkY2FsbAplYWRkKCBQVFJTIHNyYywgUFRSUyBudW0gKQp7CglQVFJTIGRlZiA9IHNyYzsKCXVjaGFyIGNhcnJ5ID0gMCwgYml0OwoJZm9yKCB1Y2hhciBpID0gMTsgc3JjLnNpemUtLSAmJiBudW0uc2l6ZS0tOyBpIF49IDEsCgkgICAgIHNyYy5iZWcudXB0ciArPSBpID8gc3JjLnBvczEgOiBzcmMucG9zMiwKCSAgICAgbnVtLmJlZy51cHRyICs9IGkgPyBudW0ucG9zMSA6IG51bS5wb3MyICkKCXsKCQlmb3IoIGJpdCA9IDE7IGJpdDsgYml0IDw8PSAxICkKCQl7CgkJCWlmKCBjYXJyeSApCgkJCXsKCQkJCWlmKCAqc3JjLmJlZy5jcHRyICYgYml0ICkKCQkJCXsKCQkJCQkqc3JjLmJlZy5jcHRyIF49IGJpdDsKCQkJCX0KCQkJCWVsc2UKCQkJCXsKCQkJCQkqc3JjLmJlZy5jcHRyIHw9IGJpdDsKCQkJCQljYXJyeSA9IDA7CgkJCQl9CgkJCX0KCQkJaWYoICpzcmMuYmVnLmNwdHIgJiBiaXQgKQoJCQl7CgkJCQlpZiggKm51bS5iZWcuY3B0ciAmIGJpdCApCgkJCQl7CgkJCQkJKnNyYy5iZWcuY3B0ciBePSBiaXQ7CgkJCQkJY2FycnkgPSAxOwoJCQkJfQoJCQl9CgkJCWVsc2UgaWYoICpudW0uYmVnLmNwdHIgJiBiaXQgKQoJCQl7CgkJCQkqc3JjLmJlZy5jcHRyIHw9IGJpdDsKCQkJfQoJCX0KCX0KCXJldHVybiBkZWY7Cn0KUFRSUwpfX25vdGhyb3cgX19zdGRjYWxsCmVzdWIoIFBUUlMgc3JjLCBQVFJTIG51bSApCnsKCVBUUlMgZGVmID0gc3JjOwoJdWNoYXIgY2FycnkgPSAwLCBiaXQgPSB1Y2hhcl9lbmQsIGNsciA9IDAsIGkgPSAxOwoJZm9yKCBzaXplX3Qgc3JjU2l6ZSA9IHNyYy5zaXplOyAhKCAqc3JjLmVuZC5jcHRyICkgJiYgc3JjU2l6ZS0tOyBpIF49IDEgKQoJewoJCXNyYy5lbmQudXB0ciArPSBpID8gc3JjLm5lZzEgOiBzcmMubmVnMjsKCX0KCXdoaWxlKCBiaXQgJiYgISggKnNyYy5lbmQuY3B0ciAmIGJpdCApICkKCXsKCQljbHIgfD0gYml0OwoJCWJpdCA+Pj0gMTsKCX0KCWNsciA9IH5jbHI7Cglmb3IoIGkgPSAxOyBzcmMuc2l6ZS0tICYmIG51bS5zaXplLS07CgkgICAgIHNyYy5iZWcudXB0ciArPSBpID8gc3JjLnBvczEgOiBzcmMucG9zMiwKCSAgICAgbnVtLmJlZy51cHRyICs9IGkgPyBudW0ucG9zMSA6IG51bS5wb3MyLCBpIF49IDEgKQoJewoJCWZvciggYml0ID0gMTsgYml0OyBiaXQgPDw9IDEgKQoJCXsKCQkJaWYoIGNhcnJ5ICkKCQkJewoJCQkJaWYoICooIHNyYy5iZWcuY3B0ciApICYgYml0ICkKCQkJCXsKCQkJCQkqKCBzcmMuYmVnLmNwdHIgKSBePSBiaXQ7CgkJCQkJY2FycnkgPSAwOwoJCQkJfQoJCQkJZWxzZQoJCQkJewoJCQkJCSooIHNyYy5iZWcuY3B0ciApIHw9IGJpdDsKCQkJCX0KCQkJfQoJCQlpZiggKiggc3JjLmJlZy5jcHRyICkgJiBiaXQgKQoJCQl7CgkJCQlpZiggKiggbnVtLmJlZy5jcHRyICkgJiBiaXQgKQoJCQkJewoJCQkJCSooIHNyYy5iZWcuY3B0ciApIF49IGJpdDsKCQkJCX0KCQkJfQoJCQllbHNlIGlmKCAqKCBudW0uYmVnLmNwdHIgKSAmIGJpdCApCgkJCXsKCQkJCSooIHNyYy5iZWcuY3B0ciApIHw9IGJpdDsKCQkJCWNhcnJ5ID0gMTsKCQkJfQoJCX0KCX0KCSooIHNyYy5iZWcuY3B0ciApICY9IGNscjsKCXJldHVybiBkZWY7Cn0KUFRSUwpfX25vdGhyb3cgX19zdGRjYWxsCmVjcHkoIFBUUlMgc3JjLCBQVFJTIG51bSApCnsKCVBUUlMgZGVmID0gc3JjOwoJZm9yKCB1Y2hhciBpID0gMTsgc3JjLnNpemUtLSAmJiBudW0uc2l6ZS0tOyBpIF49IDEsCgkgICAgIHNyYy5iZWcudXB0ciArPSBpID8gc3JjLnBvczEgOiBzcmMucG9zMiwKCSAgICAgbnVtLmJlZy51cHRyICs9IGkgPyBudW0ucG9zMSA6IG51bS5wb3MyICkKCXsKCQkqc3JjLmJlZy5jcHRyID0gKm51bS5iZWcuY3B0cjsKCX0KCXJldHVybiBkZWY7Cn0KClBUUlMKX19ub3Rocm93IF9fc3RkY2FsbAplZGl2KCBQVFJTIHF1bywgUFRSUyBzcmMsIFBUUlMgbnVtLCB1bGxvbmcgKnJhZGl4LCB1bGxvbmcgcmFkaXhfbWF4ICkKewoJaWYoICFxdW8uU1JDIHx8ICFxdW8uc2l6ZSApIHsgcmV0dXJuICggUFRSUyApIHsgTlVMTCB9OyB9CgkoIHZvaWQgKW1lbXNldCggcXVvLlNSQywgMCwgcXVvLnNpemUgKTsKCWlmKCBlaXMwKCBzcmMsIE5VTEwgKSB8fCBlaXMwKCBudW0sIE5VTEwgKSApIHsgcmV0dXJuIHF1bzsgfQoJdm9pZCAqVE1QID0gY2FsbG9jKCAxLCBzcmMuc2l6ZSApOwoJaWYoICFUTVAgKSByZXR1cm4gKCBQVFJTICkgeyBOVUxMIH07CglQVFJTIHRtcCA9IGVuZGlhbiggVE1QLCBzcmMuc2l6ZSwgc3JjLmVuZGlhbiApOwoJdWNoYXIgaSA9IDEsIGJpdDsKCXNpemVfdCBzaXplID0gc3JjLnNpemU7CgkvLwoJZm9yKCA7ICEoICpzcmMuZW5kLmNwdHIgKSAmJiBzaXplLS07IGkgXj0gMSApCgl7CgkJc3JjLmVuZC51cHRyICs9IGkgPyBzcmMubmVnMSA6IHNyYy5uZWcyOwoJfQoJLy8qLwoJLy9QVFJTIGRlZiA9IHNyYzsKCWZvciggOyBzaXplLS07Ly8mJiBlbXRlcSggc3JjLCBudW0sIE5VTEwsIE5VTEwgKTsKCSAgICAgc3JjLmVuZC51cHRyICs9IGkgPyBzcmMubmVnMSA6IHNyYy5uZWcyLCBpIF49IDEgKQoJewoJCWZvciggYml0ID0gdWNoYXJfZW5kOyBiaXQ7IGJpdCA+Pj0gMSApCgkJewoJCQkoIHZvaWQgKWVzaGwxKCBxdW8gKTsKCQkJKCB2b2lkICllc2hsMSggdG1wICk7CgkJCWlmKCAqc3JjLmVuZC5jcHRyICYgYml0ICkKCQkJewoJCQkJKnRtcC5iZWcuY3B0ciB8PSAxOwoJCQkJKnNyYy5lbmQuY3B0ciBePSBiaXQ7CgkJCX0KCQkJaWYoIGVtdGVxKCB0bXAsIG51bSwgTlVMTCwgTlVMTCApICkKCQkJewoJCQkJKnF1by5iZWcuY3B0ciB8PSAxOwoJCQkJKCB2b2lkICllc3ViKCB0bXAsIG51bSApOwoJCQl9CgkJfQoJfQoJaWYoIHJhZGl4ICkKCXsKCQlmb3IoICpyYWRpeCA9IDA7ICpyYWRpeCA8IHJhZGl4X21heCAmJiAhZWlzMCggdG1wLCBOVUxMICk7ICsrKCAqcmFkaXggKSApCgkJewoJCQkoIHZvaWQgKWVzaGwxKCBxdW8gKTsKCQkJKCB2b2lkICllc2hsMSggdG1wICk7CgkJCWlmKCBlbXRlcSggdG1wLCBudW0sIE5VTEwsIE5VTEwgKSApCgkJCXsKCQkJCSpxdW8uYmVnLmNwdHIgfD0gMTsKCQkJCSggdm9pZCApZXN1YiggdG1wLCBudW0gKTsKCQkJfQoJCX0KCX0KCSggdm9pZCApbWVtY3B5KCBzcmMuU1JDLCBUTVAsIHRtcC5zaXplICk7CgkvL2ZyZWUoIHRtcC5TUkMgKTsKCXJldHVybiBxdW87Cn0KCi8vIE5vcm1hbCBTaGlmdCAmIEFkZCBBbGdvcml0aG0KUFRSUwpfX25vdGhyb3cgX19zdGRjYWxsCmVtdWwoIFBUUlMgc3JjLCBQVFJTIG51bSApCnsKCWlmKCBVUFRSX0lTMCggc3JjLlNSQywgc3JjLnNpemUsIHNyYy5wb3MxLCBzcmMucG9zMiApCgkgICAgfHwgVVBUUl9JUzAoIG51bS5TUkMsIG51bS5zaXplLCBudW0ucG9zMSwgbnVtLnBvczIgKSApCgkJcmV0dXJuICggUFRSUyApIHtOVUxMfTsKCWlmKCBlaXMwKCBzcmMsIE5VTEwgKSApCgl7IHJldHVybiBzcmM7IH0KCWlmKCBlaXMwKCBudW0sIE5VTEwgKSApCgl7CgkJKCB2b2lkICltZW1zZXQoIHNyYy5TUkMsIDAsIHNyYy5zaXplICk7CgkJcmV0dXJuIHNyYzsKCX0KCVBUUlMgZGVmID0gc3JjOwoJdWNoYXIgKlRNUCA9IGNhbGxvYyggc3JjLnNpemUsIDEgKTsKCWlmKCAhVE1QICkgcmV0dXJuICggKCBQVFJTICkge05VTEx9ICk7CglQVFJTIHRtcCA9IGVuZGlhbiggVE1QLCBzcmMuc2l6ZSwgc3JjLmVuZGlhbiApOwoJdWNoYXIgYml0OwoJZm9yKCB1Y2hhciBpID0gMTsgbnVtLnNpemUtLTsgaSBePSAxLCBudW0uYmVnLnVwdHIgKz0gaSA/IG51bS5wb3MxIDogbnVtLnBvczIgKQoJewoJCWZvciggYml0ID0gMTsgYml0OyBiaXQgPDw9IDEsIGVzaGwxKCBzcmMgKSApCgkJewoJCQlpZiggKm51bS5iZWcuY3B0ciAmIGJpdCApIHsgKCB2b2lkICllYWRkKCB0bXAsIHNyYyApOyB9CgkJfQoJfQoJKCB2b2lkICltZW1jcHkoIHNyYy5TUkMsIFRNUCwgc3JjLnNpemUgKTsKCWZyZWUoIFRNUCApOwoJcmV0dXJuIGRlZjsKfQpjaGFyCl9fbm90aHJvdyBfX3N0ZGNhbGwKZ2V0SW50RW5kaWFuRXgoIHNjaGFyICppMSwgc2NoYXIgKmkyICkKewoJdWludCBudW0gPSAweDEyMzQ1Njc4OwoJdWNoYXIgKmJ1ZiA9ICggdWNoYXIqICkoICZudW0gKTsKCXN3aXRjaCggYnVmWzBdICkKCXsKCS8vIDB4MTIzNDY1Njc4CgljYXNlIDB4MTI6CgkJaWYoIGkxICkgeyAqaTEgPSAtMTsgfQoJCWlmKCBpMiApIHsgKmkyID0gLTE7IH0KCQlyZXR1cm4gJ0InOwoJLy8gMHg3ODU2MzQxMgoJY2FzZSAweDc4OgoJCWlmKCBpMSApIHsgKmkxID0gMTsgfQoJCWlmKCBpMiApIHsgKmkyID0gMTsgfQoJCXJldHVybiAnTCc7CgkvLyAweDU2NzgxMjM0CgljYXNlIDB4NTY6CgkJaWYoIGkxICkgeyAqaTEgPSAxOyB9CgkJaWYoIGkyICkgeyAqaTIgPSAtNDsgfQoJCXJldHVybiAnUic7Cgl9CgkvLyAweDM0MTI3ODU2CglpZiggaTEgKSB7ICppMSA9IC0xOyB9CglpZiggaTIgKSB7ICppMiA9IDM7IH0KCXJldHVybiAnTSc7Cn0KI2RlZmluZSBnZXRJbnRFbmRpYW4oKSBnZXRJbnRFbmRpYW5FeChOVUxMLCBOVUxMKQpjaGFyCl9fbm90aHJvdyBfX3N0ZGNhbGwKZ2V0U2hvcnRFbmRpYW5FeCggc2NoYXIgKmkgKQp7Cgl1c2hvcnQgdmFsdWUgPSAweDEyMzQ7Cgl1Y2hhciAqYnVmZiA9ICggdWNoYXIqICkoICZ2YWx1ZSApOwoJc3dpdGNoKCAqYnVmZiApCgl7CgljYXNlIDB4MTI6CgkJaWYoIGkgKSB7ICppID0gLTE7IH0KCQlyZXR1cm4gJ0InOwoJY2FzZSAweDM0OgoJCWlmKCBpICkgeyAqaSA9IDE7IH0KCQlyZXR1cm4gJ0wnOwoJfQoJaWYoIGkgKSB7ICppID0gMDsgfQoJcmV0dXJuIDA7Cn0KI2RlZmluZSBnZXRTaG9ydEVuZGlhbigpIGdldFNob3J0RW5kaWFuRXgoTlVMTCkKUFRSUwpfX25vdGhyb3cgX19zdGRjYWxsCmVtdWxfa2FyYXRzdWJhKCBQVFJTIFNSQywgUFRSUyBOVU0gKQp7Ci8vI2Vycm9yICJCdWcgY2F1c2luZyB3cml0ZSB0byBCRUZPUkUgYnVmZmVyIgoJaWYoIFNSQy5zaXplIDwgMiB8fCBOVU0uc2l6ZSA8IDIKCSAgICB8fCBlbHRlcSggU1JDLCBlbmRpYW4oICggdm9pZCogKSZ1c2hvcnRfbWF4LCBzaXplb2YoIHNob3J0ICksCgkgICAgICAgICAgICAgICAgICAgICAgICAgICBnZXRTaG9ydEVuZGlhbigpICksIE5VTEwsIE5VTEwgKSApCgl7CgkJcmV0dXJuIGVtdWwoIFNSQywgTlVNICk7Cgl9CglQVFJTIGxvdzEgPSBlbmRpYW4oIFNSQy5TUkMsIFNSQy5zaXplIC8gMiwgU1JDLmVuZGlhbiApLCBoaWdoMSA9IGxvdzE7CglQVFJTIGxvdzIgPSBlbmRpYW4oIE5VTS5TUkMsIE5VTS5zaXplIC8gMiwgTlVNLmVuZGlhbiApLCBoaWdoMiA9IGxvdzI7Cgl2b2lkICpTQ1BZID0gbWFsbG9jKCBsb3cxLnNpemUgKTsKCWlmKCAhU0NQWSApIHJldHVybiAoIFBUUlMgKSB7TlVMTH07Cgl2b2lkICpOQ1BZID0gbWFsbG9jKCBsb3cyLnNpemUgKTsKCWlmKCAhTkNQWSApCgl7CgkJZnJlZSggU0NQWSApOwoJCXJldHVybiAoIFBUUlMgKSB7TlVMTH07Cgl9CglQVFJTIHNjcHkgPSBlbmRpYW4oIFNDUFksIGxvdzEuc2l6ZSwgU1JDLmVuZGlhbiApOwoJUFRSUyBuY3B5ID0gZW5kaWFuKCBOQ1BZLCBsb3cyLnNpemUsIE5VTS5lbmRpYW4gKTsKCXVjaGFyIHNpID0gMSwgbmkgPSAxOwoJKCB2b2lkICltZW1jcHkoIFNDUFksIFNSQy5TUkMsIGxvdzEuc2l6ZSApOwoJKCB2b2lkICltZW1jcHkoIE5DUFksIE5VTS5TUkMsIGxvdzIuc2l6ZSApOwoJd2hpbGUoIFNSQy5zaXplLS0gPiBsb3cxLnNpemUgKQoJewoJCWxvdzEuZW5kLnVwdHIgKz0gc2kgPyBsb3cxLm5lZzEgOiBsb3cxLm5lZzI7CgkJc2NweS5lbmQudXB0ciArPSBzaSA/IGxvdzEubmVnMSA6IGxvdzEubmVnMjsKCQlzaSBePSAxOwoJfQoJd2hpbGUoIE5VTS5zaXplLS0gPiBsb3cyLnNpemUgKQoJewoJCWxvdzIuZW5kLnVwdHIgKz0gbmkgPyBsb3cyLm5lZzEgOiBsb3cyLm5lZzI7CgkJbmNweS5lbmQudXB0ciArPSBuaSA/IGxvdzIubmVnMSA6IGxvdzIubmVnMjsKCQluaSBePSAxOwoJfQoJUFRSUyB6MCA9IGVtdWxfa2FyYXRzdWJhKCBlbmRpYW4oIHNjcHkuYmVnLnZwdHIsIGxvdzEuc2l6ZSwgU1JDLmVuZGlhbiApLAoJICAgICAgICAgICAgICAgICAgICAgICAgICBlbmRpYW4oIG5jcHkuYmVnLnZwdHIsIGxvdzIuc2l6ZSwgTlVNLmVuZGlhbiApICk7CglQVFJTIHoyID0gZW11bF9rYXJhdHN1YmEoIGVuZGlhbiggc2NweS5lbmQudnB0ciwgbG93MS5zaXplLCBTUkMuZW5kaWFuICksCgkgICAgICAgICAgICAgICAgICAgICAgICAgIGVuZGlhbiggbmNweS5lbmQudnB0ciwgbG93Mi5zaXplLCBOVU0uZW5kaWFuICkgKTsKCVBUUlMgejEgPSBlbXVsX2thcmF0c3ViYSggZWFkZCggbG93MSwgaGlnaDEgKSwgZWFkZCggbG93MiwgaGlnaDIgKSApOwoJZWFkZCggZWFkZCggZW11bCggZXN1YiggZXN1YiggejEsIHoyICksIHowICksIGVuZGlhbiggJmxvdzEuc2l6ZSwKCSAgICAgICAgICAgICAgICAgIHNpemVvZiggc2l6ZV90ICksIGdldEludEVuZGlhbigpICkgKSwgejAgKSwgZW11bCggejIsIGVuZGlhbiggJmxvdzEuc2l6ZSwKCSAgICAgICAgICAgICAgICAgICAgICBzaXplb2YoIHNpemVfdCApLCBnZXRJbnRFbmRpYW4oKSApICkgKTsKCWZyZWUoIFNDUFkgKTsKCWZyZWUoIE5DUFkgKTsKCXJldHVybiBsb3cxOwp9CnZvaWQKX19ub3Rocm93IF9fc3RkY2FsbApwdXR0KCBjaGFyICp0ZXh0LCB1Y2hhciByZXN1bHQgKQp7CglmcHV0cyggdGV4dCwgc3Rkb3V0ICk7CglwdXRzKCByZXN1bHQgPyAiIHN1Y2NlZWRlZCIgOiAiIGZhaWxlZCIgKTsKfQp2b2lkCl9fbm90aHJvdyBfX3N0ZGNhbGwKcHV0aSggY2hhciogdGV4dCwgdWxsb25nIGkxLCB1bGxvbmcgaTIsIHVsbG9uZyBxMSwgdWxsb25nIHEyICkKewoJdWxsb25nIGxhc3QgPSBMTE9OR19CSVQsIGkgPSBsYXN0IC0gMSwgYml0ID0gMTsKCWNoYXIgYjFbIExMT05HX0JJVCArIDFdID0gIiI7CgljaGFyIGIyWyBMTE9OR19CSVQgKyAxXSA9ICIiOwoJY2hhciBiM1sgTExPTkdfQklUICsgMV0gPSAiIjsKCWNoYXIgYjRbIExMT05HX0JJVCArIDFdID0gIiI7CglkbwoJewoJCWIxW2ldID0gKCBpMSAmIGJpdCApID8gJzEnIDogJzAnOwoJCWIyW2ldID0gKCBpMiAmIGJpdCApID8gJzEnIDogJzAnOwoJCWIzW2ldID0gKCBxMSAmIGJpdCApID8gJzEnIDogJzAnOwoJCWI0W2ldID0gKCBxMiAmIGJpdCApID8gJzEnIDogJzAnOwoJCWJpdCA8PD0gMTsKCQktLWk7Cgl9Cgl3aGlsZSggYml0ICk7CgliMVtsYXN0XSA9IGIyW2xhc3RdID0gYjNbbGFzdF0gPSBiNFtsYXN0XSA9ICdcMCc7CglwdXRzKCB0ZXh0ICk7CglwdXRzKCBiMSApOwoJcHV0cyggYjIgKTsKCXB1dHMoIGIzICk7CglwdXRzKCBiNCApOwp9CgppbnQKbWFpbiggdm9pZCApCnsKCXVsbG9uZyBpMSA9IDk5OTksIGkyID0gOTk5OSA8PCAxLCBxMSA9IDAsIHEyID0gMCwgaSA9IDA7CglQVFJTIFExID0gZW5kaWFuKCAmcTEsIHNpemVvZiggbGxvbmcgKSwgZ2V0SW50RW5kaWFuKCkgKTsKCS8vUFRSUyBRMiA9IGVuZGlhbiggJnEyLCBzaXplb2YoIGludCApLCBnZXRJbnRFbmRpYW4oKSk7CglQVFJTICBJID0gZW5kaWFuKCAmaSwgc2l6ZW9mKCBsbG9uZyApLCBnZXRJbnRFbmRpYW4oKSApOwoJUFRSUyBJMSA9IGVuZGlhbiggJmkxLCBzaXplb2YoIGxsb25nICksIGdldEludEVuZGlhbigpICk7CgkvLyoKCVBUUlMgSTIgPSBlbmRpYW4oICZpMiwgc2l6ZW9mKCBsbG9uZyApLCBnZXRJbnRFbmRpYW4oKSApOwoJcHV0dCggImVpc2VxIiwgIWVpc2VxKCBJMSwgSTIsIE5VTEwsIE5VTEwgKSApOwoJcHV0dCggIiAgZW10IiwgICAhZW10KCBJMSwgSTIsIE5VTEwsIE5VTEwgKSApOwoJcHV0dCggImVtdGVxIiwgIWVtdGVxKCBJMSwgSTIsIE5VTEwsIE5VTEwgKSApOwoJcHV0dCggIiAgZWx0IiwgICAgZWx0KCBJMSwgSTIsIE5VTEwsIE5VTEwgKSApOwoJcHV0dCggImVsdGVxIiwgIGVsdGVxKCBJMSwgSTIsIE5VTEwsIE5VTEwgKSApOwoJcHV0dCggIiBlaXMwIiwgICFlaXMwKCBJMSwgTlVMTCApICk7CgkvLyovCgllc2hsKCBJMSwgMSApOwoJcHV0aSggIjw8IDE6IiwgaTEsIGkyLCBxMSwgcTIgKTsKCWkyID4+PSA3OwoJZXNociggSTEsIDcgKTsKCXB1dGkoICI+PiA3OiIsIGkxLCBpMiwgcTEsIHEyICk7CglpID0gMTc3Nzc3OwoJaTIgKz0gaTsKCWVhZGQoIEkxLCBJICk7CglwdXRpKCAiKyAxNzc3Nzc6IiwgaTEsIGkyLCBxMSwgcTIgKTsKCWkgPSAzOwoJZm9yKCBpMSA9IDA7IGkxIDwgMzsgKytpMSApIHsgcHV0dCggImVtdGVxIiwgIWVtdGVxKCBJMSwgSSwgTlVMTCwgTlVMTCApICk7IH0KCWZvciggICAgICAgOyBpMSA8IDg7ICsraTEgKSB7IHB1dHQoICJlbXRlcSIsICBlbXRlcSggSTEsIEksIE5VTEwsIE5VTEwgKSApOyB9CglpMSA9IGkyID0gMzsKCWkyIC09IGk7Cgllc3ViKCBJMSwgSSApOwoJcHV0aSggIjMgLSAzOiIsIGkxLCBpMiwgcTEsIHEyICk7CglpID0gNTU7CglpMSA9IGkyID0gNTU7CglpMiAqPSBpOwoJZW11bCggSTEsIEkgKTsKCXB1dGkoICI1NSAqIDU1OiIsIGkxLCBpMiwgcTEsIHEyICk7CglpID0gODg5NjM7CglpMiAqPSBpOwoJZW11bF9rYXJhdHN1YmEoIEkxLCBJICk7CglwdXRpKCAiKiA4ODk2MzoiLCBpMSwgaTIsIHExLCBxMiApOwoJaSA9IDM7CglxMiA9IGkyICUgaTsKCWkyIC89IGk7CgllZGl2KCBRMSwgSTEsIEksIE5VTEwsIDAgKTsKCXB1dGkoICIvIDM6IiwgaTEsIGkyLCBxMSwgcTIgKTsKCWkxID0gcTE7CglxMSA9IDA7CglxMiA9IDA7CglwdXRzKCAiUHJlc3MgYW55IGtleSB0byBjb250aW51ZS4uLiIgKTsKCWZnZXRjKCBzdGRpbiApOwoJcmV0dXJuIDA7Cn0K