#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <immintrin.h>
#include <math.h>
struct md5x8_context {
__m256i k[ 64 ] ;
__m256i iv[ 4 ] ;
__m256i a, b, c, d;
} ;
void md5x8_pre_init( struct md5x8_context* ctx) {
for ( uint32_t i = 0 ; i < 64 ; ++ i) {
uint32_t x
= floor ( fabs ( sin ( i
+ 1 ) ) * ( double ) 0x100000000ull
) ; ctx-> k[ i] = _mm256_set1_epi32( x) ;
}
ctx-> iv[ 0 ] = _mm256_set1_epi32( 0x67452301 ) ;
ctx-> iv[ 1 ] = _mm256_set1_epi32( 0xefcdab89 ) ;
ctx-> iv[ 2 ] = _mm256_set1_epi32( 0x98badcfe ) ;
ctx-> iv[ 3 ] = _mm256_set1_epi32( 0x10325476 ) ;
}
void md5x8_init( struct md5x8_context* ctx) {
ctx-> a = ctx-> iv[ 0 ] ;
ctx-> b = ctx-> iv[ 1 ] ;
ctx-> c = ctx-> iv[ 2 ] ;
ctx-> d = ctx-> iv[ 3 ] ;
}
inline __m256i md5x8_fx( int s, __m256i a, __m256i b, __m256i k, __m256i x, __m256i f) {
f = _mm256_add_epi32( _mm256_add_epi32( f, a) , _mm256_add_epi32( k, x) ) ;
return _mm256_add_epi32( b, _mm256_or_si256( _mm256_slli_epi32( f, s) , _mm256_srli_epi32( f, 32 - s) ) ) ;
}
inline __m256i md5x8_f1( int s, __m256i a, __m256i b, __m256i c, __m256i d, __m256i k, __m256i x) {
return md5x8_fx( s, a, b, k, x, _mm256_or_si256( _mm256_and_si256( b, c) , _mm256_andnot_si256( b, d) ) ) ;
}
inline __m256i md5x8_f2( int s, __m256i a, __m256i b, __m256i c, __m256i d, __m256i k, __m256i x) {
return md5x8_fx( s, a, b, k, x, _mm256_or_si256( _mm256_and_si256( d, b) , _mm256_andnot_si256( d, c) ) ) ;
}
inline __m256i md5x8_f3( int s, __m256i a, __m256i b, __m256i c, __m256i d, __m256i k, __m256i x) {
return md5x8_fx( s, a, b, k, x, _mm256_xor_si256( _mm256_xor_si256( b, c) , d) ) ;
}
inline __m256i md5x8_f4( int s, __m256i a, __m256i b, __m256i c, __m256i d, __m256i k, __m256i x) {
return md5x8_fx( s, a, b, k, x, _mm256_xor_si256( c, _mm256_or_si256( b, _mm256_xor_si256( d, _mm256_set1_epi32( 0xFFFFFFFF ) ) ) ) ) ;
}
void md5x8_raw_update( struct md5x8_context* ctx, const uint8_t blocks[ 8 ] [ 64 ] )
{
__m256i x[ 16 ] = { 0 } ;
for ( size_t i = 0 ; i < 2 ; ++ i) {
__m256i x0 = _mm256_loadu_si256( ( const __m256i* ) blocks[ 0 ] + i) ;
__m256i x1 = _mm256_loadu_si256( ( const __m256i* ) blocks[ 1 ] + i) ;
__m256i x2 = _mm256_loadu_si256( ( const __m256i* ) blocks[ 2 ] + i) ;
__m256i x3 = _mm256_loadu_si256( ( const __m256i* ) blocks[ 3 ] + i) ;
__m256i x4 = _mm256_loadu_si256( ( const __m256i* ) blocks[ 4 ] + i) ;
__m256i x5 = _mm256_loadu_si256( ( const __m256i* ) blocks[ 5 ] + i) ;
__m256i x6 = _mm256_loadu_si256( ( const __m256i* ) blocks[ 6 ] + i) ;
__m256i x7 = _mm256_loadu_si256( ( const __m256i* ) blocks[ 7 ] + i) ;
__m256i t0 = _mm256_unpacklo_epi32( x0, x1) ;
__m256i t1 = _mm256_unpackhi_epi32( x0, x1) ;
__m256i t2 = _mm256_unpacklo_epi32( x2, x3) ;
__m256i t3 = _mm256_unpackhi_epi32( x2, x3) ;
__m256i t4 = _mm256_unpacklo_epi32( x4, x5) ;
__m256i t5 = _mm256_unpackhi_epi32( x4, x5) ;
__m256i t6 = _mm256_unpacklo_epi32( x6, x7) ;
__m256i t7 = _mm256_unpackhi_epi32( x6, x7) ;
__m256i s0 = _mm256_unpacklo_epi64( t0, t2) ;
__m256i s1 = _mm256_unpackhi_epi64( t0, t2) ;
__m256i s2 = _mm256_unpacklo_epi64( t1, t3) ;
__m256i s3 = _mm256_unpackhi_epi64( t1, t3) ;
__m256i s4 = _mm256_unpacklo_epi64( t4, t6) ;
__m256i s5 = _mm256_unpackhi_epi64( t4, t6) ;
__m256i s6 = _mm256_unpacklo_epi64( t5, t7) ;
__m256i s7 = _mm256_unpackhi_epi64( t5, t7) ;
x[ i * 8 + 0 ] = _mm256_permute2x128_si256( s0, s4, 0x20 ) ;
x[ i * 8 + 1 ] = _mm256_permute2x128_si256( s1, s5, 0x20 ) ;
x[ i * 8 + 2 ] = _mm256_permute2x128_si256( s2, s6, 0x20 ) ;
x[ i * 8 + 3 ] = _mm256_permute2x128_si256( s3, s7, 0x20 ) ;
x[ i * 8 + 4 ] = _mm256_permute2x128_si256( s0, s4, 0x31 ) ;
x[ i * 8 + 5 ] = _mm256_permute2x128_si256( s1, s5, 0x31 ) ;
x[ i * 8 + 6 ] = _mm256_permute2x128_si256( s2, s6, 0x31 ) ;
x[ i * 8 + 7 ] = _mm256_permute2x128_si256( s3, s7, 0x31 ) ;
}
__m256i a = ctx-> a;
__m256i b = ctx-> b;
__m256i c = ctx-> c;
__m256i d = ctx-> d;
a = md5x8_f1( 7 , a, b, c, d, ctx-> k[ 0 ] , x[ 0 ] ) ;
d = md5x8_f1( 12 , d, a, b, c, ctx-> k[ 1 ] , x[ 1 ] ) ;
c = md5x8_f1( 17 , c, d, a, b, ctx-> k[ 2 ] , x[ 2 ] ) ;
b = md5x8_f1( 22 , b, c, d, a, ctx-> k[ 3 ] , x[ 3 ] ) ;
a = md5x8_f1( 7 , a, b, c, d, ctx-> k[ 4 ] , x[ 4 ] ) ;
d = md5x8_f1( 12 , d, a, b, c, ctx-> k[ 5 ] , x[ 5 ] ) ;
c = md5x8_f1( 17 , c, d, a, b, ctx-> k[ 6 ] , x[ 6 ] ) ;
b = md5x8_f1( 22 , b, c, d, a, ctx-> k[ 7 ] , x[ 7 ] ) ;
a = md5x8_f1( 7 , a, b, c, d, ctx-> k[ 8 ] , x[ 8 ] ) ;
d = md5x8_f1( 12 , d, a, b, c, ctx-> k[ 9 ] , x[ 9 ] ) ;
c = md5x8_f1( 17 , c, d, a, b, ctx-> k[ 10 ] , x[ 10 ] ) ;
b = md5x8_f1( 22 , b, c, d, a, ctx-> k[ 11 ] , x[ 11 ] ) ;
a = md5x8_f1( 7 , a, b, c, d, ctx-> k[ 12 ] , x[ 12 ] ) ;
d = md5x8_f1( 12 , d, a, b, c, ctx-> k[ 13 ] , x[ 13 ] ) ;
c = md5x8_f1( 17 , c, d, a, b, ctx-> k[ 14 ] , x[ 14 ] ) ;
b = md5x8_f1( 22 , b, c, d, a, ctx-> k[ 15 ] , x[ 15 ] ) ;
a = md5x8_f2( 5 , a, b, c, d, ctx-> k[ 16 ] , x[ 1 ] ) ;
d = md5x8_f2( 9 , d, a, b, c, ctx-> k[ 17 ] , x[ 6 ] ) ;
c = md5x8_f2( 14 , c, d, a, b, ctx-> k[ 18 ] , x[ 11 ] ) ;
b = md5x8_f2( 20 , b, c, d, a, ctx-> k[ 19 ] , x[ 0 ] ) ;
a = md5x8_f2( 5 , a, b, c, d, ctx-> k[ 20 ] , x[ 5 ] ) ;
d = md5x8_f2( 9 , d, a, b, c, ctx-> k[ 21 ] , x[ 10 ] ) ;
c = md5x8_f2( 14 , c, d, a, b, ctx-> k[ 22 ] , x[ 15 ] ) ;
b = md5x8_f2( 20 , b, c, d, a, ctx-> k[ 23 ] , x[ 4 ] ) ;
a = md5x8_f2( 5 , a, b, c, d, ctx-> k[ 24 ] , x[ 9 ] ) ;
d = md5x8_f2( 9 , d, a, b, c, ctx-> k[ 25 ] , x[ 14 ] ) ;
c = md5x8_f2( 14 , c, d, a, b, ctx-> k[ 26 ] , x[ 3 ] ) ;
b = md5x8_f2( 20 , b, c, d, a, ctx-> k[ 27 ] , x[ 8 ] ) ;
a = md5x8_f2( 5 , a, b, c, d, ctx-> k[ 28 ] , x[ 13 ] ) ;
d = md5x8_f2( 9 , d, a, b, c, ctx-> k[ 29 ] , x[ 2 ] ) ;
c = md5x8_f2( 14 , c, d, a, b, ctx-> k[ 30 ] , x[ 7 ] ) ;
b = md5x8_f2( 20 , b, c, d, a, ctx-> k[ 31 ] , x[ 12 ] ) ;
a = md5x8_f3( 4 , a, b, c, d, ctx-> k[ 32 ] , x[ 5 ] ) ;
d = md5x8_f3( 11 , d, a, b, c, ctx-> k[ 33 ] , x[ 8 ] ) ;
c = md5x8_f3( 16 , c, d, a, b, ctx-> k[ 34 ] , x[ 11 ] ) ;
b = md5x8_f3( 23 , b, c, d, a, ctx-> k[ 35 ] , x[ 14 ] ) ;
a = md5x8_f3( 4 , a, b, c, d, ctx-> k[ 36 ] , x[ 1 ] ) ;
d = md5x8_f3( 11 , d, a, b, c, ctx-> k[ 37 ] , x[ 4 ] ) ;
c = md5x8_f3( 16 , c, d, a, b, ctx-> k[ 38 ] , x[ 7 ] ) ;
b = md5x8_f3( 23 , b, c, d, a, ctx-> k[ 39 ] , x[ 10 ] ) ;
a = md5x8_f3( 4 , a, b, c, d, ctx-> k[ 40 ] , x[ 13 ] ) ;
d = md5x8_f3( 11 , d, a, b, c, ctx-> k[ 41 ] , x[ 0 ] ) ;
c = md5x8_f3( 16 , c, d, a, b, ctx-> k[ 42 ] , x[ 3 ] ) ;
b = md5x8_f3( 23 , b, c, d, a, ctx-> k[ 43 ] , x[ 6 ] ) ;
a = md5x8_f3( 4 , a, b, c, d, ctx-> k[ 44 ] , x[ 9 ] ) ;
d = md5x8_f3( 11 , d, a, b, c, ctx-> k[ 45 ] , x[ 12 ] ) ;
c = md5x8_f3( 16 , c, d, a, b, ctx-> k[ 46 ] , x[ 15 ] ) ;
b = md5x8_f3( 23 , b, c, d, a, ctx-> k[ 47 ] , x[ 2 ] ) ;
a = md5x8_f4( 6 , a, b, c, d, ctx-> k[ 48 ] , x[ 0 ] ) ;
d = md5x8_f4( 10 , d, a, b, c, ctx-> k[ 49 ] , x[ 7 ] ) ;
c = md5x8_f4( 15 , c, d, a, b, ctx-> k[ 50 ] , x[ 14 ] ) ;
b = md5x8_f4( 21 , b, c, d, a, ctx-> k[ 51 ] , x[ 5 ] ) ;
a = md5x8_f4( 6 , a, b, c, d, ctx-> k[ 52 ] , x[ 12 ] ) ;
d = md5x8_f4( 10 , d, a, b, c, ctx-> k[ 53 ] , x[ 3 ] ) ;
c = md5x8_f4( 15 , c, d, a, b, ctx-> k[ 54 ] , x[ 10 ] ) ;
b = md5x8_f4( 21 , b, c, d, a, ctx-> k[ 55 ] , x[ 1 ] ) ;
a = md5x8_f4( 6 , a, b, c, d, ctx-> k[ 56 ] , x[ 8 ] ) ;
d = md5x8_f4( 10 , d, a, b, c, ctx-> k[ 57 ] , x[ 15 ] ) ;
c = md5x8_f4( 15 , c, d, a, b, ctx-> k[ 58 ] , x[ 6 ] ) ;
b = md5x8_f4( 21 , b, c, d, a, ctx-> k[ 59 ] , x[ 13 ] ) ;
a = md5x8_f4( 6 , a, b, c, d, ctx-> k[ 60 ] , x[ 4 ] ) ;
d = md5x8_f4( 10 , d, a, b, c, ctx-> k[ 61 ] , x[ 11 ] ) ;
c = md5x8_f4( 15 , c, d, a, b, ctx-> k[ 62 ] , x[ 2 ] ) ;
b = md5x8_f4( 21 , b, c, d, a, ctx-> k[ 63 ] , x[ 9 ] ) ;
ctx-> a = _mm256_add_epi32( ctx-> a, a) ;
ctx-> b = _mm256_add_epi32( ctx-> b, b) ;
ctx-> c = _mm256_add_epi32( ctx-> c, c) ;
ctx-> d = _mm256_add_epi32( ctx-> d, d) ;
}
void md5x8_final( struct md5x8_context* ctx, uint8_t out[ 8 ] [ 32 ] ) {
__m256i x0 = ctx-> a;
__m256i x1 = ctx-> b;
__m256i x2 = ctx-> c;
__m256i x3 = ctx-> d;
__m256i x4 = _mm256_set1_epi32( 0 ) ;
__m256i x5 = _mm256_set1_epi32( 0 ) ;
__m256i x6 = _mm256_set1_epi32( 0 ) ;
__m256i x7 = _mm256_set1_epi32( 0 ) ;
__m256i t0 = _mm256_unpacklo_epi32( x0, x1) ;
__m256i t1 = _mm256_unpackhi_epi32( x0, x1) ;
__m256i t2 = _mm256_unpacklo_epi32( x2, x3) ;
__m256i t3 = _mm256_unpackhi_epi32( x2, x3) ;
__m256i t4 = _mm256_unpacklo_epi32( x4, x5) ;
__m256i t5 = _mm256_unpackhi_epi32( x4, x5) ;
__m256i t6 = _mm256_unpacklo_epi32( x6, x7) ;
__m256i t7 = _mm256_unpackhi_epi32( x6, x7) ;
__m256i s0 = _mm256_unpacklo_epi64( t0, t2) ;
__m256i s1 = _mm256_unpackhi_epi64( t0, t2) ;
__m256i s2 = _mm256_unpacklo_epi64( t1, t3) ;
__m256i s3 = _mm256_unpackhi_epi64( t1, t3) ;
__m256i s4 = _mm256_unpacklo_epi64( t4, t6) ;
__m256i s5 = _mm256_unpackhi_epi64( t4, t6) ;
__m256i s6 = _mm256_unpacklo_epi64( t5, t7) ;
__m256i s7 = _mm256_unpackhi_epi64( t5, t7) ;
_mm256_storeu_si256( ( __m256i* ) ( out + 0 ) , _mm256_permute2x128_si256( s0, s4, 0x20 ) ) ;
_mm256_storeu_si256( ( __m256i* ) ( out + 1 ) , _mm256_permute2x128_si256( s1, s5, 0x20 ) ) ;
_mm256_storeu_si256( ( __m256i* ) ( out + 2 ) , _mm256_permute2x128_si256( s2, s6, 0x20 ) ) ;
_mm256_storeu_si256( ( __m256i* ) ( out + 3 ) , _mm256_permute2x128_si256( s3, s7, 0x20 ) ) ;
_mm256_storeu_si256( ( __m256i* ) ( out + 4 ) , _mm256_permute2x128_si256( s0, s4, 0x31 ) ) ;
_mm256_storeu_si256( ( __m256i* ) ( out + 5 ) , _mm256_permute2x128_si256( s1, s5, 0x31 ) ) ;
_mm256_storeu_si256( ( __m256i* ) ( out + 6 ) , _mm256_permute2x128_si256( s2, s6, 0x31 ) ) ;
_mm256_storeu_si256( ( __m256i* ) ( out + 7 ) , _mm256_permute2x128_si256( s3, s7, 0x31 ) ) ;
}
void unsafe_pad_block( uint8_t block[ 64 ] , size_t length) {
block[ length] = 0x80 ;
* ( uint64_t * ) ( block + 56 ) = length * 8 ;
}
int main( ) {
struct md5x8_context ctx;
md5x8_pre_init( & ctx) ;
uint8_t data[ 8 ] [ 64 ] = {
"We are the others" ,
"We are the cast-outs" ,
"We're the outsiders" ,
"But you can't hide us" ,
} ;
unsafe_pad_block( data[ 0 ] , 17 ) ;
unsafe_pad_block( data[ 1 ] , 20 ) ;
unsafe_pad_block( data[ 2 ] , 19 ) ;
unsafe_pad_block( data[ 3 ] , 21 ) ;
uint8_t digests[ 8 ] [ 32 ] = { 0 } ;
md5x8_init( & ctx) ;
md5x8_raw_update( & ctx, data) ;
md5x8_final( & ctx, digests) ;
for ( size_t i = 0 ; i < 8 ; ++ i) {
for ( size_t j = 0 ; j < 16 ; ++ j)
printf ( "%02X " , digests
[ i
] [ j
] ) ; }
return 0 ;
}
I2luY2x1ZGUgPHN0ZGludC5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8aW1taW50cmluLmg+CiNpbmNsdWRlIDxtYXRoLmg+CgpzdHJ1Y3QgbWQ1eDhfY29udGV4dCB7CiAgICBfX20yNTZpIGtbNjRdOwogICAgX19tMjU2aSBpdls0XTsKCiAgICBfX20yNTZpIGEsIGIsIGMsIGQ7Cn07Cgp2b2lkIG1kNXg4X3ByZV9pbml0KHN0cnVjdCBtZDV4OF9jb250ZXh0KiBjdHgpIHsKICAgIGZvciAodWludDMyX3QgaSA9IDA7IGkgPCA2NDsgKytpKSB7CiAgICAgICAgdWludDMyX3QgeCA9IGZsb29yKGZhYnMoc2luKGkgKyAxKSkgKiAoZG91YmxlKTB4MTAwMDAwMDAwdWxsKTsKICAgICAgICBjdHgtPmtbaV0gPSBfbW0yNTZfc2V0MV9lcGkzMih4KTsKICAgIH0KICAgIGN0eC0+aXZbMF0gPSBfbW0yNTZfc2V0MV9lcGkzMigweDY3NDUyMzAxKTsKICAgIGN0eC0+aXZbMV0gPSBfbW0yNTZfc2V0MV9lcGkzMigweGVmY2RhYjg5KTsKICAgIGN0eC0+aXZbMl0gPSBfbW0yNTZfc2V0MV9lcGkzMigweDk4YmFkY2ZlKTsKICAgIGN0eC0+aXZbM10gPSBfbW0yNTZfc2V0MV9lcGkzMigweDEwMzI1NDc2KTsKfQoKdm9pZCBtZDV4OF9pbml0KHN0cnVjdCBtZDV4OF9jb250ZXh0KiBjdHgpIHsKICAgIGN0eC0+YSA9IGN0eC0+aXZbMF07CiAgICBjdHgtPmIgPSBjdHgtPml2WzFdOwogICAgY3R4LT5jID0gY3R4LT5pdlsyXTsKICAgIGN0eC0+ZCA9IGN0eC0+aXZbM107Cn0KCmlubGluZSBfX20yNTZpIG1kNXg4X2Z4KGludCBzLCBfX20yNTZpIGEsIF9fbTI1NmkgYiwgX19tMjU2aSBrLCBfX20yNTZpIHgsIF9fbTI1NmkgZikgewogICAgZiA9IF9tbTI1Nl9hZGRfZXBpMzIoX21tMjU2X2FkZF9lcGkzMihmLCBhKSwgX21tMjU2X2FkZF9lcGkzMihrLCB4KSk7CiAgICByZXR1cm4gX21tMjU2X2FkZF9lcGkzMihiLCBfbW0yNTZfb3Jfc2kyNTYoX21tMjU2X3NsbGlfZXBpMzIoZiwgcyksIF9tbTI1Nl9zcmxpX2VwaTMyKGYsIDMyIC0gcykpKTsKfQoKaW5saW5lIF9fbTI1NmkgbWQ1eDhfZjEoaW50IHMsIF9fbTI1NmkgYSwgX19tMjU2aSBiLCBfX20yNTZpIGMsIF9fbTI1NmkgZCwgX19tMjU2aSBrLCBfX20yNTZpIHgpIHsKICAgIHJldHVybiBtZDV4OF9meChzLCBhLCBiLCBrLCB4LCBfbW0yNTZfb3Jfc2kyNTYoX21tMjU2X2FuZF9zaTI1NihiLCBjKSwgX21tMjU2X2FuZG5vdF9zaTI1NihiLCBkKSkpOwp9CgppbmxpbmUgX19tMjU2aSBtZDV4OF9mMihpbnQgcywgX19tMjU2aSBhLCBfX20yNTZpIGIsIF9fbTI1NmkgYywgX19tMjU2aSBkLCBfX20yNTZpIGssIF9fbTI1NmkgeCkgewogICAgcmV0dXJuIG1kNXg4X2Z4KHMsIGEsIGIsIGssIHgsIF9tbTI1Nl9vcl9zaTI1NihfbW0yNTZfYW5kX3NpMjU2KGQsIGIpLCBfbW0yNTZfYW5kbm90X3NpMjU2KGQsIGMpKSk7Cn0KCmlubGluZSBfX20yNTZpIG1kNXg4X2YzKGludCBzLCBfX20yNTZpIGEsIF9fbTI1NmkgYiwgX19tMjU2aSBjLCBfX20yNTZpIGQsIF9fbTI1NmkgaywgX19tMjU2aSB4KSB7CiAgICByZXR1cm4gbWQ1eDhfZngocywgYSwgYiwgaywgeCwgX21tMjU2X3hvcl9zaTI1NihfbW0yNTZfeG9yX3NpMjU2KGIsIGMpLCBkKSk7Cn0KCmlubGluZSBfX20yNTZpIG1kNXg4X2Y0KGludCBzLCBfX20yNTZpIGEsIF9fbTI1NmkgYiwgX19tMjU2aSBjLCBfX20yNTZpIGQsIF9fbTI1NmkgaywgX19tMjU2aSB4KSB7CiAgICByZXR1cm4gbWQ1eDhfZngocywgYSwgYiwgaywgeCwgX21tMjU2X3hvcl9zaTI1NihjLCBfbW0yNTZfb3Jfc2kyNTYoYiwgX21tMjU2X3hvcl9zaTI1NihkLCBfbW0yNTZfc2V0MV9lcGkzMigweEZGRkZGRkZGKSkpKSk7Cn0KCnZvaWQgbWQ1eDhfcmF3X3VwZGF0ZShzdHJ1Y3QgbWQ1eDhfY29udGV4dCogY3R4LCBjb25zdCB1aW50OF90IGJsb2Nrc1s4XVs2NF0pCnsKICAgIF9fbTI1NmkgeFsxNl0gPSB7MH07CiAgICBmb3IgKHNpemVfdCBpID0gMDsgaSA8IDI7ICsraSkgewogICAgICAgIF9fbTI1NmkgeDAgPSBfbW0yNTZfbG9hZHVfc2kyNTYoKGNvbnN0IF9fbTI1NmkqKWJsb2Nrc1swXSArIGkpOwogICAgICAgIF9fbTI1NmkgeDEgPSBfbW0yNTZfbG9hZHVfc2kyNTYoKGNvbnN0IF9fbTI1NmkqKWJsb2Nrc1sxXSArIGkpOwogICAgICAgIF9fbTI1NmkgeDIgPSBfbW0yNTZfbG9hZHVfc2kyNTYoKGNvbnN0IF9fbTI1NmkqKWJsb2Nrc1syXSArIGkpOwogICAgICAgIF9fbTI1NmkgeDMgPSBfbW0yNTZfbG9hZHVfc2kyNTYoKGNvbnN0IF9fbTI1NmkqKWJsb2Nrc1szXSArIGkpOwogICAgICAgIF9fbTI1NmkgeDQgPSBfbW0yNTZfbG9hZHVfc2kyNTYoKGNvbnN0IF9fbTI1NmkqKWJsb2Nrc1s0XSArIGkpOwogICAgICAgIF9fbTI1NmkgeDUgPSBfbW0yNTZfbG9hZHVfc2kyNTYoKGNvbnN0IF9fbTI1NmkqKWJsb2Nrc1s1XSArIGkpOwogICAgICAgIF9fbTI1NmkgeDYgPSBfbW0yNTZfbG9hZHVfc2kyNTYoKGNvbnN0IF9fbTI1NmkqKWJsb2Nrc1s2XSArIGkpOwogICAgICAgIF9fbTI1NmkgeDcgPSBfbW0yNTZfbG9hZHVfc2kyNTYoKGNvbnN0IF9fbTI1NmkqKWJsb2Nrc1s3XSArIGkpOwoKICAgICAgICBfX20yNTZpIHQwID0gX21tMjU2X3VucGFja2xvX2VwaTMyKHgwLCB4MSk7CiAgICAgICAgX19tMjU2aSB0MSA9IF9tbTI1Nl91bnBhY2toaV9lcGkzMih4MCwgeDEpOwogICAgICAgIF9fbTI1NmkgdDIgPSBfbW0yNTZfdW5wYWNrbG9fZXBpMzIoeDIsIHgzKTsKICAgICAgICBfX20yNTZpIHQzID0gX21tMjU2X3VucGFja2hpX2VwaTMyKHgyLCB4Myk7CiAgICAgICAgX19tMjU2aSB0NCA9IF9tbTI1Nl91bnBhY2tsb19lcGkzMih4NCwgeDUpOwogICAgICAgIF9fbTI1NmkgdDUgPSBfbW0yNTZfdW5wYWNraGlfZXBpMzIoeDQsIHg1KTsKICAgICAgICBfX20yNTZpIHQ2ID0gX21tMjU2X3VucGFja2xvX2VwaTMyKHg2LCB4Nyk7CiAgICAgICAgX19tMjU2aSB0NyA9IF9tbTI1Nl91bnBhY2toaV9lcGkzMih4NiwgeDcpOwoKICAgICAgICBfX20yNTZpIHMwID0gX21tMjU2X3VucGFja2xvX2VwaTY0KHQwLCB0Mik7CiAgICAgICAgX19tMjU2aSBzMSA9IF9tbTI1Nl91bnBhY2toaV9lcGk2NCh0MCwgdDIpOwogICAgICAgIF9fbTI1NmkgczIgPSBfbW0yNTZfdW5wYWNrbG9fZXBpNjQodDEsIHQzKTsKICAgICAgICBfX20yNTZpIHMzID0gX21tMjU2X3VucGFja2hpX2VwaTY0KHQxLCB0Myk7CiAgICAgICAgX19tMjU2aSBzNCA9IF9tbTI1Nl91bnBhY2tsb19lcGk2NCh0NCwgdDYpOwogICAgICAgIF9fbTI1NmkgczUgPSBfbW0yNTZfdW5wYWNraGlfZXBpNjQodDQsIHQ2KTsKICAgICAgICBfX20yNTZpIHM2ID0gX21tMjU2X3VucGFja2xvX2VwaTY0KHQ1LCB0Nyk7CiAgICAgICAgX19tMjU2aSBzNyA9IF9tbTI1Nl91bnBhY2toaV9lcGk2NCh0NSwgdDcpOwoKICAgICAgICB4W2kgKiA4ICsgMF0gPSBfbW0yNTZfcGVybXV0ZTJ4MTI4X3NpMjU2KHMwLCBzNCwgMHgyMCk7CiAgICAgICAgeFtpICogOCArIDFdID0gX21tMjU2X3Blcm11dGUyeDEyOF9zaTI1NihzMSwgczUsIDB4MjApOwogICAgICAgIHhbaSAqIDggKyAyXSA9IF9tbTI1Nl9wZXJtdXRlMngxMjhfc2kyNTYoczIsIHM2LCAweDIwKTsKICAgICAgICB4W2kgKiA4ICsgM10gPSBfbW0yNTZfcGVybXV0ZTJ4MTI4X3NpMjU2KHMzLCBzNywgMHgyMCk7CiAgICAgICAgeFtpICogOCArIDRdID0gX21tMjU2X3Blcm11dGUyeDEyOF9zaTI1NihzMCwgczQsIDB4MzEpOwogICAgICAgIHhbaSAqIDggKyA1XSA9IF9tbTI1Nl9wZXJtdXRlMngxMjhfc2kyNTYoczEsIHM1LCAweDMxKTsKICAgICAgICB4W2kgKiA4ICsgNl0gPSBfbW0yNTZfcGVybXV0ZTJ4MTI4X3NpMjU2KHMyLCBzNiwgMHgzMSk7CiAgICAgICAgeFtpICogOCArIDddID0gX21tMjU2X3Blcm11dGUyeDEyOF9zaTI1NihzMywgczcsIDB4MzEpOwogICAgfQoKICAgIF9fbTI1NmkgYSA9IGN0eC0+YTsKICAgIF9fbTI1NmkgYiA9IGN0eC0+YjsKICAgIF9fbTI1NmkgYyA9IGN0eC0+YzsKICAgIF9fbTI1NmkgZCA9IGN0eC0+ZDsKCiAgICBhID0gbWQ1eDhfZjEoNywgYSwgYiwgYywgZCwgY3R4LT5rWzBdLCB4WzBdKTsKICAgIGQgPSBtZDV4OF9mMSgxMiwgZCwgYSwgYiwgYywgY3R4LT5rWzFdLCB4WzFdKTsKICAgIGMgPSBtZDV4OF9mMSgxNywgYywgZCwgYSwgYiwgY3R4LT5rWzJdLCB4WzJdKTsKICAgIGIgPSBtZDV4OF9mMSgyMiwgYiwgYywgZCwgYSwgY3R4LT5rWzNdLCB4WzNdKTsKICAgIGEgPSBtZDV4OF9mMSg3LCBhLCBiLCBjLCBkLCBjdHgtPmtbNF0sIHhbNF0pOwogICAgZCA9IG1kNXg4X2YxKDEyLCBkLCBhLCBiLCBjLCBjdHgtPmtbNV0sIHhbNV0pOwogICAgYyA9IG1kNXg4X2YxKDE3LCBjLCBkLCBhLCBiLCBjdHgtPmtbNl0sIHhbNl0pOwogICAgYiA9IG1kNXg4X2YxKDIyLCBiLCBjLCBkLCBhLCBjdHgtPmtbN10sIHhbN10pOwogICAgYSA9IG1kNXg4X2YxKDcsIGEsIGIsIGMsIGQsIGN0eC0+a1s4XSwgeFs4XSk7CiAgICBkID0gbWQ1eDhfZjEoMTIsIGQsIGEsIGIsIGMsIGN0eC0+a1s5XSwgeFs5XSk7CiAgICBjID0gbWQ1eDhfZjEoMTcsIGMsIGQsIGEsIGIsIGN0eC0+a1sxMF0sIHhbMTBdKTsKICAgIGIgPSBtZDV4OF9mMSgyMiwgYiwgYywgZCwgYSwgY3R4LT5rWzExXSwgeFsxMV0pOwogICAgYSA9IG1kNXg4X2YxKDcsIGEsIGIsIGMsIGQsIGN0eC0+a1sxMl0sIHhbMTJdKTsKICAgIGQgPSBtZDV4OF9mMSgxMiwgZCwgYSwgYiwgYywgY3R4LT5rWzEzXSwgeFsxM10pOwogICAgYyA9IG1kNXg4X2YxKDE3LCBjLCBkLCBhLCBiLCBjdHgtPmtbMTRdLCB4WzE0XSk7CiAgICBiID0gbWQ1eDhfZjEoMjIsIGIsIGMsIGQsIGEsIGN0eC0+a1sxNV0sIHhbMTVdKTsKCiAgICBhID0gbWQ1eDhfZjIoNSwgYSwgYiwgYywgZCwgY3R4LT5rWzE2XSwgeFsxXSk7CiAgICBkID0gbWQ1eDhfZjIoOSwgZCwgYSwgYiwgYywgY3R4LT5rWzE3XSwgeFs2XSk7CiAgICBjID0gbWQ1eDhfZjIoMTQsIGMsIGQsIGEsIGIsIGN0eC0+a1sxOF0sIHhbMTFdKTsKICAgIGIgPSBtZDV4OF9mMigyMCwgYiwgYywgZCwgYSwgY3R4LT5rWzE5XSwgeFswXSk7CiAgICBhID0gbWQ1eDhfZjIoNSwgYSwgYiwgYywgZCwgY3R4LT5rWzIwXSwgeFs1XSk7CiAgICBkID0gbWQ1eDhfZjIoOSwgZCwgYSwgYiwgYywgY3R4LT5rWzIxXSwgeFsxMF0pOwogICAgYyA9IG1kNXg4X2YyKDE0LCBjLCBkLCBhLCBiLCBjdHgtPmtbMjJdLCB4WzE1XSk7CiAgICBiID0gbWQ1eDhfZjIoMjAsIGIsIGMsIGQsIGEsIGN0eC0+a1syM10sIHhbNF0pOwogICAgYSA9IG1kNXg4X2YyKDUsIGEsIGIsIGMsIGQsIGN0eC0+a1syNF0sIHhbOV0pOwogICAgZCA9IG1kNXg4X2YyKDksIGQsIGEsIGIsIGMsIGN0eC0+a1syNV0sIHhbMTRdKTsKICAgIGMgPSBtZDV4OF9mMigxNCwgYywgZCwgYSwgYiwgY3R4LT5rWzI2XSwgeFszXSk7CiAgICBiID0gbWQ1eDhfZjIoMjAsIGIsIGMsIGQsIGEsIGN0eC0+a1syN10sIHhbOF0pOwogICAgYSA9IG1kNXg4X2YyKDUsIGEsIGIsIGMsIGQsIGN0eC0+a1syOF0sIHhbMTNdKTsKICAgIGQgPSBtZDV4OF9mMig5LCBkLCBhLCBiLCBjLCBjdHgtPmtbMjldLCB4WzJdKTsKICAgIGMgPSBtZDV4OF9mMigxNCwgYywgZCwgYSwgYiwgY3R4LT5rWzMwXSwgeFs3XSk7CiAgICBiID0gbWQ1eDhfZjIoMjAsIGIsIGMsIGQsIGEsIGN0eC0+a1szMV0sIHhbMTJdKTsKCiAgICBhID0gbWQ1eDhfZjMoNCwgYSwgYiwgYywgZCwgY3R4LT5rWzMyXSwgeFs1XSk7CiAgICBkID0gbWQ1eDhfZjMoMTEsIGQsIGEsIGIsIGMsIGN0eC0+a1szM10sIHhbOF0pOwogICAgYyA9IG1kNXg4X2YzKDE2LCBjLCBkLCBhLCBiLCBjdHgtPmtbMzRdLCB4WzExXSk7CiAgICBiID0gbWQ1eDhfZjMoMjMsIGIsIGMsIGQsIGEsIGN0eC0+a1szNV0sIHhbMTRdKTsKICAgIGEgPSBtZDV4OF9mMyg0LCBhLCBiLCBjLCBkLCBjdHgtPmtbMzZdLCB4WzFdKTsKICAgIGQgPSBtZDV4OF9mMygxMSwgZCwgYSwgYiwgYywgY3R4LT5rWzM3XSwgeFs0XSk7CiAgICBjID0gbWQ1eDhfZjMoMTYsIGMsIGQsIGEsIGIsIGN0eC0+a1szOF0sIHhbN10pOwogICAgYiA9IG1kNXg4X2YzKDIzLCBiLCBjLCBkLCBhLCBjdHgtPmtbMzldLCB4WzEwXSk7CiAgICBhID0gbWQ1eDhfZjMoNCwgYSwgYiwgYywgZCwgY3R4LT5rWzQwXSwgeFsxM10pOwogICAgZCA9IG1kNXg4X2YzKDExLCBkLCBhLCBiLCBjLCBjdHgtPmtbNDFdLCB4WzBdKTsKICAgIGMgPSBtZDV4OF9mMygxNiwgYywgZCwgYSwgYiwgY3R4LT5rWzQyXSwgeFszXSk7CiAgICBiID0gbWQ1eDhfZjMoMjMsIGIsIGMsIGQsIGEsIGN0eC0+a1s0M10sIHhbNl0pOwogICAgYSA9IG1kNXg4X2YzKDQsIGEsIGIsIGMsIGQsIGN0eC0+a1s0NF0sIHhbOV0pOwogICAgZCA9IG1kNXg4X2YzKDExLCBkLCBhLCBiLCBjLCBjdHgtPmtbNDVdLCB4WzEyXSk7CiAgICBjID0gbWQ1eDhfZjMoMTYsIGMsIGQsIGEsIGIsIGN0eC0+a1s0Nl0sIHhbMTVdKTsKICAgIGIgPSBtZDV4OF9mMygyMywgYiwgYywgZCwgYSwgY3R4LT5rWzQ3XSwgeFsyXSk7CgogICAgYSA9IG1kNXg4X2Y0KDYsIGEsIGIsIGMsIGQsIGN0eC0+a1s0OF0sIHhbMF0pOwogICAgZCA9IG1kNXg4X2Y0KDEwLCBkLCBhLCBiLCBjLCBjdHgtPmtbNDldLCB4WzddKTsKICAgIGMgPSBtZDV4OF9mNCgxNSwgYywgZCwgYSwgYiwgY3R4LT5rWzUwXSwgeFsxNF0pOwogICAgYiA9IG1kNXg4X2Y0KDIxLCBiLCBjLCBkLCBhLCBjdHgtPmtbNTFdLCB4WzVdKTsKICAgIGEgPSBtZDV4OF9mNCg2LCBhLCBiLCBjLCBkLCBjdHgtPmtbNTJdLCB4WzEyXSk7CiAgICBkID0gbWQ1eDhfZjQoMTAsIGQsIGEsIGIsIGMsIGN0eC0+a1s1M10sIHhbM10pOwogICAgYyA9IG1kNXg4X2Y0KDE1LCBjLCBkLCBhLCBiLCBjdHgtPmtbNTRdLCB4WzEwXSk7CiAgICBiID0gbWQ1eDhfZjQoMjEsIGIsIGMsIGQsIGEsIGN0eC0+a1s1NV0sIHhbMV0pOwogICAgYSA9IG1kNXg4X2Y0KDYsIGEsIGIsIGMsIGQsIGN0eC0+a1s1Nl0sIHhbOF0pOwogICAgZCA9IG1kNXg4X2Y0KDEwLCBkLCBhLCBiLCBjLCBjdHgtPmtbNTddLCB4WzE1XSk7CiAgICBjID0gbWQ1eDhfZjQoMTUsIGMsIGQsIGEsIGIsIGN0eC0+a1s1OF0sIHhbNl0pOwogICAgYiA9IG1kNXg4X2Y0KDIxLCBiLCBjLCBkLCBhLCBjdHgtPmtbNTldLCB4WzEzXSk7CiAgICBhID0gbWQ1eDhfZjQoNiwgYSwgYiwgYywgZCwgY3R4LT5rWzYwXSwgeFs0XSk7CiAgICBkID0gbWQ1eDhfZjQoMTAsIGQsIGEsIGIsIGMsIGN0eC0+a1s2MV0sIHhbMTFdKTsKICAgIGMgPSBtZDV4OF9mNCgxNSwgYywgZCwgYSwgYiwgY3R4LT5rWzYyXSwgeFsyXSk7CiAgICBiID0gbWQ1eDhfZjQoMjEsIGIsIGMsIGQsIGEsIGN0eC0+a1s2M10sIHhbOV0pOwoKICAgIGN0eC0+YSA9IF9tbTI1Nl9hZGRfZXBpMzIoY3R4LT5hLCBhKTsKICAgIGN0eC0+YiA9IF9tbTI1Nl9hZGRfZXBpMzIoY3R4LT5iLCBiKTsKICAgIGN0eC0+YyA9IF9tbTI1Nl9hZGRfZXBpMzIoY3R4LT5jLCBjKTsKICAgIGN0eC0+ZCA9IF9tbTI1Nl9hZGRfZXBpMzIoY3R4LT5kLCBkKTsKfQoKdm9pZCBtZDV4OF9maW5hbChzdHJ1Y3QgbWQ1eDhfY29udGV4dCogY3R4LCB1aW50OF90IG91dFs4XVszMl0pIHsKICAgIF9fbTI1NmkgeDAgPSBjdHgtPmE7CiAgICBfX20yNTZpIHgxID0gY3R4LT5iOwogICAgX19tMjU2aSB4MiA9IGN0eC0+YzsKICAgIF9fbTI1NmkgeDMgPSBjdHgtPmQ7CiAgICBfX20yNTZpIHg0ID0gX21tMjU2X3NldDFfZXBpMzIoMCk7CiAgICBfX20yNTZpIHg1ID0gX21tMjU2X3NldDFfZXBpMzIoMCk7CiAgICBfX20yNTZpIHg2ID0gX21tMjU2X3NldDFfZXBpMzIoMCk7CiAgICBfX20yNTZpIHg3ID0gX21tMjU2X3NldDFfZXBpMzIoMCk7CgogICAgX19tMjU2aSB0MCA9IF9tbTI1Nl91bnBhY2tsb19lcGkzMih4MCwgeDEpOwogICAgX19tMjU2aSB0MSA9IF9tbTI1Nl91bnBhY2toaV9lcGkzMih4MCwgeDEpOwogICAgX19tMjU2aSB0MiA9IF9tbTI1Nl91bnBhY2tsb19lcGkzMih4MiwgeDMpOwogICAgX19tMjU2aSB0MyA9IF9tbTI1Nl91bnBhY2toaV9lcGkzMih4MiwgeDMpOwogICAgX19tMjU2aSB0NCA9IF9tbTI1Nl91bnBhY2tsb19lcGkzMih4NCwgeDUpOwogICAgX19tMjU2aSB0NSA9IF9tbTI1Nl91bnBhY2toaV9lcGkzMih4NCwgeDUpOwogICAgX19tMjU2aSB0NiA9IF9tbTI1Nl91bnBhY2tsb19lcGkzMih4NiwgeDcpOwogICAgX19tMjU2aSB0NyA9IF9tbTI1Nl91bnBhY2toaV9lcGkzMih4NiwgeDcpOwoKICAgIF9fbTI1NmkgczAgPSBfbW0yNTZfdW5wYWNrbG9fZXBpNjQodDAsIHQyKTsKICAgIF9fbTI1NmkgczEgPSBfbW0yNTZfdW5wYWNraGlfZXBpNjQodDAsIHQyKTsKICAgIF9fbTI1NmkgczIgPSBfbW0yNTZfdW5wYWNrbG9fZXBpNjQodDEsIHQzKTsKICAgIF9fbTI1NmkgczMgPSBfbW0yNTZfdW5wYWNraGlfZXBpNjQodDEsIHQzKTsKICAgIF9fbTI1NmkgczQgPSBfbW0yNTZfdW5wYWNrbG9fZXBpNjQodDQsIHQ2KTsKICAgIF9fbTI1NmkgczUgPSBfbW0yNTZfdW5wYWNraGlfZXBpNjQodDQsIHQ2KTsKICAgIF9fbTI1NmkgczYgPSBfbW0yNTZfdW5wYWNrbG9fZXBpNjQodDUsIHQ3KTsKICAgIF9fbTI1NmkgczcgPSBfbW0yNTZfdW5wYWNraGlfZXBpNjQodDUsIHQ3KTsKCiAgICBfbW0yNTZfc3RvcmV1X3NpMjU2KChfX20yNTZpKikob3V0ICsgMCksIF9tbTI1Nl9wZXJtdXRlMngxMjhfc2kyNTYoczAsIHM0LCAweDIwKSk7CiAgICBfbW0yNTZfc3RvcmV1X3NpMjU2KChfX20yNTZpKikob3V0ICsgMSksIF9tbTI1Nl9wZXJtdXRlMngxMjhfc2kyNTYoczEsIHM1LCAweDIwKSk7CiAgICBfbW0yNTZfc3RvcmV1X3NpMjU2KChfX20yNTZpKikob3V0ICsgMiksIF9tbTI1Nl9wZXJtdXRlMngxMjhfc2kyNTYoczIsIHM2LCAweDIwKSk7CiAgICBfbW0yNTZfc3RvcmV1X3NpMjU2KChfX20yNTZpKikob3V0ICsgMyksIF9tbTI1Nl9wZXJtdXRlMngxMjhfc2kyNTYoczMsIHM3LCAweDIwKSk7CiAgICBfbW0yNTZfc3RvcmV1X3NpMjU2KChfX20yNTZpKikob3V0ICsgNCksIF9tbTI1Nl9wZXJtdXRlMngxMjhfc2kyNTYoczAsIHM0LCAweDMxKSk7CiAgICBfbW0yNTZfc3RvcmV1X3NpMjU2KChfX20yNTZpKikob3V0ICsgNSksIF9tbTI1Nl9wZXJtdXRlMngxMjhfc2kyNTYoczEsIHM1LCAweDMxKSk7CiAgICBfbW0yNTZfc3RvcmV1X3NpMjU2KChfX20yNTZpKikob3V0ICsgNiksIF9tbTI1Nl9wZXJtdXRlMngxMjhfc2kyNTYoczIsIHM2LCAweDMxKSk7CiAgICBfbW0yNTZfc3RvcmV1X3NpMjU2KChfX20yNTZpKikob3V0ICsgNyksIF9tbTI1Nl9wZXJtdXRlMngxMjhfc2kyNTYoczMsIHM3LCAweDMxKSk7Cn0KCgp2b2lkIHVuc2FmZV9wYWRfYmxvY2sodWludDhfdCBibG9ja1s2NF0sIHNpemVfdCBsZW5ndGgpIHsKICAgIGJsb2NrW2xlbmd0aF0gPSAweDgwOwogICAgKih1aW50NjRfdCopKGJsb2NrICsgNTYpID0gbGVuZ3RoICogODsKfQoKaW50IG1haW4oKSB7CiAgICBzdHJ1Y3QgbWQ1eDhfY29udGV4dCBjdHg7CiAgICBtZDV4OF9wcmVfaW5pdCgmY3R4KTsKCiAgICB1aW50OF90IGRhdGFbOF1bNjRdID0gewogICAgICAgICJXZSBhcmUgdGhlIG90aGVycyIsCiAgICAgICAgIldlIGFyZSB0aGUgY2FzdC1vdXRzIiwKICAgICAgICAiV2UncmUgdGhlIG91dHNpZGVycyIsCiAgICAgICAgIkJ1dCB5b3UgY2FuJ3QgaGlkZSB1cyIsCiAgICB9OwoKICAgIHVuc2FmZV9wYWRfYmxvY2soZGF0YVswXSwgMTcpOwogICAgdW5zYWZlX3BhZF9ibG9jayhkYXRhWzFdLCAyMCk7CiAgICB1bnNhZmVfcGFkX2Jsb2NrKGRhdGFbMl0sIDE5KTsKICAgIHVuc2FmZV9wYWRfYmxvY2soZGF0YVszXSwgMjEpOwoKICAgIHVpbnQ4X3QgZGlnZXN0c1s4XVszMl0gPSB7MH07CgogICAgbWQ1eDhfaW5pdCgmY3R4KTsKICAgIG1kNXg4X3Jhd191cGRhdGUoJmN0eCwgZGF0YSk7CiAgICBtZDV4OF9maW5hbCgmY3R4LCBkaWdlc3RzKTsKCiAgICBmb3IgKHNpemVfdCBpID0gMDsgaSA8IDg7ICsraSkgewogICAgICAgIGZvciAoc2l6ZV90IGogPSAwOyBqIDwgMTY7ICsraikKICAgICAgICAgICAgcHJpbnRmKCIlMDJYICIsIGRpZ2VzdHNbaV1bal0pOwogICAgICAgIHByaW50ZigiXG4iKTsKICAgIH0KCiAgICByZXR1cm4gMDsKfQ==