1 /*
2    +----------------------------------------------------------------------+
3    | PHP Version 7                                                        |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 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 
19 #include "php.h"
20 #include <stdlib.h>
21 #include <errno.h>
22 #include <ctype.h>
23 #include "php_string.h"
24 
25 #define LEVENSHTEIN_MAX_LENGTH 255
26 
27 /* {{{ reference_levdist
28  * 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 )29 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 )
30 {
31 	zend_long *p1, *p2, *tmp;
32 	zend_long c0, c1, c2;
33 	size_t i1, i2;
34 
35 	if (l1 == 0) {
36 		return l2 * cost_ins;
37 	}
38 	if (l2 == 0) {
39 		return l1 * cost_del;
40 	}
41 
42 	if ((l1 > LEVENSHTEIN_MAX_LENGTH) || (l2 > LEVENSHTEIN_MAX_LENGTH)) {
43 		return -1;
44 	}
45 	p1 = safe_emalloc((l2 + 1), sizeof(zend_long), 0);
46 	p2 = safe_emalloc((l2 + 1), sizeof(zend_long), 0);
47 
48 	for (i2 = 0; i2 <= l2; i2++) {
49 		p1[i2] = i2 * cost_ins;
50 	}
51 	for (i1 = 0; i1 < l1 ; i1++) {
52 		p2[0] = p1[0] + cost_del;
53 
54 		for (i2 = 0; i2 < l2; i2++) {
55 			c0 = p1[i2] + ((s1[i1] == s2[i2]) ? 0 : cost_rep);
56 			c1 = p1[i2 + 1] + cost_del;
57 			if (c1 < c0) {
58 				c0 = c1;
59 			}
60 			c2 = p2[i2] + cost_ins;
61 			if (c2 < c0) {
62 				c0 = c2;
63 			}
64 			p2[i2 + 1] = c0;
65 		}
66 		tmp = p1;
67 		p1 = p2;
68 		p2 = tmp;
69 	}
70 	c0 = p1[l2];
71 
72 	efree(p1);
73 	efree(p2);
74 
75 	return c0;
76 }
77 /* }}} */
78 
79 /* {{{ custom_levdist
80  */
custom_levdist(char *str1, char *str2, char *callback_name)81 static int custom_levdist(char *str1, char *str2, char *callback_name)
82 {
83 	php_error_docref(NULL, E_WARNING, "The general Levenshtein support is not there yet");
84 	/* not there yet */
85 
86 	return -1;
87 }
88 /* }}} */
89 
90 /* {{{ proto int levenshtein(string str1, string str2[, int cost_ins, int cost_rep, int cost_del])
91    Calculate Levenshtein distance between two strings */
PHP_FUNCTIONnull92 PHP_FUNCTION(levenshtein)
93 {
94 	int argc = ZEND_NUM_ARGS();
95 	char *str1, *str2;
96 	char *callback_name;
97 	size_t str1_len, str2_len, callback_len;
98 	zend_long cost_ins, cost_rep, cost_del;
99 	zend_long distance = -1;
100 
101 	switch (argc) {
102 		case 2: /* just two strings: use maximum performance version */
103 			if (zend_parse_parameters(2, "ss", &str1, &str1_len, &str2, &str2_len) == FAILURE) {
104 				return;
105 			}
106 			distance = reference_levdist(str1, str1_len, str2, str2_len, 1, 1, 1);
107 			break;
108 
109 		case 5: /* more general version: calc cost by ins/rep/del weights */
110 			if (zend_parse_parameters(5, "sslll", &str1, &str1_len, &str2, &str2_len, &cost_ins, &cost_rep, &cost_del) == FAILURE) {
111 				return;
112 			}
113 			distance = reference_levdist(str1, str1_len, str2, str2_len, cost_ins, cost_rep, cost_del);
114 			break;
115 
116 		case 3: /* most general version: calc cost by user-supplied function */
117 			if (zend_parse_parameters(3, "sss", &str1, &str1_len, &str2, &str2_len, &callback_name, &callback_len) == FAILURE) {
118 				return;
119 			}
120 			distance = custom_levdist(str1, str2, callback_name);
121 			break;
122 
123 		default:
124 			WRONG_PARAM_COUNT;
125 	}
126 
127 	if (distance < 0 && /* TODO */ ZEND_NUM_ARGS() != 3) {
128 		php_error_docref(NULL, E_WARNING, "Argument string(s) too long");
129 	}
130 
131 	RETURN_LONG(distance);
132 }
133 /* }}} */
134