KeyNote version 2 trust-management system (security policy handling).

Utilities to follow.

1 files changed, 899 insertions, 0 deletions

diff --git a/lib/libkeynote/keynote.y b/lib/libkeynote/keynote.y
new file mode 100644
index 00000000000..ca6c3fbf066
--- /dev/null
+++ b/lib/libkeynote/keynote.y
@@ -0,0 +1,899 @@
+/* $OpenBSD: keynote.y,v 1.1 1999/05/23 22:11:05 angelos Exp $ */
+
+/*
+ * The author of this code is Angelos D. Keromytis (angelos@dsl.cis.upenn.edu)
+ *
+ * This code was written by Angelos D. Keromytis in Philadelphia, PA, USA,
+ * in April-May 1998
+ *
+ * Copyright (C) 1998, 1999 by Angelos D. Keromytis.
+ *	
+ * Permission to use, copy, and modify this software without fee
+ * is hereby granted, provided that this entire notice is included in
+ * all copies of any software which is or includes a copy or
+ * modification of this software. 
+ *
+ * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR
+ * IMPLIED WARRANTY. IN PARTICULAR, THE AUTHORS MAKES NO
+ * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE
+ * MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR
+ * PURPOSE.
+ */
+%union {
+    char   *string;
+    double  doubval;
+    int     intval;
+    int     bool;
+};
+%type <bool> stringexp numexp expr floatexp
+%type <intval> NUM KOF numex afterhint notemptyprog
+%type <intval> notemptykeypredicate prog key keyexp keylist
+%type <doubval> FLOAT floatex
+%type <string> STRING VARIABLE str strnotconcat 
+%token TRUE FALSE NUM FLOAT STRING VARIABLE 
+%token OPENPAREN CLOSEPAREN EQQ COMMA ACTSTR LOCINI KOF KEYPRE KNVERSION
+%token DOTT SIGNERKEY HINT OPENBLOCK CLOSEBLOCK SIGNATUREENTRY PRIVATEKEY
+%token SEMICOLON TRUE FALSE
+%nonassoc EQ NE LT GT LE GE REGEXP
+%left OR
+%left AND
+%right NOT
+%left PLUS MINUS DOTT
+%left MULT DIV MOD
+%left EXP
+%nonassoc UNARYMINUS DEREF OPENNUM OPENFLT
+%start grammarswitch
+%{
+#include <sys/types.h>
+#include <stdio.h>
+#include <math.h>
+#include <string.h>
+#include <stdlib.h>
+#include <ctype.h>
+#include <regex.h>
+#include "environment.h"
+#include "signature.h"
+
+static int *keynote_kth_array = (int *) NULL;
+static int keylistcount = 0;
+
+static int   resolve_assertion(char *);
+static int   keynote_init_kth(void);
+static int   isfloatstring(char *);
+static int   checkexception(int);
+static char *my_lookup(char *);
+static int   intpow(int, int);
+static int   get_kth(int);
+
+extern int keynote_in_action_authorizers(void *, int);
+extern int knlex();
+
+extern int keynote_exceptionflag, keynote_donteval;
+extern char **keynote_values, *keynote_privkey;
+extern struct keylist *keynote_keypred_keylist;
+extern struct environment *keynote_temp_list;
+extern struct environment *keynote_init_list;
+extern int knlineno, keynote_used_variable;
+ 
+void knerror(char *);
+%}
+%%
+
+grammarswitch: LOCINI { keynote_exceptionflag = keynote_donteval = 0; }
+                localinit
+             | ACTSTR { keynote_exceptionflag = keynote_donteval = 0; } program
+   	     | KEYPRE { keynote_exceptionflag = keynote_donteval = 0; }
+                keypredicate
+             | SIGNERKEY { keynote_exceptionflag = keynote_donteval = 0; } key
+             | SIGNATUREENTRY { keynote_exceptionflag = keynote_donteval = 0; }
+                key
+             | KNVERSION { keynote_exceptionflag = keynote_donteval = 0; }
+                        STRING { keynote_lex_remove($3);
+				 if (strcmp($3, KEYNOTE_VERSION_STRING))
+				   keynote_errno = ERROR_SYNTAX;
+				 free($3);
+			       }
+             | PRIVATEKEY { keynote_exceptionflag = keynote_donteval = 0; }
+                        STRING { keynote_lex_remove($3);
+			         keynote_privkey = $3;
+			       }
+    
+keypredicate: /* Nothing */   { keynote_returnvalue = 0;
+                                return 0; 
+                              }
+       | notemptykeypredicate { keynote_returnvalue = $1;
+				return 0;
+                              }
+
+notemptykeypredicate:  key     { $$ = $1; }
+       		     | keyexp  { $$ = $1; }
+
+keyexp: notemptykeypredicate AND { if (($1 == 0) && !keynote_justrecord)
+                                     keynote_donteval = 1;
+                                 } notemptykeypredicate 
+                 { if ($1 > $4)
+		     $$ = $4;
+		   else
+	       	     $$ = $1;
+		   keynote_donteval = 0;
+                 }  /* Min */
+      | notemptykeypredicate OR { if (($1 == (keynote_current_session->ks_values_num - 1)) && !keynote_justrecord)
+	                             keynote_donteval = 1;
+       	                         } notemptykeypredicate
+                 { if ($1 >= $4)
+		     $$ = $1;
+		   else
+		     $$ = $4;
+		   keynote_donteval = 0;
+                 }  /* Max */
+       | OPENPAREN keyexp CLOSEPAREN { $$ = $2; }
+       | KOF { keylistcount = 0; } OPENPAREN {
+			 if (!keynote_justrecord && !keynote_donteval)
+ 	                   if (keynote_init_kth() == -1)
+			     return -1;
+                       } keylist CLOSEPAREN 
+                          {
+			      if (keylistcount < $1)
+			      {
+				  keynote_errno = ERROR_SYNTAX;
+				  return -1;
+			      }
+
+			    if (!keynote_justrecord && !keynote_donteval)
+			      $$ = get_kth($1);
+			    else
+			      $$ = 0;
+			  }  /* K-th */
+
+keylist: key
+	    { /* Don't do anything if we're just recording */ 
+              if (!keynote_justrecord && !keynote_donteval)
+		if (($1 < keynote_current_session->ks_values_num) && ($1 >= 0))
+		  keynote_kth_array[$1]++;
+
+	      keylistcount++;
+            }
+        | key COMMA keylist
+            { /* Don't do anything if we're just recording */ 
+	      if (!keynote_justrecord && !keynote_donteval)
+		if (($1 < keynote_current_session->ks_values_num) && ($1 >= 0))
+		  keynote_kth_array[$1]++;
+
+	      keylistcount++;
+            }
+
+key: str        {
+		   if (keynote_donteval)
+		     $$ = 0;
+		   else
+		   {
+		       keynote_lex_remove($1);
+		       if (keynote_justrecord)
+		       {
+			   if (keynote_keylist_add(&keynote_keypred_keylist,
+						   $1) == -1)
+			   {
+			       free($1);
+			       return -1;
+			   }
+
+			   $$ = 0;
+		       }
+		       else
+			 switch (keynote_in_action_authorizers($1, KEYNOTE_ALGORITHM_UNSPEC))
+			 {
+			     case -1:
+				 free($1);
+				 return -1;
+				 
+			     case RESULT_TRUE:
+				 free($1);
+				 $$ = keynote_current_session->ks_values_num -
+				      1;
+				 break;
+				 
+			     default:
+				 $$ = resolve_assertion($1);
+				 free($1);
+				 break;
+			 }
+		   }
+                 }
+
+localinit: /* Nothing */
+         | localconstants
+
+localconstants: VARIABLE EQQ STRING 
+	  {
+            int i;
+
+            keynote_lex_remove($1);
+	    keynote_lex_remove($3);
+ 
+	    /*
+	     * Variable names starting with underscores are illegal here.
+	     */
+	    if ($1[0] == '_')
+	    {
+		free($1);
+		free($3);
+		keynote_errno = ERROR_SYNTAX;
+		return -1;
+	    }
+	    
+	    /* If the identifier already exists, report error. */
+	    if (keynote_env_lookup($1, &keynote_init_list, 1) != (char *) NULL)
+	    {
+		free($1);
+		free($3);
+		keynote_errno = ERROR_SYNTAX;
+		return -1;
+	    }
+
+	    i = keynote_env_add($1, $3, &keynote_init_list, 1, 0);
+	    free($1);
+	    free($3);
+
+	    if (i != RESULT_TRUE)
+	      return -1;
+	  }
+         | VARIABLE EQQ STRING
+	  {
+            int i;
+
+	    keynote_lex_remove($1);
+	    keynote_lex_remove($3);
+
+	    /*
+	     * Variable names starting with underscores are illegal here.
+	     */
+	    if ($1[0] == '_')
+	    {
+		free($1);
+		free($3);
+		keynote_errno = ERROR_SYNTAX;
+		return -1;
+	    }
+	 
+	    /* If the identifier already exists, report error. */
+	    if (keynote_env_lookup($1, &keynote_init_list, 1) != (char *) NULL)
+	    {
+		free($1);
+		free($3);
+		keynote_errno = ERROR_SYNTAX;
+		return -1;
+	    }
+
+	    i = keynote_env_add($1, $3, &keynote_init_list, 1, 0);
+	    free($1);
+	    free($3);
+
+	    if (i != RESULT_TRUE)
+	      return -1;
+	  } localconstants
+
+program: prog { 
+	        keynote_returnvalue = $1;
+		return 0;
+	      }
+
+prog:   /* Nada */ { $$ = 0; }
+       | notemptyprog {
+			  /* 
+			   * Cleanup envlist of additions such as 
+			   * regexp results
+			   */
+			  keynote_env_cleanup(&keynote_temp_list, 1);
+                    } SEMICOLON prog
+                    {
+		      if ($1 > $4)
+			$$ = $1;
+		      else
+			$$ = $4;
+                    } 
+
+notemptyprog: expr HINT afterhint
+              {
+		if (checkexception($1))
+		  $$ = $3;
+		else
+		  $$ = 0;
+	      }
+       |  expr 
+              {
+		if (checkexception($1))
+		  $$ = keynote_current_session->ks_values_num - 1;
+		else
+		  $$ = 0;
+	      }
+
+afterhint: str {  if (keynote_exceptionflag || keynote_donteval)
+		    $$ = 0;
+		  else
+		  {
+		      keynote_lex_remove($1);
+
+		      $$ = keynote_retindex($1);
+		      if ($$ == -1)   /* Invalid return value */
+			$$ = 0;
+
+		      free($1);
+		  }
+                }
+         | OPENBLOCK prog CLOSEBLOCK { $$ = $2; }
+
+
+expr:     OPENPAREN expr CLOSEPAREN 	{ $$ = $2; }
+	| expr AND { if ($1 == 0)
+	               keynote_donteval = 1;
+	           } expr               { $$ = ($1 && $4);
+		                          keynote_donteval = 0;
+		                        }
+	| expr OR { if ($1)
+	              keynote_donteval = 1; 
+	          } expr 		{ $$ = ($1 || $4);
+		                          keynote_donteval = 0;
+                                        }
+	| NOT expr 			{ $$ = !($2); }
+	| numexp 			{ $$ = $1; }
+	| floatexp			{ $$ = $1; }
+	| stringexp 			{ $$ = $1; }
+        | TRUE	  		        { $$ = 1; }
+        | FALSE	  		        { $$ = 0; }
+
+numexp:	  numex LT numex { $$ = $1 < $3; }
+	| numex GT numex { $$ = $1 > $3; }
+	| numex EQ numex { $$ = $1 == $3; }
+	| numex LE numex { $$ = $1 <= $3; }
+	| numex GE numex { $$ = $1 >= $3; }
+	| numex NE numex { $$ = $1 != $3; }
+
+floatexp: floatex LT floatex { $$ = $1 < $3; }
+	| floatex GT floatex { $$ = $1 > $3; }
+	| floatex LE floatex { $$ = $1 <= $3; }
+	| floatex GE floatex { $$ = $1 >= $3; }
+
+numex:	  numex PLUS numex  { $$ = $1 + $3; }
+	| numex MINUS numex { $$ = $1 - $3; }
+	| numex MULT numex  { $$ = $1 * $3; }
+        | numex DIV numex   { if ($3 == 0)
+	                      {
+				  if (!keynote_donteval)
+				    keynote_exceptionflag = 1;
+			      }
+	                      else
+			        $$ = ($1 / $3);
+			    }
+	| numex MOD numex   { if ($3 == 0)
+	                      {
+				  if (!keynote_donteval)
+				    keynote_exceptionflag = 1;
+			      }
+	                      else
+			        $$ = $1 % $3;
+			    }
+	| numex EXP numex   		{ $$ = intpow($1, $3); }
+	| MINUS numex %prec UNARYMINUS 	{ $$ = -($2); }
+	| OPENPAREN numex CLOSEPAREN   	{ $$ = $2; }
+	| NUM 			       	{ $$ = $1; }
+        | OPENNUM strnotconcat         	{ if (keynote_exceptionflag ||
+					      keynote_donteval)
+	                                    $$ = 0;
+ 	                                  else
+					  {
+					      keynote_lex_remove($2);
+
+					      if (!isfloatstring($2))
+						$$ = 0;
+					      else
+						$$ = (int) floor(atof($2));
+					      free($2);
+					  }
+					}
+
+floatex:  floatex PLUS floatex  	{ $$ = ($1 + $3); }
+	| floatex MINUS floatex 	{ $$ = ($1 - $3); }
+	| floatex MULT floatex          { $$ = ($1 * $3); }
+        | floatex DIV floatex   	{ if ($3 == 0)
+	                                  {
+					      if (!keynote_donteval)
+						keynote_exceptionflag = 1;
+					  }
+	                                  else
+			        	   $$ = ($1 / $3);
+					}
+	| floatex EXP floatex  			{ if (!keynote_exceptionflag &&
+						      !keynote_donteval)
+	                                            $$ = pow($1, $3);
+	                                        }
+	| MINUS floatex %prec UNARYMINUS 	{ $$ = -($2); }
+	| OPENPAREN floatex CLOSEPAREN	 	{ $$ = $2; }
+	| FLOAT			       		{ $$ = $1; }
+        | OPENFLT strnotconcat          {
+	                                  if (keynote_exceptionflag ||
+					      keynote_donteval)
+					    $$ = 0.0;
+					  else
+					  {
+					      keynote_lex_remove($2);
+					  
+					      if (!isfloatstring($2))
+						$$ = 0.0;
+					      else
+						$$ = atof($2);
+					      free($2);
+					  }
+	                                }
+
+stringexp: str EQ str {
+                        if (keynote_exceptionflag || keynote_donteval)
+			  $$ = 0;
+			else
+			{
+			    $$ = strcmp($1, $3) == 0 ? 1 : 0;
+			    keynote_lex_remove($1);
+			    keynote_lex_remove($3);
+			    free($1);
+			    free($3);
+			}
+		      }
+	 | str NE str {
+	                if (keynote_exceptionflag || keynote_donteval)
+			  $$ = 0;
+			else
+			{
+			    $$ = strcmp($1, $3) != 0 ? 1 : 0;
+			    keynote_lex_remove($1);
+			    keynote_lex_remove($3);
+			    free($1);
+			    free($3);
+			}
+		      }
+	 | str LT str {
+	                if (keynote_exceptionflag || keynote_donteval)
+			  $$ = 0;
+			else
+			{
+			    $$ = strcmp($1, $3) < 0 ? 1 : 0;
+			    keynote_lex_remove($1);
+			    keynote_lex_remove($3);
+			    free($1);
+			    free($3);
+			}
+		      }
+	 | str GT str {
+	                if (keynote_exceptionflag || keynote_donteval)
+			  $$ = 0;
+			else
+			{
+			    $$ = strcmp($1, $3) > 0 ? 1 : 0;
+			    keynote_lex_remove($1);
+			    keynote_lex_remove($3);
+			    free($1);
+			    free($3);
+			}
+		      }
+	 | str LE str {
+	                if (keynote_exceptionflag || keynote_donteval)
+			  $$ = 0;
+			else
+			{
+			    $$ = strcmp($1, $3) <= 0 ? 1 : 0;
+			    keynote_lex_remove($1);
+			    keynote_lex_remove($3);
+			    free($1);
+			    free($3);
+			}
+		      }
+	 | str GE str {
+	                if (keynote_exceptionflag || keynote_donteval)
+			  $$ = 0;
+			else
+			{
+			    $$ = strcmp($1, $3) >= 0 ? 1 : 0;
+			    keynote_lex_remove($1);
+			    keynote_lex_remove($3);
+			    free($1);
+			    free($3);
+			}
+		      }
+	 | str REGEXP str 
+            {
+	      regmatch_t pmatch[32];
+	      char grp[4], *gr;
+	      regex_t preg;
+	      int i;
+
+	      if (keynote_exceptionflag || keynote_donteval)
+		$$ = 0;
+	      else
+	      {
+		  keynote_lex_remove($1);
+		  keynote_lex_remove($3);
+
+		  memset(pmatch, 0, sizeof(pmatch));
+		  memset(grp, 0, sizeof(grp));
+
+		  if (regcomp(&preg, $3, REG_EXTENDED))
+		  {
+		      free($1);
+		      free($3);
+		      keynote_exceptionflag = 1;
+		  }
+		  else
+		  {
+		      /* Clean-up residuals from previous regexps */
+		      keynote_env_cleanup(&keynote_temp_list, 1);
+
+		      free($3);
+		      i = regexec(&preg, $1, 32, pmatch, 0);
+		      $$ = (i == 0 ? 1 : 0);
+		      if (i == 0)
+		      {
+#ifdef NO_SNPRINTF
+			  sprintf(grp, "%d", preg.re_nsub);
+#else /* NO_SNPRINTF */
+			  snprintf(grp, 3, "%d", preg.re_nsub);
+#endif /* NO_SNPRINTF */
+			  if (keynote_env_add("_0", grp, &keynote_temp_list,
+					      1, 0) != RESULT_TRUE)
+			  {
+			      free($1);
+			      regfree(&preg);
+			      return -1;
+			  }
+
+			  for (i = 1; i < 32 && pmatch[i].rm_so != -1; i++)
+			  {
+			      gr = calloc(pmatch[i].rm_eo - pmatch[i].rm_so +
+					  1, sizeof(char));
+			      if (gr == (char *) NULL)
+			      {
+				  free($1);
+				  regfree(&preg);
+				  keynote_errno = ERROR_MEMORY;
+				  return -1;
+			      }
+
+			      strncpy(gr, $1 + pmatch[i].rm_so,
+				      pmatch[i].rm_eo - pmatch[i].rm_so);
+			      gr[pmatch[i].rm_eo - pmatch[i].rm_so] = '\0';
+#ifdef NO_SNPRINTF
+			      sprintf(grp, "_%d", i);
+#else /* NO_SNPRINTF */
+			      snprintf(grp, 3, "_%d", i);
+#endif /* NO_SNPRINTF */
+			      if (keynote_env_add(grp, gr, &keynote_temp_list,
+						  1, 0) == -1)
+			      {
+				  free($1);
+				  regfree(&preg);
+				  free(gr);
+				  return -1;
+			      }
+			      else
+				free(gr);
+			  }
+		      }
+
+		      regfree(&preg);
+		      free($1);
+		  }
+	      }
+	    }
+
+str: str DOTT str    {  if (keynote_exceptionflag || keynote_donteval)
+			  $$ = (char *) NULL;
+			else
+			{
+			    $$ = calloc(strlen($1) + strlen($3) + 1,
+					sizeof(char));
+			    keynote_lex_remove($1);
+			    keynote_lex_remove($3);
+			    if ($$ == (char *) NULL)
+			    {
+				free($1);
+				free($3);
+				keynote_errno = ERROR_MEMORY;
+				return -1;
+			    }
+ 
+			    strcpy($$, $1);
+			    strcpy($$ + strlen($1), $3);
+			    free($1);
+			    free($3);
+			    if (keynote_lex_add($$, LEXTYPE_CHAR) == -1)
+			      return -1;
+			}
+		      }
+	| strnotconcat { $$ = $1; }
+
+strnotconcat: STRING 	                { $$ = $1; }
+        | OPENPAREN str CLOSEPAREN 	{ $$ = $2; }
+        | VARIABLE      {  if (keynote_exceptionflag || keynote_donteval)
+	                     $$ = (char *) NULL;
+ 	                   else
+			   {
+			       $$ = my_lookup($1);
+			       keynote_lex_remove($1);
+			       free($1);
+			       if ($$ == (char *) NULL)
+			       {
+				   if (keynote_errno)
+				     return -1;
+				   $$ = strdup("");
+			       }
+			       else
+				 $$ = strdup($$);
+
+			       if ($$ == (char *) NULL)
+			       {
+				   keynote_errno = ERROR_MEMORY;
+				   return -1;
+			       }
+
+			       if (keynote_lex_add($$, LEXTYPE_CHAR) == -1)
+				 return -1;
+			   }
+	                 }
+	| DEREF str      {  if (keynote_exceptionflag || keynote_donteval)
+			      $$ = (char *) NULL;
+			    else
+			    {
+				$$ = my_lookup($2);
+				keynote_lex_remove($2);
+				free($2);
+				if ($$ == (char *) NULL)
+				{
+				    if (keynote_errno)
+				      return -1;
+				    $$ = strdup("");
+				}
+				else
+				  $$ = strdup($$);
+
+				if ($$ == (char *) NULL)
+				{
+				    keynote_errno = ERROR_MEMORY;
+				    return -1;
+				}
+
+				if (keynote_lex_add($$, LEXTYPE_CHAR) == -1)
+				  return -1;
+			    }
+			 }
+%%
+
+/*
+ * Find all assertions signed by s and give us the one with the highest
+ * return value.
+ */
+static int
+resolve_assertion(char *s)
+{
+    int i, alg = KEYNOTE_ALGORITHM_NONE, p = 0;
+    void *key = (void *) s;
+    struct assertion *as;
+    struct keylist *kl;
+
+    kl = keynote_keylist_find(keynote_current_assertion->as_keylist, s);
+    if (kl != (struct keylist *) NULL)
+    {
+	alg = kl->key_alg;
+	key = kl->key_key;
+    }
+
+    for (i = 0;; i++)
+    {
+	as = keynote_find_assertion(key, i, alg);
+	if (as == (struct assertion *) NULL)  /* Gone through all of them */
+	  return p;
+
+	if (as->as_kresult == KRESULT_DONE)
+	  if (p < as->as_result)
+	    p = as->as_result;
+
+	/* Short circuit if we find an assertion with maximum return value */
+	if (p == (keynote_current_session->ks_values_num - 1))
+	  return p;
+    }
+
+    return 0;
+}
+
+/* 
+ * Environment variable lookup. 
+ */
+static char *
+my_lookup(char *s)
+{
+    struct keynote_session *ks = keynote_current_session;
+    char *ret;
+
+    if (!strcmp(s, "_MIN_TRUST"))
+    {
+	keynote_used_variable = 1;
+	return ks->ks_values[0];
+    }
+    else
+    {
+	if (!strcmp(s, "_MAX_TRUST"))
+	{
+	    keynote_used_variable = 1;
+	    return ks->ks_values[ks->ks_values_num - 1];
+	}
+	else
+	{
+	    if (!strcmp(s, "_VALUES"))
+	    {
+		keynote_used_variable = 1;
+		return keynote_env_lookup("_VALUES", ks->ks_env_table,
+					  HASHTABLESIZE);
+	    }
+	    else
+	    {
+		if (!strcmp(s, "_ACTION_AUTHORIZERS"))
+		{
+		    keynote_used_variable = 1;
+		    return keynote_env_lookup("_ACTION_AUTHORIZERS",
+					      ks->ks_env_table, HASHTABLESIZE);
+		}
+	    }
+	}
+    }
+
+    /* Temporary list (regexp results) */
+    ret = keynote_env_lookup(s, &keynote_temp_list, 1);
+    if (ret != (char *) NULL)
+      return ret;
+    else
+      if (keynote_errno != 0)
+	return (char *) NULL;
+
+    /* Local-Constants */
+    ret = keynote_env_lookup(s, &keynote_init_list, 1);
+    if (ret != (char *) NULL)
+      return ret;
+    else
+      if (keynote_errno != 0)
+	return (char *) NULL;
+
+    keynote_used_variable = 1;
+
+    /* Action environment */
+    ret = keynote_env_lookup(s, ks->ks_env_table, HASHTABLESIZE);
+    if (ret != (char *) NULL)
+      return ret;
+    else
+      if (keynote_errno != 0)
+	return (char *) NULL;
+
+    /* Regex table */
+    return keynote_env_lookup(s, &(ks->ks_env_regex), 1);
+}
+
+/*
+ * If we had an exception, the boolean expression should return false.
+ * Otherwise, return the result of the expression (the argument).
+ */
+static int
+checkexception(int i)
+{
+    if (keynote_exceptionflag)
+    {
+	keynote_exceptionflag = 0;
+	return 0;
+    }
+    else
+      return i;
+}
+
+
+/* 
+ * Integer exponentation -- copied from Schneier's AC2, page 244. 
+ */
+static int
+intpow(int x, int y)
+{
+    int s = 1;
+    
+    /* 
+     * x^y with y < 0 is equivalent to 1/(x^y), which for
+     * integer arithmetic is 0.
+     */
+    if (y < 0)
+      return 0;
+
+    while (y)
+    {
+	if (y & 1)
+	  s *= x;
+	
+	y >>= 1;
+	x *= x;
+    }
+
+    return s;
+}
+
+/* 
+ * Check whether the string is a floating point number. 
+ */
+static int
+isfloatstring(char *s)
+{
+    int i, point = 0;
+    
+    for (i = strlen(s) - 1; i >= 0; i--)
+      if (!isdigit(s[i]))
+      {
+	  if (s[i] == '.')
+	  {
+	      if (point == 1)
+	        return 0;
+	      else
+	        point = 1;
+	  }
+	  else
+	    return 0;
+      }
+
+    return 1;
+}
+
+/*
+ * Initialize array for threshold search.
+ */
+static int
+keynote_init_kth(void)
+{
+    int i = keynote_current_session->ks_values_num;
+    
+    if (i == -1)
+      return -1;
+    
+    keynote_kth_array = (int *) calloc(i, sizeof(int));
+    if (keynote_kth_array == (int *) NULL)
+    {
+	keynote_errno = ERROR_MEMORY;
+	return -1;
+    }
+
+    return RESULT_TRUE;
+}
+
+/*
+ * Get the k-th best return value.
+ */
+static int
+get_kth(int k)
+{
+    int i;
+
+    for (i = keynote_current_session->ks_values_num - 1; i >= 0; i--)
+    {
+	k -= keynote_kth_array[i];
+	
+	if (k <= 0)
+	  return i;
+    }
+
+    return 0;
+}
+
+/*
+ * Cleanup array.
+ */
+void
+keynote_cleanup_kth(void)
+{
+    if (keynote_kth_array != (int *) NULL)
+    {
+	free(keynote_kth_array);
+	keynote_kth_array = (int *) NULL;
+    }
+}
+
+void
+knerror(char *s)
+{}