#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

//
// if this is 1 then
//    1==i==l
//    0==o
//
#define EQUATE_SIMILAR_CHARS    1

#define PUZZLE_CODES_NEEDED     30
#define PUZZLE_CODE_LEN         6

#define LOCATION_CODE_LEN       6
#define LOCATION_CODES_NEEDED   2
//#define LOCATION_CODES_NEEDED 30

#define MIN_UNIQUE              2
#define MIN_FAR                 1
#define MIN_SHIFTED_UNIQUE      1
#define MIN_SHIFTED_FAR         0

#define MAX_PARM_VAL    30
#define MAX_PARM1_VAL   30
#define MAX_PARM2_VAL   30
#define MAX_CODE_LEN    10

#if EQUATE_SIMILAR_CHARS
#define NUM_CHARS       33
#else
#define NUM_CHARS       36
#endif

typedef unsigned long long icode;

int do_print = 0;

#if 0
icode p1_mul[MAX_CODE_LEN];
icode p2_mul[MAX_CODE_LEN];
icode code_max[MAX_CODE_LEN];
#endif

#define USE_RANDOM_CODE_ADD     0

//icode     g_code_add = 0xfad0beefeL;
icode       g_code_add = 103995407L;        // a large prime


typedef struct CodeCriterion_s {
    int mins[4];
} CodeCriterion;

typedef enum CodeMode_e {
    CM_PUZZLE,
    CM_SPECIAL,
    CM_LOCATION,
    CM_EXTRA_PUZ,
    CM_EXTRA_LOC,

    CM_END
} CodeMode;

typedef struct CodeInfo_s {
    char        *code;
    char        *func;
    char        *parm0;
    int          id;
    int          parm1_max;
    int          parm2_max;
    CodeMode     mode;
    struct CodeInfo_s   *next;
    
} CodeInfo;

typedef struct CodeCollide_s {
    int      hist[4][MAX_CODE_LEN+1];
    int      min[4];
    char    *colcode[4];
} CodeCollide;

typedef struct CodeList_s {
    CodeInfo    **list[MAX_CODE_LEN];
    int           cnt[MAX_CODE_LEN];
    int           max[MAX_CODE_LEN];
    int           puzzle_cnt;
    int           location_cnt;

    CodeInfo    *puzzle_head;
    CodeInfo    **puzzle_tail;
    CodeInfo    *location_head;
    CodeInfo    **location_tail;
    CodeInfo    *special_head;
    CodeInfo    **special_tail;

    CodeInfo    *puzzles[PUZZLE_CODES_NEEDED];
    CodeInfo    *locations[LOCATION_CODES_NEEDED];

} CodeList;

int code_max_cnt = 0;

//int ocode_cnt = 0;
//int pcode_cnt = 0;
//int code_len;

CodeList code_list1;
CodeList *code_list = &code_list1;

#define ASSERT(cond)    if (!(cond)) { assert_err( #cond ); }

CodeInfo *check_add_code(CodeList *list, char *code, char *func,
                        char *parm0, int parm1_max, int parm2_max,
                        CodeCriterion *criterion);
char *fixup_code(char *code);

void assert_err(char *str)
{
    fprintf(stderr,"ASSERT FAILED: %s\n",str);
    exit(1);
}

int find_mul = 0;

void check_code_chars(char *str)
{
    while(*str) {
        ASSERT( (*str >= '0' && *str <= '9') ||
                (*str >= 'a' && *str <= 'z'));
        str++;
    }
}

void init_codes(CodeList *list)
{
    int i;
    int cnt = (MAX_PARM1_VAL+1)*(MAX_PARM2_VAL+1) * (LOCATION_CODES_NEEDED+1) + PUZZLE_CODES_NEEDED + 100;
    int size = cnt * sizeof(CodeInfo*);
    memset(list, 0, sizeof(*list));
    for (i=0; i<MAX_CODE_LEN; i++) {
        list->list[i] = (CodeInfo**)malloc(size);
        memset(list->list[i],0,size);
        list->cnt[i] = 0;
        list->max[i] = cnt;
        list->puzzle_cnt = 0;
        list->location_cnt = 0;
    }

    list->puzzle_tail = &list->puzzle_head;
    list->location_tail = &list->location_head;
    list->special_tail = &list->special_head;
}

void set_puzzle_code(CodeList *list, CodeInfo *ci, int val)
{
    if (val < 0) {
        for (val = 0; val < PUZZLE_CODES_NEEDED; val++) {
            if (list->puzzles[val] == 0) break;
        }
        ASSERT(val < PUZZLE_CODES_NEEDED);
    }

    if (list->puzzles[val] != 0) {
        fprintf(stderr,"ERROR: puzzle %d is already assigned to '%s' - cannot be reassigned to '%s'!\n",
            val,list->puzzles[val]->code,ci->code);
        return;
    }
    
    ci->id = val;
    list->puzzles[val] = ci;
}

CodeInfo *set_location_code(CodeList *list, CodeInfo *ci, int val)
{
    if (val < 0) {
        for (val = 0; val < LOCATION_CODES_NEEDED; val++) {
            if (list->locations[val] == 0) break;
        }
        ASSERT(val < LOCATION_CODES_NEEDED);
    }

    if (list->locations[val] != 0) {
        fprintf(stderr,"ERROR: locations %d is already assigned to '%s' - cannot be reassigned to '%s'!\n",
            val,list->locations[val]->code,ci->code);
        return;
    }
    
    ci->id = val;
    list->locations[val] = ci;
}

void delete_code(CodeInfo *ci)
{
    ASSERT(ci->mode == CM_EXTRA_LOC || ci->mode == CM_EXTRA_PUZ);
    ASSERT(ci->id == -1);
    if (ci->code) free(ci->code);
    if (ci->func) free(ci->func);
    if (ci->parm0) free(ci->parm0);
    free(ci);
}

void remove_code(CodeList *list, char *code)
{
    int i;
    int len = strlen(code);
    for (i=0; i<list->cnt[len]; i++) {
        CodeInfo *ci = list->list[len][i];
        if (!strcmp(ci->code, code)) {
            delete_code(ci);
            list->cnt[len]--;
            list->list[len][i] = list->list[len][list->cnt[len]];
            list->list[len][list->cnt[len]] = 0;
        }
    }
}

int is_loc_func(char *func)
{
    if (!func) return 0;
    if (!strcmp(func, "LOCATION")) return 1;
    if (!strcmp(func, "func_fn_loccode")) return 1;
    return 0;
}

int is_puz_func(char *func)
{
    if (!func) return 0;
    if (!strcmp(func, "PUZZLE")) return 1;
    if (!strcmp(func, "func_fn_puzcode")) return 1;
    return 0;
}

CodeInfo *add_code(CodeList *list, char *ocode, char *func, char *parm0, int parm1_max, int parm2_max, int is_loc)
{
    char *code = fixup_code(ocode);

    int idx;
    int len = strlen(code);
    CodeInfo *ci = (CodeInfo*)malloc(sizeof(CodeInfo) + len + 1);

    check_code_chars(code);

    remove_code(list, code);

    ASSERT(len >0 && len <= MAX_CODE_LEN);
    ci->code = strdup(code);
    ci->func = 0;
    ci->parm0 = (parm0&&parm0[0])?strdup(parm0):0;
    ci->parm1_max = parm1_max;
    ci->parm2_max = parm2_max;
    ci->mode = is_loc ? CM_EXTRA_LOC : CM_EXTRA_PUZ;
    ci->next = 0;
    ci->id = -1;

    if (func) {
        if (!strncmp(func,"func_fn_",8)) {
            ci->func = strdup(func);
            if (is_loc_func(func)) {
                ci->mode = CM_LOCATION;
            } else if (is_puz_func(func)) {
                ci->mode = CM_PUZZLE;
            } else {
                ci->mode = CM_SPECIAL;
            }
        } else if (is_loc_func(func)) {
            ci->mode = CM_LOCATION;
        } else if (is_puz_func(func)) {
            ci->mode = CM_PUZZLE;
        } else {
            fprintf(stderr,"Bad function name: '%s'\n",func);
        }
    }

    switch(ci->mode) {
        case CM_PUZZLE:
            list->puzzle_cnt++;
            *list->puzzle_tail = ci;
            list->puzzle_tail  = &ci->next;
            if (ci->parm0 && !strncmp(ci->parm0, "puz", 3)) {
                char *e;
                long val = strtol(ci->parm0+3,&e,10);
                if (e && *e == 0 && e != ci->parm0+3) {
                    set_puzzle_code(list, ci, val);
                } else {
                    fprintf(stderr,"parm0='%s'\n",ci->parm0);
                    fprintf(stderr,"WARNING: "
                        "Could not determine puzzle number for code '%s'\n",
                        ci->code);
                }
            }
            break;
        case CM_LOCATION:
            list->location_cnt++;
            *list->location_tail = ci;
            list->location_tail  = &ci->next;
            if (ci->parm0 && !strncmp(ci->parm0, "loc", 3)) {
                char *e;
                long val = strtol(ci->parm0+3,&e,10);
                if (e && *e == 0 && e != ci->parm0+3) {
                    set_location_code(list, ci, val);
                } else {
                    fprintf(stderr,"WARNING: "
                        "Could not determine location number for code '%s'\n",
                        ci->code);
                }
            }
            break;
        case CM_SPECIAL:
            *list->special_tail = ci;
            list->special_tail  = &ci->next;
            break;
        default:
            break;
    }

    ASSERT(list->cnt[len] < list->max[len]);
    idx = list->cnt[len]++;
    if (list->list[len][idx]) {
        free(list->list[len][idx]);
    }
    list->list[len][idx] = ci;
    
    free(code);

    return ci;
}

CodeList *bookmark_create(CodeList *list)
{
    CodeList *bookmark = (CodeList *)malloc(sizeof(CodeList));
    memcpy(bookmark, list, sizeof(CodeList));
    return bookmark;
}

void bookmark_delete(CodeList *bookmark)
{
    free(bookmark);
}

void bookmark_restore(CodeList *list, CodeList *bookmark)
{
    memcpy(list, bookmark, sizeof(CodeList));
    bookmark_delete(bookmark);
}


void read_codes(CodeList *list, char *filename)
{
    FILE *fp = fopen(filename,"rt");
    int c;
    int state = 1;
    int linenum = 1;
    char code[100];
    char func[100];
    char parm0[100];
    int parm1_max;
    int parm2_max;
    CodeCollide *cc;

    if (!fp) {
        fprintf(stderr,"ERROR: Could not read file '%s'\n",filename);
        return;
    }   

    c = getc(fp);
    while(state != 1000) {
        while (state < 7) {
            switch(c) {
                case 'C': if (state==1) state++; break;
                case 'O': if (state==2) state++; break;
                case 'D': if (state==3) state++; break;
                case 'E': if (state==4) state++; break;
                case ' ': if (state==5) state = 7; break;
                case '\t': if (state==5) state = 7; break;
                case EOF: state = 1000; break;
                case '\n': state = 1; linenum++; break;
                default:    state = 6; break;
            }
            c = getc(fp);
        }

        #define PARSE_ASSERT(cond)                                          \
                if (!(cond)) {                                              \
                    fprintf(stderr,"PARSE ERROR: %s:%d: ASSERT(%s)\n",      \
                        filename,linenum,#cond);                            \
                    continue;                                               \
                }

        if (state == 7) {
            int cnt;
            state = 6;

            //
            // read code string
            //
            while(isspace(c) && c!= '\n') c = getc(fp);
            PARSE_ASSERT(c=='"');
            c = getc(fp);
            cnt=0;
            while(c!='"' && c!='\n' && c!=EOF) {
                PARSE_ASSERT(cnt<100);
                code[cnt++] = tolower(c);
                c = getc(fp);
            }
            PARSE_ASSERT(c=='"');
            c = getc(fp);
            code[cnt++] = 0;

            //
            // read func name
            //
            while(isspace(c) && c!= '\n') c = getc(fp);
            PARSE_ASSERT(c=='f');
            cnt = 0;
            while(!isspace(c) && c!=EOF && c!= '#') {
                PARSE_ASSERT(cnt<100);
                func[cnt++] = c;
                c = getc(fp);
            }
            func[cnt++] = 0;
            
            //
            // read parm0 (optional)
            //
            while(isspace(c) && c!= '\n') c = getc(fp);
            cnt = 0;
            while(!isspace(c) && c!=EOF && c!= '#') {
                PARSE_ASSERT(cnt<100);
                parm0[cnt++] = c;
                c = getc(fp);
            }
            parm0[cnt++] = 0;
            
            //
            // read parm1_max (optional)
            //
            while(isspace(c) && c!= '\n') c = getc(fp);
            parm1_max = 0;
            while(!isspace(c) && c!=EOF && c!= '#') {
                PARSE_ASSERT(isdigit(c));
                parm1_max *= 10;
                parm1_max += c - '0';
                c = getc(fp);
            }
            
            //
            // read parm2_max (optional)
            //
            while(isspace(c) && c!= '\n') c = getc(fp);
            parm2_max = 0;
            while(!isspace(c) && c!=EOF && c!= '#') {
                PARSE_ASSERT(isdigit(c));
                parm2_max *= 10;
                parm2_max += c - '0';
                c = getc(fp);
            }

            //
            // read rest of line
            //
            while(isspace(c) && c!= '\n') c = getc(fp);
            PARSE_ASSERT(c == '\n' || c==EOF || c=='#');
            
            //
            // add code
            //
            check_add_code(list, code, func, parm0, parm1_max, parm2_max, 0);
        }
    }
    #undef PARSE_ASSERT

    fclose(fp);
}

#if 0
void setup(void)
{
#if 0
    static int p1_sc[MAX_CODE_LEN] = 
        {1,0,2,0,3,0,4,0,5,0};
    static int p2_sc[MAX_CODE_LEN] = 
        {0,1,0,2,0,3,0,4,0,5};
#else
    static int p1_sc[MAX_CODE_LEN] = 
        {3,1,4,0,3,2,4,3,1,3};
    static int p2_sc[MAX_CODE_LEN] = 
        {2,0,1,3,2,4,2,0,2,1};
#endif

    int i;
    icode digit;

    time_t t;
    time(&t);
    srandom(t);

    while(1) {
        CodeList *save_cnt = bookmark_create(code_list);
        digit = 1;
        p1_mul[0] = p2_mul[0] = p1_mul[1] = p2_mul[1] = 0;
        for (i=2; i<MAX_CODE_LEN; i++) {
            if (find_mul) {
                p1_sc[i-1] = random() % 5;
                do {
                    p2_sc[i-1] = random() % 5;
                } while (p2_sc[i-1] == p1_sc[i-1]);
            }
            p1_mul[i] = p1_mul[i-1] + digit * p1_sc[i-1];
            p2_mul[i] = p2_mul[i-1] + digit * p2_sc[i-1];
            digit *= NUM_CHARS;
            code_max[i-1] = digit;
            fprintf(stderr,"len=%2d  p1_sc=%d p2_sc=%d code_max=%-16Ld p1_mul=%-16Ld p2_mul=%-16Ld\n",
                i+1,p1_sc[i],p2_sc[i],code_max[i],p1_mul[i],p2_mul[i]);
        }

        for (i=0; i<MAX_CODE_LEN+1; i++) {
            hist3[i] = 0;
            hist4[i] = 0;
        }
        check_perms("aaaaaa", MAX_PARM1_VAL, MAX_PARM2_VAL, 0);
        for (i=0; i<MAX_CODE_LEN+1; i++) {
            fprintf(stderr,"[%2d]%-10d ",i,hist3[i]);
        }
        fprintf(stderr,"\n");
        for (i=0; i<MAX_CODE_LEN+1; i++) {
            fprintf(stderr,"[%2d]%-10d ",i,hist4[i]);
        }
        fprintf(stderr,"\n");

        bookmark_restore(code_list,save_cnt);

        if (!find_mul) break;

        if (hist3[6]==1 &&
            hist4[6]==1 &&
            hist3[5]==0 &&
            hist4[5]==0 &&
            hist3[4]==0 /*&&
            hist4[4]==0 /*&&
            hist3[3]==0 /*&&
            (hist4[3]==0 || hist3[2]==0)*/) {
            break;
        }
    }
}
#endif

icode find_prime(icode max)
{
    #define MAX_PRIMES  100000
    icode list[MAX_PRIMES];
    icode cnt = 1;
    icode p = 1;
    icode i;
    icode p10 = 100;

    list[0] = 2;

    fprintf(stderr,"FINDING PRIMES (max=0x%08x%08x)\n",
        (int)(max >> (icode)32),
        (int)(max & (icode)0xffffffffL));
    while(1) {
        p += 2;
        if (p > max) {
            p = list[cnt-1];
            break;
        }
        for (i=0; (p % list[i]) != 0;) {
            i++;
            if (i == cnt) {
                if (p > p10) {
                    p10 *= (icode)10;

                    fprintf(stderr,"\n  0x%08x%08x ",
                        (int)(p >> (icode)32),
                        (int)(p & (icode)0xffffffffL));
                }
                if ((cnt % 64) == 0) {
                    fprintf(stderr,".");
                }
                ASSERT(cnt < MAX_PRIMES);
                list[cnt++] = p;
                break;
            }
        }
    }
    fprintf(stderr,"\n");

    fprintf(stderr,"FOUND PRIME: 0x%08x%08x\n",
        (int)(p >> (icode)32),
        (int)(p & (icode)0xffffffffL));
}

void setup(void)
{
    int i;
    icode digit;

    time_t t;
    time(&t);
    srandom(t);

#if USE_RANDOM_CODE_ADD
    g_code_add =  (icode)random();
    g_code_add ^= (icode)random() << (icode)32;
    g_code_add ^= (icode)random() << (icode)16;
#endif
#if USE_PRIME_CODE_ADD
    {
        icode max = 1;
        max *= NUM_CHARS;
        max *= NUM_CHARS;
        max *= NUM_CHARS;
        max *= NUM_CHARS;
        max *= NUM_CHARS;
        max *= NUM_CHARS;

        max -= 1;

        g_code_add = find_prime(max);
    }
#endif
    fprintf(stderr,"USING code_add = 0x%08x%08x\n",
        (int)(g_code_add >> (icode)32),
        (int)(g_code_add & (icode)0xffffffffL));
}

int char2int(int c)
{
#if EQUATE_SIMILAR_CHARS
    if (c>='a' && c<'l') return c-'a';
    if (c>'l' && c<='z') return c-'a' - 1;
    if (c>='2' && c<='9') return c-'2'+25;
#else
    if (c>='a' && c<='z') return c-'a';
    if (c>='0' && c<='9') return c-'0'+26;
    //if (c>='A' && c<='Z') return c-'A';
#endif
    fprintf(stderr,"BAD CODE CHARACTER: %d = 0x%02x = '%c'\n",
        c,c,isprint(c)?c:'?');
    exit(1);
    return -1;
}

int int2char(int i)
{
#if EQUATE_SIMILAR_CHARS
    if (i>=0 && i<'l'-'a') return i+'a';
    if (i>='l'-'a' && i<25) return i+'a'+1;
    if (i>=25 && i<=32) return i+'2'-25;
#else
    if (i>=0 && i<=25) return i+'a';
    if (i>=26 && i<=35) return i+'0'-26;
#endif
    fprintf(stderr,"BAD CODE DIGIT: %d = 0x%02x = '%c'\n",
        i,i,isprint(i)?i:'?');
    exit(1);
    return -1;
}

icode code2int(char *code)
{
    int len = strlen(code);
    icode num = 0;
    int i;
    for (i=0; i<len; i++) {
        num *= NUM_CHARS;
        num += char2int(code[i]);
    }
    return num;
}

char *int2code(icode num, int len)
{
    char *code;
    int i=1;
    icode digit = 1;
    ASSERT(digit > 0);
    while(i<len || num >= digit * NUM_CHARS) {
        i++;
        digit *= NUM_CHARS;
        ASSERT(digit > 0);
    }

    len = i;
    code = (char*)malloc(len + 1);
    code[len] = 0;
    
    for (i=0; i<len; i++) {
        int val = num/digit;
        num = num - (digit * val);
        code[i] = int2char(val);
        digit /= NUM_CHARS;
    }
    return code;
}

char *fixup_code(char *code)
{
    char *c2 = strdup(code);
    char *s;

    for (s=c2; *s; s++) {
        *s = tolower(*s);

#if EQUATE_SIMILAR_CHARS
        if (*s == '0') *s = 'o';
        if (*s == '1') *s = 'i';
        if (*s == 'l') *s = 'i';
#endif
    }

    return c2;
}

#if 1
//
// create next code
//
char *next_code(char *code)
{
    int len =strlen(code);
    icode ic = code2int(code);
    icode ic2;
    int i;
    icode max = 1;
    char *nc;

    for (i=0; i<len; i++) {
        max *= NUM_CHARS;
    }

    //
    // swap each nibble pair
    //
    ic2 = 0;
    for (i=0; ic != 0; i++) {
        icode v;
        v = ic >> (icode)(i*8);
        v &= (icode)0xf;
        ic2 |= v << (icode)(i*8+4);
        v = ic >> (icode)(i*8+4);
        v &= (icode)0xf;
        ic2 |= v << (icode)(i*8);

        ic &= ~((icode)0xff << (icode)(i*8));
    }
    ic = ic2;

    //
    // add constant
    //
    ic = ic + g_code_add;
    
    //
    // clamp
    //
    ic = ic % max;

    nc = int2code(ic, len);
    if (strlen(nc) != len) {
        free(nc);
        nc = 0;
    }
    return nc;
}
#else
//
// create next code
//
char *next_code(char *code)
{
    int len =strlen(code);
    icode ic = code2int(code);
    icode ic2;
    int i;
    icode max = 1;
    char *nc;

    for (i=0; i<len; i++) {
        max *= NUM_CHARS;
    }

    //
    // swap each nibble pair
    //
    ic2 = 0;
    for (i=0; ic != 0; i++) {
        icode v;
        v = ic >> (icode)(i*8);
        v &= (icode)0xf;
        ic2 |= v << (icode)(i*8+4);
        v = ic >> (icode)(i*8+4);
        v &= (icode)0xf;
        ic2 |= v << (icode)(i*8);

        ic &= ~((icode)0xff << (icode)(i*8));
    }
    ic = ic2;

    //
    // add constant
    //
    ic = ic + g_code_add;
    
    //
    // clamp
    //
    ic = ic % max;

    nc = int2code(ic, len);
    if (strlen(nc) != len) {
        free(nc);
        nc = 0;
    }
    return nc;
}
#endif


CodeCollide *create_code_collide(void)
{
    int i;
    CodeCollide *cc = (CodeCollide*)malloc(sizeof(CodeCollide));

    memset(cc, 0, sizeof(*cc));

    for (i=0; i<4; i++) {
        cc->colcode[i] = strdup("NONE");
        cc->min[i] = MAX_CODE_LEN;
    }

    return cc;
}

void add_code_collide(CodeCollide *res, CodeCollide *a, CodeCollide *b)
{
    int i, j;
    for (i=0; i<4; i++) {
        char *colcode;
        if (a->min[i] < b->min[i]) {
            res->min[i] = a->min[i];
            colcode = strdup(a->colcode[i]);
        } else {
            res->min[i] = b->min[i];
            colcode = strdup(b->colcode[i]);
        }
        free(res->colcode[i]);
        res->colcode[i] = colcode;

        for (j=0; j<MAX_CODE_LEN; j++) {
            res->hist[i][j] = a->hist[i][j] + b->hist[i][j];
        }
    }
}

void delete_code_collide(CodeCollide *cc)
{
    free(cc->colcode[0]);
    free(cc->colcode[1]);
    free(cc->colcode[2]);
    free(cc->colcode[3]);
    free(cc);
}

void show_code_collide(CodeCollide *cc, char *code, char *ind)
{
    int len = strlen(code);
    int i,j;
    int max  = 100000;
    int maxd = 5;
    fprintf(stderr,"%scollision for code '%s' len=%d\n",ind,code,len);
#if 1
    for (j=0; j<4; j++) {
        for (i=0; i<=len+1; i++) {
            while (max <= cc->hist[j][i]) {
                max *= 10;
                maxd++;
            }
        }
    }
#endif
    for (j=0; j<4; j++) {
        static char *nm[4] = {
            "unique     ",
            "very unique",
            "sh unique  ",
            "sh v unique",
        };
        fprintf(stderr,"%s   %s ",ind,nm[j]);
        for (i=0; i<=len+1; i++) {
            fprintf(stderr,"%*d ",maxd,cc->hist[j][i]);
        }
        fprintf(stderr,"  %s\n",cc->colcode[j]);
    }
    fprintf(stderr,"\n");
}

//
// return 0 if ok
// return 1 if too close
//
int check_code_collide(CodeCollide *cc, CodeCriterion *crit)
{
    int i,j;
    if (!crit) return 0;
    for (i=0; i<4; i++) {
#if 1
        if (cc->min[i] < crit->mins[i]) return 1;
#else
        for (j=0; j<crit->mins[i]; j++) {
            if (cc->hist[i][j] > 0) {
                return 1;
            }
        }
#endif
    }
    return 0;
}

int check_similar(int c1, int c2)
{
    if (c1 == c2) return 1;
    if (c1 == c2+1) return 1;
    if (c1 == c2-1) return 1;
#if EQUATE_SIMILAR_CHARS
    // i==l==1   0==o
    if (c1 == '2' && c2=='z') return 1;
    if (c1 == '9' && c2=='a') return 1;
    if (c2 == '2' && c1=='z') return 1;
    if (c2 == '9' && c1=='a') return 1;
    if (c1 == 'o') {
        if (c2 == 'i' || c2 == 'z') return 1;
    }
    if (c1 == 'i') {
        if (c2 == 'k' || c2 == 'm') return 1;
        if (c2 == 'o' || c2 == '2') return 1;
    }
#else
    if (c1 == '0' && c2=='z') return 1;
    if (c1 == '9' && c2=='a') return 1;
    if (c2 == '0' && c1=='z') return 1;
    if (c2 == '9' && c1=='a') return 1;
    if (c1 == '0' && c2=='o') return 1;
    if (c2 == '0' && c1=='o') return 1;
    if (c1 == '1' && c2=='l') return 1;
    if (c2 == '1' && c1=='l') return 1;
    if (c1 == '1' && c2=='i') return 1;
    if (c2 == '1' && c1=='i') return 1;
    if (c1 == 'i' && c2=='l') return 1;
    if (c2 == 'i' && c1=='l') return 1;
#endif

    return 0;
}

void iswap(int *i1, int *i2)
{
    int tmp;
    tmp = *i1;
    *i1 = *i2;
    *i2 = tmp;
}

void sswap(char **s1, char **s2)
{
    char *tmp;
    tmp = *s1;
    *s1 = *s2;
    *s2 = tmp;
}

void check_combine(int *min, int *cnt, int len)
{
    int i;
    for (i=0; i<4; i++) {
        int c = len - cnt[i];
        if (min[i] > c) {
            min[i] = c;
        }
        cnt[i] = 0;
    }
}

void check_code2(CodeCollide *cc, char *code1, char *code2, int both_loc)
{
    int len1 = strlen(code1);
    int len2 = strlen(code2);
    int i,j;
    int cnt[4] = {0,0,0,0};
    int min[4] = {len1+len2,len1+len2,len1+len2,len1+len2};
    int close = 0;
    int same = 0;
    int shift_close = 0;
    int shift_same = 0;
    char cp[100];
    char *tc;
    int  ti;

    char *l_code = code2;

    if (len1 < len2) {
        iswap(&len1,&len2);
        sswap(&code1,&code2);
    }

    if (len1 == len2) {
        for (i=0; i<len1; i++) {
            if (check_similar(code1[i], code2[i])) {
                cnt[1]++;
                if (code1[i] == code2[i]) {
                    cnt[0]++;
                }
            }
        }
        check_combine(min, cnt, len1);

        if (!both_loc) {
            //
            // check shifted
            //
            for (j=1; j<len1; j++) {
                for (i=0; i<len1; i++) {
                    int i2 = (i+j) % len1;
                    if (check_similar(code1[i], code2[i2])) {
                        cnt[3]++;
                        if (code1[i] == code2[i2]) {
                            cnt[2]++;
                        }
                    }
                }
                check_combine(min, cnt, len1);
            }

            //
            // check shifted reversed
            //
            for (j=1; j<len1; j++) {
                for (i=0; i<len1; i++) {
                    int i2 = (i-j+len1) % len1;
                    if (check_similar(code1[i], code2[i2])) {
                        cnt[3]++;
                        if (code1[i] == code2[i2]) {
                            cnt[2]++;
                        }
                    }
                }
                check_combine(min, cnt, len1);
            }
        }

    } else if (len1 == len2 + 1) {

        ASSERT(!both_loc);

        for (j=0; j<len1; j++) {
            for (i=0; i<len2; i++) {
                int i1 = (i>=j) ? i : (i+1);
                if (check_similar(code1[i1], code2[i])) {
                    cnt[3]++;
                    if (code1[i1] == code2[i]) {
                        cnt[2]++;
                    }
                }
            }
            check_combine(min, cnt, len1);
        }

    } else {
        ASSERT(!both_loc);
        return;
    }

    //
    // min indicates how many unique/very unique characters
    //   min[0] = at least this many unique chars
    //   min[1] = at least this many very unique chars
    //   min[2] = at least this many unique chars in any rotation
    //   min[3] = at least this many very unique chars in any rotation
    //
    //   (very unique means they are not adjacent characters)
    //
    for (i=0; i<4; i++) {
        ASSERT(min[i] >= 0 && min[i] <= MAX_CODE_LEN);
        cc->hist[i][min[i]]++;
        if (min[i] < cc->min[i]) {
            cc->min[i] = min[i];
            free(cc->colcode[i]);
            cc->colcode[i] = strdup(l_code);
        }
    }
}

CodeCollide *check_code(CodeList *list, char *code, int isloc)
{
    CodeCollide *cc = create_code_collide();
    int i,len;

    check_code_chars(code);

    len = strlen(code);

    for (i=len-1; i<= len+1; i++) {
        CodeInfo **cip;
        CodeInfo **cie;
        if (i <= 0) continue;
        if (i > MAX_CODE_LEN) continue;
        cip = list->list[i];
        cie = cip + list->cnt[i];
        for (; cip != cie; cip++) {
            check_code2(cc,code,(*cip)->code,
                isloc && ((*cip)->mode == CM_LOCATION ||
                          (*cip)->mode == CM_EXTRA_LOC));
        }
    }

    return cc;
}

CodeInfo *check_add_code(CodeList *list, char *ocode, char *func,
                        char *parm0, int parm1_max, int parm2_max,
                        CodeCriterion *criterion)
{
    char *code = fixup_code(ocode);

    int cnt = (parm1_max+1) * (parm2_max+1);
    CodeList *save_cnt = bookmark_create(list);
    char *code1 = strdup(code);
    CodeCollide *cc = create_code_collide();
    CodeCollide *cc2;
    int i;
    int is_loc = is_loc_func(func);


    for(i=1; i<cnt; i++) {
        char *code2;
        if (i%64 == 0) {
            fprintf(stderr,".");
        }

        code2 = next_code(code1);
        free(code1);
        code1 = code2;
        if (code1) {
            cc2 = check_code(list, code1, is_loc);
        }

        if (!code1 || check_code_collide(cc2, criterion)) {
            fprintf(stderr,"\n");
            if (code1) {
                fprintf(stderr,"REJECT code='%s' for perm[%d]='%s'\n",
                    code,i,code1);
                show_code_collide(cc2, code1, "REJECT ");
                delete_code_collide(cc2);
                free(code1);
            } else {
                fprintf(stderr,"REJECT code='%s' Could not create perm[%d]\n",
                    code,i);
            }
            delete_code_collide(cc);
            
            bookmark_restore(list, save_cnt);
            free(code);
            return 0;
        }
        add_code_collide(cc,cc,cc2);
        add_code(list, code1, 0, 0, 0, 0, is_loc);
    }
    if (cnt > 127) {
        fprintf(stderr,"\n");
    }

    free(code1);

    cc2 = check_code(list, code, is_loc);

    if (check_code_collide(cc2, criterion)) {
        fprintf(stderr,"REJECT code='%s' for itself\n",
            code);
        show_code_collide(cc2, code, "REJECT ");
        delete_code_collide(cc2);
        delete_code_collide(cc);
        
        bookmark_restore(list, save_cnt);
        free(code);
        return 0;
    }
    add_code_collide(cc,cc,cc2);

    show_code_collide(cc, code, "ADD ");

    bookmark_delete(save_cnt);

    free(code);
    return add_code(list, ocode, func, parm0, parm1_max, parm2_max, is_loc);
}

CodeInfo *add_rand_code(int len, int max_p1, int max_p2, char *func,
                        CodeCriterion *crit)
{
    char code[MAX_CODE_LEN+1];
    int i;

    ASSERT(len <= MAX_CODE_LEN);
    
    code[len] = 0;
    for (i=0; i<len; i++) {
        code[i] = int2char(random() % NUM_CHARS);
    }

    fprintf(stderr,"try(%d,%d)(%d) %s\n",max_p1,max_p2,code_list->cnt[len],code);

    return check_add_code(code_list, code, func, 0, max_p1, max_p2, crit);
}

void output_code(FILE *out, char *code, char *func, char *parm0, int parm1_max, int parm2_max)
{
    fprintf(out,"CODE \"%s\" %s",
        code,
        func?func:"func_fn_unknown");

    if (parm0 || parm1_max || parm2_max) {
        fprintf(out," %s",parm0?parm0:"parmval_0");

        if (parm1_max || parm2_max) {
            ASSERT(parm1_max >= 0 && parm1_max <= MAX_PARM_VAL);
            fprintf(out," parmval_%d",parm1_max);
            if (parm2_max) {
                ASSERT(parm2_max >= 0 && parm2_max <= MAX_PARM_VAL);
                fprintf(out," parmval_%d",parm2_max);
            }
        }
    }
    fprintf(out,"\n");
}

void output(FILE *out, CodeList *list)
{
    CodeInfo *ci;
    int i;

    fprintf(out,"; Justice Unlimited Gadget Microcode\n");
    fprintf(out,"; (C) 2004 Nathan (Acorn) Pooley\n");
    fprintf(out,";\n");
    fprintf(out,"; gcodes.sstr\n");
    fprintf(out,";\n");
    fprintf(out,";@DOC@ Codes\n");
    fprintf(out,";\n");
    fprintf(out,"\n");
    fprintf(out,"; WARNING: DO NOT EDIT THIS FILE BY HAND\n");
    fprintf(out,"; This file is autogenerated by codegen.c.\n");


    fprintf(out,"\n\n");
    for (i=0; i<8; i++) {
        icode icb;
        icb = g_code_add >> (icode)(i*8);
        icb &= (icode)0xff;
        fprintf(out,"#define CODE_ADD_%d\t\t0x%02x\n",
                i,(int)icb);
    }
    fprintf(out,"\n\n");

    for (i=0; i<=MAX_PARM_VAL; i++) {
        fprintf(out,"#define parmval_%d     %d\n",i,i);
    }
    fprintf(out,"\n\n");

    ci = list->special_head;
    while(ci) {
        output_code(out, ci->code, ci->func, ci->parm0, ci->parm1_max, ci->parm2_max);
        ci = ci->next;
    }
    fprintf(out,"\n\n");

    ci = list->puzzle_head;
    while(ci) {
        if (ci->id < 0) {
            set_puzzle_code(list, ci, -1);
        }
        ci = ci->next;
    }

    ci = list->location_head;
    while(ci) {
        if (ci->id < 0) {
            set_location_code(list, ci, -1);
        }
        ci = ci->next;
    }

    for (i=0; i<PUZZLE_CODES_NEEDED; i++) {
        char *func;
        char *parm0p;
        char parm0[100];
        ci = list->puzzles[i];
        ASSERT(ci);
        func = ci->func ? ci->func : "func_fn_puzcode";
        sprintf(parm0,"puz%d",i);
        parm0p = (ci->parm0 && ci->parm0[0]) ? ci->parm0 : parm0;
        
        output_code(out, ci->code, func, parm0p, ci->parm1_max, ci->parm2_max);
    }
    fprintf(out,"\n\n");

    for (i=0; i<LOCATION_CODES_NEEDED; i++) {
        int j,k;
        int len;
        char *func;
        char *parm0p;
        char parm0[100];
        char *code1;
        ci = list->locations[i];
        ASSERT(ci);
        func = ci->func ? ci->func : "func_fn_loccode";
        sprintf(parm0,"loc%d",i);
        parm0p = (ci->parm0 && ci->parm0[0]) ? ci->parm0 : parm0;

        output_code(out, ci->code, func, parm0p, ci->parm1_max, ci->parm2_max);

        len = strlen(ci->code);
        fprintf(out,"\n;   ");
        for (k=0; k<ci->parm2_max; k++) {
            fprintf(out,"%*d  ",len,k);
        }
        code1 = strdup(ci->code);
        for (j=0; j<ci->parm1_max; j++) {
            fprintf(out,"\n; %3d ",j);
            for (k=0; k<ci->parm2_max; k++) {
                char *code2 = next_code(code1);
                fprintf(out,"%s  ",code1);
                free(code1);
                code1 = code2;
            }
        }
        fprintf(out,"\n\n");
    }
    fprintf(out,"\n\n");
}


int main(int argc, char *argv[])
{
    int i;
    int o_cnt;
    CodeCriterion crit;

    ASSERT(sizeof(icode) >= 8);

    init_codes(code_list);
    setup();

    //
    // get pre-assigned codes
    //
    read_codes(code_list,"gadget_codes.sstr");
    
    //
    // get location codes
    //
    crit.mins[0] = 2;
    crit.mins[1] = 1;
    crit.mins[2] = 1;
    crit.mins[3] = 1;
    while(code_list->location_cnt < LOCATION_CODES_NEEDED) {
        add_rand_code(LOCATION_CODE_LEN, MAX_PARM1_VAL, MAX_PARM2_VAL,
                    "LOCATION", &crit);
    }

    //
    // get puzzle codes
    //
    crit.mins[0] = 3;
    crit.mins[1] = 2;
    crit.mins[2] = 2;
    crit.mins[3] = 2;
    while(code_list->puzzle_cnt < PUZZLE_CODES_NEEDED) {
        add_rand_code(LOCATION_CODE_LEN, 0, 0, "PUZZLE", &crit);
    }


    output(stdout, code_list);


    return 0;
}