Compression program

[Prime95]

Here is the program I use to create the factor.cmp and nofactor.cmp files.

[Prime95]

Hmm. Attachment didn't work.....


#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 ();
}