From 954dbb2d3554080dbfe84c4c6f7ee2017c48807e Mon Sep 17 00:00:00 2001
From: Hartmut Holzgraefe <hholzgra@php.net>
Date: Sun, 7 Apr 2002 19:46:45 +0000
Subject: [PATCH] fix and regression test for Bug #16473

---
 ext/standard/levenshtein.c                    | 26 +++++++++----------
 ext/standard/tests/general_functions/003.phpt |  6 +++++
 2 files changed, 18 insertions(+), 14 deletions(-)

diff --git a/ext/standard/levenshtein.c b/ext/standard/levenshtein.c
index 47a8de7540..f5c23687cf 100644
--- a/ext/standard/levenshtein.c
+++ b/ext/standard/levenshtein.c
@@ -40,33 +40,31 @@ static int reference_levdist(const char *s1, int l1,
 	if((l1>LEVENSHTEIN_MAX_LENTH)||(l2>LEVENSHTEIN_MAX_LENTH))
 		return -1;
 
-	if(!(p1=emalloc(l2*sizeof(int)))) {
+	if(!(p1=emalloc((l2+1)*sizeof(int)))) {
 		return -2;
 	}
-	if(!(p2=emalloc(l2*sizeof(int)))) {
+	if(!(p2=emalloc((l2+1)*sizeof(int)))) {
 		free(p1);
 		return -2;
 	}
 
-	p1[0]=(s1[0]==s2[0])?0:cost_rep;
+	for(i2=0;i2<=l2;i2++)
+		p1[i2] = i2*cost_ins;
 
-	for(i2=1;i2<l2;i2++)
-		p1[i2]=i2*cost_ins;
-
-	for(i1=1;i1<l1;i1++)
+	for(i1=0;i1<l1;i1++)
 		{
-			p2[0]=i1*cost_del;
-			for(i2=1;i2<l2;i2++)
+			p2[0]=p1[0]+cost_del;
+			for(i2=0;i2<l2;i2++)
 				{
-					c0=p1[i2-1]+((s1[i1]==s2[i2])?0:cost_rep);
-					c1=p1[i2]+cost_del; if(c1<c0) c0=c1;
-					c2=p2[i2-1]+cost_ins; if(c2<c0) c0=c2;				
-					p2[i2]=c0;
+					c0=p1[i2]+((s1[i1]==s2[i2])?0:cost_rep);
+					c1=p1[i2+1]+cost_del; if(c1<c0) c0=c1;
+					c2=p2[i2]+cost_ins; if(c2<c0) c0=c2;				
+					p2[i2+1]=c0;
 				}
 			tmp=p1; p1=p2; p2=tmp;
 		}
 
-	c0=p1[l2-1];
+	c0=p1[l2];
 
 	efree(p1);
 	efree(p2);
diff --git a/ext/standard/tests/general_functions/003.phpt b/ext/standard/tests/general_functions/003.phpt
index 22cbd4eb4e..141b4d7052 100644
--- a/ext/standard/tests/general_functions/003.phpt
+++ b/ext/standard/tests/general_functions/003.phpt
@@ -47,6 +47,12 @@ $n += test_me("bug #6562", 1,    "ddebug",    "debug");
 $n += test_me("bug #6562", 2,   "debbbug",    "debug");
 $n += test_me("bug #6562", 1, "debugging", "debuging");
 
+$n += test_me("bug #16473", 2, "a", "bc");
+$n += test_me("bug #16473", 2, "xa", "xbc");
+$n += test_me("bug #16473", 2, "xax", "xbcx");
+$n += test_me("bug #16473", 2, "ax", "bcx");
+
+
 echo ($n==0)?"all passed\n":"$n failed\n";
 
 ?>
-- 
2.40.0