Issue #1538 - remove speech recognition engine

This removes speech recognition, pocketsphinx, training models
and the speech automated test interface.
This also re-establishes proper use of MOZ_WEBSPEECH to work
for the speech API (synthesis part only) that was a broken mess
before, with some synth parts being always built, some parts
being built only with it enabled and recognition parts being
dependent on it. I'm pretty sure it'd be totally busted if you'd
ever have tried building without MOZ_WEBPEECH before.

Tested that synthesis still works as-intended.

This resolves #1538

1 files changed, 0 insertions, 1550 deletions

diff --git a/media/pocketsphinx/src/fsg_search.c b/media/pocketsphinx/src/fsg_search.c
deleted file mode 100644
index f24a0fb83..000000000
--- a/media/pocketsphinx/src/fsg_search.c
+++ /dev/null
@@ -1,1550 +0,0 @@
-/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
-/* ====================================================================
- * Copyright (c) 1999-2004 Carnegie Mellon University.  All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer. 
- *
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in
- *    the documentation and/or other materials provided with the
- *    distribution.
- *
- *
- * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND 
- * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 
- * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
- * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * ====================================================================
- *
- */
-
-/*
- * fsg_search.c -- Search structures for FSM decoding.
- * 
- * **********************************************
- * CMU ARPA Speech Project
- *
- * Copyright (c) 2004 Carnegie Mellon University.
- * ALL RIGHTS RESERVED.
- * **********************************************
- * 
- * HISTORY
- *
- * 18-Feb-2004	M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon
- * 		Started.
- */
-
-/* System headers. */
-#include <stdio.h>
-#include <string.h>
-#include <assert.h>
-
-/* SphinxBase headers. */
-#include <sphinxbase/err.h>
-#include <sphinxbase/ckd_alloc.h>
-#include <sphinxbase/strfuncs.h>
-#include <sphinxbase/cmd_ln.h>
-
-/* Local headers. */
-#include "pocketsphinx_internal.h"
-#include "ps_lattice_internal.h"
-#include "fsg_search_internal.h"
-#include "fsg_history.h"
-#include "fsg_lextree.h"
-#include "dict.h"
-
-/* Turn this on for detailed debugging dump */
-#define __FSG_DBG__		0
-#define __FSG_DBG_CHAN__	0
-
-static ps_seg_t *fsg_search_seg_iter(ps_search_t *search, int32 *out_score);
-static ps_lattice_t *fsg_search_lattice(ps_search_t *search);
-static int fsg_search_prob(ps_search_t *search);
-
-static ps_searchfuncs_t fsg_funcs = {
-    /* name: */   "fsg",
-    /* start: */  fsg_search_start,
-    /* step: */   fsg_search_step,
-    /* finish: */ fsg_search_finish,
-    /* reinit: */ fsg_search_reinit,
-    /* free: */   fsg_search_free,
-    /* lattice: */  fsg_search_lattice,
-    /* hyp: */      fsg_search_hyp,
-    /* prob: */     fsg_search_prob,
-    /* seg_iter: */ fsg_search_seg_iter,
-};
-
-static int
-fsg_search_add_silences(fsg_search_t *fsgs, fsg_model_t *fsg)
-{
-    dict_t *dict;
-    int32 wid;
-    int n_sil;
-
-    dict = ps_search_dict(fsgs);
-    /*
-     * NOTE: Unlike N-Gram search, we do not use explicit start and
-     * end symbols.  This is because the start and end nodes are
-     * defined in the grammar.  We do add silence/filler self-loops to
-     * all states in order to allow for silence between words and at
-     * the beginning and end of utterances.
-     *
-     * This has some implications for word graph generation, namely,
-     * that there can (and usually will) be multiple start and end
-     * states in the word graph.  We therefore do add explicit start
-     * and end nodes to the graph.
-     */
-    /* Add silence self-loops to all states. */
-    fsg_model_add_silence(fsg, "<sil>", -1,
-                          cmd_ln_float32_r(ps_search_config(fsgs), "-silprob"));
-    n_sil = 0;
-    /* Add self-loops for all other fillers. */
-    for (wid = dict_filler_start(dict); wid < dict_filler_end(dict); ++wid) {
-        char const *word = dict_wordstr(dict, wid);
-        if (wid == dict_startwid(dict) || wid == dict_finishwid(dict))
-            continue;
-        fsg_model_add_silence(fsg, word, -1,
-                              cmd_ln_float32_r(ps_search_config(fsgs), "-fillprob"));
-        ++n_sil;
-    }
-
-    return n_sil;
-}
-
-/* Scans the dictionary and check if all words are present. */
-static int
-fsg_search_check_dict(fsg_search_t *fsgs, fsg_model_t *fsg)
-{
-    dict_t *dict;
-    int i;
-
-    dict = ps_search_dict(fsgs);
-    for (i = 0; i < fsg_model_n_word(fsg); ++i) {
-        char const *word;
-        int32 wid;
-
-        word = fsg_model_word_str(fsg, i);
-        wid = dict_wordid(dict, word);
-        if (wid == BAD_S3WID) {
-            E_WARN("The word '%s' is missing in the dictionary. Trying to create new phoneme \n", word);
-            if (!dict->ngram_g2p_model) {
-                E_ERROR("NO dict->ngram_g2p_model. Aborting..");
-                return FALSE;
-            }
-
-            int new_wid = dict_add_g2p_word(dict, word);
-            if (new_wid > 0){
-                /* Now we also have to add it to dict2pid. */
-                dict2pid_add_word(ps_search_dict2pid(fsgs), new_wid);
-            } else {
-                E_ERROR("Exiting... \n");
-                return FALSE;
-            }
-        }
-    }
-
-    return TRUE;
-}
-
-static int
-fsg_search_add_altpron(fsg_search_t *fsgs, fsg_model_t *fsg)
-{
-    dict_t *dict;
-    int n_alt, n_word;
-    int i;
-
-    dict = ps_search_dict(fsgs);
-    /* Scan FSG's vocabulary for words that have alternate pronunciations. */
-    n_alt = 0;
-    n_word = fsg_model_n_word(fsg);
-    for (i = 0; i < n_word; ++i) {
-        char const *word;
-        int32 wid;
-
-        word = fsg_model_word_str(fsg, i);
-        wid = dict_wordid(dict, word);
-        if (wid != BAD_S3WID) {
-            while ((wid = dict_nextalt(dict, wid)) != BAD_S3WID) {
-	        n_alt += fsg_model_add_alt(fsg, word, dict_wordstr(dict, wid));
-    	    }
-    	}
-    }
-
-    E_INFO("Added %d alternate word transitions\n", n_alt);
-    return n_alt;
-}
-
-ps_search_t *
-fsg_search_init(fsg_model_t *fsg,
-                cmd_ln_t *config,
-                acmod_t *acmod,
-                dict_t *dict,
-                dict2pid_t *d2p)
-{
-    fsg_search_t *fsgs = ckd_calloc(1, sizeof(*fsgs));
-    ps_search_init(ps_search_base(fsgs), &fsg_funcs, config, acmod, dict, d2p);
-
-    fsgs->fsg = fsg_model_retain(fsg);
-    /* Initialize HMM context. */
-    fsgs->hmmctx = hmm_context_init(bin_mdef_n_emit_state(acmod->mdef),
-                                    acmod->tmat->tp, NULL, acmod->mdef->sseq);
-    if (fsgs->hmmctx == NULL) {
-        ps_search_free(ps_search_base(fsgs));
-        return NULL;
-    }
-
-    /* Intialize the search history object */
-    fsgs->history = fsg_history_init(NULL, dict);
-    fsgs->frame = -1;
-
-    /* Get search pruning parameters */
-    fsgs->beam_factor = 1.0f;
-    fsgs->beam = fsgs->beam_orig
-        = (int32) logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-beam"))
-        >> SENSCR_SHIFT;
-    fsgs->pbeam = fsgs->pbeam_orig
-        = (int32) logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-pbeam"))
-        >> SENSCR_SHIFT;
-    fsgs->wbeam = fsgs->wbeam_orig
-        = (int32) logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-wbeam"))
-        >> SENSCR_SHIFT;
-
-    /* LM related weights/penalties */
-    fsgs->lw = cmd_ln_float32_r(config, "-lw");
-    fsgs->pip = (int32) (logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-pip"))
-                           * fsgs->lw)
-        >> SENSCR_SHIFT;
-    fsgs->wip = (int32) (logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-wip"))
-                           * fsgs->lw)
-        >> SENSCR_SHIFT;
-
-    /* Acoustic score scale for posterior probabilities. */
-    fsgs->ascale = 1.0 / cmd_ln_float32_r(config, "-ascale");
-
-    E_INFO("FSG(beam: %d, pbeam: %d, wbeam: %d; wip: %d, pip: %d)\n",
-           fsgs->beam_orig, fsgs->pbeam_orig, fsgs->wbeam_orig,
-           fsgs->wip, fsgs->pip);
-
-    if (!fsg_search_check_dict(fsgs, fsg)) {
-        fsg_search_free(ps_search_base(fsgs));
-        return NULL;
-    }
-
-    if (cmd_ln_boolean_r(config, "-fsgusefiller") &&
-        !fsg_model_has_sil(fsg))
-        fsg_search_add_silences(fsgs, fsg);
-
-    if (cmd_ln_boolean_r(config, "-fsgusealtpron") &&
-        !fsg_model_has_alt(fsg))
-        fsg_search_add_altpron(fsgs, fsg);
-
-    if (fsg_search_reinit(ps_search_base(fsgs),
-                          ps_search_dict(fsgs),
-                          ps_search_dict2pid(fsgs)) < 0)
-    {
-        ps_search_free(ps_search_base(fsgs));
-        return NULL;
-    }
-        
-    return ps_search_base(fsgs);
-}
-
-void
-fsg_search_free(ps_search_t *search)
-{
-    fsg_search_t *fsgs = (fsg_search_t *)search;
-
-    ps_search_deinit(search);
-    fsg_lextree_free(fsgs->lextree);
-    if (fsgs->history) {
-        fsg_history_reset(fsgs->history);
-        fsg_history_set_fsg(fsgs->history, NULL, NULL);
-        fsg_history_free(fsgs->history);
-    }
-    hmm_context_free(fsgs->hmmctx);
-    fsg_model_free(fsgs->fsg);
-    ckd_free(fsgs);
-}
-
-int
-fsg_search_reinit(ps_search_t *search, dict_t *dict, dict2pid_t *d2p)
-{
-    fsg_search_t *fsgs = (fsg_search_t *)search;
-
-    /* Free the old lextree */
-    if (fsgs->lextree)
-        fsg_lextree_free(fsgs->lextree);
-
-    /* Free old dict2pid, dict */
-    ps_search_base_reinit(search, dict, d2p);
-    
-    /* Update the number of words (not used by this module though). */
-    search->n_words = dict_size(dict);
-
-    /* Allocate new lextree for the given FSG */
-    fsgs->lextree = fsg_lextree_init(fsgs->fsg, dict, d2p,
-                                     ps_search_acmod(fsgs)->mdef,
-                                     fsgs->hmmctx, fsgs->wip, fsgs->pip);
-
-    /* Inform the history module of the new fsg */
-    fsg_history_set_fsg(fsgs->history, fsgs->fsg, dict);
-
-    return 0;
-}
-
-
-static void
-fsg_search_sen_active(fsg_search_t *fsgs)
-{
-    gnode_t *gn;
-    fsg_pnode_t *pnode;
-    hmm_t *hmm;
-
-    acmod_clear_active(ps_search_acmod(fsgs));
-
-    for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
-        pnode = (fsg_pnode_t *) gnode_ptr(gn);
-        hmm = fsg_pnode_hmmptr(pnode);
-        assert(hmm_frame(hmm) == fsgs->frame);
-        acmod_activate_hmm(ps_search_acmod(fsgs), hmm);
-    }
-}
-
-
-/*
- * Evaluate all the active HMMs.
- * (Executed once per frame.)
- */
-static void
-fsg_search_hmm_eval(fsg_search_t *fsgs)
-{
-    gnode_t *gn;
-    fsg_pnode_t *pnode;
-    hmm_t *hmm;
-    int32 bestscore;
-    int32 n, maxhmmpf;
-
-    bestscore = WORST_SCORE;
-
-    if (!fsgs->pnode_active) {
-        E_ERROR("Frame %d: No active HMM!!\n", fsgs->frame);
-        return;
-    }
-
-    for (n = 0, gn = fsgs->pnode_active; gn; gn = gnode_next(gn), n++) {
-        int32 score;
-
-        pnode = (fsg_pnode_t *) gnode_ptr(gn);
-        hmm = fsg_pnode_hmmptr(pnode);
-        assert(hmm_frame(hmm) == fsgs->frame);
-
-#if __FSG_DBG__
-        E_INFO("pnode(%08x) active @frm %5d\n", (int32) pnode,
-               fsgs->frame);
-        hmm_dump(hmm, stdout);
-#endif
-        score = hmm_vit_eval(hmm);
-#if __FSG_DBG_CHAN__
-        E_INFO("pnode(%08x) after eval @frm %5d\n",
-               (int32) pnode, fsgs->frame);
-        hmm_dump(hmm, stdout);
-#endif
-
-        if (score BETTER_THAN bestscore)
-            bestscore = score;
-    }
-
-#if __FSG_DBG__
-    E_INFO("[%5d] %6d HMM; bestscr: %11d\n", fsgs->frame, n, bestscore);
-#endif
-    fsgs->n_hmm_eval += n;
-
-    /* Adjust beams if #active HMMs larger than absolute threshold */
-    maxhmmpf = cmd_ln_int32_r(ps_search_config(fsgs), "-maxhmmpf");
-    if (maxhmmpf != -1 && n > maxhmmpf) {
-        /*
-         * Too many HMMs active; reduce the beam factor applied to the default
-         * beams, but not if the factor is already at a floor (0.1).
-         */
-        if (fsgs->beam_factor > 0.1) {        /* Hack!!  Hardwired constant 0.1 */
-            fsgs->beam_factor *= 0.9f;        /* Hack!!  Hardwired constant 0.9 */
-            fsgs->beam =
-                (int32) (fsgs->beam_orig * fsgs->beam_factor);
-            fsgs->pbeam =
-                (int32) (fsgs->pbeam_orig * fsgs->beam_factor);
-            fsgs->wbeam =
-                (int32) (fsgs->wbeam_orig * fsgs->beam_factor);
-        }
-    }
-    else {
-        fsgs->beam_factor = 1.0f;
-        fsgs->beam = fsgs->beam_orig;
-        fsgs->pbeam = fsgs->pbeam_orig;
-        fsgs->wbeam = fsgs->wbeam_orig;
-    }
-
-    if (n > fsg_lextree_n_pnode(fsgs->lextree))
-        E_FATAL("PANIC! Frame %d: #HMM evaluated(%d) > #PNodes(%d)\n",
-                fsgs->frame, n, fsg_lextree_n_pnode(fsgs->lextree));
-
-    fsgs->bestscore = bestscore;
-}
-
-
-static void
-fsg_search_pnode_trans(fsg_search_t *fsgs, fsg_pnode_t * pnode)
-{
-    fsg_pnode_t *child;
-    hmm_t *hmm;
-    int32 newscore, thresh, nf;
-
-    assert(pnode);
-    assert(!fsg_pnode_leaf(pnode));
-
-    nf = fsgs->frame + 1;
-    thresh = fsgs->bestscore + fsgs->beam;
-
-    hmm = fsg_pnode_hmmptr(pnode);
-
-    for (child = fsg_pnode_succ(pnode);
-         child; child = fsg_pnode_sibling(child)) {
-        newscore = hmm_out_score(hmm) + child->logs2prob;
-
-        if ((newscore BETTER_THAN thresh)
-            && (newscore BETTER_THAN hmm_in_score(&child->hmm))) {
-            /* Incoming score > pruning threshold and > target's existing score */
-            if (hmm_frame(&child->hmm) < nf) {
-                /* Child node not yet activated; do so */
-                fsgs->pnode_active_next =
-                    glist_add_ptr(fsgs->pnode_active_next,
-                                  (void *) child);
-            }
-
-            hmm_enter(&child->hmm, newscore, hmm_out_history(hmm), nf);
-        }
-    }
-}
-
-
-static void
-fsg_search_pnode_exit(fsg_search_t *fsgs, fsg_pnode_t * pnode)
-{
-    hmm_t *hmm;
-    fsg_link_t *fl;
-    int32 wid;
-    fsg_pnode_ctxt_t ctxt;
-
-    assert(pnode);
-    assert(fsg_pnode_leaf(pnode));
-
-    hmm = fsg_pnode_hmmptr(pnode);
-    fl = fsg_pnode_fsglink(pnode);
-    assert(fl);
-
-    wid = fsg_link_wid(fl);
-    assert(wid >= 0);
-
-#if __FSG_DBG__
-    E_INFO("[%5d] Exit(%08x) %10d(score) %5d(pred)\n",
-           fsgs->frame, (int32) pnode,
-           hmm_out_score(hmm), hmm_out_history(hmm));
-#endif
-
-    /*
-     * Check if this is filler or single phone word; these do not model right
-     * context (i.e., the exit score applies to all right contexts).
-     */
-    if (fsg_model_is_filler(fsgs->fsg, wid)
-        /* FIXME: This might be slow due to repeated calls to dict_to_id(). */
-        || (dict_is_single_phone(ps_search_dict(fsgs),
-                                   dict_wordid(ps_search_dict(fsgs),
-                                               fsg_model_word_str(fsgs->fsg, wid))))) {
-        /* Create a dummy context structure that applies to all right contexts */
-        fsg_pnode_add_all_ctxt(&ctxt);
-
-        /* Create history table entry for this word exit */
-        fsg_history_entry_add(fsgs->history,
-                              fl,
-                              fsgs->frame,
-                              hmm_out_score(hmm),
-                              hmm_out_history(hmm),
-                              pnode->ci_ext, ctxt);
-
-    }
-    else {
-        /* Create history table entry for this word exit */
-        fsg_history_entry_add(fsgs->history,
-                              fl,
-                              fsgs->frame,
-                              hmm_out_score(hmm),
-                              hmm_out_history(hmm),
-                              pnode->ci_ext, pnode->ctxt);
-    }
-}
-
-
-/*
- * (Beam) prune the just evaluated HMMs, determine which ones remain
- * active, which ones transition to successors, which ones exit and
- * terminate in their respective destination FSM states.
- * (Executed once per frame.)
- */
-static void
-fsg_search_hmm_prune_prop(fsg_search_t *fsgs)
-{
-    gnode_t *gn;
-    fsg_pnode_t *pnode;
-    hmm_t *hmm;
-    int32 thresh, word_thresh, phone_thresh;
-
-    assert(fsgs->pnode_active_next == NULL);
-
-    thresh = fsgs->bestscore + fsgs->beam;
-    phone_thresh = fsgs->bestscore + fsgs->pbeam;
-    word_thresh = fsgs->bestscore + fsgs->wbeam;
-
-    for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
-        pnode = (fsg_pnode_t *) gnode_ptr(gn);
-        hmm = fsg_pnode_hmmptr(pnode);
-
-        if (hmm_bestscore(hmm) >= thresh) {
-            /* Keep this HMM active in the next frame */
-            if (hmm_frame(hmm) == fsgs->frame) {
-                hmm_frame(hmm) = fsgs->frame + 1;
-                fsgs->pnode_active_next =
-                    glist_add_ptr(fsgs->pnode_active_next,
-                                  (void *) pnode);
-            }
-            else {
-                assert(hmm_frame(hmm) == fsgs->frame + 1);
-            }
-
-            if (!fsg_pnode_leaf(pnode)) {
-                if (hmm_out_score(hmm) >= phone_thresh) {
-                    /* Transition out of this phone into its children */
-                    fsg_search_pnode_trans(fsgs, pnode);
-                }
-            }
-            else {
-                if (hmm_out_score(hmm) >= word_thresh) {
-                    /* Transition out of leaf node into destination FSG state */
-                    fsg_search_pnode_exit(fsgs, pnode);
-                }
-            }
-        }
-    }
-}
-
-
-/*
- * Propagate newly created history entries through null transitions.
- */
-static void
-fsg_search_null_prop(fsg_search_t *fsgs)
-{
-    int32 bpidx, n_entries, thresh, newscore;
-    fsg_hist_entry_t *hist_entry;
-    fsg_link_t *l;
-    int32 s;
-    fsg_model_t *fsg;
-
-    fsg = fsgs->fsg;
-    thresh = fsgs->bestscore + fsgs->wbeam; /* Which beam really?? */
-
-    n_entries = fsg_history_n_entries(fsgs->history);
-
-    for (bpidx = fsgs->bpidx_start; bpidx < n_entries; bpidx++) {
-        fsg_arciter_t *itor;
-        hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
-
-        l = fsg_hist_entry_fsglink(hist_entry);
-
-        /* Destination FSG state for history entry */
-        s = l ? fsg_link_to_state(l) : fsg_model_start_state(fsg);
-
-        /*
-         * Check null transitions from d to all other states.  (Only need to
-         * propagate one step, since FSG contains transitive closure of null
-         * transitions.)
-         */
-        /* Add all links from from_state to dst */
-        for (itor = fsg_model_arcs(fsg, s); itor;
-             itor = fsg_arciter_next(itor)) {
-            fsg_link_t *l = fsg_arciter_get(itor);
-
-            /* FIXME: Need to deal with tag transitions somehow. */
-            if (fsg_link_wid(l) != -1)
-                continue;
-            newscore =
-                fsg_hist_entry_score(hist_entry) +
-                (fsg_link_logs2prob(l) >> SENSCR_SHIFT);
-
-            if (newscore >= thresh) {
-                fsg_history_entry_add(fsgs->history, l,
-                                      fsg_hist_entry_frame(hist_entry),
-                                      newscore,
-                                      bpidx,
-                                      fsg_hist_entry_lc(hist_entry),
-                                      fsg_hist_entry_rc(hist_entry));
-            }
-        }
-    }
-}
-
-
-/*
- * Perform cross-word transitions; propagate each history entry created in this
- * frame to lextree roots attached to the target FSG state for that entry.
- */
-static void
-fsg_search_word_trans(fsg_search_t *fsgs)
-{
-    int32 bpidx, n_entries;
-    fsg_hist_entry_t *hist_entry;
-    fsg_link_t *l;
-    int32 score, newscore, thresh, nf, d;
-    fsg_pnode_t *root;
-    int32 lc, rc;
-
-    n_entries = fsg_history_n_entries(fsgs->history);
-
-    thresh = fsgs->bestscore + fsgs->beam;
-    nf = fsgs->frame + 1;
-
-    for (bpidx = fsgs->bpidx_start; bpidx < n_entries; bpidx++) {
-        hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
-        assert(hist_entry);
-        score = fsg_hist_entry_score(hist_entry);
-        assert(fsgs->frame == fsg_hist_entry_frame(hist_entry));
-
-        l = fsg_hist_entry_fsglink(hist_entry);
-
-        /* Destination state for hist_entry */
-        d = l ? fsg_link_to_state(l) : fsg_model_start_state(fsgs->
-                                                                fsg);
-
-        lc = fsg_hist_entry_lc(hist_entry);
-
-        /* Transition to all root nodes attached to state d */
-        for (root = fsg_lextree_root(fsgs->lextree, d);
-             root; root = root->sibling) {
-            rc = root->ci_ext;
-
-            if ((root->ctxt.bv[lc >> 5] & (1 << (lc & 0x001f))) &&
-                (hist_entry->rc.bv[rc >> 5] & (1 << (rc & 0x001f)))) {
-                /*
-                 * Last CIphone of history entry is in left-context list supported by
-                 * target root node, and
-                 * first CIphone of target root node is in right context list supported
-                 * by history entry;
-                 * So the transition can go ahead (if new score is good enough).
-                 */
-                newscore = score + root->logs2prob;
-
-                if ((newscore BETTER_THAN thresh)
-                    && (newscore BETTER_THAN hmm_in_score(&root->hmm))) {
-                    if (hmm_frame(&root->hmm) < nf) {
-                        /* Newly activated node; add to active list */
-                        fsgs->pnode_active_next =
-                            glist_add_ptr(fsgs->pnode_active_next,
-                                          (void *) root);
-#if __FSG_DBG__
-                        E_INFO
-                            ("[%5d] WordTrans bpidx[%d] -> pnode[%08x] (activated)\n",
-                             fsgs->frame, bpidx, (int32) root);
-#endif
-                    }
-                    else {
-#if __FSG_DBG__
-                        E_INFO
-                            ("[%5d] WordTrans bpidx[%d] -> pnode[%08x]\n",
-                             fsgs->frame, bpidx, (int32) root);
-#endif
-                    }
-
-                    hmm_enter(&root->hmm, newscore, bpidx, nf);
-                }
-            }
-        }
-    }
-}
-
-
-int
-fsg_search_step(ps_search_t *search, int frame_idx)
-{
-    fsg_search_t *fsgs = (fsg_search_t *)search;
-    int16 const *senscr;
-    acmod_t *acmod = search->acmod;
-    gnode_t *gn;
-    fsg_pnode_t *pnode;
-    hmm_t *hmm;
-
-    /* Activate our HMMs for the current frame if need be. */
-    if (!acmod->compallsen)
-        fsg_search_sen_active(fsgs);
-    /* Compute GMM scores for the current frame. */
-    senscr = acmod_score(acmod, &frame_idx);
-    fsgs->n_sen_eval += acmod->n_senone_active;
-    hmm_context_set_senscore(fsgs->hmmctx, senscr);
-
-    /* Mark backpointer table for current frame. */
-    fsgs->bpidx_start = fsg_history_n_entries(fsgs->history);
-
-    /* Evaluate all active pnodes (HMMs) */
-    fsg_search_hmm_eval(fsgs);
-
-    /*
-     * Prune and propagate the HMMs evaluated; create history entries for
-     * word exits.  The words exits are tentative, and may be pruned; make
-     * the survivors permanent via fsg_history_end_frame().
-     */
-    fsg_search_hmm_prune_prop(fsgs);
-    fsg_history_end_frame(fsgs->history);
-
-    /*
-     * Propagate new history entries through any null transitions, creating
-     * new history entries, and then make the survivors permanent.
-     */
-    fsg_search_null_prop(fsgs);
-    fsg_history_end_frame(fsgs->history);
-
-    /*
-     * Perform cross-word transitions; propagate each history entry across its
-     * terminating state to the root nodes of the lextree attached to the state.
-     */
-    fsg_search_word_trans(fsgs);
-
-    /*
-     * We've now come full circle, HMM and FSG states have been updated for
-     * the next frame.
-     * Update the active lists, deactivate any currently active HMMs that
-     * did not survive into the next frame
-     */
-    for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
-        pnode = (fsg_pnode_t *) gnode_ptr(gn);
-        hmm = fsg_pnode_hmmptr(pnode);
-
-        if (hmm_frame(hmm) == fsgs->frame) {
-            /* This HMM NOT activated for the next frame; reset it */
-            fsg_psubtree_pnode_deactivate(pnode);
-        }
-        else {
-            assert(hmm_frame(hmm) == (fsgs->frame + 1));
-        }
-    }
-
-    /* Free the currently active list */
-    glist_free(fsgs->pnode_active);
-
-    /* Make the next-frame active list the current one */
-    fsgs->pnode_active = fsgs->pnode_active_next;
-    fsgs->pnode_active_next = NULL;
-
-    /* End of this frame; ready for the next */
-    ++fsgs->frame;
-
-    return 1;
-}
-
-
-/*
- * Set all HMMs to inactive, clear active lists, initialize FSM start
- * state to be the only active node.
- * (Executed at the start of each utterance.)
- */
-int
-fsg_search_start(ps_search_t *search)
-{
-    fsg_search_t *fsgs = (fsg_search_t *)search;
-    int32 silcipid;
-    fsg_pnode_ctxt_t ctxt;
-
-    /* Reset dynamic adjustment factor for beams */
-    fsgs->beam_factor = 1.0f;
-    fsgs->beam = fsgs->beam_orig;
-    fsgs->pbeam = fsgs->pbeam_orig;
-    fsgs->wbeam = fsgs->wbeam_orig;
-
-    silcipid = bin_mdef_ciphone_id(ps_search_acmod(fsgs)->mdef, "SIL");
-
-    /* Initialize EVERYTHING to be inactive */
-    assert(fsgs->pnode_active == NULL);
-    assert(fsgs->pnode_active_next == NULL);
-
-    fsg_history_reset(fsgs->history);
-    fsg_history_utt_start(fsgs->history);
-    fsgs->final = FALSE;
-
-    /* Dummy context structure that allows all right contexts to use this entry */
-    fsg_pnode_add_all_ctxt(&ctxt);
-
-    /* Create dummy history entry leading to start state */
-    fsgs->frame = -1;
-    fsgs->bestscore = 0;
-    fsg_history_entry_add(fsgs->history,
-                          NULL, -1, 0, -1, silcipid, ctxt);
-    fsgs->bpidx_start = 0;
-
-    /* Propagate dummy history entry through NULL transitions from start state */
-    fsg_search_null_prop(fsgs);
-
-    /* Perform word transitions from this dummy history entry */
-    fsg_search_word_trans(fsgs);
-
-    /* Make the next-frame active list the current one */
-    fsgs->pnode_active = fsgs->pnode_active_next;
-    fsgs->pnode_active_next = NULL;
-
-    ++fsgs->frame;
-
-    fsgs->n_hmm_eval = 0;
-    fsgs->n_sen_eval = 0;
-
-    return 0;
-}
-
-/*
- * Cleanup at the end of each utterance.
- */
-int
-fsg_search_finish(ps_search_t *search)
-{
-    fsg_search_t *fsgs = (fsg_search_t *)search;
-    gnode_t *gn;
-    fsg_pnode_t *pnode;
-    int32 n_hist;
-
-    /* Deactivate all nodes in the current and next-frame active lists */
-    for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
-        pnode = (fsg_pnode_t *) gnode_ptr(gn);
-        fsg_psubtree_pnode_deactivate(pnode);
-    }
-    for (gn = fsgs->pnode_active_next; gn; gn = gnode_next(gn)) {
-        pnode = (fsg_pnode_t *) gnode_ptr(gn);
-        fsg_psubtree_pnode_deactivate(pnode);
-    }
-
-    glist_free(fsgs->pnode_active);
-    fsgs->pnode_active = NULL;
-    glist_free(fsgs->pnode_active_next);
-    fsgs->pnode_active_next = NULL;
-
-    fsgs->final = TRUE;
-
-    n_hist = fsg_history_n_entries(fsgs->history);
-    E_INFO
-        ("%d frames, %d HMMs (%d/fr), %d senones (%d/fr), %d history entries (%d/fr)\n\n",
-         fsgs->frame, fsgs->n_hmm_eval,
-         (fsgs->frame > 0) ? fsgs->n_hmm_eval / fsgs->frame : 0,
-         fsgs->n_sen_eval,
-         (fsgs->frame > 0) ? fsgs->n_sen_eval / fsgs->frame : 0,
-         n_hist, (fsgs->frame > 0) ? n_hist / fsgs->frame : 0);
-
-    return 0;
-}
-
-static int
-fsg_search_find_exit(fsg_search_t *fsgs, int frame_idx, int final, int32 *out_score, int32* out_is_final)
-{
-    fsg_hist_entry_t *hist_entry = NULL;
-    fsg_model_t *fsg;
-    int bpidx, frm, last_frm, besthist;
-    int32 bestscore;
-
-    if (out_is_final)
-	*out_is_final = FALSE;
-
-    if (frame_idx == -1)
-        frame_idx = fsgs->frame - 1;
-    last_frm = frm = frame_idx;
-
-    /* Scan backwards to find a word exit in frame_idx. */
-    bpidx = fsg_history_n_entries(fsgs->history) - 1;
-    while (bpidx > 0) {
-        hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
-        if (fsg_hist_entry_frame(hist_entry) <= frame_idx) {
-            frm = last_frm = fsg_hist_entry_frame(hist_entry);
-            break;
-        }
-        bpidx--;
-    }
-
-    /* No hypothesis (yet). */
-    if (bpidx <= 0)
-        return bpidx;
-
-    /* Now find best word exit in this frame. */
-    bestscore = INT_MIN;
-    besthist = -1;
-    fsg = fsgs->fsg;
-    while (frm == last_frm) {
-        fsg_link_t *fl;
-        int32 score;
-
-        fl = fsg_hist_entry_fsglink(hist_entry);
-        score = fsg_hist_entry_score(hist_entry);
-        
-        if (fl == NULL)
-	    break;
-
-	/* Prefer final hypothesis */
-	if (score == bestscore && fsg_link_to_state(fl) == fsg_model_final_state(fsg)) {
-    	    besthist = bpidx;
-	} else if (score BETTER_THAN bestscore) {
-            /* Only enforce the final state constraint if this is a final hypothesis. */
-            if ((!final)
-                || fsg_link_to_state(fl) == fsg_model_final_state(fsg)) {
-                bestscore = score;
-                besthist = bpidx;
-            }
-        }
-        
-        --bpidx;
-        if (bpidx < 0)
-            break;
-        hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
-        frm = fsg_hist_entry_frame(hist_entry);
-    }
-
-    /* Final state not reached. */
-    if (besthist == -1) {
-        E_ERROR("Final result does not match the grammar in frame %d\n", frame_idx);
-        return -1;
-    }
-
-    /* This here's the one we want. */
-    if (out_score)
-        *out_score = bestscore;
-    if (out_is_final) {
-	fsg_link_t *fl;
-	hist_entry = fsg_history_entry_get(fsgs->history, besthist);
-	fl = fsg_hist_entry_fsglink(hist_entry);
-	*out_is_final = (fsg_link_to_state(fl) == fsg_model_final_state(fsg));
-    }
-    return besthist;
-}
-
-/* FIXME: Mostly duplicated with ngram_search_bestpath(). */
-static ps_latlink_t *
-fsg_search_bestpath(ps_search_t *search, int32 *out_score, int backward)
-{
-    fsg_search_t *fsgs = (fsg_search_t *)search;
-
-    if (search->last_link == NULL) {
-        search->last_link = ps_lattice_bestpath(search->dag, NULL,
-                                                1.0, fsgs->ascale);
-        if (search->last_link == NULL)
-            return NULL;
-        /* Also calculate betas so we can fill in the posterior
-         * probability field in the segmentation. */
-        if (search->post == 0)
-            search->post = ps_lattice_posterior(search->dag, NULL, fsgs->ascale);
-    }
-    if (out_score)
-        *out_score = search->last_link->path_scr + search->dag->final_node_ascr;
-    return search->last_link;
-}
-
-char const *
-fsg_search_hyp(ps_search_t *search, int32 *out_score, int32 *out_is_final)
-{
-    fsg_search_t *fsgs = (fsg_search_t *)search;
-    dict_t *dict = ps_search_dict(search);
-    char *c;
-    size_t len;
-    int bp, bpidx;
-
-    /* Get last backpointer table index. */
-    bpidx = fsg_search_find_exit(fsgs, fsgs->frame, fsgs->final, out_score, out_is_final);
-    /* No hypothesis (yet). */
-    if (bpidx <= 0) {
-        return NULL;
-    }
-
-    /* If bestpath is enabled and the utterance is complete, then run it. */
-    if (fsgs->bestpath && fsgs->final) {
-        ps_lattice_t *dag;
-        ps_latlink_t *link;
-
-        if ((dag = fsg_search_lattice(search)) == NULL) {
-    	    E_WARN("Failed to obtain the lattice while bestpath enabled\n");
-            return NULL;
-        }
-        if ((link = fsg_search_bestpath(search, out_score, FALSE)) == NULL) {
-    	    E_WARN("Failed to find the bestpath in a lattice\n");
-            return NULL;
-        }
-        return ps_lattice_hyp(dag, link);
-    }
-
-    bp = bpidx;
-    len = 0;
-    while (bp > 0) {
-        fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
-        fsg_link_t *fl = fsg_hist_entry_fsglink(hist_entry);
-        char const *baseword;
-        int32 wid;
-
-        bp = fsg_hist_entry_pred(hist_entry);
-        wid = fsg_link_wid(fl);
-        if (wid < 0 || fsg_model_is_filler(fsgs->fsg, wid))
-            continue;
-        baseword = dict_basestr(dict,
-                                dict_wordid(dict,
-                                            fsg_model_word_str(fsgs->fsg, wid)));
-        len += strlen(baseword) + 1;
-    }
-    
-    ckd_free(search->hyp_str);
-    if (len == 0) {
-	search->hyp_str = NULL;
-	return search->hyp_str;
-    }
-    search->hyp_str = ckd_calloc(1, len);
-
-    bp = bpidx;
-    c = search->hyp_str + len - 1;
-    while (bp > 0) {
-        fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
-        fsg_link_t *fl = fsg_hist_entry_fsglink(hist_entry);
-        char const *baseword;
-        int32 wid;
-
-        bp = fsg_hist_entry_pred(hist_entry);
-        wid = fsg_link_wid(fl);
-        if (wid < 0 || fsg_model_is_filler(fsgs->fsg, wid))
-            continue;
-        baseword = dict_basestr(dict,
-                                dict_wordid(dict,
-                                            fsg_model_word_str(fsgs->fsg, wid)));
-        len = strlen(baseword);
-        c -= len;
-        memcpy(c, baseword, len);
-        if (c > search->hyp_str) {
-            --c;
-            *c = ' ';
-        }
-    }
-
-    return search->hyp_str;
-}
-
-static void
-fsg_seg_bp2itor(ps_seg_t *seg, fsg_hist_entry_t *hist_entry)
-{
-    fsg_search_t *fsgs = (fsg_search_t *)seg->search;
-    fsg_hist_entry_t *ph = NULL;
-    int32 bp;
-
-    if ((bp = fsg_hist_entry_pred(hist_entry)) >= 0)
-        ph = fsg_history_entry_get(fsgs->history, bp);
-    seg->word = fsg_model_word_str(fsgs->fsg, hist_entry->fsglink->wid);
-    seg->ef = fsg_hist_entry_frame(hist_entry);
-    seg->sf = ph ? fsg_hist_entry_frame(ph) + 1 : 0;
-    /* This is kind of silly but it happens for null transitions. */
-    if (seg->sf > seg->ef) seg->sf = seg->ef;
-    seg->prob = 0; /* Bogus value... */
-    /* "Language model" score = transition probability. */
-    seg->lback = 1;
-    seg->lscr = fsg_link_logs2prob(hist_entry->fsglink) >> SENSCR_SHIFT;
-    if (ph) {
-        /* FIXME: Not sure exactly how cross-word triphones are handled. */
-        seg->ascr = hist_entry->score - ph->score - seg->lscr;
-    }
-    else
-        seg->ascr = hist_entry->score - seg->lscr;
-}
-
-
-static void
-fsg_seg_free(ps_seg_t *seg)
-{
-    fsg_seg_t *itor = (fsg_seg_t *)seg;
-    ckd_free(itor->hist);
-    ckd_free(itor);
-}
-
-static ps_seg_t *
-fsg_seg_next(ps_seg_t *seg)
-{
-    fsg_seg_t *itor = (fsg_seg_t *)seg;
-
-    if (++itor->cur == itor->n_hist) {
-        fsg_seg_free(seg);
-        return NULL;
-    }
-
-    fsg_seg_bp2itor(seg, itor->hist[itor->cur]);
-    return seg;
-}
-
-static ps_segfuncs_t fsg_segfuncs = {
-    /* seg_next */ fsg_seg_next,
-    /* seg_free */ fsg_seg_free
-};
-
-static ps_seg_t *
-fsg_search_seg_iter(ps_search_t *search, int32 *out_score)
-{
-    fsg_search_t *fsgs = (fsg_search_t *)search;
-    fsg_seg_t *itor;
-    int bp, bpidx, cur;
-
-    bpidx = fsg_search_find_exit(fsgs, fsgs->frame, fsgs->final, out_score, NULL);
-    /* No hypothesis (yet). */
-    if (bpidx <= 0)
-        return NULL;
-
-    /* If bestpath is enabled and the utterance is complete, then run it. */
-    if (fsgs->bestpath && fsgs->final) {
-        ps_lattice_t *dag;
-        ps_latlink_t *link;
-
-        if ((dag = fsg_search_lattice(search)) == NULL)
-            return NULL;
-        if ((link = fsg_search_bestpath(search, out_score, TRUE)) == NULL)
-            return NULL;
-        return ps_lattice_seg_iter(dag, link, 1.0);
-    }
-
-    /* Calling this an "iterator" is a bit of a misnomer since we have
-     * to get the entire backtrace in order to produce it.  On the
-     * other hand, all we actually need is the bptbl IDs, and we can
-     * allocate a fixed-size array of them. */
-    itor = ckd_calloc(1, sizeof(*itor));
-    itor->base.vt = &fsg_segfuncs;
-    itor->base.search = search;
-    itor->base.lwf = 1.0;
-    itor->n_hist = 0;
-    bp = bpidx;
-    while (bp > 0) {
-        fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
-        bp = fsg_hist_entry_pred(hist_entry);
-        ++itor->n_hist;
-    }
-    if (itor->n_hist == 0) {
-        ckd_free(itor);
-        return NULL;
-    }
-    itor->hist = ckd_calloc(itor->n_hist, sizeof(*itor->hist));
-    cur = itor->n_hist - 1;
-    bp = bpidx;
-    while (bp > 0) {
-        fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
-        itor->hist[cur] = hist_entry;
-        bp = fsg_hist_entry_pred(hist_entry);
-        --cur;
-    }
-
-    /* Fill in relevant fields for first element. */
-    fsg_seg_bp2itor((ps_seg_t *)itor, itor->hist[0]);
-    
-    return (ps_seg_t *)itor;
-}
-
-static int
-fsg_search_prob(ps_search_t *search)
-{
-    fsg_search_t *fsgs = (fsg_search_t *)search;
-
-    /* If bestpath is enabled and the utterance is complete, then run it. */
-    if (fsgs->bestpath && fsgs->final) {
-        ps_lattice_t *dag;
-        ps_latlink_t *link;
-
-        if ((dag = fsg_search_lattice(search)) == NULL)
-            return 0;
-        if ((link = fsg_search_bestpath(search, NULL, TRUE)) == NULL)
-            return 0;
-        return search->post;
-    }
-    else {
-        /* FIXME: Give some kind of good estimate here, eventually. */
-        return 0;
-    }
-}
-
-static ps_latnode_t *
-find_node(ps_lattice_t *dag, fsg_model_t *fsg, int sf, int32 wid, int32 node_id)
-{
-    ps_latnode_t *node;
-
-    for (node = dag->nodes; node; node = node->next)
-        if ((node->sf == sf) && (node->wid == wid) && (node->node_id == node_id))
-            break;
-    return node;
-}
-
-static ps_latnode_t *
-new_node(ps_lattice_t *dag, fsg_model_t *fsg, int sf, int ef, int32 wid, int32 node_id, int32 ascr)
-{
-    ps_latnode_t *node;
-
-    node = find_node(dag, fsg, sf, wid, node_id);
-
-    if (node) {
-        /* Update end frames. */
-        if (node->lef == -1 || node->lef < ef)
-            node->lef = ef;
-        if (node->fef == -1 || node->fef > ef)
-            node->fef = ef;
-        /* Update best link score. */
-        if (ascr BETTER_THAN node->info.best_exit)
-            node->info.best_exit = ascr;
-    }
-    else {
-        /* New node; link to head of list */
-        node = listelem_malloc(dag->latnode_alloc);
-        node->wid = wid;
-        node->sf = sf;
-        node->fef = node->lef = ef;
-        node->reachable = FALSE;
-        node->entries = NULL;
-        node->exits = NULL;
-        node->info.best_exit = ascr;
-        node->node_id = node_id;
-
-        node->next = dag->nodes;
-        dag->nodes = node;
-        ++dag->n_nodes;
-    }
-
-    return node;
-}
-
-static ps_latnode_t *
-find_start_node(fsg_search_t *fsgs, ps_lattice_t *dag)
-{
-    ps_latnode_t *node;
-    glist_t start = NULL;
-    int nstart = 0;
-
-    /* Look for all nodes starting in frame zero with some exits. */
-    for (node = dag->nodes; node; node = node->next) {
-        if (node->sf == 0 && node->exits) {
-            E_INFO("Start node %s.%d:%d:%d\n",
-                   fsg_model_word_str(fsgs->fsg, node->wid),
-                   node->sf, node->fef, node->lef);
-            start = glist_add_ptr(start, node);
-            ++nstart;
-        }
-    }
-
-    /* If there was more than one start node candidate, then we need
-     * to create an artificial start node with epsilon transitions to
-     * all of them. */
-    if (nstart == 1) {
-        node = gnode_ptr(start);
-    }
-    else {
-        gnode_t *st;
-        int wid;
-
-        wid = fsg_model_word_add(fsgs->fsg, "<s>");
-        if (fsgs->fsg->silwords)
-            bitvec_set(fsgs->fsg->silwords, wid);
-        node = new_node(dag, fsgs->fsg, 0, 0, wid, -1, 0);
-        for (st = start; st; st = gnode_next(st))
-            ps_lattice_link(dag, node, gnode_ptr(st), 0, 0);
-    }
-    glist_free(start);
-    return node;
-}
-
-static ps_latnode_t *
-find_end_node(fsg_search_t *fsgs, ps_lattice_t *dag)
-{
-    ps_latnode_t *node;
-    glist_t end = NULL;
-    int nend = 0;
-
-    /* Look for all nodes ending in last frame with some entries. */
-    for (node = dag->nodes; node; node = node->next) {
-        if (node->lef == dag->n_frames - 1 && node->entries) {
-            E_INFO("End node %s.%d:%d:%d (%d)\n",
-                   fsg_model_word_str(fsgs->fsg, node->wid),
-                   node->sf, node->fef, node->lef, node->info.best_exit);
-            end = glist_add_ptr(end, node);
-            ++nend;
-        }
-    }
-
-    if (nend == 1) {
-        node = gnode_ptr(end);
-    }
-    else if (nend == 0) {
-        ps_latnode_t *last = NULL;
-        int ef = 0;
-
-        /* If there were no end node candidates, then just use the
-         * node with the last exit frame. */
-        for (node = dag->nodes; node; node = node->next) {
-            if (node->lef > ef && node->entries) {
-                last = node;
-                ef = node->lef;
-            }
-        }
-        node = last;
-        if (node)
-            E_INFO("End node %s.%d:%d:%d (%d)\n",
-                   fsg_model_word_str(fsgs->fsg, node->wid),
-                   node->sf, node->fef, node->lef, node->info.best_exit);
-    }    
-    else {
-        /* If there was more than one end node candidate, then we need
-         * to create an artificial end node with epsilon transitions
-         * out of all of them. */
-        gnode_t *st;
-        int wid;
-        wid = fsg_model_word_add(fsgs->fsg, "</s>");
-        if (fsgs->fsg->silwords)
-            bitvec_set(fsgs->fsg->silwords, wid);
-        node = new_node(dag, fsgs->fsg, fsgs->frame, fsgs->frame, wid, -1, 0);
-        /* Use the "best" (in reality it will be the only) exit link
-         * score from this final node as the link score. */
-        for (st = end; st; st = gnode_next(st)) {
-            ps_latnode_t *src = gnode_ptr(st);
-            ps_lattice_link(dag, src, node, src->info.best_exit, fsgs->frame);
-        }
-    }
-    glist_free(end);
-    return node;
-}
-
-static void
-mark_reachable(ps_lattice_t *dag, ps_latnode_t *end)
-{
-    glist_t q;
-
-    /* It doesn't matter which order we do this in. */
-    end->reachable = TRUE;
-    q = glist_add_ptr(NULL, end);
-    while (q) {
-        ps_latnode_t *node = gnode_ptr(q);
-        latlink_list_t *x;
-
-        /* Pop the front of the list. */
-        q = gnode_free(q, NULL);
-        /* Expand all its predecessors that haven't been seen yet. */
-        for (x = node->entries; x; x = x->next) {
-            ps_latnode_t *next = x->link->from;
-            if (!next->reachable) {
-                next->reachable = TRUE;
-                q = glist_add_ptr(q, next);
-            }
-        }
-    }
-}
-
-/**
- * Generate a lattice from FSG search results.
- *
- * One might think that this is simply a matter of adding acoustic
- * scores to the FSG's edges.  However, one would be wrong.  The
- * crucial difference here is that the word lattice is acyclic, and it
- * also contains timing information.
- */
-static ps_lattice_t *
-fsg_search_lattice(ps_search_t *search)
-{
-    fsg_search_t *fsgs;
-    fsg_model_t *fsg;
-    ps_latnode_t *node;
-    ps_lattice_t *dag;
-    int32 i, n;
-
-    fsgs = (fsg_search_t *)search;
-
-    /* Check to see if a lattice has previously been created over the
-     * same number of frames, and reuse it if so. */
-    if (search->dag && search->dag->n_frames == fsgs->frame)
-        return search->dag;
-
-    /* Nope, create a new one. */
-    ps_lattice_free(search->dag);
-    search->dag = NULL;
-    dag = ps_lattice_init_search(search, fsgs->frame);
-    fsg = fsgs->fsg;
-
-    /*
-     * Each history table entry represents a link in the word graph.
-     * The set of nodes is determined by the number of unique
-     * (word,start-frame) pairs in the history table.  So we will
-     * first find all those nodes.
-     */
-    n = fsg_history_n_entries(fsgs->history);
-    for (i = 0; i < n; ++i) {
-        fsg_hist_entry_t *fh = fsg_history_entry_get(fsgs->history, i);
-        int32 ascr;
-        int sf;
-
-        /* Skip null transitions. */
-        if (fh->fsglink == NULL || fh->fsglink->wid == -1)
-            continue;
-
-        /* Find the start node of this link. */
-        if (fh->pred) {
-            fsg_hist_entry_t *pfh = fsg_history_entry_get(fsgs->history, fh->pred);
-            /* FIXME: We include the transition score in the lattice
-             * link score.  This is because of the practical
-             * difficulty of obtaining it separately in bestpath or
-             * forward-backward search, and because it is essentially
-             * a unigram probability, so there is no need to treat it
-             * separately from the acoustic score.  However, it's not
-             * clear that this will actually yield correct results.*/
-            ascr = fh->score - pfh->score;
-            sf = pfh->frame + 1;
-        }
-        else {
-            ascr = fh->score;
-            sf = 0;
-        }
-
-        /*
-         * Note that although scores are tied to links rather than
-         * nodes, it's possible that there are no links out of the
-         * destination node, and thus we need to preserve its score in
-         * case it turns out to be utterance-final.
-         */
-        new_node(dag, fsg, sf, fh->frame, fh->fsglink->wid, fsg_link_to_state(fh->fsglink), ascr);
-    }
-
-    /*
-     * Now, we will create links only to nodes that actually exist.
-     */
-    n = fsg_history_n_entries(fsgs->history);
-    for (i = 0; i < n; ++i) {
-        fsg_hist_entry_t *fh = fsg_history_entry_get(fsgs->history, i);
-        fsg_arciter_t *itor;
-        ps_latnode_t *src, *dest;
-        int32 ascr;
-        int sf;
-
-        /* Skip null transitions. */
-        if (fh->fsglink == NULL || fh->fsglink->wid == -1)
-            continue;
-
-        /* Find the start node of this link and calculate its link score. */
-        if (fh->pred) {
-            fsg_hist_entry_t *pfh = fsg_history_entry_get(fsgs->history, fh->pred);
-            sf = pfh->frame + 1;
-            ascr = fh->score - pfh->score;
-        }
-        else {
-            ascr = fh->score;
-            sf = 0;
-        }
-        src = find_node(dag, fsg, sf, fh->fsglink->wid, fsg_link_to_state(fh->fsglink));
-        sf = fh->frame + 1;
-
-        for (itor = fsg_model_arcs(fsg, fsg_link_to_state(fh->fsglink));
-             itor; itor = fsg_arciter_next(itor)) {
-            fsg_link_t *link = fsg_arciter_get(itor);
-            
-            /* FIXME: Need to figure out what to do about tag transitions. */
-            if (link->wid >= 0) {
-                /*
-                 * For each non-epsilon link following this one, look for a
-                 * matching node in the lattice and link to it.
-                 */
-                if ((dest = find_node(dag, fsg, sf, link->wid, fsg_link_to_state(link))) != NULL)
-            	    ps_lattice_link(dag, src, dest, ascr, fh->frame);
-            }
-            else {
-                /*
-                 * Transitive closure on nulls has already been done, so we
-                 * just need to look one link forward from them.
-                 */
-                fsg_arciter_t *itor2;
-                
-                /* Add all non-null links out of j. */
-                for (itor2 = fsg_model_arcs(fsg, fsg_link_to_state(link));
-                     itor2; itor2 = fsg_arciter_next(itor2)) {
-                    fsg_link_t *link = fsg_arciter_get(itor2);
-
-                    if (link->wid == -1)
-                        continue;
-                    
-                    if ((dest = find_node(dag, fsg, sf, link->wid, fsg_link_to_state(link))) != NULL) {
-                        ps_lattice_link(dag, src, dest, ascr, fh->frame);
-                    }
-                }
-            }
-        }
-    }
-
-
-    /* Figure out which nodes are the start and end nodes. */
-    if ((dag->start = find_start_node(fsgs, dag)) == NULL) {
-	E_WARN("Failed to find the start node\n");
-        goto error_out;
-    }
-    if ((dag->end = find_end_node(fsgs, dag)) == NULL) {
-	E_WARN("Failed to find the end node\n");
-        goto error_out;
-    }
-
-
-    E_INFO("lattice start node %s.%d end node %s.%d\n",
-           fsg_model_word_str(fsg, dag->start->wid), dag->start->sf,
-           fsg_model_word_str(fsg, dag->end->wid), dag->end->sf);
-    /* FIXME: Need to calculate final_node_ascr here. */
-
-    /*
-     * Convert word IDs from FSG to dictionary.
-     */
-    for (node = dag->nodes; node; node = node->next) {
-        node->wid = dict_wordid(dag->search->dict,
-                                fsg_model_word_str(fsg, node->wid));
-        node->basewid = dict_basewid(dag->search->dict, node->wid);
-    }
-
-    /*
-     * Now we are done, because the links in the graph are uniquely
-     * defined by the history table.  However we should remove any
-     * nodes which are not reachable from the end node of the FSG.
-     * Everything is reachable from the start node by definition.
-     */
-    mark_reachable(dag, dag->end);
-
-    ps_lattice_delete_unreachable(dag);
-    {
-        int32 silpen, fillpen;
-
-        silpen = (int32)(logmath_log(fsg->lmath,
-                                     cmd_ln_float32_r(ps_search_config(fsgs), "-silprob"))
-                         * fsg->lw)
-            >> SENSCR_SHIFT;
-        fillpen = (int32)(logmath_log(fsg->lmath,
-                                      cmd_ln_float32_r(ps_search_config(fsgs), "-fillprob"))
-                          * fsg->lw)
-            >> SENSCR_SHIFT;
-	
-	ps_lattice_penalize_fillers(dag, silpen, fillpen);
-    }
-    search->dag = dag;
-
-    return dag;
-
-
-error_out:
-    ps_lattice_free(dag);
-    return NULL;
-
-}
-