void
word_fsg_free(word_fsg_t * fsg)
{
    int32 i, j;
    gnode_t *gn;
    word_fsglink_t *tl;

    for (i = 0; i < fsg->n_state; i++) {
        for (j = 0; j < fsg->n_state; j++) {
            /* Free all non-null transitions between states i and j */
            for (gn = fsg->trans[i][j]; gn; gn = gnode_next(gn)) {
                tl = (word_fsglink_t *) gnode_ptr(gn);
                ckd_free((void *) tl);
            }

            glist_free(fsg->trans[i][j]);

            /* Free any null transition i->j */
            ckd_free((void *) fsg->null_trans[i][j]);
        }
    }

    ctxt_table_free(fsg->ctxt);
    ckd_free_2d((void **) fsg->trans);
    ckd_free_2d((void **) fsg->null_trans);
    ckd_free((void *) fsg->name);

    if (fsg->lc)
        ckd_free_2d((void **) fsg->lc);
    if (fsg->rc)
        ckd_free_2d((void **) fsg->rc);

    ckd_free((void *) fsg);
}

void
mdef_free(mdef_t * m)
{
    int i, j;

    if (m) {
        if (m->sen2cimap)
            ckd_free((void *) m->sen2cimap);
        if (m->cd2cisen)
            ckd_free((void *) m->cd2cisen);

        /* RAH, go down the ->next list and delete all the pieces */
        for (i = 0; i < N_WORD_POSN; i++)
            for (j = 0; j < m->n_ciphone; j++)
                if (m->wpos_ci_lclist[i][j]) {
                    mdef_free_recursive_lc(m->wpos_ci_lclist[i][j]->next);
                    mdef_free_recursive_rc(m->wpos_ci_lclist[i][j]->
                                           rclist);
                }

        for (i = 0; i < N_WORD_POSN; i++)
            for (j = 0; j < m->n_ciphone; j++)
                if (m->wpos_ci_lclist[i][j])
                    ckd_free((void *) m->wpos_ci_lclist[i][j]);


        if (m->wpos_ci_lclist)
            ckd_free_2d((void *) m->wpos_ci_lclist);
        if (m->sseq)
            ckd_free_2d((void *) m->sseq);
        /* Free phone context */
        if (m->phone)
            ckd_free((void *) m->phone);
        if (m->ciphone_ht)
            hash_table_free(m->ciphone_ht);

        for (i = 0; i < m->n_ciphone; i++) {
            if (m->ciphone[i].name)
                ckd_free((void *) m->ciphone[i].name);
        }


        if (m->ciphone)
            ckd_free((void *) m->ciphone);

        if (m->st2senmap)
            ckd_free((void *) m->st2senmap);

        ckd_free((void *) m);
    }
}

void
s3_endpointer_feed_frames(s3_endpointer_t *_ep,
			  float32 **_frames,
			  int _n_frames,
			  int _eof)
{
    float32 **fbuf;
    int *cbuf;
    int i, sz, leftover;

    assert(_ep != NULL);

    if (_ep->n_frames > _ep->offset) {
	leftover = _ep->n_frames - _ep->offset;
	sz = _n_frames + leftover;
	fbuf = (float32 **)ckd_calloc_2d(sz, CEP_LEN, sizeof(float32));
	cbuf = (int *)ckd_calloc(sizeof(int), sz);
	for (i = 0; i < leftover; i++)
	    memcpy(fbuf[i], _ep->frames[_ep->offset + i], FRAME_LEN);
	memcpy(cbuf, &_ep->classes[_ep->offset], leftover * sizeof(int));
	for (i = leftover; i < sz; i++)
	    memcpy(fbuf[i], _frames[i - leftover], FRAME_LEN);
	get_frame_classes(_ep, _frames, _n_frames, &cbuf[leftover]);

	ckd_free_2d((void **)_ep->frames);
	ckd_free(_ep->classes);
	_ep->frames = fbuf;
	_ep->classes = cbuf;
	_ep->n_frames = sz;
	_ep->offset = 0;
    }
    else {
	fbuf = (float32 **)ckd_calloc_2d(_n_frames, CEP_LEN, sizeof(float32));
	cbuf = (int *)ckd_calloc(sizeof(int), _n_frames);
	for (i = 0; i < _n_frames; i++)
	    memcpy(fbuf[i], _frames[i], FRAME_LEN);
	get_frame_classes(_ep, _frames, _n_frames, cbuf);

	ckd_free_2d((void **)_ep->frames);
	ckd_free(_ep->classes);
	_ep->frames = fbuf;
	_ep->classes = cbuf;
	_ep->n_frames = _n_frames;
	_ep->offset = 0;
    }

    if (_ep->state == STATE_BEGIN_STREAM && update_available(_ep))
	init_frame_stats(_ep);

    _ep->eof = _eof;
}

/* RAH 4.15.01 Lots of memory is allocated, but never freed, this function will clean up.
 * First pass will get the low hanging fruit.*/
void kb_free (kb_t *kb)
{
  vithist_t *vithist = kb->vithist;

  if (kb->sen_active)
    ckd_free ((void *)kb->sen_active);
  if (kb->ssid_active) 
    ckd_free ((void *)kb->ssid_active);
  if (kb->comssid_active)
    ckd_free ((void *)kb->comssid_active);
  if (kb->fillertree) 
    ckd_free ((void *)kb->fillertree);
  if (kb->hmm_hist) 
    ckd_free ((void *)kb->hmm_hist);
  

  /* vithist */
  if (vithist) {
    ckd_free ((void *) vithist->entry);
    ckd_free ((void *) vithist->frame_start);
    ckd_free ((void *) vithist->bestscore);
    ckd_free ((void *) vithist->bestvh);
    ckd_free ((void *) vithist->lms2vh_root);    
    ckd_free ((void *) kb->vithist);
  }


  kbcore_free (kb->kbcore);

  if (kb->feat) {
    ckd_free ((void *)kb->feat[0][0]);
    ckd_free_2d ((void **)kb->feat);
  }

  if (kb->cache_ci_senscr) {
    ckd_free_2d ((void **)kb->cache_ci_senscr);
  }
  if( kb->cache_best_list) {
    ckd_free((void*) kb->cache_best_list);
  }
  if(kb->phn_heur_list) {
    ckd_free((void*) kb->phn_heur_list);
  }

  if (kb->matchsegfp) fclose(kb->matchsegfp);
  if (kb->matchfp) fclose(kb->matchfp);

  kb_freehyps(kb);
}

int
feat_free(feat_t * f)
{
    if (f == 0)
        return 0;
    if (--f->refcount > 0)
        return f->refcount;

    if (f->cepbuf)
        ckd_free_2d((void **) f->cepbuf);
    ckd_free(f->tmpcepbuf);

    if (f->name) {
        ckd_free((void *) f->name);
    }
    if (f->lda)
        ckd_free_3d((void ***) f->lda);

    ckd_free(f->stream_len);
    ckd_free(f->sv_len);
    ckd_free(f->sv_buf);
    subvecs_free(f->subvecs);

    cmn_free(f->cmn_struct);
    agc_free(f->agc_struct);

    ckd_free(f);
    return 0;
}

void
ld_finish(live_decoder_t * _decoder)
{
    assert(_decoder != NULL);

    if (_decoder->fe != NULL) {
        fe_close(_decoder->fe);
    }
    if (_decoder->features != NULL) {
        /* consult the implementation of feat_array_alloc() for how to free our
         * internal feature vector buffer */
        ckd_free((void *) **_decoder->features);
        ckd_free_2d((void **) _decoder->features);
    }
    if (_decoder->internal_cmdln == TRUE) {
        cmd_ln_free();
    }
    kb_free(&_decoder->kb);
    ld_free_hyps(_decoder);
    if (_decoder->uttid != NULL) {
        ckd_free(_decoder->uttid);
        _decoder->uttid = NULL;
    }
    _decoder->ld_state = LD_STATE_FINISHED;
}

int
sphinx_wave2feat_free(sphinx_wave2feat_t *wtf)
{
    if (wtf == NULL)
        return 0;
    if (--wtf->refcount > 0)
        return wtf->refcount;

    if (wtf->audio)
	ckd_free(wtf->audio);
    if (wtf->feat)
	ckd_free_2d(wtf->feat);
    if (wtf->infile)
        ckd_free(wtf->infile);
    if (wtf->outfile)
	ckd_free(wtf->outfile);
    if (wtf->infh) {
        if (fclose(wtf->infh) == EOF)
            E_ERROR_SYSTEM("Failed to close input file");
    }
    if (wtf->outfh) {
        if (fclose(wtf->outfh) == EOF)
            E_ERROR_SYSTEM("Failed to close output file");
    }
    cmd_ln_free_r(wtf->config);
    fe_free(wtf->fe);
    ckd_free(wtf);

    return 0;
}

int32
solve(float32 **a, /*Input : an n*n matrix A */
      float32 *b,  /*Input : a n dimesion vector b */
      float32 *out_x,  /*Output : a n dimesion vector x */
      int32   n)
{
    char uplo;
    float32 **tmp_a;
    int32 info, nrhs;

    /* a is assumed to be symmetric, so we don't need to switch the
     * ordering of the data.  But we do need to copy it since it is
     * overwritten by LAPACK. */
    tmp_a = (float32 **)ckd_calloc_2d(n, n, sizeof(float32));
    memcpy(tmp_a[0], a[0], n*n*sizeof(float32));
    memcpy(out_x, b, n*sizeof(float32));
    uplo = 'L';
    nrhs = 1;
    sposv_(&uplo, &n, &nrhs, tmp_a[0], &n, out_x, &n, &info);
    ckd_free_2d((void **)tmp_a);

    if (info != 0)
	return -1;
    else
	return info;
}

int32
free_mllr_A(float32 ****A,
	    uint32  n_class,
	    uint32  n_stream)
{
    uint32 i,j;

    for (i=0; i < n_class; i++) {
	for (j=0; j < n_stream; j++) {
	    ckd_free_2d((void **)A[i][j]);
	}
    }
    ckd_free_2d((void **)A);

    return S3_SUCCESS;
}

static int
acmod_process_full_raw(acmod_t *acmod,
                       int16 const **inout_raw,
                       size_t *inout_n_samps)
{
    int32 nfr, ntail;
    mfcc_t **cepptr;

    /* Write to logging file if any. */
    if (acmod->rawfh)
        fwrite(*inout_raw, 2, *inout_n_samps, acmod->rawfh);
    /* Resize mfc_buf to fit. */
    if (fe_process_frames(acmod->fe, NULL, inout_n_samps, NULL, &nfr) < 0)
        return -1;
    if (acmod->n_mfc_alloc < nfr + 1) {
        ckd_free_2d(acmod->mfc_buf);
        acmod->mfc_buf = ckd_calloc_2d(nfr + 1, fe_get_output_size(acmod->fe),
                                       sizeof(**acmod->mfc_buf));
        acmod->n_mfc_alloc = nfr + 1;
    }
    acmod->n_mfc_frame = 0;
    acmod->mfc_outidx = 0;
    fe_start_utt(acmod->fe);
    if (fe_process_frames(acmod->fe, inout_raw, inout_n_samps,
                          acmod->mfc_buf, &nfr) < 0)
        return -1;
    fe_end_utt(acmod->fe, acmod->mfc_buf[nfr], &ntail);
    nfr += ntail;

    cepptr = acmod->mfc_buf;
    nfr = acmod_process_full_cep(acmod, &cepptr, &nfr);
    acmod->n_mfc_frame = 0;
    return nfr;
}

/* Find inverse by solving AX=I. */
int32
invert(float32 ** ainv, float32 ** a, int32 n)
{
    char uplo;
    float32 **tmp_a;
    int32 info, nrhs, i;

    /* a is assumed to be symmetric, so we don't need to switch the
     * ordering of the data.  But we do need to copy it since it is
     * overwritten by LAPACK. */
    tmp_a = (float32 **)ckd_calloc_2d(n, n, sizeof(float32));
    memcpy(tmp_a[0], a[0], n*n*sizeof(float32));

    /* Construct an identity matrix. */
    memset(ainv[0], 0, sizeof(float32) * n * n);
    for (i = 0; i < n; i++)
        ainv[i][i] = 1.0;

    uplo = 'L';
    nrhs = n;
    sposv_(&uplo, &n, &nrhs, tmp_a[0], &n, ainv[0], &n, &info);

    ckd_free_2d((void **)tmp_a);

    if (info != 0)
	return -1;
    else
	return info;
}

void
ngram_model_set_map_words(ngram_model_t * base,
                          const char **words, int32 n_words)
{
    ngram_model_set_t *set = (ngram_model_set_t *) base;
    int32 i;

    /* Recreate the word mapping. */
    if (base->writable) {
        for (i = 0; i < base->n_words; ++i) {
            ckd_free(base->word_str[i]);
        }
    }
    ckd_free(base->word_str);
    ckd_free_2d((void **) set->widmap);
    base->writable = TRUE;
    base->n_words = base->n_1g_alloc = n_words;
    base->word_str = ckd_calloc(n_words, sizeof(*base->word_str));
    set->widmap =
        (int32 **) ckd_calloc_2d(n_words, set->n_models,
                                 sizeof(**set->widmap));
    hash_table_empty(base->wid);
    for (i = 0; i < n_words; ++i) {
        int32 j;
        base->word_str[i] = ckd_salloc(words[i]);
        (void) hash_table_enter_int32(base->wid, base->word_str[i], i);
        for (j = 0; j < set->n_models; ++j) {
            set->widmap[i][j] = ngram_wid(set->lms[j], base->word_str[i]);
        }
    }
}

/* Find determinant through LU decomposition. */
float64
determinant(float32 ** a, int32 n)
{
    float32 **tmp_a;
    float64 det;
    char uplo;
    int32 info, i;

    /* a is assumed to be symmetric, so we don't need to switch the
     * ordering of the data.  But we do need to copy it since it is
     * overwritten by LAPACK. */
    tmp_a = (float32 **)ckd_calloc_2d(n, n, sizeof(float32));
    memcpy(tmp_a[0], a[0], n*n*sizeof(float32));

    uplo = 'L';
    spotrf_(&uplo, &n, tmp_a[0], &n, &info);
    det = tmp_a[0][0];
    /* det = prod(diag(l))^2 */
    for (i = 1; i < n; ++i)
	det *= tmp_a[i][i];
    ckd_free_2d((void **)tmp_a);
    if (info > 0)
	return -1.0; /* Generic "not positive-definite" answer */
    else
	return det * det;
}

/* RAH 4.15.01 Lots of memory is allocated, but never freed, this function will clean up.
 * First pass will get the low hanging fruit.*/
void kb_free (kb_t *kb)
{
  vithist_t *vithist = kb->vithist;

  if (kb->sen_active)
    ckd_free ((void *)kb->sen_active);
  if (kb->ssid_active) 
    ckd_free ((void *)kb->ssid_active);
  if (kb->comssid_active)
    ckd_free ((void *)kb->comssid_active);
  if (kb->fillertree) 
    ckd_free ((void *)kb->fillertree);
  if (kb->hmm_hist) 
    ckd_free ((void *)kb->hmm_hist);
  

  /* vithist */
  if (vithist) {
    ckd_free ((void *) vithist->entry);
    ckd_free ((void *) vithist->frame_start);
    ckd_free ((void *) vithist->bestscore);
    ckd_free ((void *) vithist->bestvh);
    ckd_free ((void *) vithist->lms2vh_root);    
    ckd_free ((void *) kb->vithist);
  }


  kbcore_free (kb->kbcore);

  if (kb->feat) {
    ckd_free ((void *)kb->feat[0][0]);
    ckd_free_2d ((void **)kb->feat);
  }
    
}

ngram_model_t *
ngram_model_set_add(ngram_model_t * base,
                    ngram_model_t * model,
                    const char *name, float32 weight, int reuse_widmap)
{
    ngram_model_set_t *set = (ngram_model_set_t *) base;
    float32 fprob;
    int32 scale, i;

    /* Add it to the array of lms. */
    ++set->n_models;
    set->lms = ckd_realloc(set->lms, set->n_models * sizeof(*set->lms));
    set->lms[set->n_models - 1] = model;
    set->names =
        ckd_realloc(set->names, set->n_models * sizeof(*set->names));
    set->names[set->n_models - 1] = ckd_salloc(name);
    /* Expand the history mapping table if necessary. */
    if (model->n > base->n) {
        base->n = model->n;
        set->maphist = ckd_realloc(set->maphist,
                                   (model->n - 1) * sizeof(*set->maphist));
    }

    /* Renormalize the interpolation weights. */
    fprob = weight * 1.0f / set->n_models;
    set->lweights = ckd_realloc(set->lweights,
                                set->n_models * sizeof(*set->lweights));
    set->lweights[set->n_models - 1] = logmath_log(base->lmath, fprob);
    /* Now normalize everything else to fit it in.  This is
     * accomplished by simply scaling all the other probabilities
     * by (1-fprob). */
    scale = logmath_log(base->lmath, 1.0 - fprob);
    for (i = 0; i < set->n_models - 1; ++i)
        set->lweights[i] += scale;

    /* Reuse the old word ID mapping if requested. */
    if (reuse_widmap) {
        int32 **new_widmap;

        /* Tack another column onto the widmap array. */
        new_widmap = (int32 **) ckd_calloc_2d(base->n_words, set->n_models,
                                              sizeof(**new_widmap));
        for (i = 0; i < base->n_words; ++i) {
            /* Copy all the existing mappings. */
            memcpy(new_widmap[i], set->widmap[i],
                   (set->n_models - 1) * sizeof(**new_widmap));
            /* Create the new mapping. */
            new_widmap[i][set->n_models - 1] =
                ngram_wid(model, base->word_str[i]);
        }
        ckd_free_2d((void **) set->widmap);
        set->widmap = new_widmap;
    }
    else {
        build_widmap(base, base->lmath, base->n);
    }
    return model;
}

/* RAH 4.15.01 Lots of memory is allocated, but never freed, this function will clean up.
 * First pass will get the low hanging fruit.*/
void
kb_free(kb_t * kb)
{
    if (kb->srch) {
        srch_uninit(kb->srch);
    /** Add search free code */
    }

    if (kb->stat) {
        stat_free((void *) kb->stat);
    }

    if (kb->ascr)
        ascr_free((void *) kb->ascr);

    if (kb->fastgmm)
        fast_gmm_free((void *) kb->fastgmm);

    if (kb->beam)
        beam_free((void *) kb->beam);


    if (kb->pl)
        pl_free((void *) kb->pl);

    if (kb->kbcore != NULL)
        kbcore_free(kb->kbcore);

    /* This is awkward, currently, there are two routines to control MLLRs and I don't have time 
       to unify them yet. TBD */
    if (kb->adapt_am->regA && kb->adapt_am->regB && kb->adapt_am->regH)
        mllr_free_regmat(kb->adapt_am->regA, kb->adapt_am->regB, kb->adapt_am->regH);
    if (kb->adapt_am)
        adapt_am_free(kb->adapt_am);

    if (kb->feat) {
        ckd_free((void *) kb->feat[0][0]);
        ckd_free_2d((void **) kb->feat);
    }


    if (kb->uttid) {
        ckd_free(kb->uttid);
    }

    if (kb->uttfile) {
        ckd_free(kb->uttfile);
    }


#if 0                           /* valgrind reports this one. */
    if (kb->matchsegfp)
        fclose(kb->matchsegfp);
    if (kb->matchfp)
        fclose(kb->matchfp);
#endif
}

void
fsg_lextree_free(fsg_lextree_t * lextree)
{
    int32 s;

    if (lextree == NULL)
        return;

    if (lextree->fsg)
        for (s = 0; s < fsg_model_n_state(lextree->fsg); s++)
            fsg_psubtree_free(lextree->alloc_head[s]);

    ckd_free_2d(lextree->lc);
    ckd_free_2d(lextree->rc);
    ckd_free(lextree->root);
    ckd_free(lextree->alloc_head);
    ckd_free(lextree);
}

void subvq_free (subvq_t *s)
{
    int32 i;
    
    for (i = 0; i < s->n_sv; i++) {
	ckd_free_2d ((void **) s->mean[i]);
	ckd_free_2d ((void **) s->var[i]);
	ckd_free ((void *) s->featdim[i]);
    }
    
    ckd_free ((void *) s->svsize);
    ckd_free ((void *) s->featdim);
    ckd_free ((void *) s->mean);
    ckd_free ((void *) s->var);
    ckd_free_3d ((void ***) s->map);
    
    ckd_free ((void *) s);
}

static void
build_widmap(ngram_model_t * base, logmath_t * lmath, int32 n)
{
    ngram_model_set_t *set = (ngram_model_set_t *) base;
    ngram_model_t **models = set->lms;
    hash_table_t *vocab;
    glist_t hlist;
    gnode_t *gn;
    int32 i;

    /* Construct a merged vocabulary and a set of word-ID mappings. */
    vocab = hash_table_new(models[0]->n_words, FALSE);
    /* Create the set of merged words. */
    for (i = 0; i < set->n_models; ++i) {
        int32 j;
        for (j = 0; j < models[i]->n_words; ++j) {
            /* Ignore collisions. */
            (void) hash_table_enter_int32(vocab, models[i]->word_str[j],
                                          j);
        }
    }
    /* Create the array of words, then sort it. */
    if (hash_table_lookup(vocab, "<UNK>", NULL) != 0)
        (void) hash_table_enter_int32(vocab, "<UNK>", 0);
    /* Now we know the number of unigrams, initialize the base model. */
    ngram_model_init(base, &ngram_model_set_funcs, lmath, n,
                     hash_table_inuse(vocab));
    base->writable = FALSE;     /* We will reuse the pointers from the submodels. */
    i = 0;
    hlist = hash_table_tolist(vocab, NULL);
    for (gn = hlist; gn; gn = gnode_next(gn)) {
        hash_entry_t *ent = gnode_ptr(gn);
        base->word_str[i++] = (char *) ent->key;
    }
    glist_free(hlist);
    qsort(base->word_str, base->n_words, sizeof(*base->word_str),
          my_compare);

    /* Now create the word ID mappings. */
    if (set->widmap)
        ckd_free_2d((void **) set->widmap);
    set->widmap = (int32 **) ckd_calloc_2d(base->n_words, set->n_models,
                                           sizeof(**set->widmap));
    for (i = 0; i < base->n_words; ++i) {
        int32 j;
        /* Also create the master wid mapping. */
        (void) hash_table_enter_int32(base->wid, base->word_str[i], i);
        /* printf("%s: %d => ", base->word_str[i], i); */
        for (j = 0; j < set->n_models; ++j) {
            set->widmap[i][j] = ngram_wid(models[j], base->word_str[i]);
            /* printf("%d ", set->widmap[i][j]); */
        }
        /* printf("\n"); */
    }
    hash_table_free(vocab);
}

int32
free_mllr_reg(float32 *****regl,
              float32 ****regr,
              uint32  n_class,
              uint32  n_stream)
{
    uint32 i,j;

    for (i=0; i < n_class; i++) {
        for (j=0; j < n_stream; j++) {
            ckd_free_3d((void ***)regl[i][j]);
            ckd_free_2d((void **)regr[i][j]);
        }
    }
    ckd_free_2d((void **)regl);
    ckd_free_2d((void **)regr);

    return S3_SUCCESS;
}