xref: /PHP-7.3/ext/dba/libcdb/cdb_make.c (revision a6519d05)
1 /*
2    +----------------------------------------------------------------------+
3    | PHP Version 7                                                        |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 1997-2018 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: Marcus Boerger <helly@php.net>                               |
16    +----------------------------------------------------------------------+
17  */
18 
19 /* $Id: 92cfbe7421bcb318d3fd0c02b188921d38296ef8 $ */
20 
21 /* incorporated from D.J.Bernstein's cdb-0.75 (http://cr.yp.to/cdb.html)*/
22 
23 #ifdef HAVE_CONFIG_H
24 #include "config.h"
25 #endif
26 
27 #include "php.h"
28 
29 #include <sys/types.h>
30 #ifdef HAVE_UNISTD_H
31 #include <unistd.h>
32 #endif
33 #include <stdlib.h>
34 #include <stdio.h>
35 #include <errno.h>
36 #include "cdb.h"
37 #include "cdb_make.h"
38 #include "uint32.h"
39 
40 /* {{{ cdb_make_write */
cdb_make_write(struct cdb_make * c,char * buf,uint32 sz)41 static int cdb_make_write(struct cdb_make *c, char *buf, uint32 sz) {
42 	return php_stream_write(c->fp, buf, sz) == sz ? 0 : -1;
43 }
44 
45 /* {{{ cdb_posplus */
cdb_posplus(struct cdb_make * c,uint32 len)46 static int cdb_posplus(struct cdb_make *c, uint32 len)
47 {
48 	uint32 newpos = c->pos + len;
49 	if (newpos < len) {
50 		errno = ENOMEM;
51 		return -1;
52 	}
53 	c->pos = newpos;
54 	return 0;
55 }
56 /* }}} */
57 
58 /* {{{ cdb_make_start */
cdb_make_start(struct cdb_make * c,php_stream * f)59 int cdb_make_start(struct cdb_make *c, php_stream * f)
60 {
61 	c->head = 0;
62 	c->split = 0;
63 	c->hash = 0;
64 	c->numentries = 0;
65 	c->fp = f;
66 	c->pos = sizeof(c->final);
67 	if (php_stream_seek(f, c->pos, SEEK_SET) == -1) {
68 		php_error_docref(NULL, E_NOTICE, "Fseek failed");
69 		return -1;
70 	}
71 	return php_stream_tell(c->fp);
72 }
73 /* }}} */
74 
75 /* {{{ cdb_make_addend */
cdb_make_addend(struct cdb_make * c,unsigned int keylen,unsigned int datalen,uint32 h)76 int cdb_make_addend(struct cdb_make *c, unsigned int keylen, unsigned int datalen, uint32 h)
77 {
78 	struct cdb_hplist *head;
79 
80 	head = c->head;
81 	if (!head || (head->num >= CDB_HPLIST)) {
82 		head = (struct cdb_hplist *) emalloc(sizeof(struct cdb_hplist));
83 		if (!head)
84 			return -1;
85 		head->num = 0;
86 		head->next = c->head;
87 		c->head = head;
88 	}
89 	head->hp[head->num].h = h;
90 	head->hp[head->num].p = c->pos;
91 	++head->num;
92 	++c->numentries;
93 	if (cdb_posplus(c,8) == -1)
94 		return -1;
95 	if (cdb_posplus(c, keylen) == -1)
96 		return -1;
97 	if (cdb_posplus(c, datalen) == -1)
98 		return -1;
99 	return 0;
100 }
101 /* }}} */
102 
103 /* {{{ cdb_make_addbegin */
cdb_make_addbegin(struct cdb_make * c,unsigned int keylen,unsigned int datalen)104 int cdb_make_addbegin(struct cdb_make *c, unsigned int keylen, unsigned int datalen)
105 {
106 	char buf[8];
107 
108 	if (keylen > 0xffffffff) {
109 		errno = ENOMEM;
110 		return -1;
111 	}
112 	if (datalen > 0xffffffff) {
113 		errno = ENOMEM;
114 		return -1;
115 	}
116 
117 	uint32_pack(buf, keylen);
118 	uint32_pack(buf + 4, datalen);
119 	if (cdb_make_write(c, buf, 8) != 0)
120 		return -1;
121 	return 0;
122 }
123 
124 /* {{{ cdb_make_add */
cdb_make_add(struct cdb_make * c,char * key,unsigned int keylen,char * data,unsigned int datalen)125 int cdb_make_add(struct cdb_make *c,char *key,unsigned int keylen,char *data,unsigned int datalen)
126 {
127 	if (cdb_make_addbegin(c, keylen, datalen) == -1)
128 		return -1;
129 	if (cdb_make_write(c, key, keylen) != 0)
130 		return -1;
131 	if (cdb_make_write(c, data, datalen) != 0)
132 		return -1;
133 	return cdb_make_addend(c, keylen, datalen, cdb_hash(key, keylen));
134 }
135 /* }}} */
136 
137 /* {{{ cdb_make_finish */
cdb_make_finish(struct cdb_make * c)138 int cdb_make_finish(struct cdb_make *c)
139 {
140 	char buf[8];
141 	int i;
142 	uint32 len;
143 	uint32 u;
144 	uint32 memsize;
145 	uint32 count;
146 	uint32 where;
147 	struct cdb_hplist *x;
148 	struct cdb_hp *hp;
149 
150 	for (i = 0;i < 256;++i)
151 	c->count[i] = 0;
152 
153 	for (x = c->head; x; x = x->next) {
154 		i = x->num;
155 		while (i--)
156 		++c->count[255 & x->hp[i].h];
157 	}
158 
159 	memsize = 1;
160 	for (i = 0;i < 256;++i) {
161 		u = c->count[i] * 2;
162 		if (u > memsize)
163 		memsize = u;
164 	}
165 
166 	memsize += c->numentries; /* no overflow possible up to now */
167 	u = (uint32) 0 - (uint32) 1;
168 	u /= sizeof(struct cdb_hp);
169 	if (memsize > u) {
170 		errno = ENOMEM;
171 		return -1;
172 	}
173 
174 	c->split = (struct cdb_hp *) safe_emalloc(memsize, sizeof(struct cdb_hp), 0);
175 	if (!c->split)
176 		return -1;
177 
178 	c->hash = c->split + c->numentries;
179 
180 	u = 0;
181 	for (i = 0;i < 256;++i) {
182 		u += c->count[i]; /* bounded by numentries, so no overflow */
183 		c->start[i] = u;
184 	}
185 
186 	for (x = c->head; x; x = x->next) {
187 		i = x->num;
188 		while (i--)
189 		c->split[--c->start[255 & x->hp[i].h]] = x->hp[i];
190 	}
191 
192 	for (i = 0;i < 256;++i) {
193 		count = c->count[i];
194 
195 		len = count + count; /* no overflow possible */
196 		uint32_pack(c->final + 8 * i,c->pos);
197 		uint32_pack(c->final + 8 * i + 4,len);
198 
199 		for (u = 0;u < len;++u)
200 			c->hash[u].h = c->hash[u].p = 0;
201 
202 		hp = c->split + c->start[i];
203 		for (u = 0;u < count;++u) {
204 			where = (hp->h >> 8) % len;
205 			while (c->hash[where].p)
206 				if (++where == len)
207 					where = 0;
208 			c->hash[where] = *hp++;
209 		}
210 
211 		for (u = 0;u < len;++u) {
212 			uint32_pack(buf, c->hash[u].h);
213 			uint32_pack(buf + 4, c->hash[u].p);
214 			if (cdb_make_write(c, buf, 8) != 0)
215 				return -1;
216 			if (cdb_posplus(c, 8) == -1)
217 				return -1;
218 		}
219 	}
220 
221 	if (c->split)
222 		efree(c->split);
223 
224 	for (x = c->head; x; c->head = x) {
225 		x = x->next;
226 		efree(c->head);
227 	}
228 
229 	if (php_stream_flush(c->fp) != 0)
230 		return -1;
231 	php_stream_rewind(c->fp);
232 	if (php_stream_tell(c->fp) != 0)
233 		return -1;
234 	if (cdb_make_write(c, c->final, sizeof(c->final)) != 0)
235 		return -1;
236 	return php_stream_flush(c->fp);
237 }
238 /* }}} */
239 
240 /* {{{ cdb_make_version */
cdb_make_version()241 char *cdb_make_version()
242 {
243 	return "0.75, $Id: 92cfbe7421bcb318d3fd0c02b188921d38296ef8 $";
244 }
245