123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208 |
- /* -*- mode:c; c-file-style:"k&r"; c-basic-offset: 4; tab-width:4; indent-tabs-mode:nil; mode:auto-fill; fill-column:78; -*- */
- /* vim: set ts=4 sw=4 et tw=78 fo=cqt wm=0: */
- /* Copyright (C) 2014 Stony Brook University
- This file is part of Graphene Library OS.
- Graphene Library OS is free software: you can redistribute it and/or
- modify it under the terms of the GNU Lesser General Public License
- as published by the Free Software Foundation, either version 3 of the
- License, or (at your option) any later version.
- Graphene Library OS is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU Lesser General Public License for more details.
- You should have received a copy of the GNU Lesser General Public License
- along with this program. If not, see <http://www.gnu.org/licenses/>. */
- /*
- * shim_fs_hash.c
- *
- * This file contains functions to generate hash values for FS paths.
- */
- #include <shim_internal.h>
- #include <shim_fs.h>
- #include <shim_utils.h>
- #include <pal.h>
- #include <pal_error.h>
- static inline unsigned int fold_hash(unsigned long hash)
- {
- hash += hash >> (8*sizeof(int));
- return hash;
- }
- uint64_t hash_one(const char *name, unsigned int len)
- {
- unsigned long a = 0;
- unsigned long mask = 0;
- uint64_t hash = 0;
- //debug ("Hashing %s, len %d seed %llx\n", name, len, hash);
- for (;;) {
- if (len < sizeof(unsigned long)) {
- a = 0;
- while (len) {
- a += *name;
- a <<= 8;
- name++;
- len--;
- }
- } else {
- a = *((unsigned long *) name);
- len -= sizeof(unsigned long);
- }
- hash += a;
- hash *= 9;
- name += sizeof(unsigned long);
- if (!len)
- goto done;
- }
- mask = ~(~0ul << len*8);
- hash += mask & a;
- done:
- hash = fold_hash(hash);
- //debug("Hash returning %llx\n", hash);
- return hash;
- }
- static inline int __check_sep (int c, const char * sep)
- {
- if (!*sep)
- return 0;
- if (!*(sep + 1))
- return c == *sep;
- if (!*(sep + 2))
- return c == *sep || c == *(sep + 1);
- for (const char * t = sep ; *sep ; sep++)
- if (c == *t)
- return 1;
- return 0;
- }
- static inline uint64_t __hash_path (const char * path,
- int size, const char * sep)
- {
- uint64_t hash = 0;
- uint64_t digest = 0;
- const char * next_name = path;
- const char * c = path;
- while (c < path + size && *c) {
- if (__check_sep(*c, sep)) {
- if (next_name < c) {
- hash = hash_one(next_name, c - next_name);
- digest ^= hash;
- }
- next_name = c + 1;
- }
- c++;
- }
- if (next_name < c) {
- hash = hash_one(next_name, c - next_name);
- digest ^= hash;
- }
- return digest;
- }
- HASHTYPE hash_path (const char * path, int size,
- const char * sep)
- {
- return __hash_path(path, size, sep ? sep : "/");
- }
- HASHTYPE hash_parent_path (HASHTYPE hbuf, const char * path,
- int * size, const char * sep)
- {
- if (*size < 0)
- *size = strlen (path);
- if (*size == 0)
- goto zero;
- sep = sep ? sep : "/";
- const char * last_name = path + *size;
- const char * last_frame_end = path + *size;
- while (last_name > path) {
- if (__check_sep(*(last_name - 1), sep)) {
- if (last_name < last_frame_end)
- break;
- last_frame_end = last_name - 1;
- }
- last_name--;
- }
- const char * parent_end = last_name - 1;
- while (parent_end > path && !__check_sep(*parent_end, sep))
- parent_end--;
- if (parent_end <= path)
- goto zero;
- HASHTYPE hash = 0;
- hash = hash_one(last_name, last_frame_end - last_name);
- hbuf ^= hash;
- *size = parent_end - path;
- return hbuf;
- zero:
- hbuf = 0;
- *size = 0;
- return 0;
- }
- HASHTYPE rehash_name (HASHTYPE parent_hbuf,
- const char * name, int size)
- {
- HASHTYPE ret = 0;
- ret = hash_one(name, size);
- ret ^= parent_hbuf;
- return ret;
- }
- HASHTYPE rehash_path (HASHTYPE ancester_hbuf,
- const char * path, int size, const char * sep)
- {
- HASHTYPE ctx = 0;
- HASHTYPE digest = 0;
- HASHTYPE hbuf;
- sep = sep ? : "/";
- const char * next_name = path;
- const char * c = path;
- while (c < path + size && *c) {
- if (__check_sep(*c, sep)) {
- if (next_name < c) {
- ctx = hash_one(next_name, c - next_name);
- digest ^= ctx;
- }
- next_name = c + 1;
- }
- c++;
- }
- if (next_name < c) {
- ctx = hash_one(next_name, c - next_name);
- digest ^= ctx;
- }
- hbuf = ancester_hbuf ^ digest;
- return hbuf;
- }
|