home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume10 / cbw / part06 / lpair.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-06-17  |  13.8 KB  |  625 lines
  1. /*
  2.  * Letter pair and equivalence class guessing.
  3.  *
  4.  * Bob Baldwin, May 1985.
  5.  */
  6.  
  7. #include    <stdio.h>
  8. #include    <math.h>
  9. #include    "window.h"
  10. #include    "terminal.h"
  11. #include    "layout.h"
  12. #include    "specs.h"
  13. #include    "cipher.h"
  14.  
  15.  
  16. #define    DEBUG        FALSE
  17. #define    AUTOREPEAT    1    /* Number of times to repeat guess loop. */
  18.  
  19. #define    LPBLABEL1    "Bigram guess, level %6.3f, prob %6.3f  -- Wait"
  20. #define    LPBLABEL2    "Bigram guess, level %6.3f, prob %6.3f  -- Done"
  21. #define    LPBHELP "F3 enters guess, ^G undoes it."
  22.  
  23.  
  24. extern    char    mcbuf[];
  25. extern    ecinfo    gecinfo;
  26. extern    ec_init();
  27. extern    lpbdraw(), lpbfirst(), lpbenter(), lpbundo();
  28.  
  29. /* Gloabal State. */
  30. keyer    lpbktab[] = {
  31.         {CACCEPT, lpbenter},
  32.         {CUNDO, lpbundo},
  33.         {CGO_UP, jogup},
  34.         {CGO_DOWN, jogdown},
  35.         {CGO_LEFT, jogleft},
  36.         {CGO_RIGHT, jogright},
  37.         {0, NULL},
  38. };
  39.  
  40. /* Routine invoked by user to put up the letter pair equivalence class
  41.  * guessing window.
  42.  * The window is drawn empty, and then filled in with the guess.
  43.  * Return NULL if command completes ok.
  44.  */
  45. char    *lpbguess(str)
  46. char    *str;            /* Command line */
  47. {
  48.     ecinfo    *ecbi;
  49.     int        i;
  50.     gwindow    *ecb;
  51.     float    lp_accept_level, lp_prob_cutoff;
  52.  
  53.     ecb = &gbstore;
  54.     ecbi = &gecinfo;
  55.     lp_init(mcbuf, refperm(dbsgetblk(&dbstore)), ecbi);
  56.  
  57.     if ((i = sscanf(str, "%*[^:]: %f %*[^:]: %f",
  58.             &lp_accept_level, &lp_prob_cutoff)) != 2)  {
  59.         return("Could not parameters.");
  60.         }
  61.  
  62.     gbsswitch(ecb, ((char *) ecbi), lpbktab, lpbfirst, wl_noop, lpbdraw);
  63.  
  64.     sprintf(statmsg, LPBLABEL1, lp_accept_level, lp_prob_cutoff);
  65.     gblset(&gblabel, statmsg);
  66.     gbsclear(ecb);
  67.     fflush(stdout);
  68.  
  69.     lp_autoguess(ecbi, lp_accept_level);
  70.     decode(ecbi->ciphertext, ecbi->plaintext, ecbi->perm);
  71.  
  72.     sprintf(statmsg, LPBLABEL2, lp_accept_level, lp_prob_cutoff);
  73.     gblset(&gblabel, statmsg);
  74.     lpbdraw(ecb);
  75.  
  76.     return(NULL);
  77. }
  78.  
  79.  
  80. /*  (re) Draw the window.
  81.  */
  82. lpbdraw(ecb)
  83. gwindow    *ecb;
  84. {
  85.     int            i;
  86.     int            row, col;
  87.     ecinfo        *ecbi;
  88.  
  89.     ecbi = ((ecinfo *) ecb->wprivate);
  90.     row = 1;
  91.     col = 1;
  92.  
  93.     for (i = 0 ; i < BLOCKSIZE ; i++)  {
  94.         if (i%LINELEN == 0) {
  95.             wl_setcur(ecb, gbspos2row(i), gbspos2col(i));
  96.             }
  97.         plnchars(1, char2sym(ecbi->plaintext[i]));
  98.         }
  99.  
  100.     for (i = gbspos2row(BLOCKSIZE) ; i <= GBHEIGHT ; i++) {
  101.         wl_setcur(ecb, i, 1);
  102.         plnchars(LINELEN, ' ');
  103.         }
  104.  
  105.     for (i = 1 ; i <= GBHEIGHT ; i++) {
  106.         wl_setcur(ecb, i, LINELEN+1);
  107.         plnchars(ecb->wwidth - LINELEN, ' ');
  108.         }
  109.  
  110.     wl_setcur(ecb, row, col);
  111. }
  112.  
  113.  
  114. /* First time cursor enters window.
  115.  */
  116. lpbfirst(ecb, row, col)
  117. gwindow    *ecb;
  118. int            row, col;
  119. {
  120.     usrhelp(&user, LPBHELP);
  121.     wl_setcur(ecb, row, col);
  122. }
  123.  
  124.  
  125. /* Enter the guess into the decryption block.
  126.  */
  127. lpbenter(ecb)
  128. gwindow    *ecb;
  129. {
  130.     ecinfo        *ecbi;
  131.  
  132.     ecbi = ((ecinfo *) ecb->wprivate);
  133.     dbsmerge(&dbstore, ecbi->perm);
  134.     wl_rcursor(ecb);
  135. }
  136.  
  137.  
  138. /* Undo the last guess.
  139.  */
  140. lpbundo(ecb)
  141. gwindow    *ecb;
  142. {
  143.     ecinfo        *ecbi;
  144.  
  145.     ecbi = ((ecinfo *) ecb->wprivate);
  146.     dbsundo(&dbstore);
  147.     wl_rcursor(ecb);
  148. }
  149.  
  150.  
  151.  
  152. /* Guess at a block using letter pair statistics.
  153.  * The parameter accept_level is the minimum ratio (of estmated prob
  154.  * that the guess is right over estimate prob that some other guess
  155.  * is right) needed to accept a guess.
  156.  * The parameter prob_cutoff is the minimum probability (density) that
  157.  * the guess is right.  This parameter comes into play when there is one
  158.  * guess which looks much better than the rest (i.e., has a high ratio),
  159.  * but in fact all the guesses look pretty bad, so the program should
  160.  * avoid picking one.
  161.  * Modfies eci.
  162.  */
  163. lp_autoguess(eci, accept_level, prob_cutoff)
  164. reg    ecinfo    *eci;
  165.     float    accept_level;
  166.     float    prob_cutoff;
  167. {
  168.     int        i;
  169. reg    int        c;
  170.     int        ntried;
  171. reg    int        classpos;
  172.     int        *permp;
  173.     int        repeat;
  174.  
  175. for(repeat = 0 ; repeat < AUTOREPEAT ; repeat++)  {
  176.     ntried = 0;
  177.     for (ntried = 0 ; ntried < BLOCKSIZE ; ntried++)  {
  178.         classpos = lp_best_pos(eci, 2);
  179.         if (classpos == NONE)
  180.             break;
  181.         c = lp_best_char(eci, classpos,
  182.                         accept_level - ((repeat == 0) ? 0.0 : 0.0),
  183.                         prob_cutoff);
  184.         if (c != NONE) {
  185.             lp_accept(eci, classpos, c);
  186.             }
  187.         }
  188. #if (AUTOREPEAT > 1)
  189.     for (i = 0 ; i < eci->nclasses ; i++)  {
  190.         eci->classlist[i].changed = TRUE;
  191.         }
  192. #endif
  193.     }
  194. }
  195.  
  196.  
  197. /* Score a guess using letter pair statistics.
  198.  * Bigger scores are better scores.  They range from 0 to 1.
  199.  * A score of zero means the choice is not possible.
  200.  * The result is the probability density that the guess is correct.
  201.  * Actually, the resulting score is the product of the prob densities
  202.  * of the first and second order statistics.
  203.  */
  204. float    lp_cscore(gsi)
  205. reg    gsinfo    *gsi;
  206. {
  207.     extern    float    score2_scale, score1_scale;
  208.     float    score1, score2;
  209. reg    float    sdev1, sdev2;        /* Standard Deviation for 1st and 2nd stats. */
  210.     int        ccount;
  211.  
  212.     for (ccount = 0 ; gsi->cpos[ccount] != NONE ; ccount++);
  213.  
  214.     sdev1 = gsi_1score(gsi);
  215.     if (sdev1 < 0.0)  return(0.0);
  216.     score1 = fexp(sdev1);
  217.     score1 = (score1 * isqrt[ccount]) / score1_scale;
  218.  
  219.     sdev2 = gsi_2score(gsi);
  220.     if (sdev2 < 0.0)  return(0.0);
  221.     score2 = fexp(sdev2);
  222.     score2 = (score2 * isqrt[ccount]) / score2_scale;
  223.  
  224.     return(score1 * score2);
  225. }
  226.  
  227.  
  228. /* Select best plaintext value for a ciphertext equiv class.
  229.  * The class is identified by the position in the block of one
  230.  * of the characters in the class.  The plaintext value for
  231.  * an entire class can be specified by the plaintext value of
  232.  * one of its members.  This routine returns the best plaintext
  233.  * value for the ciphertext character at position firstpos.
  234.  * If there is not a clear best value, NONE is returned.
  235.  */
  236. int    lp_best_char(eci, firstpos, alevel, min_prob)
  237. reg        ecinfo    *eci;
  238. int        firstpos;
  239. float    alevel;        /* Level to accept a guess ~= prob(right)/prob(wrong) */
  240. float    min_prob;
  241. {
  242. #if DEBUG
  243.     int        pvec[BLOCKSIZE+1];
  244.     char    str[BLOCKSIZE+1];
  245. #endif
  246.     float    total_score, score;
  247.     float    best_score;
  248.     int        best_char;
  249. reg    int        c;
  250.     int        x,y;
  251.     int        class;
  252.     float    count;
  253. reg    gsinfo    *gsi;
  254.     gsinfo    tmpgsi;
  255.     int        gssbuf[BLOCKSIZE+1];
  256.  
  257.     gsi = &tmpgsi;
  258.     gsi_init(gsi, eci->plaintext, gssbuf);
  259.  
  260.     total_score = 0.0;
  261.     best_score = 0.0;
  262.     count = 0.0;
  263.     best_char = NONE;
  264.  
  265.     for (c = 0 ; c <= MAXCHAR  ; c++)  {
  266.         gsi_clear(gsi);
  267.         if (gsi_class_guess(gsi, eci, firstpos, c) == 0)
  268.             continue;
  269.         score = lp_cscore(gsi);
  270.         if (score > 0.0)  {
  271.             count += 1.0;
  272.             total_score += score;
  273.             }
  274.         if (score > best_score) {
  275.             best_score = score;
  276.             best_char = c;
  277.             }
  278.         }
  279.  
  280. #if DEBUG
  281.     printf("Total score is %7.4f", total_score);
  282.     printf(".  Count is %4.0f.\n", count);
  283. #endif
  284.     if (total_score == 0.0  ||  count == 0.0  ||  best_char == NONE) {
  285. #if DEBUG
  286.         printf("NO GUESSES\n");
  287. #endif
  288.         return(NONE);
  289.         }
  290. #if DEBUG
  291.     printf("Best score is %7.4f", best_score);
  292.     printf(", which is %7.4f fraction of total", best_score/total_score);
  293.     printf(".\n");
  294.  
  295.     class = eci->posclass[firstpos];
  296.     printf("Class reliability is %d.",
  297.         (2 * eci->classlist[class].npairs) + eci->classlist[class].nchars);
  298.     printf("  ");
  299.  
  300.     decode_class(eci, firstpos, best_char, pvec);
  301.     pvec2str(str, pvec);
  302.     printf("The best chars are '%s'\n", str);
  303. #endif
  304.  
  305.     if ((best_score  >  alevel * (total_score - best_score))
  306.      && (best_score > min_prob)) {
  307.         return(best_char);
  308.         }
  309.     else {
  310.         return(NONE);
  311.         }
  312. }
  313.  
  314.  
  315. /* Accept a guess.
  316.  * Updates the eci plaintext to reflect the characters deduced from
  317.  * assuming that the plaintext character at position pos is pchar.
  318.  * It updates the npairs count and used flag in the class info list.
  319.  * The changed flag is set for positions pos-1 and pos+1 (if they exist).
  320.  * The used flag is set for the class(es) that now have an accepted value.
  321.  */
  322. lp_accept(eci, firstpos, firstpchar)
  323. reg        ecinfo    *eci;
  324. int        firstpos;
  325. int        firstpchar;
  326. {
  327.     int        firstflag;    /* For macro for_pos_in_class. */
  328.     int        otherpos;
  329. reg    int        pos;
  330.     int        x,y;
  331.     int        pchar;
  332.     int        delta;
  333.     clinfo    *firstclassp, *otherclassp;
  334. reg    clinfo    *classp;
  335.  
  336.     firstpos = firstpos & MODMASK;
  337.     firstpchar = firstpchar & CHARMASK;
  338.     x = eci->scipher[firstpos];
  339.     y = MODMASK & (firstpchar + firstpos);
  340.  
  341.     eci->perm[x] = y;
  342.     eci->perm[y] = x;
  343.  
  344.     firstclassp = &(eci->classlist[eci->posclass[firstpos]]);
  345.     firstclassp->used = TRUE;
  346.  
  347.     otherpos = eci->permmap[y];
  348.     if (otherpos == NONE)  {
  349.         otherclassp = NULL;
  350.         }
  351.       else  {
  352.         otherclassp = &(eci->classlist[eci->posclass[otherpos]]);
  353.         otherclassp->used = TRUE;
  354.         }
  355.  
  356.  
  357.     delta = y - x;
  358.     for_pos_in_class(pos, firstpos)  {
  359.         pchar = MODMASK & (eci->scipher[pos] + delta - pos);
  360.         eci->plaintext[pos] = pchar;
  361.         if ((pos - 1) >= 0)  {
  362.             classp = &(eci->classlist[eci->posclass[pos - 1]]);
  363.             if (classp != firstclassp)  {
  364.                 classp->changed = TRUE;
  365.                 classp->npairs++;
  366.                 }
  367.             }
  368.         if ((pos + 1) < BLOCKSIZE)  {
  369.             classp = &(eci->classlist[eci->posclass[pos + 1]]);
  370.             if (classp != firstclassp)  {
  371.                 classp->changed = TRUE;
  372.                 classp->npairs++;
  373.                 }
  374.             }
  375.         }
  376.  
  377.     if (otherpos != NONE)  {
  378.         delta = x - y;
  379.         for_pos_in_class(pos, otherpos)  {
  380.             pchar = MODMASK & (eci->scipher[pos] + delta - pos);
  381.             eci->plaintext[pos] = pchar;
  382.             if ((pos - 1) >= 0)  {
  383.                 classp = &(eci->classlist[eci->posclass[pos - 1]]);
  384.                 if (classp != otherclassp)  {
  385.                     classp->changed = TRUE;
  386.                     classp->npairs++;
  387.                     }
  388.                 }
  389.             if ((pos + 1) < BLOCKSIZE)  {
  390.                 classp = &(eci->classlist[eci->posclass[pos + 1]]);
  391.                 if (classp != otherclassp)  {
  392.                     classp->changed = TRUE;
  393.                     classp->npairs++;
  394.                     }
  395.                 }
  396.             }
  397.         }
  398. }
  399.  
  400.  
  401.  
  402. /* Pick the best position to do guessing.
  403.  * Use the class info list to select the unused class that will yield
  404.  * the most reliable guesses.
  405.  * The changed flag is cleared to make sure that a class is not considered
  406.  * again unless the reliability of its guesses has changed.
  407.  * At first, all the changed flags should be set.
  408.  * The changed flag for the selected class is cleared.
  409.  * Returns a position or NONE.
  410.  */
  411. int    lp_best_pos(eci, min_reliability)
  412. reg        ecinfo    *eci;
  413. int        min_reliability;
  414. {
  415.     int        score;
  416.     int        best_score, best_pos;
  417. reg    clinfo    *classp;
  418. reg    clinfo    *endclassp;
  419.  
  420.     best_score = 0;
  421.     best_pos = NONE;
  422.     endclassp = &(eci->classlist[eci->nclasses]);
  423.     for (classp = &(eci->classlist[0]) ; classp < endclassp ; classp++)  {
  424.         if ((classp->used) || (!(classp->changed)))
  425.             continue;
  426.         score = (2 * (classp->npairs)) + classp->nchars;
  427.         if (score > best_score)  {
  428.             best_score = score;
  429.             best_pos = classp->firstpos;
  430.             }
  431.         }
  432.     if (best_score < min_reliability)
  433.         return(NONE);
  434.  
  435.     if (best_pos != NONE)  {
  436.         eci->classlist[eci->posclass[best_pos]].changed = FALSE;
  437.         }
  438.     return(best_pos);
  439. }
  440.  
  441.  
  442. /* Fill in equiv class info from given ciphertext block
  443.  * and permutation.
  444.  */
  445. lp_init(cipher, perm, eci)
  446. char    cipher[];
  447. int        perm[];
  448. reg        ecinfo    *eci;
  449. {
  450.     int        firstflag;    /* Used by for_pos_in_class */
  451.     int        i,j;
  452.     int        firstpos, char_count, pair_count;
  453. reg    int        pos;
  454. reg    clinfo    *class;
  455.  
  456.     ec_init(cipher, perm, eci);
  457.  
  458.     for (i = 0 ; i < BLOCKSIZE ; i++)  {
  459.         eci->posclass[i] = NONE;
  460.         }
  461.  
  462.     eci->nclasses = 0;
  463.     for (i = 0 ; i < BLOCKSIZE ; i++)  {
  464.         if ((firstpos = eci->permmap[i]) == NONE)
  465.             continue;
  466.         char_count = 0;
  467.         pair_count = 0;
  468.         for_pos_in_class(pos, firstpos) {
  469.             eci->posclass[pos] = eci->nclasses;
  470.             char_count++;
  471.             }
  472.         for_pos_in_class(pos, firstpos) {
  473.             if ((pos + 1) < BLOCKSIZE)  {
  474.                  if (eci->posclass[pos + 1] == eci->nclasses)  {
  475.                     pair_count++;
  476.                     }
  477.                 else if (eci->perm[eci->scipher[pos + 1]] != NONE)  {
  478.                     pair_count++;
  479.                     }
  480.                 }
  481.             if ((pos - 1) >= 0)  {
  482.                  if (eci->posclass[pos - 1] == eci->nclasses)  {
  483.                     /* Don't double count it. */
  484.                     }
  485.                 else if (eci->perm[eci->scipher[pos - 1]] != NONE)  {
  486.                     pair_count++;
  487.                     }
  488.                 }
  489.             }
  490.         class = &(eci->classlist[eci->nclasses]);
  491.         class->nchars = char_count;
  492.         class->npairs = pair_count;
  493.         class->firstpos = firstpos;
  494.         class->changed = TRUE;
  495.         if (eci->perm[i] != NONE)
  496.             class->used = TRUE;
  497.         else
  498.             class->used = FALSE;
  499.  
  500.         eci->nclasses++;
  501.         }
  502. }
  503.  
  504.  
  505. /* Initialize a guess info structure.
  506.  * Also clears the guess buffer.
  507.  */
  508. gsi_init(gsi, pbuf, gssbuf)
  509. reg        gsinfo    *gsi;
  510.         int        *pbuf;        /* Accepted characters. */
  511. reg        int        *gssbuf;    /* Buffer for new guesses. */
  512. {
  513. reg    int        i;
  514.  
  515.     gsi->cknown = pbuf;
  516.     gsi->cpos[0] = NONE;
  517.     gsi->cguessed = gssbuf;
  518.     for (i = 0 ; i < BLOCKSIZE ; i++)
  519.         *gssbuf++ = NONE;
  520. }
  521.  
  522.  
  523. /* Clear out a guess from a gsi.
  524.  */
  525. gsi_clear(gsi)
  526. reg    gsinfo    *gsi;
  527. {
  528. reg    int        *ip;
  529.  
  530.     for (ip = &(gsi->cpos[0]) ; *ip != NONE ; ip++)  {
  531.         gsi->cguessed[*ip] = NONE;
  532.         }
  533.     gsi->cpos[0] = NONE;
  534. }
  535.  
  536.  
  537. /* Add to a gsi with the characters deduced from assuming that
  538.  * the character at firstpos is c.
  539.  * If that asumption conflicts with eci->perm, then nothing is added.
  540.  * Returns the number of characters added.
  541.  */
  542. int    gsi_class_guess(gsi, eci, firstpos, c)
  543. reg        gsinfo    *gsi;
  544. reg        ecinfo    *eci;
  545.         int        firstpos;
  546.         int        c;
  547. {
  548.     int        firstflag;    /* For macro for_pos_in_class. */
  549.     int        otherpos;
  550. reg    int        pos;
  551.     int        x,y;
  552.     int        pchar;
  553.     int        delta;
  554.     int        *cposp;
  555.     int        nchars;
  556.  
  557.     for (cposp = &(gsi->cpos[0]) ; *cposp != NONE ; cposp++);
  558.     nchars = 0;
  559.  
  560.     firstpos = firstpos & MODMASK;
  561.     c = c & CHARMASK;
  562.     x = eci->scipher[firstpos];
  563.     y = MODMASK & (c + firstpos);
  564.  
  565.     if (perm_conflict(eci->perm, x, y))
  566.         return(nchars);
  567.  
  568.     delta = y - x;
  569.     for_pos_in_class(pos, firstpos)  {
  570.         pchar = MODMASK & (eci->scipher[pos] + delta - pos);
  571.         if ((pchar & CHARMASK) != pchar)  {
  572.             *cposp = NONE;
  573.             return(0);
  574.             }
  575.         gsi->cguessed[pos] = pchar;
  576.         *cposp++ = pos;
  577.         nchars++;
  578.         }
  579.  
  580.     otherpos = eci->permmap[y];
  581.     if (otherpos != NONE)  {
  582.         delta = x - y;
  583.         for_pos_in_class(pos, otherpos)  {
  584.             pchar = MODMASK & (eci->scipher[pos] + delta - pos);
  585.             if ((pchar & CHARMASK) != pchar)  {
  586.                 *cposp = NONE;
  587.                 return(0);
  588.                 }
  589.             gsi->cguessed[pos] = pchar;
  590.             *cposp++ = pos;
  591.             nchars++;
  592.             }
  593.         }
  594.     *cposp = NONE;
  595.     return(nchars);
  596. }
  597.  
  598.  
  599. /* Dump class table onto a stream.
  600.  */
  601. lp_dclasses(out, eci)
  602. FILE    *out;
  603. ecinfo    *eci;
  604. {
  605.     int        i;
  606.  
  607.     fprintf(out, "\nThere are %d classes.\n", eci->nclasses);
  608.     for (i = 0 ; i < eci->nclasses ; i++)  {
  609.         fprintf(out, "Singles: %d, pairs: %d,  First member: %d",
  610.                 eci->classlist[i].nchars, eci->classlist[i].npairs,
  611.                 eci->classlist[i].firstpos);
  612.         fprintf(out, ", flags:");
  613.         if (!(eci->classlist[i].used))
  614.             fprintf(out, " not");
  615.         fprintf(out, " used");
  616.         fprintf(out, " and");
  617.         if (!(eci->classlist[i].changed))
  618.             fprintf(out, " not");
  619.         fprintf(out, " changed");
  620.         fprintf(out, "\n");
  621.         }
  622. }
  623.  
  624.  
  625.