xfs_bit.c 7.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296
  1. /*
  2. * Copyright (c) 2000-2005 Silicon Graphics, Inc.
  3. * All Rights Reserved.
  4. *
  5. * This program is free software; you can redistribute it and/or
  6. * modify it under the terms of the GNU General Public License as
  7. * published by the Free Software Foundation.
  8. *
  9. * This program is distributed in the hope that it would 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 General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with this program; if not, write the Free Software Foundation,
  16. * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  17. */
  18. #include "xfs.h"
  19. #include "xfs_bit.h"
  20. #include "xfs_log.h"
  21. #include "xfs_trans.h"
  22. #include "xfs_buf_item.h"
  23. /*
  24. * XFS bit manipulation routines, used in non-realtime code.
  25. */
  26. #ifndef HAVE_ARCH_HIGHBIT
  27. /*
  28. * Index of high bit number in byte, -1 for none set, 0..7 otherwise.
  29. */
  30. static const char xfs_highbit[256] = {
  31. -1, 0, 1, 1, 2, 2, 2, 2, /* 00 .. 07 */
  32. 3, 3, 3, 3, 3, 3, 3, 3, /* 08 .. 0f */
  33. 4, 4, 4, 4, 4, 4, 4, 4, /* 10 .. 17 */
  34. 4, 4, 4, 4, 4, 4, 4, 4, /* 18 .. 1f */
  35. 5, 5, 5, 5, 5, 5, 5, 5, /* 20 .. 27 */
  36. 5, 5, 5, 5, 5, 5, 5, 5, /* 28 .. 2f */
  37. 5, 5, 5, 5, 5, 5, 5, 5, /* 30 .. 37 */
  38. 5, 5, 5, 5, 5, 5, 5, 5, /* 38 .. 3f */
  39. 6, 6, 6, 6, 6, 6, 6, 6, /* 40 .. 47 */
  40. 6, 6, 6, 6, 6, 6, 6, 6, /* 48 .. 4f */
  41. 6, 6, 6, 6, 6, 6, 6, 6, /* 50 .. 57 */
  42. 6, 6, 6, 6, 6, 6, 6, 6, /* 58 .. 5f */
  43. 6, 6, 6, 6, 6, 6, 6, 6, /* 60 .. 67 */
  44. 6, 6, 6, 6, 6, 6, 6, 6, /* 68 .. 6f */
  45. 6, 6, 6, 6, 6, 6, 6, 6, /* 70 .. 77 */
  46. 6, 6, 6, 6, 6, 6, 6, 6, /* 78 .. 7f */
  47. 7, 7, 7, 7, 7, 7, 7, 7, /* 80 .. 87 */
  48. 7, 7, 7, 7, 7, 7, 7, 7, /* 88 .. 8f */
  49. 7, 7, 7, 7, 7, 7, 7, 7, /* 90 .. 97 */
  50. 7, 7, 7, 7, 7, 7, 7, 7, /* 98 .. 9f */
  51. 7, 7, 7, 7, 7, 7, 7, 7, /* a0 .. a7 */
  52. 7, 7, 7, 7, 7, 7, 7, 7, /* a8 .. af */
  53. 7, 7, 7, 7, 7, 7, 7, 7, /* b0 .. b7 */
  54. 7, 7, 7, 7, 7, 7, 7, 7, /* b8 .. bf */
  55. 7, 7, 7, 7, 7, 7, 7, 7, /* c0 .. c7 */
  56. 7, 7, 7, 7, 7, 7, 7, 7, /* c8 .. cf */
  57. 7, 7, 7, 7, 7, 7, 7, 7, /* d0 .. d7 */
  58. 7, 7, 7, 7, 7, 7, 7, 7, /* d8 .. df */
  59. 7, 7, 7, 7, 7, 7, 7, 7, /* e0 .. e7 */
  60. 7, 7, 7, 7, 7, 7, 7, 7, /* e8 .. ef */
  61. 7, 7, 7, 7, 7, 7, 7, 7, /* f0 .. f7 */
  62. 7, 7, 7, 7, 7, 7, 7, 7, /* f8 .. ff */
  63. };
  64. #endif
  65. /*
  66. * Count of bits set in byte, 0..8.
  67. */
  68. static const char xfs_countbit[256] = {
  69. 0, 1, 1, 2, 1, 2, 2, 3, /* 00 .. 07 */
  70. 1, 2, 2, 3, 2, 3, 3, 4, /* 08 .. 0f */
  71. 1, 2, 2, 3, 2, 3, 3, 4, /* 10 .. 17 */
  72. 2, 3, 3, 4, 3, 4, 4, 5, /* 18 .. 1f */
  73. 1, 2, 2, 3, 2, 3, 3, 4, /* 20 .. 27 */
  74. 2, 3, 3, 4, 3, 4, 4, 5, /* 28 .. 2f */
  75. 2, 3, 3, 4, 3, 4, 4, 5, /* 30 .. 37 */
  76. 3, 4, 4, 5, 4, 5, 5, 6, /* 38 .. 3f */
  77. 1, 2, 2, 3, 2, 3, 3, 4, /* 40 .. 47 */
  78. 2, 3, 3, 4, 3, 4, 4, 5, /* 48 .. 4f */
  79. 2, 3, 3, 4, 3, 4, 4, 5, /* 50 .. 57 */
  80. 3, 4, 4, 5, 4, 5, 5, 6, /* 58 .. 5f */
  81. 2, 3, 3, 4, 3, 4, 4, 5, /* 60 .. 67 */
  82. 3, 4, 4, 5, 4, 5, 5, 6, /* 68 .. 6f */
  83. 3, 4, 4, 5, 4, 5, 5, 6, /* 70 .. 77 */
  84. 4, 5, 5, 6, 5, 6, 6, 7, /* 78 .. 7f */
  85. 1, 2, 2, 3, 2, 3, 3, 4, /* 80 .. 87 */
  86. 2, 3, 3, 4, 3, 4, 4, 5, /* 88 .. 8f */
  87. 2, 3, 3, 4, 3, 4, 4, 5, /* 90 .. 97 */
  88. 3, 4, 4, 5, 4, 5, 5, 6, /* 98 .. 9f */
  89. 2, 3, 3, 4, 3, 4, 4, 5, /* a0 .. a7 */
  90. 3, 4, 4, 5, 4, 5, 5, 6, /* a8 .. af */
  91. 3, 4, 4, 5, 4, 5, 5, 6, /* b0 .. b7 */
  92. 4, 5, 5, 6, 5, 6, 6, 7, /* b8 .. bf */
  93. 2, 3, 3, 4, 3, 4, 4, 5, /* c0 .. c7 */
  94. 3, 4, 4, 5, 4, 5, 5, 6, /* c8 .. cf */
  95. 3, 4, 4, 5, 4, 5, 5, 6, /* d0 .. d7 */
  96. 4, 5, 5, 6, 5, 6, 6, 7, /* d8 .. df */
  97. 3, 4, 4, 5, 4, 5, 5, 6, /* e0 .. e7 */
  98. 4, 5, 5, 6, 5, 6, 6, 7, /* e8 .. ef */
  99. 4, 5, 5, 6, 5, 6, 6, 7, /* f0 .. f7 */
  100. 5, 6, 6, 7, 6, 7, 7, 8, /* f8 .. ff */
  101. };
  102. /*
  103. * xfs_highbit32: get high bit set out of 32-bit argument, -1 if none set.
  104. */
  105. inline int
  106. xfs_highbit32(
  107. __uint32_t v)
  108. {
  109. #ifdef HAVE_ARCH_HIGHBIT
  110. return highbit32(v);
  111. #else
  112. int i;
  113. if (v & 0xffff0000)
  114. if (v & 0xff000000)
  115. i = 24;
  116. else
  117. i = 16;
  118. else if (v & 0x0000ffff)
  119. if (v & 0x0000ff00)
  120. i = 8;
  121. else
  122. i = 0;
  123. else
  124. return -1;
  125. return i + xfs_highbit[(v >> i) & 0xff];
  126. #endif
  127. }
  128. /*
  129. * xfs_lowbit64: get low bit set out of 64-bit argument, -1 if none set.
  130. */
  131. int
  132. xfs_lowbit64(
  133. __uint64_t v)
  134. {
  135. __uint32_t w = (__uint32_t)v;
  136. int n = 0;
  137. if (w) { /* lower bits */
  138. n = ffs(w);
  139. } else { /* upper bits */
  140. w = (__uint32_t)(v >> 32);
  141. if (w && (n = ffs(w)))
  142. n += 32;
  143. }
  144. return n - 1;
  145. }
  146. /*
  147. * xfs_highbit64: get high bit set out of 64-bit argument, -1 if none set.
  148. */
  149. int
  150. xfs_highbit64(
  151. __uint64_t v)
  152. {
  153. __uint32_t h = (__uint32_t)(v >> 32);
  154. if (h)
  155. return xfs_highbit32(h) + 32;
  156. return xfs_highbit32((__uint32_t)v);
  157. }
  158. /*
  159. * Count the number of bits set in the bitmap starting with bit
  160. * start_bit. Size is the size of the bitmap in words.
  161. *
  162. * Do the counting by mapping a byte value to the number of set
  163. * bits for that value using the xfs_countbit array, i.e.
  164. * xfs_countbit[0] == 0, xfs_countbit[1] == 1, xfs_countbit[2] == 1,
  165. * xfs_countbit[3] == 2, etc.
  166. */
  167. int
  168. xfs_count_bits(uint *map, uint size, uint start_bit)
  169. {
  170. register int bits;
  171. register unsigned char *bytep;
  172. register unsigned char *end_map;
  173. int byte_bit;
  174. bits = 0;
  175. end_map = (char*)(map + size);
  176. bytep = (char*)(map + (start_bit & ~0x7));
  177. byte_bit = start_bit & 0x7;
  178. /*
  179. * If the caller fell off the end of the map, return 0.
  180. */
  181. if (bytep >= end_map) {
  182. return (0);
  183. }
  184. /*
  185. * If start_bit is not byte aligned, then process the
  186. * first byte separately.
  187. */
  188. if (byte_bit != 0) {
  189. /*
  190. * Shift off the bits we don't want to look at,
  191. * before indexing into xfs_countbit.
  192. */
  193. bits += xfs_countbit[(*bytep >> byte_bit)];
  194. bytep++;
  195. }
  196. /*
  197. * Count the bits in each byte until the end of the bitmap.
  198. */
  199. while (bytep < end_map) {
  200. bits += xfs_countbit[*bytep];
  201. bytep++;
  202. }
  203. return (bits);
  204. }
  205. /*
  206. * Count the number of contiguous bits set in the bitmap starting with bit
  207. * start_bit. Size is the size of the bitmap in words.
  208. */
  209. int
  210. xfs_contig_bits(uint *map, uint size, uint start_bit)
  211. {
  212. uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
  213. uint result = 0;
  214. uint tmp;
  215. size <<= BIT_TO_WORD_SHIFT;
  216. ASSERT(start_bit < size);
  217. size -= start_bit & ~(NBWORD - 1);
  218. start_bit &= (NBWORD - 1);
  219. if (start_bit) {
  220. tmp = *p++;
  221. /* set to one first offset bits prior to start */
  222. tmp |= (~0U >> (NBWORD-start_bit));
  223. if (tmp != ~0U)
  224. goto found;
  225. result += NBWORD;
  226. size -= NBWORD;
  227. }
  228. while (size) {
  229. if ((tmp = *p++) != ~0U)
  230. goto found;
  231. result += NBWORD;
  232. size -= NBWORD;
  233. }
  234. return result - start_bit;
  235. found:
  236. return result + ffz(tmp) - start_bit;
  237. }
  238. /*
  239. * This takes the bit number to start looking from and
  240. * returns the next set bit from there. It returns -1
  241. * if there are no more bits set or the start bit is
  242. * beyond the end of the bitmap.
  243. *
  244. * Size is the number of words, not bytes, in the bitmap.
  245. */
  246. int xfs_next_bit(uint *map, uint size, uint start_bit)
  247. {
  248. uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
  249. uint result = start_bit & ~(NBWORD - 1);
  250. uint tmp;
  251. size <<= BIT_TO_WORD_SHIFT;
  252. if (start_bit >= size)
  253. return -1;
  254. size -= result;
  255. start_bit &= (NBWORD - 1);
  256. if (start_bit) {
  257. tmp = *p++;
  258. /* set to zero first offset bits prior to start */
  259. tmp &= (~0U << start_bit);
  260. if (tmp != 0U)
  261. goto found;
  262. result += NBWORD;
  263. size -= NBWORD;
  264. }
  265. while (size) {
  266. if ((tmp = *p++) != 0U)
  267. goto found;
  268. result += NBWORD;
  269. size -= NBWORD;
  270. }
  271. return -1;
  272. found:
  273. return result + ffs(tmp) - 1;
  274. }