shim_fs_hash.c 4.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208
  1. /* -*- mode:c; c-file-style:"k&r"; c-basic-offset: 4; tab-width:4; indent-tabs-mode:nil; mode:auto-fill; fill-column:78; -*- */
  2. /* vim: set ts=4 sw=4 et tw=78 fo=cqt wm=0: */
  3. /* Copyright (C) 2014 Stony Brook University
  4. This file is part of Graphene Library OS.
  5. Graphene Library OS is free software: you can redistribute it and/or
  6. modify it under the terms of the GNU Lesser General Public License
  7. as published by the Free Software Foundation, either version 3 of the
  8. License, or (at your option) any later version.
  9. Graphene Library OS is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU Lesser General Public License for more details.
  13. You should have received a copy of the GNU Lesser General Public License
  14. along with this program. If not, see <http://www.gnu.org/licenses/>. */
  15. /*
  16. * shim_fs_hash.c
  17. *
  18. * This file contains functions to generate hash values for FS paths.
  19. */
  20. #include <shim_internal.h>
  21. #include <shim_fs.h>
  22. #include <shim_utils.h>
  23. #include <pal.h>
  24. #include <pal_error.h>
  25. static inline unsigned int fold_hash(unsigned long hash)
  26. {
  27. hash += hash >> (8*sizeof(int));
  28. return hash;
  29. }
  30. uint64_t hash_one(const char *name, unsigned int len)
  31. {
  32. unsigned long a = 0;
  33. unsigned long mask = 0;
  34. uint64_t hash = 0;
  35. //debug ("Hashing %s, len %d seed %llx\n", name, len, hash);
  36. for (;;) {
  37. if (len < sizeof(unsigned long)) {
  38. a = 0;
  39. while (len) {
  40. a += *name;
  41. a <<= 8;
  42. name++;
  43. len--;
  44. }
  45. } else {
  46. a = *((unsigned long *) name);
  47. len -= sizeof(unsigned long);
  48. }
  49. hash += a;
  50. hash *= 9;
  51. name += sizeof(unsigned long);
  52. if (!len)
  53. goto done;
  54. }
  55. mask = ~(~0ul << len*8);
  56. hash += mask & a;
  57. done:
  58. hash = fold_hash(hash);
  59. //debug("Hash returning %llx\n", hash);
  60. return hash;
  61. }
  62. static inline int __check_sep (int c, const char * sep)
  63. {
  64. if (!*sep)
  65. return 0;
  66. if (!*(sep + 1))
  67. return c == *sep;
  68. if (!*(sep + 2))
  69. return c == *sep || c == *(sep + 1);
  70. for (const char * t = sep ; *sep ; sep++)
  71. if (c == *t)
  72. return 1;
  73. return 0;
  74. }
  75. static inline uint64_t __hash_path (const char * path,
  76. int size, const char * sep)
  77. {
  78. uint64_t hash = 0;
  79. uint64_t digest = 0;
  80. const char * next_name = path;
  81. const char * c = path;
  82. while (c < path + size && *c) {
  83. if (__check_sep(*c, sep)) {
  84. if (next_name < c) {
  85. hash = hash_one(next_name, c - next_name);
  86. digest ^= hash;
  87. }
  88. next_name = c + 1;
  89. }
  90. c++;
  91. }
  92. if (next_name < c) {
  93. hash = hash_one(next_name, c - next_name);
  94. digest ^= hash;
  95. }
  96. return digest;
  97. }
  98. HASHTYPE hash_path (const char * path, int size,
  99. const char * sep)
  100. {
  101. return __hash_path(path, size, sep ? sep : "/");
  102. }
  103. HASHTYPE hash_parent_path (HASHTYPE hbuf, const char * path,
  104. int * size, const char * sep)
  105. {
  106. if (*size < 0)
  107. *size = strlen (path);
  108. if (*size == 0)
  109. goto zero;
  110. sep = sep ? sep : "/";
  111. const char * last_name = path + *size;
  112. const char * last_frame_end = path + *size;
  113. while (last_name > path) {
  114. if (__check_sep(*(last_name - 1), sep)) {
  115. if (last_name < last_frame_end)
  116. break;
  117. last_frame_end = last_name - 1;
  118. }
  119. last_name--;
  120. }
  121. const char * parent_end = last_name - 1;
  122. while (parent_end > path && !__check_sep(*parent_end, sep))
  123. parent_end--;
  124. if (parent_end <= path)
  125. goto zero;
  126. HASHTYPE hash = 0;
  127. hash = hash_one(last_name, last_frame_end - last_name);
  128. hbuf ^= hash;
  129. *size = parent_end - path;
  130. return hbuf;
  131. zero:
  132. hbuf = 0;
  133. *size = 0;
  134. return 0;
  135. }
  136. HASHTYPE rehash_name (HASHTYPE parent_hbuf,
  137. const char * name, int size)
  138. {
  139. HASHTYPE ret = 0;
  140. ret = hash_one(name, size);
  141. ret ^= parent_hbuf;
  142. return ret;
  143. }
  144. HASHTYPE rehash_path (HASHTYPE ancester_hbuf,
  145. const char * path, int size, const char * sep)
  146. {
  147. HASHTYPE ctx = 0;
  148. HASHTYPE digest = 0;
  149. HASHTYPE hbuf;
  150. sep = sep ? : "/";
  151. const char * next_name = path;
  152. const char * c = path;
  153. while (c < path + size && *c) {
  154. if (__check_sep(*c, sep)) {
  155. if (next_name < c) {
  156. ctx = hash_one(next_name, c - next_name);
  157. digest ^= ctx;
  158. }
  159. next_name = c + 1;
  160. }
  161. c++;
  162. }
  163. if (next_name < c) {
  164. ctx = hash_one(next_name, c - next_name);
  165. digest ^= ctx;
  166. }
  167. hbuf = ancester_hbuf ^ digest;
  168. return hbuf;
  169. }