123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186 |
- /*
- * lmo - Lua Machine Objects - Base functions
- *
- * Copyright (C) 2009-2010 Jo-Philipp Wich <jow@openwrt.org>
- * Copyright (C) 2018 Matthias Schiffer <mschiffer@universe-factory.net>
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
- #include "template_lmo.h"
- #include <sys/stat.h>
- #include <sys/mman.h>
- #include <arpa/inet.h>
- #include <fcntl.h>
- #include <stdio.h>
- #include <stdint.h>
- #include <stdlib.h>
- #include <string.h>
- #include <unistd.h>
- struct lmo_entry {
- uint32_t key_id;
- uint32_t val_id;
- uint32_t offset;
- uint32_t length;
- } __attribute__((packed));
- static inline uint16_t get_le16(const void *data) {
- const uint8_t *d = data;
- return (((uint16_t)d[1]) << 8) | d[0];
- }
- static inline uint32_t get_be32(const void *data) {
- const uint8_t *d = data;
- return (((uint32_t)d[0]) << 24)
- | (((uint32_t)d[1]) << 16)
- | (((uint32_t)d[2]) << 8)
- | d[3];
- }
- /*
- * Hash function from http://www.azillionmonkeys.com/qed/hash.html
- * Copyright (C) 2004-2008 by Paul Hsieh
- */
- static uint32_t sfh_hash(const void *input, size_t len)
- {
- const uint8_t *data = input;
- uint32_t hash = len, tmp;
- /* Main loop */
- for (; len > 3; len -= 4) {
- hash += get_le16(data);
- tmp = (get_le16(data+2) << 11) ^ hash;
- hash = (hash << 16) ^ tmp;
- data += 4;
- hash += hash >> 11;
- }
- /* Handle end cases */
- switch (len) {
- case 3: hash += get_le16(data);
- hash ^= hash << 16;
- hash ^= data[2] << 18;
- hash += hash >> 11;
- break;
- case 2: hash += get_le16(data);
- hash ^= hash << 11;
- hash += hash >> 17;
- break;
- case 1: hash += *data;
- hash ^= hash << 10;
- hash += hash >> 1;
- }
- /* Force "avalanching" of final 127 bits */
- hash ^= hash << 3;
- hash += hash >> 5;
- hash ^= hash << 4;
- hash += hash >> 17;
- hash ^= hash << 25;
- hash += hash >> 6;
- return hash;
- }
- bool lmo_load(lmo_catalog_t *cat, const char *file)
- {
- int fd = -1;
- struct stat s;
- cat->data = MAP_FAILED;
- fd = open(file, O_RDONLY|O_CLOEXEC);
- if (fd < 0)
- goto err;
- if (fstat(fd, &s))
- goto err;
- cat->data = mmap(NULL, s.st_size, PROT_READ, MAP_SHARED, fd, 0);
- close(fd);
- fd = -1;
- if (cat->data == MAP_FAILED)
- goto err;
- cat->end = cat->data + s.st_size;
- uint32_t idx_offset = get_be32(cat->end - sizeof(uint32_t));
- cat->index = (const lmo_entry_t *)(cat->data + idx_offset);
- if ((const char *)cat->index > (cat->end - sizeof(uint32_t)))
- goto err;
- cat->length = (cat->end - sizeof(uint32_t) - (const char *)cat->index) / sizeof(lmo_entry_t);
- return true;
- err:
- if (fd >= 0)
- close(fd);
- if (cat->data != MAP_FAILED)
- munmap(cat->data, cat->end - cat->data);
- return false;
- }
- void lmo_unload(lmo_catalog_t *cat)
- {
- if (cat->data != MAP_FAILED)
- munmap(cat->data, cat->end - cat->data);
- }
- static int lmo_compare_entry(const void *a, const void *b)
- {
- const lmo_entry_t *ea = a, *eb = b;
- uint32_t ka = ntohl(ea->key_id), kb = ntohl(eb->key_id);
- if (ka < kb)
- return -1;
- else if (ka > kb)
- return 1;
- else
- return 0;
- }
- static const lmo_entry_t * lmo_find_entry(const lmo_catalog_t *cat, uint32_t hash)
- {
- lmo_entry_t key;
- key.key_id = htonl(hash);
- return bsearch(&key, cat->index, cat->length, sizeof(lmo_entry_t), lmo_compare_entry);
- }
- bool lmo_translate(const lmo_catalog_t *cat, const char *key, size_t keylen, const char **out, size_t *outlen)
- {
- uint32_t hash = sfh_hash(key, keylen);
- const lmo_entry_t *e = lmo_find_entry(cat, hash);
- if (!e)
- return false;
- *out = cat->data + ntohl(e->offset);
- *outlen = ntohl(e->length);
- if (*out + *outlen > cat->end)
- return false;
- return true;
- }
|