/* prime.c -- programming with prime numbers
* compile as: gcc -O3 prime.c -lgmp -o prime
* run as: ./prime */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#include <gmp.h>
/* bit arrays */
#define ISBITSET(x, i) ((x[i>>3] & (1<<(i&7))) != 0)
#define SETBIT (x, i) x[i>>3] |= (1<<(i&7)) ;
#define CLEARBIT(x, i) x[i>>3] &= (1<<(i&7)) ^ 0xFF;
/* basic list library */
typedef struct list {
void *data;
struct list *next;
} List;
List *insert(void *data, List *next)
{
List *new;
new->data = data;
new->next = next;
return new;
}
List *reverse(List *list) {
List *new = NULL;
List *next;
while (list != NULL)
{
next = list->next;
list->next = new;
new = list;
list = next;
}
return new;
}
int length(List *xs)
{
int len = 0;
while (xs != NULL)
{
len += 1;
xs = xs->next;
}
return len;
}
/* sieve of eratosthenes */
List *primes(long n)
{
int m = (n-1) / 2;
unsigned char b[(m+7)/8];
int i = 0;
int p = 3;
List *ps = NULL;
int j;
ps = insert((void *) 2, ps);
while (p*p <= n)
{
if (ISBITSET(b,i))
{
ps = insert((void *) p, ps);
j = (p*p - 3) / 2;
while (j < m)
{
CLEARBIT(b, j);
j += p;
}
}
i += 1; p += 2;
}
while (i < m)
{
if (ISBITSET(b,i))
{
ps = insert((void *) p, ps);
}
i += 1; p += 2;
}
return reverse(ps);
}
/* test primality by trial division */
int td_prime(unsigned long long int n)
{
if (n % 2 == 0)
{
return n == 2;
}
unsigned long long int d = 3;
while (d*d <= n)
{
if (n % d == 0)
{
return 0;
}
d += 2;
}
return 1;
}
/* factorization by trial division */
List *td_factors(unsigned long long int n)
{
List *fs = NULL;
while (n % 2 == 0)
{
fs = insert((void *) 2, fs);
n /= 2;
}
if (n == 1)
{
return reverse(fs);
}
unsigned long long int f = 3;
while (f*f <= n)
{
if (n % f == 0)
{
fs = insert((void *) f, fs);
n /= f;
}
else
{
f += 2;
}
}
fs = insert((void *) n, fs);
return reverse(fs);
}
/* miller-rabin primality checker */
int is_spsp(mpz_t n, mpz_t a)
{
mpz_t d, n1, t;
mpz_inits(d, n1, t, NULL);
mpz_sub_ui(n1, n, 1);
mpz_set(d, n1);
int s = 0;
while (mpz_even_p(d))
{
mpz_divexact_ui(d, d, 2);
s += 1;
}
mpz_powm(t, a, d, n);
if (mpz_cmp_ui(t, 1) == 0 || mpz_cmp(t, n1) == 0)
{
mpz_clears(d, n1, t, NULL);
return 1;
}
while (--s > 0)
{
mpz_mul(t, t, t);
mpz_mod(t, t, n);
if (mpz_cmp(t, n1) == 0)
{
mpz_clears(d, n1, t, NULL);
return 1;
}
}
mpz_clears(d, n1, t, NULL);
return 0;
}
int is_prime(mpz_t n)
{
static gmp_randstate_t gmpRandState;
static int is_seeded = 0;
if (! is_seeded)
{
gmp_randinit_default(gmpRandState);
gmp_randseed_ui
(gmpRandState
, time(NULL
)); is_seeded = 1;
}
mpz_t a, n3, t;
mpz_inits(a, n3, t, NULL);
mpz_sub_ui(n3, n, 3);
int i;
int k = 25;
long unsigned ps[] = { 2, 3, 5, 7 };
if (mpz_cmp_ui(n, 2) < 0)
{
mpz_clears(a, n3, t, NULL);
return 0;
}
for (i = 0; i < sizeof(ps) / sizeof(long unsigned); i++)
{
mpz_mod_ui(t, n, ps[i]);
if (mpz_cmp_ui(t, 0) == 0)
{
mpz_clears(a, n3, t, NULL);
return mpz_cmp_ui(n, ps[i]) == 0;
}
}
while (k > 0)
{
mpz_urandomm(a, gmpRandState, n3);
mpz_add_ui(a, a, 2);
if (! is_spsp(n, a))
{
mpz_clears(a, n3, t, NULL);
return 0;
}
k -= 1;
}
mpz_clears(a, n3, t, NULL);
return 1;
}
/* integer factorization by pollard rho */
List *insert_in_order(void *x, List *xs)
{
if (xs == NULL || mpz_cmp(x, xs->data) < 0)
{
return insert(x, xs);
}
else
{
List *head = xs;
while (xs->next != NULL && mpz_cmp(x, xs->next->data) > 0)
{
xs = xs->next;
}
xs->next = insert(x, xs->next);
return head;
}
}
void rho_factor(mpz_t f, mpz_t n, long unsigned c)
{
mpz_t t, h, d, r;
mpz_init_set_ui(t, 2);
mpz_init_set_ui(h, 2);
mpz_init_set_ui(d, 1);
mpz_init(r);
while (mpz_cmp_si(d, 1) == 0)
{
mpz_mul(t, t, t);
mpz_add_ui(t, t, c);
mpz_mod(t, t, n);
mpz_mul(h, h, h);
mpz_add_ui(h, h, c);
mpz_mod(h, h, n);
mpz_mul(h, h, h);
mpz_add_ui(h, h, c);
mpz_mod(h, h, n);
mpz_sub(r, t, h);
mpz_gcd(d, r, n);
}
if (mpz_cmp(d, n) == 0) /* cycle */
{
rho_factor(f, n, c+1);
}
else if (mpz_probab_prime_p(d, 25)) /* success */
{
mpz_set(f, d);
}
else /* found composite factor */
{
rho_factor(f, d, c+1);
}
mpz_clears(t, h, d, r, NULL);
}
void rho_factors(List **fs, mpz_t n)
{
while (mpz_even_p(n))
{
mpz_t
*f
= malloc(sizeof(*f
)); mpz_init_set_ui(*f, 2);
*fs = insert(*f, *fs);
mpz_divexact_ui(n, n, 2);
}
if (mpz_cmp_ui(n, 1) == 0) return;
while (! (mpz_probab_prime_p(n, 25)))
{
mpz_t
*f
= malloc(sizeof(*f
)); mpz_init_set_ui(*f, 0);
rho_factor(*f, n, 1);
*fs = insert_in_order(*f, *fs);
mpz_divexact(n, n, *f);
}
*fs = insert_in_order(n, *fs);
}
/* demonstration */
int main(int argc, char *argv[])
{
mpz_t n;
mpz_init(n);
List *ps = NULL;
List *fs = NULL;
ps = primes(100); /* 2 3 5 7 11 13 17 19 23 29 31 37 41 */
while (ps != NULL) /* 43 47 53 59 61 67 71 73 79 83 89 97 */
{
printf("%ld%s", (long) ps
->data
, (ps->next == NULL) ? "\n" : " ");
ps = ps->next;
}
printf("%d\n", length
(primes
(1000000))); /* 78498 */
printf("%d\n", td_prime
(600851475143LL
)); /* composite */
fs = td_factors(600851475143LL); /* 71 839 1471 6857 */
while (fs != NULL)
{
printf("%llu%s", (unsigned long long int) fs
->data
, (fs->next == NULL) ? "\n" : " ");
fs = fs->next;
}
mpz_t a;
mpz_init(a);
mpz_set_str(n, "2047", 10);
mpz_set_str(a, "2", 10);
printf("%d\n", is_spsp
(n
, a
)); /* pseudo-prime */
mpz_set_str(n, "600851475143", 10); /* composite */
mpz_set_str(n, "2305843009213693951", 10); /* prime */
mpz_set_str(n, "600851475143", 10);
rho_factors(&fs, n); /* 71 839 1471 6857 */
while (fs != NULL) {
printf("%s%s", mpz_get_str
(NULL
, 10, fs
->data
), (fs->next == NULL) ? "\n" : " ");
fs = fs->next;
}
}
LyogcHJpbWUuYyAtLSBwcm9ncmFtbWluZyB3aXRoIHByaW1lIG51bWJlcnMKICogY29tcGlsZSBhczogZ2NjIC1PMyBwcmltZS5jIC1sZ21wIC1vIHByaW1lCiAqIHJ1biBhczogLi9wcmltZSAqLwoKI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0ZGludC5oPgojaW5jbHVkZSA8c3RyaW5nLmg+CiNpbmNsdWRlIDx0aW1lLmg+CiNpbmNsdWRlIDxnbXAuaD4KCi8qIGJpdCBhcnJheXMgKi8KCiNkZWZpbmUgSVNCSVRTRVQoeCwgaSkgKCh4W2k+PjNdICYgICgxPDwoaSY3KSkpICE9IDApCiNkZWZpbmUgU0VUQklUICAoeCwgaSkgICB4W2k+PjNdIHw9ICgxPDwoaSY3KSkgICAgICAgOwojZGVmaW5lIENMRUFSQklUKHgsIGkpICAgeFtpPj4zXSAmPSAoMTw8KGkmNykpIF4gMHhGRjsKCi8qIGJhc2ljIGxpc3QgbGlicmFyeSAqLwoKdHlwZWRlZiBzdHJ1Y3QgbGlzdCB7CiAgICB2b2lkICpkYXRhOwogICAgc3RydWN0IGxpc3QgKm5leHQ7Cn0gTGlzdDsKCkxpc3QgKmluc2VydCh2b2lkICpkYXRhLCBMaXN0ICpuZXh0KQp7CiAgICBMaXN0ICpuZXc7CgogICAgbmV3ID0gbWFsbG9jKHNpemVvZihMaXN0KSk7CiAgICBuZXctPmRhdGEgPSBkYXRhOwogICAgbmV3LT5uZXh0ID0gbmV4dDsKICAgIHJldHVybiBuZXc7Cn0KCkxpc3QgKnJldmVyc2UoTGlzdCAqbGlzdCkgewogICAgTGlzdCAqbmV3ID0gTlVMTDsKICAgIExpc3QgKm5leHQ7CgogICAgd2hpbGUgKGxpc3QgIT0gTlVMTCkKICAgIHsKICAgICAgICBuZXh0ID0gbGlzdC0+bmV4dDsKICAgICAgICBsaXN0LT5uZXh0ID0gbmV3OwogICAgICAgIG5ldyA9IGxpc3Q7CiAgICAgICAgbGlzdCA9IG5leHQ7CiAgICB9CgogICAgcmV0dXJuIG5ldzsKfQoKaW50IGxlbmd0aChMaXN0ICp4cykKewogICAgaW50IGxlbiA9IDA7CiAgICB3aGlsZSAoeHMgIT0gTlVMTCkKICAgIHsKICAgICAgICBsZW4gKz0gMTsKICAgICAgICB4cyA9IHhzLT5uZXh0OwogICAgfQogICAgcmV0dXJuIGxlbjsKfQoKLyogc2lldmUgb2YgZXJhdG9zdGhlbmVzICovCgpMaXN0ICpwcmltZXMobG9uZyBuKQp7CiAgICBpbnQgbSA9IChuLTEpIC8gMjsKICAgIHVuc2lnbmVkIGNoYXIgYlsobSs3KS84XTsKICAgIGludCBpID0gMDsKICAgIGludCBwID0gMzsKICAgIExpc3QgKnBzID0gTlVMTDsKICAgIGludCBqOwoKICAgIHBzID0gaW5zZXJ0KCh2b2lkICopIDIsIHBzKTsKCiAgICBtZW1zZXQoYiwgMHhGRiwgc2l6ZW9mKGIpKTsKCiAgICB3aGlsZSAocCpwIDw9IG4pCiAgICB7CiAgICAgICAgaWYgKElTQklUU0VUKGIsaSkpCiAgICAgICAgewogICAgICAgICAgICBwcyA9IGluc2VydCgodm9pZCAqKSBwLCBwcyk7CiAgICAgICAgICAgIGogPSAocCpwIC0gMykgLyAyOwogICAgICAgICAgICB3aGlsZSAoaiA8IG0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIENMRUFSQklUKGIsIGopOwogICAgICAgICAgICAgICAgaiArPSBwOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGkgKz0gMTsgcCArPSAyOwogICAgfQoKICAgIHdoaWxlIChpIDwgbSkKICAgIHsKICAgICAgICBpZiAoSVNCSVRTRVQoYixpKSkKICAgICAgICB7CiAgICAgICAgICAgIHBzID0gaW5zZXJ0KCh2b2lkICopIHAsIHBzKTsKICAgICAgICB9CiAgICAgICAgaSArPSAxOyBwICs9IDI7CiAgICB9CgogICAgcmV0dXJuIHJldmVyc2UocHMpOwp9CgovKiB0ZXN0IHByaW1hbGl0eSBieSB0cmlhbCBkaXZpc2lvbiAqLwoKaW50IHRkX3ByaW1lKHVuc2lnbmVkIGxvbmcgbG9uZyBpbnQgbikKewogICAgaWYgKG4gJSAyID09IDApCiAgICB7CiAgICAgICAgcmV0dXJuIG4gPT0gMjsKICAgIH0KCiAgICB1bnNpZ25lZCBsb25nIGxvbmcgaW50IGQgPSAzOwoKICAgIHdoaWxlIChkKmQgPD0gbikKICAgIHsKICAgICAgICBpZiAobiAlIGQgPT0gMCkKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgIH0KICAgICAgICBkICs9IDI7CiAgICB9CgogICAgcmV0dXJuIDE7Cn0KCi8qIGZhY3Rvcml6YXRpb24gYnkgdHJpYWwgZGl2aXNpb24gKi8KCkxpc3QgKnRkX2ZhY3RvcnModW5zaWduZWQgbG9uZyBsb25nIGludCBuKQp7CiAgICBMaXN0ICpmcyA9IE5VTEw7CgogICAgd2hpbGUgKG4gJSAyID09IDApCiAgICB7CiAgICAgICAgZnMgPSBpbnNlcnQoKHZvaWQgKikgMiwgZnMpOwogICAgICAgIG4gLz0gMjsKICAgIH0KCiAgICBpZiAobiA9PSAxKQogICAgewogICAgICAgIHJldHVybiByZXZlcnNlKGZzKTsKICAgIH0KCiAgICB1bnNpZ25lZCBsb25nIGxvbmcgaW50IGYgPSAzOwoKICAgIHdoaWxlIChmKmYgPD0gbikKICAgIHsKICAgICAgICBpZiAobiAlIGYgPT0gMCkKICAgICAgICB7CiAgICAgICAgICAgIGZzID0gaW5zZXJ0KCh2b2lkICopIGYsIGZzKTsKICAgICAgICAgICAgbiAvPSBmOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBmICs9IDI7CiAgICAgICAgfQogICAgfQoKICAgIGZzID0gaW5zZXJ0KCh2b2lkICopIG4sIGZzKTsKICAgIHJldHVybiByZXZlcnNlKGZzKTsKfQoKLyogbWlsbGVyLXJhYmluIHByaW1hbGl0eSBjaGVja2VyICovCgppbnQgaXNfc3BzcChtcHpfdCBuLCBtcHpfdCBhKQp7CiAgICBtcHpfdCBkLCBuMSwgdDsKICAgIG1wel9pbml0cyhkLCBuMSwgdCwgTlVMTCk7CiAgICBtcHpfc3ViX3VpKG4xLCBuLCAxKTsKICAgIG1wel9zZXQoZCwgbjEpOwogICAgaW50IHMgPSAwOwoKICAgIHdoaWxlIChtcHpfZXZlbl9wKGQpKQogICAgewogICAgICAgIG1wel9kaXZleGFjdF91aShkLCBkLCAyKTsKICAgICAgICBzICs9IDE7CiAgICB9CgogICAgbXB6X3Bvd20odCwgYSwgZCwgbik7CiAgICBpZiAobXB6X2NtcF91aSh0LCAxKSA9PSAwIHx8IG1wel9jbXAodCwgbjEpID09IDApCiAgICB7CiAgICAgICAgbXB6X2NsZWFycyhkLCBuMSwgdCwgTlVMTCk7CiAgICAgICAgcmV0dXJuIDE7CiAgICB9CgogICAgd2hpbGUgKC0tcyA+IDApCiAgICB7CiAgICAgICAgbXB6X211bCh0LCB0LCB0KTsKICAgICAgICBtcHpfbW9kKHQsIHQsIG4pOwogICAgICAgIGlmIChtcHpfY21wKHQsIG4xKSA9PSAwKQogICAgICAgIHsKICAgICAgICAgICAgbXB6X2NsZWFycyhkLCBuMSwgdCwgTlVMTCk7CiAgICAgICAgICAgIHJldHVybiAxOwogICAgICAgIH0KICAgIH0KCiAgICBtcHpfY2xlYXJzKGQsIG4xLCB0LCBOVUxMKTsKICAgIHJldHVybiAwOwp9CgppbnQgaXNfcHJpbWUobXB6X3QgbikKewogICAgc3RhdGljIGdtcF9yYW5kc3RhdGVfdCBnbXBSYW5kU3RhdGU7CiAgICBzdGF0aWMgaW50IGlzX3NlZWRlZCA9IDA7CgogICAgaWYgKCEgaXNfc2VlZGVkKQogICAgewogICAgICAgIGdtcF9yYW5kaW5pdF9kZWZhdWx0KGdtcFJhbmRTdGF0ZSk7CiAgICAgICAgZ21wX3JhbmRzZWVkX3VpKGdtcFJhbmRTdGF0ZSwgdGltZShOVUxMKSk7CiAgICAgICAgaXNfc2VlZGVkID0gMTsKICAgIH0KCiAgICBtcHpfdCBhLCBuMywgdDsKICAgIG1wel9pbml0cyhhLCBuMywgdCwgTlVMTCk7CiAgICBtcHpfc3ViX3VpKG4zLCBuLCAzKTsKICAgIGludCBpOwogICAgaW50IGsgPSAyNTsKICAgIGxvbmcgdW5zaWduZWQgcHNbXSA9IHsgMiwgMywgNSwgNyB9OwoKICAgIGlmIChtcHpfY21wX3VpKG4sIDIpIDwgMCkKICAgIHsKICAgICAgICBtcHpfY2xlYXJzKGEsIG4zLCB0LCBOVUxMKTsKICAgICAgICByZXR1cm4gMDsKICAgIH0KCiAgICBmb3IgKGkgPSAwOyBpIDwgc2l6ZW9mKHBzKSAvIHNpemVvZihsb25nIHVuc2lnbmVkKTsgaSsrKQogICAgewogICAgICAgIG1wel9tb2RfdWkodCwgbiwgcHNbaV0pOwogICAgICAgIGlmIChtcHpfY21wX3VpKHQsIDApID09IDApCiAgICAgICAgewogICAgICAgICAgICBtcHpfY2xlYXJzKGEsIG4zLCB0LCBOVUxMKTsKICAgICAgICAgICAgcmV0dXJuIG1wel9jbXBfdWkobiwgcHNbaV0pID09IDA7CiAgICAgICAgfQogICAgfQoKICAgIHdoaWxlIChrID4gMCkKICAgIHsKICAgICAgICBtcHpfdXJhbmRvbW0oYSwgZ21wUmFuZFN0YXRlLCBuMyk7CiAgICAgICAgbXB6X2FkZF91aShhLCBhLCAyKTsKICAgICAgICBpZiAoISBpc19zcHNwKG4sIGEpKQogICAgICAgIHsKICAgICAgICAgICAgbXB6X2NsZWFycyhhLCBuMywgdCwgTlVMTCk7CiAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgIH0KICAgICAgICBrIC09IDE7CiAgICB9CgogICAgbXB6X2NsZWFycyhhLCBuMywgdCwgTlVMTCk7CiAgICByZXR1cm4gMTsKfQoKLyogaW50ZWdlciBmYWN0b3JpemF0aW9uIGJ5IHBvbGxhcmQgcmhvICovCgpMaXN0ICppbnNlcnRfaW5fb3JkZXIodm9pZCAqeCwgTGlzdCAqeHMpCnsKICAgIGlmICh4cyA9PSBOVUxMIHx8IG1wel9jbXAoeCwgeHMtPmRhdGEpIDwgMCkKICAgIHsKICAgICAgICByZXR1cm4gaW5zZXJ0KHgsIHhzKTsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBMaXN0ICpoZWFkID0geHM7CiAgICAgICAgd2hpbGUgKHhzLT5uZXh0ICE9IE5VTEwgJiYgbXB6X2NtcCh4LCB4cy0+bmV4dC0+ZGF0YSkgPiAwKQogICAgICAgIHsKICAgICAgICAgICAgeHMgPSB4cy0+bmV4dDsKICAgICAgICB9CiAgICAgICAgeHMtPm5leHQgPSBpbnNlcnQoeCwgeHMtPm5leHQpOwogICAgICAgIHJldHVybiBoZWFkOwogICAgfQp9Cgp2b2lkIHJob19mYWN0b3IobXB6X3QgZiwgbXB6X3QgbiwgbG9uZyB1bnNpZ25lZCBjKQp7CiAgICBtcHpfdCB0LCBoLCBkLCByOwoKICAgIG1wel9pbml0X3NldF91aSh0LCAyKTsKICAgIG1wel9pbml0X3NldF91aShoLCAyKTsKICAgIG1wel9pbml0X3NldF91aShkLCAxKTsKICAgIG1wel9pbml0KHIpOwoKICAgIHdoaWxlIChtcHpfY21wX3NpKGQsIDEpID09IDApCiAgICB7CiAgICAgICAgbXB6X211bCh0LCB0LCB0KTsKICAgICAgICBtcHpfYWRkX3VpKHQsIHQsIGMpOwogICAgICAgIG1wel9tb2QodCwgdCwgbik7CgogICAgICAgIG1wel9tdWwoaCwgaCwgaCk7CiAgICAgICAgbXB6X2FkZF91aShoLCBoLCBjKTsKICAgICAgICBtcHpfbW9kKGgsIGgsIG4pOwoKICAgICAgICBtcHpfbXVsKGgsIGgsIGgpOwogICAgICAgIG1wel9hZGRfdWkoaCwgaCwgYyk7CiAgICAgICAgbXB6X21vZChoLCBoLCBuKTsKCiAgICAgICAgbXB6X3N1YihyLCB0LCBoKTsKICAgICAgICBtcHpfZ2NkKGQsIHIsIG4pOwogICAgfQoKICAgIGlmIChtcHpfY21wKGQsIG4pID09IDApIC8qIGN5Y2xlICovCiAgICB7CiAgICAgICAgcmhvX2ZhY3RvcihmLCBuLCBjKzEpOwogICAgfQogICAgZWxzZSBpZiAobXB6X3Byb2JhYl9wcmltZV9wKGQsIDI1KSkgLyogc3VjY2VzcyAqLwogICAgewogICAgICAgIG1wel9zZXQoZiwgZCk7CiAgICB9CiAgICBlbHNlIC8qIGZvdW5kIGNvbXBvc2l0ZSBmYWN0b3IgKi8KICAgIHsKICAgICAgICByaG9fZmFjdG9yKGYsIGQsIGMrMSk7CiAgICB9CgogICAgbXB6X2NsZWFycyh0LCBoLCBkLCByLCBOVUxMKTsKfQoKdm9pZCByaG9fZmFjdG9ycyhMaXN0ICoqZnMsIG1wel90IG4pCnsKCiAgICB3aGlsZSAobXB6X2V2ZW5fcChuKSkKICAgIHsKICAgICAgICBtcHpfdCAqZiA9IG1hbGxvYyhzaXplb2YoKmYpKTsKICAgICAgICBtcHpfaW5pdF9zZXRfdWkoKmYsIDIpOwogICAgICAgICpmcyA9IGluc2VydCgqZiwgKmZzKTsKICAgICAgICBtcHpfZGl2ZXhhY3RfdWkobiwgbiwgMik7CiAgICB9CgogICAgaWYgKG1wel9jbXBfdWkobiwgMSkgPT0gMCkgcmV0dXJuOwoKICAgIHdoaWxlICghIChtcHpfcHJvYmFiX3ByaW1lX3AobiwgMjUpKSkKICAgIHsKICAgICAgICBtcHpfdCAqZiA9IG1hbGxvYyhzaXplb2YoKmYpKTsKICAgICAgICBtcHpfaW5pdF9zZXRfdWkoKmYsIDApOwoKICAgICAgICByaG9fZmFjdG9yKCpmLCBuLCAxKTsKICAgICAgICAqZnMgPSBpbnNlcnRfaW5fb3JkZXIoKmYsICpmcyk7CiAgICAgICAgbXB6X2RpdmV4YWN0KG4sIG4sICpmKTsKICAgIH0KCiAgICAqZnMgPSBpbnNlcnRfaW5fb3JkZXIobiwgKmZzKTsKfQoKLyogZGVtb25zdHJhdGlvbiAqLwoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgKmFyZ3ZbXSkKewogICAgbXB6X3QgbjsKICAgIG1wel9pbml0KG4pOwogICAgTGlzdCAqcHMgPSBOVUxMOwogICAgTGlzdCAqZnMgPSBOVUxMOwoKICAgIHBzID0gcHJpbWVzKDEwMCk7IC8qIDIgMyA1IDcgMTEgMTMgMTcgMTkgMjMgMjkgMzEgMzcgNDEgKi8KICAgIHdoaWxlIChwcyAhPSBOVUxMKSAvKiA0MyA0NyA1MyA1OSA2MSA2NyA3MSA3MyA3OSA4MyA4OSA5NyAqLwogICAgewogICAgICAgIHByaW50ZigiJWxkJXMiLCAobG9uZykgcHMtPmRhdGEsCiAgICAgICAgICAgIChwcy0+bmV4dCA9PSBOVUxMKSA/ICJcbiIgOiAiICIpOwogICAgICAgIHBzID0gcHMtPm5leHQ7CiAgICB9CgogICAgcHJpbnRmKCIlZFxuIiwgbGVuZ3RoKHByaW1lcygxMDAwMDAwKSkpOyAvKiA3ODQ5OCAqLwoKICAgIHByaW50ZigiJWRcbiIsIHRkX3ByaW1lKDYwMDg1MTQ3NTE0M0xMKSk7IC8qIGNvbXBvc2l0ZSAqLwoKICAgIGZzID0gdGRfZmFjdG9ycyg2MDA4NTE0NzUxNDNMTCk7IC8qIDcxIDgzOSAxNDcxIDY4NTcgKi8KICAgIHdoaWxlIChmcyAhPSBOVUxMKQogICAgewogICAgICAgIHByaW50ZigiJWxsdSVzIiwgKHVuc2lnbmVkIGxvbmcgbG9uZyBpbnQpIGZzLT5kYXRhLAogICAgICAgICAgICAoZnMtPm5leHQgPT0gTlVMTCkgPyAiXG4iIDogIiAiKTsKICAgICAgICBmcyA9IGZzLT5uZXh0OwogICAgfQoKICAgIG1wel90IGE7CiAgICBtcHpfaW5pdChhKTsKICAgIG1wel9zZXRfc3RyKG4sICIyMDQ3IiwgMTApOwogICAgbXB6X3NldF9zdHIoYSwgIjIiLCAxMCk7CiAgICBwcmludGYoIiVkXG4iLCBpc19zcHNwKG4sIGEpKTsgLyogcHNldWRvLXByaW1lICovCgogICAgbXB6X3NldF9zdHIobiwgIjYwMDg1MTQ3NTE0MyIsIDEwKTsgLyogY29tcG9zaXRlICovCiAgICBwcmludGYoIiVkXG4iLCBpc19wcmltZShuKSk7CgogICAgbXB6X3NldF9zdHIobiwgIjIzMDU4NDMwMDkyMTM2OTM5NTEiLCAxMCk7IC8qIHByaW1lICovCiAgICBwcmludGYoIiVkXG4iLCBpc19wcmltZShuKSk7CgogICAgbXB6X3NldF9zdHIobiwgIjYwMDg1MTQ3NTE0MyIsIDEwKTsKICAgIHJob19mYWN0b3JzKCZmcywgbik7IC8qIDcxIDgzOSAxNDcxIDY4NTcgKi8KICAgIHdoaWxlIChmcyAhPSBOVUxMKSB7CiAgICAgICAgcHJpbnRmKCIlcyVzIiwgbXB6X2dldF9zdHIoTlVMTCwgMTAsIGZzLT5kYXRhKSwKICAgICAgICAgICAgKGZzLT5uZXh0ID09IE5VTEwpID8gIlxuIiA6ICIgIik7CiAgICAgICAgZnMgPSBmcy0+bmV4dDsKICAgIH0KfQ==