home *** CD-ROM | disk | FTP | other *** search
/ Mega Top 1 / os2_top1.zip / os2_top1 / APPS / TEKST / CMTEX330 / SOURCE / HYPH.C < prev    next >
C/C++ Source or Header  |  1992-02-19  |  23KB  |  1,255 lines
  1.  
  2. /*
  3.  * %Y%:%M%:%I%:%Q%
  4.  *
  5.  * Copyright 1987,1988,1991 Pat J Monardo
  6.  *
  7.  * Redistribution of this file is permitted through
  8.  * the specifications in the file COPYING.
  9.  *
  10.  * 
  11.  */
  12.  
  13. #ifndef lint
  14. static char *sccsid = "%A%";
  15. #endif
  16.  
  17. #include "tex.h"
  18.  
  19. ptr    ha;
  20. ptr    hb;
  21. int    hc[66];
  22. fnt    hf;
  23. int    hn;
  24. int    hu[64];
  25. int    hyf[65];
  26. int    hyf_char;
  27.  
  28. int    hyphen_passed;
  29.  
  30. int    l_hyf;
  31. int    r_hyf;
  32. int    cur_lang;
  33.  
  34. ptr    init_list;
  35. bool    init_lig;
  36. bool    init_lft;
  37.  
  38. #define HYPH_SIZE    307
  39.  
  40. int    hyph_count;
  41. int    *hyph_len;
  42. str    *hyph_word;
  43. ptr    *hyph_list;
  44.  
  45. #define TRIE_SIZE    20000
  46.  
  47. bool    trie_not_ready;
  48.  
  49. trie_t    *trie;
  50. int    trie_max;
  51. int    trie_ptr;
  52. int    *trie_hash;
  53. bool    *trie_taken;
  54. int    *trie_min;
  55. int    *trie_c;
  56. int    *trie_o;
  57. int    *trie_l;
  58. int    *trie_r;
  59.  
  60. #define TRIE_OP_SIZE        600
  61. #define MAX_TRIE_OPS_PER_LANG    300
  62.  
  63. int    trie_op_ptr;
  64. int    *trie_op_hash;    
  65. int    *trie_op_lang;
  66. int    *trie_op_used;
  67. int    *trie_op_val;
  68. int    *op_start;
  69. int    *hyf_distance;
  70. int    *hyf_next;
  71. int    *hyf_num;
  72.  
  73. void
  74. init_hyph ()
  75. {
  76.     if (trie_not_ready)
  77.         init_trie();
  78.     l_hyf = lhmin;
  79.     r_hyf = rhmin;
  80.     cur_lang = 0;
  81. }
  82.  
  83. void
  84. try_hyph ()
  85. {
  86.     int    c, j;
  87.     ptr    prev_p, p, q;
  88.     
  89.     prev_p = cur_p;
  90.     p = link(cur_p);
  91.     if (p != null) {
  92.         loop {
  93.             if (is_char_node(p)) {
  94.                 c = character(p);
  95.                 hf = font(p);
  96.             } else if (type(p) == LIGATURE_NODE) {
  97.                 if (lig_ptr(p) == null)
  98.                     goto contin;
  99.                 q = lig_ptr(p);
  100.                 c = character(q);
  101.                 hf = font(q);
  102.             } else if (type(p) == KERN_NODE
  103.                 && subtype(p) == NORMAL) {
  104.                 goto contin;
  105.             } else if (type(p) == WHATSIT_NODE) {
  106.                 try_hyph_whatsit(p);
  107.                 goto contin;
  108.             } else {
  109.                 goto done1;
  110.             }
  111.             if (lc_code(c) != 0) {
  112.                 if (lc_code(c) == c || uc_hyph > 0) {
  113.                     goto done2;
  114.                 } else {
  115.                     goto done1;
  116.                 }
  117.             }
  118.         contin:
  119.             prev_p = p;
  120.             p = link(p);
  121.         }
  122.     done2:
  123.         hyf_char = hyphen_char(hf);
  124.         if (hyf_char < 0 || hyf_char > 255)
  125.             goto done1;
  126.         ha = prev_p;
  127.         if (l_hyf + r_hyf > 63)
  128.             goto done1;
  129.         hn = 0;
  130.         loop {
  131.             if (is_char_node(p)) {
  132.                 if (font(p) != hf)
  133.                     goto done3;
  134.                 c = character(p);
  135.                 if (lc_code(c) == 0 || hn == 63)
  136.                     goto done3;
  137.                 hb = p;
  138.                 incr(hn);
  139.                 hu[hn] = c;
  140.                 hc[hn] = lc_code(c);
  141.             } else if (type(p) == LIGATURE_NODE) {
  142.                 if (font(lig_char(p)) != hf)
  143.                     goto done3;
  144.                 j = hn;
  145.                 q = lig_ptr(p);
  146.                 while (q != null) {
  147.                     c = character(q);
  148.                     if (lc_code(c) == 0 || j == 63)
  149.                         goto done3;
  150.                     incr(j);
  151.                     hu[j] = c;
  152.                     hc[j] = lc_code(c);
  153.                     q = link(q);
  154.                 }
  155.                 hb = p;
  156.                 hn = j;
  157.             } else if (type(p) != KERN_NODE
  158.                 || subtype(p) != NORMAL) {
  159.                 goto done3;
  160.             }
  161.             p = link(p);
  162.         }
  163.     done3:
  164.         if (hn < l_hyf + r_hyf)
  165.             goto done1;
  166.         loop {
  167.             if (!is_char_node(p)) {
  168.                 switch (type(p))
  169.                 {
  170.                 case LIGATURE_NODE:
  171.                     break;
  172.  
  173.                 case KERN_NODE:
  174.                     if (subtype(p) != NORMAL)
  175.                         goto done4;
  176.                     break;
  177.  
  178.                 case WHATSIT_NODE:
  179.                 case GLUE_NODE:
  180.                 case PENALTY_NODE:
  181.                 case INS_NODE:
  182.                 case ADJUST_NODE:
  183.                 case MARK_NODE:
  184.                     goto done4;
  185.                 
  186.                 default: 
  187.                     goto done1;
  188.                 }
  189.             }
  190.             p = link(p);
  191.         }
  192.  
  193.     done4:
  194.         hyphenate();
  195.     }
  196. done1:    return;
  197. }
  198.  
  199. void
  200. hyphenate ()
  201. {
  202.     str    t, u;
  203.     ptr    q, r, s;
  204.     ptr    hyf_node;
  205.     int    bchar;
  206.     int    c_loc;
  207.     int    r_count;
  208.     ptr    major_tail;
  209.     ptr    minor_tail;
  210.     int    c, h, i, j, l, v, z;
  211.  
  212.     for (j = 0; j <= hn; incr(j))
  213.         hyf[j] = 0;
  214.     h = hc[1];
  215.     incr(hn);
  216.     hc[hn] = cur_lang;
  217.     for (j = 2; j <= hn; incr(j))
  218.         h = (h + h + hc[j]) % HYPH_SIZE;
  219.     loop {
  220.         t = hyph_word[h];
  221.         if (t == null_str)
  222.             goto not_found;
  223.         l = hyph_len[h];
  224.         if (l < hn)
  225.             goto not_found;
  226.         if (l == hn) {
  227.             j = 1;
  228.             u = t;
  229.             while (j <= hn) {
  230.                 if (*u < hc[j])
  231.                     goto not_found;
  232.                 if (*u > hc[j])
  233.                     goto done;
  234.                 incr(u);
  235.                 incr(j);
  236.             }
  237.             for (s = hyph_list[h]; s != null; s = link(s))
  238.                 hyf[info(s)] = 1;
  239.             decr(hn);
  240.             goto found;
  241.         }
  242.  
  243.     done:
  244.         if (h > 0) {
  245.             decr(h);
  246.         } else {
  247.             h = HYPH_SIZE;
  248.         }
  249.     }
  250.  
  251. not_found:
  252.     decr(hn);
  253.     if (trie_char(cur_lang + 1) != cur_lang)
  254.         return;
  255.     hc[0] = 0;
  256.     hc[hn + 1] = 0;
  257.     hc[hn + 2] = 256;
  258.     for (j = 0; j <= hn - r_hyf + 1; incr(j)) {
  259.         z = trie_link(cur_lang + 1) + hc[j];
  260.         l = j;
  261.         while (hc[l] == trie_char(z)) {
  262.             if (v = trie_op(z)) {
  263.                 while (v) {
  264.                     v += op_start[cur_lang];
  265.                     i = l - hyf_distance[v];
  266.                     if (hyf_num[v] > hyf[i])
  267.                         hyf[i] = hyf_num[v];
  268.                     v = hyf_next[v];
  269.                 }
  270.             }
  271.             incr(l);
  272.             z = trie_link(z) + hc[l];
  273.         }
  274.     }
  275.  
  276. found:
  277.     for (j = 0; j < l_hyf; incr(j)) {
  278.         hyf[j] = 0;
  279.     }
  280.     for (j = 0; j < r_hyf; incr(j)) {
  281.         hyf[hn - j] = 0;
  282.     }
  283.     for (j = l_hyf; j <= hn - r_hyf; incr(j))
  284.         if (odd(hyf[j]))
  285.             goto found1;
  286.     return;
  287.  
  288. found1:
  289.     q = link(hb);
  290.     link(hb) = null;
  291.     r = link(ha);
  292.     link(ha) = null;
  293.     bchar = NON_CHAR;
  294.     if (type(hb) == LIGATURE_NODE && odd(subtype(hb))) {
  295.         bchar = font_bchar(hf);
  296.     }
  297.     if (is_char_node(ha)) {
  298.         if (font(ha) != hf) {
  299.             goto found2;
  300.         } else {
  301.             init_list = ha;
  302.             init_lig = FALSE;
  303.             hu[0] = character(ha);
  304.         }
  305.     } else if (type(ha) == LIGATURE_NODE) {
  306.         if (font(lig_char(ha)) != hf) {
  307.             goto found2;
  308.         } else {
  309.             init_list = lig_ptr(ha);
  310.             init_lig = TRUE;
  311.             init_lft = subtype(ha) > 1;
  312.             hu[0] = character(lig_char(ha));
  313.             if (init_list == null && init_lft) {
  314.                 hu[0] = 256;
  315.                 init_lig = FALSE;
  316.             }
  317.             free_node(ha, SMALL_NODE_SIZE);
  318.         }
  319.     } else {
  320.         if (type(r) == LIGATURE_NODE && subtype(r) > 1) {
  321.             goto found2;
  322.         }
  323.         j = 1;
  324.         s = ha;
  325.         init_list = null;
  326.         goto common_end;
  327.     }
  328.     s = cur_p;
  329.     while (link(s) != ha)
  330.         s = link(s);
  331.     j = 0;
  332.     goto common_end;
  333.  
  334. found2:
  335.     s = ha;
  336.     j = 0;
  337.     hu[0] = 256;
  338.     init_lig = FALSE;
  339.     init_list = null;
  340.  
  341. common_end:
  342.     flush_node_list(r);
  343.  
  344. #define advance_major_tail()                        \
  345. {    major_tail = link(major_tail);                    \
  346.     incr(r_count);                            \
  347. }
  348.  
  349. #define put_pre_break()                            \
  350. {    minor_tail = null;                        \
  351.     pre_break(r) = null;                        \
  352.     hyf_node = new_character(hf, hyf_char);                \
  353.     if (hyf_node != null) {                        \
  354.         incr(i);                        \
  355.         c = hu[i];                        \
  356.         hu[i] = hyf_char;                    \
  357.         free_avail(hyf_node);                    \
  358.     }                                \
  359.     while (l <= i) {                        \
  360.         l = reconstitute(l, i, font_bchar(hf), NON_CHAR) + 1;    \
  361.         if (link(hold_head) == null) {                \
  362.             continue;                    \
  363.         }                            \
  364.         if (minor_tail == null) {                \
  365.             pre_break(r) = link(hold_head);            \
  366.         } else {                        \
  367.             link(minor_tail) = link(hold_head);        \
  368.         }                            \
  369.         minor_tail = link(hold_head);                \
  370.         while (link(minor_tail) != null)            \
  371.             minor_tail = link(minor_tail);            \
  372.     }                                \
  373.     if (hyf_node != null) {                        \
  374.         hu[i] = c;                        \
  375.         l = i;                            \
  376.         decr(i);                        \
  377.     }                                \
  378. }
  379.  
  380. #define put_post_break()                        \
  381. {    minor_tail = null;                        \
  382.     post_break(r) = null;                        \
  383.     c_loc = 0;                            \
  384.     if (bchar_label(hf) != NON_ADDRESS) {                \
  385.         decr(l);                        \
  386.         c = hu[l];                        \
  387.         c_loc = l;                        \
  388.         hu[l] = 256;                        \
  389.     }                                \
  390.     while (l < j) {                            \
  391.         do {                            \
  392.             l = reconstitute(l, hn, bchar, NON_CHAR) + 1;    \
  393.             if (c_loc > 0) {                \
  394.                 hu[c_loc] = c;                \
  395.                 c_loc = 0;                \
  396.             }                        \
  397.             if (link(hold_head) == null) {            \
  398.                 continue;                \
  399.             }                        \
  400.             if (minor_tail == null) {            \
  401.                 post_break(r) = link(hold_head);    \
  402.             } else {                    \
  403.                 link(minor_tail) = link(hold_head);    \
  404.             }                        \
  405.             minor_tail = link(hold_head);            \
  406.             while (link(minor_tail) != null)        \
  407.                 minor_tail = link(minor_tail);        \
  408.         } while (l < j);                    \
  409.         while (l > j) {                        \
  410.             j = reconstitute(j, hn, bchar, NON_CHAR) + 1;    \
  411.             link(major_tail) = link(hold_head);        \
  412.             while (link(major_tail) != null) {        \
  413.                 advance_major_tail();            \
  414.             }                        \
  415.         }                            \
  416.     }                                \
  417. }
  418.  
  419.     do {
  420.         l = j;
  421.         j = reconstitute(j, hn, bchar, hyf_char) + 1;
  422.         if (hyphen_passed == 0) {
  423.             link(s) = link(hold_head);
  424.             while (link(s) != null)
  425.                 s = link(s);
  426.             if (odd(hyf[j - 1])) {
  427.                 l = j;
  428.                 hyphen_passed = j - 1;
  429.                 link(hold_head) = null;
  430.             }
  431.         }
  432.         if (hyphen_passed > 0) {
  433.             do {
  434.                 r = new_node(SMALL_NODE_SIZE);
  435.                 link(r) = link(hold_head);
  436.                 type(r) = DISC_NODE;
  437.                 major_tail = r;
  438.                 r_count = 0;
  439.                 while (link(major_tail) != null) {
  440.                     advance_major_tail();
  441.                 }
  442.                 i = hyphen_passed;
  443.                 hyf[i] = 0;
  444.                 put_pre_break();
  445.                 put_post_break();
  446.                 if (r_count > 127) {
  447.                     link(s) = link(r);
  448.                     link(r) = null;
  449.                     flush_node_list(r);
  450.                 } else {
  451.                     link(s) = r;
  452.                     replace_count(r) = r_count;
  453.                 }
  454.                 s = major_tail;
  455.                 hyphen_passed = j - 1;
  456.                 link(hold_head) = null;
  457.             } while (odd(hyf[j - 1]));
  458.         }
  459.     } while (j <= hn);
  460.     link(s) = q;
  461.     flush_list(init_list);
  462. }
  463.  
  464. #define append_charnode_to_t(C)                    \
  465. {    t = link(t) = new_avail();                 \
  466.     font(t) = hf; character(t) = (C);             \
  467. }
  468.  
  469. #define set_cur_r()                        \
  470. {    cur_r = (j < n) ? hu[j + 1] : bchar;            \
  471.     cur_rh = (odd(hyf[j])) ? hchar : NON_CHAR;        \
  472. }
  473.  
  474. #define wrap_lig(RT_HIT)                    \
  475. {    if (ligature_present) {                    \
  476.         p = new_ligature(hf, cur_l, link(cur_q));    \
  477.         if (lft_hit) {                    \
  478.             subtype(p) = 2;                \
  479.             lft_hit = FALSE;            \
  480.         }                        \
  481.         if (RT_HIT) {                    \
  482.             if (lig_stack == null) {        \
  483.                 incr(subtype(p));        \
  484.                 rt_hit = FALSE;            \
  485.             }                    \
  486.         }                        \
  487.         t = link(cur_q) = p;                \
  488.         ligature_present = FALSE;            \
  489.     }                            \
  490. }
  491.  
  492. #define pop_lig_stack()                        \
  493. {    if (lig_ptr(lig_stack) != null) {            \
  494.         t = link(t) = lig_ptr(lig_stack);        \
  495.         incr(j);                    \
  496.     }                            \
  497.     p = lig_stack;                        \
  498.     lig_stack = link(p);                    \
  499.     free_node(p, SMALL_NODE_SIZE);                \
  500.     if (lig_stack == null) {                \
  501.         set_cur_r();                    \
  502.     } else {                        \
  503.         cur_r = character(lig_stack);            \
  504.     }                            \
  505. }
  506.  
  507. #define lig_replace()                         \
  508. {    if (cur_l == NON_CHAR)                     \
  509.         lft_hit = TRUE;                    \
  510.     if (j == n && lig_stack == null)            \
  511.         rt_hit = TRUE;                    \
  512.     check_interrupt();                     \
  513.     switch (op_byte(q)) {                    \
  514.     case 1: case 5:                        \
  515.         cur_l = rem_byte(q);                \
  516.         ligature_present = TRUE;            \
  517.         break;                        \
  518.     case 2: case 6:                        \
  519.         cur_r = rem_byte(q);                \
  520.         if (lig_stack != null) {            \
  521.             character(lig_stack) = cur_r;        \
  522.         } else {                    \
  523.             lig_stack = new_lig_item(cur_r);    \
  524.             if (j == n) {                \
  525.                 bchar = NON_CHAR;        \
  526.             } else {                \
  527.                 p = new_avail();        \
  528.                 lig_ptr(lig_stack) = p;        \
  529.                 character(p) = hu[j + 1];    \
  530.                 font(p) = hf;            \
  531.             }                    \
  532.         }                        \
  533.         break;                        \
  534.     case 3:                            \
  535.         cur_r = rem_byte(q);                \
  536.         p = lig_stack;                    \
  537.         lig_stack = new_lig_item(cur_r);        \
  538.         link(lig_stack) = p;                \
  539.         break;                        \
  540.     case 7: case 11:                    \
  541.         wrap_lig(FALSE);                \
  542.         cur_q = t;                    \
  543.         cur_l = rem_byte(q);                \
  544.         ligature_present = TRUE;            \
  545.         break;                        \
  546.     default:                        \
  547.         cur_l = rem_byte(q);                \
  548.         ligature_present = TRUE;            \
  549.         if (lig_stack != null) {            \
  550.             pop_lig_stack();            \
  551.         } else if (j == n) {                \
  552.             goto done;                \
  553.         } else {                    \
  554.             append_charnode_to_t(cur_r);        \
  555.             incr(j);                \
  556.             set_cur_r();                \
  557.         }                        \
  558.         break;                        \
  559.     }                            \
  560.     if (op_byte(q) > 4 && op_byte(q) != 7) {        \
  561.         goto done;                    \
  562.     }                            \
  563.     goto contin;                        \
  564. }
  565.  
  566.  
  567. int
  568. reconstitute (j, n, bchar, hchar)
  569.     int    j, n, bchar, hchar;
  570. {
  571.     scal    w;
  572.     qcell    *k, q;
  573.     ptr    p, t;
  574.     int    cur_rh;
  575.     int    test_char;
  576.     
  577.     hyphen_passed = 0;
  578.     t = hold_head;
  579.     link(hold_head) = null;
  580.     w = 0;
  581.     cur_l = hu[j];
  582.     cur_q = t;
  583.     if (j == 0) {
  584.         ligature_present = init_lig;
  585.         p = init_list;
  586.         if (ligature_present)
  587.             lft_hit = init_lft;
  588.         while (p != null) {
  589.             append_charnode_to_t(character(p));
  590.             p = link(p);
  591.         }
  592.     } else if (cur_l < NON_CHAR) {
  593.         append_charnode_to_t(cur_l);
  594.     }
  595.     lig_stack = null;
  596.     set_cur_r();
  597.  
  598. contin:
  599.     if (cur_l == NON_CHAR) {
  600.         k = bchar_label(hf);
  601.         if (k == NON_ADDRESS) {
  602.             goto done;
  603.         } else {
  604.             q = *k;
  605.         }
  606.     } else {
  607.         q = char_info(hf, cur_l);
  608.         if (char_tag(q) != LIG_TAG)
  609.             goto done;
  610.         k = lig_kern_start(hf, q);
  611.         q = *k;
  612.         if (skip_byte(q) > STOP_FLAG) {
  613.             k = lig_kern_restart(hf, q);
  614.             q = *k;
  615.         }
  616.     }
  617.     test_char = (cur_rh < NON_CHAR) ? cur_rh : cur_r;
  618.     loop {
  619.         if (next_char(q) == test_char
  620.         && skip_byte(q) <= STOP_FLAG) {
  621.             if (cur_rh < NON_CHAR) {
  622.                 hyphen_passed = j;
  623.                 hchar = NON_CHAR;
  624.                 cur_rh = NON_CHAR;
  625.                 goto contin;
  626.             } else {
  627.                 if (hchar < NON_CHAR && odd(hyf[j])) {
  628.                     hyphen_passed = j;
  629.                     hchar = NON_CHAR;
  630.                 }
  631.                 if (op_byte(q) < KERN_FLAG) {
  632.                     lig_replace();
  633.                 }
  634.                 w = char_kern(hf, q);
  635.                 goto done;
  636.             }
  637.         }
  638.         if (skip_byte(q) >= STOP_FLAG) {
  639.             if (cur_rh == NON_CHAR) {
  640.                 goto done;
  641.             } else {
  642.                 cur_rh = NON_CHAR;
  643.                 goto contin;
  644.             }
  645.         }
  646.         k += skip_byte(q) + 1;
  647.         q = *k;
  648.     }
  649. done:
  650.     wrap_lig(rt_hit);
  651.     if (w != 0) {
  652.         t = link(t) = new_kern(w);
  653.         w = 0;
  654.     }
  655.     if (lig_stack != null) {
  656.         cur_q = t;
  657.         cur_l = character(lig_stack);
  658.         ligature_present = TRUE;
  659.         pop_lig_stack();
  660.         goto contin;
  661.     }
  662.     return j;
  663. }
  664.  
  665. #define set_cur_lang() \
  666.     {cur_lang = (language <= 0 || language > 255) ? 0 : language;}
  667.  
  668. void
  669. new_hyph_exceptions ()
  670. {
  671.     ptr    p, q;
  672.  
  673.     scan_left_brace();
  674.     set_cur_lang();
  675.     hn = 0;
  676.     p = null;
  677.     loop {
  678.         get_x_token();
  679.  
  680.     reswitch:
  681.         switch (cur_cmd)
  682.         {
  683.         case LETTER:
  684.         case OTHER_CHAR:
  685.         case CHAR_GIVEN:
  686.             if (cur_chr == '-') {
  687.                 if (hn < 63) {
  688.                     q = new_avail();
  689.                     link(q) = p;
  690.                     info(q) = hn;
  691.                     p = q;
  692.                 }
  693.             } else {
  694.                 if (lc_code(cur_chr) == 0) {
  695.                     print_err("Not a letter");
  696.                     help_hyph_lccode();
  697.                     error();
  698.                 } else if (hn < 63) {
  699.                     incr(hn);
  700.                     hc[hn] = lc_code(cur_chr);
  701.                 }
  702.             }
  703.             break;
  704.         
  705.         case CHAR_NUM:
  706.             scan_char_num();
  707.             cur_chr = cur_val;
  708.             cur_cmd = CHAR_GIVEN;
  709.             goto reswitch;
  710.  
  711.         case SPACER:
  712.         case RIGHT_BRACE:
  713.             if (hn > 1)
  714.                 enter_hyph_exception(p);
  715.             if (cur_cmd == RIGHT_BRACE)
  716.                 return;
  717.             hn = 0;
  718.             p = null;
  719.             break;
  720.  
  721.         default:
  722.             print_err("Improper ");
  723.             print_esc("hyphenation");
  724.             print(" will be flushed");
  725.             help_hyph();
  726.             error();
  727.             break;
  728.         }
  729.     }
  730. }
  731.  
  732. void
  733. enter_hyph_exception (p)
  734.     ptr    p;
  735. {
  736.     ptr    q;
  737.     int    h, j, l, m;
  738.     str     s, t, u, v, w;
  739.  
  740.     incr(hn);
  741.     hc[hn] = cur_lang;
  742.     str_room(hn);
  743.     h = 0;
  744.     for (j = 1; j <= hn; incr(j)) {
  745.         h = (h + h + hc[j]) % HYPH_SIZE;
  746.         append_char(hc[j]);
  747.     }
  748.     l = cur_length();
  749.     s = make_str();
  750.     if (hyph_count == HYPH_SIZE)
  751.         overflow("exception dictionary", HYPH_SIZE);
  752.     incr(hyph_count);
  753.     while (hyph_word[h] != null_str) {
  754.         w = hyph_word[h];
  755.         m = hyph_len[h];
  756.         if (m < l)
  757.             goto found;
  758.         if (m > l)
  759.             goto not_found;
  760.         u = w;
  761.         v = s;
  762.         while (m--) {
  763.             if (*u < *v)
  764.                 goto found;
  765.             if (*u > *v)
  766.                 goto not_found;
  767.             incr(u);
  768.             incr(v);
  769.         }
  770.  
  771.     found:
  772.         q = hyph_list[h];
  773.         hyph_list[h] = p;
  774.         p = q;
  775.         t = hyph_word[h];
  776.         hyph_word[h] = s;
  777.         s = t;
  778.         m = hyph_len[h];
  779.         hyph_len[h] = l;
  780.         l = m;
  781.     
  782.     not_found:
  783.         if (h > 0) {
  784.             decr(h);
  785.         } else {
  786.             h = HYPH_SIZE;
  787.         }
  788.     }
  789.     hyph_word[h] = s;
  790.     hyph_len[h] = l;
  791.     hyph_list[h] = p;
  792. }
  793.  
  794. void
  795. new_patterns ()
  796. {
  797.     int    c, k, l, p, q, v;
  798.     bool    first_child;
  799.     bool    digit_sensed;
  800.  
  801.     if (trie_not_ready == FALSE) {
  802.         print_err("Too late for ");
  803.         print_esc("patterns");
  804.         help_patterns();
  805.         error();
  806.         scan_toks(FALSE, FALSE);
  807.         flush_list(def_ref);
  808.         return;
  809.     }
  810.     set_cur_lang();
  811.     scan_left_brace();
  812.     k = hyf[0] = 0;
  813.     digit_sensed = FALSE;
  814.     loop {
  815.         get_x_token();
  816.         switch (cur_cmd)
  817.         {
  818.         case LETTER:
  819.         case OTHER_CHAR:
  820.             if (digit_sensed || cur_chr < '0' || cur_chr > '9') {
  821.                 if (cur_chr == '.') {
  822.                     cur_chr = 0;
  823.                 } else {
  824.                     cur_chr = lc_code(cur_chr);
  825.                     if (cur_chr == 0) {
  826.                         print_err("Nonletter");
  827.                         help1("(See Appendix H.)");
  828.                         error();
  829.                     }
  830.                 }
  831.                 if (k < 63) {
  832.                     incr(k);
  833.                     hc[k] = cur_chr;
  834.                     hyf[k] = 0;
  835.                     digit_sensed = FALSE;
  836.                 }
  837.             } else if (k < 63){
  838.                 hyf[k] = cur_chr - '0';
  839.                 digit_sensed = TRUE;
  840.             }
  841.             break;
  842.  
  843.         case SPACER:
  844.         case RIGHT_BRACE:
  845.             if (k == 0) {
  846.                 if (cur_cmd == RIGHT_BRACE)
  847.                     goto done;
  848.                 break;
  849.             }
  850.             if (hc[1] == 0)
  851.                 hyf[0] = 0;
  852.             if (hc[k] == 0)
  853.                 hyf[k] = 0;
  854.             v = 0;
  855.             l = k;
  856.             loop {
  857.                 if (hyf[l])
  858.                     v = new_trie_op(k - l, hyf[l], v);
  859.                 if (l > 0) {
  860.                     decr(l);
  861.                 } else {
  862.                     break;
  863.                 }
  864.             }
  865.             q = 0; 
  866.             hc[0] = cur_lang;
  867.             while (l <= k) {
  868.                 c = hc[l];
  869.                 incr(l);
  870.                 p = trie_l[q];
  871.                 first_child = TRUE;
  872.                 while (p > 0 && c > trie_c[p]) {
  873.                     q = p;
  874.                     p = trie_r[q];
  875.                     first_child = FALSE;
  876.                 }
  877.                 if (p == 0 || c < trie_c[p]) {
  878.                     check_trie_ptr();
  879.                     incr(trie_ptr);
  880.                     trie_r[trie_ptr] = p;
  881.                     p = trie_ptr;
  882.                     trie_l[p] = 0;
  883.                     if (first_child) {
  884.                         trie_l[q] = p;
  885.                     } else {
  886.                         trie_r[q] = p;
  887.                     }
  888.                     trie_c[p] = c;
  889.                     trie_o[p] = 0;
  890.                 }
  891.                 q = p;
  892.             }
  893.             if (trie_o[q]) {
  894.                 print_err("Duplicate pattern");
  895.                 help1("(See Appendix H.)");
  896.                 error();
  897.             }
  898.             trie_o[q] = v;
  899.             if (cur_cmd == RIGHT_BRACE)
  900.                 goto done;
  901.             k = hyf[0] = 0;
  902.             digit_sensed = FALSE;
  903.             if (cur_cmd == RIGHT_BRACE)
  904.                 goto done;
  905.             break;
  906.  
  907.         default:
  908.             print_err("Bad ");
  909.             print_esc("patterns");
  910.             help1("(See Appendix H.)");
  911.             error();
  912.             break;
  913.         }
  914.     }
  915. done:
  916.     return;
  917. }
  918.  
  919. check_trie_ptr ()
  920. {
  921.     if (trie_ptr == TRIE_SIZE) {
  922.         overflow("pattern memory", TRIE_SIZE);
  923.     }
  924. }
  925.  
  926. void
  927. init_trie ()
  928. {
  929.     int    j, k, p, r, s, t;
  930.     trie_t    z;
  931.  
  932.     op_start[0] = 0;
  933.     for (j = 1; j <= 255; incr(j))
  934.         op_start[j] = op_start[j - 1] + trie_op_used[j - 1];
  935.     for (j = 1; j <= trie_op_ptr; incr(j))
  936.         trie_op_hash[j] = op_start[trie_op_lang[j]] + trie_op_val[j];
  937.     for (j = 1; j <= trie_op_ptr; incr(j)) {
  938.         while (trie_op_hash[j] > j) {
  939.             k = trie_op_hash[j];
  940.             t = hyf_distance[k];
  941.             hyf_distance[k] = hyf_distance[j];
  942.             hyf_distance[j] = t;
  943.             t = hyf_num[k];
  944.             hyf_num[k] = hyf_num[j];
  945.             hyf_num[j] = t;
  946.             t = hyf_next[k];
  947.             hyf_next[k] = hyf_next[j];
  948.             hyf_next[j] = t;
  949.             trie_op_hash[j] = trie_op_hash[k];
  950.             trie_op_hash[k] = k;
  951.         }
  952.     }
  953.     for (p = 0; p <= TRIE_SIZE; incr(p))
  954.         trie_hash[p] = 0;
  955.     trie_root = trie_compress(trie_root);
  956.     for (p = 0; p <= trie_ptr; incr(p))
  957.         trie_ref[p] = 0;
  958.     for (p = 0; p <= 255; incr(p))
  959.         trie_min[p] = p + 1;
  960.     trie_link(0) = 1;
  961.     trie_max = 0;
  962.     if (trie_root != 0) {
  963.         first_fit(trie_root);
  964.         trie_pack(trie_root);
  965.     }
  966.     z.s = 0;
  967.     z.u_s.bb.b0 = z.u_s.bb.b1 = 0;
  968.     if (trie_root == 0) {
  969.         for (r = 0; r <= 256; incr(r))
  970.             trie[r] = z;
  971.         trie_max = 256;
  972.     } else {
  973.         trie_fix(trie_root);
  974.         for (r = 0; r <= trie_max; r = s) {
  975.             s = trie_link(r);
  976.             trie[r] = z;
  977.         }
  978.     }
  979.     trie_char(0) = '?';
  980.     trie_not_ready = FALSE;
  981.     free_pattern_memory();
  982. }
  983.  
  984. int
  985. new_trie_op (d, n, v)
  986.     int    d;
  987.     int    n;
  988.     int    v;
  989. {
  990.     int    h;
  991.     int    u;
  992.     int    l;
  993.  
  994.     h = abs(n + 313 * d + 361 * v + 1009 * cur_lang);
  995.     h = h % (TRIE_OP_SIZE + TRIE_OP_SIZE) - TRIE_OP_SIZE;
  996.     loop {
  997.         l = trie_op_hash[h];
  998.         if (l == 0) {
  999.             if (trie_op_ptr == TRIE_OP_SIZE) {
  1000.                 overflow("pattern memory ops", TRIE_OP_SIZE);
  1001.             }
  1002.             u = trie_op_used[cur_lang];
  1003.             if (u == MAX_TRIE_OPS_PER_LANG) {
  1004.                 overflow("pattern memory ops per language",
  1005.                     MAX_TRIE_OPS_PER_LANG);
  1006.             }
  1007.             incr(u);
  1008.             trie_op_used[cur_lang] = u;
  1009.             incr(trie_op_ptr);
  1010.             hyf_distance[trie_op_ptr] = d;
  1011.             hyf_num[trie_op_ptr] = n;
  1012.             hyf_next[trie_op_ptr] = v;
  1013.             trie_op_lang[trie_op_ptr] = cur_lang;
  1014.             trie_op_val[trie_op_ptr] = u;
  1015.             trie_op_hash[h] = trie_op_ptr;
  1016.             return u;
  1017.         }
  1018.         if (hyf_distance[l] == d
  1019.         && hyf_num[l] == n
  1020.         && hyf_next[l] == v
  1021.         && trie_op_lang[l] == cur_lang) {
  1022.             return (trie_op_val[l]);
  1023.         }
  1024.         if (h > -TRIE_OP_SIZE) {
  1025.             decr(h);
  1026.         } else {
  1027.             h = TRIE_OP_SIZE;
  1028.         }
  1029.     }
  1030. }
  1031.  
  1032. int
  1033. trie_compress (p)
  1034.     int    p;
  1035. {
  1036.     if (p == 0)
  1037.         return 0;
  1038.     trie_l[p] = trie_compress(trie_l[p]);
  1039.     trie_r[p] = trie_compress(trie_r[p]);
  1040.     return (trie_node(p));
  1041. }
  1042.         
  1043. int
  1044. trie_node (p)
  1045.     int    p;
  1046. {
  1047.     int    h;
  1048.     int    q;
  1049.  
  1050.     h = trie_c[p] + 1009 * trie_o[p] +
  1051.         2718 * trie_l[p] + 3142 * trie_r[p];
  1052.     h = abs(h) % TRIE_SIZE;
  1053.     loop {
  1054.         q = trie_hash[h];
  1055.         if (q == 0) {
  1056.             trie_hash[h] = p; 
  1057.             return p;
  1058.         }
  1059.         if (trie_c[q] == trie_c[p]
  1060.         && trie_o[q] == trie_o[p]
  1061.         && trie_l[q] == trie_l[p]
  1062.         && trie_r[q] == trie_r[p])
  1063.             return q;
  1064.         if (h > 0) {
  1065.             decr(h);
  1066.         } else {
  1067.             h = TRIE_SIZE;
  1068.         }
  1069.     }
  1070. }
  1071.  
  1072. void
  1073. trie_pack (p)
  1074.     int    p;
  1075. {
  1076.     int    q;
  1077.  
  1078.     do {
  1079.         q = trie_l[p];
  1080.         if (q > 0 && trie_ref[q] == 0) {
  1081.             first_fit(q);
  1082.             trie_pack(q);
  1083.         }
  1084.         p = trie_r[p];
  1085.     } while (p);
  1086. }
  1087.  
  1088. void
  1089. first_fit (p)
  1090.     int    p;
  1091. {
  1092.     int    c, h, l, r, ll, q, z;
  1093.  
  1094.     c = trie_c[p];
  1095.     z = trie_min[c];
  1096.     loop {
  1097.         h = z - c;
  1098.         if (trie_max < h + 256) {
  1099.             if (TRIE_SIZE <= h + 256)
  1100.                 overflow("pattern memory", TRIE_SIZE);
  1101.             while (trie_max != h + 256) {
  1102.                 incr(trie_max); 
  1103.                 trie_taken[trie_max] = FALSE;
  1104.                 trie_link(trie_max) = trie_max + 1;
  1105.                 trie_back(trie_max) = trie_max - 1;
  1106.             }
  1107.         }
  1108.         if (trie_taken[h])
  1109.             goto not_found;
  1110.         for (q = trie_r[p]; q > 0; q = trie_r[q])
  1111.             if (trie_link(h + trie_c[q]) == 0)
  1112.                 goto not_found;
  1113.         goto found;
  1114.  
  1115.     not_found:
  1116.         z = trie_link(z);
  1117.     }
  1118.  
  1119. found:
  1120.     trie_taken[h] = TRUE;
  1121.     trie_ref[p] = h;
  1122.     for (q = p; q > 0; q = trie_r[q]) {
  1123.         z = h + trie_c[q];
  1124.         l = trie_back(z);
  1125.         r = trie_link(z);
  1126.         trie_back(r) = l;
  1127.         trie_link(l) = r;
  1128.         trie_link(z) = 0;
  1129.         if (l < 256) {
  1130.             ll = (z < 256) ? z : 256;
  1131.             while (l != ll) {
  1132.                 trie_min[l] = r;
  1133.                 incr(l);
  1134.             }
  1135.         }
  1136.     }
  1137. }
  1138.  
  1139. void
  1140. trie_fix (p)
  1141.     int    p;
  1142. {
  1143.     int    c;
  1144.     int    q;
  1145.     int    z;
  1146.  
  1147.     z = trie_ref[p];
  1148.     while (p) {
  1149.         q = trie_l[p];
  1150.         c = trie_c[p];
  1151.         trie_link(z + c) = trie_ref[q];
  1152.         trie_char(z + c) = c;
  1153.         trie_op(z + c) = trie_o[p];
  1154.         if (q > 0)
  1155.             trie_fix(q);
  1156.         p = trie_r[p];
  1157.     }
  1158. }
  1159.  
  1160. void
  1161. init_pattern_memory ()
  1162. {
  1163.     int    l;
  1164.     int    p;
  1165.  
  1166.     l = TRIE_OP_SIZE + 1;
  1167.     trie_op_hash = (int *) malloc ((l+l)*sizeof(int));
  1168.     trie_op_hash += l;
  1169.     trie_op_val = (int *) malloc (l*sizeof(int));
  1170.     trie_op_lang = (int *) malloc (l*sizeof(int));
  1171.     trie_op_used = (int *) malloc (256*sizeof(int));
  1172.     for (p = -TRIE_OP_SIZE; p <= TRIE_OP_SIZE; incr(p))
  1173.         trie_op_hash[p] = 0;
  1174.     for (p = 0; p <= 255; incr(p))
  1175.         trie_op_used[p] = 0;
  1176.     trie_op_ptr = 0;
  1177.  
  1178.     l = TRIE_SIZE + 1;
  1179.     trie_hash = (int *) malloc (l*sizeof(int));
  1180.     trie_taken = (bool *) malloc (l*sizeof(bool));
  1181.     trie_c = (int *) malloc (l*sizeof(int));
  1182.     trie_o = (int *) malloc (l*sizeof(int));
  1183.     trie_l = (int *) malloc (l*sizeof(int));
  1184.     trie_r = (int *) malloc (l*sizeof(int));
  1185.     trie_min = (int *) malloc(256*sizeof(int));
  1186.     trie_root = 0;
  1187.     trie_c[0] = 0;
  1188.     trie_ptr = 0;
  1189. }
  1190.  
  1191. void
  1192. free_pattern_memory ()
  1193. {
  1194.     free(trie_op_hash - TRIE_OP_SIZE - 1);
  1195.     free(trie_op_used);
  1196.     free(trie_op_val);
  1197.     free(trie_op_lang);
  1198.     free(trie_hash);
  1199.     free(trie_taken);
  1200.     free(trie_min);
  1201.     free(trie_c);
  1202.     free(trie_o);
  1203.     free(trie_l);
  1204.     free(trie_r);
  1205. }
  1206.  
  1207. void
  1208. _hyph_init ()
  1209. {
  1210. }
  1211.  
  1212. void
  1213. _hyph_init_once ()
  1214. {
  1215.     int    k;
  1216.  
  1217.     init_pattern_memory();
  1218.     trie = (trie_t *)malloc((TRIE_SIZE+1)*sizeof(trie_t));
  1219.     op_start = (int *)malloc(256*sizeof(int));
  1220.     hyf_distance = (int *)malloc((TRIE_OP_SIZE+1)*sizeof(int));
  1221.     hyf_num = (int *)malloc((TRIE_OP_SIZE+1)*sizeof(int));
  1222.     hyf_next = (int *)malloc((TRIE_OP_SIZE+1)*sizeof(int));
  1223.     hyph_word = (str *)malloc((HYPH_SIZE+1)*sizeof(str));
  1224.     hyph_len = (int *)malloc((HYPH_SIZE+1)*sizeof(int));
  1225.     hyph_list = (ptr *)malloc((HYPH_SIZE+1)*sizeof(ptr));
  1226.     for (k = 0; k <= HYPH_SIZE; incr(k)) {
  1227.         hyph_word[k] = null_str;
  1228.         hyph_list[k] = null;
  1229.     }
  1230.     hyph_count = 0;
  1231.     trie_not_ready = TRUE;
  1232. }
  1233.  
  1234. /*
  1235. **    Help text
  1236. */
  1237.  
  1238. help_patterns ()
  1239. {
  1240.     help1("All patterns must be given before typesetting begins.");
  1241. }
  1242.  
  1243. help_hyph_lccode ()
  1244. {
  1245.     help2("Letters in \\hyphenation words must have \\lccode > 0",
  1246.     "Proceed; I'll ignore the character I just read.");
  1247. }
  1248.  
  1249. help_hyph ()
  1250. {
  1251.     help2("Hyphenation exceptions must contain only letters",
  1252.     "and hyphens. But continue; I'll forgive and forget.");
  1253. }
  1254.  
  1255.