The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/fs/hfs/bitops.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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 General 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 }

Cache object: 57fee245e07e9c890153f2cd71ab0087


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.