Reverse Decomp Program
 

I have been working on a reverse decomp program to allow LMH>79M to operate in a more similar fashion to normal LMH. Since I don't have much time, I have only completed my work for the nofactor data (which is no longer produced, but these programs will still be useful once we get that process automated). I had to change the sieve limit on decomp to allow it to go beyond 79300000, and it now goes to 1000000000. I also wrote a program called missed.exe, which prints the primes above 79300000 in neither factor nor nofactor into a file called primes. This allows the compression program (compress.exe) to account for the fact that the primes aren’t there. (Note: as it stands, this program needs 125MB of memory, and writes a 125MB file to the disk. The memory is proportional to the upper bound; the file size is of course dependant on what is missing from the data files.) The reason I do this is it allows compress to work without a sieve, making it fast and still effective. Ideally, the data files would have all primes; with the ones with no work done on them in nofactor with fact bits equal to 10 (as we know there are no factors below 1024). Once this is done, missed.exe will not be needed, and the compression operation will take less than a minute. Finally, I would like to note that currently these programs are very picky about the data files, and will fail (sometimes discreetly) if they are not exactly as expected. For example, the most recent factor data has an invalid line after 129999929, causing it to give a false result for exponents larger than 129999929 without an error message. I gave brief instructions in the readme on how to use these programs. Questions, comments, and improvements are welcome. I have the Dec 11 version of the nofactor data if anyone would like to make it available somewhere so people can use it.

Since nothing can be done without the nofactor data, I am going to try to automate the process of creating it, but I can only do work on weekends. Xyzzy, I think you should put the raw data on opteron so many people can try to convert it into usable data.
Nick

Okay, the raw data files are here:

[url]http://opteron.mersenneforum.org/lmh/[/url]

The compress program I use:


#include "stdio.h"
#include "math.h"
#include "malloc.h"
#include "memory.h"

int COMPRESS_FACTORS = 0;
int COMPRESS_NOFACTORS = 0;

#define bitset(a,i) { a[(i) >> 3] |= (1 << ((i) & 7)); }
#define bitclr(a,i) { a[(i) >> 3] &= ~(1 << ((i) & 7)); }
#define bittst(a,i) (a[(i) >> 3] & (1 << ((i) & 7)))

/* Return TRUE if arg is a prime */

int isprime (
unsigned long p)
{
unsigned long f, fmax;
if ((p & 1) == 0) return (p == 2);
if (p % 3 == 0) return (p == 3);
fmax = sqrt (p);
for (f = 5; f <= fmax; f += 6) {
if (p % f == 0) return (0);
if (p % (f+2) == 0) return (0);
}
return (1);
}

/* Use a simple sieve to find prime numbers */

#define MAX_PRIMES 6600
static unsigned int num_primes = 0;
static unsigned int *primes = NULL;
static struct sieve_info {
unsigned long first_number;
unsigned int bit_number;
unsigned int num_bits;
unsigned long start;
unsigned long end;
char array[4096];
} si;

/* Start sieve by allocate a sieve info structure */

void start_sieve (
unsigned long start,
unsigned long end)
{
unsigned int i, fmax;

if (start < 3) start = 3;
si.start = start;
si.end = end;
si.first_number = start | 1;
si.bit_number = 1;
si.num_bits = 0;

if (primes == NULL) {
unsigned int f;
primes = (unsigned int *) malloc (MAX_PRIMES * 2 * sizeof (unsigned int));
for (i = 0, f = 3; i < MAX_PRIMES * 2; f += 2)
if (isprime (f)) primes[i] = f, i += 2;
}

/* Determine the first bit to clear */

fmax = (unsigned int) sqrt ((double) end);
for (i = 0; i < MAX_PRIMES * 2; i += 2) {
unsigned long f, r, bit;
f = primes[i];
if (f > fmax) break;
if (si.first_number == 3) {
bit = (f * f - 3) >> 1;
} else {
r = (unsigned long) (si.first_number % f);
if (r == 0) bit = 0;
else if (r & 1) bit = (f - r) / 2;
else bit = (f + f - r) / 2;
if (f == si.first_number + 2 * bit) bit += f;
}
primes[i+1] = bit;
}
num_primes = i;
}

/* Return next prime from the sieve */

unsigned long sieve ()
{
unsigned int i;

/* Return next prime in the sieve */

ret: while (si.bit_number < si.num_bits) {
unsigned int bit = si.bit_number++;
if (bittst (si.array, bit))
return (si.first_number + 2 * bit);
}

/* See if we are done */

si.first_number += 2 * si.num_bits;
if (si.first_number > si.end)
return (0xFFFFFFFF);

/* Fill the sieve with ones, then zero out the composites */

memset (si.array, 0xFF, sizeof (si.array));
si.num_bits = (unsigned int) (si.end - si.first_number) / 2 + 1;
if (si.num_bits > sizeof (si.array) * 8)
si.num_bits = sizeof (si.array) * 8;
for (i = 0; i < num_primes; i += 2) {
unsigned int f, bit;
f = primes[i];
for (bit = primes[i+1]; bit < si.num_bits; bit += f)
bitclr (si.array, bit);
primes[i+1] = bit - si.num_bits;
}
si.bit_number = 0;
goto ret;
}

void end_sieve ()
{
}

/* Do a subtraction on an ascii number */

void ascsub (char *n, unsigned long amt)
{
unsigned long digit;
char *p;

p = n + strlen (n);
for ( ; ; ) {
digit = *--p - '0';
if (digit < amt) {
*p = (char) (10 + digit - amt + '0');
amt = 1;
} else {
*p = (char) (digit - amt + '0');
break;
}
}
if (n[0] == '0' && n[1] != 0) strcpy (n, n+1);
}

/* Do a division on an ascii number */

void ascdiv (char *fac, unsigned long p, char *res)
{
int leadzero = 1;
unsigned long n, q;

for (n = 0; *fac; fac++) {
n = n * 10 + *fac - '0';
if (leadzero) {
if (n < p) continue;
leadzero = 0;
}
q = n / p;
*res++ = (char) (q + '0');
n = n - q * p;
}
*res = 0;
}

/* Compress one file of factoring data */

void compress_factors (char *fname)
{
static unsigned long group = 999999999;
static FILE *out = NULL;
FILE *factors;
unsigned long p, count;
char fac[200], k[200];

factors = fopen (fname, "r");
if (factors == NULL) {
printf ("Error opening %s\n", fname);
return;
}

if (out == NULL) {
out = fopen ("factors.cmp", "w");
if (out == NULL) {
printf ("Error opening factors.cmp\n");
return;
}
}

for ( ; ; ) {
p = 0;
fscanf (factors, "%lu,%s\n", &p, &fac);
if (p == 0) break;

for (count = 0; sieve () != p; count++);
if (count > 500) {printf ("Fac not found: %lu?\n", p); return;}

ascdiv (fac, p + p, k);
if ((p & 3) == 1) {
ascsub (k, 2);
ascdiv (k, 2, k);
} else {
ascsub (k, 1);
ascdiv (k, 2, k);
}

if (p / 100000 != group) {
group = p / 100000;
fprintf (out, "%lu,%s\n", p, k);
}

else if (count == 0 && k[0] == 0)
fprintf (out, "\n");
else if (count < 10)
fprintf (out, "%lu%s\n", count, k);
else if (count < 36)
fprintf (out, "%c%s\n", count - 10 + 'A', k);
else if (count < 62)
fprintf (out, "%c%s\n", count - 36 + 'a', k);
else
fprintf (out, "%lu,%s\n", count - 62, k);
}

fclose (factors);
}

/* Compress one file of nofactoring data */

void compress_nofactors (char *nofname)
{
static unsigned long group = 999999999;
static FILE *out = NULL;
FILE *nofactors;
unsigned long p, count, limit, b1, b2, last_limit = 0;

nofactors = fopen (nofname, "r");
if (nofactors == NULL) {
printf ("Error opening %s\n", nofname);
return;
}

if (out == NULL) {
out = fopen ("nofactor.cmp", "w");
if (out == NULL) {
printf ("Error opening nofactor.cmp\n");
return;
}
}

for ( ; ; ) {
p = 0;
fscanf (nofactors, "%lu,%lu\n", &p, &limit);
if (p == 0) break;
fscanf (nofactors, ",%lu\n", &b1);
fscanf (nofactors, ",%lu\n", &b2);

for (count = 0; sieve () != p; count++);
if (count > 500) {printf ("Fac not found: %lu?\n", p); return;}

if (p / 100000 != group) {
group = p / 100000;
fprintf (out, "%lu,%lu\n", p, limit);
last_limit = limit;
continue;
}

else if (count == 0 && limit == last_limit)
;
else if (count < 10)
fprintf (out, "%lu", count);
else if (count < 36)
fprintf (out, "%c", count - 10 + 'A');
else if (count < 62)
fprintf (out, "%c", count - 36 + 'a');
else
fprintf (out, "%lu,", count - 62);

if (limit != last_limit) {
if (limit > last_limit && limit - last_limit <= 5)
fprintf (out, "%c\n", limit-last_limit-1+'0');
else if (last_limit > limit && last_limit - limit <= 5)
fprintf (out, "%c\n", last_limit-limit-1+'5');
else
fprintf (out, "%lu\n", limit);
last_limit = limit;
} else
fprintf (out, "\n");
}

fclose (nofactors);
}

/* Compress factoring data */

void compress ()
{
if (COMPRESS_FACTORS) {
start_sieve (3, 79300000);
compress_factors ("c:\\database\\factors");
compress_factors ("c:\\database\\fac2");
end_sieve ();
}
if (COMPRESS_NOFACTORS) {
start_sieve (3, 79300000);
compress_nofactors ("c:\\database\\nofactor");
compress_nofactors ("c:\\database\\nofac2");
end_sieve ();
}
}

/* Compress/decompress factoring data */

void main (int argc, char **argv)
{
int i;
char *p;

/* Process command line switches */

for (i = 1; i < argc; i++) {
p = argv[i];

if (*p++ != '-') break;
switch (*p++) {

case 'F':
case 'f':
COMPRESS_FACTORS = 1;
break;

case 'N':
case 'n':
COMPRESS_NOFACTORS = 1;
break;

/* Otherwise unknown switch */

default:
printf ("Invalid switch\n");
}
}

compress ();
}