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_FUNCTION(levenshtein)92 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
