1da2e3ebchin/***********************************************************************
2da2e3ebchin*                                                                      *
3da2e3ebchin*               This software is part of the ast package               *
43e14f97Roger A. Faulkner*          Copyright (c) 1985-2010 AT&T Intellectual Property          *
5da2e3ebchin*                      and is licensed under the                       *
6da2e3ebchin*                  Common Public License, Version 1.0                  *
77c2fbfbApril Chin*                    by AT&T Intellectual Property                     *
8da2e3ebchin*                                                                      *
9da2e3ebchin*                A copy of the License is available at                 *
10da2e3ebchin*            http://www.opensource.org/licenses/cpl1.0.txt             *
11da2e3ebchin*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
12da2e3ebchin*                                                                      *
13da2e3ebchin*              Information and Software Systems Research               *
14da2e3ebchin*                            AT&T Research                             *
15da2e3ebchin*                           Florham Park NJ                            *
16da2e3ebchin*                                                                      *
17da2e3ebchin*                 Glenn Fowler <gsf@research.att.com>                  *
18da2e3ebchin*                  David Korn <dgk@research.att.com>                   *
19da2e3ebchin*                   Phong Vo <kpv@research.att.com>                    *
20da2e3ebchin*                                                                      *
21da2e3ebchin***********************************************************************/
22da2e3ebchin#pragma prototyped
23da2e3ebchin/*
24da2e3ebchin * original code
25da2e3ebchin *
26da2e3ebchin *  	James A. Woods, Informatics General Corporation,
27da2e3ebchin *	NASA Ames Research Center, 6/81.
28da2e3ebchin *	Usenix ;login:, February/March, 1983, p. 8.
29da2e3ebchin *
30da2e3ebchin * discipline/method interface
31da2e3ebchin *
32da2e3ebchin *	Glenn Fowler
33da2e3ebchin *	AT&T Research
34da2e3ebchin *	modified from the original BSD source
35da2e3ebchin *
36da2e3ebchin * 'fastfind' scans a file list for the full pathname of a file
37da2e3ebchin * given only a piece of the name.  The list is processed with
38da2e3ebchin * with "front-compression" and bigram coding.  Front compression reduces
39da2e3ebchin * space by a factor of 4-5, bigram coding by a further 20-25%.
40da2e3ebchin *
41da2e3ebchin * there are 4 methods:
42da2e3ebchin *
43da2e3ebchin *	FF_old	original with 7 bit bigram encoding (no magic)
44da2e3ebchin *	FF_gnu	8 bit clean front compression (FF_gnu_magic)
45da2e3ebchin *	FF_dir	FF_gnu with sfgetl/sfputl and trailing / on dirs (FF_dir_magic)
46da2e3ebchin *	FF_typ	FF_dir with (mime) types (FF_typ_magic)
47da2e3ebchin *
48da2e3ebchin * the bigram encoding steals the eighth bit (that's why its FF_old)
49da2e3ebchin * maybe one day we'll limit it to readonly:
50da2e3ebchin *
51da2e3ebchin * 0-2*FF_OFF	 likeliest differential counts + offset to make nonnegative
52da2e3ebchin * FF_ESC	 4 byte big-endian out-of-range count+FF_OFF follows
53da2e3ebchin * FF_MIN-FF_MAX ascii residue
54da2e3ebchin * >=FF_MAX	 bigram codes
55da2e3ebchin *
56da2e3ebchin * a two-tiered string search technique is employed
57da2e3ebchin *
58da2e3ebchin * a metacharacter-free subpattern and partial pathname is matched
59da2e3ebchin * backwards to avoid full expansion of the pathname list
60da2e3ebchin *
61da2e3ebchin * then the actual shell glob-style regular expression (if in this form)
62da2e3ebchin * is matched against the candidate pathnames using the slower regexec()
63da2e3ebchin *
64da2e3ebchin * The original BSD code is covered by the BSD license:
65da2e3ebchin *
66da2e3ebchin * Copyright (c) 1985, 1993, 1999
67da2e3ebchin *	The Regents of the University of California.  All rights reserved.
68da2e3ebchin *
69da2e3ebchin * Redistribution and use in source and binary forms, with or without
70da2e3ebchin * modification, are permitted provided that the following conditions
71da2e3ebchin * are met:
72da2e3ebchin * 1. Redistributions of source code must retain the above copyright
73da2e3ebchin *    notice, this list of conditions and the following disclaimer.
74da2e3ebchin * 2. Redistributions in binary form must reproduce the above copyright
75da2e3ebchin *    notice, this list of conditions and the following disclaimer in the
76da2e3ebchin *    documentation and/or other materials provided with the distribution.
77da2e3ebchin * 3. Neither the name of the University nor the names of its contributors
78da2e3ebchin *    may be used to endorse or promote products derived from this software
79da2e3ebchin *    without specific prior written permission.
80da2e3ebchin *
81da2e3ebchin * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
82da2e3ebchin * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
83da2e3ebchin * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
84da2e3ebchin * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
85da2e3ebchin * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
86da2e3ebchin * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
87da2e3ebchin * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
88da2e3ebchin * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
89da2e3ebchin * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
90da2e3ebchin * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
91da2e3ebchin * SUCH DAMAGE.
92da2e3ebchin */
93da2e3ebchin
94da2e3ebchinstatic const char id[] = "\n@(#)$Id: fastfind (AT&T Research) 2002-10-02 $\0\n";
95da2e3ebchin
96da2e3ebchinstatic const char lib[] = "libast:fastfind";
97da2e3ebchin
98da2e3ebchin#include "findlib.h"
99da2e3ebchin
100da2e3ebchin#define FIND_MATCH	"*/(find|locate)/*"
101da2e3ebchin
102da2e3ebchin/*
103da2e3ebchin * this db could be anywhere
104da2e3ebchin * findcodes[] directories are checked for findnames[i]
105da2e3ebchin */
106da2e3ebchin
107da2e3ebchinstatic char*		findcodes[] =
108da2e3ebchin{
109da2e3ebchin	0,
110da2e3ebchin	0,
111da2e3ebchin	FIND_CODES,
112da2e3ebchin	"/usr/local/share/lib",
113da2e3ebchin	"/usr/local/lib",
114da2e3ebchin	"/usr/share/lib",
115da2e3ebchin	"/usr/lib",
116da2e3ebchin	"/var/spool",
117da2e3ebchin	"/usr/local/var",
118da2e3ebchin	"/var/lib",
119da2e3ebchin	"/var/lib/slocate",
120da2e3ebchin	"/var/db",
121da2e3ebchin};
122da2e3ebchin
123da2e3ebchinstatic char*		findnames[] =
124da2e3ebchin{
125da2e3ebchin	"find/codes",
126da2e3ebchin	"find/find.codes",
127da2e3ebchin	"locate/locatedb",
128da2e3ebchin	"locatedb",
129da2e3ebchin	"locate.database",
130da2e3ebchin	"slocate.db",
131da2e3ebchin};
132da2e3ebchin
133da2e3ebchin/*
134da2e3ebchin * convert t to lower case and drop leading x- and x- after /
135da2e3ebchin * converted value copied to b of size n
136da2e3ebchin */
137da2e3ebchin
138da2e3ebchinchar*
139da2e3ebchintypefix(char* buf, size_t n, register const char* t)
140da2e3ebchin{
141da2e3ebchin	register int	c;
142da2e3ebchin	register char*	b = buf;
143da2e3ebchin
144da2e3ebchin	if ((*t == 'x' || *t == 'X') && *(t + 1) == '-')
145da2e3ebchin		t += 2;
146da2e3ebchin	while (c = *t++)
147da2e3ebchin	{
148da2e3ebchin		if (isupper(c))
149da2e3ebchin			c = tolower(c);
150da2e3ebchin		if ((*b++ = c) == '/' && (*t == 'x' || *t == 'X') && *(t + 1) == '-')
151da2e3ebchin			t += 2;
152da2e3ebchin	}
153da2e3ebchin	*b = 0;
154da2e3ebchin	return buf;
155da2e3ebchin}
156da2e3ebchin
157da2e3ebchin/*
158da2e3ebchin * return a fastfind stream handle for pattern
159da2e3ebchin */
160da2e3ebchin
161da2e3ebchinFind_t*
162da2e3ebchinfindopen(const char* file, const char* pattern, const char* type, Finddisc_t* disc)
163da2e3ebchin{
164da2e3ebchin	register Find_t*	fp;
165da2e3ebchin	register char*		p;
166da2e3ebchin	register char*		s;
167da2e3ebchin	register char*		b;
168da2e3ebchin	register int		i;
169da2e3ebchin	register int		j;
170da2e3ebchin	char*			path;
171da2e3ebchin	int			brace = 0;
172da2e3ebchin	int			paren = 0;
173da2e3ebchin	int			k;
174da2e3ebchin	int			q;
175da2e3ebchin	int			fd;
176da2e3ebchin	int			uid;
177da2e3ebchin	Vmalloc_t*		vm;
178da2e3ebchin	Type_t*			tp;
179da2e3ebchin	struct stat		st;
180da2e3ebchin
181da2e3ebchin
182da2e3ebchin	if (!(vm = vmopen(Vmdcheap, Vmbest, 0)))
183da2e3ebchin		goto nospace;
184da2e3ebchin
185da2e3ebchin	/*
186da2e3ebchin	 * NOTE: searching for FIND_CODES would be much simpler if we
187da2e3ebchin	 *       just stuck with our own, but we also support GNU
188da2e3ebchin	 *	 locate codes and have to search for the one of a
189da2e3ebchin	 *	 bazillion possible names for that file
190da2e3ebchin	 */
191da2e3ebchin
192da2e3ebchin	if (!findcodes[1])
193da2e3ebchin		findcodes[1] = getenv(FIND_CODES_ENV);
194da2e3ebchin	if (disc->flags & FIND_GENERATE)
195da2e3ebchin	{
196da2e3ebchin		if (!(fp = (Find_t*)vmnewof(vm, 0, Find_t, 1, sizeof(Encode_t) - sizeof(Code_t))))
197da2e3ebchin			goto nospace;
198da2e3ebchin		fp->vm = vm;
199da2e3ebchin		fp->id = lib;
200da2e3ebchin		fp->disc = disc;
201da2e3ebchin		fp->generate = 1;
202da2e3ebchin		if (file && (!*file || streq(file, "-")))
203da2e3ebchin			file = 0;
204da2e3ebchin		uid = geteuid();
205da2e3ebchin		j = (findcodes[0] = (char*)file) && *file == '/' ? 1 : elementsof(findcodes);
206da2e3ebchin
207da2e3ebchin		/*
208da2e3ebchin		 * look for the codes file, but since it may not exist yet,
209da2e3ebchin		 * also look for the containing directory if i<2 or if
210da2e3ebchin		 * it is sufficiently qualified (FIND_MATCH)
211da2e3ebchin		 */
212da2e3ebchin
213da2e3ebchin		for (i = 0; i < j; i++)
214da2e3ebchin			if (path = findcodes[i])
215da2e3ebchin			{
216da2e3ebchin				if (*path == '/')
217da2e3ebchin				{
218da2e3ebchin					if (!stat(path, &st))
219da2e3ebchin					{
220da2e3ebchin						if (S_ISDIR(st.st_mode))
221da2e3ebchin						{
222da2e3ebchin							for (k = 0; k < elementsof(findnames); k++)
223da2e3ebchin							{
224da2e3ebchin								sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%s/%s", path, findnames[k]);
225da2e3ebchin								if (!eaccess(fp->encode.file, R_OK|W_OK))
226da2e3ebchin								{
227da2e3ebchin									path = fp->encode.file;
228da2e3ebchin									break;
229da2e3ebchin								}
230da2e3ebchin								if (strchr(findnames[k], '/') && (b = strrchr(fp->encode.file, '/')))
231da2e3ebchin								{
232da2e3ebchin									*b = 0;
233da2e3ebchin									if (!stat(fp->encode.file, &st) && st.st_uid == uid && (st.st_mode & S_IWUSR))
234da2e3ebchin									{
235da2e3ebchin										*b = '/';
236da2e3ebchin										path = fp->encode.file;
237da2e3ebchin										break;
238da2e3ebchin									}
239da2e3ebchin								}
240da2e3ebchin							}
241da2e3ebchin							if (k < elementsof(findnames))
242da2e3ebchin								break;
243da2e3ebchin						}
244da2e3ebchin						else if (st.st_uid == uid && (st.st_mode & S_IWUSR))
245da2e3ebchin						{
246da2e3ebchin							sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%s", path);
247da2e3ebchin							path = fp->encode.file;
248da2e3ebchin							break;
249da2e3ebchin						}
250da2e3ebchin					}
251da2e3ebchin					else if (i < 2 || strmatch(path, FIND_MATCH))
252da2e3ebchin					{
253da2e3ebchin						sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%s", path);
254da2e3ebchin						if (b = strrchr(fp->encode.file, '/'))
255da2e3ebchin						{
256da2e3ebchin							*b = 0;
257da2e3ebchin							if (!stat(fp->encode.file, &st) && st.st_uid == uid && (st.st_mode & S_IWUSR))
258da2e3ebchin							{
259da2e3ebchin								*b = '/';
260da2e3ebchin								path = fp->encode.file;
261da2e3ebchin								break;
262da2e3ebchin							}
263da2e3ebchin						}
264da2e3ebchin					}
265da2e3ebchin				}
266da2e3ebchin				else if (pathpath(fp->encode.file, path, "", PATH_REGULAR|PATH_READ|PATH_WRITE))
267da2e3ebchin				{
268da2e3ebchin					path = fp->encode.file;
269da2e3ebchin					break;
270da2e3ebchin				}
271da2e3ebchin				else if (b = strrchr(path, '/'))
272da2e3ebchin				{
273da2e3ebchin					sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%-.*s", b - path, path);
274da2e3ebchin					if (pathpath(fp->encode.temp, fp->encode.file, "", PATH_EXECUTE|PATH_READ|PATH_WRITE) &&
275da2e3ebchin					    !stat(fp->encode.temp, &st) && st.st_uid == uid && (st.st_mode & S_IWUSR))
276da2e3ebchin					{
277da2e3ebchin						sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%s%s", fp->encode.temp, b);
278da2e3ebchin						path = fp->encode.file;
279da2e3ebchin						break;
280da2e3ebchin					}
281da2e3ebchin				}
282da2e3ebchin			}
283da2e3ebchin		if (i >= j)
284da2e3ebchin		{
285da2e3ebchin			if (fp->disc->errorf)
286da2e3ebchin				(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot locate codes", file ? file : findcodes[2]);
287da2e3ebchin			goto drop;
288da2e3ebchin		}
289da2e3ebchin		if (fp->disc->flags & FIND_OLD)
290da2e3ebchin		{
291da2e3ebchin			/*
292da2e3ebchin			 * FF_old generates temp data that is read
293da2e3ebchin			 * in a second pass to generate the real codes
294da2e3ebchin			 */
295da2e3ebchin
296da2e3ebchin			fp->method = FF_old;
297da2e3ebchin			if (!(fp->fp = sftmp(32 * PATH_MAX)))
298da2e3ebchin			{
299da2e3ebchin				if (fp->disc->errorf)
300da2e3ebchin					(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "cannot create tmp file");
301da2e3ebchin				goto drop;
302da2e3ebchin			}
303da2e3ebchin		}
304da2e3ebchin		else
305da2e3ebchin		{
306da2e3ebchin			/*
307da2e3ebchin			 * the rest generate into a temp file that
308da2e3ebchin			 * is simply renamed on completion
309da2e3ebchin			 */
310da2e3ebchin
311da2e3ebchin			if (s = strrchr(path, '/'))
312da2e3ebchin			{
313da2e3ebchin				*s = 0;
314da2e3ebchin				p = path;
315da2e3ebchin			}
316da2e3ebchin			else
317da2e3ebchin				p = ".";
318da2e3ebchin			if (!pathtemp(fp->encode.temp, sizeof(fp->encode.temp), p, "ff", &fd))
319da2e3ebchin			{
320da2e3ebchin				if (fp->disc->errorf)
321da2e3ebchin					(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "%s: cannot create tmp file in this directory", p ? p : ".");
322da2e3ebchin				goto drop;
323da2e3ebchin			}
324da2e3ebchin			if (s)
325da2e3ebchin				*s = '/';
326da2e3ebchin			if (!(fp->fp = sfnew(NiL, NiL, (size_t)SF_UNBOUND, fd, SF_WRITE)))
327da2e3ebchin			{
328da2e3ebchin				if (fp->disc->errorf)
329da2e3ebchin					(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "%s: cannot open tmp file", fp->encode.temp);
330da2e3ebchin				close(fd);
331da2e3ebchin				goto drop;
332da2e3ebchin			}
333da2e3ebchin			if (fp->disc->flags & FIND_TYPE)
334da2e3ebchin			{
335da2e3ebchin				fp->method = FF_typ;
336da2e3ebchin				fp->encode.namedisc.key = offsetof(Type_t, name);
337da2e3ebchin				fp->encode.namedisc.link = offsetof(Type_t, byname);
338da2e3ebchin				fp->encode.indexdisc.key = offsetof(Type_t, index);
339da2e3ebchin				fp->encode.indexdisc.size = sizeof(unsigned long);
340da2e3ebchin				fp->encode.indexdisc.link = offsetof(Type_t, byindex);
341da2e3ebchin				s = "system/dir";
342da2e3ebchin				if (!(fp->encode.namedict = dtopen(&fp->encode.namedisc, Dttree)) || !(fp->encode.indexdict = dtopen(&fp->encode.indexdisc, Dttree)) || !(tp = newof(0, Type_t, 1, strlen(s) + 1)))
343da2e3ebchin				{
344da2e3ebchin					if (fp->encode.namedict)
345da2e3ebchin						dtclose(fp->encode.namedict);
346da2e3ebchin					if (fp->disc->errorf)
347da2e3ebchin						(*fp->disc->errorf)(fp, fp->disc, 2, "cannot allocate type table");
348da2e3ebchin					goto drop;
349da2e3ebchin				}
350da2e3ebchin
351da2e3ebchin				/*
352da2e3ebchin				 * type index 1 is always system/dir
353da2e3ebchin				 */
354da2e3ebchin
355da2e3ebchin				tp->index = ++fp->types;
356da2e3ebchin				strcpy(tp->name, s);
357da2e3ebchin				dtinsert(fp->encode.namedict, tp);
358da2e3ebchin				dtinsert(fp->encode.indexdict, tp);
359da2e3ebchin			}
360da2e3ebchin			else if (fp->disc->flags & FIND_GNU)
361da2e3ebchin			{
362da2e3ebchin				fp->method = FF_gnu;
363da2e3ebchin				sfputc(fp->fp, 0);
364da2e3ebchin				sfputr(fp->fp, FF_gnu_magic, 0);
365da2e3ebchin			}
366da2e3ebchin			else
367da2e3ebchin			{
368da2e3ebchin				fp->method = FF_dir;
369da2e3ebchin				sfputc(fp->fp, 0);
370da2e3ebchin				sfputr(fp->fp, FF_dir_magic, 0);
371da2e3ebchin			}
372da2e3ebchin		}
373da2e3ebchin	}
374da2e3ebchin	else
375da2e3ebchin	{
376da2e3ebchin		i = sizeof(Decode_t) + sizeof(Code_t);
377da2e3ebchin		if (!pattern || !*pattern)
378da2e3ebchin			pattern = "*";
379da2e3ebchin		i += (j = 2 * (strlen(pattern) + 1));
380da2e3ebchin		if (!(fp = (Find_t*)vmnewof(vm, 0, Find_t, 1, i)))
381da2e3ebchin		{
382da2e3ebchin			vmclose(vm);
383da2e3ebchin			return 0;
384da2e3ebchin		}
385da2e3ebchin		fp->vm = vm;
386da2e3ebchin		fp->id = lib;
387da2e3ebchin		fp->disc = disc;
388da2e3ebchin		if (disc->flags & FIND_ICASE)
389da2e3ebchin			fp->decode.ignorecase = 1;
390da2e3ebchin		j = (findcodes[0] = (char*)file) && *file == '/' ? 1 : elementsof(findcodes);
391da2e3ebchin		for (i = 0; i < j; i++)
392da2e3ebchin			if (path = findcodes[i])
393da2e3ebchin			{
394da2e3ebchin				if (*path == '/')
395da2e3ebchin				{
396da2e3ebchin					if (!stat(path, &st))
397da2e3ebchin					{
398da2e3ebchin						if (S_ISDIR(st.st_mode))
399da2e3ebchin						{
400da2e3ebchin							for (k = 0; k < elementsof(findnames); k++)
401da2e3ebchin							{
402da2e3ebchin								sfsprintf(fp->decode.path, sizeof(fp->decode.path), "%s/%s", path, findnames[k]);
403da2e3ebchin								if (fp->fp = sfopen(NiL, fp->decode.path, "r"))
404da2e3ebchin								{
405da2e3ebchin									path = fp->decode.path;
406da2e3ebchin									break;
407da2e3ebchin								}
408da2e3ebchin							}
409da2e3ebchin							if (fp->fp)
410da2e3ebchin								break;
411da2e3ebchin						}
412da2e3ebchin						else if (fp->fp = sfopen(NiL, path, "r"))
413da2e3ebchin							break;
414da2e3ebchin					}
415da2e3ebchin				}
416da2e3ebchin				else if ((path = pathpath(fp->decode.path, path, "", PATH_REGULAR|PATH_READ)) && (fp->fp = sfopen(NiL, path, "r")))
417da2e3ebchin					break;
418da2e3ebchin			}
419da2e3ebchin		if (!fp->fp)
420da2e3ebchin		{
421da2e3ebchin			if (fp->disc->errorf)
422da2e3ebchin				(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot locate codes", file ? file : findcodes[2]);
423da2e3ebchin			goto drop;
424da2e3ebchin		}
425da2e3ebchin		if (fstat(sffileno(fp->fp), &st))
426da2e3ebchin		{
427da2e3ebchin			if (fp->disc->errorf)
428da2e3ebchin				(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot stat codes", path);
429da2e3ebchin			goto drop;
430da2e3ebchin		}
431da2e3ebchin		if (fp->secure = ((st.st_mode & (S_IRGRP|S_IROTH)) == S_IRGRP) && st.st_gid == getegid() && getegid() != getgid())
432da2e3ebchin			setgid(getgid());
433da2e3ebchin		fp->stamp = st.st_mtime;
434da2e3ebchin		b = (s = fp->decode.temp) + 1;
435da2e3ebchin		for (i = 0; i < elementsof(fp->decode.bigram1); i++)
436da2e3ebchin		{
437da2e3ebchin			if ((j = sfgetc(fp->fp)) == EOF)
438da2e3ebchin				goto invalid;
439da2e3ebchin			if (!(*s++ = fp->decode.bigram1[i] = j) && i)
440da2e3ebchin			{
441da2e3ebchin				i = -i;
442da2e3ebchin				break;
443da2e3ebchin			}
444da2e3ebchin			if ((j = sfgetc(fp->fp)) == EOF)
445da2e3ebchin				goto invalid;
446da2e3ebchin			if (!(*s++ = fp->decode.bigram2[i] = j) && (i || fp->decode.bigram1[0] >= '0' && fp->decode.bigram1[0] <= '1'))
447da2e3ebchin				break;
448da2e3ebchin		}
449da2e3ebchin		if (streq(b, FF_typ_magic))
450da2e3ebchin		{
451da2e3ebchin			if (type)
452da2e3ebchin			{
453da2e3ebchin				type = (const char*)typefix(fp->decode.bigram2, sizeof(fp->decode.bigram2), type);
454da2e3ebchin				memset(fp->decode.bigram1, 0, sizeof(fp->decode.bigram1));
455da2e3ebchin			}
456da2e3ebchin			fp->method = FF_typ;
457da2e3ebchin			for (j = 0, i = 1;; i++)
458da2e3ebchin			{
459da2e3ebchin				if (!(s = sfgetr(fp->fp, 0, 0)))
460da2e3ebchin					goto invalid;
461da2e3ebchin				if (!*s)
462da2e3ebchin					break;
463da2e3ebchin				if (type && strmatch(s, type))
464da2e3ebchin				{
465da2e3ebchin					FF_SET_TYPE(fp, i);
466da2e3ebchin					j++;
467da2e3ebchin				}
468da2e3ebchin			}
469da2e3ebchin			if (type && !j)
470da2e3ebchin				goto drop;
471da2e3ebchin			fp->types = j;
472da2e3ebchin		}
473da2e3ebchin		else if (streq(b, FF_dir_magic))
474da2e3ebchin			fp->method = FF_dir;
475da2e3ebchin		else if (streq(b, FF_gnu_magic))
476da2e3ebchin			fp->method = FF_gnu;
477da2e3ebchin		else if (!*b && *--b >= '0' && *b <= '1')
478da2e3ebchin		{
479da2e3ebchin			fp->method = FF_gnu;
480da2e3ebchin			while (j = sfgetc(fp->fp))
481da2e3ebchin			{
482da2e3ebchin				if (j == EOF || fp->decode.count >= sizeof(fp->decode.path))
483da2e3ebchin					goto invalid;
484da2e3ebchin				fp->decode.path[fp->decode.count++] = j;
485da2e3ebchin			}
486da2e3ebchin		}
487da2e3ebchin		else
488da2e3ebchin		{
489da2e3ebchin			fp->method = FF_old;
490da2e3ebchin			if (i < 0)
491da2e3ebchin			{
492da2e3ebchin				if ((j = sfgetc(fp->fp)) == EOF)
493da2e3ebchin					goto invalid;
494da2e3ebchin				fp->decode.bigram2[i = -i] = j;
495da2e3ebchin			}
496da2e3ebchin			while (++i < elementsof(fp->decode.bigram1))
497da2e3ebchin			{
498da2e3ebchin				if ((j = sfgetc(fp->fp)) == EOF)
499da2e3ebchin					goto invalid;
500da2e3ebchin				fp->decode.bigram1[i] = j;
501da2e3ebchin				if ((j = sfgetc(fp->fp)) == EOF)
502da2e3ebchin					goto invalid;
503da2e3ebchin				fp->decode.bigram2[i] = j;
504da2e3ebchin			}
505da2e3ebchin			if ((fp->decode.peek = sfgetc(fp->fp)) != FF_OFF)
506da2e3ebchin				goto invalid;
507da2e3ebchin		}
508da2e3ebchin
509da2e3ebchin		/*
510da2e3ebchin		 * set up the physical dir table
511da2e3ebchin		 */
512da2e3ebchin
513da2e3ebchin		if (disc->version >= 19980301L)
514da2e3ebchin		{
515da2e3ebchin			fp->verifyf = disc->verifyf;
516da2e3ebchin			if (disc->dirs && *disc->dirs)
517da2e3ebchin			{
518da2e3ebchin				for (k = 0; disc->dirs[k]; k++);
519da2e3ebchin				if (k == 1 && streq(disc->dirs[0], "/"))
520da2e3ebchin					k = 0;
521da2e3ebchin				if (k)
522da2e3ebchin				{
523da2e3ebchin					if (!(fp->dirs = vmnewof(fp->vm, 0, char*, 2 * k + 1, 0)))
524da2e3ebchin						goto drop;
525da2e3ebchin					if (!(fp->lens = vmnewof(fp->vm, 0, int, 2 * k, 0)))
526da2e3ebchin						goto drop;
527da2e3ebchin					p = 0;
528da2e3ebchin					b = fp->decode.temp;
529da2e3ebchin					j = fp->method == FF_old || fp->method == FF_gnu;
530da2e3ebchin
531da2e3ebchin					/*
532da2e3ebchin					 * fill the dir list with logical and
533da2e3ebchin					 * physical names since we don't know
534da2e3ebchin					 * which way the db was encoded (it
535da2e3ebchin					 * could be *both* ways)
536da2e3ebchin					 */
537da2e3ebchin
538da2e3ebchin					for (i = q = 0; i < k; i++)
539da2e3ebchin					{
540da2e3ebchin						if (*(s = disc->dirs[i]) == '/')
541da2e3ebchin							sfsprintf(b, sizeof(fp->decode.temp) - 1, "%s", s);
542da2e3ebchin						else if (!p && !(p = getcwd(fp->decode.path, sizeof(fp->decode.path))))
543da2e3ebchin							goto nospace;
544da2e3ebchin						else
545da2e3ebchin							sfsprintf(b, sizeof(fp->decode.temp) - 1, "%s/%s", p, s);
546da2e3ebchin						s = pathcanon(b, 0);
547da2e3ebchin						*s = '/';
548da2e3ebchin						*(s + 1) = 0;
549da2e3ebchin						if (!(fp->dirs[q] = vmstrdup(fp->vm, b)))
550da2e3ebchin							goto nospace;
551da2e3ebchin						if (j)
552da2e3ebchin							(fp->dirs[q])[s - b] = 0;
553da2e3ebchin						q++;
554da2e3ebchin						*s = 0;
555da2e3ebchin						s = pathcanon(b, PATH_PHYSICAL);
556da2e3ebchin						*s = '/';
557da2e3ebchin						*(s + 1) = 0;
558da2e3ebchin						if (!strneq(b, fp->dirs[q - 1], s - b))
559da2e3ebchin						{
560da2e3ebchin							if (!(fp->dirs[q] = vmstrdup(fp->vm, b)))
561da2e3ebchin								goto nospace;
562da2e3ebchin							if (j)
563da2e3ebchin								(fp->dirs[q])[s - b] = 0;
564da2e3ebchin							q++;
565da2e3ebchin						}
566da2e3ebchin					}
567da2e3ebchin					strsort(fp->dirs, q, strcasecmp);
568da2e3ebchin					for (i = 0; i < q; i++)
569da2e3ebchin						fp->lens[i] = strlen(fp->dirs[i]);
570da2e3ebchin				}
571da2e3ebchin			}
572da2e3ebchin		}
573da2e3ebchin		if (fp->verifyf || (disc->flags & FIND_VERIFY))
574da2e3ebchin		{
575da2e3ebchin			if (fp->method != FF_dir && fp->method != FF_typ)
576da2e3ebchin			{
577da2e3ebchin				if (fp->disc->errorf)
578da2e3ebchin					(*fp->disc->errorf)(fp, fp->disc, 2, "%s: %s code format does not support directory verification", path, fp->method == FF_gnu ? FF_gnu_magic : "OLD-BIGRAM");
579da2e3ebchin				goto drop;
580da2e3ebchin			}
581da2e3ebchin			fp->verify = 1;
582da2e3ebchin		}
583da2e3ebchin
584da2e3ebchin		/*
585da2e3ebchin		 * extract last glob-free subpattern in name for fast pre-match
586da2e3ebchin		 * prepend 0 for backwards match
587da2e3ebchin		 */
588da2e3ebchin
589da2e3ebchin		if (p = s = (char*)pattern)
590da2e3ebchin		{
591da2e3ebchin			b = fp->decode.pattern;
592da2e3ebchin			for (;;)
593da2e3ebchin			{
594da2e3ebchin				switch (*b++ = *p++)
595da2e3ebchin				{
596da2e3ebchin				case 0:
597da2e3ebchin					break;
598da2e3ebchin				case '\\':
599da2e3ebchin					s = p;
600da2e3ebchin					if (!*p++)
601da2e3ebchin						break;
602da2e3ebchin					continue;
603da2e3ebchin				case '[':
604da2e3ebchin					if (!brace)
605da2e3ebchin					{
606da2e3ebchin						brace++;
607da2e3ebchin						if (*p == ']')
608da2e3ebchin							p++;
609da2e3ebchin					}
610da2e3ebchin					continue;
611da2e3ebchin				case ']':
612da2e3ebchin					if (brace)
613da2e3ebchin					{
614da2e3ebchin						brace--;
615da2e3ebchin						s = p;
616da2e3ebchin					}
617da2e3ebchin					continue;
618da2e3ebchin				case '(':
619da2e3ebchin					if (!brace)
620da2e3ebchin						paren++;
621da2e3ebchin					continue;
622da2e3ebchin				case ')':
623da2e3ebchin					if (!brace && paren > 0 && !--paren)
624da2e3ebchin						s = p;
625da2e3ebchin					continue;
626da2e3ebchin				case '|':
627da2e3ebchin				case '&':
628da2e3ebchin					if (!brace && !paren)
629da2e3ebchin					{
630da2e3ebchin						s = "";
631da2e3ebchin						break;
632da2e3ebchin					}
633