xref: /PHP-7.0/ext/standard/levenshtein.c (revision 478f119a)
1 /*
2    +----------------------------------------------------------------------+
3    | PHP Version 7                                                        |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 1997-2017 The PHP Group                                |
6    +----------------------------------------------------------------------+
7    | This source file is subject to version 3.01 of the PHP license,      |
8    | that is bundled with this package in the file LICENSE, and is        |
9    | available through the world-wide-web at the following url:           |
10    | http://www.php.net/license/3_01.txt                                  |
11    | If you did not receive a copy of the PHP license and are unable to   |
12    | obtain it through the world-wide-web, please send a note to          |
13    | license@php.net so we can mail you a copy immediately.               |
14    +----------------------------------------------------------------------+
15    | Author: Hartmut Holzgraefe <hholzgra@php.net>                        |
16    +----------------------------------------------------------------------+
17  */
18 /* $Id$ */
19 
20 #include "php.h"
21 #include <stdlib.h>
22 #include <errno.h>
23 #include <ctype.h>
24 #include "php_string.h"
25 
26 #define LEVENSHTEIN_MAX_LENGTH 255
27 
28 /* {{{ reference_levdist
29  * reference implementation, only optimized for memory usage, not speed */
reference_levdist(const char * s1,size_t l1,const char * s2,size_t l2,zend_long cost_ins,zend_long cost_rep,zend_long cost_del)30 static zend_long reference_levdist(const char *s1, size_t l1, const char *s2, size_t l2, zend_long cost_ins, zend_long cost_rep, zend_long cost_del )
31 {
32 	zend_long *p1, *p2, *tmp;
33 	zend_long c0, c1, c2;
34 	size_t i1, i2;
35 
36 	if (l1 == 0) {
37 		return l2 * cost_ins;
38 	}
39 	if (l2 == 0) {
40 		return l1 * cost_del;
41 	}
42 
43 	if ((l1 > LEVENSHTEIN_MAX_LENGTH) || (l2 > LEVENSHTEIN_MAX_LENGTH)) {
44 		return -1;
45 	}
46 	p1 = safe_emalloc((l2 + 1), sizeof(zend_long), 0);
47 	p2 = safe_emalloc((l2 + 1), sizeof(zend_long), 0);
48 
49 	for (i2 = 0; i2 <= l2; i2++) {
50 		p1[i2] = i2 * cost_ins;
51 	}
52 	for (i1 = 0; i1 < l1 ; i1++) {
53 		p2[0] = p1[0] + cost_del;
54 
55 		for (i2 = 0; i2 < l2; i2++) {
56 			c0 = p1[i2] + ((s1[i1] == s2[i2]) ? 0 : cost_rep);
57 			c1 = p1[i2 + 1] + cost_del;
58 			if (c1 < c0) {
59 				c0 = c1;
60 			}
61 			c2 = p2[i2] + cost_ins;
62 			if (c2 < c0) {
63 				c0 = c2;
64 			}
65 			p2[i2 + 1] = c0;
66 		}
67 		tmp = p1;
68 		p1 = p2;
69 		p2 = tmp;
70 	}
71 	c0 = p1[l2];
72 
73 	efree(p1);
74 	efree(p2);
75 
76 	return c0;
77 }
78 /* }}} */
79 
80 /* {{{ custom_levdist
81  */
custom_levdist(char * str1,char * str2,char * callback_name)82 static int custom_levdist(char *str1, char *str2, char *callback_name)
83 {
84 	php_error_docref(NULL, E_WARNING, "The general Levenshtein support is not there yet");
85 	/* not there yet */
86 
87 	return -1;
88 }
89 /* }}} */
90 
91 /* {{{ proto int levenshtein(string str1, string str2[, int cost_ins, int cost_rep, int cost_del])
92    Calculate Levenshtein distance between two strings */
PHP_FUNCTION(levenshtein)93 PHP_FUNCTION(levenshtein)
94 {
95 	int argc = ZEND_NUM_ARGS();
96 	char *str1, *str2;
97 	char *callback_name;
98 	size_t str1_len, str2_len, callback_len;
99 	zend_long cost_ins, cost_rep, cost_del;
100 	zend_long distance = -1;
101 
102 	switch (argc) {
103 		case 2: /* just two strings: use maximum performance version */
104 			if (zend_parse_parameters(2, "ss", &str1, &str1_len, &str2, &str2_len) == FAILURE) {
105 				return;
106 			}
107 			distance = reference_levdist(str1, str1_len, str2, str2_len, 1, 1, 1);
108 			break;
109 
110 		case 5: /* more general version: calc cost by ins/rep/del weights */
111 			if (zend_parse_parameters(5, "sslll", &str1, &str1_len, &str2, &str2_len, &cost_ins, &cost_rep, &cost_del) == FAILURE) {
112 				return;
113 			}
114 			distance = reference_levdist(str1, str1_len, str2, str2_len, cost_ins, cost_rep, cost_del);
115 			break;
116 
117 		case 3: /* most general version: calc cost by user-supplied function */
118 			if (zend_parse_parameters(3, "sss", &str1, &str1_len, &str2, &str2_len, &callback_name, &callback_len) == FAILURE) {
119 				return;
120 			}
121 			distance = custom_levdist(str1, str2, callback_name);
122 			break;
123 
124 		default:
125 			WRONG_PARAM_COUNT;
126 	}
127 
128 	if (distance < 0 && /* TODO */ ZEND_NUM_ARGS() != 3) {
129 		php_error_docref(NULL, E_WARNING, "Argument string(s) too long");
130 	}
131 
132 	RETURN_LONG(distance);
133 }
134 /* }}} */
135 
136 /*
137  * Local variables:
138  * tab-width: 4
139  * c-basic-offset: 4
140  * End:
141  * vim600: sw=4 ts=4 fdm=marker
142  * vim<600: sw=4 ts=4
143  */
144