blob: d18ab7744246bd286fbc8a67117c320a29169700 [file] [log] [blame]
Rich Felker41421d62014-07-26 02:34:09 -04001#include <stdint.h>
2#include <string.h>
3
4static inline uint32_t swapc(uint32_t x, int c)
5{
6 return c ? x>>24 | x>>8&0xff00 | x<<8&0xff0000 | x<<24 : x;
7}
8
9const char *__mo_lookup(const void *p, size_t size, const char *s)
10{
11 const uint32_t *mo = p;
12 int sw = *mo - 0x950412de;
13 uint32_t b = 0, n = swapc(mo[2], sw);
14 uint32_t o = swapc(mo[3], sw);
15 uint32_t t = swapc(mo[4], sw);
16 if (n>=size/4 || o>=size-4*n || t>=size-4*n || ((o|t)%4))
17 return 0;
18 o/=4;
19 t/=4;
20 for (;;) {
Rich Felker6e892102014-07-29 11:48:36 -040021 uint32_t ol = swapc(mo[o+2*(b+n/2)], sw);
Rich Felker41421d62014-07-26 02:34:09 -040022 uint32_t os = swapc(mo[o+2*(b+n/2)+1], sw);
Rich Felker6e892102014-07-29 11:48:36 -040023 if (os >= size || ol >= size-os || ((char *)p)[os+ol])
24 return 0;
Rich Felker41421d62014-07-26 02:34:09 -040025 int sign = strcmp(s, (char *)p + os);
26 if (!sign) {
Rich Felker6e892102014-07-29 11:48:36 -040027 uint32_t tl = swapc(mo[t+2*(b+n/2)], sw);
Rich Felker41421d62014-07-26 02:34:09 -040028 uint32_t ts = swapc(mo[t+2*(b+n/2)+1], sw);
Rich Felker6e892102014-07-29 11:48:36 -040029 if (ts >= size || tl >= size-ts || ((char *)p)[ts+tl])
30 return 0;
Rich Felker41421d62014-07-26 02:34:09 -040031 return (char *)p + ts;
32 }
33 else if (n == 1) return 0;
34 else if (sign < 0)
35 n /= 2;
36 else {
37 b += n/2;
38 n -= n/2;
39 }
40 }
41 return 0;
42}