fs/hfs/bitops.c

   1 /*
   2  * linux/fs/hfs/bitops.c
   3  *
   4  * Copyright (C) 1996  Paul H. Hargrove
   5  * This file may be distributed under the terms of the GNU Public License.
   6  *
   7  * This file contains functions to handle bitmaps in "left-to-right"
   8  * bit-order such that the MSB of a 32-bit big-endian word is bit 0.
   9  * (This corresponds to bit 7 of a 32-bit little-endian word.)
  10  *
  11  * I have tested and confirmed that the results are identical on the
  12  * Intel x86, PowerPC and DEC Alpha processors.
  13  *
  14  * "XXX" in a comment is a note to myself to consider changing something.
  15  */
  16
  17 #include "hfs.h"
  18
  19 /*================ Global functions ================*/
  20
  21 /*
  22  * hfs_find_zero_bit()
  23  *
  24  * Description:
  25  *  Given a block of memory, its length in bits, and a starting bit number,
  26  *  determine the number of the first zero bits (in left-to-right ordering)
  27  *  in that range.
  28  *
  29  *  Returns >= 'size' if no zero bits are found in the range.
  30  *
  31  *  Accesses memory in 32-bit aligned chunks of 32-bits and thus
  32  *  may read beyond the 'size'th bit.
  33  */
  34 hfs_u32 hfs_find_zero_bit(const hfs_u32 *start, hfs_u32 size, hfs_u32 offset)
  35 {
  36         const hfs_u32 *end   = start + ((size + 31) >> 5);
  37         const hfs_u32 *curr  = start + (offset >> 5);
  38         int bit = offset % 32;
  39
  40         if (offset < size) {
  41                 /* scan the first partial hfs_u32 for zero bits */
  42                 if (bit != 0) {
  43                         do {
  44                                 if (!hfs_test_bit(bit, curr)) {
  45                                         goto done;
  46                                 }
  47                                 ++bit;
  48                         } while (bit < 32);
  49                         bit = 0;
  50                         ++curr;
  51                 }
  52
  53                 /* scan complete hfs_u32s for the first zero bit */
  54                 while (curr < end) {
  55                         if (*curr == ~((hfs_u32)0)) {
  56                                 ++curr;
  57                         } else {
  58                                 while (hfs_test_bit(bit, curr)) {
  59                                         ++bit;
  60                                 }
  61                                 break;
  62                         }
  63                 }
  64
  65 done:
  66                 bit |= (curr - start) << 5;
  67                 return bit;
  68         } else {
  69                 return size;
  70         }
  71 }
  72
  73 /*
  74  * hfs_count_zero_bits()
  75  *
  76  * Description:
  77  *  Given a block of memory, its length in bits, and a starting bit number,
  78  *  determine the number of consecutive zero bits (in left-to-right ordering)
  79  *  in that range.
  80  *
  81  *  Accesses memory in 32-bit aligned chunks of 32-bits and thus
  82  *  may read beyond the 'size'th bit.
  83  */
  84 hfs_u32 hfs_count_zero_bits(const hfs_u32 *start, hfs_u32 size, hfs_u32 offset)
  85 {
  86         const hfs_u32 *end   = start + ((size + 31) >> 5);
  87         const hfs_u32 *curr  = start + (offset >> 5);
  88         int bit = offset % 32;
  89
  90         if (offset < size) {
  91                 /* scan the first partial hfs_u32 for one bits */
  92                 if (bit != 0) {
  93                         do {
  94                                 if (hfs_test_bit(bit, curr)) {
  95                                         goto done;
  96                                 }
  97                                 ++bit;
  98                         } while (bit < 32);
  99                         bit = 0;
 100                         ++curr;
 101                 }
 102
 103                 /* scan complete hfs_u32s for the first one bit */
 104                 while (curr < end) {
 105                         if (*curr == ((hfs_u32)0)) {
 106                                 ++curr;
 107                         } else {
 108                                 while (!hfs_test_bit(bit, curr)) {
 109                                         ++bit;
 110                                 }
 111                                 break;
 112                         }
 113                 }
 114
 115 done:
 116                 bit |= (curr - start) << 5;
 117                 if (bit > size) {
 118                         bit = size;
 119                 }
 120                 return bit - offset;
 121         } else {
 122                 return 0;
 123         }
 124 }